tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 6386

 
 
 

VP8 Data Format and Decoding Guide

Part 3 of 11, p. 41 to 76
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 41 
10.  Segment-Based Feature Adjustments

   Every macroblock may optionally override some of the default
   behaviors of the decoder.  Specifically, VP8 uses segment-based
   adjustments to support changing quantizer level and loop filter level
   for a macroblock.  When the segment-based adjustment feature is
   enabled for a frame, each macroblock within the frame is coded with a
   segment_id.  This effectively segments all the macroblocks in the
   current frame into a number of different segments.  Macroblocks
   within the same segment behave exactly the same for quantizer and
   loop filter level adjustments.

   If both the segmentation_enabled and update_mb_segmentation_map flags
   in subsection B of the frame header take a value of 1, the prediction
   data for each (intra- or inter-coded) macroblock begins with a
   specification of segment_id for the current macroblock.  It is
   decoded using this simple tree ...

Top      Up      ToC       Page 42 
   ---- Begin code block --------------------------------------

   const tree_index mb_segment_tree [2 * (4-1)] =
     {
       2,  4,     /* root: "0", "1" subtrees */
       -0, -1,    /* "00" = 0th value, "01" = 1st value */
        -2, -3    /* "10" = 2nd value, "11" = 3rd value */
     }

   ---- End code block ----------------------------------------

   ... combined with a 3-entry probability table,
   mb_segment_tree_probs[3].  The macroblock's segment_id is used later
   in the decoding process to look into the segment_feature_data table
   and determine how the quantizer and loop filter levels are adjusted.

   The decoding of segment_id, together with the parsing of
   intra-prediction modes (which is taken up next), is implemented in
   the reference decoder file modemv.c.

11.  Key Frame Macroblock Prediction Records

   After specifying the features described above, the macroblock
   prediction record next specifies the prediction mode used for the
   macroblock.

11.1.  mb_skip_coeff

   The single bool flag is decoded using prob_skip_false if and only if
   mb_no_skip_coeff is set to 1 (see Sections 9.10 and 9.11).  If
   mb_no_skip_coeff is set to 0, then this value defaults to 0.

11.2.  Luma Modes

   First comes the luma specification of type intra_mbmode, coded using
   the kf_ymode_tree, as described in Section 8 and repeated here for
   convenience:

Top      Up      ToC       Page 43 
   ---- Begin code block --------------------------------------

   typedef enum
   {
       DC_PRED, /* predict DC using row above and column to the left */
       V_PRED,  /* predict rows using row above */
       H_PRED,  /* predict columns using column to the left */
       TM_PRED, /* propagate second differences a la "True Motion" */

       B_PRED,  /* each Y subblock is independently predicted */

       num_uv_modes = B_PRED,  /* first four modes apply to chroma */
       num_ymodes   /* all modes apply to luma */
   }
   intra_mbmode;

   const tree_index kf_ymode_tree [2 * (num_ymodes - 1)] =
   {
    -B_PRED, 2,            /* root: B_PRED = "0", "1" subtree */
     4, 6,                 /* "1" subtree has 2 descendant subtrees */
      -DC_PRED, -V_PRED,   /* "10" subtree: DC_PRED = "100",
                              V_PRED = "101" */
      -H_PRED, -TM_PRED    /* "11" subtree: H_PRED = "110",
                              TM_PRED = "111" */
   };

   ---- End code block ----------------------------------------

   For key frames, the Y mode is decoded using a fixed probability array
   as follows:

   ---- Begin code block --------------------------------------

   const Prob kf_ymode_prob [num_ymodes - 1] = { 145, 156, 163, 128};
   Ymode = (intra_mbmode) treed_read(d, kf_ymode_tree, kf_ymode_prob);

   ---- End code block ----------------------------------------

   d is of course the bool_decoder being used to read the first data
   partition.

   If the Ymode is B_PRED, it is followed by a (tree-coded) mode for
   each of the 16 Y subblocks.  The 10 subblock modes and their coding
   tree are as follows:

Top      Up      ToC       Page 44 
   ---- Begin code block --------------------------------------

   typedef enum
   {
       B_DC_PRED,  /* predict DC using row above and column
                      to the left */
       B_TM_PRED,  /* propagate second differences a la
                      "True Motion" */

       B_VE_PRED,  /* predict rows using row above */
       B_HE_PRED,  /* predict columns using column to the left */

       B_LD_PRED,  /* southwest (left and down) 45 degree diagonal
                      prediction */
       B_RD_PRED,  /* southeast (right and down) "" */

       B_VR_PRED,  /* SSE (vertical right) diagonal prediction */
       B_VL_PRED,  /* SSW (vertical left) "" */
       B_HD_PRED,  /* ESE (horizontal down) "" */
       B_HU_PRED,  /* ENE (horizontal up) "" */

       num_intra_bmodes
   }
   intra_bmode;

   /* Coding tree for the above, with implied codings as comments */

   const tree_index bmode_tree [2 * (num_intra_bmodes - 1)] =
   {
    -B_DC_PRED, 2,                   /* B_DC_PRED = "0" */
     -B_TM_PRED, 4,                  /* B_TM_PRED = "10" */
      -B_VE_PRED, 6,                 /* B_VE_PRED = "110" */
       8, 12,
        -B_HE_PRED, 10,              /* B_HE_PRED = "11100" */
         -B_RD_PRED, -B_VR_PRED,     /* B_RD_PRED = "111010",
                                        B_VR_PRED = "111011" */
        -B_LD_PRED, 14,              /* B_LD_PRED = "111110" */
          -B_VL_PRED, 16,            /* B_VL_PRED = "1111110" */
            -B_HD_PRED, -B_HU_PRED   /* HD = "11111110",
                                        HU = "11111111" */
   };

   ---- End code block ----------------------------------------

   The first four modes are smaller versions of the similarly named
   16x16 modes above, albeit with slightly different numbering.  The
   last six "diagonal" modes are unique to luma subblocks.

Top      Up      ToC       Page 45 
11.3.  Subblock Mode Contexts

   The coding of subblock modes in key frames uses the modes already
   coded for the subblocks to the left of and above the subblock to
   select a probability array for decoding the current subblock mode.
   This is our first instance of contextual prediction, and there are
   several caveats associated with it:

   1.  The adjacency relationships between subblocks are based on the
       normal default raster placement of the subblocks.

   2.  The adjacent subblocks need not lie in the current macroblock.
       The subblocks to the left of the left-edge subblocks 0, 4, 8, and
       12 are the right-edge subblocks 3, 7, 11, and 15, respectively,
       of the (already coded) macroblock immediately to the left.
       Similarly, the subblocks above the top-edge subblocks 0, 1, 2,
       and 3 are the bottom-edge subblocks 12, 13, 14, and 15 of the
       already-coded macroblock immediately above us.

   3.  For macroblocks on the top row or left edge of the image, some of
       the predictors will be non-existent.  Such predictors are taken
       to have had the value B_DC_PRED, which, perhaps conveniently,
       takes the value 0 in the enumeration above.  A simple management
       scheme for these contexts might maintain a row of above
       predictors and four left predictors.  Before decoding the frame,
       the entire row is initialized to B_DC_PRED; before decoding each
       row of macroblocks, the four left predictors are also set to
       B_DC_PRED.  After decoding a macroblock, the bottom four subblock
       modes are copied into the row predictor (at the current position,
       which then advances to be above the next macroblock), and the
       right four subblock modes are copied into the left predictor.

   4.  Many macroblocks will of course be coded using a 16x16 luma
       prediction mode.  For the purpose of predicting ensuing subblock
       modes (only), such macroblocks derive a subblock mode, constant
       throughout the macroblock, from the 16x16 luma mode as follows:
       DC_PRED uses B_DC_PRED, V_PRED uses B_VE_PRED, H_PRED uses
       B_HE_PRED, and TM_PRED uses B_TM_PRED.

   5.  Although we discuss interframe modes in Section 16, we remark
       here that, while interframes do use all the intra-coding modes
       described here and below, the subblock modes in an interframe are
       coded using a single constant probability array that does not
       depend on any context.

   The dependence of subblock mode probability on the nearby subblock
   mode context is most easily handled using a three-dimensional
   constant array:

