1/* inflate.c -- zlib decompression
2 * Copyright (C) 1995-2010 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/*
7 * Change history:
8 *
9 * 1.2.beta0 24 Nov 2002
10 * - First version -- complete rewrite of inflate to simplify code, avoid

--- 29 unchanged lines hidden (view full) ---

40 *
41 * 1.2.beta4 1 Jan 2003
42 * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings
43 * - Move a comment on output buffer sizes from inffast.c to inflate.c
44 * - Add comments in inffast.c to introduce the inflate_fast() routine
45 * - Rearrange window copies in inflate_fast() for speed and simplification
46 * - Unroll last copy for window match in inflate_fast()
47 * - Use local copies of window variables in inflate_fast() for speed
48 * - Pull out common wnext == 0 case for speed in inflate_fast()
49 * - Make op and len in inflate_fast() unsigned for consistency
50 * - Add FAR to lcode and dcode declarations in inflate_fast()
51 * - Simplified bad distance check in inflate_fast()
52 * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new
53 * source file infback.c to provide a call-back interface to inflate for
54 * programs like gzip and unzip -- uses window as output buffer to avoid
55 * window copying
56 *

--- 55 unchanged lines hidden (view full) ---

112 strm->adler = 1; /* to support ill-conceived Java test suite */
113 state->mode = HEAD;
114 state->last = 0;
115 state->havedict = 0;
116 state->dmax = 32768U;
117 state->head = Z_NULL;
118 state->wsize = 0;
119 state->whave = 0;
120 state->wnext = 0;
121 state->hold = 0;
122 state->bits = 0;
123 state->lencode = state->distcode = state->next = state->codes;
124 state->sane = 1;
125 state->back = -1;
126 Tracev((stderr, "inflate: reset\n"));
127 return Z_OK;
128}
129
130int ZEXPORT inflateReset2(strm, windowBits)
131z_streamp strm;
132int windowBits;
133{
134 int wrap;
135 struct inflate_state FAR *state;
136
137 /* get the state */
138 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
139 state = (struct inflate_state FAR *)strm->state;
140
141 /* extract wrap request from windowBits parameter */
142 if (windowBits < 0) {
143 wrap = 0;
144 windowBits = -windowBits;
145 }
146 else {
147 wrap = (windowBits >> 4) + 1;
148#ifdef GUNZIP
149 if (windowBits < 48)
150 windowBits &= 15;
151#endif
152 }
153
154 /* set number of window bits, free window if different */
155 if (windowBits && (windowBits < 8 || windowBits > 15))
156 return Z_STREAM_ERROR;
157 if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
158 ZFREE(strm, state->window);
159 state->window = Z_NULL;
160 }
161
162 /* update state and reset the rest of it */
163 state->wrap = wrap;
164 state->wbits = (unsigned)windowBits;
165 return inflateReset(strm);
166}
167
168int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
169z_streamp strm;
170int windowBits;
171const char *version;
172int stream_size;
173{
174 int ret;
175 struct inflate_state FAR *state;
176
177 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
178 stream_size != (int)(sizeof(z_stream)))
179 return Z_VERSION_ERROR;
180 if (strm == Z_NULL) return Z_STREAM_ERROR;
181 strm->msg = Z_NULL; /* in case we return an error */
182 if (strm->zalloc == (alloc_func)0) {
183 strm->zalloc = zcalloc;
184 strm->opaque = (voidpf)0;
185 }
186 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
187 state = (struct inflate_state FAR *)
188 ZALLOC(strm, 1, sizeof(struct inflate_state));
189 if (state == Z_NULL) return Z_MEM_ERROR;
190 Tracev((stderr, "inflate: allocated\n"));
191 strm->state = (struct internal_state FAR *)state;
192 state->window = Z_NULL;
193 ret = inflateReset2(strm, windowBits);
194 if (ret != Z_OK) {
195 ZFREE(strm, state);
196 strm->state = Z_NULL;
197 }
198 return ret;
199}
200
201int ZEXPORT inflateInit_(strm, version, stream_size)
202z_streamp strm;
203const char *version;
204int stream_size;
205{
206 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
207}
208
209int ZEXPORT inflatePrime(strm, bits, value)
210z_streamp strm;
211int bits;
212int value;
213{
214 struct inflate_state FAR *state;
215
216 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
217 state = (struct inflate_state FAR *)strm->state;
218 if (bits < 0) {
219 state->hold = 0;
220 state->bits = 0;
221 return Z_OK;
222 }
223 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
224 value &= (1L << bits) - 1;
225 state->hold += value << state->bits;
226 state->bits += bits;
227 return Z_OK;
228}
229
230/*
231 Return state with length and distance decoding tables and index sizes set to
232 fixed code decoding. Normally this returns fixed tables from inffixed.h.
233 If BUILDFIXED is defined, then instead this routine builds the tables the
234 first time it's called, and returns those tables the first time and
235 thereafter. This reduces the size of the code by about 2K bytes, in
236 exchange for a little execution time. However, BUILDFIXED should not be
237 used for threaded applications, since the rewriting of the tables and virgin

--- 132 unchanged lines hidden (view full) ---

370 ZALLOC(strm, 1U << state->wbits,
371 sizeof(unsigned char));
372 if (state->window == Z_NULL) return 1;
373 }
374
375 /* if window not in use yet, initialize */
376 if (state->wsize == 0) {
377 state->wsize = 1U << state->wbits;
378 state->wnext = 0;
379 state->whave = 0;
380 }
381
382 /* copy state->wsize or less output bytes into the circular window */
383 copy = out - strm->avail_out;
384 if (copy >= state->wsize) {
385 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
386 state->wnext = 0;
387 state->whave = state->wsize;
388 }
389 else {
390 dist = state->wsize - state->wnext;
391 if (dist > copy) dist = copy;
392 zmemcpy(state->window + state->wnext, strm->next_out - copy, dist);
393 copy -= dist;
394 if (copy) {
395 zmemcpy(state->window, strm->next_out - copy, copy);
396 state->wnext = copy;
397 state->whave = state->wsize;
398 }
399 else {
400 state->wnext += dist;
401 if (state->wnext == state->wsize) state->wnext = 0;
402 if (state->whave < state->wsize) state->whave += dist;
403 }
404 }
405 return 0;
406}
407
408/* Macros for inflate(): */
409

