Forem: Kristijan Sedlak

How do UDP and TCP work?

Kristijan Sedlak — Wed, 29 Dec 2021 10:59:52 +0000

It seems the deeper we go according to the OSI classification, the less one deals with this topic. If you are developing applications that communicate over the network, it would be nice to understand how things actually work, right? Let us take a look at how today's computers work and the role that sockets, ports, and processes play.

As an example, let us take a normal computer that has an operating system (OS). In the OS there is a part called "network stack" which takes care of network communication. In it there is an array of port numbers from 0 to 65535, where 0-1023 are known ports and 1024-65535 are treated as random ports. On the OS there is a part (I call it stage) where processes are handled - i.e. software or applications. When a process communicates over a network stack, the process is called a service. In this way, when we communicate, we define exactly what kind of process it is.

Let’s take a look at how communication between processes works. The diagram below shows two processes, one of which is a server and the other a client. To make it as understandable as possible, both processes (services) run on the same computer.

┌──────────────────────────────────────────────────┐────────────┐
│    ┌────────────┐                                │            │
│    │    ...     │                                │            │
│    ├────────────┤   ┌──────────────────────────┐ │ ┌────────┐ │
│ ┌─▶│ PORT=8080  │◀─▶│  SOCK=10.0.1.10:8080:TCP │◀┼▶│ SERVER │ │
│ │  ├────────────┤   └──────────────────────────┘ │ └────────┘ │
│ │  │    ...     │                                │            │
│ │  ├────────────┤   ┌──────────────────────────┐ │ ┌────────┐ │
│ └─▶│ PORT=50000 │◀─▶│ SOCK=10.0.0.10:50000:TCP │◀┼▶│ CLIENT │ │
│    ├────────────┤   └──────────────────────────┘ │ └────────┘ │
│    │    ...     │                                │            │
│    └────────────┘                                │            │
├──────────────────────────────────────────────────├────────────┤
│                   Network Stack                  │    Stage   │
└──────────────────────────────────────────────────└────────────┘
│                        Operating System                       │
└───────────────────────────────────────────────────────────────┘

For a process to communicate over a network with another local process or a process on another computer, it must first ask the OS to create a socket. A socket represents the communication interface between the process and the OS's network stack. It contains information about IP, port and communication protocol (e.g. TCP or UDP).

The OS thus creates a socket and the process gets a handle to the network stack. In order for the process to actually communicate with other services, it must send a "bind" request to the operating system, which binds the socket to a specific port number. This means that messages are sent over this port and incoming messages from other services that communicate with this service are also sent over the same port.

This concept applies to both the server and the client. This is the part where application developers get confused, because higher level programming, especially over TCP, hides all these things and people feel that bind is synonymous with the function listen and is exclusively for a server listening and waiting for incoming connections. So the client also needs a socket bound to a port to communicate with the server. The server service usually defines the known port over which it wants to communicate. The client can use a feature of the operating system that is intelligent enough to automatically bind the client to one of the available random ports when it sends the message for the first time, so that the client does not have to perform this step explicitly.

Now that the server and client are connected to the network stack, both can send a message since the path from server to client is known. Such a unique communication path is also called a 5-tuple.

┌─────────────┬─────────────┬─────────────┬─────────────┬─────────────┐
│ Local IP    │ Remote IP   │ Local Port  │ Remote Port │ Protocol    │
│ 10.0.0.10   │ 10.0.0.10   │ 8080        │ 50000       │ TCP         │
└─────────────┴─────────────┴─────────────┴─────────────┴─────────────┘

The TCP and UDP protocol data about the sender and the receiver are appended to the beginning of the header of each message. TCP and UDP both belong to the OSI layer 4 transport protocols. They are similar and at the same time very different.

TCP is a robust and proven protocol that drives most online communication today. It is reliable and we can trust that packets sent will always arrive at their destination. UDP, on the other hand, is very lightweight, faster than TCP, but unreliable and sent packets can be lost without the sender being informed. TCP is connection-oriented, meaning that the protocol establishes a stateful connection between two endpoints before it can start sending messages. UDP is connectionless, meaning that it simply starts sending messages and is not interested in details.

