This is an update to a question I posed nearly two years ago about my implementation of Huffman Coding which I had written in C. Since then I have had time to grow as a programmer and have managed to integrate most, if not all, of the suggestions given to me then and I am looking for fresh feedback on the current version of my code.

Let’s begin with a high level look at the internals of the library. The library is very simple to use and consists of two interface functions, huffman_encode() and huffman_decode().

Encoding Overview

huffman_encode() begins by performing a frequency analysis of the bytes in the input from which it generates a binary Huffman Tree, and in turn generates an encoding table to allow for fast compression. Once this is complete, it writes all the the header information (encoding representations of each byte, the original decompressed length of the data, the length of the encoded data, and the size of the header) before writing the compressed data itself to the output byte by byte.

One of the criticisms I received in my original implementation of this process was that my code relied on writing only one bit at a time to the output. I was able to devise a significantly faster way of achieving the same result by writing up to 16 bits in blocks of up to 8 bits simultaneously to the output via the function write_k_bits().

Decoding Overview

huffman_decode() first reads the decompressed length of and the header size before building a decoding table based on the encoding representations stored in the header. Then, it uses this table and the function peek_buffer() to read two bytes of the compressed data at an arbitrary bit offset and convert that to the decoded representation of that character. This process is then repeated until the entirety of the input has been decompressed.

Decoding was where the focus of the criticisms were in my previous implementation. My previous decoded would work by building a Huffman Tree from the header and then reading one bit at a time from the compressed data and traversing the tree to see if the currently read bits represented a compressed character. This was a very slow method as it not only read a single bit at a time but it also required a traversal of the tree for every single bit read from the buffer which for long strings would require multiple fruitless traversals of the tree for every single byte of data! I have solved this by reading multiple bytes of data simultaneously via the function peek_buffer() and using a lookup table for decoding instead of rebuilding the original tree.

Additional Changes

As well as the changes referenced above, I have made many other improvements since my previous post. These include increasing the maximum number of bits which can represent a compressed byte from 8 to 16, reduction of the header size, compression of arbitrary data (previously only character strings could be compressed), removal of the clunky linked list, improved file organisation and folder structure, addition of a Makefile, and other small improvements.

Feedback I am looking for

The majority of the changes I have made have involved improving the performance of my code and the compression ratios of my tests and I am very interested in hearing about any further improvements I could make in these areas. I am particularly interested in ways which I might reduce the size of the headers as their current size often leads to compression ratios > 1 for shorter and more diverse inputs and therefore end up making the "compressed" versions of certain inputs larger than the original uncompressed versions. Of course if you can find any bugs in my code then I’d very much like to hear about those as well.

Other slightly less important things which would still be good to get feedback on might include potential memory usage reductions, documentation/comment quality, style improvements, and potential porting issues between systems (this code was compiled with GCC 8.3.0 on Debian Sid).

I have posted all the code below as per the Code Review rules, although I would recommend you clone it from my GitHub repository if you plan on testing it yourself (you will need to create the directory obj/ inside the cloned repo before you run make).

The Code

huffman.c

/* 
 *  Filename:   huffman.c
 *  Author:     Jess Turner
 *  Date:       13/07/20
 *  Licence:    GNU GPL V3
 *
 *  Encode and decode a byte stream using Huffman coding
 *
 *  Return/exit codes:
 *      EXIT_SUCCESS    - No error
 *      MEM_ERROR       - Memory allocation error
 *      INPUT_ERROR     - No input given
 *
 *  Interface Functions:
 *      - huffman_encode()      - Encodes a string using Huffman coding
 *      - huffman_decode()      - Decodes a Huffman encoded string 
 *
 *  Internal Functions:
 *
 *      Encoding:
 *          - create_huffman_tree()     - Generate a Huffman tree from a frequency analysis
 *          - create_encoding_table()   - Generate a "code array" from the huffman tree, used for fast encoding
 *          - node_compare()            - Calculate the difference in frequency between two nodes
 *          - create_byte_node()        - Generate a byte node
 *          - create_internal_node()    - Generate an internal node
 *          - destroy_huffmantree()     - Traverses a Huffman tree and frees all memory associated with it
 *          - write_k_bits()            - Write an arbitrary number of bits to a buffer
 *
 *      Decoding:
 *          - peek_buffer()             - Read a two bytes from a buffer at any given bit offset
 *
 *  Data structures:
 *
 *      Code array:
 *          - Fast way to encode and decode data using the information generated from a Huffman tree and an easy way to store a representation of the tree
 *          - 2D array that represents each byte to be encoded and how it is encoded allowing for O(1) time to determine how a given byte is encoded
 *          - Position in the array (i.e. code_array[0-255]) represents the byte to be encoded or an encoded byte
 *
 *      Huffman tree:
 *          - Binary tree that operates much like any other Huffman tree
 *          - Contains two types of nodes, internal nodes and byte nodes
 *          - Every node contains either the frequency of the byte it represents if it is a byte node or the combined frequencies of its child nodes if it is an internal node
 *
 *  Encoded data format:
 *
 *      - Header
 *          - Compressed string length (1x uint32_t)
 *          - Decompressed string length (1x uint32_t)
 *          - Header size (1x uint16_t)
 *          - Huffman tree stored as an encoding table (16 + (number of bits representing the encoded byte) bits per byte: byte, bit length of encoded representation, encoded representation)
 *      - Encoded data
 *
 *  The future:
 *      - Find way to reduce header size
 *          - Possibly using the huffman algorithm twice to encode the header?
 *      - Combine with duplicate string removal and make full LZW compression
 *
 */

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#include "../include/huffman.h"

