text: /*
   * bzip2 is written by Julian Seward <jseward@bzip.org>.
   * Adapted for busybox by Denys Vlasenko <vda.linux@googlemail.com>.
   * See README and LICENSE files in this directory for more information.
   */
  
  /*-------------------------------------------------------------*/
  /*--- 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.4 of 20 December 2006
  Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
  
  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" */
  
  #define mswap(zz1, zz2) \
  { \
  	int32_t zztmp = zz1; \
  	zz1 = zz2; \
  	zz2 = zztmp; \
  }
  
  static
  /* No measurable speed gain with inlining */
  /* ALWAYS_INLINE */
  void mvswap(uint32_t* ptr, int32_t zzp1, int32_t zzp2, int32_t zzn)
  {
  	while (zzn > 0) {
  		mswap(ptr[zzp1], ptr[zzp2]);
  		zzp1++;
  		zzp2++;
  		zzn--;
  	}
  }
  
  static
  ALWAYS_INLINE
  int32_t mmin(int32_t a, int32_t b)
  {
  	return (a < b) ? a : b;
  }
  
  
  /*---------------------------------------------*/
  /*--- Fallback O(N log(N)^2) sorting        ---*/
  /*--- algorithm, for repetitive blocks      ---*/
  /*---------------------------------------------*/
  
  /*---------------------------------------------*/
  static
  inline
  void fallbackSimpleSort(uint32_t* fmap,
  		uint32_t* eclass,
  		int32_t   lo,
  		int32_t   hi)
  {
  	int32_t i, j, tmp;
  	uint32_t 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 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   100
  
  static
  void fallbackQSort3(uint32_t* fmap,
  		uint32_t* eclass,
  		int32_t   loSt,
  		int32_t   hiSt)
  {
  	int32_t unLo, unHi, ltLo, gtHi, n, m;
  	int32_t sp, lo, hi;
  	uint32_t med, r, r3;
  	int32_t stackLo[FALLBACK_QSORT_STACK_SIZE];
  	int32_t stackHi[FALLBACK_QSORT_STACK_SIZE];
  
  	r = 0;
  
  	sp = 0;
  	fpush(loSt, hiSt);
  
  	while (sp > 0) {
  		AssertH(sp < FALLBACK_QSORT_STACK_SIZE - 1, 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_t)eclass[fmap[unLo]] - (int32_t)med;
  				if (n == 0) {
  					mswap(fmap[unLo], fmap[ltLo]);
  					ltLo++;
  					unLo++;
  					continue;
  				};
  				if (n > 0) break;
  				unLo++;
  			}
  			while (1) {
  				if (unLo > unHi) break;
  				n = (int32_t)eclass[fmap[unHi]] - (int32_t)med;
  				if (n == 0) {
  					mswap(fmap[unHi], fmap[gtHi]);
  					gtHi--; unHi--;
  					continue;
  				};
  				if (n < 0) break;
  				unHi--;
  			}
  			if (unLo > unHi) break;
  			mswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
  		}
  
  		AssertD(unHi == unLo-1, "fallbackQSort3(2)");
  
  		if (gtHi < ltLo) continue;
  
  		n = mmin(ltLo-lo, unLo-ltLo); mvswap(fmap, lo, unLo-n, n);
  		m = mmin(hi-gtHi, gtHi-unHi); mvswap(fmap, 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 fpush
  #undef fpop
  #undef FALLBACK_QSORT_SMALL_THRESH
  #undef FALLBACK_QSORT_STACK_SIZE
  
  
  /*---------------------------------------------*/
  /* Pre:
   *	nblock > 0
   *	eclass exists for [0 .. nblock-1]
   *	((uint8_t*)eclass) [0 .. nblock-1] holds block
   *	ptr exists for [0 .. nblock-1]
   *
   * Post:
   *	((uint8_t*)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)
  
  static
  void fallbackSort(uint32_t* fmap,
  		uint32_t* eclass,
  		uint32_t* bhtab,
  		int32_t   nblock)
  {
  	int32_t ftab[257];
  	int32_t ftabCopy[256];
  	int32_t H, i, j, k, l, r, cc, cc1;
  	int32_t nNotDone;
  	int32_t nBhtab;
  	uint8_t* eclass8 = (uint8_t*)eclass;
  
  	/*
  	 * Initial 1-char radix sort to generate
  	 * initial fmap and initial BH bits.
  	 */
  	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];
  
  	j = ftab[0];  /* bbox: optimized */
  	for (i = 1; i < 257;    i++) {
  		j += ftab[i];
  		ftab[i] = j;
  	}
  
  	for (i = 0; i < nblock; i++) {
  		j = eclass8[i];
  		k = ftab[j] - 1;
  		ftab[j] = k;
  		fmap[k] = i;
  	}
  
  	nBhtab = 2 + ((uint32_t)nblock / 32); /* bbox: unsigned div is easier */
  	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) {
  		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;
  					};
  				}
  			}
  		}
  
  		H *= 2;
  		if (H > nblock || nNotDone == 0)
  			break;
  	}
  
  	/*
  	 * Reconstruct the original block in
  	 * eclass8 [0 .. nblock-1], since the
  	 * previous phase destroyed it.
  	 */
  	j = 0;
  	for (i = 0; i < nblock; i++) {
  		while (ftabCopy[j] == 0)
  			j++;
  		ftabCopy[j]--;
  		eclass8[fmap[i]] = (uint8_t)j;
  	}
  	AssertH(j < 256, 1005);
  }
  
  #undef       SET_BH
  #undef     CLEAR_BH
  #undef     ISSET_BH
  #undef      WORD_BH
  #undef UNALIGNED_BH
  
  
  /*---------------------------------------------*/
  /*--- The main, O(N^2 log(N)) sorting       ---*/
  /*--- algorithm.  Faster for "normal"       ---*/
  /*--- non-repetitive blocks.                ---*/
  /*---------------------------------------------*/
  
  /*---------------------------------------------*/
  static
  NOINLINE
  int mainGtU(
  		uint32_t  i1,
  		uint32_t  i2,
  		uint8_t*  block,
  		uint16_t* quadrant,
  		uint32_t  nblock,
  		int32_t*  budget)
  {
  	int32_t  k;
  	uint8_t  c1, c2;
  	uint16_t s1, s2;
  
  /* Loop unrolling here is actually very useful
   * (generated code is much simpler),
   * code size increase is only 270 bytes (i386)
   * but speeds up compression 10% overall
   */
  
  #if CONFIG_BZIP2_FEATURE_SPEED >= 1
  
  #define TIMES_8(code) \
  	code; code; code; code; \
  	code; code; code; code;
  #define TIMES_12(code) \
  	code; code; code; code; \
  	code; code; code; code; \
  	code; code; code; code;
  
  #else
  
  #define TIMES_8(code) \
  { \
  	int nn = 8; \
  	do { \
  		code; \
  	} while (--nn); \
  }
  #define TIMES_12(code) \
  { \
  	int nn = 12; \
  	do { \
  		code; \
  	} while (--nn); \
  }
  
  #endif
  
  	AssertD(i1 != i2, "mainGtU");
  	TIMES_12(
  		c1 = block[i1]; c2 = block[i2];
  		if (c1 != c2) return (c1 > c2);
  		i1++; i2++;
  	)
  
  	k = nblock + 8;
  
  	do {
  		TIMES_8(
  			c1 = block[i1]; c2 = block[i2];
  			if (c1 != c2) return (c1 > c2);
  			s1 = quadrant[i1]; s2 = quadrant[i2];
  			if (s1 != s2) return (s1 > s2);
  			i1++; i2++;
  		)
  
  		if (i1 >= nblock) i1 -= nblock;
  		if (i2 >= nblock) i2 -= nblock;
  
  		(*budget)--;
  		k -= 8;
  	} while (k >= 0);
  
  	return False;
  }
  #undef TIMES_8
  #undef TIMES_12
  
  /*---------------------------------------------*/
  /*
   * Knuth's increments seem to work better
   * than Incerpi-Sedgewick here.  Possibly
   * because the number of elems to sort is
   * usually small, typically <= 20.
   */
  static
  const int32_t incs[14] = {
  	1, 4, 13, 40, 121, 364, 1093, 3280,
  	9841, 29524, 88573, 265720,
  	797161, 2391484
  };
  
  static
  void mainSimpleSort(uint32_t* ptr,
  		uint8_t*  block,
  		uint16_t* quadrant,
  		int32_t   nblock,
  		int32_t   lo,
  		int32_t   hi,
  		int32_t   d,
  		int32_t*  budget)
  {
  	int32_t i, j, h, bigN, hp;
  	uint32_t v;
  
  	bigN = hi - lo + 1;
  	if (bigN < 2) return;
  
  	hp = 0;
  	while (incs[hp] < bigN) hp++;
  	hp--;
  
  	for (; hp >= 0; hp--) {
  		h = incs[hp];
  
  		i = lo + h;
  		while (1) {
  			/*-- copy 1 --*/
  			if (i > hi) break;
  			v = ptr[i];
  			j = i;
  			while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) {
  				ptr[j] = ptr[j-h];
  				j = j - h;
  				if (j <= (lo + h - 1)) break;
  			}
  			ptr[j] = v;
  			i++;
  
  /* 1.5% overall speedup, +290 bytes */
  #if CONFIG_BZIP2_FEATURE_SPEED >= 3
  			/*-- copy 2 --*/
  			if (i > hi) break;
  			v = ptr[i];
  			j = i;
  			while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) {
  				ptr[j] = ptr[j-h];
  				j = j - h;
  				if (j <= (lo + h - 1)) break;
  			}
  			ptr[j] = v;
  			i++;
  
  			/*-- copy 3 --*/
  			if (i > hi) break;
  			v = ptr[i];
  			j = i;
  			while (mainGtU(ptr[j-h]+d, v+d, block, quadrant, nblock, budget)) {
  				ptr[j] = ptr[j-h];
  				j = j - h;
  				if (j <= (lo + h - 1)) break;
  			}
  			ptr[j] = v;
  			i++;
  #endif
  			if (*budget < 0) return;
  		}
  	}
  }
  
  
  /*---------------------------------------------*/
  /*
   * The following is an implementation of
   * an elegant 3-way quicksort for strings,
   * described in a paper "Fast Algorithms for
   * Sorting and Searching Strings", by Robert
   * Sedgewick and Jon L. Bentley.
   */
  
  static
  ALWAYS_INLINE
  uint8_t mmed3(uint8_t a, uint8_t b, uint8_t c)
  {
  	uint8_t t;
  	if (a > b) {
  		t = a;
  		a = b;
  		b = t;
  	};
  	/* here b >= a */
  	if (b > c) {
  		b = c;
  		if (a > b)
  			b = a;
  	}
  	return b;
  }
  
  #define mpush(lz,hz,dz) \
  { \
  	stackLo[sp] = lz; \
  	stackHi[sp] = hz; \
  	stackD [sp] = dz; \
  	sp++; \
  }
  
  #define mpop(lz,hz,dz) \
  { \
  	sp--; \
  	lz = stackLo[sp]; \
  	hz = stackHi[sp]; \
  	dz = stackD [sp]; \
  }
  
  #define mnextsize(az) (nextHi[az] - nextLo[az])
  
  #define mnextswap(az,bz) \
  { \
  	int32_t tz; \
  	tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
  	tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
  	tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; \
  }
  
  #define MAIN_QSORT_SMALL_THRESH 20
  #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
  #define MAIN_QSORT_STACK_SIZE   100
  
  static
  void mainQSort3(uint32_t* ptr,
  		uint8_t*  block,
  		uint16_t* quadrant,
  		int32_t   nblock,
  		int32_t   loSt,
  		int32_t   hiSt,
  		int32_t   dSt,
  		int32_t*  budget)
  {
  	int32_t unLo, unHi, ltLo, gtHi, n, m, med;
  	int32_t sp, lo, hi, d;
  
  	int32_t stackLo[MAIN_QSORT_STACK_SIZE];
  	int32_t stackHi[MAIN_QSORT_STACK_SIZE];
  	int32_t stackD [MAIN_QSORT_STACK_SIZE];
  
  	int32_t nextLo[3];
  	int32_t nextHi[3];
  	int32_t nextD [3];
  
  	sp = 0;
  	mpush(loSt, hiSt, dSt);
  
  	while (sp > 0) {
  		AssertH(sp < MAIN_QSORT_STACK_SIZE - 2, 1001);
  
  		mpop(lo, hi, d);
  		if (hi - lo < MAIN_QSORT_SMALL_THRESH
  		 || d > MAIN_QSORT_DEPTH_THRESH
  		) {
  			mainSimpleSort(ptr, block, quadrant, nblock, lo, hi, d, budget);
  			if (*budget < 0)
  				return;
  			continue;
  		}
  		med = (int32_t)	mmed3(block[ptr[lo          ] + d],
  		                      block[ptr[hi          ] + d],
  		                      block[ptr[(lo+hi) >> 1] + d]);
  
  		unLo = ltLo = lo;
  		unHi = gtHi = hi;
  
  		while (1) {
  			while (1) {
  				if (unLo > unHi)
  					break;
  				n = ((int32_t)block[ptr[unLo]+d]) - med;
  				if (n == 0) {
  					mswap(ptr[unLo], ptr[ltLo]);
  					ltLo++;
  					unLo++;
  					continue;
  				};
  				if (n >  0) break;
  				unLo++;
  			}
  			while (1) {
  				if (unLo > unHi)
  					break;
  				n = ((int32_t)block[ptr[unHi]+d]) - med;
  				if (n == 0) {
  					mswap(ptr[unHi], ptr[gtHi]);
  					gtHi--;
  					unHi--;
  					continue;
  				};
  				if (n <  0) break;
  				unHi--;
  			}
  			if (unLo > unHi)
  				break;
  			mswap(ptr[unLo], ptr[unHi]);
  			unLo++;
  			unHi--;
  		}
  
  		AssertD(unHi == unLo-1, "mainQSort3(2)");
  
  		if (gtHi < ltLo) {
  			mpush(lo, hi, d + 1);
  			continue;
  		}
  
  		n = mmin(ltLo-lo, unLo-ltLo); mvswap(ptr, lo, unLo-n, n);
  		m = mmin(hi-gtHi, gtHi-unHi); mvswap(ptr, unLo, hi-m+1, m);
  
  		n = lo + unLo - ltLo - 1;
  		m = hi - (gtHi - unHi) + 1;
  
  		nextLo[0] = lo;  nextHi[0] = n;   nextD[0] = d;
  		nextLo[1] = m;   nextHi[1] = hi;  nextD[1] = d;
  		nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
  
  		if (mnextsize(0) < mnextsize(1)) mnextswap(0, 1);
  		if (mnextsize(1) < mnextsize(2)) mnextswap(1, 2);
  		if (mnextsize(0) < mnextsize(1)) mnextswap(0, 1);
  
  		AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)");
  		AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)");
  
  		mpush(nextLo[0], nextHi[0], nextD[0]);
  		mpush(nextLo[1], nextHi[1], nextD[1]);
  		mpush(nextLo[2], nextHi[2], nextD[2]);
  	}
  }
  
  #undef mpush
  #undef mpop
  #undef mnextsize
  #undef mnextswap
  #undef MAIN_QSORT_SMALL_THRESH
  #undef MAIN_QSORT_DEPTH_THRESH
  #undef MAIN_QSORT_STACK_SIZE
  
  
  /*---------------------------------------------*/
  /* Pre:
   *	nblock > N_OVERSHOOT
   *	block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
   *	((uint8_t*)block32) [0 .. nblock-1] holds block
   *	ptr exists for [0 .. nblock-1]
   *
   * Post:
   *	((uint8_t*)block32) [0 .. nblock-1] holds block
   *	All other areas of block32 destroyed
   *	ftab[0 .. 65536] destroyed
   *	ptr [0 .. nblock-1] holds sorted order
   *	if (*budget < 0), sorting was abandoned
   */
  
  #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
  #define SETMASK (1 << 21)
  #define CLEARMASK (~(SETMASK))
  
  static NOINLINE
  void mainSort(uint32_t*   ptr,
  		uint8_t*  block,
  		uint16_t* quadrant,
  		uint32_t* ftab,
  		int32_t   nblock,
  		int32_t*  budget)
  {
  	int32_t  i, j, k, ss, sb;
  	int32_t  runningOrder[256];
  	Bool     bigDone[256];
  	int32_t  copyStart[256];
  	int32_t  copyEnd  [256];
  	uint8_t  c1;
  	int32_t  numQSorted;
  	uint16_t s;
  
  	/*-- set up the 2-byte frequency table --*/
  	/* was: for (i = 65536; i >= 0; i--) ftab[i] = 0; */
  	memset(ftab, 0, 65537 * sizeof(ftab[0]));
  
  	j = block[0] << 8;
  	i = nblock - 1;
  /* 3%, +300 bytes */
  #if CONFIG_BZIP2_FEATURE_SPEED >= 2
  	for (; i >= 3; i -= 4) {
  		quadrant[i] = 0;
  		j = (j >> 8) | (((uint16_t)block[i]) << 8);
  		ftab[j]++;
  		quadrant[i-1] = 0;
  		j = (j >> 8) | (((uint16_t)block[i-1]) << 8);
  		ftab[j]++;
  		quadrant[i-2] = 0;
  		j = (j >> 8) | (((uint16_t)block[i-2]) << 8);
  		ftab[j]++;
  		quadrant[i-3] = 0;
  		j = (j >> 8) | (((uint16_t)block[i-3]) << 8);
  		ftab[j]++;
  	}
  #endif
  	for (; i >= 0; i--) {
  		quadrant[i] = 0;
  		j = (j >> 8) | (((uint16_t)block[i]) << 8);
  		ftab[j]++;
  	}
  
  	/*-- (emphasises close relationship of block & quadrant) --*/
  	for (i = 0; i < BZ_N_OVERSHOOT; i++) {
  		block   [nblock+i] = block[i];
  		quadrant[nblock+i] = 0;
  	}
  
  	/*-- Complete the initial radix sort --*/
  	j = ftab[0]; /* bbox: optimized */
  	for (i = 1; i <= 65536; i++) {
  		j += ftab[i];
  		ftab[i] = j;
  	}
  
  	s = block[0] << 8;
  	i = nblock - 1;
  #if CONFIG_BZIP2_FEATURE_SPEED >= 2
  	for (; i >= 3; i -= 4) {
  		s = (s >> 8) | (block[i] << 8);
  		j = ftab[s] - 1;
  		ftab[s] = j;
  		ptr[j] = i;
  		s = (s >> 8) | (block[i-1] << 8);
  		j = ftab[s] - 1;
  		ftab[s] = j;
  		ptr[j] = i-1;
  		s = (s >> 8) | (block[i-2] << 8);
  		j = ftab[s] - 1;
  		ftab[s] = j;
  		ptr[j] = i-2;
  		s = (s >> 8) | (block[i-3] << 8);
  		j = ftab[s] - 1;
  		ftab[s] = j;
  		ptr[j] = i-3;
  	}
  #endif
  	for (; i >= 0; i--) {
  		s = (s >> 8) | (block[i] << 8);
  		j = ftab[s] - 1;
  		ftab[s] = j;
  		ptr[j] = i;
  	}
  
  	/*
  	 * Now ftab contains the first loc of every small bucket.
  	 * Calculate the running order, from smallest to largest
  	 * big bucket.
  	 */
  	for (i = 0; i <= 255; i++) {
  		bigDone     [i] = False;
  		runningOrder[i] = i;
  	}
  
  	{
  		int32_t vv;
  		/* bbox: was: int32_t h = 1; */
  		/* do h = 3 * h + 1; while (h <= 256); */
  		uint32_t h = 364;
  
  		do {
  			/*h = h / 3;*/
  			h = (h * 171) >> 9; /* bbox: fast h/3 */
  			for (i = h; i <= 255; i++) {
  				vv = runningOrder[i];
  				j = i;
  				while (BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv)) {
  					runningOrder[j] = runningOrder[j-h];
  					j = j - h;
  					if (j <= (h - 1))
  						goto zero;
  				}
   zero:
  				runningOrder[j] = vv;
  			}
  		} while (h != 1);
  	}
  
  	/*
  	 * The main sorting loop.
  	 */
  
  	numQSorted = 0;
  
  	for (i = 0; i <= 255; i++) {
  
  		/*
  		 * Process big buckets, starting with the least full.
  		 * Basically this is a 3-step process in which we call
  		 * mainQSort3 to sort the small buckets [ss, j], but
  		 * also make a big effort to avoid the calls if we can.
  		 */
  		ss = runningOrder[i];
  
  		/*
  		 * Step 1:
  		 * Complete the big bucket [ss] by quicksorting
  		 * any unsorted small buckets [ss, j], for j != ss.
  		 * Hopefully previous pointer-scanning phases have already
  		 * completed many of the small buckets [ss, j], so
  		 * we don't have to sort them at all.
  		 */
  		for (j = 0; j <= 255; j++) {
  			if (j != ss) {
  				sb = (ss << 8) + j;
  				if (!(ftab[sb] & SETMASK)) {
  					int32_t lo =  ftab[sb]   & CLEARMASK;
  					int32_t hi = (ftab[sb+1] & CLEARMASK) - 1;
  					if (hi > lo) {
  						mainQSort3(
  							ptr, block, quadrant, nblock,
  							lo, hi, BZ_N_RADIX, budget
  						);
  						if (*budget < 0) return;
  						numQSorted += (hi - lo + 1);
  					}
  				}
  				ftab[sb] |= SETMASK;
  			}
  		}
  
  		AssertH(!bigDone[ss], 1006);
  
  		/*
  		 * Step 2:
  		 * Now scan this big bucket [ss] so as to synthesise the
  		 * sorted order for small buckets [t, ss] for all t,
  		 * including, magically, the bucket [ss,ss] too.
  		 * This will avoid doing Real Work in subsequent Step 1's.
  		 */
  		{
  			for (j = 0; j <= 255; j++) {
  				copyStart[j] =  ftab[(j << 8) + ss]     & CLEARMASK;
  				copyEnd  [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
  			}
  			for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
  				k = ptr[j] - 1;
  				if (k < 0)
  					k += nblock;
  				c1 = block[k];
  				if (!bigDone[c1])
  					ptr[copyStart[c1]++] = k;
  			}
  			for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
  				k = ptr[j]-1;
  				if (k < 0)
  					k += nblock;
  				c1 = block[k];
  				if (!bigDone[c1])
  					ptr[copyEnd[c1]--] = k;
  			}
  		}
  
  		/* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
  		 * Necessity for this case is demonstrated by compressing
  		 * a sequence of approximately 48.5 million of character
  		 * 251; 1.0.0/1.0.1 will then die here. */
  		AssertH((copyStart[ss]-1 == copyEnd[ss]) \
  		     || (copyStart[ss] == 0 && copyEnd[ss] == nblock-1), 1007);
  
  		for (j = 0; j <= 255; j++)
  			ftab[(j << 8) + ss] |= SETMASK;
  
  		/*
  		 * Step 3:
  		 * The [ss] big bucket is now done.  Record this fact,
  		 * and update the quadrant descriptors.  Remember to
  		 * update quadrants in the overshoot area too, if
  		 * necessary.  The "if (i < 255)" test merely skips
  		 * this updating for the last bucket processed, since
  		 * updating for the last bucket is pointless.
  		 *
  		 * The quadrant array provides a way to incrementally
  		 * cache sort orderings, as they appear, so as to
  		 * make subsequent comparisons in fullGtU() complete
  		 * faster.  For repetitive blocks this makes a big
  		 * difference (but not big enough to be able to avoid
  		 * the fallback sorting mechanism, exponential radix sort).
  		 *
  		 * The precise meaning is: at all times:
  		 *
  		 *	for 0 <= i < nblock and 0 <= j <= nblock
  		 *
  		 *	if block[i] != block[j],
  		 *
  		 *		then the relative values of quadrant[i] and
  		 *			  quadrant[j] are meaningless.
  		 *
  		 *		else {
  		 *			if quadrant[i] < quadrant[j]
  		 *				then the string starting at i lexicographically
  		 *				precedes the string starting at j
  		 *
  		 *			else if quadrant[i] > quadrant[j]
  		 *				then the string starting at j lexicographically
  		 *				precedes the string starting at i
  		 *
  		 *			else
  		 *				the relative ordering of the strings starting
  		 *				at i and j has not yet been determined.
  		 *		}
  		 */
  		bigDone[ss] = True;
  
  		if (i < 255) {
  			int32_t bbStart = ftab[ss << 8] & CLEARMASK;
  			int32_t bbSize  = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
  			int32_t shifts  = 0;
  
  			while ((bbSize >> shifts) > 65534) shifts++;
  
  			for (j = bbSize-1; j >= 0; j--) {
  				int32_t a2update   = ptr[bbStart + j];
  				uint16_t qVal      = (uint16_t)(j >> shifts);
  				quadrant[a2update] = qVal;
  				if (a2update < BZ_N_OVERSHOOT)
  					quadrant[a2update + nblock] = qVal;
  			}
  			AssertH(((bbSize-1) >> shifts) <= 65535, 1002);
  		}
  	}
  }
  
  #undef BIGFREQ
  #undef SETMASK
  #undef CLEARMASK
  
  
  /*---------------------------------------------*/
  /* Pre:
   *	nblock > 0
   *	arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
   *	  ((uint8_t*)arr2)[0 .. nblock-1] holds block
   *	arr1 exists for [0 .. nblock-1]
   *
   * Post:
   *	((uint8_t*)arr2) [0 .. nblock-1] holds block
   *	All other areas of block destroyed
   *	ftab[0 .. 65536] destroyed
   *	arr1[0 .. nblock-1] holds sorted order
   */
  static NOINLINE
  void BZ2_blockSort(EState* s)
  {
  	/* In original bzip2 1.0.4, it's a parameter, but 30
  	 * (which was the default) should work ok. */
  	enum { wfact = 30 };
  
  	uint32_t* ptr    = s->ptr;
  	uint8_t*  block  = s->block;
  	uint32_t* ftab   = s->ftab;
  	int32_t   nblock = s->nblock;
  	uint16_t* quadrant;
  	int32_t   budget;
  	int32_t   i;
  
  	if (nblock < 10000) {
  		fallbackSort(s->arr1, s->arr2, ftab, nblock);
  	} else {
  		/* Calculate the location for quadrant, remembering to get
  		 * the alignment right.  Assumes that &(block[0]) is at least
  		 * 2-byte aligned -- this should be ok since block is really
  		 * the first section of arr2.
  		 */
  		i = nblock + BZ_N_OVERSHOOT;
  		if (i & 1) i++;
  		quadrant = (uint16_t*)(&(block[i]));
  
  		/* (wfact-1) / 3 puts the default-factor-30
  		 * transition point at very roughly the same place as
  		 * with v0.1 and v0.9.0.
  		 * Not that it particularly matters any more, since the
  		 * resulting compressed stream is now the same regardless
  		 * of whether or not we use the main sort or fallback sort.
  		 */
  		budget = nblock * ((wfact-1) / 3);
  
  		mainSort(ptr, block, quadrant, ftab, nblock, &budget);
  		if (budget < 0) {
  			fallbackSort(s->arr1, s->arr2, ftab, nblock);
  		}
  	}
  
  	s->origPtr = -1;
  	for (i = 0; i < s->nblock; i++)
  		if (ptr[i] == 0) {
  			s->origPtr = i;
  			break;
  		};
  
  	AssertH(s->origPtr != -1, 1003);
  }
  
  
  /*-------------------------------------------------------------*/
  /*--- end                                       blocksort.c ---*/
  /*-------------------------------------------------------------*/
  