lib/bzip2/bzlib_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.6 of 6 September 2010
  47   Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
  48
  49   This program is based on (at least) the work of:
  50      Mike Burrows
  51      David Wheeler
  52      Peter Fenwick
  53      Alistair Moffat
  54      Radford Neal
  55      Ian H. Witten
  56      Robert Sedgewick
  57      Jon L. Bentley
  58
  59   For more information on these sources, see the manual.
  60 --*/
  61
  62 /* CHANGES
  63     0.9.0    -- original version.
  64     0.9.0a/b -- no changes in this file.
  65     0.9.0c   -- changed setting of nGroups in sendMTFValues()
  66                 so as to do a bit better on small files
  67 */
  68
  69 #include "bzlib_private.h"
  70
  71
  72 /*---------------------------------------------------*/
  73 /*--- Bit stream I/O                              ---*/
  74 /*---------------------------------------------------*/
  75
  76 /*---------------------------------------------------*/
  77 void BZ2_bsInitWrite ( EState* s )
  78 {
  79    s->bsLive = 0;
  80    s->bsBuff = 0;
  81 }
  82
  83
  84 /*---------------------------------------------------*/
  85 static
  86 void bsFinishWrite ( EState* s )
  87 {
  88    while (s->bsLive > 0) {
  89       s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
  90       s->numZ++;
  91       s->bsBuff <<= 8;
  92       s->bsLive -= 8;
  93    }
  94 }
  95
  96
  97 /*---------------------------------------------------*/
  98 #define bsNEEDW(nz)                           \
  99 {                                             \
 100    while (s->bsLive >= 8) {                   \
 101       s->zbits[s->numZ]                       \
 102          = (UChar)(s->bsBuff >> 24);          \
 103       s->numZ++;                              \
 104       s->bsBuff <<= 8;                        \
 105       s->bsLive -= 8;                         \
 106    }                                          \
 107 }
 108
 109
 110 /*---------------------------------------------------*/
 111 static
 112 __inline__
 113 void bsW ( EState* s, Int32 n, UInt32 v )
 114 {
 115    bsNEEDW ( n );
 116    s->bsBuff |= (v << (32 - s->bsLive - n));
 117    s->bsLive += n;
 118 }
 119
 120
 121 /*---------------------------------------------------*/
 122 static
 123 void bsPutUInt32 ( EState* s, UInt32 u )
 124 {
 125    bsW ( s, 8, (u >> 24) & 0xffL );
 126    bsW ( s, 8, (u >> 16) & 0xffL );
 127    bsW ( s, 8, (u >>  8) & 0xffL );
 128    bsW ( s, 8,  u        & 0xffL );
 129 }
 130
 131
 132 /*---------------------------------------------------*/
 133 static
 134 void bsPutUChar ( EState* s, UChar c )
 135 {
 136    bsW( s, 8, (UInt32)c );
 137 }
 138
 139
 140 /*---------------------------------------------------*/
 141 /*--- The back end proper                         ---*/
 142 /*---------------------------------------------------*/
 143
 144 /*---------------------------------------------------*/
 145 static
 146 void makeMaps_e ( EState* s )
 147 {
 148    Int32 i;
 149    s->nInUse = 0;
 150    for (i = 0; i < 256; i++)
 151       if (s->inUse[i]) {
 152          s->unseqToSeq[i] = s->nInUse;
 153          s->nInUse++;
 154       }
 155 }
 156
 157
 158 /*---------------------------------------------------*/
 159 static
 160 void generateMTFValues ( EState* s )
 161 {
 162    UChar   yy[256];
 163    Int32   i, j;
 164    Int32   zPend;
 165    Int32   wr;
 166    Int32   EOB;
 167
 168    /*
 169       After sorting (eg, here),
 170          s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
 171          and
 172          ((UChar*)s->arr2) [ 0 .. s->nblock-1 ]
 173          holds the original block data.
 174
 175       The first thing to do is generate the MTF values,
 176       and put them in
 177          ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
 178       Because there are strictly fewer or equal MTF values
 179       than block values, ptr values in this area are overwritten
 180       with MTF values only when they are no longer needed.
 181
 182       The final compressed bitstream is generated into the
 183       area starting at
 184          (UChar*) (&((UChar*)s->arr2)[s->nblock])
 185
 186       These storage aliases are set up in bzCompressInit(),
 187       except for the last one, which is arranged in
 188       compressBlock().
 189    */
 190    UInt32* ptr   = s->ptr;
 191    UChar* block  = s->block;
 192    UInt16* mtfv  = s->mtfv;
 193
 194    makeMaps_e ( s );
 195    EOB = s->nInUse+1;
 196
 197    for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
 198
 199    wr = 0;
 200    zPend = 0;
 201    for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
 202
 203    for (i = 0; i < s->nblock; i++) {
 204       UChar ll_i;
 205       AssertD ( wr <= i, "generateMTFValues(1)" );
 206       j = ptr[i]-1; if (j < 0) j += s->nblock;
 207       ll_i = s->unseqToSeq[block[j]];
 208       AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
 209
 210       if (yy[0] == ll_i) {
 211          zPend++;
 212       } else {
 213
 214          if (zPend > 0) {
 215             zPend--;
 216             while (True) {
 217                if (zPend & 1) {
 218                   mtfv[wr] = BZ_RUNB; wr++;
 219                   s->mtfFreq[BZ_RUNB]++;
 220                } else {
 221                   mtfv[wr] = BZ_RUNA; wr++;
 222                   s->mtfFreq[BZ_RUNA]++;
 223                }
 224                if (zPend < 2) break;
 225                zPend = (zPend - 2) / 2;
 226             };
 227             zPend = 0;
 228          }
 229          {
 230             register UChar  rtmp;
 231             register UChar* ryy_j;
 232             register UChar  rll_i;
 233             rtmp  = yy[1];
 234             yy[1] = yy[0];
 235             ryy_j = &(yy[1]);
 236             rll_i = ll_i;
 237             while ( rll_i != rtmp ) {
 238                register UChar rtmp2;
 239                ryy_j++;
 240                rtmp2  = rtmp;
 241                rtmp   = *ryy_j;
 242                *ryy_j = rtmp2;
 243             };
 244             yy[0] = rtmp;
 245             j = ryy_j - &(yy[0]);
 246             mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
 247          }
 248
 249       }
 250    }
 251
 252    if (zPend > 0) {
 253       zPend--;
 254       while (True) {
 255          if (zPend & 1) {
 256             mtfv[wr] = BZ_RUNB; wr++;
 257             s->mtfFreq[BZ_RUNB]++;
 258          } else {
 259             mtfv[wr] = BZ_RUNA; wr++;
 260             s->mtfFreq[BZ_RUNA]++;
 261          }
 262          if (zPend < 2) break;
 263          zPend = (zPend - 2) / 2;
 264       };
 265       zPend = 0;
 266    }
 267
 268    mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
 269
 270    s->nMTF = wr;
 271 }
 272
 273
 274 /*---------------------------------------------------*/
 275 #define BZ_LESSER_ICOST  0
 276 #define BZ_GREATER_ICOST 15
 277
 278 static
 279 void sendMTFValues ( EState* s )
 280 {
 281    Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
 282    Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
 283    Int32 nGroups, nBytes;
 284
 285    /*--
 286    UChar  len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 287    is a global since the decoder also needs it.
 288
 289    Int32  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 290    Int32  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 291    are also globals only used in this proc.
 292    Made global to keep stack frame size small.
 293    --*/
 294
 295
 296    UInt16 cost[BZ_N_GROUPS];
 297    Int32  fave[BZ_N_GROUPS];
 298
 299    UInt16* mtfv = s->mtfv;
 300
 301    if (s->verbosity >= 3)
 302       VPrintf3( "      %d in block, %d after MTF & 1-2 coding, "
 303                 "%d+2 syms in use\n",
 304                 s->nblock, s->nMTF, s->nInUse );
 305
 306    alphaSize = s->nInUse+2;
 307    for (t = 0; t < BZ_N_GROUPS; t++)
 308       for (v = 0; v < alphaSize; v++)
 309          s->len[t][v] = BZ_GREATER_ICOST;
 310
 311    /*--- Decide how many coding tables to use ---*/
 312    AssertH ( s->nMTF > 0, 3001 );
 313    if (s->nMTF < 200)  nGroups = 2; else
 314    if (s->nMTF < 600)  nGroups = 3; else
 315    if (s->nMTF < 1200) nGroups = 4; else
 316    if (s->nMTF < 2400) nGroups = 5; else
 317                        nGroups = 6;
 318
 319    /*--- Generate an initial set of coding tables ---*/
 320    {
 321       Int32 nPart, remF, tFreq, aFreq;
 322
 323       nPart = nGroups;
 324       remF  = s->nMTF;
 325       gs = 0;
 326       while (nPart > 0) {
 327          tFreq = remF / nPart;
 328          ge = gs-1;
 329          aFreq = 0;
 330          while (aFreq < tFreq && ge < alphaSize-1) {
 331             ge++;
 332             aFreq += s->mtfFreq[ge];
 333          }
 334
 335          if (ge > gs
 336              && nPart != nGroups && nPart != 1
 337              && ((nGroups-nPart) % 2 == 1)) {
 338             aFreq -= s->mtfFreq[ge];
 339             ge--;
 340          }
 341
 342          if (s->verbosity >= 3)
 343             VPrintf5( "      initial group %d, [%d .. %d], "
 344                       "has %d syms (%4.1f%%)\n",
 345                       nPart, gs, ge, aFreq,
 346                       (100.0 * (float)aFreq) / (float)(s->nMTF) );
 347
 348          for (v = 0; v < alphaSize; v++)
 349             if (v >= gs && v <= ge)
 350                s->len[nPart-1][v] = BZ_LESSER_ICOST; else
 351                s->len[nPart-1][v] = BZ_GREATER_ICOST;
 352
 353          nPart--;
 354          gs = ge+1;
 355          remF -= aFreq;
 356       }
 357    }
 358
 359    /*---
 360       Iterate up to BZ_N_ITERS times to improve the tables.
 361    ---*/
 362    for (iter = 0; iter < BZ_N_ITERS; iter++) {
 363
 364       for (t = 0; t < nGroups; t++) fave[t] = 0;
 365
 366       for (t = 0; t < nGroups; t++)
 367          for (v = 0; v < alphaSize; v++)
 368             s->rfreq[t][v] = 0;
 369
 370       /*---
 371         Set up an auxiliary length table which is used to fast-track
 372         the common case (nGroups == 6).
 373       ---*/
 374       if (nGroups == 6) {
 375          for (v = 0; v < alphaSize; v++) {
 376             s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
 377             s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
 378             s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
 379          }
 380       }
 381
 382       nSelectors = 0;
 383       totc = 0;
 384       gs = 0;
 385       while (True) {
 386
 387          /*--- Set group start & end marks. --*/
 388          if (gs >= s->nMTF) break;
 389          ge = gs + BZ_G_SIZE - 1;
 390          if (ge >= s->nMTF) ge = s->nMTF-1;
 391
 392          /*--
 393             Calculate the cost of this group as coded
 394             by each of the coding tables.
 395          --*/
 396          for (t = 0; t < nGroups; t++) cost[t] = 0;
 397
 398          if (nGroups == 6 && 50 == ge-gs+1) {
 399             /*--- fast track the common case ---*/
 400             register UInt32 cost01, cost23, cost45;
 401             register UInt16 icv;
 402             cost01 = cost23 = cost45 = 0;
 403
 404 #           define BZ_ITER(nn)                \
 405                icv = mtfv[gs+(nn)];           \
 406                cost01 += s->len_pack[icv][0]; \
 407                cost23 += s->len_pack[icv][1]; \
 408                cost45 += s->len_pack[icv][2]; \
 409
 410             BZ_ITER(0);  BZ_ITER(1);  BZ_ITER(2);  BZ_ITER(3);  BZ_ITER(4);
 411             BZ_ITER(5);  BZ_ITER(6);  BZ_ITER(7);  BZ_ITER(8);  BZ_ITER(9);
 412             BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
 413             BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
 414             BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
 415             BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
 416             BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
 417             BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
 418             BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
 419             BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
 420
 421 #           undef BZ_ITER
 422
 423             cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
 424             cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
 425             cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
 426
 427          } else {
 428             /*--- slow version which correctly handles all situations ---*/
 429             for (i = gs; i <= ge; i++) {
 430                UInt16 icv = mtfv[i];
 431                for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
 432             }
 433          }
 434
 435          /*--
 436             Find the coding table which is best for this group,
 437             and record its identity in the selector table.
 438          --*/
 439          bc = 999999999; bt = -1;
 440          for (t = 0; t < nGroups; t++)
 441             if (cost[t] < bc) { bc = cost[t]; bt = t; };
 442          totc += bc;
 443          fave[bt]++;
 444          s->selector[nSelectors] = bt;
 445          nSelectors++;
 446
 447          /*--
 448             Increment the symbol frequencies for the selected table.
 449           --*/
 450          if (nGroups == 6 && 50 == ge-gs+1) {
 451             /*--- fast track the common case ---*/
 452
 453 #           define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
 454
 455             BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
 456             BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
 457             BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
 458             BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
 459             BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
 460             BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
 461             BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
 462             BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
 463             BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
 464             BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
 465
 466 #           undef BZ_ITUR
 467
 468          } else {
 469             /*--- slow version which correctly handles all situations ---*/
 470             for (i = gs; i <= ge; i++)
 471                s->rfreq[bt][ mtfv[i] ]++;
 472          }
 473
 474          gs = ge+1;
 475       }
 476       if (s->verbosity >= 3) {
 477          VPrintf2 ( "      pass %d: size is %d, grp uses are ",
 478                    iter+1, totc/8 );
 479          for (t = 0; t < nGroups; t++)
 480             VPrintf1 ( "%d ", fave[t] );
 481          VPrintf0 ( "\n" );
 482       }
 483
 484       /*--
 485         Recompute the tables based on the accumulated frequencies.
 486       --*/
 487       /* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See
 488          comment in huffman.c for details. */
 489       for (t = 0; t < nGroups; t++)
 490          BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
 491                                  alphaSize, 17 /*20*/ );
 492    }
 493
 494
 495    AssertH( nGroups < 8, 3002 );
 496    AssertH( nSelectors < 32768 &&
 497             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
 498             3003 );
 499
 500
 501    /*--- Compute MTF values for the selectors. ---*/
 502    {
 503       UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
 504       for (i = 0; i < nGroups; i++) pos[i] = i;
 505       for (i = 0; i < nSelectors; i++) {
 506          ll_i = s->selector[i];
 507          j = 0;
 508          tmp = pos[j];
 509          while ( ll_i != tmp ) {
 510             j++;
 511             tmp2 = tmp;
 512             tmp = pos[j];
 513             pos[j] = tmp2;
 514          };
 515          pos[0] = tmp;
 516          s->selectorMtf[i] = j;
 517       }
 518    };
 519
 520    /*--- Assign actual codes for the tables. --*/
 521    for (t = 0; t < nGroups; t++) {
 522       minLen = 32;
 523       maxLen = 0;
 524       for (i = 0; i < alphaSize; i++) {
 525          if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
 526          if (s->len[t][i] < minLen) minLen = s->len[t][i];
 527       }
 528       AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
 529       AssertH ( !(minLen < 1),  3005 );
 530       BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
 531                           minLen, maxLen, alphaSize );
 532    }
 533
 534    /*--- Transmit the mapping table. ---*/
 535    {
 536       Bool inUse16[16];
 537       for (i = 0; i < 16; i++) {
 538           inUse16[i] = False;
 539           for (j = 0; j < 16; j++)
 540              if (s->inUse[i * 16 + j]) inUse16[i] = True;
 541       }
 542
 543       nBytes = s->numZ;
 544       for (i = 0; i < 16; i++)
 545          if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
 546
 547       for (i = 0; i < 16; i++)
 548          if (inUse16[i])
 549             for (j = 0; j < 16; j++) {
 550                if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
 551             }
 552
 553       if (s->verbosity >= 3)
 554          VPrintf1( "      bytes: mapping %d, ", s->numZ-nBytes );
 555    }
 556
 557    /*--- Now the selectors. ---*/
 558    nBytes = s->numZ;
 559    bsW ( s, 3, nGroups );
 560    bsW ( s, 15, nSelectors );
 561    for (i = 0; i < nSelectors; i++) {
 562       for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
 563       bsW(s,1,0);
 564    }
 565    if (s->verbosity >= 3)
 566       VPrintf1( "selectors %d, ", s->numZ-nBytes );
 567
 568    /*--- Now the coding tables. ---*/
 569    nBytes = s->numZ;
 570
 571    for (t = 0; t < nGroups; t++) {
 572       Int32 curr = s->len[t][0];
 573       bsW ( s, 5, curr );
 574       for (i = 0; i < alphaSize; i++) {
 575          while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
 576          while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
 577          bsW ( s, 1, 0 );
 578       }
 579    }
 580
 581    if (s->verbosity >= 3)
 582       VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
 583
 584    /*--- And finally, the block data proper ---*/
 585    nBytes = s->numZ;
 586    selCtr = 0;
 587    gs = 0;
 588    while (True) {
 589       if (gs >= s->nMTF) break;
 590       ge = gs + BZ_G_SIZE - 1;
 591       if (ge >= s->nMTF) ge = s->nMTF-1;
 592       AssertH ( s->selector[selCtr] < nGroups, 3006 );
 593
 594       if (nGroups == 6 && 50 == ge-gs+1) {
 595             /*--- fast track the common case ---*/
 596             UInt16 mtfv_i;
 597             UChar* s_len_sel_selCtr
 598                = &(s->len[s->selector[selCtr]][0]);
 599             Int32* s_code_sel_selCtr
 600                = &(s->code[s->selector[selCtr]][0]);
 601
 602 #           define BZ_ITAH(nn)                      \
 603                mtfv_i = mtfv[gs+(nn)];              \
 604                bsW ( s,                             \
 605                      s_len_sel_selCtr[mtfv_i],      \
 606                      s_code_sel_selCtr[mtfv_i] )
 607
 608             BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
 609             BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
 610             BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
 611             BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
 612             BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
 613             BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
 614             BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
 615             BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
 616             BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
 617             BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
 618
 619 #           undef BZ_ITAH
 620
 621       } else {
 622          /*--- slow version which correctly handles all situations ---*/
 623          for (i = gs; i <= ge; i++) {
 624             bsW ( s,
 625                   s->len  [s->selector[selCtr]] [mtfv[i]],
 626                   s->code [s->selector[selCtr]] [mtfv[i]] );
 627          }
 628       }
 629
 630
 631       gs = ge+1;
 632       selCtr++;
 633    }
 634    AssertH( selCtr == nSelectors, 3007 );
 635
 636    if (s->verbosity >= 3)
 637       VPrintf1( "codes %d\n", s->numZ-nBytes );
 638    else /* squash compiler 'used but not set' warning */
 639       nBytes = 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%08x, "
 655                    "combined CRC = 0x%08x, 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%08x\n   ", s->combinedCRC );
 707       bsFinishWrite ( s );
 708    }
 709 }
 710
 711
 712 /*-------------------------------------------------------------*/
 713 /*--- end                                        compress.c ---*/
 714 /*-------------------------------------------------------------*/