"Fossies" - the Fresh Open Source Software Archive

Member "src/Common/zlib/inffast.c" (10 Oct 2018, 12978 Bytes) of package /windows/misc/VeraCrypt_1.23-Hotfix-2_Source.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "inffast.c" see the Fossies "Dox" file reference documentation.

    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 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 */