Huffman.h

Go to the documentation of this file.

/*
 *  Copyright (c) 2015-present, Facebook, Inc.
 *  All rights reserved.
 *
 *  This source code is licensed under the BSD-style license found in the
 *  LICENSE file in the root directory of this source tree. An additional grant
 *  of patent rights can be found in the PATENTS file in the same directory.
 *
 */
#pragma once

#include <folly/FBString.h>
#include <folly/io/Cursor.h>
#include <folly/io/IOBuf.h>
#include <proxygen/lib/http/codec/compress/HPACKConstants.h>
#include <string>

namespace proxygen { namespace huffman {

// size of the huffman tables (codes and bits)
const uint32_t kTableSize = 256;

// not used explicitly, since the prefixes are all 1's and they are
// used only for padding of up to 7 bits
const uint32_t kEOSHpack = 0x3fffffff;

struct HuffNode {
  union {
    uint8_t ch;   // leafs hold characters
    uint8_t superNodeIndex;
  } data{0};
  struct {
    uint8_t bits:4; // how many bits are used for representing ch, range is 0-8
    bool isSuperNode:1;
  } metadata{0,false};

  bool isLeaf() const {
    return !metadata.isSuperNode;
  }
};

struct SuperHuffNode {
  HuffNode index[256];
};

class HuffTree {
 public:
  explicit HuffTree(const uint32_t* codes, const uint8_t* bits);
  explicit HuffTree(HuffTree&& tree) = default;
  ~HuffTree() {}

  bool decode(const uint8_t* buf, uint32_t size,
              folly::fbstring& literal) const;

  uint32_t encode(folly::StringPiece literal,
                  folly::io::QueueAppender& buf) const;

  uint32_t getEncodeSize(folly::StringPiece literal) const;

  std::pair<uint32_t, uint8_t> getCode(uint8_t ch) const;

  // get internal tables for codes and bit lengths, useful for testing
  const uint32_t* codesTable() const;
  const uint8_t* bitsTable() const;

 private:
  void fillIndex(SuperHuffNode& snode, uint32_t code, uint8_t bits, uint8_t ch,
     uint8_t level);
  void buildTree();
  void insert(uint32_t code, uint8_t bits, uint8_t ch);

  uint32_t nodes_{0};
  const uint32_t* codes_;
  const uint8_t* bits_;

 protected:
  explicit HuffTree(const HuffTree& tree);
  SuperHuffNode table_[46];
};

const HuffTree& huffTree();

}}