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 /* U-Boot: we already included these
7 #include "zutil.h"
8 #include "inftrees.h"
9 #include "inflate.h"
10 #include "inffast.h"
11 */
12
13 #ifndef ASMINF
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 */
inflate_fast(strm,start)50 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 state = (struct inflate_state FAR *)strm->state;
82 in = strm->next_in;
83 last = in + (strm->avail_in - 5);
84 if (in > last && strm->avail_in > 5) {
85 /*
86 * overflow detected, limit strm->avail_in to the
87 * max. possible size and recalculate last
88 */
89 strm->avail_in = 0xffffffff - (uintptr_t)in;
90 last = in + (strm->avail_in - 5);
91 }
92 out = strm->next_out;
93 beg = out - (start - strm->avail_out);
94 end = out + (strm->avail_out - 257);
95 #ifdef INFLATE_STRICT
96 dmax = state->dmax;
97 #endif
98 wsize = state->wsize;
99 whave = state->whave;
100 wnext = state->wnext;
101 window = state->window;
102 hold = state->hold;
103 bits = state->bits;
104 lcode = state->lencode;
105 dcode = state->distcode;
106 lmask = (1U << state->lenbits) - 1;
107 dmask = (1U << state->distbits) - 1;
108
109 /* decode literals and length/distances until end-of-block or not enough
110 input data or output space */
111 do {
112 if (bits < 15) {
113 hold += (unsigned long)(*in++) << bits;
114 bits += 8;
115 hold += (unsigned long)(*in++) << bits;
116 bits += 8;
117 }
118 here = lcode[hold & lmask];
119 dolen:
120 op = (unsigned)(here.bits);
121 hold >>= op;
122 bits -= op;
123 op = (unsigned)(here.op);
124 if (op == 0) { /* literal */
125 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
126 "inflate: literal '%c'\n" :
127 "inflate: literal 0x%02x\n", here.val));
128 *out++ = (unsigned char)(here.val);
129 }
130 else if (op & 16) { /* length base */
131 len = (unsigned)(here.val);
132 op &= 15; /* number of extra bits */
133 if (op) {
134 if (bits < op) {
135 hold += (unsigned long)(*in++) << bits;
136 bits += 8;
137 }
138 len += (unsigned)hold & ((1U << op) - 1);
139 hold >>= op;
140 bits -= op;
141 }
142 Tracevv((stderr, "inflate: length %u\n", len));
143 if (bits < 15) {
144 hold += (unsigned long)(*in++) << bits;
145 bits += 8;
146 hold += (unsigned long)(*in++) << bits;
147 bits += 8;
148 }
149 here = dcode[hold & dmask];
150 dodist:
151 op = (unsigned)(here.bits);
152 hold >>= op;
153 bits -= op;
154 op = (unsigned)(here.op);
155 if (op & 16) { /* distance base */
156 dist = (unsigned)(here.val);
157 op &= 15; /* number of extra bits */
158 if (bits < op) {
159 hold += (unsigned long)(*in++) << bits;
160 bits += 8;
161 if (bits < op) {
162 hold += (unsigned long)(*in++) << bits;
163 bits += 8;
164 }
165 }
166 dist += (unsigned)hold & ((1U << op) - 1);
167 #ifdef INFLATE_STRICT
168 if (dist > dmax) {
169 strm->msg = (char *)"invalid distance too far back";
170 state->mode = BAD;
171 break;
172 }
173 #endif
174 hold >>= op;
175 bits -= op;
176 Tracevv((stderr, "inflate: distance %u\n", dist));
177 op = (unsigned)(out - beg); /* max distance in output */
178 if (dist > op) { /* see if copy from window */
179 op = dist - op; /* distance back in window */
180 if (op > whave) {
181 strm->msg =
182 (char *)"invalid distance too far back";
183 state->mode = BAD;
184 break;
185 }
186 from = window;
187 if (wnext == 0) { /* very common case */
188 from += wsize - op;
189 if (op < len) { /* some from window */
190 len -= op;
191 do {
192 *out++ = *from++;
193 } while (--op);
194 from = out - dist; /* rest from output */
195 }
196 }
197 else if (wnext < op) { /* wrap around window */
198 from += wsize + wnext - op;
199 op -= wnext;
200 if (op < len) { /* some from end of window */
201 len -= op;
202 do {
203 *out++ = *from++;
204 } while (--op);
205 from = window;
206 if (wnext < len) { /* some from start of window */
207 op = wnext;
208 len -= op;
209 do {
210 *out++ = *from++;
211 } while (--op);
212 from = out - dist; /* rest from output */
213 }
214 }
215 }
216 else { /* contiguous in window */
217 from += wnext - op;
218 if (op < len) { /* some from window */
219 len -= op;
220 do {
221 *out++ = *from++;
222 } while (--op);
223 from = out - dist; /* rest from output */
224 }
225 }
226 while (len > 2) {
227 *out++ = *from++;
228 *out++ = *from++;
229 *out++ = *from++;
230 len -= 3;
231 }
232 if (len) {
233 *out++ = *from++;
234 if (len > 1)
235 *out++ = *from++;
236 }
237 }
238 else {
239 unsigned short *sout;
240 unsigned long loops;
241
242 from = out - dist; /* copy direct from output */
243 /* minimum length is three */
244 /* Align out addr */
245 if (!((long)(out - 1) & 1)) {
246 *out++ = *from++;
247 len--;
248 }
249 sout = (unsigned short *)out;
250 if (dist > 2 ) {
251 unsigned short *sfrom;
252
253 sfrom = (unsigned short *)from;
254 loops = len >> 1;
255 do
256 *sout++ = get_unaligned(sfrom++);
257 while (--loops);
258 out = (unsigned char *)sout;
259 from = (unsigned char *)sfrom;
260 } else { /* dist == 1 or dist == 2 */
261 unsigned short pat16;
262
263 pat16 = *(sout - 1);
264 if (dist == 1)
265 #if defined(__BIG_ENDIAN)
266 pat16 = (pat16 & 0xff) | ((pat16 & 0xff ) << 8);
267 #elif defined(__LITTLE_ENDIAN)
268 pat16 = (pat16 & 0xff00) | ((pat16 & 0xff00 ) >> 8);
269 #else
270 #error __BIG_ENDIAN nor __LITTLE_ENDIAN is defined
271 #endif
272 loops = len >> 1;
273 do
274 *sout++ = pat16;
275 while (--loops);
276 out = (unsigned char *)sout;
277 }
278 if (len & 1)
279 *out++ = *from++;
280 }
281 }
282 else if ((op & 64) == 0) { /* 2nd level distance code */
283 here = dcode[here.val + (hold & ((1U << op) - 1))];
284 goto dodist;
285 }
286 else {
287 strm->msg = (char *)"invalid distance code";
288 state->mode = BAD;
289 break;
290 }
291 }
292 else if ((op & 64) == 0) { /* 2nd level length code */
293 here = lcode[here.val + (hold & ((1U << op) - 1))];
294 goto dolen;
295 }
296 else if (op & 32) { /* end-of-block */
297 Tracevv((stderr, "inflate: end of block\n"));
298 state->mode = TYPE;
299 break;
300 }
301 else {
302 strm->msg = (char *)"invalid literal/length code";
303 state->mode = BAD;
304 break;
305 }
306 } while (in < last && out < end);
307
308 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
309 len = bits >> 3;
310 in -= len;
311 bits -= len << 3;
312 hold &= (1U << bits) - 1;
313
314 /* update state and return */
315 strm->next_in = in;
316 strm->next_out = out;
317 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
318 strm->avail_out = (unsigned)(out < end ?
319 257 + (end - out) : 257 - (out - end));
320 state->hold = hold;
321 state->bits = bits;
322 return;
323 }
324
325 /*
326 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
327 - Using bit fields for code structure
328 - Different op definition to avoid & for extra bits (do & for table bits)
329 - Three separate decoding do-loops for direct, window, and wnext == 0
330 - Special case for distance > 1 copies to do overlapped load and store copy
331 - Explicit branch predictions (based on measured branch probabilities)
332 - Deferring match copy and interspersed it with decoding subsequent codes
333 - Swapping literal/length else
334 - Swapping window/direct else
335 - Larger unrolled copy loops (three is about right)
336 - Moving len -= 3 statement into middle of loop
337 */
338
339 #endif /* !ASMINF */
340