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