Top      Up      ToC       Page 46 
   ---- Begin code block --------------------------------------

   const Prob kf_bmode_prob [num_intra_bmodes] [num_intra_bmodes]
     [num_intra_bmodes-1];

   ---- End code block ----------------------------------------

   The outer two dimensions of this array are indexed by the already-
   coded subblock modes above and to the left of the current block,
   respectively.  The inner dimension is a typical tree probability list
   whose indices correspond to the even indices of the bmode_tree above.
   The mode for the j^(th) luma subblock is then

   ---- Begin code block --------------------------------------

   Bmode = (intra_bmode) treed_read(d, bmode_tree, kf_bmode_prob
     [A] [L]);

   ---- End code block ----------------------------------------

   Where the 4x4 Y subblock index j varies from 0 to 15 in raster order,
   and A and L are the modes used above and to the left of the j^(th)
   subblock.

   The contents of the kf_bmode_prob array are given at the end of this
   section.

11.4.  Chroma Modes

   After the Y mode (and optional subblock mode) specification comes the
   chroma mode.  The chroma modes are a subset of the Y modes and are
   coded using the uv_mode_tree, as described in Section 8 and repeated
   here for convenience:

   ---- Begin code block --------------------------------------

   const tree_index uv_mode_tree [2 * (num_uv_modes - 1)] =
   {
    -DC_PRED, 2,           /* root: DC_PRED = "0", "1" subtree */
     -V_PRED, 4,           /* "1" subtree:  V_PRED = "10",
                              "11" subtree */
      -H_PRED, -TM_PRED    /* "11" subtree: H_PRED = "110",
                              TM_PRED = "111" */
   };

   ---- End code block ----------------------------------------

Top      Up      ToC       Page 47 
   As for the Y modes (in a key frame), the chroma modes are coded using
   a fixed, contextless probability table:

   ---- Begin code block --------------------------------------

   const Prob kf_uv_mode_prob [num_uv_modes - 1] = { 142, 114, 183};
   uv_mode = (intra_mbmode) treed_read(d, uv_mode_tree,
     kf_uv_mode_prob);

   ---- End code block ----------------------------------------

   This completes the description of macroblock prediction coding for
   key frames.  As will be discussed in Section 16, the coding of intra
   modes within interframes is similar, but not identical, to that
   described here (and in the reference code) for prediction modes and,
   indeed, for all tree-coded data in VP8.

11.5.  Subblock Mode Probability Table

   Finally, here is the fixed probability table used to decode subblock
   modes in key frames.

   ---- Begin code block --------------------------------------

   const Prob kf_bmode_prob [num_intra_bmodes] [num_intra_bmodes]
     [num_intra_bmodes-1] =
   {
     {
       { 231, 120,  48,  89, 115, 113, 120, 152, 112},
       { 152, 179,  64, 126, 170, 118,  46,  70,  95},
       { 175,  69, 143,  80,  85,  82,  72, 155, 103},
       {  56,  58,  10, 171, 218, 189,  17,  13, 152},
       { 144,  71,  10,  38, 171, 213, 144,  34,  26},
       { 114,  26,  17, 163,  44, 195,  21,  10, 173},
       { 121,  24,  80, 195,  26,  62,  44,  64,  85},
       { 170,  46,  55,  19, 136, 160,  33, 206,  71},
       {  63,  20,   8, 114, 114, 208,  12,   9, 226},
       {  81,  40,  11,  96, 182,  84,  29,  16,  36}
     },

Top      Up      ToC       Page 48 
     {
       { 134, 183,  89, 137,  98, 101, 106, 165, 148},
       {  72, 187, 100, 130, 157, 111,  32,  75,  80},
       {  66, 102, 167,  99,  74,  62,  40, 234, 128},
       {  41,  53,   9, 178, 241, 141,  26,   8, 107},
       { 104,  79,  12,  27, 217, 255,  87,  17,   7},
       {  74,  43,  26, 146,  73, 166,  49,  23, 157},
       {  65,  38, 105, 160,  51,  52,  31, 115, 128},
       {  87,  68,  71,  44, 114,  51,  15, 186,  23},
       {  47,  41,  14, 110, 182, 183,  21,  17, 194},
       {  66,  45,  25, 102, 197, 189,  23,  18,  22}
     },
     {
       {  88,  88, 147, 150,  42,  46,  45, 196, 205},
       {  43,  97, 183, 117,  85,  38,  35, 179,  61},
       {  39,  53, 200,  87,  26,  21,  43, 232, 171},
       {  56,  34,  51, 104, 114, 102,  29,  93,  77},
       { 107,  54,  32,  26,  51,   1,  81,  43,  31},
       {  39,  28,  85, 171,  58, 165,  90,  98,  64},
       {  34,  22, 116, 206,  23,  34,  43, 166,  73},
       {  68,  25, 106,  22,  64, 171,  36, 225, 114},
       {  34,  19,  21, 102, 132, 188,  16,  76, 124},
       {  62,  18,  78,  95,  85,  57,  50,  48,  51}
     },
     {
       { 193, 101,  35, 159, 215, 111,  89,  46, 111},
       {  60, 148,  31, 172, 219, 228,  21,  18, 111},
       { 112, 113,  77,  85, 179, 255,  38, 120, 114},
       {  40,  42,   1, 196, 245, 209,  10,  25, 109},
       { 100,  80,   8,  43, 154,   1,  51,  26,  71},
       {  88,  43,  29, 140, 166, 213,  37,  43, 154},
       {  61,  63,  30, 155,  67,  45,  68,   1, 209},
       { 142,  78,  78,  16, 255, 128,  34, 197, 171},
       {  41,  40,   5, 102, 211, 183,   4,   1, 221},
       {  51,  50,  17, 168, 209, 192,  23,  25,  82}
     },
     {
       { 125,  98,  42,  88, 104,  85, 117, 175,  82},
       {  95,  84,  53,  89, 128, 100, 113, 101,  45},
       {  75,  79, 123,  47,  51, 128,  81, 171,   1},
       {  57,  17,   5,  71, 102,  57,  53,  41,  49},
       { 115,  21,   2,  10, 102, 255, 166,  23,   6},
       {  38,  33,  13, 121,  57,  73,  26,   1,  85},
       {  41,  10,  67, 138,  77, 110,  90,  47, 114},
       { 101,  29,  16,  10,  85, 128, 101, 196,  26},
       {  57,  18,  10, 102, 102, 213,  34,  20,  43},
       { 117,  20,  15,  36, 163, 128,  68,   1,  26}
     },

Top      Up      ToC       Page 49 
     {
       { 138,  31,  36, 171,  27, 166,  38,  44, 229},
       {  67,  87,  58, 169,  82, 115,  26,  59, 179},
       {  63,  59,  90, 180,  59, 166,  93,  73, 154},
       {  40,  40,  21, 116, 143, 209,  34,  39, 175},
       {  57,  46,  22,  24, 128,   1,  54,  17,  37},
       {  47,  15,  16, 183,  34, 223,  49,  45, 183},
       {  46,  17,  33, 183,   6,  98,  15,  32, 183},
       {  65,  32,  73, 115,  28, 128,  23, 128, 205},
       {  40,   3,   9, 115,  51, 192,  18,   6, 223},
       {  87,  37,   9, 115,  59,  77,  64,  21,  47}
     },
     {
       { 104,  55,  44, 218,   9,  54,  53, 130, 226},
       {  64,  90,  70, 205,  40,  41,  23,  26,  57},
       {  54,  57, 112, 184,   5,  41,  38, 166, 213},
       {  30,  34,  26, 133, 152, 116,  10,  32, 134},
       {  75,  32,  12,  51, 192, 255, 160,  43,  51},
       {  39,  19,  53, 221,  26, 114,  32,  73, 255},
       {  31,   9,  65, 234,   2,  15,   1, 118,  73},
       {  88,  31,  35,  67, 102,  85,  55, 186,  85},
       {  56,  21,  23, 111,  59, 205,  45,  37, 192},
       {  55,  38,  70, 124,  73, 102,   1,  34,  98}
     },
     {
       { 102,  61,  71,  37,  34,  53,  31, 243, 192},
       {  69,  60,  71,  38,  73, 119,  28, 222,  37},
       {  68,  45, 128,  34,   1,  47,  11, 245, 171},
       {  62,  17,  19,  70, 146,  85,  55,  62,  70},
       {  75,  15,   9,   9,  64, 255, 184, 119,  16},
       {  37,  43,  37, 154, 100, 163,  85, 160,   1},
       {  63,   9,  92, 136,  28,  64,  32, 201,  85},
       {  86,   6,  28,   5,  64, 255,  25, 248,   1},
       {  56,   8,  17, 132, 137, 255,  55, 116, 128},
       {  58,  15,  20,  82, 135,  57,  26, 121,  40}
     },
     {
       { 164,  50,  31, 137, 154, 133,  25,  35, 218},
       {  51, 103,  44, 131, 131, 123,  31,   6, 158},
       {  86,  40,  64, 135, 148, 224,  45, 183, 128},
       {  22,  26,  17, 131, 240, 154,  14,   1, 209},
       {  83,  12,  13,  54, 192, 255,  68,  47,  28},
       {  45,  16,  21,  91,  64, 222,   7,   1, 197},
       {  56,  21,  39, 155,  60, 138,  23, 102, 213},
       {  85,  26,  85,  85, 128, 128,  32, 146, 171},
       {  18,  11,   7,  63, 144, 171,   4,   4, 246},
       {  35,  27,  10, 146, 174, 171,  12,  26, 128}
     },

Top      Up      ToC       Page 50 
     {
       { 190,  80,  35,  99, 180,  80, 126,  54,  45},
       {  85, 126,  47,  87, 176,  51,  41,  20,  32},
       { 101,  75, 128, 139, 118, 146, 116, 128,  85},
       {  56,  41,  15, 176, 236,  85,  37,   9,  62},
       { 146,  36,  19,  30, 171, 255,  97,  27,  20},
       {  71,  30,  17, 119, 118, 255,  17,  18, 138},
       { 101,  38,  60, 138,  55,  70,  43,  26, 142},
       { 138,  45,  61,  62, 219,   1,  81, 188,  64},
       {  32,  41,  20, 117, 151, 142,  20,  21, 163},
       { 112,  19,  12,  61, 195, 128,  48,   4,  24}
     }
   };

   ---- End code block ----------------------------------------

