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 = (zPend - 2) / 2;
 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
 218         if (zPend > 0) {
 219                 zPend--;
 220                 while (1) {
 221                         if (zPend & 1) {
 222                                 mtfv[wr] = BZ_RUNB; wr++;
 223                                 s->mtfFreq[BZ_RUNB]++;
 224                         } else {
 225                                 mtfv[wr] = BZ_RUNA; wr++;
 226                                 s->mtfFreq[BZ_RUNA]++;
 227                         }
 228                         if (zPend < 2)
 229                                 break;
 230                         zPend = (zPend - 2) / 2;
 231                 };
 232                 zPend = 0;
 233         }
 234
 235         mtfv[wr] = EOB;
 236         wr++;
 237         s->mtfFreq[EOB]++;
 238
 239         s->nMTF = wr;
 240 }
 241
 242
 243 /*---------------------------------------------------*/
 244 #define BZ_LESSER_ICOST  0
 245 #define BZ_GREATER_ICOST 15
 246
 247 static NOINLINE
 248 void sendMTFValues(EState* s)
 249 {
 250         int32_t v, t, i, j, gs, ge, totc, bt, bc, iter;
 251         int32_t nSelectors, alphaSize, minLen, maxLen, selCtr;
 252         int32_t nGroups, nBytes;
 253
 254         /*
 255          * uint8_t len[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 256          * is a global since the decoder also needs it.
 257          *
 258          * int32_t  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 259          * int32_t  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
 260          * are also globals only used in this proc.
 261          * Made global to keep stack frame size small.
 262          */
 263
 264         uint16_t cost[BZ_N_GROUPS];
 265         int32_t  fave[BZ_N_GROUPS];
 266
 267         uint16_t* mtfv = s->mtfv;
 268
 269         alphaSize = s->nInUse+2;
 270         for (t = 0; t < BZ_N_GROUPS; t++)
 271                 for (v = 0; v < alphaSize; v++)
 272                         s->len[t][v] = BZ_GREATER_ICOST;
 273
 274         /*--- Decide how many coding tables to use ---*/
 275         AssertH(s->nMTF > 0, 3001);
 276         if (s->nMTF < 200)  nGroups = 2; else
 277         if (s->nMTF < 600)  nGroups = 3; else
 278         if (s->nMTF < 1200) nGroups = 4; else
 279         if (s->nMTF < 2400) nGroups = 5; else
 280         nGroups = 6;
 281
 282         /*--- Generate an initial set of coding tables ---*/
 283         {
 284                 int32_t nPart, remF, tFreq, aFreq;
 285
 286                 nPart = nGroups;
 287                 remF  = s->nMTF;
 288                 gs = 0;
 289                 while (nPart > 0) {
 290                         tFreq = remF / nPart;
 291                         ge = gs-1;
 292                         aFreq = 0;
 293                         while (aFreq < tFreq && ge < alphaSize-1) {
 294                                 ge++;
 295                                 aFreq += s->mtfFreq[ge];
 296                         }
 297
 298                         if (ge > gs
 299                          && nPart != nGroups && nPart != 1
 300                          && ((nGroups - nPart) % 2 == 1)
 301                         ) {
 302                                 aFreq -= s->mtfFreq[ge];
 303                                 ge--;
 304                         }
 305
 306                         for (v = 0; v < alphaSize; v++)
 307                                 if (v >= gs && v <= ge)
 308                                         s->len[nPart-1][v] = BZ_LESSER_ICOST;
 309                                 else
 310                                         s->len[nPart-1][v] = BZ_GREATER_ICOST;
 311
 312                         nPart--;
 313                         gs = ge+1;
 314                         remF -= aFreq;
 315                 }
 316         }
 317
 318         /*
 319          * Iterate up to BZ_N_ITERS times to improve the tables.
 320          */
 321         for (iter = 0; iter < BZ_N_ITERS; iter++) {
 322                 for (t = 0; t < nGroups; t++)
 323                         fave[t] = 0;
 324
 325                 for (t = 0; t < nGroups; t++)
 326                         for (v = 0; v < alphaSize; v++)
 327                                 s->rfreq[t][v] = 0;
 328
 329 #if CONFIG_BZIP2_FEATURE_SPEED >= 5
 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 #endif
 342                 nSelectors = 0;
 343                 totc = 0;
 344                 gs = 0;
 345                 while (1) {
 346                         /*--- Set group start & end marks. --*/
 347                         if (gs >= s->nMTF)
 348                                 break;
 349                         ge = gs + BZ_G_SIZE - 1;
 350                         if (ge >= s->nMTF)
 351                                 ge = s->nMTF-1;
 352
 353                         /*
 354                          * Calculate the cost of this group as coded
 355                          * by each of the coding tables.
 356                          */
 357                         for (t = 0; t < nGroups; t++)
 358                                 cost[t] = 0;
 359 #if CONFIG_BZIP2_FEATURE_SPEED >= 5
 360                         if (nGroups == 6 && 50 == ge-gs+1) {
 361                                 /*--- fast track the common case ---*/
 362                                 register uint32_t cost01, cost23, cost45;
 363                                 register uint16_t icv;
 364                                 cost01 = cost23 = cost45 = 0;
 365 #define BZ_ITER(nn) \
 366         icv = mtfv[gs+(nn)]; \
 367         cost01 += s->len_pack[icv][0]; \
 368         cost23 += s->len_pack[icv][1]; \
 369         cost45 += s->len_pack[icv][2];
 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 #undef BZ_ITER
 381                                 cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
 382                                 cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
 383                                 cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
 384
 385                         } else
 386 #endif
 387                         {
 388                                 /*--- slow version which correctly handles all situations ---*/
 389                                 for (i = gs; i <= ge; i++) {
 390                                         uint16_t icv = mtfv[i];
 391                                         for (t = 0; t < nGroups; t++)
 392                                                 cost[t] += s->len[t][icv];
 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;*/
 400                         /*bt = -1;*/
 401                         bc = cost[0];
 402                         bt = 0;
 403                         for (t = 1 /*0*/; t < nGroups; t++) {
 404                                 if (cost[t] < bc) {
 405                                         bc = cost[t];
 406                                         bt = t;
 407                                 }
 408                         }
 409                         totc += bc;
 410                         fave[bt]++;
 411                         s->selector[nSelectors] = bt;
 412                         nSelectors++;
 413
 414                         /*
 415                          * Increment the symbol frequencies for the selected table.
 416                          */
 417 /* 1% faster compress. +800 bytes */
 418 #if CONFIG_BZIP2_FEATURE_SPEED >= 4
 419                         if (nGroups == 6 && 50 == ge-gs+1) {
 420                                 /*--- fast track the common case ---*/
 421 #define BZ_ITUR(nn) s->rfreq[bt][mtfv[gs + (nn)]]++
 422                                 BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
 423                                 BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
 424                                 BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
 425                                 BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
 426                                 BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
 427                                 BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
 428                                 BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
 429                                 BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
 430                                 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
 431                                 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
 432 #undef BZ_ITUR
 433                                 gs = ge + 1;
 434                         } else
 435 #endif
 436                         {
 437                                 /*--- slow version which correctly handles all situations ---*/
 438                                 while (gs <= ge) {
 439                                         s->rfreq[bt][mtfv[gs]]++;
 440                                         gs++;
 441                                 }
 442                                 /* already is: gs = ge + 1; */
 443                         }
 444                 }
 445
 446                 /*
 447                  * Recompute the tables based on the accumulated frequencies.
 448                  */
 449                 /* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See
 450                  * comment in huffman.c for details. */
 451                 for (t = 0; t < nGroups; t++)
 452                         BZ2_hbMakeCodeLengths(&(s->len[t][0]), &(s->rfreq[t][0]), alphaSize, 17 /*20*/);
 453         }
 454
 455         AssertH(nGroups < 8, 3002);
 456         AssertH(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZ_G_SIZE)), 3003);
 457
 458         /*--- Compute MTF values for the selectors. ---*/
 459         {
 460                 uint8_t pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
 461
 462                 for (i = 0; i < nGroups; i++)
 463                         pos[i] = i;
 464                 for (i = 0; i < nSelectors; i++) {
 465                         ll_i = s->selector[i];
 466                         j = 0;
 467                         tmp = pos[j];
 468                         while (ll_i != tmp) {
 469                                 j++;
 470                                 tmp2 = tmp;
 471                                 tmp = pos[j];
 472                                 pos[j] = tmp2;
 473                         };
 474                         pos[0] = tmp;
 475                         s->selectorMtf[i] = j;
 476                 }
 477         };
 478
 479         /*--- Assign actual codes for the tables. --*/
 480         for (t = 0; t < nGroups; t++) {
 481                 minLen = 32;
 482                 maxLen = 0;
 483                 for (i = 0; i < alphaSize; i++) {
 484                         if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
 485                         if (s->len[t][i] < minLen) minLen = s->len[t][i];
 486                 }
 487                 AssertH(!(maxLen > 17 /*20*/), 3004);
 488                 AssertH(!(minLen < 1), 3005);
 489                 BZ2_hbAssignCodes(&(s->code[t][0]), &(s->len[t][0]), minLen, maxLen, alphaSize);
 490         }
 491
 492         /*--- Transmit the mapping table. ---*/
 493         {
 494                 /* bbox: optimized a bit more than in bzip2 */
 495                 int inUse16 = 0;
 496                 for (i = 0; i < 16; i++) {
 497                         if (sizeof(long) <= 4) {
 498                                 inUse16 = inUse16*2 +
 499                                         ((*(uint32_t*)&(s->inUse[i * 16 + 0])
 500                                         | *(uint32_t*)&(s->inUse[i * 16 + 4])
 501                                         | *(uint32_t*)&(s->inUse[i * 16 + 8])
 502                                         | *(uint32_t*)&(s->inUse[i * 16 + 12])) != 0);
 503                         } else { /* Our CPU can do better */
 504                                 inUse16 = inUse16*2 +
 505                                         ((*(uint64_t*)&(s->inUse[i * 16 + 0])
 506                                         | *(uint64_t*)&(s->inUse[i * 16 + 8])) != 0);
 507                         }
 508                 }
 509
 510                 nBytes = s->numZ;
 511                 bsW(s, 16, inUse16);
 512
 513                 inUse16 <<= (sizeof(int)*8 - 16); /* move 15th bit into sign bit */
 514                 for (i = 0; i < 16; i++) {
 515                         if (inUse16 < 0) {
 516                                 unsigned v16 = 0;
 517                                 for (j = 0; j < 16; j++)
 518                                         v16 = v16*2 + s->inUse[i * 16 + j];
 519                                 bsW(s, 16, v16);
 520                         }
 521                         inUse16 <<= 1;
 522                 }
 523         }
 524
 525         /*--- Now the selectors. ---*/
 526         nBytes = s->numZ;
 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         nBytes = s->numZ;
 537
 538         for (t = 0; t < nGroups; t++) {
 539                 int32_t curr = s->len[t][0];
 540                 bsW(s, 5, curr);
 541                 for (i = 0; i < alphaSize; i++) {
 542                         while (curr < s->len[t][i]) { bsW(s, 2, 2); curr++; /* 10 */ };
 543                         while (curr > s->len[t][i]) { bsW(s, 2, 3); curr--; /* 11 */ };
 544                         bsW(s, 1, 0);
 545                 }
 546         }
 547
 548         /*--- And finally, the block data proper ---*/
 549         nBytes = s->numZ;
 550         selCtr = 0;
 551         gs = 0;
 552         while (1) {
 553                 if (gs >= s->nMTF)
 554                         break;
 555                 ge = gs + BZ_G_SIZE - 1;
 556                 if (ge >= s->nMTF)
 557                         ge = s->nMTF-1;
 558                 AssertH(s->selector[selCtr] < nGroups, 3006);
 559
 560 /* Costs 1300 bytes and is _slower_ (on Intel Core 2) */
 561 #if 0
 562                 if (nGroups == 6 && 50 == ge-gs+1) {
 563                         /*--- fast track the common case ---*/
 564                         uint16_t mtfv_i;
 565                         uint8_t* s_len_sel_selCtr  = &(s->len[s->selector[selCtr]][0]);
 566                         int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
 567 #define BZ_ITAH(nn) \
 568         mtfv_i = mtfv[gs+(nn)]; \
 569         bsW(s, s_len_sel_selCtr[mtfv_i], s_code_sel_selCtr[mtfv_i])
 570                         BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
 571                         BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
 572                         BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
 573                         BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
 574                         BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
 575                         BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
 576                         BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
 577                         BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
 578                         BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
 579                         BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
 580 #undef BZ_ITAH
 581                         gs = ge+1;
 582                 } else
 583 #endif
 584                 {
 585                         /*--- slow version which correctly handles all situations ---*/
 586                         /* code is bit bigger, but moves multiply out of the loop */
 587                         uint8_t* s_len_sel_selCtr  = &(s->len [s->selector[selCtr]][0]);
 588                         int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
 589                         while (gs <= ge) {
 590                                 bsW(s,
 591                                         s_len_sel_selCtr[mtfv[gs]],
 592                                         s_code_sel_selCtr[mtfv[gs]]
 593                                 );
 594                                 gs++;
 595                         }
 596                         /* already is: gs = ge+1; */
 597                 }
 598                 selCtr++;
 599         }
 600         AssertH(selCtr == nSelectors, 3007);
 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 /*-------------------------------------------------------------*/