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: it would probably be useful to add a third format
11 * type to read and write actual gzip files.
13 * - Feature: the decompress function should return error codes
14 * indicating what kind of thing went wrong in a decoding error
15 * situation, possibly even including a file pointer. I envisage
16 * an enum of error codes in the header file, and one of those
17 * nasty preprocessor tricks to permit a user to define a
18 * code-to-text mapping array.
20 * - Feature: could do with forms of flush other than SYNC_FLUSH.
21 * I'm not sure exactly how those work when you don't know in
22 * advance that your next block will be static (as we did in
23 * PuTTY). And remember the 9-bit limitation of zlib.
25 * - Compression quality: introduce the option of choosing a
26 * static block instead of a dynamic one, where that's more
29 * - Compression quality: the actual LZ77 engine appears to be
30 * unable to track a match going beyond the input data passed to
31 * it in a single call. I'd prefer it to be more restartable
32 * than that: we ought to be able to pass in our input data in
33 * whatever size blocks happen to be convenient and not affect
36 * - Compression quality: chooseblock() appears to be computing
37 * wildly inaccurate block size estimates. Possible resolutions:
38 * + find and fix some trivial bug I haven't spotted yet
39 * + abandon the entropic approximation and go with trial
42 * - Compression quality: see if increasing SYMLIMIT causes
43 * dynamic blocks to start being consistently smaller than it.
45 * - Compression quality: we ought to be able to fall right back
46 * to actual uncompressed blocks if really necessary, though
47 * it's not clear what the criterion for doing so would be.
49 * - Performance: chooseblock() is currently computing the whole
50 * entropic approximation for every possible block size. It
51 * ought to be able to update it incrementally as it goes along
52 * (assuming of course we don't jack it all in and go for a
53 * proper Huffman analysis).
57 * This software is copyright 2000-2006 Simon Tatham.
59 * Permission is hereby granted, free of charge, to any person
60 * obtaining a copy of this software and associated documentation
61 * files (the "Software"), to deal in the Software without
62 * restriction, including without limitation the rights to use,
63 * copy, modify, merge, publish, distribute, sublicense, and/or
64 * sell copies of the Software, and to permit persons to whom the
65 * Software is furnished to do so, subject to the following
68 * The above copyright notice and this permission notice shall be
69 * included in all copies or substantial portions of the Software.
71 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
72 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
73 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
74 * NONINFRINGEMENT. IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE
75 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
76 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
77 * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
90 #define snew(type) ( (type *) malloc(sizeof(type)) )
91 #define snewn(n, type) ( (type *) malloc((n) * sizeof(type)) )
92 #define sresize(x, n, type) ( (type *) realloc((x), (n) * sizeof(type)) )
93 #define sfree(x) ( free((x)) )
95 #define lenof(x) (sizeof((x)) / sizeof(*(x)))
98 /* gcc-specific diagnostic macro */
99 #define debug_int(x...) ( fprintf(stderr, x) )
100 #define debug(x) ( debug_int x )
107 #define TRUE (!FALSE)
110 /* ----------------------------------------------------------------------
111 * Basic LZ77 code. This bit is designed modularly, so it could be
112 * ripped out and used in a different LZ77 compressor. Go to it,
116 struct LZ77InternalContext
;
118 struct LZ77InternalContext
*ictx
;
120 void (*literal
) (struct LZ77Context
* ctx
, unsigned char c
);
121 void (*match
) (struct LZ77Context
* ctx
, int distance
, int len
);
125 * Initialise the private fields of an LZ77Context. It's up to the
126 * user to initialise the public fields.
128 static int lz77_init(struct LZ77Context
*ctx
);
131 * Supply data to be compressed. Will update the private fields of
132 * the LZ77Context, and will call literal() and match() to output.
133 * If `compress' is FALSE, it will never emit a match, but will
134 * instead call literal() for everything.
136 static void lz77_compress(struct LZ77Context
*ctx
,
137 const unsigned char *data
, int len
, int compress
);
140 * Modifiable parameters.
142 #define WINSIZE 32768 /* window size. Must be power of 2! */
143 #define HASHMAX 2039 /* one more than max hash value */
144 #define MAXMATCH 32 /* how many matches we track */
145 #define HASHCHARS 3 /* how many chars make a hash */
148 * This compressor takes a less slapdash approach than the
149 * gzip/zlib one. Rather than allowing our hash chains to fall into
150 * disuse near the far end, we keep them doubly linked so we can
151 * _find_ the far end, and then every time we add a new byte to the
152 * window (thus rolling round by one and removing the previous
153 * byte), we can carefully remove the hash chain entry.
156 #define INVALID -1 /* invalid hash _and_ invalid offset */
158 short next
, prev
; /* array indices within the window */
163 short first
; /* window index of first in chain */
170 struct LZ77InternalContext
{
171 struct WindowEntry win
[WINSIZE
];
172 unsigned char data
[WINSIZE
];
174 struct HashEntry hashtab
[HASHMAX
];
175 unsigned char pending
[HASHCHARS
];
179 static int lz77_hash(const unsigned char *data
)
181 return (257 * data
[0] + 263 * data
[1] + 269 * data
[2]) % HASHMAX
;
184 static int lz77_init(struct LZ77Context
*ctx
)
186 struct LZ77InternalContext
*st
;
189 st
= snew(struct LZ77InternalContext
);
195 for (i
= 0; i
< WINSIZE
; i
++)
196 st
->win
[i
].next
= st
->win
[i
].prev
= st
->win
[i
].hashval
= INVALID
;
197 for (i
= 0; i
< HASHMAX
; i
++)
198 st
->hashtab
[i
].first
= INVALID
;
206 static void lz77_advance(struct LZ77InternalContext
*st
,
207 unsigned char c
, int hash
)
212 * Remove the hash entry at winpos from the tail of its chain,
213 * or empty the chain if it's the only thing on the chain.
215 if (st
->win
[st
->winpos
].prev
!= INVALID
) {
216 st
->win
[st
->win
[st
->winpos
].prev
].next
= INVALID
;
217 } else if (st
->win
[st
->winpos
].hashval
!= INVALID
) {
218 st
->hashtab
[st
->win
[st
->winpos
].hashval
].first
= INVALID
;
222 * Create a new entry at winpos and add it to the head of its
225 st
->win
[st
->winpos
].hashval
= hash
;
226 st
->win
[st
->winpos
].prev
= INVALID
;
227 off
= st
->win
[st
->winpos
].next
= st
->hashtab
[hash
].first
;
228 st
->hashtab
[hash
].first
= st
->winpos
;
230 st
->win
[off
].prev
= st
->winpos
;
231 st
->data
[st
->winpos
] = c
;
234 * Advance the window pointer.
236 st
->winpos
= (st
->winpos
+ 1) & (WINSIZE
- 1);
239 #define CHARAT(k) ( (k)<0 ? st->data[(st->winpos+k)&(WINSIZE-1)] : data[k] )
241 static void lz77_compress(struct LZ77Context
*ctx
,
242 const unsigned char *data
, int len
, int compress
)
244 struct LZ77InternalContext
*st
= ctx
->ictx
;
245 int i
, hash
, distance
, off
, nmatch
, matchlen
, advance
;
246 struct Match defermatch
, matches
[MAXMATCH
];
250 * Add any pending characters from last time to the window. (We
251 * might not be able to.)
253 for (i
= 0; i
< st
->npending
; i
++) {
254 unsigned char foo
[HASHCHARS
];
256 if (len
+ st
->npending
- i
< HASHCHARS
) {
257 /* Update the pending array. */
258 for (j
= i
; j
< st
->npending
; j
++)
259 st
->pending
[j
- i
] = st
->pending
[j
];
262 for (j
= 0; j
< HASHCHARS
; j
++)
263 foo
[j
] = (i
+ j
< st
->npending ? st
->pending
[i
+ j
] :
264 data
[i
+ j
- st
->npending
]);
265 lz77_advance(st
, foo
[0], lz77_hash(foo
));
273 /* Don't even look for a match, if we're not compressing. */
274 if (compress
&& len
>= HASHCHARS
) {
276 * Hash the next few characters.
278 hash
= lz77_hash(data
);
281 * Look the hash up in the corresponding hash chain and see
285 for (off
= st
->hashtab
[hash
].first
;
286 off
!= INVALID
; off
= st
->win
[off
].next
) {
287 /* distance = 1 if off == st->winpos-1 */
288 /* distance = WINSIZE if off == st->winpos */
290 WINSIZE
- (off
+ WINSIZE
- st
->winpos
) % WINSIZE
;
291 for (i
= 0; i
< HASHCHARS
; i
++)
292 if (CHARAT(i
) != CHARAT(i
- distance
))
294 if (i
== HASHCHARS
) {
295 matches
[nmatch
].distance
= distance
;
296 matches
[nmatch
].len
= 3;
297 if (++nmatch
>= MAXMATCH
)
308 * We've now filled up matches[] with nmatch potential
309 * matches. Follow them down to find the longest. (We
310 * assume here that it's always worth favouring a
311 * longer match over a shorter one.)
313 matchlen
= HASHCHARS
;
314 while (matchlen
< len
) {
316 for (i
= j
= 0; i
< nmatch
; i
++) {
317 if (CHARAT(matchlen
) ==
318 CHARAT(matchlen
- matches
[i
].distance
)) {
319 matches
[j
++] = matches
[i
];
329 * We've now got all the longest matches. We favour the
330 * shorter distances, which means we go with matches[0].
331 * So see if we want to defer it or throw it away.
333 matches
[0].len
= matchlen
;
334 if (defermatch
.len
> 0) {
335 if (matches
[0].len
> defermatch
.len
+ 1) {
336 /* We have a better match. Emit the deferred char,
337 * and defer this match. */
338 ctx
->literal(ctx
, (unsigned char) deferchr
);
339 defermatch
= matches
[0];
343 /* We don't have a better match. Do the deferred one. */
344 ctx
->match(ctx
, defermatch
.distance
, defermatch
.len
);
345 advance
= defermatch
.len
- 1;
349 /* There was no deferred match. Defer this one. */
350 defermatch
= matches
[0];
356 * We found no matches. Emit the deferred match, if
357 * any; otherwise emit a literal.
359 if (defermatch
.len
> 0) {
360 ctx
->match(ctx
, defermatch
.distance
, defermatch
.len
);
361 advance
= defermatch
.len
- 1;
364 ctx
->literal(ctx
, data
[0]);
370 * Now advance the position by `advance' characters,
371 * keeping the window and hash chains consistent.
373 while (advance
> 0) {
374 if (len
>= HASHCHARS
) {
375 lz77_advance(st
, *data
, lz77_hash(data
));
377 st
->pending
[st
->npending
++] = *data
;
386 /* ----------------------------------------------------------------------
387 * Deflate functionality common to both compression and decompression.
390 static const unsigned char lenlenmap
[] = {
391 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
394 #define MAXCODELEN 16
397 * Given a sequence of Huffman code lengths, compute the actual
398 * codes, in the final form suitable for feeding to outbits (i.e.
399 * already bit-mirrored).
401 * Returns the maximum code length found.
403 static int hufcodes(const unsigned char *lengths
, int *codes
, int nsyms
)
405 int count
[MAXCODELEN
], startcode
[MAXCODELEN
];
409 /* Count the codes of each length. */
411 for (i
= 1; i
< MAXCODELEN
; i
++)
413 for (i
= 0; i
< nsyms
; i
++) {
415 if (maxlen
< lengths
[i
])
418 /* Determine the starting code for each length block. */
420 for (i
= 1; i
< MAXCODELEN
; i
++) {
425 /* Determine the code for each symbol. Mirrored, of course. */
426 for (i
= 0; i
< nsyms
; i
++) {
427 code
= startcode
[lengths
[i
]]++;
429 for (j
= 0; j
< lengths
[i
]; j
++) {
430 codes
[i
] = (codes
[i
] << 1) | (code
& 1);
438 /* ----------------------------------------------------------------------
439 * Deflate compression.
442 #define SYMLIMIT 65536
443 #define SYMPFX_LITLEN 0x00000000U
444 #define SYMPFX_DIST 0x40000000U
445 #define SYMPFX_EXTRABITS 0x80000000U
446 #define SYMPFX_CODELEN 0xC0000000U
447 #define SYMPFX_MASK 0xC0000000U
449 #define SYM_EXTRABITS_MASK 0x3C000000U
450 #define SYM_EXTRABITS_SHIFT 26
452 struct deflate_compress_ctx
{
453 struct LZ77Context
*lzc
;
454 unsigned char *outbuf
;
456 unsigned long outbits
;
462 unsigned long adler32
;
466 unsigned long bitcount
;
470 static void outbits(deflate_compress_ctx
*out
,
471 unsigned long bits
, int nbits
)
473 assert(out
->noutbits
+ nbits
<= 32);
474 out
->outbits
|= bits
<< out
->noutbits
;
475 out
->noutbits
+= nbits
;
476 while (out
->noutbits
>= 8) {
477 if (out
->outlen
>= out
->outsize
) {
478 out
->outsize
= out
->outlen
+ 64;
479 out
->outbuf
= sresize(out
->outbuf
, out
->outsize
, unsigned char);
481 out
->outbuf
[out
->outlen
++] = (unsigned char) (out
->outbits
& 0xFF);
486 out
->bitcount
+= nbits
;
491 * Binary heap functions used by buildhuf(). Each one assumes the
492 * heap to be stored in an array of ints, with two ints per node
493 * (user data and key). They take in the old heap length, and
494 * return the new one.
496 #define HEAPPARENT(x) (((x)-2)/4*2)
497 #define HEAPLEFT(x) ((x)*2+2)
498 #define HEAPRIGHT(x) ((x)*2+4)
499 static int addheap(int *heap
, int len
, int userdata
, int key
)
504 heap
[len
++] = userdata
;
508 dad
= HEAPPARENT(me
);
509 if (heap
[me
+1] < heap
[dad
+1]) {
510 tmp
= heap
[me
]; heap
[me
] = heap
[dad
]; heap
[dad
] = tmp
;
511 tmp
= heap
[me
+1]; heap
[me
+1] = heap
[dad
+1]; heap
[dad
+1] = tmp
;
519 static int rmheap(int *heap
, int len
, int *userdata
, int *key
)
521 int me
, lc
, rc
, c
, tmp
;
527 heap
[1] = heap
[len
+1];
536 else if (rc
>= len
|| heap
[lc
+1] < heap
[rc
+1])
540 if (heap
[me
+1] > heap
[c
+1]) {
541 tmp
= heap
[me
]; heap
[me
] = heap
[c
]; heap
[c
] = tmp
;
542 tmp
= heap
[me
+1]; heap
[me
+1] = heap
[c
+1]; heap
[c
+1] = tmp
;
552 * The core of the Huffman algorithm: takes an input array of
553 * symbol frequencies, and produces an output array of code
556 * This is basically a generic Huffman implementation, but it has
557 * one zlib-related quirk which is that it caps the output code
558 * lengths to fit in an unsigned char (which is safe since Deflate
559 * will reject anything longer than 15 anyway). Anyone wanting to
560 * rip it out and use it in another context should find that easy
564 static void buildhuf(const int *freqs
, unsigned char *lengths
, int nsyms
)
566 int parent
[2*HUFMAX
-1];
567 int length
[2*HUFMAX
-1];
573 assert(nsyms
<= HUFMAX
);
575 memset(parent
, 0, sizeof(parent
));
578 * Begin by building the heap.
581 for (i
= 0; i
< nsyms
; i
++)
582 if (freqs
[i
] > 0) /* leave unused symbols out totally */
583 heapsize
= addheap(heap
, heapsize
, i
, freqs
[i
]);
586 * Now repeatedly take two elements off the heap and merge
590 while (heapsize
> 2) {
591 heapsize
= rmheap(heap
, heapsize
, &i
, &si
);
592 heapsize
= rmheap(heap
, heapsize
, &j
, &sj
);
595 heapsize
= addheap(heap
, heapsize
, n
, si
+ sj
);
600 * Now we have our tree, in the form of a link from each node
601 * to the index of its parent. Count back down the tree to
602 * determine the code lengths.
604 memset(length
, 0, sizeof(length
));
605 /* The tree root has length 0 after that, which is correct. */
608 length
[i
] = 1 + length
[parent
[i
]];
611 * And that's it. (Simple, wasn't it?) Copy the lengths into
612 * the output array and leave.
614 * Here we cap lengths to fit in unsigned char.
616 for (i
= 0; i
< nsyms
; i
++)
617 lengths
[i
] = (length
[i
] > 255 ?
255 : length
[i
]);
621 * Wrapper around buildhuf() which enforces the Deflate restriction
622 * that no code length may exceed 15 bits, or 7 for the auxiliary
623 * code length alphabet. This function has the same calling
624 * semantics as buildhuf(), except that it might modify the freqs
627 static void deflate_buildhuf(int *freqs
, unsigned char *lengths
,
628 int nsyms
, int limit
)
630 int smallestfreq
, totalfreq
, nactivesyms
;
631 int num
, denom
, adjust
;
636 * First, try building the Huffman table the normal way. If
637 * this works, it's optimal, so we don't want to mess with it.
639 buildhuf(freqs
, lengths
, nsyms
);
641 for (i
= 0; i
< nsyms
; i
++)
642 if (lengths
[i
] > limit
)
649 * The Huffman algorithm can only ever generate a code length
650 * of N bits or more if there is a symbol whose probability is
651 * less than the reciprocal of the (N+2)th Fibonacci number
652 * (counting from F_0=0 and F_1=1), i.e. 1/2584 for N=16, or
653 * 1/55 for N=8. (This is a necessary though not sufficient
656 * Why is this? Well, consider the input symbol with the
657 * smallest probability. Let that probability be x. In order
658 * for this symbol to have a code length of at least 1, the
659 * Huffman algorithm will have to merge it with some other
660 * node; and since x is the smallest probability, the node it
661 * gets merged with must be at least x. Thus, the probability
662 * of the resulting combined node will be at least 2x. Now in
663 * order for our node to reach depth 2, this 2x-node must be
664 * merged again. But what with? We can't assume the node it
665 * merges with is at least 2x, because this one might only be
666 * the _second_ smallest remaining node. But we do know the
667 * node it merges with must be at least x, so our order-2
668 * internal node is at least 3x.
670 * How small a node can merge with _that_ to get an order-3
671 * internal node? Well, it must be at least 2x, because if it
672 * was smaller than that then it would have been one of the two
673 * smallest nodes in the previous step and been merged at that
674 * point. So at least 3x, plus at least 2x, comes to at least
675 * 5x for an order-3 node.
677 * And so it goes on: at every stage we must merge our current
678 * node with a node at least as big as the bigger of this one's
679 * two parents, and from this starting point that gives rise to
680 * the Fibonacci sequence. So we find that in order to have a
681 * node n levels deep (i.e. a maximum code length of n), the
682 * overall probability of the root of the entire tree must be
683 * at least F_{n+2} times the probability of the rarest symbol.
684 * In other words, since the overall probability is 1, it is a
685 * necessary condition for a code length of 16 or more that
686 * there must be at least one symbol with probability <=
689 * (To demonstrate that a probability this big really can give
690 * rise to a code length of 16, consider the set of input
691 * frequencies { 1-epsilon, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
692 * 89, 144, 233, 377, 610, 987 }, for arbitrarily small
695 * So here buildhuf() has returned us an overlong code. So to
696 * ensure it doesn't do it again, we add a constant to all the
697 * (non-zero) symbol frequencies, causing them to become more
698 * balanced and removing the danger. We can then feed the
699 * results back to the standard buildhuf() and be
700 * assert()-level confident that the resulting code lengths
701 * contain nothing outside the permitted range.
703 maxprob
= (limit
== 16 ?
2584 : 55); /* no point in computing full F_n */
704 totalfreq
= nactivesyms
= 0;
706 for (i
= 0; i
< nsyms
; i
++) {
709 if (smallestfreq
< 0 || smallestfreq
> freqs
[i
])
710 smallestfreq
= freqs
[i
];
711 totalfreq
+= freqs
[i
];
714 assert(smallestfreq
<= totalfreq
/ maxprob
);
717 * We want to find the smallest integer `adjust' such that
718 * (totalfreq + nactivesyms * adjust) / (smallestfreq +
719 * adjust) is less than maxprob. A bit of algebra tells us
720 * that the threshold value is equal to
722 * totalfreq - maxprob * smallestfreq
723 * ----------------------------------
724 * maxprob - nactivesyms
726 * rounded up, of course. And we'll only even be trying
729 num
= totalfreq
- smallestfreq
* maxprob
;
730 denom
= maxprob
- nactivesyms
;
731 adjust
= (num
+ denom
- 1) / denom
;
734 * Now add `adjust' to all the input symbol frequencies.
736 for (i
= 0; i
< nsyms
; i
++)
741 * Rebuild the Huffman tree...
743 buildhuf(freqs
, lengths
, nsyms
);
746 * ... and this time it ought to be OK.
748 for (i
= 0; i
< nsyms
; i
++)
749 assert(lengths
[i
] <= limit
);
753 unsigned char *len_litlen
;
755 unsigned char *len_dist
;
757 unsigned char *len_codelen
;
762 * Write out a single symbol, given the three Huffman trees.
764 static void writesym(deflate_compress_ctx
*out
,
765 unsigned sym
, struct huftrees
*trees
)
767 unsigned basesym
= sym
&~ SYMPFX_MASK
;
770 switch (sym
& SYMPFX_MASK
) {
772 debug(("send: litlen %d\n", basesym
));
773 outbits(out
, trees
->code_litlen
[basesym
], trees
->len_litlen
[basesym
]);
776 debug(("send: dist %d\n", basesym
));
777 outbits(out
, trees
->code_dist
[basesym
], trees
->len_dist
[basesym
]);
780 debug(("send: codelen %d\n", basesym
));
781 outbits(out
, trees
->code_codelen
[basesym
],trees
->len_codelen
[basesym
]);
783 case SYMPFX_EXTRABITS
:
784 i
= basesym
>> SYM_EXTRABITS_SHIFT
;
785 basesym
&= ~SYM_EXTRABITS_MASK
;
786 debug(("send: extrabits %d/%d\n", basesym
, i
));
787 outbits(out
, basesym
, i
);
792 static void outblock(deflate_compress_ctx
*out
,
793 int blklen
, int dynamic
)
795 int freqs1
[286], freqs2
[30], freqs3
[19];
796 unsigned char len1
[286], len2
[30], len3
[19];
797 int code1
[286], code2
[30], code3
[19];
798 int hlit
, hdist
, hclen
, bfinal
, btype
;
799 int treesrc
[286 + 30];
800 int treesyms
[286 + 30];
802 int i
, ntreesrc
, ntreesyms
;
805 unsigned long bitcount_before
;
808 ht
.len_litlen
= len1
;
810 ht
.len_codelen
= len3
;
811 ht
.code_litlen
= code1
;
812 ht
.code_dist
= code2
;
813 ht
.code_codelen
= code3
;
816 * Build the two main Huffman trees.
820 * Count up the frequency tables.
822 memset(freqs1
, 0, sizeof(freqs1
));
823 memset(freqs2
, 0, sizeof(freqs2
));
824 freqs1
[256] = 1; /* we're bound to need one EOB */
825 for (i
= 0; i
< blklen
; i
++) {
826 unsigned sym
= out
->syms
[(out
->symstart
+ i
) % SYMLIMIT
];
829 * Increment the occurrence counter for this symbol, if
830 * it's in one of the Huffman alphabets and isn't extra
833 if ((sym
& SYMPFX_MASK
) == SYMPFX_LITLEN
) {
835 assert(sym
< lenof(freqs1
));
837 } else if ((sym
& SYMPFX_MASK
) == SYMPFX_DIST
) {
839 assert(sym
< lenof(freqs2
));
843 deflate_buildhuf(freqs1
, len1
, lenof(freqs1
), 15);
844 deflate_buildhuf(freqs2
, len2
, lenof(freqs2
), 15);
847 * Fixed static trees.
849 for (i
= 0; i
< lenof(len1
); i
++)
850 len1
[i
] = (i
< 144 ?
8 :
853 for (i
= 0; i
< lenof(len2
); i
++)
856 hufcodes(len1
, code1
, lenof(freqs1
));
857 hufcodes(len2
, code2
, lenof(freqs2
));
861 * Determine HLIT and HDIST.
863 for (hlit
= 286; hlit
> 257 && len1
[hlit
-1] == 0; hlit
--);
864 for (hdist
= 30; hdist
> 1 && len2
[hdist
-1] == 0; hdist
--);
867 * Write out the list of symbols used to transmit the
871 for (i
= 0; i
< hlit
; i
++)
872 treesrc
[ntreesrc
++] = len1
[i
];
873 for (i
= 0; i
< hdist
; i
++)
874 treesrc
[ntreesrc
++] = len2
[i
];
876 for (i
= 0; i
< ntreesrc
;) {
880 /* Find length of run of the same length code. */
881 while (i
+j
< ntreesrc
&& treesrc
[i
+j
] == treesrc
[i
])
884 /* Encode that run as economically as we can. */
886 if (treesrc
[i
] == 0) {
888 * Zero code length: we can output run codes for
889 * 3-138 zeroes. So if we have fewer than 3 zeroes,
890 * we just output literals. Otherwise, we output
891 * nothing but run codes, and tweak their lengths
892 * to make sure we aren't left with under 3 at the
897 treesyms
[ntreesyms
++] = 0 | SYMPFX_CODELEN
;
900 int rpt
= (k
< 138 ? k
: 138);
901 if (rpt
> k
-3 && rpt
< k
)
903 assert(rpt
>= 3 && rpt
<= 138);
905 treesyms
[ntreesyms
++] = 17 | SYMPFX_CODELEN
;
906 treesyms
[ntreesyms
++] =
907 (SYMPFX_EXTRABITS
| (rpt
- 3) |
908 (3 << SYM_EXTRABITS_SHIFT
));
910 treesyms
[ntreesyms
++] = 18 | SYMPFX_CODELEN
;
911 treesyms
[ntreesyms
++] =
912 (SYMPFX_EXTRABITS
| (rpt
- 11) |
913 (7 << SYM_EXTRABITS_SHIFT
));
920 * Non-zero code length: we must output the first
921 * one explicitly, then we can output a copy code
922 * for 3-6 repeats. So if we have fewer than 4
923 * repeats, we _just_ output literals. Otherwise,
924 * we output one literal plus at least one copy
925 * code, and tweak the copy codes to make sure we
926 * aren't left with under 3 at the end.
928 assert(treesrc
[i
] < 16);
929 treesyms
[ntreesyms
++] = treesrc
[i
] | SYMPFX_CODELEN
;
933 treesyms
[ntreesyms
++] = treesrc
[i
] | SYMPFX_CODELEN
;
936 int rpt
= (k
< 6 ? k
: 6);
937 if (rpt
> k
-3 && rpt
< k
)
939 assert(rpt
>= 3 && rpt
<= 6);
940 treesyms
[ntreesyms
++] = 16 | SYMPFX_CODELEN
;
941 treesyms
[ntreesyms
++] = (SYMPFX_EXTRABITS
| (rpt
- 3) |
942 (2 << SYM_EXTRABITS_SHIFT
));
950 assert((unsigned)ntreesyms
< lenof(treesyms
));
953 * Count up the frequency table for the tree-transmission
954 * symbols, and build the auxiliary Huffman tree for that.
956 memset(freqs3
, 0, sizeof(freqs3
));
957 for (i
= 0; i
< ntreesyms
; i
++) {
958 unsigned sym
= treesyms
[i
];
961 * Increment the occurrence counter for this symbol, if
962 * it's the Huffman alphabet and isn't extra bits.
964 if ((sym
& SYMPFX_MASK
) == SYMPFX_CODELEN
) {
966 assert(sym
< lenof(freqs3
));
970 deflate_buildhuf(freqs3
, len3
, lenof(freqs3
), 7);
971 hufcodes(len3
, code3
, lenof(freqs3
));
974 * Reorder the code length codes into transmission order, and
977 for (i
= 0; i
< 19; i
++)
978 codelen
[i
] = len3
[lenlenmap
[i
]];
979 for (hclen
= 19; hclen
> 4 && codelen
[hclen
-1] == 0; hclen
--);
983 * Actually transmit the block.
986 /* 3-bit block header */
987 bfinal
= (out
->lastblock ?
1 : 0);
988 btype
= dynamic ?
2 : 1;
989 debug(("send: bfinal=%d btype=%d\n", bfinal
, btype
));
990 outbits(out
, bfinal
, 1);
991 outbits(out
, btype
, 2);
994 bitcount_before
= out
->bitcount
;
998 /* HLIT, HDIST and HCLEN */
999 debug(("send: hlit=%d hdist=%d hclen=%d\n", hlit
, hdist
, hclen
));
1000 outbits(out
, hlit
- 257, 5);
1001 outbits(out
, hdist
- 1, 5);
1002 outbits(out
, hclen
- 4, 4);
1004 /* Code lengths for the auxiliary tree */
1005 for (i
= 0; i
< hclen
; i
++) {
1006 debug(("send: lenlen %d\n", codelen
[i
]));
1007 outbits(out
, codelen
[i
], 3);
1010 /* Code lengths for the literal/length and distance trees */
1011 for (i
= 0; i
< ntreesyms
; i
++)
1012 writesym(out
, treesyms
[i
], &ht
);
1014 fprintf(stderr
, "total tree size %lu bits\n",
1015 out
->bitcount
- bitcount_before
);
1019 /* Output the actual symbols from the buffer */
1020 for (i
= 0; i
< blklen
; i
++) {
1021 unsigned sym
= out
->syms
[(out
->symstart
+ i
) % SYMLIMIT
];
1022 writesym(out
, sym
, &ht
);
1025 /* Output the end-of-data symbol */
1026 writesym(out
, SYMPFX_LITLEN
| 256, &ht
);
1029 * Remove all the just-output symbols from the symbol buffer by
1030 * adjusting symstart and nsyms.
1032 out
->symstart
= (out
->symstart
+ blklen
) % SYMLIMIT
;
1033 out
->nsyms
-= blklen
;
1036 static void outblock_wrapper(deflate_compress_ctx
*out
,
1037 int best_dynamic_len
)
1040 * Final block choice function: we have the option of either
1041 * outputting a dynamic block of length best_dynamic_len, or a
1042 * static block of length out->nsyms. Whichever gives us the
1043 * best value for money, we do.
1045 * FIXME: currently we always choose dynamic except for empty
1046 * blocks. We should make a sensible judgment.
1048 if (out
->nsyms
== 0)
1049 outblock(out
, 0, FALSE
);
1051 outblock(out
, best_dynamic_len
, TRUE
);
1054 static void chooseblock(deflate_compress_ctx
*out
)
1056 int freqs1
[286], freqs2
[30];
1061 memset(freqs1
, 0, sizeof(freqs1
));
1062 memset(freqs2
, 0, sizeof(freqs2
));
1063 freqs1
[256] = 1; /* we're bound to need one EOB */
1067 * Iterate over all possible block lengths, computing the
1068 * entropic coding approximation to the final length at every
1069 * stage. We divide the result by the number of symbols
1070 * encoded, to determine the `value for money' (overall
1071 * bits-per-symbol count) of a block of that length.
1075 for (i
= 0; i
< out
->nsyms
; i
++) {
1076 unsigned sym
= out
->syms
[(out
->symstart
+ i
) % SYMLIMIT
];
1078 if (i
> 0 && (sym
& SYMPFX_MASK
) == SYMPFX_LITLEN
) {
1080 * This is a viable point at which to end the block.
1081 * Compute the length approximation and hence the value
1084 double len
= 0.0, vfm
;
1089 * FIXME: we should be doing this incrementally, rather
1090 * than recomputing the whole thing at every byte
1091 * position. Also, can we fiddle the logs somehow to
1092 * avoid having to do floating point?
1095 for (k
= 0; k
< (int)lenof(freqs1
); k
++) {
1097 len
-= freqs1
[k
] * log(freqs1
[k
]);
1101 len
+= total
* log(total
);
1103 for (k
= 0; k
< (int)lenof(freqs2
); k
++) {
1105 len
-= freqs2
[k
] * log(freqs2
[k
]);
1109 len
+= total
* log(total
);
1112 len
+= 300; /* very approximate size of the Huffman trees */
1114 vfm
= i
/ len
; /* symbols encoded per bit */
1115 /* fprintf(stderr, "chooseblock: i=%d gives len %g, vfm %g\n", i, len, vfm); */
1116 if (bestlen
< 0 || vfm
> bestvfm
) {
1123 * Increment the occurrence counter for this symbol, if
1124 * it's in one of the Huffman alphabets and isn't extra
1127 if ((sym
& SYMPFX_MASK
) == SYMPFX_LITLEN
) {
1128 sym
&= ~SYMPFX_MASK
;
1129 assert(sym
< lenof(freqs1
));
1131 } else if ((sym
& SYMPFX_MASK
) == SYMPFX_DIST
) {
1132 sym
&= ~SYMPFX_MASK
;
1133 assert(sym
< lenof(freqs2
));
1135 } else if ((sym
& SYMPFX_MASK
) == SYMPFX_EXTRABITS
) {
1136 nextrabits
+= (sym
&~ SYMPFX_MASK
) >> SYM_EXTRABITS_SHIFT
;
1140 assert(bestlen
> 0);
1142 /* fprintf(stderr, "chooseblock: bestlen %d, bestvfm %g\n", bestlen, bestvfm); */
1143 outblock_wrapper(out
, bestlen
);
1147 * Force the current symbol buffer to be flushed out as a single
1150 static void flushblock(deflate_compress_ctx
*out
)
1153 * Because outblock_wrapper guarantees to output either a
1154 * dynamic block of the given length or a static block of
1155 * length out->nsyms, we know that passing out->nsyms as the
1156 * given length will definitely result in us using up the
1159 outblock_wrapper(out
, out
->nsyms
);
1160 assert(out
->nsyms
== 0);
1164 * Place a symbol into the symbols buffer.
1166 static void outsym(deflate_compress_ctx
*out
, unsigned long sym
)
1168 assert(out
->nsyms
< SYMLIMIT
);
1169 out
->syms
[(out
->symstart
+ out
->nsyms
++) % SYMLIMIT
] = sym
;
1171 if (out
->nsyms
== SYMLIMIT
)
1176 short code
, extrabits
;
1180 static const coderecord lencodes
[] = {
1212 static const coderecord distcodes
[] = {
1233 {20, 9, 1025, 1536},
1234 {21, 9, 1537, 2048},
1235 {22, 10, 2049, 3072},
1236 {23, 10, 3073, 4096},
1237 {24, 11, 4097, 6144},
1238 {25, 11, 6145, 8192},
1239 {26, 12, 8193, 12288},
1240 {27, 12, 12289, 16384},
1241 {28, 13, 16385, 24576},
1242 {29, 13, 24577, 32768},
1245 static void literal(struct LZ77Context
*ectx
, unsigned char c
)
1247 deflate_compress_ctx
*out
= (deflate_compress_ctx
*) ectx
->userdata
;
1249 outsym(out
, SYMPFX_LITLEN
| c
);
1252 static void match(struct LZ77Context
*ectx
, int distance
, int len
)
1254 const coderecord
*d
, *l
;
1256 deflate_compress_ctx
*out
= (deflate_compress_ctx
*) ectx
->userdata
;
1262 * We can transmit matches of lengths 3 through 258
1263 * inclusive. So if len exceeds 258, we must transmit in
1264 * several steps, with 258 or less in each step.
1266 * Specifically: if len >= 261, we can transmit 258 and be
1267 * sure of having at least 3 left for the next step. And if
1268 * len <= 258, we can just transmit len. But if len == 259
1269 * or 260, we must transmit len-3.
1271 thislen
= (len
> 260 ?
258 : len
<= 258 ? len
: len
- 3);
1275 * Binary-search to find which length code we're
1279 j
= sizeof(lencodes
) / sizeof(*lencodes
);
1283 if (thislen
< lencodes
[k
].min
)
1285 else if (thislen
> lencodes
[k
].max
)
1289 break; /* found it! */
1294 * Transmit the length code.
1296 outsym(out
, SYMPFX_LITLEN
| l
->code
);
1299 * Transmit the extra bits.
1302 outsym(out
, (SYMPFX_EXTRABITS
| (thislen
- l
->min
) |
1303 (l
->extrabits
<< SYM_EXTRABITS_SHIFT
)));
1307 * Binary-search to find which distance code we're
1311 j
= sizeof(distcodes
) / sizeof(*distcodes
);
1315 if (distance
< distcodes
[k
].min
)
1317 else if (distance
> distcodes
[k
].max
)
1321 break; /* found it! */
1326 * Write the distance code.
1328 outsym(out
, SYMPFX_DIST
| d
->code
);
1331 * Transmit the extra bits.
1334 outsym(out
, (SYMPFX_EXTRABITS
| (distance
- d
->min
) |
1335 (d
->extrabits
<< SYM_EXTRABITS_SHIFT
)));
1340 deflate_compress_ctx
*deflate_compress_new(int type
)
1342 deflate_compress_ctx
*out
;
1343 struct LZ77Context
*ectx
= snew(struct LZ77Context
);
1346 ectx
->literal
= literal
;
1347 ectx
->match
= match
;
1349 out
= snew(deflate_compress_ctx
);
1351 out
->outbits
= out
->noutbits
= 0;
1352 out
->firstblock
= TRUE
;
1357 out
->syms
= snewn(SYMLIMIT
, unsigned long);
1358 out
->symstart
= out
->nsyms
= 0;
1361 out
->lastblock
= FALSE
;
1362 out
->finished
= FALSE
;
1364 ectx
->userdata
= out
;
1370 void deflate_compress_free(deflate_compress_ctx
*out
)
1372 struct LZ77Context
*ectx
= out
->lzc
;
1380 static unsigned long adler32_update(unsigned long s
,
1381 const unsigned char *data
, int len
)
1383 unsigned s1
= s
& 0xFFFF, s2
= (s
>> 16) & 0xFFFF;
1386 for (i
= 0; i
< len
; i
++) {
1395 return ((s2
% 65521) << 16) | (s1
% 65521);
1398 int deflate_compress_data(deflate_compress_ctx
*out
,
1399 const void *vblock
, int len
, int flushtype
,
1400 void **outblock
, int *outlen
)
1402 struct LZ77Context
*ectx
= out
->lzc
;
1403 const unsigned char *block
= (const unsigned char *)vblock
;
1405 assert(!out
->finished
);
1408 out
->outlen
= out
->outsize
= 0;
1411 * If this is the first block, output the header.
1413 if (out
->firstblock
) {
1414 switch (out
->type
) {
1415 case DEFLATE_TYPE_BARE
:
1416 break; /* no header */
1417 case DEFLATE_TYPE_ZLIB
:
1419 * Zlib (RFC1950) header bytes: 78 9C. (Deflate
1420 * compression, 32K window size, default algorithm.)
1422 outbits(out
, 0x9C78, 16);
1425 out
->firstblock
= FALSE
;
1429 * Feed our data to the LZ77 compression phase.
1431 lz77_compress(ectx
, block
, len
, TRUE
);
1436 if (out
->type
== DEFLATE_TYPE_ZLIB
)
1437 out
->adler32
= adler32_update(out
->adler32
, block
, len
);
1439 switch (flushtype
) {
1441 * FIXME: what other flush types are available and useful?
1442 * In PuTTY, it was clear that we generally wanted to be in
1443 * a static block so it was safe to open one. Here, we
1444 * probably prefer to be _outside_ a block if we can. Think
1447 case DEFLATE_NO_FLUSH
:
1448 break; /* don't flush any data at all (duh) */
1449 case DEFLATE_SYNC_FLUSH
:
1451 * Close the current block.
1456 * Then output an empty _uncompressed_ block: send 000,
1457 * then sync to byte boundary, then send bytes 00 00 FF
1462 outbits(out
, 0, 8 - out
->noutbits
);
1463 outbits(out
, 0, 16);
1464 outbits(out
, 0xFFFF, 16);
1466 case DEFLATE_END_OF_DATA
:
1468 * Output a block with BFINAL set.
1470 out
->lastblock
= TRUE
;
1474 * Sync to byte boundary, flushing out the final byte.
1477 outbits(out
, 0, 8 - out
->noutbits
);
1480 * Output the adler32 checksum, in zlib mode.
1482 if (out
->type
== DEFLATE_TYPE_ZLIB
) {
1483 outbits(out
, (out
->adler32
>> 24) & 0xFF, 8);
1484 outbits(out
, (out
->adler32
>> 16) & 0xFF, 8);
1485 outbits(out
, (out
->adler32
>> 8) & 0xFF, 8);
1486 outbits(out
, (out
->adler32
>> 0) & 0xFF, 8);
1489 out
->finished
= TRUE
;
1494 * Return any data that we've generated.
1496 *outblock
= (void *)out
->outbuf
;
1497 *outlen
= out
->outlen
;
1502 /* ----------------------------------------------------------------------
1503 * deflate decompression.
1507 * The way we work the Huffman decode is to have a table lookup on
1508 * the first N bits of the input stream (in the order they arrive,
1509 * of course, i.e. the first bit of the Huffman code is in bit 0).
1510 * Each table entry lists the number of bits to consume, plus
1511 * either an output code or a pointer to a secondary table.
1517 unsigned char nbits
;
1519 struct table
*nexttable
;
1523 int mask
; /* mask applied to input bit stream */
1524 struct tableentry
*table
;
1530 * Build a single-level decode table for elements
1531 * [minlength,maxlength) of the provided code/length tables, and
1532 * recurse to build subtables.
1534 static struct table
*mkonetab(int *codes
, unsigned char *lengths
, int nsyms
,
1535 int pfx
, int pfxbits
, int bits
)
1537 struct table
*tab
= snew(struct table
);
1538 int pfxmask
= (1 << pfxbits
) - 1;
1539 int nbits
, i
, j
, code
;
1541 tab
->table
= snewn(1 << bits
, struct tableentry
);
1542 tab
->mask
= (1 << bits
) - 1;
1544 for (code
= 0; code
<= tab
->mask
; code
++) {
1545 tab
->table
[code
].code
= -1;
1546 tab
->table
[code
].nbits
= 0;
1547 tab
->table
[code
].nexttable
= NULL
;
1550 for (i
= 0; i
< nsyms
; i
++) {
1551 if (lengths
[i
] <= pfxbits
|| (codes
[i
] & pfxmask
) != pfx
)
1553 code
= (codes
[i
] >> pfxbits
) & tab
->mask
;
1554 for (j
= code
; j
<= tab
->mask
; j
+= 1 << (lengths
[i
] - pfxbits
)) {
1555 tab
->table
[j
].code
= i
;
1556 nbits
= lengths
[i
] - pfxbits
;
1557 if (tab
->table
[j
].nbits
< nbits
)
1558 tab
->table
[j
].nbits
= nbits
;
1561 for (code
= 0; code
<= tab
->mask
; code
++) {
1562 if (tab
->table
[code
].nbits
<= bits
)
1564 /* Generate a subtable. */
1565 tab
->table
[code
].code
= -1;
1566 nbits
= tab
->table
[code
].nbits
- bits
;
1569 tab
->table
[code
].nbits
= bits
;
1570 tab
->table
[code
].nexttable
= mkonetab(codes
, lengths
, nsyms
,
1571 pfx
| (code
<< pfxbits
),
1572 pfxbits
+ bits
, nbits
);
1579 * Build a decode table, given a set of Huffman tree lengths.
1581 static struct table
*mktable(unsigned char *lengths
, int nlengths
)
1586 maxlen
= hufcodes(lengths
, codes
, nlengths
);
1589 * Now we have the complete list of Huffman codes. Build a
1592 return mkonetab(codes
, lengths
, nlengths
, 0, 0, maxlen
< 9 ? maxlen
: 9);
1595 static int freetable(struct table
**ztab
)
1608 for (code
= 0; code
<= tab
->mask
; code
++)
1609 if (tab
->table
[code
].nexttable
!= NULL
)
1610 freetable(&tab
->table
[code
].nexttable
);
1621 struct deflate_decompress_ctx
{
1622 struct table
*staticlentable
, *staticdisttable
;
1623 struct table
*currlentable
, *currdisttable
, *lenlentable
;
1626 TREES_HDR
, TREES_LENLEN
, TREES_LEN
, TREES_LENREP
,
1627 INBLK
, GOTLENSYM
, GOTLEN
, GOTDISTSYM
,
1628 UNCOMP_LEN
, UNCOMP_NLEN
, UNCOMP_DATA
,
1629 END
, ADLER1
, ADLER2
, FINALSPIN
1631 int sym
, hlit
, hdist
, hclen
, lenptr
, lenextrabits
, lenaddon
, len
,
1634 unsigned char lenlen
[19];
1635 unsigned char lengths
[286 + 32];
1638 unsigned char window
[WINSIZE
];
1640 unsigned char *outblk
;
1641 int outlen
, outsize
;
1643 unsigned long adler32
;
1646 deflate_decompress_ctx
*deflate_decompress_new(int type
)
1648 deflate_decompress_ctx
*dctx
= snew(deflate_decompress_ctx
);
1649 unsigned char lengths
[288];
1651 memset(lengths
, 8, 144);
1652 memset(lengths
+ 144, 9, 256 - 144);
1653 memset(lengths
+ 256, 7, 280 - 256);
1654 memset(lengths
+ 280, 8, 288 - 280);
1655 dctx
->staticlentable
= mktable(lengths
, 288);
1656 memset(lengths
, 5, 32);
1657 dctx
->staticdisttable
= mktable(lengths
, 32);
1658 if (type
== DEFLATE_TYPE_BARE
)
1659 dctx
->state
= OUTSIDEBLK
;
1661 dctx
->state
= START
;
1662 dctx
->currlentable
= dctx
->currdisttable
= dctx
->lenlentable
= NULL
;
1667 dctx
->lastblock
= FALSE
;
1673 void deflate_decompress_free(deflate_decompress_ctx
*dctx
)
1675 if (dctx
->currlentable
&& dctx
->currlentable
!= dctx
->staticlentable
)
1676 freetable(&dctx
->currlentable
);
1677 if (dctx
->currdisttable
&& dctx
->currdisttable
!= dctx
->staticdisttable
)
1678 freetable(&dctx
->currdisttable
);
1679 if (dctx
->lenlentable
)
1680 freetable(&dctx
->lenlentable
);
1681 freetable(&dctx
->staticlentable
);
1682 freetable(&dctx
->staticdisttable
);
1686 static int huflookup(unsigned long *bitsp
, int *nbitsp
, struct table
*tab
)
1688 unsigned long bits
= *bitsp
;
1689 int nbits
= *nbitsp
;
1691 struct tableentry
*ent
;
1692 ent
= &tab
->table
[bits
& tab
->mask
];
1693 if (ent
->nbits
> nbits
)
1694 return -1; /* not enough data */
1695 bits
>>= ent
->nbits
;
1696 nbits
-= ent
->nbits
;
1697 if (ent
->code
== -1)
1698 tab
= ent
->nexttable
;
1707 * There was a missing entry in the table, presumably
1708 * due to an invalid Huffman table description, and the
1709 * subsequent data has attempted to use the missing
1710 * entry. Return a decoding failure.
1717 static void emit_char(deflate_decompress_ctx
*dctx
, int c
)
1719 dctx
->window
[dctx
->winpos
] = c
;
1720 dctx
->winpos
= (dctx
->winpos
+ 1) & (WINSIZE
- 1);
1721 if (dctx
->outlen
>= dctx
->outsize
) {
1722 dctx
->outsize
= dctx
->outlen
+ 512;
1723 dctx
->outblk
= sresize(dctx
->outblk
, dctx
->outsize
, unsigned char);
1725 if (dctx
->type
== DEFLATE_TYPE_ZLIB
) {
1726 unsigned char uc
= c
;
1727 dctx
->adler32
= adler32_update(dctx
->adler32
, &uc
, 1);
1729 dctx
->outblk
[dctx
->outlen
++] = c
;
1732 #define EATBITS(n) ( dctx->nbits -= (n), dctx->bits >>= (n) )
1734 int deflate_decompress_data(deflate_decompress_ctx
*dctx
,
1735 const void *vblock
, int len
,
1736 void **outblock
, int *outlen
)
1738 const coderecord
*rec
;
1739 const unsigned char *block
= (const unsigned char *)vblock
;
1740 int code
, bfinal
, btype
, rep
, dist
, nlen
, header
, adler
;
1742 dctx
->outblk
= snewn(256, unsigned char);
1743 dctx
->outsize
= 256;
1746 while (len
> 0 || dctx
->nbits
> 0) {
1747 while (dctx
->nbits
< 24 && len
> 0) {
1748 dctx
->bits
|= (*block
++) << dctx
->nbits
;
1752 switch (dctx
->state
) {
1754 /* Expect 16-bit zlib header. */
1755 if (dctx
->nbits
< 16)
1756 goto finished
; /* done all we can */
1759 * The header is stored as a big-endian 16-bit integer,
1760 * in contrast to the general little-endian policy in
1761 * the rest of the format :-(
1763 header
= (((dctx
->bits
& 0xFF00) >> 8) |
1764 ((dctx
->bits
& 0x00FF) << 8));
1770 * - bits 8-11 should be 1000 (Deflate/RFC1951)
1771 * - bits 12-15 should be at most 0111 (window size)
1772 * - bit 5 should be zero (no dictionary present)
1773 * - we don't care about bits 6-7 (compression rate)
1774 * - bits 0-4 should be set up to make the whole thing
1775 * a multiple of 31 (checksum).
1777 if ((header
& 0x0F00) != 0x0800 ||
1778 (header
& 0xF000) > 0x7000 ||
1779 (header
& 0x0020) != 0x0000 ||
1783 dctx
->state
= OUTSIDEBLK
;
1786 /* Expect 3-bit block header. */
1787 if (dctx
->nbits
< 3)
1788 goto finished
; /* done all we can */
1789 bfinal
= dctx
->bits
& 1;
1791 dctx
->lastblock
= TRUE
;
1793 btype
= dctx
->bits
& 3;
1796 int to_eat
= dctx
->nbits
& 7;
1797 dctx
->state
= UNCOMP_LEN
;
1798 EATBITS(to_eat
); /* align to byte boundary */
1799 } else if (btype
== 1) {
1800 dctx
->currlentable
= dctx
->staticlentable
;
1801 dctx
->currdisttable
= dctx
->staticdisttable
;
1802 dctx
->state
= INBLK
;
1803 } else if (btype
== 2) {
1804 dctx
->state
= TREES_HDR
;
1806 debug(("recv: bfinal=%d btype=%d\n", bfinal
, btype
));
1810 * Dynamic block header. Five bits of HLIT, five of
1811 * HDIST, four of HCLEN.
1813 if (dctx
->nbits
< 5 + 5 + 4)
1814 goto finished
; /* done all we can */
1815 dctx
->hlit
= 257 + (dctx
->bits
& 31);
1817 dctx
->hdist
= 1 + (dctx
->bits
& 31);
1819 dctx
->hclen
= 4 + (dctx
->bits
& 15);
1821 debug(("recv: hlit=%d hdist=%d hclen=%d\n", dctx
->hlit
,
1822 dctx
->hdist
, dctx
->hclen
));
1824 dctx
->state
= TREES_LENLEN
;
1825 memset(dctx
->lenlen
, 0, sizeof(dctx
->lenlen
));
1828 if (dctx
->nbits
< 3)
1830 while (dctx
->lenptr
< dctx
->hclen
&& dctx
->nbits
>= 3) {
1831 dctx
->lenlen
[lenlenmap
[dctx
->lenptr
++]] =
1832 (unsigned char) (dctx
->bits
& 7);
1833 debug(("recv: lenlen %d\n", (unsigned char) (dctx
->bits
& 7)));
1836 if (dctx
->lenptr
== dctx
->hclen
) {
1837 dctx
->lenlentable
= mktable(dctx
->lenlen
, 19);
1838 dctx
->state
= TREES_LEN
;
1843 if (dctx
->lenptr
>= dctx
->hlit
+ dctx
->hdist
) {
1844 dctx
->currlentable
= mktable(dctx
->lengths
, dctx
->hlit
);
1845 dctx
->currdisttable
= mktable(dctx
->lengths
+ dctx
->hlit
,
1847 freetable(&dctx
->lenlentable
);
1848 dctx
->lenlentable
= NULL
;
1849 dctx
->state
= INBLK
;
1852 code
= huflookup(&dctx
->bits
, &dctx
->nbits
, dctx
->lenlentable
);
1853 debug(("recv: codelen %d\n", code
));
1859 dctx
->lengths
[dctx
->lenptr
++] = code
;
1861 dctx
->lenextrabits
= (code
== 16 ?
2 : code
== 17 ?
3 : 7);
1862 dctx
->lenaddon
= (code
== 18 ?
11 : 3);
1863 dctx
->lenrep
= (code
== 16 && dctx
->lenptr
> 0 ?
1864 dctx
->lengths
[dctx
->lenptr
- 1] : 0);
1865 dctx
->state
= TREES_LENREP
;
1869 if (dctx
->nbits
< dctx
->lenextrabits
)
1873 (dctx
->bits
& ((1 << dctx
->lenextrabits
) - 1));
1874 EATBITS(dctx
->lenextrabits
);
1875 if (dctx
->lenextrabits
)
1876 debug(("recv: codelen-extrabits %d/%d\n", rep
- dctx
->lenaddon
,
1877 dctx
->lenextrabits
));
1878 while (rep
> 0 && dctx
->lenptr
< dctx
->hlit
+ dctx
->hdist
) {
1879 dctx
->lengths
[dctx
->lenptr
] = dctx
->lenrep
;
1883 dctx
->state
= TREES_LEN
;
1886 code
= huflookup(&dctx
->bits
, &dctx
->nbits
, dctx
->currlentable
);
1887 debug(("recv: litlen %d\n", code
));
1893 emit_char(dctx
, code
);
1894 else if (code
== 256) {
1895 if (dctx
->lastblock
)
1898 dctx
->state
= OUTSIDEBLK
;
1899 if (dctx
->currlentable
!= dctx
->staticlentable
) {
1900 freetable(&dctx
->currlentable
);
1901 dctx
->currlentable
= NULL
;
1903 if (dctx
->currdisttable
!= dctx
->staticdisttable
) {
1904 freetable(&dctx
->currdisttable
);
1905 dctx
->currdisttable
= NULL
;
1907 } else if (code
< 286) { /* static tree can give >285; ignore */
1908 dctx
->state
= GOTLENSYM
;
1913 rec
= &lencodes
[dctx
->sym
- 257];
1914 if (dctx
->nbits
< rec
->extrabits
)
1917 rec
->min
+ (dctx
->bits
& ((1 << rec
->extrabits
) - 1));
1919 debug(("recv: litlen-extrabits %d/%d\n",
1920 dctx
->len
- rec
->min
, rec
->extrabits
));
1921 EATBITS(rec
->extrabits
);
1922 dctx
->state
= GOTLEN
;
1925 code
= huflookup(&dctx
->bits
, &dctx
->nbits
, dctx
->currdisttable
);
1926 debug(("recv: dist %d\n", code
));
1931 dctx
->state
= GOTDISTSYM
;
1935 rec
= &distcodes
[dctx
->sym
];
1936 if (dctx
->nbits
< rec
->extrabits
)
1938 dist
= rec
->min
+ (dctx
->bits
& ((1 << rec
->extrabits
) - 1));
1940 debug(("recv: dist-extrabits %d/%d\n",
1941 dist
- rec
->min
, rec
->extrabits
));
1942 EATBITS(rec
->extrabits
);
1943 dctx
->state
= INBLK
;
1945 emit_char(dctx
, dctx
->window
[(dctx
->winpos
- dist
) &
1950 * Uncompressed block. We expect to see a 16-bit LEN.
1952 if (dctx
->nbits
< 16)
1954 dctx
->uncomplen
= dctx
->bits
& 0xFFFF;
1956 dctx
->state
= UNCOMP_NLEN
;
1960 * Uncompressed block. We expect to see a 16-bit NLEN,
1961 * which should be the one's complement of the previous
1964 if (dctx
->nbits
< 16)
1966 nlen
= dctx
->bits
& 0xFFFF;
1968 if (dctx
->uncomplen
== 0)
1969 dctx
->state
= OUTSIDEBLK
; /* block is empty */
1971 dctx
->state
= UNCOMP_DATA
;
1974 if (dctx
->nbits
< 8)
1976 emit_char(dctx
, dctx
->bits
& 0xFF);
1978 if (--dctx
->uncomplen
== 0)
1979 dctx
->state
= OUTSIDEBLK
; /* end of uncompressed block */
1983 * End of compressed data. We align to a byte boundary,
1984 * and then look for format-specific trailer data.
1987 int to_eat
= dctx
->nbits
& 7;
1990 if (dctx
->type
== DEFLATE_TYPE_ZLIB
)
1991 dctx
->state
= ADLER1
;
1993 dctx
->state
= FINALSPIN
;
1996 if (dctx
->nbits
< 16)
1998 adler
= (dctx
->bits
& 0xFF) << 8;
2000 adler
|= (dctx
->bits
& 0xFF);
2002 if (adler
!= ((dctx
->adler32
>> 16) & 0xFFFF))
2004 dctx
->state
= ADLER2
;
2007 if (dctx
->nbits
< 16)
2009 adler
= (dctx
->bits
& 0xFF) << 8;
2011 adler
|= (dctx
->bits
& 0xFF);
2013 if (adler
!= (dctx
->adler32
& 0xFFFF))
2015 dctx
->state
= FINALSPIN
;
2018 /* Just ignore any trailing garbage on the data stream. */
2019 EATBITS(dctx
->nbits
);
2025 *outblock
= dctx
->outblk
;
2026 *outlen
= dctx
->outlen
;
2030 sfree(dctx
->outblk
);
2031 *outblock
= dctx
->outblk
= NULL
;
2038 int main(int argc
, char **argv
)
2040 unsigned char buf
[65536], *outbuf
;
2042 deflate_decompress_ctx
*dhandle
;
2043 deflate_compress_ctx
*chandle
;
2044 int type
= DEFLATE_TYPE_ZLIB
, opts
= TRUE
, compress
= FALSE
;
2045 char *filename
= NULL
;
2051 if (p
[0] == '-' && opts
) {
2052 if (!strcmp(p
, "-d"))
2053 type
= DEFLATE_TYPE_BARE
;
2054 if (!strcmp(p
, "-c"))
2056 else if (!strcmp(p
, "--"))
2057 opts
= FALSE
; /* next thing is filename */
2059 fprintf(stderr
, "unknown command line option '%s'\n", p
);
2062 } else if (!filename
) {
2065 fprintf(stderr
, "can only handle one filename\n");
2071 chandle
= deflate_compress_new(type
);
2074 dhandle
= deflate_decompress_new(type
);
2079 fp
= fopen(filename
, "rb");
2085 fprintf(stderr
, "unable to open '%s'\n", filename
);
2090 ret
= fread(buf
, 1, sizeof(buf
), fp
);
2093 deflate_decompress_data(dhandle
, buf
, ret
,
2094 (void **)&outbuf
, &outlen
);
2097 deflate_compress_data(chandle
, buf
, ret
, DEFLATE_NO_FLUSH
,
2098 (void **)&outbuf
, &outlen
);
2100 deflate_compress_data(chandle
, buf
, ret
, DEFLATE_END_OF_DATA
,
2101 (void **)&outbuf
, &outlen
);
2105 fwrite(outbuf
, 1, outlen
, stdout
);
2107 } else if (dhandle
) {
2108 fprintf(stderr
, "decoding error\n");
2114 deflate_decompress_free(dhandle
);
2116 deflate_compress_free(chandle
);
2128 int main(int argc
, char **argv
)
2130 char *filename
= NULL
;
2132 deflate_compress_ctx
*chandle
;
2133 deflate_decompress_ctx
*dhandle
;
2134 unsigned char buf
[65536], *outbuf
, *outbuf2
;
2135 int ret
, outlen
, outlen2
;
2136 int dlen
= 0, clen
= 0;
2142 if (p
[0] == '-' && opts
) {
2143 if (!strcmp(p
, "--"))
2144 opts
= FALSE
; /* next thing is filename */
2146 fprintf(stderr
, "unknown command line option '%s'\n", p
);
2149 } else if (!filename
) {
2152 fprintf(stderr
, "can only handle one filename\n");
2158 fp
= fopen(filename
, "rb");
2164 fprintf(stderr
, "unable to open '%s'\n", filename
);
2168 chandle
= deflate_compress_new(DEFLATE_TYPE_ZLIB
);
2169 dhandle
= deflate_decompress_new(DEFLATE_TYPE_ZLIB
);
2172 ret
= fread(buf
, 1, sizeof(buf
), fp
);
2174 deflate_compress_data(chandle
, NULL
, 0, DEFLATE_END_OF_DATA
,
2175 (void **)&outbuf
, &outlen
);
2178 deflate_compress_data(chandle
, buf
, ret
, DEFLATE_NO_FLUSH
,
2179 (void **)&outbuf
, &outlen
);
2183 deflate_decompress_data(dhandle
, outbuf
, outlen
,
2184 (void **)&outbuf2
, &outlen2
);
2188 fwrite(outbuf2
, 1, outlen2
, stdout
);
2191 fprintf(stderr
, "decoding error\n");
2197 fprintf(stderr
, "%d plaintext -> %d compressed\n", dlen
, clen
);