4bd364ee3c3336f061d383c635b288be01b2e5e4
[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 = (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 /*-------------------------------------------------------------*/