VirtualBox

source: vbox/trunk/src/libs/libvorbis-1.3.7/doc/03-codebook.tex@ 103131

Last change on this file since 103131 was 96468, checked in by vboxsync, 2 years ago

libs/libvorbis-1.3.7: Re-exporting, hopefully this time everything is there. bugref:10275

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 17.0 KB
Line 
1% -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*-
2%!TEX root = Vorbis_I_spec.tex
3\section{Probability Model and Codebooks} \label{vorbis:spec:codebook}
4
5\subsection{Overview}
6
7Unlike practically every other mainstream audio codec, Vorbis has no
8statically configured probability model, instead packing all entropy
9decoding configuration, VQ and Huffman, into the bitstream itself in
10the third header, the codec setup header. This packed configuration
11consists of multiple 'codebooks', each containing a specific
12Huffman-equivalent representation for decoding compressed codewords as
13well as an optional lookup table of output vector values to which a
14decoded Huffman value is applied as an offset, generating the final
15decoded output corresponding to a given compressed codeword.
16
17\subsubsection{Bitwise operation}
18The codebook mechanism is built on top of the vorbis bitpacker. Both
19the codebooks themselves and the codewords they decode are unrolled
20from a packet as a series of arbitrary-width values read from the
21stream according to \xref{vorbis:spec:bitpacking}.
22
23
24
25
26\subsection{Packed codebook format}
27
28For purposes of the examples below, we assume that the storage
29system's native byte width is eight bits. This is not universally
30true; see \xref{vorbis:spec:bitpacking} for discussion
31relating to non-eight-bit bytes.
32
33\subsubsection{codebook decode}
34
35A codebook begins with a 24 bit sync pattern, 0x564342:
36
37\begin{Verbatim}[commandchars=\\\{\}]
38byte 0: [ 0 1 0 0 0 0 1 0 ] (0x42)
39byte 1: [ 0 1 0 0 0 0 1 1 ] (0x43)
40byte 2: [ 0 1 0 1 0 1 1 0 ] (0x56)
41\end{Verbatim}
42
4316 bit \varname{[codebook\_dimensions]} and 24 bit \varname{[codebook\_entries]} fields:
44
45\begin{Verbatim}[commandchars=\\\{\}]
46
47byte 3: [ X X X X X X X X ]
48byte 4: [ X X X X X X X X ] [codebook\_dimensions] (16 bit unsigned)
49
50byte 5: [ X X X X X X X X ]
51byte 6: [ X X X X X X X X ]
52byte 7: [ X X X X X X X X ] [codebook\_entries] (24 bit unsigned)
53
54\end{Verbatim}
55
56Next is the \varname{[ordered]} bit flag:
57
58\begin{Verbatim}[commandchars=\\\{\}]
59
60byte 8: [ X ] [ordered] (1 bit)
61
62\end{Verbatim}
63
64Each entry, numbering a
65total of \varname{[codebook\_entries]}, is assigned a codeword length.
66We now read the list of codeword lengths and store these lengths in
67the array \varname{[codebook\_codeword\_lengths]}. Decode of lengths is
68according to whether the \varname{[ordered]} flag is set or unset.
69
70\begin{itemize}
71\item
72 If the \varname{[ordered]} flag is unset, the codeword list is not
73 length ordered and the decoder needs to read each codeword length
74 one-by-one.
75
76 The decoder first reads one additional bit flag, the
77 \varname{[sparse]} flag. This flag determines whether or not the
78 codebook contains unused entries that are not to be included in the
79 codeword decode tree:
80
81\begin{Verbatim}[commandchars=\\\{\}]
82byte 8: [ X 1 ] [sparse] flag (1 bit)
83\end{Verbatim}
84
85 The decoder now performs for each of the \varname{[codebook\_entries]}
86 codebook entries:
87
88\begin{Verbatim}[commandchars=\\\{\}]
89
90 1) if([sparse] is set) \{
91
92 2) [flag] = read one bit;
93 3) if([flag] is set) \{
94
95 4) [length] = read a five bit unsigned integer;
96 5) codeword length for this entry is [length]+1;
97
98 \} else \{
99
100 6) this entry is unused. mark it as such.
101
102 \}
103
104 \} else the sparse flag is not set \{
105
106 7) [length] = read a five bit unsigned integer;
107 8) the codeword length for this entry is [length]+1;
108
109 \}
110
111\end{Verbatim}
112
113\item
114 If the \varname{[ordered]} flag is set, the codeword list for this
115 codebook is encoded in ascending length order. Rather than reading
116 a length for every codeword, the encoder reads the number of
117 codewords per length. That is, beginning at entry zero:
118
119\begin{Verbatim}[commandchars=\\\{\}]
120 1) [current\_entry] = 0;
121 2) [current\_length] = read a five bit unsigned integer and add 1;
122 3) [number] = read \link{vorbis:spec:ilog}{ilog}([codebook\_entries] - [current\_entry]) bits as an unsigned integer
123 4) set the entries [current\_entry] through [current\_entry]+[number]-1, inclusive,
124 of the [codebook\_codeword\_lengths] array to [current\_length]
125 5) set [current\_entry] to [number] + [current\_entry]
126 6) increment [current\_length] by 1
127 7) if [current\_entry] is greater than [codebook\_entries] ERROR CONDITION;
128 the decoder will not be able to read this stream.
129 8) if [current\_entry] is less than [codebook\_entries], repeat process starting at 3)
130 9) done.
131\end{Verbatim}
132
133\end{itemize}
134
135After all codeword lengths have been decoded, the decoder reads the
136vector lookup table. Vorbis I supports three lookup types:
137\begin{enumerate}
138\item
139No lookup
140\item
141Implicitly populated value mapping (lattice VQ)
142\item
143Explicitly populated value mapping (tessellated or 'foam'
144VQ)
145\end{enumerate}
146
147
148The lookup table type is read as a four bit unsigned integer:
149\begin{Verbatim}[commandchars=\\\{\}]
150 1) [codebook\_lookup\_type] = read four bits as an unsigned integer
151\end{Verbatim}
152
153Codebook decode precedes according to \varname{[codebook\_lookup\_type]}:
154\begin{itemize}
155\item
156Lookup type zero indicates no lookup to be read. Proceed past
157lookup decode.
158\item
159Lookup types one and two are similar, differing only in the
160number of lookup values to be read. Lookup type one reads a list of
161values that are permuted in a set pattern to build a list of vectors,
162each vector of order \varname{[codebook\_dimensions]} scalars. Lookup
163type two builds the same vector list, but reads each scalar for each
164vector explicitly, rather than building vectors from a smaller list of
165possible scalar values. Lookup decode proceeds as follows:
166
167\begin{Verbatim}[commandchars=\\\{\}]
168 1) [codebook\_minimum\_value] = \link{vorbis:spec:float32:unpack}{float32\_unpack}( read 32 bits as an unsigned integer)
169 2) [codebook\_delta\_value] = \link{vorbis:spec:float32:unpack}{float32\_unpack}( read 32 bits as an unsigned integer)
170 3) [codebook\_value\_bits] = read 4 bits as an unsigned integer and add 1
171 4) [codebook\_sequence\_p] = read 1 bit as a boolean flag
172
173 if ( [codebook\_lookup\_type] is 1 ) \{
174
175 5) [codebook\_lookup\_values] = \link{vorbis:spec:lookup1:values}{lookup1\_values}(\varname{[codebook\_entries]}, \varname{[codebook\_dimensions]} )
176
177 \} else \{
178
179 6) [codebook\_lookup\_values] = \varname{[codebook\_entries]} * \varname{[codebook\_dimensions]}
180
181 \}
182
183 7) read a total of [codebook\_lookup\_values] unsigned integers of [codebook\_value\_bits] each;
184 store these in order in the array [codebook\_multiplicands]
185\end{Verbatim}
186\item
187A \varname{[codebook\_lookup\_type]} of greater than two is reserved
188and indicates a stream that is not decodable by the specification in this
189document.
190
191\end{itemize}
192
193
194An 'end of packet' during any read operation in the above steps is
195considered an error condition rendering the stream undecodable.
196
197\paragraph{Huffman decision tree representation}
198
199The \varname{[codebook\_codeword\_lengths]} array and
200\varname{[codebook\_entries]} value uniquely define the Huffman decision
201tree used for entropy decoding.
202
203Briefly, each used codebook entry (recall that length-unordered
204codebooks support unused codeword entries) is assigned, in order, the
205lowest valued unused binary Huffman codeword possible. Assume the
206following codeword length list:
207
208\begin{Verbatim}[commandchars=\\\{\}]
209entry 0: length 2
210entry 1: length 4
211entry 2: length 4
212entry 3: length 4
213entry 4: length 4
214entry 5: length 2
215entry 6: length 3
216entry 7: length 3
217\end{Verbatim}
218
219Assigning codewords in order (lowest possible value of the appropriate
220length to highest) results in the following codeword list:
221
222\begin{Verbatim}[commandchars=\\\{\}]
223entry 0: length 2 codeword 00
224entry 1: length 4 codeword 0100
225entry 2: length 4 codeword 0101
226entry 3: length 4 codeword 0110
227entry 4: length 4 codeword 0111
228entry 5: length 2 codeword 10
229entry 6: length 3 codeword 110
230entry 7: length 3 codeword 111
231\end{Verbatim}
232
233
234\begin{note}
235Unlike most binary numerical values in this document, we
236intend the above codewords to be read and used bit by bit from left to
237right, thus the codeword '001' is the bit string 'zero, zero, one'.
238When determining 'lowest possible value' in the assignment definition
239above, the leftmost bit is the MSb.
240\end{note}
241
242It is clear that the codeword length list represents a Huffman
243decision tree with the entry numbers equivalent to the leaves numbered
244left-to-right:
245
246\begin{center}
247\includegraphics[width=10cm]{hufftree}
248\captionof{figure}{huffman tree illustration}
249\end{center}
250
251
252As we assign codewords in order, we see that each choice constructs a
253new leaf in the leftmost possible position.
254
255Note that it's possible to underspecify or overspecify a Huffman tree
256via the length list. In the above example, if codeword seven were
257eliminated, it's clear that the tree is unfinished:
258
259\begin{center}
260\includegraphics[width=10cm]{hufftree-under}
261\captionof{figure}{underspecified huffman tree illustration}
262\end{center}
263
264
265Similarly, in the original codebook, it's clear that the tree is fully
266populated and a ninth codeword is impossible. Both underspecified and
267overspecified trees are an error condition rendering the stream
268undecodable.
269
270Codebook entries marked 'unused' are simply skipped in the assigning
271process. They have no codeword and do not appear in the decision
272tree, thus it's impossible for any bit pattern read from the stream to
273decode to that entry number.
274
275\paragraph{Errata 20150226: Single entry codebooks}
276
277A 'single-entry codebook' is a codebook with one active codeword
278entry. A single-entry codebook may be either a fully populated
279codebook with only one declared entry, or a sparse codebook with only
280one entry marked used. The Vorbis I spec provides no means to specify
281a codeword length of zero, and as a result, a single-entry codebook is
282inherently malformed because it is underpopulated. The original
283specification did not address directly the matter of single-entry
284codebooks; they were implicitly illegal as it was not possible to
285write such a codebook with a valid tree structure.
286
287In r14811 of the libvorbis reference implementation, Xiph added an
288additional check to the codebook implementation to reject
289underpopulated Huffman trees. This change led to the discovery of
290single-entry books used 'in the wild' when the new, stricter checks
291rejected a number of apparently working streams.
292
293In order to minimize breakage of deployed (if technically erroneous)
294streams, r16073 of the reference implementation explicitly
295special-cased single-entry codebooks to tolerate the single-entry
296case. Commit r16073 also added the following to the specification:
297
298\blockquote{\sout{Take special care that a codebook with a single used
299 entry is handled properly; it consists of a single codework of
300 zero bits and ’reading’ a value out of such a codebook always
301 returns the single used value and sinks zero bits.
302}}
303
304The intent was to clarify the spec and codify current practice.
305However, this addition is erroneously at odds with the intent of preserving
306usability of existing streams using single-entry codebooks, disagrees
307with the code changes that reinstated decoding, and does not address how
308single-entry codebooks should be encoded.
309
310As such, the above addition made in r16037 is struck from the
311specification and replaced by the following:
312
313\blockquote{It is possible to declare a Vorbis codebook containing a
314 single codework entry. A single-entry codebook may be either a
315 fully populated codebook with \varname{[codebook\_entries]} set to
316 1, or a sparse codebook marking only one entry used. Note that it
317 is not possible to also encode a \varname{[codeword\_length]} of
318 zero for the single used codeword, as the unsigned value written to
319 the stream is \varname{[codeword\_length]-1}. Instead, encoder
320 implementations should indicate a \varname{[codeword\_length]} of 1
321 and 'write' the codeword to a stream during audio encoding by
322 writing a single zero bit.
323
324 Decoder implementations shall reject a codebook if it contains only
325 one used entry and the encoded \varname{[codeword\_length]} of that
326 entry is not 1. 'Reading' a value from single-entry codebook always
327 returns the single used codeword value and sinks one bit. Decoders
328 should tolerate that the bit read from the stream be '1' instead of
329 '0'; both values shall return the single used codeword.}
330
331\paragraph{VQ lookup table vector representation}
332
333Unpacking the VQ lookup table vectors relies on the following values:
334\begin{programlisting}
335the [codebook\_multiplicands] array
336[codebook\_minimum\_value]
337[codebook\_delta\_value]
338[codebook\_sequence\_p]
339[codebook\_lookup\_type]
340[codebook\_entries]
341[codebook\_dimensions]
342[codebook\_lookup\_values]
343\end{programlisting}
344
345\bigskip
346
347Decoding (unpacking) a specific vector in the vector lookup table
348proceeds according to \varname{[codebook\_lookup\_type]}. The unpacked
349vector values are what a codebook would return during audio packet
350decode in a VQ context.
351
352\paragraph{Vector value decode: Lookup type 1}
353
354Lookup type one specifies a lattice VQ lookup table built
355algorithmically from a list of scalar values. Calculate (unpack) the
356final values of a codebook entry vector from the entries in
357\varname{[codebook\_multiplicands]} as follows (\varname{[value\_vector]}
358is the output vector representing the vector of values for entry number
359\varname{[lookup\_offset]} in this codebook):
360
361\begin{Verbatim}[commandchars=\\\{\}]
362 1) [last] = 0;
363 2) [index\_divisor] = 1;
364 3) iterate [i] over the range 0 ... [codebook\_dimensions]-1 (once for each scalar value in the value vector) \{
365
366 4) [multiplicand\_offset] = ( [lookup\_offset] divided by [index\_divisor] using integer
367 division ) integer modulo [codebook\_lookup\_values]
368
369 5) vector [value\_vector] element [i] =
370 ( [codebook\_multiplicands] array element number [multiplicand\_offset] ) *
371 [codebook\_delta\_value] + [codebook\_minimum\_value] + [last];
372
373 6) if ( [codebook\_sequence\_p] is set ) then set [last] = vector [value\_vector] element [i]
374
375 7) [index\_divisor] = [index\_divisor] * [codebook\_lookup\_values]
376
377 \}
378
379 8) vector calculation completed.
380\end{Verbatim}
381
382
383
384\paragraph{Vector value decode: Lookup type 2}
385
386Lookup type two specifies a VQ lookup table in which each scalar in
387each vector is explicitly set by the \varname{[codebook\_multiplicands]}
388array in a one-to-one mapping. Calculate [unpack] the
389final values of a codebook entry vector from the entries in
390\varname{[codebook\_multiplicands]} as follows (\varname{[value\_vector]}
391is the output vector representing the vector of values for entry number
392\varname{[lookup\_offset]} in this codebook):
393
394\begin{Verbatim}[commandchars=\\\{\}]
395 1) [last] = 0;
396 2) [multiplicand\_offset] = [lookup\_offset] * [codebook\_dimensions]
397 3) iterate [i] over the range 0 ... [codebook\_dimensions]-1 (once for each scalar value in the value vector) \{
398
399 4) vector [value\_vector] element [i] =
400 ( [codebook\_multiplicands] array element number [multiplicand\_offset] ) *
401 [codebook\_delta\_value] + [codebook\_minimum\_value] + [last];
402
403 5) if ( [codebook\_sequence\_p] is set ) then set [last] = vector [value\_vector] element [i]
404
405 6) increment [multiplicand\_offset]
406
407 \}
408
409 7) vector calculation completed.
410\end{Verbatim}
411
412
413
414
415
416
417
418
419
420\subsection{Use of the codebook abstraction}
421
422The decoder uses the codebook abstraction much as it does the
423bit-unpacking convention; a specific codebook reads a
424codeword from the bitstream, decoding it into an entry number, and then
425returns that entry number to the decoder (when used in a scalar
426entropy coding context), or uses that entry number as an offset into
427the VQ lookup table, returning a vector of values (when used in a context
428desiring a VQ value). Scalar or VQ context is always explicit; any call
429to the codebook mechanism requests either a scalar entry number or a
430lookup vector.
431
432Note that VQ lookup type zero indicates that there is no lookup table;
433requesting decode using a codebook of lookup type 0 in any context
434expecting a vector return value (even in a case where a vector of
435dimension one) is forbidden. If decoder setup or decode requests such
436an action, that is an error condition rendering the packet
437undecodable.
438
439Using a codebook to read from the packet bitstream consists first of
440reading and decoding the next codeword in the bitstream. The decoder
441reads bits until the accumulated bits match a codeword in the
442codebook. This process can be though of as logically walking the
443Huffman decode tree by reading one bit at a time from the bitstream,
444and using the bit as a decision boolean to take the 0 branch (left in
445the above examples) or the 1 branch (right in the above examples).
446Walking the tree finishes when the decode process hits a leaf in the
447decision tree; the result is the entry number corresponding to that
448leaf. Reading past the end of a packet propagates the 'end-of-stream'
449condition to the decoder.
450
451When used in a scalar context, the resulting codeword entry is the
452desired return value.
453
454When used in a VQ context, the codeword entry number is used as an
455offset into the VQ lookup table. The value returned to the decoder is
456the vector of scalars corresponding to this offset.
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette