apps/plugins/png/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 #include "plugin.h"
  11
  12 #ifndef ASMINF
  13
  14 extern struct inflate_state state;
  15 extern unsigned char *memory_max;
  16
  17 /* Allow machine dependent optimization for post-increment or pre-increment.
  18    Based on testing to date,
  19    Pre-increment preferred for:
  20    - PowerPC G3 (Adler)
  21    - MIPS R5000 (Randers-Pehrson)
  22    Post-increment preferred for:
  23    - none
  24    No measurable difference:
  25    - Pentium III (Anderson)
  26    - M68060 (Nikl)
  27  */
  28 #ifdef POSTINC
  29 #  define OFF 0
  30 #  define PUP(a) *(a)++
  31 #else
  32 #  define OFF 1
  33 #  define PUP(a) *++(a)
  34 #endif
  35
  36 /*
  37    Decode literal, length, and distance codes and write out the resulting
  38    literal and match bytes until either not enough input or output is
  39    available, an end-of-block is encountered, or a data error is encountered.
  40    When large enough input and output buffers are supplied to inflate(), for
  41    example, a 16K input buffer and a 64K output buffer, more than 95% of the
  42    inflate execution time is spent in this routine.
  43
  44    Entry assumptions:
  45
  46         state->mode == LEN
  47         strm->avail_in >= 6
  48         strm->avail_out >= 258
  49         start >= strm->avail_out
  50         state->bits < 8
  51
  52    On return, state->mode is one of:
  53
  54         LEN -- ran out of enough output space or enough available input
  55         TYPE -- reached end of block code, inflate() to interpret next block
  56         BAD -- error in block data
  57
  58    Notes:
  59
  60     - The maximum input bits used by a length/distance pair is 15 bits for the
  61       length code, 5 bits for the length extra, 15 bits for the distance code,
  62       and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
  63       Therefore if strm->avail_in >= 6, then there is enough input to avoid
  64       checking for available input while decoding.
  65
  66     - The maximum bytes that a single length/distance pair can output is 258
  67       bytes, which is the maximum length that can be coded.  inflate_fast()
  68       requires strm->avail_out >= 258 for each loop to avoid checking for
  69       output space.
  70  */
  71 void inflate_fast(strm, start)
  72 z_streamp strm;
  73 unsigned start;         /* inflate()'s starting value for strm->avail_out */
  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     code this;                  /* retrieved table entry */
  95     unsigned op;                /* code bits, operation, extra bits, or */
  96                                 /*  window position, window bytes to copy */
  97     unsigned len;               /* match length, unused bytes */
  98     unsigned dist;              /* match distance */
  99     unsigned char FAR *from;    /* where to copy match from */
 100
 101     /* copy state to local variables */
 102     //state = (struct inflate_state FAR *)strm->state;
 103     in = strm->next_in - OFF;
 104     last = in + (strm->avail_in - 5);
 105     out = strm->next_out - OFF;
 106     beg = out - (start - strm->avail_out);
 107     end = out + (strm->avail_out - 257);
 108 #ifdef INFLATE_STRICT
 109     dmax = state->dmax;
 110 #endif
 111     wsize = state.wsize;
 112     whave = state.whave;
 113     write = state.write;
 114     window = state.window;
 115     hold = state.hold;
 116     bits = state.bits;
 117     lcode = state.lencode;
 118     dcode = state.distcode;
 119     lmask = (1U << state.lenbits) - 1;
 120     dmask = (1U << state.distbits) - 1;
 121
 122     /* decode literals and length/distances until end-of-block or not enough
 123        input data or output space */
 124     do {
 125         if (bits < 15) {
 126             hold += (unsigned long)(PUP(in)) << bits;
 127             bits += 8;
 128             hold += (unsigned long)(PUP(in)) << bits;
 129             bits += 8;
 130         }
 131         this = lcode[hold & lmask];
 132       dolen:
 133         op = (unsigned)(this.bits);
 134         hold >>= op;
 135         bits -= op;
 136         op = (unsigned)(this.op);
 137         if (op == 0) {                          /* literal */
 138             //DEBUGF(this.val >= 0x20 && this.val < 0x7f ?
 139             //        "inflate:         literal '%c'\n" :
 140             //        "inflate:         literal 0x%02x\n", this.val);
 141           if (out >= memory_max) {
 142             strm->msg = (char *)"Out of memory";
 143             state.mode = ZMEM;
 144             break;
 145           }
 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             //DEBUGF("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                 //DEBUGF("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                               if (out >= memory_max) {
 210                                 strm->msg = (char *)"Out of memory";
 211                                 state.mode = ZMEM;
 212                                 break;
 213                               }
 214                               PUP(out) = PUP(from);
 215                             } while (--op);
 216                             from = out - dist;  /* rest from output */
 217                         }
 218                     }
 219                     else if (write < op) {      /* wrap around window */
 220                         from += wsize + write - op;
 221                         op -= write;
 222                         if (op < len) {         /* some from end of window */
 223                             len -= op;
 224                             do {
 225                               if (out >= memory_max) {
 226                                 strm->msg = (char *)"Out of memory";
 227                                 state.mode = ZMEM;
 228                                 break;
 229                               }
 230                               PUP(out) = PUP(from);
 231                             } while (--op);
 232                             from = window - OFF;
 233                             if (write < len) {  /* some from start of window */
 234                                 op = write;
 235                                 len -= op;
 236                                 do {
 237                                   if (out >= memory_max) {
 238                                     strm->msg = (char *)"Out of memory";
 239                                     state.mode = ZMEM;
 240                                     break;
 241                                   }
 242                                   PUP(out) = PUP(from);
 243                                 } while (--op);
 244                                 from = out - dist;      /* rest from output */
 245                             }
 246                         }
 247                     }
 248                     else {                      /* contiguous in window */
 249                         from += write - op;
 250                         if (op < len) {         /* some from window */
 251                             len -= op;
 252                             do {
 253                               if (out >= memory_max) {
 254                                 strm->msg = (char *)"Out of memory";
 255                                 state.mode = ZMEM;
 256                                 break;
 257                               }
 258                               PUP(out) = PUP(from);
 259                             } while (--op);
 260                             from = out - dist;  /* rest from output */
 261                         }
 262                     }
 263                     while (len > 2) {
 264                       if (out >= memory_max-2) {
 265                         strm->msg = (char *)"Out of memory";
 266                         state.mode = ZMEM;
 267                         break;
 268                       }
 269                       PUP(out) = PUP(from);
 270                       PUP(out) = PUP(from);
 271                       PUP(out) = PUP(from);
 272                       len -= 3;
 273                     }
 274                     if (len) {
 275                       if (out >= memory_max) {
 276                         strm->msg = (char *)"Out of memory";
 277                         state.mode = ZMEM;
 278                         break;
 279                       }
 280                         PUP(out) = PUP(from);
 281                         if (len > 1) {
 282                           if (out >= memory_max) {
 283                             strm->msg = (char *)"Out of memory";
 284                             state.mode = ZMEM;
 285                             break;
 286                           }
 287                             PUP(out) = PUP(from);
 288                         }
 289                     }
 290                 }
 291                 else {
 292                     from = out - dist;          /* copy direct from output */
 293                     do {                        /* minimum length is three */
 294                       if (out >= memory_max-2) {
 295                         strm->msg = (char *)"Out of memory";
 296                         state.mode = ZMEM;
 297                         break;
 298                       }
 299                         PUP(out) = PUP(from);
 300                         PUP(out) = PUP(from);
 301                         PUP(out) = PUP(from);
 302                         len -= 3;
 303                     } while (len > 2);
 304                     if (len) {
 305                       if (out >= memory_max) {
 306                         strm->msg = (char *)"Out of memory";
 307                         state.mode = ZMEM;
 308                         break;
 309                       }
 310                         PUP(out) = PUP(from);
 311                         if (len > 1) {
 312                           if (out >= memory_max) {
 313                             strm->msg = (char *)"Out of memory";
 314                             state.mode = ZMEM;
 315                             break;
 316                           }
 317                             PUP(out) = PUP(from);
 318                         }
 319                     }
 320                 }
 321             }
 322             else if ((op & 64) == 0) {          /* 2nd level distance code */
 323                 this = dcode[this.val + (hold & ((1U << op) - 1))];
 324                 goto dodist;
 325             }
 326             else {
 327                 strm->msg = (char *)"invalid distance code";
 328                 state.mode = BAD;
 329                 break;
 330             }
 331         }
 332         else if ((op & 64) == 0) {              /* 2nd level length code */
 333             this = lcode[this.val + (hold & ((1U << op) - 1))];
 334             goto dolen;
 335         }
 336         else if (op & 32) {                     /* end-of-block */
 337           //DEBUGF("inflate:         end of block\n");
 338             state.mode = TYPE;
 339             break;
 340         }
 341         else {
 342             strm->msg = (char *)"invalid literal/length code";
 343             state.mode = BAD;
 344             break;
 345         }
 346     } while (in < last && out < end);
 347
 348     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
 349     len = bits >> 3;
 350     in -= len;
 351     bits -= len << 3;
 352     hold &= (1U << bits) - 1;
 353
 354     /* update state and return */
 355     strm->next_in = in + OFF;
 356     strm->next_out = out + OFF;
 357     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
 358     strm->avail_out = (unsigned)(out < end ?
 359                                  257 + (end - out) : 257 - (out - end));
 360     state.hold = hold;
 361     state.bits = bits;
 362     return;
 363 }
 364
 365 /*
 366    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
 367    - Using bit fields for code structure
 368    - Different op definition to avoid & for extra bits (do & for table bits)
 369    - Three separate decoding do-loops for direct, window, and write == 0
 370    - Special case for distance > 1 copies to do overlapped load and store copy
 371    - Explicit branch predictions (based on measured branch probabilities)
 372    - Deferring match copy and interspersed it with decoding subsequent codes
 373    - Swapping literal/length else
 374    - Swapping window/direct else
 375    - Larger unrolled copy loops (three is about right)
 376    - Moving len -= 3 statement into middle of loop
 377  */
 378
 379 #endif /* !ASMINF */