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 --- 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