bzip2-1.0.6.tar.gz

/*-------------------------------------------------------------*/
/*--- Block sorting machinery                               ---*/
/*---                                           blocksort.c ---*/
/*-------------------------------------------------------------*/

/* ------------------------------------------------------------------
   This file is part of bzip2/libbzip2 a program and library for
   lossless block-sorting data compression.

   bzip2/libbzip2 version 1.0.6 of 6 September 2010
   Copyright （C） 1996-2010 Julian Seward 

   Please read the WARNING DISCLAIMER and PATENTS sections in the 
   README file.

   This program is released under the terms of the license contained
   in the file LICENSE.
   ------------------------------------------------------------------ */


#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（ab） （（a） < （b）） ? （a） : （b）

#define fpush（lzhz） { stackLo[sp] = lz; \
                       stackHi[sp] = hz; \
                       sp++; }

#define fpop（lzhz） { sp--;              \
                      lz = stackLo[sp];  \
                      hz = stackHi[sp]; }

#define FALLBACK_QSORT_SMALL_THRESH 10
#define FALLBACK_QSORT_STACK_SIZE   100


static
void 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