inflater.cs

没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的

// Inflater.cs
// Copyright (C) 2001 Mike Krueger
//
// This file was translated from java, it was part of the GNU Classpath
// Copyright (C) 2001 Free Software Foundation, Inc.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//
// Linking this library statically or dynamically with other modules is
// making a combined work based on this library.  Thus, the terms and
// conditions of the GNU General Public License cover the whole
// combination.
// 
// As a special exception, the copyright holders of this library give you
// permission to link this library with independent modules to produce an
// executable, regardless of the license terms of these independent
// modules, and to copy and distribute the resulting executable under
// terms of your choice, provided that you also meet, for each linked
// independent module, the terms and conditions of the license of that
// module.  An independent module is a module which is not derived from
// or based on this library.  If you modify this library, you may extend
// this exception to your version of the library, but you are not
// obligated to do so.  If you do not wish to do so, delete this
// exception statement from your version.

using System;

using ICSharpCode.SharpZipLib.Checksums;
using ICSharpCode.SharpZipLib.Zip.Compression.Streams;

namespace ICSharpCode.SharpZipLib.Zip.Compression 
{
	
	/// <summary>
	/// Inflater is used to decompress data that has been compressed according
	/// to the "deflate" standard described in rfc1950.
	///
	/// The usage is as following.  First you have to set some input with
	/// <code>setInput()</code>, then inflate() it.  If inflate doesn't
	/// inflate any bytes there may be three reasons:
	/// <ul>
	/// <li>needsInput() returns true because the input buffer is empty.
	/// You have to provide more input with <code>setInput()</code>.
	/// NOTE: needsInput() also returns true when, the stream is finished.
	/// </li>
	/// <li>needsDictionary() returns true, you have to provide a preset
	///    dictionary with <code>setDictionary()</code>.</li>
	/// <li>finished() returns true, the inflater has finished.</li>
	/// </ul>
	/// Once the first output byte is produced, a dictionary will not be
	/// needed at a later stage.
	///
	/// author of the original java version : John Leuner, Jochen Hoenicke
	/// </summary>
	public class Inflater
	{
		/// <summary>
		/// Copy lengths for literal codes 257..285
		/// </summary>
		private static int[] CPLENS = {
										  3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
										  35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
									  };
		
		/// <summary>
		/// Extra bits for literal codes 257..285
		/// </summary>
		private static int[] CPLEXT = {
										  0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
										  3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
									  };
		
		/// <summary>
		/// Copy offsets for distance codes 0..29
		/// </summary>
		private static int[] CPDIST = {
										  1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
										  257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
										  8193, 12289, 16385, 24577
									  };
		
		/// <summary>
		/// Extra bits for distance codes
		/// </summary>
		private static int[] CPDEXT = {
										  0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
										  7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
										  12, 12, 13, 13
									  };
		
		/// <summary>
		/// This are the state in which the inflater can be.
		/// </summary>
		private const int DECODE_HEADER           = 0;
		private const int DECODE_DICT             = 1;
		private const int DECODE_BLOCKS           = 2;
		private const int DECODE_STORED_LEN1      = 3;
		private const int DECODE_STORED_LEN2      = 4;
		private const int DECODE_STORED           = 5;
		private const int DECODE_DYN_HEADER       = 6;
		private const int DECODE_HUFFMAN          = 7;
		private const int DECODE_HUFFMAN_LENBITS  = 8;
		private const int DECODE_HUFFMAN_DIST     = 9;
		private const int DECODE_HUFFMAN_DISTBITS = 10;
		private const int DECODE_CHKSUM           = 11;
		private const int FINISHED                = 12;
		
		/// <summary>
		/// This variable contains the current state.
		/// </summary>
		private int mode;
		
		/// <summary>
		/// The adler checksum of the dictionary or of the decompressed
		/// stream, as it is written in the header resp. footer of the
		/// compressed stream. 
		/// Only valid if mode is DECODE_DICT or DECODE_CHKSUM.
		/// </summary>
		private int readAdler;
		
