huffman-encode.c 9.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470
  1. /* huffman-encode.c */
  2. /*
  3. This file is part of the AVR-Huffman.
  4. Copyright (C) 2009 Daniel Otte (daniel.otte@rub.de)
  5. This program is free software: you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation, either version 3 of the License, or
  8. (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program. If not, see <http://www.gnu.org/licenses/>.
  15. */
  16. #include <stdio.h>
  17. #include <string.h>
  18. #include <stdint.h>
  19. #include <stdlib.h>
  20. #define DEBUG 0
  21. #define XDEBUG 0
  22. typedef struct{
  23. uint8_t depth;
  24. uint16_t value;
  25. uint32_t weight;
  26. void* left;
  27. void* right;
  28. } node_t;
  29. typedef struct{
  30. uint16_t value;
  31. unsigned depth;
  32. void* encoding;
  33. } item_t;
  34. typedef struct{
  35. uint8_t initialized;
  36. item_t* item;
  37. void* parent;
  38. void* left;
  39. void* right;
  40. } node2_t;
  41. uint32_t histogram[256];
  42. node_t* pool[256+1];
  43. unsigned poolsize;
  44. unsigned item_count;
  45. node_t* tree;
  46. node_t* treenodes;
  47. unsigned treeindex=0;
  48. item_t* itemlist;
  49. unsigned itemindex=0;
  50. node2_t* node2list=NULL;
  51. unsigned node2list_index=0;
  52. item_t* valueencode[256];
  53. item_t* eof_encoding;
  54. void reset_histogram(void){
  55. memset(histogram, 0, 256*sizeof(uint32_t));
  56. }
  57. void build_histogram(char* fname){
  58. FILE* f;
  59. int t;
  60. f = fopen(fname, "r");
  61. while((t=fgetc(f))!=EOF){
  62. histogram[(uint8_t)t&0xFF]++;
  63. }
  64. fclose(f);
  65. }
  66. void build_pool(void){
  67. unsigned i,j;
  68. memset(pool, 0, 256*sizeof(node_t*));
  69. for(i=0,j=0;i<256;++i){
  70. if(histogram[i]==0)
  71. continue;
  72. pool[j] = malloc(sizeof(node_t));
  73. if(pool[j]==NULL){
  74. fprintf(stderr,"out of memory error (%d)!\n", __LINE__);
  75. exit(-1);
  76. }
  77. pool[j]->depth = 0;
  78. pool[j]->value = i;
  79. pool[j]->left = NULL;
  80. pool[j]->right = NULL;
  81. pool[j]->weight = histogram[i];
  82. j++;
  83. }
  84. pool[j] = malloc(sizeof(node_t));
  85. if(pool[j]==NULL){
  86. fprintf(stderr,"out of memory error (%d)!\n", __LINE__);
  87. exit(-1);
  88. }
  89. pool[j]->depth = 0;
  90. pool[j]->value = 0xFFFF;
  91. pool[j]->left = NULL;
  92. pool[j]->right = NULL;
  93. pool[j]->weight = 1;
  94. j++;
  95. poolsize = j;
  96. item_count = j;
  97. }
  98. void find_lightest2(unsigned* a, unsigned* b, unsigned* depth){
  99. unsigned ia=0;
  100. unsigned ib=0;
  101. uint32_t wa, wb;
  102. unsigned i;
  103. wa = wb = 0xFFFFFFFF;
  104. for(i=0; i<poolsize; ++i){
  105. if(pool[i]==NULL)
  106. continue;
  107. if(wa>=pool[i]->weight){
  108. wb = wa;
  109. ib = ia;
  110. wa = pool[i]->weight;
  111. ia = i;
  112. }else{
  113. if(wb>pool[i]->weight){
  114. wb = pool[i]->weight;
  115. ib = i;
  116. }
  117. }
  118. }
  119. if(wb == 0xFFFFFFFF || wa == 0xFFFFFFFF){
  120. fprintf(stderr, "Error while searching!\n");
  121. exit(-2);
  122. }
  123. if(pool[ia]->depth <= pool[ib]->depth){
  124. *a = ia;
  125. *b = ib;
  126. *depth = pool[ib]->depth;
  127. } else {
  128. *a = ib;
  129. *b = ia;
  130. *depth = pool[ia]->depth;
  131. }
  132. }
  133. void init_tree(void){
  134. treenodes = malloc((poolsize-1)*sizeof(node_t));
  135. if(treenodes==NULL){
  136. fprintf(stderr,"out of memory error (%d)!\n", __LINE__);
  137. exit(-1);
  138. }
  139. #if XDEBUG
  140. printf("treenodes := %p\n", (void*)treenodes);
  141. #endif
  142. }
  143. void update_tree(void){
  144. if(poolsize<2)
  145. return;
  146. unsigned a,b, depth;
  147. find_lightest2(&a,&b,&depth);
  148. #if XDEBUG
  149. printf("joining %d and %d\n", a,b);
  150. #endif
  151. treenodes[treeindex].depth = depth+1;
  152. treenodes[treeindex].weight = pool[a]->weight + pool[b]->weight;
  153. treenodes[treeindex].left = (pool[a]);
  154. treenodes[treeindex].right = (pool[b]);
  155. #if XDEBUG
  156. printf(" idx = %d\n self = %p\n depth = %d\n weight = %d\n"
  157. " left = %p\n right = %p\n",
  158. treeindex, (void*)&(treenodes[treeindex]), treenodes[treeindex].depth,
  159. treenodes[treeindex].weight, treenodes[treeindex].left,
  160. treenodes[treeindex].right);
  161. #endif
  162. pool[a] = &(treenodes[treeindex]);
  163. pool[b] = pool[poolsize-1];
  164. pool[poolsize-1] = NULL;
  165. --poolsize;
  166. ++treeindex;
  167. }
  168. void build_tree(void){
  169. while(poolsize>1){
  170. update_tree();
  171. }
  172. tree = &(treenodes[treeindex-1]);
  173. }
  174. void free_leaf(node_t* node){
  175. if(node->depth==0){
  176. free(node);
  177. }else{
  178. free_leaf(node->left);
  179. free_leaf(node->right);
  180. }
  181. }
  182. void free_tree(void){
  183. free_leaf(tree);
  184. free(treenodes);
  185. tree = NULL;
  186. }
  187. void init_itemlist(void){
  188. itemlist = calloc((item_count),sizeof(item_t));
  189. if(itemlist==NULL){
  190. fprintf(stderr,"out of memory error (%d)!\n", __LINE__);
  191. exit(-1);
  192. }
  193. }
  194. void update_itemlist(node_t* node, unsigned depth){
  195. if(node->depth==0){
  196. itemlist[itemindex].value = node->value;
  197. itemlist[itemindex].depth = depth;
  198. ++itemindex;
  199. } else {
  200. update_itemlist(node->left, depth+1);
  201. update_itemlist(node->right, depth+1);
  202. }
  203. }
  204. void build_itemlist(void){
  205. update_itemlist(tree, 0);
  206. }
  207. int item_compare_depth(const void* a, const void* b){
  208. if(((item_t*)a)->value==0xFFFF)
  209. return 1;
  210. if(((item_t*)b)->value==0xFFFF)
  211. return -1;
  212. return ((item_t*)a)->depth - ((item_t*)b)->depth;
  213. }
  214. void sort_itemlist(void){
  215. qsort(itemlist, item_count, sizeof(item_t), item_compare_depth);
  216. }
  217. #define PREFIX_SIZE_B 32
  218. void prefix_increment(uint8_t* prefix){
  219. uint8_t i;
  220. for(i=0; i<PREFIX_SIZE_B; ++i){
  221. prefix[i] += 1;
  222. if(prefix[i]!=0)
  223. return;
  224. }
  225. }
  226. void prefix_shiftleft(uint8_t* prefix){
  227. uint8_t i;
  228. uint8_t c[2]={0,0};
  229. uint8_t ci=0;
  230. for(i=0; i<PREFIX_SIZE_B; ++i){
  231. c[ci] = (prefix[i])>>7;
  232. prefix[i]<<=1;
  233. ci ^= 1;
  234. prefix[i]|=c[ci];
  235. }
  236. }
  237. void gen_itemencoding(void){
  238. uint8_t prefix[PREFIX_SIZE_B];
  239. memset(prefix, 0, PREFIX_SIZE_B);
  240. unsigned depth=0;
  241. unsigned depth_B=0;
  242. unsigned i,j;
  243. for(i=0; i<item_count; ++i){
  244. if(depth!=itemlist[i].depth){
  245. for(j=depth; j<itemlist[i].depth; ++j)
  246. prefix_shiftleft(prefix);
  247. depth = itemlist[i].depth;
  248. depth_B = (depth+7)/8;
  249. }
  250. itemlist[i].encoding=malloc(depth_B);
  251. if(itemlist[i].encoding==NULL){
  252. fprintf(stderr,"out of memory error (%d)!\n", __LINE__);
  253. exit(-1);
  254. }
  255. memcpy(itemlist[i].encoding, prefix, depth_B);
  256. prefix_increment(prefix);
  257. }
  258. }
  259. void add_item2(item_t* item){
  260. int i;
  261. uint8_t t;
  262. node2_t* current;
  263. current = node2list;
  264. char c;
  265. c = item->value;
  266. // printf(" %2.2X (%c) => ", c, (c>32&&c<128)?c:' ');
  267. for(i=item->depth-1; i>=0; --i){
  268. t = (((uint8_t*)(item->encoding))[i/8])&(1<<(i%8));
  269. if(current->initialized==0){
  270. current->initialized=1;
  271. current->parent = NULL;
  272. current->item = NULL;
  273. current->left = NULL;
  274. current->right = NULL;
  275. node2list_index++;
  276. }
  277. if(t==0){
  278. // putchar('0');
  279. if(current->left){
  280. current = current->left;
  281. } else {
  282. current->left = &(node2list[node2list_index++]);
  283. ((node2_t*)(current->left))->parent = current;
  284. current = current->left;
  285. current->initialized=1;
  286. current->item=NULL;
  287. }
  288. } else {
  289. // putchar('1');
  290. if(current->right){
  291. current = current->right;
  292. } else {
  293. current->right = &(node2list[node2list_index++]);
  294. ((node2_t*)(current->right))->parent = current;
  295. current = current->right;
  296. current->initialized=1;
  297. current->item=NULL;
  298. }
  299. }
  300. }
  301. current->item = item;
  302. current->left = NULL;
  303. current->right = NULL;
  304. // printf("\n");
  305. }
  306. void gen_tree2(void){
  307. unsigned i;
  308. node2list = calloc(2*item_count-1, sizeof(node2_t));
  309. #if XDEBUG
  310. printf("item_count = %d\n", item_count);
  311. #endif
  312. if(node2list==NULL){
  313. fprintf(stderr,"out of memory error (%d)!\n", __LINE__);
  314. exit(-1);
  315. }
  316. for(i=0;i<item_count;++i){
  317. add_item2(&(itemlist[i]));
  318. }
  319. }
  320. void bit_writer(FILE* f, uint8_t bit, uint8_t flush){
  321. static uint8_t buffer;
  322. static uint8_t buffer_index=0;
  323. if(flush){
  324. for(;buffer_index<8;++buffer_index)
  325. buffer<<=1;
  326. }
  327. if(buffer_index==8){
  328. fputc(buffer, f);
  329. buffer_index=0;
  330. }
  331. buffer<<=1;
  332. buffer|=bit?1:0;
  333. buffer_index++;
  334. }
  335. void encoding_writer(FILE* f, uint8_t* data, uint16_t length){
  336. int i;
  337. if(data==NULL)
  338. bit_writer(f, 0, 1);
  339. for(i=length-1;i>=0;--i){
  340. bit_writer(f,data[i/8]&(1<<(i%8)),0);
  341. }
  342. }
  343. void build_valueencode(void){
  344. unsigned i;
  345. memset(valueencode, 0, 256*sizeof(void*));
  346. for(i=0; i<item_count-1; ++i){
  347. valueencode[itemlist[i].value] = &(itemlist[i]);
  348. }
  349. eof_encoding = &(itemlist[i]);
  350. }
  351. void write_tree(FILE* f){
  352. unsigned i,j;
  353. unsigned last=0;
  354. unsigned last_depth=1;
  355. fputc(0xc0, f);
  356. fputc(0xde + (item_count>>8), f);
  357. fputc(item_count,f);
  358. for(i=0; i<item_count; ++i){
  359. if(itemlist[i].depth!=last_depth){
  360. if(i-last>=255){
  361. fputc(255, f);
  362. fputc(i-last-255, f);
  363. } else {
  364. fputc(i-last, f);
  365. }
  366. for(j=last; j<i; ++j){
  367. fputc(itemlist[j].value, f);
  368. }
  369. for(j=last_depth+1; j<itemlist[i].depth; ++j)
  370. fputc(0, f);
  371. last=i;
  372. last_depth=itemlist[i].depth;
  373. }
  374. }
  375. if(i-last>=255){
  376. fputc(255, f);
  377. fputc(i-last-255, f);
  378. } else {
  379. fputc(i-last, f);
  380. }
  381. for(j=last; j<i; ++j){
  382. fputc(itemlist[j].value, f);
  383. }
  384. }
  385. void compress_file(FILE* fin, FILE* fout){
  386. int t;
  387. while((t=fgetc(fin))!=EOF){
  388. t = (uint8_t)t;
  389. if(valueencode[t]==NULL){
  390. fprintf(stderr,"no encoding for %2.2X (%c) found!\n",t,(t>32&&t<128)?t:' ');
  391. exit(-3);
  392. }
  393. encoding_writer(fout, valueencode[t]->encoding, valueencode[t]->depth);
  394. };
  395. encoding_writer(fout, eof_encoding->encoding, eof_encoding->depth);
  396. encoding_writer(fout, NULL, 0);
  397. }
  398. void compress_huffman(char * filename_in, char * filename_out){
  399. FILE* fin;
  400. FILE* fout;
  401. reset_histogram();
  402. build_histogram(filename_in);
  403. build_pool();
  404. init_tree();
  405. build_tree();
  406. init_itemlist();
  407. build_itemlist();
  408. free_tree();
  409. sort_itemlist();
  410. gen_itemencoding();
  411. gen_tree2();
  412. build_valueencode();
  413. fin = fopen(filename_in, "r");
  414. fout = fopen(filename_out, "w");
  415. write_tree(fout);
  416. compress_file(fin, fout);
  417. fclose(fin);
  418. fclose(fout);
  419. }
  420. int main(int argc, char** argv){
  421. char filename_out[strlen(argv[1])+20];
  422. strcpy(filename_out, argv[1]);
  423. strcat(filename_out, ".hfm");
  424. compress_huffman(argv[1],filename_out);
  425. return 0;
  426. }