linux/lib/zlib_inflate/inffast.c
<<
>>
Prefs
   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 <linux/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 */
  24union uu {
  25        unsigned short us;
  26        unsigned char b[2];
  27};
  28
  29/* Endian independed version */
  30static inline unsigned short
  31get_unaligned16(const unsigned short *p)
  32{
  33        union uu  mm;
  34        unsigned char *b = (unsigned char *)p;
  35
  36        mm.b[0] = b[0];
  37        mm.b[1] = b[1];
  38        return mm.us;
  39}
  40
  41#ifdef POSTINC
  42#  define OFF 0
  43#  define PUP(a) *(a)++
  44#  define UP_UNALIGNED(a) get_unaligned16((a)++)
  45#else
  46#  define OFF 1
  47#  define PUP(a) *++(a)
  48#  define UP_UNALIGNED(a) get_unaligned16(++(a))
  49#endif
  50
  51/*
  52   Decode literal, length, and distance codes and write out the resulting
  53   literal and match bytes until either not enough input or output is
  54   available, an end-of-block is encountered, or a data error is encountered.
  55   When large enough input and output buffers are supplied to inflate(), for
  56   example, a 16K input buffer and a 64K output buffer, more than 95% of the
  57   inflate execution time is spent in this routine.
  58
  59   Entry assumptions:
  60
  61        state->mode == LEN
  62        strm->avail_in >= 6
  63        strm->avail_out >= 258
  64        start >= strm->avail_out
  65        state->bits < 8
  66
  67   On return, state->mode is one of:
  68
  69        LEN -- ran out of enough output space or enough available input
  70        TYPE -- reached end of block code, inflate() to interpret next block
  71        BAD -- error in block data
  72
  73   Notes:
  74
  75    - The maximum input bits used by a length/distance pair is 15 bits for the
  76      length code, 5 bits for the length extra, 15 bits for the distance code,
  77      and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
  78      Therefore if strm->avail_in >= 6, then there is enough input to avoid
  79      checking for available input while decoding.
  80
  81    - The maximum bytes that a single length/distance pair can output is 258
  82      bytes, which is the maximum length that can be coded.  inflate_fast()
  83      requires strm->avail_out >= 258 for each loop to avoid checking for
  84      output space.
  85
  86    - @start:   inflate()'s starting value for strm->avail_out
  87 */
  88void inflate_fast(z_streamp strm, unsigned start)
  89{
  90    struct inflate_state *state;
  91    const unsigned char *in;    /* local strm->next_in */
  92    const unsigned char *last;  /* while in < last, enough input available */
  93    unsigned char *out;         /* local strm->next_out */
  94    unsigned char *beg;         /* inflate()'s initial strm->next_out */
  95    unsigned char *end;         /* while out < end, enough space available */
  96#ifdef INFLATE_STRICT
  97    unsigned dmax;              /* maximum distance from zlib header */
  98#endif
  99    unsigned wsize;             /* window size or zero if not using window */
 100    unsigned whave;             /* valid bytes in the window */
 101    unsigned write;             /* window write index */
 102    unsigned char *window;      /* allocated sliding window, if wsize != 0 */
 103    unsigned long hold;         /* local strm->hold */
 104    unsigned bits;              /* local strm->bits */
 105    code const *lcode;          /* local strm->lencode */
 106    code const *dcode;          /* local strm->distcode */
 107    unsigned lmask;             /* mask for first level of length codes */
 108    unsigned dmask;             /* mask for first level of distance codes */
 109    code this;                  /* retrieved table entry */
 110    unsigned op;                /* code bits, operation, extra bits, or */
 111                                /*  window position, window bytes to copy */
 112    unsigned len;               /* match length, unused bytes */
 113    unsigned dist;              /* match distance */
 114    unsigned char *from;        /* where to copy match from */
 115
 116    /* copy state to local variables */
 117    state = (struct inflate_state *)strm->state;
 118    in = strm->next_in - OFF;
 119    last = in + (strm->avail_in - 5);
 120    out = strm->next_out - OFF;
 121    beg = out - (start - strm->avail_out);
 122    end = out + (strm->avail_out - 257);
 123#ifdef INFLATE_STRICT
 124    dmax = state->dmax;
 125#endif
 126    wsize = state->wsize;
 127    whave = state->whave;
 128    write = state->write;
 129    window = state->window;
 130    hold = state->hold;
 131    bits = state->bits;
 132    lcode = state->lencode;
 133    dcode = state->distcode;
 134    lmask = (1U << state->lenbits) - 1;
 135    dmask = (1U << state->distbits) - 1;
 136
 137    /* decode literals and length/distances until end-of-block or not enough
 138       input data or output space */
 139    do {
 140        if (bits < 15) {
 141            hold += (unsigned long)(PUP(in)) << bits;
 142            bits += 8;
 143            hold += (unsigned long)(PUP(in)) << bits;
 144            bits += 8;
 145        }
 146        this = lcode[hold & lmask];
 147      dolen:
 148        op = (unsigned)(this.bits);
 149        hold >>= op;
 150        bits -= op;
 151        op = (unsigned)(this.op);
 152        if (op == 0) {                          /* literal */
 153            PUP(out) = (unsigned char)(this.val);
 154        }
 155        else if (op & 16) {                     /* length base */
 156            len = (unsigned)(this.val);
 157            op &= 15;                           /* number of extra bits */
 158            if (op) {
 159                if (bits < op) {
 160                    hold += (unsigned long)(PUP(in)) << bits;
 161                    bits += 8;
 162                }
 163                len += (unsigned)hold & ((1U << op) - 1);
 164                hold >>= op;
 165                bits -= op;
 166            }
 167            if (bits < 15) {
 168                hold += (unsigned long)(PUP(in)) << bits;
 169                bits += 8;
 170                hold += (unsigned long)(PUP(in)) << bits;
 171                bits += 8;
 172            }
 173            this = dcode[hold & dmask];
 174          dodist:
 175            op = (unsigned)(this.bits);
 176            hold >>= op;
 177            bits -= op;
 178            op = (unsigned)(this.op);
 179            if (op & 16) {                      /* distance base */
 180                dist = (unsigned)(this.val);
 181                op &= 15;                       /* number of extra bits */
 182                if (bits < op) {
 183                    hold += (unsigned long)(PUP(in)) << bits;
 184                    bits += 8;
 185                    if (bits < op) {
 186                        hold += (unsigned long)(PUP(in)) << bits;
 187                        bits += 8;
 188                    }
 189                }
 190                dist += (unsigned)hold & ((1U << op) - 1);
 191#ifdef INFLATE_STRICT
 192                if (dist > dmax) {
 193                    strm->msg = (char *)"invalid distance too far back";
 194                    state->mode = BAD;
 195                    break;
 196                }
 197#endif
 198                hold >>= op;
 199                bits -= op;
 200                op = (unsigned)(out - beg);     /* max distance in output */
 201                if (dist > op) {                /* see if copy from window */
 202                    op = dist - op;             /* distance back in window */
 203                    if (op > whave) {
 204                        strm->msg = (char *)"invalid distance too far back";
 205                        state->mode = BAD;
 206                        break;
 207                    }
 208                    from = window - OFF;
 209                    if (write == 0) {           /* very common case */
 210                        from += wsize - op;
 211                        if (op < len) {         /* some from window */
 212                            len -= op;
 213                            do {
 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                                PUP(out) = PUP(from);
 226                            } while (--op);
 227                            from = window - OFF;
 228                            if (write < len) {  /* some from start of window */
 229                                op = write;
 230                                len -= op;
 231                                do {
 232                                    PUP(out) = PUP(from);
 233                                } while (--op);
 234                                from = out - dist;      /* rest from output */
 235                            }
 236                        }
 237                    }
 238                    else {                      /* contiguous in window */
 239                        from += write - op;
 240                        if (op < len) {         /* some from window */
 241                            len -= op;
 242                            do {
 243                                PUP(out) = PUP(from);
 244                            } while (--op);
 245                            from = out - dist;  /* rest from output */
 246                        }
 247                    }
 248                    while (len > 2) {
 249                        PUP(out) = PUP(from);
 250                        PUP(out) = PUP(from);
 251                        PUP(out) = PUP(from);
 252                        len -= 3;
 253                    }
 254                    if (len) {
 255                        PUP(out) = PUP(from);
 256                        if (len > 1)
 257                            PUP(out) = PUP(from);
 258                    }
 259                }
 260                else {
 261                    unsigned short *sout;
 262                    unsigned long loops;
 263
 264                    from = out - dist;          /* copy direct from output */
 265                    /* minimum length is three */
 266                    /* Align out addr */
 267                    if (!((long)(out - 1 + OFF) & 1)) {
 268                        PUP(out) = PUP(from);
 269                        len--;
 270                    }
 271                    sout = (unsigned short *)(out - OFF);
 272                    if (dist > 2) {
 273                        unsigned short *sfrom;
 274
 275                        sfrom = (unsigned short *)(from - OFF);
 276                        loops = len >> 1;
 277                        do
 278#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
 279                            PUP(sout) = PUP(sfrom);
 280#else
 281                            PUP(sout) = UP_UNALIGNED(sfrom);
 282#endif
 283                        while (--loops);
 284                        out = (unsigned char *)sout + OFF;
 285                        from = (unsigned char *)sfrom + OFF;
 286                    } else { /* dist == 1 or dist == 2 */
 287                        unsigned short pat16;
 288
 289                        pat16 = *(sout-1+OFF);
 290                        if (dist == 1) {
 291                                union uu mm;
 292                                /* copy one char pattern to both bytes */
 293                                mm.us = pat16;
 294                                mm.b[0] = mm.b[1];
 295                                pat16 = mm.us;
 296                        }
 297                        loops = len >> 1;
 298                        do
 299                            PUP(sout) = pat16;
 300                        while (--loops);
 301                        out = (unsigned char *)sout + OFF;
 302                    }
 303                    if (len & 1)
 304                        PUP(out) = PUP(from);
 305                }
 306            }
 307            else if ((op & 64) == 0) {          /* 2nd level distance code */
 308                this = dcode[this.val + (hold & ((1U << op) - 1))];
 309                goto dodist;
 310            }
 311            else {
 312                strm->msg = (char *)"invalid distance code";
 313                state->mode = BAD;
 314                break;
 315            }
 316        }
 317        else if ((op & 64) == 0) {              /* 2nd level length code */
 318            this = lcode[this.val + (hold & ((1U << op) - 1))];
 319            goto dolen;
 320        }
 321        else if (op & 32) {                     /* end-of-block */
 322            state->mode = TYPE;
 323            break;
 324        }
 325        else {
 326            strm->msg = (char *)"invalid literal/length code";
 327            state->mode = BAD;
 328            break;
 329        }
 330    } while (in < last && out < end);
 331
 332    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
 333    len = bits >> 3;
 334    in -= len;
 335    bits -= len << 3;
 336    hold &= (1U << bits) - 1;
 337
 338    /* update state and return */
 339    strm->next_in = in + OFF;
 340    strm->next_out = out + OFF;
 341    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
 342    strm->avail_out = (unsigned)(out < end ?
 343                                 257 + (end - out) : 257 - (out - end));
 344    state->hold = hold;
 345    state->bits = bits;
 346    return;
 347}
 348
 349/*
 350   inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
 351   - Using bit fields for code structure
 352   - Different op definition to avoid & for extra bits (do & for table bits)
 353   - Three separate decoding do-loops for direct, window, and write == 0
 354   - Special case for distance > 1 copies to do overlapped load and store copy
 355   - Explicit branch predictions (based on measured branch probabilities)
 356   - Deferring match copy and interspersed it with decoding subsequent codes
 357   - Swapping literal/length else
 358   - Swapping window/direct else
 359   - Larger unrolled copy loops (three is about right)
 360   - Moving len -= 3 statement into middle of loop
 361 */
 362
 363#endif /* !ASMINF */
 364
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.