contrib/bzip2/compress.c

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