Unnamed

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

#include <arpa/inet.h>

// copyright of capisce

uint32_t read_uint32(FILE *fp)
{
    int32_t value;
    fread(&value, 4, 1, fp);
    return ntohl(value);
}

uint16_t read_uint16(FILE *fp)
{
    uint16_t value;
    fread(&value, 2, 1, fp);
    return ntohs(value);
}

typedef int (*max_heap_less_than_func)(void *a, void *b);

typedef struct max_heap
{
    void **data;
    int size;
    max_heap_less_than_func less_than;
} max_heap;

void max_heap_init(max_heap *heap, max_heap_less_than_func less_than)
{
    heap->data = malloc(0);
    heap->size = 0;
    heap->less_than = less_than;
}

void max_heap_destroy(max_heap *heap)
{
    free(heap->data);
    heap->data = 0;
    heap->size = 0;
}

void max_heap_swap(void **a, void **b)
{
    void *temp = *a;
    *a = *b;
    *b = temp;
}

void max_heap_insert(max_heap *heap, void *node)
{
    heap->size++;
    heap->data = realloc(heap->data, heap->size * sizeof(void *));

    int index = heap->size - 1;
    heap->data[index] = node;

    while (index > 0) {
        int parent = ((index+1) / 2) - 1;

        if (!heap->less_than(heap->data[parent], heap->data[index]))
            break;

        max_heap_swap(&heap->data[parent], &heap->data[index]);

        index = parent;
    }
}

void max_heapify(max_heap *heap, int index)
{
    int right_child = (index + 1) * 2;
    int left_child = right_child - 1;

    int largest = index;

    if (left_child < heap->size && heap->less_than(heap->data[largest], heap->data[left_child]))
        largest = left_child;

    if (right_child < heap->size && heap->less_than(heap->data[largest], heap->data[right_child]))
        largest = right_child;

    if (largest != index) {
        max_heap_swap(&heap->data[index], &heap->data[largest]);
        max_heapify(heap, largest);
    }
}

void *max_heap_remove(max_heap *heap)
{
    if (heap->size == 0)
        return 0;

    void *node = heap->data[0];

    heap->size--;
    heap->data[0] = heap->data[heap->size];
    heap->data = realloc(heap->data, heap->size * sizeof(void *));

    if (heap->size > 1)
        max_heapify(heap, 0);

    return node;
}

typedef struct huffman_node
{
    uint8_t value;
    uint32_t frequency;

    struct huffman_node *child[2];
} huffman_node;

int huffman_node_less_than(void *a, void *b)
{
    huffman_node *ha = (huffman_node *)a;
    huffman_node *hb = (huffman_node *)b;

    if (ha->frequency == hb->frequency)
        return ha->value > hb->value;

    return ha->frequency > hb->frequency;
}

huffman_node *huffman_node_create(uint8_t value, uint32_t frequency)
{
    huffman_node *node = (huffman_node *)malloc(sizeof(huffman_node));
    node->value = value;
    node->frequency = frequency;
    node->child[0] = 0;
    node->child[1] = 0;
    return node;
}

huffman_node *huffman_node_combine(huffman_node *a, huffman_node *b)
{
    huffman_node *node = (huffman_node *)malloc(sizeof(huffman_node));
    node->frequency = a->frequency + b->frequency;
    int index = huffman_node_less_than((void *)a, (void *)b);
    node->child[index] = a;
    node->child[!index] = b;
    node->value = node->child[node->child[0]->value > node->child[1]->value]->value;
    return node;
}

typedef struct bit_input_stream
{
    FILE *fp;
    int remaining;
    uint8_t current;
} bit_input_stream;

void bit_input_stream_init(bit_input_stream *stream, FILE *fp)
{
    stream->fp = fp;
    stream->remaining = 0;
    stream->current = 0;
}

int bit_input_stream_next(bit_input_stream *stream)
{
    if (stream->remaining == 0) {
        fread(&stream->current, 1, 1, stream->fp);
        stream->remaining = 8;
    }

    stream->remaining--;
    return (stream->current >> stream->remaining) & 1;
}

char decode_next(huffman_node *tree, bit_input_stream *stream)
{
    while (tree->child[0] != 0)
        tree = tree->child[bit_input_stream_next(stream)];

    return tree->value;
}

void huffman_node_free(huffman_node *node)
{
    for (int i = 0; i < 2; ++i)
        if (node->child[i])
            huffman_node_free(node->child[i]);
    free(node);
}

int main(int argc, char **argv)
{
    if (argc < 2) {
        fprintf(stderr, "Usage: %s filename\n", argv[0]);
        return -1;
    }

    FILE *fp = fopen(argv[1], "r");

    if (!fp) {
        fprintf(stderr, "Couldn't open %s, aborting\n", argv[1]);
        return -1;
    }

    uint32_t decoded_length = read_uint32(fp);

    max_heap heap;
    max_heap_init(&heap, huffman_node_less_than);

    for (int i = 0; i < 256; ++i)
        max_heap_insert(&heap, huffman_node_create(i, read_uint16(fp)));

    huffman_node *tree;

    for (;;) {
        tree = max_heap_remove(&heap);

        huffman_node *next = max_heap_remove(&heap);
        if (next == 0)
            break;

        max_heap_insert(&heap, huffman_node_combine(tree, next));
    }

    max_heap_destroy(&heap);

    bit_input_stream stream;
    bit_input_stream_init(&stream, fp);

    char *result = malloc(decoded_length + 1);

    for (int i = 0; i < decoded_length; ++i)
        result[i] = decode_next(tree, &stream);

    result[decoded_length] = '\0';

    printf("%s", result);

    huffman_node_free(tree);

    free(result);

    fclose(fp);

    return 0;
}