summaryrefslogtreecommitdiff
path: root/infblock.c
diff options
context:
space:
mode:
Diffstat (limited to 'infblock.c')
-rw-r--r--infblock.c324
1 files changed, 324 insertions, 0 deletions
diff --git a/infblock.c b/infblock.c
new file mode 100644
index 0000000..3a58280
--- /dev/null
+++ b/infblock.c
@@ -0,0 +1,324 @@
1/* infblock.c -- interpret and process block types to last block
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include "zutil.h"
7#include "infblock.h"
8#include "inftrees.h"
9#include "infcodes.h"
10#include "infutil.h"
11
12struct inflate_codes_state {int dummy;}; /* for buggy compilers */
13
14/* Table for deflate from PKZIP's appnote.txt. */
15local uInt border[] = { /* Order of the bit length code lengths */
16 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
17
18/*
19 Notes beyond the 1.93a appnote.txt:
20
21 1. Distance pointers never point before the beginning of the output
22 stream.
23 2. Distance pointers can point back across blocks, up to 32k away.
24 3. There is an implied maximum of 7 bits for the bit length table and
25 15 bits for the actual data.
26 4. If only one code exists, then it is encoded using one bit. (Zero
27 would be more efficient, but perhaps a little confusing.) If two
28 codes exist, they are coded using one bit each (0 and 1).
29 5. There is no way of sending zero distance codes--a dummy must be
30 sent if there are none. (History: a pre 2.0 version of PKZIP would
31 store blocks with no distance codes, but this was discovered to be
32 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
33 zero distance codes, which is sent as one code of zero bits in
34 length.
35 6. There are up to 286 literal/length codes. Code 256 represents the
36 end-of-block. Note however that the static length tree defines
37 288 codes just to fill out the Huffman codes. Codes 286 and 287
38 cannot be used though, since there is no length base or extra bits
39 defined for them. Similarily, there are up to 30 distance codes.
40 However, static trees define 32 codes (all 5 bits) to fill out the
41 Huffman codes, but the last two had better not show up in the data.
42 7. Unzip can check dynamic Huffman blocks for complete code sets.
43 The exception is that a single code would not be complete (see #4).
44 8. The five bits following the block type is really the number of
45 literal codes sent minus 257.
46 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
47 (1+6+6). Therefore, to output three times the length, you output
48 three codes (1+1+1), whereas to output four times the same length,
49 you only need two codes (1+3). Hmm.
50 10. In the tree reconstruction algorithm, Code = Code + Increment
51 only if BitLength(i) is not zero. (Pretty obvious.)
52 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
53 12. Note: length code 284 can represent 227-258, but length code 285
54 really is 258. The last length deserves its own, short code
55 since it gets used a lot in very redundant files. The length
56 258 is special since 258 - 3 (the min match length) is 255.
57 13. The literal/length and distance code bit lengths are read as a
58 single stream of lengths. It is possible (and advantageous) for
59 a repeat code (16, 17, or 18) to go across the boundary between
60 the two sets of lengths.
61 */
62
63struct inflate_blocks_state *inflate_blocks_new(z,wsize)
64z_stream *z;
65uInt wsize;
66{
67 struct inflate_blocks_state *s;
68
69 if ((s = (struct inflate_blocks_state *)ZALLOC
70 (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
71 return s;
72 if ((s->window = (Byte *)ZALLOC(z,1,wsize)) == Z_NULL)
73 {
74 ZFREE(z, s);
75 return Z_NULL;
76 }
77 s->mode = TYPE;
78 s->bitk = 0;
79 s->read = s->write = s->window;
80 s->end = s->window + wsize;
81 s->check = 1;
82 return s;
83}
84
85
86int inflate_blocks(s, z, r)
87struct inflate_blocks_state *s;
88z_stream *z;
89int r;
90{
91 uInt t; /* temporary storage */
92 uLong b; /* bit buffer */
93 uInt k; /* bits in bit buffer */
94 Byte *p; /* input data pointer */
95 uInt n; /* bytes available there */
96 Byte *q; /* output window write pointer */
97 uInt m; /* bytes to end of window or read pointer */
98
99 /* copy input/output information to locals (UPDATE macro restores) */
100 LOAD
101
102 /* process input based on current state */
103 while (1) switch (s->mode)
104 {
105 case TYPE:
106 NEEDBITS(3)
107 t = (uInt)b & 7;
108 s->last = t & 1;
109 switch (t >> 1)
110 {
111 case 0: /* stored */
112 DUMPBITS(3)
113 t = k & 7; /* go to byte boundary */
114 DUMPBITS(t)
115 s->mode = LENS; /* get length of stored block */
116 break;
117 case 1: /* fixed */
118 {
119 uInt bl, bd;
120 inflate_huft *tl, *td;
121
122 inflate_trees_fixed(&bl, &bd, &tl, &td);
123 s->sub.codes = inflate_codes_new(bl, bd, tl, td, z);
124 if (s->sub.codes == Z_NULL)
125 {
126 r = Z_MEM_ERROR;
127 LEAVE
128 }
129 }
130 DUMPBITS(3)
131 s->mode = CODES;
132 break;
133 case 2: /* dynamic */
134 DUMPBITS(3)
135 s->mode = TABLE;
136 break;
137 case 3: /* illegal */
138 DUMPBITS(3)
139 s->mode = ERROR;
140 z->msg = "invalid block type";
141 r = Z_DATA_ERROR;
142 LEAVE
143 }
144 break;
145 case LENS:
146 NEEDBITS(32)
147 if ((~b) >> 16 != (b & 0xffff))
148 {
149 s->mode = ERROR;
150 z->msg = "invalid stored block lengths";
151 r = Z_DATA_ERROR;
152 LEAVE
153 }
154 k = 0; /* dump bits */
155 s->sub.left = (uInt)b & 0xffff;
156 s->mode = s->sub.left ? STORED : TYPE;
157 break;
158 case STORED:
159 do {
160 NEEDBYTE
161 NEEDOUT
162 OUTBYTE(NEXTBYTE)
163 } while (--s->sub.left);
164 s->mode = s->last ? DRY : TYPE;
165 break;
166 case TABLE:
167 NEEDBITS(14)
168 s->sub.trees.table = t = (uInt)b & 0x3fff;
169#ifndef PKZIP_BUG_WORKAROUND
170 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
171 {
172 s->mode = ERROR;
173 z->msg = "too many length or distance symbols";
174 r = Z_DATA_ERROR;
175 LEAVE
176 }
177#endif
178 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
179 if (t < 19)
180 t = 19;
181 if ((s->sub.trees.blens = (uInt*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
182 {
183 r = Z_MEM_ERROR;
184 LEAVE
185 }
186 DUMPBITS(14)
187 s->sub.trees.index = 0;
188 s->mode = BTREE;
189 case BTREE:
190 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
191 {
192 NEEDBITS(3)
193 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
194 DUMPBITS(3)
195 }
196 while (s->sub.trees.index < 19)
197 s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
198 s->sub.trees.bb = 7;
199 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
200 &s->sub.trees.tb, z);
201 if (t != Z_OK)
202 {
203 r = t;
204 if (r == Z_DATA_ERROR)
205 s->mode = ERROR;
206 LEAVE
207 }
208 s->sub.trees.index = 0;
209 s->mode = DTREE;
210 case DTREE:
211 while (t = s->sub.trees.table,
212 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
213 {
214 inflate_huft *h;
215 uInt i, j, c;
216
217 t = s->sub.trees.bb;
218 NEEDBITS(t)
219 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
220 t = h->word.what.Bits;
221 c = h->more.Base;
222 if (c < 16)
223 {
224 DUMPBITS(t)
225 s->sub.trees.blens[s->sub.trees.index++] = c;
226 }
227 else /* c == 16..18 */
228 {
229 i = c == 18 ? 7 : c - 14;
230 j = c == 18 ? 11 : 3;
231 NEEDBITS(t + i)
232 DUMPBITS(t)
233 j += (uInt)b & inflate_mask[i];
234 DUMPBITS(i)
235 i = s->sub.trees.index;
236 t = s->sub.trees.table;
237 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
238 (c == 16 && i < 1))
239 {
240 s->mode = ERROR;
241 z->msg = "invalid bit length repeat";
242 r = Z_DATA_ERROR;
243 LEAVE
244 }
245 c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
246 do {
247 s->sub.trees.blens[i++] = c;
248 } while (--j);
249 s->sub.trees.index = i;
250 }
251 }
252 inflate_trees_free(s->sub.trees.tb, z);
253 s->sub.trees.tb = Z_NULL;
254 {
255 uInt bl, bd;
256 inflate_huft *tl, *td;
257 struct inflate_codes_state *c;
258
259 bl = 9;
260 bd = 6;
261 t = s->sub.trees.table;
262 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
263 s->sub.trees.blens, &bl, &bd, &tl, &td, z);
264 if (t != Z_OK)
265 {
266 if (t == (uInt)Z_DATA_ERROR)
267 s->mode = ERROR;
268 r = t;
269 LEAVE
270 }
271 if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
272 {
273 inflate_trees_free(td, z);
274 inflate_trees_free(tl, z);
275 r = Z_MEM_ERROR;
276 LEAVE
277 }
278 ZFREE(z, s->sub.trees.blens);
279 s->sub.codes = c;
280 }
281 s->mode = CODES;
282 case CODES:
283 UPDATE
284 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
285 return inflate_flush(s, z, r);
286 r = Z_OK;
287 inflate_codes_free(s->sub.codes, z);
288 LOAD
289 s->mode = s->last ? DRY : TYPE;
290 break;
291 case DRY:
292 FLUSH
293 if (s->read != s->write)
294 LEAVE
295 s->mode = DONE;
296 case DONE:
297 r = Z_STREAM_END;
298 LEAVE
299 case ERROR:
300 r = Z_DATA_ERROR;
301 LEAVE
302 default:
303 r = Z_STREAM_ERROR;
304 LEAVE
305 }
306}
307
308
309int inflate_blocks_free(s, z, c, e)
310struct inflate_blocks_state *s;
311z_stream *z;
312uLong *c;
313int *e;
314{
315 *e = s->bitk > 7 ? (s->bitb >> (s->bitk & 7)) & 0xff : -1;
316 *c = s->check;
317 if (s->mode == BTREE || s->mode == DTREE)
318 ZFREE(z, s->sub.trees.blens);
319 if (s->mode == CODES)
320 inflate_codes_free(s->sub.codes, z);
321 ZFREE(z, s->window);
322 ZFREE(z, s);
323 return Z_OK;
324}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-15 23:19:04 +0000