varnish-cache/lib/libvgz/inffast.c
1
/* inffast.c -- fast decoding
2
 * Copyright (C) 1995-2017 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
11
#ifdef ASMINF
12
#  pragma message("Assembler code may have bugs -- use at your own risk")
13
#else
14
15
/*
16
   Decode literal, length, and distance codes and write out the resulting
17
   literal and match bytes until either not enough input or output is
18
   available, an end-of-block is encountered, or a data error is encountered.
19
   When large enough input and output buffers are supplied to inflate(), for
20
   example, a 16K input buffer and a 64K output buffer, more than 95% of the
21
   inflate execution time is spent in this routine.
22
23
   Entry assumptions:
24
25
        state->mode == LEN
26
        strm->avail_in >= 6
27
        strm->avail_out >= 258
28
        start >= strm->avail_out
29
        state->bits < 8
30
31
   On return, state->mode is one of:
32
33
        LEN -- ran out of enough output space or enough available input
34
        TYPE -- reached end of block code, inflate() to interpret next block
35
        BAD -- error in block data
36
37
   Notes:
38
39
    - The maximum input bits used by a length/distance pair is 15 bits for the
40
      length code, 5 bits for the length extra, 15 bits for the distance code,
41
      and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
42
      Therefore if strm->avail_in >= 6, then there is enough input to avoid
43
      checking for available input while decoding.
44
45
    - The maximum bytes that a single length/distance pair can output is 258
46
      bytes, which is the maximum length that can be coded.  inflate_fast()
47
      requires strm->avail_out >= 258 for each loop to avoid checking for
48
      output space.
49
 */
50 18930
void ZLIB_INTERNAL inflate_fast(strm, start)
51
z_streamp strm;
52
unsigned start;         /* inflate()'s starting value for strm->avail_out */
53
{
54
    struct inflate_state FAR *state;
55
    z_const unsigned char FAR *in;      /* local strm->next_in */
56
    z_const unsigned char FAR *last;    /* have enough input while in < last */
57
    unsigned char FAR *out;     /* local strm->next_out */
58
    unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
59
    unsigned char FAR *end;     /* while out < end, enough space available */
60
#ifdef INFLATE_STRICT
61
    unsigned dmax;              /* maximum distance from zlib header */
62
#endif
63
    unsigned wsize;             /* window size or zero if not using window */
64
    unsigned whave;             /* valid bytes in the window */
65
    unsigned wnext;             /* window write index */
66
    unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
67
    unsigned long hold;         /* local strm->hold */
68
    unsigned bits;              /* local strm->bits */
69
    code const FAR *lcode;      /* local strm->lencode */
70
    code const FAR *dcode;      /* local strm->distcode */
71
    unsigned lmask;             /* mask for first level of length codes */
72
    unsigned dmask;             /* mask for first level of distance codes */
73
    code here;                  /* retrieved table entry */
74
    unsigned op;                /* code bits, operation, extra bits, or */
75
                                /*  window position, window bytes to copy */
76
    unsigned len;               /* match length, unused bytes */
77
    unsigned dist;              /* match distance */
78
    unsigned char FAR *from;    /* where to copy match from */
79
80
    /* copy state to local variables */
81 18930
    state = (struct inflate_state FAR *)strm->state;
82 18930
    in = strm->next_in;
83 18930
    last = in + (strm->avail_in - 5);
84 18930
    out = strm->next_out;
85 18930
    beg = out - (start - strm->avail_out);
86 18930
    end = out + (strm->avail_out - 257);
87
#ifdef INFLATE_STRICT
88
    dmax = state->dmax;
89
#endif
90 18930
    wsize = state->wsize;
91 18930
    whave = state->whave;
92 18930
    wnext = state->wnext;
93 18930
    window = state->window;
94 18930
    hold = state->hold;
95 18930
    bits = state->bits;
96 18930
    lcode = state->lencode;
97 18930
    dcode = state->distcode;
98 18930
    lmask = (1U << state->lenbits) - 1;
99 18930
    dmask = (1U << state->distbits) - 1;
100
101
    /* decode literals and length/distances until end-of-block or not enough
102
       input data or output space */
103
    do {
104 7426049
        if (bits < 15) {
105 3227160
            hold += (unsigned long)(*in++) << bits;
106 3227160
            bits += 8;
107 3227160
            hold += (unsigned long)(*in++) << bits;
108 3227160
            bits += 8;
109
        }
110 7426049
        here = lcode[hold & lmask];
111
      dolen:
112 7458591
        op = (unsigned)(here.bits);
113 7458591
        hold >>= op;
114 7458591
        bits -= op;
115 7458591
        op = (unsigned)(here.op);
116 7458591
        if (op == 0) {                          /* literal */
117
            Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
118
                    "inflate:         literal '%c'\n" :
119
                    "inflate:         literal 0x%02x\n", here.val));
120 5218464
            *out++ = (unsigned char)(here.val);
121
        }
