(WEIGHTOF(zw1)+WEIGHTOF(zw2)) |                    \
   (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))

{                                             \
   while (bsLive < nz) {                      \
      Int32 zzi = fgetc ( bsStream );         \
      if (zzi == EOF) compressedStreamEOF();  \
      bsBuff = (bsBuff << 8) | (zzi & 0xffL); \
      bsLive += 8;                            \
   }                                          \
}

{                                             \
   while (bsLive >= 8) {                      \
      fputc ( (UChar)(bsBuff >> 24),          \
               bsStream );                    \
      bsBuff <<= 8;                           \
      bsLive -= 8;                            \
      bytesOut++;                             \
   }                                          \
}

{                                             \
   bsNEEDR(1);                                \
   vz = (bsBuff >> (bsLive-1)) & 1;           \
   bsLive--;                                  \
}

{                                                     \
   Int32 zz, yy, tmp;                                 \
   zz = z; tmp = heap[zz];                            \
   while (True) {                                     \
      yy = zz << 1;                                   \
      if (yy > nHeap) break;                          \
      if (yy < nHeap &&                               \
          weight[heap[yy+1]] < weight[heap[yy]])      \
         yy++;                                        \
      if (weight[tmp] < weight[heap[yy]]) break;      \
      heap[zz] = heap[yy];                            \
      zz = yy;                                        \
   }                                                  \
   heap[zz] = tmp;                                    \
}

\
      cccc = ll8[tPos];                      \
      tPos = tt[tPos];

{                                         \
   Int32 zt, zn, zvec, zj;                \
   if (groupPos == 0) {                   \
      groupNo++;                          \
      groupPos = G_SIZE;                  \
   }                                      \
   groupPos--;                            \
   zt = selector[groupNo];                \
   zn = minLens[zt];                      \
   zvec = bsR ( zn );                     \
   while (zvec > limit[zt][zn]) {         \
      zn++; bsR1(zj);                     \
      zvec = (zvec << 1) | zj;            \
   };                                     \
   lval = perm[zt][zvec - base[zt][zn]];  \
}

\
      cccc = indexIntoF ( tPos, cftab );    \
      tPos = GET_LL(tPos);

{ sp--;               \
                        lz = stack[sp].ll;  \
                        hz = stack[sp].hh;  \
                        dz = stack[sp].dd; }

{ stack[sp].ll = lz; \
                         stack[sp].hh = hz; \
                         stack[sp].dd = dz; \
                         sp++; }

Int32 rNToGo = 0;                              \
   Int32 rTPos  = 0;                              \

if (rNToGo == 0) {                             \
      rNToGo = rNums[rTPos];                      \
      rTPos++; if (rTPos == 512) rTPos = 0;       \
   }                                              \
   rNToGo--;

{ ll16[i] = (UInt16)(n & 0x0000ffff);  \
     SET_LL4(i, n >> 16);                 \
   }

