Theora Specification
Xiph.Org Foundation
June 3, 2017

Contents
1 Introduction
1.1 VP3 and Theora . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Video Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Codec Setup and Probability Model . . . . . . . . . . . . . . . .
1.6 Format Conformance . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
1
2
2
2
3

2 Coded Video Structure
2.1 Frame Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Picture Region . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Blocks and Super Blocks . . . . . . . . . . . . . . . . . . . . . . .
2.4 Macro Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Coding Modes and Prediction . . . . . . . . . . . . . . . . . . . .
2.6 DCT Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
5
6
7
9
11
11

3 Decoding Overview
13
3.1 Decoder Configuration . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1 Global Configuration . . . . . . . . . . . . . . . . . . . . . 13
3.1.2 Quantization Matrices . . . . . . . . . . . . . . . . . . . . 13
3.1.3 Huffman Codebooks . . . . . . . . . . . . . . . . . . . . . 14
3.2 High-Level Decode Process . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Decoder Setup . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.2 Decode Procedure . . . . . . . . . . . . . . . . . . . . . . 15
4 Video Formats
21
4.1 Color Space Conventions . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Color Space Conversions and Parameters . . . . . . . . . . . . . 22
4.3 Available Color Spaces . . . . . . . . . . . . . . . . . . . . . . . . 24
4.3.1 Rec. 470M (Rec. ITU-R BT.470-6 System M/NTSC with
Rec. ITU-R BT.601-5) . . . . . . . . . . . . . . . . . . . . 24
4.3.2 Rec. 470BG (Rec. ITU-R BT.470-6 Systems B and G with
Rec. ITU-R BT.601-5) . . . . . . . . . . . . . . . . . . . . 25
4.4 Pixel Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
i

ii

CONTENTS
4.4.1
4.4.2
4.4.3
4.4.4

4:4:4 Subsampling . . . . . . . . . . . . . . . . . . . . . .
4:2:2 Subsampling . . . . . . . . . . . . . . . . . . . . . .
4:2:0 Subsampling . . . . . . . . . . . . . . . . . . . . . .
Subsampling and the Picture Region . . . . . . . . . . . .

27
27
28
29

5 Bitpacking Convention
33
5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.1.1 Octets and Bytes . . . . . . . . . . . . . . . . . . . . . . . 33
5.1.2 Words and Byte Order . . . . . . . . . . . . . . . . . . . . 33
5.1.3 Bit Order . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 Coding Bits into Bytes . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2.1 Signedness . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2.2 Encoding Example . . . . . . . . . . . . . . . . . . . . . . 35
5.2.3 Decoding Example . . . . . . . . . . . . . . . . . . . . . . 36
5.2.4 End-of-Packet Alignment . . . . . . . . . . . . . . . . . . 37
5.2.5 Reading Zero Bit Integers . . . . . . . . . . . . . . . . . . 37
6 Bitstream Headers39
6.1 Common Header Decode . . . . . . . . . . . . . . . . . . . . . . . 39
6.2 Identification Header Decode . . . . . . . . . . . . . . . . . . . . 41
6.3 Comment Header . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.3.1 Comment Length Decode . . . . . . . . . . . . . . . . . . 46
6.3.2 Comment Header Decode . . . . . . . . . . . . . . . . . . 47
6.3.3 User Comment Format . . . . . . . . . . . . . . . . . . . . 48
6.4 Setup Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.4.1 Loop Filter Limit Table Decode . . . . . . . . . . . . . . . 50
6.4.2 Quantization Parameters Decode . . . . . . . . . . . . . . 51
6.4.3 Computing a Quantization Matrix . . . . . . . . . . . . . 54
6.4.4 DCT Token Huffman Tables . . . . . . . . . . . . . . . . . 57
6.4.5 Setup Header Decode . . . . . . . . . . . . . . . . . . . . 58
7 Frame Decode
61
7.1 Frame Header Decode . . . . . . . . . . . . . . . . . . . . . . . . 61
7.2 Run-Length Encoded Bit Strings . . . . . . . . . . . . . . . . . . 63
7.2.1 Long-Run Bit String Decode . . . . . . . . . . . . . . . . 63
7.2.2 Short-Run Bit String Decode . . . . . . . . . . . . . . . . 65
7.3 Coded Block Flags Decode . . . . . . . . . . . . . . . . . . . . . 67
7.4 Macro Block Coding Modes . . . . . . . . . . . . . . . . . . . . . 69
7.5 Motion Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.5.1 Motion Vector Decode . . . . . . . . . . . . . . . . . . . . 72
7.5.2 Macro Block Motion Vector Decode . . . . . . . . . . . . 73
7.6 Block-Level qi Decode . . . . . . . . . . . . . . . . . . . . . . . . 79
7.7 DCT Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.7.1 EOB Token Decode . . . . . . . . . . . . . . . . . . . . . 83
7.7.2 Coefficient Token Decode . . . . . . . . . . . . . . . . . . 86
7.7.3 DCT Coefficient Decode . . . . . . . . . . . . . . . . . . . 94

CONTENTS

iii

7.8

Undoing DC Prediction . . . . . . . . . . . . . . . . . . . . . . . 96
7.8.1 Computing the DC Predictor . . . . . . . . . . . . . . . . 97
7.8.2 Inverting the DC Prediction Process . . . . . . . . . . . . 101
7.9 Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.9.1 Predictors . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.9.1.1 The Intra Predictor . . . . . . . . . . . . . . . . 104
7.9.1.2 The Whole-Pixel Predictor . . . . . . . . . . . . 105
7.9.1.3 The Half-Pixel Predictor . . . . . . . . . . . . . 106
7.9.2 Dequantization . . . . . . . . . . . . . . . . . . . . . . . . 108
7.9.3 The Inverse DCT . . . . . . . . . . . . . . . . . . . . . . . 111
7.9.3.1 The 1D Inverse DCT . . . . . . . . . . . . . . . 112
7.9.3.2 The 2D Inverse DCT . . . . . . . . . . . . . . . 116
7.9.3.3 The 1D Forward DCT (Non-Normative) . . . . . 117
7.9.4 The Complete Reconstruction Algorithm . . . . . . . . . 120
7.10 Loop Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.10.1 Horizontal Filter . . . . . . . . . . . . . . . . . . . . . . . 128
7.10.2 Vertical Filter . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.10.3 Complete Loop Filter . . . . . . . . . . . . . . . . . . . . 130
7.11 Complete Frame Decode . . . . . . . . . . . . . . . . . . . . . . . 135
A Ogg Bitstream Encapsulation
143
A.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
A.1.1 MIME type . . . . . . . . . . . . . . . . . . . . . . . . . . 143
A.2 Embedding in a logical bitstream . . . . . . . . . . . . . . . . . . 144
A.2.1 Headers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
A.2.2 Frame data . . . . . . . . . . . . . . . . . . . . . . . . . . 144
A.2.3 Granule position . . . . . . . . . . . . . . . . . . . . . . . 144
A.3 Multiplexed stream mapping . . . . . . . . . . . . . . . . . . . . 145
A.3.1 Chained streams . . . . . . . . . . . . . . . . . . . . . . . 145
A.3.2 Grouped streams . . . . . . . . . . . . . . . . . . . . . . . 145
B VP3
147
B.1 VP3 Compatibility . . . . . . . . . . . . . . . . . . . . . . . . . . 147
B.2 Loop Filter Limit Values . . . . . . . . . . . . . . . . . . . . . . . 148
B.3 Quantization Parameters . . . . . . . . . . . . . . . . . . . . . . . 148
B.4 Huffman Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
C Colophon

191

iv

CONTENTS

List of Figures
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8

Location of frame and picture regions . . . . . . . . . . . . . . .
Subdivision of a frame into blocks and super blocks . . . . . . . .
Raster ordering of n × m blocks . . . . . . . . . . . . . . . . . . .
Hilbert curve ordering of blocks within a super block . . . . . . .
Subdivision of a frame into macro blocks . . . . . . . . . . . . . .
Hilbert curve ordering of macro blocks within a super block . . .
Example of reference frames for an inter frame . . . . . . . . . .
Zig-zag order . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6
7
8
9
10
10
11
12

4.1
4.2
4.3
4.4

27
28
29

4.5
4.6
4.7

Pixels encoded 4:4:4 . . . . . . . . . . . . . . . . . . . . . . . . .
Pixels encoded 4:2:2 . . . . . . . . . . . . . . . . . . . . . . . . .
Pixels encoded 4:2:0 . . . . . . . . . . . . . . . . . . . . . . . . .
Pixel correspondence between color planes with even picture offset and even picture size . . . . . . . . . . . . . . . . . . . . . . .
Pixel correspondence with even picture offset and odd picture size
Pixel correspondence with odd picture offset and odd picture size
Pixel correspondence with odd picture offset and even picture size

30
31
31
31

6.1
6.2
6.3
6.4
6.5

Common Header Packet Layout . . . . . . . . . . . . . . . . . . .
Identification Header Packet . . . . . . . . . . . . . . . . . . . . .
Length encoded string layout . . . . . . . . . . . . . . . . . . . .
Comment Header Layout . . . . . . . . . . . . . . . . . . . . . .
Setup Header structure . . . . . . . . . . . . . . . . . . . . . . .

39
41
46
47
50

7.1
7.2
7.3

Signal Flow Graph for the 1D Inverse DCT . . . . . . . . . . . . 113
Signal Flow Graph for the 1D Forward DCT . . . . . . . . . . . 119
The loop filter response function. . . . . . . . . . . . . . . . . . . 128v

vi

LIST OF FIGURESList of Tables
2.1

Color Plane Indices . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3.1

Quantization Type Indices . . . . . . . . . . . . . . . . . . . . . .

14

4.1
4.2

Rec. 470M Parameters . . . . . . . . . . . . . . . . . . . . . . . .
Rec. 470BG Parameters . . . . . . . . . . . . . . . . . . . . . . .

25
26

6.3 Enumerated List of Color Spaces . . . . . . . . . . . . . . . . . .
6.4 Enumerated List of Pixel Formats . . . . . . . . . . . . . . . . .
6.5 Number of Super Blocks for each Pixel Format . . . . . . . . . .
6.6 Number of Blocks for each Pixel Format . . . . . . . . . . . . . .
6.18 Minimum Quantization Values . . . . . . . . . . . . . . . . . . .

44
45
45
46
57

7.3 Frame Type Values . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.7 Huffman Codes for Long Run Lengths . . . . . . . . . . . . . . . 65
7.11 Huffman Codes for Short Run Lengths . . . . . . . . . . . . . . . 66
7.18 Macro Block Coding Modes . . . . . . . . . . . . . . . . . . . . . 70
7.19 Macro Block Mode Schemes . . . . . . . . . . . . . . . . . . . . . 71
7.23 Huffman Codes for Motion Vector Components . . . . . . . . . . 81
7.33 EOB Token Summary . . . . . . . . . . . . . . . . . . . . . . . . 84
7.38 Coefficient Token Summary . . . . . . . . . . . . . . . . . . . . . 88
7.42 Huffman Table Groups . . . . . . . . . . . . . . . . . . . . . . . . 96
7.46 Reference Frames for Each Coding Mode . . . . . . . . . . . . . . 99
7.47 Weights and Divisors for Each Set of Available DC Predictors . . 101
7.65 16-bit Approximations of Sines and Cosines . . . . . . . . . . . . 114
7.75 Reference Planes and Sizes for Each rfi and pli . . . . . . . . . . 126
7.85 Reconstructed Planes and Sizes for Each pli . . . . . . . . . . . . 133
7.89 Width and Height of Chroma Planes for each Pixel Format . . . 140

vii

viii

LIST OF TABLES

Notation and Conventions
All parameters either passed in or out of a decoding procedure are given inbold face.
The prefix b indicates that the following value is to be interpreted as a binary
number (base 2).
Example: The value b1110100 is equal to the decimal value 116.
The prefix 0x indicates the following value is to be interpreted as a hexadecimal number (base 16).
Example: The value 0x74 is equal to the decimal value 116.
All arithmetic defined by this specification is exact. However, any real numbers that do arise will always be converted back to integers again in short order.
The entire specification can be implemented using only normal integer operations. All operations are to be implemented with sufficiently large integers sothat overflow cannot occur. Where the result of a computation is to be truncated to a fixed-sized binary representation, this will be explicitly noted. The
size given for all variables is the maximum number of bits needed to store any
value in that variable. Intermediate computations involving that variable may
require more bits.
The following operators are defined:|a| The absolute value of a number a.

−a,
|a| =
a,

a<0
a≥0

a ∗ b Multiplication of a number a by a number b.
ab

Exact division of a number a by a number b, producing a potentially noninteger result.

bac The largest integer less than or equal to a real number a.
dae The smallest integer greater than or equal to a real number a.
ix

x

Notation and Conventions

a//b Integer division of a by b.
 a
 ab  ,a//b =
b ,

a<0
a≥0

a%b The remainder from the integer division of a by b.
 
aa%b = a − |b| ∗|b|Note that with this definition, the result is always non-negative and lessthan |b|.
a << b The value obtained by left-shifting the two’s complement integer a byb bits. For purposes of this specification, overflow is ignored, and so thisis equivalent to integer multiplication of a by 2b .
a >> b The value obtained by right-shifting the two’s complement integer a byb bits, filling in the leftmost bits of the new value with 0 if a is non-negative
and 1 if a is negative. This is not equivalent to integer division of a by 2b .
Instead,jaka >> b = b .
2round(a) Rounds a number a to the nearest integer, with ties rounded awayfrom 0.
da − 21 e a ≤ 0round(a) =ba + 21 c a > 0sign(a) Returns the sign of a given number.
 −10
sign(a) =

1

a<0
a=0
a>0

ilog(a) The minimum number of bits required to store a positive integer a in
two’s complement notation, or 0 for a non-positive integer a.
0,a≤0ilog(a) =blog2 ac + 1, a > 0
Examples:• ilog(−1) = 0• ilog(0) = 0• ilog(1) = 1• ilog(2) = 2

Notation and Conventions• ilog(3) = 2• ilog(4) = 3• ilog(7) = 3
min(a, b) The minimum of two numbers a and b.
max(a, b) The maximum of two numbers a and b.

xi

xii

Notation and Conventions

Key words
The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL
NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and“OPTIONAL” in this document are to be intrepreted as described in RFC
2119 [Bra97].
Where such assertions are placed on the contents of a Theora bitstream itself,
implementations should be prepared to encounter bitstreams that do not follow
these requirements. An application’s behavior in the presecence of such nonconforming bitstreams is not defined by this specification, but any reasonable
method of handling them MAY be used. By way of example, applications MAY
discard the current frame, retain the current output thus far, or attempt tocontinue on by assuming some default values for the erroneous bits. When suchan error occurs in the bitstream headers, an application MAY refuse to decode
the entire stream. An application SHOULD NOT allow such non-conformant
bitstreams to overflow buffers and potentially execute arbitrary code, as thisrepresents a serious security risk.
An application MUST, however, ensure any bits marked as reserved havethe value zero, and refuse to decode the stream if they do not. These are used
as place holders for future bitstream features with which the current bitstream
is forward-compatible. Such features may not increment the bitstream version
number, and can only be recognized by checking the value of these reserved bits.

xiii

xiv

Key words

Chapter 1

