archival/bz/compress.c

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

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

/* 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];
				s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
			}
		}
#endif
		nSelectors = 0;
		totc = 0;
		gs = 0;
		while (1) {
			/*--- Set group start & end marks. --*/
			if (gs >= s->nMTF)
				break;
			ge = gs + BZ_G_SIZE - 1;
			if (ge >= s->nMTF)
				ge = s->nMTF-1;

			/*
			 * Calculate the cost of this group as coded
			 * by each of the coding tables.
			 */
			for (t = 0; t < nGroups; t++)
				cost[t] = 0;
#if CONFIG_BZIP2_FEATURE_SPEED >= 5
			if (nGroups == 6 && 50 == ge-gs+1) {
				/*--- fast track the common case ---*/
				register uint32_t cost01, cost23, cost45;
				register uint16_t icv;
				cost01 = cost23 = cost45 = 0;
#define BZ_ITER(nn) \
	icv = mtfv[gs+(nn)]; \
	cost01 += s->len_pack[icv][0]; \
	cost23 += s->len_pack[icv][1]; \
	cost45 += s->len_pack[icv][2];
				BZ_ITER(0);  BZ_ITER(1);  BZ_ITER(2);  BZ_ITER(3);  BZ_ITER(4);
				BZ_ITER(5);  BZ_ITER(6);  BZ_ITER(7);  BZ_ITER(8);  BZ_ITER(9);
				BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
				BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
				BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
				BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
				BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
				BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
				BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
				BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
#undef BZ_ITER
				cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
				cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
				cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;

			} else
#endif
			{
				/*--- slow version which correctly handles all situations ---*/
				for (i = gs; i <= ge; i++) {
					uint16_t icv = mtfv[i];
					for (t = 0; t < nGroups; t++)
						cost[t] += s->len[t][icv];
				}
			}
			/*
			 * Find the coding table which is best for this group,
			 * and record its identity in the selector table.
			 */
			/*bc = 999999999;*/
			/*bt = -1;*/
			bc = cost[0];
			bt = 0;
			for (t = 1 /*0*/; t < nGroups; t++) {
				if (cost[t] < bc) {
					bc = cost[t];
					bt = t;
				}
			}
			totc += bc;
			fave[bt]++;
			s->selector[nSelectors] = bt;
			nSelectors++;

			/*
			 * Increment the symbol frequencies for the selected table.
			 */
/* 1% faster compress. +800 bytes */
#if CONFIG_BZIP2_FEATURE_SPEED >= 4
			if (nGroups == 6 && 50 == ge-gs+1) {
				/*--- fast track the common case ---*/
#define BZ_ITUR(nn) s->rfreq[bt][mtfv[gs + (nn)]]++
				BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
				BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
				BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
				BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
				BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
				BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
				BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
				BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
				BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
				BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
#undef BZ_ITUR
				gs = ge + 1;
			} else
