I have been curious about how data compression works for a very long time - back in the day there was an archiver race, with WinRar and KGB archiver being insanely good at it. Bear in mind, those were the days where you had to use 1.44MB 3.5" magnetic "floppy" disks to transfer data - that was the era before DVD and even CD disks. And what WinRar could offer was no joke - you could compress 14MB Doom 2 and split it into 5 tomes, write each of them to a separate disk and then unarchive them on another computer - archiver would prompt you to insert the next disk with the next tome when it is done decompressing the current one.

But I digress. I was curious how WinRar can do that and how the size of the data is actually reduced.

And recently I got back to this topic. What I found was actually quite interesting.

Back in the day I had an idea to transform the data like so: for each character, replace it with a short code followed by the number of times it is repeated in a row:

AAAAABBB (8 characters)

  |
  v

A5B3 (4 characters - 50% compression!)

This is exactly what run-length encoding is doing. The problem with this solution was that even this very text does not contain a whole lot of repeated characters in a row, so it is quite inefficient:

Hello world (11 characters)

     |
     v

H1e1l2o1 1w1o1r1l1d1 (20 characters - negative 100% compression)

The next idea I had was to represent each character's original binary code with a shorter one:

Hello world

H (72 = 01001000 => 000000001)
e (101 = 01100101 => 00000010)
l (108 = 01101100 => 00000011) <------\
l (108 = 01101100 => 00000011) <-----/|
o (111 = 01101111 => 00000100) <-\    |
  (32 = 00100000 => 00000101)    |    |
w (119 = 01110111 => 00000110)   |    |
o (111 = 01101111 => 00000100) <-/    |
r (114 = 01110010 => 00000110)        |
l (108 = 01101100 => 00000011) <------/
d (100 = 01100100 => 00000111)

Original:

Hello world
01001000 01100101 01101100 01101100 01101111 00100000 01110111 01101111 01110010 01101100 01100100

New:

00000001 00000010 00000011 00000011 00000100 00000101 00000110 00000100 00000110 00000011 00000111

On itself this does not present any compression, but what if characters were packed into half-bytes? The longest short code is only 4 (meaningful) bits, so we could get rid of most of zeros:

Old:

0000'0001 0000'0010 0000'0011 0000'0011 0000'0100 0000'0101 0000'0110 0000'0100 0000'0111 0000'0011 0000'1000

(11 bytes)

New:

0001'0010 0011'0011 0100'0101 0110'0100 0111'0011 1000'0000

(6 bytes)

This is a reduction of about 50%! But this method does not preserve the mapping of characters to short codes. If we were to add this mapping, the message size would be actually much larger:

01001000 00000001 01100101 00000010 01101100 00000011 01101111 00000100 00100000 00000101 01110111 00000110 01110010 00000111 01100100 00001000
H        code     e        code     l        code     o        code     <space>  code     w        code     r        code     d        code

This is already 16 bytes. Then add the 6 bytes for the encoded message and you get 22 bytes - a -100% (negative 100%) compression again.

If the initial text was much, much longer, this could actually be an improvement, but here's the challenge: once the number of unique letters in the initial text is larger than 15 (the maximum number of variants that could be represented by 4 bits), the compression rate drops below zero - simply because we can not represent every character in less than a full byte anymore.

Literal decades of break and I learned about Huffman encoding. The idea is somewhat similar - represent each letter of the input text with a short(er) code. The algorithm looks like this: get all the unique letters of the input text, order them by the number of their occurrences in the text, in decreasing order:

l => 3
o => 2
d => 1
r => 1
w => 1
" " => 1
e => 1
H => 1

Within this list, order the pairs with the same number of occurrences by the character code, in ascending order:

l => 3
o => 2
" " => 1
H => 1
d => 1
e => 1
r => 1
w => 1

Imagine each of these entries as a node:

(l, 3) (o, 2) (" ", 1) (H, 1) (d, 1) (e, 1) (r, 1) (w, 1)

Then, take a pair of nodes with the smallest number of occurrences each and merge them into a new node with the number of occurrences as a sum of two original nodes:

                                                 (2)
                                               /     \
(l, 3) (o, 2) (" ", 1) (H, 1) (d, 1) (e, 1) (r, 1) (w, 1)

becomes

(l, 3) (o, 2) (" ", 1) (H, 1) (d, 1) (e, 1)      (2)
                                               /     \
                                            (r, 1) (w, 1)

Repeat this process until there is just one node left:

                                   (2)
                                 /     \
(l, 3) (o, 2) (" ", 1) (H, 1) (d, 1) (e, 1)      (2)
                                               /     \
                                            (r, 1) (w, 1)

becomes

(l, 3) (o, 2) (" ", 1) (H, 1)  (2)              (2)
                             /     \          /     \
                         (d, 1)  (e, 1)    (r, 1) (w, 1)

And again:

                     (2)
                   /     \
(l, 3) (o, 2) (" ", 1) (H, 1)  (2)              (2)
                             /     \          /     \
                         (d, 1)  (e, 1)    (r, 1) (w, 1)

becomes

(l, 3)  (2)   (o, 2)      (2)               (2)
      /     \           /     \           /     \
 (" ", 1) (H, 1)    (d, 1)  (e, 1)     (r, 1) (w, 1)

There are four candidates for the smallest amongst the (2) nodes: (o, 2) and three internal nodes; in this case the (o, 2) node will become the left branch (because the ordering of the characters - none of the internal nodes has the character assigned, but the (o, 2) node has it; its code is lexicographically larger than the empty character, assuming empty character has code of 0):

            (4)
          /     \
(l, 3)  (2)   (o, 2)      (2)               (2)
      /     \           /     \           /     \
 (" ", 1) (H, 1)    (d, 1)  (e, 1)     (r, 1) (w, 1)

becomes

            (4)      (l, 3)      (2)            (2)
          /     \              /     \        /     \
        (2)   (o, 2)        (r, 1) (w, 1)  (d, 1)  (e, 1)
      /     \
 (" ", 1) (H, 1)

Note how the node (l, 3) has moved to the middle of the list, between (4) and (2) nodes - this is needed to preserve the ordering by the number of occurrences.

There are two more nodes (2), join them:

                                        (4)
                                         |
                                    /----------\
                                   /            \
            (4)      (l, 3)      (2)            (2)
          /     \              /     \        /     \
        (2)   (o, 2)        (r, 1) (w, 1)  (d, 1)  (e, 1)
      /     \
 (" ", 1) (H, 1)

becomes

            (4)                   (4)        (l, 3)
          /     \                  |
        (2)   (o, 2)          /----------\
      /     \                /            \
 (" ", 1) (H, 1)           (2)            (2)
                         /     \        /     \
                      (r, 1) (w, 1)  (d, 1)  (e, 1)

Now the smallest two nodes are (l, 3) and (4):

                                        (7)
                                         |
                                    /---------\
                                   /           \
            (4)                   (4)        (l, 3)
          /     \                  |
        (2)   (o, 2)          /----------\
      /     \                /            \
 (" ", 1) (H, 1)           (2)            (2)
                         /     \        /     \
                      (r, 1) (w, 1)  (d, 1)  (e, 1)

becomes

                  (7)                      (4)
                   |                     /     \
              /---------\              (2)   (o, 2)
             /           \           /     \
            (4)        (l, 3)   (" ", 1) (H, 1)
             |
        /----------\
       /            \
     (2)            (2)
   /     \        /     \
(r, 1) (w, 1)  (d, 1)  (e, 1)

And lastly there are (7) and (4) nodes to merge:

                              (11)
                               |
                     /--------------------\
                    /                      \
                  (7)                      (4)
                   |                     /     \
              /---------\              (2)   (o, 2)
             /           \           /     \
            (4)        (l, 3)   (" ", 1) (H, 1)
             |
        /----------\
       /            \
     (2)            (2)
   /     \        /     \
(r, 1) (w, 1)  (d, 1)  (e, 1)

Then, following the rule "left branch -> '0', right branch -> '1'", mark each branches of this tree:

                              (11)
                               |
                      /------------------\
                    <0>                  <1>
                    /                      \
                  (7)                      (4)
                 /   \                    /   \
               <0>   <1>                <0>   <1>
               /       \                /       \
             (4)     (l, 3)          (2)     (o, 2)
            /   \                    /   \
          <0>   <1>                <0>   <1>
          /       \                /       \
         /         \          (" ", 1)    (H, 1)
       (2)         (2)
      /   \        /  \
    <0>   <1>    <0>   <1>
     |     |      |     |
  (r, 1) (w, 1) (d, 1) (e, 1)

Lastly, by following the branches from the root node of this tree, gather the branch labels into the binary code for each of the leaf nodes:

(l, 3, 0b01)  (o, 2, 0b11)  (" ", 1, 0b100)  (H, 1, 0b101)  (d, 1, 0b0010)  (e, 1, 0b0011)  (r, 1, 0b0000)  (w, 1, 0b0001)

This is called Huffman encoding or Huffman tree. Using these codes, the initial text Hello world is encoded as following:

H   e    l  l  o      w    o  r    l  d
101 0011 01 01 11 100 0001 11 0000 01 0010

joining into bytes

10100110 10111100 00011100 00010010

This could be programmed in Ruby like so:

s = 'Hello world'
a = s.chars.uniq.map {|c| {char: c, count: s.chars.count(c)}}.sort {|a, b| [b[:count], a[:char]] <=> [a[:count], b[:char]]}
pq = a.map { |c| {char: c[:char], count: c[:count], left: nil, right: nil} }

while pq.size > 1 do
  left, right = pq.pop(2)

  if left[:count] < right[:count]
    left, right = right, left
  end

  pq << {char: nil, count: left[:count] + right[:count], left: left, right: right}

  pq.sort! {|a,b| [b[:count], a[:char] || ''] <=> [a[:count], b[:char] || '']}
end

q = [{node: pq[0], code: ''}]

codes = {}

while q.size > 0 do
  e = q.shift

  if e[:node][:left].nil? && e[:node][:right].nil?
    codes[e[:node][:char]] = e[:code]
    next
  end

  q.push({node: e[:node][:left], code: e[:code] + '0'}) if !e[:node][:left].nil?

  q.push({node: e[:node][:right], code: e[:code] + '1'}) if !e[:node][:right].nil?
end

or in C++:

#include <string>
#include <map>
#include <queue>
#include <iostream>

struct Node {
    char c;
    int count;
    Node* left;
    Node* right;
};

struct CodeNode {
    Node* node;
    std::string code;
};

int main() {
    const std::string s = "Hello world";

    std::map<char, int> freq;

    for (auto i : s) {
        if (freq.find(i) == freq.end()) {
            freq[i] = 1;
        } else {
            freq[i]++;
        }
    }

    auto cmpNode = [](Node* a, Node* b) {
        if (a->count != b->count) {
            return a->count > b->count;
        }

        if ((a->c == static_cast<char>(255)) != (b->c == static_cast<char>(255))) {
            return b->c == static_cast<char>(255);
        }

        return a->c < b->c;
    };

    std::priority_queue<Node*, std::vector<Node*>, decltype(cmpNode)> pq(cmpNode);

    for (auto i : freq) {
        pq.push(new Node{.c = i.first, .count = i.second, .left = nullptr, .right = nullptr});
    }

    while (pq.size() > 1) {
        auto* left = pq.top();
        pq.pop();

        auto* right = pq.top();
        pq.pop();

        if (left->count < right->count) {
            std::swap(left, right);
        }

        pq.push(new Node{ .c = static_cast<char>(255), .count = left->count + right->count, .left = left, .right = right });
    }

    std::queue<CodeNode*> q;

    q.push(new CodeNode{ .node = pq.top(), .code = std::string() });

    std::map<char, std::string> codes;

    while (!q.empty()) {
        auto* e = q.front();
        q.pop();

        if (!e->node->left && !e->node->right) {
            codes[e->node->c] = e->code;
            continue;
        }

        if (e->node->left) {
            q.push(new CodeNode{ .node = e->node->left, .code = e->code + "0" });
        }

        if (e->node->right) {
            q.push(new CodeNode{ .node = e->node->right, .code = e->code + "1" });
        }
    }

    for (auto i : codes) {
        std::cout << "'" << i.first << "'" << ": " << i.second << std::endl;
    }

    return 0;
}

If the Huffman table is known, the source could be decoded by traversing from the root: if the next bit in the input sequence is 0 - traverse the left child of the current node, if the next bit is 1 - traverse the right child of the current node; if the leaf node is reached - emit a corresponding character:

In Ruby:

encoded = s.chars.map {|c| codes[c]}.join
tree = pq[0]

def decode(tree, encoded)
  root = tree
  res = ''

  encoded.chars.each do |c|
    root = if c == '0' then root[:left] else root[:right] end

    if not root[:char].nil?
      res += root[:char]
      root = tree
    end
  end

  res
end

Or in C++:

#include <string>
#include <map>
#include <queue>
#include <iostream>

struct Node {
    char c;
    int count;
    Node* left;
    Node* right;
};

struct CodeNode {
    Node* node;
    std::string code;
};

Node* buildHuffmanTree(std::string_view s) {
  std::map<char, int> freq;

  for (auto i : s) {
    if (freq.find(i) == freq.end()) {
      freq[i] = 1;
    } else {
      freq[i]++;
    }
  }

  auto cmpNode = [](Node *a, Node *b) {
    if (a->count != b->count) {
      return a->count > b->count;
    }

    if ((a->c == static_cast<char>(255)) != (b->c == static_cast<char>(255))) {
      return b->c == static_cast<char>(255);
    }

    return a->c < b->c;
  };

  std::priority_queue<Node *, std::vector<Node *>, decltype(cmpNode)> pq(
      cmpNode);

  for (auto i : freq) {
    pq.push(new Node{
        .c = i.first, .count = i.second, .left = nullptr, .right = nullptr});
  }

  while (pq.size() > 1) {
    auto *left = pq.top();
    pq.pop();

    auto *right = pq.top();
    pq.pop();

    if (left->count < right->count) {
      std::swap(left, right);
    }

    pq.push(new Node{.c = static_cast<char>(255),
                     .count = left->count + right->count,
                     .left = left,
                     .right = right});
  }

  return pq.top();
}