Introduction
Theora is a general purpose, lossy video codec. It is based on the VP3 video
codec produced by On2 Technologies (http://www.on2.com/). On2 donatedthe VP3.1 source code to the Xiph.Org Foundation and released it under a
BSD-like license. On2 also made an irrevocable, royalty-free license grant forany patent claims it might have over the software and any derivatives. No formal
specification exists for the VP3 format beyond this source code, however Mike
Melanson maintains a detailed description [Mel04]. Portions of this specification
were adopted from that text with permission.

1.1

VP3 and Theora

Theora contains a superset of the features that were available in the original
VP3 codec. Content encoded with VP3.1 can be losslessly transcoded into the
Theora format. Theora content cannot, in general, be losslessly transcoded into
the VP3 format. If a feature is not available in the original VP3 format, thisis mentioned when that feature is defined. A complete list of these featuresappears in Appendix B.1.

1.2

Video Formats

Theora currently supports progressive video data of arbitrary dimensions at aconstant frame rate in one of several Y 0 Cb Cr color spaces. The precise definition
the supported color spaces appears in Section 4.3. Three different chroma subsampling formats are supported: 4:2:0, 4:2:2, and 4:4:4. The precise details ofeach of these formats and their sampling locations are described in Section 4.4.
The Theora format does not support interlaced material, variable frame
rates, bit-depths larger than 8 bits per component, nor alternate color spaces
such as RGB or arbitrary multi-channel spaces. Black and white content canbe efficiently encoded, however, because the uniform chroma planes compress
well. Support for interlaced material is planned for a future version.
1

2

CHAPTER 1. INTRODUCTION
Note: Infrequently changing frame rates—as when film and video
sequences are cut together—can be supported in the Ogg container format by chaining several Theora streams together.

Support for increased bit depths or additional color spaces is not planned.

1.3Classification

Theora is a block-based lossy transform codec that utilizes an 8 × 8 Type-II
Discrete Cosine Transform and block-based motion compensation. This places
it in the same class of codecs as MPEG-1, -2, -4, and H.263. The details of
how individual blocks are organized and how DCT coefficients are stored in the
bitstream differ substantially from these codecs, however. Theora supports only
intra frames (I frames in MPEG) and inter frames (P frames in MPEG). Thereis no equivalent to the bi-predictive frames (B frames) found in MPEG codecs.

1.4

Assumptions

The Theora codec design assumes a complex, psychovisually-aware encoder anda simple, low-complexity decoder.
Theora provides none of its own framing, synchronization, or protection
against transmission errors. An encoder is solely a method of accepting input
video frames and compressing these frames into raw, unformatted ‘packets’.
The decoder then accepts these raw packets in sequence, decodes them, andsynthesizes a fascimile of the original video frames. Theora is a free-form variable
bit rate (VBR) codec, and packets have no minimum size, maximum size, or
fixed/expected size.
Theora packets are thus intended to be used with a transport mechanism thatprovides free-form framing, synchronization, positioning, and error correction inaccordance with these design assumptions, such as Ogg (for file transport) or
RTP (for network multicast). For the purposes of a few examples in this document, we will assume that Theora is embedded in an Ogg stream specifically,
although this is by no means a requirement or fundamental assumption in the
Theora design.
The specification for embedding Theora into an Ogg transport stream isgiven in Appendix A.

1.5

Codec Setup and Probability Model

Theora’s heritage is the proprietary commerical codec VP3, and it retains afair amount of inflexibility when compared to Vorbis [Xip02], the first Xiph.Org
codec, which began as a research codec. However, to provide additional scopefor encoder improvement, Theora adopts some of the configurable aspects of1.6. FORMAT CONFORMANCE

3

decoder setup that are present in Vorbis. This configuration data is not available
in VP3, which uses hardcoded values instead.
Theora makes the same controversial design decision that Vorbis made toinclude the entire probability model for the DCT coefficients and all the quantization parameters in the bitstream headers. This is often several hundred
fields. It is therefore impossible to decode any frame in the stream without
having previously fetched the codec info and codec setup headers.
Note: Theora can initiate decode at an arbitrary intra-frame packet
within a bitstream so long as the codec has been initialized withthe setup headers.
Thus, Theora headers are both required for decode to begin and relatively
large as bitstream headers go. The header size is unbounded, although as arule-of-thumb less than 16kB is recommended, and Xiph.Org’s reference encoder
follows this suggestion.
Our own design work indicates that the primary liability of the required
header is in mindshare; it is an unusual design and thus causes some amountof complaint among engineers as this runs against current design trends andpoints out limitations in some existing software/interface designs. However, wefind that it does not fundamentally limit Theora’s suitable application space.

1.6

Format Conformance

The Theora format is well-defined by its decode specification; any encoder that
produces packets that are correctly decoded by an implementation following thisspecification may be considered a proper Theora encoder. A decoder must faithfully and completely implement the specification defined herein to be considereda conformant Theora decoder. A decoder need not be implemented strictly as
described, but the actual decoder process MUST be entirely mathematicallyequivalent to the described process. Where appropriate, a non-normative description of encoder processes is included. These sections will be marked assuch, and a proper Theora encoder is not bound to follow them.

4

CHAPTER 1. INTRODUCTION

Chapter 2

Coded Video Structure
Theora’s encoding and decoding process is based on 8 × 8 blocks of pixels. Thissections describes how a video frame is laid out, divided into blocks, and how
those blocks are organized.

2.1

Frame Layout

A video frame in Theora is a two-dimensional array of pixels. Theora, like VP3,
uses a right-handed coordinate system, with the origin in the lower-left cornerof the frame. This is contrary to many video formats which use a left-handed
coordinate system with the origin in the upper-left corner of the frame.
Theora divides the pixel array up into three separate color planes, one foreach of the Y 0 , Cb , and Cr components of the pixel. The Y 0 plane is also called
the luma plane, and the Cb and Cr planes are also called the chroma planes.
Each plane is assigned a numerical value, as shown in Table 2.1.
Index
0
1
2

Color Plane
Y0
Cb
Cr

Table 2.1: Color Plane Indices
In some pixel formats, the chroma planes are subsampled by a factor of two
in one or both directions. This means that the width or height of the chroma
planes may be half that of the total frame width and height. The luma plane isnever subsampled.
5

6

CHAPTER 2. CODED VIDEO STRUCTURE

2.2

Picture Region

An encoded video frame in Theora is required to have a width and height that are
multiples of sixteen, making an integral number of blocks even when the chroma
planes are subsampled. However, inside a frame a smaller picture region may
be defined to present material whose dimensions are not a multiple of sixteen
pixels, as shown in Figure 2.1. The picture region can be offset from the lowerleft corner of the frame by up to 255 pixels in each direction, and may havean arbitrary width and height, provided that it is contained entirely within thecoded frame. It is this picture region that contains the actual video data. The
portions of the frame which lie outside the picture region may contain arbitrary
image data, so the frame must be cropped to the picture region before display.
The picture region plays no other role in the decode process, which operates on
the entire video frame.

Frame Width

PictureY Offset

Picture Height

Frame Height

Frame

Picture(0,0)
PictureX Offset

Picture Width

Figure 2.1: Location of frame and picture regions

2.3. BLOCKS AND SUPER BLOCKS

2.3

7

Blocks and Super Blocks

Each color plane is subdivided into blocks of 8 × 8 pixels. Blocks are grouped
into 4 × 4 arrays called super blocks as shown in Figure 2.2. Each color plane has
its own set of blocks and super blocks. If the chroma planes are subsampled,they are still divided into 8 × 8 blocks of pixels; there are just fewer blocks
than in the luma plane. The boundaries of blocks and super blocks in the luma
plane do not necessarily coincide with those of the chroma planes, if the chroma
planes have been subsampled.
Frame

...
Super Block (4x4)

...
Block
8x8
(0,0)

Figure 2.2: Subdivision of a frame into blocks and super blocks
Blocks are accessed in two different orders in the various decoder processes.
The first is raster order, illustrated in Figure 2.3. This accesses each block in
row-major order, starting in the lower left of the frame and continuing along
the bottom row of the entire frame, followed by the next row up, starting on
the left edge of the frame, etc.
The second is coded order. In coded order, blocks are accessed by super
block. Within each frame, super blocks are traversed in raster order, similar to8

CHAPTER 2. CODED VIDEO STRUCTURE

n*m−1(n−1)*m

...
2m−1

m

0

1

...

2

m−1

Figure 2.3: Raster ordering of n × m blocks
raster order for blocks. Within each super block, however, blocks are accessedin a Hilbert curve pattern, illustrated in Figure 2.4. If a color plane does notcontain a complete super block on the top or right sides, the same ordering is
still used, simply with any blocks outside the frame boundary ommitted.
To illustrate this ordering, consider a frame that is 240 pixels wide and 48
pixels high. Each row of the luma plane has 30 blocks and 8 super blocks, andthere are 6 rows of blocks and two rows of super blocks.
When accessed in coded order, each block in the luma plane is assigned thefollowing indices:
123
120
5
4
3
0

122
121
6
7
2
1

125
126
9
8
13
14

124
127
10
11
12
15

...
...
...
...
...
...

179
176
117
116
115
112

178
177
118
119
114
113

Here the index values specify the order in which the blocks would be accessed.
The indices of the blocks are numbered continuously from one color plane to
the next. They do not reset to zero at the start of each plane. Instead, thenumbering increases continuously from the Y 0 plane to the Cb plane to the Cr2.4. MACRO BLOCKS

9

5

6

9

10

4

7

8

11

3

2

13

12

0

1

14

15

Figure 2.4: Hilbert curve ordering of blocks within a super blockplane. The implication is that the blocks from all planes are treated as a unit
during the various processing steps.
Although blocks are sometimes accessed in raster order, in this document
the index associated with a block is always its index in coded order.

2.4

Macro Blocks

A macro block contains a 2 × 2 array of blocks in the luma plane and the colocated blocks in the chroma planes, as shown in Figure 2.5. Thus macro blocks
can represent anywhere from six to twelve blocks, depending on how the chroma
planes are subsampled. This is in contrast to super blocks, which only containblocks from a single color plane. Macro blocks contain information about coding
mode and motion vectors for the corresponding blocks in all color planes.
Macro blocks are also accessed in a coded order. This coded order proceeds by
examining each super block in the luma plane in raster order, and traversing thefour macro blocks inside using a smaller Hilbert curve, as shown in Figure 2.6.
If the luma plane does not contain a complete super block on the top or rightsides, the same ordering is still used, with any macro blocks outside the frameboundary simply omitted. Because the frame size is constrained to be a multipleof 16, there are never any partial macro blocks. Unlike blocks, macro blocks
need never be accessed in a pure raster order.

10

CHAPTER 2. CODED VIDEO STRUCTURE

Frame: chroma plane

Frame: chroma plane

Frame: luma plane

Macroblock

Block
Block
8x8
(0,0)

Figure 2.5: Subdivision of a frame into macro blocks

1

2

0

3

Figure 2.6: Hilbert curve ordering of macro blocks within a super block2.5. CODING MODES AND PREDICTION

11

Using the same frame size as the example above, there are 15 macro blocks
in each row and 3 rows of macro blocks. The macro blocks are assigned thefollowing indices:

30
1
0

2.5

31
2
3

32
5
4

33
6
7

···
···
···

42
25
24

43
26
27

44
29
28

Coding Modes and Prediction

Each block is coded using one of a small, fixed set of coding modes that define
how the block is predicted from previous frames. A block is predicted using
one of two reference frames, selected according to the coding mode. A reference
frame is the fully decoded version of a previous frame in the stream. The firstavailable reference frame is the previous intra frame, called the golden frame.
The second available reference frame is the previous frame, whether it was an
intra frame or an inter frame. If the previous frame was an intra frame, thenboth reference frames are the same. See Figure 2.7 for an illustration of thereference frames used for an intra frame that does not follow an intra frame.

Intra

Inter

Inter

Inter

Inter

Inter

Inter

...
goldenframe

referenceframe

current
frame

Figure 2.7: Example of reference frames for an inter frame
Two coding modes in particular are worth mentioning here. The INTRA
mode is used for blocks that are not predicted from either reference frame. Thisis the only coding mode allowed in intra frames. The INTER NOMV coding
mode uses the co-located contents of the block in the previous frame as thepredictor. This is the default coding mode.

2.6

DCT Coefficients

A residual is added to the predicted contents of a block to form the final reconstruction. The residual is stored as a set of quantized coefficients from an

12

CHAPTER 2. CODED VIDEO STRUCTURE

integer approximation of a two-dimensional Type II Discrete Cosine Transform.
The DCT takes an 8 × 8 array of pixel values as input and returns an 8 × 8 arrayof coefficient values. The natural ordering of these coefficients is defined to be
row-major order, from lowest to highest frequency. They are also often indexedin zig-zag order, as shown in Figure 2.8.

0
1
2
3
r
4
5
6
7

c
0 1 2 3 4 5 6 7
0 → 1 5 → 6 14→15 27→28. % . % . % .
2 4 7 13 16 26 29 42↓% . % . % . %↓3 8 12 17 25 30 41 43. % . % . % .
9 11 18 24 31 40 44 53↓% . % . % . %↓10 19 23 32 39 45 52 54. % . % . % .
20 22 33 38 46 51 55 60↓% . % . % . %↓21 34 37 47 50 56 59 61. % . % . % .
35→36 48→49 57→58 62→63
Figure 2.8: Zig-zag order

Note: the row and column indices refer to frequency number andnot pixel locations. The frequency numbers are defined independently of the memory organization of the pixels. They havebeen written from top to bottom here to follow conventional notation, despite the right-handed coordinate system Theora uses
for pixel locations. Many implementations of the DCT operate‘in-place’. That is, they return DCT coefficients in the same
memory buffer that the initial pixel values were stored in. Dueto the right-handed coordinate system used for pixel locations in
Theora, one must note carefully how both pixel values and DCT
coefficients are organized in memory in such a system.
DCT coefficient (0, 0) is called the DC coefficient. All the other coefficientsare called AC coefficients.

Chapter 3

Decoding Overview
This section provides a high level description of the Theora codec’s construction.
A bit-by-bit specification appears beginning in Section 5. The later sections assume a high-level understanding of the Theora decode process, which is provided
below.

3.1

Decoder Configuration

Decoder setup consists of configuration of the quantization matrices and the
Huffman codebooks for the DCT coefficients, and a table of limit values for the
deblocking filter. The remainder of the decoding pipeline is not configurable.

3.1.1

Global Configuration

The global codec configuration consists of a few video related fields, such as
frame rate, frame size, picture size and offset, aspect ratio, color space, pixel
format, and a version number. The version number is divided into a major
version, a minor version, amd a minor revision number. For the format defined inthis specification, these are ‘3’, ‘2’, and ‘1’, respectively, in reference to Theora’s
origin as a successor to the VP3.1 format.

3.1.2

Quantization Matrices

Theora allows up to 384 different quantization matrices to be defined, one foreach quantization type, color plane (Y 0 , Cb , or Cr ), and quantization index, qi ,which ranges from zero to 63, inclusive. There are currently two quantization
types defined, which depend on the coding mode of the block being dequantized,
as shown in Table 3.1.
The quantization index, on the other hand, nominally represents a progressive range of quality levels, from low quality near zero to high quality near 63.
However, the interpretation is arbitrary, and it is possible, for example, to partition the scale into two completely separate ranges with 32 levels each that are13

14

CHAPTER 3. DECODING OVERVIEW
Quantization Type
0
1

Usage
INTRA-mode blocks
Blocks in any other mode.

Table 3.1: Quantization Type Indicesmeant to represent different classes of source material, or any other arrangementthat suits the encoder’s requirements.
Each quantization matrix is an 8×8 matrix of 16-bit values, which is used toquantize the output of the 8 × 8 DCT. Quantization matrices are specified using
three components: a base matrix and two scale values. The first scale value isthe DC scale, which is applied to the DC component of the base matrix. The
second scale value is the AC scale, which is applied to all the other componentsof the base matrix. There are 64 DC scale values and 64 AC scale values, one
for each qi value.
There are 64 elements in each base matrix, one for each DCT coefficient.
They are stored in natural order (cf. Section 2.6). There is a separate setof base matrices for each quantization type and each color plane, with up to
64 possible base matrices in each set, one for each qi value. Typically the
bitstream contains matrices for only a sparse subset of the possible qi values.
The base matrices for the remainder of the qi values are computed using linear
interpolation. This configuration allows the encoder to adjust the quantization
matrices to approximate the complex, non-linear response of the human visualsystem to different quantization errors.
Finally, because the in-loop deblocking filter strength depends on the strengthof the quantization matrices defined in this header, a table of 64 loop filter limit
values is defined, one for each qi value.
The precise specification of how all of this information is decoded appears
in Section 6.4.1 and Section 6.4.2.

3.1.3

Huffman Codebooks

Theora uses 80 configurable binary Huffman codes to represent the 32 tokens
used to encode DCT coefficients. Each of the 32 token values has a different
semantic meaning and is used to represent single coefficient values, zero runs,
combinations of the two, and End-Of-Block markers.
The 80 codes are divided up into five groups of 16, with each group corresponding to a set of DCT coefficient indices. The first group corresponds to the
DC coefficient, while the remaining four groups correspond to different subsetsof the AC coefficients. Within each frame, two pairs of 4-bit codebook indices
are stored. The first pair selects which codebooks to use from the DC coefficientgroup for the Y 0 coefficients and the Cb and Cr coefficients. The second pairselects which codebooks to use from all four of the AC coefficient groups for theY 0 coefficients and the Cb and Cr coefficients.

3.2. HIGH-LEVEL DECODE PROCESS

15

The precise specification of how the codebooks are decoded appears in Section 6.4.4.

3.2

High-Level Decode Process

3.2.1

Decoder Setup

Before decoding can begin, a decoder MUST be initialized using the bitstream
headers corresponding to the stream to be decoded. Theora uses three header
packets; all are required, in order, by this specification. Once set up, decode
may begin at any intra-frame packet—or even inter-frame packets, provided theappropriate decoded reference frames have already been decoded and cached—belonging to the Theora stream. In Theora I, all packets after the three initialheaders are intra-frame or inter-frame packets.
The header packets are, in order, the identification header, the comment
header, and the setup header.
Identification Header
The identification header identifies the stream as Theora, provides a version
number, and defines the characteristics of the video stream such as frame size.
A complete description of the identification header appears in Section 6.2.
Comment Header
The comment header includes user text comments (‘tags’) and a vendor string
for the application/library that produced the stream. The format of the comment header is the same as that used in the Vorbis I and Speex codecs, withslight modifications due to the use of a different bit packing mechanism. A complete description of how the comment header is coded appears in Section 6.3,
along with a suggested set of tags.
Setup Header
The setup header includes extensive codec setup information, including the complete set of quantization matrices and Huffman codebooks needed to decode the
DCT coefficients. A complete description of the setup header appears in Section 6.4.

3.2.2

Decode Procedure

The decoding and synthesis procedure for all video packets is fundamentally thesame, with some steps omitted for intra frames.
• Decode packet type flag.
• Decode frame header.

16

CHAPTER 3. DECODING OVERVIEW• Decode coded block information (inter frames only).
• Decode macro block mode information (inter frames only).
• Decode motion vectors (inter frames only).
• Decode block-level qi information.
• Decode DC coefficient for each coded block.
• Decode 1st AC coefficient for each coded block.
• Decode 2nd AC coefficient for each coded block.
• ...
• Decode 63rd AC coefficient for each coded block.
• Perform DC coefficient prediction.
• Reconstruct coded blocks.
• Copy uncoded bocks.
• Perform loop filtering.
Note: clever rearrangement of the steps in this process is possible. As an example, in a memory-constrained environment, one
can make multiple passes through the DCT coefficients to avoid
buffering them all in memory. On the first pass, the starting
location of each coefficient is identified, and then 64 separate getpointers are used to read in the 64 DCT coefficients required toreconstruct each coded block in sequence. This operation produces entirely equivalent output and is naturally perfectly legal.
It may even be a benefit in non-memory-constrained environments due to a reduced cache footprint.

Theora makes equivalence easy to check by defining all decoding operationsin terms of exact integer operations. No floating-point math is required, andin particular, the implementation of the iDCT transform MUST be followed
precisely. This prevents the decoder mismatch problem commonly associatedwith codecs that provide a less rigorous transform specification. Such a mismatch problem would be devastating to Theora, since a single rounding error in
one frame could propagate throughout the entire succeeding frame due to DC
prediction.

3.2. HIGH-LEVEL DECODE PROCESS

17

Packet Type Decode
Theora uses four packet types. The first three packet types mark each of thethree Theora headers described above. The fourth packet type marks a video
packet. All other packet types are reserved; packets marked with a reserved
type should be ignored.
Additionally, zero-length packets are treated as if they were an inter framewith no blocks coded. That is, as a duplicate frame.
Frame Header Decode
The frame header contains some global information about the current frame.
The first is the frame type field, which specifies if this is an intra frame oran inter frame. Inter frames predict their contents from previously decodedreference frames. Intra frames can be independently decoded with no establishedreference frames.
The next piece of information in the frame header is the list of qi values
allowed in the frame. Theora allows from one to three different qi values to be
used in a single frame, each of which selects a set of six quantization matrices,
one for each quantization type (inter or intra), and one for each color plane.
The first qi value is always used when dequantizing DC coefficients. The qi
value used when dequantizing AC coefficients, however, can vary from block toblock. VP3, in contrast, only allows a single qi value per frame for both the DC
and AC coefficients.
Coded Block Information
This stage determines which blocks in the frame are coded and which are uncoded. A coded block list is constructed which lists all the coded blocks in coded
order. For intra frames, every block is coded, and so no data needs to be readfrom the packet.
Macro Block Mode Information
For intra frames, every block is coded in INTRA mode, and this stage is skipped.
In inter frames a coded macro block list is constructed from the coded block list.
Any macro block which has at least one of its luma blocks coded is considered
coded; all other macro blocks are uncoded, even if they contain coded chroma
blocks. A coding mode is decoded for each coded macro block, and assigned
to all its constituent coded blocks. All coded chroma blocks in uncoded macro
blocks are assigned the INTER NOMV coding mode.
Motion Vectors
Intra frames are coded entirely in INTRA mode, and so this stage is skipped.
Some inter coding modes, however, require one or more motion vectors to be

18

CHAPTER 3. DECODING OVERVIEW

specified for each macro block. These are decoded in this stage, and an appropriate motion vector is assigned to each coded block in the macro block.
Block-Level qi Information
If a frame allows multiple qi values, the qi value assigned to each block is
decoded here. Frames that use only a single qi value have nothing to decode.
DCT Coefficients
Finally, the quantized DCT coefficients are decoded. A list of DCT coefficientsin zig-zag order for a single block is represented by a list of tokens. A token
can take on one of 32 different values, each with a different semantic meaning.
A single token can represent a single DCT coefficient, a run of zero coefficients
within a single block, a combination of a run of zero coefficients followed by asingle non-zero coefficient, an End-Of-Block marker, or a run of EOB markers.
EOB markers signify that the remainder of the block is one long zero run. Unlike
JPEG and MPEG, there is no requirement for each block to end with a special
marker. If non-EOB tokens yield values for all 64 of the coefficients in a block,then no EOB marker occurs.
Each token is associated with a specific token index in a block. For singlecoefficient tokens, this index is the zig-zag index of the token in the block. For
zero-run tokens, this index is the zig-zag index of the first coefficient in therun. For combination tokens, the index is again the zig-zag index of the firstcoefficient in the zero run. For EOB markers, which signify that the remainderof the block is one long zero run, the index is the zig-zag index of the first zerocoefficient in that run. For EOB runs, the token index is that of the first EOB
marker in the run. Due to zero runs and EOB markers, a block does not haveto have a token for every zig-zag index.
Tokens are grouped in the stream by token index, not by the block they
originate from. This means that for each zig-zag index in turn, the tokens withthat index from all the coded blocks are coded in coded block order. When
decoding, a current token index is maintained for each coded block. This index
is advanced by the number of coefficients that are added to the block as eachtoken is decoded. After fully decoding all the tokens with token index ti , thecurrent token index of every coded block will be ti or greater.
If an EOB run of n blocks is decoded at token index ti , then it ends thenext n blocks in coded block order whose current token index is equal to ti , but
not greater. If there are fewer than n blocks with a current token index of ti ,then the decoder goes through the coded block list again from the start, ending
blocks with a current token index of ti + 1, and so on, until n blocks have been
ended.
Tokens are read by parsing a Huffman code that depends on ti and the color
plane of the next coded block whose current token index is equal to ti , but not
greater. The Huffman codebooks are selected on a per-frame basis from the 80
codebooks defined in the setup header. Many tokens have a fixed number of3.2. HIGH-LEVEL DECODE PROCESS

19

extra bits associated with them. These bits are read from the packet immediately
after the token is decoded. These are used to define things such as coefficientmagnitude, sign, and the length of runs.
DC Prediction
After the coefficients for each block are decoded, the quantized DC value of eachblock is adjusted based on the DC values of its neighbors. This adjustment isperformed by scanning the blocks in raster order, not coded block order.
Reconstruction
Finally, using the coding mode, motion vector (if applicable), quantized coefficient list, and qi value defined for each block, all the coded blocks are reconstructed. The DCT coefficients are dequantized, an inverse DCT transform isapplied, and the predictor is formed from the coding mode and motion vector
and added to the result.
Loop Filtering
To complete the reconstructed frame, an “in-loop” deblocking filter is applied
to the edges of all coded blocks.

20

CHAPTER 3. DECODING OVERVIEWChapter 4

Video Formats
This section gives a precise description of the video formats that Theora is capable of storing. The Theora bitstream is capable of handling video at any
arbitrary resolution up to 1048560 × 1048560. Such video would require almost three terabytes of storage per frame for uncompressed data, so compliant
decoders MAY refuse to decode images with sizes beyond their capabilities.
The remainder of this section talks about two specific aspects of the video
format: the color space and the pixel format. The first describes how color
is represented and how to transform that color representation into a device
independent color space such as CIE XY Z (1931). The second describes thevarious schemes for sampling the color values in time and space.

4.1

Color Space Conventions

There are a large number of different color standards used in digital video. Since
Theora is a lossy codec, it restricts itself to only a few of them to simplify playback. Unlike the alternate method of describing all the parameters of the color
model, this allows a few dedicated routines for color conversion to be written
and heavily optimized in a decoder. More flexible conversion functions should
instead be specified in an encoder, where additional computational complexity
is more easily tolerated. The color spaces were selected to give a fair representation of color standards in use around the world today. Most of the standards
that do not exactly match one of these can be converted to one fairly easily.
All Theora color spaces are Y 0 Cb Cr color spaces with one luma channel
and two chroma channels. Each channel contains 8-bit discrete values in therange 0 . . . 255, which represent non-linear gamma pre-corrected signals. The
Theora identification header contains an 8-bit value that describes the color
space. This merely selects one of the color spaces available from an enumerated
list. Currently, only two color spaces are defined, with a third possibility thatindicates the color space is “unknown”.
21

22

4.2

CHAPTER 4. VIDEO FORMATS

Color Space Conversions and Parameters

The parameters which describe the conversions between each color space arelisted below. These are the parameters needed to map colors from the encoded
Y 0 Cb Cr representation to the device-independent color space CIE XY Z (1931).
These parameters define abstract mathematical conversion functions which are
infinitely precise. The accuracy and precision with which the conversions are
performed in a real system is determined by the quality of output desired and theavailable processing power. Exact decoder output is defined by this specification
only in the original Y 0 Cb Cr space.
Y 0 Cb Cr to Y 0 Pb Pr :This conversion takes 8-bit discrete values in the range [0 . . . 255] and maps
them to real values in the range [0 . . . 1] for Y and [− 12 . . . 12 ] for Pb andPr . Because some values may fall outside the offset and excursion definedfor each channel in the Y 0 Cb Cr space, the results may fall outside theseranges in Y 0 Pb Pr space. No clamping should be done at this stage.
Yin0 − OffsetY
ExcursionYCb − OffsetCb
Pb =ExcursionCb
Cr − OffsetCr
Pr =ExcursionCr

0
Yout
=

(4.1)
(4.2)
(4.3)

Parameters: OffsetY,Cb ,Cr , ExcursionY,Cb ,Cr .
Y 0 Pb Pr to R0 G0 B 0 :This conversion takes the one luma and two chroma channel representationand maps it to the non-linear R0 G0 B 0 space used to drive actual output
devices. Values should be clamped into the range [0 . . . 1] after this stage.

R0 = Y 0 + 2(1 − Kr )Pr(1 − Kb )Kb(1 − Kr )Kr
Pb − 2Pr
1 − Kb − Kr
1 − Kb − Kr
B 0 = Y 0 + 2(1 − Kb )Pb
G0 = Y 0 − 2

Parameters: Kb , Kr .
R0 G0 B 0 to RGB (Output device gamma correction):

(4.4)
(4.5)
(4.6)

4.2. COLOR SPACE CONVERSIONS AND PARAMETERS

23

This conversion takes the non-linear R0 G0 B 0 voltage levels and maps themto linear light levels produced by the actual output device. Note that thisconversion is only that of the output device, and its inverse is not thatused by the input device. Because a dim viewing environment is assumed
in most television standards, the overall gamma between the input andoutput devices is usually around 1.1 to 1.2, and not a strict 1.0.
For calibration with actual output devices, the model
L = (E 0 + ∆)γ(4.7)

should be used, with ∆ the free parameter and γ held fixed to the value
specified in this document. The conversion function presented here is an
idealized version with ∆ = 0.

R = R0γ(4.8)

G = G0γ(4.9)

0γ(4.10)

B=B
Parameters: γ.

RGB to R0 G0 B 0 (Input device gamma correction):
This conversion takes linear light levels and maps them to the non-linear
voltage levels produced in the actual input device. This information ismerely informative. It is not required for building a decoder or for converting between the various formats and the actual output capabilities ofa particular device.
A linear segment is introduced on the low end to reduce noise in darkareas of the image. The rest of the scale is adjusted so that the power
segment of the curve intersects the linear segment with the proper slope,and so that it still maps 0 to 0 and 1 to 1.

0



R =
G0 =
B0 =
Parameters: β, α, δ, .
RGB to CIE XY Z (1931):




αR,
0≤R<δ
(1 + )Rβ − , δ ≤ R ≤ 1(4.11)αG,0≤G<δ(1 + )Gβ − , δ ≤ G ≤ 1(4.12)αB,0≤B<δ(1 + )B β − , δ ≤ B ≤ 1(4.13)

24

CHAPTER 4. VIDEO FORMATS
This conversion maps a device-dependent linear RGB space to the deviceindependent linear CIE XY Z space. The parameters are the CIE chromaticity coordinates of the three primaries—red, green, and blue—as wellas the chromaticity coordinates of the white point of the device. This is
how hardware manufacturers and standards typically describe a particular
RGB space. The math required to convert these parameters into a usefultransformation matrix is reproduced below.
xg
yg

xb
yb



1

1

1

1−xr −yryr

1−xg −ygyg

1−xb −yb
yb






xr
yr


F =




xw
sr
yw
 sg  = F −1 
1
1−xw −yw
sb
y


w

sr R
X
 Y  = F  sg G 
sb BZ(4.14)

(4.15)(4.16)

Parameters: xr , xg , xb , xw , yr , yg , yb , yw .

4.3

Available Color Spaces

These are the color spaces currently defined for use by Theora video. Each one
has a short name, with which it is referred to in this document, and a moredetailed specification of the standards from which its parameters are derived.
Some standards do not specify all the parameters necessary. For these unspecified parameters, this document serves as the definition of what should be used
when encoding or decoding Theora video.

4.3.1

Rec. 470M (Rec. ITU-R BT.470-6 System M/NTSC
with Rec. ITU-R BT.601-5)

This color space is used by broadcast television and DVDs in much of theAmericas, Japan, Korea, and the Union of Myanmar [ITU98]. This color space
may also be used for System M/PAL (Brazil), with an appropriate conversion
supplied by the encoder to compensate for the different gamma value. See
Section 4.3.2 for an appropriate gamma value to assume for M/PAL input.
In the US, studio monitors are adjusted to a D65 white point (xw , yw =0.313, 0.329). In Japan, studio monitors are adjusted to a D white of 9300K(xw , yw = 0.285, 0.293).
Rec. 470 does not specify a digital encoding of the color signals. For Theora,
Rec. ITU-R BT.601-5 [ITU95] is used, starting from the R0 G0 B 0 signals specified
by Rec. 470.

4.3. AVAILABLE COLOR SPACES

25

Rec. 470 does not specify an input gamma function. For Theora, the Rec. 709[ITU02] input function is assumed. This is the same as that specified by SMPTE
170M [SMP94], which claims to reflect modern practice in the creation of NTSC
signals circa 1994.
The parameters for all the color transformations defined in Section 4.2 aregiven in Table 4.1.

OffsetY,Cb ,Cr = (16, 128, 128)
ExcursionY,Cb ,Cr = (219, 224, 224)
Kr = 0.299
Kb = 0.114
γ = 2.2
β = 0.45
α = 4.5
δ = 0.018
 = 0.099
xr , yr = 0.67, 0.33
xg , yg = 0.21, 0.71
xb , yb = 0.14, 0.08
(Illuminant C) xw , yw = 0.310, 0.316

Table 4.1: Rec. 470M Parameters

4.3.2

Rec. 470BG (Rec. ITU-R BT.470-6 Systems B andG with Rec. ITU-R BT.601-5)

This color space is used by the PAL and SECAM systems in much of the restof the world [ITU98] This can be used directly by systems (B, B1, D, D1, G, H,
I, K, N)/PAL and (B, D, G, H, K, K1, L)/SECAM.
Note: the Rec. 470BG chromaticity values are different from thosespecified in Rec. 470M. When PAL and SECAM systems werefirst designed, they were based upon the same primaries as NTSC.
However, as methods of making color picture tubes have changed,
the primaries used have changed as well. The U.S. recommends
using correction circuitry to approximate the existing, standard
NTSC primaries. Current PAL and SECAM systems have standardized on primaries in accord with more recent technology.

26

CHAPTER 4. VIDEO FORMATS

Rec. 470 provisionally permits the use of the NTSC chromaticity values(given in Section 4.3.1) with legacy PAL and SECAM equipment. In Theora,material must be decoded assuming the new PAL and SECAM primaries. Material intended for display on old legacy devices should be converted by the
decoder.
The official Rec. 470BG specifies a gamma value of γ = 2.8. However, inpractice this value is unrealistically high [Poy97]. Rec. 470BG states that theoverall system gamma should be approximately γβ = 1.2. Since most cameras
pre-correct with a gamma value of β = 0.45, this suggests an output device
gamma of approximately γ = 2.67. This is the value recommended for use with
PAL systems in Theora.
Rec. 470 does not specify a digital encoding of the color signals. For Theora,
Rec. ITU-R BT.601-5 [ITU95] is used, starting from the R0 G0 B 0 signals specified
by Rec. 470.
Rec. 470 does not specify an input gamma function. For Theora, the Rec
709 [ITU02] input function is assumed.
The parameters for all the color transformations defined in Section 4.2 aregiven in Table 4.2.

OffsetY,Cb ,Cr = (16, 128, 128)
ExcursionY,Cb ,Cr = (219, 224, 224)
Kr = 0.299
Kb = 0.114
γ = 2.67
β = 0.45
α = 4.5
δ = 0.018
 = 0.099
xr , yr = 0.64, 0.33
xg , yg = 0.29, 0.60
xb , yb = 0.15, 0.06
(D65) xw , yw = 0.313, 0.329

Table 4.2: Rec. 470BG Parameters

4.4

Pixel Formats

Theora supports several different pixel formats, each of which uses different
subsampling for the chroma planes relative to the luma plane. A decoder may

4.4. PIXEL FORMATS

27

need to recover a full resolution chroma plane with samples co-sited with theluma plane in order to convert to RGB for display or perform other processing. Decoders can assume that the chroma signal satisfies the Nyquist-Shannon
sampling theorem. The ideal low-pass reconstruction filter this implies is notpractical, but any suitable approximation can be used, depending on the available computing power. Decoders MAY simply use a box filter, assigning to eachluma sample the chroma sample closest to it. Encoders would not go wrong inassuming that this will be the most common approach.

4.4.1

4:4:4 Subsampling

All three color planes are stored at full resolution—each pixel has a Y 0 , a Cb
and a Cr value (see Figure 4.1). The samples in the different planes are all at
co-located sites.
Frame: chroma plane Cr

Frame: chroma plane Cb

Frame: luma planeY’

Pixels(0,0)

Figure 4.1: Pixels encoded 4:4:4

4.4.2

4:2:2 Subsampling

The Cb and Cr planes are stored with half the horizontal resolution of the Y 0plane. Thus, each of these planes has half the number of horizontal blocks as the28

CHAPTER 4. VIDEO FORMATS

luma plane (see Figure 4.2). Similarly, they have half the number of horizontal
super blocks, rounded up. Macro blocks are defined across color planes, andso their number does not change, but each macro block contains half as many
chroma blocks.
The chroma samples are vertically aligned with the luma samples, but horizontally centered between two luma samples. Thus, each luma sample has aunique closest chroma sample. A horizontal phase shift may be required to
produce signals which use different horizontal chroma sampling locations forcompatibility with different systems.
Frame: chroma plane Cr

Frame: chroma plane Cb

Frame: luma planeY’

Pixels(0,0)

Figure 4.2: Pixels encoded 4:2:2

4.4.3

4:2:0 Subsampling

The Cb and Cr planes are stored with half the horizontal and half the verticalresolution of the Y 0 plane. Thus, each of these planes has half the number ofhorizontal blocks and half the number of vertical blocks as the luma plane, for a
total of one quarter the number of blocks (see Figure 4.3). Similarly, they have
half the number of horizontal super blocks and half the number of vertical super
blocks, rounded up. Macro blocks are defined across color planes, and so their4.4. PIXEL FORMATS

29

number does not change, but each macro block contains within it one quarteras many chroma blocks.
The chroma samples are vertically and horizontally centered between four
luma samples. Thus, each luma sample has a unique closest chroma sample.
This is the same sub-sampling pattern used with JPEG, MJPEG, and MPEG1, and was inherited from VP3. A horizontal or vertical phase shift may berequired to produce signals which use different chroma sampling locations forcompatibility with different systems.
Frame: chroma plane Cr

Frame: chroma plane Cb

Frame: luma planeY’

Pixels(0,0)

Figure 4.3: Pixels encoded 4:2:0

4.4.4

Subsampling and the Picture Region

Although the frame size must be an integral number of macro blocks, and thus
both the number of pixels and the number of blocks in each direction must be
even, no such requirement is made of the picture region. Thus, when using subsampled pixel formats, careful attention must be paid to which chroma samples
correspond to which luma samples.
As mentioned above, for each pixel format, there is a unique chroma sample
that is the closest to each luma sample. When cropping the chroma planes tothe picture region, all the chroma samples corresponding to a luma sample in

30

CHAPTER 4. VIDEO FORMATS

the cropped picture region must be included. Thus, when dividing the width orheight of the picture region by two to obtain the size of the subsampled chroma
planes, they must be rounded up.
Furthermore, the sampling locations are defined relative to the frame, notthe picture region. When using the 4:2:2 and 4:2:0 formats, the locations ofchroma samples relative to the luma samples depends on whether or not the X
offset of the picture region is odd. If the offset is even, each column of chroma
samples corresponds to two columns of luma samples (see Figure 4.4 for an
example). The only exception is if the width is odd, in which case the lastcolumn corresponds to only one column of luma samples (see Figure 4.5). If
the offset is odd, then the first column of chroma samples corresponds to only
one column of luma samples, while the remaining columns each correspond totwo (see Figure 4.6). In this case, if the width is even, the last column again
corresponds to only one column of luma samples (see Figure 4.7).
A similar process is followed with the rows of a picture region of odd height
encoded in the 4:2:0 format. If the Y offset is even, each row of chroma samples
corresponds to two rows of luma samples (see Figure 4.4), except with an odd
height, where the last row corresponds to one row of chroma luna samples only
(see Figure 4.5). If the offset is odd, then it is the first row of chroma samples
which corresponds to only one row of luma samples, while the remaining rows
each correspond to two (Figure 4.6), except with an even height, where the last
row also corresponds to one (Figure 4.7).
Encoders should be aware of these differences in the subsampling when using
an even or odd offset. In the typical case, with an even width and height, where
one expects two rows or columns of luma samples for every row or column ofchroma samples, the encoder must take care to ensure that the offsets used areboth even.
Frame: chroma (4:2:2 case)...

Frame: luma

...
(0,0)

...

Frame: chroma (4:2:0 case)

...
(0,0)

...
...

Pixels(0,0)

Figure 4.4: Pixel correspondence between color planes with even picture offset
and even picture size

4.4. PIXEL FORMATS

31

Frame: chroma (4:2:2 case)...

Frame: luma...

Frame: chroma (4:2:0 case)

...
(0,0)

...

...
...

(0,0)

Pixels(0,0)

Figure 4.5: Pixel correspondence with even picture offset and odd picture size
Frame: chroma (4:2:2 case)...

Frame: luma...

Frame: chroma (4:2:0 case)

...
(0,0)

...

...
...

(0,0)

Pixels(0,0)

Figure 4.6: Pixel correspondence with odd picture offset and odd picture size
Frame: chroma (4:2:2 case)...

Frame: luma

...
(0,0)

...

Frame: chroma (4:2:0 case)

...
(0,0)

...
...

Pixels(0,0)

Figure 4.7: Pixel correspondence with odd picture offset and even picture size

32

CHAPTER 4. VIDEO FORMATS

Chapter 5

Bitpacking Convention
5.1

Overview

The Theora codec uses relatively unstructured raw packets containing binary
integer fields of arbitrary width. Logically, each packet is a bitstream in whichbits are written one-by-one by the encoder and then read one-by-one in the sameorder by the decoder. Most current binary storage arrangements group bits intoa native storage unit of eight bits (octets), sixteen bits, thirty-two bits, or lesscommonly other fixed sizes. The Theora bitpacking convention specifies thecorrect mapping of the logical packet bitstream into an actual representation in
fixed-width units.

5.1.1

Octets and Bytes

In most contemporary architectures, a ‘byte’ is synonymous with an ‘octect’,that is, eight bits. For purposes of the bitpacking convention, a byte implies thesmallest native integer storage representation offered by a platform. Modern
file systems invariably offer bytes as the fundamental atom of storage.
The most ubiquitous architectures today consider a ‘byte’ to be an octet.
Note, however, that the Theora bitpacking convention is still well defined forany native byte size; an implementation can use the native bit-width of a given
storage system. This document assumes that a byte is one octet for purposesof example only.

5.1.2

Words and Byte OrderA ‘word’ is an integer size that is a grouped multiple of the byte size. Mostarchitectures consider a word to be a group of two, four, or eight bytes. Eachbyte in the word can be ranked by order of ‘significance’, e.g. the significanceof the bits in each byte when storing a binary integer in the word. Several byteorderings are possible in a word. The common ones are
33

34

CHAPTER 5. BITPACKING CONVENTION• Big-endian: in which the most significant byte comes first, e.g. 3-2-1-0,• Little-endian: in which the least significant byte comes first, e.g. 0-1-2-3,
and• Mixed-endian: one of the less-common orderings that cannot be put into
the above two categories, e.g. 3-1-2-0 or 0-2-1-3.

The Theora bitpacking convention specifies storage and bitstream manipulation at the byte, not word, level. Thus host word ordering is of a concern only
during optimization, when writing code that operates on a word of storage ata time rather than a byte. Logically, bytes are always encoded and decoded inorder from byte zero through byte n.

5.1.3

Bit Order

A byte has a well-defined ‘least significant’ bit (LSb), which is the only bit set
when the byte is storing the two’s complement integer value +1. A byte’s ‘most
significant’ bit (MSb) is at the opposite end. Bits in a byte are numbered fromzero at the LSb to n for the MSb, where n = 7 in an octet.

5.2

Coding Bits into Bytes

The Theora codec needs to encode arbitrary bit-width integers from zero to 32
bits wide into packets. These integer fields are not aligned to the boundaries ofthe byte representation; the next field is read at the bit position immediately
after the end of the previous field.
The decoder logically unpacks integers by first reading the MSb of a binary
integer from the logical bitstream, followed by the next most significant bit,etc., until the required number of bits have been read. When unpacking thebytes into bits, the decoder begins by reading the MSb of the integer to be readfrom the most significant unread bit position of the source byte, followed by thenext-most significant bit position of the destination integer, and so on up to therequested number of bits. Note that this differs from the Vorbis I codec, which
begins decoding with the LSb of the source integer, reading it from the LSb of
the source byte. When all the bits of the current source byte are read, decoding
continues with the MSb of the next byte. Any unfilled bits in the last byte of
the packet MUST be cleared to zero by the encoder.

5.2.1

Signedness

The binary integers decoded by the above process may be either signed orunsigned. This varies from integer to integer, and this specification indicates
how each value should be interpreted as it is read. That is, depending oncontext, the three bit binary pattern b111 can be taken to represent either ‘7’
as an unsigned integer or ‘−1’ as a signed, two’s complement integer.

5.2. CODING BITS INTO BYTES

5.2.2

35

Encoding Example

The following example shows the state of an (8-bit) byte stream after several
binary integers are encoded, including the location of the put pointer for the
next bit to write to and the total length of the stream in bytes.
Encode the 4 bit unsigned integer value ‘12’ (b1100) into an empty byte
stream.

byte 0byte 1byte 2byte 3..
.
byte n

7
1
0
0
0

6
1
0
0
0

5
0
0
0
0

4
0
0
0
0

↓
3
0
0
0
0

2
0
0
0
0

1
0
0
0
0

0
0
0
0
0

0

0

0

0

←

..
.
0

0

0

0

byte stream length: 1 byte

Continue by encoding the 3 bit signed integer value ‘-1’ (b111).

byte 0byte 1byte 2byte 3..
.
byte n

7
1
0
0
0

6
1
0
0
0

5
0
0
0
0

4
0
0
0
0

3
1
0
0
0

2
1
0
0
0

1
1
0
0
0

↓
0
0
0
0
0

0

0

0

0

←

..
.
0

0

0

0

byte stream length: 1 byte

Continue by encoding the 7 bit integer value ‘17’ (b0010001).

byte 0byte 1byte 2byte 3..
.
byte n

7
1
0
0
0

6
1
1
0
0

5
0
0
0
0

4
0
0
0
0

3
1
0
0
0

2
1
1
0
0

↓
1
1
0
0
0

0
0
0
0
0

←

0

0

0

0

byte stream length: 2 bytes

..
.
0

0

0

0

Continue by encoding the 13 bit integer value ‘6969’ (b11011 00111001).

36

CHAPTER 5. BITPACKING CONVENTION

byte 0byte 1byte 2byte 3..
.
byte n

5.2.3

7
1
0
0
0

6
1
1
1
0

5
0
0
1
1

↓
4
0
0
0
0

3
1
0
0
0

2
1
1
1
0

1
1
1
1
0

0
0
1
1
0

←

0

0

0

0

byte stream length: 4 bytes

..
.
0

0

0

0

Decoding Example

The following example shows the state of the (8-bit) byte stream encoded in
the previous example after several binary integers are decoded, including thelocation of the get pointer for the next bit to read.
Read a two bit unsigned integer from the example encoded above.
↓7 6 5 4 3 2 1 0
byte 0 1 1 0 0 1 1 1 0 ←byte 1 0 1 0 0 0 1 1 1
byte 2 0 1 1 0 0 1 1 1
byte 3 0 0 1 0 0 0 0 0 byte stream length: 4 bytes
Value read: 3 (b11).
Read another two bit unsigned integer from the example encoded above.
↓7 6 5 4 3 2 1 0
byte 0 1 1 0 0 1 1 1 0 ←byte 1 0 1 0 0 0 1 1 1
byte 2 0 1 1 0 0 1 1 1
byte 3 0 0 1 0 0 0 0 0 byte stream length: 4 bytes
Value read: 0 (b00).
Two things are worth noting here.
• Although these four bits were originally written as a single four-bit integer, reading some other combination of bit-widths from the bitstream
is well defined. No artificial alignment boundaries are maintained in the
bitstream.
• The first value is the integer ‘3’ only because the context stated we werereading an unsigned integer. Had the context stated we were reading asigned integer, the returned value would have been the integer ‘−1’.

5.2. CODING BITS INTO BYTES

5.2.4

37

End-of-Packet Alignment

The typical use of bitpacking is to produce many independent byte-aligned
packets which are embedded into a larger byte-aligned container structure, suchas an Ogg transport bitstream. Externally, each bitstream encoded as a byte
stream MUST begin and end on a byte boundary. Often, the encoded packet
bitstream is not an integer number of bytes, and so there is unused space in thelast byte of a packet.
When a Theora encoder produces packets for embedding in a byte-aligned
container, unused space in the last byte of a packet is always zeroed during theencoding process. Thus, should this unused space be read, it will return binary
zeroes. There is no marker pattern or stuffing bits that will allow the decoder
to obtain the exact size, in bits, of the original bitstream. This knowledge is
not required for decoding.
Attempting to read past the end of an encoded packet results in an ‘end-ofpacket’ condition. Any further read operations after an ‘end-of-packet’ condition
shall also return ‘end-of-packet’. Unlike Vorbis, Theora does not use truncatedpackets as a normal mode of operation. Therefore if a decoder encounters the‘end-of-packet’ condition during normal decoding, it may attempt to use thebits that were read to recover as much of encoded data as possible, signal awarning or error, or both.

5.2.5

Reading Zero Bit Integers

Reading a zero bit integer returns the value ‘0’ and does not increment thestream pointer. Reading to the end of the packet, but not past the end, sothat an ‘end-of-packet’ condition is not triggered, and then reading a zero bit
integer shall succeed, returning ‘0’, and not trigger an ‘end-of-packet’ condition.
Reading a zero bit integer after a previous read sets the ‘end-of-packet’ condition
shall fail, also returning ‘end-of-packet’.

38

CHAPTER 5. BITPACKING CONVENTION

Chapter 6

Bitstream Headers
A Theora bitstream begins with three header packets. The header packets
are, in order, the identification header, the comment header, and the setup
header. All are required for decode compliance. An end-of-packet condition
encountered while decoding the identification or setup header packets renders
the stream undecodable. An end-of-packet condition encountered while decodethe comment header is a non-fatal error condition, and MAY be ignored by adecoder.
VP3 Compatibility
VP3 relies on the headers provided by its container, usually either AVI or Quicktime. As such, several parameters available in these headers are not available
to VP3 streams. These are indicated as they appear in the sections below.

6.1

Common Header Decode012
3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| header type |
‘t’
|
‘h’
|
‘e’
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
‘o’
|
‘r’
|
‘a’
|
data...
|+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|... header-specific data ...
|
|
...
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 6.1: Common Header Packet Layout
39

40

CHAPTER 6. BITSTREAM HEADERS

Input parameters:
None.
Output parameters:

Name

Type

Size
(bits)HEADERTYPE

Integer8Signed?

Description and restrictions

No

The type of the header being decoded.

Variables used:
None.

Each header packet begins with the same header fields, which are decoded
as follows:

1. Read an 8-bit unsigned integer as HEADERTYPE. If the most significant bit of this integer is not set, then stop. This is not a header packet.

2. Read 6 8-bit unsigned integers. If these do not have the values 0x74, 0x68,
0x65, 0x6F, 0x72, and 0x61, respectively, then stop. This stream is notdecodable by this specification. These values correspond to the ASCII
values of the characters ‘t’, ‘h’, ‘e’, ‘o’, ‘r’, and ‘a’.

Decode continues according to HEADERTYPE. The identification header
is type 0x80, the comment header is type 0x81, and the setup header is type0x82. These packets must occur in the order: identification, comment, setup.
All header packets have the most significant bit of the type field—which is theinitial bit in the packet—set. This distinguishes them from video data packets
in which the first bit is unset. Packets with other header types (0x83–0xFF) arereserved and MUST be ignored.

6.2. IDENTIFICATION HEADER DECODE

6.2

41

Identification Header Decode012
3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
0x80
|
‘t’
|
‘h’
|
‘e’
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
‘o’
|
‘r’
|
‘a’
|
VMAJ
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
VMIN
|
VREV
|
FMBW
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|FMBH|
PICW...
|+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|...PICW|PICH|+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
PICX
|
PICY
|
FRN...
|+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|...FRN|
FRD...
|+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|...FRD|
PARN...
|+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|...PARN|
PARD|+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
CS
|
NOMBR
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|QUAL| KFGSHIFT| PF| Res |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 6.2: Identification Header Packet
Input parameters:
None.
Output parameters:

Name
VMAJ
VMIN
VREV

Type

Size
(bits)

Integer
Integer
Integer888Signed?

Description and restrictions

No
No
No

The major version number.
The minor version number.
The version revision number.

42

CHAPTER 6. BITSTREAM HEADERS
Name

Type

Size
(bits)

Signed?

Description and restrictions

FMBW

Integer

16

No

Integer

16

No

NSBS

Integer

32

No

NBS

Integer

36

No

NMBS

Integer

32

No

PICW

Integer

20

No

PICH

Integer

20

No

PICX

Integer

8

No

PICY

Integer

8

No

FRN
FRD
PARN

Integer
Integer
Integer

32
32
24

No
No
No

PARD

Integer

24

No

CS
PF
NOMBR

Integer
Integer
Integer

8
2
24

No
No
No

QUAL
KFGSHIFT

Integer
Integer

6
5

No
No

The width of the frame in macro
blocks.
The height of the frame in macro
blocks.
The total number of super blocks
in a frame.
The total number of blocks in aframe.
The total number of macro
blocks in a frame.
The width of the picture regionin pixels.
The height of the picture regionin pixels.
The X offset of the picture regionin pixels.
The Y offset of the picture regionin pixels.
The frame-rate numerator.
The frame-rate denominator.
The pixel aspect-ratio numerator.
The pixel aspect-ratio denominator.
The color space.
The pixel format.
The nominal bitrate of thestream, in bits per second.
The quality hint.
The amount to shift the key
frame number by in the granuleposition.

FMBH

Variables used:None.
The identification header is a short header with only a few fields used todeclare the stream definitively as Theora and provide detailed information about
the format of the fully decoded video data. The identification header is decoded
as follows:
1. Decode the common header fields according to the procedure described in
Section 6.1. If HEADERTYPE returned by this procedure is not 0x80,

6.2. IDENTIFICATION HEADER DECODE

43

then stop. This packet is not the identification header.
2. Read an 8-bit unsigned integer as VMAJ. If VMAJ is not 3, then stop.
This stream is not decodable according to this specification.
3. Read an 8-bit unsigned integer as VMIN. If VMIN is not 2, then stop.
This stream is not decodable according to this specification.
4. Read an 8-bit unsigned integer as VREV. If VREV is greater than 1,
then this stream may contain optional features or interpretational changes
documented in a future version of this specification. Regardless of thevalue of VREV, the stream is decodable according to this specification.
5. Read a 16-bit unsigned integer as FMBW. This MUST be greater thanzero. This specifies the width of the coded frame in macro blocks. The
actual width of the frame in pixels is FMBW ∗ 16.
6. Read a 16-bit unsigned integer as FMBH. This MUST be greater thanzero. This specifies the height of the coded frame in macro blocks. The
actual height of the frame in pixels is FMBH ∗ 16.
7. Read a 24-bit unsigned integer as PICW. This MUST be no greaterthan (FMBW ∗ 16). Note that 24 bits are read, even though only 20 bits
are sufficient to specify any value of the picture width. This is done topreserve octet alignment in this header, to allow for a simplified parser
implementation.
8. Read a 24-bit unsigned integer as PICH. This MUST be no greaterthan (FMBH ∗ 16). Together with PICW, this specifies the size of thedisplayable picture region within the coded frame. See Figure 2.1. Again,
24 bits are read instead of 20.
9. Read an 8-bit unsigned integer as PICX. This MUST be no greater than
(FMBW ∗ 16 − PICX).
10. Read an 8-bit unsigned integer as PICY. This MUST be no greater than
(FMBH ∗ 16 − PICY). Together with PICX, this specifies the locationof the lower-left corner of the displayable picture region. See Figure 2.1.
11. Read a 32-bit unsigned integer as FRN. This MUST be greater thanzero.
12. Read a 32-bit unsigned integer as FRD. This MUST be greater thanzero. Theora is a fixed-frame rate video codec. Frames are sampled at
the constant rate of FRN
FRD frames per second. The presentation time of
the first frame is at zero seconds. No mechanism is provided to specify anon-zero offset for the initial frame.
13. Read a 24-bit unsigned integer as PARN.

44

CHAPTER 6. BITSTREAM HEADERS

14. Read a 24-bit unsigned integer as PARD. Together with PARN, these
specify the aspect ratio of the pixels within a frame, defined as the ratioof the physical width of a pixel to its physical height. This is given by
the ratio PARN : PARD. If either of these fields are zero, this indicatesthat pixel aspect ratio information was not available to the encoder. In
this case it MAY be specified by the application via an external means,or a default value of 1 : 1 MAY be used.
15. Read an 8-bit unsigned integer as CS. This is a value from an enumerated
list of the available color spaces, given in Table 6.3. The ‘Undefined’ value
indicates that color space information was not available to the encoder. It
MAY be specified by the application via an external means. If a reserved
value is given, a decoder MAY refuse to decode the stream.
Value
0
1
2
3
..
.

Color Space
Undefined.
Rec. 470M (see Section 4.3.1).
Rec. 470BG (see Section 4.3.2).
Reserved.

255

Table 6.3: Enumerated List of Color Spaces
16. Read a 24-bit unsigned integer as NOMBR signifying a rate in bits per
second. Rates equal to or greater than 224 − 1 bits per second are represented as 224 − 1. The NOMBR field is used only as a hint. For pure
VBR streams, this value may be considerably off. The field MAY be set
to zero to indicate that the encoder did not care to speculate.
17. Read a 6-bit unsigned integer as QUAL. This value is used to provide
a hint as to the relative quality of the stream when compared to others
produced by the same encoder. Larger values indicate higher quality. Thiscan be used, for example, to select among several streams containing thesame material encoded with different settings.
18. Read a 5-bit unsigned integer as KFGSHIFT. The KFGSHIFT isused to partition the granule position associated with each packet into two
different parts. The frame number of the last key frame, starting from zero,is stored in the upper 64−KFGSHIFT bits, while the lower KFGSHIFT
bits contain the number of frames since the last keyframe. Complete
details on the granule position mapping are specified in Section REF.
19. Read a 2-bit unsigned integer as PF. The PF field contains a value froman enumerated list of the available pixel formats, given in Table 6.4. If the6.3. COMMENT HEADER

45

reserved value 1 is given, stop. This stream is not decodable according tothis specification.
Value
0
1
2
3

Pixel Format
4:2:0 (see Section 4.4.3).
Reserved.
4:2:2 (see Section 4.4.2).
4:4:4 (see Section 4.4.1).

Table 6.4: Enumerated List of Pixel Formats
20. Read a 3-bit unsigned integer. These bits are reserved. If this value
is not zero, then stop. This stream is not decodable according to thisspecification.
21. Assign NSBS a value according to PF, as given by Table 6.5.
22. Assign NBS a value according to PF, as given by Table 6.6.
23. Assign NMBS the value (FMBW ∗ FMBH).
VP3 Compatibility
VP3 does not correctly handle frame sizes that are not a multiple of 16. Thus,
PICW and PICH should be set to the frame width and height in pixels,
respectively, and PICX and PICY should be set to zero. VP3 headers do not
specify a color space. VP3 only supports the 4:2:0 pixel format.

6.3

Comment Header

The Theora comment header is the second of three header packets that begin
a Theora stream. It is meant for short text comments, not aribtrary metadata;

PF
0
2
3

NSBS
((FMBW + 1)//2) ∗ ((FMBH + 1)//2)+ 2 ∗ ((FMBW + 3)//4) ∗ ((FMBH + 3)//4)((FMBW + 1)//2) ∗ ((FMBH + 1)//2)+ 2 ∗ ((FMBW + 3)//4) ∗ ((FMBH + 1)//2)
3 ∗ ((FMBW + 1)//2) ∗ ((FMBH + 1)//2)

Table 6.5: Number of Super Blocks for each Pixel Format

46

CHAPTER 6. BITSTREAM HEADERS
PF

NBS

0

6 ∗ FMBW ∗ FMBH

28 ∗ FMBW ∗ FMBH

3

12 ∗ FMBW ∗ FMBH

Table 6.6: Number of Blocks for each Pixel Format
4 byte length

UTF-8 encoded string ...

Figure 6.3: Length encoded string layout
arbitrary metadata belongs in a separate logical stream that provides greater
structure and machine parseability.
The comment field is meant to be used much like someone jotting a quick
note on the label of a video. It should be a little information to remember thedisc or tape by and explain it to others; a short, to-the-point text note that canbe more than a couple words, but isn’t going to be more than a short paragraph.
The essentials, in other words, whatever they turn out to be, e.g.:
The comment header is stored as a logical list of eight-bit clean vectors; thenumber of vectors is bounded at 232 − 1 and the length of each vector is limited
to 232 − 1 bytes. The vector length is encoded; the vector contents themselves
are not null terminated. In addition to the vector list, there is a single vector
for a vendor name, also eight-bit clean with a length encoded in 32 bits.

6.3.1

Comment Length Decode

Input parameters:
None.
Output parameters:

Name

Type

Size
(bits)

LEN

Integer32

Signed?
No

Description and restrictions
A single 32-bit length value.

Variables used:

Name

Type

Size
(bits)

LEN0
LEN1
LEN2
LEN3

Integer
Integer
Integer
Integer8888Signed?

Description and restrictions

No
No
No
No

The first octet of the string length.
The second octet of the string length.
The third octet of the string length.
The fourth octet of the string length.

A single comment vector is decoded as follows:

6.3. COMMENT HEADER

47
vendor string
number of commentscomment string
comment string...

Figure 6.4: Comment Header Layout
3. Read an 8-bit unsigned integer as LEN2.
4. Read an 8-bit unsigned integer as LEN3.
5. Assign LEN the value (LEN0+(LEN1 << 8)+(LEN2 << 16)+(LEN3 <<24)). This construction is used so that on platforms with 8-bit bytes, thememory organization of the comment header is identical with that of Vorbis I, allowing for common parsing code despite the different bit packing
conventions.

6.3.2

Comment Header Decode

Input parameters:
None.
Output parameters:

Name

Type

Size
(bits)VENDORNCOMMENTS

StringInteger

COMMENTS

String Array

32

Signed?

No

Description and restrictions
The vendor string.
The number of user comments.
A list of NCOMMENTS
user comment values.

Variables used:

Name

Type

Size
(bits)

ci

Integer32

Signed?

Description and restrictions

No

The index of the current user comment.

The complete comment header is decoded as follows:
1. Decode the common header fields according to the procedure described in
Section 6.1. If HEADERTYPE returned by this procedure is not 0x81,
then stop. This packet is not the comment header.
2. Decode the length of the vendor string using the procedure given in Section 6.3.1 into LEN.

48

CHAPTER 6. BITSTREAM HEADERS
3. Read LEN 8-bit unsigned integers.
4. Set the string VENDOR to the contents of these octets.
5. Decode the number of user comments using the procedure given in Section 6.3.1 into LEN.
6. Assign NCOMMENTS the value stored in LEN.
7. For each consecutive value of ci from 0 to (NCOMMENTS − 1), inclusive:(a) Decode the length of the current user comment using the procedure
given in Section 6.3.1 into LEN.
(b) Read LEN 8-bit unsigned integers.
(c) Set the string COMMENTS[ci ] to the contents of these octets.

The comment header comprises the entirety of the second header packet.
Unlike the first header packet, it is not generally the only packet on the second
page and may span multiple pages. The length of the comment header packet is(practically) unbounded. The comment header packet is not optional; it must
be present in the stream even if it is logically empty.

6.3.3

User Comment Format

The user comment vectors are structured similarly to a UNIX environment
variable. That is, comment fields consist of a field name and a corresponding
value and look like:
COMMENTS[0]COMMENTS[1]==“TITLE=the look of Theora”“DIRECTOR=me”

The field name is case-insensitive and MUST consist of ASCII characters
0x20 through 0x7D, 0x3D (‘=’) excluded. ASCII 0x41 through 0x5A inclusive(characters ‘A’–‘Z’) are to be considered equivalent to ASCII 0x61 through0x7A inclusive (characters ‘a’–‘z’). An entirely empty field name—one that iszero characters long—is not disallowed.
The field name is immediately followed by ASCII 0x3D (‘=’); this equals sign
is used to terminate the field name.
The data immediately after 0x3D until the end of the vector is the eight-bit
clean value of the field contents encoded as a UTF-8 string [Yer96].
Field names MUST NOT be ‘internationalized’; this is a concession to simplicity, not an attempt to exclude the majority of the world that doesn’t speak
English. Applications MAY wish to present internationalized versions of thestandard field names listed below to the user, but they are not to be stored in
the bitstream. Field contents, however, use the UTF-8 character encoding toallow easy representation of any language.

6.3. COMMENT HEADER

49

Individual ‘vendors’ MAY use non-standard field names within reason. The
proper use of comment fields as human-readable notes has already been explained. Abuse will be discouraged.
There is no vendor-specific prefix to ‘non-standard’ field names. Vendors
SHOULD make some effort to avoid arbitrarily polluting the common namespace. Xiph.Org and other bodies will generally collect and rationalize the more
useful tags to help with standardization.
Field names are not restricted to occur only once within a comment header.
Field Names
Below is a proposed, minimal list of standard field names with a descriptionof their intended use. No field names are mandatory; a comment header may
contain one or more, all, or none of the names in this list.
TITLE: Video name.
ARTIST: Filmmaker or other creator name.
VERSION: Subtitle, remix info, or other text distinguishing versions of a video.
DATE: Date associated with the video. Implementations SHOULD attempt
to parse this field as an ISO 8601 date for machine interpretation andconversion.
LOCATION: Location associated with the video. This is usually the filming
location for non-fiction works.
COPYRIGHT: Copyright statement.
LICENSE: Copyright and other licensing information. Implementations wishing to do automatic parsing of e.g of distribution terms SHOULD lookhere for a URL uniquely defining the license. If no instance of this field ispresent, or if no instance contains a parseable URL, and implementation
MAY look in the COPYRIGHT field for such a URL.
ORGANIZATION: Studio name, Publisher, or other organization involved in
the creation of the video.
DIRECTOR: Director or Filmmaker credit, similar to ARTIST.
PRODUCER: Producer credit for the video.
COMPOSER: Music credit for the video.
ACTOR: Acting credit for the video.
TAG: subject or category tag, keyword, or other content classification labels.
The value of each instance of this field SHOULD be treated as a single
label, with multiple instances of the field for multiple tags. The value ofa single field SHOULD NOT be parsed into multiple tags based on someinternal delimeter.

50

CHAPTER 6. BITSTREAM HEADERS
common header block
loop filter table resolution
loop filter tablescale table resolution
AC scale table
DC scale table
number of base matricies
base quatization matricies...
quant range interpolation table
DCT token Huffman tables
Figure 6.5: Setup Header structure

DESCRIPTION: General description, summary, or blurb.

6.4

Setup Header

The Theora setup header contains the limit values used to drive the loop filter,the base matrices and scale values used to build the dequantization tables, andthe Huffman tables used to unpack the DCT tokens. Because the contents ofthis header are specific to Theora, no concessions have been made to keep thefields octet-aligned for easy parsing.

6.4.1

Loop Filter Limit Table Decode

Input parameters:
None.
Output parameters:

Name

Type

Size
(bits)

LFLIMS

Integerarray

7

Signed?

Description and restrictions

No

A 64-element array of loop filter
limit values.

Variables used:

Name

Type

Size
(bits)qi
NBITS

Integer
Integer63Signed?

Description and restrictions

No
No

The quantization index.
The size of values being read in the current table.

This procedure decodes the table of loop filter limit values used to drive theloop filter, which is described in Section 6.4.1. It is decoded as follows:

6.4. SETUP HEADER

51

VP3 Compatibility
The loop filter limit values are hardcoded in VP3. The values used are given in
Appendix B.2.

6.4.2

Quantization Parameters Decode

Input parameters:
None.
Output parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

ACSCALE

Integer
array

16

No

Integer
array

16

No

Integer
2D Integer
array
2D Integer
array

10
8

No
No

6

No

QRSIZES

3D Integer
array

6

No

QRBMIS

3D Integer
array

9

No

A 64-element array of scalevalues for AC coefficients foreach qi value.
A 64-element array of scalevalues for the DC coefficientfor each qi value.
The number of base matrices.
A NBMS × 64 array containing the base matrices.
A 2 × 3 array containing thenumber of quant ranges for agiven qti and pli , respectively.
This is at most 63.
A 2 × 3 × 63 array of thesizes of each quant range for agiven qti and pli , respectively.
Only the first NQRS[qti ][pli ]values are used.
A 2 × 3 × 64 array of the
bmi ’s used for each quantrange for a given qti and pli ,respectively. Only the first(NQRS[qti ][pli ] + 1) values
are used.

DCSCALE

NBMS
BMS
NQRS

52

CHAPTER 6. BITSTREAM HEADERS

Variables used:

Name

Type

Size
(bits)

Signed?

Description and restrictions

qti

Integer

1

No

Integer
Integer
Integer
Integer
Integer
Integer
Integer
Integer
Integer

1
2
2
6
6
9
6
5
1

No
No
No
No
No
No
No
No
No

Integer

1

No

A quantization type index. See Table 3.1.
A quantization type index.
A color plane index. See Table 2.1.
A color plane index.
The quantization index.
The DCT coefficient index.
The base matrix index.
The quant range index.
The size of fields to read.
Flag that indicates a new set of quantranges will be defined.
Flag that indicates the quant ranges
to copy will come from the same color
plane.

qtj
pli
plj
qi
ci
bmi
qri
NBITS
NEWQR
RPQR

The AC scale and DC scale values are defined in two simple tables with 64
values each, one for each qi value. The same scale values are used for every
quantization type and color plane.
The base matrices for all quantization types and color planes are stored in asingle table. These are then referenced by index in several sets of quant ranges.
The purpose of the quant ranges is to specify which base matrices are used forwhich qi values.
A set of quant ranges is defined for each quantization type and color plane.
To save space in the header, bit flags allow a set of quant ranges to be copied froma previously defined set instead of being specified explicitly. Every set except
the first one can be copied from the immediately preceding set. Similarly, if thequantization type is not 0, the set can be copied from the set defined for thesame color plane for the preceding quantization type. This formulation allows
compact representation of, for example, the same set of quant ranges in both
chroma channels, as is done in the original VP3, or the same set of quant ranges
in INTRA and INTER modes.
Each quant range is defined by a size and two base matrix indices, one foreach end of the range. The base matrix for the end of one range is used as thestart of the next range, so that for n ranges, n + 1 base matrices are specified.
The base matrices for the qi values between the two endpoints of the range are
generated by linear interpolation.
The location of the endpoints of each range is encoded by their size. The qi

6.4. SETUP HEADER

53

value for the left end-point is the sum of the sizes of all preceding ranges, andthe qi value for the right end-point adds the size of the current range. Thus thesum of the sizes of all the ranges MUST be 63, so that the last range falls on
the last possible qi value.
The complete set of quantization parameters are decoded as follows:
1. Read a 4-bit unsigned integer. Assign NBITS the value read, plus one.
2. For each consecutive value of qi from 0 to 63, inclusive:(a) Read an NBITS-bit unsigned integer as ACSCALE[qi ].
3. Read a 4-bit unsigned integer. Assign NBITS the value read, plus one.
4. For each consecutive value of qi from 0 to 63, inclusive:(a) Read an NBITS-bit unsigned integer as DCSCALE[qi ].
5. Read a 9-bit unsigned integer. Assign NBMS the value decoded, plus
one. NBMS MUST be no greater than 384.
6. For each consecutive value of bmi from 0 to (NBMS − 1), inclusive:(a) For each consecutive value of ci from 0 to 63, inclusive:i. Read an 8-bit unsigned integer as BMS[bmi ][ci ].
7. For each consecutive value of qti from 0 to 1, inclusive:(a) For each consecutive value of pli from 0 to 2, inclusive:i. If qti > 0 or pli > 0, read a 1-bit unsigned integer as NEWQR.
ii. Else, assign NEWQR the value one.
iii. If NEWQR is zero, then we are copying a previously defined setof quant ranges. In that case:
A. If qti > 0, read a 1-bit unsigned integer as RPQR.
B. Else, assign RPQR the value zero.
C. If RPQR is one, assign qtj the value (qti − 1) and assign plj
the value pli . This selects the set of quant ranges definedfor the same color plane as this one, but for the previous
quantization type.
D. Else assign qtj the value (3 ∗ qti + pli − 1)//3 and assign plj
the value (pli + 2)%3. This selects the most recent set ofquant ranges defined.
E. Assign NQRS[qti ][pli ] the value NQRS[qtj ][plj ].
F. Assign QRSIZES[qti ][pli ] the values in QRSIZES[qtj ][plj ].
G. Assign QRBMIS[qti ][pli ] the values in QRBMIS[qtj ][plj ].
iv. Else, NEWQR is one, which indicates that we are defining a new
set of quant ranges. In that case:

54

CHAPTER 6. BITSTREAM HEADERS
A. Assign qri the value zero.
B. Assign qi the value zero.
C. Read an ilog(NBMS − 1)-bit unsigned integer as
QRBMIS[qti ][pli ][qri ]. If this is greater than or equal to
NBMS, stop. The stream is undecodable.
D. Read an ilog(62 − qi )-bit unsigned integer. Assign
QRSIZES[qti ][pli ][qri ] the value read, plus one.
E. Assign qi the value qi + QRSIZES[qti ][pli ][qri ].
F. Assign qri the value qri + 1.
G. Read an ilog(NBMS − 1)-bit unsigned integer as
QRBMIS[qti ][pli ][qri ].
H. If qi is less than 63, go back to step 7(a)ivD.
I. If qi is greater than 63, stop. The stream is undecodable.
J. Assign NQRS[qti ][pli ] the value qri .

VP3 Compatibility
The quantization parameters are hardcoded in VP3. The values used are given
in Appendix B.3.

6.4.3

Computing a Quantization Matrix

Input parameters:

Name

Type

Size
(bits)ACSCALE

Integerarray

DCSCALEBMSNQRSQRSIZES

Signed?

Description and restrictions

16

No

Integer
array

16

No

2D Integer
array
2D Integer
array

8

No

6

No

6

No

A 64-element array of scalevalues for AC coefficients foreach qi value.
A 64-element array of scalevalues for the DC coefficientfor each qi value.
A NBMS × 64 array containing the base matrices.
A 2 × 3 array containing thenumber of quant ranges for agiven qti and pli , respectively.
This is at most 63.
A 2 × 3 × 63 array of thesizes of each quant range for agiven qti and pli , respectively.
Only the first NQRS[qti ][pli ]values are used.

3D Integerarray6.4. SETUP HEADER

55

Name

Type

Size
(bits)

Signed?

Description and restrictions

QRBMIS

3D Integer
array

9

No

Integer

1

No

pli

Integer2

No

qi

Integer6No

A 2 × 3 × 64 array of the
bmi ’s used for each quantrange for a given qti and pli ,respectively. Only the first(NQRS[qti ][pli ] + 1) values
are used.
A quantization type index.
See Table 3.1.
A color plane index. See Table 2.1.
The quantization index.

qti

Output parameters:

Name

Type

Size
(bits)

QMAT

Integerarray

16

Signed?

Description and restrictions

No

A 64-element array of quantization
values for each DCT coefficient innatural order.

Variables used:

Name

Type

Size
(bits)

Signed?

Description and restrictions

ci
bmi
bmj
qri
QISTART
QIEND

Integer
Integer
Integer
Integer
Integer
Integer

6
9
9
6
6
6

No
No
No
No
No
No

8

No

16

No

16

No

The DCT coefficient index.
The base matrix index.
The base matrix index.
The quant range index.
The left end-point of the qi range.
The right end-point of the qi
range.
A 64-element array containing theinterpolated base matrix.
The minimum quantization value
allowed for the current coefficient.
The current scale value.

BM
QMIN

Integerarray
IntegerQSCALE

Integer

56

CHAPTER 6. BITSTREAM HEADERS

The following procedure can be used to generate a single quantization matrix
for a given quantization type, color plane, and qi value, given the quantization
parameters decoded in Section 6.4.2.
Note that the product of the scale value and the base matrix value is in unitsof 100ths of a pixel value, and thus is divided by 100 to return it to units of asingle pixel value. This value is then scaled by four, to match the scaling of the
DCT output, which is also a factor of four larger than the orthonormal versionof the transform.
1. Assign qri the index of a quant range such that
qi ≥

qri−1
X

QRSIZES[qti ][pli ][qrj ],qrj =0

and

qri
X

qi ≤

QRSIZES[qti ][pli ][qrj ],qrj =0where summation from 0 to −1 is defined to be zero. If there is more than
one such value of qri , i.e., if qi lies on the boundary between two quantranges, then the output will be the same regardless of which one is chosen.
2. Assign QISTART the value
qri−1
X

QRSIZES[qti ][pli ][qrj ].

qrj =03. Assign QIEND the value
qri
X

QRSIZES[qti ][pli ][qrj ].

qrj =0

4. Assign bmi the value QRBMIS[qti ][pli ][qri ].
5. Assign bmj the value QRBMIS[qti ][pli ][qri + 1].
6. For each consecutive value of ci from 0 to 63, inclusive:(a) Assign BM[ci ] the value(2 ∗ (QIEND − qi ) ∗ BMS[bmi ][ci ]+ 2 ∗ (qi − QISTART) ∗ BMS[bmj ][ci ]+ QRSIZES[qti ][pli ][qri ])//(2 ∗ QRSIZES[qti ][pli ][qri ])(b) Assign QMIN the value given by Table 6.18 according to qti and ci .
(c) If ci equals zero, assign QSCALE the value DCSCALE[qi ].
(d) Else, assign QSCALE the value ACSCALE[qi ].
(e) Assign QMAT[ci ] the valuemax(QMIN, min((QSCALE ∗ BM[ci ]//100) ∗ 4, 4096)).

6.4. SETUP HEADER

57
Coefficient

qti

QMIN

ci = 0ci > 0ci = 0ci > 00 (Intra)0 (Intra)1 (Inter)
1 (Inter)

16
8
32
16

Table 6.18: Minimum Quantization Values

6.4.4

DCT Token Huffman Tables

Input parameters:
None.
Output parameters:

Name

Type

Size
(bits)

Signed?

HTS

Huffman table array

Description and restrictions
An 80-element array of Huffman tables
with up to 32 entries each.

Variables used:

Name

Type

HBITS
TOKEN
ISLEAF

Bit string
Integer
IntegerSize(bits)
32
51

Signed?

Description and restrictions

No
No
No

A string of up to 32 bits.
A single DCT token value.
Flag that indicates if the current
node of the tree being decoded isa leaf node.

The Huffman tables used to decode DCT tokens are stored in the setup
header in the form of a binary tree. This enforces the requirements that thecode be full—so that any sequence of bits will produce a valid sequence of
tokens—and that the code be prefix-free so that there is no ambiguity when
decoding.
One more restriction is placed on the tables that is not explicitly enforced by
the bitstream syntax, but nevertheless must be obeyed by compliant encoders.
There must be no more than 32 entries in a single table. Note that this restriction along with the fullness requirement limit the maximum size of a single
Huffman code to 32 bits. It is probably a good idea to enforce this latter consequence explicitly when implementing the decoding procedure as a recursivealgorithm, so as to prevent a possible stack overflow given an invalid bitstream.
Although there are 32 different DCT tokens, and thus a normal table will
have exactly 32 entries, this is not explicitly required. It is allowable to use a
Huffman code that omits some—but not all—of the possible token values. It isalso allowable, if not particularly useful, to specify multiple codes for the same

58

CHAPTER 6. BITSTREAM HEADERS

token value in a single table. Note also that token values may appear in thetree in any order. In particular, it is not safe to assume that token value zero(which ends a single block), has a Huffman code of all zeros.
The tree is decoded as follows:
1. For each consecutive value of hti from 0 to 79, inclusive:(a) Set HBITS to the empty string.
(b) If HBITS is longer than 32 bits in length, stop. The stream is undecodable.
(c) Read a 1-bit unsigned integer as ISLEAF.
(d) If ISLEAF is one:i. If the number of entries in table HTS[hti ] is already 32, stop.
The stream is undecodable.
ii. Read a 5-bit unsigned integer as TOKEN.
iii. Add the pair (HBITS, TOKEN) to Huffman table HTS[hti ].
(e) Otherwise:i. Add a ‘0’ to the end of HBITS.
ii. Decode the ‘0’ sub-tree using this procedure, starting from step 1b.
iii. Remove the ‘0’ from the end of HBITS and add a ‘1’ to the endof HBITS.
iv. Decode the ‘1’ sub-tree using this procedure, starting from step 1b.
v. Remove the ‘1’ from the end of HBITS.
VP3 Compatibility
The DCT token Huffman tables are hardcoded in VP3. The values used are
given in Appendix B.4.

6.4.5

Setup Header Decode

Input parameters:
None.
Output parameters:

Name

Type

Size
(bits)

LFLIMS

Integerarray

7

Signed?

Description and restrictions

No

A 64-element array of loop filter limit values.

6.4. SETUP HEADER
Name

59

Type

Size
(bits)

Signed?

Description and restrictions

ACSCALE

Integer
array

16

No

Integer
array

16

No

Integer
2D Integer
array
2D Integer
array

10
8

No
No

6

No

QRSIZES

3D Integer
array

6

No

QRBMIS

3D Integer
array

9

No

HTS

Huffman table array

A 64-element array of scalevalues for AC coefficients foreach qi value.
A 64-element array of scalevalues for the DC coefficientfor each qi value.
The number of base matrices.
A NBMS × 64 array containing the base matrices.
A 2 × 3 array containing thenumber of quant ranges for agiven qti and pli , respectively.
This is at most 63.
A 2 × 3 × 63 array of thesizes of each quant range for agiven qti and pli , respectively.
Only the first NQRS[qti ][pli ]values will be used.
A 2 × 3 × 64 array of the
bmi ’s used for each quantrange for a given qti and pli ,respectively. Only the first(NQRS[qti ][pli ] + 1) values
will be used.
An 80-element array of Huffman tables with up to 32 entries each.

DCSCALE

NBMS
BMS
NQRS

Variables used:None.
The complete setup header is decoded as follows:
1. Decode the common header fields according to the procedure described in
Section 6.1. If HEADERTYPE returned by this procedure is not 0x82,
then stop. This packet is not the setup header.
2. Decode the loop filter limit value table using the procedure given in Section 6.4.1 into LFLIMS.
3. Decode the quantization parameters using the procedure given in Section 6.4.2. The results are stored in ACSCALE, DCSCALE, NBMS,BMS, NQRS, QRSIZES, and QRBMIS.

60

CHAPTER 6. BITSTREAM HEADERS
4. Decode the DCT token Huffman tables using the procedure given in Section 6.4.4 into HTS.

Chapter 7

Frame DecodeThis section describes the complete procedure necessary to decode a single
frame. This begins with the frame header, followed by coded block flags, macro
block modes, motion vectors, block-level qi values, and finally the DCT residual
tokens, which are used to reconstruct the frame.

7.1

Frame Header Decode

Input parameters:
None.
Output parameters:

Name

Type

Size
(bits)

FTYPE
NQIS
QIS

Integer
Integer
Integer
array

1
2
6

Signed?

Description and restrictions

No
No
No

The frame type.
The number of qi values.
An NQIS-element array of qi values.

Variables used:

61

62

CHAPTER 7. FRAME DECODE
Name

Type

Size
(bits)MOREQIS

Integer1

Signed?

Description and restrictions

No

A flag indicating there are more qi
values to be decoded.

The frame header selects which type of frame is being decoded, intra or inter,and contains the list of qi values that will be used in this frame. The first qi
value will be used for all DC coefficients in all blocks. This is done to ensurethat DC prediction, which is done in the quantized domain, works as expected.
The AC coefficients, however, can be dequantized using any qi value on the list,
selected on a block-by-block basis.
1. Read a 1-bit unsigned integer. If the value read is not zero, stop. This is
not a data packet.
2. Read a 1-bit unsigned integer as FTYPE. This is the type of frame being
decoded, as given in Table 7.3. If this is the first frame being decoded,
this MUST be zero.
FTYPE

Frame Type01

Intra frame
Inter frame

Table 7.3: Frame Type Values
3. Read in a 6-bit unsigned integer as QIS[0].
4. Read a 1-bit unsigned integer as MOREQIS.
5. If MOREQIS is zero, set NQIS to 1.
6. Otherwise:(a) Read in a 6-bit unsigned integer as QIS[1].
(b) Read a 1-bit unsigned integer as MOREQIS.
(c) If MOREQIS is zero, set NQIS to 2.
(d) Otherwise:i. Read in a 6-bit unsigned integer as QIS[2].
ii. Set NQIS to 3.
7. If FTYPE is 0, read a 3-bit unsigned integer. These bits are reserved. If
this value is not zero, stop. This frame is not decodable according to thisspecification.

7.2. RUN-LENGTH ENCODED BIT STRINGS

63

VP3 Compatibility
The precise format of the frame header is substantially different in Theora thanin VP3. The original VP3 format includes a larger number of unused, reserved
bits that are required to be zero. The original VP3 frame header also can contain
only a single qi value, because VP3 does not support block-level qi values anduses the same qi value for all the coefficients in a frame.

7.2

Run-Length Encoded Bit Strings

Two variations of run-length encoding are used to store sequences of bits forthe block coded flags and the block-level qi values. The procedures to decodethese bit sequences are specified in the following two sections.

7.2.1

Long-Run Bit String Decode

Input parameters:

Name

Type

Size
(bits)

Signed?

NBITS

Integer

36

No

Size
(bits)

Signed?

Description and restrictions
The number of bits to decode.

Output parameters:

Name

Type

BITS

Bit string

Description and restrictions
The decoded bits.

Variables used:

Name

Type

Size
(bits)

Signed?

Description and restrictions

LEN
BIT

Integer
Integer

36
1

No
No

13

No

The number of bits decoded so far.
The value associated with the current
run.
The length of the current run.

RLEN

Integer

64

CHAPTER 7. FRAME DECODE
Name

Type

Size
(bits)

Signed?

Description and restrictions

RBITS

Integer

4No

Integer

6No

Integer

12No

The number of extra bits needed to
decode the run length.
The start of the possible run-length
values for a given Huffman code.
The offset from RSTART of the runlength.

RSTART
ROFFS

There is no practical limit to the number of consecutive 0’s and 1’s thatcan be decoded with this procedure. In reality, the run length is limited by
the number of blocks in a single frame, because more will never be requested.
A separate procedure described in Section 7.2.2 is used when there is a known
limit on the maximum size of the runs.
For the first run, a single bit value is read, and then a Huffman-coded representation of a run length is decoded, and that many copies of the bit value
are appended to the bit string. For each consecutive run, the value of the bit istoggled instead of being read from the bitstream.
The only exception is if the length of the previous run was 4129, the maximum possible length encodable by the Huffman-coded representation. In thiscase another bit value is read from the stream, to allow for consecutive runs of
0’s or 1’s longer than this maximum.
Note that in both cases—for the first run and after a run of length 4129—if
no more bits are needed, then no bit value is read.
The complete decoding procedure is as follows:
1. Assign LEN the value 0.
2. Assign BITS the empty string.
3. If LEN equals NBITS, return the completely decoded string BITS.
4. Read a 1-bit unsigned integer as BIT.
5. Read a bit at a time until one of the Huffman codes given in Table 7.7 isrecognized.
6. Assign RSTART and RBITS the values given in Table 7.7 according to
the Huffman code read.
7. Read an RBITS-bit unsigned integer as ROFFS.
8. Assign RLEN the value (RSTART + ROFFS).
9. Append RLEN copies of BIT to BITS.
10. Add RLEN to the value LEN. LEN MUST be less than or equal to
NBITS.

7.2. RUN-LENGTH ENCODED BIT STRINGS
Huffman CodeRSTART

RBITS

1
2
4
6
10
18
34

0
1
1
2
3
4
12

b0
b10
b110
b1110
b11110b111110b11111165
Run Lengths
1
2...3
4...5
6...9
10 . . . 17
18 . . . 33
34 . . . 4129

Table 7.7: Huffman Codes for Long Run Lengths
11. If LEN equals NBITS, return the completely decoded string BITS.
12. If RLEN equals 4129, read a 1-bit unsigned integer as BIT.
13. Otherwise, assign BIT the value (1 − BIT).
14. Continue decoding runs from step 5.
VP3 Compatibility
VP3 does not read a new bit value after decoding a run length of 4129. This
limits the maximum number of consecutive 0’s or 1’s to 4129 in VP3-compatible
streams. For reasonable video sizes of 1920 × 1080 or less in 4:2:0 format—the
only pixel format VP3 supports—this does not pose any problems because runs
longer than 4129 are not needed.

7.2.2

Short-Run Bit String Decode

Input parameters:

Name

Type

Size
(bits)

Signed?

NBITS

Integer

36

No

Size
(bits)

Signed?

Description and restrictions
The number of bits to decode.

Output parameters:

Name

Type

BITS

Bit string

Description and restrictions
The decoded bits.

Variables used:

Name

Type

Size
(bits)

Signed?

Description and restrictions

66

CHAPTER 7. FRAME DECODE
Name

Type

Size
(bits)

Signed?

Description and restrictions

RLEN
RBITS

Integer
Integer

13
4

No
No

Integer

6No

Integer

12No

The length of the current run.
The number of extra bits needed to
decode the run length.
The start of the possible run-length
values for a given Huffman code.
The offset from RSTART of the runlength.

RSTART
ROFFS

This procedure is similar to the procedure outlined in Section 7.2.1, exceptthat the maximum number of consecutive 0’s or 1’s is limited to 30. This is the
maximum run length needed when encoding a bit for each of the 16 blocks in asuper block when it is known that not all the bits in a super block are the same.
The complete decoding procedure is as follows:
1. Assign LEN the value 0.
2. Assign BITS the empty string.
3. If LEN equals NBITS, return the completely decoded string BITS.
4. Read a 1-bit unsigned integer as BIT.
5. Read a bit at a time until one of the Huffman codes given in Table 7.11
is recognized.
Huffman Code
b0
b10
b110
b1110
b11110b11111RSTART

RBITS

1
3
5
7
11
15

1
1
1
2
2
4

Run Lengths
1...2
3...4
5...6
7 . . . 10
11 . . . 14
15 . . . 30

Table 7.11: Huffman Codes for Short Run Lengths
6. Assign RSTART and RBITS the values given in Table 7.11 according to
the Huffman code read.
7. Read an RBITS-bit unsigned integer as ROFFS.
8. Assign RLEN the value (RSTART + ROFFS).
9. Append RLEN copies of BIT to BITS.

7.3. CODED BLOCK FLAGS DECODE

67

10. Add RLEN to the value LEN. LEN MUST be less than or equal to
NBITS.
11. If LEN equals NBITS, return the completely decoded string BITS.
12. Assign BIT the value (1 − BIT).
13. Continue decoding runs from step 5.

7.3

Coded Block Flags Decode

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

FTYPE
NSBS

Integer
Integer

1
32

No
No

36

No

The frame type.
The total number of super blocks in aframe.
The total number of blocks in a frame.

NBS

Integer

Output parameters:

Name

Type

Size
(bits)BCODED

IntegerArray

1

Signed?

Description and restrictionsNo

An NBS-element array of flags
indicating which blocks arecoded.

Variables used:

Name

Type

Size
(bits)

NBITS

Integer36

BITS

Bit string

Signed?

Description and restrictions

No

The length of a bit string to decode.
A decoded set of flags.

68

CHAPTER 7. FRAME DECODE
Name

Type

Size
(bits)

Signed?

Description and restrictions

SBPCODED

Integer
Array

1

No

Integer
Array

1

No

sbi

Integer

32

No

bi

Integer36

No

An NSBS-element array offlags indicating whether or noteach super block is partiallycoded.
An NSBS-element array offlags indicating whether or noteach non-partially coded super
block is fully coded.
The index of the current super
block.
The index of the current blockin coded order.

SBFCODED

This procedure determines which blocks are coded in a given frame. In an
intra frame, it marks all blocks coded. In an inter frame, however, any or all of
the blocks may remain uncoded. The output is a list of bit flags, one for eachblock, marking it coded or not coded.
It is important to note that flags are still decoded for any blocks which lie
entirely outside the picture region, even though they are not displayed. Encoders
MAY choose to code such blocks. Decoders MUST faithfully reconstruct suchblocks, because their contents can be used for predictors in future frames. Flags
are not decoded for portions of a super block which lie outside the full frame,as there are no blocks in those regions.
The complete procedure is as follows:
1. If FTYPE is zero (intra frame):(a) For each consecutive value of bi from 0 to (NBS−1), assign BCODED[bi ]the value one.
2. Otherwise (inter frame):(a) Assign NBITS the value NSBS.
(b) Read an NBITS-bit bit string into BITS, using the procedure described in Section 7.2.1. This represents the list of partially codedsuper blocks.
(c) For each consecutive value of sbi from 0 to (NSBS − 1), remove thebit at the head of the string BITS and assign it to SBPCODED[sbi ].
(d) Assign NBITS the total number of super blocks such that
SBPCODED[sbi ] equals zero.
(e) Read an NBITS-bit bit string into BITS, using the procedure described in Section 7.2.1. This represents the list of fully coded super
blocks.

7.4. MACRO BLOCK CODING MODES

69(f) For each consecutive value of sbi from 0 to (NSBS − 1) such that
SBPCODED[sbi ] equals zero, remove the bit at the head of the string
BITS and assign it to SBFCODED[sbi ].
(g) Assign NBITS the number of blocks contained in super blocks where
SBPCODED[sbi ] equals one. Note that this might not be equal to 16
times the number of partially coded super blocks, since super blocks
which overlap the edge of the frame will have fewer than 16 blocks
in them.
(h) Read an NBITS-bit bit string into BITS, using the procedure described in Section 7.2.2.
(i) For each block in coded order—indexed by bi :i. Assign sbi the index of the super block containing block bi .
ii. If SBPCODED[sbi ] is zero, assign BCODED[bi ] the value SBFCODED[sbi ].
iii. Otherwise, remove the bit at the head of the string BITS andassign it to BCODED[bi ].

7.4

Macro Block Coding Modes

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

FTYPE
NMBS

Integer
Integer

1
32

No
No

Integer

36

No

Integer
Array

1

No

The frame type.
The total number of macro
blocks in a frame.
The total number of blocks in aframe.
An NBS-element array of flags
indicating which blocks arecoded.

NBS
BCODED

Output parameters:

70

CHAPTER 7. FRAME DECODE
Name

Type

Size
(bits)

MBMODES

IntegerArray

3

Signed?

Description and restrictions

No

An NMBS-element array ofcoding modes for each macro
block.

Signed?

Description and restrictions
The mode coding scheme.
The list of modes corresponding to each Huffman code.
The index of the current
macro block.
The index of the current
block in coded order.
The index of a Huffman
code from Table 7.19, starting from 0.

Variables used:

Name

Type

Size
(bits)MSCHEME
MALPHABET

3
3

No
No

mbi

Integer
Integerarray
Integer

32

No

bi

Integer

36

No

mi

Integer

3

No

In an intra frame, every macro block marked as coded in INTRA mode. In
an inter frame, however, a macro block can be coded in one of eight coding
modes, given in Table 7.18. All of the blocks in all color planes contained in amacro block will be assigned the coding mode of that macro block.
Index
0
1
2
3
4
5
6
7

Coding Mode
INTER NOMVINTRA
INTER MV
INTER MV LASTINTER MV LAST2
INTER GOLDEN NOMVINTER GOLDEN MV
INTER MV FOUR

Table 7.18: Macro Block Coding Modes
An important thing to note is that a coding mode is only stored in the
bitstream for a macro block if it has at least one luma block coded. A macro7.4. MACRO BLOCK CODING MODES

71

block that contains coded blocks in the chroma planes, but not in the luma
plane, MUST be coded in INTER NOMV mode. Thus, no coding mode needs
to be decoded for such a macro block.
Coding modes are encoded using one of eight different schemes. Schemes 0
through 6 use the same simple Huffman code to represent the mode numbers, as
given in Table 7.19. The difference in the schemes is the mode number assigned
to each code. Scheme 0 uses an assignment specified in the bitstream, while
schemes 1–6 use a fixed assignment, also given in Table 7.19. Scheme 7 simply
codes each mode directly in the bitstream using three bits.
Scheme1

Huffman Code
b0
b10
b110
b1110
b11110b111110b1111110b1111111

2

3

4

5

6

Coding Mode
3
4
2
0
1
5
6
7

3
4
0
2
1
5
6
7

3
2
4
0
1
5
6
7

3
2
0
4
1
5
6
7

0
3
4
2
1
5
6
7

7
mi

0
5
3
4
2
1
6
7

0
1
2
3
4
5
6
7

Table 7.19: Macro Block Mode Schemes

1. If FTYPE is 0 (intra frame):(a) For each consecutive value of mbi from 0 to (NMBS − 1), inclusive,
assign MBMODES[mbi ] the value 1 (INTRA).
2. Otherwise (inter frame):(a) Read a 3-bit unsigned integer as MSCHEME.
(b) If MSCHEME is 0:
i. For each consecutive value of MODE from 0 to 7, inclusive:
A. Read a 3-bit unsigned integer as mi .
B. Assign MALPHABET[mi ] the value MODE.
(c) Otherwise, if MSCHEME is not 7, assign the entries of MALPHABET
the values in the corresponding column of Table 7.19.
(d) For each consecutive macro block in coded order (cf. Section 2.4)—
indexed by mbi :i. If a block bi in the luma plane of macro block mbi exists suchthat BCODED[bi ] is 1:

72

CHAPTER 7. FRAME DECODE
A. If MSCHEME is not 7, read one bit at a time until one of
the Huffman codes in Table 7.19 is recognized, and assign
MBMODES[mbi ] the value MALPHABET[mi ], where miis the index of the Huffman code decoded.
B. Otherwise, read a 3-bit unsigned integer as MBMODES[mbi ].
ii. Otherwise, if no luma-plane blocks in the macro block are coded,
assign MBMODES[mbi ] the value 0 (INTER NOMV).

7.5

Motion Vectors

In an intra frame, no motion vectors are used, and so motion vector decoding isskipped. In an inter frame, however, many of the inter coding modes require a
motion vector in order to specify an offset into the reference frame from which topredict a block. These procedures assigns such a motion vector to every block.

7.5.1

Motion Vector Decode

Input parameters:

Name

Type

Size
(bits)

Signed?

MVMODE

Integer

1

No

Description and restrictions
The motion
method.

vectordecoding

Output parameters:

Name

Type

Size
(bits)MVX
MVY

Integer
Integer

6
6

Variables used:

Signed?

Description and restrictions

Yes
Yes

The X component of the motion vector.
The Y component of the motion vector.

7.5. MOTION VECTORS

73

Name

Type

Size
(bits)MVSIGN

Integer1

Signed?

Description and restrictions

No

The sign of the motion vector component just decoded.

The individual components of a motion vector can be coded using one of two
methods. The first uses a variable length Huffman code, given in Table 7.23.
The second encodes the magnitude of the component directly in 5 bits, and thesign in one bit. Note that in this case there are two representations for the value
zero. For compatibility with VP3, a sign bit is read even if the magnitude readis zero. One scheme is chosen and used for the entire frame.
Each component can take on integer values from −31 . . . 31, inclusive, at
half-pixel resolution, i.e. −15.5 . . . 15.5 pixels in the luma plane. For each subsampled axis in the chroma planes, the corresponding motion vector component
is interpreted as being at quarter-pixel resolution, i.e. −7.75 . . . 7.75 pixels. The
precise details of how these vectors are used to compute predictors for eachblock are described in Section 7.9.1.
A single motion vector is decoded is follows:
1. If MVMODE is 0:(a) Read 1 bit at a time until one of the Huffman codes in Table 7.23 isrecognized, and assign the value to MVX.
(b) Read 1 bit at a time until one of the Huffman codes in Table 7.23 isrecognized, and assign the value to MVY.
2. Otherwise:(a) Read a 5-bit unsigned integer as MVX.
(b) Read a 1-bit unsigned integer as MVSIGN.
(c) If MVSIGN is 1, assign MVX the value −MVX.
(d) Read a 5-bit unsigned integer as MVY.
(e) Read a 1-bit unsigned integer as MVSIGN.
(f) If MVSIGN is 1, assign MVY the value −MVY.

7.5.2

Macro Block Motion Vector Decode

Input parameters:

74

CHAPTER 7. FRAME DECODE
Name

Type

Size
(bits)

Signed?

Description and restrictions

PF
NMBS

Integer
Integer

2
32

No
No

Integer
Array

3

No

NBS

Integer

36

No

BCODED

Integer
Array

1

No

The pixel format.
The total number of macro
blocks in a frame.
An NMBS-element array ofcoding modes for each macro
block.
The total number of blocks ina frame.
An NBS-element array offlags indicating which blocks
are coded.

MBMODES

Output parameters:

Name

Type

Size
(bits)MVECTSArrayof
2D Integer
Vectors

Signed?

Description and restrictionsYes

An NBS-element array of motion vectors for each block.

6

Variables used:

Name

Type

LAST1

MVX

2D Integer
Vector
2D Integer
VectorIntegerMVY

Size(bits)

Signed?

Description and restrictions

6

Yes

The last motion vector.

6

Yes

The second to last motion vector.

6

Yes

Integer

6

Yes

mbi

Integer

32

No

A

Integer

36

No

The X component of a motion vector.
The Y component of a motion vector.
The index of the current macro
block.
The index of the lower-left luma
block in the macro block.

LAST2

7.5. MOTION VECTORS
Name

75

Type

Size
(bits)

Signed?

Description and restrictions

B

Integer

36

No

Integer

36

No

D

Integer

36

No

E

Integer

36

No

F

Integer

36

No

G

Integer

36

No

H

Integer

36

No

I

Integer

36

No

J

Integer

36

No

K

Integer

36

No

L

Integer

36

No

The index of the lower-right luma
block in the macro block.
The index of the upper-left luma
block in the macro block.
The index of the upper-right luma
block in the macro block.
The index of a chroma block inthe macro block, depending on the
pixel format.
The index of a chroma block inthe macro block, depending on the
pixel format.
The index of a chroma block inthe macro block, depending on the
pixel format.
The index of a chroma block inthe macro block, depending on the
pixel format.
The index of a chroma block inthe macro block, depending on the
pixel format.
The index of a chroma block inthe macro block, depending on the
pixel format.
The index of a chroma block inthe macro block, depending on the
pixel format.
The index of a chroma block inthe macro block, depending on the
pixel format.

C

Motion vectors are stored for each macro block. In every mode except for
INTER MV FOUR, every block in all the color planes are assigned the same
motion vector. In INTER MV FOUR mode, all four blocks in the luma plane
are assigned their own motion vector, and motion vectors for blocks in thechroma planes are computed from these, using averaging appropriate to the
pixel format.
For INTER MV and INTER GOLDEN MV modes, a single motion vector
is decoded and applied to each block. For INTER MV FOUR macro blocks, amotion vector is decoded for each coded luma block, in raster order, not coded
order. Uncoded luma blocks receive the default (0, 0) vector for the purposes ofcomputing the chroma motion vectors.

76

CHAPTER 7. FRAME DECODE

None of the remaining macro block coding modes require decoding motion
vectors from the stream. INTRA mode does not use a motion-compensatedpredictor, and thus does not require a motion vector. Both the INTER NOMVand the INTER GOLDEN NOMV modes use the default vector (0, 0) for eachblock. This also includes all macro blocks with no coded luma blocks, as they
are coded in INTER NOMV mode by definition.
The modes INTER MV LAST and INTER MV LAST2 use the motion vector from the last macro block (in coded order) and the second to last macro
block, respectively, that contained a motion vector pointing to the previous
frame. Thus no explicit motion vector needs to be decoded for these modes.
Macro blocks coded in INTRA mode or one of the GOLDEN modes are not considered in this process. For macro blocks coded in INTER MV FOUR mode,
this process uses the vector from the last coded luma block in the macro block,again in raster order, not coded order. This is usually the upper-right block. If
an insufficient number of macro blocks have been coded in one of the INTER
modes, then the (0, 0) vector is used instead.
The motion vectors are decoded from the stream as follows:
1. Assign LAST1 and LAST2 both the value (0, 0).
2. Read a 1-bit unsigned integer as MVMODE. Note that this value is readeven if no macro blocks require a motion vector to be decoded.
3. For each consecutive value of mbi from 0 to (NMBS − 1):(a) If MBMODES[mbi ] is 7 (INTER MV FOUR):
i. Let A, B, C, and D be the indices in coded order bi of the luma
blocks in macro block mbi , arranged into raster order. Thus, A
is the index in coded order of the block in the lower left, B thelower right, C the upper left, and D the upper right.
ii. If BCODED[A] is non-zero:
A. Decode a single motion vector into MVX and MVY using
the procedure described in Section 7.5.1.
B. Assign MVECTS[A] the value (MVX, MVY).
iii. Otherwise, assign MVECTS[A] the value (0, 0).
iv. If BCODED[B] is non-zero:
A. Decode a single motion vector into MVX and MVY using
the procedure described in Section 7.5.1.
B. Assign MVECTS[B] the value (MVX, MVY).
v. Otherwise assign MVECTS[B] the value (0, 0).
vi. If BCODED[C] is non-zero:
A. Decode a single motion vector into MVX and MVY using
the procedure described in Section 7.5.1.
B. Assign MVECTS[C] the value (MVX, MVY).
vii. Otherwise assign MVECTS[C] the value (0, 0).

7.5. MOTION VECTORS

77

viii. If BCODED[D] is non-zero:
A. Decode a single motion vector into MVX and MVY using
the procedure described in Section 7.5.1.
B. Assign MVECTS[D] the value (MVX, MVY).
ix. Otherwise, assign MVECTS[D] the value (0, 0).
x. If PF is 0 (4:2:0):
A. Let E and F be the index in coded order of the one block inthe macro block from the Cb and Cr planes, respectively.
B. Assign MVECTS[E] and MVECTS[F] the value
MVECTS[A]x + MVECTS[B]x +(round
MVECTS[C]x + MVECTS[D]x,
4
MVECTS[A]y + MVECTS[B]y +

round


MVECTS[C]y + MVECTS[D]y)4xi. If PF is 2 (4:2:2):
A. Let E and F be the indices in coded order of the bottom andtop blocks in the macro block from the Cb plane, respectively,
and G and H be the indices in coded order of the bottom andtop blocks in the Cr plane, respectively.
B. Assign MVECTS[E] and MVECTS[G] the value(round
MVECTS[A]x + MVECTS[B]x,2MVECTS[A]y + MVECTS[B]y
)
round
2

C. Assign MVECTS[F] and MVECTS[H] the value(round
MVECTS[C]x + MVECTS[D]x,2MVECTS[C]y + MVECTS[D]y
round
)
2

xii. If PF is 3 (4:4:4):
A. Let E, F, G, and H be the indices bi in coded order of the Cb
plane blocks in macro block mbi , arranged into raster order,and I, J, K, and L be the indices bi in coded order of the Crplane blocks in macro block mbi , arranged into raster order.
B. Assign MVECTS[E] and MVECTS[I] the value
MVECTS[A].

78

CHAPTER 7. FRAME DECODE
C. Assign MVECTS[F] and MVECTS[J] the value
MVECTS[B].
D. Assign MVECTS[G] and MVECTS[K] the value
MVECTS[C].
E. Assign MVECTS[H] and MVECTS[L] the value
MVECTS[D].
xiii. Assign LAST2 the value LAST1.
xiv. Assign LAST1 the value (MVX, MVY). This is the value of the
motion vector decoded from the last coded luma block in rasterorder. There must always be at least one, since macro blocks
with no coded luma blocks must use mode 0: INTER NOMV.
(b) Otherwise, if MBMODES[mbi ] is 6 (INTER GOLDEN MV), decode a single motion vector into MVX and MVY using the proceduredescribed in Section 7.5.1.
(c) Otherwise, if MBMODES[mbi ] is 4 (INTER MV LAST2):
i. Assign (MVX, MVY) the value LAST2.
ii. Assign LAST2 the value LAST1.
iii. Assign LAST1 the value (MVX, MVY).
(d) Otherwise, if MBMODES[mbi ] is 3 (INTER MV LAST), assign(MVX, MVY) the value LAST1.
(e) Otherwise, if MBMODES[mbi ] is 2 (INTER MV):
i. Decode a single motion vector into MVX and MVY using theprocedure described in Section 7.5.1.
ii. Assign LAST2 the value LAST1.
iii. Assign LAST1 the value (MVX, MVY).
(f) Otherwise (MBMODES[mbi ] is 5: INTER GOLDEN NOMV, 1: INTRA, or 0: INTER NOMV), assign MVX and MVY the value zero.
(g) If MBMODES[mbi ] is not 7 (not INTER MV FOUR), then for each
coded block bi in macro block mbi :i. Assign MVECTS[bi ] the value (MVX, MVY).

VP3 Compatibility
Unless all four luma blocks in the macro block are coded, the VP3 encoder does
not select mode INTER MV FOUR. Theora removes this restriction by treating
the motion vector for an uncoded luma block as the default (0, 0) vector. Thisis consistent with the premise that the block has not changed since the previous
frame and that chroma information can be largely ignored when estimating
motion.
No modification is required for INTER MV FOUR macro blocks in VP3
streams to be decoded correctly by a Theora decoder. However, regardless of
how many of the luma blocks are actually coded, the VP3 decoder always reads

7.6. BLOCK-LEVEL QI DECODE

79

four motion vectors from the stream for INTER MV FOUR mode. The motion
vectors read are used to calculate the motion vectors for the chroma blocks, but
are otherwise ignored. Thus, care should be taken when creating Theora streams
meant to be backwards compatible with VP3 to only use INTER MV FOUR
mode when all four luma blocks are coded.

7.6

Block-Level qi Decode

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

NBS

Integer

36

No

Integer
Array

1

No

Integer2

No

The total number of blocks in aframe.
An NBS-element array of flags
indicating which blocks arecoded.
The number of qi values.

BCODED

NQIS

Output parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

QIIS

Integer
Array

2

No

An NBS-element array of qii values
for each block.

Signed?

Description and restrictions

36

No

36

No

The length of a bit string to decode.
A decoded set of flags.
The index of the current block incoded order.

Variables used:

Name

Type

NBITS
BITS
bi

Integer
Bit string
IntegerSize(bits)

80

CHAPTER 7. FRAME DECODE

Name
qii

Type

Size
(bits)

Integer2

Signed?

Description and restrictions

No

The index of qi value in the list of qi
values defined for this frame.

This procedure selects the qi value to be used for dequantizing the AC
coefficients of each block. DC coefficients all use the same qi value, so as to avoid
interference with the DC prediction mechanism, which occurs in the quantizeddomain.
The value is actually represented by an index qii into the list of qi values
defined for the frame. The decoder makes multiple passes through the list ofcoded blocks, one for each qi value except the last one. In each pass, an RLEcoded bitmask is decoded to divide the blocks into two groups: those that use
the current qi value in the list, and those that use a value from later in the list.
Each subsequent pass is restricted to the blocks in the second group.
1. For each value of bi from 0 to (NBS − 1), assign QIIS[bi ] the value zero.
2. For each consecutive value of qii from 0 to (NQIS − 2):(a) Assign NBITS be the number of blocks bi such that BCODED[bi ]is non-zero and QIIS[bi ] equals qii .
(b) Read an NBITS-bit bit string into BITS, using the procedure described in Section 7.2.1. This represents the list of blocks that use qi
value qii or higher.
(c) For each consecutive value of bi from 0 to (NBS − 1) such that
BCODED[bi ] is non-zero and QIIS[bi ] equals qii :i. Remove the bit at the head of the string BITS and add its value
to QIIS[bi ].
VP3 Compatibility
For VP3 compatible streams, only one qi value can be specified in the frame
header, so the main loop of the above procedure, which would iterate from 0 to
−1, is never executed. Thus, no bits are read, and each block uses the one qi
value defined for the frame.

7.6. BLOCK-LEVEL QI DECODE

Huffman Code
b000
b001
b0110
b1000
b101000
b101010b101100
b101110b1100000
b1100010
b1100100b1100110b1101000
b1101010
b1101100b1101110b11100000
b11100010
b11100100
b11100110
b11101000
b11101010
b11101100
b11101110
b11110000
b11110010
b11110100
b11110110
b11111000
b11111010
b11111100
b11111110

Value
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

81

Huffman Code

Value

b010
b0111
b1001
b101001b101011b101101
b101111b1100001
b1100011
b1100101b1100111b1101001
b1101011
b1101101b1101111b11100001
b11100011
b11100101
b11100111
b11101001
b11101011
b11101101
b11101111
b11110001
b11110011
b11110101
b11110111
b11111001
b11111011
b11111101
b11111111

−1
−2
−3
−4
−5
−6
−7
−8
−9
−10
−11
−12
−13
−14
−15
−16
−17
−18
−19
−20
−21
−22
−23
−24
−25
−26
−27
−28
−29
−30
−31

Table 7.23: Huffman Codes for Motion Vector Components

82

CHAPTER 7. FRAME DECODE

7.7. DCT COEFFICIENTS

7.7

83

DCT Coefficients

The quantized DCT coefficients are decoded by making 64 passes through thelist of coded blocks, one for each token index in zig-zag order. For the DC
tokens, two Huffman tables are chosen from among the first 16, one for the luma
plane and one for the chroma planes. The AC tokens, however, are divided into
four different groups. Again, two 4-bit indices are decoded, one for the luma
plane, and one for the chroma planes, but these select the codebooks for all fourgroups. AC coefficients in group one use codebooks 16 . . . 31, while group two
uses 32 . . . 47, etc. Note that this second set of indices is decoded even if there
are no non-zero AC coefficients in the frame.
Tokens are divided into two major types: EOB tokens, which fill the remainder of one or more blocks with zeros, and coefficient tokens, which fill in
one or more coefficients within a single block. A decoding procedure for the
first is given in Section 7.7.1, and for the second in Section 7.7.2. The decoding
procedure for the complete set of quantized coefficients is given in Section 7.7.3.

7.7.1

EOB Token Decode

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

TOKEN

Integer

5NoInteger

36

No

TIS

Integer
Array

7

No

NCOEFFS

Integer
Array

7

No

COEFFS

2D Integer
Array

16

Yes

bi

Integer

36

No

ti

Integer

6No

The token being decoded.
This must be in the range
0 . . . 6.
The total number of blocks ina frame.
An NBS-element array of thecurrent token index for eachblock.
An NBS-element array ofthe coefficient count for eachblock.
An NBS × 64 array of quantized DCT coefficient values
for each block in zig-zag order.
The index of the current blockin coded order.
The current token index.

NBS

84

CHAPTER 7. FRAME DECODE

Output parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

TIS

Integer
Array

7

No

2D Integer
Array

16

Yes

Integer

36

No

An NBS-element array of thecurrent token index for eachblock.
An NBS×64 array of quantized
DCT coefficient values for eachblock in zig-zag order.
The remaining length of thecurrent EOB run.

COEFFS

EOBS

Variables used:

Name

Type

Size
(bits)

bj
tj

Integer
Integer366Signed?

Description and restrictions

No
No

Another index of a block in coded order.
Another token index.

A summary of the EOB tokens is given in Table 7.33. An important thing
to note is that token 6 does not add an offset to the decoded run value, eventhough in general it should only be used for runs of size 32 or longer. If avalue of zero is decoded for this run, it is treated as an EOB run the size of theremaining coded blocks.
Token Value

Extra Bits

0
1
2
3
4
5
6

0
0
0
2
3
4
12

EOB Run Lengths
1
2
3
4...7
8 . . . 15
16 . . . 31
1 . . . 4095, or all remaining blocks

Table 7.33: EOB Token Summary

7.7. DCT COEFFICIENTS

85

There is no restriction that one EOB token cannot be immediately followedby another, so no special cases are necessary to extend the range of the maximum
run length as were required in Section 7.2.1. Indeed, depending on the lengthsof the Huffman codes, it may even cheaper to encode, by way of example, an
EOB run of length 31 followed by an EOB run of length 1 than to encode an
EOB run of length 32 directly. There is also no restriction that an EOB runstop at the end of a color plane or a token index. The run MUST, however, end
at or before the end of the frame.
1. If TOKEN is 0, assign EOBS the value 1.
2. Otherwise, if TOKEN is 1, assign EOBS the value 2.
3. Otherwise, if TOKEN is 2, assign EOBS the value 3.
4. Otherwise, if TOKEN is 3:(a) Read a 2-bit unsigned integer as EOBS.
(b) Assign EOBS the value (EOBS + 4).
5. Otherwise, if TOKEN is 4:(a) Read a 3-bit unsigned integer as EOBS.
(b) Assign EOBS the value (EOBS + 8).
6. Otherwise, if TOKEN is 5:(a) Read a 4-bit unsigned integer as EOBS.
(b) Assign EOBS the value (EOBS + 16).
7. Otherwise, TOKEN is 6:(a) Read a 12-bit unsigned integer as EOBS.
(b) If EOBS is zero, assign EOBS to be the number of coded blocks bj
such that TIS[bj ] is less than 64.
8. For each value of tj from ti to 63, assign COEFFS[bi ][tj ] the value zero.
9. Assign NCOEFFS[bi ] the value TIS[bi ].
10. Assign TIS[bi ] the value 64.
11. Assign EOBS the value (EOBS − 1).
VP3 Compatibility
The VP3 encoder does not use the special interpretation of a zero-length EOBrun, though its decoder does support it. That may be due more to a happy accident in the way the decoder was written than intentional design, however, andother VP3 implementations might not reproduce it faithfully. For backwards
compatibility, it may be wise to avoid it, especially as for most frame sizes there
are fewer than 4095 blocks, making it unnecessary.

86

CHAPTER 7. FRAME DECODE

7.7.2

Coefficient Token Decode

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

TOKEN

Integer

5NoInteger

36

No

TIS

Integer
Array

7

No

COEFFS

2D Integer
Array

16

Yes

bi

Integer

36

No

ti

Integer

6No

The token being decoded. This
must be in the range 7 . . . 31.
The total number of blocks in aframe.
An NBS-element array of thecurrent token index for eachblock.
An NBS×64 array of quantized
DCT coefficient values for eachblock in zig-zag order.
The index of the current blockin coded order.
The current token index.

NBS

Output parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

TIS

Integer
Array

7

No

Integer
Array

7

No

2D Integer
Array

16

Yes

An NBS-element array of thecurrent token index for eachblock.
An NBS-element array ofthe coefficient count for eachblock.
An NBS × 64 array of quantized DCT coefficient values
for each block in zig-zag order.

NCOEFFS

COEFFS

Variables used:

7.7. DCT COEFFICIENTS
Name

Type

Size
(bits)

SIGN

Integer

MAG
RLEN
tj

87
Signed?

Description and restrictions

1

No

Integer

10NoInteger
Integer

6
6

No
No

A flag indicating the sign of the current
coefficient.
The magnitude of the current coefficient.
The length of the current zero run.
Another token index.

Each of these tokens decodes one or more coefficients in the current block. A
summary of the meanings of the token values is presented in Table 7.38. There
are often several different ways to tokenize a given coefficient list. Which one is
optimal depends on the exact lengths of the Huffman codes used to represent
each token. Note that we do not update the coefficient count for the block if we
decode a pure zero run.
For tokens which represent more than one coefficient, they MUST NOT bring
the total number of coefficients in the block to more than 64. Care should betaken in a decoder to check for this, as otherwise it may permit buffer overflows
from invalidly formed packets.
Note: One way to achieve this efficiently is to combine the inverse
zig-zag mapping (described later in Section 7.9.2) with coefficient
decode, and use a table look-up to map zig-zag indices greaterthan 63 to a safe location.
1. If TOKEN is 7:(a) Read in a 3-bit unsigned integer as RLEN.
(b) Assign RLEN the value (RLEN + 1).
(c) For each value of tj from ti to (ti +RLEN−1), assign COEFFS[bi ][tj ]the value zero.
(d) Assign TIS[bi ] the value TIS[bi ] + RLEN.
2. Otherwise, if TOKEN is 8:(a) Read in a 6-bit unsigned integer as RLEN.
(b) Assign RLEN the value (RLEN + 1).
(c) For each value of tj from ti to (ti +RLEN−1), assign COEFFS[bi ][tj ]the value zero.
(d) Assign TIS[bi ] the value TIS[bi ] + RLEN.
3. Otherwise, if TOKEN is 9:(a) Assign COEFFS[bi ][ti ] the value 1.

88

CHAPTER 7. FRAME DECODE

Token Value

Extra Bits

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3
6
0
0
0
0
1
1
1
1
2
3
4
5
6
10
1
1
1
1
1
3
4
2
3

Number of
Coefficients

Description

1...8
1 . . . 64
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
3
4
5
6
7 . . . 10
11 . . . 18
2
3...4

Short zero run.
Zero run.
1.
−1.
2.
−2.
±3.
±4.
±5.
±6.
±7 . . . 8.
±9 . . . 12.
±13 . . . 20.
±21 . . . 36.
±37 . . . 68.
±69 . . . 580.
One zero followed by ±1.
Two zeros followed by ±1.
Three zeros followed by ±1.
Four zeros followed by ±1.
Five zeros followed by ±1.
6 . . . 9 zeros followed by ±1.
10 . . . 17 zeros followed by ±1.
One zero followed by ±2 . . . 3.
2 . . . 3 zeros followed by ±2 . . . 3.

Table 7.38: Coefficient Token Summary

7.7. DCT COEFFICIENTS(b) Assign TIS[bi ] the value TIS[bi ] + 1.
(c) Assign NCOEFFS[bi ] the value TIS[bi ].
4. Otherwise, if TOKEN is 10:(a) Assign COEFFS[bi ][ti ] the value −1.
(b) Assign TIS[bi ] the value TIS[bi ] + 1.
(c) Assign NCOEFFS[bi ] the value TIS[bi ].
5. Otherwise, if TOKEN is 11:(a) Assign COEFFS[bi ][ti ] the value 2.
(b) Assign TIS[bi ] the value TIS[bi ] + 1.
(c) Assign NCOEFFS[bi ] the value TIS[bi ].
6. Otherwise, if TOKEN is 12:(a) Assign COEFFS[bi ][ti ] the value −2.
(b) Assign TIS[bi ] the value TIS[bi ] + 1.
(c) Assign NCOEFFS[bi ] the value TIS[bi ].
7. Otherwise, if TOKEN is 13:(a) Read a 1-bit unsigned integer as SIGN.
(b) If SIGN is zero, assign COEFFS[bi ][ti ] the value 3.
(c) Otherwise, assign COEFFS[bi ][ti ] the value −3.
(d) Assign TIS[bi ] the value TIS[bi ] + 1.
(e) Assign NCOEFFS[bi ] the value TIS[bi ].
8. Otherwise, if TOKEN is 14:(a) Read a 1-bit unsigned integer as SIGN.
(b) If SIGN is zero, assign COEFFS[bi ][ti ] the value 4.
(c) Otherwise, assign COEFFS[bi ][ti ] the value −4.
(d) Assign TIS[bi ] the value TIS[bi ] + 1.
(e) Assign NCOEFFS[bi ] the value TIS[bi ].
9. Otherwise, if TOKEN is 15:(a) Read a 1-bit unsigned integer as SIGN.
(b) If SIGN is zero, assign COEFFS[bi ][ti ] the value 5.
(c) Otherwise, assign COEFFS[bi ][ti ] the value −5.
(d) Assign TIS[bi ] the value TIS[bi ] + 1.
(e) Assign NCOEFFS[bi ] the value TIS[bi ].

89

90

CHAPTER 7. FRAME DECODE

10. Otherwise, if TOKEN is 16:(a) Read a 1-bit unsigned integer as SIGN.
(b) If SIGN is zero, assign COEFFS[bi ][ti ] the value 6.
(c) Otherwise, assign COEFFS[bi ][ti ] the value −6.
(d) Assign TIS[bi ] the value TIS[bi ] + 1.
(e) Assign NCOEFFS[bi ] the value TIS[bi ].
11. Otherwise, if TOKEN is 17:(a) Read a 1-bit unsigned integer as SIGN.
(b) Read a 1-bit unsigned integer as MAG.
(c) Assign MAG the value (MAG + 7).
(d) If SIGN is zero, assign COEFFS[bi ][ti ] the value MAG.
(e) Otherwise, assign COEFFS[bi ][ti ] the value −MAG.
(f) Assign TIS[bi ] the value TIS[bi ] + 1.
(g) Assign NCOEFFS[bi ] the value TIS[bi ].
12. Otherwise, if TOKEN is 18:(a) Read a 1-bit unsigned integer as SIGN.
(b) Read a 2-bit unsigned integer as MAG.
(c) Assign MAG the value (MAG + 9).
(d) If SIGN is zero, assign COEFFS[bi ][ti ] the value MAG.
(e) Otherwise, assign COEFFS[bi ][ti ] the value −MAG.
(f) Assign TIS[bi ] the value TIS[bi ] + 1.
(g) Assign NCOEFFS[bi ] the value TIS[bi ].
13. Otherwise, if TOKEN is 19:(a) Read a 1-bit unsigned integer as SIGN.
(b) Read a 3-bit unsigned integer as MAG.
(c) Assign MAG the value (MAG + 13).
(d) If SIGN is zero, assign COEFFS[bi ][ti ] the value MAG.
(e) Otherwise, assign COEFFS[bi ][ti ] the value −MAG.
(f) Assign TIS[bi ] the value TIS[bi ] + 1.
(g) Assign NCOEFFS[bi ] the value TIS[bi ].
14. Otherwise, if TOKEN is 20:(a) Read a 1-bit unsigned integer as SIGN.
(b) Read a 4-bit unsigned integer as MAG.

7.7. DCT COEFFICIENTS

91(c) Assign MAG the value (MAG + 21).
(d) If SIGN is zero, assign COEFFS[bi ][ti ] the value MAG.
(e) Otherwise, assign COEFFS[bi ][ti ] the value −MAG.
(f) Assign TIS[bi ] the value TIS[bi ] + 1.
(g) Assign NCOEFFS[bi ] the value TIS[bi ].
15. Otherwise, if TOKEN is 21:(a) Read a 1-bit unsigned integer as SIGN.
(b) Read a 5-bit unsigned integer as MAG.
(c) Assign MAG the value (MAG + 37).
(d) If SIGN is zero, assign COEFFS[bi ][ti ] the value MAG.
(e) Otherwise, assign COEFFS[bi ][ti ] the value −MAG.
(f) Assign TIS[bi ] the value TIS[bi ] + 1.
(g) Assign NCOEFFS[bi ] the value TIS[bi ].
16. Otherwise, if TOKEN is 22:(a) Read a 1-bit unsigned integer as SIGN.
(b) Read a 9-bit unsigned integer as MAG.
(c) Assign MAG the value (MAG + 69).
(d) If SIGN is zero, assign COEFFS[bi ][ti ] the value MAG.
(e) Otherwise, assign COEFFS[bi ][ti ] the value −MAG.
(f) Assign TIS[bi ] the value TIS[bi ] + 1.
(g) Assign NCOEFFS[bi ] the value TIS[bi ].
17. Otherwise, if TOKEN is 23:(a) Assign COEFFS[bi ][ti ] the value zero.
(b) Read a 1-bit unsigned integer as SIGN.
(c) If SIGN is zero, assign COEFFS[bi ][ti + 1] the value 1.
(d) Otherwise, assign COEFFS[bi ][ti + 1] the value −1.
(e) Assign TIS[bi ] the value TIS[bi ] + 2.
(f) Assign NCOEFFS[bi ] the value TIS[bi ].
18. Otherwise, if TOKEN is 24:(a) For each value of tj from ti to (ti + 1), assign COEFFS[bi ][tj ] thevalue zero.
(b) Read a 1-bit unsigned integer as SIGN.
(c) If SIGN is zero, assign COEFFS[bi ][ti + 2] the value 1.

92

CHAPTER 7. FRAME DECODE(d) Otherwise, assign COEFFS[bi ][ti + 2] the value −1.
(e) Assign TIS[bi ] the value TIS[bi ] + 3.
(f) Assign NCOEFFS[bi ] the value TIS[bi ].

19. Otherwise, if TOKEN is 25:(a) For each value of tj from ti to (ti + 2), assign COEFFS[bi ][tj ] thevalue zero.
(b) Read a 1-bit unsigned integer as SIGN.
(c) If SIGN is zero, assign COEFFS[bi ][ti + 3] the value 1.
(d) Otherwise, assign COEFFS[bi ][ti + 3] the value −1.
(e) Assign TIS[bi ] the value TIS[bi ] + 4.
(f) Assign NCOEFFS[bi ] the value TIS[bi ].
20. Otherwise, if TOKEN is 26:(a) For each value of tj from ti to (ti + 3), assign COEFFS[bi ][tj ] thevalue zero.
(b) Read a 1-bit unsigned integer as SIGN.
(c) If SIGN is zero, assign COEFFS[bi ][ti + 4] the value 1.
(d) Otherwise, assign COEFFS[bi ][ti + 4] the value −1.
(e) Assign TIS[bi ] the value TIS[bi ] + 5.
(f) Assign NCOEFFS[bi ] the value TIS[bi ].
21. Otherwise, if TOKEN is 27:(a) For each value of tj from ti to (ti + 4), assign COEFFS[bi ][tj ] thevalue zero.
(b) Read a 1-bit unsigned integer as SIGN.
(c) If SIGN is zero, assign COEFFS[bi ][ti + 5] the value 1.
(d) Otherwise, assign COEFFS[bi ][ti + 5] the value −1.
(e) Assign TIS[bi ] the value TIS[bi ] + 6.
(f) Assign NCOEFFS[bi ] the value TIS[bi ].
22. Otherwise, if TOKEN is 28:(a) Read a 1-bit unsigned integer as SIGN.
(b) Read a 2-bit unsigned integer as RLEN.
(c) Assign RLEN the value (RLEN + 6).
(d) For each value of tj from ti to (ti +RLEN−1), assign COEFFS[bi ][tj ]the value zero.
(e) If SIGN is zero, assign COEFFS[bi ][ti + RLEN] the value 1.

7.7. DCT COEFFICIENTS

93(f) Otherwise, assign COEFFS[bi ][ti + RLEN] the value −1.
(g) Assign TIS[bi ] the value TIS[bi ] + RLEN + 1.
(h) Assign NCOEFFS[bi ] the value TIS[bi ].
23. Otherwise, if TOKEN is 29:(a) Read a 1-bit unsigned integer as SIGN.
(b) Read a 3-bit unsigned integer as RLEN.
(c) Assign RLEN the value (RLEN + 10).
(d) For each value of tj from ti to (ti +RLEN−1), assign COEFFS[bi ][tj ]the value zero.
(e) If SIGN is zero, assign COEFFS[bi ][ti + RLEN] the value 1.
(f) Otherwise, assign COEFFS[bi ][ti + RLEN] the value −1.
(g) Assign TIS[bi ] the value TIS[bi ]+RLEN+1. Assign NCOEFFS[bi ]the value TIS[bi ].
24. Otherwise, if TOKEN is 30:(a) Assign COEFFS[bi ][ti ] the value zero.
(b) Read a 1-bit unsigned integer as SIGN.
(c) Read a 1-bit unsigned integer as MAG.
(d) Assign MAG the value (MAG + 2).
(e) If SIGN is zero, assign COEFFS[bi ][ti + 1] the value MAG.
(f) Otherwise, assign COEFFS[bi ][ti + 1] the value −MAG.
(g) Assign TIS[bi ] the value TIS[bi ] + 2. Assign NCOEFFS[bi ] thevalue TIS[bi ].
25. Otherwise, if TOKEN is 31:(a) Read a 1-bit unsigned integer as SIGN.
(b) Read a 1-bit unsigned integer as MAG.
(c) Assign MAG the value (MAG + 2).
(d) Read a 1-bit unsigned integer as RLEN.
(e) Assign RLEN the value (RLEN + 2).
(f) For each value of tj from ti to (ti +RLEN−1), assign COEFFS[bi ][tj ]the value zero.
(g) If SIGN is zero, assign COEFFS[bi ][ti + RLEN] the value MAG.
(h) Otherwise, assign COEFFS[bi ][ti + RLEN] the value −MAG.
(i) Assign TIS[bi ] the value TIS[bi ]+RLEN+1. Assign NCOEFFS[bi ]the value TIS[bi ].

94

CHAPTER 7. FRAME DECODE

7.7.3

DCT Coefficient Decode

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

NBS

Integer

36

No

Integer
Array

1

No

NMBS

Integer

32

No

HTS

Huffman table array

The total number of blocks in aframe.
An NBS-element array of flags
indicating which blocks arecoded.
The total number of macro
blocks in a frame.
An 80-element array of Huffman
tables with up to 32 entries each.

BCODED

Output parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions
An NBS × 64 array of quantized DCT coefficient values
for each block in zig-zag order.
An NBS-element array ofthe coefficient count for eachblock.

COEFFS

2D Integer
Array

16

Yes

NCOEFFS

Integer
Array

7

No

Variables used:

Name

Type

Size
(bits)

Signed?

Description and restrictions

NLBS

Integer

34

No

7

No

The number of blocks in the luma
plane.
An NBS-element array of the current token index for each block.

TIS

IntegerArray7.7. DCT COEFFICIENTS

95

Name

Type

Size
(bits)

Signed?

Description and restrictions

EOBS

Integer

36

No

Integer
Integer
Integer

5
3
36

No
No
No

bi

Integer

36

No

bj

Integer

36

No

ti
tj
hti L

Integer
Integer
Integer

6
6
4

No
No
No

hti C

Integer

4

No

hti

Integer

7No

The remaining length of the current
EOB run.
The current token being decoded.
The current Huffman table group.
The index of the current block in thecoded block list.
The index of the current block incoded order.
Another index of a block in coded
order.
The current token index.
Another token index.
The index of the current Huffman
table to use for the luma planewithin a group.
The index of the current Huffman
table to use for the chroma planes
within a group.
The index of the current Huffman
table to use.

TOKEN
HG
cbi

This procedure puts the above two procedures to work to decode the entire
set of DCT coefficients for the frame. At the end of this procedure, EOBS
MUST be zero, and TIS[bi ] MUST be 64 for every coded bi .
Note that we update the coefficient count of every block before continuing
an EOB run or decoding a token, despite the fact that it is already up to dateunless the previous token was a pure zero run. This is done intentionally tomimic the VP3 accounting rules. Thus the only time the coefficient count does
not include the coefficients in a pure zero run is when when that run reaches all
the way to coefficient 63. Note, however, that regardless of the coefficient count,any additional coefficients are still set to zero. The only use of the count is indetermining if a special case of the inverse DCT can be used in Section 7.9.3.2.
1. Assign NLBS the value (NMBS ∗ 4).
2. For each consecutive value of bi from 0 to (NBS − 1), assign TIS[bi ] thevalue zero.
3. Assign EOBS the value 0.
4. For each consecutive value of ti from 0 to 63:(a) If ti is 0 or 1:
i. Read a 4-bit unsigned integer as hti L .

96

CHAPTER 7. FRAME DECODE
ii. Read a 4-bit unsigned integer as hti C .
(b) For each consecutive value of bi from 0 to (NBS − 1) for which
BCODED[bi ] is non-zero and TIS[bi ] equals ti :i. Assign NCOEFFS[bi ] the value ti .
ii. If EOBS is greater than zero:
A. For each value of tj from ti to 63, assign COEFFS[bi ][tj ]the value zero.
B. Assign TIS[bi ] the value 64.
C. Assign EOBS the value (EOBS − 1).
iii. Otherwise:
A. Assign HG a value based on ti from Table 7.42.
ti

HG

0
1...5
6 . . . 14
15 . . . 27
28 . . . 63

0
1
2
3
4

Table 7.42: Huffman Table Groups
B. If bi is less than NLBS, assign hti the value (16 ∗ HG + hti L ).
C. Otherwise, assign hti the value (16 ∗ HG + hti C ).
D. Read one bit at a time until one of the codes in HTS[hti ] isrecognized, and assign the value to TOKEN.
E. If TOKEN is less than 7, expand an EOB token using the procedure given in Section 7.7.1 to update TIS[bi ], COEFFS[bi ],and EOBS.
F. Otherwise, expand a coefficient token using the procedure
given in Section 7.7.2 to update TIS[bi ], COEFFS[bi ], andNCOEFFS[bi ].

7.8

Undoing DC Prediction

The actual value of a DC coefficient decoded by Section 7.7 is the residual froma predicted value computed by the encoder. This prediction is only applied to
DC coefficients. Quantized AC coefficients are encoded directly.
This section describes how to undo this prediction to recover the original
DC coefficients. The predicted DC value for a block is computed from the DC
values of its immediate neighbors which precede the block in raster order. Thus,
reversing this prediction must procede in raster order, instead of coded order.

7.8. UNDOING DC PREDICTION

97

Note that this step comes before dequantizing the coefficients. For thisreason, DC coefficients are all quantized with the same qi value, regardless ofthe block-level qi values decoded in Section 7.6. Those qi values are applied
only to the AC coefficients.

7.8.1

Computing the DC Predictor

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

BCODED

Integer
Array

1

No

Integer
Array

3

No

LASTDC

Integer
Array

16

Yes

COEFFS

2D Integer
Array

16

Yes

bi

Integer

36

No

An NBS-element array offlags indicating which blocks
are coded.
An NMBS-element arrayof coding modes for eachmacro block.
A 3-element array containing the most recently decoded DC value, one for inter mode and for each reference frame.
An NBS×64 array of quantized DCT coefficient values
for each block in zig-zag order.
The index of the current
block in coded order.

MBMODES

Output parameters:

Name

Type

Size
(bits)

DCPRED

Integer16

Signed?

Description and restrictions

Yes

The predicted DC value for the current block.

98

CHAPTER 7. FRAME DECODE

Variables used:

Name

Type

Size
(bits)

Signed?

Description and restrictions

P

Integer
Array

1

No

Integer
Array

36

No

7

Yes

PDIV

IntegerArray
Integer8No

bj

Integer

36

No

mbi

Integer

32

No

mbj

Integer

32

No

rfi

Integer2No

A 4-element array indicating whichneighbors can be used for DC prediction.
A 4-element array containing thecoded-order block index of the current block’s neighbors.
A 4-element array of the weights toapply to each neighboring DC value.
The value to divide the weighted sumby.
The index of a neighboring block incoded order.
The index of the macro block containing block bi .
The index of the macro block containing block bj .
The index of the reference frame indicated by the coding mode for macro
block mbi .

PBI

WThis procedure outlines how a predictor is formed for a single block.
The predictor is computed as a weighted sum of the neighboring DC values
from coded blocks which use the same reference frame. This latter condition isdetermined only by checking the coding mode for the block. Even if the golden
frame and the previous frame are in fact the same, e.g. for the first inter frame
after an intra frame, they are still treated as being different for the purposes of
DC prediction. The weighted sum is divided by a power of two, with truncation
towards zero, and the result is checked for outranging if necessary.
If there are no neighboring coded blocks which use the same reference frame
as the current block, then the most recent DC value of any block that used thatreference frame is used instead. If no such block exists, then the predictor is set
to zero.
1. Assign mbi the index of the macro block containing block bi .
2. Assign rfi the value of the Reference Frame Index column of Table 7.46
corresponding to MBMODES[mbi ].
3. If block bi is not along the left edge of the coded frame:

7.8. UNDOING DC PREDICTION

99

Coding Mode

Reference Frame Index

0 (INTER NOMV)
1 (INTRA)
2 (INTER MV)
3 (INTER MV LAST)
4 (INTER MV LAST2)
5 (INTER GOLDEN NOMV)
6 (INTER GOLDEN MV)
7 (INTER MV FOUR)

1 (Previous)
0 (None)1 (Previous)
1 (Previous)
1 (Previous)
2 (Golden)
2 (Golden)
1 (Previous)

Table 7.46: Reference Frames for Each Coding Mode(a) Assign bj the coded-order index of block bi ’s left neighbor, i.e., in
the same row but one column to the left.
(b) If BCODED[bj ] is not zero:i. Assign mbj the index of the macro block containing block bj .
ii. If the value of the Reference Frame Index column of Table 7.46
corresonding to MBMODES[mbj ] equals rfi :A. Assign P[0] the value 1.
B. Assign PBI[0] the value bj .
iii. Otherwise, assign P[0] the value zero.
(c) Otherwise, assign P[0] the value zero.
4. Otherwise, assign P[0] the value zero.
5. If block bi is not along the left edge nor the bottom edge of the codedframe:(a) Assign bj the coded-order index of block bi ’s lower-left neighbor, i.e.,
one row down and one column to the left.
(b) If BCODED[bj ] is not zero:i. Assign mbj the index of the macro block containing block bj .
ii. If the value of the Reference Frame Index column of Table 7.46
corresonding to MBMODES[mbj ] equals rfi :A. Assign P[1] the value 1.
B. Assign PBI[1] the value bj .
iii. Otherwise, assign P[1] the value zero.
(c) Otherwise, assign P[1] the value zero.
6. Otherwise, assign P[1] the value zero.
7. If block bi is not along the bottom edge of the coded frame:

100

CHAPTER 7. FRAME DECODE(a) Assign bj the coded-order index of block bi ’s lower neighbor, i.e., in
the same column but one row down.
(b) If BCODED[bj ] is not zero:i. Assign mbj the index of the macro block containing block bj .
ii. If the value of the Reference Frame Index column of Table 7.46
corresonding to MBMODES[mbj ] equals rfi :A. Assign P[2] the value 1.
B. Assign PBI[2] the value bj .
iii. Otherwise, assign P[2] the value zero.
(c) Otherwise, assign P[2] the value zero.

8. Otherwise, assign P[2] the value zero.
9. If block bi is not along the right edge nor the bottom edge of the codedframe:(a) Assign bj the coded-order index of block bi ’s lower-right neighbor,i.e., one row down and one column to the right.
(b) If BCODED[bj ] is not zero:i. Assign mbj the index of the macro block containing block bj .
ii. If the value of the Reference Frame Index column of Table 7.46
corresonding to MBMODES[mbj ] equals rfi :A. Assign P[3] the value 1.
B. Assign PBI[3] the value bj .
iii. Otherwise, assign P[3] the value zero.
(c) Otherwise, assign P[3] the value zero.
10. Otherwise, assign P[3] the value zero.
11. If none of the values P[0], P[1], P[2], nor P[3] are non-zero, then assign
DCPRED the value LASTDC[rfi ].
12. Otherwise:(a) Assign the array W and the variable PDIV the values from the rowof Table 7.47 corresonding to the values of each P[i ].
(b) Assign DCPRED the value zero.
(c) If P[0] is non-zero, assign DCPRED the value (DCPRED + W[0] ∗COEFFS[PBI[0]][0]).
(d) If P[1] is non-zero, assign DCPRED the value (DCPRED + W[1] ∗COEFFS[PBI[1]][0]).
(e) If P[2] is non-zero, assign DCPRED the value (DCPRED + W[2] ∗COEFFS[PBI[2]][0]).

7.8. UNDOING DC PREDICTION
P[0]
(L)

P[1]
(DL)

P[2]
(D)

P[3]
(DR)

1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

0
1
1
0
0
1
1
0
0
1
1
0
0
1
1

0
0
0
1
1
1
1
0
0
0
0
1
1
1
1

0
0
0
0
0
0
0
1
1
1
1
1
1
1
1

101
W[0]
(L)

W[1]
(DL)

W[2]
(D)

W[3]
(DR)

PDIV

1
0
1
0
1
0
29
0
75
0
75
0
75
0
29

0
1
0
0
0
0
−26
0
0
1
0
0
0
3
−26

0
0
0
1
1
1
29
0
0
0
0
1
0
10
29

0
0
0
0
0
0
0
1
53
1
53
0
53
3
0

1
1
1
1
2
1
32
1
128
2
128
1
128
16
32

Table 7.47: Weights and Divisors for Each Set of Available DC Predictors(f) If P[3] is non-zero, assign DCPRED the value (DCPRED + W[3] ∗COEFFS[PBI[3]][0]).
(g) Assign DCPRED the value (DCPRED//PDIV).
(h) If P[0], P[1], and P[2] are all non-zero:i. If |DCPRED−COEFFS[PBI[2]][0]| is greater than 128, assign
DCPRED the value COEFFS[PBI[2]][0].
ii. Otherwise, if |DCPRED − COEFFS[PBI[0]][0]| is greater than128, assign DCPRED the value COEFFS[PBI[0]][0].
iii. Otherwise, if |DCPRED − COEFFS[PBI[1]][0]| is greater than128, assign DCPRED the value COEFFS[PBI[1]][0].

7.8.2

Inverting the DC Prediction Process

Input parameters:

Name

Type

Size
(bits)BCODED

IntegerArray

1

Signed?

Description and restrictionsNo

An NBS-element array offlags indicating which blocks
are coded.

102

CHAPTER 7. FRAME DECODE
Name

Type

Size
(bits)

Signed?

Description and restrictions

MBMODES

Integer
Array

3

No

16

Yes

An NMBS-element arrayof coding modes for eachmacro block.
An NBS×64 array of quantized DCT coefficient values
for each block in zig-zag order.

COEFFS

2D Integer
Array

Output parameters:

Name

Type

COEFFS

2D Integer
Array

Size
(bits)
16

Signed?

Description and restrictionsYes

An NBS×64 array of quantized
DCT coefficient values for eachblock in zig-zag order. The DC
value of each block will be updated.

Variables used:

Name

Type

Size
(bits)

Signed?

Description and restrictions

LASTDC

Integer
Array

16

Yes

Integer

11

Yes

DC

Integer

17

Yes

bi

Integer

36

No

mbi

Integer

32

No

A 3-element array containing themost recently decoded DC value,
one for inter mode and for each reference frame.
The predicted DC value for thecurrent block.
The actual DC value for the current block.
The index of the current block incoded order.
The index of the macro block containing block bi .

DCPRED7.9. RECONSTRUCTION
Name

103

Type

Size
(bits)

Signed?

Description and restrictions

rfi

Integer

2

No

2

No

The index of the reference frame
indicated by the coding mode formacro block mbi .
A color plane index.

pli

IntegerThis procedure describes the complete process of undoing the DC prediction
to recover the original DC values. Because it is possible to add a value as large
as 580 to the predicted DC coefficient value at every block, which will then be
used to increase the predictor for the next block, the reconstructed DC value
could overflow a 16-bit integer. This is handled by truncating the result to a
16-bit signed representation, simply throwing away any higher bits in the two’s
complement representation of the number.
1. For each consecutive value of pli from 0 to 2:(a) Assign LASTDC[0] the value zero.
(b) Assign LASTDC[1] the value zero.
(c) Assign LASTDC[2] the value zero.
(d) For each block of color plane pli in raster order, with coded-orderindex bi :i. If BCODED[bi ] is non-zero:
A. Compute the value DCPRED using the procedure outlined
in Section 7.8.1.
B. Assign DC the value (COEFFS[bi ][0] + DCPRED).
C. Truncate DC to a 16-bit representation by dropping any
higher-order bits.
D. Assign COEFFS[bi ][0] the value DC.
E. Assign mbi the index of the macro block containing block bi .
F. Assign rfi the value of the Reference Frame Index column ofTable 7.46 corresponding to MBMODES[mbi ].
G. Assign LASTDC[rfi ] the value DC.

7.9

Reconstruction

At this stage, the complete contents of the data packet have been decoded. All
that remains is to reconstruct the contents of the new frame. This is applied
on a block by block basis, and as each block is independent, the order they areprocessed in does not matter.

104

CHAPTER 7. FRAME DECODE

7.9.1

Predictors

For each block, a predictor is formed based on its coding mode and motion
vector. There are three basic types of predictors: the intra predictor, the wholepixel predictor, and the half-pixel predictor. The former is used for all blocks
coded in INTRA mode, while all other blocks use one of the latter two. The
whole-pixel predictor is used if the fractional part of both motion vector components is zero, otherwise the half-pixel predictor is used.
7.9.1.1

The Intra Predictor

Input parameters:
None.
Output parameters:

Name

Type

Size
(bits)PRED

2D Integer
Array

Signed?

Description and restrictions

No

An 8 × 8 array of predictor values
to use for INTRA coded blocks.

8

Variables used:

Name

Type

Size
(bits)

bx
byInteger
Integer33Signed?

Description and restrictions

No
No

The horizontal pixel index in the block.
The vertical pixel index in the block.

The intra predictor is nothing more than the constant value 128. This isapplied for the sole purpose of centering the range of possible DC values for
INTRA blocks around zero.
1. For each value of by from 0 to 7, inclusive:(a) For each value of bx from 0 to 7, inclusive:i. Assign PRED[by][bx ] the value 128.

7.9. RECONSTRUCTION
7.9.1.2

105

The Whole-Pixel Predictor

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

RPW

Integer

20

No

Integer

20

No

REFP

2D Integer
Array

8

No

BX

Integer

20

No

BY

Integer

20

No

MVX

Integer

5

No

MVY

Integer

5No

The width of the current plane of
the reference frame in pixels.
The height of the current plane of
the reference frame in pixels.
A RPH × RPW array containing
the contents of the current plane of
the reference frame.
The horizontal pixel index of thelower-left corner of the current
block.
The vertical pixel index of thelower-left corner of the current
block.
The horizontal component of theblock motion vector. This is always
a whole-pixel value.
The vertical component of theblock motion vector. This is always
a whole-pixel value.

RPH

Output parameters:

Name

Type

PRED

2D Integer
Array

Variables used:Size(bits)
8

Signed?

Description and restrictions

No

An 8 × 8 array of predictor values
to use for INTER coded blocks.

106

CHAPTER 7. FRAME DECODE

Name

Type

Size
(bits)

Signed?

Description and restrictions

bx
by
rx

Integer
Integer
Integer

3
3
20

Yes
Yes
No

20

No

The horizontal pixel index in the block.
The vertical pixel index in the block.
The horizontal pixel index in the reference frame.
The vertical pixel index in the reference
frame.

ry

Integer

The whole pixel predictor simply copies verbatim the contents of the reference frame pointed to by the block’s motion vector. If the vector points outside
the reference frame, then the closest value on the edge of the reference frame
is used instead. In practice, this is usually implemented by expanding the sizeof the reference frame by 8 or 16 pixels on each side—depending on whether or
not the corresponding axis is subsampled in the current plane—and copying theborder pixels into this region.
1. For each value of by from 0 to 7, inclusive:(a) Assign ry the value (BY + MVY + by).
(b) If ry is greater than (RPH − 1), assign ry the value (RPH − 1).
(c) If ry is less than zero, assign ry the value zero.
(d) For each value of bx from 0 to 7, inclusive:i. Assign rx the value (BX + MVX + bx ).
ii. If rx is greater than (RPW−1), assign rx the value (RPW−1).
iii. If rx is less than zero, assign rx the value zero.
iv. Assign PRED[by][bx ] the value REFP[ry][rx ].
7.9.1.3

The Half-Pixel Predictor

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

RPW

Integer

20

No

Integer

20

No

2D Integer
Array

8

No

The width of the current plane of
the reference frame in pixels.
The height of the current plane of
the reference frame in pixels.
A RPH × RPW array containing
the contents of the current planeof the reference frame.

RPH
REFP

7.9. RECONSTRUCTION
Name

107

Type

Size
(bits)

Signed?

Description and restrictions

BX

Integer

20

No

Integer

20

No

MVX

Integer

5

No

MVY

Integer

5

No

MVX2

Integer

5

No

MVY2

Integer

5No

The horizontal pixel index of thelower-left corner of the current
block.
The vertical pixel index of thelower-left corner of the current
block.
The horizontal component of thefirst whole-pixel motion vector.
The vertical component of the firstwhole-pixel motion vector.
The horizontal component of thesecond whole-pixel motion vector.
The vertical component of the second whole-pixel motion vector.

BY

Output parameters:

Name

Type

Size
(bits)PRED

2D Integer
Array

Signed?

Description and restrictions

No

An 8 × 8 array of predictor values
to use for INTER coded blocks.

8

Variables used:

Name

Type

Size
(bits)

Signed?

Description and restrictions

bx
by
rx1

Integer
Integer
Integer

3
3
20

Yes
Yes
No

Integer

20

No

rx2

Integer

20

No

ry2

Integer

20

No

The horizontal pixel index in the block.
The vertical pixel index in the block.
The first horizontal pixel index in thereference frame.
The first vertical pixel index in the reference frame.
The second horizontal pixel index in thereference frame.
The second vertical pixel index in thereference frame.

ry1

108

CHAPTER 7. FRAME DECODE

If one or both of the components of the block motion vector is not a wholepixel value, then the half-pixel predictor is used. The half-pixel predictor converts the fractional motion vector into two whole-pixel motion vectors. The
first is formed by truncating the values of each component towards zero, andthe second is formed by truncating them away from zero. The contributions
from the reference frame at the locations pointed to by each vector are averaged, truncating towards negative infinity.
Only two samples from the reference frame contribute to each predictor
value, even if both components of the motion vector have non-zero fractional
components. Motion vector components with quarter-pixel accuracy in thechroma planes are treated exactly the same as those with half-pixel accuracy.
Any non-zero fractional part gets rounded one way in the first vector, and theother way in the second.
1. For each value of by from 0 to 7, inclusive:(a) Assign ry1 the value (BY + MVY1 + by).
(b) If ry1 is greater than (RPH − 1), assign ry1 the value (RPH − 1).
(c) If ry1 is less than zero, assign ry1 the value zero.
(d) Assign ry2 the value (BY + MVY2 + by).
(e) If ry2 is greater than (RPH − 1), assign ry2 the value (RPH − 1).
(f) If ry2 is less than zero, assign ry2 the value zero.
(g) For each value of bx from 0 to 7, inclusive:i. Assign rx1 the value (BX + MVX1 + bx ).
ii. If rx1 is greater than (RPW −1), assign rx1 the value (RPW −1).
iii. If rx1 is less than zero, assign rx1 the value zero.
iv. Assign rx2 the value (BX + MVX2 + bx ).
v. If rx2 is greater than (RPW −1), assign rx2 the value (RPW −1).
vi. If rx2 is less than zero, assign rx2 the value zero.
vii. Assign PRED[by][bx ] the value(REFP[ry1 ][rx1 ] + REFP[ry2 ][rx2 ]) >> 1.

7.9.2

Dequantization

Input parameters:

7.9. RECONSTRUCTION
Name

Type

109
Size
(bits)

Signed?

Description and restrictions
An NBS × 64 array of quantized DCT coefficient values
for each block in zig-zag order.
A 64-element array of scalevalues for AC coefficients foreach qi value.
A 64-element array of scalevalues for the DC coefficientfor each qi value.
A NBMS × 64 array containing the base matrices.
A 2 × 3 array containing thenumber of quant ranges for agiven qti and pli , respectively.
This is at most 63.
A 2 × 3 × 63 array of thesizes of each quant range for agiven qti and pli , respectively.
Only the first NQRS[qti ][pli ]values are used.
A 2 × 3 × 64 array of the
bmi ’s used for each quantrange for a given qti and pli ,respectively. Only the first(NQRS[qti ][pli ] + 1) values
are used.
A quantization type index.
See Table 3.1.
A color plane index. See Table 2.1.
The quantization index of the
DC coefficient.
The quantization index of the
AC coefficients.
The index of the current blockin coded order.

COEFFS

2D Integer
Array

16

Yes

ACSCALE

Integer
array

16

No

DCSCALE

Integer
array

16

No

BMS

2D Integer
array
2D Integer
array

8

No

6

No

QRSIZES

3D Integer
array

6

No

QRBMIS

3D Integer
array

9

No

qti

Integer

1

No

pli

Integer

2

No

qi0

Integer

6No

qi

Integer

6Nobi

Integer

36

No

NQRS

Output parameters:

110

CHAPTER 7. FRAME DECODE

Name

Type

Size
(bits)

DQC

IntegerArray

14

Signed?

Description and restrictions

Yes

A 64-element array of dequantized
DCT coefficients in natural order (cf.
Section 2.6).

Signed?

Description and restrictions
A 64-element array of quantization
values for each DCT coefficient innatural order.
The DCT coefficient index in naturalorder.
The DCT coefficient index in zig-zag
order.
A single dequantized coefficient.

Variables used:

Name

Type

Size
(bits)

QMAT

Integer
array

16

No

ci

Integer

6

No

zzi

Integer

6

No

C

Integer

29

Yes

This procedure takes the quantized DCT coefficient values in zig-zag order
for a single block—after DC prediction has been undone—and returns the dequantized values in natural order. If large coefficient values are decoded forcoarsely quantized coefficients, the resulting dequantized value can be significantly larger than 16 bits. Such a coefficient is truncated to a signed 16-bit
representation by discarding the higher-order bits of its twos-complement representation.
Although this procedure recomputes the quantization matrices from the parameters in the setup header for each block, there are at most six different ones
used for each color plane. An efficient implementation could compute them oncein advance.
1. Using ACSCALE, DCSCALE, BMS, NQRS, QRSIZES, QRBMIS,
qti , pli , and qi0 , use the procedure given in Section 6.4.3 to compute theDC quantization matrix QMAT.
2. Assign C the value COEFFS[bi ][0] ∗ QMAT[0].
3. Truncate C to a 16-bit representation by dropping any higher-order bits.
4. Assign DQC[0] the value C.

7.9. RECONSTRUCTION

111

5. Using ACSCALE, DCSCALE, BMS, NQRS, QRSIZES, QRBMIS,
qti , pli , and qi , use the procedure given in Section 6.4.3 to compute theAC quantization matrix QMAT.
6. For each value of ci from 1 to 63, inclusive:(a) Assign zzi the index in zig-zag order corresponding to ci . E.g., thevalue at row (ci //8) and column (ci %8) in Figure 2.8(b) Assign C the value COEFFS[bi ][zzi ] ∗ QMAT[ci ].
(c) Truncate C to a 16-bit representation by dropping any higher-orderbits.
(d) Assign DQC[ci ] the value C.

7.9.3

The Inverse DCT

The 2D inverse DCT is separated into two applications of the 1D inverse DCT.
The transform is first applied to each row, and then applied to each column ofthe result.
Each application of the 1D inverse DCT scales the values by a factor of two
relative to the orthonormal version of the transform, for a total scale factor offour for the 2D transform. It is assumed that a similar scale factor is applied
during the forward DCT used in the encoder, so that a division by 16 is required
after the transform has been applied in both directions. The inclusion of thisscale factor allows the integerized transform to operate with increased precision.
All divisions throughout the transform are implemented with right shifts. Only
the final division by 16 is rounded, with ties rounded towards positive infinity.
All intermediate values are truncated to a 32-bit signed representation bydiscarding any higher-order bits in their two’s complement representation. The
final output of each 1D transform is truncated to a 16-bit signed value in thesame manner. In practice, if the high word of a 16 × 16 bit multiplication can beobtained directly, 16 bits is sufficient for every calculation except scaling by C4.
Thus we truncate to 16 bits before that multiplication to allow an implementation entirely in 16-bit registers. Implementations using larger registers mustsign-extend the 16-bit value to maintain compatibility.
Note that if 16-bit register are used, overflow in the additions and subtractions should be handled using unsaturated arithmetic. That is, the high-order
bits should be discarded and the low-order bits retained, instead of clamping theresult to the maximum or minimum value. This allows the maximum flexibility
in re-ordering these instructions without deviating from this specification.
The 1D transform can only overflow if input coefficients larger than ±6201
are present. However, the result of applying the 2D forward transform on pixel
values in the range −255 . . . 255 can be as large as ±8157 due to the scale factor
of four that is applied, and quantization errors could make this even larger.
Therefore, the coefficients cannot simply be clamped into a valid range before
the transform.

112
7.9.3.1

CHAPTER 7. FRAME DECODE
The 1D Inverse DCT

Input parameters:

Name
Y

Type

Size
(bits)

IntegerArray

16

Signed?

Description and restrictions

Yes

An 8-element array of DCT coefficients.

Signed?

Description and restrictions

Yes

An 8-element array of output values.

Signed?

Description and restrictions
An 8-element array containing thecurrent value of each signal line.
A temporary value.

Output parameters:

Name
X

Type

Size
(bits)

IntegerArray

16

Variables used:

Name
T
R

Type

Size
(bits)

IntegerArray
Integer

32

Yes

32

Yes

A compliant decoder MUST use the exact implementation of the inverse
DCT defined in this specification. Some operations may be re-ordered, but theresult must be precisely equivalent. This is a design decision that limits someavenues of decoder optimization, but prevents any drift in the prediction loop.
The full inverse DCT described in this section is only used when there is at least
one non-zero AC coefficient. Otherwise, a special DC-only case is used, which
is described below in step 2(d)vii of Section 7.9.4. The DC-only special case is
not exactly equivalent to applying the full inverse transform, because it avoids
the intermediate multiplications and truncation, and it MUST be used in placeof the full transform to ensure bit-exact decode.
Theora uses a 16-bit integerized approximation of the 8-point 1D inverse

7.9. RECONSTRUCTION113

DCT based on the Chen factorization [CSF77]. It requires 16 multiplications
and 26 additions and subtractions.
C4
0

0
C4

4

C6

2

2

−

−S6
C6 S6

6

1

1

−

3

−
C7
−
−S7
C4

C3

5

−S3
C3 S3

3

−

−
−

4

−

5

C4
−

6

S7
7

C7
−

7

Figure 7.1: Signal Flow Graph for the 1D Inverse DCT
A signal flow graph of the transformation is presented in Figure 7.1. Thisgraph provides a good visualization of which parts of the transform are parallelizable. Time increases from left to right.
Each signal line is involved in an operation where the line is marked with adot · or a circled plus sign ⊕. The constants Ci and Sj are the 16-bit integeriπapproximations of cos( 16) and sin( jπ16 ) listed in Table 7.65. When they appear
next to a signal line, the value on that line is scaled by the given constant. A
circled minus sign
next to a signal line indicates that the value on that line
is negated.
Operations on a single signal path through the graph cannot be reordered,but operations on different paths may be, or may be executed in parallel. Different graphs may be obtainable using the associative, commutative, and distributive properties of unsaturated arithmetic. The column of numbers on theleft represents an initial permutation of the input DCT coefficients. The column on the right represents the unpermuted output. One can be obtained bybit-reversing the 3-bit binary representation of the other.
1. Assign T[0] the value Y[0] + Y[4].
2. Truncate T[0] to a 16-bit signed representation by dropping any higherorder bits.
3. Assign T[0] the value C4 ∗ T[0] >> 16.
4. Assign T[1] the value Y[0] − Y[4].

114

CHAPTER 7. FRAME DECODE
Ci

Sj

Value

C1
C2
C3
C4
C5
C6
C7

S7
S6
S5
S4
S3
S2
S1

64277
60547
54491
46341
36410
25080
12785

Table 7.65: 16-bit Approximations of Sines and Cosines
5. Truncate T[1] to a 16-bit signed representation by dropping any higherorder bits.
6. Assign T[1] the value C4 ∗ T[1] >> 16.
7. Assign T[2] the value (C6 ∗ Y[2] >> 16) − (S6 ∗ Y[6] >> 16).
8. Assign T[3] the value (S6 ∗ Y[2] >> 16) + (C6 ∗ Y[6] >> 16).
9. Assign T[4] the value (C7 ∗ Y[1] >> 16) − (S7 ∗ Y[7] >> 16).
10. Assign T[5] the value (C3 ∗ Y[5] >> 16) − (S3 ∗ Y[3] >> 16).
11. Assign T[6] the value (S3 ∗ Y[5] >> 16) + (C3 ∗ Y[3] >> 16).
12. Assign T[7] the value (S7 ∗ Y[1] >> 16) + (C7 ∗ Y[7] >> 16).
13. Assign R the value T[4] + T[5].
14. Assign T[5] the value T[4] − T[5].
15. Truncate T[5] to a 16-bit signed representation by dropping any higherorder bits.
16. Assign T[5] the value C4 ∗ T[5] >> 16.
17. Assign T[4] the value R.
18. Assign R the value T[7] + T[6].
19. Assign T[6] the value T[7] − T[6].
20. Truncate T[6] to a 16-bit signed representation by dropping any higherorder bits.
21. Assign T[6] the value C4 ∗ T[6] >> 16.
22. Assign T[7] the value R.

7.9. RECONSTRUCTION

115

23. Assign R the value T[0] + T[3].
24. Assign T[3] the value T[0] − T[3].
25. Assign T[0] the value R.
26. Assign R the value T[1] + T[2]27. Assign T[2] the value T[1] − T[2]28. Assign T[1] the value R.
29. Assign R the value T[6] + T[5].
30. Assign T[5] the value T[6] − T[5].
31. Assign T[6] the value R.
32. Assign R the value T[0] + T[7].
33. Truncate R to a 16-bit signed representation by dropping any higher-orderbits.
34. Assign X[0] the value R.
35. Assign R the value T[1] + T[6].
36. Truncate R to a 16-bit signed representation by dropping any higher-orderbits.
37. Assign X[1] the value R.
38. Assign R the value T[2] + T[5].
39. Truncate R to a 16-bit signed representation by dropping any higher-orderbits.
40. Assign X[2] the value R.
41. Assign R the value T[3] + T[4].
42. Truncate R to a 16-bit signed representation by dropping any higher-orderbits.
43. Assign X[3] the value R.
44. Assign R the value T[3] − T[4].
45. Truncate R to a 16-bit signed representation by dropping any higher-orderbits.
46. Assign X[4] the value R.
47. Assign R the value T[2] − T[5].

116

CHAPTER 7. FRAME DECODE

48. Truncate R to a 16-bit signed representation by dropping any higher-orderbits.
49. Assign X[5] the value R.
50. Assign R the value T[1] − T[6].
51. Truncate R to a 16-bit signed representation by dropping any higher-orderbits.
52. Assign X[6] the value R.
53. Assign R the value T[0] − T[7].
54. Truncate R to a 16-bit signed representation by dropping any higher-orderbits.
55. Assign X[7] the value R.
7.9.3.2

The 2D Inverse DCT

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

DQC

Integer
Array

14

Yes

A 64-element array of dequantized
DCT coefficients in natural order (cf.
Section 2.6).

Size(bits)

Signed?

Description and restrictions

Yes

An 8 × 8 array containing thedecoded residual for the current
block.

Output parameters:

Name
RES

Type
2D Integer
Array

Variables used:16

7.9. RECONSTRUCTION
Name
ci
ri
Y
X

Type

Size
(bits)

Integer
Integer
IntegerArray
IntegerArray

117
Signed?

Description and restrictions

3
3
16

No
No
Yes

16

Yes

The column index.
The row index.
An 8-element array of 1D iDCT input
values.
An 8-element array of 1D iDCT output values.

This procedure applies the 1D inverse DCT transform 16 times to a blockof dequantized coefficients: once for each of the 8 rows, and once for each of the
8 columns of the result. Note that the coordinate system used for the columns
is the same right-handed coordinate system used by the rest of Theora. Thus,
the column is indexed from bottom to top, not top to bottom. The final values
are divided by sixteen, rounding with ties rounded towards postive infinity.
1. For each value of ri from 0 to 7:(a) For each value of ci from 0 to 7:
i. Assign Y[ci ] the value DQC[ri ∗ 8 + ci ].
(b) Compute X, the 1D inverse DCT of Y using the procedure describedin Section 7.9.3.1.
(c) For each value of ci from 0 to 7:
i. Assign RES[ri ][ci ] the value X[ci ].
2. For each value of ci from 0 to 7:(a) For each value of ri from 0 to 7:
i. Assign Y[ri ] the value RES[ri ][ci ].
(b) Compute X, the 1D inverse DCT of Y using the procedure describedin Section 7.9.3.1.
(c) For each value of ri from 0 to 7:
i. Assign RES[ri ][ci ] the value (X[ri ] + 8) >> 4.
7.9.3.3

The 1D Forward DCT (Non-Normative)

Input parameters:

118
Name
X

CHAPTER 7. FRAME DECODE
Type

Size
(bits)

IntegerArray

14

Signed?

Description and restrictions

Yes

An 8-element array of input values.

Signed?

Description and restrictions

Yes

An 8-element array of DCT coefficients.

Signed?

Description and restrictions
An 8-element array containing thecurrent value of each signal line.
A temporary value.

Output parameters:

Name
Y

Type

Size
(bits)

IntegerArray

16

Variables used:

Name
T
R

Type

Size
(bits)

IntegerArray
Integer

16

Yes

16

Yes

The forward transform used in the encoder is not mandated by this standard
as the inverse one is. Precise equivalence in the inverse transform alone is allthat is required to guarantee that there is no mismatch in the prediction loop
between encoder and any compliant decoder implementation. However, a forward transform is provided here as a convenience for implementing an encoder.
This is the version of the transform used by Xiph.Org’s Theora encoder, whichis the same as that used by VP3. Like the inverse DCT, it is first applied toeach row, and then applied to each column of the result.
The signal flow graph for the forward transform is given in Figure 7.2. It islargely the reverse of the flow graph given for the inverse DCT. It is important
to note that the signs on the constants in the rotations have changed, and theC4 scale factors on one of the lower butterflies now appear on the opposite side.
The column of numbers on the left represents the unpermuted input, and thecolumn on the right the permuted output DCT coefficients.
A proper division by 216 is done after the multiplications instead of a shift
in the forward transform. This can be implemented quickly by adding an offset
of 0xFFFF if the number is negative, and then shifting as before. This slightly

7.9. RECONSTRUCTION

119
C4

0

0
C4

1

4

−
C6

2

−

3

2

S6
C6 −S6

6

−
C7

4

1

−
−

5

S7
C4

−
C4

6

C3
−

S3
C3 −S3

−

−

5

3

−S7
7

C7
−

7

Figure 7.2: Signal Flow Graph for the 1D Forward DCT
increases the computational complexity of the transform. Unlike the inverse
DCT, 16-bit registers and a 16 × 16 → 32 bit multiply are sufficient to avoid
any overflow, so long as the input is in the range −6270 . . . 6270, which is larger
than required.
1. Assign T[0] the value X[0] + X[7].
2. Assign T[1] the value X[1] + X[6].
3. Assign T[2] the value X[2] + X[5].
4. Assign T[3] the value X[3] + X[4].
5. Assign T[4] the value X[3] − X[4].
6. Assign T[5] the value X[2] − X[5].
7. Assign T[6] the value X[1] − X[6].
8. Assign T[7] the value X[0] − X[7].
9. Assign R the value T[0] + T[3].
10. Assign T[3] the value T[0] − T[3].
11. Assign T[0] the value R.
12. Assign R the value T[1] + T[2].
13. Assign T[2] the value T[1] − T[2].

120

CHAPTER 7. FRAME DECODE

14. Assign T[1] the value R.
15. Assign R the value T[6] − T[5].
16. Assign T[6] the value (C4 ∗ (T[6] + T[5]))//16.
17. Assign T[5] the value (C4 ∗ R)//16.
18. Assign R the value T[4] + T[5].
19. Assign T[5] the value T[4] − T[5].
20. Assign T[4] the value R.
21. Assign R the value T[7] + T[6].
22. Assign T[6] the value T[7] − T[6].
23. Assign T[7] the value R.
24. Assign Y[0] the value (C4 ∗ (T[0] + T[1]))//16.
25. Assign Y[4] the value (C4 ∗ (T[0] − T[1]))//16.
26. Assign Y[2] the value ((S6 ∗ T[3])//16) + ((C6 ∗ T[2])//16).
27. Assign Y[6] the value ((C6 ∗ T[3])//16) − ((S6 ∗ T[2])//16).
28. Assign Y[1] the value ((S7 ∗ T[7])//16) + ((C7 ∗ T[4])//16).
29. Assign Y[5] the value ((S3 ∗ T[6])//16) + ((C3 ∗ T[5])//16).
30. Assign Y[3] the value ((C3 ∗ T[6])//16) − ((S3 ∗ T[5])//16).
31. Assign Y[7] the value ((C7 ∗ T[7])//16) − ((S7 ∗ T[4])//16).

7.9.4

The Complete Reconstruction Algorithm

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

ACSCALE

Integer
array

16

No

16

No

A 64-element array of
scale values for AC coefficients for each qi value.
A 64-element array of
scale values for the DC
coefficient for each qi
value.

DCSCALE

Integerarray7.9. RECONSTRUCTION
Name
BMS

Type

121
Size
(bits)

Signed?

Description and restrictions
A NBMS×64 array containing the base matrices.
A 2 × 3 array containing the number of quantranges for a given qti andpli , respectively. This is
at most 63.
A 2 × 3 × 63 array of thesizes of each quant range
for a given qti and pli ,respectively. Only the
first NQRS[qti ][pli ] values are used.
A 2 × 3 × 64 arrayof the bmi ’s used foreach quant range for agiven qti and pli , respectively.
Only the first(NQRS[qti ][pli ] + 1) values are used.
The width of the Y 0 planeof the reference frames in
pixels.
The height of the Y 0plane of the reference
frames in pixels.
The width of the Cb andCr planes of the reference
frames in pixels.
The height of the Cb andCr planes of the reference
frames in pixels.
A RPYH × RPYW array containing the contents of the Y 0 planeof the golden reference
frame.
A RPCH × RPCW array containing the contents of the Cb planeof the golden reference
frame.

2D Integer
array
2D Integer
array

8

No

6

No

QRSIZES

3D Integer
array

6

No

QRBMIS

3D Integer
array

9

No

RPYW

Integer

20

No

RPYH

Integer

20

No

RPCW

Integer

20

No

RPCH

Integer

20

No

GOLDREFY

2D Integer
Array

8

No

GOLDREFCB

2D Integer
Array

8

No

NQRS

122

CHAPTER 7. FRAME DECODE
Name

Type

GOLDREFCR

2D Integer
Array

PREVREFY

Signed?

Description and restrictions

8No

2D Integer
Array

8

No

PREVREFCB

2D Integer
Array

8

No

PREVREFCR

2D Integer
Array

8

No

NBS

Integer

36

No

BCODED

Integer
Array

1

No

MBMODES

Integer
Array

3

No

MVECTSArrayof
2D Integer
Vectors
2D Integer
Array

6

Yes

16

Yes

A RPCH × RPCW array containing the contents of the Cr planeof the golden reference
frame.
A RPYH × RPYW array containing the contents of the Y 0 planeof the previous reference
frame.
A RPCH × RPCW array containing the contents of the Cb planeof the previous reference
frame.
A RPCH × RPCW array containing the contents of the Cr planeof the previous reference
frame.
The total number ofblocks in a frame.
An NBS-element arrayof flags indicating whichblocks are coded.
An NMBS-element array of coding modes foreach macro block.
An NBS-element arrayof motion vectors for eachblock.
An NBS × 64 arrayof quantized DCT coefficient values for eachblock in zig-zag order.
An NBS-element arrayof the coefficient countfor each block.
An NQIS-element arrayof qi values.
An NBS-element arrayof qii values for eachblock.

COEFFS

Size(bits)NCOEFFS

Integer
Array

7

No

QIS

Integerarray
Integer
Array

6

No

2

No

QIIS

7.9. RECONSTRUCTION
Name

123

Type

Size
(bits)

Signed?

Description and restrictions

Output parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions
A RPYH × RPYW array containing the contents of the Y 0plane of the reconstructed frame.
A RPCH × RPCW array containing the contents of the Cb
plane of the reconstructed frame.
A RPCH × RPCW array containing the contents of the Crplane of the reconstructed frame.

RECY

2D Integer
Array

8

No

RECCB

2D Integer
Array

8

No

RECCR

2D Integer
Array

8

No

Variables used:

Name

Type

Size
(bits)

Signed?

Description and restrictions

RPW

Integer

20

No

Integer

20

No

REFP

2D Integer
Array

8

No

BX

Integer

20

No

BY

Integer

20

No

MVX

Integer

5No

The width of the current plane of
the current reference frame in pixels.
The height of the current plane of
the current reference frame in pixels.
A RPH × RPW array containing
the contents of the current plane of
the current reference frame.
The horizontal pixel index of thelower-left corner of the current
block.
The vertical pixel index of thelower-left corner of the current
block.
The horizontal component of thefirst whole-pixel motion vector.

RPH

124
Name

CHAPTER 7. FRAME DECODE
Type

Size
(bits)

Signed?

Description and restrictions

MVY

Integer

5NoInteger

5

No

MVY2

Integer

5

No

PRED

2D Integer
Array
2D Integer
Array

8

No

16

Yes

The vertical component of the firstwhole-pixel motion vector.
The horizontal component of thesecond whole-pixel motion vector.
The vertical component of the second whole-pixel motion vector.
An 8 × 8 array of predictor values
to use for the current block.
An 8 × 8 array containing thedecoded residual for the current
block.
A 64-element array of quantization
values for each DCT coefficient innatural order.
The dequantized DC coefficient ofa block.
A reconstructed pixel value.
The index of the current block incoded order.
The index of the macro block containing block bi .
The color plane index of the current
block.
The index of the reference frame
indicated by the coding mode formacro block mbi .
The horizontal pixel index in theblock.
The vertical pixel index in theblock.
A quantization type index. See Table 3.1.
The quantization index of the DC
coefficient.
The quantization index of the AC
coefficients.

MVX2

RES

QMAT

Integer
array

16

No

DC

Integer

29

Yes

P
bi

Integer
Integer

17
36

Yes
No

mbi

Integer

32

No

pli

Integer

2

No

rfi

Integer2

Nobx

Integer

3

No

byInteger

3

No

qti

Integer

1

No

qi0

Integer

6No

qi

Integer

6

NoThis section takes the decoded packet data and uses the previously definedprocedures to reconstruct each block of the current frame. For coded blocks,
a predictor is formed using the coding mode and, if applicable, the motion
vector, and then the residual is computed from the quantized DCT coefficients.
For uncoded blocks, the contents of the co-located block are copied from the7.9. RECONSTRUCTION

125

previous frame and the residual is cleared to zero. Then the predictor andresidual are added, and the result clamped to the range 0 . . . 255 and stored in
the current frame.
In the special case that a block contains only a DC coefficient, the dequantization and inverse DCT transform is skipped. Instead the constant pixel value
for the entire block is computed in one step. Note that the truncation of intermediate operations is omitted and the final rounding is slightly different inthis case. The check for whether or not the block contains only a DC coefficientis based on the coefficient count returned from the token decode procedure ofSection 7.7, and not by checking to see if the remaining coefficient values are
zero. Also note that even when the coefficient count indicates the block contains
zero coefficients, the DC coefficient is still processed, as undoing DC prediction
might have made it non-zero.
After this procedure, the frame is completely reconstructed, but before it
can be used as a reference frame, a loop filter must be run over it to help reduce
blocking artifacts. This is detailed in Section 7.10.
1. Assign qi0 the value QIS[0].
2. For each value of bi from 0 to (NBS − 1):(a) Assign pli the index of the color plane block bi belongs to.
(b) Assign BX the horizontal pixel index of the lower-left corner of blockbi .
(c) Assign BY the vertical pixel index of the lower-left corner of blockbi .
(d) If BCODED[bi ] is non-zero:i. Assign mbi the index of the macro block containing block bi .
ii. If MBMODES[mbi ] is 1 (INTRA), assign qti the value 0.
iii. Otherwise, assign qti the value 1.
iv. Assign rfi the value of the Reference Frame Index column ofTable 7.46 corresponding to MBMODES[mbi ].
v. If rfi is zero, compute PRED using the procedure given in Section 7.9.1.1.
vi. Otherwise:
A. Assign REFP, RPW, and RPH the values given in Table 7.75
corresponding to current value of rfi and pli .
B. Assign MVX the valueb|MVECTS[bi ]x |c ∗ sign(MVECTS[bi ]x ).
C. Assign MVY the valueb|MVECTS[bi ]y |c ∗ sign(MVECTS[bi ]y ).

126

CHAPTER 7. FRAME DECODE
rfi

pli

REFP

RPW

RPH

1
1
1
2
2
2

0
1
2
0
1
2

PREVREFYPREVREFCBPREVREFCRGOLDREFYGOLDREFCBGOLDREFCR

RPYW
RPCW
RPCW
RPYW
RPCW
RPCW

RPYH
RPCH
RPCH
RPYH
RPCH
RPCH

Table 7.75: Reference Planes and Sizes for Each rfi and pli
D. Assign MVX2 the value
d|MVECTS[bi ]x |e ∗ sign(MVECTS[bi ]x ).
E. Assign MVY2 the value
d|MVECTS[bi ]y |e ∗ sign(MVECTS[bi ]y ).
F. If MVX equals MVX2 and MVY equals MVY2, use the values REFP, RPW, RPH, BX, BY, MVX, and MVY, compute
PRED using the procedure given in Section 7.9.1.2.
G. Otherwise, use the values REFP, RPW, RPH, BX, BY,
MVX, MVY, MVX2, and MVY2 to compute PRED using
the procedure given in Section 7.9.1.3.
vii. If NCOEFFS[bi ] is less than 2:
A. Using ACSCALE, DCSCALE, BMS, NQRS,QRSIZES, QRBMIS, qti , pli , and qi0 , use the procedure
given in Section 6.4.3 to compute the DC quantization matrix
QMAT.
B. Assign DC the value(COEFFS[bi ][0] ∗ QMAT[0] + 15) >> 5.
C. Truncate DC to a 16-bit signed representation by dropping
any higher-order bits.
D. For each value of by from 0 to 7, and each value of bx from0 to 7, assign RES[by][bx ] the value DC.
viii. Otherwise:
A. Assign qi the value QIS[QIIS[bi ]].
B. Using ACSCALE, DCSCALE, BMS, NQRS,QRSIZES, QRBMIS, qti , pli , qi0 , and qi , compute DQC
using the procedure given in Section 7.9.2.
C. Using DQC, compute RES using the procedure given in Section 7.9.3.2.

7.10. LOOP FILTERING

127(e) Otherwise:i. Assign rfi the value 1.
ii. Assign REFP, RPW, and RPH the values given in Table 7.75
corresponding to current value of rfi and pli .
iii. Assign MVX the value 0.
iv. Assign MVY the value 0.
v. Using the values REFP, RPW, RPH, BX, BY, MVX, and MVY,
compute PRED using the procedure given in Section 7.9.1.2.
This is simply a copy of the co-located block in the previous
reference frame.
vi. For each value of by from 0 to 7, and each value of bx from 0 to
7, assign RES[by][bx ] the value 0.
(f) For each value of by from 0 to 7, and each value of bx from 0 to 7:
i. Assign P the value (PRED[by][bx ] + RES[by][bx ]).
ii. If P is greater than 255, assign P the value 255.
iii. If P is less than 0, assign P the value 0.
iv. If pli equals 0, assign RECY[BY + by][BX + bx ] the value P.
v. Otherwise, if pli equals 1, assign RECB[BY + by][BX + bx ] thevalue P.
vi. Otherwise, pli equals 2, so assign RECR[BY + by][BX + bx ] thevalue P.

7.10

Loop Filtering

The loop filter is a simple deblocking filter that is based on running a small edge
detecting filter over the coded block edges and adjusting the pixel values by atapered response. The filter response is modulated by the following non-linear
function:0,R ≤ −2 ∗ L −R − 2 ∗ L, −2 ∗ L < R ≤ −L
R,
−L < R < L
lflim(R, L) =


−R
+
2
∗
L,
L≤R<2∗L



0,
2∗L≤R
Here L is a limiting value equal to LFLIMS[qi0 ]. It defines the peaks of thefunction, illustrated in Figure 7.3. LFLIMS is an array of values specified in
the setup header and is indexed by qi0 , the first quantization index for theframe, the one used for all the DC coefficients. Larger values of L indicate astronger filter.

128

CHAPTER 7. FRAME DECODE

lflim
(L,L)

(−2L,0)(2L,0)

R(−L,−L)

Figure 7.3: The loop filter response function.

7.10.1

Horizontal Filter

Input parameters:

Name

Type

RECP

2D Integer
Array

FX

Size
(bits)

Signed?

Description and restrictions

8

No

Integer

20

No

FY

Integer

20

No

L

Integer

7

No

A RPH × RPW array containing
the contents of a plane of the reconstructed frame.
The horizontal pixel index of thelower-left corner of the area to be
filtered.
The vertical pixel index of thelower-left corner of the area to be
filtered.
The loop filter limit value.

Signed?

Description and restrictions

No

A RPH × RPW array containing
the contents of a plane of the reconstructed frame.

Output parameters:

Name

Type

RECP

2D Integer
Array

Variables used:Size(bits)
8

7.10. LOOP FILTERING

129

1. For each value of by from 0 to 7:(a) Assign R the value(RECP[FY + by][FX] − 3 ∗ RECP[FY + by][FX + 1]+
3 ∗ RECP[FY + by][FX + 2] − RECP[FY + by][FX + 3] + 4) >> 3(b) Assign P the value (RECP[FY + by][FX + 1] + lflim(R, L)).
(c) If P is less than zero, assign RECP[FY + by][FX + 1] the value zero.
(d) Otherwise, if P is greater than 255, assign RECP[FY + by][FX + 1]
the value 255.
(e) Otherwise, assign RECP[FY + by][FX + 1] the value P.
(f) Assign P the value (RECP[FY + by][FX + 2] − lflim(R, L)).
(g) If P is less than zero, assign RECP[FY + by][FX + 2] the value zero.
(h) Otherwise, if P is greater than 255, assign RECP[FY + by][FX + 2]
the value 255.
(i) Otherwise, assign RECP[FY + by][FX + 2] the value P.

7.10.2

Vertical Filter

Input parameters:

Name

Type

RECP

2D Integer
Array

FX

Signed?

Description and restrictions

8

No

Integer

20

No

FY

Integer

20

No

L

Integer

7

No

A RPH × RPW array containing
the contents of a plane of the reconstructed frame.
The horizontal pixel index of thelower-left corner of the area to be
filtered.
The vertical pixel index of thelower-left corner of the area to be
filtered.
The loop filter limit value.

Output parameters:

Size(bits)

130

CHAPTER 7. FRAME DECODE

Name

Type

Size
(bits)RECP

2D Integer
Array

Signed?

Description and restrictions

No

A RPH × RPW array containing
the contents of a plane of the reconstructed frame.

8

Variables used:

Name

Type

Size
(bits)

R
P
bx

Integer
Integer
Integer9920Signed?

Description and restrictions

Yes
Yes
No

The edge detector response.
A filtered pixel value.
The horizontal pixel index in the block.

This procedure applies a 4-tap vertical filter to each column of a horizontal
block edge.
1. For each value of bx from 0 to 7:(a) Assign R the value(RECP[FY][FX + bx ] − 3 ∗ RECP[FY + 1][FX + bx ]+3 ∗ RECP[FY + 2][FX + bx ] − RECP[FY + 3][FX + bx ] + 4) >> 3(b) Assign P the value (RECP[FY + 1][FX + bx ] + lflim(R, L)).
(c) If P is less than zero, assign RECP[FY + 1][FX + bx ] the value zero.
(d) Otherwise, if P is greater than 255, assign RECP[FY + 1][FX + bx ]the value 255.
(e) Otherwise, assign RECP[FY + 1][FX + bx ] the value P.
(f) Assign P the value (RECP[FY + 2][FX + bx ] − lflim(R, L)).
(g) If P is less than zero, assign RECP[FY + 2][FX + bx ] the value zero.
(h) Otherwise, if P is greater than 255, assign RECP[FY + 2][FX + bx ]the value 255.
(i) Otherwise, assign RECP[FY + 2][FX + bx ] the value P.

7.10.3Complete Loop Filter

Input parameters:

7.10. LOOP FILTERING

131

Name

Type

Size
(bits)

Signed?

Description and restrictions

LFLIMS
RPYW

Integerarray
Integer

7

No

20

No

Integer

20

No

RPCW

Integer

20

No

RPCH

Integer

20

No

NBS

Integer

36

No

BCODED

Integer
Array

1

No

QIS

Integerarray
2D Integer
Array

6

No

8

No

RECCB

2D Integer
Array

8

No

RECCR

2D Integer
Array

8

No

A 64-element array of loop filter limit values.
The width of the Y 0 plane of
the reconstruced frame in pixels.
The height of the Y 0 plane of
the reconstruced frame in pixels.
The width of the Cb andCr planes of the reconstrucedframe in pixels.
The height of the Cb andCr planes of the reconstrucedframe in pixels.
The total number of blocks ina frame.
An NBS-element array of flags
indicating which blocks arecoded.
An NQIS-element array of qi
values.
A RPYH × RPYW array
containing the contents of theY 0 plane of the reconstructed
frame.
A RPCH × RPCW array
containing the contents of the
Cb plane of the reconstructed
frame.
A RPCH × RPCW array
containing the contents of the
Cr plane of the reconstructed
frame.

RPYH

RECY

Output parameters:

132
Name

CHAPTER 7. FRAME DECODE
Type

Size
(bits)

Signed?

Description and restrictions
A RPYH × RPYW array containing the contents of the Y 0plane of the reconstructed frame.
A RPCH × RPCW array containing the contents of the Cb
plane of the reconstructed frame.
A RPCH × RPCW array containing the contents of the Crplane of the reconstructed frame.

RECY

2D Integer
Array

8

No

RECCB

2D Integer
Array

8

No

RECCR

2D Integer
Array

8

No

Variables used:

Name

Type

Size
(bits)

Signed?

Description and restrictions

RPW

Integer

20

No

Integer

20

No

RECP

2D Integer
Array

8

No

BX

Integer

20

No

BY

Integer

20

No

FX

Integer

20

No

FY

Integer

20

No

L
bi

Integer
Integer

7
36

No
No

bj

Integer

36

No

pli

Integer

2

No

The width of the current plane of
the reconstructed frame in pixels.
The height of the current plane of
the reconstructed frame in pixels.
A RPH × RPW array containing
the contents of the current plane of
the reconstruced frame.
The horizontal pixel index of thelower-left corner of the current
block.
The vertical pixel index of thelower-left corner of the current
block.
The horizontal pixel index of thelower-left corner of the area to be
filtered.
The vertical pixel index of thelower-left corner of the area to be
filtered.
The loop filter limit value.
The index of the current block incoded order.
The index of a neighboring block incoded order.
The color plane index of the current
block.

RPH

7.10. LOOP FILTERING
Name

Type

Size
(bits)

133
Signed?

Description and restrictions

This procedure defines the order that the various block edges are filtered.
Because each application of one of the two filters above destructively modifies
the contents of the reconstructed image, the precise output obtained differs
depending on the order that horizontal and vertical filters are applied to theedges of a single block. The order defined here conforms to that used by VP3.
1. Assign L the value LFLIMS[QIS[0]].
2. For each block in raster order, with coded-order index bi :(a) If BCODED[bi ] is non-zero:i. Assign pli the index of the color plane block bi belongs to.
ii. Assign RECP, RPW, and RPH the values given in Table 7.85
corresponding to the value of pli .
pli

RECP

RPW

RPH

0
1
2

RECY
RECCB
RECCR

RPYW
RPCW
RPCW

RPYH
RPCH
RPCH

Table 7.85: Reconstructed Planes and Sizes for Each pliiii. Assign BX the horizontal pixel index of the lower-left corner ofthe block bi .
iv. Assign BY the vertical pixel index of the lower-left corner of theblock bi .
v. If BX is greater than zero:
A. Assign FX the value (BX − 2).
B. Assign FY the value BY.
C. Using RECP, FX, FY, and L, apply the horizontal block
filter to the left edge of block bi with the procedure describedin Section 7.10.1.
vi. If BY is greater than zero:
A. Assign FX the value BX.
B. Assign FY the value (BY − 2)
C. Using RECP, FX, FY, and L, apply the vertical block filter
to the bottom edge of block bi with the procedure describedin Section 7.10.2.

134

CHAPTER 7. FRAME DECODE
vii. If (BX + 8) is less than RPW and BCODED[bj ] is zero, where
bj is the coded-order index of the block adjacent to bi on theright:
A. Assign FX the value (BX + 6).
B. Assign FY the value BY.
C. Using RECP, FX, FY, and L, apply the horizontal block filter to the right edge of block bi with the procedure describedin Section 7.10.1.
viii. If (BY + 8) is less than RPH and BCODED[bj ] is zero, where
bj is the coded-order index of the block adjacent to bi above:
A. Assign FX the value BX.
B. Assign FY the value (BY + 6)
C. Using RECP, FX, FY, and L, apply the vertical block filter
to the top edge of block bi with the procedure described in
Section 7.10.2.

VP3 Compatibility
The original VP3 decoder implemented unrestricted motion vectors by enlarging
the reconstructed frame buffers and repeating the pixels on its edges into thepadding region. However, for the previous reference frame this padding ocurred
before the loop filter was applied, but for the golden reference frame it occurred
afterwards.
This means that for the previous reference frame, the padding values wererequired to be stored separately from the main image values. Furthermore, even
if the previous and golden reference frames were in fact the same frame, they
could have different padding values. Finally, the encoder did not apply the loop
filter at all, which resulted in artifacts, particularly in near-static scenes, due toprediction-loop mismatch. This last can only be considered a bug in the VP3
encoder.
Given all these things, Theora now uniformly applies the loop filter before
the reference frames are padded. This means it is possible to use the same buffer
for the previous and golden reference frames when they do indeed refer to thesame frame. It also means that on architectures where memory bandwidth islimited, it is possible to avoid storing padding values, and simply clamp the
motion vectors applied to each pixel as described in Sections 7.9.1.2 and 7.9.1.3.
This means that the predicted pixel values along the edges of the frame might
differ slightly between VP3 and Theora, but since the VP3 encoder did not
apply the loop filter in the first place, this is not likely to impose any serious
compatibility issues.

7.11. COMPLETE FRAME DECODE

7.11

135

Complete Frame Decode

Input parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions

FMBW

Integer

16

No

Integer

16

No

NSBS

Integer

32

No

NBS

Integer

36

No

NMBS

Integer

32

No

FRN

Integer

32

No

FRD

Integer

32

No

PARN

Integer

24

No

PARD

Integer

24

No

CS
PF
NOMBR

Integer
Integer
Integer

8
2
24

No
No
No

QUAL
KFGSHIFT

Integer
Integer

6
5

No
No

LFLIMS

Integerarray
Integer
array

7

No

16

No

16

No

The width of the frame inmacro blocks.
The height of the frame
in macro blocks.
The total number of super blocks in a frame.
The total number ofblocks in a frame.
The total number ofmacro blocks in a frame.
The frame-rate numerator.
The frame-rate denominator.
The pixel aspect-ratio
numerator.
The pixel aspect-ratio denominator.
The color space.
The pixel format.
The nominal bitrate of
the stream, in bits per
second.
The quality hint.
The amount to shift the
key frame number by in
the granule position.
A 64-element array ofloop filter limit values.
A 64-element array of
scale values for AC coefficients for each qi value.
A 64-element array of
scale values for the DC
coefficient for each qi
value.

FMBH

ACSCALEDCSCALE

Integer
array

136

CHAPTER 7. FRAME DECODE
Name

Type

Size
(bits)

Signed?

Description and restrictions

NBMS

Integer

10

No

2D Integer
array
2D Integer
array

8

No

6

No

QRSIZES

3D Integer
array

6

No

QRBMIS

3D Integer
array

9

No

HTS

Huffman table array

GOLDREFY

2D Integer
Array

8

No

GOLDREFCB

2D Integer
Array

8

No

GOLDREFCR

2D Integer
Array

8

No

The number of base matrices.
A NBMS×64 array containing the base matrices.
A 2 × 3 array containing the number of quantranges for a given qti andpli , respectively. This is
at most 63.
A 2 × 3 × 63 array of thesizes of each quant range
for a given qti and pli ,respectively. Only the
first NQRS[qti ][pli ] values will be used.
A 2 × 3 × 64 arrayof the bmi ’s used foreach quant range for agiven qti and pli , respectively.
Only the first(NQRS[qti ][pli ] + 1) values will be used.
An 80-element array of
Huffman tables with up
to 32 entries each.
A RPYH × RPYW array containing the contents of the Y 0 planeof the golden reference
frame.
A RPCH × RPCW array containing the contents of the Cb planeof the golden reference
frame.
A RPCH × RPCW array containing the contents of the Cr planeof the golden reference
frame.

BMS
NQRS

7.11. COMPLETE FRAME DECODE
Name

Type

Size
(bits)

137
Signed?

Description and restrictions
A RPYH × RPYW array containing the contents of the Y 0 planeof the previous reference
frame.
A RPCH × RPCW array containing the contents of the Cb planeof the previous reference
frame.
A RPCH × RPCW array containing the contents of the Cr planeof the previous reference
frame.

PREVREFY

2D Integer
Array

8

No

PREVREFCB

2D Integer
Array

8

No

PREVREFCR

2D Integer
Array

8

No

Output parameters:

Name

Type

Size
(bits)

Signed?

Description and restrictions
A RPYH × RPYW array containing the contents of the Y 0 plane of
the reconstructed frame.
A RPCH × RPCW array containing the contents of the Cb plane of
the reconstructed frame.
A RPCH × RPCW array containing the contents of the Cr plane of
the reconstructed frame.
A RPYH × RPYW array containing the contents of the Y 0 planeof the golden reference
frame.

RECY

2D Integer
Array

8

No

RECCB

2D Integer
Array

8

No

RECCR

2D Integer
Array

8

No

GOLDREFY

2D Integer
Array

8

No

138

CHAPTER 7. FRAME DECODE
Name

Type

Size
(bits)

Signed?

Description and restrictions

GOLDREFCB

2D Integer
Array

8

No

2D Integer
Array

8

No

PREVREFY

2D Integer
Array

8

No

PREVREFCB

2D Integer
Array

8

No

PREVREFCR

2D Integer
Array

8

No

A RPCH × RPCW array containing the contents of the Cb planeof the golden reference
frame.
A RPCH × RPCW array containing the contents of the Cr planeof the golden reference
frame.
A RPYH × RPYW array containing the contents of the Y 0 planeof the previous reference
frame.
A RPCH × RPCW array containing the contents of the Cb planeof the previous reference
frame.
A RPCH × RPCW array containing the contents of the Cr planeof the previous reference
frame.

GOLDREFCR

Type

Size
(bits)

Signed?

Description and restrictions

Integer
Integer
Integerarray
Integer
Array

1
2
6

No
No
No

1

No

Integer
Array

3

No

The frame type.
The number of qi values.
An NQIS-element array of qi
values.
An NBS-element array offlags indicating which blocks
are coded.
An NMBS-element array ofcoding modes for each macro
block.

Variables used:

Name
FTYPE
NQIS
QIS
BCODED

MBMODES

7.11. COMPLETE FRAME DECODE
Name
MVECTSQIISCOEFFS

Type
Array
of
2D Integer
Vectors
IntegerArray
2D Integer
Array

Size
(bits)

139

Signed?

Description and restrictions

6

Yes

An NBS-element array of motion vectors for each block.

2

No

16

Yes

An NBS-element array of qii
values for each block.
An NBS × 64 array of quantized DCT coefficient values
for each block in zig-zag order.
An NBS-element array ofthe coefficient count for eachblock.
The width of the Y 0 plane of
the reference frames in pixels.
The height of the Y 0 plane of
the reference frames in pixels.
The width of the Cb and Cr
planes of the reference framesin pixels.
The height of the Cb and Cr
planes of the reference framesin pixels.
The index of the current blockin coded order.

NCOEFFS

Integer
Array

7

No

RPYW

Integer

20

No

RPYH

Integer

20

No

RPCW

Integer

20

No

RPCH

Integer

20

No

bi

Integer

36

No

This procedure uses all the procedures defined in the previous section of thischapter to decode and reconstruct a complete frame. It takes as input values
decoded from the headers, as well as the current reference frames. As output,
it gives the uncropped, reconstructed frame. This should be cropped to picture
region before display. As a special case, a 0-byte packet is treated exactly likean inter frame with no coded blocks.
1. If the size of the data packet is non-zero:(a) Decode the frame header values FTYPE, NQIS, and QIS using theprocedure given in Section 7.1.
(b) Using FTYPE, NSBS, and NBS, decode the list of coded block
flags into BCODED using the procedure given in Section 7.3.
(c) Using FTYPE, NMBS, NBS, and BCODED, decode the macro
block coding modes into MBMODES using the procedure given in
Section 7.4.
(d) If FTYPE is non-zero (inter frame), using PF, NMBS, MBMODES,NBS, and BCODED, decode the motion vectors into MVECTS using
the procedure given in Section 7.5.2.

140

CHAPTER 7. FRAME DECODE
PF

RPCW

RPCH

0
2
3

8 ∗ FMBW
8 ∗ FMBW
16 ∗ FMBW

8 ∗ FMBH
16 ∗ FMBH
16 ∗ FMBH

Table 7.89: Width and Height of Chroma Planes for each Pixel Format(e) Using NBS, BCODED, and NQIS, decode the block-level qi values
into QIIS using the procedure given in Section 7.6.
(f) Using NBS, NMBS, BCODED, and HTS, decode the DCT coefficients into NCOEFFS and NCOEFFS using the procedure given in
Section 7.7.3.
(g) Using BCODED and MBMODES, undo the DC prediction on the
DC coefficients stored in COEFFS using the procedure given in Section 7.8.2.
2. Otherwise:(a) Assign FTYPE the value 1 (inter frame).
(b) Assign NQIS the value 1.
(c) Assign QIS[0] the value 63.
(d) For each value of bi from 0 to (NBS − 1), assign BCODED[bi ] thevalue zero.
3. Assign RPYW and RPYH the values (16 ∗ FMBW) and (16 ∗ FMBH),
respectively.
4. Assign RPCW and RPCH the values from the row of Table 7.89 corresponding to PF.
5. Using ACSCALE, DCSCALE, BMS, NQRS, QRSIZES, QRBMIS,
NBS, BCODED, MBMODES, MVECTS, COEFFS, NCOEFFS, QIS,QIIS, RPYW, RPYH, RPCW, RPCH, GOLDREFY, GOLDREFCB,GOLDREFCR, PREVREFY, PREVREFCB, and PREVREFCR,
reconstruct the complete frame into RECY, RECCB, and RECCR using the procedure given in Section 7.9.4.
6. Using LFLIMS, RPYW, RPYH, RPCW, RPCH, NBS, BCODED, and
QIS, apply the loop filter to the reconstructed frame in RECY, RECCB,
and RECCR using the procedure given in Section 7.10.3.
7. If FTYPE is zero (intra frame), assign GOLDREFY, GOLDREFCB,
and GOLDREFCR the values RECY, RECCB, and RECCR, respectively.

7.11. COMPLETE FRAME DECODE

141

8. Assign PREVREFY, PREVREFCB, and PREVREFCR the values
RECY, RECCB, and RECCR, respectively.

142

CHAPTER 7. FRAME DECODE

Appendix A

Ogg Bitstream
Encapsulation
A.1

Overview

This document specifies the embedding or encapsulation of Theora packets inan Ogg transport stream.
Ogg is a stream oriented wrapper for coded, linear time-based data. It provides syncronization, multiplexing, framing, error detection and seeking landmarks for the decoder and complements the raw packet format used by the
Theora codec.
This document assumes familiarity with the details of the Ogg standard.
The Xiph.Org documentation provides an overview of the Ogg transport stream
format at http://www.xiph.org/ogg/doc/oggstream.html and a detailed description at http://www.xiph.org/ogg/doc/framing.html. The format is also
defined in RFC 3533 [Pfe03]. While Theora packets can be embedded in a wide
variety of media containers and streaming mechanisms, the Xiph.Org Foundation recommends Ogg as the native format for Theora video in file-oriented
storage and transmission contexts.

A.1.1

MIME typeThe generic MIME type of any Ogg file is application/ogg. The specific
MIME type for the Ogg Theora profile documented here is video/ogg. Thisis the MIME type recommended for files conforming to this appendix. The
recommended filename extension is .ogv.
Outside of an encapsulation, the mime type video/theora may be used torefer specifically to the Theora compressed video stream.
143

144

A.2

APPENDIX A. OGG BITSTREAM ENCAPSULATION

Embedding in a logical bitstream

Ogg separates the concept of a logical bitstream consisting of the framing ofa particular sequence of packets and complete within itself from the physicalbitstream which may consist either of a single logical bitstream or a number oflogical bitstreams multiplexed together. This section specifies the embeddingof Theora packets in a logical Ogg bitstream. The mapping of Ogg Theora
logical bitstreams into a multiplexed physical Ogg stream is described in thenext section.

A.2.1

Headers

The initial identification header packet appears by itself in a single Ogg page.
This page defines the start of the logical stream and MUST have the ‘beginningof stream’ flag set.
The second and third header packets (comment metadata and decoder setupdata) can together span one or more Ogg pages. If there are additional nonnormative header packets, they MUST be included in this sequence of pages
as well. The comment header packet MUST begin the second Ogg page in the
logical bitstream, and there MUST be a page break between the last header
packet and the first frame data packet.
These two page break requirements facilitate stream identification and simplify header acquisition for seeking and live streaming applications.
All header pages MUST have their granule position field set to zero.

A.2.2

Frame data

The first frame data packet in a logical bitstream MUST begin a new Ogg page.
All other data packets are placed one at a time into Ogg pages until the end of
the stream. Packets can span pages and multiple packets can be placed within
any one page. The last page in the logical bitstream SHOULD have its ’end of
stream’ flag set to indicate complete transmission of the available video.
Frame data pages MUST be marked with a granule position corresponding
to the end of the display interval of the last frame/packet that finishes in that
page. See the next section for details.

A.2.3

Granule position

Data packets are marked by a granulepos derived from the count of decodable
frames after that packet is processed. The field itself is divided into two sections,
the width of the less significant section being given by the KFGSHIFT parameter decoded from the identification header (Section 6.2). The more significant
portion of the field gives the count of coded frames after the coding of the last
keyframe in stream, and the less significant portion gives the count of frames
since the last keyframe. Thus a stream would begin with a split granulepos ofA.3. MULTIPLEXED STREAM MAPPING

145

1|0 (a keyframe), followed by 1|1, 1|2, 1|3, etc. Around a keyframe in the middle of the stream the granulepos sequence might be 1234|35, 1234|36, 1234|37,
1271|0 (for the keyframe), 1271|1, and so on. In this way the granulepos field increased monotonically as required by the Ogg format, but contains informationnecessary to efficiently find the previous keyframe to continue decoding after aseek.
Prior to bitstream version 3.2.1, data packets were marked by a granulepos
derived from the index of the frame being decoded, rather than the count. Thatis they marked the beginning of the display interval of a frame rather than theend. Such streams have the VREV field of the identification header set to ‘0’instead of ‘1’. They can be interpreted according to the description above byadding 1 to the more signification field of the split granulepos when VREV isless than 1.

A.3

Multiplexed stream mapping

Applications supporting Ogg Theora must support Theora bitstreams multiplexed with compressed audio data in the Vorbis I and Speex formats, andshould support Ogg-encapsulated MNG graphics for overlays.
Multiple audio and video bitstreams may be multiplexed together. How
playback of multiple/alternate streams is handled is up to the application. Some
conventions based on included metadata aide interoperability in this respect.

A.3.1

Chained streams

Ogg Theora decoders and playback applications MUST support both grouped
streams (multiplexed concurrent logical streams) and chained streams (sequential concatenation of independent physical bitstreams).
The number and codec data types of multiplexed streams and the decoder
parameters for those stream types that re-occur can all change at a chaining
boundary. A playback application MUST be prepared to handle such changes
and SHOULD do so smoothly with the minimum possible visible disruption.
The specification of grouped streams below applies independently to each segment of a chained bitstream.

A.3.2

Grouped streams

At the beginning of a multiplexed stream, the ‘beginning of stream’ pages foreach logical bitstream will be grouped together. Within these, the first pageto occur MUST be the Theora page. This facilitates identification of Ogg Theora files among other Ogg-encapsulated content. A playback application mustnevertheless handle streams where this arrangement is not correct.
If there is more than one Theora logical stream, the first page should be fromthe primary stream. That is, the best choice for the stream a generic player
should begin displaying without special user direction. If there is more than

146

APPENDIX A. OGG BITSTREAM ENCAPSULATION

one audio stream, or of any other stream type, the identification page of the
primary stream of that type should be placed before the others.
After the ‘beginning of stream’ pages, the header pages of each of the logicalstreams MUST be grouped together before any data pages occur.
After all the header pages have been placed, the data pages are multiplexed
together. They should be placed in the stream in increasing order by the timeequivalents of their granule position fields. This facilitates seeking while limiting
the buffering requirements of the playback demultiplexer.

Appendix B

VP3
B.1

VP3 Compatibility

This section lists all of the encoder and decoder issues that may affect VP3compatibly. Each is described in more detail in the text itself. This list isprovided merely for reference.
• Bitstream headers (Section 6).
– Identification header (Section 6.2).
∗ Non-multiple of 16 picture sizes.
∗ Standardized color spaces.
∗ Support for 4 : 4 : 4 and 4 : 2 : 2 pixel formats.
– Setup header∗ Loop filter limit values (Section 6.4.1).
∗ Quantization parameters (Section 6.4.2).
∗ Huffman tables (Section 6.4.4).
• Frame header format (Section 7.1).
• Extended long-run bit strings (Section 7.2.1).
• INTER MV FOUR handling of uncoded blocks (Section 7.5.2).
• Block-level qi values (Section 7.6).
• Zero-length EOB runs (Section 7.7.1).
• Unrestricted motion vector padding and the loop filter (Section 7.10.3).
147

148

B.2

APPENDIX B. VP3Loop Filter Limit Values

The hard-coded loop filter limit values used in VP3 are defined as follows:
LFLIMS = {30, 25, 20, 20, 15, 15, 14, 14,
13, 13, 12, 12, 11, 11, 10, 10,9, 9,8, 8, 7, 7,
7, 7,
6, 6,
6, 6, 5, 5,
5, 5,
4, 4,
4,
4, 3, 3,
3, 3,
2, 2,
2,
2, 2, 2,
2,
2,
0, 0,
0,
0, 0, 0,0,
0,0, 0, 0,0, 0, 0, 0,0}

B.3

Quantization Parameters

The hard-coded quantization parameters used by VP3 are defined as follows:

ACSCALE = {500, 450, 400, 370, 340, 310, 285, 265,
245, 225, 210, 195, 185, 180, 170, 160,
150, 145, 135, 130, 125, 115, 110, 107,
100, 96, 93, 89, 85,
82,
75,
74,
70, 68, 64, 60, 57,
56,
52,
50,
49, 45, 44, 43, 40,
38,
37,
35,
33, 32, 30, 29, 28,
25,
24,
22,
21, 19, 18, 17, 15,
13,
12,
10 }
DCSCALE = {220, 200, 190, 180, 170, 170, 160, 160,
150, 150, 140, 140, 130, 130, 120, 120,
110, 110, 100, 100, 90,
90,
90,
80,
80, 80, 70, 70, 70,
60,
60,
60,
60, 50, 50, 50, 50,
40,
40,
40,
40, 40, 30, 30, 30,
30,
30,
30,
30, 20, 20, 20, 20,
20,
20,
20,
20, 10, 10, 10, 10,
10,
10,
10 }

VP3 defines only a single quantization range for each quantization type andcolor plane, and the base matrix used is constant throughout the range. There
are three base matrices defined. The first is used for the Y 0 channel of INTRA
mode blocks, and the second for both the Cb and Cr channels of INTRA mode
blocks. The last is used for INTER mode blocks of all channels.

B.4. HUFFMAN TABLESBMS = { {16,
12,
14,
14,
18,
24,
49,
72,
{17,
18,
24,
47,
99,
99,
99,
99,
{16,
16,
16,
20,
24,
28,
32,
40,

11,
12,
13,
17,
22,
35,
64,
92,
18,
21,
26,
66,
99,
99,
99,
99,
16,
16,
20,
24,
28,
32,
40,
48,

149

10,
14,
16,
22,
37,
55,
78,
95,
24,
26,
56,
99,
99,
99,
99,
99,
16,
20,
24,
28,
32,
40,
48,
64,

16,
24,
40,
19,
26, 58,24, 40, 57,
29, 51, 87,
58, 68, 109,
64, 81, 104,87, 103, 121,
98, 112, 100,
47, 99, 99,
66, 99, 99,
99, 99, 99,
99, 99, 99,
99, 99, 99,
99, 99,
99,
99,
99,
99,
99,
99,
99,
20,
24,
28,
24,
28,
32,
28,
32,
40,
32,
40, 48,40, 48, 64,
48, 64, 64,
64, 64, 64,
64, 64, 96,

51, 61,60, 55,69, 56,80, 62,103, 77,
113, 92,
120, 101,
103,
99 },
99,
99,
99,
99,
99,
99,
99,
99,
99,
99,
99,
99,
99,
99,
99,
99 },
32,
40,
40, 48,48, 64,64, 64,64, 64,64, 96,96, 128,
128, 128 } }The remaining parameters simply assign these matrices to the proper quantranges.
NQRS ={{1, 1, 1}, {1, 1, 1}}
QRSIZES ={{{63}, {63}, {63}}, {{63}, {63}, {63}}}QRBMIS ={{{0, 0}, {1, 1}, {1, 1}}, {{2, 2}, {2, 2}, {2, 2}}}

B.4

Huffman Tables

The following tables contain the hard-coded Huffman codes used by VP3. There
are 80 tables in all, each with a Huffman code for all 32 token values. The tokens
are sorted by the most significant bits of their Huffman code. This is the sameorder in which they will be decoded from the setup header.

150

APPENDIX B. VP3

Huffman CodeToken Value

Huffman CodeToken Value

b000
b001
b01000b010010b0100110b01001110
b010011110
b010011111000
b010011111001
b01001111101
b0100111111
b0101
b0110
b0111
b1000
b1001
b101000
b101001b10101b1011000
b10110010
b101100110
b1011001110
b10110011110
b10110011111
b101101
b10111b1100
b11010b11011
b1110
b1111

20
19
7
30
1
3
28
26
8
6
29
14
12
17
13
21
24
23
16
31
25
2
4
5
27
0
22
18
15
11
10
9

b000
b001
b0100
b0101
b0110
b0111
b10000b100010b10001100
b1000110100000
b1000110100001
b100011010001
b10001101001
b10001101010
b10001101011
b100011011
b1000111
b1001
b1010
b10110b10111
b1100
b1101
b1110
b11110b1111100b1111101b1111110b11111110
b1111111100
b1111111101
b111111111

20
19
11
12
14
17
0
7
3
29
8
26
6
5
28
25
1
13
21
16
22
18
10
9
15
30
23
24
31
4
27
2

VP3.1 Huffman Table Number 0

VP3.1 Huffman Table Number 1

B.4. HUFFMAN TABLES
Huffman Code
b000
b001
b0100
b0101
b0110
b0111
b100000
b1000010
b10000110
b10000111
b10001b1001
b1010
b10110b10111b1100
b11010b11011000
b1101100100
b11011001010
b11011001011
b11011001100
b110110011010
b11011001101100
b11011001101101
b1101100110111
b1101100111
b1101101b1101110b1101111
b1110
b1111

151

Token Value

Huffman CodeToken Value

20
19
11
12
14
17
1
30
2
3
16
21
13
0
22
18
15
31
25
27
6
5
26
29
8
28
4
24
7
23
10
9

b0000
b0001
b0010
b00110b001110b001111
b010
b011
b1000
b1001
b1010
b1011000
b101100100
b1011001010
b1011001011
b1011001100000
b1011001100001
b101100110001
b10110011001
b1011001101
b101100111
b101101
b10111
b1100
b1101
b1110
b1111000
b1111001
b1111010
b11110110
b11110111
b11111

0
17
14
21
7
23
10
9
11
12
20
3
25
6
5
29
8
28
26
27
4
1
16
18
13
19
22
30
24
31
2
15

VP3.1 Huffman Table Number 2

VP3.1 Huffman Table Number 3

152

APPENDIX B. VP3
Huffman CodeToken Value

Huffman CodeToken Value

b0000
b000100000
b000100001
b00010001
b0001001
b000101
b000110b000111000
b0001110010
b0001110011000
b0001110011001
b000111001101
b00011100111
b00011101
b0001111
b0010
b0011
b0100
b0101
b0110
b0111
b100
b101
b110000
b110001b11001b1101
b1110
b111100
b1111010
b1111011
b11111

15
5
25
22
31
24
7
27
6
29
8
28
26
4
2
17
0
14
11
12
19
9
10
21
23
16
18
13
1
3
30
20

b0000
b00010b000110b000111
b0010
b0011
b0100
b0101
b01100b011010000
b011010001
b0110100100000
b0110100100001
b011010010001
b01101001001
b0110100101
b0110100110
b0110100111
b0110101b011011
b0111
b1000
b1001
b101
b110
b11100b1110100b1110101b11101100
b11101101
b1110111
b1111

15
1
7
3
17
19
14
18
20
27
5
29
8
28
26
25
6
22
21
23
12
11
0
9
10
16
2
30
4
31
24
13

VP3.1 Huffman Table Number 4

VP3.1 Huffman Table Number 5

B.4. HUFFMAN TABLES
Huffman Code
b000
b0010
b0011
b010000
b010001b010010b010011000
b010011001
b01001101
b0100111
b0101
b01100b011010b011011b01110b01111
b1000
b1001
b1010
b101100
b1011010
b101101100
b1011011010
b1011011011000
b10110110110010
b10110110110011
b101101101101
b10110110111
b10110111
b10111
b110
b111

153

Token Value
13
17
18
30
24
2
27
6
21
31
14
1
20
3
16
19
12
11
0
23
7
5
25
8
29
22
28
26
4
15
10
9

VP3.1 Huffman Table Number 6

Huffman Codeb00
b01000b01001b010100
b0101010
b01010110
b010101110
b010101111
b01011b0110
b011100
b011101
b01111b1000
b1001
b1010000
b1010001
b1010010000
b101001000100
b1010010001010
b10100100010110
b10100100010111
b10100100011
b101001001
b10100101
b1010011
b10101b10110b10111
b1100
b1101
b111

Token Value
10
3
19
24
7
5
21
6
16
14
23
2
1
11
12
20
4
25
28
8
29
22
26
27
31
30
18
17
15
13
0
9

VP3.1 Huffman Table Number 7

154

APPENDIX B. VP3

Huffman CodeToken Value

Huffman CodeToken Value

b00000b00001
b0001
b0010
b001100
b001101
b00111
b0100
b0101
b0110
b011100
b011101
b01111b100000
b100001b10001b1001000
b10010010
b10010011000
b10010011001
b1001001101
b100100111
b100101b10011
b101
b110
b1110
b111100
b11110100
b11110101
b1111011
b11111

29
7
0
13
26
19
14
24
12
11
17
1
28
18
8
25
20
21
6
5
4
22
15
31
10
9
23
27
3
2
16
30

b0000
b00010b0001100000
b0001100001
b000110001
b00011001
b0001101b000111b0010
b0011
b010000
b010001b01001
b0101
b0110
b0111
b1000000
b1000001
b100001b10001b100100
b100101b10011
b101
b110
b1110
b111100
b11110100
b11110101
b1111011
b111110b111111

30
7
6
5
4
22
3
16
13
24
19
26
14
0
12
11
2
20
17
25
18
15
31
10
9
23
1
21
8
29
28
27

VP3.1 Huffman Table Number 8

VP3.1 Huffman Table Number 9

B.4. HUFFMAN TABLES

155

Huffman CodeToken Value

Huffman CodeToken Value

b0000000
b0000001
b000001b00001b0001
b001000
b001001b00101b00110b00111
b0100
b010100
b010101
b010110b010111
b0110
b0111
b1000
b10010b1001100000
b1001100001
b100110001
b10011001
b1001101b100111b1010
b101100
b101101
b101110b101111
b110
b111

22
8
2
31
24
29
3
25
30
1
23
16
7
19
26
13
12
11
14
6
5
4
21
20
17
0
28
18
27
15
10
9

b000
b0010000
b0010001
b001001b00101b00110b001110b0011110b0011111000
b0011111001
b001111101
b00111111
b0100
b010100
b010101
b010110b010111b0110
b01110b01111b1000
b1001
b1010000
b1010001
b101001b101010b101011b101100
b101101
b10111
b110
b111

0
4
21
30
15
25
29
7
6
5
22
8
23
26
19
16
2
13
1
14
12
11
20
31
17
3
18
27
28
24
10
9

VP3.1 Huffman Table Number 10

VP3.1 Huffman Table Number 11

156

APPENDIX B. VP3

Huffman CodeToken Value

Huffman CodeToken Value

b00
b010
b01100b01101b011100
b011101
b011110b01111100
b01111101
b0111111
b1000
b1001
b101000
b10100100
b1010010100
b1010010101
b101001011
b1010011
b101010b101011b10110b101110b101111b11000b11001b1101000
b1101001
b1101010
b11010110
b11010111
b11011
b111

9
0
14
3
26
18
17
8
21
30
12
11
15
7
6
5
22
4
28
27
24
25
2
1
23
29
19
16
31
20
13
10

b00
b010
b01100b01101b01110b011110b0111110b01111110
b01111111
b1000
b1001
b101000
b101001b101010b101011b10110b101110b1011110000
b1011110001
b101111001
b10111101
b1011111
b11000b1100100b1100101b110011000
b110011001
b11001101
b1100111b11010b11011
b111

9
0
2
14
24
17
29
21
5
12
11
28
4
15
27
23
25
6
22
8
30
19
3
16
26
7
31
20
18
13
1
10

VP3.1 Huffman Table Number 12

VP3.1 Huffman Table Number 13

B.4. HUFFMAN TABLES

157

Huffman CodeToken Value

Huffman CodeToken Value

b00
b010
b0110
b0111
b1000
b1001
b10100b101010b10101100
b10101101
b101011100
b101011101
b101011110
b1010111110
b1010111111
b10110b1011100b1011101b1011110b1011111
b11000b1100100b11001010
b11001011
b110011b110100
b1101010
b1101011
b110110b1101110b1101111
b111

9
0
3
1
12
11
23
15
30
21
7
6
31
22
8
2
5
19
16
26
13
18
29
20
24
14
17
28
4
25
27
10

b00
b01
b1000
b1001
b101000
b101001b101010000
b101010001
b10101001
b101010100000
b101010100001
b10101010001
b1010101001
b101010101
b10101011
b1010110b1010111
b1011
b11000b11001b1101000
b1101001
b1101010
b11010110
b11010111
b11011b111000b11100100
b11100101
b1110011
b11101
b1111

10
9
12
11
15
5
30
29
28
22
8
7
31
21
26
19
16
3
2
4
18
24
17
6
25
13
14
27
20
23
1
0

VP3.1 Huffman Table Number 14

VP3.1 Huffman Table Number 15

158

APPENDIX B. VP3
Huffman Code

b0000
b0001
b0010
b0011
b01000b0100100b0100101b010011b01010b01011
b0110
b0111
b1000
b1001
b1010
b10110b1011100b1011101b10111100b101111010
b10111101100
b1011110110100
b10111101101010
b10111101101011
b101111011011
b1011110111
b1011111
b1100
b1101
b11100b11101b1111

Token Value

Huffman CodeToken Value

15
11
12
21
0
26
1
24
22
30
14
10
9
17
13
23
28
25
27
2
29
5
8
6
4
3
31
20
18
16
7
19

b0000
b0001
b0010
b0011
b010000
b010001b0100100b01001010
b01001011
b010011b0101
b0110
b01110b01111
b1000
b1001
b1010
b1011
b110000
b1100010
b11000110
b110001110000
b110001110001
b110001110010
b110001110011
b1100011101
b110001111
b11001b1101
b11100b11101
b1111

15
7
11
12
1
31
26
27
2
22
17
14
30
0
9
10
20
13
24
25
3
6
5
29
8
4
28
21
18
16
23
19

VP3.1 Huffman Table Number 16

VP3.1 Huffman Table Number 17

B.4. HUFFMAN TABLES

159

Huffman CodeToken Value

Huffman CodeToken Value

b00000b000010b000011
b0001
b0010
b0011
b0100
b0101
b0110
b0111
b1000000
b1000001
b100001b100010b10001100
b10001101
b100011100000
b1000111000010
b1000111000011
b10001110001
b1000111001
b100011101
b10001111
b1001
b1010
b1011
b1100
b11010b11011b1110
b11110b11111

21
25
1
15
20
7
11
12
17
14
3
22
31
24
27
2
6
29
8
5
4
28
26
10
9
19
18
30
0
13
16
23

b0000000
b0000001
b00000100
b000001010000
b000001010001
b00000101001
b0000010101
b000001011
b0000011
b000010b000011
b0001
b0010
b0011
b0100
b0101
b0110
b0111
b100000
b1000010
b1000011
b10001b1001
b1010
b101100
b101101
b10111
b1100
b1101
b1110
b11110b11111

28
27
22
8
6
29
5
4
2
21
1
15
23
7
11
17
12
19
25
26
3
20
18
14
31
24
30
10
9
13
16
0

VP3.1 Huffman Table Number 18

VP3.1 Huffman Table Number 19

160

APPENDIX B. VP3

Huffman CodeToken Value

Huffman CodeToken Value

b0000
b0001
b0010
b0011
b0100
b0101
b0110
b0111000
b0111001
b0111010
b0111011
b011110b011111
b1000
b1001
b1010
b10110b10111000
b1011100100
b10111001010
b1011100101100
b1011100101101
b101110010111
b101110011
b1011101b101111b1100
b11010b110110b110111
b1110
b1111

30
15
17
0
7
18
23
21
27
2
26
25
1
12
11
14
16
28
5
22
8
6
29
4
3
20
13
19
31
24
10
9

b000
b0010
b001100
b0011010
b0011011
b00111
b0100
b01010b01011
b0110
b0111
b1000
b1001
b1010
b10110b101110000
b10111000100
b1011100010100
b1011100010101
b101110001011
b1011100011
b10111001
b1011101b1011110b1011111
b1100
b11010b110110b110111b11100b11101
b1111

9
30
3
28
27
31
7
24
19
0
12
11
14
23
16
21
6
22
8
29
5
4
2
20
26
13
18
25
1
17
15
10

VP3.1 Huffman Table Number 20

VP3.1 Huffman Table Number 21

B.4. HUFFMAN TABLES

161

Huffman CodeToken Value

Huffman CodeToken Value

b000
b001
b01000b01001b010100
b010101
b01011b01100b01101b0111
b10000b100010b1000110000
b100011000100
b1000110001010
b1000110001011
b10001100011
b100011001
b10001101
b1000111
b1001
b1010
b1011
b1100
b1101
b11100b11101b11110000
b11110001
b1111001
b111101b11111

10
9
18
25
26
19
1
31
17
14
24
3
6
8
22
21
29
5
20
27
12
11
13
0
23
15
7
4
28
2
16
30

b000
b001
b010
b01100b011010b011011b0111
b10000b100010b1000110b1000111
b1001
b1010
b10110b10111b11000b110010b110011b11010b11011b1110
b11110000
b1111000100000
b1111000100001
b1111000100010
b1111000100011
b11110001001
b1111000101
b111100011
b1111001
b111101b11111

0
10
9
3
27
16
13
31
17
4
28
11
12
24
7
25
26
2
1
14
23
19
20
8
22
21
29
6
5
18
15
30

VP3.1 Huffman Table Number 22

VP3.1 Huffman Table Number 23

162

APPENDIX B. VP3

Huffman CodeToken Value

Huffman CodeToken Value

b000
b0010
b0011
b01000b010010b0100110b01001110
b010011110
b01001111100
b0100111110100
b0100111110101
b010011111011
b0100111111
b0101
b01100b01101b011100
b011101
b01111
b1000
b1001
b1010
b1011
b1100000
b1100001
b110001b11001b1101
b111000b111001b11101
b1111

9
24
7
17
19
20
2
3
4
6
5
22
21
14
25
15
27
29
28
30
13
12
11
8
1
16
31
23
18
26
0
10

b000
b001
b010000
b0100010
b010001100000
b010001100001
b01000110001
b0100011001
b010001101
b01000111
b01001b0101
b011000
b011001
b01101
b0111
b1000
b1001
b10100b1010100b10101010
b10101011
b101011b1011
b1100
b110100
b110101b11011b1110
b111100
b111101b11111

10
9
27
20
6
5
22
4
21
8
25
14
19
1
15
0
30
13
31
29
3
2
26
12
11
28
16
7
23
18
17
24

VP3.1 Huffman Table Number 24

VP3.1 Huffman Table Number 25

B.4. HUFFMAN TABLES

163

Huffman CodeToken Value

Huffman CodeToken Valueb000
b001000
b0010010
b001001100000
b001001100001
b00100110001
b0010011001
b001001101
b00100111
b00101b00110b00111
b0100
b010100
b010101
b01011b0110
b011100
b011101
b01111
b1000
b1001
b1010
b101100
b1011010
b1011011
b10111b1100
b11010b11011
b1110
b1111

9
2
8
22
6
5
21
4
20
1
15
26
24
29
18
28
13
16
27
25
30
12
11
17
19
3
31
0
7
14
23
10

b0000
b0001
b001
b010
b011
b10000b10001b100100
b10010100000
b100101000010
b100101000011
b1001010001
b100101001
b10010101
b1001011
b10011b1010
b101100
b101101
b10111b11000b11001000
b11001001
b1100101b110011b11010b11011b11100b1110100b1110101b111011
b1111

12
11
10
9
23
7
14
3
6
22
21
5
20
4
18
1
24
15
29
28
26
8
19
16
27
13
30
25
17
2
31
0

VP3.1 Huffman Table Number 26

VP3.1 Huffman Table Number 27

164

APPENDIX B. VP3

Huffman CodeToken Value

Huffman CodeToken Value

b000
b001
b0100
b0101000
b0101001
b0101010
b0101011
b01011
b011
b100
b1010
b101100
b101101
b10111b11000b11001b11010b110110b110111b111000b11100100
b1110010100000
b1110010100001
b111001010001
b11100101001
b1110010101
b111001011
b1110011
b111010b111011b11110b11111

10
9
25
4
18
16
17
28
0
23
24
29
2
13
26
30
1
27
7
3
8
22
21
6
20
5
19
15
14
31
12
11

b000
b001
b0100
b01010b010110b010111
b011
b100
b1010
b10110b10111b11000b110010b110011b11010b11011b11100b1110100b1110101b111011b11110b11111000
b11111001
b111110100000
b1111101000010
b1111101000011
b11111010001
b1111101001
b111110101
b111110110
b111110111
b111111

10
9
1
13
29
7
23
0
24
30
3
28
14
31
12
11
26
15
4
27
25
16
17
20
22
21
6
19
5
8
18
2

VP3.1 Huffman Table Number 28

VP3.1 Huffman Table Number 29

B.4. HUFFMAN TABLES

165

Huffman CodeToken Value

b000
b001
b010
b0110000000
b01100000010
b011000000110
b011000000111
b011000001
b01100001
b0110001
b011001
b01101
b0111
b100
b1010
b10110b1011100b10111010
b101110110
b101110111
b101111b11000b11001b11010b110110b110111b11100b111010b1110110b1110111b11110b11111

10
9
23
19
20
22
21
18
17
5
14
30
1
0
24
28
15
16
8
6
31
2
12
11
4
27
26
13
29
7
3
25

VP3.1 Huffman Table Number 30

Huffman Code
b000
b001
b010
b0110
b0111000
b0111001000
b0111001001000
b0111001001001
b0111001001010
b01110010010110
b01110010010111
b01110010011
b011100101
b01110011
b011101
b01111b100
b1010
b10110b101110b1011110b1011111
b1100
b11010b11011b111000b111001b11101b1111000
b1111001
b111101b11111

Token Value
0
10
9
24
29
17
22
21
18
20
19
8
16
15
27
12
23
1
11
13
7
14
3
2
26
28
5
4
6
31
30
25

VP3.1 Huffman Table Number 31

166

APPENDIX B. VP3

Huffman CodeToken Value

Huffman CodeToken Value

b00000b000010b000011
b0001
b0010
b0011
b0100
b010100
b01010100
b010101010
b010101011
b0101011
b01011
b0110
b0111
b1000
b1001
b1010
b1011
b1100
b11010b1101100b11011010
b110110110000
b110110110001
b11011011001
b1101101101
b110110111
b110111b11100b11101
b1111

24
28
21
23
7
15
17
25
2
22
8
1
0
19
11
12
9
10
18
14
20
26
27
6
5
4
29
3
31
30
16
13

b0000
b000100
b000101
b00011
b0010
b0011
b0100
b0101
b01100b0110100b01101010
b01101011
b011011
b0111
b1000
b1001
b1010
b101100
b1011010
b10110110
b1011011100000
b1011011100001
b101101110001
b10110111001
b1011011101
b101101111
b10111b1100
b1101
b11100b11101
b1111

30
1
28
24
17
15
18
23
31
27
3
21
25
7
12
11
14
20
26
2
6
5
22
4
29
8
16
9
10
19
0
13

VP3.1 Huffman Table Number 32

VP3.1 Huffman Table Number 33

B.4. HUFFMAN TABLES

167

Huffman CodeToken Value

Huffman CodeToken Value

b000
b0010
b0011
b0100
b01010b01011b0110
b0111
b1000000
b10000010
b1000001100
b100000110100
b1000001101010
b1000001101011
b10000011011
b100000111
b100001b10001b1001
b10100000
b10100001
b1010001
b101001b10101
b1011
b1100
b1101
b1110
b11110b111110b1111110b1111111

13
15
0
30
24
31
23
7
20
8
4
5
22
6
21
29
28
16
14
3
2
27
25
18
11
12
10
9
17
19
26
1

b0000
b00010b00011b001
b010
b01100b011010b011011b0111
b1000
b10010b10011
b1010
b1011
b1100
b1101
b11100b11101000000
b111010000010
b1110100000110
b1110100000111
b1110100001
b111010001
b11101001
b1110101b111011b111100
b1111010
b11110110
b111101110
b111101111
b11111

30
18
16
9
10
31
26
1
0
14
17
24
23
11
12
13
15
5
6
22
21
4
20
3
19
25
28
27
2
29
8
7

VP3.1 Huffman Table Number 34

VP3.1 Huffman Table Number 35

168

APPENDIX B. VP3

Huffman CodeToken Value

Huffman CodeToken Value

b0000
b0001
b001
b010
b01100b011010b0110110000
b01101100010
b011011000110
b0110110001110
b0110110001111
b011011001
b01101101
b0110111
b01110b01111b100000
b1000010
b10000110
b10000111
b10001b100100
b100101b10011
b1010
b1011
b1100
b1101
b1110
b111100
b111101b11111

30
14
9
10
25
18
20
5
6
22
21
4
29
3
31
15
27
2
8
19
28
26
16
24
13
12
11
0
23
17
1
7

b000
b0010
b00110b00111
b010
b011
b1000
b10010b10011b101000
b10100100
b10100101
b1010011000
b1010011001000
b1010011001001
b1010011001010
b1010011001011
b10100110011
b101001101
b10100111
b101010b101011b1011
b1100
b11010b11011b11100b1110100b1110101b1110110b1110111
b1111

0
30
31
25
9
10
13
1
7
27
29
8
19
20
6
22
21
5
4
18
26
15
11
12
14
28
24
17
16
2
3
23

VP3.1 Huffman Table Number 36

VP3.1 Huffman Table Number 37

B.4. HUFFMAN TABLES

169

Huffman CodeToken Value

Huffman CodeToken Valueb000
b00100b00101b00110b00111
b010
b011
b100
b101000000
b101000001000
b101000001001
b101000001010
b1010000010110
b1010000010111
b1010000011
b10100001
b10100010
b10100011
b101001b101010b101011b1011
b1100
b11010b11011b11100b111010b11101100
b11101101
b1110111b11110b11111

23
7
31
14
25
0
10
9
18
22
21
6
20
19
5
8
17
16
27
26
2
11
12
1
30
28
3
29
4
15
24
13

b000
b0010
b00110b00111000
b001110010
b001110011000
b0011100110010
b0011100110011
b0011100110100
b0011100110101
b001110011011
b00111001110
b00111001111
b0011101b001111
b010
b0110
b0111
b100
b101
b11000b11001b110100
b110101b11011b111000b11100100
b11100101
b1110011
b11101b11110b11111

23
1
13
15
8
18
20
19
22
21
17
16
6
7
27
0
11
12
9
10
2
30
26
4
25
31
5
29
14
3
28
24

VP3.1 Huffman Table Number 38

VP3.1 Huffman Table Number 39

170

APPENDIX B. VP3
Huffman Code

b000
b001
b01000b01001
b0101
b0110
b011100
b011101
b01111b1000
b1001
b1010000
b1010001
b101001b10101b10110b10111000
b101110010
b1011100110000
b1011100110001
b1011100110010
b10111001100110
b10111001100111
b10111001101
b1011100111
b1011101b101111b1100
b1101
b11100b11101b1111

Token Value

Huffman CodeToken Value

10
9
26
15
24
7
16
17
25
30
13
1
8
27
31
0
19
2
22
21
4
6
5
20
3
18
29
12
11
14
28
23

b000
b001
b0100
b0101
b0110
b0111
b1000000
b1000001
b100001b10001b1001
b10100b101010b1010110000
b1010110001000
b1010110001001
b1010110001010
b1010110001011
b10101100011
b101011001
b10101101
b1010111b10110b101110b1011110b1011111
b1100
b1101
b11100b111010b111011
b1111

9
23
28
24
13
30
2
18
1
14
0
25
15
4
6
5
22
21
20
19
3
16
31
27
17
8
12
11
7
29
26
10

VP3.1 Huffman Table Number 40

VP3.1 Huffman Table Number 41

B.4. HUFFMAN TABLES

171

Huffman CodeToken Value

b000
b0010
b0011000
b001100100
b001100101000
b001100101001
b001100101010
b0011001010110
b0011001010111
b0011001011
b00110011
b001101
b00111b010
b0110
b01110b01111b10000b1000100b1000101b1000110b1000111
b1001
b1010
b1011
b11000b11001b11010b110110b110111
b1110
b1111

9
30
17
4
22
21
5
20
6
19
18
8
1
23
24
26
29
31
16
3
2
15
28
11
12
7
25
13
14
27
0
10

VP3.1 Huffman Table Number 42

Huffman Code
b000
b001
b010
b011
b10000b100010b100011b1001
b10100b10101b10110b10111b11000b1100100b110010100
b11001010100
b1100101010100
b1100101010101
b1100101010110
b11001010101110
b11001010101111
b1100101011
b110010110
b110010111
b110011b1101
b11100b111010b1110110b1110111b11110b11111

Token Value
23
10
9
0
27
14
2
24
13
26
30
29
1
15
4
19
22
21
5
20
6
18
17
16
31
28
25
7
8
3
12
11

VP3.1 Huffman Table Number 43

172

APPENDIX B. VP3
Huffman Code

b000
b001
b010
b0110
b0111
b10000b10001b1001000
b10010010
b100100110
b1001001110
b10010011110
b10010011111000
b10010011111001
b10010011111010
b100100111110110
b100100111110111
b100100111111
b100101b10011b101
b11000b110010b1100110b1100111b110100
b110101b11011b1110
b11110b111110b111111

Token Value
23
10
9
1
24
3
26
4
15
16
17
18
22
21
6
20
19
5
31
29
0
25
7
14
8
13
30
11
28
12
2
27

VP3.1 Huffman Table Number 44

Huffman Code
b000
b001
b010
b0110
b011100
b01110100
b011101010
b0111010110
b0111010111000
b0111010111001
b01110101110100
b01110101110101
b01110101110110
b01110101110111
b01110101111
b0111011
b011110b011111b1000
b10010b10011b101
b11000b110010b1100110b1100111b11010b11011b11100b111010b111011b1111

Token Value
28
9
10
24
4
15
5
16
22
21
18
6
20
19
17
14
7
13
1
2
25
0
29
30
8
31
12
11
3
27
26
23

VP3.1 Huffman Table Number 45

B.4. HUFFMAN TABLES

173

Huffman CodeToken Value

Huffman CodeToken Value

b000
b001
b010
b011000
b011001
b01101b01110b01111b100
b1010
b10110b10111b1100
b110100000
b11010000100
b110100001010
b1101000010110
b1101000010111
b11010000110
b1101000011100
b1101000011101
b110100001111
b11010001
b1101001
b110101b11011b111000b1110010
b11100110
b11100111
b11101
b1111

28
10
9
13
30
4
25
29
0
1
12
11
3
15
6
18
20
19
16
22
21
17
14
31
26
2
27
7
5
8
24
23

b000
b00100b001010000
b001010001
b0010100100
b001010010100
b0010100101010
b0010100101011
b0010100101100
b0010100101101
b0010100101110
b0010100101111
b001010011
b0010101b001011
b0011
b010
b011
b100
b101000
b101001b10101b10110b101110b10111100b10111101
b1011111
b1100
b11010b11011
b1110
b1111

3
25
14
6
15
16
18
17
20
19
22
21
8
13
29
4
10
0
9
26
27
12
11
5
7
31
30
1
24
2
23
28

VP3.1 Huffman Table Number 46

VP3.1 Huffman Table Number 47

174

APPENDIX B. VP3

Huffman CodeToken Value

Huffman CodeToken Valueb000
b001000
b001001b0010100b0010101b001011b0011
b0100
b01010b01011b01100b01101
b0111
b1000
b1001
b10100b101010b101011b1011
b1100
b11010000
b1101000100
b110100010100
b1101000101010
b1101000101011
b11010001011
b110100011
b1101001
b110101b11011
b1110
b1111

9
29
1
20
8
26
0
7
16
24
31
18
30
23
14
17
19
25
11
12
2
4
5
22
6
21
3
27
28
15
13
10

b000
b001
b0100
b010100
b010101
b01011b0110000
b011000100000
b011000100001
b011000100010
b011000100011
b0110001001
b011000101
b01100011
b0110010
b0110011
b01101b0111
b10000b100010b100011b10010b100110b100111
b1010
b1011
b1100
b1101
b1110
b111100
b111101b11111

10
9
14
18
27
28
3
6
5
22
21
20
4
19
2
8
15
30
31
26
29
24
16
17
0
23
13
12
11
1
25
7

VP3.1 Huffman Table Number 48

VP3.1 Huffman Table Number 49

B.4. HUFFMAN TABLES

175

Huffman CodeToken Value

Huffman CodeToken Value

b000
b001
b010000
b01000100
b0100010100
b010001010100
b010001010101
b010001010110
b010001010111
b010001011
b0100011
b01001b01010b010110b010111b01100b01101b0111
b100000
b1000010
b1000011
b10001b1001
b101000
b101001b10101b1011
b11000b11001
b1101
b1110
b1111

10
9
3
4
5
20
6
22
21
19
8
15
25
17
16
1
28
30
27
18
2
31
13
29
26
24
23
7
14
12
11
0

b0000000
b0000001
b000001b00001b00010b00011
b001
b010
b011
b1000
b10010b10011b10100000
b10100001000
b1010000100100
b1010000100101
b1010000100110
b1010000100111
b1010000101
b101000011
b1010001
b101001b101010b101011b1011
b1100
b11010b110110b110111b11100b11101
b1111

8
17
15
31
7
25
0
9
10
13
14
28
4
19
20
6
22
21
5
18
16
2
3
27
12
11
1
29
26
24
30
23

VP3.1 Huffman Table Number 50

VP3.1 Huffman Table Number 51

176

APPENDIX B. VP3

Huffman CodeToken Valueb000
b00100b00101000
b0010100100
b00101001010
b0010100101100
b0010100101101
b0010100101110
b0010100101111
b001010011
b00101010
b00101011
b0010110b0010111
b00110b00111
b010
b011
b100
b10100b10101b1011
b1100
b110100
b110101b110110b110111b11100b11101b111100
b111101b11111

23
26
17
18
6
20
19
22
21
5
8
16
4
15
3
25
9
10
0
28
30
11
12
7
27
29
14
13
24
31
2
1

VP3.1 Huffman Table Number 52

Huffman Codeb000
b001000
b001001b00101b00110b00111
b010
b011
b100
b1010
b101100
b101101
b10111b1100
b1101
b111000b111001b11101b11110b111110000
b1111100010000
b1111100010001
b1111100010010
b11111000100110
b11111000100111
b11111000101
b11111000110
b11111000111
b111110010
b111110011
b1111101b111111

Token Value
23
7
4
30
25
2
10
9
0
1
29
31
13
12
11
27
26
3
24
8
22
21
18
20
19
17
16
6
15
5
14
28

VP3.1 Huffman Table Number 53

B.4. HUFFMAN TABLES

177

Huffman CodeToken Valueb000
b001000
b0010010
b00100110
b0010011100000
b0010011100001
b0010011100010
b0010011100011
b0010011100100
b0010011100101
b0010011100110
b0010011100111
b0010011101
b001001111
b00101b0011
b010
b01100b0110100b0110101b011011
b0111
b100
b101
b11000b110010b110011b1101
b1110
b111100
b111101b11111

23
31
7
14
20
19
22
21
16
8
18
17
15
6
4
3
0
25
29
5
30
1
10
9
2
28
13
11
12
27
26
24

VP3.1 Huffman Table Number 54

Huffman Code
b000
b0010
b00110b00111
b0100
b01010b0101100b0101101b010111
b011
b100
b101
b1100
b1101
b11100b11101000
b1110100100
b1110100101000
b1110100101001
b1110100101010
b11101001010110
b11101001010111
b111010010110
b11101001011100
b11101001011101
b11101001011110
b11101001011111
b111010011
b1110101b1110110b1110111b1111

Token Value
0
4
24
5
1
25
26
31
27
23
10
9
12
11
2
7
30
22
21
8
16
15
14
18
17
20
19
29
6
28
13
3

VP3.1 Huffman Table Number 55

178

APPENDIX B. VP3

Huffman CodeToken Value

b00000b00001
b0001
b001
b010
b0110
b0111
b100000
b100001000000
b100001000001
b100001000010
b1000010000110
b1000010000111
b1000010001
b100001001
b10000101
b1000011
b10001b100100
b100101b10011b1010
b10110b101110b1011110b10111110
b10111111
b11000b11001
b1101
b1110
b1111

26
29
24
9
10
30
13
8
22
21
5
20
6
4
19
3
17
25
1
15
14
0
31
27
16
18
2
7
28
12
11
23

VP3.1 Huffman Table Number 56

Huffman Code
b000
b001
b010
b0110
b01110b01111b1000
b10010b10011b1010
b1011
b1100000
b1100001
b110001b11001b11010b110110b11011100
b1101110100
b1101110101000
b11011101010010
b11011101010011
b11011101010100
b11011101010101
b1101110101011
b11011101011
b110111011
b1101111
b1110
b11110b111110b111111

Token Value
9
10
0
24
26
1
28
7
25
11
12
15
3
14
30
13
8
16
4
5
20
6
22
21
19
18
17
2
23
29
27
31

VP3.1 Huffman Table Number 57

B.4. HUFFMAN TABLES
Huffman Code
b000
b001
b01000b01001b01010b01011b011
b1000
b100100
b100101b10011
b1010
b1011
b1100
b1101
b11100b111010b11101100
b111011010
b1110110110
b11101101110
b11101101111000
b11101101111001
b1110110111101
b11101101111100
b111011011111010
b111011011111011
b1110110111111
b1110111b111100
b111101b11111

179

Token Value

Huffman CodeToken Value

9
10
27
30
26
13
0
29
3
2
25
12
11
28
23
1
31
15
4
16
17
22
21
5
6
20
19
18
14
7
8
24

b0000
b0001
b00100b00101
b0011
b010
b011
b10000b100010b1000110b100011100
b1000111010000
b1000111010001
b1000111010010
b1000111010011
b10001110101
b1000111011000
b1000111011001
b100011101101
b10001110111
b10001111
b10010b100110b100111
b101
b1100
b1101
b1110
b1111000
b1111001
b111101b11111

12
11
2
26
1
9
10
3
30
14
15
18
6
20
19
5
22
21
17
16
4
25
13
8
0
28
23
29
31
7
27
24

VP3.1 Huffman Table Number 58

VP3.1 Huffman Table Number 59

180

APPENDIX B. VP3
Huffman Codeb0000
b00010b000110b0001110b0001111
b001
b010
b011
b1000
b1001
b101
b1100
b110100
b110101b11011b11100b11101b11110b111110000
b1111100010
b11111000110
b11111000111000
b11111000111001
b11111000111010
b11111000111011
b11111000111100
b11111000111101
b11111000111110
b11111000111111
b11111001
b1111101b111111

Token Value
3
25
4
30
7
29
10
9
23
28
0
1
8
27
2
24
12
11
14
5
15
20
19
22
21
16
6
18
17
31
13
26

VP3.1 Huffman Table Number 60

Huffman Code
b0000
b0001
b001
b0100000
b01000010
b01000011
b010001b01001b0101
b01100b01101b011100000
b0111000010
b0111000011000
b0111000011001
b0111000011010
b0111000011011
b0111000011100
b0111000011101
b0111000011110
b01110000111110
b01110000111111
b01110001
b0111001
b011101
b011110b011111
b100
b1010
b1011
b110
b111

Token Value
23
2
29
13
31
30
27
24
28
12
11
5
14
18
17
20
19
22
21
6
16
15
7
8
25
4
26
0
3
1
10
9

VP3.1 Huffman Table Number 61

B.4. HUFFMAN TABLES
Huffman Codeb00
b010
b01100b011010b011011b0111
b100
b10100b101010b101011b101100
b1011010
b101101100
b1011011010000
b1011011010001
b1011011010010
b1011011010011
b10110110101
b1011011011000
b1011011011001
b10110110110100
b10110110110101
b10110110110110
b10110110110111
b10110110111
b101101110
b1011011110
b1011011111
b10111
b1100
b1101
b111

181

Token Value
9
3
23
27
26
2
0
4
24
12
11
25
5
14
6
16
15
31
22
21
18
17
20
19
30
8
13
7
28
29
1
10

VP3.1 Huffman Table Number 62

Huffman Code
b00
b01
b10
b1100
b1101000
b1101001
b110101000
b110101001
b11010101
b110101100
b1101011010
b1101011011000
b11010110110010
b11010110110011
b11010110110100
b11010110110101
b11010110110110
b11010110110111
b11010110111000
b11010110111001
b11010110111010
b11010110111011
b11010110111100
b11010110111101
b11010110111110
b11010110111111
b11010111
b11011b11100b111010b111011b1111

Token Value
10
9
0
3
12
11
24
23
27
5
25
6
8
7
22
21
31
30
18
17
20
19
14
13
16
15
26
29
2
28
4
1

VP3.1 Huffman Table Number 63

182

APPENDIX B. VP3

Huffman CodeToken Value

Huffman CodeToken Value

b000
b0010
b0011
b010
b011
b10000b10001b10010b10011b10100b1010100b101010100
b101010101000
b1010101010010
b1010101010011
b1010101010100
b1010101010101
b101010101011
b1010101011
b10101011
b101011
b1011
b1100
b1101
b1110000b1110001
b1110010
b1110011
b11101b11110b111110b111111

0
28
13
9
10
1
14
25
31
7
16
4
6
20
19
22
21
5
18
17
27
12
11
23
8
3
2
15
30
24
26
29

b00000b00001b00010b0001100
b000110100000
b000110100001
b0001101000100
b0001101000101
b0001101000110
b0001101000111
b0001101001
b0001101010
b0001101011
b00011011
b000111
b001
b010
b011
b1000
b10010b10011b101000
b101001b10101b1011
b1100
b11010b11011b1110
b111100
b111101b11111

26
31
7
4
22
21
18
6
20
19
5
17
16
15
14
10
9
0
28
25
30
8
2
13
23
12
24
29
11
27
3
1

VP3.1 Huffman Table Number 64

VP3.1 Huffman Table Number 65

B.4. HUFFMAN TABLES

183

Huffman CodeToken Value

Huffman CodeToken Value

b000
b001
b0100
b0101
b01100b01101b0111
b100
b10100b101010b1010110b101011100
b1010111010000
b1010111010001
b1010111010010
b1010111010011
b1010111010100
b1010111010101
b1010111010110
b1010111010111
b1010111011
b10101111
b1011
b110000
b110001b11001b1101
b1110
b111100
b111101b111110b111111

9
10
1
29
13
25
28
0
3
8
4
5
20
19
22
21
16
6
18
17
15
14
23
31
27
24
12
11
7
30
26
2

b0000
b000100000000
b000100000001
b000100000010
b000100000011
b000100000100
b000100000101
b000100000110
b0001000001110
b0001000001111
b000100001
b00010001
b0001001
b0001010
b0001011
b00011
b0010
b0011
b010
b011
b1000
b1001
b101
b1100
b11010b110110b1101110b1101111
b1110
b11110b111110b111111

3
18
17
20
19
22
21
6
16
15
14
5
31
7
30
25
12
11
9
10
1
28
0
23
2
4
8
13
29
24
26
27

VP3.1 Huffman Table Number 66

VP3.1 Huffman Table Number 67

184

APPENDIX B. VP3
Huffman Codeb000
b00100b0010100b00101010
b0010101100
b0010101101
b0010101110000
b0010101110001
b0010101110010
b0010101110011
b0010101110100
b0010101110101
b0010101110110
b00101011101110
b00101011101111
b0010101111
b001011
b0011
b010
b011
b100
b1010
b10110b10111b1100
b11010b110110b1101110b1101111
b1110
b11110b11111

Token Value
29
25
8
13
31
6
18
17
20
19
22
21
14
16
15
7
27
23
0
10
9
28
24
12
3
11
26
5
30
1
2
4

VP3.1 Huffman Table Number 68

Huffman Code
b000
b001
b0100
b0101
b011
b100
b101000
b101001000
b1010010010000
b1010010010001
b1010010010010
b1010010010011
b1010010010100
b1010010010101
b1010010010110
b1010010010111
b10100100110
b101001001110
b10100100111100
b10100100111101
b10100100111110
b10100100111111
b10100101
b10100110
b10100111
b10101b101100
b101101
b101110b101111b110
b111

Token Value
23
3
4
1
2
0
24
26
17
16
19
18
13
7
15
14
6
30
21
20
31
22
25
8
27
29
12
11
28
5
10
9

VP3.1 Huffman Table Number 69

B.4. HUFFMAN TABLES
Huffman Code
b000
b001
b0100
b0101
b011
b100
b101000
b101001000
b1010010010000
b1010010010001
b1010010010010
b1010010010011
b1010010010100
b1010010010101
b1010010010110
b1010010010111
b10100100110
b101001001110
b10100100111100
b10100100111101
b10100100111110
b10100100111111
b10100101
b10100110
b10100111
b10101b101100
b101101
b101110b101111
b110
b111

185

Token Value
23
3
4
1
2
0
24
26
17
16
19
18
13
7
15
14
6
30
21
20
31
22
25
8
27
29
12
11
28
5
10
9

VP3.1 Huffman Table Number 70

Huffman Code
b000
b001
b0100
b0101
b011
b100
b101000
b101001000
b1010010010000
b1010010010001
b1010010010010
b1010010010011
b1010010010100
b1010010010101
b1010010010110
b1010010010111
b10100100110
b101001001110
b10100100111100
b10100100111101
b10100100111110
b10100100111111
b10100101
b10100110
b10100111
b10101b101100
b101101
b101110b101111b110
b111

Token Value
23
3
4
1
2
0
24
26
17
16
19
18
13
7
15
14
6
30
21
20
31
22
25
8
27
29
12
11
28
5
10
9

VP3.1 Huffman Table Number 71

186

APPENDIX B. VP3

Huffman CodeToken Value

b000
b001
b0100
b01010b01011b011
b100000
b1000010
b100001100000
b1000011000010
b1000011000011
b1000011000100
b1000011000101
b100001100011
b1000011001
b100001101
b100001110
b100001111
b10001
b1001
b1010
b1011
b11000b11001b11010b11011b111000b111001b1110100b1110101b111011
b1111

10
9
24
7
26
0
2
15
6
20
19
22
21
5
18
4
17
16
1
28
12
11
13
25
30
29
14
27
3
8
31
23

VP3.1 Huffman Table Number 72

Huffman Codeb00000b00001
b0001
b001
b010
b0110
b01110b011110b011111
b1000
b1001
b101
b1100
b1101
b1110000b11100010
b1110001100
b11100011010
b11100011011000
b11100011011001
b11100011011010
b11100011011011
b11100011011100
b11100011011101
b1110001101111
b111000111
b111001b11101b111100
b111101b111110b111111

Token Value
13
3
1
10
9
29
25
31
8
12
11
0
28
23
14
4
16
17
18
6
20
19
22
21
5
15
7
24
27
30
2
26

VP3.1 Huffman Table Number 73

B.4. HUFFMAN TABLES
Huffman Codeb000000
b000001b00001
b0001
b001
b010
b0110
b0111
b100000
b100001b10001
b1001
b1010
b1011
b110
b11100b1110100b111010100
b1110101010
b1110101011000
b1110101011001
b1110101011010
b1110101011011
b1110101011100
b11101010111010
b11101010111011
b111010101111
b11101011
b111011b11110b111110b111111187

Token Value
31
7
25
28
9
10
12
11
30
8
2
29
23
1
0
24
4
15
5
20
19
22
21
6
18
17
16
14
27
3
13
26

VP3.1 Huffman Table Number 74

Huffman Code
b0000
b0001
b00100b001010b0010110b0010111
b0011
b0100
b01010b010110b010111
b0110
b0111
b100
b1010
b101100
b10110100
b101101010
b1011010110000
b1011010110001
b1011010110010
b1011010110011
b101101011010
b10110101101100
b10110101101101
b10110101101110
b10110101101111
b1011010111
b1011011
b10111b110
b111

Token Value
12
11
25
13
30
7
28
3
24
4
27
23
29
0
1
26
31
5
16
6
18
17
15
20
19
22
21
14
8
2
9
10

VP3.1 Huffman Table Number 75

188

APPENDIX B. VP3
Huffman Code

b00
b0100
b0101
b01100000
b01100001
b0110001
b011001
b011010b011011b0111
b10000b10001b1001
b101
b11000b11001000
b1100100100
b1100100101000
b1100100101001
b1100100101010
b1100100101011
b1100100101100
b11001001011010
b11001001011011
b11001001011100
b11001001011101
b1100100101111
b110010011
b1100101b110011b1101
b111

Token Value
9
28
2
30
7
8
27
24
25
29
11
12
3
0
23
13
31
18
17
20
19
6
16
15
22
21
14
5
26
4
1
10

VP3.1 Huffman Table Number 76

Huffman Code
b000
b0010
b00110b001110b001111
b01
b10
b110
b111000b111001b111010b111011000000
b1110110000010
b11101100000110
b11101100000111
b11101100001
b11101100010
b11101100011000
b11101100011001
b11101100011010
b11101100011011
b11101100011100
b11101100011101
b11101100011110
b11101100011111
b111011001
b11101101
b11101110
b111011110
b1110111110
b1110111111
b1111

Token Value
1
2
29
12
11
9
10
0
23
4
28
30
6
15
14
7
13
21
20
31
22
17
16
19
18
5
25
27
24
8
26
3

VP3.1 Huffman Table Number 77

B.4. HUFFMAN TABLES
Huffman Code
b00
b010
b0110
b011100
b0111010000
b0111010001000
b0111010001001
b0111010001010
b0111010001011
b0111010001100
b01110100011010
b01110100011011
b01110100011100
b01110100011101
b01110100011110
b01110100011111
b011101001
b011101010
b01110101100000
b01110101100001
b01110101100010
b01110101100011
b01110101100100
b01110101100101
b01110101100110
b01110101100111
b01110101101
b0111010111
b0111011
b01111
b10
b11

189

Token Value
0
1
3
4
5
14
13
16
15
6
8
7
27
26
31
30
12
11
22
21
25
24
18
17
20
19
23
29
28
2
10
9

VP3.1 Huffman Table Number 78

Huffman Code
b00
b01
b10
b1100
b1101000
b1101001
b110101000
b110101001
b11010101
b110101100
b1101011010
b1101011011000
b11010110110010
b11010110110011
b11010110110100
b11010110110101
b11010110110110
b11010110110111
b11010110111000
b11010110111001
b11010110111010
b11010110111011
b11010110111100
b11010110111101
b11010110111110
b11010110111111
b11010111
b11011b11100b111010b111011b1111

Token Value
10
9
0
3
12
11
24
23
27
5
25
6
8
7
22
21
31
30
18
17
20
19
14
13
16
15
26
29
2
28
4
1

VP3.1 Huffman Table Number 79

190

APPENDIX B. VP3

Appendix C

Colophon
Ogg is a Xiph.Org Foundation effort to protect essential tenets of Internet multimedia from corporate hostage-taking; Open Source is the net’s greatest tool
to keep everyone honest. See About the Xiph.Org Foundation for details.
Ogg Theora is the first Ogg video codec. Anyone may freely use and distribute the Ogg and Theora specifications, whether in private, public, or corporate capacity. However, the Xiph.Org Foundation and the Ogg project reserve
the right to set the Ogg Theora specification and certify specification compliance.
Xiph.Org’s Theora software codec implementation is distributed under a
BSD-like license. This does not restrict third parties from distributing independent implementations of Theora software under other licenses.
These pages are Copyright © 2004-2007 Xiph.Org Foundation. All rights reserved. Ogg, Theora, Vorbis, Xiph.Org
Foundation and their logos are trademarks (™) of theXiph.Org Foundation.
This document is set in LATEX.

191

192

APPENDIX C. COLOPHON

Bibliography[Bra97] Scott Bradner. RFC 2119: Key words for use in RFCs to Indicate Requirement Levels, March 1997. http://www.ietf.org/rfc/rfc2119.
txt.
[CSF77] Wen-Hsiung Chen, C. Harrison Smith, and S. C. Fralick. A fast computational algorithm for the discrete cosine transform. IEEE Transactions
on Communications, COM-25(9):1004–1011, September 1977.
[ITU95] International Telecommunications Union, 1211 Geneva 20, Switzerland. Reccomendation ITU-R BT.601-5: Studio Encoding Parametersof Digital Television for Standard 4:3 and Wide-Screen 16:9 Aspect Ratios, 1982, revised edition, 1995.
[ITU98] International Telecommunications Union, 1211 Geneva 20, Switzerland. Reccomendation ITU-R BT.470-6: Conventional Television Systems, 1970, revised edition, 1998.
[ITU02] International Telecommunications Union, 1211 Geneva 20, Switzerland. Recommendation ITU-R BT.709-5: Parameter values for the
HDTV standards for production and international programme exchange,
1990, revised edition, 2002.
[Mel04] Mike Melanson. VP3 bitstream format and decoding process. http://www.multimedia.cx/vp3-format.txt, March 2004.
[Pfe03] Silvia Pfeiffer. RFC 3533: The Ogg Encapsulation Format Version 0,
May 2003. http://www.ietf.org/rfc/rfc3533.txt.
[Poy97] Charles Poynton. Frequently-asked questions about gamma. http://www.poynton.com/GammaFAQ.html, February 1997.
[SMP94] Society of Motion Pciture and Television Engineers. SMPTE-170M:
Television — Composite Analog Video Signal — NTSC for Studio Applications, 1994.
[Xip02] Xiph.Org Foundation. Vorbis I specification, 2002. http://www.xiph.
org/ogg/vorbis/doc/.
193

194

BIBLIOGRAPHY[Yer96] Francois Yergeau. RFC 2044: UTF-8, a transformation format ofUnicode and ISO 10646, October 1996. http://www.ietf.org/rfc/
rfc2044.txt.