src/huffman_table.h

// 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/include/puffin/errors.h"
#include "puffin/src/set_errors.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,
                                Error* error);

  // 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.
  // |error|  OUT     The error code.
  bool BuildDynamicHuffmanTable(const uint8_t* buffer,
                                size_t length,
                                BitWriterInterface* bw,
                                Error* error);

 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.
  // |error|     OUT     The error code.
  bool BuildHuffmanCodeLengths(BitReaderInterface* br,
                               uint8_t* buffer,
                               size_t* length,
                               size_t max_bits,
                               size_t num_codes,
                               Buffer* lens,
                               Error* error);

  // 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.
  // |error|     OUT     The error code.
  bool BuildHuffmanCodeLengths(const uint8_t* buffer,
                               size_t* length,
                               BitWriterInterface* bw,
                               size_t num_codes,
                               Buffer* lens,
                               Error* error);

 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_;

  // 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_