12.  Intraframe Prediction

   Intraframe prediction uses already-coded macroblocks within the
   current frame to approximate the contents of the current macroblock.
   It applies to intra-coded macroblocks in an interframe and to all
   macroblocks in a key frame.

   Relative to the current macroblock "M", the already-coded macroblocks
   include all macroblocks above M together with the macroblocks on the
   same row as, and to the left of, M, though at most four of these
   macroblocks are actually used: the block "A" directly above M, the
   blocks immediately to the left and right of A, and the block
   immediately to the left of M.

   Each of the prediction modes (i.e., means of extrapolation from
   already-calculated values) uses fairly simple arithmetic on pixel
   values whose positions, relative to the current position, are defined
   by the mode.

   The chroma (U and V) and luma (Y) predictions are independent of each
   other.

   The relative addressing of pixels applied to macroblocks on the upper
   row or left column of the frame will sometimes cause pixels outside
   the visible frame to be referenced.  Usually such out-of-bounds
   pixels have an assumed value of 129 for pixels to the left of the
   leftmost column of the visible frame and 127 for pixels above the top
   row of the visible frame (including the special case of the pixel
   above and to the left of the top-left pixel in the visible frame).
   Exceptions to this (associated to certain modes) will be noted below.

Top      Up      ToC       Page 51 
   The already-coded macroblocks referenced by intra-prediction have
   been "reconstructed", that is, have been predicted and residue-
   adjusted (as described in Section 14), but have not been loop-
   filtered.  While it does process the edges between individual
   macroblocks and individual subblocks, loop filtering (described in
   Section 15) is applied to the frame as a whole, after all of the
   macroblocks have been reconstructed.

12.1.  mb_skip_coeff

   The single bool flag is decoded using prob_skip_false if and only if
   mb_no_skip_coeff is set to 1 (see Sections 9.10 and 9.11).  If
   mb_no_skip_coeff is set to 0, then this value defaults to 0.

12.2.  Chroma Prediction

   The chroma prediction is a little simpler than the luma prediction,
   so we treat it first.  Each of the chroma modes treats U and V
   identically; that is, the U and V prediction values are calculated in
   parallel, using the same relative addressing and arithmetic in each
   of the two planes.

   The modes extrapolate prediction values using the 8-pixel row "A"
   lying immediately above the block (that is, the bottom chroma row of
   the macroblock immediately above the current macroblock) and the
   8-pixel column "L" immediately to the left of the block (that is, the
   rightmost chroma column of the macroblock immediately to the left of
   the current macroblock).

   Vertical prediction (chroma mode V_PRED) simply fills each 8-pixel
   row of the 8x8 chroma block with a copy of the "above" row (A).  If
   the current macroblock lies on the top row of the frame, all 8 of the
   pixel values in A are assigned the value 127.

   Similarly, horizontal prediction (H_PRED) fills each 8-pixel column
   of the 8x8 chroma block with a copy of the "left" column (L).  If the
   current macroblock is in the left column of the frame, all 8 pixel
   values in L are assigned the value 129.

   DC prediction (DC_PRED) fills the 8x8 chroma block with a single
   value.  In the generic case of a macroblock lying below the top row
   and right of the leftmost column of the frame, this value is the
   average of the 16 (genuinely visible) pixels in the (union of the)
   above row A and left column L.

   Otherwise, if the current macroblock lies on the top row of the
   frame, the average of the 8 pixels in L is used; if it lies in the
   left column of the frame, the average of the 8 pixels in A is used.

Top      Up      ToC       Page 52 
   Note that the averages used in these exceptional cases are not the
   same as those that would be arrived at by using the out-of-bounds A
   and L values defined for V_PRED and H_PRED.  In the case of the
   leftmost macroblock on the top row of the frame, the 8x8 block is
   simply filled with the constant value 128.

   For DC_PRED, apart from the exceptional case of the top-left
   macroblock, we are averaging either 16 or 8 pixel values to get a
   single prediction value that fills the 8x8 block.  The rounding is
   done as follows:

   ---- Begin code block --------------------------------------

   int sum;  /* sum of 8 or 16 pixels at (at least) 16-bit precision */
   int shf;  /* base 2 logarithm of the number of pixels (3 or 4) */

   Pixel DCvalue = (sum + (1 << (shf-1))) >> shf;

   ---- End code block ----------------------------------------

   Because the summands are all valid pixels, no "clamp" is necessary in
   the calculation of DCvalue.

   The remaining "True Motion" (TM_PRED) chroma mode gets its name from
   an older technique of video compression used by On2 Technologies, to
   which it bears some relation.  In addition to the row "A" and column
   "L", TM_PRED uses the pixel "P" above and to the left of the chroma
   block.

