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