theora-old/lib/frarray.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 <string.h>
  19 #include "codec_internal.h"
  20 #include "block_inline.h"
  21
  22 /* Long run bit string coding */
  23 static ogg_uint32_t FrArrayCodeSBRun( CP_INSTANCE *cpi, ogg_uint32_t value ){
  24   ogg_uint32_t CodedVal = 0;
  25   ogg_uint32_t CodedBits = 0;
  26
  27   /* Coding scheme:
  28         Codeword              RunLength
  29       0                       1
  30       10x                     2-3
  31       110x                    4-5
  32       1110xx                  6-9
  33       11110xxx                10-17
  34       111110xxxx              18-33
  35       111111xxxxxxxxxxxx      34-4129 */
  36
  37   if ( value == 1 ){
  38     CodedVal = 0;
  39     CodedBits = 1;
  40   } else if ( value <= 3 ) {
  41     CodedVal = 0x0004 + (value - 2);
  42     CodedBits = 3;
  43   } else if ( value <= 5 ) {
  44     CodedVal = 0x000C + (value - 4);
  45     CodedBits = 4;
  46   } else if ( value <= 9 ) {
  47     CodedVal = 0x0038 + (value - 6);
  48     CodedBits = 6;
  49   } else if ( value <= 17 ) {
  50     CodedVal = 0x00F0 + (value - 10);
  51     CodedBits = 8;
  52   } else if ( value <= 33 ) {
  53     CodedVal = 0x03E0 + (value - 18);
  54     CodedBits = 10;
  55   } else {
  56     CodedVal = 0x3F000 + (value - 34);
  57     CodedBits = 18;
  58   }
  59   /* todo: handle value > 4129 extension */
  60
  61   /* Add the bits to the encode holding buffer. */
  62   oggpackB_write( cpi->oggbuffer, CodedVal, CodedBits );
  63
  64   return CodedBits;
  65 }
  66
  67 /* Short run bit string coding */
  68 static ogg_uint32_t FrArrayCodeBlockRun( CP_INSTANCE *cpi,
  69                                          ogg_uint32_t value ) {
  70   ogg_uint32_t CodedVal = 0;
  71   ogg_uint32_t CodedBits = 0;
  72
  73   /* Coding scheme:
  74         Codeword                                RunLength
  75         0x                                      1-2
  76         10x                                     3-4
  77         110x                                    5-6
  78         1110xx                                  7-10
  79         11110xx                                 11-14
  80         11111xxxx                               15-30 */
  81
  82   if ( value <= 2 ) {
  83     CodedVal = value - 1;
  84     CodedBits = 2;
  85   } else if ( value <= 4 ) {
  86     CodedVal = 0x0004 + (value - 3);
  87     CodedBits = 3;
  88
  89   } else if ( value <= 6 ) {
  90     CodedVal = 0x000C + (value - 5);
  91     CodedBits = 4;
  92
  93   } else if ( value <= 10 ) {
  94     CodedVal = 0x0038 + (value - 7);
  95     CodedBits = 6;
  96
  97   } else if ( value <= 14 ) {
  98     CodedVal = 0x0078 + (value - 11);
  99     CodedBits = 7;
 100   } else {
 101     CodedVal = 0x01F0 + (value - 15);
 102     CodedBits = 9;
 103  }
 104
 105   /* Add the bits to the encode holding buffer. */
 106   oggpackB_write( cpi->oggbuffer, CodedVal, CodedBits );
 107
 108   return CodedBits;
 109 }
 110
 111 void PackAndWriteDFArray( CP_INSTANCE *cpi ){
 112   ogg_uint32_t  i;
 113   unsigned char val;
 114   ogg_uint32_t  run_count;
 115
 116   ogg_uint32_t  SB, MB, B;   /* Block, MB and SB loop variables */
 117   ogg_uint32_t  BListIndex = 0;
 118   ogg_uint32_t  LastSbBIndex = 0;
 119   ogg_int32_t   DfBlockIndex;  /* Block index in display_fragments */
 120
 121   /* Initialise workspaces */
 122   memset( cpi->pb.SBFullyFlags, 1, cpi->pb.SuperBlocks);
 123   memset( cpi->pb.SBCodedFlags, 0, cpi->pb.SuperBlocks );
 124   memset( cpi->PartiallyCodedFlags, 0, cpi->pb.SuperBlocks );
 125   memset( cpi->BlockCodedFlags, 0, cpi->pb.UnitFragments);
 126
 127   for( SB = 0; SB < cpi->pb.SuperBlocks; SB++ ) {
 128     /* Check for coded blocks and macro-blocks */
 129     for ( MB=0; MB<4; MB++ ) {
 130       /* If MB in frame */
 131       if ( QuadMapToMBTopLeft(cpi->pb.BlockMap,SB,MB) >= 0 ) {
 132         for ( B=0; B<4; B++ ) {
 133           DfBlockIndex = QuadMapToIndex1( cpi->pb.BlockMap,SB, MB, B );
 134
 135           /* Does Block lie in frame: */
 136           if ( DfBlockIndex >= 0 ) {
 137             /* In Frame: If it is not coded then this SB is only
 138                partly coded.: */
 139             if ( cpi->pb.display_fragments[DfBlockIndex] ) {
 140               cpi->pb.SBCodedFlags[SB] = 1; /* SB at least partly coded */
 141               cpi->BlockCodedFlags[BListIndex] = 1; /* Block is coded */
 142             }else{
 143               cpi->pb.SBFullyFlags[SB] = 0; /* SB not fully coded */
 144               cpi->BlockCodedFlags[BListIndex] = 0; /* Block is not coded */
 145             }
 146
 147             BListIndex++;
 148           }
 149         }
 150       }
 151     }
 152
 153     /* Is the SB fully coded or uncoded.
 154        If so then backup BListIndex and MBListIndex */
 155     if ( cpi->pb.SBFullyFlags[SB] || !cpi->pb.SBCodedFlags[SB] ) {
 156       BListIndex = LastSbBIndex; /* Reset to values from previous SB */
 157     }else{
 158       cpi->PartiallyCodedFlags[SB] = 1; /* Set up list of partially
 159                                            coded SBs */
 160       LastSbBIndex = BListIndex;
 161     }
 162   }
 163
 164   /* Code list of partially coded Super-Block.  */
 165   val = cpi->PartiallyCodedFlags[0];
 166   oggpackB_write( cpi->oggbuffer, (ogg_uint32_t)val, 1);
 167   i = 0;
 168   while ( i < cpi->pb.SuperBlocks ) {
 169     run_count = 0;
 170     while ( (i<cpi->pb.SuperBlocks) && (cpi->PartiallyCodedFlags[i]==val) ) {
 171       i++;
 172       run_count++;
 173     }
 174
 175     /* Code the run */
 176     FrArrayCodeSBRun( cpi, run_count );
 177     val = ( val == 0 ) ? 1 : 0;
 178   }
 179
 180   /* RLC Super-Block fully/not coded. */
 181   i = 0;
 182
 183   /* Skip partially coded blocks */
 184   while( (i < cpi->pb.SuperBlocks) && cpi->PartiallyCodedFlags[i] )
 185     i++;
 186
 187   if ( i < cpi->pb.SuperBlocks ) {
 188     val = cpi->pb.SBFullyFlags[i];
 189     oggpackB_write( cpi->oggbuffer, (ogg_uint32_t)val, 1);
 190
 191     while ( i < cpi->pb.SuperBlocks ) {
 192       run_count = 0;
 193       while ( (i < cpi->pb.SuperBlocks) && (cpi->pb.SBFullyFlags[i] == val) ) {
 194         i++;
 195         /* Skip partially coded blocks */
 196         while( (i < cpi->pb.SuperBlocks) && cpi->PartiallyCodedFlags[i] )
 197           i++;
 198         run_count++;
 199       }
 200
 201       /* Code the run */
 202       FrArrayCodeSBRun( cpi, run_count );
 203       val = ( val == 0 ) ? 1 : 0;
 204     }
 205   }
 206
 207   /*  Now code the block flags */
 208   if ( BListIndex > 0 ) {
 209     /* Code the block flags start value */
 210     val = cpi->BlockCodedFlags[0];
 211     oggpackB_write( cpi->oggbuffer, (ogg_uint32_t)val, 1);
 212
 213     /* Now code the block flags. */
 214     for ( i = 0; i < BListIndex; ) {
 215       run_count = 0;
 216       while ( (cpi->BlockCodedFlags[i] == val) && (i < BListIndex) ) {
 217         i++;
 218         run_count++;
 219       }
 220
 221       FrArrayCodeBlockRun( cpi, run_count );
 222       val = ( val == 0 ) ? 1 : 0;
 223
 224     }
 225   }
 226 }
 227
 228 static void FrArrayDeCodeInit(PB_INSTANCE *pbi){
 229   /* Initialise the decoding of a run.  */
 230   pbi->bit_pattern = 0;
 231   pbi->bits_so_far = 0;
 232 }
 233
 234 /* Short run bit string decoding */
 235 static int FrArrayDeCodeBlockRun(  PB_INSTANCE *pbi, ogg_uint32_t bit_value,
 236                             ogg_int32_t * run_value ){
 237   int  ret_val = 0;
 238
 239   /* Add in the new bit value. */
 240   pbi->bits_so_far++;
 241   pbi->bit_pattern = (pbi->bit_pattern << 1) + (bit_value & 1);
 242
 243   /* Coding scheme:
 244      Codeword           RunLength
 245      0x                    1-2
 246      10x                   3-4
 247      110x                  5-6
 248      1110xx                7-10
 249      11110xx              11-14
 250      11111xxxx            15-30
 251   */
 252
 253   switch ( pbi->bits_so_far ){
 254   case 2:
 255     /* If bit 1 is clear */
 256     if ( !(pbi->bit_pattern & 0x0002) ){
 257       ret_val = 1;
 258       *run_value = (pbi->bit_pattern & 0x0001) + 1;
 259     }
 260     break;
 261
 262   case 3:
 263     /* If bit 1 is clear */
 264     if ( !(pbi->bit_pattern & 0x0002) ){
 265       ret_val = 1;
 266       *run_value = (pbi->bit_pattern & 0x0001) + 3;
 267     }
 268     break;
 269
 270   case 4:
 271     /* If bit 1 is clear */
 272     if ( !(pbi->bit_pattern & 0x0002) ){
 273       ret_val = 1;
 274       *run_value = (pbi->bit_pattern & 0x0001) + 5;
 275     }
 276     break;
 277
 278   case 6:
 279     /* If bit 2 is clear */
 280     if ( !(pbi->bit_pattern & 0x0004) ){
 281       ret_val = 1;
 282       *run_value = (pbi->bit_pattern & 0x0003) + 7;
 283     }
 284     break;
 285
 286   case 7:
 287     /* If bit 2 is clear */
 288     if ( !(pbi->bit_pattern & 0x0004) ){
 289       ret_val = 1;
 290       *run_value = (pbi->bit_pattern & 0x0003) + 11;
 291     }
 292     break;
 293
 294   case 9:
 295     ret_val = 1;
 296     *run_value = (pbi->bit_pattern & 0x000F) + 15;
 297     break;
 298   }
 299
 300   return ret_val;
 301 }
 302
 303 /* Long run bit string decoding */
 304 static int FrArrayDeCodeSBRun (PB_INSTANCE *pbi, ogg_uint32_t bit_value,
 305                         ogg_int32_t * run_value ){
 306   int ret_val = 0;
 307
 308   /* Add in the new bit value. */
 309   pbi->bits_so_far++;
 310   pbi->bit_pattern = (pbi->bit_pattern << 1) + (bit_value & 1);
 311
 312   /* Coding scheme:
 313      Codeword            RunLength
 314      0                       1
 315      10x                    2-3
 316      110x                   4-5
 317      1110xx                 6-9
 318      11110xxx              10-17
 319      111110xxxx            18-33
 320      111111xxxxxxxxxxxx    34-4129
 321   */
 322
 323   switch ( pbi->bits_so_far ){
 324   case 1:
 325     if ( pbi->bit_pattern == 0 ){
 326       ret_val = 1;
 327       *run_value = 1;
 328     }
 329     break;
 330
 331   case 3:
 332     /* Bit 1 clear */
 333     if ( !(pbi->bit_pattern & 0x0002) ){
 334       ret_val = 1;
 335       *run_value = (pbi->bit_pattern & 0x0001) + 2;
 336     }
 337     break;
 338
 339   case 4:
 340     /* Bit 1 clear */
 341     if ( !(pbi->bit_pattern & 0x0002) ){
 342       ret_val = 1;
 343       *run_value = (pbi->bit_pattern & 0x0001) + 4;
 344     }
 345     break;
 346
 347   case 6:
 348     /* Bit 2 clear */
 349     if ( !(pbi->bit_pattern & 0x0004) ){
 350       ret_val = 1;
 351       *run_value = (pbi->bit_pattern & 0x0003) + 6;
 352     }
 353     break;
 354
 355   case 8:
 356     /* Bit 3 clear */
 357     if ( !(pbi->bit_pattern & 0x0008) ){
 358       ret_val = 1;
 359       *run_value = (pbi->bit_pattern & 0x0007) + 10;
 360     }
 361     break;
 362
 363   case 10:
 364     /* Bit 4 clear */
 365     if ( !(pbi->bit_pattern & 0x0010) ){
 366       ret_val = 1;
 367       *run_value = (pbi->bit_pattern & 0x000F) + 18;
 368     }
 369     break;
 370
 371   case 18:
 372     ret_val = 1;
 373     *run_value = (pbi->bit_pattern & 0x0FFF) + 34;
 374     break;
 375
 376   default:
 377     ret_val = 0;
 378     break;
 379   }
 380
 381   /* todo: handle additional bits for values over 4129 */
 382
 383   return ret_val;
 384 }
 385
 386 static void GetNextBInit(PB_INSTANCE *pbi){
 387   long ret;
 388
 389   theora_read(pbi->opb,1,&ret);
 390   pbi->NextBit = (unsigned char)ret;
 391
 392   /* Read run length */
 393   FrArrayDeCodeInit(pbi);
 394   do theora_read(pbi->opb,1,&ret);
 395   while (FrArrayDeCodeBlockRun(pbi,ret,&pbi->BitsLeft)==0);
 396
 397 }
 398
 399 static unsigned char GetNextBBit (PB_INSTANCE *pbi){
 400   long ret;
 401   if ( !pbi->BitsLeft ){
 402     /* Toggle the value.   */
 403     pbi->NextBit = ( pbi->NextBit == 1 ) ? 0 : 1;
 404
 405     /* Read next run */
 406     FrArrayDeCodeInit(pbi);
 407     do theora_read(pbi->opb,1,&ret);
 408     while (FrArrayDeCodeBlockRun(pbi,ret,&pbi->BitsLeft)==0);
 409
 410   }
 411
 412   /* Have  read a bit */
 413   pbi->BitsLeft--;
 414
 415   /* Return next bit value */
 416   return pbi->NextBit;
 417 }
 418
 419 static void GetNextSbInit(PB_INSTANCE *pbi){
 420   long ret;
 421
 422   theora_read(pbi->opb,1,&ret);
 423   pbi->NextBit = (unsigned char)ret;
 424
 425   /* Read run length */
 426   FrArrayDeCodeInit(pbi);
 427   do theora_read(pbi->opb,1,&ret);
 428   while (FrArrayDeCodeSBRun(pbi,ret,&pbi->BitsLeft)==0);
 429
 430 }
 431
 432 static unsigned char GetNextSbBit (PB_INSTANCE *pbi){
 433   long ret;
 434
 435   if ( !pbi->BitsLeft ){
 436     /* Toggle the value.   */
 437     pbi->NextBit = ( pbi->NextBit == 1 ) ? 0 : 1;
 438
 439     /* Read next run */
 440     FrArrayDeCodeInit(pbi);
 441     do theora_read(pbi->opb,1,&ret);
 442     while (FrArrayDeCodeSBRun(pbi,ret,&pbi->BitsLeft)==0);
 443
 444   }
 445
 446   /* Have  read a bit */
 447   pbi->BitsLeft--;
 448
 449   /* Return next bit value */
 450   return pbi->NextBit;
 451 }
 452
 453 void QuadDecodeDisplayFragments ( PB_INSTANCE *pbi ){
 454   ogg_uint32_t  SB, MB, B;
 455   int    DataToDecode;
 456
 457   ogg_int32_t   dfIndex;
 458   ogg_uint32_t  MBIndex = 0;
 459
 460   /* Reset various data structures common to key frames and inter frames. */
 461   pbi->CodedBlockIndex = 0;
 462   memset ( pbi->display_fragments, 0, pbi->UnitFragments );
 463
 464   /* For "Key frames" mark all blocks as coded and return. */
 465   /* Else initialise the ArrayPtr array to 0 (all blocks uncoded by default) */
 466   if ( GetFrameType(pbi) == KEY_FRAME ) {
 467     memset( pbi->SBFullyFlags, 1, pbi->SuperBlocks );
 468     memset( pbi->SBCodedFlags, 1, pbi->SuperBlocks );
 469         memset( pbi->MBCodedFlags, 0, pbi->MacroBlocks );
 470   }else{
 471     memset( pbi->SBFullyFlags, 0, pbi->SuperBlocks );
 472     memset( pbi->MBCodedFlags, 0, pbi->MacroBlocks );
 473
 474     /* Un-pack the list of partially coded Super-Blocks */
 475     GetNextSbInit(pbi);
 476     for( SB = 0; SB < pbi->SuperBlocks; SB++){
 477       pbi->SBCodedFlags[SB] = GetNextSbBit (pbi);
 478     }
 479
 480     /* Scan through the list of super blocks.  Unless all are marked
 481        as partially coded we have more to do. */
 482     DataToDecode = 0;
 483     for ( SB=0; SB<pbi->SuperBlocks; SB++ ) {
 484       if ( !pbi->SBCodedFlags[SB] ) {
 485         DataToDecode = 1;
 486         break;
 487       }
 488     }
 489
 490     /* Are there further block map bits to decode ? */
 491     if ( DataToDecode ) {
 492       /* Un-pack the Super-Block fully coded flags. */
 493       GetNextSbInit(pbi);
 494       for( SB = 0; SB < pbi->SuperBlocks; SB++) {
 495         /* Skip blocks already marked as partially coded */
 496         while( (SB < pbi->SuperBlocks) && pbi->SBCodedFlags[SB] )
 497           SB++;
 498
 499         if ( SB < pbi->SuperBlocks ) {
 500           pbi->SBFullyFlags[SB] = GetNextSbBit (pbi);
 501
 502           if ( pbi->SBFullyFlags[SB] )       /* If SB is fully coded. */
 503             pbi->SBCodedFlags[SB] = 1;       /* Mark the SB as coded */
 504         }
 505       }
 506     }
 507
 508     /* Scan through the list of coded super blocks.  If at least one
 509        is marked as partially coded then we have a block list to
 510        decode. */
 511     for ( SB=0; SB<pbi->SuperBlocks; SB++ ) {
 512       if ( pbi->SBCodedFlags[SB] && !pbi->SBFullyFlags[SB] ) {
 513         /* Initialise the block list decoder. */
 514         GetNextBInit(pbi);
 515         break;
 516       }
 517     }
 518   }
 519
 520   /* Decode the block data from the bit stream. */
 521   for ( SB=0; SB<pbi->SuperBlocks; SB++ ){
 522     for ( MB=0; MB<4; MB++ ){
 523       /* If MB is in the frame */
 524       if ( QuadMapToMBTopLeft(pbi->BlockMap, SB,MB) >= 0 ){
 525         /* Only read block level data if SB was fully or partially coded */
 526         if ( pbi->SBCodedFlags[SB] ) {
 527           for ( B=0; B<4; B++ ){
 528             /* If block is valid (in frame)... */
 529             dfIndex = QuadMapToIndex1( pbi->BlockMap, SB, MB, B );
 530             if ( dfIndex >= 0 ){
 531               if ( pbi->SBFullyFlags[SB] )
 532                 pbi->display_fragments[dfIndex] = 1;
 533               else
 534                 pbi->display_fragments[dfIndex] = GetNextBBit(pbi);
 535
 536               /* Create linear list of coded block indices */
 537               if ( pbi->display_fragments[dfIndex] ) {
 538                 pbi->MBCodedFlags[MBIndex] = 1;
 539                 pbi->CodedBlockList[pbi->CodedBlockIndex] = dfIndex;
 540                 pbi->CodedBlockIndex++;
 541               }
 542             }
 543           }
 544         }
 545         MBIndex++;
 546
 547       }
 548     }
 549   }
 550 }
 551
 552 CODING_MODE FrArrayUnpackMode(PB_INSTANCE *pbi){
 553   long ret;
 554   /* Coding scheme:
 555      Token                      Codeword           Bits
 556      Entry   0 (most frequent)  0                   1
 557      Entry   1                  10                  2
 558      Entry   2                  110                 3
 559      Entry   3                  1110                4
 560      Entry   4                  11110               5
 561      Entry   5                  111110              6
 562      Entry   6                  1111110             7
 563      Entry   7                  1111111             7
 564   */
 565
 566   /* Initialise the decoding. */
 567   pbi->bits_so_far = 0;
 568
 569   theora_read(pbi->opb,1,&ret);
 570   pbi->bit_pattern = ret;
 571
 572   /* Do we have a match */
 573   if ( pbi->bit_pattern == 0 )
 574     return (CODING_MODE)0;
 575
 576   /* Get the next bit */
 577   theora_read(pbi->opb,1,&ret);
 578   pbi->bit_pattern = (pbi->bit_pattern << 1) | ret;
 579
 580   /* Do we have a match */
 581   if ( pbi->bit_pattern == 0x0002 )
 582     return (CODING_MODE)1;
 583
 584   theora_read(pbi->opb,1,&ret);
 585   pbi->bit_pattern = (pbi->bit_pattern << 1) | ret;
 586
 587   /* Do we have a match  */
 588   if ( pbi->bit_pattern == 0x0006 )
 589     return (CODING_MODE)2;
 590
 591   theora_read(pbi->opb,1,&ret);
 592   pbi->bit_pattern = (pbi->bit_pattern << 1) | ret;
 593
 594   /* Do we have a match */
 595   if ( pbi->bit_pattern == 0x000E )
 596     return (CODING_MODE)3;
 597
 598   theora_read(pbi->opb,1,&ret);
 599   pbi->bit_pattern = (pbi->bit_pattern << 1) | ret;
 600
 601   /* Do we have a match */
 602   if ( pbi->bit_pattern == 0x001E )
 603     return (CODING_MODE)4;
 604
 605   theora_read(pbi->opb,1,&ret);
 606   pbi->bit_pattern = (pbi->bit_pattern << 1) | ret;
 607
 608   /* Do we have a match */
 609   if ( pbi->bit_pattern == 0x003E )
 610     return (CODING_MODE)5;
 611
 612   theora_read(pbi->opb,1,&ret);
 613   pbi->bit_pattern = (pbi->bit_pattern << 1) | ret;
 614
 615   /* Do we have a match */
 616   if ( pbi->bit_pattern == 0x007E )
 617     return (CODING_MODE)6;
 618   else
 619     return (CODING_MODE)7;
 620 }
 621