00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 using System;
00041
00042 using ICSharpCode.SharpZipLib.Checksums;
00043
00044 namespace ICSharpCode.SharpZipLib.Zip.Compression
00045 {
00046
00050 public enum DeflateStrategy
00051 {
00055 Default = 0,
00056
00061 Filtered = 1,
00062
00063
00069 HuffmanOnly = 2
00070 }
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00090 public class DeflaterEngine : DeflaterConstants
00091 {
00092 static int TOO_FAR = 4096;
00093
00094 int ins_h;
00095
00102 short[] head;
00103
00111 short[] prev;
00112
00113 int matchStart;
00114 int matchLen;
00115 bool prevAvailable;
00116 int blockStart;
00117
00121 int strstart;
00122
00129 int lookahead;
00130
00135 byte[] window;
00136
00137 DeflateStrategy strategy;
00138 int max_chain, max_lazy, niceLength, goodLength;
00139
00143 int comprFunc;
00144
00148 byte[] inputBuf;
00149
00153 int totalIn;
00154
00158 int inputOff;
00159
00163 int inputEnd;
00164
00165 DeflaterPending pending;
00166 DeflaterHuffman huffman;
00167
00171 Adler32 adler;
00172
00179 public DeflaterEngine(DeflaterPending pending)
00180 {
00181 this.pending = pending;
00182 huffman = new DeflaterHuffman(pending);
00183 adler = new Adler32();
00184
00185 window = new byte[2 * WSIZE];
00186 head = new short[HASH_SIZE];
00187 prev = new short[WSIZE];
00188
00189
00190
00191 blockStart = strstart = 1;
00192 }
00193
00197 public void Reset()
00198 {
00199 huffman.Reset();
00200 adler.Reset();
00201 blockStart = strstart = 1;
00202 lookahead = 0;
00203 totalIn = 0;
00204 prevAvailable = false;
00205 matchLen = MIN_MATCH - 1;
00206
00207 for (int i = 0; i < HASH_SIZE; i++) {
00208 head[i] = 0;
00209 }
00210
00211 for (int i = 0; i < WSIZE; i++) {
00212 prev[i] = 0;
00213 }
00214 }
00215
00219 public void ResetAdler()
00220 {
00221 adler.Reset();
00222 }
00223
00227 public int Adler {
00228 get {
00229 return (int)adler.Value;
00230 }
00231 }
00232
00236 public int TotalIn {
00237 get {
00238 return totalIn;
00239 }
00240 }
00241
00245 public DeflateStrategy Strategy {
00246 get {
00247 return strategy;
00248 }
00249 set {
00250 strategy = value;
00251 }
00252 }
00253
00257 public void SetLevel(int lvl)
00258 {
00259 goodLength = DeflaterConstants.GOOD_LENGTH[lvl];
00260 max_lazy = DeflaterConstants.MAX_LAZY[lvl];
00261 niceLength = DeflaterConstants.NICE_LENGTH[lvl];
00262 max_chain = DeflaterConstants.MAX_CHAIN[lvl];
00263
00264 if (DeflaterConstants.COMPR_FUNC[lvl] != comprFunc) {
00265
00266
00267
00268
00269
00270
00271 switch (comprFunc) {
00272 case DEFLATE_STORED:
00273 if (strstart > blockStart) {
00274 huffman.FlushStoredBlock(window, blockStart,
00275 strstart - blockStart, false);
00276 blockStart = strstart;
00277 }
00278 UpdateHash();
00279 break;
00280 case DEFLATE_FAST:
00281 if (strstart > blockStart) {
00282 huffman.FlushBlock(window, blockStart, strstart - blockStart,
00283 false);
00284 blockStart = strstart;
00285 }
00286 break;
00287 case DEFLATE_SLOW:
00288 if (prevAvailable) {
00289 huffman.TallyLit(window[strstart-1] & 0xff);
00290 }
00291 if (strstart > blockStart) {
00292 huffman.FlushBlock(window, blockStart, strstart - blockStart, false);
00293 blockStart = strstart;
00294 }
00295 prevAvailable = false;
00296 matchLen = MIN_MATCH - 1;
00297 break;
00298 }
00299 comprFunc = COMPR_FUNC[lvl];
00300 }
00301 }
00302
00303 void UpdateHash()
00304 {
00305
00306
00307
00308
00309
00310 ins_h = (window[strstart] << HASH_SHIFT) ^ window[strstart + 1];
00311 }
00312
00318 int InsertString()
00319 {
00320 short match;
00321 int hash = ((ins_h << HASH_SHIFT) ^ window[strstart + (MIN_MATCH -1)]) & HASH_MASK;
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334 prev[strstart & WMASK] = match = head[hash];
00335 head[hash] = (short)strstart;
00336 ins_h = hash;
00337 return match & 0xffff;
00338 }
00339
00340 void SlideWindow()
00341 {
00342 Array.Copy(window, WSIZE, window, 0, WSIZE);
00343 matchStart -= WSIZE;
00344 strstart -= WSIZE;
00345 blockStart -= WSIZE;
00346
00347
00348
00349
00350 for (int i = 0; i < HASH_SIZE; ++i) {
00351 int m = head[i] & 0xffff;
00352 head[i] = (short)(m >= WSIZE ? (m - WSIZE) : 0);
00353 }
00354
00355
00356 for (int i = 0; i < WSIZE; i++) {
00357 int m = prev[i] & 0xffff;
00358 prev[i] = (short)(m >= WSIZE ? (m - WSIZE) : 0);
00359 }
00360 }
00361
00365 public void FillWindow()
00366 {
00367
00368
00369
00370 if (strstart >= WSIZE + MAX_DIST) {
00371 SlideWindow();
00372 }
00373
00374
00375
00376
00377 while (lookahead < DeflaterConstants.MIN_LOOKAHEAD && inputOff < inputEnd) {
00378 int more = 2 * WSIZE - lookahead - strstart;
00379
00380 if (more > inputEnd - inputOff) {
00381 more = inputEnd - inputOff;
00382 }
00383
00384 System.Array.Copy(inputBuf, inputOff, window, strstart + lookahead, more);
00385 adler.Update(inputBuf, inputOff, more);
00386
00387 inputOff += more;
00388 totalIn += more;
00389 lookahead += more;
00390 }
00391
00392 if (lookahead >= MIN_MATCH) {
00393 UpdateHash();
00394 }
00395 }
00396
00407 bool FindLongestMatch(int curMatch)
00408 {
00409 int chainLength = this.max_chain;
00410 int niceLength = this.niceLength;
00411 short[] prev = this.prev;
00412 int scan = this.strstart;
00413 int match;
00414 int best_end = this.strstart + matchLen;
00415 int best_len = Math.Max(matchLen, MIN_MATCH - 1);
00416
00417 int limit = Math.Max(strstart - MAX_DIST, 0);
00418
00419 int strend = strstart + MAX_MATCH - 1;
00420 byte scan_end1 = window[best_end - 1];
00421 byte scan_end = window[best_end];
00422
00423
00424 if (best_len >= this.goodLength) {
00425 chainLength >>= 2;
00426 }
00427
00428
00429
00430
00431 if (niceLength > lookahead) {
00432 niceLength = lookahead;
00433 }
00434
00435
00436
00437
00438
00439
00440 do {
00441
00442
00443
00444
00445
00446 if (window[curMatch + best_len] != scan_end ||
00447 window[curMatch + best_len - 1] != scan_end1 ||
00448 window[curMatch] != window[scan] ||
00449 window[curMatch + 1] != window[scan + 1]) {
00450 continue;
00451 }
00452
00453 match = curMatch + 2;
00454 scan += 2;
00455
00456
00457
00458
00459 while (window[++scan] == window[++match] &&
00460 window[++scan] == window[++match] &&
00461 window[++scan] == window[++match] &&
00462 window[++scan] == window[++match] &&
00463 window[++scan] == window[++match] &&
00464 window[++scan] == window[++match] &&
00465 window[++scan] == window[++match] &&
00466 window[++scan] == window[++match] && scan < strend) ;
00467
00468 if (scan > best_end) {
00469
00470
00471
00472
00473 matchStart = curMatch;
00474 best_end = scan;
00475 best_len = scan - strstart;
00476
00477 if (best_len >= niceLength) {
00478 break;
00479 }
00480
00481 scan_end1 = window[best_end - 1];
00482 scan_end = window[best_end];
00483 }
00484 scan = strstart;
00485 } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit && --chainLength != 0);
00486
00487 matchLen = Math.Min(best_len, lookahead);
00488 return matchLen >= MIN_MATCH;
00489 }
00490
00494 public void SetDictionary(byte[] buffer, int offset, int length)
00495 {
00496
00497
00498
00499
00500
00501 adler.Update(buffer, offset, length);
00502 if (length < MIN_MATCH) {
00503 return;
00504 }
00505 if (length > MAX_DIST) {
00506 offset += length - MAX_DIST;
00507 length = MAX_DIST;
00508 }
00509
00510 System.Array.Copy(buffer, offset, window, strstart, length);
00511
00512 UpdateHash();
00513 --length;
00514 while (--length > 0) {
00515 InsertString();
00516 strstart++;
00517 }
00518 strstart += 2;
00519 blockStart = strstart;
00520 }
00521
00522 bool DeflateStored(bool flush, bool finish)
00523 {
00524 if (!flush && lookahead == 0) {
00525 return false;
00526 }
00527
00528 strstart += lookahead;
00529 lookahead = 0;
00530
00531 int storedLen = strstart - blockStart;
00532
00533 if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) ||
00534 (blockStart < WSIZE && storedLen >= MAX_DIST) ||
00535 flush) {
00536 bool lastBlock = finish;
00537 if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE) {
00538 storedLen = DeflaterConstants.MAX_BLOCK_SIZE;
00539 lastBlock = false;
00540 }
00541
00542
00543
00544
00545
00546
00547
00548 huffman.FlushStoredBlock(window, blockStart, storedLen, lastBlock);
00549 blockStart += storedLen;
00550 return !lastBlock;
00551 }
00552 return true;
00553 }
00554
00555 private bool DeflateFast(bool flush, bool finish)
00556 {
00557 if (lookahead < MIN_LOOKAHEAD && !flush) {
00558 return false;
00559 }
00560
00561 while (lookahead >= MIN_LOOKAHEAD || flush) {
00562 if (lookahead == 0) {
00563
00564 huffman.FlushBlock(window, blockStart, strstart - blockStart, finish);
00565 blockStart = strstart;
00566 return false;
00567 }
00568
00569 if (strstart > 2 * WSIZE - MIN_LOOKAHEAD) {
00570
00571
00572
00573
00574 SlideWindow();
00575 }
00576
00577 int hashHead;
00578 if (lookahead >= MIN_MATCH &&
00579 (hashHead = InsertString()) != 0 &&
00580 strategy != DeflateStrategy.HuffmanOnly &&
00581 strstart - hashHead <= MAX_DIST &&
00582 FindLongestMatch(hashHead)) {
00583
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594 if (huffman.TallyDist(strstart - matchStart, matchLen)) {
00595 bool lastBlock = finish && lookahead == 0;
00596 huffman.FlushBlock(window, blockStart, strstart - blockStart, lastBlock);
00597 blockStart = strstart;
00598 }
00599
00600 lookahead -= matchLen;
00601 if (matchLen <= max_lazy && lookahead >= MIN_MATCH) {
00602 while (--matchLen > 0) {
00603 ++strstart;
00604 InsertString();
00605 }
00606 ++strstart;
00607 } else {
00608 strstart += matchLen;
00609 if (lookahead >= MIN_MATCH - 1) {
00610 UpdateHash();
00611 }
00612 }
00613 matchLen = MIN_MATCH - 1;
00614 continue;
00615 } else {
00616
00617 huffman.TallyLit(window[strstart] & 0xff);
00618 ++strstart;
00619 --lookahead;
00620 }
00621
00622 if (huffman.IsFull()) {
00623 bool lastBlock = finish && lookahead == 0;
00624 huffman.FlushBlock(window, blockStart, strstart - blockStart, lastBlock);
00625 blockStart = strstart;
00626 return !lastBlock;
00627 }
00628 }
00629 return true;
00630 }
00631
00632 bool DeflateSlow(bool flush, bool finish)
00633 {
00634 if (lookahead < MIN_LOOKAHEAD && !flush) {
00635 return false;
00636 }
00637
00638 while (lookahead >= MIN_LOOKAHEAD || flush) {
00639 if (lookahead == 0) {
00640 if (prevAvailable) {
00641 huffman.TallyLit(window[strstart-1] & 0xff);
00642 }
00643 prevAvailable = false;
00644
00645
00646
00647
00648
00649
00650
00651 huffman.FlushBlock(window, blockStart, strstart - blockStart,
00652 finish);
00653 blockStart = strstart;
00654 return false;
00655 }
00656
00657 if (strstart >= 2 * WSIZE - MIN_LOOKAHEAD) {
00658
00659
00660
00661
00662 SlideWindow();
00663 }
00664
00665 int prevMatch = matchStart;
00666 int prevLen = matchLen;
00667 if (lookahead >= MIN_MATCH) {
00668 int hashHead = InsertString();
00669 if (strategy != DeflateStrategy.HuffmanOnly && hashHead != 0 && strstart - hashHead <= MAX_DIST && FindLongestMatch(hashHead)) {
00670
00671
00672
00673 if (matchLen <= 5 && (strategy == DeflateStrategy.Filtered || (matchLen == MIN_MATCH && strstart - matchStart > TOO_FAR))) {
00674 matchLen = MIN_MATCH - 1;
00675 }
00676 }
00677 }
00678
00679
00680 if (prevLen >= MIN_MATCH && matchLen <= prevLen) {
00681
00682
00683
00684
00685
00686
00687
00688
00689 huffman.TallyDist(strstart - 1 - prevMatch, prevLen);
00690 prevLen -= 2;
00691 do {
00692 strstart++;
00693 lookahead--;
00694 if (lookahead >= MIN_MATCH) {
00695 InsertString();
00696 }
00697 } while (--prevLen > 0);
00698 strstart ++;
00699 lookahead--;
00700 prevAvailable = false;
00701 matchLen = MIN_MATCH - 1;
00702 } else {
00703 if (prevAvailable) {
00704 huffman.TallyLit(window[strstart-1] & 0xff);
00705 }
00706 prevAvailable = true;
00707 strstart++;
00708 lookahead--;
00709 }
00710
00711 if (huffman.IsFull()) {
00712 int len = strstart - blockStart;
00713 if (prevAvailable) {
00714 len--;
00715 }
00716 bool lastBlock = (finish && lookahead == 0 && !prevAvailable);
00717 huffman.FlushBlock(window, blockStart, len, lastBlock);
00718 blockStart += len;
00719 return !lastBlock;
00720 }
00721 }
00722 return true;
00723 }
00724
00728 public bool Deflate(bool flush, bool finish)
00729 {
00730 bool progress;
00731 do {
00732 FillWindow();
00733 bool canFlush = flush && inputOff == inputEnd;
00734
00735
00736
00737
00738 switch (comprFunc) {
00739 case DEFLATE_STORED:
00740 progress = DeflateStored(canFlush, finish);
00741 break;
00742 case DEFLATE_FAST:
00743 progress = DeflateFast(canFlush, finish);
00744 break;
00745 case DEFLATE_SLOW:
00746 progress = DeflateSlow(canFlush, finish);
00747 break;
00748 default:
00749 throw new InvalidOperationException("unknown comprFunc");
00750 }
00751 } while (pending.IsFlushed && progress);
00752 return progress;
00753 }
00754
00755
00763 public void SetInput(byte[] buf, int off, int len)
00764 {
00765 if (inputOff < inputEnd) {
00766 throw new InvalidOperationException("Old input was not completely processed");
00767 }
00768
00769 int end = off + len;
00770
00771
00772
00773
00774 if (0 > off || off > end || end > buf.Length) {
00775 throw new ArgumentOutOfRangeException();
00776 }
00777
00778 inputBuf = buf;
00779 inputOff = off;
00780 inputEnd = end;
00781 }
00782
00786 public bool NeedsInput()
00787 {
00788 return inputEnd == inputOff;
00789 }
00790 }
00791 }