mbtransquant.c

这是一个压缩解压包,用C语言进行编程的,里面有详细的源代码.

				dQ2 = dQ1 + Mult;
				Level2 = Level1 + 1;
				Tbl_L1		= (Level1>=-24) ? B16_17_Code_Len[Level1^-1]	  : Code_Len0;
				Tbl_L2		= (Level2>=-24) ? B16_17_Code_Len[Level2^-1]	  : Code_Len0;
				Tbl_L1_Last = (Level1>=- 6) ? B16_17_Code_Len_Last[Level1^-1] : Code_Len0;
				Tbl_L2_Last = (Level2>=- 6) ? B16_17_Code_Len_Last[Level2^-1] : Code_Len0;
			}

			Dist1 = Lambda*dQ1*dQ1;
			Dist2 = Lambda*dQ2*dQ2;
			dDist21 = Dist2-Dist1;

			for(Run=i-Run_Start; Run>0; --Run)
			{
				const uint32_t Cost_Base = Dist1 + Run_Costs[i-Run];
				uint32_t Cost1, Cost2;
				int bLevel;

				/* for sub-optimal (but slightly worth it, speed-wise) search,
				 * uncomment the following:
				 *		if (Cost_Base>=Best_Cost) continue;
				 * (? doesn't seem to have any effect -- gruel ) */

				Cost1 = Cost_Base + (Tbl_L1[Run-1]<<TL_SHIFT);
				Cost2 = Cost_Base + (Tbl_L2[Run-1]<<TL_SHIFT) + dDist21;

				if (Cost2<Cost1) {
					Cost1 = Cost2;
					bLevel = Level2;
				} else {
					bLevel = Level1;
				}

				if (Cost1<Best_Cost) {
					Best_Cost = Cost1;
					Nodes[i].Run   = Run;
					Nodes[i].Level = bLevel;
				}

				Cost1 = Cost_Base + (Tbl_L1_Last[Run-1]<<TL_SHIFT);
				Cost2 = Cost_Base + (Tbl_L2_Last[Run-1]<<TL_SHIFT) + dDist21;

				if (Cost2<Cost1) {
					Cost1 = Cost2;
					bLevel = Level2;
				} else {
					bLevel = Level1;
				}

				if (Cost1<Last_Cost) {
					Last_Cost  = Cost1;
					Last.Run   = Run;
					Last.Level = bLevel;
					Last_Node  = i;
				}
			} /* end of "for Run" */
		} else {
			/* Very very high levels, with no chance of being optimizable
			 * => Simply pick best Run. */
			int Run;
			for(Run=i-Run_Start; Run>0; --Run) {  
				/* 30 bits + no distortion */
				const uint32_t Cost = (30<<TL_SHIFT) + Run_Costs[i-Run];
				if (Cost<Best_Cost) {
					Best_Cost = Cost;
					Nodes[i].Run   = Run;
					Nodes[i].Level = Level1;
				}

				if (Cost<Last_Cost) {
					Last_Cost  = Cost;
					Last.Run   = Run;
					Last.Level = Level1;
					Last_Node  = i;	 
				}
			}
		}


		Run_Costs[i] = Best_Cost;

		if (Best_Cost < Min_Cost + Dist0) {
			Min_Cost = Best_Cost;
			Run_Start = i;
		} else {
			/* as noticed by Michael Niedermayer (michaelni at gmx.at),
			 * there's a code shorter by 1 bit for a larger run (!), same
			 * level. We give it a chance by not moving the left barrier too
			 * much. */
			while( Run_Costs[Run_Start]>Min_Cost+(1<<TL_SHIFT) )
				Run_Start++;

			/* spread on preceding coeffs the cost incurred by skipping this
			 * one */
			for(j=Run_Start; j<i; ++j) Run_Costs[j] += Dist0;
			Min_Cost += Dist0;
		}
	}

	/* It seems trellis doesn't give good results... just leave the block untouched
	 * and return the original sum value */
	if (Last_Node<0)
		return Sum;

	/* reconstruct optimal sequence backward with surviving paths */
	memset(Out, 0x00, 64*sizeof(*Out));
	Out[Zigzag[Last_Node]] = Last.Level;
	i = Last_Node - Last.Run;
	Sum = abs(Last.Level);
	while(i>=0) {
		Out[Zigzag[i]] = Nodes[i].Level;
		Sum += abs(Nodes[i].Level);
		i -= Nodes[i].Run;
	}

	return Sum;
}

