diff options
Diffstat (limited to 'encode.c')
| -rw-r--r-- | encode.c | 150 |
1 files changed, 87 insertions, 63 deletions
@@ -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); } |