--- branches/dev-api-4/xvidcore/src/utils/mbtransquant.c 2003/05/09 22:03:13 1011 +++ branches/dev-api-4/xvidcore/src/utils/mbtransquant.c 2003/07/24 13:09:27 1095 @@ -21,12 +21,13 @@ * along with this program ; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * - * $Id: mbtransquant.c,v 1.21.2.10 2003-05-09 22:03:13 chl Exp $ + * $Id: mbtransquant.c,v 1.21.2.15 2003-07-24 13:09:14 Isibaar Exp $ * ****************************************************************************/ -#include +#include #include +#include #include "../portab.h" #include "mbfunctions.h" @@ -161,11 +162,20 @@ 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); +dct_quantize_trellis_h263_c(int16_t *const Out, + const int16_t *const In, + int Q, + const uint16_t * const Zigzag, + int Non_Zero); +#if 0 static int -dct_quantize_trellis_mpeg_c(int16_t *const Out, const int16_t *const In, int Q, const uint16_t * const Zigzag, int Non_Zero); - +dct_quantize_trellis_mpeg_c(int16_t *const Out, + const int16_t *const In, + int Q, + const uint16_t * const Zigzag, + int Non_Zero); +#endif /* Quantize all blocks -- Inter mode */ static __inline uint8_t @@ -191,12 +201,14 @@ sum = quant_inter(&qcoeff[i*64], &data[i*64], pMB->quant); if ( (sum) && (frame->vop_flags & XVID_VOP_TRELLISQUANT) ) { sum = dct_quantize_trellis_h263_c(&qcoeff[i*64], &data[i*64], pMB->quant, &scan_tables[0][0], 63)+1; - limit = 1; +/* limit = 1; // Isibaar: why? deactivated so far - so please complain! ;-) */ } } else { sum = quant4_inter(&qcoeff[i * 64], &data[i * 64], pMB->quant); -// if ( (sum) && (frame->vop_flags & XVID_VOP_TRELLISQUANT) ) -// sum = dct_quantize_trellis_mpeg_c (&qcoeff[i*64], &data[i*64], pMB->quant)+1; +#if 0 + if ( (sum) && (frame->vop_flags & XVID_VOP_TRELLISQUANT) ) + sum = dct_quantize_trellis_mpeg_c (&qcoeff[i*64], &data[i*64], pMB->quant)+1; +#endif } stop_quant_timer(); @@ -429,6 +441,9 @@ /* Set the limit threshold */ limit = PVOP_TOOSMALL_LIMIT + ((pMB->quant == 1)? 1 : 0); + if (frame->vop_flags & XVID_VOP_CARTOON) + limit *= 3; + /* Quantize the block */ cbp = MBQuantInter(pParam, frame, pMB, data, qcoeff, 0, limit); @@ -467,6 +482,9 @@ /* Set the limit threshold */ limit = BVOP_TOOSMALL_LIMIT; + if (frame->vop_flags & XVID_VOP_CARTOON) + limit *= 2; + /* Quantize the block */ cbp = MBQuantInter(pParam, frame, pMB, data, qcoeff, 1, limit); @@ -545,26 +563,26 @@ /* left blocks */ - // 1=2, 2=4, 4=8, 8=1 + /* 1=2, 2=4, 4=8, 8=1 */ MOVLINE(tmp, LINE(0, 1)); MOVLINE(LINE(0, 1), LINE(0, 2)); MOVLINE(LINE(0, 2), LINE(0, 4)); MOVLINE(LINE(0, 4), LINE(2, 0)); MOVLINE(LINE(2, 0), tmp); - // 3=6, 6=12, 12=9, 9=3 + /* 3=6, 6=12, 12=9, 9=3 */ MOVLINE(tmp, LINE(0, 3)); MOVLINE(LINE(0, 3), LINE(0, 6)); MOVLINE(LINE(0, 6), LINE(2, 4)); MOVLINE(LINE(2, 4), LINE(2, 1)); MOVLINE(LINE(2, 1), tmp); - // 5=10, 10=5 + /* 5=10, 10=5 */ MOVLINE(tmp, LINE(0, 5)); MOVLINE(LINE(0, 5), LINE(2, 2)); MOVLINE(LINE(2, 2), tmp); - // 7=14, 14=13, 13=11, 11=7 + /* 7=14, 14=13, 13=11, 11=7 */ MOVLINE(tmp, LINE(0, 7)); MOVLINE(LINE(0, 7), LINE(2, 6)); MOVLINE(LINE(2, 6), LINE(2, 5)); @@ -573,26 +591,26 @@ /* right blocks */ - // 1=2, 2=4, 4=8, 8=1 + /* 1=2, 2=4, 4=8, 8=1 */ MOVLINE(tmp, LINE(1, 1)); MOVLINE(LINE(1, 1), LINE(1, 2)); MOVLINE(LINE(1, 2), LINE(1, 4)); MOVLINE(LINE(1, 4), LINE(3, 0)); MOVLINE(LINE(3, 0), tmp); - // 3=6, 6=12, 12=9, 9=3 + /* 3=6, 6=12, 12=9, 9=3 */ MOVLINE(tmp, LINE(1, 3)); MOVLINE(LINE(1, 3), LINE(1, 6)); MOVLINE(LINE(1, 6), LINE(3, 4)); MOVLINE(LINE(3, 4), LINE(3, 1)); MOVLINE(LINE(3, 1), tmp); - // 5=10, 10=5 + /* 5=10, 10=5 */ MOVLINE(tmp, LINE(1, 5)); MOVLINE(LINE(1, 5), LINE(3, 2)); MOVLINE(LINE(3, 2), tmp); - // 7=14, 14=13, 13=11, 11=7 + /* 7=14, 14=13, 13=11, 11=7 */ MOVLINE(tmp, LINE(1, 7)); MOVLINE(LINE(1, 7), LINE(3, 6)); MOVLINE(LINE(3, 6), LINE(3, 5)); @@ -604,43 +622,49 @@ -/************************************************************************ - * Trellis based R-D optimal quantization * - * * - * Trellis Quant code (C) 2003 Pascal Massimino skal(at)planet-d.net * - * * - ************************************************************************/ - - -static int -dct_quantize_trellis_inter_mpeg_c (int16_t *qcoeff, const int16_t *data, int quant) -{ return 63; } - - -////////////////////////////////////////////////////////// -// -// Trellis-Based quantization -// -// So far I understand this paper: -// -// "Trellis-Based R-D Optimal Quantization in H.263+" -// J.Wen, M.Luttrell, J.Villasenor -// IEEE Transactions on Image Processing, Vol.9, No.8, Aug. 2000. -// -// we are at stake with a simplified Bellmand-Ford / Dijkstra Single -// Source Shorted Path algo. But due to the underlying graph structure -// ("Trellis"), it can be turned into a dynamic programming algo, -// partially saving the explicit graph's nodes representation. And -// without using a heap, since the open frontier of the DAG is always -// known, and of fixed sized. -// -////////////////////////////////////////////////////////// +/***************************************************************************** + * Trellis based R-D optimal quantization + * + * Trellis Quant code (C) 2003 Pascal Massimino skal(at)planet-d.net + * + ****************************************************************************/ + + +#if 0 +static int +dct_quantize_trellis_mpeg_c(int16_t *const Out, + const int16_t *const In, + int Q, + const uint16_t * const Zigzag, + int Non_Zero) +{ + return 63; +} +#endif + +/*---------------------------------------------------------------------------- + * + * Trellis-Based quantization + * + * So far I understand this paper: + * + * "Trellis-Based R-D Optimal Quantization in H.263+" + * J.Wen, M.Luttrell, J.Villasenor + * IEEE Transactions on Image Processing, Vol.9, No.8, Aug. 2000. + * + * we are at stake with a simplified Bellmand-Ford / Dijkstra Single + * Source Shorted Path algo. But due to the underlying graph structure + * ("Trellis"), it can be turned into a dynamic programming algo, + * partially saving the explicit graph's nodes representation. And + * without using a heap, since the open frontier of the DAG is always + * known, and of fixed sized. + *--------------------------------------------------------------------------*/ + -////////////////////////////////////////////////////////// -// Codes lengths for relevant levels. +/* Codes lengths for relevant levels. */ - // let's factorize: + /* let's factorize: */ static const uint8_t Code_Len0[64] = { 30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, 30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; @@ -705,7 +729,7 @@ 3, 4, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9,10,10,10,10,10,10,10,10,12,12,13,13,12,13,14,15,15, 15,16,16,16,16,17,17,17,18,18,19,19,19,19,19,19,19,19,21,21,22,22,30,30,30,30,30,30,30,30,30,30 }; - // a few more table for LAST table: + /* a few more table for LAST table: */ static const uint8_t Code_Len21[64] = { 13,20,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, 30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30}; @@ -720,7 +744,7 @@ 12,13,13,13,13,13,13,13,13,14,16,16,16,16,17,17,17,17,18,18,18,18,18,18,18,18,19,19,19,19,19,19}; -static const uint8_t * const B16_17_Code_Len[24] = { // levels [1..24] +static const uint8_t * const B16_17_Code_Len[24] = { /* levels [1..24] */ Code_Len20,Code_Len19,Code_Len18,Code_Len17, Code_Len16,Code_Len15,Code_Len14,Code_Len13, Code_Len12,Code_Len11,Code_Len10,Code_Len9, @@ -729,7 +753,7 @@ Code_Len2, Code_Len1, Code_Len1, Code_Len1, }; -static const uint8_t * const B16_17_Code_Len_Last[6] = { // levels [1..6] +static const uint8_t * const B16_17_Code_Len_Last[6] = { /* levels [1..6] */ Code_Len24,Code_Len23,Code_Len22,Code_Len21, Code_Len3, Code_Len1, }; @@ -743,7 +767,7 @@ }; #undef TL -static inline int Find_Last(const int16_t *C, const uint16_t *Zigzag, int i) +static __inline int Find_Last(const int16_t *C, const uint16_t *Zigzag, int i) { while(i>=0) if (C[Zigzag[i]]) @@ -752,47 +776,274 @@ return -1; } -////////////////////////////////////////////////////////// +/* this routine has been strippen of all debug code */ + +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; + uint32_t Min_Cost = 2<<16; + + int Last_Node = -1; + uint32_t Last_Cost = 0; + + int i, j; + Run_Costs[-1] = 2<<16; /* source (w/ CBP penalty) */ + + 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]<<16) + 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]<<16); + const uint32_t lCost = Cost_Base + (Code_Len24[Run-1]<<16); + + /* + * 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... + */ + + /* (I'd say: favour short runs => hifreq errors (HVS) -- gruel ) */ + + if (Cost1) { + 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; + * (? doesn't seem to have any effect -- gruel ) + */ + + Cost1 = Cost_Base + (Tbl_L1[Run-1]<<16); + Cost2 = Cost_Base + (Tbl_L2[Run-1]<<16) + dDist21; + + if (Cost2Min_Cost+(1<<16) ) + Run_Start++; + + /* spread on preceding coeffs the cost incurred by skipping this one */ + for(j=Run_Start; j=0) { + Out[Zigzag[i]] = Nodes[i].Level; + i -= Nodes[i].Run; + } + return Last_Node; +} + + + + + + + + + + + +/* original version including heavy debugging info */ + +#ifdef DBGTRELL #define DBG 0 -static uint32_t Evaluate_Cost(const int16_t *C, int Mult, int Bias, +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; - while(Last>=0 && C[Zigzag[Last]]==0) Last--; int Bits = 0; + int Dist = 0; + int i; + uint32_t Cost; + + while(Last>=0 && C[Zigzag[Last]]==0) + Last--; + if (Last>=0) { - Bits = 2; // CBP int j=0, j0=0; int Run, Level; + + Bits = 2; /* CBP */ while(j=-24 && Level<=24) Bits += B16_17_Code_Len[(Level<0) ? -Level-1 : Level-1][Run]; - else Bits += 30; + 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; + if (Level>=-6 && Level<=6) + Bits += B16_17_Code_Len_Last[(Level<0) ? -Level-1 : Level-1][Run]; + else + Bits += 30; } - int Dist = 0; - int i; for(i=0; i<=Last; ++i) { int V = C[Zigzag[i]]*Mult; - if (V>0) V += Bias; - else if (V<0) V -= Bias; + if (V>0) + V += Bias; + else + if (V<0) + V -= Bias; V -= Ref[Zigzag[i]]; Dist += V*V; } - uint32_t Cost = Lambda*Dist + (Bits<<16); + Cost = Lambda*Dist + (Bits<<16); 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; @@ -807,34 +1058,35 @@ 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, - + /* + * 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], * const Run_Costs = Run_Costs0 + 1; - + 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 + const int Lambda = Trellis_Lambda_Tabs[Q-1]; /* it's 1/lambda, actually */ int Run_Start = -1; - Run_Costs[-1] = 2<<16; // source (w/ CBP penalty) + Run_Costs[-1] = 2<<16; /* source (w/ CBP penalty) */ uint32_t Min_Cost = 2<<16; 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 + Last.Level = 0; Last.Run = -1; /* just initialize to smthg */ #endif - int i, j; - Non_Zero = Find_Last(Out, Zigzag, Non_Zero); if (Non_Zero<0) return -1; @@ -847,10 +1099,11 @@ uint32_t Best_Cost = 0xf0000000; Last_Cost += Dist0; - if ((uint32_t)(Level1+1)<3) // very specialized loop for -1,0,+1 + if ((uint32_t)(Level1+1)<3) /* very specialized loop for -1,0,+1 */ { - int dQ; - int Run; + int dQ; + int Run; + uint32_t Cost0; if (AC<0) { Nodes[i].Level = -1; @@ -859,32 +1112,34 @@ Nodes[i].Level = 1; dQ = Lev0 - AC; } - const uint32_t Cost0 = Lambda*dQ*dQ; - + Cost0 = Lambda*dQ*dQ; + Nodes[i].Run = 1; Best_Cost = (Code_Len20[0]<<16) + 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]<<16); - // 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 (Cost1) { dQ1 = Level1*Mult-AC + Bias; dQ2 = dQ1 - Mult; @@ -916,8 +1173,7 @@ 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 + } else { /* Level1<-1 */ dQ1 = Level1*Mult-AC - Bias; dQ2 = dQ1 + Mult; Level2 = Level1 + 1; @@ -926,28 +1182,30 @@ 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; } - const uint32_t Dist1 = Lambda*dQ1*dQ1; - const uint32_t Dist2 = Lambda*dQ2*dQ2; - const int dDist21 = Dist2-Dist1; + 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]; - -// for sub-optimal (but slightly worth it, speed-wise) search, uncomment the following: -// if (Cost_Base>=Best_Cost) continue; - 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]<<16); Cost2 = Cost_Base + (Tbl_L2[Run-1]<<16) + dDist21; - if (Cost2Min_Cost+(1<<16) ) Run_Start++; - // spread on preceding coeffs the cost incurred by skipping this one + /* spread on preceding coeffs the cost incurred by skipping this one */ for(j=Run_Start; j=0) { @@ -1037,3 +1301,5 @@ } #undef DBG + +#endif