Top      Up      ToC       Page 53 
   The following figure gives an example of how TM_PRED works:

   ---- Begin code block --------------------------------------

   |-----|-----|-----|-----|-----|-----|-----|-----|-----|
   | P   | A0  | A1  | A2  | A3  | A4  | A5  | A6  | A7  |
   |-----|-----|-----|-----|-----|-----|-----|-----|-----|
   | L0  | X00 | X01 | X02 | X03 | X04 | X05 | X06 | X07 |
   |-----|-----|-----|-----|-----|-----|-----|-----|-----|
   | L1  | X10 | X11 | X12 | X13 | X14 | X15 | X16 | X17 |
   |-----|-----|-----|-----|-----|-----|-----|-----|-----|
   | L2  | X20 | X21 | X22 | X23 | X24 | X25 | X26 | X27 |
   |-----|-----|-----|-----|-----|-----|-----|-----|-----|
   | L3  | X30 | X31 | X32 | X33 | X34 | X35 | X36 | X37 |
   |-----|-----|-----|-----|-----|-----|-----|-----|-----|
   | L4  | X40 | X41 | X42 | X43 | X44 | X45 | X46 | X47 |
   |-----|-----|-----|-----|-----|-----|-----|-----|-----|
   | L5  | X50 | X51 | X52 | X53 | X54 | X55 | X56 | X57 |
   |-----|-----|-----|-----|-----|-----|-----|-----|-----|
   | L6  | X60 | X61 | X62 | X63 | X64 | X65 | X66 | X67 |
   |-----|-----|-----|-----|-----|-----|-----|-----|-----|
   | L7  | X70 | X71 | X72 | X73 | X74 | X75 | X76 | X77 |
   |-----|-----|-----|-----|-----|-----|-----|-----|-----|

   ---- End code block ----------------------------------------

   Where P, As, and Ls represent reconstructed pixel values from
   previously coded blocks, and X00 through X77 represent predicted
   values for the current block.  TM_PRED uses the following equation to
   calculate X_ij:

   X_ij = L_i + A_j - P (i, j=0, 1, 2, 3)

Top      Up      ToC       Page 54 
   The exact algorithm is as follows:

   ---- Begin code block --------------------------------------

   void TMpred(
       Pixel b[8][8],      /* chroma (U or V) prediction block */
       const Pixel A[8],   /* row of already-constructed pixels
                              above block */
       const Pixel L[8],   /* column of "" just to the left of
                              block */
       const Pixel P       /* pixel just to the left of A and
                              above L*/
   ) {
       int r = 0;          /* row */
       do {
           int c = 0;      /* column */
           do {
               b[r][c] = clamp255(L[r]+ A[c] - P);
           } while (++c < 8);
       } while (++r < 8);
   }

   ---- End code block ----------------------------------------

   Note that the process could equivalently be described as propagating
   the vertical differences between pixels in L (starting from P), using
   the pixels from A to start each column.

   An implementation of chroma intra-prediction may be found in the
   reference decoder file predict.c (Section 20.14).

   Unlike DC_PRED, for macroblocks on the top row or left edge, TM_PRED
   does use the out-of-bounds values of 127 and 129 (respectively)
   defined for V_PRED and H_PRED.

12.3.  Luma Prediction

   The prediction processes for the first four 16x16 luma modes
   (DC_PRED, V_PRED, H_PRED, and TM_PRED) are essentially identical to
   the corresponding chroma prediction processes described above, the
   only difference being that we are predicting a single 16x16 luma
   block instead of two 8x8 chroma blocks.

   Thus, the row "A" and column "L" here contain 16 pixels, the DC
   prediction is calculated using 16 or 32 pixels (and shf is 4 or 5),
   and we of course fill the entire prediction buffer, that is, 16 rows
   (or columns) containing 16 pixels each.  The reference implementation
   of 16x16 luma prediction is also in predict.c.

Top      Up      ToC       Page 55 
   In the remaining luma mode (B_PRED), each 4x4 Y subblock is
   independently predicted using one of ten modes (listed, along with
   their encodings, in Section 11).

   Also, unlike the full-macroblock modes already described, some of the
   subblock modes use prediction pixels above and to the right of the
   current subblock.  In detail, each 4x4 subblock "B" is predicted
   using (at most) the 4-pixel column "L" immediately to the left of B
   and the 8-pixel row "A" immediately above B, consisting of the 4
   pixels above B followed by the 4 adjacent pixels above and to the
   right of B, together with the single pixel "P" immediately to the
   left of A (and immediately above L).

   For the purpose of subblock intra-prediction, the pixels immediately
   to the left and right of a pixel in a subblock are the same as the
   pixels immediately to the left and right of the corresponding pixel
   in the frame buffer "F".  Vertical offsets behave similarly: The
   above row A lies immediately above B in F, and the adjacent pixels in
   the left column L are separated by a single row in F.

   Because entire macroblocks (as opposed to their constituent
   subblocks) are reconstructed in raster-scan order, for subblocks
   lying along the right edge (and not along the top row) of the current
   macroblock, the four "extra" prediction pixels in A above and to the
   right of B have not yet actually been constructed.

   Subblocks 7, 11, and 15 are affected.  All three of these subblocks
   use the same extra pixels as does subblock 3 (at the upper right
   corner of the macroblock), namely the 4 pixels immediately above and
   to the right of subblock 3.  Writing (R,C) for a frame buffer
   position offset from the upper left corner of the current macroblock
   by R rows and C columns, the extra pixels for all the right-edge
   subblocks (3, 7, 11, and 15) are at positions (-1,16), (-1,17),
   (-1,18), and (-1,19).  For the rightmost macroblock in each
   macroblock row except the top row, the extra pixels shall use the
   same value as the pixel at position (-1,15), which is the rightmost
   visible pixel on the line immediately above the macroblock row.  For
   the top macroblock row, all the extra pixels assume a value of 127.

   The details of the prediction modes are most easily described in
   code.

