10
\$\begingroup\$

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] = '\0';

    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 = '\0';

    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",
                "\0",
                "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: %lf\n", 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:\n\nTests completed: %zu\nSuccessful 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)
\$\endgroup\$
3
\$\begingroup\$

A bug

This version of the program uses limited-length codes, which is good. Decoding looks good. However, limited-length codes create a new edge case: what if the tree is deeper than the length limit? There are various solutions, but as far as I can tell, none of them are used in this program - a length that exceeds MAX_CODE_LEN is generated and things go wrong. This is difficult to find with tests, as almost any realistic string would not result in such a long code. As an example of an unrealistic string, here is one (I cannot put it directly in this answer, it exceeds the size limit of 64KB). I mentioned some approaches to handle that edge case last time, but to go into a little more detail of the simplest trick: divide the frequencies by 2 while rounding up, then rebuild the tree (iterate if necessary).

Or, as an alternative to correctly handling that edge case, I suggest at least correctly failing to handle it: outputting an appropriate error message instead of producing bad data which cannot be decompressed.

Divide rounding up

A couple of times there is a construction like (n >> 3) + !!(n & 0x7). There is a simpler way: (n + 7) / 8, or if you prefer, (n + 7) >> 3.

Header size

Similar as in the previous review: if canonical Huffman codes were used, the header would not need to store the codes (as they can be reconstructed from the lengths and the implicit alphabetical order of the symbols), saving space. The sequence of lengths could be further compressed.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Note: (n + 7) / 8 can overflow. (n >> 3) + !!(n & 0x7) does not. \$\endgroup\$ – chux - Reinstate Monica Jul 16 at 8:45
6
\$\begingroup\$

Magic buffer sizes

Consider making a const or #define for 256 and 65536.

Const inputs

uint8_t * input

should be

const uint8_t *input

since you don't (and shouldn't) change it.

Loop combination

This:

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++;

does not need to be two loops. In the first loop, before incrementing freq, check if it's zero. If it is, you can increment encoded_bytes.

Redundant else

Due to the return, this:

if(!encoded_bytes) {
    return INPUT_ERROR;
} else

does not need an else.

Consistent increment style

You should pick a pre- or post-increment as your standard:

    freq[input[i]]++;
    ++freq[i > 0 ? i - 1 : i + 1];

C standard

You're definitely using features that require C99 or later, such as

{{ .code = 0, .length = 0 }};

While this is good, you do not explicitly declare your std in your makefile. Unless you have a specific reason, it's quite safe to indicate C17.

In-expression assignment

This:

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

should be avoided. Save everyone the headache and do it in two statements. I promise you that you will not see a performance difference.

Temporary pointer

Since you need this three times:

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

make a temporary pointer to store (uint32_t *)(*output). Better yet: make a structure to represent that header, and then rather than using indexing, just assign members.

Ternary abuse

    encoded_length = encoded_length ? encoded_length : 16;

might as well be

if (!encoded_length)
    encoded_length = 16;

For loops

while(node_count > 1) {
    // ...
    node_count--;
}

is, I find, more legible as

for (; node_count > 1; node_count--) {

Internal functions

You say that these are internal functions:

/* Internal Decoding Functions */
/* Internal Encoding Functions */

So then why declare them in the header? If you declare them static and omit them from the header, the compiler will understand that they are not for export and may be able to do more optimization.

Similarly, is it necessary for your structures to have declarations in the header? It would enforce more loose coupling if you move your full definitions to the C file, particularly given that they are only used by internal functions.

Make idempotence

you will need to create the directory obj/

This can be avoided by making any compilation step depend on a rule that makes obj, in turn running mkdir -p obj/.

| improve this answer | |
\$\endgroup\$
  • 4
    \$\begingroup\$ @ThePainfull It is because one of the ternary branches is effectively a no-op, so there isn't really a benefit to expressing this as a ternary. \$\endgroup\$ – Reinderien Jul 14 at 13:34
  • 4
    \$\begingroup\$ @frarugi87 It's a matter of legibility and style. I prefer the de-nesting and brevity that multiple returns can provide. For more discussion see stackoverflow.com/questions/36707/… \$\endgroup\$ – Reinderien Jul 14 at 13:37
  • 4
    \$\begingroup\$ Loose coupling. The consumer of your library should not need to see the spinning gears; they should only see the nice, clean interface that you provide to them. \$\endgroup\$ – Reinderien Jul 14 at 15:47
  • 4
    \$\begingroup\$ Is it considered best practice to move as much information as possible from the header file to the source file - when those details are considered "internal", then yes, absolutely. Why have the opaque definition in the header file at all - actually, since that struct is only ever used by internal functions, then you're right: you don't need to declare it in the header file at all. \$\endgroup\$ – Reinderien Jul 14 at 15:54
  • 4
    \$\begingroup\$ Would you recommend moving some of my #define's to the source file - Yes, but the ones that define the return values from your external functions should stay. \$\endgroup\$ – Reinderien Jul 14 at 15:55
2
\$\begingroup\$

Array sizes

uint32_t may be too small or needlessly large to index arrays. Use size_t for array indexing and sizing.

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

Namespace spattered

Rather than huffman.h include defines/functions with names all over the place, consider using a common prefix like below:

//#define EXIT_SUCCESS 0
#define HUFFMAN_EXIT_SUCCESS 0
//#define INTERNAL_NODE 0
#define HUFFMAN_INTERNAL_NODE 0
// void create_encoding_table(huffman_node_t * node, huffman_coding_table_t huffman_array[256], uint8_t bits_set);
void huffman_create_encoding_table(huffman_node_t * node, huffman_coding_table_t huffman_array[256], uint8_t bits_set);

Many of the offending name belong in huffman.c and not in huffman.h

Enough #includes <> in huffman.h?

huffman.h may be missing some standard includes. size_t is not certainly defined through stdint.h>

A simple test is in huffman.c to include huffman.h first.

#include "../include/huffman.h" // add
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
// #include "../include/huffman.h"

Document in huffman.h

Much of the useful documentation about the overall code would benefit being in huffman.h.

Consider a user may only see huffman.h and binary huffman.o.

Efficient size indexes

Why uint16_t i vs. usigned i vs. uint_fast16_t? Why force a narrow type?

for(uint16_t i = 0; i < 256; i++)

Assume the compiler knows best, use unsigned.

Allocate to the size of the referenced object

Easier to code right, review and maintain. Long lines of code deserve breaking up.

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

size_t n = HEADER_BASE_SIZE + header_byte_length + encoded_byte_length + 1;
output = calloc(n, sizeof *output);
//                 ^^^^^^^^^^^^^^  size of the referenced object
if(output == NULL) {
    return MEM_ERROR;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ uint32_t may be too small or needlessly large to index arrays Surely since I'm writing this value to the header I need guarantees about its width so I can decode it properly later on? If I use size_t then I don't have such guarantees and I'm perfectly happy with limiting the compression to 4GB inputs \$\endgroup\$ – jess Jul 17 at 9:05
  • \$\begingroup\$ @DemonessJess The type of uint32_t decompressed_length and size_t freq[256] should match. "Surely since I'm writing this value to the header I need guarantees about its width " is a curious premise. Code can easily be better written without such a guarantee/limitation Lots of good and portable code can be written without the optional types uintN_t. uintN_t types are useful and good where required. The algorithm here does not rely on 32-bit length. uint32_t vs int as a convention for everyday programming explores these issue more. \$\endgroup\$ – chux - Reinstate Monica Jul 17 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.