#endif
			{
				/*--- slow version which correctly handles all situations ---*/
				while (gs <= ge) {
					s->rfreq[bt][mtfv[gs]]++;
					gs++;
				}
				/* already is: gs = ge + 1; */
			}
		}

		/*
		 * Recompute the tables based on the accumulated frequencies.
		 */
		/* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See
		 * comment in huffman.c for details. */
		for (t = 0; t < nGroups; t++)
			BZ2_hbMakeCodeLengths(s, &(s->len[t][0]), &(s->rfreq[t][0]), alphaSize, 17 /*20*/);
	}

	AssertH(nGroups < 8, 3002);
	AssertH(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZ_G_SIZE)),	3003);

	/*--- Compute MTF values for the selectors. ---*/
	{
		uint8_t pos[BZ_N_GROUPS], ll_i, tmp2, tmp;

		for (i = 0; i < nGroups; i++)
			pos[i] = i;
		for (i = 0; i < nSelectors; i++) {
			ll_i = s->selector[i];
			j = 0;
			tmp = pos[j];
			while (ll_i != tmp) {
				j++;
				tmp2 = tmp;
				tmp = pos[j];
				pos[j] = tmp2;
			};
			pos[0] = tmp;
			s->selectorMtf[i] = j;
		}
	};

	/*--- Assign actual codes for the tables. --*/
	for (t = 0; t < nGroups; t++) {
		minLen = 32;
		maxLen = 0;
		for (i = 0; i < alphaSize; i++) {
			if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
			if (s->len[t][i] < minLen) minLen = s->len[t][i];
		}
		AssertH(!(maxLen > 17 /*20*/), 3004);
		AssertH(!(minLen < 1), 3005);
		BZ2_hbAssignCodes(&(s->code[t][0]), &(s->len[t][0]), minLen, maxLen, alphaSize);
	}

	/*--- Transmit the mapping table. ---*/
	{
		/* bbox: optimized a bit more than in bzip2 */
		int inUse16 = 0;
		for (i = 0; i < 16; i++) {
			if (sizeof(long) <= 4) {
				inUse16 = inUse16*2 +
					((*(uint32_t*)&(s->inUse[i * 16 + 0])
					| *(uint32_t*)&(s->inUse[i * 16 + 4])
					| *(uint32_t*)&(s->inUse[i * 16 + 8])
					| *(uint32_t*)&(s->inUse[i * 16 + 12])) != 0);
			} else { /* Our CPU can do better */
				inUse16 = inUse16*2 +
					((*(uint64_t*)&(s->inUse[i * 16 + 0])
					| *(uint64_t*)&(s->inUse[i * 16 + 8])) != 0);
			}
		}

		nBytes = s->numZ;
		bsW(s, 16, inUse16);

		inUse16 <<= (sizeof(int)*8 - 16); /* move 15th bit into sign bit */
		for (i = 0; i < 16; i++) {
			if (inUse16 < 0) {
				unsigned v16 = 0;
				for (j = 0; j < 16; j++)
					v16 = v16*2 + s->inUse[i * 16 + j];
				bsW(s, 16, v16);
			}
			inUse16 <<= 1;
		}
	}

	/*--- Now the selectors. ---*/
	nBytes = s->numZ;
	bsW(s, 3, nGroups);
	bsW(s, 15, nSelectors);
	for (i = 0; i < nSelectors; i++) {
		for (j = 0; j < s->selectorMtf[i]; j++)
			bsW(s, 1, 1);
		bsW(s, 1, 0);
	}

	/*--- Now the coding tables. ---*/
	nBytes = s->numZ;

	for (t = 0; t < nGroups; t++) {
		int32_t curr = s->len[t][0];
		bsW(s, 5, curr);
		for (i = 0; i < alphaSize; i++) {
			while (curr < s->len[t][i]) { bsW(s, 2, 2); curr++; /* 10 */ };
			while (curr > s->len[t][i]) { bsW(s, 2, 3); curr--; /* 11 */ };
			bsW(s, 1, 0);
		}
	}

	/*--- And finally, the block data proper ---*/
	nBytes = s->numZ;
	selCtr = 0;
	gs = 0;
	while (1) {
		if (gs >= s->nMTF)
			break;
		ge = gs + BZ_G_SIZE - 1;
		if (ge >= s->nMTF)
			ge = s->nMTF-1;
		AssertH(s->selector[selCtr] < nGroups, 3006);

/* Costs 1300 bytes and is _slower_ (on Intel Core 2) */
#if 0
		if (nGroups == 6 && 50 == ge-gs+1) {
			/*--- fast track the common case ---*/
			uint16_t mtfv_i;
			uint8_t* s_len_sel_selCtr  = &(s->len[s->selector[selCtr]][0]);
			int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
#define BZ_ITAH(nn) \
	mtfv_i = mtfv[gs+(nn)]; \
	bsW(s, s_len_sel_selCtr[mtfv_i], s_code_sel_selCtr[mtfv_i])
			BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
			BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
			BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
			BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
			BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
			BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
			BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
			BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
			BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
			BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
#undef BZ_ITAH
			gs = ge+1;
		} else
#endif
		{
			/*--- slow version which correctly handles all situations ---*/
			/* code is bit bigger, but moves multiply out of the loop */
			uint8_t* s_len_sel_selCtr  = &(s->len [s->selector[selCtr]][0]);
			int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
			while (gs <= ge) {
				bsW(s,
					s_len_sel_selCtr[mtfv[gs]],
					s_code_sel_selCtr[mtfv[gs]]
				);
				gs++;
			}
			/* already is: gs = ge+1; */
		}
		selCtr++;
	}
	AssertH(selCtr == nSelectors, 3007);
#undef code
#undef rfreq
#undef len_pack
}


