Huffman compressor in plain C

Question

I recently picked up C, because I am getting tired of the hell that is Java Enterprise development. I decided that writing a Huffman compressor will be a great little exercise, and I have always wanted to write a compression algorithm. I want some pointers(get it) on how to make the code more idiomatic, modular and less verbose.

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

#define MAX_SZ 128
#define MAX_CODE_LEN 64

int counts[MAX_SZ];
char codes[MAX_SZ][MAX_CODE_LEN];

typedef struct Node {
    char character;
    int count;
    struct Node *left;
    struct Node *right;
} Node;

void calculate_prob(char *str, int *counts) {
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        counts[*str++]++;
    }
}

int comparator(const void *a, const void *b) {
    Node *n1 = (Node *)a;
    Node *n2 = (Node *)b;
    return (n1->count - n2->count);
}

Node *find_and_remove_min(Node *nodes, int sz) {
    int idx = 0;
    Node *minNode = &nodes[0];
    for (int i = 0; i < sz; i++) {
        if (nodes[i].count < minNode->count) {
            minNode = &nodes[i];
            idx = i;
        }
    }
    Node *node = (Node *)malloc(sizeof(Node));
    memcpy(node, minNode, sizeof(Node));
    nodes[idx] = nodes[sz - 1];
    return node;
}

void dfs(Node *node, char *path, int sz) {
    if (node == NULL) {
        return;
    }
    if (node->left == NULL && node->right == NULL) {
        strncpy(codes[node->character], path, sz);
        return;
    }
    path[sz] = '0';
    dfs(node->left, path, sz + 1);
    path[sz] = '1';
    dfs(node->right, path, sz + 1);
}

char *fileToString(char *file_name) {
    FILE *file = fopen(file_name, "r");
    if (file == NULL) return NULL;

    fseek(file, 0, SEEK_END);
    long int size = ftell(file);
    fclose(file);

    file = fopen(file_name, "r");
    char *str = (char *)malloc(size);
    int bytes_read = fread(str, sizeof(char), size, file);
    fclose(file);
    return str;
}

void writeCodeBook(FILE* file){
    for (int i = 0; i < MAX_SZ; i++) {
        if (codes[i][0] == '\0') {
            continue;
        }
        putc((char)i, file);
        putc(':', file);
        fwrite(codes[i], sizeof(char), strlen(codes[i]), file);
        putc('\n', file);
    }
}

void writeBitToFile(unsigned char bit, FILE *file, int flush) {
    static int count = 0;
    static char buffer = 0;
    
    if(flush){
        buffer <<= (8 - count); 
        fwrite(&buffer, sizeof(buffer), 1, file);
        return;
    }

    buffer <<= 1;          // Make room for next bit.
    if (bit) buffer |= 1;  // Set if necessary.
    count++;

    if (count == 8) {
        fwrite(&buffer, sizeof(buffer), 1, file);  // Error handling elided.
        buffer = 0;
        count = 0;
    } 
}

int main(int argc, char **argv) {
    char *str = NULL;

    if (argc > 1) {
        str = fileToString(argv[1]);
    } else {
        return 1;
    }

    calculate_prob(str, counts);
    int node_count = 0;

    for (int i = 0; i < MAX_SZ; i++) {
        if (counts[i] != 0) {
            node_count++;
        }
    }
    const int SZ = node_count;
    Node nodes[SZ];

    for (int i = 0, idx = 0; i < MAX_SZ; i++) {
        if (counts[i] != 0) {
            struct Node node = {(char)i, counts[i], NULL, NULL};
            nodes[idx++] = node;
        }
    }

    qsort(nodes, SZ, sizeof(Node), comparator);

    int sz = SZ;
    Node *root = NULL;

    while (sz != 1) {
        struct Node *min = find_and_remove_min(nodes, sz);
        struct Node *min_2 = NULL;
        sz--;
        min_2 = find_and_remove_min(nodes, sz);
        Node new_node = {'\0', min->count + min_2->count, min, min_2};
        nodes[sz - 1] = new_node;
        root = &new_node;
    }

    char path[MAX_CODE_LEN];
    memset(path, '\0', MAX_CODE_LEN);

    dfs(root, path, 0);

    FILE *file = NULL;

    if (argc > 2) {
        file = fopen(argv[2], "w+");
    } else {
        return 1;
    }

    writeCodeBook(file);

    for (char *s = str; *s; s++) {
        char *code = codes[*s];
        int len = strlen(code);
        
        for (int i = 0; i < len; i++) {
            unsigned char bit = code[i] - '0';
            // printf("%d", bit);
            writeBitToFile(bit, file, 0);
        }
    }
    writeBitToFile(0, file, 1);
}

