summaryrefslogtreecommitdiff
path: root/contrib/blast
diff options
context:
space:
mode:
authorMark Adler <madler@alumni.caltech.edu>2011-09-09 23:22:37 -0700
committerMark Adler <madler@alumni.caltech.edu>2011-09-09 23:22:37 -0700
commit4b5a43a219d51066c01ff2ab86af18b967f2d0dd (patch)
tree4dcaf0cd18751d04cf638a9a6ec521990d4f2e90 /contrib/blast
parent086e982175da84b3db958191031380794315f95f (diff)
downloadzlib-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.c154
-rw-r--r--contrib/blast/blast.h2
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 */
35struct state { 35struct 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 */
66local int bits(struct state *s, int need) 66local 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 */
97struct huffman { 97struct 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 */
123local int decode(struct state *s, struct huffman *h) 123local 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 */
185local int construct(struct huffman *h, const unsigned char *rep, int n) 185local 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 */
276local int decomp(struct state *s) 276local 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 */
377int blast(blast_in infun, void *inhow, blast_out outfun, void *outhow) 377int 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