Building a Lossless File Compressor from Scratch in C: My Journey with Shannon-Fano, Bitstreams, and Low-Level Performance

Like most developers, I’ve used compression tools like gzip, zip, and tar for years without ever really understanding how they work under the hood. You pass a file in, run a command, and out comes a file half the size. It feels like magic.

Recently, I decided to pull back the curtain and learn low-level systems programming by building a lossless compression tool from scratch in C

The project is called kmprs (available on GitHub).

In this post, I want to share the full journey: how the Shannon-Fano algorithm works, the practical challenges of reading and writing arbitrary bits to disk, how an innocent-looking function call created a 100-million-operation bottleneck, and why building this from zero taught me more about computer architecture than any textbook.

---

The Core Idea: What is Entropy Encoding?

In standard ASCII or raw binary data, every single character occupies a fixed size of 8 bits (1 byte).

Whether a byte is the letter 'e' (which appears thousands of times in English prose) or the character '~' (which might appear once), they both take up 8 bits of disk space:

'e' -> 01100101 (8 bits)
'~' -> 01111110 (8 bits)

Entropy encoding flips this premise on its head:

• Assign short bit codes (e.g., 2 to 4 bits) to frequently occurring symbols.
• Assign longer bit codes (e.g., 9 to 14 bits) to rare symbols.

Because common characters appear millions of times, the average number of bits per character drops well below 8, compressing the overall file size.

---

How the Shannon-Fano Algorithm Works

In 1948, Claude Shannon and Robert Fano introduced one of the earliest statistical prefix-coding algorithms.

The algorithm builds a binary prefix tree using a top-down recursive splitting approach:

                         [ All Symbols (Sum = 100) ]
                                  /       \
                       Split at ~50       Split at ~50
                               /             \
                   '0' [ Group A (52) ]   '1' [ Group B (48) ]
                         /        \             /        \
                    '0' [e (30)] '1' [t (22)] '0' [a (28)] '1' [z (20)]

The Step-by-Step Algorithm

1. Count Frequencies: Perform a first pass over the input file to build a histogram of all 256 possible byte values ($0$ to $255$).
2. Filter & Sort: Collect all symbols with non-zero counts and sort them in descending order of frequency.
3. Recursive Partitioning:
   • Find a split index $k$ such that the sum of frequencies on the left is as close as possible to the sum on the right: $$\left| \sum_{i=\text{start}}^{k} \text{freq}[i] - \sum_{i=k+1}^{\text{end}} \text{freq}[i] \right| \text{ is minimized}$$
   • Assign bit 0 to the left group and bit 1 to the right group.
   • Recursively split both halves until every group contains a single symbol.
4. Generate Prefix Codes: Each symbol receives a unique binary code corresponding to its path from the root.

The Prefix-Free Property

A crucial rule in data compression is that no code can be a prefix of another code.

For example, if 'e' is encoded as 01, no other character can start with 01 (like 011). This guarantees that when the decompressor reads incoming bits sequentially, it can instantaneously and unambiguously decode each character without needing delimiter markers.

---

The Reality Check: Building Bit-Level I/O

The math of Shannon-Fano is simple on paper. But as soon as you sit down to implement it in C, you run into your first major hardware hurdle:

Computers do not read or write individual bits.

The OS filesystem and CPU architecture work in chunks of bytes (8 bits), words (64 bits), and pages (4 KiB). If symbol 'e' has the 3-bit codeword 101 and symbol 't' has the 5-bit codeword 01100, how do you write 8 bits across arbitrary boundaries?

To solve this, I had to build custom BitWriter and BitReader abstractions.

The BitWriter Architecture

The BitWriter uses a 64-bit integer as a bit accumulator (reservoir). It packs variable-length bits into the accumulator and siphons off completed 8-bit bytes:

typedef struct BitWriter {
    FILE *out;
    uint8_t buffer[4096];     // 4 KiB block buffer
    size_t buffer_pos;         // Cursor in buffer
    uint64_t accumulator;      // 64-bit temporary bit reservoir
    uint8_t bits_in_buffer;    // Unwritten bits count (0 to 64)
} BitWriter;

When writing a codeword of length $L$:

1. Left-shift the accumulator by $L$ bits.
2. Bitwise-OR the new codeword into the lower $L$ bits.
3. Increment bits_in_buffer by $L$.
4. Whenever bits_in_buffer >= 8, extract the top 8 bits, store them in the output buffer, and decrement bits_in_buffer by 8.

static inline void bit_writer_write(BitWriter *bw, uint32_t code, uint8_t length) {
    uint64_t mask = (length == 32U) ? 0xFFFFFFFFULL : ((1ULL << length) - 1ULL);
    bw->accumulator = (bw->accumulator << length) | ((uint64_t)code & mask);
    bw->bits_in_buffer += length;

    while (bw->bits_in_buffer >= 8U) {
        bw->bits_in_buffer -= 8U;
        uint8_t byte = (uint8_t)((bw->accumulator >> bw->bits_in_buffer) & 0xFFU);
        bw->buffer[bw->buffer_pos++] = byte;
        if (bw->buffer_pos == 4096) {
            fwrite(bw->buffer, 1, 4096, bw->out);
            bw->buffer_pos = 0;
        }
    }
}

---

Designing the Binary Container Format (.shn)

A raw stream of compressed bits is useless by itself. When decompressing, the program needs to know:

1. Is this actually a valid compressed file?
2. What codebook was used to encode the file?
3. How many uncompressed bytes should we restore? (Since the final byte in a bitstream often contains trailing zero padding).

I designed a binary container format with a fixed metadata header:

