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

     /*
      * Copyright (c) 2008 Apple Inc. All rights reserved.
      *
      * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
      * 
      * This file contains Original Code and/or Modifications of Original Code
      * as defined in and that are subject to the Apple Public Source License
      * Version 2.0 (the 'License'). You may not use this file except in
      * compliance with the License. The rights granted to you under the License
     * may not be used to create, or enable the creation or redistribution of,
     * unlawful or unlicensed copies of an Apple operating system, or to
     * circumvent, violate, or enable the circumvention or violation of, any
     * terms of an Apple operating system software license agreement.
     * 
     * Please obtain a copy of the License at
     * http://www.opensource.apple.com/apsl/ and read it before using this file.
     * 
     * The Original Code and all software distributed under the License are
     * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
     * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
     * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
     * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
     * Please see the License for the specific language governing rights and
     * limitations under the License.
     * 
     * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
     */
    /* 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 */

Cache object: 7b6485ece545f739174804cf83671a4a