TCP is an ordered data transmission and therefore determines the order in which packets sent on the other end must be processed. With UDP, the packets can be sent in the wrong order. TCP has many other features like "error recovery" and "flow control" and hence is popular for HTTP communication. UDP, on the other hand, is mainly used for video streaming or similar cases where it does not matter if a packet is lost.

The main argument for using TCP is that we can trust it to deliver the packet to the designated location. However, UDP can also be given similar properties with some additional programming. An example of this is QUIC, the protocol we associate with the upcoming HTTP/3, which is otherwise intended for general use.

Deep dive into the binary algorithm of Protocol Buffers

Kristijan Sedlak — Tue, 21 Sep 2021 21:52:11 +0000

When a human-understandable format is not a priority, it is best to think binary. Protocol Buffers, also know as protobufs or protos, is an open-source interface description language originally developed by Google and a library that allows JSON-like data messages to be transmitted over the wire without unnecessary ballast. Today, it is most relevant in the context of gRPC, where RPC server and client code for arbitrary programming languages is generated based on Protocol Buffers descriptions.

Protocol Buffers were developed primarily with the goal of speeding up the transmission of strongly typed key-value message objects over the network, which in turn means reducing the amount of data that needs to be transmitted over the wire from A to B. In this article, I focus on the process of encoding and decoding data, i.e. at the wire protocol level.

REST and RPC are two concepts that are now considered a kind of de facto way of developing APIs in web development. Communication between the client and the server is mostly about transferring data in JSON format. This is user-friendly but highly suboptimal at the network level. So people have developed compression mechanisms like that and others, but if you really want to optimize something, you have to start from scratch at the network layer and work your way up from there to the user part, not the other way around.

There are a variety of alternatives to sending JSON-like data such as Apache Thrift, Ion, the Bond protocol (Microsoft), Apache Avro, SBE, Bincode, CBir, MsgPack, Cap'n Proto, Flatbuffers and others could be enumerated. All of these are solutions to the same problem, at least at the network level. In terms of strongly-typed messages over the wire, Protocol Buffers are one of the most optimized protocols and are also growing in popularity, especially in the world of Kubernetes and similar communities. In fact, it is a good and popular solution, which makes it an obvious choice.

Protocol Buffers is a simple protocol that can be explained on a plain sheet of paper. The documentation is quite loosely formulated but does not answer all the questions you might encounter during implementation. Protocol Buffers is, fortunately, open source and any doubts can be cleared by looking at the source code written by the main authors.

The encoder and decoder convert messages from input keys to a shrunken binary format and back. Property names are represented in the Protocol Buffers by unique numbers rather than strings. Compared to the raw JSON format, this already has a significant impact on the final size of the message that is then sent over the wire.

+-------------------+------------------+-------------------+
+      1. JSON      +   2. Transform   +     3. Encode     + 
+-------------------+------------------+-------------------+
+ {                 +                  +                   +
+   "name": "John", + 1, John          + 0a 04 4a 6f 68 6e +
+   "age": 35       + 2, 35            + 10 23             +
+ }                 +                  +                   +
+-------------------+------------------+-------------------+
+      6. JSON      +    5. Rebuild    +     4. Decode     + 
+-------------------+------------------+-------------------+

In addition, Protocol Buffers cover 4 wire types, allowing 18 data types to be represented.

Type	Meaning	Used For
0	Varint	int32, int64, uint32, uint64, sint32, sint64, bool, enum
1	64-bit	fixed64, sfixed64, double
2	Length-delimited	string, bytes, embedded messages, packed repeated fields
5	32-bit	fixed32, sfixed32, float

The encoder converts the message into a binary format. The message is then represented on the wire as a kind of flattened sequence of encoded key-value properties. The key and the value are encoded separately. Each wire type has its own rules and therefore its own way of encoding.