+-------------------------------------------------------------+
| Magic Bytes: "\x7fSHN\x01" (4 bytes)                        |
+-------------------------------------------------------------+
| Original File Size: uint64_t (8 bytes, little-endian)       |
+-------------------------------------------------------------+
| Symbol Count: uint16_t (2 bytes)                            |
+-------------------------------------------------------------+
| Serialized Codebook Entries: [Symbol (1B) | Len (1B) | ...] |
+-------------------------------------------------------------+
| Compressed Bitstream Payload ...                            |
+-------------------------------------------------------------+

During decompression, kmprs parses the header, reconstructs the Shannon-Fano binary decode tree, and reads bits from the bitstream to traverse the tree from root to leaf, emitting exact original characters until the original file byte count is reached.

---

The 100-Million-Call Bottleneck & Optimization

Once the compressor worked end-to-end and passed verification roundtrips, I benchmarked it on a 100 MB test dataset (dummy.data).

The first implementation felt surprisingly sluggish (~1.33 seconds).

Finding the Bottleneck

In my initial prototype of BitWriter, whenever 8 bits accumulated, I emitted the byte immediately using fputc():

// Naive unbuffered approach
while (bw->bits_in_buffer >= 8) {
    bw->bits_in_buffer -= 8;
    uint8_t byte = (uint8_t)(bw->accumulator >> bw->bits_in_buffer);
    fputc(byte, bw->out);  // <-- PROBLEM!
}

On a 100 MB file, this meant:

• ~100,000,000 function calls into the C standard library.
• 100,000,000 thread lock/unlock operations (since standard libc file streams like fputc acquire internal reentrant locks per call).
• Cache thrashing and function prologue/epilogue overhead inside the innermost encoding loop.

The Two-Tier Solution

I re-architected the I/O pipeline:

1. Inlined Bit Packing: Moved bit_writer_write() to bit_io.h as a static inline function so the compiler could optimize the bit shifts directly inside the encoding loop.
2. 4 KiB Block Buffer: Accumulated completed bytes into an internal uint8_t buffer[4096] array.
3. Bulk fwrite(): Only flushed to the OS stream once every 4,096 bytes.

The Benchmark Results

Testing with hyperfine on the 100 MB test payload:

Version	Mean Execution Time	User CPU Time	System Time	Speedup
Buffered BitWriter (4 KiB + inline)	710.5 ms ± 18.0 ms	625.7 ms	79.6 ms	~1.87x faster (2.0x CPU reduction)
Unbuffered BitWriter (per-byte fputc)	1.327 s ± 0.002 s	1.249 s	74.0 ms	Baseline

Cutting execution time in half simply by buffering bytes and avoiding function call overhead in hot loops was a huge practical lesson.

---

Real-World Comparison: kmprs vs gzip

When benchmarked against standard gzip -kf dummy.data:

Command	Mean Execution Time	User Time	Compressed Size	Space Savings
kmprs dummy.data	690.1 ms ± 4.6 ms	620.1 ms	53.25 MB	49.2%
gzip -kf dummy.data	2.684 s ± 0.007 s	2.645 s	59.72 MB	43.0%

Why is kmprs faster than gzip?

kmprs performs a single frequency pass, builds a small 256-element tree, and directly streams bits through an inlined bit-reservoir. It does very little memory allocation and has minimal computational complexity.

But why is gzip the better general-purpose compressor?

This brings us to an important distinction in data compression theory:

1. Order-0 Entropy vs. Dictionary Compression:

   • kmprs only looks at individual byte frequencies (order-0 entropy). It cannot detect repeated phrases, patterns, or words.
   • gzip uses DEFLATE, which combines LZ77 sliding-window dictionary matching with Huffman coding. When compressing source code, JSON, logs, or prose, LZ77 replaces entire repeated strings (like "function" or <div class="...">) with tiny (distance, length) tokens, achieving vastly superior compression ratios.

2. Shannon-Fano is Suboptimal Compared to Huffman:

   • Shannon-Fano is a top-down greedy heuristic that divides probabilities in half. It does not guarantee the minimum possible expected code length.
   • David Huffman later proved that a bottom-up priority-queue approach generates the mathematically optimal prefix codebook.

---

What Writing C in 2026 Taught Me

Building a low-level tool in C is unforgiving, but modern tooling makes it a fantastic learning experience:

• AddressSanitizer & UBSan (-fsanitize=address,undefined): Caught subtle bugs immediately, including a 32-bit shift overflow when masking 32-bit codewords (1ULL << 32 vs (length == 32) ? 0xFFFFFFFF : ...).
• Clang-Tidy: Enforced clean typing, explicit conversions, and consistent header hygiene across all compilation units.
• Automated Testing: Writing unit tests for truncated headers, corrupt magic bytes, and single-byte edge cases caught bugs before they hit production.

---

Conclusion & What's Next

Taking a compression algorithm from theoretical pseudocode to a working, optimized CLI binary gave me a deep appreciation for systems programming. Concepts like bitwise operations, cache locality, branch predictability, and I/O buffer management went from abstract textbook ideas to tangible, measurable engineering realities.

Roadmap for kmprs:

• [ ] Table-Driven Multi-Bit Peek Decoder: Accelerate decompression using an 8-bit lookup table ($O(1)$ symbol resolution).
• [ ] Canonical Huffman Coding: Replace Shannon-Fano with true Huffman coding and pack headers using canonical code lengths.
• [ ] CRC32 Checksum Verification: Add stream integrity verification.

If you'd like to check out the code, run the benchmarks, or contribute:

⭐ GitHub Repository: github.com/shadowmkj/kmprs

Have you ever built a compression tool or worked with bit-level I/O? What were your biggest takeaways? I’d love to hear your thoughts in the comments!