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