[svn] / branches / dev-api-4 / xvidcore / src / utils / mbtransquant.c Repository:
ViewVC logotype

Diff of /branches/dev-api-4/xvidcore/src/utils/mbtransquant.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1011, Fri May 9 22:03:13 2003 UTC revision 1012, Sun May 11 13:26:14 2003 UTC
# Line 21  Line 21 
21   *  along with this program ; if not, write to the Free Software   *  along with this program ; if not, write to the Free Software
22   *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA   *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
23   *   *
24   * $Id: mbtransquant.c,v 1.21.2.10 2003-05-09 22:03:13 chl Exp $   * $Id: mbtransquant.c,v 1.21.2.11 2003-05-11 13:26:14 chl Exp $
25   *   *
26   ****************************************************************************/   ****************************************************************************/
27    
28  #include <string.h>  #include <stdio.h>
29  #include <stdlib.h>  #include <stdlib.h>
30    #include <string.h>
31    
32  #include "../portab.h"  #include "../portab.h"
33  #include "mbfunctions.h"  #include "mbfunctions.h"
# Line 613  Line 614 
614    
615    
616  static int  static int
617  dct_quantize_trellis_inter_mpeg_c (int16_t *qcoeff, const int16_t *data, int quant)  dct_quantize_trellis_mpeg_c(int16_t *const Out, const int16_t *const In, int Q,
618                    const uint16_t * const Zigzag, int Non_Zero)
619  { return 63; }  { return 63; }
620    
621    
# Line 753  Line 755 
755  }  }
756    
757  //////////////////////////////////////////////////////////  //////////////////////////////////////////////////////////
758    // this routine has been strippen of all debug code
759    //////////////////////////////////////////////////////////
760    
761    static int
762    dct_quantize_trellis_h263_c(int16_t *const Out, const int16_t *const In, int Q, const uint16_t * const Zigzag, int Non_Zero)
763    {
764    
765        // Note: We should search last non-zero coeffs on *real* DCT input coeffs (In[]),
766        // not quantized one (Out[]). However, it only improves the result *very*
767        // slightly (~0.01dB), whereas speed drops to crawling level :)
768        // Well, actually, taking 1 more coeff past Non_Zero into account sometimes helps,
769    
770      typedef struct { int16_t Run, Level; } NODE;
771    
772      NODE Nodes[65], Last;
773      uint32_t Run_Costs0[64+1];
774      uint32_t * const Run_Costs = Run_Costs0 + 1;
775      const int Mult = 2*Q;
776      const int Bias = (Q-1) | 1;
777      const int Lev0 = Mult + Bias;
778      const int Lambda = Trellis_Lambda_Tabs[Q-1];    // it's 1/lambda, actually
779    
780      int Run_Start = -1;
781      Run_Costs[-1] = 2<<16;                          // source (w/ CBP penalty)
782      uint32_t Min_Cost = 2<<16;
783    
784      int Last_Node = -1;
785      uint32_t Last_Cost = 0;
786    
787      int i, j;
788    
789      Non_Zero = Find_Last(Out, Zigzag, Non_Zero);
790      if (Non_Zero<0)
791          return -1;
792    
793      for(i=0; i<=Non_Zero; i++)
794      {
795        const int AC = In[Zigzag[i]];
796        const int Level1 = Out[Zigzag[i]];
797        const int Dist0 = Lambda* AC*AC;
798        uint32_t Best_Cost = 0xf0000000;
799        Last_Cost += Dist0;
800    
801        if ((uint32_t)(Level1+1)<3)                 // very specialized loop for -1,0,+1
802        {
803            int dQ;
804                    int Run;
805          uint32_t Cost0;
806    
807          if (AC<0) {
808            Nodes[i].Level = -1;
809            dQ = Lev0 + AC;
810          } else {
811            Nodes[i].Level = 1;
812            dQ = Lev0 - AC;
813          }
814                    Cost0 = Lambda*dQ*dQ;
815    
816          Nodes[i].Run = 1;
817          Best_Cost = (Code_Len20[0]<<16) + Run_Costs[i-1]+Cost0;
818          for(Run=i-Run_Start; Run>0; --Run)
819          {
820            const uint32_t Cost_Base = Cost0 + Run_Costs[i-Run];
821            const uint32_t Cost = Cost_Base + (Code_Len20[Run-1]<<16);
822            const uint32_t lCost = Cost_Base + (Code_Len24[Run-1]<<16);
823    
824              // TODO: what about tie-breaks? Should we favor short runs or
825              // long runs? Although the error is the same, it would not be
826              // spread the same way along high and low frequencies...
827    
828                            // (I'd say: favour short runs => hifreq errors (HVS) -- gruel )
829    
830            if (Cost<Best_Cost) {
831              Best_Cost    = Cost;
832              Nodes[i].Run = Run;
833            }
834    
835            if (lCost<Last_Cost) {
836              Last_Cost  = lCost;
837              Last.Run   = Run;
838              Last_Node  = i;
839            }
840          }
841          if (Last_Node==i)
842                            Last.Level = Nodes[i].Level;
843        }
844        else                      // "big" levels
845        {
846          const uint8_t *Tbl_L1, *Tbl_L2, *Tbl_L1_Last, *Tbl_L2_Last;
847          int Level2;
848          int dQ1, dQ2;
849          int Run;
850                    uint32_t Dist1,Dist2;
851                    int dDist21;
852    
853              if (Level1>1) {
854            dQ1 = Level1*Mult-AC + Bias;
855            dQ2 = dQ1 - Mult;
856            Level2 = Level1-1;
857            Tbl_L1      = (Level1<=24) ? B16_17_Code_Len[Level1-1]     : Code_Len0;
858            Tbl_L2      = (Level2<=24) ? B16_17_Code_Len[Level2-1]     : Code_Len0;
859            Tbl_L1_Last = (Level1<=6) ? B16_17_Code_Len_Last[Level1-1] : Code_Len0;
860            Tbl_L2_Last = (Level2<=6) ? B16_17_Code_Len_Last[Level2-1] : Code_Len0;
861          } else { // Level1<-1
862            dQ1 = Level1*Mult-AC - Bias;
863            dQ2 = dQ1 + Mult;
864            Level2 = Level1 + 1;
865            Tbl_L1      = (Level1>=-24) ? B16_17_Code_Len[Level1^-1]      : Code_Len0;
866            Tbl_L2      = (Level2>=-24) ? B16_17_Code_Len[Level2^-1]      : Code_Len0;
867            Tbl_L1_Last = (Level1>=- 6) ? B16_17_Code_Len_Last[Level1^-1] : Code_Len0;
868            Tbl_L2_Last = (Level2>=- 6) ? B16_17_Code_Len_Last[Level2^-1] : Code_Len0;
869          }
870          Dist1 = Lambda*dQ1*dQ1;
871          Dist2 = Lambda*dQ2*dQ2;
872          dDist21 = Dist2-Dist1;
873    
874          for(Run=i-Run_Start; Run>0; --Run)
875          {
876            const uint32_t Cost_Base = Dist1 + Run_Costs[i-Run];
877            uint32_t Cost1, Cost2;
878            int bLevel;
879    
880    // for sub-optimal (but slightly worth it, speed-wise) search, uncomment the following:
881    //        if (Cost_Base>=Best_Cost) continue;
882    // (? doesn't seem to have any effect -- gruel )
883    
884            Cost1 = Cost_Base + (Tbl_L1[Run-1]<<16);
885            Cost2 = Cost_Base + (Tbl_L2[Run-1]<<16) + dDist21;
886    
887            if (Cost2<Cost1) {
888                             Cost1 = Cost2;
889                             bLevel = Level2;
890                      } else
891                             bLevel = Level1;
892    
893            if (Cost1<Best_Cost) {
894              Best_Cost = Cost1;
895              Nodes[i].Run   = Run;
896              Nodes[i].Level = bLevel;
897            }
898    
899            Cost1 = Cost_Base + (Tbl_L1_Last[Run-1]<<16);
900            Cost2 = Cost_Base + (Tbl_L2_Last[Run-1]<<16) + dDist21;
901    
902            if (Cost2<Cost1) {
903                             Cost1 = Cost2;
904                             bLevel = Level2;
905                      } else
906                             bLevel = Level1;
907    
908            if (Cost1<Last_Cost) {
909              Last_Cost  = Cost1;
910              Last.Run   = Run;
911              Last.Level = bLevel;
912              Last_Node  = i;
913            }
914          } //end of "for Run"
915    
916        }
917    
918        Run_Costs[i] = Best_Cost;
919    
920        if (Best_Cost < Min_Cost + Dist0) {
921          Min_Cost = Best_Cost;
922          Run_Start = i;
923        }
924        else
925        {
926            // as noticed by Michael Niedermayer (michaelni at gmx.at), there's
927            // a code shorter by 1 bit for a larger run (!), same level. We give
928            // it a chance by not moving the left barrier too much.
929    
930          while( Run_Costs[Run_Start]>Min_Cost+(1<<16) )
931            Run_Start++;
932    
933            // spread on preceding coeffs the cost incurred by skipping this one
934          for(j=Run_Start; j<i; ++j) Run_Costs[j] += Dist0;
935          Min_Cost += Dist0;
936        }
937      }
938    
939      if (Last_Node<0)
940        return -1;
941    
942           // reconstruct optimal sequence backward with surviving paths
943      memset(Out, 0x00, 64*sizeof(*Out));
944      Out[Zigzag[Last_Node]] = Last.Level;
945      i = Last_Node - Last.Run;
946      while(i>=0) {
947        Out[Zigzag[i]] = Nodes[i].Level;
948        i -= Nodes[i].Run;
949      }
950      return Last_Node;
951    }
952    
953    
954    
955    
956    
957    
958    
959    
960    
961    
962    
963    //////////////////////////////////////////////////////////
964    // original version including heavy debugging info
965    //////////////////////////////////////////////////////////
966    
967    
968    #ifdef DBGTRELL
969    
970  #define DBG 0  #define DBG 0
971    
972  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,
973                                  const uint16_t * Zigzag, int Max, int Lambda)                                  const uint16_t * Zigzag, int Max, int Lambda)
974  {  {
975  #if (DBG>0)  #if (DBG>0)
976    const int16_t * const Ref = C + 6*64;    const int16_t * const Ref = C + 6*64;
977    int Last = Max;    int Last = Max;
   while(Last>=0 && C[Zigzag[Last]]==0) Last--;  
978    int Bits = 0;    int Bits = 0;
979      int Dist = 0;
980      int i;
981      uint32_t Cost;
982    
983      while(Last>=0 && C[Zigzag[Last]]==0)
984            Last--;
985    
986    if (Last>=0) {    if (Last>=0) {
     Bits = 2;   // CBP  
987      int j=0, j0=0;      int j=0, j0=0;
988      int Run, Level;      int Run, Level;
989    
990        Bits = 2;   // CBP
991      while(j<Last) {      while(j<Last) {
992        while(!C[Zigzag[j]]) j++;        while(!C[Zigzag[j]])
993        if (j==Last) break;                          j++;
994          if (j==Last)
995                            break;
996        Level=C[Zigzag[j]];        Level=C[Zigzag[j]];
997        Run = j - j0;        Run = j - j0;
998        j0 = ++j;        j0 = ++j;
999        if (Level>=-24 && Level<=24) Bits += B16_17_Code_Len[(Level<0) ? -Level-1 : Level-1][Run];        if (Level>=-24 && Level<=24)
1000        else Bits += 30;                          Bits += B16_17_Code_Len[(Level<0) ? -Level-1 : Level-1][Run];
1001          else
1002                            Bits += 30;
1003      }      }
1004      Level = C[Zigzag[Last]];      Level = C[Zigzag[Last]];
1005      Run = j - j0;      Run = j - j0;
1006      if (Level>=-6 && Level<=6) Bits += B16_17_Code_Len_Last[(Level<0) ? -Level-1 : Level-1][Run];      if (Level>=-6 && Level<=6)
1007      else Bits += 30;                  Bits += B16_17_Code_Len_Last[(Level<0) ? -Level-1 : Level-1][Run];
1008        else
1009                    Bits += 30;
1010    }    }
1011    
   int Dist = 0;  
   int i;  
1012    for(i=0; i<=Last; ++i) {    for(i=0; i<=Last; ++i) {
1013      int V = C[Zigzag[i]]*Mult;      int V = C[Zigzag[i]]*Mult;
1014      if      (V>0) V += Bias;      if (V>0)
1015      else if (V<0) V -= Bias;                  V += Bias;
1016        else
1017                    if (V<0)
1018                            V -= Bias;
1019      V -= Ref[Zigzag[i]];      V -= Ref[Zigzag[i]];
1020      Dist += V*V;      Dist += V*V;
1021    }    }
1022    uint32_t Cost = Lambda*Dist + (Bits<<16);    Cost = Lambda*Dist + (Bits<<16);
1023    if (DBG==1)    if (DBG==1)
1024      printf( " Last:%2d/%2d Cost = [(Bits=%5.0d) + Lambda*(Dist=%6.0d) = %d ] >>12= %d ", Last,Max, Bits, Dist, Cost, Cost>>12 );      printf( " Last:%2d/%2d Cost = [(Bits=%5.0d) + Lambda*(Dist=%6.0d) = %d ] >>12= %d ", Last,Max, Bits, Dist, Cost, Cost>>12 );
1025    return Cost;    return Cost;
# Line 815  Line 1042 
1042    typedef struct { int16_t Run, Level; } NODE;    typedef struct { int16_t Run, Level; } NODE;
1043    
1044    NODE Nodes[65], Last;    NODE Nodes[65], Last;
1045    uint32_t Run_Costs0[64+1], * const Run_Costs = Run_Costs0 + 1;    uint32_t Run_Costs0[64+1];
1046      uint32_t * const Run_Costs = Run_Costs0 + 1;
1047    const int Mult = 2*Q;    const int Mult = 2*Q;
1048    const int Bias = (Q-1) | 1;    const int Bias = (Q-1) | 1;
1049    const int Lev0 = Mult + Bias;    const int Lev0 = Mult + Bias;
# Line 829  Line 1056 
1056    int Last_Node = -1;    int Last_Node = -1;
1057    uint32_t Last_Cost = 0;    uint32_t Last_Cost = 0;
1058    
1059      int i, j;
1060    
1061  #if (DBG>0)  #if (DBG>0)
1062    Last.Level = 0; Last.Run = -1; // just initialize to smthg    Last.Level = 0; Last.Run = -1; // just initialize to smthg
1063  #endif  #endif
1064    
   int i, j;  
   
1065    Non_Zero = Find_Last(Out, Zigzag, Non_Zero);    Non_Zero = Find_Last(Out, Zigzag, Non_Zero);
1066    if (Non_Zero<0)    if (Non_Zero<0)
1067        return -1;        return -1;
# Line 851  Line 1078 
1078      {      {
1079        int dQ;        int dQ;
1080            int Run;            int Run;
1081          uint32_t Cost0;
1082    
1083        if (AC<0) {        if (AC<0) {
1084          Nodes[i].Level = -1;          Nodes[i].Level = -1;
# Line 859  Line 1087 
1087          Nodes[i].Level = 1;          Nodes[i].Level = 1;
1088          dQ = Lev0 - AC;          dQ = Lev0 - AC;
1089        }        }
1090        const uint32_t Cost0 = Lambda*dQ*dQ;                  Cost0 = Lambda*dQ*dQ;
1091    
1092        Nodes[i].Run = 1;        Nodes[i].Run = 1;
1093        Best_Cost = (Code_Len20[0]<<16) + Run_Costs[i-1]+Cost0;        Best_Cost = (Code_Len20[0]<<16) + Run_Costs[i-1]+Cost0;
# Line 867  Line 1095 
1095        {        {
1096          const uint32_t Cost_Base = Cost0 + Run_Costs[i-Run];          const uint32_t Cost_Base = Cost0 + Run_Costs[i-Run];
1097          const uint32_t Cost = Cost_Base + (Code_Len20[Run-1]<<16);          const uint32_t Cost = Cost_Base + (Code_Len20[Run-1]<<16);
1098            const uint32_t lCost = Cost_Base + (Code_Len24[Run-1]<<16);
1099    
1100            // TODO: what about tie-breaks? Should we favor short runs or            // TODO: what about tie-breaks? Should we favor short runs or
1101            // long runs? Although the error is the same, it would not be            // long runs? Although the error is the same, it would not be
1102            // spread the same way along high and low frequencies...            // spread the same way along high and low frequencies...
1103          if (Cost<Best_Cost)          if (Cost<Best_Cost) {
         {  
1104            Best_Cost    = Cost;            Best_Cost    = Cost;
1105            Nodes[i].Run = Run;            Nodes[i].Run = Run;
1106          }          }
1107          const uint32_t lCost = Cost_Base + (Code_Len24[Run-1]<<16);  
1108          if (lCost<Last_Cost)          if (lCost<Last_Cost) {
         {  
1109            Last_Cost  = lCost;            Last_Cost  = lCost;
1110            Last.Run   = Run;            Last.Run   = Run;
1111            Last_Node  = i;            Last_Node  = i;
1112          }          }
1113        }        }
1114        if (Last_Node==i) Last.Level = Nodes[i].Level;        if (Last_Node==i)
1115                            Last.Level = Nodes[i].Level;
1116    
1117        if (DBG==1) {        if (DBG==1) {
1118          Run_Costs[i] = Best_Cost;          Run_Costs[i] = Best_Cost;
# Line 907  Line 1135 
1135        int Level2;        int Level2;
1136        int dQ1, dQ2;        int dQ1, dQ2;
1137        int Run;        int Run;
1138                    uint32_t Dist1,Dist2;
1139                    int dDist21;
1140    
1141            if (Level1>1) {            if (Level1>1) {
1142          dQ1 = Level1*Mult-AC + Bias;          dQ1 = Level1*Mult-AC + Bias;
# Line 916  Line 1146 
1146          Tbl_L2      = (Level2<=24) ? B16_17_Code_Len[Level2-1]     : Code_Len0;          Tbl_L2      = (Level2<=24) ? B16_17_Code_Len[Level2-1]     : Code_Len0;
1147          Tbl_L1_Last = (Level1<=6) ? B16_17_Code_Len_Last[Level1-1] : Code_Len0;          Tbl_L1_Last = (Level1<=6) ? B16_17_Code_Len_Last[Level1-1] : Code_Len0;
1148          Tbl_L2_Last = (Level2<=6) ? B16_17_Code_Len_Last[Level2-1] : Code_Len0;          Tbl_L2_Last = (Level2<=6) ? B16_17_Code_Len_Last[Level2-1] : Code_Len0;
1149        }        } else { // Level1<-1
       else { // Level1<-1  
1150          dQ1 = Level1*Mult-AC - Bias;          dQ1 = Level1*Mult-AC - Bias;
1151          dQ2 = dQ1 + Mult;          dQ2 = dQ1 + Mult;
1152          Level2 = Level1 + 1;          Level2 = Level1 + 1;
# Line 926  Line 1155 
1155          Tbl_L1_Last = (Level1>=- 6) ? B16_17_Code_Len_Last[Level1^-1] : Code_Len0;          Tbl_L1_Last = (Level1>=- 6) ? B16_17_Code_Len_Last[Level1^-1] : Code_Len0;
1156          Tbl_L2_Last = (Level2>=- 6) ? B16_17_Code_Len_Last[Level2^-1] : Code_Len0;          Tbl_L2_Last = (Level2>=- 6) ? B16_17_Code_Len_Last[Level2^-1] : Code_Len0;
1157        }        }
1158        const uint32_t Dist1 = Lambda*dQ1*dQ1;        Dist1 = Lambda*dQ1*dQ1;
1159        const uint32_t Dist2 = Lambda*dQ2*dQ2;        Dist2 = Lambda*dQ2*dQ2;
1160        const int dDist21 = Dist2-Dist1;        dDist21 = Dist2-Dist1;
1161    
1162        for(Run=i-Run_Start; Run>0; --Run)        for(Run=i-Run_Start; Run>0; --Run)
1163        {        {
1164          const uint32_t Cost_Base = Dist1 + Run_Costs[i-Run];          const uint32_t Cost_Base = Dist1 + Run_Costs[i-Run];
1165            uint32_t Cost1, Cost2;
1166            int bLevel;
1167    
1168  // for sub-optimal (but slightly worth it, speed-wise) search, uncomment the following:  // for sub-optimal (but slightly worth it, speed-wise) search, uncomment the following:
1169  //        if (Cost_Base>=Best_Cost) continue;  //        if (Cost_Base>=Best_Cost) continue;
1170    
         uint32_t Cost1, Cost2;  
         int bLevel;  
   
1171          Cost1 = Cost_Base + (Tbl_L1[Run-1]<<16);          Cost1 = Cost_Base + (Tbl_L1[Run-1]<<16);
1172          Cost2 = Cost_Base + (Tbl_L2[Run-1]<<16) + dDist21;          Cost2 = Cost_Base + (Tbl_L2[Run-1]<<16) + dDist21;
1173    
1174          if (Cost2<Cost1) { Cost1 = Cost2; bLevel = Level2; }          if (Cost2<Cost1) {
1175          else bLevel = Level1;                           Cost1 = Cost2;
1176                             bLevel = Level2;
1177                      } else
1178                             bLevel = Level1;
1179    
1180          if (Cost1<Best_Cost)          if (Cost1<Best_Cost) {
         {  
1181            Best_Cost = Cost1;            Best_Cost = Cost1;
1182            Nodes[i].Run   = Run;            Nodes[i].Run   = Run;
1183            Nodes[i].Level = bLevel;            Nodes[i].Level = bLevel;
# Line 956  Line 1186 
1186          Cost1 = Cost_Base + (Tbl_L1_Last[Run-1]<<16);          Cost1 = Cost_Base + (Tbl_L1_Last[Run-1]<<16);
1187          Cost2 = Cost_Base + (Tbl_L2_Last[Run-1]<<16) + dDist21;          Cost2 = Cost_Base + (Tbl_L2_Last[Run-1]<<16) + dDist21;
1188    
1189          if (Cost2<Cost1) { Cost1 = Cost2; bLevel = Level2; }          if (Cost2<Cost1) {
1190          else bLevel = Level1;                           Cost1 = Cost2;
1191          if (Cost1<Last_Cost)                           bLevel = Level2;
1192          {                    } else
1193                             bLevel = Level1;
1194    
1195            if (Cost1<Last_Cost) {
1196            Last_Cost  = Cost1;            Last_Cost  = Cost1;
1197            Last.Run   = Run;            Last.Run   = Run;
1198            Last.Level = bLevel;            Last.Level = bLevel;
1199            Last_Node  = i;            Last_Node  = i;
1200          }          }
1201        }        } //end of "for Run"
1202    
1203        if (DBG==1) {        if (DBG==1) {
1204          Run_Costs[i] = Best_Cost;          Run_Costs[i] = Best_Cost;
# Line 994  Line 1227 
1227          // as noticed by Michael Niedermayer (michaelni at gmx.at), there's          // as noticed by Michael Niedermayer (michaelni at gmx.at), there's
1228          // a code shorter by 1 bit for a larger run (!), same level. We give          // a code shorter by 1 bit for a larger run (!), same level. We give
1229          // it a chance by not moving the left barrier too much.          // it a chance by not moving the left barrier too much.
1230    
1231        while( Run_Costs[Run_Start]>Min_Cost+(1<<16) )        while( Run_Costs[Run_Start]>Min_Cost+(1<<16) )
1232          Run_Start++;          Run_Start++;
1233    
# Line 1016  Line 1250 
1250      return -1;      return -1;
1251    
1252         // reconstruct optimal sequence backward with surviving paths         // reconstruct optimal sequence backward with surviving paths
1253    bzero(Out, 64*sizeof(*Out));    memset(Out, 0x00, 64*sizeof(*Out));
1254    Out[Zigzag[Last_Node]] = Last.Level;    Out[Zigzag[Last_Node]] = Last.Level;
1255    i = Last_Node - Last.Run;    i = Last_Node - Last.Run;
1256    while(i>=0) {    while(i>=0) {
# Line 1037  Line 1271 
1271  }  }
1272    
1273  #undef DBG  #undef DBG
1274    
1275    #endif

Legend:
Removed from v.1011  
changed lines
  Added in v.1012

No admin address has been configured
ViewVC Help
Powered by ViewVC 1.0.4