bzip2: eliminate some divisions
[people/mcb30/busybox.git] / 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
219         if (zPend > 0) {
220                 zPend--;
221                 while (1) {
222                         if (zPend & 1) {
223                                 mtfv[wr] = BZ_RUNB;
224                                 wr++;
225                                 s->mtfFreq[BZ_RUNB]++;
226                         } else {
227                                 mtfv[wr] = BZ_RUNA;
228                                 wr++;
229                                 s->mtfFreq[BZ_RUNA]++;
230                         }
231                         if (zPend < 2)
232                                 break;
233                         zPend = (uint32_t)(zPend - 2) / 2;
234                         /* bbox: unsigned div is easier */
235                 };
236                 zPend = 0;
237         }
238
239         mtfv[wr] = EOB;
240         wr++;
241         s->mtfFreq[EOB]++;
242
243         s->nMTF = wr;
244 }
245
246
247 /*---------------------------------------------------*/
248 #define BZ_LESSER_ICOST  0
249 #define BZ_GREATER_ICOST 15
250
251 static NOINLINE
252 void sendMTFValues(EState* s)
253 {
254         int32_t v, t, i, j, gs, ge, totc, bt, bc, iter;
255         int32_t nSelectors, alphaSize, minLen, maxLen, selCtr;
256         int32_t nGroups, nBytes;
257
258         /*
259          * uint8_t len[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
260          * is a global since the decoder also needs it.
261          *
262          * int32_t  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
263          * int32_t  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
264          * are also globals only used in this proc.
265          * Made global to keep stack frame size small.
266          */
267
268         uint16_t cost[BZ_N_GROUPS];
269         int32_t  fave[BZ_N_GROUPS];
270
271         uint16_t* mtfv = s->mtfv;
272
273         alphaSize = s->nInUse+2;
274         for (t = 0; t < BZ_N_GROUPS; t++)
275                 for (v = 0; v < alphaSize; v++)
276                         s->len[t][v] = BZ_GREATER_ICOST;
277
278         /*--- Decide how many coding tables to use ---*/
279         AssertH(s->nMTF > 0, 3001);
280         if (s->nMTF < 200)  nGroups = 2; else
281         if (s->nMTF < 600)  nGroups = 3; else
282         if (s->nMTF < 1200) nGroups = 4; else
283         if (s->nMTF < 2400) nGroups = 5; else
284         nGroups = 6;
285
286         /*--- Generate an initial set of coding tables ---*/
287         {
288                 int32_t nPart, remF, tFreq, aFreq;
289
290                 nPart = nGroups;
291                 remF  = s->nMTF;
292                 gs = 0;
293                 while (nPart > 0) {
294                         tFreq = remF / nPart;
295                         ge = gs - 1;
296                         aFreq = 0;
297                         while (aFreq < tFreq && ge < alphaSize-1) {
298                                 ge++;
299                                 aFreq += s->mtfFreq[ge];
300                         }
301
302                         if (ge > gs
303                          && nPart != nGroups && nPart != 1
304                          && ((nGroups - nPart) % 2 == 1) /* bbox: can this be replaced by x & 1? */
305                         ) {
306                                 aFreq -= s->mtfFreq[ge];
307                                 ge--;
308                         }
309
310                         for (v = 0; v < alphaSize; v++)
311                                 if (v >= gs && v <= ge)
312                                         s->len[nPart-1][v] = BZ_LESSER_ICOST;
313                                 else
314                                         s->len[nPart-1][v] = BZ_GREATER_ICOST;
315
316                         nPart--;
317                         gs = ge + 1;
318                         remF -= aFreq;
319                 }
320         }
321
322         /*
323          * Iterate up to BZ_N_ITERS times to improve the tables.
324          */
325         for (iter = 0; iter < BZ_N_ITERS; iter++) {
326                 for (t = 0; t < nGroups; t++)
327                         fave[t] = 0;
328
329                 for (t = 0; t < nGroups; t++)
330                         for (v = 0; v < alphaSize; v++)
331                                 s->rfreq[t][v] = 0;
332
333 #if CONFIG_BZIP2_FEATURE_SPEED >= 5
334                 /*
335                  * Set up an auxiliary length table which is used to fast-track
336                  * the common case (nGroups == 6).
337                  */
338                 if (nGroups == 6) {
339                         for (v = 0; v < alphaSize; v++) {
340                                 s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
341                                 s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
342                                 s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
343                         }
344                 }
345 #endif
346                 nSelectors = 0;
347                 totc = 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_FEATURE_SPEED >= 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
389                         } else
390 #endif
391                         {
392                                 /*--- slow version which correctly handles all situations ---*/
393                                 for (i = gs; i <= ge; i++) {
394                                         uint16_t icv = mtfv[i];
395                                         for (t = 0; t < nGroups; t++)
396                                                 cost[t] += s->len[t][icv];
397                                 }
398                         }
399                         /*
400                          * Find the coding table which is best for this group,
401                          * and record its identity in the selector table.
402                          */
403                         /*bc = 999999999;*/
404                         /*bt = -1;*/
405                         bc = cost[0];
406                         bt = 0;
407                         for (t = 1 /*0*/; t < nGroups; t++) {
408                                 if (cost[t] < bc) {
409                                         bc = cost[t];
410                                         bt = t;
411                                 }
412                         }
413                         totc += bc;
414                         fave[bt]++;
415                         s->selector[nSelectors] = bt;
416                         nSelectors++;
417
418                         /*
419                          * Increment the symbol frequencies for the selected table.
420                          */
421 /* 1% faster compress. +800 bytes */ 
422 #if CONFIG_BZIP2_FEATURE_SPEED >= 4
423                         if (nGroups == 6 && 50 == ge-gs+1) {
424                                 /*--- fast track the common case ---*/
425 #define BZ_ITUR(nn) s->rfreq[bt][mtfv[gs + (nn)]]++
426                                 BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
427                                 BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
428                                 BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
429                                 BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
430                                 BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
431                                 BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
432                                 BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
433                                 BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
434                                 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
435                                 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
436 #undef BZ_ITUR
437                                 gs = ge + 1;
438                         } else
439 #endif
440                         {
441                                 /*--- slow version which correctly handles all situations ---*/
442                                 while (gs <= ge) {
443                                         s->rfreq[bt][mtfv[gs]]++;
444                                         gs++;
445                                 }
446                                 /* already is: gs = ge + 1; */
447                         }
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]), alphaSize, 17 /*20*/);
457         }
458
459         AssertH(nGroups < 8, 3002);
460         AssertH(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZ_G_SIZE)), 3003);
461
462         /*--- Compute MTF values for the selectors. ---*/
463         {
464                 uint8_t pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
465
466                 for (i = 0; i < nGroups; i++)
467                         pos[i] = i;
468                 for (i = 0; i < nSelectors; i++) {
469                         ll_i = s->selector[i];
470                         j = 0;
471                         tmp = pos[j];
472                         while (ll_i != tmp) {
473                                 j++;
474                                 tmp2 = tmp;
475                                 tmp = pos[j];
476                                 pos[j] = tmp2;
477                         };
478                         pos[0] = tmp;
479                         s->selectorMtf[i] = j;
480                 }
481         };
482
483         /*--- Assign actual codes for the tables. --*/
484         for (t = 0; t < nGroups; t++) {
485                 minLen = 32;
486                 maxLen = 0;
487                 for (i = 0; i < alphaSize; i++) {
488                         if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
489                         if (s->len[t][i] < minLen) minLen = s->len[t][i];
490                 }
491                 AssertH(!(maxLen > 17 /*20*/), 3004);
492                 AssertH(!(minLen < 1), 3005);
493                 BZ2_hbAssignCodes(&(s->code[t][0]), &(s->len[t][0]), minLen, maxLen, alphaSize);
494         }
495
496         /*--- Transmit the mapping table. ---*/
497         {
498                 /* bbox: optimized a bit more than in bzip2 */
499                 int inUse16 = 0;
500                 for (i = 0; i < 16; i++) {
501                         if (sizeof(long) <= 4) {
502                                 inUse16 = inUse16*2 +
503                                         ((*(uint32_t*)&(s->inUse[i * 16 + 0])
504                                         | *(uint32_t*)&(s->inUse[i * 16 + 4])
505                                         | *(uint32_t*)&(s->inUse[i * 16 + 8])
506                                         | *(uint32_t*)&(s->inUse[i * 16 + 12])) != 0);
507                         } else { /* Our CPU can do better */
508                                 inUse16 = inUse16*2 +
509                                         ((*(uint64_t*)&(s->inUse[i * 16 + 0])
510                                         | *(uint64_t*)&(s->inUse[i * 16 + 8])) != 0);
511                         }
512                 }
513
514                 nBytes = s->numZ;
515                 bsW(s, 16, inUse16);
516
517                 inUse16 <<= (sizeof(int)*8 - 16); /* move 15th bit into sign bit */
518                 for (i = 0; i < 16; i++) {
519                         if (inUse16 < 0) {
520                                 unsigned v16 = 0;
521                                 for (j = 0; j < 16; j++)
522                                         v16 = v16*2 + s->inUse[i * 16 + j];
523                                 bsW(s, 16, v16);
524                         }
525                         inUse16 <<= 1;
526                 }
527         }
528
529         /*--- Now the selectors. ---*/
530         nBytes = s->numZ;
531         bsW(s, 3, nGroups);
532         bsW(s, 15, nSelectors);
533         for (i = 0; i < nSelectors; i++) {
534                 for (j = 0; j < s->selectorMtf[i]; j++)
535                         bsW(s, 1, 1);
536                 bsW(s, 1, 0);
537         }
538
539         /*--- Now the coding tables. ---*/
540         nBytes = s->numZ;
541
542         for (t = 0; t < nGroups; t++) {
543                 int32_t curr = s->len[t][0];
544                 bsW(s, 5, curr);
545                 for (i = 0; i < alphaSize; i++) {
546                         while (curr < s->len[t][i]) { bsW(s, 2, 2); curr++; /* 10 */ };
547                         while (curr > s->len[t][i]) { bsW(s, 2, 3); curr--; /* 11 */ };
548                         bsW(s, 1, 0);
549                 }
550         }
551
552         /*--- And finally, the block data proper ---*/
553         nBytes = s->numZ;
554         selCtr = 0;
555         gs = 0;
556         while (1) {
557                 if (gs >= s->nMTF)
558                         break;
559                 ge = gs + BZ_G_SIZE - 1;
560                 if (ge >= s->nMTF)
561                         ge = s->nMTF-1;
562                 AssertH(s->selector[selCtr] < nGroups, 3006);
563
564 /* Costs 1300 bytes and is _slower_ (on Intel Core 2) */
565 #if 0
566                 if (nGroups == 6 && 50 == ge-gs+1) {
567                         /*--- fast track the common case ---*/
568                         uint16_t mtfv_i;
569                         uint8_t* s_len_sel_selCtr  = &(s->len[s->selector[selCtr]][0]);
570                         int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
571 #define BZ_ITAH(nn) \
572         mtfv_i = mtfv[gs+(nn)]; \
573         bsW(s, s_len_sel_selCtr[mtfv_i], s_code_sel_selCtr[mtfv_i])
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 #undef BZ_ITAH
585                         gs = ge+1;
586                 } else
587 #endif
588                 {
589                         /*--- slow version which correctly handles all situations ---*/
590                         /* code is bit bigger, but moves multiply out of the loop */
591                         uint8_t* s_len_sel_selCtr  = &(s->len [s->selector[selCtr]][0]);
592                         int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
593                         while (gs <= ge) {
594                                 bsW(s,
595                                         s_len_sel_selCtr[mtfv[gs]],
596                                         s_code_sel_selCtr[mtfv[gs]]
597                                 );
598                                 gs++;
599                         }
600                         /* already is: gs = ge+1; */
601                 }
602                 selCtr++;
603         }
604         AssertH(selCtr == nSelectors, 3007);
605 }
606
607
608 /*---------------------------------------------------*/
609 static
610 void BZ2_compressBlock(EState* s, int is_last_block)
611 {
612         if (s->nblock > 0) {
613                 BZ_FINALISE_CRC(s->blockCRC);
614                 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
615                 s->combinedCRC ^= s->blockCRC;
616                 if (s->blockNo > 1)
617                         s->numZ = 0;
618
619                 BZ2_blockSort(s);
620         }
621
622         s->zbits = &((uint8_t*)s->arr2)[s->nblock];
623
624         /*-- If this is the first block, create the stream header. --*/
625         if (s->blockNo == 1) {
626                 BZ2_bsInitWrite(s);
627                 /*bsPutU8(s, BZ_HDR_B);*/
628                 /*bsPutU8(s, BZ_HDR_Z);*/
629                 /*bsPutU8(s, BZ_HDR_h);*/
630                 /*bsPutU8(s, BZ_HDR_0 + s->blockSize100k);*/
631                 bsPutU32(s, BZ_HDR_BZh0 + s->blockSize100k);
632         }
633
634         if (s->nblock > 0) {
635                 /*bsPutU8(s, 0x31);*/
636                 /*bsPutU8(s, 0x41);*/
637                 /*bsPutU8(s, 0x59);*/
638                 /*bsPutU8(s, 0x26);*/
639                 bsPutU32(s, 0x31415926);
640                 /*bsPutU8(s, 0x53);*/
641                 /*bsPutU8(s, 0x59);*/
642                 bsPutU16(s, 0x5359);
643
644                 /*-- Now the block's CRC, so it is in a known place. --*/
645                 bsPutU32(s, s->blockCRC);
646
647                 /*
648                  * Now a single bit indicating (non-)randomisation.
649                  * As of version 0.9.5, we use a better sorting algorithm
650                  * which makes randomisation unnecessary.  So always set
651                  * the randomised bit to 'no'.  Of course, the decoder
652                  * still needs to be able to handle randomised blocks
653                  * so as to maintain backwards compatibility with
654                  * older versions of bzip2.
655                  */
656                 bsW(s, 1, 0);
657
658                 bsW(s, 24, s->origPtr);
659                 generateMTFValues(s);
660                 sendMTFValues(s);
661         }
662
663         /*-- If this is the last block, add the stream trailer. --*/
664         if (is_last_block) {
665                 /*bsPutU8(s, 0x17);*/
666                 /*bsPutU8(s, 0x72);*/
667                 /*bsPutU8(s, 0x45);*/
668                 /*bsPutU8(s, 0x38);*/
669                 bsPutU32(s, 0x17724538);
670                 /*bsPutU8(s, 0x50);*/
671                 /*bsPutU8(s, 0x90);*/
672                 bsPutU16(s, 0x5090);
673                 bsPutU32(s, s->combinedCRC);
674                 bsFinishWrite(s);
675         }
676 }
677
678
679 /*-------------------------------------------------------------*/
680 /*--- end                                        compress.c ---*/
681 /*-------------------------------------------------------------*/