text_src/06.00__vp8-bitstream__description-of-algorithms.txt

### Section 6: Description of Algorithms                   {#h-06-00}

As the intent of this document, together with the reference decoder
source code, is to specify a platform-independent procedure for the
decoding and reconstruction of a VP8 video stream, many (small)
algorithms must be described exactly.

Due to its near-universality, terseness, ability to easily describe
calculation at specific precisions, and the fact that On2's reference
VP8 decoder is written in C, these algorithm fragments are written
using the C programming language, augmented with a few simple
definitions below.

The standard (and best) reference for C is [Kernighan].

Many code fragments will be presented in this document.  Some will be
nearly identical to corresponding sections of the reference decoder;
others will differ.  Roughly speaking, there are three reasons for
such differences:

  1. For reasons of efficiency, the reference decoder version may be
     less obvious.

  2. The reference decoder often uses large data structures to
     maintain context that need not be described or used here.

  3. The authors of this document felt that a different expression of
     the same algorithm might facilitate exposition.

Regardless of the chosen presentation, the calculation effected by
any of the algorithms described here is identical to that effected by
the corresponding portion of the reference decoder.

All VP8 decoding algorithms use integer math.  To facilitate
specification of arithmetic precision, we define the following types.


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
typedef   signed char  int8; /* signed int exactly 8 bits wide */
typedef unsigned char uint8; /* unsigned "" */

typedef short int16;         /* signed int exactly 16 bits wide */
typedef unsigned int16 uint16; /* unsigned "" */

/* int32 is a signed integer type at least 32 bits wide */

typedef long int32; /* guaranteed to work on all systems */
typedef int  int32; /* will be more efficient on some systems */

typedef unsigned int32 uint32;

/* unsigned integer type, at least 16 bits wide, whose exact size
   is most convenient to whatever processor we are using */

typedef unsigned int uint;

/* While pixels themselves are 8-bit unsigned integers,
   pixel arithmetic often occurs at 16- or 32-bit precision and
   the results need to be "saturated" or clamped to an 8-bit
   range. */

typedef uint8 Pixel;

Pixel clamp255( int32 v) { return v < 0? 0 : (v < 255? v : 255);}

/*  As is elaborated in the discussion of the bool_decoder below,
    VP8 represents probabilities as unsigned 8-bit numbers. */

typedef uint8 Prob;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
{:lang="c"}


We occasionally need to discuss mathematical functions involving
honest-to-goodness "infinite precision" real numbers.  The DCT is
first described via the cosine function cos; the ratio of the lengths
of the circumference and diameter of a circle is denoted pi; at one
point, we take a (base 1/2) logarithm, denoted log; and pow(x, y)
denotes x raised to the power y.  If x = 2 and y is a small non-
negative integer, pow(2, y) may be expressed in C as 1 << y.

Finally, we sometimes need to divide signed integers by powers of
two; that is, we occasionally right-shift signed numbers.  The
behavior of such shifts (i.e., the propagation of the sign bit) is,
perhaps surprisingly, not defined by the C language itself and is
left up to individual compilers.  Because of the utility of this
frequently needed operation, it is at least arguable that it should
be defined by the language (to naturally propagate the sign bit) and,
at a minimum, should be correctly implemented by any reasonable
compiler.  In the interest of strict portability, we attempt to call
attention to these shifts when they arise.