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