Subversion Repositories KoE_projects

Rev

Blame | Last modification | View Log | Download | RSS feed | ?url?

  1. #include <setjmp.h>
  2. #include "compress.h"
  3.  
  4. //--------------------------------------------------------------------------------
  5.  
  6. /*
  7.     (C) ─. ╠рёЄЁ■ъют, "╠юэшЄюЁ", N1, 1994.
  8.     └ыуюЁшЄь√ ёцрЄш  шэЇюЁьрЎшш
  9. */
  10.  
  11. // ╩юышўхёЄтю сшЄют т ЁхушёЄЁх
  12. #define BITS_IN_REGISTER 16
  13.  
  14. // ╠ръёшьры№эю тючьюцэюх чэрўхэшх т ЁхушёЄЁх
  15. #define TOP_VALUE (((long) 1 << BITS_IN_REGISTER) - 1)
  16.  
  17. // ─шрярчюэ√
  18. #define FIRST_QTR (TOP_VALUE / 4 + 1)
  19. #define HALF      (2 * FIRST_QTR)
  20. #define THIRD_QTR (3 * FIRST_QTR)
  21.  
  22. // ╩юышўхёЄтю ёшьтюыют рыЇртшЄр
  23. #define NO_OF_CHARS 256
  24. // ╤яхЎшры№э√щ ёшьтюы ╩юэхЎ╘рщыр
  25. #define EOF_SYMBOL    (NO_OF_CHARS + 1)
  26. // ┬ёхую ёшьтюыют т ьюфхыш
  27. #define NO_OF_SYMBOLS (NO_OF_CHARS + 1)
  28.  
  29. // ╧юЁюу ўрёЄюЄ√ фы  ьрё°ЄрсшЁютрэш 
  30. #define MAX_FREQUENCY 16383
  31.  
  32. // ╥рсышЎ√ яхЁхъюфшЁютъш
  33. static unsigned char index_to_char [NO_OF_SYMBOLS];
  34. static int char_to_index [NO_OF_CHARS];
  35.  
  36. // ╥рсышЎ√ ўрёЄюЄ
  37. static int cum_freq [NO_OF_SYMBOLS + 1];
  38. static int freq[NO_OF_SYMBOLS + 1];
  39.  
  40. // ╨хушёЄЁ√ уЁрэшЎ ш ъюфр
  41. static long low, high;
  42. static long value;
  43.  
  44. // ╧юффхЁцър яюсшЄыт√ї юяхЁрЎшщ ё Їрщырьш
  45. static long bits_to_follow;
  46. static int      buffer;
  47. static int      bits_to_go;
  48. static int  garbage_bits;
  49.  
  50. // ┬їюфэющ ш т√їюфэющ сєЇхЁр
  51. static unsigned long inbuf_pos;
  52. static unsigned long inbuf_size;
  53. static unsigned char *outbuf;
  54. static unsigned long outbuf_pos;
  55.  
  56. static read_func_type read_byte_func;
  57.  
  58. // setjmp/longjmp
  59. static jmp_buf mark;
  60.  
  61. int input_bit(void);
  62. void start_model(void);
  63.  
  64.  
  65. //////////////////////////////////////////////////
  66. // ╚эшЎшрышчрЎш  рфряЄштэющ ьюфхыш
  67.  
  68. static void start_model()
  69. {
  70.     int i;
  71.  
  72.     for ( i = 0; i < NO_OF_CHARS; i++)
  73.     {
  74.         char_to_index[i] = i + 1;
  75.         index_to_char[i + 1] = i;
  76.     }
  77.     for (i = 0; i <= NO_OF_SYMBOLS; i++)
  78.     {
  79.         freq[i] = 1;
  80.         cum_freq[i] = NO_OF_SYMBOLS - i;
  81.     }
  82.     freq [0] = 0;
  83. }
  84.  
  85. //////////////////////////////////////////////////
  86. // ╬сэютыхэшх ьюфхыш юўхЁхфэ√ь ёшьтюыюь
  87.  
  88. static void update_model (int symbol)
  89. {
  90.     int i;
  91.     int ch_i, ch_symbol;
  92.     int cum;
  93.  
  94.     // яЁютхЁър эр яхЁхяюыэхэшх ёўхЄўшър ўрёЄюЄ√
  95.     if (cum_freq [0] == MAX_FREQUENCY)
  96.     {
  97.         cum = 0;
  98.         // ьрё°ЄрсшЁютрэшх ўрёЄюЄ яЁш яхЁхяюыэхэшш
  99.         for ( i = NO_OF_SYMBOLS; i >= 0; i--)
  100.         {
  101.             freq [i] = (freq [i] + 1) / 2;
  102.             cum_freq [i] = cum;
  103.             cum += freq [i];
  104.         }
  105.     }
  106.     for ( i = symbol; freq [i] == freq [i - 1]; i--);
  107.     if (i < symbol)
  108.     {
  109.         ch_i                      = index_to_char [i];
  110.         ch_symbol                 = index_to_char [symbol];
  111.         index_to_char [i]         = ch_symbol;
  112.         index_to_char [symbol]    = ch_i;
  113.         char_to_index [ch_i]      = symbol;
  114.         char_to_index [ch_symbol] = i;
  115.     }
  116.     // юсэютыхэшх чэрўхэшщ т ЄрсышЎрї ўрёЄюЄ
  117.     freq [i] += 1;
  118.     while (i > 0)
  119.     {
  120.         i -= 1;
  121.         cum_freq [i] += 1;
  122.     }
  123. }
  124.  
  125. //////////////////////////////////////////////////
  126. // ╚эшЎшрышчрЎш  яюсшЄютюую ттюфр
  127.  
  128. void start_inputing_bits()
  129. {
  130.     bits_to_go = 0;
  131.     garbage_bits = 0;
  132. }
  133.  
  134. //////////////////////////////////////////////////
  135. // ┬тюф юўхЁхфэюую сшЄр ёцрЄющ шэЇюЁьрЎшш
  136.  
  137. static int input_bit()
  138. {
  139.     int t;
  140.  
  141.     if (bits_to_go == 0)
  142.     {
  143.         buffer = (*read_byte_func)(inbuf_pos++);
  144.         if (inbuf_pos == inbuf_size)
  145.         {
  146.             garbage_bits += 1;
  147.             if (garbage_bits > BITS_IN_REGISTER - 2)
  148.             {
  149.                 longjmp(mark, -1);
  150.             }
  151.         }
  152.         bits_to_go = 8;
  153.     }
  154.     t = buffer & 1;
  155.     buffer >>= 1;
  156.     bits_to_go -= 1;
  157.     return t;
  158. }
  159.  
  160. #ifndef __KEIL__
  161.  
  162. //////////////////////////////////////////////////
  163. // ╚эшЎшрышчрЎш  яюсшЄютюую т√тюфр
  164.  
  165. static void start_outputing_bits()
  166. {
  167.     buffer = 0;
  168.     bits_to_go = 8;
  169. }
  170.  
  171. //////////////////////////////////////////////////
  172. // ┬√тюф юўхЁхфэюую сшЄр ёцрЄющ шэЇюЁьрЎшш
  173.  
  174. static void output_bit(int bt)
  175. {
  176.     buffer >>= 1;
  177.     if (bt)
  178.         buffer |= 0x80;
  179.     bits_to_go -= 1;
  180.     if (bits_to_go == 0)
  181.     {
  182.         outbuf[outbuf_pos++] = buffer;
  183.         bits_to_go = 8;
  184.     }
  185. }
  186.  
  187. //////////////////////////////////////////////////
  188. // ╬ўшёЄър сєЇхЁр яюсшЄютюую т√тюфр
  189.  
  190. static void done_outputing_bits()
  191. {
  192.     outbuf[outbuf_pos++] = buffer >> bits_to_go;
  193. }
  194.  
  195. //////////////////////////////////////////////////
  196. // ┬√тюф єърчрээюую сшЄр ш юЄыюцхээ√ї Ёрэхх
  197.  
  198. static void output_bit_plus_follow(int bt)
  199. {
  200.     output_bit(bt);
  201.     while (bits_to_follow > 0)
  202.     {
  203.         output_bit(!bt);
  204.         bits_to_follow--;
  205.     }
  206. }
  207.  
  208. //////////////////////////////////////////////////
  209. // ╚эшЎшрышчрЎш  ЁхушёЄЁют уЁрэшЎ ш ъюфр яхЁхф эрўрыюь ёцрЄш 
  210.  
  211. static void start_encoding()
  212. {
  213.     low = 0l;
  214.     high = TOP_VALUE;
  215.     bits_to_follow = 0l;
  216. }
  217.  
  218. //////////////////////////////////////////////////
  219. // ╬ўшёЄър яюсшЄютюую т√тюфр
  220.  
  221. static void done_encoding()
  222. {
  223.     bits_to_follow++;
  224.     if (low < FIRST_QTR)
  225.         output_bit_plus_follow(0);
  226.     else
  227.         output_bit_plus_follow(1);
  228. }
  229.  
  230. //////////////////////////////////////////////////
  231. // ╩юфшЁютрэшх юўхЁхфэюую ёшьтюыр
  232.  
  233. static void encode_symbol ( int symbol)
  234. {
  235.     long range;
  236.  
  237.     // яхЁхёўхЄ чэрўхэшщ уЁрэшЎ
  238.     range = (long) (high - low) + 1;
  239.     high = low + (range * cum_freq [symbol - 1]) / cum_freq [0] - 1;
  240.     low = low + (range * cum_freq [symbol]) / cum_freq [0];
  241.     // т√фтшурэшх юўхЁхфэ√ї сшЄют
  242.     for (;;)
  243.     {
  244.         if (high < HALF)
  245.             output_bit_plus_follow(0);
  246.         else if (low >= HALF)
  247.         {
  248.             output_bit_plus_follow(1);
  249.             low -= HALF;
  250.             high -= HALF;
  251.         }
  252.         else if (low >= FIRST_QTR && high < THIRD_QTR)
  253.         {
  254.             bits_to_follow += 1;
  255.             low -= FIRST_QTR;
  256.             high -= FIRST_QTR;
  257.         }
  258.         else
  259.             break;
  260.         // ёфтшу тыхтю ё "тЄ уштрэшхь" юўхЁхфэюую сшЄр
  261.         low = 2 * low;
  262.         high = 2 * high + 1;
  263.     }
  264. }
  265. #endif  //__KEIL__
  266.  
  267. //////////////////////////////////////////////////
  268. // ╚эшЎшрышчрЎш  ЁхушёЄЁют яхЁхф фхъюфшЁютрэшхь.
  269. // ╟руЁєчър эрўрыр ёцрЄюую ёююс∙хэш 
  270.  
  271. static void start_decoding()
  272. {
  273.     int i;
  274.  
  275.     value = 0l;
  276.     for ( i = 1; i <= BITS_IN_REGISTER; i++)
  277.         value = 2 * value + input_bit ();
  278.     low = 0l;
  279.     high = TOP_VALUE;
  280. }
  281.  
  282. //////////////////////////////////////////////////
  283. // ─хъюфшЁютрэшх юўхЁхфэюую ёшьтюыр
  284.  
  285. static int decode_symbol()
  286. {
  287.     long range;
  288.     int cum, symbol;
  289.  
  290.     // юяЁхфхыхэшх Єхъє∙хую ьрё°Єрср ўрёЄюЄ
  291.     range = (long) (high - low) + 1;
  292.     // ьрё°ЄрсшЁютрэшх чэрўхэш  т ЁхушёЄЁх ъюфр
  293.     cum = (int)
  294.         ((((long) (value - low) + 1) * cum_freq [0] - 1) / range);
  295.     // яюшёъ ёююЄтхЄёЄтє■∙хую ёшьтюыр т ЄрсышЎх ўрёЄюЄ
  296.     for (symbol = 1; cum_freq [symbol] > cum; symbol++);
  297.     // яхЁхёўхЄ уЁрэшЎ
  298.     high = low + (range * cum_freq [symbol - 1]) / cum_freq [0] - 1;
  299.     low = low + (range * cum_freq [symbol]) / cum_freq [0];
  300.     // єфрыхэшх юўхЁхфэюую ёшьтюыр шч тїюфэюую яюЄюър
  301.     for (;;)
  302.     {
  303.         if (high < HALF)
  304.         {
  305.         }
  306.         else if (low >= HALF)
  307.         {
  308.             value -= HALF;
  309.             low -= HALF;
  310.             high -= HALF;
  311.         }
  312.         else if (low >= FIRST_QTR && high < THIRD_QTR)
  313.         {
  314.             value -= FIRST_QTR;
  315.             low -= FIRST_QTR;
  316.             high -= FIRST_QTR;
  317.         }
  318.         else
  319.             break;
  320.         // ёфтшу тыхтю ё "тЄ уштрэшхь юўхЁхфэюую сшЄр
  321.         low = 2 * low;
  322.         high = 2 * high + 1;
  323.         value = 2 * value + input_bit ();
  324.     }
  325.     return symbol;
  326. }
  327.  
  328. #ifndef __KEIL__
  329. //////////////////////////////////////////////////
  330. // └фряЄштэюх рЁшЇьхЄшўхёъюх ъюфшЁютрэшх
  331. // ╧рЁрьхЄЁ√:
  332. // buf - тїюфэющ сєЇхЁ;
  333. // buf_size - ЁрчьхЁ тїюфэюую сєЇхЁр;
  334. // cbuf - сєЇхЁ фы  ёцрЄ√ї фрээ√ї;
  335. // cbuf_size - ЁрчьхЁ ёцрЄ√ї фрээ√ї.
  336.  
  337. void arithmetic_compress(const unsigned char* buf, unsigned long buf_size, unsigned char* cbuf, unsigned long* cbuf_size)
  338. {
  339.     unsigned long i;
  340.     int ch, symbol;
  341.  
  342.     outbuf = cbuf;
  343.     outbuf_pos = 0;
  344.  
  345.     start_model();
  346.     start_outputing_bits();
  347.     start_encoding();
  348.  
  349.     for (i = 0; i < buf_size; i++)
  350.     {
  351.         ch = buf[i];
  352.         symbol = char_to_index[ch];
  353.         encode_symbol(symbol);
  354.         update_model(symbol);
  355.     }
  356.  
  357.     encode_symbol(EOF_SYMBOL);
  358.     done_encoding();
  359.     done_outputing_bits();
  360.  
  361.     *cbuf_size = outbuf_pos;
  362. }
  363.  
  364. #endif  //__KEIL__
  365.  
  366. //////////////////////////////////////////////////
  367. // arithmetic_decompress_init()
  368. // ╚эшЎшрышчрЎш  ЁрчцрЄш 
  369. // read_func - ЇєэЎш  ўЄхэш  шч сєЇхЁр ёю ёцрЄ√ьш фрээ√ьш;
  370. //
  371. // !!!! KEIL C WORKAROUND !!!
  372. // ╙ърчрЄхыш эр ЇєэъЎшш ЄЁхсє■Є юёюсюую юсЁр∙хэш :
  373. // http://www.keil.com/appnotes/files/apnt_129.pdf
  374. // !!!! END OF WORKAROUND !!!
  375. //
  376. // cbuf_size - ЁрчьхЁ сєЇхЁр ёю ёцрЄ√ьш фрээ√ьш.
  377.  
  378. unsigned char arithmetic_decompress_init(read_func_type read_func, unsigned long cbuf_size)
  379. {
  380.     if (setjmp(mark) != 0)
  381.     {
  382.         return 0;
  383.     }
  384.  
  385.     read_byte_func = read_func;
  386.     inbuf_pos = 0;
  387.     inbuf_size = cbuf_size;
  388.  
  389.     start_model();
  390.     start_inputing_bits();
  391.     start_decoding();
  392.  
  393.     return 1;
  394. }
  395.  
  396. //////////////////////////////////////////////////
  397. // arithmetic_decompress_done
  398. //
  399.  
  400. void arithmetic_decompress_done()
  401. {
  402.     // nothing to do
  403. }
  404.  
  405. //////////////////////////////////////////////////
  406. // └фряЄштэюх рЁшЇьхЄшўхёъюх фхъюфшЁютрэшх
  407. // ╧рЁрьхЄЁ√:
  408. // chunk - сєЇхЁ фы  ЁрчцрЄ√ї фрээ√ї;
  409. // chunk_size - ЁрчьхЁ сєЇхЁр;
  410. // decompressed - ЁрчьхЁ ЁрчцрЄ√ї фрээ√ї.
  411.  
  412. void arithmetic_decompress_chunk(unsigned char* chunk, volatile unsigned int chunk_size, unsigned int* decompressed)
  413. {
  414.     unsigned long i;
  415.     int ch, symbol;
  416.  
  417.         if (inbuf_pos >= inbuf_size)
  418.         {
  419.         *decompressed = 0;
  420.         return;
  421.         }
  422.  
  423.     if (setjmp(mark) != 0)
  424.     {
  425.         *decompressed = 0;
  426.         return;
  427.     }
  428.  
  429.     outbuf = chunk;
  430.     outbuf_pos = 0;
  431.  
  432.     for (i = 0; i < chunk_size; i++)
  433.     {
  434.         symbol = decode_symbol();
  435.         if (symbol == EOF_SYMBOL)
  436.             break;
  437.         ch = index_to_char[symbol];
  438.         outbuf[outbuf_pos++] = ch;
  439.         update_model(symbol);
  440.     }
  441.  
  442.     *decompressed = outbuf_pos;
  443. }
  444.  
  445. //////////////////////////////////////////////////
  446.