home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / packery / bwt / src / ari.cpp next >
C/C++ Source or Header  |  1996-06-17  |  11KB  |  292 lines
  1. //
  2. //  ARI.CPP
  3. //
  4. //  Mark Nelson
  5. //  March 8, 1996
  6. //  http://web2.airmail.net/markn
  7. //
  8. // DESCRIPTION
  9. // -----------
  10. //
  11. //  This program performs an order-0 adaptive arithmetic encoding
  12. //  function on an input file/stream, and sends the result to an
  13. //  output file or stream.
  14. //
  15. //  This program contains the source code from the 1987 CACM
  16. //  article by Witten, Neal, and Cleary.  I have taken the
  17. //  source modules and combined them into this single file for
  18. //  ease of distribution and compilation.  Other than that,
  19. //  the code is essentially unchanged.
  20. //
  21. //  This program takes two arguments: an input file and an output
  22. //  file.  You can leave off one argument and send your output to
  23. //  stdout.  Leave off two arguments and read your input from stdin
  24. //  as well.
  25. //
  26. //  This program accompanies my article "Data Compression with the
  27. //  Burrows-Wheeler Transform."
  28. //
  29. // Build Instructions
  30. // ------------------
  31. //
  32. //  Define the constant unix for UNIX or UNIX-like systems.  The
  33. //  use of this constant turns off the code used to force the MS-DOS
  34. //  file system into binary mode.  g++ already does this, and your
  35. //  UNIX C++ compiler might also.
  36. //
  37. //  Borland C++ 4.5 16 bit    : bcc -w ari.cpp
  38. //  Borland C++ 4.5 32 bit    : bcc32 -w ari.cpp
  39. //  Microsoft Visual C++ 1.52 : cl /W4 ari.cpp
  40. //  Microsoft Visual C++ 2.1  : cl /W4 ari.cpp
  41. //  g++                       : g++ -o ari ari.cpp
  42. //
  43. // Typical Use
  44. // -----------
  45. //
  46. //  rle < raw-file | bwt | mtf | rle | ari > compressed-file
  47. //
  48. //
  49.  
  50. #define unix
  51.  
  52. #include <stdio.h>
  53. #include <stdlib.h>
  54. #if !defined( unix )
  55. #include <io.h>
  56. #endif
  57. #include <fcntl.h>
  58.  
  59. #define No_of_chars 256                 /* Number of character symbols      */
  60. #define EOF_symbol (No_of_chars+1)      /* Index of EOF symbol              */
  61.  
  62. #define No_of_symbols (No_of_chars+1)   /* Total number of symbols          */
  63.  
  64. /* TRANSLATION TABLES BETWEEN CHARACTERS AND SYMBOL INDEXES. */
  65.  
  66. int char_to_index[No_of_chars];         /* To index from character          */
  67. unsigned char index_to_char[No_of_symbols+1]; /* To character from index    */
  68.  
  69. /* ADAPTIVE SOURCE MODEL */
  70.  
  71. int freq[No_of_symbols+1];      /* Symbol frequencies                       */
  72. int cum_freq[No_of_symbols+1];  /* Cumulative symbol frequencies            */
  73.  
  74. /* DECLARATIONS USED FOR ARITHMETIC ENCODING AND DECODING */
  75.  
  76. /* SIZE OF ARITHMETIC CODE VALUES. */
  77.  
  78. #define Code_value_bits 16              /* Number of bits in a code value   */
  79. typedef long code_value;                /* Type of an arithmetic code value */
  80.  
  81. #define Top_value (((long)1<<Code_value_bits)-1)      /* Largest code value */
  82.  
  83.  
  84. /* HALF AND QUARTER POINTS IN THE CODE VALUE RANGE. */
  85.  
  86. #define First_qtr (Top_value/4+1)       /* Point after first quarter        */
  87. #define Half      (2*First_qtr)            /* Point after first half           */
  88. #define Third_qtr (3*First_qtr)         /* Point after third quarter        */
  89.  
  90.  
  91. /* CUMULATIVE FREQUENCY TABLE. */
  92.  
  93. #define Max_frequency 16383             /* Maximum allowed frequency count  */
  94.  
  95. extern int cum_freq[No_of_symbols+1];   /* Cumulative symbol frequencies    */
  96.  
  97.  
  98. void start_model( void );
  99. void start_encoding( void );
  100. void encode_symbol(int symbol,int cum_freq[] );
  101. void update_model(int symbol);
  102. void done_encoding( void );
  103. void done_outputing_bits( void );
  104.  
  105. /* BIT OUTPUT ROUTINES. */
  106.  
  107. /* THE BIT BUFFER. */
  108.  
  109. int buffer;                     /* Bits buffered for output                 */
  110. int bits_to_go;                 /* Number of bits free in buffer            */
  111.  
  112.  
  113. /* INITIALIZE FOR BIT OUTPUT. */
  114.  
  115. void start_outputing_bits( void )
  116. {   buffer = 0;                                 /* Buffer is empty to start */
  117.     bits_to_go= 8;                              /* with.                    */
  118. }
  119.  
  120. /* OUTPUT A BIT. */
  121.  
  122. inline void output_bit( int bit )
  123. {   buffer >>= 1; if (bit) buffer |= 0x80;      /* Put bit in top of buffer.*/
  124.     bits_to_go -= 1;
  125.     if (bits_to_go==0) {                        /* Output buffer if it is   */
  126.         putc( (char) buffer, stdout );          /* now full.                */
  127.         bits_to_go = 8;
  128.     }
  129. }
  130.  
  131. /* FLUSH OUT THE LAST BITS. */
  132.  
  133. void done_outputing_bits( void )
  134. {   putc( (char) ( buffer >> bits_to_go ),stdout);
  135. }
  136.  
  137. /* CURRENT STATE OF THE ENCODING. */
  138.  
  139. code_value low, high;           /* Ends of the current code region          */
  140. long bits_to_follow;            /* Number of opposite bits to output after  */
  141.                                 /* the next bit.                            */
  142. /* OUTPUT BITS PLUS FOLLOWING OPPOSITE BITS. */
  143.  
  144. void bit_plus_follow( int bit )
  145. {   output_bit(bit);                            /* Output the bit.          */
  146.     while (bits_to_follow>0) {
  147.         output_bit(!bit);                       /* Output bits_to_follow    */
  148.         bits_to_follow -= 1;                    /* opposite bits. Set       */
  149.     }                                           /* bits_to_follow to zero.  */
  150. }
  151.  
  152. int main( int argc, char *argv[] )
  153. {
  154.     int ticker = 0;
  155.  
  156.     fprintf( stderr, "Arithmetic coding on " );
  157.     if ( argc > 1 ) {
  158.         freopen( argv[ 1 ], "rb", stdin );
  159.         fprintf( stderr, "%s", argv[ 1 ] );
  160.     } else
  161.         fprintf( stderr, "stdin" );
  162.     fprintf( stderr, " to " );
  163.     if ( argc > 2 ) {
  164.         freopen( argv[ 2 ], "wb", stdout );
  165.         fprintf( stderr, "%s", argv[ 2 ] );
  166.     } else
  167.         fprintf( stderr, "stdout" );
  168.     fprintf( stderr, "\n" );
  169. #if !defined( unix )
  170.     setmode( fileno( stdin ), O_BINARY );
  171.     setmode( fileno( stdout ), O_BINARY );
  172. #endif
  173.     start_model();                              /* Set up other modules.    */
  174.     start_outputing_bits();
  175.     start_encoding();
  176.     for (;;) {                                  /* Loop through characters. */
  177.         int ch; int symbol;
  178.         if ( ( ticker++ % 1024 ) == 0 )
  179.             putc( '.', stderr );
  180.         ch = getc(stdin);                       /* Read the next character. */
  181.         if (ch==EOF) break;                     /* Exit loop on end-of-file.*/
  182.         symbol = char_to_index[ch];             /* Translate to an index.   */
  183.         encode_symbol(symbol,cum_freq);         /* Encode that symbol.      */
  184.         update_model(symbol);                   /* Update the model.        */
  185.     }
  186.     encode_symbol(EOF_symbol,cum_freq);         /* Encode the EOF symbol.   */
  187.     done_encoding();                            /* Send the last few bits.  */
  188.     done_outputing_bits();
  189.     putc( '\n', stderr );
  190.     return 0;
  191. }
  192.  
  193. /* ARITHMETIC ENCODING ALGORITHM. */
  194.  
  195.  
  196. /* START ENCODING A STREAM OF SYMBOLS. */
  197.  
  198. void start_encoding( void )
  199. {   low = 0;                                    /* Full code range.         */
  200.     high = Top_value;
  201.     bits_to_follow = 0;                         /* No bits to follow next.  */
  202. }
  203.  
  204.  
  205. /* ENCODE A SYMBOL. */
  206.  
  207. void encode_symbol(int symbol,int cum_freq[] )
  208. {   long range;                 /* Size of the current code region          */
  209.     range = (long)(high-low)+1;
  210.     high = low +                                /* Narrow the code region   */
  211.       (range*cum_freq[symbol-1])/cum_freq[0]-1; /* to that allotted to this */
  212.     low = low +                                 /* symbol.                  */
  213.       (range*cum_freq[symbol])/cum_freq[0];
  214.     for (;;) {                                  /* Loop to output bits.     */
  215.         if (high<Half) {
  216.             bit_plus_follow(0);                 /* Output 0 if in low half. */
  217.         }
  218.         else if (low>=Half) {                   /* Output 1 if in high half.*/
  219.             bit_plus_follow(1);
  220.             low -= Half;
  221.             high -= Half;                       /* Subtract offset to top.  */
  222.         }
  223.         else if (low>=First_qtr                 /* Output an opposite bit   */
  224.               && high<Third_qtr) {              /* later if in middle half. */
  225.             bits_to_follow += 1;
  226.             low -= First_qtr;                   /* Subtract offset to middle*/
  227.             high -= First_qtr;
  228.         }
  229.         else break;                             /* Otherwise exit loop.     */
  230.         low = 2*low;
  231.         high = 2*high+1;                        /* Scale up code range.     */
  232.     }
  233. }
  234.  
  235.  
  236. /* FINISH ENCODING THE STREAM. */
  237.  
  238. void done_encoding( void )
  239. {   bits_to_follow += 1;                        /* Output two bits that     */
  240.     if (low<First_qtr) bit_plus_follow(0);      /* select the quarter that  */
  241.     else bit_plus_follow(1);                    /* the current code range   */
  242. }                                               /* contains.                */
  243.  
  244.  
  245. /* THE ADAPTIVE SOURCE MODEL */
  246.  
  247. /* INITIALIZE THE MODEL. */
  248.  
  249. void start_model( void )
  250. {   int i;
  251.     for (i = 0; i<No_of_chars; i++) {           /* Set up tables that       */
  252.         char_to_index[i] = i+1;                 /* translate between symbol */
  253.         index_to_char[i+1] = (unsigned char) i; /* indexes and characters.  */
  254.     }
  255.     for (i = 0; i<=No_of_symbols; i++) {        /* Set up initial frequency */
  256.         freq[i] = 1;                            /* counts to be one for all */
  257.         cum_freq[i] = No_of_symbols-i;          /* symbols.                 */
  258.     }
  259.     freq[0] = 0;                                /* Freq[0] must not be the  */
  260. }                                               /* same as freq[1].         */
  261.  
  262.  
  263. /* UPDATE THE MODEL TO ACCOUNT FOR A NEW SYMBOL. */
  264.  
  265. void update_model( int symbol )
  266. {   int i;                      /* New index for symbol                     */
  267.     if (cum_freq[0]==Max_frequency) {           /* See if frequency counts  */
  268.         int cum;                                /* are at their maximum.    */
  269.         cum = 0;
  270.         for (i = No_of_symbols; i>=0; i--) {    /* If so, halve all the     */
  271.             freq[i] = (freq[i]+1)/2;            /* counts (keeping them     */
  272.             cum_freq[i] = cum;                  /* non-zero).               */
  273.             cum += freq[i];
  274.         }
  275.     }
  276.     for (i = symbol; freq[i]==freq[i-1]; i--) ; /* Find symbol's new index. */
  277.     if (i<symbol) {
  278.         int ch_i, ch_symbol;
  279.         ch_i = index_to_char[i];                /* Update the translation   */
  280.         ch_symbol = index_to_char[symbol];      /* tables if the symbol has */
  281.         index_to_char[i] = (unsigned char) ch_symbol;           /* moved.                   */
  282.         index_to_char[symbol] = (unsigned char) ch_i;
  283.         char_to_index[ch_i] = symbol;
  284.         char_to_index[ch_symbol] = i;
  285.     }
  286.     freq[i] += 1;                               /* Increment the frequency  */
  287.     while (i>0) {                               /* count for the symbol and */
  288.         i -= 1;                                 /* update the cumulative    */
  289.         cum_freq[i] += 1;                       /* frequencies.             */
  290.     }
  291. }
  292.