home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / packery / bwt / src / unari.cpp < prev    next >
C/C++ Source or Header  |  1996-06-17  |  10KB  |  286 lines
  1. //
  2. //  UNARI.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 decoding
  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++ does this already, your UNIX
  35. //  C++ compiler might also.
  36. //
  37. //  Borland C++ 4.5 16 bit    : bcc -w unari.cpp
  38. //  Borland C++ 4.5 32 bit    : bcc32 -w unari.cpp
  39. //  Microsoft Visual C++ 1.52 : cl /W4 unari.cpp
  40. //  Microsoft Visual C++ 2.1  : cl /W4 unari.cpp
  41. //  g++                       : g++ -o unari unari.cpp
  42. //
  43. // Typical Use
  44. // -----------
  45. //
  46. //  unari < compressed-file | unrle | unmtf | unbwt | unrle > raw-file
  47. //
  48. //
  49.  
  50. #define unix
  51.  
  52. #include <stdio.h>
  53. #include <stdlib.h>
  54. #include <fcntl.h>
  55. #if !defined( unix )
  56. #include <io.h>
  57. #endif
  58.  
  59. /* THE SET OF SYMBOLS THAT MAY BE ENCODED. */
  60.  
  61. #define No_of_chars 256                 /* Number of character symbols      */
  62. #define EOF_symbol (No_of_chars+1)      /* Index of EOF symbol              */
  63.  
  64. #define No_of_symbols (No_of_chars+1)   /* Total number of symbols          */
  65.  
  66.  
  67. /* TRANSLATION TABLES BETWEEN CHARACTERS AND SYMBOL INDEXES. */
  68.  
  69. int char_to_index[No_of_chars];         /* To index from character          */
  70. unsigned char index_to_char[No_of_symbols+1]; /* To character from index    */
  71.  
  72. int freq[No_of_symbols+1];      /* Symbol frequencies                       */
  73. int cum_freq[No_of_symbols+1];  /* Cumulative symbol frequencies            */
  74.  
  75. /* CUMULATIVE FREQUENCY TABLE. */
  76.  
  77. #define Max_frequency 16383             /* Maximum allowed frequency count  */
  78.  
  79. /* DECLARATIONS USED FOR ARITHMETIC ENCODING AND DECODING */
  80.  
  81.  
  82. /* SIZE OF ARITHMETIC CODE VALUES. */
  83.  
  84. #define Code_value_bits 16              /* Number of bits in a code value   */
  85. typedef long code_value;                /* Type of an arithmetic code value */
  86.  
  87. #define Top_value (((long)1<<Code_value_bits)-1)      /* Largest code value */
  88.  
  89.  
  90. /* HALF AND QUARTER POINTS IN THE CODE VALUE RANGE. */
  91.  
  92. #define First_qtr (Top_value/4+1)       /* Point after first quarter        */
  93. #define Half      (2*First_qtr)         /* Point after first half           */
  94. #define Third_qtr (3*First_qtr)         /* Point after third quarter        */
  95.  
  96.  
  97. /* BIT INPUT ROUTINES. */
  98.  
  99. /* THE BIT BUFFER. */
  100.  
  101. int buffer;                     /* Bits waiting to be input                 */
  102. int bits_to_go;                 /* Number of bits still in buffer           */
  103. int garbage_bits;               /* Number of bits past end-of-file          */
  104.  
  105.  
  106. /* INITIALIZE BIT INPUT. */
  107.  
  108. void start_inputing_bits( void )
  109. {   bits_to_go = 0;                             /* Buffer starts out with   */
  110.     garbage_bits = 0;                           /* no bits in it.           */
  111. }
  112.  
  113.  
  114. /* INPUT A BIT. */
  115.  
  116. inline int input_bit( void )
  117. {   int t;
  118.     if (bits_to_go==0) {                        /* Read the next byte if no */
  119.         buffer = getc(stdin);                   /* bits are left in buffer. */
  120.         if (buffer==EOF) {
  121.             garbage_bits += 1;                      /* Return arbitrary bits*/
  122.             if (garbage_bits>Code_value_bits-2) {   /* after eof, but check */
  123.                 fprintf(stderr,"Bad input file\n"); /* for too many such.   */
  124.                 exit(-1);
  125.             }
  126.         }
  127.         bits_to_go = 8;
  128.     }
  129.     t = buffer&1;                               /* Return the next bit from */
  130.     buffer >>= 1;                               /* the bottom of the byte.  */
  131.     bits_to_go -= 1;
  132.     return t;
  133. }
  134.  
  135.  
  136. void start_model( void );
  137. void start_decoding( void );
  138. int decode_symbol( int cum_freq[] );
  139. void update_model( int symbol );
  140.  
  141. int main( int argc, char *argv[] )
  142. {
  143.     int ticker = 0;
  144.  
  145.     fprintf( stderr, "Arithmetic decoding on " );
  146.     if ( argc > 1 ) {
  147.         freopen( argv[ 1 ], "rb", stdin );
  148.         fprintf( stderr, "%s", argv[ 1 ] );
  149.     } else
  150.         fprintf( stderr, "stdin" );
  151.     fprintf( stderr, " to " );
  152.     if ( argc > 2 ) {
  153.         freopen( argv[ 2 ], "wb", stdout );
  154.         fprintf( stderr, "%s", argv[ 2 ] );
  155.     } else
  156.         fprintf( stderr, "stdout" );
  157.     fprintf( stderr, "\n" );
  158. #if !defined( unix )
  159.     setmode( fileno( stdin ), O_BINARY );
  160.     setmode( fileno( stdout ), O_BINARY );
  161. #endif
  162.  
  163.     start_model();                              /* Set up other modules.    */
  164.     start_inputing_bits();
  165.     start_decoding();
  166.     for (;;) {                                  /* Loop through characters. */
  167.         int ch; int symbol;
  168.         symbol = decode_symbol(cum_freq);       /* Decode next symbol.      */
  169.         if (symbol==EOF_symbol) break;          /* Exit loop if EOF symbol. */
  170.         ch = index_to_char[symbol];             /* Translate to a character.*/
  171.         if ( ( ticker++ % 1024 ) == 0 )
  172.             putc( '.', stderr );
  173.         putc((char) ch,stdout);                 /* Write that character.    */
  174.         update_model(symbol);                   /* Update the model.        */
  175.     }
  176.     putc( '\n', stderr );
  177.     return 1;
  178. }
  179.  
  180. /* ARITHMETIC DECODING ALGORITHM. */
  181.  
  182. /* CURRENT STATE OF THE DECODING. */
  183.  
  184. static code_value value;        /* Currently-seen code value                */
  185. static code_value low, high;    /* Ends of current code region              */
  186.  
  187. /* START DECODING A STREAM OF SYMBOLS. */
  188.  
  189. void start_decoding( void )
  190. {   int i;
  191.     value = 0;                                  /* Input bits to fill the   */
  192.     for (i = 1; i<=Code_value_bits; i++) {      /* code value.              */
  193.         value = 2*value+input_bit();
  194.     }
  195.     low = 0;                                    /* Full code range.         */
  196.     high = Top_value;
  197. }
  198.  
  199.  
  200. /* DECODE THE NEXT SYMBOL. */
  201.  
  202. int decode_symbol( int cum_freq[] )
  203. {   long range;                 /* Size of current code region              */
  204.     int cum;                    /* Cumulative frequency calculated          */
  205.     int symbol;                 /* Symbol decoded                           */
  206.     range = (long)(high-low)+1;
  207.     cum = (int)                                 /* Find cum freq for value. */
  208.       ((((long)(value-low)+1)*cum_freq[0]-1)/range);
  209.     for (symbol = 1; cum_freq[symbol]>cum; symbol++) ; /* Then find symbol. */
  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 get rid of bits. */
  215.         if (high<Half) {
  216.             /* nothing */                       /* Expand low half.         */
  217.         }
  218.         else if (low>=Half) {                   /* Expand high half.        */
  219.             value -= Half;
  220.             low -= Half;                        /* Subtract offset to top.  */
  221.             high -= Half;
  222.         }
  223.         else if (low>=First_qtr                 /* Expand middle half.      */
  224.               && high<Third_qtr) {
  225.             value -= First_qtr;
  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.         value = 2*value+input_bit();            /* Move in next input bit.  */
  233.     }
  234.     return symbol;
  235. }
  236.  
  237. /* THE ADAPTIVE SOURCE MODEL */
  238.  
  239. /* INITIALIZE THE MODEL. */
  240.  
  241. void start_model( void )
  242. {   int i;
  243.     for (i = 0; i<No_of_chars; i++) {           /* Set up tables that       */
  244.         char_to_index[i] = i+1;                 /* translate between symbol */
  245.         index_to_char[i+1] = (unsigned char) i; /* indexes and characters.  */
  246.     }
  247.     for (i = 0; i<=No_of_symbols; i++) {        /* Set up initial frequency */
  248.         freq[i] = 1;                            /* counts to be one for all */
  249.         cum_freq[i] = No_of_symbols-i;          /* symbols.                 */
  250.     }
  251.     freq[0] = 0;                                /* Freq[0] must not be the  */
  252. }                                               /* same as freq[1].         */
  253.  
  254.  
  255. /* UPDATE THE MODEL TO ACCOUNT FOR A NEW SYMBOL. */
  256.  
  257. void update_model( int symbol )
  258. {   int i;                      /* New index for symbol                     */
  259.     if (cum_freq[0]==Max_frequency) {           /* See if frequency counts  */
  260.         int cum;                                /* are at their maximum.    */
  261.         cum = 0;
  262.         for (i = No_of_symbols; i>=0; i--) {    /* If so, halve all the     */
  263.             freq[i] = (freq[i]+1)/2;            /* counts (keeping them     */
  264.             cum_freq[i] = cum;                  /* non-zero).               */
  265.             cum += freq[i];
  266.         }
  267.     }
  268.     for (i = symbol; freq[i]==freq[i-1]; i--) ; /* Find symbol's new index. */
  269.     if (i<symbol) {
  270.         int ch_i, ch_symbol;
  271.         ch_i = index_to_char[i];                /* Update the translation   */
  272.         ch_symbol = index_to_char[symbol];      /* tables if the symbol has */
  273.         index_to_char[i] = (unsigned char) ch_symbol; /* moved.             */
  274.         index_to_char[symbol] = (unsigned char) ch_i;
  275.         char_to_index[ch_i] = symbol;
  276.         char_to_index[ch_symbol] = i;
  277.     }
  278.     freq[i] += 1;                               /* Increment the frequency  */
  279.     while (i>0) {                               /* count for the symbol and */
  280.         i -= 1;                                 /* update the cumulative    */
  281.         cum_freq[i] += 1;                       /* frequencies.             */
  282.     }
  283. }
  284.  
  285.  
  286.