/* original version including heavy debugging info */

#ifdef DBGTRELL

#define DBG 0

static __inline uint32_t Evaluate_Cost(const int16_t *C, int Mult, int Bias,
									   const uint16_t * Zigzag, int Max, int Lambda)
{
#if (DBG>0)
	const int16_t * const Ref = C + 6*64;
	int Last = Max;
	int Bits = 0;
	int Dist = 0;
	int i;
	uint32_t Cost;

	while(Last>=0 && C[Zigzag[Last]]==0)
		Last--;

	if (Last>=0) {
		int j=0, j0=0;
		int Run, Level;

		Bits = 2;   /* CBP */
		while(j<Last) {
			while(!C[Zigzag[j]])
				j++;
			if (j==Last)
				break;
			Level=C[Zigzag[j]];
			Run = j - j0;
			j0 = ++j;
			if (Level>=-24 && Level<=24)
				Bits += B16_17_Code_Len[(Level<0) ? -Level-1 : Level-1][Run];
			else
				Bits += 30;
		}
		Level = C[Zigzag[Last]];
		Run = j - j0;
		if (Level>=-6 && Level<=6)
			Bits += B16_17_Code_Len_Last[(Level<0) ? -Level-1 : Level-1][Run];
		else
			Bits += 30;
	}

	for(i=0; i<=Last; ++i) {
		int V = C[Zigzag[i]]*Mult;
		if (V>0)
			V += Bias;
		else
			if (V<0)
				V -= Bias;
		V -= Ref[Zigzag[i]];
		Dist += V*V;
	}
	Cost = Lambda*Dist + (Bits<<TL_SHIFT);
	if (DBG==1)
		printf( " Last:%2d/%2d Cost = [(Bits=%5.0d) + Lambda*(Dist=%6.0d) = %d ] >>12= %d ", Last,Max, Bits, Dist, Cost, Cost>>12 );
	return Cost;

#else
	return 0;
#endif
}