[key1][value1][key2][value2] ... [keyN][valueN]

The key is encoded as a uint32 varint type, and in the last 3 bits (T) contains the wire type. The key's field tag can thus be between 1 and 2^29 - 1 = 536,870,911 (0 is not a valid tag number).

tag = 12345 (unsigned 32-bit), type = 1 (Varint)

11001000 10000011 00000110 ... on the wire
CNNNNNNN CNNNNNNN CNNNNTTT ... bits per type

C = Contiunation, X = Number, T = Type

Varints are a method for serializing integers with one or more bytes. The algorithm used here is known as LEB128. All bytes except the last have the most significant bit (MSB) set (C), so that the decoder can determine where the value ends. The other 7 bits (N) of each byte are intended to represent the number.

LEB128 is an algorithm for encoding integers of arbitrary length in which the bytes are arranged in a little-endian sequence. However, the Protocol Buffers limit the size of the numbers to the supported data types.

value = 150 (unsigned 32-bit)

Standard varint encoding:
   XXXXXXXX 10010110 ... Number 150 in bytes.
   X0000001 X0010110 ... Split to 7-bit sequence.
   X0010110 X0000001 ... Revert the array of bytes.
   10010110 00000001 ... Add MSB (1=continuation, 0=last byte).

Standard varint decoding:
   10010110 00000001 ... Encoded number.
   00000001 10010110 ... Revert the array of bytes.
   X0000001 X0010110 ... Remove MSB.
   XXXXXXXX 10010110 ... Merge bits together (number 150 in bytes).

There is a big difference between signed integer types (sint32 and sint64) and the "standard" integer types (int32 and int64). If you use int32 or int64 as the type for a negative number, the result is always ten bytes long, which makes a very large unsigned integer. In case you know that the value will most likely be negative, you can optimize the result and use one of the signed types, where the resulting varint uses ZigZag encoding for efficiency. Essentially, this means that the positive and negative integers are zigzagged through so that -1 is encoded as 1, 1 as 2, -2 as 3, and so on.

value = -12345 (signed 32-bit)

Signed 32-bit varint encoding:
   -12345 ... Unsigned 32-bit integer.
    24689 ... ZigZag value using (value << 1) ^ (value >> 31).
          ... Continue with the standard varint encoding.
Signed 32-bit varint decoding:
          ... Start with the standard varint decoding.
    24689 ... ZigZag value using (value >> 1) ^ -(value & 1).
   -12345 ... Unsigned 32-bit integer.

value = -54321 (signed 64-bit)

Signed 64-bit varint encoding:
   -54321 ... Unsigned 64-bit integer.
   108641 ... ZigZag value using (val << 1) ^ (val >> 63).
          ... Continue with the standard varint encoding.
Signed 64-bit varint decoding:
          ... Start with the standard varint decoding.
   108641 ... ZigZag value using (value >> 1) ^ -(value & 1).
   -54321 ... Unsigned 64-bit integer.

Numbers can also be represented by the wire types 1 or 5. These are 32-bit data types float, fixed32 and sfixed32 and 64-bit data types double, fixed64 and sfixed64. These numbers are simply represented by bytes in little-endian byte order (so in a reversed order).

value = 12345 (signed 32-bit)

Fixed-size encoding:
   00000000 00000000 00110000 00111001 ... Value in (big-endian) bytes.
   00111001 00110000 00000000 00000000 ... Reverse bytes to little-endian order.
Fixed-size decoding:
   00111001 00110000 00000000 00000000 ... Encoded value in (little-endian) order.
   00000000 00000000 00110000 00111001 ... Value in (big-endian) bytes.

What about wire type 2? "Length-delimited" means that the value is a varint encoded length, followed by the specified number of bytes of data. This describes strings, embedded messages (nested objects), and raw bytes data type.

value = "foo"

Length-delimited encoding:
   00000011 XXXXXXXX XXXXXXXX XXXXXXXX ... Encode message size (3 bytes) as standard 32-bit varint.
   00000011 01100110 01101111 01101111 ... Append string (foo) in bytes.

