external/bsd/bzip2/dist/compress.c

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