/*-------------------------------------------------------------*//*--- Block sorting machinery                               ---*//*---                                           blocksort.c ---*//*-------------------------------------------------------------*//*--  This file is a part of bzip2 and/or libbzip2, a program and  library for lossless, block-sorting data compression.  Copyright (C) 1996-2000 Julian R Seward.  All rights reserved.  Redistribution and use in source and binary forms, with or without  modification, are permitted provided that the following conditions  are met:  1. Redistributions of source code must retain the above copyright     notice, this list of conditions and the following disclaimer.  2. The origin of this software must not be misrepresented; you must      not claim that you wrote the original software.  If you use this      software in a product, an acknowledgment in the product      documentation would be appreciated but is not required.  3. Altered source versions must be plainly marked as such, and must     not be misrepresented as being the original software.  4. The name of the author may not be used to endorse or promote      products derived from this software without specific prior written      permission.  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE  ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY  DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE  GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.  Julian Seward, Cambridge, UK.  jseward@acm.org  bzip2/libbzip2 version 1.0 of 21 March 2000  This program is based on (at least) the work of:     Mike Burrows     David Wheeler     Peter Fenwick     Alistair Moffat     Radford Neal     Ian H. Witten     Robert Sedgewick     Jon L. Bentley  For more information on these sources, see the manual.  To get some idea how the block sorting algorithms in this file   work, read my paper      On the Performance of BWT Sorting Algorithms  in Proceedings of the IEEE Data Compression Conference 2000,  Snowbird, Utah, USA, 27-30 March 2000.  The main sort in this  file implements the algorithm called  cache  in the paper.--*/#include "bzlib_private.h"/*---------------------------------------------*//*--- Fallback O(N log(N)^2) sorting        ---*//*--- algorithm, for repetitive blocks      ---*//*---------------------------------------------*//*---------------------------------------------*/static __inline__void fallbackSimpleSort ( UInt32* fmap,                           UInt32* eclass,                           Int32   lo,                           Int32   hi ){   Int32 i, j, tmp;   UInt32 ec_tmp;   if (lo == hi) return;   if (hi - lo > 3) {      for ( i = hi-4; i >= lo; i-- ) {         tmp = fmap[i];         ec_tmp = eclass[tmp];         for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )            fmap[j-4] = fmap[j];         fmap[j-4] = tmp;      }   }   for ( i = hi-1; i >= lo; i-- ) {      tmp = fmap[i];      ec_tmp = eclass[tmp];      for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )         fmap[j-1] = fmap[j];      fmap[j-1] = tmp;   }}/*---------------------------------------------*/#define fswap(zz1, zz2) \   { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }#define fvswap(zzp1, zzp2, zzn)       \{                                     \   Int32 yyp1 = (zzp1);               \   Int32 yyp2 = (zzp2);               \   Int32 yyn  = (zzn);                \   while (yyn > 0) {                  \      fswap(fmap[yyp1], fmap[yyp2]);  \      yyp1++; yyp2++; yyn--;          \   }                                  \}#define fmin(a,b) ((a) < (b)) ? (a) : (b)#define fpush(lz,hz) { stackLo[sp] = lz; \                       stackHi[sp] = hz; \                       sp++; }#define fpop(lz,hz) { sp--;              \                      lz = stackLo[sp];  \                      hz = stackHi[sp]; }#define FALLBACK_QSORT_SMALL_THRESH 10#define FALLBACK_QSORT_STACK_SIZE   100staticvoid fallbackQSort3 ( UInt32* fmap,                       UInt32* eclass,                      Int32   loSt,                       Int32   hiSt ){   Int32 unLo, unHi, ltLo, gtHi, n, m;   Int32 sp, lo, hi;   UInt32 med, r, r3;   Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];   Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];   r = 0;   sp = 0;   fpush ( loSt, hiSt );   while (sp > 0) {      AssertH ( sp < FALLBACK_QSORT_STACK_SIZE, 1004 );      fpop ( lo, hi );      if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {         fallbackSimpleSort ( fmap, eclass, lo, hi );         continue;      }      /* Random partitioning.  Median of 3 sometimes fails to         avoid bad cases.  Median of 9 seems to help but          looks rather expensive.  This too seems to work but         is cheaper.  Guidance for the magic constants          7621 and 32768 is taken from Sedgewick's algorithms         book, chapter 35.      */      r = ((r * 7621) + 1) % 32768;      r3 = r % 3;      if (r3 == 0) med = eclass[fmap[lo]]; else      if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else                   med = eclass[fmap[hi]];      unLo = ltLo = lo;      unHi = gtHi = hi;      while (1) {         while (1) {            if (unLo > unHi) break;            n = (Int32)eclass[fmap[unLo]] - (Int32)med;            if (n == 0) {                fswap(fmap[unLo], fmap[ltLo]);                ltLo++; unLo++;                continue;             };            if (n > 0) break;            unLo++;         }         while (1) {            if (unLo > unHi) break;            n = (Int32)eclass[fmap[unHi]] - (Int32)med;            if (n == 0) {                fswap(fmap[unHi], fmap[gtHi]);                gtHi--; unHi--;                continue;             };            if (n < 0) break;            unHi--;         }         if (unLo > unHi) break;         fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;      }      AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );      if (gtHi < ltLo) continue;      n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);      m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);      n = lo + unLo - ltLo - 1;      m = hi - (gtHi - unHi) + 1;      if (n - lo > hi - m) {         fpush ( lo, n );         fpush ( m, hi );      } else {         fpush ( m, hi );         fpush ( lo, n );      }   }}#undef fmin#undef fpush#undef fpop#undef fswap#undef fvswap#undef FALLBACK_QSORT_SMALL_THRESH#undef FALLBACK_QSORT_STACK_SIZE/*---------------------------------------------*//* Pre:      nblock > 0      eclass exists for [0 .. nblock-1]      ((UChar*)eclass) [0 .. nblock-1] holds block      ptr exists for [0 .. nblock-1]   Post:      ((UChar*)eclass) [0 .. nblock-1] holds block      All other areas of eclass destroyed      fmap [0 .. nblock-1] holds sorted order      bhtab [ 0 .. 2+(nblock/32) ] destroyed*/#define       SET_BH(zz)  bhtab[(zz) >> 5] |= (1 << ((zz) & 31))#define     CLEAR_BH(zz)  bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))#define     ISSET_BH(zz)  (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))#define      WORD_BH(zz)  bhtab[(zz) >> 5]#define UNALIGNED_BH(zz)  ((zz) & 0x01f)staticvoid fallbackSort ( UInt32* fmap,                     UInt32* eclass,                     UInt32* bhtab,                    Int32   nblock,                    Int32   verb ){   Int32 ftab[257];   Int32 ftabCopy[256];   Int32 H, i, j, k, l, r, cc, cc1;   Int32 nNotDone;   Int32 nBhtab;   UChar* eclass8 = (UChar*)eclass;   /*--      Initial 1-char radix sort to generate      initial fmap and initial BH bits.   --*/   if (verb >= 4)      VPrintf0 ( "        bucket sorting ...\n" );   for (i = 0; i < 257;    i++) ftab[i] = 0;   for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;   for (i = 0; i < 256;    i++) ftabCopy[i] = ftab[i];   for (i = 1; i < 257;    i++) ftab[i] += ftab[i-1];   for (i = 0; i < nblock; i++) {      j = eclass8[i];      k = ftab[j] - 1;      ftab[j] = k;      fmap[k] = i;   }   nBhtab = 2 + (nblock / 32);   for (i = 0; i < nBhtab; i++) bhtab[i] = 0;   for (i = 0; i < 256; i++) SET_BH(ftab[i]);   /*--      Inductively refine the buckets.  Kind-of an      "exponential radix sort" (!), inspired by the      Manber-Myers suffix array construction algorithm.   --*/   /*-- set sentinel bits for block-end detection --*/   for (i = 0; i < 32; i++) {       SET_BH(nblock + 2*i);      CLEAR_BH(nblock + 2*i + 1);   }   /*-- the log(N) loop --*/   H = 1;   while (1) {      if (verb >= 4)          VPrintf1 ( "        depth %6d has ", H );      j = 0;      for (i = 0; i < nblock; i++) {         if (ISSET_BH(i)) j = i;         k = fmap[i] - H; if (k < 0) k += nblock;         eclass[k] = j;      }      nNotDone = 0;      r = -1;      while (1) {	 /*-- find the next non-singleton bucket --*/         k = r + 1;         while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;         if (ISSET_BH(k)) {            while (WORD_BH(k) == 0xffffffff) k += 32;            while (ISSET_BH(k)) k++;         }         l = k - 1;         if (l >= nblock) break;         while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;         if (!ISSET_BH(k)) {            while (WORD_BH(k) == 0x00000000) k += 32;            while (!ISSET_BH(k)) k++;         }         r = k - 1;         if (r >= nblock) break;         /*-- now [l, r] bracket current bucket --*/         if (r > l) {            nNotDone += (r - l + 1);            fallbackQSort3 ( fmap, eclass, l, r );            /*-- scan bucket and generate header bits-- */            cc = -1;            for (i = l; i <= r; i++) {               cc1 = eclass[fmap[i]];               if (cc != cc1) { SET_BH(i); cc = cc1; };            }         }      }      if (verb >= 4)          VPrintf1 ( "%6d unresolved strings\n", nNotDone );      H *= 2;      if (H > nblock || nNotDone == 0) break;   }   /*--       Reconstruct the original block in      eclass8 [0 .. nblock-1], since the      previous phase destroyed it.   --*/   if (verb >= 4)      VPrintf0 ( "        reconstructing block ...\n" );   j = 0;   for (i = 0; i < nblock; i++) {      while (ftabCopy[j] == 0) j++;      ftabCopy[j]--;      eclass8[fmap[i]] = (UChar)j;   }   AssertH ( j < 256, 1005 );}#undef       SET_BH#undef     CLEAR_BH