home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / packery / bwt / src / bwta.cpp < prev    next >
C/C++ Source or Header  |  1996-04-20  |  10KB  |  267 lines
  1. //
  2. //  BWTA.CPP
  3. //
  4. //  Mark Nelson
  5. //  March 8, 1996
  6. //  http://web2.airmail.net/markn
  7. //
  8. // DESCRIPTION
  9. // -----------
  10. //
  11. //  This program performs a 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 will suffer
  15. //  greatly by virtue of the fact that it will need to drop its
  16. //  block size tremendously.
  17. //
  18. //  This program takes two arguments: an input file and an output
  19. //  file.  You can leave off one argument and send your output to
  20. //  stdout.  Leave off two arguments and read your input from stdin
  21. //  as well.  You can also specify "-d" as the first argument to get
  22. //  a debug dump as well.  However, the debug listing can be a little
  23. //  overwhelming if you are working on a large file!
  24. //
  25. //  The output consists of a series of blocks that look like this:
  26. //
  27. //  long byte_count |  ...data... | long first | long last
  28. //
  29. //  The byte_count refers to the number of data bytes.  The data
  30. //  itself is the "L" column from the sorted data.  "first" is the
  31. //  index where the first character from the buffer appears in the
  32. //  sorted output.  "last" is where the end-of-buffer special byte
  33. //  appears in the output buffer.  These blocks are repeated until
  34. //  I'm out of data.
  35. //
  36. //  This program accompanies my article "Data Compression with the
  37. //  Burrows-Wheeler Transform."  There is one major deviation from
  38. //  the text of the article in this implementation.  To simplify the
  39. //  sorting, I append a special end-of-buffer character to the end
  40. //  of the input buffer.  The end-of-buffer character isn't found
  41. //  in the buffer, which means I no longer have to wrap around to
  42. //  the start of the buffer when performing comparisons.  Instead,
  43. //  I'm guaranteed that a memcmp() will terminate at or before the
  44. //  last character in the buffer.
  45. //
  46. //  One problem, though.  Since I can handle any kind of binary input,
  47. //  what character is guaranteed to never appear in the buffer?  None,
  48. //  so instead I do a special hack and make sure I never *really*
  49. //  look at that last position when comparing.  Instead, I only compare
  50. //  until one or the other string gets to the end, then award the
  51. //  comparison to whoever hit the end first.
  52. //
  53. //  This special character means the output has N+1 characters.  I just
  54. //  output a '?' when I hit that special end-of-buffer character, but
  55. //  I also have to pass along the information about the end-of-buffer
  56. //  character's position to the decoder, so I append it to the end
  57. //  of each data block.
  58. //
  59. //  The sorting for this routine is done by inserting pointers into
  60. //  the buffer into an STL set.  There are two good things about this.
  61. //  First, I can create a templated comparison function which is then
  62. //  called in-line during the insertion.  Second, since I insert each
  63. //  string one at a time, I can provide some indication to the end user
  64. //  of how far along in the process I am.  With a function like qsort(),
  65. //  it's hard to know how far along you are.
  66. //
  67. //  If you don't have an STL capable compiler, you are going to have to
  68. //  use the less-sexy version of this program, BWTA.CPP.
  69. //
  70. // Build Instructions
  71. // ------------------
  72. //
  73. //  Borland C++ 4.5 16 bit    : bcc -w -ml bwt.cpp  //Yes, large model!
  74. //  Borland C++ 4.5 32 bit    : bcc32 -w bwt.cpp
  75. //  Microsoft Visual C++ 4.0  : ???? haven't had a chance to test it
  76. //
  77. //  This code has not been tested under UNIX.  I don't have a g++
  78. //  testbed that supports the STL.
  79. //
  80. // Typical Use
  81. // -----------
  82. //
  83. //  rle < raw-file | bwta | mtf | rle | ari > compressed-file
  84. //
  85.  
  86. //
  87. // Borland STL hack
  88. //
  89. #define __MINMAX_DEFINED
  90.  
  91. //
  92. // set.h is an STL file.  If you don't have the STL on your system,
  93. // you can expect an error here.
  94. //
  95. #include <set.h>
  96.  
  97. #include <stdio.h>
  98. #include <ctype.h>
  99. #include <string.h>
  100. #include <fcntl.h>
  101. #include <io.h>
  102. #include <limits.h>
  103.  
  104. #if ( INT_MAX == 32767 )
  105. #define BLOCK_SIZE 20000
  106. #else
  107. #define BLOCK_SIZE 200000
  108. #endif
  109.  
  110. //
  111. // length has the number of bytes presently read into the buffer,
  112. // buffer contains the data itself.
  113. //
  114. long length;
  115. unsigned char buffer[ BLOCK_SIZE ];
  116.  
  117. //
  118. // This is the special comparison function used when inserting
  119. // strings into the sorted set.  Remember that the character
  120. // at buffer+length doesn't really exist, but it is assumed to
  121. // be the special end-of-buffer character, which is bigger than
  122. // any character found in the input buffer.  So I terminate the
  123. // comparison at the end of the buffer.
  124. //
  125. class BoundedCompare {
  126.     public :
  127.         operator()( const unsigned char *p1,
  128.                     const unsigned char *p2 ) const
  129.         {
  130.             unsigned int l1 = (unsigned int) (( buffer - p1 ) + length );
  131.             unsigned int l2 = (unsigned int) (( buffer - p2 ) + length );
  132.             int result = memcmp( p1, p2, min( l1, l2 ) );
  133.             if ( result < 0 )
  134.                 return 1;
  135.             if ( result > 0 )
  136.                 return 0;
  137.             return l1 > l2;
  138.         }
  139. };
  140.  
  141.  
  142. main( int argc, char *argv[] )
  143. {
  144.     int debug = 0;
  145.     if ( argc > 1 && strcmp( argv[ 1 ], "-d" ) == 0 ) {
  146.         debug = 1;
  147.         argv++;
  148.         argc--;
  149.     }
  150.     fprintf( stderr, "Performing BWT on " );
  151.     if ( argc > 1 ) {
  152.         freopen( argv[ 1 ], "rb", stdin );
  153.         fprintf( stderr, "%s", argv[ 1 ] );
  154.     } else
  155.         fprintf( stderr, "stdin" );
  156.     fprintf( stderr, " to " );
  157.     if ( argc > 2 ) {
  158.         freopen( argv[ 2 ], "wb", stdout );
  159.         fprintf( stderr, "%s", argv[ 2 ] );
  160.     } else
  161.         fprintf( stderr, "stdout" );
  162.     fprintf( stderr, "\n" );
  163.     setmode( fileno( stdin ), O_BINARY );
  164.     setmode( fileno( stdout ), O_BINARY );
  165. //
  166. // This is the start of the giant outer loop.  Each pass
  167. // through the loop compresses up to BLOCK_SIZE characters.
  168. // When an fread() operation finally reads in 0 characters,
  169. // we break out of the loop and are done.
  170. //
  171.     for ( ; ; ) {
  172. //
  173. // After reading in the data into the buffer, I do some
  174. // UI stuff, then write the length out to the output
  175. // stream.
  176. //
  177.         length = fread( buffer, 1, BLOCK_SIZE, stdin );
  178.         if ( length == 0 )
  179.             break;
  180.         fprintf( stderr, "Performing BWT on %ld bytes\n", length );
  181.         long l = length + 1;
  182.         fwrite( &l, 1, sizeof( long ), stdout );
  183. //
  184. // Sorting the input strings is simply a matter of inserting
  185. // a pointer to each string into an STL set<> container.
  186. // The sorting is done by operator()() in the BoundedCompare
  187. // class.  Note that I insert N+1 pointers. The last pointer
  188. // points one past the end of the buffer, which is where the
  189. // imaginary end-of-buffer character resides.  Sort of.
  190. //
  191.         int i;
  192.         int ticker = 0;
  193.         set< unsigned char *, BoundedCompare > p;
  194.         for ( i = 0 ; i <= length ; i++ ) {
  195.             if ( ( ticker++ % 1024 ) == 0 )
  196.                 fprintf( stderr, "." );
  197.             p.insert( buffer + i );
  198.         }
  199.         fprintf( stderr, "\n" );
  200.         set< unsigned char *, BoundedCompare >::iterator ii;
  201. //
  202. // If the debug flag was turned on, I print out the sorted
  203. // strings, along with their prefix characters.  This is
  204. // not a very good idea when you are compressing a giant
  205. // binary file, but it can be real helpful when debugging.
  206. //
  207.         if ( debug ) {
  208.             for ( ii = p.begin(), i = 0 ; ii != p.end() ; ii++, i++ ) {
  209.                 unsigned char *s = *ii;
  210.                 fprintf( stderr, "%d : " );
  211.                 unsigned char prefix;
  212.                 if ( s == buffer )
  213.                     prefix = '?';
  214.                 else
  215.                     prefix = s[ -1 ];
  216.                 if ( isprint( prefix ) )
  217.                     fprintf( stderr, "%c", prefix );
  218.                 else
  219.                     fprintf( stderr, "<%d>", prefix );
  220.                 fprintf( stderr, ": " );
  221.                 int stop = (int)( ( buffer - s ) + length );
  222.                 if ( stop > 30 )
  223.                     stop = 30;
  224.                 for ( int j = 0 ; j < stop ; j++ ) {
  225.                     if ( isprint( *s ) )
  226.                         fprintf( stderr, "%c", *s );
  227.                     else
  228.                         fprintf( stderr, "<%d>", *s );
  229.                     s++;
  230.                 }
  231.                 fprintf( stderr, "\n" );
  232.             }
  233.         }
  234. //
  235. // Finally, I write out column L.  Column L consists of all
  236. // the prefix characters to the sorted strings, in order.
  237. // It's easy to get the prefix character, but I have to
  238. // handle S0 with care, since its prefix character is the
  239. // imaginary end-of-buffer character.  I also have to spot
  240. // the positions in L of the end-of-buffer character and
  241. // the first character, so I can write them out at the end
  242. // for transmission to the output stream.
  243. //
  244.         long first;
  245.         long last;
  246.         for ( i = 0, ii = p.begin() ; ii != p.end() ; i++, ii++ ) {
  247.             if ( *ii == ( buffer + 1 ) )
  248.                 first = i;
  249.             if ( *ii == buffer ) {
  250.                 last = i;
  251.                 fputc( '?', stdout );
  252.             } else
  253.                 fputc( (*ii)[ -1 ], stdout );
  254.         }
  255.         p.erase( p.begin(), p.end() );
  256.         fprintf( stderr,
  257.                  "first = %ld"
  258.                  "  last = %ld\n",
  259.                  first,
  260.                  last );
  261.         fwrite( &first, 1, sizeof( long ), stdout );
  262.         fwrite( &last, 1, sizeof( long ), stdout );
  263.     }
  264.     return 0;
  265. }
  266.  
  267.