[PATCH v2 next 11/15] kallsyms: scripts/kallsyms: Keep full expansion of tokens

[David Laight <david.laight.linux@gmail.com>]

Expand the full string when a new token is allocated.
Saves the recursive expansions later on.
It probably means that token 0 could be used earlier, but the reverse
order is maintained so that the output files can be compared.

The entries for the initial tokens [0-9A-Za-z_.] are now no different
and don't need special casing.

No change to generated output.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 scripts/kallsyms.c | 117 +++++++++++++++++++++++----------------------
 1 file changed, 60 insertions(+), 57 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 5603b2a6c77b..9e1bc0fdaa9f 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -74,8 +74,8 @@ static int token_profit[0x10000];
 
 /* the table that holds the result of the compression */
 static struct token_table {
-	unsigned short len;
-	unsigned char  ch[2];
+	char           *str;		/* Full expansion, '\0' terminated */
+	unsigned short len;		/* Length of str */
 } token_table[256];
 
 static void usage(void)
@@ -301,29 +301,17 @@ static void output_value(const char *label, unsigned int value)
 	printf("\n");
 }
 
-/* uncompress a compressed symbol. When this function is called, the best table
- * might still be compressed itself, so the function needs to be recursive */
-static int expand_symbol(const unsigned char *data, int len, char *result)
+static unsigned int expand_symbol(const unsigned char *data, int len, char *result)
 {
-	int c, rlen, total=0;
-
-	while (len) {
-		c = *data;
-		/* if the table holds a single char that is the same as the one
-		 * we are looking for, then end the search */
-		if (token_table[c].ch[0] == c && token_table[c].len == 1) {
-			*result++ = c;
-			total++;
-		} else {
-			/* if not, recurse and expand */
-			rlen = expand_symbol(token_table[c].ch, token_table[c].len, result);
-			total += rlen;
-			result += rlen;
-		}
-		data++;
-		len--;
+	struct token_table *tt;
+	unsigned int total = 0;
+
+	while (len--) {
+		tt = token_table + *data++;
+		memcpy(result + total, tt->str, tt->len);
+		total += tt->len;
 	}
-	*result=0;
+	result[total] = 0;
 
 	return total;
 }
@@ -396,8 +384,8 @@ static void write_src(void)
 		 * Now that we wrote out the compressed symbol name, restore the
 		 * original name and print it in the comment.
 		 */
-		expand_symbol(se->sym, se->len, buf);
-		strcpy((char *)se->sym, buf);
+		se->len = expand_symbol(se->sym, se->len, buf);
+		memcpy(se->sym, buf, se->len + 1);
 		printf("\t/* %s */\n", se->sym);
 	}
 	table_size = off;
@@ -415,9 +403,8 @@ static void write_src(void)
 	off = 0;
 	for (i = 0; i < 256; i++) {
 		best_idx[i] = off;
-		expand_symbol(token_table[i].ch, token_table[i].len, buf);
-		printf("\t.asciz\t\"%s\"\n", buf);
-		off += strlen(buf) + 1;
+		off += token_table[i].len + 1;
+		printf("\t.asciz\t\"%s\"\n", token_table[i].str);
 	}
 	printf(".size kallsyms_token_table, . - kallsyms_token_table\n");
 	printf("\n");
@@ -454,7 +441,8 @@ static void write_src(void)
 	for (i = 0; i < symbol_cnt; i++) {
 		se = symbol[i];
 		off = se->seq << 1;
-		if (i && !strcmp((char *)symbol[i - 1]->sym + 1, (char *)se->sym + 1))
+		if (i && symbol[i - 1]->len == se->len &&
+		    !memcmp(symbol[i - 1]->sym + 1, se->sym + 1, se->len - 1))
 			/* Mark that this is a duplicate of the previous symbol */
 			off |= 1;
 		if (off_size == 24) {
@@ -510,20 +498,22 @@ static void build_initial_token_table(void)
 }
 
 static unsigned char *find_token(unsigned char *str, int len,
-				 const unsigned char *token)
+				 unsigned int want)
 {
+	unsigned int token = PAIR(0, *str++);
 	int i;
 
 	for (i = 0; i < len - 1; i++) {
-		if (str[i] == token[0] && str[i+1] == token[1])
-			return &str[i];
+		token = PAIR(RIGHT(token), *str++);
+		if (token == want)
+			return str - 2;
 	}
 	return NULL;
 }
 
 /* replace a given token in all the valid symbols. Use the sampled symbols
  * to update the counts */
