c62d2810 |
1 | /* inffast.c -- process literals and length/distance pairs fast |
2 | * Copyright (C) 1995-2002 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 "infblock.h" |
9 | #include "infcodes.h" |
10 | #include "infutil.h" |
11 | #include "inffast.h" |
12 | |
13 | struct inflate_codes_state {int dummy;}; /* for buggy compilers */ |
14 | |
15 | /* simplify the use of the inflate_huft type with some defines */ |
16 | #define exop word.what.Exop |
17 | #define bits word.what.Bits |
18 | |
19 | /* macros for bit input with no checking and for returning unused bytes */ |
20 | #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} |
21 | #define UNGRAB {c=z->avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;} |
22 | |
23 | /* Called with number of bytes left to write in window at least 258 |
24 | (the maximum string length) and number of input bytes available |
25 | at least ten. The ten bytes are six bytes for the longest length/ |
26 | distance pair plus four bytes for overloading the bit buffer. */ |
27 | |
28 | int inflate_fast(bl, bd, tl, td, s, z) |
29 | uInt bl, bd; |
30 | inflate_huft *tl; |
31 | inflate_huft *td; /* need separate declaration for Borland C++ */ |
32 | inflate_blocks_statef *s; |
33 | z_streamp z; |
34 | { |
35 | inflate_huft *t; /* temporary pointer */ |
36 | uInt e; /* extra bits or operation */ |
37 | uLong b; /* bit buffer */ |
38 | uInt k; /* bits in bit buffer */ |
39 | Bytef *p; /* input data pointer */ |
40 | uInt n; /* bytes available there */ |
41 | Bytef *q; /* output window write pointer */ |
42 | uInt m; /* bytes to end of window or read pointer */ |
43 | uInt ml; /* mask for literal/length tree */ |
44 | uInt md; /* mask for distance tree */ |
45 | uInt c; /* bytes to copy */ |
46 | uInt d; /* distance back to copy from */ |
47 | Bytef *r; /* copy source pointer */ |
48 | |
49 | /* load input, output, bit values */ |
50 | LOAD |
51 | |
52 | /* initialize masks */ |
53 | ml = inflate_mask[bl]; |
54 | md = inflate_mask[bd]; |
55 | |
56 | /* do until not enough input or output space for fast loop */ |
57 | do { /* assume called with m >= 258 && n >= 10 */ |
58 | /* get literal/length code */ |
59 | GRABBITS(20) /* max bits for literal/length code */ |
60 | if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) |
61 | { |
62 | DUMPBITS(t->bits) |
63 | Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? |
64 | "inflate: * literal '%c'\n" : |
65 | "inflate: * literal 0x%02x\n", t->base)); |
66 | *q++ = (Byte)t->base; |
67 | m--; |
68 | continue; |
69 | } |
70 | do { |
71 | DUMPBITS(t->bits) |
72 | if (e & 16) |
73 | { |
74 | /* get extra bits for length */ |
75 | e &= 15; |
76 | c = t->base + ((uInt)b & inflate_mask[e]); |
77 | DUMPBITS(e) |
78 | Tracevv((stderr, "inflate: * length %u\n", c)); |
79 | |
80 | /* decode distance base of block to copy */ |
81 | GRABBITS(15); /* max bits for distance code */ |
82 | e = (t = td + ((uInt)b & md))->exop; |
83 | do { |
84 | DUMPBITS(t->bits) |
85 | if (e & 16) |
86 | { |
87 | /* get extra bits to add to distance base */ |
88 | e &= 15; |
89 | GRABBITS(e) /* get extra bits (up to 13) */ |
90 | d = t->base + ((uInt)b & inflate_mask[e]); |
91 | DUMPBITS(e) |
92 | Tracevv((stderr, "inflate: * distance %u\n", d)); |
93 | |
94 | /* do the copy */ |
95 | m -= c; |
96 | r = q - d; |
97 | if (r < s->window) /* wrap if needed */ |
98 | { |
99 | do { |
100 | r += s->end - s->window; /* force pointer in window */ |
101 | } while (r < s->window); /* covers invalid distances */ |
102 | e = s->end - r; |
103 | if (c > e) |
104 | { |
105 | c -= e; /* wrapped copy */ |
106 | do { |
107 | *q++ = *r++; |
108 | } while (--e); |
109 | r = s->window; |
110 | do { |
111 | *q++ = *r++; |
112 | } while (--c); |
113 | } |
114 | else /* normal copy */ |
115 | { |
116 | *q++ = *r++; c--; |
117 | *q++ = *r++; c--; |
118 | do { |
119 | *q++ = *r++; |
120 | } while (--c); |
121 | } |
122 | } |
123 | else /* normal copy */ |
124 | { |
125 | *q++ = *r++; c--; |
126 | *q++ = *r++; c--; |
127 | do { |
128 | *q++ = *r++; |
129 | } while (--c); |
130 | } |
131 | break; |
132 | } |
133 | else if ((e & 64) == 0) |
134 | { |
135 | t += t->base; |
136 | e = (t += ((uInt)b & inflate_mask[e]))->exop; |
137 | } |
138 | else |
139 | { |
140 | z->msg = (char*)"invalid distance code"; |
141 | UNGRAB |
142 | UPDATE |
143 | return Z_DATA_ERROR; |
144 | } |
145 | } while (1); |
146 | break; |
147 | } |
148 | if ((e & 64) == 0) |
149 | { |
150 | t += t->base; |
151 | if ((e = (t += ((uInt)b & inflate_mask[e]))->exop) == 0) |
152 | { |
153 | DUMPBITS(t->bits) |
154 | Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? |
155 | "inflate: * literal '%c'\n" : |
156 | "inflate: * literal 0x%02x\n", t->base)); |
157 | *q++ = (Byte)t->base; |
158 | m--; |
159 | break; |
160 | } |
161 | } |
162 | else if (e & 32) |
163 | { |
164 | Tracevv((stderr, "inflate: * end of block\n")); |
165 | UNGRAB |
166 | UPDATE |
167 | return Z_STREAM_END; |
168 | } |
169 | else |
170 | { |
171 | z->msg = (char*)"invalid literal/length code"; |
172 | UNGRAB |
173 | UPDATE |
174 | return Z_DATA_ERROR; |
175 | } |
176 | } while (1); |
177 | } while (m >= 258 && n >= 10); |
178 | |
179 | /* not enough input or output--restore pointers and return */ |
180 | UNGRAB |
181 | UPDATE |
182 | return Z_OK; |
183 | } |