Top      Up      ToC       Page 56 
   ---- Begin code block --------------------------------------

   /* Result pixels are often averages of two or three predictor
      pixels.  The following subroutines are used to calculate
      these averages.  Because the arguments are valid pixels, no
      clamping is necessary.  An actual implementation would
      probably use inline functions or macros. */

   /* Compute weighted average centered at y w/adjacent x, z */

   Pixel avg3(Pixel x, Pixel y, Pixel z) {
     return (x + y + y + z + 2) >> 2;}

   /* Weighted average of 3 adjacent pixels centered at p */

   Pixel avg3p(const Pixel *p) { return avg3(p[-1], p[0], p[1]);}

   /* Simple average of x and y */

   Pixel avg2(Pixel x, Pixel y) { return (x + y + 1) >> 1;}

   /* Average of p[0] and p[1] may be considered to be a synthetic
      pixel lying between the two, that is, one half-step past p. */

   Pixel avg2p(const Pixel *p) { return avg2(p[0], p[1]);}

   void subblock_intra_predict(
       Pixel B[4][4],     /* Y subblock prediction buffer */
       const Pixel *A,    /* A[0]...A[7] = above row, A[-1] = P */
       const Pixel *L,    /* L[0]...L[3] = left column, L[-1] = P */
       intra_bmode mode   /* enum is in Section 11.2 */
   ) {
       Pixel E[9];        /* 9 already-constructed edge pixels */
       E[0] = L[3];  E[1] = L[2];  E[2] = L[1];  E[3] = L[0];
       E[4] = A[-1];      /* == L[-1] == P */
       E[5] = A[0];  E[6] = A[1];  E[7] = A[2];  E[8] = A[3];

     switch(mode) {
       /* First four modes are similar to corresponding
          full-block modes. */

       case B_DC_PRED:
       {
           int v = 4;      /* DC sum/avg, 4 is rounding adjustment */
           int i = 0;  do { v += A[i] + L[i];}  while (++i < 4);
           v >>= 3;        /* averaging 8 pixels */
           i = 0;  do {    /* fill prediction buffer with constant DC
                              value */

Top      Up      ToC       Page 57 
               int j = 0;  do { B[i][j] = v;}  while (++j < 4);
           } while (++i < 4);
           break;
       }

       case B_TM_PRED: /* just like 16x16 TM_PRED */
       {
           int r = 0;  do {
               int c = 0;  do {
                   B[r][c] = clamp255(L[r] + A[c] - A[-1]);
               } while (++c < 4);
           } while (++r < 4);
           break;
       }

       case B_VE_PRED: /* like 16x16 V_PRED except using averages */
       {
           int c = 0;  do { /* all 4 rows = smoothed top row */
               B[0][c] = B[1][c] = B[2][c] = B[3][c] = avg3p(A + c);
           } while (++c < 4);
           break;
       }

       case B_HE_PRED: /* like 16x16 H_PRED except using averages */
       {
           /* Bottom row is exceptional because L[4] does not exist */
           int v = avg3(L[2], L[3], L[3]);
           int r = 3;  while (1) {  /* all 4 columns = smoothed left
                                       column */
               B[r][0] = B[r][1] = B[r][2] = B[r][3] = v;
               if (--r < 0)
                   break;
               v = avg3p(L + r);  /* upper 3 rows use average of
                                      3 pixels */
           }
           break;
       }

       /* The remaining six "diagonal" modes subdivide the
          prediction buffer into diagonal lines.  All the pixels
          on each line are assigned the same value; this value is
          (a smoothed or synthetic version of) an
          already-constructed predictor value lying on the same
          line.  For clarity, in the comments, we express the
          positions of these predictor pixels relative to the
          upper left corner of the destination array B.

Top      Up      ToC       Page 58 
          These modes are unique to subblock prediction and have
          no full-block analogs.  The first two use lines at
          +|- 45 degrees from horizontal (or, equivalently,
          vertical), that is, lines whose slopes are +|- 1. */

       case B_LD_PRED:    /* southwest (left and down) step =
                             (-1, 1) or (1,-1) */
           /* avg3p(A + j) is the "smoothed" pixel at (-1,j) */
           B[0][0] = avg3p(A + 1);
           B[0][1] = B[1][0] = avg3p(A + 2);
           B[0][2] = B[1][1] = B[2][0] = avg3p(A + 3);
           B[0][3] = B[1][2] = B[2][1] = B[3][0] = avg3p(A + 4);
           B[1][3] = B[2][2] = B[3][1] = avg3p(A + 5);
           B[2][3] = B[3][2] = avg3p(A + 6);
           B[3][3] = avg3(A[6], A[7], A[7]); /* A[8] does not exist */
           break;

       case B_RD_PRED: /* southeast (right and down) step =
                          (1,1) or (-1,-1) */
           B[3][0] = avg3p(E + 1);  /* predictor is from (2, -1) */
           B[3][1] = B[2][0] = avg3p(E + 2);  /* (1, -1) */
           B[3][2] = B[2][1] = B[1][0] = avg3p(E + 3);  /* (0, -1) */
           B[3][3] = B[2][2] = B[1][1] = B[0][0] =
             avg3p(E + 4);  /* (-1, -1) */
           B[2][3] = B[1][2] = B[0][1] = avg3p(E + 5);  /* (-1, 0) */
           B[1][3] = B[0][2] = avg3p(E + 6);  /* (-1, 1) */
           B[0][3] = avg3p(E + 7);  /* (-1, 2) */
           break;

       /* The remaining 4 diagonal modes use lines whose slopes are
          +|- 2 and +|- 1/2.  The angles of these lines are roughly
          +|- 27 degrees from horizontal or vertical.

          Unlike the 45 degree diagonals, here we often need to
          "synthesize" predictor pixels midway between two actual
          predictors using avg2p(p), which we think of as returning
          the pixel "at" p[1/2]. */

       case B_VR_PRED:    /* SSE (vertical right) step =
                             (2,1) or (-2,-1) */
           B[3][0] = avg3p(E + 2);  /* predictor is from (1, -1) */
           B[2][0] = avg3p(E + 3);  /* (0, -1) */
           B[3][1] = B[1][0] = avg3p(E + 4);  /* (-1,   -1) */
           B[2][1] = B[0][0] = avg2p(E + 4);  /* (-1, -1/2) */
           B[3][2] = B[1][1] = avg3p(E + 5);  /* (-1,    0) */
           B[2][2] = B[0][1] = avg2p(E + 5);  /* (-1,  1/2) */
           B[3][3] = B[1][2] = avg3p(E + 6);  /* (-1,    1) */
           B[2][3] = B[0][2] = avg2p(E + 6);  /* (-1,  3/2) */

Top      Up      ToC       Page 59 
           B[1][3] = avg3p(E + 7);  /* (-1, 2) */
           B[0][3] = avg2p(E + 7);  /* (-1, 5/2) */
           break;

       case B_VL_PRED:    /* SSW (vertical left) step =
                             (2,-1) or (-2,1) */
           B[0][0] = avg2p(A);  /* predictor is from (-1, 1/2) */
           B[1][0] = avg3p(A + 1);  /* (-1, 1) */
           B[2][0] = B[0][1] = avg2p(A + 1);  /* (-1, 3/2) */
           B[1][1] = B[3][0] = avg3p(A + 2);  /* (-1,   2) */
           B[2][1] = B[0][2] = avg2p(A + 2);  /* (-1, 5/2) */
           B[3][1] = B[1][2] = avg3p(A + 3);  /* (-1,   3) */
           B[2][2] = B[0][3] = avg2p(A + 3);  /* (-1, 7/2) */
           B[3][2] = B[1][3] = avg3p(A + 4);  /* (-1,   4) */
           /* Last two values do not strictly follow the pattern. */
           B[2][3] = avg3p(A + 5);  /* (-1, 5) [avg2p(A + 4) =
                                        (-1,9/2)] */
           B[3][3] = avg3p(A + 6);  /* (-1, 6) [avg3p(A + 5) =
                                        (-1,5)] */
           break;

       case B_HD_PRED:    /* ESE (horizontal down) step =
                             (1,2) or (-1,-2) */
           B[3][0] = avg2p(E);  /* predictor is from (5/2, -1) */
           B[3][1] = avg3p(E + 1);  /* (2, -1) */
           B[2][0] = B[3][2] = svg2p(E + 1);  /* ( 3/2, -1) */
           B[2][1] = B[3][3] = avg3p(E + 2);  /* (   1, -1) */
           B[2][2] = B[1][0] = avg2p(E + 2);  /* ( 1/2, -1) */
           B[2][3] = B[1][1] = avg3p(E + 3);  /* (   0, -1) */
           B[1][2] = B[0][0] = avg2p(E + 3);  /* (-1/2, -1) */
           B[1][3] = B[0][1] = avg3p(E + 4);  /* (  -1, -1) */
           B[0][2] = avg3p(E + 5);  /* (-1, 0) */
           B[0][3] = avg3p(E + 6);  /* (-1, 1) */
           break;

       case B_HU_PRED:    /* ENE (horizontal up) step = (1,-2)
                             or (-1,2) */
           B[0][0] = avg2p(L);  /* predictor is from (1/2, -1) */
           B[0][1] = avg3p(L + 1);  /* (1, -1) */
           B[0][2] = B[1][0] = avg2p(L + 1);  /* (3/2, -1) */
           B[0][3] = B[1][1] = avg3p(L + 2);  /* (  2, -1) */
           B[1][2] = B[2][0] = avg2p(L + 2);  /* (5/2, -1) */
           B[1][3] = B[2][1] = avg3(L[2], L[3], L[3]);  /* (3, -1) */

Top      Up      ToC       Page 60 
           /* Not possible to follow pattern for much of the bottom
              row because no (nearby) already-constructed pixels lie
              on the diagonals in question. */
           B[2][2] = B[2][3] = B[3][0] = B[3][1] = B[3][2] = B[3][3]
             = L[3];
     }
   }

   ---- End code block ----------------------------------------

   The reference decoder implementation of subblock intra-prediction may
   be found in predict.c (Section 20.14).

