doesnt work

3 files changed, 268 insertions, 64 deletions

diff --git a/build.sh b/build.sh
index 680c10a..94427a6 100755
--- a/build.sh
+++ b/build.sh
@@ -3,4 +3,4 @@
 set -xe
 
 gcc -o encode encode.c -Wall -Wextra -pedantic -g
-# gcc -o decode decode.c -Wall -Wextra -pedantic -g
+gcc -o decode decode.c -Wall -Wextra -pedantic -g
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);
+}
diff --git a/encode.c b/encode.c
index 9139c06..5a03f92 100644
--- a/encode.c
+++ b/encode.c
@@ -2,7 +2,6 @@
 #include <stdlib.h>
 #include <string.h>
 #include <stdbool.h>
-#include <assert.h>
 
 typedef struct node {
     bool is_char;
@@ -18,8 +17,10 @@ typedef struct node {
     struct node *parent;
 } node_t;
 
-void node_char_init(node_t *node, size_t ref, char ch);
-void node_link_init(node_t *node, node_t* left, node_t* right);
+node_t *node_char_create(char ch, size_t ref);
+node_t *node_link_create(node_t* left, node_t* right);
+void node_free(node_t *root);
+void node_print(node_t *root, int indent);
 
 // void liner_insert(void base[.size * .nmemb + 1],
 //                   size_t nmemb, size_t size, void *el,
@@ -27,36 +28,39 @@ void node_link_init(node_t *node, node_t* left, node_t* right);
 void liner_insert(void *base, size_t nmemb, size_t size, void *el, int (*compar)(const void *, const void *));
 int compare_nodes(const void *p1, const void *p2);
 
-void free_encoding_table();
 void wb_flush(size_t nmemb);
+void gen_tree();
 
-void gen_tree(FILE *fp);
-size_t write_tree_shape(node_t *root);
 size_t write_tree_data(node_t *root);
-
+size_t write_tree_shape(node_t *root);
 size_t write_encoded(node_t *root);
-void encode(FILE *fp);
+void encode();
 
-
-size_t POOL_CAP = 512;
-node_t *pool;
-size_t pool_sz;
+FILE *in;
+FILE *out;
 
 size_t WRITE_BUF_CAP = 512;
 char *write_buf;
 
+node_t *root;
 node_t *encoding_table[256] = {0};
 
-void encode(FILE *fp)
+void encode()
 {
     // write tree //
     wb_flush(1); // flush amount of bits (written in gen_tree())
-    wb_flush(write_tree_shape(&pool[pool_sz-1])/8 + 1);
-    wb_flush(write_tree_data(&pool[pool_sz-1]));
+    wb_flush(write_tree_data(root));
+    wb_flush(write_tree_shape(root)/8 + 1);
+
+    // write amount of characters
+    fseek(in, 0, SEEK_END);
+    size_t text_len = ftell(in);
+    rewind(in);
+    fwrite(&text_len, sizeof(size_t), 1, out);
 
     // encode //
     char ch;
-    while((ch = fgetc(fp)) != EOF) {
+    while(fread(&ch, sizeof(char), 1, in) > 0) {
         if(encoding_table[ch] == NULL) {
             fprintf(stderr, "Character %c not found encoding table\n", ch);
             exit(1);
@@ -66,56 +70,59 @@ void encode(FILE *fp)
     wb_flush(write_encoded(NULL)/8+1);
 }
 
-int main(int argc, char **argv)
+int main(void)
 {
-    if(argc != 2) {
-        fprintf(stderr, "ERROR: Not enough command line arguments\n");
-        exit(1);
-    }
-
     write_buf = malloc(sizeof(char) * WRITE_BUF_CAP);
-    pool = malloc(sizeof(node_t) * POOL_CAP);
 
-    FILE *fp = fopen(argv[1], "rb");
-    if(!fp) {
-        fprintf(stderr, "ERROR: Could not open file %s\n", argv[1]);
-        exit(1);
-    }
+    in = stdin;
+    out = stdout;
+
+    // in = fopen(argv[1], "rb");
+    // if(!in) {
+    //     fprintf(stderr, "ERROR: Could not open file %s\n", argv[1]);
+    //     exit(1);
+    // }
 
-    gen_tree(fp);
-    encode(fp);
+    // out = fopen(argv[1], "wb");
+    // if(!out) {
+        // fprintf(stderr, "ERROR Could not open file %s\n", argv[1]);
+        // exit(1);
+    // }
 
-    free_encoding_table();
-    free(pool);
+    gen_tree();
+    encode();
+
+    // node_print(root, 0);
+    node_free(root);
     free(write_buf);
 
-    fclose(fp);
+    // fclose(in);
+    // fclose(out);
     return 0;
 }
 
-void gen_tree(FILE *fp)
+void gen_tree()
 {
     node_t *nodes[256];
     size_t nodes_sz = 0;
 
-    size_t char_counts[256] = {0};
+    size_t char_refs[256] = {0};
     char mem[1024] = {0}; size_t sz;
 
     // load char counts
-    while((sz = fread(mem, sizeof(char), 1024, fp)) != 0)
+    while((sz = fread(mem, sizeof(char), 1024, in)) != 0)
     {
         for(size_t i = 0; i < sz; i++) {
-            char_counts[(size_t)mem[i]]++;
+            char_refs[(size_t)mem[i]]++;
         }
     }
-    rewind(fp);
+    rewind(in);
 
     // make the tree
     for(int i = 0; i < 256; i++) {
-        if(char_counts[i] <= 0) continue;
+        if(char_refs[i] <= 0) continue;
 
-        nodes[nodes_sz] = malloc(sizeof(node_t));
-        node_char_init(nodes[nodes_sz], char_counts[i], (char)i);
+        nodes[nodes_sz] = node_char_create((char)i, char_refs[i]);
         encoding_table[i] = nodes[nodes_sz];
         nodes_sz++;
     }
@@ -123,18 +130,13 @@ void gen_tree(FILE *fp)
     qsort(nodes, nodes_sz, sizeof(node_t *), compare_nodes);
 
     // save the amount of bits
-    write_buf[0] = nodes_sz * 2 - 1;
+    write_buf[0] = (char)nodes_sz;
 
     // pair last 2 elements and do linear sort
-    for(pool_sz = 0; nodes_sz != 1; nodes_sz--, pool_sz++)
+    for(; nodes_sz != 1; nodes_sz--)
     {
-        if(pool_sz >= POOL_CAP) {
-            fprintf(stderr, "ERROR: POOL_CAP reached, please re-run the program with a bigger POOL_CAP\n");
-            exit(1);
-        }
-
-        node_link_init(&pool[pool_sz], nodes[nodes_sz-1], nodes[nodes_sz-2]);
-        liner_insert(nodes, nodes_sz-2, sizeof(node_t *), &pool[pool_sz], compare_nodes);
+        root = node_link_create(nodes[nodes_sz-1], nodes[nodes_sz-2]);
+        liner_insert(nodes, nodes_sz-2, sizeof(node_t *), root, compare_nodes);
     }
 }
 
@@ -160,7 +162,7 @@ size_t write_tree_shape(node_t *root)
     static size_t bits = 0;
     if(root == NULL) return bits;
 
-    write_buf[bits/8] |= root->is_char << (8 - (bits%8));
+    write_buf[bits/8] |= root->is_char << (bits % 8);
     bits++;
 
     if(bits/8 == WRITE_BUF_CAP) {
@@ -195,19 +197,10 @@ size_t write_tree_data(node_t *root)
 
 void wb_flush(size_t nmemb)
 {
-    fwrite(write_buf, sizeof(char), nmemb, stdout);
+    fwrite(write_buf, sizeof(char), nmemb, out);
     memset(write_buf, 0, sizeof(char) * WRITE_BUF_CAP);
 }
 
-void free_encoding_table()
-{
-    for(int i = 0; i < 256; i++) {
-        if(encoding_table[i] != NULL) {
-            free(encoding_table[i]);
-        }
-    }
-}
-
 int compare_nodes(const void *p1, const void *p2)
 {
     return (*(node_t **)p2)->references - (*(node_t **)p1)->references;
@@ -235,19 +228,26 @@ void liner_insert(void *base, size_t nmemb, size_t size, void *el, int (*compar)
     memcpy(base + (nmemb * size), &el, size);
 }
 
-void node_char_init(node_t *node, size_t ref, char ch)
+node_t *node_char_create(char ch, size_t ref)
 {
+    node_t *node = malloc(sizeof(node_t));
+
     node->is_char = true;
     node->ch = ch;
     node->references = ref;
     node->parent = NULL;
     node->left = NULL;
     node->right = NULL;
+
+    return node;
 }
 
-void node_link_init(node_t *node, node_t* left, node_t* right)
+node_t *node_link_create(node_t* left, node_t* right)
 {
+    node_t *node = malloc(sizeof(node_t));
+
     node->is_char = false;
+    node->ch = 0;
     node->references = left->references + right->references;
     node->parent = NULL;
     node->left = left;
@@ -257,4 +257,28 @@ void node_link_init(node_t *node, node_t* left, node_t* right)
     right->parent = node;
     left->direction = 0;
     right->direction = 1;
+
+    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);
 }