home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / l / lds_10.zip / ASH / ARITH.C next >
C/C++ Source or Header  |  1992-01-15  |  8KB  |  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.