theora-old/lib/encode.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggTheora SOFTWARE CODEC SOURCE CODE.   *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
   5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
   6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
   7  *                                                                  *
   8  * THE Theora SOURCE CODE IS COPYRIGHT (C) 2002-2003                *
   9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13   function:
  14   last mod: $Id$
  15
  16  ********************************************************************/
  17
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include "codec_internal.h"
  21 #include "encoder_lookup.h"
  22 #include "block_inline.h"
  23
  24 #define PUR 8
  25 #define PU 4
  26 #define PUL 2
  27 #define PL 1
  28 #define HIGHBITDUPPED(X) (((ogg_int16_t) X)  >> 15)
  29
  30 static ogg_uint32_t QuadCodeComponent ( CP_INSTANCE *cpi,
  31                                  ogg_uint32_t FirstSB,
  32                                  ogg_uint32_t SBRows,
  33                                  ogg_uint32_t SBCols,
  34                                  ogg_uint32_t PixelsPerLine ){
  35
  36   ogg_int32_t   FragIndex;      /* Fragment number */
  37   ogg_uint32_t  MB, B;          /* Macro-Block, Block indices */
  38   ogg_uint32_t  SBrow;          /* Super-Block row number */
  39   ogg_uint32_t  SBcol;          /* Super-Block row number */
  40   ogg_uint32_t  SB=FirstSB;     /* Super-Block index, initialised to first
  41                                    of this component */
  42   ogg_uint32_t  coded_pixels=0; /* Number of pixels coded */
  43   int           MBCodedFlag;
  44
  45   /* actually transform and quantize the image now that we've decided
  46      on the modes Parse in quad-tree ordering */
  47
  48   SB=FirstSB;
  49   for ( SBrow=0; SBrow<SBRows; SBrow++ ) {
  50     for ( SBcol=0; SBcol<SBCols; SBcol++ ) {
  51       /* Check its four Macro-Blocks  */
  52       for ( MB=0; MB<4; MB++ ) {
  53
  54         if ( QuadMapToMBTopLeft(cpi->pb.BlockMap,SB,MB) >= 0 ) {
  55
  56           MBCodedFlag = 0;
  57
  58           /*  Now actually code the blocks */
  59           for ( B=0; B<4; B++ ) {
  60             FragIndex = QuadMapToIndex1( cpi->pb.BlockMap, SB, MB, B );
  61
  62             /* Does Block lie in frame: */
  63             if ( FragIndex >= 0 ) {
  64               /* In Frame: Is it coded: */
  65               if ( cpi->pb.display_fragments[FragIndex] ) {
  66
  67                 /* transform and quantize block */
  68                 TransformQuantizeBlock( cpi, FragIndex, PixelsPerLine );
  69
  70                 /* Has the block got struck off (no MV and no data
  71                    generated after DCT) If not then mark it and the
  72                    assosciated MB as coded. */
  73                 if ( cpi->pb.display_fragments[FragIndex] ) {
  74                   /* Create linear list of coded block indices */
  75                   cpi->pb.CodedBlockList[cpi->pb.CodedBlockIndex] = FragIndex;
  76                   cpi->pb.CodedBlockIndex++;
  77
  78                   /* MB is still coded */
  79                   MBCodedFlag = 1;
  80                   cpi->MBCodingMode = cpi->pb.FragCodingMethod[FragIndex];
  81
  82                 }
  83               }
  84             }
  85           }
  86           /* If the MB is marked as coded and we are in the Y plane then */
  87           /* the mode list needs to be updated. */
  88           if ( MBCodedFlag && (FirstSB == 0) ){
  89             /* Make a note of the selected mode in the mode list */
  90             cpi->ModeList[cpi->ModeListCount] = cpi->MBCodingMode;
  91             cpi->ModeListCount++;
  92           }
  93         }
  94       }
  95
  96       SB++;
  97
  98     }
  99   }
 100
 101   /* Return number of pixels coded */
 102   return coded_pixels;
 103 }
 104
 105 static void EncodeDcTokenList (CP_INSTANCE *cpi) {
 106   ogg_int32_t   i,j;
 107   ogg_uint32_t  Token;
 108   ogg_uint32_t  ExtraBitsToken;
 109   ogg_uint32_t  HuffIndex;
 110
 111   ogg_uint32_t  BestDcBits;
 112   ogg_uint32_t  DcHuffChoice[2];
 113   ogg_uint32_t  EntropyTableBits[2][DC_HUFF_CHOICES];
 114
 115   oggpack_buffer *opb=cpi->oggbuffer;
 116
 117   /* Clear table data structure */
 118   memset ( EntropyTableBits, 0, sizeof(ogg_uint32_t)*DC_HUFF_CHOICES*2 );
 119
 120   /* Analyse token list to see which is the best entropy table to use */
 121   for ( i = 0; i < cpi->OptimisedTokenCount; i++ ) {
 122     /* Count number of bits for each table option */
 123     Token = (ogg_uint32_t)cpi->OptimisedTokenList[i];
 124     for ( j = 0; j < DC_HUFF_CHOICES; j++ ){
 125       EntropyTableBits[cpi->OptimisedTokenListPl[i]][j] +=
 126         cpi->pb.HuffCodeLengthArray_VP3x[DC_HUFF_OFFSET + j][Token];
 127     }
 128   }
 129
 130   /* Work out which table option is best for Y */
 131   BestDcBits = EntropyTableBits[0][0];
 132   DcHuffChoice[0] = 0;
 133   for ( j = 1; j < DC_HUFF_CHOICES; j++ ) {
 134     if ( EntropyTableBits[0][j] < BestDcBits ) {
 135       BestDcBits = EntropyTableBits[0][j];
 136       DcHuffChoice[0] = j;
 137     }
 138   }
 139
 140   /* Add the DC huffman table choice to the bitstream */
 141   oggpackB_write( opb, DcHuffChoice[0], DC_HUFF_CHOICE_BITS );
 142
 143   /* Work out which table option is best for UV */
 144   BestDcBits = EntropyTableBits[1][0];
 145   DcHuffChoice[1] = 0;
 146   for ( j = 1; j < DC_HUFF_CHOICES; j++ ) {
 147     if ( EntropyTableBits[1][j] < BestDcBits ) {
 148       BestDcBits = EntropyTableBits[1][j];
 149       DcHuffChoice[1] = j;
 150     }
 151   }
 152
 153   /* Add the DC huffman table choice to the bitstream */
 154   oggpackB_write( opb, DcHuffChoice[1], DC_HUFF_CHOICE_BITS );
 155
 156   /* Encode the token list */
 157   for ( i = 0; i < cpi->OptimisedTokenCount; i++ ) {
 158
 159     /* Get the token and extra bits */
 160     Token = (ogg_uint32_t)cpi->OptimisedTokenList[i];
 161     ExtraBitsToken = (ogg_uint32_t)cpi->OptimisedTokenListEb[i];
 162
 163     /* Select the huffman table */
 164     if ( cpi->OptimisedTokenListPl[i] == 0)
 165       HuffIndex = (ogg_uint32_t)DC_HUFF_OFFSET + (ogg_uint32_t)DcHuffChoice[0];
 166     else
 167       HuffIndex = (ogg_uint32_t)DC_HUFF_OFFSET + (ogg_uint32_t)DcHuffChoice[1];
 168
 169     /* Add the bits to the encode holding buffer. */
 170     cpi->FrameBitCount += cpi->pb.HuffCodeLengthArray_VP3x[HuffIndex][Token];
 171     oggpackB_write( opb, cpi->pb.HuffCodeArray_VP3x[HuffIndex][Token],
 172                      (ogg_uint32_t)cpi->
 173                      pb.HuffCodeLengthArray_VP3x[HuffIndex][Token] );
 174
 175     /* If the token is followed by an extra bits token then code it */
 176     if ( cpi->pb.ExtraBitLengths_VP3x[Token] > 0 ) {
 177       /* Add the bits to the encode holding buffer.  */
 178       cpi->FrameBitCount += cpi->pb.ExtraBitLengths_VP3x[Token];
 179       oggpackB_write( opb, ExtraBitsToken,
 180                        (ogg_uint32_t)cpi->pb.ExtraBitLengths_VP3x[Token] );
 181     }
 182   }
 183
 184   /* Reset the count of second order optimised tokens */
 185   cpi->OptimisedTokenCount = 0;
 186 }
 187
 188 static void EncodeAcTokenList (CP_INSTANCE *cpi) {
 189   ogg_int32_t   i,j;
 190   ogg_uint32_t  Token;
 191   ogg_uint32_t  ExtraBitsToken;
 192   ogg_uint32_t  HuffIndex;
 193
 194   ogg_uint32_t  BestAcBits;
 195   ogg_uint32_t  AcHuffChoice[2];
 196   ogg_uint32_t  EntropyTableBits[2][AC_HUFF_CHOICES];
 197
 198   oggpack_buffer *opb=cpi->oggbuffer;
 199
 200   memset ( EntropyTableBits, 0, sizeof(ogg_uint32_t)*AC_HUFF_CHOICES*2 );
 201
 202   /* Analyse token list to see which is the best entropy table to use */
 203   for ( i = 0; i < cpi->OptimisedTokenCount; i++ ) {
 204     /* Count number of bits for each table option */
 205     Token = (ogg_uint32_t)cpi->OptimisedTokenList[i];
 206     HuffIndex = cpi->OptimisedTokenListHi[i];
 207     for ( j = 0; j < AC_HUFF_CHOICES; j++ ) {
 208       EntropyTableBits[cpi->OptimisedTokenListPl[i]][j] +=
 209         cpi->pb.HuffCodeLengthArray_VP3x[HuffIndex + j][Token];
 210     }
 211   }
 212
 213   /* Select the best set of AC tables for Y */
 214   BestAcBits = EntropyTableBits[0][0];
 215   AcHuffChoice[0] = 0;
 216   for ( j = 1; j < AC_HUFF_CHOICES; j++ ) {
 217     if ( EntropyTableBits[0][j] < BestAcBits ) {
 218       BestAcBits = EntropyTableBits[0][j];
 219       AcHuffChoice[0] = j;
 220     }
 221   }
 222
 223   /* Add the AC-Y huffman table choice to the bitstream */
 224   oggpackB_write( opb, AcHuffChoice[0], AC_HUFF_CHOICE_BITS );
 225
 226   /* Select the best set of AC tables for UV */
 227   BestAcBits = EntropyTableBits[1][0];
 228   AcHuffChoice[1] = 0;
 229   for ( j = 1; j < AC_HUFF_CHOICES; j++ ) {
 230     if ( EntropyTableBits[1][j] < BestAcBits ) {
 231       BestAcBits = EntropyTableBits[1][j];
 232       AcHuffChoice[1] = j;
 233     }
 234   }
 235
 236   /* Add the AC-UV huffman table choice to the bitstream */
 237   oggpackB_write( opb, AcHuffChoice[1], AC_HUFF_CHOICE_BITS );
 238
 239   /* Encode the token list */
 240   for ( i = 0; i < cpi->OptimisedTokenCount; i++ ) {
 241     /* Get the token and extra bits */
 242     Token = (ogg_uint32_t)cpi->OptimisedTokenList[i];
 243     ExtraBitsToken = (ogg_uint32_t)cpi->OptimisedTokenListEb[i];
 244
 245     /* Select the huffman table */
 246     HuffIndex = (ogg_uint32_t)cpi->OptimisedTokenListHi[i] +
 247       AcHuffChoice[cpi->OptimisedTokenListPl[i]];
 248
 249     /* Add the bits to the encode holding buffer. */
 250     cpi->FrameBitCount += cpi->pb.HuffCodeLengthArray_VP3x[HuffIndex][Token];
 251     oggpackB_write( opb, cpi->pb.HuffCodeArray_VP3x[HuffIndex][Token],
 252                      (ogg_uint32_t)cpi->
 253                      pb.HuffCodeLengthArray_VP3x[HuffIndex][Token] );
 254
 255     /* If the token is followed by an extra bits token then code it */
 256     if ( cpi->pb.ExtraBitLengths_VP3x[Token] > 0 ) {
 257       /* Add the bits to the encode holding buffer. */
 258       cpi->FrameBitCount += cpi->pb.ExtraBitLengths_VP3x[Token];
 259       oggpackB_write( opb, ExtraBitsToken,
 260                        (ogg_uint32_t)cpi->pb.ExtraBitLengths_VP3x[Token] );
 261     }
 262   }
 263
 264   /* Reset the count of second order optimised tokens */
 265   cpi->OptimisedTokenCount = 0;
 266 }
 267
 268 static void PackModes (CP_INSTANCE *cpi) {
 269   ogg_uint32_t    i,j;
 270   unsigned char   ModeIndex;
 271   unsigned char  *SchemeList;
 272
 273   unsigned char   BestModeSchemes[MAX_MODES];
 274   ogg_int32_t     ModeCount[MAX_MODES];
 275   ogg_int32_t     TmpFreq = -1;
 276   ogg_int32_t     TmpIndex = -1;
 277
 278   ogg_uint32_t    BestScheme;
 279   ogg_uint32_t    BestSchemeScore;
 280   ogg_uint32_t    SchemeScore;
 281
 282   oggpack_buffer *opb=cpi->oggbuffer;
 283
 284   /* Build a frequency map for the modes in this frame */
 285   memset( ModeCount, 0, MAX_MODES*sizeof(ogg_int32_t) );
 286   for ( i = 0; i < cpi->ModeListCount; i++ )
 287     ModeCount[cpi->ModeList[i]] ++;
 288
 289   /* Order the modes from most to least frequent.  Store result as
 290      scheme 0 */
 291   for ( j = 0; j < MAX_MODES; j++ ) {
 292     TmpFreq = -1;  /* need to re-initialize for each loop */
 293     /* Find the most frequent */
 294     for ( i = 0; i < MAX_MODES; i++ ) {
 295       /* Is this the best scheme so far ??? */
 296       if ( ModeCount[i] > TmpFreq ) {
 297         TmpFreq = ModeCount[i];
 298         TmpIndex = i;
 299       }
 300     }
 301     /* I don't know if the above loop ever fails to match, but it's
 302        better safe than sorry.  Plus this takes care of gcc warning */
 303     if ( TmpIndex != -1 ) {
 304       ModeCount[TmpIndex] = -1;
 305       BestModeSchemes[TmpIndex] = (unsigned char)j;
 306     }
 307   }
 308
 309   /* Default/ fallback scheme uses MODE_BITS bits per mode entry */
 310   BestScheme = (MODE_METHODS - 1);
 311   BestSchemeScore = cpi->ModeListCount * 3;
 312   /* Get a bit score for the available schemes. */
 313   for (  j = 0; j < (MODE_METHODS - 1); j++ ) {
 314
 315     /* Reset the scheme score */
 316     if ( j == 0 ){
 317       /* Scheme 0 additional cost of sending frequency order */
 318       SchemeScore = 24;
 319       SchemeList = BestModeSchemes;
 320     } else {
 321       SchemeScore = 0;
 322       SchemeList = ModeSchemes[j-1];
 323     }
 324
 325     /* Find the total bits to code using each avaialable scheme */
 326     for ( i = 0; i < cpi->ModeListCount; i++ )
 327       SchemeScore += ModeBitLengths[SchemeList[cpi->ModeList[i]]];
 328
 329     /* Is this the best scheme so far ??? */
 330     if ( SchemeScore < BestSchemeScore ) {
 331       BestSchemeScore = SchemeScore;
 332       BestScheme = j;
 333     }
 334   }
 335
 336   /* Encode the best scheme. */
 337   oggpackB_write( opb, BestScheme, (ogg_uint32_t)MODE_METHOD_BITS );
 338
 339   /* If the chosen schems is scheme 0 send details of the mode
 340      frequency order */
 341   if ( BestScheme == 0 ) {
 342     for ( j = 0; j < MAX_MODES; j++ )
 343       /* Note that the last two entries are implicit */
 344       oggpackB_write( opb, BestModeSchemes[j], (ogg_uint32_t)MODE_BITS );
 345     SchemeList = BestModeSchemes;
 346   }
 347   else {
 348     SchemeList = ModeSchemes[BestScheme-1];
 349   }
 350
 351   /* Are we using one of the alphabet based schemes or the fallback scheme */
 352   if ( BestScheme < (MODE_METHODS - 1)) {
 353     /* Pack and encode the Mode list */
 354     for ( i = 0; i < cpi->ModeListCount; i++ ) {
 355       /* Add the appropriate mode entropy token. */
 356       ModeIndex = SchemeList[cpi->ModeList[i]];
 357       oggpackB_write( opb, ModeBitPatterns[ModeIndex],
 358                        (ogg_uint32_t)ModeBitLengths[ModeIndex] );
 359     }
 360   }else{
 361     /* Fall back to MODE_BITS per entry */
 362     for ( i = 0; i < cpi->ModeListCount; i++ ) {
 363       /* Add the appropriate mode entropy token. */
 364       oggpackB_write( opb, cpi->ModeList[i], MODE_BITS  );
 365     }
 366   }
 367 }
 368
 369 static void PackMotionVectors (CP_INSTANCE *cpi) {
 370   ogg_int32_t  i;
 371   ogg_uint32_t MethodBits[2] = {0,0};
 372   ogg_uint32_t * MvBitsPtr;
 373   ogg_uint32_t * MvPatternPtr;
 374
 375   oggpack_buffer *opb=cpi->oggbuffer;
 376
 377   /* Choose the coding method */
 378   MvBitsPtr = &MvBits[MAX_MV_EXTENT];
 379   for ( i = 0; i < (ogg_int32_t)cpi->MvListCount; i++ ) {
 380     MethodBits[0] += MvBitsPtr[cpi->MVList[i].x];
 381     MethodBits[0] += MvBitsPtr[cpi->MVList[i].y];
 382     MethodBits[1] += 12; /* Simple six bits per mv component fallback
 383                              mechanism */
 384   }
 385
 386   /* Select entropy table */
 387   if ( MethodBits[0] < MethodBits[1] ) {
 388     oggpackB_write( opb, 0, 1 );
 389     MvBitsPtr = &MvBits[MAX_MV_EXTENT];
 390     MvPatternPtr = &MvPattern[MAX_MV_EXTENT];
 391   }else{
 392     oggpackB_write( opb, 1, 1 );
 393     MvBitsPtr = &MvBits2[MAX_MV_EXTENT];
 394     MvPatternPtr = &MvPattern2[MAX_MV_EXTENT];
 395   }
 396
 397   /* Pack and encode the motion vectors */
 398   for ( i = 0; i < (ogg_int32_t)cpi->MvListCount; i++ ) {
 399     oggpackB_write( opb, MvPatternPtr[cpi->MVList[i].x],
 400                      (ogg_uint32_t)MvBitsPtr[cpi->MVList[i].x] );
 401     oggpackB_write( opb, MvPatternPtr[cpi->MVList[i].y],
 402                      (ogg_uint32_t)MvBitsPtr[cpi->MVList[i].y] );
 403   }
 404 }
 405
 406 static void PackEOBRun( CP_INSTANCE *cpi) {
 407   if(cpi->RunLength == 0)
 408         return;
 409
 410   /* Note the appropriate EOB or EOB run token and any extra bits in
 411      the optimised token list.  Use the huffman index assosciated with
 412      the first token in the run */
 413
 414   /* Mark out which plane the block belonged to */
 415   cpi->OptimisedTokenListPl[cpi->OptimisedTokenCount] =
 416     (unsigned char)cpi->RunPlaneIndex;
 417
 418   /* Note the huffman index to be used */
 419   cpi->OptimisedTokenListHi[cpi->OptimisedTokenCount] =
 420     (unsigned char)cpi->RunHuffIndex;
 421
 422   if ( cpi->RunLength <= 3 ) {
 423     if ( cpi->RunLength == 1 ) {
 424       cpi->OptimisedTokenList[cpi->OptimisedTokenCount] = DCT_EOB_TOKEN;
 425     } else if ( cpi->RunLength == 2 ) {
 426       cpi->OptimisedTokenList[cpi->OptimisedTokenCount] = DCT_EOB_PAIR_TOKEN;
 427     } else {
 428       cpi->OptimisedTokenList[cpi->OptimisedTokenCount] = DCT_EOB_TRIPLE_TOKEN;
 429     }
 430
 431     cpi->RunLength = 0;
 432
 433   } else {
 434
 435     /* Choose a token appropriate to the run length. */
 436     if ( cpi->RunLength < 8 ) {
 437       cpi->OptimisedTokenList[cpi->OptimisedTokenCount] =
 438         DCT_REPEAT_RUN_TOKEN;
 439       cpi->OptimisedTokenListEb[cpi->OptimisedTokenCount] =
 440         cpi->RunLength - 4;
 441       cpi->RunLength = 0;
 442     } else if ( cpi->RunLength < 16 ) {
 443       cpi->OptimisedTokenList[cpi->OptimisedTokenCount] =
 444         DCT_REPEAT_RUN2_TOKEN;
 445       cpi->OptimisedTokenListEb[cpi->OptimisedTokenCount] =
 446         cpi->RunLength - 8;
 447       cpi->RunLength = 0;
 448     } else if ( cpi->RunLength < 32 ) {
 449       cpi->OptimisedTokenList[cpi->OptimisedTokenCount] =
 450         DCT_REPEAT_RUN3_TOKEN;
 451       cpi->OptimisedTokenListEb[cpi->OptimisedTokenCount] =
 452         cpi->RunLength - 16;
 453       cpi->RunLength = 0;
 454     } else if ( cpi->RunLength < 4096) {
 455       cpi->OptimisedTokenList[cpi->OptimisedTokenCount] =
 456         DCT_REPEAT_RUN4_TOKEN;
 457       cpi->OptimisedTokenListEb[cpi->OptimisedTokenCount] =
 458         cpi->RunLength;
 459       cpi->RunLength = 0;
 460     }
 461
 462   }
 463
 464   cpi->OptimisedTokenCount++;
 465   /* Reset run EOB length */
 466   cpi->RunLength = 0;
 467 }
 468
 469 static void PackToken ( CP_INSTANCE *cpi, ogg_int32_t FragmentNumber,
 470                  ogg_uint32_t HuffIndex ) {
 471   ogg_uint32_t Token =
 472     cpi->pb.TokenList[FragmentNumber][cpi->FragTokens[FragmentNumber]];
 473   ogg_uint32_t ExtraBitsToken =
 474     cpi->pb.TokenList[FragmentNumber][cpi->FragTokens[FragmentNumber] + 1];
 475   ogg_uint32_t OneOrTwo;
 476   ogg_uint32_t OneOrZero;
 477
 478   /* Update the record of what coefficient we have got up to for this
 479      block and unpack the encoded token back into the quantised data
 480      array. */
 481   if ( Token == DCT_EOB_TOKEN )
 482     cpi->pb.FragCoeffs[FragmentNumber] = BLOCK_SIZE;
 483   else
 484     ExpandToken( cpi->pb.QFragData[FragmentNumber],
 485                  &cpi->pb.FragCoeffs[FragmentNumber],
 486                  Token, ExtraBitsToken );
 487
 488   /* Update record of tokens coded and where we are in this fragment. */
 489   /* Is there an extra bits token */
 490   OneOrTwo= 1 + ( cpi->pb.ExtraBitLengths_VP3x[Token] > 0 );
 491   /* Advance to the next real token. */
 492   cpi->FragTokens[FragmentNumber] += (unsigned char)OneOrTwo;
 493
 494   /* Update the counts of tokens coded */
 495   cpi->TokensCoded += OneOrTwo;
 496   cpi->TokensToBeCoded -= OneOrTwo;
 497
 498   OneOrZero = ( FragmentNumber < (ogg_int32_t)cpi->pb.YPlaneFragments );
 499
 500   if ( Token == DCT_EOB_TOKEN ) {
 501     if ( cpi->RunLength == 0 ) {
 502       cpi->RunHuffIndex = HuffIndex;
 503       cpi->RunPlaneIndex = 1 -  OneOrZero;
 504     }
 505     cpi->RunLength++;
 506
 507     /* we have exceeded our longest run length  xmit an eob run token; */
 508     if ( cpi->RunLength == 4095 ) PackEOBRun(cpi);
 509
 510   }else{
 511
 512     /* If we have an EOB run then code it up first */
 513     if ( cpi->RunLength > 0 ) PackEOBRun( cpi);
 514
 515     /* Mark out which plane the block belonged to */
 516     cpi->OptimisedTokenListPl[cpi->OptimisedTokenCount] =
 517       (unsigned char)(1 - OneOrZero);
 518
 519     /* Note the token, extra bits and hufman table in the optimised
 520        token list */
 521     cpi->OptimisedTokenList[cpi->OptimisedTokenCount] =
 522       (unsigned char)Token;
 523     cpi->OptimisedTokenListEb[cpi->OptimisedTokenCount] =
 524       ExtraBitsToken;
 525     cpi->OptimisedTokenListHi[cpi->OptimisedTokenCount] =
 526       (unsigned char)HuffIndex;
 527
 528     cpi->OptimisedTokenCount++;
 529   }
 530 }
 531
 532 static ogg_uint32_t GetBlockReconErrorSlow( CP_INSTANCE *cpi,
 533                                      ogg_int32_t BlockIndex ) {
 534   ogg_uint32_t  ErrorVal;
 535
 536   unsigned char * SrcDataPtr =
 537     &cpi->ConvDestBuffer[cpi->pb.pixel_index_table[BlockIndex]];
 538   unsigned char * RecDataPtr =
 539     &cpi->pb.LastFrameRecon[cpi->pb.recon_pixel_index_table[BlockIndex]];
 540   ogg_int32_t   SrcStride;
 541   ogg_int32_t   RecStride;
 542
 543   /* Is the block a Y block or a UV block. */
 544   if ( BlockIndex < (ogg_int32_t)cpi->pb.YPlaneFragments ) {
 545     SrcStride = cpi->pb.info.width;
 546     RecStride = cpi->pb.YStride;
 547   }else{
 548     SrcStride = cpi->pb.info.width >> 1;
 549     RecStride = cpi->pb.UVStride;
 550   }
 551
 552   ErrorVal = dsp_sad8x8 (cpi->dsp, SrcDataPtr, SrcStride, RecDataPtr, RecStride);
 553
 554   return ErrorVal;
 555 }
 556
 557 static void PackCodedVideo (CP_INSTANCE *cpi) {
 558   ogg_int32_t i;
 559   ogg_int32_t EncodedCoeffs = 1;
 560   ogg_int32_t FragIndex;
 561   ogg_uint32_t HuffIndex; /* Index to group of tables used to code a token */
 562
 563   /* Reset the count of second order optimised tokens */
 564   cpi->OptimisedTokenCount = 0;
 565
 566   cpi->TokensToBeCoded = cpi->TotTokenCount;
 567   cpi->TokensCoded = 0;
 568
 569   /* Calculate the bit rate at which this frame should be capped. */
 570   cpi->MaxBitTarget = (ogg_uint32_t)((double)(cpi->ThisFrameTargetBytes * 8) *
 571                                      cpi->BitRateCapFactor);
 572
 573   /* Blank the various fragment data structures before we start. */
 574   memset(cpi->pb.FragCoeffs, 0, cpi->pb.UnitFragments);
 575   memset(cpi->FragTokens, 0, cpi->pb.UnitFragments);
 576
 577   /* Clear down the QFragData structure for all coded blocks. */
 578   ClearDownQFragData(&cpi->pb);
 579
 580   /* The tree is not needed (implicit) for key frames */
 581   if ( GetFrameType(&cpi->pb) != KEY_FRAME ){
 582     /* Pack the quad tree fragment mapping. */
 583     PackAndWriteDFArray( cpi );
 584   }
 585
 586   /* Note the number of bits used to code the tree itself. */
 587   cpi->FrameBitCount = oggpackB_bytes(cpi->oggbuffer) << 3;
 588
 589   /* Mode and MV data not needed for key frames. */
 590   if ( GetFrameType(&cpi->pb) != KEY_FRAME ){
 591     /* Pack and code the mode list. */
 592     PackModes(cpi);
 593     /* Pack the motion vectors */
 594     PackMotionVectors (cpi);
 595   }
 596
 597   cpi->FrameBitCount = oggpackB_bytes(cpi->oggbuffer) << 3;
 598
 599   /* Optimise the DC tokens */
 600   for ( i = 0; i < cpi->pb.CodedBlockIndex; i++ ) {
 601     /* Get the linear index for the current fragment. */
 602     FragIndex = cpi->pb.CodedBlockList[i];
 603
 604     cpi->pb.FragCoefEOB[FragIndex]=(unsigned char)EncodedCoeffs;
 605     PackToken(cpi, FragIndex, DC_HUFF_OFFSET );
 606
 607   }
 608
 609   /* Pack any outstanding EOB tokens */
 610   PackEOBRun(cpi);
 611
 612   /* Now output the optimised DC token list using the appropriate
 613      entropy tables. */
 614   EncodeDcTokenList(cpi);
 615
 616   /* Work out the number of DC bits coded */
 617
 618   /* Optimise the AC tokens */
 619   while ( EncodedCoeffs < 64 ) {
 620     /* Huffman table adjustment based upon coefficient number. */
 621     if ( EncodedCoeffs <= AC_TABLE_2_THRESH )
 622       HuffIndex = AC_HUFF_OFFSET;
 623     else if ( EncodedCoeffs <= AC_TABLE_3_THRESH )
 624       HuffIndex = AC_HUFF_OFFSET + AC_HUFF_CHOICES;
 625     else if ( EncodedCoeffs <= AC_TABLE_4_THRESH )
 626       HuffIndex = AC_HUFF_OFFSET + (AC_HUFF_CHOICES * 2);
 627     else
 628       HuffIndex = AC_HUFF_OFFSET + (AC_HUFF_CHOICES * 3);
 629
 630     /* Repeatedly scan through the list of blocks. */
 631     for ( i = 0; i < cpi->pb.CodedBlockIndex; i++ ) {
 632       /* Get the linear index for the current fragment. */
 633       FragIndex = cpi->pb.CodedBlockList[i];
 634
 635       /* Should we code a token for this block on this pass. */
 636       if ( cpi->FragTokens[FragIndex] < cpi->FragTokenCounts[FragIndex]
 637            && cpi->pb.FragCoeffs[FragIndex] <= EncodedCoeffs ) {
 638         /* Bit pack and a token for this block */
 639         cpi->pb.FragCoefEOB[FragIndex]=(unsigned char)EncodedCoeffs;
 640         PackToken( cpi, FragIndex, HuffIndex );
 641       }
 642     }
 643
 644     EncodedCoeffs ++;
 645   }
 646
 647   /* Pack any outstanding EOB tokens */
 648   PackEOBRun(cpi);
 649
 650   /* Now output the optimised AC token list using the appropriate
 651      entropy tables. */
 652   EncodeAcTokenList(cpi);
 653
 654 }
 655
 656 static ogg_uint32_t QuadCodeDisplayFragments (CP_INSTANCE *cpi) {
 657   ogg_int32_t   i,j;
 658   ogg_uint32_t  coded_pixels=0;
 659   int           QIndex;
 660   int k,m,n;
 661
 662   /* predictor multiplier up-left, up, up-right,left, shift
 663      Entries are packed in the order L, UL, U, UR, with missing entries
 664       moved to the end (before the shift parameters). */
 665   static const ogg_int16_t pc[16][6]={
 666     {0,0,0,0,0,0},
 667     {1,0,0,0,0,0},      /* PL */
 668     {1,0,0,0,0,0},      /* PUL */
 669     {1,0,0,0,0,0},      /* PUL|PL */
 670     {1,0,0,0,0,0},      /* PU */
 671     {1,1,0,0,1,1},      /* PU|PL */
 672     {0,1,0,0,0,0},      /* PU|PUL */
 673     {29,-26,29,0,5,31}, /* PU|PUL|PL */
 674     {1,0,0,0,0,0},      /* PUR */
 675     {75,53,0,0,7,127},  /* PUR|PL */
 676     {1,1,0,0,1,1},      /* PUR|PUL */
 677     {75,0,53,0,7,127},  /* PUR|PUL|PL */
 678     {1,0,0,0,0,0},      /* PUR|PU */
 679     {75,0,53,0,7,127},  /* PUR|PU|PL */
 680     {3,10,3,0,4,15},    /* PUR|PU|PUL */
 681     {29,-26,29,0,5,31}  /* PUR|PU|PUL|PL */
 682   };
 683
 684   /* boundary case bit masks. */
 685   static const int bc_mask[8]={
 686     /* normal case no boundary condition */
 687     PUR|PU|PUL|PL,
 688     /* left column */
 689     PUR|PU,
 690     /* top row */
 691     PL,
 692     /* top row, left column */
 693     0,
 694     /* right column */
 695     PU|PUL|PL,
 696     /* right and left column */
 697     PU,
 698     /* top row, right column */
 699     PL,
 700     /* top row, right and left column */
 701     0
 702   };
 703
 704   /* value left value up-left, value up, value up-right, missing
 705       values skipped. */
 706   int v[4];
 707
 708   /* fragment number left, up-left, up, up-right */
 709   int fn[4];
 710
 711   /* predictor count. */
 712   int pcount;
 713
 714   /*which predictor constants to use */
 715   ogg_int16_t wpc;
 716
 717   /* last used inter predictor (Raster Order) */
 718   ogg_int16_t Last[3];  /* last value used for given frame */
 719
 720   int FragsAcross=cpi->pb.HFragments;
 721   int FragsDown = cpi->pb.VFragments;
 722   int FromFragment,ToFragment;
 723   ogg_int32_t   FragIndex;
 724   int WhichFrame;
 725   int WhichCase;
 726
 727   static const ogg_int16_t Mode2Frame[] = {
 728     1,  /* CODE_INTER_NO_MV     0 => Encoded diff from same MB last frame  */
 729     0,  /* CODE_INTRA           1 => DCT Encoded Block */
 730     1,  /* CODE_INTER_PLUS_MV   2 => Encoded diff from included MV MB last frame */
 731     1,  /* CODE_INTER_LAST_MV   3 => Encoded diff from MRU MV MB last frame */
 732     1,  /* CODE_INTER_PRIOR_MV  4 => Encoded diff from included 4 separate MV blocks */
 733     2,  /* CODE_USING_GOLDEN    5 => Encoded diff from same MB golden frame */
 734     2,  /* CODE_GOLDEN_MV       6 => Encoded diff from included MV MB golden frame */
 735     1   /* CODE_INTER_FOUR_MV   7 => Encoded diff from included 4 separate MV blocks */
 736   };
 737
 738   ogg_int16_t PredictedDC;
 739
 740   /* Initialise the coded block indices variables. These allow
 741      subsequent linear access to the quad tree ordered list of coded
 742      blocks */
 743   cpi->pb.CodedBlockIndex = 0;
 744
 745   /* Set the inter/intra descision control variables. */
 746   QIndex = Q_TABLE_SIZE - 1;
 747   while ( QIndex >= 0 ) {
 748     if ( (QIndex == 0) ||
 749          ( cpi->pb.QThreshTable[QIndex] >= cpi->pb.ThisFrameQualityValue) )
 750       break;
 751     QIndex --;
 752   }
 753
 754
 755   /* Encode and tokenise the Y, U and V components */
 756   coded_pixels = QuadCodeComponent(cpi, 0, cpi->pb.YSBRows, cpi->pb.YSBCols,
 757                                    cpi->pb.info.width );
 758   coded_pixels += QuadCodeComponent(cpi, cpi->pb.YSuperBlocks,
 759                                     cpi->pb.UVSBRows,
 760                                     cpi->pb.UVSBCols,
 761                                     cpi->pb.info.width>>1 );
 762   coded_pixels += QuadCodeComponent(cpi,
 763                                     cpi->pb.YSuperBlocks+cpi->pb.UVSuperBlocks,
 764                                     cpi->pb.UVSBRows, cpi->pb.UVSBCols,
 765                                     cpi->pb.info.width>>1 );
 766
 767   /* for y,u,v */
 768   for ( j = 0; j < 3 ; j++) {
 769     /* pick which fragments based on Y, U, V */
 770     switch(j){
 771     case 0: /* y */
 772       FromFragment = 0;
 773       ToFragment = cpi->pb.YPlaneFragments;
 774       FragsAcross = cpi->pb.HFragments;
 775       FragsDown = cpi->pb.VFragments;
 776       break;
 777     case 1: /* u */
 778       FromFragment = cpi->pb.YPlaneFragments;
 779       ToFragment = cpi->pb.YPlaneFragments + cpi->pb.UVPlaneFragments ;
 780       FragsAcross = cpi->pb.HFragments >> 1;
 781       FragsDown = cpi->pb.VFragments >> 1;
 782       break;
 783     /*case 2:  v */
 784     default:
 785       FromFragment = cpi->pb.YPlaneFragments + cpi->pb.UVPlaneFragments;
 786       ToFragment = cpi->pb.YPlaneFragments + (2 * cpi->pb.UVPlaneFragments) ;
 787       FragsAcross = cpi->pb.HFragments >> 1;
 788       FragsDown = cpi->pb.VFragments >> 1;
 789       break;
 790     }
 791
 792     /* initialize our array of last used DC Components */
 793     for(k=0;k<3;k++)Last[k]=0;
 794     i=FromFragment;
 795
 796     /* do prediction on all of Y, U or V */
 797     for ( m = 0 ; m < FragsDown ; m++) {
 798       for ( n = 0 ; n < FragsAcross ; n++, i++) {
 799         cpi->OriginalDC[i] = cpi->pb.QFragData[i][0];
 800
 801         /* only do 2 prediction if fragment coded and on non intra or
 802            if all fragments are intra */
 803         if( cpi->pb.display_fragments[i] ||
 804             (GetFrameType(&cpi->pb) == KEY_FRAME) ) {
 805           /* Type of Fragment */
 806           WhichFrame = Mode2Frame[cpi->pb.FragCodingMethod[i]];
 807
 808           /* Check Borderline Cases */
 809           WhichCase = (n==0) + ((m==0) << 1) + ((n+1 == FragsAcross) << 2);
 810
 811           fn[0]=i-1;
 812           fn[1]=i-FragsAcross-1;
 813           fn[2]=i-FragsAcross;
 814           fn[3]=i-FragsAcross+1;
 815
 816           /* fragment valid for prediction use if coded and it comes
 817              from same frame as the one we are predicting */
 818           for(k=pcount=wpc=0; k<4; k++) {
 819             int pflag;
 820             pflag=1<<k;
 821             if((bc_mask[WhichCase]&pflag) &&
 822                cpi->pb.display_fragments[fn[k]] &&
 823                (Mode2Frame[cpi->pb.FragCodingMethod[fn[k]]] == WhichFrame)){
 824               v[pcount]=cpi->OriginalDC[fn[k]];
 825               wpc|=pflag;
 826               pcount++;
 827             }
 828           }
 829
 830           if(wpc==0) {
 831
 832             /* fall back to the last coded fragment */
 833             cpi->pb.QFragData[i][0] -= Last[WhichFrame];
 834
 835           } else {
 836
 837             /* don't do divide if divisor is 1 or 0 */
 838             PredictedDC = pc[wpc][0]*v[0];
 839             for(k=1; k<pcount; k++){
 840               PredictedDC += pc[wpc][k]*v[k];
 841             }
 842
 843             /* if we need to do a shift */
 844             if(pc[wpc][4] != 0 ) {
 845
 846               /* If negative add in the negative correction factor */
 847               PredictedDC += (HIGHBITDUPPED(PredictedDC) & pc[wpc][5]);
 848               /* Shift in lieu of a divide */
 849               PredictedDC >>= pc[wpc][4];
 850
 851             }
 852
 853             /* check for outranging on the two predictors that can outrange */
 854             if((wpc&(PU|PUL|PL)) == (PU|PUL|PL)){
 855               if( abs(PredictedDC - v[2]) > 128) {
 856                 PredictedDC = v[2];
 857               } else if( abs(PredictedDC - v[0]) > 128) {
 858                 PredictedDC = v[0];
 859               } else if( abs(PredictedDC - v[1]) > 128) {
 860                 PredictedDC = v[1];
 861               }
 862             }
 863
 864             cpi->pb.QFragData[i][0] -= PredictedDC;
 865           }
 866
 867           /* Save the last fragment coded for whatever frame we are
 868              predicting from */
 869
 870           Last[WhichFrame] = cpi->OriginalDC[i];
 871
 872         }
 873       }
 874     }
 875   }
 876
 877   /* Pack DC tokens and adjust the ones we couldn't predict 2d */
 878   for ( i = 0; i < cpi->pb.CodedBlockIndex; i++ ) {
 879     /* Get the linear index for the current coded fragment. */
 880     FragIndex = cpi->pb.CodedBlockList[i];
 881     coded_pixels += DPCMTokenizeBlock ( cpi, FragIndex);
 882
 883   }
 884
 885
 886   /* Bit pack the video data data */
 887   PackCodedVideo(cpi);
 888
 889   /* End the bit packing run. */
 890   /* EndAddBitsToBuffer(cpi); */
 891
 892   /* Reconstruct the reference frames */
 893   ReconRefFrames(&cpi->pb);
 894
 895   UpdateFragQIndex(&cpi->pb);
 896
 897   /* Measure the inter reconstruction error for all the blocks that
 898      were coded */
 899   /* for use as part of the recovery monitoring process in subsequent frames. */
 900   for ( i = 0; i < cpi->pb.CodedBlockIndex; i++ ) {
 901     cpi->LastCodedErrorScore[ cpi->pb.CodedBlockList[i] ] =
 902       GetBlockReconErrorSlow( cpi, cpi->pb.CodedBlockList[i] );
 903
 904   }
 905
 906   /* Return total number of coded pixels */
 907   return coded_pixels;
 908 }
 909
 910 ogg_uint32_t EncodeData(CP_INSTANCE *cpi){
 911     ogg_uint32_t coded_pixels = 0;
 912
 913     /* Zero the count of tokens so far this frame. */
 914     cpi->TotTokenCount = 0;
 915
 916     /* Zero the mode and MV list indices. */
 917     cpi->ModeListCount = 0;
 918
 919     /* Zero Decoder EOB run count */
 920     cpi->pb.EOB_Run = 0;
 921
 922     dsp_save_fpu (cpi->dsp);
 923
 924     /* Encode any fragments coded using DCT. */
 925     coded_pixels += QuadCodeDisplayFragments (cpi);
 926
 927     dsp_restore_fpu (cpi->dsp);
 928
 929     return coded_pixels;
 930
 931 }
 932
 933 ogg_uint32_t PickIntra( CP_INSTANCE *cpi,
 934                         ogg_uint32_t SBRows,
 935                         ogg_uint32_t SBCols){
 936
 937   ogg_int32_t   FragIndex;  /* Fragment number */
 938   ogg_uint32_t  MB, B;      /* Macro-Block, Block indices */
 939   ogg_uint32_t  SBrow;      /* Super-Block row number */
 940   ogg_uint32_t  SBcol;      /* Super-Block row number */
 941   ogg_uint32_t  SB=0;       /* Super-Block index, initialised to first of
 942                                this component */
 943
 944   ogg_uint32_t UVRow;
 945   ogg_uint32_t UVColumn;
 946   ogg_uint32_t UVFragOffset;
 947
 948   /* decide what block type and motion vectors to use on all of the frames */
 949   for ( SBrow=0; SBrow<SBRows; SBrow++ ) {
 950     for ( SBcol=0; SBcol<SBCols; SBcol++ ) {
 951       /* Check its four Macro-Blocks */
 952       for ( MB=0; MB<4; MB++ ) {
 953         /* There may be MB's lying out of frame which must be
 954            ignored. For these MB's Top left block will have a negative
 955            Fragment Index. */
 956         if ( QuadMapToMBTopLeft(cpi->pb.BlockMap,SB,MB) >= 0 ) {
 957
 958           cpi->MBCodingMode = CODE_INTRA;
 959
 960           /* Now actually code the blocks. */
 961           for ( B=0; B<4; B++ ) {
 962             FragIndex = QuadMapToIndex1( cpi->pb.BlockMap, SB, MB, B );
 963             cpi->pb.FragCodingMethod[FragIndex] = cpi->MBCodingMode;
 964           }
 965
 966           /* Matching fragments in the U and V planes */
 967           UVRow = (FragIndex / (cpi->pb.HFragments * 2));
 968           UVColumn = (FragIndex % cpi->pb.HFragments) / 2;
 969           UVFragOffset = (UVRow * (cpi->pb.HFragments / 2)) + UVColumn;
 970
 971           cpi->pb.FragCodingMethod[cpi->pb.YPlaneFragments + UVFragOffset] =
 972             cpi->MBCodingMode;
 973           cpi->pb.FragCodingMethod[cpi->pb.YPlaneFragments +
 974                                   cpi->pb.UVPlaneFragments + UVFragOffset] =
 975             cpi->MBCodingMode;
 976
 977         }
 978       }
 979
 980       /* Next Super-Block */
 981       SB++;
 982     }
 983   }
 984   return 0;
 985 }
 986
 987 static void AddMotionVector(CP_INSTANCE *cpi,
 988                      MOTION_VECTOR *ThisMotionVector) {
 989   cpi->MVList[cpi->MvListCount].x = ThisMotionVector->x;
 990   cpi->MVList[cpi->MvListCount].y = ThisMotionVector->y;
 991   cpi->MvListCount++;
 992 }
 993
 994 static void SetFragMotionVectorAndMode(CP_INSTANCE *cpi,
 995                                 ogg_int32_t FragIndex,
 996                                 MOTION_VECTOR *ThisMotionVector){
 997   /* Note the coding mode and vector for each block */
 998   cpi->pb.FragMVect[FragIndex].x = ThisMotionVector->x;
 999   cpi->pb.FragMVect[FragIndex].y = ThisMotionVector->y;
1000   cpi->pb.FragCodingMethod[FragIndex] = cpi->MBCodingMode;
1001 }
1002
1003 static void SetMBMotionVectorsAndMode(CP_INSTANCE *cpi,
1004                                ogg_int32_t YFragIndex,
1005                                ogg_int32_t UFragIndex,
1006                                ogg_int32_t VFragIndex,
1007                                MOTION_VECTOR *ThisMotionVector){
1008   SetFragMotionVectorAndMode(cpi, YFragIndex, ThisMotionVector);
1009   SetFragMotionVectorAndMode(cpi, YFragIndex + 1, ThisMotionVector);
1010   SetFragMotionVectorAndMode(cpi, YFragIndex + cpi->pb.HFragments,
1011                              ThisMotionVector);
1012   SetFragMotionVectorAndMode(cpi, YFragIndex + cpi->pb.HFragments + 1,
1013                              ThisMotionVector);
1014   SetFragMotionVectorAndMode(cpi, UFragIndex, ThisMotionVector);
1015   SetFragMotionVectorAndMode(cpi, VFragIndex, ThisMotionVector);
1016 }
1017
1018 ogg_uint32_t PickModes(CP_INSTANCE *cpi,
1019                        ogg_uint32_t SBRows, ogg_uint32_t SBCols,
1020                        ogg_uint32_t PixelsPerLine,
1021                        ogg_uint32_t *InterError, ogg_uint32_t *IntraError) {
1022   ogg_int32_t   YFragIndex;
1023   ogg_int32_t   UFragIndex;
1024   ogg_int32_t   VFragIndex;
1025   ogg_uint32_t  MB, B;      /* Macro-Block, Block indices */
1026   ogg_uint32_t  SBrow;      /* Super-Block row number */
1027   ogg_uint32_t  SBcol;      /* Super-Block row number */
1028   ogg_uint32_t  SB=0;       /* Super-Block index, initialised to first
1029                                of this component */
1030
1031   ogg_uint32_t  MBIntraError;           /* Intra error for macro block */
1032   ogg_uint32_t  MBGFError;              /* Golden frame macro block error */
1033   ogg_uint32_t  MBGF_MVError;           /* Golden frame plus MV error */
1034   ogg_uint32_t  LastMBGF_MVError;       /* Golden frame error with
1035                                            last used GF motion
1036                                            vector. */
1037   ogg_uint32_t  MBInterError;           /* Inter no MV macro block error */
1038   ogg_uint32_t  MBLastInterError;       /* Inter with last used MV */
1039   ogg_uint32_t  MBPriorLastInterError;  /* Inter with prior last MV */
1040   ogg_uint32_t  MBInterMVError;         /* Inter MV macro block error */
1041   ogg_uint32_t  MBInterMVExError;       /* Inter MV (exhaustive
1042                                            search) macro block error */
1043   ogg_uint32_t  MBInterFOURMVError;     /* Inter MV error when using 4
1044                                            motion vectors per macro
1045                                            block */
1046   ogg_uint32_t  BestError;              /* Best error so far. */
1047
1048   MOTION_VECTOR FourMVect[6];     /* storage for last used vectors (one
1049                                      entry for each block in MB) */
1050   MOTION_VECTOR LastInterMVect;   /* storage for last used Inter frame
1051                                      MB motion vector */
1052   MOTION_VECTOR PriorLastInterMVect;  /* storage for prior last used
1053                                          Inter frame MB motion vector */
1054   MOTION_VECTOR TmpMVect;         /* Temporary MV storage */
1055   MOTION_VECTOR LastGFMVect;      /* storage for last used Golden
1056                                      Frame MB motion vector */
1057   MOTION_VECTOR InterMVect;       /* storage for motion vector */
1058   MOTION_VECTOR InterMVectEx;     /* storage for motion vector result
1059                                      from exhaustive search */
1060   MOTION_VECTOR GFMVect;          /* storage for motion vector */
1061   MOTION_VECTOR ZeroVect;
1062
1063   ogg_uint32_t UVRow;
1064   ogg_uint32_t UVColumn;
1065   ogg_uint32_t UVFragOffset;
1066
1067   int          MBCodedFlag;
1068   unsigned char QIndex;
1069
1070   /* initialize error scores */
1071   *InterError = 0;
1072   *IntraError = 0;
1073
1074   /* clear down the default motion vector. */
1075   cpi->MvListCount = 0;
1076   FourMVect[0].x = 0;
1077   FourMVect[0].y = 0;
1078   FourMVect[1].x = 0;
1079   FourMVect[1].y = 0;
1080   FourMVect[2].x = 0;
1081   FourMVect[2].y = 0;
1082   FourMVect[3].x = 0;
1083   FourMVect[3].y = 0;
1084   FourMVect[4].x = 0;
1085   FourMVect[4].y = 0;
1086   FourMVect[5].x = 0;
1087   FourMVect[5].y = 0;
1088   LastInterMVect.x = 0;
1089   LastInterMVect.y = 0;
1090   PriorLastInterMVect.x = 0;
1091   PriorLastInterMVect.y = 0;
1092   LastGFMVect.x = 0;
1093   LastGFMVect.y = 0;
1094   InterMVect.x = 0;
1095   InterMVect.y = 0;
1096   GFMVect.x = 0;
1097   GFMVect.y = 0;
1098
1099   ZeroVect.x = 0;
1100   ZeroVect.y = 0;
1101
1102   QIndex = (unsigned char)cpi->pb.FrameQIndex;
1103
1104
1105
1106   /* change the quatization matrix to the one at best Q to compute the
1107      new error score */
1108   cpi->MinImprovementForNewMV = (MvThreshTable[QIndex] << 12);
1109   cpi->InterTripOutThresh = (5000<<12);
1110   cpi->MVChangeFactor = MVChangeFactorTable[QIndex]; /* 0.9 */
1111
1112   if ( cpi->pb.info.quick_p ) {
1113     cpi->ExhaustiveSearchThresh = (1000<<12);
1114     cpi->FourMVThreshold = (2500<<12);
1115   } else {
1116     cpi->ExhaustiveSearchThresh = (250<<12);
1117     cpi->FourMVThreshold = (500<<12);
1118   }
1119   cpi->MinImprovementForFourMV = cpi->MinImprovementForNewMV * 4;
1120
1121   if(cpi->MinImprovementForFourMV < (40<<12))
1122     cpi->MinImprovementForFourMV = (40<<12);
1123
1124   cpi->FourMvChangeFactor = 8; /* cpi->MVChangeFactor - 0.05;  */
1125
1126   /* decide what block type and motion vectors to use on all of the frames */
1127   for ( SBrow=0; SBrow<SBRows; SBrow++ ) {
1128     for ( SBcol=0; SBcol<SBCols; SBcol++ ) {
1129       /* Check its four Macro-Blocks */
1130       for ( MB=0; MB<4; MB++ ) {
1131         /* There may be MB's lying out of frame which must be
1132            ignored. For these MB's Top left block will have a negative
1133            Fragment Index. */
1134         if ( QuadMapToMBTopLeft(cpi->pb.BlockMap,SB,MB) < 0 ) continue;
1135
1136         /* Is the current macro block coded (in part or in whole) */
1137         MBCodedFlag = 0;
1138         for ( B=0; B<4; B++ ) {
1139           YFragIndex = QuadMapToIndex1( cpi->pb.BlockMap, SB, MB, B );
1140
1141           /* Does Block lie in frame: */
1142           if ( YFragIndex >= 0 ) {
1143             /* In Frame: Is it coded: */
1144             if ( cpi->pb.display_fragments[YFragIndex] ) {
1145               MBCodedFlag = 1;
1146               break;
1147             }
1148           } else
1149             MBCodedFlag = 0;
1150         }
1151
1152         /* This one isn't coded go to the next one */
1153         if(!MBCodedFlag) continue;
1154
1155         /* Calculate U and V FragIndex from YFragIndex */
1156         YFragIndex = QuadMapToMBTopLeft(cpi->pb.BlockMap, SB,MB);
1157         UVRow = (YFragIndex / (cpi->pb.HFragments * 2));
1158         UVColumn = (YFragIndex % cpi->pb.HFragments) / 2;
1159         UVFragOffset = (UVRow * (cpi->pb.HFragments / 2)) + UVColumn;
1160         UFragIndex = cpi->pb.YPlaneFragments + UVFragOffset;
1161         VFragIndex = cpi->pb.YPlaneFragments + cpi->pb.UVPlaneFragments +
1162           UVFragOffset;
1163
1164
1165         /**************************************************************
1166          Find the block choice with the lowest error
1167
1168          NOTE THAT if U or V is coded but no Y from a macro block then
1169          the mode will be CODE_INTER_NO_MV as this is the default
1170          state to which the mode data structure is initialised in
1171          encoder and decoder at the start of each frame. */
1172
1173         BestError = HUGE_ERROR;
1174
1175
1176         /* Look at the intra coding error. */
1177         MBIntraError = GetMBIntraError( cpi, YFragIndex, PixelsPerLine );
1178         BestError = (BestError > MBIntraError) ? MBIntraError : BestError;
1179
1180         /* Get the golden frame error */
1181         MBGFError = GetMBInterError( cpi, cpi->ConvDestBuffer,
1182                                      cpi->pb.GoldenFrame, YFragIndex,
1183                                      0, 0, PixelsPerLine );
1184         BestError = (BestError > MBGFError) ? MBGFError : BestError;
1185
1186         /* Calculate the 0,0 case. */
1187         MBInterError = GetMBInterError( cpi, cpi->ConvDestBuffer,
1188                                         cpi->pb.LastFrameRecon,
1189                                         YFragIndex, 0, 0, PixelsPerLine );
1190         BestError = (BestError > MBInterError) ? MBInterError : BestError;
1191
1192         /* Measure error for last MV */
1193         MBLastInterError =  GetMBInterError( cpi, cpi->ConvDestBuffer,
1194                                              cpi->pb.LastFrameRecon,
1195                                              YFragIndex, LastInterMVect.x,
1196                                              LastInterMVect.y, PixelsPerLine );
1197         BestError = (BestError > MBLastInterError) ?
1198           MBLastInterError : BestError;
1199
1200         /* Measure error for prior last MV */
1201         MBPriorLastInterError =  GetMBInterError( cpi, cpi->ConvDestBuffer,
1202                                                   cpi->pb.LastFrameRecon,
1203                                                   YFragIndex,
1204                                                   PriorLastInterMVect.x,
1205                                                   PriorLastInterMVect.y,
1206                                                   PixelsPerLine );
1207         BestError = (BestError > MBPriorLastInterError) ?
1208           MBPriorLastInterError : BestError;
1209
1210         /* Temporarily force usage of no motionvector blocks */
1211         MBInterMVError = HUGE_ERROR;
1212         InterMVect.x = 0;  /* Set 0,0 motion vector */
1213         InterMVect.y = 0;
1214
1215         /* If the best error is above the required threshold search
1216            for a new inter MV */
1217         if ( BestError > cpi->MinImprovementForNewMV ) {
1218           /* Use a mix of heirachical and exhaustive searches for
1219              quick mode. */
1220           if ( cpi->pb.info.quick_p ) {
1221             MBInterMVError = GetMBMVInterError( cpi, cpi->pb.LastFrameRecon,
1222                                                 YFragIndex, PixelsPerLine,
1223                                                 cpi->MVPixelOffsetY,
1224                                                 &InterMVect );
1225
1226             /* If we still do not have a good match try an exhaustive
1227                MBMV search */
1228             if ( (MBInterMVError > cpi->ExhaustiveSearchThresh) &&
1229                  (BestError > cpi->ExhaustiveSearchThresh) ) {
1230
1231               MBInterMVExError =
1232                 GetMBMVExhaustiveSearch( cpi, cpi->pb.LastFrameRecon,
1233                                          YFragIndex, PixelsPerLine,
1234                                          &InterMVectEx );
1235
1236               /* Is the Variance measure for the EX search
1237                  better... If so then use it. */
1238               if ( MBInterMVExError < MBInterMVError ) {
1239                 MBInterMVError = MBInterMVExError;
1240                 InterMVect.x = InterMVectEx.x;
1241                 InterMVect.y = InterMVectEx.y;
1242               }
1243             }
1244           }else{
1245             /* Use an exhaustive search */
1246             MBInterMVError =
1247               GetMBMVExhaustiveSearch( cpi, cpi->pb.LastFrameRecon,
1248                                        YFragIndex, PixelsPerLine,
1249                                        &InterMVect );
1250           }
1251
1252
1253           /* Is the improvement, if any, good enough to justify a new MV */
1254           if ( (16 * MBInterMVError < (BestError * cpi->MVChangeFactor)) &&
1255                ((MBInterMVError + cpi->MinImprovementForNewMV) < BestError) ){
1256             BestError = MBInterMVError;
1257           }
1258
1259         }
1260
1261         /* If the best error is still above the required threshold
1262            search for a golden frame MV */
1263         MBGF_MVError = HUGE_ERROR;
1264         GFMVect.x = 0; /* Set 0,0 motion vector */
1265         GFMVect.y = 0;
1266         if ( BestError > cpi->MinImprovementForNewMV ) {
1267           /* Do an MV search in the golden reference frame */
1268           MBGF_MVError = GetMBMVInterError( cpi, cpi->pb.GoldenFrame,
1269                                             YFragIndex, PixelsPerLine,
1270                                             cpi->MVPixelOffsetY, &GFMVect );
1271
1272           /* Measure error for last GFMV */
1273           LastMBGF_MVError =  GetMBInterError( cpi, cpi->ConvDestBuffer,
1274                                                cpi->pb.GoldenFrame,
1275                                                YFragIndex, LastGFMVect.x,
1276                                                LastGFMVect.y, PixelsPerLine );
1277
1278           /* Check against last GF motion vector and reset if the
1279              search has thrown a worse result. */
1280           if ( LastMBGF_MVError < MBGF_MVError ) {
1281             GFMVect.x = LastGFMVect.x;
1282             GFMVect.y = LastGFMVect.y;
1283             MBGF_MVError = LastMBGF_MVError;
1284           }else{
1285             LastGFMVect.x = GFMVect.x;
1286             LastGFMVect.y = GFMVect.y;
1287           }
1288
1289           /* Is the improvement, if any, good enough to justify a new MV */
1290           if ( (16 * MBGF_MVError < (BestError * cpi->MVChangeFactor)) &&
1291                ((MBGF_MVError + cpi->MinImprovementForNewMV) < BestError) ) {
1292             BestError = MBGF_MVError;
1293           }
1294         }
1295
1296         /* Finally... If the best error is still to high then consider
1297            the 4MV mode */
1298         MBInterFOURMVError = HUGE_ERROR;
1299         if ( BestError > cpi->FourMVThreshold ) {
1300           /* Get the 4MV error. */
1301           MBInterFOURMVError =
1302             GetFOURMVExhaustiveSearch( cpi, cpi->pb.LastFrameRecon,
1303                                        YFragIndex, PixelsPerLine, FourMVect );
1304
1305           /* If the improvement is great enough then use the four MV mode */
1306           if ( ((MBInterFOURMVError + cpi->MinImprovementForFourMV) <
1307                 BestError) && (16 * MBInterFOURMVError <
1308                                (BestError * cpi->FourMvChangeFactor))) {
1309             BestError = MBInterFOURMVError;
1310           }
1311         }
1312
1313         /********************************************************
1314          end finding the best error
1315          *******************************************************
1316
1317          Figure out what to do with the block we chose
1318
1319          Over-ride and force intra if error high and Intra error similar
1320          Now choose a mode based on lowest error (with bias towards no MV) */
1321
1322         if ( (BestError > cpi->InterTripOutThresh) &&
1323              (10 * BestError > MBIntraError * 7 ) ) {
1324           cpi->MBCodingMode = CODE_INTRA;
1325           SetMBMotionVectorsAndMode(cpi,YFragIndex,UFragIndex,
1326                                     VFragIndex,&ZeroVect);
1327         } else if ( BestError == MBInterError ) {
1328           cpi->MBCodingMode = CODE_INTER_NO_MV;
1329           SetMBMotionVectorsAndMode(cpi,YFragIndex,UFragIndex,
1330                                     VFragIndex,&ZeroVect);
1331         } else if ( BestError == MBGFError ) {
1332           cpi->MBCodingMode = CODE_USING_GOLDEN;
1333           SetMBMotionVectorsAndMode(cpi,YFragIndex,UFragIndex,
1334                                     VFragIndex,&ZeroVect);
1335         } else if ( BestError == MBLastInterError ) {
1336           cpi->MBCodingMode = CODE_INTER_LAST_MV;
1337           SetMBMotionVectorsAndMode(cpi,YFragIndex,UFragIndex,
1338                                     VFragIndex,&LastInterMVect);
1339         } else if ( BestError == MBPriorLastInterError ) {
1340           cpi->MBCodingMode = CODE_INTER_PRIOR_LAST;
1341           SetMBMotionVectorsAndMode(cpi,YFragIndex,UFragIndex,
1342                                     VFragIndex,&PriorLastInterMVect);
1343
1344           /* Swap the prior and last MV cases over */
1345           TmpMVect.x = PriorLastInterMVect.x;
1346           TmpMVect.y = PriorLastInterMVect.y;
1347           PriorLastInterMVect.x = LastInterMVect.x;
1348           PriorLastInterMVect.y = LastInterMVect.y;
1349           LastInterMVect.x = TmpMVect.x;
1350           LastInterMVect.y = TmpMVect.y;
1351
1352         } else if ( BestError == MBInterMVError ) {
1353
1354           cpi->MBCodingMode = CODE_INTER_PLUS_MV;
1355           SetMBMotionVectorsAndMode(cpi,YFragIndex,UFragIndex,
1356                                     VFragIndex,&InterMVect);
1357
1358           /* Update Prior last mv with last mv */
1359           PriorLastInterMVect.x = LastInterMVect.x;
1360           PriorLastInterMVect.y = LastInterMVect.y;
1361
1362           /* Note last inter MV for future use */
1363           LastInterMVect.x = InterMVect.x;
1364           LastInterMVect.y = InterMVect.y;
1365
1366           AddMotionVector( cpi, &InterMVect);
1367
1368         } else if ( BestError == MBGF_MVError ) {
1369
1370           cpi->MBCodingMode = CODE_GOLDEN_MV;
1371           SetMBMotionVectorsAndMode(cpi,YFragIndex,UFragIndex,
1372                                     VFragIndex,&GFMVect);
1373
1374           /* Note last inter GF MV for future use */
1375           LastGFMVect.x = GFMVect.x;
1376           LastGFMVect.y = GFMVect.y;
1377
1378           AddMotionVector( cpi, &GFMVect);
1379         } else if ( BestError == MBInterFOURMVError ) {
1380           cpi->MBCodingMode = CODE_INTER_FOURMV;
1381
1382           /* Calculate the UV vectors as the average of the Y plane ones. */
1383           /* First .x component */
1384           FourMVect[4].x = FourMVect[0].x + FourMVect[1].x +
1385             FourMVect[2].x + FourMVect[3].x;
1386           if ( FourMVect[4].x >= 0 )
1387             FourMVect[4].x = (FourMVect[4].x + 2) / 4;
1388           else
1389             FourMVect[4].x = (FourMVect[4].x - 2) / 4;
1390           FourMVect[5].x = FourMVect[4].x;
1391
1392           /* Then .y component */
1393           FourMVect[4].y = FourMVect[0].y + FourMVect[1].y +
1394             FourMVect[2].y + FourMVect[3].y;
1395           if ( FourMVect[4].y >= 0 )
1396             FourMVect[4].y = (FourMVect[4].y + 2) / 4;
1397           else
1398             FourMVect[4].y = (FourMVect[4].y - 2) / 4;
1399           FourMVect[5].y = FourMVect[4].y;
1400
1401           SetFragMotionVectorAndMode(cpi, YFragIndex, &FourMVect[0]);
1402           SetFragMotionVectorAndMode(cpi, YFragIndex + 1, &FourMVect[1]);
1403           SetFragMotionVectorAndMode(cpi, YFragIndex + cpi->pb.HFragments,
1404                                      &FourMVect[2]);
1405           SetFragMotionVectorAndMode(cpi, YFragIndex + cpi->pb.HFragments + 1,
1406                                      &FourMVect[3]);
1407           SetFragMotionVectorAndMode(cpi, UFragIndex, &FourMVect[4]);
1408           SetFragMotionVectorAndMode(cpi, VFragIndex, &FourMVect[5]);
1409
1410           /* Note the four MVs values for current macro-block. */
1411           AddMotionVector( cpi, &FourMVect[0]);
1412           AddMotionVector( cpi, &FourMVect[1]);
1413           AddMotionVector( cpi, &FourMVect[2]);
1414           AddMotionVector( cpi, &FourMVect[3]);
1415
1416           /* Update Prior last mv with last mv */
1417           PriorLastInterMVect.x = LastInterMVect.x;
1418           PriorLastInterMVect.y = LastInterMVect.y;
1419
1420           /* Note last inter MV for future use */
1421           LastInterMVect.x = FourMVect[3].x;
1422           LastInterMVect.y = FourMVect[3].y;
1423
1424         } else {
1425
1426           cpi->MBCodingMode = CODE_INTRA;
1427           SetMBMotionVectorsAndMode(cpi,YFragIndex,UFragIndex,
1428                                     VFragIndex,&ZeroVect);
1429         }
1430
1431
1432         /* setting up mode specific block types
1433            *******************************************************/
1434
1435         *InterError += (BestError>>8);
1436         *IntraError += (MBIntraError>>8);
1437
1438
1439       }
1440       SB++;
1441
1442     }
1443   }
1444
1445   /* Return number of pixels coded */
1446   return 0;
1447 }
1448
1449 void WriteFrameHeader( CP_INSTANCE *cpi) {
1450   ogg_uint32_t i;
1451   oggpack_buffer *opb=cpi->oggbuffer;
1452
1453   /* Output the frame type (base/key frame or inter frame) */
1454   oggpackB_write( opb, cpi->pb.FrameType, 1 );
1455
1456   /* Write out details of the current value of Q... variable resolution. */
1457   for ( i = 0; i < Q_TABLE_SIZE; i++ ) {
1458     if ( cpi->pb.ThisFrameQualityValue == cpi->pb.QThreshTable[i] ) {
1459       oggpackB_write( opb, i, 6 );
1460       break;
1461     }
1462   }
1463
1464   if ( i == Q_TABLE_SIZE ) {
1465     /* An invalid DCT value was specified.  */
1466     /*IssueWarning( "Invalid Q Multiplier" );*/
1467     oggpackB_write( opb, 31, 6 );
1468   }
1469
1470   /* we only support one Q index per frame */
1471   oggpackB_write( opb, 0, 1 );
1472
1473   /* If the frame was a base frame then write out the frame dimensions. */
1474   if ( cpi->pb.FrameType == KEY_FRAME ) {
1475     /* Key frame type / method */
1476     oggpackB_write( opb, cpi->pb.KeyFrameType, 1 );
1477
1478     /* Spare configuration bits */
1479     oggpackB_write( opb, 0, 2 );
1480   }
1481 }
1482