neginf.c 9.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466
  1. /*
  2. * neginf.c
  3. * neginf -- embedded inflate lib
  4. *
  5. * inflate routines
  6. */
  7. #include <assert.h>
  8. #include <stdlib.h>
  9. #include <stdio.h>
  10. #include "neginf.h"
  11. #include "neginf_priv.h"
  12. typedef void(*mode_fun)() ;
  13. static neginf_state state;
  14. static const mode_fun mode_tab[mode_count] = {
  15. &await_block,
  16. &raw_block_begin,
  17. &raw_block_begin2,
  18. &raw_block,
  19. &fixed_block_begin,
  20. &huff_block,
  21. &huff_len_addbits,
  22. &huff_dist,
  23. &huff_dist_addbits,
  24. &dynamic_block_begin,
  25. &dynamic_read_lc,
  26. &dynamic_read_lit_len,
  27. &dynamic_read_dist
  28. };
  29. void neginf_init(nsize start_pos)
  30. {
  31. state.queue_size = 0;
  32. state.mode = mode_await_block;
  33. state.last_block = 0;
  34. #ifdef NEGINF_POS_TRACKING
  35. state.output_pos = start_pos;
  36. #endif
  37. }
  38. void neginf_process_byte(nbyte byte)
  39. {
  40. assert(state.queue_size <= 16);
  41. state.input_queue |= (byte << state.queue_size);
  42. state.queue_size += 8;
  43. while(state.queue_size >= 16)
  44. {
  45. //printf("qsize=%i mode=%i\n",state.queue_size,state.mode);
  46. mode_tab[state.mode]();
  47. }
  48. }
  49. #ifdef NEGINF_POS_TRACKING
  50. nsize neginf_output_position()
  51. {
  52. return state.output_pos;
  53. }
  54. #endif
  55. nint lookahead()
  56. {
  57. //printf("lookahead\n");
  58. return state.input_queue;
  59. }
  60. void consume(ntiny amount)
  61. {
  62. //printf("consume %i %i\n",state.queue_size,amount);
  63. assert(state.queue_size > amount);
  64. state.input_queue >>= amount;
  65. state.queue_size -= amount;
  66. }
  67. void await_block()
  68. {
  69. //printf("wait block\n");
  70. if(state.last_block)
  71. {
  72. neginf_cb_completed();
  73. consume(16);
  74. }
  75. else
  76. {
  77. nint la = lookahead();
  78. state.last_block = la & 1;
  79. consume(3);
  80. switch(la & 6)
  81. {
  82. case 0: // 00 uncompressed
  83. consume((state.queue_size) & 7); // align to byte
  84. state.mode = mode_raw_block_begin;
  85. break;
  86. case 2: // 01 fixed huffman
  87. state.mode = mode_fixed_block_begin;
  88. break;
  89. case 4: // 10 dynamic huffman
  90. state.mode = mode_dynamic_block_begin;
  91. break;
  92. default:
  93. assert(0);
  94. }
  95. }
  96. }
  97. void raw_block_begin()
  98. {
  99. //printf("raw block begin\n");
  100. state.raw_size = lookahead() & 0xFFFF; // size of raw block
  101. consume(16);
  102. state.mode = mode_raw_block_begin2;
  103. }
  104. void raw_block_begin2()
  105. {
  106. //printf("raw block begin2\n");
  107. consume(16); // we ignore the inverted size
  108. state.mode = mode_raw_block;
  109. }
  110. void raw_block()
  111. {
  112. //printf("raw block\n");
  113. if(state.raw_size == 0)
  114. {
  115. state.mode = mode_await_block;
  116. }
  117. else
  118. {
  119. state.raw_size--;
  120. neginf_cb_seq_byte(lookahead() & 0xFF);
  121. #ifdef NEGINF_POS_TRACKING
  122. state.output_pos++;
  123. #endif
  124. consume(8);
  125. }
  126. }
  127. void fixed_block_begin()
  128. {
  129. //printf("fixed block begin\n");
  130. nint i = 0;
  131. for(; i < 144; i++)
  132. state.lit_len_lengths[i] = 8;
  133. for(; i < 256; i++)
  134. state.lit_len_lengths[i] = 9;
  135. for(; i < 280; i++)
  136. state.lit_len_lengths[i] = 7;
  137. for(; i < 288; i++)
  138. state.lit_len_lengths[i] = 8;
  139. ntiny j;
  140. for(j = 0; i < 32; i++)
  141. state.dist_lengths[i] = 5;
  142. compute_begins();
  143. state.mode = mode_huff_block;
  144. }
  145. void huff_block()
  146. {
  147. //printf("huff block\n");
  148. nint code = lit_len_read();
  149. if(code == 256)
  150. {
  151. state.mode = mode_await_block;
  152. }
  153. else if(code < 256)
  154. {
  155. neginf_cb_seq_byte(code);
  156. #ifdef NEGINF_POS_TRACKING
  157. state.output_pos++;
  158. #endif
  159. }
  160. else
  161. {
  162. state.code = code;
  163. state.mode = mode_huff_len_addbits;
  164. }
  165. }
  166. void huff_len_addbits()
  167. {
  168. //printf("huff len addbits\n");
  169. nint len;
  170. nint code = state.code;
  171. nint la = lookahead();
  172. if(code < 265)
  173. len = code - 257 + 3;
  174. else if(code < 269)
  175. {
  176. len = (code - 265) * 2 + 11 + (la & 1);
  177. consume(1);
  178. }
  179. else if(code < 273)
  180. {
  181. len = (code - 269) * 4 + 19 + (la & 3);
  182. consume(2);
  183. }
  184. else if(code < 277)
  185. {
  186. len = (code - 273) * 8 + 35 + (la & 7);
  187. consume(3);
  188. }
  189. else if(code < 281)
  190. {
  191. len = (code - 277) * 16 + 67 + (la & 15);
  192. consume(4);
  193. }
  194. else if(code < 285)
  195. {
  196. len = (code - 281) * 32 + 131 + (la & 31);
  197. consume(5);
  198. }
  199. else
  200. {
  201. len = 258;
  202. }
  203. state.match_len = len;
  204. state.mode = mode_huff_dist;
  205. }
  206. void huff_dist()
  207. {
  208. //printf("huff dist\n");
  209. state.tcode = dist_read();
  210. state.mode = mode_huff_dist_addbits;
  211. }
  212. void huff_dist_addbits()
  213. {
  214. //printf("huff addbits\n");
  215. nint dist;
  216. ntiny code = state.tcode;
  217. if(code < 4)
  218. {
  219. dist = code+1;
  220. }
  221. else if(code > 29)
  222. {
  223. assert(0);
  224. }
  225. else
  226. {
  227. nint la = lookahead();
  228. ntiny len = (code - 2) / 2;
  229. dist = ((2 + (code & 1)) << len) + 1 + (((1 << len) - 1) & la);
  230. consume(len);
  231. }
  232. neginf_cb_rel_copy(dist, state.match_len);
  233. #ifdef NEGINF_POS_TRACKING
  234. state.output_pos += state.match_len;
  235. #endif
  236. state.mode = mode_huff_block;
  237. }
  238. void dynamic_block_begin()
  239. {
  240. nint j;
  241. ntiny i;
  242. //printf("dynamic block begin\n");
  243. for(j = 0; j < 288; j++)
  244. state.lit_len_lengths[j] = 0;
  245. for(i = 0; i < 32; i++)
  246. state.dist_lengths[i] = 0;
  247. for(i = 0; i < 19; i++)
  248. state.hc_lengths[i] = 0;
  249. nint la = lookahead();
  250. state.hlit = (la & 31) + 257;
  251. state.hdist = ((la >> 5) & 31) + 1;
  252. state.hclen = ((la >> 10) & 15) + 4;
  253. state.torder = 0;
  254. consume(5+5+4);
  255. state.mode = mode_dynamic_read_lc;
  256. }
  257. void dynamic_read_lc()
  258. {
  259. //printf("dynamic read lc\n");
  260. if(state.hclen == 0)
  261. {
  262. compute_begin(state.hc_lengths, state.hc_begins, 19);
  263. state.mode = mode_dynamic_read_lit_len;
  264. state.order = 0;
  265. }
  266. else
  267. {
  268. static const ntiny order[19] = {
  269. 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
  270. };
  271. ntiny i = lookahead() & 7;
  272. state.hc_lengths[order[state.torder]] = i;
  273. consume(3);
  274. state.torder++;
  275. state.hclen--;
  276. }
  277. }
  278. void dynamic_read_lit_len()
  279. {
  280. //printf("dynamic read lit len\n");
  281. if(state.hlit == 0)
  282. {
  283. state.mode = mode_dynamic_read_dist;
  284. state.order = 0;
  285. }
  286. else
  287. {
  288. state.hlit -= lc_read(state.lit_len_lengths);
  289. }
  290. }
  291. void dynamic_read_dist()
  292. {
  293. //printf("dynamic read dist\n");
  294. if(state.hdist == 0)
  295. {
  296. compute_begins();
  297. state.mode = mode_huff_block;
  298. }
  299. else
  300. {
  301. state.hdist -= lc_read(state.dist_lengths);
  302. }
  303. }
  304. ntiny lc_read(ntiny * lenghts)
  305. {
  306. //printf("read lc\n");
  307. ntiny code = huff_read(state.hc_lengths, state.hc_begins, 19);
  308. // this reads 7 bits max so we still have 9 bits left in the buffer
  309. if(code < 16)
  310. {
  311. lenghts[state.order] = code;
  312. state.order++;
  313. return 1;
  314. }
  315. else if(code == 16)
  316. {
  317. ntiny i;
  318. ntiny copy = (lookahead() & 3) + 3;
  319. consume(2);
  320. for(i = 0; i < copy; i++)
  321. lenghts[state.order + i] = lenghts[state.order - 1];
  322. state.order += copy;
  323. return copy;
  324. }
  325. else
  326. {
  327. ntiny fill;
  328. ntiny i;
  329. if(code == 17)
  330. {
  331. fill = (lookahead() & 7) + 3;
  332. consume(3);
  333. }
  334. else
  335. {
  336. fill = (lookahead() & 127) + 11;
  337. consume(7);
  338. }
  339. for(i = 0; i < fill; i++)
  340. {
  341. lenghts[state.order] = 0;
  342. state.order++;
  343. }
  344. return fill;
  345. }
  346. }
  347. void compute_begins()
  348. {
  349. //printf("compute begins\n");
  350. compute_begin(state.lit_len_lengths, state.lit_len_begins, 288);
  351. compute_begin(state.dist_lengths, state.dist_begins, 32);
  352. }
  353. void compute_begin(ntiny * lengths, nint * begins, nint size)
  354. {
  355. ntiny j;
  356. nint i;
  357. //printf("compute begin\n");
  358. for(j = 0; j < 14; j++)
  359. begins[j] = 0;
  360. for(i = 0; i < size; i++)
  361. {
  362. nint len = lengths[i];
  363. if(len != 0 && len != 15)
  364. begins[len-1] += 1 << (15 - len);
  365. }
  366. nint acc = 0;
  367. for(j = 0; j < 14; j++)
  368. {
  369. nint val = begins[j];
  370. acc += val;
  371. begins[j] = acc;
  372. }
  373. }
  374. nint lit_len_read()
  375. {
  376. //printf("lit len read\n");
  377. return huff_read(state.lit_len_lengths, state.lit_len_begins, 288);
  378. }
  379. nint dist_read()
  380. {
  381. //printf("dist read\n");
  382. return huff_read(state.dist_lengths, state.dist_begins, 32);
  383. }
  384. nint huff_read(ntiny * lenghts, nint * begins, nint size)
  385. {
  386. //printf("huff read\n");
  387. nint code = 0;
  388. ntiny i;
  389. for(i = 1; i < 16; i++)
  390. {
  391. code |= (lookahead() & 1) << (15-i);
  392. consume(1);
  393. if(i == 15 || code < begins[i-1])
  394. break;
  395. }
  396. code -= begins[i-2];
  397. code >>= (15-i);
  398. nint j;
  399. for(j = 0; j < size; j++)
  400. {
  401. if(lenghts[j] == i)
  402. {
  403. if(code == 0)
  404. return j;
  405. code--;
  406. }
  407. }
  408. //assert(0);
  409. return 0; // silent warning
  410. }
  411. #ifndef NEGINF_USE_SEQ_WRITES
  412. void neginf_cb_seq_byte(nbyte byte)
  413. {
  414. neginf_cb_byte(state.output_pos, byte);
  415. }
  416. #endif
  417. #ifndef NEGINF_USE_REL_COPY
  418. void neginf_cb_rel_copy(nint distance, nint length)
  419. {
  420. neginf_cb_copy(state.output_pos - distance, state.output_pos, length);
  421. }
  422. #endif