| /* Copyright 2013 Google Inc. All Rights Reserved. |
| |
| Licensed under the Apache License, Version 2.0 (the "License"); |
| you may not use this file except in compliance with the License. |
| You may obtain a copy of the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, software |
| distributed under the License is distributed on an "AS IS" BASIS, |
| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| See the License for the specific language governing permissions and |
| limitations under the License. |
| */ |
| |
| /* Utilities for building Huffman decoding tables. */ |
| |
| #include <assert.h> |
| #include <stdlib.h> |
| #include <stdio.h> |
| #include <string.h> |
| #include "./huffman.h" |
| #include "./safe_malloc.h" |
| |
| #if defined(__cplusplus) || defined(c_plusplus) |
| extern "C" { |
| #endif |
| |
| #define MAX_LENGTH 15 |
| |
| /* Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the |
| bit-wise reversal of the len least significant bits of key. */ |
| static BROTLI_INLINE int GetNextKey(int key, int len) { |
| int step = 1 << (len - 1); |
| while (key & step) { |
| step >>= 1; |
| } |
| return (key & (step - 1)) + step; |
| } |
| |
| /* Stores code in table[0], table[step], table[2*step], ..., table[end] */ |
| /* Assumes that end is an integer multiple of step */ |
| static BROTLI_INLINE void ReplicateValue(HuffmanCode* table, |
| int step, int end, |
| HuffmanCode code) { |
| do { |
| end -= step; |
| table[end] = code; |
| } while (end > 0); |
| } |
| |
| /* Returns the table width of the next 2nd level table. count is the histogram |
| of bit lengths for the remaining symbols, len is the code length of the next |
| processed symbol */ |
| static BROTLI_INLINE int NextTableBitSize(const int* const count, |
| int len, int root_bits) { |
| int left = 1 << (len - root_bits); |
| while (len < MAX_LENGTH) { |
| left -= count[len]; |
| if (left <= 0) break; |
| ++len; |
| left <<= 1; |
| } |
| return len - root_bits; |
| } |
| |
| int BrotliBuildHuffmanTable(HuffmanCode* root_table, |
| int root_bits, |
| const uint8_t* const code_lengths, |
| int code_lengths_size) { |
| HuffmanCode code; /* current table entry */ |
| HuffmanCode* table; /* next available space in table */ |
| int len; /* current code length */ |
| int symbol; /* symbol index in original or sorted table */ |
| int key; /* reversed prefix code */ |
| int step; /* step size to replicate values in current table */ |
| int low; /* low bits for current root entry */ |
| int mask; /* mask for low bits */ |
| int table_bits; /* key length of current table */ |
| int table_size; /* size of current table */ |
| int total_size; /* sum of root table size and 2nd level table sizes */ |
| int* sorted; /* symbols sorted by code length */ |
| int count[MAX_LENGTH + 1] = { 0 }; /* number of codes of each length */ |
| int offset[MAX_LENGTH + 1]; /* offsets in sorted table for each length */ |
| |
| sorted = (int*)malloc((size_t)code_lengths_size * sizeof(*sorted)); |
| if (sorted == NULL) { |
| return 0; |
| } |
| |
| /* build histogram of code lengths */ |
| for (symbol = 0; symbol < code_lengths_size; symbol++) { |
| count[code_lengths[symbol]]++; |
| } |
| |
| /* generate offsets into sorted symbol table by code length */ |
| offset[1] = 0; |
| for (len = 1; len < MAX_LENGTH; len++) { |
| offset[len + 1] = offset[len] + count[len]; |
| } |
| |
| /* sort symbols by length, by symbol order within each length */ |
| for (symbol = 0; symbol < code_lengths_size; symbol++) { |
| if (code_lengths[symbol] != 0) { |
| sorted[offset[code_lengths[symbol]]++] = symbol; |
| } |
| } |
| |
| table = root_table; |
| table_bits = root_bits; |
| table_size = 1 << table_bits; |
| total_size = table_size; |
| |
| /* special case code with only one value */ |
| if (offset[MAX_LENGTH] == 1) { |
| code.bits = 0; |
| code.value = (uint16_t)sorted[0]; |
| for (key = 0; key < total_size; ++key) { |
| table[key] = code; |
| } |
| free(sorted); |
| return total_size; |
| } |
| |
| /* fill in root table */ |
| key = 0; |
| symbol = 0; |
| for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) { |
| for (; count[len] > 0; --count[len]) { |
| code.bits = (uint8_t)(len); |
| code.value = (uint16_t)sorted[symbol++]; |
| ReplicateValue(&table[key], step, table_size, code); |
| key = GetNextKey(key, len); |
| } |
| } |
| |
| /* fill in 2nd level tables and add pointers to root table */ |
| mask = total_size - 1; |
| low = -1; |
| for (len = root_bits + 1, step = 2; len <= MAX_LENGTH; ++len, step <<= 1) { |
| for (; count[len] > 0; --count[len]) { |
| if ((key & mask) != low) { |
| table += table_size; |
| table_bits = NextTableBitSize(count, len, root_bits); |
| table_size = 1 << table_bits; |
| total_size += table_size; |
| low = key & mask; |
| root_table[low].bits = (uint8_t)(table_bits + root_bits); |
| root_table[low].value = (uint16_t)((table - root_table) - low); |
| } |
| code.bits = (uint8_t)(len - root_bits); |
| code.value = (uint16_t)sorted[symbol++]; |
| ReplicateValue(&table[key >> root_bits], step, table_size, code); |
| key = GetNextKey(key, len); |
| } |
| } |
| |
| free(sorted); |
| return total_size; |
| } |
| |
| void BrotliHuffmanTreeGroupInit(HuffmanTreeGroup* group, int alphabet_size, |
| int ntrees) { |
| group->alphabet_size = alphabet_size; |
| group->num_htrees = ntrees; |
| group->codes = (HuffmanCode*)malloc( |
| sizeof(HuffmanCode) * (size_t)(ntrees * BROTLI_HUFFMAN_MAX_TABLE_SIZE)); |
| group->htrees = (HuffmanCode**)malloc(sizeof(HuffmanCode*) * (size_t)ntrees); |
| } |
| |
| void BrotliHuffmanTreeGroupRelease(HuffmanTreeGroup* group) { |
| if (group->codes) { |
| free(group->codes); |
| } |
| if (group->htrees) { |
| free(group->htrees); |
| } |
| } |
| |
| #if defined(__cplusplus) || defined(c_plusplus) |
| } /* extern "C" */ |
| #endif |