Answer 1

Quite well-formatted, but does not quite escape your Java roots.
Unfortunately, they lead to unidiomatic code, inefficient code, and even bugs.

1. A string in C is a data-structure, not a type. Specifically, it's a sequence of non-nul elements terminated and including the terminating nul.
   Yes, that means embedded zeros are not supported. Also, you must mind the terminator. If you need something more sophisticated, write it yourself or include third-party code.

   1. strlen() just gives you the index of the terminator. Using it to determine how often your loop iterating over a string should iterate is a waste, just test for the terminator directly.

   2. strncpy() does not do what you expect. Despite its name, it is not quite a string-function.
      It copies up to n characters from the source, stopping if encountering the string terminator. The rest of the target-buffer is nulled out.

      • Yes, that means it always writes the whole buffer, even if you only want to copy an empty string.

      • Yes, the target might not begin with a string after the call.

   3. A file might contain nulls. Also, the random garbage beyond the copy of the file-contents might be null or not, but you shouldn't assume, even if you were allowed to access it at all.
      Should you abandon reading it into a string, consider leaving standard C and memory-mapping instead.

2. Java lacks unsigned types. If a value cannot ever be negative, consider whether one makes sense.

3. size_t is the type designed for object sizes and thus also array-counts, being guaranteed to be big enough and supposed not to be too excessive.

4. Const-correctness is important for letting the compiler help find errors.

   Thus if a pointee is never modified by design, let the type reflect it. Doing so for function-arguments makes the function more broadly applicable.

5. Avoid casting. Casting is telling the compiler to blindly trust you to get it right.

   Especially, never cast a void-pointer to/from another data-pointer, as that allows you to break const-correctness, like in comparator(). Luckily, though the code invites UB, you don't actually modify the pointee.

6. Avoid sizeof(TYPE). This duplicated type-info is impossible for the compiler to check, and often needs careful manual checking.
   sizeof *pointer couples the size to the target, avoiding those problems. It is much more refactoring and general maintenance friendly.

   Also see Do I cast the result of malloc? No.

7. C knows struct-assignment. Use it instead of memcpy() for example in find_and_remove_min().

8. Java numbers and pointers have no truth-value. C ones do, as truthy is defined as value != 0, and literal zero in pointer-context is a null pointer constant. A true boolean type was only added in C99. Don't be shy to take advantage.

9. calculate_prob() doesn't calculate probabilities. It counts occurrences, creating a histogram.

10. There is a dedicated function for writing a string to a file: fputs().

11. putc() expects an int, which it internally casts to unsigned char before output. Casting the argument to char yourself does not help, but at least it does not hinder either.

12. Consider extracting most of main() into separate functions. Just validate the arguments, open files, and call out for the rest after.

Answer 2

memcpy(node, minNode, sizeof(Node));

Hmm, doesn't C let you assign structures? *node = *minNode;

---

Use const where you can.

---

Don't compare against NULL. Just use if(p) or if(!p);

---

return is not a function call. Don't put superfluous parenthesis around the value to be returned.

---

I see you are already aware of some good things, like initializing variable when declared, not declaring them 'till you're ready, and using const with pointers for the input. 😀