lib/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 /* U-boot: we already included these
   7 #include "zutil.h"
   8 #include "inftrees.h"
   9 #include "inflate.h"
  10 #include "inffast.h"
  11 */
  12
  13 #ifndef ASMINF
  14
  15 /* Allow machine dependent optimization for post-increment or pre-increment.
  16    Based on testing to date,
  17    Pre-increment preferred for:
  18    - PowerPC G3 (Adler)
  19    - MIPS R5000 (Randers-Pehrson)
  20    Post-increment preferred for:
  21    - none
  22    No measurable difference:
  23    - Pentium III (Anderson)
  24    - M68060 (Nikl)
  25  */
  26 #ifdef POSTINC
  27 #  define OFF 0
  28 #  define PUP(a) *(a)++
  29 #else
  30 #  define OFF 1
  31 #  define PUP(a) *++(a)
  32 #endif
  33
  34 /*
  35    Decode literal, length, and distance codes and write out the resulting
  36    literal and match bytes until either not enough input or output is
  37    available, an end-of-block is encountered, or a data error is encountered.
  38    When large enough input and output buffers are supplied to inflate(), for
  39    example, a 16K input buffer and a 64K output buffer, more than 95% of the
  40    inflate execution time is spent in this routine.
  41
  42    Entry assumptions:
  43
  44         state->mode == LEN
  45         strm->avail_in >= 6
  46         strm->avail_out >= 258
  47         start >= strm->avail_out
  48         state->bits < 8
  49
  50    On return, state->mode is one of:
  51
  52         LEN -- ran out of enough output space or enough available input
  53         TYPE -- reached end of block code, inflate() to interpret next block
  54         BAD -- error in block data
  55
  56    Notes:
  57
  58     - The maximum input bits used by a length/distance pair is 15 bits for the
  59       length code, 5 bits for the length extra, 15 bits for the distance code,
  60       and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
  61       Therefore if strm->avail_in >= 6, then there is enough input to avoid
  62       checking for available input while decoding.
  63
  64     - The maximum bytes that a single length/distance pair can output is 258
  65       bytes, which is the maximum length that can be coded.  inflate_fast()
  66       requires strm->avail_out >= 258 for each loop to avoid checking for
  67       output space.
  68  */
  69 void inflate_fast(z_streamp strm, unsigned start)
  70 /* start: inflate()'s starting value for strm->avail_out */
  71 {
  72     struct inflate_state FAR *state;
  73     unsigned char FAR *in;      /* local strm->next_in */
  74     unsigned char FAR *last;    /* while in < last, enough input available */
  75     unsigned char FAR *out;     /* local strm->next_out */
  76     unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
  77     unsigned char FAR *end;     /* while out < end, enough space available */
  78 #ifdef INFLATE_STRICT
  79     unsigned dmax;              /* maximum distance from zlib header */
  80 #endif
  81     unsigned wsize;             /* window size or zero if not using window */
  82     unsigned whave;             /* valid bytes in the window */
  83     unsigned write;             /* window write index */
  84     unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
  85     unsigned long hold;         /* local strm->hold */
  86     unsigned bits;              /* local strm->bits */
  87     code const FAR *lcode;      /* local strm->lencode */
  88     code const FAR *dcode;      /* local strm->distcode */
  89     unsigned lmask;             /* mask for first level of length codes */
  90     unsigned dmask;             /* mask for first level of distance codes */
  91     code this;                  /* retrieved table entry */
  92     unsigned op;                /* code bits, operation, extra bits, or */
  93                                 /*  window position, window bytes to copy */
  94     unsigned len;               /* match length, unused bytes */
  95     unsigned dist;              /* match distance */
  96     unsigned char FAR *from;    /* where to copy match from */
  97
  98     /* copy state to local variables */
  99     state = (struct inflate_state FAR *)strm->state;
 100     in = strm->next_in - OFF;
 101     last = in + (strm->avail_in - 5);
 102     if (in > last && strm->avail_in > 5) {
 103         /*
 104          * overflow detected, limit strm->avail_in to the
 105          * max. possible size and recalculate last
 106          */
 107         strm->avail_in = 0xffffffff - (uintptr_t)in;
 108         last = in + (strm->avail_in - 5);
 109     }
 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                     unsigned short *sout;
 257                     unsigned long loops;
 258
 259                     from = out - dist;          /* copy direct from output */
 260                     /* minimum length is three */
 261                     /* Align out addr */
 262                     if (!((long)(out - 1 + OFF) & 1)) {
 263                         PUP(out) = PUP(from);
 264                         len--;
 265                     }
 266                     sout = (unsigned short *)(out - OFF);
 267                     if (dist > 2 ) {
 268                         unsigned short *sfrom;
 269
 270                         sfrom = (unsigned short *)(from - OFF);
 271                         loops = len >> 1;
 272                         do
 273                             PUP(sout) = get_unaligned(++sfrom);
 274                         while (--loops);
 275                         out = (unsigned char *)sout + OFF;
 276                         from = (unsigned char *)sfrom + OFF;
 277                     } else { /* dist == 1 or dist == 2 */
 278                         unsigned short pat16;
 279
 280                         pat16 = *(sout-2+2*OFF);
 281                         if (dist == 1)
 282 #if defined(__BIG_ENDIAN)
 283                             pat16 = (pat16 & 0xff) | ((pat16 & 0xff ) << 8);
 284 #elif defined(__LITTLE_ENDIAN)
 285                             pat16 = (pat16 & 0xff00) | ((pat16 & 0xff00 ) >> 8);
 286 #else
 287 #error __BIG_ENDIAN nor __LITTLE_ENDIAN is defined
 288 #endif
 289                         loops = len >> 1;
 290                         do
 291                             PUP(sout) = pat16;
 292                         while (--loops);
 293                         out = (unsigned char *)sout + OFF;
 294                     }
 295                     if (len & 1)
 296                         PUP(out) = PUP(from);
 297                 }
 298             }
 299             else if ((op & 64) == 0) {          /* 2nd level distance code */
 300                 this = dcode[this.val + (hold & ((1U << op) - 1))];
 301                 goto dodist;
 302             }
 303             else {
 304                 strm->msg = (char *)"invalid distance code";
 305                 state->mode = BAD;
 306                 break;
 307             }
 308         }
 309         else if ((op & 64) == 0) {              /* 2nd level length code */
 310             this = lcode[this.val + (hold & ((1U << op) - 1))];
 311             goto dolen;
 312         }
 313         else if (op & 32) {                     /* end-of-block */
 314             Tracevv((stderr, "inflate:         end of block\n"));
 315             state->mode = TYPE;
 316             break;
 317         }
 318         else {
 319             strm->msg = (char *)"invalid literal/length code";
 320             state->mode = BAD;
 321             break;
 322         }
 323     } while (in < last && out < end);
 324
 325     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
 326     len = bits >> 3;
 327     in -= len;
 328     bits -= len << 3;
 329     hold &= (1U << bits) - 1;
 330
 331     /* update state and return */
 332     strm->next_in = in + OFF;
 333     strm->next_out = out + OFF;
 334     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
 335     strm->avail_out = (unsigned)(out < end ?
 336                                  257 + (end - out) : 257 - (out - end));
 337     state->hold = hold;
 338     state->bits = bits;
 339     return;
 340 }
 341
 342 /*
 343    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
 344    - Using bit fields for code structure
 345    - Different op definition to avoid & for extra bits (do & for table bits)
 346    - Three separate decoding do-loops for direct, window, and write == 0
 347    - Special case for distance > 1 copies to do overlapped load and store copy
 348    - Explicit branch predictions (based on measured branch probabilities)
 349    - Deferring match copy and interspersed it with decoding subsequent codes
 350    - Swapping literal/length else
 351    - Swapping window/direct else
 352    - Larger unrolled copy loops (three is about right)
 353    - Moving len -= 3 statement into middle of loop
 354  */
 355
 356 #endif /* !ASMINF */