Huffman_encoding.c

// https://rosettacode.org/wiki/Huffman_coding - solved in C

#include <stdio.h>
#include <string.h>
#include <sys/time.h>

typedef struct timeval timepoint_t;
static inline timepoint_t get_time(void) {
  struct timeval t; gettimeofday(&t, NULL); return t;
}
static inline double time_diff_us(timepoint_t start, timepoint_t end) {
  return (end.tv_sec - start.tv_sec) * 1000000.0 + (end.tv_usec - start.tv_usec);
}

// Fixed typedef - self-referential struct
typedef struct node_t { struct node_t *left, *right; int freq; char c; } node_t, *node;

// Ultra-compact globals
static node_t pool[256];
static node q[256];
static char *code[256], buf[1024], *buf_pos;
static int n_nodes, qend;

static inline node new_node(int freq, char c, node a, node b) {
  node n = pool + n_nodes++;
  n->freq = freq; n->c = freq ? c : 0; n->left = a; n->right = b;
  return n;
}

static inline void qup(int i, node n) {
  while (i > 1 && q[i>>1]->freq > n->freq) { q[i] = q[i>>1]; i >>= 1; }
  q[i] = n;
}

static inline node qdown(void) {
  node top = q[1], last = q[--qend];
  int i = 1, j;
  while ((j = i << 1) < qend) {
    if (j + 1 < qend && q[j+1]->freq < q[j]->freq) j++;
    if (last->freq <= q[j]->freq) break;
    q[i] = q[j]; i = j;
  }
  q[i] = last;
  return top;
}

static void code_gen(node n, char *s, int len) {
  if (n->c) {
    s[len] = 0;
    char *dst = buf_pos;
    char *src = s;
    while ((*dst++ = *src++));
    code[n->c] = buf_pos;
    buf_pos = dst;
    return;
  }
  s[len] = '0'; code_gen(n->left, s, len + 1);
  s[len] = '1'; code_gen(n->right, s, len + 1);
}

void huffman_init(const char *text) {
  int freq[256] = {0};

  n_nodes = 0; qend = 1; buf_pos = buf;
  memset(code, 0, sizeof(code));

  while (*text) freq[*text++]++;

  for (int i = 0; i < 256; i++) {
    if (freq[i]) qup(qend++, new_node(freq[i], i, 0, 0));
  }

  if (qend <= 2) {
    if (qend == 2) { *buf_pos = '0'; buf_pos[1] = 0; code[q[1]->c] = buf_pos; }
    return;
  }

  while (qend > 2) qup(qend++, new_node(0, 0, qdown(), qdown()));

  char path[16];
  code_gen(q[1], path, 0);
}

int huffman_encode(const char *text, char *out) {
  char *start = out;
  while (*text) {
    char *c = code[*text++];
    if (c) while (*c) *out++ = *c++;
  }
  *out = 0;
  return out - start;
}

int main(void) {
  const char *tests[] = {
    "***this is an example for huffman encoding***",
    "hello world", "aaaaaaa", "ab"
  };

  timepoint_t start = get_time();

  for (int i = 0; i < 4; i++) {
    timepoint_t t1 = get_time();
    huffman_init(tests[i]);
    timepoint_t t2 = get_time();

    char encoded[4096];
    int bits = huffman_encode(tests[i], encoded);
    timepoint_t t3 = get_time();

    printf("Test %d: %.1f μs init, %.1f μs encode, %d->%d bits\n",
           i+1, time_diff_us(t1,t2), time_diff_us(t2,t3), (int)strlen(tests[i])*8, bits);
  }

  printf("Total: %.2f ms\n", time_diff_us(start, get_time()) / 1000.0);
  return 0;
}

gcc -std=c11 -O3 -march=native -DNDEBUG -flto -fomit-frame-pointer huffman.c -o huffman_ultra

./huffman_ultra

Test 1: 19.0 μs init, 4.0 μs encode, 360->315 bits
Test 2: 3.0 μs init, 1.0 μs encode, 88->39 bits
Test 3: 1.0 μs init, 0.0 μs encode, 56->7 bits
Test 4: 1.0 μs init, 0.0 μs encode, 16->2 bits

Total: 0.13 ms

Test 1 Init-19 μs
Encoding-Sub-microsecond Near-optimal