skl_mpg4_enc.cpp

mpeg4编解码器

/********************************************************
 * Some code. Copyright (C) 2003 by Pascal Massimino.   *
 * All Rights Reserved.      (http://skal.planet-d.net) *
 * For Educational/Academic use ONLY. See 'LICENSE.TXT'.*
 ********************************************************/
/*
 * skl_mpg4_enc.cpp
 *
 * MPEG4 encoder
 ********************************************************/

#include "./skl_mpg4i.h"
#include "skl_syst/skl_exception.h"

static const char * const ID_STRING = "sklmp4 004";

//////////////////////////////////////////////////////////

#define ABS(x)  (((x)<0) ? -(x) : (x))
#define DIV_ROUND(x,y)  ( (x)>=0 ? ((x)+((y)>>1))/(y) : ((x)-((y)>>1))/(y) )

//////////////////////////////////////////////////////////
// Encoding tables
//////////////////////////////////////////////////////////

struct SKL_VLC { SKL_INT16 Val, Len; };

  // Table B-12
static const SKL_VLC MV_B12_Tab[32+1+32] = {
  { 5, 13}, { 7, 13}, { 5, 12}, { 7, 12}, { 9, 12}, {11, 12}, {13, 12}, {15, 12}
, { 9, 11}, {11, 11}, {13, 11}, {15, 11}, {17, 11}, {19, 11}, {21, 11}, {23, 11}
, {25, 11}, {27, 11}, {29, 11}, {31, 11}, {33, 11}, {35, 11}, {19, 10}, {21, 10}
, {23, 10}, { 7,  8}, { 9,  8}, {11,  8}, { 7,  7}, { 3,  5}, { 3,  4}, { 3,  3}
, { 1,  1}
, { 2,  3}, { 2,  4}, { 2,  5}, { 6,  7}, {10,  8}, { 8,  8}, { 6,  8}, {22, 10}
, {20, 10}, {18, 10}, {34, 11}, {32, 11}, {30, 11}, {28, 11}, {26, 11}, {24, 11}
, {22, 11}, {20, 11}, {18, 11}, {16, 11}, {14, 11}, {12, 11}, {10, 11}, { 8, 11}
, {14, 12}, {12, 12}, {10, 12}, { 8, 12}, { 6, 12}, { 4, 12}, { 6, 13}, { 4, 13}
};

  // Table B-6
static const SKL_VLC MCBPC_Intra_B6[2][4] = {  // index: [MB_Type-3][Cbpc]
  { {1, 1}, {1, 3}, {2, 3}, {3, 3} }    // MB_Type = 3, Cbpc=00 .. 11
, { {1, 4}, {1, 6}, {2, 6}, {3, 6} }    // MB_Type = 4, Cbpc=00 .. 11
};
  // Table B-7
static const SKL_VLC MCBPC_Inter_B7[5][4] = {  // index: [MB_Type][Cbpc]
  { {1, 1}, {3, 4}, {2, 4}, {5, 6} }
, { {3, 3}, {7, 7}, {6, 7}, {5, 9} }
, { {2, 3}, {5, 7}, {4, 7}, {5, 8} }
, { {3, 5}, {4, 8}, {3, 8}, {3, 7} }
, { {4, 6}, {4, 9}, {3, 9}, {2, 9} }
};

static const SKL_VLC CBPY_B8[16] = {   // index: Cbpy
  {3, 4}, {5, 5}, {4, 5}, { 9, 4}
, {3, 5}, {7, 4}, {2, 6}, {11, 4}
, {2, 5}, {3, 6}, {5, 4}, {10, 4}
, {4, 4}, {8, 4}, {6, 4}, { 3, 2}
};

 // Table B13/B14: DC-diff code, indexed by [size-1]. 
 // Bits for |DC| are blanked. 
 // Final Marker bit included for Size>8

static const SKL_VLC DCY_Tab_B13[12] = {
  { 6,  3}, { 8,  4}, {16,  6}, {16,  7},
  {32,  9}, {64, 11}, {128, 13}, {256, 15},
  {1025, 18}, {4097, 21}, {8193, 23}, {8193, 24}
};
  
static const SKL_VLC DCC_Tab_B14[12] = {
  { 4,  3}, { 4,  4}, { 8,  6}, {16,  8}
, {32, 10}, {64, 12}, {128, 14}, {256, 16}
, {1025, 19}, {2049, 21}, {4097, 23}, {8193, 25}
};

  // Table 6-27
static const int DQuant_Tab[5] = { 1, 0, -1 /*error*/, 2, 3 };

  // Table 6-33
static const SKL_VLC Spr_Tab_B33[15] = {
  {   0, 2}, {   2, 3}, {   3, 3}, {  4, 3}
, {   5, 3}, {   6, 3}, {  14, 4}, { 30, 5}
, {  62, 6}, { 126, 7}, { 254, 8}, {510, 9}
, {1022,10}, {2046,11}, {4094,12}
};
  
