Name: Huffman Compress Kallsyms Names
Status: Booted on 2.6.7-bk4

If we want to do fast searches (for proc/X/wchan) we should keep an
offset to the name with each address (we currently iterate through all
the names to find the nth one).  But this doesn't sit well with stem
compression, and also enlarges the size of the kernel by 4 bytes per
symbol (ie. about 30k-60k, depending on configuration).

A simple huffman table, calculated at build time, is more effective.
We could use zlib, but we want robustness.

vmlinux before: 2966147
vmlinux after: 2974360

diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.6.7-bk4/kernel/kallsyms.c working-2.6.7-bk4-kallsyms-compress/kernel/kallsyms.c
--- linux-2.6.7-bk4/kernel/kallsyms.c	2004-06-22 10:36:51.000000000 +1000
+++ working-2.6.7-bk4-kallsyms-compress/kernel/kallsyms.c	2004-06-22 21:59:16.000000000 +1000
@@ -14,10 +14,16 @@
 #include <linux/err.h>
 #include <linux/proc_fs.h>
 
+/* jump[0] is where to go if bit is zero, [1] if bit is 1.  Positive
+ * means new location in table, negative means char index. */
+struct huff_table { signed char jump[2]; };
+
 /* These will be re-linked against their real values during the second link stage */
 extern unsigned long kallsyms_addresses[] __attribute__((weak));
 extern unsigned long kallsyms_num_syms __attribute__((weak));
-extern char kallsyms_names[] __attribute__((weak));
+extern unsigned char kallsyms_names[] __attribute__((weak));
+extern unsigned int kallsyms_offsets[] __attribute__((weak));
+extern const struct huff_table kallsyms_huff[] __attribute__((weak));
 
 /* Defined by the linker script. */
 extern char _stext[], _etext[], _sinittext[], _einittext[];
@@ -37,78 +43,117 @@ static inline int is_kernel_text(unsigne
 	return 0;
 }
 
