context: #region Derivative Work License (Stability.Data.Compression.ThirdParty)
  
  // Disclaimer: All of the compression algorithms in this assembly are the work of others.
  //             They are aggregated here to provide an easy way to learn about and test
  //             alternative techniques. In the subfolders "Internal\<libname>" you will
  //             find the minimal subset of files needed to expose each algorithm.
  //             In the "Licenses" folder you will find the licensing information for each
  //             of the third-party libraries. Those licenses (if more restrictive than
  //             GPL v3) are meant to override.
  //
  // Namespace : Stability.Data.Compression.ThirdParty.Internal.SharpZipLib.Zip
  // FileName  : InflaterHuffmanTree.cs
  // Created   : 2015-4-25
  // Author    : Bennett R. Stabile (Original and Derivative Work)
  // Copyright : Stability Systems LLC, 2015
  // License   : GPL v3
  // Website   : http://DeltaCodec.CodePlex.com
  
  #endregion // Derivative Work License (Stability.Data.Compression.ThirdParty)
  
  // InflaterHuffmanTree.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 Stability.Data.Compression.ThirdParty.Internal.SharpZipLib.Zip.Streams;
  
  namespace Stability.Data.Compression.ThirdParty.Internal.SharpZipLib.Zip
  {
  	
  	/// <summary>
  	/// Huffman tree used for inflation
  	/// </summary>
  	internal class InflaterHuffmanTree
  	{
  		#region Constants
  		const int MAX_BITLEN = 15;
  		#endregion
  
  		#region Instance Fields
  		short[] tree;
  		#endregion
  
  		/// <summary>
  		/// Literal length tree
  		/// </summary>
  		public static InflaterHuffmanTree defLitLenTree;
  		
  		/// <summary>
  		/// Distance tree
  		/// </summary>
  		public static InflaterHuffmanTree defDistTree;
  		
  		static InflaterHuffmanTree()
  		{
  			try {
  				byte[] codeLengths = new byte[288];
  				int i = 0;
  				while (i < 144) {
  					codeLengths[i++] = 8;
  				}
  				while (i < 256) {
  					codeLengths[i++] = 9;
  				}
  				while (i < 280) {
  					codeLengths[i++] = 7;
  				}
  				while (i < 288) {
  					codeLengths[i++] = 8;
  				}
  				defLitLenTree = new InflaterHuffmanTree(codeLengths);
  				
  				codeLengths = new byte[32];
  				i = 0;
  				while (i < 32) {
  					codeLengths[i++] = 5;
  				}
  				defDistTree = new InflaterHuffmanTree(codeLengths);
  			} catch (Exception) {
  				throw new SharpZipBaseException("InflaterHuffmanTree: static tree length illegal");
  			}
  		}
  
  		#region Constructors
  		/// <summary>
  		/// Constructs a Huffman tree from the array of code lengths.
  		/// </summary>
  		/// <param name = "codeLengths">
  		/// the array of code lengths
  		/// </param>
  		public InflaterHuffmanTree(byte[] codeLengths)
  		{
  			BuildTree(codeLengths);
  		}
  		#endregion
  
  		void BuildTree(byte[] codeLengths)
  		{
  			int[] blCount  = new int[MAX_BITLEN + 1];
  			int[] nextCode = new int[MAX_BITLEN + 1];
  			
  			for (int i = 0; i < codeLengths.Length; i++) {
  				int bits = codeLengths[i];
  				if (bits > 0) {
  					blCount[bits]++;
  				}
  			}
  			
  			int code = 0;
  			int treeSize = 512;
  			for (int bits = 1; bits <= MAX_BITLEN; bits++) {
  				nextCode[bits] = code;
  				code += blCount[bits] << (16 - bits);
  				if (bits >= 10) {
  					/* We need an extra table for bit lengths >= 10. */
  					int start = nextCode[bits] & 0x1ff80;
  					int end   = code & 0x1ff80;
  					treeSize += (end - start) >> (16 - bits);
  				}
  			}
  			
  /* -jr comment this out! doesnt work for dynamic trees and pkzip 2.04g
  			if (code != 65536) 
  			{
  				throw new SharpZipBaseException("Code lengths don't add up properly.");
  			}
  */
  			/* Now create and fill the extra tables from longest to shortest
  			* bit len.  This way the sub trees will be aligned.
  			*/
  			tree = new short[treeSize];
  			int treePtr = 512;
  			for (int bits = MAX_BITLEN; bits >= 10; bits--) {
  				int end   = code & 0x1ff80;
  				code -= blCount[bits] << (16 - bits);
  				int start = code & 0x1ff80;
  				for (int i = start; i < end; i += 1 << 7) {
  					tree[DeflaterHuffman.BitReverse(i)] = (short) ((-treePtr << 4) | bits);
  					treePtr += 1 << (bits-9);
  				}
  			}
  			
  			for (int i = 0; i < codeLengths.Length; i++) {
  				int bits = codeLengths[i];
  				if (bits == 0) {
  					continue;
  				}
  				code = nextCode[bits];
  				int revcode = DeflaterHuffman.BitReverse(code);
  				if (bits <= 9) {
  					do {
  						tree[revcode] = (short) ((i << 4) | bits);
  						revcode += 1 << bits;
  					} while (revcode < 512);
  				} else {
  					int subTree = tree[revcode & 511];
  					int treeLen = 1 << (subTree & 15);
  					subTree = -(subTree >> 4);
  					do {
  						tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
  						revcode += 1 << bits;
  					} while (revcode < treeLen);
  				}
  				nextCode[bits] = code + (1 << (16 - bits));
  			}
  			
  		}
  		
  		/// <summary>
  		/// Reads the next symbol from input.  The symbol is encoded using the
  		/// huffman tree.
  		/// </summary>
  		/// <param name="input">
  		/// input the input source.
  		/// </param>
  		/// <returns>
  		/// the next symbol, or -1 if not enough input is available.
  		/// </returns>
  		public int GetSymbol(StreamManipulator input)
  		{
  			int lookahead, symbol;
  			if ((lookahead = input.PeekBits(9)) >= 0) {
  				if ((symbol = tree[lookahead]) >= 0) {
  					input.DropBits(symbol & 15);
  					return symbol >> 4;
  				}
  				int subtree = -(symbol >> 4);
  				int bitlen = symbol & 15;
  				if ((lookahead = input.PeekBits(bitlen)) >= 0) {
  
gt: 					symbol = tree[subtree | (lookahead >> 9)];