]> git.jsancho.org Git - lugaru.git/blob - Dependencies/libvorbis/doc/08-residue.tex
Commented out usage of header in OpenGL headers because it broke MSVC
[lugaru.git] / Dependencies / libvorbis / doc / 08-residue.tex
1 % -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*-
2 %!TEX root = Vorbis_I_spec.tex
3 % $Id$
4 \section{Residue setup and decode} \label{vorbis:spec:residue}
5
6 \subsection{Overview}
7
8 A residue vector represents the fine detail of the audio spectrum of
9 one channel in an audio frame after the encoder subtracts the floor
10 curve and performs any channel coupling.  A residue vector may
11 represent spectral lines, spectral magnitude, spectral phase or
12 hybrids as mixed by channel coupling.  The exact semantic content of
13 the vector does not matter to the residue abstraction.
14
15 Whatever the exact qualities, the Vorbis residue abstraction codes the
16 residue vectors into the bitstream packet, and then reconstructs the
17 vectors during decode.  Vorbis makes use of three different encoding
18 variants (numbered 0, 1 and 2) of the same basic vector encoding
19 abstraction.
20
21
22
23 \subsection{Residue format}
24
25 Residue format partitions each vector in the vector bundle into chunks,
26 classifies each chunk, encodes the chunk classifications and finally
27 encodes the chunks themselves using the the specific VQ arrangement
28 defined for each selected classification.
29 The exact interleaving and partitioning vary by residue encoding number,
30 however the high-level process used to classify and encode the residue
31 vector is the same in all three variants.
32
33 A set of coded residue vectors are all of the same length.  High level
34 coding structure, ignoring for the moment exactly how a partition is
35 encoded and simply trusting that it is, is as follows:
36
37 \begin{itemize}
38 \item Each vector is partitioned into multiple equal sized chunks
39 according to configuration specified.  If we have a vector size of
40 \emph{n}, a partition size \emph{residue_partition_size}, and a total
41 of \emph{ch} residue vectors, the total number of partitioned chunks
42 coded is \emph{n}/\emph{residue_partition_size}*\emph{ch}.  It is
43 important to note that the integer division truncates.  In the below
44 example, we assume an example \emph{residue_partition_size} of 8.
45
46 \item Each partition in each vector has a classification number that
47 specifies which of multiple configured VQ codebook setups are used to
48 decode that partition.  The classification numbers of each partition
49 can be thought of as forming a vector in their own right, as in the
50 illustration below.  Just as the residue vectors are coded in grouped
51 partitions to increase encoding efficiency, the classification vector
52 is also partitioned into chunks.  The integer elements of each scalar
53 in a classification chunk are built into a single scalar that
54 represents the classification numbers in that chunk.  In the below
55 example, the classification codeword encodes two classification
56 numbers.
57
58 \item The values in a residue vector may be encoded monolithically in a
59 single pass through the residue vector, but more often efficient
60 codebook design dictates that each vector is encoded as the additive
61 sum of several passes through the residue vector using more than one
62 VQ codebook.  Thus, each residue value potentially accumulates values
63 from multiple decode passes.  The classification value associated with
64 a partition is the same in each pass, thus the classification codeword
65 is coded only in the first pass.
66
67 \end{itemize}
68
69
70 \begin{center}
71 \includegraphics[width=\textwidth]{residue-pack}
72 \captionof{figure}{illustration of residue vector format}
73 \end{center}
74
75
76
77 \subsection{residue 0}
78
79 Residue 0 and 1 differ only in the way the values within a residue
80 partition are interleaved during partition encoding (visually treated
81 as a black box--or cyan box or brown box--in the above figure).
82
83 Residue encoding 0 interleaves VQ encoding according to the
84 dimension of the codebook used to encode a partition in a specific
85 pass.  The dimension of the codebook need not be the same in multiple
86 passes, however the partition size must be an even multiple of the
87 codebook dimension.
88
89 As an example, assume a partition vector of size eight, to be encoded
90 by residue 0 using codebook sizes of 8, 4, 2 and 1:
91
92 \begin{programlisting}
93
94             original residue vector: [ 0 1 2 3 4 5 6 7 ]
95
96 codebook dimensions = 8  encoded as: [ 0 1 2 3 4 5 6 7 ]
97
98 codebook dimensions = 4  encoded as: [ 0 2 4 6 ], [ 1 3 5 7 ]
99
100 codebook dimensions = 2  encoded as: [ 0 4 ], [ 1 5 ], [ 2 6 ], [ 3 7 ]
101
102 codebook dimensions = 1  encoded as: [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ]
103
104 \end{programlisting}
105
106 It is worth mentioning at this point that no configurable value in the
107 residue coding setup is restricted to a power of two.
108
109
110
111 \subsection{residue 1}
112
113 Residue 1 does not interleave VQ encoding.  It represents partition
114 vector scalars in order.  As with residue 0, however, partition length
115 must be an integer multiple of the codebook dimension, although
116 dimension may vary from pass to pass.
117
118 As an example, assume a partition vector of size eight, to be encoded
119 by residue 0 using codebook sizes of 8, 4, 2 and 1:
120
121 \begin{programlisting}
122
123             original residue vector: [ 0 1 2 3 4 5 6 7 ]
124
125 codebook dimensions = 8  encoded as: [ 0 1 2 3 4 5 6 7 ]
126
127 codebook dimensions = 4  encoded as: [ 0 1 2 3 ], [ 4 5 6 7 ]
128
129 codebook dimensions = 2  encoded as: [ 0 1 ], [ 2 3 ], [ 4 5 ], [ 6 7 ]
130
131 codebook dimensions = 1  encoded as: [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ]
132
133 \end{programlisting}
134
135
136
137 \subsection{residue 2}
138
139 Residue type two can be thought of as a variant of residue type 1.
140 Rather than encoding multiple passed-in vectors as in residue type 1,
141 the \emph{ch} passed in vectors of length \emph{n} are first
142 interleaved and flattened into a single vector of length
143 \emph{ch}*\emph{n}.  Encoding then proceeds as in type 1. Decoding is
144 as in type 1 with decode interleave reversed. If operating on a single
145 vector to begin with, residue type 1 and type 2 are equivalent.
146
147 \begin{center}
148 \includegraphics[width=\textwidth]{residue2}
149 \captionof{figure}{illustration of residue type 2}
150 \end{center}
151
152
153 \subsection{Residue decode}
154
155 \subsubsection{header decode}
156
157 Header decode for all three residue types is identical.
158 \begin{programlisting}
159   1) [residue_begin] = read 24 bits as unsigned integer
160   2) [residue_end] = read 24 bits as unsigned integer
161   3) [residue_partition_size] = read 24 bits as unsigned integer and add one
162   4) [residue_classifications] = read 6 bits as unsigned integer and add one
163   5) [residue_classbook] = read 8 bits as unsigned integer
164 \end{programlisting}
165
166 \varname{[residue_begin]} and
167 \varname{[residue_end]} select the specific sub-portion of
168 each vector that is actually coded; it implements akin to a bandpass
169 where, for coding purposes, the vector effectively begins at element
170 \varname{[residue_begin]} and ends at
171 \varname{[residue_end]}.  Preceding and following values in
172 the unpacked vectors are zeroed.  Note that for residue type 2, these
173 values as well as \varname{[residue_partition_size]}apply to
174 the interleaved vector, not the individual vectors before interleave.
175 \varname{[residue_partition_size]} is as explained above,
176 \varname{[residue_classifications]} is the number of possible
177 classification to which a partition can belong and
178 \varname{[residue_classbook]} is the codebook number used to
179 code classification codewords.  The number of dimensions in book
180 \varname{[residue_classbook]} determines how many
181 classification values are grouped into a single classification
182 codeword.  Note that the number of entries and dimensions in book
183 \varname{[residue_classbook]}, along with
184 \varname{[residue_classifications]}, overdetermines to
185 possible number of classification codewords.  
186 If \varname{[residue_classifications]}\^{}\varname{[residue_classbook]}.dimensions
187 exceeds \varname{[residue_classbook]}.entries, the
188 bitstream should be regarded to be undecodable.
189
190 Next we read a bitmap pattern that specifies which partition classes
191 code values in which passes.
192
193 \begin{programlisting}
194   1) iterate [i] over the range 0 ... [residue_classifications]-1 {
195
196        2) [high_bits] = 0
197        3) [low_bits] = read 3 bits as unsigned integer
198        4) [bitflag] = read one bit as boolean
199        5) if ( [bitflag] is set ) then [high_bits] = read five bits as unsigned integer
200        6) vector [residue_cascade] element [i] = [high_bits] * 8 + [low_bits]
201      }
202   7) done
203 \end{programlisting}
204
205 Finally, we read in a list of book numbers, each corresponding to
206 specific bit set in the cascade bitmap.  We loop over the possible
207 codebook classifications and the maximum possible number of encoding
208 stages (8 in Vorbis I, as constrained by the elements of the cascade
209 bitmap being eight bits):
210
211 \begin{programlisting}
212   1) iterate [i] over the range 0 ... [residue_classifications]-1 {
213
214        2) iterate [j] over the range 0 ... 7 {
215
216             3) if ( vector [residue_cascade] element [i] bit [j] is set ) {
217
218                  4) array [residue_books] element [i][j] = read 8 bits as unsigned integer
219
220                } else {
221
222                  5) array [residue_books] element [i][j] = unused
223
224                }
225           }
226       }
227
228   6) done
229 \end{programlisting}
230
231 An end-of-packet condition at any point in header decode renders the
232 stream undecodable.  In addition, any codebook number greater than the
233 maximum numbered codebook set up in this stream also renders the
234 stream undecodable. All codebooks in array [residue_books] are
235 required to have a value mapping.  The presence of codebook in array
236 [residue_books] without a value mapping (maptype equals zero) renders
237 the stream undecodable.
238
239
240
241 \subsubsection{packet decode}
242
243 Format 0 and 1 packet decode is identical except for specific
244 partition interleave.  Format 2 packet decode can be built out of the
245 format 1 decode process.  Thus we describe first the decode
246 infrastructure identical to all three formats.
247
248 In addition to configuration information, the residue decode process
249 is passed the number of vectors in the submap bundle and a vector of
250 flags indicating if any of the vectors are not to be decoded.  If the
251 passed in number of vectors is 3 and vector number 1 is marked 'do not
252 decode', decode skips vector 1 during the decode loop.  However, even
253 'do not decode' vectors are allocated and zeroed.
254
255 Depending on the values of \varname{[residue_begin]} and
256 \varname{[residue_end]}, it is obvious that the encoded
257 portion of a residue vector may be the entire possible residue vector
258 or some other strict subset of the actual residue vector size with
259 zero padding at either uncoded end.  However, it is also possible to
260 set \varname{[residue_begin]} and
261 \varname{[residue_end]} to specify a range partially or
262 wholly beyond the maximum vector size.  Before beginning residue
263 decode, limit \varname{[residue_begin]} and
264 \varname{[residue_end]} to the maximum possible vector size
265 as follows.  We assume that the number of vectors being encoded,
266 \varname{[ch]} is provided by the higher level decoding
267 process.
268
269 \begin{programlisting}
270   1) [actual_size] = current blocksize/2;
271   2) if residue encoding is format 2
272        3) [actual_size] = [actual_size] * [ch];
273   4) [limit_residue_begin] = maximum of ([residue_begin],[actual_size]);
274   5) [limit_residue_end] = maximum of ([residue_end],[actual_size]);
275 \end{programlisting}
276
277 The following convenience values are conceptually useful to clarifying
278 the decode process:
279
280 \begin{programlisting}
281   1) [classwords_per_codeword] = [codebook_dimensions] value of codebook [residue_classbook]
282   2) [n_to_read] = [limit_residue_end] - [limit_residue_begin]
283   3) [partitions_to_read] = [n_to_read] / [residue_partition_size]
284 \end{programlisting}
285
286 Packet decode proceeds as follows, matching the description offered earlier in the document.
287 \begin{programlisting}
288   1) allocate and zero all vectors that will be returned.
289   2) if ([n_to_read] is zero), stop; there is no residue to decode.
290   3) iterate [pass] over the range 0 ... 7 {
291
292        4) [partition_count] = 0
293
294        5) while [partition_count] is less than [partitions_to_read]
295
296             6) if ([pass] is zero) {
297
298                  7) iterate [j] over the range 0 .. [ch]-1 {
299
300                       8) if vector [j] is not marked 'do not decode' {
301
302                            9) [temp] = read from packet using codebook [residue_classbook] in scalar context
303                           10) iterate [i] descending over the range [classwords_per_codeword]-1 ... 0 {
304
305                                11) array [classifications] element [j],([i]+[partition_count]) =
306                                    [temp] integer modulo [residue_classifications]
307                                12) [temp] = [temp] / [residue_classifications] using integer division
308
309                               }
310
311                          }
312
313                     }
314
315                }
316
317            13) iterate [i] over the range 0 .. ([classwords_per_codeword] - 1) while [partition_count]
318                is also less than [partitions_to_read] {
319
320                  14) iterate [j] over the range 0 .. [ch]-1 {
321
322                       15) if vector [j] is not marked 'do not decode' {
323
324                            16) [vqclass] = array [classifications] element [j],[partition_count]
325                            17) [vqbook] = array [residue_books] element [vqclass],[pass]
326                            18) if ([vqbook] is not 'unused') {
327
328                                 19) decode partition into output vector number [j], starting at scalar
329                                     offset [limit_residue_begin]+[partition_count]*[residue_partition_size] using
330                                     codebook number [vqbook] in VQ context
331                           }
332                      }
333
334                  20) increment [partition_count] by one
335
336                }
337           }
338      }
339
340  21) done
341
342 \end{programlisting}
343
344 An end-of-packet condition during packet decode is to be considered a
345 nominal occurrence.  Decode returns the result of vector decode up to
346 that point.
347
348
349
350 \subsubsection{format 0 specifics}
351
352 Format zero decodes partitions exactly as described earlier in the
353 'Residue Format: residue 0' section.  The following pseudocode
354 presents the same algorithm. Assume:
355
356 \begin{itemize}
357 \item  \varname{[n]} is the value in \varname{[residue_partition_size]}
358 \item \varname{[v]} is the residue vector
359 \item \varname{[offset]} is the beginning read offset in [v]
360 \end{itemize}
361
362
363 \begin{programlisting}
364  1) [step] = [n] / [codebook_dimensions]
365  2) iterate [i] over the range 0 ... [step]-1 {
366
367       3) vector [entry_temp] = read vector from packet using current codebook in VQ context
368       4) iterate [j] over the range 0 ... [codebook_dimensions]-1 {
369
370            5) vector [v] element ([offset]+[i]+[j]*[step]) =
371                 vector [v] element ([offset]+[i]+[j]*[step]) +
372                 vector [entry_temp] element [j]
373
374          }
375
376     }
377
378   6) done
379
380 \end{programlisting}
381
382
383
384 \subsubsection{format 1 specifics}
385
386 Format 1 decodes partitions exactly as described earlier in the
387 'Residue Format: residue 1' section.  The following pseudocode
388 presents the same algorithm. Assume:
389
390 \begin{itemize}
391 \item  \varname{[n]} is the value in
392 \varname{[residue_partition_size]}
393 \item \varname{[v]} is the residue vector
394 \item \varname{[offset]} is the beginning read offset in [v]
395 \end{itemize}
396
397
398 \begin{programlisting}
399  1) [i] = 0
400  2) vector [entry_temp] = read vector from packet using current codebook in VQ context
401  3) iterate [j] over the range 0 ... [codebook_dimensions]-1 {
402
403       4) vector [v] element ([offset]+[i]) =
404           vector [v] element ([offset]+[i]) +
405           vector [entry_temp] element [j]
406       5) increment [i]
407
408     }
409
410   6) if ( [i] is less than [n] ) continue at step 2
411   7) done
412 \end{programlisting}
413
414
415
416 \subsubsection{format 2 specifics}
417
418 Format 2 is reducible to format 1.  It may be implemented as an additional step prior to and an additional post-decode step after a normal format 1 decode.
419
420
421 Format 2 handles 'do not decode' vectors differently than residue 0 or
422 1; if all vectors are marked 'do not decode', no decode occurrs.
423 However, if at least one vector is to be decoded, all the vectors are
424 decoded.  We then request normal format 1 to decode a single vector
425 representing all output channels, rather than a vector for each
426 channel.  After decode, deinterleave the vector into independent vectors, one for each output channel.  That is:
427
428 \begin{enumerate}
429  \item If all vectors 0 through \emph{ch}-1 are marked 'do not decode', allocate and clear a single vector \varname{[v]}of length \emph{ch*n} and skip step 2 below; proceed directly to the post-decode step.
430  \item Rather than performing format 1 decode to produce \emph{ch} vectors of length \emph{n} each, call format 1 decode to produce a single vector \varname{[v]} of length \emph{ch*n}.
431  \item Post decode: Deinterleave the single vector \varname{[v]} returned by format 1 decode as described above into \emph{ch} independent vectors, one for each outputchannel, according to:
432   \begin{programlisting}
433   1) iterate [i] over the range 0 ... [n]-1 {
434
435        2) iterate [j] over the range 0 ... [ch]-1 {
436
437             3) output vector number [j] element [i] = vector [v] element ([i] * [ch] + [j])
438
439           }
440      }
441
442   4) done
443   \end{programlisting}
444
445 \end{enumerate}
446
447
448
449
450
451
452