+
+ output_label("kallsyms_markers");
+ for (i = 0; i < ((table_cnt + 255) >> 8); i++)
+ printf("\tPTR\t%d\n", markers[i]);
+ printf("\n");
+
+ free(markers);
+
+ output_label("kallsyms_token_table");
+ off = 0;
+ for (i = 0; i < 256; i++) {
+ best_idx[i] = off;
+ expand_symbol(best_table[i], best_table_len[i], buf);
+ printf("\t.asciz\t\"%s\"\n", buf);
+ off += strlen(buf) + 1;
+ }
+ printf("\n");
+
+ output_label("kallsyms_token_index");
+ for (i = 0; i < 256; i++)
+ printf("\t.short\t%d\n", best_idx[i]);
+ printf("\n");
+}
+
+
+/* table lookup compression functions */
+
+/* count all the possible tokens in a symbol */
+static void learn_symbol(unsigned char *symbol, int len)
+{
+ int i;
+
+ for (i = 0; i < len - 1; i++)
+ token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
+}
+
+/* decrease the count for all the possible tokens in a symbol */
+static void forget_symbol(unsigned char *symbol, int len)
+{
+ int i;
+
+ for (i = 0; i < len - 1; i++)
+ token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
+}
+
+/* remove all the invalid symbols from the table and do the initial token count */
+static void build_initial_tok_table(void)
+{
+ unsigned int i, pos;
+
+ pos = 0;
+ for (i = 0; i < table_cnt; i++) {
+ if ( symbol_valid(&table[i]) ) {
+ if (pos != i)
+ table[pos] = table[i];
+ learn_symbol(table[pos].sym, table[pos].len);
+ pos++;
+ }
+ }
+ table_cnt = pos;
+}
+
+/* replace a given token in all the valid symbols. Use the sampled symbols
+ * to update the counts */
+static void compress_symbols(unsigned char *str, int idx)
+{
+ unsigned int i, len, size;
+ unsigned char *p1, *p2;
+
+ for (i = 0; i < table_cnt; i++) {
+
+ len = table[i].len;
+ p1 = table[i].sym;
+
+ /* find the token on the symbol */
+ p2 = memmem(p1, len, str, 2);
+ if (!p2) continue;
+
+ /* decrease the counts for this symbol's tokens */
+ forget_symbol(table[i].sym, len);
+
+ size = len;
+
+ do {
+ *p2 = idx;
+ p2++;
+ size -= (p2 - p1);
+ memmove(p2, p2 + 1, size);
+ p1 = p2;
+ len--;
+
+ if (size < 2) break;
+
+ /* find the token on the symbol */
+ p2 = memmem(p1, size, str, 2);
+
+ } while (p2);
+
+ table[i].len = len;
+
+ /* increase the counts for this symbol's new tokens */
+ learn_symbol(table[i].sym, len);
+ }
+}
+
+/* search the token with the maximum profit */
+static int find_best_token(void)
+{
+ int i, best, bestprofit;
+
+ bestprofit=-10000;
+ best = 0;
+
+ for (i = 0; i < 0x10000; i++) {
+ if (token_profit[i] > bestprofit) {
+ best = i;
+ bestprofit = token_profit[i];
+ }
+ }
+ return best;