home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / graphics / gifbla20.zip / SOURCE / ARITH.C next >
C/C++ Source or Header  |  1992-12-15  |  3KB  |  170 lines
  1.  
  2. /* arith.c - Arithmetic coding routines. */
  3.  
  4. #include <stdio.h>
  5. #include <string.h>
  6.  
  7. #include "uffile.h"
  8. #include "arith.h"
  9.  
  10. #define CODE_VALUE_BITS 16
  11. #define FIRST_QUARTER (1L << (CODE_VALUE_BITS-2))
  12. #define HALF (2*FIRST_QUARTER)
  13. #define THIRD_QUARTER (3*FIRST_QUARTER)
  14. #define TOP_VALUE ((1L<<CODE_VALUE_BITS) - 1)
  15.  
  16. int
  17. arith_start_encoding(ac,ff)
  18. ARITH_CODER *ac; FFILE *ff;
  19. {
  20.     if (ff == NULL)
  21.         return -1;
  22.     ac->ff = ff;
  23.     ff_start1bit(ac->ff);
  24.     ac->low = 0L;
  25.     ac->high = TOP_VALUE;
  26.     ac->u.e.bits_to_follow = 0L;
  27.     return 0;
  28. }
  29.  
  30. static int
  31. f_bit_plus_follow(ac,bit)
  32. ARITH_CODER *ac; int bit;
  33. {
  34.     if (ff_put1bit(ac->ff,bit) < 0)
  35.         return -1;
  36.     bit = !bit;
  37.     for (; ac->u.e.bits_to_follow>0; ac->u.e.bits_to_follow--)
  38.         if (ff_put1bit(ac->ff,bit) < 0)
  39.             return -1;
  40.     return 0;
  41. }
  42.  
  43. #define bit_plus_follow(ac,bit) ((ac)->u.e.bits_to_follow==0 \
  44.     ? ff_put1bit((ac)->ff,(bit)) : f_bit_plus_follow(ac,bit))
  45.  
  46. int
  47. arith_encode(ac,rstart,rend,rtot)
  48. ARITH_CODER *ac; int rstart; int rend; int rtot;
  49. {
  50.     long iwidth;
  51.     register unsigned int high,low;
  52.  
  53.     iwidth = ac->high+1-ac->low;
  54.     high = (unsigned int)(ac->low + (iwidth*rend)/rtot - 1);
  55.     low = (unsigned int)(ac->low + (iwidth*rstart)/rtot);
  56.     for (;;) {
  57.         if (high < HALF) {
  58.             if (bit_plus_follow(ac,0) < 0)
  59.                 return -1;
  60.         } else if (HALF <= low) {
  61.             if (bit_plus_follow(ac,1) < 0)
  62.                 return -1;
  63.             low -= HALF;
  64.             high -= HALF;
  65.         } else if (FIRST_QUARTER<=low && high<THIRD_QUARTER) {
  66.             ac->u.e.bits_to_follow++;
  67.             low -= FIRST_QUARTER;
  68.             high -= FIRST_QUARTER;
  69.         } else {
  70.             ac->high = high;
  71.             ac->low = low;
  72.             return 0;
  73.         }
  74.         low <<= 1;
  75.         high <<= 1;
  76.         high++;
  77.     }
  78. }
  79.  
  80. int
  81. arith_end_encoding(ac)
  82. ARITH_CODER *ac;
  83. {
  84.     int bit,i;
  85.  
  86.     ac->u.e.bits_to_follow++;
  87.     bit = (ac->low >= FIRST_QUARTER);
  88.     if (bit_plus_follow(ac,bit) < 0)
  89.         return -1;
  90.     for (i=0; i<CODE_VALUE_BITS-2; i++)
  91.         if (ff_put1bit(ac->ff,0) < 0)
  92.             return -1;
  93.     return ff_end1bit(ac->ff);
  94. }
  95.  
  96. int
  97. arith_start_decoding(ac,ff)
  98. ARITH_CODER *ac; FFILE *ff;
  99. {
  100.     int i,bit;
  101.  
  102.     if (ff == NULL)
  103.         return -1;
  104.     ac->ff = ff;
  105.     ff_start1bit(ac->ff);
  106.     ac->low = 0L;
  107.     ac->high = TOP_VALUE;
  108.     ac->u.d.value = 0L;
  109.     for (i=0; i<CODE_VALUE_BITS; i++) {
  110.         if ((bit=ff_get1bit(ac->ff)) < 0)
  111.             return -1;
  112.         ac->u.d.value <<= 1;
  113.         ac->u.d.value |= bit;
  114.     }
  115.     return 0;
  116. }
  117.  
  118. int
  119. arith_decode_getrpos(ac,rtot)
  120. ARITH_CODER *ac; int rtot;
  121. {
  122.     return ((ac->u.d.value+1-ac->low)*rtot - 1) / (ac->high+1-ac->low);
  123. }
  124.  
  125. int
  126. arith_decode_advance(ac,rstart,rend,rtot)
  127. ARITH_CODER *ac; int rstart; int rend; int rtot;
  128. {
  129.     long iwidth;
  130.     int bit;
  131.     register unsigned int high,low,value;
  132.  
  133.     iwidth = ac->high+1-ac->low;
  134.     high = (unsigned int)(ac->low + (iwidth*rend)/rtot - 1);
  135.     low = (unsigned int)(ac->low + (iwidth*rstart)/rtot);
  136.     value = (unsigned int)ac->u.d.value;
  137.     for (;;) {
  138.         if (high < HALF)
  139.             /* NOTHING */;
  140.         else if (HALF <= low) {
  141.             value -= HALF;
  142.             low -= HALF;
  143.             high -= HALF;
  144.         } else if (FIRST_QUARTER<=low && high<THIRD_QUARTER) {
  145.             value -= FIRST_QUARTER;
  146.             low -= FIRST_QUARTER;
  147.             high -= FIRST_QUARTER;
  148.         } else {
  149.             ac->high = high;
  150.             ac->low = low;
  151.             ac->u.d.value = value;
  152.             return 0;
  153.         }
  154.         low <<= 1;
  155.         high <<= 1;
  156.         high++;
  157.         value <<= 1;
  158.         if ((bit=ff_get1bit(ac->ff)) < 0)
  159.             return -1;
  160.         value |= bit;
  161.     }
  162. }
  163.  
  164. int
  165. arith_end_decoding(ac)
  166. ARITH_CODER *ac;
  167. {
  168.     return ff_end1bit(ac->ff);
  169. }
  170.