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"
65 /*---------------------------------------------*/
66 /*--- Fallback O(N log(N)^2) sorting ---*/
67 /*--- algorithm, for repetitive blocks ---*/
68 /*---------------------------------------------*/
70 /*---------------------------------------------*/
73 void fallbackSimpleSort ( UInt32
* fmap
,
84 for ( i
= hi
-4; i
>= lo
; i
-- ) {
87 for ( j
= i
+4; j
<= hi
&& ec_tmp
> eclass
[fmap
[j
]]; j
+= 4 )
93 for ( i
= hi
-1; i
>= lo
; i
-- ) {
96 for ( j
= i
+1; j
<= hi
&& ec_tmp
> eclass
[fmap
[j
]]; j
++ )
103 /*---------------------------------------------*/
104 #define fswap(zz1, zz2) \
105 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
107 #define fvswap(zzp1, zzp2, zzn) \
109 Int32 yyp1 = (zzp1); \
110 Int32 yyp2 = (zzp2); \
113 fswap(fmap[yyp1], fmap[yyp2]); \
114 yyp1++; yyp2++; yyn--; \
119 #define fmin(a,b) ((a) < (b)) ? (a) : (b)
121 #define fpush(lz,hz) { stackLo[sp] = lz; \
125 #define fpop(lz,hz) { sp--; \
129 #define FALLBACK_QSORT_SMALL_THRESH 10
130 #define FALLBACK_QSORT_STACK_SIZE 100
134 void fallbackQSort3 ( UInt32
* fmap
,
139 Int32 unLo
, unHi
, ltLo
, gtHi
, n
, m
;
142 Int32 stackLo
[FALLBACK_QSORT_STACK_SIZE
];
143 Int32 stackHi
[FALLBACK_QSORT_STACK_SIZE
];
148 fpush ( loSt
, hiSt
);
152 AssertH ( sp
< FALLBACK_QSORT_STACK_SIZE
- 1, 1004 );
155 if (hi
- lo
< FALLBACK_QSORT_SMALL_THRESH
) {
156 fallbackSimpleSort ( fmap
, eclass
, lo
, hi
);
160 /* Random partitioning. Median of 3 sometimes fails to
161 avoid bad cases. Median of 9 seems to help but
162 looks rather expensive. This too seems to work but
163 is cheaper. Guidance for the magic constants
164 7621 and 32768 is taken from Sedgewick's algorithms
167 r
= ((r
* 7621) + 1) % 32768;
169 if (r3
== 0) med
= eclass
[fmap
[lo
]]; else
170 if (r3
== 1) med
= eclass
[fmap
[(lo
+hi
)>>1]]; else
171 med
= eclass
[fmap
[hi
]];
178 if (unLo
> unHi
) break;
179 n
= (Int32
)eclass
[fmap
[unLo
]] - (Int32
)med
;
181 fswap(fmap
[unLo
], fmap
[ltLo
]);
189 if (unLo
> unHi
) break;
190 n
= (Int32
)eclass
[fmap
[unHi
]] - (Int32
)med
;
192 fswap(fmap
[unHi
], fmap
[gtHi
]);
199 if (unLo
> unHi
) break;
200 fswap(fmap
[unLo
], fmap
[unHi
]); unLo
++; unHi
--;
203 AssertD ( unHi
== unLo
-1, "fallbackQSort3(2)" );
205 if (gtHi
< ltLo
) continue;
207 n
= fmin(ltLo
-lo
, unLo
-ltLo
); fvswap(lo
, unLo
-n
, n
);
208 m
= fmin(hi
-gtHi
, gtHi
-unHi
); fvswap(unLo
, hi
-m
+1, m
);
210 n
= lo
+ unLo
- ltLo
- 1;
211 m
= hi
- (gtHi
- unHi
) + 1;
213 if (n
- lo
> hi
- m
) {
228 #undef FALLBACK_QSORT_SMALL_THRESH
229 #undef FALLBACK_QSORT_STACK_SIZE
232 /*---------------------------------------------*/
235 eclass exists for [0 .. nblock-1]
236 ((UChar*)eclass) [0 .. nblock-1] holds block
237 ptr exists for [0 .. nblock-1]
240 ((UChar*)eclass) [0 .. nblock-1] holds block
241 All other areas of eclass destroyed
242 fmap [0 .. nblock-1] holds sorted order
243 bhtab [ 0 .. 2+(nblock/32) ] destroyed
246 #define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
247 #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
248 #define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
249 #define WORD_BH(zz) bhtab[(zz) >> 5]
250 #define UNALIGNED_BH(zz) ((zz) & 0x01f)
253 void fallbackSort ( UInt32
* fmap
,
261 Int32 H
, i
, j
, k
, l
, r
, cc
, cc1
;
264 UChar
* eclass8
= (UChar
*)eclass
;
267 Initial 1-char radix sort to generate
268 initial fmap and initial BH bits.
271 VPrintf0 ( " bucket sorting ...\n" );
272 for (i
= 0; i
< 257; i
++) ftab
[i
] = 0;
273 for (i
= 0; i
< nblock
; i
++) ftab
[eclass8
[i
]]++;
274 for (i
= 0; i
< 256; i
++) ftabCopy
[i
] = ftab
[i
];
275 for (i
= 1; i
< 257; i
++) ftab
[i
] += ftab
[i
-1];
277 for (i
= 0; i
< nblock
; i
++) {
284 nBhtab
= 2 + (nblock
/ 32);
285 for (i
= 0; i
< nBhtab
; i
++) bhtab
[i
] = 0;
286 for (i
= 0; i
< 256; i
++) SET_BH(ftab
[i
]);
289 Inductively refine the buckets. Kind-of an
290 "exponential radix sort" (!), inspired by the
291 Manber-Myers suffix array construction algorithm.
294 /*-- set sentinel bits for block-end detection --*/
295 for (i
= 0; i
< 32; i
++) {
296 SET_BH(nblock
+ 2*i
);
297 CLEAR_BH(nblock
+ 2*i
+ 1);
300 /*-- the log(N) loop --*/
305 VPrintf1 ( " depth %6d has ", H
);
308 for (i
= 0; i
< nblock
; i
++) {
309 if (ISSET_BH(i
)) j
= i
;
310 k
= fmap
[i
] - H
; if (k
< 0) k
+= nblock
;
318 /*-- find the next non-singleton bucket --*/
320 while (ISSET_BH(k
) && UNALIGNED_BH(k
)) k
++;
322 while (WORD_BH(k
) == 0xffffffff) k
+= 32;
323 while (ISSET_BH(k
)) k
++;
326 if (l
>= nblock
) break;
327 while (!ISSET_BH(k
) && UNALIGNED_BH(k
)) k
++;
329 while (WORD_BH(k
) == 0x00000000) k
+= 32;
330 while (!ISSET_BH(k
)) k
++;
333 if (r
>= nblock
) break;
335 /*-- now [l, r] bracket current bucket --*/
337 nNotDone
+= (r
- l
+ 1);
338 fallbackQSort3 ( fmap
, eclass
, l
, r
);
340 /*-- scan bucket and generate header bits-- */
342 for (i
= l
; i
<= r
; i
++) {
343 cc1
= eclass
[fmap
[i
]];
344 if (cc
!= cc1
) { SET_BH(i
); cc
= cc1
; };
350 VPrintf1 ( "%6d unresolved strings\n", nNotDone
);
353 if (H
> nblock
|| nNotDone
== 0) break;
357 Reconstruct the original block in
358 eclass8 [0 .. nblock-1], since the
359 previous phase destroyed it.
362 VPrintf0 ( " reconstructing block ...\n" );
364 for (i
= 0; i
< nblock
; i
++) {
365 while (ftabCopy
[j
] == 0) j
++;
367 eclass8
[fmap
[i
]] = (UChar
)j
;
369 AssertH ( j
< 256, 1005 );
379 /*---------------------------------------------*/
380 /*--- The main, O(N^2 log(N)) sorting ---*/
381 /*--- algorithm. Faster for "normal" ---*/
382 /*--- non-repetitive blocks. ---*/
383 /*---------------------------------------------*/
385 /*---------------------------------------------*/
388 Bool
mainGtU ( UInt32 i1
,
399 AssertD ( i1
!= i2
, "mainGtU" );
401 c1
= block
[i1
]; c2
= block
[i2
];
402 if (c1
!= c2
) return (c1
> c2
);
405 c1
= block
[i1
]; c2
= block
[i2
];
406 if (c1
!= c2
) return (c1
> c2
);
409 c1
= block
[i1
]; c2
= block
[i2
];
410 if (c1
!= c2
) return (c1
> c2
);
413 c1
= block
[i1
]; c2
= block
[i2
];
414 if (c1
!= c2
) return (c1
> c2
);
417 c1
= block
[i1
]; c2
= block
[i2
];
418 if (c1
!= c2
) return (c1
> c2
);
421 c1
= block
[i1
]; c2
= block
[i2
];
422 if (c1
!= c2
) return (c1
> c2
);
425 c1
= block
[i1
]; c2
= block
[i2
];
426 if (c1
!= c2
) return (c1
> c2
);
429 c1
= block
[i1
]; c2
= block
[i2
];
430 if (c1
!= c2
) return (c1
> c2
);
433 c1
= block
[i1
]; c2
= block
[i2
];
434 if (c1
!= c2
) return (c1
> c2
);
437 c1
= block
[i1
]; c2
= block
[i2
];
438 if (c1
!= c2
) return (c1
> c2
);
441 c1
= block
[i1
]; c2
= block
[i2
];
442 if (c1
!= c2
) return (c1
> c2
);
445 c1
= block
[i1
]; c2
= block
[i2
];
446 if (c1
!= c2
) return (c1
> c2
);
453 c1
= block
[i1
]; c2
= block
[i2
];
454 if (c1
!= c2
) return (c1
> c2
);
455 s1
= quadrant
[i1
]; s2
= quadrant
[i2
];
456 if (s1
!= s2
) return (s1
> s2
);
459 c1
= block
[i1
]; c2
= block
[i2
];
460 if (c1
!= c2
) return (c1
> c2
);
461 s1
= quadrant
[i1
]; s2
= quadrant
[i2
];
462 if (s1
!= s2
) return (s1
> s2
);
465 c1
= block
[i1
]; c2
= block
[i2
];
466 if (c1
!= c2
) return (c1
> c2
);
467 s1
= quadrant
[i1
]; s2
= quadrant
[i2
];
468 if (s1
!= s2
) return (s1
> s2
);
471 c1
= block
[i1
]; c2
= block
[i2
];
472 if (c1
!= c2
) return (c1
> c2
);
473 s1
= quadrant
[i1
]; s2
= quadrant
[i2
];
474 if (s1
!= s2
) return (s1
> s2
);
477 c1
= block
[i1
]; c2
= block
[i2
];
478 if (c1
!= c2
) return (c1
> c2
);
479 s1
= quadrant
[i1
]; s2
= quadrant
[i2
];
480 if (s1
!= s2
) return (s1
> s2
);
483 c1
= block
[i1
]; c2
= block
[i2
];
484 if (c1
!= c2
) return (c1
> c2
);
485 s1
= quadrant
[i1
]; s2
= quadrant
[i2
];
486 if (s1
!= s2
) return (s1
> s2
);
489 c1
= block
[i1
]; c2
= block
[i2
];
490 if (c1
!= c2
) return (c1
> c2
);
491 s1
= quadrant
[i1
]; s2
= quadrant
[i2
];
492 if (s1
!= s2
) return (s1
> s2
);
495 c1
= block
[i1
]; c2
= block
[i2
];
496 if (c1
!= c2
) return (c1
> c2
);
497 s1
= quadrant
[i1
]; s2
= quadrant
[i2
];
498 if (s1
!= s2
) return (s1
> s2
);
501 if (i1
>= nblock
) i1
-= nblock
;
502 if (i2
>= nblock
) i2
-= nblock
;
513 /*---------------------------------------------*/
515 Knuth's increments seem to work better
516 than Incerpi-Sedgewick here. Possibly
517 because the number of elems to sort is
518 usually small, typically <= 20.
521 Int32 incs
[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
522 9841, 29524, 88573, 265720,
526 void mainSimpleSort ( UInt32
* ptr
,
535 Int32 i
, j
, h
, bigN
, hp
;
539 if (bigN
< 2) return;
542 while (incs
[hp
] < bigN
) hp
++;
545 for (; hp
>= 0; hp
--) {
556 ptr
[j
-h
]+d
, v
+d
, block
, quadrant
, nblock
, budget
560 if (j
<= (lo
+ h
- 1)) break;
570 ptr
[j
-h
]+d
, v
+d
, block
, quadrant
, nblock
, budget
574 if (j
<= (lo
+ h
- 1)) break;
584 ptr
[j
-h
]+d
, v
+d
, block
, quadrant
, nblock
, budget
588 if (j
<= (lo
+ h
- 1)) break;
593 if (*budget
< 0) return;
599 /*---------------------------------------------*/
601 The following is an implementation of
602 an elegant 3-way quicksort for strings,
603 described in a paper "Fast Algorithms for
604 Sorting and Searching Strings", by Robert
605 Sedgewick and Jon L. Bentley.
608 #define mswap(zz1, zz2) \
609 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
611 #define mvswap(zzp1, zzp2, zzn) \
613 Int32 yyp1 = (zzp1); \
614 Int32 yyp2 = (zzp2); \
617 mswap(ptr[yyp1], ptr[yyp2]); \
618 yyp1++; yyp2++; yyn--; \
624 UChar
mmed3 ( UChar a
, UChar b
, UChar c
)
627 if (a
> b
) { t
= a
; a
= b
; b
= t
; };
635 #define mmin(a,b) ((a) < (b)) ? (a) : (b)
637 #define mpush(lz,hz,dz) { stackLo[sp] = lz; \
642 #define mpop(lz,hz,dz) { sp--; \
648 #define mnextsize(az) (nextHi[az]-nextLo[az])
650 #define mnextswap(az,bz) \
652 tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
653 tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
654 tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
657 #define MAIN_QSORT_SMALL_THRESH 20
658 #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
659 #define MAIN_QSORT_STACK_SIZE 100
662 void mainQSort3 ( UInt32
* ptr
,
671 Int32 unLo
, unHi
, ltLo
, gtHi
, n
, m
, med
;
674 Int32 stackLo
[MAIN_QSORT_STACK_SIZE
];
675 Int32 stackHi
[MAIN_QSORT_STACK_SIZE
];
676 Int32 stackD
[MAIN_QSORT_STACK_SIZE
];
683 mpush ( loSt
, hiSt
, dSt
);
687 AssertH ( sp
< MAIN_QSORT_STACK_SIZE
- 2, 1001 );
690 if (hi
- lo
< MAIN_QSORT_SMALL_THRESH
||
691 d
> MAIN_QSORT_DEPTH_THRESH
) {
692 mainSimpleSort ( ptr
, block
, quadrant
, nblock
, lo
, hi
, d
, budget
);
693 if (*budget
< 0) return;
698 mmed3 ( block
[ptr
[ lo
]+d
],
700 block
[ptr
[ (lo
+hi
)>>1 ]+d
] );
707 if (unLo
> unHi
) break;
708 n
= ((Int32
)block
[ptr
[unLo
]+d
]) - med
;
710 mswap(ptr
[unLo
], ptr
[ltLo
]);
711 ltLo
++; unLo
++; continue;
717 if (unLo
> unHi
) break;
718 n
= ((Int32
)block
[ptr
[unHi
]+d
]) - med
;
720 mswap(ptr
[unHi
], ptr
[gtHi
]);
721 gtHi
--; unHi
--; continue;
726 if (unLo
> unHi
) break;
727 mswap(ptr
[unLo
], ptr
[unHi
]); unLo
++; unHi
--;
730 AssertD ( unHi
== unLo
-1, "mainQSort3(2)" );
737 n
= mmin(ltLo
-lo
, unLo
-ltLo
); mvswap(lo
, unLo
-n
, n
);
738 m
= mmin(hi
-gtHi
, gtHi
-unHi
); mvswap(unLo
, hi
-m
+1, m
);
740 n
= lo
+ unLo
- ltLo
- 1;
741 m
= hi
- (gtHi
- unHi
) + 1;
743 nextLo
[0] = lo
; nextHi
[0] = n
; nextD
[0] = d
;
744 nextLo
[1] = m
; nextHi
[1] = hi
; nextD
[1] = d
;
745 nextLo
[2] = n
+1; nextHi
[2] = m
-1; nextD
[2] = d
+1;
747 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
748 if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
749 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
751 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );
752 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );
754 mpush (nextLo
[0], nextHi
[0], nextD
[0]);
755 mpush (nextLo
[1], nextHi
[1], nextD
[1]);
756 mpush (nextLo
[2], nextHi
[2], nextD
[2]);
767 #undef MAIN_QSORT_SMALL_THRESH
768 #undef MAIN_QSORT_DEPTH_THRESH
769 #undef MAIN_QSORT_STACK_SIZE
772 /*---------------------------------------------*/
775 block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
776 ((UChar*)block32) [0 .. nblock-1] holds block
777 ptr exists for [0 .. nblock-1]
780 ((UChar*)block32) [0 .. nblock-1] holds block
781 All other areas of block32 destroyed
782 ftab [0 .. 65536 ] destroyed
783 ptr [0 .. nblock-1] holds sorted order
784 if (*budget < 0), sorting was abandoned
787 #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
788 #define SETMASK (1 << 21)
789 #define CLEARMASK (~(SETMASK))
792 void mainSort ( UInt32
* ptr
,
800 Int32 i
, j
, k
, ss
, sb
;
801 Int32 runningOrder
[256];
803 Int32 copyStart
[256];
808 if (verb
>= 4) VPrintf0 ( " main sort initialise ...\n" );
810 /*-- set up the 2-byte frequency table --*/
811 for (i
= 65536; i
>= 0; i
--) ftab
[i
] = 0;
815 for (; i
>= 3; i
-= 4) {
817 j
= (j
>> 8) | ( ((UInt16
)block
[i
]) << 8);
820 j
= (j
>> 8) | ( ((UInt16
)block
[i
-1]) << 8);
823 j
= (j
>> 8) | ( ((UInt16
)block
[i
-2]) << 8);
826 j
= (j
>> 8) | ( ((UInt16
)block
[i
-3]) << 8);
829 for (; i
>= 0; i
--) {
831 j
= (j
>> 8) | ( ((UInt16
)block
[i
]) << 8);
835 /*-- (emphasises close relationship of block & quadrant) --*/
836 for (i
= 0; i
< BZ_N_OVERSHOOT
; i
++) {
837 block
[nblock
+i
] = block
[i
];
838 quadrant
[nblock
+i
] = 0;
841 if (verb
>= 4) VPrintf0 ( " bucket sorting ...\n" );
843 /*-- Complete the initial radix sort --*/
844 for (i
= 1; i
<= 65536; i
++) ftab
[i
] += ftab
[i
-1];
848 for (; i
>= 3; i
-= 4) {
849 s
= (s
>> 8) | (block
[i
] << 8);
853 s
= (s
>> 8) | (block
[i
-1] << 8);
857 s
= (s
>> 8) | (block
[i
-2] << 8);
861 s
= (s
>> 8) | (block
[i
-3] << 8);
866 for (; i
>= 0; i
--) {
867 s
= (s
>> 8) | (block
[i
] << 8);
874 Now ftab contains the first loc of every small bucket.
875 Calculate the running order, from smallest to largest
878 for (i
= 0; i
<= 255; i
++) {
886 do h
= 3 * h
+ 1; while (h
<= 256);
889 for (i
= h
; i
<= 255; i
++) {
890 vv
= runningOrder
[i
];
892 while ( BIGFREQ(runningOrder
[j
-h
]) > BIGFREQ(vv
) ) {
893 runningOrder
[j
] = runningOrder
[j
-h
];
895 if (j
<= (h
- 1)) goto zero
;
898 runningOrder
[j
] = vv
;
904 The main sorting loop.
909 for (i
= 0; i
<= 255; i
++) {
912 Process big buckets, starting with the least full.
913 Basically this is a 3-step process in which we call
914 mainQSort3 to sort the small buckets [ss, j], but
915 also make a big effort to avoid the calls if we can.
917 ss
= runningOrder
[i
];
921 Complete the big bucket [ss] by quicksorting
922 any unsorted small buckets [ss, j], for j != ss.
923 Hopefully previous pointer-scanning phases have already
924 completed many of the small buckets [ss, j], so
925 we don't have to sort them at all.
927 for (j
= 0; j
<= 255; j
++) {
930 if ( ! (ftab
[sb
] & SETMASK
) ) {
931 Int32 lo
= ftab
[sb
] & CLEARMASK
;
932 Int32 hi
= (ftab
[sb
+1] & CLEARMASK
) - 1;
935 VPrintf4 ( " qsort [0x%x, 0x%x] "
937 ss
, j
, numQSorted
, hi
- lo
+ 1 );
939 ptr
, block
, quadrant
, nblock
,
940 lo
, hi
, BZ_N_RADIX
, budget
942 numQSorted
+= (hi
- lo
+ 1);
943 if (*budget
< 0) return;
950 AssertH ( !bigDone
[ss
], 1006 );
954 Now scan this big bucket [ss] so as to synthesise the
955 sorted order for small buckets [t, ss] for all t,
956 including, magically, the bucket [ss,ss] too.
957 This will avoid doing Real Work in subsequent Step 1's.
960 for (j
= 0; j
<= 255; j
++) {
961 copyStart
[j
] = ftab
[(j
<< 8) + ss
] & CLEARMASK
;
962 copyEnd
[j
] = (ftab
[(j
<< 8) + ss
+ 1] & CLEARMASK
) - 1;
964 for (j
= ftab
[ss
<< 8] & CLEARMASK
; j
< copyStart
[ss
]; j
++) {
965 k
= ptr
[j
]-1; if (k
< 0) k
+= nblock
;
968 ptr
[ copyStart
[c1
]++ ] = k
;
970 for (j
= (ftab
[(ss
+1) << 8] & CLEARMASK
) - 1; j
> copyEnd
[ss
]; j
--) {
971 k
= ptr
[j
]-1; if (k
< 0) k
+= nblock
;
974 ptr
[ copyEnd
[c1
]-- ] = k
;
978 AssertH ( (copyStart
[ss
]-1 == copyEnd
[ss
])
980 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
981 Necessity for this case is demonstrated by compressing
982 a sequence of approximately 48.5 million of character
983 251; 1.0.0/1.0.1 will then die here. */
984 (copyStart
[ss
] == 0 && copyEnd
[ss
] == nblock
-1),
987 for (j
= 0; j
<= 255; j
++) ftab
[(j
<< 8) + ss
] |= SETMASK
;
991 The [ss] big bucket is now done. Record this fact,
992 and update the quadrant descriptors. Remember to
993 update quadrants in the overshoot area too, if
994 necessary. The "if (i < 255)" test merely skips
995 this updating for the last bucket processed, since
996 updating for the last bucket is pointless.
998 The quadrant array provides a way to incrementally
999 cache sort orderings, as they appear, so as to
1000 make subsequent comparisons in fullGtU() complete
1001 faster. For repetitive blocks this makes a big
1002 difference (but not big enough to be able to avoid
1003 the fallback sorting mechanism, exponential radix sort).
1005 The precise meaning is: at all times:
1007 for 0 <= i < nblock and 0 <= j <= nblock
1009 if block[i] != block[j],
1011 then the relative values of quadrant[i] and
1012 quadrant[j] are meaningless.
1015 if quadrant[i] < quadrant[j]
1016 then the string starting at i lexicographically
1017 precedes the string starting at j
1019 else if quadrant[i] > quadrant[j]
1020 then the string starting at j lexicographically
1021 precedes the string starting at i
1024 the relative ordering of the strings starting
1025 at i and j has not yet been determined.
1031 Int32 bbStart
= ftab
[ss
<< 8] & CLEARMASK
;
1032 Int32 bbSize
= (ftab
[(ss
+1) << 8] & CLEARMASK
) - bbStart
;
1035 while ((bbSize
>> shifts
) > 65534) shifts
++;
1037 for (j
= bbSize
-1; j
>= 0; j
--) {
1038 Int32 a2update
= ptr
[bbStart
+ j
];
1039 UInt16 qVal
= (UInt16
)(j
>> shifts
);
1040 quadrant
[a2update
] = qVal
;
1041 if (a2update
< BZ_N_OVERSHOOT
)
1042 quadrant
[a2update
+ nblock
] = qVal
;
1044 AssertH ( ((bbSize
-1) >> shifts
) <= 65535, 1002 );
1050 VPrintf3 ( " %d pointers, %d sorted, %d scanned\n",
1051 nblock
, numQSorted
, nblock
- numQSorted
);
1059 /*---------------------------------------------*/
1062 arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
1063 ((UChar*)arr2) [0 .. nblock-1] holds block
1064 arr1 exists for [0 .. nblock-1]
1067 ((UChar*)arr2) [0 .. nblock-1] holds block
1068 All other areas of block destroyed
1069 ftab [ 0 .. 65536 ] destroyed
1070 arr1 [0 .. nblock-1] holds sorted order
1072 void BZ2_blockSort ( EState
* s
)
1074 UInt32
* ptr
= s
->ptr
;
1075 UChar
* block
= s
->block
;
1076 UInt32
* ftab
= s
->ftab
;
1077 Int32 nblock
= s
->nblock
;
1078 Int32 verb
= s
->verbosity
;
1079 Int32 wfact
= s
->workFactor
;
1085 if (nblock
< 10000) {
1086 fallbackSort ( s
->arr1
, s
->arr2
, ftab
, nblock
, verb
);
1088 /* Calculate the location for quadrant, remembering to get
1089 the alignment right. Assumes that &(block[0]) is at least
1090 2-byte aligned -- this should be ok since block is really
1091 the first section of arr2.
1093 i
= nblock
+BZ_N_OVERSHOOT
;
1095 quadrant
= (UInt16
*)(&(block
[i
]));
1097 /* (wfact-1) / 3 puts the default-factor-30
1098 transition point at very roughly the same place as
1099 with v0.1 and v0.9.0.
1100 Not that it particularly matters any more, since the
1101 resulting compressed stream is now the same regardless
1102 of whether or not we use the main sort or fallback sort.
1104 if (wfact
< 1 ) wfact
= 1;
1105 if (wfact
> 100) wfact
= 100;
1106 budgetInit
= nblock
* ((wfact
-1) / 3);
1107 budget
= budgetInit
;
1109 mainSort ( ptr
, block
, quadrant
, ftab
, nblock
, verb
, &budget
);
1111 VPrintf3 ( " %d work, %d block, ratio %5.2f\n",
1112 budgetInit
- budget
,
1114 (float)(budgetInit
- budget
) /
1115 (float)(nblock
==0 ? 1 : nblock
) );
1118 VPrintf0 ( " too repetitive; using fallback"
1119 " sorting algorithm\n" );
1120 fallbackSort ( s
->arr1
, s
->arr2
, ftab
, nblock
, verb
);
1125 for (i
= 0; i
< s
->nblock
; i
++)
1127 { s
->origPtr
= i
; break; };
1129 AssertH( s
->origPtr
!= -1, 1003 );
1133 /*-------------------------------------------------------------*/
1134 /*--- end blocksort.c ---*/
1135 /*-------------------------------------------------------------*/