--- 184 unchanged lines hidden (view full) ---

594 unsigned char FAR *next; /* next input */
595 unsigned char FAR *put; /* next output */
596 unsigned have, left; /* available input and output */
597 unsigned long hold; /* bit buffer */
598 unsigned bits; /* bits in bit buffer */
599 unsigned in, out; /* save starting available input and output */
600 unsigned copy; /* number of stored or match bytes to copy */
601 unsigned char FAR *from; /* where to copy match bytes from */
602 code here; /* current decoding table entry */
603 code last; /* parent table entry */
604 unsigned len; /* length to copy for repeats, bits to drop */
605 int ret; /* return code */
606#ifdef GUNZIP
607 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
608#endif
609 static const unsigned short order[19] = /* permutation of code lengths */
610 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};

--- 38 unchanged lines hidden (view full) ---

649 }
650 if (BITS(4) != Z_DEFLATED) {
651 strm->msg = (char *)"unknown compression method";
652 state->mode = BAD;
653 break;
654 }
655 DROPBITS(4);
656 len = BITS(4) + 8;
657 if (state->wbits == 0)
658 state->wbits = len;
659 else if (len > state->wbits) {
660 strm->msg = (char *)"invalid window size";
661 state->mode = BAD;
662 break;
663 }
664 state->dmax = 1U << len;
665 Tracev((stderr, "inflate: zlib header ok\n"));
666 strm->adler = state->check = adler32(0L, Z_NULL, 0);
667 state->mode = hold & 0x200 ? DICTID : TYPE;

