context: // Tree.cs
  // ------------------------------------------------------------------
  //
  // Copyright (c) 2009 Dino Chiesa and Microsoft Corporation.  
  // All rights reserved.
  //
  // This code module is part of DotNetZip, a zipfile class library.
  //
  // ------------------------------------------------------------------
  //
  // This code is licensed under the Microsoft Public License. 
  // See the file License.txt for the license details.
  // More info on: http://dotnetzip.codeplex.com
  //
  // ------------------------------------------------------------------
  //
  // last saved (in emacs): 
  // Time-stamp: <2009-October-28 13:29:50>
  //
  // ------------------------------------------------------------------
  //
  // This module defines classes for zlib compression and
  // decompression. This code is derived from the jzlib implementation of
  // zlib. In keeping with the license for jzlib, the copyright to that
  // code is below.
  //
  // ------------------------------------------------------------------
  // 
  // Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
  // 
  // Redistribution and use in source and binary forms, with or without
  // modification, are permitted provided that the following conditions are met:
  // 
  // 1. Redistributions of source code must retain the above copyright notice,
  // this list of conditions and the following disclaimer.
  // 
  // 2. Redistributions in binary form must reproduce the above copyright 
  // notice, this list of conditions and the following disclaimer in 
  // the documentation and/or other materials provided with the distribution.
  // 
  // 3. The names of the authors may not be used to endorse or promote products
  // derived from this software without specific prior written permission.
  // 
  // THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
  // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
  // INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
  // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  // OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  // EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  // 
  // -----------------------------------------------------------------------
  //
  // This program is based on zlib-1.1.3; credit to authors
  // Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
  // and contributors of zlib.
  //
  // -----------------------------------------------------------------------
  
  
  using System;
  
  namespace AL.Utils.Ionic.Zlib
  {
      sealed class Tree
      {
          private static readonly int HEAP_SIZE = (2 * InternalConstants.L_CODES + 1);
                  
          // extra bits for each length code
          internal static readonly int[] ExtraLengthBits = new int[]
          {
              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
          };
                  
          // extra bits for each distance code
          internal static readonly int[] ExtraDistanceBits = new int[]
          {
              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
          };
                  
          // extra bits for each bit length code
          internal static readonly int[] extra_blbits = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7};
                  
          internal static readonly sbyte[] bl_order = new sbyte[]{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
                  
                  
          // The lengths of the bit length codes are sent in order of decreasing
          // probability, to avoid transmitting the lengths for unused bit
          // length codes.
                  
          internal const int Buf_size = 8 * 2;
                  
          // see definition of array dist_code below
          //internal const int DIST_CODE_LEN = 512;
                  
          private static readonly sbyte[] _dist_code = new sbyte[]
          {
              0,  1,  2,  3,  4,  4,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7, 
              8,  8,  8,  8,  8,  8,  8,  8,  9,  9,  9,  9,  9,  9,  9,  9,
              10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 
              11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 
              12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 
              12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 
              13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 
              13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 
              14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 
              14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 
              14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 
              14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 
              15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 
              15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 
              15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 
              15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 
              0,   0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 
              22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 
              24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 
              25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 
              26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 
              26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 
              27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 
              27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 
              28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 
              28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 
              28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 
              28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 
              29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 
              29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 
              29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 
              29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29
          };
                  
          internal static readonly sbyte[] LengthCode = new sbyte[]
          {
              0,   1,  2,  3,  4,  5,  6,  7,  8,  8,  9,  9, 10, 10, 11, 11,
              12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
              16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
              18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19,
              20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
              21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
              22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
              23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
              24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
              24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
              25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
              25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
              26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
              26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
              27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
              27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28
          };
                  
  
          internal static readonly int[] LengthBase = new int[]
          {
              0,   1,  2,  3,  4,  5,  6,   7,   8,  10,  12,  14, 16, 20, 24, 28,
              32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 0
          };
                  
  
          internal static readonly int[] DistanceBase = new int[]
          {
              0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192,
              256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576
          };
  
          
          /// <summary>
          /// Map from a distance to a distance code.
          /// </summary>
          /// <remarks> 
          /// No side effects. _dist_code[256] and _dist_code[257] are never used.
          /// </remarks>
          internal static int DistanceCode(int dist)
          {
              return (dist < 256)
                  ? _dist_code[dist]
                  : _dist_code[256 + SharedUtils.URShift(dist, 7)];
          }
  
          internal short[] dyn_tree; // the dynamic tree
          internal int max_code; // largest code with non zero frequency
          internal StaticTree staticTree; // the corresponding static tree
                  
          // Compute the optimal bit lengths for a tree and update the total bit length
          // for the current block.
          // IN assertion: the fields freq and dad are set, heap[heap_max] and
          //    above are the tree nodes sorted by increasing frequency.
          // OUT assertions: the field len is set to the optimal bit length, the
          //     array bl_count contains the frequencies for each bit length.
          //     The length opt_len is updated; static_len is also updated if stree is
          //     not null.
          internal void  gen_bitlen(DeflateManager s)
          {
              short[] tree = dyn_tree;
              short[] stree = staticTree.treeCodes;
              int[] extra = staticTree.extraBits;
              int base_Renamed = staticTree.extraBase;
              int max_length = staticTree.maxLength;
              int h; // heap index
              int n, m; // iterate over the tree elements
              int bits; // bit length
  
gt:             int xbits; // extra bits