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