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

  1. //------------------------------------------------------------------------------
  2. // <copyright file="HuffmanTree.cs" company="Microsoft">
  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. // </copyright>
  14. //------------------------------------------------------------------------------
  15. namespace System.IO.Compression
  16. {
  17.     using System;
  18.     using System.Diagnostics;
  19.    
  20.     // Strictly speaking this class is not a HuffmanTree, this class is
  21.     // a lookup table combined with a HuffmanTree. The idea is to speed up
  22.     // the lookup for short symbols (they should appear more frequently ideally.)
  23.     // However we don't want to create a huge table since it might take longer to
  24.     // build the table than decoding (Deflate usually generates new tables frequently.)
  25.     //
  26.     // Jean-loup Gailly and Mark Adler gave a very good explanation about this.
  27.     // The full text (algorithm.txt) can be found inside
  28.     // ftp://ftp.uu.net/pub/archiving/zip/zlib/zlib.zip.
  29.     //
  30.     // Following paper explains decoding in details:
  31.     // Hirschberg and Lelewer, "Efficient decoding of prefix codes,"
  32.     // Comm. ACM, 33,4, April 1990, pp. 449-459.
  33.     //
  34.    
  35.     internal class HuffmanTree
  36.     {
  37.         internal const int MaxLiteralTreeElements = 288;
  38.         internal const int MaxDistTreeElements = 32;
  39.         internal const int EndOfBlockCode = 256;
  40.         internal const int NumberOfCodeLengthTreeElements = 19;
  41.        
  42.         int tableBits;
  43.         short[] table;
  44.         short[] left;
  45.         short[] right;
  46.         byte[] codeLengthArray;
  47.         #if DEBUG
  48.         uint[] codeArrayDebug;
  49.         #endif
  50.        
  51.         int tableMask;
  52.        
  53.         // huffman tree for static block
  54.         static HuffmanTree staticLiteralLengthTree;
  55.         static HuffmanTree staticDistanceTree;
  56.        
  57.         static HuffmanTree()
  58.         {
  59.             // construct the static literal tree and distance tree
  60.             staticLiteralLengthTree = new HuffmanTree(GetStaticLiteralTreeLength());
  61.             staticDistanceTree = new HuffmanTree(GetStaticDistanceTreeLength());
  62.         }
  63.        
  64.         public static HuffmanTree StaticLiteralLengthTree {
  65.             get { return staticLiteralLengthTree; }
  66.         }
  67.        
  68.         public static HuffmanTree StaticDistanceTree {
  69.             get { return staticDistanceTree; }
  70.         }
  71.        
  72.         public HuffmanTree(byte[] codeLengths)
  73.         {
  74.             Debug.Assert(codeLengths.Length == MaxLiteralTreeElements || codeLengths.Length == MaxDistTreeElements || codeLengths.Length == NumberOfCodeLengthTreeElements, "we only expect three kinds of Length here");
  75.             codeLengthArray = codeLengths;
  76.            
  77.             if (codeLengthArray.Length == MaxLiteralTreeElements) {
  78.                 // bits for Literal/Length tree table
  79.                 tableBits = 9;
  80.             }
  81.             else {
  82.                 // bits for distance tree table and code length tree table
  83.                 tableBits = 7;
  84.             }
  85.             tableMask = (1 << tableBits) - 1;
  86.            
  87.             CreateTable();
  88.         }
  89.        
  90.        
  91.         // Generate the array contains huffman codes lengths for static huffman tree.
  92.         // The data is in RFC 1951.
  93.         static byte[] GetStaticLiteralTreeLength()
  94.         {
  95.             byte[] literalTreeLength = new byte[MaxLiteralTreeElements];
  96.             for (int i = 0; i <= 143; i++)
  97.                 literalTreeLength[i] = 8;
  98.            
  99.             for (int i = 144; i <= 255; i++)
  100.                 literalTreeLength[i] = 9;
  101.            
  102.             for (int i = 256; i <= 279; i++)
  103.                 literalTreeLength[i] = 7;
  104.            
  105.             for (int i = 280; i <= 287; i++)
  106.                 literalTreeLength[i] = 8;
  107.            
  108.             return literalTreeLength;
  109.         }
  110.        
  111.         static byte[] GetStaticDistanceTreeLength()
  112.         {
  113.             byte[] staticDistanceTreeLength = new byte[MaxDistTreeElements];
  114.             for (int i = 0; i < MaxDistTreeElements; i++) {
  115.                 staticDistanceTreeLength[i] = 5;
  116.             }
  117.             return staticDistanceTreeLength;
  118.         }
  119.        
  120.        
  121.         // Calculate the huffman code for each character based on the code length for each character.
  122.         // This algorithm is described in standard RFC 1951
  123.         uint[] CalculateHuffmanCode()
  124.         {
  125.             uint[] bitLengthCount = new uint[17];
  126.             foreach (int codeLength in codeLengthArray) {
  127.                 bitLengthCount[codeLength]++;
  128.             }
  129.             bitLengthCount[0] = 0;
  130.             // clear count for length 0
  131.             uint[] nextCode = new uint[17];
  132.             uint tempCode = 0;
  133.             for (int bits = 1; bits <= 16; bits++) {
  134.                 tempCode = (tempCode + bitLengthCount[bits - 1]) << 1;
  135.                 nextCode[bits] = tempCode;
  136.             }
  137.            
  138.             uint[] code = new uint[MaxLiteralTreeElements];
  139.             for (int i = 0; i < codeLengthArray.Length; i++) {
  140.                 int len = codeLengthArray[i];
  141.                
  142.                 if (len > 0) {
  143.                     code[i] = DecodeHelper.BitReverse(nextCode[len], len);
  144.                     nextCode[len]++;
  145.                 }
  146.             }
  147.             return code;
  148.         }
  149.        
  150.         private void CreateTable()
  151.         {
  152.            
  153.             uint[] codeArray = CalculateHuffmanCode();
  154.             table = new short[1 << tableBits];
  155.             #if DEBUG
  156.             codeArrayDebug = codeArray;
  157.             #endif
  158.            
  159.             // I need to find proof that left and right array will always be
  160.             // enough. I think they are.
  161.             left = new short[2 * codeLengthArray.Length];
  162.             right = new short[2 * codeLengthArray.Length];
  163.             short avail = (short)codeLengthArray.Length;
  164.            
  165.             for (int ch = 0; ch < codeLengthArray.Length; ch++) {
  166.                 // length of this code
  167.                 int len = codeLengthArray[ch];
  168.                 if (len > 0) {
  169.                     // start value (bit reversed)
  170.                     int start = (int)codeArray[ch];
  171.                    
  172.                     if (len <= tableBits) {
  173.                         // If a particular symbol is shorter than nine bits,
  174.                         // then that symbol's translation is duplicated
  175.                         // in all those entries that start with that symbol's bits.
  176.                         // For example, if the symbol is four bits, then it's duplicated
  177.                         // 32 times in a nine-bit table. If a symbol is nine bits long,
  178.                         // it appears in the table once.
  179.                         //
  180.                         // Make sure that in the loop below, code is always
  181.                         // less than table_size.
  182.                         //
  183.                         // On last iteration we store at array index:
  184.                         // initial_start_at + (locs-1)*increment
  185.                         // = initial_start_at + locs*increment - increment
  186.                         // = initial_start_at + (1 << tableBits) - increment
  187.                         // = initial_start_at + table_size - increment
  188.                         //
  189.                         // Therefore we must ensure:
  190.                         // initial_start_at + table_size - increment < table_size
  191.                         // or: initial_start_at < increment
  192.                         //
  193.                         int increment = 1 << len;
  194.                         if (start >= increment) {
  195.                             throw new InvalidDataException(SR.GetString(SR.InvalidHuffmanData));
  196.                         }
  197.                        
  198.                         // Note the bits in the table are reverted.
  199.                         int locs = 1 << (tableBits - len);
  200.                         for (int j = 0; j < locs; j++) {
  201.                             table[start] = (short)ch;
  202.                             start += increment;
  203.                         }
  204.                     }
  205.                     else {
  206.                         // For any code which has length longer than num_elements,
  207.                         // build a binary tree.
  208.                        
  209.                         int overflowBits = len - tableBits;
  210.                         // the nodes we need to respent the data.
  211.                         int codeBitMask = 1 << tableBits;
  212.                         // mask to get current bit (the bits can't fit in the table)
  213.                         // the left, right table is used to repesent the
  214.                         // the rest bits. When we got the first part (number bits.) and look at
  215.                         // tbe table, we will need to follow the tree to find the real character.
  216.                         // This is in place to avoid bloating the table if there are
  217.                         // a few ones with long code.
  218.                         int index = start & ((1 << tableBits) - 1);
  219.                         short[] array = table;
  220.                        
  221.                         do {
  222.                             short value = array[index];
  223.                            
  224.                             if (value == 0) {
  225.                                 // set up next pointer if this node is not used before.
  226.                                 array[index] = (short)-avail;
  227.                                 // use next available slot.
  228.                                 value = (short)-avail;
  229.                                 avail++;
  230.                             }
  231.                            
  232.                             Debug.Assert(value < 0, "Only negative number is used a tree pointer!");
  233.                             if ((start & codeBitMask) == 0) {
  234.                                 // if current bit is 0, go change the left array
  235.                                 array = left;
  236.                             }
  237.                             else {
  238.                                 // if current bit is 1, set value in the right array
  239.                                 array = right;
  240.                             }
  241.                             index = -value;
  242.                             // go to next node
  243.                             codeBitMask <<= 1;
  244.                             overflowBits--;
  245.                         }
  246.                         while (overflowBits != 0);
  247.                        
  248.                         array[index] = (short)ch;
  249.                     }
  250.                 }
  251.             }
  252.         }
  253.        
  254.         //
  255.         // This function will try to get enough bits from input and
  256.         // try to decode the bits.
  257.         // If there are no enought bits in the input, this function will return -1.
  258.         //
  259.         public int GetNextSymbol(InputBuffer input)
  260.         {
  261.             // Try to load 16 bits into input buffer if possible and get the bitBuffer value.
  262.             // If there aren't 16 bits available we will return all we have in the
  263.             // input buffer.
  264.             uint bitBuffer = input.TryLoad16Bits();
  265.             if (input.AvailableBits == 0) {
  266.                 // running out of input.
  267.                 return -1;
  268.             }
  269.            
  270.             // decode an element
  271.             int symbol = table[bitBuffer & tableMask];
  272.             if (symbol < 0) {
  273.                 // this will be the start of the binary tree
  274.                 // navigate the tree
  275.                 uint mask = (uint)1 << tableBits;
  276.                 do {
  277.                     symbol = -symbol;
  278.                     if ((bitBuffer & mask) == 0)
  279.                         symbol = left[symbol];
  280.                     else
  281.                         symbol = right[symbol];
  282.                     mask <<= 1;
  283.                 }
  284.                 while (symbol < 0);
  285.             }
  286.            
  287.             //
  288.             // If this code is longer than the # bits we had in the bit buffer (i.e.
  289.             // we read only part of the code), we can hit the entry in the table or the tree
  290.             // for another symbol. However the length of another symbol will not match the
  291.             // available bits count.
  292.             if (codeLengthArray[symbol] > input.AvailableBits) {
  293.                 // We already tried to load 16 bits and maximum length is 15,
  294.                 // so this means we are running out of input.
  295.                 return -1;
  296.             }
  297.            
  298.             input.SkipBits(codeLengthArray[symbol]);
  299.             return symbol;
  300.         }
  301.        
  302.     }
  303. }

Developer Fusion