3
0

gzip.c 71 KB

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