HPACK: Huffman decoder
Tags: huffman, decoding, hpack, http2
Published: 2020-10-20 09:38:13

---
title: HPACK: Huffman decoder
published: true
description: The steps to decode a Huffman sequence by reading N-bits at a time.
tags: huffman, decoding, hpack, http2
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/740wfezp6mk30101slba.jpg
---

This is the last of a series of articles, in which I examined in detail the Huffman algorithm and its connection to [HPACK] for [HTTP/2]. In previous ones, I explained what the Huffman algorithm is, and started to explain how the encoding process of messages works, and in the last article [HPACK: Huffman translation matrix]. I already started the topic of decoding and have described the first part of the decoding process. 
 
The algorithm for decoding the [canonical Huffman] algorithm for [HPACK] is being executed based on a matrix, where the Huffman tree is shown in the form of the 2-dimensional table and is made for a specific number of bits being read at the time. 
 
In this last article, we decided that our decoder will decode the Huffman sequence by reading 2 bits at a time. For this purpose, we created a matrix, which will enable us to reverse the coded message back to the original content. 
 
| Path | ID | SYM | LFT | 00 | 01 | 10 | 11
|-|-|-|-|-|-|-|-
| // | 0 | - | - | 1 | 2 | 3 | 6
| //00 | 1 | A | 0 | - | - | - | -
| //01 | 2 | B | 0 | - | - | - | -
| //10 | 2 | B | 0 | - | - | - | -
| //10 | 3 | - | - | 4 | 4 | 5 | 5
| //100X | 4 | C | 1 | - | - | - | -
| //101X | 5 | D | 1 | - | - | - | -
| //11 | 6 | E | 0 | - | - | - | -
 
As an example we are using a sequence of characters in the order: A, D, and B. 
 
```
ADE = 0010101
```

The Huffman sequence will be decoded by reading 2 bits at a time. Every reading begins at the root symbol `//`. First, we read the first two bits `00`. In line one of the matrix at `ID=0`, we need to check where this code leads, or if it corresponds to any of the characters. Read bits lead to the second line with `ID=1` and they represent the letter A. 
 
The process is repeated for the next 2 bits `10`. This code leads us to the line with `ID=3` which doesn’t represent a character, so we continue the process for the next 2 bits `10`. This code then leads us to line 5, representing the letter D. Here we can see that the value of the column `LFT=1`, meaning that there is a leftover 1. This means that in order to continue reading bits we have to shift to one bit back and continue the process there. 
 
We position ourselves back to the root position while keeping the last bit `0`, and keep reading until we reach the sum of 2 bits. This means that we need to read only 1 bit `1`. Code `01` corresponds with character B and with this we conclude the decoding process. 
 
```
00XXXXX => A
XX10XXX => continue
XXXX10X => D
XXXXX01 => B
```
 
With the use of the translation matrix, which we created to read 2 bits at a time, we successfully decoded the Huffman sequence back into readable characters. This is how [HPACK] in [HTTP/2] decodes header literal values. The process is optimal, while it is best for web servers to read more bits at a time. Considering that the shortest Huffman code for an individual character is 5 bits long, it’s optimal, for the best ratio between speed and used resources, to read 4 bits at a time. More bits at a time mean faster decoding but at the same time a larger translation table and with it a higher memory footprint. 
 
I made a complete decoder implemented in [Rust]. It is available open-source at the public [Github repository].

[HPACK]: https://tools.ietf.org/html/rfc7541
[HTTP/2]: https://tools.ietf.org/html/rfc7540
[canonical Huffman]: https://en.wikipedia.org/wiki/Canonical_Huffman_code
[GitHub repository]: https://github.com/xpepermint/httlib-rs/tree/main/huffman
[Rust]: https://www.rust-lang.org/
[HPACK: Huffman translation matrix]: https://dev.to/xpepermint/hpack-huffman-translation-matrix-64c