/* Interface functions */

int huffman_encode(uint8_t * input, uint8_t ** output, uint32_t decompressed_length)
{
    size_t      freq[256]           = { 0 };
    uint16_t    encoded_bytes       = 0;

    /* Frequency analysis */

    for(size_t i = 0; i < decompressed_length; i++)
        freq[input[i]]++;

    for(uint16_t i = 0; i < 256; i++)
        if(freq[i])
            encoded_bytes++;

    /* Handle strings with either one unique byte or zero bytes */

    if(!encoded_bytes) {
        return INPUT_ERROR;
    } else if(encoded_bytes == 1) {
        for(uint16_t i = 0; i < 256; i++) {
            if(freq[i]) {
                ++freq[i > 0 ? i - 1 : i + 1];
            }
        }
    }

    /* Construct a Huffman tree from the frequency analysis */

    huffman_node_t * head_node = NULL;

    if(create_huffman_tree(freq, &head_node) != EXIT_SUCCESS)
        return MEM_ERROR;

    huffman_coding_table_t encoding_table[256] = {{ .code = 0, .length = 0 }};

    /* Convert the tree to a lookup table */

    create_encoding_table(head_node, encoding_table, 0);
    destroy_huffman_tree(head_node);

    size_t header_bit_length = 0;

    /* Use the generated encoding table to calculate the byte length of the output */

    for(uint16_t i = 0; i < 256; i++)
        if(encoding_table[i].length)
            header_bit_length += 16 + encoding_table[i].length;

    size_t header_byte_length = (header_bit_length >> 3) + !!(header_bit_length & 0x7); /* Fast division by 8, add one if there's a remainder */
    size_t encoded_bit_length = 0;

    for(size_t i = 0; i < decompressed_length; i++)
        encoded_bit_length += encoding_table[input[i]].length;

    size_t encoded_byte_length = (encoded_bit_length >> 3) + !!(encoded_bit_length & 0x7);

    if(!(*output = calloc(HEADER_BASE_SIZE + header_byte_length + encoded_byte_length + 1, sizeof(uint8_t))))
        return MEM_ERROR;

    /* Write header information */

    ((uint32_t *)(*output))[0] = decompressed_length;
    ((uint32_t *)(*output))[1] = encoded_byte_length;
    ((uint16_t *)(*output))[4] = header_bit_length;

    size_t bit_pos = HEADER_BASE_SIZE << 3;

    /* Store the encoding information */

    for(uint16_t i = 0; i < 256; i++) {
        if(encoding_table[i].length) {
            write_k_bits(*output, i, &bit_pos, 8);
            write_k_bits(*output, encoding_table[i].length, &bit_pos, 8);
            write_k_bits(*output, encoding_table[i].code, &bit_pos, encoding_table[i].length);
        }
    }

    /* Encode output stream */

    for(size_t i = 0; i < decompressed_length; i++)
        write_k_bits(*output, encoding_table[input[i]].code, &bit_pos, encoding_table[input[i]].length);

    return EXIT_SUCCESS;
}

