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.6 of 6 September 2010
12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
15 README file.
16
17 This program is released under the terms of the license contained
18 in the file LICENSE.
19 ------------------------------------------------------------------ */
20
21
22 #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__
fallbackSimpleSort(UInt32 * fmap,UInt32 * eclass,Int32 lo,Int32 hi)32 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 if (lo == hi) return;
41
42 if (hi - lo > 3) {
43 for ( i = hi-4; i >= lo; i-- ) {
44 tmp = fmap[i];
45 ec_tmp = eclass[tmp];
46 for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
47 fmap[j-4] = fmap[j];
48 fmap[j-4] = tmp;
49 }
50 }
51
52 for ( i = hi-1; i >= lo; i-- ) {
53 tmp = fmap[i];
54 ec_tmp = eclass[tmp];
55 for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
56 fmap[j-1] = fmap[j];
57 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
fallbackQSort3(UInt32 * fmap,UInt32 * eclass,Int32 loSt,Int32 hiSt)93 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 r = 0;
105
106 sp = 0;
107 fpush ( loSt, hiSt );
108
109 while (sp > 0) {
110
111 AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 );
112
113 fpop ( lo, hi );
114 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
115 fallbackSimpleSort ( fmap, eclass, lo, hi );
116 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 r = ((r * 7621) + 1) % 32768;
127 r3 = r % 3;
128 if (r3 == 0) med = eclass[fmap[lo]]; else
129 if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
130 med = eclass[fmap[hi]];
131
132 unLo = ltLo = lo;
133 unHi = gtHi = hi;
134
135 while (1) {
136 while (1) {
137 if (unLo > unHi) break;
138 n = (Int32)eclass[fmap[unLo]] - (Int32)med;
139 if (n == 0) {
140 fswap(fmap[unLo], fmap[ltLo]);
141 ltLo++; unLo++;
142 continue;
143 };
144 if (n > 0) break;
145 unLo++;
146 }
147 while (1) {
148 if (unLo > unHi) break;
149 n = (Int32)eclass[fmap[unHi]] - (Int32)med;
150 if (n == 0) {
151 fswap(fmap[unHi], fmap[gtHi]);
152 gtHi--; unHi--;
153 continue;
154 };
155 if (n < 0) break;
156 unHi--;
157 }
158 if (unLo > unHi) break;
159 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
160 }
161
162 AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );
163
164 if (gtHi < ltLo) continue;
165
166 n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
167 m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
168
169 n = lo + unLo - ltLo - 1;
170 m = hi - (gtHi - unHi) + 1;
171
172 if (n - lo > hi - m) {
173 fpush ( lo, n );
174 fpush ( m, hi );
175 } else {
176 fpush ( m, hi );
177 fpush ( lo, n );
178 }
179 }
180 }
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] |= (1 << ((zz) & 31))
206 #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
207 #define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
208 #define WORD_BH(zz) bhtab[(zz) >> 5]
209 #define UNALIGNED_BH(zz) ((zz) & 0x01f)
210
211 static
fallbackSort(UInt32 * fmap,UInt32 * eclass,UInt32 * bhtab,Int32 nblock,Int32 verb)212 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 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 for (i = 0; i < 257; i++) ftab[i] = 0;
232 for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
233 for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i];
234 for (i = 1; i < 257; i++) ftab[i] += ftab[i-1];
235
236 for (i = 0; i < nblock; i++) {
237 j = eclass8[i];
238 k = ftab[j] - 1;
239 ftab[j] = k;
240 fmap[k] = i;
241 }
242
243 nBhtab = 2 + (nblock / 32);
244 for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
245 for (i = 0; i < 256; i++) SET_BH(ftab[i]);
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 for (i = 0; i < 32; i++) {
255 SET_BH(nblock + 2*i);
256 CLEAR_BH(nblock + 2*i + 1);
257 }
258
259 /*-- the log(N) loop --*/
260 H = 1;
261 while (1) {
262
263 if (verb >= 4)
264 VPrintf1 ( " depth %6d has ", H );
265
266 j = 0;
267 for (i = 0; i < nblock; i++) {
268 if (ISSET_BH(i)) j = i;
269 k = fmap[i] - H; if (k < 0) k += nblock;
270 eclass[k] = j;
271 }
272
273 nNotDone = 0;
274 r = -1;
275 while (1) {
276
277 /*-- find the next non-singleton bucket --*/
278 k = r + 1;
279 while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
280 if (ISSET_BH(k)) {
281 while (WORD_BH(k) == 0xffffffff) k += 32;
282 while (ISSET_BH(k)) k++;
283 }
284 l = k - 1;
285 if (l >= nblock) break;
286 while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
287 if (!ISSET_BH(k)) {
288 while (WORD_BH(k) == 0x00000000) k += 32;
289 while (!ISSET_BH(k)) k++;
290 }
291 r = k - 1;
292 if (r >= nblock) break;
293
294 /*-- now [l, r] bracket current bucket --*/
295 if (r > l) {
296 nNotDone += (r - l + 1);
297 fallbackQSort3 ( fmap, eclass, l, r );
298
299 /*-- scan bucket and generate header bits-- */
300 cc = -1;
301 for (i = l; i <= r; i++) {
302 cc1 = eclass[fmap[i]];
303 if (cc != cc1) { SET_BH(i); cc = cc1; };
304 }
305 }
306 }
307
308 if (verb >= 4)
309 VPrintf1 ( "%6d unresolved strings\n", nNotDone );
310
311 H *= 2;
312 if (H > nblock || nNotDone == 0) break;
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 j = 0;
323 for (i = 0; i < nblock; i++) {
324 while (ftabCopy[j] == 0) j++;
325 ftabCopy[j]--;
326 eclass8[fmap[i]] = (UChar)j;
327 }
328 AssertH ( j < 256, 1005 );
329 }
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__
mainGtU(UInt32 i1,UInt32 i2,UChar * block,UInt16 * quadrant,UInt32 nblock,Int32 * budget)347 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 c1 = block[i1]; c2 = block[i2];
361 if (c1 != c2) return (c1 > c2);
362 i1++; i2++;
363 /* 2 */
364 c1 = block[i1]; c2 = block[i2];
365 if (c1 != c2) return (c1 > c2);
366 i1++; i2++;
367 /* 3 */
368 c1 = block[i1]; c2 = block[i2];
369 if (c1 != c2) return (c1 > c2);
370 i1++; i2++;
371 /* 4 */
372 c1 = block[i1]; c2 = block[i2];
373 if (c1 != c2) return (c1 > c2);
374 i1++; i2++;
375 /* 5 */
376 c1 = block[i1]; c2 = block[i2];
377 if (c1 != c2) return (c1 > c2);
378 i1++; i2++;
379 /* 6 */
380 c1 = block[i1]; c2 = block[i2];
381 if (c1 != c2) return (c1 > c2);
382 i1++; i2++;
383 /* 7 */
384 c1 = block[i1]; c2 = block[i2];
385 if (c1 != c2) return (c1 > c2);
386 i1++; i2++;
387 /* 8 */
388 c1 = block[i1]; c2 = block[i2];
389 if (c1 != c2) return (c1 > c2);
390 i1++; i2++;
391 /* 9 */
392 c1 = block[i1]; c2 = block[i2];
393 if (c1 != c2) return (c1 > c2);
394 i1++; i2++;
395 /* 10 */
396 c1 = block[i1]; c2 = block[i2];
397 if (c1 != c2) return (c1 > c2);
398 i1++; i2++;
399 /* 11 */
400 c1 = block[i1]; c2 = block[i2];
401 if (c1 != c2) return (c1 > c2);
402 i1++; i2++;
403 /* 12 */
404 c1 = block[i1]; c2 = block[i2];
405 if (c1 != c2) return (c1 > c2);
406 i1++; i2++;
407
408 k = nblock + 8;
409
410 do {
411 /* 1 */
412 c1 = block[i1]; c2 = block[i2];
413 if (c1 != c2) return (c1 > c2);
414 s1 = quadrant[i1]; s2 = quadrant[i2];
415 if (s1 != s2) return (s1 > s2);
416 i1++; i2++;
417 /* 2 */
418 c1 = block[i1]; c2 = block[i2];
419 if (c1 != c2) return (c1 > c2);
420 s1 = quadrant[i1]; s2 = quadrant[i2];
421 if (s1 != s2) return (s1 > s2);
422 i1++; i2++;
423 /* 3 */
424 c1 = block[i1]; c2 = block[i2];
425 if (c1 != c2) return (c1 > c2);
426 s1 = quadrant[i1]; s2 = quadrant[i2];
427 if (s1 != s2) return (s1 > s2);
428 i1++; i2++;
429 /* 4 */
430 c1 = block[i1]; c2 = block[i2];
431 if (c1 != c2) return (c1 > c2);
432 s1 = quadrant[i1]; s2 = quadrant[i2];
433 if (s1 != s2) return (s1 > s2);
434 i1++; i2++;
435 /* 5 */
436 c1 = block[i1]; c2 = block[i2];
437 if (c1 != c2) return (c1 > c2);
438 s1 = quadrant[i1]; s2 = quadrant[i2];
439 if (s1 != s2) return (s1 > s2);
440 i1++; i2++;
441 /* 6 */
442 c1 = block[i1]; c2 = block[i2];
443 if (c1 != c2) return (c1 > c2);
444 s1 = quadrant[i1]; s2 = quadrant[i2];
445 if (s1 != s2) return (s1 > s2);
446 i1++; i2++;
447 /* 7 */
448 c1 = block[i1]; c2 = block[i2];
449 if (c1 != c2) return (c1 > c2);
450 s1 = quadrant[i1]; s2 = quadrant[i2];
451 if (s1 != s2) return (s1 > s2);
452 i1++; i2++;
453 /* 8 */
454 c1 = block[i1]; c2 = block[i2];
455 if (c1 != c2) return (c1 > c2);
456 s1 = quadrant[i1]; s2 = quadrant[i2];
457 if (s1 != s2) return (s1 > s2);
458 i1++; i2++;
459
460 if (i1 >= nblock) i1 -= nblock;
461 if (i2 >= nblock) i2 -= nblock;
462
463 k -= 8;
464 (*budget)--;
465 }
466 while (k >= 0);
467
468 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
mainSimpleSort(UInt32 * ptr,UChar * block,UInt16 * quadrant,Int32 nblock,Int32 lo,Int32 hi,Int32 d,Int32 * budget)485 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 bigN = hi - lo + 1;
498 if (bigN < 2) return;
499
500 hp = 0;
501 while (incs[hp] < bigN) hp++;
502 hp--;
503
504 for (; hp >= 0; hp--) {
505 h = incs[hp];
506
507 i = lo + h;
508 while (True) {
509
510 /*-- copy 1 --*/
511 if (i > hi) break;
512 v = ptr[i];
513 j = i;
514 while ( mainGtU (
515 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
516 ) ) {
517 ptr[j] = ptr[j-h];
518 j = j - h;
519 if (j <= (lo + h - 1)) break;
520 }
521 ptr[j] = v;
522 i++;
523
524 /*-- copy 2 --*/
525 if (i > hi) break;
526 v = ptr[i];
527 j = i;
528 while ( mainGtU (
529 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
530 ) ) {
531 ptr[j] = ptr[j-h];
532 j = j - h;
533 if (j <= (lo + h - 1)) break;
534 }
535 ptr[j] = v;
536 i++;
537
538 /*-- copy 3 --*/
539 if (i > hi) break;
540 v = ptr[i];
541 j = i;
542 while ( mainGtU (
543 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
544 ) ) {
545 ptr[j] = ptr[j-h];
546 j = j - h;
547 if (j <= (lo + h - 1)) break;
548 }
549 ptr[j] = v;
550 i++;
551
552 if (*budget < 0) return;
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__
mmed3(UChar a,UChar b,UChar c)583 UChar mmed3 ( UChar a, UChar b, UChar c )
584 {
585 UChar t;
586 if (a > b) { t = a; a = b; b = t; };
587 if (b > c) {
588 b = c;
589 if (a > b) b = a;
590 }
591 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
mainQSort3(UInt32 * ptr,UChar * block,UInt16 * quadrant,Int32 nblock,Int32 loSt,Int32 hiSt,Int32 dSt,Int32 * budget)621 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 sp = 0;
642 mpush ( loSt, hiSt, dSt );
643
644 while (sp > 0) {
645
646 AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 );
647
648 mpop ( lo, hi, d );
649 if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
650 d > MAIN_QSORT_DEPTH_THRESH) {
651 mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
652 if (*budget < 0) return;
653 continue;
654 }
655
656 med = (Int32)
657 mmed3 ( block[ptr[ lo ]+d],
658 block[ptr[ hi ]+d],
659 block[ptr[ (lo+hi)>>1 ]+d] );
660
661 unLo = ltLo = lo;
662 unHi = gtHi = hi;
663
664 while (True) {
665 while (True) {
666 if (unLo > unHi) break;
667 n = ((Int32)block[ptr[unLo]+d]) - med;
668 if (n == 0) {
669 mswap(ptr[unLo], ptr[ltLo]);
670 ltLo++; unLo++; continue;
671 };
672 if (n > 0) break;
673 unLo++;
674 }
675 while (True) {
676 if (unLo > unHi) break;
677 n = ((Int32)block[ptr[unHi]+d]) - med;
678 if (n == 0) {
679 mswap(ptr[unHi], ptr[gtHi]);
680 gtHi--; unHi--; continue;
681 };
682 if (n < 0) break;
683 unHi--;
684 }
685 if (unLo > unHi) break;
686 mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
687 }
688
689 AssertD ( unHi == unLo-1, "mainQSort3(2)" );
690
691 if (gtHi < ltLo) {
692 mpush(lo, hi, d+1 );
693 continue;
694 }
695
696 n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
697 m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
698
699 n = lo + unLo - ltLo - 1;
700 m = hi - (gtHi - unHi) + 1;
701
702 nextLo[0] = lo; nextHi[0] = n; nextD[0] = d;
703 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;
704 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
705
706 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
707 if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
708 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
709
710 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );
711 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );
712
713 mpush (nextLo[0], nextHi[0], nextD[0]);
714 mpush (nextLo[1], nextHi[1], nextD[1]);
715 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
mainSort(UInt32 * ptr,UChar * block,UInt16 * quadrant,UInt32 * ftab,Int32 nblock,Int32 verb,Int32 * budget)751 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 if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" );
768
769 /*-- set up the 2-byte frequency table --*/
770 for (i = 65536; i >= 0; i--) ftab[i] = 0;
771
772 j = block[0] << 8;
773 i = nblock-1;
774 for (; i >= 3; i -= 4) {
775 quadrant[i] = 0;
776 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
777 ftab[j]++;
778 quadrant[i-1] = 0;
779 j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);
780 ftab[j]++;
781 quadrant[i-2] = 0;
782 j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);
783 ftab[j]++;
784 quadrant[i-3] = 0;
785 j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);
786 ftab[j]++;
787 }
788 for (; i >= 0; i--) {
789 quadrant[i] = 0;
790 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
791 ftab[j]++;
792 }
793
794 /*-- (emphasises close relationship of block & quadrant) --*/
795 for (i = 0; i < BZ_N_OVERSHOOT; i++) {
796 block [nblock+i] = block[i];
797 quadrant[nblock+i] = 0;
798 }
799
800 if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" );
801
802 /*-- Complete the initial radix sort --*/
803 for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
804
805 s = block[0] << 8;
806 i = nblock-1;
807 for (; i >= 3; i -= 4) {
808 s = (s >> 8) | (block[i] << 8);
809 j = ftab[s] -1;
810 ftab[s] = j;
811 ptr[j] = i;
812 s = (s >> 8) | (block[i-1] << 8);
813 j = ftab[s] -1;
814 ftab[s] = j;
815 ptr[j] = i-1;
816 s = (s >> 8) | (block[i-2] << 8);
817 j = ftab[s] -1;
818 ftab[s] = j;
819 ptr[j] = i-2;
820 s = (s >> 8) | (block[i-3] << 8);
821 j = ftab[s] -1;
822 ftab[s] = j;
823 ptr[j] = i-3;
824 }
825 for (; i >= 0; i--) {
826 s = (s >> 8) | (block[i] << 8);
827 j = ftab[s] -1;
828 ftab[s] = j;
829 ptr[j] = i;
830 }
831
832 /*--
833 Now ftab contains the first loc of every small bucket.
834 Calculate the running order, from smallest to largest
835 big bucket.
836 --*/
837 for (i = 0; i <= 255; i++) {
838 bigDone [i] = False;
839 runningOrder[i] = i;
840 }
841
842 {
843 Int32 vv;
844 Int32 h = 1;
845 do h = 3 * h + 1; while (h <= 256);
846 do {
847 h = h / 3;
848 for (i = h; i <= 255; i++) {
849 vv = runningOrder[i];
850 j = i;
851 while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
852 runningOrder[j] = runningOrder[j-h];
853 j = j - h;
854 if (j <= (h - 1)) goto zero;
855 }
856 zero:
857 runningOrder[j] = vv;
858 }
859 } while (h != 1);
860 }
861
862 /*--
863 The main sorting loop.
864 --*/
865
866 numQSorted = 0;
867
868 for (i = 0; i <= 255; i++) {
869
870 /*--
871 Process big buckets, starting with the least full.
872 Basically this is a 3-step process in which we call
873 mainQSort3 to sort the small buckets [ss, j], but
874 also make a big effort to avoid the calls if we can.
875 --*/
876 ss = runningOrder[i];
877
878 /*--
879 Step 1:
880 Complete the big bucket [ss] by quicksorting
881 any unsorted small buckets [ss, j], for j != ss.
882 Hopefully previous pointer-scanning phases have already
883 completed many of the small buckets [ss, j], so
884 we don't have to sort them at all.
885 --*/
886 for (j = 0; j <= 255; j++) {
887 if (j != ss) {
888 sb = (ss << 8) + j;
889 if ( ! (ftab[sb] & SETMASK) ) {
890 Int32 lo = ftab[sb] & CLEARMASK;
891 Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
892 if (hi > lo) {
893 if (verb >= 4)
894 VPrintf4 ( " qsort [0x%x, 0x%x] "
895 "done %d this %d\n",
896 ss, j, numQSorted, hi - lo + 1 );
897 mainQSort3 (
898 ptr, block, quadrant, nblock,
899 lo, hi, BZ_N_RADIX, budget
900 );
901 numQSorted += (hi - lo + 1);
902 if (*budget < 0) return;
903 }
904 }
905 ftab[sb] |= SETMASK;
906 }
907 }
908
909 AssertH ( !bigDone[ss], 1006 );
910
911 /*--
912 Step 2:
913 Now scan this big bucket [ss] so as to synthesise the
914 sorted order for small buckets [t, ss] for all t,
915 including, magically, the bucket [ss,ss] too.
916 This will avoid doing Real Work in subsequent Step 1's.
917 --*/
918 {
919 for (j = 0; j <= 255; j++) {
920 copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK;
921 copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
922 }
923 for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
924 k = ptr[j]-1; if (k < 0) k += nblock;
925 c1 = block[k];
926 if (!bigDone[c1])
927 ptr[ copyStart[c1]++ ] = k;
928 }
929 for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
930 k = ptr[j]-1; if (k < 0) k += nblock;
931 c1 = block[k];
932 if (!bigDone[c1])
933 ptr[ copyEnd[c1]-- ] = k;
934 }
935 }
936
937 AssertH ( (copyStart[ss]-1 == copyEnd[ss])
938 ||
939 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
940 Necessity for this case is demonstrated by compressing
941 a sequence of approximately 48.5 million of character
942 251; 1.0.0/1.0.1 will then die here. */
943 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
944 1007 )
945
946 for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;
947
948 /*--
949 Step 3:
950 The [ss] big bucket is now done. Record this fact,
951 and update the quadrant descriptors. Remember to
952 update quadrants in the overshoot area too, if
953 necessary. The "if (i < 255)" test merely skips
954 this updating for the last bucket processed, since
955 updating for the last bucket is pointless.
956
957 The quadrant array provides a way to incrementally
958 cache sort orderings, as they appear, so as to
959 make subsequent comparisons in fullGtU() complete
960 faster. For repetitive blocks this makes a big
961 difference (but not big enough to be able to avoid
962 the fallback sorting mechanism, exponential radix sort).
963
964 The precise meaning is: at all times:
965
966 for 0 <= i < nblock and 0 <= j <= nblock
967
968 if block[i] != block[j],
969
970 then the relative values of quadrant[i] and
971 quadrant[j] are meaningless.
972
973 else {
974 if quadrant[i] < quadrant[j]
975 then the string starting at i lexicographically
976 precedes the string starting at j
977
978 else if quadrant[i] > quadrant[j]
979 then the string starting at j lexicographically
980 precedes the string starting at i
981
982 else
983 the relative ordering of the strings starting
984 at i and j has not yet been determined.
985 }
986 --*/
987 bigDone[ss] = True;
988
989 if (i < 255) {
990 Int32 bbStart = ftab[ss << 8] & CLEARMASK;
991 Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
992 Int32 shifts = 0;
993
994 while ((bbSize >> shifts) > 65534) shifts++;
995
996 for (j = bbSize-1; j >= 0; j--) {
997 Int32 a2update = ptr[bbStart + j];
998 UInt16 qVal = (UInt16)(j >> shifts);
999 quadrant[a2update] = qVal;
1000 if (a2update < BZ_N_OVERSHOOT)
1001 quadrant[a2update + nblock] = qVal;
1002 }
1003 AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
1004 }
1005
1006 }
1007
1008 if (verb >= 4)
1009 VPrintf3 ( " %d pointers, %d sorted, %d scanned\n",
1010 nblock, numQSorted, nblock - numQSorted );
1011 }
1012
1013 #undef BIGFREQ
1014 #undef SETMASK
1015 #undef CLEARMASK
1016
1017
1018 /*---------------------------------------------*/
1019 /* Pre:
1020 nblock > 0
1021 arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
1022 ((UChar*)arr2) [0 .. nblock-1] holds block
1023 arr1 exists for [0 .. nblock-1]
1024
1025 Post:
1026 ((UChar*)arr2) [0 .. nblock-1] holds block
1027 All other areas of block destroyed
1028 ftab [ 0 .. 65536 ] destroyed
1029 arr1 [0 .. nblock-1] holds sorted order
1030 */
BZ2_blockSort(EState * s)1031 void BZ2_blockSort ( EState* s )
1032 {
1033 UInt32* ptr = s->ptr;
1034 UChar* block = s->block;
1035 UInt32* ftab = s->ftab;
1036 Int32 nblock = s->nblock;
1037 Int32 verb = s->verbosity;
1038 Int32 wfact = s->workFactor;
1039 UInt16* quadrant;
1040 Int32 budget;
1041 Int32 budgetInit;
1042 Int32 i;
1043
1044 if (nblock < 10000) {
1045 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1046 } else {
1047 /* Calculate the location for quadrant, remembering to get
1048 the alignment right. Assumes that &(block[0]) is at least
1049 2-byte aligned -- this should be ok since block is really
1050 the first section of arr2.
1051 */
1052 i = nblock+BZ_N_OVERSHOOT;
1053 if (i & 1) i++;
1054 quadrant = (UInt16*)(&(block[i]));
1055
1056 /* (wfact-1) / 3 puts the default-factor-30
1057 transition point at very roughly the same place as
1058 with v0.1 and v0.9.0.
1059 Not that it particularly matters any more, since the
1060 resulting compressed stream is now the same regardless
1061 of whether or not we use the main sort or fallback sort.
1062 */
1063 if (wfact < 1 ) wfact = 1;
1064 if (wfact > 100) wfact = 100;
1065 budgetInit = nblock * ((wfact-1) / 3);
1066 budget = budgetInit;
1067
1068 mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
1069 if (verb >= 3)
1070 VPrintf3 ( " %d work, %d block, ratio %5.2f\n",
1071 budgetInit - budget,
1072 nblock,
1073 (float)(budgetInit - budget) /
1074 (float)(nblock==0 ? 1 : nblock) );
1075 if (budget < 0) {
1076 if (verb >= 2)
1077 VPrintf0 ( " too repetitive; using fallback"
1078 " sorting algorithm\n" );
1079 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1080 }
1081 }
1082
1083 s->origPtr = -1;
1084 for (i = 0; i < s->nblock; i++)
1085 if (ptr[i] == 0)
1086 { s->origPtr = i; break; };
1087
1088 AssertH( s->origPtr != -1, 1003 );
1089 }
1090
1091
1092 /*-------------------------------------------------------------*/
1093 /*--- end blocksort.c ---*/
1094 /*-------------------------------------------------------------*/
1095