		/// <summary>
		/// The number of bits needed to complete the current state.  This
		/// is valid, if mode is DECODE_DICT, DECODE_CHKSUM,
		/// DECODE_HUFFMAN_LENBITS or DECODE_HUFFMAN_DISTBITS.
		/// </summary>
		private int neededBits;
		private int repLength, repDist;
		private int uncomprLen;
		
		/// <summary>
		/// True, if the last block flag was set in the last block of the
		/// inflated stream.  This means that the stream ends after the
		/// current block.
		/// </summary>
		private bool isLastBlock;
		
		/// <summary>
		/// The total number of inflated bytes.
		/// </summary>
		private int totalOut;
		
		/// <summary>
		/// The total number of bytes set with setInput().  This is not the
		/// value returned by getTotalIn(), since this also includes the
		/// unprocessed input.
		/// </summary>
		private int totalIn;
		
		/// <summary>
		/// This variable stores the nowrap flag that was given to the constructor.
		/// True means, that the inflated stream doesn't contain a header nor the
		/// checksum in the footer.
		/// </summary>
		private bool nowrap;
		
		private StreamManipulator input;
		private OutputWindow outputWindow;
		private InflaterDynHeader dynHeader;
		private InflaterHuffmanTree litlenTree, distTree;
		private Adler32 adler;
		
		/// <summary>
		/// Creates a new inflater.
		/// </summary>
		public Inflater() : this(false)
		{
		}
		
		/// <summary>
		/// Creates a new inflater.
		/// </summary>
		/// <param name="nowrap">
		/// true if no header and checksum field appears in the
		/// stream.  This is used for GZIPed input.  For compatibility with
		/// Sun JDK you should provide one byte of input more than needed in
		/// this case.
		/// </param>
		public Inflater(bool nowrap)
		{
			this.nowrap = nowrap;
			this.adler = new Adler32();
			input = new StreamManipulator();
			outputWindow = new OutputWindow();
			mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
		}
		
		/// <summary>
		/// Resets the inflater so that a new stream can be decompressed.  All
		/// pending input and output will be discarded.
		/// </summary>
		public void Reset()
		{
			mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
			totalIn = totalOut = 0;
			input.Reset();
			outputWindow.Reset();
			dynHeader = null;
			litlenTree = null;
			distTree = null;
			isLastBlock = false;
			adler.Reset();
		}
		
		/// <summary>
		/// Decodes the deflate header.
		/// </summary>
		/// <returns>
		/// false if more input is needed.
		/// </returns>
		/// <exception cref="System.FormatException">
		/// if header is invalid.
		/// </exception>
		private bool DecodeHeader()
		{
			int header = input.PeekBits(16);
			if (header < 0) 
			{
				return false;
			}
			input.DropBits(16);
			/* The header is written in "wrong" byte order */
			header = ((header << 8) | (header >> 8)) & 0xffff;
			if (header % 31 != 0) 
			{
				throw new FormatException("Header checksum illegal");
			}
			
			if ((header & 0x0f00) != (Deflater.DEFLATED << 8)) 
			{
				throw new FormatException("Compression Method unknown");
			}
			
			/* Maximum size of the backwards window in bits.
			* We currently ignore this, but we could use it to make the
			* inflater window more space efficient. On the other hand the
			* full window (15 bits) is needed most times, anyway.
			int max_wbits = ((header & 0x7000) >> 12) + 8;
			*/
			
			if ((header & 0x0020) == 0) 
			{ // Dictionary flag?
				mode = DECODE_BLOCKS;
			} 
			else 
			{
				mode = DECODE_DICT;
				neededBits = 32;
			}
			return true;
		}
		
