diff options
author | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:22:37 -0700 |
---|---|---|
committer | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:22:37 -0700 |
commit | 4b5a43a219d51066c01ff2ab86af18b967f2d0dd (patch) | |
tree | 4dcaf0cd18751d04cf638a9a6ec521990d4f2e90 /contrib/blast | |
parent | 086e982175da84b3db958191031380794315f95f (diff) | |
download | zlib-1.2.0.5.tar.gz zlib-1.2.0.5.tar.bz2 zlib-1.2.0.5.zip |
zlib 1.2.0.5v1.2.0.5
Diffstat (limited to 'contrib/blast')
-rw-r--r-- | contrib/blast/blast.c | 154 | ||||
-rw-r--r-- | contrib/blast/blast.h | 2 |
2 files changed, 78 insertions, 78 deletions
diff --git a/contrib/blast/blast.c b/contrib/blast/blast.c index 67dab4e..4ce697a 100644 --- a/contrib/blast/blast.c +++ b/contrib/blast/blast.c | |||
@@ -20,36 +20,36 @@ | |||
20 | /* | 20 | /* |
21 | * Change history: | 21 | * Change history: |
22 | * | 22 | * |
23 | * 1.0 12 Feb 2003 - First version | 23 | * 1.0 12 Feb 2003 - First version |
24 | * 1.1 16 Feb 2003 - Fixed distance check for > 4 GB uncompressed data | 24 | * 1.1 16 Feb 2003 - Fixed distance check for > 4 GB uncompressed data |
25 | */ | 25 | */ |
26 | 26 | ||
27 | #include <setjmp.h> /* for setjmp(), longjmp(), and jmp_buf */ | 27 | #include <setjmp.h> /* for setjmp(), longjmp(), and jmp_buf */ |
28 | #include "blast.h" /* prototype for blast() */ | 28 | #include "blast.h" /* prototype for blast() */ |
29 | 29 | ||
30 | #define local static /* for local function definitions */ | 30 | #define local static /* for local function definitions */ |
31 | #define MAXBITS 13 /* maximum code length */ | 31 | #define MAXBITS 13 /* maximum code length */ |
32 | #define MAXWIN 4096 /* maximum window size */ | 32 | #define MAXWIN 4096 /* maximum window size */ |
33 | 33 | ||
34 | /* input and output state */ | 34 | /* input and output state */ |
35 | struct state { | 35 | struct state { |
36 | /* input state */ | 36 | /* input state */ |
37 | blast_in infun; /* input function provided by user */ | 37 | blast_in infun; /* input function provided by user */ |
38 | void *inhow; /* opaque information passed to infun() */ | 38 | void *inhow; /* opaque information passed to infun() */ |
39 | unsigned char *in; /* next input location */ | 39 | unsigned char *in; /* next input location */ |
40 | unsigned left; /* available input at in */ | 40 | unsigned left; /* available input at in */ |
41 | int bitbuf; /* bit buffer */ | 41 | int bitbuf; /* bit buffer */ |
42 | int bitcnt; /* number of bits in bit buffer */ | 42 | int bitcnt; /* number of bits in bit buffer */ |
43 | 43 | ||
44 | /* input limit error return state for bits() and decode() */ | 44 | /* input limit error return state for bits() and decode() */ |
45 | jmp_buf env; | 45 | jmp_buf env; |
46 | 46 | ||
47 | /* output state */ | 47 | /* output state */ |
48 | blast_out outfun; /* output function provided by user */ | 48 | blast_out outfun; /* output function provided by user */ |
49 | void *outhow; /* opaque information passed to outfun() */ | 49 | void *outhow; /* opaque information passed to outfun() */ |
50 | unsigned next; /* index of next write location in out[] */ | 50 | unsigned next; /* index of next write location in out[] */ |
51 | int first; /* true to check distances (for first 4K) */ | 51 | int first; /* true to check distances (for first 4K) */ |
52 | unsigned char out[MAXWIN]; /* output buffer and sliding window */ | 52 | unsigned char out[MAXWIN]; /* output buffer and sliding window */ |
53 | }; | 53 | }; |
54 | 54 | ||
55 | /* | 55 | /* |
@@ -65,16 +65,16 @@ struct state { | |||
65 | */ | 65 | */ |
66 | local int bits(struct state *s, int need) | 66 | local int bits(struct state *s, int need) |
67 | { | 67 | { |
68 | int val; /* bit accumulator */ | 68 | int val; /* bit accumulator */ |
69 | 69 | ||
70 | /* load at least need bits into val */ | 70 | /* load at least need bits into val */ |
71 | val = s->bitbuf; | 71 | val = s->bitbuf; |
72 | while (s->bitcnt < need) { | 72 | while (s->bitcnt < need) { |
73 | if (s->left == 0) { | 73 | if (s->left == 0) { |
74 | s->left = s->infun(s->inhow, &(s->in)); | 74 | s->left = s->infun(s->inhow, &(s->in)); |
75 | if (s->left == 0) longjmp(s->env, 1); /* out of input */ | 75 | if (s->left == 0) longjmp(s->env, 1); /* out of input */ |
76 | } | 76 | } |
77 | val |= (int)(*(s->in)++) << s->bitcnt; /* load eight bits */ | 77 | val |= (int)(*(s->in)++) << s->bitcnt; /* load eight bits */ |
78 | s->left--; | 78 | s->left--; |
79 | s->bitcnt += 8; | 79 | s->bitcnt += 8; |
80 | } | 80 | } |
@@ -95,8 +95,8 @@ local int bits(struct state *s, int need) | |||
95 | * seen in the function decode() below. | 95 | * seen in the function decode() below. |
96 | */ | 96 | */ |
97 | struct huffman { | 97 | struct huffman { |
98 | short *count; /* number of symbols of each length */ | 98 | short *count; /* number of symbols of each length */ |
99 | short *symbol; /* canonically ordered symbols */ | 99 | short *symbol; /* canonically ordered symbols */ |
100 | }; | 100 | }; |
101 | 101 | ||
102 | /* | 102 | /* |
@@ -122,14 +122,14 @@ struct huffman { | |||
122 | */ | 122 | */ |
123 | local int decode(struct state *s, struct huffman *h) | 123 | local int decode(struct state *s, struct huffman *h) |
124 | { | 124 | { |
125 | int len; /* current number of bits in code */ | 125 | int len; /* current number of bits in code */ |
126 | int code; /* len bits being decoded */ | 126 | int code; /* len bits being decoded */ |
127 | int first; /* first code of length len */ | 127 | int first; /* first code of length len */ |
128 | int count; /* number of codes of length len */ | 128 | int count; /* number of codes of length len */ |
129 | int index; /* index of first code of length len in symbol table */ | 129 | int index; /* index of first code of length len in symbol table */ |
130 | int bitbuf; /* bits from stream */ | 130 | int bitbuf; /* bits from stream */ |
131 | int left; /* bits left in next or left to process */ | 131 | int left; /* bits left in next or left to process */ |
132 | short *next; /* next number of codes */ | 132 | short *next; /* next number of codes */ |
133 | 133 | ||
134 | bitbuf = s->bitbuf; | 134 | bitbuf = s->bitbuf; |
135 | left = s->bitcnt; | 135 | left = s->bitcnt; |
@@ -138,15 +138,15 @@ local int decode(struct state *s, struct huffman *h) | |||
138 | next = h->count + 1; | 138 | next = h->count + 1; |
139 | while (1) { | 139 | while (1) { |
140 | while (left--) { | 140 | while (left--) { |
141 | code |= (bitbuf & 1) ^ 1; /* invert code */ | 141 | code |= (bitbuf & 1) ^ 1; /* invert code */ |
142 | bitbuf >>= 1; | 142 | bitbuf >>= 1; |
143 | count = *next++; | 143 | count = *next++; |
144 | if (code < first + count) { /* if length len, return symbol */ | 144 | if (code < first + count) { /* if length len, return symbol */ |
145 | s->bitbuf = bitbuf; | 145 | s->bitbuf = bitbuf; |
146 | s->bitcnt = (s->bitcnt - len) & 7; | 146 | s->bitcnt = (s->bitcnt - len) & 7; |
147 | return h->symbol[index + (code - first)]; | 147 | return h->symbol[index + (code - first)]; |
148 | } | 148 | } |
149 | index += count; /* else update for next length */ | 149 | index += count; /* else update for next length */ |
150 | first += count; | 150 | first += count; |
151 | first <<= 1; | 151 | first <<= 1; |
152 | code <<= 1; | 152 | code <<= 1; |
@@ -156,13 +156,13 @@ local int decode(struct state *s, struct huffman *h) | |||
156 | if (left == 0) break; | 156 | if (left == 0) break; |
157 | if (s->left == 0) { | 157 | if (s->left == 0) { |
158 | s->left = s->infun(s->inhow, &(s->in)); | 158 | s->left = s->infun(s->inhow, &(s->in)); |
159 | if (s->left == 0) longjmp(s->env, 1); /* out of input */ | 159 | if (s->left == 0) longjmp(s->env, 1); /* out of input */ |
160 | } | 160 | } |
161 | bitbuf = *(s->in)++; | 161 | bitbuf = *(s->in)++; |
162 | s->left--; | 162 | s->left--; |
163 | if (left > 8) left = 8; | 163 | if (left > 8) left = 8; |
164 | } | 164 | } |
165 | return -9; /* ran out of codes */ | 165 | return -9; /* ran out of codes */ |
166 | } | 166 | } |
167 | 167 | ||
168 | /* | 168 | /* |
@@ -184,11 +184,11 @@ local int decode(struct state *s, struct huffman *h) | |||
184 | */ | 184 | */ |
185 | local int construct(struct huffman *h, const unsigned char *rep, int n) | 185 | local int construct(struct huffman *h, const unsigned char *rep, int n) |
186 | { | 186 | { |
187 | int symbol; /* current symbol when stepping through length[] */ | 187 | int symbol; /* current symbol when stepping through length[] */ |
188 | int len; /* current length when stepping through h->count[] */ | 188 | int len; /* current length when stepping through h->count[] */ |
189 | int left; /* number of possible codes left of current length */ | 189 | int left; /* number of possible codes left of current length */ |
190 | short offs[MAXBITS+1]; /* offsets in symbol table for each length */ | 190 | short offs[MAXBITS+1]; /* offsets in symbol table for each length */ |
191 | short length[256]; /* code lengths */ | 191 | short length[256]; /* code lengths */ |
192 | 192 | ||
193 | /* convert compact repeat counts into symbol bit length list */ | 193 | /* convert compact repeat counts into symbol bit length list */ |
194 | symbol = 0; | 194 | symbol = 0; |
@@ -206,17 +206,17 @@ local int construct(struct huffman *h, const unsigned char *rep, int n) | |||
206 | for (len = 0; len <= MAXBITS; len++) | 206 | for (len = 0; len <= MAXBITS; len++) |
207 | h->count[len] = 0; | 207 | h->count[len] = 0; |
208 | for (symbol = 0; symbol < n; symbol++) | 208 | for (symbol = 0; symbol < n; symbol++) |
209 | (h->count[length[symbol]])++; /* assumes lengths are within bounds */ | 209 | (h->count[length[symbol]])++; /* assumes lengths are within bounds */ |
210 | if (h->count[0] == n) /* no codes! */ | 210 | if (h->count[0] == n) /* no codes! */ |
211 | return 0; /* complete, but decode() will fail */ | 211 | return 0; /* complete, but decode() will fail */ |
212 | 212 | ||
213 | /* check for an over-subscribed or incomplete set of lengths */ | 213 | /* check for an over-subscribed or incomplete set of lengths */ |
214 | left = 1; /* one possible code of zero length */ | 214 | left = 1; /* one possible code of zero length */ |
215 | for (len = 1; len <= MAXBITS; len++) { | 215 | for (len = 1; len <= MAXBITS; len++) { |
216 | left <<= 1; /* one more bit, double codes left */ | 216 | left <<= 1; /* one more bit, double codes left */ |
217 | left -= h->count[len]; /* deduct count from possible codes */ | 217 | left -= h->count[len]; /* deduct count from possible codes */ |
218 | if (left < 0) return left; /* over-subscribed--return negative */ | 218 | if (left < 0) return left; /* over-subscribed--return negative */ |
219 | } /* left > 0 means incomplete */ | 219 | } /* left > 0 means incomplete */ |
220 | 220 | ||
221 | /* generate offsets into symbol table for each length for sorting */ | 221 | /* generate offsets into symbol table for each length for sorting */ |
222 | offs[1] = 0; | 222 | offs[1] = 0; |
@@ -275,35 +275,35 @@ local int construct(struct huffman *h, const unsigned char *rep, int n) | |||
275 | */ | 275 | */ |
276 | local int decomp(struct state *s) | 276 | local int decomp(struct state *s) |
277 | { | 277 | { |
278 | int lit; /* true if literals are coded */ | 278 | int lit; /* true if literals are coded */ |
279 | int dict; /* log2(dictionary size) - 6 */ | 279 | int dict; /* log2(dictionary size) - 6 */ |
280 | int symbol; /* decoded symbol, extra bits for distance */ | 280 | int symbol; /* decoded symbol, extra bits for distance */ |
281 | int len; /* length for copy */ | 281 | int len; /* length for copy */ |
282 | int dist; /* distance for copy */ | 282 | int dist; /* distance for copy */ |
283 | int copy; /* copy counter */ | 283 | int copy; /* copy counter */ |
284 | unsigned char *from, *to; /* copy pointers */ | 284 | unsigned char *from, *to; /* copy pointers */ |
285 | static int virgin = 1; /* build tables once */ | 285 | static int virgin = 1; /* build tables once */ |
286 | static short litcnt[MAXBITS+1], litsym[256]; /* litcode memory */ | 286 | static short litcnt[MAXBITS+1], litsym[256]; /* litcode memory */ |
287 | static short lencnt[MAXBITS+1], lensym[16]; /* lencode memory */ | 287 | static short lencnt[MAXBITS+1], lensym[16]; /* lencode memory */ |
288 | static short distcnt[MAXBITS+1], distsym[64]; /* distcode memory */ | 288 | static short distcnt[MAXBITS+1], distsym[64]; /* distcode memory */ |
289 | static struct huffman litcode = {litcnt, litsym}; /* length code */ | 289 | static struct huffman litcode = {litcnt, litsym}; /* length code */ |
290 | static struct huffman lencode = {lencnt, lensym}; /* length code */ | 290 | static struct huffman lencode = {lencnt, lensym}; /* length code */ |
291 | static struct huffman distcode = {distcnt, distsym};/* distance code */ | 291 | static struct huffman distcode = {distcnt, distsym};/* distance code */ |
292 | /* bit lengths of literal codes */ | 292 | /* bit lengths of literal codes */ |
293 | static const unsigned char litlen[] = { | 293 | static const unsigned char litlen[] = { |
294 | 11, 124, 8, 7, 28, 7, 188, 13, 76, 4, 10, 8, 12, 10, 12, 10, 8, 23, 8, | 294 | 11, 124, 8, 7, 28, 7, 188, 13, 76, 4, 10, 8, 12, 10, 12, 10, 8, 23, 8, |
295 | 9, 7, 6, 7, 8, 7, 6, 55, 8, 23, 24, 12, 11, 7, 9, 11, 12, 6, 7, 22, 5, | 295 | 9, 7, 6, 7, 8, 7, 6, 55, 8, 23, 24, 12, 11, 7, 9, 11, 12, 6, 7, 22, 5, |
296 | 7, 24, 6, 11, 9, 6, 7, 22, 7, 11, 38, 7, 9, 8, 25, 11, 8, 11, 9, 12, | 296 | 7, 24, 6, 11, 9, 6, 7, 22, 7, 11, 38, 7, 9, 8, 25, 11, 8, 11, 9, 12, |
297 | 8, 12, 5, 38, 5, 38, 5, 11, 7, 5, 6, 21, 6, 10, 53, 8, 7, 24, 10, 27, | 297 | 8, 12, 5, 38, 5, 38, 5, 11, 7, 5, 6, 21, 6, 10, 53, 8, 7, 24, 10, 27, |
298 | 44, 253, 253, 253, 252, 252, 252, 13, 12, 45, 12, 45, 12, 61, 12, 45, | 298 | 44, 253, 253, 253, 252, 252, 252, 13, 12, 45, 12, 45, 12, 61, 12, 45, |
299 | 44, 173}; | 299 | 44, 173}; |
300 | /* bit lengths of length codes 0..15 */ | 300 | /* bit lengths of length codes 0..15 */ |
301 | static const unsigned char lenlen[] = {2, 35, 36, 53, 38, 23}; | 301 | static const unsigned char lenlen[] = {2, 35, 36, 53, 38, 23}; |
302 | /* bit lengths of distance codes 0..63 */ | 302 | /* bit lengths of distance codes 0..63 */ |
303 | static const unsigned char distlen[] = {2, 20, 53, 230, 247, 151, 248}; | 303 | static const unsigned char distlen[] = {2, 20, 53, 230, 247, 151, 248}; |
304 | static const short base[16] = { /* base for length codes */ | 304 | static const short base[16] = { /* base for length codes */ |
305 | 3, 2, 4, 5, 6, 7, 8, 9, 10, 12, 16, 24, 40, 72, 136, 264}; | 305 | 3, 2, 4, 5, 6, 7, 8, 9, 10, 12, 16, 24, 40, 72, 136, 264}; |
306 | static const char extra[16] = { /* extra bits for length codes */ | 306 | static const char extra[16] = { /* extra bits for length codes */ |
307 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8}; | 307 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8}; |
308 | 308 | ||
309 | /* set up decoding tables (once--might not be thread-safe) */ | 309 | /* set up decoding tables (once--might not be thread-safe) */ |
@@ -326,7 +326,7 @@ local int decomp(struct state *s) | |||
326 | /* get length */ | 326 | /* get length */ |
327 | symbol = decode(s, &lencode); | 327 | symbol = decode(s, &lencode); |
328 | len = base[symbol] + bits(s, extra[symbol]); | 328 | len = base[symbol] + bits(s, extra[symbol]); |
329 | if (len == 519) break; /* end code */ | 329 | if (len == 519) break; /* end code */ |
330 | 330 | ||
331 | /* get distance */ | 331 | /* get distance */ |
332 | symbol = len == 2 ? 2 : dict; | 332 | symbol = len == 2 ? 2 : dict; |
@@ -334,7 +334,7 @@ local int decomp(struct state *s) | |||
334 | dist += bits(s, symbol); | 334 | dist += bits(s, symbol); |
335 | dist++; | 335 | dist++; |
336 | if (s->first && dist > s->next) | 336 | if (s->first && dist > s->next) |
337 | return -3; /* distance too far back */ | 337 | return -3; /* distance too far back */ |
338 | 338 | ||
339 | /* copy length bytes from distance bytes back */ | 339 | /* copy length bytes from distance bytes back */ |
340 | do { | 340 | do { |
@@ -376,8 +376,8 @@ local int decomp(struct state *s) | |||
376 | /* See comments in blast.h */ | 376 | /* See comments in blast.h */ |
377 | int blast(blast_in infun, void *inhow, blast_out outfun, void *outhow) | 377 | int blast(blast_in infun, void *inhow, blast_out outfun, void *outhow) |
378 | { | 378 | { |
379 | struct state s; /* input/output state */ | 379 | struct state s; /* input/output state */ |
380 | int err; /* return value */ | 380 | int err; /* return value */ |
381 | 381 | ||
382 | /* initialize input state */ | 382 | /* initialize input state */ |
383 | s.infun = infun; | 383 | s.infun = infun; |
@@ -393,10 +393,10 @@ int blast(blast_in infun, void *inhow, blast_out outfun, void *outhow) | |||
393 | s.first = 1; | 393 | s.first = 1; |
394 | 394 | ||
395 | /* return if bits() or decode() tries to read past available input */ | 395 | /* return if bits() or decode() tries to read past available input */ |
396 | if (setjmp(s.env) != 0) /* if came back here via longjmp(), */ | 396 | if (setjmp(s.env) != 0) /* if came back here via longjmp(), */ |
397 | err = 2; /* then skip decomp(), return error */ | 397 | err = 2; /* then skip decomp(), return error */ |
398 | else | 398 | else |
399 | err = decomp(&s); /* decompress */ | 399 | err = decomp(&s); /* decompress */ |
400 | 400 | ||
401 | /* write any leftover output and update the error code if needed */ | 401 | /* write any leftover output and update the error code if needed */ |
402 | if (err != 1 && s.next && s.outfun(s.outhow, s.out, s.next) && err == 0) | 402 | if (err != 1 && s.next && s.outfun(s.outhow, s.out, s.next) && err == 0) |
diff --git a/contrib/blast/blast.h b/contrib/blast/blast.h index 2417837..ce9e541 100644 --- a/contrib/blast/blast.h +++ b/contrib/blast/blast.h | |||
@@ -18,7 +18,7 @@ | |||
18 | misrepresented as being the original software. | 18 | misrepresented as being the original software. |
19 | 3. This notice may not be removed or altered from any source distribution. | 19 | 3. This notice may not be removed or altered from any source distribution. |
20 | 20 | ||
21 | Mark Adler madler@alumni.caltech.edu | 21 | Mark Adler madler@alumni.caltech.edu |
22 | */ | 22 | */ |
23 | 23 | ||
24 | 24 | ||