Changeset 1770 in MondoRescue for branches/stable/mindi-busybox/archival/gzip.c
- Timestamp:
- Nov 6, 2007, 11:01:53 AM (16 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/stable/mindi-busybox/archival/gzip.c
r821 r1770 6 6 * 7 7 * Originally adjusted for busybox by Charles P. Wright <cpw@unix.asb.com> 8 * 9 * 10 * 8 * "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." 11 11 * 12 12 * Adjusted further by Erik Andersen <andersen@codepoet.org> to support … … 17 17 */ 18 18 19 /* 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 30 * 0000047a b heap 31 * 00000480 b static_ltree 32 * 000008f4 b dyn_ltree 33 */ 34 35 /* TODO: full support for -v for DESKTOP 36 * "/usr/bin/gzip -v a bogus aa" should say: 37 a: 85.1% -- replaced with a.gz 38 gzip: bogus: No such file or directory 39 aa: 85.1% -- replaced with aa.gz 40 */ 41 42 #include "libbb.h" 43 44 45 /* =========================================================================== 46 */ 47 //#define DEBUG 1 48 /* Diagnostic functions */ 49 #ifdef DEBUG 50 # define Assert(cond,msg) { if (!(cond)) bb_error_msg(msg); } 51 # define Trace(x) fprintf x 52 # define Tracev(x) {if (verbose) fprintf x; } 53 # define Tracevv(x) {if (verbose > 1) fprintf x; } 54 # define Tracec(c,x) {if (verbose && (c)) fprintf x; } 55 # define Tracecv(c,x) {if (verbose > 1 && (c)) fprintf x; } 56 #else 57 # define Assert(cond,msg) 58 # define Trace(x) 59 # define Tracev(x) 60 # define Tracevv(x) 61 # define Tracec(c,x) 62 # define Tracecv(c,x) 63 #endif 64 65 66 /* =========================================================================== 67 */ 19 68 #define SMALL_MEM 20 21 #include <stdlib.h>22 #include <stdio.h>23 #include <string.h>24 #include <unistd.h>25 #include <errno.h>26 #include <sys/types.h>27 #include <signal.h>28 #include <utime.h>29 #include <ctype.h>30 #include <sys/types.h>31 #include <unistd.h>32 #include <dirent.h>33 #include <fcntl.h>34 #include <time.h>35 #include "busybox.h"36 37 typedef unsigned char uch;38 typedef unsigned short ush;39 typedef unsigned long ulg;40 41 /* Return codes from gzip */42 #define OK 043 #define ERROR 144 #define WARNING 245 46 /* Compression methods (see algorithm.doc) */47 /* Only STORED and DEFLATED are supported by this BusyBox module */48 #define STORED 049 /* methods 4 to 7 reserved */50 #define DEFLATED 851 52 /* To save memory for 16 bit systems, some arrays are overlaid between53 * the various modules:54 * deflate: prev+head window d_buf l_buf outbuf55 * unlzw: tab_prefix tab_suffix stack inbuf outbuf56 * For compression, input is done in window[]. For decompression, output57 * is done in window except for unlzw.58 */59 69 60 70 #ifndef INBUFSIZ … … 65 75 # endif 66 76 #endif 67 #define INBUF_EXTRA 64 /* required by unlzw() */68 77 69 78 #ifndef OUTBUFSIZ … … 74 83 # endif 75 84 #endif 76 #define OUTBUF_EXTRA 2048 /* required by unlzw() */77 85 78 86 #ifndef DIST_BUFSIZE … … 83 91 # endif 84 92 #endif 85 86 # define DECLARE(type, array, size) static type * array87 # define ALLOC(type, array, size) { \88 array = (type*)xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type)); \89 }90 # define FREE(array) {free(array), array=NULL;}91 92 #define tab_suffix window93 #define tab_prefix prev /* hash link (see deflate.c) */94 #define head (prev+WSIZE) /* hash head (see deflate.c) */95 96 static long bytes_in; /* number of input bytes */97 98 #define isize bytes_in99 /* for compatibility with old zip sources (to be cleaned) */100 101 typedef int file_t; /* Do not use stdio */102 103 #define NO_FILE (-1) /* in memory compression */104 105 106 #define PACK_MAGIC "\037\036" /* Magic header for packed files */107 #define GZIP_MAGIC "\037\213" /* Magic header for gzip files, 1F 8B */108 #define OLD_GZIP_MAGIC "\037\236" /* Magic header for gzip 0.5 = freeze 1.x */109 #define LZH_MAGIC "\037\240" /* Magic header for SCO LZH Compress files */110 #define PKZIP_MAGIC "\120\113\003\004" /* Magic header for pkzip files */111 93 112 94 /* gzip flag byte */ … … 124 106 125 107 #ifndef WSIZE 126 # define WSIZE 0x8000 127 #endif 108 # define WSIZE 0x8000 /* window size--must be a power of two, and */ 109 #endif /* at least 32K for zip's deflate method */ 128 110 129 111 #define MIN_MATCH 3 … … 141 123 */ 142 124 143 /* put_byte is used for the compressed output */ 144 #define put_byte(c) {outbuf[outcnt++]=(uch)(c); if (outcnt==OUTBUFSIZ)\ 145 flush_outbuf();} 146 147 148 /* Output a 32 bit value to the bit stream, lsb first */ 149 #if 0 150 #define put_long(n) { \ 151 put_short((n) & 0xffff); \ 152 put_short(((ulg)(n)) >> 16); \ 153 } 125 #ifndef MAX_PATH_LEN 126 # define MAX_PATH_LEN 1024 /* max pathname length */ 154 127 #endif 155 128 156 129 #define seekable() 0 /* force sequential output */ 157 130 #define translate_eol 0 /* no option -a yet */ 158 159 /* Diagnostic functions */160 #ifdef DEBUG161 # define Assert(cond,msg) {if(!(cond)) bb_error_msg(msg);}162 # define Trace(x) fprintf x163 # define Tracev(x) {if (verbose) fprintf x ;}164 # define Tracevv(x) {if (verbose>1) fprintf x ;}165 # define Tracec(c,x) {if (verbose && (c)) fprintf x ;}166 # define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}167 #else168 # define Assert(cond,msg)169 # define Trace(x)170 # define Tracev(x)171 # define Tracevv(x)172 # define Tracec(c,x)173 # define Tracecv(c,x)174 #endif175 176 #define WARN(msg) {if (!quiet) fprintf msg ; \177 if (exit_code == OK) exit_code = WARNING;}178 179 #ifndef MAX_PATH_LEN180 # define MAX_PATH_LEN 1024 /* max pathname length */181 #endif182 183 184 /* from zip.c: */185 static int zip(int in, int out);186 static int file_read(char *buf, unsigned size);187 188 /* from deflate.c */189 static void lm_init(ush * flags);190 static ulg deflate(void);191 192 /* from trees.c */193 static void ct_init(ush * attr, int *methodp);194 static int ct_tally(int dist, int lc);195 static ulg flush_block(char *buf, ulg stored_len, int eof);196 197 /* from bits.c */198 static void bi_init(file_t zipfile);199 static void send_bits(int value, int length);200 static unsigned bi_reverse(unsigned value, int length);201 static void bi_windup(void);202 static void copy_block(char *buf, unsigned len, int header);203 static int (*read_buf) (char *buf, unsigned size);204 205 /* from util.c: */206 static void flush_outbuf(void);207 208 /* lzw.h -- define the lzw functions.209 * Copyright (C) 1992-1993 Jean-loup Gailly.210 * This is free software; you can redistribute it and/or modify it under the211 * terms of the GNU General Public License, see the file COPYING.212 */213 131 214 132 #ifndef BITS … … 227 145 */ 228 146 229 /* tailor.h -- target dependent definitions230 * Copyright (C) 1992-1993 Jean-loup Gailly.231 * This is free software; you can redistribute it and/or modify it under the232 * terms of the GNU General Public License, see the file COPYING.233 */234 235 /* The target dependent definitions should be defined here only.236 * The target dependent functions should be defined in tailor.c.237 */238 239 240 /* Common defaults */241 242 #ifndef OS_CODE243 # define OS_CODE 0x03 /* assume Unix */244 #endif245 246 #ifndef PATH_SEP247 # define PATH_SEP '/'248 #endif249 250 #ifndef OPTIONS_VAR251 # define OPTIONS_VAR "GZIP"252 #endif253 254 #ifndef Z_SUFFIX255 # define Z_SUFFIX ".gz"256 #endif257 258 147 #ifdef MAX_EXT_CHARS 259 148 # define MAX_SUFFIX MAX_EXT_CHARS … … 262 151 #endif 263 152 264 /* global buffers */ 265 266 DECLARE(uch, inbuf, INBUFSIZ + INBUF_EXTRA); 267 DECLARE(uch, outbuf, OUTBUFSIZ + OUTBUF_EXTRA); 268 DECLARE(ush, d_buf, DIST_BUFSIZE); 269 DECLARE(uch, window, 2L * WSIZE); 270 DECLARE(ush, tab_prefix, 1L << BITS); 271 272 static int foreground; /* set if program run in foreground */ 273 static int method = DEFLATED; /* compression method */ 274 static int exit_code = OK; /* program exit code */ 275 static int part_nb; /* number of parts in .gz file */ 276 static long time_stamp; /* original time stamp (modification time) */ 277 static long ifile_size; /* input file size, -1 for devices (debug only) */ 278 static char z_suffix[MAX_SUFFIX + 1]; /* default suffix (can be set with --suffix) */ 279 static int z_len; /* strlen(z_suffix) */ 280 281 static int ifd; /* input file descriptor */ 282 static int ofd; /* output file descriptor */ 283 static unsigned insize; /* valid bytes in inbuf */ 284 static unsigned outcnt; /* bytes in output buffer */ 285 286 static uint32_t *crc_32_tab; 287 288 /* Output a 16 bit value, lsb first */ 289 static void put_short(ush w) 290 { 291 if (outcnt < OUTBUFSIZ - 2) { 292 outbuf[outcnt++] = (uch) ((w) & 0xff); 293 outbuf[outcnt++] = (uch) ((ush) (w) >> 8); 294 } else { 295 put_byte((uch) ((w) & 0xff)); 296 put_byte((uch) ((ush) (w) >> 8)); 297 } 298 } 299 300 /* ======================================================================== 301 * Signal and error handler. 302 */ 303 static void abort_gzip(int ATTRIBUTE_UNUSED ignored) 304 { 305 exit(ERROR); 306 } 307 308 /* =========================================================================== 309 * Clear input and output buffers 310 */ 311 static void clear_bufs(void) 312 { 313 outcnt = 0; 314 insize = 0; 315 bytes_in = 0L; 316 } 317 318 /* =========================================================================== 319 * Does the same as write(), but also handles partial pipe writes and checks 320 * for error return. 321 */ 322 static void write_buf(int fd, void *buf, unsigned cnt) 323 { 324 unsigned n; 325 326 while ((n = write(fd, buf, cnt)) != cnt) { 327 if (n == (unsigned) (-1)) bb_error_msg_and_die(bb_msg_write_error); 328 cnt -= n; 329 buf = (void *) ((char *) buf + n); 330 } 331 } 332 333 /* =========================================================================== 334 * Run a set of bytes through the crc shift register. If s is a NULL 335 * pointer, then initialize the crc shift register contents instead. 336 * Return the current crc in either case. 337 */ 338 static uint32_t updcrc(uch * s, unsigned n) 339 { 340 static uint32_t crc = ~0; /* shift register contents */ 341 uint32_t c; /* temporary variable */ 342 343 if (s == NULL) { 344 c = ~0; 345 } else { 346 c = crc; 347 if (n) 348 do { 349 c = crc_32_tab[((int) c ^ (*s++)) & 0xff] ^ (c >> 8); 350 } while (--n); 351 } 352 crc = c; 353 return ~c; 354 } 355 356 /* bits.c -- output variable-length bit strings 357 * Copyright (C) 1992-1993 Jean-loup Gailly 358 * This is free software; you can redistribute it and/or modify it under the 359 * terms of the GNU General Public License, see the file COPYING. 360 */ 361 362 363 /* 364 * PURPOSE 365 * 366 * Output variable-length bit strings. Compression can be done 367 * to a file or to memory. (The latter is not supported in this version.) 368 * 369 * DISCUSSION 370 * 371 * The PKZIP "deflate" file format interprets compressed file data 372 * as a sequence of bits. Multi-bit strings in the file may cross 373 * byte boundaries without restriction. 374 * 375 * The first bit of each byte is the low-order bit. 376 * 377 * The routines in this file allow a variable-length bit value to 378 * be output right-to-left (useful for literal values). For 379 * left-to-right output (useful for code strings from the tree routines), 380 * the bits must have been reversed first with bi_reverse(). 381 * 382 * For in-memory compression, the compressed bit stream goes directly 383 * into the requested output buffer. The input data is read in blocks 384 * by the mem_read() function. The buffer is limited to 64K on 16 bit 385 * machines. 386 * 387 * INTERFACE 388 * 389 * void bi_init (FILE *zipfile) 390 * Initialize the bit string routines. 391 * 392 * void send_bits (int value, int length) 393 * Write out a bit string, taking the source bits right to 394 * left. 395 * 396 * int bi_reverse (int value, int length) 397 * Reverse the bits of a bit string, taking the source bits left to 398 * right and emitting them right to left. 399 * 400 * void bi_windup (void) 401 * Write out any remaining bits in an incomplete byte. 402 * 403 * void copy_block(char *buf, unsigned len, int header) 404 * Copy a stored block to the zip file, storing first the length and 405 * its one's complement if requested. 406 * 407 */ 408 409 /* =========================================================================== 410 * Local data used by the "bit string" routines. 411 */ 412 413 static file_t zfile; /* output gzip file */ 414 415 static unsigned short bi_buf; 416 417 /* Output buffer. bits are inserted starting at the bottom (least significant 418 * bits). 419 */ 420 421 #define Buf_size (8 * 2*sizeof(char)) 422 /* Number of bits used within bi_buf. (bi_buf might be implemented on 423 * more than 16 bits on some systems.) 424 */ 425 426 static int bi_valid; 427 428 /* Current input function. Set to mem_read for in-memory compression */ 429 430 #ifdef DEBUG 431 ulg bits_sent; /* bit length of the compressed data */ 432 #endif 433 434 /* =========================================================================== 435 * Initialize the bit string routines. 436 */ 437 static void bi_init(file_t zipfile) 438 { 439 zfile = zipfile; 440 bi_buf = 0; 441 bi_valid = 0; 442 #ifdef DEBUG 443 bits_sent = 0L; 444 #endif 445 446 /* Set the defaults for file compression. They are set by memcompress 447 * for in-memory compression. 448 */ 449 if (zfile != NO_FILE) { 450 read_buf = file_read; 451 } 452 } 453 454 /* =========================================================================== 455 * Send a value on a given number of bits. 456 * IN assertion: length <= 16 and value fits in length bits. 457 */ 458 static void send_bits(int value, int length) 459 { 460 #ifdef DEBUG 461 Tracev((stderr, " l %2d v %4x ", length, value)); 462 Assert(length > 0 && length <= 15, "invalid length"); 463 bits_sent += (ulg) length; 464 #endif 465 /* If not enough room in bi_buf, use (valid) bits from bi_buf and 466 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 467 * unused bits in value. 468 */ 469 if (bi_valid > (int) Buf_size - length) { 470 bi_buf |= (value << bi_valid); 471 put_short(bi_buf); 472 bi_buf = (ush) value >> (Buf_size - bi_valid); 473 bi_valid += length - Buf_size; 474 } else { 475 bi_buf |= value << bi_valid; 476 bi_valid += length; 477 } 478 } 479 480 /* =========================================================================== 481 * Reverse the first len bits of a code, using straightforward code (a faster 482 * method would use a table) 483 * IN assertion: 1 <= len <= 15 484 */ 485 static unsigned bi_reverse(unsigned code, int len) 486 { 487 register unsigned res = 0; 488 489 do { 490 res |= code & 1; 491 code >>= 1, res <<= 1; 492 } while (--len > 0); 493 return res >> 1; 494 } 495 496 /* =========================================================================== 497 * Write out any remaining bits in an incomplete byte. 498 */ 499 static void bi_windup(void) 500 { 501 if (bi_valid > 8) { 502 put_short(bi_buf); 503 } else if (bi_valid > 0) { 504 put_byte(bi_buf); 505 } 506 bi_buf = 0; 507 bi_valid = 0; 508 #ifdef DEBUG 509 bits_sent = (bits_sent + 7) & ~7; 510 #endif 511 } 512 513 /* =========================================================================== 514 * Copy a stored block to the zip file, storing first the length and its 515 * one's complement if requested. 516 */ 517 static void copy_block(char *buf, unsigned len, int header) 518 { 519 bi_windup(); /* align on byte boundary */ 520 521 if (header) { 522 put_short((ush) len); 523 put_short((ush) ~ len); 524 #ifdef DEBUG 525 bits_sent += 2 * 16; 526 #endif 527 } 528 #ifdef DEBUG 529 bits_sent += (ulg) len << 3; 530 #endif 531 while (len--) { 532 put_byte(*buf++); 533 } 534 } 535 536 /* deflate.c -- compress data using the deflation algorithm 537 * Copyright (C) 1992-1993 Jean-loup Gailly 538 * This is free software; you can redistribute it and/or modify it under the 539 * terms of the GNU General Public License, see the file COPYING. 540 */ 541 542 /* 543 * PURPOSE 544 * 545 * Identify new text as repetitions of old text within a fixed- 546 * length sliding window trailing behind the new text. 547 * 548 * DISCUSSION 549 * 550 * The "deflation" process depends on being able to identify portions 551 * of the input text which are identical to earlier input (within a 552 * sliding window trailing behind the input currently being processed). 553 * 554 * The most straightforward technique turns out to be the fastest for 555 * most input files: try all possible matches and select the longest. 556 * The key feature of this algorithm is that insertions into the string 557 * dictionary are very simple and thus fast, and deletions are avoided 558 * completely. Insertions are performed at each input character, whereas 559 * string matches are performed only when the previous match ends. So it 560 * is preferable to spend more time in matches to allow very fast string 561 * insertions and avoid deletions. The matching algorithm for small 562 * strings is inspired from that of Rabin & Karp. A brute force approach 563 * is used to find longer strings when a small match has been found. 564 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 565 * (by Leonid Broukhis). 566 * A previous version of this file used a more sophisticated algorithm 567 * (by Fiala and Greene) which is guaranteed to run in linear amortized 568 * time, but has a larger average cost, uses more memory and is patented. 569 * However the F&G algorithm may be faster for some highly redundant 570 * files if the parameter max_chain_length (described below) is too large. 571 * 572 * ACKNOWLEDGMENTS 573 * 574 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 575 * I found it in 'freeze' written by Leonid Broukhis. 576 * Thanks to many info-zippers for bug reports and testing. 577 * 578 * REFERENCES 579 * 580 * APPNOTE.TXT documentation file in PKZIP 1.93a distribution. 581 * 582 * A description of the Rabin and Karp algorithm is given in the book 583 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 584 * 585 * Fiala,E.R., and Greene,D.H. 586 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 587 * 588 * INTERFACE 589 * 590 * void lm_init (int pack_level, ush *flags) 591 * Initialize the "longest match" routines for a new file 592 * 593 * ulg deflate (void) 594 * Processes a new input file and return its compressed length. Sets 595 * the compressed length, crc, deflate flags and internal file 596 * attributes. 597 */ 598 599 600 /* =========================================================================== 601 * Configuration parameters 602 */ 603 604 /* Compile with MEDIUM_MEM to reduce the memory requirements or 153 154 /* =========================================================================== 155 * Compile with MEDIUM_MEM to reduce the memory requirements or 605 156 * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the 606 157 * entire input file can be held in memory (not possible on 16 bit systems). … … 621 172 #endif 622 173 623 /* To save space (see unlzw.c), we overlay prev+head with tab_prefix and624 * window with tab_suffix. Check that we can do this:625 */626 #if (WSIZE<<1) > (1<<BITS)627 # error cannot overlay window with tab_suffix and prev with tab_prefix0628 #endif629 #if HASH_BITS > BITS-1630 # error cannot overlay head with tab_prefix1631 #endif632 174 #define HASH_SIZE (unsigned)(1<<HASH_BITS) 633 175 #define HASH_MASK (HASH_SIZE-1) 634 176 #define WMASK (WSIZE-1) 635 177 /* HASH_SIZE and WSIZE must be powers of two */ 636 #define NIL 0637 /* Tail of hash chains */638 #define FAST 4639 #define SLOW 2640 /* speed options for the general purpose bit flag */641 178 #ifndef TOO_FAR 642 179 # define TOO_FAR 4096 643 180 #endif 644 181 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 645 /* =========================================================================== 646 * Local data used by the "longest match" routines. 647 */ 182 183 184 /* =========================================================================== 185 * These types are not really 'char', 'short' and 'long' 186 */ 187 typedef uint8_t uch; 188 typedef uint16_t ush; 189 typedef uint32_t ulg; 190 typedef int32_t lng; 191 648 192 typedef ush Pos; 649 193 typedef unsigned IPos; 650 651 194 /* A Pos is an index in the character window. We use short instead of int to 652 195 * save space in the various tables. IPos is used only for parameter passing. 653 196 */ 654 197 655 /* DECLARE(uch, window, 2L*WSIZE); */ 198 enum { 199 WINDOW_SIZE = 2 * WSIZE, 200 /* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the 201 * input file length plus MIN_LOOKAHEAD. 202 */ 203 204 max_chain_length = 4096, 205 /* To speed up deflation, hash chains are never searched beyond this length. 206 * A higher limit improves compression ratio but degrades the speed. 207 */ 208 209 max_lazy_match = 258, 210 /* Attempt to find a better match only when the current match is strictly 211 * smaller than this value. This mechanism is used only for compression 212 * levels >= 4. 213 */ 214 215 max_insert_length = max_lazy_match, 216 /* Insert new strings in the hash table only if the match length 217 * is not greater than this length. This saves time but degrades compression. 218 * max_insert_length is used only for compression levels <= 3. 219 */ 220 221 good_match = 32, 222 /* Use a faster search when the previous match is longer than this */ 223 224 /* Values for max_lazy_match, good_match and max_chain_length, depending on 225 * the desired pack level (0..9). The values given below have been tuned to 226 * exclude worst case performance for pathological files. Better values may be 227 * found for specific files. 228 */ 229 230 nice_match = 258, /* Stop searching when current match exceeds this */ 231 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 232 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 233 * meaning. 234 */ 235 }; 236 237 238 struct globals { 239 240 lng block_start; 241 242 /* window position at the beginning of the current output block. Gets 243 * negative when the window is moved backwards. 244 */ 245 unsigned ins_h; /* hash index of string to be inserted */ 246 247 #define H_SHIFT ((HASH_BITS+MIN_MATCH-1) / MIN_MATCH) 248 /* Number of bits by which ins_h and del_h must be shifted at each 249 * input step. It must be such that after MIN_MATCH steps, the oldest 250 * byte no longer takes part in the hash key, that is: 251 * H_SHIFT * MIN_MATCH >= HASH_BITS 252 */ 253 254 unsigned prev_length; 255 256 /* Length of the best match at previous step. Matches not greater than this 257 * are discarded. This is used in the lazy match evaluation. 258 */ 259 260 unsigned strstart; /* start of string to insert */ 261 unsigned match_start; /* start of matching string */ 262 unsigned lookahead; /* number of valid bytes ahead in window */ 263 264 /* =========================================================================== 265 */ 266 #define DECLARE(type, array, size) \ 267 type * array 268 #define ALLOC(type, array, size) \ 269 array = xzalloc((size_t)(((size)+1L)/2) * 2*sizeof(type)); 270 #define FREE(array) \ 271 do { free(array); array = NULL; } while (0) 272 273 /* global buffers */ 274 275 /* buffer for literals or lengths */ 276 /* DECLARE(uch, l_buf, LIT_BUFSIZE); */ 277 DECLARE(uch, l_buf, INBUFSIZ); 278 279 DECLARE(ush, d_buf, DIST_BUFSIZE); 280 DECLARE(uch, outbuf, OUTBUFSIZ); 281 656 282 /* Sliding window. Input bytes are read into the second half of the window, 657 283 * and move to the first half later to keep a dictionary of at least WSIZE … … 663 289 * be less efficient). 664 290 */ 665 666 /* DECLARE(Pos, prev, WSIZE); */ 291 DECLARE(uch, window, 2L * WSIZE); 292 667 293 /* Link to older string with same hash index. To limit the size of this 668 294 * array to 64K, this link is maintained only for the last 32K strings. 669 295 * An index in this array is thus a window index modulo 32K. 670 296 */ 671 672 /* DECLARE(Pos, head, 1<<HASH_BITS); */ 673 /* Heads of the hash chains or NIL. */ 674 675 static const ulg window_size = (ulg) 2 * WSIZE; 676 677 /* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the 678 * input file length plus MIN_LOOKAHEAD. 679 */ 680 681 static long block_start; 682 683 /* window position at the beginning of the current output block. Gets 684 * negative when the window is moved backwards. 685 */ 686 687 static unsigned ins_h; /* hash index of string to be inserted */ 688 689 #define H_SHIFT ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH) 690 /* Number of bits by which ins_h and del_h must be shifted at each 691 * input step. It must be such that after MIN_MATCH steps, the oldest 692 * byte no longer takes part in the hash key, that is: 693 * H_SHIFT * MIN_MATCH >= HASH_BITS 694 */ 695 696 static unsigned int prev_length; 697 698 /* Length of the best match at previous step. Matches not greater than this 699 * are discarded. This is used in the lazy match evaluation. 700 */ 701 702 static unsigned strstart; /* start of string to insert */ 703 static unsigned match_start; /* start of matching string */ 704 static int eofile; /* flag set at end of input file */ 705 static unsigned lookahead; /* number of valid bytes ahead in window */ 706 707 enum { 708 max_chain_length = 4096, 709 710 /* To speed up deflation, hash chains are never searched beyond this length. 711 * A higher limit improves compression ratio but degrades the speed. 712 */ 713 714 max_lazy_match = 258, 715 716 /* Attempt to find a better match only when the current match is strictly 717 * smaller than this value. This mechanism is used only for compression 718 * levels >= 4. 719 */ 720 max_insert_length = max_lazy_match, 721 /* Insert new strings in the hash table only if the match length 722 * is not greater than this length. This saves time but degrades compression. 723 * max_insert_length is used only for compression levels <= 3. 724 */ 725 726 good_match = 32, 727 728 /* Use a faster search when the previous match is longer than this */ 729 730 731 /* Values for max_lazy_match, good_match and max_chain_length, depending on 732 * the desired pack level (0..9). The values given below have been tuned to 733 * exclude worst case performance for pathological files. Better values may be 734 * found for specific files. 735 */ 736 737 nice_match = 258 /* Stop searching when current match exceeds this */ 738 739 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 740 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 741 * meaning. 742 */ 297 /* DECLARE(Pos, prev, WSIZE); */ 298 DECLARE(ush, prev, 1L << BITS); 299 300 /* Heads of the hash chains or 0. */ 301 /* DECLARE(Pos, head, 1<<HASH_BITS); */ 302 #define head (G1.prev + WSIZE) /* hash head (see deflate.c) */ 303 304 /* number of input bytes */ 305 ulg isize; /* only 32 bits stored in .gz file */ 306 307 /* bbox always use stdin/stdout */ 308 #define ifd STDIN_FILENO /* input file descriptor */ 309 #define ofd STDOUT_FILENO /* output file descriptor */ 310 311 #ifdef DEBUG 312 unsigned insize; /* valid bytes in l_buf */ 313 #endif 314 unsigned outcnt; /* bytes in output buffer */ 315 316 smallint eofile; /* flag set at end of input file */ 317 318 /* =========================================================================== 319 * Local data used by the "bit string" routines. 320 */ 321 322 unsigned short bi_buf; 323 324 /* Output buffer. bits are inserted starting at the bottom (least significant 325 * bits). 326 */ 327 328 #undef BUF_SIZE 329 #define BUF_SIZE (8 * sizeof(G1.bi_buf)) 330 /* Number of bits used within bi_buf. (bi_buf might be implemented on 331 * more than 16 bits on some systems.) 332 */ 333 334 int bi_valid; 335 336 /* Current input function. Set to mem_read for in-memory compression */ 337 338 #ifdef DEBUG 339 ulg bits_sent; /* bit length of the compressed data */ 340 #endif 341 342 uint32_t *crc_32_tab; 343 uint32_t crc; /* shift register contents */ 743 344 }; 744 345 745 #define EQUAL 0 746 /* result of memcmp for equal strings */ 747 748 /* =========================================================================== 749 * Prototypes for local functions. 750 */ 751 static void fill_window(void); 752 753 static int longest_match(IPos cur_match); 754 346 #define G1 (*(ptr_to_globals - 1)) 347 348 349 /* =========================================================================== 350 * Write the output buffer outbuf[0..outcnt-1] and update bytes_out. 351 * (used for the compressed data only) 352 */ 353 static void flush_outbuf(void) 354 { 355 if (G1.outcnt == 0) 356 return; 357 358 xwrite(ofd, (char *) G1.outbuf, G1.outcnt); 359 G1.outcnt = 0; 360 } 361 362 363 /* =========================================================================== 364 */ 365 /* put_8bit is used for the compressed output */ 366 #define put_8bit(c) \ 367 do { \ 368 G1.outbuf[G1.outcnt++] = (c); \ 369 if (G1.outcnt == OUTBUFSIZ) flush_outbuf(); \ 370 } while (0) 371 372 /* Output a 16 bit value, lsb first */ 373 static void put_16bit(ush w) 374 { 375 if (G1.outcnt < OUTBUFSIZ - 2) { 376 G1.outbuf[G1.outcnt++] = w; 377 G1.outbuf[G1.outcnt++] = w >> 8; 378 } else { 379 put_8bit(w); 380 put_8bit(w >> 8); 381 } 382 } 383 384 static void put_32bit(ulg n) 385 { 386 put_16bit(n); 387 put_16bit(n >> 16); 388 } 389 390 /* =========================================================================== 391 * Clear input and output buffers 392 */ 393 static void clear_bufs(void) 394 { 395 G1.outcnt = 0; 755 396 #ifdef DEBUG 756 static void check_match(IPos start, IPos match, int length); 757 #endif 758 759 /* =========================================================================== 760 * Update a hash value with the given input byte 761 * IN assertion: all calls to to UPDATE_HASH are made with consecutive 762 * input characters, so that a running hash key can be computed from the 763 * previous key instead of complete recalculation each time. 764 */ 765 #define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK) 766 767 /* =========================================================================== 768 * Insert string s in the dictionary and set match_head to the previous head 769 * of the hash chain (the most recent string with same hash key). Return 770 * the previous length of the hash chain. 771 * IN assertion: all calls to to INSERT_STRING are made with consecutive 772 * input characters and the first MIN_MATCH bytes of s are valid 773 * (except for the last MIN_MATCH-1 bytes of the input file). 774 */ 775 #define INSERT_STRING(s, match_head) \ 776 (UPDATE_HASH(ins_h, window[(s) + MIN_MATCH-1]), \ 777 prev[(s) & WMASK] = match_head = head[ins_h], \ 778 head[ins_h] = (s)) 779 780 /* =========================================================================== 781 * Initialize the "longest match" routines for a new file 782 */ 783 static void lm_init(ush * flags) 784 { 785 register unsigned j; 786 787 /* Initialize the hash table. */ 788 memset(head, 0, HASH_SIZE * sizeof(*head)); 789 /* prev will be initialized on the fly */ 790 791 *flags |= SLOW; 792 /* ??? reduce max_chain_length for binary files */ 793 794 strstart = 0; 795 block_start = 0L; 796 797 lookahead = read_buf((char *) window, 798 sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE); 799 800 if (lookahead == 0 || lookahead == (unsigned) EOF) { 801 eofile = 1, lookahead = 0; 802 return; 803 } 804 eofile = 0; 805 /* Make sure that we always have enough lookahead. This is important 806 * if input comes from a device such as a tty. 807 */ 808 while (lookahead < MIN_LOOKAHEAD && !eofile) 809 fill_window(); 810 811 ins_h = 0; 812 for (j = 0; j < MIN_MATCH - 1; j++) 813 UPDATE_HASH(ins_h, window[j]); 814 /* If lookahead < MIN_MATCH, ins_h is garbage, but this is 815 * not important since only literal bytes will be emitted. 816 */ 817 } 397 G1.insize = 0; 398 #endif 399 G1.isize = 0; 400 } 401 402 403 /* =========================================================================== 404 * Run a set of bytes through the crc shift register. If s is a NULL 405 * pointer, then initialize the crc shift register contents instead. 406 * Return the current crc in either case. 407 */ 408 static uint32_t updcrc(uch * s, unsigned n) 409 { 410 uint32_t c = G1.crc; 411 while (n) { 412 c = G1.crc_32_tab[(uch)(c ^ *s++)] ^ (c >> 8); 413 n--; 414 } 415 G1.crc = c; 416 return c; 417 } 418 419 420 /* =========================================================================== 421 * Read a new buffer from the current input file, perform end-of-line 422 * translation, and update the crc and input file size. 423 * IN assertion: size >= 2 (for end-of-line translation) 424 */ 425 static unsigned file_read(void *buf, unsigned size) 426 { 427 unsigned len; 428 429 Assert(G1.insize == 0, "l_buf not empty"); 430 431 len = safe_read(ifd, buf, size); 432 if (len == (unsigned)(-1) || len == 0) 433 return len; 434 435 updcrc(buf, len); 436 G1.isize += len; 437 return len; 438 } 439 440 441 /* =========================================================================== 442 * Send a value on a given number of bits. 443 * IN assertion: length <= 16 and value fits in length bits. 444 */ 445 static void send_bits(int value, int length) 446 { 447 #ifdef DEBUG 448 Tracev((stderr, " l %2d v %4x ", length, value)); 449 Assert(length > 0 && length <= 15, "invalid length"); 450 G1.bits_sent += length; 451 #endif 452 /* If not enough room in bi_buf, use (valid) bits from bi_buf and 453 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 454 * unused bits in value. 455 */ 456 if (G1.bi_valid > (int) BUF_SIZE - length) { 457 G1.bi_buf |= (value << G1.bi_valid); 458 put_16bit(G1.bi_buf); 459 G1.bi_buf = (ush) value >> (BUF_SIZE - G1.bi_valid); 460 G1.bi_valid += length - BUF_SIZE; 461 } else { 462 G1.bi_buf |= value << G1.bi_valid; 463 G1.bi_valid += length; 464 } 465 } 466 467 468 /* =========================================================================== 469 * Reverse the first len bits of a code, using straightforward code (a faster 470 * method would use a table) 471 * IN assertion: 1 <= len <= 15 472 */ 473 static unsigned bi_reverse(unsigned code, int len) 474 { 475 unsigned res = 0; 476 477 while (1) { 478 res |= code & 1; 479 if (--len <= 0) return res; 480 code >>= 1; 481 res <<= 1; 482 } 483 } 484 485 486 /* =========================================================================== 487 * Write out any remaining bits in an incomplete byte. 488 */ 489 static void bi_windup(void) 490 { 491 if (G1.bi_valid > 8) { 492 put_16bit(G1.bi_buf); 493 } else if (G1.bi_valid > 0) { 494 put_8bit(G1.bi_buf); 495 } 496 G1.bi_buf = 0; 497 G1.bi_valid = 0; 498 #ifdef DEBUG 499 G1.bits_sent = (G1.bits_sent + 7) & ~7; 500 #endif 501 } 502 503 504 /* =========================================================================== 505 * Copy a stored block to the zip file, storing first the length and its 506 * one's complement if requested. 507 */ 508 static void copy_block(char *buf, unsigned len, int header) 509 { 510 bi_windup(); /* align on byte boundary */ 511 512 if (header) { 513 put_16bit(len); 514 put_16bit(~len); 515 #ifdef DEBUG 516 G1.bits_sent += 2 * 16; 517 #endif 518 } 519 #ifdef DEBUG 520 G1.bits_sent += (ulg) len << 3; 521 #endif 522 while (len--) { 523 put_8bit(*buf++); 524 } 525 } 526 527 528 /* =========================================================================== 529 * Fill the window when the lookahead becomes insufficient. 530 * Updates strstart and lookahead, and sets eofile if end of input file. 531 * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0 532 * OUT assertions: at least one byte has been read, or eofile is set; 533 * file reads are performed for at least two bytes (required for the 534 * translate_eol option). 535 */ 536 static void fill_window(void) 537 { 538 unsigned n, m; 539 unsigned more = WINDOW_SIZE - G1.lookahead - G1.strstart; 540 /* Amount of free space at the end of the window. */ 541 542 /* If the window is almost full and there is insufficient lookahead, 543 * move the upper half to the lower one to make room in the upper half. 544 */ 545 if (more == (unsigned) -1) { 546 /* Very unlikely, but possible on 16 bit machine if strstart == 0 547 * and lookahead == 1 (input done one byte at time) 548 */ 549 more--; 550 } else if (G1.strstart >= WSIZE + MAX_DIST) { 551 /* By the IN assertion, the window is not empty so we can't confuse 552 * more == 0 with more == 64K on a 16 bit machine. 553 */ 554 Assert(WINDOW_SIZE == 2 * WSIZE, "no sliding with BIG_MEM"); 555 556 memcpy(G1.window, G1.window + WSIZE, WSIZE); 557 G1.match_start -= WSIZE; 558 G1.strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */ 559 560 G1.block_start -= WSIZE; 561 562 for (n = 0; n < HASH_SIZE; n++) { 563 m = head[n]; 564 head[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0); 565 } 566 for (n = 0; n < WSIZE; n++) { 567 m = G1.prev[n]; 568 G1.prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0); 569 /* If n is not on any hash chain, prev[n] is garbage but 570 * its value will never be used. 571 */ 572 } 573 more += WSIZE; 574 } 575 /* At this point, more >= 2 */ 576 if (!G1.eofile) { 577 n = file_read(G1.window + G1.strstart + G1.lookahead, more); 578 if (n == 0 || n == (unsigned) -1) { 579 G1.eofile = 1; 580 } else { 581 G1.lookahead += n; 582 } 583 } 584 } 585 818 586 819 587 /* =========================================================================== … … 833 601 { 834 602 unsigned chain_length = max_chain_length; /* max hash chain length */ 835 register uch *scan = window + strstart; /* current string */ 836 register uch *match; /* matched string */ 837 register int len; /* length of current match */ 838 int best_len = prev_length; /* best match length so far */ 839 IPos limit = 840 strstart > (IPos) MAX_DIST ? strstart - (IPos) MAX_DIST : NIL; 603 uch *scan = G1.window + G1.strstart; /* current string */ 604 uch *match; /* matched string */ 605 int len; /* length of current match */ 606 int best_len = G1.prev_length; /* best match length so far */ 607 IPos limit = G1.strstart > (IPos) MAX_DIST ? G1.strstart - (IPos) MAX_DIST : 0; 841 608 /* Stop when cur_match becomes <= limit. To simplify the code, 842 609 * we prevent matches with the string of window index 0. … … 849 616 # error Code too clever 850 617 #endif 851 register uch *strend = window +strstart + MAX_MATCH;852 registeruch scan_end1 = scan[best_len - 1];853 registeruch scan_end = scan[best_len];618 uch *strend = G1.window + G1.strstart + MAX_MATCH; 619 uch scan_end1 = scan[best_len - 1]; 620 uch scan_end = scan[best_len]; 854 621 855 622 /* Do not waste too much time if we already have a good match: */ 856 if ( prev_length >= good_match) {623 if (G1.prev_length >= good_match) { 857 624 chain_length >>= 2; 858 625 } 859 Assert( strstart <= window_size- MIN_LOOKAHEAD, "insufficient lookahead");626 Assert(G1.strstart <= WINDOW_SIZE - MIN_LOOKAHEAD, "insufficient lookahead"); 860 627 861 628 do { 862 Assert(cur_match < strstart, "no future");863 match = window + cur_match;629 Assert(cur_match < G1.strstart, "no future"); 630 match = G1.window + cur_match; 864 631 865 632 /* Skip to next match if the match length cannot increase … … 892 659 893 660 if (len > best_len) { 894 match_start = cur_match;661 G1.match_start = cur_match; 895 662 best_len = len; 896 663 if (len >= nice_match) … … 899 666 scan_end = scan[best_len]; 900 667 } 901 } while ((cur_match = prev[cur_match & WMASK]) > limit668 } while ((cur_match = G1.prev[cur_match & WMASK]) > limit 902 669 && --chain_length != 0); 903 670 … … 905 672 } 906 673 674 907 675 #ifdef DEBUG 908 676 /* =========================================================================== … … 912 680 { 913 681 /* check that the match is indeed a match */ 914 if (memcmp((char *) window + match, 915 (char *) window + start, length) != EQUAL) { 682 if (memcmp(G1.window + match, G1.window + start, length) != 0) { 916 683 bb_error_msg(" start %d, match %d, length %d", start, match, length); 917 684 bb_error_msg("invalid match"); … … 920 687 bb_error_msg("\\[%d,%d]", start - match, length); 921 688 do { 922 putc( window[start++], stderr);689 putc(G1.window[start++], stderr); 923 690 } while (--length != 0); 924 691 } 925 692 } 926 693 #else 927 # define check_match(start, match, length) 928 #endif 929 930 /* =========================================================================== 931 * Fill the window when the lookahead becomes insufficient. 932 * Updates strstart and lookahead, and sets eofile if end of input file. 933 * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0 934 * OUT assertions: at least one byte has been read, or eofile is set; 935 * file reads are performed for at least two bytes (required for the 936 * translate_eol option). 937 */ 938 static void fill_window(void) 939 { 940 register unsigned n, m; 941 unsigned more = 942 (unsigned) (window_size - (ulg) lookahead - (ulg) strstart); 943 /* Amount of free space at the end of the window. */ 944 945 /* If the window is almost full and there is insufficient lookahead, 946 * move the upper half to the lower one to make room in the upper half. 947 */ 948 if (more == (unsigned) EOF) { 949 /* Very unlikely, but possible on 16 bit machine if strstart == 0 950 * and lookahead == 1 (input done one byte at time) 951 */ 952 more--; 953 } else if (strstart >= WSIZE + MAX_DIST) { 954 /* By the IN assertion, the window is not empty so we can't confuse 955 * more == 0 with more == 64K on a 16 bit machine. 956 */ 957 Assert(window_size == (ulg) 2 * WSIZE, "no sliding with BIG_MEM"); 958 959 memcpy((char *) window, (char *) window + WSIZE, (unsigned) WSIZE); 960 match_start -= WSIZE; 961 strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */ 962 963 block_start -= (long) WSIZE; 964 965 for (n = 0; n < HASH_SIZE; n++) { 966 m = head[n]; 967 head[n] = (Pos) (m >= WSIZE ? m - WSIZE : NIL); 968 } 969 for (n = 0; n < WSIZE; n++) { 970 m = prev[n]; 971 prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : NIL); 972 /* If n is not on any hash chain, prev[n] is garbage but 973 * its value will never be used. 974 */ 975 } 976 more += WSIZE; 977 } 978 /* At this point, more >= 2 */ 979 if (!eofile) { 980 n = read_buf((char *) window + strstart + lookahead, more); 981 if (n == 0 || n == (unsigned) EOF) { 982 eofile = 1; 983 } else { 984 lookahead += n; 985 } 986 } 987 } 988 989 /* =========================================================================== 990 * Flush the current block, with given end-of-file flag. 991 * IN assertion: strstart is set to the end of the current match. 992 */ 993 #define FLUSH_BLOCK(eof) \ 994 flush_block(block_start >= 0L ? (char*)&window[(unsigned)block_start] : \ 995 (char*)NULL, (long)strstart - block_start, (eof)) 996 997 /* =========================================================================== 998 * Same as above, but achieves better compression. We use a lazy 999 * evaluation for matches: a match is finally adopted only if there is 1000 * no better match at the next window position. 1001 */ 1002 static ulg deflate(void) 1003 { 1004 IPos hash_head; /* head of hash chain */ 1005 IPos prev_match; /* previous match */ 1006 int flush; /* set if current block must be flushed */ 1007 int match_available = 0; /* set if previous match exists */ 1008 register unsigned match_length = MIN_MATCH - 1; /* length of best match */ 1009 1010 /* Process the input block. */ 1011 while (lookahead != 0) { 1012 /* Insert the string window[strstart .. strstart+2] in the 1013 * dictionary, and set hash_head to the head of the hash chain: 1014 */ 1015 INSERT_STRING(strstart, hash_head); 1016 1017 /* Find the longest match, discarding those <= prev_length. 1018 */ 1019 prev_length = match_length, prev_match = match_start; 1020 match_length = MIN_MATCH - 1; 1021 1022 if (hash_head != NIL && prev_length < max_lazy_match && 1023 strstart - hash_head <= MAX_DIST) { 1024 /* To simplify the code, we prevent matches with the string 1025 * of window index 0 (in particular we have to avoid a match 1026 * of the string with itself at the start of the input file). 1027 */ 1028 match_length = longest_match(hash_head); 1029 /* longest_match() sets match_start */ 1030 if (match_length > lookahead) 1031 match_length = lookahead; 1032 1033 /* Ignore a length 3 match if it is too distant: */ 1034 if (match_length == MIN_MATCH && strstart - match_start > TOO_FAR) { 1035 /* If prev_match is also MIN_MATCH, match_start is garbage 1036 * but we will ignore the current match anyway. 1037 */ 1038 match_length--; 1039 } 1040 } 1041 /* If there was a match at the previous step and the current 1042 * match is not better, output the previous match: 1043 */ 1044 if (prev_length >= MIN_MATCH && match_length <= prev_length) { 1045 1046 check_match(strstart - 1, prev_match, prev_length); 1047 1048 flush = 1049 ct_tally(strstart - 1 - prev_match, prev_length - MIN_MATCH); 1050 1051 /* Insert in hash table all strings up to the end of the match. 1052 * strstart-1 and strstart are already inserted. 1053 */ 1054 lookahead -= prev_length - 1; 1055 prev_length -= 2; 1056 do { 1057 strstart++; 1058 INSERT_STRING(strstart, hash_head); 1059 /* strstart never exceeds WSIZE-MAX_MATCH, so there are 1060 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH 1061 * these bytes are garbage, but it does not matter since the 1062 * next lookahead bytes will always be emitted as literals. 1063 */ 1064 } while (--prev_length != 0); 1065 match_available = 0; 1066 match_length = MIN_MATCH - 1; 1067 strstart++; 1068 if (flush) 1069 FLUSH_BLOCK(0), block_start = strstart; 1070 1071 } else if (match_available) { 1072 /* If there was no match at the previous position, output a 1073 * single literal. If there was a match but the current match 1074 * is longer, truncate the previous match to a single literal. 1075 */ 1076 Tracevv((stderr, "%c", window[strstart - 1])); 1077 if (ct_tally(0, window[strstart - 1])) { 1078 FLUSH_BLOCK(0), block_start = strstart; 1079 } 1080 strstart++; 1081 lookahead--; 1082 } else { 1083 /* There is no previous match to compare with, wait for 1084 * the next step to decide. 1085 */ 1086 match_available = 1; 1087 strstart++; 1088 lookahead--; 1089 } 1090 Assert(strstart <= isize && lookahead <= isize, "a bit too far"); 1091 1092 /* Make sure that we always have enough lookahead, except 1093 * at the end of the input file. We need MAX_MATCH bytes 1094 * for the next match, plus MIN_MATCH bytes to insert the 1095 * string following the next match. 1096 */ 1097 while (lookahead < MIN_LOOKAHEAD && !eofile) 1098 fill_window(); 1099 } 1100 if (match_available) 1101 ct_tally(0, window[strstart - 1]); 1102 1103 return FLUSH_BLOCK(1); /* eof */ 1104 } 1105 1106 /* gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface 1107 * Copyright (C) 1992-1993 Jean-loup Gailly 1108 * The unzip code was written and put in the public domain by Mark Adler. 1109 * Portions of the lzw code are derived from the public domain 'compress' 1110 * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies, 1111 * Ken Turkowski, Dave Mack and Peter Jannesen. 1112 * 1113 * See the license_msg below and the file COPYING for the software license. 1114 * See the file algorithm.doc for the compression algorithms and file formats. 1115 */ 1116 1117 /* Compress files with zip algorithm and 'compress' interface. 1118 * See usage() and help() functions below for all options. 1119 * Outputs: 1120 * file.gz: compressed file with same mode, owner, and utimes 1121 * or stdout with -c option or if stdin used as input. 1122 * If the output file name had to be truncated, the original name is kept 1123 * in the compressed file. 1124 */ 1125 1126 /* configuration */ 1127 1128 typedef struct dirent dir_type; 1129 1130 /* ======================================================================== */ 1131 int gzip_main(int argc, char **argv) 1132 { 1133 int result; 1134 int inFileNum; 1135 int outFileNum; 1136 struct stat statBuf; 1137 char *delFileName; 1138 int tostdout = 0; 1139 int force = 0; 1140 int opt; 1141 1142 while ((opt = getopt(argc, argv, "cf123456789dq")) != -1) { 1143 switch (opt) { 1144 case 'c': 1145 tostdout = 1; 1146 break; 1147 case 'f': 1148 force = 1; 1149 break; 1150 /* Ignore 1-9 (compression level) options */ 1151 case '1': 1152 case '2': 1153 case '3': 1154 case '4': 1155 case '5': 1156 case '6': 1157 case '7': 1158 case '8': 1159 case '9': 1160 break; 1161 case 'q': 1162 break; 1163 #ifdef CONFIG_GUNZIP 1164 case 'd': 1165 optind = 1; 1166 return gunzip_main(argc, argv); 1167 #endif 1168 default: 1169 bb_show_usage(); 1170 } 1171 } 1172 1173 foreground = signal(SIGINT, SIG_IGN) != SIG_IGN; 1174 if (foreground) { 1175 (void) signal(SIGINT, abort_gzip); 1176 } 1177 #ifdef SIGTERM 1178 if (signal(SIGTERM, SIG_IGN) != SIG_IGN) { 1179 (void) signal(SIGTERM, abort_gzip); 1180 } 1181 #endif 1182 #ifdef SIGHUP 1183 if (signal(SIGHUP, SIG_IGN) != SIG_IGN) { 1184 (void) signal(SIGHUP, abort_gzip); 1185 } 1186 #endif 1187 1188 strncpy(z_suffix, Z_SUFFIX, sizeof(z_suffix) - 1); 1189 z_len = strlen(z_suffix); 1190 1191 /* Allocate all global buffers (for DYN_ALLOC option) */ 1192 ALLOC(uch, inbuf, INBUFSIZ + INBUF_EXTRA); 1193 ALLOC(uch, outbuf, OUTBUFSIZ + OUTBUF_EXTRA); 1194 ALLOC(ush, d_buf, DIST_BUFSIZE); 1195 ALLOC(uch, window, 2L * WSIZE); 1196 ALLOC(ush, tab_prefix, 1L << BITS); 1197 1198 /* Initialise the CRC32 table */ 1199 crc_32_tab = bb_crc32_filltable(0); 1200 1201 clear_bufs(); 1202 part_nb = 0; 1203 1204 if (optind == argc) { 1205 time_stamp = 0; 1206 ifile_size = -1L; 1207 zip(STDIN_FILENO, STDOUT_FILENO); 1208 } else { 1209 int i; 1210 1211 for (i = optind; i < argc; i++) { 1212 char *path = NULL; 1213 1214 clear_bufs(); 1215 if (strcmp(argv[i], "-") == 0) { 1216 time_stamp = 0; 1217 ifile_size = -1L; 1218 inFileNum = STDIN_FILENO; 1219 outFileNum = STDOUT_FILENO; 1220 } else { 1221 inFileNum = bb_xopen3(argv[i], O_RDONLY, 0); 1222 if (fstat(inFileNum, &statBuf) < 0) 1223 bb_perror_msg_and_die("%s", argv[i]); 1224 time_stamp = statBuf.st_ctime; 1225 ifile_size = statBuf.st_size; 1226 1227 if (!tostdout) { 1228 path = xmalloc(strlen(argv[i]) + 4); 1229 strcpy(path, argv[i]); 1230 strcat(path, ".gz"); 1231 1232 /* Open output file */ 1233 #if (__GLIBC__ >= 2) && (__GLIBC_MINOR__ >= 1) && defined O_NOFOLLOW 1234 outFileNum = 1235 open(path, O_RDWR | O_CREAT | O_EXCL | O_NOFOLLOW); 1236 #else 1237 outFileNum = open(path, O_RDWR | O_CREAT | O_EXCL); 1238 #endif 1239 if (outFileNum < 0) { 1240 bb_perror_msg("%s", path); 1241 free(path); 1242 continue; 1243 } 1244 1245 /* Set permissions on the file */ 1246 fchmod(outFileNum, statBuf.st_mode); 1247 } else 1248 outFileNum = STDOUT_FILENO; 1249 } 1250 1251 if (path == NULL && isatty(outFileNum) && force == 0) { 1252 bb_error_msg 1253 ("compressed data not written to a terminal. Use -f to force compression."); 1254 free(path); 1255 continue; 1256 } 1257 1258 result = zip(inFileNum, outFileNum); 1259 1260 if (path != NULL) { 1261 close(inFileNum); 1262 close(outFileNum); 1263 1264 /* Delete the original file */ 1265 if (result == OK) 1266 delFileName = argv[i]; 1267 else 1268 delFileName = path; 1269 1270 if (unlink(delFileName) < 0) 1271 bb_perror_msg("%s", delFileName); 1272 } 1273 1274 free(path); 1275 } 1276 } 1277 1278 return (exit_code); 1279 } 694 # define check_match(start, match, length) ((void)0) 695 #endif 696 1280 697 1281 698 /* trees.c -- output deflated data using Huffman coding … … 1285 702 */ 1286 703 1287 /* 1288 * PURPOSE 1289 * 704 /* PURPOSE 1290 705 * Encode various sets of source values using variable-length 1291 706 * binary code trees. 1292 707 * 1293 708 * DISCUSSION 1294 *1295 709 * The PKZIP "deflation" process uses several Huffman trees. The more 1296 710 * common source values are represented by shorter bit sequences. … … 1304 718 * 1305 719 * REFERENCES 1306 *1307 720 * Lynch, Thomas J. 1308 721 * Data Compression: Techniques and Applications, pp. 53-55. … … 1318 731 * 1319 732 * INTERFACE 733 * void ct_init() 734 * Allocate the match buffer, initialize the various tables [and save 735 * the location of the internal file attribute (ascii/binary) and 736 * method (DEFLATE/STORE) -- deleted in bbox] 1320 737 * 1321 * void ct_init (ush *attr, int *methodp) 1322 * Allocate the match buffer, initialize the various tables and save 1323 * the location of the internal file attribute (ascii/binary) and 1324 * method (DEFLATE/STORE) 1325 * 1326 * void ct_tally (int dist, int lc); 738 * void ct_tally(int dist, int lc); 1327 739 * Save the match info and tally the frequency counts. 1328 740 * 1329 * long flush_block(char *buf, ulg stored_len, int eof)741 * ulg flush_block(char *buf, ulg stored_len, int eof) 1330 742 * Determine the best encoding for the current block: dynamic trees, 1331 743 * static trees or store, and output the encoded block to the zip 1332 744 * file. Returns the total compressed length for the file so far. 1333 *1334 */1335 1336 /* ===========================================================================1337 * Constants1338 745 */ 1339 746 … … 1362 769 /* number of codes used to transfer the bit lengths */ 1363 770 1364 typedef uch extra_bits_t;1365 1366 771 /* extra bits for each length code */ 1367 static const extra_bits_t extra_lbits[LENGTH_CODES]1368 = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4,772 static const uint8_t extra_lbits[LENGTH_CODES] ALIGN1 = { 773 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 1369 774 4, 4, 5, 5, 5, 5, 0 1370 775 }; 1371 776 1372 777 /* extra bits for each distance code */ 1373 static const extra_bits_t extra_dbits[D_CODES]1374 = {0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9,778 static const uint8_t extra_dbits[D_CODES] ALIGN1 = { 779 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 1375 780 10, 10, 11, 11, 12, 12, 13, 13 1376 781 }; 1377 782 1378 783 /* extra bits for each bit length code */ 1379 static const extra_bits_t extra_blbits[BL_CODES] 1380 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 }; 784 static const uint8_t extra_blbits[BL_CODES] ALIGN1 = { 785 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 }; 786 787 /* number of codes at each bit length for an optimal tree */ 788 static const uint8_t bl_order[BL_CODES] ALIGN1 = { 789 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; 1381 790 1382 791 #define STORED_BLOCK 0 … … 1419 828 * if we rely on DIST_BUFSIZE == LIT_BUFSIZE. 1420 829 */ 1421 #if LIT_BUFSIZE > INBUFSIZ1422 #error cannot overlay l_buf and inbuf1423 #endif1424 830 #define REP_3_6 16 1425 831 /* repeat previous bit length 3-6 times (2 bits of repeat count) */ … … 1430 836 1431 837 /* =========================================================================== 1432 * Local data 1433 */ 1434 838 */ 1435 839 /* Data structure describing a single value and its code string. */ 1436 840 typedef struct ct_data { … … 1450 854 #define Len dl.len 1451 855 1452 #define HEAP_SIZE (2*L_CODES +1)856 #define HEAP_SIZE (2*L_CODES + 1) 1453 857 /* maximum heap size */ 1454 1455 static ct_data dyn_ltree[HEAP_SIZE]; /* literal and length tree */1456 static ct_data dyn_dtree[2 * D_CODES + 1]; /* distance tree */1457 1458 static ct_data static_ltree[L_CODES + 2];1459 1460 /* The static literal tree. Since the bit lengths are imposed, there is no1461 * need for the L_CODES extra codes used during heap construction. However1462 * The codes 286 and 287 are needed to build a canonical tree (see ct_init1463 * below).1464 */1465 1466 static ct_data static_dtree[D_CODES];1467 1468 /* The static distance tree. (Actually a trivial tree since all codes use1469 * 5 bits.)1470 */1471 1472 static ct_data bl_tree[2 * BL_CODES + 1];1473 1474 /* Huffman tree for the bit lengths */1475 858 1476 859 typedef struct tree_desc { 1477 860 ct_data *dyn_tree; /* the dynamic tree */ 1478 861 ct_data *static_tree; /* corresponding static tree or NULL */ 1479 const extra_bits_t *extra_bits; /* extra bits for each code or NULL */862 const uint8_t *extra_bits; /* extra bits for each code or NULL */ 1480 863 int extra_base; /* base index for extra_bits */ 1481 864 int elems; /* max number of elements in the tree */ … … 1484 867 } tree_desc; 1485 868 1486 static tree_desc l_desc = 1487 { dyn_ltree, static_ltree, extra_lbits, LITERALS + 1, L_CODES, 1488 MAX_BITS, 0 1489 }; 1490 1491 static tree_desc d_desc = 1492 { dyn_dtree, static_dtree, extra_dbits, 0, D_CODES, MAX_BITS, 0 }; 1493 1494 static tree_desc bl_desc = 1495 { bl_tree, (ct_data *) 0, extra_blbits, 0, BL_CODES, MAX_BL_BITS, 1496 0 1497 }; 1498 1499 1500 static ush bl_count[MAX_BITS + 1]; 1501 1502 /* number of codes at each bit length for an optimal tree */ 1503 1504 static const uch bl_order[BL_CODES] 1505 = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; 869 struct globals2 { 870 871 ush heap[HEAP_SIZE]; /* heap used to build the Huffman trees */ 872 int heap_len; /* number of elements in the heap */ 873 int heap_max; /* element of largest frequency */ 874 875 /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 876 * The same heap array is used to build all trees. 877 */ 878 879 ct_data dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 880 ct_data dyn_dtree[2 * D_CODES + 1]; /* distance tree */ 881 882 ct_data static_ltree[L_CODES + 2]; 883 884 /* The static literal tree. Since the bit lengths are imposed, there is no 885 * need for the L_CODES extra codes used during heap construction. However 886 * The codes 286 and 287 are needed to build a canonical tree (see ct_init 887 * below). 888 */ 889 890 ct_data static_dtree[D_CODES]; 891 892 /* The static distance tree. (Actually a trivial tree since all codes use 893 * 5 bits.) 894 */ 895 896 ct_data bl_tree[2 * BL_CODES + 1]; 897 898 /* Huffman tree for the bit lengths */ 899 900 tree_desc l_desc; 901 tree_desc d_desc; 902 tree_desc bl_desc; 903 904 ush bl_count[MAX_BITS + 1]; 1506 905 1507 906 /* The lengths of the bit length codes are sent in order of decreasing … … 1509 908 */ 1510 909 1511 static int heap[2 * L_CODES + 1]; /* heap used to build the Huffman trees */ 1512 static int heap_len; /* number of elements in the heap */ 1513 static int heap_max; /* element of largest frequency */ 1514 1515 /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 1516 * The same heap array is used to build all trees. 1517 */ 1518 1519 static uch depth[2 * L_CODES + 1]; 910 uch depth[2 * L_CODES + 1]; 1520 911 1521 912 /* Depth of each subtree used as tie breaker for trees of equal frequency */ 1522 913 1523 staticuch length_code[MAX_MATCH - MIN_MATCH + 1];914 uch length_code[MAX_MATCH - MIN_MATCH + 1]; 1524 915 1525 916 /* length code for each normalized match length (0 == MIN_MATCH) */ 1526 917 1527 staticuch dist_code[512];918 uch dist_code[512]; 1528 919 1529 920 /* distance codes. The first 256 values correspond to the distances … … 1532 923 */ 1533 924 1534 staticint base_length[LENGTH_CODES];925 int base_length[LENGTH_CODES]; 1535 926 1536 927 /* First normalized length for each code (0 = MIN_MATCH) */ 1537 928 1538 staticint base_dist[D_CODES];929 int base_dist[D_CODES]; 1539 930 1540 931 /* First normalized distance for each code (0 = distance of 1) */ 1541 932 1542 #define l_buf inbuf 1543 /* DECLARE(uch, l_buf, LIT_BUFSIZE); buffer for literals or lengths */ 1544 1545 /* DECLARE(ush, d_buf, DIST_BUFSIZE); buffer for distances */ 1546 1547 static uch flag_buf[(LIT_BUFSIZE / 8)]; 933 uch flag_buf[LIT_BUFSIZE / 8]; 1548 934 1549 935 /* flag_buf is a bit array distinguishing literals from lengths in … … 1551 937 */ 1552 938 1553 static unsigned last_lit;/* running index in l_buf */1554 static unsigned last_dist;/* running index in d_buf */1555 static unsigned last_flags;/* running index in flag_buf */1556 static uch flags;/* current flags not yet saved in flag_buf */1557 static uch flag_bit;/* current bit used in flags */939 unsigned last_lit; /* running index in l_buf */ 940 unsigned last_dist; /* running index in d_buf */ 941 unsigned last_flags; /* running index in flag_buf */ 942 uch flags; /* current flags not yet saved in flag_buf */ 943 uch flag_bit; /* current bit used in flags */ 1558 944 1559 945 /* bits are filled in flags starting at bit 0 (least significant). … … 1562 948 */ 1563 949 1564 static ulg opt_len; /* bit length of current block with optimal trees */ 1565 static ulg static_len; /* bit length of current block with static trees */ 1566 1567 static ulg compressed_len; /* total bit length of compressed file */ 1568 1569 1570 static ush *file_type; /* pointer to UNKNOWN, BINARY or ASCII */ 1571 static int *file_method; /* pointer to DEFLATE or STORE */ 1572 1573 /* =========================================================================== 1574 * Local (static) routines in this file. 1575 */ 1576 1577 static void init_block(void); 1578 static void pqdownheap(ct_data * tree, int k); 1579 static void gen_bitlen(tree_desc * desc); 950 ulg opt_len; /* bit length of current block with optimal trees */ 951 ulg static_len; /* bit length of current block with static trees */ 952 953 ulg compressed_len; /* total bit length of compressed file */ 954 }; 955 956 #define G2ptr ((struct globals2*)(ptr_to_globals)) 957 #define G2 (*G2ptr) 958 959 960 /* =========================================================================== 961 */ 1580 962 static void gen_codes(ct_data * tree, int max_code); 1581 963 static void build_tree(tree_desc * desc); … … 1585 967 static void send_all_trees(int lcodes, int dcodes, int blcodes); 1586 968 static void compress_block(ct_data * ltree, ct_data * dtree); 1587 static void set_file_type(void);1588 969 1589 970 1590 971 #ifndef DEBUG 1591 # define send_code(c, tree) send_bits(tree[c].Code, tree[c].Len) 1592 /* Send a code of the given tree. c and tree must not have side effects */ 1593 1594 #else /* DEBUG */ 1595 # define send_code(c, tree) \ 1596 { if (verbose>1) bb_error_msg("\ncd %3d ",(c)); \ 1597 send_bits(tree[c].Code, tree[c].Len); } 1598 #endif 1599 1600 #define d_code(dist) \ 1601 ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)]) 972 /* Send a code of the given tree. c and tree must not have side effects */ 973 # define SEND_CODE(c, tree) send_bits(tree[c].Code, tree[c].Len) 974 #else 975 # define SEND_CODE(c, tree) \ 976 { \ 977 if (verbose > 1) bb_error_msg("\ncd %3d ",(c)); \ 978 send_bits(tree[c].Code, tree[c].Len); \ 979 } 980 #endif 981 982 #define D_CODE(dist) \ 983 ((dist) < 256 ? G2.dist_code[dist] : G2.dist_code[256 + ((dist)>>7)]) 1602 984 /* Mapping from a distance to a distance code. dist is the distance - 1 and 1603 985 * must not have side effects. dist_code[256] and dist_code[257] are never 1604 986 * used. 1605 */ 1606 1607 /* the arguments must not have side effects */ 1608 1609 /* =========================================================================== 1610 * Allocate the match buffer, initialize the various tables and save the 1611 * location of the internal file attribute (ascii/binary) and method 1612 * (DEFLATE/STORE). 1613 */ 1614 static void ct_init(ush * attr, int *methodp) 1615 { 1616 int n; /* iterates over tree elements */ 1617 int bits; /* bit counter */ 1618 int length; /* length value */ 1619 int code; /* code value */ 1620 int dist; /* distance index */ 1621 1622 file_type = attr; 1623 file_method = methodp; 1624 compressed_len = 0L; 1625 1626 if (static_dtree[0].Len != 0) 1627 return; /* ct_init already called */ 1628 1629 /* Initialize the mapping length (0..255) -> length code (0..28) */ 1630 length = 0; 1631 for (code = 0; code < LENGTH_CODES - 1; code++) { 1632 base_length[code] = length; 1633 for (n = 0; n < (1 << extra_lbits[code]); n++) { 1634 length_code[length++] = (uch) code; 1635 } 1636 } 1637 Assert(length == 256, "ct_init: length != 256"); 1638 /* Note that the length 255 (match length 258) can be represented 1639 * in two different ways: code 284 + 5 bits or code 285, so we 1640 * overwrite length_code[255] to use the best encoding: 1641 */ 1642 length_code[length - 1] = (uch) code; 1643 1644 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 1645 dist = 0; 1646 for (code = 0; code < 16; code++) { 1647 base_dist[code] = dist; 1648 for (n = 0; n < (1 << extra_dbits[code]); n++) { 1649 dist_code[dist++] = (uch) code; 1650 } 1651 } 1652 Assert(dist == 256, "ct_init: dist != 256"); 1653 dist >>= 7; /* from now on, all distances are divided by 128 */ 1654 for (; code < D_CODES; code++) { 1655 base_dist[code] = dist << 7; 1656 for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) { 1657 dist_code[256 + dist++] = (uch) code; 1658 } 1659 } 1660 Assert(dist == 256, "ct_init: 256+dist != 512"); 1661 1662 /* Construct the codes of the static literal tree */ 1663 for (bits = 0; bits <= MAX_BITS; bits++) 1664 bl_count[bits] = 0; 1665 n = 0; 1666 while (n <= 143) 1667 static_ltree[n++].Len = 8, bl_count[8]++; 1668 while (n <= 255) 1669 static_ltree[n++].Len = 9, bl_count[9]++; 1670 while (n <= 279) 1671 static_ltree[n++].Len = 7, bl_count[7]++; 1672 while (n <= 287) 1673 static_ltree[n++].Len = 8, bl_count[8]++; 1674 /* Codes 286 and 287 do not exist, but we must include them in the 1675 * tree construction to get a canonical Huffman tree (longest code 1676 * all ones) 1677 */ 1678 gen_codes((ct_data *) static_ltree, L_CODES + 1); 1679 1680 /* The static distance tree is trivial: */ 1681 for (n = 0; n < D_CODES; n++) { 1682 static_dtree[n].Len = 5; 1683 static_dtree[n].Code = bi_reverse(n, 5); 1684 } 1685 1686 /* Initialize the first block of the first file: */ 1687 init_block(); 1688 } 987 * The arguments must not have side effects. 988 */ 989 1689 990 1690 991 /* =========================================================================== … … 1693 994 static void init_block(void) 1694 995 { 1695 int n; 996 int n; /* iterates over tree elements */ 1696 997 1697 998 /* Initialize the trees. */ 1698 999 for (n = 0; n < L_CODES; n++) 1699 dyn_ltree[n].Freq = 0;1000 G2.dyn_ltree[n].Freq = 0; 1700 1001 for (n = 0; n < D_CODES; n++) 1701 dyn_dtree[n].Freq = 0;1002 G2.dyn_dtree[n].Freq = 0; 1702 1003 for (n = 0; n < BL_CODES; n++) 1703 bl_tree[n].Freq = 0; 1704 1705 dyn_ltree[END_BLOCK].Freq = 1; 1706 opt_len = static_len = 0L; 1707 last_lit = last_dist = last_flags = 0; 1708 flags = 0; 1709 flag_bit = 1; 1710 } 1711 1712 #define SMALLEST 1 1713 /* Index within the heap array of least frequent node in the Huffman tree */ 1714 1715 1716 /* =========================================================================== 1717 * Remove the smallest element from the heap and recreate the heap with 1718 * one less element. Updates heap and heap_len. 1719 */ 1720 #define pqremove(tree, top) \ 1721 {\ 1722 top = heap[SMALLEST]; \ 1723 heap[SMALLEST] = heap[heap_len--]; \ 1724 pqdownheap(tree, SMALLEST); \ 1725 } 1726 1727 /* =========================================================================== 1728 * Compares to subtrees, using the tree depth as tie breaker when 1729 * the subtrees have equal frequency. This minimizes the worst case length. 1730 */ 1731 #define smaller(tree, n, m) \ 1732 (tree[n].Freq < tree[m].Freq || \ 1733 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 1004 G2.bl_tree[n].Freq = 0; 1005 1006 G2.dyn_ltree[END_BLOCK].Freq = 1; 1007 G2.opt_len = G2.static_len = 0; 1008 G2.last_lit = G2.last_dist = G2.last_flags = 0; 1009 G2.flags = 0; 1010 G2.flag_bit = 1; 1011 } 1012 1734 1013 1735 1014 /* =========================================================================== … … 1739 1018 * two sons). 1740 1019 */ 1020 1021 /* Compares to subtrees, using the tree depth as tie breaker when 1022 * the subtrees have equal frequency. This minimizes the worst case length. */ 1023 #define SMALLER(tree, n, m) \ 1024 (tree[n].Freq < tree[m].Freq \ 1025 || (tree[n].Freq == tree[m].Freq && G2.depth[n] <= G2.depth[m])) 1026 1741 1027 static void pqdownheap(ct_data * tree, int k) 1742 1028 { 1743 int v = heap[k];1029 int v = G2.heap[k]; 1744 1030 int j = k << 1; /* left son of k */ 1745 1031 1746 while (j <= heap_len) {1032 while (j <= G2.heap_len) { 1747 1033 /* Set j to the smallest of the two sons: */ 1748 if (j < heap_len && smaller(tree, heap[j + 1],heap[j]))1034 if (j < G2.heap_len && SMALLER(tree, G2.heap[j + 1], G2.heap[j])) 1749 1035 j++; 1750 1036 1751 1037 /* Exit if v is smaller than both sons */ 1752 if ( smaller(tree, v,heap[j]))1038 if (SMALLER(tree, v, G2.heap[j])) 1753 1039 break; 1754 1040 1755 1041 /* Exchange v with the smallest son */ 1756 heap[k] =heap[j];1042 G2.heap[k] = G2.heap[j]; 1757 1043 k = j; 1758 1044 … … 1760 1046 j <<= 1; 1761 1047 } 1762 heap[k] = v; 1763 } 1048 G2.heap[k] = v; 1049 } 1050 1764 1051 1765 1052 /* =========================================================================== … … 1776 1063 { 1777 1064 ct_data *tree = desc->dyn_tree; 1778 const extra_bits_t *extra = desc->extra_bits;1065 const uint8_t *extra = desc->extra_bits; 1779 1066 int base = desc->extra_base; 1780 1067 int max_code = desc->max_code; … … 1789 1076 1790 1077 for (bits = 0; bits <= MAX_BITS; bits++) 1791 bl_count[bits] = 0;1078 G2.bl_count[bits] = 0; 1792 1079 1793 1080 /* In a first pass, compute the optimal bit lengths (which may 1794 1081 * overflow in the case of the bit length tree). 1795 1082 */ 1796 tree[ heap[heap_max]].Len = 0; /* root of the heap */1797 1798 for (h = heap_max + 1; h < HEAP_SIZE; h++) {1799 n = heap[h];1083 tree[G2.heap[G2.heap_max]].Len = 0; /* root of the heap */ 1084 1085 for (h = G2.heap_max + 1; h < HEAP_SIZE; h++) { 1086 n = G2.heap[h]; 1800 1087 bits = tree[tree[n].Dad].Len + 1; 1801 if (bits > max_length) 1802 bits = max_length, overflow++; 1088 if (bits > max_length) { 1089 bits = max_length; 1090 overflow++; 1091 } 1803 1092 tree[n].Len = (ush) bits; 1804 1093 /* We overwrite tree[n].Dad which is no longer needed */ … … 1807 1096 continue; /* not a leaf node */ 1808 1097 1809 bl_count[bits]++;1098 G2.bl_count[bits]++; 1810 1099 xbits = 0; 1811 1100 if (n >= base) 1812 1101 xbits = extra[n - base]; 1813 1102 f = tree[n].Freq; 1814 opt_len += (ulg) f *(bits + xbits);1103 G2.opt_len += (ulg) f *(bits + xbits); 1815 1104 1816 1105 if (stree) 1817 static_len += (ulg) f *(stree[n].Len + xbits);1106 G2.static_len += (ulg) f * (stree[n].Len + xbits); 1818 1107 } 1819 1108 if (overflow == 0) … … 1826 1115 do { 1827 1116 bits = max_length - 1; 1828 while ( bl_count[bits] == 0)1117 while (G2.bl_count[bits] == 0) 1829 1118 bits--; 1830 bl_count[bits]--; /* move one leaf down the tree */1831 bl_count[bits + 1] += 2; /* move one overflow item as its brother */1832 bl_count[max_length]--;1119 G2.bl_count[bits]--; /* move one leaf down the tree */ 1120 G2.bl_count[bits + 1] += 2; /* move one overflow item as its brother */ 1121 G2.bl_count[max_length]--; 1833 1122 /* The brother of the overflow item also moves one step up, 1834 1123 * but this does not affect bl_count[max_length] … … 1843 1132 */ 1844 1133 for (bits = max_length; bits != 0; bits--) { 1845 n = bl_count[bits];1134 n = G2.bl_count[bits]; 1846 1135 while (n != 0) { 1847 m = heap[--h];1136 m = G2.heap[--h]; 1848 1137 if (m > max_code) 1849 1138 continue; 1850 1139 if (tree[m].Len != (unsigned) bits) { 1851 Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len, 1852 bits)); 1853 opt_len += 1854 ((long) bits - (long) tree[m].Len) * (long) tree[m].Freq; 1855 tree[m].Len = (ush) bits; 1140 Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len, bits)); 1141 G2.opt_len += ((int32_t) bits - tree[m].Len) * tree[m].Freq; 1142 tree[m].Len = bits; 1856 1143 } 1857 1144 n--; … … 1859 1146 } 1860 1147 } 1148 1861 1149 1862 1150 /* =========================================================================== … … 1879 1167 */ 1880 1168 for (bits = 1; bits <= MAX_BITS; bits++) { 1881 next_code[bits] = code = (code + bl_count[bits - 1]) << 1;1169 next_code[bits] = code = (code + G2.bl_count[bits - 1]) << 1; 1882 1170 } 1883 1171 /* Check that the bit counts in bl_count are consistent. The last code 1884 1172 * must be all ones. 1885 1173 */ 1886 Assert(code + bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1,1174 Assert(code + G2.bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1, 1887 1175 "inconsistent bit counts"); 1888 1176 Tracev((stderr, "\ngen_codes: max_code %d ", max_code)); … … 1896 1184 tree[n].Code = bi_reverse(next_code[len]++, len); 1897 1185 1898 Tracec(tree != static_ltree,1186 Tracec(tree != G2.static_ltree, 1899 1187 (stderr, "\nn %3d %c l %2d c %4x (%x) ", n, 1900 1188 (isgraph(n) ? n : ' '), len, tree[n].Code, … … 1902 1190 } 1903 1191 } 1192 1904 1193 1905 1194 /* =========================================================================== … … 1911 1200 * also updated if stree is not null. The field max_code is set. 1912 1201 */ 1202 1203 /* Remove the smallest element from the heap and recreate the heap with 1204 * one less element. Updates heap and heap_len. */ 1205 1206 #define SMALLEST 1 1207 /* Index within the heap array of least frequent node in the Huffman tree */ 1208 1209 #define PQREMOVE(tree, top) \ 1210 do { \ 1211 top = G2.heap[SMALLEST]; \ 1212 G2.heap[SMALLEST] = G2.heap[G2.heap_len--]; \ 1213 pqdownheap(tree, SMALLEST); \ 1214 } while (0) 1215 1913 1216 static void build_tree(tree_desc * desc) 1914 1217 { … … 1924 1227 * heap[0] is not used. 1925 1228 */ 1926 heap_len = 0, heap_max = HEAP_SIZE; 1229 G2.heap_len = 0; 1230 G2.heap_max = HEAP_SIZE; 1927 1231 1928 1232 for (n = 0; n < elems; n++) { 1929 1233 if (tree[n].Freq != 0) { 1930 heap[++heap_len] = max_code = n;1931 depth[n] = 0;1234 G2.heap[++G2.heap_len] = max_code = n; 1235 G2.depth[n] = 0; 1932 1236 } else { 1933 1237 tree[n].Len = 0; … … 1940 1244 * two codes of non zero frequency. 1941 1245 */ 1942 while ( heap_len < 2) {1943 int new = heap[++heap_len] = (max_code < 2 ? ++max_code : 0);1246 while (G2.heap_len < 2) { 1247 int new = G2.heap[++G2.heap_len] = (max_code < 2 ? ++max_code : 0); 1944 1248 1945 1249 tree[new].Freq = 1; 1946 depth[new] = 0;1947 opt_len--;1250 G2.depth[new] = 0; 1251 G2.opt_len--; 1948 1252 if (stree) 1949 static_len -= stree[new].Len;1253 G2.static_len -= stree[new].Len; 1950 1254 /* new is 0 or 1 so it does not have extra bits */ 1951 1255 } … … 1955 1259 * establish sub-heaps of increasing lengths: 1956 1260 */ 1957 for (n = heap_len / 2; n >= 1; n--)1261 for (n = G2.heap_len / 2; n >= 1; n--) 1958 1262 pqdownheap(tree, n); 1959 1263 … … 1962 1266 */ 1963 1267 do { 1964 pqremove(tree, n); /* n = node of least frequency */1965 m = heap[SMALLEST]; /* m = node of next least frequency */1966 1967 heap[--heap_max] = n; /* keep the nodes sorted by frequency */1968 heap[--heap_max] = m;1268 PQREMOVE(tree, n); /* n = node of least frequency */ 1269 m = G2.heap[SMALLEST]; /* m = node of next least frequency */ 1270 1271 G2.heap[--G2.heap_max] = n; /* keep the nodes sorted by frequency */ 1272 G2.heap[--G2.heap_max] = m; 1969 1273 1970 1274 /* Create a new node father of n and m */ 1971 1275 tree[node].Freq = tree[n].Freq + tree[m].Freq; 1972 depth[node] = (uch) (MAX(depth[n], depth[m]) + 1);1276 G2.depth[node] = MAX(G2.depth[n], G2.depth[m]) + 1; 1973 1277 tree[n].Dad = tree[m].Dad = (ush) node; 1974 1278 #ifdef DUMP_BL_TREE 1975 if (tree == bl_tree) {1279 if (tree == G2.bl_tree) { 1976 1280 bb_error_msg("\nnode %d(%d), sons %d(%d) %d(%d)", 1977 1281 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); … … 1979 1283 #endif 1980 1284 /* and insert the new node in the heap */ 1981 heap[SMALLEST] = node++;1285 G2.heap[SMALLEST] = node++; 1982 1286 pqdownheap(tree, SMALLEST); 1983 1287 1984 } while ( heap_len >= 2);1985 1986 heap[--heap_max] =heap[SMALLEST];1288 } while (G2.heap_len >= 2); 1289 1290 G2.heap[--G2.heap_max] = G2.heap[SMALLEST]; 1987 1291 1988 1292 /* At this point, the fields freq and dad are set. We can now … … 1994 1298 gen_codes((ct_data *) tree, max_code); 1995 1299 } 1300 1996 1301 1997 1302 /* =========================================================================== … … 2011 1316 int min_count = 4; /* min repeat count */ 2012 1317 2013 if (nextlen == 0) 2014 max_count = 138, min_count = 3; 2015 tree[max_code + 1].Len = (ush) 0xffff; /* guard */ 1318 if (nextlen == 0) { 1319 max_count = 138; 1320 min_count = 3; 1321 } 1322 tree[max_code + 1].Len = 0xffff; /* guard */ 2016 1323 2017 1324 for (n = 0; n <= max_code; n++) { 2018 1325 curlen = nextlen; 2019 1326 nextlen = tree[n + 1].Len; 2020 if (++count < max_count && curlen == nextlen) {1327 if (++count < max_count && curlen == nextlen) 2021 1328 continue; 2022 } else if (count < min_count) { 2023 bl_tree[curlen].Freq += count; 1329 1330 if (count < min_count) { 1331 G2.bl_tree[curlen].Freq += count; 2024 1332 } else if (curlen != 0) { 2025 1333 if (curlen != prevlen) 2026 bl_tree[curlen].Freq++;2027 bl_tree[REP_3_6].Freq++;1334 G2.bl_tree[curlen].Freq++; 1335 G2.bl_tree[REP_3_6].Freq++; 2028 1336 } else if (count <= 10) { 2029 bl_tree[REPZ_3_10].Freq++;1337 G2.bl_tree[REPZ_3_10].Freq++; 2030 1338 } else { 2031 bl_tree[REPZ_11_138].Freq++;1339 G2.bl_tree[REPZ_11_138].Freq++; 2032 1340 } 2033 1341 count = 0; 2034 1342 prevlen = curlen; 1343 1344 max_count = 7; 1345 min_count = 4; 2035 1346 if (nextlen == 0) { 2036 max_count = 138, min_count = 3; 1347 max_count = 138; 1348 min_count = 3; 2037 1349 } else if (curlen == nextlen) { 2038 max_count = 6, min_count = 3; 2039 } else { 2040 max_count = 7, min_count = 4; 1350 max_count = 6; 1351 min_count = 3; 2041 1352 } 2042 1353 } 2043 1354 } 1355 2044 1356 2045 1357 /* =========================================================================== … … 2068 1380 } else if (count < min_count) { 2069 1381 do { 2070 send_code(curlen, bl_tree); 2071 } while (--count != 0); 2072 1382 SEND_CODE(curlen, G2.bl_tree); 1383 } while (--count); 2073 1384 } else if (curlen != 0) { 2074 1385 if (curlen != prevlen) { 2075 send_code(curlen,bl_tree);1386 SEND_CODE(curlen, G2.bl_tree); 2076 1387 count--; 2077 1388 } 2078 1389 Assert(count >= 3 && count <= 6, " 3_6?"); 2079 send_code(REP_3_6,bl_tree);1390 SEND_CODE(REP_3_6, G2.bl_tree); 2080 1391 send_bits(count - 3, 2); 2081 2082 1392 } else if (count <= 10) { 2083 send_code(REPZ_3_10,bl_tree);1393 SEND_CODE(REPZ_3_10, G2.bl_tree); 2084 1394 send_bits(count - 3, 3); 2085 2086 1395 } else { 2087 send_code(REPZ_11_138,bl_tree);1396 SEND_CODE(REPZ_11_138, G2.bl_tree); 2088 1397 send_bits(count - 11, 7); 2089 1398 } … … 2091 1400 prevlen = curlen; 2092 1401 if (nextlen == 0) { 2093 max_count = 138, min_count = 3; 1402 max_count = 138; 1403 min_count = 3; 2094 1404 } else if (curlen == nextlen) { 2095 max_count = 6, min_count = 3; 1405 max_count = 6; 1406 min_count = 3; 2096 1407 } else { 2097 max_count = 7, min_count = 4; 1408 max_count = 7; 1409 min_count = 4; 2098 1410 } 2099 1411 } 2100 1412 } 1413 2101 1414 2102 1415 /* =========================================================================== … … 2109 1422 2110 1423 /* Determine the bit length frequencies for literal and distance trees */ 2111 scan_tree( (ct_data *) dyn_ltree,l_desc.max_code);2112 scan_tree( (ct_data *) dyn_dtree,d_desc.max_code);1424 scan_tree(G2.dyn_ltree, G2.l_desc.max_code); 1425 scan_tree(G2.dyn_dtree, G2.d_desc.max_code); 2113 1426 2114 1427 /* Build the bit length tree: */ 2115 build_tree( (tree_desc *) (&bl_desc));1428 build_tree(&G2.bl_desc); 2116 1429 /* opt_len now includes the length of the tree representations, except 2117 1430 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. … … 2123 1436 */ 2124 1437 for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) { 2125 if ( bl_tree[bl_order[max_blindex]].Len != 0)1438 if (G2.bl_tree[bl_order[max_blindex]].Len != 0) 2126 1439 break; 2127 1440 } 2128 1441 /* Update opt_len to include the bit length tree and counts */ 2129 opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;2130 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", opt_len,static_len));1442 G2.opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4; 1443 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", G2.opt_len, G2.static_len)); 2131 1444 2132 1445 return max_blindex; 2133 1446 } 1447 2134 1448 2135 1449 /* =========================================================================== … … 2151 1465 for (rank = 0; rank < blcodes; rank++) { 2152 1466 Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 2153 send_bits(bl_tree[bl_order[rank]].Len, 3); 2154 } 2155 Tracev((stderr, "\nbl tree: sent %ld", bits_sent)); 2156 2157 send_tree((ct_data *) dyn_ltree, lcodes - 1); /* send the literal tree */ 2158 Tracev((stderr, "\nlit tree: sent %ld", bits_sent)); 2159 2160 send_tree((ct_data *) dyn_dtree, dcodes - 1); /* send the distance tree */ 2161 Tracev((stderr, "\ndist tree: sent %ld", bits_sent)); 2162 } 1467 send_bits(G2.bl_tree[bl_order[rank]].Len, 3); 1468 } 1469 Tracev((stderr, "\nbl tree: sent %ld", G1.bits_sent)); 1470 1471 send_tree((ct_data *) G2.dyn_ltree, lcodes - 1); /* send the literal tree */ 1472 Tracev((stderr, "\nlit tree: sent %ld", G1.bits_sent)); 1473 1474 send_tree((ct_data *) G2.dyn_dtree, dcodes - 1); /* send the distance tree */ 1475 Tracev((stderr, "\ndist tree: sent %ld", G1.bits_sent)); 1476 } 1477 1478 1479 /* =========================================================================== 1480 * Save the match info and tally the frequency counts. Return true if 1481 * the current block must be flushed. 1482 */ 1483 static int ct_tally(int dist, int lc) 1484 { 1485 G1.l_buf[G2.last_lit++] = lc; 1486 if (dist == 0) { 1487 /* lc is the unmatched char */ 1488 G2.dyn_ltree[lc].Freq++; 1489 } else { 1490 /* Here, lc is the match length - MIN_MATCH */ 1491 dist--; /* dist = match distance - 1 */ 1492 Assert((ush) dist < (ush) MAX_DIST 1493 && (ush) lc <= (ush) (MAX_MATCH - MIN_MATCH) 1494 && (ush) D_CODE(dist) < (ush) D_CODES, "ct_tally: bad match" 1495 ); 1496 1497 G2.dyn_ltree[G2.length_code[lc] + LITERALS + 1].Freq++; 1498 G2.dyn_dtree[D_CODE(dist)].Freq++; 1499 1500 G1.d_buf[G2.last_dist++] = dist; 1501 G2.flags |= G2.flag_bit; 1502 } 1503 G2.flag_bit <<= 1; 1504 1505 /* Output the flags if they fill a byte: */ 1506 if ((G2.last_lit & 7) == 0) { 1507 G2.flag_buf[G2.last_flags++] = G2.flags; 1508 G2.flags = 0; 1509 G2.flag_bit = 1; 1510 } 1511 /* Try to guess if it is profitable to stop the current block here */ 1512 if ((G2.last_lit & 0xfff) == 0) { 1513 /* Compute an upper bound for the compressed length */ 1514 ulg out_length = G2.last_lit * 8L; 1515 ulg in_length = (ulg) G1.strstart - G1.block_start; 1516 int dcode; 1517 1518 for (dcode = 0; dcode < D_CODES; dcode++) { 1519 out_length += G2.dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]); 1520 } 1521 out_length >>= 3; 1522 Trace((stderr, 1523 "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", 1524 G2.last_lit, G2.last_dist, in_length, out_length, 1525 100L - out_length * 100L / in_length)); 1526 if (G2.last_dist < G2.last_lit / 2 && out_length < in_length / 2) 1527 return 1; 1528 } 1529 return (G2.last_lit == LIT_BUFSIZE - 1 || G2.last_dist == DIST_BUFSIZE); 1530 /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K 1531 * on 16 bit machines and because stored blocks are restricted to 1532 * 64K-1 bytes. 1533 */ 1534 } 1535 1536 /* =========================================================================== 1537 * Send the block data compressed using the given Huffman trees 1538 */ 1539 static void compress_block(ct_data * ltree, ct_data * dtree) 1540 { 1541 unsigned dist; /* distance of matched string */ 1542 int lc; /* match length or unmatched char (if dist == 0) */ 1543 unsigned lx = 0; /* running index in l_buf */ 1544 unsigned dx = 0; /* running index in d_buf */ 1545 unsigned fx = 0; /* running index in flag_buf */ 1546 uch flag = 0; /* current flags */ 1547 unsigned code; /* the code to send */ 1548 int extra; /* number of extra bits to send */ 1549 1550 if (G2.last_lit != 0) do { 1551 if ((lx & 7) == 0) 1552 flag = G2.flag_buf[fx++]; 1553 lc = G1.l_buf[lx++]; 1554 if ((flag & 1) == 0) { 1555 SEND_CODE(lc, ltree); /* send a literal byte */ 1556 Tracecv(isgraph(lc), (stderr, " '%c' ", lc)); 1557 } else { 1558 /* Here, lc is the match length - MIN_MATCH */ 1559 code = G2.length_code[lc]; 1560 SEND_CODE(code + LITERALS + 1, ltree); /* send the length code */ 1561 extra = extra_lbits[code]; 1562 if (extra != 0) { 1563 lc -= G2.base_length[code]; 1564 send_bits(lc, extra); /* send the extra length bits */ 1565 } 1566 dist = G1.d_buf[dx++]; 1567 /* Here, dist is the match distance - 1 */ 1568 code = D_CODE(dist); 1569 Assert(code < D_CODES, "bad d_code"); 1570 1571 SEND_CODE(code, dtree); /* send the distance code */ 1572 extra = extra_dbits[code]; 1573 if (extra != 0) { 1574 dist -= G2.base_dist[code]; 1575 send_bits(dist, extra); /* send the extra distance bits */ 1576 } 1577 } /* literal or match pair ? */ 1578 flag >>= 1; 1579 } while (lx < G2.last_lit); 1580 1581 SEND_CODE(END_BLOCK, ltree); 1582 } 1583 2163 1584 2164 1585 /* =========================================================================== … … 2169 1590 static ulg flush_block(char *buf, ulg stored_len, int eof) 2170 1591 { 2171 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 2172 int max_blindex; /* index of last bit length code of non zero freq */ 2173 2174 flag_buf[last_flags] = flags; /* Save the flags for the last 8 items */ 2175 2176 /* Check if the file is ascii or binary */ 2177 if (*file_type == (ush) UNKNOWN) 2178 set_file_type(); 1592 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 1593 int max_blindex; /* index of last bit length code of non zero freq */ 1594 1595 G2.flag_buf[G2.last_flags] = G2.flags; /* Save the flags for the last 8 items */ 2179 1596 2180 1597 /* Construct the literal and distance trees */ 2181 build_tree( (tree_desc *) (&l_desc));2182 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", opt_len,static_len));2183 2184 build_tree( (tree_desc *) (&d_desc));2185 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", opt_len,static_len));1598 build_tree(&G2.l_desc); 1599 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", G2.opt_len, G2.static_len)); 1600 1601 build_tree(&G2.d_desc); 1602 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", G2.opt_len, G2.static_len)); 2186 1603 /* At this point, opt_len and static_len are the total bit lengths of 2187 1604 * the compressed block data, excluding the tree representations. … … 2194 1611 2195 1612 /* Determine the best encoding. Compute first the block length in bytes */ 2196 opt_lenb = ( opt_len + 3 + 7) >> 3;2197 static_lenb = ( static_len + 3 + 7) >> 3;1613 opt_lenb = (G2.opt_len + 3 + 7) >> 3; 1614 static_lenb = (G2.static_len + 3 + 7) >> 3; 2198 1615 2199 1616 Trace((stderr, 2200 1617 "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ", 2201 opt_lenb, opt_len, static_lenb,static_len, stored_len,2202 last_lit,last_dist));1618 opt_lenb, G2.opt_len, static_lenb, G2.static_len, stored_len, 1619 G2.last_lit, G2.last_dist)); 2203 1620 2204 1621 if (static_lenb <= opt_lenb) … … 2209 1626 * the whole file is transformed into a stored file: 2210 1627 */ 2211 if (stored_len <= opt_lenb && eof && compressed_len == 0L && seekable()) {1628 if (stored_len <= opt_lenb && eof && G2.compressed_len == 0L && seekable()) { 2212 1629 /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ 2213 if (buf == (char *) 0)1630 if (buf == NULL) 2214 1631 bb_error_msg("block vanished"); 2215 1632 2216 1633 copy_block(buf, (unsigned) stored_len, 0); /* without header */ 2217 compressed_len = stored_len << 3; 2218 *file_method = STORED; 2219 2220 } else if (stored_len + 4 <= opt_lenb && buf != (char *) 0) { 1634 G2.compressed_len = stored_len << 3; 1635 1636 } else if (stored_len + 4 <= opt_lenb && buf != NULL) { 2221 1637 /* 4: two words for the lengths */ 2222 1638 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. … … 2227 1643 */ 2228 1644 send_bits((STORED_BLOCK << 1) + eof, 3); /* send block type */ 2229 compressed_len = (compressed_len + 3 + 7) & ~7L;2230 compressed_len += (stored_len + 4) << 3;1645 G2.compressed_len = (G2.compressed_len + 3 + 7) & ~7L; 1646 G2.compressed_len += (stored_len + 4) << 3; 2231 1647 2232 1648 copy_block(buf, (unsigned) stored_len, 1); /* with header */ … … 2234 1650 } else if (static_lenb == opt_lenb) { 2235 1651 send_bits((STATIC_TREES << 1) + eof, 3); 2236 compress_block((ct_data *) static_ltree, (ct_data *)static_dtree);2237 compressed_len += 3 +static_len;1652 compress_block((ct_data *) G2.static_ltree, (ct_data *) G2.static_dtree); 1653 G2.compressed_len += 3 + G2.static_len; 2238 1654 } else { 2239 1655 send_bits((DYN_TREES << 1) + eof, 3); 2240 send_all_trees( l_desc.max_code + 1,d_desc.max_code + 1,1656 send_all_trees(G2.l_desc.max_code + 1, G2.d_desc.max_code + 1, 2241 1657 max_blindex + 1); 2242 compress_block((ct_data *) dyn_ltree, (ct_data *)dyn_dtree);2243 compressed_len += 3 +opt_len;2244 } 2245 Assert( compressed_len ==bits_sent, "bad compressed size");1658 compress_block((ct_data *) G2.dyn_ltree, (ct_data *) G2.dyn_dtree); 1659 G2.compressed_len += 3 + G2.opt_len; 1660 } 1661 Assert(G2.compressed_len == G1.bits_sent, "bad compressed size"); 2246 1662 init_block(); 2247 1663 2248 1664 if (eof) { 2249 1665 bi_windup(); 2250 compressed_len += 7; /* align on byte boundary */ 2251 } 2252 Tracev((stderr, "\ncomprlen %lu(%lu) ", compressed_len >> 3, 2253 compressed_len - 7 * eof)); 2254 2255 return compressed_len >> 3; 2256 } 2257 2258 /* =========================================================================== 2259 * Save the match info and tally the frequency counts. Return true if 2260 * the current block must be flushed. 2261 */ 2262 static int ct_tally(int dist, int lc) 2263 { 2264 l_buf[last_lit++] = (uch) lc; 2265 if (dist == 0) { 2266 /* lc is the unmatched char */ 2267 dyn_ltree[lc].Freq++; 2268 } else { 2269 /* Here, lc is the match length - MIN_MATCH */ 2270 dist--; /* dist = match distance - 1 */ 2271 Assert((ush) dist < (ush) MAX_DIST && 2272 (ush) lc <= (ush) (MAX_MATCH - MIN_MATCH) && 2273 (ush) d_code(dist) < (ush) D_CODES, "ct_tally: bad match"); 2274 2275 dyn_ltree[length_code[lc] + LITERALS + 1].Freq++; 2276 dyn_dtree[d_code(dist)].Freq++; 2277 2278 d_buf[last_dist++] = (ush) dist; 2279 flags |= flag_bit; 2280 } 2281 flag_bit <<= 1; 2282 2283 /* Output the flags if they fill a byte: */ 2284 if ((last_lit & 7) == 0) { 2285 flag_buf[last_flags++] = flags; 2286 flags = 0, flag_bit = 1; 2287 } 2288 /* Try to guess if it is profitable to stop the current block here */ 2289 if ((last_lit & 0xfff) == 0) { 2290 /* Compute an upper bound for the compressed length */ 2291 ulg out_length = (ulg) last_lit * 8L; 2292 ulg in_length = (ulg) strstart - block_start; 2293 int dcode; 2294 2295 for (dcode = 0; dcode < D_CODES; dcode++) { 2296 out_length += 2297 (ulg) dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]); 1666 G2.compressed_len += 7; /* align on byte boundary */ 1667 } 1668 Tracev((stderr, "\ncomprlen %lu(%lu) ", G2.compressed_len >> 3, 1669 G2.compressed_len - 7 * eof)); 1670 1671 return G2.compressed_len >> 3; 1672 } 1673 1674 1675 /* =========================================================================== 1676 * Update a hash value with the given input byte 1677 * IN assertion: all calls to to UPDATE_HASH are made with consecutive 1678 * input characters, so that a running hash key can be computed from the 1679 * previous key instead of complete recalculation each time. 1680 */ 1681 #define UPDATE_HASH(h, c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK) 1682 1683 1684 /* =========================================================================== 1685 * Same as above, but achieves better compression. We use a lazy 1686 * evaluation for matches: a match is finally adopted only if there is 1687 * no better match at the next window position. 1688 * 1689 * Processes a new input file and return its compressed length. Sets 1690 * the compressed length, crc, deflate flags and internal file 1691 * attributes. 1692 */ 1693 1694 /* Flush the current block, with given end-of-file flag. 1695 * IN assertion: strstart is set to the end of the current match. */ 1696 #define FLUSH_BLOCK(eof) \ 1697 flush_block( \ 1698 G1.block_start >= 0L \ 1699 ? (char*)&G1.window[(unsigned)G1.block_start] \ 1700 : (char*)NULL, \ 1701 (ulg)G1.strstart - G1.block_start, \ 1702 (eof) \ 1703 ) 1704 1705 /* Insert string s in the dictionary and set match_head to the previous head 1706 * of the hash chain (the most recent string with same hash key). Return 1707 * the previous length of the hash chain. 1708 * IN assertion: all calls to to INSERT_STRING are made with consecutive 1709 * input characters and the first MIN_MATCH bytes of s are valid 1710 * (except for the last MIN_MATCH-1 bytes of the input file). */ 1711 #define INSERT_STRING(s, match_head) \ 1712 do { \ 1713 UPDATE_HASH(G1.ins_h, G1.window[(s) + MIN_MATCH-1]); \ 1714 G1.prev[(s) & WMASK] = match_head = head[G1.ins_h]; \ 1715 head[G1.ins_h] = (s); \ 1716 } while (0) 1717 1718 static ulg deflate(void) 1719 { 1720 IPos hash_head; /* head of hash chain */ 1721 IPos prev_match; /* previous match */ 1722 int flush; /* set if current block must be flushed */ 1723 int match_available = 0; /* set if previous match exists */ 1724 unsigned match_length = MIN_MATCH - 1; /* length of best match */ 1725 1726 /* Process the input block. */ 1727 while (G1.lookahead != 0) { 1728 /* Insert the string window[strstart .. strstart+2] in the 1729 * dictionary, and set hash_head to the head of the hash chain: 1730 */ 1731 INSERT_STRING(G1.strstart, hash_head); 1732 1733 /* Find the longest match, discarding those <= prev_length. 1734 */ 1735 G1.prev_length = match_length; 1736 prev_match = G1.match_start; 1737 match_length = MIN_MATCH - 1; 1738 1739 if (hash_head != 0 && G1.prev_length < max_lazy_match 1740 && G1.strstart - hash_head <= MAX_DIST 1741 ) { 1742 /* To simplify the code, we prevent matches with the string 1743 * of window index 0 (in particular we have to avoid a match 1744 * of the string with itself at the start of the input file). 1745 */ 1746 match_length = longest_match(hash_head); 1747 /* longest_match() sets match_start */ 1748 if (match_length > G1.lookahead) 1749 match_length = G1.lookahead; 1750 1751 /* Ignore a length 3 match if it is too distant: */ 1752 if (match_length == MIN_MATCH && G1.strstart - G1.match_start > TOO_FAR) { 1753 /* If prev_match is also MIN_MATCH, G1.match_start is garbage 1754 * but we will ignore the current match anyway. 1755 */ 1756 match_length--; 1757 } 2298 1758 } 2299 out_length >>= 3; 2300 Trace((stderr, 2301 "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", 2302 last_lit, last_dist, in_length, out_length, 2303 100L - out_length * 100L / in_length)); 2304 if (last_dist < last_lit / 2 && out_length < in_length / 2) 2305 return 1; 2306 } 2307 return (last_lit == LIT_BUFSIZE - 1 || last_dist == DIST_BUFSIZE); 2308 /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K 2309 * on 16 bit machines and because stored blocks are restricted to 2310 * 64K-1 bytes. 2311 */ 2312 } 2313 2314 /* =========================================================================== 2315 * Send the block data compressed using the given Huffman trees 2316 */ 2317 static void compress_block(ct_data * ltree, ct_data * dtree) 2318 { 2319 unsigned dist; /* distance of matched string */ 2320 int lc; /* match length or unmatched char (if dist == 0) */ 2321 unsigned lx = 0; /* running index in l_buf */ 2322 unsigned dx = 0; /* running index in d_buf */ 2323 unsigned fx = 0; /* running index in flag_buf */ 2324 uch flag = 0; /* current flags */ 2325 unsigned code; /* the code to send */ 2326 int extra; /* number of extra bits to send */ 2327 2328 if (last_lit != 0) 2329 do { 2330 if ((lx & 7) == 0) 2331 flag = flag_buf[fx++]; 2332 lc = l_buf[lx++]; 2333 if ((flag & 1) == 0) { 2334 send_code(lc, ltree); /* send a literal byte */ 2335 Tracecv(isgraph(lc), (stderr, " '%c' ", lc)); 2336 } else { 2337 /* Here, lc is the match length - MIN_MATCH */ 2338 code = length_code[lc]; 2339 send_code(code + LITERALS + 1, ltree); /* send the length code */ 2340 extra = extra_lbits[code]; 2341 if (extra != 0) { 2342 lc -= base_length[code]; 2343 send_bits(lc, extra); /* send the extra length bits */ 2344 } 2345 dist = d_buf[dx++]; 2346 /* Here, dist is the match distance - 1 */ 2347 code = d_code(dist); 2348 Assert(code < D_CODES, "bad d_code"); 2349 2350 send_code(code, dtree); /* send the distance code */ 2351 extra = extra_dbits[code]; 2352 if (extra != 0) { 2353 dist -= base_dist[code]; 2354 send_bits(dist, extra); /* send the extra distance bits */ 2355 } 2356 } /* literal or match pair ? */ 2357 flag >>= 1; 2358 } while (lx < last_lit); 2359 2360 send_code(END_BLOCK, ltree); 2361 } 2362 2363 /* =========================================================================== 2364 * Set the file type to ASCII or BINARY, using a crude approximation: 2365 * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. 2366 * IN assertion: the fields freq of dyn_ltree are set and the total of all 2367 * frequencies does not exceed 64K (to fit in an int on 16 bit machines). 2368 */ 2369 static void set_file_type(void) 2370 { 2371 int n = 0; 2372 unsigned ascii_freq = 0; 2373 unsigned bin_freq = 0; 2374 2375 while (n < 7) 2376 bin_freq += dyn_ltree[n++].Freq; 2377 while (n < 128) 2378 ascii_freq += dyn_ltree[n++].Freq; 2379 while (n < LITERALS) 2380 bin_freq += dyn_ltree[n++].Freq; 2381 *file_type = bin_freq > (ascii_freq >> 2) ? BINARY : ASCII; 2382 if (*file_type == BINARY && translate_eol) { 2383 bb_error_msg("-l used on binary file"); 2384 } 2385 } 2386 2387 /* zip.c -- compress files to the gzip or pkzip format 2388 * Copyright (C) 1992-1993 Jean-loup Gailly 2389 * This is free software; you can redistribute it and/or modify it under the 2390 * terms of the GNU General Public License, see the file COPYING. 2391 */ 2392 2393 2394 static uint32_t crc; /* crc on uncompressed file data */ 2395 static long header_bytes; /* number of bytes in gzip header */ 2396 2397 static void put_long(ulg n) 2398 { 2399 put_short((n) & 0xffff); 2400 put_short(((ulg) (n)) >> 16); 2401 } 2402 2403 /* put_header_byte is used for the compressed output 2404 * - for the initial 4 bytes that can't overflow the buffer. 2405 */ 2406 #define put_header_byte(c) {outbuf[outcnt++]=(uch)(c);} 1759 /* If there was a match at the previous step and the current 1760 * match is not better, output the previous match: 1761 */ 1762 if (G1.prev_length >= MIN_MATCH && match_length <= G1.prev_length) { 1763 check_match(G1.strstart - 1, prev_match, G1.prev_length); 1764 flush = ct_tally(G1.strstart - 1 - prev_match, G1.prev_length - MIN_MATCH); 1765 1766 /* Insert in hash table all strings up to the end of the match. 1767 * strstart-1 and strstart are already inserted. 1768 */ 1769 G1.lookahead -= G1.prev_length - 1; 1770 G1.prev_length -= 2; 1771 do { 1772 G1.strstart++; 1773 INSERT_STRING(G1.strstart, hash_head); 1774 /* strstart never exceeds WSIZE-MAX_MATCH, so there are 1775 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH 1776 * these bytes are garbage, but it does not matter since the 1777 * next lookahead bytes will always be emitted as literals. 1778 */ 1779 } while (--G1.prev_length != 0); 1780 match_available = 0; 1781 match_length = MIN_MATCH - 1; 1782 G1.strstart++; 1783 if (flush) { 1784 FLUSH_BLOCK(0); 1785 G1.block_start = G1.strstart; 1786 } 1787 } else if (match_available) { 1788 /* If there was no match at the previous position, output a 1789 * single literal. If there was a match but the current match 1790 * is longer, truncate the previous match to a single literal. 1791 */ 1792 Tracevv((stderr, "%c", G1.window[G1.strstart - 1])); 1793 if (ct_tally(0, G1.window[G1.strstart - 1])) { 1794 FLUSH_BLOCK(0); 1795 G1.block_start = G1.strstart; 1796 } 1797 G1.strstart++; 1798 G1.lookahead--; 1799 } else { 1800 /* There is no previous match to compare with, wait for 1801 * the next step to decide. 1802 */ 1803 match_available = 1; 1804 G1.strstart++; 1805 G1.lookahead--; 1806 } 1807 Assert(G1.strstart <= G1.isize && lookahead <= G1.isize, "a bit too far"); 1808 1809 /* Make sure that we always have enough lookahead, except 1810 * at the end of the input file. We need MAX_MATCH bytes 1811 * for the next match, plus MIN_MATCH bytes to insert the 1812 * string following the next match. 1813 */ 1814 while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile) 1815 fill_window(); 1816 } 1817 if (match_available) 1818 ct_tally(0, G1.window[G1.strstart - 1]); 1819 1820 return FLUSH_BLOCK(1); /* eof */ 1821 } 1822 1823 1824 /* =========================================================================== 1825 * Initialize the bit string routines. 1826 */ 1827 static void bi_init(void) 1828 { 1829 G1.bi_buf = 0; 1830 G1.bi_valid = 0; 1831 #ifdef DEBUG 1832 G1.bits_sent = 0L; 1833 #endif 1834 } 1835 1836 1837 /* =========================================================================== 1838 * Initialize the "longest match" routines for a new file 1839 */ 1840 static void lm_init(ush * flagsp) 1841 { 1842 unsigned j; 1843 1844 /* Initialize the hash table. */ 1845 memset(head, 0, HASH_SIZE * sizeof(*head)); 1846 /* prev will be initialized on the fly */ 1847 1848 /* speed options for the general purpose bit flag */ 1849 *flagsp |= 2; /* FAST 4, SLOW 2 */ 1850 /* ??? reduce max_chain_length for binary files */ 1851 1852 G1.strstart = 0; 1853 G1.block_start = 0L; 1854 1855 G1.lookahead = file_read(G1.window, 1856 sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE); 1857 1858 if (G1.lookahead == 0 || G1.lookahead == (unsigned) -1) { 1859 G1.eofile = 1; 1860 G1.lookahead = 0; 1861 return; 1862 } 1863 G1.eofile = 0; 1864 /* Make sure that we always have enough lookahead. This is important 1865 * if input comes from a device such as a tty. 1866 */ 1867 while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile) 1868 fill_window(); 1869 1870 G1.ins_h = 0; 1871 for (j = 0; j < MIN_MATCH - 1; j++) 1872 UPDATE_HASH(G1.ins_h, G1.window[j]); 1873 /* If lookahead < MIN_MATCH, ins_h is garbage, but this is 1874 * not important since only literal bytes will be emitted. 1875 */ 1876 } 1877 1878 1879 /* =========================================================================== 1880 * Allocate the match buffer, initialize the various tables and save the 1881 * location of the internal file attribute (ascii/binary) and method 1882 * (DEFLATE/STORE). 1883 * One callsite in zip() 1884 */ 1885 static void ct_init(void) 1886 { 1887 int n; /* iterates over tree elements */ 1888 int length; /* length value */ 1889 int code; /* code value */ 1890 int dist; /* distance index */ 1891 1892 G2.compressed_len = 0L; 1893 1894 #ifdef NOT_NEEDED 1895 if (G2.static_dtree[0].Len != 0) 1896 return; /* ct_init already called */ 1897 #endif 1898 1899 /* Initialize the mapping length (0..255) -> length code (0..28) */ 1900 length = 0; 1901 for (code = 0; code < LENGTH_CODES - 1; code++) { 1902 G2.base_length[code] = length; 1903 for (n = 0; n < (1 << extra_lbits[code]); n++) { 1904 G2.length_code[length++] = code; 1905 } 1906 } 1907 Assert(length == 256, "ct_init: length != 256"); 1908 /* Note that the length 255 (match length 258) can be represented 1909 * in two different ways: code 284 + 5 bits or code 285, so we 1910 * overwrite length_code[255] to use the best encoding: 1911 */ 1912 G2.length_code[length - 1] = code; 1913 1914 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 1915 dist = 0; 1916 for (code = 0; code < 16; code++) { 1917 G2.base_dist[code] = dist; 1918 for (n = 0; n < (1 << extra_dbits[code]); n++) { 1919 G2.dist_code[dist++] = code; 1920 } 1921 } 1922 Assert(dist == 256, "ct_init: dist != 256"); 1923 dist >>= 7; /* from now on, all distances are divided by 128 */ 1924 for (; code < D_CODES; code++) { 1925 G2.base_dist[code] = dist << 7; 1926 for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) { 1927 G2.dist_code[256 + dist++] = code; 1928 } 1929 } 1930 Assert(dist == 256, "ct_init: 256+dist != 512"); 1931 1932 /* Construct the codes of the static literal tree */ 1933 /* already zeroed - it's in bss 1934 for (n = 0; n <= MAX_BITS; n++) 1935 G2.bl_count[n] = 0; */ 1936 1937 n = 0; 1938 while (n <= 143) { 1939 G2.static_ltree[n++].Len = 8; 1940 G2.bl_count[8]++; 1941 } 1942 while (n <= 255) { 1943 G2.static_ltree[n++].Len = 9; 1944 G2.bl_count[9]++; 1945 } 1946 while (n <= 279) { 1947 G2.static_ltree[n++].Len = 7; 1948 G2.bl_count[7]++; 1949 } 1950 while (n <= 287) { 1951 G2.static_ltree[n++].Len = 8; 1952 G2.bl_count[8]++; 1953 } 1954 /* Codes 286 and 287 do not exist, but we must include them in the 1955 * tree construction to get a canonical Huffman tree (longest code 1956 * all ones) 1957 */ 1958 gen_codes((ct_data *) G2.static_ltree, L_CODES + 1); 1959 1960 /* The static distance tree is trivial: */ 1961 for (n = 0; n < D_CODES; n++) { 1962 G2.static_dtree[n].Len = 5; 1963 G2.static_dtree[n].Code = bi_reverse(n, 5); 1964 } 1965 1966 /* Initialize the first block of the first file: */ 1967 init_block(); 1968 } 1969 2407 1970 2408 1971 /* =========================================================================== 2409 1972 * Deflate in to out. 2410 1973 * IN assertions: the input and output buffers are cleared. 2411 * The variables time_stamp and save_orig_name are initialized. 2412 */ 2413 static int zip(int in, int out) 2414 { 2415 uch my_flags = 0; /* general purpose bit flags */ 2416 ush attr = 0; /* ascii/binary flag */ 2417 ush deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */ 2418 2419 ifd = in; 2420 ofd = out; 2421 outcnt = 0; 1974 */ 1975 1976 static void zip(ulg time_stamp) 1977 { 1978 ush deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */ 1979 1980 G1.outcnt = 0; 2422 1981 2423 1982 /* Write the header to the gzip file. See algorithm.doc for the format */ 2424 2425 2426 method = DEFLATED; 2427 put_header_byte(GZIP_MAGIC[0]); /* magic header */ 2428 put_header_byte(GZIP_MAGIC[1]); 2429 put_header_byte(DEFLATED); /* compression method */ 2430 2431 put_header_byte(my_flags); /* general flags */ 2432 put_long(time_stamp); 1983 /* magic header for gzip files: 1F 8B */ 1984 /* compression method: 8 (DEFLATED) */ 1985 /* general flags: 0 */ 1986 put_32bit(0x00088b1f); 1987 put_32bit(time_stamp); 2433 1988 2434 1989 /* Write deflated file to zip file */ 2435 crc = updcrc(0, 0);2436 2437 bi_init( out);2438 ct_init( &attr, &method);1990 G1.crc = ~0; 1991 1992 bi_init(); 1993 ct_init(); 2439 1994 lm_init(&deflate_flags); 2440 1995 2441 put_byte((uch) deflate_flags); /* extra flags */ 2442 put_byte(OS_CODE); /* OS identifier */ 2443 2444 header_bytes = (long) outcnt; 2445 2446 (void) deflate(); 1996 put_8bit(deflate_flags); /* extra flags */ 1997 put_8bit(3); /* OS identifier = 3 (Unix) */ 1998 1999 deflate(); 2447 2000 2448 2001 /* Write the crc and uncompressed size */ 2449 put_long(crc); 2450 put_long(isize); 2451 header_bytes += 2 * sizeof(long); 2002 put_32bit(~G1.crc); 2003 put_32bit(G1.isize); 2452 2004 2453 2005 flush_outbuf(); 2454 return OK; 2455 } 2456 2457 2458 /* =========================================================================== 2459 * Read a new buffer from the current input file, perform end-of-line 2460 * translation, and update the crc and input file size. 2461 * IN assertion: size >= 2 (for end-of-line translation) 2462 */ 2463 static int file_read(char *buf, unsigned size) 2464 { 2465 unsigned len; 2466 2467 Assert(insize == 0, "inbuf not empty"); 2468 2469 len = read(ifd, buf, size); 2470 if (len == (unsigned) (-1) || len == 0) 2471 return (int) len; 2472 2473 crc = updcrc((uch *) buf, len); 2474 isize += (ulg) len; 2475 return (int) len; 2476 } 2477 2478 /* =========================================================================== 2479 * Write the output buffer outbuf[0..outcnt-1] and update bytes_out. 2480 * (used for the compressed data only) 2481 */ 2482 static void flush_outbuf(void) 2483 { 2484 if (outcnt == 0) 2485 return; 2486 2487 write_buf(ofd, (char *) outbuf, outcnt); 2488 outcnt = 0; 2489 } 2006 } 2007 2008 2009 /* ======================================================================== */ 2010 static 2011 char* make_new_name_gzip(char *filename) 2012 { 2013 return xasprintf("%s.gz", filename); 2014 } 2015 2016 static 2017 USE_DESKTOP(long long) int pack_gzip(void) 2018 { 2019 struct stat s; 2020 2021 clear_bufs(); 2022 s.st_ctime = 0; 2023 fstat(STDIN_FILENO, &s); 2024 zip(s.st_ctime); 2025 return 0; 2026 } 2027 2028 int gzip_main(int argc, char **argv); 2029 int gzip_main(int argc, char **argv) 2030 { 2031 unsigned opt; 2032 2033 /* Must match bbunzip's constants OPT_STDOUT, OPT_FORCE! */ 2034 opt = getopt32(argv, "cfv" USE_GUNZIP("d") "q123456789" ); 2035 option_mask32 &= 0x7; /* Clear -d, ignore -q, -0..9 */ 2036 //if (opt & 0x1) // -c 2037 //if (opt & 0x2) // -f 2038 //if (opt & 0x4) // -v 2039 #if ENABLE_GUNZIP /* gunzip_main may not be visible... */ 2040 if (opt & 0x8) { // -d 2041 return gunzip_main(argc, argv); 2042 } 2043 #endif 2044 argv += optind; 2045 2046 PTR_TO_GLOBALS = xzalloc(sizeof(struct globals) + sizeof(struct globals2)) 2047 + sizeof(struct globals); 2048 G2.l_desc.dyn_tree = G2.dyn_ltree; 2049 G2.l_desc.static_tree = G2.static_ltree; 2050 G2.l_desc.extra_bits = extra_lbits; 2051 G2.l_desc.extra_base = LITERALS + 1; 2052 G2.l_desc.elems = L_CODES; 2053 G2.l_desc.max_length = MAX_BITS; 2054 //G2.l_desc.max_code = 0; 2055 2056 G2.d_desc.dyn_tree = G2.dyn_dtree; 2057 G2.d_desc.static_tree = G2.static_dtree; 2058 G2.d_desc.extra_bits = extra_dbits; 2059 //G2.d_desc.extra_base = 0; 2060 G2.d_desc.elems = D_CODES; 2061 G2.d_desc.max_length = MAX_BITS; 2062 //G2.d_desc.max_code = 0; 2063 2064 G2.bl_desc.dyn_tree = G2.bl_tree; 2065 //G2.bl_desc.static_tree = NULL; 2066 G2.bl_desc.extra_bits = extra_blbits, 2067 //G2.bl_desc.extra_base = 0; 2068 G2.bl_desc.elems = BL_CODES; 2069 G2.bl_desc.max_length = MAX_BL_BITS; 2070 //G2.bl_desc.max_code = 0; 2071 2072 /* Allocate all global buffers (for DYN_ALLOC option) */ 2073 ALLOC(uch, G1.l_buf, INBUFSIZ); 2074 ALLOC(uch, G1.outbuf, OUTBUFSIZ); 2075 ALLOC(ush, G1.d_buf, DIST_BUFSIZE); 2076 ALLOC(uch, G1.window, 2L * WSIZE); 2077 ALLOC(ush, G1.prev, 1L << BITS); 2078 2079 /* Initialise the CRC32 table */ 2080 G1.crc_32_tab = crc32_filltable(NULL, 0); 2081 2082 return bbunpack(argv, make_new_name_gzip, pack_gzip); 2083 }
Note:
See TracChangeset
for help on using the changeset viewer.