Mercurial > hg > CbC > CbC_gcc

comparison zlib/inffast.c @ 111:04ced10e8804

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents ae3a4bfb450b
children
comparison
equal deleted inserted replaced
68:561a7518be6b 111:04ced10e8804
1 /* inffast.c -- fast decoding 1 /* inffast.c -- fast decoding
2 * Copyright (C) 1995-2004 Mark Adler 2 * Copyright (C) 1995-2017 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */ 4 */
5 5
6 #include "zutil.h" 6 #include "zutil.h"
7 #include "inftrees.h" 7 #include "inftrees.h"
8 #include "inflate.h" 8 #include "inflate.h"
9 #include "inffast.h" 9 #include "inffast.h"
10 10
11 #ifndef ASMINF 11 #ifdef ASMINF
12 12 # pragma message("Assembler code may have bugs -- use at your own risk")
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 13 #else
28 # define OFF 1
29 # define PUP(a) *++(a)
30 #endif
31 14
32 /* 15 /*
33 Decode literal, length, and distance codes and write out the resulting 16 Decode literal, length, and distance codes and write out the resulting
34 literal and match bytes until either not enough input or output is 17 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. 18 available, an end-of-block is encountered, or a data error is encountered.
62 - The maximum bytes that a single length/distance pair can output is 258 45 - 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() 46 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 47 requires strm->avail_out >= 258 for each loop to avoid checking for
65 output space. 48 output space.
66 */ 49 */
67 void inflate_fast(strm, start) 50 void ZLIB_INTERNAL inflate_fast(strm, start)
68 z_streamp strm; 51 z_streamp strm;
69 unsigned start; /* inflate()'s starting value for strm->avail_out */ 52 unsigned start; /* inflate()'s starting value for strm->avail_out */
70 { 53 {
71 struct inflate_state FAR *state; 54 struct inflate_state FAR *state;
72 unsigned char FAR *in; /* local strm->next_in */ 55 z_const unsigned char FAR *in; /* local strm->next_in */
73 unsigned char FAR *last; /* while in < last, enough input available */ 56 z_const unsigned char FAR *last; /* have enough input while in < last */
74 unsigned char FAR *out; /* local strm->next_out */ 57 unsigned char FAR *out; /* local strm->next_out */
75 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */ 58 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
76 unsigned char FAR *end; /* while out < end, enough space available */ 59 unsigned char FAR *end; /* while out < end, enough space available */
77 #ifdef INFLATE_STRICT 60 #ifdef INFLATE_STRICT
78 unsigned dmax; /* maximum distance from zlib header */ 61 unsigned dmax; /* maximum distance from zlib header */
79 #endif 62 #endif
80 unsigned wsize; /* window size or zero if not using window */ 63 unsigned wsize; /* window size or zero if not using window */
81 unsigned whave; /* valid bytes in the window */ 64 unsigned whave; /* valid bytes in the window */
82 unsigned write; /* window write index */ 65 unsigned wnext; /* window write index */
83 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */ 66 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
84 unsigned long hold; /* local strm->hold */ 67 unsigned long hold; /* local strm->hold */
85 unsigned bits; /* local strm->bits */ 68 unsigned bits; /* local strm->bits */
86 code const FAR *lcode; /* local strm->lencode */ 69 code const FAR *lcode; /* local strm->lencode */
87 code const FAR *dcode; /* local strm->distcode */ 70 code const FAR *dcode; /* local strm->distcode */
88 unsigned lmask; /* mask for first level of length codes */ 71 unsigned lmask; /* mask for first level of length codes */
89 unsigned dmask; /* mask for first level of distance codes */ 72 unsigned dmask; /* mask for first level of distance codes */
90 code this; /* retrieved table entry */ 73 code here; /* retrieved table entry */
91 unsigned op; /* code bits, operation, extra bits, or */ 74 unsigned op; /* code bits, operation, extra bits, or */
92 /* window position, window bytes to copy */ 75 /* window position, window bytes to copy */
93 unsigned len; /* match length, unused bytes */ 76 unsigned len; /* match length, unused bytes */
94 unsigned dist; /* match distance */ 77 unsigned dist; /* match distance */
95 unsigned char FAR *from; /* where to copy match from */ 78 unsigned char FAR *from; /* where to copy match from */
96 79
97 /* copy state to local variables */ 80 /* copy state to local variables */
98 state = (struct inflate_state FAR *)strm->state; 81 state = (struct inflate_state FAR *)strm->state;
99 in = strm->next_in - OFF; 82 in = strm->next_in;
100 last = in + (strm->avail_in - 5); 83 last = in + (strm->avail_in - 5);
101 out = strm->next_out - OFF; 84 out = strm->next_out;
102 beg = out - (start - strm->avail_out); 85 beg = out - (start - strm->avail_out);
103 end = out + (strm->avail_out - 257); 86 end = out + (strm->avail_out - 257);
104 #ifdef INFLATE_STRICT 87 #ifdef INFLATE_STRICT
105 dmax = state->dmax; 88 dmax = state->dmax;
106 #endif 89 #endif
107 wsize = state->wsize; 90 wsize = state->wsize;
108 whave = state->whave; 91 whave = state->whave;
109 write = state->write; 92 wnext = state->wnext;
110 window = state->window; 93 window = state->window;
111 hold = state->hold; 94 hold = state->hold;
112 bits = state->bits; 95 bits = state->bits;
113 lcode = state->lencode; 96 lcode = state->lencode;
114 dcode = state->distcode; 97 dcode = state->distcode;
117 100
118 /* decode literals and length/distances until end-of-block or not enough 101 /* decode literals and length/distances until end-of-block or not enough
119 input data or output space */ 102 input data or output space */
120 do { 103 do {
121 if (bits < 15) { 104 if (bits < 15) {
122 hold += (unsigned long)(PUP(in)) << bits; 105 hold += (unsigned long)(*in++) << bits;
123 bits += 8; 106 bits += 8;
124 hold += (unsigned long)(PUP(in)) << bits; 107 hold += (unsigned long)(*in++) << bits;
125 bits += 8; 108 bits += 8;
126 } 109 }
127 this = lcode[hold & lmask]; 110 here = lcode[hold & lmask];
128 dolen: 111 dolen:
129 op = (unsigned)(this.bits); 112 op = (unsigned)(here.bits);
130 hold >>= op; 113 hold >>= op;
131 bits -= op; 114 bits -= op;
132 op = (unsigned)(this.op); 115 op = (unsigned)(here.op);
133 if (op == 0) { /* literal */ 116 if (op == 0) { /* literal */
134 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ? 117 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
135 "inflate: literal '%c'\n" : 118 "inflate: literal '%c'\n" :
136 "inflate: literal 0x%02x\n", this.val)); 119 "inflate: literal 0x%02x\n", here.val));
137 PUP(out) = (unsigned char)(this.val); 120 *out++ = (unsigned char)(here.val);
138 } 121 }
139 else if (op & 16) { /* length base */ 122 else if (op & 16) { /* length base */
140 len = (unsigned)(this.val); 123 len = (unsigned)(here.val);
141 op &= 15; /* number of extra bits */ 124 op &= 15; /* number of extra bits */
142 if (op) { 125 if (op) {
143 if (bits < op) { 126 if (bits < op) {
144 hold += (unsigned long)(PUP(in)) << bits; 127 hold += (unsigned long)(*in++) << bits;
145 bits += 8; 128 bits += 8;
146 } 129 }
147 len += (unsigned)hold & ((1U << op) - 1); 130 len += (unsigned)hold & ((1U << op) - 1);
148 hold >>= op; 131 hold >>= op;
149 bits -= op; 132 bits -= op;
150 } 133 }
151 Tracevv((stderr, "inflate: length %u\n", len)); 134 Tracevv((stderr, "inflate: length %u\n", len));
152 if (bits < 15) { 135 if (bits < 15) {
153 hold += (unsigned long)(PUP(in)) << bits; 136 hold += (unsigned long)(*in++) << bits;
154 bits += 8; 137 bits += 8;
155 hold += (unsigned long)(PUP(in)) << bits; 138 hold += (unsigned long)(*in++) << bits;
156 bits += 8; 139 bits += 8;
157 } 140 }
158 this = dcode[hold & dmask]; 141 here = dcode[hold & dmask];
159 dodist: 142 dodist:
160 op = (unsigned)(this.bits); 143 op = (unsigned)(here.bits);
161 hold >>= op; 144 hold >>= op;
162 bits -= op; 145 bits -= op;
163 op = (unsigned)(this.op); 146 op = (unsigned)(here.op);
164 if (op & 16) { /* distance base */ 147 if (op & 16) { /* distance base */
165 dist = (unsigned)(this.val); 148 dist = (unsigned)(here.val);
166 op &= 15; /* number of extra bits */ 149 op &= 15; /* number of extra bits */
167 if (bits < op) { 150 if (bits < op) {
168 hold += (unsigned long)(PUP(in)) << bits; 151 hold += (unsigned long)(*in++) << bits;
169 bits += 8; 152 bits += 8;
170 if (bits < op) { 153 if (bits < op) {
171 hold += (unsigned long)(PUP(in)) << bits; 154 hold += (unsigned long)(*in++) << bits;
172 bits += 8; 155 bits += 8;
173 } 156 }
174 } 157 }
175 dist += (unsigned)hold & ((1U << op) - 1); 158 dist += (unsigned)hold & ((1U << op) - 1);
176 #ifdef INFLATE_STRICT 159 #ifdef INFLATE_STRICT
185 Tracevv((stderr, "inflate: distance %u\n", dist)); 168 Tracevv((stderr, "inflate: distance %u\n", dist));
186 op = (unsigned)(out - beg); /* max distance in output */ 169 op = (unsigned)(out - beg); /* max distance in output */
187 if (dist > op) { /* see if copy from window */ 170 if (dist > op) { /* see if copy from window */
188 op = dist - op; /* distance back in window */ 171 op = dist - op; /* distance back in window */
189 if (op > whave) { 172 if (op > whave) {
190 strm->msg = (char *)"invalid distance too far back"; 173 if (state->sane) {
191 state->mode = BAD; 174 strm->msg =
192 break; 175 (char *)"invalid distance too far back";
193 } 176 state->mode = BAD;
194 from = window - OFF; 177 break;
195 if (write == 0) { /* very common case */ 178 }
179 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
180 if (len <= op - whave) {
181 do {
182 *out++ = 0;
183 } while (--len);
184 continue;
185 }
186 len -= op - whave;
187 do {
188 *out++ = 0;
189 } while (--op > whave);
190 if (op == 0) {
191 from = out - dist;
192 do {
193 *out++ = *from++;
194 } while (--len);
195 continue;
196 }
197 #endif
198 }
199 from = window;
200 if (wnext == 0) { /* very common case */
196 from += wsize - op; 201 from += wsize - op;
197 if (op < len) { /* some from window */ 202 if (op < len) { /* some from window */
198 len -= op; 203 len -= op;
199 do { 204 do {
200 PUP(out) = PUP(from); 205 *out++ = *from++;
201 } while (--op); 206 } while (--op);
202 from = out - dist; /* rest from output */ 207 from = out - dist; /* rest from output */
203 } 208 }
204 } 209 }
205 else if (write < op) { /* wrap around window */ 210 else if (wnext < op) { /* wrap around window */
206 from += wsize + write - op; 211 from += wsize + wnext - op;
207 op -= write; 212 op -= wnext;
208 if (op < len) { /* some from end of window */ 213 if (op < len) { /* some from end of window */
209 len -= op; 214 len -= op;
210 do { 215 do {
211 PUP(out) = PUP(from); 216 *out++ = *from++;
212 } while (--op); 217 } while (--op);
213 from = window - OFF; 218 from = window;
214 if (write < len) { /* some from start of window */ 219 if (wnext < len) { /* some from start of window */
215 op = write; 220 op = wnext;
216 len -= op; 221 len -= op;
217 do { 222 do {
218 PUP(out) = PUP(from); 223 *out++ = *from++;
219 } while (--op); 224 } while (--op);
220 from = out - dist; /* rest from output */ 225 from = out - dist; /* rest from output */
221 } 226 }
222 } 227 }
223 } 228 }
224 else { /* contiguous in window */ 229 else { /* contiguous in window */
225 from += write - op; 230 from += wnext - op;
226 if (op < len) { /* some from window */ 231 if (op < len) { /* some from window */
227 len -= op; 232 len -= op;
228 do { 233 do {
229 PUP(out) = PUP(from); 234 *out++ = *from++;
230 } while (--op); 235 } while (--op);
231 from = out - dist; /* rest from output */ 236 from = out - dist; /* rest from output */
232 } 237 }
233 } 238 }
234 while (len > 2) { 239 while (len > 2) {
235 PUP(out) = PUP(from); 240 *out++ = *from++;
236 PUP(out) = PUP(from); 241 *out++ = *from++;
237 PUP(out) = PUP(from); 242 *out++ = *from++;
238 len -= 3; 243 len -= 3;
239 } 244 }
240 if (len) { 245 if (len) {
241 PUP(out) = PUP(from); 246 *out++ = *from++;
242 if (len > 1) 247 if (len > 1)
243 PUP(out) = PUP(from); 248 *out++ = *from++;
244 } 249 }
245 } 250 }
246 else { 251 else {
247 from = out - dist; /* copy direct from output */ 252 from = out - dist; /* copy direct from output */
248 do { /* minimum length is three */ 253 do { /* minimum length is three */
249 PUP(out) = PUP(from); 254 *out++ = *from++;
250 PUP(out) = PUP(from); 255 *out++ = *from++;
251 PUP(out) = PUP(from); 256 *out++ = *from++;
252 len -= 3; 257 len -= 3;
253 } while (len > 2); 258 } while (len > 2);
254 if (len) { 259 if (len) {
255 PUP(out) = PUP(from); 260 *out++ = *from++;
256 if (len > 1) 261 if (len > 1)
257 PUP(out) = PUP(from); 262 *out++ = *from++;
258 } 263 }
259 } 264 }
260 } 265 }
261 else if ((op & 64) == 0) { /* 2nd level distance code */ 266 else if ((op & 64) == 0) { /* 2nd level distance code */
262 this = dcode[this.val + (hold & ((1U << op) - 1))]; 267 here = dcode[here.val + (hold & ((1U << op) - 1))];
263 goto dodist; 268 goto dodist;
264 } 269 }
265 else { 270 else {
266 strm->msg = (char *)"invalid distance code"; 271 strm->msg = (char *)"invalid distance code";
267 state->mode = BAD; 272 state->mode = BAD;
268 break; 273 break;
269 } 274 }
270 } 275 }
271 else if ((op & 64) == 0) { /* 2nd level length code */ 276 else if ((op & 64) == 0) { /* 2nd level length code */
272 this = lcode[this.val + (hold & ((1U << op) - 1))]; 277 here = lcode[here.val + (hold & ((1U << op) - 1))];
273 goto dolen; 278 goto dolen;
274 } 279 }
275 else if (op & 32) { /* end-of-block */ 280 else if (op & 32) { /* end-of-block */
276 Tracevv((stderr, "inflate: end of block\n")); 281 Tracevv((stderr, "inflate: end of block\n"));
277 state->mode = TYPE; 282 state->mode = TYPE;
289 in -= len; 294 in -= len;
290 bits -= len << 3; 295 bits -= len << 3;
291 hold &= (1U << bits) - 1; 296 hold &= (1U << bits) - 1;
292 297
293 /* update state and return */ 298 /* update state and return */
294 strm->next_in = in + OFF; 299 strm->next_in = in;
295 strm->next_out = out + OFF; 300 strm->next_out = out;
296 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last)); 301 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
297 strm->avail_out = (unsigned)(out < end ? 302 strm->avail_out = (unsigned)(out < end ?
298 257 + (end - out) : 257 - (out - end)); 303 257 + (end - out) : 257 - (out - end));
299 state->hold = hold; 304 state->hold = hold;
300 state->bits = bits; 305 state->bits = bits;
303 308
304 /* 309 /*
305 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe): 310 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
306 - Using bit fields for code structure 311 - Using bit fields for code structure
307 - Different op definition to avoid & for extra bits (do & for table bits) 312 - Different op definition to avoid & for extra bits (do & for table bits)
308 - Three separate decoding do-loops for direct, window, and write == 0 313 - Three separate decoding do-loops for direct, window, and wnext == 0
309 - Special case for distance > 1 copies to do overlapped load and store copy 314 - Special case for distance > 1 copies to do overlapped load and store copy
310 - Explicit branch predictions (based on measured branch probabilities) 315 - Explicit branch predictions (based on measured branch probabilities)
311 - Deferring match copy and interspersed it with decoding subsequent codes 316 - Deferring match copy and interspersed it with decoding subsequent codes
312 - Swapping literal/length else 317 - Swapping literal/length else
313 - Swapping window/direct else 318 - Swapping window/direct else