| Geant4 Cross Reference |
1 /* inffast.c -- fast decoding 1 /* inffast.c -- fast decoding
2 * Copyright (C) 1995-2017 Mark Adler 2 * Copyright (C) 1995-2017 Mark Adler
3 * For conditions of distribution and use, see 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */ 4 */
5 5
6 #include "zutil.h" 6 #include "zutil.h"
7 #include "inftrees.h" 7 #include "inftrees.h"
8 #include "inflate.h" 8 #include "inflate.h"
9 #include "inffast.h" 9 #include "inffast.h"
10 10
11 #ifdef ASMINF 11 #ifdef ASMINF
12 # pragma message("Assembler code may have bug 12 # pragma message("Assembler code may have bugs -- use at your own risk")
13 #else 13 #else
14 14
15 /* 15 /*
16 Decode literal, length, and distance codes 16 Decode literal, length, and distance codes and write out the resulting
17 literal and match bytes until either not en 17 literal and match bytes until either not enough input or output is
18 available, an end-of-block is encountered, 18 available, an end-of-block is encountered, or a data error is encountered.
19 When large enough input and output buffers 19 When large enough input and output buffers are supplied to inflate(), for
20 example, a 16K input buffer and a 64K outpu 20 example, a 16K input buffer and a 64K output buffer, more than 95% of the
21 inflate execution time is spent in this rou 21 inflate execution time is spent in this routine.
22 22
23 Entry assumptions: 23 Entry assumptions:
24 24
25 state->mode == LEN 25 state->mode == LEN
26 strm->avail_in >= 6 26 strm->avail_in >= 6
27 strm->avail_out >= 258 27 strm->avail_out >= 258
28 start >= strm->avail_out 28 start >= strm->avail_out
29 state->bits < 8 29 state->bits < 8
30 30
31 On return, state->mode is one of: 31 On return, state->mode is one of:
32 32
33 LEN -- ran out of enough output space 33 LEN -- ran out of enough output space or enough available input
34 TYPE -- reached end of block code, inf 34 TYPE -- reached end of block code, inflate() to interpret next block
35 BAD -- error in block data 35 BAD -- error in block data
36 36
37 Notes: 37 Notes:
38 38
39 - The maximum input bits used by a length/ 39 - The maximum input bits used by a length/distance pair is 15 bits for the
40 length code, 5 bits for the length extra 40 length code, 5 bits for the length extra, 15 bits for the distance code,
41 and 13 bits for the distance extra. Thi 41 and 13 bits for the distance extra. This totals 48 bits, or six bytes.
42 Therefore if strm->avail_in >= 6, then t 42 Therefore if strm->avail_in >= 6, then there is enough input to avoid
43 checking for available input while decod 43 checking for available input while decoding.
44 44
45 - The maximum bytes that a single length/d 45 - The maximum bytes that a single length/distance pair can output is 258
46 bytes, which is the maximum length that 46 bytes, which is the maximum length that can be coded. inflate_fast()
47 requires strm->avail_out >= 258 for each 47 requires strm->avail_out >= 258 for each loop to avoid checking for
48 output space. 48 output space.
49 */ 49 */
50 void ZLIB_INTERNAL inflate_fast(strm, start) 50 void ZLIB_INTERNAL inflate_fast(strm, start)
51 z_streamp strm; 51 z_streamp strm;
52 unsigned start; /* inflate()'s startin 52 unsigned start; /* inflate()'s starting value for strm->avail_out */
53 { 53 {
54 struct inflate_state FAR *state; 54 struct inflate_state FAR *state;
55 z_const unsigned char FAR *in; /* loc 55 z_const unsigned char FAR *in; /* local strm->next_in */
56 z_const unsigned char FAR *last; /* hav 56 z_const unsigned char FAR *last; /* have enough input while in < last */
57 unsigned char FAR *out; /* local strm- 57 unsigned char FAR *out; /* local strm->next_out */
58 unsigned char FAR *beg; /* inflate()'s 58 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
59 unsigned char FAR *end; /* while out < 59 unsigned char FAR *end; /* while out < end, enough space available */
60 #ifdef INFLATE_STRICT 60 #ifdef INFLATE_STRICT
61 unsigned dmax; /* maximum dis 61 unsigned dmax; /* maximum distance from zlib header */
62 #endif 62 #endif
63 unsigned wsize; /* window size 63 unsigned wsize; /* window size or zero if not using window */
64 unsigned whave; /* valid bytes 64 unsigned whave; /* valid bytes in the window */
65 unsigned wnext; /* window writ 65 unsigned wnext; /* window write index */
66 unsigned char FAR *window; /* allocated s 66 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
67 unsigned long hold; /* local strm- 67 unsigned long hold; /* local strm->hold */
68 unsigned bits; /* local strm- 68 unsigned bits; /* local strm->bits */
69 code const FAR *lcode; /* local strm- 69 code const FAR *lcode; /* local strm->lencode */
70 code const FAR *dcode; /* local strm- 70 code const FAR *dcode; /* local strm->distcode */
71 unsigned lmask; /* mask for fi 71 unsigned lmask; /* mask for first level of length codes */
72 unsigned dmask; /* mask for fi 72 unsigned dmask; /* mask for first level of distance codes */
73 code const *here; /* retrieved t << 73 code here; /* retrieved table entry */
74 unsigned op; /* code bits, 74 unsigned op; /* code bits, operation, extra bits, or */
75 /* window pos 75 /* window position, window bytes to copy */
76 unsigned len; /* match lengt 76 unsigned len; /* match length, unused bytes */
77 unsigned dist; /* match dista 77 unsigned dist; /* match distance */
78 unsigned char FAR *from; /* where to co 78 unsigned char FAR *from; /* where to copy match from */
79 79
80 /* copy state to local variables */ 80 /* copy state to local variables */
81 state = (struct inflate_state FAR *)strm-> 81 state = (struct inflate_state FAR *)strm->state;
82 in = strm->next_in; 82 in = strm->next_in;
83 last = in + (strm->avail_in - 5); 83 last = in + (strm->avail_in - 5);
84 out = strm->next_out; 84 out = strm->next_out;
85 beg = out - (start - strm->avail_out); 85 beg = out - (start - strm->avail_out);
86 end = out + (strm->avail_out - 257); 86 end = out + (strm->avail_out - 257);
87 #ifdef INFLATE_STRICT 87 #ifdef INFLATE_STRICT
88 dmax = state->dmax; 88 dmax = state->dmax;
89 #endif 89 #endif
90 wsize = state->wsize; 90 wsize = state->wsize;
91 whave = state->whave; 91 whave = state->whave;
92 wnext = state->wnext; 92 wnext = state->wnext;
93 window = state->window; 93 window = state->window;
94 hold = state->hold; 94 hold = state->hold;
95 bits = state->bits; 95 bits = state->bits;
96 lcode = state->lencode; 96 lcode = state->lencode;
97 dcode = state->distcode; 97 dcode = state->distcode;
98 lmask = (1U << state->lenbits) - 1; 98 lmask = (1U << state->lenbits) - 1;
99 dmask = (1U << state->distbits) - 1; 99 dmask = (1U << state->distbits) - 1;
100 100
101 /* decode literals and length/distances un 101 /* decode literals and length/distances until end-of-block or not enough
102 input data or output space */ 102 input data or output space */
103 do { 103 do {
104 if (bits < 15) { 104 if (bits < 15) {
105 hold += (unsigned long)(*in++) << 105 hold += (unsigned long)(*in++) << bits;
106 bits += 8; 106 bits += 8;
107 hold += (unsigned long)(*in++) << 107 hold += (unsigned long)(*in++) << bits;
108 bits += 8; 108 bits += 8;
109 } 109 }
110 here = lcode + (hold & lmask); << 110 here = lcode[hold & lmask];
111 dolen: 111 dolen:
112 op = (unsigned)(here->bits); << 112 op = (unsigned)(here.bits);
113 hold >>= op; 113 hold >>= op;
114 bits -= op; 114 bits -= op;
115 op = (unsigned)(here->op); << 115 op = (unsigned)(here.op);
116 if (op == 0) { 116 if (op == 0) { /* literal */
117 Tracevv((stderr, here->val >= 0x20 << 117 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
118 "inflate: literal 118 "inflate: literal '%c'\n" :
119 "inflate: literal << 119 "inflate: literal 0x%02x\n", here.val));
120 *out++ = (unsigned char)(here->val << 120 *out++ = (unsigned char)(here.val);
121 } 121 }
122 else if (op & 16) { 122 else if (op & 16) { /* length base */
123 len = (unsigned)(here->val); << 123 len = (unsigned)(here.val);
124 op &= 15; 124 op &= 15; /* number of extra bits */
125 if (op) { 125 if (op) {
126 if (bits < op) { 126 if (bits < op) {
127 hold += (unsigned long)(*i 127 hold += (unsigned long)(*in++) << bits;
128 bits += 8; 128 bits += 8;
129 } 129 }
130 len += (unsigned)hold & ((1U < 130 len += (unsigned)hold & ((1U << op) - 1);
131 hold >>= op; 131 hold >>= op;
132 bits -= op; 132 bits -= op;
133 } 133 }
134 Tracevv((stderr, "inflate: 134 Tracevv((stderr, "inflate: length %u\n", len));
135 if (bits < 15) { 135 if (bits < 15) {
136 hold += (unsigned long)(*in++) 136 hold += (unsigned long)(*in++) << bits;
137 bits += 8; 137 bits += 8;
138 hold += (unsigned long)(*in++) 138 hold += (unsigned long)(*in++) << bits;
139 bits += 8; 139 bits += 8;
140 } 140 }
141 here = dcode + (hold & dmask); << 141 here = dcode[hold & dmask];
142 dodist: 142 dodist:
143 op = (unsigned)(here->bits); << 143 op = (unsigned)(here.bits);
144 hold >>= op; 144 hold >>= op;
145 bits -= op; 145 bits -= op;
146 op = (unsigned)(here->op); << 146 op = (unsigned)(here.op);
147 if (op & 16) { 147 if (op & 16) { /* distance base */
148 dist = (unsigned)(here->val); << 148 dist = (unsigned)(here.val);
149 op &= 15; 149 op &= 15; /* number of extra bits */
150 if (bits < op) { 150 if (bits < op) {
151 hold += (unsigned long)(*i 151 hold += (unsigned long)(*in++) << bits;
152 bits += 8; 152 bits += 8;
153 if (bits < op) { 153 if (bits < op) {
154 hold += (unsigned long 154 hold += (unsigned long)(*in++) << bits;
155 bits += 8; 155 bits += 8;
156 } 156 }
157 } 157 }
158 dist += (unsigned)hold & ((1U 158 dist += (unsigned)hold & ((1U << op) - 1);
159 #ifdef INFLATE_STRICT 159 #ifdef INFLATE_STRICT
160 if (dist > dmax) { 160 if (dist > dmax) {
161 strm->msg = (char *)"inval 161 strm->msg = (char *)"invalid distance too far back";
162 state->mode = BAD; 162 state->mode = BAD;
163 break; 163 break;
164 } 164 }
165 #endif 165 #endif
166 hold >>= op; 166 hold >>= op;
167 bits -= op; 167 bits -= op;
168 Tracevv((stderr, "inflate: 168 Tracevv((stderr, "inflate: distance %u\n", dist));
169 op = (unsigned)(out - beg); 169 op = (unsigned)(out - beg); /* max distance in output */
170 if (dist > op) { 170 if (dist > op) { /* see if copy from window */
171 op = dist - op; 171 op = dist - op; /* distance back in window */
172 if (op > whave) { 172 if (op > whave) {
173 if (state->sane) { 173 if (state->sane) {
174 strm->msg = 174 strm->msg =
175 (char *)"inval 175 (char *)"invalid distance too far back";
176 state->mode = BAD; 176 state->mode = BAD;
177 break; 177 break;
178 } 178 }
179 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_A 179 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
180 if (len <= op - whave) 180 if (len <= op - whave) {
181 do { 181 do {
182 *out++ = 0; 182 *out++ = 0;
183 } while (--len); 183 } while (--len);
184 continue; 184 continue;
185 } 185 }
186 len -= op - whave; 186 len -= op - whave;
187 do { 187 do {
188 *out++ = 0; 188 *out++ = 0;
189 } while (--op > whave) 189 } while (--op > whave);
190 if (op == 0) { 190 if (op == 0) {
191 from = out - dist; 191 from = out - dist;
192 do { 192 do {
193 *out++ = *from 193 *out++ = *from++;
194 } while (--len); 194 } while (--len);
195 continue; 195 continue;
196 } 196 }
197 #endif 197 #endif
198 } 198 }
199 from = window; 199 from = window;
200 if (wnext == 0) { 200 if (wnext == 0) { /* very common case */
201 from += wsize - op; 201 from += wsize - op;
202 if (op < len) { 202 if (op < len) { /* some from window */
203 len -= op; 203 len -= op;
204 do { 204 do {
205 *out++ = *from 205 *out++ = *from++;
206 } while (--op); 206 } while (--op);
207 from = out - dist; 207 from = out - dist; /* rest from output */
208 } 208 }
209 } 209 }
210 else if (wnext < op) { 210 else if (wnext < op) { /* wrap around window */
211 from += wsize + wnext 211 from += wsize + wnext - op;
212 op -= wnext; 212 op -= wnext;
213 if (op < len) { 213 if (op < len) { /* some from end of window */
214 len -= op; 214 len -= op;
215 do { 215 do {
216 *out++ = *from 216 *out++ = *from++;
217 } while (--op); 217 } while (--op);
218 from = window; 218 from = window;
219 if (wnext < len) { 219 if (wnext < len) { /* some from start of window */
220 op = wnext; 220 op = wnext;
221 len -= op; 221 len -= op;
222 do { 222 do {
223 *out++ = * 223 *out++ = *from++;
224 } while (--op) 224 } while (--op);
225 from = out - d 225 from = out - dist; /* rest from output */
226 } 226 }
227 } 227 }
228 } 228 }
229 else { 229 else { /* contiguous in window */
230 from += wnext - op; 230 from += wnext - op;
231 if (op < len) { 231 if (op < len) { /* some from window */
232 len -= op; 232 len -= op;
233 do { 233 do {
234 *out++ = *from 234 *out++ = *from++;
235 } while (--op); 235 } while (--op);
236 from = out - dist; 236 from = out - dist; /* rest from output */
237 } 237 }
238 } 238 }
239 while (len > 2) { 239 while (len > 2) {
240 *out++ = *from++; 240 *out++ = *from++;
241 *out++ = *from++; 241 *out++ = *from++;
242 *out++ = *from++; 242 *out++ = *from++;
243 len -= 3; 243 len -= 3;
244 } 244 }
245 if (len) { 245 if (len) {
246 *out++ = *from++; 246 *out++ = *from++;
247 if (len > 1) 247 if (len > 1)
248 *out++ = *from++; 248 *out++ = *from++;
249 } 249 }
250 } 250 }
251 else { 251 else {
252 from = out - dist; 252 from = out - dist; /* copy direct from output */
253 do { 253 do { /* minimum length is three */
254 *out++ = *from++; 254 *out++ = *from++;
255 *out++ = *from++; 255 *out++ = *from++;
256 *out++ = *from++; 256 *out++ = *from++;
257 len -= 3; 257 len -= 3;
258 } while (len > 2); 258 } while (len > 2);
259 if (len) { 259 if (len) {
260 *out++ = *from++; 260 *out++ = *from++;
261 if (len > 1) 261 if (len > 1)
262 *out++ = *from++; 262 *out++ = *from++;
263 } 263 }
264 } 264 }
265 } 265 }
266 else if ((op & 64) == 0) { 266 else if ((op & 64) == 0) { /* 2nd level distance code */
267 here = dcode + here->val + (ho << 267 here = dcode[here.val + (hold & ((1U << op) - 1))];
268 goto dodist; 268 goto dodist;
269 } 269 }
270 else { 270 else {
271 strm->msg = (char *)"invalid d 271 strm->msg = (char *)"invalid distance code";
272 state->mode = BAD; 272 state->mode = BAD;
273 break; 273 break;
274 } 274 }
275 } 275 }
276 else if ((op & 64) == 0) { 276 else if ((op & 64) == 0) { /* 2nd level length code */
277 here = lcode + here->val + (hold & << 277 here = lcode[here.val + (hold & ((1U << op) - 1))];
278 goto dolen; 278 goto dolen;
279 } 279 }
280 else if (op & 32) { 280 else if (op & 32) { /* end-of-block */
281 Tracevv((stderr, "inflate: 281 Tracevv((stderr, "inflate: end of block\n"));
282 state->mode = TYPE; 282 state->mode = TYPE;
283 break; 283 break;
284 } 284 }
285 else { 285 else {
286 strm->msg = (char *)"invalid liter 286 strm->msg = (char *)"invalid literal/length code";
287 state->mode = BAD; 287 state->mode = BAD;
288 break; 288 break;
289 } 289 }
290 } while (in < last && out < end); 290 } while (in < last && out < end);
291 291
292 /* return unused bytes (on entry, bits < 8 292 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
293 len = bits >> 3; 293 len = bits >> 3;
294 in -= len; 294 in -= len;
295 bits -= len << 3; 295 bits -= len << 3;
296 hold &= (1U << bits) - 1; 296 hold &= (1U << bits) - 1;
297 297
298 /* update state and return */ 298 /* update state and return */
299 strm->next_in = in; 299 strm->next_in = in;
300 strm->next_out = out; 300 strm->next_out = out;
301 strm->avail_in = (unsigned)(in < last ? 5 301 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
302 strm->avail_out = (unsigned)(out < end ? 302 strm->avail_out = (unsigned)(out < end ?
303 257 + (end - 303 257 + (end - out) : 257 - (out - end));
304 state->hold = hold; 304 state->hold = hold;
305 state->bits = bits; 305 state->bits = bits;
306 return; 306 return;
307 } 307 }
308 308
309 /* 309 /*
310 inflate_fast() speedups that turned out slo 310 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
311 - Using bit fields for code structure 311 - Using bit fields for code structure
312 - Different op definition to avoid & for ex 312 - Different op definition to avoid & for extra bits (do & for table bits)
313 - Three separate decoding do-loops for dire 313 - Three separate decoding do-loops for direct, window, and wnext == 0
314 - Special case for distance > 1 copies to d 314 - Special case for distance > 1 copies to do overlapped load and store copy
315 - Explicit branch predictions (based on mea 315 - Explicit branch predictions (based on measured branch probabilities)
316 - Deferring match copy and interspersed it 316 - Deferring match copy and interspersed it with decoding subsequent codes
317 - Swapping literal/length else 317 - Swapping literal/length else
318 - Swapping window/direct else 318 - Swapping window/direct else
319 - Larger unrolled copy loops (three is abou 319 - Larger unrolled copy loops (three is about right)
320 - Moving len -= 3 statement into middle of 320 - Moving len -= 3 statement into middle of loop
321 */ 321 */
322 322
323 #endif /* !ASMINF */ 323 #endif /* !ASMINF */
324 324