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