This source file includes following definitions.
- huft_build
- huft_free
- inflate_codes
- inflate_stored
- inflate_fixed
- inflate_dynamic
- inflate_block
- inflate
1 #define DEBG(x)
2 #define DEBG1(x)
3
4
5
6
7
8
9
10
11 #ifndef lint
12 static char rcsid[] = "$Id: inflate.c,v 0.10 1993/02/04 13:21:06 jloup Exp $";
13 #endif
14
15 #include "gzip.h"
16 #define slide window
17
18 #if defined(STDC_HEADERS) || defined(HAVE_STDLIB_H)
19 # include <sys/types.h>
20 # include <stdlib.h>
21 #endif
22
23 struct huft {
24 uch e;
25 uch b;
26 union {
27 ush n;
28 struct huft *t;
29 } v;
30 };
31
32
33
34 int huft_build OF((unsigned *, unsigned, unsigned, ush *, ush *,
35 struct huft **, int *));
36 int huft_free OF((struct huft *));
37 int inflate_codes OF((struct huft *, struct huft *, int, int));
38 int inflate_stored OF((void));
39 int inflate_fixed OF((void));
40 int inflate_dynamic OF((void));
41 int inflate_block OF((int *));
42 int inflate OF((void));
43
44
45 #define wp outcnt
46 #define flush_output(w) (wp=(w),flush_window())
47
48
49 static unsigned border[] = {
50 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
51 static ush cplens[] = {
52 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
53 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
54
55 static ush cplext[] = {
56 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
57 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99};
58 static ush cpdist[] = {
59 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
60 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
61 8193, 12289, 16385, 24577};
62 static ush cpdext[] = {
63 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
64 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
65 12, 12, 13, 13};
66
67
68 ulg bb;
69 unsigned bk;
70
71 ush mask_bits[] = {
72 0x0000,
73 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
74 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
75 };
76
77 #ifdef CRYPT
78 uch cc;
79 # define NEXTBYTE() \
80 (decrypt ? (cc = get_byte(), zdecode(cc), cc) : get_byte())
81 #else
82 # define NEXTBYTE() (uch)get_byte()
83 #endif
84 #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}}
85 #define DUMPBITS(n) {b>>=(n);k-=(n);}
86
87 int lbits = 9;
88 int dbits = 6;
89
90
91
92 #define BMAX 16
93 #define N_MAX 288
94
95
96 unsigned hufts;
97
98
99 int huft_build(b, n, s, d, e, t, m)
100 unsigned *b;
101 unsigned n;
102 unsigned s;
103 ush *d;
104 ush *e;
105 struct huft **t;
106 int *m;
107
108
109
110
111
112 {
113 unsigned a;
114 unsigned c[BMAX+1];
115 unsigned f;
116 int g;
117 int h;
118 register unsigned i;
119 register unsigned j;
120 register int k;
121 int l;
122 register unsigned *p;
123 register struct huft *q;
124 struct huft r;
125 struct huft *u[BMAX];
126 unsigned v[N_MAX];
127 register int w;
128 unsigned x[BMAX+1];
129 unsigned *xp;
130 int y;
131 unsigned z;
132
133 DEBG("huft1 ");
134
135
136 memzero(c, sizeof(c));
137 p = b; i = n;
138 do {
139 c[*p++]++;
140 } while (--i);
141 if (c[0] == n)
142 {
143 *t = (struct huft *)NULL;
144 *m = 0;
145 return 0;
146 }
147
148 DEBG("huft2 ");
149
150
151 l = *m;
152 for (j = 1; j <= BMAX; j++)
153 if (c[j])
154 break;
155 k = j;
156 if ((unsigned)l < j)
157 l = j;
158 for (i = BMAX; i; i--)
159 if (c[i])
160 break;
161 g = i;
162 if ((unsigned)l > i)
163 l = i;
164 *m = l;
165
166 DEBG("huft3 ");
167
168
169 for (y = 1 << j; j < i; j++, y <<= 1)
170 if ((y -= c[j]) < 0)
171 return 2;
172 if ((y -= c[i]) < 0)
173 return 2;
174 c[i] += y;
175
176 DEBG("huft4 ");
177
178
179 x[1] = j = 0;
180 p = c + 1; xp = x + 2;
181 while (--i) {
182 *xp++ = (j += *p++);
183 }
184
185 DEBG("huft5 ");
186
187
188 p = b; i = 0;
189 do {
190 if ((j = *p++) != 0)
191 v[x[j]++] = i;
192 } while (++i < n);
193
194 DEBG("h6 ");
195
196
197 x[0] = i = 0;
198 p = v;
199 h = -1;
200 w = -l;
201 u[0] = (struct huft *)NULL;
202 q = (struct huft *)NULL;
203 z = 0;
204 DEBG("h6a ");
205
206
207 for (; k <= g; k++)
208 {
209 DEBG("h6b ");
210 a = c[k];
211 while (a--)
212 {
213 DEBG("h6b1 ");
214
215
216 while (k > w + l)
217 {
218 DEBG1("1 ");
219 h++;
220 w += l;
221
222
223 z = (z = g - w) > (unsigned)l ? l : z;
224 if ((f = 1 << (j = k - w)) > a + 1)
225 {
226 DEBG1("2 ");
227 f -= a + 1;
228 xp = c + k;
229 while (++j < z)
230 {
231 if ((f <<= 1) <= *++xp)
232 break;
233 f -= *xp;
234 }
235 }
236 DEBG1("3 ");
237 z = 1 << j;
238
239
240 if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) ==
241 (struct huft *)NULL)
242 {
243 DEBG1("31 ");
244 error("malloc failed\n");
245 if (h)
246 huft_free(u[0]);
247 return 3;
248 }
249 DEBG1("4 ");
250 hufts += z + 1;
251 *t = q + 1;
252 *(t = &(q->v.t)) = (struct huft *)NULL;
253 u[h] = ++q;
254
255 DEBG1("5 ");
256
257 if (h)
258 {
259 x[h] = i;
260 r.b = (uch)l;
261 r.e = (uch)(16 + j);
262 r.v.t = q;
263 j = i >> (w - l);
264 u[h-1][j] = r;
265 }
266 DEBG1("6 ");
267 }
268 DEBG("h6c ");
269
270
271 r.b = (uch)(k - w);
272 if (p >= v + n)
273 r.e = 99;
274 else if (*p < s)
275 {
276 r.e = (uch)(*p < 256 ? 16 : 15);
277 r.v.n = *p++;
278 }
279 else
280 {
281 r.e = (uch)e[*p - s];
282 r.v.n = d[*p++ - s];
283 }
284 DEBG("h6d ");
285
286
287 f = 1 << (k - w);
288 for (j = i >> w; j < z; j += f)
289 q[j] = r;
290
291
292 for (j = 1 << (k - 1); i & j; j >>= 1)
293 i ^= j;
294 i ^= j;
295
296
297 while ((i & ((1 << w) - 1)) != x[h])
298 {
299 h--;
300 w -= l;
301 }
302 DEBG("h6e ");
303 }
304 DEBG("h6f ");
305 }
306
307 DEBG("huft7 ");
308
309
310 return y != 0 && g != 1;
311 }
312
313
314
315 int huft_free(t)
316 struct huft *t;
317
318
319
320 {
321 register struct huft *p, *q;
322
323
324
325 p = t;
326 while (p != (struct huft *)NULL)
327 {
328 q = (--p)->v.t;
329 free(p);
330 p = q;
331 }
332 return 0;
333 }
334
335
336 int inflate_codes(tl, td, bl, bd)
337 struct huft *tl, *td;
338 int bl, bd;
339
340
341 {
342 register unsigned e;
343 unsigned n, d;
344 unsigned w;
345 struct huft *t;
346 unsigned ml, md;
347 register ulg b;
348 register unsigned k;
349
350
351
352 b = bb;
353 k = bk;
354 w = wp;
355
356
357 ml = mask_bits[bl];
358 md = mask_bits[bd];
359 for (;;)
360 {
361 NEEDBITS((unsigned)bl)
362 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
363 do {
364 if (e == 99)
365 return 1;
366 DUMPBITS(t->b)
367 e -= 16;
368 NEEDBITS(e)
369 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
370 DUMPBITS(t->b)
371 if (e == 16)
372 {
373 slide[w++] = (uch)t->v.n;
374 if (w == WSIZE)
375 {
376 flush_output(w);
377 w = 0;
378 }
379 }
380 else
381 {
382
383 if (e == 15)
384 break;
385
386
387 NEEDBITS(e)
388 n = t->v.n + ((unsigned)b & mask_bits[e]);
389 DUMPBITS(e);
390
391
392 NEEDBITS((unsigned)bd)
393 if ((e = (t = td + ((unsigned)b & md))->e) > 16)
394 do {
395 if (e == 99)
396 return 1;
397 DUMPBITS(t->b)
398 e -= 16;
399 NEEDBITS(e)
400 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
401 DUMPBITS(t->b)
402 NEEDBITS(e)
403 d = w - t->v.n - ((unsigned)b & mask_bits[e]);
404 DUMPBITS(e)
405
406
407 do {
408 n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
409 #if !defined(NOMEMCPY) && !defined(DEBUG)
410 if (w - d >= e)
411 {
412 memcpy(slide + w, slide + d, e);
413 w += e;
414 d += e;
415 }
416 else
417 #endif
418 do {
419 slide[w++] = slide[d++];
420 } while (--e);
421 if (w == WSIZE)
422 {
423 flush_output(w);
424 w = 0;
425 }
426 } while (n);
427 }
428 }
429
430
431
432 wp = w;
433 bb = b;
434 bk = k;
435
436
437 return 0;
438 }
439
440
441
442 int inflate_stored()
443
444 {
445 unsigned n;
446 unsigned w;
447 register ulg b;
448 register unsigned k;
449
450 DEBG("<stor");
451
452
453 b = bb;
454 k = bk;
455 w = wp;
456
457
458
459 n = k & 7;
460 DUMPBITS(n);
461
462
463
464 NEEDBITS(16)
465 n = ((unsigned)b & 0xffff);
466 DUMPBITS(16)
467 NEEDBITS(16)
468 if (n != (unsigned)((~b) & 0xffff))
469 return 1;
470 DUMPBITS(16)
471
472
473
474 while (n--)
475 {
476 NEEDBITS(8)
477 slide[w++] = (uch)b;
478 if (w == WSIZE)
479 {
480 flush_output(w);
481 w = 0;
482 }
483 DUMPBITS(8)
484 }
485
486
487
488 wp = w;
489 bb = b;
490 bk = k;
491
492 DEBG(">");
493 return 0;
494 }
495
496
497
498 int inflate_fixed()
499
500
501
502 {
503 int i;
504 struct huft *tl;
505 struct huft *td;
506 int bl;
507 int bd;
508 unsigned l[288];
509
510 DEBG("<fix");
511
512
513 for (i = 0; i < 144; i++)
514 l[i] = 8;
515 for (; i < 256; i++)
516 l[i] = 9;
517 for (; i < 280; i++)
518 l[i] = 7;
519 for (; i < 288; i++)
520 l[i] = 8;
521 bl = 7;
522 if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
523 return i;
524
525
526
527 for (i = 0; i < 30; i++)
528 l[i] = 5;
529 bd = 5;
530 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
531 {
532 huft_free(tl);
533
534 DEBG(">");
535 return i;
536 }
537
538
539
540 if (inflate_codes(tl, td, bl, bd))
541 return 1;
542
543
544
545 huft_free(tl);
546 huft_free(td);
547 return 0;
548 }
549
550
551
552 int inflate_dynamic()
553
554 {
555 int i;
556 unsigned j;
557 unsigned l;
558 unsigned m;
559 unsigned n;
560 struct huft *tl;
561 struct huft *td;
562 int bl;
563 int bd;
564 unsigned nb;
565 unsigned nl;
566 unsigned nd;
567 #ifdef PKZIP_BUG_WORKAROUND
568 unsigned ll[288+32];
569 #else
570 unsigned ll[286+30];
571 #endif
572 register ulg b;
573 register unsigned k;
574
575 DEBG("<dyn");
576
577
578 b = bb;
579 k = bk;
580
581
582
583 NEEDBITS(5)
584 nl = 257 + ((unsigned)b & 0x1f);
585 DUMPBITS(5)
586 NEEDBITS(5)
587 nd = 1 + ((unsigned)b & 0x1f);
588 DUMPBITS(5)
589 NEEDBITS(4)
590 nb = 4 + ((unsigned)b & 0xf);
591 DUMPBITS(4)
592 #ifdef PKZIP_BUG_WORKAROUND
593 if (nl > 288 || nd > 32)
594 #else
595 if (nl > 286 || nd > 30)
596 #endif
597 return 1;
598
599 DEBG("dyn1 ");
600
601
602 for (j = 0; j < nb; j++)
603 {
604 NEEDBITS(3)
605 ll[border[j]] = (unsigned)b & 7;
606 DUMPBITS(3)
607 }
608 for (; j < 19; j++)
609 ll[border[j]] = 0;
610
611 DEBG("dyn2 ");
612
613
614 bl = 7;
615 if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
616 {
617 if (i == 1)
618 huft_free(tl);
619 return i;
620 }
621
622 DEBG("dyn3 ");
623
624
625 n = nl + nd;
626 m = mask_bits[bl];
627 i = l = 0;
628 while ((unsigned)i < n)
629 {
630 NEEDBITS((unsigned)bl)
631 j = (td = tl + ((unsigned)b & m))->b;
632 DUMPBITS(j)
633 j = td->v.n;
634 if (j < 16)
635 ll[i++] = l = j;
636 else if (j == 16)
637 {
638 NEEDBITS(2)
639 j = 3 + ((unsigned)b & 3);
640 DUMPBITS(2)
641 if ((unsigned)i + j > n)
642 return 1;
643 while (j--)
644 ll[i++] = l;
645 }
646 else if (j == 17)
647 {
648 NEEDBITS(3)
649 j = 3 + ((unsigned)b & 7);
650 DUMPBITS(3)
651 if ((unsigned)i + j > n)
652 return 1;
653 while (j--)
654 ll[i++] = 0;
655 l = 0;
656 }
657 else
658 {
659 NEEDBITS(7)
660 j = 11 + ((unsigned)b & 0x7f);
661 DUMPBITS(7)
662 if ((unsigned)i + j > n)
663 return 1;
664 while (j--)
665 ll[i++] = 0;
666 l = 0;
667 }
668 }
669
670 DEBG("dyn4 ");
671
672
673 huft_free(tl);
674
675 DEBG("dyn5 ");
676
677
678 bb = b;
679 bk = k;
680
681 DEBG("dyn5a ");
682
683
684 bl = lbits;
685 if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
686 {
687 DEBG("dyn5b ");
688 if (i == 1) {
689 error(" incomplete literal tree\n");
690 huft_free(tl);
691 }
692 return i;
693 }
694 DEBG("dyn5c ");
695 bd = dbits;
696 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
697 {
698 DEBG("dyn5d ");
699 if (i == 1) {
700 error(" incomplete distance tree\n");
701 #ifdef PKZIP_BUG_WORKAROUND
702 i = 0;
703 }
704 #else
705 huft_free(td);
706 }
707 huft_free(tl);
708 return i;
709 #endif
710 }
711
712 DEBG("dyn6 ");
713
714
715 if (inflate_codes(tl, td, bl, bd))
716 return 1;
717
718 DEBG("dyn7 ");
719
720
721 huft_free(tl);
722 huft_free(td);
723
724 DEBG(">");
725 return 0;
726 }
727
728
729
730 int inflate_block(e)
731 int *e;
732
733 {
734 unsigned t;
735 register ulg b;
736 register unsigned k;
737
738 DEBG("<blk");
739
740
741 b = bb;
742 k = bk;
743
744
745
746 NEEDBITS(1)
747 *e = (int)b & 1;
748 DUMPBITS(1)
749
750
751
752 NEEDBITS(2)
753 t = (unsigned)b & 3;
754 DUMPBITS(2)
755
756
757
758 bb = b;
759 bk = k;
760
761
762 if (t == 2)
763 return inflate_dynamic();
764 if (t == 0)
765 return inflate_stored();
766 if (t == 1)
767 return inflate_fixed();
768
769 DEBG(">");
770
771
772 return 2;
773 }
774
775
776
777 int inflate()
778
779 {
780 int e;
781 int r;
782 unsigned h;
783
784
785
786 wp = 0;
787 bk = 0;
788 bb = 0;
789
790
791
792 h = 0;
793 do {
794 hufts = 0;
795 if ((r = inflate_block(&e)) != 0)
796 return r;
797 if (hufts > h)
798 h = hufts;
799 } while (!e);
800
801
802
803
804 while (bk >= 8) {
805 bk -= 8;
806 inptr--;
807 }
808
809
810 flush_output(wp);
811
812
813
814 #ifdef DEBUG
815 fprintf(stderr, "<%u> ", h);
816 #endif
817 return 0;
818 }