// 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.
|
|
#ifndef SRC_HUFFMAN_TABLE_H_
|
#define SRC_HUFFMAN_TABLE_H_
|
|
#include <cstddef>
|
#include <cstdint>
|
#include <string>
|
#include <vector>
|
|
#include "puffin/src/bit_reader.h"
|
#include "puffin/src/bit_writer.h"
|
#include "puffin/src/include/puffin/common.h"
|
#include "puffin/src/logging.h"
|
|
namespace puffin {
|
|
// Maximum Huffman code length based on RFC1951.
|
constexpr size_t kMaxHuffmanBits = 15;
|
|
// Permutations of input Huffman code lengths (used only to read
|
// |dynamic_code_lens_|).
|
extern const uint8_t kPermutations[];
|
|
// 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.
|
extern const uint16_t kLengthBases[];
|
|
// Number of extra bits that comes after the associating Huffman code.
|
extern const uint8_t kLengthExtraBits[];
|
|
// same as |kLengthBases| except for the the distances instead of lengths.
|
// The last element is a guard.
|
extern const uint16_t kDistanceBases[];
|
|
// Same as |kLengthExtraBits| except for distances instead of lengths.
|
extern const uint8_t kDistanceExtraBits[];
|
|
class HuffmanTable {
|
public:
|
HuffmanTable();
|
virtual ~HuffmanTable() = default;
|
|
// Checks the lengths of Huffman length arrays for correctness
|
//
|
// |num_lit_len| IN The number of literal/lengths code lengths
|
// |num_distance| IN The number of distance code lengths
|
// |num_codes| IN The number of code lengths for reading Huffman table.
|
inline bool CheckHuffmanArrayLengths(size_t num_lit_len,
|
size_t num_distance,
|
size_t num_codes) {
|
if (num_lit_len > 286 || num_distance > 30 || num_codes > 19) {
|
LOG(ERROR) << "The lengths of the dynamic Huffman table are invalid: "
|
<< "num_lit_len(" << num_lit_len << ") "
|
<< "num_distance(" << num_distance << ") "
|
<< "num_codes(" << num_codes << ")";
|
return false;
|
}
|
return true;
|
}
|
|
// Returns the maximum number of bits used in the current literal/length
|
// Huffman codes.
|
inline size_t LitLenMaxBits() { return lit_len_max_bits_; }
|
|
// Returns the maximum number of bits used in the current distance Huffman
|
// codes.
|
inline size_t DistanceMaxBits() { return distance_max_bits_; }
|
|
// Returns the alphabet associated with the set of input bits for the code
|
// length array.
|
//
|
// |bits| IN The input Huffman bits read from the deflate stream.
|
// |alphabet| OUT The alphabet associated with the given |bits|.
|
// |nbits| OUT The number of bits in the Huffman code of alphabet.
|
// Returns true if there is an alphabet associated with |bits|.
|
inline bool CodeAlphabet(uint32_t bits, uint16_t* alphabet, size_t* nbits) {
|
auto hc = code_hcodes_[bits];
|
TEST_AND_RETURN_FALSE(hc & 0x8000);
|
*alphabet = hc & 0x7FFF;
|
*nbits = code_lens_[*alphabet];
|
return true;
|
}
|
|
// Returns the alphabet associated with the set of input bits for the
|
// literal/length code length array.
|
//
|
// |bits| IN The input Huffman bits read from the deflate stream.
|
// |alphabet| OUT The alphabet associated with the given |bits|.
|
// |nbits| OUT The number of bits in the Huffman code of the |alphabet|.
|
// Returns true if there is an alphabet associated with |bits|.
|
inline bool LitLenAlphabet(uint32_t bits, uint16_t* alphabet, size_t* nbits) {
|
auto hc = lit_len_hcodes_[bits];
|
TEST_AND_RETURN_FALSE(hc & 0x8000);
|
*alphabet = hc & 0x7FFF;
|
*nbits = lit_len_lens_[*alphabet];
|
return true;
|
}
|
|
// Returns the alphabet associated with the set of input bits for the
|
// distance code length array.
|
//
|
// |bits| IN The input Huffman bits read from the deflate stream.
|
// |alphabet| OUT The alphabet associated with the given |bits|.
|
// |nbits| OUT The number of bits in the Huffman code of the |alphabet|.
|
// Returns true if there is an alphabet associated with |bits|.
|
inline bool DistanceAlphabet(uint32_t bits,
|
uint16_t* alphabet,
|
size_t* nbits) {
|
auto hc = distance_hcodes_[bits];
|
TEST_AND_RETURN_FALSE(hc & 0x8000);
|
*alphabet = hc & 0x7FFF;
|
*nbits = distance_lens_[*alphabet];
|
return true;
|
}
|
|
// Returns the Huffman code of a give alphabet for Huffman table codes.
|
//
|
// |alphabet| IN The alphabet.
|
// |huffman| OUT The Huffman code for |alphabet|.
|
// |nbits| OUT The maximum number of bits in the Huffman code of the
|
// |alphabet|.
|
inline bool CodeHuffman(uint16_t alphabet, uint16_t* huffman, size_t* nbits) {
|
TEST_AND_RETURN_FALSE(alphabet < code_lens_.size());
|
*huffman = code_rcodes_[alphabet];
|
*nbits = code_lens_[alphabet];
|
return true;
|
}
|
|
// Returns the Huffman code of a give alphabet for literal/length codes.
|
//
|
// |alphabet| IN The alphabet.
|
// |huffman| OUT The Huffman code for |alphabet|.
|
// |nbits| OUT The maximum number of bits in the Huffman code of the
|
// |alphabet|.
|
inline bool LitLenHuffman(uint16_t alphabet,
|
uint16_t* huffman,
|
size_t* nbits) {
|
TEST_AND_RETURN_FALSE(alphabet < lit_len_lens_.size());
|
*huffman = lit_len_rcodes_[alphabet];
|
*nbits = lit_len_lens_[alphabet];
|
return true;
|
}
|
|
inline bool EndOfBlockBitLength(size_t* nbits) {
|
TEST_AND_RETURN_FALSE(256 < lit_len_lens_.size());
|
*nbits = lit_len_lens_[256];
|
return true;
|
}
|
|
// Returns the Huffman code of a give alphabet for distance codes.
|
//
|
// |alphabet| IN The alphabet.
|
// |huffman| OUT The Huffman code for |alphabet|.
|
// |nbits| OUT The maximum number of bits in the Huffman code of the
|
// |alphabet|.
|
inline bool DistanceHuffman(uint16_t alphabet,
|
uint16_t* huffman,
|
size_t* nbits) {
|
TEST_AND_RETURN_FALSE(alphabet < distance_lens_.size());
|
*huffman = distance_rcodes_[alphabet];
|
*nbits = distance_lens_[alphabet];
|
return true;
|
}
|
|
// This populates the object with fixed huffman table parameters.
|
// TODO(ahassani): Revamp the use of this function to be initiliazed once in
|
// the lifetime of the program and only one instance needed.
|
bool BuildFixedHuffmanTable();
|
|
// This functions first reads the Huffman code length arrays from the input
|
// deflate stream, then builds both literal/length and distance Huffman
|
// code arrays. It also writes the Huffman table into the puffed stream.
|
//
|
// |br| IN The |BitReaderInterface| reading the deflate stream.
|
// |buffer| OUT The object to write the Huffman table.
|
// |length| IN/OUT The length available in the |buffer| and in return it
|
// will be the length of Huffman table data written into
|
// the |buffer|.
|
bool BuildDynamicHuffmanTable(BitReaderInterface* br,
|
uint8_t* buffer,
|
size_t* length);
|
|
// This functions first reads the Huffman code length arrays from the input
|
// puffed |buffer|, then builds both literal/length and distance Huffman code
|
// arrays. It also writes the coded Huffman table arrays into the deflate
|
// stream.
|
//
|
// |buffer| IN The array to read the Huffman table from.
|
// |length| IN The length available in the |buffer|.
|
// |bw| IN/OUT The |BitWriterInterface| for writing into the deflate
|
// stream.
|
bool BuildDynamicHuffmanTable(const uint8_t* buffer,
|
size_t length,
|
BitWriterInterface* bw);
|
|
protected:
|
// Initializes the Huffman codes from an array of lengths.
|
//
|
// |lens| IN The input array of code lengths.
|
// |max_bits| OUT The maximum number of bits used for the Huffman codes.
|
bool InitHuffmanCodes(const Buffer& lens, size_t* max_bits);
|
|
// Creates the Huffman code to alphabet array.
|
// |lens| IN The input array of code lengths.
|
// |hcodes| OUT The Huffman to alphabet array.
|
// |max_bits| OUT The maximum number of bits used for the Huffman codes.
|
bool BuildHuffmanCodes(const Buffer& lens,
|
std::vector<uint16_t>* hcodes,
|
size_t* max_bits);
|
|
// Creates the alphabet to Huffman code array.
|
// |lens| IN The input array of code lengths.
|
// |rcodes| OUT The Huffman to Huffman array.
|
// |max_bits| OUT The maximum number of bits used for the Huffman codes.
|
bool BuildHuffmanReverseCodes(const Buffer& lens,
|
std::vector<uint16_t>* rcodes,
|
size_t* max_bits);
|
|
// Reads a specific Huffman code length array from input. At the same time
|
// writes the array into the puffed stream. The Huffman code length array is
|
// either the literal/lengths or distance codes.
|
//
|
// |br| IN The |BitReaderInterface| for reading the deflate
|
// stream.
|
// |buffer| OUT The array to write the Huffman table.
|
// |length| IN/OUT The length available in the |buffer| and in return it
|
// will be the length of data written into the |buffer|.
|
// |max_bits| IN The maximum number of bits in the Huffman codes.
|
// |num_codes| IN The size of the Huffman code length array in the input.
|
// |lens| OUT The resulting Huffman code length array.
|
bool BuildHuffmanCodeLengths(BitReaderInterface* br,
|
uint8_t* buffer,
|
size_t* length,
|
size_t max_bits,
|
size_t num_codes,
|
Buffer* lens);
|
|
// Similar to |BuildHuffmanCodeLengths| but for reading from puffed buffer and
|
// writing into deflate stream.
|
//
|
// |buffer| IN The array to read the Huffman table from.
|
// |length| IN The length available in the |buffer|.
|
// |bw| IN/OUT The |BitWriterInterface| for writing into the deflate
|
// stream.
|
// |num_codes| IN Number of Huffman code lengths to read from the
|
// |buffer|.
|
// |lens| OUT The Huffman code lengths array.
|
bool BuildHuffmanCodeLengths(const uint8_t* buffer,
|
size_t* length,
|
BitWriterInterface* bw,
|
size_t num_codes,
|
Buffer* lens);
|
|
private:
|
// A utility struct used to create Huffman codes.
|
struct CodeIndexPair {
|
uint16_t code; // The Huffman code
|
uint16_t index; // The alphabet
|
};
|
// A vector with maximum size of 286 that is only uses as temporary space for
|
// building Huffman codes.
|
std::vector<CodeIndexPair> codeindexpairs_;
|
|
// Used in building Huffman codes for literals/lengths and distances.
|
std::vector<uint8_t> lit_len_lens_;
|
std::vector<uint16_t> lit_len_hcodes_;
|
std::vector<uint16_t> lit_len_rcodes_;
|
size_t lit_len_max_bits_;
|
std::vector<uint8_t> distance_lens_;
|
std::vector<uint16_t> distance_hcodes_;
|
std::vector<uint16_t> distance_rcodes_;
|
size_t distance_max_bits_;
|
|
// The reason for keeping a temporary buffer here is to avoid reallocing each
|
// time.
|
std::vector<uint8_t> tmp_lens_;
|
|
// Used in building Huffman codes for reading and decoding literal/length and
|
// distance Huffman code length arrays.
|
std::vector<uint8_t> code_lens_;
|
std::vector<uint16_t> code_hcodes_;
|
std::vector<uint16_t> code_rcodes_;
|
size_t code_max_bits_;
|
|
bool initialized_;
|
|
DISALLOW_COPY_AND_ASSIGN(HuffmanTable);
|
};
|
|
// The type of a block in a deflate stream.
|
enum class BlockType : uint8_t {
|
kUncompressed = 0x00,
|
kFixed = 0x01,
|
kDynamic = 0x02,
|
};
|
|
std::string BlockTypeToString(BlockType type);
|
|
} // namespace puffin
|
|
#endif // SRC_HUFFMAN_TABLE_H_
|
