gzip.c 71 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246
  1. /* vi: set sw=4 ts=4: */
  2. /*
  3. * Gzip implementation for busybox
  4. *
  5. * Based on GNU gzip Copyright (C) 1992-1993 Jean-loup Gailly.
  6. *
  7. * Originally adjusted for busybox by Charles P. Wright <cpw@unix.asb.com>
  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. *
  12. * Adjusted further by Erik Andersen <andersen@codepoet.org> to support
  13. * files as well as stdin/stdout, and to generally behave itself wrt
  14. * command line handling.
  15. *
  16. * Licensed under GPLv2 or later, see file LICENSE in this source tree.
  17. */
  18. /* TODO: full support for -v for DESKTOP
  19. * "/usr/bin/gzip -v a bogus aa" should say:
  20. a: 85.1% -- replaced with a.gz
  21. gzip: bogus: No such file or directory
  22. aa: 85.1% -- replaced with aa.gz
  23. */
  24. //config:config GZIP
  25. //config: bool "gzip (17 kb)"
  26. //config: default y
  27. //config: help
  28. //config: gzip is used to compress files.
  29. //config: It's probably the most widely used UNIX compression program.
  30. //config:
  31. //config:config FEATURE_GZIP_LONG_OPTIONS
  32. //config: bool "Enable long options"
  33. //config: default y
  34. //config: depends on GZIP && LONG_OPTS
  35. //config:
  36. //config:config GZIP_FAST
  37. //config: int "Trade memory for speed (0:small,slow - 2:fast,big)"
  38. //config: default 0
  39. //config: range 0 2
  40. //config: depends on GZIP
  41. //config: help
  42. //config: Enable big memory options for gzip.
  43. //config: 0: small buffers, small hash-tables
  44. //config: 1: larger buffers, larger hash-tables
  45. //config: 2: larger buffers, largest hash-tables
  46. //config: Larger models may give slightly better compression
  47. //config:
  48. //config:config FEATURE_GZIP_LEVELS
  49. //config: bool "Enable compression levels"
  50. //config: default n
  51. //config: depends on GZIP
  52. //config: help
  53. //config: Enable support for compression levels 4-9. The default level
  54. //config: is 6. If levels 1-3 are specified, 4 is used.
  55. //config: If this option is not selected, -N options are ignored and -9
  56. //config: is used.
  57. //config:
  58. //config:config FEATURE_GZIP_DECOMPRESS
  59. //config: bool "Enable decompression"
  60. //config: default y
  61. //config: depends on GZIP || GUNZIP || ZCAT
  62. //config: help
  63. //config: Enable -d (--decompress) and -t (--test) options for gzip.
  64. //config: This will be automatically selected if gunzip or zcat is
  65. //config: enabled.
  66. //applet:IF_GZIP(APPLET(gzip, BB_DIR_BIN, BB_SUID_DROP))
  67. //kbuild:lib-$(CONFIG_GZIP) += gzip.o
  68. //usage:#define gzip_trivial_usage
  69. //usage: "[-cfk" IF_FEATURE_GZIP_DECOMPRESS("dt") IF_FEATURE_GZIP_LEVELS("123456789") "] [FILE]..."
  70. //usage:#define gzip_full_usage "\n\n"
  71. //usage: "Compress FILEs (or stdin)\n"
  72. //usage: IF_FEATURE_GZIP_LEVELS(
  73. //usage: "\n -1..9 Compression level"
  74. //usage: )
  75. //usage: IF_FEATURE_GZIP_DECOMPRESS(
  76. //usage: "\n -d Decompress"
  77. //usage: "\n -t Test file integrity"
  78. //usage: )
  79. //usage: "\n -c Write to stdout"
  80. //usage: "\n -f Force"
  81. //usage: "\n -k Keep input files"
  82. //usage:
  83. //usage:#define gzip_example_usage
  84. //usage: "$ ls -la /tmp/busybox*\n"
  85. //usage: "-rw-rw-r-- 1 andersen andersen 1761280 Apr 14 17:47 /tmp/busybox.tar\n"
  86. //usage: "$ gzip /tmp/busybox.tar\n"
  87. //usage: "$ ls -la /tmp/busybox*\n"
  88. //usage: "-rw-rw-r-- 1 andersen andersen 554058 Apr 14 17:49 /tmp/busybox.tar.gz\n"
  89. #include "libbb.h"
  90. #include "bb_archive.h"
  91. /* ===========================================================================
  92. */
  93. //#define DEBUG 1
  94. /* Diagnostic functions */
  95. #ifdef DEBUG
  96. static int verbose;
  97. # define Assert(cond,msg) { if (!(cond)) bb_error_msg(msg); }
  98. # define Trace(x) fprintf x
  99. # define Tracev(x) {if (verbose) fprintf x; }
  100. # define Tracevv(x) {if (verbose > 1) fprintf x; }
  101. # define Tracec(c,x) {if (verbose && (c)) fprintf x; }
  102. # define Tracecv(c,x) {if (verbose > 1 && (c)) fprintf x; }
  103. #else
  104. # define Assert(cond,msg)
  105. # define Trace(x)
  106. # define Tracev(x)
  107. # define Tracevv(x)
  108. # define Tracec(c,x)
  109. # define Tracecv(c,x)
  110. #endif
  111. /* ===========================================================================
  112. */
  113. #if CONFIG_GZIP_FAST == 0
  114. # define SMALL_MEM
  115. #elif CONFIG_GZIP_FAST == 1
  116. # define MEDIUM_MEM
  117. #elif CONFIG_GZIP_FAST == 2
  118. # define BIG_MEM
  119. #else
  120. # error "Invalid CONFIG_GZIP_FAST value"
  121. #endif
  122. #ifndef INBUFSIZ
  123. # ifdef SMALL_MEM
  124. # define INBUFSIZ 0x2000 /* input buffer size */
  125. # else
  126. # define INBUFSIZ 0x8000 /* input buffer size */
  127. # endif
  128. #endif
  129. #ifndef OUTBUFSIZ
  130. # ifdef SMALL_MEM
  131. # define OUTBUFSIZ 8192 /* output buffer size */
  132. # else
  133. # define OUTBUFSIZ 16384 /* output buffer size */
  134. # endif
  135. #endif
  136. #ifndef DIST_BUFSIZE
  137. # ifdef SMALL_MEM
  138. # define DIST_BUFSIZE 0x2000 /* buffer for distances, see trees.c */
  139. # else
  140. # define DIST_BUFSIZE 0x8000 /* buffer for distances, see trees.c */
  141. # endif
  142. #endif
  143. /* gzip flag byte */
  144. #define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
  145. #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
  146. #define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
  147. #define ORIG_NAME 0x08 /* bit 3 set: original file name present */
  148. #define COMMENT 0x10 /* bit 4 set: file comment present */
  149. #define RESERVED 0xC0 /* bit 6,7: reserved */
  150. /* internal file attribute */
  151. #define UNKNOWN 0xffff
  152. #define BINARY 0
  153. #define ASCII 1
  154. #ifndef WSIZE
  155. # define WSIZE 0x8000 /* window size--must be a power of two, and */
  156. #endif /* at least 32K for zip's deflate method */
  157. #define MIN_MATCH 3
  158. #define MAX_MATCH 258
  159. /* The minimum and maximum match lengths */
  160. #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
  161. /* Minimum amount of lookahead, except at the end of the input file.
  162. * See deflate.c for comments about the MIN_MATCH+1.
  163. */
  164. #define MAX_DIST (WSIZE-MIN_LOOKAHEAD)
  165. /* In order to simplify the code, particularly on 16 bit machines, match
  166. * distances are limited to MAX_DIST instead of WSIZE.
  167. */
  168. #ifndef MAX_PATH_LEN
  169. # define MAX_PATH_LEN 1024 /* max pathname length */
  170. #endif
  171. #define seekable() 0 /* force sequential output */
  172. #define translate_eol 0 /* no option -a yet */
  173. #ifndef BITS
  174. # define BITS 16
  175. #endif
  176. #define INIT_BITS 9 /* Initial number of bits per code */
  177. #define BIT_MASK 0x1f /* Mask for 'number of compression bits' */
  178. /* Mask 0x20 is reserved to mean a fourth header byte, and 0x40 is free.
  179. * It's a pity that old uncompress does not check bit 0x20. That makes
  180. * extension of the format actually undesirable because old compress
  181. * would just crash on the new format instead of giving a meaningful
  182. * error message. It does check the number of bits, but it's more
  183. * helpful to say "unsupported format, get a new version" than
  184. * "can only handle 16 bits".
  185. */
  186. #ifdef MAX_EXT_CHARS
  187. # define MAX_SUFFIX MAX_EXT_CHARS
  188. #else
  189. # define MAX_SUFFIX 30
  190. #endif
  191. /* ===========================================================================
  192. * Compile with MEDIUM_MEM to reduce the memory requirements or
  193. * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
  194. * entire input file can be held in memory (not possible on 16 bit systems).
  195. * Warning: defining these symbols affects HASH_BITS (see below) and thus
  196. * affects the compression ratio. The compressed output
  197. * is still correct, and might even be smaller in some cases.
  198. */
  199. #ifdef SMALL_MEM
  200. # define HASH_BITS 13 /* Number of bits used to hash strings */
  201. #endif
  202. #ifdef MEDIUM_MEM
  203. # define HASH_BITS 14
  204. #endif
  205. #ifndef HASH_BITS
  206. # define HASH_BITS 15
  207. /* For portability to 16 bit machines, do not use values above 15. */
  208. #endif
  209. #define HASH_SIZE (unsigned)(1<<HASH_BITS)
  210. #define HASH_MASK (HASH_SIZE-1)
  211. #define WMASK (WSIZE-1)
  212. /* HASH_SIZE and WSIZE must be powers of two */
  213. #ifndef TOO_FAR
  214. # define TOO_FAR 4096
  215. #endif
  216. /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  217. /* ===========================================================================
  218. * These types are not really 'char', 'short' and 'long'
  219. */
  220. typedef uint8_t uch;
  221. typedef uint16_t ush;
  222. typedef uint32_t ulg;
  223. typedef int32_t lng;
  224. typedef ush Pos;
  225. typedef unsigned IPos;
  226. /* A Pos is an index in the character window. We use short instead of int to
  227. * save space in the various tables. IPos is used only for parameter passing.
  228. */
  229. enum {
  230. WINDOW_SIZE = 2 * WSIZE,
  231. /* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
  232. * input file length plus MIN_LOOKAHEAD.
  233. */
  234. #if !ENABLE_FEATURE_GZIP_LEVELS
  235. max_chain_length = 4096,
  236. /* To speed up deflation, hash chains are never searched beyond this length.
  237. * A higher limit improves compression ratio but degrades the speed.
  238. */
  239. max_lazy_match = 258,
  240. /* Attempt to find a better match only when the current match is strictly
  241. * smaller than this value. This mechanism is used only for compression
  242. * levels >= 4.
  243. */
  244. max_insert_length = max_lazy_match,
  245. /* Insert new strings in the hash table only if the match length
  246. * is not greater than this length. This saves time but degrades compression.
  247. * max_insert_length is used only for compression levels <= 3.
  248. */
  249. good_match = 32,
  250. /* Use a faster search when the previous match is longer than this */
  251. /* Values for max_lazy_match, good_match and max_chain_length, depending on
  252. * the desired pack level (0..9). The values given below have been tuned to
  253. * exclude worst case performance for pathological files. Better values may be
  254. * found for specific files.
  255. */
  256. nice_match = 258, /* Stop searching when current match exceeds this */
  257. /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
  258. * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
  259. * meaning.
  260. */
  261. #endif /* ENABLE_FEATURE_GZIP_LEVELS */
  262. };
  263. struct globals {
  264. /* =========================================================================== */
  265. /* global buffers, allocated once */
  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. /* buffer for literals or lengths */
  273. /* DECLARE(uch, l_buf, LIT_BUFSIZE); */
  274. DECLARE(uch, l_buf, INBUFSIZ);
  275. DECLARE(ush, d_buf, DIST_BUFSIZE);
  276. DECLARE(uch, outbuf, OUTBUFSIZ);
  277. /* Sliding window. Input bytes are read into the second half of the window,
  278. * and move to the first half later to keep a dictionary of at least WSIZE
  279. * bytes. With this organization, matches are limited to a distance of
  280. * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
  281. * performed with a length multiple of the block size. Also, it limits
  282. * the window size to 64K, which is quite useful on MSDOS.
  283. * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
  284. * be less efficient).
  285. */
  286. DECLARE(uch, window, 2L * WSIZE);
  287. /* Link to older string with same hash index. To limit the size of this
  288. * array to 64K, this link is maintained only for the last 32K strings.
  289. * An index in this array is thus a window index modulo 32K.
  290. */
  291. /* DECLARE(Pos, prev, WSIZE); */
  292. DECLARE(ush, prev, 1L << BITS);
  293. /* Heads of the hash chains or 0. */
  294. /* DECLARE(Pos, head, 1<<HASH_BITS); */
  295. #define head (G1.prev + WSIZE) /* hash head (see deflate.c) */
  296. #if ENABLE_FEATURE_GZIP_LEVELS
  297. unsigned max_chain_length;
  298. unsigned max_lazy_match;
  299. unsigned good_match;
  300. unsigned nice_match;
  301. #define max_chain_length (G1.max_chain_length)
  302. #define max_lazy_match (G1.max_lazy_match)
  303. #define good_match (G1.good_match)
  304. #define nice_match (G1.nice_match)
  305. #endif
  306. /* =========================================================================== */
  307. /* all members below are zeroed out in pack_gzip() for each next file */
  308. uint32_t crc; /* shift register contents */
  309. /*uint32_t *crc_32_tab;*/
  310. /* window position at the beginning of the current output block. Gets
  311. * negative when the window is moved backwards.
  312. */
  313. lng block_start;
  314. unsigned ins_h; /* hash index of string to be inserted */
  315. /* Number of bits by which ins_h and del_h must be shifted at each
  316. * input step. It must be such that after MIN_MATCH steps, the oldest
  317. * byte no longer takes part in the hash key, that is:
  318. * H_SHIFT * MIN_MATCH >= HASH_BITS
  319. */
  320. #define H_SHIFT ((HASH_BITS+MIN_MATCH-1) / MIN_MATCH)
  321. /* Length of the best match at previous step. Matches not greater than this
  322. * are discarded. This is used in the lazy match evaluation.
  323. */
  324. unsigned prev_length;
  325. unsigned strstart; /* start of string to insert */
  326. unsigned match_start; /* start of matching string */
  327. unsigned lookahead; /* number of valid bytes ahead in window */
  328. /* number of input bytes */
  329. ulg isize; /* only 32 bits stored in .gz file */
  330. /* bbox always use stdin/stdout */
  331. #define ifd STDIN_FILENO /* input file descriptor */
  332. #define ofd STDOUT_FILENO /* output file descriptor */
  333. #ifdef DEBUG
  334. unsigned insize; /* valid bytes in l_buf */
  335. #endif
  336. unsigned outcnt; /* bytes in output buffer */
  337. smallint eofile; /* flag set at end of input file */
  338. /* ===========================================================================
  339. * Local data used by the "bit string" routines.
  340. */
  341. /* Output buffer. bits are inserted starting at the bottom (least significant
  342. * bits).
  343. */
  344. unsigned bi_buf; /* was unsigned short */
  345. #undef BUF_SIZE
  346. #define BUF_SIZE (int)(8 * sizeof(G1.bi_buf))
  347. /* Number of bits used within bi_buf. (bi_buf might be implemented on
  348. * more than 16 bits on some systems.)
  349. */
  350. unsigned bi_valid;
  351. #ifdef DEBUG
  352. ulg bits_sent; /* bit length of the compressed data */
  353. # define DEBUG_bits_sent(v) (void)(G1.bits_sent v)
  354. #else
  355. # define DEBUG_bits_sent(v) ((void)0)
  356. #endif
  357. };
  358. #define G1 (*(ptr_to_globals - 1))
  359. /* ===========================================================================
  360. * Write the output buffer outbuf[0..outcnt-1] and update bytes_out.
  361. * (used for the compressed data only)
  362. */
  363. static void flush_outbuf(void)
  364. {
  365. if (G1.outcnt == 0)
  366. return;
  367. xwrite(ofd, (char *) G1.outbuf, G1.outcnt);
  368. G1.outcnt = 0;
  369. }
  370. /* ===========================================================================
  371. */
  372. /* put_8bit is used for the compressed output */
  373. #define put_8bit(c) \
  374. do { \
  375. G1.outbuf[G1.outcnt++] = (c); \
  376. if (G1.outcnt == OUTBUFSIZ) \
  377. flush_outbuf(); \
  378. } while (0)
  379. /* Output a 16 bit value, lsb first */
  380. static void put_16bit(ush w)
  381. {
  382. /* GCC 4.2.1 won't optimize out redundant loads of G1.outcnt
  383. * (probably because of fear of aliasing with G1.outbuf[]
  384. * stores), do it explicitly:
  385. */
  386. unsigned outcnt = G1.outcnt;
  387. uch *dst = &G1.outbuf[outcnt];
  388. #if BB_UNALIGNED_MEMACCESS_OK && BB_LITTLE_ENDIAN
  389. if (outcnt < OUTBUFSIZ-2) {
  390. /* Common case */
  391. ush *dst16 = (void*) dst;
  392. *dst16 = w; /* unaligned LSB 16-bit store */
  393. G1.outcnt = outcnt + 2;
  394. return;
  395. }
  396. *dst = (uch)w;
  397. w >>= 8;
  398. G1.outcnt = ++outcnt;
  399. #else
  400. *dst = (uch)w;
  401. w >>= 8;
  402. if (outcnt < OUTBUFSIZ-2) {
  403. /* Common case */
  404. dst[1] = w;
  405. G1.outcnt = outcnt + 2;
  406. return;
  407. }
  408. G1.outcnt = ++outcnt;
  409. #endif
  410. /* Slowpath: we will need to do flush_outbuf() */
  411. if (outcnt == OUTBUFSIZ)
  412. flush_outbuf(); /* here */
  413. put_8bit(w); /* or here */
  414. }
  415. #define OPTIMIZED_PUT_32BIT (CONFIG_GZIP_FAST > 0 && BB_UNALIGNED_MEMACCESS_OK && BB_LITTLE_ENDIAN)
  416. static void put_32bit(ulg n)
  417. {
  418. if (OPTIMIZED_PUT_32BIT) {
  419. unsigned outcnt = G1.outcnt;
  420. if (outcnt < OUTBUFSIZ-4) {
  421. /* Common case */
  422. ulg *dst32 = (void*) &G1.outbuf[outcnt];
  423. *dst32 = n; /* unaligned LSB 32-bit store */
  424. //bb_error_msg("%p", dst32); // store alignment debugging
  425. G1.outcnt = outcnt + 4;
  426. return;
  427. }
  428. }
  429. put_16bit(n);
  430. put_16bit(n >> 16);
  431. }
  432. static ALWAYS_INLINE void flush_outbuf_if_32bit_optimized(void)
  433. {
  434. /* If put_32bit() performs 32bit stores && it is used in send_bits() */
  435. if (OPTIMIZED_PUT_32BIT && BUF_SIZE > 16)
  436. flush_outbuf();
  437. }
  438. /* ===========================================================================
  439. * Run a set of bytes through the crc shift register. If s is a NULL
  440. * pointer, then initialize the crc shift register contents instead.
  441. * Return the current crc in either case.
  442. */
  443. static void updcrc(uch * s, unsigned n)
  444. {
  445. G1.crc = crc32_block_endian0(G1.crc, s, n, global_crc32_table /*G1.crc_32_tab*/);
  446. }
  447. /* ===========================================================================
  448. * Read a new buffer from the current input file, perform end-of-line
  449. * translation, and update the crc and input file size.
  450. * IN assertion: size >= 2 (for end-of-line translation)
  451. */
  452. static unsigned file_read(void *buf, unsigned size)
  453. {
  454. unsigned len;
  455. Assert(G1.insize == 0, "l_buf not empty");
  456. len = safe_read(ifd, buf, size);
  457. if (len == (unsigned)(-1) || len == 0)
  458. return len;
  459. updcrc(buf, len);
  460. G1.isize += len;
  461. return len;
  462. }
  463. /* ===========================================================================
  464. * Send a value on a given number of bits.
  465. * IN assertion: length <= 16 and value fits in length bits.
  466. */
  467. static void send_bits(unsigned value, unsigned length)
  468. {
  469. unsigned new_buf;
  470. #ifdef DEBUG
  471. Tracev((stderr, " l %2d v %4x ", length, value));
  472. Assert(length > 0 && length <= 15, "invalid length");
  473. DEBUG_bits_sent(+= length);
  474. #endif
  475. BUILD_BUG_ON(BUF_SIZE != 32 && BUF_SIZE != 16);
  476. new_buf = G1.bi_buf | (value << G1.bi_valid);
  477. /* NB: the above may sometimes do "<< 32" shift (undefined)
  478. * if check below is changed to "length > BUF_SIZE" instead of >= */
  479. length += G1.bi_valid;
  480. /* If bi_buf is full */
  481. if (length >= BUF_SIZE) {
  482. /* ...use (valid) bits from bi_buf and
  483. * (BUF_SIZE - bi_valid) bits from value,
  484. * leaving (width - (BUF_SIZE-bi_valid)) unused bits in value.
  485. */
  486. value >>= (BUF_SIZE - G1.bi_valid);
  487. if (BUF_SIZE == 32) {
  488. put_32bit(new_buf);
  489. } else { /* 16 */
  490. put_16bit(new_buf);
  491. }
  492. new_buf = value;
  493. length -= BUF_SIZE;
  494. }
  495. G1.bi_buf = new_buf;
  496. G1.bi_valid = length;
  497. }
  498. /* ===========================================================================
  499. * Reverse the first len bits of a code, using straightforward code (a faster
  500. * method would use a table)
  501. * IN assertion: 1 <= len <= 15
  502. */
  503. static unsigned bi_reverse(unsigned code, int len)
  504. {
  505. unsigned res = 0;
  506. while (1) {
  507. res |= code & 1;
  508. if (--len <= 0) return res;
  509. code >>= 1;
  510. res <<= 1;
  511. }
  512. }
  513. /* ===========================================================================
  514. * Write out any remaining bits in an incomplete byte.
  515. */
  516. static void bi_windup(void)
  517. {
  518. unsigned bits = G1.bi_buf;
  519. int cnt = G1.bi_valid;
  520. while (cnt > 0) {
  521. put_8bit(bits);
  522. bits >>= 8;
  523. cnt -= 8;
  524. }
  525. G1.bi_buf = 0;
  526. G1.bi_valid = 0;
  527. DEBUG_bits_sent(= (G1.bits_sent + 7) & ~7);
  528. }
  529. /* ===========================================================================
  530. * Copy a stored block to the zip file, storing first the length and its
  531. * one's complement if requested.
  532. */
  533. static void copy_block(char *buf, unsigned len, int header)
  534. {
  535. bi_windup(); /* align on byte boundary */
  536. if (header) {
  537. unsigned v = ((uint16_t)len) | ((~len) << 16);
  538. put_32bit(v);
  539. DEBUG_bits_sent(+= 2 * 16);
  540. }
  541. DEBUG_bits_sent(+= (ulg) len << 3);
  542. while (len--) {
  543. put_8bit(*buf++);
  544. }
  545. /* The above can 32-bit misalign outbuf */
  546. if (G1.outcnt & 3) /* syscalls are expensive, is it really misaligned? */
  547. flush_outbuf_if_32bit_optimized();
  548. }
  549. /* ===========================================================================
  550. * Fill the window when the lookahead becomes insufficient.
  551. * Updates strstart and lookahead, and sets eofile if end of input file.
  552. * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
  553. * OUT assertions: at least one byte has been read, or eofile is set;
  554. * file reads are performed for at least two bytes (required for the
  555. * translate_eol option).
  556. */
  557. static void fill_window(void)
  558. {
  559. unsigned n, m;
  560. unsigned more = WINDOW_SIZE - G1.lookahead - G1.strstart;
  561. /* Amount of free space at the end of the window. */
  562. /* If the window is almost full and there is insufficient lookahead,
  563. * move the upper half to the lower one to make room in the upper half.
  564. */
  565. if (more == (unsigned) -1) {
  566. /* Very unlikely, but possible on 16 bit machine if strstart == 0
  567. * and lookahead == 1 (input done one byte at time)
  568. */
  569. more--;
  570. } else if (G1.strstart >= WSIZE + MAX_DIST) {
  571. /* By the IN assertion, the window is not empty so we can't confuse
  572. * more == 0 with more == 64K on a 16 bit machine.
  573. */
  574. Assert(WINDOW_SIZE == 2 * WSIZE, "no sliding with BIG_MEM");
  575. memcpy(G1.window, G1.window + WSIZE, WSIZE);
  576. G1.match_start -= WSIZE;
  577. G1.strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */
  578. G1.block_start -= WSIZE;
  579. for (n = 0; n < HASH_SIZE; n++) {
  580. m = head[n];
  581. head[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0);
  582. }
  583. for (n = 0; n < WSIZE; n++) {
  584. m = G1.prev[n];
  585. G1.prev[n] = (Pos) (m >= WSIZE ? m - WSIZE : 0);
  586. /* If n is not on any hash chain, prev[n] is garbage but
  587. * its value will never be used.
  588. */
  589. }
  590. more += WSIZE;
  591. }
  592. /* At this point, more >= 2 */
  593. if (!G1.eofile) {
  594. n = file_read(G1.window + G1.strstart + G1.lookahead, more);
  595. if (n == 0 || n == (unsigned) -1) {
  596. G1.eofile = 1;
  597. } else {
  598. G1.lookahead += n;
  599. }
  600. }
  601. }
  602. /* Both users fill window with the same loop: */
  603. static void fill_window_if_needed(void)
  604. {
  605. while (G1.lookahead < MIN_LOOKAHEAD && !G1.eofile)
  606. fill_window();
  607. }
  608. /* ===========================================================================
  609. * Set match_start to the longest match starting at the given string and
  610. * return its length. Matches shorter or equal to prev_length are discarded,
  611. * in which case the result is equal to prev_length and match_start is
  612. * garbage.
  613. * IN assertions: cur_match is the head of the hash chain for the current
  614. * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  615. */
  616. /* For MSDOS, OS/2 and 386 Unix, an optimized version is in match.asm or
  617. * match.s. The code is functionally equivalent, so you can use the C version
  618. * if desired.
  619. */
  620. static int longest_match(IPos cur_match)
  621. {
  622. unsigned chain_length = max_chain_length; /* max hash chain length */
  623. uch *scan = G1.window + G1.strstart; /* current string */
  624. uch *match; /* matched string */
  625. int len; /* length of current match */
  626. int best_len = G1.prev_length; /* best match length so far */
  627. IPos limit = G1.strstart > (IPos) MAX_DIST ? G1.strstart - (IPos) MAX_DIST : 0;
  628. /* Stop when cur_match becomes <= limit. To simplify the code,
  629. * we prevent matches with the string of window index 0.
  630. */
  631. /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
  632. * It is easy to get rid of this optimization if necessary.
  633. */
  634. #if HASH_BITS < 8 || MAX_MATCH != 258
  635. # error Code too clever
  636. #endif
  637. uch *strend = G1.window + G1.strstart + MAX_MATCH;
  638. uch scan_end1 = scan[best_len - 1];
  639. uch scan_end = scan[best_len];
  640. /* Do not waste too much time if we already have a good match: */
  641. if (G1.prev_length >= good_match) {
  642. chain_length >>= 2;
  643. }
  644. Assert(G1.strstart <= WINDOW_SIZE - MIN_LOOKAHEAD, "insufficient lookahead");
  645. do {
  646. Assert(cur_match < G1.strstart, "no future");
  647. match = G1.window + cur_match;
  648. /* Skip to next match if the match length cannot increase
  649. * or if the match length is less than 2:
  650. */
  651. if (match[best_len] != scan_end
  652. || match[best_len - 1] != scan_end1
  653. || *match != *scan || *++match != scan[1]
  654. ) {
  655. continue;
  656. }
  657. /* The check at best_len-1 can be removed because it will be made
  658. * again later. (This heuristic is not always a win.)
  659. * It is not necessary to compare scan[2] and match[2] since they
  660. * are always equal when the other bytes match, given that
  661. * the hash keys are equal and that HASH_BITS >= 8.
  662. */
  663. scan += 2, match++;
  664. /* We check for insufficient lookahead only every 8th comparison;
  665. * the 256th check will be made at strstart+258.
  666. */
  667. do {
  668. } while (*++scan == *++match && *++scan == *++match &&
  669. *++scan == *++match && *++scan == *++match &&
  670. *++scan == *++match && *++scan == *++match &&
  671. *++scan == *++match && *++scan == *++match && scan < strend);
  672. len = MAX_MATCH - (int) (strend - scan);
  673. scan = strend - MAX_MATCH;
  674. if (len > best_len) {
  675. G1.match_start = cur_match;
  676. best_len = len;
  677. if (len >= nice_match)
  678. break;
  679. scan_end1 = scan[best_len - 1];
  680. scan_end = scan[best_len];
  681. }
  682. } while ((cur_match = G1.prev[cur_match & WMASK]) > limit
  683. && --chain_length != 0);
  684. return best_len;
  685. }
  686. #ifdef DEBUG
  687. /* ===========================================================================
  688. * Check that the match at match_start is indeed a match.
  689. */
  690. static void check_match(IPos start, IPos match, int length)
  691. {
  692. /* check that the match is indeed a match */
  693. if (memcmp(G1.window + match, G1.window + start, length) != 0) {
  694. bb_error_msg(" start %d, match %d, length %d", start, match, length);
  695. bb_error_msg("invalid match");
  696. }
  697. if (verbose > 1) {
  698. bb_error_msg("\\[%d,%d]", start - match, length);
  699. do {
  700. bb_putchar_stderr(G1.window[start++]);
  701. } while (--length != 0);
  702. }
  703. }
  704. #else
  705. # define check_match(start, match, length) ((void)0)
  706. #endif
  707. /* trees.c -- output deflated data using Huffman coding
  708. * Copyright (C) 1992-1993 Jean-loup Gailly
  709. * This is free software; you can redistribute it and/or modify it under the
  710. * terms of the GNU General Public License, see the file COPYING.
  711. */
  712. /* PURPOSE
  713. * Encode various sets of source values using variable-length
  714. * binary code trees.
  715. *
  716. * DISCUSSION
  717. * The PKZIP "deflation" process uses several Huffman trees. The more
  718. * common source values are represented by shorter bit sequences.
  719. *
  720. * Each code tree is stored in the ZIP file in a compressed form
  721. * which is itself a Huffman encoding of the lengths of
  722. * all the code strings (in ascending order by source values).
  723. * The actual code strings are reconstructed from the lengths in
  724. * the UNZIP process, as described in the "application note"
  725. * (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
  726. *
  727. * REFERENCES
  728. * Lynch, Thomas J.
  729. * Data Compression: Techniques and Applications, pp. 53-55.
  730. * Lifetime Learning Publications, 1985. ISBN 0-534-03418-7.
  731. *
  732. * Storer, James A.
  733. * Data Compression: Methods and Theory, pp. 49-50.
  734. * Computer Science Press, 1988. ISBN 0-7167-8156-5.
  735. *
  736. * Sedgewick, R.
  737. * Algorithms, p290.
  738. * Addison-Wesley, 1983. ISBN 0-201-06672-6.
  739. *
  740. * INTERFACE
  741. * void ct_init()
  742. * Allocate the match buffer, initialize the various tables [and save
  743. * the location of the internal file attribute (ascii/binary) and
  744. * method (DEFLATE/STORE) -- deleted in bbox]
  745. *
  746. * void ct_tally(int dist, int lc);
  747. * Save the match info and tally the frequency counts.
  748. *
  749. * ulg flush_block(char *buf, ulg stored_len, int eof)
  750. * Determine the best encoding for the current block: dynamic trees,
  751. * static trees or store, and output the encoded block to the zip
  752. * file. Returns the total compressed length for the file so far.
  753. */
  754. #define MAX_BITS 15
  755. /* All codes must not exceed MAX_BITS bits */
  756. #define MAX_BL_BITS 7
  757. /* Bit length codes must not exceed MAX_BL_BITS bits */
  758. #define LENGTH_CODES 29
  759. /* number of length codes, not counting the special END_BLOCK code */
  760. #define LITERALS 256
  761. /* number of literal bytes 0..255 */
  762. #define END_BLOCK 256
  763. /* end of block literal code */
  764. #define L_CODES (LITERALS+1+LENGTH_CODES)
  765. /* number of Literal or Length codes, including the END_BLOCK code */
  766. #define D_CODES 30
  767. /* number of distance codes */
  768. #define BL_CODES 19
  769. /* number of codes used to transfer the bit lengths */
  770. /* extra bits for each length code */
  771. static const uint8_t extra_lbits[LENGTH_CODES] ALIGN1 = {
  772. 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4,
  773. 4, 4, 5, 5, 5, 5, 0
  774. };
  775. /* extra bits for each distance code */
  776. static const uint8_t extra_dbits[D_CODES] ALIGN1 = {
  777. 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9,
  778. 10, 10, 11, 11, 12, 12, 13, 13
  779. };
  780. /* extra bits for each bit length code */
  781. static const uint8_t extra_blbits[BL_CODES] ALIGN1 = {
  782. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 };
  783. /* number of codes at each bit length for an optimal tree */
  784. static const uint8_t bl_order[BL_CODES] ALIGN1 = {
  785. 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
  786. #define STORED_BLOCK 0
  787. #define STATIC_TREES 1
  788. #define DYN_TREES 2
  789. /* The three kinds of block type */
  790. #ifndef LIT_BUFSIZE
  791. # ifdef SMALL_MEM
  792. # define LIT_BUFSIZE 0x2000
  793. # else
  794. # ifdef MEDIUM_MEM
  795. # define LIT_BUFSIZE 0x4000
  796. # else
  797. # define LIT_BUFSIZE 0x8000
  798. # endif
  799. # endif
  800. #endif
  801. #ifndef DIST_BUFSIZE
  802. # define DIST_BUFSIZE LIT_BUFSIZE
  803. #endif
  804. /* Sizes of match buffers for literals/lengths and distances. There are
  805. * 4 reasons for limiting LIT_BUFSIZE to 64K:
  806. * - frequencies can be kept in 16 bit counters
  807. * - if compression is not successful for the first block, all input data is
  808. * still in the window so we can still emit a stored block even when input
  809. * comes from standard input. (This can also be done for all blocks if
  810. * LIT_BUFSIZE is not greater than 32K.)
  811. * - if compression is not successful for a file smaller than 64K, we can
  812. * even emit a stored file instead of a stored block (saving 5 bytes).
  813. * - creating new Huffman trees less frequently may not provide fast
  814. * adaptation to changes in the input data statistics. (Take for
  815. * example a binary file with poorly compressible code followed by
  816. * a highly compressible string table.) Smaller buffer sizes give
  817. * fast adaptation but have of course the overhead of transmitting trees
  818. * more frequently.
  819. * - I can't count above 4
  820. * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
  821. * memory at the expense of compression). Some optimizations would be possible
  822. * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
  823. */
  824. #define REP_3_6 16
  825. /* repeat previous bit length 3-6 times (2 bits of repeat count) */
  826. #define REPZ_3_10 17
  827. /* repeat a zero length 3-10 times (3 bits of repeat count) */
  828. #define REPZ_11_138 18
  829. /* repeat a zero length 11-138 times (7 bits of repeat count) */
  830. /* ===========================================================================
  831. */
  832. /* Data structure describing a single value and its code string. */
  833. typedef struct ct_data {
  834. union {
  835. ush freq; /* frequency count */
  836. ush code; /* bit string */
  837. } fc;
  838. union {
  839. ush dad; /* father node in Huffman tree */
  840. ush len; /* length of bit string */
  841. } dl;
  842. } ct_data;
  843. #define Freq fc.freq
  844. #define Code fc.code
  845. #define Dad dl.dad
  846. #define Len dl.len
  847. #define HEAP_SIZE (2*L_CODES + 1)
  848. /* maximum heap size */
  849. typedef struct tree_desc {
  850. ct_data *dyn_tree; /* the dynamic tree */
  851. ct_data *static_tree; /* corresponding static tree or NULL */
  852. const uint8_t *extra_bits; /* extra bits for each code or NULL */
  853. int extra_base; /* base index for extra_bits */
  854. int elems; /* max number of elements in the tree */
  855. int max_length; /* max bit length for the codes */
  856. int max_code; /* largest code with non zero frequency */
  857. } tree_desc;
  858. struct globals2 {
  859. ush heap[HEAP_SIZE]; /* heap used to build the Huffman trees */
  860. int heap_len; /* number of elements in the heap */
  861. int heap_max; /* element of largest frequency */
  862. /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  863. * The same heap array is used to build all trees.
  864. */
  865. ct_data dyn_ltree[HEAP_SIZE]; /* literal and length tree */
  866. ct_data dyn_dtree[2 * D_CODES + 1]; /* distance tree */
  867. ct_data static_ltree[L_CODES + 2];
  868. /* The static literal tree. Since the bit lengths are imposed, there is no
  869. * need for the L_CODES extra codes used during heap construction. However
  870. * The codes 286 and 287 are needed to build a canonical tree (see ct_init
  871. * below).
  872. */
  873. ct_data static_dtree[D_CODES];
  874. /* The static distance tree. (Actually a trivial tree since all codes use
  875. * 5 bits.)
  876. */
  877. ct_data bl_tree[2 * BL_CODES + 1];
  878. /* Huffman tree for the bit lengths */
  879. tree_desc l_desc;
  880. tree_desc d_desc;
  881. tree_desc bl_desc;
  882. ush bl_count[MAX_BITS + 1];
  883. /* The lengths of the bit length codes are sent in order of decreasing
  884. * probability, to avoid transmitting the lengths for unused bit length codes.
  885. */
  886. uch depth[2 * L_CODES + 1];
  887. /* Depth of each subtree used as tie breaker for trees of equal frequency */
  888. uch length_code[MAX_MATCH - MIN_MATCH + 1];
  889. /* length code for each normalized match length (0 == MIN_MATCH) */
  890. uch dist_code[512];
  891. /* distance codes. The first 256 values correspond to the distances
  892. * 3 .. 258, the last 256 values correspond to the top 8 bits of
  893. * the 15 bit distances.
  894. */
  895. int base_length[LENGTH_CODES];
  896. /* First normalized length for each code (0 = MIN_MATCH) */
  897. int base_dist[D_CODES];
  898. /* First normalized distance for each code (0 = distance of 1) */
  899. uch flag_buf[LIT_BUFSIZE / 8];
  900. /* flag_buf is a bit array distinguishing literals from lengths in
  901. * l_buf, thus indicating the presence or absence of a distance.
  902. */
  903. unsigned last_lit; /* running index in l_buf */
  904. unsigned last_dist; /* running index in d_buf */
  905. unsigned last_flags; /* running index in flag_buf */
  906. uch flags; /* current flags not yet saved in flag_buf */
  907. uch flag_bit; /* current bit used in flags */
  908. /* bits are filled in flags starting at bit 0 (least significant).
  909. * Note: these flags are overkill in the current code since we don't
  910. * take advantage of DIST_BUFSIZE == LIT_BUFSIZE.
  911. */
  912. ulg opt_len; /* bit length of current block with optimal trees */
  913. ulg static_len; /* bit length of current block with static trees */
  914. // ulg compressed_len; /* total bit length of compressed file */
  915. };
  916. #define G2ptr ((struct globals2*)(ptr_to_globals))
  917. #define G2 (*G2ptr)
  918. /* ===========================================================================
  919. */
  920. #ifndef DEBUG
  921. /* Send a code of the given tree. c and tree must not have side effects */
  922. # define SEND_CODE(c, tree) send_bits(tree[c].Code, tree[c].Len)
  923. #else
  924. # define SEND_CODE(c, tree) \
  925. { \
  926. if (verbose > 1) bb_error_msg("\ncd %3d ", (c)); \
  927. send_bits(tree[c].Code, tree[c].Len); \
  928. }
  929. #endif
  930. #define D_CODE(dist) \
  931. ((dist) < 256 ? G2.dist_code[dist] : G2.dist_code[256 + ((dist)>>7)])
  932. /* Mapping from a distance to a distance code. dist is the distance - 1 and
  933. * must not have side effects. dist_code[256] and dist_code[257] are never
  934. * used.
  935. * The arguments must not have side effects.
  936. */
  937. /* ===========================================================================
  938. * Initialize a new block.
  939. */
  940. static void init_block(void)
  941. {
  942. int n; /* iterates over tree elements */
  943. /* Initialize the trees. */
  944. for (n = 0; n < L_CODES; n++)
  945. G2.dyn_ltree[n].Freq = 0;
  946. for (n = 0; n < D_CODES; n++)
  947. G2.dyn_dtree[n].Freq = 0;
  948. for (n = 0; n < BL_CODES; n++)
  949. G2.bl_tree[n].Freq = 0;
  950. G2.dyn_ltree[END_BLOCK].Freq = 1;
  951. G2.opt_len = G2.static_len = 0;
  952. G2.last_lit = G2.last_dist = G2.last_flags = 0;
  953. G2.flags = 0;
  954. G2.flag_bit = 1;
  955. }
  956. /* ===========================================================================
  957. * Restore the heap property by moving down the tree starting at node k,
  958. * exchanging a node with the smallest of its two sons if necessary, stopping
  959. * when the heap property is re-established (each father smaller than its
  960. * two sons).
  961. */
  962. /* Compares to subtrees, using the tree depth as tie breaker when
  963. * the subtrees have equal frequency. This minimizes the worst case length. */
  964. #define SMALLER(tree, n, m) \
  965. (tree[n].Freq < tree[m].Freq \
  966. || (tree[n].Freq == tree[m].Freq && G2.depth[n] <= G2.depth[m]))
  967. static void pqdownheap(ct_data * tree, int k)
  968. {
  969. int v = G2.heap[k];
  970. int j = k << 1; /* left son of k */
  971. while (j <= G2.heap_len) {
  972. /* Set j to the smallest of the two sons: */
  973. if (j < G2.heap_len && SMALLER(tree, G2.heap[j + 1], G2.heap[j]))
  974. j++;
  975. /* Exit if v is smaller than both sons */
  976. if (SMALLER(tree, v, G2.heap[j]))
  977. break;
  978. /* Exchange v with the smallest son */
  979. G2.heap[k] = G2.heap[j];
  980. k = j;
  981. /* And continue down the tree, setting j to the left son of k */
  982. j <<= 1;
  983. }
  984. G2.heap[k] = v;
  985. }
  986. /* ===========================================================================
  987. * Compute the optimal bit lengths for a tree and update the total bit length
  988. * for the current block.
  989. * IN assertion: the fields freq and dad are set, heap[heap_max] and
  990. * above are the tree nodes sorted by increasing frequency.
  991. * OUT assertions: the field len is set to the optimal bit length, the
  992. * array bl_count contains the frequencies for each bit length.
  993. * The length opt_len is updated; static_len is also updated if stree is
  994. * not null.
  995. */
  996. static void gen_bitlen(tree_desc * desc)
  997. {
  998. ct_data *tree = desc->dyn_tree;
  999. const uint8_t *extra = desc->extra_bits;
  1000. int base = desc->extra_base;
  1001. int max_code = desc->max_code;
  1002. int max_length = desc->max_length;
  1003. ct_data *stree = desc->static_tree;
  1004. int h; /* heap index */
  1005. int n, m; /* iterate over the tree elements */
  1006. int bits; /* bit length */
  1007. int xbits; /* extra bits */
  1008. ush f; /* frequency */
  1009. int overflow = 0; /* number of elements with bit length too large */
  1010. for (bits = 0; bits <= MAX_BITS; bits++)
  1011. G2.bl_count[bits] = 0;
  1012. /* In a first pass, compute the optimal bit lengths (which may
  1013. * overflow in the case of the bit length tree).
  1014. */
  1015. tree[G2.heap[G2.heap_max]].Len = 0; /* root of the heap */
  1016. for (h = G2.heap_max + 1; h < HEAP_SIZE; h++) {
  1017. n = G2.heap[h];
  1018. bits = tree[tree[n].Dad].Len + 1;
  1019. if (bits > max_length) {
  1020. bits = max_length;
  1021. overflow++;
  1022. }
  1023. tree[n].Len = (ush) bits;
  1024. /* We overwrite tree[n].Dad which is no longer needed */
  1025. if (n > max_code)
  1026. continue; /* not a leaf node */
  1027. G2.bl_count[bits]++;
  1028. xbits = 0;
  1029. if (n >= base)
  1030. xbits = extra[n - base];
  1031. f = tree[n].Freq;
  1032. G2.opt_len += (ulg) f *(bits + xbits);
  1033. if (stree)
  1034. G2.static_len += (ulg) f * (stree[n].Len + xbits);
  1035. }
  1036. if (overflow == 0)
  1037. return;
  1038. Trace((stderr, "\nbit length overflow\n"));
  1039. /* This happens for example on obj2 and pic of the Calgary corpus */
  1040. /* Find the first bit length which could increase: */
  1041. do {
  1042. bits = max_length - 1;
  1043. while (G2.bl_count[bits] == 0)
  1044. bits--;
  1045. G2.bl_count[bits]--; /* move one leaf down the tree */
  1046. G2.bl_count[bits + 1] += 2; /* move one overflow item as its brother */
  1047. G2.bl_count[max_length]--;
  1048. /* The brother of the overflow item also moves one step up,
  1049. * but this does not affect bl_count[max_length]
  1050. */
  1051. overflow -= 2;
  1052. } while (overflow > 0);
  1053. /* Now recompute all bit lengths, scanning in increasing frequency.
  1054. * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
  1055. * lengths instead of fixing only the wrong ones. This idea is taken
  1056. * from 'ar' written by Haruhiko Okumura.)
  1057. */
  1058. for (bits = max_length; bits != 0; bits--) {
  1059. n = G2.bl_count[bits];
  1060. while (n != 0) {
  1061. m = G2.heap[--h];
  1062. if (m > max_code)
  1063. continue;
  1064. if (tree[m].Len != (unsigned) bits) {
  1065. Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len, bits));
  1066. G2.opt_len += ((int32_t) bits - tree[m].Len) * tree[m].Freq;
  1067. tree[m].Len = bits;
  1068. }
  1069. n--;
  1070. }
  1071. }
  1072. }
  1073. /* ===========================================================================
  1074. * Generate the codes for a given tree and bit counts (which need not be
  1075. * optimal).
  1076. * IN assertion: the array bl_count contains the bit length statistics for
  1077. * the given tree and the field len is set for all tree elements.
  1078. * OUT assertion: the field code is set for all tree elements of non
  1079. * zero code length.
  1080. */
  1081. static void gen_codes(ct_data * tree, int max_code)
  1082. {
  1083. ush next_code[MAX_BITS + 1]; /* next code value for each bit length */
  1084. ush code = 0; /* running code value */
  1085. int bits; /* bit index */
  1086. int n; /* code index */
  1087. /* The distribution counts are first used to generate the code values
  1088. * without bit reversal.
  1089. */
  1090. for (bits = 1; bits <= MAX_BITS; bits++) {
  1091. next_code[bits] = code = (code + G2.bl_count[bits - 1]) << 1;
  1092. }
  1093. /* Check that the bit counts in bl_count are consistent. The last code
  1094. * must be all ones.
  1095. */
  1096. Assert(code + G2.bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1,
  1097. "inconsistent bit counts");
  1098. Tracev((stderr, "\ngen_codes: max_code %d ", max_code));
  1099. for (n = 0; n <= max_code; n++) {
  1100. int len = tree[n].Len;
  1101. if (len == 0)
  1102. continue;
  1103. /* Now reverse the bits */
  1104. tree[n].Code = bi_reverse(next_code[len]++, len);
  1105. Tracec(tree != G2.static_ltree,
  1106. (stderr, "\nn %3d %c l %2d c %4x (%x) ", n,
  1107. (n > ' ' ? n : ' '), len, tree[n].Code,
  1108. next_code[len] - 1));
  1109. }
  1110. }
  1111. /* ===========================================================================
  1112. * Construct one Huffman tree and assigns the code bit strings and lengths.
  1113. * Update the total bit length for the current block.
  1114. * IN assertion: the field freq is set for all tree elements.
  1115. * OUT assertions: the fields len and code are set to the optimal bit length
  1116. * and corresponding code. The length opt_len is updated; static_len is
  1117. * also updated if stree is not null. The field max_code is set.
  1118. */
  1119. /* Remove the smallest element from the heap and recreate the heap with
  1120. * one less element. Updates heap and heap_len. */
  1121. #define SMALLEST 1
  1122. /* Index within the heap array of least frequent node in the Huffman tree */
  1123. #define PQREMOVE(tree, top) \
  1124. do { \
  1125. top = G2.heap[SMALLEST]; \
  1126. G2.heap[SMALLEST] = G2.heap[G2.heap_len--]; \
  1127. pqdownheap(tree, SMALLEST); \
  1128. } while (0)
  1129. static void build_tree(tree_desc * desc)
  1130. {
  1131. ct_data *tree = desc->dyn_tree;
  1132. ct_data *stree = desc->static_tree;
  1133. int elems = desc->elems;
  1134. int n, m; /* iterate over heap elements */
  1135. int max_code = -1; /* largest code with non zero frequency */
  1136. int node = elems; /* next internal node of the tree */
  1137. /* Construct the initial heap, with least frequent element in
  1138. * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
  1139. * heap[0] is not used.
  1140. */
  1141. G2.heap_len = 0;
  1142. G2.heap_max = HEAP_SIZE;
  1143. for (n = 0; n < elems; n++) {
  1144. if (tree[n].Freq != 0) {
  1145. G2.heap[++G2.heap_len] = max_code = n;
  1146. G2.depth[n] = 0;
  1147. } else {
  1148. tree[n].Len = 0;
  1149. }
  1150. }
  1151. /* The pkzip format requires that at least one distance code exists,
  1152. * and that at least one bit should be sent even if there is only one
  1153. * possible code. So to avoid special checks later on we force at least
  1154. * two codes of non zero frequency.
  1155. */
  1156. while (G2.heap_len < 2) {
  1157. int new = G2.heap[++G2.heap_len] = (max_code < 2 ? ++max_code : 0);
  1158. tree[new].Freq = 1;
  1159. G2.depth[new] = 0;
  1160. G2.opt_len--;
  1161. if (stree)
  1162. G2.static_len -= stree[new].Len;
  1163. /* new is 0 or 1 so it does not have extra bits */
  1164. }
  1165. desc->max_code = max_code;
  1166. /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
  1167. * establish sub-heaps of increasing lengths:
  1168. */
  1169. for (n = G2.heap_len / 2; n >= 1; n--)
  1170. pqdownheap(tree, n);
  1171. /* Construct the Huffman tree by repeatedly combining the least two
  1172. * frequent nodes.
  1173. */
  1174. do {
  1175. PQREMOVE(tree, n); /* n = node of least frequency */
  1176. m = G2.heap[SMALLEST]; /* m = node of next least frequency */
  1177. G2.heap[--G2.heap_max] = n; /* keep the nodes sorted by frequency */
  1178. G2.heap[--G2.heap_max] = m;
  1179. /* Create a new node father of n and m */
  1180. tree[node].Freq = tree[n].Freq + tree[m].Freq;
  1181. G2.depth[node] = MAX(G2.depth[n], G2.depth[m]) + 1;
  1182. tree[n].Dad = tree[m].Dad = (ush) node;
  1183. #ifdef DUMP_BL_TREE
  1184. if (tree == G2.bl_tree) {
  1185. bb_error_msg("\nnode %d(%d), sons %d(%d) %d(%d)",
  1186. node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
  1187. }
  1188. #endif
  1189. /* and insert the new node in the heap */
  1190. G2.heap[SMALLEST] = node++;
  1191. pqdownheap(tree, SMALLEST);
  1192. } while (G2.heap_len >= 2);
  1193. G2.heap[--G2.heap_max] = G2.heap[SMALLEST];
  1194. /* At this point, the fields freq and dad are set. We can now
  1195. * generate the bit lengths.
  1196. */
  1197. gen_bitlen((tree_desc *) desc);
  1198. /* The field len is now set, we can generate the bit codes */
  1199. gen_codes((ct_data *) tree, max_code);
  1200. }
  1201. /* ===========================================================================
  1202. * Scan a literal or distance tree to determine the frequencies of the codes
  1203. * in the bit length tree. Updates opt_len to take into account the repeat
  1204. * counts. (The contribution of the bit length codes will be added later
  1205. * during the construction of bl_tree.)
  1206. */
  1207. static void scan_tree(ct_data * tree, int max_code)
  1208. {
  1209. int n; /* iterates over all tree elements */
  1210. int prevlen = -1; /* last emitted length */
  1211. int curlen; /* length of current code */
  1212. int nextlen = tree[0].Len; /* length of next code */
  1213. int count = 0; /* repeat count of the current code */
  1214. int max_count = 7; /* max repeat count */
  1215. int min_count = 4; /* min repeat count */
  1216. if (nextlen == 0) {
  1217. max_count = 138;
  1218. min_count = 3;
  1219. }
  1220. tree[max_code + 1].Len = 0xffff; /* guard */
  1221. for (n = 0; n <= max_code; n++) {
  1222. curlen = nextlen;
  1223. nextlen = tree[n + 1].Len;
  1224. if (++count < max_count && curlen == nextlen)
  1225. continue;
  1226. if (count < min_count) {
  1227. G2.bl_tree[curlen].Freq += count;
  1228. } else if (curlen != 0) {
  1229. if (curlen != prevlen)
  1230. G2.bl_tree[curlen].Freq++;
  1231. G2.bl_tree[REP_3_6].Freq++;
  1232. } else if (count <= 10) {
  1233. G2.bl_tree[REPZ_3_10].Freq++;
  1234. } else {
  1235. G2.bl_tree[REPZ_11_138].Freq++;
  1236. }
  1237. count = 0;
  1238. prevlen = curlen;
  1239. max_count = 7;
  1240. min_count = 4;
  1241. if (nextlen == 0) {
  1242. max_count = 138;
  1243. min_count = 3;
  1244. } else if (curlen == nextlen) {
  1245. max_count = 6;
  1246. min_count = 3;
  1247. }
  1248. }
  1249. }
  1250. /* ===========================================================================
  1251. * Send a literal or distance tree in compressed form, using the codes in
  1252. * bl_tree.
  1253. */
  1254. static void send_tree(ct_data * tree, int max_code)
  1255. {
  1256. int n; /* iterates over all tree elements */
  1257. int prevlen = -1; /* last emitted length */
  1258. int curlen; /* length of current code */
  1259. int nextlen = tree[0].Len; /* length of next code */
  1260. int count = 0; /* repeat count of the current code */
  1261. int max_count = 7; /* max repeat count */
  1262. int min_count = 4; /* min repeat count */
  1263. /* tree[max_code+1].Len = -1; *//* guard already set */
  1264. if (nextlen == 0)
  1265. max_count = 138, min_count = 3;
  1266. for (n = 0; n <= max_code; n++) {
  1267. curlen = nextlen;
  1268. nextlen = tree[n + 1].Len;
  1269. if (++count < max_count && curlen == nextlen) {
  1270. continue;
  1271. } else if (count < min_count) {
  1272. do {
  1273. SEND_CODE(curlen, G2.bl_tree);
  1274. } while (--count);
  1275. } else if (curlen != 0) {
  1276. if (curlen != prevlen) {
  1277. SEND_CODE(curlen, G2.bl_tree);
  1278. count--;
  1279. }
  1280. Assert(count >= 3 && count <= 6, " 3_6?");
  1281. SEND_CODE(REP_3_6, G2.bl_tree);
  1282. send_bits(count - 3, 2);
  1283. } else if (count <= 10) {
  1284. SEND_CODE(REPZ_3_10, G2.bl_tree);
  1285. send_bits(count - 3, 3);
  1286. } else {
  1287. SEND_CODE(REPZ_11_138, G2.bl_tree);
  1288. send_bits(count - 11, 7);
  1289. }
  1290. count = 0;
  1291. prevlen = curlen;
  1292. if (nextlen == 0) {
  1293. max_count = 138;
  1294. min_count = 3;
  1295. } else if (curlen == nextlen) {
  1296. max_count = 6;
  1297. min_count = 3;
  1298. } else {
  1299. max_count = 7;
  1300. min_count = 4;
  1301. }
  1302. }
  1303. }
  1304. /* ===========================================================================
  1305. * Construct the Huffman tree for the bit lengths and return the index in
  1306. * bl_order of the last bit length code to send.
  1307. */
  1308. static int build_bl_tree(void)
  1309. {
  1310. int max_blindex; /* index of last bit length code of non zero freq */
  1311. /* Determine the bit length frequencies for literal and distance trees */
  1312. scan_tree(G2.dyn_ltree, G2.l_desc.max_code);
  1313. scan_tree(G2.dyn_dtree, G2.d_desc.max_code);
  1314. /* Build the bit length tree: */
  1315. build_tree(&G2.bl_desc);
  1316. /* opt_len now includes the length of the tree representations, except
  1317. * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
  1318. */
  1319. /* Determine the number of bit length codes to send. The pkzip format
  1320. * requires that at least 4 bit length codes be sent. (appnote.txt says
  1321. * 3 but the actual value used is 4.)
  1322. */
  1323. for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) {
  1324. if (G2.bl_tree[bl_order[max_blindex]].Len != 0)
  1325. break;
  1326. }
  1327. /* Update opt_len to include the bit length tree and counts */
  1328. G2.opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;
  1329. Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", (long)G2.opt_len, (long)G2.static_len));
  1330. return max_blindex;
  1331. }
  1332. /* ===========================================================================
  1333. * Send the header for a block using dynamic Huffman trees: the counts, the
  1334. * lengths of the bit length codes, the literal tree and the distance tree.
  1335. * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
  1336. */
  1337. static void send_all_trees(int lcodes, int dcodes, int blcodes)
  1338. {
  1339. int rank; /* index in bl_order */
  1340. Assert(lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
  1341. Assert(lcodes <= L_CODES && dcodes <= D_CODES
  1342. && blcodes <= BL_CODES, "too many codes");
  1343. Tracev((stderr, "\nbl counts: "));
  1344. send_bits(lcodes - 257, 5); /* not +255 as stated in appnote.txt */
  1345. send_bits(dcodes - 1, 5);
  1346. send_bits(blcodes - 4, 4); /* not -3 as stated in appnote.txt */
  1347. for (rank = 0; rank < blcodes; rank++) {
  1348. Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
  1349. send_bits(G2.bl_tree[bl_order[rank]].Len, 3);
  1350. }
  1351. Tracev((stderr, "\nbl tree: sent %ld", (long)G1.bits_sent));
  1352. send_tree((ct_data *) G2.dyn_ltree, lcodes - 1); /* send the literal tree */
  1353. Tracev((stderr, "\nlit tree: sent %ld", (long)G1.bits_sent));
  1354. send_tree((ct_data *) G2.dyn_dtree, dcodes - 1); /* send the distance tree */
  1355. Tracev((stderr, "\ndist tree: sent %ld", (long)G1.bits_sent));
  1356. }
  1357. /* ===========================================================================
  1358. * Save the match info and tally the frequency counts. Return true if
  1359. * the current block must be flushed.
  1360. */
  1361. static int ct_tally(int dist, int lc)
  1362. {
  1363. G1.l_buf[G2.last_lit++] = lc;
  1364. if (dist == 0) {
  1365. /* lc is the unmatched char */
  1366. G2.dyn_ltree[lc].Freq++;
  1367. } else {
  1368. /* Here, lc is the match length - MIN_MATCH */
  1369. dist--; /* dist = match distance - 1 */
  1370. Assert((ush) dist < (ush) MAX_DIST
  1371. && (ush) lc <= (ush) (MAX_MATCH - MIN_MATCH)
  1372. && (ush) D_CODE(dist) < (ush) D_CODES, "ct_tally: bad match"
  1373. );
  1374. G2.dyn_ltree[G2.length_code[lc] + LITERALS + 1].Freq++;
  1375. G2.dyn_dtree[D_CODE(dist)].Freq++;
  1376. G1.d_buf[G2.last_dist++] = dist;
  1377. G2.flags |= G2.flag_bit;
  1378. }
  1379. G2.flag_bit <<= 1;
  1380. /* Output the flags if they fill a byte: */
  1381. if ((G2.last_lit & 7) == 0) {
  1382. G2.flag_buf[G2.last_flags++] = G2.flags;
  1383. G2.flags = 0;
  1384. G2.flag_bit = 1;
  1385. }
  1386. /* Try to guess if it is profitable to stop the current block here */
  1387. if ((G2.last_lit & 0xfff) == 0) {
  1388. /* Compute an upper bound for the compressed length */
  1389. ulg out_length = G2.last_lit * 8L;
  1390. ulg in_length = (ulg) G1.strstart - G1.block_start;
  1391. int dcode;
  1392. for (dcode = 0; dcode < D_CODES; dcode++) {
  1393. out_length += G2.dyn_dtree[dcode].Freq * (5L + extra_dbits[dcode]);
  1394. }
  1395. out_length >>= 3;
  1396. Trace((stderr,
  1397. "\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
  1398. G2.last_lit, G2.last_dist,
  1399. (long)in_length, (long)out_length,
  1400. 100L - out_length * 100L / in_length));
  1401. if (G2.last_dist < G2.last_lit / 2 && out_length < in_length / 2)
  1402. return 1;
  1403. }
  1404. return (G2.last_lit == LIT_BUFSIZE - 1 || G2.last_dist == DIST_BUFSIZE);
  1405. /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
  1406. * on 16 bit machines and because stored blocks are restricted to
  1407. * 64K-1 bytes.
  1408. */
  1409. }
  1410. /* ===========================================================================
  1411. * Send the block data compressed using the given Huffman trees
  1412. */
  1413. static void compress_block(ct_data * ltree, ct_data * dtree)
  1414. {
  1415. unsigned dist; /* distance of matched string */
  1416. int lc; /* match length or unmatched char (if dist == 0) */
  1417. unsigned lx = 0; /* running index in l_buf */
  1418. unsigned dx = 0; /* running index in d_buf */
  1419. unsigned fx = 0; /* running index in flag_buf */
  1420. uch flag = 0; /* current flags */
  1421. unsigned code; /* the code to send */
  1422. int extra; /* number of extra bits to send */
  1423. if (G2.last_lit != 0) do {
  1424. if ((lx & 7) == 0)
  1425. flag = G2.flag_buf[fx++];
  1426. lc = G1.l_buf[lx++];
  1427. if ((flag & 1) == 0) {
  1428. SEND_CODE(lc, ltree); /* send a literal byte */
  1429. Tracecv(lc > ' ', (stderr, " '%c' ", lc));
  1430. } else {
  1431. /* Here, lc is the match length - MIN_MATCH */
  1432. code = G2.length_code[lc];
  1433. SEND_CODE(code + LITERALS + 1, ltree); /* send the length code */
  1434. extra = extra_lbits[code];
  1435. if (extra != 0) {
  1436. lc -= G2.base_length[code];
  1437. send_bits(lc, extra); /* send the extra length bits */
  1438. }
  1439. dist = G1.d_buf[dx++];
  1440. /* Here, dist is the match distance - 1 */
  1441. code = D_CODE(dist);
  1442. Assert(code < D_CODES, "bad d_code");
  1443. SEND_CODE(code, dtree); /* send the distance code */
  1444. extra = extra_dbits[code];
  1445. if (extra != 0) {
  1446. dist -= G2.base_dist[code];
  1447. send_bits(dist, extra); /* send the extra distance bits */
  1448. }
  1449. } /* literal or match pair ? */
  1450. flag >>= 1;
  1451. } while (lx < G2.last_lit);
  1452. SEND_CODE(END_BLOCK, ltree);
  1453. }
  1454. /* ===========================================================================
  1455. * Determine the best encoding for the current block: dynamic trees, static
  1456. * trees or store, and output the encoded block to the zip file. This function
  1457. * returns the total compressed length for the file so far.
  1458. */
  1459. static void flush_block(char *buf, ulg stored_len, int eof)
  1460. {
  1461. ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
  1462. int max_blindex; /* index of last bit length code of non zero freq */
  1463. G2.flag_buf[G2.last_flags] = G2.flags; /* Save the flags for the last 8 items */
  1464. /* Construct the literal and distance trees */
  1465. build_tree(&G2.l_desc);
  1466. Tracev((stderr, "\nlit data: dyn %ld, stat %ld", (long)G2.opt_len, (long)G2.static_len));
  1467. build_tree(&G2.d_desc);
  1468. Tracev((stderr, "\ndist data: dyn %ld, stat %ld", (long)G2.opt_len, (long)G2.static_len));
  1469. /* At this point, opt_len and static_len are the total bit lengths of
  1470. * the compressed block data, excluding the tree representations.
  1471. */
  1472. /* Build the bit length tree for the above two trees, and get the index
  1473. * in bl_order of the last bit length code to send.
  1474. */
  1475. max_blindex = build_bl_tree();
  1476. /* Determine the best encoding. Compute first the block length in bytes */
  1477. opt_lenb = (G2.opt_len + 3 + 7) >> 3;
  1478. static_lenb = (G2.static_len + 3 + 7) >> 3;
  1479. Trace((stderr,
  1480. "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ",
  1481. (unsigned long)opt_lenb, (unsigned long)G2.opt_len,
  1482. (unsigned long)static_lenb, (unsigned long)G2.static_len,
  1483. (unsigned long)stored_len,
  1484. G2.last_lit, G2.last_dist));
  1485. if (static_lenb <= opt_lenb)
  1486. opt_lenb = static_lenb;
  1487. /* If compression failed and this is the first and last block,
  1488. * and if the zip file can be seeked (to rewrite the local header),
  1489. * the whole file is transformed into a stored file:
  1490. */
  1491. // seekable() is constant FALSE in busybox, and G2.compressed_len is disabled
  1492. // (this was the only user)
  1493. // if (stored_len <= opt_lenb && eof && G2.compressed_len == 0L && seekable()) {
  1494. // /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
  1495. // if (buf == NULL)
  1496. // bb_error_msg("block vanished");
  1497. //
  1498. // G2.compressed_len = stored_len << 3;
  1499. // copy_block(buf, (unsigned) stored_len, 0); /* without header */
  1500. // } else
  1501. if (stored_len + 4 <= opt_lenb && buf != NULL) {
  1502. /* 4: two words for the lengths */
  1503. /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
  1504. * Otherwise we can't have processed more than WSIZE input bytes since
  1505. * the last block flush, because compression would have been
  1506. * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
  1507. * transform a block into a stored block.
  1508. */
  1509. send_bits((STORED_BLOCK << 1) + eof, 3); /* send block type */
  1510. // G2.compressed_len = ((G2.compressed_len + 3 + 7) & ~7L)
  1511. // + ((stored_len + 4) << 3);
  1512. copy_block(buf, (unsigned) stored_len, 1); /* with header */
  1513. } else
  1514. if (static_lenb == opt_lenb) {
  1515. send_bits((STATIC_TREES << 1) + eof, 3);
  1516. compress_block((ct_data *) G2.static_ltree, (ct_data *) G2.static_dtree);
  1517. // G2.compressed_len += 3 + G2.static_len;
  1518. } else {
  1519. send_bits((DYN_TREES << 1) + eof, 3);
  1520. send_all_trees(G2.l_desc.max_code + 1, G2.d_desc.max_code + 1,
  1521. max_blindex + 1);
  1522. compress_block((ct_data *) G2.dyn_ltree, (ct_data *) G2.dyn_dtree);
  1523. // G2.compressed_len += 3 + G2.opt_len;
  1524. }
  1525. // Assert(G2.compressed_len == G1.bits_sent, "bad compressed size");
  1526. init_block();
  1527. if (eof) {
  1528. bi_windup();
  1529. // G2.compressed_len += 7; /* align on byte boundary */
  1530. }
  1531. // Tracev((stderr, "\ncomprlen %lu(%lu) ",
  1532. // (unsigned long)G2.compressed_len >> 3,
  1533. // (unsigned long)G2.compressed_len - 7 * eof));
  1534. return; /* was "return G2.compressed_len >> 3;" */
  1535. }
  1536. /* ===========================================================================
  1537. * Update a hash value with the given input byte
  1538. * IN assertion: all calls to UPDATE_HASH are made with consecutive
  1539. * input characters, so that a running hash key can be computed from the
  1540. * previous key instead of complete recalculation each time.
  1541. */
  1542. #define UPDATE_HASH(h, c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
  1543. /* ===========================================================================
  1544. * Same as above, but achieves better compression. We use a lazy
  1545. * evaluation for matches: a match is finally adopted only if there is
  1546. * no better match at the next window position.
  1547. *
  1548. * Processes a new input file and return its compressed length. Sets
  1549. * the compressed length, crc, deflate flags and internal file
  1550. * attributes.
  1551. */
  1552. /* Flush the current block, with given end-of-file flag.
  1553. * IN assertion: strstart is set to the end of the current match. */
  1554. #define FLUSH_BLOCK(eof) \
  1555. flush_block( \
  1556. G1.block_start >= 0L \
  1557. ? (char*)&G1.window[(unsigned)G1.block_start] \
  1558. : (char*)NULL, \
  1559. (ulg)G1.strstart - G1.block_start, \
  1560. (eof) \
  1561. )
  1562. /* Insert string s in the dictionary and set match_head to the previous head
  1563. * of the hash chain (the most recent string with same hash key). Return
  1564. * the previous length of the hash chain.
  1565. * IN assertion: all calls to INSERT_STRING are made with consecutive
  1566. * input characters and the first MIN_MATCH bytes of s are valid
  1567. * (except for the last MIN_MATCH-1 bytes of the input file). */
  1568. #define INSERT_STRING(s, match_head) \
  1569. do { \
  1570. UPDATE_HASH(G1.ins_h, G1.window[(s) + MIN_MATCH-1]); \
  1571. G1.prev[(s) & WMASK] = match_head = head[G1.ins_h]; \
  1572. head[G1.ins_h] = (s); \
  1573. } while (0)
  1574. static NOINLINE void deflate(void)
  1575. {
  1576. IPos hash_head; /* head of hash chain */
  1577. IPos prev_match; /* previous match */
  1578. int flush; /* set if current block must be flushed */
  1579. int match_available = 0; /* set if previous match exists */
  1580. unsigned match_length = MIN_MATCH - 1; /* length of best match */
  1581. /* Process the input block. */
  1582. while (G1.lookahead != 0) {
  1583. /* Insert the string window[strstart .. strstart+2] in the
  1584. * dictionary, and set hash_head to the head of the hash chain:
  1585. */
  1586. INSERT_STRING(G1.strstart, hash_head);
  1587. /* Find the longest match, discarding those <= prev_length.
  1588. */
  1589. G1.prev_length = match_length;
  1590. prev_match = G1.match_start;
  1591. match_length = MIN_MATCH - 1;
  1592. if (hash_head != 0 && G1.prev_length < max_lazy_match
  1593. && G1.strstart - hash_head <= MAX_DIST
  1594. ) {
  1595. /* To simplify the code, we prevent matches with the string
  1596. * of window index 0 (in particular we have to avoid a match
  1597. * of the string with itself at the start of the input file).
  1598. */
  1599. match_length = longest_match(hash_head);
  1600. /* longest_match() sets match_start */
  1601. if (match_length > G1.lookahead)
  1602. match_length = G1.lookahead;
  1603. /* Ignore a length 3 match if it is too distant: */
  1604. if (match_length == MIN_MATCH && G1.strstart - G1.match_start > TOO_FAR) {
  1605. /* If prev_match is also MIN_MATCH, G1.match_start is garbage
  1606. * but we will ignore the current match anyway.
  1607. */
  1608. match_length--;
  1609. }
  1610. }
  1611. /* If there was a match at the previous step and the current
  1612. * match is not better, output the previous match:
  1613. */
  1614. if (G1.prev_length >= MIN_MATCH && match_length <= G1.prev_length) {
  1615. check_match(G1.strstart - 1, prev_match, G1.prev_length);
  1616. flush = ct_tally(G1.strstart - 1 - prev_match, G1.prev_length - MIN_MATCH);
  1617. /* Insert in hash table all strings up to the end of the match.
  1618. * strstart-1 and strstart are already inserted.
  1619. */
  1620. G1.lookahead -= G1.prev_length - 1;
  1621. G1.prev_length -= 2;
  1622. do {
  1623. G1.strstart++;
  1624. INSERT_STRING(G1.strstart, hash_head);
  1625. /* strstart never exceeds WSIZE-MAX_MATCH, so there are
  1626. * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
  1627. * these bytes are garbage, but it does not matter since the
  1628. * next lookahead bytes will always be emitted as literals.
  1629. */
  1630. } while (--G1.prev_length != 0);
  1631. match_available = 0;
  1632. match_length = MIN_MATCH - 1;
  1633. G1.strstart++;
  1634. if (flush) {
  1635. FLUSH_BLOCK(0);
  1636. G1.block_start = G1.strstart;
  1637. }
  1638. } else if (match_available) {
  1639. /* If there was no match at the previous position, output a
  1640. * single literal. If there was a match but the current match
  1641. * is longer, truncate the previous match to a single literal.
  1642. */
  1643. Tracevv((stderr, "%c", G1.window[G1.strstart - 1]));
  1644. if (ct_tally(0, G1.window[G1.strstart - 1])) {
  1645. FLUSH_BLOCK(0);
  1646. G1.block_start = G1.strstart;
  1647. }
  1648. G1.strstart++;
  1649. G1.lookahead--;
  1650. } else {
  1651. /* There is no previous match to compare with, wait for
  1652. * the next step to decide.
  1653. */
  1654. match_available = 1;
  1655. G1.strstart++;
  1656. G1.lookahead--;
  1657. }
  1658. Assert(G1.strstart <= G1.isize && G1.lookahead <= G1.isize, "a bit too far");
  1659. /* Make sure that we always have enough lookahead, except
  1660. * at the end of the input file. We need MAX_MATCH bytes
  1661. * for the next match, plus MIN_MATCH bytes to insert the
  1662. * string following the next match.
  1663. */
  1664. fill_window_if_needed();
  1665. }
  1666. if (match_available)
  1667. ct_tally(0, G1.window[G1.strstart - 1]);
  1668. FLUSH_BLOCK(1); /* eof */
  1669. }
  1670. /* ===========================================================================
  1671. * Initialize the bit string routines.
  1672. */
  1673. static void bi_init(void)
  1674. {
  1675. //G1.bi_buf = 0; // globals are zeroed in pack_gzip()
  1676. //G1.bi_valid = 0; // globals are zeroed in pack_gzip()
  1677. //DEBUG_bits_sent(= 0L); // globals are zeroed in pack_gzip()
  1678. }
  1679. /* ===========================================================================
  1680. * Initialize the "longest match" routines for a new file
  1681. */
  1682. static void lm_init(unsigned *flags16p)
  1683. {
  1684. unsigned j;
  1685. /* Initialize the hash table. */
  1686. memset(head, 0, HASH_SIZE * sizeof(*head));
  1687. /* prev will be initialized on the fly */
  1688. /* speed options for the general purpose bit flag */
  1689. *flags16p |= 2; /* FAST 4, SLOW 2 */
  1690. /* ??? reduce max_chain_length for binary files */
  1691. //G1.strstart = 0; // globals are zeroed in pack_gzip()
  1692. //G1.block_start = 0L; // globals are zeroed in pack_gzip()
  1693. G1.lookahead = file_read(G1.window,
  1694. sizeof(int) <= 2 ? (unsigned) WSIZE : 2 * WSIZE);
  1695. if (G1.lookahead == 0 || G1.lookahead == (unsigned) -1) {
  1696. G1.eofile = 1;
  1697. G1.lookahead = 0;
  1698. return;
  1699. }
  1700. //G1.eofile = 0; // globals are zeroed in pack_gzip()
  1701. /* Make sure that we always have enough lookahead. This is important
  1702. * if input comes from a device such as a tty.
  1703. */
  1704. fill_window_if_needed();
  1705. //G1.ins_h = 0; // globals are zeroed in pack_gzip()
  1706. for (j = 0; j < MIN_MATCH - 1; j++)
  1707. UPDATE_HASH(G1.ins_h, G1.window[j]);
  1708. /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
  1709. * not important since only literal bytes will be emitted.
  1710. */
  1711. }
  1712. /* ===========================================================================
  1713. * Allocate the match buffer, initialize the various tables and save the
  1714. * location of the internal file attribute (ascii/binary) and method
  1715. * (DEFLATE/STORE).
  1716. * One callsite in zip()
  1717. */
  1718. static void ct_init(void)
  1719. {
  1720. int n; /* iterates over tree elements */
  1721. int length; /* length value */
  1722. int code; /* code value */
  1723. int dist; /* distance index */
  1724. // //G2.compressed_len = 0L; // globals are zeroed in pack_gzip()
  1725. #ifdef NOT_NEEDED
  1726. if (G2.static_dtree[0].Len != 0)
  1727. return; /* ct_init already called */
  1728. #endif
  1729. /* Initialize the mapping length (0..255) -> length code (0..28) */
  1730. length = 0;
  1731. for (code = 0; code < LENGTH_CODES - 1; code++) {
  1732. G2.base_length[code] = length;
  1733. for (n = 0; n < (1 << extra_lbits[code]); n++) {
  1734. G2.length_code[length++] = code;
  1735. }
  1736. }
  1737. Assert(length == 256, "ct_init: length != 256");
  1738. /* Note that the length 255 (match length 258) can be represented
  1739. * in two different ways: code 284 + 5 bits or code 285, so we
  1740. * overwrite length_code[255] to use the best encoding:
  1741. */
  1742. G2.length_code[length - 1] = code;
  1743. /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
  1744. dist = 0;
  1745. for (code = 0; code < 16; code++) {
  1746. G2.base_dist[code] = dist;
  1747. for (n = 0; n < (1 << extra_dbits[code]); n++) {
  1748. G2.dist_code[dist++] = code;
  1749. }
  1750. }
  1751. Assert(dist == 256, "ct_init: dist != 256");
  1752. dist >>= 7; /* from now on, all distances are divided by 128 */
  1753. for (; code < D_CODES; code++) {
  1754. G2.base_dist[code] = dist << 7;
  1755. for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) {
  1756. G2.dist_code[256 + dist++] = code;
  1757. }
  1758. }
  1759. Assert(dist == 256, "ct_init: 256+dist != 512");
  1760. /* Construct the codes of the static literal tree */
  1761. //for (n = 0; n <= MAX_BITS; n++) // globals are zeroed in pack_gzip()
  1762. // G2.bl_count[n] = 0;
  1763. n = 0;
  1764. while (n <= 143) {
  1765. G2.static_ltree[n++].Len = 8;
  1766. //G2.bl_count[8]++;
  1767. }
  1768. //G2.bl_count[8] = 143 + 1;
  1769. while (n <= 255) {
  1770. G2.static_ltree[n++].Len = 9;
  1771. //G2.bl_count[9]++;
  1772. }
  1773. //G2.bl_count[9] = 255 - 143;
  1774. while (n <= 279) {
  1775. G2.static_ltree[n++].Len = 7;
  1776. //G2.bl_count[7]++;
  1777. }
  1778. //G2.bl_count[7] = 279 - 255;
  1779. while (n <= 287) {
  1780. G2.static_ltree[n++].Len = 8;
  1781. //G2.bl_count[8]++;
  1782. }
  1783. //G2.bl_count[8] += 287 - 279;
  1784. G2.bl_count[7] = 279 - 255;
  1785. G2.bl_count[8] = (143 + 1) + (287 - 279);
  1786. G2.bl_count[9] = 255 - 143;
  1787. /* Codes 286 and 287 do not exist, but we must include them in the
  1788. * tree construction to get a canonical Huffman tree (longest code
  1789. * all ones)
  1790. */
  1791. gen_codes((ct_data *) G2.static_ltree, L_CODES + 1);
  1792. /* The static distance tree is trivial: */
  1793. for (n = 0; n < D_CODES; n++) {
  1794. G2.static_dtree[n].Len = 5;
  1795. G2.static_dtree[n].Code = bi_reverse(n, 5);
  1796. }
  1797. /* Initialize the first block of the first file: */
  1798. init_block();
  1799. }
  1800. /* ===========================================================================
  1801. * Deflate in to out.
  1802. * IN assertions: the input and output buffers are cleared.
  1803. */
  1804. static void zip(void)
  1805. {
  1806. unsigned deflate_flags;
  1807. //G1.outcnt = 0; // globals are zeroed in pack_gzip()
  1808. /* Write the header to the gzip file. See algorithm.doc for the format */
  1809. /* magic header for gzip files: 1F 8B */
  1810. /* compression method: 8 (DEFLATED) */
  1811. /* general flags: 0 */
  1812. put_32bit(0x00088b1f);
  1813. put_32bit(0); /* Unix timestamp */
  1814. /* Write deflated file to zip file */
  1815. G1.crc = ~0;
  1816. bi_init();
  1817. ct_init();
  1818. deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */
  1819. lm_init(&deflate_flags);
  1820. put_16bit(deflate_flags | 0x300); /* extra flags. OS id = 3 (Unix) */
  1821. /* The above 32-bit misaligns outbuf (10 bytes are stored), flush it */
  1822. flush_outbuf_if_32bit_optimized();
  1823. deflate();
  1824. /* Write the crc and uncompressed size */
  1825. put_32bit(~G1.crc);
  1826. put_32bit(G1.isize);
  1827. flush_outbuf();
  1828. }
  1829. /* ======================================================================== */
  1830. static
  1831. IF_DESKTOP(long long) int FAST_FUNC pack_gzip(transformer_state_t *xstate UNUSED_PARAM)
  1832. {
  1833. /* Reinit G1.xxx except pointers to allocated buffers, and entire G2 */
  1834. memset(&G1.crc, 0, (sizeof(G1) - offsetof(struct globals, crc)) + sizeof(G2));
  1835. /* Clear input and output buffers */
  1836. //G1.outcnt = 0;
  1837. #ifdef DEBUG
  1838. //G1.insize = 0;
  1839. #endif
  1840. //G1.isize = 0;
  1841. /* Reinit G2.xxx */
  1842. G2.l_desc.dyn_tree = G2.dyn_ltree;
  1843. G2.l_desc.static_tree = G2.static_ltree;
  1844. G2.l_desc.extra_bits = extra_lbits;
  1845. G2.l_desc.extra_base = LITERALS + 1;
  1846. G2.l_desc.elems = L_CODES;
  1847. G2.l_desc.max_length = MAX_BITS;
  1848. //G2.l_desc.max_code = 0;
  1849. G2.d_desc.dyn_tree = G2.dyn_dtree;
  1850. G2.d_desc.static_tree = G2.static_dtree;
  1851. G2.d_desc.extra_bits = extra_dbits;
  1852. //G2.d_desc.extra_base = 0;
  1853. G2.d_desc.elems = D_CODES;
  1854. G2.d_desc.max_length = MAX_BITS;
  1855. //G2.d_desc.max_code = 0;
  1856. G2.bl_desc.dyn_tree = G2.bl_tree;
  1857. //G2.bl_desc.static_tree = NULL;
  1858. G2.bl_desc.extra_bits = extra_blbits,
  1859. //G2.bl_desc.extra_base = 0;
  1860. G2.bl_desc.elems = BL_CODES;
  1861. G2.bl_desc.max_length = MAX_BL_BITS;
  1862. //G2.bl_desc.max_code = 0;
  1863. #if 0
  1864. /* Saving of timestamp is disabled. Why?
  1865. * - it is not Y2038-safe.
  1866. * - some people want deterministic results
  1867. * (normally they'd use -n, but our -n is a nop).
  1868. * - it's bloat.
  1869. * Per RFC 1952, gzfile.time=0 is "no timestamp".
  1870. * If users will demand this to be reinstated,
  1871. * implement -n "don't save timestamp".
  1872. */
  1873. struct stat s;
  1874. s.st_ctime = 0;
  1875. fstat(STDIN_FILENO, &s);
  1876. zip(s.st_ctime);
  1877. #else
  1878. zip();
  1879. #endif
  1880. return 0;
  1881. }
  1882. #if ENABLE_FEATURE_GZIP_LONG_OPTIONS
  1883. static const char gzip_longopts[] ALIGN1 =
  1884. "stdout\0" No_argument "c"
  1885. "to-stdout\0" No_argument "c"
  1886. "force\0" No_argument "f"
  1887. "verbose\0" No_argument "v"
  1888. #if ENABLE_FEATURE_GZIP_DECOMPRESS
  1889. "decompress\0" No_argument "d"
  1890. "uncompress\0" No_argument "d"
  1891. "test\0" No_argument "t"
  1892. #endif
  1893. "quiet\0" No_argument "q"
  1894. "fast\0" No_argument "1"
  1895. "best\0" No_argument "9"
  1896. "no-name\0" No_argument "n"
  1897. ;
  1898. #endif
  1899. /*
  1900. * Linux kernel build uses gzip -d -n. We accept and ignore -n.
  1901. * Man page says:
  1902. * -n --no-name
  1903. * gzip: do not save the original file name and time stamp.
  1904. * (The original name is always saved if the name had to be truncated.)
  1905. * gunzip: do not restore the original file name/time even if present
  1906. * (remove only the gzip suffix from the compressed file name).
  1907. * This option is the default when decompressing.
  1908. * -N --name
  1909. * gzip: always save the original file name and time stamp (this is the default)
  1910. * gunzip: restore the original file name and time stamp if present.
  1911. */
  1912. int gzip_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
  1913. #if ENABLE_FEATURE_GZIP_DECOMPRESS
  1914. int gzip_main(int argc, char **argv)
  1915. #else
  1916. int gzip_main(int argc UNUSED_PARAM, char **argv)
  1917. #endif
  1918. {
  1919. unsigned opt;
  1920. #if ENABLE_FEATURE_GZIP_LEVELS
  1921. static const struct {
  1922. uint8_t good;
  1923. uint8_t chain_shift;
  1924. uint8_t lazy2;
  1925. uint8_t nice2;
  1926. } gzip_level_config[6] = {
  1927. {4, 4, 4/2, 16/2}, /* Level 4 */
  1928. {8, 5, 16/2, 32/2}, /* Level 5 */
  1929. {8, 7, 16/2, 128/2}, /* Level 6 */
  1930. {8, 8, 32/2, 128/2}, /* Level 7 */
  1931. {32, 10, 128/2, 258/2}, /* Level 8 */
  1932. {32, 12, 258/2, 258/2}, /* Level 9 */
  1933. };
  1934. #endif
  1935. SET_PTR_TO_GLOBALS((char *)xzalloc(sizeof(struct globals)+sizeof(struct globals2))
  1936. + sizeof(struct globals));
  1937. /* Must match bbunzip's constants OPT_STDOUT, OPT_FORCE! */
  1938. #if ENABLE_FEATURE_GZIP_LONG_OPTIONS
  1939. opt = getopt32long(argv, BBUNPK_OPTSTR IF_FEATURE_GZIP_DECOMPRESS("dt") "n123456789", gzip_longopts);
  1940. #else
  1941. opt = getopt32(argv, BBUNPK_OPTSTR IF_FEATURE_GZIP_DECOMPRESS("dt") "n123456789");
  1942. #endif
  1943. #if ENABLE_FEATURE_GZIP_DECOMPRESS /* gunzip_main may not be visible... */
  1944. if (opt & (BBUNPK_OPT_DECOMPRESS|BBUNPK_OPT_TEST)) /* -d and/or -t */
  1945. return gunzip_main(argc, argv);
  1946. #endif
  1947. #if ENABLE_FEATURE_GZIP_LEVELS
  1948. opt >>= (BBUNPK_OPTSTRLEN IF_FEATURE_GZIP_DECOMPRESS(+ 2) + 1); /* drop cfkvq[dt]n bits */
  1949. if (opt == 0)
  1950. opt = 1 << 6; /* default: 6 */
  1951. opt = ffs(opt >> 4); /* Maps -1..-4 to [0], -5 to [1] ... -9 to [5] */
  1952. max_chain_length = 1 << gzip_level_config[opt].chain_shift;
  1953. good_match = gzip_level_config[opt].good;
  1954. max_lazy_match = gzip_level_config[opt].lazy2 * 2;
  1955. nice_match = gzip_level_config[opt].nice2 * 2;
  1956. #endif
  1957. option_mask32 &= BBUNPK_OPTSTRMASK; /* retain only -cfkvq */
  1958. /* Allocate all global buffers (for DYN_ALLOC option) */
  1959. ALLOC(uch, G1.l_buf, INBUFSIZ);
  1960. ALLOC(uch, G1.outbuf, OUTBUFSIZ);
  1961. ALLOC(ush, G1.d_buf, DIST_BUFSIZE);
  1962. ALLOC(uch, G1.window, 2L * WSIZE);
  1963. ALLOC(ush, G1.prev, 1L << BITS);
  1964. /* Initialize the CRC32 table */
  1965. global_crc32_new_table_le();
  1966. argv += optind;
  1967. return bbunpack(argv, pack_gzip, append_ext, "gz");
  1968. }