+++ /dev/null
-/* inffast.c -- fast decoding\r
- * Copyright (C) 1995-2008, 2010, 2013 Mark Adler\r
- * For conditions of distribution and use, see copyright notice in zlib.h\r
- */\r
-\r
-#include "zutil.h"\r
-#include "inftrees.h"\r
-#include "inflate.h"\r
-#include "inffast.h"\r
-\r
-#ifndef ASMINF\r
-\r
-/* Allow machine dependent optimization for post-increment or pre-increment.\r
- Based on testing to date,\r
- Pre-increment preferred for:\r
- - PowerPC G3 (Adler)\r
- - MIPS R5000 (Randers-Pehrson)\r
- Post-increment preferred for:\r
- - none\r
- No measurable difference:\r
- - Pentium III (Anderson)\r
- - M68060 (Nikl)\r
- */\r
-#ifdef POSTINC\r
-# define OFF 0\r
-# define PUP(a) *(a)++\r
-#else\r
-# define OFF 1\r
-# define PUP(a) *++(a)\r
-#endif\r
-\r
-/*\r
- Decode literal, length, and distance codes and write out the resulting\r
- literal and match bytes until either not enough input or output is\r
- available, an end-of-block is encountered, or a data error is encountered.\r
- When large enough input and output buffers are supplied to inflate(), for\r
- example, a 16K input buffer and a 64K output buffer, more than 95% of the\r
- inflate execution time is spent in this routine.\r
-\r
- Entry assumptions:\r
-\r
- state->mode == LEN\r
- strm->avail_in >= 6\r
- strm->avail_out >= 258\r
- start >= strm->avail_out\r
- state->bits < 8\r
-\r
- On return, state->mode is one of:\r
-\r
- LEN -- ran out of enough output space or enough available input\r
- TYPE -- reached end of block code, inflate() to interpret next block\r
- BAD -- error in block data\r
-\r
- Notes:\r
-\r
- - The maximum input bits used by a length/distance pair is 15 bits for the\r
- length code, 5 bits for the length extra, 15 bits for the distance code,\r
- and 13 bits for the distance extra. This totals 48 bits, or six bytes.\r
- Therefore if strm->avail_in >= 6, then there is enough input to avoid\r
- checking for available input while decoding.\r
-\r
- - The maximum bytes that a single length/distance pair can output is 258\r
- bytes, which is the maximum length that can be coded. inflate_fast()\r
- requires strm->avail_out >= 258 for each loop to avoid checking for\r
- output space.\r
- */\r
-void ZLIB_INTERNAL inflate_fast(strm, start)\r
-z_streamp strm;\r
-unsigned start; /* inflate()'s starting value for strm->avail_out */\r
-{\r
- struct inflate_state FAR *state;\r
- z_const unsigned char FAR *in; /* local strm->next_in */\r
- z_const unsigned char FAR *last; /* have enough input while in < last */\r
- unsigned char FAR *out; /* local strm->next_out */\r
- unsigned char FAR *beg; /* inflate()'s initial strm->next_out */\r
- unsigned char FAR *end; /* while out < end, enough space available */\r
-#ifdef INFLATE_STRICT\r
- unsigned dmax; /* maximum distance from zlib header */\r
-#endif\r
- unsigned wsize; /* window size or zero if not using window */\r
- unsigned whave; /* valid bytes in the window */\r
- unsigned wnext; /* window write index */\r
- unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */\r
- unsigned long hold; /* local strm->hold */\r
- unsigned bits; /* local strm->bits */\r
- code const FAR *lcode; /* local strm->lencode */\r
- code const FAR *dcode; /* local strm->distcode */\r
- unsigned lmask; /* mask for first level of length codes */\r
- unsigned dmask; /* mask for first level of distance codes */\r
- code here; /* retrieved table entry */\r
- unsigned op; /* code bits, operation, extra bits, or */\r
- /* window position, window bytes to copy */\r
- unsigned len; /* match length, unused bytes */\r
- unsigned dist; /* match distance */\r
- unsigned char FAR *from; /* where to copy match from */\r
-\r
- /* copy state to local variables */\r
- state = (struct inflate_state FAR *)strm->state;\r
- in = strm->next_in - OFF;\r
- last = in + (strm->avail_in - 5);\r
- out = strm->next_out - OFF;\r
- beg = out - (start - strm->avail_out);\r
- end = out + (strm->avail_out - 257);\r
-#ifdef INFLATE_STRICT\r
- dmax = state->dmax;\r
-#endif\r
- wsize = state->wsize;\r
- whave = state->whave;\r
- wnext = state->wnext;\r
- window = state->window;\r
- hold = state->hold;\r
- bits = state->bits;\r
- lcode = state->lencode;\r
- dcode = state->distcode;\r
- lmask = (1U << state->lenbits) - 1;\r
- dmask = (1U << state->distbits) - 1;\r
-\r
- /* decode literals and length/distances until end-of-block or not enough\r
- input data or output space */\r
- do {\r
- if (bits < 15) {\r
- hold += (unsigned long)(PUP(in)) << bits;\r
- bits += 8;\r
- hold += (unsigned long)(PUP(in)) << bits;\r
- bits += 8;\r
- }\r
- here = lcode[hold & lmask];\r
- dolen:\r
- op = (unsigned)(here.bits);\r
- hold >>= op;\r
- bits -= op;\r
- op = (unsigned)(here.op);\r
- if (op == 0) { /* literal */\r
- Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?\r
- "inflate: literal '%c'\n" :\r
- "inflate: literal 0x%02x\n", here.val));\r
- PUP(out) = (unsigned char)(here.val);\r
- }\r
- else if (op & 16) { /* length base */\r
- len = (unsigned)(here.val);\r
- op &= 15; /* number of extra bits */\r
- if (op) {\r
- if (bits < op) {\r
- hold += (unsigned long)(PUP(in)) << bits;\r
- bits += 8;\r
- }\r
- len += (unsigned)hold & ((1U << op) - 1);\r
- hold >>= op;\r
- bits -= op;\r
- }\r
- Tracevv((stderr, "inflate: length %u\n", len));\r
- if (bits < 15) {\r
- hold += (unsigned long)(PUP(in)) << bits;\r
- bits += 8;\r
- hold += (unsigned long)(PUP(in)) << bits;\r
- bits += 8;\r
- }\r
- here = dcode[hold & dmask];\r
- dodist:\r
- op = (unsigned)(here.bits);\r
- hold >>= op;\r
- bits -= op;\r
- op = (unsigned)(here.op);\r
- if (op & 16) { /* distance base */\r
- dist = (unsigned)(here.val);\r
- op &= 15; /* number of extra bits */\r
- if (bits < op) {\r
- hold += (unsigned long)(PUP(in)) << bits;\r
- bits += 8;\r
- if (bits < op) {\r
- hold += (unsigned long)(PUP(in)) << bits;\r
- bits += 8;\r
- }\r
- }\r
- dist += (unsigned)hold & ((1U << op) - 1);\r
-#ifdef INFLATE_STRICT\r
- if (dist > dmax) {\r
- strm->msg = (char *)"invalid distance too far back";\r
- state->mode = BAD;\r
- break;\r
- }\r
-#endif\r
- hold >>= op;\r
- bits -= op;\r
- Tracevv((stderr, "inflate: distance %u\n", dist));\r
- op = (unsigned)(out - beg); /* max distance in output */\r
- if (dist > op) { /* see if copy from window */\r
- op = dist - op; /* distance back in window */\r
- if (op > whave) {\r
- if (state->sane) {\r
- strm->msg =\r
- (char *)"invalid distance too far back";\r
- state->mode = BAD;\r
- break;\r
- }\r
-#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR\r
- if (len <= op - whave) {\r
- do {\r
- PUP(out) = 0;\r
- } while (--len);\r
- continue;\r
- }\r
- len -= op - whave;\r
- do {\r
- PUP(out) = 0;\r
- } while (--op > whave);\r
- if (op == 0) {\r
- from = out - dist;\r
- do {\r
- PUP(out) = PUP(from);\r
- } while (--len);\r
- continue;\r
- }\r
-#endif\r
- }\r
- from = window - OFF;\r
- if (wnext == 0) { /* very common case */\r
- from += wsize - op;\r
- if (op < len) { /* some from window */\r
- len -= op;\r
- do {\r
- PUP(out) = PUP(from);\r
- } while (--op);\r
- from = out - dist; /* rest from output */\r
- }\r
- }\r
- else if (wnext < op) { /* wrap around window */\r
- from += wsize + wnext - op;\r
- op -= wnext;\r
- if (op < len) { /* some from end of window */\r
- len -= op;\r
- do {\r
- PUP(out) = PUP(from);\r
- } while (--op);\r
- from = window - OFF;\r
- if (wnext < len) { /* some from start of window */\r
- op = wnext;\r
- len -= op;\r
- do {\r
- PUP(out) = PUP(from);\r
- } while (--op);\r
- from = out - dist; /* rest from output */\r
- }\r
- }\r
- }\r
- else { /* contiguous in window */\r
- from += wnext - op;\r
- if (op < len) { /* some from window */\r
- len -= op;\r
- do {\r
- PUP(out) = PUP(from);\r
- } while (--op);\r
- from = out - dist; /* rest from output */\r
- }\r
- }\r
- while (len > 2) {\r
- PUP(out) = PUP(from);\r
- PUP(out) = PUP(from);\r
- PUP(out) = PUP(from);\r
- len -= 3;\r
- }\r
- if (len) {\r
- PUP(out) = PUP(from);\r
- if (len > 1)\r
- PUP(out) = PUP(from);\r
- }\r
- }\r
- else {\r
- from = out - dist; /* copy direct from output */\r
- do { /* minimum length is three */\r
- PUP(out) = PUP(from);\r
- PUP(out) = PUP(from);\r
- PUP(out) = PUP(from);\r
- len -= 3;\r
- } while (len > 2);\r
- if (len) {\r
- PUP(out) = PUP(from);\r
- if (len > 1)\r
- PUP(out) = PUP(from);\r
- }\r
- }\r
- }\r
- else if ((op & 64) == 0) { /* 2nd level distance code */\r
- here = dcode[here.val + (hold & ((1U << op) - 1))];\r
- goto dodist;\r
- }\r
- else {\r
- strm->msg = (char *)"invalid distance code";\r
- state->mode = BAD;\r
- break;\r
- }\r
- }\r
- else if ((op & 64) == 0) { /* 2nd level length code */\r
- here = lcode[here.val + (hold & ((1U << op) - 1))];\r
- goto dolen;\r
- }\r
- else if (op & 32) { /* end-of-block */\r
- Tracevv((stderr, "inflate: end of block\n"));\r
- state->mode = TYPE;\r
- break;\r
- }\r
- else {\r
- strm->msg = (char *)"invalid literal/length code";\r
- state->mode = BAD;\r
- break;\r
- }\r
- } while (in < last && out < end);\r
-\r
- /* return unused bytes (on entry, bits < 8, so in won't go too far back) */\r
- len = bits >> 3;\r
- in -= len;\r
- bits -= len << 3;\r
- hold &= (1U << bits) - 1;\r
-\r
- /* update state and return */\r
- strm->next_in = in + OFF;\r
- strm->next_out = out + OFF;\r
- strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));\r
- strm->avail_out = (unsigned)(out < end ?\r
- 257 + (end - out) : 257 - (out - end));\r
- state->hold = hold;\r
- state->bits = bits;\r
- return;\r
-}\r
-\r
-/*\r
- inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):\r
- - Using bit fields for code structure\r
- - Different op definition to avoid & for extra bits (do & for table bits)\r
- - Three separate decoding do-loops for direct, window, and wnext == 0\r
- - Special case for distance > 1 copies to do overlapped load and store copy\r
- - Explicit branch predictions (based on measured branch probabilities)\r
- - Deferring match copy and interspersed it with decoding subsequent codes\r
- - Swapping literal/length else\r
- - Swapping window/direct else\r
- - Larger unrolled copy loops (three is about right)\r
- - Moving len -= 3 statement into middle of loop\r
- */\r
-\r
-#endif /* !ASMINF */\r
projects / mirror_edk2.git / blobdiff