Finally, let us mention repeated fields. These represent arrays of one data type. There are no special encoding rules other than the rule that each element in an array is sent as a separate key-value encoded stream, with all of these fields having the same tag number.

Well, not everything above is completely true. If the array contains elements of numeric types, the array can be shrunk into what is called a "packed" encoding, where the key is sent only once, followed by the encrypted numbers in sequence. Do you remember how numbers are encoded? For numbers, this is possible because the decoder can always determine where a single number ends. With strings and related data types, this is not possible.

Packed repeated fields:
   [key][value1][value2]...[valueN]

Unpacked repeated fields:
   [key][value1][key][value2]...[key][valueN]

As you can see, Protocol Buffers deals in-depth with optimizing the representation of data types on the wire so that as little data as possible is transmitted between client and server.

As with most of my blogs, these are again my personal notes and insights I gained while implementing protocol buffers in Rust. I hope they will be of use to others as well. The library is again released as an open-source package and the source code is available on GitHub.

HPACK: The secret ingredient of HTTP/2

Kristijan Sedlak — Wed, 11 Nov 2020 13:17:13 +0000

Many protocols are now being used in a way, not at all envisioned at the time of their creation. HTTP is no exception to this. Since the amount of transferred data is getting higher each year, the HTTP protocol is regularly adopting its functioning to enhance the speed of data transfer over the wire.

In this article, I dive into one of the key features, based on which the HTTP/2 protocol significantly reduces the amount of transferred data from one entity to another. This feature is the header compression format, called HPACK. The older versions of HTTP protocol support data compression, but the HPACK introduces a whole new level of compression.

HPACK introduces a completely new approach to header packaging and management. Websites today require dozens or hundreds of requests and the redundant header fields in these requests consume bandwidth unnecessarily. Therefore, HPACK is a compressor, which's main function is to eliminate redundant header fields.

HPACK specification is rather short, but as it goes for other HTTP/2 related specifications, this one is also often unclear and ambiguous, creating numerous issues and uncertainty for implementers. It is also written with an experienced developer in mind and focuses primarily on the decoder functioning and assumes that the implementor will be knowledgeable enough to add all details he sees are needed for the working product.

On top of that, a significant shift in thinking is required from the implementer of the HTTP/2 protocol. It’s not only a single request/response session that a connection in HTTP/2 represents. We can start multiple simultaneous streams in one connection, representing multiple request/response sessions, which was not possible in the previous versions of the HTTP protocol. The HPACK compressor uses this characteristic of HTTP/2 by indexing headers considering the whole connection and not per stream, which might seem somewhat unusual. Since I was well acquainted with the HTTP protocol, I somehow missed this particular information during my first read, that’s why I’m specifically addressing it here. So please take a moment to let this last paragraph sink in before you continue reading.

Specification quickly goes into a very technical level of the HPACK decoding so it gives the impression that HPACK is very complex and contains a lot of “unnecessary” rules. While in fact, the implementation of HPACK contains three main parts of the process: Indexing table, Encoder, and Decoder.

Indexing table

Indexing table is a list, to which the HPACK saves the commonly used headers. Each entity indexes headers per connection, separately for incoming (decoding) and for outgoing (encoding) data.

The numbering of entries starts with index 1 and the first 61 headers are static items, keeping their position in the table. These are specific headers, provided by the HPACK specification, based on their statistical relevance, and therefore deserve their permanent position in the table.

Other headers are listed in the table from position 62 onwards and are called dynamic headers. Header entries are ordered as FIFO (first-in, first-out) and duplicated entries are allowed. Dynamic headers are always inserted at index 62, which shifts all indexes of the existing custom headers one step lower. For the dynamic part of the table, we need to set a limit of how many bytes of the dynamic headers the table is allowed to store. When, while adding a header, this limit is crossed, the headers are evicted from the back of the table, so the table never exceeds the limit.