		/// <summary>
		/// Decodes the dictionary checksum after the deflate header.
		/// </summary>
		/// <returns>
		/// false if more input is needed.
		/// </returns>
		private bool DecodeDict()
		{
			while (neededBits > 0) 
			{
				int dictByte = input.PeekBits(8);
				if (dictByte < 0) 
				{
					return false;
				}
				input.DropBits(8);
				readAdler = (readAdler << 8) | dictByte;
				neededBits -= 8;
			}
			return false;
		}
		
		/// <summary>
		/// Decodes the huffman encoded symbols in the input stream.
		/// </summary>
		/// <returns>
		/// false if more input is needed, true if output window is
		/// full or the current block ends.
		/// </returns>
		/// <exception cref="System.FormatException">
		/// if deflated stream is invalid.
		/// </exception>
		private bool DecodeHuffman()
		{
			int free = outputWindow.GetFreeSpace();
			while (free >= 258) 
			{
				int symbol;
				switch (mode) 
				{
					case DECODE_HUFFMAN:
						/* This is the inner loop so it is optimized a bit */
						while (((symbol = litlenTree.GetSymbol(input)) & ~0xff) == 0) 
						{
							outputWindow.Write(symbol);
							if (--free < 258) 
							{
								return true;
							}
						}
						if (symbol < 257) 
						{
							if (symbol < 0) 
							{
								return false;
							} 
							else 
							{
								/* symbol == 256: end of block */
								distTree = null;
								litlenTree = null;
								mode = DECODE_BLOCKS;
								return true;
							}
						}
						
						try 
						{
							repLength = CPLENS[symbol - 257];
							neededBits = CPLEXT[symbol - 257];
						} 
						catch (Exception) 
						{
							throw new FormatException("Illegal rep length code");
						}
						goto case DECODE_HUFFMAN_LENBITS;/* fall through */
					case DECODE_HUFFMAN_LENBITS:
						if (neededBits > 0) 
						{
							mode = DECODE_HUFFMAN_LENBITS;
							int i = input.PeekBits(neededBits);
							if (i < 0) 
							{
								return false;
							}
							input.DropBits(neededBits);
							repLength += i;
						}
						mode = DECODE_HUFFMAN_DIST;
						goto case DECODE_HUFFMAN_DIST;/* fall through */
					case DECODE_HUFFMAN_DIST:
						symbol = distTree.GetSymbol(input);
						if (symbol < 0) 
						{
							return false;
						}
						try 
						{
							repDist = CPDIST[symbol];
							neededBits = CPDEXT[symbol];
						} 
						catch (Exception) 
						{
							throw new FormatException("Illegal rep dist code");
						}
						
						goto case DECODE_HUFFMAN_DISTBITS;/* fall through */
					case DECODE_HUFFMAN_DISTBITS:
						if (neededBits > 0) 
						{
							mode = DECODE_HUFFMAN_DISTBITS;
							int i = input.PeekBits(neededBits);
							if (i < 0) 
							{
								return false;
							}
							input.DropBits(neededBits);
							repDist += i;
						}
						outputWindow.Repeat(repLength, repDist);
						free -= repLength;
						mode = DECODE_HUFFMAN;
						break;
					default:
						throw new FormatException();
				}
			}
			return true;
		}
		
		/// <summary>
		/// Decodes the adler checksum after the deflate stream.
		/// </summary>
		/// <returns>
		/// false if more input is needed.
		/// </returns>
		/// <exception cref="System.FormatException">
		/// DataFormatException, if checksum doesn't match.
		/// </exception>
		private bool DecodeChksum()
		{
			while (neededBits > 0) 
			{
				int chkByte = input.PeekBits(8);
				if (chkByte < 0) 
				{
					return false;
				}
				input.DropBits(8);
				readAdler = (readAdler << 8) | chkByte;
				neededBits -= 8;
			}
			if ((int) adler.Value != readAdler) 
			{
				throw new FormatException("Adler chksum doesn't match: "
					+ (int)adler.Value
					+ " vs. " + readAdler);
			}
			mode = FINISHED;
			return false;
		}