in zlib/contrib/blast/blast.c [282:380]
local int decomp(struct state *s)
{
int lit; /* true if literals are coded */
int dict; /* log2(dictionary size) - 6 */
int symbol; /* decoded symbol, extra bits for distance */
int len; /* length for copy */
unsigned dist; /* distance for copy */
int copy; /* copy counter */
unsigned char *from, *to; /* copy pointers */
static int virgin = 1; /* build tables once */
static short litcnt[MAXBITS+1], litsym[256]; /* litcode memory */
static short lencnt[MAXBITS+1], lensym[16]; /* lencode memory */
static short distcnt[MAXBITS+1], distsym[64]; /* distcode memory */
static struct huffman litcode = {litcnt, litsym}; /* length code */
static struct huffman lencode = {lencnt, lensym}; /* length code */
static struct huffman distcode = {distcnt, distsym};/* distance code */
/* bit lengths of literal codes */
static const unsigned char litlen[] = {
11, 124, 8, 7, 28, 7, 188, 13, 76, 4, 10, 8, 12, 10, 12, 10, 8, 23, 8,
9, 7, 6, 7, 8, 7, 6, 55, 8, 23, 24, 12, 11, 7, 9, 11, 12, 6, 7, 22, 5,
7, 24, 6, 11, 9, 6, 7, 22, 7, 11, 38, 7, 9, 8, 25, 11, 8, 11, 9, 12,
8, 12, 5, 38, 5, 38, 5, 11, 7, 5, 6, 21, 6, 10, 53, 8, 7, 24, 10, 27,
44, 253, 253, 253, 252, 252, 252, 13, 12, 45, 12, 45, 12, 61, 12, 45,
44, 173};
/* bit lengths of length codes 0..15 */
static const unsigned char lenlen[] = {2, 35, 36, 53, 38, 23};
/* bit lengths of distance codes 0..63 */
static const unsigned char distlen[] = {2, 20, 53, 230, 247, 151, 248};
static const short base[16] = { /* base for length codes */
3, 2, 4, 5, 6, 7, 8, 9, 10, 12, 16, 24, 40, 72, 136, 264};
static const char extra[16] = { /* extra bits for length codes */
0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8};
/* set up decoding tables (once--might not be thread-safe) */
if (virgin) {
construct(&litcode, litlen, sizeof(litlen));
construct(&lencode, lenlen, sizeof(lenlen));
construct(&distcode, distlen, sizeof(distlen));
virgin = 0;
}
/* read header */
lit = bits(s, 8);
if (lit > 1) return -1;
dict = bits(s, 8);
if (dict < 4 || dict > 6) return -2;
/* decode literals and length/distance pairs */
do {
if (bits(s, 1)) {
/* get length */
symbol = decode(s, &lencode);
len = base[symbol] + bits(s, extra[symbol]);
if (len == 519) break; /* end code */
/* get distance */
symbol = len == 2 ? 2 : dict;
dist = decode(s, &distcode) << symbol;
dist += bits(s, symbol);
dist++;
if (s->first && dist > s->next)
return -3; /* distance too far back */
/* copy length bytes from distance bytes back */
do {
to = s->out + s->next;
from = to - dist;
copy = MAXWIN;
if (s->next < dist) {
from += copy;
copy = dist;
}
copy -= s->next;
if (copy > len) copy = len;
len -= copy;
s->next += copy;
do {
*to++ = *from++;
} while (--copy);
if (s->next == MAXWIN) {
if (s->outfun(s->outhow, s->out, s->next)) return 1;
s->next = 0;
s->first = 0;
}
} while (len != 0);
}
else {
/* get literal and write it */
symbol = lit ? decode(s, &litcode) : bits(s, 8);
s->out[s->next++] = symbol;
if (s->next == MAXWIN) {
if (s->outfun(s->outhow, s->out, s->next)) return 1;
s->next = 0;
s->first = 0;
}
}
} while (1);
return 0;
}