13.  DCT Coefficient Decoding

   The second data partition consists of an encoding of the quantized
   DCT (and WHT) coefficients of the residue signal.  As discussed in
   the format overview (Section 2), for each macroblock, the residue is
   added to the (intra- or inter-generated) prediction buffer to produce
   the final (except for loop filtering) reconstructed macroblock.

   VP8 works exclusively with 4x4 DCTs and WHTs, applied to the 24 (or
   25 with the Y2 subblock) 4x4 subblocks of a macroblock.  The ordering
   of macroblocks within any of the "residue" partitions in general
   follows the same raster scan as used in the first "prediction"
   partition.

   For all intra- and inter-prediction modes apart from B_PRED (intra:
   whose Y subblocks are independently predicted) and SPLITMV (inter),
   each macroblock's residue record begins with the Y2 component of the
   residue, coded using a WHT.  B_PRED and SPLITMV coded macroblocks
   omit this WHT and specify the 0th DCT coefficient in each of the 16 Y
   subblocks.

   After the optional Y2 block, the residue record continues with 16
   DCTs for the Y subblocks, followed by 4 DCTs for the U subblocks,
   ending with 4 DCTs for the V subblocks.  The subblocks occur in the
   usual order.

   The DCTs and WHT are tree-coded using a 12-element alphabet whose
   members we call "tokens".  Except for the end-of-block token (which
   sets the remaining subblock coefficients to zero and is followed by
   the next block), each token (sometimes augmented with data
   immediately following the token) specifies the value of the single
   coefficient at the current (implicit) position and is followed by a
   token applying to the next (implicit) position.

Top      Up      ToC       Page 61 
   For all the Y and chroma subblocks, the ordering of the coefficients
   follows a so-called zig-zag order.  DCTs begin at coefficient 1 if Y2
   is present, and begin at coefficient 0 if Y2 is absent.  The WHT for
   a Y2 subblock always begins at coefficient 0.

13.1.  Macroblock without Non-Zero Coefficient Values

   If the flag within macroblock (MB) MODE_INFO indicates that a
   macroblock does not have any non-zero coefficients, the decoding
   process of DCT coefficients is skipped for the macroblock.

13.2.  Coding of Individual Coefficient Values

   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.

   ---- Begin code block --------------------------------------

   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;

Top      Up      ToC       Page 62 
   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" */
   };

   ---- End code block ----------------------------------------

   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.

Top      Up      ToC       Page 63 
   ---- Begin code block --------------------------------------

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

   ---- End code block ----------------------------------------

   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:

   ---- Begin code block --------------------------------------

   if (read_bool(d, 128))
       v = -v;

   ---- End code block ----------------------------------------

13.3.  Token Probabilities

   The probability specification for the token tree (unlike that for the
   "extra bits" described above) is rather involved.  It uses three
   pieces of context to index a large probability table, the contents of
   which may be incrementally modified in the frame header.  The full
   (non-constant) probability table is laid out as follows.

   ---- Begin code block --------------------------------------

   Prob coeff_probs [4] [8] [3] [num_dct_tokens-1];

   ---- End code block ----------------------------------------

Top      Up      ToC       Page 64 
   Working from the outside in, the outermost dimension is indexed by
   the type of plane being decoded:

   o  0 - Y beginning at coefficient 1 (i.e., Y after Y2)

   o  1 - Y2

   o  2 - U or V

   o  3 - Y beginning at coefficient 0 (i.e., Y in the absence of Y2).

   The next dimension is selected by the position of the coefficient
   being decoded.  That position, c, steps by ones up to 15, starting
   from zero for block types 1, 2, or 3 and starting from one for block
   type 0.  The second array index is then

   ---- Begin code block --------------------------------------

   coeff_bands [c]

   ---- End code block ----------------------------------------

   Where:

   ---- Begin code block --------------------------------------

   const int coeff_bands [16] = {
        0, 1, 2, 3, 6, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7
   };

   ---- End code block ----------------------------------------

   is a fixed mapping of position to "band".

   The third dimension is the trickiest.  Roughly speaking, it measures
   the "local complexity" or extent to which nearby coefficients are
   non-zero.

   For the first coefficient (DC, unless the block type is 0), we
   consider the (already encoded) blocks within the same plane (Y2, Y,
   U, or V) above and to the left of the current block.  The context
   index is then the number (0, 1, or 2) of these blocks that had at
   least one non-zero coefficient in their residue record.  Specifically
   for Y2, because macroblocks above and to the left may or may not have
   a Y2 block, the block above is determined by the most recent
   macroblock in the same column that has a Y2 block, and the block to
   the left is determined by the most recent macroblock in the same row
   that has a Y2 block.

Top      Up      ToC       Page 65 
   Beyond the first coefficient, the context index is determined by the
   absolute value of the most recently decoded coefficient (necessarily
   within the current block) and is 0 if the last coefficient was a
   zero, 1 if it was plus or minus one, and 2 if its absolute value
   exceeded one.

   Note that the intuitive meaning of this measure changes as
   coefficients are decoded.  For example, prior to the first token, a
   zero means that the neighbors are empty, suggesting that the current
   block may also be empty.  After the first token, because an end-of-
   block token must have at least one non-zero value before it, a zero
   means that we just decoded a zero and hence guarantees that a
   non-zero coefficient will appear later in this block.  However, this
   shift in meaning is perfectly okay because the complete context
   depends also on the coefficient band (and since band 0 is occupied
   exclusively by position 0).

   As with other contexts used by VP8, the "neighboring block" context
   described here needs a special definition for subblocks lying along
   the top row or left edge of the frame.  These "non-existent"
   predictors above and to the left of the image are simply taken to be
   empty -- that is, taken to contain no non-zero coefficients.

   The residue decoding of each macroblock then requires, in each of two
   directions (above and to the left), an aggregate coefficient
   predictor consisting of a single Y2 predictor, two predictors for
   each of U and V, and four predictors for Y.  In accordance with the
   scan-ordering of macroblocks, a decoder needs to maintain a single
   "left" aggregate predictor and a row of "above" aggregate predictors.

   Before decoding any residue, these maintained predictors may simply
   be cleared, in compliance with the definition of "non-existent"
   prediction.  After each block is decoded, the two predictors
   referenced by the block are replaced with the (empty or non-empty)
   state of the block, in preparation for the later decoding of the
   blocks below and to the right of the block just decoded.

   The fourth, and final, dimension of the token probability array is of
   course indexed by (half) the position in the token tree structure, as
   are all tree probability arrays.

   The pseudocode below illustrates the decoding process.  Note that
   criteria, functions, etc. delimited with ** are either dependent on
   decoder architecture or are elaborated on elsewhere in this document.