--- 135 unchanged lines hidden (view full) ---

803 case DICT:
804 if (state->havedict == 0) {
805 RESTORE();
806 return Z_NEED_DICT;
807 }
808 strm->adler = state->check = adler32(0L, Z_NULL, 0);
809 state->mode = TYPE;
810 case TYPE:
811 if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
812 case TYPEDO:
813 if (state->last) {
814 BYTEBITS();
815 state->mode = CHECK;
816 break;
817 }
818 NEEDBITS(3);
819 state->last = BITS(1);
820 DROPBITS(1);
821 switch (BITS(2)) {
822 case 0: /* stored block */
823 Tracev((stderr, "inflate: stored block%s\n",
824 state->last ? " (last)" : ""));
825 state->mode = STORED;
826 break;
827 case 1: /* fixed block */
828 fixedtables(state);
829 Tracev((stderr, "inflate: fixed codes block%s\n",
830 state->last ? " (last)" : ""));
831 state->mode = LEN_; /* decode codes */
832 if (flush == Z_TREES) {
833 DROPBITS(2);
834 goto inf_leave;
835 }
836 break;
837 case 2: /* dynamic block */
838 Tracev((stderr, "inflate: dynamic codes block%s\n",
839 state->last ? " (last)" : ""));
840 state->mode = TABLE;
841 break;
842 case 3:
843 strm->msg = (char *)"invalid block type";

--- 8 unchanged lines hidden (view full) ---

852 strm->msg = (char *)"invalid stored block lengths";
853 state->mode = BAD;
854 break;
855 }
856 state->length = (unsigned)hold & 0xffff;
857 Tracev((stderr, "inflate: stored length %u\n",
858 state->length));
859 INITBITS();
860 state->mode = COPY_;
861 if (flush == Z_TREES) goto inf_leave;
862 case COPY_:
863 state->mode = COPY;
864 case COPY:
865 copy = state->length;
866 if (copy) {
867 if (copy > have) copy = have;
868 if (copy > left) copy = left;
869 if (copy == 0) goto inf_leave;
870 zmemcpy(put, next, copy);

--- 44 unchanged lines hidden (view full) ---

915 break;
916 }
917 Tracev((stderr, "inflate: code lengths ok\n"));
918 state->have = 0;
919 state->mode = CODELENS;
920 case CODELENS:
921 while (state->have < state->nlen + state->ndist) {
922 for (;;) {
923 here = state->lencode[BITS(state->lenbits)];
924 if ((unsigned)(here.bits) <= bits) break;
925 PULLBYTE();
926 }
927 if (here.val < 16) {
928 NEEDBITS(here.bits);
929 DROPBITS(here.bits);
930 state->lens[state->have++] = here.val;
931 }
932 else {
933 if (here.val == 16) {
934 NEEDBITS(here.bits + 2);
935 DROPBITS(here.bits);
936 if (state->have == 0) {
937 strm->msg = (char *)"invalid bit length repeat";
938 state->mode = BAD;
939 break;
940 }
941 len = state->lens[state->have - 1];
942 copy = 3 + BITS(2);
943 DROPBITS(2);
944 }
945 else if (here.val == 17) {
946 NEEDBITS(here.bits + 3);
947 DROPBITS(here.bits);
948 len = 0;
949 copy = 3 + BITS(3);
950 DROPBITS(3);
951 }
952 else {
953 NEEDBITS(here.bits + 7);
954 DROPBITS(here.bits);
955 len = 0;
956 copy = 11 + BITS(7);
957 DROPBITS(7);
958 }
959 if (state->have + copy > state->nlen + state->ndist) {
960 strm->msg = (char *)"invalid bit length repeat";
961 state->mode = BAD;
962 break;
963 }
964 while (copy--)
965 state->lens[state->have++] = (unsigned short)len;
966 }
967 }
968
969 /* handle error breaks in while */
970 if (state->mode == BAD) break;
971
972 /* check for end-of-block code (better have one) */
973 if (state->lens[256] == 0) {
974 strm->msg = (char *)"invalid code -- missing end-of-block";
975 state->mode = BAD;
976 break;
977 }
978
979 /* build code tables -- note: do not change the lenbits or distbits
980 values here (9 and 6) without reading the comments in inftrees.h
981 concerning the ENOUGH constants, which depend on those values */
982 state->next = state->codes;
983 state->lencode = (code const FAR *)(state->next);
984 state->lenbits = 9;
985 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
986 &(state->lenbits), state->work);
987 if (ret) {
988 strm->msg = (char *)"invalid literal/lengths set";
989 state->mode = BAD;

--- 4 unchanged lines hidden (view full) ---

994 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
995 &(state->next), &(state->distbits), state->work);
996 if (ret) {
997 strm->msg = (char *)"invalid distances set";
998 state->mode = BAD;
999 break;
1000 }
1001 Tracev((stderr, "inflate: codes ok\n"));
1002 state->mode = LEN_;
1003 if (flush == Z_TREES) goto inf_leave;
1004 case LEN_:
1005 state->mode = LEN;
1006 case LEN:
1007 if (have >= 6 && left >= 258) {
1008 RESTORE();
1009 inflate_fast(strm, out);
1010 LOAD();
1011 if (state->mode == TYPE)
1012 state->back = -1;
1013 break;
1014 }
1015 state->back = 0;
1016 for (;;) {
1017 here = state->lencode[BITS(state->lenbits)];
1018 if ((unsigned)(here.bits) <= bits) break;
1019 PULLBYTE();
1020 }
1021 if (here.op && (here.op & 0xf0) == 0) {
1022 last = here;
1023 for (;;) {
1024 here = state->lencode[last.val +
1025 (BITS(last.bits + last.op) >> last.bits)];
1026 if ((unsigned)(last.bits + here.bits) <= bits) break;
1027 PULLBYTE();
1028 }
1029 DROPBITS(last.bits);
1030 state->back += last.bits;
1031 }
1032 DROPBITS(here.bits);
1033 state->back += here.bits;
1034 state->length = (unsigned)here.val;
1035 if ((int)(here.op) == 0) {
1036 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
1037 "inflate: literal '%c'\n" :
1038 "inflate: literal 0x%02x\n", here.val));
1039 state->mode = LIT;
1040 break;
1041 }
1042 if (here.op & 32) {
1043 Tracevv((stderr, "inflate: end of block\n"));
1044 state->back = -1;
1045 state->mode = TYPE;
1046 break;
1047 }
1048 if (here.op & 64) {
1049 strm->msg = (char *)"invalid literal/length code";
1050 state->mode = BAD;
1051 break;
1052 }
1053 state->extra = (unsigned)(here.op) & 15;
1054 state->mode = LENEXT;
1055 case LENEXT:
1056 if (state->extra) {
1057 NEEDBITS(state->extra);
1058 state->length += BITS(state->extra);
1059 DROPBITS(state->extra);
1060 state->back += state->extra;
1061 }
1062 Tracevv((stderr, "inflate: length %u\n", state->length));
1063 state->was = state->length;
1064 state->mode = DIST;
1065 case DIST:
1066 for (;;) {
1067 here = state->distcode[BITS(state->distbits)];
1068 if ((unsigned)(here.bits) <= bits) break;
1069 PULLBYTE();
1070 }
1071 if ((here.op & 0xf0) == 0) {
1072 last = here;
1073 for (;;) {
1074 here = state->distcode[last.val +
1075 (BITS(last.bits + last.op) >> last.bits)];
1076 if ((unsigned)(last.bits + here.bits) <= bits) break;
1077 PULLBYTE();
1078 }
1079 DROPBITS(last.bits);
1080 state->back += last.bits;
1081 }
1082 DROPBITS(here.bits);
1083 state->back += here.bits;
1084 if (here.op & 64) {
1085 strm->msg = (char *)"invalid distance code";
1086 state->mode = BAD;
1087 break;
1088 }
1089 state->offset = (unsigned)here.val;
1090 state->extra = (unsigned)(here.op) & 15;
1091 state->mode = DISTEXT;
1092 case DISTEXT:
1093 if (state->extra) {
1094 NEEDBITS(state->extra);
1095 state->offset += BITS(state->extra);
1096 DROPBITS(state->extra);
1097 state->back += state->extra;
1098 }
1099#ifdef INFLATE_STRICT
1100 if (state->offset > state->dmax) {
1101 strm->msg = (char *)"invalid distance too far back";
1102 state->mode = BAD;
1103 break;
1104 }
1105#endif
1106 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1107 state->mode = MATCH;
1108 case MATCH:
1109 if (left == 0) goto inf_leave;
1110 copy = out - left;
1111 if (state->offset > copy) { /* copy from window */
1112 copy = state->offset - copy;
1113 if (copy > state->whave) {
1114 if (state->sane) {
1115 strm->msg = (char *)"invalid distance too far back";
1116 state->mode = BAD;
1117 break;
1118 }
1119#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1120 Trace((stderr, "inflate.c too far\n"));
1121 copy -= state->whave;
1122 if (copy > state->length) copy = state->length;
1123 if (copy > left) copy = left;
1124 left -= copy;
1125 state->length -= copy;
1126 do {
1127 *put++ = 0;
1128 } while (--copy);
1129 if (state->length == 0) state->mode = LEN;
1130 break;
1131#endif
1132 }
1133 if (copy > state->wnext) {
1134 copy -= state->wnext;
1135 from = state->window + (state->wsize - copy);
1136 }
1137 else
1138 from = state->window + (state->wnext - copy);
1139 if (copy > state->length) copy = state->length;
1140 }
1141 else { /* copy from output */
1142 from = put - state->offset;
1143 copy = state->length;
1144 }
1145 if (copy > left) copy = left;
1146 left -= copy;

