Coverage Report

Created: 2023-09-25 06:56

/src/bzip2/compress.c
Line
Count
Source (jump to first uncovered line)
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.8 of 13 July 2019
12
   Copyright (C) 1996-2019 Julian Seward <jseward@acm.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
4.52k
{
39
4.52k
   s->bsLive = 0;
40
4.52k
   s->bsBuff = 0;
41
4.52k
}
42
43
44
/*---------------------------------------------------*/
45
static
46
void bsFinishWrite ( EState* s )
47
4.52k
{
48
12.9k
   while (s->bsLive > 0) {
49
8.45k
      s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
50
8.45k
      s->numZ++;
51
8.45k
      s->bsBuff <<= 8;
52
8.45k
      s->bsLive -= 8;
53
8.45k
   }
54
4.52k
}
55
56
57
/*---------------------------------------------------*/
58
164M
#define bsNEEDW(nz)                           \
59
164M
{                                             \
60
299M
   while (s->bsLive >= 8) {                   \
61
135M
      s->zbits[s->numZ]                       \
62
135M
         = (UChar)(s->bsBuff >> 24);          \
63
135M
      s->numZ++;                              \
64
135M
      s->bsBuff <<= 8;                        \
65
135M
      s->bsLive -= 8;                         \
66
135M
   }                                          \
67
164M
}
68
69
70
/*---------------------------------------------------*/
71
static
72
__inline__
73
void bsW ( EState* s, Int32 n, UInt32 v )
74
164M
{
75
164M
   bsNEEDW ( n );
76
164M
   s->bsBuff |= (v << (32 - s->bsLive - n));
77
164M
   s->bsLive += n;
78
164M
}
79
80
81
/*---------------------------------------------------*/
82
static
83
void bsPutUInt32 ( EState* s, UInt32 u )
84
10.7k
{
85
10.7k
   bsW ( s, 8, (u >> 24) & 0xffL );
86
10.7k
   bsW ( s, 8, (u >> 16) & 0xffL );
87
10.7k
   bsW ( s, 8, (u >>  8) & 0xffL );
88
10.7k
   bsW ( s, 8,  u        & 0xffL );
89
10.7k
}
90
91
92
/*---------------------------------------------------*/
93
static
94
void bsPutUChar ( EState* s, UChar c )
95
82.6k
{
96
82.6k
   bsW( s, 8, (UInt32)c );
97
82.6k
}
98
99
100
/*---------------------------------------------------*/
101
/*--- The back end proper                         ---*/
102
/*---------------------------------------------------*/
103
104
/*---------------------------------------------------*/
105
static
106
void makeMaps_e ( EState* s )
107
6.22k
{
108
6.22k
   Int32 i;
109
6.22k
   s->nInUse = 0;
110
1.60M
   for (i = 0; i < 256; i++)
111
1.59M
      if (s->inUse[i]) {
112
730k
         s->unseqToSeq[i] = s->nInUse;
113
730k
         s->nInUse++;
114
730k
      }
115
6.22k
}
116
117
118
/*---------------------------------------------------*/
119
static
120
void generateMTFValues ( EState* s )
121
6.22k
{
122
6.22k
   UChar   yy[256];
123
6.22k
   Int32   i, j;
124
6.22k
   Int32   zPend;
125
6.22k
   Int32   wr;
126
6.22k
   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
6.22k
   UInt32* ptr   = s->ptr;
151
6.22k
   UChar* block  = s->block;
152
6.22k
   UInt16* mtfv  = s->mtfv;
153
154
6.22k
   makeMaps_e ( s );
155
6.22k
   EOB = s->nInUse+1;
156
157
749k
   for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
158
159
6.22k
   wr = 0;
160
6.22k
   zPend = 0;
161
737k
   for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
162
163
346M
   for (i = 0; i < s->nblock; i++) {
164
346M
      UChar ll_i;
165
346M
      AssertD ( wr <= i, "generateMTFValues(1)" );
166
346M
      j = ptr[i]-1; if (j < 0) j += s->nblock;
167
346M
      ll_i = s->unseqToSeq[block[j]];
168
346M
      AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
169
170
346M
      if (yy[0] == ll_i) { 
171
212M
         zPend++;
172
212M
      } else {
173
174
133M
         if (zPend > 0) {
175
13.1M
            zPend--;
176
16.0M
            while (True) {
177
16.0M
               if (zPend & 1) {
178
2.48M
                  mtfv[wr] = BZ_RUNB; wr++; 
179
2.48M
                  s->mtfFreq[BZ_RUNB]++; 
180
13.5M
               } else {
181
13.5M
                  mtfv[wr] = BZ_RUNA; wr++; 
182
13.5M
                  s->mtfFreq[BZ_RUNA]++; 
183
13.5M
               }
184
16.0M
               if (zPend < 2) break;
185
2.91M
               zPend = (zPend - 2) / 2;
186
2.91M
            };
187
13.1M
            zPend = 0;
188
13.1M
         }
189
133M
         {
190
133M
            register UChar  rtmp;
191
133M
            register UChar* ryy_j;
192
133M
            register UChar  rll_i;
193
133M
            rtmp  = yy[1];
194
133M
            yy[1] = yy[0];
195
133M
            ryy_j = &(yy[1]);
196
133M
            rll_i = ll_i;
197
15.5G
            while ( rll_i != rtmp ) {
198
15.3G
               register UChar rtmp2;
199
15.3G
               ryy_j++;
200
15.3G
               rtmp2  = rtmp;
201
15.3G
               rtmp   = *ryy_j;
202
15.3G
               *ryy_j = rtmp2;
203
15.3G
            };
204
133M
            yy[0] = rtmp;
205
133M
            j = ryy_j - &(yy[0]);
206
133M
            mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
207
133M
         }
208
209
133M
      }
210
346M
   }
211
212
6.22k
   if (zPend > 0) {
213
2.52k
      zPend--;
214
9.40k
      while (True) {
215
9.40k
         if (zPend & 1) {
216
3.93k
            mtfv[wr] = BZ_RUNB; wr++; 
217
3.93k
            s->mtfFreq[BZ_RUNB]++; 
218
5.47k
         } else {
219
5.47k
            mtfv[wr] = BZ_RUNA; wr++; 
220
5.47k
            s->mtfFreq[BZ_RUNA]++; 
221
5.47k
         }
222
9.40k
         if (zPend < 2) break;
223
6.87k
         zPend = (zPend - 2) / 2;
224
6.87k
      };
225
2.52k
      zPend = 0;
226
2.52k
   }
227
228
6.22k
   mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
229
230
6.22k
   s->nMTF = wr;
231
6.22k
}
232
233
234
/*---------------------------------------------------*/
235
743k
#define BZ_LESSER_ICOST  0
236
7.77M
#define BZ_GREATER_ICOST 15
237
238
static
239
void sendMTFValues ( EState* s )
240
6.22k
{
241
6.22k
   Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
242
6.22k
   Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
243
6.22k
   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
6.22k
   UInt16 cost[BZ_N_GROUPS];
257
6.22k
   Int32  fave[BZ_N_GROUPS];
258
259
6.22k
   UInt16* mtfv = s->mtfv;
260
261
6.22k
   if (s->verbosity >= 3)
262
0
      VPrintf3( "      %d in block, %d after MTF & 1-2 coding, "
263
6.22k
                "%d+2 syms in use\n", 
264
6.22k
                s->nblock, s->nMTF, s->nInUse );
265
266
6.22k
   alphaSize = s->nInUse+2;
267
43.5k
   for (t = 0; t < BZ_N_GROUPS; t++)
268
4.49M
      for (v = 0; v < alphaSize; v++)
269
4.45M
         s->len[t][v] = BZ_GREATER_ICOST;
270
271
   /*--- Decide how many coding tables to use ---*/
272
6.22k
   AssertH ( s->nMTF > 0, 3001 );
273
6.22k
   if (s->nMTF < 200)  nGroups = 2; else
274
4.04k
   if (s->nMTF < 600)  nGroups = 3; else
275
3.13k
   if (s->nMTF < 1200) nGroups = 4; else
276
2.76k
   if (s->nMTF < 2400) nGroups = 5; else
277
2.42k
                       nGroups = 6;
278
279
   /*--- Generate an initial set of coding tables ---*/
280
6.22k
   { 
281
6.22k
      Int32 nPart, remF, tFreq, aFreq;
282
283
6.22k
      nPart = nGroups;
284
6.22k
      remF  = s->nMTF;
285
6.22k
      gs = 0;
286
31.0k
      while (nPart > 0) {
287
24.8k
         tFreq = remF / nPart;
288
24.8k
         ge = gs-1;
289
24.8k
         aFreq = 0;
290
773k
         while (aFreq < tFreq && ge < alphaSize-1) {
291
748k
            ge++;
292
748k
            aFreq += s->mtfFreq[ge];
293
748k
         }
294
295
24.8k
         if (ge > gs 
296
24.8k
             && nPart != nGroups && nPart != 1 
297
24.8k
             && ((nGroups-nPart) % 2 == 1)) {
298
5.12k
            aFreq -= s->mtfFreq[ge];
299
5.12k
            ge--;
300
5.12k
         }
301
302
24.8k
         if (s->verbosity >= 3)
303
0
            VPrintf5( "      initial group %d, [%d .. %d], "
304
24.8k
                      "has %d syms (%4.1f%%)\n",
305
24.8k
                      nPart, gs, ge, aFreq, 
306
24.8k
                      (100.0 * (float)aFreq) / (float)(s->nMTF) );
307
 
308
4.07M
         for (v = 0; v < alphaSize; v++)
309
4.05M
            if (v >= gs && v <= ge) 
310
743k
               s->len[nPart-1][v] = BZ_LESSER_ICOST; else
311
3.31M
               s->len[nPart-1][v] = BZ_GREATER_ICOST;
312
 
313
24.8k
         nPart--;
314
24.8k
         gs = ge+1;
315
24.8k
         remF -= aFreq;
316
24.8k
      }
317
6.22k
   }
318
319
   /*--- 
320
      Iterate up to BZ_N_ITERS times to improve the tables.
321
   ---*/
322
31.1k
   for (iter = 0; iter < BZ_N_ITERS; iter++) {
323
324
174k
      for (t = 0; t < BZ_N_GROUPS; t++) fave[t] = 0;
325
326
124k
      for (t = 0; t < nGroups; t++)
327
16.3M
         for (v = 0; v < alphaSize; v++)
328
16.2M
            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
24.9k
      if (nGroups == 6) {
335
2.31M
         for (v = 0; v < alphaSize; v++) {
336
2.30M
            s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
337
2.30M
            s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
338
2.30M
            s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
339
2.30M
   }
340
9.68k
      }
341
342
24.9k
      nSelectors = 0;
343
24.9k
      totc = 0;
344
24.9k
      gs = 0;
345
11.9M
      while (True) {
346
347
         /*--- Set group start & end marks. --*/
348
11.9M
         if (gs >= s->nMTF) break;
349
11.9M
         ge = gs + BZ_G_SIZE - 1; 
350
11.9M
         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
83.6M
         for (t = 0; t < BZ_N_GROUPS; t++) cost[t] = 0;
357
358
11.9M
         if (nGroups == 6 && 50 == ge-gs+1) {
359
            /*--- fast track the common case ---*/
360
11.8M
            register UInt32 cost01, cost23, cost45;
361
11.8M
            register UInt16 icv;
362
11.8M
            cost01 = cost23 = cost45 = 0;
363
364
11.8M
#           define BZ_ITER(nn)                \
365
591M
               icv = mtfv[gs+(nn)];           \
366
591M
               cost01 += s->len_pack[icv][0]; \
367
591M
               cost23 += s->len_pack[icv][1]; \
368
591M
               cost45 += s->len_pack[icv][2]; \
369
11.8M
370
11.8M
            BZ_ITER(0);  BZ_ITER(1);  BZ_ITER(2);  BZ_ITER(3);  BZ_ITER(4);
371
11.8M
            BZ_ITER(5);  BZ_ITER(6);  BZ_ITER(7);  BZ_ITER(8);  BZ_ITER(9);
372
11.8M
            BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
373
11.8M
            BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
374
11.8M
            BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
375
11.8M
            BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
376
11.8M
            BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
377
11.8M
            BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
378
11.8M
            BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
379
11.8M
            BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
380
381
11.8M
#           undef BZ_ITER
382
383
11.8M
            cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
384
11.8M
            cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
385
11.8M
            cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
386
387
11.8M
         } else {
388
      /*--- slow version which correctly handles all situations ---*/
389
5.65M
            for (i = gs; i <= ge; i++) { 
390
5.53M
               UInt16 icv = mtfv[i];
391
28.0M
               for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
392
5.53M
            }
393
123k
         }
394
 
395
         /*-- 
396
            Find the coding table which is best for this group,
397
            and record its identity in the selector table.
398
         --*/
399
11.9M
         bc = 999999999; bt = -1;
400
83.4M
         for (t = 0; t < nGroups; t++)
401
71.4M
            if (cost[t] < bc) { bc = cost[t]; bt = t; };
402
11.9M
         totc += bc;
403
11.9M
         fave[bt]++;
404
11.9M
         s->selector[nSelectors] = bt;
405
11.9M
         nSelectors++;
406
407
         /*-- 
408
            Increment the symbol frequencies for the selected table.
409
          --*/
410
11.9M
         if (nGroups == 6 && 50 == ge-gs+1) {
411
            /*--- fast track the common case ---*/
412
413
591M
#           define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
414
415
11.8M
            BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
416
11.8M
            BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
417
11.8M
            BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
418
11.8M
            BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
419
11.8M
            BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
420
11.8M
            BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
421
11.8M
            BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
422
11.8M
            BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
423
11.8M
            BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
424
11.8M
            BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
425
426
11.8M
#           undef BZ_ITUR
427
428
11.8M
         } else {
429
      /*--- slow version which correctly handles all situations ---*/
430
5.65M
            for (i = gs; i <= ge; i++)
431
5.53M
               s->rfreq[bt][ mtfv[i] ]++;
432
123k
         }
433
434
11.9M
         gs = ge+1;
435
11.9M
      }
436
24.9k
      if (s->verbosity >= 3) {
437
0
         VPrintf2 ( "      pass %d: size is %d, grp uses are ", 
438
0
                   iter+1, totc/8 );
439
0
         for (t = 0; t < nGroups; t++)
440
0
            VPrintf1 ( "%d ", fave[t] );
441
0
         VPrintf0 ( "\n" );
442
0
      }
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
124k
      for (t = 0; t < nGroups; t++)
450
99.2k
         BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), 
451
99.2k
                                 alphaSize, 17 /*20*/ );
