win32port/zlib/inffast.c

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