contrib/bzip2/compress.c

   1
   2 /*-------------------------------------------------------------*/
   3 /*--- Compression machinery (not incl block sorting)        ---*/
   4 /*---                                            compress.c ---*/
   5 /*-------------------------------------------------------------*/
   6
   7 /*--
   8   This file is a part of bzip2 and/or libbzip2, a program and
   9   library for lossless, block-sorting data compression.
  10
  11   Copyright (C) 1996-2002 Julian R Seward.  All rights reserved.
  12
  13   Redistribution and use in source and binary forms, with or without
  14   modification, are permitted provided that the following conditions
  15   are met:
  16
  17   1. Redistributions of source code must retain the above copyright
  18      notice, this list of conditions and the following disclaimer.
  19
  20   2. The origin of this software must not be misrepresented; you must
  21      not claim that you wrote the original software.  If you use this
  22      software in a product, an acknowledgment in the product
  23      documentation would be appreciated but is not required.
  24
  25   3. Altered source versions must be plainly marked as such, and must
  26      not be misrepresented as being the original software.
  27
  28   4. The name of the author may not be used to endorse or promote
  29      products derived from this software without specific prior written
  30      permission.
  31
  32   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
  33   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  34   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  35   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  36   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  37   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  38   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  39   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  40   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  41   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  42   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  43
  44   Julian Seward, Cambridge, UK.
  45   jseward@acm.org
  46   bzip2/libbzip2 version 1.0 of 21 March 2000
  47
  48   This program is based on (at least) the work of:
  49      Mike Burrows
  50      David Wheeler
  51      Peter Fenwick
  52      Alistair Moffat
  53      Radford Neal
  54      Ian H. Witten
  55      Robert Sedgewick
  56      Jon L. Bentley
  57
  58   For more information on these sources, see the manual.
  59 --*/
  60
  61 /*--
  62    CHANGES
  63    ~~~~~~~
  64    0.9.0 -- original version.
  65
  66    0.9.0a/b -- no changes in this file.
  67
  68    0.9.0c
  69       * changed setting of nGroups in sendMTFValues() so as to
  70         do a bit better on small files
  71 --*/
  72
  73 #include "bzlib_private.h"
  74
  75
  76 /*---------------------------------------------------*/
  77 /*--- Bit stream I/O                              ---*/
  78 /*---------------------------------------------------*/
  79
  80 /*---------------------------------------------------*/
  81 void BZ2_bsInitWrite ( EState* s )
  82 {
  83    s->bsLive = 0;
  84    s->bsBuff = 0;
  85 }
  86
  87
  88 /*---------------------------------------------------*/
  89 static
  90 void bsFinishWrite ( EState* s )
  91 {
  92    while (s->bsLive > 0) {
  93       s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
  94       s->numZ++;
  95       s->bsBuff <<= 8;
  96       s->bsLive -= 8;
  97    }
  98 }
  99
 100
 101 /*---------------------------------------------------*/
 102 #define bsNEEDW(nz)                           \
 103 {                                             \
 104    while (s->bsLive >= 8) {                   \
 105       s->zbits[s->numZ]                       \
 106          = (UChar)(s->bsBuff >> 24);          \
 107       s->numZ++;                              \
 108       s->bsBuff <<= 8;                        \
 109       s->bsLive -= 8;                         \
 110    }                                          \
 111 }
 112
 113
 114 /*---------------------------------------------------*/
 115 static
 116 __inline__
 117 void bsW ( EState* s, Int32 n, UInt32 v )
 118 {
 119    bsNEEDW ( n );
 120    s->bsBuff |= (v << (32 - s->bsLive - n));
 121    s->bsLive += n;
 122 }
 123
 124
 125 /*---------------------------------------------------*/
 126 static
 127 void bsPutUInt32 ( EState* s, UInt32 u )
 128 {
 129    bsW ( s, 8, (u >> 24) & 0xffL );
 130    bsW ( s, 8, (u >> 16) & 0xffL );
 131    bsW ( s, 8, (u >>  8) & 0xffL );
 132    bsW ( s, 8,  u        & 0xffL );
 133 }
 134
 135
 136 /*---------------------------------------------------*/
 137 static
 138 void bsPutUChar ( EState* s, UChar c )
 139 {
 140    bsW( s, 8, (UInt32)c );
 141 }
 142
 143
 144 /*---------------------------------------------------*/
 145 /*--- The back end proper                         ---*/
 146 /*---------------------------------------------------*/
 147
 148 /*---------------------------------------------------*/
 149 static
 150 void makeMaps_e ( EState* s )
 151 {
 152    Int32 i;
 153    s->nInUse = 0;
 154    for (i = 0; i < 256; i++)
 155       if (s->inUse[i]) {
 156          s->unseqToSeq[i] = s->nInUse;
 157          s->nInUse++;
 158       }
 159 }
 160
 161
 162 /*---------------------------------------------------*/
 163 static
 164 void generateMTFValues ( EState* s )
 165 {
 166    UChar   yy[256];
 167    Int32   i, j;
 168    Int32   zPend;
 169    Int32   wr;
 170    Int32   EOB;
 171
 172    /*
 173       After sorting (eg, here),
 174          s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
 175          and
 176          ((UChar*)s->arr2) [ 0 .. s->nblock-1 ]
 177          holds the original block data.
 178
 179       The first thing to do is generate the MTF values,
 180       and put them in
 181          ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
 182       Because there are strictly fewer or equal MTF values
 183       than block values, ptr values in this area are overwritten
 184       with MTF values only when they are no longer needed.
 185
 186       The final compressed bitstream is generated into the
 187       area starting at
 188          (UChar*) (&((UChar*)s->arr2)[s->nblock])
 189
 190       These storage aliases are set up in bzCompressInit(),
 191       except for the last one, which is arranged in
 192       compressBlock().
 193    */
 194    UInt32* ptr   = s->ptr;
 195    UChar* block  = s->block;
 196    UInt16* mtfv  = s->mtfv;
 197
 198    makeMaps_e ( s );
 199    EOB = s->nInUse+1;
 200
 201    for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
 202
 203    wr = 0;
 204    zPend = 0;
 205    for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
 206
 207    for (i = 0; i < s->nblock; i++) {
 208       UChar ll_i;
 209       AssertD ( wr <= i, "generateMTFValues(1)" );
 210       j = ptr[i]-1; if (j < 0) j += s->nblock;
 211       ll_i = s->unseqToSeq[block[j]];
 212       AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
 213
 214       if (yy[0] == ll_i) {
 215          zPend++;
 216       } else {
 217
 218          if (zPend > 0) {
 219             zPend--;
 220             while (True) {
 221                if (zPend & 1) {
 222                   mtfv[wr] = BZ_RUNB; wr++;
 223                   s->mtfFreq[BZ_RUNB]++;
 224                } else {
 225                   mtfv[wr] = BZ_RUNA; wr++;
 226                   s->mtfFreq[BZ_RUNA]++;
 227                }
 228                if (zPend < 2) break;
 229                zPend = (zPend - 2) / 2;
 230             };
 231             zPend = 0;
 232          }
 233          {
 234             register UChar  rtmp;
 235             register UChar* ryy_j;
 236             register UChar  rll_i;
 237             rtmp  = yy[1];
 238             yy[1] = yy[0];
 239             ryy_j = &(yy[1]);
 240             rll_i = ll_i;
 241             while ( rll_i != rtmp ) {
 242                register UChar rtmp2;
 243                ryy_j++;
 244                rtmp2  = rtmp;
 245                rtmp   = *ryy_j;
 246                *ryy_j = rtmp2;
 247             };
 248             yy[0] = rtmp;
 249             j = ryy_j - &(yy[0]);
 250             mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
 251          }
 252
 253       }
 254    }
 255
 256    if (zPend > 0) {
 257       zPend--;
 258       while (True) {
 259          if (zPend & 1) {
 260             mtfv[wr] = BZ_RUNB; wr++;
 261             s->mtfFreq[BZ_RUNB]++;
 262          } else {
 263             mtfv[wr] = BZ_RUNA; wr++;
 264             s->mtfFreq[BZ_RUNA]++;
 265          }
 266          if (zPend < 2) break;
 267          zPend = (zPend - 2) / 2;
 268       };
 269       zPend = 0;
 270    }
 271
 272    mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
 273
 274    s->nMTF = wr;
 275 }
 276
 277
 278 /*---------------------------------------------------*/
 279 #define BZ_LESSER_ICOST  0
 280 #define BZ_GREATER_ICOST 15
 281
 282 static
 283 void sendMTFValues ( EState* s )
 284 {
 285    Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
 286    Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
 287    Int32 nGroups, nBytes;
 288
 289    /*--
 290    UChar  len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 291    is a global since the decoder also needs it.
 292
 293    Int32  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 294    Int32  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 295    are also globals only used in this proc.
 296    Made global to keep stack frame size small.
 297    --*/
 298
 299
 300    UInt16 cost[BZ_N_GROUPS];
 301    Int32  fave[BZ_N_GROUPS];
 302
 303    UInt16* mtfv = s->mtfv;
 304
 305    if (s->verbosity >= 3)
 306       VPrintf3( "      %d in block, %d after MTF & 1-2 coding, "
 307                 "%d+2 syms in use\n",
 308                 s->nblock, s->nMTF, s->nInUse );
 309
 310    alphaSize = s->nInUse+2;
 311    for (t = 0; t < BZ_N_GROUPS; t++)
 312       for (v = 0; v < alphaSize; v++)
 313          s->len[t][v] = BZ_GREATER_ICOST;
 314
 315    /*--- Decide how many coding tables to use ---*/
 316    AssertH ( s->nMTF > 0, 3001 );
 317    if (s->nMTF < 200)  nGroups = 2; else
 318    if (s->nMTF < 600)  nGroups = 3; else
 319    if (s->nMTF < 1200) nGroups = 4; else
 320    if (s->nMTF < 2400) nGroups = 5; else
 321                        nGroups = 6;
 322
 323    /*--- Generate an initial set of coding tables ---*/
 324    {
 325       Int32 nPart, remF, tFreq, aFreq;
 326
 327       nPart = nGroups;
 328       remF  = s->nMTF;
 329       gs = 0;
 330       while (nPart > 0) {
 331          tFreq = remF / nPart;
 332          ge = gs-1;
 333          aFreq = 0;
 334          while (aFreq < tFreq && ge < alphaSize-1) {
 335             ge++;
 336             aFreq += s->mtfFreq[ge];
 337          }
 338
 339          if (ge > gs
 340              && nPart != nGroups && nPart != 1
 341              && ((nGroups-nPart) % 2 == 1)) {
 342             aFreq -= s->mtfFreq[ge];
 343             ge--;
 344          }
 345
 346          if (s->verbosity >= 3)
 347             VPrintf5( "      initial group %d, [%d .. %d], "
 348                       "has %d syms (%4.1f%%)\n",
 349                       nPart, gs, ge, aFreq,
 350                       (100.0 * (float)aFreq) / (float)(s->nMTF) );
 351
 352          for (v = 0; v < alphaSize; v++)
 353             if (v >= gs && v <= ge)
 354                s->len[nPart-1][v] = BZ_LESSER_ICOST; else
 355                s->len[nPart-1][v] = BZ_GREATER_ICOST;
 356
 357          nPart--;
 358          gs = ge+1;
 359          remF -= aFreq;
 360       }
 361    }
 362
 363    /*---
 364       Iterate up to BZ_N_ITERS times to improve the tables.
 365    ---*/
 366    for (iter = 0; iter < BZ_N_ITERS; iter++) {
 367
 368       for (t = 0; t < nGroups; t++) fave[t] = 0;
 369
 370       for (t = 0; t < nGroups; t++)
 371          for (v = 0; v < alphaSize; v++)
 372             s->rfreq[t][v] = 0;
 373
 374       /*---
 375         Set up an auxiliary length table which is used to fast-track
 376         the common case (nGroups == 6).
 377       ---*/
 378       if (nGroups == 6) {
 379          for (v = 0; v < alphaSize; v++) {
 380             s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
 381             s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
 382             s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
 383          }
 384       }
 385
 386       nSelectors = 0;
 387       totc = 0;
 388       gs = 0;
 389       while (True) {
 390
 391          /*--- Set group start & end marks. --*/
 392          if (gs >= s->nMTF) break;
 393          ge = gs + BZ_G_SIZE - 1;
 394          if (ge >= s->nMTF) ge = s->nMTF-1;
 395
 396          /*--
 397             Calculate the cost of this group as coded
 398             by each of the coding tables.
 399          --*/
 400          for (t = 0; t < nGroups; t++) cost[t] = 0;
 401
 402          if (nGroups == 6 && 50 == ge-gs+1) {
 403             /*--- fast track the common case ---*/
 404             register UInt32 cost01, cost23, cost45;
 405             register UInt16 icv;
 406             cost01 = cost23 = cost45 = 0;
 407
 408 #           define BZ_ITER(nn)                \
 409                icv = mtfv[gs+(nn)];           \
 410                cost01 += s->len_pack[icv][0]; \
 411                cost23 += s->len_pack[icv][1]; \
 412                cost45 += s->len_pack[icv][2]; \
 413
 414             BZ_ITER(0);  BZ_ITER(1);  BZ_ITER(2);  BZ_ITER(3);  BZ_ITER(4);
 415             BZ_ITER(5);  BZ_ITER(6);  BZ_ITER(7);  BZ_ITER(8);  BZ_ITER(9);
 416             BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
 417             BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
 418             BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
 419             BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
 420             BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
 421             BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
 422             BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
 423             BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
 424
 425 #           undef BZ_ITER
 426
 427             cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
 428             cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
 429             cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
 430
 431          } else {
 432             /*--- slow version which correctly handles all situations ---*/
 433             for (i = gs; i <= ge; i++) {
 434                UInt16 icv = mtfv[i];
 435                for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
 436             }
 437          }
 438
 439          /*--
 440             Find the coding table which is best for this group,
 441             and record its identity in the selector table.
 442          --*/
 443          bc = 999999999; bt = -1;
 444          for (t = 0; t < nGroups; t++)
 445             if (cost[t] < bc) { bc = cost[t]; bt = t; };
 446          totc += bc;
 447          fave[bt]++;
 448          s->selector[nSelectors] = bt;
 449          nSelectors++;
 450
 451          /*--
 452             Increment the symbol frequencies for the selected table.
 453           --*/
 454          if (nGroups == 6 && 50 == ge-gs+1) {
 455             /*--- fast track the common case ---*/
 456
 457 #           define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
 458
 459             BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
 460             BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
 461             BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
 462             BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
 463             BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
 464             BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
 465             BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
 466             BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
 467             BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
 468             BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
 469
 470 #           undef BZ_ITUR
 471
 472          } else {
 473             /*--- slow version which correctly handles all situations ---*/
 474             for (i = gs; i <= ge; i++)
 475                s->rfreq[bt][ mtfv[i] ]++;
 476          }
 477
 478          gs = ge+1;
 479       }
 480       if (s->verbosity >= 3) {
 481          VPrintf2 ( "      pass %d: size is %d, grp uses are ",
 482                    iter+1, totc/8 );
 483          for (t = 0; t < nGroups; t++)
 484             VPrintf1 ( "%d ", fave[t] );
 485          VPrintf0 ( "\n" );
 486       }
 487
 488       /*--
 489         Recompute the tables based on the accumulated frequencies.
 490       --*/
 491       for (t = 0; t < nGroups; t++)
 492          BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
 493                                  alphaSize, 20 );
 494    }
 495
 496
 497    AssertH( nGroups < 8, 3002 );
 498    AssertH( nSelectors < 32768 &&
 499             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
 500             3003 );
 501
 502
 503    /*--- Compute MTF values for the selectors. ---*/
 504    {
 505       UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
 506       for (i = 0; i < nGroups; i++) pos[i] = i;
 507       for (i = 0; i < nSelectors; i++) {
 508          ll_i = s->selector[i];
 509          j = 0;
 510          tmp = pos[j];
 511          while ( ll_i != tmp ) {
 512             j++;
 513             tmp2 = tmp;
 514             tmp = pos[j];
 515             pos[j] = tmp2;
 516          };
 517          pos[0] = tmp;
 518          s->selectorMtf[i] = j;
 519       }
 520    };
 521
 522    /*--- Assign actual codes for the tables. --*/
 523    for (t = 0; t < nGroups; t++) {
 524       minLen = 32;
 525       maxLen = 0;
 526       for (i = 0; i < alphaSize; i++) {
 527          if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
 528          if (s->len[t][i] < minLen) minLen = s->len[t][i];
 529       }
 530       AssertH ( !(maxLen > 20), 3004 );
 531       AssertH ( !(minLen < 1),  3005 );
 532       BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
 533                           minLen, maxLen, alphaSize );
 534    }
 535
 536    /*--- Transmit the mapping table. ---*/
 537    {
 538       Bool inUse16[16];
 539       for (i = 0; i < 16; i++) {
 540           inUse16[i] = False;
 541           for (j = 0; j < 16; j++)
 542              if (s->inUse[i * 16 + j]) inUse16[i] = True;
 543       }
 544
 545       nBytes = s->numZ;
 546       for (i = 0; i < 16; i++)
 547          if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
 548
 549       for (i = 0; i < 16; i++)
 550          if (inUse16[i])
 551             for (j = 0; j < 16; j++) {
 552                if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
 553             }
 554
 555       if (s->verbosity >= 3)
 556          VPrintf1( "      bytes: mapping %d, ", s->numZ-nBytes );
 557    }
 558
 559    /*--- Now the selectors. ---*/
 560    nBytes = s->numZ;
 561    bsW ( s, 3, nGroups );
 562    bsW ( s, 15, nSelectors );
 563    for (i = 0; i < nSelectors; i++) {
 564       for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
 565       bsW(s,1,0);
 566    }
 567    if (s->verbosity >= 3)
 568       VPrintf1( "selectors %d, ", s->numZ-nBytes );
 569
 570    /*--- Now the coding tables. ---*/
 571    nBytes = s->numZ;
 572
 573    for (t = 0; t < nGroups; t++) {
 574       Int32 curr = s->len[t][0];
 575       bsW ( s, 5, curr );
 576       for (i = 0; i < alphaSize; i++) {
 577          while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
 578          while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
 579          bsW ( s, 1, 0 );
 580       }
 581    }
 582
 583    if (s->verbosity >= 3)
 584       VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
 585
 586    /*--- And finally, the block data proper ---*/
 587    nBytes = s->numZ;
 588    selCtr = 0;
 589    gs = 0;
 590    while (True) {
 591       if (gs >= s->nMTF) break;
 592       ge = gs + BZ_G_SIZE - 1;
 593       if (ge >= s->nMTF) ge = s->nMTF-1;
 594       AssertH ( s->selector[selCtr] < nGroups, 3006 );
 595
 596       if (nGroups == 6 && 50 == ge-gs+1) {
 597             /*--- fast track the common case ---*/
 598             UInt16 mtfv_i;
 599             UChar* s_len_sel_selCtr
 600                = &(s->len[s->selector[selCtr]][0]);
 601             Int32* s_code_sel_selCtr
 602                = &(s->code[s->selector[selCtr]][0]);
 603
 604 #           define BZ_ITAH(nn)                      \
 605                mtfv_i = mtfv[gs+(nn)];              \
 606                bsW ( s,                             \
 607                      s_len_sel_selCtr[mtfv_i],      \
 608                      s_code_sel_selCtr[mtfv_i] )
 609
 610             BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
 611             BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
 612             BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
 613             BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
 614             BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
 615             BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
 616             BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
 617             BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
 618             BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
 619             BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
 620
 621 #           undef BZ_ITAH
 622
 623       } else {
 624          /*--- slow version which correctly handles all situations ---*/
 625          for (i = gs; i <= ge; i++) {
 626             bsW ( s,
 627                   s->len  [s->selector[selCtr]] [mtfv[i]],
 628                   s->code [s->selector[selCtr]] [mtfv[i]] );
 629          }
 630       }
 631
 632
 633       gs = ge+1;
 634       selCtr++;
 635    }
 636    AssertH( selCtr == nSelectors, 3007 );
 637
 638    if (s->verbosity >= 3)
 639       VPrintf1( "codes %d\n", s->numZ-nBytes );
 640 }
 641
 642
 643 /*---------------------------------------------------*/
 644 void BZ2_compressBlock ( EState* s, Bool is_last_block )
 645 {
 646    if (s->nblock > 0) {
 647
 648       BZ_FINALISE_CRC ( s->blockCRC );
 649       s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
 650       s->combinedCRC ^= s->blockCRC;
 651       if (s->blockNo > 1) s->numZ = 0;
 652
 653       if (s->verbosity >= 2)
 654          VPrintf4( "    block %d: crc = 0x%8x, "
 655                    "combined CRC = 0x%8x, size = %d\n",
 656                    s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
 657
 658       BZ2_blockSort ( s );
 659    }
 660
 661    s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
 662
 663    /*-- If this is the first block, create the stream header. --*/
 664    if (s->blockNo == 1) {
 665       BZ2_bsInitWrite ( s );
 666       bsPutUChar ( s, BZ_HDR_B );
 667       bsPutUChar ( s, BZ_HDR_Z );
 668       bsPutUChar ( s, BZ_HDR_h );
 669       bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
 670    }
 671
 672    if (s->nblock > 0) {
 673
 674       bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
 675       bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
 676       bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
 677
 678       /*-- Now the block's CRC, so it is in a known place. --*/
 679       bsPutUInt32 ( s, s->blockCRC );
 680
 681       /*--
 682          Now a single bit indicating (non-)randomisation.
 683          As of version 0.9.5, we use a better sorting algorithm
 684          which makes randomisation unnecessary.  So always set
 685          the randomised bit to 'no'.  Of course, the decoder
 686          still needs to be able to handle randomised blocks
 687          so as to maintain backwards compatibility with
 688          older versions of bzip2.
 689       --*/
 690       bsW(s,1,0);
 691
 692       bsW ( s, 24, s->origPtr );
 693       generateMTFValues ( s );
 694       sendMTFValues ( s );
 695    }
 696
 697
 698    /*-- If this is the last block, add the stream trailer. --*/
 699    if (is_last_block) {
 700
 701       bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
 702       bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
 703       bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
 704       bsPutUInt32 ( s, s->combinedCRC );
 705       if (s->verbosity >= 2)
 706          VPrintf1( "    final combined CRC = 0x%x\n   ", s->combinedCRC );
 707       bsFinishWrite ( s );
 708    }
 709 }
 710
 711
 712 /*-------------------------------------------------------------*/
 713 /*--- end                                        compress.c ---*/
 714 /*-------------------------------------------------------------*/