std::string encode(Node* tree, std::string_view s) {
  std::queue<CodeNode *> q;

  q.push(new CodeNode{.node = tree, .code = std::string()});

  std::map<char, std::string> codes;

  while (!q.empty()) {
    auto *e = q.front();
    q.pop();

    if (!e->node->left && !e->node->right) {
      codes[e->node->c] = e->code;
      continue;
    }

    if (e->node->left) {
      q.push(new CodeNode{.node = e->node->left, .code = e->code + "0"});
    }

    if (e->node->right) {
      q.push(new CodeNode{.node = e->node->right, .code = e->code + "1"});
    }
  }

  std::string res = "";

  for (auto ch : s) {
    res += codes[ch];
  }

  return res;
}

std::string decode(Node* tree, std::string_view s) {
  std::string res = "";
  auto root = tree;

  for (auto ch : s) {
    if (ch == '0') {
      root = root->left;
    } else {
      root = root->right;
    }

    if (!root->left && !root->right) {
      res += root->c;
      root = tree;
    }
  }

  return res;
}

int main() {
    const std::string s = "Hello world";

    auto root = buildHuffmanTree(s);
    
    auto encoded = encode(root, s);
    auto decoded = decode(root, encoded);

    std::cout << "Input: " << s << std::endl;
    std::cout << "Encoded: " << encoded << std::endl;
    std::cout << "Decoded: " << decoded << std::endl;

    return 0;
}

To construct a Huffman tree from encodings table (given the encodings are sorted in the descending order of their frequency), a very simple algorithm is used - traverse the tree by the bits of the character encoding and if there is no node matched, add to the last seen node - a left child if a bit is 0 or a right child if a bit is 1.

As an example from above, consider the following encodings table (sorted already):

l => 0b01; o => 0b11; " " => 0b100; H => 0b101; d => 0b0010; e => 0b0011; r => 0b0000; w => 0b0001

Iterate over the encodings one by one, starting with l => 0b01:

encoding: (l, 0b01)
tree is empty, current node (*):

   (*)

first bit: 0
add a new left child, make it the current node:

   ()
  /
(*)

next bit: 1
add a new right child to the previously added node and make it the new current node:

      ()
     /
    ()
      \
      (*)

since this is the last bit, add the value to the current node:

      ()
     /
    ()
      \
      (l)

Next encoding, o => 0b11:

encoding: (o, 0b11)
reset the current node (*) to the root:

     (*)
     /
    ()
     \
     (l)

first bit: 1
add a new right child node to the current node and make it the new current (*):

      ()
     /  \
    ()  (*)
     \
     (l)

next bit: 1
add a new right child node and make it current:

      ()
     /  \
    ()  ()
     \   \
     (l) (*)

since this is the last bit, add the value to the current node:

      ()
     /  \
    ()   ()
      \    \
      (l)  (o)

Next encoding, " " => 0b100:

encoding: (" " => 0b100)
reset the current node (*) to the root:

      (*)
     /   \
    ()    ()
      \     \
      (l)   (o)

first bit: 1
no changes to the tree, since the node exists:

      ()
     /  \
    ()   (*)
      \    \
      (l)  (o)

next bit: 0
add a new left child to the current node and make it the new current (*):

        ()
     /      \
    ()      ()
      \     / \
      (l) (*) (o)

next bit: 0
add a new left child to the current node and make it the new current (*):

        ()
     /      \
    ()      ()
     \      / \
     (l)   () (o)
          /
        (*)

since this is the last bit, add a value to the current node:

              ()
              /\
       /------  -----\
      ()             ()
       \            /  \
        (l)        ()  (o)
                   /
                 (" ")

Next encoding is H => 0b101:

reset the current node (*) to root:

              (*)
              / \
       /------   -----\
      ()              ()
       \             /  \
        (l)         ()  (o)
                    /
                  (" ")

first bit is: 1
no changes to the tree since the node exists, just make it current (*):

              ()
             /  \
      /------    -----\
    ()               (*)
      \              /  \
      (l)           ()  (o)
                   /
                 (" ")

next bit is: 0
no changes to the tree since the node exists, just make it current (*):

             ()
            /  \
     /------    -----\
    ()                ()
      \              /  \
     (l)          (*)  (o)
                  /
               (" ")

next bit is: 1
add a right child node and make it current (*):

             ()
            /  \
     /------    -----\
    ()               ()
      \             /  \
      (l)          ()  (o)
                  /  \
              (" ")  (*)

since this was the last bit, add a value to the current node:

               ()
              /  \
       /------    -----\
     ()                 ()
      \                  / \
      (l)              ()  (o)
                      /  \
                   (" ") (H)

And without going step-by-step, for all the remaining encodings:

encoding: d => 0b0010
               ()
              /  \
       /------    -----\
     ()                 ()
    /  \                / \
   ()  (l)            ()  (o)
    \                /  \
    ()           (" ")  (H)
    /
   (d)

encoding: e => 0b0011

                ()
               /  \
        /------    -----\
      ()                 ()
    /    \               /  \
   ()    (l)          ()   (o)
     \               /  \
     ()           (" ") (H)
    /  \  
   (d) (e)

encoding: r => 0b0000

                 ()
                /  \
         /------    -----\
       ()                 ()
      /   \              /  \
     ()    (l)          ()   (o)
    /  \               /  \
   ()  ()          (" ")  (H)
  /   /  \   
(r)  (d) (e) 

encoding: w => 0b0001

                    ()
                   /  \
            /------    -----\
          ()                 ()
       /     \              /  \
      ()      (l)          ()   (o)
    /    \                /  \
   ()     ()          (" ")  (H)
  / \    /  \ 
(r) (w) (d) (e)

If the initial message (Hello world) is encoded with this algorithm (to four bytes: 0xA6 0xBC 0x1C 0x12), in order to properly decode it, the tree or the code table has to be given alongside with the encoded message:

message: 'Hello world' (11 bytes)
encoded: 0xA6 0xBC 0x1C 0x12 (4 bytes)
table:   {"l"=>"01", "o"=>"11", " "=>"100", "H"=>"101", "r"=>"0000", "w"=>"0001", "d"=>"0010", "e"=>"0011"} (8 keys + 8 values = 16 bytes)
compression = 11 bytes -> 20 bytes = negative 100%

This is not entirely a compression algorithm, though. Algorithms such as ZIP (DEFLATE) and JPEG (although slightly different in details, the general approach still applicable) go further to compress the table itself. To understand how they work, one needs to understand the tricks behind them.

Canonical Huffman codes

There is one issue with just general Huffman encoding: there are multiple ways to build a different tree for the same input. Refer to the early stage of encoding from above:

(l, 3)  (2)   (o, 2)      (2)               (2)
      /     \           /     \           /     \
 (" ", 1) (H, 1)    (d, 1)  (e, 1)     (r, 1) (w, 1)

Here's the non-deterministic part: which pair of nodes to merge next? Depending on the choice, the code for each character would be different (although the code length would remain the same).

That's where canonical Huffman codes come into play: this simple algorithm unifies the logic, transforming any valid Huffman tree for a given input into the same tree (so the codes remain the same).

To obtain canonical codes from any valid Huffman tree for a given input, the codes are transformed following two simple rules:

1. sort the codes by code length (ascending) and then by character (also ascendig)
2. starting with current_code = 0 and current_length = 0, iterate over each code length (assume iterator is length_i):
3. if the length is greater than current_length, left shift current_code by the difference length_i - current_length
4. increment current_code, filling the unused left-most bits with zeroes
5. update current_length to length_i

In the example above, the codes are:

l:   01
o:   11
" ": 100
H:   101
r:   0000
w:   0001
d:   0010
e:   0011

The lengths of those codes are:

l:   2 (Huffman code: '01', length of '01' = 2)
o:   2 (Huffman code: '11', length of '11' = 2)
" ": 3 (Huffman code: '100', length of '100' = 3)
H:   3 (Huffman code: '101', length of '101' = 3)
r:   4 (Huffman code: '0000', length of '0000' = 4)
w:   4 (Huffman code: '0001', length of '0001' = 4)
d:   4 (Huffman code: '0010', length of '0010' = 4)
e:   4 (Huffman code: '0011', length of '0011' = 4)

Making these codes canonical requires sorting by Huffman code's length first and then by character (I have left old codes in braces for reference):

l:   2 (old code: 01, its length = 2)
o:   2 (old code: 11, its length = 2)
" ": 3 (old code: 100, its length = 3)
H:   3 (old code: 101, its length = 3)
d:   4 (old code: 0010, its length = 4)
e:   4 (old code: 0011, its length = 4)
r:   4 (old code: 0000, its length = 4)
w:   4 (old code: 0001, its length = 4)

Then, re-assign codes, starting with 0 and padding to the length of old code:

l:   00 (old code length = 2, next code = 00 + 1 = 01)
o:   01 (old code length = 2, next code = 01 + 1 = 10)
" ": 100 (old code length = 3; but previous entry ('o' = 01) has length 2, so shift left by 1 bit ('10' << 1 == '100'); next code = 100 + 1 = 101)
H:   101 (old code length = 3; next code = 101 + 1 = 110)
d:   1100 (old code length = 4; but previous entry ('H' = 101) has length 3, so shift left by 1 bit ('110' << 1 == '1100'); next code = 1100 + 1 = 1101)
e:   1101 (old code length = 4; next code = 1101 + 1 = 1110)
r:   1110 (old code length = 4; next code = 1110 + 1 = 1111)
w:   1111 (old code length = 4)

Interestingly, this code did not use the previous codes themselves. This implies the codes could be calculated automatically if only the lengths of the codes are given.

For the example above, the encoding table is:

l:   00
o:   01
" ": 100
H:   101
d:   1100
e:   1101
r:   1110
w:   1111

Encoded message with this table looks like this:

message:

Hello world

encoded:

101 1101 00 00 01 100 1111 01 1110 00 1100

joined:

10111010000011001111011110001100

In Ruby:

def build_canonical_table(codes)
    codes = codes.sort_by {|k, v| [v.length, k]}
    canonical_codes = {}
    curr_code = 0
    prev_length = 0

    codes.each do |char, old_code|
        curr_code <<= (old_code.length - prev_length)
        canonical_codes[char] = curr_code.to_s(2).rjust(old_code.length, '0')
        curr_code += 1
        prev_length = old_code.length
    end

    canonical_codes
end

In C++:

std::vector<std::pair<char, std::string>> sorted_codes(codes.begin(), codes.end());

std::sort(sorted_codes.begin(), sorted_codes.end(),
    [](const auto& a, const auto& b) {
        if (a.second.length() != b.second.length()) {
            return a.second.length() < b.second.length();
        }

        return a.first < b.first;
    });

std::map<char, std::string> canonical_codes;

int curr_code = 0;
int prev_length = 0;

for (auto [ch, code] : sorted_codes) {
    curr_code <<= (code.length() - prev_length);
    canonical_codes[ch] = std::bitset<32>(curr_code).to_string().substr(32 - code.length());
    curr_code++;
    prev_length = code.length();
}

ZIP, DEFLATE

DEFLATE algorithm compresses the list of codes lengths using a constant table, defined by the standard (or algorithm description, if you will).

The constant table is defined in the archiver code itself, so it remains the same for all archives and does not need to be a part of archive itself.

The archive, on the other hand, stores a list of 256 values, each representing the length of the code of the corresponding character.

For example, archive may store a list like this:

0, 0, 2, 2, 4, 0, 0, 0, 0, ... (total 256 elements, all the rest are zeros)

But this is highly inefficient, so this list is also comressed using Huffman encoding. The difference is that this list is first compressed using run-length encoding (from the very top of this blog) and the result is compressed using the pre-defined Huffman table.

Step-by-step this looks like this: first, the original content is compressed. This produces a Huffman table. Assume this table of canonical Huffman codes for input Hello world:

l  : "00"
o  : "01"
" ": "100"
H  : "101"
d  : "1100"
e  : "1101"
r  : "1110"
w  : "1111"

As described above, for canonical Huffman codes, storing only codes' lengths is enough to reconstruct the codes:

"00"   : 2
"01"   : 2
"100"  : 3
"101"  : 3
"1100" : 4
"1101" : 4
"1110" : 4
"1111" : 4

So the table of codes' lengths looks like this:

1: 0 (codes of length 1: none)
2: 2 (codes of length 2: two codes)
3: 2 (codes of length 3: two codes)
4: 4 (codes of length 4: four codes)

This table looks very much like an indexed array (1-based, though - indexes start at 1 instead of 0 like in C), so it could be represented as an array.

Given this data, at any point Huffman codes could be re-created:

code = 0

// lengths: [0, 2, 2, 4]

length_i = 1, codes_length_i = 0;
  no codes of length 1 => skip

length_i = 2, codes_length_i = 2;
  code (0) << 1 => code = 00;
  create <codes_length_i (2)> codes:
    emit code (00), code += 1 (code = 01);
    emit code (01), code += 1 (code = 10);

length_i = 3, codes_length_i = 2;
  code (10) << 1 => code = 100;
  create <codes_length_i (2)> codes:
    emit code (100), code += 1 (code = 101)
    emit code (101), code += 1 (code = 110);

length_i = 4, codes_length_i = 4;
  code (110) << 1 => code = 1100;
  create <codes_length_i (4)> codes:
    emit code (1100), code += 1 (code = 1101);
    emit code (1101), code += 1 (code = 1110);
    emit code (1110), code += 1 (code = 1111);
    emit code (1111), code += 1 (code = 1100);

