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