context: // 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 Fomm.SharpZipLib.Zip.Compression.Streams;
  
  namespace Fomm.SharpZipLib.Zip.Compression
  {
    /// <summary>
    ///   Huffman tree used for inflation
    /// </summary>
    internal class InflaterHuffmanTree
    {
      #region Constants
  
      private const int MAX_BITLEN = 15;
  
      #endregion
  
      #region Instance Fields
  
      private short[] tree;
  
      #endregion
  
      /// <summary>
      ///   Literal length tree
      /// </summary>
      public static readonly InflaterHuffmanTree defLitLenTree;
  
      /// <summary>
      ///   Distance tree
      /// </summary>
      public static readonly InflaterHuffmanTree defDistTree;
  
      static InflaterHuffmanTree()
      {
        var codeLengths = new byte[288];
        var 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);
      }
  
      #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
  
      private void BuildTree(byte[] codeLengths)
      {
        var blCount = new int[MAX_BITLEN + 1];
        var nextCode = new int[MAX_BITLEN + 1];
  
        foreach (int bits in codeLengths)
        {
          if (bits > 0)
          {
            blCount[bits]++;
          }
        }
  
        var code = 0;
        var treeSize = 512;
        for (var 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. */
            var start = nextCode[bits] & 0x1ff80;
            var 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];
        var treePtr = 512;
        for (var bits = MAX_BITLEN; bits >= 10; bits--)
        {
          var end = code & 0x1ff80;
          code -= blCount[bits] << (16 - bits);
          var start = code & 0x1ff80;
          for (var i = start; i < end; i += 1 << 7)
          {
            tree[DeflaterHuffman.BitReverse(i)] = (short) ((-treePtr << 4) | bits);
            treePtr += 1 << (bits - 9);
          }
        }
  
        for (var 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];
            var 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;
        int bits;
        if ((lookahead = input.PeekBits(9)) >= 0)
        {
  
gt:         if ((symbol = tree[lookahead]) >= 0)