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 arrange
the symbols by address, but stem compression does better if we sort
them by name.  If we're going to do something to save space, a simple
huffman table 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 .4563-linux-2.6.7-bk4/kernel/kallsyms.c .4563-linux-2.6.7-bk4.updated/kernel/kallsyms.c
--- .4563-linux-2.6.7-bk4/kernel/kallsyms.c	2004-06-22 10:36:51.000000000 +1000
+++ .4563-linux-2.6.7-bk4.updated/kernel/kallsyms.c	2004-06-22 20:51:09.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 .4563-linux-2.6.7-bk4/scripts/Makefile .4563-linux-2.6.7-bk4.updated/scripts/Makefile
--- .4563-linux-2.6.7-bk4/scripts/Makefile	2004-06-22 10:36:52.000000000 +1000
+++ .4563-linux-2.6.7-bk4.updated/scripts/Makefile	2004-06-22 20:50:30.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 .4563-linux-2.6.7-bk4/scripts/huffenc.c .4563-linux-2.6.7-bk4.updated/scripts/huffenc.c
--- .4563-linux-2.6.7-bk4/scripts/huffenc.c	1970-01-01 10:00:00.000000000 +1000
+++ .4563-linux-2.6.7-bk4.updated/scripts/huffenc.c	2004-06-22 20:50:30.000000000 +1000
@@ -0,0 +1,263 @@
+#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_edges = 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_edges++;
+	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;
+}
+
+static char *str_bitpattern(unsigned char bits[], int numbits)
+{
+	static char buffer[8 * 8 + 1];
+	unsigned int i;
+
+	for (i = 0; i < numbits; i++)
+		if (bits[i / 8] & (1 << (i % 8)))
+			buffer[i] = '1';
+		else
+			buffer[i] = '0';
+	buffer[i] = '\0';
+	return buffer;
+}
+
+/* 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;
+
+	if (terminal(head->b))
+		head->jump[1] = (unsigned char)-(head->b->index + 1);
+	else
+		head->jump[1] = ++max;
+
+	if (!terminal(head->a))
+		max = order_decode_table(head->a, ptrs, head->jump[0], max);
+	if (!terminal(head->b))
+		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_edges];
+
+	/* Order so we can dump it. */
+	order_decode_table(head, ptrs, 0, 0);
+
+	for (i = 0; i < huff_edges; i++) {
+		printf("\t.byte 0x%02x", ptrs[i]->jump[0] & 0xFF);
+		if (terminal(ptrs[i]->a))
+			printf(" # %i: %c (%s)\n",
+			       i, 
+			       acceptable_chars[ptrs[i]->a->index] ?: '.',
+			       str_bitpattern(ptrs[i]->a->bits,
+					      ptrs[i]->a->numbits));
+		else
+			printf("\n");
+		printf("\t.byte 0x%02x", ptrs[i]->jump[1] & 0xFF);
+		if (terminal(ptrs[i]->b))
+			printf(" # %i: %c (%s)\n",
+			       i, 
+			       acceptable_chars[ptrs[i]->b->index] ?: '.',
+			       str_bitpattern(ptrs[i]->b->bits,
+					      ptrs[i]->b->numbits));
+		else
+			printf("\n");
+	}
+}
+
+/* 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 .4563-linux-2.6.7-bk4/scripts/kallsyms.c .4563-linux-2.6.7-bk4.updated/scripts/kallsyms.c
--- .4563-linux-2.6.7-bk4/scripts/kallsyms.c	2004-06-17 08:50:00.000000000 +1000
+++ .4563-linux-2.6.7-bk4.updated/scripts/kallsyms.c	2004-06-22 20:50:30.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 .4563-linux-2.6.7-bk4/scripts/kallsyms.h .4563-linux-2.6.7-bk4.updated/scripts/kallsyms.h
--- .4563-linux-2.6.7-bk4/scripts/kallsyms.h	1970-01-01 10:00:00.000000000 +1000
+++ .4563-linux-2.6.7-bk4.updated/scripts/kallsyms.h	2004-06-22 20:50:30.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 */