| // Copyright 2017 The Chromium OS Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "puffin/src/huffman_table.h" |
| |
| #include <algorithm> |
| #include <vector> |
| |
| #include "puffin/src/logging.h" |
| |
| using std::string; |
| using std::vector; |
| |
| namespace puffin { |
| |
| // Permutations of input Huffman code lengths (used only to read code lengths |
| // necessary for reading Huffman table.) |
| const uint8_t kPermutations[19] = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, |
| 11, 4, 12, 3, 13, 2, 14, 1, 15}; |
| |
| // The bases of each alphabet which is added to the integer value of extra |
| // bits that comes after the Huffman code in the input to create the given |
| // length value. The last element is a guard. |
| const uint16_t kLengthBases[30] = { |
| 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, |
| 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0xFFFF}; |
| |
| // Number of extra bits that comes after the associating Huffman code. |
| const uint8_t kLengthExtraBits[29] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, |
| 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, |
| 4, 4, 4, 4, 5, 5, 5, 5, 0}; |
| |
| // Same as |kLengthBases| but for the distances instead of lengths. The last |
| // element is a guard. |
| const uint16_t kDistanceBases[31] = { |
| 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, |
| 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, |
| 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577, 0xFFFF}; |
| |
| // Same as |kLengthExtraBits| but for distances instead of lengths. |
| const uint8_t kDistanceExtraBits[30] = {0, 0, 0, 0, 1, 1, 2, 2, 3, 3, |
| 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, |
| 9, 9, 10, 10, 11, 11, 12, 12, 13, 13}; |
| |
| // 288 is the maximum number of needed huffman codes for an alphabet. Fixed |
| // huffman table needs 288 and dynamic huffman table needs maximum 286. |
| // 286 = 256 (coding a byte) + |
| // 1 (coding the end of block symbole) + |
| // 29 (coding the lengths) |
| HuffmanTable::HuffmanTable() : codeindexpairs_(288), initialized_(false) {} |
| |
| bool HuffmanTable::InitHuffmanCodes(const Buffer& lens, size_t* max_bits) { |
| // Temporary buffers used in |InitHuffmanCodes|. |
| uint16_t len_count_[kMaxHuffmanBits + 1] = {0}; |
| uint16_t next_code_[kMaxHuffmanBits + 1] = {0}; |
| |
| // 1. Count the number of codes for each length; |
| for (auto len : lens) { |
| len_count_[len]++; |
| } |
| |
| for (*max_bits = kMaxHuffmanBits; *max_bits >= 1; (*max_bits)--) { |
| if (len_count_[*max_bits] != 0) { |
| break; |
| } |
| } |
| |
| // Check for oversubscribed code lengths. (A code with length 'L' cannot have |
| // more than 2^L items. |
| for (size_t idx = 1; idx <= *max_bits; idx++) { |
| if (len_count_[idx] > (1 << idx)) { |
| LOG(ERROR) << "Oversubscribed code lengths error!"; |
| return false; |
| } |
| } |
| |
| // 2. Compute the coding of the first element for each length. |
| uint16_t code = 0; |
| len_count_[0] = 0; |
| for (size_t bits = 1; bits <= kMaxHuffmanBits; bits++) { |
| code = (code + len_count_[bits - 1]) << 1; |
| next_code_[bits] = code; |
| } |
| |
| codeindexpairs_.clear(); |
| // 3. Calculate all the code values. |
| for (size_t idx = 0; idx < lens.size(); idx++) { |
| auto len = lens[idx]; |
| if (len == 0) { |
| continue; |
| } |
| |
| // Reverse the code |
| CodeIndexPair cip; |
| cip.code = 0; |
| auto tmp_code = next_code_[len]; |
| for (size_t r = 0; r < len; r++) { |
| cip.code <<= 1; |
| cip.code |= tmp_code & 1U; |
| tmp_code >>= 1; |
| } |
| cip.index = idx; |
| codeindexpairs_.push_back(cip); |
| next_code_[len]++; |
| } |
| return true; |
| } |
| |
| bool HuffmanTable::BuildHuffmanCodes(const Buffer& lens, |
| vector<uint16_t>* hcodes, |
| size_t* max_bits) { |
| TEST_AND_RETURN_FALSE(InitHuffmanCodes(lens, max_bits)); |
| // Sort descending based on the bit-length of the code. |
| std::sort(codeindexpairs_.begin(), codeindexpairs_.end(), |
| [&lens](const CodeIndexPair& a, const CodeIndexPair& b) { |
| return lens[a.index] > lens[b.index]; |
| }); |
| |
| // Only zero out the part of hcodes which is valuable. |
| memset(hcodes->data(), 0, (1 << *max_bits) * sizeof(uint16_t)); |
| for (const auto& cip : codeindexpairs_) { |
| // The MSB bit of the code in hcodes is set if it is a valid code and its |
| // code exists in the input Huffman table. |
| (*hcodes)[cip.code] = cip.index | 0x8000; |
| auto fill_bits = *max_bits - lens[cip.index]; |
| for (auto idx = 1; idx < (1 << fill_bits); idx++) { |
| auto location = (idx << lens[cip.index]) | cip.code; |
| if (!((*hcodes)[location] & 0x8000)) { |
| (*hcodes)[location] = cip.index | 0x8000; |
| } |
| } |
| } |
| return true; |
| } |
| |
| bool HuffmanTable::BuildHuffmanReverseCodes(const Buffer& lens, |
| vector<uint16_t>* rcodes, |
| size_t* max_bits) { |
| TEST_AND_RETURN_FALSE(InitHuffmanCodes(lens, max_bits)); |
| // Sort ascending based on the index. |
| std::sort(codeindexpairs_.begin(), codeindexpairs_.end(), |
| [](const CodeIndexPair& a, const CodeIndexPair& b) -> bool { |
| return a.index < b.index; |
| }); |
| |
| size_t index = 0; |
| for (size_t idx = 0; idx < rcodes->size(); idx++) { |
| if (index < codeindexpairs_.size() && idx == codeindexpairs_[index].index) { |
| (*rcodes)[idx] = codeindexpairs_[index].code; |
| index++; |
| } else { |
| (*rcodes)[idx] = 0; |
| } |
| } |
| return true; |
| } |
| |
| bool HuffmanTable::BuildFixedHuffmanTable() { |
| if (!initialized_) { |
| // For all the vectors used in this class, we set the size in the |
| // constructor and we do not change the size later. This is for optimization |
| // purposes. The total size of data in this class is approximately |
| // 2KB. Because it is a constructor return values cannot be checked. |
| lit_len_lens_.resize(288); |
| lit_len_rcodes_.resize(288); |
| lit_len_hcodes_.resize(1 << 9); |
| |
| distance_lens_.resize(30); |
| distance_rcodes_.resize(30); |
| distance_hcodes_.resize(1 << 5); |
| |
| size_t i = 0; |
| while (i < 144) { |
| lit_len_lens_[i++] = 8; |
| } |
| while (i < 256) { |
| lit_len_lens_[i++] = 9; |
| } |
| while (i < 280) { |
| lit_len_lens_[i++] = 7; |
| } |
| while (i < 288) { |
| lit_len_lens_[i++] = 8; |
| } |
| |
| i = 0; |
| while (i < 30) { |
| distance_lens_[i++] = 5; |
| } |
| |
| TEST_AND_RETURN_FALSE( |
| BuildHuffmanCodes(lit_len_lens_, &lit_len_hcodes_, &lit_len_max_bits_)); |
| |
| TEST_AND_RETURN_FALSE(BuildHuffmanCodes(distance_lens_, &distance_hcodes_, |
| &distance_max_bits_)); |
| |
| TEST_AND_RETURN_FALSE(BuildHuffmanReverseCodes( |
| lit_len_lens_, &lit_len_rcodes_, &lit_len_max_bits_)); |
| |
| TEST_AND_RETURN_FALSE(BuildHuffmanReverseCodes( |
| distance_lens_, &distance_rcodes_, &distance_max_bits_)); |
| |
| initialized_ = true; |
| } |
| return true; |
| } |
| |
| bool HuffmanTable::BuildDynamicHuffmanTable(BitReaderInterface* br, |
| uint8_t* buffer, |
| size_t* length) { |
| // Initilize only once and reuse. |
| if (!initialized_) { |
| // Only resizing the arrays needed. |
| code_lens_.resize(19); |
| code_hcodes_.resize(1 << 7); |
| |
| lit_len_lens_.resize(286); |
| lit_len_hcodes_.resize(1 << 15); |
| |
| distance_lens_.resize(30); |
| distance_hcodes_.resize(1 << 15); |
| |
| // 286: Maximum number of literal/lengths symbols. |
| // 30: Maximum number of distance symbols. |
| // The reason we reserve this to the sum of both maximum sizes is that we |
| // need to calculate both huffman codes contiguously. See b/72815313. |
| tmp_lens_.resize(286 + 30); |
| initialized_ = true; |
| } |
| |
| // Read the header. Reads the first portion of the Huffman data from input and |
| // writes it into the puff |buffer|. The first portion includes the size |
| // (|num_lit_len|) of the literals/lengths Huffman code length array |
| // (|dynamic_lit_len_lens_|), the size (|num_distance|) of distance Huffman |
| // code length array (|dynamic_distance_lens_|), and the size (|num_codes|) of |
| // Huffman code length array (dynamic_code_lens_) for reading |
| // |dynamic_lit_len_lens_| and |dynamic_distance_lens_|. Then it follows by |
| // reading |dynamic_code_lens_|. |
| |
| TEST_AND_RETURN_FALSE(*length >= 3); |
| size_t index = 0; |
| TEST_AND_RETURN_FALSE(br->CacheBits(14)); |
| buffer[index++] = br->ReadBits(5); // HLIST |
| auto num_lit_len = br->ReadBits(5) + 257; |
| br->DropBits(5); |
| |
| buffer[index++] = br->ReadBits(5); // HDIST |
| auto num_distance = br->ReadBits(5) + 1; |
| br->DropBits(5); |
| |
| buffer[index++] = br->ReadBits(4); // HCLEN |
| auto num_codes = br->ReadBits(4) + 4; |
| br->DropBits(4); |
| |
| TEST_AND_RETURN_FALSE( |
| CheckHuffmanArrayLengths(num_lit_len, num_distance, num_codes)); |
| |
| bool checked = false; |
| size_t idx = 0; |
| TEST_AND_RETURN_FALSE(*length - index >= (num_codes + 1) / 2); |
| // Two codes per byte |
| for (; idx < num_codes; idx++) { |
| TEST_AND_RETURN_FALSE(br->CacheBits(3)); |
| code_lens_[kPermutations[idx]] = br->ReadBits(3); |
| if (checked) { |
| buffer[index++] |= br->ReadBits(3); |
| } else { |
| buffer[index] = br->ReadBits(3) << 4; |
| } |
| checked = !checked; |
| br->DropBits(3); |
| } |
| // Pad the last byte if odd number of codes. |
| if (checked) { |
| index++; |
| } |
| for (; idx < 19; idx++) { |
| code_lens_[kPermutations[idx]] = 0; |
| } |
| |
| TEST_AND_RETURN_FALSE( |
| BuildHuffmanCodes(code_lens_, &code_hcodes_, &code_max_bits_)); |
| |
| // Build literals/lengths and distance Huffman code length arrays. |
| auto bytes_available = (*length - index); |
| tmp_lens_.clear(); |
| TEST_AND_RETURN_FALSE(BuildHuffmanCodeLengths( |
| br, buffer + index, &bytes_available, code_max_bits_, |
| num_lit_len + num_distance, &tmp_lens_)); |
| index += bytes_available; |
| |
| // TODO(ahassani): Optimize this so the memcpy is not needed anymore. |
| lit_len_lens_.clear(); |
| lit_len_lens_.insert(lit_len_lens_.begin(), tmp_lens_.begin(), |
| tmp_lens_.begin() + num_lit_len); |
| |
| distance_lens_.clear(); |
| distance_lens_.insert(distance_lens_.begin(), tmp_lens_.begin() + num_lit_len, |
| tmp_lens_.end()); |
| |
| TEST_AND_RETURN_FALSE( |
| BuildHuffmanCodes(lit_len_lens_, &lit_len_hcodes_, &lit_len_max_bits_)); |
| |
| // Build distance Huffman codes. |
| TEST_AND_RETURN_FALSE(BuildHuffmanCodes(distance_lens_, &distance_hcodes_, |
| &distance_max_bits_)); |
| |
| *length = index; |
| return true; |
| } |
| |
| bool HuffmanTable::BuildHuffmanCodeLengths(BitReaderInterface* br, |
| uint8_t* buffer, |
| size_t* length, |
| size_t max_bits, |
| size_t num_codes, |
| Buffer* lens) { |
| size_t index = 0; |
| lens->clear(); |
| for (size_t idx = 0; idx < num_codes;) { |
| TEST_AND_RETURN_FALSE(br->CacheBits(max_bits)); |
| auto bits = br->ReadBits(max_bits); |
| uint16_t code; |
| size_t nbits; |
| TEST_AND_RETURN_FALSE(CodeAlphabet(bits, &code, &nbits)); |
| TEST_AND_RETURN_FALSE(index < *length); |
| br->DropBits(nbits); |
| if (code < 16) { |
| buffer[index++] = code; |
| lens->push_back(code); |
| idx++; |
| } else { |
| TEST_AND_RETURN_FALSE(code < 19); |
| size_t copy_num = 0; |
| uint8_t copy_val; |
| switch (code) { |
| case 16: |
| TEST_AND_RETURN_FALSE(idx != 0); |
| TEST_AND_RETURN_FALSE(br->CacheBits(2)); |
| copy_num = 3 + br->ReadBits(2); |
| buffer[index++] = 16 + br->ReadBits(2); // 3 - 6 times |
| copy_val = (*lens)[idx - 1]; |
| br->DropBits(2); |
| break; |
| |
| case 17: |
| TEST_AND_RETURN_FALSE(br->CacheBits(3)); |
| copy_num = 3 + br->ReadBits(3); |
| buffer[index++] = 20 + br->ReadBits(3); // 3 - 10 times |
| copy_val = 0; |
| br->DropBits(3); |
| break; |
| |
| case 18: |
| TEST_AND_RETURN_FALSE(br->CacheBits(7)); |
| copy_num = 11 + br->ReadBits(7); |
| buffer[index++] = 28 + br->ReadBits(7); // 11 - 138 times |
| copy_val = 0; |
| br->DropBits(7); |
| break; |
| |
| default: |
| LOG(ERROR) << "Invalid code!"; |
| return false; |
| } |
| idx += copy_num; |
| while (copy_num--) { |
| lens->push_back(copy_val); |
| } |
| } |
| } |
| TEST_AND_RETURN_FALSE(lens->size() == num_codes); |
| *length = index; |
| return true; |
| } |
| |
| bool HuffmanTable::BuildDynamicHuffmanTable(const uint8_t* buffer, |
| size_t length, |
| BitWriterInterface* bw) { |
| if (!initialized_) { |
| // Only resizing the arrays needed. |
| code_lens_.resize(19); |
| code_rcodes_.resize(19); |
| |
| lit_len_lens_.resize(286); |
| lit_len_rcodes_.resize(286); |
| |
| distance_lens_.resize(30); |
| distance_rcodes_.resize(30); |
| |
| tmp_lens_.resize(286 + 30); |
| |
| initialized_ = true; |
| } |
| |
| TEST_AND_RETURN_FALSE(length >= 3); |
| size_t index = 0; |
| // Write the header. |
| size_t num_lit_len = buffer[index] + 257; |
| TEST_AND_RETURN_FALSE(bw->WriteBits(5, buffer[index++])); |
| |
| size_t num_distance = buffer[index] + 1; |
| TEST_AND_RETURN_FALSE(bw->WriteBits(5, buffer[index++])); |
| |
| size_t num_codes = buffer[index] + 4; |
| TEST_AND_RETURN_FALSE(bw->WriteBits(4, buffer[index++])); |
| |
| TEST_AND_RETURN_FALSE( |
| CheckHuffmanArrayLengths(num_lit_len, num_distance, num_codes)); |
| |
| TEST_AND_RETURN_FALSE(length - index >= (num_codes + 1) / 2); |
| bool checked = false; |
| size_t idx = 0; |
| for (; idx < num_codes; idx++) { |
| uint8_t len; |
| if (checked) { |
| len = buffer[index++] & 0x0F; |
| } else { |
| len = buffer[index] >> 4; |
| } |
| checked = !checked; |
| code_lens_[kPermutations[idx]] = len; |
| TEST_AND_RETURN_FALSE(bw->WriteBits(3, len)); |
| } |
| if (checked) { |
| index++; |
| } |
| for (; idx < 19; idx++) { |
| code_lens_[kPermutations[idx]] = 0; |
| } |
| |
| TEST_AND_RETURN_FALSE( |
| BuildHuffmanReverseCodes(code_lens_, &code_rcodes_, &code_max_bits_)); |
| |
| // Build literal/lengths and distance Huffman code length arrays. |
| auto bytes_available = length - index; |
| TEST_AND_RETURN_FALSE( |
| BuildHuffmanCodeLengths(buffer + index, &bytes_available, bw, |
| num_lit_len + num_distance, &tmp_lens_)); |
| index += bytes_available; |
| |
| lit_len_lens_.clear(); |
| lit_len_lens_.insert(lit_len_lens_.begin(), tmp_lens_.begin(), |
| tmp_lens_.begin() + num_lit_len); |
| |
| distance_lens_.clear(); |
| distance_lens_.insert(distance_lens_.begin(), tmp_lens_.begin() + num_lit_len, |
| tmp_lens_.end()); |
| |
| // Build literal/lengths Huffman reverse codes. |
| TEST_AND_RETURN_FALSE(BuildHuffmanReverseCodes( |
| lit_len_lens_, &lit_len_rcodes_, &lit_len_max_bits_)); |
| |
| // Build distance Huffman reverse codes. |
| TEST_AND_RETURN_FALSE(BuildHuffmanReverseCodes( |
| distance_lens_, &distance_rcodes_, &distance_max_bits_)); |
| |
| TEST_AND_RETURN_FALSE(length == index); |
| |
| return true; |
| } |
| |
| bool HuffmanTable::BuildHuffmanCodeLengths(const uint8_t* buffer, |
| size_t* length, |
| BitWriterInterface* bw, |
| size_t num_codes, |
| Buffer* lens) { |
| lens->clear(); |
| uint16_t hcode; |
| size_t nbits; |
| size_t index = 0; |
| for (size_t idx = 0; idx < num_codes;) { |
| TEST_AND_RETURN_FALSE(index < *length); |
| auto pcode = buffer[index++]; |
| TEST_AND_RETURN_FALSE(pcode <= 155); |
| |
| auto code = pcode < 16 ? pcode : pcode < 20 ? 16 : pcode < 28 ? 17 : 18; |
| TEST_AND_RETURN_FALSE(CodeHuffman(code, &hcode, &nbits)); |
| TEST_AND_RETURN_FALSE(bw->WriteBits(nbits, hcode)); |
| if (code < 16) { |
| lens->push_back(code); |
| idx++; |
| } else { |
| size_t copy_num = 0; |
| uint8_t copy_val; |
| switch (code) { |
| case 16: |
| // Cannot repeat a non-existent last code if idx == 0. |
| TEST_AND_RETURN_FALSE(idx != 0); |
| TEST_AND_RETURN_FALSE(bw->WriteBits(2, pcode - 16)); |
| copy_num = 3 + pcode - 16; |
| copy_val = (*lens)[idx - 1]; |
| break; |
| |
| case 17: |
| TEST_AND_RETURN_FALSE(bw->WriteBits(3, pcode - 20)); |
| copy_num = 3 + pcode - 20; |
| copy_val = 0; |
| break; |
| |
| case 18: |
| TEST_AND_RETURN_FALSE(bw->WriteBits(7, pcode - 28)); |
| copy_num = 11 + pcode - 28; |
| copy_val = 0; |
| break; |
| |
| default: |
| break; |
| } |
| idx += copy_num; |
| while (copy_num--) { |
| lens->push_back(copy_val); |
| } |
| } |
| } |
| TEST_AND_RETURN_FALSE(lens->size() == num_codes); |
| *length = index; |
| return true; |
| } |
| |
| string BlockTypeToString(BlockType type) { |
| switch (type) { |
| case BlockType::kUncompressed: |
| return "Uncompressed"; |
| |
| case BlockType::kFixed: |
| return "Fixed"; |
| |
| case BlockType::kDynamic: |
| return "Dynamic"; |
| |
| default: |
| return "Unknown"; |
| } |
| } |
| |
| } // namespace puffin |
