#include "bzlib_private.h"
Go to the source code of this file.
Defines | |
#define | fswap(zz1, zz2) { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } |
#define | fvswap(zzp1, zzp2, zzn) |
#define | fmin(a, b) ((a) < (b)) ? (a) : (b) |
#define | fpush(lz, hz) |
#define | fpop(lz, hz) |
#define | FALLBACK_QSORT_SMALL_THRESH 10 |
#define | FALLBACK_QSORT_STACK_SIZE 100 |
#define | SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31)) |
#define | CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31)) |
#define | ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31))) |
#define | WORD_BH(zz) bhtab[(zz) >> 5] |
#define | UNALIGNED_BH(zz) ((zz) & 0x01f) |
#define | mswap(zz1, zz2) { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } |
#define | mvswap(zzp1, zzp2, zzn) |
#define | mmin(a, b) ((a) < (b)) ? (a) : (b) |
#define | mpush(lz, hz, dz) |
#define | mpop(lz, hz, dz) |
#define | mnextsize(az) (nextHi[az]-nextLo[az]) |
#define | mnextswap(az, bz) |
#define | MAIN_QSORT_SMALL_THRESH 20 |
#define | MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT) |
#define | MAIN_QSORT_STACK_SIZE 100 |
#define | BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8]) |
#define | SETMASK (1 << 21) |
#define | CLEARMASK (~(SETMASK)) |
Functions | |
__inline__ void | fallbackSimpleSort (UInt32 *fmap, UInt32 *eclass, Int32 lo, Int32 hi) |
void | fallbackQSort3 (UInt32 *fmap, UInt32 *eclass, Int32 loSt, Int32 hiSt) |
void | fallbackSort (UInt32 *fmap, UInt32 *eclass, UInt32 *bhtab, Int32 nblock, Int32 verb) |
__inline__ Bool | mainGtU (UInt32 i1, UInt32 i2, UInt16 *block, UInt16 *quadrant, UInt32 nblock, Int32 *budget) |
void | mainSimpleSort (UInt32 *ptr, UInt16 *block, UInt16 *quadrant, Int32 nblock, Int32 lo, Int32 hi, Int32 d, Int32 *budget) |
__inline__ UInt16 | mmed3 (UInt16 a, UInt16 b, UInt16 c) |
void | mainQSort3 (UInt32 *ptr, UInt16 *block, UInt16 *quadrant, Int32 nblock, Int32 loSt, Int32 hiSt, Int32 dSt, Int32 *budget) |
void | mainSort (UInt32 *ptr, UInt16 *block, UInt16 *quadrant, UInt32 *ftab, Int32 nblock, Int32 verb, Int32 *budget) |
void | blockSort (EState *s) |
Variables | |
Int32 | incs [14] |
|
Definition at line 736 of file blocksort.c. Referenced by mainSort().
|
|
Definition at line 738 of file blocksort.c. |
|
Definition at line 246 of file blocksort.c. Referenced by fallbackSort().
|
|
Definition at line 128 of file blocksort.c. |
|
Definition at line 129 of file blocksort.c. |
|
Definition at line 247 of file blocksort.c. Referenced by fallbackSort().
|
|
Definition at line 607 of file blocksort.c. |
|
Definition at line 606 of file blocksort.c. |
|
Definition at line 608 of file blocksort.c. |
|
Definition at line 737 of file blocksort.c. |
|
Definition at line 245 of file blocksort.c. Referenced by fallbackSort().
|
|
Definition at line 249 of file blocksort.c. Referenced by fallbackSort().
|
|
Definition at line 248 of file blocksort.c. Referenced by fallbackSort().
|
|
Definition at line 118 of file blocksort.c. Referenced by fallbackQSort3().
|
|
Value: { sp--; \ lz = stackLo[sp]; \ hz = stackHi[sp]; } Definition at line 124 of file blocksort.c. Referenced by fallbackQSort3().
|
|
Value: { stackLo[sp] = lz; \ stackHi[sp] = hz; \ sp++; } Definition at line 120 of file blocksort.c. Referenced by fallbackQSort3().
|
|
Definition at line 103 of file blocksort.c. Referenced by fallbackQSort3().
|
|
Value: { \ Int32 yyp1 = (zzp1); \ Int32 yyp2 = (zzp2); \ Int32 yyn = (zzn); \ while (yyn > 0) { \ fswap(fmap[yyp1], fmap[yyp2]); \ yyp1++; yyp2++; yyn--; \ } \ } Definition at line 106 of file blocksort.c. Referenced by fallbackQSort3().
|
|
Definition at line 584 of file blocksort.c. Referenced by mainQSort3().
|
|
Definition at line 597 of file blocksort.c. Referenced by mainQSort3().
|
|
Value: { Int32 tz; \ tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \ tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \ tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; } Definition at line 599 of file blocksort.c. Referenced by mainQSort3().
|
|
Value: { sp--; \ lz = stackLo[sp]; \ hz = stackHi[sp]; \ dz = stackD [sp]; } Definition at line 591 of file blocksort.c. Referenced by mainQSort3().
|
|
Value: { stackLo[sp] = lz; \ stackHi[sp] = hz; \ stackD [sp] = dz; \ sp++; } Definition at line 586 of file blocksort.c. Referenced by mainQSort3().
|
|
Definition at line 557 of file blocksort.c. Referenced by mainQSort3().
|
|
Value: { \ Int32 yyp1 = (zzp1); \ Int32 yyp2 = (zzp2); \ Int32 yyn = (zzn); \ while (yyn > 0) { \ mswap(ptr[yyp1], ptr[yyp2]); \ yyp1++; yyp2++; yyn--; \ } \ } Definition at line 560 of file blocksort.c. Referenced by mainQSort3().
|
|
Definition at line 1017 of file blocksort.c. 01018 { 01019 UInt32* ptr = s->ptr; 01020 UInt16* block = s->block; 01021 UInt32* ftab = s->ftab; 01022 Int32 nblock = s->nblock; 01023 Int32 verb = s->verbosity; 01024 Int32 wfact = s->workFactor; 01025 UInt16* quadrant; 01026 Int32 budget; 01027 Int32 budgetInit; 01028 Int32 i; 01029 01030 if (nblock < 10000) { 01031 for (i = 0; i < nblock; i++) block[i] <<= 8; 01032 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); 01033 } else { 01034 quadrant = &(block[nblock+BZ_N_OVERSHOOT]); 01035 01036 /* (wfact-1) / 3 puts the default-factor-30 01037 transition point at very roughly the same place as 01038 with v0.1 and v0.9.0. 01039 Not that it particularly matters any more, since the 01040 resulting compressed stream is now the same regardless 01041 of whether or not we use the main sort or fallback sort. 01042 */ 01043 if (wfact < 1 ) wfact = 1; 01044 if (wfact > 100) wfact = 100; 01045 budgetInit = nblock * ((wfact-1) / 3); 01046 budget = budgetInit; 01047 01048 mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget ); 01049 if (verb >= 3) 01050 VPrintf3 ( " %d work, %d block, ratio %5.2f\n", 01051 budgetInit - budget, 01052 nblock, 01053 (float)(budgetInit - budget) / 01054 (float)(nblock==0 ? 1 : nblock) ); 01055 if (budget < 0) { 01056 if (verb >= 2) 01057 VPrintf0 ( " too repetitive; using fallback" 01058 " sorting algorithm\n" ); 01059 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); 01060 } 01061 } 01062 01063 s->origPtr = -1; 01064 for (i = 0; i < s->nblock; i++) 01065 if (ptr[i] == 0) 01066 { s->origPtr = i; break; }; 01067 01068 AssertH( s->origPtr != -1, 1003 ); 01069 } |
|
Definition at line 133 of file blocksort.c. Referenced by fallbackSort().
00137 { 00138 Int32 unLo, unHi, ltLo, gtHi, n, m; 00139 Int32 sp, lo, hi; 00140 UInt32 med, r, r3; 00141 Int32 stackLo[FALLBACK_QSORT_STACK_SIZE]; 00142 Int32 stackHi[FALLBACK_QSORT_STACK_SIZE]; 00143 00144 r = 0; 00145 00146 sp = 0; 00147 fpush ( loSt, hiSt ); 00148 00149 while (sp > 0) { 00150 00151 AssertH ( sp < FALLBACK_QSORT_STACK_SIZE, 1004 ); 00152 00153 fpop ( lo, hi ); 00154 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) { 00155 fallbackSimpleSort ( fmap, eclass, lo, hi ); 00156 continue; 00157 } 00158 00159 /* Random partitioning. Median of 3 sometimes fails to 00160 avoid bad cases. Median of 9 seems to help but 00161 looks rather expensive. This too seems to work but 00162 is cheaper. Guidance for the magic constants 00163 7621 and 32768 is taken from Sedgewick's algorithms 00164 book, chapter 35. 00165 */ 00166 r = ((r * 7621) + 1) % 32768; 00167 r3 = r % 3; 00168 if (r3 == 0) med = eclass[fmap[lo]]; else 00169 if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else 00170 med = eclass[fmap[hi]]; 00171 00172 unLo = ltLo = lo; 00173 unHi = gtHi = hi; 00174 00175 while (1) { 00176 while (1) { 00177 if (unLo > unHi) break; 00178 n = (Int32)eclass[fmap[unLo]] - (Int32)med; 00179 if (n == 0) { 00180 fswap(fmap[unLo], fmap[ltLo]); 00181 ltLo++; unLo++; 00182 continue; 00183 }; 00184 if (n > 0) break; 00185 unLo++; 00186 } 00187 while (1) { 00188 if (unLo > unHi) break; 00189 n = eclass[fmap[unHi]] - med; 00190 if (n == 0) { 00191 fswap(fmap[unHi], fmap[gtHi]); 00192 gtHi--; unHi--; 00193 continue; 00194 }; 00195 if (n < 0) break; 00196 unHi--; 00197 } 00198 if (unLo > unHi) break; 00199 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--; 00200 } 00201 00202 AssertD ( unHi == unLo-1, "fallbackQSort3(2)" ); 00203 00204 if (gtHi < ltLo) continue; 00205 00206 n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n); 00207 m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m); 00208 00209 n = lo + unLo - ltLo - 1; 00210 m = hi - (gtHi - unHi) + 1; 00211 00212 if (n - lo > hi - m) { 00213 fpush ( lo, n ); 00214 fpush ( m, hi ); 00215 } else { 00216 fpush ( m, hi ); 00217 fpush ( lo, n ); 00218 } 00219 } 00220 } |
|
Definition at line 72 of file blocksort.c. Referenced by fallbackQSort3().
00076 { 00077 Int32 i, j, tmp; 00078 UInt32 ec_tmp; 00079 00080 if (lo == hi) return; 00081 00082 if (hi - lo > 3) { 00083 for ( i = hi-4; i >= lo; i-- ) { 00084 tmp = fmap[i]; 00085 ec_tmp = eclass[tmp]; 00086 for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 ) 00087 fmap[j-4] = fmap[j]; 00088 fmap[j-4] = tmp; 00089 } 00090 } 00091 00092 for ( i = hi-1; i >= lo; i-- ) { 00093 tmp = fmap[i]; 00094 ec_tmp = eclass[tmp]; 00095 for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ ) 00096 fmap[j-1] = fmap[j]; 00097 fmap[j-1] = tmp; 00098 } 00099 } |
|
Definition at line 252 of file blocksort.c. Referenced by blockSort().
00257 { 00258 Int32 ftab[257]; 00259 Int32 ftabCopy[256]; 00260 Int32 H, i, j, k, l, r, cc, cc1; 00261 Int32 nNotDone; 00262 Int32 nBhtab; 00263 UInt16* eclass16 = (UInt16*)eclass; 00264 00265 /*-- 00266 Initial 1-char radix sort to generate 00267 initial fmap and initial BH bits. 00268 --*/ 00269 if (verb >= 4) 00270 VPrintf0 ( " bucket sorting ...\n" ); 00271 for (i = 0; i < 257; i++) ftab[i] = 0; 00272 for (i = 0; i < nblock; i++) ftab[eclass16[i] >> 8]++; 00273 for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i]; 00274 for (i = 1; i < 257; i++) ftab[i] += ftab[i-1]; 00275 00276 for (i = 0; i < nblock; i++) { 00277 j = eclass16[i] >> 8; 00278 k = ftab[j] - 1; 00279 ftab[j] = k; 00280 fmap[k] = i; 00281 } 00282 00283 nBhtab = 2 + (nblock / 32); 00284 for (i = 0; i < nBhtab; i++) bhtab[i] = 0; 00285 for (i = 0; i < 256; i++) SET_BH(ftab[i]); 00286 00287 /*-- 00288 Inductively refine the buckets. Kind-of an 00289 "exponential radix sort" (!), inspired by the 00290 Manber-Myers suffix array construction algorithm. 00291 --*/ 00292 00293 /*-- set sentinel bits for block-end detection --*/ 00294 for (i = 0; i < 32; i++) { 00295 SET_BH(nblock + 2*i); 00296 CLEAR_BH(nblock + 2*i + 1); 00297 } 00298 00299 /*-- the log(N) loop --*/ 00300 H = 1; 00301 while (1) { 00302 00303 if (verb >= 4) 00304 VPrintf1 ( " depth %6d has ", H ); 00305 00306 j = 0; 00307 for (i = 0; i < nblock; i++) { 00308 if (ISSET_BH(i)) j = i; 00309 k = fmap[i] - H; if (k < 0) k += nblock; 00310 eclass[k] = j; 00311 } 00312 00313 nNotDone = 0; 00314 r = -1; 00315 while (1) { 00316 00317 /*-- find the next non-singleton bucket --*/ 00318 k = r + 1; 00319 while (ISSET_BH(k) && UNALIGNED_BH(k)) k++; 00320 if (ISSET_BH(k)) { 00321 while (WORD_BH(k) == 0xffffffff) k += 32; 00322 while (ISSET_BH(k)) k++; 00323 } 00324 l = k - 1; 00325 if (l >= nblock) break; 00326 while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++; 00327 if (!ISSET_BH(k)) { 00328 while (WORD_BH(k) == 0x00000000) k += 32; 00329 while (!ISSET_BH(k)) k++; 00330 } 00331 r = k - 1; 00332 if (r >= nblock) break; 00333 00334 /*-- now [l, r] bracket current bucket --*/ 00335 if (r > l) { 00336 nNotDone += (r - l + 1); 00337 fallbackQSort3 ( fmap, eclass, l, r ); 00338 00339 /*-- scan bucket and generate header bits-- */ 00340 cc = -1; 00341 for (i = l; i <= r; i++) { 00342 cc1 = eclass[fmap[i]]; 00343 if (cc != cc1) { SET_BH(i); cc = cc1; }; 00344 } 00345 } 00346 } 00347 00348 if (verb >= 4) 00349 VPrintf1 ( "%6d unresolved strings\n", nNotDone ); 00350 00351 H *= 2; 00352 if (H > nblock || nNotDone == 0) break; 00353 } 00354 00355 /*-- 00356 Reconstruct the original block in 00357 eclass16 [0 .. nblock-1] [15:8], since the 00358 previous phase destroyed it. 00359 --*/ 00360 if (verb >= 4) 00361 VPrintf0 ( " reconstructing block ...\n" ); 00362 j = 0; 00363 for (i = 0; i < nblock; i++) { 00364 while (ftabCopy[j] == 0) j++; 00365 ftabCopy[j]--; 00366 eclass16[fmap[i]] = j << 8; 00367 } 00368 AssertH ( j < 256, 1005 ); 00369 } |
|
Definition at line 387 of file blocksort.c. Referenced by mainSimpleSort().
00393 { 00394 Int32 k; 00395 UInt16 s1, s2; 00396 00397 AssertD ( i1 != i2, "mainGtU" ); 00398 00399 s1 = block[i1]; s2 = block[i2]; 00400 if (s1 != s2) return (s1 > s2); 00401 i1 += 2; i2 += 2; 00402 00403 s1 = block[i1]; s2 = block[i2]; 00404 if (s1 != s2) return (s1 > s2); 00405 i1 += 2; i2 += 2; 00406 00407 s1 = block[i1]; s2 = block[i2]; 00408 if (s1 != s2) return (s1 > s2); 00409 i1 += 2; i2 += 2; 00410 00411 s1 = block[i1]; s2 = block[i2]; 00412 if (s1 != s2) return (s1 > s2); 00413 i1 += 2; i2 += 2; 00414 00415 s1 = block[i1]; s2 = block[i2]; 00416 if (s1 != s2) return (s1 > s2); 00417 i1 += 2; i2 += 2; 00418 00419 s1 = block[i1]; s2 = block[i2]; 00420 if (s1 != s2) return (s1 > s2); 00421 i1 += 2; i2 += 2; 00422 00423 k = nblock + 8; 00424 00425 do { 00426 00427 s1 = block[i1]; s2 = block[i2]; 00428 if (s1 != s2) return (s1 > s2); 00429 s1 = quadrant[i1]; s2 = quadrant[i2]; 00430 if (s1 != s2) return (s1 > s2); 00431 i1 += 2; i2 += 2; 00432 00433 s1 = block[i1]; s2 = block[i2]; 00434 if (s1 != s2) return (s1 > s2); 00435 s1 = quadrant[i1]; s2 = quadrant[i2]; 00436 if (s1 != s2) return (s1 > s2); 00437 i1 += 2; i2 += 2; 00438 00439 s1 = block[i1]; s2 = block[i2]; 00440 if (s1 != s2) return (s1 > s2); 00441 s1 = quadrant[i1]; s2 = quadrant[i2]; 00442 if (s1 != s2) return (s1 > s2); 00443 i1 += 2; i2 += 2; 00444 00445 s1 = block[i1]; s2 = block[i2]; 00446 if (s1 != s2) return (s1 > s2); 00447 s1 = quadrant[i1]; s2 = quadrant[i2]; 00448 if (s1 != s2) return (s1 > s2); 00449 i1 += 2; i2 += 2; 00450 00451 if (i1 >= nblock) i1 -= nblock; 00452 if (i2 >= nblock) i2 -= nblock; 00453 00454 k -= 8; 00455 (*budget)--; 00456 } 00457 while (k >= 0); 00458 00459 return False; 00460 } |
|
Definition at line 611 of file blocksort.c. Referenced by mainSort().
00619 { 00620 Int32 unLo, unHi, ltLo, gtHi, n, m, med; 00621 Int32 sp, lo, hi, d; 00622 00623 Int32 stackLo[MAIN_QSORT_STACK_SIZE]; 00624 Int32 stackHi[MAIN_QSORT_STACK_SIZE]; 00625 Int32 stackD [MAIN_QSORT_STACK_SIZE]; 00626 00627 Int32 nextLo[3]; 00628 Int32 nextHi[3]; 00629 Int32 nextD [3]; 00630 00631 sp = 0; 00632 mpush ( loSt, hiSt, dSt ); 00633 00634 while (sp > 0) { 00635 00636 AssertH ( sp < MAIN_QSORT_STACK_SIZE, 1001 ); 00637 00638 mpop ( lo, hi, d ); 00639 if (hi - lo < MAIN_QSORT_SMALL_THRESH || 00640 d > MAIN_QSORT_DEPTH_THRESH) { 00641 mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget ); 00642 if (*budget < 0) return; 00643 continue; 00644 } 00645 00646 med = (Int32) 00647 mmed3 ( block[ptr[ lo ]+d], 00648 block[ptr[ hi ]+d], 00649 block[ptr[ (lo+hi)>>1 ]+d] ); 00650 00651 unLo = ltLo = lo; 00652 unHi = gtHi = hi; 00653 00654 while (True) { 00655 while (True) { 00656 if (unLo > unHi) break; 00657 n = ((Int32)block[ptr[unLo]+d]) - med; 00658 if (n == 0) { 00659 mswap(ptr[unLo], ptr[ltLo]); 00660 ltLo++; unLo++; continue; 00661 }; 00662 if (n > 0) break; 00663 unLo++; 00664 } 00665 while (True) { 00666 if (unLo > unHi) break; 00667 n = ((Int32)block[ptr[unHi]+d]) - med; 00668 if (n == 0) { 00669 mswap(ptr[unHi], ptr[gtHi]); 00670 gtHi--; unHi--; continue; 00671 }; 00672 if (n < 0) break; 00673 unHi--; 00674 } 00675 if (unLo > unHi) break; 00676 mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--; 00677 } 00678 00679 AssertD ( unHi == unLo-1, "mainQSort3(2)" ); 00680 00681 if (gtHi < ltLo) { 00682 mpush(lo, hi, d+2 ); 00683 continue; 00684 } 00685 00686 n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n); 00687 m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m); 00688 00689 n = lo + unLo - ltLo - 1; 00690 m = hi - (gtHi - unHi) + 1; 00691 00692 nextLo[0] = lo; nextHi[0] = n; nextD[0] = d; 00693 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d; 00694 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+2; 00695 00696 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); 00697 if (mnextsize(1) < mnextsize(2)) mnextswap(1,2); 00698 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); 00699 00700 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" ); 00701 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" ); 00702 00703 mpush (nextLo[0], nextHi[0], nextD[0]); 00704 mpush (nextLo[1], nextHi[1], nextD[1]); 00705 mpush (nextLo[2], nextHi[2], nextD[2]); 00706 } 00707 } |
|
Definition at line 475 of file blocksort.c. Referenced by mainQSort3().
00483 { 00484 Int32 i, j, h, bigN, hp; 00485 UInt32 v; 00486 00487 bigN = hi - lo + 1; 00488 if (bigN < 2) return; 00489 00490 hp = 0; 00491 while (incs[hp] < bigN) hp++; 00492 hp--; 00493 00494 for (; hp >= 0; hp--) { 00495 h = incs[hp]; 00496 00497 i = lo + h; 00498 while (True) { 00499 00500 /*-- copy 1 --*/ 00501 if (i > hi) break; 00502 v = ptr[i]; 00503 j = i; 00504 while ( mainGtU ( 00505 ptr[j-h]+d, v+d, block, quadrant, nblock, budget 00506 ) ) { 00507 ptr[j] = ptr[j-h]; 00508 j = j - h; 00509 if (j <= (lo + h - 1)) break; 00510 } 00511 ptr[j] = v; 00512 i++; 00513 00514 /*-- copy 2 --*/ 00515 if (i > hi) break; 00516 v = ptr[i]; 00517 j = i; 00518 while ( mainGtU ( 00519 ptr[j-h]+d, v+d, block, quadrant, nblock, budget 00520 ) ) { 00521 ptr[j] = ptr[j-h]; 00522 j = j - h; 00523 if (j <= (lo + h - 1)) break; 00524 } 00525 ptr[j] = v; 00526 i++; 00527 00528 /*-- copy 3 --*/ 00529 if (i > hi) break; 00530 v = ptr[i]; 00531 j = i; 00532 while ( mainGtU ( 00533 ptr[j-h]+d, v+d, block, quadrant, nblock, budget 00534 ) ) { 00535 ptr[j] = ptr[j-h]; 00536 j = j - h; 00537 if (j <= (lo + h - 1)) break; 00538 } 00539 ptr[j] = v; 00540 i++; 00541 00542 if (*budget < 0) return; 00543 } 00544 } 00545 } |
|
Definition at line 741 of file blocksort.c. Referenced by blockSort().
00748 { 00749 Int32 i, j, k, m, ss, sb; 00750 Int32 runningOrder[256]; 00751 Int32 copy[256]; 00752 Bool bigDone[256]; 00753 UChar c1; 00754 Int32 numQSorted; 00755 Int32 biggestSoFar; 00756 UInt16 s; 00757 00758 if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" ); 00759 00760 /*-- Stripe the block data into 16 bits, and at the 00761 same time set up the 2-byte frequency table 00762 --*/ 00763 for (i = 65536; i >= 0; i--) ftab[i] = 0; 00764 00765 s = block[0]; 00766 for (i = 1; i < nblock; i++) { 00767 quadrant[i] = 0; 00768 s = (s << 8) | block[i]; 00769 block[i-1] = s; 00770 ftab[s]++; 00771 } 00772 quadrant[0] = 0; 00773 s = (s << 8) | (block[0] >> 8); 00774 block[nblock-1] = s; 00775 ftab[s]++; 00776 00777 /*-- (emphasises close relationship of block & quadrant) --*/ 00778 for (i = 0; i < BZ_N_OVERSHOOT; i++) { 00779 block [nblock+i] = block[i]; 00780 quadrant[nblock+i] = 0; 00781 } 00782 00783 if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" ); 00784 00785 /*-- Complete the initial radix sort --*/ 00786 for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1]; 00787 00788 for (i = 0; i < nblock; i++) { 00789 s = block[i]; 00790 j = ftab[s] - 1; 00791 ftab[s] = j; 00792 ptr[j] = i; 00793 } 00794 00795 /*-- 00796 Now ftab contains the first loc of every small bucket. 00797 Calculate the running order, from smallest to largest 00798 big bucket. 00799 --*/ 00800 for (i = 0; i <= 255; i++) { 00801 bigDone [i] = False; 00802 runningOrder[i] = i; 00803 } 00804 00805 { 00806 Int32 vv; 00807 Int32 h = 1; 00808 do h = 3 * h + 1; while (h <= 256); 00809 do 00810 { 00811 // printf("h=%lu\n",h); 00812 h = h / 3; 00813 for (i = h; i <= 255; i++) 00814 { 00815 // printf("i=%lu\n",i); 00816 vv = runningOrder[i]; 00817 j = i; 00818 while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) { 00819 // printf("j=%lu\n",j); 00820 j-=h; 00821 runningOrder[j+h] = runningOrder[j]; 00822 // printf("j-h=%lu\n",j-h); 00823 // j = j - h; 00824 00825 // printf("j=%lu\n",j); 00826 if (j <= (h - 1)) goto zero; 00827 } 00828 zero: 00829 runningOrder[j] = vv; 00830 } 00831 } while (h != 1); 00832 } 00833 00834 /*-- 00835 The main sorting loop. 00836 --*/ 00837 00838 biggestSoFar = numQSorted = 0; 00839 00840 for (i = 0; i <= 255; i++) { 00841 00842 /*-- 00843 Process big buckets, starting with the least full. 00844 Basically this is a 4-step process in which we call 00845 mainQSort3 to sort the small buckets [ss, j], but 00846 also make a big effort to avoid the calls if we can. 00847 --*/ 00848 ss = runningOrder[i]; 00849 00850 /*-- 00851 Step 1: 00852 Complete the big bucket [ss] by quicksorting 00853 any unsorted small buckets [ss, j], for j != ss. 00854 Hopefully previous pointer-scanning phases have already 00855 completed many of the small buckets [ss, j], so 00856 we don't have to sort them at all. 00857 --*/ 00858 for (j = 0; j <= 255; j++) { 00859 if (j != ss) { 00860 sb = (ss << 8) + j; 00861 if ( ! (ftab[sb] & SETMASK) ) { 00862 Int32 lo = ftab[sb] & CLEARMASK; 00863 Int32 hi = (ftab[sb+1] & CLEARMASK) - 1; 00864 if (hi > lo) { 00865 if (verb >= 4) 00866 VPrintf4 ( " qsort [0x%x, 0x%x] " 00867 "done %d this %d\n", 00868 ss, j, numQSorted, hi - lo + 1 ); 00869 mainQSort3 ( 00870 ptr, block, quadrant, nblock, 00871 lo, hi, BZ_N_RADIX, budget 00872 ); 00873 numQSorted += (hi - lo + 1); 00874 if (*budget < 0) return; 00875 } 00876 } 00877 ftab[sb] |= SETMASK; 00878 } 00879 } 00880 00881 /*-- 00882 Step 2: 00883 Deal specially with case [ss, ss]. This establishes the 00884 sorted order for [ss, ss] without any comparisons. 00885 A clever trick, cryptically described as steps Q6b and Q6c 00886 in SRC-124 (aka BW94). Compared to bzip2, this makes it 00887 practical not to use a preliminary run-length coder. 00888 --*/ 00889 { 00890 Int32 put0, get0, put1, get1; 00891 Int32 sbn = (ss << 8) + ss; 00892 Int32 lo = ftab[sbn] & CLEARMASK; 00893 Int32 hi = (ftab[sbn+1] & CLEARMASK) - 1; 00894 UChar ssc = (UChar)ss; 00895 put0 = lo; 00896 get0 = ftab[ss << 8] & CLEARMASK; 00897 put1 = hi; 00898 get1 = (ftab[(ss+1) << 8] & CLEARMASK) - 1; 00899 while (get0 < put0) { 00900 j = ptr[get0]-1; if (j < 0) j += nblock; 00901 c1 = (UChar)(block[j] >> 8); 00902 if (c1 == ssc) { ptr[put0] = j; put0++; }; 00903 get0++; 00904 } 00905 while (get1 > put1) { 00906 j = ptr[get1]-1; if (j < 0) j += nblock; 00907 c1 = (UChar)(block[j] >> 8); 00908 if (c1 == ssc) { ptr[put1] = j; put1--; }; 00909 get1--; 00910 } 00911 ftab[sbn] |= SETMASK; 00912 } 00913 00914 /*-- 00915 Step 3: 00916 The [ss] big bucket is now done. Record this fact, 00917 and update the quadrant descriptors. Remember to 00918 update quadrants in the overshoot area too, if 00919 necessary. The "if (i < 255)" test merely skips 00920 this updating for the last bucket processed, since 00921 updating for the last bucket is pointless. 00922 00923 The quadrant array provides a way to incrementally 00924 cache sort orderings, as they appear, so as to 00925 make subsequent comparisons in fullGtU() complete 00926 faster. For repetitive blocks this makes a big 00927 difference (but not big enough to be able to avoid 00928 the fallback sorting mechanism, exponential radix sort). 00929 00930 The precise meaning is: at all times: 00931 00932 for 0 <= i < nblock and 0 <= j <= nblock 00933 00934 if block[i] != block[j], 00935 00936 then the relative values of quadrant[i] and 00937 quadrant[j] are meaningless. 00938 00939 else { 00940 if quadrant[i] < quadrant[j] 00941 then the string starting at i lexicographically 00942 precedes the string starting at j 00943 00944 else if quadrant[i] > quadrant[j] 00945 then the string starting at j lexicographically 00946 precedes the string starting at i 00947 00948 else 00949 the relative ordering of the strings starting 00950 at i and j has not yet been determined. 00951 } 00952 --*/ 00953 bigDone[ss] = True; 00954 00955 if (i < 255) { 00956 Int32 bbStart = ftab[ss << 8] & CLEARMASK; 00957 Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart; 00958 Int32 shifts = 0; 00959 00960 while ((bbSize >> shifts) > 65534) shifts++; 00961 00962 for (j = 0; j < bbSize; j++) { 00963 Int32 a2update = ptr[bbStart + j]; 00964 UInt16 qVal = (UInt16)(j >> shifts); 00965 quadrant[a2update] = qVal; 00966 if (a2update < BZ_N_OVERSHOOT) 00967 quadrant[a2update + nblock] = qVal; 00968 } 00969 AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 ); 00970 } 00971 00972 /*-- 00973 Step 4: 00974 Now scan this big bucket [ss] so as to synthesise the 00975 sorted order for small buckets [t, ss] for all t != ss. 00976 This will avoid doing Real Work in subsequent Step 1's. 00977 --*/ 00978 for (j = 0; j <= 255; j++) 00979 copy[j] = ftab[(j << 8) + ss] & CLEARMASK; 00980 00981 m = ftab[(ss+1) << 8] & CLEARMASK; 00982 for (j = ftab[ss << 8] & CLEARMASK; j < m; j++) { 00983 k = ptr[j] - 1; if (k < 0) k += nblock; 00984 c1 = (UChar)(block[k] >> 8); 00985 if ( ! bigDone[c1] ) { 00986 ptr[copy[c1]] = k; 00987 copy[c1] ++; 00988 } 00989 } 00990 00991 for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK; 00992 } 00993 00994 if (verb >= 4) 00995 VPrintf3 ( " %d pointers, %d sorted, %d scanned\n", 00996 nblock, numQSorted, nblock - numQSorted ); 00997 } |
|
Definition at line 574 of file blocksort.c. Referenced by mainQSort3().
|
|
Initial value: { 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484 } Definition at line 470 of file blocksort.c. |