Include a pre-rendered pdf version

[dirac-spec-errata.git] / spec-conventions.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% - This chapter defines specification         - %
% - conventions                                - % 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{spec-conventions}
\subsection{State representation}

This standard uses a state model to express parsing and decoding operations. 
The state of the decoder/parser shall be stored in the variable state. Individual elements of the decoder $\StateName$ (state variables) may be accessed
 by means of 
named labels, e.g. $\StateName[\text{VAR\_NAME}]$ (i.e. state is a map, as defined in Section \ref{datatypes}). 

The decoder state shall be globally accessible within the decoder. Other 
variables, not declared as inputs to a process, shall be local to that process.
The parsing and decoding operations are defined in terms of modifying the 
decoder state. The state variables need not directly correspond to elements 
of the stream, but may be calculated from them taking into account the decoder 
state as a whole. For example, a state variable value may be differentially 
encoded with respect to another value, with the difference, not the variable 
itself, encoded in the stream. 

\begin{comment}
The Dirac stream syntax structure is illustrated with informative parse diagrams,
contained in Annex \ref{parsediagrams},
 that complement the normative stream syntax definitions.
\end{comment}
 The parsing process 
is defined by means of pseudocode and/or mathematical formulae. The 
conventions for these elements are described in the following sections.

\subsection{Number formats}
\label{mathnotation}

Numbers without a prefix shall be interpreted as decimal numbers.

The prefix b indicates that the following value shall be interpreted as a binary
natural number (non-negative integer). 

{\bf Example} The value b1110100 is equal to the decimal value 116. 

The prefix 0x shall indicate that the following value is to be interpreted as a hexadecimal (base 16) natural number. 

{\bf Example} The value 0x7A is equal to the decimal value 122. 

\subsection{Data types}
\label{datatypes}

\subsubsection{Elementary data types}

Three basic types are used in the pseudo code:
\begin{description}
\item[Boolean] - A Boolean variable that has only two possible values: $\true$ and $\false$.
\item[Integer] - A positive or negative whole number or zero.
\item[Label] - a unique immutable value used in control structures and to 
access maps (see below).
\end{description}

\subsubsection{Compound data types}

Elementary and compound data types may be aggregated into a single 
compound data type.
There are three compound data type:

\begin{description}
\item[Set]
 A collection of data types. A set is indicated by enclosing the elements within 
curly braces, for example $\{a,b,c\}$ represents a set containing the values $a,b$
 and $c$. An empty set may be indicated by $\{\}$. The usual set-theoretic 
operations such as: $\cup$ (union), $\cap$ (intersection), $\in$ (membership) 
apply to sets and the other compound data types. 

\item[Map] A set of data types whose elements are accessed by their 
corresponding label. For example, $p[Y] ,p[C1] ,p[C2] $ might be the values 
of the different video components of a pixel. The set of  labels corresponding to 
the elements of a map $m$ can be accessed by $\args(m)$, so that, for example, $args(p)$ returns$\{Y,C1,C2\}$.
\item[Array]  A collection of data types accessed by a non-negative integer index.
 This compound data type is typically used to represent an array of variables. Elements of a 1-dimensional array $a$ are accessed by $a[n]$ for $n$
 in the range 0 to $\length(a) - 1$. 
\end{description}

A compound data type may contain other compound data types. For example, 
a two dimensional array is an array of one dimensional arrays. Elements of a 2-dimensional array are accessed by $a[n][m]$ for $0\leq m\leq(\width(a)-1)$, 
and $0\leq n\leq (\height(a)-1)$. Compound data types may be more complex. 
For example, picture data, pic, may be considered to be a map of arrays, where $pic[Y]$ is a 2-dimensional array storing luma data, and $pic[C1]$ and $pic[C2]$
 are two-dimensional arrays storing chroma data.

Elements may be added to a map or array by assignment using the appropriate
 index (label or integer). For example, $a[7]=2$, adds element 7 to the array $a$,
 if a does not already contain element 7, then this element is assigned the value 2.

\subsection{Functions and operators}
\label{functionoperators}

This section defines the functions and operators used 
in the pseudocode in this specification. Functions and operators
are similar but functions use the syntax, $(arg1, arg2,\ldots)$ 
whereas operators are simply placed before or between operands, 
e.g. $a+b$. The difference is purely syntactic and is to 
correspond with conventional mathematical notation.

\subsubsection{Assignment}

The assignment operation  = applies to all variable types. After performing 
\[a=b\]
the value of $a$ shall become equal to that of $b$, and the value of $b$ shall remain unchanged. For a set (or map or array) this constitutes an element-wise copy
 i.e.
