2 * Reimplementation of Deflate (RFC1951) compression. Adapted from
3 * the version in PuTTY, and extended to write dynamic Huffman
4 * trees and choose block boundaries usefully.
10 * - Feature: could do with forms of flush other than SYNC_FLUSH.
11 * I'm not sure exactly how those work when you don't know in
12 * advance that your next block will be static (as we did in
13 * PuTTY). And remember the 9-bit limitation of zlib.
14 * + also, zlib has FULL_FLUSH which clears the LZ77 state as
15 * well, for random access.
17 * - Compression quality: chooseblock() appears to be computing
18 * wildly inaccurate block size estimates. Possible resolutions:
19 * + find and fix some trivial bug I haven't spotted yet
20 * + abandon the entropic approximation and go with trial
23 * - Compression quality: see if increasing SYMLIMIT causes
24 * dynamic blocks to start being consistently smaller than it.
25 * + actually we seem to be there already, but check on a
28 * - Compression quality: we ought to be able to fall right back
29 * to actual uncompressed blocks if really necessary, though
30 * it's not clear what the criterion for doing so would be.
34 * This software is copyright 2000-2006 Simon Tatham.
36 * Permission is hereby granted, free of charge, to any person
37 * obtaining a copy of this software and associated documentation
38 * files (the "Software"), to deal in the Software without
39 * restriction, including without limitation the rights to use,
40 * copy, modify, merge, publish, distribute, sublicense, and/or
41 * sell copies of the Software, and to permit persons to whom the
42 * Software is furnished to do so, subject to the following
45 * The above copyright notice and this permission notice shall be
46 * included in all copies or substantial portions of the Software.
48 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
49 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
50 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
51 * NONINFRINGEMENT. IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE
52 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
53 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
54 * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
66 #define snew(type) ( (type *) malloc(sizeof(type)) )
67 #define snewn(n, type) ( (type *) malloc((n) * sizeof(type)) )
68 #define sresize(x, n, type) ( (type *) realloc((x), (n) * sizeof(type)) )
69 #define sfree(x) ( free((x)) )
71 #define lenof(x) (sizeof((x)) / sizeof(*(x)))
78 /* ----------------------------------------------------------------------
79 * This file can be compiled in a number of modes.
81 * With -DSTANDALONE, it builds a self-contained deflate tool which
82 * can compress, decompress, and also analyse a deflated file to
83 * print out the sequence of literals and copy commands it
86 * With -DTESTMODE, it builds a test application which is given a
87 * file on standard input, both compresses and decompresses it, and
88 * outputs the re-decompressed result so it can be conveniently
89 * diffed against the original. Define -DTESTDBG as well for lots
94 /* gcc-specific diagnostic macro */
95 #define debug_int(x...) ( fprintf(stderr, x) )
96 #define debug(x) ( debug_int x )
106 int analyse_level
= 0;
109 /* ----------------------------------------------------------------------
110 * Basic LZ77 code. This bit is designed modularly, so it could be
111 * ripped out and used in a different LZ77 compressor. Go to it,
115 struct LZ77InternalContext
;
117 struct LZ77InternalContext
*ictx
;
119 void (*literal
) (struct LZ77Context
* ctx
, unsigned char c
);
120 void (*match
) (struct LZ77Context
* ctx
, int distance
, int len
);
124 * Initialise the private fields of an LZ77Context. It's up to the
125 * user to initialise the public fields.
127 static int lz77_init(struct LZ77Context
*ctx
);
130 * Supply data to be compressed. Will update the private fields of
131 * the LZ77Context, and will call literal() and match() to output.
132 * If `compress' is FALSE, it will never emit a match, but will
133 * instead call literal() for everything.
135 static void lz77_compress(struct LZ77Context
*ctx
,
136 const unsigned char *data
, int len
, int compress
);
139 * Modifiable parameters.
141 #define WINSIZE 32768 /* window size. Must be power of 2! */
142 #define HASHMAX 2039 /* one more than max hash value */
143 #define MAXMATCH 32 /* how many matches we track */
144 #define HASHCHARS 3 /* how many chars make a hash */
147 * This compressor takes a less slapdash approach than the
148 * gzip/zlib one. Rather than allowing our hash chains to fall into
149 * disuse near the far end, we keep them doubly linked so we can
150 * _find_ the far end, and then every time we add a new byte to the
151 * window (thus rolling round by one and removing the previous
152 * byte), we can carefully remove the hash chain entry.
155 #define INVALID -1 /* invalid hash _and_ invalid offset */
157 short next
, prev
; /* array indices within the window */
162 short first
; /* window index of first in chain */
169 struct LZ77InternalContext
{
170 struct WindowEntry win
[WINSIZE
];
171 unsigned char data
[WINSIZE
];
173 struct HashEntry hashtab
[HASHMAX
];
174 unsigned char pending
[HASHCHARS
];
178 static int lz77_hash(const unsigned char *data
)
180 return (257 * data
[0] + 263 * data
[1] + 269 * data
[2]) % HASHMAX
;
183 static int lz77_init(struct LZ77Context
*ctx
)
185 struct LZ77InternalContext
*st
;
188 st
= snew(struct LZ77InternalContext
);
194 for (i
= 0; i
< WINSIZE
; i
++)
195 st
->win
[i
].next
= st
->win
[i
].prev
= st
->win
[i
].hashval
= INVALID
;
196 for (i
= 0; i
< HASHMAX
; i
++)
197 st
->hashtab
[i
].first
= INVALID
;
205 static void lz77_advance(struct LZ77InternalContext
*st
,
206 unsigned char c
, int hash
)
211 * Remove the hash entry at winpos from the tail of its chain,
212 * or empty the chain if it's the only thing on the chain.
214 if (st
->win
[st
->winpos
].prev
!= INVALID
) {
215 st
->win
[st
->win
[st
->winpos
].prev
].next
= INVALID
;
216 } else if (st
->win
[st
->winpos
].hashval
!= INVALID
) {
217 st
->hashtab
[st
->win
[st
->winpos
].hashval
].first
= INVALID
;
221 * Create a new entry at winpos and add it to the head of its
224 st
->win
[st
->winpos
].hashval
= hash
;
225 st
->win
[st
->winpos
].prev
= INVALID
;
226 off
= st
->win
[st
->winpos
].next
= st
->hashtab
[hash
].first
;
227 st
->hashtab
[hash
].first
= st
->winpos
;
229 st
->win
[off
].prev
= st
->winpos
;
230 st
->data
[st
->winpos
] = c
;
233 * Advance the window pointer.
235 st
->winpos
= (st
->winpos
+ 1) & (WINSIZE
- 1);
238 #define CHARAT(k) ( (k)<0 ? st->data[(st->winpos+k)&(WINSIZE-1)] : data[k] )
240 static void lz77_compress(struct LZ77Context
*ctx
,
241 const unsigned char *data
, int len
, int compress
)
243 struct LZ77InternalContext
*st
= ctx
->ictx
;
244 int i
, hash
, distance
, off
, nmatch
, matchlen
, advance
;
245 struct Match defermatch
, matches
[MAXMATCH
];
249 * Add any pending characters from last time to the window. (We
250 * might not be able to.)
252 for (i
= 0; i
< st
->npending
; i
++) {
253 unsigned char foo
[HASHCHARS
];
255 if (len
+ st
->npending
- i
< HASHCHARS
) {
256 /* Update the pending array. */
257 for (j
= i
; j
< st
->npending
; j
++)
258 st
->pending
[j
- i
] = st
->pending
[j
];
261 for (j
= 0; j
< HASHCHARS
; j
++)
262 foo
[j
] = (i
+ j
< st
->npending ? st
->pending
[i
+ j
] :
263 data
[i
+ j
- st
->npending
]);
264 lz77_advance(st
, foo
[0], lz77_hash(foo
));
272 /* Don't even look for a match, if we're not compressing. */
273 if (compress
&& len
>= HASHCHARS
) {
275 * Hash the next few characters.
277 hash
= lz77_hash(data
);
280 * Look the hash up in the corresponding hash chain and see
284 for (off
= st
->hashtab
[hash
].first
;
285 off
!= INVALID
; off
= st
->win
[off
].next
) {
286 /* distance = 1 if off == st->winpos-1 */
287 /* distance = WINSIZE if off == st->winpos */
289 WINSIZE
- (off
+ WINSIZE
- st
->winpos
) % WINSIZE
;
290 for (i
= 0; i
< HASHCHARS
; i
++)
291 if (CHARAT(i
) != CHARAT(i
- distance
))
293 if (i
== HASHCHARS
) {
294 matches
[nmatch
].distance
= distance
;
295 matches
[nmatch
].len
= 3;
296 if (++nmatch
>= MAXMATCH
)
307 * We've now filled up matches[] with nmatch potential
308 * matches. Follow them down to find the longest. (We
309 * assume here that it's always worth favouring a
310 * longer match over a shorter one.)
312 matchlen
= HASHCHARS
;
313 while (matchlen
< len
) {
315 for (i
= j
= 0; i
< nmatch
; i
++) {
316 if (CHARAT(matchlen
) ==
317 CHARAT(matchlen
- matches
[i
].distance
)) {
318 matches
[j
++] = matches
[i
];
328 * We've now got all the longest matches. We favour the
329 * shorter distances, which means we go with matches[0].
330 * So see if we want to defer it or throw it away.
332 matches
[0].len
= matchlen
;
333 if (defermatch
.len
> 0) {
334 if (matches
[0].len
> defermatch
.len
+ 1) {
335 /* We have a better match. Emit the deferred char,
336 * and defer this match. */
337 ctx
->literal(ctx
, (unsigned char) deferchr
);
338 defermatch
= matches
[0];
342 /* We don't have a better match. Do the deferred one. */
343 ctx
->match(ctx
, defermatch
.distance
, defermatch
.len
);
344 advance
= defermatch
.len
- 1;
348 /* There was no deferred match. Defer this one. */
349 defermatch
= matches
[0];
355 * We found no matches. Emit the deferred match, if
356 * any; otherwise emit a literal.
358 if (defermatch
.len
> 0) {
359 ctx
->match(ctx
, defermatch
.distance
, defermatch
.len
);
360 advance
= defermatch
.len
- 1;
363 ctx
->literal(ctx
, data
[0]);
369 * Now advance the position by `advance' characters,
370 * keeping the window and hash chains consistent.
372 while (advance
> 0) {
373 if (len
>= HASHCHARS
) {
374 lz77_advance(st
, *data
, lz77_hash(data
));
376 st
->pending
[st
->npending
++] = *data
;
385 /* ----------------------------------------------------------------------
386 * Deflate functionality common to both compression and decompression.
389 static const unsigned char lenlenmap
[] = {
390 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
393 #define MAXCODELEN 16
396 * Given a sequence of Huffman code lengths, compute the actual
397 * codes, in the final form suitable for feeding to outbits (i.e.
398 * already bit-mirrored).
400 * Returns the maximum code length found. Can also return -1 to
401 * indicate the table was overcommitted (too many or too short
402 * codes to exactly cover the possible space), or -2 to indicate it
403 * was undercommitted (too few or too long codes).
405 static int hufcodes(const unsigned char *lengths
, int *codes
, int nsyms
)
407 int count
[MAXCODELEN
], startcode
[MAXCODELEN
];
411 /* Count the codes of each length. */
413 for (i
= 1; i
< MAXCODELEN
; i
++)
415 for (i
= 0; i
< nsyms
; i
++) {
417 if (maxlen
< lengths
[i
])
420 /* Determine the starting code for each length block. */
422 for (i
= 1; i
< MAXCODELEN
; i
++) {
426 maxlen
= -1; /* overcommitted */
429 if (code
< (1 << MAXCODELEN
))
430 maxlen
= -2; /* undercommitted */
431 /* Determine the code for each symbol. Mirrored, of course. */
432 for (i
= 0; i
< nsyms
; i
++) {
433 code
= startcode
[lengths
[i
]]++;
435 for (j
= 0; j
< lengths
[i
]; j
++) {
436 codes
[i
] = (codes
[i
] << 1) | (code
& 1);
445 * Adler32 checksum function.
447 static unsigned long adler32_update(unsigned long s
,
448 const unsigned char *data
, int len
)
450 unsigned s1
= s
& 0xFFFF, s2
= (s
>> 16) & 0xFFFF;
453 for (i
= 0; i
< len
; i
++) {
462 return ((s2
% 65521) << 16) | (s1
% 65521);
466 * CRC32 checksum function.
469 static unsigned long crc32_update(unsigned long crcword
,
470 const unsigned char *data
, int len
)
472 static const unsigned long crc32_table
[256] = {
473 0x00000000L
, 0x77073096L
, 0xEE0E612CL
, 0x990951BAL
,
474 0x076DC419L
, 0x706AF48FL
, 0xE963A535L
, 0x9E6495A3L
,
475 0x0EDB8832L
, 0x79DCB8A4L
, 0xE0D5E91EL
, 0x97D2D988L
,
476 0x09B64C2BL
, 0x7EB17CBDL
, 0xE7B82D07L
, 0x90BF1D91L
,
477 0x1DB71064L
, 0x6AB020F2L
, 0xF3B97148L
, 0x84BE41DEL
,
478 0x1ADAD47DL
, 0x6DDDE4EBL
, 0xF4D4B551L
, 0x83D385C7L
,
479 0x136C9856L
, 0x646BA8C0L
, 0xFD62F97AL
, 0x8A65C9ECL
,
480 0x14015C4FL
, 0x63066CD9L
, 0xFA0F3D63L
, 0x8D080DF5L
,
481 0x3B6E20C8L
, 0x4C69105EL
, 0xD56041E4L
, 0xA2677172L
,
482 0x3C03E4D1L
, 0x4B04D447L
, 0xD20D85FDL
, 0xA50AB56BL
,
483 0x35B5A8FAL
, 0x42B2986CL
, 0xDBBBC9D6L
, 0xACBCF940L
,
484 0x32D86CE3L
, 0x45DF5C75L
, 0xDCD60DCFL
, 0xABD13D59L
,
485 0x26D930ACL
, 0x51DE003AL
, 0xC8D75180L
, 0xBFD06116L
,
486 0x21B4F4B5L
, 0x56B3C423L
, 0xCFBA9599L
, 0xB8BDA50FL
,
487 0x2802B89EL
, 0x5F058808L
, 0xC60CD9B2L
, 0xB10BE924L
,
488 0x2F6F7C87L
, 0x58684C11L
, 0xC1611DABL
, 0xB6662D3DL
,
489 0x76DC4190L
, 0x01DB7106L
, 0x98D220BCL
, 0xEFD5102AL
,
490 0x71B18589L
, 0x06B6B51FL
, 0x9FBFE4A5L
, 0xE8B8D433L
,
491 0x7807C9A2L
, 0x0F00F934L
, 0x9609A88EL
, 0xE10E9818L
,
492 0x7F6A0DBBL
, 0x086D3D2DL
, 0x91646C97L
, 0xE6635C01L
,
493 0x6B6B51F4L
, 0x1C6C6162L
, 0x856530D8L
, 0xF262004EL
,
494 0x6C0695EDL
, 0x1B01A57BL
, 0x8208F4C1L
, 0xF50FC457L
,
495 0x65B0D9C6L
, 0x12B7E950L
, 0x8BBEB8EAL
, 0xFCB9887CL
,
496 0x62DD1DDFL
, 0x15DA2D49L
, 0x8CD37CF3L
, 0xFBD44C65L
,
497 0x4DB26158L
, 0x3AB551CEL
, 0xA3BC0074L
, 0xD4BB30E2L
,
498 0x4ADFA541L
, 0x3DD895D7L
, 0xA4D1C46DL
, 0xD3D6F4FBL
,
499 0x4369E96AL
, 0x346ED9FCL
, 0xAD678846L
, 0xDA60B8D0L
,
500 0x44042D73L
, 0x33031DE5L
, 0xAA0A4C5FL
, 0xDD0D7CC9L
,
501 0x5005713CL
, 0x270241AAL
, 0xBE0B1010L
, 0xC90C2086L
,
502 0x5768B525L
, 0x206F85B3L
, 0xB966D409L
, 0xCE61E49FL
,
503 0x5EDEF90EL
, 0x29D9C998L
, 0xB0D09822L
, 0xC7D7A8B4L
,
504 0x59B33D17L
, 0x2EB40D81L
, 0xB7BD5C3BL
, 0xC0BA6CADL
,
505 0xEDB88320L
, 0x9ABFB3B6L
, 0x03B6E20CL
, 0x74B1D29AL
,
506 0xEAD54739L
, 0x9DD277AFL
, 0x04DB2615L
, 0x73DC1683L
,
507 0xE3630B12L
, 0x94643B84L
, 0x0D6D6A3EL
, 0x7A6A5AA8L
,
508 0xE40ECF0BL
, 0x9309FF9DL
, 0x0A00AE27L
, 0x7D079EB1L
,
509 0xF00F9344L
, 0x8708A3D2L
, 0x1E01F268L
, 0x6906C2FEL
,
510 0xF762575DL
, 0x806567CBL
, 0x196C3671L
, 0x6E6B06E7L
,
511 0xFED41B76L
, 0x89D32BE0L
, 0x10DA7A5AL
, 0x67DD4ACCL
,
512 0xF9B9DF6FL
, 0x8EBEEFF9L
, 0x17B7BE43L
, 0x60B08ED5L
,
513 0xD6D6A3E8L
, 0xA1D1937EL
, 0x38D8C2C4L
, 0x4FDFF252L
,
514 0xD1BB67F1L
, 0xA6BC5767L
, 0x3FB506DDL
, 0x48B2364BL
,
515 0xD80D2BDAL
, 0xAF0A1B4CL
, 0x36034AF6L
, 0x41047A60L
,
516 0xDF60EFC3L
, 0xA867DF55L
, 0x316E8EEFL
, 0x4669BE79L
,
517 0xCB61B38CL
, 0xBC66831AL
, 0x256FD2A0L
, 0x5268E236L
,
518 0xCC0C7795L
, 0xBB0B4703L
, 0x220216B9L
, 0x5505262FL
,
519 0xC5BA3BBEL
, 0xB2BD0B28L
, 0x2BB45A92L
, 0x5CB36A04L
,
520 0xC2D7FFA7L
, 0xB5D0CF31L
, 0x2CD99E8BL
, 0x5BDEAE1DL
,
521 0x9B64C2B0L
, 0xEC63F226L
, 0x756AA39CL
, 0x026D930AL
,
522 0x9C0906A9L
, 0xEB0E363FL
, 0x72076785L
, 0x05005713L
,
523 0x95BF4A82L
, 0xE2B87A14L
, 0x7BB12BAEL
, 0x0CB61B38L
,
524 0x92D28E9BL
, 0xE5D5BE0DL
, 0x7CDCEFB7L
, 0x0BDBDF21L
,
525 0x86D3D2D4L
, 0xF1D4E242L
, 0x68DDB3F8L
, 0x1FDA836EL
,
526 0x81BE16CDL
, 0xF6B9265BL
, 0x6FB077E1L
, 0x18B74777L
,
527 0x88085AE6L
, 0xFF0F6A70L
, 0x66063BCAL
, 0x11010B5CL
,
528 0x8F659EFFL
, 0xF862AE69L
, 0x616BFFD3L
, 0x166CCF45L
,
529 0xA00AE278L
, 0xD70DD2EEL
, 0x4E048354L
, 0x3903B3C2L
,
530 0xA7672661L
, 0xD06016F7L
, 0x4969474DL
, 0x3E6E77DBL
,
531 0xAED16A4AL
, 0xD9D65ADCL
, 0x40DF0B66L
, 0x37D83BF0L
,
532 0xA9BCAE53L
, 0xDEBB9EC5L
, 0x47B2CF7FL
, 0x30B5FFE9L
,
533 0xBDBDF21CL
, 0xCABAC28AL
, 0x53B39330L
, 0x24B4A3A6L
,
534 0xBAD03605L
, 0xCDD70693L
, 0x54DE5729L
, 0x23D967BFL
,
535 0xB3667A2EL
, 0xC4614AB8L
, 0x5D681B02L
, 0x2A6F2B94L
,
536 0xB40BBE37L
, 0xC30C8EA1L
, 0x5A05DF1BL
, 0x2D02EF8DL
538 crcword
^= 0xFFFFFFFFL
;
540 unsigned long newbyte
= *data
++;
541 newbyte
^= crcword
& 0xFFL
;
542 crcword
= (crcword
>> 8) ^ crc32_table
[newbyte
];
544 return crcword
^ 0xFFFFFFFFL
;
548 short code
, extrabits
;
552 static const coderecord lencodes
[] = {
584 static const coderecord distcodes
[] = {
607 {22, 10, 2049, 3072},
608 {23, 10, 3073, 4096},
609 {24, 11, 4097, 6144},
610 {25, 11, 6145, 8192},
611 {26, 12, 8193, 12288},
612 {27, 12, 12289, 16384},
613 {28, 13, 16385, 24576},
614 {29, 13, 24577, 32768},
617 /* ----------------------------------------------------------------------
618 * Deflate compression.
621 #define SYMLIMIT 65536
622 #define SYMPFX_LITLEN 0x00000000U
623 #define SYMPFX_DIST 0x40000000U
624 #define SYMPFX_EXTRABITS 0x80000000U
625 #define SYMPFX_CODELEN 0xC0000000U
626 #define SYMPFX_MASK 0xC0000000U
628 #define SYM_EXTRABITS_MASK 0x3C000000U
629 #define SYM_EXTRABITS_SHIFT 26
632 unsigned char *len_litlen
;
634 unsigned char *len_dist
;
636 unsigned char *len_codelen
;
640 struct deflate_compress_ctx
{
641 struct LZ77Context
*lzc
;
642 unsigned char *outbuf
;
644 unsigned long outbits
;
650 unsigned long checksum
;
651 unsigned long datasize
;
654 unsigned char static_len1
[286], static_len2
[30];
655 int static_code1
[286], static_code2
[30];
658 unsigned long bitcount
;
662 static void outbits(deflate_compress_ctx
*out
,
663 unsigned long bits
, int nbits
)
665 assert(out
->noutbits
+ nbits
<= 32);
666 out
->outbits
|= bits
<< out
->noutbits
;
667 out
->noutbits
+= nbits
;
668 while (out
->noutbits
>= 8) {
669 if (out
->outlen
>= out
->outsize
) {
670 out
->outsize
= out
->outlen
+ 64;
671 out
->outbuf
= sresize(out
->outbuf
, out
->outsize
, unsigned char);
673 out
->outbuf
[out
->outlen
++] = (unsigned char) (out
->outbits
& 0xFF);
678 out
->bitcount
+= nbits
;
683 * Binary heap functions used by buildhuf(). Each one assumes the
684 * heap to be stored in an array of ints, with two ints per node
685 * (user data and key). They take in the old heap length, and
686 * return the new one.
688 #define HEAPPARENT(x) (((x)-2)/4*2)
689 #define HEAPLEFT(x) ((x)*2+2)
690 #define HEAPRIGHT(x) ((x)*2+4)
691 static int addheap(int *heap
, int len
, int userdata
, int key
)
696 heap
[len
++] = userdata
;
700 dad
= HEAPPARENT(me
);
701 if (heap
[me
+1] < heap
[dad
+1]) {
702 tmp
= heap
[me
]; heap
[me
] = heap
[dad
]; heap
[dad
] = tmp
;
703 tmp
= heap
[me
+1]; heap
[me
+1] = heap
[dad
+1]; heap
[dad
+1] = tmp
;
711 static int rmheap(int *heap
, int len
, int *userdata
, int *key
)
713 int me
, lc
, rc
, c
, tmp
;
719 heap
[1] = heap
[len
+1];
728 else if (rc
>= len
|| heap
[lc
+1] < heap
[rc
+1])
732 if (heap
[me
+1] > heap
[c
+1]) {
733 tmp
= heap
[me
]; heap
[me
] = heap
[c
]; heap
[c
] = tmp
;
734 tmp
= heap
[me
+1]; heap
[me
+1] = heap
[c
+1]; heap
[c
+1] = tmp
;
744 * The core of the Huffman algorithm: takes an input array of
745 * symbol frequencies, and produces an output array of code
748 * This is basically a generic Huffman implementation, but it has
749 * one zlib-related quirk which is that it caps the output code
750 * lengths to fit in an unsigned char (which is safe since Deflate
751 * will reject anything longer than 15 anyway). Anyone wanting to
752 * rip it out and use it in another context should find that easy
756 static void buildhuf(const int *freqs
, unsigned char *lengths
, int nsyms
)
758 int parent
[2*HUFMAX
-1];
759 int length
[2*HUFMAX
-1];
765 assert(nsyms
<= HUFMAX
);
767 memset(parent
, 0, sizeof(parent
));
770 * Begin by building the heap.
773 for (i
= 0; i
< nsyms
; i
++)
774 if (freqs
[i
] > 0) /* leave unused symbols out totally */
775 heapsize
= addheap(heap
, heapsize
, i
, freqs
[i
]);
778 * Now repeatedly take two elements off the heap and merge
782 while (heapsize
> 2) {
783 heapsize
= rmheap(heap
, heapsize
, &i
, &si
);
784 heapsize
= rmheap(heap
, heapsize
, &j
, &sj
);
787 heapsize
= addheap(heap
, heapsize
, n
, si
+ sj
);
792 * Now we have our tree, in the form of a link from each node
793 * to the index of its parent. Count back down the tree to
794 * determine the code lengths.
796 memset(length
, 0, sizeof(length
));
797 /* The tree root has length 0 after that, which is correct. */
800 length
[i
] = 1 + length
[parent
[i
]];
803 * And that's it. (Simple, wasn't it?) Copy the lengths into
804 * the output array and leave.
806 * Here we cap lengths to fit in unsigned char.
808 for (i
= 0; i
< nsyms
; i
++)
809 lengths
[i
] = (length
[i
] > 255 ?
255 : length
[i
]);
813 * Wrapper around buildhuf() which enforces the Deflate restriction
814 * that no code length may exceed 15 bits, or 7 for the auxiliary
815 * code length alphabet. This function has the same calling
816 * semantics as buildhuf(), except that it might modify the freqs
819 static void deflate_buildhuf(int *freqs
, unsigned char *lengths
,
820 int nsyms
, int limit
)
822 int smallestfreq
, totalfreq
, nactivesyms
;
823 int num
, denom
, adjust
;
828 * Nasty special case: if the frequency table has fewer than
829 * two non-zero elements, we must invent some, because we can't
830 * have fewer than one bit encoding a symbol.
835 for (i
= 0; i
< nsyms
; i
++)
839 for (i
= 0; i
< nsyms
&& count
> 0; i
++)
848 * First, try building the Huffman table the normal way. If
849 * this works, it's optimal, so we don't want to mess with it.
851 buildhuf(freqs
, lengths
, nsyms
);
853 for (i
= 0; i
< nsyms
; i
++)
854 if (lengths
[i
] > limit
)
861 * The Huffman algorithm can only ever generate a code length
862 * of N bits or more if there is a symbol whose probability is
863 * less than the reciprocal of the (N+2)th Fibonacci number
864 * (counting from F_0=0 and F_1=1), i.e. 1/2584 for N=16, or
865 * 1/55 for N=8. (This is a necessary though not sufficient
868 * Why is this? Well, consider the input symbol with the
869 * smallest probability. Let that probability be x. In order
870 * for this symbol to have a code length of at least 1, the
871 * Huffman algorithm will have to merge it with some other
872 * node; and since x is the smallest probability, the node it
873 * gets merged with must be at least x. Thus, the probability
874 * of the resulting combined node will be at least 2x. Now in
875 * order for our node to reach depth 2, this 2x-node must be
876 * merged again. But what with? We can't assume the node it
877 * merges with is at least 2x, because this one might only be
878 * the _second_ smallest remaining node. But we do know the
879 * node it merges with must be at least x, so our order-2
880 * internal node is at least 3x.
882 * How small a node can merge with _that_ to get an order-3
883 * internal node? Well, it must be at least 2x, because if it
884 * was smaller than that then it would have been one of the two
885 * smallest nodes in the previous step and been merged at that
886 * point. So at least 3x, plus at least 2x, comes to at least
887 * 5x for an order-3 node.
889 * And so it goes on: at every stage we must merge our current
890 * node with a node at least as big as the bigger of this one's
891 * two parents, and from this starting point that gives rise to
892 * the Fibonacci sequence. So we find that in order to have a
893 * node n levels deep (i.e. a maximum code length of n), the
894 * overall probability of the root of the entire tree must be
895 * at least F_{n+2} times the probability of the rarest symbol.
896 * In other words, since the overall probability is 1, it is a
897 * necessary condition for a code length of 16 or more that
898 * there must be at least one symbol with probability <=
901 * (To demonstrate that a probability this big really can give
902 * rise to a code length of 16, consider the set of input
903 * frequencies { 1-epsilon, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
904 * 89, 144, 233, 377, 610, 987 }, for arbitrarily small
907 * So here buildhuf() has returned us an overlong code. So to
908 * ensure it doesn't do it again, we add a constant to all the
909 * (non-zero) symbol frequencies, causing them to become more
910 * balanced and removing the danger. We can then feed the
911 * results back to the standard buildhuf() and be
912 * assert()-level confident that the resulting code lengths
913 * contain nothing outside the permitted range.
915 maxprob
= (limit
== 16 ?
2584 : 55); /* no point in computing full F_n */
916 totalfreq
= nactivesyms
= 0;
918 for (i
= 0; i
< nsyms
; i
++) {
921 if (smallestfreq
< 0 || smallestfreq
> freqs
[i
])
922 smallestfreq
= freqs
[i
];
923 totalfreq
+= freqs
[i
];
926 assert(smallestfreq
<= totalfreq
/ maxprob
);
929 * We want to find the smallest integer `adjust' such that
930 * (totalfreq + nactivesyms * adjust) / (smallestfreq +
931 * adjust) is less than maxprob. A bit of algebra tells us
932 * that the threshold value is equal to
934 * totalfreq - maxprob * smallestfreq
935 * ----------------------------------
936 * maxprob - nactivesyms
938 * rounded up, of course. And we'll only even be trying
941 num
= totalfreq
- smallestfreq
* maxprob
;
942 denom
= maxprob
- nactivesyms
;
943 adjust
= (num
+ denom
- 1) / denom
;
946 * Now add `adjust' to all the input symbol frequencies.
948 for (i
= 0; i
< nsyms
; i
++)
953 * Rebuild the Huffman tree...
955 buildhuf(freqs
, lengths
, nsyms
);
958 * ... and this time it ought to be OK.
960 for (i
= 0; i
< nsyms
; i
++)
961 assert(lengths
[i
] <= limit
);
965 * Compute the bit length of a symbol, given the three Huffman
968 static int symsize(unsigned sym
, const struct huftrees
*trees
)
970 unsigned basesym
= sym
&~ SYMPFX_MASK
;
972 switch (sym
& SYMPFX_MASK
) {
974 return trees
->len_litlen
[basesym
];
976 return trees
->len_dist
[basesym
];
978 return trees
->len_codelen
[basesym
];
979 default /*case SYMPFX_EXTRABITS*/:
980 return basesym
>> SYM_EXTRABITS_SHIFT
;
985 * Write out a single symbol, given the three Huffman trees.
987 static void writesym(deflate_compress_ctx
*out
,
988 unsigned sym
, const struct huftrees
*trees
)
990 unsigned basesym
= sym
&~ SYMPFX_MASK
;
993 switch (sym
& SYMPFX_MASK
) {
995 debug(("send: litlen %d\n", basesym
));
996 outbits(out
, trees
->code_litlen
[basesym
], trees
->len_litlen
[basesym
]);
999 debug(("send: dist %d\n", basesym
));
1000 outbits(out
, trees
->code_dist
[basesym
], trees
->len_dist
[basesym
]);
1002 case SYMPFX_CODELEN
:
1003 debug(("send: codelen %d\n", basesym
));
1004 outbits(out
, trees
->code_codelen
[basesym
],trees
->len_codelen
[basesym
]);
1006 case SYMPFX_EXTRABITS
:
1007 i
= basesym
>> SYM_EXTRABITS_SHIFT
;
1008 basesym
&= ~SYM_EXTRABITS_MASK
;
1009 debug(("send: extrabits %d/%d\n", basesym
, i
));
1010 outbits(out
, basesym
, i
);
1016 * outblock() must output _either_ a dynamic block of length
1017 * `dynamic_len', _or_ a static block of length `static_len', but
1018 * it gets to choose which.
1020 static void outblock(deflate_compress_ctx
*out
,
1021 int dynamic_len
, int static_len
)
1023 int freqs1
[286], freqs2
[30], freqs3
[19];
1024 unsigned char len1
[286], len2
[30], len3
[19];
1025 int code1
[286], code2
[30], code3
[19];
1026 int hlit
, hdist
, hclen
, bfinal
, btype
;
1027 int treesrc
[286 + 30];
1028 int treesyms
[286 + 30];
1030 int i
, ntreesrc
, ntreesyms
;
1031 int dynamic
, blklen
;
1032 struct huftrees dht
;
1033 const struct huftrees
*ht
;
1035 unsigned long bitcount_before
;
1038 dht
.len_litlen
= len1
;
1039 dht
.len_dist
= len2
;
1040 dht
.len_codelen
= len3
;
1041 dht
.code_litlen
= code1
;
1042 dht
.code_dist
= code2
;
1043 dht
.code_codelen
= code3
;
1046 * We make our choice of block to output by doing all the
1047 * detailed work to determine the exact length of each possible
1048 * block. Then we choose the one which has fewest output bits
1053 * First build the two main Huffman trees for the dynamic
1058 * Count up the frequency tables.
1060 memset(freqs1
, 0, sizeof(freqs1
));
1061 memset(freqs2
, 0, sizeof(freqs2
));
1062 freqs1
[256] = 1; /* we're bound to need one EOB */
1063 for (i
= 0; i
< dynamic_len
; i
++) {
1064 unsigned sym
= out
->syms
[(out
->symstart
+ i
) % SYMLIMIT
];
1067 * Increment the occurrence counter for this symbol, if
1068 * it's in one of the Huffman alphabets and isn't extra
1071 if ((sym
& SYMPFX_MASK
) == SYMPFX_LITLEN
) {
1072 sym
&= ~SYMPFX_MASK
;
1073 assert(sym
< lenof(freqs1
));
1075 } else if ((sym
& SYMPFX_MASK
) == SYMPFX_DIST
) {
1076 sym
&= ~SYMPFX_MASK
;
1077 assert(sym
< lenof(freqs2
));
1081 deflate_buildhuf(freqs1
, len1
, lenof(freqs1
), 15);
1082 deflate_buildhuf(freqs2
, len2
, lenof(freqs2
), 15);
1083 hufcodes(len1
, code1
, lenof(freqs1
));
1084 hufcodes(len2
, code2
, lenof(freqs2
));
1087 * Determine HLIT and HDIST.
1089 for (hlit
= 286; hlit
> 257 && len1
[hlit
-1] == 0; hlit
--);
1090 for (hdist
= 30; hdist
> 1 && len2
[hdist
-1] == 0; hdist
--);
1093 * Write out the list of symbols used to transmit the
1097 for (i
= 0; i
< hlit
; i
++)
1098 treesrc
[ntreesrc
++] = len1
[i
];
1099 for (i
= 0; i
< hdist
; i
++)
1100 treesrc
[ntreesrc
++] = len2
[i
];
1102 for (i
= 0; i
< ntreesrc
;) {
1106 /* Find length of run of the same length code. */
1107 while (i
+j
< ntreesrc
&& treesrc
[i
+j
] == treesrc
[i
])
1110 /* Encode that run as economically as we can. */
1112 if (treesrc
[i
] == 0) {
1114 * Zero code length: we can output run codes for
1115 * 3-138 zeroes. So if we have fewer than 3 zeroes,
1116 * we just output literals. Otherwise, we output
1117 * nothing but run codes, and tweak their lengths
1118 * to make sure we aren't left with under 3 at the
1123 treesyms
[ntreesyms
++] = 0 | SYMPFX_CODELEN
;
1126 int rpt
= (k
< 138 ? k
: 138);
1127 if (rpt
> k
-3 && rpt
< k
)
1129 assert(rpt
>= 3 && rpt
<= 138);
1131 treesyms
[ntreesyms
++] = 17 | SYMPFX_CODELEN
;
1132 treesyms
[ntreesyms
++] =
1133 (SYMPFX_EXTRABITS
| (rpt
- 3) |
1134 (3 << SYM_EXTRABITS_SHIFT
));
1136 treesyms
[ntreesyms
++] = 18 | SYMPFX_CODELEN
;
1137 treesyms
[ntreesyms
++] =
1138 (SYMPFX_EXTRABITS
| (rpt
- 11) |
1139 (7 << SYM_EXTRABITS_SHIFT
));
1146 * Non-zero code length: we must output the first
1147 * one explicitly, then we can output a copy code
1148 * for 3-6 repeats. So if we have fewer than 4
1149 * repeats, we _just_ output literals. Otherwise,
1150 * we output one literal plus at least one copy
1151 * code, and tweak the copy codes to make sure we
1152 * aren't left with under 3 at the end.
1154 assert(treesrc
[i
] < 16);
1155 treesyms
[ntreesyms
++] = treesrc
[i
] | SYMPFX_CODELEN
;
1159 treesyms
[ntreesyms
++] = treesrc
[i
] | SYMPFX_CODELEN
;
1162 int rpt
= (k
< 6 ? k
: 6);
1163 if (rpt
> k
-3 && rpt
< k
)
1165 assert(rpt
>= 3 && rpt
<= 6);
1166 treesyms
[ntreesyms
++] = 16 | SYMPFX_CODELEN
;
1167 treesyms
[ntreesyms
++] = (SYMPFX_EXTRABITS
| (rpt
- 3) |
1168 (2 << SYM_EXTRABITS_SHIFT
));
1176 assert((unsigned)ntreesyms
< lenof(treesyms
));
1179 * Count up the frequency table for the tree-transmission
1180 * symbols, and build the auxiliary Huffman tree for that.
1182 memset(freqs3
, 0, sizeof(freqs3
));
1183 for (i
= 0; i
< ntreesyms
; i
++) {
1184 unsigned sym
= treesyms
[i
];
1187 * Increment the occurrence counter for this symbol, if
1188 * it's the Huffman alphabet and isn't extra bits.
1190 if ((sym
& SYMPFX_MASK
) == SYMPFX_CODELEN
) {
1191 sym
&= ~SYMPFX_MASK
;
1192 assert(sym
< lenof(freqs3
));
1196 deflate_buildhuf(freqs3
, len3
, lenof(freqs3
), 7);
1197 hufcodes(len3
, code3
, lenof(freqs3
));
1200 * Reorder the code length codes into transmission order, and
1203 for (i
= 0; i
< 19; i
++)
1204 codelen
[i
] = len3
[lenlenmap
[i
]];
1205 for (hclen
= 19; hclen
> 4 && codelen
[hclen
-1] == 0; hclen
--);
1208 * Now work out the exact size of both the dynamic and the
1209 * static block, in bits.
1215 * First the dynamic block.
1217 dsize
= 3 + 5 + 5 + 4; /* 3-bit header, HLIT, HDIST, HCLEN */
1218 dsize
+= 3 * hclen
; /* code-length-alphabet code lengths */
1220 for (i
= 0; i
< ntreesyms
; i
++)
1221 dsize
+= symsize(treesyms
[i
], &dht
);
1222 /* The actual block data */
1223 for (i
= 0; i
< dynamic_len
; i
++) {
1224 unsigned sym
= out
->syms
[(out
->symstart
+ i
) % SYMLIMIT
];
1225 dsize
+= symsize(sym
, &dht
);
1227 /* And the end-of-data symbol. */
1228 dsize
+= symsize(SYMPFX_LITLEN
| 256, &dht
);
1231 * Now the static block.
1233 ssize
= 3; /* 3-bit block header */
1234 /* The actual block data */
1235 for (i
= 0; i
< static_len
; i
++) {
1236 unsigned sym
= out
->syms
[(out
->symstart
+ i
) % SYMLIMIT
];
1237 ssize
+= symsize(sym
, &out
->sht
);
1239 /* And the end-of-data symbol. */
1240 ssize
+= symsize(SYMPFX_LITLEN
| 256, &out
->sht
);
1243 * Compare the two and decide which to output. We break
1244 * exact ties in favour of the static block, because of the
1245 * special case in which that block has zero length.
1247 dynamic
= ((double)ssize
* dynamic_len
> (double)dsize
* static_len
);
1248 ht
= dynamic ?
&dht
: &out
->sht
;
1249 blklen
= dynamic ? dynamic_len
: static_len
;
1253 * Actually transmit the block.
1256 /* 3-bit block header */
1257 bfinal
= (out
->lastblock ?
1 : 0);
1258 btype
= dynamic ?
2 : 1;
1259 debug(("send: bfinal=%d btype=%d\n", bfinal
, btype
));
1260 outbits(out
, bfinal
, 1);
1261 outbits(out
, btype
, 2);
1264 bitcount_before
= out
->bitcount
;
1268 /* HLIT, HDIST and HCLEN */
1269 debug(("send: hlit=%d hdist=%d hclen=%d\n", hlit
, hdist
, hclen
));
1270 outbits(out
, hlit
- 257, 5);
1271 outbits(out
, hdist
- 1, 5);
1272 outbits(out
, hclen
- 4, 4);
1274 /* Code lengths for the auxiliary tree */
1275 for (i
= 0; i
< hclen
; i
++) {
1276 debug(("send: lenlen %d\n", codelen
[i
]));
1277 outbits(out
, codelen
[i
], 3);
1280 /* Code lengths for the literal/length and distance trees */
1281 for (i
= 0; i
< ntreesyms
; i
++)
1282 writesym(out
, treesyms
[i
], ht
);
1284 fprintf(stderr
, "total tree size %lu bits\n",
1285 out
->bitcount
- bitcount_before
);
1289 /* Output the actual symbols from the buffer */
1290 for (i
= 0; i
< blklen
; i
++) {
1291 unsigned sym
= out
->syms
[(out
->symstart
+ i
) % SYMLIMIT
];
1292 writesym(out
, sym
, ht
);
1295 /* Output the end-of-data symbol */
1296 writesym(out
, SYMPFX_LITLEN
| 256, ht
);
1299 * Remove all the just-output symbols from the symbol buffer by
1300 * adjusting symstart and nsyms.
1302 out
->symstart
= (out
->symstart
+ blklen
) % SYMLIMIT
;
1303 out
->nsyms
-= blklen
;
1307 * Give the approximate log-base-2 of an input integer, measured in
1308 * 8ths of a bit. (I.e. this computes an integer approximation to
1311 static int approxlog2(unsigned x
)
1316 * Binary-search to get the top bit of x up to bit 31.
1318 if (x
< 0x00010000U
) x
<<= 16, ret
-= 16*8;
1319 if (x
< 0x01000000U
) x
<<= 8, ret
-= 8*8;
1320 if (x
< 0x10000000U
) x
<<= 4, ret
-= 4*8;
1321 if (x
< 0x40000000U
) x
<<= 2, ret
-= 2*8;
1322 if (x
< 0x80000000U
) x
<<= 1, ret
-= 1*8;
1325 * Now we know the logarithm we want is in [ret,ret+1).
1326 * Determine the bottom three bits by checking against
1329 * (Each of these threshold values is 0x80000000 times an odd
1330 * power of 2^(1/16). Therefore, this function rounds to
1333 if (x
<= 0xAD583EEAU
) {
1334 if (x
<= 0x91C3D373U
)
1335 ret
+= (x
<= 0x85AAC367U ?
0 : 1);
1337 ret
+= (x
<= 0x9EF53260U ?
2 : 3);
1339 if (x
<= 0xCE248C15U
)
1340 ret
+= (x
<= 0xBD08A39FU ?
4 : 5);
1342 ret
+= (x
<= 0xE0CCDEECU ?
6 : x
<= 0xF5257D15L ?
7 : 8);
1348 static void chooseblock(deflate_compress_ctx
*out
)
1350 int freqs1
[286], freqs2
[30];
1351 int i
, len
, bestlen
, longestlen
= 0;
1355 memset(freqs1
, 0, sizeof(freqs1
));
1356 memset(freqs2
, 0, sizeof(freqs2
));
1357 freqs1
[256] = 1; /* we're bound to need one EOB */
1362 * Iterate over all possible block lengths, computing the
1363 * entropic coding approximation to the final length at every
1364 * stage. We divide the result by the number of symbols
1365 * encoded, to determine the `value for money' (overall
1366 * bits-per-symbol count) of a block of that length.
1371 len
= 300 * 8; /* very approximate size of the Huffman trees */
1373 for (i
= 0; i
< out
->nsyms
; i
++) {
1374 unsigned sym
= out
->syms
[(out
->symstart
+ i
) % SYMLIMIT
];
1376 if (i
> 0 && (sym
& SYMPFX_MASK
) == SYMPFX_LITLEN
) {
1378 * This is a viable point at which to end the block.
1379 * Compute the value for money.
1381 int vfm
= i
* 32768 / len
; /* symbols encoded per bit */
1383 if (bestlen
< 0 || vfm
> bestvfm
) {
1392 * Increment the occurrence counter for this symbol, if
1393 * it's in one of the Huffman alphabets and isn't extra
1396 if ((sym
& SYMPFX_MASK
) == SYMPFX_LITLEN
) {
1397 sym
&= ~SYMPFX_MASK
;
1398 assert(sym
< lenof(freqs1
));
1399 len
+= freqs1
[sym
] * approxlog2(freqs1
[sym
]);
1400 len
-= total1
* approxlog2(total1
);
1403 len
-= freqs1
[sym
] * approxlog2(freqs1
[sym
]);
1404 len
+= total1
* approxlog2(total1
);
1405 } else if ((sym
& SYMPFX_MASK
) == SYMPFX_DIST
) {
1406 sym
&= ~SYMPFX_MASK
;
1407 assert(sym
< lenof(freqs2
));
1408 len
+= freqs2
[sym
] * approxlog2(freqs2
[sym
]);
1409 len
-= total2
* approxlog2(total2
);
1412 len
-= freqs2
[sym
] * approxlog2(freqs2
[sym
]);
1413 len
+= total2
* approxlog2(total2
);
1414 } else if ((sym
& SYMPFX_MASK
) == SYMPFX_EXTRABITS
) {
1415 len
+= 8 * ((sym
&~ SYMPFX_MASK
) >> SYM_EXTRABITS_SHIFT
);
1419 assert(bestlen
> 0);
1421 outblock(out
, bestlen
, longestlen
);
1425 * Force the current symbol buffer to be flushed out as a single
1428 static void flushblock(deflate_compress_ctx
*out
)
1431 * No need to check that out->nsyms is a valid block length: we
1432 * know it has to be, because flushblock() is called in between
1433 * two matches/literals.
1435 outblock(out
, out
->nsyms
, out
->nsyms
);
1436 assert(out
->nsyms
== 0);
1440 * Place a symbol into the symbols buffer.
1442 static void outsym(deflate_compress_ctx
*out
, unsigned long sym
)
1444 assert(out
->nsyms
< SYMLIMIT
);
1445 out
->syms
[(out
->symstart
+ out
->nsyms
++) % SYMLIMIT
] = sym
;
1447 if (out
->nsyms
== SYMLIMIT
)
1451 static void literal(struct LZ77Context
*ectx
, unsigned char c
)
1453 deflate_compress_ctx
*out
= (deflate_compress_ctx
*) ectx
->userdata
;
1455 outsym(out
, SYMPFX_LITLEN
| c
);
1458 static void match(struct LZ77Context
*ectx
, int distance
, int len
)
1460 const coderecord
*d
, *l
;
1462 deflate_compress_ctx
*out
= (deflate_compress_ctx
*) ectx
->userdata
;
1468 * We can transmit matches of lengths 3 through 258
1469 * inclusive. So if len exceeds 258, we must transmit in
1470 * several steps, with 258 or less in each step.
1472 * Specifically: if len >= 261, we can transmit 258 and be
1473 * sure of having at least 3 left for the next step. And if
1474 * len <= 258, we can just transmit len. But if len == 259
1475 * or 260, we must transmit len-3.
1477 thislen
= (len
> 260 ?
258 : len
<= 258 ? len
: len
- 3);
1481 * Binary-search to find which length code we're
1485 j
= sizeof(lencodes
) / sizeof(*lencodes
);
1489 if (thislen
< lencodes
[k
].min
)
1491 else if (thislen
> lencodes
[k
].max
)
1495 break; /* found it! */
1500 * Transmit the length code.
1502 outsym(out
, SYMPFX_LITLEN
| l
->code
);
1505 * Transmit the extra bits.
1508 outsym(out
, (SYMPFX_EXTRABITS
| (thislen
- l
->min
) |
1509 (l
->extrabits
<< SYM_EXTRABITS_SHIFT
)));
1513 * Binary-search to find which distance code we're
1517 j
= sizeof(distcodes
) / sizeof(*distcodes
);
1521 if (distance
< distcodes
[k
].min
)
1523 else if (distance
> distcodes
[k
].max
)
1527 break; /* found it! */
1532 * Write the distance code.
1534 outsym(out
, SYMPFX_DIST
| d
->code
);
1537 * Transmit the extra bits.
1540 outsym(out
, (SYMPFX_EXTRABITS
| (distance
- d
->min
) |
1541 (d
->extrabits
<< SYM_EXTRABITS_SHIFT
)));
1546 deflate_compress_ctx
*deflate_compress_new(int type
)
1548 deflate_compress_ctx
*out
;
1549 struct LZ77Context
*ectx
= snew(struct LZ77Context
);
1552 ectx
->literal
= literal
;
1553 ectx
->match
= match
;
1555 out
= snew(deflate_compress_ctx
);
1557 out
->outbits
= out
->noutbits
= 0;
1558 out
->firstblock
= TRUE
;
1563 out
->syms
= snewn(SYMLIMIT
, unsigned long);
1564 out
->symstart
= out
->nsyms
= 0;
1566 out
->checksum
= (type
== DEFLATE_TYPE_ZLIB ?
1 : 0);
1568 out
->lastblock
= FALSE
;
1569 out
->finished
= FALSE
;
1572 * Build the static Huffman tables now, so we'll have them
1573 * available every time outblock() is called.
1578 for (i
= 0; i
< lenof(out
->static_len1
); i
++)
1579 out
->static_len1
[i
] = (i
< 144 ?
8 :
1582 for (i
= 0; i
< lenof(out
->static_len2
); i
++)
1583 out
->static_len2
[i
] = 5;
1585 hufcodes(out
->static_len1
, out
->static_code1
, lenof(out
->static_code1
));
1586 hufcodes(out
->static_len2
, out
->static_code2
, lenof(out
->static_code2
));
1587 out
->sht
.len_litlen
= out
->static_len1
;
1588 out
->sht
.len_dist
= out
->static_len2
;
1589 out
->sht
.len_codelen
= NULL
;
1590 out
->sht
.code_litlen
= out
->static_code1
;
1591 out
->sht
.code_dist
= out
->static_code2
;
1592 out
->sht
.code_codelen
= NULL
;
1594 ectx
->userdata
= out
;
1600 void deflate_compress_free(deflate_compress_ctx
*out
)
1602 struct LZ77Context
*ectx
= out
->lzc
;
1610 void deflate_compress_data(deflate_compress_ctx
*out
,
1611 const void *vblock
, int len
, int flushtype
,
1612 void **outblock
, int *outlen
)
1614 struct LZ77Context
*ectx
= out
->lzc
;
1615 const unsigned char *block
= (const unsigned char *)vblock
;
1617 assert(!out
->finished
);
1620 out
->outlen
= out
->outsize
= 0;
1623 * If this is the first block, output the header.
1625 if (out
->firstblock
) {
1626 switch (out
->type
) {
1627 case DEFLATE_TYPE_BARE
:
1628 break; /* no header */
1629 case DEFLATE_TYPE_ZLIB
:
1631 * zlib (RFC1950) header bytes: 78 9C. (Deflate
1632 * compression, 32K window size, default algorithm.)
1634 outbits(out
, 0x9C78, 16);
1636 case DEFLATE_TYPE_GZIP
:
1638 * Minimal gzip (RFC1952) header:
1640 * - basic header of 1F 8B
1641 * - compression method byte (8 = deflate)
1642 * - flags byte (zero: we use no optional features)
1643 * - modification time (zero: no time stamp available)
1644 * - extra flags byte (2: we use maximum compression
1646 * - operating system byte (255: we do not specify)
1648 outbits(out
, 0x00088B1F, 32); /* header, CM, flags */
1649 outbits(out
, 0, 32); /* mtime */
1650 outbits(out
, 0xFF02, 16); /* xflags, OS */
1653 out
->firstblock
= FALSE
;
1657 * Feed our data to the LZ77 compression phase.
1659 lz77_compress(ectx
, block
, len
, TRUE
);
1662 * Update checksums and counters.
1664 switch (out
->type
) {
1665 case DEFLATE_TYPE_ZLIB
:
1666 out
->checksum
= adler32_update(out
->checksum
, block
, len
);
1668 case DEFLATE_TYPE_GZIP
:
1669 out
->checksum
= crc32_update(out
->checksum
, block
, len
);
1672 out
->datasize
+= len
;
1674 switch (flushtype
) {
1676 * FIXME: what other flush types are available and useful?
1677 * In PuTTY, it was clear that we generally wanted to be in
1678 * a static block so it was safe to open one. Here, we
1679 * probably prefer to be _outside_ a block if we can. Think
1682 case DEFLATE_NO_FLUSH
:
1683 break; /* don't flush any data at all (duh) */
1684 case DEFLATE_SYNC_FLUSH
:
1686 * Close the current block.
1691 * Then output an empty _uncompressed_ block: send 000,
1692 * then sync to byte boundary, then send bytes 00 00 FF
1697 outbits(out
, 0, 8 - out
->noutbits
);
1698 outbits(out
, 0, 16);
1699 outbits(out
, 0xFFFF, 16);
1701 case DEFLATE_END_OF_DATA
:
1703 * Output a block with BFINAL set.
1705 out
->lastblock
= TRUE
;
1709 * Sync to byte boundary, flushing out the final byte.
1712 outbits(out
, 0, 8 - out
->noutbits
);
1715 * Format-specific trailer data.
1717 switch (out
->type
) {
1718 case DEFLATE_TYPE_ZLIB
:
1720 * Just write out the Adler32 checksum.
1722 outbits(out
, (out
->checksum
>> 24) & 0xFF, 8);
1723 outbits(out
, (out
->checksum
>> 16) & 0xFF, 8);
1724 outbits(out
, (out
->checksum
>> 8) & 0xFF, 8);
1725 outbits(out
, (out
->checksum
>> 0) & 0xFF, 8);
1727 case DEFLATE_TYPE_GZIP
:
1729 * Write out the CRC32 checksum and the data length.
1731 outbits(out
, out
->checksum
, 32);
1732 outbits(out
, out
->datasize
, 32);
1736 out
->finished
= TRUE
;
1741 * Return any data that we've generated.
1743 *outblock
= (void *)out
->outbuf
;
1744 *outlen
= out
->outlen
;
1747 /* ----------------------------------------------------------------------
1748 * Deflate decompression.
1752 * The way we work the Huffman decode is to have a table lookup on
1753 * the first N bits of the input stream (in the order they arrive,
1754 * of course, i.e. the first bit of the Huffman code is in bit 0).
1755 * Each table entry lists the number of bits to consume, plus
1756 * either an output code or a pointer to a secondary table.
1762 unsigned char nbits
;
1764 struct table
*nexttable
;
1768 int mask
; /* mask applied to input bit stream */
1769 struct tableentry
*table
;
1774 #define DWINSIZE 32768
1777 * Build a single-level decode table for elements
1778 * [minlength,maxlength) of the provided code/length tables, and
1779 * recurse to build subtables.
1781 static struct table
*mkonetab(int *codes
, unsigned char *lengths
, int nsyms
,
1782 int pfx
, int pfxbits
, int bits
)
1784 struct table
*tab
= snew(struct table
);
1785 int pfxmask
= (1 << pfxbits
) - 1;
1786 int nbits
, i
, j
, code
;
1788 tab
->table
= snewn(1 << bits
, struct tableentry
);
1789 tab
->mask
= (1 << bits
) - 1;
1791 for (code
= 0; code
<= tab
->mask
; code
++) {
1792 tab
->table
[code
].code
= -1;
1793 tab
->table
[code
].nbits
= 0;
1794 tab
->table
[code
].nexttable
= NULL
;
1797 for (i
= 0; i
< nsyms
; i
++) {
1798 if (lengths
[i
] <= pfxbits
|| (codes
[i
] & pfxmask
) != pfx
)
1800 code
= (codes
[i
] >> pfxbits
) & tab
->mask
;
1801 for (j
= code
; j
<= tab
->mask
; j
+= 1 << (lengths
[i
] - pfxbits
)) {
1802 tab
->table
[j
].code
= i
;
1803 nbits
= lengths
[i
] - pfxbits
;
1804 if (tab
->table
[j
].nbits
< nbits
)
1805 tab
->table
[j
].nbits
= nbits
;
1808 for (code
= 0; code
<= tab
->mask
; code
++) {
1809 if (tab
->table
[code
].nbits
<= bits
)
1811 /* Generate a subtable. */
1812 tab
->table
[code
].code
= -1;
1813 nbits
= tab
->table
[code
].nbits
- bits
;
1816 tab
->table
[code
].nbits
= bits
;
1817 tab
->table
[code
].nexttable
= mkonetab(codes
, lengths
, nsyms
,
1818 pfx
| (code
<< pfxbits
),
1819 pfxbits
+ bits
, nbits
);
1826 * Build a decode table, given a set of Huffman tree lengths.
1828 static struct table
*mktable(unsigned char *lengths
, int nlengths
,
1830 const char *alphabet
,
1838 if (alphabet
&& analyse_level
> 1) {
1840 printf("code lengths for %s alphabet:\n", alphabet
);
1841 for (i
= 0; i
< nlengths
; i
++) {
1842 col
+= printf("%3d", lengths
[i
]);
1853 maxlen
= hufcodes(lengths
, codes
, nlengths
);
1856 *error
= (maxlen
== -1 ? DEFLATE_ERR_LARGE_HUFTABLE
:
1857 DEFLATE_ERR_SMALL_HUFTABLE
);
1862 * Now we have the complete list of Huffman codes. Build a
1865 return mkonetab(codes
, lengths
, nlengths
, 0, 0, maxlen
< 9 ? maxlen
: 9);
1868 static int freetable(struct table
**ztab
)
1881 for (code
= 0; code
<= tab
->mask
; code
++)
1882 if (tab
->table
[code
].nexttable
!= NULL
)
1883 freetable(&tab
->table
[code
].nexttable
);
1894 struct deflate_decompress_ctx
{
1895 struct table
*staticlentable
, *staticdisttable
;
1896 struct table
*currlentable
, *currdisttable
, *lenlentable
;
1899 GZIPSTART
, GZIPMETHFLAGS
, GZIPIGNORE1
, GZIPIGNORE2
, GZIPIGNORE3
,
1900 GZIPEXTRA
, GZIPFNAME
, GZIPCOMMENT
,
1901 OUTSIDEBLK
, TREES_HDR
, TREES_LENLEN
, TREES_LEN
, TREES_LENREP
,
1902 INBLK
, GOTLENSYM
, GOTLEN
, GOTDISTSYM
,
1903 UNCOMP_LEN
, UNCOMP_NLEN
, UNCOMP_DATA
,
1906 CRC1
, CRC2
, ILEN1
, ILEN2
,
1909 int sym
, hlit
, hdist
, hclen
, lenptr
, lenextrabits
, lenaddon
, len
,
1912 unsigned char lenlen
[19];
1913 unsigned char lengths
[286 + 32];
1916 unsigned char window
[DWINSIZE
];
1918 unsigned char *outblk
;
1919 int outlen
, outsize
;
1921 unsigned long checksum
;
1922 unsigned long bytesout
;
1923 int gzflags
, gzextralen
;
1926 int bitcount_before
;
1927 #define BITCOUNT(dctx) ( (dctx)->bytesread * 8 - (dctx)->nbits )
1931 deflate_decompress_ctx
*deflate_decompress_new(int type
)
1933 deflate_decompress_ctx
*dctx
= snew(deflate_decompress_ctx
);
1934 unsigned char lengths
[288];
1936 memset(lengths
, 8, 144);
1937 memset(lengths
+ 144, 9, 256 - 144);
1938 memset(lengths
+ 256, 7, 280 - 256);
1939 memset(lengths
+ 280, 8, 288 - 280);
1940 dctx
->staticlentable
= mktable(lengths
, 288,
1945 assert(dctx
->staticlentable
);
1946 memset(lengths
, 5, 32);
1947 dctx
->staticdisttable
= mktable(lengths
, 32,
1952 assert(dctx
->staticdisttable
);
1953 dctx
->state
= (type
== DEFLATE_TYPE_ZLIB ? ZLIBSTART
:
1954 type
== DEFLATE_TYPE_GZIP ? GZIPSTART
:
1956 dctx
->currlentable
= dctx
->currdisttable
= dctx
->lenlentable
= NULL
;
1961 dctx
->lastblock
= FALSE
;
1962 dctx
->checksum
= (type
== DEFLATE_TYPE_ZLIB ?
1 : 0);
1964 dctx
->gzflags
= dctx
->gzextralen
= 0;
1966 dctx
->bytesread
= dctx
->bitcount_before
= 0;
1972 void deflate_decompress_free(deflate_decompress_ctx
*dctx
)
1974 if (dctx
->currlentable
&& dctx
->currlentable
!= dctx
->staticlentable
)
1975 freetable(&dctx
->currlentable
);
1976 if (dctx
->currdisttable
&& dctx
->currdisttable
!= dctx
->staticdisttable
)
1977 freetable(&dctx
->currdisttable
);
1978 if (dctx
->lenlentable
)
1979 freetable(&dctx
->lenlentable
);
1980 freetable(&dctx
->staticlentable
);
1981 freetable(&dctx
->staticdisttable
);
1985 static int huflookup(unsigned long *bitsp
, int *nbitsp
, struct table
*tab
)
1987 unsigned long bits
= *bitsp
;
1988 int nbits
= *nbitsp
;
1990 struct tableentry
*ent
;
1991 ent
= &tab
->table
[bits
& tab
->mask
];
1992 if (ent
->nbits
> nbits
)
1993 return -1; /* not enough data */
1994 bits
>>= ent
->nbits
;
1995 nbits
-= ent
->nbits
;
1996 if (ent
->code
== -1)
1997 tab
= ent
->nexttable
;
2005 * If we reach here with `tab' null, it can only be because
2006 * there was a missing entry in the Huffman table. This
2007 * should never occur even with invalid input data, because
2008 * we enforce at mktable time that the Huffman codes should
2009 * precisely cover the code space; so we can enforce this
2016 static void emit_char(deflate_decompress_ctx
*dctx
, int c
)
2018 dctx
->window
[dctx
->winpos
] = c
;
2019 dctx
->winpos
= (dctx
->winpos
+ 1) & (DWINSIZE
- 1);
2020 if (dctx
->outlen
>= dctx
->outsize
) {
2021 dctx
->outsize
= dctx
->outlen
* 3 / 2 + 512;
2022 dctx
->outblk
= sresize(dctx
->outblk
, dctx
->outsize
, unsigned char);
2024 if (dctx
->type
== DEFLATE_TYPE_ZLIB
) {
2025 unsigned char uc
= c
;
2026 dctx
->checksum
= adler32_update(dctx
->checksum
, &uc
, 1);
2027 } else if (dctx
->type
== DEFLATE_TYPE_GZIP
) {
2028 unsigned char uc
= c
;
2029 dctx
->checksum
= crc32_update(dctx
->checksum
, &uc
, 1);
2031 dctx
->outblk
[dctx
->outlen
++] = c
;
2035 #define EATBITS(n) ( dctx->nbits -= (n), dctx->bits >>= (n) )
2037 int deflate_decompress_data(deflate_decompress_ctx
*dctx
,
2038 const void *vblock
, int len
,
2039 void **outblock
, int *outlen
)
2041 const coderecord
*rec
;
2042 const unsigned char *block
= (const unsigned char *)vblock
;
2043 int code
, bfinal
, btype
, rep
, dist
, nlen
, header
, cksum
;
2049 if (dctx
->state
!= FINALSPIN
)
2050 return DEFLATE_ERR_UNEXPECTED_EOF
;
2055 dctx
->outblk
= NULL
;
2059 while (len
> 0 || dctx
->nbits
> 0) {
2060 while (dctx
->nbits
< 24 && len
> 0) {
2061 dctx
->bits
|= (*block
++) << dctx
->nbits
;
2068 switch (dctx
->state
) {
2070 /* Expect 16-bit zlib header. */
2071 if (dctx
->nbits
< 16)
2072 goto finished
; /* done all we can */
2075 * The header is stored as a big-endian 16-bit integer,
2076 * in contrast to the general little-endian policy in
2077 * the rest of the format :-(
2079 header
= (((dctx
->bits
& 0xFF00) >> 8) |
2080 ((dctx
->bits
& 0x00FF) << 8));
2086 * - bits 8-11 should be 1000 (Deflate/RFC1951)
2087 * - bits 12-15 should be at most 0111 (window size)
2088 * - bit 5 should be zero (no dictionary present)
2089 * - we don't care about bits 6-7 (compression rate)
2090 * - bits 0-4 should be set up to make the whole thing
2091 * a multiple of 31 (checksum).
2093 if ((header
& 0xF000) > 0x7000 ||
2094 (header
& 0x0020) != 0x0000 ||
2095 (header
% 31) != 0) {
2096 error
= DEFLATE_ERR_ZLIB_HEADER
;
2099 if ((header
& 0x0F00) != 0x0800) {
2100 error
= DEFLATE_ERR_ZLIB_WRONGCOMP
;
2103 dctx
->state
= OUTSIDEBLK
;
2106 /* Expect 16-bit gzip header. */
2107 if (dctx
->nbits
< 16)
2109 header
= dctx
->bits
& 0xFFFF;
2111 if (header
!= 0x8B1F) {
2112 error
= DEFLATE_ERR_GZIP_HEADER
;
2115 dctx
->state
= GZIPMETHFLAGS
;
2118 /* Expect gzip compression method and flags bytes. */
2119 if (dctx
->nbits
< 16)
2121 header
= dctx
->bits
& 0xFF;
2124 error
= DEFLATE_ERR_GZIP_WRONGCOMP
;
2127 dctx
->gzflags
= dctx
->bits
& 0xFF;
2128 if (dctx
->gzflags
& 2) {
2130 * The FHCRC flag is slightly confusing. RFC1952
2131 * documents it as indicating the presence of a
2132 * two-byte CRC16 of the gzip header, occurring
2133 * just before the beginning of the Deflate stream.
2134 * However, gzip itself (as of 1.3.5) appears to
2135 * believe it indicates that the current gzip
2136 * `member' is not the final one, i.e. that the
2137 * stream is composed of multiple gzip members
2138 * concatenated together, and furthermore gzip will
2139 * refuse to decode any file that has it set.
2141 * For this reason, I label it as `disputed' and
2142 * also refuse to decode anything that has it set.
2143 * I don't expect this to be a problem in practice.
2145 error
= DEFLATE_ERR_GZIP_FHCRC
;
2149 dctx
->state
= GZIPIGNORE1
;
2154 /* Expect two bytes of gzip timestamp/XFL/OS, which we ignore. */
2155 if (dctx
->nbits
< 16)
2158 if (dctx
->state
== GZIPIGNORE3
) {
2159 dctx
->state
= GZIPEXTRA
;
2161 dctx
->state
++; /* maps IGNORE1 -> IGNORE2 -> IGNORE3 */
2164 if (dctx
->gzflags
& 4) {
2165 /* Expect two bytes of extra-length count, then that many
2166 * extra bytes of header data, all of which we ignore. */
2167 if (!dctx
->gzextralen
) {
2168 if (dctx
->nbits
< 16)
2170 dctx
->gzextralen
= dctx
->bits
& 0xFFFF;
2173 } else if (dctx
->gzextralen
> 0) {
2174 if (dctx
->nbits
< 8)
2177 if (--dctx
->gzextralen
> 0)
2181 dctx
->state
= GZIPFNAME
;
2184 if (dctx
->gzflags
& 8) {
2186 * Expect a NUL-terminated filename.
2188 if (dctx
->nbits
< 8)
2190 code
= dctx
->bits
& 0xFF;
2195 dctx
->state
= GZIPCOMMENT
;
2198 if (dctx
->gzflags
& 16) {
2200 * Expect a NUL-terminated filename.
2202 if (dctx
->nbits
< 8)
2204 code
= dctx
->bits
& 0xFF;
2209 dctx
->state
= OUTSIDEBLK
;
2212 /* Expect 3-bit block header. */
2213 if (dctx
->nbits
< 3)
2214 goto finished
; /* done all we can */
2215 bfinal
= dctx
->bits
& 1;
2217 dctx
->lastblock
= TRUE
;
2219 btype
= dctx
->bits
& 3;
2222 int to_eat
= dctx
->nbits
& 7;
2223 dctx
->state
= UNCOMP_LEN
;
2224 EATBITS(to_eat
); /* align to byte boundary */
2225 } else if (btype
== 1) {
2226 dctx
->currlentable
= dctx
->staticlentable
;
2227 dctx
->currdisttable
= dctx
->staticdisttable
;
2228 dctx
->state
= INBLK
;
2229 } else if (btype
== 2) {
2230 dctx
->state
= TREES_HDR
;
2232 debug(("recv: bfinal=%d btype=%d\n", bfinal
, btype
));
2234 if (analyse_level
> 1) {
2235 static const char *const btypes
[] = {
2236 "uncompressed", "static", "dynamic", "type 3 (unknown)"
2238 printf("new block, %sfinal, %s\n",
2239 bfinal ?
"" : "not ",
2246 * Dynamic block header. Five bits of HLIT, five of
2247 * HDIST, four of HCLEN.
2249 if (dctx
->nbits
< 5 + 5 + 4)
2250 goto finished
; /* done all we can */
2251 dctx
->hlit
= 257 + (dctx
->bits
& 31);
2253 dctx
->hdist
= 1 + (dctx
->bits
& 31);
2255 dctx
->hclen
= 4 + (dctx
->bits
& 15);
2257 debug(("recv: hlit=%d hdist=%d hclen=%d\n", dctx
->hlit
,
2258 dctx
->hdist
, dctx
->hclen
));
2260 if (analyse_level
> 1)
2261 printf("hlit=%d, hdist=%d, hclen=%d\n",
2262 dctx
->hlit
, dctx
->hdist
, dctx
->hclen
);
2265 dctx
->state
= TREES_LENLEN
;
2266 memset(dctx
->lenlen
, 0, sizeof(dctx
->lenlen
));
2269 if (dctx
->nbits
< 3)
2271 while (dctx
->lenptr
< dctx
->hclen
&& dctx
->nbits
>= 3) {
2272 dctx
->lenlen
[lenlenmap
[dctx
->lenptr
++]] =
2273 (unsigned char) (dctx
->bits
& 7);
2274 debug(("recv: lenlen %d\n", (unsigned char) (dctx
->bits
& 7)));
2277 if (dctx
->lenptr
== dctx
->hclen
) {
2278 dctx
->lenlentable
= mktable(dctx
->lenlen
, 19,
2283 if (!dctx
->lenlentable
)
2284 goto finished
; /* error code set up by mktable */
2285 dctx
->state
= TREES_LEN
;
2290 if (dctx
->lenptr
>= dctx
->hlit
+ dctx
->hdist
) {
2291 dctx
->currlentable
= mktable(dctx
->lengths
, dctx
->hlit
,
2296 if (!dctx
->currlentable
)
2297 goto finished
; /* error code set up by mktable */
2298 dctx
->currdisttable
= mktable(dctx
->lengths
+ dctx
->hlit
,
2304 if (!dctx
->currdisttable
)
2305 goto finished
; /* error code set up by mktable */
2306 freetable(&dctx
->lenlentable
);
2307 dctx
->lenlentable
= NULL
;
2308 dctx
->state
= INBLK
;
2311 code
= huflookup(&dctx
->bits
, &dctx
->nbits
, dctx
->lenlentable
);
2312 debug(("recv: codelen %d\n", code
));
2317 if (analyse_level
> 1)
2318 printf("code-length %d\n", code
);
2320 dctx
->lengths
[dctx
->lenptr
++] = code
;
2322 dctx
->lenextrabits
= (code
== 16 ?
2 : code
== 17 ?
3 : 7);
2323 dctx
->lenaddon
= (code
== 18 ?
11 : 3);
2324 dctx
->lenrep
= (code
== 16 && dctx
->lenptr
> 0 ?
2325 dctx
->lengths
[dctx
->lenptr
- 1] : 0);
2326 dctx
->state
= TREES_LENREP
;
2330 if (dctx
->nbits
< dctx
->lenextrabits
)
2334 (dctx
->bits
& ((1 << dctx
->lenextrabits
) - 1));
2335 EATBITS(dctx
->lenextrabits
);
2336 if (dctx
->lenextrabits
)
2337 debug(("recv: codelen-extrabits %d/%d\n", rep
- dctx
->lenaddon
,
2338 dctx
->lenextrabits
));
2340 if (analyse_level
> 1)
2341 printf("code-length-repeat: %d copies of %d\n", rep
,
2344 while (rep
> 0 && dctx
->lenptr
< dctx
->hlit
+ dctx
->hdist
) {
2345 dctx
->lengths
[dctx
->lenptr
] = dctx
->lenrep
;
2349 dctx
->state
= TREES_LEN
;
2353 dctx
->bitcount_before
= BITCOUNT(dctx
);
2355 code
= huflookup(&dctx
->bits
, &dctx
->nbits
, dctx
->currlentable
);
2356 debug(("recv: litlen %d\n", code
));
2361 if (analyse_level
> 0)
2362 printf("%lu: literal %d [%d]\n", dctx
->bytesout
, code
,
2363 BITCOUNT(dctx
) - dctx
->bitcount_before
);
2365 emit_char(dctx
, code
);
2366 } else if (code
== 256) {
2367 if (dctx
->lastblock
)
2370 dctx
->state
= OUTSIDEBLK
;
2371 if (dctx
->currlentable
!= dctx
->staticlentable
) {
2372 freetable(&dctx
->currlentable
);
2373 dctx
->currlentable
= NULL
;
2375 if (dctx
->currdisttable
!= dctx
->staticdisttable
) {
2376 freetable(&dctx
->currdisttable
);
2377 dctx
->currdisttable
= NULL
;
2379 } else if (code
< 286) { /* static tree can give >285; ignore */
2380 dctx
->state
= GOTLENSYM
;
2385 rec
= &lencodes
[dctx
->sym
- 257];
2386 if (dctx
->nbits
< rec
->extrabits
)
2389 rec
->min
+ (dctx
->bits
& ((1 << rec
->extrabits
) - 1));
2391 debug(("recv: litlen-extrabits %d/%d\n",
2392 dctx
->len
- rec
->min
, rec
->extrabits
));
2393 EATBITS(rec
->extrabits
);
2394 dctx
->state
= GOTLEN
;
2397 code
= huflookup(&dctx
->bits
, &dctx
->nbits
, dctx
->currdisttable
);
2398 debug(("recv: dist %d\n", code
));
2401 dctx
->state
= GOTDISTSYM
;
2405 rec
= &distcodes
[dctx
->sym
];
2406 if (dctx
->nbits
< rec
->extrabits
)
2408 dist
= rec
->min
+ (dctx
->bits
& ((1 << rec
->extrabits
) - 1));
2410 debug(("recv: dist-extrabits %d/%d\n",
2411 dist
- rec
->min
, rec
->extrabits
));
2412 EATBITS(rec
->extrabits
);
2413 dctx
->state
= INBLK
;
2415 if (analyse_level
> 0)
2416 printf("%lu: copy len=%d dist=%d [%d]\n", dctx
->bytesout
,
2418 BITCOUNT(dctx
) - dctx
->bitcount_before
);
2421 emit_char(dctx
, dctx
->window
[(dctx
->winpos
- dist
) &
2426 * Uncompressed block. We expect to see a 16-bit LEN.
2428 if (dctx
->nbits
< 16)
2430 dctx
->uncomplen
= dctx
->bits
& 0xFFFF;
2432 dctx
->state
= UNCOMP_NLEN
;
2436 * Uncompressed block. We expect to see a 16-bit NLEN,
2437 * which should be the one's complement of the previous
2440 if (dctx
->nbits
< 16)
2442 nlen
= dctx
->bits
& 0xFFFF;
2444 if (dctx
->uncomplen
== 0)
2445 dctx
->state
= OUTSIDEBLK
; /* block is empty */
2447 dctx
->state
= UNCOMP_DATA
;
2450 if (dctx
->nbits
< 8)
2453 if (analyse_level
> 0)
2454 printf("%lu: uncompressed %d [8]\n", dctx
->bytesout
,
2455 (int)(dctx
->bits
& 0xFF));
2457 emit_char(dctx
, dctx
->bits
& 0xFF);
2459 if (--dctx
->uncomplen
== 0)
2460 dctx
->state
= OUTSIDEBLK
; /* end of uncompressed block */
2464 * End of compressed data. We align to a byte boundary,
2465 * and then look for format-specific trailer data.
2468 int to_eat
= dctx
->nbits
& 7;
2471 if (dctx
->type
== DEFLATE_TYPE_ZLIB
)
2472 dctx
->state
= ADLER1
;
2473 else if (dctx
->type
== DEFLATE_TYPE_GZIP
)
2476 dctx
->state
= FINALSPIN
;
2479 if (dctx
->nbits
< 16)
2481 cksum
= (dctx
->bits
& 0xFF) << 8;
2483 cksum
|= (dctx
->bits
& 0xFF);
2485 if (cksum
!= ((dctx
->checksum
>> 16) & 0xFFFF)) {
2486 error
= DEFLATE_ERR_CHECKSUM
;
2489 dctx
->state
= ADLER2
;
2492 if (dctx
->nbits
< 16)
2494 cksum
= (dctx
->bits
& 0xFF) << 8;
2496 cksum
|= (dctx
->bits
& 0xFF);
2498 if (cksum
!= (dctx
->checksum
& 0xFFFF)) {
2499 error
= DEFLATE_ERR_CHECKSUM
;
2502 dctx
->state
= FINALSPIN
;
2505 if (dctx
->nbits
< 16)
2507 cksum
= dctx
->bits
& 0xFFFF;
2509 if (cksum
!= (dctx
->checksum
& 0xFFFF)) {
2510 error
= DEFLATE_ERR_CHECKSUM
;
2516 if (dctx
->nbits
< 16)
2518 cksum
= dctx
->bits
& 0xFFFF;
2520 if (cksum
!= ((dctx
->checksum
>> 16) & 0xFFFF)) {
2521 error
= DEFLATE_ERR_CHECKSUM
;
2524 dctx
->state
= ILEN1
;
2527 if (dctx
->nbits
< 16)
2529 cksum
= dctx
->bits
& 0xFFFF;
2531 if (cksum
!= (dctx
->bytesout
& 0xFFFF)) {
2532 error
= DEFLATE_ERR_INLEN
;
2535 dctx
->state
= ILEN2
;
2538 if (dctx
->nbits
< 16)
2540 cksum
= dctx
->bits
& 0xFFFF;
2542 if (cksum
!= ((dctx
->bytesout
>> 16) & 0xFFFF)) {
2543 error
= DEFLATE_ERR_INLEN
;
2546 dctx
->state
= FINALSPIN
;
2549 /* Just ignore any trailing garbage on the data stream. */
2550 /* (We could alternatively throw an error here, if we wanted
2551 * to detect and complain about trailing garbage.) */
2552 EATBITS(dctx
->nbits
);
2558 *outblock
= dctx
->outblk
;
2559 *outlen
= dctx
->outlen
;
2563 #define A(code,str) str
2564 const char *const deflate_error_msg
[DEFLATE_NUM_ERRORS
] = {
2565 DEFLATE_ERRORLIST(A
)
2569 #define A(code,str) #code
2570 const char *const deflate_error_sym
[DEFLATE_NUM_ERRORS
] = {
2571 DEFLATE_ERRORLIST(A
)
2577 int main(int argc
, char **argv
)
2579 unsigned char buf
[65536];
2581 int ret
, err
, outlen
;
2582 deflate_decompress_ctx
*dhandle
;
2583 deflate_compress_ctx
*chandle
;
2584 int type
= DEFLATE_TYPE_ZLIB
, opts
= TRUE
;
2585 int compress
= FALSE
, decompress
= FALSE
;
2586 int got_arg
= FALSE
;
2587 char *filename
= NULL
;
2595 if (p
[0] == '-' && opts
) {
2596 if (!strcmp(p
, "-b"))
2597 type
= DEFLATE_TYPE_BARE
;
2598 else if (!strcmp(p
, "-g"))
2599 type
= DEFLATE_TYPE_GZIP
;
2600 else if (!strcmp(p
, "-c"))
2602 else if (!strcmp(p
, "-d"))
2604 else if (!strcmp(p
, "-a"))
2605 analyse_level
++, decompress
= TRUE
;
2606 else if (!strcmp(p
, "--"))
2607 opts
= FALSE
; /* next thing is filename */
2609 fprintf(stderr
, "unknown command line option '%s'\n", p
);
2612 } else if (!filename
) {
2615 fprintf(stderr
, "can only handle one filename\n");
2620 if (!compress
&& !decompress
) {
2621 fprintf(stderr
, "usage: deflate [ -c | -d | -a ] [ -b | -g ]"
2623 return (got_arg ?
1 : 0);
2626 if (compress
&& decompress
) {
2627 fprintf(stderr
, "please do not specify both compression and"
2628 " decompression\n");
2629 return (got_arg ?
1 : 0);
2633 chandle
= deflate_compress_new(type
);
2636 dhandle
= deflate_decompress_new(type
);
2641 fp
= fopen(filename
, "rb");
2647 fprintf(stderr
, "unable to open '%s'\n", filename
);
2652 ret
= fread(buf
, 1, sizeof(buf
), fp
);
2656 err
= deflate_decompress_data(dhandle
, buf
, ret
,
2657 (void **)&outbuf
, &outlen
);
2659 err
= deflate_decompress_data(dhandle
, NULL
, 0,
2660 (void **)&outbuf
, &outlen
);
2663 deflate_compress_data(chandle
, buf
, ret
, DEFLATE_NO_FLUSH
,
2664 (void **)&outbuf
, &outlen
);
2666 deflate_compress_data(chandle
, buf
, ret
, DEFLATE_END_OF_DATA
,
2667 (void **)&outbuf
, &outlen
);
2671 if (!analyse_level
&& outlen
)
2672 fwrite(outbuf
, 1, outlen
, stdout
);
2676 fprintf(stderr
, "decoding error: %s\n", deflate_error_msg
[err
]);
2682 deflate_decompress_free(dhandle
);
2684 deflate_compress_free(chandle
);
2696 int main(int argc
, char **argv
)
2698 char *filename
= NULL
;
2700 deflate_compress_ctx
*chandle
;
2701 deflate_decompress_ctx
*dhandle
;
2702 unsigned char buf
[65536], *outbuf
, *outbuf2
;
2703 int ret
, err
, outlen
, outlen2
;
2704 int dlen
= 0, clen
= 0;
2710 if (p
[0] == '-' && opts
) {
2711 if (!strcmp(p
, "--"))
2712 opts
= FALSE
; /* next thing is filename */
2714 fprintf(stderr
, "unknown command line option '%s'\n", p
);
2717 } else if (!filename
) {
2720 fprintf(stderr
, "can only handle one filename\n");
2726 fp
= fopen(filename
, "rb");
2732 fprintf(stderr
, "unable to open '%s'\n", filename
);
2736 chandle
= deflate_compress_new(DEFLATE_TYPE_ZLIB
);
2737 dhandle
= deflate_decompress_new(DEFLATE_TYPE_ZLIB
);
2740 ret
= fread(buf
, 1, sizeof(buf
), fp
);
2742 deflate_compress_data(chandle
, NULL
, 0, DEFLATE_END_OF_DATA
,
2743 (void **)&outbuf
, &outlen
);
2746 deflate_compress_data(chandle
, buf
, ret
, DEFLATE_NO_FLUSH
,
2747 (void **)&outbuf
, &outlen
);
2751 err
= deflate_decompress_data(dhandle
, outbuf
, outlen
,
2752 (void **)&outbuf2
, &outlen2
);
2756 fwrite(outbuf2
, 1, outlen2
, stdout
);
2759 if (!err
&& ret
<= 0) {
2763 err
= deflate_decompress_data(dhandle
, NULL
, 0,
2764 (void **)&outbuf2
, &outlen2
);
2765 assert(outbuf2
== NULL
);
2768 fprintf(stderr
, "decoding error: %s\n",
2769 deflate_error_msg
[err
]);
2775 fprintf(stderr
, "%d plaintext -> %d compressed\n", dlen
, clen
);