int huffman_decode(uint8_t * input, uint8_t ** output)
{
    size_t                  bit_pos                 = HEADER_BASE_SIZE << 3;
    huffman_coding_table_t  decoding_table[65536]   = {{ .symbol = 0, .length = 0 }};

    /* Extract header information */

    uint32_t decompressed_length    = * (uint32_t *) &input[0];
    uint16_t header_bit_length      = * (uint16_t *) &input[8] + (HEADER_BASE_SIZE << 3);

    /* Build decoding lookup table */

    while(bit_pos < header_bit_length) {
        uint8_t decoded_byte = peek_buffer(input, bit_pos);

        bit_pos += 8;

        uint8_t encoded_length = peek_buffer(input, bit_pos) & 15;

        encoded_length = encoded_length ? encoded_length : 16;
        bit_pos += 8;

        uint8_t pad_length = MAX_CODE_LEN - encoded_length;
        uint16_t encoded_byte = peek_buffer(input, bit_pos) & ((1U << encoded_length) - 1); /* Trim all leading bits */

        bit_pos += encoded_length;

        uint16_t padmask = (1U << pad_length) - 1;

        for(uint16_t padding = 0; padding <= padmask; padding++)
            decoding_table[encoded_byte | (padding << encoded_length)] = (huffman_coding_table_t) { .symbol = decoded_byte, .length = encoded_length };
    }

    if(!(*output = calloc(decompressed_length + 1, sizeof(uint8_t))))
        return MEM_ERROR;

    /* Decode input stream */

    for(uint32_t byte_count = 0; byte_count < decompressed_length; byte_count++) {
        uint16_t buffer = peek_buffer(input, bit_pos);

        (*output)[byte_count] = decoding_table[buffer].symbol;
        bit_pos += decoding_table[buffer].length;
    }

    (*output)[decompressed_length] = '';

    return EXIT_SUCCESS;
}

/* Encoding functions */

huffman_node_t * create_byte_node(uint8_t c, size_t freq)
{
    huffman_node_t * node;

    if(!(node = malloc(sizeof(huffman_node_t))))
        return NULL;

    node->freq = freq;
    node->child[0] = NULL;
    node->child[1] = NULL;
    node->c = c;

    return node;
}

huffman_node_t * create_internal_node(huffman_node_t * first_child, huffman_node_t * second_child)
{
    huffman_node_t * node;

    if(!(node = malloc(sizeof(huffman_node_t))))
        return NULL;

    node->freq = first_child->freq + second_child->freq;
    node->child[0] = first_child;
    node->child[1] = second_child;

    return node;
}

int create_huffman_tree(size_t * freq, huffman_node_t ** head_node) {
    huffman_node_t  *   node_list[256]  = { NULL };
    huffman_node_t  *   internal_node;
    huffman_node_t  **  node_list_p;
    size_t              node_count      = 0;

    for(uint16_t i = 0; i < 256; i++)
        if(freq[i] && !(node_list[node_count++] = create_byte_node((uint8_t)i, freq[i])))
            return MEM_ERROR;

    node_list_p = node_list;

    while(node_count > 1) {
        qsort(node_list_p, node_count, sizeof(huffman_node_t *), node_compare);

        if(!(internal_node = create_internal_node(node_list_p[0], node_list_p[1])))
            return MEM_ERROR;

        node_list_p[0] = NULL;
        node_list_p[1] = internal_node;

        node_list_p++;
        node_count--;
    }

    *head_node = node_list_p[0];

    return EXIT_SUCCESS;
}

int node_compare(const void * first_node, const void * second_node)
{
    huffman_node_t * first  = *(huffman_node_t **)first_node;
    huffman_node_t * second = *(huffman_node_t **)second_node;

    if(!(first->freq - second->freq)) {
        if(first->child[1] && !second->child[1])
            return 1;
        else if(!first->child[1] && second->child[1])
            return -1;
        else
            return 0;
    } else {
        return first->freq - second->freq;
    }
}

void create_encoding_table(huffman_node_t * node, huffman_coding_table_t huffman_array[256], uint8_t bits_set)
{
    static uint16_t value = '';

    if(node->child[1]) {
        value &= ~(0x1 << bits_set);
        create_encoding_table(node->child[0], huffman_array, bits_set + 1);
        value |= 0x1 << bits_set;
        create_encoding_table(node->child[1], huffman_array, bits_set + 1);
    } else {
        huffman_array[node->c].code = value & ((1U << bits_set) - 1);
        huffman_array[node->c].length = bits_set;
    }
}

void destroy_huffman_tree(huffman_node_t * node)
{
    if(node->child[1]) {
        destroy_huffman_tree(node->child[0]);
        destroy_huffman_tree(node->child[1]);
    }

    free(node);

    return;
}