--- 76 unchanged lines hidden (view full) ---

1223 out -= strm->avail_out;
1224 strm->total_in += in;
1225 strm->total_out += out;
1226 state->total += out;
1227 if (state->wrap && out)
1228 strm->adler = state->check =
1229 UPDATE(state->check, strm->next_out - out, out);
1230 strm->data_type = state->bits + (state->last ? 64 : 0) +
1231 (state->mode == TYPE ? 128 : 0) +
1232 (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1233 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1234 ret = Z_BUF_ERROR;
1235 return ret;
1236}
1237
1238int ZEXPORT inflateEnd(strm)
1239z_streamp strm;
1240{

--- 203 unchanged lines hidden (view full) ---

1444 if (window != Z_NULL) {
1445 wsize = 1U << state->wbits;
1446 zmemcpy(window, state->window, wsize);
1447 }
1448 copy->window = window;
1449 dest->state = (struct internal_state FAR *)copy;
1450 return Z_OK;
1451}
1452
1453int ZEXPORT inflateUndermine(strm, subvert)
1454z_streamp strm;
1455int subvert;
1456{
1457 struct inflate_state FAR *state;
1458
1459 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1460 state = (struct inflate_state FAR *)strm->state;
1461 state->sane = !subvert;
1462#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1463 return Z_OK;
1464#else
1465 state->sane = 1;
1466 return Z_DATA_ERROR;
1467#endif
1468}
1469
1470long ZEXPORT inflateMark(strm)
1471z_streamp strm;
1472{
1473 struct inflate_state FAR *state;
1474
1475 if (strm == Z_NULL || strm->state == Z_NULL) return -1L << 16;
1476 state = (struct inflate_state FAR *)strm->state;
1477 return ((long)(state->back) << 16) +
1478 (state->mode == COPY ? state->length :
1479 (state->mode == MATCH ? state->was - state->length : 0));
1480}