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 7 package org.brotli.dec; 8 9 /** 10 * Utilities for building Huffman decoding tables. 11 */ 12 final class Huffman { 13 14 private static final int MAX_LENGTH = 15; 15 16 /** 17 * Returns reverse(reverse(key, len) + 1, len). 18 * 19 * <p> reverse(key, len) is the bit-wise reversal of the len least significant bits of key. 20 */ getNextKey(int key, int len)21 private static int getNextKey(int key, int len) { 22 int step = 1 << (len - 1); 23 while ((key & step) != 0) { 24 step >>= 1; 25 } 26 return (key & (step - 1)) + step; 27 } 28 29 /** 30 * Stores {@code item} in {@code table[0], table[step], table[2 * step] .., table[end]}. 31 * 32 * <p> Assumes that end is an integer multiple of step. 33 */ replicateValue(int[] table, int offset, int step, int end, int item)34 private static void replicateValue(int[] table, int offset, int step, int end, int item) { 35 do { 36 end -= step; 37 table[offset + end] = item; 38 } while (end > 0); 39 } 40 41 /** 42 * @param count histogram of bit lengths for the remaining symbols, 43 * @param len code length of the next processed symbol. 44 * @return table width of the next 2nd level table. 45 */ nextTableBitSize(int[] count, int len, int rootBits)46 private static int nextTableBitSize(int[] count, int len, int rootBits) { 47 int left = 1 << (len - rootBits); 48 while (len < MAX_LENGTH) { 49 left -= count[len]; 50 if (left <= 0) { 51 break; 52 } 53 len++; 54 left <<= 1; 55 } 56 return len - rootBits; 57 } 58 59 /** 60 * Builds Huffman lookup table assuming code lengths are in symbol order. 61 * 62 * @return number of slots used by resulting Huffman table 63 */ buildHuffmanTable(int[] tableGroup, int tableIdx, int rootBits, int[] codeLengths, int codeLengthsSize)64 static int buildHuffmanTable(int[] tableGroup, int tableIdx, int rootBits, int[] codeLengths, 65 int codeLengthsSize) { 66 int tableOffset = tableGroup[tableIdx]; 67 int key; // Reversed prefix code. 68 int[] sorted = new int[codeLengthsSize]; // Symbols sorted by code length. 69 // TODO: fill with zeroes? 70 int[] count = new int[MAX_LENGTH + 1]; // Number of codes of each length. 71 int[] offset = new int[MAX_LENGTH + 1]; // Offsets in sorted table for each length. 72 int symbol; 73 74 // Build histogram of code lengths. 75 for (symbol = 0; symbol < codeLengthsSize; symbol++) { 76 count[codeLengths[symbol]]++; 77 } 78 79 // Generate offsets into sorted symbol table by code length. 80 offset[1] = 0; 81 for (int len = 1; len < MAX_LENGTH; len++) { 82 offset[len + 1] = offset[len] + count[len]; 83 } 84 85 // Sort symbols by length, by symbol order within each length. 86 for (symbol = 0; symbol < codeLengthsSize; symbol++) { 87 if (codeLengths[symbol] != 0) { 88 sorted[offset[codeLengths[symbol]]++] = symbol; 89 } 90 } 91 92 int tableBits = rootBits; 93 int tableSize = 1 << tableBits; 94 int totalSize = tableSize; 95 96 // Special case code with only one value. 97 if (offset[MAX_LENGTH] == 1) { 98 for (key = 0; key < totalSize; key++) { 99 tableGroup[tableOffset + key] = sorted[0]; 100 } 101 return totalSize; 102 } 103 104 // Fill in root table. 105 key = 0; 106 symbol = 0; 107 for (int len = 1, step = 2; len <= rootBits; len++, step <<= 1) { 108 for (; count[len] > 0; count[len]--) { 109 replicateValue(tableGroup, tableOffset + key, step, tableSize, 110 len << 16 | sorted[symbol++]); 111 key = getNextKey(key, len); 112 } 113 } 114 115 // Fill in 2nd level tables and add pointers to root table. 116 int mask = totalSize - 1; 117 int low = -1; 118 int currentOffset = tableOffset; 119 for (int len = rootBits + 1, step = 2; len <= MAX_LENGTH; len++, step <<= 1) { 120 for (; count[len] > 0; count[len]--) { 121 if ((key & mask) != low) { 122 currentOffset += tableSize; 123 tableBits = nextTableBitSize(count, len, rootBits); 124 tableSize = 1 << tableBits; 125 totalSize += tableSize; 126 low = key & mask; 127 tableGroup[tableOffset + low] = 128 (tableBits + rootBits) << 16 | (currentOffset - tableOffset - low); 129 } 130 replicateValue(tableGroup, currentOffset + (key >> rootBits), step, tableSize, 131 (len - rootBits) << 16 | sorted[symbol++]); 132 key = getNextKey(key, len); 133 } 134 } 135 return totalSize; 136 } 137 } 138