452
24.9k
   }
453
454
455
6.22k
   AssertH( nGroups < 8, 3002 );
456
6.22k
   AssertH( nSelectors < 32768 &&
457
6.22k
            nSelectors <= BZ_MAX_SELECTORS,
458
6.22k
            3003 );
459
460
461
   /*--- Compute MTF values for the selectors. ---*/
462
6.22k
   {
463
6.22k
      UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
464
31.0k
      for (i = 0; i < nGroups; i++) pos[i] = i;
465
2.99M
      for (i = 0; i < nSelectors; i++) {
466
2.98M
         ll_i = s->selector[i];
467
2.98M
         j = 0;
468
2.98M
         tmp = pos[j];
469
8.34M
         while ( ll_i != tmp ) {
470
5.35M
            j++;
471
5.35M
            tmp2 = tmp;
472
5.35M
            tmp = pos[j];
473
5.35M
            pos[j] = tmp2;
474
5.35M
         };
475
2.98M
         pos[0] = tmp;
476
2.98M
         s->selectorMtf[i] = j;
477
2.98M
      }
478
6.22k
   };
479
480
   /*--- Assign actual codes for the tables. --*/
481
31.0k
   for (t = 0; t < nGroups; t++) {
482
24.8k
      minLen = 32;
483
24.8k
      maxLen = 0;
484
4.07M
      for (i = 0; i < alphaSize; i++) {
485
4.05M
         if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
486
4.05M
         if (s->len[t][i] < minLen) minLen = s->len[t][i];
487
4.05M
      }
488
24.8k
      AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
489
24.8k
      AssertH ( !(minLen < 1),  3005 );
490
24.8k
      BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), 
