compress.c

最新的busybox源码

/*
 * bzip2 is written by Julian Seward <[e-mail]>.
 * Adapted for busybox by Denys Vlasenko <[e-mail]>.
 * See README and LICENSE files in this directory for more information.
 */

/*-------------------------------------------------------------*/
/*--- Compression machinery (not incl block sorting)        ---*/
/*---                                            compress.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 <[e-mail]>

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.
------------------------------------------------------------------ */

/* CHANGES
 * 0.9.0    -- original version.
 * 0.9.0a/b -- no changes in this file.
 * 0.9.0c   -- changed setting of nGroups in sendMTFValues()
 *             so as to do a bit better on small files
*/

/* #include "bzlib_private.h" */

/*---------------------------------------------------*/
/*--- Bit stream I/O                              ---*/
/*---------------------------------------------------*/

/*---------------------------------------------------*/
static
void BZ2_bsInitWrite(EState* s)
{
	s->bsLive = 0;
	s->bsBuff = 0;
}


/*---------------------------------------------------*/
static NOINLINE
void bsFinishWrite(EState* s)
{
	while (s->bsLive > 0) {
		s->zbits[s->numZ] = (uint8_t)(s->bsBuff >> 24);
		s->numZ++;
		s->bsBuff <<= 8;
		s->bsLive -= 8;
	}
}


/*---------------------------------------------------*/
static
/* Helps only on level 5, on other levels hurts. ? */
#if CONFIG_BZIP2_FEATURE_SPEED >= 5
ALWAYS_INLINE
#endif
void bsW(EState* s, int32_t n, uint32_t v)
{
	while (s->bsLive >= 8) {
		s->zbits[s->numZ] = (uint8_t)(s->bsBuff >> 24);
		s->numZ++;
		s->bsBuff <<= 8;
		s->bsLive -= 8;
	}
	s->bsBuff |= (v << (32 - s->bsLive - n));
	s->bsLive += n;
}


/*---------------------------------------------------*/
static
void bsPutU32(EState* s, unsigned u)
{
	bsW(s, 8, (u >> 24) & 0xff);
	bsW(s, 8, (u >> 16) & 0xff);
	bsW(s, 8, (u >>  8) & 0xff);
	bsW(s, 8,  u        & 0xff);
}


/*---------------------------------------------------*/
static
void bsPutU16(EState* s, unsigned u)
{
	bsW(s, 8, (u >>  8) & 0xff);
	bsW(s, 8,  u        & 0xff);
}


/*---------------------------------------------------*/
/*--- The back end proper                         ---*/
/*---------------------------------------------------*/

/*---------------------------------------------------*/
static
void makeMaps_e(EState* s)
{
	int i;
	s->nInUse = 0;
	for (i = 0; i < 256; i++) {
		if (s->inUse[i]) {
			s->unseqToSeq[i] = s->nInUse;
			s->nInUse++;
		}
	}
}


/*---------------------------------------------------*/
static NOINLINE
void generateMTFValues(EState* s)
{
	uint8_t yy[256];
	int32_t i, j;
	int32_t zPend;
	int32_t wr;
	int32_t EOB;

	/*
	 * After sorting (eg, here),
	 * s->arr1[0 .. s->nblock-1] holds sorted order,
	 * and
	 * ((uint8_t*)s->arr2)[0 .. s->nblock-1]
	 * holds the original block data.
	 *
	 * The first thing to do is generate the MTF values,
	 * and put them in
	 *	((uint16_t*)s->arr1)[0 .. s->nblock-1].
	 * Because there are strictly fewer or equal MTF values
	 * than block values, ptr values in this area are overwritten
	 * with MTF values only when they are no longer needed.
	 *
	 * The final compressed bitstream is generated into the
	 * area starting at
	 *	&((uint8_t*)s->arr2)[s->nblock]
	 *
	 * These storage aliases are set up in bzCompressInit(),
	 * except for the last one, which is arranged in
	 * compressBlock().
	 */
	uint32_t* ptr   = s->ptr;
	uint8_t*  block = s->block;
	uint16_t* mtfv  = s->mtfv;

	makeMaps_e(s);
	EOB = s->nInUse+1;

	for (i = 0; i <= EOB; i++)
		s->mtfFreq[i] = 0;

	wr = 0;
	zPend = 0;
	for (i = 0; i < s->nInUse; i++)
		yy[i] = (uint8_t) i;

	for (i = 0; i < s->nblock; i++) {
		uint8_t ll_i;
		AssertD(wr <= i, "generateMTFValues(1)");
		j = ptr[i] - 1;
		if (j < 0)
			j += s->nblock;
		ll_i = s->unseqToSeq[block[j]];
		AssertD(ll_i < s->nInUse, "generateMTFValues(2a)");

		if (yy[0] == ll_i) {
			zPend++;
		} else {
			if (zPend > 0) {
				zPend--;
				while (1) {
					if (zPend & 1) {
						mtfv[wr] = BZ_RUNB; wr++;
						s->mtfFreq[BZ_RUNB]++;
					} else {
						mtfv[wr] = BZ_RUNA; wr++;
						s->mtfFreq[BZ_RUNA]++;
					}
					if (zPend < 2) break;
					zPend = (uint32_t)(zPend - 2) / 2;
					/* bbox: unsigned div is easier */
				};
				zPend = 0;
			}
			{
				register uint8_t  rtmp;
				register uint8_t* ryy_j;
				register uint8_t  rll_i;
				rtmp  = yy[1];
				yy[1] = yy[0];
				ryy_j = &(yy[1]);
				rll_i = ll_i;
				while (rll_i != rtmp) {
					register uint8_t rtmp2;
					ryy_j++;
					rtmp2  = rtmp;
					rtmp   = *ryy_j;
					*ryy_j = rtmp2;
				};
				yy[0] = rtmp;
				j = ryy_j - &(yy[0]);
				mtfv[wr] = j+1;
				wr++;
				s->mtfFreq[j+1]++;
			}

		}
	}

	if (zPend > 0) {
		zPend--;
		while (1) {
			if (zPend & 1) {
				mtfv[wr] = BZ_RUNB;
				wr++;
				s->mtfFreq[BZ_RUNB]++;
			} else {
				mtfv[wr] = BZ_RUNA;
				wr++;
				s->mtfFreq[BZ_RUNA]++;
			}
			if (zPend < 2)
				break;
			zPend = (uint32_t)(zPend - 2) / 2;
			/* bbox: unsigned div is easier */
		};
		zPend = 0;
	}

	mtfv[wr] = EOB;
	wr++;
	s->mtfFreq[EOB]++;

	s->nMTF = wr;
}


