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