//////////////////////////////////////////////////////////
// MV coding
//////////////////////////////////////////////////////////

static void Write_Vector_Comp(SKL_FBB * const Bits, SKL_INT16 Val, SKL_INT32 Fix)
{
  const int High = 16 << Fix;
  SKL_ASSERT(Val>=-2*High && Val<2*High);

  if      (Val < -High) Val += 2*High;
  else if (Val >= High) Val -= 2*High;

  if (!Val)
    Bits->Put_Bits(1, 1); // 0 case hardcoded
  else {
    if (--Fix) {
      const SKL_UINT32 Sign = (Val<0);
      if (Sign) Val ^= -1;
      else      Val -= 1;
      const int Residue = Val & SKL_BMASKS::And[Fix];
      Val >>= Fix;
      SKL_ASSERT(Val>=0 && Val<=31);
      Bits->Put_Bits( MV_B12_Tab[33+Val].Val | Sign, MV_B12_Tab[33+Val].Len );
      Bits->Put_Bits( Residue, Fix );
    }
    else {
      SKL_ASSERT(Val>=-32 && Val<=32);
      Bits->Put_Bits( MV_B12_Tab[Val+32].Val, MV_B12_Tab[Val+32].Len );
    }
  }  
}

static void Write_Vector(SKL_FBB * const Bits, const SKL_MV MV, SKL_INT32 Fix)
{
  Write_Vector_Comp(Bits, MV[0], Fix);
  Write_Vector_Comp(Bits, MV[1], Fix);
}

//////////////////////////////////////////////////////////
//   AC coeff coding. 
//
// Description of the matrices Code[Run][Level]:
//  Codable {run,level} combinaisons ('x') are packed on the
//  upper left corner. Actually, the matrix looks like:
//    +-----------------[level]
//    |xxxxxxxxxxx...... <-
//    |xxxxxxxx......... <- max_level[run]
//    |xxxx............. <-
//    |xx...............
//    |x................
//    |x................
//    |.................
//    |.................
//[run]^^^^___ max_run[level]
//
//  Uncharted coeffs ('.') need being coded with escape code.
// If you use Esc-1 coding, you will jump on the left by
// max_level[run] steps, in hope you fall on a 'x' coded
// combinaison. With Esc-2 coding, you will move up by
// max_run[level]+1 steps. If neither works, you have to
// fall back to expensive Esc-3 coding.
//////////////////////////////////////////////////////////

#include "./skl_mpg4_enc_tbl.h"

static inline void Write_DC_Coeff(SKL_FBB * const Bits,
                                  SKL_INT16 DC,
                                  const int Lum)
{
  if (DC) {
    const int Sign = (DC<0);
    if (Sign) DC = -DC;
    int Size = SKL_BMASKS::Log2(DC);
    SKL_ASSERT(Size>=1 && Size<=12);
    if (Sign) DC ^= SKL_BMASKS::And[Size];
    const SKL_VLC *VLC = Lum ? &DCY_Tab_B13[Size-1] : &DCC_Tab_B14[Size-1];
    if (Size>8) DC <<= 1;     // make room for marker bit
    Bits->Put_Bits( VLC->Val | DC, VLC->Len );
  }
  else {
    if (Lum) Bits->Put_Bits( 3, 3 );
    else     Bits->Put_Bits( 3, 2 );
  }
}

static inline void Encode_Coeff(SKL_FBB *Bits, int Level, const SKL_UINT32 * const Tab)
{
  SKL_ASSERT(Level!=0 && Level>=-2048 && Level<=2047);
  if (!((Level+64)&-128)) { // Level is in [-64,63] -> use table
    const SKL_UINT32 Code = Tab[Level];
    if (0<=(SKL_INT32)Code)  // !bit31? -> it's a regular 21bits-max code
      Bits->Put_Bits( Code&0x00ffffff, Code>>24 );
    else                     // otherwise, code is actually a 30bits-Esc3
      Bits->Put_Bits( Code&0x7fffffff, 7+2+1+6+1+12+1 );
  }
  else {
      // Esc3 encoding (30bits total) for level not in [-64,63]
      // Tab[0] contains the esc3 code base: 0x01e02001 | (last<<20) | (run<<14)
    const SKL_UINT32 Code = Tab[0] | ((Level&0xfff)<<1);
    Bits->Put_Bits( Code, 7+2+1+6+1+12+1 );
  }
}

static inline void Write_Coeffs(SKL_FBB * const Bits, 
                                const SKL_INT16 *C,
                                const int Zigzag[],
                                int Last,
                                const SKL_UINT32 Tabs[2][64][128])
{
  Zigzag += Last;
  int j = -Last;
  while(1) {
    int Level;
    do Level = C[Zigzag[j++]]; while (!Level);
    if (j<=0) {
      Encode_Coeff( Bits, Level, &Tabs[0][Last+j-1][64] );
      Last = -j;
    }
    else {
      Encode_Coeff( Bits, Level, &Tabs[1][Last][64] );
      break;
    }
  }
}