/*---------------------------------------------------*/
#define BZ_LESSER_ICOST  0
#define BZ_GREATER_ICOST 15

static NOINLINE
void sendMTFValues(EState* s)
{
	int32_t v, t, i, j, gs, ge, totc, bt, bc, iter;
	int32_t nSelectors, alphaSize, minLen, maxLen, selCtr;
	int32_t nGroups, nBytes;

	/*
	 * uint8_t len[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
	 * is a global since the decoder also needs it.
	 *
	 * int32_t  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
	 * int32_t  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
	 * are also globals only used in this proc.
	 * Made global to keep stack frame size small.
	 */
#define code     sendMTFValues__code
#define rfreq    sendMTFValues__rfreq
#define len_pack sendMTFValues__len_pack

	uint16_t cost[BZ_N_GROUPS];
	int32_t  fave[BZ_N_GROUPS];

	uint16_t* mtfv = s->mtfv;

	alphaSize = s->nInUse + 2;
	for (t = 0; t < BZ_N_GROUPS; t++)
		for (v = 0; v < alphaSize; v++)
			s->len[t][v] = BZ_GREATER_ICOST;

	/*--- Decide how many coding tables to use ---*/
	AssertH(s->nMTF > 0, 3001);
	if (s->nMTF < 200)  nGroups = 2; else
	if (s->nMTF < 600)  nGroups = 3; else
	if (s->nMTF < 1200) nGroups = 4; else
	if (s->nMTF < 2400) nGroups = 5; else
	nGroups = 6;

	/*--- Generate an initial set of coding tables ---*/
	{
		int32_t nPart, remF, tFreq, aFreq;

		nPart = nGroups;
		remF  = s->nMTF;
		gs = 0;
		while (nPart > 0) {
			tFreq = remF / nPart;
			ge = gs - 1;
			aFreq = 0;
			while (aFreq < tFreq && ge < alphaSize-1) {
				ge++;
				aFreq += s->mtfFreq[ge];
			}

			if (ge > gs
			 && nPart != nGroups && nPart != 1
			 && ((nGroups - nPart) % 2 == 1) /* bbox: can this be replaced by x & 1? */
			) {
				aFreq -= s->mtfFreq[ge];
				ge--;
			}

			for (v = 0; v < alphaSize; v++)
				if (v >= gs && v <= ge)
					s->len[nPart-1][v] = BZ_LESSER_ICOST;
				else
					s->len[nPart-1][v] = BZ_GREATER_ICOST;

			nPart--;
			gs = ge + 1;
			remF -= aFreq;
		}
	}

	/*
	 * Iterate up to BZ_N_ITERS times to improve the tables.
	 */
	for (iter = 0; iter < BZ_N_ITERS; iter++) {
		for (t = 0; t < nGroups; t++)
			fave[t] = 0;

		for (t = 0; t < nGroups; t++)
			for (v = 0; v < alphaSize; v++)
				s->rfreq[t][v] = 0;

#if CONFIG_BZIP2_FEATURE_SPEED >= 5
		/*
		 * Set up an auxiliary length table which is used to fast-track
		 * the common case (nGroups == 6).
		 */
		if (nGroups == 6) {
			for (v = 0; v < alphaSize; v++) {
				s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
				s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];