DeflaterEngine.cs 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845
  1. using System;
  2. using ICSharpCode.SharpZipLib.Checksum;
  3. namespace ICSharpCode.SharpZipLib.Zip.Compression
  4. {
  5. /// <summary>
  6. /// Strategies for deflater
  7. /// </summary>
  8. public enum DeflateStrategy
  9. {
  10. /// <summary>
  11. /// The default strategy
  12. /// </summary>
  13. Default = 0,
  14. /// <summary>
  15. /// This strategy will only allow longer string repetitions. It is
  16. /// useful for random data with a small character set.
  17. /// </summary>
  18. Filtered = 1,
  19. /// <summary>
  20. /// This strategy will not look for string repetitions at all. It
  21. /// only encodes with Huffman trees (which means, that more common
  22. /// characters get a smaller encoding.
  23. /// </summary>
  24. HuffmanOnly = 2
  25. }
  26. // DEFLATE ALGORITHM:
  27. //
  28. // The uncompressed stream is inserted into the window array. When
  29. // the window array is full the first half is thrown away and the
  30. // second half is copied to the beginning.
  31. //
  32. // The head array is a hash table. Three characters build a hash value
  33. // and they the value points to the corresponding index in window of
  34. // the last string with this hash. The prev array implements a
  35. // linked list of matches with the same hash: prev[index & WMASK] points
  36. // to the previous index with the same hash.
  37. //
  38. /// <summary>
  39. /// Low level compression engine for deflate algorithm which uses a 32K sliding window
  40. /// with secondary compression from Huffman/Shannon-Fano codes.
  41. /// </summary>
  42. public class DeflaterEngine
  43. {
  44. #region Constants
  45. const int TooFar = 4096;
  46. #endregion
  47. #region Constructors
  48. /// <summary>
  49. /// Construct instance with pending buffer
  50. /// </summary>
  51. /// <param name="pending">
  52. /// Pending buffer to use
  53. /// </param>>
  54. public DeflaterEngine(DeflaterPending pending)
  55. {
  56. this.pending = pending;
  57. huffman = new DeflaterHuffman(pending);
  58. adler = new Adler32();
  59. window = new byte[2 * DeflaterConstants.WSIZE];
  60. head = new short[DeflaterConstants.HASH_SIZE];
  61. prev = new short[DeflaterConstants.WSIZE];
  62. // We start at index 1, to avoid an implementation deficiency, that
  63. // we cannot build a repeat pattern at index 0.
  64. blockStart = strstart = 1;
  65. }
  66. #endregion
  67. /// <summary>
  68. /// Deflate drives actual compression of data
  69. /// </summary>
  70. /// <param name="flush">True to flush input buffers</param>
  71. /// <param name="finish">Finish deflation with the current input.</param>
  72. /// <returns>Returns true if progress has been made.</returns>
  73. public bool Deflate(bool flush, bool finish)
  74. {
  75. bool progress;
  76. do {
  77. FillWindow();
  78. bool canFlush = flush && (inputOff == inputEnd);
  79. #if DebugDeflation
  80. if (DeflaterConstants.DEBUGGING) {
  81. Console.WriteLine("window: [" + blockStart + "," + strstart + ","
  82. + lookahead + "], " + compressionFunction + "," + canFlush);
  83. }
  84. #endif
  85. switch (compressionFunction) {
  86. case DeflaterConstants.DEFLATE_STORED:
  87. progress = DeflateStored(canFlush, finish);
  88. break;
  89. case DeflaterConstants.DEFLATE_FAST:
  90. progress = DeflateFast(canFlush, finish);
  91. break;
  92. case DeflaterConstants.DEFLATE_SLOW:
  93. progress = DeflateSlow(canFlush, finish);
  94. break;
  95. default:
  96. throw new InvalidOperationException("unknown compressionFunction");
  97. }
  98. } while (pending.IsFlushed && progress); // repeat while we have no pending output and progress was made
  99. return progress;
  100. }
  101. /// <summary>
  102. /// Sets input data to be deflated. Should only be called when <code>NeedsInput()</code>
  103. /// returns true
  104. /// </summary>
  105. /// <param name="buffer">The buffer containing input data.</param>
  106. /// <param name="offset">The offset of the first byte of data.</param>
  107. /// <param name="count">The number of bytes of data to use as input.</param>
  108. public void SetInput(byte[] buffer, int offset, int count)
  109. {
  110. if (buffer == null) {
  111. throw new ArgumentNullException("nameof(buffer)");
  112. }
  113. if (offset < 0) {
  114. throw new ArgumentOutOfRangeException("nameof(offset)");
  115. }
  116. if (count < 0) {
  117. throw new ArgumentOutOfRangeException("nameof(count)");
  118. }
  119. if (inputOff < inputEnd) {
  120. throw new InvalidOperationException("Old input was not completely processed");
  121. }
  122. int end = offset + count;
  123. /* We want to throw an ArrayIndexOutOfBoundsException early. The
  124. * check is very tricky: it also handles integer wrap around.
  125. */
  126. if ((offset > end) || (end > buffer.Length)) {
  127. throw new ArgumentOutOfRangeException("nameof(count)");
  128. }
  129. inputBuf = buffer;
  130. inputOff = offset;
  131. inputEnd = end;
  132. }
  133. /// <summary>
  134. /// Determines if more <see cref="SetInput">input</see> is needed.
  135. /// </summary>
  136. /// <returns>Return true if input is needed via <see cref="SetInput">SetInput</see></returns>
  137. public bool NeedsInput()
  138. {
  139. return (inputEnd == inputOff);
  140. }
  141. /// <summary>
  142. /// Set compression dictionary
  143. /// </summary>
  144. /// <param name="buffer">The buffer containing the dictionary data</param>
  145. /// <param name="offset">The offset in the buffer for the first byte of data</param>
  146. /// <param name="length">The length of the dictionary data.</param>
  147. public void SetDictionary(byte[] buffer, int offset, int length)
  148. {
  149. #if DebugDeflation
  150. if (DeflaterConstants.DEBUGGING && (strstart != 1) )
  151. {
  152. throw new InvalidOperationException("strstart not 1");
  153. }
  154. #endif
  155. adler.Update(buffer, offset, length);
  156. if (length < DeflaterConstants.MIN_MATCH) {
  157. return;
  158. }
  159. if (length > DeflaterConstants.MAX_DIST) {
  160. offset += length - DeflaterConstants.MAX_DIST;
  161. length = DeflaterConstants.MAX_DIST;
  162. }
  163. System.Array.Copy(buffer, offset, window, strstart, length);
  164. UpdateHash();
  165. --length;
  166. while (--length > 0) {
  167. InsertString();
  168. strstart++;
  169. }
  170. strstart += 2;
  171. blockStart = strstart;
  172. }
  173. /// <summary>
  174. /// Reset internal state
  175. /// </summary>
  176. public void Reset()
  177. {
  178. huffman.Reset();
  179. adler.Reset();
  180. blockStart = strstart = 1;
  181. lookahead = 0;
  182. totalIn = 0;
  183. prevAvailable = false;
  184. matchLen = DeflaterConstants.MIN_MATCH - 1;
  185. for (int i = 0; i < DeflaterConstants.HASH_SIZE; i++) {
  186. head[i] = 0;
  187. }
  188. for (int i = 0; i < DeflaterConstants.WSIZE; i++) {
  189. prev[i] = 0;
  190. }
  191. }
  192. /// <summary>
  193. /// Reset Adler checksum
  194. /// </summary>
  195. public void ResetAdler()
  196. {
  197. adler.Reset();
  198. }
  199. /// <summary>
  200. /// Get current value of Adler checksum
  201. /// </summary>
  202. public int Adler {
  203. get {
  204. return unchecked((int)adler.Value);
  205. }
  206. }
  207. /// <summary>
  208. /// Total data processed
  209. /// </summary>
  210. public long TotalIn {
  211. get {
  212. return totalIn;
  213. }
  214. }
  215. /// <summary>
  216. /// Get/set the <see cref="DeflateStrategy">deflate strategy</see>
  217. /// </summary>
  218. public DeflateStrategy Strategy {
  219. get {
  220. return strategy;
  221. }
  222. set {
  223. strategy = value;
  224. }
  225. }
  226. /// <summary>
  227. /// Set the deflate level (0-9)
  228. /// </summary>
  229. /// <param name="level">The value to set the level to.</param>
  230. public void SetLevel(int level)
  231. {
  232. if ((level < 0) || (level > 9)) {
  233. throw new ArgumentOutOfRangeException("nameof(level)");
  234. }
  235. goodLength = DeflaterConstants.GOOD_LENGTH[level];
  236. max_lazy = DeflaterConstants.MAX_LAZY[level];
  237. niceLength = DeflaterConstants.NICE_LENGTH[level];
  238. max_chain = DeflaterConstants.MAX_CHAIN[level];
  239. if (DeflaterConstants.COMPR_FUNC[level] != compressionFunction) {
  240. #if DebugDeflation
  241. if (DeflaterConstants.DEBUGGING) {
  242. Console.WriteLine("Change from " + compressionFunction + " to "
  243. + DeflaterConstants.COMPR_FUNC[level]);
  244. }
  245. #endif
  246. switch (compressionFunction) {
  247. case DeflaterConstants.DEFLATE_STORED:
  248. if (strstart > blockStart) {
  249. huffman.FlushStoredBlock(window, blockStart,
  250. strstart - blockStart, false);
  251. blockStart = strstart;
  252. }
  253. UpdateHash();
  254. break;
  255. case DeflaterConstants.DEFLATE_FAST:
  256. if (strstart > blockStart) {
  257. huffman.FlushBlock(window, blockStart, strstart - blockStart,
  258. false);
  259. blockStart = strstart;
  260. }
  261. break;
  262. case DeflaterConstants.DEFLATE_SLOW:
  263. if (prevAvailable) {
  264. huffman.TallyLit(window[strstart - 1] & 0xff);
  265. }
  266. if (strstart > blockStart) {
  267. huffman.FlushBlock(window, blockStart, strstart - blockStart, false);
  268. blockStart = strstart;
  269. }
  270. prevAvailable = false;
  271. matchLen = DeflaterConstants.MIN_MATCH - 1;
  272. break;
  273. }
  274. compressionFunction = DeflaterConstants.COMPR_FUNC[level];
  275. }
  276. }
  277. /// <summary>
  278. /// Fill the window
  279. /// </summary>
  280. public void FillWindow()
  281. {
  282. /* If the window is almost full and there is insufficient lookahead,
  283. * move the upper half to the lower one to make room in the upper half.
  284. */
  285. if (strstart >= DeflaterConstants.WSIZE + DeflaterConstants.MAX_DIST) {
  286. SlideWindow();
  287. }
  288. /* If there is not enough lookahead, but still some input left,
  289. * read in the input
  290. */
  291. if (lookahead < DeflaterConstants.MIN_LOOKAHEAD && inputOff < inputEnd) {
  292. int more = 2 * DeflaterConstants.WSIZE - lookahead - strstart;
  293. if (more > inputEnd - inputOff) {
  294. more = inputEnd - inputOff;
  295. }
  296. System.Array.Copy(inputBuf, inputOff, window, strstart + lookahead, more);
  297. adler.Update(inputBuf, inputOff, more);
  298. inputOff += more;
  299. totalIn += more;
  300. lookahead += more;
  301. }
  302. if (lookahead >= DeflaterConstants.MIN_MATCH) {
  303. UpdateHash();
  304. }
  305. }
  306. void UpdateHash()
  307. {
  308. /*
  309. if (DEBUGGING) {
  310. Console.WriteLine("updateHash: "+strstart);
  311. }
  312. */
  313. ins_h = (window[strstart] << DeflaterConstants.HASH_SHIFT) ^ window[strstart + 1];
  314. }
  315. /// <summary>
  316. /// Inserts the current string in the head hash and returns the previous
  317. /// value for this hash.
  318. /// </summary>
  319. /// <returns>The previous hash value</returns>
  320. int InsertString()
  321. {
  322. short match;
  323. int hash = ((ins_h << DeflaterConstants.HASH_SHIFT) ^ window[strstart + (DeflaterConstants.MIN_MATCH - 1)]) & DeflaterConstants.HASH_MASK;
  324. #if DebugDeflation
  325. if (DeflaterConstants.DEBUGGING)
  326. {
  327. if (hash != (((window[strstart] << (2*HASH_SHIFT)) ^
  328. (window[strstart + 1] << HASH_SHIFT) ^
  329. (window[strstart + 2])) & HASH_MASK)) {
  330. throw new SharpZipBaseException("hash inconsistent: " + hash + "/"
  331. +window[strstart] + ","
  332. +window[strstart + 1] + ","
  333. +window[strstart + 2] + "," + HASH_SHIFT);
  334. }
  335. }
  336. #endif
  337. prev[strstart & DeflaterConstants.WMASK] = match = head[hash];
  338. head[hash] = unchecked((short)strstart);
  339. ins_h = hash;
  340. return match & 0xffff;
  341. }
  342. void SlideWindow()
  343. {
  344. Array.Copy(window, DeflaterConstants.WSIZE, window, 0, DeflaterConstants.WSIZE);
  345. matchStart -= DeflaterConstants.WSIZE;
  346. strstart -= DeflaterConstants.WSIZE;
  347. blockStart -= DeflaterConstants.WSIZE;
  348. // Slide the hash table (could be avoided with 32 bit values
  349. // at the expense of memory usage).
  350. for (int i = 0; i < DeflaterConstants.HASH_SIZE; ++i) {
  351. int m = head[i] & 0xffff;
  352. head[i] = (short)(m >= DeflaterConstants.WSIZE ? (m - DeflaterConstants.WSIZE) : 0);
  353. }
  354. // Slide the prev table.
  355. for (int i = 0; i < DeflaterConstants.WSIZE; i++) {
  356. int m = prev[i] & 0xffff;
  357. prev[i] = (short)(m >= DeflaterConstants.WSIZE ? (m - DeflaterConstants.WSIZE) : 0);
  358. }
  359. }
  360. /// <summary>
  361. /// Find the best (longest) string in the window matching the
  362. /// string starting at strstart.
  363. ///
  364. /// Preconditions:
  365. /// <code>
  366. /// strstart + DeflaterConstants.MAX_MATCH &lt;= window.length.</code>
  367. /// </summary>
  368. /// <param name="curMatch"></param>
  369. /// <returns>True if a match greater than the minimum length is found</returns>
  370. bool FindLongestMatch( int curMatch )
  371. {
  372. int match;
  373. int scan = strstart;
  374. // scanMax is the highest position that we can look at
  375. int scanMax = scan + Math.Min( DeflaterConstants.MAX_MATCH, lookahead ) - 1;
  376. int limit = Math.Max( scan - DeflaterConstants.MAX_DIST, 0 );
  377. byte[] window = this.window;
  378. short[] prev = this.prev;
  379. int chainLength = this.max_chain;
  380. int niceLength = Math.Min( this.niceLength, lookahead );
  381. matchLen = Math.Max( matchLen, DeflaterConstants.MIN_MATCH - 1 );
  382. if (scan + matchLen > scanMax) return false;
  383. byte scan_end1 = window[scan + matchLen - 1];
  384. byte scan_end = window[scan + matchLen];
  385. // Do not waste too much time if we already have a good match:
  386. if (matchLen >= this.goodLength) chainLength >>= 2;
  387. do
  388. {
  389. match = curMatch;
  390. scan = strstart;
  391. if (window[match + matchLen] != scan_end
  392. || window[match + matchLen - 1] != scan_end1
  393. || window[match] != window[scan]
  394. || window[++match] != window[++scan])
  395. {
  396. continue;
  397. }
  398. // scan is set to strstart+1 and the comparison passed, so
  399. // scanMax - scan is the maximum number of bytes we can compare.
  400. // below we compare 8 bytes at a time, so first we compare
  401. // (scanMax - scan) % 8 bytes, so the remainder is a multiple of 8
  402. switch( (scanMax - scan) % 8 )
  403. {
  404. case 1: if (window[++scan] == window[++match]) break;
  405. break;
  406. case 2: if (window[++scan] == window[++match]
  407. && window[++scan] == window[++match]) break;
  408. break;
  409. case 3: if (window[++scan] == window[++match]
  410. && window[++scan] == window[++match]
  411. && window[++scan] == window[++match]) break;
  412. break;
  413. case 4: if (window[++scan] == window[++match]
  414. && window[++scan] == window[++match]
  415. && window[++scan] == window[++match]
  416. && window[++scan] == window[++match]) break;
  417. break;
  418. case 5: if (window[++scan] == window[++match]
  419. && window[++scan] == window[++match]
  420. && window[++scan] == window[++match]
  421. && window[++scan] == window[++match]
  422. && window[++scan] == window[++match]) break;
  423. break;
  424. case 6: if (window[++scan] == window[++match]
  425. && window[++scan] == window[++match]
  426. && window[++scan] == window[++match]
  427. && window[++scan] == window[++match]
  428. && window[++scan] == window[++match]
  429. && window[++scan] == window[++match]) break;
  430. break;
  431. case 7: if (window[++scan] == window[++match]
  432. && window[++scan] == window[++match]
  433. && window[++scan] == window[++match]
  434. && window[++scan] == window[++match]
  435. && window[++scan] == window[++match]
  436. && window[++scan] == window[++match]
  437. && window[++scan] == window[++match]) break;
  438. break;
  439. }
  440. if (window[scan] == window[match])
  441. {
  442. /* We check for insufficient lookahead only every 8th comparison;
  443. * the 256th check will be made at strstart + 258 unless lookahead is
  444. * exhausted first.
  445. */
  446. do
  447. {
  448. if (scan == scanMax)
  449. {
  450. ++scan; // advance to first position not matched
  451. ++match;
  452. break;
  453. }
  454. }
  455. while (window[++scan] == window[++match]
  456. && window[++scan] == window[++match]
  457. && window[++scan] == window[++match]
  458. && window[++scan] == window[++match]
  459. && window[++scan] == window[++match]
  460. && window[++scan] == window[++match]
  461. && window[++scan] == window[++match]
  462. && window[++scan] == window[++match]);
  463. }
  464. if (scan - strstart > matchLen)
  465. {
  466. #if DebugDeflation
  467. if (DeflaterConstants.DEBUGGING && (ins_h == 0) )
  468. Console.Error.WriteLine("Found match: " + curMatch + "-" + (scan - strstart));
  469. #endif
  470. matchStart = curMatch;
  471. matchLen = scan - strstart;
  472. if (matchLen >= niceLength)
  473. break;
  474. scan_end1 = window[scan - 1];
  475. scan_end = window[scan];
  476. }
  477. } while ((curMatch = (prev[curMatch & DeflaterConstants.WMASK] & 0xffff)) > limit && 0 != --chainLength );
  478. return matchLen >= DeflaterConstants.MIN_MATCH;
  479. }
  480. bool DeflateStored(bool flush, bool finish)
  481. {
  482. if (!flush && (lookahead == 0)) {
  483. return false;
  484. }
  485. strstart += lookahead;
  486. lookahead = 0;
  487. int storedLength = strstart - blockStart;
  488. if ((storedLength >= DeflaterConstants.MAX_BLOCK_SIZE) || // Block is full
  489. (blockStart < DeflaterConstants.WSIZE && storedLength >= DeflaterConstants.MAX_DIST) || // Block may move out of window
  490. flush) {
  491. bool lastBlock = finish;
  492. if (storedLength > DeflaterConstants.MAX_BLOCK_SIZE) {
  493. storedLength = DeflaterConstants.MAX_BLOCK_SIZE;
  494. lastBlock = false;
  495. }
  496. #if DebugDeflation
  497. if (DeflaterConstants.DEBUGGING)
  498. {
  499. Console.WriteLine("storedBlock[" + storedLength + "," + lastBlock + "]");
  500. }
  501. #endif
  502. huffman.FlushStoredBlock(window, blockStart, storedLength, lastBlock);
  503. blockStart += storedLength;
  504. return !lastBlock;
  505. }
  506. return true;
  507. }
  508. bool DeflateFast(bool flush, bool finish)
  509. {
  510. if (lookahead < DeflaterConstants.MIN_LOOKAHEAD && !flush) {
  511. return false;
  512. }
  513. while (lookahead >= DeflaterConstants.MIN_LOOKAHEAD || flush) {
  514. if (lookahead == 0) {
  515. // We are flushing everything
  516. huffman.FlushBlock(window, blockStart, strstart - blockStart, finish);
  517. blockStart = strstart;
  518. return false;
  519. }
  520. if (strstart > 2 * DeflaterConstants.WSIZE - DeflaterConstants.MIN_LOOKAHEAD) {
  521. /* slide window, as FindLongestMatch needs this.
  522. * This should only happen when flushing and the window
  523. * is almost full.
  524. */
  525. SlideWindow();
  526. }
  527. int hashHead;
  528. if (lookahead >= DeflaterConstants.MIN_MATCH &&
  529. (hashHead = InsertString()) != 0 &&
  530. strategy != DeflateStrategy.HuffmanOnly &&
  531. strstart - hashHead <= DeflaterConstants.MAX_DIST &&
  532. FindLongestMatch(hashHead)) {
  533. // longestMatch sets matchStart and matchLen
  534. #if DebugDeflation
  535. if (DeflaterConstants.DEBUGGING)
  536. {
  537. for (int i = 0 ; i < matchLen; i++) {
  538. if (window[strstart + i] != window[matchStart + i]) {
  539. throw new SharpZipBaseException("Match failure");
  540. }
  541. }
  542. }
  543. #endif
  544. bool full = huffman.TallyDist(strstart - matchStart, matchLen);
  545. lookahead -= matchLen;
  546. if (matchLen <= max_lazy && lookahead >= DeflaterConstants.MIN_MATCH) {
  547. while (--matchLen > 0) {
  548. ++strstart;
  549. InsertString();
  550. }
  551. ++strstart;
  552. } else {
  553. strstart += matchLen;
  554. if (lookahead >= DeflaterConstants.MIN_MATCH - 1) {
  555. UpdateHash();
  556. }
  557. }
  558. matchLen = DeflaterConstants.MIN_MATCH - 1;
  559. if (!full) {
  560. continue;
  561. }
  562. } else {
  563. // No match found
  564. huffman.TallyLit(window[strstart] & 0xff);
  565. ++strstart;
  566. --lookahead;
  567. }
  568. if (huffman.IsFull()) {
  569. bool lastBlock = finish && (lookahead == 0);
  570. huffman.FlushBlock(window, blockStart, strstart - blockStart, lastBlock);
  571. blockStart = strstart;
  572. return !lastBlock;
  573. }
  574. }
  575. return true;
  576. }
  577. bool DeflateSlow(bool flush, bool finish)
  578. {
  579. if (lookahead < DeflaterConstants.MIN_LOOKAHEAD && !flush) {
  580. return false;
  581. }
  582. while (lookahead >= DeflaterConstants.MIN_LOOKAHEAD || flush) {
  583. if (lookahead == 0) {
  584. if (prevAvailable) {
  585. huffman.TallyLit(window[strstart - 1] & 0xff);
  586. }
  587. prevAvailable = false;
  588. // We are flushing everything
  589. #if DebugDeflation
  590. if (DeflaterConstants.DEBUGGING && !flush)
  591. {
  592. throw new SharpZipBaseException("Not flushing, but no lookahead");
  593. }
  594. #endif
  595. huffman.FlushBlock(window, blockStart, strstart - blockStart,
  596. finish);
  597. blockStart = strstart;
  598. return false;
  599. }
  600. if (strstart >= 2 * DeflaterConstants.WSIZE - DeflaterConstants.MIN_LOOKAHEAD) {
  601. /* slide window, as FindLongestMatch needs this.
  602. * This should only happen when flushing and the window
  603. * is almost full.
  604. */
  605. SlideWindow();
  606. }
  607. int prevMatch = matchStart;
  608. int prevLen = matchLen;
  609. if (lookahead >= DeflaterConstants.MIN_MATCH) {
  610. int hashHead = InsertString();
  611. if (strategy != DeflateStrategy.HuffmanOnly &&
  612. hashHead != 0 &&
  613. strstart - hashHead <= DeflaterConstants.MAX_DIST &&
  614. FindLongestMatch(hashHead)) {
  615. // longestMatch sets matchStart and matchLen
  616. // Discard match if too small and too far away
  617. if (matchLen <= 5 && (strategy == DeflateStrategy.Filtered || (matchLen == DeflaterConstants.MIN_MATCH && strstart - matchStart > TooFar))) {
  618. matchLen = DeflaterConstants.MIN_MATCH - 1;
  619. }
  620. }
  621. }
  622. // previous match was better
  623. if ((prevLen >= DeflaterConstants.MIN_MATCH) && (matchLen <= prevLen)) {
  624. #if DebugDeflation
  625. if (DeflaterConstants.DEBUGGING)
  626. {
  627. for (int i = 0 ; i < matchLen; i++) {
  628. if (window[strstart-1+i] != window[prevMatch + i])
  629. throw new SharpZipBaseException();
  630. }
  631. }
  632. #endif
  633. huffman.TallyDist(strstart - 1 - prevMatch, prevLen);
  634. prevLen -= 2;
  635. do {
  636. strstart++;
  637. lookahead--;
  638. if (lookahead >= DeflaterConstants.MIN_MATCH) {
  639. InsertString();
  640. }
  641. } while (--prevLen > 0);
  642. strstart++;
  643. lookahead--;
  644. prevAvailable = false;
  645. matchLen = DeflaterConstants.MIN_MATCH - 1;
  646. } else {
  647. if (prevAvailable) {
  648. huffman.TallyLit(window[strstart - 1] & 0xff);
  649. }
  650. prevAvailable = true;
  651. strstart++;
  652. lookahead--;
  653. }
  654. if (huffman.IsFull()) {
  655. int len = strstart - blockStart;
  656. if (prevAvailable) {
  657. len--;
  658. }
  659. bool lastBlock = (finish && (lookahead == 0) && !prevAvailable);
  660. huffman.FlushBlock(window, blockStart, len, lastBlock);
  661. blockStart += len;
  662. return !lastBlock;
  663. }
  664. }
  665. return true;
  666. }
  667. #region Instance Fields
  668. // Hash index of string to be inserted
  669. int ins_h;
  670. /// <summary>
  671. /// Hashtable, hashing three characters to an index for window, so
  672. /// that window[index]..window[index+2] have this hash code.
  673. /// Note that the array should really be unsigned short, so you need
  674. /// to and the values with 0xffff.
  675. /// </summary>
  676. short[] head;
  677. /// <summary>
  678. /// <code>prev[index &amp; WMASK]</code> points to the previous index that has the
  679. /// same hash code as the string starting at index. This way
  680. /// entries with the same hash code are in a linked list.
  681. /// Note that the array should really be unsigned short, so you need
  682. /// to and the values with 0xffff.
  683. /// </summary>
  684. short[] prev;
  685. int matchStart;
  686. // Length of best match
  687. int matchLen;
  688. // Set if previous match exists
  689. bool prevAvailable;
  690. int blockStart;
  691. /// <summary>
  692. /// Points to the current character in the window.
  693. /// </summary>
  694. int strstart;
  695. /// <summary>
  696. /// lookahead is the number of characters starting at strstart in
  697. /// window that are valid.
  698. /// So window[strstart] until window[strstart+lookahead-1] are valid
  699. /// characters.
  700. /// </summary>
  701. int lookahead;
  702. /// <summary>
  703. /// This array contains the part of the uncompressed stream that
  704. /// is of relevance. The current character is indexed by strstart.
  705. /// </summary>
  706. byte[] window;
  707. DeflateStrategy strategy;
  708. int max_chain, max_lazy, niceLength, goodLength;
  709. /// <summary>
  710. /// The current compression function.
  711. /// </summary>
  712. int compressionFunction;
  713. /// <summary>
  714. /// The input data for compression.
  715. /// </summary>
  716. byte[] inputBuf;
  717. /// <summary>
  718. /// The total bytes of input read.
  719. /// </summary>
  720. long totalIn;
  721. /// <summary>
  722. /// The offset into inputBuf, where input data starts.
  723. /// </summary>
  724. int inputOff;
  725. /// <summary>
  726. /// The end offset of the input data.
  727. /// </summary>
  728. int inputEnd;
  729. DeflaterPending pending;
  730. DeflaterHuffman huffman;
  731. /// <summary>
  732. /// The adler checksum
  733. /// </summary>
  734. Adler32 adler;
  735. #endregion
  736. }
  737. }