This specific functioning is addressed in the HPACk specification as two separate tables, to which it refers as the static and the dynamic table. However, we are dealing with a single list, where two tables are combined into a single address space for defining index values.

The illustration below shows the structure of the indexing table.

<---------- Index Address Space --------->
<    Static Table   ><   Dynamic Table   >
+--+-------------+--++--+-------------+--+
|01|     ...     |61||62|     ...     |XX|
+--+-------------+--++II+-------------+DD+

II = Insertion point
DD = Dropping point

Let's see how such a table is used by entities. When a client sends the request, it can indicate in the header block that a particular header and potentially also its value, should be indexed. The table for outgoing headers on the client's side would thus look something like this:

Index	Name	Value
01	:authority
02	:method	GET
..	...	...
62	name1	value1
63	value2	value2

On the server’s side, when it reads the headers it would create a table that would look exactly the same. If the next client request would send the same headers, it could simply send a header block including only header indexes:

62 63

The server will then look up and expand into the full headers what those indexes represent. This essentially explains the whole concept. The mechanism is innovative and highly efficient. I guess no added discussion on its effects on the performance is necessary since there are plenty of benchmarks, proving its efficacy available online.

Encoder

The encoder performs the task of data compression. It converts the data from its original readable form into an optimized byte sequence by applying the rules defined in the HPACK specification. As explained earlier, the specification is interspersed with rules, and is best to take notes and map these rules out to understand how the compressor performs each task. This way we can understand what needs to be implemented and, most importantly, how to start the implementation process itself.

The HPACK encoding has specific rules for representing integer and string primitive types. Usually, the implementer will start with this part, since all other encoding rules are based on these primitive type representations.

Integer representation defines the rules for encoding integer numbers. Integers are used to represent name indexes, header field indexes, or character string lengths.
String literal representation defines the rules for encoding string literals. With these, we encode the header name and value literals. The content of these rules can be written in plain text format or encoded with the Huffman algorithm.

With these basic rules, HPACK defines the binary formats for the representation of the actual headers.

Indexed header field representation represents fully indexed headers. These are the headers that are stored in the indexing table under specific index numbers. Since both the header name and value are stored in the indexing table, only this index number is encoded. Such headers are really minimal and therefore optimal in terms of performance.
Literal header field representation defines headers that are not or only partially indexed. If the header field name matches the header field name of an entry stored in the static or dynamic table, the header field name can be displayed using the index of this entry. Otherwise, the header field name is displayed as a string literal. Header values are always displayed as a string literal. Such headers can be marked as "index", "do not index" or "never index". The latter tells us that the data is sensitive and that the entity should handle it with some restrictions (e.g.: protect it with a password).

HPACK is designed as a single-standing mechanism that can also be used outside the HTTP/2 protocol. For this reason, the specification provides a rule for signaling changes related to the allowed size of the dynamic table.

Dynamic table size update defines the rule for signaling changes in the size of the dynamic table. Such a change is signaled by the encoder, while the limit must be less than or equal to the limit determined by the protocol using HPACK. In HTTP/2 this limit is the last value of the SETTINGS_HEADER_TABLE_SIZE received by the decoder and acknowledged by the encoder. Encoder and decoder use the HTTP/2 protocol to communicate the change in table size and if the change is accepted at both ends, the encoder applies the change and reports it to the decoder using the HPACK mechanism.

These five rules, with some additional conditional rules as described in the HPACK specification, define the HPACK encoder.

Decoder

The decoder takes over the task of the decompressor, i.e. it executes the commands inversely to the encoder. It converts the data back into its readable form, ensuring that the indexing table is identical to that on the encoder side.

The decoder is usually the one that determines how many resources can be used for the purposes of HPACK compression, among others. The decoder signals this to the encoder in the HTTP/2 protocol with the parameter SETTINGS_HEADER_TABLE_SIZE using the SETTINGS frame. This change is made when the settings are confirmed by both sides in a way that the HTTP/2 protocol requires. In fact, the encoder is the one that actually requires a change in the size of the dynamic table to meet the requirements of the values agreed upon via the HTTP/2 protocol.

