blob: 71505698c6590adadc298ecd5cbd6ed84f4d01c5 [file] [log] [blame]
Erik Andersene49d5ec2000-02-08 19:58:47 +00001/* vi: set sw=4 ts=4: */
Erik Andersen61677fe2000-04-13 01:18:56 +00002/*
3 * Gzip implementation for busybox
Eric Andersencc8ed391999-10-05 16:24:54 +00004 *
Erik Andersen61677fe2000-04-13 01:18:56 +00005 * Based on GNU gzip Copyright (C) 1992-1993 Jean-loup Gailly.
6 *
7 * Originally adjusted for busybox by Charles P. Wright <cpw@unix.asb.com>
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00008 * "this is a stripped down version of gzip I put into busybox, it does
9 * only standard in to standard out with -9 compression. It also requires
10 * the zcat module for some important functions."
Erik Andersen61677fe2000-04-13 01:18:56 +000011 *
Eric Andersenc7bda1c2004-03-15 08:29:22 +000012 * Adjusted further by Erik Andersen <andersen@codepoet.org> to support
13 * files as well as stdin/stdout, and to generally behave itself wrt
Erik Andersen61677fe2000-04-13 01:18:56 +000014 * command line handling.
15 *
Bernhard Reutner-Fischer20f40002006-01-30 17:17:14 +000016 * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
Eric Andersencc8ed391999-10-05 16:24:54 +000017 */
Eric Andersencc8ed391999-10-05 16:24:54 +000018
Denis Vlasenko2f6df7f2007-01-07 19:44:35 +000019/* big objects in bss:
20 * 00000020 b bl_count
21 * 00000074 b base_length
22 * 00000078 b base_dist
23 * 00000078 b static_dtree
24 * 0000009c b bl_tree
25 * 000000f4 b dyn_dtree
26 * 00000100 b length_code
27 * 00000200 b dist_code
28 * 0000023d b depth
29 * 00000400 b flag_buf
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +000030 * 0000047a b heap
Denis Vlasenko2f6df7f2007-01-07 19:44:35 +000031 * 00000480 b static_ltree
32 * 000008f4 b dyn_ltree
Denis Vlasenko2f6df7f2007-01-07 19:44:35 +000033 */
34
Denis Vlasenkobb119d02006-10-01 16:44:04 +000035/* TODO: full support for -v for DESKTOP
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +000036 * "/usr/bin/gzip -v a bogus aa" should say:
Denis Vlasenkobb119d02006-10-01 16:44:04 +000037a: 85.1% -- replaced with a.gz
38gzip: bogus: No such file or directory
39aa: 85.1% -- replaced with aa.gz
40*/
Denis Vlasenko97a8dd32006-10-01 15:55:11 +000041
Denis Vlasenkob6adbf12007-05-26 19:00:18 +000042#include "libbb.h"
Denis Vlasenko1a9e9bd2008-11-01 12:54:56 +000043#include "unarchive.h"
Eric Andersencbe31da2001-02-20 06:14:08 +000044
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +000045
46/* ===========================================================================
47 */
48//#define DEBUG 1
49/* Diagnostic functions */
50#ifdef DEBUG
Denis Vlasenko51742f42007-04-12 00:32:05 +000051# define Assert(cond,msg) { if (!(cond)) bb_error_msg(msg); }
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +000052# define Trace(x) fprintf x
Denis Vlasenkob71c6682007-07-21 15:08:09 +000053# define Tracev(x) {if (verbose) fprintf x; }
54# define Tracevv(x) {if (verbose > 1) fprintf x; }
55# define Tracec(c,x) {if (verbose && (c)) fprintf x; }
56# define Tracecv(c,x) {if (verbose > 1 && (c)) fprintf x; }
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +000057#else
58# define Assert(cond,msg)
59# define Trace(x)
60# define Tracev(x)
61# define Tracevv(x)
62# define Tracec(c,x)
63# define Tracecv(c,x)
64#endif
65
66
67/* ===========================================================================
68 */
69#define SMALL_MEM
70
Eric Andersencc8ed391999-10-05 16:24:54 +000071#ifndef INBUFSIZ
72# ifdef SMALL_MEM
Erik Andersene49d5ec2000-02-08 19:58:47 +000073# define INBUFSIZ 0x2000 /* input buffer size */
Eric Andersencc8ed391999-10-05 16:24:54 +000074# else
Erik Andersene49d5ec2000-02-08 19:58:47 +000075# define INBUFSIZ 0x8000 /* input buffer size */
Eric Andersencc8ed391999-10-05 16:24:54 +000076# endif
77#endif
Denis Vlasenkoad403412007-01-07 19:37:42 +000078
Eric Andersencc8ed391999-10-05 16:24:54 +000079#ifndef OUTBUFSIZ
80# ifdef SMALL_MEM
Erik Andersene49d5ec2000-02-08 19:58:47 +000081# define OUTBUFSIZ 8192 /* output buffer size */
Eric Andersencc8ed391999-10-05 16:24:54 +000082# else
Erik Andersene49d5ec2000-02-08 19:58:47 +000083# define OUTBUFSIZ 16384 /* output buffer size */
Eric Andersencc8ed391999-10-05 16:24:54 +000084# endif
85#endif
Eric Andersencc8ed391999-10-05 16:24:54 +000086
87#ifndef DIST_BUFSIZE
88# ifdef SMALL_MEM
Erik Andersene49d5ec2000-02-08 19:58:47 +000089# define DIST_BUFSIZE 0x2000 /* buffer for distances, see trees.c */
Eric Andersencc8ed391999-10-05 16:24:54 +000090# else
Erik Andersene49d5ec2000-02-08 19:58:47 +000091# define DIST_BUFSIZE 0x8000 /* buffer for distances, see trees.c */
Eric Andersencc8ed391999-10-05 16:24:54 +000092# endif
93#endif
94
Eric Andersencc8ed391999-10-05 16:24:54 +000095/* gzip flag byte */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +000096#define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
97#define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
98#define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
99#define ORIG_NAME 0x08 /* bit 3 set: original file name present */
100#define COMMENT 0x10 /* bit 4 set: file comment present */
101#define RESERVED 0xC0 /* bit 6,7: reserved */
Eric Andersencc8ed391999-10-05 16:24:54 +0000102
103/* internal file attribute */
104#define UNKNOWN 0xffff
105#define BINARY 0
106#define ASCII 1
107
108#ifndef WSIZE
Denis Vlasenkobb119d02006-10-01 16:44:04 +0000109# define WSIZE 0x8000 /* window size--must be a power of two, and */
110#endif /* at least 32K for zip's deflate method */
Eric Andersencc8ed391999-10-05 16:24:54 +0000111
112#define MIN_MATCH 3
113#define MAX_MATCH 258
114/* The minimum and maximum match lengths */
115
116#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
117/* Minimum amount of lookahead, except at the end of the input file.
118 * See deflate.c for comments about the MIN_MATCH+1.
119 */
120
121#define MAX_DIST (WSIZE-MIN_LOOKAHEAD)
122/* In order to simplify the code, particularly on 16 bit machines, match
123 * distances are limited to MAX_DIST instead of WSIZE.
124 */
125
Denis Vlasenkoad403412007-01-07 19:37:42 +0000126#ifndef MAX_PATH_LEN
127# define MAX_PATH_LEN 1024 /* max pathname length */
128#endif
Eric Andersencc8ed391999-10-05 16:24:54 +0000129
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000130#define seekable() 0 /* force sequential output */
131#define translate_eol 0 /* no option -a yet */
Eric Andersencc8ed391999-10-05 16:24:54 +0000132
Denis Vlasenkoad403412007-01-07 19:37:42 +0000133#ifndef BITS
134# define BITS 16
135#endif
136#define INIT_BITS 9 /* Initial number of bits per code */
137
138#define BIT_MASK 0x1f /* Mask for 'number of compression bits' */
139/* Mask 0x20 is reserved to mean a fourth header byte, and 0x40 is free.
140 * It's a pity that old uncompress does not check bit 0x20. That makes
141 * extension of the format actually undesirable because old compress
142 * would just crash on the new format instead of giving a meaningful
143 * error message. It does check the number of bits, but it's more
144 * helpful to say "unsupported format, get a new version" than
145 * "can only handle 16 bits".
146 */
147
148#ifdef MAX_EXT_CHARS
149# define MAX_SUFFIX MAX_EXT_CHARS
150#else
151# define MAX_SUFFIX 30
152#endif
153
154
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000155/* ===========================================================================
156 * Compile with MEDIUM_MEM to reduce the memory requirements or
157 * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
158 * entire input file can be held in memory (not possible on 16 bit systems).
159 * Warning: defining these symbols affects HASH_BITS (see below) and thus
160 * affects the compression ratio. The compressed output
161 * is still correct, and might even be smaller in some cases.
162 */
163
164#ifdef SMALL_MEM
165# define HASH_BITS 13 /* Number of bits used to hash strings */
166#endif
167#ifdef MEDIUM_MEM
168# define HASH_BITS 14
169#endif
170#ifndef HASH_BITS
171# define HASH_BITS 15
172 /* For portability to 16 bit machines, do not use values above 15. */
173#endif
174
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000175#define HASH_SIZE (unsigned)(1<<HASH_BITS)
176#define HASH_MASK (HASH_SIZE-1)
177#define WMASK (WSIZE-1)
178/* HASH_SIZE and WSIZE must be powers of two */
179#ifndef TOO_FAR
180# define TOO_FAR 4096
181#endif
182/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
183
184
185/* ===========================================================================
Denis Vlasenko3ae6f342007-01-07 19:44:57 +0000186 * These types are not really 'char', 'short' and 'long'
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000187 */
Denis Vlasenko3ae6f342007-01-07 19:44:57 +0000188typedef uint8_t uch;
189typedef uint16_t ush;
190typedef uint32_t ulg;
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +0000191typedef int32_t lng;
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000192
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000193typedef ush Pos;
194typedef unsigned IPos;
Denis Vlasenkoda799e82007-03-14 00:06:29 +0000195/* A Pos is an index in the character window. We use short instead of int to
196 * save space in the various tables. IPos is used only for parameter passing.
197 */
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000198
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000199enum {
200 WINDOW_SIZE = 2 * WSIZE,
201/* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
202 * input file length plus MIN_LOOKAHEAD.
203 */
204
205 max_chain_length = 4096,
206/* To speed up deflation, hash chains are never searched beyond this length.
207 * A higher limit improves compression ratio but degrades the speed.
208 */
209
210 max_lazy_match = 258,
211/* Attempt to find a better match only when the current match is strictly
212 * smaller than this value. This mechanism is used only for compression
213 * levels >= 4.
214 */
215
216 max_insert_length = max_lazy_match,
217/* Insert new strings in the hash table only if the match length
218 * is not greater than this length. This saves time but degrades compression.
219 * max_insert_length is used only for compression levels <= 3.
220 */
221
222 good_match = 32,
223/* Use a faster search when the previous match is longer than this */
224
225/* Values for max_lazy_match, good_match and max_chain_length, depending on
226 * the desired pack level (0..9). The values given below have been tuned to
227 * exclude worst case performance for pathological files. Better values may be
228 * found for specific files.
229 */
230
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +0000231 nice_match = 258, /* Stop searching when current match exceeds this */
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000232/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
233 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
234 * meaning.
235 */
236};
237
238
Denis Vlasenko972288e2007-03-15 00:57:01 +0000239struct globals {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000240
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000241 lng block_start;
242
243/* window position at the beginning of the current output block. Gets
244 * negative when the window is moved backwards.
245 */
246 unsigned ins_h; /* hash index of string to be inserted */
247
248#define H_SHIFT ((HASH_BITS+MIN_MATCH-1) / MIN_MATCH)
249/* Number of bits by which ins_h and del_h must be shifted at each
250 * input step. It must be such that after MIN_MATCH steps, the oldest
251 * byte no longer takes part in the hash key, that is:
252 * H_SHIFT * MIN_MATCH >= HASH_BITS
253 */
254
255 unsigned prev_length;
256
257/* Length of the best match at previous step. Matches not greater than this
258 * are discarded. This is used in the lazy match evaluation.
259 */
260
261 unsigned strstart; /* start of string to insert */
262 unsigned match_start; /* start of matching string */
263 unsigned lookahead; /* number of valid bytes ahead in window */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000264
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +0000265/* ===========================================================================
266 */
267#define DECLARE(type, array, size) \
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000268 type * array
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +0000269#define ALLOC(type, array, size) \
Denys Vlasenko167cd702009-05-18 13:08:57 +0200270 array = xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type))
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +0000271#define FREE(array) \
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000272 do { free(array); array = NULL; } while (0)
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +0000273
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000274 /* global buffers */
Eric Andersencc8ed391999-10-05 16:24:54 +0000275
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000276 /* buffer for literals or lengths */
277 /* DECLARE(uch, l_buf, LIT_BUFSIZE); */
278 DECLARE(uch, l_buf, INBUFSIZ);
Eric Andersencc8ed391999-10-05 16:24:54 +0000279
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000280 DECLARE(ush, d_buf, DIST_BUFSIZE);
281 DECLARE(uch, outbuf, OUTBUFSIZ);
Eric Andersencc8ed391999-10-05 16:24:54 +0000282
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000283/* Sliding window. Input bytes are read into the second half of the window,
284 * and move to the first half later to keep a dictionary of at least WSIZE
285 * bytes. With this organization, matches are limited to a distance of
286 * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
287 * performed with a length multiple of the block size. Also, it limits
288 * the window size to 64K, which is quite useful on MSDOS.
289 * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
290 * be less efficient).
291 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000292 DECLARE(uch, window, 2L * WSIZE);
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000293
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000294/* Link to older string with same hash index. To limit the size of this
295 * array to 64K, this link is maintained only for the last 32K strings.
296 * An index in this array is thus a window index modulo 32K.
297 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000298 /* DECLARE(Pos, prev, WSIZE); */
299 DECLARE(ush, prev, 1L << BITS);
Eric Andersencc8ed391999-10-05 16:24:54 +0000300
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +0000301/* Heads of the hash chains or 0. */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000302 /* DECLARE(Pos, head, 1<<HASH_BITS); */
303#define head (G1.prev + WSIZE) /* hash head (see deflate.c) */
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +0000304
Denis Vlasenko3ae6f342007-01-07 19:44:57 +0000305/* number of input bytes */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000306 ulg isize; /* only 32 bits stored in .gz file */
Denis Vlasenkoad403412007-01-07 19:37:42 +0000307
Denis Vlasenkofe42d172007-03-14 00:08:28 +0000308/* bbox always use stdin/stdout */
309#define ifd STDIN_FILENO /* input file descriptor */
310#define ofd STDOUT_FILENO /* output file descriptor */
Denis Vlasenko3ae6f342007-01-07 19:44:57 +0000311
Bernhard Reutner-Fischerd591a362006-08-20 17:35:13 +0000312#ifdef DEBUG
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000313 unsigned insize; /* valid bytes in l_buf */
Bernhard Reutner-Fischerd591a362006-08-20 17:35:13 +0000314#endif
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000315 unsigned outcnt; /* bytes in output buffer */
Glenn L McGrathf58efb52001-03-28 05:35:16 +0000316
Denis Vlasenkofe42d172007-03-14 00:08:28 +0000317 smallint eofile; /* flag set at end of input file */
Denis Vlasenkoad403412007-01-07 19:37:42 +0000318
319/* ===========================================================================
320 * Local data used by the "bit string" routines.
321 */
322
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000323 unsigned short bi_buf;
Denis Vlasenkoad403412007-01-07 19:37:42 +0000324
325/* Output buffer. bits are inserted starting at the bottom (least significant
326 * bits).
327 */
328
329#undef BUF_SIZE
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000330#define BUF_SIZE (8 * sizeof(G1.bi_buf))
Denis Vlasenkoad403412007-01-07 19:37:42 +0000331/* Number of bits used within bi_buf. (bi_buf might be implemented on
332 * more than 16 bits on some systems.)
333 */
334
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000335 int bi_valid;
Denis Vlasenkoad403412007-01-07 19:37:42 +0000336
337/* Current input function. Set to mem_read for in-memory compression */
338
339#ifdef DEBUG
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000340 ulg bits_sent; /* bit length of the compressed data */
Denis Vlasenkoad403412007-01-07 19:37:42 +0000341#endif
342
Denis Vlasenkoda799e82007-03-14 00:06:29 +0000343 uint32_t *crc_32_tab;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000344 uint32_t crc; /* shift register contents */
345};
346
Denis Vlasenko07766bb2007-03-14 00:06:51 +0000347#define G1 (*(ptr_to_globals - 1))
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000348
Denis Vlasenkoad403412007-01-07 19:37:42 +0000349
350/* ===========================================================================
Denis Vlasenkoed0f6db2007-01-07 19:38:26 +0000351 * Write the output buffer outbuf[0..outcnt-1] and update bytes_out.
352 * (used for the compressed data only)
353 */
354static void flush_outbuf(void)
355{
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000356 if (G1.outcnt == 0)
Denis Vlasenkoed0f6db2007-01-07 19:38:26 +0000357 return;
358
Denis Vlasenkofe42d172007-03-14 00:08:28 +0000359 xwrite(ofd, (char *) G1.outbuf, G1.outcnt);
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000360 G1.outcnt = 0;
Denis Vlasenkoed0f6db2007-01-07 19:38:26 +0000361}
362
363
364/* ===========================================================================
Denis Vlasenkoad403412007-01-07 19:37:42 +0000365 */
366/* put_8bit is used for the compressed output */
367#define put_8bit(c) \
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000368do { \
369 G1.outbuf[G1.outcnt++] = (c); \
370 if (G1.outcnt == OUTBUFSIZ) flush_outbuf(); \
371} while (0)
Denis Vlasenkoad403412007-01-07 19:37:42 +0000372
Aaron Lehmannb9df4702001-12-06 03:22:43 +0000373/* Output a 16 bit value, lsb first */
Denis Vlasenkoad403412007-01-07 19:37:42 +0000374static void put_16bit(ush w)
Aaron Lehmannb9df4702001-12-06 03:22:43 +0000375{
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000376 if (G1.outcnt < OUTBUFSIZ - 2) {
377 G1.outbuf[G1.outcnt++] = w;
378 G1.outbuf[G1.outcnt++] = w >> 8;
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000379 } else {
Denis Vlasenkoad403412007-01-07 19:37:42 +0000380 put_8bit(w);
381 put_8bit(w >> 8);
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000382 }
Aaron Lehmannb9df4702001-12-06 03:22:43 +0000383}
384
Denis Vlasenkoad403412007-01-07 19:37:42 +0000385static void put_32bit(ulg n)
Glenn L McGrathf58efb52001-03-28 05:35:16 +0000386{
Denis Vlasenkoad403412007-01-07 19:37:42 +0000387 put_16bit(n);
388 put_16bit(n >> 16);
389}
390
Glenn L McGrathf58efb52001-03-28 05:35:16 +0000391/* ===========================================================================
Glenn L McGrathf58efb52001-03-28 05:35:16 +0000392 * Run a set of bytes through the crc shift register. If s is a NULL
393 * pointer, then initialize the crc shift register contents instead.
394 * Return the current crc in either case.
395 */
Rob Landleyc57ec372006-04-10 17:07:15 +0000396static uint32_t updcrc(uch * s, unsigned n)
Glenn L McGrathf58efb52001-03-28 05:35:16 +0000397{
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000398 uint32_t c = G1.crc;
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000399 while (n) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000400 c = G1.crc_32_tab[(uch)(c ^ *s++)] ^ (c >> 8);
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000401 n--;
Glenn L McGrathf58efb52001-03-28 05:35:16 +0000402 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000403 G1.crc = c;
Denis Vlasenko30551fd2007-01-07 19:38:06 +0000404 return c;
Glenn L McGrathf58efb52001-03-28 05:35:16 +0000405}
406
Denis Vlasenkoed0f6db2007-01-07 19:38:26 +0000407
408/* ===========================================================================
409 * Read a new buffer from the current input file, perform end-of-line
410 * translation, and update the crc and input file size.
411 * IN assertion: size >= 2 (for end-of-line translation)
412 */
413static unsigned file_read(void *buf, unsigned size)
414{
415 unsigned len;
416
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000417 Assert(G1.insize == 0, "l_buf not empty");
Denis Vlasenkoed0f6db2007-01-07 19:38:26 +0000418
Denis Vlasenkofe42d172007-03-14 00:08:28 +0000419 len = safe_read(ifd, buf, size);
Denis Vlasenkoed0f6db2007-01-07 19:38:26 +0000420 if (len == (unsigned)(-1) || len == 0)
421 return len;
422
423 updcrc(buf, len);
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000424 G1.isize += len;
Denis Vlasenkoed0f6db2007-01-07 19:38:26 +0000425 return len;
426}
427
428
Eric Andersencc8ed391999-10-05 16:24:54 +0000429/* ===========================================================================
Eric Andersencc8ed391999-10-05 16:24:54 +0000430 * Send a value on a given number of bits.
431 * IN assertion: length <= 16 and value fits in length bits.
432 */
Eric Andersen3073dfb2001-07-02 17:57:32 +0000433static void send_bits(int value, int length)
Eric Andersencc8ed391999-10-05 16:24:54 +0000434{
435#ifdef DEBUG
Erik Andersene49d5ec2000-02-08 19:58:47 +0000436 Tracev((stderr, " l %2d v %4x ", length, value));
437 Assert(length > 0 && length <= 15, "invalid length");
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000438 G1.bits_sent += length;
Eric Andersencc8ed391999-10-05 16:24:54 +0000439#endif
Erik Andersene49d5ec2000-02-08 19:58:47 +0000440 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
441 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
442 * unused bits in value.
443 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000444 if (G1.bi_valid > (int) BUF_SIZE - length) {
445 G1.bi_buf |= (value << G1.bi_valid);
446 put_16bit(G1.bi_buf);
447 G1.bi_buf = (ush) value >> (BUF_SIZE - G1.bi_valid);
448 G1.bi_valid += length - BUF_SIZE;
Erik Andersene49d5ec2000-02-08 19:58:47 +0000449 } else {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000450 G1.bi_buf |= value << G1.bi_valid;
451 G1.bi_valid += length;
Erik Andersene49d5ec2000-02-08 19:58:47 +0000452 }
Eric Andersencc8ed391999-10-05 16:24:54 +0000453}
454
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000455
Eric Andersencc8ed391999-10-05 16:24:54 +0000456/* ===========================================================================
457 * Reverse the first len bits of a code, using straightforward code (a faster
458 * method would use a table)
459 * IN assertion: 1 <= len <= 15
460 */
Eric Andersen3073dfb2001-07-02 17:57:32 +0000461static unsigned bi_reverse(unsigned code, int len)
Eric Andersencc8ed391999-10-05 16:24:54 +0000462{
"Robert P. J. Day"68229832006-07-01 13:08:46 +0000463 unsigned res = 0;
Erik Andersene49d5ec2000-02-08 19:58:47 +0000464
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000465 while (1) {
Erik Andersene49d5ec2000-02-08 19:58:47 +0000466 res |= code & 1;
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000467 if (--len <= 0) return res;
468 code >>= 1;
469 res <<= 1;
470 }
Eric Andersencc8ed391999-10-05 16:24:54 +0000471}
472
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000473
Eric Andersencc8ed391999-10-05 16:24:54 +0000474/* ===========================================================================
475 * Write out any remaining bits in an incomplete byte.
476 */
Mike Frysinger4e5936e2005-04-16 04:30:38 +0000477static void bi_windup(void)
Eric Andersencc8ed391999-10-05 16:24:54 +0000478{
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000479 if (G1.bi_valid > 8) {
480 put_16bit(G1.bi_buf);
481 } else if (G1.bi_valid > 0) {
482 put_8bit(G1.bi_buf);
Erik Andersene49d5ec2000-02-08 19:58:47 +0000483 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000484 G1.bi_buf = 0;
485 G1.bi_valid = 0;
Eric Andersencc8ed391999-10-05 16:24:54 +0000486#ifdef DEBUG
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000487 G1.bits_sent = (G1.bits_sent + 7) & ~7;
Eric Andersencc8ed391999-10-05 16:24:54 +0000488#endif
489}
490
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000491
Eric Andersencc8ed391999-10-05 16:24:54 +0000492/* ===========================================================================
493 * Copy a stored block to the zip file, storing first the length and its
494 * one's complement if requested.
495 */
Eric Andersen3073dfb2001-07-02 17:57:32 +0000496static void copy_block(char *buf, unsigned len, int header)
Eric Andersencc8ed391999-10-05 16:24:54 +0000497{
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000498 bi_windup(); /* align on byte boundary */
Eric Andersencc8ed391999-10-05 16:24:54 +0000499
Erik Andersene49d5ec2000-02-08 19:58:47 +0000500 if (header) {
Denis Vlasenko30551fd2007-01-07 19:38:06 +0000501 put_16bit(len);
502 put_16bit(~len);
Eric Andersencc8ed391999-10-05 16:24:54 +0000503#ifdef DEBUG
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000504 G1.bits_sent += 2 * 16;
Eric Andersencc8ed391999-10-05 16:24:54 +0000505#endif
Erik Andersene49d5ec2000-02-08 19:58:47 +0000506 }
Eric Andersencc8ed391999-10-05 16:24:54 +0000507#ifdef DEBUG
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000508 G1.bits_sent += (ulg) len << 3;
Eric Andersencc8ed391999-10-05 16:24:54 +0000509#endif
Erik Andersene49d5ec2000-02-08 19:58:47 +0000510 while (len--) {
Denis Vlasenkoad403412007-01-07 19:37:42 +0000511 put_8bit(*buf++);
Erik Andersene49d5ec2000-02-08 19:58:47 +0000512 }
Eric Andersencc8ed391999-10-05 16:24:54 +0000513}
Erik Andersene49d5ec2000-02-08 19:58:47 +0000514
Eric Andersencc8ed391999-10-05 16:24:54 +0000515
516/* ===========================================================================
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000517 * Fill the window when the lookahead becomes insufficient.
518 * Updates strstart and lookahead, and sets eofile if end of input file.
519 * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
520 * OUT assertions: at least one byte has been read, or eofile is set;
521 * file reads are performed for at least two bytes (required for the
522 * translate_eol option).
523 */
524static void fill_window(void)
525{
526 unsigned n, m;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000527 unsigned more = WINDOW_SIZE - G1.lookahead - G1.strstart;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000528 /* Amount of free space at the end of the window. */
529
530 /* If the window is almost full and there is insufficient lookahead,
531 * move the upper half to the lower one to make room in the upper half.
532 */
533 if (more == (unsigned) -1) {
534 /* Very unlikely, but possible on 16 bit machine if strstart == 0
535 * and lookahead == 1 (input done one byte at time)
536 */
537 more--;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000538 } else if (G1.strstart >= WSIZE + MAX_DIST) {
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000539 /* By the IN assertion, the window is not empty so we can't confuse
540 * more == 0 with more == 64K on a 16 bit machine.
541 */
542 Assert(WINDOW_SIZE == 2 * WSIZE, "no sliding with BIG_MEM");
543
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000544 memcpy(G1.window, G1.window + WSIZE, WSIZE);
545 G1.match_start -= WSIZE;
546 G1.strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000547
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000548 G1.block_start -= WSIZE;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000549
550 for (n = 0; n < HASH_SIZE; n++) {
551 m = head[n];
552 head[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0);
553 }
554 for (n = 0; n < WSIZE; n++) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000555 m = G1.prev[n];
556 G1.prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0);
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000557 /* If n is not on any hash chain, prev[n] is garbage but
558 * its value will never be used.
559 */
560 }
561 more += WSIZE;
562 }
563 /* At this point, more >= 2 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000564 if (!G1.eofile) {
565 n = file_read(G1.window + G1.strstart + G1.lookahead, more);
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000566 if (n == 0 || n == (unsigned) -1) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000567 G1.eofile = 1;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000568 } else {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000569 G1.lookahead += n;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000570 }
571 }
572}
573
574
575/* ===========================================================================
Eric Andersencc8ed391999-10-05 16:24:54 +0000576 * Set match_start to the longest match starting at the given string and
577 * return its length. Matches shorter or equal to prev_length are discarded,
578 * in which case the result is equal to prev_length and match_start is
579 * garbage.
580 * IN assertions: cur_match is the head of the hash chain for the current
581 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
582 */
Eric Andersen3073dfb2001-07-02 17:57:32 +0000583
Eric Andersencc8ed391999-10-05 16:24:54 +0000584/* For MSDOS, OS/2 and 386 Unix, an optimized version is in match.asm or
585 * match.s. The code is functionally equivalent, so you can use the C version
586 * if desired.
587 */
Eric Andersen3073dfb2001-07-02 17:57:32 +0000588static int longest_match(IPos cur_match)
Eric Andersencc8ed391999-10-05 16:24:54 +0000589{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000590 unsigned chain_length = max_chain_length; /* max hash chain length */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000591 uch *scan = G1.window + G1.strstart; /* current string */
"Robert P. J. Day"68229832006-07-01 13:08:46 +0000592 uch *match; /* matched string */
593 int len; /* length of current match */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000594 int best_len = G1.prev_length; /* best match length so far */
595 IPos limit = G1.strstart > (IPos) MAX_DIST ? G1.strstart - (IPos) MAX_DIST : 0;
Erik Andersene49d5ec2000-02-08 19:58:47 +0000596 /* Stop when cur_match becomes <= limit. To simplify the code,
597 * we prevent matches with the string of window index 0.
598 */
Eric Andersencc8ed391999-10-05 16:24:54 +0000599
600/* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
601 * It is easy to get rid of this optimization if necessary.
602 */
603#if HASH_BITS < 8 || MAX_MATCH != 258
Eric Andersen3073dfb2001-07-02 17:57:32 +0000604# error Code too clever
Eric Andersencc8ed391999-10-05 16:24:54 +0000605#endif
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000606 uch *strend = G1.window + G1.strstart + MAX_MATCH;
"Robert P. J. Day"68229832006-07-01 13:08:46 +0000607 uch scan_end1 = scan[best_len - 1];
608 uch scan_end = scan[best_len];
Eric Andersencc8ed391999-10-05 16:24:54 +0000609
Erik Andersene49d5ec2000-02-08 19:58:47 +0000610 /* Do not waste too much time if we already have a good match: */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000611 if (G1.prev_length >= good_match) {
Erik Andersene49d5ec2000-02-08 19:58:47 +0000612 chain_length >>= 2;
613 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000614 Assert(G1.strstart <= WINDOW_SIZE - MIN_LOOKAHEAD, "insufficient lookahead");
Eric Andersencc8ed391999-10-05 16:24:54 +0000615
Erik Andersene49d5ec2000-02-08 19:58:47 +0000616 do {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000617 Assert(cur_match < G1.strstart, "no future");
618 match = G1.window + cur_match;
Eric Andersencc8ed391999-10-05 16:24:54 +0000619
Erik Andersene49d5ec2000-02-08 19:58:47 +0000620 /* Skip to next match if the match length cannot increase
621 * or if the match length is less than 2:
622 */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000623 if (match[best_len] != scan_end ||
624 match[best_len - 1] != scan_end1 ||
625 *match != *scan || *++match != scan[1])
626 continue;
Eric Andersencc8ed391999-10-05 16:24:54 +0000627
Erik Andersene49d5ec2000-02-08 19:58:47 +0000628 /* The check at best_len-1 can be removed because it will be made
629 * again later. (This heuristic is not always a win.)
630 * It is not necessary to compare scan[2] and match[2] since they
631 * are always equal when the other bytes match, given that
632 * the hash keys are equal and that HASH_BITS >= 8.
633 */
634 scan += 2, match++;
Eric Andersencc8ed391999-10-05 16:24:54 +0000635
Erik Andersene49d5ec2000-02-08 19:58:47 +0000636 /* We check for insufficient lookahead only every 8th comparison;
637 * the 256th check will be made at strstart+258.
638 */
639 do {
640 } while (*++scan == *++match && *++scan == *++match &&
641 *++scan == *++match && *++scan == *++match &&
642 *++scan == *++match && *++scan == *++match &&
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000643 *++scan == *++match && *++scan == *++match && scan < strend);
Eric Andersencc8ed391999-10-05 16:24:54 +0000644
Erik Andersene49d5ec2000-02-08 19:58:47 +0000645 len = MAX_MATCH - (int) (strend - scan);
646 scan = strend - MAX_MATCH;
Eric Andersencc8ed391999-10-05 16:24:54 +0000647
Erik Andersene49d5ec2000-02-08 19:58:47 +0000648 if (len > best_len) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000649 G1.match_start = cur_match;
Erik Andersene49d5ec2000-02-08 19:58:47 +0000650 best_len = len;
651 if (len >= nice_match)
652 break;
Erik Andersene49d5ec2000-02-08 19:58:47 +0000653 scan_end1 = scan[best_len - 1];
654 scan_end = scan[best_len];
Erik Andersene49d5ec2000-02-08 19:58:47 +0000655 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000656 } while ((cur_match = G1.prev[cur_match & WMASK]) > limit
Erik Andersene49d5ec2000-02-08 19:58:47 +0000657 && --chain_length != 0);
Eric Andersencc8ed391999-10-05 16:24:54 +0000658
Erik Andersene49d5ec2000-02-08 19:58:47 +0000659 return best_len;
Eric Andersencc8ed391999-10-05 16:24:54 +0000660}
Eric Andersencc8ed391999-10-05 16:24:54 +0000661
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000662
Eric Andersencc8ed391999-10-05 16:24:54 +0000663#ifdef DEBUG
664/* ===========================================================================
665 * Check that the match at match_start is indeed a match.
666 */
Eric Andersen3073dfb2001-07-02 17:57:32 +0000667static void check_match(IPos start, IPos match, int length)
Eric Andersencc8ed391999-10-05 16:24:54 +0000668{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000669 /* check that the match is indeed a match */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000670 if (memcmp(G1.window + match, G1.window + start, length) != 0) {
Manuel Novoa III cad53642003-03-19 09:13:01 +0000671 bb_error_msg(" start %d, match %d, length %d", start, match, length);
672 bb_error_msg("invalid match");
Erik Andersene49d5ec2000-02-08 19:58:47 +0000673 }
674 if (verbose > 1) {
Manuel Novoa III cad53642003-03-19 09:13:01 +0000675 bb_error_msg("\\[%d,%d]", start - match, length);
Erik Andersene49d5ec2000-02-08 19:58:47 +0000676 do {
Denis Vlasenko4daad902007-09-27 10:20:47 +0000677 fputc(G1.window[start++], stderr);
Erik Andersene49d5ec2000-02-08 19:58:47 +0000678 } while (--length != 0);
679 }
Eric Andersencc8ed391999-10-05 16:24:54 +0000680}
681#else
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000682# define check_match(start, match, length) ((void)0)
Eric Andersencc8ed391999-10-05 16:24:54 +0000683#endif
684
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +0000685
Eric Andersencc8ed391999-10-05 16:24:54 +0000686/* trees.c -- output deflated data using Huffman coding
687 * Copyright (C) 1992-1993 Jean-loup Gailly
688 * This is free software; you can redistribute it and/or modify it under the
689 * terms of the GNU General Public License, see the file COPYING.
690 */
691
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000692/* PURPOSE
Eric Andersencc8ed391999-10-05 16:24:54 +0000693 * Encode various sets of source values using variable-length
694 * binary code trees.
695 *
696 * DISCUSSION
Eric Andersencc8ed391999-10-05 16:24:54 +0000697 * The PKZIP "deflation" process uses several Huffman trees. The more
698 * common source values are represented by shorter bit sequences.
699 *
700 * Each code tree is stored in the ZIP file in a compressed form
701 * which is itself a Huffman encoding of the lengths of
702 * all the code strings (in ascending order by source values).
703 * The actual code strings are reconstructed from the lengths in
704 * the UNZIP process, as described in the "application note"
705 * (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
706 *
707 * REFERENCES
Eric Andersencc8ed391999-10-05 16:24:54 +0000708 * Lynch, Thomas J.
709 * Data Compression: Techniques and Applications, pp. 53-55.
710 * Lifetime Learning Publications, 1985. ISBN 0-534-03418-7.
711 *
712 * Storer, James A.
713 * Data Compression: Methods and Theory, pp. 49-50.
714 * Computer Science Press, 1988. ISBN 0-7167-8156-5.
715 *
716 * Sedgewick, R.
717 * Algorithms, p290.
718 * Addison-Wesley, 1983. ISBN 0-201-06672-6.
719 *
720 * INTERFACE
Denis Vlasenkofe42d172007-03-14 00:08:28 +0000721 * void ct_init()
722 * Allocate the match buffer, initialize the various tables [and save
Eric Andersencc8ed391999-10-05 16:24:54 +0000723 * the location of the internal file attribute (ascii/binary) and
Denis Vlasenkofe42d172007-03-14 00:08:28 +0000724 * method (DEFLATE/STORE) -- deleted in bbox]
Eric Andersencc8ed391999-10-05 16:24:54 +0000725 *
Denis Vlasenko30551fd2007-01-07 19:38:06 +0000726 * void ct_tally(int dist, int lc);
Eric Andersencc8ed391999-10-05 16:24:54 +0000727 * Save the match info and tally the frequency counts.
728 *
Denis Vlasenko3ae6f342007-01-07 19:44:57 +0000729 * ulg flush_block(char *buf, ulg stored_len, int eof)
Eric Andersencc8ed391999-10-05 16:24:54 +0000730 * Determine the best encoding for the current block: dynamic trees,
731 * static trees or store, and output the encoded block to the zip
732 * file. Returns the total compressed length for the file so far.
Eric Andersencc8ed391999-10-05 16:24:54 +0000733 */
734
Eric Andersencc8ed391999-10-05 16:24:54 +0000735#define MAX_BITS 15
736/* All codes must not exceed MAX_BITS bits */
737
738#define MAX_BL_BITS 7
739/* Bit length codes must not exceed MAX_BL_BITS bits */
740
741#define LENGTH_CODES 29
742/* number of length codes, not counting the special END_BLOCK code */
743
744#define LITERALS 256
745/* number of literal bytes 0..255 */
746
747#define END_BLOCK 256
748/* end of block literal code */
749
750#define L_CODES (LITERALS+1+LENGTH_CODES)
751/* number of Literal or Length codes, including the END_BLOCK code */
752
753#define D_CODES 30
754/* number of distance codes */
755
756#define BL_CODES 19
757/* number of codes used to transfer the bit lengths */
758
Eric Andersen39eb0402001-08-22 04:15:47 +0000759/* extra bits for each length code */
Denis Vlasenko6ca409e2007-08-12 20:58:27 +0000760static const uint8_t extra_lbits[LENGTH_CODES] ALIGN1 = {
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000761 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4,
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000762 4, 4, 5, 5, 5, 5, 0
763};
Eric Andersencc8ed391999-10-05 16:24:54 +0000764
Eric Andersen39eb0402001-08-22 04:15:47 +0000765/* extra bits for each distance code */
Denis Vlasenko6ca409e2007-08-12 20:58:27 +0000766static const uint8_t extra_dbits[D_CODES] ALIGN1 = {
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000767 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9,
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000768 10, 10, 11, 11, 12, 12, 13, 13
769};
Eric Andersencc8ed391999-10-05 16:24:54 +0000770
Eric Andersen39eb0402001-08-22 04:15:47 +0000771/* extra bits for each bit length code */
Denis Vlasenko6ca409e2007-08-12 20:58:27 +0000772static const uint8_t extra_blbits[BL_CODES] ALIGN1 = {
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000773 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 };
Eric Andersencc8ed391999-10-05 16:24:54 +0000774
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000775/* number of codes at each bit length for an optimal tree */
Denis Vlasenko6ca409e2007-08-12 20:58:27 +0000776static const uint8_t bl_order[BL_CODES] ALIGN1 = {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000777 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
778
Eric Andersencc8ed391999-10-05 16:24:54 +0000779#define STORED_BLOCK 0
780#define STATIC_TREES 1
781#define DYN_TREES 2
782/* The three kinds of block type */
783
784#ifndef LIT_BUFSIZE
785# ifdef SMALL_MEM
786# define LIT_BUFSIZE 0x2000
787# else
788# ifdef MEDIUM_MEM
789# define LIT_BUFSIZE 0x4000
790# else
791# define LIT_BUFSIZE 0x8000
792# endif
793# endif
794#endif
795#ifndef DIST_BUFSIZE
796# define DIST_BUFSIZE LIT_BUFSIZE
797#endif
798/* Sizes of match buffers for literals/lengths and distances. There are
799 * 4 reasons for limiting LIT_BUFSIZE to 64K:
800 * - frequencies can be kept in 16 bit counters
801 * - if compression is not successful for the first block, all input data is
802 * still in the window so we can still emit a stored block even when input
803 * comes from standard input. (This can also be done for all blocks if
804 * LIT_BUFSIZE is not greater than 32K.)
805 * - if compression is not successful for a file smaller than 64K, we can
806 * even emit a stored file instead of a stored block (saving 5 bytes).
807 * - creating new Huffman trees less frequently may not provide fast
808 * adaptation to changes in the input data statistics. (Take for
809 * example a binary file with poorly compressible code followed by
810 * a highly compressible string table.) Smaller buffer sizes give
811 * fast adaptation but have of course the overhead of transmitting trees
812 * more frequently.
813 * - I can't count above 4
814 * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
815 * memory at the expense of compression). Some optimizations would be possible
816 * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
817 */
Eric Andersencc8ed391999-10-05 16:24:54 +0000818#define REP_3_6 16
819/* repeat previous bit length 3-6 times (2 bits of repeat count) */
Eric Andersencc8ed391999-10-05 16:24:54 +0000820#define REPZ_3_10 17
821/* repeat a zero length 3-10 times (3 bits of repeat count) */
Eric Andersencc8ed391999-10-05 16:24:54 +0000822#define REPZ_11_138 18
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000823/* repeat a zero length 11-138 times (7 bits of repeat count) */
824
825/* ===========================================================================
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000826*/
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000827/* Data structure describing a single value and its code string. */
828typedef struct ct_data {
Erik Andersene49d5ec2000-02-08 19:58:47 +0000829 union {
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000830 ush freq; /* frequency count */
831 ush code; /* bit string */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000832 } fc;
833 union {
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000834 ush dad; /* father node in Huffman tree */
835 ush len; /* length of bit string */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000836 } dl;
Eric Andersencc8ed391999-10-05 16:24:54 +0000837} ct_data;
838
839#define Freq fc.freq
840#define Code fc.code
841#define Dad dl.dad
842#define Len dl.len
843
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +0000844#define HEAP_SIZE (2*L_CODES + 1)
Eric Andersencc8ed391999-10-05 16:24:54 +0000845/* maximum heap size */
846
Eric Andersencc8ed391999-10-05 16:24:54 +0000847typedef struct tree_desc {
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000848 ct_data *dyn_tree; /* the dynamic tree */
Eric Andersen3073dfb2001-07-02 17:57:32 +0000849 ct_data *static_tree; /* corresponding static tree or NULL */
Denis Vlasenko6ca409e2007-08-12 20:58:27 +0000850 const uint8_t *extra_bits; /* extra bits for each code or NULL */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000851 int extra_base; /* base index for extra_bits */
852 int elems; /* max number of elements in the tree */
853 int max_length; /* max bit length for the codes */
854 int max_code; /* largest code with non zero frequency */
Eric Andersencc8ed391999-10-05 16:24:54 +0000855} tree_desc;
856
Denis Vlasenko972288e2007-03-15 00:57:01 +0000857struct globals2 {
Eric Andersencc8ed391999-10-05 16:24:54 +0000858
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000859 ush heap[HEAP_SIZE]; /* heap used to build the Huffman trees */
860 int heap_len; /* number of elements in the heap */
861 int heap_max; /* element of largest frequency */
Eric Andersencc8ed391999-10-05 16:24:54 +0000862
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000863/* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
864 * The same heap array is used to build all trees.
865 */
Eric Andersencc8ed391999-10-05 16:24:54 +0000866
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000867 ct_data dyn_ltree[HEAP_SIZE]; /* literal and length tree */
868 ct_data dyn_dtree[2 * D_CODES + 1]; /* distance tree */
Eric Andersencc8ed391999-10-05 16:24:54 +0000869
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000870 ct_data static_ltree[L_CODES + 2];
Erik Andersene49d5ec2000-02-08 19:58:47 +0000871
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000872/* The static literal tree. Since the bit lengths are imposed, there is no
873 * need for the L_CODES extra codes used during heap construction. However
874 * The codes 286 and 287 are needed to build a canonical tree (see ct_init
875 * below).
876 */
Eric Andersencc8ed391999-10-05 16:24:54 +0000877
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000878 ct_data static_dtree[D_CODES];
879
880/* The static distance tree. (Actually a trivial tree since all codes use
881 * 5 bits.)
882 */
883
884 ct_data bl_tree[2 * BL_CODES + 1];
885
886/* Huffman tree for the bit lengths */
887
888 tree_desc l_desc;
889 tree_desc d_desc;
890 tree_desc bl_desc;
891
892 ush bl_count[MAX_BITS + 1];
Erik Andersene49d5ec2000-02-08 19:58:47 +0000893
Eric Andersencc8ed391999-10-05 16:24:54 +0000894/* The lengths of the bit length codes are sent in order of decreasing
895 * probability, to avoid transmitting the lengths for unused bit length codes.
896 */
897
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000898 uch depth[2 * L_CODES + 1];
Erik Andersene49d5ec2000-02-08 19:58:47 +0000899
Eric Andersencc8ed391999-10-05 16:24:54 +0000900/* Depth of each subtree used as tie breaker for trees of equal frequency */
901
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000902 uch length_code[MAX_MATCH - MIN_MATCH + 1];
Erik Andersene49d5ec2000-02-08 19:58:47 +0000903
Eric Andersencc8ed391999-10-05 16:24:54 +0000904/* length code for each normalized match length (0 == MIN_MATCH) */
905
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000906 uch dist_code[512];
Erik Andersene49d5ec2000-02-08 19:58:47 +0000907
Eric Andersencc8ed391999-10-05 16:24:54 +0000908/* distance codes. The first 256 values correspond to the distances
909 * 3 .. 258, the last 256 values correspond to the top 8 bits of
910 * the 15 bit distances.
911 */
912
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000913 int base_length[LENGTH_CODES];
Erik Andersene49d5ec2000-02-08 19:58:47 +0000914
Eric Andersencc8ed391999-10-05 16:24:54 +0000915/* First normalized length for each code (0 = MIN_MATCH) */
916
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000917 int base_dist[D_CODES];
Erik Andersene49d5ec2000-02-08 19:58:47 +0000918
Eric Andersencc8ed391999-10-05 16:24:54 +0000919/* First normalized distance for each code (0 = distance of 1) */
920
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000921 uch flag_buf[LIT_BUFSIZE / 8];
Erik Andersene49d5ec2000-02-08 19:58:47 +0000922
Eric Andersencc8ed391999-10-05 16:24:54 +0000923/* flag_buf is a bit array distinguishing literals from lengths in
924 * l_buf, thus indicating the presence or absence of a distance.
925 */
926
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000927 unsigned last_lit; /* running index in l_buf */
928 unsigned last_dist; /* running index in d_buf */
929 unsigned last_flags; /* running index in flag_buf */
930 uch flags; /* current flags not yet saved in flag_buf */
931 uch flag_bit; /* current bit used in flags */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000932
Eric Andersencc8ed391999-10-05 16:24:54 +0000933/* bits are filled in flags starting at bit 0 (least significant).
934 * Note: these flags are overkill in the current code since we don't
935 * take advantage of DIST_BUFSIZE == LIT_BUFSIZE.
936 */
937
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000938 ulg opt_len; /* bit length of current block with optimal trees */
939 ulg static_len; /* bit length of current block with static trees */
Eric Andersencc8ed391999-10-05 16:24:54 +0000940
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000941 ulg compressed_len; /* total bit length of compressed file */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000942};
943
Denis Vlasenko972288e2007-03-15 00:57:01 +0000944#define G2ptr ((struct globals2*)(ptr_to_globals))
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000945#define G2 (*G2ptr)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000946
Eric Andersencc8ed391999-10-05 16:24:54 +0000947
948/* ===========================================================================
Eric Andersencc8ed391999-10-05 16:24:54 +0000949 */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +0000950static void gen_codes(ct_data * tree, int max_code);
951static void build_tree(tree_desc * desc);
952static void scan_tree(ct_data * tree, int max_code);
953static void send_tree(ct_data * tree, int max_code);
954static int build_bl_tree(void);
955static void send_all_trees(int lcodes, int dcodes, int blcodes);
956static void compress_block(ct_data * ltree, ct_data * dtree);
Eric Andersencc8ed391999-10-05 16:24:54 +0000957
958
959#ifndef DEBUG
Denis Vlasenkof8241362007-01-07 19:38:42 +0000960/* Send a code of the given tree. c and tree must not have side effects */
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000961# define SEND_CODE(c, tree) send_bits(tree[c].Code, tree[c].Len)
962#else
963# define SEND_CODE(c, tree) \
Denis Vlasenkof8241362007-01-07 19:38:42 +0000964{ \
965 if (verbose > 1) bb_error_msg("\ncd %3d ",(c)); \
Denis Vlasenko150f4022007-01-13 21:06:21 +0000966 send_bits(tree[c].Code, tree[c].Len); \
Denis Vlasenkof8241362007-01-07 19:38:42 +0000967}
Eric Andersencc8ed391999-10-05 16:24:54 +0000968#endif
969
Denis Vlasenko89af56b2007-01-07 19:40:34 +0000970#define D_CODE(dist) \
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000971 ((dist) < 256 ? G2.dist_code[dist] : G2.dist_code[256 + ((dist)>>7)])
Eric Andersencc8ed391999-10-05 16:24:54 +0000972/* Mapping from a distance to a distance code. dist is the distance - 1 and
973 * must not have side effects. dist_code[256] and dist_code[257] are never
974 * used.
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000975 * The arguments must not have side effects.
Eric Andersencc8ed391999-10-05 16:24:54 +0000976 */
977
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000978
979/* ===========================================================================
980 * Initialize a new block.
981 */
982static void init_block(void)
983{
984 int n; /* iterates over tree elements */
985
986 /* Initialize the trees. */
987 for (n = 0; n < L_CODES; n++)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000988 G2.dyn_ltree[n].Freq = 0;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000989 for (n = 0; n < D_CODES; n++)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000990 G2.dyn_dtree[n].Freq = 0;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000991 for (n = 0; n < BL_CODES; n++)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000992 G2.bl_tree[n].Freq = 0;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000993
Denis Vlasenkoe930fe12007-03-14 00:06:10 +0000994 G2.dyn_ltree[END_BLOCK].Freq = 1;
995 G2.opt_len = G2.static_len = 0;
996 G2.last_lit = G2.last_dist = G2.last_flags = 0;
997 G2.flags = 0;
998 G2.flag_bit = 1;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +0000999}
Eric Andersencc8ed391999-10-05 16:24:54 +00001000
Denis Vlasenkof8241362007-01-07 19:38:42 +00001001
Eric Andersencc8ed391999-10-05 16:24:54 +00001002/* ===========================================================================
Eric Andersencc8ed391999-10-05 16:24:54 +00001003 * Restore the heap property by moving down the tree starting at node k,
1004 * exchanging a node with the smallest of its two sons if necessary, stopping
1005 * when the heap property is re-established (each father smaller than its
1006 * two sons).
1007 */
Denis Vlasenkof8241362007-01-07 19:38:42 +00001008
1009/* Compares to subtrees, using the tree depth as tie breaker when
Denis Vlasenko89af56b2007-01-07 19:40:34 +00001010 * the subtrees have equal frequency. This minimizes the worst case length. */
1011#define SMALLER(tree, n, m) \
Denis Vlasenkof8241362007-01-07 19:38:42 +00001012 (tree[n].Freq < tree[m].Freq \
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001013 || (tree[n].Freq == tree[m].Freq && G2.depth[n] <= G2.depth[m]))
Denis Vlasenkof8241362007-01-07 19:38:42 +00001014
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001015static void pqdownheap(ct_data * tree, int k)
Eric Andersencc8ed391999-10-05 16:24:54 +00001016{
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001017 int v = G2.heap[k];
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001018 int j = k << 1; /* left son of k */
Eric Andersencc8ed391999-10-05 16:24:54 +00001019
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001020 while (j <= G2.heap_len) {
Erik Andersene49d5ec2000-02-08 19:58:47 +00001021 /* Set j to the smallest of the two sons: */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001022 if (j < G2.heap_len && SMALLER(tree, G2.heap[j + 1], G2.heap[j]))
Erik Andersene49d5ec2000-02-08 19:58:47 +00001023 j++;
Eric Andersencc8ed391999-10-05 16:24:54 +00001024
Erik Andersene49d5ec2000-02-08 19:58:47 +00001025 /* Exit if v is smaller than both sons */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001026 if (SMALLER(tree, v, G2.heap[j]))
Erik Andersene49d5ec2000-02-08 19:58:47 +00001027 break;
Eric Andersencc8ed391999-10-05 16:24:54 +00001028
Erik Andersene49d5ec2000-02-08 19:58:47 +00001029 /* Exchange v with the smallest son */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001030 G2.heap[k] = G2.heap[j];
Erik Andersene49d5ec2000-02-08 19:58:47 +00001031 k = j;
1032
1033 /* And continue down the tree, setting j to the left son of k */
1034 j <<= 1;
1035 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001036 G2.heap[k] = v;
Eric Andersencc8ed391999-10-05 16:24:54 +00001037}
1038
Denis Vlasenkof8241362007-01-07 19:38:42 +00001039
Eric Andersencc8ed391999-10-05 16:24:54 +00001040/* ===========================================================================
1041 * Compute the optimal bit lengths for a tree and update the total bit length
1042 * for the current block.
1043 * IN assertion: the fields freq and dad are set, heap[heap_max] and
1044 * above are the tree nodes sorted by increasing frequency.
1045 * OUT assertions: the field len is set to the optimal bit length, the
1046 * array bl_count contains the frequencies for each bit length.
1047 * The length opt_len is updated; static_len is also updated if stree is
1048 * not null.
1049 */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001050static void gen_bitlen(tree_desc * desc)
Eric Andersencc8ed391999-10-05 16:24:54 +00001051{
Eric Andersen3073dfb2001-07-02 17:57:32 +00001052 ct_data *tree = desc->dyn_tree;
Denis Vlasenko6ca409e2007-08-12 20:58:27 +00001053 const uint8_t *extra = desc->extra_bits;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001054 int base = desc->extra_base;
1055 int max_code = desc->max_code;
1056 int max_length = desc->max_length;
Eric Andersen3073dfb2001-07-02 17:57:32 +00001057 ct_data *stree = desc->static_tree;
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001058 int h; /* heap index */
1059 int n, m; /* iterate over the tree elements */
1060 int bits; /* bit length */
1061 int xbits; /* extra bits */
1062 ush f; /* frequency */
1063 int overflow = 0; /* number of elements with bit length too large */
Eric Andersencc8ed391999-10-05 16:24:54 +00001064
Erik Andersene49d5ec2000-02-08 19:58:47 +00001065 for (bits = 0; bits <= MAX_BITS; bits++)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001066 G2.bl_count[bits] = 0;
Eric Andersencc8ed391999-10-05 16:24:54 +00001067
Erik Andersene49d5ec2000-02-08 19:58:47 +00001068 /* In a first pass, compute the optimal bit lengths (which may
1069 * overflow in the case of the bit length tree).
1070 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001071 tree[G2.heap[G2.heap_max]].Len = 0; /* root of the heap */
Eric Andersencc8ed391999-10-05 16:24:54 +00001072
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001073 for (h = G2.heap_max + 1; h < HEAP_SIZE; h++) {
1074 n = G2.heap[h];
Erik Andersene49d5ec2000-02-08 19:58:47 +00001075 bits = tree[tree[n].Dad].Len + 1;
Denis Vlasenkof8241362007-01-07 19:38:42 +00001076 if (bits > max_length) {
1077 bits = max_length;
1078 overflow++;
1079 }
Erik Andersene49d5ec2000-02-08 19:58:47 +00001080 tree[n].Len = (ush) bits;
1081 /* We overwrite tree[n].Dad which is no longer needed */
Eric Andersencc8ed391999-10-05 16:24:54 +00001082
Erik Andersene49d5ec2000-02-08 19:58:47 +00001083 if (n > max_code)
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001084 continue; /* not a leaf node */
Eric Andersencc8ed391999-10-05 16:24:54 +00001085
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001086 G2.bl_count[bits]++;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001087 xbits = 0;
1088 if (n >= base)
1089 xbits = extra[n - base];
1090 f = tree[n].Freq;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001091 G2.opt_len += (ulg) f *(bits + xbits);
Eric Andersencc8ed391999-10-05 16:24:54 +00001092
Erik Andersene49d5ec2000-02-08 19:58:47 +00001093 if (stree)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001094 G2.static_len += (ulg) f * (stree[n].Len + xbits);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001095 }
1096 if (overflow == 0)
1097 return;
Eric Andersencc8ed391999-10-05 16:24:54 +00001098
Erik Andersene49d5ec2000-02-08 19:58:47 +00001099 Trace((stderr, "\nbit length overflow\n"));
1100 /* This happens for example on obj2 and pic of the Calgary corpus */
Eric Andersencc8ed391999-10-05 16:24:54 +00001101
Erik Andersene49d5ec2000-02-08 19:58:47 +00001102 /* Find the first bit length which could increase: */
1103 do {
1104 bits = max_length - 1;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001105 while (G2.bl_count[bits] == 0)
Erik Andersene49d5ec2000-02-08 19:58:47 +00001106 bits--;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001107 G2.bl_count[bits]--; /* move one leaf down the tree */
1108 G2.bl_count[bits + 1] += 2; /* move one overflow item as its brother */
1109 G2.bl_count[max_length]--;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001110 /* The brother of the overflow item also moves one step up,
1111 * but this does not affect bl_count[max_length]
1112 */
1113 overflow -= 2;
1114 } while (overflow > 0);
1115
1116 /* Now recompute all bit lengths, scanning in increasing frequency.
1117 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
1118 * lengths instead of fixing only the wrong ones. This idea is taken
1119 * from 'ar' written by Haruhiko Okumura.)
1120 */
1121 for (bits = max_length; bits != 0; bits--) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001122 n = G2.bl_count[bits];
Erik Andersene49d5ec2000-02-08 19:58:47 +00001123 while (n != 0) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001124 m = G2.heap[--h];
Erik Andersene49d5ec2000-02-08 19:58:47 +00001125 if (m > max_code)
1126 continue;
1127 if (tree[m].Len != (unsigned) bits) {
Denis Vlasenko1a03c212007-01-07 19:39:34 +00001128 Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len, bits));
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001129 G2.opt_len += ((int32_t) bits - tree[m].Len) * tree[m].Freq;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001130 tree[m].Len = bits;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001131 }
1132 n--;
1133 }
1134 }
Eric Andersencc8ed391999-10-05 16:24:54 +00001135}
1136
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001137
Eric Andersencc8ed391999-10-05 16:24:54 +00001138/* ===========================================================================
1139 * Generate the codes for a given tree and bit counts (which need not be
1140 * optimal).
1141 * IN assertion: the array bl_count contains the bit length statistics for
1142 * the given tree and the field len is set for all tree elements.
1143 * OUT assertion: the field code is set for all tree elements of non
1144 * zero code length.
1145 */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001146static void gen_codes(ct_data * tree, int max_code)
Eric Andersencc8ed391999-10-05 16:24:54 +00001147{
Erik Andersene49d5ec2000-02-08 19:58:47 +00001148 ush next_code[MAX_BITS + 1]; /* next code value for each bit length */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001149 ush code = 0; /* running code value */
1150 int bits; /* bit index */
1151 int n; /* code index */
Eric Andersencc8ed391999-10-05 16:24:54 +00001152
Erik Andersene49d5ec2000-02-08 19:58:47 +00001153 /* The distribution counts are first used to generate the code values
1154 * without bit reversal.
1155 */
1156 for (bits = 1; bits <= MAX_BITS; bits++) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001157 next_code[bits] = code = (code + G2.bl_count[bits - 1]) << 1;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001158 }
1159 /* Check that the bit counts in bl_count are consistent. The last code
1160 * must be all ones.
1161 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001162 Assert(code + G2.bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1,
Erik Andersene49d5ec2000-02-08 19:58:47 +00001163 "inconsistent bit counts");
1164 Tracev((stderr, "\ngen_codes: max_code %d ", max_code));
Eric Andersencc8ed391999-10-05 16:24:54 +00001165
Erik Andersene49d5ec2000-02-08 19:58:47 +00001166 for (n = 0; n <= max_code; n++) {
1167 int len = tree[n].Len;
Eric Andersencc8ed391999-10-05 16:24:54 +00001168
Erik Andersene49d5ec2000-02-08 19:58:47 +00001169 if (len == 0)
1170 continue;
1171 /* Now reverse the bits */
1172 tree[n].Code = bi_reverse(next_code[len]++, len);
1173
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001174 Tracec(tree != G2.static_ltree,
Erik Andersene49d5ec2000-02-08 19:58:47 +00001175 (stderr, "\nn %3d %c l %2d c %4x (%x) ", n,
Denys Vlasenkof2cbb032009-10-23 03:16:08 +02001176 (n > ' ' ? n : ' '), len, tree[n].Code,
Erik Andersene49d5ec2000-02-08 19:58:47 +00001177 next_code[len] - 1));
1178 }
Eric Andersencc8ed391999-10-05 16:24:54 +00001179}
1180
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001181
Eric Andersencc8ed391999-10-05 16:24:54 +00001182/* ===========================================================================
1183 * Construct one Huffman tree and assigns the code bit strings and lengths.
1184 * Update the total bit length for the current block.
1185 * IN assertion: the field freq is set for all tree elements.
1186 * OUT assertions: the fields len and code are set to the optimal bit length
1187 * and corresponding code. The length opt_len is updated; static_len is
1188 * also updated if stree is not null. The field max_code is set.
1189 */
Denis Vlasenko89af56b2007-01-07 19:40:34 +00001190
1191/* Remove the smallest element from the heap and recreate the heap with
1192 * one less element. Updates heap and heap_len. */
1193
1194#define SMALLEST 1
1195/* Index within the heap array of least frequent node in the Huffman tree */
1196
1197#define PQREMOVE(tree, top) \
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001198do { \
1199 top = G2.heap[SMALLEST]; \
1200 G2.heap[SMALLEST] = G2.heap[G2.heap_len--]; \
Denis Vlasenko89af56b2007-01-07 19:40:34 +00001201 pqdownheap(tree, SMALLEST); \
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001202} while (0)
Denis Vlasenko89af56b2007-01-07 19:40:34 +00001203
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001204static void build_tree(tree_desc * desc)
Eric Andersencc8ed391999-10-05 16:24:54 +00001205{
Eric Andersen3073dfb2001-07-02 17:57:32 +00001206 ct_data *tree = desc->dyn_tree;
1207 ct_data *stree = desc->static_tree;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001208 int elems = desc->elems;
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001209 int n, m; /* iterate over heap elements */
1210 int max_code = -1; /* largest code with non zero frequency */
1211 int node = elems; /* next internal node of the tree */
Eric Andersencc8ed391999-10-05 16:24:54 +00001212
Erik Andersene49d5ec2000-02-08 19:58:47 +00001213 /* Construct the initial heap, with least frequent element in
1214 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
1215 * heap[0] is not used.
1216 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001217 G2.heap_len = 0;
1218 G2.heap_max = HEAP_SIZE;
Eric Andersencc8ed391999-10-05 16:24:54 +00001219
Erik Andersene49d5ec2000-02-08 19:58:47 +00001220 for (n = 0; n < elems; n++) {
1221 if (tree[n].Freq != 0) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001222 G2.heap[++G2.heap_len] = max_code = n;
1223 G2.depth[n] = 0;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001224 } else {
1225 tree[n].Len = 0;
1226 }
1227 }
Eric Andersencc8ed391999-10-05 16:24:54 +00001228
Erik Andersene49d5ec2000-02-08 19:58:47 +00001229 /* The pkzip format requires that at least one distance code exists,
1230 * and that at least one bit should be sent even if there is only one
1231 * possible code. So to avoid special checks later on we force at least
1232 * two codes of non zero frequency.
1233 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001234 while (G2.heap_len < 2) {
1235 int new = G2.heap[++G2.heap_len] = (max_code < 2 ? ++max_code : 0);
Eric Andersencc8ed391999-10-05 16:24:54 +00001236
Erik Andersene49d5ec2000-02-08 19:58:47 +00001237 tree[new].Freq = 1;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001238 G2.depth[new] = 0;
1239 G2.opt_len--;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001240 if (stree)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001241 G2.static_len -= stree[new].Len;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001242 /* new is 0 or 1 so it does not have extra bits */
1243 }
1244 desc->max_code = max_code;
Eric Andersencc8ed391999-10-05 16:24:54 +00001245
Erik Andersene49d5ec2000-02-08 19:58:47 +00001246 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
1247 * establish sub-heaps of increasing lengths:
1248 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001249 for (n = G2.heap_len / 2; n >= 1; n--)
Erik Andersene49d5ec2000-02-08 19:58:47 +00001250 pqdownheap(tree, n);
Eric Andersencc8ed391999-10-05 16:24:54 +00001251
Erik Andersene49d5ec2000-02-08 19:58:47 +00001252 /* Construct the Huffman tree by repeatedly combining the least two
1253 * frequent nodes.
1254 */
1255 do {
Denis Vlasenko89af56b2007-01-07 19:40:34 +00001256 PQREMOVE(tree, n); /* n = node of least frequency */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001257 m = G2.heap[SMALLEST]; /* m = node of next least frequency */
Eric Andersencc8ed391999-10-05 16:24:54 +00001258
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001259 G2.heap[--G2.heap_max] = n; /* keep the nodes sorted by frequency */
1260 G2.heap[--G2.heap_max] = m;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001261
1262 /* Create a new node father of n and m */
1263 tree[node].Freq = tree[n].Freq + tree[m].Freq;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001264 G2.depth[node] = MAX(G2.depth[n], G2.depth[m]) + 1;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001265 tree[n].Dad = tree[m].Dad = (ush) node;
Eric Andersencc8ed391999-10-05 16:24:54 +00001266#ifdef DUMP_BL_TREE
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001267 if (tree == G2.bl_tree) {
Manuel Novoa III cad53642003-03-19 09:13:01 +00001268 bb_error_msg("\nnode %d(%d), sons %d(%d) %d(%d)",
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001269 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001270 }
Eric Andersencc8ed391999-10-05 16:24:54 +00001271#endif
Erik Andersene49d5ec2000-02-08 19:58:47 +00001272 /* and insert the new node in the heap */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001273 G2.heap[SMALLEST] = node++;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001274 pqdownheap(tree, SMALLEST);
Eric Andersencc8ed391999-10-05 16:24:54 +00001275
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001276 } while (G2.heap_len >= 2);
Eric Andersencc8ed391999-10-05 16:24:54 +00001277
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001278 G2.heap[--G2.heap_max] = G2.heap[SMALLEST];
Eric Andersencc8ed391999-10-05 16:24:54 +00001279
Erik Andersene49d5ec2000-02-08 19:58:47 +00001280 /* At this point, the fields freq and dad are set. We can now
1281 * generate the bit lengths.
1282 */
Eric Andersen3073dfb2001-07-02 17:57:32 +00001283 gen_bitlen((tree_desc *) desc);
Eric Andersencc8ed391999-10-05 16:24:54 +00001284
Erik Andersene49d5ec2000-02-08 19:58:47 +00001285 /* The field len is now set, we can generate the bit codes */
Eric Andersen3073dfb2001-07-02 17:57:32 +00001286 gen_codes((ct_data *) tree, max_code);
Eric Andersencc8ed391999-10-05 16:24:54 +00001287}
1288
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001289
Eric Andersencc8ed391999-10-05 16:24:54 +00001290/* ===========================================================================
1291 * Scan a literal or distance tree to determine the frequencies of the codes
1292 * in the bit length tree. Updates opt_len to take into account the repeat
1293 * counts. (The contribution of the bit length codes will be added later
1294 * during the construction of bl_tree.)
1295 */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001296static void scan_tree(ct_data * tree, int max_code)
Eric Andersencc8ed391999-10-05 16:24:54 +00001297{
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001298 int n; /* iterates over all tree elements */
1299 int prevlen = -1; /* last emitted length */
1300 int curlen; /* length of current code */
Erik Andersene49d5ec2000-02-08 19:58:47 +00001301 int nextlen = tree[0].Len; /* length of next code */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001302 int count = 0; /* repeat count of the current code */
1303 int max_count = 7; /* max repeat count */
1304 int min_count = 4; /* min repeat count */
Eric Andersencc8ed391999-10-05 16:24:54 +00001305
Denis Vlasenko1a03c212007-01-07 19:39:34 +00001306 if (nextlen == 0) {
1307 max_count = 138;
1308 min_count = 3;
1309 }
Denis Vlasenko2f6df7f2007-01-07 19:44:35 +00001310 tree[max_code + 1].Len = 0xffff; /* guard */
Eric Andersencc8ed391999-10-05 16:24:54 +00001311
Erik Andersene49d5ec2000-02-08 19:58:47 +00001312 for (n = 0; n <= max_code; n++) {
1313 curlen = nextlen;
1314 nextlen = tree[n + 1].Len;
Denis Vlasenko2f6df7f2007-01-07 19:44:35 +00001315 if (++count < max_count && curlen == nextlen)
Erik Andersene49d5ec2000-02-08 19:58:47 +00001316 continue;
Denis Vlasenko2f6df7f2007-01-07 19:44:35 +00001317
1318 if (count < min_count) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001319 G2.bl_tree[curlen].Freq += count;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001320 } else if (curlen != 0) {
1321 if (curlen != prevlen)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001322 G2.bl_tree[curlen].Freq++;
1323 G2.bl_tree[REP_3_6].Freq++;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001324 } else if (count <= 10) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001325 G2.bl_tree[REPZ_3_10].Freq++;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001326 } else {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001327 G2.bl_tree[REPZ_11_138].Freq++;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001328 }
1329 count = 0;
1330 prevlen = curlen;
Denis Vlasenko2f6df7f2007-01-07 19:44:35 +00001331
1332 max_count = 7;
1333 min_count = 4;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001334 if (nextlen == 0) {
Denis Vlasenko1a03c212007-01-07 19:39:34 +00001335 max_count = 138;
1336 min_count = 3;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001337 } else if (curlen == nextlen) {
Denis Vlasenko1a03c212007-01-07 19:39:34 +00001338 max_count = 6;
1339 min_count = 3;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001340 }
1341 }
Eric Andersencc8ed391999-10-05 16:24:54 +00001342}
1343
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001344
Eric Andersencc8ed391999-10-05 16:24:54 +00001345/* ===========================================================================
1346 * Send a literal or distance tree in compressed form, using the codes in
1347 * bl_tree.
1348 */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001349static void send_tree(ct_data * tree, int max_code)
Eric Andersencc8ed391999-10-05 16:24:54 +00001350{
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001351 int n; /* iterates over all tree elements */
1352 int prevlen = -1; /* last emitted length */
1353 int curlen; /* length of current code */
Erik Andersene49d5ec2000-02-08 19:58:47 +00001354 int nextlen = tree[0].Len; /* length of next code */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001355 int count = 0; /* repeat count of the current code */
1356 int max_count = 7; /* max repeat count */
1357 int min_count = 4; /* min repeat count */
Eric Andersencc8ed391999-10-05 16:24:54 +00001358
Erik Andersene49d5ec2000-02-08 19:58:47 +00001359/* tree[max_code+1].Len = -1; *//* guard already set */
1360 if (nextlen == 0)
1361 max_count = 138, min_count = 3;
Eric Andersencc8ed391999-10-05 16:24:54 +00001362
Erik Andersene49d5ec2000-02-08 19:58:47 +00001363 for (n = 0; n <= max_code; n++) {
1364 curlen = nextlen;
1365 nextlen = tree[n + 1].Len;
1366 if (++count < max_count && curlen == nextlen) {
1367 continue;
1368 } else if (count < min_count) {
1369 do {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001370 SEND_CODE(curlen, G2.bl_tree);
Denis Vlasenko1a03c212007-01-07 19:39:34 +00001371 } while (--count);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001372 } else if (curlen != 0) {
1373 if (curlen != prevlen) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001374 SEND_CODE(curlen, G2.bl_tree);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001375 count--;
1376 }
1377 Assert(count >= 3 && count <= 6, " 3_6?");
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001378 SEND_CODE(REP_3_6, G2.bl_tree);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001379 send_bits(count - 3, 2);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001380 } else if (count <= 10) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001381 SEND_CODE(REPZ_3_10, G2.bl_tree);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001382 send_bits(count - 3, 3);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001383 } else {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001384 SEND_CODE(REPZ_11_138, G2.bl_tree);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001385 send_bits(count - 11, 7);
1386 }
1387 count = 0;
1388 prevlen = curlen;
1389 if (nextlen == 0) {
Denis Vlasenko1a03c212007-01-07 19:39:34 +00001390 max_count = 138;
1391 min_count = 3;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001392 } else if (curlen == nextlen) {
Denis Vlasenko1a03c212007-01-07 19:39:34 +00001393 max_count = 6;
1394 min_count = 3;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001395 } else {
Denis Vlasenko1a03c212007-01-07 19:39:34 +00001396 max_count = 7;
1397 min_count = 4;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001398 }
1399 }
Eric Andersencc8ed391999-10-05 16:24:54 +00001400}
1401
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001402
Eric Andersencc8ed391999-10-05 16:24:54 +00001403/* ===========================================================================
1404 * Construct the Huffman tree for the bit lengths and return the index in
1405 * bl_order of the last bit length code to send.
1406 */
Mike Frysinger4e5936e2005-04-16 04:30:38 +00001407static int build_bl_tree(void)
Eric Andersencc8ed391999-10-05 16:24:54 +00001408{
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001409 int max_blindex; /* index of last bit length code of non zero freq */
Eric Andersencc8ed391999-10-05 16:24:54 +00001410
Erik Andersene49d5ec2000-02-08 19:58:47 +00001411 /* Determine the bit length frequencies for literal and distance trees */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001412 scan_tree(G2.dyn_ltree, G2.l_desc.max_code);
1413 scan_tree(G2.dyn_dtree, G2.d_desc.max_code);
Eric Andersencc8ed391999-10-05 16:24:54 +00001414
Erik Andersene49d5ec2000-02-08 19:58:47 +00001415 /* Build the bit length tree: */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001416 build_tree(&G2.bl_desc);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001417 /* opt_len now includes the length of the tree representations, except
1418 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
1419 */
Eric Andersencc8ed391999-10-05 16:24:54 +00001420
Erik Andersene49d5ec2000-02-08 19:58:47 +00001421 /* Determine the number of bit length codes to send. The pkzip format
1422 * requires that at least 4 bit length codes be sent. (appnote.txt says
1423 * 3 but the actual value used is 4.)
1424 */
1425 for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001426 if (G2.bl_tree[bl_order[max_blindex]].Len != 0)
Erik Andersene49d5ec2000-02-08 19:58:47 +00001427 break;
1428 }
1429 /* Update opt_len to include the bit length tree and counts */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001430 G2.opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;
1431 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
Eric Andersencc8ed391999-10-05 16:24:54 +00001432
Erik Andersene49d5ec2000-02-08 19:58:47 +00001433 return max_blindex;
Eric Andersencc8ed391999-10-05 16:24:54 +00001434}
1435
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001436
Eric Andersencc8ed391999-10-05 16:24:54 +00001437/* ===========================================================================
1438 * Send the header for a block using dynamic Huffman trees: the counts, the
1439 * lengths of the bit length codes, the literal tree and the distance tree.
1440 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
1441 */
Eric Andersen3073dfb2001-07-02 17:57:32 +00001442static void send_all_trees(int lcodes, int dcodes, int blcodes)
Eric Andersencc8ed391999-10-05 16:24:54 +00001443{
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001444 int rank; /* index in bl_order */
Eric Andersencc8ed391999-10-05 16:24:54 +00001445
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001446 Assert(lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
Erik Andersene49d5ec2000-02-08 19:58:47 +00001447 Assert(lcodes <= L_CODES && dcodes <= D_CODES
1448 && blcodes <= BL_CODES, "too many codes");
1449 Tracev((stderr, "\nbl counts: "));
1450 send_bits(lcodes - 257, 5); /* not +255 as stated in appnote.txt */
1451 send_bits(dcodes - 1, 5);
1452 send_bits(blcodes - 4, 4); /* not -3 as stated in appnote.txt */
1453 for (rank = 0; rank < blcodes; rank++) {
1454 Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001455 send_bits(G2.bl_tree[bl_order[rank]].Len, 3);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001456 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001457 Tracev((stderr, "\nbl tree: sent %ld", G1.bits_sent));
Eric Andersencc8ed391999-10-05 16:24:54 +00001458
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001459 send_tree((ct_data *) G2.dyn_ltree, lcodes - 1); /* send the literal tree */
1460 Tracev((stderr, "\nlit tree: sent %ld", G1.bits_sent));
Eric Andersencc8ed391999-10-05 16:24:54 +00001461
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001462 send_tree((ct_data *) G2.dyn_dtree, dcodes - 1); /* send the distance tree */
1463 Tracev((stderr, "\ndist tree: sent %ld", G1.bits_sent));
Eric Andersencc8ed391999-10-05 16:24:54 +00001464}
1465
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001466
Eric Andersencc8ed391999-10-05 16:24:54 +00001467/* ===========================================================================
1468 * Save the match info and tally the frequency counts. Return true if
1469 * the current block must be flushed.
1470 */
Eric Andersen3073dfb2001-07-02 17:57:32 +00001471static int ct_tally(int dist, int lc)
Eric Andersencc8ed391999-10-05 16:24:54 +00001472{
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001473 G1.l_buf[G2.last_lit++] = lc;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001474 if (dist == 0) {
1475 /* lc is the unmatched char */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001476 G2.dyn_ltree[lc].Freq++;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001477 } else {
1478 /* Here, lc is the match length - MIN_MATCH */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001479 dist--; /* dist = match distance - 1 */
Denis Vlasenko1a03c212007-01-07 19:39:34 +00001480 Assert((ush) dist < (ush) MAX_DIST
1481 && (ush) lc <= (ush) (MAX_MATCH - MIN_MATCH)
Denis Vlasenko89af56b2007-01-07 19:40:34 +00001482 && (ush) D_CODE(dist) < (ush) D_CODES, "ct_tally: bad match"
Denis Vlasenko1a03c212007-01-07 19:39:34 +00001483 );
Eric Andersencc8ed391999-10-05 16:24:54 +00001484
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001485 G2.dyn_ltree[G2.length_code[lc] + LITERALS + 1].Freq++;
1486 G2.dyn_dtree[D_CODE(dist)].Freq++;
Eric Andersencc8ed391999-10-05 16:24:54 +00001487
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001488 G1.d_buf[G2.last_dist++] = dist;
1489 G2.flags |= G2.flag_bit;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001490 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001491 G2.flag_bit <<= 1;
Eric Andersencc8ed391999-10-05 16:24:54 +00001492
Erik Andersene49d5ec2000-02-08 19:58:47 +00001493 /* Output the flags if they fill a byte: */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001494 if ((G2.last_lit & 7) == 0) {
1495 G2.flag_buf[G2.last_flags++] = G2.flags;
1496 G2.flags = 0;
1497 G2.flag_bit = 1;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001498 }
1499 /* Try to guess if it is profitable to stop the current block here */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001500 if ((G2.last_lit & 0xfff) == 0) {
Erik Andersene49d5ec2000-02-08 19:58:47 +00001501 /* Compute an upper bound for the compressed length */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001502 ulg out_length = G2.last_lit * 8L;
1503 ulg in_length = (ulg) G1.strstart - G1.block_start;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001504 int dcode;
1505
1506 for (dcode = 0; dcode < D_CODES; dcode++) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001507 out_length += G2.dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001508 }
1509 out_length >>= 3;
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001510 Trace((stderr,
Erik Andersene49d5ec2000-02-08 19:58:47 +00001511 "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001512 G2.last_lit, G2.last_dist, in_length, out_length,
Erik Andersene49d5ec2000-02-08 19:58:47 +00001513 100L - out_length * 100L / in_length));
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001514 if (G2.last_dist < G2.last_lit / 2 && out_length < in_length / 2)
Erik Andersene49d5ec2000-02-08 19:58:47 +00001515 return 1;
1516 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001517 return (G2.last_lit == LIT_BUFSIZE - 1 || G2.last_dist == DIST_BUFSIZE);
Erik Andersene49d5ec2000-02-08 19:58:47 +00001518 /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
1519 * on 16 bit machines and because stored blocks are restricted to
1520 * 64K-1 bytes.
1521 */
Eric Andersencc8ed391999-10-05 16:24:54 +00001522}
1523
1524/* ===========================================================================
1525 * Send the block data compressed using the given Huffman trees
1526 */
Glenn L McGrathd827e8b2002-08-22 13:21:26 +00001527static void compress_block(ct_data * ltree, ct_data * dtree)
Eric Andersencc8ed391999-10-05 16:24:54 +00001528{
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001529 unsigned dist; /* distance of matched string */
1530 int lc; /* match length or unmatched char (if dist == 0) */
1531 unsigned lx = 0; /* running index in l_buf */
1532 unsigned dx = 0; /* running index in d_buf */
1533 unsigned fx = 0; /* running index in flag_buf */
1534 uch flag = 0; /* current flags */
1535 unsigned code; /* the code to send */
1536 int extra; /* number of extra bits to send */
Eric Andersencc8ed391999-10-05 16:24:54 +00001537
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001538 if (G2.last_lit != 0) do {
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001539 if ((lx & 7) == 0)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001540 flag = G2.flag_buf[fx++];
1541 lc = G1.l_buf[lx++];
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001542 if ((flag & 1) == 0) {
1543 SEND_CODE(lc, ltree); /* send a literal byte */
Denys Vlasenkof2cbb032009-10-23 03:16:08 +02001544 Tracecv(lc > ' ', (stderr, " '%c' ", lc));
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001545 } else {
1546 /* Here, lc is the match length - MIN_MATCH */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001547 code = G2.length_code[lc];
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001548 SEND_CODE(code + LITERALS + 1, ltree); /* send the length code */
1549 extra = extra_lbits[code];
1550 if (extra != 0) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001551 lc -= G2.base_length[code];
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001552 send_bits(lc, extra); /* send the extra length bits */
1553 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001554 dist = G1.d_buf[dx++];
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001555 /* Here, dist is the match distance - 1 */
1556 code = D_CODE(dist);
1557 Assert(code < D_CODES, "bad d_code");
Eric Andersencc8ed391999-10-05 16:24:54 +00001558
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001559 SEND_CODE(code, dtree); /* send the distance code */
1560 extra = extra_dbits[code];
1561 if (extra != 0) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001562 dist -= G2.base_dist[code];
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001563 send_bits(dist, extra); /* send the extra distance bits */
1564 }
1565 } /* literal or match pair ? */
1566 flag >>= 1;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001567 } while (lx < G2.last_lit);
Eric Andersencc8ed391999-10-05 16:24:54 +00001568
Denis Vlasenko89af56b2007-01-07 19:40:34 +00001569 SEND_CODE(END_BLOCK, ltree);
Eric Andersencc8ed391999-10-05 16:24:54 +00001570}
1571
Erik Andersene49d5ec2000-02-08 19:58:47 +00001572
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001573/* ===========================================================================
1574 * Determine the best encoding for the current block: dynamic trees, static
1575 * trees or store, and output the encoded block to the zip file. This function
1576 * returns the total compressed length for the file so far.
1577 */
1578static ulg flush_block(char *buf, ulg stored_len, int eof)
1579{
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001580 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
1581 int max_blindex; /* index of last bit length code of non zero freq */
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001582
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001583 G2.flag_buf[G2.last_flags] = G2.flags; /* Save the flags for the last 8 items */
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001584
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001585 /* Construct the literal and distance trees */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001586 build_tree(&G2.l_desc);
1587 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001588
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001589 build_tree(&G2.d_desc);
1590 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", G2.opt_len, G2.static_len));
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001591 /* At this point, opt_len and static_len are the total bit lengths of
1592 * the compressed block data, excluding the tree representations.
1593 */
1594
1595 /* Build the bit length tree for the above two trees, and get the index
1596 * in bl_order of the last bit length code to send.
1597 */
1598 max_blindex = build_bl_tree();
1599
1600 /* Determine the best encoding. Compute first the block length in bytes */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001601 opt_lenb = (G2.opt_len + 3 + 7) >> 3;
1602 static_lenb = (G2.static_len + 3 + 7) >> 3;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001603
1604 Trace((stderr,
1605 "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ",
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001606 opt_lenb, G2.opt_len, static_lenb, G2.static_len, stored_len,
1607 G2.last_lit, G2.last_dist));
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001608
1609 if (static_lenb <= opt_lenb)
1610 opt_lenb = static_lenb;
1611
1612 /* If compression failed and this is the first and last block,
1613 * and if the zip file can be seeked (to rewrite the local header),
1614 * the whole file is transformed into a stored file:
1615 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001616 if (stored_len <= opt_lenb && eof && G2.compressed_len == 0L && seekable()) {
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001617 /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
1618 if (buf == NULL)
1619 bb_error_msg("block vanished");
1620
1621 copy_block(buf, (unsigned) stored_len, 0); /* without header */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001622 G2.compressed_len = stored_len << 3;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001623
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001624 } else if (stored_len + 4 <= opt_lenb && buf != NULL) {
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001625 /* 4: two words for the lengths */
1626 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
1627 * Otherwise we can't have processed more than WSIZE input bytes since
1628 * the last block flush, because compression would have been
1629 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
1630 * transform a block into a stored block.
1631 */
1632 send_bits((STORED_BLOCK << 1) + eof, 3); /* send block type */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001633 G2.compressed_len = (G2.compressed_len + 3 + 7) & ~7L;
1634 G2.compressed_len += (stored_len + 4) << 3;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001635
1636 copy_block(buf, (unsigned) stored_len, 1); /* with header */
1637
1638 } else if (static_lenb == opt_lenb) {
1639 send_bits((STATIC_TREES << 1) + eof, 3);
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001640 compress_block((ct_data *) G2.static_ltree, (ct_data *) G2.static_dtree);
1641 G2.compressed_len += 3 + G2.static_len;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001642 } else {
1643 send_bits((DYN_TREES << 1) + eof, 3);
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001644 send_all_trees(G2.l_desc.max_code + 1, G2.d_desc.max_code + 1,
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001645 max_blindex + 1);
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001646 compress_block((ct_data *) G2.dyn_ltree, (ct_data *) G2.dyn_dtree);
1647 G2.compressed_len += 3 + G2.opt_len;
Erik Andersene49d5ec2000-02-08 19:58:47 +00001648 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001649 Assert(G2.compressed_len == G1.bits_sent, "bad compressed size");
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001650 init_block();
1651
1652 if (eof) {
1653 bi_windup();
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001654 G2.compressed_len += 7; /* align on byte boundary */
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001655 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001656 Tracev((stderr, "\ncomprlen %lu(%lu) ", G2.compressed_len >> 3,
1657 G2.compressed_len - 7 * eof));
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001658
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001659 return G2.compressed_len >> 3;
Eric Andersencc8ed391999-10-05 16:24:54 +00001660}
Erik Andersene49d5ec2000-02-08 19:58:47 +00001661
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001662
1663/* ===========================================================================
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001664 * Update a hash value with the given input byte
1665 * IN assertion: all calls to to UPDATE_HASH are made with consecutive
1666 * input characters, so that a running hash key can be computed from the
1667 * previous key instead of complete recalculation each time.
1668 */
1669#define UPDATE_HASH(h, c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
1670
1671
1672/* ===========================================================================
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001673 * Same as above, but achieves better compression. We use a lazy
1674 * evaluation for matches: a match is finally adopted only if there is
1675 * no better match at the next window position.
1676 *
1677 * Processes a new input file and return its compressed length. Sets
1678 * the compressed length, crc, deflate flags and internal file
1679 * attributes.
1680 */
1681
1682/* Flush the current block, with given end-of-file flag.
1683 * IN assertion: strstart is set to the end of the current match. */
1684#define FLUSH_BLOCK(eof) \
1685 flush_block( \
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001686 G1.block_start >= 0L \
1687 ? (char*)&G1.window[(unsigned)G1.block_start] \
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001688 : (char*)NULL, \
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001689 (ulg)G1.strstart - G1.block_start, \
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001690 (eof) \
1691 )
1692
1693/* Insert string s in the dictionary and set match_head to the previous head
1694 * of the hash chain (the most recent string with same hash key). Return
1695 * the previous length of the hash chain.
1696 * IN assertion: all calls to to INSERT_STRING are made with consecutive
1697 * input characters and the first MIN_MATCH bytes of s are valid
1698 * (except for the last MIN_MATCH-1 bytes of the input file). */
1699#define INSERT_STRING(s, match_head) \
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001700do { \
1701 UPDATE_HASH(G1.ins_h, G1.window[(s) + MIN_MATCH-1]); \
1702 G1.prev[(s) & WMASK] = match_head = head[G1.ins_h]; \
1703 head[G1.ins_h] = (s); \
1704} while (0)
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001705
1706static ulg deflate(void)
1707{
1708 IPos hash_head; /* head of hash chain */
1709 IPos prev_match; /* previous match */
1710 int flush; /* set if current block must be flushed */
1711 int match_available = 0; /* set if previous match exists */
1712 unsigned match_length = MIN_MATCH - 1; /* length of best match */
1713
1714 /* Process the input block. */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001715 while (G1.lookahead != 0) {
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001716 /* Insert the string window[strstart .. strstart+2] in the
1717 * dictionary, and set hash_head to the head of the hash chain:
1718 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001719 INSERT_STRING(G1.strstart, hash_head);
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001720
1721 /* Find the longest match, discarding those <= prev_length.
1722 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001723 G1.prev_length = match_length;
1724 prev_match = G1.match_start;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001725 match_length = MIN_MATCH - 1;
1726
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001727 if (hash_head != 0 && G1.prev_length < max_lazy_match
1728 && G1.strstart - hash_head <= MAX_DIST
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001729 ) {
1730 /* To simplify the code, we prevent matches with the string
1731 * of window index 0 (in particular we have to avoid a match
1732 * of the string with itself at the start of the input file).
1733 */
1734 match_length = longest_match(hash_head);
1735 /* longest_match() sets match_start */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001736 if (match_length > G1.lookahead)
1737 match_length = G1.lookahead;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001738
1739 /* Ignore a length 3 match if it is too distant: */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001740 if (match_length == MIN_MATCH && G1.strstart - G1.match_start > TOO_FAR) {
1741 /* If prev_match is also MIN_MATCH, G1.match_start is garbage
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001742 * but we will ignore the current match anyway.
1743 */
1744 match_length--;
1745 }
1746 }
1747 /* If there was a match at the previous step and the current
1748 * match is not better, output the previous match:
1749 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001750 if (G1.prev_length >= MIN_MATCH && match_length <= G1.prev_length) {
1751 check_match(G1.strstart - 1, prev_match, G1.prev_length);
1752 flush = ct_tally(G1.strstart - 1 - prev_match, G1.prev_length - MIN_MATCH);
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001753
1754 /* Insert in hash table all strings up to the end of the match.
1755 * strstart-1 and strstart are already inserted.
1756 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001757 G1.lookahead -= G1.prev_length - 1;
1758 G1.prev_length -= 2;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001759 do {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001760 G1.strstart++;
1761 INSERT_STRING(G1.strstart, hash_head);
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001762 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1763 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
1764 * these bytes are garbage, but it does not matter since the
1765 * next lookahead bytes will always be emitted as literals.
1766 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001767 } while (--G1.prev_length != 0);
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001768 match_available = 0;
1769 match_length = MIN_MATCH - 1;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001770 G1.strstart++;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001771 if (flush) {
1772 FLUSH_BLOCK(0);
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001773 G1.block_start = G1.strstart;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001774 }
1775 } else if (match_available) {
1776 /* If there was no match at the previous position, output a
1777 * single literal. If there was a match but the current match
1778 * is longer, truncate the previous match to a single literal.
1779 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001780 Tracevv((stderr, "%c", G1.window[G1.strstart - 1]));
1781 if (ct_tally(0, G1.window[G1.strstart - 1])) {
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001782 FLUSH_BLOCK(0);
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001783 G1.block_start = G1.strstart;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001784 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001785 G1.strstart++;
1786 G1.lookahead--;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001787 } else {
1788 /* There is no previous match to compare with, wait for
1789 * the next step to decide.
1790 */
1791 match_available = 1;
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001792 G1.strstart++;
1793 G1.lookahead--;
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001794 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001795 Assert(G1.strstart <= G1.isize && lookahead <= G1.isize, "a bit too far");
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001796
1797 /* Make sure that we always have enough lookahead, except
1798 * at the end of the input file. We need MAX_MATCH bytes
1799 * for the next match, plus MIN_MATCH bytes to insert the
1800 * string following the next match.
1801 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001802 while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile)
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001803 fill_window();
1804 }
1805 if (match_available)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001806 ct_tally(0, G1.window[G1.strstart - 1]);
Denis Vlasenko56c83ea2007-01-07 19:40:50 +00001807
1808 return FLUSH_BLOCK(1); /* eof */
1809}
1810
1811
Eric Andersencc8ed391999-10-05 16:24:54 +00001812/* ===========================================================================
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001813 * Initialize the bit string routines.
1814 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001815static void bi_init(void)
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001816{
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001817 G1.bi_buf = 0;
1818 G1.bi_valid = 0;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001819#ifdef DEBUG
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001820 G1.bits_sent = 0L;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001821#endif
1822}
1823
1824
1825/* ===========================================================================
1826 * Initialize the "longest match" routines for a new file
1827 */
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001828static void lm_init(ush * flagsp)
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001829{
1830 unsigned j;
1831
1832 /* Initialize the hash table. */
1833 memset(head, 0, HASH_SIZE * sizeof(*head));
1834 /* prev will be initialized on the fly */
1835
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001836 /* speed options for the general purpose bit flag */
1837 *flagsp |= 2; /* FAST 4, SLOW 2 */
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001838 /* ??? reduce max_chain_length for binary files */
1839
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001840 G1.strstart = 0;
1841 G1.block_start = 0L;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001842
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001843 G1.lookahead = file_read(G1.window,
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001844 sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE);
1845
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001846 if (G1.lookahead == 0 || G1.lookahead == (unsigned) -1) {
1847 G1.eofile = 1;
1848 G1.lookahead = 0;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001849 return;
1850 }
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001851 G1.eofile = 0;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001852 /* Make sure that we always have enough lookahead. This is important
1853 * if input comes from a device such as a tty.
1854 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001855 while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile)
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001856 fill_window();
1857
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001858 G1.ins_h = 0;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001859 for (j = 0; j < MIN_MATCH - 1; j++)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001860 UPDATE_HASH(G1.ins_h, G1.window[j]);
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001861 /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
1862 * not important since only literal bytes will be emitted.
1863 */
1864}
1865
1866
1867/* ===========================================================================
1868 * Allocate the match buffer, initialize the various tables and save the
1869 * location of the internal file attribute (ascii/binary) and method
1870 * (DEFLATE/STORE).
1871 * One callsite in zip()
1872 */
Denis Vlasenkofe42d172007-03-14 00:08:28 +00001873static void ct_init(void)
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001874{
1875 int n; /* iterates over tree elements */
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001876 int length; /* length value */
1877 int code; /* code value */
1878 int dist; /* distance index */
1879
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001880 G2.compressed_len = 0L;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001881
1882#ifdef NOT_NEEDED
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001883 if (G2.static_dtree[0].Len != 0)
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001884 return; /* ct_init already called */
1885#endif
1886
1887 /* Initialize the mapping length (0..255) -> length code (0..28) */
1888 length = 0;
1889 for (code = 0; code < LENGTH_CODES - 1; code++) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001890 G2.base_length[code] = length;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001891 for (n = 0; n < (1 << extra_lbits[code]); n++) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001892 G2.length_code[length++] = code;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001893 }
1894 }
1895 Assert(length == 256, "ct_init: length != 256");
1896 /* Note that the length 255 (match length 258) can be represented
1897 * in two different ways: code 284 + 5 bits or code 285, so we
1898 * overwrite length_code[255] to use the best encoding:
1899 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001900 G2.length_code[length - 1] = code;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001901
1902 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
1903 dist = 0;
1904 for (code = 0; code < 16; code++) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001905 G2.base_dist[code] = dist;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001906 for (n = 0; n < (1 << extra_dbits[code]); n++) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001907 G2.dist_code[dist++] = code;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001908 }
1909 }
1910 Assert(dist == 256, "ct_init: dist != 256");
1911 dist >>= 7; /* from now on, all distances are divided by 128 */
1912 for (; code < D_CODES; code++) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001913 G2.base_dist[code] = dist << 7;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001914 for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001915 G2.dist_code[256 + dist++] = code;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001916 }
1917 }
1918 Assert(dist == 256, "ct_init: 256+dist != 512");
1919
1920 /* Construct the codes of the static literal tree */
1921 /* already zeroed - it's in bss
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001922 for (n = 0; n <= MAX_BITS; n++)
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001923 G2.bl_count[n] = 0; */
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001924
1925 n = 0;
1926 while (n <= 143) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001927 G2.static_ltree[n++].Len = 8;
1928 G2.bl_count[8]++;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001929 }
1930 while (n <= 255) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001931 G2.static_ltree[n++].Len = 9;
1932 G2.bl_count[9]++;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001933 }
1934 while (n <= 279) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001935 G2.static_ltree[n++].Len = 7;
1936 G2.bl_count[7]++;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001937 }
1938 while (n <= 287) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001939 G2.static_ltree[n++].Len = 8;
1940 G2.bl_count[8]++;
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001941 }
1942 /* Codes 286 and 287 do not exist, but we must include them in the
1943 * tree construction to get a canonical Huffman tree (longest code
1944 * all ones)
1945 */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001946 gen_codes((ct_data *) G2.static_ltree, L_CODES + 1);
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001947
1948 /* The static distance tree is trivial: */
1949 for (n = 0; n < D_CODES; n++) {
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001950 G2.static_dtree[n].Len = 5;
1951 G2.static_dtree[n].Code = bi_reverse(n, 5);
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001952 }
1953
1954 /* Initialize the first block of the first file: */
1955 init_block();
1956}
1957
1958
1959/* ===========================================================================
Eric Andersencc8ed391999-10-05 16:24:54 +00001960 * Deflate in to out.
1961 * IN assertions: the input and output buffers are cleared.
Eric Andersencc8ed391999-10-05 16:24:54 +00001962 */
Denis Vlasenko3ae6f342007-01-07 19:44:57 +00001963
Denis Vlasenkofe42d172007-03-14 00:08:28 +00001964static void zip(ulg time_stamp)
Eric Andersencc8ed391999-10-05 16:24:54 +00001965{
Denis Vlasenkodb6a5c32007-01-07 19:45:51 +00001966 ush deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */
Eric Andersencc8ed391999-10-05 16:24:54 +00001967
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001968 G1.outcnt = 0;
Eric Andersencc8ed391999-10-05 16:24:54 +00001969
Erik Andersene49d5ec2000-02-08 19:58:47 +00001970 /* Write the header to the gzip file. See algorithm.doc for the format */
Denis Vlasenkoda799e82007-03-14 00:06:29 +00001971 /* magic header for gzip files: 1F 8B */
Denis Vlasenkofe42d172007-03-14 00:08:28 +00001972 /* compression method: 8 (DEFLATED) */
Denis Vlasenkoda799e82007-03-14 00:06:29 +00001973 /* general flags: 0 */
1974 put_32bit(0x00088b1f);
Denis Vlasenkofe42d172007-03-14 00:08:28 +00001975 put_32bit(time_stamp);
Eric Andersencc8ed391999-10-05 16:24:54 +00001976
Erik Andersene49d5ec2000-02-08 19:58:47 +00001977 /* Write deflated file to zip file */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001978 G1.crc = ~0;
Eric Andersencc8ed391999-10-05 16:24:54 +00001979
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001980 bi_init();
Denis Vlasenkofe42d172007-03-14 00:08:28 +00001981 ct_init();
Erik Andersene49d5ec2000-02-08 19:58:47 +00001982 lm_init(&deflate_flags);
Eric Andersencc8ed391999-10-05 16:24:54 +00001983
Denis Vlasenkoda31fbc2007-01-07 19:39:02 +00001984 put_8bit(deflate_flags); /* extra flags */
Denis Vlasenkoad403412007-01-07 19:37:42 +00001985 put_8bit(3); /* OS identifier = 3 (Unix) */
Eric Andersencc8ed391999-10-05 16:24:54 +00001986
Denis Vlasenkoed0f6db2007-01-07 19:38:26 +00001987 deflate();
Eric Andersencc8ed391999-10-05 16:24:54 +00001988
Erik Andersene49d5ec2000-02-08 19:58:47 +00001989 /* Write the crc and uncompressed size */
Denis Vlasenkoe930fe12007-03-14 00:06:10 +00001990 put_32bit(~G1.crc);
1991 put_32bit(G1.isize);
Eric Andersencc8ed391999-10-05 16:24:54 +00001992
Erik Andersene49d5ec2000-02-08 19:58:47 +00001993 flush_outbuf();
Eric Andersencc8ed391999-10-05 16:24:54 +00001994}
Denis Vlasenko52933d42007-01-07 19:40:13 +00001995
1996
1997/* ======================================================================== */
Denis Vlasenko75605782007-03-14 00:07:51 +00001998static
1999char* make_new_name_gzip(char *filename)
2000{
2001 return xasprintf("%s.gz", filename);
2002}
2003
2004static
Denis Vlasenko5e34ff22009-04-21 11:09:40 +00002005IF_DESKTOP(long long) int pack_gzip(unpack_info_t *info UNUSED_PARAM)
Denis Vlasenko75605782007-03-14 00:07:51 +00002006{
2007 struct stat s;
Denis Vlasenkoc86e0522007-03-20 11:30:28 +00002008
Denys Vlasenko167cd702009-05-18 13:08:57 +02002009 /* Clear input and output buffers */
2010 G1.outcnt = 0;
2011#ifdef DEBUG
2012 G1.insize = 0;
2013#endif
2014 G1.isize = 0;
2015
2016 /* Reinit G2.xxx */
2017 memset(&G2, 0, sizeof(G2));
2018 G2.l_desc.dyn_tree = G2.dyn_ltree;
2019 G2.l_desc.static_tree = G2.static_ltree;
2020 G2.l_desc.extra_bits = extra_lbits;
2021 G2.l_desc.extra_base = LITERALS + 1;
2022 G2.l_desc.elems = L_CODES;
2023 G2.l_desc.max_length = MAX_BITS;
2024 //G2.l_desc.max_code = 0;
2025 G2.d_desc.dyn_tree = G2.dyn_dtree;
2026 G2.d_desc.static_tree = G2.static_dtree;
2027 G2.d_desc.extra_bits = extra_dbits;
2028 //G2.d_desc.extra_base = 0;
2029 G2.d_desc.elems = D_CODES;
2030 G2.d_desc.max_length = MAX_BITS;
2031 //G2.d_desc.max_code = 0;
2032 G2.bl_desc.dyn_tree = G2.bl_tree;
2033 //G2.bl_desc.static_tree = NULL;
2034 G2.bl_desc.extra_bits = extra_blbits,
2035 //G2.bl_desc.extra_base = 0;
2036 G2.bl_desc.elems = BL_CODES;
2037 G2.bl_desc.max_length = MAX_BL_BITS;
2038 //G2.bl_desc.max_code = 0;
2039
Denis Vlasenkofe42d172007-03-14 00:08:28 +00002040 s.st_ctime = 0;
2041 fstat(STDIN_FILENO, &s);
2042 zip(s.st_ctime);
Denis Vlasenko75605782007-03-14 00:07:51 +00002043 return 0;
2044}
2045
Denis Vlasenko52978092008-03-30 13:11:47 +00002046/*
2047 * Linux kernel build uses gzip -d -n. We accept and ignore it.
2048 * Man page says:
2049 * -n --no-name
2050 * gzip: do not save the original file name and time stamp.
2051 * (The original name is always saved if the name had to be truncated.)
2052 * gunzip: do not restore the original file name/time even if present
2053 * (remove only the gzip suffix from the compressed file name).
2054 * This option is the default when decompressing.
2055 * -N --name
2056 * gzip: always save the original file name and time stamp (this is the default)
2057 * gunzip: restore the original file name and time stamp if present.
2058 */
2059
Denis Vlasenko9b49a5e2007-10-11 10:05:36 +00002060int gzip_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
Denis Vlasenko85c24712008-03-17 09:04:04 +00002061#if ENABLE_GUNZIP
Denis Vlasenko75605782007-03-14 00:07:51 +00002062int gzip_main(int argc, char **argv)
Denis Vlasenko85c24712008-03-17 09:04:04 +00002063#else
Denis Vlasenkoa60f84e2008-07-05 09:18:54 +00002064int gzip_main(int argc UNUSED_PARAM, char **argv)
Denis Vlasenko85c24712008-03-17 09:04:04 +00002065#endif
Denis Vlasenko75605782007-03-14 00:07:51 +00002066{
2067 unsigned opt;
2068
2069 /* Must match bbunzip's constants OPT_STDOUT, OPT_FORCE! */
Denis Vlasenko5e34ff22009-04-21 11:09:40 +00002070 opt = getopt32(argv, "cfv" IF_GUNZIP("dt") "q123456789n");
Denis Vlasenko77f1ec12007-10-13 03:36:03 +00002071#if ENABLE_GUNZIP /* gunzip_main may not be visible... */
Denis Vlasenko55da0be2008-06-27 21:52:41 +00002072 if (opt & 0x18) // -d and/or -t
Denis Vlasenko77f1ec12007-10-13 03:36:03 +00002073 return gunzip_main(argc, argv);
2074#endif
2075 option_mask32 &= 0x7; /* ignore -q, -0..9 */
Denis Vlasenko75605782007-03-14 00:07:51 +00002076 //if (opt & 0x1) // -c
2077 //if (opt & 0x2) // -f
2078 //if (opt & 0x4) // -v
Denis Vlasenkocbcff292007-03-22 18:56:23 +00002079 argv += optind;
Denis Vlasenko75605782007-03-14 00:07:51 +00002080
Denys Vlasenko90a99042009-09-06 02:36:23 +02002081 SET_PTR_TO_GLOBALS((char *)xzalloc(sizeof(struct globals)+sizeof(struct globals2))
Denis Vlasenko574f2f42008-02-27 18:41:59 +00002082 + sizeof(struct globals));
Denis Vlasenko55da0be2008-06-27 21:52:41 +00002083 barrier();
Denis Vlasenko75605782007-03-14 00:07:51 +00002084
2085 /* Allocate all global buffers (for DYN_ALLOC option) */
2086 ALLOC(uch, G1.l_buf, INBUFSIZ);
2087 ALLOC(uch, G1.outbuf, OUTBUFSIZ);
2088 ALLOC(ush, G1.d_buf, DIST_BUFSIZE);
2089 ALLOC(uch, G1.window, 2L * WSIZE);
2090 ALLOC(ush, G1.prev, 1L << BITS);
2091
2092 /* Initialise the CRC32 table */
Denis Vlasenkoc6758a02007-04-10 21:40:19 +00002093 G1.crc_32_tab = crc32_filltable(NULL, 0);
Denis Vlasenko75605782007-03-14 00:07:51 +00002094
Denis Vlasenko75605782007-03-14 00:07:51 +00002095 return bbunpack(argv, make_new_name_gzip, pack_gzip);
2096}