text_src/13.02__vp8-bitstream__coding-of-individual-coefficient-values.txt

#### 13.2 Coding of Individual Coefficient Values            {#h-13-02}


The coding of coefficient tokens is the same for the DCT and WHT and for the remainder of this chapter DCT should be taken to mean either DCT or WHT.

All tokens (except end-of-block) specify either a single unsigned value or a range of unsigned values (immediately) followed by a simple probabilistic encoding of the offset of the value from the base of that range.

Non-zero values (of either type) are then followed by a flag indicating the sign of the coded value (negative if `1`, positive if `0`).

Here are the tokens and decoding tree.


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
typedef enum
{
    DCT_0,      /* value 0 */
    DCT_1,      /* 1 */
    DCT_2,      /* 2 */
    DCT_3,      /* 3 */
    DCT_4,      /* 4 */
    dct_cat1,   /* range 5 - 6  (size 2) */
    dct_cat2,   /* 7 - 10   (4) */
    dct_cat3,   /* 11 - 18  (8) */
    dct_cat4,   /* 19 - 34  (16) */
    dct_cat5,   /* 35 - 66  (32) */
    dct_cat6,   /* 67 - 2048  (1982) */
    dct_eob,    /* end of block */

    num_dct_tokens   /* 12 */
}
dct_token;

const tree_index coef_tree [2 * (num_dct_tokens - 1)] =
{
 -dct_eob, 2,               /* eob = "0"   */
  -DCT_0, 4,                /* 0   = "10"  */
   -DCT_1, 6,               /* 1   = "110" */
    8, 12,
     -DCT_2, 10,            /* 2   = "11100" */
      -DCT_3, -DCT_4,       /* 3   = "111010", 4 = "111011" */
     14, 16,
      -dct_cat1, -dct_cat2, /* cat1 =  "111100", 
                               cat2 = "111101" */
     18, 20,
      -dct_cat3, -dct_cat4, /* cat3 = "1111100", 
                               cat4 = "1111101" */
      -dct_cat5, -dct_cat6  /* cat4 = "1111110", 
                               cat4 = "1111111" */
};
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
{:lang="c"}


While in general all DCT coefficients are decoded using the same tree, decoding of certain DCT coefficients may skip the first branch, whose preceding coefficient is a `DCT_0`. This makes use of the fact that in any block last non zero coefficient before the end of the block is not `0`, therefore no `dct_eob` follows a `DCT_0` coefficient in any block.

The tokens `dct_cat1` ... `dct_cat6` specify ranges of unsigned values, the value within the range being formed by adding an unsigned offset (whose width is 1, 2, 3, 4, 5, or 11 bits, respectively) to the base of the range, using the following algorithm and fixed probability tables.


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
uint DCTextra( bool_decoder *d, const Prob *p)
{
    uint v = 0;
    do { v += v + read_bool( d, *p);}  while( *++p);
    return v;
}

const Prob Pcat1[] = { 159, 0};
const Prob Pcat2[] = { 165, 145, 0};
const Prob Pcat3[] = { 173, 148, 140, 0};
const Prob Pcat4[] = { 176, 155, 140, 135, 0};
const Prob Pcat5[] = { 180, 157, 141, 134, 130, 0};
const Prob Pcat6[] =
    { 254, 254, 243, 230, 196, 177, 153, 140, 133, 130, 129, 0};
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
{:lang="c"}


If `v`, the unsigned value decoded using the coefficient tree, possibly augmented by the process above, is non-zero, its sign is set by simply reading a flag:


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
if( read_bool( d, 128))
    v = -v;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
{:lang="c"}