Coverage Report

Created: 2023-03-02 15:14

/src/zlib/inffast.c
Line
Count
Source (jump to first uncovered line)
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
void ZLIB_INTERNAL inflate_fast(strm, start)
51
z_streamp strm;
52
unsigned start;         /* inflate()'s starting value for strm->avail_out */
53
22.4k
{
54
22.4k
    struct inflate_state FAR *state;
55
22.4k
    z_const unsigned char FAR *in;      /* local strm->next_in */
56
22.4k
    z_const unsigned char FAR *last;    /* have enough input while in < last */
57
22.4k
    unsigned char FAR *out;     /* local strm->next_out */
58
22.4k
    unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
59
22.4k
    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
22.4k
    unsigned wsize;             /* window size or zero if not using window */
64
22.4k
    unsigned whave;             /* valid bytes in the window */
65
22.4k
    unsigned wnext;             /* window write index */
66
22.4k
    unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
67
22.4k
    unsigned long hold;         /* local strm->hold */
68
22.4k
    unsigned bits;              /* local strm->bits */
69
22.4k
    code const FAR *lcode;      /* local strm->lencode */
70
22.4k
    code const FAR *dcode;      /* local strm->distcode */
71
22.4k
    unsigned lmask;             /* mask for first level of length codes */
72
22.4k
    unsigned dmask;             /* mask for first level of distance codes */
73
22.4k
    code const *here;           /* retrieved table entry */
74
22.4k
    unsigned op;                /* code bits, operation, extra bits, or */
75
                                /*  window position, window bytes to copy */
76
22.4k
    unsigned len;               /* match length, unused bytes */
77
22.4k
    unsigned dist;              /* match distance */
78
22.4k
    unsigned char FAR *from;    /* where to copy match from */
79
80
    /* copy state to local variables */
81
22.4k
    state = (struct inflate_state FAR *)strm->state;
82
22.4k
    in = strm->next_in;
83
22.4k
    last = in + (strm->avail_in - 5);
84
22.4k
    out = strm->next_out;
85
22.4k
    beg = out - (start - strm->avail_out);
86
22.4k
    end = out + (strm->avail_out - 257);
87
#ifdef INFLATE_STRICT
88
    dmax = state->dmax;
89
#endif
90
22.4k
    wsize = state->wsize;
91
22.4k
    whave = state->whave;
92
22.4k
    wnext = state->wnext;
93
22.4k
    window = state->window;
94
22.4k
    hold = state->hold;
95
22.4k
    bits = state->bits;
96
22.4k
    lcode = state->lencode;
97
22.4k
    dcode = state->distcode;
98
22.4k
    lmask = (1U << state->lenbits) - 1;
99
22.4k
    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
442k
    do {
104
442k
        if (bits < 15) {
105
234k
            hold += (unsigned long)(*in++) << bits;
106
234k
            bits += 8;
107
234k
            hold += (unsigned long)(*in++) << bits;
108
234k
            bits += 8;
109
234k
        }
110
442k
        here = lcode + (hold & lmask);
111
443k
      dolen:
112
443k
        op = (unsigned)(here->bits);
113
443k
        hold >>= op;
114
443k
        bits -= op;
115
443k
        op = (unsigned)(here->op);
116
443k
        if (op == 0) {                          /* literal */
117
362k
            Tracevv((stderr, here->val >= 0x20 && here->val < 0x7f ?
118
362k
                    "inflate:         literal '%c'\n" :
119
362k
                    "inflate:         literal 0x%02x\n", here->val));
120
362k
            *out++ = (unsigned char)(here->val);
121
362k
        }
122
80.7k
        else if (op & 16) {                     /* length base */
123
65.7k
            len = (unsigned)(here->val);
124
65.7k
            op &= 15;                           /* number of extra bits */
125
65.7k
            if (op) {
126
26.6k
                if (bits < op) {
127
0
                    hold += (unsigned long)(*in++) << bits;
128
0
                    bits += 8;
129
0
                }
130
26.6k
                len += (unsigned)hold & ((1U << op) - 1);
131
26.6k
                hold >>= op;
132
26.6k
                bits -= op;
133
26.6k
            }
134
65.7k
            Tracevv((stderr, "inflate:         length %u\n", len));
135
65.7k
            if (bits < 15) {
136
33.0k
                hold += (unsigned long)(*in++) << bits;
137
33.0k
                bits += 8;
138
33.0k
                hold += (unsigned long)(*in++) << bits;
139
33.0k
                bits += 8;
140
33.0k
            }
141
65.7k
            here = dcode + (hold & dmask);
142
65.7k
          dodist:
143
65.7k
            op = (unsigned)(here->bits);
144
65.7k
            hold >>= op;
145
65.7k
            bits -= op;
146
65.7k
            op = (unsigned)(here->op);
147
65.7k
            if (op & 16) {                      /* distance base */
148
65.6k
                dist = (unsigned)(here->val);
149
65.6k
                op &= 15;                       /* number of extra bits */
150
65.6k
                if (bits < op) {
151
74
                    hold += (unsigned long)(*in++) << bits;
152
74
                    bits += 8;
153
74
                    if (bits < op) {
154
0
                        hold += (unsigned long)(*in++) << bits;
155
0
                        bits += 8;
156
0
                    }
157
74
                }
158
65.6k
                dist += (unsigned)hold & ((1U << op) - 1);
159
#ifdef INFLATE_STRICT
160
                if (dist > dmax) {
161
                    strm->msg = (char *)"invalid distance too far back";
162
                    state->mode = BAD;
163
                    break;
164
                }
165
#endif
166
65.6k
                hold >>= op;
167
65.6k
                bits -= op;
168
65.6k
                Tracevv((stderr, "inflate:         distance %u\n", dist));
169
65.6k
                op = (unsigned)(out - beg);     /* max distance in output */
170
65.6k
                if (dist > op) {                /* see if copy from window */
171
18.0k
                    op = dist - op;             /* distance back in window */
172
18.0k
                    if (op > whave) {
173
1.32k
                        if (state->sane) {
174
1.32k
                            strm->msg =
175
1.32k
                                (char *)"invalid distance too far back";
176
1.32k
                            state->mode = BAD;
177
1.32k
                            break;
178
1.32k
                        }
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
1.32k
                    }
199
16.7k
                    from = window;
200
16.7k
                    if (wnext == 0) {           /* very common case */
201
0
                        from += wsize - op;
202
0
                        if (op < len) {         /* some from window */
203
0
                            len -= op;
204
0
                            do {
205
0
                                *out++ = *from++;
206
0
                            } while (--op);
207
0
                            from = out - dist;  /* rest from output */
208
0
                        }
209
0
                    }
210
16.7k
                    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
0
                            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
0
                                do {
223
0
                                    *out++ = *from++;
224
0
                                } while (--op);
225
0
                                from = out - dist;      /* rest from output */
226
0
                            }
227
0
                        }
228
0
                    }
229
16.7k
                    else {                      /* contiguous in window */
230
16.7k
                        from += wnext - op;
231
16.7k
                        if (op < len) {         /* some from window */
232
9.10k
                            len -= op;
233
206k
                            do {
234
206k
                                *out++ = *from++;
235
206k
                            } while (--op);
236
9.10k
                            from = out - dist;  /* rest from output */
237
9.10k
                        }
238
16.7k
                    }
239
179k
                    while (len > 2) {
240
163k
                        *out++ = *from++;
241
163k
                        *out++ = *from++;
242
163k
                        *out++ = *from++;
243
163k
                        len -= 3;
244
163k
                    }
245
16.7k
                    if (len) {
246
9.70k
                        *out++ = *from++;
247
9.70k
                        if (len > 1)
248
4.24k
                            *out++ = *from++;
249
9.70k
                    }
250
16.7k
                }
251
47.5k
                else {
252
47.5k
                    from = out - dist;          /* copy direct from output */
253
331k
                    do {                        /* minimum length is three */
254
331k
                        *out++ = *from++;
255
331k
                        *out++ = *from++;
256
331k
                        *out++ = *from++;
257
331k
                        len -= 3;
258
331k
                    } while (len > 2);
259
47.5k
                    if (len) {
260
24.1k
                        *out++ = *from++;
261
24.1k
                        if (len > 1)
262
8.90k
                            *out++ = *from++;
263
24.1k
                    }
264
47.5k
                }
265
65.6k
            }
