spec: Update reference to MV decoding procedure.
[theora.git] / doc / spec / spec.tex
1 \documentclass[9pt,letterpaper]{book}
2
3 \usepackage{latexsym}
4 \usepackage{amssymb}
5 \usepackage{amsmath}
6 \usepackage{bm}
7 \usepackage{textcomp}
8 \usepackage{graphicx}
9 \usepackage{booktabs}
10 \usepackage{tabularx}
11 \usepackage{longtable}
12 \usepackage{ltablex}
13 \usepackage{wrapfig}
14 \usepackage[pdfpagemode=None,pdfstartview=FitH,pdfview=FitH,colorlinks=true]%
15  {hyperref}
16
17 \newtheorem{theorem}{Theorem}[section]
18 \newcommand{\idx}[1]{{\ensuremath{\mathit{#1}}}}
19 \newcommand{\qti}{\idx{qti}}
20 \newcommand{\qtj}{\idx{qtj}}
21 \newcommand{\pli}{\idx{pli}}
22 \newcommand{\plj}{\idx{plj}}
23 \newcommand{\qi}{\idx{qi}}
24 \newcommand{\ci}{\idx{ci}}
25 \newcommand{\bmi}{\idx{bmi}}
26 \newcommand{\bmj}{\idx{bmj}}
27 \newcommand{\qri}{\idx{qri}}
28 \newcommand{\qrj}{\idx{qrj}}
29 \newcommand{\hti}{\idx{hti}}
30 \newcommand{\sbi}{\idx{sbi}}
31 \newcommand{\bi}{\idx{bi}}
32 \newcommand{\bj}{\idx{bj}}
33 \newcommand{\mbi}{\idx{mbi}}
34 \newcommand{\mbj}{\idx{mbj}}
35 \newcommand{\mi}{\idx{mi}}
36 \newcommand{\cbi}{\idx{cbi}}
37 \newcommand{\qii}{\idx{qii}}
38 \newcommand{\ti}{\idx{ti}}
39 \newcommand{\tj}{\idx{tj}}
40 \newcommand{\rfi}{\idx{rfi}}
41 \newcommand{\zzi}{\idx{zzi}}
42 \newcommand{\ri}{\idx{ri}}
43 %This somewhat odd construct ensures that \bitvar{\qi}, etc., will set the
44 % qi in bold face, even though it is in a \mathit font, yet \bitvar{VAR} will
45 % set VAR in a bold, roman font.
46 \newcommand{\bitvar}[1]{\ensuremath{\mathbf{\bm{#1}}}}
47 \newcommand{\locvar}[1]{\ensuremath{\mathrm{#1}}}
48 \newcommand{\term}[1]{{\em #1}}
49 \newcommand{\bin}[1]{\ensuremath{\mathtt{b#1}}}
50 \newcommand{\hex}[1]{\ensuremath{\mathtt{0x#1}}}
51 \newcommand{\ilog}{\ensuremath{\mathop{\mathrm{ilog}}\nolimits}}
52 \newcommand{\round}{\ensuremath{\mathop{\mathrm{round}}\nolimits}}
53 \newcommand{\sign}{\ensuremath{\mathop{\mathrm{sign}}\nolimits}}
54 \newcommand{\lflim}{\ensuremath{\mathop{\mathrm{lflim}}\nolimits}}
55
56 %Section-based table, figure, and equation numbering.
57 \numberwithin{equation}{chapter}
58 \numberwithin{figure}{chapter}
59 \numberwithin{table}{chapter}
60
61 %Provide section numbering for \paragraph.
62 \makeatletter
63 \renewcommand{\paragraph}{\@startsection{paragraph}{4}{0ex}%
64  {-3.25ex plus -1ex minus -0.2ex}%
65  {1.5ex plus 0.2ex}%
66  {\normalfont\normalsize\bfseries}}
67 \makeatother
68 \stepcounter{secnumdepth}
69 \stepcounter{tocdepth}
70
71 \keepXColumns
72
73 \pagestyle{headings}
74 \bibliographystyle{alpha}
75
76 \title{Theora Specification}
77 \author{Xiph.Org Foundation}
78 \date{\today}
79
80
81 \begin{document}
82
83 \frontmatter
84
85 \begin{titlepage}
86 \maketitle
87 \end{titlepage}
88 \thispagestyle{empty}
89 \cleardoublepage
90
91 \pagenumbering{roman}
92
93 \thispagestyle{plain}
94 \tableofcontents
95 \cleardoublepage
96
97 \thispagestyle{plain}
98 \listoffigures
99 \cleardoublepage
100
101 \thispagestyle{plain}
102 \listoftables
103 \cleardoublepage
104
105 \thispagestyle{plain}
106 \markboth{{\sc Notation and Conventions}}{{\sc Notation and Conventions}}
107 \chapter*{Notation and Conventions}
108
109 All parameters either passed in or out of a decoding procedure are given in
110  \bitvar{bold\ face}.
111
112 The prefix \bin{} indicates that the following value is to be interpreted as a
113  binary number (base 2).
114 \begin{verse}
115 {\bf Example:} The value \bin{1110100} is equal to the decimal value 116.
116 \end{verse}
117
118 The prefix \hex{} indicates the the following value is to be interpreted as a
119  hexadecimal number (base 16).
120 \begin{verse}
121 {\bf Example:} The value \hex{74} is equal to the decimal value 116.
122 \end{verse}
123
124 All arithmetic defined by this specification is exact.
125 However, any real numbers that do arise will always be converted back to
126  integers again in short order.
127 The entire specification can be implemented using only normal integer
128  operations.
129 All operations are to be implemented with sufficiently large integers so that
130  overflow cannot occur.
131 Where the result of a computation is to be truncated to a fixed-sized binary
132  representation, this will be explicitly noted.
133 The size given for all variables is the maximum number of bits needed to store
134  any value in that variable.
135 Intermediate computations involving that variable may require more bits.
136
137 The following operators are defined:
138
139 \begin{description}
140 \item[$|a|$]
141 The absolute value of a number $a$.
142 \begin{align*}
143 |a| & = \left\{\begin{array}{ll}
144 -a, & a < 0 \\
145 a, & a \ge 0
146 \end{array}\right.
147 \end{align*}
148
149 \item[$a*b$]
150 Multiplication of a number $a$ by a number $b$.
151 \item[$\frac{a}{b}$]
152 Exact division of a number $a$ by a number $b$, producing a potentially
153  non-integer result.
154
155 \item[$\left\lfloor a\right\rfloor$] 
156 The largest integer less than or equal to a real number $a$.
157
158 \item[$\left\lceil a\right\rceil$]
159 The smallest integer greater than or equal to a real number $a$.
160
161 \item[$a//b$]
162 Integer division of $a$ by $b$.
163 \begin{align*}
164 a//b & = \left\{\begin{array}{ll}
165 \left\lceil\frac{a}{b}\right\rceil, & a < 0 \\
166 \left\lfloor\frac{a}{b}\right\rfloor, & a \ge 0
167 \end{array}\right.
168 \end{align*}
169
170 \item[$a\%b$]
171 The remainder from the integer division of $a$ by $b$.
172 \begin{align*}
173 a\%b & = a-|b|*\left\lfloor\frac{a}{|b|}\right\rfloor
174 \end{align*}
175 Note that with this definition, the result is always non-negative and less than
176  $|b|$.
177
178 \item[$a<<b$]
179 The value obtained by left-shifting the two's complement integer $a$ by $b$
180  bits.
181 For purposes of this specification, overflow is ignored, and so this is
182  equivalent to integer multiplication of $a$ by $2^b$.
183
184 \item[$a>>b$]
185 The value obtained by right-shifting the two's complement integer $a$ by $b$
186  bits, filling in the leftmost bits of the new value with $0$ if $a$ is
187  non-negative and $1$ if $a$ is negative.
188 This is {\em not} equivalent to integer division of $a$ by $2^b$.
189 Instead,
190 \begin{align*}
191 a>>b & = \left\lfloor\frac{a}{2^b}\right\rfloor.
192 \end{align*}
193
194 \item[$\round(a)$]
195 Rounds a number $a$ to the nearest integer, with ties rounded away from $0$.
196 \begin{align*}
197 \round(a) = \left\{\begin{array}{ll}
198 \lceil a-\frac{1}{2}\rceil   & a \le 0 \\
199 \lfloor a+\frac{1}{2}\rfloor & a > 0
200 \end{array}\right.
201 \end{align*}
202
203 \item[$\sign(a)$]
204 Returns the sign of a given number.
205 \begin{align*}
206 \sign(a) = \left\{\begin{array}{ll}
207 -1 & a < 0 \\
208 0  & a = 0 \\
209 1  & a > 0
210 \end{array}\right.
211 \end{align*}
212
213 \item[$\ilog(a)$]
214 The minimum number of bits required to store a positive integer $a$ in
215  two's complement notation, or $0$ for a non-positive integer $a$.
216 \begin{align*}
217 \ilog(a) = \left\{\begin{array}{ll}
218 0, & a \le 0 \\
219 \left\lfloor\log_2{a}\right\rfloor+1, & a > 0
220 \end{array}\right.
221 \end{align*}
222
223 \begin{verse}
224 {\bf Examples:}
225 \begin{itemize}
226 \item $\ilog(-1)=0$
227 \item $\ilog(0)=0$
228 \item $\ilog(1)=1$
229 \item $\ilog(2)=2$
230 \item $\ilog(3)=2$
231 \item $\ilog(4)=3$
232 \item $\ilog(7)=3$
233 \end{itemize}
234 \end{verse}
235
236 \item[$\min(a,b)$]
237 The minimum of two numbers $a$ and $b$.
238
239 \item[$\max(a,b)$]
240 The maximum of two numbers $a$ and $b$.
241
242 \end{description}
243 \cleardoublepage
244
245
246 \thispagestyle{plain}
247 \markboth{{\sc Key words}}{{\sc Key words}}
248 \chapter*{Key words}
249
250 %We can't rewrite this, because this is text required by RFC 2119, so we use
251 % some emergency stretching to get it typeset properly.
252 \setlength{\emergencystretch}{2em}
253 The key words ``MUST'', ``MUST NOT'', ``REQUIRED'', ``SHALL'', ``SHALL NOT'',
254  ``SHOULD'', ``SHOULD NOT'', ``RECOMMENDED'', ``MAY'', and ``OPTIONAL'' in this
255  document are to be intrepreted as described in RFC 2119 \cite{rfc2119}.\par
256 \setlength{\emergencystretch}{0em}
257
258 Where such assertions are placed on the contents of a Theora bitstream itself,
259  implementations should be prepared to encounter bitstreams that do not follow
260  these requirements.
261 An application's behavior in the presecence of such non-conforming bitstreams
262  is not defined by this specification, but any reasonable method of handling 
263  them MAY be used.
264 By way of example, applications MAY discard the current frame, retain the
265  current output thus far, or attempt to continue on by assuming some default
266  values for the erroneous bits.
267 When such an error occurs in the bitstream headers, an application MAY refuse
268  to decode the entire stream.
269 An application SHOULD NOT allow such non-conformant bitstreams to overflow
270  buffers and potentially execute arbitrary code, as this represents a serious
271  security risk.
272
273 An application MUST, however, ensure any bits marked as reserved have the value
274  zero, and refuse to decode the stream if they do not.
275 These are used as place holders for future bitstream features with which the
276  current bitstream is forward-compatible.
277 Such features may not increment the bitstream version number, and can only be
278  recognized by checking the value of these reserved bits.
279
280 \cleardoublepage
281
282
283
284 \mainmatter
285
286 \pagenumbering{arabic}
287 \setcounter{page}{1}
288
289 \chapter{Introduction}
290
291 Theora is a general purpose, lossy video codec.
292 It is based on the VP3 video codec produced by On2 Technologies
293  (\url{http://www.on2.com/}).
294 On2 donated the VP3.1 source code to the Xiph.Org Foundation and released it
295  under a BSD-like license.
296 On2 also made an irrevocable, royalty-free license grant for any patent claims
297  it might have over the software and any derivatives.
298 No formal specification exists for the VP3 format beyond this source code,
299  however Mike Melanson maintains a detailed description \cite{Mel04}.
300 Portions of this specification were adopted from that text with permission.
301
302 \section{VP3 and Theora}
303
304 Theora contains a superset of the features that were available in the original
305  VP3 codec.
306 Content encoded with VP3.1 can be losslessly transcoded into the Theora format.
307 Theora content cannot, in general, be losslessly transcoded into the VP3
308  format.
309 If a feature is not available in the original VP3 format, this is mentioned
310  when that feature is defined.
311 A complete list of these features appears in Appendix~\ref{app:vp3-compat}.
312 %TODO: VP3 - theora comparison in appendix
313
314 \section{Video Formats}
315
316 Theora currently supports progressive video data of arbitrary dimensions at a
317  constant frame rate in one of several $Y'C_bC_r$ color spaces.
318 The precise definition the supported color spaces appears in
319  Section~\ref{sec:colorspaces}.
320 Three different chroma subsampling formats are supported: 4:2:0, 4:2:2,
321  and 4:4:4.
322 The precise details of each of these formats and their sampling locations are
323  described in Section~\ref{sec:pixfmts}.
324
325 The Theora format does not support interlaced material, variable frame rates,
326  bit-depths larger than 8 bits per component, nor alternate color spaces such
327  as RGB or arbitrary multi-channel spaces.
328 Black and white content can be efficiently encoded, however, because the
329  uniform chroma planes compress well.
330 Support for interlaced material is planned for a future version.
331 \begin{verse}
332 {\bf Note:} Infrequently changing frame rates---as when film and video
333  sequences are cut together---can be supported in the Ogg container format by
334  chaining several Theora streams together.
335 \end{verse}
336 Support for increased bit depths or additional color spaces is not planned.
337
338 \section{Classification}
339
340 Theora is a block-based lossy transform codec that utilizes an
341  $8\times 8$ Type-II Discrete Cosine Transform and block-based motion
342  compensation.
343 This places it in the same class of codecs as MPEG-1, -2, -4, and H.263.
344 The details of how individual blocks are organized and how DCT coefficients are
345  stored in the bitstream differ substantially from these codecs, however.
346 Theora supports only intra frames (I frames in MPEG) and inter frames (P frames
347  in MPEG).
348 There is no equivalent to the bi-predictive frames (B frames) found in MPEG
349  codecs.
350
351 \section{Assumptions}
352
353 The Theora codec design assumes a complex, psychovisually-aware encoder and a
354  simple, low-complexity decoder.
355 %TODO: Talk more about implementation complexity.
356
357 Theora provides none of its own framing, synchronization, or protection against
358  transmission errors. 
359 An encoder is solely a method of accepting input video frames and
360  compressing these frames into raw, unformatted `packets'.
361 The decoder then accepts these raw packets in sequence, decodes them, and
362  synthesizes a fascimile of the original video frames.
363 Theora is a free-form variable bit rate (VBR) codec, and packets have no
364  minimum size, maximum size, or fixed/expected size.
365
366 Theora packets are thus intended to be used with a transport mechanism that
367  provides free-form framing, synchronization, positioning, and error correction
368  in accordance with these design assumptions, such as Ogg (for file transport)
369  or RTP (for network multicast).
370 For the purposes of a few examples in this document, we will assume that Theora
371  is embedded in an Ogg stream specifically, although this is by no means a
372  requirement or fundamental assumption in the Theora design.
373
374 The specification for embedding Theora into an Ogg transport stream is given in
375  Appendix~\ref{app:oggencapsulation}.
376
377 \section{Codec Setup and Probability Model}
378
379 Theora's heritage is the proprietary commerical codec VP3, and it retains a
380  fair amount of inflexibility when compared to Vorbis \cite{vorbis}, the first
381  Xiph.Org codec, which began as a research codec.
382 However, to provide additional scope for encoder improvement, Theora adopts
383  some of the configurable aspects of decoder setup that are present in Vorbis.
384 This configuration data is not available in VP3, which uses hardcoded values
385  instead.
386
387 Theora makes the same controversial design decision that Vorbis made to include
388  the entire probability model for the DCT coefficients and all the quantization
389  parameters in the bitstream headers.
390 This is often several hundred fields.
391 It is therefore impossible to decode any frame in the stream without
392  having previously fetched the codec info and codec setup headers.
393
394 \begin{verse}
395 {\bf Note:} Theora {\em can} initiate decode at an arbitrary intra-frame packet
396  within a bitstream so long as the codec has been initialized with the setup
397  headers.
398 \end{verse}
399
400 Thus, Theora headers are both required for decode to begin and relatively large
401  as bitstream headers go.
402 The header size is unbounded, although as a rule-of-thumb less than 16kB is
403  recommended, and Xiph.Org's reference encoder follows this suggestion.
404 %TODO: Is 8kB enough? My setup header is 7.4kB, that doesn't leave much room
405 % for comments.
406 %RG: the lesson from vorbis is that as small as possible is really
407 % important in some applications. Practically, what's acceptable
408 % depends a great deal on the target bitrate. I'd leave 16 kB in the
409 % spec for now. fwiw more than 1k of comments is quite unusual.
410
411 Our own design work indicates that the primary liability of the required header
412  is in mindshare; it is an unusual design and thus causes some amount of
413  complaint among engineers as this runs against current design trends and
414  points out limitations in some existing software/interface designs.
415 However, we find that it does not fundamentally limit Theora's suitable
416  application space.
417
418 %silvia: renamed
419 %\subsection{Format Specification}
420 \section{Format Conformance}
421
422 The Theora format is well-defined by its decode specification; any encoder that
423  produces packets that are correctly decoded by an implementation following
424  this specification may be considered a proper Theora encoder.
425 A decoder must faithfully and completely implement the specification defined
426  herein %, except where noted,
427  to be considered a conformant Theora decoder.
428 A decoder need not be implemented strictly as described, but the
429  actual decoder process MUST be {\em entirely mathematically equivalent}
430  to the described process.
431 Where appropriate, a non-normative description of encoder processes is
432  included.
433 These sections will be marked as such, and a proper Theora encoder is not
434  bound to follow them.
435
436 %TODO: \subsection{Hardware Profile}
437
438
439 \chapter{Coded Video Structure}
440
441 Theora's encoding and decoding process is based on $8\times 8$ blocks of
442  pixels.
443 This sections describes how a video frame is laid out, divided into
444  blocks, and how those blocks are organized.
445
446 \section{Frame Layout}
447
448 A video frame in Theora is a two-dimensional array of pixels.
449 Theora, like VP3, uses a right-handed coordinate system, with the origin in the
450  lower-left corner of the frame.
451 This is contrary to many video formats which use a left-handed coordinate
452  system with the origin in the upper-left corner of the frame.
453 %INT: This means that for interlaced material, the definition of `even fields'
454 %INT:  and `odd fields' may be reversed between Theora and other video codecs.
455 %INT: This document will always refer to them as `top fields' and `bottom
456 %INT:  fields'.
457
458 Theora divides the pixel array up into three separate \term{color planes}, one
459  for each of the $Y'$, $C_b$, and $C_r$ components of the pixel.
460 The $Y'$ plane is also called the \term{luma plane}, and the $C_b$ and $C_r$
461  planes are also called the \term{chroma planes}.
462 Each plane is assigned a numerical value, as shown in
463  Table~\ref{tab:color-planes}.
464
465 \begin{table}[htbp]
466 \begin{center}
467 \begin{tabular}{cl}\toprule
468 Index & Color Plane \\\midrule
469 $0$   & $Y'$        \\
470 $1$   & $C_b$       \\
471 $2$   & $C_r$       \\
472 \bottomrule\end{tabular}
473 \end{center}
474 \caption{Color Plane Indices}
475 \label{tab:color-planes}
476 \end{table}
477
478 In some pixel formats, the chroma planes are subsampled by a factor of two
479  in one or both directions.
480 This means that the width or height of the chroma planes may be half that of
481  the total frame width and height.
482 The luma plane is never subsampled.
483
484 \section{Picture Region}
485
486 An encoded video frame in Theora is required to have a width and height that
487  are multiples of sixteen, making an integral number of blocks even when the
488  chroma planes are subsampled.
489 However, inside a frame a smaller \term{picture region} may be defined
490  to present material whose dimensions are not a multiple of sixteen pixels, as
491  shown in Figure~\ref{fig:pic-frame}.
492 The picture region can be offset from the lower-left corner of the frame by up
493  to 255 pixels in each direction, and may have an arbitrary width and height,
494  provided that it is contained entirely within the coded frame.
495 It is this picture region that contains the actual video data.
496 The portions of the frame which lie outside the picture region may contain
497  arbitrary image data, so the frame must be cropped to the picture region
498  before display.
499 The picture region plays no other role in the decode process, which operates on
500  the entire video frame.
501
502 \begin{figure}[htbp]
503 \begin{center}
504 \includegraphics{pic-frame}
505 \end{center}
506 \caption{Location of frame and picture regions}
507 \label{fig:pic-frame}
508 \end{figure}
509
510 \section{Blocks and Super Blocks}
511 \label{sec:blocks-and-sbs}
512
513 Each color plane is subdivided into \term{blocks} of $8\times 8$ pixels.
514 Blocks are grouped into $4\times 4$ arrays called \term{super blocks} as
515  shown in Figure~\ref{fig:superblock}.
516 Each color plane has its own set of blocks and super blocks.
517 If the chroma planes are subsampled, they are still divided into $8\times 8$
518  blocks of pixels; there are just fewer blocks than in the luma plane.
519 The boundaries of blocks and super blocks in the luma plane do not necessarily
520  coincide with those of the chroma planes, if the chroma planes have been
521  subsampled.
522
523 \begin{figure}[htbp]
524 \begin{center}
525 \includegraphics{superblock}
526 \end{center}
527 \caption{Subdivision of a frame into blocks and super blocks}
528 \label{fig:superblock}
529 \end{figure}
530
531 Blocks are accessed in two different orders in the various decoder processes.
532 The first is \term{raster order}, illustrated in Figure~\ref{fig:raster-block}.
533 This accesses each block in row-major order, starting in the lower left of the
534  frame and continuing along the bottom row of the entire frame, followed by the
535  next row up, starting on the left edge of the frame, etc.
536
537 \begin{figure}[htbp]
538 \begin{center}
539 \includegraphics{raster-block}
540 \end{center}
541 \caption{Raster ordering of $n\times m$ blocks}
542 \label{fig:raster-block}
543 \end{figure}
544
545 The second is \term{coded order}.
546 In coded order, blocks are accessed by super block.
547 Within each frame, super blocks are traversed in raster order,
548  similar to raster order for blocks.
549 Within each super block, however, blocks are accessed in a Hilbert curve
550  pattern, illustrated in Figure~\ref{fig:hilbert-block}.
551 If a color plane does not contain a complete super block on the top or right
552  sides, the same ordering is still used, simply with any blocks outside the
553  frame boundary ommitted.
554
555 \begin{figure}[htbp]
556 \begin{center}
557 \includegraphics{hilbert-block}
558 \end{center}
559 \caption{Hilbert curve ordering of blocks within a super block}
560 \label{fig:hilbert-block}
561 \end{figure}
562
563 To illustrate this ordering, consider a frame that is 240 pixels wide and
564  48 pixels high.
565 Each row of the luma plane has 30 blocks and 8 super blocks, and there are 6
566  rows of blocks and two rows of super blocks.
567
568 %When accessed in raster order, each block in the luma plane is assigned the
569 % following indices:
570
571 %\vspace{\baselineskip}
572 %\begin{center}
573 %\begin{tabular}{|ccccccc|}\hline
574 %150 & 151 & 152 & 153 & $\ldots$ & 178 & 179 \\
575 %120 & 121 & 122 & 123 & $\ldots$ & 148 & 149 \\\hline
576 % 90 &  91 &  92 &  93 & $\ldots$ & 118 & 119 \\
577 % 60 &  61 &  62 &  63 & $\ldots$ &  88 &  89 \\
578 % 30 &  31 &  32 &  33 & $\ldots$ &  58 &  59 \\
579 %  0 &   1 &   2 &   3 & $\ldots$ &  28 &  29 \\\hline
580 %\end{tabular}
581 %\end{center}
582 %\vspace{\baselineskip}
583
584 When accessed in coded order, each block in the luma plane is assigned the
585  following indices:
586
587 \vspace{\baselineskip}
588 \begin{center}
589 \begin{tabular}{|cccc|c|cc|}\hline
590 123 & 122 & 125 & 124 & $\ldots$ & 179 & 178 \\
591 120 & 121 & 126 & 127 & $\ldots$ & 176 & 177 \\\hline
592   5 &   6 &   9 &  10 & $\ldots$ & 117 & 118 \\
593   4 &   7 &   8 &  11 & $\ldots$ & 116 & 119 \\
594   3 &   2 &  13 &  12 & $\ldots$ & 115 & 114 \\
595   0 &   1 &  14 &  15 & $\ldots$ & 112 & 113 \\\hline
596 \end{tabular}
597 \end{center}
598 \vspace{\baselineskip}
599
600 Here the index values specify the order in which the blocks would be accessed.
601 The indices of the blocks are numbered continuously from one color plane to the
602  next.
603 They do not reset to zero at the start of each plane.
604 Instead, the numbering increases continuously from the $Y'$ plane to the $C_b$
605  plane to the $C_r$ plane.
606 The implication is that the blocks from all planes are treated as a unit during
607  the various processing steps.
608
609 Although blocks are sometimes accessed in raster order, in this document the
610  index associated with a block is {\em always} its index in coded order.
611
612 \section{Macro Blocks}
613 \label{sec:mbs}
614
615 A macro block contains a $2\times 2$ array of blocks in the luma plane
616  {\em and} the co-located blocks in the chroma planes, as shown in
617  Figure~\ref{fig:macroblock}.
618 Thus macro blocks can represent anywhere from six to twelve blocks, depending
619  on how the chroma planes are subsampled.
620 This is in contrast to super blocks, which only contain blocks from a single
621  color plane.
622 % the whole super vs. macro blocks thing is a little confusing, and it can be
623 % hard to remember which is what initially. A figure would/will help here,
624 % but I tried to add some text emphasizing the difference in terms of
625 % functionality.
626 %TBT: At this point we haven't described any functionality yet.
627 %TBT: As far as the reader knows, the only purpose of the blocks, macro blocks
628 %TBT:  and super blocks is for data organization---and for blocks and super
629 %TBT:  blocks, this is essentially true.
630 %TBT: So lets restrict the differences we emphasize to those of data
631 %TBT:  organization, which the sentence I just added above does.
632 Macro blocks contain information about coding mode and motion vectors for the
633  corresponding blocks in all color planes.
634
635 \begin{figure}[htbp]
636  \begin{center}
637  \includegraphics{macroblock}
638  \end{center}
639  \caption{Subdivision of a frame into macro blocks}
640  \label{fig:macroblock}
641 \end{figure}
642
643 Macro blocks are also accessed in a \term{coded order}.
644 This coded order proceeds by examining each super block in the luma plane in
645  raster order, and traversing the four macro blocks inside using a smaller
646  Hilbert curve, as shown in Figure~\ref{fig:hilbert-mb}.
647 %r: I rearranged the wording to make a more formal idiom here
648 If the luma plane does not contain a complete super block on the top or right
649  sides, the same ordering is still used, with any macro blocks outside
650  the frame boundary simply omitted.
651 Because the frame size is constrained to be a multiple of 16, there are never
652  any partial macro blocks.
653 Unlike blocks, macro blocks need never be accessed in a pure raster order.
654
655 \begin{figure}[htbp]
656 \begin{center}
657 \includegraphics{hilbert-mb}
658 \end{center}
659 \caption{Hilbert curve ordering of macro blocks within a super block}
660 \label{fig:hilbert-mb}
661 \end{figure}
662
663 Using the same frame size as the example above, there are 15 macro blocks in
664  each row and 3 rows of macro blocks.
665 The macro blocks are assigned the following indices:
666
667 \vspace{\baselineskip}
668 \begin{center}
669 \begin{tabular}{|cc|cc|c|cc|c|}\hline
670 30 & 31 & 32 & 33 & $\cdots$ & 42 & 43 & 44 \\\hline
671  1 &  2 &  5 &  6 & $\cdots$ & 25 & 26 & 29 \\
672  0 &  3 &  4 &  7 & $\cdots$ & 24 & 27 & 28 \\\hline
673 \end{tabular}
674 \end{center}
675 \vspace{\baselineskip}
676
677 \section{Coding Modes and Prediction}
678
679 Each block is coded using one of a small, fixed set of \term{coding modes} that
680  define how the block is predicted from previous frames.
681 A block is predicted using one of two \term{reference frames}, selected
682  according to the coding mode.
683 A reference frame is the fully decoded version of a previous frame in the
684  stream.
685 The first available reference frame is the previous intra frame, called the
686  \term{golden frame}.
687 The second available reference frame is the previous frame, whether it was an
688  intra frame or an inter frame.
689 If the previous frame was an intra frame, then both reference frames are the
690  same.
691 See Figure~\ref{fig:reference-frames} for an illustration of the reference
692  frames used for an intra frame that does not follow an intra frame.
693
694 \begin{figure}[htbp]
695 \begin{center}
696 \includegraphics{reference-frames}
697 \end{center}
698 \caption{Example of reference frames for an inter frame}
699 \label{fig:reference-frames}
700 \end{figure}
701
702 Two coding modes in particular are worth mentioning here.
703 The INTRA mode is used for blocks that are not predicted from either reference
704  frame.
705 This is the only coding mode allowed in intra frames.
706 The INTER\_NOMV coding mode uses the co-located contents of the block in the
707  previous frame as the predictor.
708 This is the default coding mode.
709
710 \section{DCT Coefficients}
711 \label{sec:dct-coeffs}
712
713 A \term{residual} is added to the predicted contents of a block to form the
714  final reconstruction.
715 The residual is stored as a set of quantized coefficients from an integer
716  approximation of a two-dimensional Type II Discrete Cosine Transform.
717 The DCT takes an $8\times 8$ array of pixel values as input and returns an
718  $8\times 8$ array of coefficient values.
719 The \term{natural ordering} of these coefficients is defined to be row-major
720  order, from lowest to highest frequency.
721 They are also often indexed in \term{zig-zag order}, as shown in
722  Figure~\ref{tab:zig-zag}.
723
724 \begin{figure}[htbp]
725 \begin{center}
726 \begin{tabular}[c]{rr|c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c}
727  &\multicolumn{1}{r}{} & && &&&&&$c$&&& && &&  \\
728  &\multicolumn{1}{r}{} &0&&1&&2&&3&&4&&5&&6&&7 \\\cline{3-17}
729  &0 &  0 &$\rightarrow$&  1 &&  5 &$\rightarrow$&  6 && 14 &$\rightarrow$& 15 && 27 &$\rightarrow$& 28            \\[-0.5\defaultaddspace]
730  &  &    &$\swarrow$&&$\nearrow$& &$\swarrow$&&$\nearrow$& &$\swarrow$&&$\nearrow$& &$\swarrow$&                  \\
731  &1 &  2 &             &  4 &&  7 &             & 13 && 16 &             & 26 && 29 &             & 42            \\[-0.5\defaultaddspace]
732  &  &$\downarrow$&$\nearrow$&&$\swarrow$&&$\nearrow$&&$\swarrow$&&$\nearrow$&&$\swarrow$&&$\nearrow$&$\downarrow$ \\
733  &2 &  3 &             &  8 && 12 &             & 17 && 25 &             & 30 && 41 &             & 43            \\[-0.5\defaultaddspace]
734  &  &    &$\swarrow$&&$\nearrow$& &$\swarrow$&&$\nearrow$& &$\swarrow$&&$\nearrow$& &$\swarrow$&                  \\
735  &3 &  9 &             & 11 && 18 &             & 24 && 31 &             & 40 && 44 &             & 53            \\[-0.5\defaultaddspace]
736 $r$&&$\downarrow$&$\nearrow$&&$\swarrow$&&$\nearrow$&&$\swarrow$&&$\nearrow$&&$\swarrow$&&$\nearrow$&$\downarrow$ \\
737  &4 & 10 &             & 19 && 23 &             & 32 && 39 &             & 45 && 52 &             & 54            \\[-0.5\defaultaddspace]
738  &  &    &$\swarrow$&&$\nearrow$& &$\swarrow$&&$\nearrow$& &$\swarrow$&&$\nearrow$& &$\swarrow$&                  \\
739  &5 & 20 &             & 22 && 33 &             & 38 && 46 &             & 51 && 55 &             & 60            \\[-0.5\defaultaddspace]
740  &  &$\downarrow$&$\nearrow$&&$\swarrow$&&$\nearrow$&&$\swarrow$&&$\nearrow$&&$\swarrow$&&$\nearrow$&$\downarrow$ \\
741  &6 & 21 &             & 34 && 37 &             & 47 && 50 &             & 56 && 59 &             & 61            \\[-0.5\defaultaddspace]
742  &  &    &$\swarrow$&&$\nearrow$& &$\swarrow$&&$\nearrow$& &$\swarrow$&&$\nearrow$& &$\swarrow$&                  \\
743  &7 & 35 &$\rightarrow$& 36 && 48 &$\rightarrow$& 49 && 57 &$\rightarrow$& 58 && 62 &$\rightarrow$& 63
744 \end{tabular}
745 \end{center}
746 \caption{Zig-zag order}
747 \label{tab:zig-zag}
748 \end{figure}
749
750 \begin{verse}
751 {\bf Note:} the row and column indices refer to {\em frequency number} and not
752  pixel locations.
753 The frequency numbers are defined independently of the memory organization of
754  the pixels.
755 They have been written from top to bottom here to follow conventional notation,
756  despite the right-handed coordinate system Theora uses for pixel locations.
757 %RG: I'd rather we were internally consistent and put dc at the lower left.
758 Many implementations of the DCT operate `in-place'.
759 That is, they return DCT coefficients in the same memory buffer that the
760  initial pixel values were stored in.
761 Due to the right-handed coordinate system used for pixel locations in Theora,
762  one must note carefully how both pixel values and DCT coefficients are
763  organized in memory in such a system.
764 \end{verse}
765
766 DCT coefficient $(0,0)$ is called the \term{DC coefficient}.
767 All the other coefficients are called \term{AC coefficients}.
768
769
770 \chapter{Decoding Overview}
771
772 This section provides a high level description of the Theora codec's
773  construction.
774 A bit-by-bit specification appears beginning in Section~\ref{sec:bitpacking}.
775 The later sections assume a high-level understanding of the Theora decode
776  process, which is provided below.
777
778 \section{Decoder Configuration}
779
780 Decoder setup consists of configuration of the quantization matrices and the
781  Huffman codebooks for the DCT coefficients, and a table of limit values for
782  the deblocking filter.
783 The remainder of the decoding pipeline is not configurable.
784
785 \subsection{Global Configuration}
786
787 The global codec configuration consists of a few video related fields, such as
788  frame rate, frame size, picture size and offset, aspect ratio, color space,
789  pixel format, and a version number.
790 The version number is divided into a major version, a minor version, amd a
791  minor revision number.
792 %r: afaik the released vp3 codec called itself 3.1 and is compatible w/ theora
793 %r: even though we received the in-progress 3.2 codebase
794 For the format defined in this specification, these are `3', `2', and
795  `1', respectively, in reference to Theora's origin as a successor to 
796  the VP3.1 format.
797
798 \subsection{Quantization Matrices}
799
800 Theora allows up to 384 different quantization matrices to be defined, one for
801  each \term{quantization type}, \term{color plane} ($Y'$, $C_b$, or $C_r$), and
802  \term{quantization index}, \qi, which ranges from zero to 63, inclusive.
803 There are currently two quantization types defined, which depend on the coding
804  mode of the block being dequantized, as shown in Table~\ref{tab:quant-types}.
805
806 \begin{table}[htbp]
807 \begin{center}
808 \begin{tabular}{cl}\toprule
809 Quantization Type & Usage                     \\\midrule
810 $0$               & INTRA-mode blocks         \\
811 $1$               & Blocks in any other mode. \\
812 \bottomrule\end{tabular}
813 \end{center}
814 \caption{Quantization Type Indices}
815 \label{tab:quant-types}
816 \end{table}
817
818 %r: I think 'nominally' is more specific than 'generally' here
819 The quantization index, on the other hand, nominally represents a progressive
820  range of quality levels, from low quality near zero to high quality near 63.
821 However, the interpretation is arbitrary, and it is possible, for example, to
822  partition the scale into two completely separate ranges with 32 levels each
823  that are meant to represent different classes of source material, or any
824  other arrangement that suits the encoder's requirements.
825
826 Each quantization matrix is an $8\times 8$ matrix of 16-bit values, which is
827  used to quantize the output of the $8\times 8$ DCT\@.
828 Quantization matrices are specified using three components: a
829  \term{base matrix} and two \term{scale values}.
830 The first scale value is the \term{DC scale}, which is applied to the DC
831  component of the base matrix.
832 The second scale value is the \term{AC scale}, which is applied to all the
833  other components of the base matrix.
834 There are 64 DC scale values and 64 AC scale values, one for each \qi\ value.
835
836 There are 64 elements in each base matrix, one for each DCT coefficient.
837 They are stored in natural order (cf. Section~\ref{sec:dct-coeffs}).
838 There is a separate set of base matrices for each quantization type and each
839  color plane, with up to 64 possible base matrices in each set, one for each
840  \qi\ value.
841 %r: we will mention that the given matricies must bound the \qi range
842 %r: in the detailed section. it's not important at this level.
843 Typically the bitstream contains matrices for only a sparse subset of the
844  possible \qi\ values.
845 The base matrices for the remainder of the \qi\ values are computed using
846  linear interpolation.
847 This configuration allows the encoder to adjust the quantization matrices to
848  approximate the complex, non-linear response of the human visual system to
849  different quantization errors.
850
851 Finally, because the in-loop deblocking filter strength depends on the strength
852  of the quantization matrices defined in this header, a table of 64 \term{loop
853  filter limit values} is defined, one for each \qi\ value.
854
855 The precise specification of how all of this information is decoded appears in
856  Section~\ref{sub:loop-filter-limits} and Section~\ref{sub:quant-params}.
857
858 \subsection{Huffman Codebooks}
859
860 Theora uses 80 configurable binary Huffman codes to represent the 32 tokens
861  used to encode DCT coefficients.
862 Each of the 32 token values has a different semantic meaning and is used to
863  represent single coefficient values, zero runs, combinations of the two, and
864  \term{End-Of-Block markers}.
865
866 The 80 codes are divided up into five groups of 16, with each group
867  corresponding to a set of DCT coefficient indices.
868 The first group corresponds to the DC coefficient, while the remaining four
869  groups correspond to different subsets of the AC coefficients.
870 Within each frame, two pairs of 4-bit codebook indices are stored.
871 The first pair selects which codebooks to use from the DC coefficient group for
872  the $Y'$ coefficients and the $C_b$ and $C_r$ coefficients.
873 The second pair selects which codebooks to use from {\em all four} of the AC
874  coefficient groups for the $Y'$ coefficients and the $C_b$ and $C_r$
875  coefficients.
876
877 The precise specification of how the codebooks are decoded appears in
878  Section~\ref{sub:huffman-tables}.
879
880 \section{High-Level Decode Process}
881
882 \subsection{Decoder Setup}
883
884 Before decoding can begin, a decoder MUST be initialized using the bitstream
885  headers corresponding to the stream to be decoded.
886 Theora uses three header packets; all are required, in order, by this
887  specification.
888 Once set up, decode may begin at any intra-frame packet---or even inter-frame
889  packets, provided the appropriate decoded reference frames have already been
890  decoded and cached---belonging to the Theora stream.
891 In Theora I, all packets after the three initial headers are intra-frame or
892  inter-frame packets.
893
894 The header packets are, in order, the identification header, the comment
895  header, and the setup header.
896
897 \paragraph{Identification Header}
898
899 The identification header identifies the stream as Theora, provides a version
900  number, and defines the characteristics of the video stream such as frame
901  size.
902 A complete description of the identification header appears in
903  Section~\ref{sec:idheader}.
904
905 \paragraph{Comment Header}
906
907 The comment header includes user text comments (`tags') and a vendor string
908  for the application/library that produced the stream.
909 The format of the comment header is the same as that used in the Vorbis I and
910  Speex codecs, with slight modifications due to the use of a different bit
911  packing mechanism.
912 A complete description of how the comment header is coded appears in
913  Section~\ref{sec:commentheader}, along with a suggested set of tags.
914
915 \paragraph{Setup Header}
916
917 The setup header includes extensive codec setup information, including the
918  complete set of quantization matrices and Huffman codebooks needed to decode
919  the DCT coefficients.
920 A complete description of the setup header appears in
921  Section~\ref{sec:setupheader}.
922
923 \subsection{Decode Procedure}
924
925 The decoding and synthesis procedure for all video packets is fundamentally the
926  same, with some steps omitted for intra frames.
927 \begin{itemize}
928 \item
929 Decode packet type flag.
930 \item
931 Decode frame header.
932 \item
933 Decode coded block information (inter frames only).
934 \item
935 Decode macro block mode information (inter frames only).
936 \item
937 Decode motion vectors (inter frames only).
938 \item
939 Decode block-level \qi\ information.
940 \item
941 Decode DC coefficient for each coded block.
942 \item
943 Decode 1st AC coefficient for each coded block.
944 \item
945 Decode 2nd AC coefficient for each coded block.
946 \item
947 $\ldots$
948 \item
949 Decode 63rd AC coefficient for each coded block.
950 \item Perform DC coefficient prediction.
951 \item Reconstruct coded blocks.
952 \item Copy uncoded bocks.
953 \item Perform loop filtering.
954 \end{itemize}
955
956 \begin{verse}
957 {\bf Note:} clever rearrangement of the steps in this process is possible.
958 As an example, in a memory-constrained environment, one can make multiple
959  passes through the DCT coefficients to avoid buffering them all in memory.
960 On the first pass, the starting location of each coefficient is identified, and
961  then 64 separate get pointers are used to read in the 64 DCT coefficients
962  required to reconstruct each coded block in sequence.
963 This operation produces entirely equivalent output and is naturally perfectly
964  legal.
965 It may even be a benefit in non-memory-constrained environments due to a
966  reduced cache footprint.
967 \end{verse}
968
969 Theora makes equivalence easy to check by defining all decoding operations in
970  terms of exact integer operations.
971 No floating-point math is required, and in particular, the implementation of
972  the iDCT transform MUST be followed precisely.
973 This prevents the decoder mismatch problem commonly associated with codecs that
974  provide a less rigorous transform specification.
975 Such a mismatch problem would be devastating to Theora, since a single rounding
976  error in one frame could propagate throughout the entire succeeding frame due
977  to DC prediction.
978
979 \paragraph{Packet Type Decode}
980
981 Theora uses four packet types.
982 The first three packet types mark each of the three Theora headers described
983  above.
984 The fourth packet type marks a video packet.
985 All other packet types are reserved; packets marked with a reserved type should
986  be ignored.
987
988 Additionally, zero-length packets are treated as if they were an inter 
989 frame with no blocks coded. That is, as a duplicate frame.
990
991 \paragraph{Frame Header Decode}
992
993 The frame header contains some global information about the current frame.
994 The first is the frame type field, which specifies if this is an intra frame or
995  an inter frame.
996 Inter frames predict their contents from previously decoded reference frames.
997 Intra frames can be independently decoded with no established reference frames.
998
999 The next piece of information in the frame header is the list of \qi\ values
1000  allowed in the frame.
1001 Theora allows from one to three different \qi\ values to be used in a single
1002  frame, each of which selects a set of six quantization matrices, one for each
1003  quantization type (inter or intra), and one for each color plane.
1004 The first \qi\ value is {\em always} used when dequantizing DC coefficients.
1005 The \qi\ value used when dequantizing AC coefficients, however, can vary from
1006  block to block.
1007 VP3, in contrast, only allows a single \qi\ value per frame for both the DC and
1008  AC coefficients.
1009
1010 \paragraph{Coded Block Information}
1011
1012 This stage determines which blocks in the frame are coded and which are
1013  uncoded.
1014 A \term{coded block list} is constructed which lists all the coded blocks in
1015  coded order.
1016 For intra frames, every block is coded, and so no data needs to be read from
1017  the packet.
1018
1019 \paragraph{Macro Block Mode Information}
1020
1021 For intra frames, every block is coded in INTRA mode, and this stage is
1022  skipped.
1023 In inter frames a \term{coded macro block list} is constructed from the coded
1024  block list.
1025 Any macro block which has at least one of its luma blocks coded is considered
1026  coded; all other macro blocks are uncoded, even if they contain coded chroma
1027  blocks.
1028 A coding mode is decoded for each coded macro block, and assigned to all its
1029  constituent coded blocks.
1030 All coded chroma blocks in uncoded macro blocks are assigned the INTER\_NOMV
1031  coding mode.
1032
1033 \paragraph{Motion Vectors}
1034
1035 Intra frames are coded entirely in INTRA mode, and so this stage is skipped.
1036 Some inter coding modes, however, require one or more motion vectors to be
1037  specified for each macro block.
1038 These are decoded in this stage, and an appropriate motion vector is assigned
1039  to each coded block in the macro block.
1040
1041 \paragraph{Block-Level \qi\ Information}
1042
1043 If a frame allows multiple \qi\ values, the \qi\ value assigned to each block
1044  is decoded here.
1045 Frames that use only a single \qi\ value have nothing to decode.
1046
1047 \paragraph{DCT Coefficients}
1048
1049 Finally, the quantized DCT coefficients are decoded.
1050 A list of DCT coefficients in zig-zag order for a single block is represented
1051  by a list of tokens.
1052 A token can take on one of 32 different values, each with a different semantic
1053  meaning.
1054 A single token can represent a single DCT coefficient, a run of zero
1055  coefficients within a single block, a combination of a run of zero
1056  coefficients followed by a single non-zero coefficient, an
1057  \term{End-Of-Block marker}, or a run of EOB markers.
1058 EOB markers signify that the remainder of the block is one long zero run.
1059 Unlike JPEG and MPEG, there is no requirement for each block to end with 
1060  a special marker.
1061 If non-EOB tokens yield values for all 64 of the coefficients in a block, then
1062  no EOB marker occurs.
1063
1064 Each token is associated with a specific \term{token index} in a block.
1065 For single-coefficient tokens, this index is the zig-zag index of the token in
1066  the block.
1067 For zero-run tokens, this index is the zig-zag index of the {\em first}
1068  coefficient in the run.
1069 For combination tokens, the index is again the zig-zag index of the first
1070  coefficient in the zero run.
1071 For EOB markers, which signify that the remainder of the block is one long zero
1072  run, the index is the zig-zag index of the first zero coefficient in that run.
1073 For EOB runs, the token index is that of the first EOB marker in the run.
1074 Due to zero runs and EOB markers, a block does not have to have a token for
1075  every zig-zag index.
1076
1077 Tokens are grouped in the stream by token index, not by the block they
1078  originate from.
1079 This means that for each zig-zag index in turn, the tokens with that index from
1080  {\em all} the coded blocks are coded in coded block order.
1081 When decoding, a current token index is maintained for each coded block.
1082 This index is advanced by the number of coefficients that are added to the
1083  block as each token is decoded.
1084 After fully decoding all the tokens with token index \ti, the current token
1085  index of every coded block will be \ti\ or greater.
1086
1087 If an EOB run of $n$ blocks is decoded at token index \ti, then it ends the
1088  next $n$ blocks in coded block order whose current token index is equal to
1089  \ti, but not greater.
1090 If there are fewer than $n$ blocks with a current token index of \ti, then the
1091  decoder goes through the coded block list again from the start, ending blocks
1092  with a current token index of $\ti+1$, and so on, until $n$ blocks have been
1093  ended.
1094
1095 Tokens are read by parsing a Huffman code that depends on \ti\ and the color
1096  plane of the next coded block whose current token index is equal to \ti, but
1097  not greater.
1098 The Huffman codebooks are selected on a per-frame basis from the 80 codebooks
1099  defined in the setup header.
1100 Many tokens have a fixed number of \term{extra bits} associated with them.
1101 These bits are read from the packet immediately after the token is decoded.
1102 These are used to define things such as coefficient magnitude, sign, and the
1103  length of runs.
1104
1105 \paragraph{DC Prediction}
1106
1107 After the coefficients for each block are decoded, the quantized DC value of
1108  each block is adjusted based on the DC values of its neighbors.
1109 This adjustment is performed by scanning the blocks in raster order, not coded
1110  block order.
1111
1112 \paragraph{Reconstruction}
1113
1114 Finally, using the coding mode, motion vector (if applicable), quantized
1115  coefficient list, and \qi\ value defined for each block, all the coded blocks
1116  are reconstructed.
1117 The DCT coefficients are dequantized, an inverse DCT transform is applied, and
1118  the predictor is formed from the coding mode and motion vector and added to
1119  the result.
1120
1121 \paragraph{Loop Filtering}
1122
1123 To complete the reconstructed frame, an ``in-loop'' deblocking filter is
1124  applied to the edges of all coded blocks.
1125
1126
1127 \chapter{Video Formats}
1128
1129 This section gives a precise description of the video formats that Theora is
1130  capable of storing.
1131 The Theora bitstream is capable of handling video at any arbitrary resolution
1132  up to $1048560\times 1048560$.
1133 Such video would require almost three terabytes of storage per frame for
1134  uncompressed data, so compliant decoders MAY refuse to decode images with
1135  sizes beyond their capabilities.
1136 %TODO: What MUST a "compliant" decoder accept?
1137 %TODO: What SHOULD a decoder use for an upper bound? (derive from total amount
1138 %TODO:  of memory and memory bandwidth)
1139 %TODO: Any lower limits?
1140 %TODO: We really need hardware device profiles, but such things should be
1141 %TODO:  developed with input from the hardware community.
1142 %TODO: And even then sometimes they're useless
1143
1144 The remainder of this section talks about two specific aspects of the video
1145  format: the color space and the pixel format.
1146 The first describes how color is represented and how to transform that color
1147  representation into a device independent color space such as CIE $XYZ$ (1931).
1148 The second describes the various schemes for sampling the color values in time
1149  and space.
1150
1151 \section{Color Space Conventions}
1152
1153 There are a large number of different color standards used in digital video.
1154 Since Theora is a lossy codec, it restricts itself to only a few of them to
1155  simplify playback.
1156 Unlike the alternate method of describing all the parameters of the color
1157  model, this allows a few dedicated routines for color conversion to be written
1158  and heavily optimized in a decoder.
1159 More flexible conversion functions should instead be specified in an encoder,
1160  where additional computational complexity is more easily tolerated.
1161 The color spaces were selected to give a fair representation of color standards
1162  in use around the world today.
1163 Most of the standards that do not exactly match one of these can be converted
1164  to one fairly easily.
1165
1166 All Theora color spaces are $Y'C_bC_r$ color spaces with one luma channel and
1167  two chroma channels.
1168 Each channel contains 8-bit discrete values in the range $0\ldots255$, which
1169  represent non-linear gamma pre-corrected signals.
1170 The Theora identification header contains an 8-bit value that describes the
1171  color space.
1172 This merely selects one of the color spaces available from an enumerated list.
1173 Currently, only two color spaces are defined, with a third possibility that
1174  indicates the color space is ``unknown".
1175
1176 \section{Color Space Conversions and Parameters}
1177 \label{sec:color-xforms}
1178
1179 The parameters which describe the conversions between each color space are
1180  listed below.
1181 These are the parameters needed to map colors from the encoded $Y'C_bC_r$
1182  representation to the device-independent color space CIE $XYZ$ (1931).
1183 These parameters define abstract mathematical conversion functions which are
1184  infinitely precise.
1185 The accuracy and precision with which the conversions are performed in a real
1186  system is determined by the quality of output desired and the available
1187  processing power.
1188 Exact decoder output is defined by this specification only in the original
1189  $Y'C_bC_r$ space.
1190
1191 \begin{description}
1192 \item[$Y'C_bC_r$ to $Y'P_bP_r$:]
1193 \vspace{\baselineskip}\hfill
1194
1195 This conversion takes 8-bit discrete values in the range $[0\ldots255]$ and
1196  maps them to real values in the range $[0\ldots1]$ for Y and
1197  $[-\frac{1}{2}\ldots\frac{1}{2}]$ for $P_b$ and $P_r$.
1198 Because some values may fall outside the offset and excursion defined for each
1199  channel in the $Y'C_bC_r$ space, the results may fall outside these ranges in
1200  $Y'P_bP_r$ space.
1201 No clamping should be done at this stage.
1202
1203 \begin{align}
1204 Y'_\mathrm{out} & =
1205  \frac{Y'_\mathrm{in}-\mathrm{Offset}_Y}{\mathrm{Excursion}_Y} \\
1206 P_b             & =
1207  \frac{C_b-\mathrm{Offset}_{C_b}}{\mathrm{Excursion}_{C_b}} \\
1208 P_r             & =
1209  \frac{C_r-\mathrm{Offset}_{C_r}}{\mathrm{Excursion}_{C_r}}
1210 \end{align}
1211
1212 Parameters: $\mathrm{Offset}_{Y,C_b,C_r}$, $\mathrm{Excursion}_{Y,C_b,C_r}$.
1213
1214 \item[$Y'P_bP_r$ to $R'G'B'$:]
1215 \vspace{\baselineskip}\hfill
1216
1217 This conversion takes the one luma and two chroma channel representation and
1218  maps it to the non-linear $R'G'B'$ space used to drive actual output devices.
1219 Values should be clamped into the range $[0\ldots1]$ after this stage.
1220
1221 \begin{align}
1222 R' & = Y'+2(1-K_r)P_r \\
1223 G' & = Y'-2\frac{(1-K_b)K_b}{1-K_b-K_r}P_b-2\frac{(1-K_r)K_r}{1-K_b-K_r}P_r\\
1224 B' & = Y'+2(1-K_b)P_b
1225 \end{align}
1226
1227 Parameters: $K_b,K_r$.
1228
1229 \item[$R'G'B'$ to $RGB$ (Output device gamma correction):]
1230 \vspace{\baselineskip}\hfill
1231
1232 This conversion takes the non-linear $R'G'B'$ voltage levels and maps them to
1233  linear light levels produced by the actual output device.
1234 Note that this conversion is only that of the output device, and its inverse is
1235  {\em not} that used by the input device.
1236 Because a dim viewing environment is assumed in most television standards, the
1237  overall gamma between the input and output devices is usually around $1.1$ to
1238  $1.2$, and not a strict $1.0$.
1239
1240 For calibration with actual output devices, the model
1241 \begin{align}
1242 L & =(E'+\Delta)^\gamma
1243 \end{align}
1244  should be used, with $\Delta$ the free parameter and $\gamma$ held fixed to
1245  the value specified in this document.
1246 The conversion function presented here is an idealized version with $\Delta=0$.
1247
1248 \begin{align}
1249 R & = R'^\gamma \\
1250 G & = G'^\gamma \\
1251 B & = B'^\gamma
1252 \end{align}
1253
1254 Parameters: $\gamma$.
1255
1256 \item[$RGB$ to $R'G'B'$ (Input device gamma correction):]
1257 \vspace{\baselineskip}\hfill
1258
1259 %TODO: Tag section as non-normative
1260
1261 This conversion takes linear light levels and maps them to the non-linear
1262  voltage levels produced in the actual input device.
1263 This information is merely informative.
1264 It is not required for building a decoder or for converting between the various
1265  formats and the actual output capabilities of a particular device.
1266
1267 A linear segment is introduced on the low end to reduce noise in dark areas of
1268  the image.
1269 The rest of the scale is adjusted so that the power segment of the curve
1270  intersects the linear segment with the proper slope, and so that it still maps
1271  0 to 0 and 1 to 1.
1272
1273 \begin{align}
1274 R' & = \left\{
1275 \begin{array}{ll}
1276 \alpha R,                     & 0\le R<\delta   \\
1277 (1+\epsilon)R^\beta-\epsilon, & \delta\le R\le1
1278 \end{array}\right. \\
1279 G' & = \left\{
1280 \begin{array}{ll}
1281 \alpha G,                     & 0\le G<\delta   \\
1282 (1+\epsilon)G^\beta-\epsilon, & \delta\le G\le1
1283 \end{array}\right. \\
1284 B' & = \left\{
1285 \begin{array}{ll}
1286 \alpha B,                     & 0\le B<\delta   \\
1287 (1+\epsilon)B^\beta-\epsilon, & \delta\le B\le1
1288 \end{array}\right.
1289 \end{align}
1290
1291 Parameters: $\beta$, $\alpha$, $\delta$, $\epsilon$.
1292
1293 \item[$RGB$ to CIE $XYZ$ (1931):]
1294 \vspace{\baselineskip}\hfill
1295
1296 This conversion maps a device-dependent linear RGB space to the
1297  device-independent linear CIE $XYZ$ space.
1298 The parameters are the CIE chromaticity coordinates of the three
1299  primaries---red, green, and blue---as well as the chromaticity coordinates
1300  of the white point of the device.
1301 This is how hardware manufacturers and standards typically describe a
1302  particular $RGB$ space.
1303 The math required to convert these parameters into a useful transformation
1304  matrix is reproduced below.
1305
1306 \begin{align}
1307 F                  & =
1308 \left[\begin{array}{ccc}
1309 \frac{x_r}{y_r}       & \frac{x_g}{y_g}       & \frac{x_b}{y_b}       \\
1310 1                     & 1                     & 1                     \\
1311 \frac{1-x_r-y_r}{y_r} & \frac{1-x_g-y_g}{y_g} & \frac{1-x_b-y_b}{y_b}
1312 \end{array}\right] \\
1313 \left[\begin{array}{c}
1314 s_r \\
1315 s_g \\
1316 s_b
1317 \end{array}\right] & =
1318 F^{-1}\left[\begin{array}{c}
1319 \frac{x_w}{y_w} \\
1320 1 \\
1321 \frac{1-x_w-y_w}{y_w}
1322 \end{array}\right] \\
1323 \left[\begin{array}{c}
1324 X \\
1325 Y \\
1326 Z
1327 \end{array}\right] & =
1328 F\left[\begin{array}{c}
1329 s_rR \\
1330 s_gG \\
1331 s_bB
1332 \end{array}\right]
1333 \end{align}
1334 Parameters: $x_r,x_g,x_b,x_w, y_r,y_g,y_b,y_w$.
1335
1336 \end{description}
1337
1338 \section{Available Color Spaces}
1339 \label{sec:colorspaces}
1340
1341 These are the color spaces currently defined for use by Theora video.
1342 Each one has a short name, with which it is referred to in this document, and
1343  a more detailed specification of the standards from which its parameters are
1344  derived.
1345 Some standards do not specify all the parameters necessary.
1346 For these unspecified parameters, this document serves as the definition of
1347  what should be used when encoding or decoding Theora video.
1348
1349 \subsection{Rec.~470M (Rec.~ITU-R~BT.470-6 System M/NTSC with
1350  Rec.~ITU-R~BT.601-5)}
1351 \label{sec:470m}
1352
1353 This color space is used by broadcast television and DVDs in much of the
1354  Americas, Japan, Korea, and the Union of Myanmar \cite{rec470}.
1355 This color space may also be used for System M/PAL (Brazil), with an
1356  appropriate conversion supplied by the encoder to compensate for the
1357  different gamma value.
1358 See Section~\ref{sec:470bg} for an appropriate gamma value to assume for M/PAL
1359  input.
1360
1361 In the US, studio monitors are adjusted to a D65 white point
1362  ($x_w,y_w=0.313,0.329$).
1363 In Japan, studio monitors are adjusted to a D white of 9300K
1364  ($x_w,y_w=0.285,0.293$).
1365
1366 Rec.~470 does not specify a digital encoding of the color signals.
1367 For Theora, Rec.~ITU-R~BT.601-5 \cite{rec601} is used, starting from the
1368  $R'G'B'$ signals specified by Rec.~470.
1369
1370 Rec.~470 does not specify an input gamma function.
1371 For Theora, the Rec.~709 \cite{rec709} input function is assumed.
1372 This is the same as that specified by SMPTE 170M \cite{smpte170m}, which claims
1373  to reflect modern practice in the creation of NTSC signals circa 1994.
1374
1375 The parameters for all the color transformations defined in
1376  Section~\ref{sec:color-xforms} are given in Table~\ref{tab:470m}.
1377
1378 \begin{table}[htb]
1379 \begin{align*}
1380 \mathrm{Offset}_{Y,C_b,C_r}    & = (16, 128, 128)  \\
1381 \mathrm{Excursion}_{Y,C_b,C_r} & = (219, 224, 224) \\
1382 K_r                            & = 0.299           \\
1383 K_b                            & = 0.114           \\
1384 \gamma                         & = 2.2             \\
1385 \beta                          & = 0.45            \\
1386 \alpha                         & = 4.5             \\
1387 \delta                         & = 0.018           \\
1388 \epsilon                       & = 0.099           \\
1389 x_r,y_r                        & = 0.67, 0.33      \\
1390 x_g,y_g                        & = 0.21, 0.71      \\
1391 x_b,y_b                        & = 0.14, 0.08      \\
1392 \text{(Illuminant C) } x_w,y_w & = 0.310, 0.316    \\
1393 \end{align*}
1394 \caption{Rec.~470M Parameters}
1395 \label{tab:470m}
1396 \end{table}
1397
1398 \subsection{Rec.~470BG (Rec.~ITU-R~BT.470-6 Systems B and G with
1399  Rec.~ITU-R~BT.601-5)}
1400 \label{sec:470bg}
1401
1402 This color space is used by the PAL and SECAM systems in much of the rest of
1403  the world \cite{rec470}
1404 This can be used directly by systems (B, B1, D, D1, G, H, I, K, N)/PAL and (B,
1405  D, G, H, K, K1, L)/SECAM\@.
1406
1407 \begin{verse}
1408 {\bf Note:} the Rec.~470BG chromaticity values are different from those
1409  specified in Rec.~470M\@.
1410 When PAL and SECAM systems were first designed, they were based upon the same
1411  primaries as NTSC\@.
1412 However, as methods of making color picture tubes have changed, the primaries
1413  used have changed as well.
1414 The U.S. recommends using correction circuitry to approximate the existing,
1415  standard NTSC primaries.
1416 Current PAL and SECAM systems have standardized on primaries in accord with
1417  more recent technology.
1418 \end{verse}
1419
1420 Rec.~470 provisionally permits the use of the NTSC chromaticity values (given
1421  in Section~\ref{sec:470m}) with legacy PAL and SECAM equipment.
1422 In Theora, material must be decoded assuming the new PAL and SECAM primaries.
1423 Material intended for display on old legacy devices should be converted by the
1424  decoder.
1425
1426 The official Rec.~470BG specifies a gamma value of $\gamma=2.8$.
1427 However, in practice this value is unrealistically high \cite{Poyn97}.
1428 Rec.~470BG states that the overall system gamma should be approximately
1429  $\gamma\beta=1.2$.
1430 Since most cameras pre-correct with a gamma value of $\beta=0.45$,
1431  this suggests an output device gamma of approximately $\gamma=2.67$.
1432 This is the value recommended for use with PAL systems in Theora.
1433
1434 Rec.~470 does not specify a digital encoding of the color signals.
1435 For Theora, Rec.~ITU-R~BT.601-5 \cite{rec601} is used, starting from the
1436  $R'G'B'$ signals specified by Rec.~470.
1437
1438 Rec.~470 does not specify an input gamma function.
1439 For Theora, the Rec 709 \cite{rec709} input function is assumed.
1440
1441 The parameters for all the color transformations defined in
1442  Section~\ref{sec:color-xforms} are given in Table~\ref{tab:470bg}.
1443
1444 \begin{table}[htb]
1445 \begin{align*}
1446 \mathrm{Offset}_{Y,C_b,C_r}    & = (16, 128, 128)  \\
1447 \mathrm{Excursion}_{Y,C_b,C_r} & = (219, 224, 224) \\
1448 K_r                            & = 0.299           \\
1449 K_b                            & = 0.114           \\
1450 \gamma                         & = 2.67            \\
1451 \beta                          & = 0.45            \\
1452 \alpha                         & = 4.5             \\
1453 \delta                         & = 0.018           \\
1454 \epsilon                       & = 0.099           \\
1455 x_r,y_r                        & = 0.64, 0.33      \\
1456 x_g,y_g                        & = 0.29, 0.60      \\
1457 x_b,y_b                        & = 0.15, 0.06      \\
1458 \text{(D65) } x_w,y_w          & = 0.313, 0.329    \\
1459 \end{align*}
1460 \caption{Rec.~470BG Parameters}
1461 \label{tab:470bg}
1462 \end{table}
1463
1464 \section{Pixel Formats}
1465 \label{sec:pixfmts}
1466
1467 Theora supports several different pixel formats, each of which uses different
1468  subsampling for the chroma planes relative to the luma plane.
1469 A decoder may need to recover a full resolution chroma plane with samples
1470  co-sited with the luma plane in order to convert to RGB for display or perform
1471  other processing.
1472 Decoders can assume that the chroma signal satisfies the Nyquist-Shannon
1473  sampling theorem.
1474 The ideal low-pass reconstruction filter this implies is not practical, but any
1475  suitable approximation can be used, depending on the available computing
1476  power.
1477 Decoders MAY simply use a box filter, assigning to each luma sample the chroma
1478  sample closest to it.
1479 Encoders would not go wrong in assuming that this will be the most common
1480  approach.
1481
1482 \subsection{4:4:4 Subsampling}
1483 \label{sec:444}
1484
1485 All three color planes are stored at full resolution---each pixel has a $Y'$,
1486  a $C_b$ and a $C_r$ value (see Figure~\ref{fig:pixel444}).
1487 The samples in the different planes are all at co-located sites.
1488
1489 \begin{figure}[htbp]
1490 \begin{center}
1491 \includegraphics{pixel444}
1492 \end{center}
1493 \caption{Pixels encoded 4:4:4}
1494 \label{fig:pixel444}
1495 \end{figure}
1496
1497 % Figure.
1498 %YRB         YRB
1499 %
1500 %
1501 %
1502 %YRB         YRB
1503 %
1504 %
1505 %
1506
1507
1508 \subsection{4:2:2 Subsampling}
1509 \label{sec:422}
1510
1511 The $C_b$ and $C_r$ planes are stored with half the horizontal resolution of
1512  the $Y'$ plane.
1513 Thus, each of these planes has half the number of horizontal blocks as the luma
1514  plane (see Figure~\ref{fig:pixel422}).
1515 Similarly, they have half the number of horizontal super blocks, rounded up.
1516 Macro blocks are defined across color planes, and so their number does not
1517  change, but each macro block contains half as many chroma blocks.
1518
1519 The chroma samples are vertically aligned with the luma samples, but
1520  horizontally centered between two luma samples.
1521 Thus, each luma sample has a unique closest chroma sample.
1522 A horizontal phase shift may be required to produce signals which use different
1523  horizontal chroma sampling locations for compatibility with different systems.
1524
1525 \begin{figure}[htbp]
1526 \begin{center}
1527 \includegraphics{pixel422}
1528 \end{center}
1529 \caption{Pixels encoded 4:2:2}
1530 \label{fig:pixel422}
1531 \end{figure}
1532
1533 % Figure.
1534 %Y     RB    Y           Y     RB    Y
1535 %
1536 %
1537 %
1538 %Y     RB    Y           Y     RB    Y
1539 %
1540 %
1541 %
1542
1543 \subsection{4:2:0 Subsampling}
1544 \label{sec:420}
1545
1546 The $C_b$ and $C_r$ planes are stored with half the horizontal and half the
1547  vertical resolution of the $Y'$ plane.
1548 Thus, each of these planes has half the number of horizontal blocks and half
1549  the number of vertical blocks as the luma plane, for a total of one quarter
1550  the number of blocks (see Figure~\ref{fig:pixel420}).
1551 Similarly, they have half the number of horizontal super blocks and half the
1552  number of vertical super blocks, rounded up.
1553 Macro blocks are defined across color planes, and so their number does not
1554  change, but each macro block contains within it one quarter as many 
1555  chroma blocks.
1556
1557 The chroma samples are vertically and horizontally centered between four luma
1558  samples.
1559 Thus, each luma sample has a unique closest chroma sample.
1560 This is the same sub-sampling pattern used with JPEG, MJPEG, and MPEG-1, and
1561  was inherited from VP3.
1562 A horizontal or vertical phase shift may be required to produce signals which
1563  use different chroma sampling locations for compatibility with different
1564  systems.
1565
1566 \begin{figure}[htbp]
1567 \begin{center}
1568 \includegraphics{pixel420}
1569 \end{center}
1570 \caption{Pixels encoded 4:2:0}
1571 \label{fig:pixel420}
1572 \end{figure}
1573
1574 % Figure.
1575 %Y           Y           Y           Y
1576 %
1577 %      RB                      RB
1578 %
1579 %Y           Y           Y           Y
1580 %
1581 %
1582 %
1583 %Y           Y           Y           Y
1584 %
1585 %      RB                      RB
1586 %
1587 %Y           Y           Y           Y
1588 %
1589 %
1590 %
1591
1592 \subsection{Subsampling and the Picture Region}
1593
1594 Although the frame size must be an integral number of macro blocks, and thus
1595  both the number of pixels and the number of blocks in each direction must be
1596  even, no such requirement is made of the picture region.
1597 Thus, when using subsampled pixel formats, careful attention must be paid to
1598  which chroma samples correspond to which luma samples.
1599
1600 As mentioned above, for each pixel format, there is a unique chroma sample that
1601  is the closest to each luma sample.
1602 When cropping the chroma planes to the picture region, all the chroma samples
1603  corresponding to a luma sample in the cropped picture region must be included.
1604 Thus, when dividing the width or height of the picture region by two to obtain
1605  the size of the subsampled chroma planes, they must be rounded up.
1606
1607 Furthermore, the sampling locations are defined relative to the frame,
1608  {\em not} the picture region.
1609 When using the 4:2:2 and 4:2:0 formats, the locations of chroma samples
1610  relative to the luma samples depends on whether or not the X offset of the
1611  picture region is odd.
1612 If the offset is even, each column of chroma samples corresponds to two columns
1613  of luma samples (see Figure~\ref{fig:pic_even} for an example).
1614 The only exception is if the width is odd, in which case the last column
1615  corresponds to only one column of luma samples (see Figure~\ref{fig:pic_even_odd}).
1616 If the offset is odd, then the first column of chroma samples corresponds to
1617  only one column of luma samples, while the remaining columns each correspond
1618  to two (see Figure~\ref{fig:pic_odd}).
1619 In this case, if the width is even, the last column again corresponds to only
1620  one column of luma samples (see Figure~\ref{fig:pic_odd_even}).
1621
1622 A similar process is followed with the rows of a picture region of odd height
1623  encoded in the 4:2:0 format.
1624 If the Y offset is even, each row of chroma samples corresponds to two rows of
1625  luma samples (see Figure~\ref{fig:pic_even}), except with an odd height, where
1626  the last row corresponds to one row of chroma luna samples only (see 
1627  Figure~\ref{fig:pic_even_odd}).
1628 If the offset is odd, then it is the first row of chroma samples which
1629  corresponds to only one row of luma samples, while the remaining rows each
1630  correspond to two (Figure~\ref{fig:pic_odd}), except with an even height, 
1631  where the last row also corresponds to one (Figure~\ref{fig:pic_odd_even}).
1632
1633 Encoders should be aware of these differences in the subsampling when using an
1634  even or odd offset.
1635 In the typical case, with an even width and height, where one expects two rows
1636  or columns of luma samples for every row or column of chroma samples, the
1637  encoder must take care to ensure that the offsets used are both even.
1638
1639 \begin{figure}[htbp]
1640 \begin{center}
1641 \includegraphics[width=\textwidth]{pic_even}
1642 \end{center}
1643 \caption{Pixel correspondence between color planes with even picture 
1644  offset and even picture size}
1645 \label{fig:pic_even}
1646 \end{figure}
1647
1648 \begin{figure}[htbp]
1649 \begin{center}
1650 \includegraphics[width=\textwidth]{pic_even_odd}
1651 \end{center}
1652 \caption{Pixel correspondence with even picture offset and 
1653  odd picture size}
1654 \label{fig:pic_even_odd}
1655 \end{figure}
1656
1657 \begin{figure}[htbp]
1658 \begin{center}
1659 \includegraphics[width=\textwidth]{pic_odd}
1660 \end{center}
1661 \caption{Pixel correspondence with odd picture offset and 
1662  odd picture size}
1663 \label{fig:pic_odd}
1664 \end{figure}
1665
1666 \begin{figure}[htbp]
1667 \begin{center}
1668 \includegraphics[width=\textwidth]{pic_odd_even}
1669 \end{center}
1670 \caption{Pixel correspondence with odd picture offset and 
1671  even picture size}
1672 \label{fig:pic_odd_even}
1673 \end{figure}
1674
1675
1676 \chapter{Bitpacking Convention}
1677 \label{sec:bitpacking}
1678
1679 \section{Overview}
1680
1681 The Theora codec uses relatively unstructured raw packets containing
1682  binary integer fields of arbitrary width.
1683 Logically, each packet is a bitstream in which bits are written one-by-one by
1684  the encoder and then read one-by-one in the same order by the decoder.
1685 Most current binary storage arrangements group bits into a native storage unit
1686  of eight bits (octets), sixteen bits, thirty-two bits, or less commonly other
1687  fixed sizes.
1688 The Theora bitpacking convention specifies the correct mapping of the logical
1689  packet bitstream into an actual representation in fixed-width units.
1690
1691 \subsection{Octets and Bytes}
1692
1693 In most contemporary architectures, a `byte' is synonymous with an `octect',
1694  that is, eight bits.
1695 For purposes of the bitpacking convention, a byte implies the smallest native
1696  integer storage representation offered by a platform.
1697 Modern file systems invariably offer bytes as the fundamental atom of storage.
1698
1699 The most ubiquitous architectures today consider a `byte' to be an octet.
1700 Note, however, that the Theora bitpacking convention is still well defined for
1701  any native byte size; an implementation can use the native bit-width of a
1702  given storage system.
1703 This document assumes that a byte is one octet for purposes of example only.
1704
1705 \subsection{Words and Byte Order}
1706
1707 A `word' is an integer size that is a grouped multiple of the byte size.
1708 Most architectures consider a word to be a group of two, four, or eight bytes.
1709 Each byte in the word can be ranked by order of `significance', e.g.\ the
1710  significance of the bits in each byte when storing a binary integer in the
1711  word.
1712 Several byte orderings are possible in a word.
1713 The common ones are
1714 \begin{itemize}
1715 \item{Big-endian:}
1716 in which the most significant byte comes first, e.g.\ 3-2-1-0,
1717 \item{Little-endian:}
1718 in which the least significant byte comes first, e.g.\ 0-1-2-3, and
1719 \item{Mixed-endian:}
1720 one of the less-common orderings that cannot be put into the above two
1721  categories, e.g.\ 3-1-2-0 or 0-2-1-3.
1722 \end{itemize}
1723
1724 The Theora bitpacking convention specifies storage and bitstream manipulation
1725  at the byte, not word, level.
1726 Thus host word ordering is of a concern only during optimization, when writing
1727  code that operates on a word of storage at a time rather than a byte.
1728 Logically, bytes are always encoded and decoded in order from byte zero through
1729  byte $n$.
1730
1731 \subsection{Bit Order}
1732
1733 A byte has a well-defined `least significant' bit (LSb), which is the only bit
1734  set when the byte is storing the two's complement integer value $+1$.
1735 A byte's `most significant' bit (MSb) is at the opposite end.
1736 Bits in a byte are numbered from zero at the LSb to $n$ for the MSb, where
1737  $n=7$ in an octet.
1738
1739 \section{Coding Bits into Bytes}
1740
1741 The Theora codec needs to encode arbitrary bit-width integers from zero to 32
1742  bits wide into packets.
1743 These integer fields are not aligned to the boundaries of the byte
1744  representation; the next field is read at the bit position immediately
1745  after the end of the previous field.
1746
1747 The decoder logically unpacks integers by first reading the MSb of a binary
1748  integer from the logical bitstream, followed by the next most significant
1749  bit, etc., until the required number of bits have been read.
1750 When unpacking the bytes into bits, the decoder begins by reading the MSb of
1751  the integer to be read from the most significant unread bit position of the
1752  source byte, followed by the next-most significant bit position of the
1753  destination integer, and so on up to the requested number of bits.
1754 Note that this differs from the Vorbis I codec, which
1755  begins decoding with the LSb of the source integer, reading it from the
1756  LSb of the source byte.
1757 When all the bits of the current source byte are read, decoding continues with
1758  the MSb of the next byte.
1759 Any unfilled bits in the last byte of the packet MUST be cleared to zero by the
1760  encoder.
1761
1762 \subsection{Signedness}
1763
1764 The binary integers decoded by the above process may be either signed or
1765  unsigned.
1766 This varies from integer to integer, and this specification
1767  indicates how each value should be interpreted as it is read.
1768 That is, depending on context, the three bit binary pattern \bin{111} can be
1769  taken to represent either `$7$' as an unsigned integer or `$-1$' as a signed,
1770  two's complement integer.
1771
1772 \subsection{Encoding Example}
1773
1774 The following example shows the state of an (8-bit) byte stream after several
1775  binary integers are encoded, including the location of the put pointer for the
1776  next bit to write to and the total length of the stream in bytes.
1777
1778 Encode the 4 bit unsigned integer value `12' (\bin{1100}) into an empty byte
1779  stream.
1780
1781 \begin{tabular}{r|ccccccccl}
1782 \multicolumn{1}{r}{}& &&&&$\downarrow$&&&& \\
1783          & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 & \\\cline{1-9}
1784 byte 0   & \textbf{1} & \textbf{1} & \textbf{0} & \textbf{0} &
1785                            0 & 0 & 0 & 0 & $\leftarrow$     \\
1786 byte 1   & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &                  \\
1787 byte 2   & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &                  \\
1788 byte 3   & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &                  \\
1789 \multicolumn{1}{c|}{$\vdots$}&\multicolumn{8}{c}{$\vdots$}& \\
1790 byte $n$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
1791 byte stream length: 1 byte
1792 \end{tabular}
1793 \vspace{\baselineskip}
1794
1795 Continue by encoding the 3 bit signed integer value `-1' (\bin{111}).
1796
1797 \begin{tabular}{r|ccccccccl}
1798 \multicolumn{1}{r}{} &&&&&&&&$\downarrow$& \\
1799          & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 & \\\cline{1-9}
1800 byte 0   & \textbf{1} & \textbf{1} & \textbf{0} & \textbf{0} &
1801            \textbf{1} & \textbf{1} & \textbf{1} & 0 & $\leftarrow$ \\
1802 byte 1   & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &                         \\
1803 byte 2   & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &                         \\
1804 byte 3   & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &                         \\
1805 \multicolumn{1}{c|}{$\vdots$}&\multicolumn{8}{c}{$\vdots$}&        \\
1806 byte $n$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
1807 byte stream length: 1 byte
1808 \end{tabular}
1809 \vspace{\baselineskip}
1810
1811 Continue by encoding the 7 bit integer value `17' (\bin{0010001}).
1812
1813 \begin{tabular}{r|ccccccccl}
1814 \multicolumn{1}{r}{} &&&&&&&$\downarrow$&& \\
1815          & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 & \\\cline{1-9}
1816 byte 0   & \textbf{1} & \textbf{1} & \textbf{0} & \textbf{0} &
1817            \textbf{1} & \textbf{1} & \textbf{1} & \textbf{0} & \\
1818 byte 1   & \textbf{0} & \textbf{1} & \textbf{0} & \textbf{0} &
1819            \textbf{0} & \textbf{1} & 0 & 0 & $\leftarrow$      \\
1820 byte 2   & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &                     \\
1821 byte 3   & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &                     \\
1822 \multicolumn{1}{c|}{$\vdots$}&\multicolumn{8}{c}{$\vdots$}&    \\
1823 byte $n$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
1824 byte stream length: 2 bytes
1825 \end{tabular}
1826 \vspace{\baselineskip}
1827
1828 Continue by encoding the 13 bit integer value `6969' (\bin{11011\ 00111001}).
1829
1830 \begin{tabular}{r|ccccccccl}
1831 \multicolumn{1}{r}{} &&&&$\downarrow$&&&&& \\
1832          & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 &            \\\cline{1-9}
1833 byte 0   & \textbf{1} & \textbf{1} & \textbf{0} & \textbf{0} &
1834            \textbf{1} & \textbf{1} & \textbf{1} & \textbf{0} & \\
1835 byte 1   & \textbf{0} & \textbf{1} & \textbf{0} & \textbf{0} &
1836            \textbf{0} & \textbf{1} & \textbf{1} & \textbf{1} & \\
1837 byte 2   & \textbf{0} & \textbf{1} & \textbf{1} & \textbf{0} &
1838            \textbf{0} & \textbf{1} & \textbf{1} & \textbf{1} & \\
1839 byte 3   & \textbf{0} & \textbf{0} & \textbf{1} &
1840                        0 & 0 & 0 & 0 & 0 & $\leftarrow$        \\
1841 \multicolumn{1}{c|}{$\vdots$}&\multicolumn{8}{c}{$\vdots$}&    \\
1842 byte $n$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
1843 byte stream length: 4 bytes
1844 \end{tabular}
1845 \vspace{\baselineskip}
1846
1847 \subsection{Decoding Example}
1848
1849 The following example shows the state of the (8-bit) byte stream encoded in the
1850  previous example after several binary integers are decoded, including the
1851  location of the get pointer for the next bit to read.
1852
1853 Read a two bit unsigned integer from the example encoded above.
1854
1855 \begin{tabular}{r|ccccccccl}
1856 \multicolumn{1}{r}{} &&&$\downarrow$&&&&&&              \\
1857          & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 &              \\\cline{1-9}
1858 byte 0   & \textbf{1} & \textbf{1} & 0 & 0 & 1 & 1 & 1 & 0 & $\leftarrow$ \\
1859 byte 1   & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 &              \\
1860 byte 2   & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 &              \\
1861 byte 3   & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 &
1862 byte stream length: 4 bytes
1863 \end{tabular}
1864 \vspace{\baselineskip}
1865
1866 Value read: 3 (\bin{11}).
1867
1868 Read another two bit unsigned integer from the example encoded above.
1869
1870 \begin{tabular}{r|ccccccccl}
1871 \multicolumn{1}{r}{} &&&&&$\downarrow$&&&&              \\
1872          & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 &              \\\cline{1-9}
1873 byte 0   & \textbf{1} & \textbf{1} & \textbf{0} & \textbf{0} &
1874                            1 & 1 & 1 & 0 & $\leftarrow$ \\
1875 byte 1   & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 &              \\
1876 byte 2   & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 &              \\
1877 byte 3   & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 &
1878 byte stream length: 4 bytes
1879 \end{tabular}
1880 \vspace{\baselineskip}
1881
1882 Value read: 0 (\bin{00}).
1883
1884 Two things are worth noting here.
1885 \begin{itemize}
1886 \item
1887 Although these four bits were originally written as a single four-bit integer,
1888  reading some other combination of bit-widths from the bitstream is well
1889  defined.
1890 No artificial alignment boundaries are maintained in the bitstream.
1891 \item
1892 The first value is the integer `$3$' only because the context stated we were
1893  reading an unsigned integer.
1894 Had the context stated we were reading a signed integer, the returned value
1895  would have been the integer `$-1$'.
1896 \end{itemize}
1897
1898 \subsection{End-of-Packet Alignment}
1899
1900 The typical use of bitpacking is to produce many independent byte-aligned
1901  packets which are embedded into a larger byte-aligned container structure,
1902  such as an Ogg transport bitstream.
1903 Externally, each bitstream encoded as a byte stream MUST begin and end on a
1904  byte boundary.
1905 Often, the encoded packet bitstream is not an integer number of bytes, and so
1906  there is unused space in the last byte of a packet.
1907
1908 %r: I think the generality here is necessary to be consistent with our assertions
1909 %r: elsewhere about being independent of transport and byte width
1910 When a Theora encoder produces packets for embedding in a byte-aligned
1911  container, unused space in the last byte of a packet is always zeroed during
1912  the encoding process.
1913 Thus, should this unused space be read, it will return binary zeroes.
1914 There is no marker pattern or stuffing bits that will allow the decoder to
1915  obtain the exact size, in bits, of the original bitstream.
1916 This knowledge is not required for decoding.
1917
1918 Attempting to read past the end of an encoded packet results in an
1919  `end-of-packet' condition.
1920 Any further read operations after an `end-of-packet' condition shall also
1921  return `end-of-packet'.
1922 Unlike Vorbis, Theora does not use truncated packets as a normal mode of
1923  operation.
1924 Therefore if a decoder encounters the `end-of-packet' condition during normal
1925  decoding, it may attempt to use the bits that were read to recover as much of
1926  encoded data as possible, signal a warning or error, or both.
1927
1928 \subsection{Reading Zero Bit Integers}
1929
1930 Reading a zero bit integer returns the value `$0$' and does not increment
1931  the stream pointer.
1932 Reading to the end of the packet, but not past the end, so that an
1933  `end-of-packet' condition is not triggered, and then reading a zero bit
1934  integer shall succeed, returning `$0$', and not trigger an `end-of-packet'
1935  condition.
1936 Reading a zero bit integer after a previous read sets the `end-of-packet'
1937  condition shall fail, also returning `end-of-packet'.
1938
1939 \chapter{Bitstream Headers}
1940 \label{sec:headers}
1941
1942 A Theora bitstream begins with three header packets.
1943 The header packets are, in order, the identification header, the comment
1944  header, and the setup header.
1945 All are required for decode compliance.
1946 An end-of-packet condition encountered while decoding the identification or
1947  setup header packets renders the stream undecodable.
1948 An end-of-packet condition encountered while decode the comment header is a
1949  non-fatal error condition, and MAY be ignored by a decoder.
1950
1951 \paragraph{VP3 Compatibility}
1952
1953 VP3 relies on the headers provided by its container, usually either AVI or
1954  Quicktime.
1955 As such, several parameters available in these headers are not available to VP3
1956  streams.
1957 These are indicated as they appear in the sections below.
1958
1959 \section{Common Header Decode}
1960 \label{sub:common-header}
1961
1962 \begin{figure}[Htbp]
1963 \begin{center}
1964 \begin{verbatim}
1965   0                   1                   2                   3   
1966   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 
1967  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1968  |  header type  |      `t'      |      `h'      |      `e'      |
1969  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1970  |      `o'      |      `r'      |      `a'      |     data...   |
1971  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1972  |                 ... header-specific data ...                  |
1973  |                              ...                              |
1974  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1975 \end{verbatim}
1976 \end{center}
1977 \caption{Common Header Packet Layout}
1978 \label{fig:commonheader}
1979 \end{figure}
1980
1981
1982 \paragraph{Input parameters:} None.
1983
1984 \paragraph{Output parameters:}\hfill\\*
1985 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
1986 \multicolumn{1}{c}{Name} &
1987 \multicolumn{1}{c}{Type} &
1988 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
1989 \multicolumn{1}{c}{Signed?} &
1990 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
1991 \bitvar{HEADERTYPE} & Integer & 8 & No & The type of the header being
1992  decoded. \\
1993 \bottomrule\end{tabularx}
1994
1995 \paragraph{Variables used:} None.
1996 \medskip
1997
1998 Each header packet begins with the same header fields, which are decoded as
1999  follows:
2000
2001 \begin{enumerate}
2002 \item
2003 Read an 8-bit unsigned integer as \bitvar{HEADERTYPE}.
2004 If the most significant bit of this integer is not set, then stop.
2005 This is not a header packet.
2006 \item
2007 Read 6 8-bit unsigned integers.
2008 If these do not have the values \hex{74}, \hex{68}, \hex{65}, \hex{6F},
2009  \hex{72}, and \hex{61}, respectively, then stop.
2010 This stream is not decodable by this specification.
2011 These values correspond to the ASCII values of the characters `t', `h', `e',
2012  `o', `r', and `a'.
2013 \end{enumerate}
2014
2015 Decode continues according to \bitvar{HEADERTYPE}.
2016 The identification header is type \hex{80}, the comment header is type
2017  \hex{81}, and the setup header is type \hex{82}.
2018 These packets must occur in the order: identification, comment, setup.
2019 %r: I clarified the initial-bit scheme here
2020 %TBT: Dashes let the reader know they'll have to pick up the rest of the
2021 %TBT:  sentence after the explanatory phrase.
2022 %TBT: Otherwise it just sounds like the bit must exist.
2023 All header packets have the most significant bit of the type
2024  field---which is the initial bit in the packet---set.
2025 This distinguishes them from video data packets in which the first bit
2026  is unset.
2027 % extra header packets are a feature Dan argued for way back when for 
2028 % backward-compatible extensions (and icc colourspace for example)
2029 % I think it's reasonable
2030 %TBT: You can always just stick more stuff in the setup header.
2031 Packets with other header types (\hex{83}--\hex{FF}) are reserved and MUST be
2032  ignored.
2033
2034 \section{Identification Header Decode}
2035 \label{sec:idheader}
2036
2037 \begin{figure}[Htbp]
2038 \begin{center}
2039 \begin{verbatim}
2040   0                   1                   2                   3   
2041   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 
2042  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2043  |      0x80     |      `t'      |      `h'      |      `e'      |
2044  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2045  |      `o'      |      `r'      |      `a'      |     VMAJ      |
2046  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2047  |     VMIN      |     VREV      |           FMBW                |
2048  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2049  |             FMBH              |           PICW...             |
2050  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2051  |   ...PICW     |                 PICH                          |
2052  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2053  |     PICX      |     PICY      |            FRN...             |
2054  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2055  |           ...FRN              |            FRD...             |
2056  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2057  |           ...FRD              |            PARN...            |
2058  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2059  |    ...PARN    |                   PARD                        |
2060  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2061  |      CS       |                  NOMBR                        |
2062  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2063  |    QUAL   | KFGSHIFT| PF| Res |
2064  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2065 \end{verbatim}
2066 \end{center}
2067 \caption{Identification Header Packet}
2068 \label{fig:idheader}
2069 \end{figure}
2070
2071 \paragraph{Input parameters:} None.
2072
2073 \paragraph{Output parameters:}\hfill\\*
2074 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2075 \multicolumn{1}{c}{Name} &
2076 \multicolumn{1}{c}{Type} &
2077 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2078 \multicolumn{1}{c}{Signed?} &
2079 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2080 \bitvar{VMAJ}     & Integer &  8 & No & The major version number. \\
2081 \bitvar{VMIN}     & Integer &  8 & No & The minor version number. \\
2082 \bitvar{VREV}     & Integer &  8 & No & The version revision number. \\
2083 \bitvar{FMBW}     & Integer & 16 & No & The width of the frame in macro
2084  blocks. \\
2085 \bitvar{FMBH}     & Integer & 16 & No & The height of the frame in macro
2086  blocks. \\
2087 \bitvar{NSBS}     & Integer & 32 & No & The total number of super blocks in a
2088  frame. \\
2089 \bitvar{NBS}      & Integer & 36 & No & The total number of blocks in a
2090  frame. \\
2091 \bitvar{NMBS}     & Integer & 32 & No & The total number of macro blocks in a
2092  frame. \\
2093 \bitvar{PICW}     & Integer & 20 & No & The width of the picture region in
2094  pixels. \\
2095 \bitvar{PICH}     & Integer & 20 & No & The height of the picture region in
2096  pixels. \\
2097 \bitvar{PICX}     & Integer &  8 & No & The X offset of the picture region in
2098  pixels. \\
2099 \bitvar{PICY}     & Integer &  8 & No & The Y offset of the picture region in
2100  pixels. \\
2101 \bitvar{FRN}      & Integer & 32 & No & The frame-rate numerator. \\
2102 \bitvar{FRD}      & Integer & 32 & No & The frame-rate denominator. \\
2103 \bitvar{PARN}     & Integer & 24 & No & The pixel aspect-ratio numerator. \\
2104 \bitvar{PARD}     & Integer & 24 & No & The pixel aspect-ratio denominator. \\
2105 \bitvar{CS}       & Integer &  8 & No & The color space. \\
2106 \bitvar{PF}       & Integer &  2 & No & The pixel format. \\
2107 \bitvar{NOMBR}    & Integer & 24 & No & The nominal bitrate of the stream, in
2108  bits per second. \\
2109 \bitvar{QUAL}     & Integer &  6 & No & The quality hint. \\
2110 \bitvar{KFGSHIFT} & Integer &  5 & No & The amount to shift the key frame
2111  number by in the granule position. \\
2112 \bottomrule\end{tabularx}
2113
2114 \paragraph{Variables used:} None.
2115 \medskip
2116
2117 The identification header is a short header with only a few fields used to
2118  declare the stream definitively as Theora and provide detailed information
2119  about the format of the fully decoded video data.
2120 The identification header is decoded as follows:
2121
2122 \begin{enumerate}
2123 \item
2124 Decode the common header fields according to the procedure described in
2125  Section~\ref{sub:common-header}.
2126 If \bitvar{HEADERTYPE} returned by this procedure is not \hex{80}, then stop.
2127 This packet is not the identification header.
2128 \item
2129 Read an 8-bit unsigned integer as \bitvar{VMAJ}.
2130 If \bitvar{VMAJ} is not $3$, then stop.
2131 This stream is not decodable according to this specification.
2132 \item
2133 Read an 8-bit unsigned integer as \bitvar{VMIN}.
2134 If \bitvar{VMIN} is not $2$, then stop.
2135 This stream is not decodable according to this specification.
2136 \item
2137 Read an 8-bit unsigned integer as \bitvar{VREV}.
2138 If \bitvar{VREV} is greater than $1$, then this stream
2139 may contain optional features or interpretational changes 
2140 documented in a future version of this specification.
2141 Regardless of the value of \bitvar{VREV}, the stream is decodable 
2142 according to this specification.
2143 \item
2144 Read a 16-bit unsigned integer as \bitvar{FMBW}.
2145 This MUST be greater than zero.
2146 This specifies the width of the coded frame in macro blocks.
2147 The actual width of the frame in pixels is $\bitvar{FMBW}*16$.
2148 \item
2149 Read a 16-bit unsigned integer as \bitvar{FMBH}.
2150 This MUST be greater than zero.
2151 This specifies the height of the coded frame in macro blocks.
2152 The actual height of the frame in pixels is $\bitvar{FMBH}*16$.
2153 \item
2154 Read a 24-bit unsigned integer as \bitvar{PICW}.
2155 This MUST be no greater than $(\bitvar{FMBW}*16)$.
2156 Note that 24 bits are read, even though only 20 bits are sufficient to specify
2157  any value of the picture width.
2158 This is done to preserve octet alignment in this header, to allow for a
2159  simplified parser implementation.
2160 \item
2161 Read a 24-bit unsigned integer as \bitvar{PICH}.
2162 This MUST be no greater than $(\bitvar{FMBH}*16)$.
2163 Together with \bitvar{PICW}, this specifies the size of the displayable picture
2164  region within the coded frame.
2165 See Figure~\ref{fig:pic-frame}.
2166 Again, 24 bits are read instead of 20.
2167 \item
2168 Read an 8-bit unsigned integer as \bitvar{PICX}.
2169 This MUST be no greater than $(\bitvar{FMBW}*16-\bitvar{PICX})$.
2170 \item
2171 Read an 8-bit unsigned integer as \bitvar{PICY}.
2172 This MUST be no greater than $(\bitvar{FMBH}*16-\bitvar{PICY})$.
2173 Together with \bitvar{PICX}, this specifies the location of the lower-left
2174  corner of the displayable picture region.
2175 See Figure~\ref{fig:pic-frame}.
2176 \item
2177 Read a 32-bit unsigned integer as \bitvar{FRN}.
2178 This MUST be greater than zero.
2179 \item
2180 Read a 32-bit unsigned integer as \bitvar{FRD}.
2181 This MUST be greater than zero.
2182 Theora is a fixed-frame rate video codec.
2183 Frames are sampled at the constant rate of $\frac{\bitvar{FRN}}{\bitvar{FRD}}$
2184  frames per second.
2185 The presentation time of the first frame is at zero seconds.
2186 No mechanism is provided to specify a non-zero offset for the initial
2187  frame.
2188 \item
2189 Read a 24-bit unsigned integer as \bitvar{PARN}.
2190 \item
2191 Read a 24-bit unsigned integer as \bitvar{PARD}.
2192 Together with \bitvar{PARN}, these specify the aspect ratio of the pixels
2193  within a frame, defined as the ratio of the physical width of a pixel to its
2194  physical height.
2195 This is given by the ratio $\bitvar{PARN}:\bitvar{PARD}$.
2196 If either of these fields are zero, this indicates that pixel aspect ratio
2197  information was not available to the encoder.
2198 In this case it MAY be specified by the application via an external means, or
2199  a default value of $1:1$ MAY be used.
2200 \item
2201 Read an 8-bit unsigned integer as \bitvar{CS}.
2202 This is a value from an enumerated list of the available color spaces, given in
2203  Table~\ref{tab:colorspaces}.
2204 The `Undefined' value indicates that color space information was not available
2205  to the encoder.
2206 It MAY be specified by the application via an external means.
2207 If a reserved value is given, a decoder MAY refuse to decode the stream.
2208 \begin{table}[htbp]
2209 \begin{center}
2210 \begin{tabular*}{215pt}{cl@{\extracolsep{\fill}}c}\toprule
2211 Value    & Color Space                               \\\midrule
2212 $0$      & Undefined.                                \\
2213 $1$      & Rec.~470M (see Section~\ref{sec:470m}).   \\
2214 $2$      & Rec.~470BG (see Section~\ref{sec:470bg}). \\
2215 $3$      & Reserved.                                 \\
2216 $\vdots$ &                                           \\
2217 $255$    &                                           \\
2218 \bottomrule\end{tabular*}
2219 \end{center}
2220 \caption{Enumerated List of Color Spaces}
2221 \label{tab:colorspaces}
2222 \end{table}
2223 \item
2224 Read a 24-bit unsigned integer as \bitvar{NOMBR} signifying a rate in bits
2225 per second. Rates equal to or greater than $2^{24}-1$ bits per second are
2226 represented as $2^{24}-1$. 
2227 The \bitvar{NOMBR} field is used only as a hint.
2228 For pure VBR streams, this value may be considerably off.
2229 The field MAY be set to zero to indicate that the encoder did not care to
2230 speculate. 
2231 \item
2232 Read a 6-bit unsigned integer as \bitvar{QUAL}.
2233 This value is used to provide a hint as to the relative quality of the stream
2234  when compared to others produced by the same encoder.
2235 Larger values indicate higher quality.
2236 This can be used, for example, to select among several streams containing the
2237  same material encoded with different settings.
2238 \item
2239 Read a 5-bit unsigned integer as \bitvar{KFGSHIFT}.
2240 The \bitvar{KFGSHIFT} is used to partition the granule position associated with
2241  each packet into two different parts.
2242 The frame number of the last key frame, starting from zero, is stored in the
2243  upper $64-\bitvar{KFGSHIFT}$ bits, while the lower \bitvar{KFGSHIFT} bits
2244  contain the number of frames since the last keyframe.
2245 Complete details on the granule position mapping are specified in Section~REF.
2246 \item
2247 Read a 2-bit unsigned integer as \bitvar{PF}.
2248 The \bitvar{PF} field contains a value from an enumerated list of the available
2249  pixel formats, given in Table~\ref{tab:pixel-formats}.
2250 If the reserved value $1$ is given, stop.
2251 This stream is not decodable according to this specification.
2252
2253 \begin{table}[htbp]
2254 \begin{center}
2255 \begin{tabular*}{215pt}{cl@{\extracolsep{\fill}}c}\toprule
2256 Value & Pixel Format             \\\midrule
2257 $0$   & 4:2:0 (see Section~\ref{sec:420}). \\
2258 $1$   & Reserved.                \\
2259 $2$   & 4:2:2 (see Section~\ref{sec:422}). \\
2260 $3$   & 4:4:4 (see Section~\ref{sec:444}). \\
2261 \bottomrule\end{tabular*}
2262 \end{center}
2263 \caption{Enumerated List of Pixel Formats}
2264 \label{tab:pixel-formats}
2265 \end{table}
2266
2267 \item
2268 Read a 3-bit unsigned integer.
2269 These bits are reserved.
2270 If this value is not zero, then stop.
2271 This stream is not decodable according to this specification.
2272 \item
2273 Assign \bitvar{NSBS} a value according to \bitvar{PF}, as given by
2274  Table~\ref{tab:nsbs-for-pf}.
2275
2276 \begin{table}[bt]
2277 \begin{center}
2278 \begin{tabular}{cc}\toprule
2279 \bitvar{PF} & \bitvar{NSBS}                                     \\\midrule
2280 $0$         & $\begin{aligned}
2281 &((\bitvar{FMBW}+1)//2)*((\bitvar{FMBH}+1)//2)\\
2282 & +2*((\bitvar{FMBW}+3)//4)*((\bitvar{FMBH}+3)//4)
2283 \end{aligned}$                                                  \\\midrule
2284 $2$         & $\begin{aligned}
2285 &((\bitvar{FMBW}+1)//2)*((\bitvar{FMBH}+1)//2)\\
2286 & +2*((\bitvar{FMBW}+3)//4)*((\bitvar{FMBH}+1)//2)
2287 \end{aligned}$                                                  \\\midrule
2288 $3$         & $3*((\bitvar{FMBW}+1)//2)*((\bitvar{FMBH}+1)//2)$ \\
2289 \bottomrule\end{tabular}
2290 \end{center}
2291 \caption{Number of Super Blocks for each Pixel Format}
2292 \label{tab:nsbs-for-pf}
2293 \end{table}
2294
2295 \item
2296 Assign \bitvar{NBS} a value according to \bitvar{PF}, as given by
2297  Table~\ref{tab:nbs-for-pf}.
2298
2299 \begin{table}[tb]
2300 \begin{center}
2301 \begin{tabular}{cc}\toprule
2302 \bitvar{PF} & \bitvar{NBS}                     \\\midrule
2303 $0$         & $6*\bitvar{FMBW}*\bitvar{FMBH}$  \\\midrule
2304 $2$         & $8*\bitvar{FMBW}*\bitvar{FMBH}$  \\\midrule
2305 $3$         & $12*\bitvar{FMBW}*\bitvar{FMBH}$ \\
2306 \bottomrule\end{tabular}
2307 \end{center}
2308 \caption{Number of Blocks for each Pixel Format}
2309 \label{tab:nbs-for-pf}
2310 \end{table}
2311
2312 \item
2313 Assign \bitvar{NMBS} the value $(\bitvar{FMBW}*\bitvar{FMBH})$.
2314
2315 \end{enumerate}
2316
2317 \paragraph{VP3 Compatibility}
2318
2319 VP3 does not correctly handle frame sizes that are not a multiple of 16.
2320 Thus, \bitvar{PICW} and \bitvar{PICH} should be set to the frame width and
2321  height in pixels, respectively, and \bitvar{PICX} and \bitvar{PICY} should be
2322  set to zero.
2323 VP3 headers do not specify a color space.
2324 VP3 only supports the 4:2:0 pixel format.
2325
2326 \section{Comment Header}
2327 \label{sec:commentheader}
2328
2329 The Theora comment header is the second of three header packets that begin a
2330  Theora stream.
2331 It is meant for short text comments, not aribtrary metadata; arbitrary metadata
2332  belongs in a separate logical stream that provides greater structure and
2333  machine parseability.
2334
2335 %r: I tried to morph this a little more in the direction of our 
2336 %   application space 
2337 The comment field is meant to be used much like someone jotting a quick note on
2338  the label of a video.
2339 It should be a little information to remember the disc or tape by and explain it to
2340  others; a short, to-the-point text note that can be more than a couple words,
2341  but isn't going to be more than a short paragraph.
2342 The essentials, in other words, whatever they turn out to be, e.g.:
2343
2344 %TODO: Example
2345
2346 The comment header is stored as a logical list of eight-bit clean vectors; the
2347  number of vectors is bounded at $2^{32}-1$ and the length of each vector is
2348  limited to $2^{32}-1$ bytes.
2349 The vector length is encoded; the vector contents themselves are not null
2350  terminated.
2351 In addition to the vector list, there is a single vector for a vendor name,
2352  also eight-bit clean with a length encoded in 32 bits.
2353 %TODO: The 1.0 release of libtheora sets the vendor string to ...
2354
2355 \subsection{Comment Length Decode}
2356 \label{sub:comment-len}
2357
2358 \begin{figure}
2359 \begin{center}
2360 \begin{tabular}{ | c | c | }
2361  \hline
2362  4 byte length &
2363  UTF-8 encoded string ...\\
2364  \hline
2365 \end{tabular}
2366 \end{center}
2367 \caption{Length encoded string layout}
2368 \label{fig:comment-len}
2369 \end{figure}
2370
2371 \paragraph{Input parameters:} None.
2372
2373 \paragraph{Output parameters:}\hfill\\*
2374 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2375 \multicolumn{1}{c}{Name} &
2376 \multicolumn{1}{c}{Type} &
2377 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2378 \multicolumn{1}{c}{Signed?} &
2379 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2380 \bitvar{LEN}  & Integer & 32 & No & A single 32-bit length value. \\
2381 \bottomrule\end{tabularx}
2382
2383 \paragraph{Variables used:}\hfill\\*
2384 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2385 \multicolumn{1}{c}{Name} &
2386 \multicolumn{1}{c}{Type} &
2387 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2388 \multicolumn{1}{c}{Signed?} &
2389 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2390 \locvar{LEN0} & Integer &  8 & No & The first octet of the string length. \\
2391 \locvar{LEN1} & Integer &  8 & No & The second octet of the string length. \\
2392 \locvar{LEN2} & Integer &  8 & No & The third octet of the string length. \\
2393 \locvar{LEN3} & Integer &  8 & No & The fourth octet of the string
2394  length. \\
2395 \bottomrule\end{tabularx}
2396 \medskip
2397
2398 A single comment vector is decoded as follows:
2399
2400 \begin{enumerate}
2401 \item
2402 Read an 8-bit unsigned integer as \locvar{LEN0}.
2403 \item
2404 Read an 8-bit unsigned integer as \locvar{LEN1}.
2405 \item
2406 Read an 8-bit unsigned integer as \locvar{LEN2}.
2407 \item
2408 Read an 8-bit unsigned integer as \locvar{LEN3}.
2409 \item
2410 Assign \bitvar{LEN} the value $(\locvar{LEN0}+(\locvar{LEN1}<<8)+
2411  (\locvar{LEN2}<<16)+(\locvar{LEN3}<<24))$.
2412 This construction is used so that on platforms with 8-bit bytes, the memory
2413  organization of the comment header is identical with that of Vorbis I,
2414  allowing for common parsing code despite the different bit packing
2415  conventions.
2416 \end{enumerate}
2417
2418 \subsection{Comment Header Decode}
2419
2420 \begin{figure}
2421 \begin{center}
2422 \begin{tabular}{ | c | }
2423   \hline
2424   vendor string \\ \hline
2425   number of comments \\ \hline
2426   comment string \\ \hline
2427   comment string \\ \hline
2428   ... \\
2429   \hline
2430 \end{tabular}
2431 \end{center}
2432 \caption{Comment Header Layout}
2433 \label{fig:commentheader}
2434 \end{figure}
2435
2436 \paragraph{Input parameters:} None.
2437
2438 \paragraph{Output parameters:}\hfill\\*
2439 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2440 \multicolumn{1}{c}{Name} &
2441 \multicolumn{1}{c}{Type} &
2442 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2443 \multicolumn{1}{c}{Signed?} &
2444 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2445 \bitvar{VENDOR}    & \multicolumn{3}{l}{String}       & The vendor string. \\
2446 \bitvar{NCOMMENTS} & Integer                & 32 & No & The number of user
2447  comments. \\
2448 \bitvar{COMMENTS}  & \multicolumn{3}{l}{String Array} & A list of
2449  \bitvar{NCOMMENTS} user comment values. \\
2450 \bottomrule\end{tabularx}
2451
2452 \paragraph{Variables used:}\hfill\\*
2453 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2454 \multicolumn{1}{c}{Name} &
2455 \multicolumn{1}{c}{Type} &
2456 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2457 \multicolumn{1}{c}{Signed?} &
2458 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2459 \locvar{\ci} & Integer & 32 & No & The index of the current user
2460  comment. \\
2461 \bottomrule\end{tabularx}
2462 \medskip
2463
2464 The complete comment header is decoded as follows:
2465
2466 \begin{enumerate}
2467 \item
2468 Decode the common header fields according to the procedure described in
2469  Section~\ref{sub:common-header}.
2470 If \bitvar{HEADERTYPE} returned by this procedure is not \hex{81}, then stop.
2471 This packet is not the comment header.
2472 \item
2473 Decode the length of the vendor string using the procedure given in
2474  Section~\ref{sub:comment-len} into \bitvar{LEN}.
2475 \item
2476 Read \bitvar{LEN} 8-bit unsigned integers.
2477 \item
2478 Set the string \bitvar{VENDOR} to the contents of these octets.
2479 \item
2480 Decode the number of user comments using the procedure given in
2481  Section~\ref{sub:comment-len} into \bitvar{LEN}.
2482 \item
2483 Assign \bitvar{NCOMMENTS} the value stored in \bitvar{LEN}.
2484 \item
2485 For each consecutive value of \locvar{\ci} from $0$ to
2486  $(\bitvar{NCOMMENTS}-1)$, inclusive:
2487 \begin{enumerate}
2488 \item
2489 Decode the length of the current user comment using the procedure given in
2490  Section~\ref{sub:comment-len} into \bitvar{LEN}.
2491 \item
2492 Read \bitvar{LEN} 8-bit unsigned integers.
2493 \item
2494 Set the string $\bitvar{COMMENTS}[\locvar{\ci}]$ to the contents of these
2495  octets.
2496 \end{enumerate}
2497 \end{enumerate}
2498
2499 The comment header comprises the entirety of the second header packet.
2500 Unlike the first header packet, it is not generally the only packet on the
2501  second page and may span multiple pages.
2502 The length of the comment header packet is (practically) unbounded.
2503 The comment header packet is not optional; it must be present in the stream
2504  even if it is logically empty.
2505
2506 %TODO: \paragraph{VP3 Compatibility}
2507
2508 \subsection{User Comment Format}
2509
2510 The user comment vectors are structured similarly to a UNIX environment
2511  variable.
2512 That is, comment fields consist of a field name and a corresponding value and
2513  look like:
2514 \begin{center}
2515 \begin{tabular}{rcl}
2516 $\bitvar{COMMENTS}[0]$ & = & ``TITLE=the look of Theora" \\
2517 $\bitvar{COMMENTS}[1]$ & = & ``DIRECTOR=me"
2518 \end{tabular}
2519 \end{center}
2520
2521 The field name is case-insensitive and MUST consist of ASCII characters
2522  \hex{20} through \hex{7D}, \hex{3D} (`=') excluded.
2523 ASCII \hex{41} through \hex{5A} inclusive (characters `A'--`Z') are to be
2524  considered equivalent to ASCII \hex{61} through \hex{7A} inclusive
2525  (characters `a'--`z').
2526 An entirely empty field name---one that is zero characters long---is not
2527  disallowed.
2528
2529 The field name is immediately followed by ASCII \hex{3D} (`='); this equals
2530  sign is used to terminate the field name.
2531
2532 The data immediately after \hex{3D} until the end of the vector is the eight-bit
2533  clean value of the field contents encoded as a UTF-8 string~\cite{rfc2044}.
2534
2535 Field names MUST NOT be `internationalized'; this is a concession to
2536  simplicity, not an attempt to exclude the majority of the world that doesn't
2537  speak English.
2538 Applications MAY wish to present internationalized versions of the standard
2539  field names listed below to the user, but they are not to be stored in the
2540  bitstream.
2541 Field {\em contents}, however, use the UTF-8 character encoding to allow easy
2542  representation of any language.
2543
2544 Individual `vendors' MAY use non-standard field names within reason.
2545 The proper use of comment fields as human-readable notes has already been
2546  explained.
2547 Abuse will be discouraged.
2548
2549 There is no vendor-specific prefix to `non-standard' field names.
2550 Vendors SHOULD make some effort to avoid arbitrarily polluting the common
2551  namespace.
2552 %"and other bodies"?
2553 %If you're going to be that vague, you might as well not say anything at all.
2554 Xiph.Org and other bodies will generally collect and rationalize the more 
2555  useful tags to help with standardization.
2556
2557 Field names are not restricted to occur only once within a comment header.
2558 %TODO: Example
2559
2560 \paragraph{Field Names}
2561
2562 %r should this be an appendix?
2563
2564 Below is a proposed, minimal list of standard field names with a description of
2565  their intended use.
2566 No field names are mandatory; a comment header may contain one or more, all, or
2567  none of the names in this list.
2568
2569 \begin{description}
2570 \item{TITLE:} Video name.
2571 \item{ARTIST:} Filmmaker or other creator name.
2572 \item{VERSION:} Subtitle, remix info, or other text distinguishing
2573  versions of a video.
2574 \item{DATE:} Date associated with the video. Implementations SHOULD attempt
2575  to parse this field as an ISO 8601 date for machine interpretation and 
2576  conversion.
2577 \item{LOCATION:} Location associated with the video. This is usually the
2578  filming location for non-fiction works.
2579 \item{COPYRIGHT:} Copyright statement.
2580 \item{LICENSE:} Copyright and other licensing information. 
2581  Implementations wishing to do automatic parsing of e.g
2582  of distribution terms SHOULD look here for a URL uniquely defining
2583  the license. If no instance of this field is present, or if no 
2584  instance contains a parseable URL, and implementation MAY look
2585  in the COPYRIGHT field for such a URL.
2586 \item{ORGANIZATION:} Studio name, Publisher, or other organization
2587  involved in the creation of the video.
2588
2589 \item{DIRECTOR:} Director or Filmmaker credit, similar to ARTIST.
2590 \item{PRODUCER:} Producer credit for the video.
2591 \item{COMPOSER:} Music credit for the video.
2592 \item{ACTOR:} Acting credit for the video.
2593
2594 \item{TAG:} subject or category tag, keyword, or other content
2595  classification labels. The value of each instance of this
2596  field SHOULD be treated as a single label, with multiple
2597  instances of the field for multiple tags. The value of
2598  a single field SHOULD NOT be parsed into multiple tags
2599  based on some internal delimeter.
2600 \item{DESCRIPTION:} General description, summary, or blurb.
2601 \end{description}
2602
2603 \section{Setup Header}
2604 \label{sec:setupheader}
2605
2606 The Theora setup header contains the limit values used to drive the loop
2607  filter, the base matrices and scale values used to build the dequantization
2608  tables, and the Huffman tables used to unpack the DCT tokens.
2609 Because the contents of this header are specific to Theora, no concessions have
2610  been made to keep the fields octet-aligned for easy parsing.
2611
2612 \begin{figure}
2613 \begin{center}
2614 \begin{tabular}{ | c | }
2615  \hline
2616  common header block \\ \hline
2617  loop filter table resolution \\ \hline
2618  loop filter table \\ \hline
2619  scale table resolution \\ \hline
2620  AC scale table \\ \hline
2621  DC scale table \\ \hline
2622  number of base matricies \\ \hline
2623  base quatization matricies \\ \hline
2624  ... \\ \hline
2625  quant range interpolation table \\ \hline
2626  DCT token Huffman tables \\
2627  \hline
2628 \end{tabular}
2629 \end{center}
2630 \caption{Setup Header structure}
2631 \label{fig:setupheader}
2632 \end{figure}
2633
2634 \subsection{Loop Filter Limit Table Decode}
2635 \label{sub:loop-filter-limits}
2636
2637 \paragraph{Input parameters:} None.
2638
2639 \paragraph{Output parameters:}\hfill\\*
2640 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2641 \multicolumn{1}{c}{Name} &
2642 \multicolumn{1}{c}{Type} &
2643 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2644 \multicolumn{1}{c}{Signed?} &
2645 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2646 \bitvar{LFLIMS}    & \multicolumn{1}{p{40pt}}{Integer array} &
2647                               7 & No & A 64-element array of loop filter limit
2648  values. \\
2649 \bottomrule\end{tabularx}
2650
2651 \paragraph{Variables used:}\hfill\\*
2652 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2653 \multicolumn{1}{c}{Name} &
2654 \multicolumn{1}{c}{Type} &
2655 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2656 \multicolumn{1}{c}{Signed?} &
2657 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2658 \locvar{\qi}    & Integer &  6 & No & The quantization index. \\
2659 \locvar{NBITS}  & Integer &  3 & No & The size of values being read in the
2660  current table. \\
2661 \bottomrule\end{tabularx}
2662 \medskip
2663
2664 This procedure decodes the table of loop filter limit values used to drive the
2665  loop filter, which is described in Section~\ref{sub:loop-filter-limits}.
2666 It is decoded as follows:
2667
2668 \begin{enumerate}
2669 \item
2670 Read a 3-bit unsigned integer as \locvar{NBITS}.
2671 \item
2672 For each consecutive value of \locvar{\qi} from $0$ to $63$, inclusive:
2673 \begin{enumerate}
2674 \item
2675 Read an \locvar{NBITS}-bit unsigned integer as $\bitvar{LFLIMS}[\locvar{\qi}]$.
2676 \end{enumerate}
2677 \end{enumerate}
2678
2679 \paragraph{VP3 Compatibility}
2680
2681 The loop filter limit values are hardcoded in VP3.
2682 The values used are given in Appendix~\ref{app:vp3-loop-filter-limits}.
2683
2684 \subsection{Quantization Parameters Decode}
2685 \label{sub:quant-params}
2686
2687 \paragraph{Input parameters:} None.
2688
2689 \paragraph{Output parameters:}\hfill\\*
2690 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2691 \multicolumn{1}{c}{Name} &
2692 \multicolumn{1}{c}{Type} &
2693 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2694 \multicolumn{1}{c}{Signed?} &
2695 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2696 \bitvar{ACSCALE} & \multicolumn{1}{p{40pt}}{Integer array} &
2697                              16 & No & A 64-element array of scale values for
2698  AC coefficients for each \qi\ value. \\
2699 \bitvar{DCSCALE} & \multicolumn{1}{p{40pt}}{Integer array} &
2700                              16 & No & A 64-element array of scale values for
2701  the DC coefficient for each \qi\ value. \\
2702 \bitvar{NBMS}    & Integer & 10 & No & The number of base matrices. \\
2703 \bitvar{BMS}     & \multicolumn{1}{p{50pt}}{2D Integer array} &
2704                               8 & No & A $\bitvar{NBMS}\times 64$ array
2705  containing the base matrices. \\
2706 \bitvar{NQRS}    & \multicolumn{1}{p{50pt}}{2D Integer array} &
2707                               6 & No & A $2\times 3$ array containing the
2708  number of quant ranges for a given \qti\ and \pli, respectively.
2709 This is at most $63$. \\
2710 \bitvar{QRSIZES} & \multicolumn{1}{p{50pt}}{3D Integer array} &
2711                               6 & No & A $2\times 3\times 63$ array of the
2712  sizes of each quant range for a given \qti\ and \pli, respectively.
2713 Only the first $\bitvar{NQRS}[\qti][\pli]$ values are used. \\
2714 \bitvar{QRBMIS}  & \multicolumn{1}{p{50pt}}{3D Integer array} &
2715                               9 & No & A $2\times 3\times 64$ array of the
2716  \bmi's used for each quant range for a given \qti\ and \pli, respectively.
2717 Only the first $(\bitvar{NQRS}[\qti][\pli]+1)$ values are used. \\
2718 \bottomrule\end{tabularx}
2719
2720 \paragraph{Variables used:}\hfill\\*
2721 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2722 \multicolumn{1}{c}{Name} &
2723 \multicolumn{1}{c}{Type} &
2724 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2725 \multicolumn{1}{c}{Signed?} &
2726 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2727 \locvar{\qti}    & Integer &  1 & No & A quantization type index.
2728 See Table~\ref{tab:quant-types}.\\
2729 \locvar{\qtj}    & Integer &  1 & No & A quantization type index. \\
2730 \locvar{\pli}    & Integer &  2 & No & A color plane index.
2731 See Table~\ref{tab:color-planes}.\\
2732 \locvar{\plj}    & Integer &  2 & No & A color plane index. \\
2733 \locvar{\qi}     & Integer &  6 & No & The quantization index. \\
2734 \locvar{\ci}     & Integer &  6 & No & The DCT coefficient index. \\
2735 \locvar{\bmi}    & Integer &  9 & No & The base matrix index. \\
2736 \locvar{\qri}    & Integer &  6 & No & The quant range index. \\
2737 \locvar{NBITS}   & Integer &  5 & No & The size of fields to read. \\
2738 \locvar{NEWQR}   & Integer &  1 & No & Flag that indicates a new set of quant
2739  ranges will be defined. \\
2740 \locvar{RPQR}    & Integer &  1 & No & Flag that indicates the quant ranges to
2741  copy will come from the same color plane. \\
2742 \bottomrule\end{tabularx}
2743 \medskip
2744
2745 The AC scale and DC scale values are defined in two simple tables with 64
2746  values each, one for each \qi\ value.
2747 The same scale values are used for every quantization type and color plane.
2748
2749 The base matrices for all quantization types and color planes are stored in a
2750  single table.
2751 These are then referenced by index in several sets of \term{quant ranges}.
2752 The purpose of the quant ranges is to specify which base matrices are used for
2753  which \qi\ values.
2754
2755 A set of quant ranges is defined for each quantization type and color plane.
2756 To save space in the header, bit flags allow a set of quant ranges to be copied
2757  from a previously defined set instead of being specified explicitly.
2758 Every set except the first one can be copied from the immediately preceding
2759  set.
2760 Similarly, if the quantization type is not $0$, the set can be copied from the
2761  set defined for the same color plane for the preceding quantization type.
2762 This formulation allows compact representation of, for example, the same 
2763  set of quant ranges in both chroma channels, as is done in the original VP3,
2764  or the same set of quant ranges in INTRA and INTER modes.
2765
2766 Each quant range is defined by a size and two base matrix indices, one for each
2767  end of the range.
2768 The base matrix for the end of one range is used as the start of the next
2769  range, so that for $n$ ranges, $n+1$ base matrices are specified.
2770 The base matrices for the \qi\ values between the two endpoints of the range
2771  are generated by linear interpolation.
2772
2773 %TODO: figure
2774
2775 The location of the endpoints of each range is encoded by their size.
2776 The \qi\ value for the left end-point is the sum of the sizes of all preceding
2777  ranges, and the \qi\ value for the right end-point adds the size of the
2778  current range.
2779 Thus the sum of the sizes of all the ranges MUST be 63, so that the last range
2780  falls on the last possible \qi\ value.
2781
2782 The complete set of quantization parameters are decoded as follows:
2783
2784 \begin{enumerate}
2785 \item
2786 Read a 4-bit unsigned integer.
2787 Assign \locvar{NBITS} the value read, plus one.
2788 \item
2789 For each consecutive value of \locvar{\qi} from $0$ to $63$, inclusive:
2790 \begin{enumerate}
2791 \item
2792 Read an \locvar{NBITS}-bit unsigned integer as
2793  $\bitvar{ACSCALE}[\locvar{\qi}]$.
2794 \end{enumerate}
2795 \item
2796 Read a 4-bit unsigned integer.
2797 Assign \locvar{NBITS} the value read, plus one.
2798 \item
2799 For each consecutive value of \locvar{\qi} from $0$ to $63$, inclusive:
2800 \begin{enumerate}
2801 \item
2802 Read an \locvar{NBITS}-bit unsigned integer as
2803  $\bitvar{DCSCALE}[\locvar{\qi}]$.
2804 \end{enumerate}
2805 \item
2806 Read a 9-bit unsigned integer.
2807 Assign \bitvar{NBMS} the value decoded, plus one.
2808 \bitvar{NBMS} MUST be no greater than 384.
2809 \item
2810 For each consecutive value of \locvar{\bmi} from $0$ to $(\bitvar{NBMS}-1)$,
2811  inclusive:
2812 \begin{enumerate}
2813 \item
2814 For each consecutive value of \locvar{\ci} from $0$ to $63$, inclusive:
2815 \begin{enumerate}
2816 \item
2817 Read an 8-bit unsigned integer as $\bitvar{BMS}[\locvar{\bmi}][\locvar{\ci}]$.
2818 \end{enumerate}
2819 \end{enumerate}
2820 \item
2821 For each consecutive value of \locvar{\qti} from $0$ to $1$, inclusive:
2822 \begin{enumerate}
2823 \item
2824 For each consecutive value of \locvar{\pli} from $0$ to $2$, inclusive:
2825 \begin{enumerate}
2826 \item
2827 If $\locvar{\qti}>0$ or $\locvar{\pli}>0$, read a 1-bit unsigned integer as
2828  \locvar{NEWQR}.
2829 \item
2830 Else, assign \locvar{NEWQR} the value one.
2831 \item
2832 If \locvar{NEWQR} is zero, then we are copying a previously defined set of
2833  quant ranges.
2834 In that case:
2835 \begin{enumerate}
2836 \item
2837 If $\locvar{\qti}>0$, read a 1-bit unsigned integer as \locvar{RPQR}.
2838 \item
2839 Else, assign \locvar{RPQR} the value zero.
2840 \item
2841 If \locvar{RPQR} is one, assign \locvar{\qtj} the value $(\locvar{\qti}-1)$
2842  and assign \locvar{\plj} the value \locvar{\pli}.
2843 This selects the set of quant ranges defined for the same color plane as this
2844  one, but for the previous quantization type.
2845 \item
2846 Else assign \locvar{\qtj} the value $(3*\locvar{\qti}+\locvar{\pli}-1)//3$ and
2847  assign \locvar{\plj} the value $(\locvar{\pli}+2)\%3$.
2848 This selects the most recent set of quant ranges defined.
2849 \item
2850 Assign $\bitvar{NQRS}[\locvar{\qti}][\locvar{\pli}]$ the value
2851  $\bitvar{NQRS}[\locvar{\qtj}][\locvar{\plj}]$.
2852 \item
2853 Assign $\bitvar{QRSIZES}[\locvar{\qti}][\locvar{\pli}]$ the values in 
2854  $\bitvar{QRSIZES}[\locvar{\qtj}][\locvar{\plj}]$.
2855 \item
2856 Assign $\bitvar{QRBMIS}[\locvar{\qti}][\locvar{\pli}]$ the values in
2857  $\bitvar{QRBMIS}[\locvar{\qtj}][\locvar{\plj}]$.
2858 \end{enumerate}
2859 \item
2860 Else, \locvar{NEWQR} is one, which indicates that we are defining a new set of
2861  quant ranges.
2862 In that case:
2863 \begin{enumerate}
2864 \item
2865 Assign $\locvar{\qri}$ the value zero.
2866 \item
2867 Assign $\locvar{\qi}$ the value zero.
2868 \item
2869 Read an $\ilog(\bitvar{NBMS}-1)$-bit unsigned integer as\\
2870  $\bitvar{QRBMIS}[\locvar{\qti}][\locvar{\pli}][\locvar{\qri}]$.
2871 If this is greater than or equal to \bitvar{NBMS}, stop.
2872 The stream is undecodable.
2873 \item
2874 \label{step:qr-loop}
2875 Read an $\ilog(62-\locvar{\qi})$-bit unsigned integer.
2876 Assign\\ $\bitvar{QRSIZES}[\locvar{\qti}][\locvar{\pli}][\locvar{\qri}]$ the value
2877  read, plus one.
2878 \item
2879 Assign \locvar{\qi} the value $\locvar{\qi}+
2880  \bitvar{QRSIZES}[\locvar{\qti}][\locvar{\pli}][\locvar{\qri}]$.
2881 \item
2882 Assign \locvar{\qri} the value $\locvar{\qri}+1$.
2883 \item
2884 Read an $\ilog(\bitvar{NBMS}-1)$-bit unsigned integer as\\
2885  $\bitvar{QRBMIS}[\locvar{\qti}][\locvar{\pli}][\locvar{\qri}]$.
2886 \item
2887 If \locvar{\qi} is less than 63, go back to step~\ref{step:qr-loop}.
2888 \item
2889 If \locvar{\qi} is greater than 63, stop.
2890 The stream is undecodable.
2891 \item
2892 Assign $\bitvar{NQRS}[\locvar{\qti}][\locvar{\pli}]$ the value \locvar{\qri}.
2893 \end{enumerate}
2894 \end{enumerate}
2895 \end{enumerate}
2896 \end{enumerate}
2897
2898 \paragraph{VP3 Compatibility}
2899
2900 The quantization parameters are hardcoded in VP3.
2901 The values used are given in Appendix~\ref{app:vp3-quant-params}.
2902
2903 \subsection{Computing a Quantization Matrix}
2904 \label{sub:quant-mat}
2905
2906 \paragraph{Input parameters:}\hfill\\*
2907 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2908 \multicolumn{1}{c}{Name} &
2909 \multicolumn{1}{c}{Type} &
2910 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2911 \multicolumn{1}{c}{Signed?} &
2912 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2913 \bitvar{ACSCALE} & \multicolumn{1}{p{40pt}}{Integer array} &
2914                              16 & No & A 64-element array of scale values for
2915  AC coefficients for each \qi\ value. \\
2916 \bitvar{DCSCALE} & \multicolumn{1}{p{40pt}}{Integer array} &
2917                              16 & No & A 64-element array of scale values for
2918  the DC coefficient for each \qi\ value. \\
2919 \bitvar{BMS}     & \multicolumn{1}{p{50pt}}{2D Integer array} &
2920                               8 & No & A $\bitvar{NBMS}\times 64$ array
2921  containing the base matrices. \\
2922 \bitvar{NQRS}    & \multicolumn{1}{p{50pt}}{2D Integer array} &
2923                               6 & No & A $2\times 3$ array containing the
2924  number of quant ranges for a given \qti\ and \pli, respectively.
2925 This is at most $63$. \\
2926 \bitvar{QRSIZES} & \multicolumn{1}{p{50pt}}{3D Integer array} &
2927                               6 & No & A $2\times 3\times 63$ array of the
2928  sizes of each quant range for a given \qti\ and \pli, respectively.
2929 Only the first $\bitvar{NQRS}[\qti][\pli]$ values are used. \\
2930 \bitvar{QRBMIS}  & \multicolumn{1}{p{50pt}}{3D Integer array} &
2931                               9 & No & A $2\times 3\times 64$ array of the
2932  \bmi's used for each quant range for a given \qti\ and \pli, respectively.
2933 Only the first $(\bitvar{NQRS}[\qti][\pli]+1)$ values are used. \\
2934 \bitvar{\qti}    & Integer &  1 & No & A quantization type index.
2935 See Table~\ref{tab:quant-types}.\\
2936 \bitvar{\pli}    & Integer &  2 & No & A color plane index.
2937 See Table~\ref{tab:color-planes}.\\
2938 \bitvar{\qi}     & Integer &  6 & No & The quantization index. \\
2939 \bottomrule\end{tabularx}
2940
2941 \paragraph{Output parameters:}\hfill\\*
2942 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2943 \multicolumn{1}{c}{Name} &
2944 \multicolumn{1}{c}{Type} &
2945 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2946 \multicolumn{1}{c}{Signed?} &
2947 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2948 \bitvar{QMAT} & \multicolumn{1}{p{40pt}}{Integer array} &
2949                              16 & No & A 64-element array of quantization
2950  values for each DCT coefficient in natural order. \\
2951 \bottomrule\end{tabularx}
2952
2953 \paragraph{Variables used:}\hfill\\*
2954 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
2955 \multicolumn{1}{c}{Name} &
2956 \multicolumn{1}{c}{Type} &
2957 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
2958 \multicolumn{1}{c}{Signed?} &
2959 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
2960 \locvar{\ci}     & Integer &  6 & No & The DCT coefficient index. \\
2961 \locvar{\bmi}    & Integer &  9 & No & The base matrix index. \\
2962 \locvar{\bmj}    & Integer &  9 & No & The base matrix index. \\
2963 \locvar{\qri}    & Integer &  6 & No & The quant range index. \\
2964 \locvar{QISTART} & Integer &  6 & No & The left end-point of the \qi\ range. \\
2965 \locvar{QIEND  } & Integer &  6 & No & The right end-point of the \qi\ range. \\
2966 \locvar{BM}      & \multicolumn{1}{p{40pt}}{Integer array} &
2967                               8 & No & A 64-element array containing the
2968  interpolated base matrix. \\
2969 \locvar{QMIN}    & Integer & 16 & No & The minimum quantization value allowed
2970  for the current coefficient. \\
2971 \locvar{QSCALE}  & Integer & 16 & No & The current scale value. \\
2972 \bottomrule\end{tabularx}
2973 \medskip
2974
2975 The following procedure can be used to generate a single quantization matrix
2976  for a given quantization type, color plane, and \qi\ value, given the
2977  quantization parameters decoded in Section~\ref{sub:quant-params}.
2978
2979 Note that the product of the scale value and the base matrix value is in units
2980  of $100$ths of a pixel value, and thus is divided by $100$ to return it to
2981  units of a single pixel value.
2982 This value is then scaled by four, to match the scaling of the DCT output,
2983  which is also a factor of four larger than the orthonormal version of the
2984  transform.
2985
2986 \begin{enumerate}
2987 \item
2988 Assign \locvar{\qri} the index of a quant range such that
2989 \begin{displaymath}
2990 \bitvar{\qi} \ge \sum_{\qrj=0}^{\locvar{\qri}-1}
2991  \bitvar{QRSIZES}[\bitvar{\qti}][\bitvar{\pli}][\qrj],
2992 \end{displaymath}
2993  and
2994 \begin{displaymath}
2995 \bitvar{\qi} \le \sum_{\qrj=0}^{\locvar{\qri}}
2996  \bitvar{QRSIZES}[\bitvar{\qti}][\bitvar{\pli}][\qrj],
2997 \end{displaymath}
2998  where summation from $0$ to $-1$ is defined to be zero.
2999 If there is more than one such value of $\locvar{\qri}$, i.e., if \bitvar{\qi}
3000  lies on the boundary between two quant ranges, then the output will be the
3001  same regardless of which one is chosen.
3002 \item
3003 Assign \locvar{QISTART} the value
3004 \begin{displaymath}
3005 \sum_{\qrj=0}^{\qri-1} \bitvar{QRSIZES}[\bitvar{\qti}][\bitvar{\pli}][\qrj].
3006 \end{displaymath}
3007 \item
3008 Assign \locvar{QIEND} the value
3009 \begin{displaymath}
3010 \sum_{\qrj=0}^{\qri} \bitvar{QRSIZES}[\bitvar{\qti}][\bitvar{\pli}][\qrj].
3011 \end{displaymath}
3012 \item
3013 Assign \locvar{\bmi} the value
3014  $\bitvar{QRBMIS}[\bitvar{\qti}][\bitvar{\pli}][\qri]$.
3015 \item
3016 Assign \locvar{\bmj} the value
3017  $\bitvar{QRBMIS}[\bitvar{\qti}][\bitvar{\pli}][\qri+1]$.
3018 \item
3019 For each consecutive value of \locvar{\ci} from $0$ to $63$, inclusive:
3020 \begin{enumerate}
3021 \item
3022 Assign $\locvar{BM}[\locvar{\ci}]$ the value
3023 \begin{displaymath}
3024 \begin{split}
3025 (&2*(\locvar{QIEND}-\bitvar{\qi})*\bitvar{BMS}[\locvar{\bmi}][\locvar{\ci}]\\
3026  &+2*(\bitvar{\qi}-
3027    \locvar{QISTART})*\bitvar{BMS}[\locvar{\bmj}][\locvar{\ci}]\\
3028  &+\bitvar{QRSIZES}[\bitvar{\qti}][\bitvar{\pli}][\locvar{\qri}])//
3029  (2*\bitvar{QRSIZES}[\bitvar{\qti}][\bitvar{\pli}][\locvar{\qri}])
3030 \end{split}
3031 \end{displaymath}
3032 \item
3033 Assign \locvar{QMIN} the value given by Table~\ref{tab:qmin} according to
3034  \bitvar{\qti} and \locvar{\ci}.
3035
3036 \begin{table}[htbp]
3037 \begin{center}
3038 \begin{tabular}{clr}\toprule
3039 Coefficient      & \multicolumn{1}{c}{\bitvar{\qti}}
3040                                & \locvar{QMIN} \\\midrule
3041 $\locvar{\ci}=0$ & $0$ (Intra) & $16$          \\
3042 $\locvar{\ci}>0$ & $0$ (Intra) & $8$           \\
3043 $\locvar{\ci}=0$ & $1$ (Inter) & $32$          \\
3044 $\locvar{\ci}>0$ & $1$ (Inter) & $16$          \\
3045 \bottomrule\end{tabular}
3046 \end{center}
3047 \caption{Minimum Quantization Values}
3048 \label{tab:qmin}
3049 \end{table}
3050
3051 \item
3052 If \locvar{\ci} equals zero, assign $\locvar{QSCALE}$ the value
3053  $\bitvar{DCSCALE}[\bitvar{\qi}]$.
3054 \item
3055 Else, assign $\locvar{QSCALE}$ the value
3056  $\bitvar{ACSCALE}[\bitvar{\qi}]$.
3057 \item
3058 Assign $\bitvar{QMAT}[\locvar{\ci}]$ the value
3059 \begin{displaymath}
3060 \max(\locvar{QMIN},
3061  \min((\locvar{QSCALE}*\locvar{BM}[\locvar{\ci}]//100)*4,4096)).
3062 \end{displaymath}
3063 \end{enumerate}
3064 \end{enumerate}
3065
3066 \subsection{DCT Token Huffman Tables}
3067 \label{sub:huffman-tables}
3068
3069 \paragraph{Input parameters:} None.
3070
3071 \paragraph{Output parameters:}\hfill\\*
3072 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3073 \multicolumn{1}{c}{Name} &
3074 \multicolumn{1}{c}{Type} &
3075 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3076 \multicolumn{1}{c}{Signed?} &
3077 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3078 \bitvar{HTS} & \multicolumn{3}{l}{Huffman table array}
3079                                      & An 80-element array of Huffman tables
3080  with up to 32 entries each. \\
3081 \bottomrule\end{tabularx}
3082
3083 \paragraph{Variables used:}\hfill\\*
3084 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3085 \multicolumn{1}{c}{Name} &
3086 \multicolumn{1}{c}{Type} &
3087 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3088 \multicolumn{1}{c}{Signed?} &
3089 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3090 \locvar{HBITS}   & Bit string & 32 & No & A string of up to 32 bits. \\
3091 \locvar{TOKEN}   & Integer    &  5 & No & A single DCT token value. \\
3092 \locvar{ISLEAF}  & Integer    &  1 & No & Flag that indicates if the current
3093  node of the tree being decoded is a leaf node. \\
3094 \bottomrule\end{tabularx}
3095 \medskip
3096
3097 The Huffman tables used to decode DCT tokens are stored in the setup header in
3098  the form of a binary tree.
3099 This enforces the requirements that the code be full---so that any sequence of
3100  bits will produce a valid sequence of tokens---and that the code be
3101  prefix-free so that there is no ambiguity when decoding.
3102
3103 One more restriction is placed on the tables that is not explicitly enforced by
3104  the bitstream syntax, but nevertheless must be obeyed by compliant encoders.
3105 There must be no more than 32 entries in a single table.
3106 Note that this restriction along with the fullness requirement limit the
3107  maximum size of a single Huffman code to 32 bits.
3108 It is probably a good idea to enforce this latter consequence explicitly when
3109  implementing the decoding procedure as a recursive algorithm, so as to prevent
3110  a possible stack overflow given an invalid bitstream.
3111
3112 Although there are 32 different DCT tokens, and thus a normal table will have
3113  exactly 32 entries, this is not explicitly required.
3114 It is allowable to use a Huffman code that omits some---but not all---of the
3115  possible token values.
3116 It is also allowable, if not particularly useful, to specify multiple codes for
3117  the same token value in a single table.
3118 Note also that token values may appear in the tree in any order.
3119 In particular, it is not safe to assume that token value zero (which ends a
3120  single block), has a Huffman code of all zeros.
3121
3122 The tree is decoded as follows:
3123
3124 \begin{enumerate}
3125 \item
3126 For each consecutive value of \locvar{\hti} from $0$ to $79$, inclusive:
3127 \begin{enumerate}
3128 \item
3129 Set \locvar{HBITS} to the empty string.
3130 \item
3131 \label{step:huff-tree-loop}
3132 If \locvar{HBITS} is longer than 32 bits in length, stop.
3133 The stream is undecodable.
3134 \item
3135 Read a 1-bit unsigned integer as \locvar{ISLEAF}.
3136 \item
3137 If \locvar{ISLEAF} is one:
3138 \begin{enumerate}
3139 \item
3140 If the number of entries in table $\bitvar{HTS}[\locvar{\hti}]$ is already 32,
3141  stop.
3142 The stream is undecodable.
3143 \item
3144 Read a 5-bit unsigned integer as \locvar{TOKEN}.
3145 \item
3146 Add the pair $(\locvar{HBITS},\locvar{TOKEN})$ to Huffman table
3147  $\bitvar{HTS}[\locvar{\hti}]$.
3148 \end{enumerate}
3149 \item
3150 Otherwise:
3151 \begin{enumerate}
3152 \item
3153 Add a `0' to the end of \locvar{HBITS}.
3154 \item
3155 Decode the `0' sub-tree using this procedure, starting from
3156  step~\ref{step:huff-tree-loop}.
3157 \item
3158 Remove the `0' from the end of \locvar{HBITS} and add a `1' to the end of
3159  \locvar{HBITS}.
3160 \item
3161 Decode the `1' sub-tree using this procedure, starting from
3162  step~\ref{step:huff-tree-loop}.
3163 \item
3164 Remove the `1' from the end of \locvar{HBITS}.
3165 \end{enumerate}
3166 \end{enumerate}
3167 \end{enumerate}
3168
3169 \paragraph{VP3 Compatibility}
3170
3171 The DCT token Huffman tables are hardcoded in VP3.
3172 The values used are given in Appendix~\ref{app:vp3-huffman-tables}.
3173
3174 \subsection{Setup Header Decode}
3175
3176 \paragraph{Input parameters:} None.
3177
3178 \paragraph{Output parameters:}\hfill\\*
3179 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3180 \multicolumn{1}{c}{Name} &
3181 \multicolumn{1}{c}{Type} &
3182 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3183 \multicolumn{1}{c}{Signed?} &
3184 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3185 \bitvar{LFLIMS}  & \multicolumn{1}{p{40pt}}{Integer array} &
3186                               7 & No & A 64-element array of loop filter limit
3187  values. \\
3188 \bitvar{ACSCALE} & \multicolumn{1}{p{40pt}}{Integer array} &
3189                              16 & No & A 64-element array of scale values for
3190  AC coefficients for each \qi\ value. \\
3191 \bitvar{DCSCALE} & \multicolumn{1}{p{40pt}}{Integer array} &
3192                              16 & No & A 64-element array of scale values for
3193  the DC coefficient for each \qi\ value. \\
3194 \bitvar{NBMS}    & Integer & 10 & No & The number of base matrices. \\
3195 \bitvar{BMS}     & \multicolumn{1}{p{50pt}}{2D Integer array} &
3196                               8 & No & A $\bitvar{NBMS}\times 64$ array
3197  containing the base matrices. \\
3198 \bitvar{NQRS}    & \multicolumn{1}{p{50pt}}{2D Integer array} &
3199                               6 & No & A $2\times 3$ array containing the
3200  number of quant ranges for a given \qti\ and \pli, respectively.
3201 This is at most $63$. \\
3202 \bitvar{QRSIZES} & \multicolumn{1}{p{50pt}}{3D Integer array} &
3203                               6 & No & A $2\times 3\times 63$ array of the
3204  sizes of each quant range for a given \qti\ and \pli, respectively.
3205 Only the first $\bitvar{NQRS}[\qti][\pli]$ values will be used. \\
3206 \bitvar{QRBMIS}  & \multicolumn{1}{p{50pt}}{3D Integer array} &
3207                               9 & No & A $2\times 3\times 64$ array of the
3208  \bmi's used for each quant range for a given \qti\ and \pli, respectively.
3209 Only the first $(\bitvar{NQRS}[\qti][\pli]+1)$ values will be used. \\
3210 \bitvar{HTS} & \multicolumn{3}{l}{Huffman table array}
3211                                      & An 80-element array of Huffman tables
3212  with up to 32 entries each. \\
3213 \bottomrule\end{tabularx}
3214
3215 \paragraph{Variables used:} None.
3216 \medskip
3217
3218 The complete setup header is decoded as follows:
3219
3220 \begin{enumerate}
3221 \item
3222 Decode the common header fields according to the procedure described in
3223  Section~\ref{sub:common-header}.
3224 If \bitvar{HEADERTYPE} returned by this procedure is not \hex{82}, then stop.
3225 This packet is not the setup header.
3226 \item
3227 Decode the loop filter limit value table using the procedure given in
3228  Section~\ref{sub:loop-filter-limits} into \bitvar{LFLIMS}.
3229 \item
3230 Decode the quantization parameters using the procedure given in
3231  Section~\ref{sub:quant-params}.
3232 The results are stored in \bitvar{ACSCALE}, \bitvar{DCSCALE}, \bitvar{NBMS},
3233  \bitvar{BMS}, \bitvar{NQRS}, \bitvar{QRSIZES}, and \bitvar{QRBMIS}.
3234 \item
3235 Decode the DCT token Huffman tables using the procedure given in
3236  Section~\ref{sub:huffman-tables} into \bitvar{HTS}.
3237 \end{enumerate}
3238
3239 \chapter{Frame Decode}
3240
3241 This section describes the complete procedure necessary to decode a single
3242  frame.
3243 This begins with the frame header, followed by coded block flags, macro block
3244  modes, motion vectors, block-level \qi\ values, and finally the DCT residual
3245  tokens, which are used to reconstruct the frame.
3246
3247 \section{Frame Header Decode}
3248 \label{sub:frame-header}
3249
3250 \paragraph{Input parameters:} None.
3251
3252 \paragraph{Output parameters:}\hfill\\*
3253 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3254 \multicolumn{1}{c}{Name} &
3255 \multicolumn{1}{c}{Type} &
3256 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3257 \multicolumn{1}{c}{Signed?} &
3258 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3259 \bitvar{FTYPE}   & Integer &  1 & No & The frame type. \\
3260 \bitvar{NQIS}    & Integer &  2 & No & The number of \qi\ values. \\
3261 \bitvar{QIS}     & \multicolumn{1}{p{40pt}}{Integer array} &
3262                              6 & No & An \bitvar{NQIS}-element array of
3263  \qi\ values. \\
3264 \bottomrule\end{tabularx}
3265
3266 \paragraph{Variables used:}\hfill\\*
3267 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3268 \multicolumn{1}{c}{Name} &
3269 \multicolumn{1}{c}{Type} &
3270 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3271 \multicolumn{1}{c}{Signed?} &
3272 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3273 \locvar{MOREQIS} & Integer &  1 & No & A flag indicating there are more
3274  \qi\ values to be decoded. \\
3275 \bottomrule\end{tabularx}
3276 \medskip
3277
3278 The frame header selects which type of frame is being decoded, intra or inter,
3279  and contains the list of \qi\ values that will be used in this frame.
3280 The first \qi\ value will be used for {\em all} DC coefficients in all blocks.
3281 This is done to ensure that DC prediction, which is done in the quantized
3282  domain, works as expected.
3283 The AC coefficients, however, can be dequantized using any \qi\ value on the
3284  list, selected on a block-by-block basis.
3285
3286 \begin{enumerate}
3287 \item
3288 Read a 1-bit unsigned integer.
3289 If the value read is not zero, stop.
3290 This is not a data packet.
3291 \item
3292 Read a 1-bit unsigned integer as \bitvar{FTYPE}.
3293 This is the type of frame being decoded, as given in
3294  Table~\ref{tab:frame-type}.
3295 If this is the first frame being decoded, this MUST be zero.
3296
3297 \begin{table}[htbp]
3298 \begin{center}
3299 \begin{tabular}{cl}\toprule
3300 \bitvar{FTYPE} & Frame Type  \\\midrule
3301 $0$            & Intra frame \\
3302 $1$            & Inter frame \\
3303 \bottomrule\end{tabular}
3304 \end{center}
3305 \caption{Frame Type Values}
3306 \label{tab:frame-type}
3307 \end{table}
3308
3309 \item
3310 Read in a 6-bit unsigned integer as $\bitvar{QIS}[0]$.
3311 \item
3312 Read a 1-bit unsigned integer as \locvar{MOREQIS}.
3313 \item
3314 If \locvar{MOREQIS} is zero, set \bitvar{NQIS} to 1.
3315 \item
3316 Otherwise:
3317 \begin{enumerate}
3318 \item
3319 Read in a 6-bit unsigned integer as $\bitvar{QIS}[1]$.
3320 \item
3321 Read a 1-bit unsigned integer as \locvar{MOREQIS}.
3322 \item
3323 If \locvar{MOREQIS} is zero, set \bitvar{NQIS} to 2.
3324 \item
3325 Otherwise:
3326 \begin{enumerate}
3327 \item
3328 Read in a 6-bit unsigned integer as $\bitvar{QIS}[2]$.
3329 \item
3330 Set \bitvar{NQIS} to 3.
3331 \end{enumerate}
3332 \end{enumerate}
3333 \item
3334 If \bitvar{FTYPE} is 0, read a 3-bit unsigned integer.
3335 These bits are reserved.
3336 If this value is not zero, stop.
3337 This frame is not decodable according to this specification.
3338 \end{enumerate}
3339
3340 \paragraph{VP3 Compatibility}
3341
3342 The precise format of the frame header is substantially different in Theora
3343  than in VP3.
3344 The original VP3 format includes a larger number of unused, reserved bits that
3345  are required to be zero.
3346 The original VP3 frame header also can contain only a single \qi\ value,
3347  because VP3 does not support block-level \qi\ values and uses the same
3348  \qi\ value for all the coefficients in a frame.
3349
3350 \section{Run-Length Encoded Bit Strings}
3351
3352 Two variations of run-length encoding are used to store sequences of bits for
3353  the block coded flags and the block-level \qi\ values.
3354 The procedures to decode these bit sequences are specified in the following two
3355  sections.
3356
3357 \subsection{Long-Run Bit String Decode}
3358 \label{sub:long-run}
3359
3360 \paragraph{Input parameters:}\hfill\\*
3361 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3362 \multicolumn{1}{c}{Name} &
3363 \multicolumn{1}{c}{Type} &
3364 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3365 \multicolumn{1}{c}{Signed?} &
3366 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3367 \bitvar{NBITS}   & Integer & 36 & No & The number of bits to decode. \\
3368 \bottomrule\end{tabularx}
3369
3370 \paragraph{Output parameters:}\hfill\\*
3371 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3372 \multicolumn{1}{c}{Name} &
3373 \multicolumn{1}{c}{Type} &
3374 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3375 \multicolumn{1}{c}{Signed?} &
3376 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3377 \bitvar{BITS}    & Bit string &    &    & The decoded bits. \\
3378 \bottomrule\end{tabularx}
3379
3380 \paragraph{Variables used:}\hfill\\*
3381 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3382 \multicolumn{1}{c}{Name} &
3383 \multicolumn{1}{c}{Type} &
3384 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3385 \multicolumn{1}{c}{Signed?} &
3386 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3387 \locvar{LEN}    & Integer & 36 & No & The number of bits decoded so far. \\
3388 \locvar{BIT}    & Integer &  1 & No & The value associated with the current
3389  run. \\
3390 \locvar{RLEN}   & Integer & 13 & No & The length of the current run. \\
3391 \locvar{RBITS}  & Integer &  4 & No & The number of extra bits needed to
3392  decode the run length. \\
3393 \locvar{RSTART} & Integer &  6 & No & The start of the possible run-length
3394  values for a given Huffman code. \\
3395 \locvar{ROFFS}  & Integer & 12 & No & The offset from \locvar{RSTART} of the
3396  run-length. \\
3397 \bottomrule\end{tabularx}
3398 \medskip
3399
3400 There is no practical limit to the number of consecutive 0's and 1's that can
3401  be decoded with this procedure.
3402 In reality, the run length is limited by the number of blocks in a single
3403  frame, because more will never be requested.
3404 A separate procedure described in Section~\ref{sub:short-run} is used when
3405  there is a known limit on the maximum size of the runs.
3406
3407 For the first run, a single bit value is read, and then a Huffman-coded
3408  representation of a run length is decoded, and that many copies of the bit
3409  value are appended to the bit string.
3410 For each consecutive run, the value of the bit is toggled instead of being read
3411  from the bitstream.
3412
3413 The only exception is if the length of the previous run was 4129, the maximum
3414  possible length encodable by the Huffman-coded representation.
3415 In this case another bit value is read from the stream, to allow for
3416  consecutive runs of 0's or 1's longer than this maximum.
3417
3418 Note that in both cases---for the first run and after a run of length 4129---if
3419  no more bits are needed, then no bit value is read.
3420
3421 The complete decoding procedure is as follows:
3422
3423 \begin{enumerate}
3424 \item
3425 Assign \locvar{LEN} the value 0.
3426 \item
3427 Assign \bitvar{BITS} the empty string.
3428 \item
3429 If \locvar{LEN} equals \bitvar{NBITS}, return the completely decoded string
3430  \bitvar{BITS}.
3431 \item
3432 Read a 1-bit unsigned integer as \locvar{BIT}.
3433 \item
3434 \label{step:long-run-loop}
3435 Read a bit at a time until one of the Huffman codes given in
3436  Table~\ref{tab:long-run} is recognized.
3437
3438 \begin{table}[htbp]
3439 \begin{center}
3440 \begin{tabular}{lrrl}\toprule
3441 Huffman Code & \locvar{RSTART} & \locvar{RBITS} & Run Lengths     \\\midrule
3442 \bin{0}      & $1$             & $0$            & $1$             \\
3443 \bin{10}     & $2$             & $1$            & $2\ldots 3$     \\
3444 \bin{110}    & $4$             & $1$            & $4\ldots 5$     \\
3445 \bin{1110}   & $6$             & $2$            & $6\ldots 9$     \\
3446 \bin{11110}  & $10$            & $3$            & $10\ldots 17$   \\
3447 \bin{111110} & $18$            & $4$            & $18\ldots 33$   \\
3448 \bin{111111} & $34$            & $12$           & $34\ldots 4129$ \\
3449 \bottomrule\end{tabular}
3450 \end{center}
3451 \caption{Huffman Codes for Long Run Lengths}
3452 \label{tab:long-run}
3453 \end{table}
3454
3455 \item
3456 Assign \locvar{RSTART} and \locvar{RBITS} the values given in
3457  Table~\ref{tab:long-run} according to the Huffman code read.
3458 \item
3459 Read an \locvar{RBITS}-bit unsigned integer as \locvar{ROFFS}.
3460 \item
3461 Assign \locvar{RLEN} the value $(\locvar{RSTART}+\locvar{ROFFS})$.
3462 \item
3463 Append \locvar{RLEN} copies of \locvar{BIT} to \bitvar{BITS}.
3464 \item
3465 Add \locvar{RLEN} to the value \locvar{LEN}.
3466 \locvar{LEN} MUST be less than or equal to \bitvar{NBITS}.
3467 \item
3468 If \locvar{LEN} equals \bitvar{NBITS}, return the completely decoded string
3469  \bitvar{BITS}.
3470 \item
3471 If \locvar{RLEN} equals 4129, read a 1-bit unsigned integer as \locvar{BIT}.
3472 \item
3473 Otherwise, assign \locvar{BIT} the value $(1-\locvar{BIT})$.
3474 \item
3475 Continue decoding runs from step~\ref{step:long-run-loop}.
3476 \end{enumerate}
3477
3478 \paragraph{VP3 Compatibility}
3479
3480 VP3 does not read a new bit value after decoding a run length of 4129.
3481 This limits the maximum number of consecutive 0's or 1's to 4129 in
3482  VP3-compatible streams.
3483 For reasonable video sizes of $1920\times 1080$ or less in 4:2:0 format---the
3484  only pixel format VP3 supports---this does not pose any problems because runs
3485  longer than 4129 are not needed.
3486
3487 \subsection{Short-Run Bit String Decode}
3488 \label{sub:short-run}
3489
3490 \paragraph{Input parameters:}\hfill\\*
3491 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3492 \multicolumn{1}{c}{Name} &
3493 \multicolumn{1}{c}{Type} &
3494 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3495 \multicolumn{1}{c}{Signed?} &
3496 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3497 \bitvar{NBITS}   & Integer & 36 & No & The number of bits to decode. \\
3498 \bottomrule\end{tabularx}
3499
3500 \paragraph{Output parameters:}\hfill\\*
3501 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3502 \multicolumn{1}{c}{Name} &
3503 \multicolumn{1}{c}{Type} &
3504 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3505 \multicolumn{1}{c}{Signed?} &
3506 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3507 \bitvar{BITS}    & Bit string &    &    & The decoded bits. \\
3508 \bottomrule\end{tabularx}
3509
3510 \paragraph{Variables used:}\hfill\\*
3511 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3512 \multicolumn{1}{c}{Name} &
3513 \multicolumn{1}{c}{Type} &
3514 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3515 \multicolumn{1}{c}{Signed?} &
3516 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3517 \locvar{LEN}    & Integer & 36 & No & The number of bits decoded so far. \\
3518 \locvar{BIT}    & Integer &  1 & No & The value associated with the current
3519  run. \\
3520 \locvar{RLEN}   & Integer & 13 & No & The length of the current run. \\
3521 \locvar{RBITS}  & Integer &  4 & No & The number of extra bits needed to
3522  decode the run length. \\
3523 \locvar{RSTART} & Integer &  6 & No & The start of the possible run-length
3524  values for a given Huffman code. \\
3525 \locvar{ROFFS}  & Integer & 12 & No & The offset from \locvar{RSTART} of the
3526  run-length. \\
3527 \bottomrule\end{tabularx}
3528 \medskip
3529
3530 This procedure is similar to the procedure outlined in
3531  Section~\ref{sub:long-run}, except that the maximum number of consecutive 0's
3532  or 1's is limited to 30.
3533 This is the maximum run length needed when encoding a bit for each of the 16
3534  blocks in a super block when it is known that not all the bits in a super
3535  block are the same.
3536
3537 The complete decoding procedure is as follows:
3538
3539 \begin{enumerate}
3540 \item
3541 Assign \locvar{LEN} the value 0.
3542 \item
3543 Assign \bitvar{BITS} the empty string.
3544 \item
3545 If \locvar{LEN} equals \bitvar{NBITS}, return the completely decoded string
3546  \bitvar{BITS}.
3547 \item
3548 Read a 1-bit unsigned integer as \locvar{BIT}.
3549 \item
3550 \label{step:short-run-loop}
3551 Read a bit at a time until one of the Huffman codes given in
3552  Table~\ref{tab:short-run} is recognized.
3553
3554 \begin{table}[htbp]
3555 \begin{center}
3556 \begin{tabular}{lrrl}\toprule
3557 Huffman Code & \locvar{RSTART} & \locvar{RBITS} & Run Lengths   \\\midrule
3558 \bin{0}      & $1$             & $1$            & $1\ldots 2$   \\
3559 \bin{10}     & $3$             & $1$            & $3\ldots 4$   \\
3560 \bin{110}    & $5$             & $1$            & $5\ldots 6$   \\
3561 \bin{1110}   & $7$             & $2$            & $7\ldots 10$  \\
3562 \bin{11110}  & $11$            & $2$            & $11\ldots 14$ \\
3563 \bin{11111}  & $15$            & $4$            & $15\ldots 30$ \\
3564 \bottomrule\end{tabular}
3565 \end{center}
3566 \caption{Huffman Codes for Short Run Lengths}
3567 \label{tab:short-run}
3568 \end{table}
3569
3570 \item
3571 Assign \locvar{RSTART} and \locvar{RBITS} the values given in
3572  Table~\ref{tab:short-run} according to the Huffman code read.
3573 \item
3574 Read an \locvar{RBITS}-bit unsigned integer as \locvar{ROFFS}.
3575 \item
3576 Assign \locvar{RLEN} the value $(\locvar{RSTART}+\locvar{ROFFS})$.
3577 \item
3578 Append \locvar{RLEN} copies of \locvar{BIT} to \bitvar{BITS}.
3579 \item
3580 Add \locvar{RLEN} to the value \locvar{LEN}.
3581 \locvar{LEN} MUST be less than or equal to \bitvar{NBITS}.
3582 \item
3583 If \locvar{LEN} equals \bitvar{NBITS}, return the completely decoded string
3584  \bitvar{BITS}.
3585 \item
3586 Assign \locvar{BIT} the value $(1-\locvar{BIT})$.
3587 \item
3588 Continue decoding runs from step~\ref{step:short-run-loop}.
3589 \end{enumerate}
3590
3591 \section{Coded Block Flags Decode}
3592 \label{sub:coded-blocks}
3593
3594 \paragraph{Input parameters:}\hfill\\*
3595 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3596 \multicolumn{1}{c}{Name} &
3597 \multicolumn{1}{c}{Type} &
3598 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3599 \multicolumn{1}{c}{Signed?} &
3600 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3601 \bitvar{FTYPE}   & Integer &  1 & No & The frame type. \\
3602 \bitvar{NSBS}    & Integer & 32 & No & The total number of super blocks in a
3603  frame. \\
3604 \bitvar{NBS}     & Integer & 36 & No & The total number of blocks in a
3605  frame. \\
3606 \bottomrule\end{tabularx}
3607
3608 \paragraph{Output parameters:}\hfill\\*
3609 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3610 \multicolumn{1}{c}{Name} &
3611 \multicolumn{1}{c}{Type} &
3612 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3613 \multicolumn{1}{c}{Signed?} &
3614 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3615 \bitvar{BCODED}   & \multicolumn{1}{p{40pt}}{Integer Array} &
3616                                1 & No & An \bitvar{NBS}-element array of flags
3617  indicating which blocks are coded. \\
3618 \bottomrule\end{tabularx}
3619
3620 \paragraph{Variables used:}\hfill\\*
3621 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3622 \multicolumn{1}{c}{Name} &
3623 \multicolumn{1}{c}{Type} &
3624 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3625 \multicolumn{1}{c}{Signed?} &
3626 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3627 \locvar{NBITS}    & Integer & 36 & No & The length of a bit string to decode. \\
3628 \locvar{BITS}     & Bit string & &    & A decoded set of flags. \\
3629 \locvar{SBPCODED} & \multicolumn{1}{p{40pt}}{Integer Array} &
3630                                1 & No & An \bitvar{NSBS}-element array of flags
3631  indicating whether or not each super block is partially coded. \\
3632 \locvar{SBFCODED} & \multicolumn{1}{p{40pt}}{Integer Array} &
3633                                1 & No & An \bitvar{NSBS}-element array of flags
3634  indicating whether or not each non-partially coded super block is fully
3635  coded. \\
3636 \locvar{\sbi}     & Integer & 32 & No & The index of the current super
3637  block. \\
3638 \locvar{\bi}      & Integer & 36 & No & The index of the current block in coded
3639  order. \\
3640 \bottomrule\end{tabularx}
3641 \medskip
3642
3643 This procedure determines which blocks are coded in a given frame.
3644 In an intra frame, it marks all blocks coded.
3645 In an inter frame, however, any or all of the blocks may remain uncoded.
3646 The output is a list of bit flags, one for each block, marking it coded or not
3647  coded.
3648
3649 It is important to note that flags are still decoded for any blocks which lie
3650  entirely outside the picture region, even though they are not displayed.
3651 Encoders MAY choose to code such blocks.
3652 Decoders MUST faithfully reconstruct such blocks, because their contents can be
3653  used for predictors in future frames.
3654 Flags are \textit{not} decoded for portions of a super block which lie outside
3655  the full frame, as there are no blocks in those regions.
3656
3657 The complete procedure is as follows:
3658
3659 \begin{enumerate}
3660 \item
3661 If \bitvar{FTYPE} is zero (intra frame):
3662 \begin{enumerate}
3663 \item
3664 For each consecutive value of \locvar{\bi} from 0 to $(\locvar{NBS}-1)$, assign
3665  $\bitvar{BCODED}[\locvar{\bi}]$ the value one.
3666 \end{enumerate}
3667 \item
3668 Otherwise (inter frame):
3669 \begin{enumerate}
3670 \item
3671 Assign \locvar{NBITS} the value \bitvar{NSBS}.
3672 \item
3673 Read an \locvar{NBITS}-bit bit string into \locvar{BITS}, using the procedure
3674  described in Section~\ref{sub:long-run}.
3675 This represents the list of partially coded super blocks.
3676 \item
3677 For each consecutive value of \locvar{\sbi} from 0 to $(\locvar{NSBS}-1)$,
3678  remove the bit at the head of the string \locvar{BITS} and assign it to
3679  $\locvar{SBPCODED}[\locvar{\sbi}]$.
3680 \item
3681 Assign \locvar{NBITS} the total number of super blocks such that \\
3682  $\locvar{SBPCODED}[\locvar{\sbi}]$ equals zero.
3683 \item
3684 Read an \locvar{NBITS}-bit bit string into \locvar{BITS}, using the procedure
3685  described in Section~\ref{sub:long-run}.
3686 This represents the list of fully coded super blocks.
3687 \item
3688 For each consecutive value of \locvar{\sbi} from 0 to $(\locvar{NSBS}-1)$ such
3689  that $\locvar{SBPCODED}[\locvar{\sbi}]$ equals zero, remove the bit at the
3690  head of the string \locvar{BITS} and assign it to
3691  $\locvar{SBFCODED}[\locvar{\sbi}]$.
3692 \item
3693 Assign \locvar{NBITS} the number of blocks contained in super blocks where
3694  $\locvar{SBPCODED}[\locvar{\sbi}]$ equals one.
3695 Note that this might {\em not} be equal to 16 times the number of partially
3696  coded super blocks, since super blocks which overlap the edge of the frame
3697  will have fewer than 16 blocks in them.
3698 \item
3699 Read an \locvar{NBITS}-bit bit string into \locvar{BITS}, using the procedure
3700  described in Section~\ref{sub:short-run}.
3701 \item
3702 For each block in coded order---indexed by \locvar{\bi}:
3703 \begin{enumerate}
3704 \item
3705 Assign \locvar{\sbi} the index of the super block containing block
3706  \locvar{\bi}.
3707 \item
3708 If $\locvar{SBPCODED}[\locvar{\sbi}]$ is zero, assign
3709  $\bitvar{BCODED}[\locvar{\bi}]$ the value $\locvar{SBFCODED}[\locvar{\sbi}]$.
3710 \item
3711 Otherwise, remove the bit at the head of the string \locvar{BITS} and assign it
3712  to $\bitvar{BCODED}[\locvar{\bi}]$.
3713 \end{enumerate}
3714 \end{enumerate}
3715 \end{enumerate}
3716
3717 \section{Macro Block Coding Modes}
3718 \label{sub:mb-modes}
3719
3720 \paragraph{Input parameters:}\hfill\\*
3721 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3722 \multicolumn{1}{c}{Name} &
3723 \multicolumn{1}{c}{Type} &
3724 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3725 \multicolumn{1}{c}{Signed?} &
3726 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3727 \bitvar{FTYPE}    & Integer &  1 & No & The frame type. \\
3728 \bitvar{NMBS}     & Integer & 32 & No & The total number of macro blocks in a
3729  frame. \\
3730 \bitvar{NBS}      & Integer & 36 & No & The total number of blocks in a
3731  frame. \\
3732 \bitvar{BCODED}   & \multicolumn{1}{p{40pt}}{Integer Array} &
3733                               1 & No & An \bitvar{NBS}-element array of flags
3734  indicating which blocks are coded. \\
3735 \bottomrule\end{tabularx}
3736
3737 \paragraph{Output parameters:}\hfill\\*
3738 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3739 \multicolumn{1}{c}{Name} &
3740 \multicolumn{1}{c}{Type} &
3741 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3742 \multicolumn{1}{c}{Signed?} &
3743 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3744 \bitvar{MBMODES} & \multicolumn{1}{p{40pt}}{Integer Array} &
3745                               3 & No & An \bitvar{NMBS}-element array of coding
3746  modes for each macro block. \\
3747 \bottomrule\end{tabularx}
3748
3749 \paragraph{Variables used:}\hfill\\*
3750 \begin{tabularx}{\textwidth}{@{}llrcX@{}}\toprule
3751 \multicolumn{1}{c}{Name} &
3752 \multicolumn{1}{c}{Type} &
3753 \multicolumn{1}{p{30pt}}{\centering Size (bits)} &
3754 \multicolumn{1}{c}{Signed?} &
3755 \multicolumn{1}{c}{Description and restrictions} \\\midrule\endhead
3756 \locvar{MSCHEME}   & Integer &  3 & No & The mode coding scheme. \\
3757 \locvar{MALPHABET} & \multicolumn{1}{p{40pt}}{Integer array}
3758                              &  3 & No & The list of modes corresponding to each
3759  Huffman code. \\
3760 \locvar{\mbi}      & Integer & 32 & No & The index of the current macro
3761  block. \\
3762 \locvar{\bi}       & Integer & 36 & No & The index of the current block in
3763  coded order. \\
3764 \locvar{\mi}       & Integer &  3 & No & The index of a Huffman code from
3765  Table~\ref{tab:mode-codes}, starting from $0$. \\
3766 \bottomrule\end{tabularx}
3767 \medskip
3768
3769 In an intra frame, every macro block marked as coded in INTRA mode.
3770 In an inter frame, however, a macro block can be coded in one of eight coding
3771  modes, given in Table~\ref{tab:coding-modes}.
3772 All of the blocks in all color planes contained in a macro block will be
3773  assigned the coding mode of that macro block.
3774
3775 \begin{table}[htbp]
3776 \begin{center}
3777 \begin{tabular}{cl}\toprule
3778 Index & Coding Mode \\\midrule
3779 $0$   & INTER\_NOMV         \\
3780 $1$   & INTRA               \\
3781 $2$   & INTER\_MV           \\
3782 $3$   & INTER\_MV\_LAST     \\
3783 $4$   & INTER\_MV\_LAST2    \\
3784 $5$   & INTER\_GOLDEN\_NOMV \\
3785 $6$   & INTER\_GOLDEN\_MV   \\
3786 $7$   & INTER\_MV\_FOUR     \\
3787 \bottomrule\end{tabular}
3788 \end{center}
3789 \caption{Macro Block Coding Modes}
3790 \label{tab:coding-modes}
3791 \end{table}
3792
3793 An important thing to note is that a coding mode is only stored in the
3794  bitstream for a macro block if it has at least one {\em luma} block coded.
3795 A macro block that contains coded blocks in the chroma planes, but not in the
3796  luma plane, MUST be coded in INTER\_NOMV mode.
3797 Thus, no coding mode needs to be decoded for such a macro block.
3798
3799 Coding modes are encoded using one of eight different schemes.
3800 Schemes 0 through 6 use the same simple Huffman code to represent the mode
3801  numbers, as given in Table~\ref{tab:mode-codes}.
3802 The difference in the schemes is&nbs