00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 #include "bzlib_private.h"
00063
00064
00065
00066
00067
00068
00069
00070 static
00071 __inline__
00072 void fallbackSimpleSort ( UInt32* fmap,
00073 UInt32* eclass,
00074 Int32 lo,
00075 Int32 hi )
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 }
00100
00101
00102
00103 #define fswap(zz1, zz2) \
00104 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
00105
00106 #define fvswap(zzp1, zzp2, zzn) \
00107 { \
00108 Int32 yyp1 = (zzp1); \
00109 Int32 yyp2 = (zzp2); \
00110 Int32 yyn = (zzn); \
00111 while (yyn > 0) { \
00112 fswap(fmap[yyp1], fmap[yyp2]); \
00113 yyp1++; yyp2++; yyn--; \
00114 } \
00115 }
00116
00117
00118 #define fmin(a,b) ((a) < (b)) ? (a) : (b)
00119
00120 #define fpush(lz,hz) { stackLo[sp] = lz; \
00121 stackHi[sp] = hz; \
00122 sp++; }
00123
00124 #define fpop(lz,hz) { sp--; \
00125 lz = stackLo[sp]; \
00126 hz = stackHi[sp]; }
00127
00128 #define FALLBACK_QSORT_SMALL_THRESH 10
00129 #define FALLBACK_QSORT_STACK_SIZE 100
00130
00131
00132 static
00133 void fallbackQSort3 ( UInt32* fmap,
00134 UInt32* eclass,
00135 Int32 loSt,
00136 Int32 hiSt )
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
00160
00161
00162
00163
00164
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 }
00221
00222 #undef fmin
00223 #undef fpush
00224 #undef fpop
00225 #undef fswap
00226 #undef fvswap
00227 #undef FALLBACK_QSORT_SMALL_THRESH
00228 #undef FALLBACK_QSORT_STACK_SIZE
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245 #define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
00246 #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
00247 #define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
00248 #define WORD_BH(zz) bhtab[(zz) >> 5]
00249 #define UNALIGNED_BH(zz) ((zz) & 0x01f)
00250
00251 static
00252 void fallbackSort ( UInt32* fmap,
00253 UInt32* eclass,
00254 UInt32* bhtab,
00255 Int32 nblock,
00256 Int32 verb )
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
00267
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
00289
00290
00291
00292
00293
00294 for (i = 0; i < 32; i++) {
00295 SET_BH(nblock + 2*i);
00296 CLEAR_BH(nblock + 2*i + 1);
00297 }
00298
00299
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
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
00335 if (r > l) {
00336 nNotDone += (r - l + 1);
00337 fallbackQSort3 ( fmap, eclass, l, r );
00338
00339
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
00357
00358
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 }
00370
00371 #undef SET_BH
00372 #undef CLEAR_BH
00373 #undef ISSET_BH
00374 #undef WORD_BH
00375 #undef UNALIGNED_BH
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385 static
00386 __inline__
00387 Bool mainGtU ( UInt32 i1,
00388 UInt32 i2,
00389 UInt16* block,
00390 UInt16* quadrant,
00391 UInt32 nblock,
00392 Int32* budget )
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 }
00461
00462
00463
00464
00465
00466
00467
00468
00469
00470 Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
00471 9841, 29524, 88573, 265720,
00472 797161, 2391484 };
00473
00474 static
00475 void mainSimpleSort ( UInt32* ptr,
00476 UInt16* block,
00477 UInt16* quadrant,
00478 Int32 nblock,
00479 Int32 lo,
00480 Int32 hi,
00481 Int32 d,
00482 Int32* budget )
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
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
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
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 }
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557 #define mswap(zz1, zz2) \
00558 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
00559
00560 #define mvswap(zzp1, zzp2, zzn) \
00561 { \
00562 Int32 yyp1 = (zzp1); \
00563 Int32 yyp2 = (zzp2); \
00564 Int32 yyn = (zzn); \
00565 while (yyn > 0) { \
00566 mswap(ptr[yyp1], ptr[yyp2]); \
00567 yyp1++; yyp2++; yyn--; \
00568 } \
00569 }
00570
00571
00572 static
00573 __inline__
00574 UInt16 mmed3 ( UInt16 a, UInt16 b, UInt16 c )
00575 {
00576 UInt16 t;
00577 if (a > b) { t = a; a = b; b = t; };
00578 if (b > c) { t = b; b = c; c = t; };
00579 if (a > b) b = a;
00580 return b;
00581 }
00582
00583
00584 #define mmin(a,b) ((a) < (b)) ? (a) : (b)
00585
00586 #define mpush(lz,hz,dz) { stackLo[sp] = lz; \
00587 stackHi[sp] = hz; \
00588 stackD [sp] = dz; \
00589 sp++; }
00590
00591 #define mpop(lz,hz,dz) { sp--; \
00592 lz = stackLo[sp]; \
00593 hz = stackHi[sp]; \
00594 dz = stackD [sp]; }
00595
00596
00597 #define mnextsize(az) (nextHi[az]-nextLo[az])
00598
00599 #define mnextswap(az,bz) \
00600 { Int32 tz; \
00601 tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
00602 tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
00603 tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
00604
00605
00606 #define MAIN_QSORT_SMALL_THRESH 20
00607 #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
00608 #define MAIN_QSORT_STACK_SIZE 100
00609
00610 static
00611 void mainQSort3 ( UInt32* ptr,
00612 UInt16* block,
00613 UInt16* quadrant,
00614 Int32 nblock,
00615 Int32 loSt,
00616 Int32 hiSt,
00617 Int32 dSt,
00618 Int32* budget )
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 }
00708
00709 #undef mswap
00710 #undef mvswap
00711 #undef mpush
00712 #undef mpop
00713 #undef mmin
00714 #undef mnextsize
00715 #undef mnextswap
00716 #undef MAIN_QSORT_SMALL_THRESH
00717 #undef MAIN_QSORT_DEPTH_THRESH
00718 #undef MAIN_QSORT_STACK_SIZE
00719
00720
00721
00722
00723
00724
00725
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735
00736 #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
00737 #define SETMASK (1 << 21)
00738 #define CLEARMASK (~(SETMASK))
00739
00740 static
00741 void mainSort ( UInt32* ptr,
00742 UInt16* block,
00743 UInt16* quadrant,
00744 UInt32* ftab,
00745 Int32 nblock,
00746 Int32 verb,
00747 Int32* budget )
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
00761
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
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
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
00797
00798
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
00812 h = h / 3;
00813 for (i = h; i <= 255; i++)
00814 {
00815
00816 vv = runningOrder[i];
00817 j = i;
00818 while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
00819
00820 j-=h;
00821 runningOrder[j+h] = runningOrder[j];
00822
00823
00824
00825
00826 if (j <= (h - 1)) goto zero;
00827 }
00828 zero:
00829 runningOrder[j] = vv;
00830 }
00831 } while (h != 1);
00832 }
00833
00834
00835
00836
00837
00838 biggestSoFar = numQSorted = 0;
00839
00840 for (i = 0; i <= 255; i++) {
00841
00842
00843
00844
00845
00846
00847
00848 ss = runningOrder[i];
00849
00850
00851
00852
00853
00854
00855
00856
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
00883
00884
00885
00886
00887
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
00916
00917
00918
00919
00920
00921
00922
00923
00924
00925
00926
00927
00928
00929
00930
00931
00932
00933
00934
00935
00936
00937
00938
00939
00940
00941
00942
00943
00944
00945
00946
00947
00948
00949
00950
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
00974
00975
00976
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 }
00998
00999 #undef BIGFREQ
01000 #undef SETMASK
01001 #undef CLEARMASK
01002
01003
01004
01005
01006
01007
01008
01009
01010
01011
01012
01013
01014
01015
01016
01017 void blockSort ( EState* s )
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
01037
01038
01039
01040
01041
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 }
01070
01071
01072
01073
01074