+static inline int get_bit(const unsigned char *addr, unsigned int *bitnum)
+{
+	int bit;
+
+	bit = addr[*bitnum / 8] & (1 << (*bitnum % 8));
+	(*bitnum)++;
+	return !!bit;
+}
+
+static const char huff_chars[]
+= "_0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
+
+static char get_char(const unsigned char *addr, unsigned int *bitnum)
+{
+	int next;
+	unsigned int cursor;
+
+	/* Start at zero, follow jump table. */
+	for (cursor = 0;
+	     (next = kallsyms_huff[cursor].jump[get_bit(addr, bitnum)]) >= 0;
+	     cursor = next) ;
+	return huff_chars[-next - 1];
+}
+
+static unsigned int decode_name(unsigned int bitnum, char outbuf[])
+{
+	unsigned int i;
+
+	for (i = 0; (outbuf[i] = get_char(kallsyms_names, &bitnum)); i++) {
+		if (i == 128) {
+			strcpy(outbuf, "*error*");
+			break;
+		}
+	}
+	return bitnum;
+}
+
 /* Lookup the address for this symbol. Returns 0 if not found. */
 unsigned long kallsyms_lookup_name(const char *name)
 {
 	char namebuf[128];
 	unsigned long i;
-	char *knames;
-
-	for (i = 0, knames = kallsyms_names; i < kallsyms_num_syms; i++) {
-		unsigned prefix = *knames++;
 
-		strlcpy(namebuf + prefix, knames, 127 - prefix);
+	for (i = 0; i < kallsyms_num_syms; i++) {
+		decode_name(kallsyms_offsets[i], namebuf);
 		if (strcmp(namebuf, name) == 0)
 			return kallsyms_addresses[i];
-
-		knames += strlen(knames) + 1;
 	}
 	return module_kallsyms_lookup_name(name);
 }
 
+static unsigned int find_kallsyms_address(unsigned long addr)
+{
+	int first, last, mid = 0;
+
+	first = 0;
+	last = kallsyms_num_syms-1;
+
+	while (first <= last) {
+		mid = (last - first) / 2 + first;
+		if (kallsyms_addresses[mid] < addr)
+			first = mid + 1;
+		else if (kallsyms_addresses[mid] > addr)
+			last = mid - 1;
+		else
+			break;
+	}
+	return mid;
+}
+
 /* Lookup an address.  modname is set to NULL if it's in the kernel. */
 const char *kallsyms_lookup(unsigned long addr,
 			    unsigned long *symbolsize,
 			    unsigned long *offset,
 			    char **modname, char *namebuf)
 {
-	unsigned long i, best = 0;
+	unsigned int i, next;
+	unsigned long symbol_end;
 
 	/* This kernel should never had been booted. */
 	BUG_ON(!kallsyms_addresses);
 
-	namebuf[127] = 0;
-	namebuf[0] = 0;
-
-	if (is_kernel_text(addr) || is_kernel_inittext(addr)) {
-		unsigned long symbol_end;
-		char *name = kallsyms_names;
+	if (addr < kallsyms_addresses[0]
+	    || addr > kallsyms_addresses[kallsyms_num_syms-1])
+		return module_address_lookup(addr,symbolsize,offset,modname);
 
-		/* They're sorted, we could be clever here, but who cares? */
-		for (i = 0; i < kallsyms_num_syms; i++) {
-			if (kallsyms_addresses[i] > kallsyms_addresses[best] &&
-			    kallsyms_addresses[i] <= addr)
-				best = i;
-		}
+	i = find_kallsyms_address(addr);
+	/* Finds nearest address, we want previous address. */
+	while (kallsyms_addresses[i] > addr)
+		i--;
 
-		/* Grab name */
-		for (i = 0; i <= best; i++) { 
-			unsigned prefix = *name++;
-			strncpy(namebuf + prefix, name, 127 - prefix);
-			name += strlen(name) + 1;
-		}
+	decode_name(kallsyms_offsets[i], namebuf);
 
-		/* At worst, symbol ends at end of section. */
-		if (is_kernel_inittext(addr))
-			symbol_end = (unsigned long)_einittext;
-		else
-			symbol_end = (unsigned long)_etext;
+	/* At worst, symbol ends at end of section. */
+	if (is_kernel_inittext(addr))
+		symbol_end = (unsigned long)_einittext;
+	else
+		symbol_end = (unsigned long)_etext;
 
-		/* Search for next non-aliased symbol */
-		for (i = best+1; i < kallsyms_num_syms; i++) {
-			if (kallsyms_addresses[i] > kallsyms_addresses[best]) {
-				symbol_end = kallsyms_addresses[i];
-				break;
-			}
+	/* Search for next non-aliased symbol */
+	for (next = i+1; next < kallsyms_num_syms; next++) {
+		if (kallsyms_addresses[next] > kallsyms_addresses[i]) {
+			symbol_end = kallsyms_addresses[i];
+			break;
 		}
-
-		*symbolsize = symbol_end - kallsyms_addresses[best];
-		*modname = NULL;
-		*offset = addr - kallsyms_addresses[best];
-		return namebuf;
 	}
 
-	return module_address_lookup(addr, symbolsize, offset, modname);
+	*symbolsize = symbol_end - kallsyms_addresses[i];
+	*modname = NULL;
+	*offset = addr - kallsyms_addresses[i];
+	return namebuf;
 }
 
 /* Replace "%s" in format with address, or returns -errno. */
@@ -147,110 +192,63 @@ void __print_symbol(const char *fmt, uns
 	}
 }
 
-/* To avoid O(n^2) iteration, we carry prefix along. */
 struct kallsym_iter
 {
-	loff_t pos;
 	struct module *owner;
 	unsigned long value;
-	unsigned int nameoff; /* If iterating in core kernel symbols */
 	char type;
 	char name[128];
 };
 
-/* Only label it "global" if it is exported. */
-static void upcase_if_global(struct kallsym_iter *iter)
-{
-	if (is_exported(iter->name, iter->owner))
-		iter->type += 'A' - 'a';
-}
-
-static int get_ksymbol_mod(struct kallsym_iter *iter)
-{
-	iter->owner = module_get_kallsym(iter->pos - kallsyms_num_syms,
-					 &iter->value,
-					 &iter->type, iter->name);
-	if (iter->owner == NULL)
-		return 0;
-
-	upcase_if_global(iter);
-	return 1;
-}
-
-/* Returns space to next name. */
-static unsigned long get_ksymbol_core(struct kallsym_iter *iter)
-{
-	unsigned stemlen, off = iter->nameoff;
-
-	/* First char of each symbol name indicates prefix length
-	   shared with previous name (stem compression). */
-	stemlen = kallsyms_names[off++];
-
-	strlcpy(iter->name+stemlen, kallsyms_names + off, 128-stemlen);
-	off += strlen(kallsyms_names + off) + 1;
-	iter->owner = NULL;
-	iter->value = kallsyms_addresses[iter->pos];
-	if (is_kernel_text(iter->value) || is_kernel_inittext(iter->value))
-		iter->type = 't';
-	else
-		iter->type = 'd';
-
-	upcase_if_global(iter);
-	return off - iter->nameoff;
-}
-
-static void reset_iter(struct kallsym_iter *iter)
+static void *fill_iter(struct kallsym_iter *iter, loff_t pos)
 {
-	iter->name[0] = '\0';
-	iter->nameoff = 0;
-	iter->pos = 0;
+	if (pos < kallsyms_num_syms) {
+		decode_name(kallsyms_offsets[pos], iter->name);
+		iter->owner = NULL;
+		iter->value = kallsyms_addresses[pos];
+		if (is_kernel_text(iter->value)
+		    || is_kernel_inittext(iter->value))
+			iter->type = 't';
+		else
+			iter->type = 'd';
+		if (is_exported(iter->name, NULL))
+			iter->type += 'A' - 'a';
+	} else {
+		iter->owner = module_get_kallsym(pos - kallsyms_num_syms,
+						 &iter->value,
+						 &iter->type, iter->name);
+		if (!iter->owner) {
+			kfree(iter);
+			return NULL;
+		}
+	}
+	return iter;
 }
 
-/* Returns false if pos at or past end of file. */
-static int update_iter(struct kallsym_iter *iter, loff_t pos)
+static void *s_start(struct seq_file *m, loff_t *pos)
 {
-	/* Module symbols can be accessed randomly. */
-	if (pos >= kallsyms_num_syms) {
-		iter->pos = pos;
-		return get_ksymbol_mod(iter);
-	}
-	
-	/* If we're past the desired position, reset to start. */
-	if (pos < iter->pos)
-		reset_iter(iter);
+	struct kallsym_iter *iter;
 
-	/* We need to iterate through the previous symbols: can be slow */
-	for (; iter->pos != pos; iter->pos++) {
-		iter->nameoff += get_ksymbol_core(iter);
-		cond_resched();
-	}
-	get_ksymbol_core(iter);
-	return 1;
+	iter = kmalloc(sizeof(*iter), GFP_KERNEL);
+	if (!iter)
+		return ERR_PTR(-ENOMEM);
+	return fill_iter(iter, *pos);
 }
 
 static void *s_next(struct seq_file *m, void *p, loff_t *pos)
 {
 	(*pos)++;
-
-	if (!update_iter(m->private, *pos))
-		return NULL;
-	return p;
-}
-
-static void *s_start(struct seq_file *m, loff_t *pos)
-{
-	if (!update_iter(m->private, *pos))
-		return NULL;
-	return m->private;
+	return fill_iter(p, *pos);
 }
 
 static void s_stop(struct seq_file *m, void *p)
 {
+	kfree(p);
 }
 
 static int s_show(struct seq_file *m, void *p)
 {
-	struct kallsym_iter *iter = m->private;
+	struct kallsym_iter *iter = p;
 
 	/* Some debugging symbols have no name.  Ignore them. */ 
 	if (!iter->name[0])
@@ -277,36 +275,13 @@ struct seq_operations kallsyms_op = {
 
 static int kallsyms_open(struct inode *inode, struct file *file)
 {
-	/* We keep iterator in m->private, since normal case is to
-	 * s_start from where we left off, so we avoid O(N^2). */
-	struct kallsym_iter *iter;
-	int ret;
-
-	iter = kmalloc(sizeof(*iter), GFP_KERNEL);
-	if (!iter)
-		return -ENOMEM;
-	reset_iter(iter);
-
-	ret = seq_open(file, &kallsyms_op);
-	if (ret == 0)
-		((struct seq_file *)file->private_data)->private = iter;
-	else
-		kfree(iter);
-	return ret;
-}
-
-static int kallsyms_release(struct inode *inode, struct file *file)
-{
-	struct seq_file *m = (struct seq_file *)file->private_data;
-	kfree(m->private);
-	return seq_release(inode, file);
+	return seq_open(file, &kallsyms_op);
 }
-
 static struct file_operations kallsyms_operations = {
 	.open = kallsyms_open,
 	.read = seq_read,
 	.llseek = seq_lseek,
-	.release = kallsyms_release,
+	.release = seq_release,
 };
 
 int __init kallsyms_init(void)
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.6.7-bk4/scripts/Makefile working-2.6.7-bk4-kallsyms-compress/scripts/Makefile
--- linux-2.6.7-bk4/scripts/Makefile	2004-06-22 10:36:52.000000000 +1000
+++ working-2.6.7-bk4-kallsyms-compress/scripts/Makefile	2004-06-22 21:59:16.000000000 +1000
@@ -9,6 +9,7 @@ host-progs	:= conmakehash kallsyms modpo
 always		:= $(host-progs) empty.o
 
 modpost-objs	:= modpost.o file2alias.o sumversion.o
+kallsyms-objs	:= kallsyms.o huffenc.o
 
 subdir-$(CONFIG_MODVERSIONS)	+= genksyms
 
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.6.7-bk4/scripts/huffenc.c working-2.6.7-bk4-kallsyms-compress/scripts/huffenc.c
--- linux-2.6.7-bk4/scripts/huffenc.c	1970-01-01 10:00:00.000000000 +1000
+++ working-2.6.7-bk4-kallsyms-compress/scripts/huffenc.c	2004-06-22 22:06:27.000000000 +1000
@@ -0,0 +1,232 @@
+#include <string.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <stdio.h>
+#include "kallsyms.h"
+
+struct huff
+{
+	struct huff *next, *prev;
+
+	/* If these are NULL, we're a terminal character */
+	struct huff *a, *b;
+	unsigned int freq;
+
+	/* For terminals: index into acceptable_chars[], ie. which letter. */
+	int index;
+
+	/* For populating the jump table. */
+	signed char jump[2];
+
+	unsigned char numbits;
+	unsigned char bits[8]; 	/* Can't be more than 64 bits. */
+};
+
+static const char acceptable_chars[]
+= "_0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
+
+static struct huff *huff_head;
+static struct huff huff_base[64];
+static unsigned int huff_entries = 0;
+
+static inline int terminal(const struct huff *h)
+{
+	return !h->a;
+}
+
+static int acceptable_index(char c)
+{
+	if (!c) return 63;
+	return strchr(acceptable_chars, c) - acceptable_chars;
+}
+
+static void replace_least_frequent(struct huff *head)
+{
+	struct huff *a = head, *b = head, *i;
+
+	for (i = head->next; i != head; i = i->next) {
+		if (i->freq < a->freq) {
+			b = a;
+			a = i;
+		} else if (i->freq < b->freq) b = i;
+	}
+
+	i = malloc(sizeof(struct huff));
+	huff_entries++;
+	i->a = a; i->b = b;
+	i->freq = a->freq + b->freq;
+	/* Delete a and b from list */
+	a->next->prev = a->prev;
+	a->prev->next = a->next;
+	b->next->prev = b->prev;
+	b->prev->next = b->next;
+	a->next = b->next = NULL;
+
+	/* Insert new element into list */
+	i->next = head->next;
+	i->prev = head;
+	head->next = i;
+	i->next->prev = i;
+}
+
+static struct huff *huffman(const struct sym_entry *table, int cnt)
+{
+	unsigned int i;
+	struct huff *head;
+
+	head = malloc(sizeof *head);
+
+	for (i = 0; i < 64; i++) {
+		huff_base[i].prev = &huff_base[i-1];
+		huff_base[i].next = &huff_base[i+1];
+		huff_base[i].a = huff_base[i].b = NULL;
+		huff_base[i].index = i;
+		huff_base[i].freq = 0;
+	}
+	huff_base[0].prev = huff_base[63].next = head;
+	head->next = &huff_base[0];
+	head->prev = &huff_base[63];
+	head->freq = UINT_MAX;
+
+	for (i = 0; i < cnt; i++) {
+		unsigned int j;
+
+		for (j = 0; table[i].sym[j]; j++)
+			huff_base[acceptable_index(table[i].sym[j])].freq++;
+		huff_base[acceptable_index(0)].freq++;
+	}
+
+	while (head->next->next != head)
+		replace_least_frequent(head);
+
+	return head;
+}
+
+/* max is max allocated slot. */
+static unsigned int order_decode_table(struct huff *head,
+				       struct huff *ptrs[],
+				       unsigned int pos,
+				       unsigned int max)
+{
+	ptrs[pos] = head;
+	if (terminal(head->a))
+		head->jump[0] = (unsigned char)-(head->a->index + 1);
+	else {
+		head->jump[0] = ++max;
+		max = order_decode_table(head->a, ptrs, head->jump[0], max);
+	}
+
+	if (terminal(head->b))
+		head->jump[1] = (unsigned char)-(head->b->index + 1);
+	else {
+		head->jump[1] = ++max;
+		max = order_decode_table(head->b, ptrs, head->jump[1], max);
+	}
+
+	return max;
+}
+
+static void dump_decode_table(struct huff *head)
+{
+	unsigned int i;
+	struct huff *ptrs[huff_entries];
+
+	/* Order so we can dump it. */
+	order_decode_table(head, ptrs, 0, 0);
+
+	for (i = 0; i < huff_entries; i++) {
+		printf("\t.byte 0x%02x\n", ptrs[i]->jump[0] & 0xFF);
+		printf("\t.byte 0x%02x\n", ptrs[i]->jump[1] & 0xFF);
+	}
+}
+
+/* Create huffman table. */
+void huffman_compress_names(struct sym_entry *table, unsigned int cnt)
+{
+	huff_head = huffman(table, cnt);
+}
+
+static inline void set_bit(int bit, unsigned char *addr, unsigned int bitnum)
+{
+	if (bit) addr[bitnum / 8] |= (1 << (bitnum % 8));
+	else addr[bitnum / 8] &= ~(1 << (bitnum % 8));
+}
+
+static void calc_encode_table(struct huff *head,
+			      unsigned char bitpattern[],
+			      unsigned int bits)
+{
+	if (terminal(head)) {
+		head->numbits = bits;
+		memcpy(head->bits, bitpattern, (bits+7)/8);
+	} else {
+		/* We want to leave bit set at 0 when finished, so do
+                   b first */
+		set_bit(1, bitpattern, bits);
+		calc_encode_table(head->b, bitpattern, bits+1);
+		set_bit(0, bitpattern, bits);
+		calc_encode_table(head->a, bitpattern, bits+1);
+	}
+}
+
+/* Decode table is a jump table containing char pairs.  First char is
+ * if bit is 0, second char is if bit is 1.  Negative numbers are
+ * terminals, positive numbers are relative jumps. */
+void huffman_dump_decode(void)
+{
+	unsigned char bitpattern[8] = { 0 };
+
+	/* Fill in the bitnum and bits fields in terminals. */
+	calc_encode_table(huff_head->next, bitpattern, 0);
+
+	dump_decode_table(huff_head->next);
+}
+
+static unsigned char add_bit(int bit, unsigned char bits, unsigned int *bitnum)
+{
+	if (bit) bits |= (1 << ((*bitnum) % 8));
+	else bits &= ~(1 << ((*bitnum) % 8));
+	(*bitnum)++;
+	if ((*bitnum % 8) == 0) {
+		printf("\t.byte 0x%02x\n", bits);
+		bits = 0;
+	}
+	return bits;
+}
+
+static unsigned char add_encoding(struct huff *h, unsigned char bits,
+				  unsigned int *bitnum)
+{
+	unsigned int i;
+
+	for (i = 0; i < h->numbits; i++)
+		bits = add_bit(h->bits[i/8] & (1 << (i%8)), bits, bitnum);
+	return bits;
+}
+
+int is_acceptable(const char *name)
+{
+	return (strspn(name, acceptable_chars) == strlen(name));
+}
+
+void huffman_dump_names(struct sym_entry *table, unsigned int cnt)
+{
+	unsigned int i, len, bitnum = 0;
+	unsigned char c, bits = 0;
+
+	/* Now use it to encode the names. */
+	for (i = 0; i < cnt; i++) {
+		if (!table[i].type)
+			continue;
+		table[i].bitoffset = bitnum;
+		for (len = 0; table[i].sym[len]; len++) {
+			c = acceptable_index(table[i].sym[len]);
+			bits = add_encoding(&huff_base[c], bits, &bitnum);
+		}
+		bits = add_encoding(&huff_base[acceptable_index(0)], bits,
+				    &bitnum);
+	}
+	/* Pad with zeros */
+	while (bitnum % 8)
+		bits = add_bit(0, bits, &bitnum);
+}
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.6.7-bk4/scripts/kallsyms.c working-2.6.7-bk4-kallsyms-compress/scripts/kallsyms.c
--- linux-2.6.7-bk4/scripts/kallsyms.c	2004-06-17 08:50:00.000000000 +1000
+++ working-2.6.7-bk4-kallsyms-compress/scripts/kallsyms.c	2004-06-22 21:59:16.000000000 +1000
@@ -12,16 +12,10 @@
 #include <stdlib.h>
 #include <string.h>
 #include <ctype.h>
-
-struct sym_entry {
-	unsigned long long addr;
-	char type;
-	char *sym;
-};
-
+#include "kallsyms.h"
 
 static struct sym_entry *table;
-static int size, cnt;
+static int cnt;
 static unsigned long long _stext, _etext, _sinittext, _einittext;
 static int all_symbols = 0;
 
@@ -58,6 +52,8 @@ read_symbol(FILE *in, struct sym_entry *
 		_einittext = s->addr;
 	else if (toupper(s->type) == 'A' || toupper(s->type) == 'U')
 		return -1;
+	if (!is_acceptable(str))
+		return -1;
 
 	s->sym = strdup(str);
 	return 0;
@@ -66,21 +62,20 @@ read_symbol(FILE *in, struct sym_entry *
 static int
 symbol_valid(struct sym_entry *s)
 {
-	if (!all_symbols) {
-		if ((s->addr < _stext || s->addr > _etext)
-		    && (s->addr < _sinittext || s->addr > _einittext))
-			return 0;
-	}
+	if (all_symbols)
+		return 1;
 
-	if (strstr(s->sym, "_compiled."))
+	if ((s->addr < _stext || s->addr > _etext)
+	    && (s->addr < _sinittext || s->addr > _einittext))
 		return 0;
-
 	return 1;
 }
 
 static void
 read_map(FILE *in)
 {
+	int size = 0;
+
 	while (!feof(in)) {
 		if (cnt >= size) {
 			size += 10000;
@@ -99,7 +94,6 @@ static void
 write_src(void)
 {
 	int i, valid = 0;
-	char *prev;
 
 	printf("#include <asm/types.h>\n");
 	printf("#if BITS_PER_LONG == 64\n");
@@ -116,8 +110,10 @@ write_src(void)
 	printf("\tALGN\n");
 	printf("kallsyms_addresses:\n");
 	for (i = 0; i < cnt; i++) {
-		if (!symbol_valid(&table[i]))
+		if (!symbol_valid(&table[i])) {
+			table[i].type = 0;
 			continue;
+		}
 
 		printf("\tPTR\t%#llx\n", table[i].addr);
 		valid++;
@@ -130,21 +126,24 @@ write_src(void)
 	printf("\tPTR\t%d\n", valid);
 	printf("\n");
 
+	printf(".globl kallsyms_huff\n");
+	printf("\tALGN\n");
+	printf("kallsyms_huff:\n");
+	huffman_dump_decode();
+	printf("\n");
+
 	printf(".globl kallsyms_names\n");
 	printf("\tALGN\n");
 	printf("kallsyms_names:\n");
-	prev = ""; 
-	for (i = 0; i < cnt; i++) {
-		int k;
-
-		if (!symbol_valid(&table[i]))
-			continue;
-
-		for (k = 0; table[i].sym[k] && table[i].sym[k] == prev[k]; ++k)
-			; 
+	huffman_dump_names(table, cnt);
+	printf("\n");
 
-		printf("\t.byte 0x%02x\n\t.asciz\t\"%s\"\n", k, table[i].sym + k);
-		prev = table[i].sym;
+	printf(".globl kallsyms_offsets\n");
+	printf("\tALGN\n");
+	printf("kallsyms_offsets:\n");
+	for (i = 0; i < cnt; i++) {
+		if (table[i].type)
+			printf("\t.long\t%#x\n", table[i].bitoffset);
 	}
 	printf("\n");
 }
@@ -158,6 +157,7 @@ main(int argc, char **argv)
 		usage();
 
 	read_map(stdin);
+	huffman_compress_names(table, cnt);
 	write_src();
 
 	return 0;
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.6.7-bk4/scripts/kallsyms.h working-2.6.7-bk4-kallsyms-compress/scripts/kallsyms.h
--- linux-2.6.7-bk4/scripts/kallsyms.h	1970-01-01 10:00:00.000000000 +1000
+++ working-2.6.7-bk4-kallsyms-compress/scripts/kallsyms.h	2004-06-22 21:59:16.000000000 +1000
@@ -0,0 +1,17 @@
+#ifndef _KALLSYMS_H
+#define _KALLSYMS_H
+
+struct sym_entry {
+	unsigned long long addr;
+	char type;
+	char *sym;
+	unsigned int bitoffset;
+};
+
+void huffman_compress_names(struct sym_entry *table, unsigned int cnt);
+void huffman_dump_decode(void);
+void huffman_dump_names(struct sym_entry *table, unsigned int cnt);
+
+/* Is this name acceptable (ie. no weird characters). */
+int is_acceptable(const char *name);
+#endif /* _KALLSYMS_H */