File Coverage

cpan/Compress-Raw-Zlib/inffast.c
Criterion Covered Total %
statement 125 143 87.4
branch n/a
condition n/a
subroutine n/a
total 125 143 87.4


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 */