blocksort.c

最新的busybox源码

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(EState* state,
		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;
	uint8_t  c1;
	int32_t  numQSorted;
	uint16_t s;
	Bool     bigDone[256];
	/* bbox: moved to EState to save stack
	int32_t  runningOrder[256];
	int32_t  copyStart[256];
	int32_t  copyEnd  [256];
	*/
#define runningOrder (state->mainSort__runningOrder)
#define copyStart    (state->mainSort__copyStart)
#define copyEnd      (state->mainSort__copyEnd)

	/*-- 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 runningOrder
#undef copyStart
#undef copyEnd
}

#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(s, 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 ---*/
/*-------------------------------------------------------------*/