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 coeff_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"}


In general, all DCT coefficients are decoded using the same tree. However, if the preceding coefficient is a `DCT_0`, decoding will skip the first branch since it is not possible for `dct_eob` to follow a `DCT_0`.

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"}