Haffman

╔════════════════════════════════════════════════════════════════╗
║ 01001000 01100001 01100110 01100110 01101101 01100001 01101110 ║
║    H        a        f        f        m        a        n     ║
╠════════════════════════════════════════════════════════════════╣
║                                                                ║
║                              (*)                               ║
║                            0 / \ 1                             ║
║                             /   \                              ║
║                           (*)   (*)                            ║
║                         0 / \ 1 0 / \ 1                        ║
║                          /   \   /   \                         ║
║                        [a] [f] [m] [n]                         ║
║                                                                ║
╟────────────────────────────────────────────────────────────────╢
║                                                                ║
║ A Huffman coder in C. Spring 2019.                             ║
║                                                                ║
║ This is the first more or less large algorithmic project I     ║
║ wrote, and I wrote it in a low-level language, at the very     ║
║ beginning of learning to program - years before there was any  ║
║ AI to ask.                                                     ║
║                                                                ║
║ It has no practical use. It is on my account because it is     ║
║ close to my heart.                                             ║
║                                                                ║
║ When I look at this code now, I see how simple it is - and I   ║
║ admire how low to the ground it is. Bits, bytes, pointers, a   ║
║ tree built by hand. This was the start of becoming a           ║
║ programmer, and I am glad I walked that stretch of the road at ║
║ a time when artificial intelligence simply did not exist.      ║
║                                                                ║
║ Back then I did not understand how an operating system really  ║
║ allocates memory, the fine points of how Unix works, or what   ║
║ hides underneath the basic commands. But it was the time when  ║
║ my belief in myself as a programmer was at its highest. That   ║
║ is what makes this repository valuable to me.                  ║
║                                                                ║
║ Even the name of the project is misspelled - it should be      ║
║ Huffman. That is part of its value too. Back then there was    ║
║ not much Google to lean on either, let alone anything smarter. ║
║ What there was plenty of was the urge to write code, and it    ║
║ was enormous.                                                  ║
║                                                                ║
║ So the code is kept exactly as it was written, and the name    ║
║ stays as it is.                                                ║
║                                                                ║
╠════════════════════════════════════════════════════════════════╣
║ 01001000 01100001 01100110 01100110 01101101 01100001 01101110 ║
╚════════════════════════════════════════════════════════════════╝

What it does

It compresses and restores a file with Huffman coding: symbols that occur often get short bit codes, rare ones get long codes.

For the input abracadabra it builds this tree — leaves are symbols with their frequencies, and the path from the root is the code:

graph TD
    R((11)) -->|0| A["a · 5"]
    R -->|1| N6((6))
    N6 -->|0| RR["r · 2"]
    N6 -->|1| N4((4))
    N4 -->|0| N2((2))
    N4 -->|1| B["b · 2"]
    N2 -->|0| C["c · 1"]
    N2 -->|1| D["d · 1"]

Loading

Symbol	Count	Code
a	5	0
r	2	10
b	2	111
c	1	1100
d	1	1101

Eleven characters fit into 23 bits instead of 88. On its own source file, main.c, the program gets 11 033 bytes down to 7 383 — about two thirds — and restores it byte for byte.

How it works

1. Count. Read the input and count how often each byte occurs.
2. Build the tree. Repeatedly take the two lightest nodes and join them under a new parent. The queue is an array kept in order with a bubble sort.
3. Assign codes. Walk the tree; going left appends 0, going right 1.
4. Write the tree. Store it in the output in pre-order: a 0 bit for an inner node, a 1 bit followed by the 8 bits of the symbol for a leaf.
5. Write the data. Replace every input byte with its code, packing bits into bytes as they fill up.

Decompression reads the tree back and then follows it bit by bit, emitting a symbol each time it lands on a leaf. The number of symbols to restore is kept in a separate file, so the padding bits at the end are not mistaken for data.

The program also writes the tree in Graphviz format (graph_c.gv when compressing, graph_d.gv when decompressing), which was how I checked that both sides built the same tree.

Build and run

cc -o haffman main.c secondary_functions.c

The program takes no arguments. It reads in.txt from the current directory and writes out.txt. The first line of in.txt is the mode — c to compress or d to decompress — followed by a Windows line break (\r\n), and the data starts right after it.

# compress
printf 'c\r\nabracadabra' > in.txt
./haffman                      # writes out.txt and cheat.txt
mv out.txt packed.bin

# decompress
(printf 'd\r\n'; cat packed.bin) > in.txt
./haffman                      # needs cheat.txt from the compress run
cat out.txt                    # abracadabra

cheat.txt holds the length of the original data as a 4-byte number.

Files

File	Contents
main.c	Counting, tree building, encoding, decoding, bit output
secondary_functions.c	Graphviz dump of the tree
struct_and_const.h	The tree node, the bit buffer and the constants