1 | /* inffast.c -- process literals and length/distance pairs fast |
---|
2 | * Copyright (C) 1995-1998 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 | if ((uInt)(q - s->window) >= d) /* offset before dest */ |
---|
97 | { /* just copy */ |
---|
98 | r = q - d; |
---|
99 | *q++ = *r++; c--; /* minimum count is three, */ |
---|
100 | *q++ = *r++; c--; /* so unroll loop a little */ |
---|
101 | } |
---|
102 | else /* else offset after destination */ |
---|
103 | { |
---|
104 | e = d - (uInt)(q - s->window); /* bytes from offset to end */ |
---|
105 | r = s->end - e; /* pointer to offset */ |
---|
106 | if (c > e) /* if source crosses, */ |
---|
107 | { |
---|
108 | c -= e; /* copy to end of window */ |
---|
109 | do { |
---|
110 | *q++ = *r++; |
---|
111 | } while (--e); |
---|
112 | r = s->window; /* copy rest from start of window */ |
---|
113 | } |
---|
114 | } |
---|
115 | do { /* copy all or what's left */ |
---|
116 | *q++ = *r++; |
---|
117 | } while (--c); |
---|
118 | break; |
---|
119 | } |
---|
120 | else if ((e & 64) == 0) |
---|
121 | { |
---|
122 | t += t->base; |
---|
123 | e = (t += ((uInt)b & inflate_mask[e]))->exop; |
---|
124 | } |
---|
125 | else |
---|
126 | { |
---|
127 | z->msg = (char*)"invalid distance code"; |
---|
128 | UNGRAB |
---|
129 | UPDATE |
---|
130 | return Z_DATA_ERROR; |
---|
131 | } |
---|
132 | } while (1); |
---|
133 | break; |
---|
134 | } |
---|
135 | if ((e & 64) == 0) |
---|
136 | { |
---|
137 | t += t->base; |
---|
138 | if ((e = (t += ((uInt)b & inflate_mask[e]))->exop) == 0) |
---|
139 | { |
---|
140 | DUMPBITS(t->bits) |
---|
141 | Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? |
---|
142 | "inflate: * literal '%c'\n" : |
---|
143 | "inflate: * literal 0x%02x\n", t->base)); |
---|
144 | *q++ = (Byte)t->base; |
---|
145 | m--; |
---|
146 | break; |
---|
147 | } |
---|
148 | } |
---|
149 | else if (e & 32) |
---|
150 | { |
---|
151 | Tracevv((stderr, "inflate: * end of block\n")); |
---|
152 | UNGRAB |
---|
153 | UPDATE |
---|
154 | return Z_STREAM_END; |
---|
155 | } |
---|
156 | else |
---|
157 | { |
---|
158 | z->msg = (char*)"invalid literal/length code"; |
---|
159 | UNGRAB |
---|
160 | UPDATE |
---|
161 | return Z_DATA_ERROR; |
---|
162 | } |
---|
163 | } while (1); |
---|
164 | } while (m >= 258 && n >= 10); |
---|
165 | |
---|
166 | /* not enough input or output--restore pointers and return */ |
---|
167 | UNGRAB |
---|
168 | UPDATE |
---|
169 | return Z_OK; |
---|
170 | } |
---|