266
134
            else if ((op & 64) == 0) {          /* 2nd level distance code */
267
0
                here = dcode + here->val + (hold & ((1U << op) - 1));
268
0
                goto dodist;
269
0
            }
270
134
            else {
271
134
                strm->msg = (char *)"invalid distance code";
272
134
                state->mode = BAD;
273
134
                break;
274
134
            }
275
65.7k
        }
276
14.9k
        else if ((op & 64) == 0) {              /* 2nd level length code */
277
567
            here = lcode + here->val + (hold & ((1U << op) - 1));
278
567
            goto dolen;
279
567
        }
280
14.4k
        else if (op & 32) {                     /* end-of-block */
281
14.3k
            Tracevv((stderr, "inflate:         end of block\n"));
282
14.3k
            state->mode = TYPE;
283
14.3k
            break;
284
14.3k
        }
285
56
        else {
286
56
            strm->msg = (char *)"invalid literal/length code";
287
56
            state->mode = BAD;
288
56
            break;
289
56
        }
290
443k
    } while (in < last && out < end);
291
292
    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
293
22.4k
    len = bits >> 3;
294
22.4k
    in -= len;
295
22.4k
    bits -= len << 3;
296
22.4k
    hold &= (1U << bits) - 1;
297
298
    /* update state and return */
299
22.4k
    strm->next_in = in;
300
22.4k
    strm->next_out = out;
301
22.4k
    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
302
22.4k
    strm->avail_out = (unsigned)(out < end ?
303
22.4k
                                 257 + (end - out) : 257 - (out - end));
304
22.4k
    state->hold = hold;
305
22.4k
    state->bits = bits;
306
22.4k
    return;
307
22.4k
}
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 */