-
Notifications
You must be signed in to change notification settings - Fork 0
/
spec-conventions.tex
453 lines (348 loc) · 17.8 KB
/
spec-conventions.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% - 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*}