/*---------------------------------------------------*/
static
void BZ2_compressBlock(EState* s, int is_last_block)
{
	if (s->nblock > 0) {
		BZ_FINALISE_CRC(s->blockCRC);
		s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
		s->combinedCRC ^= s->blockCRC;
		if (s->blockNo > 1)
			s->numZ = 0;

		BZ2_blockSort(s);
	}

	s->zbits = &((uint8_t*)s->arr2)[s->nblock];

	/*-- If this is the first block, create the stream header. --*/
	if (s->blockNo == 1) {
		BZ2_bsInitWrite(s);
		/*bsPutU8(s, BZ_HDR_B);*/
		/*bsPutU8(s, BZ_HDR_Z);*/
		/*bsPutU8(s, BZ_HDR_h);*/
		/*bsPutU8(s, BZ_HDR_0 + s->blockSize100k);*/
		bsPutU32(s, BZ_HDR_BZh0 + s->blockSize100k);
	}

	if (s->nblock > 0) {
		/*bsPutU8(s, 0x31);*/
		/*bsPutU8(s, 0x41);*/
		/*bsPutU8(s, 0x59);*/
		/*bsPutU8(s, 0x26);*/
		bsPutU32(s, 0x31415926);
		/*bsPutU8(s, 0x53);*/
		/*bsPutU8(s, 0x59);*/
		bsPutU16(s, 0x5359);

		/*-- Now the block's CRC, so it is in a known place. --*/
		bsPutU32(s, s->blockCRC);

		/*
		 * Now a single bit indicating (non-)randomisation.
		 * As of version 0.9.5, we use a better sorting algorithm
		 * which makes randomisation unnecessary.  So always set
		 * the randomised bit to 'no'.  Of course, the decoder
		 * still needs to be able to handle randomised blocks
		 * so as to maintain backwards compatibility with
		 * older versions of bzip2.
		 */
		bsW(s, 1, 0);

		bsW(s, 24, s->origPtr);
		generateMTFValues(s);
		sendMTFValues(s);
	}

	/*-- If this is the last block, add the stream trailer. --*/
	if (is_last_block) {
		/*bsPutU8(s, 0x17);*/
		/*bsPutU8(s, 0x72);*/
		/*bsPutU8(s, 0x45);*/
		/*bsPutU8(s, 0x38);*/
		bsPutU32(s, 0x17724538);
		/*bsPutU8(s, 0x50);*/
		/*bsPutU8(s, 0x90);*/
		bsPutU16(s, 0x5090);
		bsPutU32(s, s->combinedCRC);
		bsFinishWrite(s);
	}
}


