archival/libarchive/bz/compress.c

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