void write_k_bits(uint8_t * buffer, uint16_t value, size_t * bit_pos, uint8_t bits)
{
    size_t byte_pos             = *bit_pos >> 3;
    uint8_t bit_offset          = *bit_pos & 7;
    uint8_t bits_to_first_byte  = 8 - bit_offset;
    uint8_t extra_bytes_needed  = ((bit_offset + bits) >> 3) - (bit_offset >> 3);

    buffer[byte_pos] &= ~0 >> bits_to_first_byte; /* Clear the top n bits of the first byte we're writing to */
    buffer[byte_pos] |= value << bit_offset; /* Shift `value` so that the largest relevant bit is in the MSB position and write as many bits as we can to the first byte of the buffer */

    if(extra_bytes_needed > 0) {
        value >>= bits_to_first_byte; /* Shift `value` such that the relevant bits can be written to the buffer */
        buffer[byte_pos + 1] &= 0; /* Clear the next byte */
        buffer[byte_pos + 1] |= value; /* Write the next 8 bits of `value` to the buffer */

        if(extra_bytes_needed > 1) {
            value >>= 8;
            buffer[byte_pos + 2] &= 0;
            buffer[byte_pos + 2] |= value; /* Write the remainder of `value` to the buffer */
        }
    }

    *bit_pos += bits;
}

/* Decoding functions */

uint16_t peek_buffer(uint8_t * input, size_t bit_pos)
{
    size_t byte_pos = (bit_pos >> 3);
    uint32_t concat = (input[byte_pos + 2] << 0x10) | (input[byte_pos + 1] << 0x8) | input[byte_pos];

    return concat >> (bit_pos & 7); /* Concatenate three successive bytes together and return a two bytes at the calculated bit offset */
}

huffman.h

#ifndef HUFFMAN_H
#define HUFFMAN_H

/* Header files */

#include <stdint.h>

/* Return values */

#define EXIT_SUCCESS 0
#define MEM_ERROR 1
#define INPUT_ERROR 2

/* Node identifiers, might change to enumeration */

#define INTERNAL_NODE 0
#define BYTE_NODE 1

#define HEADER_BASE_SIZE 10 /* Size of the header with no bytes stored */

#define MAX_CODE_LEN 16 /* The longest any encoded representation is allowed to be */

/* Huffman Tree node */

typedef struct huffman_node_t {
    size_t freq;
    union {
        struct huffman_node_t * child[2];
        uint8_t c;
    };
} huffman_node_t;

/* Lookup table used for encoding and decoding */

typedef struct huffman_coding_table_t {
    union {
        uint16_t code;
        uint8_t symbol;
    };
    uint8_t length;
} huffman_coding_table_t;

/* Interface Functions */

int huffman_decode(uint8_t * input, uint8_t ** output);
int huffman_encode(uint8_t * input, uint8_t ** output, uint32_t decompressed_length);

/* Internal Decoding Functions */

uint16_t peek_buffer(uint8_t * input, size_t bit_pos);

/* Internal Encoding Functions */

int create_huffman_tree(size_t * freq, huffman_node_t ** head_node);
int node_compare(const void * first_node, const void * second_node);
huffman_node_t * create_byte_node(uint8_t c, size_t freq);
huffman_node_t * create_internal_node(huffman_node_t * first_child, huffman_node_t * second_child);
void create_encoding_table(huffman_node_t * node, huffman_coding_table_t huffman_array[256], uint8_t bits_set);
void destroy_huffman_tree(huffman_node_t * node);
void write_k_bits(uint8_t * buffer, uint16_t value, size_t * byte_pos, uint8_t bits);

#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "../include/huffman.h"

int compare(uint8_t * first, uint8_t * second, size_t len);

