Chapter 6: Description of Algorithms / 第6章 アルゴリズムの詳細

VP8

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

　参照復号器のソースコードと共に本稿の意図がVP8ビデオストリームの復号処理と再構成のためのプラットフォーム非依存処理を規定することにあるように，多くの（小規模な）アルゴリズムは正確に記述されなければならない．

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.

　ほぼ普遍的で，簡潔で，有用で容易に計算方法を特定の精度で記述でき，かつOn2の参照VP8復号器がC言語で書かれているという事実のために，これらのアルゴルズムの断片はC言語を用いて書かれており，以下の簡素な定義により拡張されている．

The standard (and best) reference for C is The C Programming Language, written by Brian W. Kernighan and Dennis M. Ritchie, and published by Prentice-Hall.

　標準的（かつ最適）なCの参考文献はプログラミング言語C，B.W. カーニハン, D.M. リッチー著，Prentice-Hall出版である．

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:

　多くのコード断片は本稿で見つけられるだろう．いくつかのコード断片は参照復号器の対応する章で概ね特定できるだろう．その他のは異なっている．大まかにいって，その違いには3つの理由がある．

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.

1. 効率性，すなわち参照復号器版はやや自明ではない
2. 参照復号器はしばしばコンテキストを保持するために巨大なデータ構造を用いており，ここでの記述や利用には必要ない
3. 本稿の著者が，同じアルゴリズムの異なる表現が説明しやすいと感じている

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.

　全てのVP8復号アルゴリズムは整数計算を使用する．算術精度の規定を促進するために，以下の型を定義する．

typedef signed char int8;       /* signed integer exactly 8 bits wide ぴったり8ビット幅の符号付き整数 */
typedef unsigned char uint8;    /* unsigned "" 上記と同様で符号なし整数 */

typedef short int16;            /* signed integer exactly 16 bits wide ぴったり16ビット幅の符号付き整数 */
typedef unsigned int16 uint16;  /* unsigned "" 上記と同様で符号なし整数 */

/* int32 is a signed integer type at least 32 bits wide int32は少なくとも32ビット幅を有する符号付き整数型である*/

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
少なくとも16bit幅の，符号なし整数型でその実際のビット幅は
利用しているCPUによってもっとも便利なものである */

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.
画素そのものは8bit符号なし整数であるが，
画素計算はしばしば16bitまたは32bit精度で生じ
結果は8bit幅に飽和，または上限を抑えられる必要がある */

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.
この後の真偽復号器の議論で精緻化されるように，
VP8は確率値を8bitの符号なし整数で表現する */

typedef uint8 Prob;

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 π; 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 .

　有限精度である実数の真摯さよりも十分さに起因する数学的機能を議論する必要が時々ある．DCTは当初，コサイン関数cosによって記述されている．円の円周と直径の長さ比をnとする．ここで，(1/2を基底とする）対数をlogとする．pow(x, y)をxのy乗であるとする．ここで，x=2でyが小さな非負整数ならば，pow(2, y)はC言語で1<