1 /* Copyright 2015 Google Inc. All Rights Reserved. 2 3 Distributed under MIT license. 4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 5 */ 6 namespace Org.Brotli.Dec 7 { 8 /// <summary>Utilities for building Huffman decoding tables.</summary> 9 internal sealed class Huffman 10 { 11 /// <summary> 12 /// Maximum possible Huffman table size for an alphabet size of 704, max code length 15 and root 13 /// table bits 8. 14 /// </summary> 15 internal const int HuffmanMaxTableSize = 1080; 16 17 private const int MaxLength = 15; 18 19 /// <summary>Returns reverse(reverse(key, len) + 1, len).</summary> 20 /// <remarks> 21 /// Returns reverse(reverse(key, len) + 1, len). 22 /// <p> reverse(key, len) is the bit-wise reversal of the len least significant bits of key. 23 /// </remarks> GetNextKey(int key, int len)24 private static int GetNextKey(int key, int len) 25 { 26 int step = 1 << (len - 1); 27 while ((key & step) != 0) 28 { 29 step >>= 1; 30 } 31 return (key & (step - 1)) + step; 32 } 33 34 /// <summary> 35 /// Stores 36 /// <paramref name="item"/> 37 /// in 38 /// <c>table[0], table[step], table[2 * step] .., table[end]</c> 39 /// . 40 /// <p> Assumes that end is an integer multiple of step. 41 /// </summary> ReplicateValue(int[] table, int offset, int step, int end, int item)42 private static void ReplicateValue(int[] table, int offset, int step, int end, int item) 43 { 44 do 45 { 46 end -= step; 47 table[offset + end] = item; 48 } 49 while (end > 0); 50 } 51 52 /// <param name="count">histogram of bit lengths for the remaining symbols,</param> 53 /// <param name="len">code length of the next processed symbol.</param> 54 /// <returns>table width of the next 2nd level table.</returns> NextTableBitSize(int[] count, int len, int rootBits)55 private static int NextTableBitSize(int[] count, int len, int rootBits) 56 { 57 int left = 1 << (len - rootBits); 58 while (len < MaxLength) 59 { 60 left -= count[len]; 61 if (left <= 0) 62 { 63 break; 64 } 65 len++; 66 left <<= 1; 67 } 68 return len - rootBits; 69 } 70 71 /// <summary>Builds Huffman lookup table assuming code lengths are in symbol order.</summary> BuildHuffmanTable(int[] rootTable, int tableOffset, int rootBits, int[] codeLengths, int codeLengthsSize)72 internal static void BuildHuffmanTable(int[] rootTable, int tableOffset, int rootBits, int[] codeLengths, int codeLengthsSize) 73 { 74 int key; 75 // Reversed prefix code. 76 int[] sorted = new int[codeLengthsSize]; 77 // Symbols sorted by code length. 78 // TODO: fill with zeroes? 79 int[] count = new int[MaxLength + 1]; 80 // Number of codes of each length. 81 int[] offset = new int[MaxLength + 1]; 82 // Offsets in sorted table for each length. 83 int symbol; 84 // Build histogram of code lengths. 85 for (symbol = 0; symbol < codeLengthsSize; symbol++) 86 { 87 count[codeLengths[symbol]]++; 88 } 89 // Generate offsets into sorted symbol table by code length. 90 offset[1] = 0; 91 for (int len = 1; len < MaxLength; len++) 92 { 93 offset[len + 1] = offset[len] + count[len]; 94 } 95 // Sort symbols by length, by symbol order within each length. 96 for (symbol = 0; symbol < codeLengthsSize; symbol++) 97 { 98 if (codeLengths[symbol] != 0) 99 { 100 sorted[offset[codeLengths[symbol]]++] = symbol; 101 } 102 } 103 int tableBits = rootBits; 104 int tableSize = 1 << tableBits; 105 int totalSize = tableSize; 106 // Special case code with only one value. 107 if (offset[MaxLength] == 1) 108 { 109 for (key = 0; key < totalSize; key++) 110 { 111 rootTable[tableOffset + key] = sorted[0]; 112 } 113 return; 114 } 115 // Fill in root table. 116 key = 0; 117 symbol = 0; 118 for (int len = 1, step = 2; len <= rootBits; len++, step <<= 1) 119 { 120 for (; count[len] > 0; count[len]--) 121 { 122 ReplicateValue(rootTable, tableOffset + key, step, tableSize, len << 16 | sorted[symbol++]); 123 key = GetNextKey(key, len); 124 } 125 } 126 // Fill in 2nd level tables and add pointers to root table. 127 int mask = totalSize - 1; 128 int low = -1; 129 int currentOffset = tableOffset; 130 for (int len = rootBits + 1, step = 2; len <= MaxLength; len++, step <<= 1) 131 { 132 for (; count[len] > 0; count[len]--) 133 { 134 if ((key & mask) != low) 135 { 136 currentOffset += tableSize; 137 tableBits = NextTableBitSize(count, len, rootBits); 138 tableSize = 1 << tableBits; 139 totalSize += tableSize; 140 low = key & mask; 141 rootTable[tableOffset + low] = (tableBits + rootBits) << 16 | (currentOffset - tableOffset - low); 142 } 143 ReplicateValue(rootTable, currentOffset + (key >> rootBits), step, tableSize, (len - rootBits) << 16 | sorted[symbol++]); 144 key = GetNextKey(key, len); 145 } 146 } 147 } 148 } 149 } 150