Top      Up      ToC       Page 66 
   ---- Begin code block --------------------------------------

   int block[16] = { 0 }; /* current 4x4 block coeffs */
   int firstCoeff = 0;
   int plane;
   int ctx2;
   int ctx3 = 0; /* the 3rd context referred to in above description */
   Prob *probTable;
   int token;
   int sign;
   int absValue;
   int extraBits;
   bool prevCoeffWasZero = false;
   bool currentBlockHasCoeffs = false;
   /* base coeff abs values per each category, elem #0 is
      DCT_VAL_CATEGORY1, * #1 is DCT_VAL_CATEGORY2, etc. */
   int categoryBase[6] = { 5, 7, 11, 19, 35, 67 };

   /* Determine plane to use */
   if ( **current_block_is_Y2_block** )       plane = 0;
   else if ( **current_block_is_chroma** )   plane = 2;
   else if ( **current_macroblock_has_Y2** ) plane = 1;
   else                                      plane = 3;

   /* For luma blocks of a "Y2 macroblock" we skip coeff index #0 */
   if ( plane == 1 )
       firstCoeff++;

   /* Determine whether neighbor 4x4 blocks have coefficients.
      This is dependent on the plane we are currently decoding;
      i.e., we check only coefficients from the same plane as the
      current block. */
   if ( **left_neighbor_block_has_coefficients(plane)** )
       ctx3++;
   if ( **above_neighbor_block_has_coefficients(plane)** )
       ctx3++;

   for( i = firstCoeff; i < 16; ++i )
   {
       ctx2 = coeff_bands[i];
       probTable = coeff_probs[plane][ctx2][ctx3];

       /* skip first code (dct_eob) if previous token was DCT_0 */
       if ( prevCoeffWasZero )
           token = treed_read ( d, **coeff_tree_without_eob**,
             probTable );
       else
           token = treed_read ( d, coeff_tree, probTable );

Top      Up      ToC       Page 67 
       if ( token == dct_eob )
           break;

       if ( token != DCT_0 )
       {
           currentBlockHasCoeffs = true;
     if ( **token_has_extra_bits(token)** )
     {
         extraBits = DCTextra( token );
         absValue =
             categoryBase[**token_to_cat_index(token)**] +
       extraBits;
     }
     else
     {
         absValue = **token_to_abs_value(token)**;
     }

     sign = read_bool(d, 128);
           block[i] = sign ? -absValue : absValue;
       }
       else
       {
           absValue = 0;
       }

       /* Set contexts and stuff for next coeff */
       if ( absValue == 0 )         ctx3 = 0;
       else if ( absValue == 1 )   ctx3 = 1;
       else                        ctx3 = 2;
       prevCoeffWasZero = true;
   }

   /* Store current block status to decoder internals */
   **block_has_coefficients[currentMb][currentBlock]** =
     currentBlockHasCoeffs;

   ---- End code block ----------------------------------------

   While we have in fact completely described the coefficient decoding
   procedure, the reader will probably find it helpful to consult the
   reference implementation, which can be found in the file tokens.c
   (Section 20.16).

Top      Up      ToC       Page 68 
13.4.  Token Probability Updates

   As mentioned above, the token-decoding probabilities may change from
   frame to frame.  After detection of a key frame, they are of course
   set to their defaults as shown in Section 13.5; this must occur
   before decoding the remainder of the header, as both key frames and
   interframes may adjust these probabilities.

   The layout and semantics of the coefficient probability update record
   (Section I of the frame header) are straightforward.  For each
   position in the coeff_probs array there occurs a fixed-probability
   bool indicating whether or not the corresponding probability should
   be updated.  If the bool is true, there follows a P(8) replacing that
   probability.  Note that updates are cumulative; that is, a
   probability updated on one frame is in effect for all ensuing frames
   until the next key frame, or until the probability is explicitly
   updated by another frame.

   The algorithm to effect the foregoing is simple:

   ---- Begin code block --------------------------------------

   int i = 0;  do {
    int j = 0;  do {
     int k = 0;  do {
      int t = 0;  do {

           if (read_bool(d, coeff_update_probs [i] [j] [k] [t]))
               coeff_probs [i] [j] [k] [t] = read_literal(d, 8);

      } while (++t < num_dct_tokens - 1);
     } while (++k < 3);
    } while (++j < 8);
   } while (++i < 4);

   ---- End code block ----------------------------------------

