contrib/bzip2-1.0/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-2005 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@bzip.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       /* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See
 492          comment in huffman.c for details. */
 493       for (t = 0; t < nGroups; t++)
 494          BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
 495                                  alphaSize, 17 /*20*/ );
 496    }
 497
 498
 499    AssertH( nGroups < 8, 3002 );
 500    AssertH( nSelectors < 32768 &&
 501             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
 502             3003 );
 503
 504
 505    /*--- Compute MTF values for the selectors. ---*/
 506    {
 507       UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
 508       for (i = 0; i < nGroups; i++) pos[i] = i;
 509       for (i = 0; i < nSelectors; i++) {
 510          ll_i = s->selector[i];
 511          j = 0;
 512          tmp = pos[j];
 513          while ( ll_i != tmp ) {
 514             j++;
 515             tmp2 = tmp;
 516             tmp = pos[j];
 517             pos[j] = tmp2;
 518          };
 519          pos[0] = tmp;
 520          s->selectorMtf[i] = j;
 521       }
 522    };
 523
 524    /*--- Assign actual codes for the tables. --*/
 525    for (t = 0; t < nGroups; t++) {
 526       minLen = 32;
 527       maxLen = 0;
 528       for (i = 0; i < alphaSize; i++) {
 529          if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
 530          if (s->len[t][i] < minLen) minLen = s->len[t][i];
 531       }
 532       AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
 533       AssertH ( !(minLen < 1),  3005 );
 534       BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
 535                           minLen, maxLen, alphaSize );
 536    }
 537
 538    /*--- Transmit the mapping table. ---*/
 539    {
 540       Bool inUse16[16];
 541       for (i = 0; i < 16; i++) {
 542           inUse16[i] = False;
 543           for (j = 0; j < 16; j++)
 544              if (s->inUse[i * 16 + j]) inUse16[i] = True;
 545       }
 546
 547       nBytes = s->numZ;
 548       for (i = 0; i < 16; i++)
 549          if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
 550
 551       for (i = 0; i < 16; i++)
 552          if (inUse16[i])
 553             for (j = 0; j < 16; j++) {
 554                if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
 555             }
 556
 557       if (s->verbosity >= 3)
 558          VPrintf1( "      bytes: mapping %d, ", s->numZ-nBytes );
 559    }
 560
 561    /*--- Now the selectors. ---*/
 562    nBytes = s->numZ;
 563    bsW ( s, 3, nGroups );
 564    bsW ( s, 15, nSelectors );
 565    for (i = 0; i < nSelectors; i++) {
 566       for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
 567       bsW(s,1,0);
 568    }
 569    if (s->verbosity >= 3)
 570       VPrintf1( "selectors %d, ", s->numZ-nBytes );
 571
 572    /*--- Now the coding tables. ---*/
 573    nBytes = s->numZ;
 574
 575    for (t = 0; t < nGroups; t++) {
 576       Int32 curr = s->len[t][0];
 577       bsW ( s, 5, curr );
 578       for (i = 0; i < alphaSize; i++) {
 579          while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
 580          while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
 581          bsW ( s, 1, 0 );
 582       }
 583    }
 584
 585    if (s->verbosity >= 3)
 586       VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
 587
 588    /*--- And finally, the block data proper ---*/
 589    nBytes = s->numZ;
 590    selCtr = 0;
 591    gs = 0;
 592    while (True) {
 593       if (gs >= s->nMTF) break;
 594       ge = gs + BZ_G_SIZE - 1;
 595       if (ge >= s->nMTF) ge = s->nMTF-1;
 596       AssertH ( s->selector[selCtr] < nGroups, 3006 );
 597
 598       if (nGroups == 6 && 50 == ge-gs+1) {
 599             /*--- fast track the common case ---*/
 600             UInt16 mtfv_i;
 601             UChar* s_len_sel_selCtr
 602                = &(s->len[s->selector[selCtr]][0]);
 603             Int32* s_code_sel_selCtr
 604                = &(s->code[s->selector[selCtr]][0]);
 605
 606 #           define BZ_ITAH(nn)                      \
 607                mtfv_i = mtfv[gs+(nn)];              \
 608                bsW ( s,                             \
 609                      s_len_sel_selCtr[mtfv_i],      \
 610                      s_code_sel_selCtr[mtfv_i] )
 611
 612             BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
 613             BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
 614             BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
 615             BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
 616             BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
 617             BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
 618             BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
 619             BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
 620             BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
 621             BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
 622
 623 #           undef BZ_ITAH
 624
 625       } else {
 626          /*--- slow version which correctly handles all situations ---*/
 627          for (i = gs; i <= ge; i++) {
 628             bsW ( s,
 629                   s->len  [s->selector[selCtr]] [mtfv[i]],
 630                   s->code [s->selector[selCtr]] [mtfv[i]] );
 631          }
 632       }
 633
 634
 635       gs = ge+1;
 636       selCtr++;
 637    }
 638    AssertH( selCtr == nSelectors, 3007 );
 639
 640    if (s->verbosity >= 3)
 641       VPrintf1( "codes %d\n", s->numZ-nBytes );
 642 }
 643
 644
 645 /*---------------------------------------------------*/
 646 void BZ2_compressBlock ( EState* s, Bool is_last_block )
 647 {
 648    if (s->nblock > 0) {
 649
 650       BZ_FINALISE_CRC ( s->blockCRC );
 651       s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
 652       s->combinedCRC ^= s->blockCRC;
 653       if (s->blockNo > 1) s->numZ = 0;
 654
 655       if (s->verbosity >= 2)
 656          VPrintf4( "    block %d: crc = 0x%08x, "
 657                    "combined CRC = 0x%08x, size = %d\n",
 658                    s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
 659
 660       BZ2_blockSort ( s );
 661    }
 662
 663    s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
 664
 665    /*-- If this is the first block, create the stream header. --*/
 666    if (s->blockNo == 1) {
 667       BZ2_bsInitWrite ( s );
 668       bsPutUChar ( s, BZ_HDR_B );
 669       bsPutUChar ( s, BZ_HDR_Z );
 670       bsPutUChar ( s, BZ_HDR_h );
 671       bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
 672    }
 673
 674    if (s->nblock > 0) {
 675
 676       bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
 677       bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
 678       bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
 679
 680       /*-- Now the block's CRC, so it is in a known place. --*/
 681       bsPutUInt32 ( s, s->blockCRC );
 682
 683       /*--
 684          Now a single bit indicating (non-)randomisation.
 685          As of version 0.9.5, we use a better sorting algorithm
 686          which makes randomisation unnecessary.  So always set
 687          the randomised bit to 'no'.  Of course, the decoder
 688          still needs to be able to handle randomised blocks
 689          so as to maintain backwards compatibility with
 690          older versions of bzip2.
 691       --*/
 692       bsW(s,1,0);
 693
 694       bsW ( s, 24, s->origPtr );
 695       generateMTFValues ( s );
 696       sendMTFValues ( s );
 697    }
 698
 699
 700    /*-- If this is the last block, add the stream trailer. --*/
 701    if (is_last_block) {
 702
 703       bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
 704       bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
 705       bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
 706       bsPutUInt32 ( s, s->combinedCRC );
 707       if (s->verbosity >= 2)
 708          VPrintf1( "    final combined CRC = 0x%08x\n   ", s->combinedCRC );
 709       bsFinishWrite ( s );
 710    }
 711 }
 712
 713
 714 /*-------------------------------------------------------------*/
 715 /*--- end                                        compress.c ---*/
 716 /*-------------------------------------------------------------*/