juce/source/src/io/streams/zlib/inffast.c

   1 /* inffast.c -- 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 void inflate_fast (z_streamp strm, unsigned start)
  68 {
  69     struct inflate_state FAR *state;
  70     unsigned char FAR *in;      /* local strm->next_in */
  71     unsigned char FAR *last;    /* while in < last, enough input available */
  72     unsigned char FAR *out;     /* local strm->next_out */
  73     unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
  74     unsigned char FAR *end;     /* while out < end, enough space available */
  75 #ifdef INFLATE_STRICT
  76     unsigned dmax;              /* maximum distance from zlib header */
  77 #endif
  78     unsigned wsize;             /* window size or zero if not using window */
  79     unsigned whave;             /* valid bytes in the window */
  80     unsigned write;             /* window write index */
  81     unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
  82     unsigned long hold;         /* local strm->hold */
  83     unsigned bits;              /* local strm->bits */
  84     code const FAR *lcode;      /* local strm->lencode */
  85     code const FAR *dcode;      /* local strm->distcode */
  86     unsigned lmask;             /* mask for first level of length codes */
  87     unsigned dmask;             /* mask for first level of distance codes */
  88     code thisx;                  /* retrieved table entry */
  89     unsigned op;                /* code bits, operation, extra bits, or */
  90                                 /*  window position, window bytes to copy */
  91     unsigned len;               /* match length, unused bytes */
  92     unsigned dist;              /* match distance */
  93     unsigned char FAR *from;    /* where to copy match from */
  94
  95     /* copy state to local variables */
  96     state = (struct inflate_state FAR *)strm->state;
  97     in = strm->next_in - OFF;
  98     last = in + (strm->avail_in - 5);
  99     out = strm->next_out - OFF;
 100     beg = out - (start - strm->avail_out);
 101     end = out + (strm->avail_out - 257);
 102 #ifdef INFLATE_STRICT
 103     dmax = state->dmax;
 104 #endif
 105     wsize = state->wsize;
 106     whave = state->whave;
 107     write = state->write;
 108     window = state->window;
 109     hold = state->hold;
 110     bits = state->bits;
 111     lcode = state->lencode;
 112     dcode = state->distcode;
 113     lmask = (1U << state->lenbits) - 1;
 114     dmask = (1U << state->distbits) - 1;
 115
 116     /* decode literals and length/distances until end-of-block or not enough
 117        input data or output space */
 118     do {
 119         if (bits < 15) {
 120             hold += (unsigned long)(PUP(in)) << bits;
 121             bits += 8;
 122             hold += (unsigned long)(PUP(in)) << bits;
 123             bits += 8;
 124         }
 125         thisx = lcode[hold & lmask];
 126       dolen:
 127         op = (unsigned)(thisx.bits);
 128         hold >>= op;
 129         bits -= op;
 130         op = (unsigned)(thisx.op);
 131         if (op == 0) {                          /* literal */
 132             Tracevv((stderr, thisx.val >= 0x20 && thisx.val < 0x7f ?
 133                     "inflate:         literal '%c'\n" :
 134                     "inflate:         literal 0x%02x\n", thisx.val));
 135             PUP(out) = (unsigned char)(thisx.val);
 136         }
 137         else if (op & 16) {                     /* length base */
 138             len = (unsigned)(thisx.val);
 139             op &= 15;                           /* number of extra bits */
 140             if (op) {
 141                 if (bits < op) {
 142                     hold += (unsigned long)(PUP(in)) << bits;
 143                     bits += 8;
 144                 }
 145                 len += (unsigned)hold & ((1U << op) - 1);
 146                 hold >>= op;
 147                 bits -= op;
 148             }
 149             Tracevv((stderr, "inflate:         length %u\n", len));
 150             if (bits < 15) {
 151                 hold += (unsigned long)(PUP(in)) << bits;
 152                 bits += 8;
 153                 hold += (unsigned long)(PUP(in)) << bits;
 154                 bits += 8;
 155             }
 156             thisx = dcode[hold & dmask];
 157           dodist:
 158             op = (unsigned)(thisx.bits);
 159             hold >>= op;
 160             bits -= op;
 161             op = (unsigned)(thisx.op);
 162             if (op & 16) {                      /* distance base */
 163                 dist = (unsigned)(thisx.val);
 164                 op &= 15;                       /* number of extra bits */
 165                 if (bits < op) {
 166                     hold += (unsigned long)(PUP(in)) << bits;
 167                     bits += 8;
 168                     if (bits < op) {
 169                         hold += (unsigned long)(PUP(in)) << bits;
 170                         bits += 8;
 171                     }
 172                 }
 173                 dist += (unsigned)hold & ((1U << op) - 1);
 174 #ifdef INFLATE_STRICT
 175                 if (dist > dmax) {
 176                     strm->msg = (char *)"invalid distance too far back";
 177                     state->mode = BAD;
 178                     break;
 179                 }
 180 #endif
 181                 hold >>= op;
 182                 bits -= op;
 183                 Tracevv((stderr, "inflate:         distance %u\n", dist));
 184                 op = (unsigned)(out - beg);     /* max distance in output */
 185                 if (dist > op) {                /* see if copy from window */
 186                     op = dist - op;             /* distance back in window */
 187                     if (op > whave) {
 188                         strm->msg = (char *)"invalid distance too far back";
 189                         state->mode = BAD;
 190                         break;
 191                     }
 192                     from = window - OFF;
 193                     if (write == 0) {           /* very common case */
 194                         from += wsize - op;
 195                         if (op < len) {         /* some from window */
 196                             len -= op;
 197                             do {
 198                                 PUP(out) = PUP(from);
 199                             } while (--op);
 200                             from = out - dist;  /* rest from output */
 201                         }
 202                     }
 203                     else if (write < op) {      /* wrap around window */
 204                         from += wsize + write - op;
 205                         op -= write;
 206                         if (op < len) {         /* some from end of window */
 207                             len -= op;
 208                             do {
 209                                 PUP(out) = PUP(from);
 210                             } while (--op);
 211                             from = window - OFF;
 212                             if (write < len) {  /* some from start of window */
 213                                 op = write;
 214                                 len -= op;
 215                                 do {
 216                                     PUP(out) = PUP(from);
 217                                 } while (--op);
 218                                 from = out - dist;      /* rest from output */
 219                             }
 220                         }
 221                     }
 222                     else {                      /* contiguous in window */
 223                         from += write - op;
 224                         if (op < len) {         /* some from window */
 225                             len -= op;
 226                             do {
 227                                 PUP(out) = PUP(from);
 228                             } while (--op);
 229                             from = out - dist;  /* rest from output */
 230                         }
 231                     }
 232                     while (len > 2) {
 233                         PUP(out) = PUP(from);
 234                         PUP(out) = PUP(from);
 235                         PUP(out) = PUP(from);
 236                         len -= 3;
 237                     }
 238                     if (len) {
 239                         PUP(out) = PUP(from);
 240                         if (len > 1)
 241                             PUP(out) = PUP(from);
 242                     }
 243                 }
 244                 else {
 245                     from = out - dist;          /* copy direct from output */
 246                     do {                        /* minimum length is three */
 247                         PUP(out) = PUP(from);
 248                         PUP(out) = PUP(from);
 249                         PUP(out) = PUP(from);
 250                         len -= 3;
 251                     } while (len > 2);
 252                     if (len) {
 253                         PUP(out) = PUP(from);
 254                         if (len > 1)
 255                             PUP(out) = PUP(from);
 256                     }
 257                 }
 258             }
 259             else if ((op & 64) == 0) {          /* 2nd level distance code */
 260                 thisx = dcode[thisx.val + (hold & ((1U << op) - 1))];
 261                 goto dodist;
 262             }
 263             else {
 264                 strm->msg = (char *)"invalid distance code";
 265                 state->mode = BAD;
 266                 break;
 267             }
 268         }
 269         else if ((op & 64) == 0) {              /* 2nd level length code */
 270             thisx = lcode[thisx.val + (hold & ((1U << op) - 1))];
 271             goto dolen;
 272         }
 273         else if (op & 32) {                     /* end-of-block */
 274             Tracevv((stderr, "inflate:         end of block\n"));
 275             state->mode = TYPE;
 276             break;
 277         }
 278         else {
 279             strm->msg = (char *)"invalid literal/length code";
 280             state->mode = BAD;
 281             break;
 282         }
 283     } while (in < last && out < end);
 284
 285     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
 286     len = bits >> 3;
 287     in -= len;
 288     bits -= len << 3;
 289     hold &= (1U << bits) - 1;
 290
 291     /* update state and return */
 292     strm->next_in = in + OFF;
 293     strm->next_out = out + OFF;
 294     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
 295     strm->avail_out = (unsigned)(out < end ?
 296                                  257 + (end - out) : 257 - (out - end));
 297     state->hold = hold;
 298     state->bits = bits;
 299     return;
 300 }
 301
 302 /*
 303    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
 304    - Using bit fields for code structure
 305    - Different op definition to avoid & for extra bits (do & for table bits)
 306    - Three separate decoding do-loops for direct, window, and write == 0
 307    - Special case for distance > 1 copies to do overlapped load and store copy
 308    - Explicit branch predictions (based on measured branch probabilities)
 309    - Deferring match copy and interspersed it with decoding subsequent codes
 310    - Swapping literal/length else
 311    - Swapping window/direct else
 312    - Larger unrolled copy loops (three is about right)
 313    - Moving len -= 3 statement into middle of loop
 314  */
 315
 316 #endif /* !ASMINF */