491
24.8k
                          minLen, maxLen, alphaSize );
492
24.8k
   }
493
494
   /*--- Transmit the mapping table. ---*/
495
6.22k
   { 
496
6.22k
      Bool inUse16[16];
497
105k
      for (i = 0; i < 16; i++) {
498
99.6k
          inUse16[i] = False;
499
1.69M
          for (j = 0; j < 16; j++)
500
1.59M
             if (s->inUse[i * 16 + j]) inUse16[i] = True;
501
99.6k
      }
502
     
503
6.22k
      nBytes = s->numZ;
504
105k
      for (i = 0; i < 16; i++)
505
99.6k
         if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
506
507
105k
      for (i = 0; i < 16; i++)
508
99.6k
         if (inUse16[i])
509
1.17M
            for (j = 0; j < 16; j++) {
510
1.10M
               if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
511
1.10M
            }
512
513
6.22k
      if (s->verbosity >= 3) 
514
0
         VPrintf1( "      bytes: mapping %d, ", s->numZ-nBytes );
515
6.22k
   }
516
517
   /*--- Now the selectors. ---*/
518
6.22k
   nBytes = s->numZ;
519
6.22k
   bsW ( s, 3, nGroups );
520
6.22k
   bsW ( s, 15, nSelectors );
521
2.99M
   for (i = 0; i < nSelectors; i++) { 
522
8.34M
      for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
523
2.98M
      bsW(s,1,0);
524
2.98M
   }
