inffast.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    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
    4  */
    5 
    6 #include "zutil.h"
    7 #include "inftrees.h"
    8 #include "inflate.h"
    9 #include "inffast.h"
   10 
   11 #ifdef ASMINF
   12 #  pragma message("Assembler code may have bugs -- use at your own risk")
   13 #else
   14 
   15 /*
   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.
   22 
   23    Entry assumptions:
   24 
   25         state->mode == LEN
   26         strm->avail_in >= 6
   27         strm->avail_out >= 258
   28         start >= strm->avail_out
   29         state->bits < 8
   30 
   31    On return, state->mode is one of:
   32 
   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
   36 
   37    Notes:
   38 
   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.
   44 
   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
   48       output space.
   49  */
   50 void ZLIB_INTERNAL inflate_fast(strm, start)
   51 z_streamp strm;
   52 unsigned start;         /* inflate()'s starting value for strm->avail_out */
   53 {
   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 */
   60 #ifdef INFLATE_STRICT
   61     unsigned dmax;              /* maximum distance from zlib header */
   62 #endif
   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 const *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 */
   79 
   80     /* copy state to local variables */
   81     state = (struct inflate_state FAR *)strm->state;
   82     in = strm->next_in;
   83     last = in + (strm->avail_in - 5);
   84     out = strm->next_out;
   85     beg = out - (start - strm->avail_out);
   86     end = out + (strm->avail_out - 257);
   87 #ifdef INFLATE_STRICT
   88     dmax = state->dmax;
   89 #endif
   90     wsize = state->wsize;
   91     whave = state->whave;
   92     wnext = state->wnext;
   93     window = state->window;
   94     hold = state->hold;
   95     bits = state->bits;
   96     lcode = state->lencode;
   97     dcode = state->distcode;
   98     lmask = (1U << state->lenbits) - 1;
   99     dmask = (1U << state->distbits) - 1;
  100 
  101     /* decode literals and length/distances until end-of-block or not enough
  102        input data or output space */
  103     do {
  104         if (bits < 15) {
  105             hold += (unsigned long)(*in++) << bits;
  106             bits += 8;
  107             hold += (unsigned long)(*in++) << bits;
  108             bits += 8;
  109         }
  110         here = lcode + (hold & lmask);
  111       dolen:
  112         op = (unsigned)(here->bits);
  113         hold >>= op;
  114         bits -= op;
  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);
  121         }
  122         else if (op & 16) {                     /* length base */
  123             len = (unsigned)(here->val);
  124             op &= 15;                           /* number of extra bits */
  125             if (op) {
  126                 if (bits < op) {
  127                     hold += (unsigned long)(*in++) << bits;
  128                     bits += 8;
  129                 }
  130                 len += (unsigned)hold & ((1U << op) - 1);
  131                 hold >>= op;
  132                 bits -= op;
  133             }
  134             Tracevv((stderr, "inflate:         length %u\n", len));
  135             if (bits < 15) {
  136                 hold += (unsigned long)(*in++) << bits;
  137                 bits += 8;
  138                 hold += (unsigned long)(*in++) << bits;
  139                 bits += 8;
  140             }
  141             here = dcode + (hold & dmask);
  142           dodist:
  143             op = (unsigned)(here->bits);
  144             hold >>= op;
  145             bits -= op;
  146             op = (unsigned)(here->op);
  147             if (op & 16) {                      /* distance base */
  148                 dist = (unsigned)(here->val);
  149                 op &= 15;                       /* number of extra bits */
  150                 if (bits < op) {
  151                     hold += (unsigned long)(*in++) << bits;
  152                     bits += 8;
  153                     if (bits < op) {
  154                         hold += (unsigned long)(*in++) << bits;
  155                         bits += 8;
  156                     }
  157                 }
  158                 dist += (unsigned)hold & ((1U << op) - 1);
  159 #ifdef INFLATE_STRICT
  160                 if (dist > dmax) {
  161                     strm->msg = (char *)"invalid distance too far back";
  162                     state->mode = BAD;
  163                     break;
  164                 }
  165 #endif
  166                 hold >>= op;
  167                 bits -= op;
  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 */
  172                     if (op > whave) {
  173                         if (state->sane) {
  174                             strm->msg =
  175                                 (char *)"invalid distance too far back";
  176                             state->mode = BAD;
  177                             break;
  178                         }
  179 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
  180                         if (len <= op - whave) {
  181                             do {
  182                                 *out++ = 0;
  183                             } while (--len);
  184                             continue;
  185                         }
  186                         len -= op - whave;
  187                         do {
  188                             *out++ = 0;
  189                         } while (--op > whave);
  190                         if (op == 0) {
  191                             from = out - dist;
  192                             do {
  193                                 *out++ = *from++;
  194                             } while (--len);
  195                             continue;
  196                         }
  197 #endif
  198                     }
  199                     from = window;
  200                     if (wnext == 0) {           /* very common case */
  201                         from += wsize - op;
  202                         if (op < len) {         /* some from window */
  203                             len -= op;
  204                             do {
  205                                 *out++ = *from++;
  206                             } while (--op);
  207                             from = out - dist;  /* rest from output */
  208                         }
  209                     }
  210                     else if (wnext < op) {      /* wrap around window */
  211                         from += wsize + wnext - op;
  212                         op -= wnext;
  213                         if (op < len) {         /* some from end of window */
  214                             len -= op;
  215                             do {
  216                                 *out++ = *from++;
  217                             } while (--op);
  218                             from = window;
  219                             if (wnext < len) {  /* some from start of window */
  220                                 op = wnext;
  221                                 len -= op;
  222                                 do {
  223                                     *out++ = *from++;
  224                                 } while (--op);
  225                                 from = out - dist;      /* rest from output */
  226                             }
  227                         }
  228                     }
  229                     else {                      /* contiguous in window */
  230                         from += wnext - op;
  231                         if (op < len) {         /* some from window */
  232                             len -= op;
  233                             do {
  234                                 *out++ = *from++;
  235                             } while (--op);
  236                             from = out - dist;  /* rest from output */
  237                         }
  238                     }
  239                     while (len > 2) {
  240                         *out++ = *from++;
  241                         *out++ = *from++;
  242                         *out++ = *from++;
  243                         len -= 3;
  244                     }
  245                     if (len) {
  246                         *out++ = *from++;
  247                         if (len > 1)
  248                             *out++ = *from++;
  249                     }
  250                 }
  251                 else {
  252                     from = out - dist;          /* copy direct from output */
  253                     do {                        /* minimum length is three */
  254                         *out++ = *from++;
  255                         *out++ = *from++;
  256                         *out++ = *from++;
  257                         len -= 3;
  258                     } while (len > 2);
  259                     if (len) {
  260                         *out++ = *from++;
  261                         if (len > 1)
  262                             *out++ = *from++;
  263                     }
  264                 }
  265             }
  266             else if ((op & 64) == 0) {          /* 2nd level distance code */
  267                 here = dcode + here->val + (hold & ((1U << op) - 1));
  268                 goto dodist;
  269             }
  270             else {
  271                 strm->msg = (char *)"invalid distance code";
  272                 state->mode = BAD;
  273                 break;
  274             }
  275         }
  276         else if ((op & 64) == 0) {              /* 2nd level length code */
  277             here = lcode + here->val + (hold & ((1U << op) - 1));
  278             goto dolen;
  279         }
  280         else if (op & 32) {                     /* end-of-block */
  281             Tracevv((stderr, "inflate:         end of block\n"));
  282             state->mode = TYPE;
  283             break;
  284         }
  285         else {
  286             strm->msg = (char *)"invalid literal/length code";
  287             state->mode = BAD;
  288             break;
  289         }
  290     } while (in < last && out < end);
  291 
  292     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
  293     len = bits >> 3;
  294     in -= len;
  295     bits -= len << 3;
  296     hold &= (1U << bits) - 1;
  297 
  298     /* update state and return */
  299     strm->next_in = in;
  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));
  304     state->hold = hold;
  305     state->bits = bits;
  306     return;
  307 }
  308 
  309 /*
  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
  321  */
  322 
  323 #endif /* !ASMINF */
Cache object: 91270bf107dfb3877d2940522e14f08f
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/contrib/zlib/inffast.c

FreeBSD/Linux Kernel Cross Reference
sys/contrib/zlib/inffast.c