-static void compress_symbols(const unsigned char *str, int idx)
+static void compress_symbols(unsigned int token_pair, int idx)
 {
 	unsigned int i, len, size;
 	unsigned char *p1, *p2;
@@ -534,7 +524,7 @@ static void compress_symbols(const unsigned char *str, int idx)
 		p1 = symbol[i]->sym;
 
 		/* find the token on the symbol */
-		p2 = find_token(p1, len, str);
+		p2 = find_token(p1, len, token_pair);
 		if (!p2) continue;
 
 		/* decrease the counts for this symbol's tokens */
@@ -553,7 +543,7 @@ static void compress_symbols(const unsigned char *str, int idx)
 			if (size < 2) break;
 
 			/* find the token on the symbol */
-			p2 = find_token(p1, size, str);
+			p2 = find_token(p1, size, token_pair);
 
 		} while (p2);
 
@@ -569,8 +559,8 @@ static int find_best_token(void)
 {
 	int i, best, bestprofit;
 
-	bestprofit=-10000;
-	best = 0;
+	bestprofit = 0;
+	best = -1;
 
 	for (i = 0; i < 0x10000; i++) {
 		if (token_profit[i] > bestprofit) {
@@ -585,43 +575,56 @@ static int find_best_token(void)
 static void optimize_result(void)
 {
 	int i, best;
+	unsigned int len;
+	struct token_table *left, *right;
+	char *str;
 
-	/* using the '\0' symbol last allows compress_symbols to use standard
-	 * fast string functions */
+	/* Use the '\0' symbol last so the output is unchanged */
 	for (i = 255; i >= 0; i--) {
+		/* Ignore tokens used for the original character codes. */
+		if (token_table[i].len)
+			continue;
 
-		/* if this table slot is empty (it is not used by an actual
-		 * original char code */
-		if (!token_table[i].len) {
+		/* find the token pair with the best profit value */
+		best = find_best_token();
+		if (best < 0)
+			break;
 
-			/* find the token with the best profit value */
-			best = find_best_token();
-			if (token_profit[best] == 0)
-				break;
+		/* replace this token pair in all the valid symbols */
+		compress_symbols(best, i);
 
-			/* place it in the "best" table */
-			token_table[i].len = 2;
-			token_table[i].ch[0] = LEFT(best);
-			token_table[i].ch[1] = RIGHT(best);
+		/* Generate the full name for this symbol */
+		left = &token_table[LEFT(best)];
+		right = &token_table[RIGHT(best)];
 
-			/* replace this token in all the valid symbols */
-			compress_symbols(token_table[i].ch, i);
-		}
+		len = left->len + right->len;
+		str = xmalloc(len + 1);
+		str[len] = 0;
+		memcpy(str, left->str, left->len);
+		memcpy(str + left->len, right->str, right->len);
+		token_table[i].str = str;
+		token_table[i].len = len;
 	}
 }
 
 /* start by placing the symbols that are actually used on the table */
 static void insert_real_symbols_in_table(void)
 {
-	unsigned int i, j, c;
+	unsigned int i, j;
 
 	for (i = 0; i < symbol_cnt; i++) {
 		for (j = 0; j < symbol[i]->len; j++) {
-			c = symbol[i]->sym[j];
-			token_table[c].ch[0] = c;
-			token_table[c].len = 1;
+			token_table[symbol[i]->sym[j]].len = 1;
 		}
 	}
+
+	for (i = 0; i <= 255; i++) {
+		if (!token_table[i].len)
+			continue;
+		token_table[i].str = xmalloc(2);
+		token_table[i].str[0] = i;
+		token_table[i].str[1] = 0;
+	}
 }
 
 static void optimize_token_table(void)
-- 
2.39.5