/*-------------------------------------------------------------*/
/*---?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）?
#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