gcc/testsuite/gcc.dg/params/blocksort-part.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.6 of 6 September 2010
  12    Copyright (C) 1996-2010 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 typedef char            Char;
  22 typedef unsigned char   Bool;
  23 typedef unsigned char   UChar;
  24 #if __SIZEOF_INT__ == 2
  25 typedef long             Int32;
  26 typedef unsigned long    UInt32;
  27 #else
  28 typedef int             Int32;
  29 typedef unsigned int    UInt32;
  30 #endif
  31 typedef short           Int16;
  32 typedef unsigned short  UInt16;
  33
  34 #define True  ((Bool)1)
  35 #define False ((Bool)0)
  36
  37 #define BZ_M_IDLE      1
  38 #define BZ_M_RUNNING   2
  39 #define BZ_M_FLUSHING  3
  40 #define BZ_M_FINISHING 4
  41
  42 #define BZ_S_OUTPUT    1
  43 #define BZ_S_INPUT     2
  44
  45 #define BZ_N_RADIX 2
  46 #define BZ_N_QSORT 12
  47 #define BZ_N_SHELL 18
  48 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
  49
  50 /*---------------------------------------------*/
  51 /*--- Fallback O(N log(N)^2) sorting        ---*/
  52 /*--- algorithm, for repetitive blocks      ---*/
  53 /*---------------------------------------------*/
  54
  55 /*---------------------------------------------*/
  56 void fallbackSimpleSort ( UInt32* fmap,
  57                           UInt32* eclass,
  58                           Int32   lo,
  59                           Int32   hi )
  60 {
  61    Int32 i, j, tmp;
  62    UInt32 ec_tmp;
  63
  64    if (lo == hi) return;
  65
  66    if (hi - lo > 3) {
  67       for ( i = hi-4; i >= lo; i-- ) {
  68          tmp = fmap[i];
  69          ec_tmp = eclass[tmp];
  70          for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
  71             fmap[j-4] = fmap[j];
  72          fmap[j-4] = tmp;
  73       }
  74    }
  75
  76    for ( i = hi-1; i >= lo; i-- ) {
  77       tmp = fmap[i];
  78       ec_tmp = eclass[tmp];
  79       for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
  80          fmap[j-1] = fmap[j];
  81       fmap[j-1] = tmp;
  82    }
  83 }
  84
  85
  86 /*---------------------------------------------*/
  87 #define fswap(zz1, zz2) \
  88    { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
  89
  90 #define fvswap(zzp1, zzp2, zzn)       \
  91 {                                     \
  92    Int32 yyp1 = (zzp1);               \
  93    Int32 yyp2 = (zzp2);               \
  94    Int32 yyn  = (zzn);                \
  95    while (yyn > 0) {                  \
  96       fswap(fmap[yyp1], fmap[yyp2]);  \
  97       yyp1++; yyp2++; yyn--;          \
  98    }                                  \
  99 }
 100
 101
 102 #define fmin(a,b) ((a) < (b)) ? (a) : (b)
 103
 104 #define fpush(lz,hz) { stackLo[sp] = lz; \
 105                        stackHi[sp] = hz; \
 106                        sp++; }
 107
 108 #define fpop(lz,hz) { sp--;              \
 109                       lz = stackLo[sp];  \
 110                       hz = stackHi[sp]; }
 111
 112 #define FALLBACK_QSORT_SMALL_THRESH 10
 113 #define FALLBACK_QSORT_STACK_SIZE   100
 114
 115
 116 void fallbackQSort3 ( UInt32* fmap,
 117                       UInt32* eclass,
 118                       Int32   loSt,
 119                       Int32   hiSt )
 120 {
 121    Int32 unLo, unHi, ltLo, gtHi, n, m;
 122    Int32 sp, lo, hi;
 123    UInt32 med, r, r3;
 124    Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];
 125    Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];
 126
 127    r = 0;
 128
 129    sp = 0;
 130    fpush ( loSt, hiSt );
 131
 132    while (sp > 0) {
 133
 134       fpop ( lo, hi );
 135       if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
 136          fallbackSimpleSort ( fmap, eclass, lo, hi );
 137          continue;
 138       }
 139
 140       /* Random partitioning.  Median of 3 sometimes fails to
 141          avoid bad cases.  Median of 9 seems to help but
 142          looks rather expensive.  This too seems to work but
 143          is cheaper.  Guidance for the magic constants
 144          7621 and 32768 is taken from Sedgewick's algorithms
 145          book, chapter 35.
 146       */
 147       r = ((r * 7621) + 1) % 32768;
 148       r3 = r % 3;
 149       if (r3 == 0) med = eclass[fmap[lo]]; else
 150       if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
 151                    med = eclass[fmap[hi]];
 152
 153       unLo = ltLo = lo;
 154       unHi = gtHi = hi;
 155
 156       while (1) {
 157          while (1) {
 158             if (unLo > unHi) break;
 159             n = (Int32)eclass[fmap[unLo]] - (Int32)med;
 160             if (n == 0) {
 161                fswap(fmap[unLo], fmap[ltLo]);
 162                ltLo++; unLo++;
 163                continue;
 164             };
 165             if (n > 0) break;
 166             unLo++;
 167          }
 168          while (1) {
 169             if (unLo > unHi) break;
 170             n = (Int32)eclass[fmap[unHi]] - (Int32)med;
 171             if (n == 0) {
 172                fswap(fmap[unHi], fmap[gtHi]);
 173                gtHi--; unHi--;
 174                continue;
 175             };
 176             if (n < 0) break;
 177             unHi--;
 178          }
 179          if (unLo > unHi) break;
 180          fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
 181       }
 182
 183       if (gtHi < ltLo) continue;
 184
 185       n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
 186       m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
 187
 188       n = lo + unLo - ltLo - 1;
 189       m = hi - (gtHi - unHi) + 1;
 190
 191       if (n - lo > hi - m) {
 192          fpush ( lo, n );
 193          fpush ( m, hi );
 194       } else {
 195          fpush ( m, hi );
 196          fpush ( lo, n );
 197       }
 198    }
 199 }
 200
 201 #undef fmin
 202 #undef fpush
 203 #undef fpop
 204 #undef fswap
 205 #undef fvswap
 206 #undef FALLBACK_QSORT_SMALL_THRESH
 207 #undef FALLBACK_QSORT_STACK_SIZE
 208
 209
 210 /*---------------------------------------------*/
 211 /* Pre:
 212       nblock > 0
 213       eclass exists for [0 .. nblock-1]
 214       ((UChar*)eclass) [0 .. nblock-1] holds block
 215       ptr exists for [0 .. nblock-1]
 216
 217    Post:
 218       ((UChar*)eclass) [0 .. nblock-1] holds block
 219       All other areas of eclass destroyed
 220       fmap [0 .. nblock-1] holds sorted order
 221       bhtab [ 0 .. 2+(nblock/32) ] destroyed
 222 */
 223
 224 #define       SET_BH(zz)  bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
 225 #define     CLEAR_BH(zz)  bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
 226 #define     ISSET_BH(zz)  (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
 227 #define      WORD_BH(zz)  bhtab[(zz) >> 5]
 228 #define UNALIGNED_BH(zz)  ((zz) & 0x01f)
 229
 230 void fallbackSort ( UInt32* fmap,
 231                     UInt32* eclass,
 232                     UInt32* bhtab,
 233                     Int32   nblock,
 234                     Int32   verb )
 235 {
 236    Int32 ftab[257];
 237    Int32 ftabCopy[256];
 238    Int32 H, i, j, k, l, r, cc, cc1;
 239    Int32 nNotDone;
 240    Int32 nBhtab;
 241    UChar* eclass8 = (UChar*)eclass;
 242
 243    /*--
 244       Initial 1-char radix sort to generate
 245       initial fmap and initial BH bits.
 246    --*/
 247    for (i = 0; i < 257;    i++) ftab[i] = 0;
 248    for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
 249    for (i = 0; i < 256;    i++) ftabCopy[i] = ftab[i];
 250    for (i = 1; i < 257;    i++) ftab[i] += ftab[i-1];
 251
 252    for (i = 0; i < nblock; i++) {
 253       j = eclass8[i];
 254       k = ftab[j] - 1;
 255       ftab[j] = k;
 256       fmap[k] = i;
 257    }
 258
 259    nBhtab = 2 + (nblock / 32);
 260    for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
 261    for (i = 0; i < 256; i++) SET_BH(ftab[i]);
 262
 263    /*--
 264       Inductively refine the buckets.  Kind-of an
 265       "exponential radix sort" (!), inspired by the
 266       Manber-Myers suffix array construction algorithm.
 267    --*/
 268
 269    /*-- set sentinel bits for block-end detection --*/
 270    for (i = 0; i < 32; i++) {
 271       SET_BH(nblock + 2*i);
 272       CLEAR_BH(nblock + 2*i + 1);
 273    }
 274
 275    /*-- the log(N) loop --*/
 276    H = 1;
 277    while (1) {
 278
 279
 280       j = 0;
 281       for (i = 0; i < nblock; i++) {
 282          if (ISSET_BH(i)) j = i;
 283          k = fmap[i] - H; if (k < 0) k += nblock;
 284          eclass[k] = j;
 285       }
 286
 287       nNotDone = 0;
 288       r = -1;
 289       while (1) {
 290
 291          /*-- find the next non-singleton bucket --*/
 292          k = r + 1;
 293          while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
 294          if (ISSET_BH(k)) {
 295             while (WORD_BH(k) == 0xffffffff) k += 32;
 296             while (ISSET_BH(k)) k++;
 297          }
 298          l = k - 1;
 299          if (l >= nblock) break;
 300          while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
 301          if (!ISSET_BH(k)) {
 302             while (WORD_BH(k) == 0x00000000) k += 32;
 303             while (!ISSET_BH(k)) k++;
 304          }
 305          r = k - 1;
 306          if (r >= nblock) break;
 307
 308          /*-- now [l, r] bracket current bucket --*/
 309          if (r > l) {
 310             nNotDone += (r - l + 1);
 311             fallbackQSort3 ( fmap, eclass, l, r );
 312
 313             /*-- scan bucket and generate header bits-- */
 314             cc = -1;
 315             for (i = l; i <= r; i++) {
 316                cc1 = eclass[fmap[i]];
 317                if (cc != cc1) { SET_BH(i); cc = cc1; };
 318             }
 319          }
 320       }
 321
 322       H *= 2;
 323       if (H > nblock || nNotDone == 0) break;
 324    }
 325
 326    /*--
 327       Reconstruct the original block in
 328       eclass8 [0 .. nblock-1], since the
 329       previous phase destroyed it.
 330    --*/
 331    j = 0;
 332    for (i = 0; i < nblock; i++) {
 333       while (ftabCopy[j] == 0) j++;
 334       ftabCopy[j]--;
 335       eclass8[fmap[i]] = (UChar)j;
 336    }
 337 }
 338
 339 #undef       SET_BH
 340 #undef     CLEAR_BH
 341 #undef     ISSET_BH
 342 #undef      WORD_BH
 343 #undef UNALIGNED_BH
 344
 345
 346 /*---------------------------------------------*/
 347 /*--- The main, O(N^2 log(N)) sorting       ---*/
 348 /*--- algorithm.  Faster for "normal"       ---*/
 349 /*--- non-repetitive blocks.                ---*/
 350 /*---------------------------------------------*/
 351
 352 /*---------------------------------------------*/
 353 Bool mainGtU ( UInt32  i1,
 354                UInt32  i2,
 355                UChar*  block,
 356                UInt16* quadrant,
 357                UInt32  nblock,
 358                Int32*  budget )
 359 {
 360    Int32  k;
 361    UChar  c1, c2;
 362    UInt16 s1, s2;
 363
 364    /* 1 */
 365    c1 = block[i1]; c2 = block[i2];
 366    if (c1 != c2) return (c1 > c2);
 367    i1++; i2++;
 368    /* 2 */
 369    c1 = block[i1]; c2 = block[i2];
 370    if (c1 != c2) return (c1 > c2);
 371    i1++; i2++;
 372    /* 3 */
 373    c1 = block[i1]; c2 = block[i2];
 374    if (c1 != c2) return (c1 > c2);
 375    i1++; i2++;
 376    /* 4 */
 377    c1 = block[i1]; c2 = block[i2];
 378    if (c1 != c2) return (c1 > c2);
 379    i1++; i2++;
 380    /* 5 */
 381    c1 = block[i1]; c2 = block[i2];
 382    if (c1 != c2) return (c1 > c2);
 383    i1++; i2++;
 384    /* 6 */
 385    c1 = block[i1]; c2 = block[i2];
 386    if (c1 != c2) return (c1 > c2);
 387    i1++; i2++;
 388    /* 7 */
 389    c1 = block[i1]; c2 = block[i2];
 390    if (c1 != c2) return (c1 > c2);
 391    i1++; i2++;
 392    /* 8 */
 393    c1 = block[i1]; c2 = block[i2];
 394    if (c1 != c2) return (c1 > c2);
 395    i1++; i2++;
 396    /* 9 */
 397    c1 = block[i1]; c2 = block[i2];
 398    if (c1 != c2) return (c1 > c2);
 399    i1++; i2++;
 400    /* 10 */
 401    c1 = block[i1]; c2 = block[i2];
 402    if (c1 != c2) return (c1 > c2);
 403    i1++; i2++;
 404    /* 11 */
 405    c1 = block[i1]; c2 = block[i2];
 406    if (c1 != c2) return (c1 > c2);
 407    i1++; i2++;
 408    /* 12 */
 409    c1 = block[i1]; c2 = block[i2];
 410    if (c1 != c2) return (c1 > c2);
 411    i1++; i2++;
 412
 413    k = nblock + 8;
 414
 415    do {
 416       /* 1 */
 417       c1 = block[i1]; c2 = block[i2];
 418       if (c1 != c2) return (c1 > c2);
 419       s1 = quadrant[i1]; s2 = quadrant[i2];
 420       if (s1 != s2) return (s1 > s2);
 421       i1++; i2++;
 422       /* 2 */
 423       c1 = block[i1]; c2 = block[i2];
 424       if (c1 != c2) return (c1 > c2);
 425       s1 = quadrant[i1]; s2 = quadrant[i2];
 426       if (s1 != s2) return (s1 > s2);
 427       i1++; i2++;
 428       /* 3 */
 429       c1 = block[i1]; c2 = block[i2];
 430       if (c1 != c2) return (c1 > c2);
 431       s1 = quadrant[i1]; s2 = quadrant[i2];
 432       if (s1 != s2) return (s1 > s2);
 433       i1++; i2++;
 434       /* 4 */
 435       c1 = block[i1]; c2 = block[i2];
 436       if (c1 != c2) return (c1 > c2);
 437       s1 = quadrant[i1]; s2 = quadrant[i2];
 438       if (s1 != s2) return (s1 > s2);
 439       i1++; i2++;
 440       /* 5 */
 441       c1 = block[i1]; c2 = block[i2];
 442       if (c1 != c2) return (c1 > c2);
 443       s1 = quadrant[i1]; s2 = quadrant[i2];
 444       if (s1 != s2) return (s1 > s2);
 445       i1++; i2++;
 446       /* 6 */
 447       c1 = block[i1]; c2 = block[i2];
 448       if (c1 != c2) return (c1 > c2);
 449       s1 = quadrant[i1]; s2 = quadrant[i2];
 450       if (s1 != s2) return (s1 > s2);
 451       i1++; i2++;
 452       /* 7 */
 453       c1 = block[i1]; c2 = block[i2];
 454       if (c1 != c2) return (c1 > c2);
 455       s1 = quadrant[i1]; s2 = quadrant[i2];
 456       if (s1 != s2) return (s1 > s2);
 457       i1++; i2++;
 458       /* 8 */
 459       c1 = block[i1]; c2 = block[i2];
 460       if (c1 != c2) return (c1 > c2);
 461       s1 = quadrant[i1]; s2 = quadrant[i2];
 462       if (s1 != s2) return (s1 > s2);
 463       i1++; i2++;
 464
 465       if (i1 >= nblock) i1 -= nblock;
 466       if (i2 >= nblock) i2 -= nblock;
 467
 468       k -= 8;
 469       (*budget)--;
 470    }
 471       while (k >= 0);
 472
 473    return False;
 474 }
 475
 476
 477 /*---------------------------------------------*/
 478 /*--
 479    Knuth's increments seem to work better
 480    than Incerpi-Sedgewick here.  Possibly
 481    because the number of elems to sort is
 482    usually small, typically <= 20.
 483 --*/
 484 Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
 485                    9841, 29524, 88573, 265720,
 486                    797161, 2391484 };
 487
 488 void mainSimpleSort ( UInt32* ptr,
 489                       UChar*  block,
 490                       UInt16* quadrant,
 491                       Int32   nblock,
 492                       Int32   lo,
 493                       Int32   hi,
 494                       Int32   d,
 495                       Int32*  budget )
 496 {
 497    Int32 i, j, h, bigN, hp;
 498    UInt32 v;
 499
 500    bigN = hi - lo + 1;
 501    if (bigN < 2) return;
 502
 503    hp = 0;
 504    while (incs[hp] < bigN) hp++;
 505    hp--;
 506
 507    for (; hp >= 0; hp--) {
 508       h = incs[hp];
 509
 510       i = lo + h;
 511       while (True) {
 512
 513          /*-- copy 1 --*/
 514          if (i > hi) break;
 515          v = ptr[i];
 516          j = i;
 517          while ( mainGtU (
 518                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget
 519                  ) ) {
 520             ptr[j] = ptr[j-h];
 521             j = j - h;
 522             if (j <= (lo + h - 1)) break;
 523          }
 524          ptr[j] = v;
 525          i++;
 526
 527          /*-- copy 2 --*/
 528          if (i > hi) break;
 529          v = ptr[i];
 530          j = i;
 531          while ( mainGtU (
 532                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget
 533                  ) ) {
 534             ptr[j] = ptr[j-h];
 535             j = j - h;
 536             if (j <= (lo + h - 1)) break;
 537          }
 538          ptr[j] = v;
 539          i++;
 540
 541          /*-- copy 3 --*/
 542          if (i > hi) break;
 543          v = ptr[i];
 544          j = i;
 545          while ( mainGtU (
 546                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget
 547                  ) ) {
 548             ptr[j] = ptr[j-h];
 549             j = j - h;
 550             if (j <= (lo + h - 1)) break;
 551          }
 552          ptr[j] = v;
 553          i++;
 554
 555          if (*budget < 0) return;
 556       }
 557    }
 558 }
 559
 560
 561 /*---------------------------------------------*/
 562 /*--
 563    The following is an implementation of
 564    an elegant 3-way quicksort for strings,
 565    described in a paper "Fast Algorithms for
 566    Sorting and Searching Strings", by Robert
 567    Sedgewick and Jon L. Bentley.
 568 --*/
 569
 570 #define mswap(zz1, zz2) \
 571    { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
 572
 573 #define mvswap(zzp1, zzp2, zzn)       \
 574 {                                     \
 575    Int32 yyp1 = (zzp1);               \
 576    Int32 yyp2 = (zzp2);               \
 577    Int32 yyn  = (zzn);                \
 578    while (yyn > 0) {                  \
 579       mswap(ptr[yyp1], ptr[yyp2]);    \
 580       yyp1++; yyp2++; yyn--;          \
 581    }                                  \
 582 }
 583
 584 UChar mmed3 ( UChar a, UChar b, UChar c )
 585 {
 586    UChar t;
 587    if (a > b) { t = a; a = b; b = t; };
 588    if (b > c) {
 589       b = c;
 590       if (a > b) b = a;
 591    }
 592    return b;
 593 }
 594
 595 #define mmin(a,b) ((a) < (b)) ? (a) : (b)
 596
 597 #define mpush(lz,hz,dz) { stackLo[sp] = lz; \
 598                           stackHi[sp] = hz; \
 599                           stackD [sp] = dz; \
 600                           sp++; }
 601
 602 #define mpop(lz,hz,dz) { sp--;             \
 603                          lz = stackLo[sp]; \
 604                          hz = stackHi[sp]; \
 605                          dz = stackD [sp]; }
 606
 607
 608 #define mnextsize(az) (nextHi[az]-nextLo[az])
 609
 610 #define mnextswap(az,bz)                                        \
 611    { Int32 tz;                                                  \
 612      tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
 613      tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
 614      tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
 615
 616
 617 #define MAIN_QSORT_SMALL_THRESH 20
 618 #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
 619 #define MAIN_QSORT_STACK_SIZE 100
 620
 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       mpop ( lo, hi, d );
 647       if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
 648           d > MAIN_QSORT_DEPTH_THRESH) {
 649          mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
 650          if (*budget < 0) return;
 651          continue;
 652       }
 653
 654       med = (Int32)
 655             mmed3 ( block[ptr[ lo         ]+d],
 656                     block[ptr[ hi         ]+d],
 657                     block[ptr[ (lo+hi)>>1 ]+d] );
 658
 659       unLo = ltLo = lo;
 660       unHi = gtHi = hi;
 661
 662       while (True) {
 663          while (True) {
 664             if (unLo > unHi) break;
 665             n = ((Int32)block[ptr[unLo]+d]) - med;
 666             if (n == 0) {
 667                mswap(ptr[unLo], ptr[ltLo]);
 668                ltLo++; unLo++; continue;
 669             };
 670             if (n >  0) break;
 671             unLo++;
 672          }
 673          while (True) {
 674             if (unLo > unHi) break;
 675             n = ((Int32)block[ptr[unHi]+d]) - med;
 676             if (n == 0) {
 677                mswap(ptr[unHi], ptr[gtHi]);
 678                gtHi--; unHi--; continue;
 679             };
 680             if (n <  0) break;
 681             unHi--;
 682          }
 683          if (unLo > unHi) break;
 684          mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
 685       }
 686
 687       if (gtHi < ltLo) {
 688          mpush(lo, hi, d+1 );
 689          continue;
 690       }
 691
 692       n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
 693       m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
 694
 695       n = lo + unLo - ltLo - 1;
 696       m = hi - (gtHi - unHi) + 1;
 697
 698       nextLo[0] = lo;  nextHi[0] = n;   nextD[0] = d;
 699       nextLo[1] = m;   nextHi[1] = hi;  nextD[1] = d;
 700       nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
 701
 702       if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
 703       if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
 704       if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
 705
 706
 707       mpush (nextLo[0], nextHi[0], nextD[0]);
 708       mpush (nextLo[1], nextHi[1], nextD[1]);
 709       mpush (nextLo[2], nextHi[2], nextD[2]);
 710    }
 711 }