122 2240127
        else if (op & 16) {                     /* length base */
123 2207384
            len = (unsigned)(here.val);
124 2207384
            op &= 15;                           /* number of extra bits */
125 2207384
            if (op) {
126 649131
                if (bits < op) {
127 0
                    hold += (unsigned long)(*in++) << bits;
128 0
                    bits += 8;
129
                }
130 649131
                len += (unsigned)hold & ((1U << op) - 1);
131 649131
                hold >>= op;
132 649131
                bits -= op;
133
            }
134
            Tracevv((stderr, "inflate:         length %u\n", len));
135 2207384
            if (bits < 15) {
136 741390
                hold += (unsigned long)(*in++) << bits;
137 741390
                bits += 8;
138 741390
                hold += (unsigned long)(*in++) << bits;
139 741390
                bits += 8;
140
            }
141 2207384
            here = dcode[hold & dmask];
142
          dodist:
143 2243562
            op = (unsigned)(here.bits);
144 2243562
            hold >>= op;
145 2243562
            bits -= op;
146 2243562
            op = (unsigned)(here.op);
147 2243562
            if (op & 16) {                      /* distance base */
148 2207384
                dist = (unsigned)(here.val);
149 2207384
                op &= 15;                       /* number of extra bits */
150 2207384
                if (bits < op) {
151 15350
                    hold += (unsigned long)(*in++) << bits;
152 15350
                    bits += 8;
153 15350
                    if (bits < op) {
154 0
                        hold += (unsigned long)(*in++) << bits;
155 0
                        bits += 8;
156
                    }
157
                }
158 2207384
                dist += (unsigned)hold & ((1U << op) - 1);
159
#ifdef INFLATE_STRICT
160
                if (dist > dmax) {
161
                    strm->msg = "invalid distance too far back";
162
                    state->mode = BAD;
163
                    break;
164
                }
165
#endif
166 2207384
                hold >>= op;
167 2207384
                bits -= op;
168
                Tracevv((stderr, "inflate:         distance %u\n", dist));
169 2207384
                op = (unsigned)(out - beg);     /* max distance in output */
170 2207384
                if (dist > op) {                /* see if copy from window */
171 2
                    op = dist - op;             /* distance back in window */
172 2
                    if (op > whave) {
173 2
                        if (state->sane) {
174 2
                            strm->msg =
175
                                "invalid distance too far back";
176 2
                            state->mode = BAD;
177 2
                            break;
178
                        }
179
#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
180
                        if (len <= op - whave) {
181
                            do {
182
                                *out++ = 0;
183
                            } while (--len);
184
                            continue;
185
                        }
186
                        len -= op - whave;
187
                        do {
188
                            *out++ = 0;
189
                        } while (--op > whave);
190
                        if (op == 0) {
191
                            from = out - dist;
192
                            do {
193
                                *out++ = *from++;
194
                            } while (--len);
195
                            continue;
196
                        }
197
#endif
198
                    }
199 0
                    from = window;
200 0
                    if (wnext == 0) {           /* very common case */
201 0
                        from += wsize - op;
202 0
                        if (op < len) {         /* some from window */
203 0
                            len -= op;
204
                            do {
205 0
                                *out++ = *from++;
206 0
                            } while (--op);
207 0
                            from = out - dist;  /* rest from output */
208
                        }
209
                    }
210 0
                    else if (wnext < op) {      /* wrap around window */
211 0
                        from += wsize + wnext - op;
212 0
                        op -= wnext;
213 0
                        if (op < len) {         /* some from end of window */
214 0
                            len -= op;
215
                            do {
216 0
                                *out++ = *from++;
217 0
                            } while (--op);
218 0
                            from = window;
219 0
                            if (wnext < len) {  /* some from start of window */
220 0
                                op = wnext;
221 0
                                len -= op;
222
                                do {
223 0
                                    *out++ = *from++;
224 0
                                } while (--op);
225 0
                                from = out - dist;      /* rest from output */
226
                            }
227
                        }
228
                    }
229
                    else {                      /* contiguous in window */
230 0
                        from += wnext - op;
231 0
                        if (op < len) {         /* some from window */
232 0
                            len -= op;
233
                            do {
234 0
                                *out++ = *from++;
235 0
                            } while (--op);
236 0
                            from = out - dist;  /* rest from output */
237
                        }
238
                    }
239 0
                    while (len > 2) {
240 0
                        *out++ = *from++;
241 0
                        *out++ = *from++;
242 0
                        *out++ = *from++;
243 0
                        len -= 3;
244
                    }
245 0
                    if (len) {
246 0
                        *out++ = *from++;
247 0
                        if (len > 1)
248 0
                            *out++ = *from++;
249
                    }
250
                }
251
                else {
252 2207382
                    from = out - dist;          /* copy direct from output */
253
                    do {                        /* minimum length is three */
254 8703792
                        *out++ = *from++;
255 8703792
                        *out++ = *from++;
256 8703792
                        *out++ = *from++;
257 8703792
                        len -= 3;
258 8703792
                    } while (len > 2);
259 2207382
                    if (len) {
260 1157526
                        *out++ = *from++;
261 1157526
                        if (len > 1)
262 507050
                            *out++ = *from++;
263
                    }
264
                }
265
            }
266 36178
            else if ((op & 64) == 0) {          /* 2nd level distance code */
267 36178
                here = dcode[here.val + (hold & ((1U << op) - 1))];
268 36178
                goto dodist;
269
            }
270
            else {
271 0
                strm->msg = "invalid distance code";
272 0
                state->mode = BAD;
273 0
                break;
274
            }
275
        }