Experiments show that HPACK works very well, especially on pages with large, repetitive headers (e.g. cookies). Since most of the headers sent from entity to entity for a given website are duplicated, HPACK's table lookup mechanisms effectively eliminate these duplicate bytes from communication.

In order to get an easy to read and understand the text, I intentionally kept back with some details described in the HPACK specifications. However, I strongly recommend that you also read the official HPACK documentation. Hopefully, this will be much easier to understand thanks to this blog. I have also written a complete HPACK implementation for HTTP/2 in Rust. It is publicly available on GitHub as an open-source project. The source code is well documented and therefore a good additional source of information for all who want to know all details and tricks of HPACK.

HPACK: Huffman decoder

Kristijan Sedlak — Tue, 20 Oct 2020 09:38:13 +0000

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: Huffman translation matrix

Kristijan Sedlak — Sun, 18 Oct 2020 08:07:51 +0000

To achieve a maximum decrease in the amount of data, which is being transferred with each web request and response, HTTP/2 protocol uses HPACK format for encoding headers and Hoffman algorithm for its literal values.

In our previous article HAPCK: Huffman encoder I explained what Huffman coding is and how exactly the algorithm is used to encode the content. I continue explaining this by looking at this process from a reversed point of view. Meaning; how can we convert the encoded data back to its original form, again optimally and sustainably performance-wise. For clarity, and since there is a lot of content to cover, I’ve decided to split this into two parts, also because encoding itself entails two separate procedures.

If you search the web you won’t find a lot of information about the Huffman decoding process, and there are even less concrete examples describing the actual process. Such information can be found in scientific articles, which are hardly readable for the general public. So I have been researching this question extensively. Luckily my friend William Entriken guided me in the search for the optimal solutions by sharing how he used this kind of approach while playing chess. The trick was in The Huffman data tree being flattened to a 2-dimensional table of transitions.

When the web server receives a header, for which it determines that it contains content encoded with the canonical Huffman algorithm, it has to decode this content in the shortest possible time with as few resources as possible. The execution speed of this “simple“ task will contribute significantly to the server’s response time, and this time must be as short as possible.

Encoded Huffman data represents a bit-sequence of zeros and ones. This is where we are faced with the question number. 1: Which and how many ones and zeros represent what character?

Reading and decoding bit by bit appears to be inadequate performance-wise. I guess we all know how to read the data with reader or stream objects, thus we are aware that reading in buffered chunks outperforms reading bit by bit. So the first trick of fast Huffman decoding is reading N-bits at a time. However, this information alone does not help us much, since we cannot determine how the seemingly “random” Huffman sequence corresponds to actual data. The solution is not just in the flattening of the Huffman tree into a two-dimensional table, but to create such a matrix that enables decoding N-bits at a time. Note that we can create such a matrix for an arbitrary number of bits that the decoder will read at a time.

HPACK documentation provides an already prepared and for the web optimized Huffman code for all ASCII characters. To implement the Huffman algorithm for HPACK we’ll have to first flatten this table to a two-dimensional matrix as mentioned above. This would allow for reversing the encoded Huffman sequence back into the readable characters.

First, let’s look at such flattening on a very simple example. Our algorithm will enable the conversion of letters A, B, C, D, and E into a Huffman sequence. The Huffman code for each letter is shown in the table below.

Character	Huffman code
A	00
B	01
C	100
D	101
E	11

We have decided to flatten the Huffman table into a matrix, enabling the decoder to read Huffman bit-sequence 2-bits at a time. The illustration below shows the table structure we need to fill in.

PATH	ID	SYM	LFT	00	01	10	11
//	0	-	-	-	-	-	-

