home *** CD-ROM | disk | FTP | other *** search
/ DOS/V Power Report 2002 November / VPR0211A.ISO / OLS / BZ2L003 / bz2l003.lzh / BZ2LIB / BZIP2.C < prev    next >
C/C++ Source or Header  |  1998-06-02  |  124KB  |  4,257 lines
  1. /*
  2.     bzip2.c
  3.  
  4.     This file is changed from bzip2-0.1pl2
  5.     for make bz2lib.(BZIP2 compress/de-compress library like zlib)
  6.     by Yoshioka Tsuneo(QWF00133@niftyserve.or.jp)
  7.     1998/03/28
  8.  
  9. */
  10. #include "bzip2.h"
  11. #include "bz2lib.h"
  12.  
  13. /*-----------------------------------------------------------*/
  14. /*--- A block-sorting, lossless compressor        bzip2.c ---*/
  15. /*-----------------------------------------------------------*/
  16.  
  17. /*--
  18.   This program is bzip2, a lossless, block-sorting data compressor,
  19.   version 0.1pl2, dated 29-Aug-1997.
  20.  
  21.   Copyright (C) 1996, 1997 by Julian Seward.
  22.      Guildford, Surrey, UK
  23.      email: jseward@acm.org
  24.  
  25.   This program is free software; you can redistribute it and/or modify
  26.   it under the terms of the GNU General Public License as published by
  27.   the Free Software Foundation; either version 2 of the License, or
  28.   (at your option) any later version.
  29.  
  30.   This program is distributed in the hope that it will be useful,
  31.   but WITHOUT ANY WARRANTY; without even the implied warranty of
  32.   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33.   GNU General Public License for more details.
  34.  
  35.   You should have received a copy of the GNU General Public License
  36.   along with this program; if not, write to the Free Software
  37.   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  38.  
  39.   The GNU General Public License is contained in the file LICENSE.
  40.  
  41.   This program is based on (at least) the work of:
  42.      Mike Burrows
  43.      David Wheeler
  44.      Peter Fenwick
  45.      Alistair Moffat
  46.      Radford Neal
  47.      Ian H. Witten
  48.      Robert Sedgewick
  49.      Jon L. Bentley
  50.  
  51.   For more information on these sources, see the file ALGORITHMS.
  52. --*/
  53.  
  54. /*----------------------------------------------------*/
  55. /*--- IMPORTANT                                    ---*/
  56. /*----------------------------------------------------*/
  57.  
  58. /*--
  59.    WARNING:
  60.       This program (attempts to) compress data by performing several
  61.       non-trivial transformations on it.  Unless you are 100% familiar
  62.       with *all* the algorithms contained herein, and with the
  63.       consequences of modifying them, you should NOT meddle with the
  64.       compression or decompression machinery.  Incorrect changes can
  65.       and very likely *will* lead to disasterous loss of data.
  66.  
  67.    DISCLAIMER:
  68.       I TAKE NO RESPONSIBILITY FOR ANY LOSS OF DATA ARISING FROM THE
  69.       USE OF THIS PROGRAM, HOWSOEVER CAUSED.
  70.  
  71.       Every compression of a file implies an assumption that the
  72.       compressed file can be decompressed to reproduce the original.
  73.       Great efforts in design, coding and testing have been made to
  74.       ensure that this program works correctly.  However, the
  75.       complexity of the algorithms, and, in particular, the presence
  76.       of various special cases in the code which occur with very low
  77.       but non-zero probability make it impossible to rule out the
  78.       possibility of bugs remaining in the program.  DO NOT COMPRESS
  79.       ANY DATA WITH THIS PROGRAM UNLESS YOU ARE PREPARED TO ACCEPT THE
  80.       POSSIBILITY, HOWEVER SMALL, THAT THE DATA WILL NOT BE RECOVERABLE.
  81.  
  82.       That is not to say this program is inherently unreliable.
  83.       Indeed, I very much hope the opposite is true.  bzip2 has been
  84.       carefully constructed and extensively tested.
  85.  
  86.    PATENTS:
  87.       To the best of my knowledge, bzip2 does not use any patented
  88.       algorithms.  However, I do not have the resources available to
  89.       carry out a full patent search.  Therefore I cannot give any
  90.       guarantee of the above statement.
  91. --*/
  92.  
  93.  
  94.  
  95. /*----------------------------------------------------*/
  96. /*--- and now for something much more pleasant :-) ---*/
  97. /*----------------------------------------------------*/
  98.  
  99. /*---------------------------------------------*/
  100. /*--
  101.   Place a 1 beside your platform, and 0 elsewhere.
  102. --*/
  103.  
  104. /*--
  105.   Generic 32-bit Unix.
  106.   Also works on 64-bit Unix boxes.
  107. --*/
  108. #ifndef _WIN32
  109. #define BZ_UNIX      1
  110. #endif
  111. /*--
  112.   Win32, as seen by Jacob Navia's excellent
  113.   port of (Chris Fraser & David Hanson)'s excellent
  114.   lcc compiler.
  115. --*/
  116. #ifdef _WIN32
  117. #define BZ_LCCWIN32  1
  118. #endif
  119.  
  120. /*---------------------------------------------*/
  121. /*--
  122.   Some stuff for all platforms.
  123. --*/
  124.  
  125. #include <stdio.h>
  126. #include <stdlib.h>
  127. #if DEBUG
  128.   #include <assert.h>
  129. #endif
  130. #include <string.h>
  131. #include <signal.h>
  132. #include <math.h>
  133.  
  134. #define ERROR_IF_EOF(i)       { if ((i) == EOF)  ioError(); }
  135. #define ERROR_IF_NOT_ZERO(i)  { if ((i) != 0)    ioError(); }
  136. #define ERROR_IF_MINUS_ONE(i) { if ((i) == (-1)) ioError(); }
  137.  
  138.  
  139. /*---------------------------------------------*/
  140. /*--
  141.    Platform-specific stuff.
  142. --*/
  143.  
  144. #if BZ_UNIX
  145.    #include <sys/types.h>
  146.    #include <utime.h>
  147.    #include <unistd.h>
  148.    #include <malloc.h>
  149.    #include <sys/stat.h>
  150.    #include <sys/times.h>
  151.  
  152.    #define Int32   int
  153.    #define UInt32  unsigned int
  154.    #define Char    char
  155.    #define UChar   unsigned char
  156.    #define Int16   short
  157.    #define UInt16  unsigned short
  158.  
  159.    #define PATH_SEP    '/'
  160.    #define MY_LSTAT    lstat
  161.    #define MY_S_IFREG  S_ISREG
  162.    #define MY_STAT     stat
  163.  
  164.    #define APPEND_FILESPEC(root, name) \
  165.       root=snocString((root), (name))
  166.  
  167.    #define SET_BINARY_MODE(fd) /**/
  168.  
  169.    /*--
  170.       You should try very hard to persuade your C compiler
  171.       to inline the bits marked INLINE.  Otherwise bzip2 will
  172.       run rather slowly.  gcc version 2.x is recommended.
  173.    --*/
  174.    #ifdef __GNUC__
  175.       #define INLINE   inline
  176.       #define NORETURN __attribute__ ((noreturn))
  177.    #else
  178.       #define INLINE   /**/
  179.       #define NORETURN /**/
  180.    #endif
  181. #endif
  182.  
  183.  
  184.  
  185. #if BZ_LCCWIN32
  186.    #include <io.h>
  187.    #include <fcntl.h>
  188.    #include <sys\stat.h>
  189.  
  190.    #define Int32   int
  191.    #define UInt32  unsigned int
  192.    #define Int16   short
  193.    #define UInt16  unsigned short
  194.    #define Char    char
  195.    #define UChar   unsigned char
  196.  
  197. #ifdef _MSC_VER
  198.    #define INLINE __inline
  199. #else
  200.    #define INLINE         /**/
  201. #endif
  202.    #define NORETURN       /**/
  203.    #define PATH_SEP       '\\'
  204.    #define MY_LSTAT       _stat
  205.    #define MY_STAT        _stat
  206.    #define MY_S_IFREG(x)  ((x) & _S_IFREG)
  207.  
  208.    #if 0
  209.    /*-- lcc-win32 seems to expand wildcards itself --*/
  210.    #define APPEND_FILESPEC(root, spec)                \
  211.       do {                                            \
  212.          if ((spec)[0] == '-') {                      \
  213.             root = snocString((root), (spec));        \
  214.          } else {                                     \
  215.             struct _finddata_t c_file;                \
  216.             long hFile;                               \
  217.             hFile = _findfirst((spec), &c_file);      \
  218.             if ( hFile == -1L ) {                     \
  219.                root = snocString ((root), (spec));    \
  220.             } else {                                  \
  221.                int anInt = 0;                         \
  222.                while ( anInt == 0 ) {                 \
  223.                   root = snocString((root),           \
  224.                             &c_file.name[0]);         \
  225.                   anInt = _findnext(hFile, &c_file);  \
  226.                }                                      \
  227.             }                                         \
  228.          }                                            \
  229.       } while ( 0 )
  230.    #else
  231.    #define APPEND_FILESPEC(root, name)                \
  232.       root = snocString ((root), (name))
  233.    #endif
  234.  
  235.    #define SET_BINARY_MODE(fd)                        \
  236.       do {                                            \
  237.          int retVal = setmode ( fileno ( fd ),        \
  238.                                O_BINARY );            \
  239.          ERROR_IF_MINUS_ONE ( retVal );               \
  240.       } while ( 0 )
  241.  
  242. #endif
  243.  
  244.  
  245. /*---------------------------------------------*/
  246. /*--
  247.   Some more stuff for all platforms :-)
  248. --*/
  249.  
  250. #define Bool   unsigned char
  251. #define True   1
  252. #define False  0
  253.  
  254. /*--
  255.   IntNative is your platform's `native' int size.
  256.   Only here to avoid probs with 64-bit platforms.
  257. --*/
  258. #define IntNative int
  259.  
  260.  
  261. /*--
  262.    change to 1, or compile with -DDEBUG=1 to debug
  263. --*/
  264. #ifndef DEBUG
  265. #define DEBUG 0
  266. #endif
  267.  
  268.  
  269. /*---------------------------------------------------*/
  270. /*---                                             ---*/
  271. /*---------------------------------------------------*/
  272.  
  273. /*--
  274.    Implementation notes, July 1997
  275.    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  276.  
  277.    Memory allocation
  278.    ~~~~~~~~~~~~~~~~~
  279.    All large data structures are allocated on the C heap,
  280.    for better or for worse.  That includes the various
  281.    arrays of pointers, striped words, bytes, frequency
  282.    tables and buffers for compression and decompression.
  283.  
  284.    bzip2 can operate at various block-sizes, ranging from
  285.    100k to 900k in 100k steps, and it allocates only as
  286.    much as it needs to.  When compressing, we know from the
  287.    command-line options what the block-size is going to be,
  288.    so all allocation can be done at start-up; if that
  289.    succeeds, there can be no further allocation problems.
  290.  
  291.    Decompression is more complicated.  Each compressed file
  292.    contains, in its header, a byte indicating the block
  293.    size used for compression.  This means bzip2 potentially
  294.    needs to reallocate memory for each file it deals with,
  295.    which in turn opens the possibility for a memory allocation
  296.    failure part way through a run of files, by encountering
  297.    a file requiring a much larger block size than all the
  298.    ones preceding it.
  299.  
  300.    The policy is to simply give up if a memory allocation
  301.    failure occurs.  During decompression, it would be
  302.    possible to move on to subsequent files in the hope that
  303.    some might ask for a smaller block size, but the
  304.    complications for doing this seem more trouble than they
  305.    are worth.
  306.  
  307.  
  308.    Compressed file formats
  309.    ~~~~~~~~~~~~~~~~~~~~~~~
  310.    [This is now entirely different from both 0.21, and from
  311.     any previous Huffman-coded variant of bzip.
  312.     See the associated file bzip2.txt for details.]
  313.  
  314.  
  315.    Error conditions
  316.    ~~~~~~~~~~~~~~~~
  317.    Dealing with error conditions is the least satisfactory
  318.    aspect of bzip2.  The policy is to try and leave the
  319.    filesystem in a consistent state, then quit, even if it
  320.    means not processing some of the files mentioned in the
  321.    command line.  `A consistent state' means that a file
  322.    exists either in its compressed or uncompressed form,
  323.    but not both.  This boils down to the rule `delete the
  324.    output file if an error condition occurs, leaving the
  325.    input intact'.  Input files are only deleted when we can
  326.    be pretty sure the output file has been written and
  327.    closed successfully.
  328.  
  329.    Errors are a dog because there's so many things to
  330.    deal with.  The following can happen mid-file, and
  331.    require cleaning up.
  332.  
  333.      internal `panics' -- indicating a bug
  334.      corrupted or inconsistent compressed file
  335.      can't allocate enough memory to decompress this file
  336.      I/O error reading/writing/opening/closing
  337.      signal catches -- Control-C, SIGTERM, SIGHUP.
  338.  
  339.    Other conditions, primarily pertaining to file names,
  340.    can be checked in-between files, which makes dealing
  341.    with them easier.
  342. --*/
  343.  
  344.  
  345.  
  346. /*---------------------------------------------------*/
  347. /*--- Misc (file handling) data decls             ---*/
  348. /*---------------------------------------------------*/
  349.  
  350. static UInt32  bytesIn, bytesOut;
  351. static Int32   verbosity;
  352. static Bool    keepInputFiles, smallMode, testFailsExist;
  353. static UInt32  globalCrc;
  354. static Int32   numFileNames, numFilesProcessed;
  355.  
  356.  
  357. /*-- source modes; F==file, I==stdin, O==stdout --*/
  358. #define SM_I2O           1
  359. #define SM_F2O           2
  360. #define SM_F2F           3
  361.  
  362. /*-- operation modes --*/
  363. #define OM_Z             1
  364. #define OM_UNZ           2
  365. #define OM_TEST          3
  366.  
  367. static Int32   opMode;
  368. static Int32   srcMode;
  369.  
  370.  
  371. static Int32   longestFileName;
  372. static Char    inName[1024];
  373. static Char    outName[1024];
  374. static Char    *progName;
  375. static Char    progNameReally[1024];
  376. static FILE    *outputHandleJustInCase;
  377.  
  378. static void    panic                 ( Char* )          NORETURN;
  379. static void    ioError               ( void )           NORETURN;
  380. static void    compressOutOfMemory   ( Int32, Int32 )   NORETURN;
  381. static void    uncompressOutOfMemory ( Int32, Int32 )   NORETURN;
  382. static void    blockOverrun          ( void )           NORETURN;
  383. static void    badBlockHeader        ( void )           NORETURN;
  384. static void    badBGLengths          ( void )           NORETURN;
  385. static void    crcError              ( UInt32, UInt32 ) NORETURN;
  386. static void    bitStreamEOF          ( void )           NORETURN;
  387. static void    cleanUpAndFail        ( Int32 )          NORETURN;
  388. static void    compressedStreamEOF   ( void )           NORETURN;
  389.  
  390. static void*   myMalloc ( Int32 );
  391.  
  392.  
  393.  
  394. /*---------------------------------------------------*/
  395. /*--- Data decls for the front end                ---*/
  396. /*---------------------------------------------------*/
  397.  
  398. /*--
  399.    The overshoot bytes allow us to avoid most of
  400.    the cost of pointer renormalisation during
  401.    comparison of rotations in sorting.
  402.    The figure of 20 is derived as follows:
  403.       qSort3 allows an overshoot of up to 10.
  404.       It then calls simpleSort, which calls
  405.       fullGtU, also with max overshoot 10.
  406.       fullGtU does up to 10 comparisons without
  407.       renormalising, giving 10+10 == 20.
  408. --*/
  409. #define NUM_OVERSHOOT_BYTES 20
  410.  
  411. /*--
  412.   These are the main data structures for
  413.   the Burrows-Wheeler transform.
  414. --*/
  415.  
  416. /*--
  417.   Pointers to compression and decompression
  418.   structures.  Set by
  419.      allocateCompressStructures   and
  420.      setDecompressStructureSizes
  421.  
  422.   The structures are always set to be suitable
  423.   for a block of size 100000 * blockSize100k.
  424. --*/
  425. static UChar    *block;    /*-- compress   --*/
  426. static UInt16   *quadrant; /*-- compress   --*/
  427. static Int32    *zptr;     /*-- compress   --*/ 
  428. static UInt16   *szptr;    /*-- overlays zptr ---*/
  429. static Int32    *ftab;     /*-- compress   --*/
  430.  
  431. static UInt16   *ll16;     /*-- small decompress --*/
  432. static UChar    *ll4;      /*-- small decompress --*/
  433.  
  434. static Int32    *tt;       /*-- fast decompress  --*/
  435. static UChar    *ll8;      /*-- fast decompress  --*/
  436.  
  437.  
  438. /*--
  439.   freq table collected to save a pass over the data
  440.   during decompression.
  441. --*/
  442. static Int32   unzftab[256];
  443.  
  444.  
  445. /*--
  446.    index of the last char in the block, so
  447.    the block size == last + 1.
  448. --*/
  449. static Int32  last;
  450.  
  451.  
  452. /*--
  453.   index in zptr[] of original string after sorting.
  454. --*/
  455. static Int32  origPtr;
  456.  
  457.  
  458. /*--
  459.   always: in the range 0 .. 9.
  460.   The current block size is 100000 * this number.
  461. --*/
  462. static Int32  blockSize100k;
  463.  
  464.  
  465. /*--
  466.   Used when sorting.  If too many long comparisons
  467.   happen, we stop sorting, randomise the block 
  468.   slightly, and try again.
  469. --*/
  470.  
  471. static Int32  workFactor = 30;
  472. static Int32  workDone;
  473. static Int32  workLimit;
  474. static Bool   blockRandomised;
  475. static Bool   firstAttempt;
  476. static Int32  nBlocksRandomised;
  477.  
  478.  
  479.  
  480. /*---------------------------------------------------*/
  481. /*--- Data decls for the back end                 ---*/
  482. /*---------------------------------------------------*/
  483.  
  484. #define MAX_ALPHA_SIZE 258
  485. #define MAX_CODE_LEN    23
  486.  
  487. #define RUNA 0
  488. #define RUNB 1
  489.  
  490. #define N_GROUPS 6
  491. #define G_SIZE   50
  492. #define N_ITERS  4
  493.  
  494. #define MAX_SELECTORS (2 + (900000 / G_SIZE))
  495.  
  496. static Bool  inUse[256];
  497. static Int32 nInUse;
  498.  
  499. static UChar seqToUnseq[256];
  500. static UChar unseqToSeq[256];
  501.  
  502. static UChar selector   [MAX_SELECTORS];
  503. static UChar selectorMtf[MAX_SELECTORS];
  504.  
  505. static Int32 nMTF;
  506.  
  507. static Int32 mtfFreq[MAX_ALPHA_SIZE];
  508.  
  509. static UChar len  [N_GROUPS][MAX_ALPHA_SIZE];
  510.  
  511. /*-- decompress only --*/
  512. static Int32 limit  [N_GROUPS][MAX_ALPHA_SIZE];
  513. static Int32 base   [N_GROUPS][MAX_ALPHA_SIZE];
  514. static Int32 perm   [N_GROUPS][MAX_ALPHA_SIZE];
  515. static Int32 minLens[N_GROUPS];
  516.  
  517. /*-- compress only --*/
  518. static Int32  code [N_GROUPS][MAX_ALPHA_SIZE];
  519. static Int32  rfreq[N_GROUPS][MAX_ALPHA_SIZE];
  520.  
  521.  
  522. /*---------------------------------------------------*/
  523. /*--- 32-bit CRC grunge                           ---*/
  524. /*---------------------------------------------------*/
  525.  
  526. /*--
  527.   I think this is an implementation of the AUTODIN-II,
  528.   Ethernet & FDDI 32-bit CRC standard.  Vaguely derived
  529.   from code by Rob Warnock, in Section 51 of the
  530.   comp.compression FAQ.
  531. --*/
  532.  
  533. static UInt32 crc32Table[256] = {
  534.  
  535.    /*-- Ugly, innit? --*/
  536.  
  537.    0x00000000UL, 0x04c11db7UL, 0x09823b6eUL, 0x0d4326d9UL,
  538.    0x130476dcUL, 0x17c56b6bUL, 0x1a864db2UL, 0x1e475005UL,
  539.    0x2608edb8UL, 0x22c9f00fUL, 0x2f8ad6d6UL, 0x2b4bcb61UL,
  540.    0x350c9b64UL, 0x31cd86d3UL, 0x3c8ea00aUL, 0x384fbdbdUL,
  541.    0x4c11db70UL, 0x48d0c6c7UL, 0x4593e01eUL, 0x4152fda9UL,
  542.    0x5f15adacUL, 0x5bd4b01bUL, 0x569796c2UL, 0x52568b75UL,
  543.    0x6a1936c8UL, 0x6ed82b7fUL, 0x639b0da6UL, 0x675a1011UL,
  544.    0x791d4014UL, 0x7ddc5da3UL, 0x709f7b7aUL, 0x745e66cdUL,
  545.    0x9823b6e0UL, 0x9ce2ab57UL, 0x91a18d8eUL, 0x95609039UL,
  546.    0x8b27c03cUL, 0x8fe6dd8bUL, 0x82a5fb52UL, 0x8664e6e5UL,
  547.    0xbe2b5b58UL, 0xbaea46efUL, 0xb7a96036UL, 0xb3687d81UL,
  548.    0xad2f2d84UL, 0xa9ee3033UL, 0xa4ad16eaUL, 0xa06c0b5dUL,
  549.    0xd4326d90UL, 0xd0f37027UL, 0xddb056feUL, 0xd9714b49UL,
  550.    0xc7361b4cUL, 0xc3f706fbUL, 0xceb42022UL, 0xca753d95UL,
  551.    0xf23a8028UL, 0xf6fb9d9fUL, 0xfbb8bb46UL, 0xff79a6f1UL,
  552.    0xe13ef6f4UL, 0xe5ffeb43UL, 0xe8bccd9aUL, 0xec7dd02dUL,
  553.    0x34867077UL, 0x30476dc0UL, 0x3d044b19UL, 0x39c556aeUL,
  554.    0x278206abUL, 0x23431b1cUL, 0x2e003dc5UL, 0x2ac12072UL,
  555.    0x128e9dcfUL, 0x164f8078UL, 0x1b0ca6a1UL, 0x1fcdbb16UL,
  556.    0x018aeb13UL, 0x054bf6a4UL, 0x0808d07dUL, 0x0cc9cdcaUL,
  557.    0x7897ab07UL, 0x7c56b6b0UL, 0x71159069UL, 0x75d48ddeUL,
  558.    0x6b93dddbUL, 0x6f52c06cUL, 0x6211e6b5UL, 0x66d0fb02UL,
  559.    0x5e9f46bfUL, 0x5a5e5b08UL, 0x571d7dd1UL, 0x53dc6066UL,
  560.    0x4d9b3063UL, 0x495a2dd4UL, 0x44190b0dUL, 0x40d816baUL,
  561.    0xaca5c697UL, 0xa864db20UL, 0xa527fdf9UL, 0xa1e6e04eUL,
  562.    0xbfa1b04bUL, 0xbb60adfcUL, 0xb6238b25UL, 0xb2e29692UL,
  563.    0x8aad2b2fUL, 0x8e6c3698UL, 0x832f1041UL, 0x87ee0df6UL,
  564.    0x99a95df3UL, 0x9d684044UL, 0x902b669dUL, 0x94ea7b2aUL,
  565.    0xe0b41de7UL, 0xe4750050UL, 0xe9362689UL, 0xedf73b3eUL,
  566.    0xf3b06b3bUL, 0xf771768cUL, 0xfa325055UL, 0xfef34de2UL,
  567.    0xc6bcf05fUL, 0xc27dede8UL, 0xcf3ecb31UL, 0xcbffd686UL,
  568.    0xd5b88683UL, 0xd1799b34UL, 0xdc3abdedUL, 0xd8fba05aUL,
  569.    0x690ce0eeUL, 0x6dcdfd59UL, 0x608edb80UL, 0x644fc637UL,
  570.    0x7a089632UL, 0x7ec98b85UL, 0x738aad5cUL, 0x774bb0ebUL,
  571.    0x4f040d56UL, 0x4bc510e1UL, 0x46863638UL, 0x42472b8fUL,
  572.    0x5c007b8aUL, 0x58c1663dUL, 0x558240e4UL, 0x51435d53UL,
  573.    0x251d3b9eUL, 0x21dc2629UL, 0x2c9f00f0UL, 0x285e1d47UL,
  574.    0x36194d42UL, 0x32d850f5UL, 0x3f9b762cUL, 0x3b5a6b9bUL,
  575.    0x0315d626UL, 0x07d4cb91UL, 0x0a97ed48UL, 0x0e56f0ffUL,
  576.    0x1011a0faUL, 0x14d0bd4dUL, 0x19939b94UL, 0x1d528623UL,
  577.    0xf12f560eUL, 0xf5ee4bb9UL, 0xf8ad6d60UL, 0xfc6c70d7UL,
  578.    0xe22b20d2UL, 0xe6ea3d65UL, 0xeba91bbcUL, 0xef68060bUL,
  579.    0xd727bbb6UL, 0xd3e6a601UL, 0xdea580d8UL, 0xda649d6fUL,
  580.    0xc423cd6aUL, 0xc0e2d0ddUL, 0xcda1f604UL, 0xc960ebb3UL,
  581.    0xbd3e8d7eUL, 0xb9ff90c9UL, 0xb4bcb610UL, 0xb07daba7UL,
  582.    0xae3afba2UL, 0xaafbe615UL, 0xa7b8c0ccUL, 0xa379dd7bUL,
  583.    0x9b3660c6UL, 0x9ff77d71UL, 0x92b45ba8UL, 0x9675461fUL,
  584.    0x8832161aUL, 0x8cf30badUL, 0x81b02d74UL, 0x857130c3UL,
  585.    0x5d8a9099UL, 0x594b8d2eUL, 0x5408abf7UL, 0x50c9b640UL,
  586.    0x4e8ee645UL, 0x4a4ffbf2UL, 0x470cdd2bUL, 0x43cdc09cUL,
  587.    0x7b827d21UL, 0x7f436096UL, 0x7200464fUL, 0x76c15bf8UL,
  588.    0x68860bfdUL, 0x6c47164aUL, 0x61043093UL, 0x65c52d24UL,
  589.    0x119b4be9UL, 0x155a565eUL, 0x18197087UL, 0x1cd86d30UL,
  590.    0x029f3d35UL, 0x065e2082UL, 0x0b1d065bUL, 0x0fdc1becUL,
  591.    0x3793a651UL, 0x3352bbe6UL, 0x3e119d3fUL, 0x3ad08088UL,
  592.    0x2497d08dUL, 0x2056cd3aUL, 0x2d15ebe3UL, 0x29d4f654UL,
  593.    0xc5a92679UL, 0xc1683bceUL, 0xcc2b1d17UL, 0xc8ea00a0UL,
  594.    0xd6ad50a5UL, 0xd26c4d12UL, 0xdf2f6bcbUL, 0xdbee767cUL,
  595.    0xe3a1cbc1UL, 0xe760d676UL, 0xea23f0afUL, 0xeee2ed18UL,
  596.    0xf0a5bd1dUL, 0xf464a0aaUL, 0xf9278673UL, 0xfde69bc4UL,
  597.    0x89b8fd09UL, 0x8d79e0beUL, 0x803ac667UL, 0x84fbdbd0UL,
  598.    0x9abc8bd5UL, 0x9e7d9662UL, 0x933eb0bbUL, 0x97ffad0cUL,
  599.    0xafb010b1UL, 0xab710d06UL, 0xa6322bdfUL, 0xa2f33668UL,
  600.    0xbcb4666dUL, 0xb8757bdaUL, 0xb5365d03UL, 0xb1f740b4UL
  601. };
  602.  
  603.  
  604. /*---------------------------------------------*/
  605. INLINE static void initialiseCRC ( void )
  606. {
  607.    globalCrc = 0xffffffffUL;
  608. }
  609.  
  610.  
  611. /*---------------------------------------------*/
  612. INLINE static UInt32 getFinalCRC ( void )
  613. {
  614.    return ~globalCrc;
  615. }
  616.  
  617.  
  618. /*---------------------------------------------*/
  619. INLINE static UInt32 getGlobalCRC ( void )
  620. {
  621.    return globalCrc;
  622. }
  623.  
  624.  
  625. /*---------------------------------------------*/
  626. INLINE static void setGlobalCRC ( UInt32 newCrc )
  627. {
  628.    globalCrc = newCrc;
  629. }
  630.  
  631.  
  632. /*---------------------------------------------*/
  633. #define UPDATE_CRC(crcVar,cha)              \
  634. {                                           \
  635.    crcVar = (crcVar << 8) ^                 \
  636.             crc32Table[(crcVar >> 24) ^     \
  637.                        ((UChar)cha)];       \
  638. }
  639.  
  640.  
  641. /*---------------------------------------------------*/
  642. /*--- Bit stream I/O                              ---*/
  643. /*---------------------------------------------------*/
  644.  
  645.  
  646. static UInt32 bsBuff;
  647. Int32  bsLive;
  648. FILE*  bsStream;
  649. Bool   bsWriting;
  650.  
  651.  
  652. /*---------------------------------------------*/
  653. INLINE static void bsSetStream ( FILE* f, Bool wr )
  654. {
  655.    if (bsStream != NULL) panic ( "bsSetStream" );
  656.    bsStream = f;
  657.    bsLive = 0;
  658.    bsBuff = 0;
  659.    bytesOut = 0;
  660.    bytesIn = 0;
  661.    bsWriting = wr;
  662. }
  663.  
  664.  
  665. /*---------------------------------------------*/
  666. INLINE static void bsFinishedWithStream ( void )
  667. {
  668.    if (bsWriting)
  669.       while (bsLive > 0) {
  670.          fputc ( (UChar)(bsBuff >> 24), bsStream );
  671.          bsBuff <<= 8;
  672.          bsLive -= 8;
  673.          bytesOut++;
  674.       }
  675.    bsStream = NULL;
  676. }
  677.  
  678.  
  679. /*---------------------------------------------*/
  680. #define bsNEEDR(nz)                           \
  681. {                                             \
  682.    while (bsLive < nz) {                      \
  683.       Int32 zzi = fgetc ( bsStream );         \
  684.       if (zzi == EOF) compressedStreamEOF();  \
  685.       bsBuff = (bsBuff << 8) | (zzi & 0xffL); \
  686.       bsLive += 8;                            \
  687.    }                                          \
  688. }
  689.  
  690.  
  691. /*---------------------------------------------*/
  692. /*
  693. #define bsNEEDW(nz)                           \
  694. {                                             \
  695.    while (bsLive >= 8) {                      \
  696.       fputc ( (UChar)(bsBuff >> 24),          \
  697.                bsStream );                    \
  698.       bsBuff <<= 8;                           \
  699.       bsLive -= 8;                            \
  700.       bytesOut++;                             \
  701.    }                                          \
  702. }*/
  703.  
  704. INLINE static void bsNEEDW(nz)
  705. {
  706.     while (bsLive >= 8) {
  707.       fputc ( (UChar)(bsBuff >> 24),          
  708.                bsStream );                    
  709.       bsBuff <<= 8;                           
  710.       bsLive -= 8;                            
  711.       bytesOut++;                             
  712.    }                                          
  713. }
  714.  
  715. /*---------------------------------------------*/
  716. #define bsR1(vz)                              \
  717. {                                             \
  718.    bsNEEDR(1);                                \
  719.    vz = (bsBuff >> (bsLive-1)) & 1;           \
  720.    bsLive--;                                  \
  721. }
  722.  
  723.  
  724. /*---------------------------------------------*/
  725. INLINE static UInt32 bsR ( Int32 n )
  726. {
  727.    UInt32 v;
  728.    bsNEEDR ( n );
  729.    v = (bsBuff >> (bsLive-n)) & ((1 << n)-1);
  730.    bsLive -= n;
  731.    return v;
  732. }
  733.  
  734.  
  735. /*---------------------------------------------*/
  736. INLINE static void bsW ( Int32 n, UInt32 v )
  737. {
  738.    bsNEEDW ( n );
  739.    bsBuff |= (v << (32 - bsLive - n));
  740.    bsLive += n;
  741. }
  742.  
  743.  
  744. /*---------------------------------------------*/
  745. INLINE static UChar bsGetUChar ( void )
  746. {
  747.    return (UChar)bsR(8);
  748. }
  749.  
  750.  
  751. /*---------------------------------------------*/
  752. INLINE static void bsPutUChar ( UChar c )
  753. {
  754.    bsW(8, (UInt32)c );
  755. }
  756.  
  757.  
  758. /*---------------------------------------------*/
  759. INLINE static Int32 bsGetUInt32 ( void )
  760. {
  761.    UInt32 u;
  762.    u = 0;
  763.    u = (u << 8) | bsR(8);
  764.    u = (u << 8) | bsR(8);
  765.    u = (u << 8) | bsR(8);
  766.    u = (u << 8) | bsR(8);
  767.    return u;
  768. }
  769.  
  770.  
  771. /*---------------------------------------------*/
  772. INLINE static UInt32 bsGetIntVS ( UInt32 numBits )
  773. {
  774.    return (UInt32)bsR(numBits);
  775. }
  776.  
  777.  
  778. /*---------------------------------------------*/
  779. INLINE static UInt32 bsGetInt32 ( void )
  780. {
  781.    return (Int32)bsGetUInt32();
  782. }
  783.  
  784.  
  785. /*---------------------------------------------*/
  786. INLINE static void bsPutUInt32 ( UInt32 u )
  787. {
  788.    bsW ( 8, (u >> 24) & 0xffL );
  789.    bsW ( 8, (u >> 16) & 0xffL );
  790.    bsW ( 8, (u >>  8) & 0xffL );
  791.    bsW ( 8,  u        & 0xffL );
  792. }
  793.  
  794.  
  795. /*---------------------------------------------*/
  796. INLINE static void bsPutInt32 ( Int32 c )
  797. {
  798.    bsPutUInt32 ( (UInt32)c );
  799. }
  800.  
  801.  
  802. /*---------------------------------------------*/
  803. INLINE static void bsPutIntVS ( Int32 numBits, UInt32 c )
  804. {
  805.    bsW ( numBits, c );
  806. }
  807.  
  808.  
  809. /*---------------------------------------------------*/
  810. /*--- Huffman coding low-level stuff              ---*/
  811. /*---------------------------------------------------*/
  812.  
  813. #define WEIGHTOF(zz0)  ((zz0) & 0xffffff00)
  814. #define DEPTHOF(zz1)   ((zz1) & 0x000000ff)
  815. #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
  816.  
  817. #define ADDWEIGHTS(zw1,zw2)                           \
  818.    (WEIGHTOF(zw1)+WEIGHTOF(zw2)) |                    \
  819.    (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
  820.  
  821. #define UPHEAP(z)                                     \
  822. {                                                     \
  823.    Int32 zz, tmp;                                     \
  824.    zz = z; tmp = heap[zz];                            \
  825.    while (weight[tmp] < weight[heap[zz >> 1]]) {      \
  826.       heap[zz] = heap[zz >> 1];                       \
  827.       zz >>= 1;                                       \
  828.    }                                                  \
  829.    heap[zz] = tmp;                                    \
  830. }
  831.  
  832. #define DOWNHEAP(z)                                   \
  833. {                                                     \
  834.    Int32 zz, yy, tmp;                                 \
  835.    zz = z; tmp = heap[zz];                            \
  836.    while (True) {                                     \
  837.       yy = zz << 1;                                   \
  838.       if (yy > nHeap) break;                          \
  839.       if (yy < nHeap &&                               \
  840.           weight[heap[yy+1]] < weight[heap[yy]])      \
  841.          yy++;                                        \
  842.       if (weight[tmp] < weight[heap[yy]]) break;      \
  843.       heap[zz] = heap[yy];                            \
  844.       zz = yy;                                        \
  845.    }                                                  \
  846.    heap[zz] = tmp;                                    \
  847. }
  848.  
  849.  
  850. /*---------------------------------------------*/
  851. static void hbMakeCodeLengths ( UChar *len, 
  852.                          Int32 *freq,
  853.                          Int32 alphaSize,
  854.                          Int32 maxLen )
  855. {
  856.    /*--
  857.       Nodes and heap entries run from 1.  Entry 0
  858.       for both the heap and nodes is a sentinel.
  859.    --*/
  860.    Int32 nNodes, nHeap, n1, n2, i, j, k;
  861.    Bool  tooLong;
  862.  
  863.    Int32 heap   [ MAX_ALPHA_SIZE + 2 ];
  864.    Int32 weight [ MAX_ALPHA_SIZE * 2 ];
  865.    Int32 parent [ MAX_ALPHA_SIZE * 2 ]; 
  866.  
  867.    for (i = 0; i < alphaSize; i++)
  868.       weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
  869.  
  870.    while (True) {
  871.  
  872.       nNodes = alphaSize;
  873.       nHeap = 0;
  874.  
  875.       heap[0] = 0;
  876.       weight[0] = 0;
  877.       parent[0] = -2;
  878.  
  879.       for (i = 1; i <= alphaSize; i++) {
  880.          parent[i] = -1;
  881.          nHeap++;
  882.          heap[nHeap] = i;
  883.          UPHEAP(nHeap);
  884.       }
  885.       if (!(nHeap < (MAX_ALPHA_SIZE+2))) 
  886.          panic ( "hbMakeCodeLengths(1)" );
  887.    
  888.       while (nHeap > 1) {
  889.          n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
  890.          n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
  891.          nNodes++;
  892.          parent[n1] = parent[n2] = nNodes;
  893.          weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
  894.          parent[nNodes] = -1;
  895.          nHeap++;
  896.          heap[nHeap] = nNodes;
  897.          UPHEAP(nHeap);
  898.       }
  899.       if (!(nNodes < (MAX_ALPHA_SIZE * 2)))
  900.          panic ( "hbMakeCodeLengths(2)" );
  901.  
  902.       tooLong = False;
  903.       for (i = 1; i <= alphaSize; i++) {
  904.          j = 0;
  905.          k = i;
  906.          while (parent[k] >= 0) { k = parent[k]; j++; }
  907.          len[i-1] = j;
  908.          if (j > maxLen) tooLong = True;
  909.       }
  910.       
  911.       if (! tooLong) break;
  912.  
  913.       for (i = 1; i < alphaSize; i++) {
  914.          j = weight[i] >> 8;
  915.          j = 1 + (j / 2);
  916.          weight[i] = j << 8;
  917.       }
  918.    }
  919. }
  920.  
  921.  
  922. /*---------------------------------------------*/
  923. static void hbAssignCodes ( Int32 *code,
  924.                      UChar *length,
  925.                      Int32 minLen,
  926.                      Int32 maxLen,
  927.                      Int32 alphaSize )
  928. {
  929.    Int32 n, vec, i;
  930.  
  931.    vec = 0;
  932.    for (n = minLen; n <= maxLen; n++) {
  933.       for (i = 0; i < alphaSize; i++)
  934.          if (length[i] == n) { code[i] = vec; vec++; };
  935.       vec <<= 1;
  936.    }
  937. }
  938.  
  939.  
  940. /*---------------------------------------------*/
  941. static void hbCreateDecodeTables ( Int32 *limit,
  942.                             Int32 *base,
  943.                             Int32 *perm,
  944.                             UChar *length,
  945.                             Int32 minLen,
  946.                             Int32 maxLen,
  947.                             Int32 alphaSize )
  948. {
  949.    Int32 pp, i, j, vec;
  950.  
  951.    pp = 0;
  952.    for (i = minLen; i <= maxLen; i++)
  953.       for (j = 0; j < alphaSize; j++)
  954.          if (length[j] == i) { perm[pp] = j; pp++; };
  955.  
  956.    for (i = 0; i < MAX_CODE_LEN; i++) base[i] = 0;
  957.    for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
  958.  
  959.    for (i = 1; i < MAX_CODE_LEN; i++) base[i] += base[i-1];
  960.  
  961.    for (i = 0; i < MAX_CODE_LEN; i++) limit[i] = 0;
  962.    vec = 0;
  963.  
  964.    for (i = minLen; i <= maxLen; i++) {
  965.       vec += (base[i+1] - base[i]);
  966.       limit[i] = vec-1;
  967.       vec <<= 1;
  968.    }
  969.    for (i = minLen + 1; i <= maxLen; i++)
  970.       base[i] = ((limit[i-1] + 1) << 1) - base[i];
  971. }
  972.  
  973.  
  974.  
  975. /*---------------------------------------------------*/
  976. /*--- Undoing the reversible transformation       ---*/
  977. /*---------------------------------------------------*/
  978.  
  979. /*---------------------------------------------*/
  980. #define SET_LL4(i,n)                                          \
  981.    { if (((i) & 0x1) == 0)                                    \
  982.         ll4[(i) >> 1] = (ll4[(i) >> 1] & 0xf0) | (n); else    \
  983.         ll4[(i) >> 1] = (ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
  984.    }
  985.  
  986. #define GET_LL4(i)                             \
  987.     (((UInt32)(ll4[(i) >> 1])) >> (((i) << 2) & 0x4) & 0xF)
  988.  
  989. #define SET_LL(i,n)                       \
  990.    { ll16[i] = (UInt16)(n & 0x0000ffff);  \
  991.      SET_LL4(i, n >> 16);                 \
  992.    }
  993.  
  994. #define GET_LL(i) \
  995.    (((UInt32)ll16[i]) | (GET_LL4(i) << 16))
  996.  
  997.  
  998. /*---------------------------------------------*/
  999. /*--
  1000.   Manage memory for compression/decompression.
  1001.   When compressing, a single block size applies to
  1002.   all files processed, and that's set when the
  1003.   program starts.  But when decompressing, each file
  1004.   processed could have been compressed with a
  1005.   different block size, so we may have to free
  1006.   and reallocate on a per-file basis.
  1007.  
  1008.   A call with argument of zero means
  1009.   `free up everything.'  And a value of zero for
  1010.   blockSize100k means no memory is currently allocated.
  1011. --*/
  1012.  
  1013.  
  1014. /*---------------------------------------------*/
  1015. static void allocateCompressStructures ( void )
  1016. {
  1017.    Int32 n  = 100000 * blockSize100k;
  1018.    block    = malloc ( (n + 1 + NUM_OVERSHOOT_BYTES) * sizeof(UChar) );
  1019.    quadrant = malloc ( (n     + NUM_OVERSHOOT_BYTES) * sizeof(Int16) );
  1020.    zptr     = malloc ( n                             * sizeof(Int32) );
  1021.    ftab     = malloc ( 65537                         * sizeof(Int32) );
  1022.  
  1023.    if (block == NULL || quadrant == NULL ||
  1024.        zptr == NULL  || ftab == NULL) {
  1025.       Int32 totalDraw
  1026.          = (n + 1 + NUM_OVERSHOOT_BYTES) * sizeof(UChar) +
  1027.            (n     + NUM_OVERSHOOT_BYTES) * sizeof(Int16) +
  1028.            n                             * sizeof(Int32) +
  1029.            65537                         * sizeof(Int32);
  1030.  
  1031.       compressOutOfMemory ( totalDraw, n );
  1032.    }
  1033.  
  1034.    /*--
  1035.       Since we want valid indexes for block of
  1036.       -1 to n + NUM_OVERSHOOT_BYTES - 1
  1037.       inclusive.
  1038.    --*/
  1039.    block++;
  1040.  
  1041.    /*--
  1042.       The back end needs a place to store the MTF values
  1043.       whilst it calculates the coding tables.  We could
  1044.       put them in the zptr array.  However, these values
  1045.       will fit in a short, so we overlay szptr at the 
  1046.       start of zptr, in the hope of reducing the number
  1047.       of cache misses induced by the multiple traversals
  1048.       of the MTF values when calculating coding tables.
  1049.       Seems to improve compression speed by about 1%.
  1050.    --*/
  1051.    szptr = (UInt16*)zptr;
  1052. }
  1053. static void freeCompressStructures ( void )
  1054. {
  1055.    if(block){block--;free(block);block=NULL;}  
  1056.    if(quadrant){free(quadrant);quadrant=NULL;}
  1057.    if(zptr){free(zptr);zptr=NULL;}
  1058.    if(ftab){free(ftab);ftab=NULL;}
  1059.  
  1060.    szptr = (UInt16*)zptr;
  1061. }
  1062.  
  1063.  
  1064. /*---------------------------------------------*/
  1065. static void setDecompressStructureSizes ( Int32 newSize100k )
  1066. {
  1067.    if (! (0 <= newSize100k   && newSize100k   <= 9 &&
  1068.           0 <= blockSize100k && blockSize100k <= 9))
  1069.       panic ( "setDecompressStructureSizes" );
  1070.  
  1071.    if (newSize100k == blockSize100k) return;
  1072.  
  1073.    blockSize100k = newSize100k;
  1074.  
  1075.    if (ll16  != NULL) free ( ll16  );
  1076.    if (ll4   != NULL) free ( ll4   );
  1077.    if (ll8   != NULL) free ( ll8   );
  1078.    if (tt    != NULL) free ( tt    );
  1079.  
  1080.    if (newSize100k == 0) return;
  1081.  
  1082.    if (smallMode) {
  1083.  
  1084.       Int32 n = 100000 * newSize100k;
  1085.       ll16    = malloc ( n * sizeof(UInt16) );
  1086.       ll4     = malloc ( ((n+1) >> 1) * sizeof(UChar) );
  1087.  
  1088.       if (ll4 == NULL || ll16 == NULL) {
  1089.          Int32 totalDraw
  1090.             = n * sizeof(Int16) + ((n+1) >> 1) * sizeof(UChar);
  1091.          uncompressOutOfMemory ( totalDraw, n );
  1092.       }
  1093.  
  1094.    } else {
  1095.  
  1096.       Int32 n = 100000 * newSize100k;
  1097.       ll8     = malloc ( n * sizeof(UChar) );
  1098.       tt      = malloc ( n * sizeof(Int32) );
  1099.  
  1100.       if (ll8 == NULL || tt == NULL) {
  1101.          Int32 totalDraw
  1102.             = n * sizeof(UChar) + n * sizeof(UInt32);
  1103.          uncompressOutOfMemory ( totalDraw, n );
  1104.       }
  1105.  
  1106.    }
  1107. }
  1108. static void unsetDecompressStructureSizes ()
  1109. {
  1110.     if (ll16  != NULL){free ( ll16  );ll16=NULL;}
  1111.     if (ll4   != NULL){free ( ll4   );ll4=NULL;}
  1112.     if (ll8   != NULL){free ( ll8   );ll8=NULL;}
  1113.     if (tt    != NULL){free ( tt    );tt=NULL;}
  1114. }
  1115.  
  1116.  
  1117.  
  1118. /*---------------------------------------------------*/
  1119. /*--- The new back end                            ---*/
  1120. /*---------------------------------------------------*/
  1121.  
  1122. /*---------------------------------------------*/
  1123. static void makeMaps ( void )
  1124. {
  1125.    Int32 i;
  1126.    nInUse = 0;
  1127.    for (i = 0; i < 256; i++)
  1128.       if (inUse[i]) {
  1129.          seqToUnseq[nInUse] = i;
  1130.          unseqToSeq[i] = nInUse;
  1131.          nInUse++;
  1132.       }
  1133. }
  1134.  
  1135.  
  1136. /*---------------------------------------------*/
  1137. static void generateMTFValues ( void )
  1138. {
  1139.    UChar  yy[256];
  1140.    Int32  i, j;
  1141.    UChar  tmp;
  1142.    UChar  tmp2;
  1143.    Int32  zPend;
  1144.    Int32  wr;
  1145.    Int32  EOB;
  1146.  
  1147.    makeMaps();
  1148.    EOB = nInUse+1;
  1149.  
  1150.    for (i = 0; i <= EOB; i++) mtfFreq[i] = 0;
  1151.  
  1152.    wr = 0;
  1153.    zPend = 0;
  1154.    for (i = 0; i < nInUse; i++) yy[i] = (UChar) i;
  1155.    
  1156.  
  1157.    for (i = 0; i <= last; i++) {
  1158.       UChar ll_i;
  1159.  
  1160.       #if DEBUG
  1161.          assert (wr <= i);
  1162.       #endif
  1163.  
  1164.       ll_i = unseqToSeq[block[zptr[i] - 1]];
  1165.       #if DEBUG
  1166.          assert (ll_i < nInUse);
  1167.       #endif
  1168.  
  1169.       j = 0;
  1170.       tmp = yy[j];
  1171.       while ( ll_i != tmp ) {
  1172.          j++;
  1173.          tmp2 = tmp;
  1174.          tmp = yy[j];
  1175.          yy[j] = tmp2;
  1176.       };
  1177.       yy[0] = tmp;
  1178.  
  1179.       if (j == 0) {
  1180.          zPend++;
  1181.       } else {
  1182.          if (zPend > 0) {
  1183.             zPend--;
  1184.             while (True) {
  1185.                switch (zPend % 2) {
  1186.                   case 0: szptr[wr] = RUNA; wr++; mtfFreq[RUNA]++; break;
  1187.                   case 1: szptr[wr] = RUNB; wr++; mtfFreq[RUNB]++; break;
  1188.                };
  1189.                if (zPend < 2) break;
  1190.                zPend = (zPend - 2) / 2;
  1191.             };
  1192.             zPend = 0;
  1193.          }
  1194.          szptr[wr] = j+1; wr++; mtfFreq[j+1]++;
  1195.       }
  1196.    }
  1197.  
  1198.    if (zPend > 0) {
  1199.       zPend--;
  1200.       while (True) {
  1201.          switch (zPend % 2) {
  1202.             case 0:  szptr[wr] = RUNA; wr++; mtfFreq[RUNA]++; break;
  1203.             case 1:  szptr[wr] = RUNB; wr++; mtfFreq[RUNB]++; break;
  1204.          };
  1205.          if (zPend < 2) break;
  1206.          zPend = (zPend - 2) / 2;
  1207.       };
  1208.    }
  1209.  
  1210.    szptr[wr] = EOB; wr++; mtfFreq[EOB]++;
  1211.  
  1212.    nMTF = wr;
  1213. }
  1214.  
  1215.  
  1216. /*---------------------------------------------*/
  1217. #define LESSER_ICOST  0
  1218. #define GREATER_ICOST 15
  1219.  
  1220. static void sendMTFValues ( void )
  1221. {
  1222.    Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
  1223.    Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
  1224.    Int32 nGroups, nBytes;
  1225.  
  1226.    /*--
  1227.    UChar  len [N_GROUPS][MAX_ALPHA_SIZE];
  1228.    is a global since the decoder also needs it.
  1229.  
  1230.    Int32  code[N_GROUPS][MAX_ALPHA_SIZE];
  1231.    Int32  rfreq[N_GROUPS][MAX_ALPHA_SIZE];
  1232.    are also globals only used in this proc.
  1233.    Made global to keep stack frame size small.
  1234.    --*/
  1235.  
  1236.  
  1237.    UInt16 cost[N_GROUPS];
  1238.    Int32  fave[N_GROUPS];
  1239.  
  1240.    if (verbosity >= 3)
  1241.       fprintf ( stderr, 
  1242.                 "      %d in block, %d after MTF & 1-2 coding, %d+2 syms in use\n", 
  1243.                 last+1, nMTF, nInUse );
  1244.  
  1245.    alphaSize = nInUse+2;
  1246.    for (t = 0; t < N_GROUPS; t++)
  1247.       for (v = 0; v < alphaSize; v++)
  1248.          len[t][v] = GREATER_ICOST;
  1249.  
  1250.    /*--- Decide how many coding tables to use ---*/
  1251.    if (nMTF <= 0) panic ( "sendMTFValues(0)" );
  1252.    if (nMTF < 200) nGroups = 2; else
  1253.    if (nMTF < 800) nGroups = 4; else
  1254.                    nGroups = 6;
  1255.  
  1256.    /*--- Generate an initial set of coding tables ---*/
  1257.    { 
  1258.       Int32 nPart, remF, tFreq, aFreq;
  1259.  
  1260.       nPart = nGroups;
  1261.       remF  = nMTF;
  1262.       gs = 0;
  1263.       while (nPart > 0) {
  1264.          tFreq = remF / nPart;
  1265.          ge = gs-1;
  1266.          aFreq = 0;
  1267.          while (aFreq < tFreq && ge < alphaSize-1) {
  1268.             ge++;
  1269.             aFreq += mtfFreq[ge];
  1270.          }
  1271.  
  1272.          if (ge > gs 
  1273.              && nPart != nGroups && nPart != 1 
  1274.              && ((nGroups-nPart) % 2 == 1)) {
  1275.             aFreq -= mtfFreq[ge];
  1276.             ge--;
  1277.          }
  1278.  
  1279.          if (verbosity >= 3)
  1280.             fprintf ( stderr, 
  1281.                       "      initial group %d, [%d .. %d], has %d syms (%4.1f%%)\n",
  1282.                               nPart, gs, ge, aFreq, 
  1283.                               (100.0 * (float)aFreq) / (float)nMTF );
  1284.  
  1285.          for (v = 0; v < alphaSize; v++)
  1286.             if (v >= gs && v <= ge) 
  1287.                len[nPart-1][v] = LESSER_ICOST; else
  1288.                len[nPart-1][v] = GREATER_ICOST;
  1289.  
  1290.          nPart--;
  1291.          gs = ge+1;
  1292.          remF -= aFreq;
  1293.       }
  1294.    }
  1295.  
  1296.    /*--- 
  1297.       Iterate up to N_ITERS times to improve the tables.
  1298.    ---*/
  1299.    for (iter = 0; iter < N_ITERS; iter++) {
  1300.  
  1301.       for (t = 0; t < nGroups; t++) fave[t] = 0;
  1302.  
  1303.       for (t = 0; t < nGroups; t++)
  1304.          for (v = 0; v < alphaSize; v++)
  1305.             rfreq[t][v] = 0;
  1306.  
  1307.       nSelectors = 0;
  1308.       totc = 0;
  1309.       gs = 0;
  1310.       while (True) {
  1311.  
  1312.          /*--- Set group start & end marks. --*/
  1313.          if (gs >= nMTF) break;
  1314.          ge = gs + G_SIZE - 1; 
  1315.          if (ge >= nMTF) ge = nMTF-1;
  1316.  
  1317.          /*-- 
  1318.             Calculate the cost of this group as coded
  1319.             by each of the coding tables.
  1320.          --*/
  1321.          for (t = 0; t < nGroups; t++) cost[t] = 0;
  1322.  
  1323.          if (nGroups == 6) {
  1324.             register UInt16 cost0, cost1, cost2, cost3, cost4, cost5;
  1325.             cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0;
  1326.             for (i = gs; i <= ge; i++) { 
  1327.                UInt16 icv = szptr[i];
  1328.                cost0 += len[0][icv];
  1329.                cost1 += len[1][icv];
  1330.                cost2 += len[2][icv];
  1331.                cost3 += len[3][icv];
  1332.                cost4 += len[4][icv];
  1333.                cost5 += len[5][icv];
  1334.             }
  1335.             cost[0] = cost0; cost[1] = cost1; cost[2] = cost2;
  1336.             cost[3] = cost3; cost[4] = cost4; cost[5] = cost5;
  1337.          } else {
  1338.             for (i = gs; i <= ge; i++) { 
  1339.                UInt16 icv = szptr[i];
  1340.                for (t = 0; t < nGroups; t++) cost[t] += len[t][icv];
  1341.             }
  1342.          }
  1343.  
  1344.          /*-- 
  1345.             Find the coding table which is best for this group,
  1346.             and record its identity in the selector table.
  1347.          --*/
  1348.          bc = 999999999; bt = -1;
  1349.          for (t = 0; t < nGroups; t++)
  1350.             if (cost[t] < bc) { bc = cost[t]; bt = t; };
  1351.          totc += bc;
  1352.          fave[bt]++;
  1353.          selector[nSelectors] = bt;
  1354.          nSelectors++;
  1355.  
  1356.          /*-- 
  1357.             Increment the symbol frequencies for the selected table.
  1358.           --*/
  1359.          for (i = gs; i <= ge; i++)
  1360.             rfreq[bt][ szptr[i] ]++;
  1361.  
  1362.          gs = ge+1;
  1363.       }
  1364.       if (verbosity >= 3) {
  1365.          fprintf ( stderr, 
  1366.                    "      pass %d: size is %d, grp uses are ", 
  1367.                    iter+1, totc/8 );
  1368.          for (t = 0; t < nGroups; t++)
  1369.             fprintf ( stderr, "%d ", fave[t] );
  1370.          fprintf ( stderr, "\n" );
  1371.       }
  1372.  
  1373.       /*--
  1374.         Recompute the tables based on the accumulated frequencies.
  1375.       --*/
  1376.       for (t = 0; t < nGroups; t++)
  1377.          hbMakeCodeLengths ( &len[t][0], &rfreq[t][0], alphaSize, 20 );
  1378.    }
  1379.  
  1380.  
  1381.    if (!(nGroups < 8)) panic ( "sendMTFValues(1)" );
  1382.    if (!(nSelectors < 32768 &&
  1383.          nSelectors <= (2 + (900000 / G_SIZE))))
  1384.                        panic ( "sendMTFValues(2)" );
  1385.  
  1386.  
  1387.    /*--- Compute MTF values for the selectors. ---*/
  1388.    {
  1389.       UChar pos[N_GROUPS], ll_i, tmp2, tmp;
  1390.       for (i = 0; i < nGroups; i++) pos[i] = i;
  1391.       for (i = 0; i < nSelectors; i++) {
  1392.          ll_i = selector[i];
  1393.          j = 0;
  1394.          tmp = pos[j];
  1395.          while ( ll_i != tmp ) {
  1396.             j++;
  1397.             tmp2 = tmp;
  1398.             tmp = pos[j];
  1399.             pos[j] = tmp2;
  1400.          };
  1401.          pos[0] = tmp;
  1402.          selectorMtf[i] = j;
  1403.       }
  1404.    };
  1405.  
  1406.    /*--- Assign actual codes for the tables. --*/
  1407.    for (t = 0; t < nGroups; t++) {
  1408.       minLen = 32;
  1409.       maxLen = 0;
  1410.       for (i = 0; i < alphaSize; i++) {
  1411.          if (len[t][i] > maxLen) maxLen = len[t][i];
  1412.          if (len[t][i] < minLen) minLen = len[t][i];
  1413.       }
  1414.       if (maxLen > 20) panic ( "sendMTFValues(3)" );
  1415.       if (minLen < 1)  panic ( "sendMTFValues(4)" );
  1416.       hbAssignCodes ( &code[t][0], &len[t][0], 
  1417.                       minLen, maxLen, alphaSize );
  1418.    }
  1419.  
  1420.    /*--- Transmit the mapping table. ---*/
  1421.    { 
  1422.       Bool inUse16[16];
  1423.       for (i = 0; i < 16; i++) {
  1424.           inUse16[i] = False;
  1425.           for (j = 0; j < 16; j++)
  1426.              if (inUse[i * 16 + j]) inUse16[i] = True;
  1427.       }
  1428.      
  1429.       nBytes = bytesOut;
  1430.       for (i = 0; i < 16; i++)
  1431.          if (inUse16[i]) bsW(1,1); else bsW(1,0);
  1432.  
  1433.       for (i = 0; i < 16; i++)
  1434.          if (inUse16[i])
  1435.             for (j = 0; j < 16; j++)
  1436.                if (inUse[i * 16 + j]) bsW(1,1); else bsW(1,0);
  1437.  
  1438.       if (verbosity >= 3) 
  1439.          fprintf ( stderr, "      bytes: mapping %d, ", bytesOut-nBytes );
  1440.    }
  1441.  
  1442.    /*--- Now the selectors. ---*/
  1443.    nBytes = bytesOut;
  1444.    bsW ( 3, nGroups );
  1445.    bsW ( 15, nSelectors );
  1446.    for (i = 0; i < nSelectors; i++) { 
  1447.       for (j = 0; j < selectorMtf[i]; j++) bsW(1,1);
  1448.       bsW(1,0);
  1449.    }
  1450.    if (verbosity >= 3)
  1451.       fprintf ( stderr, "selectors %d, ", bytesOut-nBytes );
  1452.  
  1453.    /*--- Now the coding tables. ---*/
  1454.    nBytes = bytesOut;
  1455.  
  1456.    for (t = 0; t < nGroups; t++) {
  1457.       Int32 curr = len[t][0];
  1458.       bsW ( 5, curr );
  1459.       for (i = 0; i < alphaSize; i++) {
  1460.          while (curr < len[t][i]) { bsW(2,2); curr++; /* 10 */ };
  1461.          while (curr > len[t][i]) { bsW(2,3); curr--; /* 11 */ };
  1462.          bsW ( 1, 0 );
  1463.       }
  1464.    }
  1465.  
  1466.    if (verbosity >= 3)
  1467.       fprintf ( stderr, "code lengths %d, ", bytesOut-nBytes );
  1468.  
  1469.    /*--- And finally, the block data proper ---*/
  1470.    nBytes = bytesOut;
  1471.    selCtr = 0;
  1472.    gs = 0;
  1473.    while (True) {
  1474.       if (gs >= nMTF) break;
  1475.       ge = gs + G_SIZE - 1; 
  1476.       if (ge >= nMTF) ge = nMTF-1;
  1477.       for (i = gs; i <= ge; i++) { 
  1478.          #if DEBUG
  1479.             assert (selector[selCtr] < nGroups);
  1480.          #endif
  1481.          bsW ( len  [selector[selCtr]] [szptr[i]],
  1482.                code [selector[selCtr]] [szptr[i]] );
  1483.       }
  1484.  
  1485.       gs = ge+1;
  1486.       selCtr++;
  1487.    }
  1488.    if (!(selCtr == nSelectors)) panic ( "sendMTFValues(5)" );
  1489.  
  1490.    if (verbosity >= 3)
  1491.       fprintf ( stderr, "codes %d\n", bytesOut-nBytes );
  1492. }
  1493.  
  1494.  
  1495. /*---------------------------------------------*/
  1496. static void moveToFrontCodeAndSend ( void )
  1497. {
  1498.    bsPutIntVS ( 24, origPtr );
  1499.    generateMTFValues();
  1500.    sendMTFValues();
  1501. }
  1502.  
  1503.  
  1504. /*---------------------------------------------*/
  1505. static void recvDecodingTables ( void )
  1506. {
  1507.    Int32 i, j, t, nGroups, nSelectors, alphaSize;
  1508.    Int32 minLen, maxLen;
  1509.    Bool inUse16[16];
  1510.  
  1511.    /*--- Receive the mapping table ---*/
  1512.    for (i = 0; i < 16; i++)
  1513.       if (bsR(1) == 1) 
  1514.          inUse16[i] = True; else 
  1515.          inUse16[i] = False;
  1516.  
  1517.    for (i = 0; i < 256; i++) inUse[i] = False;
  1518.  
  1519.    for (i = 0; i < 16; i++)
  1520.       if (inUse16[i])
  1521.          for (j = 0; j < 16; j++)
  1522.             if (bsR(1) == 1) inUse[i * 16 + j] = True;
  1523.  
  1524.    makeMaps();
  1525.    alphaSize = nInUse+2;
  1526.  
  1527.    /*--- Now the selectors ---*/
  1528.    nGroups = bsR ( 3 );
  1529.    nSelectors = bsR ( 15 );
  1530.    for (i = 0; i < nSelectors; i++) {
  1531.       j = 0;
  1532.       while (bsR(1) == 1) j++;
  1533.       selectorMtf[i] = j;
  1534.    }
  1535.  
  1536.    /*--- Undo the MTF values for the selectors. ---*/
  1537.    {
  1538.       UChar pos[N_GROUPS], tmp, v;
  1539.       for (v = 0; v < nGroups; v++) pos[v] = v;
  1540.    
  1541.       for (i = 0; i < nSelectors; i++) {
  1542.          v = selectorMtf[i];
  1543.          tmp = pos[v];
  1544.          while (v > 0) { pos[v] = pos[v-1]; v--; }
  1545.          pos[0] = tmp;
  1546.          selector[i] = tmp;
  1547.       }
  1548.    }
  1549.  
  1550.    /*--- Now the coding tables ---*/
  1551.    for (t = 0; t < nGroups; t++) {
  1552.       Int32 curr = bsR ( 5 );
  1553.       for (i = 0; i < alphaSize; i++) {
  1554.          while (bsR(1) == 1) {
  1555.             if (bsR(1) == 0) curr++; else curr--;
  1556.          }
  1557.          len[t][i] = curr;
  1558.       }
  1559.    }
  1560.  
  1561.    /*--- Create the Huffman decoding tables ---*/
  1562.    for (t = 0; t < nGroups; t++) {
  1563.       minLen = 32;
  1564.       maxLen = 0;
  1565.       for (i = 0; i < alphaSize; i++) {
  1566.          if (len[t][i] > maxLen) maxLen = len[t][i];
  1567.          if (len[t][i] < minLen) minLen = len[t][i];
  1568.       }
  1569.       hbCreateDecodeTables ( 
  1570.          &limit[t][0], &base[t][0], &perm[t][0], &len[t][0],
  1571.          minLen, maxLen, alphaSize
  1572.       );
  1573.       minLens[t] = minLen;
  1574.    }
  1575. }
  1576.  
  1577.  
  1578. /*---------------------------------------------*/
  1579. #define GET_MTF_VAL(lval)                 \
  1580. {                                         \
  1581.    Int32 zt, zn, zvec, zj;                \
  1582.    if (groupPos == 0) {                   \
  1583.       groupNo++;                          \
  1584.       groupPos = G_SIZE;                  \
  1585.    }                                      \
  1586.    groupPos--;                            \
  1587.    zt = selector[groupNo];                \
  1588.    zn = minLens[zt];                      \
  1589.    zvec = bsR ( zn );                     \
  1590.    while (zvec > limit[zt][zn]) {         \
  1591.       zn++; bsR1(zj);                     \
  1592.       zvec = (zvec << 1) | zj;            \
  1593.    };                                     \
  1594.    lval = perm[zt][zvec - base[zt][zn]];  \
  1595. }
  1596.  
  1597.  
  1598. /*---------------------------------------------*/
  1599. static void getAndMoveToFrontDecode ( void )
  1600. {
  1601.    UChar  yy[256];
  1602.    Int32  i, j, nextSym, limitLast;
  1603.    Int32  EOB, groupNo, groupPos;
  1604.  
  1605.    limitLast = 100000 * blockSize100k;
  1606.    origPtr   = bsGetIntVS ( 24 );
  1607.  
  1608.    recvDecodingTables();
  1609.    EOB      = nInUse+1;
  1610.    groupNo  = -1;
  1611.    groupPos = 0;
  1612.  
  1613.    /*--
  1614.       Setting up the unzftab entries here is not strictly
  1615.       necessary, but it does save having to do it later
  1616.       in a separate pass, and so saves a block's worth of
  1617.       cache misses.
  1618.    --*/
  1619.    for (i = 0; i <= 255; i++) unzftab[i] = 0;
  1620.  
  1621.    for (i = 0; i <= 255; i++) yy[i] = (UChar) i;
  1622.  
  1623.    last = -1;
  1624.  
  1625.    GET_MTF_VAL(nextSym);
  1626.  
  1627.    while (True) {
  1628.  
  1629.       if (nextSym == EOB) break;
  1630.  
  1631.       if (nextSym == RUNA || nextSym == RUNB) {
  1632.          UChar ch;
  1633.          Int32 s = -1;
  1634.          Int32 N = 1;
  1635.          do {
  1636.             if (nextSym == RUNA) s = s + (0+1) * N; else
  1637.             if (nextSym == RUNB) s = s + (1+1) * N;
  1638.             N = N * 2;
  1639.             GET_MTF_VAL(nextSym);
  1640.          }
  1641.             while (nextSym == RUNA || nextSym == RUNB);
  1642.  
  1643.          s++;
  1644.          ch = seqToUnseq[yy[0]];
  1645.          unzftab[ch] += s;
  1646.  
  1647.          if (smallMode)
  1648.             while (s > 0) {
  1649.                last++; 
  1650.                ll16[last] = ch;
  1651.                s--;
  1652.             }
  1653.          else
  1654.             while (s > 0) {
  1655.                last++;
  1656.                ll8[last] = ch;
  1657.                s--;
  1658.             };
  1659.  
  1660.          if (last >= limitLast) blockOverrun();
  1661.          continue;
  1662.  
  1663.       } else {
  1664.  
  1665.          UChar tmp;
  1666.          last++; if (last >= limitLast) blockOverrun();
  1667.  
  1668.          tmp = yy[nextSym-1];
  1669.          unzftab[seqToUnseq[tmp]]++;
  1670.          if (smallMode)
  1671.             ll16[last] = seqToUnseq[tmp]; else
  1672.             ll8[last]  = seqToUnseq[tmp];
  1673.  
  1674.          /*--
  1675.             This loop is hammered during decompression,
  1676.             hence the unrolling.
  1677.  
  1678.             for (j = nextSym-1; j > 0; j--) yy[j] = yy[j-1];
  1679.          --*/
  1680.  
  1681.          j = nextSym-1;
  1682.          for (; j > 3; j -= 4) {
  1683.             yy[j]   = yy[j-1];
  1684.             yy[j-1] = yy[j-2];
  1685.             yy[j-2] = yy[j-3];
  1686.             yy[j-3] = yy[j-4];
  1687.          }
  1688.          for (; j > 0; j--) yy[j] = yy[j-1];
  1689.  
  1690.          yy[0] = tmp;
  1691.          GET_MTF_VAL(nextSym);
  1692.          continue;
  1693.       }
  1694.    }
  1695. }
  1696.  
  1697.  
  1698. /*---------------------------------------------------*/
  1699. /*--- Block-sorting machinery                     ---*/
  1700. /*---------------------------------------------------*/
  1701.  
  1702. /*---------------------------------------------*/
  1703. /*--
  1704.   Compare two strings in block.  We assume (see
  1705.   discussion above) that i1 and i2 have a max
  1706.   offset of 10 on entry, and that the first
  1707.   bytes of both block and quadrant have been
  1708.   copied into the "overshoot area", ie
  1709.   into the subscript range
  1710.   [last+1 .. last+NUM_OVERSHOOT_BYTES].
  1711. --*/
  1712. INLINE static Bool fullGtU ( Int32 i1, Int32 i2 )
  1713. {
  1714.    Int32 k;
  1715.    UChar c1, c2;
  1716.    UInt16 s1, s2;
  1717.  
  1718.    #if DEBUG
  1719.       /*--
  1720.         shellsort shouldn't ask to compare
  1721.         something with itself.
  1722.       --*/
  1723.       assert (i1 != i2);
  1724.    #endif
  1725.  
  1726.    c1 = block[i1];
  1727.    c2 = block[i2];
  1728.    if (c1 != c2) return (c1 > c2);
  1729.    i1++; i2++;
  1730.  
  1731.    c1 = block[i1];
  1732.    c2 = block[i2];
  1733.    if (c1 != c2) return (c1 > c2);
  1734.    i1++; i2++;
  1735.  
  1736.    c1 = block[i1];
  1737.    c2 = block[i2];
  1738.    if (c1 != c2) return (c1 > c2);
  1739.    i1++; i2++;
  1740.  
  1741.    c1 = block[i1];
  1742.    c2 = block[i2];
  1743.    if (c1 != c2) return (c1 > c2);
  1744.    i1++; i2++;
  1745.  
  1746.    c1 = block[i1];
  1747.    c2 = block[i2];
  1748.    if (c1 != c2) return (c1 > c2);
  1749.    i1++; i2++;
  1750.  
  1751.    c1 = block[i1];
  1752.    c2 = block[i2];
  1753.    if (c1 != c2) return (c1 > c2);
  1754.    i1++; i2++;
  1755.  
  1756.    k = last + 1;
  1757.  
  1758.    do {
  1759.  
  1760.       c1 = block[i1];
  1761.       c2 = block[i2];
  1762.       if (c1 != c2) return (c1 > c2);
  1763.       s1 = quadrant[i1];
  1764.       s2 = quadrant[i2];
  1765.       if (s1 != s2) return (s1 > s2);
  1766.       i1++; i2++;
  1767.  
  1768.       c1 = block[i1];
  1769.       c2 = block[i2];
  1770.       if (c1 != c2) return (c1 > c2);
  1771.       s1 = quadrant[i1];
  1772.       s2 = quadrant[i2];
  1773.       if (s1 != s2) return (s1 > s2);
  1774.       i1++; i2++;
  1775.  
  1776.       c1 = block[i1];
  1777.       c2 = block[i2];
  1778.       if (c1 != c2) return (c1 > c2);
  1779.       s1 = quadrant[i1];
  1780.       s2 = quadrant[i2];
  1781.       if (s1 != s2) return (s1 > s2);
  1782.       i1++; i2++;
  1783.  
  1784.       c1 = block[i1];
  1785.       c2 = block[i2];
  1786.       if (c1 != c2) return (c1 > c2);
  1787.       s1 = quadrant[i1];
  1788.       s2 = quadrant[i2];
  1789.       if (s1 != s2) return (s1 > s2);
  1790.       i1++; i2++;
  1791.  
  1792.       if (i1 > last) { i1 -= last; i1--; };
  1793.       if (i2 > last) { i2 -= last; i2--; };
  1794.  
  1795.       k -= 4;
  1796.       workDone++;
  1797.    }
  1798.       while (k >= 0);
  1799.  
  1800.    return False;
  1801. }
  1802.  
  1803. /*---------------------------------------------*/
  1804. /*--
  1805.    Knuth's increments seem to work better
  1806.    than Incerpi-Sedgewick here.  Possibly
  1807.    because the number of elems to sort is
  1808.    usually small, typically <= 20.
  1809. --*/
  1810. Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
  1811.                    9841, 29524, 88573, 265720,
  1812.                    797161, 2391484 };
  1813.  
  1814. static void simpleSort ( Int32 lo, Int32 hi, Int32 d )
  1815. {
  1816.    Int32 i, j, h, bigN, hp;
  1817.    Int32 v;
  1818.  
  1819.    bigN = hi - lo + 1;
  1820.    if (bigN < 2) return;
  1821.  
  1822.    hp = 0;
  1823.    while (incs[hp] < bigN) hp++;
  1824.    hp--;
  1825.  
  1826.    for (; hp >= 0; hp--) {
  1827.       h = incs[hp];
  1828.       if (verbosity >= 5) 
  1829.          fprintf ( stderr, "          shell increment %d\n", h );
  1830.  
  1831.       i = lo + h;
  1832.       while (True) {
  1833.  
  1834.          /*-- copy 1 --*/
  1835.          if (i > hi) break;
  1836.          v = zptr[i];
  1837.          j = i;
  1838.          while ( fullGtU ( zptr[j-h]+d, v+d ) ) {
  1839.             zptr[j] = zptr[j-h];
  1840.             j = j - h;
  1841.             if (j <= (lo + h - 1)) break;
  1842.          }
  1843.          zptr[j] = v;
  1844.          i++;
  1845.  
  1846.          /*-- copy 2 --*/
  1847.          if (i > hi) break;
  1848.          v = zptr[i];
  1849.          j = i;
  1850.          while ( fullGtU ( zptr[j-h]+d, v+d ) ) {
  1851.             zptr[j] = zptr[j-h];
  1852.             j = j - h;
  1853.             if (j <= (lo + h - 1)) break;
  1854.          }
  1855.          zptr[j] = v;
  1856.          i++;
  1857.  
  1858.          /*-- copy 3 --*/
  1859.          if (i > hi) break;
  1860.          v = zptr[i];
  1861.          j = i;
  1862.          while ( fullGtU ( zptr[j-h]+d, v+d ) ) {
  1863.             zptr[j] = zptr[j-h];
  1864.             j = j - h;
  1865.             if (j <= (lo + h - 1)) break;
  1866.          }
  1867.          zptr[j] = v;
  1868.          i++;
  1869.  
  1870.          if (workDone > workLimit && firstAttempt) return;
  1871.       }
  1872.    }
  1873. }
  1874.  
  1875.  
  1876. /*---------------------------------------------*/
  1877. /*--
  1878.    The following is an implementation of
  1879.    an elegant 3-way quicksort for strings,
  1880.    described in a paper "Fast Algorithms for
  1881.    Sorting and Searching Strings", by Robert
  1882.    Sedgewick and Jon L. Bentley.
  1883. --*/
  1884.  
  1885. #define swap(lv1, lv2) \
  1886.    { Int32 tmp = lv1; lv1 = lv2; lv2 = tmp; }
  1887.  
  1888. INLINE static void vswap ( Int32 p1, Int32 p2, Int32 n )
  1889. {
  1890.    while (n > 0) {
  1891.       swap(zptr[p1], zptr[p2]);
  1892.       p1++; p2++; n--;
  1893.    }
  1894. }
  1895.  
  1896. INLINE static UChar med3 ( UChar a, UChar b, UChar c )
  1897. {
  1898.    UChar t;
  1899.    if (a > b) { t = a; a = b; b = t; };
  1900.    if (b > c) { t = b; b = c; c = t; };
  1901.    if (a > b)          b = a;
  1902.    return b;
  1903. }
  1904.  
  1905. #ifndef min
  1906. #define min(a,b) (((a) < (b)) ? (a) : (b))
  1907. #endif
  1908.  
  1909. typedef
  1910.    struct { Int32 ll; Int32 hh; Int32 dd; }
  1911.    StackElem;
  1912.  
  1913. #define push(lz,hz,dz) { stack[sp].ll = lz; \
  1914.                          stack[sp].hh = hz; \
  1915.                          stack[sp].dd = dz; \
  1916.                          sp++; }
  1917.  
  1918. #define pop(lz,hz,dz) { sp--;               \
  1919.                         lz = stack[sp].ll;  \
  1920.                         hz = stack[sp].hh;  \
  1921.                         dz = stack[sp].dd; }
  1922.  
  1923. #define SMALL_THRESH 20
  1924. #define DEPTH_THRESH 10
  1925.  
  1926. /*--
  1927.    If you are ever unlucky/improbable enough
  1928.    to get a stack overflow whilst sorting,
  1929.    increase the following constant and try
  1930.    again.  In practice I have never seen the
  1931.    stack go above 27 elems, so the following
  1932.    limit seems very generous.
  1933. --*/
  1934. #define QSORT_STACK_SIZE 1000
  1935.  
  1936.  
  1937. static void qSort3 ( Int32 loSt, Int32 hiSt, Int32 dSt )
  1938. {
  1939.    Int32 unLo, unHi, ltLo, gtHi, med, n, m;
  1940.    Int32 sp, lo, hi, d;
  1941.    StackElem stack[QSORT_STACK_SIZE];
  1942.  
  1943.    sp = 0;
  1944.    push ( loSt, hiSt, dSt );
  1945.  
  1946.    while (sp > 0) {
  1947.  
  1948.       if (sp >= QSORT_STACK_SIZE) panic ( "stack overflow in qSort3" );
  1949.  
  1950.       pop ( lo, hi, d );
  1951.  
  1952.       if (hi - lo < SMALL_THRESH || d > DEPTH_THRESH) {
  1953.          simpleSort ( lo, hi, d );
  1954.          if (workDone > workLimit && firstAttempt) return;
  1955.          continue;
  1956.       }
  1957.  
  1958.       med = med3 ( block[zptr[ lo         ]+d],
  1959.                    block[zptr[ hi         ]+d],
  1960.                    block[zptr[ (lo+hi)>>1 ]+d] );
  1961.  
  1962.       unLo = ltLo = lo;
  1963.       unHi = gtHi = hi;
  1964.  
  1965.       while (True) {
  1966.          while (True) {
  1967.             if (unLo > unHi) break;
  1968.             n = ((Int32)block[zptr[unLo]+d]) - med;
  1969.             if (n == 0) { swap(zptr[unLo], zptr[ltLo]); ltLo++; unLo++; continue; };
  1970.             if (n >  0) break;
  1971.             unLo++;
  1972.          }
  1973.          while (True) {
  1974.             if (unLo > unHi) break;
  1975.             n = ((Int32)block[zptr[unHi]+d]) - med;
  1976.             if (n == 0) { swap(zptr[unHi], zptr[gtHi]); gtHi--; unHi--; continue; };
  1977.             if (n <  0) break;
  1978.             unHi--;
  1979.          }
  1980.          if (unLo > unHi) break;
  1981.          swap(zptr[unLo], zptr[unHi]); unLo++; unHi--;
  1982.       }
  1983.       #if DEBUG
  1984.          assert (unHi == unLo-1);
  1985.       #endif
  1986.  
  1987.       if (gtHi < ltLo) {
  1988.          push(lo, hi, d+1 );
  1989.          continue;
  1990.       }
  1991.  
  1992.       n = min(ltLo-lo, unLo-ltLo); vswap(lo, unLo-n, n);
  1993.       m = min(hi-gtHi, gtHi-unHi); vswap(unLo, hi-m+1, m);
  1994.  
  1995.       n = lo + unLo - ltLo - 1;
  1996.       m = hi - (gtHi - unHi) + 1;
  1997.  
  1998.       push ( lo, n, d );
  1999.       push ( n+1, m-1, d+1 );
  2000.       push ( m, hi, d );
  2001.    }
  2002. }
  2003.  
  2004.  
  2005. /*---------------------------------------------*/
  2006.  
  2007. #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
  2008.  
  2009. #define SETMASK (1 << 21)
  2010. #define CLEARMASK (~(SETMASK))
  2011.  
  2012. static void sortIt ( void )
  2013. {
  2014.    Int32 i, j, ss, sb;
  2015.    Int32 runningOrder[256];
  2016.    Int32 copy[256];
  2017.    Bool bigDone[256];
  2018.    UChar c1, c2;
  2019.    Int32 numQSorted;
  2020.  
  2021.    /*--
  2022.       In the various block-sized structures, live data runs
  2023.       from 0 to last+NUM_OVERSHOOT_BYTES inclusive.  First,
  2024.       set up the overshoot area for block.
  2025.    --*/
  2026.  
  2027.    if (verbosity >= 4) fprintf ( stderr, "        sort initialise ...\n" );
  2028.    for (i = 0; i < NUM_OVERSHOOT_BYTES; i++)
  2029.        block[last+i+1] = block[i % (last+1)];
  2030.    for (i = 0; i <= last+NUM_OVERSHOOT_BYTES; i++)
  2031.        quadrant[i] = 0;
  2032.  
  2033.    block[-1] = block[last];
  2034.  
  2035.    if (last < 4000) {
  2036.  
  2037.       /*--
  2038.          Use simpleSort(), since the full sorting mechanism
  2039.          has quite a large constant overhead.
  2040.       --*/
  2041.       if (verbosity >= 4) fprintf ( stderr, "        simpleSort ...\n" );
  2042.       for (i = 0; i <= last; i++) zptr[i] = i;
  2043.       firstAttempt = False;
  2044.       workDone = workLimit = 0;
  2045.       simpleSort ( 0, last, 0 );
  2046.       if (verbosity >= 4) fprintf ( stderr, "        simpleSort done.\n" );
  2047.  
  2048.    } else {
  2049.  
  2050.       numQSorted = 0;
  2051.       for (i = 0; i <= 255; i++) bigDone[i] = False;
  2052.  
  2053.       if (verbosity >= 4) fprintf ( stderr, "        bucket sorting ...\n" );
  2054.  
  2055.       for (i = 0; i <= 65536; i++) ftab[i] = 0;
  2056.  
  2057.       c1 = block[-1];
  2058.       for (i = 0; i <= last; i++) {
  2059.          c2 = block[i];
  2060.          ftab[(c1 << 8) + c2]++;
  2061.          c1 = c2;
  2062.       }
  2063.  
  2064.       for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
  2065.  
  2066.       c1 = block[0];
  2067.       for (i = 0; i < last; i++) {
  2068.          c2 = block[i+1];
  2069.          j = (c1 << 8) + c2;
  2070.          c1 = c2;
  2071.          ftab[j]--;
  2072.          zptr[ftab[j]] = i;
  2073.       }
  2074.       j = (block[last] << 8) + block[0];
  2075.       ftab[j]--;
  2076.       zptr[ftab[j]] = last;
  2077.  
  2078.       /*--
  2079.          Now ftab contains the first loc of every small bucket.
  2080.          Calculate the running order, from smallest to largest
  2081.          big bucket.
  2082.       --*/
  2083.  
  2084.       for (i = 0; i <= 255; i++) runningOrder[i] = i;
  2085.  
  2086.       {
  2087.          Int32 vv;
  2088.          Int32 h = 1;
  2089.          do h = 3 * h + 1; while (h <= 256);
  2090.          do {
  2091.             h = h / 3;
  2092.             for (i = h; i <= 255; i++) {
  2093.                vv = runningOrder[i];
  2094.                j = i;
  2095.                while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
  2096.                   runningOrder[j] = runningOrder[j-h];
  2097.                   j = j - h;
  2098.                   if (j <= (h - 1)) goto zero;
  2099.                }
  2100.                zero:
  2101.                runningOrder[j] = vv;
  2102.             }
  2103.          } while (h != 1);
  2104.       }
  2105.  
  2106.       /*--
  2107.          The main sorting loop.
  2108.       --*/
  2109.  
  2110.       for (i = 0; i <= 255; i++) {
  2111.  
  2112.          /*--
  2113.             Process big buckets, starting with the least full.
  2114.          --*/
  2115.          ss = runningOrder[i];
  2116.  
  2117.          /*--
  2118.             Complete the big bucket [ss] by quicksorting
  2119.             any unsorted small buckets [ss, j].  Hopefully
  2120.             previous pointer-scanning phases have already
  2121.             completed many of the small buckets [ss, j], so
  2122.             we don't have to sort them at all.
  2123.          --*/
  2124.          for (j = 0; j <= 255; j++) {
  2125.             sb = (ss << 8) + j;
  2126.             if ( ! (ftab[sb] & SETMASK) ) {
  2127.                Int32 lo = ftab[sb]   & CLEARMASK;
  2128.                Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
  2129.                if (hi > lo) {
  2130.                   if (verbosity >= 4)
  2131.                      fprintf ( stderr,
  2132.                                "        qsort [0x%x, 0x%x]   done %d   this %d\n",
  2133.                                ss, j, numQSorted, hi - lo + 1 );
  2134.                   qSort3 ( lo, hi, 2 );
  2135.                   numQSorted += ( hi - lo + 1 );
  2136.                   if (workDone > workLimit && firstAttempt) return;
  2137.                }
  2138.                ftab[sb] |= SETMASK;
  2139.             }
  2140.          }
  2141.  
  2142.          /*--
  2143.             The ss big bucket is now done.  Record this fact,
  2144.             and update the quadrant descriptors.  Remember to
  2145.             update quadrants in the overshoot area too, if
  2146.             necessary.  The "if (i < 255)" test merely skips
  2147.             this updating for the last bucket processed, since
  2148.             updating for the last bucket is pointless.
  2149.          --*/
  2150.          bigDone[ss] = True;
  2151.  
  2152.          if (i < 255) {
  2153.             Int32 bbStart  = ftab[ss << 8] & CLEARMASK;
  2154.             Int32 bbSize   = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
  2155.             Int32 shifts   = 0;
  2156.  
  2157.             while ((bbSize >> shifts) > 65534) shifts++;
  2158.  
  2159.             for (j = 0; j < bbSize; j++) {
  2160.                Int32 a2update     = zptr[bbStart + j];
  2161.                UInt16 qVal        = (UInt16)(j >> shifts);
  2162.                quadrant[a2update] = qVal;
  2163.                if (a2update < NUM_OVERSHOOT_BYTES)
  2164.                   quadrant[a2update + last + 1] = qVal;
  2165.             }
  2166.  
  2167.             if (! ( ((bbSize-1) >> shifts) <= 65535 )) panic ( "sortIt" );
  2168.          }
  2169.  
  2170.          /*--
  2171.             Now scan this big bucket so as to synthesise the
  2172.             sorted order for small buckets [t, ss] for all t != ss.
  2173.          --*/
  2174.          for (j = 0; j <= 255; j++)
  2175.             copy[j] = ftab[(j << 8) + ss] & CLEARMASK;
  2176.  
  2177.          for (j = ftab[ss << 8] & CLEARMASK;
  2178.               j < (ftab[(ss+1) << 8] & CLEARMASK);
  2179.               j++) {
  2180.             c1 = block[zptr[j]-1];
  2181.             if ( ! bigDone[c1] ) {
  2182.                zptr[copy[c1]] = zptr[j] == 0 ? last : zptr[j] - 1;
  2183.                copy[c1] ++;
  2184.             }
  2185.          }
  2186.  
  2187.          for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;
  2188.       }
  2189.       if (verbosity >= 4)
  2190.          fprintf ( stderr, "        %d pointers, %d sorted, %d scanned\n",
  2191.                            last+1, numQSorted, (last+1) - numQSorted );
  2192.    }
  2193. }
  2194.  
  2195.  
  2196. /*---------------------------------------------------*/
  2197. /*--- Stuff for randomising repetitive blocks     ---*/
  2198. /*---------------------------------------------------*/
  2199.  
  2200. /*---------------------------------------------*/
  2201. static Int32 rNums[512] = { 
  2202.    619, 720, 127, 481, 931, 816, 813, 233, 566, 247, 
  2203.    985, 724, 205, 454, 863, 491, 741, 242, 949, 214, 
  2204.    733, 859, 335, 708, 621, 574, 73, 654, 730, 472, 
  2205.    419, 436, 278, 496, 867, 210, 399, 680, 480, 51, 
  2206.    878, 465, 811, 169, 869, 675, 611, 697, 867, 561, 
  2207.    862, 687, 507, 283, 482, 129, 807, 591, 733, 623, 
  2208.    150, 238, 59, 379, 684, 877, 625, 169, 643, 105, 
  2209.    170, 607, 520, 932, 727, 476, 693, 425, 174, 647, 
  2210.    73, 122, 335, 530, 442, 853, 695, 249, 445, 515, 
  2211.    909, 545, 703, 919, 874, 474, 882, 500, 594, 612, 
  2212.    641, 801, 220, 162, 819, 984, 589, 513, 495, 799, 
  2213.    161, 604, 958, 533, 221, 400, 386, 867, 600, 782, 
  2214.    382, 596, 414, 171, 516, 375, 682, 485, 911, 276, 
  2215.    98, 553, 163, 354, 666, 933, 424, 341, 533, 870, 
  2216.    227, 730, 475, 186, 263, 647, 537, 686, 600, 224, 
  2217.    469, 68, 770, 919, 190, 373, 294, 822, 808, 206, 
  2218.    184, 943, 795, 384, 383, 461, 404, 758, 839, 887, 
  2219.    715, 67, 618, 276, 204, 918, 873, 777, 604, 560, 
  2220.    951, 160, 578, 722, 79, 804, 96, 409, 713, 940, 
  2221.    652, 934, 970, 447, 318, 353, 859, 672, 112, 785, 
  2222.    645, 863, 803, 350, 139, 93, 354, 99, 820, 908, 
  2223.    609, 772, 154, 274, 580, 184, 79, 626, 630, 742, 
  2224.    653, 282, 762, 623, 680, 81, 927, 626, 789, 125, 
  2225.    411, 521, 938, 300, 821, 78, 343, 175, 128, 250, 
  2226.    170, 774, 972, 275, 999, 639, 495, 78, 352, 126, 
  2227.    857, 956, 358, 619, 580, 124, 737, 594, 701, 612, 
  2228.    669, 112, 134, 694, 363, 992, 809, 743, 168, 974, 
  2229.    944, 375, 748, 52, 600, 747, 642, 182, 862, 81, 
  2230.    344, 805, 988, 739, 511, 655, 814, 334, 249, 515, 
  2231.    897, 955, 664, 981, 649, 113, 974, 459, 893, 228, 
  2232.    433, 837, 553, 268, 926, 240, 102, 654, 459, 51, 
  2233.    686, 754, 806, 760, 493, 403, 415, 394, 687, 700, 
  2234.    946, 670, 656, 610, 738, 392, 760, 799, 887, 653, 
  2235.    978, 321, 576, 617, 626, 502, 894, 679, 243, 440, 
  2236.    680, 879, 194, 572, 640, 724, 926, 56, 204, 700, 
  2237.    707, 151, 457, 449, 797, 195, 791, 558, 945, 679, 
  2238.    297, 59, 87, 824, 713, 663, 412, 693, 342, 606, 
  2239.    134, 108, 571, 364, 631, 212, 174, 643, 304, 329, 
  2240.    343, 97, 430, 751, 497, 314, 983, 374, 822, 928, 
  2241.    140, 206, 73, 263, 980, 736, 876, 478, 430, 305, 
  2242.    170, 514, 364, 692, 829, 82, 855, 953, 676, 246, 
  2243.    369, 970, 294, 750, 807, 827, 150, 790, 288, 923, 
  2244.    804, 378, 215, 828, 592, 281, 565, 555, 710, 82, 
  2245.    896, 831, 547, 261, 524, 462, 293, 465, 502, 56, 
  2246.    661, 821, 976, 991, 658, 869, 905, 758, 745, 193, 
  2247.    768, 550, 608, 933, 378, 286, 215, 979, 792, 961, 
  2248.    61, 688, 793, 644, 986, 403, 106, 366, 905, 644, 
  2249.    372, 567, 466, 434, 645, 210, 389, 550, 919, 135, 
  2250.    780, 773, 635, 389, 707, 100, 626, 958, 165, 504, 
  2251.    920, 176, 193, 713, 857, 265, 203, 50, 668, 108, 
  2252.    645, 990, 626, 197, 510, 357, 358, 850, 858, 364, 
  2253.    936, 638
  2254. };
  2255.  
  2256.  
  2257. #define RAND_DECLS                                \
  2258.    Int32 rNToGo = 0;                              \
  2259.    Int32 rTPos  = 0;                              \
  2260.  
  2261. #define STATIC_RAND_DECLS                                \
  2262.    static Int32 rNToGo = 0;                              \
  2263.    static Int32 rTPos  = 0;                              \
  2264.  
  2265. #define RAND_MASK ((rNToGo == 1) ? 1 : 0)
  2266.  
  2267. #define RAND_UPD_MASK                             \
  2268.    if (rNToGo == 0) {                             \
  2269.       rNToGo = rNums[rTPos];                      \
  2270.       rTPos++; if (rTPos == 512) rTPos = 0;       \
  2271.    }                                              \
  2272.    rNToGo--;
  2273.  
  2274.  
  2275.  
  2276. /*---------------------------------------------------*/
  2277. /*--- The Reversible Transformation (tm)          ---*/
  2278. /*---------------------------------------------------*/
  2279.  
  2280. /*---------------------------------------------*/
  2281. static void randomiseBlock ( void )
  2282. {
  2283.    Int32 i;
  2284.    RAND_DECLS;
  2285.    for (i = 0; i < 256; i++) inUse[i] = False;
  2286.  
  2287.    for (i = 0; i <= last; i++) {
  2288.       RAND_UPD_MASK;
  2289.       block[i] ^= RAND_MASK;
  2290.       inUse[block[i]] = True;
  2291.    }
  2292. }
  2293.  
  2294.  
  2295. /*---------------------------------------------*/
  2296. static void doReversibleTransformation ( void )
  2297. {
  2298.    Int32 i;
  2299.  
  2300.    if (verbosity >= 2) fprintf ( stderr, "\n" );
  2301.  
  2302.    workLimit       = workFactor * last;
  2303.    workDone        = 0;
  2304.    blockRandomised = False;
  2305.    firstAttempt    = True;
  2306.  
  2307.    sortIt ();
  2308.  
  2309.    if (verbosity >= 3)
  2310.       fprintf ( stderr, "      %d work, %d block, ratio %5.2f\n",
  2311.                         workDone, last, (float)workDone / (float)(last) );
  2312.  
  2313.    if (workDone > workLimit && firstAttempt) {
  2314.       if (verbosity >= 2)
  2315.          fprintf ( stderr, "    sorting aborted; randomising block\n" );
  2316.       randomiseBlock ();
  2317.       workLimit = workDone = 0;
  2318.       blockRandomised = True;
  2319.       firstAttempt = False;
  2320.       sortIt();
  2321.       if (verbosity >= 3)
  2322.          fprintf ( stderr, "      %d work, %d block, ratio %f\n",
  2323.                            workDone, last, (float)workDone / (float)(last) );
  2324.    }
  2325.  
  2326.    origPtr = -1;
  2327.    for (i = 0; i <= last; i++)
  2328.        if (zptr[i] == 0)
  2329.           { origPtr = i; break; };
  2330.  
  2331.    if (origPtr == -1) panic ( "doReversibleTransformation" );
  2332. }
  2333.  
  2334.  
  2335. /*---------------------------------------------*/
  2336.  
  2337. INLINE static Int32 indexIntoF ( Int32 indx, Int32 *cftab )
  2338. {
  2339.    Int32 nb, na, mid;
  2340.    nb = 0;
  2341.    na = 256;
  2342.    do {
  2343.       mid = (nb + na) >> 1;
  2344.       if (indx >= cftab[mid]) nb = mid; else na = mid;
  2345.    }
  2346.    while (na - nb != 1);
  2347.    return nb;
  2348. }
  2349.  
  2350.  
  2351. #define GET_SMALL(cccc)                     \
  2352.                                             \
  2353.       cccc = indexIntoF ( tPos, cftab );    \
  2354.       tPos = GET_LL(tPos);
  2355.  
  2356.  
  2357. static void undoReversibleTransformation_small ( STRINGQ* dst ,BZ2FILE *BZ2fp)
  2358. {
  2359.    static Int32  cftab[257], cftabAlso[257];
  2360.    static Int32  i, j, tmp, tPos;
  2361.    static UChar  ch;
  2362.  
  2363.    {
  2364.        int state = BZ2fp->undoReversibleTransformation_small_state;
  2365.         BZ2fp->undoReversibleTransformation_small_state = 0;
  2366.         switch(state){
  2367.         case 0:
  2368.             goto label0;break;
  2369.         case 1:
  2370.             goto label1;break;
  2371.         case 2:
  2372.             goto label2;break;
  2373.         }
  2374.    }
  2375. label0:
  2376.    /*--
  2377.       We assume here that the global array unzftab will
  2378.       already be holding the frequency counts for
  2379.       ll8[0 .. last].
  2380.    --*/
  2381.  
  2382.    /*-- Set up cftab to facilitate generation of indexIntoF --*/
  2383.    cftab[0] = 0;
  2384.    for (i = 1; i <= 256; i++) cftab[i] = unzftab[i-1];
  2385.    for (i = 1; i <= 256; i++) cftab[i] += cftab[i-1];
  2386.  
  2387.    /*-- Make a copy of it, used in generation of T --*/
  2388.    for (i = 0; i <= 256; i++) cftabAlso[i] = cftab[i];
  2389.  
  2390.    /*-- compute the T vector --*/
  2391.    for (i = 0; i <= last; i++) {
  2392.       ch = (UChar)ll16[i];
  2393.       SET_LL(i, cftabAlso[ch]);
  2394.       cftabAlso[ch]++;
  2395.    }
  2396.  
  2397.    /*--
  2398.       Compute T^(-1) by pointer reversal on T.  This is rather
  2399.       subtle, in that, if the original block was two or more
  2400.       (in general, N) concatenated copies of the same thing,
  2401.       the T vector will consist of N cycles, each of length
  2402.       blocksize / N, and decoding will involve traversing one
  2403.       of these cycles N times.  Which particular cycle doesn't
  2404.       matter -- they are all equivalent.  The tricky part is to
  2405.       make sure that the pointer reversal creates a correct
  2406.       reversed cycle for us to traverse.  So, the code below
  2407.       simply reverses whatever cycle origPtr happens to fall into,
  2408.       without regard to the cycle length.  That gives one reversed
  2409.       cycle, which for normal blocks, is the entire block-size long.
  2410.       For repeated blocks, it will be interspersed with the other
  2411.       N-1 non-reversed cycles.  Providing that the F-subscripting
  2412.       phase which follows starts at origPtr, all then works ok.
  2413.    --*/
  2414.    i = origPtr;
  2415.    j = GET_LL(i);
  2416.    do {
  2417.       tmp = GET_LL(j);
  2418.       SET_LL(j, i);
  2419.       i = j;
  2420.       j = tmp;
  2421.    }
  2422.       while (i != origPtr);
  2423.  
  2424.    /*--
  2425.       We recreate the original by subscripting F through T^(-1).
  2426.       The run-length-decoder below requires characters incrementally,
  2427.       so tPos is set to a starting value, and is updated by
  2428.       the GET_SMALL macro.
  2429.    --*/
  2430.    tPos   = origPtr;
  2431.  
  2432.    /*-------------------------------------------------*/
  2433.    /*--
  2434.       This is pretty much a verbatim copy of the
  2435.       run-length decoder present in the distribution
  2436.       bzip-0.21; it has to be here to avoid creating
  2437.       block[] as an intermediary structure.  As in 0.21,
  2438.       this code derives from some sent to me by
  2439.       Christian von Roques.
  2440.  
  2441.       It allows dst==NULL, so as to support the test (-t)
  2442.       option without slowing down the fast decompression
  2443.       code.
  2444.    --*/
  2445.    {
  2446.       static IntNative retVal;
  2447.       static Int32     i2, count, chPrev, ch2;
  2448.       static UInt32    localCrc;
  2449.  
  2450.       count    = 0;
  2451.       i2       = 0;
  2452.       ch2      = 256;   /*-- not a char and not EOF --*/
  2453.       localCrc = getGlobalCRC();
  2454.  
  2455.       {
  2456.          /*STATIC_RAND_DECLS;*/
  2457.          static Int32 rNToGo;
  2458.          static Int32 rTPos;
  2459.          
  2460.          rNToGo = 0;rTPos =0;
  2461.  
  2462.          while ( i2 <= last ) {
  2463.             chPrev = ch2;
  2464.             GET_SMALL(ch2);
  2465.             if (blockRandomised) {
  2466.                RAND_UPD_MASK;
  2467.                ch2 ^= (UInt32)RAND_MASK;
  2468.             }
  2469.             i2++;
  2470.  
  2471.             if (dst){
  2472. label1:
  2473.                 retVal = STRINGQ_putc ( ch2, dst );
  2474.             if(retVal ==-2){BZ2fp->blocking=1;BZ2fp->undoReversibleTransformation_small_state = 1;return;}
  2475.             }
  2476.    
  2477.             UPDATE_CRC ( localCrc, (UChar)ch2 );
  2478.    
  2479.             if (ch2 != chPrev) {
  2480.                count = 1;
  2481.             } else {
  2482.                count++;
  2483.                if (count >= 4) {
  2484.                   static Int32 j2;
  2485.                   static UChar z;
  2486.                   GET_SMALL(z);
  2487.                   if (blockRandomised) {
  2488.                      RAND_UPD_MASK;
  2489.                      z ^= RAND_MASK;
  2490.                   }
  2491.                   for (j2 = 0;  j2 < (Int32)z;  j2++) {
  2492.                       if (dst){
  2493.     label2:
  2494.                           retVal = STRINGQ_putc (ch2, dst);
  2495.                         if(retVal ==-2){BZ2fp->blocking=1;BZ2fp->undoReversibleTransformation_small_state = 2;return;}
  2496.                       }
  2497.                      UPDATE_CRC ( localCrc, (UChar)ch2 );
  2498.                   }
  2499.                   i2++;
  2500.                   count = 0;
  2501.                }
  2502.             }
  2503.          }
  2504.       }
  2505.  
  2506.       setGlobalCRC ( localCrc );
  2507.    }
  2508.    /*-- end of the in-line run-length-decoder. --*/
  2509. }
  2510. #undef GET_SMALL
  2511.  
  2512.  
  2513. /*---------------------------------------------*/
  2514.  
  2515. #define GET_FAST(cccc)                       \
  2516.                                              \
  2517.       cccc = ll8[tPos];                      \
  2518.       tPos = tt[tPos];
  2519.  
  2520.  
  2521. static void undoReversibleTransformation_fast ( STRINGQ* dst ,BZ2FILE *BZ2fp)
  2522. {
  2523.    static Int32  cftab[257];
  2524.    static Int32  i, tPos;
  2525.    static UChar  ch;
  2526.  
  2527.    {
  2528.        int state = BZ2fp->undoReversibleTransformation_fast_state;
  2529.         BZ2fp->undoReversibleTransformation_fast_state = 0;
  2530.         switch(state){
  2531.         case 0:
  2532.             goto label0;break;
  2533.         case 1:
  2534.             goto label1;break;
  2535.         case 2:
  2536.             goto label2;break;
  2537.         case 3:
  2538.             goto label3;break;
  2539.         case 4:
  2540.             goto label4;break;
  2541.         }
  2542.    }
  2543. label0:
  2544.    /*--
  2545.       We assume here that the global array unzftab will
  2546.       already be holding the frequency counts for
  2547.       ll8[0 .. last].
  2548.    --*/
  2549.  
  2550.    /*-- Set up cftab to facilitate generation of T^(-1) --*/
  2551.    cftab[0] = 0;
  2552.    for (i = 1; i <= 256; i++) cftab[i] = unzftab[i-1];
  2553.    for (i = 1; i <= 256; i++) cftab[i] += cftab[i-1];
  2554.  
  2555.    /*-- compute the T^(-1) vector --*/
  2556.    for (i = 0; i <= last; i++) {
  2557.       ch = (UChar)ll8[i];
  2558.       tt[cftab[ch]] = i;
  2559.       cftab[ch]++;
  2560.    }
  2561.  
  2562.    /*--
  2563.       We recreate the original by subscripting L through T^(-1).
  2564.       The run-length-decoder below requires characters incrementally,
  2565.       so tPos is set to a starting value, and is updated by
  2566.       the GET_FAST macro.
  2567.    --*/
  2568.    tPos   = tt[origPtr];
  2569.  
  2570.    /*-------------------------------------------------*/
  2571.    /*--
  2572.       This is pretty much a verbatim copy of the
  2573.       run-length decoder present in the distribution
  2574.       bzip-0.21; it has to be here to avoid creating
  2575.       block[] as an intermediary structure.  As in 0.21,
  2576.       this code derives from some sent to me by
  2577.       Christian von Roques.
  2578.    --*/
  2579.    {
  2580.       static IntNative retVal;
  2581.       static Int32     i2, count, chPrev, ch2;
  2582.       static UInt32    localCrc;
  2583.  
  2584.       count    = 0;
  2585.       i2       = 0;
  2586.       ch2      = 256;   /*-- not a char and not EOF --*/
  2587.       localCrc = getGlobalCRC();
  2588.  
  2589.       if (blockRandomised) {
  2590.          /* STATIC_RAND_DECLS;*/
  2591.         static Int32 rNToGo;
  2592.         static Int32 rTPos;
  2593.  
  2594.         rNToGo=0;rTPos=0;
  2595.  
  2596.          while ( i2 <= last ) {
  2597.             chPrev = ch2;
  2598.             GET_FAST(ch2);
  2599.             RAND_UPD_MASK;
  2600.             ch2 ^= (UInt32)RAND_MASK;
  2601.             i2++;
  2602. label1:
  2603.             retVal = STRINGQ_putc ( ch2, dst );
  2604.             if(retVal ==-2){BZ2fp->blocking=1;BZ2fp->undoReversibleTransformation_fast_state = 1;return;}
  2605.             
  2606.             UPDATE_CRC ( localCrc, (UChar)ch2 );
  2607.    
  2608.             if (ch2 != chPrev) {
  2609.                count = 1;
  2610.             } else {
  2611.                count++;
  2612.                if (count >= 4) {
  2613.                   static Int32 j2;
  2614.                   static UChar z;
  2615.                   GET_FAST(z);
  2616.                   RAND_UPD_MASK;
  2617.                   z ^= RAND_MASK;
  2618.                   for (j2 = 0;  j2 < (Int32)z;  j2++) {
  2619. label2:
  2620.                      retVal = STRINGQ_putc (ch2, dst);
  2621.                     if(retVal ==-2){BZ2fp->blocking=1;BZ2fp->undoReversibleTransformation_fast_state = 2;return;}
  2622.                      UPDATE_CRC ( localCrc, (UChar)ch2 );
  2623.                   }
  2624.                   i2++;
  2625.                   count = 0;
  2626.                }
  2627.             }
  2628.          }
  2629.  
  2630.       } else {
  2631.  
  2632.          while ( i2 <= last ) {
  2633.             chPrev = ch2;
  2634.             GET_FAST(ch2);
  2635.             i2++;
  2636. label3:
  2637.             retVal = STRINGQ_putc ( ch2, dst );
  2638.             if(retVal ==-2){BZ2fp->blocking=1;BZ2fp->undoReversibleTransformation_fast_state = 3;return;}
  2639.  
  2640.             UPDATE_CRC ( localCrc, (UChar)ch2 );
  2641.    
  2642.             if (ch2 != chPrev) {
  2643.                count = 1;
  2644.             } else {
  2645.                count++;
  2646.                if (count >= 4) {
  2647.                   static Int32 j2;
  2648.                   static UChar z;
  2649.                   GET_FAST(z);
  2650.                   for (j2 = 0;  j2 < (Int32)z;  j2++) {
  2651. label4:
  2652.                       retVal = STRINGQ_putc (ch2, dst);
  2653.                         if(retVal ==-2){BZ2fp->blocking=1;BZ2fp->undoReversibleTransformation_fast_state = 4;return;}
  2654.                      UPDATE_CRC ( localCrc, (UChar)ch2 );
  2655.                   }
  2656.                   i2++;
  2657.                   count = 0;
  2658.                }
  2659.             }
  2660.          }
  2661.  
  2662.       }   /*-- if (blockRandomised) --*/
  2663.  
  2664.       setGlobalCRC ( localCrc );
  2665.    }
  2666.    /*-- end of the in-line run-length-decoder. --*/
  2667. }
  2668. #undef GET_FAST
  2669.  
  2670.  
  2671. /*---------------------------------------------------*/
  2672. /*--- The block loader and RLEr                   ---*/
  2673. /*---------------------------------------------------*/
  2674.  
  2675. /*---------------------------------------------*/
  2676. /*  Top 16:   run length, 1 to 255.
  2677. *   Lower 16: the char, or MY_EOF for EOF.
  2678. */
  2679.  
  2680. #define MY_EOF 257
  2681.  
  2682. INLINE static Int32 getRLEpair ( STRINGQ* src ,BZ2FILE *BZ2fp)
  2683. {
  2684.    static Int32     runLength;
  2685.    static IntNative ch, chLatest;
  2686.  
  2687.    {
  2688.        int state = BZ2fp->getRLEpair_state;
  2689.         
  2690.        BZ2fp->getRLEpair_state = 0;
  2691.        switch(state){
  2692.         case 0:
  2693.             goto label0;break;
  2694.         case 1:
  2695.             goto label1;break;
  2696.         case 2:
  2697.             goto label2;break;
  2698.        }
  2699.    }
  2700.  
  2701. label0:
  2702. label1:
  2703.    ch = STRINGQ_getc ( src );
  2704.    if(ch==-2){BZ2fp->blocking = 1,BZ2fp->getRLEpair_state=1;return;}
  2705.  
  2706.    /*--- Because I have no idea what kind of a value EOF is. ---*/
  2707.    if (ch == EOF) {
  2708.       /*ERROR_IF_NOT_ZERO ( ferror(src));*/
  2709.       return (1 << 16) | MY_EOF;
  2710.    }
  2711.  
  2712.    runLength = 0;
  2713.    do {
  2714. label2:
  2715.       chLatest = STRINGQ_getc ( src );
  2716.       if(chLatest == -2){BZ2fp->blocking=1;BZ2fp->getRLEpair_state=2;return;}
  2717.  
  2718.       runLength++;
  2719.       bytesIn++;
  2720.    }
  2721.       while (ch == chLatest && runLength < 255);
  2722.  
  2723.    if ( chLatest != EOF ) {
  2724.       if ( STRINGQ_ungetc ( chLatest, src ) == EOF )
  2725.          panic ( "getRLEpair: ungetc failed" );
  2726.    } else {
  2727.       ;/*ERROR_IF_NOT_ZERO ( ferror(src) );*/
  2728.    }
  2729.  
  2730.    /*--- Conditional is just a speedup hack. ---*/
  2731.    if (runLength == 1) {
  2732.       UPDATE_CRC ( globalCrc, (UChar)ch );
  2733.       return (1 << 16) | ch;
  2734.    } else {
  2735.       Int32 i;
  2736.       for (i = 1; i <= runLength; i++)
  2737.          UPDATE_CRC ( globalCrc, (UChar)ch );
  2738.       return (runLength << 16) | ch;
  2739.    }
  2740. }
  2741.  
  2742.  
  2743. /*---------------------------------------------*/
  2744. static void loadAndRLEsource ( STRINGQ* src , BZ2FILE *BZ2fp)
  2745. {
  2746.    static Int32 ch, allowableBlockSize, i;
  2747.  
  2748.    {
  2749.        int state = BZ2fp->loadAndRLEsource_state;
  2750.        BZ2fp->loadAndRLEsource_state = 0;
  2751.        switch(state){
  2752.        case 0:
  2753.            goto label0;break;
  2754.        case 1:
  2755.            goto label1;break;
  2756.        }
  2757.    }
  2758.  
  2759. label0:
  2760.     last = -1;
  2761.    ch   = 0;
  2762.  
  2763.    for (i = 0; i < 256; i++) inUse[i] = False;
  2764.  
  2765.    /*--- 20 is just a paranoia constant ---*/
  2766.    allowableBlockSize = 100000 * blockSize100k - 20;
  2767.  
  2768.    while (last < allowableBlockSize && ch != MY_EOF) {
  2769.       static Int32 rlePair, runLen;
  2770.  
  2771. label1:
  2772.       rlePair = getRLEpair ( src ,BZ2fp);
  2773.       if(BZ2fp->blocking == 1){    BZ2fp->loadAndRLEsource_state = 1;return;}
  2774.  
  2775.       ch      = rlePair & 0xFFFF;
  2776.       runLen  = (UInt32)rlePair >> 16;
  2777.  
  2778.       #if DEBUG
  2779.          assert (runLen >= 1 && runLen <= 255);
  2780.       #endif
  2781.  
  2782.       if (ch != MY_EOF) {
  2783.          inUse[ch] = True;
  2784.          switch (runLen) {
  2785.             case 1:
  2786.                last++; block[last] = (UChar)ch; break;
  2787.             case 2:
  2788.                last++; block[last] = (UChar)ch;
  2789.                last++; block[last] = (UChar)ch; break;
  2790.             case 3:
  2791.                last++; block[last] = (UChar)ch;
  2792.                last++; block[last] = (UChar)ch;
  2793.                last++; block[last] = (UChar)ch; break;
  2794.             default:
  2795.                inUse[runLen-4] = True;
  2796.                last++; block[last] = (UChar)ch;
  2797.                last++; block[last] = (UChar)ch;
  2798.                last++; block[last] = (UChar)ch;
  2799.                last++; block[last] = (UChar)ch;
  2800.                last++; block[last] = (UChar)(runLen-4); break;
  2801.          }
  2802.       }
  2803.    }
  2804. }
  2805.  
  2806.  
  2807. /*---------------------------------------------------*/
  2808. /*--- Processing of complete files and streams    ---*/
  2809. /*---------------------------------------------------*/
  2810.  
  2811. /*-----------------------------------------------------------*/
  2812. static void compressStream(FILE *stream,FILE *zStream)
  2813. {
  2814.     BZ2FILE *BZ2fp;
  2815.     int len;
  2816.     char buff[STRING_QUEUE_BUFFER_SIZE];
  2817.  
  2818.     BZ2fp = BZ2OpenStream(zStream,"w");
  2819.     while((len = fread(buff,1,STRING_QUEUE_BUFFER_SIZE,stream))>0){
  2820.         BZ2Write(BZ2fp,buff,len);
  2821.     }
  2822.     BZ2CloseStream(BZ2fp);
  2823. }
  2824. Bool uncompressStream(FILE *zStream,FILE *stream)
  2825. {
  2826.     BZ2FILE *BZ2fp;
  2827.     int len;
  2828.     char buff[STRING_QUEUE_BUFFER_SIZE];
  2829.     
  2830.     BZ2fp = BZ2OpenStream(zStream,"r");
  2831.     while((len = BZ2Read(BZ2fp,buff,STRING_QUEUE_BUFFER_SIZE))>0){
  2832.         fwrite(buff,1,len,stream);
  2833.     }
  2834.     BZ2CloseStream(BZ2fp);
  2835.  
  2836. }
  2837. /*---------------------------------------------*/
  2838. /*void compressStream2( FILE *stream, FILE *zStream )*/
  2839. void compressStream2(STRINGQ *stream,FILE *zStream ,BZ2FILE *BZ2fp)
  2840. {
  2841.    static IntNative  retVal;
  2842.    static UInt32     blockCRC, combinedCRC;
  2843.    static Int32      blockNo;
  2844.  
  2845.    {
  2846.        int state = BZ2fp->compressStream_state;
  2847.        BZ2fp->compressStream_state = 0;
  2848.        switch(state){
  2849.        case 0:
  2850.            goto label0;break;
  2851.        case 1:
  2852.            goto label1;break;
  2853.        }
  2854.    }
  2855. label0:
  2856.    blockSize100k = BZ2fp->level;
  2857.  
  2858.    allocateCompressStructures();
  2859.    blockNo  = 0;
  2860.    bytesIn  = 0;
  2861.    bytesOut = 0;
  2862.    nBlocksRandomised = 0;
  2863.  
  2864.    /*SET_BINARY_MODE(stream);*/
  2865.    SET_BINARY_MODE(zStream);
  2866.  
  2867.    /*ERROR_IF_NOT_ZERO ( ferror(stream) );*/
  2868.    ERROR_IF_NOT_ZERO ( ferror(zStream) );
  2869.  
  2870.    bsSetStream ( zStream, True );
  2871.  
  2872.    /*--- Write `magic' bytes B and Z,
  2873.          then h indicating file-format == huffmanised,
  2874.          followed by a digit indicating blockSize100k.
  2875.    ---*/
  2876.    bsPutUChar ( 'B' );
  2877.    bsPutUChar ( 'Z' );
  2878.    bsPutUChar ( 'h' );
  2879.    bsPutUChar ( (unsigned char)('0' + blockSize100k) );
  2880.  
  2881.    combinedCRC = 0;
  2882.  
  2883.    if (verbosity >= 2) fprintf ( stderr, "\n" );
  2884.  
  2885.    while (True) {
  2886.  
  2887.       blockNo++;
  2888.       initialiseCRC ();
  2889. label1:
  2890.       loadAndRLEsource (stream,BZ2fp);
  2891.       if(BZ2fp->error==1){ return;}
  2892.       if(BZ2fp->blocking==1){ BZ2fp->compressStream_state =1;return;}
  2893.  
  2894.       /*ERROR_IF_NOT_ZERO ( ferror(stream) );*/
  2895.       if (last == -1) break;
  2896.  
  2897.       blockCRC = getFinalCRC ();
  2898.       combinedCRC = (combinedCRC << 1) | (combinedCRC >> 31);
  2899.       combinedCRC ^= blockCRC;
  2900.  
  2901.       if (verbosity >= 2)
  2902.          fprintf ( stderr, "    block %d: crc = 0x%8x, combined CRC = 0x%8x, size = %d",
  2903.                            blockNo, blockCRC, combinedCRC, last+1 );
  2904.  
  2905.       /*-- sort the block and establish posn of original string --*/
  2906.       doReversibleTransformation ();
  2907.  
  2908.       /*--
  2909.         A 6-byte block header, the value chosen arbitrarily
  2910.         as 0x314159265359 :-).  A 32 bit value does not really
  2911.         give a strong enough guarantee that the value will not
  2912.         appear by chance in the compressed datastream.  Worst-case
  2913.         probability of this event, for a 900k block, is about
  2914.         2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits.
  2915.         For a compressed file of size 100Gb -- about 100000 blocks --
  2916.         only a 48-bit marker will do.  NB: normal compression/
  2917.         decompression do *not* rely on these statistical properties.
  2918.         They are only important when trying to recover blocks from
  2919.         damaged files.
  2920.       --*/
  2921.       bsPutUChar ( 0x31 ); bsPutUChar ( 0x41 );
  2922.       bsPutUChar ( 0x59 ); bsPutUChar ( 0x26 );
  2923.       bsPutUChar ( 0x53 ); bsPutUChar ( 0x59 );
  2924.  
  2925.       /*-- Now the block's CRC, so it is in a known place. --*/
  2926.       bsPutUInt32 ( blockCRC );
  2927.  
  2928.       /*-- Now a single bit indicating randomisation. --*/
  2929.       if (blockRandomised) {
  2930.          bsW(1,1); nBlocksRandomised++;
  2931.       } else
  2932.          bsW(1,0);
  2933.  
  2934.       /*-- Finally, block's contents proper. --*/
  2935.       moveToFrontCodeAndSend ();
  2936.  
  2937.       ERROR_IF_NOT_ZERO ( ferror(zStream) );
  2938.    }
  2939.  
  2940.    if (verbosity >= 2 && nBlocksRandomised > 0)
  2941.       fprintf ( stderr, "    %d block%s needed randomisation\n", 
  2942.                         nBlocksRandomised,
  2943.                         nBlocksRandomised == 1 ? "" : "s" );
  2944.  
  2945.    /*--
  2946.       Now another magic 48-bit number, 0x177245385090, to
  2947.       indicate the end of the last block.  (sqrt(pi), if
  2948.       you want to know.  I did want to use e, but it contains
  2949.       too much repetition -- 27 18 28 18 28 46 -- for me
  2950.       to feel statistically comfortable.  Call me paranoid.)
  2951.    --*/
  2952.  
  2953.    bsPutUChar ( 0x17 ); bsPutUChar ( 0x72 );
  2954.    bsPutUChar ( 0x45 ); bsPutUChar ( 0x38 );
  2955.    bsPutUChar ( 0x50 ); bsPutUChar ( 0x90 );
  2956.  
  2957.    bsPutUInt32 ( combinedCRC );
  2958.    if (verbosity >= 2)
  2959.       fprintf ( stderr, "    final combined CRC = 0x%x\n   ", combinedCRC );
  2960.  
  2961.    /*-- Close the files in an utterly paranoid way. --*/
  2962.    bsFinishedWithStream ();
  2963.  
  2964.    ERROR_IF_NOT_ZERO ( ferror(zStream) );
  2965.    retVal = fflush ( zStream );
  2966.    ERROR_IF_EOF ( retVal );
  2967.    /*retVal = fclose ( zStream );
  2968.    ERROR_IF_EOF ( retVal );*/
  2969.  
  2970.    /*ERROR_IF_NOT_ZERO ( ferror(stream) );*/
  2971.    /*retVal = fclose ( stream );*/
  2972.    /*ERROR_IF_EOF ( retVal );*/
  2973.     /*STRINGQ_puteof(BZ2fp->sq);*/
  2974.  
  2975.    if (bytesIn == 0) bytesIn = 1;
  2976.    if (bytesOut == 0) bytesOut = 1;
  2977.  
  2978.    if (verbosity >= 1)
  2979.       fprintf ( stderr, "%6.3f:1, %6.3f bits/byte, "
  2980.                         "%5.2f%% saved, %d in, %d out.\n",
  2981.                 (float)bytesIn / (float)bytesOut,
  2982.                 (8.0 * (float)bytesOut) / (float)bytesIn,
  2983.                 100.0 * (1.0 - (float)bytesOut / (float)bytesIn),
  2984.                 bytesIn,
  2985.                 bytesOut
  2986.               );
  2987. endlabel:
  2988.    freeCompressStructures();
  2989. }
  2990.  
  2991.  
  2992. /*---------------------------------------------*/
  2993. /*Bool uncompressStream ( FILE *zStream, FILE *stream )*/
  2994.  
  2995. Bool uncompressStream2 ( FILE *zStream, STRINGQ *stream ,BZ2FILE *BZ2fp)
  2996. {
  2997.    static UChar      magic1, magic2, magic3, magic4;
  2998.    static UChar      magic5, magic6;
  2999.    static UInt32     storedBlockCRC, storedCombinedCRC;
  3000.    static UInt32     computedBlockCRC, computedCombinedCRC;
  3001.    static Int32      currBlockNo;
  3002.    static IntNative  retVal;
  3003.  
  3004.    {
  3005.        int state = BZ2fp->uncompressStream_state;
  3006.        BZ2fp->uncompressStream_state = 0;
  3007.        switch(state){
  3008.        case 0:
  3009.            goto label0;break;
  3010.        case 1:
  3011.            goto label1;break;
  3012.        }
  3013.    }
  3014. label0:
  3015.  
  3016.    /*SET_BINARY_MODE(stream);*/
  3017.    SET_BINARY_MODE(zStream);
  3018.  
  3019.    /*ERROR_IF_NOT_ZERO ( ferror(stream) );*/
  3020.    ERROR_IF_NOT_ZERO ( ferror(zStream) );
  3021.  
  3022.    bsSetStream ( zStream, False );
  3023.  
  3024.    /*--
  3025.       A bad magic number is `recoverable from';
  3026.       return with False so the caller skips the file.
  3027.    --*/
  3028.    magic1 = bsGetUChar ();
  3029.    magic2 = bsGetUChar ();
  3030.    magic3 = bsGetUChar ();
  3031.    magic4 = bsGetUChar ();
  3032.    if (magic1 != 'B' ||
  3033.        magic2 != 'Z' ||
  3034.        magic3 != 'h' ||
  3035.        magic4 < '1'  ||
  3036.        magic4 > '9') {
  3037.      bsFinishedWithStream();
  3038.      /*retVal = fclose ( stream );
  3039.      ERROR_IF_EOF ( retVal );*/
  3040.      return False;
  3041.    }
  3042.  
  3043.    setDecompressStructureSizes ( magic4 - '0' );
  3044.    computedCombinedCRC = 0;
  3045.  
  3046.    if (verbosity >= 2) fprintf ( stderr, "\n    " );
  3047.    currBlockNo = 0;
  3048.  
  3049.    while (True) {
  3050.       magic1 = bsGetUChar ();
  3051.       magic2 = bsGetUChar ();
  3052.       magic3 = bsGetUChar ();
  3053.       magic4 = bsGetUChar ();
  3054.       magic5 = bsGetUChar ();
  3055.       magic6 = bsGetUChar ();
  3056.       if (magic1 == 0x17 && magic2 == 0x72 &&
  3057.           magic3 == 0x45 && magic4 == 0x38 &&
  3058.           magic5 == 0x50 && magic6 == 0x90) break;
  3059.  
  3060.       if (magic1 != 0x31 || magic2 != 0x41 ||
  3061.           magic3 != 0x59 || magic4 != 0x26 ||
  3062.           magic5 != 0x53 || magic6 != 0x59) badBlockHeader();
  3063.  
  3064.       storedBlockCRC = bsGetUInt32 ();
  3065.  
  3066.       if (bsR(1) == 1)
  3067.          blockRandomised = True; else
  3068.          blockRandomised = False;
  3069.  
  3070.       currBlockNo++;
  3071.       if (verbosity >= 2)
  3072.          fprintf ( stderr, "[%d: huff+mtf ", currBlockNo );
  3073.       getAndMoveToFrontDecode ();
  3074.       ERROR_IF_NOT_ZERO ( ferror(zStream) );
  3075.  
  3076.       initialiseCRC();
  3077.       if (verbosity >= 2) fprintf ( stderr, "rt+rld" );
  3078. label1:
  3079.       if (smallMode){
  3080.          undoReversibleTransformation_small ( stream ,BZ2fp);
  3081.       }else{
  3082.          undoReversibleTransformation_fast  ( stream ,BZ2fp);
  3083.       }
  3084.       if(BZ2fp->blocking){BZ2fp->uncompressStream_state = 1;return;}
  3085.  
  3086.       /*ERROR_IF_NOT_ZERO ( ferror(stream) );*/
  3087.  
  3088.       computedBlockCRC = getFinalCRC();
  3089.       if (verbosity >= 3)
  3090.          fprintf ( stderr, " {0x%x, 0x%x}", storedBlockCRC, computedBlockCRC );
  3091.       if (verbosity >= 2) fprintf ( stderr, "] " );
  3092.  
  3093.       /*-- A bad CRC is considered a fatal error. --*/
  3094.       if (storedBlockCRC != computedBlockCRC)
  3095.          crcError ( storedBlockCRC, computedBlockCRC );
  3096.  
  3097.       computedCombinedCRC = (computedCombinedCRC << 1) | (computedCombinedCRC >> 31);
  3098.       computedCombinedCRC ^= computedBlockCRC;
  3099.    };
  3100.  
  3101.    if (verbosity >= 2) fprintf ( stderr, "\n    " );
  3102.  
  3103.    storedCombinedCRC  = bsGetUInt32 ();
  3104.    if (verbosity >= 2)
  3105.       fprintf ( stderr,
  3106.                 "combined CRCs: stored = 0x%x, computed = 0x%x\n    ",
  3107.                 storedCombinedCRC, computedCombinedCRC );
  3108.    if (storedCombinedCRC != computedCombinedCRC)
  3109.       crcError ( storedCombinedCRC, computedCombinedCRC );
  3110.  
  3111.  
  3112.    bsFinishedWithStream ();
  3113.    ERROR_IF_NOT_ZERO ( ferror(zStream) );
  3114.    /*retVal = fclose ( zStream );
  3115.    ERROR_IF_EOF ( retVal );*/
  3116.  
  3117.    /*ERROR_IF_NOT_ZERO ( ferror(stream) );
  3118.    retVal = fflush ( stream );
  3119.    ERROR_IF_NOT_ZERO ( retVal );
  3120.    if (stream != stdout) {
  3121.       retVal = fclose ( stream );
  3122.       ERROR_IF_EOF ( retVal );
  3123.    }*/
  3124.     STRINGQ_puteof(BZ2fp->sq);
  3125. endlabel:
  3126.    unsetDecompressStructureSizes ();
  3127.  
  3128.    return True;
  3129. }
  3130.  
  3131.  
  3132. /*---------------------------------------------*/
  3133. static Bool testStream ( FILE *zStream )
  3134. {
  3135.    UChar      magic1, magic2, magic3, magic4;
  3136.    UChar      magic5, magic6;
  3137.    UInt32     storedBlockCRC, storedCombinedCRC;
  3138.    UInt32     computedBlockCRC, computedCombinedCRC;
  3139.    Int32      currBlockNo;
  3140.    IntNative  retVal;
  3141.  
  3142.    SET_BINARY_MODE(zStream);
  3143.    ERROR_IF_NOT_ZERO ( ferror(zStream) );
  3144.  
  3145.    bsSetStream ( zStream, False );
  3146.  
  3147.    magic1 = bsGetUChar ();
  3148.    magic2 = bsGetUChar ();
  3149.    magic3 = bsGetUChar ();
  3150.    magic4 = bsGetUChar ();
  3151.    if (magic1 != 'B' ||
  3152.        magic2 != 'Z' ||
  3153.        magic3 != 'h' ||
  3154.        magic4 < '1'  ||
  3155.        magic4 > '9') {
  3156.      bsFinishedWithStream();
  3157.      fclose ( zStream );
  3158.      fprintf ( stderr, "\n%s: bad magic number (ie, not created by bzip2)\n",
  3159.                        inName );
  3160.      return False;
  3161.    }
  3162.  
  3163.    smallMode = True;
  3164.    setDecompressStructureSizes ( magic4 - '0' );
  3165.    computedCombinedCRC = 0;
  3166.  
  3167.    if (verbosity >= 2) fprintf ( stderr, "\n" );
  3168.    currBlockNo = 0;
  3169.  
  3170.    while (True) {
  3171.       magic1 = bsGetUChar ();
  3172.       magic2 = bsGetUChar ();
  3173.       magic3 = bsGetUChar ();
  3174.       magic4 = bsGetUChar ();
  3175.       magic5 = bsGetUChar ();
  3176.       magic6 = bsGetUChar ();
  3177.       if (magic1 == 0x17 && magic2 == 0x72 &&
  3178.           magic3 == 0x45 && magic4 == 0x38 &&
  3179.           magic5 == 0x50 && magic6 == 0x90) break;
  3180.  
  3181.       currBlockNo++;
  3182.       if (magic1 != 0x31 || magic2 != 0x41 ||
  3183.           magic3 != 0x59 || magic4 != 0x26 ||
  3184.           magic5 != 0x53 || magic6 != 0x59) {
  3185.          bsFinishedWithStream();
  3186.          fclose ( zStream );
  3187.          fprintf ( stderr,
  3188.                    "\n%s, block %d: bad header (not == 0x314159265359)\n",
  3189.                    inName, currBlockNo );
  3190.          return False;
  3191.       }
  3192.       storedBlockCRC = bsGetUInt32 ();
  3193.  
  3194.       if (bsR(1) == 1)
  3195.          blockRandomised = True; else
  3196.          blockRandomised = False;
  3197.  
  3198.       if (verbosity >= 2)
  3199.          fprintf ( stderr, "    block [%d: huff+mtf ", currBlockNo );
  3200.       getAndMoveToFrontDecode ();
  3201.       ERROR_IF_NOT_ZERO ( ferror(zStream) );
  3202.  
  3203.       initialiseCRC();
  3204.       if (verbosity >= 2) fprintf ( stderr, "rt+rld" );
  3205.       /*undoReversibleTransformation_small ( NULL ,NULL);*/
  3206.  
  3207.       undoReversibleTransformation_small ( NULL ,NULL);/* may happen fatal error */
  3208.  
  3209.       computedBlockCRC = getFinalCRC();
  3210.       if (verbosity >= 3)
  3211.          fprintf ( stderr, " {0x%x, 0x%x}", storedBlockCRC, computedBlockCRC );
  3212.       if (verbosity >= 2) fprintf ( stderr, "] " );
  3213.  
  3214.       if (storedBlockCRC != computedBlockCRC) {
  3215.          bsFinishedWithStream();
  3216.          fclose ( zStream );
  3217.          fprintf ( stderr, "\n%s, block %d: computed CRC does not match stored one\n",
  3218.                            inName, currBlockNo );
  3219.          return False;
  3220.       }
  3221.  
  3222.       if (verbosity >= 2) fprintf ( stderr, "ok\n" );
  3223.       computedCombinedCRC = (computedCombinedCRC << 1) | (computedCombinedCRC >> 31);
  3224.       computedCombinedCRC ^= computedBlockCRC;
  3225.    };
  3226.  
  3227.    storedCombinedCRC  = bsGetUInt32 ();
  3228.    if (verbosity >= 2)
  3229.       fprintf ( stderr,
  3230.                 "    combined CRCs: stored = 0x%x, computed = 0x%x\n    ",
  3231.                 storedCombinedCRC, computedCombinedCRC );
  3232.    if (storedCombinedCRC != computedCombinedCRC) {
  3233.       bsFinishedWithStream();
  3234.       fclose ( zStream );
  3235.       fprintf ( stderr, "\n%s: computed CRC does not match stored one\n",
  3236.                         inName );
  3237.       return False;
  3238.    }
  3239.  
  3240.    bsFinishedWithStream ();
  3241.    ERROR_IF_NOT_ZERO ( ferror(zStream) );
  3242.    retVal = fclose ( zStream );
  3243.    ERROR_IF_EOF ( retVal );
  3244.    return True;
  3245. }
  3246.  
  3247.  
  3248.  
  3249. /*---------------------------------------------------*/
  3250. /*--- Error [non-] handling grunge                ---*/
  3251. /*---------------------------------------------------*/
  3252.  
  3253. /*---------------------------------------------*/
  3254. static void cadvise ( void )
  3255. {
  3256.    fprintf (
  3257.       stderr,
  3258.       "\nIt is possible that the compressed file(s) have become corrupted.\n"
  3259.         "You can use the -tvv option to test integrity of such files.\n\n"
  3260.         "You can use the `bzip2recover' program to *attempt* to recover\n"
  3261.         "data from undamaged sections of corrupted files.\n\n"
  3262.     );
  3263. }
  3264.  
  3265.  
  3266. /*---------------------------------------------*/
  3267. static void showFileNames ( void )
  3268. {
  3269.    fprintf (
  3270.       stderr,
  3271.       "\tInput file = %s, output file = %s\n",
  3272.       inName==NULL  ? "(null)" : inName,
  3273.       outName==NULL ? "(null)" : outName
  3274.    );
  3275. }
  3276.  
  3277.  
  3278. /*---------------------------------------------*/
  3279. static void cleanUpAndFail ( Int32 ec )
  3280. {
  3281.    IntNative retVal;
  3282.  
  3283.    if ( srcMode == SM_F2F && opMode != OM_TEST ) {
  3284.       fprintf ( stderr, "%s: Deleting output file %s, if it exists.\n",
  3285.                 progName,
  3286.                 outName==NULL ? "(null)" : outName );
  3287.       if (outputHandleJustInCase != NULL)
  3288.          fclose ( outputHandleJustInCase );
  3289.       retVal = remove ( outName );
  3290.       if (retVal != 0)
  3291.          fprintf ( stderr,
  3292.                    "%s: WARNING: deletion of output file (apparently) failed.\n",
  3293.                    progName );
  3294.    }
  3295.    if (numFileNames > 0 && numFilesProcessed < numFileNames) {
  3296.       fprintf ( stderr, 
  3297.                 "%s: WARNING: some files have not been processed:\n"
  3298.                 "\t%d specified on command line, %d not processed yet.\n\n",
  3299.                 progName, numFileNames, 
  3300.                           numFileNames - numFilesProcessed );
  3301.    }
  3302.    exit ( ec );
  3303. }
  3304.  
  3305.  
  3306. /*---------------------------------------------*/
  3307. static void panic ( Char* s )
  3308. {
  3309.    fprintf ( stderr,
  3310.              "\n%s: PANIC -- internal consistency error:\n"
  3311.              "\t%s\n"
  3312.              "\tThis is a BUG.  Please report it to me at:\n"
  3313.              "\tjseward@acm.org\n",
  3314.              progName, s );
  3315.    showFileNames();
  3316.    cleanUpAndFail( 3 );
  3317. }
  3318.  
  3319.  
  3320. /*---------------------------------------------*/
  3321. static void badBGLengths ( void )
  3322. {
  3323.    fprintf ( stderr,
  3324.              "\n%s: error when reading background model code lengths,\n"
  3325.              "\twhich probably means the compressed file is corrupted.\n",
  3326.              progName );
  3327.    showFileNames();
  3328.    cadvise();
  3329.    cleanUpAndFail( 2 );
  3330. }
  3331.  
  3332.  
  3333. /*---------------------------------------------*/
  3334. static void crcError ( UInt32 crcStored, UInt32 crcComputed )
  3335. {
  3336.    fprintf ( stderr,
  3337.              "\n%s: Data integrity error when decompressing.\n"
  3338.              "\tStored CRC = 0x%x, computed CRC = 0x%x\n",
  3339.              progName, crcStored, crcComputed );
  3340.    showFileNames();
  3341.    cadvise();
  3342.    cleanUpAndFail( 2 );
  3343. }
  3344.  
  3345.  
  3346. /*---------------------------------------------*/
  3347. static void compressedStreamEOF ( void )
  3348. {
  3349.    fprintf ( stderr,
  3350.              "\n%s: Compressed file ends unexpectedly;\n\t"
  3351.              "perhaps it is corrupted?  *Possible* reason follows.\n",
  3352.              progName );
  3353.    perror ( progName );
  3354.    showFileNames();
  3355.    cadvise();
  3356.    cleanUpAndFail( 2 );
  3357. }
  3358.  
  3359.  
  3360. /*---------------------------------------------*/
  3361. static void ioError ( )
  3362. {
  3363.    fprintf ( stderr,
  3364.              "\n%s: I/O or other error, bailing out.  Possible reason follows.\n",
  3365.              progName );
  3366.    perror ( progName );
  3367.    showFileNames();
  3368.    cleanUpAndFail( 1 );
  3369. }
  3370.  
  3371.  
  3372. /*---------------------------------------------*/
  3373. static void blockOverrun ()
  3374. {
  3375.    fprintf ( stderr,
  3376.              "\n%s: block overrun during decompression,\n"
  3377.              "\twhich probably means the compressed file\n"
  3378.              "\tis corrupted.\n",
  3379.              progName );
  3380.    showFileNames();
  3381.    cadvise();
  3382.    cleanUpAndFail( 2 );
  3383. }
  3384.  
  3385.  
  3386. /*---------------------------------------------*/
  3387. static void badBlockHeader ()
  3388. {
  3389.    fprintf ( stderr,
  3390.              "\n%s: bad block header in the compressed file,\n"
  3391.              "\twhich probably means it is corrupted.\n",
  3392.              progName );
  3393.    showFileNames();
  3394.    cadvise();
  3395.    cleanUpAndFail( 2 );
  3396. }
  3397.  
  3398.  
  3399. /*---------------------------------------------*/
  3400. static void bitStreamEOF ()
  3401. {
  3402.    fprintf ( stderr,
  3403.              "\n%s: read past the end of compressed data,\n"
  3404.              "\twhich probably means it is corrupted.\n",
  3405.              progName );
  3406.    showFileNames();
  3407.    cadvise();
  3408.    cleanUpAndFail( 2 );
  3409. }
  3410.  
  3411.  
  3412. /*---------------------------------------------*/
  3413. static void mySignalCatcher ( IntNative n )
  3414. {
  3415.    fprintf ( stderr,
  3416.              "\n%s: Control-C (or similar) caught, quitting.\n",
  3417.              progName );
  3418.    cleanUpAndFail(1);
  3419. }
  3420.  
  3421.  
  3422. /*---------------------------------------------*/
  3423. static void mySIGSEGVorSIGBUScatcher ( IntNative n )
  3424. {
  3425.    if (opMode == OM_Z)
  3426.       fprintf ( stderr,
  3427.                 "\n%s: Caught a SIGSEGV or SIGBUS whilst compressing,\n"
  3428.                 "\twhich probably indicates a bug in bzip2.  Please\n"
  3429.                 "\treport it to me at: jseward@acm.org\n",
  3430.                 progName );
  3431.       else
  3432.       fprintf ( stderr,
  3433.                 "\n%s: Caught a SIGSEGV or SIGBUS whilst decompressing,\n"
  3434.                 "\twhich probably indicates that the compressed data\n"
  3435.                 "\tis corrupted.\n",
  3436.                 progName );
  3437.  
  3438.    showFileNames();
  3439.    if (opMode == OM_Z)
  3440.       cleanUpAndFail( 3 ); else
  3441.       { cadvise(); cleanUpAndFail( 2 ); }
  3442. }
  3443.  
  3444.  
  3445. /*---------------------------------------------*/
  3446. static void uncompressOutOfMemory ( Int32 draw, Int32 blockSize )
  3447. {
  3448.    fprintf ( stderr,
  3449.              "\n%s: Can't allocate enough memory for decompression.\n"
  3450.              "\tRequested %d bytes for a block size of %d.\n"
  3451.              "\tTry selecting space-economic decompress (with flag -s)\n"
  3452.              "\tand failing that, find a machine with more memory.\n",
  3453.              progName, draw, blockSize );
  3454.    showFileNames();
  3455.    cleanUpAndFail(1);
  3456. }
  3457.  
  3458.  
  3459. /*---------------------------------------------*/
  3460. static void compressOutOfMemory ( Int32 draw, Int32 blockSize )
  3461. {
  3462.    fprintf ( stderr,
  3463.              "\n%s: Can't allocate enough memory for compression.\n"
  3464.              "\tRequested %d bytes for a block size of %d.\n"
  3465.              "\tTry selecting a small block size (with flag -s).\n",
  3466.              progName, draw, blockSize );
  3467.    showFileNames();
  3468.    cleanUpAndFail(1);
  3469. }
  3470.  
  3471.  
  3472. /*---------------------------------------------------*/
  3473. /*--- The main driver machinery                   ---*/
  3474. /*---------------------------------------------------*/
  3475.  
  3476. /*---------------------------------------------*/
  3477. static void pad ( Char *s )
  3478. {
  3479.    Int32 i;
  3480.    if ( (Int32)strlen(s) >= longestFileName ) return;
  3481.    for (i = 1; i <= longestFileName - (Int32)strlen(s); i++)
  3482.       fprintf ( stderr, " " );
  3483. }
  3484.  
  3485.  
  3486. /*---------------------------------------------*/
  3487. Bool fileExists ( Char* name )
  3488. {
  3489.    FILE *tmp   = fopen ( name, "rb" );
  3490.    Bool exists = (tmp != NULL);
  3491.    if (tmp != NULL) fclose ( tmp );
  3492.    return exists;
  3493. }
  3494.  
  3495.  
  3496. /*---------------------------------------------*/
  3497. /*--
  3498.   if in doubt, return True
  3499. --*/
  3500. Bool notABogStandardFile ( Char* name )
  3501. {
  3502.    IntNative      i;
  3503.    struct MY_STAT statBuf;
  3504.  
  3505.    i = MY_LSTAT ( name, &statBuf );
  3506.    if (i != 0) return True;
  3507.    if (MY_S_IFREG(statBuf.st_mode)) return False;
  3508.    return True;
  3509. }
  3510.  
  3511.  
  3512. /*---------------------------------------------*/
  3513. static void copyDateAndPermissions ( Char *srcName, Char *dstName )
  3514. {
  3515.    #if BZ_UNIX
  3516.    IntNative      retVal;
  3517.    struct MY_STAT statBuf;
  3518.    struct utimbuf uTimBuf;
  3519.  
  3520.    retVal = MY_LSTAT ( srcName, &statBuf );
  3521.    ERROR_IF_NOT_ZERO ( retVal );
  3522.    uTimBuf.actime = statBuf.st_atime;
  3523.    uTimBuf.modtime = statBuf.st_mtime;
  3524.  
  3525.    retVal = chmod ( dstName, statBuf.st_mode );
  3526.    ERROR_IF_NOT_ZERO ( retVal );
  3527.    retVal = utime ( dstName, &uTimBuf );
  3528.    ERROR_IF_NOT_ZERO ( retVal );
  3529.    #endif
  3530. }
  3531.  
  3532.  
  3533. /*---------------------------------------------*/
  3534. static Bool endsInBz2 ( Char* name )
  3535. {
  3536.    Int32 n = strlen ( name );
  3537.    if (n <= 4) return False;
  3538.    return
  3539.       (name[n-4] == '.' &&
  3540.        name[n-3] == 'b' &&
  3541.        name[n-2] == 'z' &&
  3542.        name[n-1] == '2');
  3543. }
  3544.  
  3545.  
  3546. /*---------------------------------------------*/
  3547. static Bool containsDubiousChars ( Char* name )
  3548. {
  3549.    Bool cdc = False;
  3550.    for (; *name != '\0'; name++)
  3551.       if (*name == '?' || *name == '*') cdc = True;
  3552.    return cdc;
  3553. }
  3554.  
  3555.  
  3556. /*---------------------------------------------*/
  3557. static void compress ( Char *name )
  3558. {
  3559.    FILE *inStr;
  3560.    FILE *outStr;
  3561.  
  3562.    if (name == NULL && srcMode != SM_I2O)
  3563.       panic ( "compress: bad modes\n" );
  3564.  
  3565.    switch (srcMode) {
  3566.       case SM_I2O: strcpy ( inName, "(stdin)" );
  3567.                    strcpy ( outName, "(stdout)" ); break;
  3568.       case SM_F2F: strcpy ( inName, name );
  3569.                    strcpy ( outName, name );
  3570.                    strcat ( outName, ".bz2" ); break;
  3571.       case SM_F2O: strcpy ( inName, name );
  3572.                    strcpy ( outName, "(stdout)" ); break;
  3573.    }
  3574.  
  3575.    if ( srcMode != SM_I2O && containsDubiousChars ( inName ) ) {
  3576.       fprintf ( stderr, "%s: There are no files matching `%s'.\n",
  3577.       progName, inName );
  3578.       return;
  3579.    }
  3580.    if ( srcMode != SM_I2O && !fileExists ( inName ) ) {
  3581.       fprintf ( stderr, "%s: Input file %s doesn't exist, skipping.\n",
  3582.                 progName, inName );
  3583.       return;
  3584.    }
  3585.    if ( srcMode != SM_I2O && endsInBz2 ( inName )) {
  3586.       fprintf ( stderr, "%s: Input file name %s ends in `.bz2', skipping.\n",
  3587.                 progName, inName );
  3588.       return;
  3589.    }
  3590.    if ( srcMode != SM_I2O && notABogStandardFile ( inName )) {
  3591.       fprintf ( stderr, "%s: Input file %s is not a normal file, skipping.\n",
  3592.                 progName, inName );
  3593.       return;
  3594.    }
  3595.    if ( srcMode == SM_F2F && fileExists ( outName ) ) {
  3596.       fprintf ( stderr, "%s: Output file %s already exists, skipping.\n",
  3597.                 progName, outName );
  3598.       return;
  3599.    }
  3600.  
  3601.    switch ( srcMode ) {
  3602.  
  3603.       case SM_I2O:
  3604.          inStr = stdin;
  3605.          outStr = stdout;
  3606.          /*if ( isatty ( fileno ( stdout ) ) ) {
  3607.             fprintf ( stderr,
  3608.                       "%s: I won't write compressed data to a terminal.\n",
  3609.                       progName );
  3610.             fprintf ( stderr, "%s: For help, type: `%s --help'.\n",
  3611.                               progName, progName );
  3612.             return;
  3613.          };*/
  3614.          break;
  3615.  
  3616.       case SM_F2O:
  3617.          inStr = fopen ( inName, "rb" );
  3618.          outStr = stdout;
  3619.          if ( isatty ( fileno ( stdout ) ) ) {
  3620.             fprintf ( stderr,
  3621.                       "%s: I won't write compressed data to a terminal.\n",
  3622.                       progName );
  3623.             fprintf ( stderr, "%s: For help, type: `%s --help'.\n",
  3624.                               progName, progName );
  3625.             return;
  3626.          };
  3627.          if ( inStr == NULL ) {
  3628.             fprintf ( stderr, "%s: Can't open input file %s, skipping.\n",
  3629.                       progName, inName );
  3630.             return;
  3631.          };
  3632.          break;
  3633.  
  3634.       case SM_F2F:
  3635.          inStr = fopen ( inName, "rb" );
  3636.          outStr = fopen ( outName, "wb" );
  3637.          if ( outStr == NULL) {
  3638.             fprintf ( stderr, "%s: Can't create output file %s, skipping.\n",
  3639.                       progName, outName );
  3640.             return;
  3641.          }
  3642.          if ( inStr == NULL ) {
  3643.             fprintf ( stderr, "%s: Can't open input file %s, skipping.\n",
  3644.                       progName, inName );
  3645.             return;
  3646.          };
  3647.          break;
  3648.  
  3649.       default:
  3650.          panic ( "compress: bad srcMode" );
  3651.          break;
  3652.    }
  3653.  
  3654.    if (verbosity >= 1) {
  3655.       fprintf ( stderr,  "  %s: ", inName );
  3656.       pad ( inName );
  3657.       fflush ( stderr );
  3658.    }
  3659.  
  3660.    /*--- Now the input and output handles are sane.  Do the Biz. ---*/
  3661.    outputHandleJustInCase = outStr;
  3662.    compressStream ( inStr, outStr );
  3663.    outputHandleJustInCase = NULL;
  3664.  
  3665.    /*--- If there was an I/O error, we won't get here. ---*/
  3666.    if ( srcMode == SM_F2F ) {
  3667.       copyDateAndPermissions ( inName, outName );
  3668.       if ( !keepInputFiles ) {
  3669.          IntNative retVal = remove ( inName );
  3670.          ERROR_IF_NOT_ZERO ( retVal );
  3671.       }
  3672.    }
  3673. }
  3674.  
  3675.  
  3676. /*---------------------------------------------*/
  3677. static void uncompress ( Char *name )
  3678. {
  3679.    FILE *inStr;
  3680.    FILE *outStr;
  3681.    Bool magicNumberOK;
  3682.  
  3683.    if (name == NULL && srcMode != SM_I2O)
  3684.       panic ( "uncompress: bad modes\n" );
  3685.  
  3686.    switch (srcMode) {
  3687.       case SM_I2O: strcpy ( inName, "(stdin)" );
  3688.                    strcpy ( outName, "(stdout)" ); break;
  3689.       case SM_F2F: strcpy ( inName, name );
  3690.                    strcpy ( outName, name );
  3691.                    if (endsInBz2 ( outName ))
  3692.                       outName [ strlen ( outName ) - 4 ] = '\0';
  3693.                    break;
  3694.       case SM_F2O: strcpy ( inName, name );
  3695.                    strcpy ( outName, "(stdout)" ); break;
  3696.    }
  3697.  
  3698.    if ( srcMode != SM_I2O && containsDubiousChars ( inName ) ) {
  3699.       fprintf ( stderr, "%s: There are no files matching `%s'.\n",
  3700.                 progName, inName );
  3701.       return;
  3702.    }
  3703.    if ( srcMode != SM_I2O && !fileExists ( inName ) ) {
  3704.       fprintf ( stderr, "%s: Input file %s doesn't exist, skipping.\n",
  3705.                 progName, inName );
  3706.       return;
  3707.    }
  3708.    if ( srcMode != SM_I2O && !endsInBz2 ( inName )) {
  3709.       fprintf ( stderr,
  3710.                 "%s: Input file name %s doesn't end in `.bz2', skipping.\n",
  3711.                 progName, inName );
  3712.       return;
  3713.    }
  3714.    if ( srcMode != SM_I2O && notABogStandardFile ( inName )) {
  3715.       fprintf ( stderr, "%s: Input file %s is not a normal file, skipping.\n",
  3716.                 progName, inName );
  3717.       return;
  3718.    }
  3719.    if ( srcMode == SM_F2F && fileExists ( outName ) ) {
  3720.       fprintf ( stderr, "%s: Output file %s already exists, skipping.\n",
  3721.                 progName, outName );
  3722.       return;
  3723.    }
  3724.  
  3725.    switch ( srcMode ) {
  3726.  
  3727.       case SM_I2O:
  3728.          inStr = stdin;
  3729.          outStr = stdout;
  3730.          if ( isatty ( fileno ( stdin ) ) ) {
  3731.             fprintf ( stderr,
  3732.                       "%s: I won't read compressed data from a terminal.\n",
  3733.                       progName );
  3734.             fprintf ( stderr, "%s: For help, type: `%s --help'.\n",
  3735.                               progName, progName );
  3736.             return;
  3737.          };
  3738.          break;
  3739.  
  3740.       case SM_F2O:
  3741.          inStr = fopen ( inName, "rb" );
  3742.          outStr = stdout;
  3743.          if ( inStr == NULL ) {
  3744.             fprintf ( stderr, "%s: Can't open input file %s, skipping.\n",
  3745.                       progName, inName );
  3746.             return;
  3747.          };
  3748.          break;
  3749.  
  3750.       case SM_F2F:
  3751.          inStr = fopen ( inName, "rb" );
  3752.          outStr = fopen ( outName, "wb" );
  3753.          if ( outStr == NULL) {
  3754.             fprintf ( stderr, "%s: Can't create output file %s, skipping.\n",
  3755.                       progName, outName );
  3756.             return;
  3757.          }
  3758.          if ( inStr == NULL ) {
  3759.             fprintf ( stderr, "%s: Can't open input file %s, skipping.\n",
  3760.                       progName, inName );
  3761.             return;
  3762.          };
  3763.          break;
  3764.  
  3765.       default:
  3766.          panic ( "uncompress: bad srcMode" );
  3767.          break;
  3768.    }
  3769.  
  3770.    if (verbosity >= 1) {
  3771.       fprintf ( stderr, "  %s: ", inName );
  3772.       pad ( inName );
  3773.       fflush ( stderr );
  3774.    }
  3775.  
  3776.    /*--- Now the input and output handles are sane.  Do the Biz. ---*/
  3777.    outputHandleJustInCase = outStr;
  3778.    magicNumberOK = uncompressStream ( inStr, outStr );
  3779.    outputHandleJustInCase = NULL;
  3780.  
  3781.    /*--- If there was an I/O error, we won't get here. ---*/
  3782.    if ( magicNumberOK ) {
  3783.       if ( srcMode == SM_F2F ) {
  3784.          copyDateAndPermissions ( inName, outName );
  3785.          if ( !keepInputFiles ) {
  3786.             IntNative retVal = remove ( inName );
  3787.             ERROR_IF_NOT_ZERO ( retVal );
  3788.          }
  3789.       }
  3790.    } else {
  3791.       if ( srcMode == SM_F2F ) {
  3792.          IntNative retVal = remove ( outName );
  3793.          ERROR_IF_NOT_ZERO ( retVal );
  3794.       }
  3795.    }
  3796.  
  3797.    if ( magicNumberOK ) {
  3798.       if (verbosity >= 1)
  3799.          fprintf ( stderr, "done\n" );
  3800.    } else {
  3801.       if (verbosity >= 1)
  3802.          fprintf ( stderr, "not a bzip2 file, skipping.\n" ); else
  3803.          fprintf ( stderr,
  3804.                    "%s: %s is not a bzip2 file, skipping.\n",
  3805.                    progName, inName );
  3806.    }
  3807.  
  3808. }
  3809.  
  3810.  
  3811. /*---------------------------------------------*/
  3812. static void testf ( Char *name )
  3813. {
  3814.    FILE *inStr;
  3815.    Bool allOK;
  3816.  
  3817.    if (name == NULL && srcMode != SM_I2O)
  3818.       panic ( "testf: bad modes\n" );
  3819.  
  3820.    strcpy ( outName, "(none)" );
  3821.    switch (srcMode) {
  3822.       case SM_I2O: strcpy ( inName, "(stdin)" ); break;
  3823.       case SM_F2F: strcpy ( inName, name ); break;
  3824.       case SM_F2O: strcpy ( inName, name ); break;
  3825.    }
  3826.  
  3827.    if ( srcMode != SM_I2O && containsDubiousChars ( inName ) ) {
  3828.       fprintf ( stderr, "%s: There are no files matching `%s'.\n",
  3829.                 progName, inName );
  3830.       return;
  3831.    }
  3832.    if ( srcMode != SM_I2O && !fileExists ( inName ) ) {
  3833.       fprintf ( stderr, "%s: Input file %s doesn't exist, skipping.\n",
  3834.                 progName, inName );
  3835.       return;
  3836.    }
  3837.    if ( srcMode != SM_I2O && !endsInBz2 ( inName )) {
  3838.       fprintf ( stderr,
  3839.                 "%s: Input file name %s doesn't end in `.bz2', skipping.\n",
  3840.                 progName, inName );
  3841.       return;
  3842.    }
  3843.    if ( srcMode != SM_I2O && notABogStandardFile ( inName )) {
  3844.       fprintf ( stderr, "%s: Input file %s is not a normal file, skipping.\n",
  3845.                 progName, inName );
  3846.       return;
  3847.    }
  3848.  
  3849.    switch ( srcMode ) {
  3850.  
  3851.       case SM_I2O:
  3852.          if ( isatty ( fileno ( stdin ) ) ) {
  3853.             fprintf ( stderr,
  3854.                       "%s: I won't read compressed data from a terminal.\n",
  3855.                       progName );
  3856.             fprintf ( stderr, "%s: For help, type: `%s --help'.\n",
  3857.                               progName, progName );
  3858.             return;
  3859.          };
  3860.          inStr = stdin;
  3861.          break;
  3862.  
  3863.       case SM_F2O: case SM_F2F:
  3864.          inStr = fopen ( inName, "rb" );
  3865.          if ( inStr == NULL ) {
  3866.             fprintf ( stderr, "%s: Can't open input file %s, skipping.\n",
  3867.                       progName, inName );
  3868.             return;
  3869.          };
  3870.          break;
  3871.  
  3872.       default:
  3873.          panic ( "testf: bad srcMode" );
  3874.          break;
  3875.    }
  3876.  
  3877.    if (verbosity >= 1) {
  3878.       fprintf ( stderr, "  %s: ", inName );
  3879.       pad ( inName );
  3880.       fflush ( stderr );
  3881.    }
  3882.  
  3883.    /*--- Now the input handle is sane.  Do the Biz. ---*/
  3884.    allOK = testStream ( inStr );
  3885.  
  3886.    if (allOK && verbosity >= 1) fprintf ( stderr, "ok\n" );
  3887.    if (!allOK) testFailsExist = True;
  3888. }
  3889.  
  3890.  
  3891. /*---------------------------------------------*/
  3892. static void license ( void )
  3893. {
  3894.    fprintf ( stderr,
  3895.  
  3896.     "bzip2, a block-sorting file compressor.  "
  3897.     "Version 0.1pl2, 29-Aug-97.\n"
  3898.     "   \n"
  3899.     "   Copyright (C) 1996, 1997 by Julian Seward.\n"
  3900.     "   \n"
  3901.     "   This program is free software; you can redistribute it and/or modify\n"
  3902.     "   it under the terms of the GNU General Public License as published by\n"
  3903.     "   the Free Software Foundation; either version 2 of the License, or\n"
  3904.     "   (at your option) any later version.\n"
  3905.     "   \n"
  3906.     "   This program is distributed in the hope that it will be useful,\n"
  3907.     "   but WITHOUT ANY WARRANTY; without even the implied warranty of\n"
  3908.     "   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n"
  3909.     "   GNU General Public License for more details.\n"
  3910.     "   \n"
  3911.     "   You should have received a copy of the GNU General Public License\n"
  3912.     "   along with this program; if not, write to the Free Software\n"
  3913.     "   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.\n"
  3914.     "   \n"
  3915.     "   The GNU General Public License is contained in the file LICENSE.\n"
  3916.     "   \n"
  3917.    );
  3918. }
  3919.  
  3920.  
  3921. /*---------------------------------------------*/
  3922. static void usage ( Char *fullProgName )
  3923. {
  3924.    fprintf (
  3925.       stderr,
  3926.       "bzip2, a block-sorting file compressor.  "
  3927.       "Version 0.1pl2, 29-Aug-97.\n"
  3928.       "\n   usage: %s [flags and input files in any order]\n"
  3929.       "\n"
  3930.       "   -h --help           print this message\n"
  3931.       "   -d --decompress     force decompression\n"
  3932.       "   -f --compress       force compression\n"
  3933.       "   -t --test           test compressed file integrity\n"
  3934.       "   -c --stdout         output to standard out\n"
  3935.       "   -v --verbose        be verbose (a 2nd -v gives more)\n"
  3936.       "   -k --keep           keep (don't delete) input files\n"
  3937.       "   -L --license        display software version & license\n"
  3938.       "   -V --version        display software version & license\n"
  3939.       "   -s --small          use less memory (at most 2500k)\n"
  3940.       "   -1 .. -9            set block size to 100k .. 900k\n"
  3941.       "   --repetitive-fast   compress repetitive blocks faster\n"
  3942.       "   --repetitive-best   compress repetitive blocks better\n"
  3943.       "\n"
  3944.       "   If invoked as `bzip2', the default action is to compress.\n"
  3945.       "              as `bunzip2', the default action is to decompress.\n"
  3946.       "\n"
  3947.       "   If no file names are given, bzip2 compresses or decompresses\n"
  3948.       "   from standard input to standard output.  You can combine\n"
  3949.       "   flags, so `-v -4' means the same as -v4 or -4v, &c.\n"
  3950.       #if BZ_UNIX
  3951.       "\n"
  3952.       #endif
  3953.       ,
  3954.  
  3955.       fullProgName
  3956.    );
  3957. }
  3958.  
  3959.  
  3960. /*---------------------------------------------*/
  3961. /*--
  3962.   All the garbage from here to main() is purely to
  3963.   implement a linked list of command-line arguments,
  3964.   into which main() copies argv[1 .. argc-1].
  3965.  
  3966.   The purpose of this ridiculous exercise is to
  3967.   facilitate the expansion of wildcard characters
  3968.   * and ? in filenames for halfwitted OSs like
  3969.   MSDOS, Windows 95 and NT.
  3970.  
  3971.   The actual Dirty Work is done by the platform-specific
  3972.   macro APPEND_FILESPEC.
  3973. --*/
  3974.  
  3975. typedef
  3976.    struct zzzz {
  3977.       Char        *name;
  3978.       struct zzzz *link;
  3979.    }
  3980.    Cell;
  3981.  
  3982.  
  3983. /*---------------------------------------------*/
  3984. static void *myMalloc ( Int32 n )
  3985. {
  3986.    void* p;
  3987.  
  3988.    p = malloc ( (size_t)n );
  3989.    if (p == NULL) {
  3990.       fprintf (
  3991.          stderr,
  3992.          "%s: `malloc' failed on request for %d bytes.\n",
  3993.          progName, n
  3994.       );
  3995.       exit ( 1 );
  3996.    }
  3997.    return p;
  3998. }
  3999.  
  4000.  
  4001. /*---------------------------------------------*/
  4002. Cell *mkCell ( void )
  4003. {
  4004.    Cell *c;
  4005.  
  4006.    c = (Cell*) myMalloc ( sizeof ( Cell ) );
  4007.    c->name = NULL;
  4008.    c->link = NULL;
  4009.    return c;
  4010. }
  4011.  
  4012.  
  4013. /*---------------------------------------------*/
  4014. Cell *snocString ( Cell *root, Char *name )
  4015. {
  4016.    if (root == NULL) {
  4017.       Cell *tmp = mkCell();
  4018.       tmp->name = (Char*) myMalloc ( 5 + strlen(name) );
  4019.       strcpy ( tmp->name, name );
  4020.       return tmp;
  4021.    } else {
  4022.       Cell *tmp = root;
  4023.       while (tmp->link != NULL) tmp = tmp->link;
  4024.       tmp->link = snocString ( tmp->link, name );
  4025.       return root;
  4026.    }
  4027. }
  4028.  
  4029. /*---------------------------------------------*/
  4030. #define ISFLAG(s) (strcmp(aa->name, (s))==0)
  4031.  
  4032. #define LIBRARY
  4033. #ifdef LIBRARY
  4034. IntNative Main ( IntNative argc, Char *argv[] )
  4035. #else
  4036. IntNative main ( IntNative argc, Char *argv[] )
  4037. #endif
  4038. {
  4039.    Int32  i, j;
  4040.    Char   *tmp;
  4041.    Cell   *argList;
  4042.    Cell   *aa;
  4043.  
  4044.  
  4045.    #if DEBUG
  4046.       fprintf ( stderr, "bzip2: *** compiled with debugging ON ***\n" );
  4047.    #endif
  4048.  
  4049.    /*-- Be really really really paranoid :-) --*/
  4050.    if (sizeof(Int32) != 4 || sizeof(UInt32) != 4  ||
  4051.        sizeof(Int16) != 2 || sizeof(UInt16) != 2  ||
  4052.        sizeof(Char)  != 1 || sizeof(UChar)  != 1) {
  4053.       fprintf ( stderr,
  4054.                 "bzip2: I'm not configured correctly for this platform!\n"
  4055.                 "\tI require Int32, Int16 and Char to have sizes\n"
  4056.                 "\tof 4, 2 and 1 bytes to run properly, and they don't.\n"
  4057.                 "\tProbably you can fix this by defining them correctly,\n"
  4058.                 "\tand recompiling.  Bye!\n" );
  4059.       exit(1);
  4060.    }
  4061.  
  4062.  
  4063.    /*-- Set up signal handlers --*/
  4064.    signal (SIGINT,  mySignalCatcher);
  4065.    signal (SIGTERM, mySignalCatcher);
  4066.    signal (SIGSEGV, mySIGSEGVorSIGBUScatcher);
  4067.    #if BZ_UNIX
  4068.    signal (SIGHUP,  mySignalCatcher);
  4069.    signal (SIGBUS,  mySIGSEGVorSIGBUScatcher);
  4070.    #endif
  4071.  
  4072.  
  4073.    /*-- Initialise --*/
  4074.    outputHandleJustInCase  = NULL;
  4075.    ftab                    = NULL;
  4076.    ll4                     = NULL;
  4077.    ll16                    = NULL;
  4078.    ll8                     = NULL;
  4079.    tt                      = NULL;
  4080.    block                   = NULL;
  4081.    zptr                    = NULL;
  4082.    smallMode               = False;
  4083.    keepInputFiles          = False;
  4084.    verbosity               = 0;
  4085.    blockSize100k           = 9;
  4086.    testFailsExist          = False;
  4087.    bsStream                = NULL;
  4088.    numFileNames            = 0;
  4089.    numFilesProcessed       = 0;
  4090.    workFactor              = 30;
  4091.  
  4092.    strcpy ( inName,  "(none)" );
  4093.    strcpy ( outName, "(none)" );
  4094.  
  4095.    strcpy ( progNameReally, argv[0] );
  4096.    progName = &progNameReally[0];
  4097.    for (tmp = &progNameReally[0]; *tmp != '\0'; tmp++)
  4098.       if (*tmp == PATH_SEP) progName = tmp + 1;
  4099.  
  4100.  
  4101.    /*-- Expand filename wildcards in arg list --*/
  4102.    argList = NULL;
  4103.    for (i = 1; i <= argc-1; i++)
  4104.       APPEND_FILESPEC(argList, argv[i]);
  4105.  
  4106.  
  4107.    /*-- Find the length of the longest filename --*/
  4108.    longestFileName = 7;
  4109.    numFileNames    = 0;
  4110.    for (aa = argList; aa != NULL; aa = aa->link)
  4111.       if (aa->name[0] != '-') {
  4112.          numFileNames++;
  4113.          if (longestFileName < (Int32)strlen(aa->name) )
  4114.             longestFileName = (Int32)strlen(aa->name);
  4115.       }
  4116.  
  4117.  
  4118.    /*-- Determine what to do (compress/uncompress/test). --*/
  4119.    /*-- Note that subsequent flag handling may change this. --*/
  4120.    opMode = OM_Z;
  4121.  
  4122.    if ( (strcmp ( "bunzip2",     progName ) == 0) ||
  4123.         (strcmp ( "BUNZIP2",     progName ) == 0) ||
  4124.         (strcmp ( "bunzip2.exe", progName ) == 0) ||
  4125.         (strcmp ( "BUNZIP2.EXE", progName ) == 0) )
  4126.       opMode = OM_UNZ;
  4127.  
  4128.  
  4129.    /*-- Determine source modes; flag handling may change this too. --*/
  4130.    if (numFileNames == 0)
  4131.       srcMode = SM_I2O; else srcMode = SM_F2F;
  4132.  
  4133.  
  4134.    /*-- Look at the flags. --*/
  4135.    for (aa = argList; aa != NULL; aa = aa->link)
  4136.       if (aa->name[0] == '-' && aa->name[1] != '-')
  4137.          for (j = 1; aa->name[j] != '\0'; j++)
  4138.             switch (aa->name[j]) {
  4139.                case 'c': srcMode          = SM_F2O; break;
  4140.                case 'd': opMode           = OM_UNZ; break;
  4141.                case 'f': opMode           = OM_Z; break;
  4142.                case 't': opMode           = OM_TEST; break;
  4143.                case 'k': keepInputFiles   = True; break;
  4144.                case 's': smallMode        = True; break;
  4145.                case '1': blockSize100k    = 1; break;
  4146.                case '2': blockSize100k    = 2; break;
  4147.                case '3': blockSize100k    = 3; break;
  4148.                case '4': blockSize100k    = 4; break;
  4149.                case '5': blockSize100k    = 5; break;
  4150.                case '6': blockSize100k    = 6; break;
  4151.                case '7': blockSize100k    = 7; break;
  4152.                case '8': blockSize100k    = 8; break;
  4153.                case '9': blockSize100k    = 9; break;
  4154.                case 'V':
  4155.                case 'L': license();            break;
  4156.                case 'v': verbosity++; break;
  4157.                case 'h': usage ( progName );
  4158.                          exit ( 1 );
  4159.                          break;
  4160.                default:  fprintf ( stderr, "%s: Bad flag `%s'\n",
  4161.                                    progName, aa->name );
  4162.                          usage ( progName );
  4163.                          exit ( 1 );
  4164.                          break;
  4165.          }
  4166.  
  4167.    /*-- And again ... --*/
  4168.    for (aa = argList; aa != NULL; aa = aa->link) {
  4169.       if (ISFLAG("--stdout"))            srcMode          = SM_F2O;  else
  4170.       if (ISFLAG("--decompress"))        opMode           = OM_UNZ;  else
  4171.       if (ISFLAG("--compress"))          opMode           = OM_Z;    else
  4172.       if (ISFLAG("--test"))              opMode           = OM_TEST; else
  4173.       if (ISFLAG("--keep"))              keepInputFiles   = True;    else
  4174.       if (ISFLAG("--small"))             smallMode        = True;    else
  4175.       if (ISFLAG("--version"))           license();                  else
  4176.       if (ISFLAG("--license"))           license();                  else
  4177.       if (ISFLAG("--repetitive-fast"))   workFactor = 5;             else
  4178.       if (ISFLAG("--repetitive-best"))   workFactor = 150;           else
  4179.       if (ISFLAG("--verbose"))           verbosity++;                else
  4180.       if (ISFLAG("--help"))              { usage ( progName ); exit ( 1 ); }
  4181.          else
  4182.          if (strncmp ( aa->name, "--", 2) == 0) {
  4183.             fprintf ( stderr, "%s: Bad flag `%s'\n", progName, aa->name );
  4184.             usage ( progName );
  4185.             exit ( 1 );
  4186.          }
  4187.    }
  4188.  
  4189.    if (opMode == OM_Z && smallMode) blockSize100k = 2;
  4190.  
  4191.    if (opMode == OM_Z && srcMode == SM_F2O && numFileNames > 1) {
  4192.       fprintf ( stderr, "%s: I won't compress multiple files to stdout.\n",
  4193.                 progName );
  4194.       exit ( 1 );
  4195.    }
  4196.  
  4197.    if (srcMode == SM_F2O && numFileNames == 0) {
  4198.       fprintf ( stderr, "%s: -c expects at least one filename.\n",
  4199.                 progName );
  4200.       exit ( 1 );
  4201.    }
  4202.  
  4203.    if (opMode == OM_TEST && srcMode == SM_F2O) {
  4204.       fprintf ( stderr, "%s: -c and -t cannot be used together.\n",
  4205.                 progName );
  4206.       exit ( 1 );
  4207.    }
  4208.  
  4209.    if (opMode != OM_Z) blockSize100k = 0;
  4210.  
  4211.    if (opMode == OM_Z) {
  4212.       /* allocateCompressStructures();*/
  4213.       if (srcMode == SM_I2O)
  4214.          compress ( NULL );
  4215.          else
  4216.          for (aa = argList; aa != NULL; aa = aa->link)
  4217.             if (aa->name[0] != '-') {
  4218.                numFilesProcessed++;
  4219.                compress ( aa->name );
  4220.             }
  4221.    } else
  4222.    if (opMode == OM_UNZ) {
  4223.       if (srcMode == SM_I2O)
  4224.          uncompress ( NULL );
  4225.          else
  4226.          for (aa = argList; aa != NULL; aa = aa->link)
  4227.             if (aa->name[0] != '-') {
  4228.                numFilesProcessed++;
  4229.                uncompress ( aa->name );
  4230.             }
  4231.    } else {
  4232.       testFailsExist = False;
  4233.       if (srcMode == SM_I2O)
  4234.          testf ( NULL );
  4235.          else
  4236.          for (aa = argList; aa != NULL; aa = aa->link)
  4237.             if (aa->name[0] != '-') {
  4238.                numFilesProcessed++;
  4239.                testf ( aa->name );
  4240.             }
  4241.       if (testFailsExist) {
  4242.          fprintf ( stderr,
  4243.            "\n"
  4244.            "You can use the `bzip2recover' program to *attempt* to recover\n"
  4245.            "data from undamaged sections of corrupted files.\n\n"
  4246.          );
  4247.          exit(2);
  4248.       }
  4249.    }
  4250.    return 0;
  4251. }
  4252.  
  4253.  
  4254. /*-----------------------------------------------------------*/
  4255. /*--- end                                         bzip2.c ---*/
  4256. /*-----------------------------------------------------------*/
  4257.