1 b6afd33e 2003-11-23 devnull #include <u.h>
2 b6afd33e 2003-11-23 devnull #include <libc.h>
3 b6afd33e 2003-11-23 devnull #include <flate.h>
6 b6afd33e 2003-11-23 devnull HistorySize= 32*1024,
7 b6afd33e 2003-11-23 devnull BufSize= 4*1024,
8 b6afd33e 2003-11-23 devnull MaxHuffBits= 17, /* maximum bits in a encoded code */
9 b6afd33e 2003-11-23 devnull Nlitlen= 288, /* number of litlen codes */
10 b6afd33e 2003-11-23 devnull Noff= 32, /* number of offset codes */
11 b6afd33e 2003-11-23 devnull Nclen= 19, /* number of codelen codes */
12 b6afd33e 2003-11-23 devnull LenShift= 10, /* code = len<<LenShift|code */
13 b6afd33e 2003-11-23 devnull LitlenBits= 7, /* number of bits in litlen decode table */
14 b6afd33e 2003-11-23 devnull OffBits= 6, /* number of bits in offset decode table */
15 b6afd33e 2003-11-23 devnull ClenBits= 6, /* number of bits in code len decode table */
16 b6afd33e 2003-11-23 devnull MaxFlatBits= LitlenBits,
17 b6afd33e 2003-11-23 devnull MaxLeaf= Nlitlen
20 b6afd33e 2003-11-23 devnull typedef struct Input Input;
21 b6afd33e 2003-11-23 devnull typedef struct History History;
22 b6afd33e 2003-11-23 devnull typedef struct Huff Huff;
24 b6afd33e 2003-11-23 devnull struct Input
26 b6afd33e 2003-11-23 devnull int error; /* first error encountered, or FlateOk */
27 b6afd33e 2003-11-23 devnull void *wr;
28 b6afd33e 2003-11-23 devnull int (*w)(void*, void*, int);
29 b6afd33e 2003-11-23 devnull void *getr;
30 b6afd33e 2003-11-23 devnull int (*get)(void*);
31 b6afd33e 2003-11-23 devnull ulong sreg;
32 b6afd33e 2003-11-23 devnull int nbits;
35 b6afd33e 2003-11-23 devnull struct History
37 b6afd33e 2003-11-23 devnull uchar his[HistorySize];
38 b6afd33e 2003-11-23 devnull uchar *cp; /* current pointer in history */
39 b6afd33e 2003-11-23 devnull int full; /* his has been filled up at least once */
42 b6afd33e 2003-11-23 devnull struct Huff
44 b6afd33e 2003-11-23 devnull int maxbits; /* max bits for any code */
45 b6afd33e 2003-11-23 devnull int minbits; /* min bits to get before looking in flat */
46 b6afd33e 2003-11-23 devnull int flatmask; /* bits used in "flat" fast decoding table */
47 b6afd33e 2003-11-23 devnull ulong flat[1<<MaxFlatBits];
48 b6afd33e 2003-11-23 devnull ulong maxcode[MaxHuffBits];
49 b6afd33e 2003-11-23 devnull ulong last[MaxHuffBits];
50 b6afd33e 2003-11-23 devnull ulong decode[MaxLeaf];
53 b6afd33e 2003-11-23 devnull /* litlen code words 257-285 extra bits */
54 b6afd33e 2003-11-23 devnull static int litlenextra[Nlitlen-257] =
56 b6afd33e 2003-11-23 devnull /* 257 */ 0, 0, 0,
57 b6afd33e 2003-11-23 devnull /* 260 */ 0, 0, 0, 0, 0, 1, 1, 1, 1, 2,
58 b6afd33e 2003-11-23 devnull /* 270 */ 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
59 b6afd33e 2003-11-23 devnull /* 280 */ 4, 5, 5, 5, 5, 0, 0, 0
62 b6afd33e 2003-11-23 devnull static int litlenbase[Nlitlen-257];
64 b6afd33e 2003-11-23 devnull /* offset code word extra bits */
65 b6afd33e 2003-11-23 devnull static int offextra[Noff] =
67 b6afd33e 2003-11-23 devnull 0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
68 b6afd33e 2003-11-23 devnull 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
69 b6afd33e 2003-11-23 devnull 9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
72 b6afd33e 2003-11-23 devnull static int offbase[Noff];
74 b6afd33e 2003-11-23 devnull /* order code lengths */
75 b6afd33e 2003-11-23 devnull static int clenorder[Nclen] =
77 b6afd33e 2003-11-23 devnull 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
80 b6afd33e 2003-11-23 devnull /* for static huffman tables */
81 b6afd33e 2003-11-23 devnull static Huff litlentab;
82 b6afd33e 2003-11-23 devnull static Huff offtab;
83 b6afd33e 2003-11-23 devnull static uchar revtab[256];
85 b6afd33e 2003-11-23 devnull static int uncblock(Input *in, History*);
86 b6afd33e 2003-11-23 devnull static int fixedblock(Input *in, History*);
87 b6afd33e 2003-11-23 devnull static int dynamicblock(Input *in, History*);
88 b6afd33e 2003-11-23 devnull static int sregfill(Input *in, int n);
89 b6afd33e 2003-11-23 devnull static int sregunget(Input *in);
90 b6afd33e 2003-11-23 devnull static int decode(Input*, History*, Huff*, Huff*);
91 b6afd33e 2003-11-23 devnull static int hufftab(Huff*, char*, int, int);
92 b6afd33e 2003-11-23 devnull static int hdecsym(Input *in, Huff *h, int b);
95 b6afd33e 2003-11-23 devnull inflateinit(void)
97 b6afd33e 2003-11-23 devnull char *len;
98 b6afd33e 2003-11-23 devnull int i, j, base;
100 b6afd33e 2003-11-23 devnull /* byte reverse table */
101 b6afd33e 2003-11-23 devnull for(i=0; i<256; i++)
102 b6afd33e 2003-11-23 devnull for(j=0; j<8; j++)
103 b6afd33e 2003-11-23 devnull if(i & (1<<j))
104 b6afd33e 2003-11-23 devnull revtab[i] |= 0x80 >> j;
106 b6afd33e 2003-11-23 devnull for(i=257,base=3; i<Nlitlen; i++) {
107 b6afd33e 2003-11-23 devnull litlenbase[i-257] = base;
108 b6afd33e 2003-11-23 devnull base += 1<<litlenextra[i-257];
110 b6afd33e 2003-11-23 devnull /* strange table entry in spec... */
111 b6afd33e 2003-11-23 devnull litlenbase[285-257]--;
113 b6afd33e 2003-11-23 devnull for(i=0,base=1; i<Noff; i++) {
114 b6afd33e 2003-11-23 devnull offbase[i] = base;
115 b6afd33e 2003-11-23 devnull base += 1<<offextra[i];
118 b6afd33e 2003-11-23 devnull len = malloc(MaxLeaf);
119 b6afd33e 2003-11-23 devnull if(len == nil)
120 b6afd33e 2003-11-23 devnull return FlateNoMem;
122 b6afd33e 2003-11-23 devnull /* static Litlen bit lengths */
123 b6afd33e 2003-11-23 devnull for(i=0; i<144; i++)
124 b6afd33e 2003-11-23 devnull len[i] = 8;
125 b6afd33e 2003-11-23 devnull for(i=144; i<256; i++)
126 b6afd33e 2003-11-23 devnull len[i] = 9;
127 b6afd33e 2003-11-23 devnull for(i=256; i<280; i++)
128 b6afd33e 2003-11-23 devnull len[i] = 7;
129 b6afd33e 2003-11-23 devnull for(i=280; i<Nlitlen; i++)
130 b6afd33e 2003-11-23 devnull len[i] = 8;
132 b6afd33e 2003-11-23 devnull if(!hufftab(&litlentab, len, Nlitlen, MaxFlatBits))
133 b6afd33e 2003-11-23 devnull return FlateInternal;
135 b6afd33e 2003-11-23 devnull /* static Offset bit lengths */
136 b6afd33e 2003-11-23 devnull for(i=0; i<Noff; i++)
137 b6afd33e 2003-11-23 devnull len[i] = 5;
139 b6afd33e 2003-11-23 devnull if(!hufftab(&offtab, len, Noff, MaxFlatBits))
140 b6afd33e 2003-11-23 devnull return FlateInternal;
141 b6afd33e 2003-11-23 devnull free(len);
143 b6afd33e 2003-11-23 devnull return FlateOk;
147 b6afd33e 2003-11-23 devnull inflate(void *wr, int (*w)(void*, void*, int), void *getr, int (*get)(void*))
149 b6afd33e 2003-11-23 devnull History *his;
150 b6afd33e 2003-11-23 devnull Input in;
151 b6afd33e 2003-11-23 devnull int final, type;
153 b6afd33e 2003-11-23 devnull his = malloc(sizeof(History));
154 b6afd33e 2003-11-23 devnull if(his == nil)
155 b6afd33e 2003-11-23 devnull return FlateNoMem;
156 b6afd33e 2003-11-23 devnull his->cp = his->his;
157 b6afd33e 2003-11-23 devnull his->full = 0;
158 b6afd33e 2003-11-23 devnull in.getr = getr;
159 b6afd33e 2003-11-23 devnull in.get = get;
160 b6afd33e 2003-11-23 devnull in.wr = wr;
161 b6afd33e 2003-11-23 devnull in.w = w;
162 b6afd33e 2003-11-23 devnull in.nbits = 0;
163 b6afd33e 2003-11-23 devnull in.sreg = 0;
164 b6afd33e 2003-11-23 devnull in.error = FlateOk;
167 b6afd33e 2003-11-23 devnull if(!sregfill(&in, 3))
168 b6afd33e 2003-11-23 devnull goto bad;
169 b6afd33e 2003-11-23 devnull final = in.sreg & 0x1;
170 b6afd33e 2003-11-23 devnull type = (in.sreg>>1) & 0x3;
171 b6afd33e 2003-11-23 devnull in.sreg >>= 3;
172 b6afd33e 2003-11-23 devnull in.nbits -= 3;
173 b6afd33e 2003-11-23 devnull switch(type) {
174 b6afd33e 2003-11-23 devnull default:
175 b6afd33e 2003-11-23 devnull in.error = FlateCorrupted;
176 b6afd33e 2003-11-23 devnull goto bad;
178 b6afd33e 2003-11-23 devnull /* uncompressed */
179 b6afd33e 2003-11-23 devnull if(!uncblock(&in, his))
180 b6afd33e 2003-11-23 devnull goto bad;
183 b6afd33e 2003-11-23 devnull /* fixed huffman */
184 b6afd33e 2003-11-23 devnull if(!fixedblock(&in, his))
185 b6afd33e 2003-11-23 devnull goto bad;
188 b6afd33e 2003-11-23 devnull /* dynamic huffman */
189 b6afd33e 2003-11-23 devnull if(!dynamicblock(&in, his))
190 b6afd33e 2003-11-23 devnull goto bad;
193 b6afd33e 2003-11-23 devnull } while(!final);
195 b6afd33e 2003-11-23 devnull if(his->cp != his->his && (*w)(wr, his->his, his->cp - his->his) != his->cp - his->his) {
196 b6afd33e 2003-11-23 devnull in.error = FlateOutputFail;
197 b6afd33e 2003-11-23 devnull goto bad;
200 b6afd33e 2003-11-23 devnull if(!sregunget(&in))
201 b6afd33e 2003-11-23 devnull goto bad;
203 b6afd33e 2003-11-23 devnull free(his);
204 b6afd33e 2003-11-23 devnull if(in.error != FlateOk)
205 b6afd33e 2003-11-23 devnull return FlateInternal;
206 b6afd33e 2003-11-23 devnull return FlateOk;
209 b6afd33e 2003-11-23 devnull free(his);
210 b6afd33e 2003-11-23 devnull if(in.error == FlateOk)
211 b6afd33e 2003-11-23 devnull return FlateInternal;
212 b6afd33e 2003-11-23 devnull return in.error;
215 b6afd33e 2003-11-23 devnull static int
216 b6afd33e 2003-11-23 devnull uncblock(Input *in, History *his)
218 b6afd33e 2003-11-23 devnull int len, nlen, c;
219 b6afd33e 2003-11-23 devnull uchar *hs, *hp, *he;
221 b6afd33e 2003-11-23 devnull if(!sregunget(in))
222 b6afd33e 2003-11-23 devnull return 0;
223 b6afd33e 2003-11-23 devnull len = (*in->get)(in->getr);
224 b6afd33e 2003-11-23 devnull len |= (*in->get)(in->getr)<<8;
225 b6afd33e 2003-11-23 devnull nlen = (*in->get)(in->getr);
226 b6afd33e 2003-11-23 devnull nlen |= (*in->get)(in->getr)<<8;
227 b6afd33e 2003-11-23 devnull if(len != (~nlen&0xffff)) {
228 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
229 b6afd33e 2003-11-23 devnull return 0;
232 b6afd33e 2003-11-23 devnull hp = his->cp;
233 b6afd33e 2003-11-23 devnull hs = his->his;
234 b6afd33e 2003-11-23 devnull he = hs + HistorySize;
236 b6afd33e 2003-11-23 devnull while(len > 0) {
237 b6afd33e 2003-11-23 devnull c = (*in->get)(in->getr);
238 b6afd33e 2003-11-23 devnull if(c < 0)
239 b6afd33e 2003-11-23 devnull return 0;
240 b6afd33e 2003-11-23 devnull *hp++ = c;
241 b6afd33e 2003-11-23 devnull if(hp == he) {
242 b6afd33e 2003-11-23 devnull his->full = 1;
243 b6afd33e 2003-11-23 devnull if((*in->w)(in->wr, hs, HistorySize) != HistorySize) {
244 b6afd33e 2003-11-23 devnull in->error = FlateOutputFail;
245 b6afd33e 2003-11-23 devnull return 0;
247 b6afd33e 2003-11-23 devnull hp = hs;
252 b6afd33e 2003-11-23 devnull his->cp = hp;
254 b6afd33e 2003-11-23 devnull return 1;
257 b6afd33e 2003-11-23 devnull static int
258 b6afd33e 2003-11-23 devnull fixedblock(Input *in, History *his)
260 b6afd33e 2003-11-23 devnull return decode(in, his, &litlentab, &offtab);
263 b6afd33e 2003-11-23 devnull static int
264 b6afd33e 2003-11-23 devnull dynamicblock(Input *in, History *his)
266 b6afd33e 2003-11-23 devnull Huff *lentab, *offtab;
267 b6afd33e 2003-11-23 devnull char *len;
268 b6afd33e 2003-11-23 devnull int i, j, n, c, nlit, ndist, nclen, res, nb;
270 b6afd33e 2003-11-23 devnull if(!sregfill(in, 14))
271 b6afd33e 2003-11-23 devnull return 0;
272 b6afd33e 2003-11-23 devnull nlit = (in->sreg&0x1f) + 257;
273 b6afd33e 2003-11-23 devnull ndist = ((in->sreg>>5) & 0x1f) + 1;
274 b6afd33e 2003-11-23 devnull nclen = ((in->sreg>>10) & 0xf) + 4;
275 b6afd33e 2003-11-23 devnull in->sreg >>= 14;
276 b6afd33e 2003-11-23 devnull in->nbits -= 14;
278 b6afd33e 2003-11-23 devnull if(nlit > Nlitlen || ndist > Noff || nlit < 257) {
279 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
280 b6afd33e 2003-11-23 devnull return 0;
283 b6afd33e 2003-11-23 devnull /* huff table header */
284 b6afd33e 2003-11-23 devnull len = malloc(Nlitlen+Noff);
285 b6afd33e 2003-11-23 devnull lentab = malloc(sizeof(Huff));
286 b6afd33e 2003-11-23 devnull offtab = malloc(sizeof(Huff));
287 b6afd33e 2003-11-23 devnull if(len == nil || lentab == nil || offtab == nil){
288 b6afd33e 2003-11-23 devnull in->error = FlateNoMem;
289 b6afd33e 2003-11-23 devnull goto bad;
291 b6afd33e 2003-11-23 devnull for(i=0; i < Nclen; i++)
292 b6afd33e 2003-11-23 devnull len[i] = 0;
293 b6afd33e 2003-11-23 devnull for(i=0; i<nclen; i++) {
294 b6afd33e 2003-11-23 devnull if(!sregfill(in, 3))
295 b6afd33e 2003-11-23 devnull goto bad;
296 b6afd33e 2003-11-23 devnull len[clenorder[i]] = in->sreg & 0x7;
297 b6afd33e 2003-11-23 devnull in->sreg >>= 3;
298 b6afd33e 2003-11-23 devnull in->nbits -= 3;
301 b6afd33e 2003-11-23 devnull if(!hufftab(lentab, len, Nclen, ClenBits)){
302 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
303 b6afd33e 2003-11-23 devnull goto bad;
306 b6afd33e 2003-11-23 devnull n = nlit+ndist;
307 b6afd33e 2003-11-23 devnull for(i=0; i<n;) {
308 b6afd33e 2003-11-23 devnull nb = lentab->minbits;
309 b6afd33e 2003-11-23 devnull for(;;){
310 b6afd33e 2003-11-23 devnull if(in->nbits<nb && !sregfill(in, nb))
311 b6afd33e 2003-11-23 devnull goto bad;
312 b6afd33e 2003-11-23 devnull c = lentab->flat[in->sreg & lentab->flatmask];
313 b6afd33e 2003-11-23 devnull nb = c & 0xff;
314 b6afd33e 2003-11-23 devnull if(nb > in->nbits){
315 b6afd33e 2003-11-23 devnull if(nb != 0xff)
316 b6afd33e 2003-11-23 devnull continue;
317 b6afd33e 2003-11-23 devnull c = hdecsym(in, lentab, c);
318 b6afd33e 2003-11-23 devnull if(c < 0)
319 b6afd33e 2003-11-23 devnull goto bad;
321 b6afd33e 2003-11-23 devnull c >>= 8;
322 b6afd33e 2003-11-23 devnull in->sreg >>= nb;
323 b6afd33e 2003-11-23 devnull in->nbits -= nb;
328 b6afd33e 2003-11-23 devnull if(c < 16) {
330 b6afd33e 2003-11-23 devnull } else if(c == 16) {
331 b6afd33e 2003-11-23 devnull if(in->nbits<2 && !sregfill(in, 2))
332 b6afd33e 2003-11-23 devnull goto bad;
333 b6afd33e 2003-11-23 devnull j = (in->sreg&0x3)+3;
334 b6afd33e 2003-11-23 devnull in->sreg >>= 2;
335 b6afd33e 2003-11-23 devnull in->nbits -= 2;
336 b6afd33e 2003-11-23 devnull if(i == 0) {
337 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
338 b6afd33e 2003-11-23 devnull goto bad;
340 b6afd33e 2003-11-23 devnull c = len[i-1];
341 b6afd33e 2003-11-23 devnull } else if(c == 17) {
342 b6afd33e 2003-11-23 devnull if(in->nbits<3 && !sregfill(in, 3))
343 b6afd33e 2003-11-23 devnull goto bad;
344 b6afd33e 2003-11-23 devnull j = (in->sreg&0x7)+3;
345 b6afd33e 2003-11-23 devnull in->sreg >>= 3;
346 b6afd33e 2003-11-23 devnull in->nbits -= 3;
348 b6afd33e 2003-11-23 devnull } else if(c == 18) {
349 b6afd33e 2003-11-23 devnull if(in->nbits<7 && !sregfill(in, 7))
350 b6afd33e 2003-11-23 devnull goto bad;
351 b6afd33e 2003-11-23 devnull j = (in->sreg&0x7f)+11;
352 b6afd33e 2003-11-23 devnull in->sreg >>= 7;
353 b6afd33e 2003-11-23 devnull in->nbits -= 7;
355 b6afd33e 2003-11-23 devnull } else {
356 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
357 b6afd33e 2003-11-23 devnull goto bad;
360 b6afd33e 2003-11-23 devnull if(i+j > n) {
361 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
362 b6afd33e 2003-11-23 devnull goto bad;
365 b6afd33e 2003-11-23 devnull while(j) {
366 b6afd33e 2003-11-23 devnull len[i] = c;
372 b6afd33e 2003-11-23 devnull if(!hufftab(lentab, len, nlit, LitlenBits)
373 b6afd33e 2003-11-23 devnull || !hufftab(offtab, &len[nlit], ndist, OffBits)){
374 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
375 b6afd33e 2003-11-23 devnull goto bad;
378 b6afd33e 2003-11-23 devnull res = decode(in, his, lentab, offtab);
380 b6afd33e 2003-11-23 devnull free(len);
381 b6afd33e 2003-11-23 devnull free(lentab);
382 b6afd33e 2003-11-23 devnull free(offtab);
384 b6afd33e 2003-11-23 devnull return res;
387 b6afd33e 2003-11-23 devnull free(len);
388 b6afd33e 2003-11-23 devnull free(lentab);
389 b6afd33e 2003-11-23 devnull free(offtab);
390 b6afd33e 2003-11-23 devnull return 0;
393 b6afd33e 2003-11-23 devnull static int
394 b6afd33e 2003-11-23 devnull decode(Input *in, History *his, Huff *litlentab, Huff *offtab)
396 b6afd33e 2003-11-23 devnull int len, off;
397 b6afd33e 2003-11-23 devnull uchar *hs, *hp, *hq, *he;
401 b6afd33e 2003-11-23 devnull hs = his->his;
402 b6afd33e 2003-11-23 devnull he = hs + HistorySize;
403 b6afd33e 2003-11-23 devnull hp = his->cp;
405 b6afd33e 2003-11-23 devnull for(;;) {
406 b6afd33e 2003-11-23 devnull nb = litlentab->minbits;
407 b6afd33e 2003-11-23 devnull for(;;){
408 b6afd33e 2003-11-23 devnull if(in->nbits<nb && !sregfill(in, nb))
409 b6afd33e 2003-11-23 devnull return 0;
410 b6afd33e 2003-11-23 devnull c = litlentab->flat[in->sreg & litlentab->flatmask];
411 b6afd33e 2003-11-23 devnull nb = c & 0xff;
412 b6afd33e 2003-11-23 devnull if(nb > in->nbits){
413 b6afd33e 2003-11-23 devnull if(nb != 0xff)
414 b6afd33e 2003-11-23 devnull continue;
415 b6afd33e 2003-11-23 devnull c = hdecsym(in, litlentab, c);
416 b6afd33e 2003-11-23 devnull if(c < 0)
417 b6afd33e 2003-11-23 devnull return 0;
419 b6afd33e 2003-11-23 devnull c >>= 8;
420 b6afd33e 2003-11-23 devnull in->sreg >>= nb;
421 b6afd33e 2003-11-23 devnull in->nbits -= nb;
426 b6afd33e 2003-11-23 devnull if(c < 256) {
427 b6afd33e 2003-11-23 devnull /* literal */
428 b6afd33e 2003-11-23 devnull *hp++ = c;
429 b6afd33e 2003-11-23 devnull if(hp == he) {
430 b6afd33e 2003-11-23 devnull his->full = 1;
431 b6afd33e 2003-11-23 devnull if((*in->w)(in->wr, hs, HistorySize) != HistorySize) {
432 b6afd33e 2003-11-23 devnull in->error = FlateOutputFail;
433 b6afd33e 2003-11-23 devnull return 0;
435 b6afd33e 2003-11-23 devnull hp = hs;
437 b6afd33e 2003-11-23 devnull continue;
440 b6afd33e 2003-11-23 devnull if(c == 256)
443 b6afd33e 2003-11-23 devnull if(c > 285) {
444 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
445 b6afd33e 2003-11-23 devnull return 0;
448 b6afd33e 2003-11-23 devnull c -= 257;
449 b6afd33e 2003-11-23 devnull nb = litlenextra[c];
450 b6afd33e 2003-11-23 devnull if(in->nbits < nb && !sregfill(in, nb))
451 b6afd33e 2003-11-23 devnull return 0;
452 b6afd33e 2003-11-23 devnull len = litlenbase[c] + (in->sreg & ((1<<nb)-1));
453 b6afd33e 2003-11-23 devnull in->sreg >>= nb;
454 b6afd33e 2003-11-23 devnull in->nbits -= nb;
456 b6afd33e 2003-11-23 devnull /* get offset */
457 b6afd33e 2003-11-23 devnull nb = offtab->minbits;
458 b6afd33e 2003-11-23 devnull for(;;){
459 b6afd33e 2003-11-23 devnull if(in->nbits<nb && !sregfill(in, nb))
460 b6afd33e 2003-11-23 devnull return 0;
461 b6afd33e 2003-11-23 devnull c = offtab->flat[in->sreg & offtab->flatmask];
462 b6afd33e 2003-11-23 devnull nb = c & 0xff;
463 b6afd33e 2003-11-23 devnull if(nb > in->nbits){
464 b6afd33e 2003-11-23 devnull if(nb != 0xff)
465 b6afd33e 2003-11-23 devnull continue;
466 b6afd33e 2003-11-23 devnull c = hdecsym(in, offtab, c);
467 b6afd33e 2003-11-23 devnull if(c < 0)
468 b6afd33e 2003-11-23 devnull return 0;
470 b6afd33e 2003-11-23 devnull c >>= 8;
471 b6afd33e 2003-11-23 devnull in->sreg >>= nb;
472 b6afd33e 2003-11-23 devnull in->nbits -= nb;
477 b6afd33e 2003-11-23 devnull if(c > 29) {
478 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
479 b6afd33e 2003-11-23 devnull return 0;
482 b6afd33e 2003-11-23 devnull nb = offextra[c];
483 b6afd33e 2003-11-23 devnull if(in->nbits < nb && !sregfill(in, nb))
484 b6afd33e 2003-11-23 devnull return 0;
486 b6afd33e 2003-11-23 devnull off = offbase[c] + (in->sreg & ((1<<nb)-1));
487 b6afd33e 2003-11-23 devnull in->sreg >>= nb;
488 b6afd33e 2003-11-23 devnull in->nbits -= nb;
490 b6afd33e 2003-11-23 devnull hq = hp - off;
491 b6afd33e 2003-11-23 devnull if(hq < hs) {
492 b6afd33e 2003-11-23 devnull if(!his->full) {
493 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
494 b6afd33e 2003-11-23 devnull return 0;
496 b6afd33e 2003-11-23 devnull hq += HistorySize;
499 b6afd33e 2003-11-23 devnull /* slow but correct */
500 b6afd33e 2003-11-23 devnull while(len) {
501 b6afd33e 2003-11-23 devnull *hp = *hq;
504 b6afd33e 2003-11-23 devnull if(hq >= he)
505 b6afd33e 2003-11-23 devnull hq = hs;
506 b6afd33e 2003-11-23 devnull if(hp == he) {
507 b6afd33e 2003-11-23 devnull his->full = 1;
508 b6afd33e 2003-11-23 devnull if((*in->w)(in->wr, hs, HistorySize) != HistorySize) {
509 b6afd33e 2003-11-23 devnull in->error = FlateOutputFail;
510 b6afd33e 2003-11-23 devnull return 0;
512 b6afd33e 2003-11-23 devnull hp = hs;
519 b6afd33e 2003-11-23 devnull his->cp = hp;
521 b6afd33e 2003-11-23 devnull return 1;
524 b6afd33e 2003-11-23 devnull static int
525 b6afd33e 2003-11-23 devnull revcode(int c, int b)
527 b6afd33e 2003-11-23 devnull /* shift encode up so it starts on bit 15 then reverse */
528 b6afd33e 2003-11-23 devnull c <<= (16-b);
529 b6afd33e 2003-11-23 devnull c = revtab[c>>8] | (revtab[c&0xff]<<8);
530 b6afd33e 2003-11-23 devnull return c;
534 b6afd33e 2003-11-23 devnull * construct the huffman decoding arrays and a fast lookup table.
535 b6afd33e 2003-11-23 devnull * the fast lookup is a table indexed by the next flatbits bits,
536 b6afd33e 2003-11-23 devnull * which returns the symbol matched and the number of bits consumed,
537 b6afd33e 2003-11-23 devnull * or the minimum number of bits needed and 0xff if more than flatbits
538 b6afd33e 2003-11-23 devnull * bits are needed.
540 b6afd33e 2003-11-23 devnull * flatbits can be longer than the smallest huffman code,
541 b6afd33e 2003-11-23 devnull * because shorter codes are assigned smaller lexical prefixes.
542 b6afd33e 2003-11-23 devnull * this means assuming zeros for the next few bits will give a
543 b6afd33e 2003-11-23 devnull * conservative answer, in the sense that it will either give the
544 b6afd33e 2003-11-23 devnull * correct answer, or return the minimum number of bits which
545 b6afd33e 2003-11-23 devnull * are needed for an answer.
547 b6afd33e 2003-11-23 devnull static int
548 b6afd33e 2003-11-23 devnull hufftab(Huff *h, char *hb, int maxleaf, int flatbits)
550 b6afd33e 2003-11-23 devnull ulong bitcount[MaxHuffBits];
551 b6afd33e 2003-11-23 devnull ulong c, fc, ec, mincode, code, nc[MaxHuffBits];
552 b6afd33e 2003-11-23 devnull int i, b, minbits, maxbits;
554 b6afd33e 2003-11-23 devnull for(i = 0; i < MaxHuffBits; i++)
555 b6afd33e 2003-11-23 devnull bitcount[i] = 0;
556 b6afd33e 2003-11-23 devnull maxbits = -1;
557 b6afd33e 2003-11-23 devnull minbits = MaxHuffBits + 1;
558 b6afd33e 2003-11-23 devnull for(i=0; i < maxleaf; i++){
559 b6afd33e 2003-11-23 devnull b = hb[i];
561 b6afd33e 2003-11-23 devnull bitcount[b]++;
562 b6afd33e 2003-11-23 devnull if(b < minbits)
563 b6afd33e 2003-11-23 devnull minbits = b;
564 b6afd33e 2003-11-23 devnull if(b > maxbits)
565 b6afd33e 2003-11-23 devnull maxbits = b;
569 b6afd33e 2003-11-23 devnull h->maxbits = maxbits;
570 b6afd33e 2003-11-23 devnull if(maxbits <= 0){
571 b6afd33e 2003-11-23 devnull h->maxbits = 0;
572 b6afd33e 2003-11-23 devnull h->minbits = 0;
573 b6afd33e 2003-11-23 devnull h->flatmask = 0;
574 b6afd33e 2003-11-23 devnull return 1;
576 b6afd33e 2003-11-23 devnull code = 0;
578 b6afd33e 2003-11-23 devnull for(b = 0; b <= maxbits; b++){
579 b6afd33e 2003-11-23 devnull h->last[b] = c;
580 b6afd33e 2003-11-23 devnull c += bitcount[b];
581 b6afd33e 2003-11-23 devnull mincode = code << 1;
582 b6afd33e 2003-11-23 devnull nc[b] = mincode;
583 b6afd33e 2003-11-23 devnull code = mincode + bitcount[b];
584 b6afd33e 2003-11-23 devnull if(code > (1 << b))
585 b6afd33e 2003-11-23 devnull return 0;
586 b6afd33e 2003-11-23 devnull h->maxcode[b] = code - 1;
587 b6afd33e 2003-11-23 devnull h->last[b] += code - 1;
590 b6afd33e 2003-11-23 devnull if(flatbits > maxbits)
591 b6afd33e 2003-11-23 devnull flatbits = maxbits;
592 b6afd33e 2003-11-23 devnull h->flatmask = (1 << flatbits) - 1;
593 b6afd33e 2003-11-23 devnull if(minbits > flatbits)
594 b6afd33e 2003-11-23 devnull minbits = flatbits;
595 b6afd33e 2003-11-23 devnull h->minbits = minbits;
597 b6afd33e 2003-11-23 devnull b = 1 << flatbits;
598 b6afd33e 2003-11-23 devnull for(i = 0; i < b; i++)
599 b6afd33e 2003-11-23 devnull h->flat[i] = ~0;
602 b6afd33e 2003-11-23 devnull * initialize the flat table to include the minimum possible
603 b6afd33e 2003-11-23 devnull * bit length for each code prefix
605 b6afd33e 2003-11-23 devnull for(b = maxbits; b > flatbits; b--){
606 b6afd33e 2003-11-23 devnull code = h->maxcode[b];
607 b6afd33e 2003-11-23 devnull if(code == -1)
609 b6afd33e 2003-11-23 devnull mincode = code + 1 - bitcount[b];
610 b6afd33e 2003-11-23 devnull mincode >>= b - flatbits;
611 b6afd33e 2003-11-23 devnull code >>= b - flatbits;
612 b6afd33e 2003-11-23 devnull for(; mincode <= code; mincode++)
613 b6afd33e 2003-11-23 devnull h->flat[revcode(mincode, flatbits)] = (b << 8) | 0xff;
616 b6afd33e 2003-11-23 devnull for(i = 0; i < maxleaf; i++){
617 b6afd33e 2003-11-23 devnull b = hb[i];
618 b6afd33e 2003-11-23 devnull if(b <= 0)
619 b6afd33e 2003-11-23 devnull continue;
620 b6afd33e 2003-11-23 devnull c = nc[b]++;
621 b6afd33e 2003-11-23 devnull if(b <= flatbits){
622 b6afd33e 2003-11-23 devnull code = (i << 8) | b;
623 b6afd33e 2003-11-23 devnull ec = (c + 1) << (flatbits - b);
624 b6afd33e 2003-11-23 devnull if(ec > (1<<flatbits))
625 b6afd33e 2003-11-23 devnull return 0; /* this is actually an internal error */
626 b6afd33e 2003-11-23 devnull for(fc = c << (flatbits - b); fc < ec; fc++)
627 b6afd33e 2003-11-23 devnull h->flat[revcode(fc, flatbits)] = code;
629 b6afd33e 2003-11-23 devnull if(b > minbits){
630 b6afd33e 2003-11-23 devnull c = h->last[b] - c;
631 b6afd33e 2003-11-23 devnull if(c >= maxleaf)
632 b6afd33e 2003-11-23 devnull return 0;
633 b6afd33e 2003-11-23 devnull h->decode[c] = i;
636 b6afd33e 2003-11-23 devnull return 1;
639 b6afd33e 2003-11-23 devnull static int
640 b6afd33e 2003-11-23 devnull hdecsym(Input *in, Huff *h, int nb)
644 b6afd33e 2003-11-23 devnull if((nb & 0xff) == 0xff)
645 b6afd33e 2003-11-23 devnull nb = nb >> 8;
647 b6afd33e 2003-11-23 devnull nb = nb & 0xff;
648 b6afd33e 2003-11-23 devnull for(; nb <= h->maxbits; nb++){
649 b6afd33e 2003-11-23 devnull if(in->nbits<nb && !sregfill(in, nb))
650 b6afd33e 2003-11-23 devnull return -1;
651 b6afd33e 2003-11-23 devnull c = revtab[in->sreg&0xff]<<8;
652 b6afd33e 2003-11-23 devnull c |= revtab[(in->sreg>>8)&0xff];
653 b6afd33e 2003-11-23 devnull c >>= (16-nb);
654 b6afd33e 2003-11-23 devnull if(c <= h->maxcode[nb]){
655 b6afd33e 2003-11-23 devnull in->sreg >>= nb;
656 b6afd33e 2003-11-23 devnull in->nbits -= nb;
657 b6afd33e 2003-11-23 devnull return h->decode[h->last[nb] - c];
660 b6afd33e 2003-11-23 devnull in->error = FlateCorrupted;
661 b6afd33e 2003-11-23 devnull return -1;
664 b6afd33e 2003-11-23 devnull static int
665 b6afd33e 2003-11-23 devnull sregfill(Input *in, int n)
669 b6afd33e 2003-11-23 devnull while(n > in->nbits) {
670 b6afd33e 2003-11-23 devnull c = (*in->get)(in->getr);
671 b6afd33e 2003-11-23 devnull if(c < 0){
672 b6afd33e 2003-11-23 devnull in->error = FlateInputFail;
673 b6afd33e 2003-11-23 devnull return 0;
675 b6afd33e 2003-11-23 devnull in->sreg |= c<<in->nbits;
676 b6afd33e 2003-11-23 devnull in->nbits += 8;
678 b6afd33e 2003-11-23 devnull return 1;
681 b6afd33e 2003-11-23 devnull static int
682 b6afd33e 2003-11-23 devnull sregunget(Input *in)
684 b6afd33e 2003-11-23 devnull if(in->nbits >= 8) {
685 b6afd33e 2003-11-23 devnull in->error = FlateInternal;
686 b6afd33e 2003-11-23 devnull return 0;
689 b6afd33e 2003-11-23 devnull /* throw other bits on the floor */
690 b6afd33e 2003-11-23 devnull in->nbits = 0;
691 b6afd33e 2003-11-23 devnull in->sreg = 0;
692 b6afd33e 2003-11-23 devnull return 1;