The first column PATH will serve for our notes in which we’ll store read bits so we will know what sequence refers to what table row. Reading of each character’s code always starts in the root row marked with //. The column ID will store the unique name of the row. The first row is marked with 0. The column SYM will store characters (e.g. A). Field LFT will store the information about the leftover bits. A leftover bit is a number of bits, missing to reach the full bit chunk (in our case 2 bits). For example, letter C and D have a leftover of 1, because to reach a round number of bits, which is in our case 2 bits * N, 1 bit remains. Letters A, B, and E have no leftover. The remaining columns represent the read chunk of 2 bits for all its possible values ranging from 00 (0) to 11 (3).

The table above will now be filled with data of sample Huffman coding. As mentioned previously, we are reading the Hoffman code 2-bits at a time. Let’s see how to insert data to the table for the first letter A.

Letter A is represented with code 00. Since there is no path //00 for this code in the first column, we create a new line with a new ID. There is no leftover, and in the root line to column 00 we write the ID of the newly established line. Since we read all the bits for the letter A, we also write character A in the SYM column.

Path	ID	SYM	LFT	00	01	10	11
//	0	-	-	1	-	-	-
//00	1	A	0	-	-	-	-

We then repeat this process for the letter B. The letter B is represented with code 01. Since there is no path //01 for this code, we create a new line with a new ID. There is no leftover, and in the root line in column 01 we write the ID of the newly established line. Since we read all the bits for the letter B, we also write character B to the SYM column.

Path	ID	SYM	LFT	00	01	10	11
//	0	-	-	1	2	-	-
//00	1	A	0	-	-	-	-
//01	2	B	0	-	-	-	-

The process for the letter C is somewhat different since its number of bits doesn’t correspond to 2-bits * N. The final bit is therefore missing, so we claim that it has a leftover of 1. First, we read the first 2 bits and insert them in the table following the same process as before. After that, we read the remaining bit, while assuming that all the possible variations of the missing bit exist. This is marked with X. Since one bit is missing, we note this in the column LFT.

Path	ID	SYM	LFT	00	01	10	11
//	0	-	-	1	2	3	-
//00	1	A	0	-	-	-	-
//01	2	B	0	-	-	-	-
//10	2	B	0	-	-	-	-
//10	3	-	-	4	4	-	-
//100X	4	C	1	-	-	-	-

We repeat the process for letters D and E. The final table should look like this:

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

Note that it would be correct to replace the variants marked with X with actual possible paths.

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
//1000	4	C	1	-	-	-	-
//1001	4	C	1	-	-	-	-
//1010	5	D	1	-	-	-	-
//1011	5	D	1	-	-	-	-
//11	6	E	0	-	-	-	-

The flattened form of the Huffman tree in the form of a matrix plays a crucial role in the process of decoding. I wrote a complete implementation of such a flattener for generating translation matrixes with the support for N-bits. It's written in Rust and is available open-source on GitHub.

We now have an idea of what the process of decoding looks like, using this matrix. I’ll be talking about this in the next article, where we’ll look at the decoding process in detail.

The next article HPACK: Huffman decoder continues here and describes the full decoding process.

HPACK: Huffman encoder

Kristijan Sedlak — Fri, 16 Oct 2020 11:38:36 +0000

Header Compression format for HTTP/2, known as HPACK, foresees the use of the Huffman algorithm for encoding header literal values. This contributes to the additional decrease in the quantity of data, transferred with each web request and response.

A Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman. The output from Huffman’s algorithm can be viewed as a variable-length code table for encoding a source symbol (such as a character in a file). The algorithm derives this table from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol. As in other entropy encoding methods, more common symbols are generally represented using fewer bits than less common symbols. Huffman’s method can be efficiently implemented, finding a code in time linear to the number of input weights if these weights are sorted. (Source: Wikipedia)

HPACK compression entails a pre-created canonical Huffman code table for encoding ASCII characters to the Huffman sequence. A canonical Huffman code is a particular type of Huffman code with unique properties that allow it to be described in a very compact manner. In the aforementioned table are the Huffman codes for each ASCII character with a length up to 32 bits (4x by 8 fields with value 0 or 1), in the form of base-2 integer, aligned on the most significant bit (MSB is the bit farthest to the left).

