Chameleon

Chameleon Svn Source Tree

Root/branches/meklortOld/i386/modules/KextPatcher/inffast.c

Source at commit 1158 created 13 years 16 days ago.
By azimutz, Match nvidia.c with the one on my branch (Chazi) adding dev id's from issue 99 and Asus G74SX (0DF4, 1251).
1/* inffast.c -- fast decoding
2 * Copyright (C) 1995-2008, 2010 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 */
67void ZLIB_INTERNAL inflate_fast(strm, start)
68z_streamp strm;
69unsigned 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#ifdef INFLATE_STRICT
78 unsigned dmax; /* maximum distance from zlib header */
79#endif
80 unsigned wsize; /* window size or zero if not using window */
81 unsigned whave; /* valid bytes in the window */
82 unsigned wnext; /* window write index */
83 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
84 unsigned long hold; /* local strm->hold */
85 unsigned bits; /* local strm->bits */
86 code const FAR *lcode; /* local strm->lencode */
87 code const FAR *dcode; /* local strm->distcode */
88 unsigned lmask; /* mask for first level of length codes */
89 unsigned dmask; /* mask for first level of distance codes */
90 code here; /* retrieved table entry */
91 unsigned op; /* code bits, operation, extra bits, or */
92 /* window position, window bytes to copy */
93 unsigned len; /* match length, unused bytes */
94 unsigned dist; /* match distance */
95 unsigned char FAR *from; /* where to copy match from */
96
97 /* copy state to local variables */
98 state = (struct inflate_state FAR *)strm->state;
99 in = strm->next_in - OFF;
100 last = in + (strm->avail_in - 5);
101 out = strm->next_out - OFF;
102 beg = out - (start - strm->avail_out);
103 end = out + (strm->avail_out - 257);
104#ifdef INFLATE_STRICT
105 dmax = state->dmax;
106#endif
107 wsize = state->wsize;
108 whave = state->whave;
109 wnext = state->wnext;
110 window = state->window;
111 hold = state->hold;
112 bits = state->bits;
113 lcode = state->lencode;
114 dcode = state->distcode;
115 lmask = (1U << state->lenbits) - 1;
116 dmask = (1U << state->distbits) - 1;
117
118 /* decode literals and length/distances until end-of-block or not enough
119 input data or output space */
120 do {
121 if (bits < 15) {
122 hold += (unsigned long)(PUP(in)) << bits;
123 bits += 8;
124 hold += (unsigned long)(PUP(in)) << bits;
125 bits += 8;
126 }
127 here = lcode[hold & lmask];
128 dolen:
129 op = (unsigned)(here.bits);
130 hold >>= op;
131 bits -= op;
132 op = (unsigned)(here.op);
133 if (op == 0) { /* literal */
134 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
135 "inflate: literal '%c'\n" :
136 "inflate: literal 0x%02x\n", here.val));
137 PUP(out) = (unsigned char)(here.val);
138 }
139 else if (op & 16) { /* length base */
140 len = (unsigned)(here.val);
141 op &= 15; /* number of extra bits */
142 if (op) {
143 if (bits < op) {
144 hold += (unsigned long)(PUP(in)) << bits;
145 bits += 8;
146 }
147 len += (unsigned)hold & ((1U << op) - 1);
148 hold >>= op;
149 bits -= op;
150 }
151 Tracevv((stderr, "inflate: length %u\n", len));
152 if (bits < 15) {
153 hold += (unsigned long)(PUP(in)) << bits;
154 bits += 8;
155 hold += (unsigned long)(PUP(in)) << bits;
156 bits += 8;
157 }
158 here = dcode[hold & dmask];
159 dodist:
160 op = (unsigned)(here.bits);
161 hold >>= op;
162 bits -= op;
163 op = (unsigned)(here.op);
164 if (op & 16) { /* distance base */
165 dist = (unsigned)(here.val);
166 op &= 15; /* number of extra bits */
167 if (bits < op) {
168 hold += (unsigned long)(PUP(in)) << bits;
169 bits += 8;
170 if (bits < op) {
171 hold += (unsigned long)(PUP(in)) << bits;
172 bits += 8;
173 }
174 }
175 dist += (unsigned)hold & ((1U << op) - 1);
176#ifdef INFLATE_STRICT
177 if (dist > dmax) {
178 strm->msg = (char *)"invalid distance too far back";
179 state->mode = BAD;
180 break;
181 }
182#endif
183 hold >>= op;
184 bits -= op;
185 Tracevv((stderr, "inflate: distance %u\n", dist));
186 op = (unsigned)(out - beg); /* max distance in output */
187 if (dist > op) { /* see if copy from window */
188 op = dist - op; /* distance back in window */
189 if (op > whave) {
190 if (state->sane) {
191 strm->msg =
192 (char *)"invalid distance too far back";
193 state->mode = BAD;
194 break;
195 }
196#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
197 if (len <= op - whave) {
198 do {
199 PUP(out) = 0;
200 } while (--len);
201 continue;
202 }
203 len -= op - whave;
204 do {
205 PUP(out) = 0;
206 } while (--op > whave);
207 if (op == 0) {
208 from = out - dist;
209 do {
210 PUP(out) = PUP(from);
211 } while (--len);
212 continue;
213 }
214#endif
215 }
216 from = window - OFF;
217 if (wnext == 0) { /* very common case */
218 from += wsize - op;
219 if (op < len) { /* some from window */
220 len -= op;
221 do {
222 PUP(out) = PUP(from);
223 } while (--op);
224 from = out - dist; /* rest from output */
225 }
226 }
227 else if (wnext < op) { /* wrap around window */
228 from += wsize + wnext - op;
229 op -= wnext;
230 if (op < len) { /* some from end of window */
231 len -= op;
232 do {
233 PUP(out) = PUP(from);
234 } while (--op);
235 from = window - OFF;
236 if (wnext < len) { /* some from start of window */
237 op = wnext;
238 len -= op;
239 do {
240 PUP(out) = PUP(from);
241 } while (--op);
242 from = out - dist; /* rest from output */
243 }
244 }
245 }
246 else { /* contiguous in window */
247 from += wnext - op;
248 if (op < len) { /* some from window */
249 len -= op;
250 do {
251 PUP(out) = PUP(from);
252 } while (--op);
253 from = out - dist; /* rest from output */
254 }
255 }
256 while (len > 2) {
257 PUP(out) = PUP(from);
258 PUP(out) = PUP(from);
259 PUP(out) = PUP(from);
260 len -= 3;
261 }
262 if (len) {
263 PUP(out) = PUP(from);
264 if (len > 1)
265 PUP(out) = PUP(from);
266 }
267 }
268 else {
269 from = out - dist; /* copy direct from output */
270 do { /* minimum length is three */
271 PUP(out) = PUP(from);
272 PUP(out) = PUP(from);
273 PUP(out) = PUP(from);
274 len -= 3;
275 } while (len > 2);
276 if (len) {
277 PUP(out) = PUP(from);
278 if (len > 1)
279 PUP(out) = PUP(from);
280 }
281 }
282 }
283 else if ((op & 64) == 0) { /* 2nd level distance code */
284 here = dcode[here.val + (hold & ((1U << op) - 1))];
285 goto dodist;
286 }
287 else {
288 strm->msg = (char *)"invalid distance code";
289 state->mode = BAD;
290 break;
291 }
292 }
293 else if ((op & 64) == 0) { /* 2nd level length code */
294 here = lcode[here.val + (hold & ((1U << op) - 1))];
295 goto dolen;
296 }
297 else if (op & 32) { /* end-of-block */
298 Tracevv((stderr, "inflate: end of block\n"));
299 state->mode = TYPE;
300 break;
301 }
302 else {
303 strm->msg = (char *)"invalid literal/length code";
304 state->mode = BAD;
305 break;
306 }
307 } while (in < last && out < end);
308
309 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
310 len = bits >> 3;
311 in -= len;
312 bits -= len << 3;
313 hold &= (1U << bits) - 1;
314
315 /* update state and return */
316 strm->next_in = in + OFF;
317 strm->next_out = out + OFF;
318 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
319 strm->avail_out = (unsigned)(out < end ?
320 257 + (end - out) : 257 - (out - end));
321 state->hold = hold;
322 state->bits = bits;
323 return;
324}
325
326/*
327 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
328 - Using bit fields for code structure
329 - Different op definition to avoid & for extra bits (do & for table bits)
330 - Three separate decoding do-loops for direct, window, and wnext == 0
331 - Special case for distance > 1 copies to do overlapped load and store copy
332 - Explicit branch predictions (based on measured branch probabilities)
333 - Deferring match copy and interspersed it with decoding subsequent codes
334 - Swapping literal/length else
335 - Swapping window/direct else
336 - Larger unrolled copy loops (three is about right)
337 - Moving len -= 3 statement into middle of loop
338 */
339
340#endif /* !ASMINF */
341

Archive Download this file

Revision: 1158