lib/zlib_inflate/inffast.c

0001 /* inffast.c -- fast decoding
0002  * Copyright (C) 1995-2004 Mark Adler
0003  * For conditions of distribution and use, see copyright notice in zlib.h
0004  */
0005
0006 #include <linux/zutil.h>
0007 #include "inftrees.h"
0008 #include "inflate.h"
0009 #include "inffast.h"
0010
0011 #ifndef ASMINF
0012
0013 union uu {
0014     unsigned short us;
0015     unsigned char b[2];
0016 };
0017
0018 /* Endian independent version */
0019 static inline unsigned short
0020 get_unaligned16(const unsigned short *p)
0021 {
0022     union uu  mm;
0023     unsigned char *b = (unsigned char *)p;
0024
0025     mm.b[0] = b[0];
0026     mm.b[1] = b[1];
0027     return mm.us;
0028 }
0029
0030 /*
0031    Decode literal, length, and distance codes and write out the resulting
0032    literal and match bytes until either not enough input or output is
0033    available, an end-of-block is encountered, or a data error is encountered.
0034    When large enough input and output buffers are supplied to inflate(), for
0035    example, a 16K input buffer and a 64K output buffer, more than 95% of the
0036    inflate execution time is spent in this routine.
0037
0038    Entry assumptions:
0039
0040         state->mode == LEN
0041         strm->avail_in >= 6
0042         strm->avail_out >= 258
0043         start >= strm->avail_out
0044         state->bits < 8
0045
0046    On return, state->mode is one of:
0047
0048         LEN -- ran out of enough output space or enough available input
0049         TYPE -- reached end of block code, inflate() to interpret next block
0050         BAD -- error in block data
0051
0052    Notes:
0053
0054     - The maximum input bits used by a length/distance pair is 15 bits for the
0055       length code, 5 bits for the length extra, 15 bits for the distance code,
0056       and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
0057       Therefore if strm->avail_in >= 6, then there is enough input to avoid
0058       checking for available input while decoding.
0059
0060     - The maximum bytes that a single length/distance pair can output is 258
0061       bytes, which is the maximum length that can be coded.  inflate_fast()
0062       requires strm->avail_out >= 258 for each loop to avoid checking for
0063       output space.
0064
0065     - @start:   inflate()'s starting value for strm->avail_out
0066  */
0067 void inflate_fast(z_streamp strm, unsigned start)
0068 {
0069     struct inflate_state *state;
0070     const unsigned char *in;    /* local strm->next_in */
0071     const unsigned char *last;  /* while in < last, enough input available */
0072     unsigned char *out;         /* local strm->next_out */
0073     unsigned char *beg;         /* inflate()'s initial strm->next_out */
0074     unsigned char *end;         /* while out < end, enough space available */
0075 #ifdef INFLATE_STRICT
0076     unsigned dmax;              /* maximum distance from zlib header */
0077 #endif
0078     unsigned wsize;             /* window size or zero if not using window */
0079     unsigned whave;             /* valid bytes in the window */
0080     unsigned write;             /* window write index */
0081     unsigned char *window;      /* allocated sliding window, if wsize != 0 */
0082     unsigned long hold;         /* local strm->hold */
0083     unsigned bits;              /* local strm->bits */
0084     code const *lcode;          /* local strm->lencode */
0085     code const *dcode;          /* local strm->distcode */
0086     unsigned lmask;             /* mask for first level of length codes */
0087     unsigned dmask;             /* mask for first level of distance codes */
0088     code this;                  /* retrieved table entry */
0089     unsigned op;                /* code bits, operation, extra bits, or */
0090                                 /*  window position, window bytes to copy */
0091     unsigned len;               /* match length, unused bytes */
0092     unsigned dist;              /* match distance */
0093     unsigned char *from;        /* where to copy match from */
0094
0095     /* copy state to local variables */
0096     state = (struct inflate_state *)strm->state;
0097     in = strm->next_in;
0098     last = in + (strm->avail_in - 5);
0099     out = strm->next_out;
0100     beg = out - (start - strm->avail_out);
0101     end = out + (strm->avail_out - 257);
0102 #ifdef INFLATE_STRICT
0103     dmax = state->dmax;
0104 #endif
0105     wsize = state->wsize;
0106     whave = state->whave;
0107     write = state->write;
0108     window = state->window;
0109     hold = state->hold;
0110     bits = state->bits;
0111     lcode = state->lencode;
0112     dcode = state->distcode;
0113     lmask = (1U << state->lenbits) - 1;
0114     dmask = (1U << state->distbits) - 1;
0115
0116     /* decode literals and length/distances until end-of-block or not enough
0117        input data or output space */
0118     do {
0119         if (bits < 15) {
0120             hold += (unsigned long)(*in++) << bits;
0121             bits += 8;
0122             hold += (unsigned long)(*in++) << bits;
0123             bits += 8;
0124         }
0125         this = lcode[hold & lmask];
0126       dolen:
0127         op = (unsigned)(this.bits);
0128         hold >>= op;
0129         bits -= op;
0130         op = (unsigned)(this.op);
0131         if (op == 0) {                          /* literal */
0132             *out++ = (unsigned char)(this.val);
0133         }
0134         else if (op & 16) {                     /* length base */
0135             len = (unsigned)(this.val);
0136             op &= 15;                           /* number of extra bits */
0137             if (op) {
0138                 if (bits < op) {
0139                     hold += (unsigned long)(*in++) << bits;
0140                     bits += 8;
0141                 }
0142                 len += (unsigned)hold & ((1U << op) - 1);
0143                 hold >>= op;
0144                 bits -= op;
0145             }
0146             if (bits < 15) {
0147                 hold += (unsigned long)(*in++) << bits;
0148                 bits += 8;
0149                 hold += (unsigned long)(*in++) << bits;
0150                 bits += 8;
0151             }
0152             this = dcode[hold & dmask];
0153           dodist:
0154             op = (unsigned)(this.bits);
0155             hold >>= op;
0156             bits -= op;
0157             op = (unsigned)(this.op);
0158             if (op & 16) {                      /* distance base */
0159                 dist = (unsigned)(this.val);
0160                 op &= 15;                       /* number of extra bits */
0161                 if (bits < op) {
0162                     hold += (unsigned long)(*in++) << bits;
0163                     bits += 8;
0164                     if (bits < op) {
0165                         hold += (unsigned long)(*in++) << bits;
0166                         bits += 8;
0167                     }
0168                 }
0169                 dist += (unsigned)hold & ((1U << op) - 1);
0170 #ifdef INFLATE_STRICT
0171                 if (dist > dmax) {
0172                     strm->msg = (char *)"invalid distance too far back";
0173                     state->mode = BAD;
0174                     break;
0175                 }
0176 #endif
0177                 hold >>= op;
0178                 bits -= op;
0179                 op = (unsigned)(out - beg);     /* max distance in output */
0180                 if (dist > op) {                /* see if copy from window */
0181                     op = dist - op;             /* distance back in window */
0182                     if (op > whave) {
0183                         strm->msg = (char *)"invalid distance too far back";
0184                         state->mode = BAD;
0185                         break;
0186                     }
0187                     from = window;
0188                     if (write == 0) {           /* very common case */
0189                         from += wsize - op;
0190                         if (op < len) {         /* some from window */
0191                             len -= op;
0192                             do {
0193                                 *out++ = *from++;
0194                             } while (--op);
0195                             from = out - dist;  /* rest from output */
0196                         }
0197                     }
0198                     else if (write < op) {      /* wrap around window */
0199                         from += wsize + write - op;
0200                         op -= write;
0201                         if (op < len) {         /* some from end of window */
0202                             len -= op;
0203                             do {
0204                                 *out++ = *from++;
0205                             } while (--op);
0206                             from = window;
0207                             if (write < len) {  /* some from start of window */
0208                                 op = write;
0209                                 len -= op;
0210                                 do {
0211                                     *out++ = *from++;
0212                                 } while (--op);
0213                                 from = out - dist;      /* rest from output */
0214                             }
0215                         }
0216                     }
0217                     else {                      /* contiguous in window */
0218                         from += write - op;
0219                         if (op < len) {         /* some from window */
0220                             len -= op;
0221                             do {
0222                                 *out++ = *from++;
0223                             } while (--op);
0224                             from = out - dist;  /* rest from output */
0225                         }
0226                     }
0227                     while (len > 2) {
0228                         *out++ = *from++;
0229                         *out++ = *from++;
0230                         *out++ = *from++;
0231                         len -= 3;
0232                     }
0233                     if (len) {
0234                         *out++ = *from++;
0235                         if (len > 1)
0236                             *out++ = *from++;
0237                     }
0238                 }
0239                 else {
0240             unsigned short *sout;
0241             unsigned long loops;
0242
0243                     from = out - dist;          /* copy direct from output */
0244             /* minimum length is three */
0245             /* Align out addr */
0246             if (!((long)(out - 1) & 1)) {
0247             *out++ = *from++;
0248             len--;
0249             }
0250             sout = (unsigned short *)(out);
0251             if (dist > 2) {
0252             unsigned short *sfrom;
0253
0254             sfrom = (unsigned short *)(from);
0255             loops = len >> 1;
0256             do {
0257                 if (IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS))
0258                 *sout++ = *sfrom++;
0259                 else
0260                 *sout++ = get_unaligned16(sfrom++);
0261             } while (--loops);
0262             out = (unsigned char *)sout;
0263             from = (unsigned char *)sfrom;
0264             } else { /* dist == 1 or dist == 2 */
0265             unsigned short pat16;
0266
0267             pat16 = *(sout-1);
0268             if (dist == 1) {
0269                 union uu mm;
0270                 /* copy one char pattern to both bytes */
0271                 mm.us = pat16;
0272                 mm.b[0] = mm.b[1];
0273                 pat16 = mm.us;
0274             }
0275             loops = len >> 1;
0276             do
0277                 *sout++ = pat16;
0278             while (--loops);
0279             out = (unsigned char *)sout;
0280             }
0281             if (len & 1)
0282             *out++ = *from++;
0283                 }
0284             }
0285             else if ((op & 64) == 0) {          /* 2nd level distance code */
0286                 this = dcode[this.val + (hold & ((1U << op) - 1))];
0287                 goto dodist;
0288             }
0289             else {
0290                 strm->msg = (char *)"invalid distance code";
0291                 state->mode = BAD;
0292                 break;
0293             }
0294         }
0295         else if ((op & 64) == 0) {              /* 2nd level length code */
0296             this = lcode[this.val + (hold & ((1U << op) - 1))];
0297             goto dolen;
0298         }
0299         else if (op & 32) {                     /* end-of-block */
0300             state->mode = TYPE;
0301             break;
0302         }
0303         else {
0304             strm->msg = (char *)"invalid literal/length code";
0305             state->mode = BAD;
0306             break;
0307         }
0308     } while (in < last && out < end);
0309
0310     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
0311     len = bits >> 3;
0312     in -= len;
0313     bits -= len << 3;
0314     hold &= (1U << bits) - 1;
0315
0316     /* update state and return */
0317     strm->next_in = in;
0318     strm->next_out = out;
0319     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
0320     strm->avail_out = (unsigned)(out < end ?
0321                                  257 + (end - out) : 257 - (out - end));
0322     state->hold = hold;
0323     state->bits = bits;
0324     return;
0325 }
0326
0327 /*
0328    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
0329    - Using bit fields for code structure
0330    - Different op definition to avoid & for extra bits (do & for table bits)
0331    - Three separate decoding do-loops for direct, window, and write == 0
0332    - Special case for distance > 1 copies to do overlapped load and store copy
0333    - Explicit branch predictions (based on measured branch probabilities)
0334    - Deferring match copy and interspersed it with decoding subsequent codes
0335    - Swapping literal/length else
0336    - Swapping window/direct else
0337    - Larger unrolled copy loops (three is about right)
0338    - Moving len -= 3 statement into middle of loop
0339  */
0340
0341 #endif /* !ASMINF */