compress.c

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