39 |
aa: 85.1% -- replaced with aa.gz |
aa: 85.1% -- replaced with aa.gz |
40 |
*/ |
*/ |
41 |
|
|
42 |
#include "busybox.h" |
#include "libbb.h" |
43 |
|
#include "unarchive.h" |
44 |
|
|
45 |
|
|
46 |
/* =========================================================================== |
/* =========================================================================== |
48 |
//#define DEBUG 1 |
//#define DEBUG 1 |
49 |
/* Diagnostic functions */ |
/* Diagnostic functions */ |
50 |
#ifdef DEBUG |
#ifdef DEBUG |
51 |
# define Assert(cond,msg) {if(!(cond)) bb_error_msg(msg);} |
# define Assert(cond,msg) { if (!(cond)) bb_error_msg(msg); } |
52 |
# define Trace(x) fprintf x |
# define Trace(x) fprintf x |
53 |
# define Tracev(x) {if (verbose) fprintf x ;} |
# define Tracev(x) {if (verbose) fprintf x; } |
54 |
# define Tracevv(x) {if (verbose > 1) fprintf x ;} |
# define Tracevv(x) {if (verbose > 1) fprintf x; } |
55 |
# define Tracec(c,x) {if (verbose && (c)) fprintf x ;} |
# define Tracec(c,x) {if (verbose && (c)) fprintf x; } |
56 |
# define Tracecv(c,x) {if (verbose > 1 && (c)) fprintf x ;} |
# define Tracecv(c,x) {if (verbose > 1 && (c)) fprintf x; } |
57 |
#else |
#else |
58 |
# define Assert(cond,msg) |
# define Assert(cond,msg) |
59 |
# define Trace(x) |
# define Trace(x) |
68 |
*/ |
*/ |
69 |
#define SMALL_MEM |
#define SMALL_MEM |
70 |
|
|
|
/* Compression methods (see algorithm.doc) */ |
|
|
/* Only STORED and DEFLATED are supported by this BusyBox module */ |
|
|
#define STORED 0 |
|
|
/* methods 4 to 7 reserved */ |
|
|
#define DEFLATED 8 |
|
|
|
|
71 |
#ifndef INBUFSIZ |
#ifndef INBUFSIZ |
72 |
# ifdef SMALL_MEM |
# ifdef SMALL_MEM |
73 |
# define INBUFSIZ 0x2000 /* input buffer size */ |
# define INBUFSIZ 0x2000 /* input buffer size */ |
190 |
typedef uint32_t ulg; |
typedef uint32_t ulg; |
191 |
typedef int32_t lng; |
typedef int32_t lng; |
192 |
|
|
|
|
|
|
/* =========================================================================== |
|
|
*/ |
|
193 |
typedef ush Pos; |
typedef ush Pos; |
194 |
typedef unsigned IPos; |
typedef unsigned IPos; |
|
|
|
195 |
/* A Pos is an index in the character window. We use short instead of int to |
/* 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. |
* save space in the various tables. IPos is used only for parameter passing. |
197 |
*/ |
*/ |
198 |
|
|
|
static lng block_start; |
|
|
|
|
|
/* window position at the beginning of the current output block. Gets |
|
|
* negative when the window is moved backwards. |
|
|
*/ |
|
|
|
|
|
static unsigned ins_h; /* hash index of string to be inserted */ |
|
|
|
|
|
#define H_SHIFT ((HASH_BITS+MIN_MATCH-1) / MIN_MATCH) |
|
|
/* Number of bits by which ins_h and del_h must be shifted at each |
|
|
* input step. It must be such that after MIN_MATCH steps, the oldest |
|
|
* byte no longer takes part in the hash key, that is: |
|
|
* H_SHIFT * MIN_MATCH >= HASH_BITS |
|
|
*/ |
|
|
|
|
|
static unsigned int prev_length; |
|
|
|
|
|
/* Length of the best match at previous step. Matches not greater than this |
|
|
* are discarded. This is used in the lazy match evaluation. |
|
|
*/ |
|
|
|
|
|
static unsigned strstart; /* start of string to insert */ |
|
|
static unsigned match_start; /* start of matching string */ |
|
|
static int eofile; /* flag set at end of input file */ |
|
|
static unsigned lookahead; /* number of valid bytes ahead in window */ |
|
|
|
|
199 |
enum { |
enum { |
200 |
WINDOW_SIZE = 2 * WSIZE, |
WINDOW_SIZE = 2 * WSIZE, |
201 |
/* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the |
/* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the |
236 |
}; |
}; |
237 |
|
|
238 |
|
|
239 |
|
struct globals { |
240 |
|
|
241 |
|
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 */ |
264 |
|
|
265 |
/* =========================================================================== |
/* =========================================================================== |
266 |
*/ |
*/ |
267 |
#define DECLARE(type, array, size) \ |
#define DECLARE(type, array, size) \ |
268 |
static type * array |
type * array |
|
|
|
269 |
#define ALLOC(type, array, size) \ |
#define ALLOC(type, array, size) \ |
270 |
{ \ |
array = xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type)); |
|
array = xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type)); \ |
|
|
} |
|
|
|
|
271 |
#define FREE(array) \ |
#define FREE(array) \ |
272 |
{ \ |
do { free(array); array = NULL; } while (0) |
|
free(array); \ |
|
|
array = NULL; \ |
|
|
} |
|
273 |
|
|
274 |
/* global buffers */ |
/* global buffers */ |
275 |
|
|
276 |
/* buffer for literals or lengths */ |
/* buffer for literals or lengths */ |
277 |
/* DECLARE(uch, l_buf, LIT_BUFSIZE); */ |
/* DECLARE(uch, l_buf, LIT_BUFSIZE); */ |
278 |
DECLARE(uch, l_buf, INBUFSIZ); |
DECLARE(uch, l_buf, INBUFSIZ); |
279 |
|
|
280 |
DECLARE(ush, d_buf, DIST_BUFSIZE); |
DECLARE(ush, d_buf, DIST_BUFSIZE); |
281 |
DECLARE(uch, outbuf, OUTBUFSIZ); |
DECLARE(uch, outbuf, OUTBUFSIZ); |
282 |
|
|
283 |
/* Sliding window. Input bytes are read into the second half of the window, |
/* 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 |
* and move to the first half later to keep a dictionary of at least WSIZE |
289 |
* To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would |
* To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would |
290 |
* be less efficient). |
* be less efficient). |
291 |
*/ |
*/ |
292 |
DECLARE(uch, window, 2L * WSIZE); |
DECLARE(uch, window, 2L * WSIZE); |
293 |
|
|
294 |
/* Link to older string with same hash index. To limit the size of this |
/* 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. |
* 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. |
* An index in this array is thus a window index modulo 32K. |
297 |
*/ |
*/ |
298 |
/* DECLARE(Pos, prev, WSIZE); */ |
/* DECLARE(Pos, prev, WSIZE); */ |
299 |
DECLARE(ush, prev, 1L << BITS); |
DECLARE(ush, prev, 1L << BITS); |
300 |
|
|
301 |
/* Heads of the hash chains or 0. */ |
/* Heads of the hash chains or 0. */ |
302 |
/* DECLARE(Pos, head, 1<<HASH_BITS); */ |
/* DECLARE(Pos, head, 1<<HASH_BITS); */ |
303 |
#define head (prev+WSIZE) /* hash head (see deflate.c) */ |
#define head (G1.prev + WSIZE) /* hash head (see deflate.c) */ |
|
|
|
304 |
|
|
305 |
/* number of input bytes */ |
/* number of input bytes */ |
306 |
static ulg isize; /* only 32 bits stored in .gz file */ |
ulg isize; /* only 32 bits stored in .gz file */ |
307 |
|
|
308 |
static int foreground; /* set if program run in foreground */ |
/* bbox always use stdin/stdout */ |
309 |
static int method = DEFLATED; /* compression method */ |
#define ifd STDIN_FILENO /* input file descriptor */ |
310 |
static int exit_code; /* program exit code */ |
#define ofd STDOUT_FILENO /* output file descriptor */ |
311 |
|
|
|
/* original time stamp (modification time) */ |
|
|
static ulg time_stamp; /* only 32 bits stored in .gz file */ |
|
|
|
|
|
static int ifd; /* input file descriptor */ |
|
|
static int ofd; /* output file descriptor */ |
|
312 |
#ifdef DEBUG |
#ifdef DEBUG |
313 |
static unsigned insize; /* valid bytes in l_buf */ |
unsigned insize; /* valid bytes in l_buf */ |
314 |
#endif |
#endif |
315 |
static unsigned outcnt; /* bytes in output buffer */ |
unsigned outcnt; /* bytes in output buffer */ |
|
|
|
|
static uint32_t *crc_32_tab; |
|
316 |
|
|
317 |
|
smallint eofile; /* flag set at end of input file */ |
318 |
|
|
319 |
/* =========================================================================== |
/* =========================================================================== |
320 |
* Local data used by the "bit string" routines. |
* Local data used by the "bit string" routines. |
321 |
*/ |
*/ |
322 |
|
|
323 |
//// static int zfile; /* output gzip file */ |
unsigned short bi_buf; |
|
|
|
|
static unsigned short bi_buf; |
|
324 |
|
|
325 |
/* Output buffer. bits are inserted starting at the bottom (least significant |
/* Output buffer. bits are inserted starting at the bottom (least significant |
326 |
* bits). |
* bits). |
327 |
*/ |
*/ |
328 |
|
|
329 |
#undef BUF_SIZE |
#undef BUF_SIZE |
330 |
#define BUF_SIZE (8 * sizeof(bi_buf)) |
#define BUF_SIZE (8 * sizeof(G1.bi_buf)) |
331 |
/* Number of bits used within bi_buf. (bi_buf might be implemented on |
/* Number of bits used within bi_buf. (bi_buf might be implemented on |
332 |
* more than 16 bits on some systems.) |
* more than 16 bits on some systems.) |
333 |
*/ |
*/ |
334 |
|
|
335 |
static int bi_valid; |
int bi_valid; |
336 |
|
|
337 |
/* Current input function. Set to mem_read for in-memory compression */ |
/* Current input function. Set to mem_read for in-memory compression */ |
338 |
|
|
339 |
#ifdef DEBUG |
#ifdef DEBUG |
340 |
static ulg bits_sent; /* bit length of the compressed data */ |
ulg bits_sent; /* bit length of the compressed data */ |
341 |
#endif |
#endif |
342 |
|
|
343 |
|
uint32_t *crc_32_tab; |
344 |
|
uint32_t crc; /* shift register contents */ |
345 |
|
}; |
346 |
|
|
347 |
|
#define G1 (*(ptr_to_globals - 1)) |
348 |
|
|
349 |
|
|
350 |
/* =========================================================================== |
/* =========================================================================== |
351 |
* Write the output buffer outbuf[0..outcnt-1] and update bytes_out. |
* Write the output buffer outbuf[0..outcnt-1] and update bytes_out. |
353 |
*/ |
*/ |
354 |
static void flush_outbuf(void) |
static void flush_outbuf(void) |
355 |
{ |
{ |
356 |
if (outcnt == 0) |
if (G1.outcnt == 0) |
357 |
return; |
return; |
358 |
|
|
359 |
xwrite(ofd, (char *) outbuf, outcnt); |
xwrite(ofd, (char *) G1.outbuf, G1.outcnt); |
360 |
outcnt = 0; |
G1.outcnt = 0; |
361 |
} |
} |
362 |
|
|
363 |
|
|
365 |
*/ |
*/ |
366 |
/* put_8bit is used for the compressed output */ |
/* put_8bit is used for the compressed output */ |
367 |
#define put_8bit(c) \ |
#define put_8bit(c) \ |
368 |
{ \ |
do { \ |
369 |
outbuf[outcnt++] = (c); \ |
G1.outbuf[G1.outcnt++] = (c); \ |
370 |
if (outcnt == OUTBUFSIZ) flush_outbuf(); \ |
if (G1.outcnt == OUTBUFSIZ) flush_outbuf(); \ |
371 |
} |
} while (0) |
372 |
|
|
373 |
/* Output a 16 bit value, lsb first */ |
/* Output a 16 bit value, lsb first */ |
374 |
static void put_16bit(ush w) |
static void put_16bit(ush w) |
375 |
{ |
{ |
376 |
if (outcnt < OUTBUFSIZ - 2) { |
if (G1.outcnt < OUTBUFSIZ - 2) { |
377 |
outbuf[outcnt++] = w; |
G1.outbuf[G1.outcnt++] = w; |
378 |
outbuf[outcnt++] = w >> 8; |
G1.outbuf[G1.outcnt++] = w >> 8; |
379 |
} else { |
} else { |
380 |
put_8bit(w); |
put_8bit(w); |
381 |
put_8bit(w >> 8); |
put_8bit(w >> 8); |
393 |
*/ |
*/ |
394 |
static void clear_bufs(void) |
static void clear_bufs(void) |
395 |
{ |
{ |
396 |
outcnt = 0; |
G1.outcnt = 0; |
397 |
#ifdef DEBUG |
#ifdef DEBUG |
398 |
insize = 0; |
G1.insize = 0; |
399 |
#endif |
#endif |
400 |
isize = 0; |
G1.isize = 0; |
401 |
} |
} |
402 |
|
|
403 |
|
|
406 |
* pointer, then initialize the crc shift register contents instead. |
* pointer, then initialize the crc shift register contents instead. |
407 |
* Return the current crc in either case. |
* Return the current crc in either case. |
408 |
*/ |
*/ |
|
static uint32_t crc; /* shift register contents */ |
|
409 |
static uint32_t updcrc(uch * s, unsigned n) |
static uint32_t updcrc(uch * s, unsigned n) |
410 |
{ |
{ |
411 |
uint32_t c = crc; |
uint32_t c = G1.crc; |
412 |
while (n) { |
while (n) { |
413 |
c = crc_32_tab[(uch)(c ^ *s++)] ^ (c >> 8); |
c = G1.crc_32_tab[(uch)(c ^ *s++)] ^ (c >> 8); |
414 |
n--; |
n--; |
415 |
} |
} |
416 |
crc = c; |
G1.crc = c; |
417 |
return c; |
return c; |
418 |
} |
} |
419 |
|
|
427 |
{ |
{ |
428 |
unsigned len; |
unsigned len; |
429 |
|
|
430 |
Assert(insize == 0, "l_buf not empty"); |
Assert(G1.insize == 0, "l_buf not empty"); |
431 |
|
|
432 |
len = safe_read(ifd, buf, size); |
len = safe_read(ifd, buf, size); |
433 |
if (len == (unsigned)(-1) || len == 0) |
if (len == (unsigned)(-1) || len == 0) |
434 |
return len; |
return len; |
435 |
|
|
436 |
updcrc(buf, len); |
updcrc(buf, len); |
437 |
isize += len; |
G1.isize += len; |
438 |
return len; |
return len; |
439 |
} |
} |
440 |
|
|
448 |
#ifdef DEBUG |
#ifdef DEBUG |
449 |
Tracev((stderr, " l %2d v %4x ", length, value)); |
Tracev((stderr, " l %2d v %4x ", length, value)); |
450 |
Assert(length > 0 && length <= 15, "invalid length"); |
Assert(length > 0 && length <= 15, "invalid length"); |
451 |
bits_sent += length; |
G1.bits_sent += length; |
452 |
#endif |
#endif |
453 |
/* If not enough room in bi_buf, use (valid) bits from bi_buf and |
/* If not enough room in bi_buf, use (valid) bits from bi_buf and |
454 |
* (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) |
* (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) |
455 |
* unused bits in value. |
* unused bits in value. |
456 |
*/ |
*/ |
457 |
if (bi_valid > (int) BUF_SIZE - length) { |
if (G1.bi_valid > (int) BUF_SIZE - length) { |
458 |
bi_buf |= (value << bi_valid); |
G1.bi_buf |= (value << G1.bi_valid); |
459 |
put_16bit(bi_buf); |
put_16bit(G1.bi_buf); |
460 |
bi_buf = (ush) value >> (BUF_SIZE - bi_valid); |
G1.bi_buf = (ush) value >> (BUF_SIZE - G1.bi_valid); |
461 |
bi_valid += length - BUF_SIZE; |
G1.bi_valid += length - BUF_SIZE; |
462 |
} else { |
} else { |
463 |
bi_buf |= value << bi_valid; |
G1.bi_buf |= value << G1.bi_valid; |
464 |
bi_valid += length; |
G1.bi_valid += length; |
465 |
} |
} |
466 |
} |
} |
467 |
|
|
489 |
*/ |
*/ |
490 |
static void bi_windup(void) |
static void bi_windup(void) |
491 |
{ |
{ |
492 |
if (bi_valid > 8) { |
if (G1.bi_valid > 8) { |
493 |
put_16bit(bi_buf); |
put_16bit(G1.bi_buf); |
494 |
} else if (bi_valid > 0) { |
} else if (G1.bi_valid > 0) { |
495 |
put_8bit(bi_buf); |
put_8bit(G1.bi_buf); |
496 |
} |
} |
497 |
bi_buf = 0; |
G1.bi_buf = 0; |
498 |
bi_valid = 0; |
G1.bi_valid = 0; |
499 |
#ifdef DEBUG |
#ifdef DEBUG |
500 |
bits_sent = (bits_sent + 7) & ~7; |
G1.bits_sent = (G1.bits_sent + 7) & ~7; |
501 |
#endif |
#endif |
502 |
} |
} |
503 |
|
|
514 |
put_16bit(len); |
put_16bit(len); |
515 |
put_16bit(~len); |
put_16bit(~len); |
516 |
#ifdef DEBUG |
#ifdef DEBUG |
517 |
bits_sent += 2 * 16; |
G1.bits_sent += 2 * 16; |
518 |
#endif |
#endif |
519 |
} |
} |
520 |
#ifdef DEBUG |
#ifdef DEBUG |
521 |
bits_sent += (ulg) len << 3; |
G1.bits_sent += (ulg) len << 3; |
522 |
#endif |
#endif |
523 |
while (len--) { |
while (len--) { |
524 |
put_8bit(*buf++); |
put_8bit(*buf++); |
537 |
static void fill_window(void) |
static void fill_window(void) |
538 |
{ |
{ |
539 |
unsigned n, m; |
unsigned n, m; |
540 |
unsigned more = WINDOW_SIZE - lookahead - strstart; |
unsigned more = WINDOW_SIZE - G1.lookahead - G1.strstart; |
541 |
/* Amount of free space at the end of the window. */ |
/* Amount of free space at the end of the window. */ |
542 |
|
|
543 |
/* If the window is almost full and there is insufficient lookahead, |
/* If the window is almost full and there is insufficient lookahead, |
548 |
* and lookahead == 1 (input done one byte at time) |
* and lookahead == 1 (input done one byte at time) |
549 |
*/ |
*/ |
550 |
more--; |
more--; |
551 |
} else if (strstart >= WSIZE + MAX_DIST) { |
} else if (G1.strstart >= WSIZE + MAX_DIST) { |
552 |
/* By the IN assertion, the window is not empty so we can't confuse |
/* By the IN assertion, the window is not empty so we can't confuse |
553 |
* more == 0 with more == 64K on a 16 bit machine. |
* more == 0 with more == 64K on a 16 bit machine. |
554 |
*/ |
*/ |
555 |
Assert(WINDOW_SIZE == 2 * WSIZE, "no sliding with BIG_MEM"); |
Assert(WINDOW_SIZE == 2 * WSIZE, "no sliding with BIG_MEM"); |
556 |
|
|
557 |
memcpy(window, window + WSIZE, WSIZE); |
memcpy(G1.window, G1.window + WSIZE, WSIZE); |
558 |
match_start -= WSIZE; |
G1.match_start -= WSIZE; |
559 |
strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */ |
G1.strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */ |
560 |
|
|
561 |
block_start -= WSIZE; |
G1.block_start -= WSIZE; |
562 |
|
|
563 |
for (n = 0; n < HASH_SIZE; n++) { |
for (n = 0; n < HASH_SIZE; n++) { |
564 |
m = head[n]; |
m = head[n]; |
565 |
head[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0); |
head[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0); |
566 |
} |
} |
567 |
for (n = 0; n < WSIZE; n++) { |
for (n = 0; n < WSIZE; n++) { |
568 |
m = prev[n]; |
m = G1.prev[n]; |
569 |
prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0); |
G1.prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0); |
570 |
/* If n is not on any hash chain, prev[n] is garbage but |
/* If n is not on any hash chain, prev[n] is garbage but |
571 |
* its value will never be used. |
* its value will never be used. |
572 |
*/ |
*/ |
574 |
more += WSIZE; |
more += WSIZE; |
575 |
} |
} |
576 |
/* At this point, more >= 2 */ |
/* At this point, more >= 2 */ |
577 |
if (!eofile) { |
if (!G1.eofile) { |
578 |
n = file_read(window + strstart + lookahead, more); |
n = file_read(G1.window + G1.strstart + G1.lookahead, more); |
579 |
if (n == 0 || n == (unsigned) -1) { |
if (n == 0 || n == (unsigned) -1) { |
580 |
eofile = 1; |
G1.eofile = 1; |
581 |
} else { |
} else { |
582 |
lookahead += n; |
G1.lookahead += n; |
583 |
} |
} |
584 |
} |
} |
585 |
} |
} |
601 |
static int longest_match(IPos cur_match) |
static int longest_match(IPos cur_match) |
602 |
{ |
{ |
603 |
unsigned chain_length = max_chain_length; /* max hash chain length */ |
unsigned chain_length = max_chain_length; /* max hash chain length */ |
604 |
uch *scan = window + strstart; /* current string */ |
uch *scan = G1.window + G1.strstart; /* current string */ |
605 |
uch *match; /* matched string */ |
uch *match; /* matched string */ |
606 |
int len; /* length of current match */ |
int len; /* length of current match */ |
607 |
int best_len = prev_length; /* best match length so far */ |
int best_len = G1.prev_length; /* best match length so far */ |
608 |
IPos limit = strstart > (IPos) MAX_DIST ? strstart - (IPos) MAX_DIST : 0; |
IPos limit = G1.strstart > (IPos) MAX_DIST ? G1.strstart - (IPos) MAX_DIST : 0; |
609 |
/* Stop when cur_match becomes <= limit. To simplify the code, |
/* Stop when cur_match becomes <= limit. To simplify the code, |
610 |
* we prevent matches with the string of window index 0. |
* we prevent matches with the string of window index 0. |
611 |
*/ |
*/ |
616 |
#if HASH_BITS < 8 || MAX_MATCH != 258 |
#if HASH_BITS < 8 || MAX_MATCH != 258 |
617 |
# error Code too clever |
# error Code too clever |
618 |
#endif |
#endif |
619 |
uch *strend = window + strstart + MAX_MATCH; |
uch *strend = G1.window + G1.strstart + MAX_MATCH; |
620 |
uch scan_end1 = scan[best_len - 1]; |
uch scan_end1 = scan[best_len - 1]; |
621 |
uch scan_end = scan[best_len]; |
uch scan_end = scan[best_len]; |
622 |
|
|
623 |
/* Do not waste too much time if we already have a good match: */ |
/* Do not waste too much time if we already have a good match: */ |
624 |
if (prev_length >= good_match) { |
if (G1.prev_length >= good_match) { |
625 |
chain_length >>= 2; |
chain_length >>= 2; |
626 |
} |
} |
627 |
Assert(strstart <= WINDOW_SIZE - MIN_LOOKAHEAD, "insufficient lookahead"); |
Assert(G1.strstart <= WINDOW_SIZE - MIN_LOOKAHEAD, "insufficient lookahead"); |
628 |
|
|
629 |
do { |
do { |
630 |
Assert(cur_match < strstart, "no future"); |
Assert(cur_match < G1.strstart, "no future"); |
631 |
match = window + cur_match; |
match = G1.window + cur_match; |
632 |
|
|
633 |
/* Skip to next match if the match length cannot increase |
/* Skip to next match if the match length cannot increase |
634 |
* or if the match length is less than 2: |
* or if the match length is less than 2: |
659 |
scan = strend - MAX_MATCH; |
scan = strend - MAX_MATCH; |
660 |
|
|
661 |
if (len > best_len) { |
if (len > best_len) { |
662 |
match_start = cur_match; |
G1.match_start = cur_match; |
663 |
best_len = len; |
best_len = len; |
664 |
if (len >= nice_match) |
if (len >= nice_match) |
665 |
break; |
break; |
666 |
scan_end1 = scan[best_len - 1]; |
scan_end1 = scan[best_len - 1]; |
667 |
scan_end = scan[best_len]; |
scan_end = scan[best_len]; |
668 |
} |
} |
669 |
} while ((cur_match = prev[cur_match & WMASK]) > limit |
} while ((cur_match = G1.prev[cur_match & WMASK]) > limit |
670 |
&& --chain_length != 0); |
&& --chain_length != 0); |
671 |
|
|
672 |
return best_len; |
return best_len; |
680 |
static void check_match(IPos start, IPos match, int length) |
static void check_match(IPos start, IPos match, int length) |
681 |
{ |
{ |
682 |
/* check that the match is indeed a match */ |
/* check that the match is indeed a match */ |
683 |
if (memcmp(window + match, window + start, length) != 0) { |
if (memcmp(G1.window + match, G1.window + start, length) != 0) { |
684 |
bb_error_msg(" start %d, match %d, length %d", start, match, length); |
bb_error_msg(" start %d, match %d, length %d", start, match, length); |
685 |
bb_error_msg("invalid match"); |
bb_error_msg("invalid match"); |
686 |
} |
} |
687 |
if (verbose > 1) { |
if (verbose > 1) { |
688 |
bb_error_msg("\\[%d,%d]", start - match, length); |
bb_error_msg("\\[%d,%d]", start - match, length); |
689 |
do { |
do { |
690 |
putc(window[start++], stderr); |
fputc(G1.window[start++], stderr); |
691 |
} while (--length != 0); |
} while (--length != 0); |
692 |
} |
} |
693 |
} |
} |
731 |
* Addison-Wesley, 1983. ISBN 0-201-06672-6. |
* Addison-Wesley, 1983. ISBN 0-201-06672-6. |
732 |
* |
* |
733 |
* INTERFACE |
* INTERFACE |
734 |
* void ct_init(ush *attr, int *methodp) |
* void ct_init() |
735 |
* Allocate the match buffer, initialize the various tables and save |
* Allocate the match buffer, initialize the various tables [and save |
736 |
* the location of the internal file attribute (ascii/binary) and |
* the location of the internal file attribute (ascii/binary) and |
737 |
* method (DEFLATE/STORE) |
* method (DEFLATE/STORE) -- deleted in bbox] |
738 |
* |
* |
739 |
* void ct_tally(int dist, int lc); |
* void ct_tally(int dist, int lc); |
740 |
* Save the match info and tally the frequency counts. |
* Save the match info and tally the frequency counts. |
769 |
#define BL_CODES 19 |
#define BL_CODES 19 |
770 |
/* number of codes used to transfer the bit lengths */ |
/* number of codes used to transfer the bit lengths */ |
771 |
|
|
|
typedef uch extra_bits_t; |
|
|
|
|
772 |
/* extra bits for each length code */ |
/* extra bits for each length code */ |
773 |
static const extra_bits_t extra_lbits[LENGTH_CODES]= { |
static const uint8_t extra_lbits[LENGTH_CODES] ALIGN1 = { |
774 |
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, |
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, |
775 |
4, 4, 5, 5, 5, 5, 0 |
4, 4, 5, 5, 5, 5, 0 |
776 |
}; |
}; |
777 |
|
|
778 |
/* extra bits for each distance code */ |
/* extra bits for each distance code */ |
779 |
static const extra_bits_t extra_dbits[D_CODES] = { |
static const uint8_t extra_dbits[D_CODES] ALIGN1 = { |
780 |
0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, |
0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, |
781 |
10, 10, 11, 11, 12, 12, 13, 13 |
10, 10, 11, 11, 12, 12, 13, 13 |
782 |
}; |
}; |
783 |
|
|
784 |
/* extra bits for each bit length code */ |
/* extra bits for each bit length code */ |
785 |
static const extra_bits_t extra_blbits[BL_CODES] = { |
static const uint8_t extra_blbits[BL_CODES] ALIGN1 = { |
786 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 }; |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 }; |
787 |
|
|
788 |
|
/* number of codes at each bit length for an optimal tree */ |
789 |
|
static const uint8_t bl_order[BL_CODES] ALIGN1 = { |
790 |
|
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; |
791 |
|
|
792 |
#define STORED_BLOCK 0 |
#define STORED_BLOCK 0 |
793 |
#define STATIC_TREES 1 |
#define STATIC_TREES 1 |
794 |
#define DYN_TREES 2 |
#define DYN_TREES 2 |
857 |
#define HEAP_SIZE (2*L_CODES + 1) |
#define HEAP_SIZE (2*L_CODES + 1) |
858 |
/* maximum heap size */ |
/* maximum heap size */ |
859 |
|
|
860 |
////static int heap[HEAP_SIZE]; /* heap used to build the Huffman trees */ |
typedef struct tree_desc { |
861 |
////let's try this |
ct_data *dyn_tree; /* the dynamic tree */ |
862 |
static ush heap[HEAP_SIZE]; /* heap used to build the Huffman trees */ |
ct_data *static_tree; /* corresponding static tree or NULL */ |
863 |
static int heap_len; /* number of elements in the heap */ |
const uint8_t *extra_bits; /* extra bits for each code or NULL */ |
864 |
static int heap_max; /* element of largest frequency */ |
int extra_base; /* base index for extra_bits */ |
865 |
|
int elems; /* max number of elements in the tree */ |
866 |
|
int max_length; /* max bit length for the codes */ |
867 |
|
int max_code; /* largest code with non zero frequency */ |
868 |
|
} tree_desc; |
869 |
|
|
870 |
|
struct globals2 { |
871 |
|
|
872 |
|
ush heap[HEAP_SIZE]; /* heap used to build the Huffman trees */ |
873 |
|
int heap_len; /* number of elements in the heap */ |
874 |
|
int heap_max; /* element of largest frequency */ |
875 |
|
|
876 |
/* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. |
/* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. |
877 |
* The same heap array is used to build all trees. |
* The same heap array is used to build all trees. |
878 |
*/ |
*/ |
879 |
|
|
880 |
static ct_data dyn_ltree[HEAP_SIZE]; /* literal and length tree */ |
ct_data dyn_ltree[HEAP_SIZE]; /* literal and length tree */ |
881 |
static ct_data dyn_dtree[2 * D_CODES + 1]; /* distance tree */ |
ct_data dyn_dtree[2 * D_CODES + 1]; /* distance tree */ |
882 |
|
|
883 |
static ct_data static_ltree[L_CODES + 2]; |
ct_data static_ltree[L_CODES + 2]; |
884 |
|
|
885 |
/* The static literal tree. Since the bit lengths are imposed, there is no |
/* The static literal tree. Since the bit lengths are imposed, there is no |
886 |
* need for the L_CODES extra codes used during heap construction. However |
* need for the L_CODES extra codes used during heap construction. However |
888 |
* below). |
* below). |
889 |
*/ |
*/ |
890 |
|
|
891 |
static ct_data static_dtree[D_CODES]; |
ct_data static_dtree[D_CODES]; |
892 |
|
|
893 |
/* The static distance tree. (Actually a trivial tree since all codes use |
/* The static distance tree. (Actually a trivial tree since all codes use |
894 |
* 5 bits.) |
* 5 bits.) |
895 |
*/ |
*/ |
896 |
|
|
897 |
static ct_data bl_tree[2 * BL_CODES + 1]; |
ct_data bl_tree[2 * BL_CODES + 1]; |
898 |
|
|
899 |
/* Huffman tree for the bit lengths */ |
/* Huffman tree for the bit lengths */ |
900 |
|
|
901 |
typedef struct tree_desc { |
tree_desc l_desc; |
902 |
ct_data *dyn_tree; /* the dynamic tree */ |
tree_desc d_desc; |
903 |
ct_data *static_tree; /* corresponding static tree or NULL */ |
tree_desc bl_desc; |
|
const extra_bits_t *extra_bits; /* extra bits for each code or NULL */ |
|
|
int extra_base; /* base index for extra_bits */ |
|
|
int elems; /* max number of elements in the tree */ |
|
|
int max_length; /* max bit length for the codes */ |
|
|
int max_code; /* largest code with non zero frequency */ |
|
|
} tree_desc; |
|
|
|
|
|
static tree_desc l_desc = { |
|
|
dyn_ltree, static_ltree, extra_lbits, |
|
|
LITERALS + 1, L_CODES, MAX_BITS, 0 |
|
|
}; |
|
904 |
|
|
905 |
static tree_desc d_desc = { |
ush bl_count[MAX_BITS + 1]; |
|
dyn_dtree, static_dtree, extra_dbits, 0, D_CODES, MAX_BITS, 0 |
|
|
}; |
|
|
|
|
|
static tree_desc bl_desc = { |
|
|
bl_tree, NULL, extra_blbits, 0, BL_CODES, MAX_BL_BITS, 0 |
|
|
}; |
|
|
|
|
|
|
|
|
static ush bl_count[MAX_BITS + 1]; |
|
|
|
|
|
/* number of codes at each bit length for an optimal tree */ |
|
|
|
|
|
static const uch bl_order[BL_CODES] = { |
|
|
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 |
|
|
}; |
|
906 |
|
|
907 |
/* The lengths of the bit length codes are sent in order of decreasing |
/* The lengths of the bit length codes are sent in order of decreasing |
908 |
* probability, to avoid transmitting the lengths for unused bit length codes. |
* probability, to avoid transmitting the lengths for unused bit length codes. |
909 |
*/ |
*/ |
910 |
|
|
911 |
static uch depth[2 * L_CODES + 1]; |
uch depth[2 * L_CODES + 1]; |
912 |
|
|
913 |
/* Depth of each subtree used as tie breaker for trees of equal frequency */ |
/* Depth of each subtree used as tie breaker for trees of equal frequency */ |
914 |
|
|
915 |
static uch length_code[MAX_MATCH - MIN_MATCH + 1]; |
uch length_code[MAX_MATCH - MIN_MATCH + 1]; |
916 |
|
|
917 |
/* length code for each normalized match length (0 == MIN_MATCH) */ |
/* length code for each normalized match length (0 == MIN_MATCH) */ |
918 |
|
|
919 |
static uch dist_code[512]; |
uch dist_code[512]; |
920 |
|
|
921 |
/* distance codes. The first 256 values correspond to the distances |
/* distance codes. The first 256 values correspond to the distances |
922 |
* 3 .. 258, the last 256 values correspond to the top 8 bits of |
* 3 .. 258, the last 256 values correspond to the top 8 bits of |
923 |
* the 15 bit distances. |
* the 15 bit distances. |
924 |
*/ |
*/ |
925 |
|
|
926 |
static int base_length[LENGTH_CODES]; |
int base_length[LENGTH_CODES]; |
927 |
|
|
928 |
/* First normalized length for each code (0 = MIN_MATCH) */ |
/* First normalized length for each code (0 = MIN_MATCH) */ |
929 |
|
|
930 |
static int base_dist[D_CODES]; |
int base_dist[D_CODES]; |
931 |
|
|
932 |
/* First normalized distance for each code (0 = distance of 1) */ |
/* First normalized distance for each code (0 = distance of 1) */ |
933 |
|
|
934 |
static uch flag_buf[LIT_BUFSIZE / 8]; |
uch flag_buf[LIT_BUFSIZE / 8]; |
935 |
|
|
936 |
/* flag_buf is a bit array distinguishing literals from lengths in |
/* flag_buf is a bit array distinguishing literals from lengths in |
937 |
* l_buf, thus indicating the presence or absence of a distance. |
* l_buf, thus indicating the presence or absence of a distance. |
938 |
*/ |
*/ |
939 |
|
|
940 |
static unsigned last_lit; /* running index in l_buf */ |
unsigned last_lit; /* running index in l_buf */ |
941 |
static unsigned last_dist; /* running index in d_buf */ |
unsigned last_dist; /* running index in d_buf */ |
942 |
static unsigned last_flags; /* running index in flag_buf */ |
unsigned last_flags; /* running index in flag_buf */ |
943 |
static uch flags; /* current flags not yet saved in flag_buf */ |
uch flags; /* current flags not yet saved in flag_buf */ |
944 |
static uch flag_bit; /* current bit used in flags */ |
uch flag_bit; /* current bit used in flags */ |
945 |
|
|
946 |
/* bits are filled in flags starting at bit 0 (least significant). |
/* bits are filled in flags starting at bit 0 (least significant). |
947 |
* Note: these flags are overkill in the current code since we don't |
* Note: these flags are overkill in the current code since we don't |
948 |
* take advantage of DIST_BUFSIZE == LIT_BUFSIZE. |
* take advantage of DIST_BUFSIZE == LIT_BUFSIZE. |
949 |
*/ |
*/ |
950 |
|
|
951 |
static ulg opt_len; /* bit length of current block with optimal trees */ |
ulg opt_len; /* bit length of current block with optimal trees */ |
952 |
static ulg static_len; /* bit length of current block with static trees */ |
ulg static_len; /* bit length of current block with static trees */ |
953 |
|
|
954 |
static ulg compressed_len; /* total bit length of compressed file */ |
ulg compressed_len; /* total bit length of compressed file */ |
955 |
|
}; |
956 |
|
|
957 |
|
#define G2ptr ((struct globals2*)(ptr_to_globals)) |
958 |
|
#define G2 (*G2ptr) |
959 |
|
|
|
static ush *file_type; /* pointer to UNKNOWN, BINARY or ASCII */ |
|
|
static int *file_method; /* pointer to DEFLATE or STORE */ |
|
960 |
|
|
961 |
/* =========================================================================== |
/* =========================================================================== |
962 |
*/ |
*/ |
981 |
#endif |
#endif |
982 |
|
|
983 |
#define D_CODE(dist) \ |
#define D_CODE(dist) \ |
984 |
((dist) < 256 ? dist_code[dist] : dist_code[256 + ((dist)>>7)]) |
((dist) < 256 ? G2.dist_code[dist] : G2.dist_code[256 + ((dist)>>7)]) |
985 |
/* Mapping from a distance to a distance code. dist is the distance - 1 and |
/* Mapping from a distance to a distance code. dist is the distance - 1 and |
986 |
* must not have side effects. dist_code[256] and dist_code[257] are never |
* must not have side effects. dist_code[256] and dist_code[257] are never |
987 |
* used. |
* used. |
998 |
|
|
999 |
/* Initialize the trees. */ |
/* Initialize the trees. */ |
1000 |
for (n = 0; n < L_CODES; n++) |
for (n = 0; n < L_CODES; n++) |
1001 |
dyn_ltree[n].Freq = 0; |
G2.dyn_ltree[n].Freq = 0; |
1002 |
for (n = 0; n < D_CODES; n++) |
for (n = 0; n < D_CODES; n++) |
1003 |
dyn_dtree[n].Freq = 0; |
G2.dyn_dtree[n].Freq = 0; |
1004 |
for (n = 0; n < BL_CODES; n++) |
for (n = 0; n < BL_CODES; n++) |
1005 |
bl_tree[n].Freq = 0; |
G2.bl_tree[n].Freq = 0; |
1006 |
|
|
1007 |
dyn_ltree[END_BLOCK].Freq = 1; |
G2.dyn_ltree[END_BLOCK].Freq = 1; |
1008 |
opt_len = static_len = 0; |
G2.opt_len = G2.static_len = 0; |
1009 |
last_lit = last_dist = last_flags = 0; |
G2.last_lit = G2.last_dist = G2.last_flags = 0; |
1010 |
flags = 0; |
G2.flags = 0; |
1011 |
flag_bit = 1; |
G2.flag_bit = 1; |
1012 |
} |
} |
1013 |
|
|
1014 |
|
|
1023 |
* the subtrees have equal frequency. This minimizes the worst case length. */ |
* the subtrees have equal frequency. This minimizes the worst case length. */ |
1024 |
#define SMALLER(tree, n, m) \ |
#define SMALLER(tree, n, m) \ |
1025 |
(tree[n].Freq < tree[m].Freq \ |
(tree[n].Freq < tree[m].Freq \ |
1026 |
|| (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) |
|| (tree[n].Freq == tree[m].Freq && G2.depth[n] <= G2.depth[m])) |
1027 |
|
|
1028 |
static void pqdownheap(ct_data * tree, int k) |
static void pqdownheap(ct_data * tree, int k) |
1029 |
{ |
{ |
1030 |
int v = heap[k]; |
int v = G2.heap[k]; |
1031 |
int j = k << 1; /* left son of k */ |
int j = k << 1; /* left son of k */ |
1032 |
|
|
1033 |
while (j <= heap_len) { |
while (j <= G2.heap_len) { |
1034 |
/* Set j to the smallest of the two sons: */ |
/* Set j to the smallest of the two sons: */ |
1035 |
if (j < heap_len && SMALLER(tree, heap[j + 1], heap[j])) |
if (j < G2.heap_len && SMALLER(tree, G2.heap[j + 1], G2.heap[j])) |
1036 |
j++; |
j++; |
1037 |
|
|
1038 |
/* Exit if v is smaller than both sons */ |
/* Exit if v is smaller than both sons */ |
1039 |
if (SMALLER(tree, v, heap[j])) |
if (SMALLER(tree, v, G2.heap[j])) |
1040 |
break; |
break; |
1041 |
|
|
1042 |
/* Exchange v with the smallest son */ |
/* Exchange v with the smallest son */ |
1043 |
heap[k] = heap[j]; |
G2.heap[k] = G2.heap[j]; |
1044 |
k = j; |
k = j; |
1045 |
|
|
1046 |
/* And continue down the tree, setting j to the left son of k */ |
/* And continue down the tree, setting j to the left son of k */ |
1047 |
j <<= 1; |
j <<= 1; |
1048 |
} |
} |
1049 |
heap[k] = v; |
G2.heap[k] = v; |
1050 |
} |
} |
1051 |
|
|
1052 |
|
|
1063 |
static void gen_bitlen(tree_desc * desc) |
static void gen_bitlen(tree_desc * desc) |
1064 |
{ |
{ |
1065 |
ct_data *tree = desc->dyn_tree; |
ct_data *tree = desc->dyn_tree; |
1066 |
const extra_bits_t *extra = desc->extra_bits; |
const uint8_t *extra = desc->extra_bits; |
1067 |
int base = desc->extra_base; |
int base = desc->extra_base; |
1068 |
int max_code = desc->max_code; |
int max_code = desc->max_code; |
1069 |
int max_length = desc->max_length; |
int max_length = desc->max_length; |
1076 |
int overflow = 0; /* number of elements with bit length too large */ |
int overflow = 0; /* number of elements with bit length too large */ |
1077 |
|
|
1078 |
for (bits = 0; bits <= MAX_BITS; bits++) |
for (bits = 0; bits <= MAX_BITS; bits++) |
1079 |
bl_count[bits] = 0; |
G2.bl_count[bits] = 0; |
1080 |
|
|
1081 |
/* In a first pass, compute the optimal bit lengths (which may |
/* In a first pass, compute the optimal bit lengths (which may |
1082 |
* overflow in the case of the bit length tree). |
* overflow in the case of the bit length tree). |
1083 |
*/ |
*/ |
1084 |
tree[heap[heap_max]].Len = 0; /* root of the heap */ |
tree[G2.heap[G2.heap_max]].Len = 0; /* root of the heap */ |
1085 |
|
|
1086 |
for (h = heap_max + 1; h < HEAP_SIZE; h++) { |
for (h = G2.heap_max + 1; h < HEAP_SIZE; h++) { |
1087 |
n = heap[h]; |
n = G2.heap[h]; |
1088 |
bits = tree[tree[n].Dad].Len + 1; |
bits = tree[tree[n].Dad].Len + 1; |
1089 |
if (bits > max_length) { |
if (bits > max_length) { |
1090 |
bits = max_length; |
bits = max_length; |
1096 |
if (n > max_code) |
if (n > max_code) |
1097 |
continue; /* not a leaf node */ |
continue; /* not a leaf node */ |
1098 |
|
|
1099 |
bl_count[bits]++; |
G2.bl_count[bits]++; |
1100 |
xbits = 0; |
xbits = 0; |
1101 |
if (n >= base) |
if (n >= base) |
1102 |
xbits = extra[n - base]; |
xbits = extra[n - base]; |
1103 |
f = tree[n].Freq; |
f = tree[n].Freq; |
1104 |
opt_len += (ulg) f *(bits + xbits); |
G2.opt_len += (ulg) f *(bits + xbits); |
1105 |
|
|
1106 |
if (stree) |
if (stree) |
1107 |
static_len += (ulg) f * (stree[n].Len + xbits); |
G2.static_len += (ulg) f * (stree[n].Len + xbits); |
1108 |
} |
} |
1109 |
if (overflow == 0) |
if (overflow == 0) |
1110 |
return; |
return; |
1115 |
/* Find the first bit length which could increase: */ |
/* Find the first bit length which could increase: */ |
1116 |
do { |
do { |
1117 |
bits = max_length - 1; |
bits = max_length - 1; |
1118 |
while (bl_count[bits] == 0) |
while (G2.bl_count[bits] == 0) |
1119 |
bits--; |
bits--; |
1120 |
bl_count[bits]--; /* move one leaf down the tree */ |
G2.bl_count[bits]--; /* move one leaf down the tree */ |
1121 |
bl_count[bits + 1] += 2; /* move one overflow item as its brother */ |
G2.bl_count[bits + 1] += 2; /* move one overflow item as its brother */ |
1122 |
bl_count[max_length]--; |
G2.bl_count[max_length]--; |
1123 |
/* The brother of the overflow item also moves one step up, |
/* The brother of the overflow item also moves one step up, |
1124 |
* but this does not affect bl_count[max_length] |
* but this does not affect bl_count[max_length] |
1125 |
*/ |
*/ |
1132 |
* from 'ar' written by Haruhiko Okumura.) |
* from 'ar' written by Haruhiko Okumura.) |
1133 |
*/ |
*/ |
1134 |
for (bits = max_length; bits != 0; bits--) { |
for (bits = max_length; bits != 0; bits--) { |
1135 |
n = bl_count[bits]; |
n = G2.bl_count[bits]; |
1136 |
while (n != 0) { |
while (n != 0) { |
1137 |
m = heap[--h]; |
m = G2.heap[--h]; |
1138 |
if (m > max_code) |
if (m > max_code) |
1139 |
continue; |
continue; |
1140 |
if (tree[m].Len != (unsigned) bits) { |
if (tree[m].Len != (unsigned) bits) { |
1141 |
Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len, bits)); |
Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len, bits)); |
1142 |
opt_len += ((int32_t) bits - tree[m].Len) * tree[m].Freq; |
G2.opt_len += ((int32_t) bits - tree[m].Len) * tree[m].Freq; |
1143 |
tree[m].Len = bits; |
tree[m].Len = bits; |
1144 |
} |
} |
1145 |
n--; |
n--; |
1167 |
* without bit reversal. |
* without bit reversal. |
1168 |
*/ |
*/ |
1169 |
for (bits = 1; bits <= MAX_BITS; bits++) { |
for (bits = 1; bits <= MAX_BITS; bits++) { |
1170 |
next_code[bits] = code = (code + bl_count[bits - 1]) << 1; |
next_code[bits] = code = (code + G2.bl_count[bits - 1]) << 1; |
1171 |
} |
} |
1172 |
/* Check that the bit counts in bl_count are consistent. The last code |
/* Check that the bit counts in bl_count are consistent. The last code |
1173 |
* must be all ones. |
* must be all ones. |
1174 |
*/ |
*/ |
1175 |
Assert(code + bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1, |
Assert(code + G2.bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1, |
1176 |
"inconsistent bit counts"); |
"inconsistent bit counts"); |
1177 |
Tracev((stderr, "\ngen_codes: max_code %d ", max_code)); |
Tracev((stderr, "\ngen_codes: max_code %d ", max_code)); |
1178 |
|
|
1184 |
/* Now reverse the bits */ |
/* Now reverse the bits */ |
1185 |
tree[n].Code = bi_reverse(next_code[len]++, len); |
tree[n].Code = bi_reverse(next_code[len]++, len); |
1186 |
|
|
1187 |
Tracec(tree != static_ltree, |
Tracec(tree != G2.static_ltree, |
1188 |
(stderr, "\nn %3d %c l %2d c %4x (%x) ", n, |
(stderr, "\nn %3d %c l %2d c %4x (%x) ", n, |
1189 |
(isgraph(n) ? n : ' '), len, tree[n].Code, |
(isgraph(n) ? n : ' '), len, tree[n].Code, |
1190 |
next_code[len] - 1)); |
next_code[len] - 1)); |
1208 |
/* Index within the heap array of least frequent node in the Huffman tree */ |
/* Index within the heap array of least frequent node in the Huffman tree */ |
1209 |
|
|
1210 |
#define PQREMOVE(tree, top) \ |
#define PQREMOVE(tree, top) \ |
1211 |
{ \ |
do { \ |
1212 |
top = heap[SMALLEST]; \ |
top = G2.heap[SMALLEST]; \ |
1213 |
heap[SMALLEST] = heap[heap_len--]; \ |
G2.heap[SMALLEST] = G2.heap[G2.heap_len--]; \ |
1214 |
pqdownheap(tree, SMALLEST); \ |
pqdownheap(tree, SMALLEST); \ |
1215 |
} |
} while (0) |
1216 |
|
|
1217 |
static void build_tree(tree_desc * desc) |
static void build_tree(tree_desc * desc) |
1218 |
{ |
{ |
1227 |
* heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. |
* heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. |
1228 |
* heap[0] is not used. |
* heap[0] is not used. |
1229 |
*/ |
*/ |
1230 |
heap_len = 0, heap_max = HEAP_SIZE; |
G2.heap_len = 0; |
1231 |
|
G2.heap_max = HEAP_SIZE; |
1232 |
|
|
1233 |
for (n = 0; n < elems; n++) { |
for (n = 0; n < elems; n++) { |
1234 |
if (tree[n].Freq != 0) { |
if (tree[n].Freq != 0) { |
1235 |
heap[++heap_len] = max_code = n; |
G2.heap[++G2.heap_len] = max_code = n; |
1236 |
depth[n] = 0; |
G2.depth[n] = 0; |
1237 |
} else { |
} else { |
1238 |
tree[n].Len = 0; |
tree[n].Len = 0; |
1239 |
} |
} |
1244 |
* possible code. So to avoid special checks later on we force at least |
* possible code. So to avoid special checks later on we force at least |
1245 |
* two codes of non zero frequency. |
* two codes of non zero frequency. |
1246 |
*/ |
*/ |
1247 |
while (heap_len < 2) { |
while (G2.heap_len < 2) { |
1248 |
int new = heap[++heap_len] = (max_code < 2 ? ++max_code : 0); |
int new = G2.heap[++G2.heap_len] = (max_code < 2 ? ++max_code : 0); |
1249 |
|
|
1250 |
tree[new].Freq = 1; |
tree[new].Freq = 1; |
1251 |
depth[new] = 0; |
G2.depth[new] = 0; |
1252 |
opt_len--; |
G2.opt_len--; |
1253 |
if (stree) |
if (stree) |
1254 |
static_len -= stree[new].Len; |
G2.static_len -= stree[new].Len; |
1255 |
/* new is 0 or 1 so it does not have extra bits */ |
/* new is 0 or 1 so it does not have extra bits */ |
1256 |
} |
} |
1257 |
desc->max_code = max_code; |
desc->max_code = max_code; |
1259 |
/* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, |
/* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, |
1260 |
* establish sub-heaps of increasing lengths: |
* establish sub-heaps of increasing lengths: |
1261 |
*/ |
*/ |
1262 |
for (n = heap_len / 2; n >= 1; n--) |
for (n = G2.heap_len / 2; n >= 1; n--) |
1263 |
pqdownheap(tree, n); |
pqdownheap(tree, n); |
1264 |
|
|
1265 |
/* Construct the Huffman tree by repeatedly combining the least two |
/* Construct the Huffman tree by repeatedly combining the least two |
1267 |
*/ |
*/ |
1268 |
do { |
do { |
1269 |
PQREMOVE(tree, n); /* n = node of least frequency */ |
PQREMOVE(tree, n); /* n = node of least frequency */ |
1270 |
m = heap[SMALLEST]; /* m = node of next least frequency */ |
m = G2.heap[SMALLEST]; /* m = node of next least frequency */ |
1271 |
|
|
1272 |
heap[--heap_max] = n; /* keep the nodes sorted by frequency */ |
G2.heap[--G2.heap_max] = n; /* keep the nodes sorted by frequency */ |
1273 |
heap[--heap_max] = m; |
G2.heap[--G2.heap_max] = m; |
1274 |
|
|
1275 |
/* Create a new node father of n and m */ |
/* Create a new node father of n and m */ |
1276 |
tree[node].Freq = tree[n].Freq + tree[m].Freq; |
tree[node].Freq = tree[n].Freq + tree[m].Freq; |
1277 |
depth[node] = MAX(depth[n], depth[m]) + 1; |
G2.depth[node] = MAX(G2.depth[n], G2.depth[m]) + 1; |
1278 |
tree[n].Dad = tree[m].Dad = (ush) node; |
tree[n].Dad = tree[m].Dad = (ush) node; |
1279 |
#ifdef DUMP_BL_TREE |
#ifdef DUMP_BL_TREE |
1280 |
if (tree == bl_tree) { |
if (tree == G2.bl_tree) { |
1281 |
bb_error_msg("\nnode %d(%d), sons %d(%d) %d(%d)", |
bb_error_msg("\nnode %d(%d), sons %d(%d) %d(%d)", |
1282 |
node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); |
node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); |
1283 |
} |
} |
1284 |
#endif |
#endif |
1285 |
/* and insert the new node in the heap */ |
/* and insert the new node in the heap */ |
1286 |
heap[SMALLEST] = node++; |
G2.heap[SMALLEST] = node++; |
1287 |
pqdownheap(tree, SMALLEST); |
pqdownheap(tree, SMALLEST); |
1288 |
|
|
1289 |
} while (heap_len >= 2); |
} while (G2.heap_len >= 2); |
1290 |
|
|
1291 |
heap[--heap_max] = heap[SMALLEST]; |
G2.heap[--G2.heap_max] = G2.heap[SMALLEST]; |
1292 |
|
|
1293 |
/* At this point, the fields freq and dad are set. We can now |
/* At this point, the fields freq and dad are set. We can now |
1294 |
* generate the bit lengths. |
* generate the bit lengths. |
1329 |
continue; |
continue; |
1330 |
|
|
1331 |
if (count < min_count) { |
if (count < min_count) { |
1332 |
bl_tree[curlen].Freq += count; |
G2.bl_tree[curlen].Freq += count; |
1333 |
} else if (curlen != 0) { |
} else if (curlen != 0) { |
1334 |
if (curlen != prevlen) |
if (curlen != prevlen) |
1335 |
bl_tree[curlen].Freq++; |
G2.bl_tree[curlen].Freq++; |
1336 |
bl_tree[REP_3_6].Freq++; |
G2.bl_tree[REP_3_6].Freq++; |
1337 |
} else if (count <= 10) { |
} else if (count <= 10) { |
1338 |
bl_tree[REPZ_3_10].Freq++; |
G2.bl_tree[REPZ_3_10].Freq++; |
1339 |
} else { |
} else { |
1340 |
bl_tree[REPZ_11_138].Freq++; |
G2.bl_tree[REPZ_11_138].Freq++; |
1341 |
} |
} |
1342 |
count = 0; |
count = 0; |
1343 |
prevlen = curlen; |
prevlen = curlen; |
1380 |
continue; |
continue; |
1381 |
} else if (count < min_count) { |
} else if (count < min_count) { |
1382 |
do { |
do { |
1383 |
SEND_CODE(curlen, bl_tree); |
SEND_CODE(curlen, G2.bl_tree); |
1384 |
} while (--count); |
} while (--count); |
1385 |
} else if (curlen != 0) { |
} else if (curlen != 0) { |
1386 |
if (curlen != prevlen) { |
if (curlen != prevlen) { |
1387 |
SEND_CODE(curlen, bl_tree); |
SEND_CODE(curlen, G2.bl_tree); |
1388 |
count--; |
count--; |
1389 |
} |
} |
1390 |
Assert(count >= 3 && count <= 6, " 3_6?"); |
Assert(count >= 3 && count <= 6, " 3_6?"); |
1391 |
SEND_CODE(REP_3_6, bl_tree); |
SEND_CODE(REP_3_6, G2.bl_tree); |
1392 |
send_bits(count - 3, 2); |
send_bits(count - 3, 2); |
1393 |
} else if (count <= 10) { |
} else if (count <= 10) { |
1394 |
SEND_CODE(REPZ_3_10, bl_tree); |
SEND_CODE(REPZ_3_10, G2.bl_tree); |
1395 |
send_bits(count - 3, 3); |
send_bits(count - 3, 3); |
1396 |
} else { |
} else { |
1397 |
SEND_CODE(REPZ_11_138, bl_tree); |
SEND_CODE(REPZ_11_138, G2.bl_tree); |
1398 |
send_bits(count - 11, 7); |
send_bits(count - 11, 7); |
1399 |
} |
} |
1400 |
count = 0; |
count = 0; |
1422 |
int max_blindex; /* index of last bit length code of non zero freq */ |
int max_blindex; /* index of last bit length code of non zero freq */ |
1423 |
|
|
1424 |
/* Determine the bit length frequencies for literal and distance trees */ |
/* Determine the bit length frequencies for literal and distance trees */ |
1425 |
scan_tree((ct_data *) dyn_ltree, l_desc.max_code); |
scan_tree(G2.dyn_ltree, G2.l_desc.max_code); |
1426 |
scan_tree((ct_data *) dyn_dtree, d_desc.max_code); |
scan_tree(G2.dyn_dtree, G2.d_desc.max_code); |
1427 |
|
|
1428 |
/* Build the bit length tree: */ |
/* Build the bit length tree: */ |
1429 |
build_tree((tree_desc *) &bl_desc); |
build_tree(&G2.bl_desc); |
1430 |
/* opt_len now includes the length of the tree representations, except |
/* opt_len now includes the length of the tree representations, except |
1431 |
* the lengths of the bit lengths codes and the 5+5+4 bits for the counts. |
* the lengths of the bit lengths codes and the 5+5+4 bits for the counts. |
1432 |
*/ |
*/ |
1436 |
* 3 but the actual value used is 4.) |
* 3 but the actual value used is 4.) |
1437 |
*/ |
*/ |
1438 |
for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) { |
for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) { |
1439 |
if (bl_tree[bl_order[max_blindex]].Len != 0) |
if (G2.bl_tree[bl_order[max_blindex]].Len != 0) |
1440 |
break; |
break; |
1441 |
} |
} |
1442 |
/* Update opt_len to include the bit length tree and counts */ |
/* Update opt_len to include the bit length tree and counts */ |
1443 |
opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4; |
G2.opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4; |
1444 |
Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", opt_len, static_len)); |
Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", G2.opt_len, G2.static_len)); |
1445 |
|
|
1446 |
return max_blindex; |
return max_blindex; |
1447 |
} |
} |
1465 |
send_bits(blcodes - 4, 4); /* not -3 as stated in appnote.txt */ |
send_bits(blcodes - 4, 4); /* not -3 as stated in appnote.txt */ |
1466 |
for (rank = 0; rank < blcodes; rank++) { |
for (rank = 0; rank < blcodes; rank++) { |
1467 |
Tracev((stderr, "\nbl code %2d ", bl_order[rank])); |
Tracev((stderr, "\nbl code %2d ", bl_order[rank])); |
1468 |
send_bits(bl_tree[bl_order[rank]].Len, 3); |
send_bits(G2.bl_tree[bl_order[rank]].Len, 3); |
1469 |
} |
} |
1470 |
Tracev((stderr, "\nbl tree: sent %ld", bits_sent)); |
Tracev((stderr, "\nbl tree: sent %ld", G1.bits_sent)); |
|
|
|
|
send_tree((ct_data *) dyn_ltree, lcodes - 1); /* send the literal tree */ |
|
|
Tracev((stderr, "\nlit tree: sent %ld", bits_sent)); |
|
1471 |
|
|
1472 |
send_tree((ct_data *) dyn_dtree, dcodes - 1); /* send the distance tree */ |
send_tree((ct_data *) G2.dyn_ltree, lcodes - 1); /* send the literal tree */ |
1473 |
Tracev((stderr, "\ndist tree: sent %ld", bits_sent)); |
Tracev((stderr, "\nlit tree: sent %ld", G1.bits_sent)); |
|
} |
|
|
|
|
|
|
|
|
/* =========================================================================== |
|
|
* Set the file type to ASCII or BINARY, using a crude approximation: |
|
|
* binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. |
|
|
* IN assertion: the fields freq of dyn_ltree are set and the total of all |
|
|
* frequencies does not exceed 64K (to fit in an int on 16 bit machines). |
|
|
*/ |
|
|
static void set_file_type(void) |
|
|
{ |
|
|
int n = 0; |
|
|
unsigned ascii_freq = 0; |
|
|
unsigned bin_freq = 0; |
|
1474 |
|
|
1475 |
while (n < 7) |
send_tree((ct_data *) G2.dyn_dtree, dcodes - 1); /* send the distance tree */ |
1476 |
bin_freq += dyn_ltree[n++].Freq; |
Tracev((stderr, "\ndist tree: sent %ld", G1.bits_sent)); |
|
while (n < 128) |
|
|
ascii_freq += dyn_ltree[n++].Freq; |
|
|
while (n < LITERALS) |
|
|
bin_freq += dyn_ltree[n++].Freq; |
|
|
*file_type = (bin_freq > (ascii_freq >> 2)) ? BINARY : ASCII; |
|
|
if (*file_type == BINARY && translate_eol) { |
|
|
bb_error_msg("-l used on binary file"); |
|
|
} |
|
1477 |
} |
} |
1478 |
|
|
1479 |
|
|
1483 |
*/ |
*/ |
1484 |
static int ct_tally(int dist, int lc) |
static int ct_tally(int dist, int lc) |
1485 |
{ |
{ |
1486 |
l_buf[last_lit++] = lc; |
G1.l_buf[G2.last_lit++] = lc; |
1487 |
if (dist == 0) { |
if (dist == 0) { |
1488 |
/* lc is the unmatched char */ |
/* lc is the unmatched char */ |
1489 |
dyn_ltree[lc].Freq++; |
G2.dyn_ltree[lc].Freq++; |
1490 |
} else { |
} else { |
1491 |
/* Here, lc is the match length - MIN_MATCH */ |
/* Here, lc is the match length - MIN_MATCH */ |
1492 |
dist--; /* dist = match distance - 1 */ |
dist--; /* dist = match distance - 1 */ |
1495 |
&& (ush) D_CODE(dist) < (ush) D_CODES, "ct_tally: bad match" |
&& (ush) D_CODE(dist) < (ush) D_CODES, "ct_tally: bad match" |
1496 |
); |
); |
1497 |
|
|
1498 |
dyn_ltree[length_code[lc] + LITERALS + 1].Freq++; |
G2.dyn_ltree[G2.length_code[lc] + LITERALS + 1].Freq++; |
1499 |
dyn_dtree[D_CODE(dist)].Freq++; |
G2.dyn_dtree[D_CODE(dist)].Freq++; |
1500 |
|
|
1501 |
d_buf[last_dist++] = dist; |
G1.d_buf[G2.last_dist++] = dist; |
1502 |
flags |= flag_bit; |
G2.flags |= G2.flag_bit; |
1503 |
} |
} |
1504 |
flag_bit <<= 1; |
G2.flag_bit <<= 1; |
1505 |
|
|
1506 |
/* Output the flags if they fill a byte: */ |
/* Output the flags if they fill a byte: */ |
1507 |
if ((last_lit & 7) == 0) { |
if ((G2.last_lit & 7) == 0) { |
1508 |
flag_buf[last_flags++] = flags; |
G2.flag_buf[G2.last_flags++] = G2.flags; |
1509 |
flags = 0, flag_bit = 1; |
G2.flags = 0; |
1510 |
|
G2.flag_bit = 1; |
1511 |
} |
} |
1512 |
/* Try to guess if it is profitable to stop the current block here */ |
/* Try to guess if it is profitable to stop the current block here */ |
1513 |
if ((last_lit & 0xfff) == 0) { |
if ((G2.last_lit & 0xfff) == 0) { |
1514 |
/* Compute an upper bound for the compressed length */ |
/* Compute an upper bound for the compressed length */ |
1515 |
ulg out_length = last_lit * 8L; |
ulg out_length = G2.last_lit * 8L; |
1516 |
ulg in_length = (ulg) strstart - block_start; |
ulg in_length = (ulg) G1.strstart - G1.block_start; |
1517 |
int dcode; |
int dcode; |
1518 |
|
|
1519 |
for (dcode = 0; dcode < D_CODES; dcode++) { |
for (dcode = 0; dcode < D_CODES; dcode++) { |
1520 |
out_length += dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]); |
out_length += G2.dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]); |
1521 |
} |
} |
1522 |
out_length >>= 3; |
out_length >>= 3; |
1523 |
Trace((stderr, |
Trace((stderr, |
1524 |
"\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", |
"\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", |
1525 |
last_lit, last_dist, in_length, out_length, |
G2.last_lit, G2.last_dist, in_length, out_length, |
1526 |
100L - out_length * 100L / in_length)); |
100L - out_length * 100L / in_length)); |
1527 |
if (last_dist < last_lit / 2 && out_length < in_length / 2) |
if (G2.last_dist < G2.last_lit / 2 && out_length < in_length / 2) |
1528 |
return 1; |
return 1; |
1529 |
} |
} |
1530 |
return (last_lit == LIT_BUFSIZE - 1 || last_dist == DIST_BUFSIZE); |
return (G2.last_lit == LIT_BUFSIZE - 1 || G2.last_dist == DIST_BUFSIZE); |
1531 |
/* We avoid equality with LIT_BUFSIZE because of wraparound at 64K |
/* We avoid equality with LIT_BUFSIZE because of wraparound at 64K |
1532 |
* on 16 bit machines and because stored blocks are restricted to |
* on 16 bit machines and because stored blocks are restricted to |
1533 |
* 64K-1 bytes. |
* 64K-1 bytes. |
1548 |
unsigned code; /* the code to send */ |
unsigned code; /* the code to send */ |
1549 |
int extra; /* number of extra bits to send */ |
int extra; /* number of extra bits to send */ |
1550 |
|
|
1551 |
if (last_lit != 0) do { |
if (G2.last_lit != 0) do { |
1552 |
if ((lx & 7) == 0) |
if ((lx & 7) == 0) |
1553 |
flag = flag_buf[fx++]; |
flag = G2.flag_buf[fx++]; |
1554 |
lc = l_buf[lx++]; |
lc = G1.l_buf[lx++]; |
1555 |
if ((flag & 1) == 0) { |
if ((flag & 1) == 0) { |
1556 |
SEND_CODE(lc, ltree); /* send a literal byte */ |
SEND_CODE(lc, ltree); /* send a literal byte */ |
1557 |
Tracecv(isgraph(lc), (stderr, " '%c' ", lc)); |
Tracecv(isgraph(lc), (stderr, " '%c' ", lc)); |
1558 |
} else { |
} else { |
1559 |
/* Here, lc is the match length - MIN_MATCH */ |
/* Here, lc is the match length - MIN_MATCH */ |
1560 |
code = length_code[lc]; |
code = G2.length_code[lc]; |
1561 |
SEND_CODE(code + LITERALS + 1, ltree); /* send the length code */ |
SEND_CODE(code + LITERALS + 1, ltree); /* send the length code */ |
1562 |
extra = extra_lbits[code]; |
extra = extra_lbits[code]; |
1563 |
if (extra != 0) { |
if (extra != 0) { |
1564 |
lc -= base_length[code]; |
lc -= G2.base_length[code]; |
1565 |
send_bits(lc, extra); /* send the extra length bits */ |
send_bits(lc, extra); /* send the extra length bits */ |
1566 |
} |
} |
1567 |
dist = d_buf[dx++]; |
dist = G1.d_buf[dx++]; |
1568 |
/* Here, dist is the match distance - 1 */ |
/* Here, dist is the match distance - 1 */ |
1569 |
code = D_CODE(dist); |
code = D_CODE(dist); |
1570 |
Assert(code < D_CODES, "bad d_code"); |
Assert(code < D_CODES, "bad d_code"); |
1572 |
SEND_CODE(code, dtree); /* send the distance code */ |
SEND_CODE(code, dtree); /* send the distance code */ |
1573 |
extra = extra_dbits[code]; |
extra = extra_dbits[code]; |
1574 |
if (extra != 0) { |
if (extra != 0) { |
1575 |
dist -= base_dist[code]; |
dist -= G2.base_dist[code]; |
1576 |
send_bits(dist, extra); /* send the extra distance bits */ |
send_bits(dist, extra); /* send the extra distance bits */ |
1577 |
} |
} |
1578 |
} /* literal or match pair ? */ |
} /* literal or match pair ? */ |
1579 |
flag >>= 1; |
flag >>= 1; |
1580 |
} while (lx < last_lit); |
} while (lx < G2.last_lit); |
1581 |
|
|
1582 |
SEND_CODE(END_BLOCK, ltree); |
SEND_CODE(END_BLOCK, ltree); |
1583 |
} |
} |
1593 |
ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ |
ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ |
1594 |
int max_blindex; /* index of last bit length code of non zero freq */ |
int max_blindex; /* index of last bit length code of non zero freq */ |
1595 |
|
|
1596 |
flag_buf[last_flags] = flags; /* Save the flags for the last 8 items */ |
G2.flag_buf[G2.last_flags] = G2.flags; /* Save the flags for the last 8 items */ |
|
|
|
|
/* Check if the file is ascii or binary */ |
|
|
if (*file_type == (ush) UNKNOWN) |
|
|
set_file_type(); |
|
1597 |
|
|
1598 |
/* Construct the literal and distance trees */ |
/* Construct the literal and distance trees */ |
1599 |
build_tree((tree_desc *) &l_desc); |
build_tree(&G2.l_desc); |
1600 |
Tracev((stderr, "\nlit data: dyn %ld, stat %ld", opt_len, static_len)); |
Tracev((stderr, "\nlit data: dyn %ld, stat %ld", G2.opt_len, G2.static_len)); |
1601 |
|
|
1602 |
build_tree((tree_desc *) &d_desc); |
build_tree(&G2.d_desc); |
1603 |
Tracev((stderr, "\ndist data: dyn %ld, stat %ld", opt_len, static_len)); |
Tracev((stderr, "\ndist data: dyn %ld, stat %ld", G2.opt_len, G2.static_len)); |
1604 |
/* At this point, opt_len and static_len are the total bit lengths of |
/* At this point, opt_len and static_len are the total bit lengths of |
1605 |
* the compressed block data, excluding the tree representations. |
* the compressed block data, excluding the tree representations. |
1606 |
*/ |
*/ |
1611 |
max_blindex = build_bl_tree(); |
max_blindex = build_bl_tree(); |
1612 |
|
|
1613 |
/* Determine the best encoding. Compute first the block length in bytes */ |
/* Determine the best encoding. Compute first the block length in bytes */ |
1614 |
opt_lenb = (opt_len + 3 + 7) >> 3; |
opt_lenb = (G2.opt_len + 3 + 7) >> 3; |
1615 |
static_lenb = (static_len + 3 + 7) >> 3; |
static_lenb = (G2.static_len + 3 + 7) >> 3; |
1616 |
|
|
1617 |
Trace((stderr, |
Trace((stderr, |
1618 |
"\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ", |
"\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ", |
1619 |
opt_lenb, opt_len, static_lenb, static_len, stored_len, |
opt_lenb, G2.opt_len, static_lenb, G2.static_len, stored_len, |
1620 |
last_lit, last_dist)); |
G2.last_lit, G2.last_dist)); |
1621 |
|
|
1622 |
if (static_lenb <= opt_lenb) |
if (static_lenb <= opt_lenb) |
1623 |
opt_lenb = static_lenb; |
opt_lenb = static_lenb; |
1626 |
* and if the zip file can be seeked (to rewrite the local header), |
* and if the zip file can be seeked (to rewrite the local header), |
1627 |
* the whole file is transformed into a stored file: |
* the whole file is transformed into a stored file: |
1628 |
*/ |
*/ |
1629 |
if (stored_len <= opt_lenb && eof && compressed_len == 0L && seekable()) { |
if (stored_len <= opt_lenb && eof && G2.compressed_len == 0L && seekable()) { |
1630 |
/* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ |
/* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ |
1631 |
if (buf == NULL) |
if (buf == NULL) |
1632 |
bb_error_msg("block vanished"); |
bb_error_msg("block vanished"); |
1633 |
|
|
1634 |
copy_block(buf, (unsigned) stored_len, 0); /* without header */ |
copy_block(buf, (unsigned) stored_len, 0); /* without header */ |
1635 |
compressed_len = stored_len << 3; |
G2.compressed_len = stored_len << 3; |
|
*file_method = STORED; |
|
1636 |
|
|
1637 |
} else if (stored_len + 4 <= opt_lenb && buf != NULL) { |
} else if (stored_len + 4 <= opt_lenb && buf != NULL) { |
1638 |
/* 4: two words for the lengths */ |
/* 4: two words for the lengths */ |
1643 |
* transform a block into a stored block. |
* transform a block into a stored block. |
1644 |
*/ |
*/ |
1645 |
send_bits((STORED_BLOCK << 1) + eof, 3); /* send block type */ |
send_bits((STORED_BLOCK << 1) + eof, 3); /* send block type */ |
1646 |
compressed_len = (compressed_len + 3 + 7) & ~7L; |
G2.compressed_len = (G2.compressed_len + 3 + 7) & ~7L; |
1647 |
compressed_len += (stored_len + 4) << 3; |
G2.compressed_len += (stored_len + 4) << 3; |
1648 |
|
|
1649 |
copy_block(buf, (unsigned) stored_len, 1); /* with header */ |
copy_block(buf, (unsigned) stored_len, 1); /* with header */ |
1650 |
|
|
1651 |
} else if (static_lenb == opt_lenb) { |
} else if (static_lenb == opt_lenb) { |
1652 |
send_bits((STATIC_TREES << 1) + eof, 3); |
send_bits((STATIC_TREES << 1) + eof, 3); |
1653 |
compress_block((ct_data *) static_ltree, (ct_data *) static_dtree); |
compress_block((ct_data *) G2.static_ltree, (ct_data *) G2.static_dtree); |
1654 |
compressed_len += 3 + static_len; |
G2.compressed_len += 3 + G2.static_len; |
1655 |
} else { |
} else { |
1656 |
send_bits((DYN_TREES << 1) + eof, 3); |
send_bits((DYN_TREES << 1) + eof, 3); |
1657 |
send_all_trees(l_desc.max_code + 1, d_desc.max_code + 1, |
send_all_trees(G2.l_desc.max_code + 1, G2.d_desc.max_code + 1, |
1658 |
max_blindex + 1); |
max_blindex + 1); |
1659 |
compress_block((ct_data *) dyn_ltree, (ct_data *) dyn_dtree); |
compress_block((ct_data *) G2.dyn_ltree, (ct_data *) G2.dyn_dtree); |
1660 |
compressed_len += 3 + opt_len; |
G2.compressed_len += 3 + G2.opt_len; |
1661 |
} |
} |
1662 |
Assert(compressed_len == bits_sent, "bad compressed size"); |
Assert(G2.compressed_len == G1.bits_sent, "bad compressed size"); |
1663 |
init_block(); |
init_block(); |
1664 |
|
|
1665 |
if (eof) { |
if (eof) { |
1666 |
bi_windup(); |
bi_windup(); |
1667 |
compressed_len += 7; /* align on byte boundary */ |
G2.compressed_len += 7; /* align on byte boundary */ |
1668 |
} |
} |
1669 |
Tracev((stderr, "\ncomprlen %lu(%lu) ", compressed_len >> 3, |
Tracev((stderr, "\ncomprlen %lu(%lu) ", G2.compressed_len >> 3, |
1670 |
compressed_len - 7 * eof)); |
G2.compressed_len - 7 * eof)); |
1671 |
|
|
1672 |
return compressed_len >> 3; |
return G2.compressed_len >> 3; |
1673 |
} |
} |
1674 |
|
|
1675 |
|
|
1696 |
* IN assertion: strstart is set to the end of the current match. */ |
* IN assertion: strstart is set to the end of the current match. */ |
1697 |
#define FLUSH_BLOCK(eof) \ |
#define FLUSH_BLOCK(eof) \ |
1698 |
flush_block( \ |
flush_block( \ |
1699 |
block_start >= 0L \ |
G1.block_start >= 0L \ |
1700 |
? (char*)&window[(unsigned)block_start] \ |
? (char*)&G1.window[(unsigned)G1.block_start] \ |
1701 |
: (char*)NULL, \ |
: (char*)NULL, \ |
1702 |
(ulg)strstart - block_start, \ |
(ulg)G1.strstart - G1.block_start, \ |
1703 |
(eof) \ |
(eof) \ |
1704 |
) |
) |
1705 |
|
|
1710 |
* input characters and the first MIN_MATCH bytes of s are valid |
* input characters and the first MIN_MATCH bytes of s are valid |
1711 |
* (except for the last MIN_MATCH-1 bytes of the input file). */ |
* (except for the last MIN_MATCH-1 bytes of the input file). */ |
1712 |
#define INSERT_STRING(s, match_head) \ |
#define INSERT_STRING(s, match_head) \ |
1713 |
{ \ |
do { \ |
1714 |
UPDATE_HASH(ins_h, window[(s) + MIN_MATCH-1]); \ |
UPDATE_HASH(G1.ins_h, G1.window[(s) + MIN_MATCH-1]); \ |
1715 |
prev[(s) & WMASK] = match_head = head[ins_h]; \ |
G1.prev[(s) & WMASK] = match_head = head[G1.ins_h]; \ |
1716 |
head[ins_h] = (s); \ |
head[G1.ins_h] = (s); \ |
1717 |
} |
} while (0) |
1718 |
|
|
1719 |
static ulg deflate(void) |
static ulg deflate(void) |
1720 |
{ |
{ |
1725 |
unsigned match_length = MIN_MATCH - 1; /* length of best match */ |
unsigned match_length = MIN_MATCH - 1; /* length of best match */ |
1726 |
|
|
1727 |
/* Process the input block. */ |
/* Process the input block. */ |
1728 |
while (lookahead != 0) { |
while (G1.lookahead != 0) { |
1729 |
/* Insert the string window[strstart .. strstart+2] in the |
/* Insert the string window[strstart .. strstart+2] in the |
1730 |
* dictionary, and set hash_head to the head of the hash chain: |
* dictionary, and set hash_head to the head of the hash chain: |
1731 |
*/ |
*/ |
1732 |
INSERT_STRING(strstart, hash_head); |
INSERT_STRING(G1.strstart, hash_head); |
1733 |
|
|
1734 |
/* Find the longest match, discarding those <= prev_length. |
/* Find the longest match, discarding those <= prev_length. |
1735 |
*/ |
*/ |
1736 |
prev_length = match_length, prev_match = match_start; |
G1.prev_length = match_length; |
1737 |
|
prev_match = G1.match_start; |
1738 |
match_length = MIN_MATCH - 1; |
match_length = MIN_MATCH - 1; |
1739 |
|
|
1740 |
if (hash_head != 0 && prev_length < max_lazy_match |
if (hash_head != 0 && G1.prev_length < max_lazy_match |
1741 |
&& strstart - hash_head <= MAX_DIST |
&& G1.strstart - hash_head <= MAX_DIST |
1742 |
) { |
) { |
1743 |
/* To simplify the code, we prevent matches with the string |
/* To simplify the code, we prevent matches with the string |
1744 |
* of window index 0 (in particular we have to avoid a match |
* of window index 0 (in particular we have to avoid a match |
1746 |
*/ |
*/ |
1747 |
match_length = longest_match(hash_head); |
match_length = longest_match(hash_head); |
1748 |
/* longest_match() sets match_start */ |
/* longest_match() sets match_start */ |
1749 |
if (match_length > lookahead) |
if (match_length > G1.lookahead) |
1750 |
match_length = lookahead; |
match_length = G1.lookahead; |
1751 |
|
|
1752 |
/* Ignore a length 3 match if it is too distant: */ |
/* Ignore a length 3 match if it is too distant: */ |
1753 |
if (match_length == MIN_MATCH && strstart - match_start > TOO_FAR) { |
if (match_length == MIN_MATCH && G1.strstart - G1.match_start > TOO_FAR) { |
1754 |
/* If prev_match is also MIN_MATCH, match_start is garbage |
/* If prev_match is also MIN_MATCH, G1.match_start is garbage |
1755 |
* but we will ignore the current match anyway. |
* but we will ignore the current match anyway. |
1756 |
*/ |
*/ |
1757 |
match_length--; |
match_length--; |
1760 |
/* If there was a match at the previous step and the current |
/* If there was a match at the previous step and the current |
1761 |
* match is not better, output the previous match: |
* match is not better, output the previous match: |
1762 |
*/ |
*/ |
1763 |
if (prev_length >= MIN_MATCH && match_length <= prev_length) { |
if (G1.prev_length >= MIN_MATCH && match_length <= G1.prev_length) { |
1764 |
check_match(strstart - 1, prev_match, prev_length); |
check_match(G1.strstart - 1, prev_match, G1.prev_length); |
1765 |
flush = ct_tally(strstart - 1 - prev_match, prev_length - MIN_MATCH); |
flush = ct_tally(G1.strstart - 1 - prev_match, G1.prev_length - MIN_MATCH); |
1766 |
|
|
1767 |
/* Insert in hash table all strings up to the end of the match. |
/* Insert in hash table all strings up to the end of the match. |
1768 |
* strstart-1 and strstart are already inserted. |
* strstart-1 and strstart are already inserted. |
1769 |
*/ |
*/ |
1770 |
lookahead -= prev_length - 1; |
G1.lookahead -= G1.prev_length - 1; |
1771 |
prev_length -= 2; |
G1.prev_length -= 2; |
1772 |
do { |
do { |
1773 |
strstart++; |
G1.strstart++; |
1774 |
INSERT_STRING(strstart, hash_head); |
INSERT_STRING(G1.strstart, hash_head); |
1775 |
/* strstart never exceeds WSIZE-MAX_MATCH, so there are |
/* strstart never exceeds WSIZE-MAX_MATCH, so there are |
1776 |
* always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH |
* always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH |
1777 |
* these bytes are garbage, but it does not matter since the |
* these bytes are garbage, but it does not matter since the |
1778 |
* next lookahead bytes will always be emitted as literals. |
* next lookahead bytes will always be emitted as literals. |
1779 |
*/ |
*/ |
1780 |
} while (--prev_length != 0); |
} while (--G1.prev_length != 0); |
1781 |
match_available = 0; |
match_available = 0; |
1782 |
match_length = MIN_MATCH - 1; |
match_length = MIN_MATCH - 1; |
1783 |
strstart++; |
G1.strstart++; |
1784 |
if (flush) { |
if (flush) { |
1785 |
FLUSH_BLOCK(0); |
FLUSH_BLOCK(0); |
1786 |
block_start = strstart; |
G1.block_start = G1.strstart; |
1787 |
} |
} |
1788 |
} else if (match_available) { |
} else if (match_available) { |
1789 |
/* If there was no match at the previous position, output a |
/* If there was no match at the previous position, output a |
1790 |
* single literal. If there was a match but the current match |
* single literal. If there was a match but the current match |
1791 |
* is longer, truncate the previous match to a single literal. |
* is longer, truncate the previous match to a single literal. |
1792 |
*/ |
*/ |
1793 |
Tracevv((stderr, "%c", window[strstart - 1])); |
Tracevv((stderr, "%c", G1.window[G1.strstart - 1])); |
1794 |
if (ct_tally(0, window[strstart - 1])) { |
if (ct_tally(0, G1.window[G1.strstart - 1])) { |
1795 |
FLUSH_BLOCK(0); |
FLUSH_BLOCK(0); |
1796 |
block_start = strstart; |
G1.block_start = G1.strstart; |
1797 |
} |
} |
1798 |
strstart++; |
G1.strstart++; |
1799 |
lookahead--; |
G1.lookahead--; |
1800 |
} else { |
} else { |
1801 |
/* There is no previous match to compare with, wait for |
/* There is no previous match to compare with, wait for |
1802 |
* the next step to decide. |
* the next step to decide. |
1803 |
*/ |
*/ |
1804 |
match_available = 1; |
match_available = 1; |
1805 |
strstart++; |
G1.strstart++; |
1806 |
lookahead--; |
G1.lookahead--; |
1807 |
} |
} |
1808 |
Assert(strstart <= isize && lookahead <= isize, "a bit too far"); |
Assert(G1.strstart <= G1.isize && lookahead <= G1.isize, "a bit too far"); |
1809 |
|
|
1810 |
/* Make sure that we always have enough lookahead, except |
/* Make sure that we always have enough lookahead, except |
1811 |
* at the end of the input file. We need MAX_MATCH bytes |
* at the end of the input file. We need MAX_MATCH bytes |
1812 |
* for the next match, plus MIN_MATCH bytes to insert the |
* for the next match, plus MIN_MATCH bytes to insert the |
1813 |
* string following the next match. |
* string following the next match. |
1814 |
*/ |
*/ |
1815 |
while (lookahead < MIN_LOOKAHEAD && !eofile) |
while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile) |
1816 |
fill_window(); |
fill_window(); |
1817 |
} |
} |
1818 |
if (match_available) |
if (match_available) |
1819 |
ct_tally(0, window[strstart - 1]); |
ct_tally(0, G1.window[G1.strstart - 1]); |
1820 |
|
|
1821 |
return FLUSH_BLOCK(1); /* eof */ |
return FLUSH_BLOCK(1); /* eof */ |
1822 |
} |
} |
1825 |
/* =========================================================================== |
/* =========================================================================== |
1826 |
* Initialize the bit string routines. |
* Initialize the bit string routines. |
1827 |
*/ |
*/ |
1828 |
static void bi_init(void) //// int zipfile) |
static void bi_init(void) |
1829 |
{ |
{ |
1830 |
//// zfile = zipfile; |
G1.bi_buf = 0; |
1831 |
bi_buf = 0; |
G1.bi_valid = 0; |
|
bi_valid = 0; |
|
1832 |
#ifdef DEBUG |
#ifdef DEBUG |
1833 |
bits_sent = 0L; |
G1.bits_sent = 0L; |
1834 |
#endif |
#endif |
1835 |
} |
} |
1836 |
|
|
1850 |
*flagsp |= 2; /* FAST 4, SLOW 2 */ |
*flagsp |= 2; /* FAST 4, SLOW 2 */ |
1851 |
/* ??? reduce max_chain_length for binary files */ |
/* ??? reduce max_chain_length for binary files */ |
1852 |
|
|
1853 |
strstart = 0; |
G1.strstart = 0; |
1854 |
block_start = 0L; |
G1.block_start = 0L; |
1855 |
|
|
1856 |
lookahead = file_read(window, |
G1.lookahead = file_read(G1.window, |
1857 |
sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE); |
sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE); |
1858 |
|
|
1859 |
if (lookahead == 0 || lookahead == (unsigned) -1) { |
if (G1.lookahead == 0 || G1.lookahead == (unsigned) -1) { |
1860 |
eofile = 1; |
G1.eofile = 1; |
1861 |
lookahead = 0; |
G1.lookahead = 0; |
1862 |
return; |
return; |
1863 |
} |
} |
1864 |
eofile = 0; |
G1.eofile = 0; |
1865 |
/* Make sure that we always have enough lookahead. This is important |
/* Make sure that we always have enough lookahead. This is important |
1866 |
* if input comes from a device such as a tty. |
* if input comes from a device such as a tty. |
1867 |
*/ |
*/ |
1868 |
while (lookahead < MIN_LOOKAHEAD && !eofile) |
while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile) |
1869 |
fill_window(); |
fill_window(); |
1870 |
|
|
1871 |
ins_h = 0; |
G1.ins_h = 0; |
1872 |
for (j = 0; j < MIN_MATCH - 1; j++) |
for (j = 0; j < MIN_MATCH - 1; j++) |
1873 |
UPDATE_HASH(ins_h, window[j]); |
UPDATE_HASH(G1.ins_h, G1.window[j]); |
1874 |
/* If lookahead < MIN_MATCH, ins_h is garbage, but this is |
/* If lookahead < MIN_MATCH, ins_h is garbage, but this is |
1875 |
* not important since only literal bytes will be emitted. |
* not important since only literal bytes will be emitted. |
1876 |
*/ |
*/ |
1883 |
* (DEFLATE/STORE). |
* (DEFLATE/STORE). |
1884 |
* One callsite in zip() |
* One callsite in zip() |
1885 |
*/ |
*/ |
1886 |
static void ct_init(ush * attr, int *methodp) |
static void ct_init(void) |
1887 |
{ |
{ |
1888 |
int n; /* iterates over tree elements */ |
int n; /* iterates over tree elements */ |
1889 |
int length; /* length value */ |
int length; /* length value */ |
1890 |
int code; /* code value */ |
int code; /* code value */ |
1891 |
int dist; /* distance index */ |
int dist; /* distance index */ |
1892 |
|
|
1893 |
file_type = attr; |
G2.compressed_len = 0L; |
|
file_method = methodp; |
|
|
compressed_len = 0L; |
|
1894 |
|
|
1895 |
#ifdef NOT_NEEDED |
#ifdef NOT_NEEDED |
1896 |
if (static_dtree[0].Len != 0) |
if (G2.static_dtree[0].Len != 0) |
1897 |
return; /* ct_init already called */ |
return; /* ct_init already called */ |
1898 |
#endif |
#endif |
1899 |
|
|
1900 |
/* Initialize the mapping length (0..255) -> length code (0..28) */ |
/* Initialize the mapping length (0..255) -> length code (0..28) */ |
1901 |
length = 0; |
length = 0; |
1902 |
for (code = 0; code < LENGTH_CODES - 1; code++) { |
for (code = 0; code < LENGTH_CODES - 1; code++) { |
1903 |
base_length[code] = length; |
G2.base_length[code] = length; |
1904 |
for (n = 0; n < (1 << extra_lbits[code]); n++) { |
for (n = 0; n < (1 << extra_lbits[code]); n++) { |
1905 |
length_code[length++] = code; |
G2.length_code[length++] = code; |
1906 |
} |
} |
1907 |
} |
} |
1908 |
Assert(length == 256, "ct_init: length != 256"); |
Assert(length == 256, "ct_init: length != 256"); |
1910 |
* in two different ways: code 284 + 5 bits or code 285, so we |
* in two different ways: code 284 + 5 bits or code 285, so we |
1911 |
* overwrite length_code[255] to use the best encoding: |
* overwrite length_code[255] to use the best encoding: |
1912 |
*/ |
*/ |
1913 |
length_code[length - 1] = code; |
G2.length_code[length - 1] = code; |
1914 |
|
|
1915 |
/* Initialize the mapping dist (0..32K) -> dist code (0..29) */ |
/* Initialize the mapping dist (0..32K) -> dist code (0..29) */ |
1916 |
dist = 0; |
dist = 0; |
1917 |
for (code = 0; code < 16; code++) { |
for (code = 0; code < 16; code++) { |
1918 |
base_dist[code] = dist; |
G2.base_dist[code] = dist; |
1919 |
for (n = 0; n < (1 << extra_dbits[code]); n++) { |
for (n = 0; n < (1 << extra_dbits[code]); n++) { |
1920 |
dist_code[dist++] = code; |
G2.dist_code[dist++] = code; |
1921 |
} |
} |
1922 |
} |
} |
1923 |
Assert(dist == 256, "ct_init: dist != 256"); |
Assert(dist == 256, "ct_init: dist != 256"); |
1924 |
dist >>= 7; /* from now on, all distances are divided by 128 */ |
dist >>= 7; /* from now on, all distances are divided by 128 */ |
1925 |
for (; code < D_CODES; code++) { |
for (; code < D_CODES; code++) { |
1926 |
base_dist[code] = dist << 7; |
G2.base_dist[code] = dist << 7; |
1927 |
for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) { |
for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) { |
1928 |
dist_code[256 + dist++] = code; |
G2.dist_code[256 + dist++] = code; |
1929 |
} |
} |
1930 |
} |
} |
1931 |
Assert(dist == 256, "ct_init: 256+dist != 512"); |
Assert(dist == 256, "ct_init: 256+dist != 512"); |
1933 |
/* Construct the codes of the static literal tree */ |
/* Construct the codes of the static literal tree */ |
1934 |
/* already zeroed - it's in bss |
/* already zeroed - it's in bss |
1935 |
for (n = 0; n <= MAX_BITS; n++) |
for (n = 0; n <= MAX_BITS; n++) |
1936 |
bl_count[n] = 0; */ |
G2.bl_count[n] = 0; */ |
1937 |
|
|
1938 |
n = 0; |
n = 0; |
1939 |
while (n <= 143) { |
while (n <= 143) { |
1940 |
static_ltree[n++].Len = 8; |
G2.static_ltree[n++].Len = 8; |
1941 |
bl_count[8]++; |
G2.bl_count[8]++; |
1942 |
} |
} |
1943 |
while (n <= 255) { |
while (n <= 255) { |
1944 |
static_ltree[n++].Len = 9; |
G2.static_ltree[n++].Len = 9; |
1945 |
bl_count[9]++; |
G2.bl_count[9]++; |
1946 |
} |
} |
1947 |
while (n <= 279) { |
while (n <= 279) { |
1948 |
static_ltree[n++].Len = 7; |
G2.static_ltree[n++].Len = 7; |
1949 |
bl_count[7]++; |
G2.bl_count[7]++; |
1950 |
} |
} |
1951 |
while (n <= 287) { |
while (n <= 287) { |
1952 |
static_ltree[n++].Len = 8; |
G2.static_ltree[n++].Len = 8; |
1953 |
bl_count[8]++; |
G2.bl_count[8]++; |
1954 |
} |
} |
1955 |
/* Codes 286 and 287 do not exist, but we must include them in the |
/* Codes 286 and 287 do not exist, but we must include them in the |
1956 |
* tree construction to get a canonical Huffman tree (longest code |
* tree construction to get a canonical Huffman tree (longest code |
1957 |
* all ones) |
* all ones) |
1958 |
*/ |
*/ |
1959 |
gen_codes((ct_data *) static_ltree, L_CODES + 1); |
gen_codes((ct_data *) G2.static_ltree, L_CODES + 1); |
1960 |
|
|
1961 |
/* The static distance tree is trivial: */ |
/* The static distance tree is trivial: */ |
1962 |
for (n = 0; n < D_CODES; n++) { |
for (n = 0; n < D_CODES; n++) { |
1963 |
static_dtree[n].Len = 5; |
G2.static_dtree[n].Len = 5; |
1964 |
static_dtree[n].Code = bi_reverse(n, 5); |
G2.static_dtree[n].Code = bi_reverse(n, 5); |
1965 |
} |
} |
1966 |
|
|
1967 |
/* Initialize the first block of the first file: */ |
/* Initialize the first block of the first file: */ |
1972 |
/* =========================================================================== |
/* =========================================================================== |
1973 |
* Deflate in to out. |
* Deflate in to out. |
1974 |
* IN assertions: the input and output buffers are cleared. |
* IN assertions: the input and output buffers are cleared. |
|
* The variables time_stamp and save_orig_name are initialized. |
|
1975 |
*/ |
*/ |
1976 |
|
|
1977 |
/* put_header_byte is used for the compressed output |
static void zip(ulg time_stamp) |
|
* - for the initial 4 bytes that can't overflow the buffer. */ |
|
|
#define put_header_byte(c) outbuf[outcnt++] = (c) |
|
|
|
|
|
static void zip(int in, int out) |
|
1978 |
{ |
{ |
|
uch my_flags = 0; /* general purpose bit flags */ |
|
|
ush attr = 0; /* ascii/binary flag */ |
|
1979 |
ush deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */ |
ush deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */ |
1980 |
|
|
1981 |
ifd = in; |
G1.outcnt = 0; |
|
ofd = out; |
|
|
outcnt = 0; |
|
1982 |
|
|
1983 |
/* Write the header to the gzip file. See algorithm.doc for the format */ |
/* Write the header to the gzip file. See algorithm.doc for the format */ |
1984 |
|
/* magic header for gzip files: 1F 8B */ |
1985 |
method = DEFLATED; |
/* compression method: 8 (DEFLATED) */ |
1986 |
put_header_byte(0x1f); /* magic header for gzip files, 1F 8B */ |
/* general flags: 0 */ |
1987 |
put_header_byte(0x8b); |
put_32bit(0x00088b1f); |
|
put_header_byte(DEFLATED); /* compression method */ |
|
|
put_header_byte(my_flags); /* general flags */ |
|
1988 |
put_32bit(time_stamp); |
put_32bit(time_stamp); |
1989 |
|
|
1990 |
/* Write deflated file to zip file */ |
/* Write deflated file to zip file */ |
1991 |
crc = ~0; |
G1.crc = ~0; |
1992 |
|
|
1993 |
bi_init(); //// (out); |
bi_init(); |
1994 |
ct_init(&attr, &method); |
ct_init(); |
1995 |
lm_init(&deflate_flags); |
lm_init(&deflate_flags); |
1996 |
|
|
1997 |
put_8bit(deflate_flags); /* extra flags */ |
put_8bit(deflate_flags); /* extra flags */ |
2000 |
deflate(); |
deflate(); |
2001 |
|
|
2002 |
/* Write the crc and uncompressed size */ |
/* Write the crc and uncompressed size */ |
2003 |
put_32bit(~crc); |
put_32bit(~G1.crc); |
2004 |
put_32bit(isize); |
put_32bit(G1.isize); |
2005 |
|
|
2006 |
flush_outbuf(); |
flush_outbuf(); |
2007 |
} |
} |
2008 |
|
|
2009 |
|
|
2010 |
/* ======================================================================== */ |
/* ======================================================================== */ |
2011 |
static void abort_gzip(int ATTRIBUTE_UNUSED ignored) |
static |
2012 |
|
char* make_new_name_gzip(char *filename) |
2013 |
{ |
{ |
2014 |
exit(1); |
return xasprintf("%s.gz", filename); |
2015 |
} |
} |
2016 |
|
|
2017 |
int gzip_main(int argc, char **argv) |
static |
2018 |
|
USE_DESKTOP(long long) int pack_gzip(unpack_info_t *info UNUSED_PARAM) |
2019 |
{ |
{ |
2020 |
enum { |
struct stat s; |
|
OPT_tostdout = 0x1, |
|
|
OPT_force = 0x2, |
|
|
}; |
|
2021 |
|
|
2022 |
|
clear_bufs(); |
2023 |
|
s.st_ctime = 0; |
2024 |
|
fstat(STDIN_FILENO, &s); |
2025 |
|
zip(s.st_ctime); |
2026 |
|
return 0; |
2027 |
|
} |
2028 |
|
|
2029 |
|
/* |
2030 |
|
* Linux kernel build uses gzip -d -n. We accept and ignore it. |
2031 |
|
* Man page says: |
2032 |
|
* -n --no-name |
2033 |
|
* gzip: do not save the original file name and time stamp. |
2034 |
|
* (The original name is always saved if the name had to be truncated.) |
2035 |
|
* gunzip: do not restore the original file name/time even if present |
2036 |
|
* (remove only the gzip suffix from the compressed file name). |
2037 |
|
* This option is the default when decompressing. |
2038 |
|
* -N --name |
2039 |
|
* gzip: always save the original file name and time stamp (this is the default) |
2040 |
|
* gunzip: restore the original file name and time stamp if present. |
2041 |
|
*/ |
2042 |
|
|
2043 |
|
int gzip_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE; |
2044 |
|
#if ENABLE_GUNZIP |
2045 |
|
int gzip_main(int argc, char **argv) |
2046 |
|
#else |
2047 |
|
int gzip_main(int argc UNUSED_PARAM, char **argv) |
2048 |
|
#endif |
2049 |
|
{ |
2050 |
unsigned opt; |
unsigned opt; |
|
int inFileNum; |
|
|
int outFileNum; |
|
|
int i; |
|
|
struct stat statBuf; |
|
2051 |
|
|
2052 |
opt = getopt32(argc, argv, "cf123456789qv" USE_GUNZIP("d")); |
/* Must match bbunzip's constants OPT_STDOUT, OPT_FORCE! */ |
2053 |
//if (opt & 0x1) // -c |
opt = getopt32(argv, "cfv" USE_GUNZIP("dt") "q123456789n"); |
|
//if (opt & 0x2) // -f |
|
|
/* Ignore 1-9 (compression level) options */ |
|
|
//if (opt & 0x4) // -1 |
|
|
//if (opt & 0x8) // -2 |
|
|
//if (opt & 0x10) // -3 |
|
|
//if (opt & 0x20) // -4 |
|
|
//if (opt & 0x40) // -5 |
|
|
//if (opt & 0x80) // -6 |
|
|
//if (opt & 0x100) // -7 |
|
|
//if (opt & 0x200) // -8 |
|
|
//if (opt & 0x400) // -9 |
|
|
//if (opt & 0x800) // -q |
|
|
//if (opt & 0x1000) // -v |
|
2054 |
#if ENABLE_GUNZIP /* gunzip_main may not be visible... */ |
#if ENABLE_GUNZIP /* gunzip_main may not be visible... */ |
2055 |
if (opt & 0x2000) { // -d |
if (opt & 0x18) // -d and/or -t |
|
/* FIXME: getopt32 should not depend on optind */ |
|
|
optind = 1; |
|
2056 |
return gunzip_main(argc, argv); |
return gunzip_main(argc, argv); |
|
} |
|
2057 |
#endif |
#endif |
2058 |
|
option_mask32 &= 0x7; /* ignore -q, -0..9 */ |
2059 |
|
//if (opt & 0x1) // -c |
2060 |
|
//if (opt & 0x2) // -f |
2061 |
|
//if (opt & 0x4) // -v |
2062 |
|
argv += optind; |
2063 |
|
|
2064 |
foreground = signal(SIGINT, SIG_IGN) != SIG_IGN; |
SET_PTR_TO_GLOBALS(xzalloc(sizeof(struct globals) + sizeof(struct globals2)) |
2065 |
if (foreground) { |
+ sizeof(struct globals)); |
2066 |
signal(SIGINT, abort_gzip); |
barrier(); |
2067 |
} |
G2.l_desc.dyn_tree = G2.dyn_ltree; |
2068 |
#ifdef SIGTERM |
G2.l_desc.static_tree = G2.static_ltree; |
2069 |
if (signal(SIGTERM, SIG_IGN) != SIG_IGN) { |
G2.l_desc.extra_bits = extra_lbits; |
2070 |
signal(SIGTERM, abort_gzip); |
G2.l_desc.extra_base = LITERALS + 1; |
2071 |
} |
G2.l_desc.elems = L_CODES; |
2072 |
#endif |
G2.l_desc.max_length = MAX_BITS; |
2073 |
#ifdef SIGHUP |
//G2.l_desc.max_code = 0; |
2074 |
if (signal(SIGHUP, SIG_IGN) != SIG_IGN) { |
|
2075 |
signal(SIGHUP, abort_gzip); |
G2.d_desc.dyn_tree = G2.dyn_dtree; |
2076 |
} |
G2.d_desc.static_tree = G2.static_dtree; |
2077 |
#endif |
G2.d_desc.extra_bits = extra_dbits; |
2078 |
|
//G2.d_desc.extra_base = 0; |
2079 |
|
G2.d_desc.elems = D_CODES; |
2080 |
|
G2.d_desc.max_length = MAX_BITS; |
2081 |
|
//G2.d_desc.max_code = 0; |
2082 |
|
|
2083 |
|
G2.bl_desc.dyn_tree = G2.bl_tree; |
2084 |
|
//G2.bl_desc.static_tree = NULL; |
2085 |
|
G2.bl_desc.extra_bits = extra_blbits, |
2086 |
|
//G2.bl_desc.extra_base = 0; |
2087 |
|
G2.bl_desc.elems = BL_CODES; |
2088 |
|
G2.bl_desc.max_length = MAX_BL_BITS; |
2089 |
|
//G2.bl_desc.max_code = 0; |
2090 |
|
|
2091 |
/* Allocate all global buffers (for DYN_ALLOC option) */ |
/* Allocate all global buffers (for DYN_ALLOC option) */ |
2092 |
ALLOC(uch, l_buf, INBUFSIZ); |
ALLOC(uch, G1.l_buf, INBUFSIZ); |
2093 |
ALLOC(uch, outbuf, OUTBUFSIZ); |
ALLOC(uch, G1.outbuf, OUTBUFSIZ); |
2094 |
ALLOC(ush, d_buf, DIST_BUFSIZE); |
ALLOC(ush, G1.d_buf, DIST_BUFSIZE); |
2095 |
ALLOC(uch, window, 2L * WSIZE); |
ALLOC(uch, G1.window, 2L * WSIZE); |
2096 |
ALLOC(ush, prev, 1L << BITS); |
ALLOC(ush, G1.prev, 1L << BITS); |
2097 |
|
|
2098 |
/* Initialise the CRC32 table */ |
/* Initialise the CRC32 table */ |
2099 |
crc_32_tab = crc32_filltable(0); |
G1.crc_32_tab = crc32_filltable(NULL, 0); |
|
|
|
|
clear_bufs(); |
|
|
|
|
|
if (optind == argc) { |
|
|
time_stamp = 0; |
|
|
zip(STDIN_FILENO, STDOUT_FILENO); |
|
|
return exit_code; |
|
|
} |
|
|
|
|
|
for (i = optind; i < argc; i++) { |
|
|
char *path = NULL; |
|
|
|
|
|
clear_bufs(); |
|
|
if (LONE_DASH(argv[i])) { |
|
|
time_stamp = 0; |
|
|
inFileNum = STDIN_FILENO; |
|
|
outFileNum = STDOUT_FILENO; |
|
|
} else { |
|
|
inFileNum = xopen(argv[i], O_RDONLY); |
|
|
if (fstat(inFileNum, &statBuf) < 0) |
|
|
bb_perror_msg_and_die("%s", argv[i]); |
|
|
time_stamp = statBuf.st_ctime; |
|
|
|
|
|
if (!(opt & OPT_tostdout)) { |
|
|
path = xasprintf("%s.gz", argv[i]); |
|
|
|
|
|
/* Open output file */ |
|
|
#if defined(__GLIBC__) && __GLIBC__ >= 2 && __GLIBC_MINOR__ >= 1 && defined(O_NOFOLLOW) |
|
|
outFileNum = open(path, O_RDWR | O_CREAT | O_EXCL | O_NOFOLLOW); |
|
|
#else |
|
|
outFileNum = open(path, O_RDWR | O_CREAT | O_EXCL); |
|
|
#endif |
|
|
if (outFileNum < 0) { |
|
|
bb_perror_msg("%s", path); |
|
|
free(path); |
|
|
continue; |
|
|
} |
|
|
|
|
|
/* Set permissions on the file */ |
|
|
fchmod(outFileNum, statBuf.st_mode); |
|
|
} else |
|
|
outFileNum = STDOUT_FILENO; |
|
|
} |
|
|
|
|
|
if (path == NULL && isatty(outFileNum) && !(opt & OPT_force)) { |
|
|
bb_error_msg("compressed data not written " |
|
|
"to a terminal. Use -f to force compression."); |
|
|
free(path); |
|
|
continue; |
|
|
} |
|
|
|
|
|
zip(inFileNum, outFileNum); |
|
|
|
|
|
if (path != NULL) { |
|
|
char *delFileName; |
|
|
|
|
|
close(inFileNum); |
|
|
close(outFileNum); |
|
|
|
|
|
/* Delete the original file */ |
|
|
// Pity we don't propagate zip failures to this place... |
|
|
//if (zip_is_ok) |
|
|
delFileName = argv[i]; |
|
|
//else |
|
|
// delFileName = path; |
|
|
if (unlink(delFileName) < 0) |
|
|
bb_perror_msg("%s", delFileName); |
|
|
} |
|
|
|
|
|
free(path); |
|
|
} |
|
2100 |
|
|
2101 |
return exit_code; |
return bbunpack(argv, make_new_name_gzip, pack_gzip); |
2102 |
} |
} |