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
12 # pragma message("Assembler code may have bugs -- use at your own risk")
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.
27 strm->avail_out >= 258
28 start >= strm->avail_out
31 On return, state->mode is one of:
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
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.
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
50 void ZLIB_INTERNAL
inflate_fast(strm
, start
)
52 unsigned start
; /* inflate()'s starting value for strm->avail_out */
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 */
61 unsigned dmax
; /* maximum distance from zlib header */
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 */
80 /* copy state to local variables */
81 state
= (struct inflate_state FAR
*)strm
->state
;
83 last
= in
+ (strm
->avail_in
- 5);
85 beg
= out
- (start
- strm
->avail_out
);
86 end
= out
+ (strm
->avail_out
- 257);
93 window
= state
->window
;
96 lcode
= state
->lencode
;
97 dcode
= state
->distcode
;
98 lmask
= (1U << state
->lenbits
) - 1;
99 dmask
= (1U << state
->distbits
) - 1;
101 /* decode literals and length/distances until end-of-block or not enough
102 input data or output space */
105 hold
+= (unsigned long)(*in
++) << bits
;
107 hold
+= (unsigned long)(*in
++) << bits
;
110 here
= lcode
[hold
& lmask
];
112 op
= (unsigned)(here
.bits
);
115 op
= (unsigned)(here
.op
);
116 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 *out
++ = (unsigned char)(here
.val
);
122 else if (op
& 16) { /* length base */
123 len
= (unsigned)(here
.val
);
124 op
&= 15; /* number of extra bits */
127 hold
+= (unsigned long)(*in
++) << bits
;
130 len
+= (unsigned)hold
& ((1U << op
) - 1);
134 Tracevv((stderr
, "inflate: length %u\n", len
));
136 hold
+= (unsigned long)(*in
++) << bits
;
138 hold
+= (unsigned long)(*in
++) << bits
;
141 here
= dcode
[hold
& dmask
];
143 op
= (unsigned)(here
.bits
);
146 op
= (unsigned)(here
.op
);
147 if (op
& 16) { /* distance base */
148 dist
= (unsigned)(here
.val
);
149 op
&= 15; /* number of extra bits */
151 hold
+= (unsigned long)(*in
++) << bits
;
154 hold
+= (unsigned long)(*in
++) << bits
;
158 dist
+= (unsigned)hold
& ((1U << op
) - 1);
159 #ifdef INFLATE_STRICT
161 strm
->msg
= (char *)"invalid distance too far back";
168 Tracevv((stderr
, "inflate: distance %u\n", dist
));
169 op
= (unsigned)(out
- beg
); /* max distance in output */
170 if (dist
> op
) { /* see if copy from window */
171 op
= dist
- op
; /* distance back in window */
175 (char *)"invalid distance too far back";
179 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
180 if (len
<= op
- whave
) {
189 } while (--op
> whave
);
200 if (wnext
== 0) { /* very common case */
202 if (op
< len
) { /* some from window */
207 from
= out
- dist
; /* rest from output */
210 else if (wnext
< op
) { /* wrap around window */
211 from
+= wsize
+ wnext
- op
;
213 if (op
< len
) { /* some from end of window */
219 if (wnext
< len
) { /* some from start of window */
225 from
= out
- dist
; /* rest from output */
229 else { /* contiguous in window */
231 if (op
< len
) { /* some from window */
236 from
= out
- dist
; /* rest from output */
252 from
= out
- dist
; /* copy direct from output */
253 do { /* minimum length is three */
266 else if ((op
& 64) == 0) { /* 2nd level distance code */
267 here
= dcode
[here
.val
+ (hold
& ((1U << op
) - 1))];
271 strm
->msg
= (char *)"invalid distance code";
276 else if ((op
& 64) == 0) { /* 2nd level length code */
277 here
= lcode
[here
.val
+ (hold
& ((1U << op
) - 1))];
280 else if (op
& 32) { /* end-of-block */
281 Tracevv((stderr
, "inflate: end of block\n"));
286 strm
->msg
= (char *)"invalid literal/length code";
290 } while (in
< last
&& out
< end
);
292 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
296 hold
&= (1U << bits
) - 1;
298 /* update state and return */
300 strm
->next_out
= out
;
301 strm
->avail_in
= (unsigned)(in
< last
? 5 + (last
- in
) : 5 - (in
- last
));
302 strm
->avail_out
= (unsigned)(out
< end
?
303 257 + (end
- out
) : 257 - (out
- end
));
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
This page took 0.036305 seconds and 4 git commands to generate.