static inline int Find_Last(const SKL_INT16 C[6*64], const int *Zigzag, int i)
{
  while(i>=0)
    if (C[Zigzag[i]])
      return i;
    else i--;
  return -1;
}


//////////////////////////////////////////////////////////
//
//        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 Bellman-Ford / Dijkstra Single
// Source Shortest 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 size.
//
//////////////////////////////////////////////////////////


#define DBG 0

SKL_UINT32 SKL_MP4_ENC_I::Evaluate_Cost(const SKL_INT16 *C, const int * const Zigzag, int Max, int Lambda) const
{
#if (DBG>0)
  const SKL_INT16 * const Ref = C + 6*64;
  int Last = Max;
  while(Last>=0 && C[Zigzag[Last]]==0) Last--;
  int Bits = 0;
  if (Last>=0) {
    Bits = 2;   // CBP
    int j=0, j0=0;
    int Run, Level;
    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;
  }

  int Dist = 0;
  for(int i=0; i<=Last; ++i) {
    const int q = Quant_Type ? ((Q*Inter_Matrix[Zigzag[i]]) >> 4) : Q;
    const int Mult = 2*q;
    const int Bias = (q-1) | 1;
    int V = C[Zigzag[i]]*Mult;
    if      (V>0) V += Bias;
    else if (V<0) V -= Bias;
    V -= Ref[Zigzag[i]];
    Dist += V*V;
  }
  SKL_UINT32 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;

#else
  return 0;
#endif
}

#define TL(q) 0xfe00/(q*q)

static const int Trellis_Lambda_Tabs[31] = {
         TL( 1),TL( 2),TL( 3),TL( 4),TL( 5),TL( 6), TL( 7),
  TL( 8),TL( 9),TL(10),TL(11),TL(12),TL(13),TL(14), TL(15),
  TL(16),TL(17),TL(18),TL(19),TL(20),TL(21),TL(22), TL(23),
  TL(24),TL(25),TL(26),TL(27),TL(28),TL(29),TL(30), TL(31)
};
#undef TL

int SKL_MP4_ENC_I::Trellis_Quantize(SKL_INT16 * const Out, const int Q, const int * const Zigzag, int Non_Zero) const
{
    // 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,

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

  struct NODE { SKL_INT16 Run, Level; };
  NODE Nodes[65], Last;
  SKL_UINT32 Run_Costs0[64+1], * const Run_Costs = Run_Costs0 + 1;

  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)
  SKL_UINT32 Min_Cost = 2<<16;

  int Last_Node = -1;
  SKL_UINT32 Last_Cost = 0;

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

  int i, j;
  for(i=0; i<=Non_Zero; i++)
  {
    const int q = Quant_Type ? ((Q*Inter_Matrix[Zigzag[i]]) >> 4) : Q;
    const int Mult = 2*q;
    const int Bias = (q-1) | 1;
    const int Lev0 = Mult + Bias;

    const SKL_INT16 * const In = Out + 6*64;
    const int AC = In[Zigzag[i]];
    const int Level1 = Out[Zigzag[i]];
    const int Dist0 = Lambda* AC*AC;
    Last_Cost += Dist0;

    SKL_UINT32 Best_Cost;
    if (3U>(SKL_UINT32)(Level1+1))                 // very specialized loop for -1,0,+1
    {
      int dQ;
      if (AC<0) {
        Nodes[i].Level = -1;
        dQ = Lev0 + AC;
      }
      else {
        Nodes[i].Level = 1;
        dQ = Lev0 - AC;
      }
      const SKL_UINT32 Cost0 = Lambda*dQ*dQ;
      Nodes[i].Run = 1;
      Best_Cost = (Code_Len20[0]<<16) + Run_Costs[i-1]+Cost0;
      for(int Run=i-Run_Start; Run>0; --Run)
      {
        const SKL_UINT32 Cost_Base = Cost0 + Run_Costs[i-Run];
        const SKL_UINT32 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 (Cost<Best_Cost)
        {
          Best_Cost    = Cost;
          Nodes[i].Run = Run;
        }
        const SKL_UINT32 lCost = Cost_Base + (Code_Len24[Run-1]<<16);
        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 );
        printf( "\n" );
      }
    }
    else if (51U>(SKL_UINT32)(Level1+25))             // "big" levels (not less than ESC3, though)
    {
      Best_Cost = 0xf0000000;
      const SKL_BYTE *Tbl_L1, *Tbl_L2, *Tbl_L1_Last, *Tbl_L2_Last;
      int Level2;
      int dQ1, dQ2;
      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;