archival/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_FEATURE_SPEED >= 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
 138          *      ((uint16_t*)s->arr1)[0 .. s->nblock-1].
 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
 145          *      &((uint8_t*)s->arr2)[s->nblock]
 146          *
 147          * These storage aliases are set up in bzCompressInit(),
 148          * except for the last one, which is arranged in
 149          * compressBlock().
 150          */
 151         uint32_t* ptr   = s->ptr;
 152         uint8_t*  block = s->block;
 153         uint16_t* mtfv  = s->mtfv;
 154
 155         makeMaps_e(s);
 156         EOB = s->nInUse+1;
 157
 158         for (i = 0; i <= EOB; i++)
 159                 s->mtfFreq[i] = 0;
 160
 161         wr = 0;
 162         zPend = 0;
 163         for (i = 0; i < s->nInUse; i++)
 164                 yy[i] = (uint8_t) i;
 165
 166         for (i = 0; i < s->nblock; i++) {
 167                 uint8_t ll_i;
 168                 AssertD(wr <= i, "generateMTFValues(1)");
 169                 j = ptr[i] - 1;
 170                 if (j < 0)
 171                         j += s->nblock;
 172                 ll_i = s->unseqToSeq[block[j]];
 173                 AssertD(ll_i < s->nInUse, "generateMTFValues(2a)");
 174
 175                 if (yy[0] == ll_i) {
 176                         zPend++;
 177                 } else {
 178                         if (zPend > 0) {
 179                                 zPend--;
 180                                 while (1) {
 181                                         if (zPend & 1) {
 182                                                 mtfv[wr] = BZ_RUNB; wr++;
 183                                                 s->mtfFreq[BZ_RUNB]++;
 184                                         } else {
 185                                                 mtfv[wr] = BZ_RUNA; wr++;
 186                                                 s->mtfFreq[BZ_RUNA]++;
 187                                         }
 188                                         if (zPend < 2) break;
 189                                         zPend = (uint32_t)(zPend - 2) / 2;
 190                                         /* bbox: unsigned div is easier */
 191                                 };
 192                                 zPend = 0;
 193                         }
 194                         {
 195                                 register uint8_t  rtmp;
 196                                 register uint8_t* ryy_j;
 197                                 register uint8_t  rll_i;
 198                                 rtmp  = yy[1];
 199                                 yy[1] = yy[0];
 200                                 ryy_j = &(yy[1]);
 201                                 rll_i = ll_i;
 202                                 while (rll_i != rtmp) {
 203                                         register uint8_t rtmp2;
 204                                         ryy_j++;
 205                                         rtmp2  = rtmp;
 206                                         rtmp   = *ryy_j;
 207                                         *ryy_j = rtmp2;
 208                                 };
 209                                 yy[0] = rtmp;
 210                                 j = ryy_j - &(yy[0]);
 211                                 mtfv[wr] = j+1;
 212                                 wr++;
 213                                 s->mtfFreq[j+1]++;
 214                         }
 215                 }
 216         }
 217
 218         if (zPend > 0) {
 219                 zPend--;
 220                 while (1) {
 221                         if (zPend & 1) {
 222                                 mtfv[wr] = BZ_RUNB;
 223                                 wr++;
 224                                 s->mtfFreq[BZ_RUNB]++;
 225                         } else {
 226                                 mtfv[wr] = BZ_RUNA;
 227                                 wr++;
 228                                 s->mtfFreq[BZ_RUNA]++;
 229                         }
 230                         if (zPend < 2)
 231                                 break;
 232                         zPend = (uint32_t)(zPend - 2) / 2;
 233                         /* bbox: unsigned div is easier */
 234                 };
 235                 zPend = 0;
 236         }
 237
 238         mtfv[wr] = EOB;
 239         wr++;
 240         s->mtfFreq[EOB]++;
 241
 242         s->nMTF = wr;
 243 }
 244
 245
 246 /*---------------------------------------------------*/
 247 #define BZ_LESSER_ICOST  0
 248 #define BZ_GREATER_ICOST 15
 249
 250 static NOINLINE
 251 void sendMTFValues(EState* s)
 252 {
 253         int32_t v, t, i, j, gs, ge, totc, bt, bc, iter;
 254         int32_t nSelectors, alphaSize, minLen, maxLen, selCtr;
 255         int32_t nGroups, nBytes;
 256
 257         /*
 258          * uint8_t len[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 259          * is a global since the decoder also needs it.
 260          *
 261          * int32_t  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 262          * int32_t  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 263          * are also globals only used in this proc.
 264          * Made global to keep stack frame size small.
 265          */
 266 #define code     sendMTFValues__code
 267 #define rfreq    sendMTFValues__rfreq
 268 #define len_pack sendMTFValues__len_pack
 269
 270         uint16_t cost[BZ_N_GROUPS];
 271         int32_t  fave[BZ_N_GROUPS];
 272
 273         uint16_t* mtfv = s->mtfv;
 274
 275         alphaSize = s->nInUse + 2;
 276         for (t = 0; t < BZ_N_GROUPS; t++)
 277                 for (v = 0; v < alphaSize; v++)
 278                         s->len[t][v] = BZ_GREATER_ICOST;
 279
 280         /*--- Decide how many coding tables to use ---*/
 281         AssertH(s->nMTF > 0, 3001);
 282         if (s->nMTF < 200)  nGroups = 2; else
 283         if (s->nMTF < 600)  nGroups = 3; else
 284         if (s->nMTF < 1200) nGroups = 4; else
 285         if (s->nMTF < 2400) nGroups = 5; else
 286         nGroups = 6;
 287
 288         /*--- Generate an initial set of coding tables ---*/
 289         {
 290                 int32_t nPart, remF, tFreq, aFreq;
 291
 292                 nPart = nGroups;
 293                 remF  = s->nMTF;
 294                 gs = 0;
 295                 while (nPart > 0) {
 296                         tFreq = remF / nPart;
 297                         ge = gs - 1;
 298                         aFreq = 0;
 299                         while (aFreq < tFreq && ge < alphaSize-1) {
 300                                 ge++;
 301                                 aFreq += s->mtfFreq[ge];
 302                         }
 303
 304                         if (ge > gs
 305                          && nPart != nGroups && nPart != 1
 306                          && ((nGroups - nPart) % 2 == 1) /* bbox: can this be replaced by x & 1? */
 307                         ) {
 308                                 aFreq -= s->mtfFreq[ge];
 309                                 ge--;
 310                         }
 311
 312                         for (v = 0; v < alphaSize; v++)
 313                                 if (v >= gs && v <= ge)
 314                                         s->len[nPart-1][v] = BZ_LESSER_ICOST;
 315                                 else
 316                                         s->len[nPart-1][v] = BZ_GREATER_ICOST;
 317
 318                         nPart--;
 319                         gs = ge + 1;
 320                         remF -= aFreq;
 321                 }
 322         }
 323
 324         /*
 325          * Iterate up to BZ_N_ITERS times to improve the tables.
 326          */
 327         for (iter = 0; iter < BZ_N_ITERS; iter++) {
 328                 for (t = 0; t < nGroups; t++)
 329                         fave[t] = 0;
 330
 331                 for (t = 0; t < nGroups; t++)
 332                         for (v = 0; v < alphaSize; v++)
 333                                 s->rfreq[t][v] = 0;
 334
 335 #if CONFIG_BZIP2_FEATURE_SPEED >= 5
 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 #endif
 348                 nSelectors = 0;
 349                 totc = 0;
 350                 gs = 0;
 351                 while (1) {
 352                         /*--- Set group start & end marks. --*/
 353                         if (gs >= s->nMTF)
 354                                 break;
 355                         ge = gs + BZ_G_SIZE - 1;
 356                         if (ge >= s->nMTF)
 357                                 ge = s->nMTF-1;
 358
 359                         /*
 360                          * Calculate the cost of this group as coded
 361                          * by each of the coding tables.
 362                          */
 363                         for (t = 0; t < nGroups; t++)
 364                                 cost[t] = 0;
 365 #if CONFIG_BZIP2_FEATURE_SPEED >= 5
 366                         if (nGroups == 6 && 50 == ge-gs+1) {
 367                                 /*--- fast track the common case ---*/
 368                                 register uint32_t cost01, cost23, cost45;
 369                                 register uint16_t icv;
 370                                 cost01 = cost23 = cost45 = 0;
 371 #define BZ_ITER(nn) \
 372         icv = mtfv[gs+(nn)]; \
 373         cost01 += s->len_pack[icv][0]; \
 374         cost23 += s->len_pack[icv][1]; \
 375         cost45 += s->len_pack[icv][2];
 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 #undef BZ_ITER
 387                                 cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
 388                                 cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
 389                                 cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
 390
 391                         } else
 392 #endif
 393                         {
 394                                 /*--- slow version which correctly handles all situations ---*/
 395                                 for (i = gs; i <= ge; i++) {
 396                                         uint16_t icv = mtfv[i];
 397                                         for (t = 0; t < nGroups; t++)
 398                                                 cost[t] += s->len[t][icv];
 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;*/
 406                         /*bt = -1;*/
 407                         bc = cost[0];
 408                         bt = 0;
 409                         for (t = 1 /*0*/; t < nGroups; t++) {
 410                                 if (cost[t] < bc) {
 411                                         bc = cost[t];
 412                                         bt = t;
 413                                 }
 414                         }
 415                         totc += bc;
 416                         fave[bt]++;
 417                         s->selector[nSelectors] = bt;
 418                         nSelectors++;
 419
 420                         /*
 421                          * Increment the symbol frequencies for the selected table.
 422                          */
 423 /* 1% faster compress. +800 bytes */
 424 #if CONFIG_BZIP2_FEATURE_SPEED >= 4
 425                         if (nGroups == 6 && 50 == ge-gs+1) {
 426                                 /*--- fast track the common case ---*/
 427 #define BZ_ITUR(nn) s->rfreq[bt][mtfv[gs + (nn)]]++
 428                                 BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
 429                                 BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
 430                                 BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
 431                                 BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
 432                                 BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
 433                                 BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
 434                                 BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
 435                                 BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
 436                                 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
 437                                 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
 438 #undef BZ_ITUR
 439                                 gs = ge + 1;
 440                         } else
 441 #endif
 442                         {
 443                                 /*--- slow version which correctly handles all situations ---*/
 444                                 while (gs <= ge) {
 445                                         s->rfreq[bt][mtfv[gs]]++;
 446                                         gs++;
 447                                 }
 448                                 /* already is: gs = ge + 1; */
 449                         }
 450                 }
 451
 452                 /*
 453                  * Recompute the tables based on the accumulated frequencies.
 454                  */
 455                 /* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See
 456                  * comment in huffman.c for details. */
 457                 for (t = 0; t < nGroups; t++)
 458                         BZ2_hbMakeCodeLengths(s, &(s->len[t][0]), &(s->rfreq[t][0]), alphaSize, 17 /*20*/);
 459         }
 460
 461         AssertH(nGroups < 8, 3002);
 462         AssertH(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZ_G_SIZE)), 3003);
 463
 464         /*--- Compute MTF values for the selectors. ---*/
 465         {
 466                 uint8_t pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
 467
 468                 for (i = 0; i < nGroups; i++)
 469                         pos[i] = i;
 470                 for (i = 0; i < nSelectors; i++) {
 471                         ll_i = s->selector[i];
 472                         j = 0;
 473                         tmp = pos[j];
 474                         while (ll_i != tmp) {
 475                                 j++;
 476                                 tmp2 = tmp;
 477                                 tmp = pos[j];
 478                                 pos[j] = tmp2;
 479                         };
 480                         pos[0] = tmp;
 481                         s->selectorMtf[i] = j;
 482                 }
 483         };
 484
 485         /*--- Assign actual codes for the tables. --*/
 486         for (t = 0; t < nGroups; t++) {
 487                 minLen = 32;
 488                 maxLen = 0;
 489                 for (i = 0; i < alphaSize; i++) {
 490                         if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
 491                         if (s->len[t][i] < minLen) minLen = s->len[t][i];
 492                 }
 493                 AssertH(!(maxLen > 17 /*20*/), 3004);
 494                 AssertH(!(minLen < 1), 3005);
 495                 BZ2_hbAssignCodes(&(s->code[t][0]), &(s->len[t][0]), minLen, maxLen, alphaSize);
 496         }
 497
 498         /*--- Transmit the mapping table. ---*/
 499         {
 500                 /* bbox: optimized a bit more than in bzip2 */
 501                 int inUse16 = 0;
 502                 for (i = 0; i < 16; i++) {
 503                         if (sizeof(long) <= 4) {
 504                                 inUse16 = inUse16*2 +
 505                                         ((*(uint32_t*)&(s->inUse[i * 16 + 0])
 506                                         | *(uint32_t*)&(s->inUse[i * 16 + 4])
 507                                         | *(uint32_t*)&(s->inUse[i * 16 + 8])
 508                                         | *(uint32_t*)&(s->inUse[i * 16 + 12])) != 0);
 509                         } else { /* Our CPU can do better */
 510                                 inUse16 = inUse16*2 +
 511                                         ((*(uint64_t*)&(s->inUse[i * 16 + 0])
 512                                         | *(uint64_t*)&(s->inUse[i * 16 + 8])) != 0);
 513                         }
 514                 }
 515
 516                 nBytes = s->numZ;
 517                 bsW(s, 16, inUse16);
 518
 519                 inUse16 <<= (sizeof(int)*8 - 16); /* move 15th bit into sign bit */
 520                 for (i = 0; i < 16; i++) {
 521                         if (inUse16 < 0) {
 522                                 unsigned v16 = 0;
 523                                 for (j = 0; j < 16; j++)
 524                                         v16 = v16*2 + s->inUse[i * 16 + j];
 525                                 bsW(s, 16, v16);
 526                         }
 527                         inUse16 <<= 1;
 528                 }
 529         }
 530
 531         /*--- Now the selectors. ---*/
 532         nBytes = s->numZ;
 533         bsW(s, 3, nGroups);
 534         bsW(s, 15, nSelectors);
 535         for (i = 0; i < nSelectors; i++) {
 536                 for (j = 0; j < s->selectorMtf[i]; j++)
 537                         bsW(s, 1, 1);
 538                 bsW(s, 1, 0);
 539         }
 540
 541         /*--- Now the coding tables. ---*/
 542         nBytes = s->numZ;
 543
 544         for (t = 0; t < nGroups; t++) {
 545                 int32_t curr = s->len[t][0];
 546                 bsW(s, 5, curr);
 547                 for (i = 0; i < alphaSize; i++) {
 548                         while (curr < s->len[t][i]) { bsW(s, 2, 2); curr++; /* 10 */ };
 549                         while (curr > s->len[t][i]) { bsW(s, 2, 3); curr--; /* 11 */ };
 550                         bsW(s, 1, 0);
 551                 }
 552         }
 553
 554         /*--- And finally, the block data proper ---*/
 555         nBytes = s->numZ;
 556         selCtr = 0;
 557         gs = 0;
 558         while (1) {
 559                 if (gs >= s->nMTF)
 560                         break;
 561                 ge = gs + BZ_G_SIZE - 1;
 562                 if (ge >= s->nMTF)
 563                         ge = s->nMTF-1;
 564                 AssertH(s->selector[selCtr] < nGroups, 3006);
 565
 566 /* Costs 1300 bytes and is _slower_ (on Intel Core 2) */
 567 #if 0
 568                 if (nGroups == 6 && 50 == ge-gs+1) {
 569                         /*--- fast track the common case ---*/
 570                         uint16_t mtfv_i;
 571                         uint8_t* s_len_sel_selCtr  = &(s->len[s->selector[selCtr]][0]);
 572                         int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
 573 #define BZ_ITAH(nn) \
 574         mtfv_i = mtfv[gs+(nn)]; \
 575         bsW(s, s_len_sel_selCtr[mtfv_i], s_code_sel_selCtr[mtfv_i])
 576                         BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
 577                         BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
 578                         BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
 579                         BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
 580                         BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
 581                         BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
 582                         BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
 583                         BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
 584                         BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
 585                         BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
 586 #undef BZ_ITAH
 587                         gs = ge+1;
 588                 } else
 589 #endif
 590                 {
 591                         /*--- slow version which correctly handles all situations ---*/
 592                         /* code is bit bigger, but moves multiply out of the loop */
 593                         uint8_t* s_len_sel_selCtr  = &(s->len [s->selector[selCtr]][0]);
 594                         int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
 595                         while (gs <= ge) {
 596                                 bsW(s,
 597                                         s_len_sel_selCtr[mtfv[gs]],
 598                                         s_code_sel_selCtr[mtfv[gs]]
 599                                 );
 600                                 gs++;
 601                         }
 602                         /* already is: gs = ge+1; */
 603                 }
 604                 selCtr++;
 605         }
 606         AssertH(selCtr == nSelectors, 3007);
 607 #undef code
 608 #undef rfreq
 609 #undef len_pack
 610 }
 611
 612
 613 /*---------------------------------------------------*/
 614 static
 615 void BZ2_compressBlock(EState* s, int is_last_block)
 616 {
 617         if (s->nblock > 0) {
 618                 BZ_FINALISE_CRC(s->blockCRC);
 619                 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
 620                 s->combinedCRC ^= s->blockCRC;
 621                 if (s->blockNo > 1)
 622                         s->numZ = 0;
 623
 624                 BZ2_blockSort(s);
 625         }
 626
 627         s->zbits = &((uint8_t*)s->arr2)[s->nblock];
 628
 629         /*-- If this is the first block, create the stream header. --*/
 630         if (s->blockNo == 1) {
 631                 BZ2_bsInitWrite(s);
 632                 /*bsPutU8(s, BZ_HDR_B);*/
 633                 /*bsPutU8(s, BZ_HDR_Z);*/
 634                 /*bsPutU8(s, BZ_HDR_h);*/
 635                 /*bsPutU8(s, BZ_HDR_0 + s->blockSize100k);*/
 636                 bsPutU32(s, BZ_HDR_BZh0 + s->blockSize100k);
 637         }
 638
 639         if (s->nblock > 0) {
 640                 /*bsPutU8(s, 0x31);*/
 641                 /*bsPutU8(s, 0x41);*/
 642                 /*bsPutU8(s, 0x59);*/
 643                 /*bsPutU8(s, 0x26);*/
 644                 bsPutU32(s, 0x31415926);
 645                 /*bsPutU8(s, 0x53);*/
 646                 /*bsPutU8(s, 0x59);*/
 647                 bsPutU16(s, 0x5359);
 648
 649                 /*-- Now the block's CRC, so it is in a known place. --*/
 650                 bsPutU32(s, s->blockCRC);
 651
 652                 /*
 653                  * Now a single bit indicating (non-)randomisation.
 654                  * As of version 0.9.5, we use a better sorting algorithm
 655                  * which makes randomisation unnecessary.  So always set
 656                  * the randomised bit to 'no'.  Of course, the decoder
 657                  * still needs to be able to handle randomised blocks
 658                  * so as to maintain backwards compatibility with
 659                  * older versions of bzip2.
 660                  */
 661                 bsW(s, 1, 0);
 662
 663                 bsW(s, 24, s->origPtr);
 664                 generateMTFValues(s);
 665                 sendMTFValues(s);
 666         }
 667
 668         /*-- If this is the last block, add the stream trailer. --*/
 669         if (is_last_block) {
 670                 /*bsPutU8(s, 0x17);*/
 671                 /*bsPutU8(s, 0x72);*/
 672                 /*bsPutU8(s, 0x45);*/
 673                 /*bsPutU8(s, 0x38);*/
 674                 bsPutU32(s, 0x17724538);
 675                 /*bsPutU8(s, 0x50);*/
 676                 /*bsPutU8(s, 0x90);*/
 677                 bsPutU16(s, 0x5090);
 678                 bsPutU32(s, s->combinedCRC);
 679                 bsFinishWrite(s);
 680         }
 681 }
 682
 683
 684 /*-------------------------------------------------------------*/
 685 /*--- end                                        compress.c ---*/
 686 /*-------------------------------------------------------------*/