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