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