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 section "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`).

Below 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  /* cat5 = "1111110", 
                               cat6 = "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"}