blocksort.c

filter: Statementstmt 94.1% 404 / 429 Branchbran 81.4% 267 / 328 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 88.6% 671 / 757 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« decompress.c ↑ Summary huffman.c »
1  
2 /*-------------------------------------------------------------*/
3 /*--- Block sorting machinery ---*/
4 /*--- blocksort.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 #include "bzlib_private.h"
23  
24 /*---------------------------------------------*/
25 /*--- Fallback O(N log(N)^2) sorting ---*/
26 /*--- algorithm, for repetitive blocks ---*/
27 /*---------------------------------------------*/
28  
29 /*---------------------------------------------*/
30 static
31 __inline__
32 6520 void fallbackSimpleSort ( UInt32* fmap,
33 UInt32* eclass,
34 Int32 lo,
35 Int32 hi )
36 {
37 Int32 i, j, tmp;
38 UInt32 ec_tmp;
39  
40 6520 ▶ if (lo == hi) return;
Branch: 1 branch
BranchTrueFalseTotal
if (lo == hi) return; 251 6269 6520
41  
42 6269 ▶ if (hi - lo > 3) {
Branch: 1 branch
BranchTrueFalseTotal
if (hi - lo > 3) { 2800 3469 6269
43 11598 ▶ for ( i = hi-4; i >= lo; i-- ) {
Branch: 1 branch
BranchTrueFalseTotal
for ( i = hi-4; i >= lo; i-- ) { 8798 2800 11598
44 8798 tmp = fmap[i];
45 8798 ec_tmp = eclass[tmp];
46 10995 ▶ for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
Branch: 2 branches
BranchTrueFalseTotal
for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 ) 9131 1864 10995
for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 ) 2197 6934 9131
47 2197 fmap[j-4] = fmap[j];
48 8798 fmap[j-4] = tmp;
49 }
50 }
51  
52 25095 ▶ for ( i = hi-1; i >= lo; i-- ) {
Branch: 1 branch
BranchTrueFalseTotal
for ( i = hi-1; i >= lo; i-- ) { 18826 6269 25095
53 18826 tmp = fmap[i];
54 18826 ec_tmp = eclass[tmp];
55 27322 ▶ for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
Branch: 2 branches
BranchTrueFalseTotal
for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ ) 25569 1753 27322
for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ ) 8496 17073 25569
56 8496 fmap[j-1] = fmap[j];
57 18826 fmap[j-1] = tmp;
58 }
59 }
60  
61  
62 /*---------------------------------------------*/
63 #define fswap(zz1, zz2) \
64 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
65  
66 #define fvswap(zzp1, zzp2, zzn) \
67 { \
68 Int32 yyp1 = (zzp1); \
69 Int32 yyp2 = (zzp2); \
70 Int32 yyn = (zzn); \
71 while (yyn > 0) { \
72 fswap(fmap[yyp1], fmap[yyp2]); \
73 yyp1++; yyp2++; yyn--; \
74 } \
75 }
76  
77  
78 #define fmin(a,b) ((a) < (b)) ? (a) : (b)
79  
80 #define fpush(lz,hz) { stackLo[sp] = lz; \
81 stackHi[sp] = hz; \
82 sp++; }
83  
84 #define fpop(lz,hz) { sp--; \
85 lz = stackLo[sp]; \
86 hz = stackHi[sp]; }
87  
88 #define FALLBACK_QSORT_SMALL_THRESH 10
89 #define FALLBACK_QSORT_STACK_SIZE 100
90  
91  
92 static
93 1649 void fallbackQSort3 ( UInt32* fmap,
94 UInt32* eclass,
95 Int32 loSt,
96 Int32 hiSt )
97 {
98 Int32 unLo, unHi, ltLo, gtHi, n, m;
99 Int32 sp, lo, hi;
100 UInt32 med, r, r3;
101 Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];
102 Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];
103  
104 1649 r = 0;
105  
106 1649 sp = 0;
107 1649 fpush ( loSt, hiSt );
108  
109 13884 ▶ while (sp > 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (sp > 0) { 12235 1649 13884
110  
111 12235 ▶ AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 );
Branch: 1 branch
BranchTrueFalseTotal
AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 ); 0 12235 12235
112  
113 12235 fpop ( lo, hi );
114 12235 ▶ if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
Branch: 1 branch
BranchTrueFalseTotal
if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) { 6520 5715 12235
115 6520 fallbackSimpleSort ( fmap, eclass, lo, hi );
116 6520 continue;
117 }
118  
119 /* Random partitioning. Median of 3 sometimes fails to
120 avoid bad cases. Median of 9 seems to help but
121 looks rather expensive. This too seems to work but
122 is cheaper. Guidance for the magic constants
123 7621 and 32768 is taken from Sedgewick's algorithms
124 book, chapter 35.
125 */
126 5715 r = ((r * 7621) + 1) % 32768;
127 5715 r3 = r % 3;
128 5715 ▶ if (r3 == 0) med = eclass[fmap[lo]]; else
Branch: 1 branch
BranchTrueFalseTotal
if (r3 == 0) med = eclass[fmap[lo]]; else 1037 4678 5715
129 4678 ▶ if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
Branch: 1 branch
BranchTrueFalseTotal
if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else 2695 1983 4678
130 1983 med = eclass[fmap[hi]];
131  
132 5715 unLo = ltLo = lo;
133 5715 unHi = gtHi = hi;
134  
135 19134 while (1) {
136 while (1) {
137 1084210 ▶ if (unLo > unHi) break;
Branch: 1 branch
BranchTrueFalseTotal
if (unLo > unHi) break; 2503 1081707 1084210
138 1081707 n = (Int32)eclass[fmap[unLo]] - (Int32)med;
139 1081707 ▶ if (n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) { 972041 109666 1081707
140 972041 fswap(fmap[unLo], fmap[ltLo]);
141 972041 ltLo++; unLo++;
142 972041 continue;
143 };
144 109666 ▶ if (n > 0) break;
Branch: 1 branch
BranchTrueFalseTotal
if (n > 0) break; 22346 87320 109666
145 87320 unLo++;
146 }
147 while (1) {
148 102688 ▶ if (unLo > unHi) break;
Branch: 1 branch
BranchTrueFalseTotal
if (unLo > unHi) break; 5715 96973 102688
149 96973 n = (Int32)eclass[fmap[unHi]] - (Int32)med;
150 96973 ▶ if (n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) { 6791 90182 96973
151 6791 fswap(fmap[unHi], fmap[gtHi]);
152 6791 gtHi--; unHi--;
153 6791 continue;
154 };
155 90182 ▶ if (n < 0) break;
Branch: 1 branch
BranchTrueFalseTotal
if (n < 0) break; 19134 71048 90182
156 71048 unHi--;
157 }
158 24849 ▶ if (unLo > unHi) break;
Branch: 1 branch
BranchTrueFalseTotal
if (unLo > unHi) break; 5715 19134 24849
159 19134 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
160 }
161  
162 AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );
163  
164 5715 ▶ if (gtHi < ltLo) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (gtHi < ltLo) continue; 422 5293 5715
165  
166 27627 ▶ n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
Branch: 1 branch
BranchTrueFalseTotal
n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n); 22334 5293 27627
167 10084 ▶ m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
Branch: 1 branch
BranchTrueFalseTotal
m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m); 4791 5293 10084
168  
169 5293 n = lo + unLo - ltLo - 1;
170 5293 m = hi - (gtHi - unHi) + 1;
171  
172 5293 ▶ if (n - lo > hi - m) {
Branch: 1 branch
BranchTrueFalseTotal
if (n - lo > hi - m) { 2001 3292 5293
173 2001 fpush ( lo, n );
174 2001 fpush ( m, hi );
175 } else {
176 3292 fpush ( m, hi );
177 3292 fpush ( lo, n );
178 }
179 }
180 1649 }
181  
182 #undef fmin
183 #undef fpush
184 #undef fpop
185 #undef fswap
186 #undef fvswap
187 #undef FALLBACK_QSORT_SMALL_THRESH
188 #undef FALLBACK_QSORT_STACK_SIZE
189  
190  
191 /*---------------------------------------------*/
192 /* Pre:
193 nblock > 0
194 eclass exists for [0 .. nblock-1]
195 ((UChar*)eclass) [0 .. nblock-1] holds block
196 ptr exists for [0 .. nblock-1]
197  
198 Post:
199 ((UChar*)eclass) [0 .. nblock-1] holds block
200 All other areas of eclass destroyed
201 fmap [0 .. nblock-1] holds sorted order
202 bhtab [ 0 .. 2+(nblock/32) ] destroyed
203 */
204  
205 #define SET_BH(zz) bhtab[(zz) >> 5] |= ((UInt32)1 << ((zz) & 31))
206 #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~((UInt32)1 << ((zz) & 31))
207 #define ISSET_BH(zz) (bhtab[(zz) >> 5] & ((UInt32)1 << ((zz) & 31)))
208 #define WORD_BH(zz) bhtab[(zz) >> 5]
209 #define UNALIGNED_BH(zz) ((zz) & 0x01f)
210  
211 static
212 20 void fallbackSort ( UInt32* fmap,
213 UInt32* eclass,
214 UInt32* bhtab,
215 Int32 nblock,
216 Int32 verb )
217 {
218 Int32 ftab[257];
219 Int32 ftabCopy[256];
220 Int32 H, i, j, k, l, r, cc, cc1;
221 Int32 nNotDone;
222 Int32 nBhtab;
223 20 UChar* eclass8 = (UChar*)eclass;
224  
225 /*--
226 Initial 1-char radix sort to generate
227 initial fmap and initial BH bits.
228 --*/
229 if (verb >= 4)
230 VPrintf0 ( " bucket sorting ...\n" );
231 5160 ▶ for (i = 0; i < 257; i++) ftab[i] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 257; i++) ftab[i] = 0; 5140 20 5160
232 75415 ▶ for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nblock; i++) ftab[eclass8[i]]++; 75395 20 75415
233 5140 ▶ for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i];
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i]; 5120 20 5140
234 5140 ▶ for (i = 1; i < 257; i++) ftab[i] += ftab[i-1];
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i < 257; i++) ftab[i] += ftab[i-1]; 5120 20 5140
235  
236 75415 ▶ for (i = 0; i < nblock; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nblock; i++) { 75395 20 75415
237 75395 j = eclass8[i];
238 75395 k = ftab[j] - 1;
239 75395 ftab[j] = k;
240 75395 fmap[k] = i;
241 }
242  
243 20 nBhtab = 2 + (nblock / 32);
244 2403 ▶ for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nBhtab; i++) bhtab[i] = 0; 2383 20 2403
245 5140 ▶ for (i = 0; i < 256; i++) SET_BH(ftab[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 256; i++) SET_BH(ftab[i]); 5120 20 5140
246  
247 /*--
248 Inductively refine the buckets. Kind-of an
249 "exponential radix sort" (!), inspired by the
250 Manber-Myers suffix array construction algorithm.
251 --*/
252  
253 /*-- set sentinel bits for block-end detection --*/
254 660 ▶ for (i = 0; i < 32; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 32; i++) { 640 20 660
255 640 SET_BH(nblock + 2*i);
256 640 CLEAR_BH(nblock + 2*i + 1);
257 }
258  
259 /*-- the log(N) loop --*/
260 20 H = 1;
261 while (1) {
262  
263 62 if (verb >= 4)
264 VPrintf1 ( " depth %6d has ", H );
265  
266 82 j = 0;
267 1054715 ▶ for (i = 0; i < nblock; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nblock; i++) { 1054633 82 1054715
268 1054633 ▶ if (ISSET_BH(i)) j = i;
Branch: 1 branch
BranchTrueFalseTotal
if (ISSET_BH(i)) j = i; 54551 1000082 1054633
269 1054633 ▶ k = fmap[i] - H; if (k < 0) k += nblock;
Branch: 1 branch
BranchTrueFalseTotal
k = fmap[i] - H; if (k < 0) k += nblock; 98418 956215 1054633
270 1054633 eclass[k] = j;
271 }
272  
273 82 nNotDone = 0;
274 82 r = -1;
275 while (1) {
276  
277 /*-- find the next non-singleton bucket --*/
278 1731 k = r + 1;
279 9249 ▶ while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
Branch: 2 branches
BranchTrueFalseTotal
while (ISSET_BH(k) && UNALIGNED_BH(k)) k++; 7958 1291 9249
while (ISSET_BH(k) && UNALIGNED_BH(k)) k++; 7518 440 7958
280 1731 ▶ if (ISSET_BH(k)) {
Branch: 1 branch
BranchTrueFalseTotal
if (ISSET_BH(k)) { 440 1291 1731
281 1753 ▶ while (WORD_BH(k) == 0xffffffff) k += 32;
Branch: 1 branch
BranchTrueFalseTotal
while (WORD_BH(k) == 0xffffffff) k += 32; 1313 440 1753
282 5539 ▶ while (ISSET_BH(k)) k++;
Branch: 1 branch
BranchTrueFalseTotal
while (ISSET_BH(k)) k++; 5099 440 5539
283 }
284 1731 l = k - 1;
285 1731 ▶ if (l >= nblock) break;
Branch: 1 branch
BranchTrueFalseTotal
if (l >= nblock) break; 82 1649 1731
286 19122 ▶ while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
Branch: 2 branches
BranchTrueFalseTotal
while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++; 18414 708 19122
while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++; 17473 941 18414
287 1649 ▶ if (!ISSET_BH(k)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!ISSET_BH(k)) { 941 708 1649
288 31253 ▶ while (WORD_BH(k) == 0x00000000) k += 32;
Branch: 1 branch
BranchTrueFalseTotal
while (WORD_BH(k) == 0x00000000) k += 32; 30312 941 31253
289 13566 ▶ while (!ISSET_BH(k)) k++;
Branch: 1 branch
BranchTrueFalseTotal
while (!ISSET_BH(k)) k++; 12625 941 13566
290 }
291 1649 r = k - 1;
292 1649 ▶ if (r >= nblock) break;
Branch: 1 branch
BranchTrueFalseTotal
if (r >= nblock) break; 0 1649 1649
293  
294 /*-- now [l, r] bracket current bucket --*/
295 1649 ▶ if (r > l) {
Branch: 1 branch
BranchTrueFalseTotal
if (r > l) { 1649 0 1649
296 1649 nNotDone += (r - l + 1);
297 1649 fallbackQSort3 ( fmap, eclass, l, r );
298  
299 /*-- scan bucket and generate header bits-- */
300 1649 cc = -1;
301 1003380 ▶ for (i = l; i <= r; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = l; i <= r; i++) { 1001731 1649 1003380
302 1001731 cc1 = eclass[fmap[i]];
303 1001731 ▶ if (cc != cc1) { SET_BH(i); cc = cc1; };
Branch: 1 branch
BranchTrueFalseTotal
if (cc != cc1) { SET_BH(i); cc = cc1; }; 28266 973465 1001731
304 }
305 }
306 }
307  
308 if (verb >= 4)
309 VPrintf1 ( "%6d unresolved strings\n", nNotDone );
310  
311 82 H *= 2;
312 82 ▶ if (H > nblock || nNotDone == 0) break;
Branch: 2 branches
BranchTrueFalseTotal
if (H > nblock || nNotDone == 0) break; 80 2 82
if (H > nblock || nNotDone == 0) break; 62 18 80
313 }
314  
315 /*--
316 Reconstruct the original block in
317 eclass8 [0 .. nblock-1], since the
318 previous phase destroyed it.
319 --*/
320 if (verb >= 4)
321 VPrintf0 ( " reconstructing block ...\n" );
322 20 j = 0;
323 75415 ▶ for (i = 0; i < nblock; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nblock; i++) { 75395 20 75415
324 77945 ▶ while (ftabCopy[j] == 0) j++;
Branch: 1 branch
BranchTrueFalseTotal
while (ftabCopy[j] == 0) j++; 2550 75395 77945
325 75395 ftabCopy[j]--;
326 75395 eclass8[fmap[i]] = (UChar)j;
327 }
328 20 ▶ AssertH ( j < 256, 1005 );
Branch: 1 branch
BranchTrueFalseTotal
AssertH ( j < 256, 1005 ); 0 20 20
329 20 }
330  
331 #undef SET_BH
332 #undef CLEAR_BH
333 #undef ISSET_BH
334 #undef WORD_BH
335 #undef UNALIGNED_BH
336  
337  
338 /*---------------------------------------------*/
339 /*--- The main, O(N^2 log(N)) sorting ---*/
340 /*--- algorithm. Faster for "normal" ---*/
341 /*--- non-repetitive blocks. ---*/
342 /*---------------------------------------------*/
343  
344 /*---------------------------------------------*/
345 static
346 __inline__
347 9070 Bool mainGtU ( UInt32 i1,
348 UInt32 i2,
349 UChar* block,
350 UInt16* quadrant,
351 UInt32 nblock,
352 Int32* budget )
353 {
354 Int32 k;
355 UChar c1, c2;
356 UInt16 s1, s2;
357  
358 AssertD ( i1 != i2, "mainGtU" );
359 /* 1 */
360 9070 c1 = block[i1]; c2 = block[i2];
361 9070 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 8835 235 9070
362 235 i1++; i2++;
363 /* 2 */
364 235 c1 = block[i1]; c2 = block[i2];
365 235 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 34 201 235
366 201 i1++; i2++;
367 /* 3 */
368 201 c1 = block[i1]; c2 = block[i2];
369 201 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 0 201 201
370 201 i1++; i2++;
371 /* 4 */
372 201 c1 = block[i1]; c2 = block[i2];
373 201 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 0 201 201
374 201 i1++; i2++;
375 /* 5 */
376 201 c1 = block[i1]; c2 = block[i2];
377 201 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 0 201 201
378 201 i1++; i2++;
379 /* 6 */
380 201 c1 = block[i1]; c2 = block[i2];
381 201 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 0 201 201
382 201 i1++; i2++;
383 /* 7 */
384 201 c1 = block[i1]; c2 = block[i2];
385 201 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 0 201 201
386 201 i1++; i2++;
387 /* 8 */
388 201 c1 = block[i1]; c2 = block[i2];
389 201 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 0 201 201
390 201 i1++; i2++;
391 /* 9 */
392 201 c1 = block[i1]; c2 = block[i2];
393 201 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 0 201 201
394 201 i1++; i2++;
395 /* 10 */
396 201 c1 = block[i1]; c2 = block[i2];
397 201 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 0 201 201
398 201 i1++; i2++;
399 /* 11 */
400 201 c1 = block[i1]; c2 = block[i2];
401 201 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 0 201 201
402 201 i1++; i2++;
403 /* 12 */
404 201 c1 = block[i1]; c2 = block[i2];
405 201 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 0 201 201
406 201 i1++; i2++;
407  
408 201 k = nblock + 8;
409  
410 do {
411 /* 1 */
412 588797 c1 = block[i1]; c2 = block[i2];
413 588797 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 16 588781 588797
414 588781 s1 = quadrant[i1]; s2 = quadrant[i2];
415 588781 ▶ if (s1 != s2) return (s1 > s2);
Branch: 1 branch
BranchTrueFalseTotal
if (s1 != s2) return (s1 > s2); 0 588781 588781
416 588781 i1++; i2++;
417 /* 2 */
418 588781 c1 = block[i1]; c2 = block[i2];
419 588781 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 17 588764 588781
420 588764 s1 = quadrant[i1]; s2 = quadrant[i2];
421 588764 ▶ if (s1 != s2) return (s1 > s2);
Branch: 1 branch
BranchTrueFalseTotal
if (s1 != s2) return (s1 > s2); 0 588764 588764
422 588764 i1++; i2++;
423 /* 3 */
424 588764 c1 = block[i1]; c2 = block[i2];
425 588764 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 16 588748 588764
426 588748 s1 = quadrant[i1]; s2 = quadrant[i2];
427 588748 ▶ if (s1 != s2) return (s1 > s2);
Branch: 1 branch
BranchTrueFalseTotal
if (s1 != s2) return (s1 > s2); 0 588748 588748
428 588748 i1++; i2++;
429 /* 4 */
430 588748 c1 = block[i1]; c2 = block[i2];
431 588748 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 16 588732 588748
432 588732 s1 = quadrant[i1]; s2 = quadrant[i2];
433 588732 ▶ if (s1 != s2) return (s1 > s2);
Branch: 1 branch
BranchTrueFalseTotal
if (s1 != s2) return (s1 > s2); 0 588732 588732
434 588732 i1++; i2++;
435 /* 5 */
436 588732 c1 = block[i1]; c2 = block[i2];
437 588732 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 16 588716 588732
438 588716 s1 = quadrant[i1]; s2 = quadrant[i2];
439 588716 ▶ if (s1 != s2) return (s1 > s2);
Branch: 1 branch
BranchTrueFalseTotal
if (s1 != s2) return (s1 > s2); 0 588716 588716
440 588716 i1++; i2++;
441 /* 6 */
442 588716 c1 = block[i1]; c2 = block[i2];
443 588716 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 16 588700 588716
444 588700 s1 = quadrant[i1]; s2 = quadrant[i2];
445 588700 ▶ if (s1 != s2) return (s1 > s2);
Branch: 1 branch
BranchTrueFalseTotal
if (s1 != s2) return (s1 > s2); 0 588700 588700
446 588700 i1++; i2++;
447 /* 7 */
448 588700 c1 = block[i1]; c2 = block[i2];
449 588700 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 16 588684 588700
450 588684 s1 = quadrant[i1]; s2 = quadrant[i2];
451 588684 ▶ if (s1 != s2) return (s1 > s2);
Branch: 1 branch
BranchTrueFalseTotal
if (s1 != s2) return (s1 > s2); 0 588684 588684
452 588684 i1++; i2++;
453 /* 8 */
454 588684 c1 = block[i1]; c2 = block[i2];
455 588684 ▶ if (c1 != c2) return (c1 > c2);
Branch: 1 branch
BranchTrueFalseTotal
if (c1 != c2) return (c1 > c2); 16 588668 588684
456 588668 s1 = quadrant[i1]; s2 = quadrant[i2];
457 588668 ▶ if (s1 != s2) return (s1 > s2);
Branch: 1 branch
BranchTrueFalseTotal
if (s1 != s2) return (s1 > s2); 0 588668 588668
458 588668 i1++; i2++;
459  
460 588668 ▶ if (i1 >= nblock) i1 -= nblock;
Branch: 1 branch
BranchTrueFalseTotal
if (i1 >= nblock) i1 -= nblock; 72 588596 588668
461 588668 ▶ if (i2 >= nblock) i2 -= nblock;
Branch: 1 branch
BranchTrueFalseTotal
if (i2 >= nblock) i2 -= nblock; 72 588596 588668
462  
463 588668 k -= 8;
464 588668 (*budget)--;
465 }
466 588668 ▶ while (k >= 0);
Branch: 1 branch
BranchTrueFalseTotal
while (k >= 0); 588596 72 588668
467  
468 72 return False;
469 }
470  
471  
472 /*---------------------------------------------*/
473 /*--
474 Knuth's increments seem to work better
475 than Incerpi-Sedgewick here. Possibly
476 because the number of elems to sort is
477 usually small, typically <= 20.
478 --*/
479 static
480 Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
481 9841, 29524, 88573, 265720,
482 797161, 2391484 };
483  
484 static
485 5832 void mainSimpleSort ( UInt32* ptr,
486 UChar* block,
487 UInt16* quadrant,
488 Int32 nblock,
489 Int32 lo,
490 Int32 hi,
491 Int32 d,
492 Int32* budget )
493 {
494 Int32 i, j, h, bigN, hp;
495 UInt32 v;
496  
497 5832 bigN = hi - lo + 1;
498 5832 ▶ if (bigN < 2) return;
Branch: 1 branch
BranchTrueFalseTotal
if (bigN < 2) return; 0 5832 5832
499  
500 5832 hp = 0;
501 11712 ▶ while (incs[hp] < bigN) hp++;
Branch: 1 branch
BranchTrueFalseTotal
while (incs[hp] < bigN) hp++; 5880 5832 11712
502 5832 hp--;
503  
504 11699 ▶ for (; hp >= 0; hp--) {
Branch: 1 branch
BranchTrueFalseTotal
for (; hp >= 0; hp--) { 5869 5830 11699
505 5869 h = incs[hp];
506  
507 5869 i = lo + h;
508 while (True) {
509  
510 /*-- copy 1 --*/
511 6182 ▶ if (i > hi) break;
Branch: 1 branch
BranchTrueFalseTotal
if (i > hi) break; 211 5971 6182
512 5971 v = ptr[i];
513 5971 j = i;
514 11979 ▶ while ( mainGtU (
Branch: 1 branch
BranchTrueFalseTotal
while ( mainGtU ( 3006 3002 6008
515 6008 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
516 ) ) {
517 3006 ptr[j] = ptr[j-h];
518 3006 j = j - h;
519 3006 ▶ if (j <= (lo + h - 1)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (j <= (lo + h - 1)) break; 2969 37 3006
520 }
521 5971 ptr[j] = v;
522 5971 i++;
523  
524 /*-- copy 2 --*/
525 5971 ▶ if (i > hi) break;
Branch: 1 branch
BranchTrueFalseTotal
if (i > hi) break; 4486 1485 5971
526 1485 v = ptr[i];
527 1485 j = i;
528 3916 ▶ while ( mainGtU (
Branch: 1 branch
BranchTrueFalseTotal
while ( mainGtU ( 1473 958 2431
529 2431 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
530 ) ) {
531 1473 ptr[j] = ptr[j-h];
532 1473 j = j - h;
533 1473 ▶ if (j <= (lo + h - 1)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (j <= (lo + h - 1)) break; 527 946 1473
534 }
535 1485 ptr[j] = v;
536 1485 i++;
537  
538 /*-- copy 3 --*/
539 1485 ▶ if (i > hi) break;
Branch: 1 branch
BranchTrueFalseTotal
if (i > hi) break; 1170 315 1485
540 315 v = ptr[i];
541 315 j = i;
542 946 ▶ while ( mainGtU (
Branch: 1 branch
BranchTrueFalseTotal
while ( mainGtU ( 415 216 631
543 631 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
544 ) ) {
545 415 ptr[j] = ptr[j-h];
546 415 j = j - h;
547 415 ▶ if (j <= (lo + h - 1)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (j <= (lo + h - 1)) break; 99 316 415
548 }
549 315 ptr[j] = v;
550 315 i++;
551  
552 315 ▶ if (*budget < 0) return;
Branch: 1 branch
BranchTrueFalseTotal
if (*budget < 0) return; 2 313 315
553 }
554 }
555 }
556  
557  
558 /*---------------------------------------------*/
559 /*--
560 The following is an implementation of
561 an elegant 3-way quicksort for strings,
562 described in a paper "Fast Algorithms for
563 Sorting and Searching Strings", by Robert
564 Sedgewick and Jon L. Bentley.
565 --*/
566  
567 #define mswap(zz1, zz2) \
568 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
569  
570 #define mvswap(zzp1, zzp2, zzn) \
571 { \
572 Int32 yyp1 = (zzp1); \
573 Int32 yyp2 = (zzp2); \
574 Int32 yyn = (zzn); \
575 while (yyn > 0) { \
576 mswap(ptr[yyp1], ptr[yyp2]); \
577 yyp1++; yyp2++; yyn--; \
578 } \
579 }
580  
581 static
582 __inline__
583 26 UChar mmed3 ( UChar a, UChar b, UChar c )
584 {
585 UChar t;
586 26 ▶ if (a > b) { t = a; a = b; b = t; };
Branch: 1 branch
BranchTrueFalseTotal
if (a > b) { t = a; a = b; b = t; }; 0 26 26
587 26 ▶ if (b > c) {
Branch: 1 branch
BranchTrueFalseTotal
if (b > c) { 0 26 26
588 0 b = c;
589 0 ▶ if (a > b) b = a;
Branch: 1 branch
BranchTrueFalseTotal
if (a > b) b = a; 0 0 0
590 }
591 26 return b;
592 }
593  
594 #define mmin(a,b) ((a) < (b)) ? (a) : (b)
595  
596 #define mpush(lz,hz,dz) { stackLo[sp] = lz; \
597 stackHi[sp] = hz; \
598 stackD [sp] = dz; \
599 sp++; }
600  
601 #define mpop(lz,hz,dz) { sp--; \
602 lz = stackLo[sp]; \
603 hz = stackHi[sp]; \
604 dz = stackD [sp]; }
605  
606  
607 #define mnextsize(az) (nextHi[az]-nextLo[az])
608  
609 #define mnextswap(az,bz) \
610 { Int32 tz; \
611 tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
612 tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
613 tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
614  
615  
616 #define MAIN_QSORT_SMALL_THRESH 20
617 #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
618 #define MAIN_QSORT_STACK_SIZE 100
619  
620 static
621 5832 void mainQSort3 ( UInt32* ptr,
622 UChar* block,
623 UInt16* quadrant,
624 Int32 nblock,
625 Int32 loSt,
626 Int32 hiSt,
627 Int32 dSt,
628 Int32* budget )
629 {
630 Int32 unLo, unHi, ltLo, gtHi, n, m, med;
631 Int32 sp, lo, hi, d;
632  
633 Int32 stackLo[MAIN_QSORT_STACK_SIZE];
634 Int32 stackHi[MAIN_QSORT_STACK_SIZE];
635 Int32 stackD [MAIN_QSORT_STACK_SIZE];
636  
637 Int32 nextLo[3];
638 Int32 nextHi[3];
639 Int32 nextD [3];
640  
641 5832 sp = 0;
642 5832 mpush ( loSt, hiSt, dSt );
643  
644 11688 ▶ while (sp > 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (sp > 0) { 5858 5830 11688
645  
646 5858 ▶ AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 );
Branch: 1 branch
BranchTrueFalseTotal
AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 ); 0 5858 5858
647  
648 5858 mpop ( lo, hi, d );
649 5858 ▶ if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
Branch: 2 branches
BranchTrueFalseTotal
if (hi - lo < MAIN_QSORT_SMALL_THRESH || 28 5830 5858
if (hi - lo < MAIN_QSORT_SMALL_THRESH || 2 26 28
650 d > MAIN_QSORT_DEPTH_THRESH) {
651 5832 mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
652 5832 ▶ if (*budget < 0) return;
Branch: 1 branch
BranchTrueFalseTotal
if (*budget < 0) return; 2 5830 5832
653 5830 continue;
654 }
655  
656 26 med = (Int32)
657 26 mmed3 ( block[ptr[ lo ]+d],
658 26 block[ptr[ hi ]+d],
659 26 block[ptr[ (lo+hi)>>1 ]+d] );
660  
661 26 unLo = ltLo = lo;
662 26 unHi = gtHi = hi;
663  
664 0 while (True) {
665 while (True) {
666 39039 ▶ if (unLo > unHi) break;
Branch: 1 branch
BranchTrueFalseTotal
if (unLo > unHi) break; 26 39013 39039
667 39013 n = ((Int32)block[ptr[unLo]+d]) - med;
668 39013 ▶ if (n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) { 39013 0 39013
669 39013 mswap(ptr[unLo], ptr[ltLo]);
670 39013 ltLo++; unLo++; continue;
671 };
672 0 ▶ if (n > 0) break;
Branch: 1 branch
BranchTrueFalseTotal
if (n > 0) break; 0 0 0
673 0 unLo++;
674 }
675 while (True) {
676 26 ▶ if (unLo > unHi) break;
Branch: 1 branch
BranchTrueFalseTotal
if (unLo > unHi) break; 26 0 26
677 0 n = ((Int32)block[ptr[unHi]+d]) - med;
678 0 ▶ if (n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) { 0 0 0
679 0 mswap(ptr[unHi], ptr[gtHi]);
680 0 gtHi--; unHi--; continue;
681 };
682 0 ▶ if (n < 0) break;
Branch: 1 branch
BranchTrueFalseTotal
if (n < 0) break; 0 0 0
683 0 unHi--;
684 }
685 26 ▶ if (unLo > unHi) break;
Branch: 1 branch
BranchTrueFalseTotal
if (unLo > unHi) break; 26 0 26
686 0 mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
687 }
688  
689 AssertD ( unHi == unLo-1, "mainQSort3(2)" );
690  
691 26 ▶ if (gtHi < ltLo) {
Branch: 1 branch
BranchTrueFalseTotal
if (gtHi < ltLo) { 26 0 26
692 26 mpush(lo, hi, d+1 );
693 26 continue;
694 }
695  
696 0 ▶ n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
Branch: 1 branch
BranchTrueFalseTotal
n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n); 0 0 0
697 0 ▶ m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
Branch: 1 branch
BranchTrueFalseTotal
m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m); 0 0 0
698  
699 0 n = lo + unLo - ltLo - 1;
700 0 m = hi - (gtHi - unHi) + 1;
701  
702 0 nextLo[0] = lo; nextHi[0] = n; nextD[0] = d;
703 0 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;
704 0 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
705  
706 0 ▶ if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
Branch: 1 branch
BranchTrueFalseTotal
if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); 0 0 0
707 0 ▶ if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
Branch: 1 branch
BranchTrueFalseTotal
if (mnextsize(1) < mnextsize(2)) mnextswap(1,2); 0 0 0
708 0 ▶ if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
Branch: 1 branch
BranchTrueFalseTotal
if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); 0 0 0
709  
710 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );
711 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );
712  
713 0 mpush (nextLo[0], nextHi[0], nextD[0]);
714 0 mpush (nextLo[1], nextHi[1], nextD[1]);
715 0 mpush (nextLo[2], nextHi[2], nextD[2]);
716 }
717 }
718  
719 #undef mswap
720 #undef mvswap
721 #undef mpush
722 #undef mpop
723 #undef mmin
724 #undef mnextsize
725 #undef mnextswap
726 #undef MAIN_QSORT_SMALL_THRESH
727 #undef MAIN_QSORT_DEPTH_THRESH
728 #undef MAIN_QSORT_STACK_SIZE
729  
730  
731 /*---------------------------------------------*/
732 /* Pre:
733 nblock > N_OVERSHOOT
734 block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
735 ((UChar*)block32) [0 .. nblock-1] holds block
736 ptr exists for [0 .. nblock-1]
737  
738 Post:
739 ((UChar*)block32) [0 .. nblock-1] holds block
740 All other areas of block32 destroyed
741 ftab [0 .. 65536 ] destroyed
742 ptr [0 .. nblock-1] holds sorted order
743 if (*budget < 0), sorting was abandoned
744 */
745  
746 #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
747 #define SETMASK (1 << 21)
748 #define CLEARMASK (~(SETMASK))
749  
750 static
751 3 void mainSort ( UInt32* ptr,
752 UChar* block,
753 UInt16* quadrant,
754 UInt32* ftab,
755 Int32 nblock,
756 Int32 verb,
757 Int32* budget )
758 {
759 Int32 i, j, k, ss, sb;
760 Int32 runningOrder[256];
761 Bool bigDone[256];
762 Int32 copyStart[256];
763 Int32 copyEnd [256];
764 UChar c1;
765 Int32 numQSorted;
766 UInt16 s;
767  
768 ((void)numQSorted); /* Silence variable ‘numQSorted’ set but not used warning */
769  
770 if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" );
771  
772 /*-- set up the 2-byte frequency table --*/
773 196614 ▶ for (i = 65536; i >= 0; i--) ftab[i] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 65536; i >= 0; i--) ftab[i] = 0; 196611 3 196614
774  
775 3 j = block[0] << 8;
776 3 i = nblock-1;
777 28762 ▶ for (; i >= 3; i -= 4) {
Branch: 1 branch
BranchTrueFalseTotal
for (; i >= 3; i -= 4) { 28759 3 28762
778 28759 quadrant[i] = 0;
779 28759 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
780 28759 ftab[j]++;
781 28759 quadrant[i-1] = 0;
782 28759 j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);
783 28759 ftab[j]++;
784 28759 quadrant[i-2] = 0;
785 28759 j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);
786 28759 ftab[j]++;
787 28759 quadrant[i-3] = 0;
788 28759 j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);
789 28759 ftab[j]++;
790 }
791 4 ▶ for (; i >= 0; i--) {
Branch: 1 branch
BranchTrueFalseTotal
for (; i >= 0; i--) { 1 3 4
792 1 quadrant[i] = 0;
793 1 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
794 1 ftab[j]++;
795 }
796  
797 /*-- (emphasises close relationship of block & quadrant) --*/
798 105 ▶ for (i = 0; i < BZ_N_OVERSHOOT; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < BZ_N_OVERSHOOT; i++) { 102 3 105
799 102 block [nblock+i] = block[i];
800 102 quadrant[nblock+i] = 0;
801 }
802  
803 if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" );
804  
805 /*-- Complete the initial radix sort --*/
806 196611 ▶ for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1]; 196608 3 196611
807  
808 3 s = block[0] << 8;
809 3 i = nblock-1;
810 28762 ▶ for (; i >= 3; i -= 4) {
Branch: 1 branch
BranchTrueFalseTotal
for (; i >= 3; i -= 4) { 28759 3 28762
811 28759 s = (s >> 8) | (block[i] << 8);
812 28759 j = ftab[s] -1;
813 28759 ftab[s] = j;
814 28759 ptr[j] = i;
815 28759 s = (s >> 8) | (block[i-1] << 8);
816 28759 j = ftab[s] -1;
817 28759 ftab[s] = j;
818 28759 ptr[j] = i-1;
819 28759 s = (s >> 8) | (block[i-2] << 8);
820 28759 j = ftab[s] -1;
821 28759 ftab[s] = j;
822 28759 ptr[j] = i-2;
823 28759 s = (s >> 8) | (block[i-3] << 8);
824 28759 j = ftab[s] -1;
825 28759 ftab[s] = j;
826 28759 ptr[j] = i-3;
827 }
828 4 ▶ for (; i >= 0; i--) {
Branch: 1 branch
BranchTrueFalseTotal
for (; i >= 0; i--) { 1 3 4
829 1 s = (s >> 8) | (block[i] << 8);
830 1 j = ftab[s] -1;
831 1 ftab[s] = j;
832 1 ptr[j] = i;
833 }
834  
835 /*--
836 Now ftab contains the first loc of every small bucket.
837 Calculate the running order, from smallest to largest
838 big bucket.
839 --*/
840 771 ▶ for (i = 0; i <= 255; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i <= 255; i++) { 768 3 771
841 768 bigDone [i] = False;
842 768 runningOrder[i] = i;
843 }
844  
845 {
846 Int32 vv;
847 3 Int32 h = 1;
848 15 ▶ do h = 3 * h + 1; while (h <= 256);
Branch: 1 branch
BranchTrueFalseTotal
do h = 3 * h + 1; while (h <= 256); 12 3 15
849 do {
850 15 h = h / 3;
851 3318 ▶ for (i = h; i <= 255; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = h; i <= 255; i++) { 3303 15 3318
852 3303 vv = runningOrder[i];
853 3303 j = i;
854 4663 ▶ while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
Branch: 1 branch
BranchTrueFalseTotal
while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) { 1503 3160 4663
855 1503 runningOrder[j] = runningOrder[j-h];
856 1503 j = j - h;
857 1503 ▶ if (j <= (h - 1)) goto zero;
Branch: 1 branch
BranchTrueFalseTotal
if (j <= (h - 1)) goto zero; 143 1360 1503
858 }
859 3160 zero:
860 3303 runningOrder[j] = vv;
861 }
862 15 ▶ } while (h != 1);
Branch: 1 branch
BranchTrueFalseTotal
} while (h != 1); 12 3 15
863 }
864  
865 /*--
866 The main sorting loop.
867 --*/
868  
869 3 numQSorted = 0;
870  
871 738 ▶ for (i = 0; i <= 255; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i <= 255; i++) { 737 1 738
872  
873 /*--
874 Process big buckets, starting with the least full.
875 Basically this is a 3-step process in which we call
876 mainQSort3 to sort the small buckets [ss, j], but
877 also make a big effort to avoid the calls if we can.
878 --*/
879 737 ss = runningOrder[i];
880  
881 /*--
882 Step 1:
883 Complete the big bucket [ss] by quicksorting
884 any unsorted small buckets [ss, j], for j != ss.
885 Hopefully previous pointer-scanning phases have already
886 completed many of the small buckets [ss, j], so
887 we don't have to sort them at all.
888 --*/
889 189112 ▶ for (j = 0; j <= 255; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j <= 255; j++) { 188377 735 189112
890 188377 ▶ if (j != ss) {
Branch: 1 branch
BranchTrueFalseTotal
if (j != ss) { 187640 737 188377
891 187640 sb = (ss << 8) + j;
892 187640 ▶ if ( ! (ftab[sb] & SETMASK) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ( ! (ftab[sb] & SETMASK) ) { 97680 89960 187640
893 97680 Int32 lo = ftab[sb] & CLEARMASK;
894 97680 Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
895 97680 ▶ if (hi > lo) {
Branch: 1 branch
BranchTrueFalseTotal
if (hi > lo) { 5832 91848 97680
896 if (verb >= 4)
897 VPrintf4 ( " qsort [0x%x, 0x%x] "
898 "done %d this %d\n",
899 ss, j, numQSorted, hi - lo + 1 );
900 5832 mainQSort3 (
901 ptr, block, quadrant, nblock,
902 lo, hi, BZ_N_RADIX, budget
903 );
904 5832 numQSorted += (hi - lo + 1);
905 5832 ▶ if (*budget < 0) return;
Branch: 1 branch
BranchTrueFalseTotal
if (*budget < 0) return; 2 5830 5832
906 }
907 }
908 187638 ftab[sb] |= SETMASK;
909 }
910 }
911  
912 735 ▶ AssertH ( !bigDone[ss], 1006 );
Branch: 1 branch
BranchTrueFalseTotal
AssertH ( !bigDone[ss], 1006 ); 0 735 735
913  
914 /*--
915 Step 2:
916 Now scan this big bucket [ss] so as to synthesise the
917 sorted order for small buckets [t, ss] for all t,
918 including, magically, the bucket [ss,ss] too.
919 This will avoid doing Real Work in subsequent Step 1's.
920 --*/
921 {
922 188895 ▶ for (j = 0; j <= 255; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j <= 255; j++) { 188160 735 188895
923 188160 copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK;
924 188160 copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
925 }
926 25816 ▶ for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) { 25081 735 25816
927 25081 ▶ k = ptr[j]-1; if (k < 0) k += nblock;
Branch: 1 branch
BranchTrueFalseTotal
k = ptr[j]-1; if (k < 0) k += nblock; 1 25080 25081
928 25081 c1 = block[k];
929 25081 ▶ if (!bigDone[c1])
Branch: 1 branch
BranchTrueFalseTotal
if (!bigDone[c1]) 12406 12675 25081
930 12406 ptr[ copyStart[c1]++ ] = k;
931 }
932 25658 ▶ for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) { 24923 735 25658
933 24923 ▶ k = ptr[j]-1; if (k < 0) k += nblock;
Branch: 1 branch
BranchTrueFalseTotal
k = ptr[j]-1; if (k < 0) k += nblock; 0 24923 24923
934 24923 c1 = block[k];
935 24923 ▶ if (!bigDone[c1])
Branch: 1 branch
BranchTrueFalseTotal
if (!bigDone[c1]) 12606 12317 24923
936 12606 ptr[ copyEnd[c1]-- ] = k;
937 }
938 }
939  
940 735 ▶ AssertH ( (copyStart[ss]-1 == copyEnd[ss])
Branch: 3 branches
BranchTrueFalseTotal
AssertH ( (copyStart[ss]-1 == copyEnd[ss]) 0 735 735
AssertH ( (copyStart[ss]-1 == copyEnd[ss]) 0 0 0
AssertH ( (copyStart[ss]-1 == copyEnd[ss]) 0 0 0
941 ||
942 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
943 Necessity for this case is demonstrated by compressing
944 a sequence of approximately 48.5 million of character
945 251; 1.0.0/1.0.1 will then die here. */
946 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
947 1007 )
948  
949 188895 ▶ for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK; 188160 735 188895
950  
951 /*--
952 Step 3:
953 The [ss] big bucket is now done. Record this fact,
954 and update the quadrant descriptors. Remember to
955 update quadrants in the overshoot area too, if
956 necessary. The "if (i < 255)" test merely skips
957 this updating for the last bucket processed, since
958 updating for the last bucket is pointless.
959  
960 The quadrant array provides a way to incrementally
961 cache sort orderings, as they appear, so as to
962 make subsequent comparisons in fullGtU() complete
963 faster. For repetitive blocks this makes a big
964 difference (but not big enough to be able to avoid
965 the fallback sorting mechanism, exponential radix sort).
966  
967 The precise meaning is: at all times:
968  
969 for 0 <= i < nblock and 0 <= j <= nblock
970  
971 if block[i] != block[j],
972  
973 then the relative values of quadrant[i] and
974 quadrant[j] are meaningless.
975  
976 else {
977 if quadrant[i] < quadrant[j]
978 then the string starting at i lexicographically
979 precedes the string starting at j
980  
981 else if quadrant[i] > quadrant[j]
982 then the string starting at j lexicographically
983 precedes the string starting at i
984  
985 else
986 the relative ordering of the strings starting
987 at i and j has not yet been determined.
988 }
989 --*/
990 735 bigDone[ss] = True;
991  
992 735 ▶ if (i < 255) {
Branch: 1 branch
BranchTrueFalseTotal
if (i < 255) { 734 1 735
993 734 Int32 bbStart = ftab[ss << 8] & CLEARMASK;
994 734 Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
995 734 Int32 shifts = 0;
996  
997 734 ▶ while ((bbSize >> shifts) > 65534) shifts++;
Branch: 1 branch
BranchTrueFalseTotal
while ((bbSize >> shifts) > 65534) shifts++; 0 734 734
998  
999 50502 ▶ for (j = bbSize-1; j >= 0; j--) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = bbSize-1; j >= 0; j--) { 49768 734 50502
1000 49768 Int32 a2update = ptr[bbStart + j];
1001 49768 UInt16 qVal = (UInt16)(j >> shifts);
1002 49768 quadrant[a2update] = qVal;
1003 49768 ▶ if (a2update < BZ_N_OVERSHOOT)
Branch: 1 branch
BranchTrueFalseTotal
if (a2update < BZ_N_OVERSHOOT) 34 49734 49768
1004 34 quadrant[a2update + nblock] = qVal;
1005 }
1006 734 ▶ AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
Branch: 1 branch
BranchTrueFalseTotal
AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 ); 0 734 734
1007 }
1008  
1009 }
1010  
1011 if (verb >= 4)
1012 VPrintf3 ( " %d pointers, %d sorted, %d scanned\n",
1013 nblock, numQSorted, nblock - numQSorted );
1014 }
1015  
1016 #undef BIGFREQ
1017 #undef SETMASK
1018 #undef CLEARMASK
1019  
1020  
1021 /*---------------------------------------------*/
1022 /* Pre:
1023 nblock > 0
1024 arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
1025 ((UChar*)arr2) [0 .. nblock-1] holds block
1026 arr1 exists for [0 .. nblock-1]
1027  
1028 Post:
1029 ((UChar*)arr2) [0 .. nblock-1] holds block
1030 All other areas of block destroyed
1031 ftab [ 0 .. 65536 ] destroyed
1032 arr1 [0 .. nblock-1] holds sorted order
1033 */
1034 21 void BZ2_blockSort ( EState* s )
1035 {
1036 21 UInt32* ptr = s->ptr;
1037 21 UChar* block = s->block;
1038 21 UInt32* ftab = s->ftab;
1039 21 Int32 nblock = s->nblock;
1040 21 Int32 verb = s->verbosity;
1041 21 Int32 wfact = s->workFactor;
1042 UInt16* quadrant;
1043 Int32 budget;
1044 Int32 budgetInit;
1045 Int32 i;
1046  
1047 21 ▶ if (nblock < 10000) {
Branch: 1 branch
BranchTrueFalseTotal
if (nblock < 10000) { 18 3 21
1048 18 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1049 } else {
1050 /* Calculate the location for quadrant, remembering to get
1051 the alignment right. Assumes that &(block[0]) is at least
1052 2-byte aligned -- this should be ok since block is really
1053 the first section of arr2.
1054 */
1055 3 i = nblock+BZ_N_OVERSHOOT;
1056 3 ▶ if (i & 1) i++;
Branch: 1 branch
BranchTrueFalseTotal
if (i & 1) i++; 1 2 3
1057 3 quadrant = (UInt16*)(&(block[i]));
1058  
1059 /* (wfact-1) / 3 puts the default-factor-30
1060 transition point at very roughly the same place as
1061 with v0.1 and v0.9.0.
1062 Not that it particularly matters any more, since the
1063 resulting compressed stream is now the same regardless
1064 of whether or not we use the main sort or fallback sort.
1065 */
1066 3 ▶ if (wfact < 1 ) wfact = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (wfact < 1 ) wfact = 1; 0 3 3
1067 3 ▶ if (wfact > 100) wfact = 100;
Branch: 1 branch
BranchTrueFalseTotal
if (wfact > 100) wfact = 100; 0 3 3
1068 3 budgetInit = nblock * ((wfact-1) / 3);
1069 3 budget = budgetInit;
1070  
1071 3 mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
1072 if (verb >= 3)
1073 VPrintf3 ( " %d work, %d block, ratio %5.2f\n",
1074 budgetInit - budget,
1075 nblock,
1076 (float)(budgetInit - budget) /
1077 (float)(nblock==0 ? 1 : nblock) );
1078 3 ▶ if (budget < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (budget < 0) { 2 1 3
1079 if (verb >= 2)
1080 VPrintf0 ( " too repetitive; using fallback"
1081 " sorting algorithm\n" );
1082 2 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1083 }
1084 }
1085  
1086 21 s->origPtr = -1;
1087 74230 ▶ for (i = 0; i < s->nblock; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < s->nblock; i++) 74230 0 74230
1088 74230 ▶ if (ptr[i] == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (ptr[i] == 0) 21 74209 74230
1089 21 { s->origPtr = i; break; };
1090  
1091 21 ▶ AssertH( s->origPtr != -1, 1003 );
Branch: 1 branch
BranchTrueFalseTotal
AssertH( s->origPtr != -1, 1003 ); 0 21 21
1092 21 }
1093  
1094  
1095 /*-------------------------------------------------------------*/
1096 /*--- end blocksort.c ---*/
1097 /*-------------------------------------------------------------*/
« decompress.c ↑ Summary huffman.c »