gzip.c 64 KB

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