home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / packery / bwt / src / bwt.cpp < prev    next >
C/C++ Source or Header  |  1996-06-12  |  10KB  |  299 lines
  1. //
  2. //  BWT.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.
  22. //
  23. //  The output consists of a series of blocks that look like this:
  24. //
  25. //  long byte_count |  ...data... | long first | long last
  26. //
  27. //  The byte_count refers to the number of data bytes.  The data
  28. //  itself is the "L" column from the sorted data.  "first" is the
  29. //  index where the first character from the buffer appears in the
  30. //  sorted output.  "last" is where the end-of-buffer special byte
  31. //  appears in the output buffer.  These blocks are repeated until
  32. //  I'm out of data.
  33. //
  34. //  This program accompanies my article "Data Compression with the
  35. //  Burrows-Wheeler Transform."  There is one major deviation from
  36. //  the text of the article in this implementation.  To simplify the
  37. //  sorting, I append a special end-of-buffer character to the end
  38. //  of the input buffer.  The end-of-buffer character isn't found
  39. //  in the buffer, which means I no longer have to wrap around to
  40. //  the start of the buffer when performing comparisons.  Instead,
  41. //  I'm guaranteed that a memcmp() will terminate at or before the
  42. //  last character in the buffer.
  43. //
  44. //  One problem, though.  Since I can handle any kind of binary input,
  45. //  what character is guaranteed to never appear in the buffer?  None,
  46. //  so instead I do a special hack and make sure I never *really*
  47. //  look at that last position when comparing.  Instead, I only compare
  48. //  until one or the other string gets to the end, then award the
  49. //  comparison to whoever hit the end first.
  50. //
  51. //  This special character means the output has N+1 characters.  I just
  52. //  output a '?' when I hit that special end-of-buffer character, but
  53. //  I also have to pass along the information about the end-of-buffer
  54. //  character's position to the decoder, so I append it to the end
  55. //  of each data block.
  56. //
  57. //  The sorting for this routine is done via conventional qsort().
  58. //  The STL capable version in BWT.CPP is neater, and in theory
  59. //  should run faster.  The comparison function here is nearly
  60. //  the same as that from BWT.CPP, but it isn't a template fn.  Also,
  61. //  instead of passing pointers into the buffer, the qsort() compare
  62. //  function gets indices.
  63. //
  64. // Build Instructions
  65. // ------------------
  66. //
  67. //  Define the constant unix for UNIX or UNIX-like systems.  The
  68. //  use of this constant turns off the code used to force the MS-DOS
  69. //  file system into binary mode.  g++ already does this, your UNIX
  70. //  C++ compiler might also.
  71. //
  72. //  Microsoft Visual C++ 2.x  : cl /W4 bwta.cpp
  73. //  Borland C++ 4.5 32 bit    : bcc32 -w bwt.cpp
  74. //  Microsoft Visual C++ 1.52 : cl /W4 bwt.cpp
  75. //  Microsoft Visual C++ 2.1  : cl /W4 bwt.cpp
  76. //  g++                       : g++ -o bwt bwt.cpp
  77. //
  78. // Typical Use
  79. // -----------
  80. //
  81. //  rle < raw-file | bwt | mtf | rle | ari > compressed-file
  82. //
  83.  
  84. #define unix
  85.  
  86. #include <stdio.h>
  87. #include <stdlib.h>
  88. #include <ctype.h>
  89. #include <string.h>
  90. #include <fcntl.h>
  91. #if !defined( unix )
  92. #include <io.h>
  93. #endif
  94. #include <limits.h>
  95.  
  96. #if ( INT_MAX == 32767 )
  97. #define BLOCK_SIZE 20000
  98. #else
  99. #define BLOCK_SIZE 200000
  100. #endif
  101.  
  102. //
  103. // length has the number of bytes presently read into the buffer,
  104. // buffer contains the data itself.  indices[] is an array of
  105. // indices into the buffer.  indices[] is what gets sorted in
  106. // order to sort all the strings in the buffer.
  107. //
  108. long length;
  109. unsigned char buffer[ BLOCK_SIZE ];
  110. int indices[ BLOCK_SIZE + 1 ];
  111.  
  112. //
  113. // The logic in unbwt.cpp depends upon the strings having been
  114. // sorted as unsigned characters.  Some versions of memcmp() sort
  115. // using *signed* characters.  When this is the case, I compare
  116. // using this special replacement version of memcmp().
  117. //
  118. int memcmp_signed;
  119.  
  120. int unsigned_memcmp( void *p1, void *p2, unsigned int i )
  121. {
  122.     unsigned char *pc1 = (unsigned char *) p1;
  123.     unsigned char *pc2 = (unsigned char *) p2;
  124.     while ( i-- ) {
  125.         if ( *pc1 < *pc2 )
  126.             return -1;
  127.         else if ( *pc1++ > *pc2++ )
  128.             return 1;
  129.     }
  130.     return 0;
  131. }
  132.  
  133. //
  134. // This is the special comparison function used when calling
  135. // qsort() to sort the array of indices into the buffer. Remember that
  136. // the character at buffer+length doesn't really exist, but it is assumed
  137. // to be the special end-of-buffer character, which is bigger than
  138. // any character found in the input buffer.  So I terminate the
  139. // comparison at the end of the buffer.
  140. //
  141.  
  142. int
  143. #if defined( _MSC_VER )
  144. _cdecl
  145. #endif
  146. bounded_compare( const unsigned int *i1,
  147.                  const unsigned int *i2 )
  148. {
  149.     static int ticker = 0;
  150.     if ( ( ticker++ % 4096 ) == 0 )
  151.         fprintf( stderr, "." );
  152.     unsigned int l1 = (unsigned int) ( length - *i1 );
  153.     unsigned int l2 = (unsigned int) ( length - *i2 );
  154.     int result;
  155.     if ( memcmp_signed )
  156.         result = unsigned_memcmp( buffer + *i1,
  157.                                   buffer + *i2,
  158.                                   l1 < l2 ? l1 : l2 );
  159.     else
  160.         result = memcmp( buffer + *i1,
  161.                          buffer + *i2,
  162.                          l1 < l2 ? l1 : l2 );
  163.     if ( result == 0 )
  164.         return l2 - l1;
  165.     else
  166.         return result;
  167. };
  168.  
  169.  
  170. main( int argc, char *argv[] )
  171. {
  172.     int debug = 0;
  173.     if ( argc > 1 && strcmp( argv[ 1 ], "-d" ) == 0 ) {
  174.         debug = 1;
  175.         argv++;
  176.         argc--;
  177.     }
  178.     fprintf( stderr, "Performing BWT on " );
  179.     if ( argc > 1 ) {
  180.         freopen( argv[ 1 ], "rb", stdin );
  181.         fprintf( stderr, "%s", argv[ 1 ] );
  182.     } else
  183.         fprintf( stderr, "stdin" );
  184.     fprintf( stderr, " to " );
  185.     if ( argc > 2 ) {
  186.         freopen( argv[ 2 ], "wb", stdout );
  187.         fprintf( stderr, "%s", argv[ 2 ] );
  188.     } else
  189.         fprintf( stderr, "stdout" );
  190.     fprintf( stderr, "\n" );
  191. #if !defined( unix )
  192.     setmode( fileno( stdin ), O_BINARY );
  193.     setmode( fileno( stdout ), O_BINARY );
  194. #endif
  195.     if ( memcmp( "\x070", "\x080", 1 ) < 0 ) {
  196.         memcmp_signed = 0;
  197.         fprintf( stderr, "memcmp() treats character data as unsigned\n" );
  198.     } else {
  199.         memcmp_signed = 1;
  200.         fprintf( stderr, "memcmp() treats character data as signed\n" );
  201.     }
  202. //
  203. // This is the start of the giant outer loop.  Each pass
  204. // through the loop compresses up to BLOCK_SIZE characters.
  205. // When an fread() operation finally reads in 0 characters,
  206. // we break out of the loop and are done.
  207. //
  208.     for ( ; ; ) {
  209. //
  210. // After reading in the data into the buffer, I do some
  211. // UI stuff, then write the length out to the output
  212. // stream.
  213. //
  214.         length = fread( (char *) buffer, 1, BLOCK_SIZE, stdin );
  215.         if ( length == 0 )
  216.             break;
  217.         fprintf( stderr, "Performing BWT on %ld bytes\n", length );
  218.         long l = length + 1;
  219.         fwrite( (char *) &l, 1, sizeof( long ), stdout );
  220. //
  221. // Sorting the input strings is simply a matter of inserting
  222. // the indices into the array, then calling qsort() with the
  223. // special bounded_compare() function I wrote to work with
  224. // these string types.  Note that I sort N+1 indices. The last index
  225. // points one past the end of the buffer, which is where the
  226. // imaginary end-of-buffer character resides.  Sort of.
  227. //
  228.         int i;
  229.         for ( i = 0 ; i <= length ; i++ )
  230.             indices[ i ] = i;
  231.         qsort( indices,
  232.                (int)( length + 1 ),
  233.                sizeof( int ),
  234.                ( int (*)(const void *, const void *) ) bounded_compare );
  235.         fprintf( stderr, "\n" );
  236. //
  237. // If the debug flag was turned on, I print out the sorted
  238. // strings, along with their prefix characters.  This is
  239. // not a very good idea when you are compressing a giant
  240. // binary file, but it can be real helpful when debugging.
  241. //
  242.         if ( debug ) {
  243.             for ( i = 0 ; i <= length ; i++ ) {
  244.                 fprintf( stderr, "%d : ", i );
  245.                 unsigned char prefix;
  246.                 if ( indices[ i ] == 0 )
  247.                     prefix = '?';
  248.                 else
  249.                     prefix = (unsigned char) buffer[ indices[ i ] - 1 ];
  250.                 if ( isprint( prefix ) )
  251.                     fprintf( stderr, "%c", prefix );
  252.                 else
  253.                     fprintf( stderr, "<%d>", prefix );
  254.                 fprintf( stderr, ": " );
  255.                 int stop = (int)( length - indices[ i ] );
  256.                 if ( stop > 30 )
  257.                     stop = 30;
  258.                 for ( int j = 0 ; j < stop ; j++ ) {
  259.                     if ( isprint( buffer[ indices[ i ] + j ] ) )
  260.                         fprintf( stderr, "%c", buffer[ indices[ i ] + j ] );
  261.                     else
  262.                         fprintf( stderr, "<%d>", buffer[ indices[ i ] + j ] );
  263.                 }
  264.                 fprintf( stderr, "\n" );
  265.             }
  266.         }
  267. //
  268. // Finally, I write out column L.  Column L consists of all
  269. // the prefix characters to the sorted strings, in order.
  270. // It's easy to get the prefix character, but I have to
  271. // handle S0 with care, since its prefix character is the
  272. // imaginary end-of-buffer character.  I also have to spot
  273. // the positions in L of the end-of-buffer character and
  274. // the first character, so I can write them out at the end
  275. // for transmission to the output stream.
  276. //
  277.         long first;
  278.         long last;
  279.         for ( i = 0 ; i <= length ; i++ ) {
  280.             if ( indices[ i ] == 1 )
  281.                 first = i;
  282.             if ( indices[ i ] == 0 ) {
  283.                 last = i;
  284.                 fputc( '?', stdout );
  285.             } else
  286.                 fputc( buffer[ indices[ i ] - 1 ], stdout );
  287.         }
  288.         fprintf( stderr,
  289.                  "first = %ld"
  290.                  "  last = %ld\n",
  291.                  first,
  292.                  last );
  293.         fwrite( (char *) &first, 1, sizeof( long ), stdout );
  294.         fwrite( (char *) &last, 1, sizeof( long ), stdout );
  295.     }
  296.     return 0;
  297. }
  298.  
  299.