Coverage Report

Created: 2024-07-27 06:28

/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
68.3k
void ZLIB_INTERNAL inflate_fast(z_streamp strm, unsigned start) {
51
68.3k
    struct inflate_state FAR *state;
52
68.3k
    z_const unsigned char FAR *in;      /* local strm->next_in */
53
68.3k
    z_const unsigned char FAR *last;    /* have enough input while in < last */
54
68.3k
    unsigned char FAR *out;     /* local strm->next_out */
55
68.3k
    unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
56
68.3k
    unsigned char FAR *end;     /* while out < end, enough space available */
57
#ifdef INFLATE_STRICT
58
    unsigned dmax;              /* maximum distance from zlib header */
59
#endif
60
68.3k
    unsigned wsize;             /* window size or zero if not using window */
61
68.3k
    unsigned whave;             /* valid bytes in the window */
62
68.3k
    unsigned wnext;             /* window write index */
63
68.3k
    unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
64
68.3k
    unsigned long hold;         /* local strm->hold */
65
68.3k
    unsigned bits;              /* local strm->bits */
66
68.3k
    code const FAR *lcode;      /* local strm->lencode */
67
68.3k
    code const FAR *dcode;      /* local strm->distcode */
68
68.3k
    unsigned lmask;             /* mask for first level of length codes */
69
68.3k
    unsigned dmask;             /* mask for first level of distance codes */
70
68.3k
    code const *here;           /* retrieved table entry */
71
68.3k
    unsigned op;                /* code bits, operation, extra bits, or */
72
                                /*  window position, window bytes to copy */
73
68.3k
    unsigned len;               /* match length, unused bytes */
74
68.3k
    unsigned dist;              /* match distance */
75
68.3k
    unsigned char FAR *from;    /* where to copy match from */
76
77
    /* copy state to local variables */
78
68.3k
    state = (struct inflate_state FAR *)strm->state;
79
68.3k
    in = strm->next_in;
80
68.3k
    last = in + (strm->avail_in - 5);
81
68.3k
    out = strm->next_out;
82
68.3k
    beg = out - (start - strm->avail_out);
83
68.3k
    end = out + (strm->avail_out - 257);
84
#ifdef INFLATE_STRICT
85
    dmax = state->dmax;
86
#endif
87
68.3k
    wsize = state->wsize;
88
68.3k
    whave = state->whave;
89
68.3k
    wnext = state->wnext;
90
68.3k
    window = state->window;
91
68.3k
    hold = state->hold;
92
68.3k
    bits = state->bits;
93
68.3k
    lcode = state->lencode;
94
68.3k
    dcode = state->distcode;
95
68.3k
    lmask = (1U << state->lenbits) - 1;
96
68.3k
    dmask = (1U << state->distbits) - 1;
97
98
    /* decode literals and length/distances until end-of-block or not enough
99
       input data or output space */
100
3.19M
    do {
101
3.19M
        if (bits < 15) {
102
1.45M
            hold += (unsigned long)(*in++) << bits;
103
1.45M
            bits += 8;
104
1.45M
            hold += (unsigned long)(*in++) << bits;
105
1.45M
            bits += 8;
106
1.45M
        }
107
3.19M
        here = lcode + (hold & lmask);
108
3.24M
      dolen:
109
3.24M
        op = (unsigned)(here->bits);
110
3.24M
        hold >>= op;
111
3.24M
        bits -= op;
112
3.24M
        op = (unsigned)(here->op);
113
3.24M
        if (op == 0) {                          /* literal */
114
953k
            Tracevv((stderr, here->val >= 0x20 && here->val < 0x7f ?
115
953k
                    "inflate:         literal '%c'\n" :
116
953k
                    "inflate:         literal 0x%02x\n", here->val));
117
953k
            *out++ = (unsigned char)(here->val);
118
953k
        }
119
2.28M
        else if (op & 16) {                     /* length base */
120
2.23M
            len = (unsigned)(here->val);
121
2.23M
            op &= 15;                           /* number of extra bits */
122
2.23M
            if (op) {
123
411k
                if (bits < op) {
124
0
                    hold += (unsigned long)(*in++) << bits;
125
0
                    bits += 8;
126
0
                }
127
411k
                len += (unsigned)hold & ((1U << op) - 1);
128
411k
                hold >>= op;
129
411k
                bits -= op;
130
411k
            }
131
2.23M
            Tracevv((stderr, "inflate:         length %u\n", len));
132
2.23M
            if (bits < 15) {
133
1.09M
                hold += (unsigned long)(*in++) << bits;
134
1.09M
                bits += 8;
135
1.09M
                hold += (unsigned long)(*in++) << bits;
136
1.09M
                bits += 8;
137
1.09M
            }
138
2.23M
            here = dcode + (hold & dmask);
139
2.25M
          dodist:
140
2.25M
            op = (unsigned)(here->bits);
141
2.25M
            hold >>= op;
142
2.25M
            bits -= op;
143
2.25M
            op = (unsigned)(here->op);
144
2.25M
            if (op & 16) {                      /* distance base */
145
2.23M
                dist = (unsigned)(here->val);
146
2.23M
                op &= 15;                       /* number of extra bits */
147
2.23M
                if (bits < op) {
148
227
                    hold += (unsigned long)(*in++) << bits;
149
227
                    bits += 8;
150
227
                    if (bits < op) {
151
0
                        hold += (unsigned long)(*in++) << bits;
152
0
                        bits += 8;
153
0
                    }
154
227
                }
155
2.23M
                dist += (unsigned)hold & ((1U << op) - 1);
156
#ifdef INFLATE_STRICT
157
                if (dist > dmax) {
158
                    strm->msg = (z_const char *)"invalid distance too far back";
159
                    state->mode = BAD;
160
                    break;
161
                }
162
#endif
163
2.23M
                hold >>= op;
164
2.23M
                bits -= op;
165
2.23M
                Tracevv((stderr, "inflate:         distance %u\n", dist));
166
2.23M
                op = (unsigned)(out - beg);     /* max distance in output */
167
2.23M
                if (dist > op) {                /* see if copy from window */
168
876k
                    op = dist - op;             /* distance back in window */
169
876k
                    if (op > whave) {
170
40
                        if (state->sane) {
171
40
                            strm->msg =
172
40
                                (z_const char *)"invalid distance too far back";
173
40
                            state->mode = BAD;
174
40
                            break;
175
40
                        }
176
#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
177
                        if (len <= op - whave) {
178
                            do {
179
                                *out++ = 0;
180
                            } while (--len);
181
                            continue;
182
                        }
183
                        len -= op - whave;
184
                        do {
185
                            *out++ = 0;
186
                        } while (--op > whave);
187
                        if (op == 0) {
188
                            from = out - dist;
189
                            do {
190
                                *out++ = *from++;
191
                            } while (--len);
192
                            continue;
193
                        }
194
#endif
195
40
                    }
196
876k
                    from = window;
197
876k
                    if (wnext == 0) {           /* very common case */
198
2.62k
                        from += wsize - op;
199
2.62k
                        if (op < len) {         /* some from window */
200
874
                            len -= op;
201
48.4k
                            do {
202
48.4k
                                *out++ = *from++;
203
48.4k
                            } while (--op);
204
874
                            from = out - dist;  /* rest from output */
205
874
                        }
206
2.62k
                    }
207
874k
                    else if (wnext < op) {      /* wrap around window */
208
46.2k
                        from += wsize + wnext - op;
209
46.2k
                        op -= wnext;
210
46.2k
                        if (op < len) {         /* some from end of window */
211
2.21k
                            len -= op;
212
151k
                            do {
213
151k
                                *out++ = *from++;
214
151k
                            } while (--op);
215
2.21k
                            from = window;
216
2.21k
                            if (wnext < len) {  /* some from start of window */
217
522
                                op = wnext;
218
522
                                len -= op;
219
56.9k
                                do {
220
56.9k
                                    *out++ = *from++;
221
56.9k
                                } while (--op);
222
522
                                from = out - dist;      /* rest from output */
223
522
                            }
224
2.21k
                        }
225
46.2k
                    }
226
828k
                    else {                      /* contiguous in window */
227
828k
                        from += wnext - op;
228
828k
                        if (op < len) {         /* some from window */
229
26.1k
                            len -= op;
230
1.35M
                            do {
231
1.35M
                                *out++ = *from++;
232
1.35M
                            } while (--op);
233
26.1k
                            from = out - dist;  /* rest from output */
234
26.1k
                        }
235
828k
                    }
236
3.65M
                    while (len > 2) {
237
2.78M
                        *out++ = *from++;
238
2.78M
                        *out++ = *from++;
239
2.78M
                        *out++ = *from++;
240
2.78M
                        len -= 3;
241
2.78M
                    }
242
876k
                    if (len) {
243
578k
                        *out++ = *from++;
244
578k
                        if (len > 1)
245
404k
                            *out++ = *from++;
246
578k
                    }
247
876k
                }
248
1.36M
                else {
249
1.36M
                    from = out - dist;          /* copy direct from output */
250
21.0M
                    do {                        /* minimum length is three */
251
21.0M
                        *out++ = *from++;
252
21.0M
                        *out++ = *from++;
253
21.0M
                        *out++ = *from++;
254
21.0M
                        len -= 3;
255
21.0M
                    } while (len > 2);
256
1.36M
                    if (len) {
257
602k
                        *out++ = *from++;
258
602k
                        if (len > 1)
259
321k
                            *out++ = *from++;
260
602k
                    }
261
1.36M
                }
262
2.23M
            }
263
15.8k
            else if ((op & 64) == 0) {          /* 2nd level distance code */
264
15.7k
                here = dcode + here->val + (hold & ((1U << op) - 1));
265
15.7k
                goto dodist;
266
15.7k
            }
267
45
            else {
268
45
                strm->msg = (z_const char *)"invalid distance code";
269
45
                state->mode = BAD;
270
45
                break;
271
45
            }
272
2.25M
        }
273
50.3k
        else if ((op & 64) == 0) {              /* 2nd level length code */
274
49.6k
            here = lcode + here->val + (hold & ((1U << op) - 1));
275
49.6k
            goto dolen;
276
49.6k
        }
277
781
        else if (op & 32) {                     /* end-of-block */
278
763
            Tracevv((stderr, "inflate:         end of block\n"));
279
763
            state->mode = TYPE;
280
763
            break;
281
763
        }
282
18
        else {
283
18
            strm->msg = (z_const char *)"invalid literal/length code";
284
18
            state->mode = BAD;
285
18
            break;
286
18
        }
287
3.24M
    } while (in < last && out < end);
288
289
    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
290
68.3k
    len = bits >> 3;
291
68.3k
    in -= len;
292
68.3k
    bits -= len << 3;
293
68.3k
    hold &= (1U << bits) - 1;
294
295
    /* update state and return */
296
68.3k
    strm->next_in = in;
297
68.3k
    strm->next_out = out;
298
68.3k
    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
299
68.3k
    strm->avail_out = (unsigned)(out < end ?
300
62.5k
                                 257 + (end - out) : 257 - (out - end));
301
68.3k
    state->hold = hold;
302
68.3k
    state->bits = bits;
303
68.3k
    return;
304
68.3k
}
305
306
/*
307
   inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
308
   - Using bit fields for code structure
309
   - Different op definition to avoid & for extra bits (do & for table bits)
310
   - Three separate decoding do-loops for direct, window, and wnext == 0
311
   - Special case for distance > 1 copies to do overlapped load and store copy
312
   - Explicit branch predictions (based on measured branch probabilities)
313
   - Deferring match copy and interspersed it with decoding subsequent codes
314
   - Swapping literal/length else
315
   - Swapping window/direct else
316
   - Larger unrolled copy loops (three is about right)
317
   - Moving len -= 3 statement into middle of loop
318
 */
319
320
#endif /* !ASMINF */