home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / packery / bwt / src / unbwt.cpp < prev    next >
C/C++ Source or Header  |  1996-06-17  |  8KB  |  238 lines
  1. //
  2. //  UNBWT.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 inverse Burrows-Wheeler transform on an input
  12. //  file or stream, and sends the result to an output file or stream.
  13. //
  14. //  While this program can be compiled in 16 bit mode, it might not
  15. //  be able to invert transforms created by a 32 bit program.  The
  16. //  16 bit program has to drop its block size quite a bit.  However,
  17. //  rewriting the code to use a huge buffer under MS-DOS might solve
  18. //  that problem.
  19. //
  20. //  This program takes two arguments: an input file and an output
  21. //  file.  You can leave off one argument and send your output to
  22. //  stdout.  Leave off two arguments and read your input from stdin
  23. //  as well.  You can also specify "-d" as the first argument to get
  24. //  a debug dump as well.
  25. //
  26. //  The UNBWT input consists of a series of blocks that look like this:
  27. //
  28. //  long byte_count |  ...data... | long first | long last
  29. //
  30. //  The byte_count refers to the number of data bytes.  The data
  31. //  itself is the "L" column from the sorted data.  "first" is the
  32. //  index where the first character from the buffer appears in the
  33. //  sorted output.  "last" is where the end-of-buffer special byte
  34. //  appears in the output buffer.  These blocks are repeated until
  35. //  an EOF indicates that everything is done.
  36. //
  37. //  This program accompanies my article "Data Compression with the
  38. //  Burrows-Wheeler Transform."  There is one major deviation from
  39. //  the text of the article in this implementation.  The BWT code
  40. //  creates a buffer of N+1 characters out of an input string of
  41. //  N charactes.  The last character is a special end-of-buffer
  42. //  character that makes sorting the input easier.  See BWT.CPP for
  43. //  details on how and why this works.
  44. //
  45. //  The end of buffer character has special implications for UNBWT.CPP,
  46. //  because we have to take note of its appearance in the data stream.
  47. //  The "last" index sent after the block indicates whhich position in
  48. //  the transformed buffer contains the virtual end-of-buffer character.
  49. //  All of the calculations I do in the program have to take into account
  50. //  the possible appearance of this virtual character in the input
  51. //  stream.
  52. //
  53. // Build Instructions
  54. // ------------------
  55. //
  56. //  Define the constant unix for UNIX or UNIX-like systems.  The
  57. //  use of this constant turns off the code used to force the MS-DOS
  58. //  file system into binary mode.  g++ already does this, your UNIX
  59. //  C++ compiler might also.
  60. //
  61. //  Borland C++ 4.5 16 bit    : bcc -w -ml unbwt.cpp
  62. //  Borland C++ 4.5 32 bit    : bcc32 -w unbwt.cpp
  63. //  Microsoft Visual C++ 1.5  : cl /W4 /AL unbwt.cpp
  64. //  Microsoft Visual C++ 4.0  : cl /W4 unbwt.cpp
  65. //  g++                       : g++ -o unbwt unbwt.cpp
  66. //
  67. // Typical Use
  68. // -----------
  69. //
  70. //  unari < compressed-file | unrle | unmtf | unbwt | unrle > raw-file
  71. //
  72.  
  73. #define unix
  74.  
  75. #include <stdio.h>
  76. #include <stdlib.h>
  77. #include <ctype.h>
  78. #include <limits.h>
  79. #include <fcntl.h>
  80. #if !defined( unix )
  81. #include <io.h>
  82. #endif
  83. #include <string.h>
  84.  
  85. #if ( INT_MAX == 32767 )
  86. #define BLOCK_SIZE 20000
  87. #else
  88. #define BLOCK_SIZE 200000
  89. #endif
  90.  
  91. unsigned char buffer[ BLOCK_SIZE + 1 ];
  92. unsigned int T[ BLOCK_SIZE + 1 ];
  93. long buflen;
  94. unsigned int Count[ 257 ];
  95. unsigned int RunningTotal[ 257 ];
  96.  
  97. main( int argc, char *argv[] )
  98. {
  99.     int debug = 0;
  100.     if ( argc > 1 && strcmp( argv[ 1 ], "-d" ) == 0 ) {
  101.         debug = 1;
  102.         argv++;
  103.         argc--;
  104.     }
  105.     fprintf( stderr, "Performing Inverse BWT on " );
  106.     if ( argc > 1 ) {
  107.         freopen( argv[ 1 ], "rb", stdin );
  108.         fprintf( stderr, "%s", argv[ 1 ] );
  109.     } else
  110.         fprintf( stderr, "stdin" );
  111.     fprintf( stderr, " to " );
  112.     if ( argc > 2 ) {
  113.         freopen( argv[ 2 ], "wb", stdout );
  114.         fprintf( stderr, "%s", argv[ 2 ] );
  115.     } else
  116.         fprintf( stderr, "stdout" );
  117.     fprintf( stderr, "\n" );
  118. #if !defined( unix )
  119.     setmode( fileno( stdin ), O_BINARY );
  120.     setmode( fileno( stdout ), O_BINARY );
  121. #endif
  122.  
  123.     for ( ; ; ) {
  124.         if ( fread( (char *) &buflen, sizeof( long ), 1, stdin ) == 0 )
  125.             break;
  126.         fprintf( stderr,
  127.                  "Processing %ld bytes\n",
  128.                  buflen );
  129.         if ( buflen > ( BLOCK_SIZE + 1 ) ) {
  130.             fprintf( stderr, "Buffer overflow!\n" );
  131.             abort();
  132.         }
  133.         if ( fread( (char *)buffer, 1, (size_t) buflen, stdin ) !=
  134.                  (size_t) buflen ) {
  135.             fprintf( stderr, "Error reading data\n" );
  136.             abort();
  137.         }
  138.         unsigned long first;
  139.         fread( (char *) &first, sizeof( long ), 1, stdin );
  140.         unsigned long last;
  141.         fread( (char *)&last, sizeof( long ), 1, stdin );
  142.         fprintf( stderr,
  143.                  "first = %lu, "
  144.                  "last = %lu\n",
  145.                  first, last );
  146. //
  147. // To determine a character's position in the output string given
  148. // its position in the input string, we can use the knowledge about
  149. // the fact that the output string is sorted.  Each character 'c' will
  150. // show up in the output stream in in position i, where i is the sum
  151. // total of all characters in the input buffer that precede c in the
  152. // alphabet, plus the count of all occurences of 'c' previously in the
  153. // input stream.
  154. //
  155. // The first part of this code calculates the running totals for all
  156. // the characters in the alphabet.  That satisfies the first part of the
  157. // equation needed to determine where each 'c' will go in the output
  158. // stream.  Remember that the character pointed to by 'last' is a special
  159. // end-of-buffer character that is supposed to be larger than any char
  160. // in the alphabet.
  161. //
  162.         unsigned int i;
  163.         for ( i = 0 ; i < 257 ; i++ )
  164.             Count[ i ] = 0;
  165.         for ( i = 0 ; i < (unsigned int) buflen ; i++ )
  166.             if ( i == last )
  167.                 Count[ 256 ]++;
  168.             else
  169.                 Count[ buffer[ i ] ]++;
  170.         if ( debug ) {
  171.             fprintf( stderr, "Byte Counts:\n" );
  172.             for ( i = 0 ; i <= 256 ; i++ )
  173.                 if ( Count[ i ] ) {
  174.                     if (isprint( i ) )
  175.                         fprintf( stderr, "%c  : ", i );
  176.                     else
  177.                         fprintf( stderr, "%3d: ", i );
  178.                     fprintf( stderr, "%u\n", Count[ i ] );
  179.                 }
  180.         }
  181.         int sum = 0;
  182.         if ( debug )
  183.             fprintf( stderr, "Running totals:\n" );
  184.         for ( i = 0 ; i < 257 ; i++ ) {
  185.             RunningTotal[ i ] = sum;
  186.             sum += Count[ i ];
  187.             if ( debug && Count[ i ] ) {
  188.                 if (isprint( i ) )
  189.                     fprintf( stderr, "%c  : ", i );
  190.                 else
  191.                     fprintf( stderr, "%3d: ", i );
  192.                 fprintf( stderr, "%u\n", (long) RunningTotal[ i ] );
  193.             }
  194.             Count[ i ] = 0;
  195.         }
  196. //
  197. // Now that the RunningTotal[] array is filled in, I have half the
  198. // information needed to position each 'c' in the input buffer.  The
  199. // next piece of information is simply the number of characters 'c'
  200. // that appear before this 'c' in the input stream.  I keep track of
  201. // that informatin in the Counts[] array as I go.  By adding those
  202. // two number together, I get the destination of each character in
  203. // the input buffer, and that allows me to fill in all the positions
  204. // in the transformation vector, T[].
  205. //
  206.         for ( i = 0 ; i < (unsigned int) buflen ; i++ ) {
  207.             int index;
  208.             if ( i == last )
  209.                 index = 256;
  210.             else
  211.                 index = buffer[ i ];
  212.             T[ Count[ index ] + RunningTotal[ index ] ] = i;
  213.             Count[ index ]++;
  214.         }
  215.         if ( debug ) {
  216.             fprintf( stderr, "T = " );
  217.             for ( i = 0 ; i < (unsigned int) buflen ; i++ )
  218.                 fprintf( stderr, "%u ", T[ i ] );
  219.             fprintf( stderr, "\n" );
  220.         }
  221. //
  222. // Once the transformation vector is in place, writing the
  223. // output is just a matter of following the indices.  Note
  224. // that I don't have to watch for the end-of-buffer character
  225. // here.  Since I am only outputting N characters, and I know
  226. // it will show up at position N+1, I know it won't pop up
  227. //
  228.         unsigned int j;
  229.         i = (unsigned int) first;
  230.         for ( j = 0 ; j < (unsigned int) ( buflen - 1 ) ; j++ ) {
  231.             putc( buffer[ i ], stdout );
  232.             i = T[ i ];
  233.         }
  234.     }
  235.     return 1;
  236. }
  237.  
  238.