inffast.c 10.4 KB
Newer Older
1
/* inffast.c -- fast decoding
Romain TISSERAND's avatar
Romain TISSERAND committed
2
 * Copyright (C) 1995-2017 Mark Adler
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

#include "zutil.h"
#include "inftrees.h"
#include "inflate.h"
#include "inffast.h"

/*
   Decode literal, length, and distance codes and write out the resulting
   literal and match bytes until either not enough input or output is
   available, an end-of-block is encountered, or a data error is encountered.
   When large enough input and output buffers are supplied to inflate(), for
   example, a 16K input buffer and a 64K output buffer, more than 95% of the
   inflate execution time is spent in this routine.

   Entry assumptions:

        state->mode == LEN
        strm->avail_in >= 6
        strm->avail_out >= 258
        start >= strm->avail_out
        state->bits < 8

   On return, state->mode is one of:

        LEN -- ran out of enough output space or enough available input
        TYPE -- reached end of block code, inflate() to interpret next block
        BAD -- error in block data

   Notes:

    - The maximum input bits used by a length/distance pair is 15 bits for the
      length code, 5 bits for the length extra, 15 bits for the distance code,
      and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
      Therefore if strm->avail_in >= 6, then there is enough input to avoid
      checking for available input while decoding.

    - The maximum bytes that a single length/distance pair can output is 258
      bytes, which is the maximum length that can be coded.  inflate_fast()
      requires strm->avail_out >= 258 for each loop to avoid checking for
      output space.
 */
