in zlib/contrib/puff/puff.c [665:747]
local int dynamic(struct state *s)
{
int nlen, ndist, ncode; /* number of lengths in descriptor */
int index; /* index of lengths[] */
int err; /* construct() return value */
short lengths[MAXCODES]; /* descriptor code lengths */
short lencnt[MAXBITS+1], lensym[MAXLCODES]; /* lencode memory */
short distcnt[MAXBITS+1], distsym[MAXDCODES]; /* distcode memory */
struct huffman lencode, distcode; /* length and distance codes */
static const short order[19] = /* permutation of code length codes */
{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
/* construct lencode and distcode */
lencode.count = lencnt;
lencode.symbol = lensym;
distcode.count = distcnt;
distcode.symbol = distsym;
/* get number of lengths in each table, check lengths */
nlen = bits(s, 5) + 257;
ndist = bits(s, 5) + 1;
ncode = bits(s, 4) + 4;
if (nlen > MAXLCODES || ndist > MAXDCODES)
return -3; /* bad counts */
/* read code length code lengths (really), missing lengths are zero */
for (index = 0; index < ncode; index++)
lengths[order[index]] = bits(s, 3);
for (; index < 19; index++)
lengths[order[index]] = 0;
/* build huffman table for code lengths codes (use lencode temporarily) */
err = construct(&lencode, lengths, 19);
if (err != 0) /* require complete code set here */
return -4;
/* read length/literal and distance code length tables */
index = 0;
while (index < nlen + ndist) {
int symbol; /* decoded value */
int len; /* last length to repeat */
symbol = decode(s, &lencode);
if (symbol < 0)
return symbol; /* invalid symbol */
if (symbol < 16) /* length in 0..15 */
lengths[index++] = symbol;
else { /* repeat instruction */
len = 0; /* assume repeating zeros */
if (symbol == 16) { /* repeat last length 3..6 times */
if (index == 0)
return -5; /* no last length! */
len = lengths[index - 1]; /* last length */
symbol = 3 + bits(s, 2);
}
else if (symbol == 17) /* repeat zero 3..10 times */
symbol = 3 + bits(s, 3);
else /* == 18, repeat zero 11..138 times */
symbol = 11 + bits(s, 7);
if (index + symbol > nlen + ndist)
return -6; /* too many lengths! */
while (symbol--) /* repeat last or zero symbol times */
lengths[index++] = len;
}
}
/* check for end-of-block code -- there better be one! */
if (lengths[256] == 0)
return -9;
/* build huffman table for literal/length codes */
err = construct(&lencode, lengths, nlen);
if (err && (err < 0 || nlen != lencode.count[0] + lencode.count[1]))
return -7; /* incomplete code ok only for single length 1 code */
/* build huffman table for distance codes */
err = construct(&distcode, lengths + nlen, ndist);
if (err && (err < 0 || ndist != distcode.count[0] + distcode.count[1]))
return -8; /* incomplete code ok only for single length 1 code */
/* decode data until end-of-block code */
return codes(s, &lencode, &distcode);
}