The Labs \ Source Viewer \ SSCLI \ System.IO.Compression \ Inflater

  1. // ==++==
  2. //
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. //
  14. // zlib.h -- interface of the 'zlib' general purpose compression library
  15. // version 1.2.1, November 17th, 2003
  16. //
  17. // Copyright (C) 1995-2003 Jean-loup Gailly and Mark Adler
  18. //
  19. // This software is provided 'as-is', without any express or implied
  20. // warranty. In no event will the authors be held liable for any damages
  21. // arising from the use of this software.
  22. //
  23. // Permission is granted to anyone to use this software for any purpose,
  24. // including commercial applications, and to alter it and redistribute it
  25. // freely, subject to the following restrictions:
  26. //
  27. // 1. The origin of this software must not be misrepresented; you must not
  28. // claim that you wrote the original software. If you use this software
  29. // in a product, an acknowledgment in the product documentation would be
  30. // appreciated but is not required.
  31. // 2. Altered source versions must be plainly marked as such, and must not be
  32. // misrepresented as being the original software.
  33. // 3. This notice may not be removed or altered from any source distribution.
  34. //
  35. //
  36. // ==--==
  37. namespace System.IO.Compression
  38. {
  39.     using System;
  40.     using System.Diagnostics;
  41.    
  42.     // Do not rearrange the enum values.
  43.     internal enum InflaterState
  44.     {
  45.         ReadingGZIPHeader = 0,
  46.         // Only applies to GZIP
  47.         ReadingBFinal = 2,
  48.         // About to read bfinal bit
  49.         ReadingBType = 3,
  50.         // About to read blockType bits
  51.         ReadingNumLitCodes = 4,
  52.         // About to read # literal codes
  53.         ReadingNumDistCodes = 5,
  54.         // About to read # dist codes
  55.         ReadingNumCodeLengthCodes = 6,
  56.         // About to read # code length codes
  57.         ReadingCodeLengthCodes = 7,
  58.         // In the middle of reading the code length codes
  59.         ReadingTreeCodesBefore = 8,
  60.         // In the middle of reading tree codes (loop top)
  61.         ReadingTreeCodesAfter = 9,
  62.         // In the middle of reading tree codes (extension; code > 15)
  63.         DecodeTop = 10,
  64.         // About to decode a literal (char/match) in a compressed block
  65.         HaveInitialLength = 11,
  66.         // Decoding a match, have the literal code (base length)
  67.         HaveFullLength = 12,
  68.         // Ditto, now have the full match length (incl. extra length bits)
  69.         HaveDistCode = 13,
  70.         // Ditto, now have the distance code also, need extra dist bits
  71. /* uncompressed blocks */       
  72.         UncompressedAligning = 15,
  73.         UncompressedByte1 = 16,
  74.         UncompressedByte2 = 17,
  75.         UncompressedByte3 = 18,
  76.         UncompressedByte4 = 19,
  77.         DecodingUncompressed = 20,
  78.        
  79.         // These three apply only to GZIP
  80.         StartReadingGZIPFooter = 21,
  81.         // (Initialisation for reading footer)
  82.         ReadingGZIPFooter = 22,
  83.         VerifyingGZIPFooter = 23,
  84.        
  85.         Done = 24
  86.         // Finished
  87.     }
  88.    
  89.    
  90.    
  91.     internal enum BlockType
  92.     {
  93.         Uncompressed = 0,
  94.         Static = 1,
  95.         Dynamic = 2
  96.     }
  97.    
  98.     internal class Inflater
  99.     {
  100.         // const tables used in decoding:
  101.        
  102.         // Extra bits for length code 257 - 285.
  103.         private static readonly byte[] extraLengthBits = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
  104.         1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
  105.         4, 4, 4, 4, 5, 5, 5, 5, 0};
  106.        
  107.         // The base length for length code 257 - 285.
  108.         // The formula to get the real length for a length code is lengthBase[code - 257] + (value stored in extraBits)
  109.         private static readonly int[] lengthBase = {3, 4, 5, 6, 7, 8, 9, 10, 11, 13,
  110.         15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
  111.         67, 83, 99, 115, 131, 163, 195, 227, 258};
  112.        
  113.         // The base distance for distance code 0 - 29
  114.         // The real distance for a distance code is distanceBasePosition[code] + (value stored in extraBits)
  115.         private static readonly int[] distanceBasePosition = {1, 2, 3, 4, 5, 7, 9, 13, 17, 25,
  116.         33, 49, 65, 97, 129, 193, 257, 385, 513, 769,
  117.         1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577,
  118.         0, 0};
  119.        
  120.         // code lengths for code length alphabet is stored in following order
  121.         private static readonly byte[] codeOrder = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
  122.         11, 4, 12, 3, 13, 2, 14, 1, 15};
  123.        
  124.         private static readonly byte[] staticDistanceTreeTable = {0, 16, 8, 24, 4, 20, 12, 28, 2, 18,
  125.         10, 26, 6, 22, 14, 30, 1, 17, 9, 25,
  126.         5, 21, 13, 29, 3, 19, 11, 27, 7, 23,
  127.         15, 31};
  128.        
  129.         private OutputWindow output;
  130.         private InputBuffer input;
  131.         HuffmanTree literalLengthTree;
  132.         HuffmanTree distanceTree;
  133.        
  134.         InflaterState state;
  135.         bool using_gzip;
  136.         int bfinal;
  137.         BlockType blockType;
  138.         uint crc32;
  139.         uint streamSize;
  140.        
  141.         // uncompressed block
  142.         byte[] blockLengthBuffer = new byte[4];
  143.         int blockLength;
  144.        
  145.         // compressed block
  146.         private int length;
  147.         private int distanceCode;
  148.         private int extraBits;
  149.        
  150.         private int loopCounter;
  151.         private int literalLengthCodeCount;
  152.         private int distanceCodeCount;
  153.         private int codeLengthCodeCount;
  154.         private int codeArraySize;
  155.         private int lengthCode;
  156.        
  157.         private byte[] codeList;
  158.         // temporary array to store the code length for literal/Length and distance
  159.         private byte[] codeLengthTreeCodeLength;
  160.         HuffmanTree codeLengthTree;
  161.        
  162.         GZipDecoder gZipDecoder;
  163.         // class to decode gzip header and footer
  164.         public Inflater(bool doGZip)
  165.         {
  166.             using_gzip = doGZip;
  167.             output = new OutputWindow();
  168.             input = new InputBuffer();
  169.             gZipDecoder = new GZipDecoder(input);
  170.            
  171.             codeList = new byte[HuffmanTree.MaxLiteralTreeElements + HuffmanTree.MaxDistTreeElements];
  172.             codeLengthTreeCodeLength = new byte[HuffmanTree.NumberOfCodeLengthTreeElements];
  173.             Reset();
  174.         }
  175.        
  176.         public void Reset()
  177.         {
  178.             if (using_gzip) {
  179.                 gZipDecoder.Reset();
  180.                 state = InflaterState.ReadingGZIPHeader;
  181.                 // start by reading GZip Header info
  182.                 streamSize = 0;
  183.                 crc32 = 0;
  184.             }
  185.             else {
  186.                 state = InflaterState.ReadingBFinal;
  187.                 // start by reading BFinal bit
  188.             }
  189.         }
  190.        
  191.         public void SetInput(byte[] inputBytes, int offset, int length)
  192.         {
  193.             input.SetInput(inputBytes, offset, length);
  194.             // append the bytes
  195.         }
  196.        
  197.        
  198.         public bool Finished()
  199.         {
  200.             return (state == InflaterState.Done || state == InflaterState.VerifyingGZIPFooter);
  201.         }
  202.        
  203.         public int AvailableOutput {
  204.             get { return output.AvailableBytes; }
  205.         }
  206.        
  207.         public bool NeedsInput()
  208.         {
  209.             return input.NeedsInput();
  210.         }
  211.        
  212.         public int Inflate(byte[] bytes, int offset, int length)
  213.         {
  214.             // copy bytes from output to outputbytes if we have aviable bytes
  215.             // if buffer is not filled up. keep decoding until no input are available
  216.             // if decodeBlock returns false. Throw an exception.
  217.             int count = 0;
  218.             do {
  219.                 int copied = output.CopyTo(bytes, offset, length);
  220.                 if (copied > 0) {
  221.                     if (using_gzip) {
  222.                         crc32 = DecodeHelper.UpdateCrc32(crc32, bytes, offset, copied);
  223.                         uint n = streamSize + (uint)copied;
  224.                         if (n < streamSize) {
  225.                             // overflow, the gzip stream is probably malicious.
  226.                             throw new InvalidDataException(SR.GetString(SR.StreamSizeOverflow));
  227.                         }
  228.                         streamSize = n;
  229.                     }
  230.                    
  231.                     offset += copied;
  232.                     count += copied;
  233.                     length -= copied;
  234.                 }
  235.                
  236.                 if (length == 0) {
  237.                     // filled in the bytes array
  238.                     break;
  239.                 }
  240.                 // Decode will return false when more input is needed
  241.             }
  242.             while (!Finished() && Decode());
  243.            
  244.             if (state == InflaterState.VerifyingGZIPFooter) {
  245.                 // finished reading CRC
  246.                 // In this case finished is true and output window has all the data.
  247.                 // But some data in output window might not be copied out.
  248.                 if (output.AvailableBytes == 0) {
  249.                     if (crc32 != gZipDecoder.Crc32) {
  250.                         throw new InvalidDataException(SR.GetString(SR.InvalidCRC));
  251.                     }
  252.                    
  253.                     if (streamSize != gZipDecoder.StreamSize) {
  254.                         throw new InvalidDataException(SR.GetString(SR.InvalidStreamSize));
  255.                     }
  256.                 }
  257.             }
  258.            
  259.             return count;
  260.         }
  261.        
  262.         //Each block of compressed data begins with 3 header bits
  263.         // containing the following data:
  264.         // first bit BFINAL
  265.         // next 2 bits BTYPE
  266.         // Note that the header bits do not necessarily begin on a byte
  267.         // boundary, since a block does not necessarily occupy an integral
  268.         // number of bytes.
  269.         // BFINAL is set if and only if this is the last block of the data
  270.         // set.
  271.         // BTYPE specifies how the data are compressed, as follows:
  272.         // 00 - no compression
  273.         // 01 - compressed with fixed Huffman codes
  274.         // 10 - compressed with dynamic Huffman codes
  275.         // 11 - reserved (error)
  276.         // The only difference between the two compressed cases is how the
  277.         // Huffman codes for the literal/length and distance alphabets are
  278.         // defined.
  279.         //
  280.         // This function returns true for success (end of block or output window is full,)
  281.         // false if we are short of input
  282.         //
  283.         private bool Decode()
  284.         {
  285.             bool eob = false;
  286.             bool result = false;
  287.            
  288.             if (Finished()) {
  289.                 return true;
  290.             }
  291.            
  292.             if (using_gzip) {
  293.                 if (state == InflaterState.ReadingGZIPHeader) {
  294.                     if (!gZipDecoder.ReadGzipHeader()) {
  295.                         return false;
  296.                     }
  297.                     state = InflaterState.ReadingBFinal;
  298.                 }
  299.                 else if (state == InflaterState.StartReadingGZIPFooter || state == InflaterState.ReadingGZIPFooter) {
  300.                     if (!gZipDecoder.ReadGzipFooter())
  301.                         return false;
  302.                    
  303.                     state = InflaterState.VerifyingGZIPFooter;
  304.                     return true;
  305.                 }
  306.             }
  307.            
  308.             if (state == InflaterState.ReadingBFinal) {
  309.                 // reading bfinal bit
  310.                 // Need 1 bit
  311.                 if (!input.EnsureBitsAvailable(1))
  312.                     return false;
  313.                
  314.                 bfinal = input.GetBits(1);
  315.                 state = InflaterState.ReadingBType;
  316.             }
  317.            
  318.             if (state == InflaterState.ReadingBType) {
  319.                 // Need 2 bits
  320.                 if (!input.EnsureBitsAvailable(2)) {
  321.                     state = InflaterState.ReadingBType;
  322.                     return false;
  323.                 }
  324.                
  325.                 blockType = (BlockType)input.GetBits(2);
  326.                 if (blockType == BlockType.Dynamic) {
  327.                     Debug.WriteLineIf(CompressionTracingSwitch.Informational, "Decoding Dynamic Block", "Compression");
  328.                     state = InflaterState.ReadingNumLitCodes;
  329.                 }
  330.                 else if (blockType == BlockType.Static) {
  331.                     Debug.WriteLineIf(CompressionTracingSwitch.Informational, "Decoding Static Block", "Compression");
  332.                     literalLengthTree = HuffmanTree.StaticLiteralLengthTree;
  333.                     distanceTree = HuffmanTree.StaticDistanceTree;
  334.                     state = InflaterState.DecodeTop;
  335.                 }
  336.                 else if (blockType == BlockType.Uncompressed) {
  337.                     Debug.WriteLineIf(CompressionTracingSwitch.Informational, "Decoding UnCompressed Block", "Compression");
  338.                     state = InflaterState.UncompressedAligning;
  339.                 }
  340.                 else {
  341.                     throw new InvalidDataException(SR.GetString(SR.UnknownBlockType));
  342.                 }
  343.             }
  344.            
  345.             if (blockType == BlockType.Dynamic) {
  346.                 if (state < InflaterState.DecodeTop) {
  347.                     // we are reading the header
  348.                     result = DecodeDynamicBlockHeader();
  349.                 }
  350.                 else {
  351.                     result = DecodeBlock(out eob);
  352.                     // this can returns true when output is full
  353.                 }
  354.             }
  355.             else if (blockType == BlockType.Static) {
  356.                 result = DecodeBlock(out eob);
  357.             }
  358.             else if (blockType == BlockType.Uncompressed) {
  359.                 result = DecodeUncompressedBlock(out eob);
  360.             }
  361.             else {
  362.                 throw new InvalidDataException(SR.GetString(SR.UnknownBlockType));
  363.             }
  364.            
  365.             //
  366.             // If we reached the end of the block and the block we were decoding had
  367.             // bfinal=1 (final block)
  368.             //
  369.             if (eob && (bfinal != 0)) {
  370.                 if (using_gzip)
  371.                     state = InflaterState.StartReadingGZIPFooter;
  372.                 else
  373.                     state = InflaterState.Done;
  374.             }
  375.             return result;
  376.         }
  377.        
  378.        
  379.         // Format of Non-compressed blocks (BTYPE=00):
  380.         //
  381.         // Any bits of input up to the next byte boundary are ignored.
  382.         // The rest of the block consists of the following information:
  383.         //
  384.         // 0 1 2 3 4...
  385.         // +---+---+---+---+================================+
  386.         // | LEN | NLEN |... LEN bytes of literal data...|
  387.         // +---+---+---+---+================================+
  388.         //
  389.         // LEN is the number of data bytes in the block. NLEN is the
  390.         // one's complement of LEN.
  391.        
  392.         bool DecodeUncompressedBlock(out bool end_of_block)
  393.         {
  394.             end_of_block = false;
  395.             while (true) {
  396.                 switch (state) {
  397.                     case InflaterState.UncompressedAligning:
  398.                        
  399.                         // intial state when calling this function
  400.                         // we must skip to a byte boundary
  401.                         input.SkipToByteBoundary();
  402.                         state = InflaterState.UncompressedByte1;
  403.                         goto case InflaterState.UncompressedByte1;
  404.                         break;
  405.                     case InflaterState.UncompressedByte1:
  406.                     case InflaterState.UncompressedByte2:
  407.                     case InflaterState.UncompressedByte3:
  408.                     case InflaterState.UncompressedByte4:
  409.                        
  410.                         // decoding block length
  411.                         int bits = input.GetBits(8);
  412.                         if (bits < 0) {
  413.                             return false;
  414.                         }
  415.                        
  416.                         blockLengthBuffer[state - InflaterState.UncompressedByte1] = (byte)bits;
  417.                         if (state == InflaterState.UncompressedByte4) {
  418.                            
  419.                             blockLength = blockLengthBuffer[0] + ((int)blockLengthBuffer[1]) * 256;
  420.                             int blockLengthComplement = blockLengthBuffer[2] + ((int)blockLengthBuffer[3]) * 256;
  421.                            
  422.                             // make sure complement matches
  423.                             if ((ushort)blockLength != (ushort)(~blockLengthComplement)) {
  424.                                 throw new InvalidDataException(SR.GetString(SR.InvalidBlockLength));
  425.                             }
  426.                         }
  427.                        
  428.                         state += 1;
  429.                         break;
  430.                     case InflaterState.DecodingUncompressed:
  431.                        
  432.                         // copying block data
  433.                         // Directly copy bytes from input to output.
  434.                         int bytesCopied = output.CopyFrom(input, blockLength);
  435.                         blockLength -= bytesCopied;
  436.                        
  437.                         if (blockLength == 0) {
  438.                             // Done with this block, need to re-init bit buffer for next block
  439.                             state = InflaterState.ReadingBFinal;
  440.                             end_of_block = true;
  441.                             Debug.WriteLineIf(CompressionTracingSwitch.Informational, "End of Block", "Compression");
  442.                             return true;
  443.                         }
  444.                        
  445.                         // We can fail to copy all bytes for two reasons:
  446.                         // Running out of Input
  447.                         // running out of free space in output window
  448.                         if (output.FreeBytes == 0) {
  449.                             return true;
  450.                         }
  451.                        
  452.                         return false;
  453.                     default:
  454.                        
  455.                         Debug.Assert(false, "check why we are here!");
  456.                         throw new InvalidDataException(SR.GetString(SR.UnknownState));
  457.                         break;
  458.                 }
  459.             }
  460.         }
  461.        
  462.         bool DecodeBlock(out bool end_of_block_code_seen)
  463.         {
  464.             end_of_block_code_seen = false;
  465.            
  466.             int freeBytes = output.FreeBytes;
  467.             // it is a little bit faster than frequently accessing the property
  468.             while (freeBytes > 258) {
  469.                 // 258 means we can safely do decoding since maximum repeat length is 258
  470.                
  471.                 int symbol;
  472.                 switch (state) {
  473.                     case InflaterState.DecodeTop:
  474.                        
  475.                         symbol = literalLengthTree.GetNextSymbol(input);
  476.                         if (symbol < 0) {
  477.                             // running out of input
  478.                             return false;
  479.                         }
  480.                        
  481.                         if (symbol < 256) {
  482.                             // literal
  483.                             output.Write((byte)symbol);
  484.                             --freeBytes;
  485.                         }
  486.                         else if (symbol == 256) {
  487.                             // end of block
  488.                             end_of_block_code_seen = true;
  489.                             Debug.WriteLineIf(CompressionTracingSwitch.Informational, "End of Block", "Compression");
  490.                             // Reset state
  491.                             state = InflaterState.ReadingBFinal;
  492.                             return true;
  493.                             // ***********
  494.                         }
  495.                         else {
  496.                             // length/distance pair
  497.                             symbol -= 257;
  498.                             // length code started at 257
  499.                             if (symbol < 8) {
  500.                                 symbol += 3;
  501.                                 // match length = 3,4,5,6,7,8,9,10
  502.                                 extraBits = 0;
  503.                             }
  504.                             else if (symbol == 28) {
  505.                                 // extra bits for code 285 is 0
  506.                                 symbol = 258;
  507.                                 // code 285 means length 258
  508.                                 extraBits = 0;
  509.                             }
  510.                             else {
  511.                                 extraBits = extraLengthBits[symbol];
  512.                                 Debug.Assert(extraBits != 0, "We handle other cases seperately!");
  513.                             }
  514.                             length = symbol;
  515.                             goto case InflaterState.HaveInitialLength;
  516.                         }
  517.                         break;
  518.                     case InflaterState.HaveInitialLength:
  519.                        
  520.                         if (extraBits > 0) {
  521.                             state = InflaterState.HaveInitialLength;
  522.                             int bits = input.GetBits(extraBits);
  523.                             if (bits < 0) {
  524.                                 return false;
  525.                             }
  526.                             length = lengthBase[length] + bits;
  527.                         }
  528.                         state = InflaterState.HaveFullLength;
  529.                         goto case InflaterState.HaveFullLength;
  530.                         break;
  531.                     case InflaterState.HaveFullLength:
  532.                        
  533.                         if (blockType == BlockType.Dynamic) {
  534.                             distanceCode = distanceTree.GetNextSymbol(input);
  535.                         }
  536.                         else {
  537.                             // get distance code directly for static block
  538.                             distanceCode = input.GetBits(5);
  539.                             if (distanceCode >= 0) {
  540.                                 distanceCode = staticDistanceTreeTable[distanceCode];
  541.                             }
  542.                         }
  543.                        
  544.                         if (distanceCode < 0) {
  545.                             // running out input
  546.                             return false;
  547.                         }
  548.                        
  549.                         state = InflaterState.HaveDistCode;
  550.                         goto case InflaterState.HaveDistCode;
  551.                         break;
  552.                     case InflaterState.HaveDistCode:
  553.                        
  554.                         // To avoid a table lookup we note that for distanceCode >= 2,
  555.                         // extra_bits = (distanceCode-2) >> 1
  556.                         int offset;
  557.                         if (distanceCode > 3) {
  558.                             extraBits = (distanceCode - 2) >> 1;
  559.                             int bits = input.GetBits(extraBits);
  560.                             if (bits < 0) {
  561.                                 return false;
  562.                             }
  563.                             offset = distanceBasePosition[distanceCode] + bits;
  564.                         }
  565.                         else {
  566.                             offset = distanceCode + 1;
  567.                         }
  568.                        
  569.                         Debug.Assert(freeBytes >= 258, "following operation is not safe!");
  570.                         output.WriteLengthDistance(length, offset);
  571.                         freeBytes -= length;
  572.                         state = InflaterState.DecodeTop;
  573.                         break;
  574.                     default:
  575.                        
  576.                         Debug.Assert(false, "check why we are here!");
  577.                         throw new InvalidDataException(SR.GetString(SR.UnknownState));
  578.                         break;
  579.                 }
  580.             }
  581.            
  582.             return true;
  583.         }
  584.        
  585.        
  586.         // Format of the dynamic block header:
  587.         // 5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286)
  588.         // 5 Bits: HDIST, # of Distance codes - 1 (1 - 32)
  589.         // 4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19)
  590.         //
  591.         // (HCLEN + 4) x 3 bits: code lengths for the code length
  592.         // alphabet given just above, in the order: 16, 17, 18,
  593.         // 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
  594.         //
  595.         // These code lengths are interpreted as 3-bit integers
  596.         // (0-7); as above, a code length of 0 means the
  597.         // corresponding symbol (literal/length or distance code
  598.         // length) is not used.
  599.         //
  600.         // HLIT + 257 code lengths for the literal/length alphabet,
  601.         // encoded using the code length Huffman code
  602.         //
  603.         // HDIST + 1 code lengths for the distance alphabet,
  604.         // encoded using the code length Huffman code
  605.         //
  606.         // The code length repeat codes can cross from HLIT + 257 to the
  607.         // HDIST + 1 code lengths. In other words, all code lengths form
  608.         // a single sequence of HLIT + HDIST + 258 values.
  609.         bool DecodeDynamicBlockHeader()
  610.         {
  611.             switch (state) {
  612.                 case InflaterState.ReadingNumLitCodes:
  613.                     literalLengthCodeCount = input.GetBits(5);
  614.                     if (literalLengthCodeCount < 0) {
  615.                         return false;
  616.                     }
  617.                     literalLengthCodeCount += 257;
  618.                     state = InflaterState.ReadingNumDistCodes;
  619.                     goto case InflaterState.ReadingNumDistCodes;
  620.                     break;
  621.                 case InflaterState.ReadingNumDistCodes:
  622.                    
  623.                     distanceCodeCount = input.GetBits(5);
  624.                     if (distanceCodeCount < 0) {
  625.                         return false;
  626.                     }
  627.                     distanceCodeCount += 1;
  628.                     state = InflaterState.ReadingNumCodeLengthCodes;
  629.                     goto case InflaterState.ReadingNumCodeLengthCodes;
  630.                     break;
  631.                 case InflaterState.ReadingNumCodeLengthCodes:
  632.                    
  633.                     codeLengthCodeCount = input.GetBits(4);
  634.                     if (codeLengthCodeCount < 0) {
  635.                         return false;
  636.                     }
  637.                     codeLengthCodeCount += 4;
  638.                     loopCounter = 0;
  639.                     state = InflaterState.ReadingCodeLengthCodes;
  640.                     goto case InflaterState.ReadingCodeLengthCodes;
  641.                     break;
  642.                 case InflaterState.ReadingCodeLengthCodes:
  643.                    
  644.                     while (loopCounter < codeLengthCodeCount) {
  645.                         int bits = input.GetBits(3);
  646.                         if (bits < 0) {
  647.                             return false;
  648.                         }
  649.                         codeLengthTreeCodeLength[codeOrder[loopCounter]] = (byte)bits;
  650.                         ++loopCounter;
  651.                     }
  652.                    
  653.                     for (int i = codeLengthCodeCount; i < codeOrder.Length; i++) {
  654.                         codeLengthTreeCodeLength[codeOrder[i]] = 0;
  655.                     }
  656.                    
  657.                     // create huffman tree for code length
  658.                     codeLengthTree = new HuffmanTree(codeLengthTreeCodeLength);
  659.                     codeArraySize = literalLengthCodeCount + distanceCodeCount;
  660.                     loopCounter = 0;
  661.                     // reset loop count
  662.                     state = InflaterState.ReadingTreeCodesBefore;
  663.                     goto case InflaterState.ReadingTreeCodesBefore;
  664.                     break;
  665.                 case InflaterState.ReadingTreeCodesBefore:
  666.                 case InflaterState.ReadingTreeCodesAfter:
  667.                    
  668.                     while (loopCounter < codeArraySize) {
  669.                         if (state == InflaterState.ReadingTreeCodesBefore) {
  670.                             if ((lengthCode = codeLengthTree.GetNextSymbol(input)) < 0) {
  671.                                 return false;
  672.                             }
  673.                         }
  674.                        
  675.                         // The alphabet for code lengths is as follows:
  676.                         // 0 - 15: Represent code lengths of 0 - 15
  677.                         // 16: Copy the previous code length 3 - 6 times.
  678.                         // The next 2 bits indicate repeat length
  679.                         // (0 = 3, ... , 3 = 6)
  680.                         // Example: Codes 8, 16 (+2 bits 11),
  681.                         // 16 (+2 bits 10) will expand to
  682.                         // 12 code lengths of 8 (1 + 6 + 5)
  683.                         // 17: Repeat a code length of 0 for 3 - 10 times.
  684.                         // (3 bits of length)
  685.                         // 18: Repeat a code length of 0 for 11 - 138 times
  686.                         // (7 bits of length)
  687.                         if (lengthCode <= 15) {
  688.                             codeList[loopCounter++] = (byte)lengthCode;
  689.                         }
  690.                         else {
  691.                             if (!input.EnsureBitsAvailable(7)) {
  692.                                 // it doesn't matter if we require more bits here
  693.                                 state = InflaterState.ReadingTreeCodesAfter;
  694.                                 return false;
  695.                             }
  696.                            
  697.                             int repeatCount;
  698.                             if (lengthCode == 16) {
  699.                                 if (loopCounter == 0) {
  700.                                     // can't have "prev code" on first code
  701.                                     throw new InvalidDataException();
  702.                                 }
  703.                                
  704.                                 byte previousCode = codeList[loopCounter - 1];
  705.                                 repeatCount = input.GetBits(2) + 3;
  706.                                
  707.                                 if (loopCounter + repeatCount > codeArraySize) {
  708.                                     throw new InvalidDataException();
  709.                                 }
  710.                                
  711.                                 for (int j = 0; j < repeatCount; j++) {
  712.                                     codeList[loopCounter++] = previousCode;
  713.                                 }
  714.                             }
  715.                             else if (lengthCode == 17) {
  716.                                 repeatCount = input.GetBits(3) + 3;
  717.                                
  718.                                 if (loopCounter + repeatCount > codeArraySize) {
  719.                                     throw new InvalidDataException();
  720.                                 }
  721.                                
  722.                                 for (int j = 0; j < repeatCount; j++) {
  723.                                     codeList[loopCounter++] = 0;
  724.                                 }
  725.                             }
  726.                             else {
  727.                                 // code == 18
  728.                                 repeatCount = input.GetBits(7) + 11;
  729.                                
  730.                                 if (loopCounter + repeatCount > codeArraySize) {
  731.                                     throw new InvalidDataException();
  732.                                 }
  733.                                
  734.                                 for (int j = 0; j < repeatCount; j++) {
  735.                                     codeList[loopCounter++] = 0;
  736.                                 }
  737.                             }
  738.                         }
  739.                         state = InflaterState.ReadingTreeCodesBefore;
  740.                         // we want to read the next code.
  741.                     }
  742.                     break;
  743.                 default:
  744.                    
  745.                     Debug.Assert(false, "check why we are here!");
  746.                     throw new InvalidDataException(SR.GetString(SR.UnknownState));
  747.                     break;
  748.             }
  749.            
  750.             byte[] literalTreeCodeLength = new byte[HuffmanTree.MaxLiteralTreeElements];
  751.             byte[] distanceTreeCodeLength = new byte[HuffmanTree.MaxDistTreeElements];
  752.            
  753.             // Create literal and distance tables
  754.             Array.Copy(codeList, literalTreeCodeLength, literalLengthCodeCount);
  755.             Array.Copy(codeList, literalLengthCodeCount, distanceTreeCodeLength, 0, distanceCodeCount);
  756.            
  757.             // Make sure there is an end-of-block code, otherwise how could we ever end?
  758.             if (literalTreeCodeLength[HuffmanTree.EndOfBlockCode] == 0) {
  759.                 throw new InvalidDataException();
  760.             }
  761.            
  762.             literalLengthTree = new HuffmanTree(literalTreeCodeLength);
  763.             distanceTree = new HuffmanTree(distanceTreeCodeLength);
  764.             state = InflaterState.DecodeTop;
  765.             return true;
  766.         }
  767.     }
  768. }

Developer Fusion