deflate.c 66 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833
  1. /* deflate.c -- compress data using the deflation algorithm
  2. * Copyright (C) 1995-2010 Jean-loup Gailly and Mark Adler
  3. * For conditions of distribution and use, see copyright notice in zlib.h
  4. */
  5. /*
  6. * ALGORITHM
  7. *
  8. * The "deflation" process depends on being able to identify portions
  9. * of the input text which are identical to earlier input (within a
  10. * sliding window trailing behind the input currently being processed).
  11. *
  12. * The most straightforward technique turns out to be the fastest for
  13. * most input files: try all possible matches and select the longest.
  14. * The key feature of this algorithm is that insertions into the string
  15. * dictionary are very simple and thus fast, and deletions are avoided
  16. * completely. Insertions are performed at each input character, whereas
  17. * string matches are performed only when the previous match ends. So it
  18. * is preferable to spend more time in matches to allow very fast string
  19. * insertions and avoid deletions. The matching algorithm for small
  20. * strings is inspired from that of Rabin & Karp. A brute force approach
  21. * is used to find longer strings when a small match has been found.
  22. * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
  23. * (by Leonid Broukhis).
  24. * A previous version of this file used a more sophisticated algorithm
  25. * (by Fiala and Greene) which is guaranteed to run in linear amortized
  26. * time, but has a larger average cost, uses more memory and is patented.
  27. * However the F&G algorithm may be faster for some highly redundant
  28. * files if the parameter max_chain_length (described below) is too large.
  29. *
  30. * ACKNOWLEDGEMENTS
  31. *
  32. * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
  33. * I found it in 'freeze' written by Leonid Broukhis.
  34. * Thanks to many people for bug reports and testing.
  35. *
  36. * REFERENCES
  37. *
  38. * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
  39. * Available in http://www.ietf.org/rfc/rfc1951.txt
  40. *
  41. * A description of the Rabin and Karp algorithm is given in the book
  42. * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  43. *
  44. * Fiala,E.R., and Greene,D.H.
  45. * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
  46. *
  47. */
  48. /* @(#) $Id$ */
  49. #include "deflate.h"
  50. #include <u-boot/crc.h>
  51. const char deflate_copyright[] =
  52. " deflate 1.2.5 Copyright 1995-2010 Jean-loup Gailly and Mark Adler ";
  53. /*
  54. If you use the zlib library in a product, an acknowledgment is welcome
  55. in the documentation of your product. If for some reason you cannot
  56. include such an acknowledgment, I would appreciate that you keep this
  57. copyright string in the executable of your product.
  58. */
  59. /* ===========================================================================
  60. * Function prototypes.
  61. */
  62. typedef enum {
  63. need_more, /* block not completed, need more input or more output */
  64. block_done, /* block flush performed */
  65. finish_started, /* finish started, need only more output at next deflate */
  66. finish_done /* finish done, accept no more input or output */
  67. } block_state;
  68. typedef block_state (*compress_func) OF((deflate_state *s, int flush));
  69. /* Compression function. Returns the block state after the call. */
  70. local void fill_window OF((deflate_state *s));
  71. local block_state deflate_stored OF((deflate_state *s, int flush));
  72. local block_state deflate_fast OF((deflate_state *s, int flush));
  73. #ifndef FASTEST
  74. local block_state deflate_slow OF((deflate_state *s, int flush));
  75. #endif
  76. local block_state deflate_rle OF((deflate_state *s, int flush));
  77. local block_state deflate_huff OF((deflate_state *s, int flush));
  78. local void lm_init OF((deflate_state *s));
  79. local void putShortMSB OF((deflate_state *s, uInt b));
  80. local void flush_pending OF((z_streamp strm));
  81. local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
  82. #ifdef ASMV
  83. void match_init OF((void)); /* asm code initialization */
  84. uInt longest_match OF((deflate_state *s, IPos cur_match));
  85. #else
  86. local uInt longest_match OF((deflate_state *s, IPos cur_match));
  87. #endif
  88. #ifdef DEBUG
  89. local void check_match OF((deflate_state *s, IPos start, IPos match,
  90. int length));
  91. #endif
  92. /* ===========================================================================
  93. * Local data
  94. */
  95. #define NIL 0
  96. /* Tail of hash chains */
  97. #ifndef TOO_FAR
  98. # define TOO_FAR 4096
  99. #endif
  100. /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  101. /* Values for max_lazy_match, good_match and max_chain_length, depending on
  102. * the desired pack level (0..9). The values given below have been tuned to
  103. * exclude worst case performance for pathological files. Better values may be
  104. * found for specific files.
  105. */
  106. typedef struct config_s {
  107. ush good_length; /* reduce lazy search above this match length */
  108. ush max_lazy; /* do not perform lazy search above this match length */
  109. ush nice_length; /* quit search above this match length */
  110. ush max_chain;
  111. compress_func func;
  112. } config;
  113. #ifdef FASTEST
  114. local const config configuration_table[2] = {
  115. /* good lazy nice chain */
  116. /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
  117. /* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */
  118. #else
  119. local const config configuration_table[10] = {
  120. /* good lazy nice chain */
  121. /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
  122. /* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */
  123. /* 2 */ {4, 5, 16, 8, deflate_fast},
  124. /* 3 */ {4, 6, 32, 32, deflate_fast},
  125. /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */
  126. /* 5 */ {8, 16, 32, 32, deflate_slow},
  127. /* 6 */ {8, 16, 128, 128, deflate_slow},
  128. /* 7 */ {8, 32, 128, 256, deflate_slow},
  129. /* 8 */ {32, 128, 258, 1024, deflate_slow},
  130. /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
  131. #endif
  132. /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
  133. * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
  134. * meaning.
  135. */
  136. #define EQUAL 0
  137. /* result of memcmp for equal strings */
  138. #ifndef NO_DUMMY_DECL
  139. struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
  140. #endif
  141. /* ===========================================================================
  142. * Update a hash value with the given input byte
  143. * IN assertion: all calls to to UPDATE_HASH are made with consecutive
  144. * input characters, so that a running hash key can be computed from the
  145. * previous key instead of complete recalculation each time.
  146. */
  147. #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
  148. /* ===========================================================================
  149. * Insert string str in the dictionary and set match_head to the previous head
  150. * of the hash chain (the most recent string with same hash key). Return
  151. * the previous length of the hash chain.
  152. * If this file is compiled with -DFASTEST, the compression level is forced
  153. * to 1, and no hash chains are maintained.
  154. * IN assertion: all calls to to INSERT_STRING are made with consecutive
  155. * input characters and the first MIN_MATCH bytes of str are valid
  156. * (except for the last MIN_MATCH-1 bytes of the input file).
  157. */
  158. #ifdef FASTEST
  159. #define INSERT_STRING(s, str, match_head) \
  160. (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
  161. match_head = s->head[s->ins_h], \
  162. s->head[s->ins_h] = (Pos)(str))
  163. #else
  164. #define INSERT_STRING(s, str, match_head) \
  165. (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
  166. match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
  167. s->head[s->ins_h] = (Pos)(str))
  168. #endif
  169. /* ===========================================================================
  170. * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
  171. * prev[] will be initialized on the fly.
  172. */
  173. #define CLEAR_HASH(s) \
  174. s->head[s->hash_size-1] = NIL; \
  175. zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
  176. /* ========================================================================= */
  177. int ZEXPORT deflateInit_(strm, level, version, stream_size)
  178. z_streamp strm;
  179. int level;
  180. const char *version;
  181. int stream_size;
  182. {
  183. return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
  184. Z_DEFAULT_STRATEGY, version, stream_size);
  185. /* To do: ignore strm->next_in if we use it as window */
  186. }
  187. /* ========================================================================= */
  188. int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
  189. version, stream_size)
  190. z_streamp strm;
  191. int level;
  192. int method;
  193. int windowBits;
  194. int memLevel;
  195. int strategy;
  196. const char *version;
  197. int stream_size;
  198. {
  199. deflate_state *s;
  200. int wrap = 1;
  201. static const char my_version[] = ZLIB_VERSION;
  202. ushf *overlay;
  203. /* We overlay pending_buf and d_buf+l_buf. This works since the average
  204. * output size for (length,distance) codes is <= 24 bits.
  205. */
  206. if (version == Z_NULL || version[0] != my_version[0] ||
  207. stream_size != sizeof(z_stream)) {
  208. return Z_VERSION_ERROR;
  209. }
  210. if (strm == Z_NULL) return Z_STREAM_ERROR;
  211. strm->msg = Z_NULL;
  212. if (strm->zalloc == (alloc_func)0) {
  213. strm->zalloc = zcalloc;
  214. strm->opaque = (voidpf)0;
  215. }
  216. if (strm->zfree == (free_func)0) strm->zfree = zcfree;
  217. #ifdef FASTEST
  218. if (level != 0) level = 1;
  219. #else
  220. if (level == Z_DEFAULT_COMPRESSION) level = 6;
  221. #endif
  222. if (windowBits < 0) { /* suppress zlib wrapper */
  223. wrap = 0;
  224. windowBits = -windowBits;
  225. }
  226. #ifdef GZIP
  227. else if (windowBits > 15) {
  228. wrap = 2; /* write gzip wrapper instead */
  229. windowBits -= 16;
  230. }
  231. #endif
  232. if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
  233. windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
  234. strategy < 0 || strategy > Z_FIXED) {
  235. return Z_STREAM_ERROR;
  236. }
  237. if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */
  238. s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
  239. if (s == Z_NULL) return Z_MEM_ERROR;
  240. strm->state = (struct internal_state FAR *)s;
  241. s->strm = strm;
  242. s->wrap = wrap;
  243. s->gzhead = Z_NULL;
  244. s->w_bits = windowBits;
  245. s->w_size = 1 << s->w_bits;
  246. s->w_mask = s->w_size - 1;
  247. s->hash_bits = memLevel + 7;
  248. s->hash_size = 1 << s->hash_bits;
  249. s->hash_mask = s->hash_size - 1;
  250. s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
  251. s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
  252. s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
  253. s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
  254. s->high_water = 0; /* nothing written to s->window yet */
  255. s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
  256. overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
  257. s->pending_buf = (uchf *) overlay;
  258. s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
  259. if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
  260. s->pending_buf == Z_NULL) {
  261. s->status = FINISH_STATE;
  262. strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);
  263. deflateEnd (strm);
  264. return Z_MEM_ERROR;
  265. }
  266. s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
  267. s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
  268. s->level = level;
  269. s->strategy = strategy;
  270. s->method = (Byte)method;
  271. return deflateReset(strm);
  272. }
  273. /* ========================================================================= */
  274. int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
  275. z_streamp strm;
  276. const Bytef *dictionary;
  277. uInt dictLength;
  278. {
  279. deflate_state *s;
  280. uInt length = dictLength;
  281. uInt n;
  282. IPos hash_head = 0;
  283. if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||
  284. strm->state->wrap == 2 ||
  285. (strm->state->wrap == 1 && strm->state->status != INIT_STATE))
  286. return Z_STREAM_ERROR;
  287. s = strm->state;
  288. if (s->wrap)
  289. strm->adler = adler32(strm->adler, dictionary, dictLength);
  290. if (length < MIN_MATCH) return Z_OK;
  291. if (length > s->w_size) {
  292. length = s->w_size;
  293. dictionary += dictLength - length; /* use the tail of the dictionary */
  294. }
  295. zmemcpy(s->window, dictionary, length);
  296. s->strstart = length;
  297. s->block_start = (long)length;
  298. /* Insert all strings in the hash table (except for the last two bytes).
  299. * s->lookahead stays null, so s->ins_h will be recomputed at the next
  300. * call of fill_window.
  301. */
  302. s->ins_h = s->window[0];
  303. UPDATE_HASH(s, s->ins_h, s->window[1]);
  304. for (n = 0; n <= length - MIN_MATCH; n++) {
  305. INSERT_STRING(s, n, hash_head);
  306. }
  307. if (hash_head) hash_head = 0; /* to make compiler happy */
  308. return Z_OK;
  309. }
  310. /* ========================================================================= */
  311. int ZEXPORT deflateReset (strm)
  312. z_streamp strm;
  313. {
  314. deflate_state *s;
  315. if (strm == Z_NULL || strm->state == Z_NULL ||
  316. strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {
  317. return Z_STREAM_ERROR;
  318. }
  319. strm->total_in = strm->total_out = 0;
  320. strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
  321. strm->data_type = Z_UNKNOWN;
  322. s = (deflate_state *)strm->state;
  323. s->pending = 0;
  324. s->pending_out = s->pending_buf;
  325. if (s->wrap < 0) {
  326. s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
  327. }
  328. s->status = s->wrap ? INIT_STATE : BUSY_STATE;
  329. strm->adler =
  330. #ifdef GZIP
  331. s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
  332. #endif
  333. adler32(0L, Z_NULL, 0);
  334. s->last_flush = Z_NO_FLUSH;
  335. _tr_init(s);
  336. lm_init(s);
  337. return Z_OK;
  338. }
  339. /* ========================================================================= */
  340. int ZEXPORT deflateSetHeader (strm, head)
  341. z_streamp strm;
  342. gz_headerp head;
  343. {
  344. if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  345. if (strm->state->wrap != 2) return Z_STREAM_ERROR;
  346. strm->state->gzhead = head;
  347. return Z_OK;
  348. }
  349. /* ========================================================================= */
  350. int ZEXPORT deflatePrime (strm, bits, value)
  351. z_streamp strm;
  352. int bits;
  353. int value;
  354. {
  355. if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  356. strm->state->bi_valid = bits;
  357. strm->state->bi_buf = (ush)(value & ((1 << bits) - 1));
  358. return Z_OK;
  359. }
  360. /* ========================================================================= */
  361. int ZEXPORT deflateParams(strm, level, strategy)
  362. z_streamp strm;
  363. int level;
  364. int strategy;
  365. {
  366. deflate_state *s;
  367. compress_func func;
  368. int err = Z_OK;
  369. if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  370. s = strm->state;
  371. #ifdef FASTEST
  372. if (level != 0) level = 1;
  373. #else
  374. if (level == Z_DEFAULT_COMPRESSION) level = 6;
  375. #endif
  376. if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {
  377. return Z_STREAM_ERROR;
  378. }
  379. func = configuration_table[s->level].func;
  380. if ((strategy != s->strategy || func != configuration_table[level].func) &&
  381. strm->total_in != 0) {
  382. /* Flush the last buffer: */
  383. err = deflate(strm, Z_BLOCK);
  384. }
  385. if (s->level != level) {
  386. s->level = level;
  387. s->max_lazy_match = configuration_table[level].max_lazy;
  388. s->good_match = configuration_table[level].good_length;
  389. s->nice_match = configuration_table[level].nice_length;
  390. s->max_chain_length = configuration_table[level].max_chain;
  391. }
  392. s->strategy = strategy;
  393. return err;
  394. }
  395. /* ========================================================================= */
  396. int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
  397. z_streamp strm;
  398. int good_length;
  399. int max_lazy;
  400. int nice_length;
  401. int max_chain;
  402. {
  403. deflate_state *s;
  404. if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  405. s = strm->state;
  406. s->good_match = good_length;
  407. s->max_lazy_match = max_lazy;
  408. s->nice_match = nice_length;
  409. s->max_chain_length = max_chain;
  410. return Z_OK;
  411. }
  412. /* =========================================================================
  413. * For the default windowBits of 15 and memLevel of 8, this function returns
  414. * a close to exact, as well as small, upper bound on the compressed size.
  415. * They are coded as constants here for a reason--if the #define's are
  416. * changed, then this function needs to be changed as well. The return
  417. * value for 15 and 8 only works for those exact settings.
  418. *
  419. * For any setting other than those defaults for windowBits and memLevel,
  420. * the value returned is a conservative worst case for the maximum expansion
  421. * resulting from using fixed blocks instead of stored blocks, which deflate
  422. * can emit on compressed data for some combinations of the parameters.
  423. *
  424. * This function could be more sophisticated to provide closer upper bounds for
  425. * every combination of windowBits and memLevel. But even the conservative
  426. * upper bound of about 14% expansion does not seem onerous for output buffer
  427. * allocation.
  428. */
  429. uLong ZEXPORT deflateBound(strm, sourceLen)
  430. z_streamp strm;
  431. uLong sourceLen;
  432. {
  433. deflate_state *s;
  434. uLong complen, wraplen;
  435. Bytef *str;
  436. /* conservative upper bound for compressed data */
  437. complen = sourceLen +
  438. ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
  439. /* if can't get parameters, return conservative bound plus zlib wrapper */
  440. if (strm == Z_NULL || strm->state == Z_NULL)
  441. return complen + 6;
  442. /* compute wrapper length */
  443. s = strm->state;
  444. switch (s->wrap) {
  445. case 0: /* raw deflate */
  446. wraplen = 0;
  447. break;
  448. case 1: /* zlib wrapper */
  449. wraplen = 6 + (s->strstart ? 4 : 0);
  450. break;
  451. case 2: /* gzip wrapper */
  452. wraplen = 18;
  453. if (s->gzhead != Z_NULL) { /* user-supplied gzip header */
  454. if (s->gzhead->extra != Z_NULL)
  455. wraplen += 2 + s->gzhead->extra_len;
  456. str = s->gzhead->name;
  457. if (str != Z_NULL)
  458. do {
  459. wraplen++;
  460. } while (*str++);
  461. str = s->gzhead->comment;
  462. if (str != Z_NULL)
  463. do {
  464. wraplen++;
  465. } while (*str++);
  466. if (s->gzhead->hcrc)
  467. wraplen += 2;
  468. }
  469. break;
  470. default: /* for compiler happiness */
  471. wraplen = 6;
  472. }
  473. /* if not default parameters, return conservative bound */
  474. if (s->w_bits != 15 || s->hash_bits != 8 + 7)
  475. return complen + wraplen;
  476. /* default settings: return tight bound for that case */
  477. return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
  478. (sourceLen >> 25) + 13 - 6 + wraplen;
  479. }
  480. /* =========================================================================
  481. * Put a short in the pending buffer. The 16-bit value is put in MSB order.
  482. * IN assertion: the stream state is correct and there is enough room in
  483. * pending_buf.
  484. */
  485. local void putShortMSB (s, b)
  486. deflate_state *s;
  487. uInt b;
  488. {
  489. put_byte(s, (Byte)(b >> 8));
  490. put_byte(s, (Byte)(b & 0xff));
  491. }
  492. /* =========================================================================
  493. * Flush as much pending output as possible. All deflate() output goes
  494. * through this function so some applications may wish to modify it
  495. * to avoid allocating a large strm->next_out buffer and copying into it.
  496. * (See also read_buf()).
  497. */
  498. local void flush_pending(strm)
  499. z_streamp strm;
  500. {
  501. unsigned len = strm->state->pending;
  502. if (len > strm->avail_out) len = strm->avail_out;
  503. if (len == 0) return;
  504. zmemcpy(strm->next_out, strm->state->pending_out, len);
  505. strm->next_out += len;
  506. strm->state->pending_out += len;
  507. strm->total_out += len;
  508. strm->avail_out -= len;
  509. strm->state->pending -= len;
  510. if (strm->state->pending == 0) {
  511. strm->state->pending_out = strm->state->pending_buf;
  512. }
  513. }
  514. /* ========================================================================= */
  515. int ZEXPORT deflate (strm, flush)
  516. z_streamp strm;
  517. int flush;
  518. {
  519. int old_flush; /* value of flush param for previous deflate call */
  520. deflate_state *s;
  521. if (strm == Z_NULL || strm->state == Z_NULL ||
  522. flush > Z_BLOCK || flush < 0) {
  523. return Z_STREAM_ERROR;
  524. }
  525. s = strm->state;
  526. if (s->status == FINISH_STATE && flush != Z_FINISH) {
  527. ERR_RETURN(strm, Z_STREAM_ERROR);
  528. }
  529. if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
  530. s->strm = strm; /* just in case */
  531. old_flush = s->last_flush;
  532. s->last_flush = flush;
  533. /* Write the header */
  534. if (s->status == INIT_STATE) {
  535. #ifdef GZIP
  536. if (s->wrap == 2) {
  537. strm->adler = crc32(0L, Z_NULL, 0);
  538. put_byte(s, 31);
  539. put_byte(s, 139);
  540. put_byte(s, 8);
  541. if (s->gzhead == Z_NULL) {
  542. put_byte(s, 0);
  543. put_byte(s, 0);
  544. put_byte(s, 0);
  545. put_byte(s, 0);
  546. put_byte(s, 0);
  547. put_byte(s, s->level == 9 ? 2 :
  548. (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
  549. 4 : 0));
  550. put_byte(s, OS_CODE);
  551. s->status = BUSY_STATE;
  552. }
  553. else {
  554. put_byte(s, (s->gzhead->text ? 1 : 0) +
  555. (s->gzhead->hcrc ? 2 : 0) +
  556. (s->gzhead->extra == Z_NULL ? 0 : 4) +
  557. (s->gzhead->name == Z_NULL ? 0 : 8) +
  558. (s->gzhead->comment == Z_NULL ? 0 : 16)
  559. );
  560. put_byte(s, (Byte)(s->gzhead->time & 0xff));
  561. put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));
  562. put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));
  563. put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));
  564. put_byte(s, s->level == 9 ? 2 :
  565. (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
  566. 4 : 0));
  567. put_byte(s, s->gzhead->os & 0xff);
  568. if (s->gzhead->extra != Z_NULL) {
  569. put_byte(s, s->gzhead->extra_len & 0xff);
  570. put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
  571. }
  572. if (s->gzhead->hcrc)
  573. strm->adler = crc32(strm->adler, s->pending_buf,
  574. s->pending);
  575. s->gzindex = 0;
  576. s->status = EXTRA_STATE;
  577. }
  578. }
  579. else
  580. #endif
  581. {
  582. uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
  583. uInt level_flags;
  584. if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
  585. level_flags = 0;
  586. else if (s->level < 6)
  587. level_flags = 1;
  588. else if (s->level == 6)
  589. level_flags = 2;
  590. else
  591. level_flags = 3;
  592. header |= (level_flags << 6);
  593. if (s->strstart != 0) header |= PRESET_DICT;
  594. header += 31 - (header % 31);
  595. s->status = BUSY_STATE;
  596. putShortMSB(s, header);
  597. /* Save the adler32 of the preset dictionary: */
  598. if (s->strstart != 0) {
  599. putShortMSB(s, (uInt)(strm->adler >> 16));
  600. putShortMSB(s, (uInt)(strm->adler & 0xffff));
  601. }
  602. strm->adler = adler32(0L, Z_NULL, 0);
  603. }
  604. }
  605. #ifdef GZIP
  606. if (s->status == EXTRA_STATE) {
  607. if (s->gzhead->extra != Z_NULL) {
  608. uInt beg = s->pending; /* start of bytes to update crc */
  609. while (s->gzindex < (s->gzhead->extra_len & 0xffff)) {
  610. if (s->pending == s->pending_buf_size) {
  611. if (s->gzhead->hcrc && s->pending > beg)
  612. strm->adler = crc32(strm->adler, s->pending_buf + beg,
  613. s->pending - beg);
  614. flush_pending(strm);
  615. beg = s->pending;
  616. if (s->pending == s->pending_buf_size)
  617. break;
  618. }
  619. put_byte(s, s->gzhead->extra[s->gzindex]);
  620. s->gzindex++;
  621. }
  622. if (s->gzhead->hcrc && s->pending > beg)
  623. strm->adler = crc32(strm->adler, s->pending_buf + beg,
  624. s->pending - beg);
  625. if (s->gzindex == s->gzhead->extra_len) {
  626. s->gzindex = 0;
  627. s->status = NAME_STATE;
  628. }
  629. }
  630. else
  631. s->status = NAME_STATE;
  632. }
  633. if (s->status == NAME_STATE) {
  634. if (s->gzhead->name != Z_NULL) {
  635. uInt beg = s->pending; /* start of bytes to update crc */
  636. int val;
  637. do {
  638. if (s->pending == s->pending_buf_size) {
  639. if (s->gzhead->hcrc && s->pending > beg)
  640. strm->adler = crc32(strm->adler, s->pending_buf + beg,
  641. s->pending - beg);
  642. flush_pending(strm);
  643. beg = s->pending;
  644. if (s->pending == s->pending_buf_size) {
  645. val = 1;
  646. break;
  647. }
  648. }
  649. val = s->gzhead->name[s->gzindex++];
  650. put_byte(s, val);
  651. } while (val != 0);
  652. if (s->gzhead->hcrc && s->pending > beg)
  653. strm->adler = crc32(strm->adler, s->pending_buf + beg,
  654. s->pending - beg);
  655. if (val == 0) {
  656. s->gzindex = 0;
  657. s->status = COMMENT_STATE;
  658. }
  659. }
  660. else
  661. s->status = COMMENT_STATE;
  662. }
  663. if (s->status == COMMENT_STATE) {
  664. if (s->gzhead->comment != Z_NULL) {
  665. uInt beg = s->pending; /* start of bytes to update crc */
  666. int val;
  667. do {
  668. if (s->pending == s->pending_buf_size) {
  669. if (s->gzhead->hcrc && s->pending > beg)
  670. strm->adler = crc32(strm->adler, s->pending_buf + beg,
  671. s->pending - beg);
  672. flush_pending(strm);
  673. beg = s->pending;
  674. if (s->pending == s->pending_buf_size) {
  675. val = 1;
  676. break;
  677. }
  678. }
  679. val = s->gzhead->comment[s->gzindex++];
  680. put_byte(s, val);
  681. } while (val != 0);
  682. if (s->gzhead->hcrc && s->pending > beg)
  683. strm->adler = crc32(strm->adler, s->pending_buf + beg,
  684. s->pending - beg);
  685. if (val == 0)
  686. s->status = HCRC_STATE;
  687. }
  688. else
  689. s->status = HCRC_STATE;
  690. }
  691. if (s->status == HCRC_STATE) {
  692. if (s->gzhead->hcrc) {
  693. if (s->pending + 2 > s->pending_buf_size)
  694. flush_pending(strm);
  695. if (s->pending + 2 <= s->pending_buf_size) {
  696. put_byte(s, (Byte)(strm->adler & 0xff));
  697. put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
  698. strm->adler = crc32(0L, Z_NULL, 0);
  699. s->status = BUSY_STATE;
  700. }
  701. }
  702. else
  703. s->status = BUSY_STATE;
  704. }
  705. #endif
  706. /* Flush as much pending output as possible */
  707. if (s->pending != 0) {
  708. flush_pending(strm);
  709. if (strm->avail_out == 0) {
  710. /* Since avail_out is 0, deflate will be called again with
  711. * more output space, but possibly with both pending and
  712. * avail_in equal to zero. There won't be anything to do,
  713. * but this is not an error situation so make sure we
  714. * return OK instead of BUF_ERROR at next call of deflate:
  715. */
  716. s->last_flush = -1;
  717. return Z_OK;
  718. }
  719. /* Make sure there is something to do and avoid duplicate consecutive
  720. * flushes. For repeated and useless calls with Z_FINISH, we keep
  721. * returning Z_STREAM_END instead of Z_BUF_ERROR.
  722. */
  723. } else if (strm->avail_in == 0 && flush <= old_flush &&
  724. flush != Z_FINISH) {
  725. ERR_RETURN(strm, Z_BUF_ERROR);
  726. }
  727. /* User must not provide more input after the first FINISH: */
  728. if (s->status == FINISH_STATE && strm->avail_in != 0) {
  729. ERR_RETURN(strm, Z_BUF_ERROR);
  730. }
  731. /* Start a new block or continue the current one.
  732. */
  733. if (strm->avail_in != 0 || s->lookahead != 0 ||
  734. (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
  735. block_state bstate;
  736. bstate = s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
  737. (s->strategy == Z_RLE ? deflate_rle(s, flush) :
  738. (*(configuration_table[s->level].func))(s, flush));
  739. if (bstate == finish_started || bstate == finish_done) {
  740. s->status = FINISH_STATE;
  741. }
  742. if (bstate == need_more || bstate == finish_started) {
  743. if (strm->avail_out == 0) {
  744. s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
  745. }
  746. return Z_OK;
  747. /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
  748. * of deflate should use the same flush parameter to make sure
  749. * that the flush is complete. So we don't have to output an
  750. * empty block here, this will be done at next call. This also
  751. * ensures that for a very small output buffer, we emit at most
  752. * one empty block.
  753. */
  754. }
  755. if (bstate == block_done) {
  756. if (flush == Z_PARTIAL_FLUSH) {
  757. _tr_align(s);
  758. } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */
  759. _tr_stored_block(s, (char*)0, 0L, 0);
  760. /* For a full flush, this empty block will be recognized
  761. * as a special marker by inflate_sync().
  762. */
  763. if (flush == Z_FULL_FLUSH) {
  764. CLEAR_HASH(s); /* forget history */
  765. if (s->lookahead == 0) {
  766. s->strstart = 0;
  767. s->block_start = 0L;
  768. }
  769. }
  770. }
  771. flush_pending(strm);
  772. if (strm->avail_out == 0) {
  773. s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
  774. return Z_OK;
  775. }
  776. }
  777. }
  778. Assert(strm->avail_out > 0, "bug2");
  779. if (flush != Z_FINISH) return Z_OK;
  780. if (s->wrap <= 0) return Z_STREAM_END;
  781. /* Write the trailer */
  782. #ifdef GZIP
  783. if (s->wrap == 2) {
  784. put_byte(s, (Byte)(strm->adler & 0xff));
  785. put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
  786. put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
  787. put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
  788. put_byte(s, (Byte)(strm->total_in & 0xff));
  789. put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
  790. put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
  791. put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
  792. }
  793. else
  794. #endif
  795. {
  796. putShortMSB(s, (uInt)(strm->adler >> 16));
  797. putShortMSB(s, (uInt)(strm->adler & 0xffff));
  798. }
  799. flush_pending(strm);
  800. /* If avail_out is zero, the application will call deflate again
  801. * to flush the rest.
  802. */
  803. if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
  804. return s->pending != 0 ? Z_OK : Z_STREAM_END;
  805. }
  806. /* ========================================================================= */
  807. int ZEXPORT deflateEnd (strm)
  808. z_streamp strm;
  809. {
  810. int status;
  811. if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  812. status = strm->state->status;
  813. if (status != INIT_STATE &&
  814. status != EXTRA_STATE &&
  815. status != NAME_STATE &&
  816. status != COMMENT_STATE &&
  817. status != HCRC_STATE &&
  818. status != BUSY_STATE &&
  819. status != FINISH_STATE) {
  820. return Z_STREAM_ERROR;
  821. }
  822. /* Deallocate in reverse order of allocations: */
  823. TRY_FREE(strm, strm->state->pending_buf);
  824. TRY_FREE(strm, strm->state->head);
  825. TRY_FREE(strm, strm->state->prev);
  826. TRY_FREE(strm, strm->state->window);
  827. ZFREE(strm, strm->state);
  828. strm->state = Z_NULL;
  829. return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
  830. }
  831. /* =========================================================================
  832. * Copy the source state to the destination state.
  833. * To simplify the source, this is not supported for 16-bit MSDOS (which
  834. * doesn't have enough memory anyway to duplicate compression states).
  835. */
  836. int ZEXPORT deflateCopy (dest, source)
  837. z_streamp dest;
  838. z_streamp source;
  839. {
  840. #ifdef MAXSEG_64K
  841. return Z_STREAM_ERROR;
  842. #else
  843. deflate_state *ds;
  844. deflate_state *ss;
  845. ushf *overlay;
  846. if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
  847. return Z_STREAM_ERROR;
  848. }
  849. ss = source->state;
  850. zmemcpy(dest, source, sizeof(z_stream));
  851. ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
  852. if (ds == Z_NULL) return Z_MEM_ERROR;
  853. dest->state = (struct internal_state FAR *) ds;
  854. zmemcpy(ds, ss, sizeof(deflate_state));
  855. ds->strm = dest;
  856. ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
  857. ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
  858. ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
  859. overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
  860. ds->pending_buf = (uchf *) overlay;
  861. if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
  862. ds->pending_buf == Z_NULL) {
  863. deflateEnd (dest);
  864. return Z_MEM_ERROR;
  865. }
  866. /* following zmemcpy do not work for 16-bit MSDOS */
  867. zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
  868. zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));
  869. zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));
  870. zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
  871. ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
  872. ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
  873. ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
  874. ds->l_desc.dyn_tree = ds->dyn_ltree;
  875. ds->d_desc.dyn_tree = ds->dyn_dtree;
  876. ds->bl_desc.dyn_tree = ds->bl_tree;
  877. return Z_OK;
  878. #endif /* MAXSEG_64K */
  879. }
  880. /* ===========================================================================
  881. * Read a new buffer from the current input stream, update the adler32
  882. * and total number of bytes read. All deflate() input goes through
  883. * this function so some applications may wish to modify it to avoid
  884. * allocating a large strm->next_in buffer and copying from it.
  885. * (See also flush_pending()).
  886. */
  887. local int read_buf(strm, buf, size)
  888. z_streamp strm;
  889. Bytef *buf;
  890. unsigned size;
  891. {
  892. unsigned len = strm->avail_in;
  893. if (len > size) len = size;
  894. if (len == 0) return 0;
  895. strm->avail_in -= len;
  896. if (strm->state->wrap == 1) {
  897. strm->adler = adler32(strm->adler, strm->next_in, len);
  898. }
  899. #ifdef GZIP
  900. else if (strm->state->wrap == 2) {
  901. strm->adler = crc32(strm->adler, strm->next_in, len);
  902. }
  903. #endif
  904. zmemcpy(buf, strm->next_in, len);
  905. strm->next_in += len;
  906. strm->total_in += len;
  907. return (int)len;
  908. }
  909. /* ===========================================================================
  910. * Initialize the "longest match" routines for a new zlib stream
  911. */
  912. local void lm_init (s)
  913. deflate_state *s;
  914. {
  915. s->window_size = (ulg)2L*s->w_size;
  916. CLEAR_HASH(s);
  917. /* Set the default configuration parameters:
  918. */
  919. s->max_lazy_match = configuration_table[s->level].max_lazy;
  920. s->good_match = configuration_table[s->level].good_length;
  921. s->nice_match = configuration_table[s->level].nice_length;
  922. s->max_chain_length = configuration_table[s->level].max_chain;
  923. s->strstart = 0;
  924. s->block_start = 0L;
  925. s->lookahead = 0;
  926. s->match_length = s->prev_length = MIN_MATCH-1;
  927. s->match_available = 0;
  928. s->ins_h = 0;
  929. #ifndef FASTEST
  930. #ifdef ASMV
  931. match_init(); /* initialize the asm code */
  932. #endif
  933. #endif
  934. }
  935. #ifndef FASTEST
  936. /* ===========================================================================
  937. * Set match_start to the longest match starting at the given string and
  938. * return its length. Matches shorter or equal to prev_length are discarded,
  939. * in which case the result is equal to prev_length and match_start is
  940. * garbage.
  941. * IN assertions: cur_match is the head of the hash chain for the current
  942. * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  943. * OUT assertion: the match length is not greater than s->lookahead.
  944. */
  945. #ifndef ASMV
  946. /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
  947. * match.S. The code will be functionally equivalent.
  948. */
  949. local uInt longest_match(s, cur_match)
  950. deflate_state *s;
  951. IPos cur_match; /* current match */
  952. {
  953. unsigned chain_length = s->max_chain_length;/* max hash chain length */
  954. register Bytef *scan = s->window + s->strstart; /* current string */
  955. register Bytef *match; /* matched string */
  956. register int len; /* length of current match */
  957. int best_len = s->prev_length; /* best match length so far */
  958. int nice_match = s->nice_match; /* stop if match long enough */
  959. IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
  960. s->strstart - (IPos)MAX_DIST(s) : NIL;
  961. /* Stop when cur_match becomes <= limit. To simplify the code,
  962. * we prevent matches with the string of window index 0.
  963. */
  964. Posf *prev = s->prev;
  965. uInt wmask = s->w_mask;
  966. #ifdef UNALIGNED_OK
  967. /* Compare two bytes at a time. Note: this is not always beneficial.
  968. * Try with and without -DUNALIGNED_OK to check.
  969. */
  970. register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
  971. register ush scan_start = *(ushf*)scan;
  972. register ush scan_end = *(ushf*)(scan+best_len-1);
  973. #else
  974. register Bytef *strend = s->window + s->strstart + MAX_MATCH;
  975. register Byte scan_end1 = scan[best_len-1];
  976. register Byte scan_end = scan[best_len];
  977. #endif
  978. /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
  979. * It is easy to get rid of this optimization if necessary.
  980. */
  981. Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
  982. /* Do not waste too much time if we already have a good match: */
  983. if (s->prev_length >= s->good_match) {
  984. chain_length >>= 2;
  985. }
  986. /* Do not look for matches beyond the end of the input. This is necessary
  987. * to make deflate deterministic.
  988. */
  989. if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
  990. Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
  991. do {
  992. Assert(cur_match < s->strstart, "no future");
  993. match = s->window + cur_match;
  994. /* Skip to next match if the match length cannot increase
  995. * or if the match length is less than 2. Note that the checks below
  996. * for insufficient lookahead only occur occasionally for performance
  997. * reasons. Therefore uninitialized memory will be accessed, and
  998. * conditional jumps will be made that depend on those values.
  999. * However the length of the match is limited to the lookahead, so
  1000. * the output of deflate is not affected by the uninitialized values.
  1001. */
  1002. #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
  1003. /* This code assumes sizeof(unsigned short) == 2. Do not use
  1004. * UNALIGNED_OK if your compiler uses a different size.
  1005. */
  1006. if (*(ushf*)(match+best_len-1) != scan_end ||
  1007. *(ushf*)match != scan_start) continue;
  1008. /* It is not necessary to compare scan[2] and match[2] since they are
  1009. * always equal when the other bytes match, given that the hash keys
  1010. * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
  1011. * strstart+3, +5, ... up to strstart+257. We check for insufficient
  1012. * lookahead only every 4th comparison; the 128th check will be made
  1013. * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
  1014. * necessary to put more guard bytes at the end of the window, or
  1015. * to check more often for insufficient lookahead.
  1016. */
  1017. Assert(scan[2] == match[2], "scan[2]?");
  1018. scan++, match++;
  1019. do {
  1020. } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
  1021. *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
  1022. *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
  1023. *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
  1024. scan < strend);
  1025. /* The funny "do {}" generates better code on most compilers */
  1026. /* Here, scan <= window+strstart+257 */
  1027. Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
  1028. if (*scan == *match) scan++;
  1029. len = (MAX_MATCH - 1) - (int)(strend-scan);
  1030. scan = strend - (MAX_MATCH-1);
  1031. #else /* UNALIGNED_OK */
  1032. if (match[best_len] != scan_end ||
  1033. match[best_len-1] != scan_end1 ||
  1034. *match != *scan ||
  1035. *++match != scan[1]) continue;
  1036. /* The check at best_len-1 can be removed because it will be made
  1037. * again later. (This heuristic is not always a win.)
  1038. * It is not necessary to compare scan[2] and match[2] since they
  1039. * are always equal when the other bytes match, given that
  1040. * the hash keys are equal and that HASH_BITS >= 8.
  1041. */
  1042. scan += 2, match++;
  1043. Assert(*scan == *match, "match[2]?");
  1044. /* We check for insufficient lookahead only every 8th comparison;
  1045. * the 256th check will be made at strstart+258.
  1046. */
  1047. do {
  1048. } while (*++scan == *++match && *++scan == *++match &&
  1049. *++scan == *++match && *++scan == *++match &&
  1050. *++scan == *++match && *++scan == *++match &&
  1051. *++scan == *++match && *++scan == *++match &&
  1052. scan < strend);
  1053. Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
  1054. len = MAX_MATCH - (int)(strend - scan);
  1055. scan = strend - MAX_MATCH;
  1056. #endif /* UNALIGNED_OK */
  1057. if (len > best_len) {
  1058. s->match_start = cur_match;
  1059. best_len = len;
  1060. if (len >= nice_match) break;
  1061. #ifdef UNALIGNED_OK
  1062. scan_end = *(ushf*)(scan+best_len-1);
  1063. #else
  1064. scan_end1 = scan[best_len-1];
  1065. scan_end = scan[best_len];
  1066. #endif
  1067. }
  1068. } while ((cur_match = prev[cur_match & wmask]) > limit
  1069. && --chain_length != 0);
  1070. if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
  1071. return s->lookahead;
  1072. }
  1073. #endif /* ASMV */
  1074. #else /* FASTEST */
  1075. /* ---------------------------------------------------------------------------
  1076. * Optimized version for FASTEST only
  1077. */
  1078. local uInt longest_match(s, cur_match)
  1079. deflate_state *s;
  1080. IPos cur_match; /* current match */
  1081. {
  1082. register Bytef *scan = s->window + s->strstart; /* current string */
  1083. register Bytef *match; /* matched string */
  1084. register int len; /* length of current match */
  1085. register Bytef *strend = s->window + s->strstart + MAX_MATCH;
  1086. /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
  1087. * It is easy to get rid of this optimization if necessary.
  1088. */
  1089. Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
  1090. Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
  1091. Assert(cur_match < s->strstart, "no future");
  1092. match = s->window + cur_match;
  1093. /* Return failure if the match length is less than 2:
  1094. */
  1095. if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
  1096. /* The check at best_len-1 can be removed because it will be made
  1097. * again later. (This heuristic is not always a win.)
  1098. * It is not necessary to compare scan[2] and match[2] since they
  1099. * are always equal when the other bytes match, given that
  1100. * the hash keys are equal and that HASH_BITS >= 8.
  1101. */
  1102. scan += 2, match += 2;
  1103. Assert(*scan == *match, "match[2]?");
  1104. /* We check for insufficient lookahead only every 8th comparison;
  1105. * the 256th check will be made at strstart+258.
  1106. */
  1107. do {
  1108. } while (*++scan == *++match && *++scan == *++match &&
  1109. *++scan == *++match && *++scan == *++match &&
  1110. *++scan == *++match && *++scan == *++match &&
  1111. *++scan == *++match && *++scan == *++match &&
  1112. scan < strend);
  1113. Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
  1114. len = MAX_MATCH - (int)(strend - scan);
  1115. if (len < MIN_MATCH) return MIN_MATCH - 1;
  1116. s->match_start = cur_match;
  1117. return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
  1118. }
  1119. #endif /* FASTEST */
  1120. #ifdef DEBUG
  1121. /* ===========================================================================
  1122. * Check that the match at match_start is indeed a match.
  1123. */
  1124. local void check_match(s, start, match, length)
  1125. deflate_state *s;
  1126. IPos start, match;
  1127. int length;
  1128. {
  1129. /* check that the match is indeed a match */
  1130. if (zmemcmp(s->window + match,
  1131. s->window + start, length) != EQUAL) {
  1132. fprintf(stderr, " start %u, match %u, length %d\n",
  1133. start, match, length);
  1134. do {
  1135. fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
  1136. } while (--length != 0);
  1137. z_error("invalid match");
  1138. }
  1139. if (z_verbose > 1) {
  1140. fprintf(stderr,"\\[%d,%d]", start-match, length);
  1141. do { putc(s->window[start++], stderr); } while (--length != 0);
  1142. }
  1143. }
  1144. #else
  1145. # define check_match(s, start, match, length)
  1146. #endif /* DEBUG */
  1147. /* ===========================================================================
  1148. * Fill the window when the lookahead becomes insufficient.
  1149. * Updates strstart and lookahead.
  1150. *
  1151. * IN assertion: lookahead < MIN_LOOKAHEAD
  1152. * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
  1153. * At least one byte has been read, or avail_in == 0; reads are
  1154. * performed for at least two bytes (required for the zip translate_eol
  1155. * option -- not supported here).
  1156. */
  1157. local void fill_window(s)
  1158. deflate_state *s;
  1159. {
  1160. register unsigned n, m;
  1161. register Posf *p;
  1162. unsigned more; /* Amount of free space at the end of the window. */
  1163. uInt wsize = s->w_size;
  1164. do {
  1165. more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
  1166. /* Deal with !@#$% 64K limit: */
  1167. if (sizeof(int) <= 2) {
  1168. if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
  1169. more = wsize;
  1170. } else if (more == (unsigned)(-1)) {
  1171. /* Very unlikely, but possible on 16 bit machine if
  1172. * strstart == 0 && lookahead == 1 (input done a byte at time)
  1173. */
  1174. more--;
  1175. }
  1176. }
  1177. /* If the window is almost full and there is insufficient lookahead,
  1178. * move the upper half to the lower one to make room in the upper half.
  1179. */
  1180. if (s->strstart >= wsize+MAX_DIST(s)) {
  1181. zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
  1182. s->match_start -= wsize;
  1183. s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
  1184. s->block_start -= (long) wsize;
  1185. /* Slide the hash table (could be avoided with 32 bit values
  1186. at the expense of memory usage). We slide even when level == 0
  1187. to keep the hash table consistent if we switch back to level > 0
  1188. later. (Using level 0 permanently is not an optimal usage of
  1189. zlib, so we don't care about this pathological case.)
  1190. */
  1191. n = s->hash_size;
  1192. p = &s->head[n];
  1193. do {
  1194. m = *--p;
  1195. *p = (Pos)(m >= wsize ? m-wsize : NIL);
  1196. } while (--n);
  1197. n = wsize;
  1198. #ifndef FASTEST
  1199. p = &s->prev[n];
  1200. do {
  1201. m = *--p;
  1202. *p = (Pos)(m >= wsize ? m-wsize : NIL);
  1203. /* If n is not on any hash chain, prev[n] is garbage but
  1204. * its value will never be used.
  1205. */
  1206. } while (--n);
  1207. #endif
  1208. more += wsize;
  1209. }
  1210. if (s->strm->avail_in == 0) return;
  1211. /* If there was no sliding:
  1212. * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
  1213. * more == window_size - lookahead - strstart
  1214. * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
  1215. * => more >= window_size - 2*WSIZE + 2
  1216. * In the BIG_MEM or MMAP case (not yet supported),
  1217. * window_size == input_size + MIN_LOOKAHEAD &&
  1218. * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
  1219. * Otherwise, window_size == 2*WSIZE so more >= 2.
  1220. * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
  1221. */
  1222. Assert(more >= 2, "more < 2");
  1223. n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
  1224. s->lookahead += n;
  1225. /* Initialize the hash value now that we have some input: */
  1226. if (s->lookahead >= MIN_MATCH) {
  1227. s->ins_h = s->window[s->strstart];
  1228. UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
  1229. #if MIN_MATCH != 3
  1230. Call UPDATE_HASH() MIN_MATCH-3 more times
  1231. #endif
  1232. }
  1233. /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
  1234. * but this is not important since only literal bytes will be emitted.
  1235. */
  1236. } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
  1237. /* If the WIN_INIT bytes after the end of the current data have never been
  1238. * written, then zero those bytes in order to avoid memory check reports of
  1239. * the use of uninitialized (or uninitialised as Julian writes) bytes by
  1240. * the longest match routines. Update the high water mark for the next
  1241. * time through here. WIN_INIT is set to MAX_MATCH since the longest match
  1242. * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
  1243. */
  1244. if (s->high_water < s->window_size) {
  1245. ulg curr = s->strstart + (ulg)(s->lookahead);
  1246. ulg init;
  1247. if (s->high_water < curr) {
  1248. /* Previous high water mark below current data -- zero WIN_INIT
  1249. * bytes or up to end of window, whichever is less.
  1250. */
  1251. init = s->window_size - curr;
  1252. if (init > WIN_INIT)
  1253. init = WIN_INIT;
  1254. zmemzero(s->window + curr, (unsigned)init);
  1255. s->high_water = curr + init;
  1256. }
  1257. else if (s->high_water < (ulg)curr + WIN_INIT) {
  1258. /* High water mark at or above current data, but below current data
  1259. * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
  1260. * to end of window, whichever is less.
  1261. */
  1262. init = (ulg)curr + WIN_INIT - s->high_water;
  1263. if (init > s->window_size - s->high_water)
  1264. init = s->window_size - s->high_water;
  1265. zmemzero(s->window + s->high_water, (unsigned)init);
  1266. s->high_water += init;
  1267. }
  1268. }
  1269. }
  1270. /* ===========================================================================
  1271. * Flush the current block, with given end-of-file flag.
  1272. * IN assertion: strstart is set to the end of the current match.
  1273. */
  1274. #define FLUSH_BLOCK_ONLY(s, last) { \
  1275. _tr_flush_block(s, (s->block_start >= 0L ? \
  1276. (charf *)&s->window[(unsigned)s->block_start] : \
  1277. (charf *)Z_NULL), \
  1278. (ulg)((long)s->strstart - s->block_start), \
  1279. (last)); \
  1280. s->block_start = s->strstart; \
  1281. flush_pending(s->strm); \
  1282. Tracev((stderr,"[FLUSH]")); \
  1283. }
  1284. /* Same but force premature exit if necessary. */
  1285. #define FLUSH_BLOCK(s, last) { \
  1286. FLUSH_BLOCK_ONLY(s, last); \
  1287. if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
  1288. }
  1289. /* ===========================================================================
  1290. * Copy without compression as much as possible from the input stream, return
  1291. * the current block state.
  1292. * This function does not insert new strings in the dictionary since
  1293. * uncompressible data is probably not useful. This function is used
  1294. * only for the level=0 compression option.
  1295. * NOTE: this function should be optimized to avoid extra copying from
  1296. * window to pending_buf.
  1297. */
  1298. local block_state deflate_stored(s, flush)
  1299. deflate_state *s;
  1300. int flush;
  1301. {
  1302. /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
  1303. * to pending_buf_size, and each stored block has a 5 byte header:
  1304. */
  1305. ulg max_block_size = 0xffff;
  1306. ulg max_start;
  1307. if (max_block_size > s->pending_buf_size - 5) {
  1308. max_block_size = s->pending_buf_size - 5;
  1309. }
  1310. /* Copy as much as possible from input to output: */
  1311. for (;;) {
  1312. /* Fill the window as much as possible: */
  1313. if (s->lookahead <= 1) {
  1314. Assert(s->strstart < s->w_size+MAX_DIST(s) ||
  1315. s->block_start >= (long)s->w_size, "slide too late");
  1316. fill_window(s);
  1317. if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
  1318. if (s->lookahead == 0) break; /* flush the current block */
  1319. }
  1320. Assert(s->block_start >= 0L, "block gone");
  1321. s->strstart += s->lookahead;
  1322. s->lookahead = 0;
  1323. /* Emit a stored block if pending_buf will be full: */
  1324. max_start = s->block_start + max_block_size;
  1325. if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
  1326. /* strstart == 0 is possible when wraparound on 16-bit machine */
  1327. s->lookahead = (uInt)(s->strstart - max_start);
  1328. s->strstart = (uInt)max_start;
  1329. FLUSH_BLOCK(s, 0);
  1330. }
  1331. /* Flush if we may have to slide, otherwise block_start may become
  1332. * negative and the data will be gone:
  1333. */
  1334. if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
  1335. FLUSH_BLOCK(s, 0);
  1336. }
  1337. }
  1338. FLUSH_BLOCK(s, flush == Z_FINISH);
  1339. return flush == Z_FINISH ? finish_done : block_done;
  1340. }
  1341. /* ===========================================================================
  1342. * Compress as much as possible from the input stream, return the current
  1343. * block state.
  1344. * This function does not perform lazy evaluation of matches and inserts
  1345. * new strings in the dictionary only for unmatched strings or for short
  1346. * matches. It is used only for the fast compression options.
  1347. */
  1348. local block_state deflate_fast(s, flush)
  1349. deflate_state *s;
  1350. int flush;
  1351. {
  1352. IPos hash_head; /* head of the hash chain */
  1353. int bflush; /* set if current block must be flushed */
  1354. for (;;) {
  1355. /* Make sure that we always have enough lookahead, except
  1356. * at the end of the input file. We need MAX_MATCH bytes
  1357. * for the next match, plus MIN_MATCH bytes to insert the
  1358. * string following the next match.
  1359. */
  1360. if (s->lookahead < MIN_LOOKAHEAD) {
  1361. fill_window(s);
  1362. if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
  1363. return need_more;
  1364. }
  1365. if (s->lookahead == 0) break; /* flush the current block */
  1366. }
  1367. /* Insert the string window[strstart .. strstart+2] in the
  1368. * dictionary, and set hash_head to the head of the hash chain:
  1369. */
  1370. hash_head = NIL;
  1371. if (s->lookahead >= MIN_MATCH) {
  1372. INSERT_STRING(s, s->strstart, hash_head);
  1373. }
  1374. /* Find the longest match, discarding those <= prev_length.
  1375. * At this point we have always match_length < MIN_MATCH
  1376. */
  1377. if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
  1378. /* To simplify the code, we prevent matches with the string
  1379. * of window index 0 (in particular we have to avoid a match
  1380. * of the string with itself at the start of the input file).
  1381. */
  1382. s->match_length = longest_match (s, hash_head);
  1383. /* longest_match() sets match_start */
  1384. }
  1385. if (s->match_length >= MIN_MATCH) {
  1386. check_match(s, s->strstart, s->match_start, s->match_length);
  1387. _tr_tally_dist(s, s->strstart - s->match_start,
  1388. s->match_length - MIN_MATCH, bflush);
  1389. s->lookahead -= s->match_length;
  1390. /* Insert new strings in the hash table only if the match length
  1391. * is not too large. This saves time but degrades compression.
  1392. */
  1393. #ifndef FASTEST
  1394. if (s->match_length <= s->max_insert_length &&
  1395. s->lookahead >= MIN_MATCH) {
  1396. s->match_length--; /* string at strstart already in table */
  1397. do {
  1398. s->strstart++;
  1399. INSERT_STRING(s, s->strstart, hash_head);
  1400. /* strstart never exceeds WSIZE-MAX_MATCH, so there are
  1401. * always MIN_MATCH bytes ahead.
  1402. */
  1403. } while (--s->match_length != 0);
  1404. s->strstart++;
  1405. } else
  1406. #endif
  1407. {
  1408. s->strstart += s->match_length;
  1409. s->match_length = 0;
  1410. s->ins_h = s->window[s->strstart];
  1411. UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
  1412. #if MIN_MATCH != 3
  1413. Call UPDATE_HASH() MIN_MATCH-3 more times
  1414. #endif
  1415. /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
  1416. * matter since it will be recomputed at next deflate call.
  1417. */
  1418. }
  1419. } else {
  1420. /* No match, output a literal byte */
  1421. Tracevv((stderr,"%c", s->window[s->strstart]));
  1422. _tr_tally_lit (s, s->window[s->strstart], bflush);
  1423. s->lookahead--;
  1424. s->strstart++;
  1425. }
  1426. if (bflush) FLUSH_BLOCK(s, 0);
  1427. }
  1428. FLUSH_BLOCK(s, flush == Z_FINISH);
  1429. return flush == Z_FINISH ? finish_done : block_done;
  1430. }
  1431. #ifndef FASTEST
  1432. /* ===========================================================================
  1433. * Same as above, but achieves better compression. We use a lazy
  1434. * evaluation for matches: a match is finally adopted only if there is
  1435. * no better match at the next window position.
  1436. */
  1437. local block_state deflate_slow(s, flush)
  1438. deflate_state *s;
  1439. int flush;
  1440. {
  1441. IPos hash_head; /* head of hash chain */
  1442. int bflush; /* set if current block must be flushed */
  1443. /* Process the input block. */
  1444. for (;;) {
  1445. /* Make sure that we always have enough lookahead, except
  1446. * at the end of the input file. We need MAX_MATCH bytes
  1447. * for the next match, plus MIN_MATCH bytes to insert the
  1448. * string following the next match.
  1449. */
  1450. if (s->lookahead < MIN_LOOKAHEAD) {
  1451. fill_window(s);
  1452. if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
  1453. return need_more;
  1454. }
  1455. if (s->lookahead == 0) break; /* flush the current block */
  1456. }
  1457. /* Insert the string window[strstart .. strstart+2] in the
  1458. * dictionary, and set hash_head to the head of the hash chain:
  1459. */
  1460. hash_head = NIL;
  1461. if (s->lookahead >= MIN_MATCH) {
  1462. INSERT_STRING(s, s->strstart, hash_head);
  1463. }
  1464. /* Find the longest match, discarding those <= prev_length.
  1465. */
  1466. s->prev_length = s->match_length, s->prev_match = s->match_start;
  1467. s->match_length = MIN_MATCH-1;
  1468. if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
  1469. s->strstart - hash_head <= MAX_DIST(s)) {
  1470. /* To simplify the code, we prevent matches with the string
  1471. * of window index 0 (in particular we have to avoid a match
  1472. * of the string with itself at the start of the input file).
  1473. */
  1474. s->match_length = longest_match (s, hash_head);
  1475. /* longest_match() sets match_start */
  1476. if (s->match_length <= 5 && (s->strategy == Z_FILTERED
  1477. #if TOO_FAR <= 32767
  1478. || (s->match_length == MIN_MATCH &&
  1479. s->strstart - s->match_start > TOO_FAR)
  1480. #endif
  1481. )) {
  1482. /* If prev_match is also MIN_MATCH, match_start is garbage
  1483. * but we will ignore the current match anyway.
  1484. */
  1485. s->match_length = MIN_MATCH-1;
  1486. }
  1487. }
  1488. /* If there was a match at the previous step and the current
  1489. * match is not better, output the previous match:
  1490. */
  1491. if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
  1492. uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
  1493. /* Do not insert strings in hash table beyond this. */
  1494. check_match(s, s->strstart-1, s->prev_match, s->prev_length);
  1495. _tr_tally_dist(s, s->strstart -1 - s->prev_match,
  1496. s->prev_length - MIN_MATCH, bflush);
  1497. /* Insert in hash table all strings up to the end of the match.
  1498. * strstart-1 and strstart are already inserted. If there is not
  1499. * enough lookahead, the last two strings are not inserted in
  1500. * the hash table.
  1501. */
  1502. s->lookahead -= s->prev_length-1;
  1503. s->prev_length -= 2;
  1504. do {
  1505. if (++s->strstart <= max_insert) {
  1506. INSERT_STRING(s, s->strstart, hash_head);
  1507. }
  1508. } while (--s->prev_length != 0);
  1509. s->match_available = 0;
  1510. s->match_length = MIN_MATCH-1;
  1511. s->strstart++;
  1512. if (bflush) FLUSH_BLOCK(s, 0);
  1513. } else if (s->match_available) {
  1514. /* If there was no match at the previous position, output a
  1515. * single literal. If there was a match but the current match
  1516. * is longer, truncate the previous match to a single literal.
  1517. */
  1518. Tracevv((stderr,"%c", s->window[s->strstart-1]));
  1519. _tr_tally_lit(s, s->window[s->strstart-1], bflush);
  1520. if (bflush) {
  1521. FLUSH_BLOCK_ONLY(s, 0);
  1522. }
  1523. s->strstart++;
  1524. s->lookahead--;
  1525. if (s->strm->avail_out == 0) return need_more;
  1526. } else {
  1527. /* There is no previous match to compare with, wait for
  1528. * the next step to decide.
  1529. */
  1530. s->match_available = 1;
  1531. s->strstart++;
  1532. s->lookahead--;
  1533. }
  1534. }
  1535. Assert (flush != Z_NO_FLUSH, "no flush?");
  1536. if (s->match_available) {
  1537. Tracevv((stderr,"%c", s->window[s->strstart-1]));
  1538. _tr_tally_lit(s, s->window[s->strstart-1], bflush);
  1539. s->match_available = 0;
  1540. }
  1541. FLUSH_BLOCK(s, flush == Z_FINISH);
  1542. return flush == Z_FINISH ? finish_done : block_done;
  1543. }
  1544. #endif /* FASTEST */
  1545. /* ===========================================================================
  1546. * For Z_RLE, simply look for runs of bytes, generate matches only of distance
  1547. * one. Do not maintain a hash table. (It will be regenerated if this run of
  1548. * deflate switches away from Z_RLE.)
  1549. */
  1550. local block_state deflate_rle(s, flush)
  1551. deflate_state *s;
  1552. int flush;
  1553. {
  1554. int bflush; /* set if current block must be flushed */
  1555. uInt prev; /* byte at distance one to match */
  1556. Bytef *scan, *strend; /* scan goes up to strend for length of run */
  1557. for (;;) {
  1558. /* Make sure that we always have enough lookahead, except
  1559. * at the end of the input file. We need MAX_MATCH bytes
  1560. * for the longest encodable run.
  1561. */
  1562. if (s->lookahead < MAX_MATCH) {
  1563. fill_window(s);
  1564. if (s->lookahead < MAX_MATCH && flush == Z_NO_FLUSH) {
  1565. return need_more;
  1566. }
  1567. if (s->lookahead == 0) break; /* flush the current block */
  1568. }
  1569. /* See how many times the previous byte repeats */
  1570. s->match_length = 0;
  1571. if (s->lookahead >= MIN_MATCH && s->strstart > 0) {
  1572. scan = s->window + s->strstart - 1;
  1573. prev = *scan;
  1574. if (prev == *++scan && prev == *++scan && prev == *++scan) {
  1575. strend = s->window + s->strstart + MAX_MATCH;
  1576. do {
  1577. } while (prev == *++scan && prev == *++scan &&
  1578. prev == *++scan && prev == *++scan &&
  1579. prev == *++scan && prev == *++scan &&
  1580. prev == *++scan && prev == *++scan &&
  1581. scan < strend);
  1582. s->match_length = MAX_MATCH - (int)(strend - scan);
  1583. if (s->match_length > s->lookahead)
  1584. s->match_length = s->lookahead;
  1585. }
  1586. }
  1587. /* Emit match if have run of MIN_MATCH or longer, else emit literal */
  1588. if (s->match_length >= MIN_MATCH) {
  1589. check_match(s, s->strstart, s->strstart - 1, s->match_length);
  1590. _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush);
  1591. s->lookahead -= s->match_length;
  1592. s->strstart += s->match_length;
  1593. s->match_length = 0;
  1594. } else {
  1595. /* No match, output a literal byte */
  1596. Tracevv((stderr,"%c", s->window[s->strstart]));
  1597. _tr_tally_lit (s, s->window[s->strstart], bflush);
  1598. s->lookahead--;
  1599. s->strstart++;
  1600. }
  1601. if (bflush) FLUSH_BLOCK(s, 0);
  1602. }
  1603. FLUSH_BLOCK(s, flush == Z_FINISH);
  1604. return flush == Z_FINISH ? finish_done : block_done;
  1605. }
  1606. /* ===========================================================================
  1607. * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table.
  1608. * (It will be regenerated if this run of deflate switches away from Huffman.)
  1609. */
  1610. local block_state deflate_huff(s, flush)
  1611. deflate_state *s;
  1612. int flush;
  1613. {
  1614. int bflush; /* set if current block must be flushed */
  1615. for (;;) {
  1616. /* Make sure that we have a literal to write. */
  1617. if (s->lookahead == 0) {
  1618. fill_window(s);
  1619. if (s->lookahead == 0) {
  1620. if (flush == Z_NO_FLUSH)
  1621. return need_more;
  1622. break; /* flush the current block */
  1623. }
  1624. }
  1625. /* Output a literal byte */
  1626. s->match_length = 0;
  1627. Tracevv((stderr,"%c", s->window[s->strstart]));
  1628. _tr_tally_lit (s, s->window[s->strstart], bflush);
  1629. s->lookahead--;
  1630. s->strstart++;
  1631. if (bflush) FLUSH_BLOCK(s, 0);
  1632. }
  1633. FLUSH_BLOCK(s, flush == Z_FINISH);
  1634. return flush == Z_FINISH ? finish_done : block_done;
  1635. }