/* huffman-encode.c */ /* This file is part of the AVR-Huffman. Copyright (C) 2009 Daniel Otte (daniel.otte@rub.de) This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include #include #include #include #define DEBUG 0 #define XDEBUG 0 typedef struct{ uint8_t depth; uint16_t value; uint32_t weight; void* left; void* right; } node_t; typedef struct{ uint16_t value; unsigned depth; void* encoding; } item_t; typedef struct{ uint8_t initialized; item_t* item; void* parent; void* left; void* right; } node2_t; uint32_t histogram[256]; node_t* pool[256+1]; unsigned poolsize; unsigned item_count; node_t* tree; node_t* treenodes; unsigned treeindex=0; item_t* itemlist; unsigned itemindex=0; node2_t* node2list=NULL; unsigned node2list_index=0; item_t* valueencode[256]; item_t* eof_encoding; void reset_histogram(void){ memset(histogram, 0, 256*sizeof(uint32_t)); } void build_histogram(char* fname){ FILE* f; int t; f = fopen(fname, "r"); while((t=fgetc(f))!=EOF){ histogram[(uint8_t)t&0xFF]++; } fclose(f); } void build_pool(void){ unsigned i,j; memset(pool, 0, 256*sizeof(node_t*)); for(i=0,j=0;i<256;++i){ if(histogram[i]==0) continue; pool[j] = malloc(sizeof(node_t)); if(pool[j]==NULL){ fprintf(stderr,"out of memory error (%d)!\n", __LINE__); exit(-1); } pool[j]->depth = 0; pool[j]->value = i; pool[j]->left = NULL; pool[j]->right = NULL; pool[j]->weight = histogram[i]; j++; } pool[j] = malloc(sizeof(node_t)); if(pool[j]==NULL){ fprintf(stderr,"out of memory error (%d)!\n", __LINE__); exit(-1); } pool[j]->depth = 0; pool[j]->value = 0xFFFF; pool[j]->left = NULL; pool[j]->right = NULL; pool[j]->weight = 1; j++; poolsize = j; item_count = j; } void find_lightest2(unsigned* a, unsigned* b, unsigned* depth){ unsigned ia=0; unsigned ib=0; uint32_t wa, wb; unsigned i; wa = wb = 0xFFFFFFFF; for(i=0; i=pool[i]->weight){ wb = wa; ib = ia; wa = pool[i]->weight; ia = i; }else{ if(wb>pool[i]->weight){ wb = pool[i]->weight; ib = i; } } } if(wb == 0xFFFFFFFF || wa == 0xFFFFFFFF){ fprintf(stderr, "Error while searching!\n"); exit(-2); } if(pool[ia]->depth <= pool[ib]->depth){ *a = ia; *b = ib; *depth = pool[ib]->depth; } else { *a = ib; *b = ia; *depth = pool[ia]->depth; } } void init_tree(void){ treenodes = malloc((poolsize-1)*sizeof(node_t)); if(treenodes==NULL){ fprintf(stderr,"out of memory error (%d)!\n", __LINE__); exit(-1); } #if XDEBUG printf("treenodes := %p\n", (void*)treenodes); #endif } void update_tree(void){ if(poolsize<2) return; unsigned a,b, depth; find_lightest2(&a,&b,&depth); #if XDEBUG printf("joining %d and %d\n", a,b); #endif treenodes[treeindex].depth = depth+1; treenodes[treeindex].weight = pool[a]->weight + pool[b]->weight; treenodes[treeindex].left = (pool[a]); treenodes[treeindex].right = (pool[b]); #if XDEBUG printf(" idx = %d\n self = %p\n depth = %d\n weight = %d\n" " left = %p\n right = %p\n", treeindex, (void*)&(treenodes[treeindex]), treenodes[treeindex].depth, treenodes[treeindex].weight, treenodes[treeindex].left, treenodes[treeindex].right); #endif pool[a] = &(treenodes[treeindex]); pool[b] = pool[poolsize-1]; pool[poolsize-1] = NULL; --poolsize; ++treeindex; } void build_tree(void){ while(poolsize>1){ update_tree(); } tree = &(treenodes[treeindex-1]); } void free_leaf(node_t* node){ if(node->depth==0){ free(node); }else{ free_leaf(node->left); free_leaf(node->right); } } void free_tree(void){ free_leaf(tree); free(treenodes); tree = NULL; } void init_itemlist(void){ itemlist = calloc((item_count),sizeof(item_t)); if(itemlist==NULL){ fprintf(stderr,"out of memory error (%d)!\n", __LINE__); exit(-1); } } void update_itemlist(node_t* node, unsigned depth){ if(node->depth==0){ itemlist[itemindex].value = node->value; itemlist[itemindex].depth = depth; ++itemindex; } else { update_itemlist(node->left, depth+1); update_itemlist(node->right, depth+1); } } void build_itemlist(void){ update_itemlist(tree, 0); } int item_compare_depth(const void* a, const void* b){ if(((item_t*)a)->value==0xFFFF) return 1; if(((item_t*)b)->value==0xFFFF) return -1; return ((item_t*)a)->depth - ((item_t*)b)->depth; } void sort_itemlist(void){ qsort(itemlist, item_count, sizeof(item_t), item_compare_depth); } #define PREFIX_SIZE_B 32 void prefix_increment(uint8_t* prefix){ uint8_t i; for(i=0; i>7; prefix[i]<<=1; ci ^= 1; prefix[i]|=c[ci]; } } void gen_itemencoding(void){ uint8_t prefix[PREFIX_SIZE_B]; memset(prefix, 0, PREFIX_SIZE_B); unsigned depth=0; unsigned depth_B=0; unsigned i,j; for(i=0; ivalue; // printf(" %2.2X (%c) => ", c, (c>32&&c<128)?c:' '); for(i=item->depth-1; i>=0; --i){ t = (((uint8_t*)(item->encoding))[i/8])&(1<<(i%8)); if(current->initialized==0){ current->initialized=1; current->parent = NULL; current->item = NULL; current->left = NULL; current->right = NULL; node2list_index++; } if(t==0){ // putchar('0'); if(current->left){ current = current->left; } else { current->left = &(node2list[node2list_index++]); ((node2_t*)(current->left))->parent = current; current = current->left; current->initialized=1; current->item=NULL; } } else { // putchar('1'); if(current->right){ current = current->right; } else { current->right = &(node2list[node2list_index++]); ((node2_t*)(current->right))->parent = current; current = current->right; current->initialized=1; current->item=NULL; } } } current->item = item; current->left = NULL; current->right = NULL; // printf("\n"); } void gen_tree2(void){ unsigned i; node2list = calloc(2*item_count-1, sizeof(node2_t)); #if XDEBUG printf("item_count = %d\n", item_count); #endif if(node2list==NULL){ fprintf(stderr,"out of memory error (%d)!\n", __LINE__); exit(-1); } for(i=0;i=0;--i){ bit_writer(f,data[i/8]&(1<<(i%8)),0); } } void build_valueencode(void){ unsigned i; memset(valueencode, 0, 256*sizeof(void*)); for(i=0; i>8), f); fputc(item_count,f); for(i=0; i=255){ fputc(255, f); fputc(i-last-255, f); } else { fputc(i-last, f); } for(j=last; j=255){ fputc(255, f); fputc(i-last-255, f); } else { fputc(i-last, f); } for(j=last; j32&&t<128)?t:' '); exit(-3); } encoding_writer(fout, valueencode[t]->encoding, valueencode[t]->depth); }; encoding_writer(fout, eof_encoding->encoding, eof_encoding->depth); encoding_writer(fout, NULL, 0); } void compress_huffman(char * filename_in, char * filename_out){ FILE* fin; FILE* fout; reset_histogram(); build_histogram(filename_in); build_pool(); init_tree(); build_tree(); init_itemlist(); build_itemlist(); free_tree(); sort_itemlist(); gen_itemencoding(); gen_tree2(); build_valueencode(); fin = fopen(filename_in, "r"); fout = fopen(filename_out, "w"); write_tree(fout); compress_file(fin, fout); fclose(fin); fclose(fout); } int main(int argc, char** argv){ char filename_out[strlen(argv[1])+20]; strcpy(filename_out, argv[1]); strcat(filename_out, ".hfm"); compress_huffman(argv[1],filename_out); return 0; }