/*-------------------------------------------------------------*/
/*--- end                                        compress.c ---*/
/*-------------------------------------------------------------*/
1	niro	816	/*
2			* bzip2 is written by Julian Seward <jseward@bzip.org>.
3			* Adapted for busybox by Denys Vlasenko <vda.linux@googlemail.com>.
4			* See README and LICENSE files in this directory for more information.
5			*/
6
7			/-------------------------------------------------------------/
8			/--- Compression machinery (not incl block sorting) ---/
9			/--- compress.c ---/
10			/-------------------------------------------------------------/
11
12			/* ------------------------------------------------------------------
13			This file is part of bzip2/libbzip2, a program and library for
14			lossless, block-sorting data compression.
15
16			bzip2/libbzip2 version 1.0.4 of 20 December 2006
17			Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
18
19			Please read the WARNING, DISCLAIMER and PATENTS sections in the
20			README file.
21
22			This program is released under the terms of the license contained
23			in the file LICENSE.
24			------------------------------------------------------------------ */
25
26			/* CHANGES
27			* 0.9.0 -- original version.
28			* 0.9.0a/b -- no changes in this file.
29			* 0.9.0c -- changed setting of nGroups in sendMTFValues()
30			* so as to do a bit better on small files
31			*/
32
33			/* #include "bzlib_private.h" */
34
35			/---------------------------------------------------/
36			/--- Bit stream I/O ---/
37			/---------------------------------------------------/
38
39			/---------------------------------------------------/
40			static
41			void BZ2_bsInitWrite(EState* s)
42			{
43			s->bsLive = 0;
44			s->bsBuff = 0;
45			}
46
47
48			/---------------------------------------------------/
49			static NOINLINE
50			void bsFinishWrite(EState* s)
51			{
52			while (s->bsLive > 0) {
53			s->zbits[s->numZ] = (uint8_t)(s->bsBuff >> 24);
54			s->numZ++;
55			s->bsBuff <<= 8;
56			s->bsLive -= 8;
57			}
58			}
59
60
61			/---------------------------------------------------/
62			static
63			/* Helps only on level 5, on other levels hurts. ? */
64			#if CONFIG_BZIP2_FEATURE_SPEED >= 5
65			ALWAYS_INLINE
66			#endif
67			void bsW(EState* s, int32_t n, uint32_t v)
68			{
69			while (s->bsLive >= 8) {
70			s->zbits[s->numZ] = (uint8_t)(s->bsBuff >> 24);
71			s->numZ++;
72			s->bsBuff <<= 8;
73			s->bsLive -= 8;
74			}
75			s->bsBuff \|= (v << (32 - s->bsLive - n));
76			s->bsLive += n;
77			}
78
79
80			/---------------------------------------------------/
81			static
82			void bsPutU32(EState* s, unsigned u)
83			{
84			bsW(s, 8, (u >> 24) & 0xff);
85			bsW(s, 8, (u >> 16) & 0xff);
86			bsW(s, 8, (u >> 8) & 0xff);
87			bsW(s, 8, u & 0xff);
88			}
89
90
91			/---------------------------------------------------/
92			static
93			void bsPutU16(EState* s, unsigned u)
94			{
95			bsW(s, 8, (u >> 8) & 0xff);
96			bsW(s, 8, u & 0xff);
97			}
98
99
100			/---------------------------------------------------/
101			/--- The back end proper ---/
102			/---------------------------------------------------/
103
104			/---------------------------------------------------/
105			static
106			void makeMaps_e(EState* s)
107			{
108			int i;
109			s->nInUse = 0;
110			for (i = 0; i < 256; i++) {
111			if (s->inUse[i]) {
112			s->unseqToSeq[i] = s->nInUse;
113			s->nInUse++;
114			}
115			}
116			}
117
118
119			/---------------------------------------------------/
120			static NOINLINE
121			void generateMTFValues(EState* s)
122			{
123			uint8_t yy[256];
124			int32_t i, j;
125			int32_t zPend;
126			int32_t wr;
127			int32_t EOB;
128
129			/*
130			* After sorting (eg, here),
131			* s->arr1[0 .. s->nblock-1] holds sorted order,
132			* and
133			* ((uint8_t*)s->arr2)[0 .. s->nblock-1]
134			* holds the original block data.
135			*
136			* The first thing to do is generate the MTF values,
137			* and put them in
138			* ((uint16_t*)s->arr1)[0 .. s->nblock-1].
139			* Because there are strictly fewer or equal MTF values
140			* than block values, ptr values in this area are overwritten
141			* with MTF values only when they are no longer needed.
142			*
143			* The final compressed bitstream is generated into the
144			* area starting at
145			* &((uint8_t*)s->arr2)[s->nblock]
146			*
147			* These storage aliases are set up in bzCompressInit(),
148			* except for the last one, which is arranged in
149			* compressBlock().
150			*/
151			uint32_t* ptr = s->ptr;
152			uint8_t* block = s->block;
153			uint16_t* mtfv = s->mtfv;
154
155			makeMaps_e(s);
156			EOB = s->nInUse+1;
157
158			for (i = 0; i <= EOB; i++)
159			s->mtfFreq[i] = 0;
160
161			wr = 0;
162			zPend = 0;
163			for (i = 0; i < s->nInUse; i++)
164			yy[i] = (uint8_t) i;
165
166			for (i = 0; i < s->nblock; i++) {
167			uint8_t ll_i;
168			AssertD(wr <= i, "generateMTFValues(1)");
169			j = ptr[i] - 1;
170			if (j < 0)
171			j += s->nblock;
172			ll_i = s->unseqToSeq[block[j]];
173			AssertD(ll_i < s->nInUse, "generateMTFValues(2a)");
174
175			if (yy[0] == ll_i) {
176			zPend++;
177			} else {
178			if (zPend > 0) {
179			zPend--;
180			while (1) {
181			if (zPend & 1) {
182			mtfv[wr] = BZ_RUNB; wr++;
183			s->mtfFreq[BZ_RUNB]++;
184			} else {
185			mtfv[wr] = BZ_RUNA; wr++;
186			s->mtfFreq[BZ_RUNA]++;
187			}
188			if (zPend < 2) break;
189			zPend = (uint32_t)(zPend - 2) / 2;
190			/* bbox: unsigned div is easier */
191			};
192			zPend = 0;
193			}
194			{
195			register uint8_t rtmp;
196			register uint8_t* ryy_j;
197			register uint8_t rll_i;
198			rtmp = yy[1];
199			yy[1] = yy[0];
200			ryy_j = &(yy[1]);
201			rll_i = ll_i;
202			while (rll_i != rtmp) {
203			register uint8_t rtmp2;
204			ryy_j++;
205			rtmp2 = rtmp;
206			rtmp = *ryy_j;
207			*ryy_j = rtmp2;
208			};
209			yy[0] = rtmp;
210			j = ryy_j - &(yy[0]);
211			mtfv[wr] = j+1;
212			wr++;
213			s->mtfFreq[j+1]++;
214			}
215
216			}
217			}
218
219			if (zPend > 0) {
220			zPend--;
221			while (1) {
222			if (zPend & 1) {
223			mtfv[wr] = BZ_RUNB;
224			wr++;
225			s->mtfFreq[BZ_RUNB]++;
226			} else {
227			mtfv[wr] = BZ_RUNA;
228			wr++;
229			s->mtfFreq[BZ_RUNA]++;
230			}
231			if (zPend < 2)
232			break;
233			zPend = (uint32_t)(zPend - 2) / 2;
234			/* bbox: unsigned div is easier */
235			};
236			zPend = 0;
237			}
238
239			mtfv[wr] = EOB;
240			wr++;
241			s->mtfFreq[EOB]++;
242
243			s->nMTF = wr;
244			}
245
246
247			/---------------------------------------------------/
248			#define BZ_LESSER_ICOST 0
249			#define BZ_GREATER_ICOST 15
250
251			static NOINLINE
252			void sendMTFValues(EState* s)
253			{
254			int32_t v, t, i, j, gs, ge, totc, bt, bc, iter;
255			int32_t nSelectors, alphaSize, minLen, maxLen, selCtr;
256			int32_t nGroups, nBytes;
257
258			/*
259			* uint8_t len[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
260			* is a global since the decoder also needs it.
261			*
262			* int32_t code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
263			* int32_t rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
264			* are also globals only used in this proc.
265			* Made global to keep stack frame size small.
266			*/
267			#define code sendMTFValues__code
268			#define rfreq sendMTFValues__rfreq
269			#define len_pack sendMTFValues__len_pack
270
271			uint16_t cost[BZ_N_GROUPS];
272			int32_t fave[BZ_N_GROUPS];
273
274			uint16_t* mtfv = s->mtfv;
275
276			alphaSize = s->nInUse + 2;
277			for (t = 0; t < BZ_N_GROUPS; t++)
278			for (v = 0; v < alphaSize; v++)
279			s->len[t][v] = BZ_GREATER_ICOST;
280
281			/--- Decide how many coding tables to use ---/
282			AssertH(s->nMTF > 0, 3001);
283			if (s->nMTF < 200) nGroups = 2; else
284			if (s->nMTF < 600) nGroups = 3; else
285			if (s->nMTF < 1200) nGroups = 4; else
286			if (s->nMTF < 2400) nGroups = 5; else
287			nGroups = 6;
288
289			/--- Generate an initial set of coding tables ---/
290			{
291			int32_t nPart, remF, tFreq, aFreq;
292
293			nPart = nGroups;
294			remF = s->nMTF;
295			gs = 0;
296			while (nPart > 0) {
297			tFreq = remF / nPart;
298			ge = gs - 1;
299			aFreq = 0;
300			while (aFreq < tFreq && ge < alphaSize-1) {
301			ge++;
302			aFreq += s->mtfFreq[ge];
303			}
304
305			if (ge > gs
306			&& nPart != nGroups && nPart != 1
307			&& ((nGroups - nPart) % 2 == 1) /* bbox: can this be replaced by x & 1? */
308			) {
309			aFreq -= s->mtfFreq[ge];
310			ge--;
311			}
312
313			for (v = 0; v < alphaSize; v++)
314			if (v >= gs && v <= ge)
315			s->len[nPart-1][v] = BZ_LESSER_ICOST;
316			else
317			s->len[nPart-1][v] = BZ_GREATER_ICOST;
318
319			nPart--;
320			gs = ge + 1;
321			remF -= aFreq;
322			}
323			}
324
325			/*
326			* Iterate up to BZ_N_ITERS times to improve the tables.
327			*/
328			for (iter = 0; iter < BZ_N_ITERS; iter++) {
329			for (t = 0; t < nGroups; t++)
330			fave[t] = 0;
331
332			for (t = 0; t < nGroups; t++)
333			for (v = 0; v < alphaSize; v++)
334			s->rfreq[t][v] = 0;
335
336			#if CONFIG_BZIP2_FEATURE_SPEED >= 5
337			/*
338			* Set up an auxiliary length table which is used to fast-track
339			* the common case (nGroups == 6).
340			*/
341			if (nGroups == 6) {
342			for (v = 0; v < alphaSize; v++) {
343			s->len_pack[v][0] = (s->len[1][v] << 16) \| s->len[0][v];
344			s->len_pack[v][1] = (s->len[3][v] << 16) \| s->len[2][v];
345			s->len_pack[v][2] = (s->len[5][v] << 16) \| s->len[4][v];
346			}
347			}
348			#endif
349			nSelectors = 0;
350			totc = 0;
351			gs = 0;
352			while (1) {
353			/--- Set group start & end marks. --/
354			if (gs >= s->nMTF)
355			break;
356			ge = gs + BZ_G_SIZE - 1;
357			if (ge >= s->nMTF)
358			ge = s->nMTF-1;
359
360			/*
361			* Calculate the cost of this group as coded
362			* by each of the coding tables.
363			*/
364			for (t = 0; t < nGroups; t++)
365			cost[t] = 0;
366			#if CONFIG_BZIP2_FEATURE_SPEED >= 5
367			if (nGroups == 6 && 50 == ge-gs+1) {
368			/--- fast track the common case ---/
369			register uint32_t cost01, cost23, cost45;
370			register uint16_t icv;
371			cost01 = cost23 = cost45 = 0;
372			#define BZ_ITER(nn) \
373			icv = mtfv[gs+(nn)]; \
374			cost01 += s->len_pack[icv][0]; \
375			cost23 += s->len_pack[icv][1]; \
376			cost45 += s->len_pack[icv][2];
377			BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4);
378			BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9);
379			BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
380			BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
381			BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
382			BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
383			BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
384			BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
385			BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
386			BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
387			#undef BZ_ITER
388			cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
389			cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
390			cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
391
392			} else
393			#endif
394			{
395			/--- slow version which correctly handles all situations ---/
396			for (i = gs; i <= ge; i++) {
397			uint16_t icv = mtfv[i];
398			for (t = 0; t < nGroups; t++)
399			cost[t] += s->len[t][icv];
400			}
401			}
402			/*
403			* Find the coding table which is best for this group,
404			* and record its identity in the selector table.
405			*/
406			/bc = 999999999;/
407			/bt = -1;/
408			bc = cost[0];
409			bt = 0;
410			for (t = 1 /0/; t < nGroups; t++) {
411			if (cost[t] < bc) {
412			bc = cost[t];
413			bt = t;
414			}
415			}
416			totc += bc;
417			fave[bt]++;
418			s->selector[nSelectors] = bt;
419			nSelectors++;
420
421			/*
422			* Increment the symbol frequencies for the selected table.
423			*/
424			/* 1% faster compress. +800 bytes */
425			#if CONFIG_BZIP2_FEATURE_SPEED >= 4
426			if (nGroups == 6 && 50 == ge-gs+1) {
427			/--- fast track the common case ---/
428			#define BZ_ITUR(nn) s->rfreq[bt][mtfv[gs + (nn)]]++
429			BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4);
430			BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9);
431			BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
432			BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
433			BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
434			BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
435			BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
436			BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
437			BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
438			BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
439			#undef BZ_ITUR
440			gs = ge + 1;
441			} else
442			#endif
443			{
444			/--- slow version which correctly handles all situations ---/
445			while (gs <= ge) {
446			s->rfreq[bt][mtfv[gs]]++;
447			gs++;
448			}
449			/* already is: gs = ge + 1; */
450			}
451			}
452
453			/*
454			* Recompute the tables based on the accumulated frequencies.
455			*/
456			/* maxLen was changed from 20 to 17 in bzip2-1.0.3. See
457			* comment in huffman.c for details. */
458			for (t = 0; t < nGroups; t++)
459			BZ2_hbMakeCodeLengths(s, &(s->len[t][0]), &(s->rfreq[t][0]), alphaSize, 17 /20/);
460			}
461
462			AssertH(nGroups < 8, 3002);
463			AssertH(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZ_G_SIZE)), 3003);
464
465			/--- Compute MTF values for the selectors. ---/
466			{
467			uint8_t pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
468
469			for (i = 0; i < nGroups; i++)
470			pos[i] = i;
471			for (i = 0; i < nSelectors; i++) {
472			ll_i = s->selector[i];
473			j = 0;
474			tmp = pos[j];
475			while (ll_i != tmp) {
476			j++;
477			tmp2 = tmp;
478			tmp = pos[j];
479			pos[j] = tmp2;
480			};
481			pos[0] = tmp;
482			s->selectorMtf[i] = j;
483			}
484			};
485
486			/--- Assign actual codes for the tables. --/
487			for (t = 0; t < nGroups; t++) {
488			minLen = 32;
489			maxLen = 0;
490			for (i = 0; i < alphaSize; i++) {
491			if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
492			if (s->len[t][i] < minLen) minLen = s->len[t][i];
493			}
494			AssertH(!(maxLen > 17 /20/), 3004);
495			AssertH(!(minLen < 1), 3005);
496			BZ2_hbAssignCodes(&(s->code[t][0]), &(s->len[t][0]), minLen, maxLen, alphaSize);
497			}
498
499			/--- Transmit the mapping table. ---/
500			{
501			/* bbox: optimized a bit more than in bzip2 */
502			int inUse16 = 0;
503			for (i = 0; i < 16; i++) {
504			if (sizeof(long) <= 4) {
505			inUse16 = inUse16*2 +
506			(((uint32_t)&(s->inUse[i * 16 + 0])
507			\| (uint32_t)&(s->inUse[i * 16 + 4])
508			\| (uint32_t)&(s->inUse[i * 16 + 8])
509			\| (uint32_t)&(s->inUse[i * 16 + 12])) != 0);
510			} else { /* Our CPU can do better */
511			inUse16 = inUse16*2 +
512			(((uint64_t)&(s->inUse[i * 16 + 0])
513			\| (uint64_t)&(s->inUse[i * 16 + 8])) != 0);
514			}
515			}
516
517			nBytes = s->numZ;
518			bsW(s, 16, inUse16);
519
520			inUse16 <<= (sizeof(int)8 - 16); / move 15th bit into sign bit */
521			for (i = 0; i < 16; i++) {
522			if (inUse16 < 0) {
523			unsigned v16 = 0;
524			for (j = 0; j < 16; j++)
525			v16 = v162 + s->inUse[i 16 + j];
526			bsW(s, 16, v16);
527			}
528			inUse16 <<= 1;
529			}
530			}
531
532			/--- Now the selectors. ---/
533			nBytes = s->numZ;
534			bsW(s, 3, nGroups);
535			bsW(s, 15, nSelectors);
536			for (i = 0; i < nSelectors; i++) {
537			for (j = 0; j < s->selectorMtf[i]; j++)
538			bsW(s, 1, 1);
539			bsW(s, 1, 0);
540			}
541
542			/--- Now the coding tables. ---/
543			nBytes = s->numZ;
544
545			for (t = 0; t < nGroups; t++) {
546			int32_t curr = s->len[t][0];
547			bsW(s, 5, curr);
548			for (i = 0; i < alphaSize; i++) {
549			while (curr < s->len[t][i]) { bsW(s, 2, 2); curr++; /* 10 */ };
550			while (curr > s->len[t][i]) { bsW(s, 2, 3); curr--; /* 11 */ };
551			bsW(s, 1, 0);
552			}
553			}
554
555			/--- And finally, the block data proper ---/
556			nBytes = s->numZ;
557			selCtr = 0;
558			gs = 0;
559			while (1) {
560			if (gs >= s->nMTF)
561			break;
562			ge = gs + BZ_G_SIZE - 1;
563			if (ge >= s->nMTF)
564			ge = s->nMTF-1;
565			AssertH(s->selector[selCtr] < nGroups, 3006);
566
567			/* Costs 1300 bytes and is _slower_ (on Intel Core 2) */
568			#if 0
569			if (nGroups == 6 && 50 == ge-gs+1) {
570			/--- fast track the common case ---/
571			uint16_t mtfv_i;
572			uint8_t* s_len_sel_selCtr = &(s->len[s->selector[selCtr]][0]);
573			int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
574			#define BZ_ITAH(nn) \
575			mtfv_i = mtfv[gs+(nn)]; \
576			bsW(s, s_len_sel_selCtr[mtfv_i], s_code_sel_selCtr[mtfv_i])
577			BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4);
578			BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9);
579			BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
580			BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
581			BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
582			BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
583			BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
584			BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
585			BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
586			BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
587			#undef BZ_ITAH
588			gs = ge+1;
589			} else
590			#endif
591			{
592			/--- slow version which correctly handles all situations ---/
593			/* code is bit bigger, but moves multiply out of the loop */
594			uint8_t* s_len_sel_selCtr = &(s->len [s->selector[selCtr]][0]);
595			int32_t* s_code_sel_selCtr = &(s->code[s->selector[selCtr]][0]);
596			while (gs <= ge) {
597			bsW(s,
598			s_len_sel_selCtr[mtfv[gs]],
599			s_code_sel_selCtr[mtfv[gs]]
600			);
601			gs++;
602			}
603			/* already is: gs = ge+1; */
604			}
605			selCtr++;
606			}
607			AssertH(selCtr == nSelectors, 3007);
608			#undef code
609			#undef rfreq
610			#undef len_pack
611			}
612
613
614			/---------------------------------------------------/
615			static
616			void BZ2_compressBlock(EState* s, int is_last_block)
617			{
618			if (s->nblock > 0) {
619			BZ_FINALISE_CRC(s->blockCRC);
620			s->combinedCRC = (s->combinedCRC << 1) \| (s->combinedCRC >> 31);
621			s->combinedCRC ^= s->blockCRC;
622			if (s->blockNo > 1)
623			s->numZ = 0;
624
625			BZ2_blockSort(s);
626			}
627
628			s->zbits = &((uint8_t*)s->arr2)[s->nblock];
629
630			/-- If this is the first block, create the stream header. --/
631			if (s->blockNo == 1) {
632			BZ2_bsInitWrite(s);
633			/bsPutU8(s, BZ_HDR_B);/
634			/bsPutU8(s, BZ_HDR_Z);/
635			/bsPutU8(s, BZ_HDR_h);/
636			/bsPutU8(s, BZ_HDR_0 + s->blockSize100k);/
637			bsPutU32(s, BZ_HDR_BZh0 + s->blockSize100k);
638			}
639
640			if (s->nblock > 0) {
641			/bsPutU8(s, 0x31);/
642			/bsPutU8(s, 0x41);/
643			/bsPutU8(s, 0x59);/
644			/bsPutU8(s, 0x26);/
645			bsPutU32(s, 0x31415926);
646			/bsPutU8(s, 0x53);/
647			/bsPutU8(s, 0x59);/
648			bsPutU16(s, 0x5359);
649
650			/-- Now the block's CRC, so it is in a known place. --/
651			bsPutU32(s, s->blockCRC);
652
653			/*
654			* Now a single bit indicating (non-)randomisation.
655			* As of version 0.9.5, we use a better sorting algorithm
656			* which makes randomisation unnecessary. So always set
657			* the randomised bit to 'no'. Of course, the decoder
658			* still needs to be able to handle randomised blocks
659			* so as to maintain backwards compatibility with
660			* older versions of bzip2.
661			*/
662			bsW(s, 1, 0);
663
664			bsW(s, 24, s->origPtr);
665			generateMTFValues(s);
666			sendMTFValues(s);
667			}
668
669			/-- If this is the last block, add the stream trailer. --/
670			if (is_last_block) {
671			/bsPutU8(s, 0x17);/
672			/bsPutU8(s, 0x72);/
673			/bsPutU8(s, 0x45);/
674			/bsPutU8(s, 0x38);/
675			bsPutU32(s, 0x17724538);
676			/bsPutU8(s, 0x50);/
677			/bsPutU8(s, 0x90);/
678			bsPutU16(s, 0x5090);
679			bsPutU32(s, s->combinedCRC);
680			bsFinishWrite(s);
681			}
682			}
683
684
685			/-------------------------------------------------------------/
686			/--- end compress.c ---/
687			/-------------------------------------------------------------/