static int
dct_quantize_trellis_h263_c(int16_t *const Out, const int16_t *const In, int Q, const uint16_t * const Zigzag, int Non_Zero)
{

    /*
	 * Note: We should search last non-zero coeffs on *real* DCT input coeffs (In[]),
	 * not quantized one (Out[]). However, it only improves the result *very*
	 * slightly (~0.01dB), whereas speed drops to crawling level :)
	 * Well, actually, taking 1 more coeff past Non_Zero into account sometimes helps.
	 */
	typedef struct { int16_t Run, Level; } NODE;

	NODE Nodes[65], Last;
	uint32_t Run_Costs0[64+1];
	uint32_t * const Run_Costs = Run_Costs0 + 1;
	const int Mult = 2*Q;
	const int Bias = (Q-1) | 1;
	const int Lev0 = Mult + Bias;
	const int Lambda = Trellis_Lambda_Tabs[Q-1];    /* it's 1/lambda, actually */

	int Run_Start = -1;
	Run_Costs[-1] = 2<<TL_SHIFT;                          /* source (w/ CBP penalty) */
	uint32_t Min_Cost = 2<<TL_SHIFT;

	int Last_Node = -1;
	uint32_t Last_Cost = 0;

	int i, j;

#if (DBG>0)
	Last.Level = 0; Last.Run = -1; /* just initialize to smthg */
#endif

	Non_Zero = Find_Last(Out, Zigzag, Non_Zero);
	if (Non_Zero<0)
		return -1;

	for(i=0; i<=Non_Zero; i++)
	{
		const int AC = In[Zigzag[i]];
		const int Level1 = Out[Zigzag[i]];
		const int Dist0 = Lambda* AC*AC;
		uint32_t Best_Cost = 0xf0000000;
		Last_Cost += Dist0;

		if ((uint32_t)(Level1+1)<3)                 /* very specialized loop for -1,0,+1 */
		{
			int dQ;
			int Run;
			uint32_t Cost0;

			if (AC<0) {
				Nodes[i].Level = -1;
				dQ = Lev0 + AC;
			} else {
				Nodes[i].Level = 1;
				dQ = Lev0 - AC;
			}
			Cost0 = Lambda*dQ*dQ;

			Nodes[i].Run = 1;
			Best_Cost = (Code_Len20[0]<<TL_SHIFT) + Run_Costs[i-1]+Cost0;
			for(Run=i-Run_Start; Run>0; --Run)
			{
				const uint32_t Cost_Base = Cost0 + Run_Costs[i-Run];
				const uint32_t Cost = Cost_Base + (Code_Len20[Run-1]<<TL_SHIFT);
				const uint32_t lCost = Cost_Base + (Code_Len24[Run-1]<<TL_SHIFT);

				/*
				 * TODO: what about tie-breaks? Should we favor short runs or
				 * long runs? Although the error is the same, it would not be
				 * spread the same way along high and low frequencies...
				 */
				if (Cost<Best_Cost) {
					Best_Cost    = Cost;
					Nodes[i].Run = Run;
				}

				if (lCost<Last_Cost) {
					Last_Cost  = lCost;
					Last.Run   = Run;
					Last_Node  = i;
				}
			}
			if (Last_Node==i)
				Last.Level = Nodes[i].Level;

			if (DBG==1) {
				Run_Costs[i] = Best_Cost;
				printf( "Costs #%2d: ", i);
				for(j=-1;j<=Non_Zero;++j) {
					if (j==Run_Start)            printf( " %3.0d|", Run_Costs[j]>>12 );
					else if (j>Run_Start && j<i) printf( " %3.0d|", Run_Costs[j]>>12 );
					else if (j==i)               printf( "(%3.0d)", Run_Costs[j]>>12 );
					else                         printf( "  - |" );
				}
				printf( "<%3.0d %2d %d>", Min_Cost>>12, Nodes[i].Level, Nodes[i].Run );
				printf( "  Last:#%2d {%3.0d %2d %d}", Last_Node, Last_Cost>>12, Last.Level, Last.Run );
				printf( " AC:%3.0d Dist0:%3d Dist(%d)=%d", AC, Dist0>>12, Nodes[i].Level, Cost0>>12 );
				printf( "\n" );
			}
		}
		else                      /* "big" levels */
		{
			const uint8_t *Tbl_L1, *Tbl_L2, *Tbl_L1_Last, *Tbl_L2_Last;
			int Level2;
			int dQ1, dQ2;
			int Run;
			uint32_t Dist1,Dist2;
			int dDist21;

			if (Level1>1) {
				dQ1 = Level1*Mult-AC + Bias;
				dQ2 = dQ1 - Mult;
				Level2 = Level1-1;
				Tbl_L1      = (Level1<=24) ? B16_17_Code_Len[Level1-1]     : Code_Len0;
				Tbl_L2      = (Level2<=24) ? B16_17_Code_Len[Level2-1]     : Code_Len0;
				Tbl_L1_Last = (Level1<=6) ? B16_17_Code_Len_Last[Level1-1] : Code_Len0;
				Tbl_L2_Last = (Level2<=6) ? B16_17_Code_Len_Last[Level2-1] : Code_Len0;
			} else { /* Level1<-1 */
				dQ1 = Level1*Mult-AC - Bias;
				dQ2 = dQ1 + Mult;
				Level2 = Level1 + 1;
				Tbl_L1      = (Level1>=-24) ? B16_17_Code_Len[Level1^-1]      : Code_Len0;
				Tbl_L2      = (Level2>=-24) ? B16_17_Code_Len[Level2^-1]      : Code_Len0;
				Tbl_L1_Last = (Level1>=- 6) ? B16_17_Code_Len_Last[Level1^-1] : Code_Len0;
				Tbl_L2_Last = (Level2>=- 6) ? B16_17_Code_Len_Last[Level2^-1] : Code_Len0;
			}
			Dist1 = Lambda*dQ1*dQ1;
			Dist2 = Lambda*dQ2*dQ2;
			dDist21 = Dist2-Dist1;

			for(Run=i-Run_Start; Run>0; --Run)
			{
				const uint32_t Cost_Base = Dist1 + Run_Costs[i-Run];
				uint32_t Cost1, Cost2;
				int bLevel;

/*
 * for sub-optimal (but slightly worth it, speed-wise) search, uncomment the following:
 *        if (Cost_Base>=Best_Cost) continue;
 */
				Cost1 = Cost_Base + (Tbl_L1[Run-1]<<TL_SHIFT);
				Cost2 = Cost_Base + (Tbl_L2[Run-1]<<TL_SHIFT) + dDist21;

				if (Cost2<Cost1) {
					Cost1 = Cost2;
					bLevel = Level2;
				} else
					bLevel = Level1;

				if (Cost1<Best_Cost) {
					Best_Cost = Cost1;
					Nodes[i].Run   = Run;
					Nodes[i].Level = bLevel;
				}

				Cost1 = Cost_Base + (Tbl_L1_Last[Run-1]<<TL_SHIFT);
				Cost2 = Cost_Base + (Tbl_L2_Last[Run-1]<<TL_SHIFT) + dDist21;

				if (Cost2<Cost1) {
					Cost1 = Cost2;
					bLevel = Level2;
				} else
					bLevel = Level1;

				if (Cost1<Last_Cost) {
					Last_Cost  = Cost1;
					Last.Run   = Run;
					Last.Level = bLevel;
					Last_Node  = i;
				}
			} /* end of "for Run" */

			if (DBG==1) {
				Run_Costs[i] = Best_Cost;
				printf( "Costs #%2d: ", i);
				for(j=-1;j<=Non_Zero;++j) {
					if (j==Run_Start)            printf( " %3.0d|", Run_Costs[j]>>12 );
					else if (j>Run_Start && j<i) printf( " %3.0d|", Run_Costs[j]>>12 );
					else if (j==i)               printf( "(%3.0d)", Run_Costs[j]>>12 );
					else                         printf( "  - |" );
				}
				printf( "<%3.0d %2d %d>", Min_Cost>>12, Nodes[i].Level, Nodes[i].Run );
				printf( "  Last:#%2d {%3.0d %2d %d}", Last_Node, Last_Cost>>12, Last.Level, Last.Run );
				printf( " AC:%3.0d Dist0:%3d Dist(%2d):%3d Dist(%2d):%3d", AC, Dist0>>12, Level1, Dist1>>12, Level2, Dist2>>12 );
				printf( "\n" );
			}
		}

		Run_Costs[i] = Best_Cost;

		if (Best_Cost < Min_Cost + Dist0) {
			Min_Cost = Best_Cost;
			Run_Start = i;
		}
		else
		{
			/*
			 * as noticed by Michael Niedermayer (michaelni at gmx.at), there's
			 * a code shorter by 1 bit for a larger run (!), same level. We give
			 * it a chance by not moving the left barrier too much.
			 */

			while( Run_Costs[Run_Start]>Min_Cost+(1<<TL_SHIFT) )
				Run_Start++;

			/* spread on preceding coeffs the cost incurred by skipping this one */
			for(j=Run_Start; j<i; ++j) Run_Costs[j] += Dist0;
			Min_Cost += Dist0;
		}
	}

	if (DBG) {
		Last_Cost = Evaluate_Cost(Out,Mult,Bias, Zigzag,Non_Zero, Lambda);
		if (DBG==1) {
			printf( "=> " );
			for(i=0; i<=Non_Zero; ++i) printf( "[%3.0d] ", Out[Zigzag[i]] );
			printf( "\n" );
		}
	}

	if (Last_Node<0)
		return -1;

	/* reconstruct optimal sequence backward with surviving paths */
	memset(Out, 0x00, 64*sizeof(*Out));
	Out[Zigzag[Last_Node]] = Last.Level;
	i = Last_Node - Last.Run;
	while(i>=0) {
		Out[Zigzag[i]] = Nodes[i].Level;
		i -= Nodes[i].Run;
	}

	if (DBG) {
		uint32_t Cost = Evaluate_Cost(Out,Mult,Bias, Zigzag,Non_Zero, Lambda);
		if (DBG==1) {
			printf( "<= " );
			for(i=0; i<=Last_Node; ++i) printf( "[%3.0d] ", Out[Zigzag[i]] );
			printf( "\n--------------------------------\n" );
		}
		if (Cost>Last_Cost) printf( "!!! %u > %u\n", Cost, Last_Cost );
	}
	return Last_Node;
}

#undef DBG

#endif