So for the list of codes lengths [0, 2, 2, 4] the re-created codes will be

00
01
100
101
1100
1101
1110
1111

In Ruby:

def recreate_canonical_huffman_codes(codes_of_length)
  code = 0
  res = []
  
  codes_of_length.each_with_index do |n, len|
    code <<= 1

    n.times do
      res << code.to_s(2).rjust(len+1, '0')
      code += 1
    end
  end

  res
end

For the second phase, the original symbols have to be correlated with these codes somehow. DEFLATE does not store the symbols or their corresponding encodings at any point - instead it uses smart algorithm to encode the encodings (so meta!) for all possible symbols.

Referring back to the compressed content's table of codes:

l  : "00" (code length: 2)
o  : "01" (code length: 2)
" ": "100" (code length: 3)
H  : "101" (code length: 3)
d  : "1100" (code length: 4)
e  : "1101" (code length: 4)
r  : "1110" (code length: 4)
w  : "1111" (code length: 4)

In a similar manner to codes lengths' table, a table of all possible 256 byte values (ASCII table, effectively) is created and the corresponding byte's code length is written to this table:

0x00: 0
0x01: 0
0x02: 0
...
0x20 (" "): 3
...
0x48 (H)  : 3
...
0x64 (d)  : 4
0x65 (e)  : 4
...
0x6c (l)  : 2
...
0x6f (o)  : 2
...
0x72 (r)  : 4
...
0x77 (w)  : 4
...

Instead of hexadecimal values, here's decimal representation:

32  (" ") : 3
72  (H)   : 3
100 (d)   : 4
101 (e)   : 4
108 (l)   : 2
111 (o)   : 2
114 (r)   : 4
119 (w)   : 4

This list could be written as follows:

index: [0, 1, 2, 3, 4, ..., 31, 32, 33, 34, 35, ..., 71, 72, 73, ..., 99, 100, 101, 102, ..., 108, ..., 111, 112, 113, 114, ..., 119, ..., 255 ]
value: [0, 0, 0, 0, 0, ..., 0,  3,  0,  0,  0,  ...,  0,  3,  0, ...,  0,   4,   4,   0, ...,   2, ...,   2,   0,   0,   4, ...,   4, ..., 0 ]

This list contains a lot of duplications and a lot of zeroes. It is then compressed using the run-length algorithm (from the very top of this blog), which now makes sense:

(0, 32), (3, 1), (0, 39), (3, 1), (0, 27), (4, 1), (4, 1), (0, 6), (2, 1), (0, 2), (2, 1), (0, 2), (4, 1), (0, 4), (4, 1), (0, 136)

But DEFLATE does it smarter - it uses pre-defined table of symbols, again:

• for zero value, use zero itself
• for values 1..15, use the value itself as a code
• to repeat previous value 3..6 times, use code 16 and 3 extra bits to represent how many repetitions (000 - repeat previous value 3 times, 001 - repeat previous value 4 times, 010 - repeat previous value 5 times, 011 - repeat previous value 6 times)
• to repeat value 0 3..10 times, use code 17 and extra bits
• to repeat value 0 11..138 times, use code 18 and extra bits

And then DEFLATE compresses the table of codes' lenghts with Huffman encoding. Since there is a very limited number of characters to encode (1..15, 16, 17, 18 - 19 values total), the maximum code length, even if all of these values were used, would be about 4 bits. The values 16, 17 and 18 will always be followed by a pre-defined number of bits (extra bits describing a parameter), so when decoding, if the value decoded is one of those three (16, 17 or 18), the following pre-defined number of bits are interpreted differently.

Look at this process step-by-step. First, the code lenghts array is replaced with the codes from above using run-length algorithm:

Repeated zeros are represented by following this simple table:

• single zero: 0
• two zeros: 0, 0 (two zero bytes)
• 3..10 zeros: 17 followed by
  • 0 for 3 zeros
  • 1 for 4 zeros
  • 2 for 5 zeros
  • etc.
  • 7 for 10 zeros
• 11..138 zeros: 18 followed by
  • 0 for 11 zeros
  • 1 for 12 zeros
  • etc.
  • 127 for 138 zeros

These extra bits are not encoded using Huffman codes. The rest of the codes (raw values 0..15, 16, 17, 18) are encoded according to their frequencies.

(0, 32)  -> 18 (repeat '0' 32 times), followed by extra bits representing 32 repetition: 32 - 11 = 21 (0b00010101)
(3, 1)   -> 3
(0, 39)  -> 18 (repeat '0' 39 times), followed by extra bits representing 39 repetitions: 39 - 11 = 28 (0b00011100)
(3, 1)   -> 3
(0, 27)  -> 18 (repeat '0' 27 times), followed by extra bits representing 27 repetitions: 27 - 11 = 16 (0b00010000)
(4, 1)   -> 4
(4, 1)   -> 4
(0, 6)   -> 17 (repeat '0' 6 times), followed by extra bits representing 6 repetitions: 6 - 3 = 3 (0b00000011)
(2, 1)   -> 2
(0, 2)   -> [0, 0]
(2, 1)   -> 2
(0, 2)   -> [0, 0]
(4, 1)   -> 4
(0, 4)   -> 17 (repeat '0' 4 times), followed by extra bits representing 4 repetitions: 4 - 3 = 1 (0b00000001)
(4, 1)   -> 4
(0, 136) -> 18 (repeat '0' 136 times), followed by extra bits representing 136 repetitions: 136 - 11 = 125 (0b01111101)

After this, the codes lengths list becomes:

18, 21 (0b00010101), 3, 18, 28 (0b00011100), 3, 18, 16 (0b00010000), 4, 4, 17, 3 (0b00000011), 2, 0, 0, 2, 0, 0, 4, 17, 1 (0b00000001), 4, 18, 125 (0b01111101)

In Ruby:

def running_codes_lengths(codes)
    codes_lengths = (0..255).map {|i| (codes[i.chr] || '').length}

    result = []
    i = 0

    while i < codes_lengths.size
        len = codes_lengths[i]
        run_length = 1

        while i + run_length < codes_lengths.size && codes_lengths[i + run_length] == len
            run_length += 1
        end

        i += run_length

        if len == 0
            while run_length > 0
                if run_length >= 11
                    # code 18, repeat '0' 11..138 times
                    diff = [138, [11, run_length].max].min
                    result << [18, diff - 11]
                    run_length -= diff
                elsif run_length >= 3
                    # code 17, repeat '0' 3..10 times
                    diff = [10, [3, run_length].max].min
                    result << [17, diff - 3]
                    run_length -= diff
                else
                    result += [0] * run_length
                    run_length = 0
                end
            end
        elsif len != 0 && run_length >= 3
            result << len
            run_length -= 1

            while run_length > 0
                # code 16, repeat previous value 3..6 times
                diff = [6, [3, run_length].max].min
                result << [16, diff - 3]
                run_length -= diff
            end
        else
            run_length.times { result << len }
            run_length = 0
        end
    end

    result
end

In C++:

struct CodeLengthNode {
    size_t length;
    int extra_bits;
};

std::vector<CodeLengthNode*> code_lengths;

for (auto i = 0; i < 256; i++) {
    auto length = canonical_codes[i].length();
    auto run_length = 1;

    while (i + run_length < 256 && canonical_codes[i + run_length].length() == length) {
        run_length++;
    }

    i += run_length - 1;

    if (length == 0) {
        while (run_length > 0) {
            if (run_length >= 11) {
                // code 18, repeat '0' 11..138 times
                auto diff = std::min(138, std::max(11, run_length));

                code_lengths.push_back(new CodeLengthNode{ .length = 18, .extra_bits = diff - 11 });

                run_length -= diff;
            }
            else if (run_length >= 3) {
                // code 17, repeat '0' 3..10 times
                auto diff = std::min(10, std::max(3, run_length));

                code_lengths.push_back(new CodeLengthNode{ .length = 17, .extra_bits = diff - 3 });

                run_length -= diff;
            }
            else {
                for (auto t = 0; t < run_length; t++) {
                    code_lengths.push_back(new CodeLengthNode{ .length = 0, .extra_bits = 0 });
                }

                run_length = 0;
            }
        }
    }
    else if (length != 0 && run_length >= 3) {
        code_lengths.push_back(new CodeLengthNode{ .length = length, .extra_bits = 0 });
        run_length--;

        while (run_length > 0) {
            auto diff = std::min(6, std::max(3, run_length));
            code_lengths.push_back(new CodeLengthNode{ .length = 16, .extra_bits = diff - 3 });
            run_length -= diff;
        }
    }
    else {
        for (auto t = 0; t < run_length; t++) {
            code_lengths.push_back(new CodeLengthNode{ .length = length, .extra_bits = 0 });
        }

        run_length = 0;
    }
}

To compress this list, ignore the extra bits and count values 0..18 only:

18, 21, 3, 18, 28, 3, 18, 16, 4, 4, 17, 3, 2, 0, 0, 2, 0, 0, 4, 17, 1, 4, 18, 125

without extra bit values:

18, 3, 18, 3, 18, 16, 4, 4, 17, 3, 2, 0, 0, 2, 0, 0, 4, 17, 1, 4, 18

counts:

18 : 4
3  : 3
16 : 1
4  : 4
17 : 2
2  : 2
0  : 4
1  : 1

Next, order these mappings by count, followed by the number itself (key of this dictionary / hashmap):

0  : 4
4  : 4
18 : 4
3  : 3
2  : 2
17 : 2
1  : 1
16 : 1

Then, create Huffman tree for these counts:

step 1:

     (8)            (7)            (4)            (2)
   /     \        /     \       /      \       /      \
(0, 4) (4, 4) (18, 4) (3, 3) (2, 2) (17, 2) (1, 1) (16, 1)

step 2:
                                           (6)
                                     /            \
     (8)            (7)            (4)            (2)
   /     \        /     \       /      \       /      \
(0, 4) (4, 4) (18, 4) (3, 3) (2, 2) (17, 2) (1, 1) (16, 1)

step 3:
                                 (13)
                         /                \
                        /                  \
                       /                   (6)
                      /              /            \
     (8)            (7)            (4)            (2)
   /     \        /     \       /      \       /      \
(0, 4) (4, 4) (18, 4) (3, 3) (2, 2) (17, 2) (1, 1) (16, 1)

step 4:
                    (21)
            /                   \
           /                   (13)
          /              /                \
         /              /                  \
        /              /                   (6)
       /              /              /            \
     (8)            (7)            (4)            (2)
   /     \        /     \       /      \       /      \
(0, 4) (4, 4) (18, 4) (3, 3) (2, 2) (17, 2) (1, 1) (16, 1)

Following the rule "left branch => 0, right branch => 1", traverse the tree and assign codes to each leaf node:

                    (21)
                /               \
               /                <1>
              /                   \
            <0>                  (13)
            /              /             \
           /              /               <1>
          /             <0>                 \
         /              /                   (6)
        /              /             <0>        <1>
       /              /              /            \
     (8)            (7)            (4)            (2)
     / \           /  \           /   \          /   \
   <0> <1>       <0>  <1>       <0>    <1>     <0>   <1>
   /     \       /      \       /       \      /       \
(0, 4) (4, 4) (18, 4) (3, 3) (2, 2) (17, 2) (1, 1)  (16, 1)

yields:

(0, 4, 00) (4, 4, 01) (18, 4, 100) (3, 3, 101) (2, 2, 1100) (17, 2, 1101) (1, 1, 1110) (16, 1, 1111)

or

0 (4 occurrences)  : 00
4 (4 occurrences)  : 01
18 (4 occurrences) : 100
3 (3 occurrences)  : 101
2 (2 occurrences)  : 1100
17 (2 occurrences) : 1101
1 (1 occurrences)  : 1110
16 (1 occurrences) : 1111

Then, assign the canonical Huffman codes:

step 1: sort codes by lengths and code itself:

0  : 00    (code length: 2)
4  : 01    (code length: 2)
18 : 100   (code length: 3)
3  : 101   (code length: 3)
2  : 1100  (code length: 4)
17 : 1101  (code length: 4)
1  : 1110  (code length: 4)
16 : 1111  (code length: 4)

becomes

0  : 00    (code length: 2)
4  : 01    (code length: 2)
3  : 101   (code length: 3)
18 : 100   (code length: 3)
1  : 1110  (code length: 4)
2  : 1100  (code length: 4)
16 : 1111  (code length: 4)
17 : 1101  (code length: 4)

step 2: assign incrementing and shifting code:

code = 0, previous_length = 0

0  : 00    (code length: 2), code = 00, next code = 01
4  : 01    (code length: 2), code = 01, next code = 10
3  : 101   (code length: 3), length > previus_length => shift code, code = 100, next code = 101
18 : 100   (code length: 3), code = 101, next code = 110
1  : 1110  (code length: 4), length > previous_length => shift code, code = 1100, next code = 1101
2  : 1100  (code length: 4), code = 1101, next code = 1110
16 : 1111  (code length: 4), code = 1110, next code = 1111
17 : 1101  (code length: 4), code = 1111

Going back to what the initial codes' lengths list was (the thing being encoded):

18, 21 (0b00010101), 3, 18, 28 (0b00011100), 3, 18, 16 (0b00010000), 4, 4, 17, 3 (0b00000011), 2, 0, 0, 2, 0, 0, 4, 17, 1 (0b00000001), 4, 18, 125 (0b01111101)

Now encoded with this new Huffman encoding:

100, 00010101, 101, 100, 00011100, 101, 100, 1111, 00010000, 01, 01, 1101, 101, 00000011, 1100, 00, 00, 1100, 00, 00, 01, 1101, 1110, 00000001, 01, 100, 01111101

joined:

1000001010110110000011100101100111100010000010111011010000001111000000110000000111011110000000010110001111101