Encoding is relatively easy since we are replacing the individual characters with the Huffman code. We add the EOS sign at the end to always fill the entire octet.

[add "!"]     1111111000
[add "$"]     11111110001111111111001
[add "%"]     11111110001111111111001010101 (fix length)
[add "&"]     1111111000111111111100101010111111000
[add "A"]     1111111000111111111100101010111111000100001
[add EOS]     1111111000111111111100101010111111000100001111111111111111111111111111111

[result]      [254   ][63    ][242   ][175   ][196   ][63    ]
              111111100011111111110010101011111100010000111111

The illustration shows how the encoder iterates through all the ASCII characters and replaces them with the Huffman code. Each line ends with the EOS character which serves as (up to 7 bits) padding.

While adding the Hoffman code to the sequence, the length of the added code must exactly match the number of bits specified in the documentation. Working with Huffman codes in bytes and then converting them to other types, such as strings, could remove the prepended zeros. In such cases, we have to do some plumbing to ensure all bits are there (an example of this would be the character “%”).

Implementation could be achieved by manipulating a string of ones and zeros. However, for more complex systems such as high-performance web servers, this would not be sustainable from the performance perspective. To manage resources accordingly, we require innovation so the investments are protected.

A replacement of the string with characters such as numbers, which are more appropriate for computers, and the use of bitwise operators gives a significant increase in performance. Before this can be done, we need to have an understanding of how the numbers are added. Although we are all aware of what “1+2=3” is, or what is a concatenation of a string such as “aa+bb=aabb”, in bit operations, these rules are not quite so obvious. Let’s see an example of the addition with bits directly:

       1 +        2 =        3
00000001 | 00000010 = 00000011

For the sum of two bit numbers, we used the bitwise operator OR denoted by the "|" symbol which serves as a sign for addition "+" in our example. Its rule is to trace the bits of both numbers and, if a 0 or a 1 is found on the same spot, change their value to 1, while setting the value to 0 in other cases. This understanding now enables us to re-implement the example above.

Instead of a string, we will use a u64 data type storing a string of 64 bits. We could also use a data type with a larger capacity (such as u128), but u64 is sufficient. The storage requirement is 32 bits, which is the maximum length of the individual Huffman code plus an extra byte (8) for the surplus cell, meaning that we need 40 bits of storage altogether.

The illustration below shows individual steps for encoding a string of characters as in the example above, while the encoding is carried out with the use of numbers and bitwise operators.

[add "!"]     111111100000000000000000000000000000000000000000
[add "$"]     11111110001111111111001000000000000000000000000000000000
[add "%"]     1111111000111111111100101010100000000000000000000000000000000000 (fix length)
[add "&"]               11111111110010101011111100000000000000000000000000000000000000
[add "A"]                     1111001010101111110001000010000000000000000000000000000000000000
[add EOS]                     1111001010101111110001000011111111111111111111111111111110000000

[result]      [254   ][63    ][242   ][175   ][196   ][63    ]
              111111100011111111110010101011111100010000111111

Although the illustration is quite similar to the previous one, it is much more colorful. It is also apparent that a string of bits is getting shorter on the left and longer on the right end.

When the Huffman code is added to the string for the individual character, the algorithm immediately ensures 32 free bit spaces where the next character will be added. This is achieved by the so-called shifting bits using the “<<” bitwise operator. Since we are dealing with bit numbers, we always rotate for 1 or more bytes, dependent on the required capacity, meaning for 8*N bits. It might not be obvious but it is interesting that, by rotating bits and adding the new Huffman character, we are adding numbers in the same way as we did in the simple example previously presented.

I implemented the full encoder in Rust and is available at the public GitHub repository.

If looked at separately, the Huffman algorithm is quite simple. But when we don’t intend to only implement it, but we are, instead, interested in the maximization of the performance and lowering of used resources, things get more complicated. The performance and quality of this solution are, therefore, comparable to the implementation in some well-known web servers.

In my next article HPACK: Huffman translation matrix I dive into the decoding process.