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 #include <compiler.h>
  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;
 284    Int32 nBytes __maybe_unused;
 285
 286    /*--
 287    UChar  len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 288    is a global since the decoder also needs it.
 289
 290    Int32  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 291    Int32  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 292    are also globals only used in this proc.
 293    Made global to keep stack frame size small.
 294    --*/
 295
 296
 297    UInt16 cost[BZ_N_GROUPS];
 298    Int32  fave[BZ_N_GROUPS];
 299
 300    UInt16* mtfv = s->mtfv;
 301
 302    if (s->verbosity >= 3)
 303       VPrintf3( "      %d in block, %d after MTF & 1-2 coding, "
 304                 "%d+2 syms in use\n",
 305                 s->nblock, s->nMTF, s->nInUse );
 306
 307    alphaSize = s->nInUse+2;
 308    for (t = 0; t < BZ_N_GROUPS; t++)
 309       for (v = 0; v < alphaSize; v++)
 310          s->len[t][v] = BZ_GREATER_ICOST;
 311
 312    /*--- Decide how many coding tables to use ---*/
 313    AssertH ( s->nMTF > 0, 3001 );
 314    if (s->nMTF < 200)  nGroups = 2; else
 315    if (s->nMTF < 600)  nGroups = 3; else
 316    if (s->nMTF < 1200) nGroups = 4; else
 317    if (s->nMTF < 2400) nGroups = 5; else
 318                        nGroups = 6;
 319
 320    /*--- Generate an initial set of coding tables ---*/
 321    {
 322       Int32 nPart, remF, tFreq, aFreq;
 323
 324       nPart = nGroups;
 325       remF  = s->nMTF;
 326       gs = 0;
 327       while (nPart > 0) {
 328          tFreq = remF / nPart;
 329          ge = gs-1;
 330          aFreq = 0;
 331          while (aFreq < tFreq && ge < alphaSize-1) {
 332             ge++;
 333             aFreq += s->mtfFreq[ge];
 334          }
 335
 336          if (ge > gs
 337              && nPart != nGroups && nPart != 1
 338              && ((nGroups-nPart) % 2 == 1)) {
 339             aFreq -= s->mtfFreq[ge];
 340             ge--;
 341          }
 342
 343          if (s->verbosity >= 3)
 344             VPrintf5( "      initial group %d, [%d .. %d], "
 345                       "has %d syms (%4.1f%%)\n",
 346                       nPart, gs, ge, aFreq,
 347                       (100.0 * (float)aFreq) / (float)(s->nMTF) );
 348
 349          for (v = 0; v < alphaSize; v++)
 350             if (v >= gs && v <= ge)
 351                s->len[nPart-1][v] = BZ_LESSER_ICOST; else
 352                s->len[nPart-1][v] = BZ_GREATER_ICOST;
 353
 354          nPart--;
 355          gs = ge+1;
 356          remF -= aFreq;
 357       }
 358    }
 359
 360    /*---
 361       Iterate up to BZ_N_ITERS times to improve the tables.
 362    ---*/
 363    for (iter = 0; iter < BZ_N_ITERS; iter++) {
 364
 365       for (t = 0; t < nGroups; t++) fave[t] = 0;
 366
 367       for (t = 0; t < nGroups; t++)
 368          for (v = 0; v < alphaSize; v++)
 369             s->rfreq[t][v] = 0;
 370
 371       /*---
 372         Set up an auxiliary length table which is used to fast-track
 373         the common case (nGroups == 6).
 374       ---*/
 375       if (nGroups == 6) {
 376          for (v = 0; v < alphaSize; v++) {
 377             s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
 378             s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
 379             s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
 380          }
 381       }
 382
 383       nSelectors = 0;
 384       totc = 0;
 385       gs = 0;
 386       while (True) {
 387
 388          /*--- Set group start & end marks. --*/
 389          if (gs >= s->nMTF) break;
 390          ge = gs + BZ_G_SIZE - 1;
 391          if (ge >= s->nMTF) ge = s->nMTF-1;
 392
 393          /*--
 394             Calculate the cost of this group as coded
 395             by each of the coding tables.
 396          --*/
 397          for (t = 0; t < nGroups; t++) cost[t] = 0;
 398
 399          if (nGroups == 6 && 50 == ge-gs+1) {
 400             /*--- fast track the common case ---*/
 401             register UInt32 cost01, cost23, cost45;
 402             register UInt16 icv;
 403             cost01 = cost23 = cost45 = 0;
 404
 405 #           define BZ_ITER(nn)                \
 406                icv = mtfv[gs+(nn)];           \
 407                cost01 += s->len_pack[icv][0]; \
 408                cost23 += s->len_pack[icv][1]; \
 409                cost45 += s->len_pack[icv][2]; \
 410
 411             BZ_ITER(0);  BZ_ITER(1);  BZ_ITER(2);  BZ_ITER(3);  BZ_ITER(4);
 412             BZ_ITER(5);  BZ_ITER(6);  BZ_ITER(7);  BZ_ITER(8);  BZ_ITER(9);
 413             BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
 414             BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
 415             BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
 416             BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
 417             BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
 418             BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
 419             BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
 420             BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
 421
 422 #           undef BZ_ITER
 423
 424             cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
 425             cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
 426             cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
 427
 428          } else {
 429             /*--- slow version which correctly handles all situations ---*/
 430             for (i = gs; i <= ge; i++) {
 431                UInt16 icv = mtfv[i];
 432                for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
 433             }
 434          }
 435
 436          /*--
 437             Find the coding table which is best for this group,
 438             and record its identity in the selector table.
 439          --*/
 440          bc = 999999999; bt = -1;
 441          for (t = 0; t < nGroups; t++)
 442             if (cost[t] < bc) { bc = cost[t]; bt = t; };
 443          totc += bc;
 444          fave[bt]++;
 445          s->selector[nSelectors] = bt;
 446          nSelectors++;
 447
 448          /*--
 449             Increment the symbol frequencies for the selected table.
 450           --*/
 451          if (nGroups == 6 && 50 == ge-gs+1) {
 452             /*--- fast track the common case ---*/
 453
 454 #           define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
 455
 456             BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
 457             BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
 458             BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
 459             BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
 460             BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
 461             BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
 462             BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
 463             BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
 464             BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
 465             BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
 466
 467 #           undef BZ_ITUR
 468
 469          } else {
 470             /*--- slow version which correctly handles all situations ---*/
 471             for (i = gs; i <= ge; i++)
 472                s->rfreq[bt][ mtfv[i] ]++;
 473          }
 474
 475          gs = ge+1;
 476       }
 477       if (s->verbosity >= 3) {
 478          VPrintf2 ( "      pass %d: size is %d, grp uses are ",
 479                    iter+1, totc/8 );
 480          for (t = 0; t < nGroups; t++)
 481             VPrintf1 ( "%d ", fave[t] );
 482          VPrintf0 ( "\n" );
 483       }
 484
 485       /*--
 486         Recompute the tables based on the accumulated frequencies.
 487       --*/
 488       /* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See
 489          comment in huffman.c for details. */
 490       for (t = 0; t < nGroups; t++)
 491          BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
 492                                  alphaSize, 17 /*20*/ );
 493    }
 494
 495
 496    AssertH( nGroups < 8, 3002 );
 497    AssertH( nSelectors < 32768 &&
 498             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
 499             3003 );
 500
 501
 502    /*--- Compute MTF values for the selectors. ---*/
 503    {
 504       UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
 505       for (i = 0; i < nGroups; i++) pos[i] = i;
 506       for (i = 0; i < nSelectors; i++) {
 507          ll_i = s->selector[i];
 508          j = 0;
 509          tmp = pos[j];
 510          while ( ll_i != tmp ) {
 511             j++;
 512             tmp2 = tmp;
 513             tmp = pos[j];
 514             pos[j] = tmp2;
 515          };
 516          pos[0] = tmp;
 517          s->selectorMtf[i] = j;
 518       }
 519    };
 520
 521    /*--- Assign actual codes for the tables. --*/
 522    for (t = 0; t < nGroups; t++) {
 523       minLen = 32;
 524       maxLen = 0;
 525       for (i = 0; i < alphaSize; i++) {
 526          if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
 527          if (s->len[t][i] < minLen) minLen = s->len[t][i];
 528       }
 529       AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
 530       AssertH ( !(minLen < 1),  3005 );
 531       BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
 532                           minLen, maxLen, alphaSize );
 533    }
 534
 535    /*--- Transmit the mapping table. ---*/
 536    {
 537       Bool inUse16[16];
 538       for (i = 0; i < 16; i++) {
 539           inUse16[i] = False;
 540           for (j = 0; j < 16; j++)
 541              if (s->inUse[i * 16 + j]) inUse16[i] = True;
 542       }
 543
 544       nBytes = s->numZ;
 545       for (i = 0; i < 16; i++)
 546          if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
 547
 548       for (i = 0; i < 16; i++)
 549          if (inUse16[i])
 550             for (j = 0; j < 16; j++) {
 551                if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
 552             }
 553
 554       if (s->verbosity >= 3)
 555          VPrintf1( "      bytes: mapping %d, ", s->numZ-nBytes );
 556    }
 557
 558    /*--- Now the selectors. ---*/
 559    nBytes = s->numZ;
 560    bsW ( s, 3, nGroups );
 561    bsW ( s, 15, nSelectors );
 562    for (i = 0; i < nSelectors; i++) {
 563       for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
 564       bsW(s,1,0);
 565    }
 566    if (s->verbosity >= 3)
 567       VPrintf1( "selectors %d, ", s->numZ-nBytes );
 568
 569    /*--- Now the coding tables. ---*/
 570    nBytes = s->numZ;
 571
 572    for (t = 0; t < nGroups; t++) {
 573       Int32 curr = s->len[t][0];
 574       bsW ( s, 5, curr );
 575       for (i = 0; i < alphaSize; i++) {
 576          while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
 577          while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
 578          bsW ( s, 1, 0 );
 579       }
 580    }
 581
 582    if (s->verbosity >= 3)
 583       VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
 584
 585    /*--- And finally, the block data proper ---*/
 586    nBytes = s->numZ;
 587    selCtr = 0;
 588    gs = 0;
 589    while (True) {
 590       if (gs >= s->nMTF) break;
 591       ge = gs + BZ_G_SIZE - 1;
 592       if (ge >= s->nMTF) ge = s->nMTF-1;
 593       AssertH ( s->selector[selCtr] < nGroups, 3006 );
 594
 595       if (nGroups == 6 && 50 == ge-gs+1) {
 596             /*--- fast track the common case ---*/
 597             UInt16 mtfv_i;
 598             UChar* s_len_sel_selCtr
 599                = &(s->len[s->selector[selCtr]][0]);
 600             Int32* s_code_sel_selCtr
 601                = &(s->code[s->selector[selCtr]][0]);
 602
 603 #           define BZ_ITAH(nn)                      \
 604                mtfv_i = mtfv[gs+(nn)];              \
 605                bsW ( s,                             \
 606                      s_len_sel_selCtr[mtfv_i],      \
 607                      s_code_sel_selCtr[mtfv_i] )
 608
 609             BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
 610             BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
 611             BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
 612             BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
 613             BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
 614             BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
 615             BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
 616             BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
 617             BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
 618             BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
 619
 620 #           undef BZ_ITAH
 621
 622       } else {
 623          /*--- slow version which correctly handles all situations ---*/
 624          for (i = gs; i <= ge; i++) {
 625             bsW ( s,
 626                   s->len  [s->selector[selCtr]] [mtfv[i]],
 627                   s->code [s->selector[selCtr]] [mtfv[i]] );
 628          }
 629       }
 630
 631
 632       gs = ge+1;
 633       selCtr++;
 634    }
 635    AssertH( selCtr == nSelectors, 3007 );
 636
 637    if (s->verbosity >= 3)
 638       VPrintf1( "codes %d\n", s->numZ-nBytes );
 639 }
 640
 641
 642 /*---------------------------------------------------*/
 643 void BZ2_compressBlock ( EState* s, Bool is_last_block )
 644 {
 645    if (s->nblock > 0) {
 646
 647       BZ_FINALISE_CRC ( s->blockCRC );
 648       s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
 649       s->combinedCRC ^= s->blockCRC;
 650       if (s->blockNo > 1) s->numZ = 0;
 651
 652       if (s->verbosity >= 2)
 653          VPrintf4( "    block %d: crc = 0x%08x, "
 654                    "combined CRC = 0x%08x, size = %d\n",
 655                    s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
 656
 657       BZ2_blockSort ( s );
 658    }
 659
 660    s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
 661
 662    /*-- If this is the first block, create the stream header. --*/
 663    if (s->blockNo == 1) {
 664       BZ2_bsInitWrite ( s );
 665       bsPutUChar ( s, BZ_HDR_B );
 666       bsPutUChar ( s, BZ_HDR_Z );
 667       bsPutUChar ( s, BZ_HDR_h );
 668       bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
 669    }
 670
 671    if (s->nblock > 0) {
 672
 673       bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
 674       bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
 675       bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
 676
 677       /*-- Now the block's CRC, so it is in a known place. --*/
 678       bsPutUInt32 ( s, s->blockCRC );
 679
 680       /*--
 681          Now a single bit indicating (non-)randomisation.
 682          As of version 0.9.5, we use a better sorting algorithm
 683          which makes randomisation unnecessary.  So always set
 684          the randomised bit to 'no'.  Of course, the decoder
 685          still needs to be able to handle randomised blocks
 686          so as to maintain backwards compatibility with
 687          older versions of bzip2.
 688       --*/
 689       bsW(s,1,0);
 690
 691       bsW ( s, 24, s->origPtr );
 692       generateMTFValues ( s );
 693       sendMTFValues ( s );
 694    }
 695
 696
 697    /*-- If this is the last block, add the stream trailer. --*/
 698    if (is_last_block) {
 699
 700       bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
 701       bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
 702       bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
 703       bsPutUInt32 ( s, s->combinedCRC );
 704       if (s->verbosity >= 2)
 705          VPrintf1( "    final combined CRC = 0x%08x\n   ", s->combinedCRC );
 706       bsFinishWrite ( s );
 707    }
 708 }
 709
 710
 711 /*-------------------------------------------------------------*/
 712 /*--- end                                        compress.c ---*/
 713 /*-------------------------------------------------------------*/