Mes documents/Visual Studio 2005/Projects/TES4ModTranslator/TES4ModTranslator/Zip/Compression/Inflater.cs

Go to the documentation of this file.
00001 // Inflater.cs
00002 //
00003 // Copyright (C) 2001 Mike Krueger
00004 // Copyright (C) 2004 John Reilly
00005 //
00006 // This file was translated from java, it was part of the GNU Classpath
00007 // Copyright (C) 2001 Free Software Foundation, Inc.
00008 //
00009 // This program is free software; you can redistribute it and/or
00010 // modify it under the terms of the GNU General Public License
00011 // as published by the Free Software Foundation; either version 2
00012 // of the License, or (at your option) any later version.
00013 //
00014 // This program is distributed in the hope that it will be useful,
00015 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00016 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00017 // GNU General Public License for more details.
00018 //
00019 // You should have received a copy of the GNU General Public License
00020 // along with this program; if not, write to the Free Software
00021 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
00022 //
00023 // Linking this library statically or dynamically with other modules is
00024 // making a combined work based on this library.  Thus, the terms and
00025 // conditions of the GNU General Public License cover the whole
00026 // combination.
00027 // 
00028 // As a special exception, the copyright holders of this library give you
00029 // permission to link this library with independent modules to produce an
00030 // executable, regardless of the license terms of these independent
00031 // modules, and to copy and distribute the resulting executable under
00032 // terms of your choice, provided that you also meet, for each linked
00033 // independent module, the terms and conditions of the license of that
00034 // module.  An independent module is a module which is not derived from
00035 // or based on this library.  If you modify this library, you may extend
00036 // this exception to your version of the library, but you are not
00037 // obligated to do so.  If you do not wish to do so, delete this
00038 // exception statement from your version.
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                         /* The header is written in "wrong" byte order */
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                         /* Maximum size of the backwards window in bits.
00255                         * We currently ignore this, but we could use it to make the
00256                         * inflater window more space efficient. On the other hand the
00257                         * full window (15 bits) is needed most times, anyway.
00258                         int max_wbits = ((header & 0x7000) >> 12) + 8;
00259                         */
00260                         
00261                         if ((header & 0x0020) == 0) { // Dictionary flag?
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                                                 /* This is the inner loop so it is optimized a bit */
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                                                                 /* symbol == 256: end of block */
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; /* fall through */
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;/* fall through */
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;/* fall through */
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; /* fall through */
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;/* fall through */
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; /* fall through */
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                         // Special case: len may be zero
00677                         if (len == 0) {
00678                                 if (IsFinished == false) { // -jr- 08-Nov-2003 INFLATE_BUG fix..
00679                                         Decode();
00680                                 }
00681                                 return 0;
00682                         }
00683 /*
00684                         // Check for correct buff, off, len triple
00685                         if (off < 0 || off + len >= buf.Length) {
00686                                 throw new ArgumentException("off/len outside buf bounds");
00687                         }
00688 */
00689                         int count = 0;
00690                         int more;
00691                         do {
00692                                 if (mode != DECODE_CHKSUM) {
00693                                         /* Don't give away any output, if we are waiting for the
00694                                         * checksum in the input stream.
00695                                         *
00696                                         * With this trick we have always:
00697                                         *   needsInput() and not finished()
00698                                         *   implies more output can be produced.
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 }

Generated on Fri Jun 23 21:50:04 2006 for OblivionModTranslator by  doxygen 1.4.6-NO