dist/bzip2/blocksort.c

   1
   2 /*-------------------------------------------------------------*/
   3 /*--- Block sorting machinery                               ---*/
   4 /*---                                           blocksort.c ---*/
   5 /*-------------------------------------------------------------*/
   6
   7 /* ------------------------------------------------------------------
   8    This file is part of bzip2/libbzip2, a program and library for
   9    lossless, block-sorting data compression.
  10
  11    bzip2/libbzip2 version 1.0.5 of 10 December 2007
  12    Copyright (C) 1996-2007 Julian Seward <jseward@bzip.org>
  13
  14    Please read the WARNING, DISCLAIMER and PATENTS sections in the
  15    README file.
  16
  17    This program is released under the terms of the license contained
  18    in the file LICENSE.
  19    ------------------------------------------------------------------ */
  20
  21
  22 #include "bzlib_private.h"
  23
  24 /*---------------------------------------------*/
  25 /*--- Fallback O(N log(N)^2) sorting        ---*/
  26 /*--- algorithm, for repetitive blocks      ---*/
  27 /*---------------------------------------------*/
  28
  29 /*---------------------------------------------*/
  30 static
  31 __inline__
  32 void fallbackSimpleSort ( UInt32* fmap,
  33                           UInt32* eclass,
  34                           Int32   lo,
  35                           Int32   hi )
  36 {
  37    Int32 i, j, tmp;
  38    UInt32 ec_tmp;
  39
  40    if (lo == hi) return;
  41
  42    if (hi - lo > 3) {
  43       for ( i = hi-4; i >= lo; i-- ) {
  44          tmp = fmap[i];
  45          ec_tmp = eclass[tmp];
  46          for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
  47             fmap[j-4] = fmap[j];
  48          fmap[j-4] = tmp;
  49       }
  50    }
  51
  52    for ( i = hi-1; i >= lo; i-- ) {
  53       tmp = fmap[i];
  54       ec_tmp = eclass[tmp];
  55       for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
  56          fmap[j-1] = fmap[j];
  57       fmap[j-1] = tmp;
  58    }
  59 }
  60
  61
  62 /*---------------------------------------------*/
  63 #define fswap(zz1, zz2) \
  64    { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
  65
  66 #define fvswap(zzp1, zzp2, zzn)       \
  67 {                                     \
  68    Int32 yyp1 = (zzp1);               \
  69    Int32 yyp2 = (zzp2);               \
  70    Int32 yyn  = (zzn);                \
  71    while (yyn > 0) {                  \
  72       fswap(fmap[yyp1], fmap[yyp2]);  \
  73       yyp1++; yyp2++; yyn--;          \
  74    }                                  \
  75 }
  76
  77
  78 #define fmin(a,b) ((a) < (b)) ? (a) : (b)
  79
  80 #define fpush(lz,hz) { stackLo[sp] = lz; \
  81                        stackHi[sp] = hz; \
  82                        sp++; }
  83
  84 #define fpop(lz,hz) { sp--;              \
  85                       lz = stackLo[sp];  \
  86                       hz = stackHi[sp]; }
  87
  88 #define FALLBACK_QSORT_SMALL_THRESH 10
  89 #define FALLBACK_QSORT_STACK_SIZE   100
  90
  91
  92 static
  93 void fallbackQSort3 ( UInt32* fmap,
  94                       UInt32* eclass,
  95                       Int32   loSt,
  96                       Int32   hiSt )
  97 {
  98    Int32 unLo, unHi, ltLo, gtHi, n, m;
  99    Int32 sp, lo, hi;
 100    UInt32 med, r, r3;
 101    Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];
 102    Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];
 103
 104    r = 0;
 105
 106    sp = 0;
 107    fpush ( loSt, hiSt );
 108
 109    while (sp > 0) {
 110
 111       AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 );
 112
 113       fpop ( lo, hi );
 114       if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
 115          fallbackSimpleSort ( fmap, eclass, lo, hi );
 116          continue;
 117       }
 118
 119       /* Random partitioning.  Median of 3 sometimes fails to
 120          avoid bad cases.  Median of 9 seems to help but
 121          looks rather expensive.  This too seems to work but
 122          is cheaper.  Guidance for the magic constants
 123          7621 and 32768 is taken from Sedgewick's algorithms
 124          book, chapter 35.
 125       */
 126       r = ((r * 7621) + 1) % 32768;
 127       r3 = r % 3;
 128       if (r3 == 0) med = eclass[fmap[lo]]; else
 129       if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
 130                    med = eclass[fmap[hi]];
 131
 132       unLo = ltLo = lo;
 133       unHi = gtHi = hi;
 134
 135       while (1) {
 136          while (1) {
 137             if (unLo > unHi) break;
 138             n = (Int32)eclass[fmap[unLo]] - (Int32)med;
 139             if (n == 0) {
 140                fswap(fmap[unLo], fmap[ltLo]);
 141                ltLo++; unLo++;
 142                continue;
 143             };
 144             if (n > 0) break;
 145             unLo++;
 146          }
 147          while (1) {
 148             if (unLo > unHi) break;
 149             n = (Int32)eclass[fmap[unHi]] - (Int32)med;
 150             if (n == 0) {
 151                fswap(fmap[unHi], fmap[gtHi]);
 152                gtHi--; unHi--;
 153                continue;
 154             };
 155             if (n < 0) break;
 156             unHi--;
 157          }
 158          if (unLo > unHi) break;
 159          fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
 160       }
 161
 162       AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );
 163
 164       if (gtHi < ltLo) continue;
 165
 166       n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
 167       m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
 168
 169       n = lo + unLo - ltLo - 1;
 170       m = hi - (gtHi - unHi) + 1;
 171
 172       if (n - lo > hi - m) {
 173          fpush ( lo, n );
 174          fpush ( m, hi );
 175       } else {
 176          fpush ( m, hi );
 177          fpush ( lo, n );
 178       }
 179    }
 180 }
 181
 182 #undef fmin
 183 #undef fpush
 184 #undef fpop
 185 #undef fswap
 186 #undef fvswap
 187 #undef FALLBACK_QSORT_SMALL_THRESH
 188 #undef FALLBACK_QSORT_STACK_SIZE
 189
 190
 191 /*---------------------------------------------*/
 192 /* Pre:
 193       nblock > 0
 194       eclass exists for [0 .. nblock-1]
 195       ((UChar*)eclass) [0 .. nblock-1] holds block
 196       ptr exists for [0 .. nblock-1]
 197
 198    Post:
 199       ((UChar*)eclass) [0 .. nblock-1] holds block
 200       All other areas of eclass destroyed
 201       fmap [0 .. nblock-1] holds sorted order
 202       bhtab [ 0 .. 2+(nblock/32) ] destroyed
 203 */
 204
 205 #define       SET_BH(zz)  bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
 206 #define     CLEAR_BH(zz)  bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
 207 #define     ISSET_BH(zz)  (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
 208 #define      WORD_BH(zz)  bhtab[(zz) >> 5]
 209 #define UNALIGNED_BH(zz)  ((zz) & 0x01f)
 210
 211 static
 212 void fallbackSort ( UInt32* fmap,
 213                     UInt32* eclass,
 214                     UInt32* bhtab,
 215                     Int32   nblock,
 216                     Int32   verb )
 217 {
 218    Int32 ftab[257];
 219    Int32 ftabCopy[256];
 220    Int32 H, i, j, k, l, r, cc, cc1;
 221    Int32 nNotDone;
 222    Int32 nBhtab;
 223    UChar* eclass8 = (UChar*)eclass;
 224
 225    /*--
 226       Initial 1-char radix sort to generate
 227       initial fmap and initial BH bits.
 228    --*/
 229    if (verb >= 4)
 230       VPrintf0 ( "        bucket sorting ...\n" );
 231    for (i = 0; i < 257;    i++) ftab[i] = 0;
 232    for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
 233    for (i = 0; i < 256;    i++) ftabCopy[i] = ftab[i];
 234    for (i = 1; i < 257;    i++) ftab[i] += ftab[i-1];
 235
 236    for (i = 0; i < nblock; i++) {
 237       j = eclass8[i];
 238       k = ftab[j] - 1;
 239       ftab[j] = k;
 240       fmap[k] = i;
 241    }
 242
 243    nBhtab = 2 + (nblock / 32);
 244    for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
 245    for (i = 0; i < 256; i++) SET_BH(ftab[i]);
 246
 247    /*--
 248       Inductively refine the buckets.  Kind-of an
 249       "exponential radix sort" (!), inspired by the
 250       Manber-Myers suffix array construction algorithm.
 251    --*/
 252
 253    /*-- set sentinel bits for block-end detection --*/
 254    for (i = 0; i < 32; i++) {
 255       SET_BH(nblock + 2*i);
 256       CLEAR_BH(nblock + 2*i + 1);
 257    }
 258
 259    /*-- the log(N) loop --*/
 260    H = 1;
 261    while (1) {
 262
 263       if (verb >= 4)
 264          VPrintf1 ( "        depth %6d has ", H );
 265
 266       j = 0;
 267       for (i = 0; i < nblock; i++) {
 268          if (ISSET_BH(i)) j = i;
 269          k = fmap[i] - H; if (k < 0) k += nblock;
 270          eclass[k] = j;
 271       }
 272
 273       nNotDone = 0;
 274       r = -1;
 275       while (1) {
 276
 277          /*-- find the next non-singleton bucket --*/
 278          k = r + 1;
 279          while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
 280          if (ISSET_BH(k)) {
 281             while (WORD_BH(k) == 0xffffffff) k += 32;
 282             while (ISSET_BH(k)) k++;
 283          }
 284          l = k - 1;
 285          if (l >= nblock) break;
 286          while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
 287          if (!ISSET_BH(k)) {
 288             while (WORD_BH(k) == 0x00000000) k += 32;
 289             while (!ISSET_BH(k)) k++;
 290          }
 291          r = k - 1;
 292          if (r >= nblock) break;
 293
 294          /*-- now [l, r] bracket current bucket --*/
 295          if (r > l) {
 296             nNotDone += (r - l + 1);
 297             fallbackQSort3 ( fmap, eclass, l, r );
 298
 299             /*-- scan bucket and generate header bits-- */
 300             cc = -1;
 301             for (i = l; i <= r; i++) {
 302                cc1 = eclass[fmap[i]];
 303                if (cc != cc1) { SET_BH(i); cc = cc1; };
 304             }
 305          }
 306       }
 307
 308       if (verb >= 4)
 309          VPrintf1 ( "%6d unresolved strings\n", nNotDone );
 310
 311       H *= 2;
 312       if (H > nblock || nNotDone == 0) break;
 313    }
 314
 315    /*--
 316       Reconstruct the original block in
 317       eclass8 [0 .. nblock-1], since the
 318       previous phase destroyed it.
 319    --*/
 320    if (verb >= 4)
 321       VPrintf0 ( "        reconstructing block ...\n" );
 322    j = 0;
 323    for (i = 0; i < nblock; i++) {
 324       while (ftabCopy[j] == 0) j++;
 325       ftabCopy[j]--;
 326       eclass8[fmap[i]] = (UChar)j;
 327    }
 328    AssertH ( j < 256, 1005 );
 329 }
 330
 331 #undef       SET_BH
 332 #undef     CLEAR_BH
 333 #undef     ISSET_BH
 334 #undef      WORD_BH
 335 #undef UNALIGNED_BH
 336
 337
 338 /*---------------------------------------------*/
 339 /*--- The main, O(N^2 log(N)) sorting       ---*/
 340 /*--- algorithm.  Faster for "normal"       ---*/
 341 /*--- non-repetitive blocks.                ---*/
 342 /*---------------------------------------------*/
 343
 344 /*---------------------------------------------*/
 345 static
 346 __inline__
 347 Bool mainGtU ( UInt32  i1,
 348                UInt32  i2,
 349                UChar*  block,
 350                UInt16* quadrant,
 351                UInt32  nblock,
 352                Int32*  budget )
 353 {
 354    Int32  k;
 355    UChar  c1, c2;
 356    UInt16 s1, s2;
 357
 358    AssertD ( i1 != i2, "mainGtU" );
 359    /* 1 */
 360    c1 = block[i1]; c2 = block[i2];
 361    if (c1 != c2) return (c1 > c2);
 362    i1++; i2++;
 363    /* 2 */
 364    c1 = block[i1]; c2 = block[i2];
 365    if (c1 != c2) return (c1 > c2);
 366    i1++; i2++;
 367    /* 3 */
 368    c1 = block[i1]; c2 = block[i2];
 369    if (c1 != c2) return (c1 > c2);
 370    i1++; i2++;
 371    /* 4 */
 372    c1 = block[i1]; c2 = block[i2];
 373    if (c1 != c2) return (c1 > c2);
 374    i1++; i2++;
 375    /* 5 */
 376    c1 = block[i1]; c2 = block[i2];
 377    if (c1 != c2) return (c1 > c2);
 378    i1++; i2++;
 379    /* 6 */
 380    c1 = block[i1]; c2 = block[i2];
 381    if (c1 != c2) return (c1 > c2);
 382    i1++; i2++;
 383    /* 7 */
 384    c1 = block[i1]; c2 = block[i2];
 385    if (c1 != c2) return (c1 > c2);
 386    i1++; i2++;
 387    /* 8 */
 388    c1 = block[i1]; c2 = block[i2];
 389    if (c1 != c2) return (c1 > c2);
 390    i1++; i2++;
 391    /* 9 */
 392    c1 = block[i1]; c2 = block[i2];
 393    if (c1 != c2) return (c1 > c2);
 394    i1++; i2++;
 395    /* 10 */
 396    c1 = block[i1]; c2 = block[i2];
 397    if (c1 != c2) return (c1 > c2);
 398    i1++; i2++;
 399    /* 11 */
 400    c1 = block[i1]; c2 = block[i2];
 401    if (c1 != c2) return (c1 > c2);
 402    i1++; i2++;
 403    /* 12 */
 404    c1 = block[i1]; c2 = block[i2];
 405    if (c1 != c2) return (c1 > c2);
 406    i1++; i2++;
 407
 408    k = nblock + 8;
 409
 410    do {
 411       /* 1 */
 412       c1 = block[i1]; c2 = block[i2];
 413       if (c1 != c2) return (c1 > c2);
 414       s1 = quadrant[i1]; s2 = quadrant[i2];
 415       if (s1 != s2) return (s1 > s2);
 416       i1++; i2++;
 417       /* 2 */
 418       c1 = block[i1]; c2 = block[i2];
 419       if (c1 != c2) return (c1 > c2);
 420       s1 = quadrant[i1]; s2 = quadrant[i2];
 421       if (s1 != s2) return (s1 > s2);
 422       i1++; i2++;
 423       /* 3 */
 424       c1 = block[i1]; c2 = block[i2];
 425       if (c1 != c2) return (c1 > c2);
 426       s1 = quadrant[i1]; s2 = quadrant[i2];
 427       if (s1 != s2) return (s1 > s2);
 428       i1++; i2++;
 429       /* 4 */
 430       c1 = block[i1]; c2 = block[i2];
 431       if (c1 != c2) return (c1 > c2);
 432       s1 = quadrant[i1]; s2 = quadrant[i2];
 433       if (s1 != s2) return (s1 > s2);
 434       i1++; i2++;
 435       /* 5 */
 436       c1 = block[i1]; c2 = block[i2];
 437       if (c1 != c2) return (c1 > c2);
 438       s1 = quadrant[i1]; s2 = quadrant[i2];
 439       if (s1 != s2) return (s1 > s2);
 440       i1++; i2++;
 441       /* 6 */
 442       c1 = block[i1]; c2 = block[i2];
 443       if (c1 != c2) return (c1 > c2);
 444       s1 = quadrant[i1]; s2 = quadrant[i2];
 445       if (s1 != s2) return (s1 > s2);
 446       i1++; i2++;
 447       /* 7 */
 448       c1 = block[i1]; c2 = block[i2];
 449       if (c1 != c2) return (c1 > c2);
 450       s1 = quadrant[i1]; s2 = quadrant[i2];
 451       if (s1 != s2) return (s1 > s2);
 452       i1++; i2++;
 453       /* 8 */
 454       c1 = block[i1]; c2 = block[i2];
 455       if (c1 != c2) return (c1 > c2);
 456       s1 = quadrant[i1]; s2 = quadrant[i2];
 457       if (s1 != s2) return (s1 > s2);
 458       i1++; i2++;
 459
 460       if (i1 >= nblock) i1 -= nblock;
 461       if (i2 >= nblock) i2 -= nblock;
 462
 463       k -= 8;
 464       (*budget)--;
 465    }
 466       while (k >= 0);
 467
 468    return False;
 469 }
 470
 471
 472 /*---------------------------------------------*/
 473 /*--
 474    Knuth's increments seem to work better
 475    than Incerpi-Sedgewick here.  Possibly
 476    because the number of elems to sort is
 477    usually small, typically <= 20.
 478 --*/
 479 static
 480 Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
 481                    9841, 29524, 88573, 265720,
 482                    797161, 2391484 };
 483
 484 static
 485 void mainSimpleSort ( UInt32* ptr,
 486                       UChar*  block,
 487                       UInt16* quadrant,
 488                       Int32   nblock,
 489                       Int32   lo,
 490                       Int32   hi,
 491                       Int32   d,
 492                       Int32*  budget )
 493 {
 494    Int32 i, j, h, bigN, hp;
 495    UInt32 v;
 496
 497    bigN = hi - lo + 1;
 498    if (bigN < 2) return;
 499
 500    hp = 0;
 501    while (incs[hp] < bigN) hp++;
 502    hp--;
 503
 504    for (; hp >= 0; hp--) {
 505       h = incs[hp];
 506
 507       i = lo + h;
 508       while (True) {
 509
 510          /*-- copy 1 --*/
 511          if (i > hi) break;
 512          v = ptr[i];
 513          j = i;
 514          while ( mainGtU (
 515                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget
 516                  ) ) {
 517             ptr[j] = ptr[j-h];
 518             j = j - h;
 519             if (j <= (lo + h - 1)) break;
 520          }
 521          ptr[j] = v;
 522          i++;
 523
 524          /*-- copy 2 --*/
 525          if (i > hi) break;
 526          v = ptr[i];
 527          j = i;
 528          while ( mainGtU (
 529                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget
 530                  ) ) {
 531             ptr[j] = ptr[j-h];
 532             j = j - h;
 533             if (j <= (lo + h - 1)) break;
 534          }
 535          ptr[j] = v;
 536          i++;
 537
 538          /*-- copy 3 --*/
 539          if (i > hi) break;
 540          v = ptr[i];
 541          j = i;
 542          while ( mainGtU (
 543                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget
 544                  ) ) {
 545             ptr[j] = ptr[j-h];
 546             j = j - h;
 547             if (j <= (lo + h - 1)) break;
 548          }
 549          ptr[j] = v;
 550          i++;
 551
 552          if (*budget < 0) return;
 553       }
 554    }
 555 }
 556
 557
 558 /*---------------------------------------------*/
 559 /*--
 560    The following is an implementation of
 561    an elegant 3-way quicksort for strings,
 562    described in a paper "Fast Algorithms for
 563    Sorting and Searching Strings", by Robert
 564    Sedgewick and Jon L. Bentley.
 565 --*/
 566
 567 #define mswap(zz1, zz2) \
 568    { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
 569
 570 #define mvswap(zzp1, zzp2, zzn)       \
 571 {                                     \
 572    Int32 yyp1 = (zzp1);               \
 573    Int32 yyp2 = (zzp2);               \
 574    Int32 yyn  = (zzn);                \
 575    while (yyn > 0) {                  \
 576       mswap(ptr[yyp1], ptr[yyp2]);    \
 577       yyp1++; yyp2++; yyn--;          \
 578    }                                  \
 579 }
 580
 581 static
 582 __inline__
 583 UChar mmed3 ( UChar a, UChar b, UChar c )
 584 {
 585    UChar t;
 586    if (a > b) { t = a; a = b; b = t; };
 587    if (b > c) {
 588       b = c;
 589       if (a > b) b = a;
 590    }
 591    return b;
 592 }
 593
 594 #define mmin(a,b) ((a) < (b)) ? (a) : (b)
 595
 596 #define mpush(lz,hz,dz) { stackLo[sp] = lz; \
 597                           stackHi[sp] = hz; \
 598                           stackD [sp] = dz; \
 599                           sp++; }
 600
 601 #define mpop(lz,hz,dz) { sp--;             \
 602                          lz = stackLo[sp]; \
 603                          hz = stackHi[sp]; \
 604                          dz = stackD [sp]; }
 605
 606
 607 #define mnextsize(az) (nextHi[az]-nextLo[az])
 608
 609 #define mnextswap(az,bz)                                        \
 610    { Int32 tz;                                                  \
 611      tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
 612      tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
 613      tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
 614
 615
 616 #define MAIN_QSORT_SMALL_THRESH 20
 617 #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
 618 #define MAIN_QSORT_STACK_SIZE 100
 619
 620 static
 621 void mainQSort3 ( UInt32* ptr,
 622                   UChar*  block,
 623                   UInt16* quadrant,
 624                   Int32   nblock,
 625                   Int32   loSt,
 626                   Int32   hiSt,
 627                   Int32   dSt,
 628                   Int32*  budget )
 629 {
 630    Int32 unLo, unHi, ltLo, gtHi, n, m, med;
 631    Int32 sp, lo, hi, d;
 632
 633    Int32 stackLo[MAIN_QSORT_STACK_SIZE];
 634    Int32 stackHi[MAIN_QSORT_STACK_SIZE];
 635    Int32 stackD [MAIN_QSORT_STACK_SIZE];
 636
 637    Int32 nextLo[3];
 638    Int32 nextHi[3];
 639    Int32 nextD [3];
 640
 641    sp = 0;
 642    mpush ( loSt, hiSt, dSt );
 643
 644    while (sp > 0) {
 645
 646       AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 );
 647
 648       mpop ( lo, hi, d );
 649       if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
 650           d > MAIN_QSORT_DEPTH_THRESH) {
 651          mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
 652          if (*budget < 0) return;
 653          continue;
 654       }
 655
 656       med = (Int32)
 657             mmed3 ( block[ptr[ lo         ]+d],
 658                     block[ptr[ hi         ]+d],
 659                     block[ptr[ (lo+hi)>>1 ]+d] );
 660
 661       unLo = ltLo = lo;
 662       unHi = gtHi = hi;
 663
 664       while (True) {
 665          while (True) {
 666             if (unLo > unHi) break;
 667             n = ((Int32)block[ptr[unLo]+d]) - med;
 668             if (n == 0) {
 669                mswap(ptr[unLo], ptr[ltLo]);
 670                ltLo++; unLo++; continue;
 671             };
 672             if (n >  0) break;
 673             unLo++;
 674          }
 675          while (True) {
 676             if (unLo > unHi) break;
 677             n = ((Int32)block[ptr[unHi]+d]) - med;
 678             if (n == 0) {
 679                mswap(ptr[unHi], ptr[gtHi]);
 680                gtHi--; unHi--; continue;
 681             };
 682             if (n <  0) break;
 683             unHi--;
 684          }
 685          if (unLo > unHi) break;
 686          mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
 687       }
 688
 689       AssertD ( unHi == unLo-1, "mainQSort3(2)" );
 690
 691       if (gtHi < ltLo) {
 692          mpush(lo, hi, d+1 );
 693          continue;
 694       }
 695
 696       n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
 697       m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
 698
 699       n = lo + unLo - ltLo - 1;
 700       m = hi - (gtHi - unHi) + 1;
 701
 702       nextLo[0] = lo;  nextHi[0] = n;   nextD[0] = d;
 703       nextLo[1] = m;   nextHi[1] = hi;  nextD[1] = d;
 704       nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
 705
 706       if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
 707       if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
 708       if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
 709
 710       AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );
 711       AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );
 712
 713       mpush (nextLo[0], nextHi[0], nextD[0]);
 714       mpush (nextLo[1], nextHi[1], nextD[1]);
 715       mpush (nextLo[2], nextHi[2], nextD[2]);
 716    }
 717 }
 718
 719 #undef mswap
 720 #undef mvswap
 721 #undef mpush
 722 #undef mpop
 723 #undef mmin
 724 #undef mnextsize
 725 #undef mnextswap
 726 #undef MAIN_QSORT_SMALL_THRESH
 727 #undef MAIN_QSORT_DEPTH_THRESH
 728 #undef MAIN_QSORT_STACK_SIZE
 729
 730
 731 /*---------------------------------------------*/
 732 /* Pre:
 733       nblock > N_OVERSHOOT
 734       block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
 735       ((UChar*)block32) [0 .. nblock-1] holds block
 736       ptr exists for [0 .. nblock-1]
 737
 738    Post:
 739       ((UChar*)block32) [0 .. nblock-1] holds block
 740       All other areas of block32 destroyed
 741       ftab [0 .. 65536 ] destroyed
 742       ptr [0 .. nblock-1] holds sorted order
 743       if (*budget < 0), sorting was abandoned
 744 */
 745
 746 #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
 747 #define SETMASK (1 << 21)
 748 #define CLEARMASK (~(SETMASK))
 749
 750 static
 751 void mainSort ( UInt32* ptr,
 752                 UChar*  block,
 753                 UInt16* quadrant,
 754                 UInt32* ftab,
 755                 Int32   nblock,
 756                 Int32   verb,
 757                 Int32*  budget )
 758 {
 759    Int32  i, j, k, ss, sb;
 760    Int32  runningOrder[256];
 761    Bool   bigDone[256];
 762    Int32  copyStart[256];
 763    Int32  copyEnd  [256];
 764    UChar  c1;
 765    Int32  numQSorted;
 766    UInt16 s;
 767    if (verb >= 4) VPrintf0 ( "        main sort initialise ...\n" );
 768
 769    /*-- set up the 2-byte frequency table --*/
 770    for (i = 65536; i >= 0; i--) ftab[i] = 0;
 771
 772    j = block[0] << 8;
 773    i = nblock-1;
 774    for (; i >= 3; i -= 4) {
 775       quadrant[i] = 0;
 776       j = (j >> 8) | ( ((UInt16)block[i]) << 8);
 777       ftab[j]++;
 778       quadrant[i-1] = 0;
 779       j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);
 780       ftab[j]++;
 781       quadrant[i-2] = 0;
 782       j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);
 783       ftab[j]++;
 784       quadrant[i-3] = 0;
 785       j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);
 786       ftab[j]++;
 787    }
 788    for (; i >= 0; i--) {
 789       quadrant[i] = 0;
 790       j = (j >> 8) | ( ((UInt16)block[i]) << 8);
 791       ftab[j]++;
 792    }
 793
 794    /*-- (emphasises close relationship of block & quadrant) --*/
 795    for (i = 0; i < BZ_N_OVERSHOOT; i++) {
 796       block   [nblock+i] = block[i];
 797       quadrant[nblock+i] = 0;
 798    }
 799
 800    if (verb >= 4) VPrintf0 ( "        bucket sorting ...\n" );
 801
 802    /*-- Complete the initial radix sort --*/
 803    for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
 804
 805    s = block[0] << 8;
 806    i = nblock-1;
 807    for (; i >= 3; i -= 4) {
 808       s = (s >> 8) | (block[i] << 8);
 809       j = ftab[s] -1;
 810       ftab[s] = j;
 811       ptr[j] = i;
 812       s = (s >> 8) | (block[i-1] << 8);
 813       j = ftab[s] -1;
 814       ftab[s] = j;
 815       ptr[j] = i-1;
 816       s = (s >> 8) | (block[i-2] << 8);
 817       j = ftab[s] -1;
 818       ftab[s] = j;
 819       ptr[j] = i-2;
 820       s = (s >> 8) | (block[i-3] << 8);
 821       j = ftab[s] -1;
 822       ftab[s] = j;
 823       ptr[j] = i-3;
 824    }
 825    for (; i >= 0; i--) {
 826       s = (s >> 8) | (block[i] << 8);
 827       j = ftab[s] -1;
 828       ftab[s] = j;
 829       ptr[j] = i;
 830    }
 831
 832    /*--
 833       Now ftab contains the first loc of every small bucket.
 834       Calculate the running order, from smallest to largest
 835       big bucket.
 836    --*/
 837    for (i = 0; i <= 255; i++) {
 838       bigDone     [i] = False;
 839       runningOrder[i] = i;
 840    }
 841
 842    {
 843       Int32 vv;
 844       Int32 h = 1;
 845       do h = 3 * h + 1; while (h <= 256);
 846       do {
 847          h = h / 3;
 848          for (i = h; i <= 255; i++) {
 849             vv = runningOrder[i];
 850             j = i;
 851             while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
 852                runningOrder[j] = runningOrder[j-h];
 853                j = j - h;
 854                if (j <= (h - 1)) goto zero;
 855             }
 856             zero:
 857             runningOrder[j] = vv;
 858          }
 859       } while (h != 1);
 860    }
 861
 862    /*--
 863       The main sorting loop.
 864    --*/
 865
 866    numQSorted = 0;
 867
 868    for (i = 0; i <= 255; i++) {
 869
 870       /*--
 871          Process big buckets, starting with the least full.
 872          Basically this is a 3-step process in which we call
 873          mainQSort3 to sort the small buckets [ss, j], but
 874          also make a big effort to avoid the calls if we can.
 875       --*/
 876       ss = runningOrder[i];
 877
 878       /*--
 879          Step 1:
 880          Complete the big bucket [ss] by quicksorting
 881          any unsorted small buckets [ss, j], for j != ss.
 882          Hopefully previous pointer-scanning phases have already
 883          completed many of the small buckets [ss, j], so
 884          we don't have to sort them at all.
 885       --*/
 886       for (j = 0; j <= 255; j++) {
 887          if (j != ss) {
 888             sb = (ss << 8) + j;
 889             if ( ! (ftab[sb] & SETMASK) ) {
 890                Int32 lo = ftab[sb]   & CLEARMASK;
 891                Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
 892                if (hi > lo) {
 893                   if (verb >= 4)
 894                      VPrintf4 ( "        qsort [0x%x, 0x%x]   "
 895                                 "done %d   this %d\n",
 896                                 ss, j, numQSorted, hi - lo + 1 );
 897                   mainQSort3 (
 898                      ptr, block, quadrant, nblock,
 899                      lo, hi, BZ_N_RADIX, budget
 900                   );
 901                   numQSorted += (hi - lo + 1);
 902                   if (*budget < 0) return;
 903                }
 904             }
 905             ftab[sb] |= SETMASK;
 906          }
 907       }
 908
 909       AssertH ( !bigDone[ss], 1006 );
 910
 911       /*--
 912          Step 2:
 913          Now scan this big bucket [ss] so as to synthesise the
 914          sorted order for small buckets [t, ss] for all t,
 915          including, magically, the bucket [ss,ss] too.
 916          This will avoid doing Real Work in subsequent Step 1's.
 917       --*/
 918       {
 919          for (j = 0; j <= 255; j++) {
 920             copyStart[j] =  ftab[(j << 8) + ss]     & CLEARMASK;
 921             copyEnd  [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
 922          }
 923          for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
 924             k = ptr[j]-1; if (k < 0) k += nblock;
 925             c1 = block[k];
 926             if (!bigDone[c1])
 927                ptr[ copyStart[c1]++ ] = k;
 928          }
 929          for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
 930             k = ptr[j]-1; if (k < 0) k += nblock;
 931             c1 = block[k];
 932             if (!bigDone[c1])
 933                ptr[ copyEnd[c1]-- ] = k;
 934          }
 935       }
 936
 937       AssertH ( (copyStart[ss]-1 == copyEnd[ss])
 938                 ||
 939                 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
 940                    Necessity for this case is demonstrated by compressing
 941                    a sequence of approximately 48.5 million of character
 942                    251; 1.0.0/1.0.1 will then die here. */
 943                 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
 944                 1007 )
 945
 946       for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;
 947
 948       /*--
 949          Step 3:
 950          The [ss] big bucket is now done.  Record this fact,
 951          and update the quadrant descriptors.  Remember to
 952          update quadrants in the overshoot area too, if
 953          necessary.  The "if (i < 255)" test merely skips
 954          this updating for the last bucket processed, since
 955          updating for the last bucket is pointless.
 956
 957          The quadrant array provides a way to incrementally
 958          cache sort orderings, as they appear, so as to
 959          make subsequent comparisons in fullGtU() complete
 960          faster.  For repetitive blocks this makes a big
 961          difference (but not big enough to be able to avoid
 962          the fallback sorting mechanism, exponential radix sort).
 963
 964          The precise meaning is: at all times:
 965
 966             for 0 <= i < nblock and 0 <= j <= nblock
 967
 968             if block[i] != block[j],
 969
 970                then the relative values of quadrant[i] and
 971                     quadrant[j] are meaningless.
 972
 973                else {
 974                   if quadrant[i] < quadrant[j]
 975                      then the string starting at i lexicographically
 976                      precedes the string starting at j
 977
 978                   else if quadrant[i] > quadrant[j]
 979                      then the string starting at j lexicographically
 980                      precedes the string starting at i
 981
 982                   else
 983                      the relative ordering of the strings starting
 984                      at i and j has not yet been determined.
 985                }
 986       --*/
 987       bigDone[ss] = True;
 988
 989       if (i < 255) {
 990          Int32 bbStart  = ftab[ss << 8] & CLEARMASK;
 991          Int32 bbSize   = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
 992          Int32 shifts   = 0;
 993
 994          while ((bbSize >> shifts) > 65534) shifts++;
 995
 996          for (j = bbSize-1; j >= 0; j--) {
 997             Int32 a2update     = ptr[bbStart + j];
 998             UInt16 qVal        = (UInt16)(j >> shifts);
 999             quadrant[a2update] = qVal;
1000             if (a2update < BZ_N_OVERSHOOT)
1001                quadrant[a2update + nblock] = qVal;
1002          }
1003          AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
1004       }
1005
1006    }
1007
1008    if (verb >= 4)
1009       VPrintf3 ( "        %d pointers, %d sorted, %d scanned\n",
1010                  nblock, numQSorted, nblock - numQSorted );
1011 }
1012
1013 #undef BIGFREQ
1014 #undef SETMASK
1015 #undef CLEARMASK
1016
1017
1018 /*---------------------------------------------*/
1019 /* Pre:
1020       nblock > 0
1021       arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
1022       ((UChar*)arr2)  [0 .. nblock-1] holds block
1023       arr1 exists for [0 .. nblock-1]
1024
1025    Post:
1026       ((UChar*)arr2) [0 .. nblock-1] holds block
1027       All other areas of block destroyed
1028       ftab [ 0 .. 65536 ] destroyed
1029       arr1 [0 .. nblock-1] holds sorted order
1030 */
1031 void BZ2_blockSort ( EState* s )
1032 {
1033    UInt32* ptr    = s->ptr;
1034    UChar*  block  = s->block;
1035    UInt32* ftab   = s->ftab;
1036    Int32   nblock = s->nblock;
1037    Int32   verb   = s->verbosity;
1038    Int32   wfact  = s->workFactor;
1039    UInt16* quadrant;
1040    Int32   budget;
1041    Int32   budgetInit;
1042    Int32   i;
1043
1044    if (nblock < 10000) {
1045       fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1046    } else {
1047       /* Calculate the location for quadrant, remembering to get
1048          the alignment right.  Assumes that &(block[0]) is at least
1049          2-byte aligned -- this should be ok since block is really
1050          the first section of arr2.
1051       */
1052       i = nblock+BZ_N_OVERSHOOT;
1053       if (i & 1) i++;
1054       quadrant = (UInt16*)(&(block[i]));
1055
1056       /* (wfact-1) / 3 puts the default-factor-30
1057          transition point at very roughly the same place as
1058          with v0.1 and v0.9.0.
1059          Not that it particularly matters any more, since the
1060          resulting compressed stream is now the same regardless
1061          of whether or not we use the main sort or fallback sort.
1062       */
1063       if (wfact < 1  ) wfact = 1;
1064       if (wfact > 100) wfact = 100;
1065       budgetInit = nblock * ((wfact-1) / 3);
1066       budget = budgetInit;
1067
1068       mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
1069       if (verb >= 3)
1070          VPrintf3 ( "      %d work, %d block, ratio %5.2f\n",
1071                     budgetInit - budget,
1072                     nblock,
1073                     (float)(budgetInit - budget) /
1074                     (float)(nblock==0 ? 1 : nblock) );
1075       if (budget < 0) {
1076          if (verb >= 2)
1077             VPrintf0 ( "    too repetitive; using fallback"
1078                        " sorting algorithm\n" );
1079          fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
1080       }
1081    }
1082
1083    s->origPtr = -1;
1084    for (i = 0; i < s->nblock; i++)
1085       if (ptr[i] == 0)
1086          { s->origPtr = i; break; };
1087
1088    AssertH( s->origPtr != -1, 1003 );
1089 }
1090
1091
1092 /*-------------------------------------------------------------*/
1093 /*--- end                                       blocksort.c ---*/
1094 /*-------------------------------------------------------------*/