media/libtheora/lib/dec/internal.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-2007                *
   9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13   function:
  14     last mod: $Id: internal.c 14385 2008-01-09 19:53:18Z giles $
  15
  16  ********************************************************************/
  17
  18 #include <stdlib.h>
  19 #include <limits.h>
  20 #include <string.h>
  21 #include "../internal.h"
  22 #include "idct.h"
  23
  24
  25
  26 /*A map from the index in the zig zag scan to the coefficient number in a
  27    block.
  28   All zig zag indices beyond 63 are sent to coefficient 64, so that zero runs
  29    past the end of a block in bogus streams get mapped to a known location.*/
  30 const int OC_FZIG_ZAG[128]={
  31    0, 1, 8,16, 9, 2, 3,10,
  32   17,24,32,25,18,11, 4, 5,
  33   12,19,26,33,40,48,41,34,
  34   27,20,13, 6, 7,14,21,28,
  35   35,42,49,56,57,50,43,36,
  36   29,22,15,23,30,37,44,51,
  37   58,59,52,45,38,31,39,46,
  38   53,60,61,54,47,55,62,63,
  39   64,64,64,64,64,64,64,64,
  40   64,64,64,64,64,64,64,64,
  41   64,64,64,64,64,64,64,64,
  42   64,64,64,64,64,64,64,64,
  43   64,64,64,64,64,64,64,64,
  44   64,64,64,64,64,64,64,64,
  45   64,64,64,64,64,64,64,64,
  46   64,64,64,64,64,64,64,64
  47 };
  48
  49 /*A map from the coefficient number in a block to its index in the zig zag
  50    scan.*/
  51 const int OC_IZIG_ZAG[64]={
  52    0, 1, 5, 6,14,15,27,28,
  53    2, 4, 7,13,16,26,29,42,
  54    3, 8,12,17,25,30,41,43,
  55    9,11,18,24,31,40,44,53,
  56   10,19,23,32,39,45,52,54,
  57   20,22,33,38,46,51,55,60,
  58   21,34,37,47,50,56,59,61,
  59   35,36,48,49,57,58,62,63
  60 };
  61
  62 /*The predictor frame to use for each macro block mode.*/
  63 const int OC_FRAME_FOR_MODE[8]={
  64   /*OC_MODE_INTER_NOMV*/
  65   OC_FRAME_PREV,
  66   /*OC_MODE_INTRA*/
  67   OC_FRAME_SELF,
  68   /*OC_MODE_INTER_MV*/
  69   OC_FRAME_PREV,
  70   /*OC_MODE_INTER_MV_LAST*/
  71   OC_FRAME_PREV,
  72   /*OC_MODE_INTER_MV_LAST2*/
  73   OC_FRAME_PREV,
  74   /*OC_MODE_GOLDEN*/
  75   OC_FRAME_GOLD,
  76   /*OC_MODE_GOLDEN_MV*/
  77   OC_FRAME_GOLD,
  78   /*OC_MODE_INTER_MV_FOUR*/
  79   OC_FRAME_PREV,
  80 };
  81
  82 /*A map from physical macro block ordering to bitstream macro block
  83    ordering within a super block.*/
  84 const int OC_MB_MAP[2][2]={{0,3},{1,2}};
  85
  86 /*A list of the indices in the oc_mb.map array that can be valid for each of
  87    the various chroma decimation types.*/
  88 const int OC_MB_MAP_IDXS[TH_PF_NFORMATS][12]={
  89   {0,1,2,3,4,8},
  90   {0,1,2,3,4,5,8,9},
  91   {0,1,2,3,4,6,8,10},
  92   {0,1,2,3,4,5,6,7,8,9,10,11}
  93 };
  94
  95 /*The number of indices in the oc_mb.map array that can be valid for each of
  96    the various chroma decimation types.*/
  97 const int OC_MB_MAP_NIDXS[TH_PF_NFORMATS]={6,8,8,12};
  98
  99 /*The number of extra bits that are coded with each of the DCT tokens.
 100   Each DCT token has some fixed number of additional bits (possibly 0) stored
 101    after the token itself, containing, for example, coefficient magnitude,
 102    sign bits, etc.*/
 103 const int OC_DCT_TOKEN_EXTRA_BITS[TH_NDCT_TOKENS]={
 104   0,0,0,2,3,4,12,3,6,
 105   0,0,0,0,
 106   1,1,1,1,2,3,4,5,6,10,
 107   1,1,1,1,1,3,4,
 108   2,3
 109 };
 110
 111
 112
 113 int oc_ilog(unsigned _v){
 114   int ret;
 115   for(ret=0;_v;ret++)_v>>=1;
 116   return ret;
 117 }
 118
 119
 120
 121 /*Determines the number of blocks or coefficients to be skipped for a given
 122    token value.
 123   _token:      The token value to skip.
 124   _extra_bits: The extra bits attached to this token.
 125   Return: A positive value indicates that number of coefficients are to be
 126            skipped in the current block.
 127           Otherwise, the negative of the return value indicates that number of
 128            blocks are to be ended.*/
 129 typedef int (*oc_token_skip_func)(int _token,int _extra_bits);
 130
 131 /*Handles the simple end of block tokens.*/
 132 static int oc_token_skip_eob(int _token,int _extra_bits){
 133   static const int NBLOCKS_ADJUST[OC_NDCT_EOB_TOKEN_MAX]={1,2,3,4,8,16,0};
 134   return -_extra_bits-NBLOCKS_ADJUST[_token];
 135 }
 136
 137 /*The last EOB token has a special case, where an EOB run of size zero ends all
 138    the remaining blocks in the frame.*/
 139 static int oc_token_skip_eob6(int _token,int _extra_bits){
 140   if(!_extra_bits)return -INT_MAX;
 141   return -_extra_bits;
 142 }
 143
 144 /*Handles the pure zero run tokens.*/
 145 static int oc_token_skip_zrl(int _token,int _extra_bits){
 146   return _extra_bits+1;
 147 }
 148
 149 /*Handles a normal coefficient value token.*/
 150 static int oc_token_skip_val(void){
 151   return 1;
 152 }
 153
 154 /*Handles a category 1A zero run/coefficient value combo token.*/
 155 static int oc_token_skip_run_cat1a(int _token){
 156   return _token-OC_DCT_RUN_CAT1A+2;
 157 }
 158
 159 /*Handles category 1b and 2 zero run/coefficient value combo tokens.*/
 160 static int oc_token_skip_run(int _token,int _extra_bits){
 161   static const int NCOEFFS_ADJUST[OC_NDCT_RUN_MAX-OC_DCT_RUN_CAT1B]={
 162     7,11,2,3
 163   };
 164   static const int NCOEFFS_MASK[OC_NDCT_RUN_MAX-OC_DCT_RUN_CAT1B]={
 165     3,7,0,1
 166   };
 167   _token-=OC_DCT_RUN_CAT1B;
 168   return (_extra_bits&NCOEFFS_MASK[_token])+NCOEFFS_ADJUST[_token];
 169 }
 170
 171 /*A jump table for computing the number of coefficients or blocks to skip for
 172    a given token value.
 173   This reduces all the conditional branches, etc., needed to parse these token
 174    values down to one indirect jump.*/
 175 static const oc_token_skip_func OC_TOKEN_SKIP_TABLE[TH_NDCT_TOKENS]={
 176   oc_token_skip_eob,
 177   oc_token_skip_eob,
 178   oc_token_skip_eob,
 179   oc_token_skip_eob,
 180   oc_token_skip_eob,
 181   oc_token_skip_eob,
 182   oc_token_skip_eob6,
 183   oc_token_skip_zrl,
 184   oc_token_skip_zrl,
 185   (oc_token_skip_func)oc_token_skip_val,
 186   (oc_token_skip_func)oc_token_skip_val,
 187   (oc_token_skip_func)oc_token_skip_val,
 188   (oc_token_skip_func)oc_token_skip_val,
 189   (oc_token_skip_func)oc_token_skip_val,
 190   (oc_token_skip_func)oc_token_skip_val,
 191   (oc_token_skip_func)oc_token_skip_val,
 192   (oc_token_skip_func)oc_token_skip_val,
 193   (oc_token_skip_func)oc_token_skip_val,
 194   (oc_token_skip_func)oc_token_skip_val,
 195   (oc_token_skip_func)oc_token_skip_val,
 196   (oc_token_skip_func)oc_token_skip_val,
 197   (oc_token_skip_func)oc_token_skip_val,
 198   (oc_token_skip_func)oc_token_skip_val,
 199   (oc_token_skip_func)oc_token_skip_run_cat1a,
 200   (oc_token_skip_func)oc_token_skip_run_cat1a,
 201   (oc_token_skip_func)oc_token_skip_run_cat1a,
 202   (oc_token_skip_func)oc_token_skip_run_cat1a,
 203   (oc_token_skip_func)oc_token_skip_run_cat1a,
 204   oc_token_skip_run,
 205   oc_token_skip_run,
 206   oc_token_skip_run,
 207   oc_token_skip_run
 208 };
 209
 210 /*Determines the number of blocks or coefficients to be skipped for a given
 211    token value.
 212   _token:      The token value to skip.
 213   _extra_bits: The extra bits attached to this token.
 214   Return: A positive value indicates that number of coefficients are to be
 215            skipped in the current block.
 216           Otherwise, the negative of the return value indicates that number of
 217            blocks are to be ended.
 218           0 will never be returned, so that at least one coefficient in one
 219            block will always be decoded for every token.*/
 220 int oc_dct_token_skip(int _token,int _extra_bits){
 221   return (*OC_TOKEN_SKIP_TABLE[_token])(_token,_extra_bits);
 222 }
 223
 224
 225 /*The function used to fill in the chroma plane motion vectors for a macro
 226    block when 4 different motion vectors are specified in the luma plane.
 227   This version is for use with chroma decimated in the X and Y directions.
 228   _cbmvs: The chroma block-level motion vectors to fill in.
 229   _lbmvs: The luma block-level motion vectors.*/
 230 static void oc_set_chroma_mvs00(oc_mv _cbmvs[4],const oc_mv _lbmvs[4]){
 231   int dx;
 232   int dy;
 233   dx=_lbmvs[0][0]+_lbmvs[1][0]+_lbmvs[2][0]+_lbmvs[3][0];
 234   dy=_lbmvs[0][1]+_lbmvs[1][1]+_lbmvs[2][1]+_lbmvs[3][1];
 235   _cbmvs[0][0]=(signed char)OC_DIV_ROUND_POW2(dx,2,2);
 236   _cbmvs[0][1]=(signed char)OC_DIV_ROUND_POW2(dy,2,2);
 237 }
 238
 239 /*The function used to fill in the chroma plane motion vectors for a macro
 240    block when 4 different motion vectors are specified in the luma plane.
 241   This version is for use with chroma decimated in the Y direction.
 242   _cbmvs: The chroma block-level motion vectors to fill in.
 243   _lbmvs: The luma block-level motion vectors.*/
 244 static void oc_set_chroma_mvs01(oc_mv _cbmvs[4],const oc_mv _lbmvs[4]){
 245   int dx;
 246   int dy;
 247   dx=_lbmvs[0][0]+_lbmvs[2][0];
 248   dy=_lbmvs[0][1]+_lbmvs[2][1];
 249   _cbmvs[0][0]=(signed char)OC_DIV_ROUND_POW2(dx,1,1);
 250   _cbmvs[0][1]=(signed char)OC_DIV_ROUND_POW2(dy,1,1);
 251   dx=_lbmvs[1][0]+_lbmvs[3][0];
 252   dy=_lbmvs[1][1]+_lbmvs[3][1];
 253   _cbmvs[1][0]=(signed char)OC_DIV_ROUND_POW2(dx,1,1);
 254   _cbmvs[1][1]=(signed char)OC_DIV_ROUND_POW2(dy,1,1);
 255 }
 256
 257 /*The function used to fill in the chroma plane motion vectors for a macro
 258    block when 4 different motion vectors are specified in the luma plane.
 259   This version is for use with chroma decimated in the X direction.
 260   _cbmvs: The chroma block-level motion vectors to fill in.
 261   _lbmvs: The luma block-level motion vectors.*/
 262 static void oc_set_chroma_mvs10(oc_mv _cbmvs[4],const oc_mv _lbmvs[4]){
 263   int dx;
 264   int dy;
 265   dx=_lbmvs[0][0]+_lbmvs[1][0];
 266   dy=_lbmvs[0][1]+_lbmvs[1][1];
 267   _cbmvs[0][0]=(signed char)OC_DIV_ROUND_POW2(dx,1,1);
 268   _cbmvs[0][1]=(signed char)OC_DIV_ROUND_POW2(dy,1,1);
 269   dx=_lbmvs[2][0]+_lbmvs[3][0];
 270   dy=_lbmvs[2][1]+_lbmvs[3][1];
 271   _cbmvs[2][0]=(signed char)OC_DIV_ROUND_POW2(dx,1,1);
 272   _cbmvs[2][1]=(signed char)OC_DIV_ROUND_POW2(dy,1,1);
 273 }
 274
 275 /*The function used to fill in the chroma plane motion vectors for a macro
 276    block when 4 different motion vectors are specified in the luma plane.
 277   This version is for use with no chroma decimation.
 278   _cbmvs: The chroma block-level motion vectors to fill in.
 279   _lmbmv: The luma macro-block level motion vector to fill in for use in
 280            prediction.
 281   _lbmvs: The luma block-level motion vectors.*/
 282 static void oc_set_chroma_mvs11(oc_mv _cbmvs[4],const oc_mv _lbmvs[4]){
 283   memcpy(_cbmvs,_lbmvs,4*sizeof(_lbmvs[0]));
 284 }
 285
 286 /*A table of functions used to fill in the chroma plane motion vectors for a
 287    macro block when 4 different motion vectors are specified in the luma
 288    plane.*/
 289 const oc_set_chroma_mvs_func OC_SET_CHROMA_MVS_TABLE[TH_PF_NFORMATS]={
 290   (oc_set_chroma_mvs_func)oc_set_chroma_mvs00,
 291   (oc_set_chroma_mvs_func)oc_set_chroma_mvs01,
 292   (oc_set_chroma_mvs_func)oc_set_chroma_mvs10,
 293   (oc_set_chroma_mvs_func)oc_set_chroma_mvs11
 294 };
 295
 296
 297
 298 void **oc_malloc_2d(size_t _height,size_t _width,size_t _sz){
 299   size_t  rowsz;
 300   size_t  colsz;
 301   size_t  datsz;
 302   char   *ret;
 303   colsz=_height*sizeof(void *);
 304   rowsz=_sz*_width;
 305   datsz=rowsz*_height;
 306   /*Alloc array and row pointers.*/
 307   ret=(char *)_ogg_malloc(datsz+colsz);
 308   /*Initialize the array.*/
 309   if(ret!=NULL){
 310     size_t   i;
 311     void   **p;
 312     char    *datptr;
 313     p=(void **)ret;
 314     i=_height;
 315     for(datptr=ret+colsz;i-->0;p++,datptr+=rowsz)*p=(void *)datptr;
 316   }
 317   return (void **)ret;
 318 }
 319
 320 void **oc_calloc_2d(size_t _height,size_t _width,size_t _sz){
 321   size_t  colsz;
 322   size_t  rowsz;
 323   size_t  datsz;
 324   char   *ret;
 325   colsz=_height*sizeof(void *);
 326   rowsz=_sz*_width;
 327   datsz=rowsz*_height;
 328   /*Alloc array and row pointers.*/
 329   ret=(char *)_ogg_calloc(datsz+colsz,1);
 330   /*Initialize the array.*/
 331   if(ret!=NULL){
 332     size_t   i;
 333     void   **p;
 334     char    *datptr;
 335     p=(void **)ret;
 336     i=_height;
 337     for(datptr=ret+colsz;i-->0;p++,datptr+=rowsz)*p=(void *)datptr;
 338   }
 339   return (void **)ret;
 340 }
 341
 342 void oc_free_2d(void *_ptr){
 343   _ogg_free(_ptr);
 344 }
 345
 346 /*Fills in a Y'CbCr buffer with a pointer to the image data in the first
 347    buffer, but with the opposite vertical orientation.
 348   _dst: The destination buffer.
 349         This can be the same as _src.
 350   _src: The source buffer.*/
 351 void oc_ycbcr_buffer_flip(th_ycbcr_buffer _dst,
 352  const th_ycbcr_buffer _src){
 353   int pli;
 354   for(pli=0;pli<3;pli++){
 355     _dst[pli].width=_src[pli].width;
 356     _dst[pli].height=_src[pli].height;
 357     _dst[pli].stride=-_src[pli].stride;
 358     _dst[pli].data=_src[pli].data+(1-_dst[pli].height)*_dst[pli].stride;
 359   }
 360 }
 361
 362 const char *th_version_string(void){
 363   return OC_VENDOR_STRING;
 364 }
 365
 366 ogg_uint32_t th_version_number(void){
 367   return (TH_VERSION_MAJOR<<16)+(TH_VERSION_MINOR<<8)+(TH_VERSION_SUB);
 368 }
 369
 370 /*Determines the packet type.
 371   Note that this correctly interprets a 0-byte packet as a video data packet.
 372   Return: 1 for a header packet, 0 for a data packet.*/
 373 int th_packet_isheader(ogg_packet *_op){
 374   return _op->bytes>0?_op->packet[0]>>7:0;
 375 }
 376
 377 /*Determines the frame type of a video data packet.
 378   Note that this correctly interprets a 0-byte packet as a delta frame.
 379   Return: 1 for a key frame, 0 for a delta frame, and -1 for a header
 380            packet.*/
 381 int th_packet_iskeyframe(ogg_packet *_op){
 382   return _op->bytes<=0?0:_op->packet[0]&0x80?-1:!(_op->packet[0]&0x40);
 383 }