blocksort.c File Reference

{ sp--;              \
                      lz = stackLo[sp];  \
                      hz = stackHi[sp]; }

{ stackLo[sp] = lz; \
                       stackHi[sp] = hz; \
                       sp++; }

{                                     \
   Int32 yyp1 = (zzp1);               \
   Int32 yyp2 = (zzp2);               \
   Int32 yyn  = (zzn);                \
   while (yyn > 0) {                  \
      fswap(fmap[yyp1], fmap[yyp2]);  \
      yyp1++; yyp2++; yyn--;          \
   }                                  \
}

{ 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; }

{ sp--;             \
                         lz = stackLo[sp]; \
                         hz = stackHi[sp]; \
                         dz = stackD [sp]; }

{ stackLo[sp] = lz; \
                          stackHi[sp] = hz; \
                          stackD [sp] = dz; \
                          sp++; }

{                                     \
   Int32 yyp1 = (zzp1);               \
   Int32 yyp2 = (zzp2);               \
   Int32 yyn  = (zzn);                \
   while (yyn > 0) {                  \
      mswap(ptr[yyp1], ptr[yyp2]);    \
      yyp1++; yyp2++; yyn--;          \
   }                                  \
}

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

 { 1, 4, 13, 40, 121, 364, 1093, 3280,
                   9841, 29524, 88573, 265720,
                   797161, 2391484 }

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]

blocksort.c File Reference

Defines

Functions

Variables

Define Documentation

Function Documentation

Variable Documentation