And the tree for this encoding could be just a list of 19 elements (one for each code used in this code lengths encoding) of codes lengths (for the encoded code lengths list):

0  : 00    (code length: 2)
4  : 01    (code length: 2)
3  : 101   (code length: 3)
18 : 100   (code length: 3)
1  : 1110  (code length: 4)
2  : 1100  (code length: 4)
16 : 1111  (code length: 4)
17 : 1101  (code length: 4)

simplified:

0  : 2
1  : 4
2  : 4
3  : 3
4  : 2
16 : 4
17 : 4
18 : 3

becomes

index: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 ]
value: [ 2, 4, 4, 3, 2, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  4,  4,  3 ]

or just

2, 4, 4, 3, 2, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  4,  4,  3

Note one interesting observation: since there is a very limited number of symbols used to encode code lengths, the maximum code for them is 7, which is 3 bits long. This means the new encodings for code lengths table could be packed into 3 bit chunks, further reducing the size of this tree:

codes lengths (for codes lengths, so meta!):

2, 4, 4, 3, 2, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  4,  4,  3

encoded into binary:

010, 100, 100, 011, 010, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 100, 100, 011

joined:

010100100011010000000000000000000000000000000000100100011

Now, build the header for the archive, consisting of code lengths encoded with DEFLATE:

code lengths tree:

010100100011010000000000000000000000000000000000100100011

code lengths for each character, encoded:

1000001010110110000011100101100111100010000010111011010000001111000000110000000111011110000000010110001111101

in bytes:

01010010 01110100 00000000 00000000 00000000 00000000 10010001 11000001 01001011 00000111 00101100 11110001 00000101 11011010 00000111 10000001 10000000 11101111 00000000 10110001 111101

in hex:

0x52 0x74 0x00 0x00 0x00 0x00 0x91 0xC1 0x4B 0x07 0x2C 0xF1 0x05 0xDA 0x07 0x81 0x80 0xEF 0x00 0xB1 0x3D

And build the content of the archive, which is just the encoded message (from a while ago):

encoded message:

10111010000011001111011110001100

in bytes:

10111010 00001100 11110111 10001100

in hex:

0xBA 0x0C 0xF7 0x8C

Joining header and the body:

0x52 0x74 0x00 0x00 0x00 0x00 0x91 0xC1 0x4B 0x07 0x2C 0xF1 0x05 0xDA 0x07 0x81 0x80 0xEF 0x00 0xB1 0x3D 0xBA 0x0C 0xF7 0x8C

Funny enough, the length of this archive is much longer than the original message itself - 25 bytes vs original 11 - more than negative 100% increase in size. But the important part is that this is due to the fact that the message is short and most symbols only occur once. On a longer text the compression is actually good: a typical AI response compression:

Source length: 3994
Encoded length: 2632
> encoded length: 2573
> header length: 59
>> header1 length: 8
>> header2 length: 51
Compression rate: 51%

Decoding works the same three-step way, just in the reverse:

1. decode canonical Huffman tree for codes' lengths
2. decode codes' lengths and build the canonical Huffman tree again
3. decode the message using that tree

The only tricky part there is decoding the codes' lengths, since it involves re-building the symbols + extra bits for repeated values.

Decoding codes' lengths:

def decode_code_lengths_lengths(header)
    bits = header.bytes.map {|ch| ch.to_s(2).rjust(8, '0')}.join

    code_lengths = []

    (0..18).each do |e|
        start_bit = e * 3
        three_bits = bits[start_bit, 3]
        length = three_bits.to_i(2)
        code_lengths[e] = length
    end

    code_lengths
end

Then the canonical Huffman codes are reconstructed for decoding next stage of codes' lengths:

def recreate_huffman_codes(code_lengths)
    symbols_with_lengths = code_lengths.each_with_index.filter {|len, _| len > 0}.map {|len, s| [s, len] }.sort_by {|s, len| [len, s]}

    res = Array.new(code_lengths.size)
    prev_length = 0
    code = 0

    symbols_with_lengths.each do |s, len|
        code <<= (len - prev_length)
        res[s] = code.to_s(2).rjust(len, '0')
        code += 1
        prev_length = len
    end

    res
end

This is then used to decode running lengths (compressed lengths):

def decode_compressed_code_lengths(bits, codes_lengths_tree)
    tree_inv = codes_lengths_tree.each_with_index.to_h

    compressed_code_lengths = []
    bit_pos = 0
    buf = ''
    decoded_count = 0

    while bit_pos < bits.length && decoded_count < 256
        buf += bits[bit_pos]
        bit_pos += 1

        if tree_inv.key?(buf)
            symbol = tree_inv[buf]
            buf = ''

            case symbol
            when 16
                extra_bits = bits[bit_pos, 2].to_i(2)
                bit_pos += 2
                compressed_code_lengths << [16, extra_bits]
                decoded_count += 3 + extra_bits # code 16 repeats 3-6 repetitions
            when 17
                extra_bits = bits[bit_pos, 3].to_i(2)
                bit_pos += 3
                compressed_code_lengths << [17, extra_bits]
                decoded_count += 3 + extra_bits # code 17 repeats 3-10 repetitions
            when 18
                extra_bits = bits[bit_pos, 7].to_i(2)
                bit_pos += 7
                compressed_code_lengths << [18, extra_bits]
                decoded_count += 11 + extra_bits # code 18 repeats 11-138 repetitions
            else
                compressed_code_lengths << symbol
                decoded_count += 1 # any other code adds 1 instance of itself
            end
        end
    end

    compressed_code_lengths
end

Which is then used to reconstruct all codes' lengths for all symbols:

def decode_running_lengths(compressed_code_lengths)
    res = []

    compressed_code_lengths.each do |e|
        if e.is_a?(Array)
            code, extras = e

            case code
            when 16
                repeats = 3 + extras
                repeats.times { res << res.last }

            when 17
                repeats = 3 + extras
                repeats.times { res << 0 }

            when 18
                repeats = 11 + extras
                repeats.times { res << 0 }
            end
        else
            res << e
        end
    end

    res
end

These last two methods are there just to showcase the same process as encoding, but in reverse. Practically speaking, it does not make sense to build the intermediate running lengths encoding (with codes 16, 17 and 18) and the actual list could be built in-place:

def decode_codes_lengths(header, codes_lengths_tree)
    bits = header.bytes.map {|b| b.to_s(2).rjust(8, '0')}.join

    tree_inv = codes_lengths_tree.each_with_index.to_h

    bit_pos = 0
    buf = ''

    res = []

    while bit_pos < bits.length && res.size < 256
        buf += bits[bit_pos]
        bit_pos += 1

        if tree_inv.key?(buf)
            symbol = tree_inv[buf]
            buf = ''

            case symbol
            when 16
                extra_bits = bits[bit_pos, 2].to_i(2)
                bit_pos += 2
                repeats = 3 + extra_bits
                repeats.times { res << res.last }
            when 17
                extra_bits = bits[bit_pos, 3].to_i(2)
                bit_pos += 3
                repeats = 3 + extra_bits
                repeats.times { res << 0 }
            when 18
                extra_bits = bits[bit_pos, 7].to_i(2)
                bit_pos += 7
                repeats = 11 + extra_bits
                repeats.times { res << 0 }
            else
                res << symbol
            end
        end
    end

    res
end

This list is then used to create the ultimate canonical Huffman codes for the message itself (the "body" of the archive), by calling recreate_huffman_codes:

def decode(header1, header2, body)
    code_lengths_lengths = decode_code_lengths_lengths(header1)
    tree = recreate_huffman_codes(code_lengths_lengths)
    codes_lengths = decode_codes_lengths(header2, tree)

    codes = recreate_huffman_codes(codes_lengths)
    decode_body(body, codes)
end

Decoding the body with this tree is simple:

def decode_with_tree(bits, tree)
    tree_inv = tree.each_with_index.to_h

    res = []
    buf = ''

    bits.each_char do |bit|
        buf += bit

        if tree_inv.key? buf
            res << tree_inv[buf]
            buf = ''
        end
    end

    res
end

def decode_body(body, codes_lengths)
    bits = body.bytes.map {|b| b.to_s(2).rjust(8, '0')}.join
    bytes = decode_with_tree(bits, codes_lengths)
    bytes.pack('C*').force_encoding('UTF-8')
end

Note how these methods use string.bytes instead of string.chars - this is to make the algorithm work with UTF-8 characters and not only ASCII.

JPEG, DHT

Define Huffman Table uses a much simpler approach - it stores the list of codes lengths using an index-as-value approach - a list of 16 values effectively translated as "element at index 'i' tells how many codes of length 'i' are there in the table". This list is followed by the list of raw characters used in the message.

For example, an array like this

[0, 0, 2, 2, 4, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0]

is expanded like so:

index: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
value: [0, 0, 2, 2, 4, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0]

codes of length 0: 0
codes of length 1: 0
codes of length 2: 2
codes of length 3: 2
codes of length 4: 4
codes of length 5: 0
codes of length 6: 0
codes of length 7: 0
codes of length 8: 0
codes of length 9: 0
codes of length 10: 0
codes of length 11: 0
codes of length 12: 0
codes of length 13: 0
codes of length 14: 0
codes of length 15: 0

For the Hello world message, the archive header, comprising of codes' lengths and the alphabet, would look as following:

canonical Huffman codes:

l:   00   (length: 2)
o:   01   (length: 2)
" ": 100  (length: 3)
H:   101  (length: 3)
d:   1100 (length: 4)
e:   1101 (length: 4)
r:   1110 (length: 4)
w:   1111 (length: 4)

number of codes per length:

