Fix kldstat option.
[dragonfly.git] / contrib / bzip2-1.0 / compress.c
1
2 /*-------------------------------------------------------------*/
3 /*--- Compression machinery (not incl block sorting)        ---*/
4 /*---                                            compress.c ---*/
5 /*-------------------------------------------------------------*/
6
7 /*--
8   This file is a part of bzip2 and/or libbzip2, a program and
9   library for lossless, block-sorting data compression.
10
11   Copyright (C) 1996-2005 Julian R Seward.  All rights reserved.
12
13   Redistribution and use in source and binary forms, with or without
14   modification, are permitted provided that the following conditions
15   are met:
16
17   1. Redistributions of source code must retain the above copyright
18      notice, this list of conditions and the following disclaimer.
19
20   2. The origin of this software must not be misrepresented; you must 
21      not claim that you wrote the original software.  If you use this 
22      software in a product, an acknowledgment in the product 
23      documentation would be appreciated but is not required.
24
25   3. Altered source versions must be plainly marked as such, and must
26      not be misrepresented as being the original software.
27
28   4. The name of the author may not be used to endorse or promote 
29      products derived from this software without specific prior written 
30      permission.
31
32   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
33   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
34   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
36   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
37   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
38   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
39   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
40   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
41   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
42   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43
44   Julian Seward, Cambridge, UK.
45   jseward@bzip.org
46   bzip2/libbzip2 version 1.0 of 21 March 2000
47
48   This program is based on (at least) the work of:
49      Mike Burrows
50      David Wheeler
51      Peter Fenwick
52      Alistair Moffat
53      Radford Neal
54      Ian H. Witten
55      Robert Sedgewick
56      Jon L. Bentley
57
58   For more information on these sources, see the manual.
59 --*/
60
61 /*--
62    CHANGES
63    ~~~~~~~
64    0.9.0 -- original version.
65
66    0.9.0a/b -- no changes in this file.
67
68    0.9.0c
69       * changed setting of nGroups in sendMTFValues() so as to 
70         do a bit better on small files
71 --*/
72
73 #include "bzlib_private.h"
74
75
76 /*---------------------------------------------------*/
77 /*--- Bit stream I/O                              ---*/
78 /*---------------------------------------------------*/
79
80 /*---------------------------------------------------*/
81 void BZ2_bsInitWrite ( EState* s )
82 {
83    s->bsLive = 0;
84    s->bsBuff = 0;
85 }
86
87
88 /*---------------------------------------------------*/
89 static
90 void bsFinishWrite ( EState* s )
91 {
92    while (s->bsLive > 0) {
93       s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
94       s->numZ++;
95       s->bsBuff <<= 8;
96       s->bsLive -= 8;
97    }
98 }
99
100
101 /*---------------------------------------------------*/
102 #define bsNEEDW(nz)                           \
103 {                                             \
104    while (s->bsLive >= 8) {                   \
105       s->zbits[s->numZ]                       \
106          = (UChar)(s->bsBuff >> 24);          \
107       s->numZ++;                              \
108       s->bsBuff <<= 8;                        \
109       s->bsLive -= 8;                         \
110    }                                          \
111 }
112
113
114 /*---------------------------------------------------*/
115 static
116 __inline__
117 void bsW ( EState* s, Int32 n, UInt32 v )
118 {
119    bsNEEDW ( n );
120    s->bsBuff |= (v << (32 - s->bsLive - n));
121    s->bsLive += n;
122 }
123
124
125 /*---------------------------------------------------*/
126 static
127 void bsPutUInt32 ( EState* s, UInt32 u )
128 {
129    bsW ( s, 8, (u >> 24) & 0xffL );
130    bsW ( s, 8, (u >> 16) & 0xffL );
131    bsW ( s, 8, (u >>  8) & 0xffL );
132    bsW ( s, 8,  u        & 0xffL );
133 }
134
135
136 /*---------------------------------------------------*/
137 static
138 void bsPutUChar ( EState* s, UChar c )
139 {
140    bsW( s, 8, (UInt32)c );
141 }
142
143
144 /*---------------------------------------------------*/
145 /*--- The back end proper                         ---*/
146 /*---------------------------------------------------*/
147
148 /*---------------------------------------------------*/
149 static
150 void makeMaps_e ( EState* s )
151 {
152    Int32 i;
153    s->nInUse = 0;
154    for (i = 0; i < 256; i++)
155       if (s->inUse[i]) {
156          s->unseqToSeq[i] = s->nInUse;
157          s->nInUse++;
158       }
159 }
160
161
162 /*---------------------------------------------------*/
163 static
164 void generateMTFValues ( EState* s )
165 {
166    UChar   yy[256];
167    Int32   i, j;
168    Int32   zPend;
169    Int32   wr;
170    Int32   EOB;
171
172    /* 
173       After sorting (eg, here),
174          s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
175          and
176          ((UChar*)s->arr2) [ 0 .. s->nblock-1 ] 
177          holds the original block data.
178
179       The first thing to do is generate the MTF values,
180       and put them in
181          ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
182       Because there are strictly fewer or equal MTF values
183       than block values, ptr values in this area are overwritten
184       with MTF values only when they are no longer needed.
185
186       The final compressed bitstream is generated into the
187       area starting at
188          (UChar*) (&((UChar*)s->arr2)[s->nblock])
189
190       These storage aliases are set up in bzCompressInit(),
191       except for the last one, which is arranged in 
192       compressBlock().
193    */
194    UInt32* ptr   = s->ptr;
195    UChar* block  = s->block;
196    UInt16* mtfv  = s->mtfv;
197
198    makeMaps_e ( s );
199    EOB = s->nInUse+1;
200
201    for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
202
203    wr = 0;
204    zPend = 0;
205    for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
206
207    for (i = 0; i < s->nblock; i++) {
208       UChar ll_i;
209       AssertD ( wr <= i, "generateMTFValues(1)" );
210       j = ptr[i]-1; if (j < 0) j += s->nblock;
211       ll_i = s->unseqToSeq[block[j]];
212       AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
213
214       if (yy[0] == ll_i) { 
215          zPend++;
216       } else {
217
218          if (zPend > 0) {
219             zPend--;
220             while (True) {
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) break;
229                zPend = (zPend - 2) / 2;
230             };
231             zPend = 0;
232          }
233          {
234             register UChar  rtmp;
235             register UChar* ryy_j;
236             register UChar  rll_i;
237             rtmp  = yy[1];
238             yy[1] = yy[0];
239             ryy_j = &(yy[1]);
240             rll_i = ll_i;
241             while ( rll_i != rtmp ) {
242                register UChar rtmp2;
243                ryy_j++;
244                rtmp2  = rtmp;
245                rtmp   = *ryy_j;
246                *ryy_j = rtmp2;
247             };
248             yy[0] = rtmp;
249             j = ryy_j - &(yy[0]);
250             mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
251          }
252
253       }
254    }
255
256    if (zPend > 0) {
257       zPend--;
258       while (True) {
259          if (zPend & 1) {
260             mtfv[wr] = BZ_RUNB; wr++; 
261             s->mtfFreq[BZ_RUNB]++; 
262          } else {
263             mtfv[wr] = BZ_RUNA; wr++; 
264             s->mtfFreq[BZ_RUNA]++; 
265          }
266          if (zPend < 2) break;
267          zPend = (zPend - 2) / 2;
268       };
269       zPend = 0;
270    }
271
272    mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
273
274    s->nMTF = wr;
275 }
276
277
278 /*---------------------------------------------------*/
279 #define BZ_LESSER_ICOST  0
280 #define BZ_GREATER_ICOST 15
281
282 static
283 void sendMTFValues ( EState* s )
284 {
285    Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
286    Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
287    Int32 nGroups, nBytes;
288
289    /*--
290    UChar  len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
291    is a global since the decoder also needs it.
292
293    Int32  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
294    Int32  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
295    are also globals only used in this proc.
296    Made global to keep stack frame size small.
297    --*/
298
299
300    UInt16 cost[BZ_N_GROUPS];
301    Int32  fave[BZ_N_GROUPS];
302
303    UInt16* mtfv = s->mtfv;
304
305    if (s->verbosity >= 3)
306       VPrintf3( "      %d in block, %d after MTF & 1-2 coding, "
307                 "%d+2 syms in use\n", 
308                 s->nblock, s->nMTF, s->nInUse );
309
310    alphaSize = s->nInUse+2;
311    for (t = 0; t < BZ_N_GROUPS; t++)
312       for (v = 0; v < alphaSize; v++)
313          s->len[t][v] = BZ_GREATER_ICOST;
314
315    /*--- Decide how many coding tables to use ---*/
316    AssertH ( s->nMTF > 0, 3001 );
317    if (s->nMTF < 200)  nGroups = 2; else
318    if (s->nMTF < 600)  nGroups = 3; else
319    if (s->nMTF < 1200) nGroups = 4; else
320    if (s->nMTF < 2400) nGroups = 5; else
321                        nGroups = 6;
322
323    /*--- Generate an initial set of coding tables ---*/
324    { 
325       Int32 nPart, remF, tFreq, aFreq;
326
327       nPart = nGroups;
328       remF  = s->nMTF;
329       gs = 0;
330       while (nPart > 0) {
331          tFreq = remF / nPart;
332          ge = gs-1;
333          aFreq = 0;
334          while (aFreq < tFreq && ge < alphaSize-1) {
335             ge++;
336             aFreq += s->mtfFreq[ge];
337          }
338
339          if (ge > gs 
340              && nPart != nGroups && nPart != 1 
341              && ((nGroups-nPart) % 2 == 1)) {
342             aFreq -= s->mtfFreq[ge];
343             ge--;
344          }
345
346          if (s->verbosity >= 3)
347             VPrintf5( "      initial group %d, [%d .. %d], "
348                       "has %d syms (%4.1f%%)\n",
349                       nPart, gs, ge, aFreq, 
350                       (100.0 * (float)aFreq) / (float)(s->nMTF) );
351  
352          for (v = 0; v < alphaSize; v++)
353             if (v >= gs && v <= ge) 
354                s->len[nPart-1][v] = BZ_LESSER_ICOST; else
355                s->len[nPart-1][v] = BZ_GREATER_ICOST;
356  
357          nPart--;
358          gs = ge+1;
359          remF -= aFreq;
360       }
361    }
362
363    /*--- 
364       Iterate up to BZ_N_ITERS times to improve the tables.
365    ---*/
366    for (iter = 0; iter < BZ_N_ITERS; iter++) {
367
368       for (t = 0; t < nGroups; t++) fave[t] = 0;
369
370       for (t = 0; t < nGroups; t++)
371          for (v = 0; v < alphaSize; v++)
372             s->rfreq[t][v] = 0;
373
374       /*---
375         Set up an auxiliary length table which is used to fast-track
376         the common case (nGroups == 6). 
377       ---*/
378       if (nGroups == 6) {
379          for (v = 0; v < alphaSize; v++) {
380             s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
381             s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
382             s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
383          }
384       }
385
386       nSelectors = 0;
387       totc = 0;
388       gs = 0;
389       while (True) {
390
391          /*--- Set group start & end marks. --*/
392          if (gs >= s->nMTF) break;
393          ge = gs + BZ_G_SIZE - 1; 
394          if (ge >= s->nMTF) ge = s->nMTF-1;
395
396          /*-- 
397             Calculate the cost of this group as coded
398             by each of the coding tables.
399          --*/
400          for (t = 0; t < nGroups; t++) cost[t] = 0;
401
402          if (nGroups == 6 && 50 == ge-gs+1) {
403             /*--- fast track the common case ---*/
404             register UInt32 cost01, cost23, cost45;
405             register UInt16 icv;
406             cost01 = cost23 = cost45 = 0;
407
408 #           define BZ_ITER(nn)                \
409                icv = mtfv[gs+(nn)];           \
410                cost01 += s->len_pack[icv][0]; \
411                cost23 += s->len_pack[icv][1]; \
412                cost45 += s->len_pack[icv][2]; \
413
414             BZ_ITER(0);  BZ_ITER(1);  BZ_ITER(2);  BZ_ITER(3);  BZ_ITER(4);
415             BZ_ITER(5);  BZ_ITER(6);  BZ_ITER(7);  BZ_ITER(8);  BZ_ITER(9);
416             BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
417             BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
418             BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
419             BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
420             BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
421             BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
422             BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
423             BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
424
425 #           undef BZ_ITER
426
427             cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
428             cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
429             cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
430
431          } else {
432             /*--- slow version which correctly handles all situations ---*/
433             for (i = gs; i <= ge; i++) { 
434                UInt16 icv = mtfv[i];
435                for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
436             }
437          }
438  
439          /*-- 
440             Find the coding table which is best for this group,
441             and record its identity in the selector table.
442          --*/
443          bc = 999999999; bt = -1;
444          for (t = 0; t < nGroups; t++)
445             if (cost[t] < bc) { bc = cost[t]; bt = t; };
446          totc += bc;
447          fave[bt]++;
448          s->selector[nSelectors] = bt;
449          nSelectors++;
450
451          /*-- 
452             Increment the symbol frequencies for the selected table.
453           --*/
454          if (nGroups == 6 && 50 == ge-gs+1) {
455             /*--- fast track the common case ---*/
456
457 #           define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
458
459             BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
460             BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
461             BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
462             BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
463             BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
464             BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
465             BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
466             BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
467             BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
468             BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
469
470 #           undef BZ_ITUR
471
472          } else {
473             /*--- slow version which correctly handles all situations ---*/
474             for (i = gs; i <= ge; i++)
475                s->rfreq[bt][ mtfv[i] ]++;
476          }
477
478          gs = ge+1;
479       }
480       if (s->verbosity >= 3) {
481          VPrintf2 ( "      pass %d: size is %d, grp uses are ", 
482                    iter+1, totc/8 );
483          for (t = 0; t < nGroups; t++)
484             VPrintf1 ( "%d ", fave[t] );
485          VPrintf0 ( "\n" );
486       }
487
488       /*--
489         Recompute the tables based on the accumulated frequencies.
490       --*/
491       /* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See 
492          comment in huffman.c for details. */
493       for (t = 0; t < nGroups; t++)
494          BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), 
495                                  alphaSize, 17 /*20*/ );
496    }
497
498
499    AssertH( nGroups < 8, 3002 );
500    AssertH( nSelectors < 32768 &&
501             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
502             3003 );
503
504
505    /*--- Compute MTF values for the selectors. ---*/
506    {
507       UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
508       for (i = 0; i < nGroups; i++) pos[i] = i;
509       for (i = 0; i < nSelectors; i++) {
510          ll_i = s->selector[i];
511          j = 0;
512          tmp = pos[j];
513          while ( ll_i != tmp ) {
514             j++;
515             tmp2 = tmp;
516             tmp = pos[j];
517             pos[j] = tmp2;
518          };
519          pos[0] = tmp;
520          s->selectorMtf[i] = j;
521       }
522    };
523
524    /*--- Assign actual codes for the tables. --*/
525    for (t = 0; t < nGroups; t++) {
526       minLen = 32;
527       maxLen = 0;
528       for (i = 0; i < alphaSize; i++) {
529          if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
530          if (s->len[t][i] < minLen) minLen = s->len[t][i];
531       }
532       AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
533       AssertH ( !(minLen < 1),  3005 );
534       BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), 
535                           minLen, maxLen, alphaSize );
536    }
537
538    /*--- Transmit the mapping table. ---*/
539    { 
540       Bool inUse16[16];
541       for (i = 0; i < 16; i++) {
542           inUse16[i] = False;
543           for (j = 0; j < 16; j++)
544              if (s->inUse[i * 16 + j]) inUse16[i] = True;
545       }
546      
547       nBytes = s->numZ;
548       for (i = 0; i < 16; i++)
549          if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
550
551       for (i = 0; i < 16; i++)
552          if (inUse16[i])
553             for (j = 0; j < 16; j++) {
554                if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
555             }
556
557       if (s->verbosity >= 3) 
558          VPrintf1( "      bytes: mapping %d, ", s->numZ-nBytes );
559    }
560
561    /*--- Now the selectors. ---*/
562    nBytes = s->numZ;
563    bsW ( s, 3, nGroups );
564    bsW ( s, 15, nSelectors );
565    for (i = 0; i < nSelectors; i++) { 
566       for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
567       bsW(s,1,0);
568    }
569    if (s->verbosity >= 3)
570       VPrintf1( "selectors %d, ", s->numZ-nBytes );
571
572    /*--- Now the coding tables. ---*/
573    nBytes = s->numZ;
574
575    for (t = 0; t < nGroups; t++) {
576       Int32 curr = s->len[t][0];
577       bsW ( s, 5, curr );
578       for (i = 0; i < alphaSize; i++) {
579          while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
580          while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
581          bsW ( s, 1, 0 );
582       }
583    }
584
585    if (s->verbosity >= 3)
586       VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
587
588    /*--- And finally, the block data proper ---*/
589    nBytes = s->numZ;
590    selCtr = 0;
591    gs = 0;
592    while (True) {
593       if (gs >= s->nMTF) break;
594       ge = gs + BZ_G_SIZE - 1; 
595       if (ge >= s->nMTF) ge = s->nMTF-1;
596       AssertH ( s->selector[selCtr] < nGroups, 3006 );
597
598       if (nGroups == 6 && 50 == ge-gs+1) {
599             /*--- fast track the common case ---*/
600             UInt16 mtfv_i;
601             UChar* s_len_sel_selCtr 
602                = &(s->len[s->selector[selCtr]][0]);
603             Int32* s_code_sel_selCtr
604                = &(s->code[s->selector[selCtr]][0]);
605
606 #           define BZ_ITAH(nn)                      \
607                mtfv_i = mtfv[gs+(nn)];              \
608                bsW ( s,                             \
609                      s_len_sel_selCtr[mtfv_i],      \
610                      s_code_sel_selCtr[mtfv_i] )
611
612             BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
613             BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
614             BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
615             BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
616             BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
617             BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
618             BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
619             BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
620             BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
621             BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
622
623 #           undef BZ_ITAH
624
625       } else {
626          /*--- slow version which correctly handles all situations ---*/
627          for (i = gs; i <= ge; i++) {
628             bsW ( s, 
629                   s->len  [s->selector[selCtr]] [mtfv[i]],
630                   s->code [s->selector[selCtr]] [mtfv[i]] );
631          }
632       }
633
634
635       gs = ge+1;
636       selCtr++;
637    }
638    AssertH( selCtr == nSelectors, 3007 );
639
640    if (s->verbosity >= 3)
641       VPrintf1( "codes %d\n", s->numZ-nBytes );
642 }
643
644
645 /*---------------------------------------------------*/
646 void BZ2_compressBlock ( EState* s, Bool is_last_block )
647 {
648    if (s->nblock > 0) {
649
650       BZ_FINALISE_CRC ( s->blockCRC );
651       s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
652       s->combinedCRC ^= s->blockCRC;
653       if (s->blockNo > 1) s->numZ = 0;
654
655       if (s->verbosity >= 2)
656          VPrintf4( "    block %d: crc = 0x%08x, "
657                    "combined CRC = 0x%08x, size = %d\n",
658                    s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
659
660       BZ2_blockSort ( s );
661    }
662
663    s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
664
665    /*-- If this is the first block, create the stream header. --*/
666    if (s->blockNo == 1) {
667       BZ2_bsInitWrite ( s );
668       bsPutUChar ( s, BZ_HDR_B );
669       bsPutUChar ( s, BZ_HDR_Z );
670       bsPutUChar ( s, BZ_HDR_h );
671       bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
672    }
673
674    if (s->nblock > 0) {
675
676       bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
677       bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
678       bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
679
680       /*-- Now the block's CRC, so it is in a known place. --*/
681       bsPutUInt32 ( s, s->blockCRC );
682
683       /*-- 
684          Now a single bit indicating (non-)randomisation. 
685          As of version 0.9.5, we use a better sorting algorithm
686          which makes randomisation unnecessary.  So always set
687          the randomised bit to 'no'.  Of course, the decoder
688          still needs to be able to handle randomised blocks
689          so as to maintain backwards compatibility with
690          older versions of bzip2.
691       --*/
692       bsW(s,1,0);
693
694       bsW ( s, 24, s->origPtr );
695       generateMTFValues ( s );
696       sendMTFValues ( s );
697    }
698
699
700    /*-- If this is the last block, add the stream trailer. --*/
701    if (is_last_block) {
702
703       bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
704       bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
705       bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
706       bsPutUInt32 ( s, s->combinedCRC );
707       if (s->verbosity >= 2)
708          VPrintf1( "    final combined CRC = 0x%08x\n   ", s->combinedCRC );
709       bsFinishWrite ( s );
710    }
711 }
712
713
714 /*-------------------------------------------------------------*/
715 /*--- end                                        compress.c ---*/
716 /*-------------------------------------------------------------*/