525
6.22k
   if (s->verbosity >= 3)
526
0
      VPrintf1( "selectors %d, ", s->numZ-nBytes );
527
528
   /*--- Now the coding tables. ---*/
529
6.22k
   nBytes = s->numZ;
530
531
31.0k
   for (t = 0; t < nGroups; t++) {
532
24.8k
      Int32 curr = s->len[t][0];
533
24.8k
      bsW ( s, 5, curr );
534
4.07M
      for (i = 0; i < alphaSize; i++) {
535
4.90M
         while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
536
4.81M
         while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
537
4.05M
         bsW ( s, 1, 0 );
538
4.05M
      }
539
24.8k
   }
540
541
6.22k
   if (s->verbosity >= 3)
542
0
      VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
543
544
   /*--- And finally, the block data proper ---*/
545
6.22k
   nBytes = s->numZ;
546
6.22k
   selCtr = 0;
547
6.22k
   gs = 0;
548
2.99M
   while (True) {
549
2.99M
      if (gs >= s->nMTF) break;
550
2.98M
      ge = gs + BZ_G_SIZE - 1; 
551
2.98M
      if (ge >= s->nMTF) ge = s->nMTF-1;
552
2.98M
      AssertH ( s->selector[selCtr] < nGroups, 3006 );
553
554
2.98M
      if (nGroups == 6 && 50 == ge-gs+1) {
555
            /*--- fast track the common case ---*/
556
2.95M
            UInt16 mtfv_i;
557
2.95M
            UChar* s_len_sel_selCtr 
558
2.95M
               = &(s->len[s->selector[selCtr]][0]);
559
2.95M
            Int32* s_code_sel_selCtr
560
2.95M
               = &(s->code[s->selector[selCtr]][0]);
561
562
2.95M
#           define BZ_ITAH(nn)                      \
563
147M
               mtfv_i = mtfv[gs+(nn)];              \
564
147M
               bsW ( s,                             \
565
147M
                     s_len_sel_selCtr[mtfv_i],      \
566
147M
                     s_code_sel_selCtr[mtfv_i] )
567
568
2.95M
            BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
569
2.95M
            BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
570
2.95M
            BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
571
2.95M
            BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
572
2.95M
            BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
573
2.95M
            BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
574
2.95M
            BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
575
2.95M
            BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
576
2.95M
            BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
577
2.95M
            BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
578
579
2.95M
#           undef BZ_ITAH
580
581
2.95M
      } else {
582
   /*--- slow version which correctly handles all situations ---*/
583
1.41M
         for (i = gs; i <= ge; i++) {
584
1.38M
            bsW ( s, 
585
1.38M
                  s->len  [s->selector[selCtr]] [mtfv[i]],
586
1.38M
                  s->code [s->selector[selCtr]] [mtfv[i]] );
587
1.38M
         }
588
30.8k
      }
589
590
591
2.98M
      gs = ge+1;
592
2.98M
      selCtr++;
593
2.98M
   }