[ 0, 0, 2, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

alphabet (in order same order as canonical Huffman codes table):

[ l, o, " ", H, d, e, r, w ]

Followed by the encoded message, the entire archive would look like this:

codes per length:

[ 0, 0, 2, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

in bytes:

0x00 0x00 0x02 0x02 0x04 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00

alphabet:

[ l, o, " ", H, d, e, r, w ]

in bytes:

0x6C 0x6F 0x20 0x48 0x64 0x65 0x72 0x77

encoded message:

10111010000011001111011110001100

in bytes:

0xBA 0x0C 0xF7 0x8C

combined:

0x00 0x00 0x02 0x02 0x04 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6C 0x6F 0x20 0x48 0x64 0x65 0x72 0x77 0xBA 0x0C 0xF7 0x8C

The total length is 28, almost triple the original length!

Implementing this in Ruby:

# using the three helpers from the previous implementations - build_tree, build_table, build_canonical_table
def build_canonical_codes(message)
  build_canonical_table(build_table(build_tree(message.bytes)))
end

def encode(message)
  codes = build_canonical_codes(message)
  grouped_codes = codes.values.group_by { |code| code.length }

  codes_count_by_length = grouped_codes.transform_values { |cs| cs.size }

  header1 = (1..15).map { |len| codes_count_by_length[len] || 0 }
  header2 = codes.keys
  body = message.bytes.map { |byte| codes[byte] }.join.chars.each_slice(8).map { |slice| slice.join.ljust(8, '0').to_i(2) }

  {
    header1: header1,
    header2: header2,
    body: body
  }
end

Then, the final message would be comprised of joining those parts together:

r = encode('Hello world')
[ :header1, :header2, :body ].map { |k| r[k].pack('C*').force_encoding('UTF-8') }.join

As I said before, for a simple message such as Hello world the archive is 27 bytes long, which is longer than the original data itself. But for something longer, like the AI chatbot response from before it is actually a bit better:

Original message: 3994
Encoded message: 2598
> header1: 15
> header2: 90
> body: 2573
Compression ratio: 49%

Decoding this is much simpler than DEFLATE: all there is to do is to reconstruct canonical Huffman codes from the number of codes by length (16-element-array)

# using `recreate_huffman_codes` helper from before
# decode_with_table is slightly different from decode_with_tree
def decode_with_table(bits, table)
    res = []
    buf = ''

    bits.each_char do |bit|
        buf += bit

        if table.key? buf
            res << table[buf]
            buf = ''
        end
    end

    res
end

def decode(message)
  bytes = message.bytes

  counts_encoded = bytes[0, 15]
  counts = counts_encoded.each_with_index.map { |n, len| [ len + 1 ] * n }.flatten
  codes = recreate_huffman_codes count

  symbols = bytes[15, codes.size]
  table = codes.zip(symbols).to_h
  
  body_encoded = bytes[15 + codes.size ..]
  body_bits = body_encoded.map { |b| b.to_s(2).rjust(8, '0') }.join
  body_decoded = decode_with_table(body_bits, table)

  body_decoded.pack('C*').force_encoding('UTF-8')
end

All the code in this blog is available in a separate repo.

My teammate has faced an issue when running our SpringBoot application in IntelliJ Idea: there were certain Gradle artifacts cached between switching the branches, which prevented the application from running. The issue is easily solved by running clean Gradle task. But my teammate was running it using IntelliJ's UI. And by default, it does not do a clean build before running - just the normal build, if the files have changed.

The solution was a bit of UI trickery.

In the run menu, edit the run configuration (from the meatball menu):

From the run configuration window, click the "Modify options" link:

In the "Before launch" section of a very long drop-down menu, click the "Add before launch task":

From the "Add task" pop-up menu select "Run Gradle task":

In the Gradle tak window fill out the "Gradle project" and "Tasks" fields (they both have auto-complete):

Bear in mind: this advice might become obsolete as IntelliJ team changes their new UI.

I was using vim on-and-off since my pal showed me Linux on my first ever computer, back in circa 2005. I then learned emacs back in 2015 and used it for remote development (over SSH). That was the first time I used a bunch of plugins to improve my developer experience. Then, circa 2022, I heard about an interesting take on vim ideology - Kakoune. I liked how it allowed user to see what he is about to operate on before actually performing an action. I did not end up using it often, but I liked the idea. Then at the end of 2024, I heard about Helix - another take on Vim ideology (or more like Kakoune at that point). At some random morning, scrolling the suggested videos on YouTube, I stumbled upon a semi-interesting (at the time) video about Vim productivity tips. Creator showed an interesting plugin, flash, which allowed him to quickly jump between any two points on the screen - much faster and easier than what I usually would do in Vim (relative line numbers and motions). I really liked the idea, to a point where I was on the edge of giving it a try. Since we have a few people in our team using NeoVim or Vim plugin for VS Code or IntelliJ Idea, I thought about using each of them for a while for work and comparing the experience.

IntelliJ Idea, baseline

For a number of years, the way I develop in IntelliJ is quite keyboard-centric - I disable tabs and use Shift-Shift menu and its tabs to navigate the project and perform actions.

The quick action menu has 6 tabs:

• Classes
• Files
• Symbols
• Actions
• Text
• All (combined of the above)

For the most part I only use Classes, Files and Actions tabs via a keyboard shortcut. From the Actions tab I rarely use more than "rename", "extract variable/method" or "copy path/reference".

The only other two features of the IDE I actually use are the file tree (so that I can see the structure of the project - it comes handy for Java packages organization, for example) which I configure to automatically focus the file currently opened in the editor and the terminal, which I use for pretty much everything else (including Git interactions and running / building project).

Actually, IntelliJ Idea gives you the statistics of features you use in the Help -> My Productivity menu.

In my case it looks like this (ordered by the usage frequency, descending - from most used to least):

• Recent files
• Go to declaration
• Code completion
• Syntax-aware selection (Cmd + w)
• Find in files
• Context actions (suggestions like "remove unused", "replace with X", "import Y", etc.)
• Find (in current file)
• Toggle comment
• Go to file
• Go to class
• Rename
• Find and replace (in current file)
• Generate code (constructors, getters and setters)
• Go to implementation
• Introduce variable
• Change case (camel case)
• Implement methods

Some of these (implement methods, introduce variable, generate code) might be hard to achieve in either of editors, so they are not requirements, but rather nice to haves.

So this would be my measure of success in other editors (in terms of comfort) - on top of movement in a document, I would like to compare the editors in terms of moving in the project (files, symbols / classes and references) and quick actions.

NeoVim

I thought about trying NeoVim since it was the hype at the time. I was dumbfolded by the fact it did not even come with the default config file to work with (in a stumbling contrast to Helix, which has :config-open and :config-reload commands built in). Yet I kept going, spending days perfecting my config. I switched my terminal emulator from Warp to Ghostty (so that I can see images right inside my terminal, improving file manager experience), installed a good dozen of plugins and messed with color schemes.

My full neovim config is actually public.

After almost a week, my NeoVim plugin setup looked like this:

• Lazy - plugin manager
• Telescope - for fzf and quick actions
• Neo-tree - the file tree

These three plugins alone allowed me to already be quite a bit productive compared to vanilla Vim experience. But it was not a complete setup:

• telescope-file-browser (?) - as an alternative for Neo-tree
• telescope-ui-select - for LSP integration (code actions, specifically)
• mason - for LSP management
• mason-lspconfig - a middleware between mason and lspconfig
• nvim-lspconfig - for configuring LSP in NeoVim
• nvim-treesitter - for treesitter integration
• toggleterm - terminal integration, toggleable; obsolete when using zellij
• vim-sleuth - automatically detects tabwidth settings for the buffer
• Comment.nvim - toggle comment for lines and blocks

A rather large set of plugins is required for autocomplete to work:

• nvim-cmp - autocomplete engine
• cmp-nvim-lsp - autocomplete integration for LSP
• cmp-path - autocomplete for file paths
• LuaSnip - snippets for Lua
• cmp_luasnip - autocomplete integration for luasnip
• friendly-snippets - a set of snippets
• lspkind.nvim - icons for autocomplete options

Those plugins make up for almost a complete setup.

But I wanted to further improve the Vim experience somewhat so motions become easier (like in the video from the top of the post):

• nvim-treesitter-textobjects (?) - for moving between text blocks (paragraphs, function / class scopes, parameters, etc.)
• nvim-surround - for operations on surrounding characters (braces, brackets, quotes, ticks, etc.)
• flash - the fast movements
• vim-visual-multi - true multi-cursor editing (unlike visual block mode, which would require macros for the best experience)

And there are a few quality-of-life improvements:

• undotree - local file history
• noice - moves command line and search line to the middle of the screen, in a popup panel
• indent-blankline - to show indentation lines
• cmp-cmdline - for autocomplete suggestions in the Noice command popup
• nvim-treesitter-context - shows the current context as fixed lines at the top of the screen (like in VSCode)
• outline with outline-treesitter-provider - shows symbols defined in the current buffer
• quicker - allows for better quickref buffer experience
• telescope-live-grep-args - allows to search not by text (or regex) alone, but also by filename / filetype (and more)

The config I have at the moment allows the following:

• file tree
  • <leader>n toggles NeoTree
  • when NeoVim opens, NeoTree opens too later I decided against this, since sometimes I want to just edit a single file without a care for the directory containing it
  • NeoTree follows the currently open file
  • NeoTree shows hidden files (including dot files and directories, like .github, which are hidden by default)
  • when NeoTree is the last open buffer, NeoVim will quit
• movements
  • s performs a Flash search (with literal references to different points in text)
  • S-s performs a treesitter Flash search
• terminal
  • trying to utilize zellij instead of built-in NeoVim terminal, following the "one tool for its purpose" principle
  • <leader>t toggles a terminal
  • C-\ C-n switches terminal to Normal mode, but I also remapped it to <Esc><Esc>
  • i switches terminal to Insert mode
• navigation
  • C-left / C-right goes through the jumplist (similarly to back/forward in IntelliJ / VSCode)
• editing
  • ys<motion><character> wraps selected text in a specified character
  • cs<old char><new char> changes the wrapped character around text under cursor from <old char> to <new char>
  • ds<char> deletes wrapped character around text under cursor
  • gcc comments / uncomments the line
  • gc comments the selected block of text
  • <Esc> in Normal mode sends nohlsearch to remove search highlights
  • <leader>u shows a list of changes (undo tree), aka local file history
  • C-n / C-<down> / C-<up> creates a new cursor for the same word occurrences / below current cursor / above current cursor
• LSP
  • S-k shows the hint for the symbol under cursor
  • <leader>ca (built-in gra since NeoVim 0.11) shows code actions for the symbol under cursor in a Telescope panel
  • treesitter-textobjects provides custom scopes (like w for word or W for WORD):
    • ac / ic - outer class code / inner class code
    • af / if - outer function / inner function
    • as - local scope
    • ai / ii - outer function call / inner function call (i for invocation)
    • ap / ip - outer / inner parameter
    • ar / ir - outer / inner return statement
  • <leader>o shows list of symbols defined in the current buffer (outline)
  • gr (built-in grr since NeoVim 0.11) shows a list of LSP references; <C-q> sends the list of locations to quick buffer
  • gd shows a list of LSP definitions
  • gI (built-in gri since NeoVim 0.11) shows a list of LSP implementations
  • grn (built-in since NeoVim 0.11) renames a symbol under cursor
  • C-s (built-in since NeoVim 0.11) shows method signature reference
  • ]d / [d (built-in) goes to previous / next diagnostic message location (e.g. warnings, errors, suggestions in the code)
  • C-w,d shows the diagnostic message at cursor
• Telescope
  • <leader><leader> opens a quick action menu (Telescope builtin)
  • <leader>f opens search in files
  • <leader>gf opens search only in files tracked by Git
  • <leader>b opens a list of NeoVim buffers, ignoring current buffer and sorting by last used timestamp
  • <leader>/ performs a live-grep (with arguments) on files
  • C-q (in the search results; needs Zellij in the locked mode - C-g - to prevent conflict) moves files to quickref buffer; then
    • ]c / [c for next / previous quickref entry
    • <leader>q toggles quickref buffer
    • <leader>l toggles locations buffer

Aside from ridiculous amount of time spent configuring Neovim, it ticks most of my boxes:

• Recent files ✅ <leader>b
• Go to declaration ✅ gd
• Code completion ✅ (nvim-cmp) C-space
• Syntax-aware selection ✅ (nvim-treesitter with customized incremental_selection): initialize treesitter selection mode with gsn and then increment / decrement node selection with gss and gsm
• Find in files ✅ <leader>/ (telescope + telescope-live-grep-args, rg-powered)
• Context actions ✅ gra
• Find in current file ✅ /
• Toggle comment ✅ gcc / gc<object> (e.g. gcaw - comment word)
• Go to file ✅ <leader>f
• Go to class ✅ <leader>S (telescope + LSP)
• Rename ✅ grn
• Find and replace in current file :%s/<search>/<replace>
• Generate code ❌
• Go to implementation ✅ gri
• Introduce variable ❌
• Change case ✅ (text-case.nvim or through external program)
• Implement methods ❌

Helix

Actually, my first try was Helix, but I immediately stumbled upon the first blocker - the task I was working on at that time involved some Mustache templates. And Helix did not support it even on the most basic level (syntax highlighting). Moreover, Helix did not have plugins at the time, so there was little I could do for that particular task. The reason I wanted at least syntax highlighting had to do with the issue I was working on, which had misplaced conditionals in the template file, resulting in an incorrect rendering. I liked, however, how Helix came with a lot of handy utilities out of the box - the file picker, treesitter integration (so I could jump between the rest of Java / TypeScript codebase with ease).

I tried configuring a file tree via Yazi, which has an integration example on their website (using zellij terminal multiplexer panels), but it just refused to work for me on my Mac. That was when I timeboxed this and decided to switch my focus to NeoVim for the moment being.

After a while of just living my life, a new version of Helix has dropped, 25.07. And it introduced a few quality o flife changes. For example, the file explorer, which is now built in. It is not as powerful as Yazi, but it does the job. So I decided to switch to Helix for a while.

Upon getting back to Helix some time after, there was a new release, 25.07.1 which introduced a few quality of life improvements, including the file browser, sort of addressing the file tree issue I had before. Invoked with <leader>e (compared to <lead>f which just lists all the files in one long list), this one allows you to see directories. It is sort of an immediate-mode file manager as in it only shows the contents of a selected directory, but it is arguably more useful solution to the file tree problem than a list of all the files (recursively listing sub-directories). Additionally, tree-sitter was replaced so the syntax highlighting should be better - this would most likely be helpful in content like my blogs, often featuring multiple languages on top of the main Markdown.

Something that I liked about Helix was how it handles selections. For the most part, native multi-cursor is a great start - you just have to remember the difference between splitting the selection and selecting inside the selection - S (split) vs s (select) - both would create multiple cursors, just in a different way.

Different selection objects, including the ones provided by the tree-sitter - with the match mode you can select different objects (ma and mi are your friends). But you can also surround the selection (ms<char>) and change the surrounding (mr<from><to>) and delete the surrounding (md<char>), which I find pretty handy sometimes.

Some things I find bearable are the use of external tools for some actions, instead of plugins. Since Helix lacks plugin system in any shape or form (as of late October 2025), you can just pipe the selection to the external program. One such case is changing the case of selection - I use this often, especially in conjunction with multiple cursors - to quickly edit, say test data or a bunch of constants or to refactor multiple class fields. In this case I found a comment on Github suggesting the use of ccase - you first need to install this Rust utility, ccase, and then you'll be able to send your selection(-s) by using :pipe ccase -t screamingsnake, for instance.

Something I did not realize until writing this blog is that there are some really useful default keybindings for insert mode, like Ctrl+w to delete the previous word, Alt+w to delete the next word, Ctrl+k to delete to the end of the line and Ctrl+x to trigger autocomplete.

One annoying thing about Helix is the buffer picker (available via <lead>b) - it shows the list of open buffers (files). It does not appear to be sorting the elements of the list and the first element is always the current buffer. This is not really helpful if you want to quickly go the previously edited file. To make things worse, it does not seem to have any configuration around it, so the behaviour is pretty much set in stone.

I also am still missing one feature which made me try NeoVim in the first place, which is flash.nvim for quick jumps on the screen. Helix team did add something similar to HopWord command from hop.nvim, called goto_word, available via gw key shortcut. But unlike hop.nvim, Helix implementation is barely configurable (you can only configure the alphabet used for making labels) and comes with just one mode - HopWord. Additionally, it enforces exactly two-character abbreviations (jump labels). I thought this is rather limiting and since Helix is an open-source project, I decided to implement a behaviour similar to leap.nvim, since it is much less obstructive (it does not cover your entire screen in labels, making it super hard to figure out where you want to jump) and it allows to narrow down the places to jump by having prefix search. So I raised a PR and a suggestion discussion on Helix Github repo. To which the team just said "we don't want it" and dismissed the proposal:

We made intentional choices when implementing the goto_word behavior. We were quite aware if the nvim plugins. We are not going to replace or add alternative commands

One comment pointed to the plugin system when it is available:

I'm not inclined to add more jumping commands as core Helix commands like gw. There are a lot of different spins on jumping functions in Neovim plugins and I believe that future work should be done in plugins (once available) rather than as core faetures.

For context, plugin system has been discussed for over three years (as the moment of this writing, since September 2022) and apparently has been worked on for over two years (since October 2023). So I have no hope of seeing it released in the near future.

But instead of giving up, I decided to give a try to this work-in-progress plugin system and after a week a flash.hx plugin was born.

Here is my condensed cheatsheet of key shortcuts I use in Helix:

• Pickers
  • <lead>b buffer list
  • <lead>e file explorer; far superior to file list
  • <lead>/ search
  • <lead>d show diagnostics (hints, errors, warnings, etc)
• Multiple cursors
  • , collapse all cursors into one
  • s select in selection; create a new cursor at each selection; takes a regexp as a pattern
  • S split selection; create a new cursor at each occurrence of pattern; takes regexp as a pattern
• Selection
  • v enters visual (selection) mode; this is how you can select multiple words - vwwww
  • m enters marking mode; this is how you can select paragraphs, text and LSP objects, add, change and remove wrapping characters (like brackets and quotes); few examples:
    • mi( - select inside parentheses
    • ma" - select everything inside double-quotes and the double-quotes themselves
    • ms[ - surround selection with square brackets
    • mr[( - replace the surrounding square brackets with regular braces
    • mif - select the body of a function (method)
  • = / < / > - format / unindent / indent selection
  • :pipe or | - send selection to an external program and replace selection with the output of said program
    • as of version 25.7 you can also use interpolation with %{}, for instance, %{cursor_line} or %{buffer_name}, so you can pass in the filename to the external tool
  • % - select an entire buffer (file)
  • <lead><c> / <lead><C> - comment/uncomment the selection
• Go to
  • gl / gh - go to end of line / start of line (contrary to $ and ^ in Vim)
  • gg / ge - go to first line / last line of the file
  • Ctrl+i / Ctrl+o - go back and forth in your jumplist (places where the cursor has been placed; jumplist itself is available with <lead>j)
  • gd / gD - go to definition / declaration
  • gr - go to references
• Copying (yanking)
  • "+y - copy to the OS clip buffer (translates to "change the buffer to the + - OS clipboard and then yank the selection")

After a few weeks of working in Helix I was pleasantly surprised by how much out-of-the-box stuff it comes shipped with. And I did not have to spend a whole lot of time configuring it (aside from that week I spent developing flash.hx).

It checks most of my boxes too:

• Recent files ✅ <leader>b
• Go to declaration ✅ gd
• Code completion ✅ C-x
• Syntax-aware selection ✅ m<selection><see tooltip>
• Find in files ✅ <leader>/ (simplified)
• Context actions ✅ <leader>a (depends on LSP)
• Find in current file ✅ /
• Toggle comment ✅ <leader>c
• Go to file ✅ <leader>f
• Go to class ✅ <leader>S (capital S for workspace symbols, lowercase s for current file symbols) (partial)
• Rename ✅ <leader>r
• Find and replace in current file ⚠️ (unconventinal): select scope (% for current buffer), then use s to select occurrences or S to split selections into multiple cursors, then use actions - i or c to change the selections, d to delete selections
• Generate code ❌
• Go to implementation ✅ gi (depends on LSP)
• Introduce variable ❌
• Change case ✅ (through external tool): select text, then | (pipe it), then specify external program (ccase -t snake, for instance)
• Implement methods ❌

Kakoune

TBD

Final thoughts

I was surprised by how nice these seemingly limiting editors have become over the years (last time I used them was over-configured Emacs back in circa 2015)!

Although rough around the edges and coming with massive pros and massive cons, both editors are being actively developed to become even nicer.

Neovim:

• 👍 comes with some quite nice things out of the box
• 👎 the out-of-the-box niceities need LSP to be plugged in, which comes through a plugin manager
• 👍 insane amount of plugins for all sorts of things
• 👎 a proportionally insane amount of time required to find and configure the plugins to make for a comfortable experience
• 👍 overall, the experience that you can create is on its own league
• 👍 has a nice file tree implementation (yes, I like to see the structure of the directory and its parents)
• 👍 has very nice semantic and LSP selection expand
• 👍 has an OG Flash implementation
• 👍 has nice surround behaviour
• 👍 file picker powered by ripgrep so you can filter all you want
• 👎 both selection expand and surround are a bit tricky to trigger (gsn followed by gss; ysaw" and cs[( and ds")

Helix:

• 👍 comes with a ton of nice things out of the box
• 👍 none of the niceities require extensive configuration (if any at all)
• 👎 very slow development cycle, so new features do not come out often (like twice a year, I believe)
• 👎 no plugin system, making the new features even less frequent or even possible
• 👎 very strongly opinionated developers, so if you are not comfortable with a feature - tough luck!
• 👎 does not have file tree
• 👎 file picker is very basic - only offers filtering by partial path match
• 👎 semantic selection expansion is not exactly expansion, but more like "select this exact scope"
• 👍 surround and semantic selection triggers are consistent e.g. make much more sense (ms(, mr([, md[; maf, maa)

My current stance is that Neovim is a much stronger contender with a much broader set of (much better implemented) features, but the amount of time you have to spend to get to that state is enormous. And whilst much nicely organised out of the box, Helix is very much undercooked (in my opinion).

Hence, for powerful and actual workloads - use Neovim, it is worth spending all that time configuring it for that purpose. For a casual relaxing but very restricted editing - Helix is an-okay choice.

Contents

1. Introduction
2. Experiment 1, hex2rgb
3. Experiment 2, simple application
   • Elm
   • F#
   • PureScript & purescript-react-dom
   • PureScript & Halogen
   • ReasonML
   • Gleam (you are here)

import gleam/float
import gleam/option.{type Option, None, Some}
import gleam/string
import lustre
import lustre/attribute.{value}
import lustre/element.{text}
import lustre/element/html.{button, div, input, p, select}
import lustre/event.{on_click, on_input}

type Shape {
  Circle
  Square
}

type Msg {
  ShapeChanged(s: Option(Shape))
  ValueChanged(x: Float)
  CalculateArea
}

type State {
  State(shape: Option(Shape), value: Float, area: Option(Float))
}

const pi = 3.14

fn calculate_area(shape: Shape, x: Float) -> Float {
  case shape {
    Circle -> pi *. x *. x
    Square -> x *. x
  }
}

fn init(_flags) -> State {
  State(shape: None, value: 0.0, area: None)
}

fn update(model: State, msg: Msg) -> State {
  case msg {
    ShapeChanged(s) -> State(..model, shape: s)
    ValueChanged(v) -> State(..model, value: v)
    CalculateArea ->
      State(
        ..model,
        area: option.map(model.shape, fn(s) { calculate_area(s, model.value) }),
      )
  }
}

fn handle_value_change(s: String) -> Msg {
  case string.is_empty(s) {
    True -> ValueChanged(0.0)
    False ->
      case float.parse(s) {
        Ok(x) -> ValueChanged(x)
        _ -> ValueChanged(0.0)
      }
  }
}

fn handle_shape_change(s: String) -> Msg {
  case s {
    "circle" -> ShapeChanged(Some(Circle))
    "square" -> ShapeChanged(Some(Square))
    _ -> ShapeChanged(None)
  }
}

fn view(model: State) {
  div([], [
    select([on_input(handle_shape_change)], [
      html.option([value("")], "Select shape"),
      html.option([value("circle")], "Circle"),
      html.option([value("square")], "Square"),
    ]),
    input([value(float.to_string(model.value)), on_input(handle_value_change)]),
    button([on_click(CalculateArea)], [text("Calculate area")]),
    p([], [
      text(
        "Area: " <> option.unwrap(option.map(model.area, float.to_string), ""),
      ),
    ]),
  ])
}

pub fn main() {
  let app = lustre.simple(init, update, view)
  let assert Ok(_) = lustre.start(app, "#app", Nil)

  Nil
}

Resulting bundle is quite big sitting at a whopping 65.9kb

Such a simple topic - iterating over a vector, is it even worth discussing?

Interestingly enough, there is a difference in how exactly you iterate - be it using iterators, for(:) sugar or plain old for(i=0; i<vec.size(); ++i).

Let us see what output does a compiler produce in each of these cases.

sample1 (simple for loop):

std::vector<int> data{ 5, 3, 2, 1, 4 };

for (auto i = 0; i < data.size(); ++i) {
  moo(data[i]);
}

        mov     DWORD PTR [rbp-20], 0
        jmp     .L3
.L4:
        mov     eax, DWORD PTR [rbp-20]
        movsx   rdx, eax
        lea     rax, [rbp-64]
        mov     rsi, rdx
        mov     rdi, rax
        call    std::vector<int, std::allocator<int> >::operator[](unsigned long)
        mov     eax, DWORD PTR [rax]
        mov     edi, eax
        call    moo(int)
        add     DWORD PTR [rbp-20], 1
.L3:
        mov     eax, DWORD PTR [rbp-20]
        movsx   rbx, eax
        lea     rax, [rbp-64]
        mov     rdi, rax
        call    std::vector<int, std::allocator<int> >::size() const
        cmp     rbx, rax
        setb    al
        test    al, al
        jne     .L4

but

sample2 (reversed for loop):

for (auto i = data.size() - 1; i >= 0; --i) {
  moo(data[i]);
}

        lea     rax, [rbp-64]
        mov     rdi, rax
        call    std::vector<int, std::allocator<int> >::size() const
        sub     rax, 1
        mov     QWORD PTR [rbp-24], rax
.L3:
        mov     rdx, QWORD PTR [rbp-24]
        lea     rax, [rbp-64]
        mov     rsi, rdx
        mov     rdi, rax
        call    std::vector<int, std::allocator<int> >::operator[](unsigned long)
        mov     eax, DWORD PTR [rax]
        mov     edi, eax
        call    moo(int)
        sub     QWORD PTR [rbp-24], 1
        jmp     .L3

also

sample3 (foreach):

for (auto i : data) {
  moo(i)
}

        lea     rax, [rbp-80]
        mov     QWORD PTR [rbp-24], rax
        mov     rax, QWORD PTR [rbp-24]
        mov     rdi, rax
        call    std::vector<int, std::allocator<int> >::begin()
        mov     QWORD PTR [rbp-88], rax
        mov     rax, QWORD PTR [rbp-24]
        mov     rdi, rax
        call    std::vector<int, std::allocator<int> >::end()
        mov     QWORD PTR [rbp-96], rax
        jmp     .L3
.L4:
        lea     rax, [rbp-88]
        mov     rdi, rax
        call    __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >::operator*() const
        mov     eax, DWORD PTR [rax]
        mov     DWORD PTR [rbp-28], eax
        mov     eax, DWORD PTR [rbp-28]
        mov     edi, eax
        call    moo(int)
        lea     rax, [rbp-88]
        mov     rdi, rax
        call    __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >::operator++()
.L3:
        lea     rdx, [rbp-96]
        lea     rax, [rbp-88]
        mov     rsi, rdx
        mov     rdi, rax
        call    bool __gnu_cxx::operator!=<int*, std::vector<int, std::allocator<int> > >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > const&, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > const&)
        test    al, al
        jne     .L4

but with -O1

sample1 (simple for loop):

        movabs  rax, 12884901893
        movabs  rdx, 4294967298
        mov     QWORD PTR [r12], rax
        mov     QWORD PTR [r12+8], rdx
        mov     DWORD PTR [r12+16], 4
        mov     QWORD PTR [rsp+8], rbp
        mov     rbx, r12
        jmp     .L10
.L20:
        add     rbx, 4
        cmp     rbp, rbx
        je      .L19
.L10:
        mov     edi, DWORD PTR [rbx]
        call    moo(int)
        jmp     .L20

sample2 (reversed for loop):

        movabs  rax, 12884901893
        movabs  rdx, 4294967298
        mov     QWORD PTR [rbp+0], rax
        mov     QWORD PTR [rbp+8], rdx
        mov     DWORD PTR [rbp+16], 4
        lea     rbx, [rbp+16]
        jmp     .L4
.L8:
        sub     rbx, 4
.L4:
        mov     edi, DWORD PTR [rbx]
        call    moo(int)
        jmp     .L8

sample3 (foreach):

        mov     r12, rax
        lea     rbp, [rax+20]
        mov     QWORD PTR [rsp+16], rbp
        movabs  rax, 12884901893
        movabs  rdx, 4294967298
        mov     QWORD PTR [r12], rax
        mov     QWORD PTR [r12+8], rdx
        mov     DWORD PTR [r12+16], 4
        mov     QWORD PTR [rsp+8], rbp
        mov     rbx, r12
        jmp     .L10
.L20:
        add     rbx, 4
        cmp     rbx, rbp
        je      .L19
.L10:
        mov     edi, DWORD PTR [rbx]
        call    moo(int)
        jmp     .L20

Interesting how iterating forwards adds an extra boundary check and a jump (cmd rbx, rbp and je .L19 in samples #1 and #3), whereas iterating backwards does not.

But this find actually must come with one pretty big caveat: the cache lines. The number of assembly instructions is a pretty poor measure of performance - after all, CPU instructions are ridiculously fast, compared to any form of IO - specifically memory access.

The code is also available on Github: [https://github.com/shybovycha/iterate-over-vector-in-cpp/]

The benchmarking results seem to prove the assumption: bacwards iteration seems to be faster:

Test	Min	Max	50%	90%	95%	delta
sample1 (++i)	1325447	3762733	1339309	1416805	1429724	+7%
sample2 (--i)	1290571	2596630	1308953	1334955	1342008	0%
sample3 (for(:))	1438847	3034474	1460698	1506001	1508657	+11%

Out of curiosity, I also benchmarked using the postfix operator instead of prefix: i++ (postfix) instead of ++i (prefix), which shows prefix operator is slightly faster:

Test	Min	Max	50%	90%	95%	delta
sample1 prefix (++i)	1325447	3762733	1339309	1416805	1429724	+11%
sample1 postfix (i++)	1292195	4155596	1308721	1370542	1382136	+7%
sample2 prefix (--i)	1290571	2596630	1308953	1334955	1342008	+5%
sample2 postfix (i--)	1256929	2598426	1267088	1277779	1282787	0%

Interestingly enough, there is some difference:

1. backward iteration with postfix decrement for (auto i=vec.size()-1; i>0; i--) is the fastest
2. backward iteration with prefix decrement --i is

• 5% slower than i--

3. forward iteration with postfix increment i++ is

• 3% slower than --i
• 7% slower than i--

4. forward iteration with prefix increment ++i is the slowest:

• 11% slower than i--
• 7% slower than --i
• 4% slower than i++

The above tests were ran 10000 times on a heap-allocated (std::vector) 10000 int elements.

Standard library iterators

Out of sheer curiosity, I decided to test how using an iterator would affect the results (sample4):

for (auto it = a.begin(); it != a.end(); ++it) {
  moo(*it);
}

With both prefix and suffix (postfix) variations:

for (auto it = a.begin(); it != a.end(); it++) {
  moo(*it);
}

And the reverse iterator (sample5):

for (auto it = a.end(); it != a.begin(); it--) {
  moo(*it);
}

Test	Min	Max	50%	90%	95%	delta
sample1 prefix (++i)	1325447	3762733	1339309	1416805	1429724	+11%
sample1 postfix (i++)	1292195	4155596	1308721	1370542	1382136	+7%
sample2 prefix (--i)	1290571	2596630	1308953	1334955	1342008	+4%
sample2 postfix (i--)	1256929	2598426	1267088	1277779	1282787	0%
sample3 (for(:))	1438847	3034474	1460698	1506001	1508657	+17%
sample4 prefix (++it)	1470583	2834386	1495310	1561023	1564850	+22%
sample4 postfix (it++)	1461634	2695552	1535905	1547865	1556815	+21%
sample5 prefix (--it)	1462156	2802714	1470567	1478957	1512621	+18%
sample5 postfix (it--)	1447920	2831859	1471334	1479670	1490088	+16%

The results are a bit surprising, looking at the assembly code generated by G++:

.L25:
        cmp     rbx, r13
        je      .L10
        mov     rbp, r13
        jmp     .L11
.L27:
        add     rbp, 4
        cmp     rbx, rbp
        je      .L26
.L11:
        mov     edi, DWORD PTR [rbp+0]
        call    moo(int)
        jmp     .L27
.L26:
        test    r13, r13
        je      .L18
        mov     rsi, r12
        sub     rsi, r13
.L15:
        mov     rdi, r13
        call    operator delete(void*, unsigned long)
        ; ... cleanup & exit ...
        ret

Clang 17.0.1 is a slightly different story:

.LBB0_1:
        cmp     r14, rax
        jne     .LBB0_2
        sub     r14, r15
        movabs  rax, 9223372036854775804
        cmp     r14, rax
        mov     qword ptr [rsp], r15
        je      .LBB0_11
        mov     rbp, r14
        sar     rbp, 2
        cmp     rbp, 1
        mov     rax, rbp
        adc     rax, 0
        lea     rdx, [rax + rbp]
        mov     rcx, r12
        cmp     rdx, r12
        jbe     .LBB0_14
        add     rax, rbp
        jae     .LBB0_16
.LBB0_17:
        test    r12, r12
        je      .LBB0_18
.LBB0_19:
        lea     rdi, [4*r12]
        call    operator new(unsigned long)@PLT
        mov     r15, rax
        jmp     .LBB0_21
.LBB0_14:
        mov     rcx, rdx
        add     rax, rbp
        jb      .LBB0_17
.LBB0_16:
        mov     r12, rcx
        test    r12, r12
        jne     .LBB0_19
.LBB0_18:
        xor     r15d, r15d
.LBB0_21:
        mov     dword ptr [r15 + 4*rbp], r13d
        test    r14, r14
        mov     rbx, qword ptr [rsp]
        jle     .LBB0_23
        mov     rdi, r15
        mov     rsi, rbx
        mov     rdx, r14
        call    memmove@PLT
.LBB0_23:
        test    rbx, rbx
        je      .LBB0_25
        mov     rdi, rbx
        call    operator delete(void*)@PLT
.LBB0_25:
        lea     rbp, [r15 + 4*rbp]
        lea     rax, [r15 + 4*r12]
        movabs  r12, 2305843009213693951
        jmp     .LBB0_26
.LBB0_3:
        cmp     r15, r14
        je      .LBB0_7
        lea     r14, [r15 - 4]
.LBB0_5:
        mov     edi, dword ptr [r14 + 4]
        call    moo(int)@PLT
        add     r14, 4
        cmp     r14, rbp
        jne     .LBB0_5
.LBB0_7:
        test    r15, r15
        je      .LBB0_9
        mov     rdi, r15
        call    operator delete(void*)@PLT
.LBB0_9:
        xor     eax, eax
        add     rsp, 8
        pop     rbx
        pop     r12
        pop     r13
        pop     r14
        pop     r15
        pop     rbp
        ret
.LBB0_11:
        lea     rdi, [rip + .L.str.1]
        call    std::__throw_length_error(char const*)@PLT
        jmp     .LBB0_30
        jmp     .LBB0_30
        mov     qword ptr [rsp], r15
.LBB0_30:
        mov     r14, rax
        cmp     qword ptr [rsp], 0
        je      .LBB0_32
        mov     rdi, qword ptr [rsp]
        call    operator delete(void*)@PLT
.LBB0_32:
        mov     rdi, r14
        call    _Unwind_Resume@PLT

Caching impact

One other assumption is that iterating over a vector backwards affects the memory caching in a pretty poor manner. This is a rather complex scenario to test, since there are two potential scenarios on how this could happen:

1. swap memory usage - happens when the dataset is so big it does not fit in the available RAM and OS has to switch to using disk instead of RAM; this is the worst-case scenario
2. data locality / CPU cache usage - CPUs usually try to predict memory access patterns and pre-load more data than actually required by a given operation; when the data block is accessed at random points (indices), CPU fails to pre-load the correct slices of memory

Since this blog is about iterating over a vector, it would be seem to be easier to generate absurdely large chunks of data and try to iterate over them. But in reality it would only happen with absurdely large files - my machine, for instance, sports 32GB of RAM, so it would be quite a task to generate multiple 32GB files.

Simulating random memory access will break the purpose of iterating over the elements one by one - in these cases we either use iterators to access a linked list (each element is in random part of RAM) or access elements by index. And there is no way to iterate over them by incrementing an index. Alternatively, we have to dereference indexes from another block of memory. Either way it has nothing to do comparing for loops.

Simulating accessing multiple cache lines could actually be easier - we just need to replace integers with structures of variable size and use std::list (linked list) instead of std::vector (single block of memory):

struct MyStruct {
  bool f0; // 1 byte
  float f1[100]; // sizeof(float) * 100 = 4 * 100 = 400 bytes
  double f2[53]; // sizeof(double) * 53 = 8 * 53 = 424 bytes
  char f3[64]; // sizeof(char) * 64 = 1 * 64 = 64 bytes
}; // total size = 889 bytes, likely to span across multiple cache lines

std::list<MyStruct> a;

and generate a large enough number of these objects:

#include <random>

std::random_device rd;
std::mt19937_64 gen(rd());

std::uniform_int_distribution<int> bool_dist(0, 1);
std::uniform_real_distribution<float> float_dist(0.0f, 1000.0f);
std::uniform_int_distribution<int> int_dist(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());

for (auto i = 0; i < 10000; ++i) {
  MyStruct e;

  e.f0 = static_cast<bool>(bool_dist(gen));

  for (auto t = 0; t < 100; ++t)
    e.f1[t] = float_dist(gen);

  for (auto t = 0; t < 53; ++t)
    e.f2[t] = static_cast<double>(float_dist(gen));

  for (auto t = 0; t < 64; ++t)
    e.f3[t] = static_cast<char>(int_dist(gen) % 255);

  a.push_back(e);
}

Just to prevent memory leaks, cleanup the test data at the end:

for (auto& item : a) {
  delete item.f3;
}

a.clear();

These benchmarks take significantly longer time to run and produce big numbers:

Test	Min	Max	50%	90%	95%	delta
sample1 (++i)	7882057	15385569	7948012	8004355	8031673	0%
sample2 (--i)	7915870	16297070	8971293	9109493	9151567	+13%
sample3 (for(:))	8094894	16496526	8159004	8229138	8259364	+3%

Compare this to a structure which actually fits in one cache line. Cache line size is apparently 64 B - that is sixty-four bytes - on most CPUs (AMD Zen, Intel Ice Lake). My Apple M1 laptop has twice as much, 128 B, as shown by running sysctl -a | grep 'hw.cachelinesize'.

If the structure was reorganized to fit in that limit, like so:

struct MyStruct {
  bool f0; // 1 byte
  float* f1; // sizeof(float*) = 8 bytes
  double* f2; // sizeof(double*) = 8 bytes
  char* f3; // sizeof(char*) = 8 bytes
}; // total size = 25 bytes, likely to fir in a single cache line

The timings are considerably lower for the backwards iteration:

Test	Min	Max	50%	90%	95%	delta
sample1 (++i)	7575860	20005185	7640651	7700057	7725933	0%
sample2 (--i)	7466816	18068148	7657415	8109531	8208603	+6%
sample3 (for(:))	7832724	14264212	7882930	7932295	7960718	+3%

This highlights how predictive cache loading and data element size that fits into a single CPU cache line actually impacts RAM reads - by a significant margin.

Conclusion

In simplest case (vector of numbers), the worst case scenario is within 11% difference, with backwards iteration being the fastest, followed by forward iteration and foreach being the slowest of the bunch. Prefix decrement in the backwards iteration being the fastest. Bear in mind: these numbers are in nanoseconds, meaning the worst case scenario is 10000 (ten thousand) elements of variable size being iterated in 1.5 ms and the fastest being 1.3 ms - that is milliseconds. For comparison, rendering a frame at 120 FPS rate would take about 8.3 ms. And if you were to process some requests (in a client-server system), you would be able to handle 699 requests per second while iterating over this list. So realistically, the way you iterate a vector of integers, any of these techniques would only really matter if you are working on a really high performance system.

That being said, this is all true while the vector elements fit in one CPU cache line or cache block, that is L1 and L2 caches.

So if the data element does not fit in a block of 64 B (or 128 B on some CPUs), the performance impact of backwards iteration is going to be more significant. In this case we are talking about 8 ms vs 9.1 ms. In terms of FPS, the difference would be 125 FPS vs 109 FPS. Or about 15 requests per second more.

Contents

• Gantt chart with D3
• Gantt chart with D3. Part 2
• Gantt chart with Canvas
• Gantt chart with CSS Grids (you are here)

Seems like every two years or so I hop on my Gantt chart implementation and rework it completely.

Last few attempts (rev. 1, rev. 2, rev. 3) were alright, but I was never quite satisfied with the implementation - be it SVG, which has a toll on a browser and has quite limited customization functionality or Canvas API, with same limited customization but being fast.

With the recent introduction of grid layouts in CSS, now supported in all browsers, now seems like a perfect time to revisit the old implementations once again:

CodeSandbox / live demo

This revision now has a proper horizontal scrolling on the panel with bars - meaning the labels on the left panel stay in place whilst the left panel is scrollable. Moreover, the chart is now relies on pure HTML and CSS (being rendered with React though), making it is possible to use rich markup inside the bars and labels.

Implementation steps

The data for the tests is going to look like this:

export const data = [
  {
    id: 1,
    name: "epic 1"
  },
  {
    id: 2,
    name: "epic 2"
  },
  {
    id: 3,
    name: "epic 3"
  },
  {
    id: 4,
    name: "story 1",
    parent: 1
  },
  {
    id: 5,
    name: "story 2",
    parent: 1
  },
  {
    id: 6,
    name: "story 3",
    parent: 1
  },
  {
    id: 7,
    name: "story 4",
    parent: 2
  },
  {
    id: 8,
    name: "story 5",
    parent: 2
  },
  {
    id: 9,
    name: "lorem ipsum dolor atata",
    parent: 5
  },
  {
    id: 10,
    name: "task 2",
    parent: 5
  }
];

The main component, <Gantt>, initially was implementated as follows:

import React, { useMemo } from "react";

import style from "./gantt.module.css";

const LeftPaneRow = ({ id, name }) => {
  return <div className={style.row}>{name}</div>;
};

const LeftPane = ({ items }) => {
  return (
    <div className={style.left_pane}>
      <div className={style.left_pane_header}>/</div>

      <div className={style.left_pane_rows}>
        {items.map((item) => (
          <LeftPaneRow key={item.id} {...item} />
        ))}
      </div>
    </div>
  );
};

const RightPaneRow = ({ id, name }) => {
  return (
    <div className={style.row}>
      <div className={style.entry} style={{ left: 0 }}>
        {id}
      </div>
    </div>
  );
};

const RightPane = ({ items }) => {
  return (
    <div className={style.right_pane}>
      <div className={style.right_pane_header}>...scale...</div>
      <div className={style.right_pane_rows}>
        {items.map((item) => (
          <RightPaneRow key={item.id} {...item} />
        ))}
      </div>
    </div>
  );
};

export const flattenTree = (items) => {
  const queue = [];

  items.filter(({ parent }) => !parent).forEach((item) => queue.push(item));

  const result = [];
  const visited = new Set();

  while (queue.length > 0) {
    const item = queue.shift();

    if (visited.has(item.id)) {
      continue;
    }

    result.push(item);
    visited.add(item.id);

    items
      .filter((child) => child.parent === item.id)
      .forEach((child) => queue.unshift(child));
  }

  return result;
};

export const Gantt = ({ items }) => {
  const itemList = useMemo(() => flattenTree(items), [items]);

  return (
    <div className={style.gantt}>
      <LeftPane items={itemList} />
      <RightPane items={itemList} />
    </div>
  );
};

The core of the proper representation of this diagram is the CSS:

.gantt {
  display: grid;
  grid-template: 1fr / auto 1fr;
  grid-template-areas: "left right";
  width: 100%;
}

.gantt .left_pane {
  display: grid;
  grid-area: left;
  border-right: 1px solid #bbb;
  grid-template: auto 1fr / 1fr;
  grid-template-areas: "corner" "rows";
}

.gantt .left_pane .left_pane_rows {
  display: grid;
  grid-area: rows;
}

.gantt .left_pane .left_pane_header {
  display: grid;
  grid-area: corner;
}

.gantt .right_pane {
  display: grid;
  grid-template: auto 1fr / 1fr;
  grid-template-areas: "scale" "rows";
  grid-area: right;
  overflow: auto;
}

.gantt .right_pane .right_pane_rows {
  width: 10000px; /*temp*/
  display: grid;
  grid-area: rows;
}

.gantt .right_pane .right_pane_header {
  display: flex;
  grid-area: scale;
}

.gantt .row {
  height: 40px;
  align-items: center;
  display: flex;
}

.gantt .right_pane .row {
  position: relative;
}

.gantt .right_pane .row .entry {
  position: absolute;
  background: #eeeeee;
  padding: 0.1rem 0.5rem;
  border-radius: 0.4rem;
}

Good, we now have two panels with items aligned in rows and the right panel being scrollable if it gets really long. Next thing, position: absolute is absolutely disgusting - we use grid layout already! Instead, split each row into the same number of columns using grid and position the elements in there:

const RightPaneRow = ({ id, name, columns, start, end }) => {
  const gridTemplate = `auto / repeat(${columns}, 1fr)`;
  const gridArea = `1 / ${start} / 1 / ${end}`;

  return (
    <div
      className={style.row}
      style={{
        gridTemplate,
      }}
    >
      <div
        className={style.entry}
        style={{
          gridArea,
        }}
      >
        {id}
      </div>
    </div>
  );
};

and clean up the CSS a bit (like removing the position: absolute and reducing the width from 10000px down to 1000px):

.gantt .right_pane .right_pane_rows {
  width: 1000px; /*temp*/
  display: grid;
  grid-area: rows;
}

.gantt .row {
  height: 40px;
  align-items: center;
  display: grid;
}

.gantt .right_pane .row {
  position: relative;
}

.gantt .right_pane .row .entry {
  background: #eeeeee;
  padding: 0.1rem 0.5rem;
  border-radius: 0.4rem;
}

Now, let's position the elements in each row using the column index:

const RightPanelRowEntry = ({ id, start, end, children }) => {
  const gridArea = `1 / ${start} / 1 / ${end}`;

  return (
    <div
      className={style.entry}
      style={{
        gridArea,
      }}
    >
      {children}
    </div>
  );
};

const RightPaneRow = ({ id, name, columns, start, end }) => {
  const gridTemplate = `auto / repeat(${columns}, 1fr)`;
  const gridArea = `1 / ${start} / 1 / ${end}`;

  return (
    <div
      className={style.row}
      style={{
        gridTemplate,
      }}
    >
      <div
        className={style.entry}
        style={{
          gridArea,
        }}
      >
        {id}
      </div>
    </div>
  );
};

const RightPaneHeaderRow = ({ columns, children }) => {
  const gridTemplate = `auto / repeat(${columns}, 1fr)`;

  return (
    <div
      className={style.right_pane_header_row}
      style={{
        gridTemplate,
      }}
    >
      {children}
    </div>
  );
};

const RightPaneHeader = ({ children }) => {
  return <div className={style.right_pane_header}>{children}</div>;
};

const RightPane = ({ items, columns }) => {
  const columnHeaders = [...Array(columns)].map((_, idx) => (
    <RightPaneHeader>{idx + 1}</RightPaneHeader>
  ));

  const rows = items.map((item) => (
    <RightPaneRow key={item.id} columns={columns}>
      <RightPanelRowEntry {...item}>{item.id}</RightPanelRowEntry>
    </RightPaneRow>
  ));

  return (
    <div className={style.right_pane}>
      <RightPaneHeaderRow columns={columns}>{columnHeaders}</RightPaneHeaderRow>
      <div className={style.right_pane_rows}>{rows}</div>
    </div>
  );
};

And add corresponding new CSS styles:

.gantt .right_pane .right_pane_header_row {
  display: grid;
  grid-area: scale;
}

.gantt .right_pane .right_pane_header_row .right_pane_header {
  display: grid;
  align-items: center;
  text-align: center;
}

This requires start and end defined for each entry:

export const data = [
  {
    id: 1,
    name: "epic 1",
    start: 1,
    end: 12,
  },
  {
    id: 2,
    name: "epic 2",
    start: 2,
    end: 4,
  },
  {
    id: 3,
    name: "epic 3",
    start: 9,
    end: 11,
  },
  {
    id: 4,
    name: "story 1",
    parent: 1,
    start: 6,
    end: 7,
  },
  // ...
};

And, to make it not repeat a dozen of inline CSS styles, we can utilize CSS variables:

const RightPaneRow = ({ id, columns, children }) => {
  return (
    <div className={style.row}>
      {children}
    </div>
  );
};

const RightPanelRowEntry = ({ id, start, end, children }) => {
  return (
    <div
      className={style.entry}
      style={{
        "--col-start": start,
        "--col-end": end,
      }}
    >
      {children}
    </div>
  );
};

const RightPane = ({ items, columns }) => {
  const columnHeaders = [...Array(columns)].map((_, idx) => (
    <RightPaneHeader>{idx + 1}</RightPaneHeader>
  ));

  const rows = items.map((item) => (
    <RightPaneRow key={item.id} columns={columns}>
      <RightPanelRowEntry {...item}>{item.id}</RightPanelRowEntry>
    </RightPaneRow>
  ));

  return (
    <div className={style.right_pane} style={{ "--columns": columns }}>
      <RightPaneHeaderRow>{columnHeaders}</RightPaneHeaderRow>
      <div className={style.right_pane_rows}>{rows}</div>
    </div>
  );
};

We can also re-use the same row for header:

const RightPaneHeaderRow = ({ children }) => {
  return <div className={style.right_pane_header_row}>{children}</div>;
};

And corresponding CSS:

.gantt .right_pane .right_pane_header_row {
  display: grid;
  grid-area: scale;

  grid-template: auto / repeat(var(--columns, 1), 1fr);
}

.gantt .right_pane .row {
  position: relative;

  grid-template: auto / repeat(var(--columns, 1), 1fr);
}

.gantt .right_pane .row .entry {
  background: #eeeeee;
  padding: 0.1rem 0.5rem;
  border-radius: 0.5rem;
  align-items: center;
  text-align: center;

  grid-area: 1 / var(--col-start, 1) / 1 / var(--col-end, 1);
}

I like to also change the fonts, since the default sans-serif just looks terrible:

@import url("https://fonts.googleapis.com/css2?family=Assistant:wght@200..800&display=swap");

:root {
  font-family: "Assistant", sans-serif;
  font-optical-sizing: auto;
  font-weight: 300;
  font-style: normal;
  font-variation-settings: "wdth" 100;
}

And maybe add some grid lines for the rows:

.gantt .row:first-child {
  border-top: 1px solid var(--border-color, #eee);
}

.gantt .row {
  padding: 0 0.75rem;
  border-bottom: 1px solid var(--border-color, #eee);
}

Now let's add some padding to separate parent and child items of a chart:

const LeftPaneRow = ({ level, id, name }) => {
  const nestingPadding = `${level}rem`;

  return (
    <div className={style.row} style={{ "--label-padding": nestingPadding }}>
      {name}
    </div>
  );
};

.gantt .left_pane .row {
  padding-left: var(--label-padding, 0);
}

and fill out the level property when flattening the item tree:

export const flattenTree = (items) => {
  const queue = [];

  items
    .filter(({ parent }) => !parent)
    .forEach((item) => queue.push({ level: 0, item }));

  const result = [];
  const visited = new Set();

  while (queue.length > 0) {
    const { level, item } = queue.shift();

    if (visited.has(item.id)) {
      continue;
    }

    result.push({ ...item, level });
    visited.add(item.id);

    items
      .filter((child) => child.parent === item.id)
      .forEach((child) => queue.unshift({ item: child, level: level + 1 }));
  }

  return result;
};

And automate the number of columns calculation:

export const Gantt = ({ items }) => {
  const itemList = flattenTree(items);

  const startsAndEnds = items.flatMap(({ start, end }) => [start, end]);
  const columns = Math.max(...startsAndEnds) - Math.min(...startsAndEnds);

  return (
    <div className={style.gantt}>
      <LeftPane items={itemList} />
      <RightPane items={itemList} columns={columns} />
    </div>
  );
};

In order to make chart panel scrollable, one can set a width CSS property for the .right_pane_rows and .right_pane_header_row:

.gantt .right_pane .right_pane_rows {
  width: 2000px;
}

.gantt .right_pane .right_pane_header_row {
  width: 2000px;
}

The last bit for a this prototype would be to have a scale for the columns.

Assume a chart item has an abstract start and end fields - these could be dates or some domain-specific numbers (like a week in a quarter or a sprint, etc.). Those will then need to be mapped onto column index. Then the chart width (in columns) would be the difference between the smallest start value and the biggest end value:

export const Gantt = ({ items, scale }) => {
  const itemList = flattenTree(items).map((item) => ({
    ...item,
    ...scale(item), // assuming `scale` function returns an object { start: number; end: number }
  }));

  const minStartItem = minBy(itemList, (item) => item.start);
  const maxEndItem = maxBy(itemList, (item) => item.end);

  const columns = maxEndItem.end - minStartItem.start;

  return (
    <div className={style.gantt}>
      <LeftPane items={itemList} />
      <RightPane items={itemList} columns={columns} />
    </div>
  );
};

The minBy and maxBy helper functions could be either taken from lodash or manually defined like this:

const minBy = (items, selector) => {
  if (items.length === 0) {
    return undefined;
  }

  let minIndex = 0;

  items.forEach((item, index) => {
    if (selector(item) < selector(items[minIndex])) {
      minIndex = index;
    }
  });

  return items[minIndex];
}

For better navigation around this code we can add some types:

interface GanttChartItem {
  id: string;
  name: string;
}

interface GanttChartProps {
  items: GanttChartItem[];
  scale: (item: GanttChartItem) => { start: number; end: number };
}

function minBy<T>(items: T[], selector: (item: T) => number): T | undefined {
  // ...
}

export const Gantt = ({ items, scale }: GanttChartProps) => {
  // ...
};

export default function App() {
  const scale = ({ start, end }) => {
    return { start: start * 2, end: end * 2 };
  };

  return <Gantt items={data} scale={scale} />;
}

We can extend this even further by adding an API to provide labels for columns:

interface GanttChartProps {
  // ...
  scaleLabel: (column: number) => React.Element;
}

export const Gantt = ({ items, scale, scaleLabel }: GanttChartProps) => {
  // ...

  return (
    <div className={style.gantt}>
      <LeftPane items={itemList} />
      <RightPane items={itemList} columns={columns} scaleLabel={scaleLabel} />
    </div>
  );
};


const RightPane = ({ items, columns, scaleLabel }) => {
  const columnHeaders = [...Array(columns)].map((_, idx) => (
    <RightPaneHeader>{scaleLabel(idx)}</RightPaneHeader>
  ));

  // ...
};

export default function App() {
  const scale = ({ start, end }) => ({ start, end });
  };

  const scaleLabel = (col) => `${col}`;

  return <Gantt items={data} scale={scale} scaleLabel={scaleLabel} />;
}

This new API can then be utilized to show month names, for instance:

export default function App() {
  const scale = ({ start, end }) => {
    return { start, end };
  };

  const months = [
    "Jan",
    "Feb",
    "Mar",
    "Apr",
    "May",
    "Jun",
    "Jul",
    "Aug",
    "Sep",
    "Oct",
    "Nov",
    "Dec",
  ];

  const scaleLabel = (col) => months[col % 12];

  return <Gantt items={data} scale={scale} scaleLabel={scaleLabel} />;
}

Moreover, it is now possible to inline HTML and CSS in the name of each chart item:

export const LeftPaneRow = ({ level, name }) => {
  const nestingPadding = `${level}rem`;

  return (
    <div className={style.row} style={{ "--label-padding": nestingPadding }}>
      <span dangerouslySetInnerHTML={{__html: name}}></span>
    </div>
  );
};

And then in data.json (note that FontAwesome requires its CSS on a page in order to work):

[
  {
    id: 7,
    name: '<i style="font-family: \'FontAwesome\';" class="fa fa-car"></i>&nbsp;story with FontAwesome',
    parent: 2,
    start: 4,
    end: 6,
  },
  {
    id: 9,
    name: 'inline <em><b style="color: #5ebebe">CSS</b> color</em> <u style="border: 1px dashed #bebefe; padding: 2px; border-radius: 2px">works</u>',
    parent: 5,
    start: 5,
    end: 6,
  },
]

The API can be further improved by providing the render function for the bars' labels:

export const RightPane = ({ items, columns, scaleLabel, barLabel }) => {
  const rows = items.map((item) => (
    <RightPaneRow key={item.id} columns={columns}>
      <RightPaneRowEntry {...item}>{barLabel ? barLabel(item) : <>{item.id}</>}</RightPaneRowEntry>
    </RightPaneRow>
  ));

  // ...
};

export interface GanttChartProps {
  items: GanttChartItem[];
  scale: (item: GanttChartItem) => { start: number; end: number };
  scaleLabel: (column: number) => React.Element;
  barLabel: (item: GanttChartItem) => React.Element;
}

export const Chart = ({
  items,
  barLabel,
  scale,
  scaleLabel,
}: GanttChartProps) => {
  // ...
  return (
    <div className={style.gantt}>
      <LeftPane items={itemList} />
      <RightPane
        items={itemList}
        columns={columns}
        scaleLabel={scaleLabel}
        barLabel={barLabel}
      />
    </div>
  );
};

and then in App component:

import pluralize from "pluralize";

export default function App() {
  const barLabel = ({ start, end }) => (
    <>
      {end - start} {pluralize("month", end - start)}
    </>
  );

  // ...

  return (
    <Chart
      items={data}
      scale={scale}
      scaleLabel={scaleLabel}
      barLabel={barLabel}
    />
  );
};