\[a[x]=b[x]\]
for all valid values of $x$.

\subsubsection{Boolean functions and operators}
\label{booleanops}
The following functions and operators are defined for one or more Boolean arguments:
\begin{description}
\item[not]              (not a) or returns $\true$ for a boolean value $a$ if and only if 
$a$ is $\false$
\item[and]              (a and b) returns $\true$ if and only if a and b are both $\true$. Operator "and" may be used in pseudo-code conditions to denote the logical AND between Boolean values, for example: if (condition1 and condition2): …etc.
\item[or]               (a or b) returns True if either a or b are True, else it returns False.  Operator "or" may be used in pseudo-code conditions to denote the logical OR between Boolean values, for example: if (condition1 or condition2): … etc.
\item[majority]         Given a set, $S =\{s_0,…, s_{n-1}\}$ of Boolean values, $\majority(S)$ returns the majority condition. That is, if the number of $\true$ 
values is greater than or equal to the number of $\false$ values, $majority(S)$
 returns $\true$, otherwise it returns $\false$.
\end{description}

Boolean operations are to be distinguished from bitwise operations which operate on non-negative 
integer values, and are defined in Section \ref{integerops}.

\subsubsection{Integer functions and operators}
\label{integerops}
The following functions and operators are defined on integer values:

\begin{description}
\item[Absolute value] $|a|=\left\lbrace\begin{array}{l} a \text{ if $a\geq 0$}\\ 
                                                                                   -a \text{ otherwise} \end{array}\right.$.

