wpkg test coverage results

Coverage test results of the Windows Packager by Made to Order Software Corporation.

LCOV - code coverage report
Current view: top level - bzip2 - blocksort.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 442 452 97.8 %
Date: 2013-07-16 Functions: 9 9 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : 
      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      233808 : 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      452337 :    if (lo == hi) return;
      41             : 
      42      218529 :    if (hi - lo > 3) {
      43      455868 :       for ( i = hi-4; i >= lo; i-- ) {
      44      354339 :          tmp = fmap[i];
      45      354339 :          ec_tmp = eclass[tmp];
      46      553417 :          for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
      47      199078 :             fmap[j-4] = fmap[j];
      48      354339 :          fmap[j-4] = tmp;
      49             :       }
      50             :    }
      51             : 
      52     1030055 :    for ( i = hi-1; i >= lo; i-- ) {
      53      811526 :       tmp = fmap[i];
      54      811526 :       ec_tmp = eclass[tmp];
      55     1594319 :       for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
      56      782793 :          fmap[j-1] = fmap[j];
      57      811526 :       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      102367 : 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      102367 :    r = 0;
     105             : 
     106      102367 :    sp = 0;
     107      102367 :    fpush ( loSt, hiSt );
     108             : 
     109      467622 :    while (sp > 0) {
     110             : 
     111      365255 :       AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 );
     112             : 
     113      365255 :       fpop ( lo, hi );
     114      365255 :       if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
     115      233808 :          fallbackSimpleSort ( fmap, eclass, lo, hi );
     116      233808 :          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      131447 :       r = ((r * 7621) + 1) % 32768;
     127      131447 :       r3 = r % 3;
     128      131447 :       if (r3 == 0) med = eclass[fmap[lo]]; else
     129      129426 :       if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
     130       74871 :                    med = eclass[fmap[hi]];
     131             : 
     132      131447 :       unLo = ltLo = lo;
     133      131447 :       unHi = gtHi = hi;
     134             : 
     135             :       while (1) {
     136             :          while (1) {
     137     1398717 :             if (unLo > unHi) break;
     138     1332871 :             n = (Int32)eclass[fmap[unLo]] - (Int32)med;
     139     1332871 :             if (n == 0) { 
     140       45403 :                fswap(fmap[unLo], fmap[ltLo]); 
     141       45403 :                ltLo++; unLo++; 
     142       45403 :                continue; 
     143             :             };
     144     1287468 :             if (n > 0) break;
     145      838962 :             unLo++;
     146      884365 :          }
     147             :          while (1) {
     148     1442746 :             if (unLo > unHi) break;
     149     1311299 :             n = (Int32)eclass[fmap[unHi]] - (Int32)med;
     150     1311299 :             if (n == 0) { 
     151      101465 :                fswap(fmap[unHi], fmap[gtHi]); 
     152      101465 :                gtHi--; unHi--; 
     153      101465 :                continue; 
     154             :             };
     155     1209834 :             if (n < 0) break;
     156      826929 :             unHi--;
     157      928394 :          }
     158      514352 :          if (unLo > unHi) break;
     159      382905 :          fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
     160      382905 :       }
     161             : 
     162             :       AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );
     163             : 
     164      131447 :       if (gtHi < ltLo) continue;
     165             : 
     166      175705 :       n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
     167      232791 :       m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
     168             : 
     169      131444 :       n = lo + unLo - ltLo - 1;
     170      131444 :       m = hi - (gtHi - unHi) + 1;
     171             : 
     172      131444 :       if (n - lo > hi - m) {
     173       64063 :          fpush ( lo, n );
     174       64063 :          fpush ( m, hi );
     175             :       } else {
     176       67381 :          fpush ( m, hi );
     177       67381 :          fpush ( lo, n );
     178             :       }
     179             :    }
     180      102367 : }
     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         209 : 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         209 :    UChar* eclass8 = (UChar*)eclass;
     224             : 
     225             :    /*--
     226             :       Initial 1-char radix sort to generate
     227             :       initial fmap and initial BH bits.
     228             :    --*/
     229         209 :    if (verb >= 4)
     230           0 :       VPrintf0 ( "        bucket sorting ...\n" );
     231       53922 :    for (i = 0; i < 257;    i++) ftab[i] = 0;
     232     1071858 :    for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
     233       53713 :    for (i = 0; i < 256;    i++) ftabCopy[i] = ftab[i];
     234       53713 :    for (i = 1; i < 257;    i++) ftab[i] += ftab[i-1];
     235             : 
     236     1071858 :    for (i = 0; i < nblock; i++) {
     237     1071649 :       j = eclass8[i];
     238     1071649 :       k = ftab[j] - 1;
     239     1071649 :       ftab[j] = k;
     240     1071649 :       fmap[k] = i;
     241             :    }
     242             : 
     243         209 :    nBhtab = 2 + (nblock / 32);
     244       34020 :    for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
     245       53713 :    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        6897 :    for (i = 0; i < 32; i++) { 
     255        6688 :       SET_BH(nblock + 2*i);
     256        6688 :       CLEAR_BH(nblock + 2*i + 1);
     257             :    }
     258             : 
     259             :    /*-- the log(N) loop --*/
     260         209 :    H = 1;
     261             :    while (1) {
     262             : 
     263         648 :       if (verb >= 4) 
     264           0 :          VPrintf1 ( "        depth %6d has ", H );
     265             : 
     266         648 :       j = 0;
     267     3365501 :       for (i = 0; i < nblock; i++) {
     268     3364853 :          if (ISSET_BH(i)) j = i;
     269     3364853 :          k = fmap[i] - H; if (k < 0) k += nblock;
     270     3364853 :          eclass[k] = j;
     271             :       }
     272             : 
     273         648 :       nNotDone = 0;
     274         648 :       r = -1;
     275             :       while (1) {
     276             : 
     277             :          /*-- find the next non-singleton bucket --*/
     278      103015 :          k = r + 1;
     279      638658 :          while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
     280      103015 :          if (ISSET_BH(k)) {
     281       72371 :             while (WORD_BH(k) == 0xffffffff) k += 32;
     282      319067 :             while (ISSET_BH(k)) k++;
     283             :          }
     284      103015 :          l = k - 1;
     285      103015 :          if (l >= nblock) break;
     286      744560 :          while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
     287      102367 :          if (!ISSET_BH(k)) {
     288       33736 :             while (WORD_BH(k) == 0x00000000) k += 32;
     289      409482 :             while (!ISSET_BH(k)) k++;
     290             :          }
     291      102367 :          r = k - 1;
     292      102367 :          if (r >= nblock) break;
     293             : 
     294             :          /*-- now [l, r] bracket current bucket --*/
     295      102367 :          if (r > l) {
     296      102367 :             nNotDone += (r - l + 1);
     297      102367 :             fallbackQSort3 ( fmap, eclass, l, r );
     298             : 
     299             :             /*-- scan bucket and generate header bits-- */
     300      102367 :             cc = -1;
     301     1278344 :             for (i = l; i <= r; i++) {
     302     1175977 :                cc1 = eclass[fmap[i]];
     303     1175977 :                if (cc != cc1) { SET_BH(i); cc = cc1; };
     304             :             }
     305             :          }
     306      102367 :       }
     307             : 
     308         648 :       if (verb >= 4) 
     309           0 :          VPrintf1 ( "%6d unresolved strings\n", nNotDone );
     310             : 
     311         648 :       H *= 2;
     312         648 :       if (H > nblock || nNotDone == 0) break;
     313         439 :    }
     314             : 
     315             :    /*-- 
     316             :       Reconstruct the original block in
     317             :       eclass8 [0 .. nblock-1], since the
     318             :       previous phase destroyed it.
     319             :    --*/
     320         209 :    if (verb >= 4)
     321           0 :       VPrintf0 ( "        reconstructing block ...\n" );
     322         209 :    j = 0;
     323     1071858 :    for (i = 0; i < nblock; i++) {
     324     1124917 :       while (ftabCopy[j] == 0) j++;
     325     1071649 :       ftabCopy[j]--;
     326     1071649 :       eclass8[fmap[i]] = (UChar)j;
     327             :    }
     328         209 :    AssertH ( j < 256, 1005 );
     329         209 : }
     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   160254889 : 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   160254889 :    c1 = block[i1]; c2 = block[i2];
     361   160254889 :    if (c1 != c2) return (c1 > c2);
     362     1257078 :    i1++; i2++;
     363             :    /* 2 */
     364     1257078 :    c1 = block[i1]; c2 = block[i2];
     365     1257078 :    if (c1 != c2) return (c1 > c2);
     366      236157 :    i1++; i2++;
     367             :    /* 3 */
     368      236157 :    c1 = block[i1]; c2 = block[i2];
     369      236157 :    if (c1 != c2) return (c1 > c2);
     370      215268 :    i1++; i2++;
     371             :    /* 4 */
     372      215268 :    c1 = block[i1]; c2 = block[i2];
     373      215268 :    if (c1 != c2) return (c1 > c2);
     374      194818 :    i1++; i2++;
     375             :    /* 5 */
     376      194818 :    c1 = block[i1]; c2 = block[i2];
     377      194818 :    if (c1 != c2) return (c1 > c2);
     378      180027 :    i1++; i2++;
     379             :    /* 6 */
     380      180027 :    c1 = block[i1]; c2 = block[i2];
     381      180027 :    if (c1 != c2) return (c1 > c2);
     382      168291 :    i1++; i2++;
     383             :    /* 7 */
     384      168291 :    c1 = block[i1]; c2 = block[i2];
     385      168291 :    if (c1 != c2) return (c1 > c2);
     386      158919 :    i1++; i2++;
     387             :    /* 8 */
     388      158919 :    c1 = block[i1]; c2 = block[i2];
     389      158919 :    if (c1 != c2) return (c1 > c2);
     390      151084 :    i1++; i2++;
     391             :    /* 9 */
     392      151084 :    c1 = block[i1]; c2 = block[i2];
     393      151084 :    if (c1 != c2) return (c1 > c2);
     394      146592 :    i1++; i2++;
     395             :    /* 10 */
     396      146592 :    c1 = block[i1]; c2 = block[i2];
     397      146592 :    if (c1 != c2) return (c1 > c2);
     398      141964 :    i1++; i2++;
     399             :    /* 11 */
     400      141964 :    c1 = block[i1]; c2 = block[i2];
     401      141964 :    if (c1 != c2) return (c1 > c2);
     402      135024 :    i1++; i2++;
     403             :    /* 12 */
     404      135024 :    c1 = block[i1]; c2 = block[i2];
     405      135024 :    if (c1 != c2) return (c1 > c2);
     406      126667 :    i1++; i2++;
     407             : 
     408      126667 :    k = nblock + 8;
     409             : 
     410             :    do {
     411             :       /* 1 */
     412      253607 :       c1 = block[i1]; c2 = block[i2];
     413      253607 :       if (c1 != c2) return (c1 > c2);
     414      243761 :       s1 = quadrant[i1]; s2 = quadrant[i2];
     415      243761 :       if (s1 != s2) return (s1 > s2);
     416      217229 :       i1++; i2++;
     417             :       /* 2 */
     418      217229 :       c1 = block[i1]; c2 = block[i2];
     419      217229 :       if (c1 != c2) return (c1 > c2);
     420      210977 :       s1 = quadrant[i1]; s2 = quadrant[i2];
     421      210977 :       if (s1 != s2) return (s1 > s2);
     422      193485 :       i1++; i2++;
     423             :       /* 3 */
     424      193485 :       c1 = block[i1]; c2 = block[i2];
     425      193485 :       if (c1 != c2) return (c1 > c2);
     426      185304 :       s1 = quadrant[i1]; s2 = quadrant[i2];
     427      185304 :       if (s1 != s2) return (s1 > s2);
     428      172660 :       i1++; i2++;
     429             :       /* 4 */
     430      172660 :       c1 = block[i1]; c2 = block[i2];
     431      172660 :       if (c1 != c2) return (c1 > c2);
     432      166885 :       s1 = quadrant[i1]; s2 = quadrant[i2];
     433      166885 :       if (s1 != s2) return (s1 > s2);
     434      157660 :       i1++; i2++;
     435             :       /* 5 */
     436      157660 :       c1 = block[i1]; c2 = block[i2];
     437      157660 :       if (c1 != c2) return (c1 > c2);
     438      153558 :       s1 = quadrant[i1]; s2 = quadrant[i2];
     439      153558 :       if (s1 != s2) return (s1 > s2);
     440      148140 :       i1++; i2++;
     441             :       /* 6 */
     442      148140 :       c1 = block[i1]; c2 = block[i2];
     443      148140 :       if (c1 != c2) return (c1 > c2);
     444      144230 :       s1 = quadrant[i1]; s2 = quadrant[i2];
     445      144230 :       if (s1 != s2) return (s1 > s2);
     446      139658 :       i1++; i2++;
     447             :       /* 7 */
     448      139658 :       c1 = block[i1]; c2 = block[i2];
     449      139658 :       if (c1 != c2) return (c1 > c2);
     450      135856 :       s1 = quadrant[i1]; s2 = quadrant[i2];
     451      135856 :       if (s1 != s2) return (s1 > s2);
     452      133540 :       i1++; i2++;
     453             :       /* 8 */
     454      133540 :       c1 = block[i1]; c2 = block[i2];
     455      133540 :       if (c1 != c2) return (c1 > c2);
     456      129663 :       s1 = quadrant[i1]; s2 = quadrant[i2];
     457      129663 :       if (s1 != s2) return (s1 > s2);
     458      126940 :       i1++; i2++;
     459             : 
     460      126940 :       if (i1 >= nblock) i1 -= nblock;
     461      126940 :       if (i2 >= nblock) i2 -= nblock;
     462             : 
     463      126940 :       k -= 8;
     464      126940 :       (*budget)--;
     465             :    }
     466      126940 :       while (k >= 0);
     467             : 
     468   160254889 :    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    33716858 : 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    33716858 :    bigN = hi - lo + 1;
     498    33716858 :    if (bigN < 2) return;
     499             : 
     500    33711659 :    hp = 0;
     501    74230234 :    while (incs[hp] < bigN) hp++;
     502    33711659 :    hp--;
     503             : 
     504    74235433 :    for (; hp >= 0; hp--) {
     505    40518575 :       h = incs[hp];
     506             : 
     507    40518575 :       i = lo + h;
     508             :       while (True) {
     509             : 
     510             :          /*-- copy 1 --*/
     511    60747064 :          if (i > hi) break;
     512    53936437 :          v = ptr[i];
     513    53936437 :          j = i;
     514    65813545 :          while ( mainGtU ( 
     515    65813545 :                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget 
     516             :                  ) ) {
     517    33209614 :             ptr[j] = ptr[j-h];
     518    33209614 :             j = j - h;
     519    33209614 :             if (j <= (lo + h - 1)) break;
     520             :          }
     521    53936437 :          ptr[j] = v;
     522    53936437 :          i++;
     523             : 
     524             :          /*-- copy 2 --*/
     525    53936437 :          if (i > hi) break;
     526    32258896 :          v = ptr[i];
     527    32258896 :          j = i;
     528    53989442 :          while ( mainGtU ( 
     529    53989442 :                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget 
     530             :                  ) ) {
     531    30485834 :             ptr[j] = ptr[j-h];
     532    30485834 :             j = j - h;
     533    30485834 :             if (j <= (lo + h - 1)) break;
     534             :          }
     535    32258896 :          ptr[j] = v;
     536    32258896 :          i++;
     537             : 
     538             :          /*-- copy 3 --*/
     539    32258896 :          if (i > hi) break;
     540    20228489 :          v = ptr[i];
     541    20228489 :          j = i;
     542    40451902 :          while ( mainGtU ( 
     543    40451902 :                     ptr[j-h]+d, v+d, block, quadrant, nblock, budget 
     544             :                  ) ) {
     545    24600057 :             ptr[j] = ptr[j-h];
     546    24600057 :             j = j - h;
     547    24600057 :             if (j <= (lo + h - 1)) break;
     548             :          }
     549    20228489 :          ptr[j] = v;
     550    20228489 :          i++;
     551             : 
     552    20228489 :          if (*budget < 0) return;
     553    20228489 :       }
     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        7779 : UChar mmed3 ( UChar a, UChar b, UChar c )
     584             : {
     585             :    UChar t;
     586        7779 :    if (a > b) { t = a; a = b; b = t; };
     587        7779 :    if (b > c) { 
     588        3903 :       b = c;
     589        3903 :       if (a > b) b = a;
     590             :    }
     591        7779 :    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    33704304 : 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    33704304 :    sp = 0;
     642    33704304 :    mpush ( loSt, hiSt, dSt );
     643             : 
     644    67428941 :    while (sp > 0) {
     645             : 
     646    33724637 :       AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 );
     647             : 
     648    33724637 :       mpop ( lo, hi, d );
     649    33724637 :       if (hi - lo < MAIN_QSORT_SMALL_THRESH || 
     650             :           d > MAIN_QSORT_DEPTH_THRESH) {
     651    33716858 :          mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
     652    67421162 :          if (*budget < 0) return;
     653    33716858 :          continue;
     654             :       }
     655             : 
     656        7779 :       med = (Int32) 
     657        7779 :             mmed3 ( block[ptr[ lo         ]+d],
     658        7779 :                     block[ptr[ hi         ]+d],
     659        7779 :                     block[ptr[ (lo+hi)>>1 ]+d] );
     660             : 
     661        7779 :       unLo = ltLo = lo;
     662        7779 :       unHi = gtHi = hi;
     663             : 
     664             :       while (True) {
     665             :          while (True) {
     666      139191 :             if (unLo > unHi) break;
     667      134761 :             n = ((Int32)block[ptr[unLo]+d]) - med;
     668      134761 :             if (n == 0) { 
     669       80557 :                mswap(ptr[unLo], ptr[ltLo]); 
     670       80557 :                ltLo++; unLo++; continue; 
     671             :             };
     672       54204 :             if (n >  0) break;
     673       33881 :             unLo++;
     674      114438 :          }
     675             :          while (True) {
     676       81418 :             if (unLo > unHi) break;
     677       73639 :             n = ((Int32)block[ptr[unHi]+d]) - med;
     678       73639 :             if (n == 0) { 
     679       23459 :                mswap(ptr[unHi], ptr[gtHi]); 
     680       23459 :                gtHi--; unHi--; continue; 
     681             :             };
     682       50180 :             if (n <  0) break;
     683       33206 :             unHi--;
     684       56665 :          }
     685       24753 :          if (unLo > unHi) break;
     686       16974 :          mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
     687       16974 :       }
     688             : 
     689             :       AssertD ( unHi == unLo-1, "mainQSort3(2)" );
     690             : 
     691        7779 :       if (gtHi < ltLo) {
     692        1502 :          mpush(lo, hi, d+1 );
     693        1502 :          continue;
     694             :       }
     695             : 
     696       17777 :       n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
     697       18389 :       m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
     698             : 
     699        6277 :       n = lo + unLo - ltLo - 1;
     700        6277 :       m = hi - (gtHi - unHi) + 1;
     701             : 
     702        6277 :       nextLo[0] = lo;  nextHi[0] = n;   nextD[0] = d;
     703        6277 :       nextLo[1] = m;   nextHi[1] = hi;  nextD[1] = d;
     704        6277 :       nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
     705             : 
     706        6277 :       if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
     707        6277 :       if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
     708        6277 :       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        6277 :       mpush (nextLo[0], nextHi[0], nextD[0]);
     714        6277 :       mpush (nextLo[1], nextHi[1], nextD[1]);
     715        6277 :       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        2746 : 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        2746 :    if (verb >= 4) VPrintf0 ( "        main sort initialise ...\n" );
     768             : 
     769             :    /*-- set up the 2-byte frequency table --*/
     770   179967348 :    for (i = 65536; i >= 0; i--) ftab[i] = 0;
     771             : 
     772        2746 :    j = block[0] << 8;
     773        2746 :    i = nblock-1;
     774    72104968 :    for (; i >= 3; i -= 4) {
     775    72102222 :       quadrant[i] = 0;
     776    72102222 :       j = (j >> 8) | ( ((UInt16)block[i]) << 8);
     777    72102222 :       ftab[j]++;
     778    72102222 :       quadrant[i-1] = 0;
     779    72102222 :       j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);
     780    72102222 :       ftab[j]++;
     781    72102222 :       quadrant[i-2] = 0;
     782    72102222 :       j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);
     783    72102222 :       ftab[j]++;
     784    72102222 :       quadrant[i-3] = 0;
     785    72102222 :       j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);
     786    72102222 :       ftab[j]++;
     787             :    }
     788        6817 :    for (; i >= 0; i--) {
     789        4071 :       quadrant[i] = 0;
     790        4071 :       j = (j >> 8) | ( ((UInt16)block[i]) << 8);
     791        4071 :       ftab[j]++;
     792             :    }
     793             : 
     794             :    /*-- (emphasises close relationship of block & quadrant) --*/
     795       96110 :    for (i = 0; i < BZ_N_OVERSHOOT; i++) {
     796       93364 :       block   [nblock+i] = block[i];
     797       93364 :       quadrant[nblock+i] = 0;
     798             :    }
     799             : 
     800        2746 :    if (verb >= 4) VPrintf0 ( "        bucket sorting ...\n" );
     801             : 
     802             :    /*-- Complete the initial radix sort --*/
     803   179964602 :    for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
     804             : 
     805        2746 :    s = block[0] << 8;
     806        2746 :    i = nblock-1;
     807    72104968 :    for (; i >= 3; i -= 4) {
     808    72102222 :       s = (s >> 8) | (block[i] << 8);
     809    72102222 :       j = ftab[s] -1;
     810    72102222 :       ftab[s] = j;
     811    72102222 :       ptr[j] = i;
     812    72102222 :       s = (s >> 8) | (block[i-1] << 8);
     813    72102222 :       j = ftab[s] -1;
     814    72102222 :       ftab[s] = j;
     815    72102222 :       ptr[j] = i-1;
     816    72102222 :       s = (s >> 8) | (block[i-2] << 8);
     817    72102222 :       j = ftab[s] -1;
     818    72102222 :       ftab[s] = j;
     819    72102222 :       ptr[j] = i-2;
     820    72102222 :       s = (s >> 8) | (block[i-3] << 8);
     821    72102222 :       j = ftab[s] -1;
     822    72102222 :       ftab[s] = j;
     823    72102222 :       ptr[j] = i-3;
     824             :    }
     825        6817 :    for (; i >= 0; i--) {
     826        4071 :       s = (s >> 8) | (block[i] << 8);
     827        4071 :       j = ftab[s] -1;
     828        4071 :       ftab[s] = j;
     829        4071 :       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      705722 :    for (i = 0; i <= 255; i++) {
     838      702976 :       bigDone     [i] = False;
     839      702976 :       runningOrder[i] = i;
     840             :    }
     841             : 
     842             :    {
     843             :       Int32 vv;
     844        2746 :       Int32 h = 1;
     845       13730 :       do h = 3 * h + 1; while (h <= 256);
     846             :       do {
     847       13730 :          h = h / 3;
     848     3037076 :          for (i = h; i <= 255; i++) {
     849     3023346 :             vv = runningOrder[i];
     850     3023346 :             j = i;
     851     6268952 :             while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
     852     3561851 :                runningOrder[j] = runningOrder[j-h];
     853     3561851 :                j = j - h;
     854     3561851 :                if (j <= (h - 1)) goto zero;
     855             :             }
     856             :             zero:
     857     3023346 :             runningOrder[j] = vv;
     858             :          }
     859       13730 :       } while (h != 1);
     860             :    }
     861             : 
     862             :    /*--
     863             :       The main sorting loop.
     864             :    --*/
     865             : 
     866        2746 :    numQSorted = 0;
     867             : 
     868      705722 :    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      702976 :       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   180664832 :       for (j = 0; j <= 255; j++) {
     887   179961856 :          if (j != ss) {
     888   179258880 :             sb = (ss << 8) + j;
     889   179258880 :             if ( ! (ftab[sb] & SETMASK) ) {
     890    89629440 :                Int32 lo = ftab[sb]   & CLEARMASK;
     891    89629440 :                Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
     892    89629440 :                if (hi > lo) {
     893    33704304 :                   if (verb >= 4)
     894           0 :                      VPrintf4 ( "        qsort [0x%x, 0x%x]   "
     895             :                                 "done %d   this %d\n",
     896             :                                 ss, j, numQSorted, hi - lo + 1 );
     897    33704304 :                   mainQSort3 ( 
     898             :                      ptr, block, quadrant, nblock, 
     899             :                      lo, hi, BZ_N_RADIX, budget 
     900             :                   );   
     901    33704304 :                   numQSorted += (hi - lo + 1);
     902    33707050 :                   if (*budget < 0) return;
     903             :                }
     904             :             }
     905   179258880 :             ftab[sb] |= SETMASK;
     906             :          }
     907             :       }
     908             : 
     909      702976 :       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   180664832 :          for (j = 0; j <= 255; j++) {
     920   179961856 :             copyStart[j] =  ftab[(j << 8) + ss]     & CLEARMASK;
     921   179961856 :             copyEnd  [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
     922             :          }
     923   144843396 :          for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
     924   144140420 :             k = ptr[j]-1; if (k < 0) k += nblock;
     925   144140420 :             c1 = block[k];
     926   144140420 :             if (!bigDone[c1])
     927    72760739 :                ptr[ copyStart[c1]++ ] = k;
     928             :          }
     929   144975515 :          for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
     930   144272539 :             k = ptr[j]-1; if (k < 0) k += nblock;
     931   144272539 :             c1 = block[k];
     932   144272539 :             if (!bigDone[c1]) 
     933    72110275 :                ptr[ copyEnd[c1]-- ] = k;
     934             :          }
     935             :       }
     936             : 
     937      702976 :       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   180664832 :       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      702976 :       bigDone[ss] = True;
     988             : 
     989      702976 :       if (i < 255) {
     990      700230 :          Int32 bbStart  = ftab[ss << 8] & CLEARMASK;
     991      700230 :          Int32 bbSize   = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
     992      700230 :          Int32 shifts   = 0;
     993             : 
     994      700230 :          while ((bbSize >> shifts) > 65534) shifts++;
     995             : 
     996   287779753 :          for (j = bbSize-1; j >= 0; j--) {
     997   287079523 :             Int32 a2update     = ptr[bbStart + j];
     998   287079523 :             UInt16 qVal        = (UInt16)(j >> shifts);
     999   287079523 :             quadrant[a2update] = qVal;
    1000   287079523 :             if (a2update < BZ_N_OVERSHOOT)
    1001       90902 :                quadrant[a2update + nblock] = qVal;
    1002             :          }
    1003      700230 :          AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
    1004             :       }
    1005             : 
    1006             :    }
    1007             : 
    1008        2746 :    if (verb >= 4)
    1009           0 :       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        2955 : void BZ2_blockSort ( EState* s )
    1032             : {
    1033        2955 :    UInt32* ptr    = s->ptr; 
    1034        2955 :    UChar*  block  = s->block;
    1035        2955 :    UInt32* ftab   = s->ftab;
    1036        2955 :    Int32   nblock = s->nblock;
    1037        2955 :    Int32   verb   = s->verbosity;
    1038        2955 :    Int32   wfact  = s->workFactor;
    1039             :    UInt16* quadrant;
    1040             :    Int32   budget;
    1041             :    Int32   budgetInit;
    1042             :    Int32   i;
    1043             : 
    1044        2955 :    if (nblock < 10000) {
    1045         209 :       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        2746 :       i = nblock+BZ_N_OVERSHOOT;
    1053        2746 :       if (i & 1) i++;
    1054        2746 :       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        2746 :       if (wfact < 1  ) wfact = 1;
    1064        2746 :       if (wfact > 100) wfact = 100;
    1065        2746 :       budgetInit = nblock * ((wfact-1) / 3);
    1066        2746 :       budget = budgetInit;
    1067             : 
    1068        2746 :       mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
    1069        2746 :       if (verb >= 3) 
    1070           0 :          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        2746 :       if (budget < 0) {
    1076           0 :          if (verb >= 2) 
    1077           0 :             VPrintf0 ( "    too repetitive; using fallback"
    1078             :                        " sorting algorithm\n" );
    1079           0 :          fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
    1080             :       }
    1081             :    }
    1082             : 
    1083        2955 :    s->origPtr = -1;
    1084   121774501 :    for (i = 0; i < s->nblock; i++)
    1085   121774501 :       if (ptr[i] == 0)
    1086        2955 :          { s->origPtr = i; break; };
    1087             : 
    1088        2955 :    AssertH( s->origPtr != -1, 1003 );
    1089        2955 : }
    1090             : 
    1091             : 
    1092             : /*-------------------------------------------------------------*/
    1093             : /*--- end                                       blocksort.c ---*/
    1094             : /*-------------------------------------------------------------*/

Generated by: LCOV version 1.9

The wpkg tool is an open source tool created by Made to Order Software Corporation.