File Coverage

deps/libgit2/deps/zlib/inffast.c
Criterion Covered Total %
statement 83 144 57.6
branch 30 70 42.8
condition n/a
subroutine n/a
pod n/a
total 113 214 52.8


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