#pragma prototyped
/*
* zip deflate decoder
*/
/* inflate.c -- Not copyrighted 1992 by Mark Adler
version c10p1, 10 January 1993 */
/* You can do whatever you like with this source file, though I would
prefer that if you modify it and redistribute it that you include
comments to that effect with your name and the date. Thank you.
[The history has been moved to the file ChangeLog.]
*/
/*
Inflate deflated (PKZIP's method 8 compressed) data. The compression
method searches for as much of the current string of bytes (up to a
length of 258) in the previous 32K bytes. If it doesn't find any
matches (of at least length 3), it codes the next byte. Otherwise, it
codes the length of the matched string and its distance backwards from
the current position. There is a single Huffman code that codes both
single bytes (called "literals") and match lengths. A second Huffman
code codes the distance information, which follows a length code. Each
length or distance code actually represents a base value and a number
of "extra" (sometimes zero) bits to get to add to the base value. At
the end of each deflated block is a special end-of-block (EOB) literal/
length code. The decoding process is basically: get a literal/length
code; if EOB then done; if a literal, emit the decoded byte; if a
length then get the distance and emit the referred-to bytes from the
sliding window of previously emitted data.
There are (currently) three kinds of inflate blocks: stored, fixed, and
dynamic. The compressor outputs a chunk of data at a time and decides
which method to use on a chunk-by-chunk basis. A chunk might typically
be 32K to 64K, uncompressed. If the chunk is uncompressible, then the
"stored" method is used. In this case, the bytes are simply stored as
is, eight bits per byte, with none of the above coding. The bytes are
preceded by a count, since there is no longer an EOB code.
If the data are compressible, then either the fixed or dynamic methods
are used. In the dynamic method, the compressed data are preceded by
an encoding of the literal/length and distance Huffman codes that are
to be used to decode this block. The representation is itself Huffman
coded, and so is preceded by a description of that code. These code
descriptions take up a little space, and so for small blocks, there is
a predefined set of codes, called the fixed codes. The fixed method is
used if the block ends up smaller that way (usually for quite small
chunks); otherwise the dynamic method is used. In the latter case, the
codes are customized to the probabilities in the current block and so
can code it much better than the pre-determined fixed codes can.
The Huffman codes themselves are decoded using a multi-level table
lookup, in order to maximize the speed of decoding plus the speed of
building the decoding tables. See the comments below that precede the
lbits and dbits tuning parameters.
*/
/*
Notes beyond the 1.93a appnote.txt:
1. Distance pointers never point before the beginning of the output
stream.
2. Distance pointers can point back across blocks, up to 32k away.
3. There is an implied maximum of 7 bits for the bit length table and
15 bits for the actual data.
4. If only one code exists, then it is encoded using one bit. (Zero
would be more efficient, but perhaps a little confusing.) If two
codes exist, they are coded using one bit each (0 and 1).
5. There is no way of sending zero distance codes--a dummy must be
sent if there are none. (History: a pre 2.0 version of PKZIP would
store blocks with no distance codes, but this was discovered to be
too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
zero distance codes, which is sent as one code of zero bits in
length.
6. There are up to 286 literal/length codes. Code 256 represents the
end-of-block. Note however that the static length tree defines
288 codes just to fill out the Huffman codes. Codes 286 and 287
cannot be used though, since there is no length base or extra bits
defined for them. Similarily, there are up to 30 distance codes.
However, static trees define 32 codes (all 5 bits) to fill out the
Huffman codes, but the last two had better not show up in the data.
7. Unzip can check dynamic Huffman blocks for complete code sets.
The exception is that a single code would not be complete (see #4).
8. The five bits following the block type is really the number of
literal codes sent minus 257.
9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
(1+6+6). Therefore, to output three times the length, you output
three codes (1+1+1), whereas to output four times the same length,
you only need two codes (1+3). Hmm.
10. In the tree reconstruction algorithm, Code = Code + Increment
only if BitLength(i) is not zero. (Pretty obvious.)
11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
12. Note: length code 284 can represent 227-258, but length code 285
really is 258. The last length deserves its own, short code
since it gets used a lot in very redundant files. The length
258 is special since 258 - 3 (the min match length) is 255.
13. The literal/length and distance code bit lengths are read as a
single stream of lengths. It is possible (and advantageous) for
a repeat code (16, 17, or 18) to go across the boundary between
the two sets of lengths.
*/
#include "zip.h"
#include "huff.h"
#define WINDOW 32768
#define STORED_BLOCK 0
#define STATIC_TREES 1
#define DYNAMIC_TREES 2
/* Save to local */
#define BITS_LOCAL \
ulg bit_buf = state->bit_buf; \
ulg bit_len = state->bit_len;
/* Restore to state */
#define BITS_GLOBAL \
state->bit_buf = bit_buf; \
state->bit_len = bit_len;
#define MASK_BITS(n) ((((ulg)1)<<(n))-1)
#define NEXTBYTE(p) (((p)->ip < (p)->ie) ? (int)*(p)->ip++ : fill(p))
#define NEEDBITS(p,n) {while (bit_len<(n)){bit_buf|=((ulg)NEXTBYTE(p))<<bit_len;bit_len+=8;}}
#define GETBITS(n) (bit_buf & MASK_BITS(n))
#define DUMPBITS(n) {bit_buf>>=(n);bit_len-=(n);}
struct State_s; typedef struct State_s State_t;
struct State_s
{
Codex_t* codex;
Vmalloc_t* vm; /* memory region for tl, td */
uch buf[SF_BUFSIZE];
uch slide[WINDOW];
int method;
int eof; /* init to 0 from this member on */
int last;
uch* ip;
uch* ie;
ulg wp; /* current position in slide */
Huff_t* fixed_tl; /* inflate static */
Huff_t* fixed_td; /* inflate static */
int fixed_bl; /* inflate static */
int fixed_bd; /* inflate static */
ulg bit_buf; /* bit buffer */
ulg bit_len; /* bits in bit buffer */
ulg copy_len;
ulg copy_pos;
Huff_t* tl; /* literal length state table */
Huff_t* td; /* literal distance state table */
int bl; /* number of bits decoded by tl[] */
int bd; /* number of bits decoded by td[] */
};
static int
fill(State_t* state)
{
ssize_t r;
if (state->eof)
return 0;
if ((r = sfrd(state->codex->sp, state->buf, sizeof(state->buf), &state->codex->sfdisc)) <= 0)
{
state->eof = 1;
return 0;
}
state->ie = (state->ip = state->buf) + r;
return *state->ip++;
}
/* The inflate algorithm uses a sliding 32K byte window on the uncompressed
stream to find repeated byte strings. This is implemented here as a
circular buffer. The index is updated simply by incrementing and then
and'ing with 0x7fff (32K-1). */
/* It is left to other modules to supply the 32K area. It is assumed
to be usable as if it were declared "uch slide[32768];" or as just
"uch *slide;" and then malloc'ed in the latter case. The definition
must be in unzip.h, included above. */
#define lbits 9 /* bits in base literal/length lookup table */
#define dbits 6 /* bits in base distance lookup table */
/* Tables for deflate from PKZIP's appnote.txt. */
static ush cplens[] = { /* Copy lengths for literal codes 257..285 */
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
/* note: see note #13 above about the 258 in this list. */
static ush cplext[] = { /* Extra bits for literal codes 257..285 */
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
static ush cpdist[] = { /* Copy offsets for distance codes 0..29 */
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
8193, 12289, 16385, 24577};
static ush cpdext[] = { /* Extra bits for distance codes */
0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
12, 12, 13, 13};
/* inflate (decompress) the codes in a deflated (compressed) block.
Return an error code or zero if it all goes ok. */
static uch*
inflate_codes(State_t* state, register uch* p, register uch* e)
{
register ulg x; /* table entry flag/number of extra bits */
Huff_t* t; /* pointer to table entry */
Huff_t* tl; /* literal length state table */
Huff_t* td; /* literal distance state table */
int bl; /* number of bits decoded by tl[] */
int bd; /* number of bits decoded by td[] */
ulg l;
ulg w;
ulg d;
uch* slide;
BITS_LOCAL;
if (p == e)
return p;
slide = state->slide;
tl = state->tl;
td = state->td;
bl = state->bl;
bd = state->bd;
w = state->wp;
/* inflate the coded data until end of block */
for (;;)
{
NEEDBITS(state, (ulg)bl);
t = tl + GETBITS(bl);
x = t->e;
while (x > 16)
{
if (x == 99)
return 0;
DUMPBITS(t->b);
x -= 16;
NEEDBITS(state, x);
t = t->v.t + GETBITS(x);
x = t->e;
}
DUMPBITS(t->b);
if (x == 16)
{
/* literal */
w &= WINDOW - 1;
*p++ = slide[w++] = (uch)t->v.n;
if (p >= e)
{
state->wp = w;
BITS_GLOBAL;
return p;
}
}
else if (x == 15)
break;
else
{
/* get length of block to copy */
NEEDBITS(state, x);
l = t->v.n + GETBITS(x);
DUMPBITS(x);
/* decode distance of block to copy */
NEEDBITS(state, (ulg)bd);
t = td + GETBITS(bd);
x = t->e;
while (x > 16)
{
if (x == 99)
return 0;
DUMPBITS(t->b);
x -= 16;
NEEDBITS(state, x);
t = t->v.t + GETBITS(x);
x = t->e;
}
DUMPBITS(t->b);
NEEDBITS(state, x);
d = w - t->v.n - GETBITS(x);
DUMPBITS(x);
/* do the copy */
while (l--)
{
d &= WINDOW - 1;
w &= WINDOW - 1;
*p++ = slide[w++] = slide[d++];
if (p >= e)
{
state->copy_len = l;
state->wp = w;
state->copy_pos = d;
BITS_GLOBAL;
return p;
}
}
}
}
state->wp = w;
state->method = -1;
BITS_GLOBAL;
return p;
}
/* "decompress" an inflated type 0 (stored) block. */
static uch*
inflate_stored(State_t* state, register uch* p, register uch* e)
{
ulg l;
ulg w;
BITS_LOCAL;
/* go to byte boundary */
l = bit_len & 7;
DUMPBITS(l);
/* get the length and its complement */
NEEDBITS(state, 16);
l = GETBITS(16);
DUMPBITS(16);
NEEDBITS(state, 16);
if (l != (ulg)((~bit_buf) & 0xffff))
{
BITS_GLOBAL;
return 0;
}
DUMPBITS(16);
/* read and output the compressed data */
w = state->wp;
for (;;)
{
if (!l--)
{
state->method = -1;
break;
}
w &= WINDOW - 1;
NEEDBITS(state, 8);
*p++ = state->slide[w++] = (uch)GETBITS(8);
DUMPBITS(8);
if (p >= e)
{
state->copy_len = l;
break;
}
}
state->wp = w;
BITS_GLOBAL;
return p;
}
/* decompress an inflated type 1 (fixed Huffman codes) block. We should
either replace this with a custom state, or at least precompute the
Huffman tables. */
static int
inflate_fixed(State_t* state)
{
/* if first time, set up tables for fixed blocks */
if (!state->fixed_tl)
{
Huff_t* tl; /* literal/length code table */
int i; /* temporary variable */
ulg l[288]; /* length list for huff() */
/* literal table */
for (i = 0; i < 144; i++)
l[i] = 8;
for (; i < 256; i++)
l[i] = 9;
for (; i < 280; i++)
l[i] = 7;
/* make a complete, but wrong code set */
for (; i < 288; i++)
l[i] = 8;
state->fixed_bl = 7;
if (huff(l, 288, 257, cplens, cplext, &tl, &state->fixed_bl, state->vm))
return -1;
/* distance table -- make an incomplete code set */
for (i = 0; i < 30; i++)
l[i] = 5;
state->fixed_bd = 5;
if (huff(l, 30, 0, cpdist, cpdext, &state->fixed_td, &state->fixed_bd, state->vm) > 1)
return -1;
state->fixed_tl = tl;
}
state->tl = state->fixed_tl;
state->td = state->fixed_td;
state->bl = state->fixed_bl;
state->bd = state->fixed_bd;
return 0;
}
/* decompress an inflated type 2 (dynamic Huffman codes) block. */
static int
inflate_dynamic(State_t* state)
{
int i; /* temporary variables */
ulg j;
ulg l; /* last length */
ulg n; /* number of lengths to get */
Huff_t* tl; /* literal/length code table */
Huff_t* td; /* distance code table */
int bl; /* lookup bits for tl */
int bd; /* lookup bits for td */
ulg nb; /* number of bit length codes */
ulg nl; /* number of literal/length codes */
ulg nd; /* number of distance codes */
#ifdef PKZIP_BUG_WORKAROUND
ulg ll[288+32]; /* literal/length and distance code lengths */
#else
ulg ll[286+30]; /* literal/length and distance code lengths */
#endif
static ulg border[] = { /* Order of the bit length code lengths */
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
BITS_LOCAL;
state->fixed_tl = 0;
vmclear(state->vm);
/* read in table lengths */
NEEDBITS(state, 5);
nl = 257 + GETBITS(5); /* number of literal/length codes */
DUMPBITS(5);
NEEDBITS(state, 5);
nd = 1 + GETBITS(5); /* number of distance codes */
DUMPBITS(5);
NEEDBITS(state, 4);
nb = 4 + GETBITS(4); /* number of bit length codes */
DUMPBITS(4);
#ifdef PKZIP_BUG_WORKAROUND
if (nl > 288 || nd > 32)
#else
if (nl > 286 || nd > 30)
#endif
{
/* bad lengths */
BITS_GLOBAL;
return -1;
}
/* read in bit-length-code lengths */
for (j = 0; j < nb; j++)
{
NEEDBITS(state, 3);
ll[border[j]] = GETBITS(3);
DUMPBITS(3);
}
for (; j < 19; j++)
ll[border[j]] = 0;
/* build decoding table for trees--single level, 7 bit lookup */
bl = 7;
if (i = huff(ll, 19, 19, NULL, NULL, &tl, &bl, state->vm))
{
/* incomplete code set */
BITS_GLOBAL;
return -1;
}
/* read in literal and distance code lengths */
n = nl + nd;
i = l = 0;
while ((ulg)i < n)
{
NEEDBITS(state, (ulg)bl);
j = (td = tl + (GETBITS(bl)))->b;
DUMPBITS(j);
j = td->v.n;
if (j < 16) /* length of code in bits (0..15) */
ll[i++] = l = j;/* save last length in l */
else if (j == 16) /* repeat last length 3 to 6 times */
{
NEEDBITS(state, 2);
j = 3 + GETBITS(2);
DUMPBITS(2);
if ((ulg)i + j > n)
{
BITS_GLOBAL;
return -1;
}
while (j--)
ll[i++] = l;
}
else if (j == 17) /* 3 to 10 zero length codes */
{
NEEDBITS(state, 3);
j = 3 + GETBITS(3);
DUMPBITS(3);
if ((ulg)i + j > n)
{
BITS_GLOBAL;
return -1;
}
while (j--)
ll[i++] = 0;
l = 0;
}
else /* j == 18: 11 to 138 0 length codes */
{
NEEDBITS(state, 7);
j = 11 + GETBITS(7);
DUMPBITS(7);
if ((ulg)i + j > n)
{
BITS_GLOBAL;
return -1;
}
while (j--)
ll[i++] = 0;
l = 0;
}
}
BITS_GLOBAL;
/* free decoding table for trees */
vmclear(state->vm);
/* build the decoding tables for literal/length and distance codes */
bl = lbits;
i = huff(ll, nl, 257, cplens, cplext, &tl, &bl, state->vm);
if (bl == 0) /* no literals or lengths */
i = 1;
if (i)
{
/* incomplete code set */
if (i == 1 && state->codex->disc->errorf)
(*state->codex->disc->errorf)(NiL, state->codex->disc, 2, "%s: incomplete literal tree", state->codex->meth->name);
return -1;
}
bd = dbits;
i = huff(ll + nl, nd, 0, cpdist, cpdext, &td, &bd, state->vm);
if (bd == 0 && nl > 257)
{
/* lengths but no distances */
if (state->codex->disc->errorf)
(*state->codex->disc->errorf)(NiL, state->codex->disc, 2, "%s: incomplete distance tree", state->codex->meth->name);
return -1;
}
if (i == 1)
{
#ifdef PKZIP_BUG_WORKAROUND
i = 0;
#else
if (state->codex->disc->errorf)
(*state->codex->disc->errorf)(NiL, state->codex->disc, 2, "%s: incomplete distance tree", state->codex->meth->name);
#endif
}
if (i)
return -1;
state->tl = tl;
state->td = td;
state->bl = bl;
state->bd = bd;
return 0;
}
static int
deflate_open(Codex_t* p, char* const args[], Codexnum_t flags)
{
State_t* state;
Vmalloc_t* vm;
if (!(vm = vmopen(Vmdcheap, Vmbest, 0)))
return -1;
if (!(state = newof(0, State_t, 1, 0)))
{
vmclose(vm);
return -1;
}
state->vm = vm;
state->codex = p;
p->data = state;
return 0;
}
static int
deflate_close(Codex_t* p)
{
State_t* state = (State_t*)p->data;
if (!state)
return -1;
if (state->vm)
vmclose(state->vm);
free(state);
return 0;
}
static int
deflate_init(Codex_t* p)
{
register State_t* state = (State_t*)p->data;
vmclear(state->vm);
state->tl = state->fixed_tl = 0;
state->method = -1;
memset((char*)state + offsetof(State_t, eof), 0, sizeof(*state) - offsetof(State_t, eof));
return 0;
}
static ssize_t
deflate_read(Sfio_t* sp, void* buf, size_t size, Sfdisc_t* disc)
{
register State_t* state = (State_t*)CODEX(disc)->data;
register uch* p = (uch*)buf;
register uch* e = p + size;
register uch* q;
ulg l;
ulg w;
ulg d;
if (state->copy_len > 0)
{
l = state->copy_len;
w = state->wp;
if (state->method != STORED_BLOCK)
{
d = state->copy_pos;
while (l && p < e)
{
l--;
d &= WINDOW - 1;
w &= WINDOW - 1;
*p++ = state->slide[w++] = state->slide[d++];
}
state->copy_pos = d;
}
else
{
BITS_LOCAL;
while (l && p < e)
{
l--;
w &= WINDOW - 1;
NEEDBITS(state, 8);
*p++ = state->slide[w++] = (uch)GETBITS(8);
DUMPBITS(8);
}
BITS_GLOBAL;
if (!l)
state->method = -1;
}
state->copy_len = l;
state->wp = w;
}
while (p < e)
{
if (state->method == -1)
{
BITS_LOCAL;
if (state->eof)
{
BITS_GLOBAL;
break;
}
if (state->last)
{
state->last = state->wp = 0;
l = bit_len & 7;
DUMPBITS(l);
}
/* read in last block bit */
NEEDBITS(state, 1);
if (GETBITS(1))
state->last = 1;
DUMPBITS(1);
/* read in block type */
NEEDBITS(state, 2);
state->method = (int)GETBITS(2);
DUMPBITS(2);
state->tl = 0;
state->copy_len = 0;
BITS_GLOBAL;
}
switch(state->method)
{
case STORED_BLOCK:
q = inflate_stored(state, p, e);
break;
case STATIC_TREES:
q = (state->tl || !inflate_fixed(state)) ? inflate_codes(state, p, e) : (uch*)0;
break;
case DYNAMIC_TREES:
q = (state->tl || !inflate_dynamic(state)) ? inflate_codes(state, p, e) : (uch*)0;
break;
default:
q = 0;
break;
}
if (!q)
{
if (p < e || state->eof)
break;
return -1;
}
p = q;
}
return p - (uch*)buf;
}
Codexmeth_t codex_zip_deflate =
{
"deflate",
"zip deflate compression (PKZIP method 8). Option is level"
" { 6:faster ... 9:better }.",
0,
CODEX_DECODE|CODEX_COMPRESS,
0,
0,
deflate_open,
deflate_close,
deflate_init,
0,
deflate_read,
0,
0,
0,
0,
0,
0,
0
};