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 using ICSharpCode.SharpZipLib.Zip.Compression.Streams;
00044
00045 namespace ICSharpCode.SharpZipLib.Zip.Compression
00046 {
00047
00073 public class Inflater
00074 {
00078 static int[] CPLENS = {
00079 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
00080 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
00081 };
00082
00086 static int[] CPLEXT = {
00087 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
00088 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
00089 };
00090
00094 static int[] CPDIST = {
00095 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
00096 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
00097 8193, 12289, 16385, 24577
00098 };
00099
00103 static int[] CPDEXT = {
00104 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
00105 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
00106 12, 12, 13, 13
00107 };
00108
00112 const int DECODE_HEADER = 0;
00113 const int DECODE_DICT = 1;
00114 const int DECODE_BLOCKS = 2;
00115 const int DECODE_STORED_LEN1 = 3;
00116 const int DECODE_STORED_LEN2 = 4;
00117 const int DECODE_STORED = 5;
00118 const int DECODE_DYN_HEADER = 6;
00119 const int DECODE_HUFFMAN = 7;
00120 const int DECODE_HUFFMAN_LENBITS = 8;
00121 const int DECODE_HUFFMAN_DIST = 9;
00122 const int DECODE_HUFFMAN_DISTBITS = 10;
00123 const int DECODE_CHKSUM = 11;
00124 const int FINISHED = 12;
00125
00129 int mode;
00130
00137 int readAdler;
00138
00144 int neededBits;
00145 int repLength;
00146 int repDist;
00147 int uncomprLen;
00148
00154 bool isLastBlock;
00155
00159 int totalOut;
00160
00166 int totalIn;
00167
00173 bool noHeader;
00174
00175 StreamManipulator input;
00176 OutputWindow outputWindow;
00177 InflaterDynHeader dynHeader;
00178 InflaterHuffmanTree litlenTree, distTree;
00179 Adler32 adler;
00180
00185 public Inflater() : this(false)
00186 {
00187 }
00188
00201 public Inflater(bool noHeader)
00202 {
00203 this.noHeader = noHeader;
00204 this.adler = new Adler32();
00205 input = new StreamManipulator();
00206 outputWindow = new OutputWindow();
00207 mode = noHeader ? DECODE_BLOCKS : DECODE_HEADER;
00208 }
00209
00214 public void Reset()
00215 {
00216 mode = noHeader ? DECODE_BLOCKS : DECODE_HEADER;
00217 totalIn = totalOut = 0;
00218 input.Reset();
00219 outputWindow.Reset();
00220 dynHeader = null;
00221 litlenTree = null;
00222 distTree = null;
00223 isLastBlock = false;
00224 adler.Reset();
00225 }
00226
00236 private bool DecodeHeader()
00237 {
00238 int header = input.PeekBits(16);
00239 if (header < 0) {
00240 return false;
00241 }
00242 input.DropBits(16);
00243
00244
00245 header = ((header << 8) | (header >> 8)) & 0xffff;
00246 if (header % 31 != 0) {
00247 throw new SharpZipBaseException("Header checksum illegal");
00248 }
00249
00250 if ((header & 0x0f00) != (Deflater.DEFLATED << 8)) {
00251 throw new SharpZipBaseException("Compression Method unknown");
00252 }
00253
00254
00255
00256
00257
00258
00259
00260
00261 if ((header & 0x0020) == 0) {
00262 mode = DECODE_BLOCKS;
00263 } else {
00264 mode = DECODE_DICT;
00265 neededBits = 32;
00266 }
00267 return true;
00268 }
00269
00276 private bool DecodeDict()
00277 {
00278 while (neededBits > 0) {
00279 int dictByte = input.PeekBits(8);
00280 if (dictByte < 0) {
00281 return false;
00282 }
00283 input.DropBits(8);
00284 readAdler = (readAdler << 8) | dictByte;
00285 neededBits -= 8;
00286 }
00287 return false;
00288 }
00289
00300 private bool DecodeHuffman()
00301 {
00302 int free = outputWindow.GetFreeSpace();
00303 while (free >= 258) {
00304 int symbol;
00305 switch (mode) {
00306 case DECODE_HUFFMAN:
00307
00308 while (((symbol = litlenTree.GetSymbol(input)) & ~0xff) == 0) {
00309 outputWindow.Write(symbol);
00310 if (--free < 258) {
00311 return true;
00312 }
00313 }
00314
00315 if (symbol < 257) {
00316 if (symbol < 0) {
00317 return false;
00318 } else {
00319
00320 distTree = null;
00321 litlenTree = null;
00322 mode = DECODE_BLOCKS;
00323 return true;
00324 }
00325 }
00326
00327 try {
00328 repLength = CPLENS[symbol - 257];
00329 neededBits = CPLEXT[symbol - 257];
00330 } catch (Exception) {
00331 throw new SharpZipBaseException("Illegal rep length code");
00332 }
00333 goto case DECODE_HUFFMAN_LENBITS;
00334
00335 case DECODE_HUFFMAN_LENBITS:
00336 if (neededBits > 0) {
00337 mode = DECODE_HUFFMAN_LENBITS;
00338 int i = input.PeekBits(neededBits);
00339 if (i < 0) {
00340 return false;
00341 }
00342 input.DropBits(neededBits);
00343 repLength += i;
00344 }
00345 mode = DECODE_HUFFMAN_DIST;
00346 goto case DECODE_HUFFMAN_DIST;
00347
00348 case DECODE_HUFFMAN_DIST:
00349 symbol = distTree.GetSymbol(input);
00350 if (symbol < 0) {
00351 return false;
00352 }
00353
00354 try {
00355 repDist = CPDIST[symbol];
00356 neededBits = CPDEXT[symbol];
00357 } catch (Exception) {
00358 throw new SharpZipBaseException("Illegal rep dist code");
00359 }
00360
00361 goto case DECODE_HUFFMAN_DISTBITS;
00362
00363 case DECODE_HUFFMAN_DISTBITS:
00364 if (neededBits > 0) {
00365 mode = DECODE_HUFFMAN_DISTBITS;
00366 int i = input.PeekBits(neededBits);
00367 if (i < 0) {
00368 return false;
00369 }
00370 input.DropBits(neededBits);
00371 repDist += i;
00372 }
00373
00374 outputWindow.Repeat(repLength, repDist);
00375 free -= repLength;
00376 mode = DECODE_HUFFMAN;
00377 break;
00378
00379 default:
00380 throw new SharpZipBaseException("Inflater unknown mode");
00381 }
00382 }
00383 return true;
00384 }
00385
00395 private bool DecodeChksum()
00396 {
00397 while (neededBits > 0) {
00398 int chkByte = input.PeekBits(8);
00399 if (chkByte < 0) {
00400 return false;
00401 }
00402 input.DropBits(8);
00403 readAdler = (readAdler << 8) | chkByte;
00404 neededBits -= 8;
00405 }
00406 if ((int) adler.Value != readAdler) {
00407 throw new SharpZipBaseException("Adler chksum doesn't match: " + (int)adler.Value + " vs. " + readAdler);
00408 }
00409 mode = FINISHED;
00410 return false;
00411 }
00412
00422 private bool Decode()
00423 {
00424 switch (mode) {
00425 case DECODE_HEADER:
00426 return DecodeHeader();
00427 case DECODE_DICT:
00428 return DecodeDict();
00429 case DECODE_CHKSUM:
00430 return DecodeChksum();
00431
00432 case DECODE_BLOCKS:
00433 if (isLastBlock) {
00434 if (noHeader) {
00435 mode = FINISHED;
00436 return false;
00437 } else {
00438 input.SkipToByteBoundary();
00439 neededBits = 32;
00440 mode = DECODE_CHKSUM;
00441 return true;
00442 }
00443 }
00444
00445 int type = input.PeekBits(3);
00446 if (type < 0) {
00447 return false;
00448 }
00449 input.DropBits(3);
00450
00451 if ((type & 1) != 0) {
00452 isLastBlock = true;
00453 }
00454 switch (type >> 1){
00455 case DeflaterConstants.STORED_BLOCK:
00456 input.SkipToByteBoundary();
00457 mode = DECODE_STORED_LEN1;
00458 break;
00459 case DeflaterConstants.STATIC_TREES:
00460 litlenTree = InflaterHuffmanTree.defLitLenTree;
00461 distTree = InflaterHuffmanTree.defDistTree;
00462 mode = DECODE_HUFFMAN;
00463 break;
00464 case DeflaterConstants.DYN_TREES:
00465 dynHeader = new InflaterDynHeader();
00466 mode = DECODE_DYN_HEADER;
00467 break;
00468 default:
00469 throw new SharpZipBaseException("Unknown block type " + type);
00470 }
00471 return true;
00472
00473 case DECODE_STORED_LEN1:
00474 {
00475 if ((uncomprLen = input.PeekBits(16)) < 0) {
00476 return false;
00477 }
00478 input.DropBits(16);
00479 mode = DECODE_STORED_LEN2;
00480 }
00481 goto case DECODE_STORED_LEN2;
00482
00483 case DECODE_STORED_LEN2:
00484 {
00485 int nlen = input.PeekBits(16);
00486 if (nlen < 0) {
00487 return false;
00488 }
00489 input.DropBits(16);
00490 if (nlen != (uncomprLen ^ 0xffff)) {
00491 throw new SharpZipBaseException("broken uncompressed block");
00492 }
00493 mode = DECODE_STORED;
00494 }
00495 goto case DECODE_STORED;
00496
00497 case DECODE_STORED:
00498 {
00499 int more = outputWindow.CopyStored(input, uncomprLen);
00500 uncomprLen -= more;
00501 if (uncomprLen == 0) {
00502 mode = DECODE_BLOCKS;
00503 return true;
00504 }
00505 return !input.IsNeedingInput;
00506 }
00507
00508 case DECODE_DYN_HEADER:
00509 if (!dynHeader.Decode(input)) {
00510 return false;
00511 }
00512
00513 litlenTree = dynHeader.BuildLitLenTree();
00514 distTree = dynHeader.BuildDistTree();
00515 mode = DECODE_HUFFMAN;
00516 goto case DECODE_HUFFMAN;
00517
00518 case DECODE_HUFFMAN:
00519 case DECODE_HUFFMAN_LENBITS:
00520 case DECODE_HUFFMAN_DIST:
00521 case DECODE_HUFFMAN_DISTBITS:
00522 return DecodeHuffman();
00523
00524 case FINISHED:
00525 return false;
00526
00527 default:
00528 throw new SharpZipBaseException("Inflater.Decode unknown mode");
00529 }
00530 }
00531
00541 public void SetDictionary(byte[] buffer)
00542 {
00543 SetDictionary(buffer, 0, buffer.Length);
00544 }
00545
00567 public void SetDictionary(byte[] buffer, int offset, int len)
00568 {
00569 if (!IsNeedingDictionary) {
00570 throw new InvalidOperationException();
00571 }
00572
00573 adler.Update(buffer, offset, len);
00574 if ((int)adler.Value != readAdler) {
00575 throw new SharpZipBaseException("Wrong adler checksum");
00576 }
00577 adler.Reset();
00578 outputWindow.CopyDict(buffer, offset, len);
00579 mode = DECODE_BLOCKS;
00580 }
00581
00589 public void SetInput(byte[] buf)
00590 {
00591 SetInput(buf, 0, buf.Length);
00592 }
00593
00613 public void SetInput(byte[] buffer, int offset, int length)
00614 {
00615 input.SetInput(buffer, offset, length);
00616 totalIn += length;
00617 }
00618
00638 public int Inflate(byte[] buf)
00639 {
00640 return Inflate(buf, 0, buf.Length);
00641 }
00642
00670 public int Inflate(byte[] buf, int offset, int len)
00671 {
00672 if (len < 0) {
00673 throw new ArgumentOutOfRangeException("len < 0");
00674 }
00675
00676
00677 if (len == 0) {
00678 if (IsFinished == false) {
00679 Decode();
00680 }
00681 return 0;
00682 }
00683
00684
00685
00686
00687
00688
00689 int count = 0;
00690 int more;
00691 do {
00692 if (mode != DECODE_CHKSUM) {
00693
00694
00695
00696
00697
00698
00699
00700 more = outputWindow.CopyOutput(buf, offset, len);
00701 adler.Update(buf, offset, more);
00702 offset += more;
00703 count += more;
00704 totalOut += more;
00705 len -= more;
00706 if (len == 0) {
00707 return count;
00708 }
00709 }
00710 } while (Decode() || (outputWindow.GetAvailable() > 0 && mode != DECODE_CHKSUM));
00711 return count;
00712 }
00713
00719 public bool IsNeedingInput {
00720 get {
00721 return input.IsNeedingInput;
00722 }
00723 }
00724
00728 public bool IsNeedingDictionary {
00729 get {
00730 return mode == DECODE_DICT && neededBits == 0;
00731 }
00732 }
00733
00738 public bool IsFinished {
00739 get {
00740 return mode == FINISHED && outputWindow.GetAvailable() == 0;
00741 }
00742 }
00743
00753 public int Adler {
00754 get {
00755 return IsNeedingDictionary ? readAdler : (int) adler.Value;
00756 }
00757 }
00758
00765 public int TotalOut {
00766 get {
00767 return totalOut;
00768 }
00769 }
00770
00777 public int TotalIn {
00778 get {
00779 return totalIn - RemainingInput;
00780 }
00781 }
00782
00783 #if TEST_HAK
00787 public int UnseenInput {
00788 get {
00789 return totalIn - ((input.AvailableBits + 7) >> 3);
00790 }
00791 }
00792
00796 public int PlainTotalIn {
00797 get {
00798 return totalIn;
00799 }
00800 }
00801 #endif
00802
00811 public int RemainingInput {
00812 get {
00813 return input.AvailableBytes;
00814 }
00815 }
00816 }
00817 }