home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / ddjcompr / ashford / arith.c next >
C/C++ Source or Header  |  1991-08-03  |  6KB  |  389 lines
  1. #include "arith.h"
  2. #include "files.h"
  3.  
  4.  
  5. /*
  6.     Declare variables use for arithmetic compression
  7. */
  8.  
  9. static int under_flow_count = 0;
  10. static unsigned int low = 0;
  11. static unsigned int range = MAX_RANGE;
  12. static unsigned int value = 0;
  13.  
  14. static unsigned int code_value = 0;
  15. static unsigned int code_bit_count = 0;
  16. static unsigned codesize = 0;
  17.  
  18.  
  19. static int shift_count (unsigned);
  20.  
  21. static void put_bit (int);
  22. static void put_bit_string (unsigned, int);
  23. static void clear_under_flow (unsigned);
  24.  
  25. static unsigned get_bit_string (int);
  26. static unsigned get_bit (void);
  27.  
  28.  
  29.  
  30. /*
  31.     Initialize arithmetic coder at start of any compress/expand procedure
  32. */
  33.  
  34. void InitCoder (void)
  35.  
  36. {
  37.     low = 0;
  38.     range = MAX_RANGE;
  39. }
  40.  
  41.  
  42.  
  43. /*
  44.     Terminate arithmetic code operation
  45.     Write bit string whose value is within active code range
  46.     Force final byte to be output to file
  47. */
  48.  
  49. void CloseCoder (void)
  50.  
  51. {
  52.     int i;
  53.  
  54.     put_bit (1);
  55.     for (i = 0; i < 7; i++) put_bit (0);
  56.     CloseOutputFile ();
  57. }
  58.  
  59.  
  60.  
  61. /*
  62.     Save state of arithmetic coder
  63.     Allows state to be restored at a later time
  64. */
  65.  
  66. void SaveCoderState (struct coder_state *p)
  67.  
  68. {
  69.     p -> low = low;
  70.     p -> range = range;
  71.     p -> uflow = under_flow_count;
  72.     p -> bits = code_bit_count;
  73.     p -> fpos = codesize;
  74. }
  75.  
  76.  
  77. /*
  78.     Restore arithmetic coder state from saved value
  79.     Repositin output file
  80.     Set all internal values to their original state
  81. */
  82.  
  83. void RestoreCoderState (struct coder_state *p)
  84.  
  85. {
  86.     int n;
  87.     int cv;
  88.     static unsigned char reset_mask [] =
  89.  
  90.     {
  91.         0x00,  0x80,  0xC0,  0xE0,  0xF0,  0xF8,  0xFC,  0xFE,  0xFF,
  92.     };
  93.  
  94.     n = codesize - p -> fpos;
  95.     cv = ResetOutputPointer (n);
  96.  
  97.     low = p -> low;
  98.     range = p -> range;
  99.  
  100.     under_flow_count = p -> uflow;
  101.     code_bit_count = p -> bits;
  102.     code_value = cv & reset_mask [code_bit_count];
  103.     codesize -= n;
  104. }
  105.  
  106.  
  107. /*
  108.     Estimate length of output code string
  109.     Uses previously saved coder state
  110.     Returns difference between saved position and current position
  111. */
  112.  
  113. int CodeLength (struct coder_state *csptr)
  114.  
  115. {
  116.     int len;
  117.  
  118.     len = codesize - csptr -> fpos;
  119.     len *= 8;
  120.     len += under_flow_count - csptr -> uflow;
  121.     len += code_bit_count - csptr -> bits;
  122.  
  123.     return len;
  124. }
  125.  
  126.  
  127. /*
  128.     Arithmetic coder
  129.     Encode symbol using input frequencies
  130.     Output as many bits as possible to output file
  131.     Update coder values for next symbol
  132. */
  133.  
  134. void EncodeArith (unsigned base, unsigned freq, unsigned cmax)
  135.  
  136. {
  137.     unsigned long t;
  138.     unsigned x;
  139.  
  140.     int n1, n2;
  141.  
  142.     t  = (long) range * (long) base;
  143.     t += (long) base;
  144.     low  += (unsigned) (t / cmax);
  145.     x     = (unsigned) (t % cmax);
  146.  
  147.     t = (long) range * (long) freq;
  148.  
  149.     t += (long) (freq + x);
  150.     t -= cmax;
  151.     range = (unsigned) (t / cmax);
  152.  
  153.     n1 = shift_count ((low + range) ^ low);
  154.     if (n1 && under_flow_count)
  155.     {
  156.         clear_under_flow ((low & 0x8000) != 0);
  157.         low ^= 0x8000;
  158.     }
  159.  
  160.     if (n1)
  161.     {
  162.         put_bit_string (low, n1);
  163.         low <<= n1;
  164.         range = ((range + 1) << n1) - 1;
  165.     }
  166.  
  167.     if (range < MIN_RANGE)
  168.     {
  169.         n2 = shift_count (range - 1) - 1;
  170.  
  171.         under_flow_count += n2;
  172.         low <<= n2;
  173.         low &= 0x7FFF;
  174.         range = ((range + 1) << n2) - 1;
  175.     }
  176. }
  177.  
  178.  
  179. /*
  180.     Send bit string based on underflow count
  181.     Uses bit value followed by its complement
  182.  
  183.     generates: 0111... or 1000...
  184. */
  185.     
  186. static void clear_under_flow (unsigned bit)
  187.  
  188. {
  189.     put_bit (bit);
  190.     bit ^= 0x01;
  191.     while (-- under_flow_count) put_bit (bit);
  192. }
  193.  
  194.  
  195.  
  196. /*
  197.     Send bit string
  198. */
  199.  
  200. static void put_bit_string (unsigned x, int count)
  201.  
  202. {
  203.     while (count)
  204.     {
  205.         put_bit ((x & 0x8000) != 0);
  206.         x <<= 1;
  207.         count --;
  208.     }
  209. }
  210.  
  211.  
  212.  
  213. /*
  214.     Write single bit to output file using internal buffer
  215. */
  216.  
  217. static void put_bit (int bit)
  218.  
  219. {
  220.     static unsigned char mask [] =
  221.     {
  222.         0x80,    0x40,    0x20,    0x10,    0x08,    0x04,    0x02,    0x01,
  223.     };
  224.  
  225.     if (bit) code_value |= mask [code_bit_count];
  226.     if (++ code_bit_count == 8)
  227.     {
  228.         WriteOutputFile (code_value);
  229.         code_value = 0;
  230.         code_bit_count = 0;
  231.         codesize ++;
  232.     }
  233. }
  234.  
  235.  
  236.  
  237. /*
  238.     Determine number of leading zero bits on unsigned value
  239. */
  240.  
  241. static int shift_count (unsigned n)
  242.  
  243. {
  244.     int i;
  245.  
  246.     i = 0;
  247.     while ((n & 0x8000) == 0 && i < 16)
  248.     {
  249.         i ++;
  250.         n <<= 1;
  251.     }
  252.  
  253.     return i;
  254. }
  255.  
  256.  
  257.  
  258. /*
  259.     Read bit string from input stream
  260.     Length is limited to word size
  261. */
  262.  
  263. static unsigned get_bit_string (int n)
  264.  
  265. {
  266.     unsigned x = 0;
  267.  
  268.     while (n)
  269.     {
  270.         x <<= 1;
  271.         x += get_bit ();
  272.         n --;
  273.     }
  274.  
  275.     return x;
  276. }
  277.  
  278.  
  279.  
  280. /*
  281.     Read a single bit from input stream
  282.     Uses a one byte buffer for intermediate values
  283. */
  284.  
  285. static unsigned get_bit (void)
  286.  
  287. {
  288.     int n;
  289.  
  290.     if (code_bit_count == 0)
  291.     {
  292.         code_bit_count = 8;
  293.         n = ReadInputFile ();
  294.         code_value = n >= 0 ? n : 0;
  295.     }
  296.  
  297.     code_bit_count --;
  298.     n = code_value & 0x80;
  299.     code_value <<= 1;
  300.  
  301.     return n != 0;
  302. }
  303.  
  304.  
  305.  
  306. /*
  307.     Initialize arithmetic decode procedure
  308. */
  309.  
  310. void StartDecode (void)
  311.  
  312. {
  313.     int i;
  314.  
  315.     value = 0;
  316.     for (i = 0; i < 16; i ++)
  317.     {
  318.         value <<= 1;
  319.         value |= get_bit ();
  320.     }
  321. }
  322.  
  323.  
  324. /*
  325.     Return value of next input code
  326.     Input consists of total frequency for active symbol set
  327.     Note that decoder must be updated with actual frequencies used
  328. */
  329.  
  330. int DecodeArith (unsigned cmax)
  331.  
  332. {
  333.     unsigned long t;
  334.  
  335.     t = (long) (value - low + 1) * (long) cmax;
  336.     t -= 1;
  337.     t /= (long) range + 1;
  338.  
  339.     return (unsigned) t;
  340. }
  341.  
  342.  
  343. /*
  344.     Update arithmetic decoder using actual symbol frequencies
  345.     Read additional bits from input based on symbol values
  346. */
  347.  
  348. void UpdateDecoder (unsigned base, unsigned freq, unsigned cmax)
  349.  
  350. {
  351.     unsigned long t;
  352.     unsigned x, y;
  353.  
  354.     int n1, n2;
  355.  
  356.     t  = (long) range * (long) base;
  357.     t += (long) base;
  358.     x  = (unsigned) (t / cmax);
  359.     y  = (unsigned) (t % cmax);
  360.  
  361.     low += x;
  362.  
  363.     t = (long) range * (long) freq;
  364.     t += (long) (freq + y);
  365.     t -= cmax;
  366.     range = (unsigned) (t / cmax);
  367.  
  368.     n1 = shift_count ((low + range) ^ low);
  369.     if (n1)
  370.     {
  371.         low <<= n1;
  372.         range = ((range + 1) << n1) - 1;
  373.         value <<= n1;
  374.         value |= get_bit_string (n1);
  375.     }
  376.  
  377.     if (range < MIN_RANGE)
  378.     {
  379.         n2 = shift_count (range - 1) - 1;
  380.         value -= low;
  381.         low <<= n2;
  382.         low &= 0x7FFF;
  383.         range = ((range + 1) << n2) - 1;
  384.         value <<= n2;
  385.         value |= get_bit_string (n2);
  386.         value += low;
  387.     }
  388. }
  389.