huffman-decode.c 5.4 KB

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