1 files changed, 180 insertions, 0 deletions
diff --git a/decode.c b/decode.c
new file mode 100644
index 0000000..9a5eea8
--- /dev/null
+++ b/decode.c
@@ -0,0 +1,180 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+typedef struct node {
+    bool is_char;
+    char ch;
+
+    struct node *left;
+    struct node *right;
+} node_t;
+
+node_t *node_char_create(char ch);
+// left right flipped because tree has to be inverted for some reason
+node_t *node_link_create(node_t* right, node_t* left);
+void node_free(node_t *root);
+void node_print(node_t *root, int indent);
+
+size_t read_tree_data(char *buf);
+node_t *read_tree_shape(char *char_buf, size_t bits);
+char read_decoded(node_t *root);
+void decode();
+
+FILE *in;
+FILE *out;
+
+node_t *root;
+
+char read_decoded(node_t *root)
+{
+    static size_t i = 0;
+    static char cur_byte = 0;
+
+    if(root == NULL) {
+        fprintf(stderr, "ERROR: real_decoded: root cannot be NULL");
+        exit(1);
+    }
+
+    if(root->is_char) return root->ch;
+
+    if(i % 8 == 0) {
+        if(fread(&cur_byte, sizeof(char), 1, in) <= 0) {
+            fprintf(stderr, "ERROR: An error has occured while reading the encoded bytes\n");
+            exit(1);
+        }
+        i = 0;
+    }
+
+    char bit = (cur_byte >> i++) & 1;
+    if(bit == 0) {
+        return read_decoded(root->left);
+    }
+
+    return read_decoded(root->right);
+}
+
+void decode()
+{
+    char buf[256] = {0};
+    size_t chars = read_tree_data(buf);
+    root = read_tree_shape(buf, chars*2 - 1);
+
+    size_t text_len;
+    fread(&text_len, sizeof(size_t), 1, in);
+
+    for(int i = 0; i < text_len; i++) {
+        char ch = read_decoded(root);
+        fwrite(&ch, sizeof(char), 1, out);
+    }
+}
+
+int main(void)
+{
+    in = stdin;
+    out = stdout;
+
+    // in = fopen(argv[1], "rb");
+    // if(!in) {
+    //     fprintf(stderr, "ERROR: Could not open file %s\n", argv[1]);
+    //     exit(1);
+    // }
+
+    // out = fopen(argv[1], "wb");
+    // if(!out) {
+        // fprintf(stderr, "ERROR Could not open file %s\n", argv[1]);
+        // exit(1);
+    // }
+
+    decode();
+
+    node_free(root);
+
+    // fclose(in);
+    // fclose(out);
+    return 0;
+}
+
+size_t read_tree_data(char *buf)
+{
+    unsigned int chars = 0;
+    fread(&chars, sizeof(char), 1, in);
+    fread(buf, sizeof(char), chars, in);
+    return chars;
+}
+
+node_t *read_tree_shape(char *char_buf, size_t bits)
+{
+    static size_t buf_i = 0;
+    static size_t read_bits = 0;
+    static char cur_byte = 0;
+
+    if(read_bits == bits) {
+        fprintf(stderr, "ERROR: An error has occred while reading the tree shape (read_bits == bits)");
+        exit(1);
+    }
+
+    if(read_bits % 8 == 0) {
+        if(fread(&cur_byte, sizeof(char), 1, in) <= 0) {
+            fprintf(stderr, "ERROR: An error has occured while reading the tree shape\n");
+            exit(1);
+        }
+    }
+
+    node_t *root;
+
+    char bit = (cur_byte >> (read_bits++ % 8)) & 1;
+    if(bit == 0) {
+        root = node_link_create(read_tree_shape(char_buf, bits),
+                                read_tree_shape(char_buf, bits));
+    } else {
+        root = node_char_create(char_buf[buf_i++]);
+    }
+
+    return root;
+}
+
+node_t *node_char_create(char ch)
+{
+    node_t *node = malloc(sizeof(node_t));
+
+    node->is_char = true;
+    node->ch = ch;
+    node->left = NULL;
+    node->right = NULL;
+
+    return node;
+}
+node_t *node_link_create(node_t* right, node_t* left)
+{
+    node_t *node = malloc(sizeof(node_t));
+
+    node->is_char = false;
+    node->ch = 0;
+    node->left = left;
+    node->right = right;
+
+    return node;
+}
+
+void node_free(node_t *root)
+{
+    if(root == NULL) return;
+
+    node_free(root->left);
+    node_free(root->right);
+
+    free(root);
+}
+
+void node_print(node_t *root, int indent)
+{
+    if(root == NULL) return;
+
+    for(int i = 0; i < indent; i++) fprintf(stderr, " ");
+
+    fprintf(stderr, "%d '%c'\n", root->is_char, (root->ch == 0) ? '-' : root->ch);
+
+    node_print(root->left, indent + 2);
+    node_print(root->right, indent + 2);
+}