276 32743
        else if ((op & 64) == 0) {              /* 2nd level length code */
277 32542
            here = lcode[here.val + (hold & ((1U << op) - 1))];
278 32542
            goto dolen;
279
        }
280 201
        else if (op & 32) {                     /* end-of-block */
281
            Tracevv((stderr, "inflate:         end of block\n"));
282 201
            state->mode = TYPE;
283 201
            break;
284
        }
285
        else {
286 0
            strm->msg = "invalid literal/length code";
287 0
            state->mode = BAD;
288 0
            break;
289
        }
290 7425846
    } while (in < last && out < end);
291
292
    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
293 18930
    len = bits >> 3;
294 18930
    in -= len;
295 18930
    bits -= len << 3;
296 18930
    hold &= (1U << bits) - 1;
297
298
    /* update state and return */
299 18930
    strm->next_in = in;
300 18930
    strm->next_out = out;
301 18930
    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
302 37860
    strm->avail_out = (unsigned)(out < end ?
303 18930
                                 257 + (end - out) : 257 - (out - end));
304 18930
    state->hold = hold;
305 18930
    state->bits = bits;
306 18930
    return;
307
}
308
309
/*
310
   inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
311
   - Using bit fields for code structure
312
   - Different op definition to avoid & for extra bits (do & for table bits)
313
   - Three separate decoding do-loops for direct, window, and wnext == 0
314
   - Special case for distance > 1 copies to do overlapped load and store copy
315
   - Explicit branch predictions (based on measured branch probabilities)
316
   - Deferring match copy and interspersed it with decoding subsequent codes
317
   - Swapping literal/length else
318
   - Swapping window/direct else
319
   - Larger unrolled copy loops (three is about right)
320
   - Moving len -= 3 statement into middle of loop
321
 */
322
323
#endif /* !ASMINF */