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