2 /*-------------------------------------------------------------*/
3 /*--- Block sorting machinery ---*/
4 /*--- blocksort.c ---*/
5 /*-------------------------------------------------------------*/
8 This file is a part of bzip2 and/or libbzip2, a program and
9 library for lossless, block-sorting data compression.
11 Copyright (C) 1996-2002 Julian R Seward. All rights reserved.
13 Redistribution and use in source and binary forms, with or without
14 modification, are permitted provided that the following conditions
17 1. Redistributions of source code must retain the above copyright
18 notice, this list of conditions and the following disclaimer.
20 2. The origin of this software must not be misrepresented; you must
21 not claim that you wrote the original software. If you use this
22 software in a product, an acknowledgment in the product
23 documentation would be appreciated but is not required.
25 3. Altered source versions must be plainly marked as such, and must
26 not be misrepresented as being the original software.
28 4. The name of the author may not be used to endorse or promote
29 products derived from this software without specific prior written
32 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
33 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
34 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
36 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
37 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
38 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
39 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
40 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
41 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
42 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44 Julian Seward, Cambridge, UK.
46 bzip2/libbzip2 version 1.0.6 of 6 September 2010
47 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
49 This program is based on (at least) the work of:
59 For more information on these sources, see the manual.
62 #include "bzlib_private.h"
64 /*---------------------------------------------*/
65 /*--- Fallback O(N log(N)^2) sorting ---*/
66 /*--- algorithm, for repetitive blocks ---*/
67 /*---------------------------------------------*/
69 /*---------------------------------------------*/
72 void fallbackSimpleSort ( UInt32* fmap,
83 for ( i = hi-4; i >= lo; i-- ) {
86 for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
92 for ( i = hi-1; i >= lo; i-- ) {
95 for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
102 /*---------------------------------------------*/
103 #define fswap(zz1, zz2) \
104 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
106 #define fvswap(zzp1, zzp2, zzn) \
108 Int32 yyp1 = (zzp1); \
109 Int32 yyp2 = (zzp2); \
112 fswap(fmap[yyp1], fmap[yyp2]); \
113 yyp1++; yyp2++; yyn--; \
118 #define fmin(a,b) ((a) < (b)) ? (a) : (b)
120 #define fpush(lz,hz) { stackLo[sp] = lz; \
124 #define fpop(lz,hz) { sp--; \
128 #define FALLBACK_QSORT_SMALL_THRESH 10
129 #define FALLBACK_QSORT_STACK_SIZE 100
133 void fallbackQSort3 ( UInt32* fmap,
138 Int32 unLo, unHi, ltLo, gtHi, n, m;
141 Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];
142 Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];
147 fpush ( loSt, hiSt );
151 AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 );
154 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
155 fallbackSimpleSort ( fmap, eclass, lo, hi );
159 /* Random partitioning. Median of 3 sometimes fails to
160 avoid bad cases. Median of 9 seems to help but
161 looks rather expensive. This too seems to work but
162 is cheaper. Guidance for the magic constants
163 7621 and 32768 is taken from Sedgewick's algorithms
166 r = ((r * 7621) + 1) % 32768;
168 if (r3 == 0) med = eclass[fmap[lo]]; else
169 if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
170 med = eclass[fmap[hi]];
177 if (unLo > unHi) break;
178 n = (Int32)eclass[fmap[unLo]] - (Int32)med;
180 fswap(fmap[unLo], fmap[ltLo]);
188 if (unLo > unHi) break;
189 n = (Int32)eclass[fmap[unHi]] - (Int32)med;
191 fswap(fmap[unHi], fmap[gtHi]);
198 if (unLo > unHi) break;
199 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
202 AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );
204 if (gtHi < ltLo) continue;
206 n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
207 m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
209 n = lo + unLo - ltLo - 1;
210 m = hi - (gtHi - unHi) + 1;
212 if (n - lo > hi - m) {
227 #undef FALLBACK_QSORT_SMALL_THRESH
228 #undef FALLBACK_QSORT_STACK_SIZE
231 /*---------------------------------------------*/
234 eclass exists for [0 .. nblock-1]
235 ((UChar*)eclass) [0 .. nblock-1] holds block
236 ptr exists for [0 .. nblock-1]
239 ((UChar*)eclass) [0 .. nblock-1] holds block
240 All other areas of eclass destroyed
241 fmap [0 .. nblock-1] holds sorted order
242 bhtab [ 0 .. 2+(nblock/32) ] destroyed
245 #define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
246 #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
247 #define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
248 #define WORD_BH(zz) bhtab[(zz) >> 5]
249 #define UNALIGNED_BH(zz) ((zz) & 0x01f)
252 void fallbackSort ( UInt32* fmap,
260 Int32 H, i, j, k, l, r, cc, cc1;
263 UChar* eclass8 = (UChar*)eclass;
266 Initial 1-char radix sort to generate
267 initial fmap and initial BH bits.
270 VPrintf0 ( " bucket sorting ...\n" );
271 for (i = 0; i < 257; i++) ftab[i] = 0;
272 for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
273 for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i];
274 for (i = 1; i < 257; i++) ftab[i] += ftab[i-1];
276 for (i = 0; i < nblock; i++) {
283 nBhtab = 2 + (nblock / 32);
284 for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
285 for (i = 0; i < 256; i++) SET_BH(ftab[i]);
288 Inductively refine the buckets. Kind-of an
289 "exponential radix sort" (!), inspired by the
290 Manber-Myers suffix array construction algorithm.
293 /*-- set sentinel bits for block-end detection --*/
294 for (i = 0; i < 32; i++) {
295 SET_BH(nblock + 2*i);
296 CLEAR_BH(nblock + 2*i + 1);
299 /*-- the log(N) loop --*/
304 VPrintf1 ( " depth %6d has ", H );
307 for (i = 0; i < nblock; i++) {
308 if (ISSET_BH(i)) j = i;
309 k = fmap[i] - H; if (k < 0) k += nblock;
317 /*-- find the next non-singleton bucket --*/
319 while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
321 while (WORD_BH(k) == 0xffffffff) k += 32;
322 while (ISSET_BH(k)) k++;
325 if (l >= nblock) break;
326 while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
328 while (WORD_BH(k) == 0x00000000) k += 32;
329 while (!ISSET_BH(k)) k++;
332 if (r >= nblock) break;
334 /*-- now [l, r] bracket current bucket --*/
336 nNotDone += (r - l + 1);
337 fallbackQSort3 ( fmap, eclass, l, r );
339 /*-- scan bucket and generate header bits-- */
341 for (i = l; i <= r; i++) {
342 cc1 = eclass[fmap[i]];
343 if (cc != cc1) { SET_BH(i); cc = cc1; };
349 VPrintf1 ( "%6d unresolved strings\n", nNotDone );
352 if (H > nblock || nNotDone == 0) break;
356 Reconstruct the original block in
357 eclass8 [0 .. nblock-1], since the
358 previous phase destroyed it.
361 VPrintf0 ( " reconstructing block ...\n" );
363 for (i = 0; i < nblock; i++) {
364 while (ftabCopy[j] == 0) j++;
366 eclass8[fmap[i]] = (UChar)j;
368 AssertH ( j < 256, 1005 );
378 /*---------------------------------------------*/
379 /*--- The main, O(N^2 log(N)) sorting ---*/
380 /*--- algorithm. Faster for "normal" ---*/
381 /*--- non-repetitive blocks. ---*/
382 /*---------------------------------------------*/
384 /*---------------------------------------------*/
387 Bool mainGtU ( UInt32 i1,
398 AssertD ( i1 != i2, "mainGtU" );
400 c1 = block[i1]; c2 = block[i2];
401 if (c1 != c2) return (c1 > c2);
404 c1 = block[i1]; c2 = block[i2];
405 if (c1 != c2) return (c1 > c2);
408 c1 = block[i1]; c2 = block[i2];
409 if (c1 != c2) return (c1 > c2);
412 c1 = block[i1]; c2 = block[i2];
413 if (c1 != c2) return (c1 > c2);
416 c1 = block[i1]; c2 = block[i2];
417 if (c1 != c2) return (c1 > c2);
420 c1 = block[i1]; c2 = block[i2];
421 if (c1 != c2) return (c1 > c2);
424 c1 = block[i1]; c2 = block[i2];
425 if (c1 != c2) return (c1 > c2);
428 c1 = block[i1]; c2 = block[i2];
429 if (c1 != c2) return (c1 > c2);
432 c1 = block[i1]; c2 = block[i2];
433 if (c1 != c2) return (c1 > c2);
436 c1 = block[i1]; c2 = block[i2];
437 if (c1 != c2) return (c1 > c2);
440 c1 = block[i1]; c2 = block[i2];
441 if (c1 != c2) return (c1 > c2);
444 c1 = block[i1]; c2 = block[i2];
445 if (c1 != c2) return (c1 > c2);
452 c1 = block[i1]; c2 = block[i2];
453 if (c1 != c2) return (c1 > c2);
454 s1 = quadrant[i1]; s2 = quadrant[i2];
455 if (s1 != s2) return (s1 > s2);
458 c1 = block[i1]; c2 = block[i2];
459 if (c1 != c2) return (c1 > c2);
460 s1 = quadrant[i1]; s2 = quadrant[i2];
461 if (s1 != s2) return (s1 > s2);
464 c1 = block[i1]; c2 = block[i2];
465 if (c1 != c2) return (c1 > c2);
466 s1 = quadrant[i1]; s2 = quadrant[i2];
467 if (s1 != s2) return (s1 > s2);
470 c1 = block[i1]; c2 = block[i2];
471 if (c1 != c2) return (c1 > c2);
472 s1 = quadrant[i1]; s2 = quadrant[i2];
473 if (s1 != s2) return (s1 > s2);
476 c1 = block[i1]; c2 = block[i2];
477 if (c1 != c2) return (c1 > c2);
478 s1 = quadrant[i1]; s2 = quadrant[i2];
479 if (s1 != s2) return (s1 > s2);
482 c1 = block[i1]; c2 = block[i2];
483 if (c1 != c2) return (c1 > c2);
484 s1 = quadrant[i1]; s2 = quadrant[i2];
485 if (s1 != s2) return (s1 > s2);
488 c1 = block[i1]; c2 = block[i2];
489 if (c1 != c2) return (c1 > c2);
490 s1 = quadrant[i1]; s2 = quadrant[i2];
491 if (s1 != s2) return (s1 > s2);
494 c1 = block[i1]; c2 = block[i2];
495 if (c1 != c2) return (c1 > c2);
496 s1 = quadrant[i1]; s2 = quadrant[i2];
497 if (s1 != s2) return (s1 > s2);
500 if (i1 >= nblock) i1 -= nblock;
501 if (i2 >= nblock) i2 -= nblock;
512 /*---------------------------------------------*/
514 Knuth's increments seem to work better
515 than Incerpi-Sedgewick here. Possibly
516 because the number of elems to sort is
517 usually small, typically <= 20.
520 Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
521 9841, 29524, 88573, 265720,
525 void mainSimpleSort ( UInt32* ptr,
534 Int32 i, j, h, bigN, hp;
538 if (bigN < 2) return;
541 while (incs[hp] < bigN) hp++;
544 for (; hp >= 0; hp--) {
555 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
559 if (j <= (lo + h - 1)) break;
569 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
573 if (j <= (lo + h - 1)) break;
583 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
587 if (j <= (lo + h - 1)) break;
592 if (*budget < 0) return;
598 /*---------------------------------------------*/
600 The following is an implementation of
601 an elegant 3-way quicksort for strings,
602 described in a paper "Fast Algorithms for
603 Sorting and Searching Strings", by Robert
604 Sedgewick and Jon L. Bentley.
607 #define mswap(zz1, zz2) \
608 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
610 #define mvswap(zzp1, zzp2, zzn) \
612 Int32 yyp1 = (zzp1); \
613 Int32 yyp2 = (zzp2); \
616 mswap(ptr[yyp1], ptr[yyp2]); \
617 yyp1++; yyp2++; yyn--; \
623 UChar mmed3 ( UChar a, UChar b, UChar c )
626 if (a > b) { t = a; a = b; b = t; };
634 #define mmin(a,b) ((a) < (b)) ? (a) : (b)
636 #define mpush(lz,hz,dz) { stackLo[sp] = lz; \
641 #define mpop(lz,hz,dz) { sp--; \
647 #define mnextsize(az) (nextHi[az]-nextLo[az])
649 #define mnextswap(az,bz) \
651 tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
652 tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
653 tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
656 #define MAIN_QSORT_SMALL_THRESH 20
657 #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
658 #define MAIN_QSORT_STACK_SIZE 100
661 void mainQSort3 ( UInt32* ptr,
670 Int32 unLo, unHi, ltLo, gtHi, n, m, med;
673 Int32 stackLo[MAIN_QSORT_STACK_SIZE];
674 Int32 stackHi[MAIN_QSORT_STACK_SIZE];
675 Int32 stackD [MAIN_QSORT_STACK_SIZE];
682 mpush ( loSt, hiSt, dSt );
686 AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 );
689 if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
690 d > MAIN_QSORT_DEPTH_THRESH) {
691 mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
692 if (*budget < 0) return;
697 mmed3 ( block[ptr[ lo ]+d],
699 block[ptr[ (lo+hi)>>1 ]+d] );
706 if (unLo > unHi) break;
707 n = ((Int32)block[ptr[unLo]+d]) - med;
709 mswap(ptr[unLo], ptr[ltLo]);
710 ltLo++; unLo++; continue;
716 if (unLo > unHi) break;
717 n = ((Int32)block[ptr[unHi]+d]) - med;
719 mswap(ptr[unHi], ptr[gtHi]);
720 gtHi--; unHi--; continue;
725 if (unLo > unHi) break;
726 mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
729 AssertD ( unHi == unLo-1, "mainQSort3(2)" );
736 n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
737 m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
739 n = lo + unLo - ltLo - 1;
740 m = hi - (gtHi - unHi) + 1;
742 nextLo[0] = lo; nextHi[0] = n; nextD[0] = d;
743 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;
744 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
746 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
747 if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
748 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
750 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );
751 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );
753 mpush (nextLo[0], nextHi[0], nextD[0]);
754 mpush (nextLo[1], nextHi[1], nextD[1]);
755 mpush (nextLo[2], nextHi[2], nextD[2]);
766 #undef MAIN_QSORT_SMALL_THRESH
767 #undef MAIN_QSORT_DEPTH_THRESH
768 #undef MAIN_QSORT_STACK_SIZE
771 /*---------------------------------------------*/
774 block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
775 ((UChar*)block32) [0 .. nblock-1] holds block
776 ptr exists for [0 .. nblock-1]
779 ((UChar*)block32) [0 .. nblock-1] holds block
780 All other areas of block32 destroyed
781 ftab [0 .. 65536 ] destroyed
782 ptr [0 .. nblock-1] holds sorted order
783 if (*budget < 0), sorting was abandoned
786 #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
787 #define SETMASK (1 << 21)
788 #define CLEARMASK (~(SETMASK))
791 void mainSort ( UInt32* ptr,
799 Int32 i, j, k, ss, sb;
800 Int32 runningOrder[256];
802 Int32 copyStart[256];
807 if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" );
809 /*-- set up the 2-byte frequency table --*/
810 for (i = 65536; i >= 0; i--) ftab[i] = 0;
814 for (; i >= 3; i -= 4) {
816 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
819 j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);
822 j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);
825 j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);
828 for (; i >= 0; i--) {
830 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
834 /*-- (emphasises close relationship of block & quadrant) --*/
835 for (i = 0; i < BZ_N_OVERSHOOT; i++) {
836 block [nblock+i] = block[i];
837 quadrant[nblock+i] = 0;
840 if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" );
842 /*-- Complete the initial radix sort --*/
843 for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
847 for (; i >= 3; i -= 4) {
848 s = (s >> 8) | (block[i] << 8);
852 s = (s >> 8) | (block[i-1] << 8);
856 s = (s >> 8) | (block[i-2] << 8);
860 s = (s >> 8) | (block[i-3] << 8);
865 for (; i >= 0; i--) {
866 s = (s >> 8) | (block[i] << 8);
873 Now ftab contains the first loc of every small bucket.
874 Calculate the running order, from smallest to largest
877 for (i = 0; i <= 255; i++) {
885 do h = 3 * h + 1; while (h <= 256);
888 for (i = h; i <= 255; i++) {
889 vv = runningOrder[i];
891 while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
892 runningOrder[j] = runningOrder[j-h];
894 if (j <= (h - 1)) goto zero;
897 runningOrder[j] = vv;
903 The main sorting loop.
908 for (i = 0; i <= 255; i++) {
911 Process big buckets, starting with the least full.
912 Basically this is a 3-step process in which we call
913 mainQSort3 to sort the small buckets [ss, j], but
914 also make a big effort to avoid the calls if we can.
916 ss = runningOrder[i];
920 Complete the big bucket [ss] by quicksorting
921 any unsorted small buckets [ss, j], for j != ss.
922 Hopefully previous pointer-scanning phases have already
923 completed many of the small buckets [ss, j], so
924 we don't have to sort them at all.
926 for (j = 0; j <= 255; j++) {
929 if ( ! (ftab[sb] & SETMASK) ) {
930 Int32 lo = ftab[sb] & CLEARMASK;
931 Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
934 VPrintf4 ( " qsort [0x%x, 0x%x] "
936 ss, j, numQSorted, hi - lo + 1 );
938 ptr, block, quadrant, nblock,
939 lo, hi, BZ_N_RADIX, budget
941 numQSorted += (hi - lo + 1);
942 if (*budget < 0) return;
949 AssertH ( !bigDone[ss], 1006 );
953 Now scan this big bucket [ss] so as to synthesise the
954 sorted order for small buckets [t, ss] for all t,
955 including, magically, the bucket [ss,ss] too.
956 This will avoid doing Real Work in subsequent Step 1's.
959 for (j = 0; j <= 255; j++) {
960 copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK;
961 copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
963 for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
964 k = ptr[j]-1; if (k < 0) k += nblock;
967 ptr[ copyStart[c1]++ ] = k;
969 for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
970 k = ptr[j]-1; if (k < 0) k += nblock;
973 ptr[ copyEnd[c1]-- ] = k;
977 AssertH ( (copyStart[ss]-1 == copyEnd[ss])
979 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
980 Necessity for this case is demonstrated by compressing
981 a sequence of approximately 48.5 million of character
982 251; 1.0.0/1.0.1 will then die here. */
983 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
986 for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;
990 The [ss] big bucket is now done. Record this fact,
991 and update the quadrant descriptors. Remember to
992 update quadrants in the overshoot area too, if
993 necessary. The "if (i < 255)" test merely skips
994 this updating for the last bucket processed, since
995 updating for the last bucket is pointless.
997 The quadrant array provides a way to incrementally
998 cache sort orderings, as they appear, so as to
999 make subsequent comparisons in fullGtU() complete
1000 faster. For repetitive blocks this makes a big
1001 difference (but not big enough to be able to avoid
1002 the fallback sorting mechanism, exponential radix sort).
1004 The precise meaning is: at all times:
1006 for 0 <= i < nblock and 0 <= j <= nblock
1008 if block[i] != block[j],
1010 then the relative values of quadrant[i] and
1011 quadrant[j] are meaningless.
1014 if quadrant[i] < quadrant[j]
1015 then the string starting at i lexicographically
1016 precedes the string starting at j
1018 else if quadrant[i] > quadrant[j]
1019 then the string starting at j lexicographically
1020 precedes the string starting at i
1023 the relative ordering of the strings starting
1024 at i and j has not yet been determined.
1030 Int32 bbStart = ftab[ss << 8] & CLEARMASK;
1031 Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
1034 while ((bbSize >> shifts) > 65534) shifts++;
1036 for (j = bbSize-1; j >= 0; j--) {
1037 Int32 a2update = ptr[bbStart + j];
1038 UInt16 qVal = (UInt16)(j >> shifts);
1039 quadrant[a2update] = qVal;
1040 if (a2update < BZ_N_OVERSHOOT)
1041 quadrant[a2update + nblock] = qVal;
1043 AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
1049 VPrintf3 ( " %d pointers, %d sorted, %d scanned\n",
1050 nblock, numQSorted, nblock - numQSorted );
1058 /*---------------------------------------------*/
1061 arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
1062 ((UChar*)arr2) [0 .. nblock-1] holds block
1063 arr1 exists for [0 .. nblock-1]
1066 ((UChar*)arr2) [0 .. nblock-1] holds block
1067 All other areas of block destroyed
1068 ftab [ 0 .. 65536 ] destroyed
1069 arr1 [0 .. nblock-1] holds sorted order
1071 void BZ2_blockSort ( EState* s )
1073 UInt32* ptr = s->ptr;
1074 UChar* block = s->block;
1075 UInt32* ftab = s->ftab;
1076 Int32 nblock = s->nblock;
1077 Int32 verb = s->verbosity;
1078 Int32 wfact = s->workFactor;
1084 if (nblock < 10000) {
1085 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1087 /* Calculate the location for quadrant, remembering to get
1088 the alignment right. Assumes that &(block[0]) is at least
1089 2-byte aligned -- this should be ok since block is really
1090 the first section of arr2.
1092 i = nblock+BZ_N_OVERSHOOT;
1094 quadrant = (UInt16*)(&(block[i]));
1096 /* (wfact-1) / 3 puts the default-factor-30
1097 transition point at very roughly the same place as
1098 with v0.1 and v0.9.0.
1099 Not that it particularly matters any more, since the
1100 resulting compressed stream is now the same regardless
1101 of whether or not we use the main sort or fallback sort.
1103 if (wfact < 1 ) wfact = 1;
1104 if (wfact > 100) wfact = 100;
1105 budgetInit = nblock * ((wfact-1) / 3);
1106 budget = budgetInit;
1108 mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
1110 VPrintf3 ( " %d work, %d block, ratio %5.2f\n",
1111 budgetInit - budget,
1113 (float)(budgetInit - budget) /
1114 (float)(nblock==0 ? 1 : nblock) );
1117 VPrintf0 ( " too repetitive; using fallback"
1118 " sorting algorithm\n" );
1119 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1124 for (i = 0; i < s->nblock; i++)
1126 { s->origPtr = i; break; };
1128 AssertH( s->origPtr != -1, 1003 );
1132 /*-------------------------------------------------------------*/
1133 /*--- end blocksort.c ---*/
1134 /*-------------------------------------------------------------*/