huffman-decode.c 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265
  1. /*
  2. * =====================================================================================
  3. *
  4. * ________ .__ __ ________ ____ ________
  5. * \_____ \ __ __|__| ____ | | __\______ \ _______ _/_ |/ _____/
  6. * / / \ \| | \ |/ ___\| |/ / | | \_/ __ \ \/ /| / __ \
  7. * / \_/. \ | / \ \___| < | ` \ ___/\ / | \ |__\ \
  8. * \_____\ \_/____/|__|\___ >__|_ \/_______ /\___ >\_/ |___|\_____ /
  9. * \__> \/ \/ \/ \/ \/
  10. *
  11. * www.optixx.org
  12. *
  13. *
  14. * Version: 1.0
  15. * Created: 07/21/2009 03:32:16 PM
  16. * Author: david@optixx.org
  17. *
  18. * =====================================================================================
  19. */
  20. #include "huffman-decode.h"
  21. #include <stdint.h>
  22. #include <stdio.h>
  23. #include <string.h>
  24. #include <stdlib.h>
  25. #ifdef DEBUG
  26. #undef DEBUG
  27. #endif
  28. #define DEBUG 1
  29. #if DEBUG
  30. #include <avr/pgmspace.h>
  31. #endif
  32. #define V_NODE (-2)
  33. #define V_EOF (-1)
  34. #define PREFIX_SIZE_B 32
  35. #define ALLOC_ERROR {}
  36. #undef BLOCK_ALLOC 1
  37. typedef struct {
  38. int16_t value;
  39. void* left;
  40. void* right;
  41. } node_t;
  42. #if HUFFMAN_USE_ADDR_16
  43. void huffman_dec_init(huffman_dec_ctx_t* ctx, uint16_t(*rb_func)(uint16_t)){
  44. #else
  45. void huffman_dec_init(huffman_dec_ctx_t* ctx, uint16_t(*rb_func)(uint32_t)){
  46. #endif
  47. ctx->tree = NULL;
  48. ctx->addr = 0;
  49. ctx->read_byte = rb_func;
  50. ctx->rbuffer_index = 8;
  51. }
  52. #if HUFFMAN_USE_ADDR_16
  53. void huffman_dec_set_addr(huffman_dec_ctx_t* ctx, uint16_t addr){
  54. #else
  55. void huffman_dec_set_addr(huffman_dec_ctx_t* ctx, uint32_t addr){
  56. #endif
  57. ctx->addr = addr;
  58. }
  59. static inline void prefix_increment(uint8_t* prefix){
  60. uint8_t i;
  61. for(i=0; i<PREFIX_SIZE_B; ++i){
  62. prefix[i] += 1;
  63. if(prefix[i]!=0)
  64. return;
  65. }
  66. }
  67. static inline void prefix_shiftleft(uint8_t* prefix){
  68. uint8_t i;
  69. uint8_t c[2]={0,0};
  70. uint8_t ci=0;
  71. for(i=0; i<PREFIX_SIZE_B; ++i){
  72. c[ci] = (prefix[i])>>7;
  73. prefix[i]<<=1;
  74. ci ^= 1;
  75. prefix[i]|=c[ci];
  76. }
  77. }
  78. static inline void set_last_to_eof(node_t* start){
  79. node_t* current = start;
  80. while(current->value==V_NODE){
  81. current=current->right;
  82. }
  83. current->value=V_EOF;
  84. }
  85. #if DEBUG
  86. void print_tree(node_t* node){
  87. if(node->value==V_NODE){
  88. printf("\n%p --> node->left=%p node->right=%p",node,node->left, node->right);
  89. print_tree(node->left);
  90. print_tree(node->right);
  91. }else{
  92. printf("\n%p => %i",node,node->value);
  93. }
  94. }
  95. #endif
  96. uint8_t build_tree(huffman_dec_ctx_t* ctx){
  97. uint16_t treesize;
  98. uint16_t treeindex=1;
  99. int8_t i,t;
  100. if(ctx->read_byte(ctx->addr++)!=0xC0)
  101. return 1;
  102. if(((treesize=ctx->read_byte(ctx->addr++))&0xFE)!=0xDE)
  103. return 1;
  104. treesize = (treesize&1)<<8;
  105. treesize += ctx->read_byte(ctx->addr++);
  106. if(treesize>0x1ff)
  107. return 2;
  108. #if BLOCK_ALLOC
  109. ctx->tree = calloc(2*treesize-1, sizeof(node_t));
  110. #else
  111. ctx->tree = calloc(1, sizeof(node_t));
  112. #endif
  113. ((node_t*)(ctx->tree))->value = V_NODE;
  114. uint16_t depth=0;
  115. uint16_t count=0;
  116. uint16_t v;
  117. uint8_t prefix[PREFIX_SIZE_B];
  118. uint8_t cdepth=0;
  119. node_t* current=ctx->tree;
  120. current->value = V_NODE;
  121. memset(prefix, 0, PREFIX_SIZE_B);
  122. do{
  123. while(count==0){
  124. depth++;
  125. count= ctx->read_byte(ctx->addr++);
  126. if(count==255)
  127. count += ctx->read_byte(ctx->addr++);
  128. }
  129. v = ctx->read_byte(ctx->addr++);
  130. if(v>0xff)
  131. return 3;
  132. --count;
  133. for(;cdepth<depth;++cdepth){
  134. prefix_shiftleft(prefix);
  135. }
  136. #if DEBUG
  137. printf("\n value %x => ",v);
  138. #endif
  139. current=ctx->tree;
  140. for(i=depth-1; i>=0; --i){
  141. t=(prefix[i/8])&(1<<(i%8));
  142. if(t==0){
  143. #if DEBUG
  144. printf("0");
  145. #endif
  146. if(current->left==NULL){
  147. #if BLOCK_ALLOC
  148. current->left=&(((node_t*)(ctx->tree))[treeindex++]);
  149. #else
  150. current->left=calloc(1, sizeof(node_t));
  151. #endif
  152. ((node_t*)(current->left))->value = V_NODE;
  153. }
  154. current = current->left;
  155. } else {
  156. #if DEBUG
  157. printf("1");
  158. #endif
  159. if(current->right==NULL){
  160. #if BLOCK_ALLOC
  161. current->right=&(((node_t*)(ctx->tree))[treeindex++]);
  162. #else
  163. current->right=calloc(1, sizeof(node_t));
  164. #endif
  165. ((node_t*)(current->right))->value=V_NODE;
  166. }
  167. current = current->right;
  168. }
  169. }
  170. #if !BLOCK_ALLOC
  171. if(current==NULL)
  172. ALLOC_ERROR
  173. #endif
  174. current->value=v;
  175. prefix_increment(prefix);
  176. }while(!(prefix[depth/8]&(1<<(depth%8))));
  177. #if DEBUG
  178. print_tree(ctx->tree);
  179. #endif
  180. set_last_to_eof(ctx->tree);
  181. return 0;
  182. }
  183. void free_tree(node_t* node){
  184. #if !BLOCK_ALLOC
  185. if(node->value==V_NODE){
  186. free_tree(node->left);
  187. free_tree(node->right);
  188. }
  189. #endif
  190. free(node);
  191. }
  192. static uint8_t read_bit(huffman_dec_ctx_t* ctx){
  193. uint16_t x;
  194. uint8_t t;
  195. if(ctx->rbuffer_index==8){
  196. x=ctx->read_byte(ctx->addr);
  197. ctx->addr++;
  198. if(t>0xff)
  199. return 0xFF;
  200. ctx->rbuffer = (uint8_t)x;
  201. ctx->rbuffer_index=0;
  202. }
  203. t=(ctx->rbuffer)>>7;
  204. ctx->rbuffer<<=1;
  205. ctx->rbuffer_index++;
  206. return t;
  207. }
  208. uint16_t huffman_dec_byte(huffman_dec_ctx_t* ctx){
  209. node_t* current=ctx->tree;
  210. uint8_t t;
  211. if(current==NULL){
  212. #if DEBUG
  213. printf("\nbuild tree");
  214. #endif
  215. t=build_tree(ctx);
  216. if(t!=0){
  217. #if DEBUG
  218. printf("\n!!! building tree failed !!!\r\n");
  219. #endif
  220. return 0xFFFF;
  221. }
  222. #if DEBUG
  223. printf("\ntree build successful");
  224. #endif
  225. current=ctx->tree;
  226. }
  227. while(current->value==V_NODE){
  228. t=read_bit(ctx);
  229. if(t==0xFF)
  230. goto eof_detected;
  231. if(t==0){
  232. current=current->left;
  233. } else {
  234. current=current->right;
  235. }
  236. }
  237. if(current->value!=V_EOF){
  238. return current->value;
  239. }
  240. eof_detected:
  241. free_tree(ctx->tree);
  242. ctx->tree = NULL;
  243. return 0xFFFF;
  244. }