18e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels% -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*- 28e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels%!TEX root = Vorbis_I_spec.tex 38e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels% $Id$ 48e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\section{Probability Model and Codebooks} \label{vorbis:spec:codebook} 58e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 68e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsection{Overview} 78e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 88e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsUnlike practically every other mainstream audio codec, Vorbis has no 98e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsstatically configured probability model, instead packing all entropy 108e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdecoding configuration, VQ and Huffman, into the bitstream itself in 118e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthe third header, the codec setup header. This packed configuration 128e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsconsists of multiple 'codebooks', each containing a specific 138e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsHuffman-equivalent representation for decoding compressed codewords as 148e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelswell as an optional lookup table of output vector values to which a 158e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdecoded Huffman value is applied as an offset, generating the final 168e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdecoded output corresponding to a given compressed codeword. 178e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 188e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsubsection{Bitwise operation} 198e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsThe codebook mechanism is built on top of the vorbis bitpacker. Both 208e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthe codebooks themselves and the codewords they decode are unrolled 218e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsfrom a packet as a series of arbitrary-width values read from the 228e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsstream according to \xref{vorbis:spec:bitpacking}. 238e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 248e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 258e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 268e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 278e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsection{Packed codebook format} 288e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 298e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsFor purposes of the examples below, we assume that the storage 308e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelssystem's native byte width is eight bits. This is not universally 318e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelstrue; see \xref{vorbis:spec:bitpacking} for discussion 328e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsrelating to non-eight-bit bytes. 338e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 348e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsubsection{codebook decode} 358e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 368e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsA codebook begins with a 24 bit sync pattern, 0x564342: 378e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 388e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 398e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbyte 0: [ 0 1 0 0 0 0 1 0 ] (0x42) 408e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbyte 1: [ 0 1 0 0 0 0 1 1 ] (0x43) 418e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbyte 2: [ 0 1 0 1 0 1 1 0 ] (0x56) 428e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 438e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 448e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels16 bit \varname{[codebook_dimensions]} and 24 bit \varname{[codebook_entries]} fields: 458e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 468e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 478e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 488e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbyte 3: [ X X X X X X X X ] 498e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbyte 4: [ X X X X X X X X ] [codebook_dimensions] (16 bit unsigned) 508e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 518e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbyte 5: [ X X X X X X X X ] 528e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbyte 6: [ X X X X X X X X ] 538e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbyte 7: [ X X X X X X X X ] [codebook_entries] (24 bit unsigned) 548e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 558e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 568e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 578e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsNext is the \varname{[ordered]} bit flag: 588e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 598e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 608e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 618e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbyte 8: [ X ] [ordered] (1 bit) 628e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 638e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 648e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 658e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsEach entry, numbering a 668e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelstotal of \varname{[codebook_entries]}, is assigned a codeword length. 678e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsWe now read the list of codeword lengths and store these lengths in 688e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthe array \varname{[codebook_codeword_lengths]}. Decode of lengths is 698e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsaccording to whether the \varname{[ordered]} flag is set or unset. 708e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 718e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{itemize} 728e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\item 738e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels If the \varname{[ordered]} flag is unset, the codeword list is not 748e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels length ordered and the decoder needs to read each codeword length 758e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels one-by-one. 768e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 778e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels The decoder first reads one additional bit flag, the 788e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \varname{[sparse]} flag. This flag determines whether or not the 798e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels codebook contains unused entries that are not to be included in the 808e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels codeword decode tree: 818e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 828e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 838e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbyte 8: [ X 1 ] [sparse] flag (1 bit) 848e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 858e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 868e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels The decoder now performs for each of the \varname{[codebook_entries]} 878e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels codebook entries: 888e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 898e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 908e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 918e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1) if([sparse] is set) \{ 928e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 938e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2) [flag] = read one bit; 948e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3) if([flag] is set) \{ 958e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 968e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4) [length] = read a five bit unsigned integer; 978e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 5) codeword length for this entry is [length]+1; 988e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 998e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \} else \{ 1008e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1018e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 6) this entry is unused. mark it as such. 1028e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1038e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \} 1048e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1058e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \} else the sparse flag is not set \{ 1068e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1078e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 7) [length] = read a five bit unsigned integer; 1088e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 8) the codeword length for this entry is [length]+1; 1098e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1108e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \} 1118e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1128e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 1138e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1148e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\item 1158e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels If the \varname{[ordered]} flag is set, the codeword list for this 1168e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels codebook is encoded in ascending length order. Rather than reading 1178e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels a length for every codeword, the encoder reads the number of 1188e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels codewords per length. That is, beginning at entry zero: 1198e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1208e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 1218e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1) [current_entry] = 0; 1228e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2) [current_length] = read a five bit unsigned integer and add 1; 1238e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3) [number] = read \link{vorbis:spec:ilog}{ilog}([codebook_entries] - [current_entry]) bits as an unsigned integer 1248e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4) set the entries [current_entry] through [current_entry]+[number]-1, inclusive, 1258e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels of the [codebook_codeword_lengths] array to [current_length] 1268e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 5) set [current_entry] to [number] + [current_entry] 1278e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 6) increment [current_length] by 1 1288e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 7) if [current_entry] is greater than [codebook_entries] ERROR CONDITION; 1298e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels the decoder will not be able to read this stream. 1308e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 8) if [current_entry] is less than [codebook_entries], repeat process starting at 3) 1318e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 9) done. 1328e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 1338e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1348e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{itemize} 1358e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1368e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsAfter all codeword lengths have been decoded, the decoder reads the 1378e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsvector lookup table. Vorbis I supports three lookup types: 1388e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{enumerate} 1398e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\item 1408e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsNo lookup 1418e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\item 1428e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsImplicitly populated value mapping (lattice VQ) 1438e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\item 1448e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsExplicitly populated value mapping (tessellated or 'foam' 1458e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsVQ) 1468e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{enumerate} 1478e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1488e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1498e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsThe lookup table type is read as a four bit unsigned integer: 1508e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 1518e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1) [codebook_lookup_type] = read four bits as an unsigned integer 1528e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 1538e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1548e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsCodebook decode precedes according to \varname{[codebook_lookup_type]}: 1558e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{itemize} 1568e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\item 1578e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsLookup type zero indicates no lookup to be read. Proceed past 1588e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelslookup decode. 1598e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\item 1608e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsLookup types one and two are similar, differing only in the 1618e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsnumber of lookup values to be read. Lookup type one reads a list of 1628e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsvalues that are permuted in a set pattern to build a list of vectors, 1638e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelseach vector of order \varname{[codebook_dimensions]} scalars. Lookup 1648e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelstype two builds the same vector list, but reads each scalar for each 1658e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsvector explicitly, rather than building vectors from a smaller list of 1668e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelspossible scalar values. Lookup decode proceeds as follows: 1678e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1688e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 1698e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1) [codebook_minimum_value] = \link{vorbis:spec:float32:unpack}{float32_unpack}( read 32 bits as an unsigned integer) 1708e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2) [codebook_delta_value] = \link{vorbis:spec:float32:unpack}{float32_unpack}( read 32 bits as an unsigned integer) 1718e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3) [codebook_value_bits] = read 4 bits as an unsigned integer and add 1 1728e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4) [codebook_sequence_p] = read 1 bit as a boolean flag 1738e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1748e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels if ( [codebook_lookup_type] is 1 ) \{ 1758e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1768e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 5) [codebook_lookup_values] = \link{vorbis:spec:lookup1:values}{lookup1_values}(\varname{[codebook_entries]}, \varname{[codebook_dimensions]} ) 1778e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1788e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \} else \{ 1798e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1808e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 6) [codebook_lookup_values] = \varname{[codebook_entries]} * \varname{[codebook_dimensions]} 1818e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1828e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \} 1838e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1848e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 7) read a total of [codebook_lookup_values] unsigned integers of [codebook_value_bits] each; 1858e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels store these in order in the array [codebook_multiplicands] 1868e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 1878e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\item 1888e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsA \varname{[codebook_lookup_type]} of greater than two is reserved 1898e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsand indicates a stream that is not decodable by the specification in this 1908e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdocument. 1918e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1928e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{itemize} 1938e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1948e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1958e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsAn 'end of packet' during any read operation in the above steps is 1968e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsconsidered an error condition rendering the stream undecodable. 1978e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1988e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\paragraph{Huffman decision tree representation} 1998e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2008e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsThe \varname{[codebook_codeword_lengths]} array and 2018e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[codebook_entries]} value uniquely define the Huffman decision 2028e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelstree used for entropy decoding. 2038e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2048e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsBriefly, each used codebook entry (recall that length-unordered 2058e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelscodebooks support unused codeword entries) is assigned, in order, the 2068e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelslowest valued unused binary Huffman codeword possible. Assume the 2078e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsfollowing codeword length list: 2088e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2098e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 2108e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 0: length 2 2118e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 1: length 4 2128e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 2: length 4 2138e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 3: length 4 2148e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 4: length 4 2158e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 5: length 2 2168e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 6: length 3 2178e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 7: length 3 2188e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 2198e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2208e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsAssigning codewords in order (lowest possible value of the appropriate 2218e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelslength to highest) results in the following codeword list: 2228e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2238e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 2248e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 0: length 2 codeword 00 2258e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 1: length 4 codeword 0100 2268e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 2: length 4 codeword 0101 2278e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 3: length 4 codeword 0110 2288e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 4: length 4 codeword 0111 2298e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 5: length 2 codeword 10 2308e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 6: length 3 codeword 110 2318e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry 7: length 3 codeword 111 2328e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 2338e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2348e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2358e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{note} 2368e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsUnlike most binary numerical values in this document, we 2378e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsintend the above codewords to be read and used bit by bit from left to 2388e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsright, thus the codeword '001' is the bit string 'zero, zero, one'. 2398e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsWhen determining 'lowest possible value' in the assignment definition 2408e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsabove, the leftmost bit is the MSb. 2418e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{note} 2428e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2438e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsIt is clear that the codeword length list represents a Huffman 2448e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdecision tree with the entry numbers equivalent to the leaves numbered 2458e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsleft-to-right: 2468e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2478e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{center} 2488e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\includegraphics[width=10cm]{hufftree} 2498e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\captionof{figure}{huffman tree illustration} 2508e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{center} 2518e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2528e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2538e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsAs we assign codewords in order, we see that each choice constructs a 2548e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsnew leaf in the leftmost possible position. 2558e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2568e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsNote that it's possible to underspecify or overspecify a Huffman tree 2578e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsvia the length list. In the above example, if codeword seven were 2588e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelseliminated, it's clear that the tree is unfinished: 2598e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2608e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{center} 2618e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\includegraphics[width=10cm]{hufftree-under} 2628e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\captionof{figure}{underspecified huffman tree illustration} 2638e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{center} 2648e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2658e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2668e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsSimilarly, in the original codebook, it's clear that the tree is fully 2678e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelspopulated and a ninth codeword is impossible. Both underspecified and 2688e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsoverspecified trees are an error condition rendering the stream 2698e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsundecodable. Take special care that a codebook with a single used 2708e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentry is handled properly; it consists of a single codework of zero 2718e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbits and 'reading' a value out of such a codebook always returns the 2728e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelssingle used value and sinks zero bits. 2738e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2748e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsCodebook entries marked 'unused' are simply skipped in the assigning 2758e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsprocess. They have no codeword and do not appear in the decision 2768e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelstree, thus it's impossible for any bit pattern read from the stream to 2778e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdecode to that entry number. 2788e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2798e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2808e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2818e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\paragraph{VQ lookup table vector representation} 2828e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2838e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsUnpacking the VQ lookup table vectors relies on the following values: 2848e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{programlisting} 2858e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthe [codebook_multiplicands] array 2868e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels[codebook_minimum_value] 2878e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels[codebook_delta_value] 2888e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels[codebook_sequence_p] 2898e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels[codebook_lookup_type] 2908e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels[codebook_entries] 2918e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels[codebook_dimensions] 2928e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels[codebook_lookup_values] 2938e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{programlisting} 2948e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2958e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\bigskip 2968e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2978e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsDecoding (unpacking) a specific vector in the vector lookup table 2988e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsproceeds according to \varname{[codebook_lookup_type]}. The unpacked 2998e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsvector values are what a codebook would return during audio packet 3008e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdecode in a VQ context. 3018e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3028e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\paragraph{Vector value decode: Lookup type 1} 3038e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3048e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsLookup type one specifies a lattice VQ lookup table built 3058e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsalgorithmically from a list of scalar values. Calculate (unpack) the 3068e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsfinal values of a codebook entry vector from the entries in 3078e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[codebook_multiplicands]} as follows (\varname{[value_vector]} 3088e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsis the output vector representing the vector of values for entry number 3098e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[lookup_offset]} in this codebook): 3108e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3118e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 3128e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1) [last] = 0; 3138e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2) [index_divisor] = 1; 3148e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) \{ 3158e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3168e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4) [multiplicand_offset] = ( [lookup_offset] divided by [index_divisor] using integer 3178e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels division ) integer modulo [codebook_lookup_values] 3188e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3198e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 5) vector [value_vector] element [i] = 3208e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels ( [codebook_multiplicands] array element number [multiplicand_offset] ) * 3218e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels [codebook_delta_value] + [codebook_minimum_value] + [last]; 3228e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3238e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 6) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i] 3248e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3258e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 7) [index_divisor] = [index_divisor] * [codebook_lookup_values] 3268e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3278e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \} 3288e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3298e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 8) vector calculation completed. 3308e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 3318e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3328e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3338e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3348e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\paragraph{Vector value decode: Lookup type 2} 3358e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3368e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsLookup type two specifies a VQ lookup table in which each scalar in 3378e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelseach vector is explicitly set by the \varname{[codebook_multiplicands]} 3388e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsarray in a one-to-one mapping. Calculate [unpack] the 3398e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsfinal values of a codebook entry vector from the entries in 3408e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[codebook_multiplicands]} as follows (\varname{[value_vector]} 3418e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsis the output vector representing the vector of values for entry number 3428e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[lookup_offset]} in this codebook): 3438e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3448e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{Verbatim}[commandchars=\\\{\}] 3458e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1) [last] = 0; 3468e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2) [multiplicand_offset] = [lookup_offset] * [codebook_dimensions] 3478e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3) iterate [i] over the range 0 ... [codebook_dimensions]-1 (once for each scalar value in the value vector) \{ 3488e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3498e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4) vector [value_vector] element [i] = 3508e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels ( [codebook_multiplicands] array element number [multiplicand_offset] ) * 3518e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels [codebook_delta_value] + [codebook_minimum_value] + [last]; 3528e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3538e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 5) if ( [codebook_sequence_p] is set ) then set [last] = vector [value_vector] element [i] 3548e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3558e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 6) increment [multiplicand_offset] 3568e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3578e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \} 3588e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3598e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 7) vector calculation completed. 3608e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{Verbatim} 3618e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3628e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3638e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3648e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3658e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3668e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3678e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3688e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3698e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3708e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsection{Use of the codebook abstraction} 3718e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3728e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsThe decoder uses the codebook abstraction much as it does the 3738e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbit-unpacking convention; a specific codebook reads a 3748e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelscodeword from the bitstream, decoding it into an entry number, and then 3758e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsreturns that entry number to the decoder (when used in a scalar 3768e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsentropy coding context), or uses that entry number as an offset into 3778e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthe VQ lookup table, returning a vector of values (when used in a context 3788e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdesiring a VQ value). Scalar or VQ context is always explicit; any call 3798e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsto the codebook mechanism requests either a scalar entry number or a 3808e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelslookup vector. 3818e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3828e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsNote that VQ lookup type zero indicates that there is no lookup table; 3838e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsrequesting decode using a codebook of lookup type 0 in any context 3848e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsexpecting a vector return value (even in a case where a vector of 3858e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdimension one) is forbidden. If decoder setup or decode requests such 3868e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsan action, that is an error condition rendering the packet 3878e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsundecodable. 3888e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3898e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsUsing a codebook to read from the packet bitstream consists first of 3908e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsreading and decoding the next codeword in the bitstream. The decoder 3918e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsreads bits until the accumulated bits match a codeword in the 3928e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelscodebook. This process can be though of as logically walking the 3938e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsHuffman decode tree by reading one bit at a time from the bitstream, 3948e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsand using the bit as a decision boolean to take the 0 branch (left in 3958e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthe above examples) or the 1 branch (right in the above examples). 3968e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsWalking the tree finishes when the decode process hits a leaf in the 3978e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdecision tree; the result is the entry number corresponding to that 3988e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsleaf. Reading past the end of a packet propagates the 'end-of-stream' 3998e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelscondition to the decoder. 4008e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4018e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsWhen used in a scalar context, the resulting codeword entry is the 4028e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdesired return value. 4038e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4048e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsWhen used in a VQ context, the codeword entry number is used as an 4058e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsoffset into the VQ lookup table. The value returned to the decoder is 4068e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthe vector of scalars corresponding to this offset. 407