Top      Up      ToC       Page 69 
   The (constant) update probabilities are as follows:

   ---- Begin code block --------------------------------------

   const Prob coeff_update_probs [4] [8] [3] [num_dct_tokens-1] =
   {
    {
     {
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 176, 246, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 223, 241, 252, 255, 255, 255, 255, 255, 255, 255, 255},
      { 249, 253, 253, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 244, 252, 255, 255, 255, 255, 255, 255, 255, 255},
      { 234, 254, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 253, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 246, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 239, 253, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 254, 255, 254, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 248, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 251, 255, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 253, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 251, 254, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 254, 255, 254, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 254, 253, 255, 254, 255, 255, 255, 255, 255, 255},
      { 250, 255, 254, 255, 254, 255, 255, 255, 255, 255, 255},
      { 254, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     }
    },

Top      Up      ToC       Page 70 
    {
     {
      { 217, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 225, 252, 241, 253, 255, 255, 254, 255, 255, 255, 255},
      { 234, 250, 241, 250, 253, 255, 253, 254, 255, 255, 255}
     },
     {
      { 255, 254, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 223, 254, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 238, 253, 254, 254, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 248, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 249, 254, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 253, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 247, 254, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 253, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 252, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 254, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 253, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 254, 253, 255, 255, 255, 255, 255, 255, 255, 255},
      { 250, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 254, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     }
    },
    {
     {
      { 186, 251, 250, 255, 255, 255, 255, 255, 255, 255, 255},
      { 234, 251, 244, 254, 255, 255, 255, 255, 255, 255, 255},
      { 251, 251, 243, 253, 254, 255, 254, 255, 255, 255, 255}
     },

Top      Up      ToC       Page 71 
     {
      { 255, 253, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 236, 253, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 251, 253, 253, 254, 254, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 254, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 254, 254, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 254, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 254, 254, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 254, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 254, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     }
    },
    {
     {
      { 248, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 250, 254, 252, 254, 255, 255, 255, 255, 255, 255, 255},
      { 248, 254, 249, 253, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 253, 253, 255, 255, 255, 255, 255, 255, 255, 255},
      { 246, 253, 253, 255, 255, 255, 255, 255, 255, 255, 255},
      { 252, 254, 251, 254, 254, 255, 255, 255, 255, 255, 255}
     },

Top      Up      ToC       Page 72 
     {
      { 255, 254, 252, 255, 255, 255, 255, 255, 255, 255, 255},
      { 248, 254, 253, 255, 255, 255, 255, 255, 255, 255, 255},
      { 253, 255, 254, 254, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 251, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 245, 251, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 253, 253, 254, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 251, 253, 255, 255, 255, 255, 255, 255, 255, 255},
      { 252, 253, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 254, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 252, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 249, 255, 254, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 254, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 255, 253, 255, 255, 255, 255, 255, 255, 255, 255},
      { 250, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     },
     {
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 254, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
      { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
     }
    }
   };

   ---- End code block ----------------------------------------

Top      Up      ToC       Page 73 
13.5.  Default Token Probability Table

   The default token probabilities are as follows.

   ---- Begin code block --------------------------------------

   const Prob default_coeff_probs [4] [8] [3] [num_dct_tokens - 1] =
   {
    {
     {
      { 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128},
      { 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128},
      { 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128}
     },
     {
      { 253, 136, 254, 255, 228, 219, 128, 128, 128, 128, 128},
      { 189, 129, 242, 255, 227, 213, 255, 219, 128, 128, 128},
      { 106, 126, 227, 252, 214, 209, 255, 255, 128, 128, 128}
     },
     {
      {   1,  98, 248, 255, 236, 226, 255, 255, 128, 128, 128},
      { 181, 133, 238, 254, 221, 234, 255, 154, 128, 128, 128},
      {  78, 134, 202, 247, 198, 180, 255, 219, 128, 128, 128}
     },
     {
      {   1, 185, 249, 255, 243, 255, 128, 128, 128, 128, 128},
      { 184, 150, 247, 255, 236, 224, 128, 128, 128, 128, 128},
      {  77, 110, 216, 255, 236, 230, 128, 128, 128, 128, 128}
     },
     {
      {   1, 101, 251, 255, 241, 255, 128, 128, 128, 128, 128},
      { 170, 139, 241, 252, 236, 209, 255, 255, 128, 128, 128},
      {  37, 116, 196, 243, 228, 255, 255, 255, 128, 128, 128}
     },
     {
      {   1, 204, 254, 255, 245, 255, 128, 128, 128, 128, 128},
      { 207, 160, 250, 255, 238, 128, 128, 128, 128, 128, 128},
      { 102, 103, 231, 255, 211, 171, 128, 128, 128, 128, 128}
     },
     {
      {   1, 152, 252, 255, 240, 255, 128, 128, 128, 128, 128},
      { 177, 135, 243, 255, 234, 225, 128, 128, 128, 128, 128},
      {  80, 129, 211, 255, 194, 224, 128, 128, 128, 128, 128}
     },

Top      Up      ToC       Page 74 
     {
      {   1,   1, 255, 128, 128, 128, 128, 128, 128, 128, 128},
      { 246,   1, 255, 128, 128, 128, 128, 128, 128, 128, 128},
      { 255, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128}
     }
    },
    {
     {
      { 198,  35, 237, 223, 193, 187, 162, 160, 145, 155,  62},
      { 131,  45, 198, 221, 172, 176, 220, 157, 252, 221,   1},
      {  68,  47, 146, 208, 149, 167, 221, 162, 255, 223, 128}
     },
     {
      {   1, 149, 241, 255, 221, 224, 255, 255, 128, 128, 128},
      { 184, 141, 234, 253, 222, 220, 255, 199, 128, 128, 128},
      {  81,  99, 181, 242, 176, 190, 249, 202, 255, 255, 128}
     },
     {
      {   1, 129, 232, 253, 214, 197, 242, 196, 255, 255, 128},
      {  99, 121, 210, 250, 201, 198, 255, 202, 128, 128, 128},
      {  23,  91, 163, 242, 170, 187, 247, 210, 255, 255, 128}
     },
     {
      {   1, 200, 246, 255, 234, 255, 128, 128, 128, 128, 128},
      { 109, 178, 241, 255, 231, 245, 255, 255, 128, 128, 128},
      {  44, 130, 201, 253, 205, 192, 255, 255, 128, 128, 128}
     },
     {
      {   1, 132, 239, 251, 219, 209, 255, 165, 128, 128, 128},
      {  94, 136, 225, 251, 218, 190, 255, 255, 128, 128, 128},
      {  22, 100, 174, 245, 186, 161, 255, 199, 128, 128, 128}
     },
     {
      {   1, 182, 249, 255, 232, 235, 128, 128, 128, 128, 128},
      { 124, 143, 241, 255, 227, 234, 128, 128, 128, 128, 128},
      {  35,  77, 181, 251, 193, 211, 255, 205, 128, 128, 128}
     },
     {
      {   1, 157, 247, 255, 236, 231, 255, 255, 128, 128, 128},
      { 121, 141, 235, 255, 225, 227, 255, 255, 128, 128, 128},
      {  45,  99, 188, 251, 195, 217, 255, 224, 128, 128, 128}
     },
     {
      {   1,   1, 251, 255, 213, 255, 128, 128, 128, 128, 128},
      { 203,   1, 248, 255, 255, 128, 128, 128, 128, 128, 128},
      { 137,   1, 177, 255, 224, 255, 128, 128, 128, 128, 128}
     }
    },

Top      Up      ToC       Page 75 
    {
     {
      { 253,   9, 248, 251, 207, 208, 255, 192, 128, 128, 128},
      { 175,  13, 224, 243, 193, 185, 249, 198, 255, 255, 128},
      {  73,  17, 171, 221, 161, 179, 236, 167, 255, 234, 128}
     },
     {
      {   1,  95, 247, 253, 212, 183, 255, 255, 128, 128, 128},
      { 239,  90, 244, 250, 211, 209, 255, 255, 128, 128, 128},
      { 155,  77, 195, 248, 188, 195, 255, 255, 128, 128, 128}
     },
     {
      {   1,  24, 239, 251, 218, 219, 255, 205, 128, 128, 128},
      { 201,  51, 219, 255, 196, 186, 128, 128, 128, 128, 128},
      {  69,  46, 190, 239, 201, 218, 255, 228, 128, 128, 128}
     },
     {
      {   1, 191, 251, 255, 255, 128, 128, 128, 128, 128, 128},
      { 223, 165, 249, 255, 213, 255, 128, 128, 128, 128, 128},
      { 141, 124, 248, 255, 255, 128, 128, 128, 128, 128, 128}
     },
     {
      {   1,  16, 248, 255, 255, 128, 128, 128, 128, 128, 128},
      { 190,  36, 230, 255, 236, 255, 128, 128, 128, 128, 128},
      { 149,   1, 255, 128, 128, 128, 128, 128, 128, 128, 128}
     },
     {
      {   1, 226, 255, 128, 128, 128, 128, 128, 128, 128, 128},
      { 247, 192, 255, 128, 128, 128, 128, 128, 128, 128, 128},
      { 240, 128, 255, 128, 128, 128, 128, 128, 128, 128, 128}
     },
     {
      {   1, 134, 252, 255, 255, 128, 128, 128, 128, 128, 128},
      { 213,  62, 250, 255, 255, 128, 128, 128, 128, 128, 128},
      {  55,  93, 255, 128, 128, 128, 128, 128, 128, 128, 128}
     },
     {
      { 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128},
      { 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128},
      { 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128}
     }
    },
    {
     {
      { 202,  24, 213, 235, 186, 191, 220, 160, 240, 175, 255},
      { 126,  38, 182, 232, 169, 184, 228, 174, 255, 187, 128},
      {  61,  46, 138, 219, 151, 178, 240, 170, 255, 216, 128}
     },

Top      Up      ToC       Page 76 
     {
      {   1, 112, 230, 250, 199, 191, 247, 159, 255, 255, 128},
      { 166, 109, 228, 252, 211, 215, 255, 174, 128, 128, 128},
      {  39,  77, 162, 232, 172, 180, 245, 178, 255, 255, 128}
     },
     {
      {   1,  52, 220, 246, 198, 199, 249, 220, 255, 255, 128},
      { 124,  74, 191, 243, 183, 193, 250, 221, 255, 255, 128},
      {  24,  71, 130, 219, 154, 170, 243, 182, 255, 255, 128}
     },
     {
      {   1, 182, 225, 249, 219, 240, 255, 224, 128, 128, 128},
      { 149, 150, 226, 252, 216, 205, 255, 171, 128, 128, 128},
      {  28, 108, 170, 242, 183, 194, 254, 223, 255, 255, 128}
     },
     {
      {   1,  81, 230, 252, 204, 203, 255, 192, 128, 128, 128},
      { 123, 102, 209, 247, 188, 196, 255, 233, 128, 128, 128},
      {  20,  95, 153, 243, 164, 173, 255, 203, 128, 128, 128}
     },
     {
      {   1, 222, 248, 255, 216, 213, 128, 128, 128, 128, 128},
      { 168, 175, 246, 252, 235, 205, 255, 255, 128, 128, 128},
      {  47, 116, 215, 255, 211, 212, 255, 255, 128, 128, 128}
     },
     {
      {   1, 121, 236, 253, 212, 214, 255, 255, 128, 128, 128},
      { 141,  84, 213, 252, 201, 202, 255, 219, 128, 128, 128},
      {  42,  80, 160, 240, 162, 185, 255, 205, 128, 128, 128}
     },
     {
      {   1,   1, 255, 128, 128, 128, 128, 128, 128, 128, 128},
      { 244,   1, 255, 128, 128, 128, 128, 128, 128, 128, 128},
      { 238,   1, 255, 128, 128, 128, 128, 128, 128, 128, 128}
     }
    }
   };

   ---- End code block ----------------------------------------



(page 76 continued on part 4)

Next RFC Part