1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/zlib/inffast.c	Thu Sep 08 06:28:38 2011 +0300
     1.3 @@ -0,0 +1,318 @@
     1.4 +/* inffast.c -- fast decoding
     1.5 + * Copyright (C) 1995-2004 Mark Adler
     1.6 + * For conditions of distribution and use, see copyright notice in zlib.h
     1.7 + */
     1.8 +
     1.9 +#include "zutil.h"
    1.10 +#include "inftrees.h"
    1.11 +#include "inflate.h"
    1.12 +#include "inffast.h"
    1.13 +
    1.14 +#ifndef ASMINF
    1.15 +
    1.16 +/* Allow machine dependent optimization for post-increment or pre-increment.
    1.17 +   Based on testing to date,
    1.18 +   Pre-increment preferred for:
    1.19 +   - PowerPC G3 (Adler)
    1.20 +   - MIPS R5000 (Randers-Pehrson)
    1.21 +   Post-increment preferred for:
    1.22 +   - none
    1.23 +   No measurable difference:
    1.24 +   - Pentium III (Anderson)
    1.25 +   - M68060 (Nikl)
    1.26 + */
    1.27 +#ifdef POSTINC
    1.28 +#  define OFF 0
    1.29 +#  define PUP(a) *(a)++
    1.30 +#else
    1.31 +#  define OFF 1
    1.32 +#  define PUP(a) *++(a)
    1.33 +#endif
    1.34 +
    1.35 +/*
    1.36 +   Decode literal, length, and distance codes and write out the resulting
    1.37 +   literal and match bytes until either not enough input or output is
    1.38 +   available, an end-of-block is encountered, or a data error is encountered.
    1.39 +   When large enough input and output buffers are supplied to inflate(), for
    1.40 +   example, a 16K input buffer and a 64K output buffer, more than 95% of the
    1.41 +   inflate execution time is spent in this routine.
    1.42 +
    1.43 +   Entry assumptions:
    1.44 +
    1.45 +        state->mode == LEN
    1.46 +        strm->avail_in >= 6
    1.47 +        strm->avail_out >= 258
    1.48 +        start >= strm->avail_out
    1.49 +        state->bits < 8
    1.50 +
    1.51 +   On return, state->mode is one of:
    1.52 +
    1.53 +        LEN -- ran out of enough output space or enough available input
    1.54 +        TYPE -- reached end of block code, inflate() to interpret next block
    1.55 +        BAD -- error in block data
    1.56 +
    1.57 +   Notes:
    1.58 +
    1.59 +    - The maximum input bits used by a length/distance pair is 15 bits for the
    1.60 +      length code, 5 bits for the length extra, 15 bits for the distance code,
    1.61 +      and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
    1.62 +      Therefore if strm->avail_in >= 6, then there is enough input to avoid
    1.63 +      checking for available input while decoding.
    1.64 +
    1.65 +    - The maximum bytes that a single length/distance pair can output is 258
    1.66 +      bytes, which is the maximum length that can be coded.  inflate_fast()
    1.67 +      requires strm->avail_out >= 258 for each loop to avoid checking for
    1.68 +      output space.
    1.69 + */
    1.70 +void inflate_fast(strm, start)
    1.71 +z_streamp strm;
    1.72 +unsigned start;         /* inflate()'s starting value for strm->avail_out */
    1.73 +{
    1.74 +    struct inflate_state FAR *state;
    1.75 +    unsigned char FAR *in;      /* local strm->next_in */
    1.76 +    unsigned char FAR *last;    /* while in < last, enough input available */
    1.77 +    unsigned char FAR *out;     /* local strm->next_out */
    1.78 +    unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
    1.79 +    unsigned char FAR *end;     /* while out < end, enough space available */
    1.80 +#ifdef INFLATE_STRICT
    1.81 +    unsigned dmax;              /* maximum distance from zlib header */
    1.82 +#endif
    1.83 +    unsigned wsize;             /* window size or zero if not using window */
    1.84 +    unsigned whave;             /* valid bytes in the window */
    1.85 +    unsigned write;             /* window write index */
    1.86 +    unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
    1.87 +    unsigned long hold;         /* local strm->hold */
    1.88 +    unsigned bits;              /* local strm->bits */
    1.89 +    code const FAR *lcode;      /* local strm->lencode */
    1.90 +    code const FAR *dcode;      /* local strm->distcode */
    1.91 +    unsigned lmask;             /* mask for first level of length codes */
    1.92 +    unsigned dmask;             /* mask for first level of distance codes */
    1.93 +    code this;                  /* retrieved table entry */
    1.94 +    unsigned op;                /* code bits, operation, extra bits, or */
    1.95 +                                /*  window position, window bytes to copy */
    1.96 +    unsigned len;               /* match length, unused bytes */
    1.97 +    unsigned dist;              /* match distance */
    1.98 +    unsigned char FAR *from;    /* where to copy match from */
    1.99 +
   1.100 +    /* copy state to local variables */
   1.101 +    state = (struct inflate_state FAR *)strm->state;
   1.102 +    in = strm->next_in - OFF;
   1.103 +    last = in + (strm->avail_in - 5);
   1.104 +    out = strm->next_out - OFF;
   1.105 +    beg = out - (start - strm->avail_out);
   1.106 +    end = out + (strm->avail_out - 257);
   1.107 +#ifdef INFLATE_STRICT
   1.108 +    dmax = state->dmax;
   1.109 +#endif
   1.110 +    wsize = state->wsize;
   1.111 +    whave = state->whave;
   1.112 +    write = state->write;
   1.113 +    window = state->window;
   1.114 +    hold = state->hold;
   1.115 +    bits = state->bits;
   1.116 +    lcode = state->lencode;
   1.117 +    dcode = state->distcode;
   1.118 +    lmask = (1U << state->lenbits) - 1;
   1.119 +    dmask = (1U << state->distbits) - 1;
   1.120 +
   1.121 +    /* decode literals and length/distances until end-of-block or not enough
   1.122 +       input data or output space */
   1.123 +    do {
   1.124 +        if (bits < 15) {
   1.125 +            hold += (unsigned long)(PUP(in)) << bits;
   1.126 +            bits += 8;
   1.127 +            hold += (unsigned long)(PUP(in)) << bits;
   1.128 +            bits += 8;
   1.129 +        }
   1.130 +        this = lcode[hold & lmask];
   1.131 +      dolen:
   1.132 +        op = (unsigned)(this.bits);
   1.133 +        hold >>= op;
   1.134 +        bits -= op;
   1.135 +        op = (unsigned)(this.op);
   1.136 +        if (op == 0) {                          /* literal */
   1.137 +            Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
   1.138 +                    "inflate:         literal '%c'\n" :
   1.139 +                    "inflate:         literal 0x%02x\n", this.val));
   1.140 +            PUP(out) = (unsigned char)(this.val);
   1.141 +        }
   1.142 +        else if (op & 16) {                     /* length base */
   1.143 +            len = (unsigned)(this.val);
   1.144 +            op &= 15;                           /* number of extra bits */
   1.145 +            if (op) {
   1.146 +                if (bits < op) {
   1.147 +                    hold += (unsigned long)(PUP(in)) << bits;
   1.148 +                    bits += 8;
   1.149 +                }
   1.150 +                len += (unsigned)hold & ((1U << op) - 1);
   1.151 +                hold >>= op;
   1.152 +                bits -= op;
   1.153 +            }
   1.154 +            Tracevv((stderr, "inflate:         length %u\n", len));
   1.155 +            if (bits < 15) {
   1.156 +                hold += (unsigned long)(PUP(in)) << bits;
   1.157 +                bits += 8;
   1.158 +                hold += (unsigned long)(PUP(in)) << bits;
   1.159 +                bits += 8;
   1.160 +            }
   1.161 +            this = dcode[hold & dmask];
   1.162 +          dodist:
   1.163 +            op = (unsigned)(this.bits);
   1.164 +            hold >>= op;
   1.165 +            bits -= op;
   1.166 +            op = (unsigned)(this.op);
   1.167 +            if (op & 16) {                      /* distance base */
   1.168 +                dist = (unsigned)(this.val);
   1.169 +                op &= 15;                       /* number of extra bits */
   1.170 +                if (bits < op) {
   1.171 +                    hold += (unsigned long)(PUP(in)) << bits;
   1.172 +                    bits += 8;
   1.173 +                    if (bits < op) {
   1.174 +                        hold += (unsigned long)(PUP(in)) << bits;
   1.175 +                        bits += 8;
   1.176 +                    }
   1.177 +                }
   1.178 +                dist += (unsigned)hold & ((1U << op) - 1);
   1.179 +#ifdef INFLATE_STRICT
   1.180 +                if (dist > dmax) {
   1.181 +                    strm->msg = (char *)"invalid distance too far back";
   1.182 +                    state->mode = BAD;
   1.183 +                    break;
   1.184 +                }
   1.185 +#endif
   1.186 +                hold >>= op;
   1.187 +                bits -= op;
   1.188 +                Tracevv((stderr, "inflate:         distance %u\n", dist));
   1.189 +                op = (unsigned)(out - beg);     /* max distance in output */
   1.190 +                if (dist > op) {                /* see if copy from window */
   1.191 +                    op = dist - op;             /* distance back in window */
   1.192 +                    if (op > whave) {
   1.193 +                        strm->msg = (char *)"invalid distance too far back";
   1.194 +                        state->mode = BAD;
   1.195 +                        break;
   1.196 +                    }
   1.197 +                    from = window - OFF;
   1.198 +                    if (write == 0) {           /* very common case */
   1.199 +                        from += wsize - op;
   1.200 +                        if (op < len) {         /* some from window */
   1.201 +                            len -= op;
   1.202 +                            do {
   1.203 +                                PUP(out) = PUP(from);
   1.204 +                            } while (--op);
   1.205 +                            from = out - dist;  /* rest from output */
   1.206 +                        }
   1.207 +                    }
   1.208 +                    else if (write < op) {      /* wrap around window */
   1.209 +                        from += wsize + write - op;
   1.210 +                        op -= write;
   1.211 +                        if (op < len) {         /* some from end of window */
   1.212 +                            len -= op;
   1.213 +                            do {
   1.214 +                                PUP(out) = PUP(from);
   1.215 +                            } while (--op);
   1.216 +                            from = window - OFF;
   1.217 +                            if (write < len) {  /* some from start of window */
   1.218 +                                op = write;
   1.219 +                                len -= op;
   1.220 +                                do {
   1.221 +                                    PUP(out) = PUP(from);
   1.222 +                                } while (--op);
   1.223 +                                from = out - dist;      /* rest from output */
   1.224 +                            }
   1.225 +                        }
   1.226 +                    }
   1.227 +                    else {                      /* contiguous in window */
   1.228 +                        from += write - op;
   1.229 +                        if (op < len) {         /* some from window */
   1.230 +                            len -= op;
   1.231 +                            do {
   1.232 +                                PUP(out) = PUP(from);
   1.233 +                            } while (--op);
   1.234 +                            from = out - dist;  /* rest from output */
   1.235 +                        }
   1.236 +                    }
   1.237 +                    while (len > 2) {
   1.238 +                        PUP(out) = PUP(from);
   1.239 +                        PUP(out) = PUP(from);
   1.240 +                        PUP(out) = PUP(from);
   1.241 +                        len -= 3;
   1.242 +                    }
   1.243 +                    if (len) {
   1.244 +                        PUP(out) = PUP(from);
   1.245 +                        if (len > 1)
   1.246 +                            PUP(out) = PUP(from);
   1.247 +                    }
   1.248 +                }
   1.249 +                else {
   1.250 +                    from = out - dist;          /* copy direct from output */
   1.251 +                    do {                        /* minimum length is three */
   1.252 +                        PUP(out) = PUP(from);
   1.253 +                        PUP(out) = PUP(from);
   1.254 +                        PUP(out) = PUP(from);
   1.255 +                        len -= 3;
   1.256 +                    } while (len > 2);
   1.257 +                    if (len) {
   1.258 +                        PUP(out) = PUP(from);
   1.259 +                        if (len > 1)
   1.260 +                            PUP(out) = PUP(from);
   1.261 +                    }
   1.262 +                }
   1.263 +            }
   1.264 +            else if ((op & 64) == 0) {          /* 2nd level distance code */
   1.265 +                this = dcode[this.val + (hold & ((1U << op) - 1))];
   1.266 +                goto dodist;
   1.267 +            }
   1.268 +            else {
   1.269 +                strm->msg = (char *)"invalid distance code";
   1.270 +                state->mode = BAD;
   1.271 +                break;
   1.272 +            }
   1.273 +        }
   1.274 +        else if ((op & 64) == 0) {              /* 2nd level length code */
   1.275 +            this = lcode[this.val + (hold & ((1U << op) - 1))];
   1.276 +            goto dolen;
   1.277 +        }
   1.278 +        else if (op & 32) {                     /* end-of-block */
   1.279 +            Tracevv((stderr, "inflate:         end of block\n"));
   1.280 +            state->mode = TYPE;
   1.281 +            break;
   1.282 +        }
   1.283 +        else {
   1.284 +            strm->msg = (char *)"invalid literal/length code";
   1.285 +            state->mode = BAD;
   1.286 +            break;
   1.287 +        }
   1.288 +    } while (in < last && out < end);
   1.289 +
   1.290 +    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
   1.291 +    len = bits >> 3;
   1.292 +    in -= len;
   1.293 +    bits -= len << 3;
   1.294 +    hold &= (1U << bits) - 1;
   1.295 +
   1.296 +    /* update state and return */
   1.297 +    strm->next_in = in + OFF;
   1.298 +    strm->next_out = out + OFF;
   1.299 +    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
   1.300 +    strm->avail_out = (unsigned)(out < end ?
   1.301 +                                 257 + (end - out) : 257 - (out - end));
   1.302 +    state->hold = hold;
   1.303 +    state->bits = bits;
   1.304 +    return;
   1.305 +}
   1.306 +
   1.307 +/*
   1.308 +   inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
   1.309 +   - Using bit fields for code structure
   1.310 +   - Different op definition to avoid & for extra bits (do & for table bits)
   1.311 +   - Three separate decoding do-loops for direct, window, and write == 0
   1.312 +   - Special case for distance > 1 copies to do overlapped load and store copy
   1.313 +   - Explicit branch predictions (based on measured branch probabilities)
   1.314 +   - Deferring match copy and interspersed it with decoding subsequent codes
   1.315 +   - Swapping literal/length else
   1.316 +   - Swapping window/direct else
   1.317 +   - Larger unrolled copy loops (three is about right)
   1.318 +   - Moving len -= 3 statement into middle of loop
   1.319 + */
   1.320 +
   1.321 +#endif /* !ASMINF */