594
6.22k
   AssertH( selCtr == nSelectors, 3007 );
595
596
6.22k
   if (s->verbosity >= 3)
597
0
      VPrintf1( "codes %d\n", s->numZ-nBytes );
598
6.22k
}
599
600
601
/*---------------------------------------------------*/
602
void BZ2_compressBlock ( EState* s, Bool is_last_block )
603
6.22k
{
604
6.22k
   if (s->nblock > 0) {
605
606
6.22k
      BZ_FINALISE_CRC ( s->blockCRC );
607
6.22k
      s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
608
6.22k
      s->combinedCRC ^= s->blockCRC;
609
6.22k
      if (s->blockNo > 1) s->numZ = 0;
610
611
6.22k
      if (s->verbosity >= 2)
612
0
         VPrintf4( "    block %d: crc = 0x%08x, "
613
6.22k
                   "combined CRC = 0x%08x, size = %d\n",
614
6.22k
                   s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
615
616
6.22k
      BZ2_blockSort ( s );
617
6.22k
   }
618
619
6.22k
   s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
620
621
   /*-- If this is the first block, create the stream header. --*/
622
6.22k
   if (s->blockNo == 1) {
623
4.52k
      BZ2_bsInitWrite ( s );
624
4.52k
      bsPutUChar ( s, BZ_HDR_B );
625
4.52k
      bsPutUChar ( s, BZ_HDR_Z );
626
4.52k
      bsPutUChar ( s, BZ_HDR_h );
627
4.52k
      bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
628
4.52k
   }
629
630
6.22k
   if (s->nblock > 0) {
631
632
6.22k
      bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
633
6.22k
      bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
634
6.22k
      bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
635
636
      /*-- Now the block's CRC, so it is in a known place. --*/
637
6.22k
      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
6.22k
      bsW(s,1,0);
649
650
6.22k
      bsW ( s, 24, s->origPtr );
651
6.22k
      generateMTFValues ( s );
652
6.22k
      sendMTFValues ( s );
653
6.22k
   }
654
655
656
   /*-- If this is the last block, add the stream trailer. --*/
657
6.22k
   if (is_last_block) {
658
659
4.52k
      bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
660
4.52k
      bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
661
4.52k
      bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
662
4.52k
      bsPutUInt32 ( s, s->combinedCRC );
663
4.52k
      if (s->verbosity >= 2)
664
0
         VPrintf1( "    final combined CRC = 0x%08x\n   ", s->combinedCRC );
665
4.52k
      bsFinishWrite ( s );
666
4.52k
   }
667
6.22k
}
668
669
670
/*-------------------------------------------------------------*/
671
/*--- end                                        compress.c ---*/
672
/*-------------------------------------------------------------*/