\item[Sign] $\sign(a)$ is defined by
\[\sign(a)=
\left\{\begin{array}{l} 
1 \text{ if $a>0$} \\
0 \text{ if $a==0$}\\
-1 \text{ if $a<0$} 
\end{array}\right.\]

\item[Addition] The sum of $a$ and $b$ is represented by $a+b$.

\item[Subtraction] $a$ minus $b$ is represented by $a-b$.

\item[Multiplication] $a$ times $b$ is represented, for clarity, by $a*b$.

\item[Integer division] Integer division is defined for integer values $a,b$ with 
$b>0$ where: $n=a//b$ is defined to be the largest integer $n$ such that
\[n*b\leq a\] 

i.e. numbers are rounded towards -infinity. N.B. this differs from C/C++ conventions
of round towards 0.

\item[Remainder] For integers $a,b$, with $b>0$, the remainder $a\%b$ is 
equal to 

\[a\%b = a-(a//b)*b \]

 $a\%b$ always lies between 0 and $b-1$.

\item[Exponentiation] For integers $a, b$, $b>0$ $a^b$ is defined as $a*a*\hdots *a$ ($b$ times). $a^0$ is 1.

\item[Maximum] $\max(a,b)$ returns the largest of $a$ and $b$.

\item[Minimum] $\min(a,b)$ returns the smallest of values $a$ and $b$.

\item[Clip] $\clip(a,b,t)$ clips the value $a$ to the range defined by $b$ (bottom)
and $t$ (top):
\[\clip(a,b,t)=\min(\max(a,b),t)\]

\item[Shift down] For integers $a,b$, with $b\geq 0$, $a\gg b$ is defined as 
$a//2^b$.

\item[Shift up] For integers $a,b$, with $b\geq 0$, $a\ll b$ is defined as $a*2^b$.

\item[Integer logarithm] $m=\intlog2(n)$, for $n>0$, $m$ is the integer such that
$2^{m-1}<n\leq 2^m$.


\item[Mean] Given a set  $S=\{s_0, s_1, \hdots, s_{n-1}\}$ of integer values, the integer unbiased mean, $\mean(S)$, is defined
to be

\[(s_0+s_1+\hdots +s_{n-1}+(n//2))//n\]

\item[Median] Given a set $S=\{s_0, s_1, \hdots, s_{n-1} \}$ of integer values the median, $\median(S)$, 
returns the middle value. If $t_0\leq t_1\leq \hdots \leq t_{n-1}$ are the values $s_i$ placed in ascending order, this
is 

$t_{(n-1)/2}$ 

if $n$ is odd and

$\mean(\{ t_{(n-2)/2},t_{n/2}\})$ if $n$ is even. If $S=\emptyset$, $\median(S)$ returns 0.
\end{description}
The following bitwise operations are defined on non-negative integer values:
\begin{description}
\item[\&] Logical AND is applied between the corresponding bits in the binary representation of two numbers, e.g.
$13\&6$ is $\text{b1101}\&\text{b110}$, which equals $\text{b100}$, or 4.

\item[${\mathbf |}$] Logical OR is applied between the corresponding bits in the binary representation of two numbers, e.g.
$13|6$ is $\text{b1101}\text{|}\text{b110}$, which equals $\text{b1111}$, or 15.

\item[${\mathbf \wedge}$] Logical XOR is applied between the corresponding bits in the binary representation of two numbers, e.g.
$13\wedge 6$ is $\text{b1101}\wedge\text{b110}$, which equals $\text{b1011}$, or 11.

\item[$\mathbf{\&=}$]    $a \&= b$ is equivalent to $a = (a \& b)$.
\item[$\mathbf{|=}$]     $a |= b$ is equivalent to $a = (a | b)$.
\item[$\mathbf{\wedge=}$]       $a\wedge= b$ is equivalent to $a = (a \wedge b)$.
\end{description}

Bitwise-not is not defined for integers to avoid ambiguity concerning leading 
zeroes

The following logical operators are defined for integer and boolean arguments:
\begin{description}
\item[==] Test of equality of two variables. $a == b$ is $\true$ if and only if the 
value of a equals the value of b.
\item[!=] Not equal to. $a != b$ is equivalent to not $(a == b)$
\end{description}

The following logical operators are defined for integer arguments only:
\begin{description}
\item[$\mathbf{<}$]     Less than
\item[$\mathbf{<=}$]    Less than or equal to
\item[$\mathbf{>}$]     Greater than
\item[$\mathbf{>=}$]    Greater than or equal to

\end{description}

The following combined assignment operators are defined for integer 
arguments:
Operators $+, -, *, //, \%, \gg, \ll, \&, |, \wedge$, may be combined with the assignment operator (as for the Boolean operators $\&$, $|$, and $\wedge$
 above). For example $a += b$ is equivalent to $a = (a + b)$.

\subsubsection{Array and map functions and operators}

The following functions and operators are defined for sets, maps and arrays. 
\begin{description}
\item[Indexing]         For an array $a$, $a[index]$ returns an element of $a$. If $a$ is a map the index shall be a label, else if $a$ is an array the index shall be an integer.
\item[Scalar Assignment]        Where the notation $a = 0$ is used for an array of integer values, it means "set all elements of the array to zero".
\item[Insertion]                $a[index] = b$ inserts a copy of $b$ into set $a$ 
if the element does not already exist.
\item[Tokens]           for a map $a$, $\args(a)$ returns the set of the indexing tokens.
\item[Length]           for a one dimensional array $a$, $\length(a)$ 
returns the number of elements in the array.
\item[Width]            for a two dimensional array $a$, $\width(a)$ returns the 
width the array. The width is the number of scalar elements corresponding to the right most array index.
\item[Height]                                   for a two dimensional array $a$, $\height(a)$ returns 
the height the array. The height is the number of one dimensional arrays in the two dimensional array and the "height" dimension corresponds to the left most array index.
\end{description}
\subsubsection{Precedence and associativity of operators}
\label{operatorprecedence}
To avoid any confusion over the order of operator precedence, every equation makes extensive use of the expression operators "(" and ")". All operations recursively execute the innermost expression(s) first until the calculation has been completed. In cases where the expression operators do not make clear the order of precedence, the following table defines the descending order of operator precedence and the associativity of each operator.
[Table tbc]
\begin{comment}
Operator Precedence     Associativity
( ) [ ] left to right
* // %  left to right
+ -     left to right
<< >>   left to right
< <= > >=       left to right
== !=   left to right
! (not) right to left
& (and) left to right
^ (xor) left to right
|       left to right
= += -= *= //= %= &= ^= |= <<= >>=      right to left
\end{comment}

\subsection{Pseudocode}
\label{pseudocode}

Most of the normative specification is defined by means of pseudocode. 
The syntax is intended to be both precise and descriptive; the pseudocode is 
not intended to form the basis for the implementation of a Dirac decoder.

All processing defined by this standard is precise and the entire specification
can be implemented using only the data types, functions and operators 
defined herein. That is, no operations on "real" or "floating point" numbers
 are required. All operations shall be implemented with sufficiently large 
integers so that overflow cannot occur.

The type of variables in the pseudocode is not explicitly declared. 
A variable assumes a type when it is assigned a value, which shall always 
have a defined type.

\subsubsection{Processes and functions}
\label{functionsprocesses}

Decoding and parsing operations are specified by means of processes
 -- a series of operations acting on input data and global variable data. 
A process can also be a function, which means it returns a value, but
it need not do so. So a process
taking in variables $in1$ and $in2$ looks like:

\begin{pseudo}{foo}{in1, in2}
\bsCODE{op1(in1)}
\bsCODE{op2(in2)}
\bsCODE{\hdots}
\end{pseudo}

Whilst a function process looks like:

\begin{pseudo}{bar}{in1, in2}
\bsCODE{op1(in1)}
\bsCODE{foo(in1,in2)}{\ref{functionsprocesses}}
\bsCODE{\hdots}
\bsRET{out1}
\end{pseudo}

The right-hand column in the pseudocode representation contains a cross-reference to the 
section in the specification containing the definition of other processes used at that line.

\subsubsection{Variables}

All input variables are deemed to be passed {\em by reference} in this
specification. This means that any modification to a variable value that
occurs within a process also applies to that variable within the calling process
{\em even if it has a different name} in the calling process. One way to understand
this is to envisage variable names as pointers to workspace memory.

For example, if we define $foo$ and $bar$ by

\begin{pseudo}{foo}{}
\bsCODE{num=0}
\bsCODE{bar(num)}
\bsCODE{\StateName[var\_name]=num}
\end{pseudo}

and 

\begin{pseudo}{bar}{val}
\bsCODE{val=val+1}
\end{pseudo}

then at the end of $foo$, $\StateName[var\_name]$ has been set to 1.

The only global variables are the state variables encapsulated in $\StateName$.
 If a variable is not declared as an input to
the process and is not a state variable, then it is local to the function.

If a process is particularly complex, it may be broken into a number of steps with 
intermediate discussion. This is signalled by appending  and prepending ``$\hdots$" to
the parts of the pseudocode specification:

\begin{pseudo}{foo}{}
\bsCODE{code}
\bsCODE{\hdots}
\end{pseudo}

[text]

\begin{pseudo*}
\bsCODE{more code}
\bsCODE{\hdots}
\end{pseudo*}

[text]

\begin{pseudo*}
\bsCODE{even more code}
\end{pseudo*}

The intervening text may define or modify variables used in the succeeding
pseudocode, and must be considered as a normative part of the specification of the process.
This is done as it is sometimes much more clear to split up a long and complicated process
into a number of steps.

\subsubsection{Control flow}
\label{controlflow}

The pseudocode comprises a series of statements, linked by functions and
flow control statements such as {\bf if}, {\bf while}, and {\bf for}.

The statements do not have a termination character, unlike the ; in C
for example.  Blocks of statements are indicated by indentation:
indenting in begins a block, indenting out ends one.

Statements that expect a block (and hence a following indentation) end
in a colon.

\paragraph*{if}

The if control evaluates a boolean or boolean function, and if true, passes the 
flow to the block of following statement or block of statements. If the control
evaluates as false, then there is an option to include one or more else if
controls which offer alternative responses if some other condition is
true.  If none of the preceding controls evaluate to true, then there is
the option to include an else control which catches remaining cases.

\begin{pseudo*}
\bsIF{control1}
    \bsCODE{block1}
\bsELSEIF{control2}
    \bsCODE{block2}
\bsELSEIF{control3}
    \bsCODE{block3}
\bsELSE
    \bsCODE{block4}
\bsEND
\end{pseudo*}

The if and else if conditions are evaluated in the order in which they
are presented. In particular, if $control1$ or $control2$ is true in
the preceding example, $block3$ will not be executed
even if $control3$ is true; neither will $block4$.

\paragraph*{for}

The for control repeats a loop over an integer range of values. For example,

\begin{pseudo*}
\bsFOR{i=0}{n-1}
    \bsCODE{foo(i)}
\bsEND
\end{pseudo*}

calls $foo()$ with value $i$, as $i$ steps through from 0 to $n-1$ inclusive.


\paragraph*{for each} The for each control loops over the elements in
a list:

\begin{pseudo*}
\bsFOREACH{c}{Y,C1,C2}
    \bsCODE{block}
\bsEND
\end{pseudo*}

\paragraph*{for such that} The for such that control loops over elements in
a set which satisfy some condition:

\begin{pseudo*}
\bsFORSUCH{a\in A}{control}
    \bsCODE{block}
\bsEND
\end{pseudo*}

This may only be used when the order in which elements are processed is 
immaterial.

\paragraph*{while}

The while control repeats a loop so long as a switch variable is true. 
When it is false, the loop breaks to the next statement(s) outside the block.

\begin{pseudo*}
\bsWHILE{condition}
    \bsCODE{block1}
\bsEND
\bsCODE{block2}
\end{pseudo*}