summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--README1
-rw-r--r--huffman/build.sh3
-rw-r--r--huffman/huffman.c306
3 files changed, 310 insertions, 0 deletions
diff --git a/README b/README
index 4948924..acec7e3 100644
--- a/README
+++ b/README
@@ -9,6 +9,7 @@ Mirror https://github.com/kvog-git/demos
aarch64 AArch64 assembly experiments
ffmpeg-shadertoy Basic offline Shadertoy renderer
gl-asylum Procedurally generated 3D OpenGL scene
+huffman Huffman encoding demo
qoidec Quite OK Image Format decoder
riffprobe Basic RIFF/WAVE file traversal
rust-asm Rust -> assembly interop demo
diff --git a/huffman/build.sh b/huffman/build.sh
new file mode 100644
index 0000000..2125bc2
--- /dev/null
+++ b/huffman/build.sh
@@ -0,0 +1,3 @@
+#!/bin/bash
+mkdir -p bin
+cc -o bin/huffman -Wall -Wextra -Wpedantic -O0 -g ./huffman.c
diff --git a/huffman/huffman.c b/huffman/huffman.c
new file mode 100644
index 0000000..b20c164
--- /dev/null
+++ b/huffman/huffman.c
@@ -0,0 +1,306 @@
+// ================================================================================================
+// Huffman encoding demo
+//
+// ref: https://en.wikipedia.org/wiki/Huffman_coding#Basic_technique
+//
+// Changelog:
+// 9/29/2026: Initial release
+//
+// License:
+// SPDX-License-Identifier: 0BSD
+// Copyright (c) 2026 Hunter Kvalevog
+//
+// Permission to use, copy, modify, and/or distribute this software for any
+// purpose with or without fee is hereby granted.
+//
+// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+// WITH REGARD TO THIS SOFTWARE.
+// ================================================================================================
+
+#include <assert.h>
+#include <stdarg.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define DEBUG
+
+#ifdef __GNUC__
+# define ATTR_NORETURN __attribute__((noreturn))
+# define ATTR_PRINTF(A1, A2) __attribute__((format(printf, A1, A2)))
+#else
+# define ATTR_NORETURN
+# define ATTR_PRINTF(A1, A2)
+#endif
+
+ATTR_NORETURN
+ATTR_PRINTF(1, 2)
+static void die(const char *fmt, ...)
+{
+ va_list va; va_start(va, fmt);
+ vprintf(fmt, va);
+ va_end(va);
+
+ exit(1);
+}
+
+// bit writer
+typedef struct BitW BitW;
+struct BitW
+{
+ uint8_t *bbuf;
+ size_t blen;
+ size_t cbyte;
+ size_t cbit;
+};
+
+static void write_bit(BitW *bw, uint8_t val)
+{
+ assert(!(val & ~1));
+ assert(bw->cbyte < bw->blen);
+ bw->bbuf[bw->cbyte] |= (val << (7 - bw->cbit));
+ bw->cbit += 1;
+ if (bw->cbit >= 8)
+ {
+ bw->cbyte += 1;
+ bw->cbit = 0;
+ }
+}
+
+static void write_bits(BitW *bw, uint64_t val, uint8_t len)
+{
+ for (uint8_t i = 0; i < len; ++i)
+ write_bit(bw, (val >> (len - i - 1)) & 1);
+}
+
+#if 0
+// bit reader
+typedef struct BitR BitR;
+struct BitR
+{
+ const uint8_t *bbuf;
+ size_t blen;
+ size_t cbyte;
+ size_t cbit;
+};
+
+static uint8_t read_bit(BitR *br)
+{
+ assert(br->cbyte < br->blen);
+ uint8_t bit = (br->bbuf[br->cbyte] >> (7 - br->cbit)) & 1;
+ br->cbit += 1;
+ if (br->cbit >= 8)
+ {
+ br->cbyte += 1;
+ br->cbit = 0;
+ }
+ return bit;
+}
+
+static uint64_t read_bits(BitR *br, uint8_t len)
+{
+ uint64_t r = 0;
+ for (size_t i = 0; i < len; ++i)
+ {
+ r <<= 1;
+ r |= read_bit(br);
+ }
+ return r;
+}
+#endif
+
+// This demo encodes raw bytes (domain [0, 255])
+#define MAX_SYMBOLS 256
+
+// In a Huffman tree, the number of internal nodes is always one less than the number of symbols.
+// ...according to Wikipedia. I don't know how to prove this.
+#define MAX_INTERNAL_NODES (MAX_SYMBOLS - 1)
+
+#define MAX_NODES (MAX_SYMBOLS + MAX_INTERNAL_NODES)
+
+typedef struct Node Node;
+struct Node
+{
+ uint8_t sym;
+ int32_t weight;
+
+ Node *tl; // tree left
+ Node *tr; // tree right
+
+ Node *ln; // linked list next
+};
+
+static int sort_node_freq(const void *p1, const void *p2)
+{
+ const Node *n1 = p1;
+ const Node *n2 = p2;
+ return (n1->weight > n2->weight) - (n1->weight < n2->weight);
+}
+
+// arena allocator for internal nodes
+static Node *new_node(void)
+{
+ static Node buf[MAX_INTERNAL_NODES];
+ static size_t idx = 0;
+ assert(idx < MAX_INTERNAL_NODES);
+ return &buf[idx++];
+}
+
+typedef struct Code Code;
+struct Code
+{
+ uint64_t bits;
+ uint8_t len;
+};
+
+static void build_dictionary(Node *node, uint64_t bits, uint8_t len, Code *dictionary)
+{
+ // Huffman tree nodes always have 0 or 2 children
+ if (!node->tl)
+ {
+ // leaf
+ dictionary[node->sym].bits = bits;
+ dictionary[node->sym].len = len;
+ return;
+ }
+
+ // internal
+ build_dictionary(node->tl, (bits << 1) | 0, len + 1, dictionary); // left = 0
+ build_dictionary(node->tr, (bits << 1) | 1, len + 1, dictionary); // right = 1
+}
+
+static void write_tree(BitW *bw, Node *n)
+{
+ if (!n->tl)
+ {
+ // leaf
+ write_bit(bw, 1);
+ write_bits(bw, n->sym, 8);
+ return;
+ }
+
+ // internal
+ write_bit(bw, 0);
+ write_tree(bw, n->tl);
+ write_tree(bw, n->tr);
+}
+
+void decompress(const uint8_t *bbuf, size_t blen);
+
+int main(int argc, char **argv)
+{
+ if (argc < 2)
+ die("supply an input string\n");
+
+ printf("inp: %s\n", argv[1]);
+ const uint8_t *ibuf = (const uint8_t *)argv[1];
+ const size_t ilen = strlen(argv[1]);
+
+ // Set of all possible symbols
+ Node syms[MAX_SYMBOLS] = { 0 };
+ for (size_t i = 0; i < MAX_SYMBOLS; ++i)
+ syms[i].sym = i & 0xFF;
+
+ // Count frequencies of symbols in input data
+ for (size_t i = 0; i < ilen; ++i)
+ syms[ibuf[i]].weight += 1;
+
+ // Sort by frequency
+ qsort(syms, MAX_SYMBOLS, sizeof(Node), sort_node_freq);
+#ifdef DEBUG
+ for (size_t i = 0; i < MAX_SYMBOLS; ++i)
+ if (syms[i].weight)
+ printf("'%c': %d\n", (char)syms[i].sym, syms[i].weight);
+#endif
+
+ // Linked list-ify
+ Node *queue = 0;
+ for (size_t i = 1; i <= MAX_SYMBOLS; ++i)
+ {
+ Node *n = &syms[MAX_SYMBOLS - i];
+ if (n->weight)
+ {
+ n->ln = queue;
+ queue = n;
+ }
+ }
+#ifdef DEBUG
+ for (Node *n = queue; n; n = n->ln)
+ printf("'%c':%d->", (char)n->sym, n->weight);
+ printf("0\n");
+#endif
+ assert(queue);
+
+ // Single-node trees do not generate valid Huffman codes. Add a dummy leaf.
+ if (!queue->ln)
+ {
+ Node *n = new_node();
+ n->sym = queue->sym ^ 1; // some value other than the existing one
+ n->ln = queue;
+ queue = n;
+ }
+
+ // Combine the two lightest nodes
+ while (queue->ln)
+ {
+ Node *n1 = queue;
+ Node *n2 = queue->ln;
+ Node *n3 = new_node();
+ // n3 adopts n1 and n2
+ n3->tl = n1;
+ n3->tr = n2;
+ n3->weight = n1->weight + n2->weight;
+ // n1 and n2 are removed from the list
+ queue = queue->ln->ln;
+ n1->ln = 0;
+ n2->ln = 0;
+ // n3 is inserted back into the sorted queue
+ Node **p = &queue;
+ while (*p && (*p)->weight <= n3->weight)
+ p = &(*p)->ln;
+ n3->ln= *p;
+ *p = n3;
+ }
+
+ // Traverse tree to build dictionary
+ Code dictionary[MAX_SYMBOLS] = { 0 };
+ build_dictionary(queue, 0, 0, dictionary);
+#ifdef DEBUG
+ for (size_t i = 0; i < MAX_SYMBOLS; ++i)
+ {
+ Code *c = &dictionary[i];
+ if (!c->len)
+ continue;
+ printf("%c: ", (char)i);
+ for (size_t j = 0; j < c->len; ++j)
+ {
+ uint8_t bit = (c->bits >> (c->len - j - 1)) & 1;
+ printf(bit ? "1" : "0");
+ }
+ printf("\n");
+ }
+#endif
+ // Calculate maximum possible tree payload len
+ uint64_t max_tree_bits = 10 * MAX_SYMBOLS;
+
+ // Calculate data payload len
+ uint64_t data_bits = 0;
+ for (size_t i = 0; i < ilen; ++i)
+ data_bits += dictionary[ibuf[i]].len;
+
+ BitW bw = { 0 };
+ bw.blen = (32 + data_bits + max_tree_bits + 7) / 8; // in bytes, rounded up
+ bw.bbuf = calloc(1, bw.blen); assert(bw.bbuf);
+
+ write_bits(&bw, ilen, 32);
+ write_tree(&bw, queue);
+ for (size_t i = 0; i < ilen; ++i)
+ {
+ Code *c = &dictionary[ibuf[i]];
+ write_bits(&bw, c->bits, c->len);
+ }
+
+ printf("input size: %zu bits\n", ilen * 8);
+ printf("compressed size: %zu bits\n", bw.cbyte * 8 + bw.cbit);
+}
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-11 22:50:40 +0000