Re: [PATCH 5/7] inflate pt1: cleanup Huffman table code

[John Reiser <jreiser@BitWagon.com>]

> Index: 2.6.16-rc4-inflate/lib/inflate.c
> ===================================================================
> --- 2.6.16-rc4-inflate.orig/lib/inflate.c	2006-02-22 17:16:07.000000000 -0600
> +++ 2.6.16-rc4-inflate/lib/inflate.c	2006-02-22 17:16:08.000000000 -0600
> @@ -117,12 +117,12 @@
>     an unused code.  If a code with e == 99 is looked up, this implies an
>     error in the data. */
>  struct huft {
> -	u8 e;			/* number of extra bits or operation */
> -	u8 b;			/* number of bits in this code or subcode */
>  	union {
> -		u16 n;		/* literal, length base, or distance base */
> -		struct huft *t;	/* pointer to next level of table */
> -	} v;
> +		u16 val; /* literal, length base, or distance base */
> +		struct huft *next; /* pointer to next level of table */
> +	};
> +	u8 extra; /* number of extra bits or operation */
> +	u8 bits; /* number of bits in this code or subcode */
>  };

How aggressive do you want to be?  About 3.7 years ago in
http://freshmeat.net/projects/gzip_x86/  I published:
-----
typedef unsigned short huft_ndx;  /* index>>1 */
struct huft {
  uch e;                /* number of extra bits or operation */
  uch b;                /* number of bits in this code or subcode */
  union {
    ush n;              /* literal, length base, or distance base */
    huft_ndx t;         /* index>>1 of next level of table */
  } v;
};
-----
which makes 4==sizeof(struct huft) and enables manipulation by 32-bit
fetch, exposing 'e' [extra] and 'b' [bits] in x86 byte registers
for fewer shift-and-mask operations.  The struct huft can be managed
as a stack of maximum length 1014.

--