int main()
{
    uint8_t * encoded = NULL;
    uint8_t * decoded = NULL;
    char * test_strings[] = {
                "test string",
                "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!"£$%^&*()-=_+\|,./<>?[]{}'#@~`¬n",
                "test",
                "Hello world!",
                "This is a test string",
                "My name is Jeff",
                "Test",
                "tteesstt",
                "test",
                "ab",
                "Ω≈ç√∫˜µ≤≥÷",
                "ЁЂЃЄЅІЇЈЉЊЋЌЍЎЏАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯабвгдежзийклмнопрстуфхцчшщъыьэюя",
                "If you're reading this, you've been in a coma for almost 20 years now. We're trying a new technique. We don't know where this message will end up in your dream, but we hope it works. Please wake up, we miss you.",
                "a",
                "aaaaaaaaaaaaaa",
                "",
                "Powerلُلُصّبُلُلصّبُررً ॣ ॣh ॣ ॣ冗",
                "When the sunlight strikes raindrops in the air, they act as a prism and form a rainbow. The rainbow is a division of white light into many beautiful colors. These take the shape of a long round arch, with its path high above, and its two ends apparently beyond the horizon. There is , according to legend, a boiling pot of gold at one end. People look, but no one ever finds it. When a man looks for something beyond his reach, his friends say he is looking for the pot of gold at the end of the rainbow. Throughout the centuries people have explained the rainbow in various ways. Some have accepted it as a miracle without physical explanation. To the Hebrews it was a token that there would be no more universal floods. The Greeks used to imagine that it was a sign from the gods to foretell war or heavy rain. The Norsemen considered the rainbow as a bridge over which the gods passed from earth to their home in the sky. Others have tried to explain the phenomenon physically. Aristotle thought that the rainbow was caused by reflection of the sun's rays by the rain. Since then physicists have found that it is not reflection, but refraction by the raindrops which causes the rainbows. Many complicated ideas about the rainbow have been formed. The difference in the rainbow depends considerably upon the size of the drops, and the width of the colored band increases as the size of the drops increases. The actual primary rainbow observed is said to be the effect of super-imposition of a number of bows. If the red of the second bow falls upon the green of the first, the result is to give a bow with an abnormally wide yellow band, since red and green light when mixed form yellow. This is a very common type of bow, one showing mainly red and yellow, with little or no green or "
            }; /* A series of horrible strings that try and break the compression */

    size_t successes = 0;
    size_t failures = 0;
    size_t test_count = sizeof(test_strings) / sizeof(test_strings[0]);

    for(size_t i = 0; i < test_count; i++) {
        printf("nEncoding string %zu...", i);
        fflush(stdout);

        if(huffman_encode((uint8_t *)test_strings[i], &encoded, strlen(test_strings[i]) + 1) != EXIT_SUCCESS) {
            fprintf(stderr, "nError: Failed to encode string %zu!n", i);
            failures++;
            continue;
        }

        printf("Done!nAttempting to decode...");
        fflush(stdout);

        if(huffman_decode(encoded, &decoded) != EXIT_SUCCESS) {
            fprintf(stderr, "nError: Failed to decode string %zu!n", i);
            free(encoded);
            failures++;
            continue;
        }

        printf("Done!nValidating...");
        
        if(!compare((uint8_t *)test_strings[i], decoded, strlen(test_strings[i]))) {
            uint32_t uncompressed_len = (*(uint32_t *) &encoded[0]) << 3;
            uint32_t compressed_len = ((*(uint32_t *) &encoded[4]) << 3) + (*(uint16_t *) &encoded[8]);

            printf("Success!nUncompressed length: %u (~%u bytes)nCompressed length: %u (~%u bytes)nCompression ratio: %lfn", uncompressed_len, uncompressed_len >> 3, compressed_len, compressed_len >> 3, (float) compressed_len / uncompressed_len);
        } else {
            printf("Failed! Got "");

            for(size_t j = 0; j < strlen(test_strings[i]); j++)
                putchar(decoded[j]);

            printf(""!n");

            failures++;
        }

        free(decoded);
        free(encoded);

        successes++;
    }

    printf("Results:nnTests completed: %zunSuccessful tests: %zu (%.0f%%)nFailed tests: %zu (%.0f%%)n", test_count, successes, 100 * (float) successes / test_count, failures, 100 * (float) failures / test_count);

    return 0;
}

int compare(uint8_t * first, uint8_t * second, size_t len)
{
    for(size_t i = 0; i < len; i++) {
        if(first[i] < second[i]) {
            return -1;
        } else if(first[i] > second[i]) {
            return 1;
        }
    }

    return 0;
}

Makefile

CC := gcc
SRCDIR := src
OBJDIR := obj
DEPDIR := include
TARGET := huffman
CFLAGS := -Wall -Wextra -Wpedantic

LIBS := 

_OBJS := huffman.o main.o

OBJS := $(patsubst %,$(OBJDIR)/%,$(_OBJS))
_DEPS := huffman.h
DEPS := $(patsubst %,$(DEPDIR)/%,$(_DEPS))

$(OBJDIR)/%.o: $(SRCDIR)/%.c $(DEPS)
    $(CC) -c -o $@ $< $(CFLAGS)

$(TARGET): $(OBJS)
    $(CC) -o $@ $^ $(CFLAGS) $(LIBS)

.PHONY: clean

clean:
    rm -f $(OBJDIR)/*.o $(TARGET)