{ if (((i) & 0x1) == 0)                                    \
        ll4[(i) >> 1] = (ll4[(i) >> 1] & 0xf0) | (n); else    \
        ll4[(i) >> 1] = (ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
   }

{                                           \
   crcVar = (crcVar << 8) ^                 \
            crc32Table[(crcVar >> 24) ^     \
                       ((UChar)cha)];       \
}

{                                                     \
   Int32 zz, tmp;                                     \
   zz = z; tmp = heap[zz];                            \
   while (weight[tmp] < weight[heap[zz >> 1]]) {      \
      heap[zz] = heap[zz >> 1];                       \
      zz >>= 1;                                       \
   }                                                  \
   heap[zz] = tmp;                                    \
}

00991 {
00992    Int32 n  = 100000 * blockSize100k;
00993    block    = malloc ( (n + 1 + NUM_OVERSHOOT_BYTES) * sizeof(UChar) );
00994    quadrant = malloc ( (n     + NUM_OVERSHOOT_BYTES) * sizeof(Int16) );
00995    zptr     = malloc ( n                             * sizeof(Int32) );
00996    ftab     = malloc ( 65537                         * sizeof(Int32) );
00997 
00998    if (block == NULL || quadrant == NULL ||
00999        zptr == NULL  || ftab == NULL) {
01000       Int32 totalDraw
01001          = (n + 1 + NUM_OVERSHOOT_BYTES) * sizeof(UChar) +
01002            (n     + NUM_OVERSHOOT_BYTES) * sizeof(Int16) +
01003            n                             * sizeof(Int32) +
01004            65537                         * sizeof(Int32);
01005 
01006       compressOutOfMemory ( totalDraw, n );
01007    }
01008 
01009    /*--
01010       Since we want valid indexes for block of
01011       -1 to n + NUM_OVERSHOOT_BYTES - 1
01012       inclusive.
01013    --*/
01014    block++;
01015 
01016    /*--
01017       The back end needs a place to store the MTF values
01018       whilst it calculates the coding tables.  We could
01019       put them in the zptr array.  However, these values
01020       will fit in a short, so we overlay szptr at the 
01021       start of zptr, in the hope of reducing the number
01022       of cache misses induced by the multiple traversals
01023       of the MTF values when calculating coding tables.
01024       Seems to improve compression speed by about 1%.
01025    --*/
01026    szptr = (UInt16*)zptr;
01027 }

03114 {
03115    fprintf ( stderr,
03116              "\n%s: error when reading background model code lengths,\n"
03117              "\twhich probably means the compressed file is corrupted.\n",
03118              progName );
03119    showFileNames();
03120    cadvise();
03121    cleanUpAndFail( 2 );
03122 }

03180 {
03181    fprintf ( stderr,
03182              "\n%s: bad block header in the compressed file,\n"
03183              "\twhich probably means it is corrupted.\n",
03184              progName );
03185    showFileNames();
03186    cadvise();
03187    cleanUpAndFail( 2 );
03188 }

03193 {
03194    fprintf ( stderr,
03195              "\n%s: read past the end of compressed data,\n"
03196              "\twhich probably means it is corrupted.\n",
03197              progName );
03198    showFileNames();
03199    cadvise();
03200    cleanUpAndFail( 2 );
03201 }

03166 {
03167    fprintf ( stderr,
03168              "\n%s: block overrun during decompression,\n"
03169              "\twhich probably means the compressed file\n"
03170              "\tis corrupted.\n",
03171              progName );
03172    showFileNames();
03173    cadvise();
03174    cleanUpAndFail( 2 );
03175 }

00653 {
00654    if (bsWriting)
00655       while (bsLive > 0) {
00656          fputc ( (UChar)(bsBuff >> 24), bsStream );
00657          bsBuff <<= 8;
00658          bsLive -= 8;
00659          bytesOut++;
00660       }
00661    bsStream = NULL;
00662 }

00755 {
00756    return (Int32)bsGetUInt32();
00757 }

00748 {
00749    return (UInt32)bsR(numBits);
00750 }

00721 {
00722    return (UChar)bsR(8);
00723 }

00735 {
00736    UInt32 u;
00737    u = 0;
00738    u = (u << 8) | bsR(8);
00739    u = (u << 8) | bsR(8);
00740    u = (u << 8) | bsR(8);
00741    u = (u << 8) | bsR(8);
00742    return u;
00743 }

00772 {
00773    bsPutUInt32 ( (UInt32)c );
00774 }

00779 {
00780    bsW ( numBits, c );
00781 }

00728 {
00729    bsW(8, (UInt32)c );
00730 }

00762 {
00763    bsW ( 8, (u >> 24) & 0xffL );
00764    bsW ( 8, (u >> 16) & 0xffL );
00765    bsW ( 8, (u >>  8) & 0xffL );
00766    bsW ( 8,  u        & 0xffL );
00767 }

00701 {
00702    UInt32 v;
00703    bsNEEDR ( n );
00704    v = (bsBuff >> (bsLive-n)) & ((1 << n)-1);
00705    bsLive -= n;
00706    return v;
00707 }

00640 {
00641    if (bsStream != NULL) panic ( "bsSetStream" );
00642    bsStream = f;
00643    bsLive = 0;
00644    bsBuff = 0;
00645    bytesOut = 0;
00646    bytesIn = 0;
00647    bsWriting = wr;
00648 }

00712 {
00713    bsNEEDW ( n );
00714    bsBuff |= (v << (32 - bsLive - n));
00715    bsLive += n;
00716 }

03047 {
03048    fprintf (
03049       stderr,
03050       "\nIt is possible that the compressed file(s) have become corrupted.\n"
03051         "You can use the -tvv option to test integrity of such files.\n\n"
03052         "You can use the `bzip2recover' program to *attempt* to recover\n"
03053         "data from undamaged sections of corrupted files.\n\n"
03054     );
03055 }

03072 {
03073    IntNative retVal;
03074 
03075    if ( srcMode == SM_F2F && opMode != OM_TEST ) {
03076       fprintf ( stderr, "%s: Deleting output file %s, if it exists.\n",
03077                 progName,
03078                 outName==NULL ? "(null)" : outName );
03079       if (outputHandleJustInCase != NULL)
03080          fclose ( outputHandleJustInCase );
03081       retVal = remove ( outName );
03082       if (retVal != 0)
03083          fprintf ( stderr,
03084                    "%s: WARNING: deletion of output file (apparently) failed.\n",
03085                    progName );
03086    }
03087    if (numFileNames > 0 && numFilesProcessed < numFileNames) {
03088       fprintf ( stderr, 
03089                 "%s: WARNING: some files have not been processed:\n"
03090                 "\t%d specified on command line, %d not processed yet.\n\n",
03091                 progName, numFileNames, 
03092                           numFileNames - numFilesProcessed );
03093    }
03094    exit ( ec );
03095 }

03350 {
03351    FILE *inStr;
03352    FILE *outStr;
03353 
03354    if (name == NULL && srcMode != SM_I2O)
03355       panic ( "compress: bad modes\n" );
03356 
03357    switch (srcMode) {
03358       case SM_I2O: strcpy ( inName, "(stdin)" );
03359                    strcpy ( outName, "(stdout)" ); break;
03360       case SM_F2F: strcpy ( inName, name );
03361                    strcpy ( outName, name );
03362                    strcat ( outName, ".bz2" ); break;
03363       case SM_F2O: strcpy ( inName, name );
03364                    strcpy ( outName, "(stdout)" ); break;
03365    }
03366 
03367    if ( srcMode != SM_I2O && containsDubiousChars ( inName ) ) {
03368       fprintf ( stderr, "%s: There are no files matching `%s'.\n",
03369       progName, inName );
03370       return;
03371    }
03372    if ( srcMode != SM_I2O && !fileExists ( inName ) ) {
03373       fprintf ( stderr, "%s: Input file %s doesn't exist, skipping.\n",
03374                 progName, inName );
03375       return;
03376    }
03377    if ( srcMode != SM_I2O && endsInBz2 ( inName )) {
03378       fprintf ( stderr, "%s: Input file name %s ends in `.bz2', skipping.\n",
03379                 progName, inName );
03380       return;
03381    }
03382    if ( srcMode != SM_I2O && notABogStandardFile ( inName )) {
03383       fprintf ( stderr, "%s: Input file %s is not a normal file, skipping.\n",
03384                 progName, inName );
03385       return;
03386    }
03387    if ( srcMode == SM_F2F && fileExists ( outName ) ) {
03388       fprintf ( stderr, "%s: Output file %s already exists, skipping.\n",
03389                 progName, outName );
03390       return;
03391    }
03392 
03393    switch ( srcMode ) {
03394 
03395       case SM_I2O:
03396          inStr = stdin;
03397          outStr = stdout;
03398          if ( isatty ( fileno ( stdout ) ) ) {
03399             fprintf ( stderr,
03400                       "%s: I won't write compressed data to a terminal.\n",
03401                       progName );
03402             fprintf ( stderr, "%s: For help, type: `%s --help'.\n",
03403                               progName, progName );
03404             return;
03405          };
03406          break;
03407 
03408       case SM_F2O:
03409          inStr = fopen ( inName, "rb" );
03410          outStr = stdout;
03411          if ( isatty ( fileno ( stdout ) ) ) {
03412             fprintf ( stderr,
03413                       "%s: I won't write compressed data to a terminal.\n",
03414                       progName );
03415             fprintf ( stderr, "%s: For help, type: `%s --help'.\n",
03416                               progName, progName );
03417             return;
03418          };
03419          if ( inStr == NULL ) {
03420             fprintf ( stderr, "%s: Can't open input file %s, skipping.\n",
03421                       progName, inName );
03422             return;
03423          };
03424          break;
03425 
03426       case SM_F2F:
03427          inStr = fopen ( inName, "rb" );
03428          outStr = fopen ( outName, "wb" );
03429          if ( outStr == NULL) {
03430             fprintf ( stderr, "%s: Can't create output file %s, skipping.\n",
03431                       progName, outName );
03432             return;
03433          }
03434          if ( inStr == NULL ) {
03435             fprintf ( stderr, "%s: Can't open input file %s, skipping.\n",
03436                       progName, inName );
03437             return;
03438          };
03439          break;
03440 
03441       default:
03442          panic ( "compress: bad srcMode" );
03443          break;
03444    }
03445 
03446    if (verbosity >= 1) {
03447       fprintf ( stderr,  "  %s: ", inName );
03448       pad ( inName );
03449       fflush ( stderr );
03450    }
03451 
03452    /*--- Now the input and output handles are sane.  Do the Biz. ---*/
03453    outputHandleJustInCase = outStr;
03454    compressStream ( inStr, outStr );
03455    outputHandleJustInCase = NULL;
03456 
03457    /*--- If there was an I/O error, we won't get here. ---*/
03458    if ( srcMode == SM_F2F ) {
03459       copyDateAndPermissions ( inName, outName );
03460       if ( !keepInputFiles ) {
03461          IntNative retVal = remove ( inName );
03462          ERROR_IF_NOT_ZERO ( retVal );
03463       }
03464    }
03465 }

03140 {
03141    fprintf ( stderr,
03142              "\n%s: Compressed file ends unexpectedly;\n\t"
03143              "perhaps it is corrupted?  *Possible* reason follows.\n",
03144              progName );
03145    perror ( progName );
03146    showFileNames();
03147    cadvise();
03148    cleanUpAndFail( 2 );
03149 }

03253 {
03254    fprintf ( stderr,
03255              "\n%s: Can't allocate enough memory for compression.\n"
03256              "\tRequested %d bytes for a block size of %d.\n"
03257              "\tTry selecting a small block size (with flag -s).\n",
03258              progName, draw, blockSize );
03259    showFileNames();
03260    cleanUpAndFail(1);
03261 }

02676 {
02677    IntNative  retVal;
02678    UInt32     blockCRC, combinedCRC;
02679    Int32      blockNo;
02680 
02681    blockNo  = 0;
02682    bytesIn  = 0;
02683    bytesOut = 0;
02684    nBlocksRandomised = 0;
02685 
02686    SET_BINARY_MODE(stream);
02687    SET_BINARY_MODE(zStream);
02688 
02689    ERROR_IF_NOT_ZERO ( ferror(stream) );
02690    ERROR_IF_NOT_ZERO ( ferror(zStream) );
02691 
02692    bsSetStream ( zStream, True );
02693 
02694    /*--- Write `magic' bytes B and Z,
02695          then h indicating file-format == huffmanised,
02696          followed by a digit indicating blockSize100k.
02697    ---*/
02698    bsPutUChar ( 'B' );
02699    bsPutUChar ( 'Z' );
02700    bsPutUChar ( 'h' );
02701    bsPutUChar ( '0' + blockSize100k );
02702 
02703    combinedCRC = 0;
02704 
02705    if (verbosity >= 2) fprintf ( stderr, "\n" );
02706 
02707    while (True) {
02708 
02709       blockNo++;
02710       initialiseCRC ();
02711       loadAndRLEsource ( stream );
02712       ERROR_IF_NOT_ZERO ( ferror(stream) );
02713       if (last == -1) break;
02714 
02715       blockCRC = getFinalCRC ();
02716       combinedCRC = (combinedCRC << 1) | (combinedCRC >> 31);
02717       combinedCRC ^= blockCRC;
02718 
02719       if (verbosity >= 2)
02720          fprintf ( stderr, "    block %d: crc = 0x%8x, combined CRC = 0x%8x, size = %d",
02721                            blockNo, blockCRC, combinedCRC, last+1 );
02722 
02723       /*-- sort the block and establish posn of original string --*/
02724       doReversibleTransformation ();
02725 
02726       /*--
02727         A 6-byte block header, the value chosen arbitrarily
02728         as 0x314159265359 :-).  A 32 bit value does not really
02729         give a strong enough guarantee that the value will not
02730         appear by chance in the compressed datastream.  Worst-case
02731         probability of this event, for a 900k block, is about
02732         2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits.
02733         For a compressed file of size 100Gb -- about 100000 blocks --
02734         only a 48-bit marker will do.  NB: normal compression/
02735         decompression do *not* rely on these statistical properties.
02736         They are only important when trying to recover blocks from
02737         damaged files.
02738       --*/
02739       bsPutUChar ( 0x31 ); bsPutUChar ( 0x41 );
02740       bsPutUChar ( 0x59 ); bsPutUChar ( 0x26 );
02741       bsPutUChar ( 0x53 ); bsPutUChar ( 0x59 );
02742 
02743       /*-- Now the block's CRC, so it is in a known place. --*/
02744       bsPutUInt32 ( blockCRC );
02745 
02746       /*-- Now a single bit indicating randomisation. --*/
02747       if (blockRandomised) {
02748          bsW(1,1); nBlocksRandomised++;
02749       } else
02750          bsW(1,0);
02751 
02752       /*-- Finally, block's contents proper. --*/
02753       moveToFrontCodeAndSend ();
02754 
02755       ERROR_IF_NOT_ZERO ( ferror(zStream) );
02756    }
02757 
02758    if (verbosity >= 2 && nBlocksRandomised > 0)
02759       fprintf ( stderr, "    %d block%s needed randomisation\n", 
02760                         nBlocksRandomised,
02761                         nBlocksRandomised == 1 ? "" : "s" );
02762 
02763    /*--
02764       Now another magic 48-bit number, 0x177245385090, to
02765       indicate the end of the last block.  (sqrt(pi), if
02766       you want to know.  I did want to use e, but it contains
02767       too much repetition -- 27 18 28 18 28 46 -- for me
02768       to feel statistically comfortable.  Call me paranoid.)
02769    --*/
02770 
02771    bsPutUChar ( 0x17 ); bsPutUChar ( 0x72 );
02772    bsPutUChar ( 0x45 ); bsPutUChar ( 0x38 );
02773    bsPutUChar ( 0x50 ); bsPutUChar ( 0x90 );
02774 
02775    bsPutUInt32 ( combinedCRC );
02776    if (verbosity >= 2)
02777       fprintf ( stderr, "    final combined CRC = 0x%x\n   ", combinedCRC );
02778 
02779    /*-- Close the files in an utterly paranoid way. --*/
02780    bsFinishedWithStream ();
02781 
02782    ERROR_IF_NOT_ZERO ( ferror(zStream) );
02783    retVal = fflush ( zStream );
02784    ERROR_IF_EOF ( retVal );
02785    retVal = fclose ( zStream );
02786    ERROR_IF_EOF ( retVal );
02787 
02788    ERROR_IF_NOT_ZERO ( ferror(stream) );
02789    retVal = fclose ( stream );
02790    ERROR_IF_EOF ( retVal );
02791 
02792    if (bytesIn == 0) bytesIn = 1;
02793    if (bytesOut == 0) bytesOut = 1;
02794 
02795    if (verbosity >= 1)
02796       fprintf ( stderr, "%6.3f:1, %6.3f bits/byte, "
02797                         "%5.2f%% saved, %d in, %d out.\n",
02798                 (float)bytesIn / (float)bytesOut,
02799                 (8.0 * (float)bytesOut) / (float)bytesIn,
02800                 100.0 * (1.0 - (float)bytesOut / (float)bytesIn),
02801                 bytesIn,
02802                 bytesOut
02803               );
02804 }

03340 {
03341    Bool cdc = False;
03342    for (; *name != '\0'; name++)
03343       if (*name == '?' || *name == '*') cdc = True;
03344    return cdc;
03345 }

03306 {
03307    #if BZ_UNIX
03308    IntNative      retVal;
03309    struct MY_STAT statBuf;
03310    struct utimbuf uTimBuf;
03311 
03312    retVal = MY_LSTAT ( srcName, &statBuf );
03313    ERROR_IF_NOT_ZERO ( retVal );
03314    uTimBuf.actime = statBuf.st_atime;
03315    uTimBuf.modtime = statBuf.st_mtime;
03316 
03317    retVal = chmod ( dstName, statBuf.st_mode );
03318    ERROR_IF_NOT_ZERO ( retVal );
03319    retVal = utime ( dstName, &uTimBuf );
03320    ERROR_IF_NOT_ZERO ( retVal );
03321    #endif
03322 }

03127 {
03128    fprintf ( stderr,
03129              "\n%s: Data integrity error when decompressing.\n"
03130              "\tStored CRC = 0x%x, computed CRC = 0x%x\n",
03131              progName, crcStored, crcComputed );
03132    showFileNames();
03133    cadvise();
03134    cleanUpAndFail( 2 );
03135 }

02251 {
02252    Int32 i;
02253 
02254    if (verbosity >= 2) fprintf ( stderr, "\n" );
02255 
02256    workLimit       = workFactor * last;
02257    workDone        = 0;
02258    blockRandomised = False;
02259    firstAttempt    = True;
02260 
02261    sortIt ();
02262 
02263    if (verbosity >= 3)
02264       fprintf ( stderr, "      %d work, %d block, ratio %5.2f\n",
02265                         workDone, last, (float)workDone / (float)(last) );
02266 
02267    if (workDone > workLimit && firstAttempt) {
02268       if (verbosity >= 2)
02269          fprintf ( stderr, "    sorting aborted; randomising block\n" );
02270       randomiseBlock ();
02271       workLimit = workDone = 0;
02272       blockRandomised = True;
02273       firstAttempt = False;
02274       sortIt();
02275       if (verbosity >= 3)
02276          fprintf ( stderr, "      %d work, %d block, ratio %f\n",
02277                            workDone, last, (float)workDone / (float)(last) );
02278    }
02279 
02280    origPtr = -1;
02281    for (i = 0; i <= last; i++)
02282        if (zptr[i] == 0)
02283           { origPtr = i; break; };
02284 
02285    if (origPtr == -1) panic ( "doReversibleTransformation" );
02286 }

03327 {
03328    Int32 n = strlen ( name );
03329    if (n <= 4) return False;
03330    return
03331       (name[n-4] == '.' &&
03332        name[n-3] == 'b' &&
03333        name[n-2] == 'z' &&
03334        name[n-1] == '2');
03335 }

03280 {
03281    FILE *tmp   = fopen ( name, "rb" );
03282    Bool exists = (tmp != NULL);
03283    if (tmp != NULL) fclose ( tmp );
03284    return exists;
03285 }

01672 {
01673    Int32 k;
01674    UChar c1, c2;
01675    UInt16 s1, s2;
01676 
01677    #if DEBUG
01678       /*--
01679         shellsort shouldn't ask to compare
01680         something with itself.
01681       --*/
01682       assert (i1 != i2);
01683    #endif
01684 
01685    c1 = block[i1];
01686    c2 = block[i2];
01687    if (c1 != c2) return (c1 > c2);
01688    i1++; i2++;
01689 
01690    c1 = block[i1];
01691    c2 = block[i2];
01692    if (c1 != c2) return (c1 > c2);
01693    i1++; i2++;
01694 
01695    c1 = block[i1];
01696    c2 = block[i2];
01697    if (c1 != c2) return (c1 > c2);
01698    i1++; i2++;
01699 
01700    c1 = block[i1];
01701    c2 = block[i2];
01702    if (c1 != c2) return (c1 > c2);
01703    i1++; i2++;
01704 
01705    c1 = block[i1];
01706    c2 = block[i2];
01707    if (c1 != c2) return (c1 > c2);
01708    i1++; i2++;
01709 
01710    c1 = block[i1];
01711    c2 = block[i2];
01712    if (c1 != c2) return (c1 > c2);
01713    i1++; i2++;
01714 
01715    k = last + 1;
01716 
01717    do {
01718 
01719       c1 = block[i1];
01720       c2 = block[i2];
01721       if (c1 != c2) return (c1 > c2);
01722       s1 = quadrant[i1];
01723       s2 = quadrant[i2];
01724       if (s1 != s2) return (s1 > s2);
01725       i1++; i2++;
01726 
01727       c1 = block[i1];
01728       c2 = block[i2];
01729       if (c1 != c2) return (c1 > c2);
01730       s1 = quadrant[i1];
01731       s2 = quadrant[i2];
01732       if (s1 != s2) return (s1 > s2);
01733       i1++; i2++;
01734 
01735       c1 = block[i1];
01736       c2 = block[i2];
01737       if (c1 != c2) return (c1 > c2);
01738       s1 = quadrant[i1];
01739       s2 = quadrant[i2];
01740       if (s1 != s2) return (s1 > s2);
01741       i1++; i2++;
01742 
01743       c1 = block[i1];
01744       c2 = block[i2];
01745       if (c1 != c2) return (c1 > c2);
01746       s1 = quadrant[i1];
01747       s2 = quadrant[i2];
01748       if (s1 != s2) return (s1 > s2);
01749       i1++; i2++;
01750 
01751       if (i1 > last) { i1 -= last; i1--; };
01752       if (i2 > last) { i2 -= last; i2--; };
01753 
01754       k -= 4;
01755       workDone++;
01756    }
01757       while (k >= 0);
01758 
01759    return False;
01760 }

01097 {
01098    UChar  yy[256];
01099    Int32  i, j;
01100    UChar  tmp;
01101    UChar  tmp2;
01102    Int32  zPend;
01103    Int32  wr;
01104    Int32  EOB;
01105 
01106    makeMaps();
01107    EOB = nInUse+1;
01108 
01109    for (i = 0; i <= EOB; i++) mtfFreq[i] = 0;
01110 
01111    wr = 0;
01112    zPend = 0;
01113    for (i = 0; i < nInUse; i++) yy[i] = (UChar) i;
01114    
01115 
01116    for (i = 0; i <= last; i++) {
01117       UChar ll_i;
01118 
01119       #if DEBUG
01120          assert (wr <= i);
01121       #endif
01122 
01123       ll_i = unseqToSeq[block[zptr[i] - 1]];
01124       #if DEBUG
01125          assert (ll_i < nInUse);
01126       #endif
01127 
01128       j = 0;
01129       tmp = yy[j];
01130       while ( ll_i != tmp ) {
01131          j++;
01132          tmp2 = tmp;
01133          tmp = yy[j];
01134          yy[j] = tmp2;
01135       };
01136       yy[0] = tmp;
01137 
01138       if (j == 0) {
01139          zPend++;
01140       } else {
01141          if (zPend > 0) {
01142             zPend--;
01143             while (True) {
01144                switch (zPend % 2) {
01145                   case 0: szptr[wr] = RUNA; wr++; mtfFreq[RUNA]++; break;
01146                   case 1: szptr[wr] = RUNB; wr++; mtfFreq[RUNB]++; break;
01147                };
01148                if (zPend < 2) break;
01149                zPend = (zPend - 2) / 2;
01150             };
01151             zPend = 0;
01152          }
01153          szptr[wr] = j+1; wr++; mtfFreq[j+1]++;
01154       }
01155    }
01156 
01157    if (zPend > 0) {
01158       zPend--;
01159       while (True) {
01160          switch (zPend % 2) {
01161             case 0:  szptr[wr] = RUNA; wr++; mtfFreq[RUNA]++; break;
01162             case 1:  szptr[wr] = RUNB; wr++; mtfFreq[RUNB]++; break;
01163          };
01164          if (zPend < 2) break;
01165          zPend = (zPend - 2) / 2;
01166       };
01167    }
01168 
01169    szptr[wr] = EOB; wr++; mtfFreq[EOB]++;
01170 
01171    nMTF = wr;
01172 }

01559 {
01560    UChar  yy[256];
01561    Int32  i, j, nextSym, limitLast;
01562    Int32  EOB, groupNo, groupPos;
01563 
01564    limitLast = 100000 * blockSize100k;
01565    origPtr   = bsGetIntVS ( 24 );
01566 
01567    recvDecodingTables();
01568    EOB      = nInUse+1;
01569    groupNo  = -1;
01570    groupPos = 0;
01571 
01572    /*--
01573       Setting up the unzftab entries here is not strictly
01574       necessary, but it does save having to do it later
01575       in a separate pass, and so saves a block's worth of
01576       cache misses.
01577    --*/
01578    for (i = 0; i <= 255; i++) unzftab[i] = 0;
01579 
01580    for (i = 0; i <= 255; i++) yy[i] = (UChar) i;
01581 
01582    last = -1;
01583 
01584    GET_MTF_VAL(nextSym);
01585 
01586    while (True) {
01587 
01588       if (nextSym == EOB) break;
01589 
01590       if (nextSym == RUNA || nextSym == RUNB) {
01591          UChar ch;
01592          Int32 s = -1;
01593          Int32 N = 1;
01594          do {
01595             if (nextSym == RUNA) s = s + (0+1) * N; else
01596             if (nextSym == RUNB) s = s + (1+1) * N;
01597             N = N * 2;
01598             GET_MTF_VAL(nextSym);
01599          }
01600             while (nextSym == RUNA || nextSym == RUNB);
01601 
01602          s++;
01603          ch = seqToUnseq[yy[0]];
01604          unzftab[ch] += s;
01605 
01606          if (smallMode)
01607             while (s > 0) {
01608                last++; 
01609                ll16[last] = ch;
01610                s--;
01611             }
01612          else
01613             while (s > 0) {
01614                last++;
01615                ll8[last] = ch;
01616                s--;
01617             };
01618 
01619          if (last >= limitLast) blockOverrun();
01620          continue;
01621 
01622       } else {
01623 
01624          UChar tmp;
01625          last++; if (last >= limitLast) blockOverrun();
01626 
01627          tmp = yy[nextSym-1];
01628          unzftab[seqToUnseq[tmp]]++;
01629          if (smallMode)
01630             ll16[last] = seqToUnseq[tmp]; else
01631             ll8[last]  = seqToUnseq[tmp];
01632 
01633          /*--
01634             This loop is hammered during decompression,
01635             hence the unrolling.
01636 
01637             for (j = nextSym-1; j > 0; j--) yy[j] = yy[j-1];
01638          --*/
01639 
01640          j = nextSym-1;
01641          for (; j > 3; j -= 4) {
01642             yy[j]   = yy[j-1];
01643             yy[j-1] = yy[j-2];
01644             yy[j-2] = yy[j-3];
01645             yy[j-3] = yy[j-4];
01646          }
01647          for (; j > 0; j--) yy[j] = yy[j-1];
01648 
01649          yy[0] = tmp;
01650          GET_MTF_VAL(nextSym);
01651          continue;
01652       }
01653    }
01654 }

00599 {
00600    return ~globalCrc;
00601 }

00606 {
00607    return globalCrc;
00608 }

02582 {
02583    Int32     runLength;
02584    IntNative ch, chLatest;
02585 
02586    ch = getc ( src );
02587 
02588    /*--- Because I have no idea what kind of a value EOF is. ---*/
02589    if (ch == EOF) {
02590       ERROR_IF_NOT_ZERO ( ferror(src));
02591       return (1 << 16) | MY_EOF;
02592    }
02593 
02594    runLength = 0;
02595    do {
02596       chLatest = getc ( src );
02597       runLength++;
02598       bytesIn++;
02599    }
02600       while (ch == chLatest && runLength < 255);
02601 
02602    if ( chLatest != EOF ) {
02603       if ( ungetc ( chLatest, src ) == EOF )
02604          panic ( "getRLEpair: ungetc failed" );
02605    } else {
02606       ERROR_IF_NOT_ZERO ( ferror(src) );
02607    }
02608 
02609    /*--- Conditional is just a speedup hack. ---*/
02610    if (runLength == 1) {
02611       UPDATE_CRC ( globalCrc, (UChar)ch );
02612       return (1 << 16) | ch;
02613    } else {
02614       Int32 i;
02615       for (i = 1; i <= runLength; i++)
02616          UPDATE_CRC ( globalCrc, (UChar)ch );
02617       return (runLength << 16) | ch;
02618    }
02619 }

00903 {
00904    Int32 n, vec, i;
00905 
00906    vec = 0;
00907    for (n = minLen; n <= maxLen; n++) {
00908       for (i = 0; i < alphaSize; i++)
00909          if (length[i] == n) { code[i] = vec; vec++; };
00910       vec <<= 1;
00911    }
00912 }

00923 {
00924    Int32 pp, i, j, vec;
00925 
00926    pp = 0;
00927    for (i = minLen; i <= maxLen; i++)
00928       for (j = 0; j < alphaSize; j++)
00929          if (length[j] == i) { perm[pp] = j; pp++; };
00930 
00931    for (i = 0; i < MAX_CODE_LEN; i++) base[i] = 0;
00932    for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
00933 
00934    for (i = 1; i < MAX_CODE_LEN; i++) base[i] += base[i-1];
00935 
00936    for (i = 0; i < MAX_CODE_LEN; i++) limit[i] = 0;
00937    vec = 0;
00938 
00939    for (i = minLen; i <= maxLen; i++) {
00940       vec += (base[i+1] - base[i]);
00941       limit[i] = vec-1;
00942       vec <<= 1;
00943    }
00944    for (i = minLen + 1; i <= maxLen; i++)
00945       base[i] = ((limit[i-1] + 1) << 1) - base[i];
00946 }

00830 {
00831    /*--
00832       Nodes and heap entries run from 1.  Entry 0
00833       for both the heap and nodes is a sentinel.
00834    --*/
00835    Int32 nNodes, nHeap, n1, n2, i, j, k;
00836    Bool  tooLong;
00837 
00838    Int32 heap   [ MAX_ALPHA_SIZE + 2 ];
00839    Int32 weight [ MAX_ALPHA_SIZE * 2 ];
00840    Int32 parent [ MAX_ALPHA_SIZE * 2 ]; 
00841 
00842    for (i = 0; i < alphaSize; i++)
00843       weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
00844 
00845    while (True) {
00846 
00847       nNodes = alphaSize;
00848       nHeap = 0;
00849 
00850       heap[0] = 0;
00851       weight[0] = 0;
00852       parent[0] = -2;
00853 
00854       for (i = 1; i <= alphaSize; i++) {
00855          parent[i] = -1;
00856          nHeap++;
00857          heap[nHeap] = i;
00858          UPHEAP(nHeap);
00859       }
00860       if (!(nHeap < (MAX_ALPHA_SIZE+2))) 
00861          panic ( "hbMakeCodeLengths(1)" );
00862    
00863       while (nHeap > 1) {
00864          n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
00865          n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
00866          nNodes++;
00867          parent[n1] = parent[n2] = nNodes;
00868          weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
00869          parent[nNodes] = -1;
00870          nHeap++;
00871          heap[nHeap] = nNodes;
00872          UPHEAP(nHeap);
00873       }
00874       if (!(nNodes < (MAX_ALPHA_SIZE * 2)))
00875          panic ( "hbMakeCodeLengths(2)" );
00876 
00877       tooLong = False;
00878       for (i = 1; i <= alphaSize; i++) {
00879          j = 0;
00880          k = i;
00881          while (parent[k] >= 0) { k = parent[k]; j++; }
00882          len[i-1] = j;
00883          if (j > maxLen) tooLong = True;
00884       }
00885       
00886       if (! tooLong) break;
00887 
00888       for (i = 1; i < alphaSize; i++) {
00889          j = weight[i] >> 8;
00890          j = 1 + (j / 2);
00891          weight[i] = j << 8;
00892       }
00893    }
00894 }

02292 {
02293    Int32 nb, na, mid;
02294    nb = 0;
02295    na = 256;
02296    do {
02297       mid = (nb + na) >> 1;
02298       if (indx >= cftab[mid]) nb = mid; else na = mid;
02299    }
02300    while (na - nb != 1);
02301    return nb;
02302 }

00592 {
00593    globalCrc = 0xffffffffUL;
00594 }

03154 {
03155    fprintf ( stderr,
03156              "\n%s: I/O or other error, bailing out.  Possible reason follows.\n",
03157              progName );
03158    perror ( progName );
03159    showFileNames();
03160    cleanUpAndFail( 1 );
03161 }

03685 {
03686    fprintf ( stderr,
03687 
03688     "bzip2, a block-sorting file compressor.  "
03689     "Version 0.1pl2, 29-Aug-97.\n"
03690     "   \n"
03691     "   Copyright (C) 1996, 1997 by Julian Seward.\n"
03692     "   \n"
03693     "   This program is free software; you can redistribute it and/or modify\n"
03694     "   it under the terms of the GNU General Public License as published by\n"
03695     "   the Free Software Foundation; either version 2 of the License, or\n"
03696     "   (at your option) any later version.\n"
03697     "   \n"
03698     "   This program is distributed in the hope that it will be useful,\n"
03699     "   but WITHOUT ANY WARRANTY; without even the implied warranty of\n"
03700     "   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n"
03701     "   GNU General Public License for more details.\n"
03702     "   \n"
03703     "   You should have received a copy of the GNU General Public License\n"
03704     "   along with this program; if not, write to the Free Software\n"
03705     "   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.\n"
03706     "   \n"
03707     "   The GNU General Public License is contained in the file LICENSE.\n"
03708     "   \n"
03709    );
03710 }

02624 {
02625    Int32 ch, allowableBlockSize, i;
02626 
02627    last = -1;
02628    ch   = 0;
02629 
02630    for (i = 0; i < 256; i++) inUse[i] = False;
02631 
02632    /*--- 20 is just a paranoia constant ---*/
02633    allowableBlockSize = 100000 * blockSize100k - 20;
02634 
02635    while (last < allowableBlockSize && ch != MY_EOF) {
02636       Int32 rlePair, runLen;
02637       rlePair = getRLEpair ( src );
02638       ch      = rlePair & 0xFFFF;
02639       runLen  = (UInt32)rlePair >> 16;
02640 
02641       #if DEBUG
02642          assert (runLen >= 1 && runLen <= 255);
02643       #endif
02644 
02645       if (ch != MY_EOF) {
02646          inUse[ch] = True;
02647          switch (runLen) {
02648             case 1:
02649                last++; block[last] = (UChar)ch; break;
02650             case 2:
02651                last++; block[last] = (UChar)ch;
02652                last++; block[last] = (UChar)ch; break;
02653             case 3:
02654                last++; block[last] = (UChar)ch;
02655                last++; block[last] = (UChar)ch;
02656                last++; block[last] = (UChar)ch; break;
02657             default:
02658                inUse[runLen-4] = True;
02659                last++; block[last] = (UChar)ch;
02660                last++; block[last] = (UChar)ch;
02661                last++; block[last] = (UChar)ch;
02662                last++; block[last] = (UChar)ch;
02663                last++; block[last] = (UChar)(runLen-4); break;
02664          }
02665       }
02666    }
02667 }

03828 {
03829    Int32  i, j;
03830    Char   *tmp;
03831    Cell   *argList;
03832    Cell   *aa;
03833 
03834 
03835    #if DEBUG
03836       fprintf ( stderr, "bzip2: *** compiled with debugging ON ***\n" );
03837    #endif
03838 
03839    /*-- Be really really really paranoid :-) --*/
03840    if (sizeof(Int32) != 4 || sizeof(UInt32) != 4  ||
03841        sizeof(Int16) != 2 || sizeof(UInt16) != 2  ||
03842        sizeof(Char)  != 1 || sizeof(UChar)  != 1) {
03843       fprintf ( stderr,
03844                 "bzip2: I'm not configured correctly for this platform!\n"
03845                 "\tI require Int32, Int16 and Char to have sizes\n"
03846                 "\tof 4, 2 and 1 bytes to run properly, and they don't.\n"
03847                 "\tProbably you can fix this by defining them correctly,\n"
03848                 "\tand recompiling.  Bye!\n" );
03849       exit(1);
03850    }
03851 
03852 
03853    /*-- Set up signal handlers --*/
03854    signal (SIGINT,  mySignalCatcher);
03855    signal (SIGTERM, mySignalCatcher);
03856    signal (SIGSEGV, mySIGSEGVorSIGBUScatcher);
03857    #if BZ_UNIX
03858    signal (SIGHUP,  mySignalCatcher);
03859    signal (SIGBUS,  mySIGSEGVorSIGBUScatcher);
03860    #endif
03861 
03862 
03863    /*-- Initialise --*/
03864    outputHandleJustInCase  = NULL;
03865    ftab                    = NULL;
03866    ll4                     = NULL;
03867    ll16                    = NULL;
03868    ll8                     = NULL;
03869    tt                      = NULL;
03870    block                   = NULL;
03871    zptr                    = NULL;
03872    smallMode               = False;
03873    keepInputFiles          = False;
03874    verbosity               = 0;
03875    blockSize100k           = 9;
03876    testFailsExist          = False;
03877    bsStream                = NULL;
03878    numFileNames            = 0;
03879    numFilesProcessed       = 0;
03880    workFactor              = 30;
03881 
03882    strcpy ( inName,  "(none)" );
03883    strcpy ( outName, "(none)" );
03884 
03885    strcpy ( progNameReally, argv[0] );
03886    progName = &progNameReally[0];
03887    for (tmp = &progNameReally[0]; *tmp != '\0'; tmp++)
03888       if (*tmp == PATH_SEP) progName = tmp + 1;
03889 
03890 
03891    /*-- Expand filename wildcards in arg list --*/
03892    argList = NULL;
03893    for (i = 1; i <= argc-1; i++)
03894       APPEND_FILESPEC(argList, argv[i]);
03895 
03896 
03897    /*-- Find the length of the longest filename --*/
03898    longestFileName = 7;
03899    numFileNames    = 0;
03900    for (aa = argList; aa != NULL; aa = aa->link)
03901       if (aa->name[0] != '-') {
03902          numFileNames++;
03903          if (longestFileName < (Int32)strlen(aa->name) )
03904             longestFileName = (Int32)strlen(aa->name);
03905       }
03906 
03907 
03908    /*-- Determine what to do (compress/uncompress/test). --*/
03909    /*-- Note that subsequent flag handling may change this. --*/
03910    opMode = OM_Z;
03911 
03912    if ( (strcmp ( "bunzip2",     progName ) == 0) ||
03913         (strcmp ( "BUNZIP2",     progName ) == 0) ||
03914         (strcmp ( "bunzip2.exe", progName ) == 0) ||
03915         (strcmp ( "BUNZIP2.EXE", progName ) == 0) )
03916       opMode = OM_UNZ;
03917 
03918 
03919    /*-- Determine source modes; flag handling may change this too. --*/
03920    if (numFileNames == 0)
03921       srcMode = SM_I2O; else srcMode = SM_F2F;
03922 
03923 
03924    /*-- Look at the flags. --*/
03925    for (aa = argList; aa != NULL; aa = aa->link)
03926       if (aa->name[0] == '-' && aa->name[1] != '-')
03927          for (j = 1; aa->name[j] != '\0'; j++)
03928             switch (aa->name[j]) {
03929                case 'c': srcMode          = SM_F2O; break;
03930                case 'd': opMode           = OM_UNZ; break;
03931                case 'f': opMode           = OM_Z; break;
03932                case 't': opMode           = OM_TEST; break;
03933                case 'k': keepInputFiles   = True; break;
03934                case 's': smallMode        = True; break;
03935                case '1': blockSize100k    = 1; break;
03936                case '2': blockSize100k    = 2; break;
03937                case '3': blockSize100k    = 3; break;
03938                case '4': blockSize100k    = 4; break;
03939                case '5': blockSize100k    = 5; break;
03940                case '6': blockSize100k    = 6; break;
03941                case '7': blockSize100k    = 7; break;
03942                case '8': blockSize100k    = 8; break;
03943                case '9': blockSize100k    = 9; break;
03944                case 'V':
03945                case 'L': license();            break;
03946                case 'v': verbosity++; break;
03947                case 'h': usage ( progName );
03948                          exit ( 1 );
03949                          break;
03950                default:  fprintf ( stderr, "%s: Bad flag `%s'\n",
03951                                    progName, aa->name );
03952                          usage ( progName );
03953                          exit ( 1 );
03954                          break;
03955          }
03956 
03957    /*-- And again ... --*/
03958    for (aa = argList; aa != NULL; aa = aa->link) {
03959       if (ISFLAG("--stdout"))            srcMode          = SM_F2O;  else
03960       if (ISFLAG("--decompress"))        opMode           = OM_UNZ;  else
03961       if (ISFLAG("--compress"))          opMode           = OM_Z;    else
03962       if (ISFLAG("--test"))              opMode           = OM_TEST; else
03963       if (ISFLAG("--keep"))              keepInputFiles   = True;    else
03964       if (ISFLAG("--small"))             smallMode        = True;    else
03965       if (ISFLAG("--version"))           license();                  else
03966       if (ISFLAG("--license"))           license();                  else
03967       if (ISFLAG("--repetitive-fast"))   workFactor = 5;             else
03968       if (ISFLAG("--repetitive-best"))   workFactor = 150;           else
03969       if (ISFLAG("--verbose"))           verbosity++;                else
03970       if (ISFLAG("--help"))              { usage ( progName ); exit ( 1 ); }
03971          else
03972          if (strncmp ( aa->name, "--", 2) == 0) {
03973             fprintf ( stderr, "%s: Bad flag `%s'\n", progName, aa->name );
03974             usage ( progName );
03975             exit ( 1 );
03976          }
03977    }
03978 
03979    if (opMode == OM_Z && smallMode) blockSize100k = 2;
03980 
03981    if (opMode == OM_Z && srcMode == SM_F2O && numFileNames > 1) {
03982       fprintf ( stderr, "%s: I won't compress multiple files to stdout.\n",
03983                 progName );
03984       exit ( 1 );
03985    }
03986 
03987    if (srcMode == SM_F2O && numFileNames == 0) {
03988       fprintf ( stderr, "%s: -c expects at least one filename.\n",
03989                 progName );
03990       exit ( 1 );
03991    }
03992 
03993    if (opMode == OM_TEST && srcMode == SM_F2O) {
03994       fprintf ( stderr, "%s: -c and -t cannot be used together.\n",
03995                 progName );
03996       exit ( 1 );
03997    }
03998 
03999    if (opMode != OM_Z) blockSize100k = 0;
04000 
04001    if (opMode == OM_Z) {
04002       allocateCompressStructures();
04003       if (srcMode == SM_I2O)
04004          compress ( NULL );
04005          else
04006          for (aa = argList; aa != NULL; aa = aa->link)
04007             if (aa->name[0] != '-') {
04008                numFilesProcessed++;
04009                compress ( aa->name );
04010             }
04011    } else
04012    if (opMode == OM_UNZ) {
04013       if (srcMode == SM_I2O)
04014          uncompress ( NULL );
04015          else
04016          for (aa = argList; aa != NULL; aa = aa->link)
04017             if (aa->name[0] != '-') {
04018                numFilesProcessed++;
04019                uncompress ( aa->name );
04020             }
04021    } else {
04022       testFailsExist = False;
04023       if (srcMode == SM_I2O)
04024          testf ( NULL );
04025          else
04026          for (aa = argList; aa != NULL; aa = aa->link)
04027             if (aa->name[0] != '-') {
04028                numFilesProcessed++;
04029                testf ( aa->name );
04030             }
04031       if (testFailsExist) {
04032          fprintf ( stderr,
04033            "\n"
04034            "You can use the `bzip2recover' program to *attempt* to recover\n"
04035            "data from undamaged sections of corrupted files.\n\n"
04036          );
04037          exit(2);
04038       }
04039    }
04040    return 0;
04041 }

01083 {
01084    Int32 i;
01085    nInUse = 0;
01086    for (i = 0; i < 256; i++)
01087       if (inUse[i]) {
01088          seqToUnseq[nInUse] = i;
01089          unseqToSeq[i] = nInUse;
01090          nInUse++;
01091       }
01092 }

01856 {
01857    UChar t;
01858    if (a > b) { t = a; a = b; b = t; };
01859    if (b > c) { t = b; b = c; c = t; };
01860    if (a > b)          b = a;
01861    return b;
01862 }

03795 {
03796    Cell *c;
03797 
03798    c = (Cell*) myMalloc ( sizeof ( Cell ) );
03799    c->name = NULL;
03800    c->link = NULL;
03801    return c;
03802 }

01456 {
01457    bsPutIntVS ( 24, origPtr );
01458    generateMTFValues();
01459    sendMTFValues();
01460 }

03777 {
03778    void* p;
03779 
03780    p = malloc ( (size_t)n );
03781    if (p == NULL) {
03782       fprintf (
03783          stderr,
03784          "%s: `malloc' failed on request for %d bytes.\n",
03785          progName, n
03786       );
03787       exit ( 1 );
03788    }
03789    return p;
03790 }

03206 {
03207    fprintf ( stderr,
03208              "\n%s: Control-C (or similar) caught, quitting.\n",
03209              progName );
03210    cleanUpAndFail(1);
03211 }

03216 {
03217    if (opMode == OM_Z)
03218       fprintf ( stderr,
03219                 "\n%s: Caught a SIGSEGV or SIGBUS whilst compressing,\n"
03220                 "\twhich probably indicates a bug in bzip2.  Please\n"
03221                 "\treport it to me at: jseward@acm.org\n",
03222                 progName );
03223       else
03224       fprintf ( stderr,
03225                 "\n%s: Caught a SIGSEGV or SIGBUS whilst decompressing,\n"
03226                 "\twhich probably indicates that the compressed data\n"
03227                 "\tis corrupted.\n",
03228                 progName );
03229 
03230    showFileNames();
03231    if (opMode == OM_Z)
03232       cleanUpAndFail( 3 ); else
03233       { cadvise(); cleanUpAndFail( 2 ); }
03234 }

03293 {
03294    IntNative      i;
03295    struct MY_STAT statBuf;
03296 
03297    i = MY_LSTAT ( name, &statBuf );
03298    if (i != 0) return True;
03299    if (MY_S_IFREG(statBuf.st_mode)) return False;
03300    return True;
03301 }

03270 {
03271    Int32 i;
03272    if ( (Int32)strlen(s) >= longestFileName ) return;
03273    for (i = 1; i <= longestFileName - (Int32)strlen(s); i++)
03274       fprintf ( stderr, " " );
03275 }

03100 {
03101    fprintf ( stderr,
03102              "\n%s: PANIC -- internal consistency error:\n"
03103              "\t%s\n"
03104              "\tThis is a BUG.  Please report it to me at:\n"
03105              "\tjseward@acm.org\n",
03106              progName, s );
03107    showFileNames();
03108    cleanUpAndFail( 3 );
03109 }

01896 {
01897    Int32 unLo, unHi, ltLo, gtHi, med, n, m;
01898    Int32 sp, lo, hi, d;
01899    StackElem stack[QSORT_STACK_SIZE];
01900 
01901    sp = 0;
01902    push ( loSt, hiSt, dSt );
01903 
01904    while (sp > 0) {
01905 
01906       if (sp >= QSORT_STACK_SIZE) panic ( "stack overflow in qSort3" );
01907 
01908       pop ( lo, hi, d );
01909 
01910       if (hi - lo < SMALL_THRESH || d > DEPTH_THRESH) {
01911          simpleSort ( lo, hi, d );
01912          if (workDone > workLimit && firstAttempt) return;
01913          continue;
01914       }
01915 
01916       med = med3 ( block[zptr[ lo         ]+d],
01917                    block[zptr[ hi         ]+d],
01918                    block[zptr[ (lo+hi)>>1 ]+d] );
01919 
01920       unLo = ltLo = lo;
01921       unHi = gtHi = hi;
01922 
01923       while (True) {
01924          while (True) {
01925             if (unLo > unHi) break;
01926             n = ((Int32)block[zptr[unLo]+d]) - med;
01927             if (n == 0) { swap(zptr[unLo], zptr[ltLo]); ltLo++; unLo++; continue; };
01928             if (n >  0) break;
01929             unLo++;
01930          }
01931          while (True) {
01932             if (unLo > unHi) break;
01933             n = ((Int32)block[zptr[unHi]+d]) - med;
01934             if (n == 0) { swap(zptr[unHi], zptr[gtHi]); gtHi--; unHi--; continue; };
01935             if (n <  0) break;
01936             unHi--;
01937          }
01938          if (unLo > unHi) break;
01939          swap(zptr[unLo], zptr[unHi]); unLo++; unHi--;
01940       }
01941       #if DEBUG
01942          assert (unHi == unLo-1);
01943       #endif
01944 
01945       if (gtHi < ltLo) {
01946          push(lo, hi, d+1 );
01947          continue;
01948       }
01949 
01950       n = min(ltLo-lo, unLo-ltLo); vswap(lo, unLo-n, n);
01951       m = min(hi-gtHi, gtHi-unHi); vswap(unLo, hi-m+1, m);
01952 
01953       n = lo + unLo - ltLo - 1;
01954       m = hi - (gtHi - unHi) + 1;
01955 
01956       push ( lo, n, d );
01957       push ( n+1, m-1, d+1 );
01958       push ( m, hi, d );
01959    }
01960 }

02236 {
02237    Int32 i;
02238    RAND_DECLS;
02239    for (i = 0; i < 256; i++) inUse[i] = False;
02240 
02241    for (i = 0; i <= last; i++) {
02242       RAND_UPD_MASK;
02243       block[i] ^= RAND_MASK;
02244       inUse[block[i]] = True;
02245    }
02246 }

01465 {
01466    Int32 i, j, t, nGroups, nSelectors, alphaSize;
01467    Int32 minLen, maxLen;
01468    Bool inUse16[16];
01469 
01470    /*--- Receive the mapping table ---*/
01471    for (i = 0; i < 16; i++)
01472       if (bsR(1) == 1) 
01473          inUse16[i] = True; else 
01474          inUse16[i] = False;
01475 
01476    for (i = 0; i < 256; i++) inUse[i] = False;
01477 
01478    for (i = 0; i < 16; i++)
01479       if (inUse16[i])
01480          for (j = 0; j < 16; j++)
01481             if (bsR(1) == 1) inUse[i * 16 + j] = True;
01482 
01483    makeMaps();
01484    alphaSize = nInUse+2;
01485 
01486    /*--- Now the selectors ---*/
01487    nGroups = bsR ( 3 );
01488    nSelectors = bsR ( 15 );
01489    for (i = 0; i < nSelectors; i++) {
01490       j = 0;
01491       while (bsR(1) == 1) j++;
01492       selectorMtf[i] = j;
01493    }
01494 
01495    /*--- Undo the MTF values for the selectors. ---*/
01496    {
01497       UChar pos[N_GROUPS], tmp, v;
01498       for (v = 0; v < nGroups; v++) pos[v] = v;
01499    
01500       for (i = 0; i < nSelectors; i++) {
01501          v = selectorMtf[i];
01502          tmp = pos[v];
01503          while (v > 0) { pos[v] = pos[v-1]; v--; }
01504          pos[0] = tmp;
01505          selector[i] = tmp;
01506       }
01507    }
01508 
01509    /*--- Now the coding tables ---*/
01510    for (t = 0; t < nGroups; t++) {
01511       Int32 curr = bsR ( 5 );
01512       for (i = 0; i < alphaSize; i++) {
01513          while (bsR(1) == 1) {
01514             if (bsR(1) == 0) curr++; else curr--;
01515          }
01516          len[t][i] = curr;
01517       }
01518    }
01519 
01520    /*--- Create the Huffman decoding tables ---*/
01521    for (t = 0; t < nGroups; t++) {
01522       minLen = 32;
01523       maxLen = 0;
01524       for (i = 0; i < alphaSize; i++) {
01525          if (len[t][i] > maxLen) maxLen = len[t][i];
01526          if (len[t][i] < minLen) minLen = len[t][i];
01527       }
01528       hbCreateDecodeTables ( 
01529          &limit[t][0], &base[t][0], &perm[t][0], &len[t][0],
01530          minLen, maxLen, alphaSize
01531       );
01532       minLens[t] = minLen;
01533    }
01534 }

01180 {
01181    Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
01182    Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
01183    Int32 nGroups, nBytes;
01184 
01185    /*--
01186    UChar  len [N_GROUPS][MAX_ALPHA_SIZE];
01187    is a global since the decoder also needs it.
01188 
01189    Int32  code[N_GROUPS][MAX_ALPHA_SIZE];
01190    Int32  rfreq[N_GROUPS][MAX_ALPHA_SIZE];
01191    are also globals only used in this proc.
01192    Made global to keep stack frame size small.
01193    --*/
01194 
01195 
01196    UInt16 cost[N_GROUPS];
01197    Int32  fave[N_GROUPS];
01198 
01199    if (verbosity >= 3)
01200       fprintf ( stderr, 
01201                 "      %d in block, %d after MTF & 1-2 coding, %d+2 syms in use\n", 
01202                 last+1, nMTF, nInUse );
01203 
01204    alphaSize = nInUse+2;
01205    for (t = 0; t < N_GROUPS; t++)
01206       for (v = 0; v < alphaSize; v++)
01207          len[t][v] = GREATER_ICOST;
01208 
01209    /*--- Decide how many coding tables to use ---*/
01210    if (nMTF <= 0) panic ( "sendMTFValues(0)" );
01211    if (nMTF < 200) nGroups = 2; else
01212    if (nMTF < 800) nGroups = 4; else
01213                    nGroups = 6;
01214 
01215    /*--- Generate an initial set of coding tables ---*/
01216    { 
01217       Int32 nPart, remF, tFreq, aFreq;
01218 
01219       nPart = nGroups;
01220       remF  = nMTF;
01221       gs = 0;
01222       while (nPart > 0) {
01223          tFreq = remF / nPart;
01224          ge = gs-1;
01225          aFreq = 0;
01226          while (aFreq < tFreq && ge < alphaSize-1) {
01227             ge++;
01228             aFreq += mtfFreq[ge];
01229          }
01230 
01231          if (ge > gs 
01232              && nPart != nGroups && nPart != 1 
01233              && ((nGroups-nPart) % 2 == 1)) {
01234             aFreq -= mtfFreq[ge];
01235             ge--;
01236          }
01237 
01238          if (verbosity >= 3)
01239             fprintf ( stderr, 
01240                       "      initial group %d, [%d .. %d], has %d syms (%4.1f%%)\n",
01241                               nPart, gs, ge, aFreq, 
01242                               (100.0 * (float)aFreq) / (float)nMTF );
01243  
01244          for (v = 0; v < alphaSize; v++)
01245             if (v >= gs && v <= ge) 
01246                len[nPart-1][v] = LESSER_ICOST; else
01247                len[nPart-1][v] = GREATER_ICOST;
01248  
01249          nPart--;
01250          gs = ge+1;
01251          remF -= aFreq;
01252       }
01253    }
01254 
01255    /*--- 
01256       Iterate up to N_ITERS times to improve the tables.
01257    ---*/
01258    for (iter = 0; iter < N_ITERS; iter++) {
01259 
01260       for (t = 0; t < nGroups; t++) fave[t] = 0;
01261 
01262       for (t = 0; t < nGroups; t++)
01263          for (v = 0; v < alphaSize; v++)
01264             rfreq[t][v] = 0;
01265 
01266       nSelectors = 0;
01267       totc = 0;
01268       gs = 0;
01269       while (True) {
01270 
01271          /*--- Set group start & end marks. --*/
01272          if (gs >= nMTF) break;
01273          ge = gs + G_SIZE - 1; 
01274          if (ge >= nMTF) ge = nMTF-1;
01275 
01276          /*-- 
01277             Calculate the cost of this group as coded
01278             by each of the coding tables.
01279          --*/
01280          for (t = 0; t < nGroups; t++) cost[t] = 0;
01281 
01282          if (nGroups == 6) {
01283             register UInt16 cost0, cost1, cost2, cost3, cost4, cost5;
01284             cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0;
01285             for (i = gs; i <= ge; i++) { 
01286                UInt16 icv = szptr[i];
01287                cost0 += len[0][icv];
01288                cost1 += len[1][icv];
01289                cost2 += len[2][icv];
01290                cost3 += len[3][icv];
01291                cost4 += len[4][icv];
01292                cost5 += len[5][icv];
01293             }
01294             cost[0] = cost0; cost[1] = cost1; cost[2] = cost2;
01295             cost[3] = cost3; cost[4] = cost4; cost[5] = cost5;
01296          } else {
01297             for (i = gs; i <= ge; i++) { 
01298                UInt16 icv = szptr[i];
01299                for (t = 0; t < nGroups; t++) cost[t] += len[t][icv];
01300             }
01301          }
01302  
01303          /*-- 
01304             Find the coding table which is best for this group,
01305             and record its identity in the selector table.
01306          --*/
01307          bc = 999999999; bt = -1;
01308          for (t = 0; t < nGroups; t++)
01309             if (cost[t] < bc) { bc = cost[t]; bt = t; };
01310          totc += bc;
01311          fave[bt]++;
01312          selector[nSelectors] = bt;
01313          nSelectors++;
01314 
01315          /*-- 
01316             Increment the symbol frequencies for the selected table.
01317           --*/
01318          for (i = gs; i <= ge; i++)
01319             rfreq[bt][ szptr[i] ]++;
01320 
01321          gs = ge+1;
01322       }
01323       if (verbosity >= 3) {
01324          fprintf ( stderr, 
01325                    "      pass %d: size is %d, grp uses are ", 
01326                    iter+1, totc/8 );
01327          for (t = 0; t < nGroups; t++)
01328             fprintf ( stderr, "%d ", fave[t] );
01329          fprintf ( stderr, "\n" );
01330       }
01331 
01332       /*--
01333         Recompute the tables based on the accumulated frequencies.
01334       --*/
01335       for (t = 0; t < nGroups; t++)
01336          hbMakeCodeLengths ( &len[t][0], &rfreq[t][0], alphaSize, 20 );
01337    }
01338 
01339 
01340    if (!(nGroups < 8)) panic ( "sendMTFValues(1)" );
01341    if (!(nSelectors < 32768 &&
01342          nSelectors <= (2 + (900000 / G_SIZE))))
01343                        panic ( "sendMTFValues(2)" );
01344 
01345 
01346    /*--- Compute MTF values for the selectors. ---*/
01347    {
01348       UChar pos[N_GROUPS], ll_i, tmp2, tmp;
01349       for (i = 0; i < nGroups; i++) pos[i] = i;
01350       for (i = 0; i < nSelectors; i++) {
01351          ll_i = selector[i];
01352          j = 0;
01353          tmp = pos[j];
01354          while ( ll_i != tmp ) {
01355             j++;
01356             tmp2 = tmp;
01357             tmp = pos[j];
01358             pos[j] = tmp2;
01359          };
01360          pos[0] = tmp;
01361          selectorMtf[i] = j;
01362       }
01363    };
01364 
01365    /*--- Assign actual codes for the tables. --*/
01366    for (t = 0; t < nGroups; t++) {
01367       minLen = 32;
01368       maxLen = 0;
01369       for (i = 0; i < alphaSize; i++) {
01370          if (len[t][i] > maxLen) maxLen = len[t][i];
01371          if (len[t][i] < minLen) minLen = len[t][i];
01372       }
01373       if (maxLen > 20) panic ( "sendMTFValues(3)" );
01374       if (minLen < 1)  panic ( "sendMTFValues(4)" );
01375       hbAssignCodes ( &code[t][0], &len[t][0], 
01376                       minLen, maxLen, alphaSize );
01377    }
01378 
01379    /*--- Transmit the mapping table. ---*/
01380    { 
01381       Bool inUse16[16];
01382       for (i = 0; i < 16; i++) {
01383           inUse16[i] = False;
01384           for (j = 0; j < 16; j++)
01385              if (inUse[i * 16 + j]) inUse16[i] = True;
01386       }
01387      
01388       nBytes = bytesOut;
01389       for (i = 0; i < 16; i++)
01390          if (inUse16[i]) bsW(1,1); else bsW(1,0);
01391 
01392       for (i = 0; i < 16; i++)
01393          if (inUse16[i])
01394             for (j = 0; j < 16; j++)
01395                if (inUse[i * 16 + j]) bsW(1,1); else bsW(1,0);
01396 
01397       if (verbosity >= 3) 
01398          fprintf ( stderr, "      bytes: mapping %d, ", bytesOut-nBytes );
01399    }
01400 
01401    /*--- Now the selectors. ---*/
01402    nBytes = bytesOut;
01403    bsW ( 3, nGroups );
01404    bsW ( 15, nSelectors );
01405    for (i = 0; i < nSelectors; i++) { 
01406       for (j = 0; j < selectorMtf[i]; j++) bsW(1,1);
01407       bsW(1,0);
01408    }
01409    if (verbosity >= 3)
01410       fprintf ( stderr, "selectors %d, ", bytesOut-nBytes );
01411 
01412    /*--- Now the coding tables. ---*/
01413    nBytes = bytesOut;
01414 
01415    for (t = 0; t < nGroups; t++) {
01416       Int32 curr = len[t][0];
01417       bsW ( 5, curr );
01418       for (i = 0; i < alphaSize; i++) {
01419          while (curr < len[t][i]) { bsW(2,2); curr++; /* 10 */ };
01420          while (curr > len[t][i]) { bsW(2,3); curr--; /* 11 */ };
01421          bsW ( 1, 0 );
01422       }
01423    }
01424 
01425    if (verbosity >= 3)
01426       fprintf ( stderr, "code lengths %d, ", bytesOut-nBytes );
01427 
01428    /*--- And finally, the block data proper ---*/
01429    nBytes = bytesOut;
01430    selCtr = 0;
01431    gs = 0;
01432    while (True) {
01433       if (gs >= nMTF) break;
01434       ge = gs + G_SIZE - 1; 
01435       if (ge >= nMTF) ge = nMTF-1;
01436       for (i = gs; i <= ge; i++) { 
01437          #if DEBUG
01438             assert (selector[selCtr] < nGroups);
01439          #endif
01440          bsW ( len  [selector[selCtr]] [szptr[i]],
01441                code [selector[selCtr]] [szptr[i]] );
01442       }
01443 
01444       gs = ge+1;
01445       selCtr++;
01446    }
01447    if (!(selCtr == nSelectors)) panic ( "sendMTFValues(5)" );
01448 
01449    if (verbosity >= 3)
01450       fprintf ( stderr, "codes %d\n", bytesOut-nBytes );
01451 }

01032 {
01033    if (! (0 <= newSize100k   && newSize100k   <= 9 &&
01034           0 <= blockSize100k && blockSize100k <= 9))
01035       panic ( "setDecompressStructureSizes" );
01036 
01037    if (newSize100k == blockSize100k) return;
01038 
01039    blockSize100k = newSize100k;
01040 
01041    if (ll16  != NULL) free ( ll16  );
01042    if (ll4   != NULL) free ( ll4   );
01043    if (ll8   != NULL) free ( ll8   );
01044    if (tt    != NULL) free ( tt    );
01045 
01046    if (newSize100k == 0) return;
01047 
01048    if (smallMode) {
01049 
01050       Int32 n = 100000 * newSize100k;
01051       ll16    = malloc ( n * sizeof(UInt16) );
01052       ll4     = malloc ( ((n+1) >> 1) * sizeof(UChar) );
01053 
01054       if (ll4 == NULL || ll16 == NULL) {
01055          Int32 totalDraw
01056             = n * sizeof(Int16) + ((n+1) >> 1) * sizeof(UChar);
01057          uncompressOutOfMemory ( totalDraw, n );
01058       }
01059 
01060    } else {
01061 
01062       Int32 n = 100000 * newSize100k;
01063       ll8     = malloc ( n * sizeof(UChar) );
01064       tt      = malloc ( n * sizeof(Int32) );
01065 
01066       if (ll8 == NULL || tt == NULL) {
01067          Int32 totalDraw
01068             = n * sizeof(UChar) + n * sizeof(UInt32);
01069          uncompressOutOfMemory ( totalDraw, n );
01070       }
01071 
01072    }
01073 }