proxygen::huffman::HuffTree Class Reference

#include <Huffman.h>

Inheritance diagram for proxygen::huffman::HuffTree:

Public Member Functions
	HuffTree (const uint32_t *codes, const uint8_t *bits)
	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
const uint32_t *	codesTable () const
const uint8_t *	bitsTable () const

Protected Member Functions
	HuffTree (const HuffTree &tree)

Protected Attributes
SuperHuffNode	table_ [46]

Private Member Functions
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)

Private Attributes
uint32_t	nodes_ {0}
const uint32_t *	codes_
const uint8_t *	bits_

Detailed Description

Immutable Huffman tree used in the process of decoding. Traditionally the huffman tree is binary, but using that approach leads to major inefficiencies since it's using per-bit level processing and needs to perform several memory accesses and bit operations for every single bit. This implementation is using 8-bit level indexing and uses aggregated nodes that link up to 256 other nodes. The complexity for lookup is reduced from O(bits) to O(Bytes) which is 1 or 2 for most of the printable characters. The tradeoff of using this approach is using more memory and generating the tree is more laborious since we need to fill all the subtrees denoted by a character code, which is an unique prefix.

Example

bit stream: 00001111 1111010

1. our lookup key is 00001111 which will point to character '/', since the entire subtree with prefix 0000 points to it. We know the subtree has just 4 bits, we remove just those from the current key. bit stream: 11111111 010
2. key is 11111111 which points to a branch, so we go down one level bit stream: 010
3. we don't have enough bits, so we use paddding and we get a key of 01011111, which points to '(' character, like any other node under the subtree '010'.

Definition at line 84 of file Huffman.h.

Constructor & Destructor Documentation

proxygen::huffman::HuffTree::HuffTree ( const uint32_t *  codes, const uint8_t *  bits  )

explicit

the constructor assumes the codes and bits tables will not be freed, ideally they are static

Definition at line 21 of file Huffman.cpp.

References buildTree().

    : codes_(codes), bits_(bits) {
  buildTree();
}

proxygen::huffman::HuffTree::HuffTree ( HuffTree &&  tree )

explicitdefault

proxygen::huffman::HuffTree::~HuffTree ( )

inline

Definition at line 92 of file Huffman.h.

References proxygen::huffman::HuffNode::ch, fizz::decode(), encode(), folly::size(), uint32_t, and uint8_t.

{}

proxygen::huffman::HuffTree::HuffTree ( const HuffTree &  tree )

explicitprotected

Definition at line 26 of file Huffman.cpp.

References buildTree().

                                       :
    codes_(tree.codes_), bits_(tree.bits_) {
  buildTree();
}

Member Function Documentation

const uint8_t * proxygen::huffman::HuffTree::bitsTable

(

)

const

Definition at line 102 of file Huffman.cpp.

References bits_.

                                         {
  return bits_;
}

void proxygen::huffman::HuffTree::buildTree ( )

private

initializes and builds the huffman tree

Definition at line 126 of file Huffman.cpp.

References bits_, codes_, i, insert(), proxygen::huffman::kTableSize, and uint32_t.

Referenced by HuffTree().

                         {
  // create the indexed table
  for (uint32_t i = 0; i < kTableSize; i++) {
    insert(codes_[i], bits_[i], i);
  }
}

const uint32_t * proxygen::huffman::HuffTree::codesTable

(

)

const

Definition at line 98 of file Huffman.cpp.

References codes_.

                                           {
  return codes_;
}

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

decode bitstream into a string literal

Parameters

buf	start of a huffman-encoded bit stream
size	size of the buffer
literal	where to append decoded characters

Returns

true if the decode process was successful

Definition at line 31 of file Huffman.cpp.

References proxygen::huffman::HuffNode::bits, proxygen::huffman::HuffNode::ch, proxygen::huffman::HuffNode::data, i, proxygen::huffman::SuperHuffNode::index, proxygen::huffman::HuffNode::isLeaf(), proxygen::huffman::HuffNode::metadata, folly::basic_fbstring< E, T, A, Storage >::push_back(), proxygen::huffman::HuffNode::superNodeIndex, table_, uint32_t, and uint8_t.

Referenced by TEST_F().

          {
  const SuperHuffNode* snode = &table_[0];
  uint32_t w = 0;
  uint32_t wbits = 0;
  uint32_t i = 0;
  while (i < size || wbits > 0) {
    // decide if we need to load more bits using an 8-bit chunk
    if (i < size && wbits < 8) {
      w = (w << 8) | buf[i];
      wbits += 8;
      i++;
    }
    // key is used for performing the indexed lookup
    uint32_t key;
    if (wbits >= 8) {
      key = w >> (wbits - 8);
    } else {
      // this the case we're at the end of the buffer
      uint8_t xbits = 8 - wbits;
      w = (w << xbits) | ((1 << xbits) - 1);
      key = w;
      wbits = 8;
    }
    // perform the indexed lookup
    const HuffNode& node = snode->index[key];
    if (node.isLeaf()) {
      // final node, we can emit the character
      literal.push_back(node.data.ch);
      wbits -= node.metadata.bits;
      snode = &table_[0];
    } else {
      // this is a branch, so we just need to move one level
      wbits -= 8;
      snode = &table_[node.data.superNodeIndex];
    }
    // remove what we've just used
    w = w & ((1 << wbits) - 1);
  }
  return true;
}

uint32_t proxygen::huffman::HuffTree::encode	(	folly::StringPiece	literal,
		folly::io::QueueAppender &	buf
	)		const

encode string literal into huffman encoded bit stream

Parameters

literal	string to encode
buf	where to append the encoded binary data

Definition at line 133 of file Huffman.cpp.

References bits_, ch, codes_, i, folly::io::detail::Writable< Derived >::push(), folly::Range< Iter >::size(), uint32_t, uint8_t, and folly::io::detail::Writable< Derived >::writeBE().

Referenced by TEST_F().

                                                           {
  uint32_t code;  // the huffman code of a given character
  uint8_t bits;   // on how many bits code is represented
  uint32_t w = 0; // 4-byte word used for packing bits and write it to memory
  uint8_t wbits = 0;  // how many bits we have in 'w'
  uint32_t totalBytes = 0;
  for (size_t i = 0; i < literal.size(); i++) {
    uint8_t ch = literal[i];
    code = codes_[ch];
    bits = bits_[ch];

    if (wbits + bits < 32) {
      w = (w << bits) | code;
      wbits += bits;
    } else {
      uint8_t xbits = wbits + bits - 32;
      w = (w << (bits - xbits)) | (code >> xbits);
      // write the word into the buffer by converting to network order, which
      // takes care of the endianness problems
      buf.writeBE<uint32_t>(w);
      totalBytes += 4;
      // carry for next batch
      wbits = xbits;
      w = code & ((1 << xbits) - 1);
    }
  }
  // we might have some padding at the byte level
  if (wbits & 0x7) {
    // padding bits
    uint8_t padbits = 8 - (wbits & 0x7);
    w = (w << padbits) | ((1 << padbits) - 1);

    wbits += padbits;
  }
  // we need to write the leftover bytes, from 1 to 4 bytes
  if (wbits > 0) {
    uint8_t bytes = wbits >> 3;
    // align the bits to the MSB
    w = w << (32 - wbits);
    // set the bytes in the network order and copy w[0], w[1]...
    w = htonl(w);
    // we need to use memcpy because we might write less than 4 bytes
    buf.push((uint8_t*)&w, bytes);
    totalBytes += bytes;
  }
  return totalBytes;
}

void proxygen::huffman::HuffTree::fillIndex ( SuperHuffNode &  snode, uint32_t  code, uint8_t  bits, uint8_t  ch, uint8_t  level  )

private

recursive function for generating subtrees

Definition at line 109 of file Huffman.cpp.

References proxygen::huffman::HuffNode::bits, proxygen::huffman::HuffNode::ch, ch, proxygen::huffman::HuffNode::data, proxygen::huffman::SuperHuffNode::index, proxygen::huffman::HuffNode::metadata, and uint8_t.

Referenced by insert().

                               {
  if (level == 8) {
    snode.index[code].data.ch = ch;
    snode.index[code].metadata.bits = bits;
    return;
  }
  // generate the bit at the current level
  code = code << 1;
  for (uint8_t bit = 0; bit <= 1; bit++) {
    fillIndex(snode, code | bit, bits, ch, level + 1);
  }
}

pair< uint32_t, uint8_t > proxygen::huffman::HuffTree::getCode

(

uint8_t

ch

)

const

get the binary representation for a given character, as a 32-bit word and a number of bits is represented on (<32). The code is aligned to LSB.

Parameters

ch	ASCII character

Returns

pair<word, bits>

Example: 'e' will be encoded as 1 using 4 bits: 0001

Definition at line 196 of file Huffman.cpp.

References bits_, and codes_.

                                                          {
  return std::make_pair(codes_[ch], bits_[ch]);
}

uint32_t proxygen::huffman::HuffTree::getEncodeSize

(

folly::StringPiece

literal

)

const

get the encode size for a string literal, works as a dry-run for the encode useful to allocate enough buffer space before doing the actual encode

Parameters

literal

string literal

Returns

size how many bytes it will take to encode the given string

Definition at line 182 of file Huffman.cpp.

References bits_, ch, i, folly::size(), folly::Range< Iter >::size(), uint32_t, and uint8_t.

Referenced by TEST_F().

                                                               {
  uint32_t totalBits = 0;
  for (size_t i = 0; i < literal.size(); i++) {
    // we just need the number of bits
    uint8_t ch = literal[i];
    totalBits += bits_[ch];
  }
  uint32_t size = totalBits >> 3;
  if (totalBits & 0x07) {
    ++size;
  }
  return size;
}

void proxygen::huffman::HuffTree::insert ( uint32_t  code, uint8_t  bits, uint8_t  ch  )

private

insert a new character into the tree, identified by an unique code, a number of bits to represent it. The code is aligned at LSB.

Definition at line 78 of file Huffman.cpp.

References proxygen::huffman::HuffNode::data, fillIndex(), proxygen::huffman::SuperHuffNode::index, proxygen::huffman::HuffNode::isLeaf(), proxygen::huffman::HuffNode::isSuperNode, proxygen::huffman::HuffNode::metadata, nodes_, proxygen::huffman::HuffNode::superNodeIndex, table_, uint32_t, and x.

Referenced by buildTree().

                                                             {
  SuperHuffNode* snode = &table_[0];
  while (bits > 8) {
    uint32_t mask = 0xFF << (bits - 8);
    uint32_t x = (code & mask) >> (bits - 8);
    // mark this node as branch
    if (snode->index[x].isLeaf()) {
      nodes_++;
      HuffNode& node = snode->index[x];
      node.metadata.isSuperNode = true;
      node.data.superNodeIndex = nodes_;
    }
    snode = &table_[snode->index[x].data.superNodeIndex];
    bits -= 8;
    code = code & ~mask;
  }
  // fill the node with all the suffixes
  fillIndex(*snode, code, bits, ch, bits);
}

Member Data Documentation

const uint8_t* proxygen::huffman::HuffTree::bits_

private

Definition at line 148 of file Huffman.h.

Referenced by bitsTable(), buildTree(), encode(), getCode(), and getEncodeSize().

const uint32_t* proxygen::huffman::HuffTree::codes_

private

Definition at line 147 of file Huffman.h.

Referenced by buildTree(), codesTable(), encode(), and getCode().

uint32_t proxygen::huffman::HuffTree::nodes_ {0}

private

Definition at line 146 of file Huffman.h.

Referenced by insert().

SuperHuffNode proxygen::huffman::HuffTree::table_[46]

protected

Definition at line 152 of file Huffman.h.

Referenced by decode(), and insert().

---

The documentation for this class was generated from the following files:

• proxygen/lib/http/codec/compress/Huffman.h
• proxygen/lib/http/codec/compress/Huffman.cpp