void ZLIB_INTERNAL inflate_fast(strm, start)
z_streamp strm;
unsigned start;         /* inflate()'s starting value for strm->avail_out */
{
    struct inflate_state FAR *state;
Romain TISSERAND's avatar
Romain TISSERAND committed
51
52
    z_const unsigned char FAR *in;      /* local strm->next_in */
    z_const unsigned char FAR *last;    /* have enough input while in < last */
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
    unsigned char FAR *out;     /* local strm->next_out */
    unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
    unsigned char FAR *end;     /* while out < end, enough space available */
    unsigned wsize;             /* window size or zero if not using window */
    unsigned whave;             /* valid bytes in the window */
    unsigned wnext;             /* window write index */
    unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
    unsigned long hold;         /* local strm->hold */
    unsigned bits;              /* local strm->bits */
    code const FAR *lcode;      /* local strm->lencode */
    code const FAR *dcode;      /* local strm->distcode */
    unsigned lmask;             /* mask for first level of length codes */
    unsigned dmask;             /* mask for first level of distance codes */
    code here;                  /* retrieved table entry */
    unsigned op;                /* code bits, operation, extra bits, or */
                                /*  window position, window bytes to copy */
    unsigned len;               /* match length, unused bytes */
    unsigned dist;              /* match distance */
    unsigned char FAR *from;    /* where to copy match from */

    /* copy state to local variables */
    state = (struct inflate_state FAR *)strm->state;
Romain TISSERAND's avatar
Romain TISSERAND committed
75
    in = strm->next_in;
76
    last = in + (strm->avail_in - 5);
Romain TISSERAND's avatar
Romain TISSERAND committed
77
    out = strm->next_out;
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
    beg = out - (start - strm->avail_out);
    end = out + (strm->avail_out - 257);
    wsize = state->wsize;
    whave = state->whave;
    wnext = state->wnext;
    window = state->window;
    hold = state->hold;
    bits = state->bits;
    lcode = state->lencode;
    dcode = state->distcode;
    lmask = (1U << state->lenbits) - 1;
    dmask = (1U << state->distbits) - 1;

    /* decode literals and length/distances until end-of-block or not enough
       input data or output space */
    do {
        if (bits < 15) {
Romain TISSERAND's avatar
Romain TISSERAND committed
95
            hold += (unsigned long)(*in++) << bits;
96
            bits += 8;
Romain TISSERAND's avatar
Romain TISSERAND committed
97
            hold += (unsigned long)(*in++) << bits;
98
99
100
101
102
103
104
105
106
            bits += 8;
        }
        here = lcode[hold & lmask];
      dolen:
        op = (unsigned)(here.bits);
        hold >>= op;
        bits -= op;
        op = (unsigned)(here.op);
        if (op == 0) {                          /* literal */
Romain TISSERAND's avatar
Romain TISSERAND committed
107
            *out++ = (unsigned char)(here.val);
108
109
110
111
112
113
        }
        else if (op & 16) {                     /* length base */
            len = (unsigned)(here.val);
            op &= 15;                           /* number of extra bits */
            if (op) {
                if (bits < op) {
Romain TISSERAND's avatar
Romain TISSERAND committed
114
                    hold += (unsigned long)(*in++) << bits;
115
116
117
118
119
120
121
                    bits += 8;
                }
                len += (unsigned)hold & ((1U << op) - 1);
                hold >>= op;
                bits -= op;
            }
            if (bits < 15) {
Romain TISSERAND's avatar
Romain TISSERAND committed
122
                hold += (unsigned long)(*in++) << bits;
123
                bits += 8;
Romain TISSERAND's avatar
Romain TISSERAND committed
124
                hold += (unsigned long)(*in++) << bits;
125
126
127
128
129
130
131
132
133
134
135
136
                bits += 8;
            }
            here = dcode[hold & dmask];
          dodist:
            op = (unsigned)(here.bits);
            hold >>= op;
            bits -= op;
            op = (unsigned)(here.op);
            if (op & 16) {                      /* distance base */
                dist = (unsigned)(here.val);
                op &= 15;                       /* number of extra bits */
                if (bits < op) {
Romain TISSERAND's avatar
Romain TISSERAND committed
137
                    hold += (unsigned long)(*in++) << bits;
138
139
                    bits += 8;
                    if (bits < op) {
Romain TISSERAND's avatar
Romain TISSERAND committed
140
                        hold += (unsigned long)(*in++) << bits;
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
                        bits += 8;
                    }
                }
                dist += (unsigned)hold & ((1U << op) - 1);
                hold >>= op;
                bits -= op;
                op = (unsigned)(out - beg);     /* max distance in output */
                if (dist > op) {                /* see if copy from window */
                    op = dist - op;             /* distance back in window */
                    if (op > whave) {
                        if (state->sane) {
                            strm->msg =
                                (char *)"invalid distance too far back";
                            state->mode = BAD;
                            break;
                        }
                    }
Romain TISSERAND's avatar
Romain TISSERAND committed
158
                    from = window;
159
160
161
162
163
                    if (wnext == 0) {           /* very common case */
                        from += wsize - op;
                        if (op < len) {         /* some from window */
                            len -= op;
                            do {
Romain TISSERAND's avatar
Romain TISSERAND committed
164
                                *out++ = *from++;
165
166
167
168
169
170
171
172
173
174
                            } while (--op);
                            from = out - dist;  /* rest from output */
                        }
                    }
                    else if (wnext < op) {      /* wrap around window */
                        from += wsize + wnext - op;
                        op -= wnext;
                        if (op < len) {         /* some from end of window */
                            len -= op;
                            do {
Romain TISSERAND's avatar
Romain TISSERAND committed
175
                                *out++ = *from++;
176
                            } while (--op);
Romain TISSERAND's avatar
Romain TISSERAND committed
177
                            from = window;
178
179
180
181
                            if (wnext < len) {  /* some from start of window */
                                op = wnext;
                                len -= op;
                                do {
Romain TISSERAND's avatar
Romain TISSERAND committed
182
                                    *out++ = *from++;
183
184
185
186
187
188
189
190
191
192
                                } while (--op);
                                from = out - dist;      /* rest from output */
                            }
                        }
                    }
                    else {                      /* contiguous in window */
                        from += wnext - op;
                        if (op < len) {         /* some from window */
                            len -= op;
                            do {
Romain TISSERAND's avatar
Romain TISSERAND committed
193
                                *out++ = *from++;
194
195
196
197
198
                            } while (--op);
                            from = out - dist;  /* rest from output */
                        }
                    }
                    while (len > 2) {
Romain TISSERAND's avatar
Romain TISSERAND committed
199
200
201
                        *out++ = *from++;
                        *out++ = *from++;
                        *out++ = *from++;
202
203
204
                        len -= 3;
                    }
                    if (len) {
Romain TISSERAND's avatar
Romain TISSERAND committed
205
                        *out++ = *from++;
206
                        if (len > 1)
Romain TISSERAND's avatar
Romain TISSERAND committed
207
                            *out++ = *from++;
208
209
210
211
212
                    }
                }
                else {
                    from = out - dist;          /* copy direct from output */
                    do {                        /* minimum length is three */
Romain TISSERAND's avatar
Romain TISSERAND committed
213
214
215
                        *out++ = *from++;
                        *out++ = *from++;
                        *out++ = *from++;
216
217
218
                        len -= 3;
                    } while (len > 2);
                    if (len) {
Romain TISSERAND's avatar
Romain TISSERAND committed
219
                        *out++ = *from++;
220
                        if (len > 1)
Romain TISSERAND's avatar
Romain TISSERAND committed
221
                            *out++ = *from++;
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
                    }
                }
            }
            else if ((op & 64) == 0) {          /* 2nd level distance code */
                here = dcode[here.val + (hold & ((1U << op) - 1))];
                goto dodist;
            }
            else {
                strm->msg = (char *)"invalid distance code";
                state->mode = BAD;
                break;
            }
        }
        else if ((op & 64) == 0) {              /* 2nd level length code */
            here = lcode[here.val + (hold & ((1U << op) - 1))];
            goto dolen;
        }
        else if (op & 32) {                     /* end-of-block */
            state->mode = TYPE;
            break;
        }
        else {
            strm->msg = (char *)"invalid literal/length code";
            state->mode = BAD;
            break;
        }
    } while (in < last && out < end);

    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
    len = bits >> 3;
    in -= len;
    bits -= len << 3;
    hold &= (1U << bits) - 1;

    /* update state and return */
Romain TISSERAND's avatar
Romain TISSERAND committed
257
258
    strm->next_in = in;
    strm->next_out = out;
259
260
261
262
263
264
    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
    strm->avail_out = (unsigned)(out < end ?
                                 257 + (end - out) : 257 - (out - end));
    state->hold = hold;
    state->bits = bits;
}