[cvs] / xvidcore / src / utils / mbtransquant.c Repository:
ViewVC logotype

Diff of /xvidcore/src/utils/mbtransquant.c

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

revision 1.21.2.8, Sun Apr 13 16:18:09 2003 UTC revision 1.21.2.12, Mon May 12 12:33:16 2003 UTC
# Line 25  Line 25 
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 34  Line 35 
35  #include "../global.h"  #include "../global.h"
36  #include "mem_transfer.h"  #include "mem_transfer.h"
37  #include "timer.h"  #include "timer.h"
38    #include "../bitstream/mbcoding.h"
39    #include "../bitstream/zigzag.h"
40  #include "../dct/fdct.h"  #include "../dct/fdct.h"
41  #include "../dct/idct.h"  #include "../dct/idct.h"
42  #include "../quant/quant_mpeg4.h"  #include "../quant/quant_mpeg4.h"
# Line 115  Line 118 
118  /* Quantize all blocks -- Intra mode */  /* Quantize all blocks -- Intra mode */
119  static __inline void  static __inline void
120  MBQuantIntra(const MBParam * pParam,  MBQuantIntra(const MBParam * pParam,
121                             const FRAMEINFO * const frame,
122                           const MACROBLOCK * pMB,                           const MACROBLOCK * pMB,
123                           int16_t qcoeff[6 * 64],                           int16_t qcoeff[6 * 64],
124                           int16_t data[6*64])                           int16_t data[6*64])
# Line 126  Line 130 
130    
131                  /* Quantize the block */                  /* Quantize the block */
132                  start_timer();                  start_timer();
133                  if (!(pParam->vol_flags & XVID_VOL_MPEGQUANT))                  if (!(pParam->vol_flags & XVID_VOL_MPEGQUANT)) {
134                          quant_intra(&data[i * 64], &qcoeff[i * 64], pMB->quant, iDcScaler);                          quant_intra(&data[i * 64], &qcoeff[i * 64], pMB->quant, iDcScaler);
135                  else                  } else {
136                          quant4_intra(&data[i * 64], &qcoeff[i * 64], pMB->quant, iDcScaler);                          quant4_intra(&data[i * 64], &qcoeff[i * 64], pMB->quant, iDcScaler);
137                    }
138                  stop_quant_timer();                  stop_quant_timer();
139          }          }
140  }  }
# Line 155  Line 160 
160          }          }
161  }  }
162    
163    
164    static int
165    dct_quantize_trellis_h263_c(int16_t *const Out, const int16_t *const In, int Q, const uint16_t * const Zigzag, int Non_Zero);
166    
167    static int
168    dct_quantize_trellis_mpeg_c(int16_t *const Out, const int16_t *const In, int Q, const uint16_t * const Zigzag, int Non_Zero);
169    
170    
171  /* Quantize all blocks -- Inter mode */  /* Quantize all blocks -- Inter mode */
172  static __inline uint8_t  static __inline uint8_t
173  MBQuantInter(const MBParam * pParam,  MBQuantInter(const MBParam * pParam,
174                             const FRAMEINFO * const frame,
175                           const MACROBLOCK * pMB,                           const MACROBLOCK * pMB,
176                           int16_t data[6 * 64],                           int16_t data[6 * 64],
177                           int16_t qcoeff[6 * 64],                           int16_t qcoeff[6 * 64],
# Line 174  Line 188 
188    
189                  /* Quantize the block */                  /* Quantize the block */
190                  start_timer();                  start_timer();
191                  if (!(pParam->vol_flags & XVID_VOL_MPEGQUANT))                  if (!(pParam->vol_flags & XVID_VOL_MPEGQUANT)) {
192                          sum = quant_inter(&qcoeff[i * 64], &data[i * 64], pMB->quant);                          sum = quant_inter(&qcoeff[i * 64], &data[i * 64], pMB->quant);
193                  else                          if ( (sum) && (frame->vop_flags & XVID_VOP_TRELLISQUANT) ) {
194                                    sum = dct_quantize_trellis_h263_c(&qcoeff[i*64], &data[i*64], pMB->quant, &scan_tables[0][0], 63)+1;
195                                    limit = 1;
196                            }
197                    } else {
198                          sum = quant4_inter(&qcoeff[i * 64], &data[i * 64], pMB->quant);                          sum = quant4_inter(&qcoeff[i * 64], &data[i * 64], pMB->quant);
199    //                      if ( (sum) && (frame->vop_flags & XVID_VOP_TRELLISQUANT) )
200    //                              sum = dct_quantize_trellis_mpeg_c (&qcoeff[i*64], &data[i*64], pMB->quant)+1;
201                    }
202                  stop_quant_timer();                  stop_quant_timer();
203    
204                  /*                  /*
# Line 202  Line 223 
223    
224                  /* Set the corresponding cbp bit */                  /* Set the corresponding cbp bit */
225                  cbp |= code_block << (5 - i);                  cbp |= code_block << (5 - i);
   
226          }          }
227    
228          return(cbp);          return(cbp);
# Line 374  Line 394 
394          MBfDCT(pParam, frame, pMB, x_pos, y_pos, data);          MBfDCT(pParam, frame, pMB, x_pos, y_pos, data);
395    
396          /* Quantize the block */          /* Quantize the block */
397          MBQuantIntra(pParam, pMB, data, qcoeff);          MBQuantIntra(pParam, frame, pMB, data, qcoeff);
398    
399          /* DeQuantize the block */          /* DeQuantize the block */
400          MBDeQuantIntra(pParam, pMB->quant, data, qcoeff);          MBDeQuantIntra(pParam, pMB->quant, data, qcoeff);
# Line 411  Line 431 
431          limit = PVOP_TOOSMALL_LIMIT + ((pMB->quant == 1)? 1 : 0);          limit = PVOP_TOOSMALL_LIMIT + ((pMB->quant == 1)? 1 : 0);
432    
433          /* Quantize the block */          /* Quantize the block */
434          cbp = MBQuantInter(pParam, pMB, data, qcoeff, 0, limit);          cbp = MBQuantInter(pParam, frame, pMB, data, qcoeff, 0, limit);
435    
436          /* DeQuantize the block */          /* DeQuantize the block */
437          MBDeQuantInter(pParam, pMB->quant, data, qcoeff, cbp);          MBDeQuantInter(pParam, pMB->quant, data, qcoeff, cbp);
# Line 449  Line 469 
469          limit = BVOP_TOOSMALL_LIMIT;          limit = BVOP_TOOSMALL_LIMIT;
470    
471          /* Quantize the block */          /* Quantize the block */
472          cbp = MBQuantInter(pParam, pMB, data, qcoeff, 1, limit);          cbp = MBQuantInter(pParam, frame, pMB, data, qcoeff, 1, limit);
473    
474          /*          /*
475           * History comment:           * History comment:
# Line 580  Line 600 
600          MOVLINE(LINE(3, 5), LINE(3, 3));          MOVLINE(LINE(3, 5), LINE(3, 3));
601          MOVLINE(LINE(3, 3), tmp);          MOVLINE(LINE(3, 3), tmp);
602  }  }
603    
604    
605    
606    
607    
608    /************************************************************************
609     *               Trellis based R-D optimal quantization                 *
610     *                                                                      *
611     *   Trellis Quant code (C) 2003 Pascal Massimino skal(at)planet-d.net  *
612     *                                                                      *
613     ************************************************************************/
614    
615    
616    static int
617    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; }
620    
621    
622    //////////////////////////////////////////////////////////
623    //
624    //        Trellis-Based quantization
625    //
626    // So far I understand this paper:
627    //
628    //  "Trellis-Based R-D Optimal Quantization in H.263+"
629    //    J.Wen, M.Luttrell, J.Villasenor
630    //    IEEE Transactions on Image Processing, Vol.9, No.8, Aug. 2000.
631    //
632    // we are at stake with a simplified Bellmand-Ford / Dijkstra Single
633    // Source Shorted Path algo. But due to the underlying graph structure
634    // ("Trellis"), it can be turned into a dynamic programming algo,
635    // partially saving the explicit graph's nodes representation. And
636    // without using a heap, since the open frontier of the DAG is always
637    // known, and of fixed sized.
638    //
639    //////////////////////////////////////////////////////////
640    
641    
642    //////////////////////////////////////////////////////////
643    // Codes lengths for relevant levels.
644    
645      // let's factorize:
646    static const uint8_t Code_Len0[64] = {
647      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,
648      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 };
649    static const uint8_t Code_Len1[64] = {
650      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,
651      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 };
652    static const uint8_t Code_Len2[64] = {
653      19,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,
654      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 };
655    static const uint8_t Code_Len3[64] = {
656      18,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,
657      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 };
658    static const uint8_t Code_Len4[64] = {
659      17,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,
660      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 };
661    static const uint8_t Code_Len5[64] = {
662      16,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,
663      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 };
664    static const uint8_t Code_Len6[64] = {
665      15,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,
666      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 };
667    static const uint8_t Code_Len7[64] = {
668      13,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,
669      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 };
670    static const uint8_t Code_Len8[64] = {
671      11,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,
672      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 };
673    static const uint8_t Code_Len9[64] = {
674      12,21,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,
675      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 };
676    static const uint8_t Code_Len10[64] = {
677      12,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,
678      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 };
679    static const uint8_t Code_Len11[64] = {
680      12,19,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,
681      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 };
682    static const uint8_t Code_Len12[64] = {
683      11,17,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,
684      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 };
685    static const uint8_t Code_Len13[64] = {
686      11,15,21,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,
687      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 };
688    static const uint8_t Code_Len14[64] = {
689      10,12,19,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,
690      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 };
691    static const uint8_t Code_Len15[64] = {
692      10,13,17,19,21,21,21,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,
693      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 };
694    static const uint8_t Code_Len16[64] = {
695       9,12,13,18,18,19,19,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,
696      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};
697    static const uint8_t Code_Len17[64] = {
698       8,11,13,14,14,14,15,19,19,19,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
699      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 };
700    static const uint8_t Code_Len18[64] = {
701       7, 9,11,11,13,13,13,15,15,15,16,22,22,22,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,
702      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 };
703    static const uint8_t Code_Len19[64] = {
704       5, 7, 9,10,10,11,11,11,11,11,13,14,16,17,17,18,18,18,18,18,18,18,18,20,20,21,21,30,30,30,30,30,
705      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 };
706    static const uint8_t Code_Len20[64] = {
707       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,
708      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 };
709    
710      // a few more table for LAST table:
711    static const uint8_t Code_Len21[64] = {
712      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,
713      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};
714    static const uint8_t Code_Len22[64] = {
715      12,15,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,
716      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};
717    static const uint8_t Code_Len23[64] = {
718      10,12,15,15,15,16,16,16,16,17,17,17,17,17,17,17,17,18,18,18,18,18,18,18,18,19,19,19,19,20,20,20,
719      20,21,21,21,21,21,21,21,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30};
720    static const uint8_t Code_Len24[64] = {
721       5, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,10,10,10,10,10,10,10,10,11,11,11,11,12,12,12,
722      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};
723    
724    
725    static const uint8_t * const B16_17_Code_Len[24] = { // levels [1..24]
726      Code_Len20,Code_Len19,Code_Len18,Code_Len17,
727      Code_Len16,Code_Len15,Code_Len14,Code_Len13,
728      Code_Len12,Code_Len11,Code_Len10,Code_Len9,
729      Code_Len8, Code_Len7 ,Code_Len6 ,Code_Len5,
730      Code_Len4, Code_Len3, Code_Len3 ,Code_Len2,
731      Code_Len2, Code_Len1, Code_Len1, Code_Len1,
732    };
733    
734    static const uint8_t * const B16_17_Code_Len_Last[6] = { // levels [1..6]
735      Code_Len24,Code_Len23,Code_Len22,Code_Len21, Code_Len3, Code_Len1,
736    };
737    
738    #define TL(q) 0xfe00/(q*q)
739    
740    static const int Trellis_Lambda_Tabs[31] = {
741             TL( 1),TL( 2),TL( 3),TL( 4),TL( 5),TL( 6), TL( 7),
742      TL( 8),TL( 9),TL(10),TL(11),TL(12),TL(13),TL(14), TL(15),
743      TL(16),TL(17),TL(18),TL(19),TL(20),TL(21),TL(22), TL(23),
744      TL(24),TL(25),TL(26),TL(27),TL(28),TL(29),TL(30), TL(31)
745    };
746    #undef TL
747    
748    static __inline int Find_Last(const int16_t *C, const uint16_t *Zigzag, int i)
749    {
750      while(i>=0)
751        if (C[Zigzag[i]])
752          return i;
753        else i--;
754      return -1;
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      uint32_t Min_Cost = 2<<16;
782    
783      int Last_Node = -1;
784      uint32_t Last_Cost = 0;
785    
786      int i, j;
787      Run_Costs[-1] = 2<<16;                          // source (w/ CBP penalty)
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
971    
972    static __inline uint32_t Evaluate_Cost(const int16_t *C, int Mult, int Bias,
973                                    const uint16_t * Zigzag, int Max, int Lambda)
974    {
975    #if (DBG>0)
976      const int16_t * const Ref = C + 6*64;
977      int Last = Max;
978      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) {
987        int j=0, j0=0;
988        int Run, Level;
989    
990        Bits = 2;   // CBP
991        while(j<Last) {
992          while(!C[Zigzag[j]])
993                            j++;
994          if (j==Last)
995                            break;
996          Level=C[Zigzag[j]];
997          Run = j - j0;
998          j0 = ++j;
999          if (Level>=-24 && Level<=24)
1000                            Bits += B16_17_Code_Len[(Level<0) ? -Level-1 : Level-1][Run];
1001          else
1002                            Bits += 30;
1003        }
1004        Level = C[Zigzag[Last]];
1005        Run = j - j0;
1006        if (Level>=-6 && Level<=6)
1007                    Bits += B16_17_Code_Len_Last[(Level<0) ? -Level-1 : Level-1][Run];
1008        else
1009                    Bits += 30;
1010      }
1011    
1012      for(i=0; i<=Last; ++i) {
1013        int V = C[Zigzag[i]]*Mult;
1014        if (V>0)
1015                    V += Bias;
1016        else
1017                    if (V<0)
1018                            V -= Bias;
1019        V -= Ref[Zigzag[i]];
1020        Dist += V*V;
1021      }
1022      Cost = Lambda*Dist + (Bits<<16);
1023      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 );
1025      return Cost;
1026    
1027    #else
1028      return 0;
1029    #endif
1030    }
1031    
1032    
1033    static int
1034    dct_quantize_trellis_h263_c(int16_t *const Out, const int16_t *const In, int Q, const uint16_t * const Zigzag, int Non_Zero)
1035    {
1036    
1037        // Note: We should search last non-zero coeffs on *real* DCT input coeffs (In[]),
1038        // not quantized one (Out[]). However, it only improves the result *very*
1039        // slightly (~0.01dB), whereas speed drops to crawling level :)
1040        // Well, actually, taking 1 more coeff past Non_Zero into account sometimes helps,
1041    
1042      typedef struct { int16_t Run, Level; } NODE;
1043    
1044      NODE Nodes[65], Last;
1045      uint32_t Run_Costs0[64+1];
1046      uint32_t * const Run_Costs = Run_Costs0 + 1;
1047      const int Mult = 2*Q;
1048      const int Bias = (Q-1) | 1;
1049      const int Lev0 = Mult + Bias;
1050      const int Lambda = Trellis_Lambda_Tabs[Q-1];    // it's 1/lambda, actually
1051    
1052      int Run_Start = -1;
1053      Run_Costs[-1] = 2<<16;                          // source (w/ CBP penalty)
1054      uint32_t Min_Cost = 2<<16;
1055    
1056      int Last_Node = -1;
1057      uint32_t Last_Cost = 0;
1058    
1059      int i, j;
1060    
1061    #if (DBG>0)
1062      Last.Level = 0; Last.Run = -1; // just initialize to smthg
1063    #endif
1064    
1065      Non_Zero = Find_Last(Out, Zigzag, Non_Zero);
1066      if (Non_Zero<0)
1067          return -1;
1068    
1069      for(i=0; i<=Non_Zero; i++)
1070      {
1071        const int AC = In[Zigzag[i]];
1072        const int Level1 = Out[Zigzag[i]];
1073        const int Dist0 = Lambda* AC*AC;
1074        uint32_t Best_Cost = 0xf0000000;
1075        Last_Cost += Dist0;
1076    
1077        if ((uint32_t)(Level1+1)<3)                 // very specialized loop for -1,0,+1
1078        {
1079            int dQ;
1080                    int Run;
1081          uint32_t Cost0;
1082    
1083          if (AC<0) {
1084            Nodes[i].Level = -1;
1085            dQ = Lev0 + AC;
1086          } else {
1087            Nodes[i].Level = 1;
1088            dQ = Lev0 - AC;
1089          }
1090                    Cost0 = Lambda*dQ*dQ;
1091    
1092          Nodes[i].Run = 1;
1093          Best_Cost = (Code_Len20[0]<<16) + Run_Costs[i-1]+Cost0;
1094          for(Run=i-Run_Start; Run>0; --Run)
1095          {
1096            const uint32_t Cost_Base = Cost0 + Run_Costs[i-Run];
1097            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
1101              // long runs? Although the error is the same, it would not be
1102              // spread the same way along high and low frequencies...
1103            if (Cost<Best_Cost) {
1104              Best_Cost    = Cost;
1105              Nodes[i].Run = Run;
1106            }
1107    
1108            if (lCost<Last_Cost) {
1109              Last_Cost  = lCost;
1110              Last.Run   = Run;
1111              Last_Node  = i;
1112            }
1113          }
1114          if (Last_Node==i)
1115                            Last.Level = Nodes[i].Level;
1116    
1117          if (DBG==1) {
1118            Run_Costs[i] = Best_Cost;
1119            printf( "Costs #%2d: ", i);
1120            for(j=-1;j<=Non_Zero;++j) {
1121              if (j==Run_Start)            printf( " %3.0d|", Run_Costs[j]>>12 );
1122              else if (j>Run_Start && j<i) printf( " %3.0d|", Run_Costs[j]>>12 );
1123              else if (j==i)               printf( "(%3.0d)", Run_Costs[j]>>12 );
1124              else                         printf( "  - |" );
1125            }
1126            printf( "<%3.0d %2d %d>", Min_Cost>>12, Nodes[i].Level, Nodes[i].Run );
1127            printf( "  Last:#%2d {%3.0d %2d %d}", Last_Node, Last_Cost>>12, Last.Level, Last.Run );
1128            printf( " AC:%3.0d Dist0:%3d Dist(%d)=%d", AC, Dist0>>12, Nodes[i].Level, Cost0>>12 );
1129            printf( "\n" );
1130          }
1131        }
1132        else                      // "big" levels
1133        {
1134          const uint8_t *Tbl_L1, *Tbl_L2, *Tbl_L1_Last, *Tbl_L2_Last;
1135          int Level2;
1136          int dQ1, dQ2;
1137          int Run;
1138                    uint32_t Dist1,Dist2;
1139                    int dDist21;
1140    
1141              if (Level1>1) {
1142            dQ1 = Level1*Mult-AC + Bias;
1143            dQ2 = dQ1 - Mult;
1144            Level2 = Level1-1;
1145            Tbl_L1      = (Level1<=24) ? B16_17_Code_Len[Level1-1]     : Code_Len0;
1146            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;
1148            Tbl_L2_Last = (Level2<=6) ? B16_17_Code_Len_Last[Level2-1] : Code_Len0;
1149          } else { // Level1<-1
1150            dQ1 = Level1*Mult-AC - Bias;
1151            dQ2 = dQ1 + Mult;
1152            Level2 = Level1 + 1;
1153            Tbl_L1      = (Level1>=-24) ? B16_17_Code_Len[Level1^-1]      : Code_Len0;
1154            Tbl_L2      = (Level2>=-24) ? B16_17_Code_Len[Level2^-1]      : Code_Len0;
1155            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;
1157          }
1158          Dist1 = Lambda*dQ1*dQ1;
1159          Dist2 = Lambda*dQ2*dQ2;
1160          dDist21 = Dist2-Dist1;
1161    
1162          for(Run=i-Run_Start; Run>0; --Run)
1163          {
1164            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:
1169    //        if (Cost_Base>=Best_Cost) continue;
1170    
1171            Cost1 = Cost_Base + (Tbl_L1[Run-1]<<16);
1172            Cost2 = Cost_Base + (Tbl_L2[Run-1]<<16) + dDist21;
1173    
1174            if (Cost2<Cost1) {
1175                             Cost1 = Cost2;
1176                             bLevel = Level2;
1177                      } else
1178                             bLevel = Level1;
1179    
1180            if (Cost1<Best_Cost) {
1181              Best_Cost = Cost1;
1182              Nodes[i].Run   = Run;
1183              Nodes[i].Level = bLevel;
1184            }
1185    
1186            Cost1 = Cost_Base + (Tbl_L1_Last[Run-1]<<16);
1187            Cost2 = Cost_Base + (Tbl_L2_Last[Run-1]<<16) + dDist21;
1188    
1189            if (Cost2<Cost1) {
1190                             Cost1 = Cost2;
1191                             bLevel = Level2;
1192                      } else
1193                             bLevel = Level1;
1194    
1195            if (Cost1<Last_Cost) {
1196              Last_Cost  = Cost1;
1197              Last.Run   = Run;
1198              Last.Level = bLevel;
1199              Last_Node  = i;
1200            }
1201          } //end of "for Run"
1202    
1203          if (DBG==1) {
1204            Run_Costs[i] = Best_Cost;
1205            printf( "Costs #%2d: ", i);
1206            for(j=-1;j<=Non_Zero;++j) {
1207              if (j==Run_Start)            printf( " %3.0d|", Run_Costs[j]>>12 );
1208              else if (j>Run_Start && j<i) printf( " %3.0d|", Run_Costs[j]>>12 );
1209              else if (j==i)               printf( "(%3.0d)", Run_Costs[j]>>12 );
1210              else                         printf( "  - |" );
1211            }
1212            printf( "<%3.0d %2d %d>", Min_Cost>>12, Nodes[i].Level, Nodes[i].Run );
1213            printf( "  Last:#%2d {%3.0d %2d %d}", Last_Node, Last_Cost>>12, Last.Level, Last.Run );
1214            printf( " AC:%3.0d Dist0:%3d Dist(%2d):%3d Dist(%2d):%3d", AC, Dist0>>12, Level1, Dist1>>12, Level2, Dist2>>12 );
1215            printf( "\n" );
1216          }
1217        }
1218    
1219        Run_Costs[i] = Best_Cost;
1220    
1221        if (Best_Cost < Min_Cost + Dist0) {
1222          Min_Cost = Best_Cost;
1223          Run_Start = i;
1224        }
1225        else
1226        {
1227            // 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
1229            // it a chance by not moving the left barrier too much.
1230    
1231          while( Run_Costs[Run_Start]>Min_Cost+(1<<16) )
1232            Run_Start++;
1233    
1234            // spread on preceding coeffs the cost incurred by skipping this one
1235          for(j=Run_Start; j<i; ++j) Run_Costs[j] += Dist0;
1236          Min_Cost += Dist0;
1237        }
1238      }
1239    
1240      if (DBG) {
1241        Last_Cost = Evaluate_Cost(Out,Mult,Bias, Zigzag,Non_Zero, Lambda);
1242        if (DBG==1) {
1243          printf( "=> " );
1244          for(i=0; i<=Non_Zero; ++i) printf( "[%3.0d] ", Out[Zigzag[i]] );
1245          printf( "\n" );
1246       }
1247      }
1248    
1249      if (Last_Node<0)
1250        return -1;
1251    
1252           // reconstruct optimal sequence backward with surviving paths
1253      memset(Out, 0x00, 64*sizeof(*Out));
1254      Out[Zigzag[Last_Node]] = Last.Level;
1255      i = Last_Node - Last.Run;
1256      while(i>=0) {
1257        Out[Zigzag[i]] = Nodes[i].Level;
1258        i -= Nodes[i].Run;
1259      }
1260    
1261      if (DBG) {
1262        uint32_t Cost = Evaluate_Cost(Out,Mult,Bias, Zigzag,Non_Zero, Lambda);
1263        if (DBG==1) {
1264          printf( "<= " );
1265          for(i=0; i<=Last_Node; ++i) printf( "[%3.0d] ", Out[Zigzag[i]] );
1266          printf( "\n--------------------------------\n" );
1267        }
1268        if (Cost>Last_Cost) printf( "!!! %u > %u\n", Cost, Last_Cost );
1269      }
1270      return Last_Node;
1271    }
1272    
1273    #undef DBG
1274    
1275    #endif
Legend:
Removed from v.1.21.2.8  
changed lines
  Added in v.1.21.2.12
No admin address has been configured
 ViewVC Help
Powered by ViewVC 1.0.4