External projects with established upstream are no longer part of this source tree

1 files changed, 0 insertions, 456 deletions

diff --git a/contrib/vorbis/doc/03-codebook.tex b/contrib/vorbis/doc/03-codebook.tex
deleted file mode 100644
index 11516a3..0000000
--- a/contrib/vorbis/doc/03-codebook.tex
+++ /dev/null
@@ -1,456 +0,0 @@
-% -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*-
-%!TEX root = Vorbis_I_spec.tex
-\section{Probability Model and Codebooks} \label{vorbis:spec:codebook}
-
-\subsection{Overview}
-
-Unlike practically every other mainstream audio codec, Vorbis has no
-statically configured probability model, instead packing all entropy
-decoding configuration, VQ and Huffman, into the bitstream itself in
-the third header, the codec setup header.  This packed configuration
-consists of multiple 'codebooks', each containing a specific
-Huffman-equivalent representation for decoding compressed codewords as
-well as an optional lookup table of output vector values to which a
-decoded Huffman value is applied as an offset, generating the final
-decoded output corresponding to a given compressed codeword.
-
-\subsubsection{Bitwise operation}
-The codebook mechanism is built on top of the vorbis bitpacker. Both
-the codebooks themselves and the codewords they decode are unrolled
-from a packet as a series of arbitrary-width values read from the
-stream according to \xref{vorbis:spec:bitpacking}.
-
-
-
-
-\subsection{Packed codebook format}
-
-For purposes of the examples below, we assume that the storage
-system's native byte width is eight bits.  This is not universally
-true; see \xref{vorbis:spec:bitpacking} for discussion
-relating to non-eight-bit bytes.
-
-\subsubsection{codebook decode}
-
-A codebook begins with a 24 bit sync pattern, 0x564342:
-
-\begin{Verbatim}[commandchars=\\\{\}]
-byte 0: [ 0 1 0 0 0 0 1 0 ] (0x42)
-byte 1: [ 0 1 0 0 0 0 1 1 ] (0x43)
-byte 2: [ 0 1 0 1 0 1 1 0 ] (0x56)
-\end{Verbatim}
-
-16 bit \varname{[codebook\_dimensions]} and 24 bit \varname{[codebook\_entries]} fields:
-
-\begin{Verbatim}[commandchars=\\\{\}]
-
-byte 3: [ X X X X X X X X ]
-byte 4: [ X X X X X X X X ] [codebook\_dimensions] (16 bit unsigned)
-
-byte 5: [ X X X X X X X X ]
-byte 6: [ X X X X X X X X ]
-byte 7: [ X X X X X X X X ] [codebook\_entries] (24 bit unsigned)
-
-\end{Verbatim}
-
-Next is the \varname{[ordered]} bit flag:
-
-\begin{Verbatim}[commandchars=\\\{\}]
-
-byte 8: [               X ] [ordered] (1 bit)
-
-\end{Verbatim}
-
-Each entry, numbering a
-total of \varname{[codebook\_entries]}, is assigned a codeword length.
-We now read the list of codeword lengths and store these lengths in
-the array \varname{[codebook\_codeword\_lengths]}. Decode of lengths is
-according to whether the \varname{[ordered]} flag is set or unset.
-
-\begin{itemize}
-\item
-  If the \varname{[ordered]} flag is unset, the codeword list is not
-  length ordered and the decoder needs to read each codeword length
-  one-by-one.
-
-  The decoder first reads one additional bit flag, the
-  \varname{[sparse]} flag.  This flag determines whether or not the
-  codebook contains unused entries that are not to be included in the
-  codeword decode tree:
-
-\begin{Verbatim}[commandchars=\\\{\}]
-byte 8: [             X 1 ] [sparse] flag (1 bit)
-\end{Verbatim}
-
-  The decoder now performs for each of the \varname{[codebook\_entries]}
-  codebook entries:
-
-\begin{Verbatim}[commandchars=\\\{\}]
-
-  1) if([sparse] is set) \{
-
-         2) [flag] = read one bit;
-         3) if([flag] is set) \{
-
-              4) [length] = read a five bit unsigned integer;
-              5) codeword length for this entry is [length]+1;
-
-            \} else \{
-
-              6) this entry is unused.  mark it as such.
-
-            \}
-
-     \} else the sparse flag is not set \{
-
-        7) [length] = read a five bit unsigned integer;
-        8) the codeword length for this entry is [length]+1;
-
-     \}
-
-\end{Verbatim}
-
-\item
-  If the \varname{[ordered]} flag is set, the codeword list for this
-  codebook is encoded in ascending length order.  Rather than reading
-  a length for every codeword, the encoder reads the number of
-  codewords per length.  That is, beginning at entry zero:
-
-\begin{Verbatim}[commandchars=\\\{\}]
-  1) [current\_entry] = 0;
-  2) [current\_length] = read a five bit unsigned integer and add 1;
-  3) [number] = read \link{vorbis:spec:ilog}{ilog}([codebook\_entries] - [current\_entry]) bits as an unsigned integer
-  4) set the entries [current\_entry] through [current\_entry]+[number]-1, inclusive,
-    of the [codebook\_codeword\_lengths] array to [current\_length]
-  5) set [current\_entry] to [number] + [current\_entry]
-  6) increment [current\_length] by 1
-  7) if [current\_entry] is greater than [codebook\_entries] ERROR CONDITION;
-    the decoder will not be able to read this stream.
-  8) if [current\_entry] is less than [codebook\_entries], repeat process starting at 3)
-  9) done.
-\end{Verbatim}
-
-\end{itemize}
-
-After all codeword lengths have been decoded, the decoder reads the
-vector lookup table.  Vorbis I supports three lookup types:
-\begin{enumerate}
-\item
-No lookup
-\item
-Implicitly populated value mapping (lattice VQ)
-\item
-Explicitly populated value mapping (tessellated or 'foam'
-VQ)
-\end{enumerate}
-
-
-The lookup table type is read as a four bit unsigned integer:
-\begin{Verbatim}[commandchars=\\\{\}]
-  1) [codebook\_lookup\_type] = read four bits as an unsigned integer
-\end{Verbatim}
-
-Codebook decode precedes according to \varname{[codebook\_lookup\_type]}:
-\begin{itemize}
-\item
-Lookup type zero indicates no lookup to be read.  Proceed past
-lookup decode.
-\item
-Lookup types one and two are similar, differing only in the
-number of lookup values to be read.  Lookup type one reads a list of
-values that are permuted in a set pattern to build a list of vectors,
-each vector of order \varname{[codebook\_dimensions]} scalars.  Lookup
-type two builds the same vector list, but reads each scalar for each
-vector explicitly, rather than building vectors from a smaller list of
-possible scalar values.  Lookup decode proceeds as follows:
-
-\begin{Verbatim}[commandchars=\\\{\}]
-  1) [codebook\_minimum\_value] = \link{vorbis:spec:float32:unpack}{float32\_unpack}( read 32 bits as an unsigned integer)
-  2) [codebook\_delta\_value] = \link{vorbis:spec:float32:unpack}{float32\_unpack}( read 32 bits as an unsigned integer)
-  3) [codebook\_value\_bits] = read 4 bits as an unsigned integer and add 1
-  4) [codebook\_sequence\_p] = read 1 bit as a boolean flag
-
-  if ( [codebook\_lookup\_type] is 1 ) \{
-
-     5) [codebook\_lookup\_values] = \link{vorbis:spec:lookup1:values}{lookup1\_values}(\varname{[codebook\_entries]}, \varname{[codebook\_dimensions]} )
-
-  \} else \{
-
-     6) [codebook\_lookup\_values] = \varname{[codebook\_entries]} * \varname{[codebook\_dimensions]}
-
-  \}
-
-  7) read a total of [codebook\_lookup\_values] unsigned integers of [codebook\_value\_bits] each;
-     store these in order in the array [codebook\_multiplicands]
-\end{Verbatim}
-\item
-A \varname{[codebook\_lookup\_type]} of greater than two is reserved
-and indicates a stream that is not decodable by the specification in this
-document.
-
-\end{itemize}
-
-
-An 'end of packet' during any read operation in the above steps is
-considered an error condition rendering the stream undecodable.
-
-\paragraph{Huffman decision tree representation}
-
-The \varname{[codebook\_codeword\_lengths]} array and
-\varname{[codebook\_entries]} value uniquely define the Huffman decision
-tree used for entropy decoding.
-
-Briefly, each used codebook entry (recall that length-unordered
-codebooks support unused codeword entries) is assigned, in order, the
-lowest valued unused binary Huffman codeword possible.  Assume the
-following codeword length list:
-
-\begin{Verbatim}[commandchars=\\\{\}]
-entry 0: length 2
-entry 1: length 4
-entry 2: length 4
-entry 3: length 4
-entry 4: length 4
-entry 5: length 2
-entry 6: length 3
-entry 7: length 3
-\end{Verbatim}
-
-Assigning codewords in order (lowest possible value of the appropriate
-length to highest) results in the following codeword list:
-
-\begin{Verbatim}[commandchars=\\\{\}]
-entry 0: length 2 codeword 00
-entry 1: length 4 codeword 0100
-entry 2: length 4 codeword 0101
-entry 3: length 4 codeword 0110
-entry 4: length 4 codeword 0111
-entry 5: length 2 codeword 10
-entry 6: length 3 codeword 110
-entry 7: length 3 codeword 111
-\end{Verbatim}
-
-
-\begin{note}
-Unlike most binary numerical values in this document, we
-intend the above codewords to be read and used bit by bit from left to
-right, thus the codeword '001' is the bit string 'zero, zero, one'.
-When determining 'lowest possible value' in the assignment definition
-above, the leftmost bit is the MSb.
-\end{note}
-
-It is clear that the codeword length list represents a Huffman
-decision tree with the entry numbers equivalent to the leaves numbered
-left-to-right:
-
-\begin{center}
-\includegraphics[width=10cm]{hufftree}
-\captionof{figure}{huffman tree illustration}
-\end{center}
-
-
-As we assign codewords in order, we see that each choice constructs a
-new leaf in the leftmost possible position.
-
-Note that it's possible to underspecify or overspecify a Huffman tree
-via the length list.  In the above example, if codeword seven were
-eliminated, it's clear that the tree is unfinished:
-
-\begin{center}
-\includegraphics[width=10cm]{hufftree-under}
-\captionof{figure}{underspecified huffman tree illustration}
-\end{center}
-
-
-Similarly, in the original codebook, it's clear that the tree is fully
-populated and a ninth codeword is impossible.  Both underspecified and
-overspecified trees are an error condition rendering the stream
-undecodable.
-
-Codebook entries marked 'unused' are simply skipped in the assigning
-process.  They have no codeword and do not appear in the decision
-tree, thus it's impossible for any bit pattern read from the stream to
-decode to that entry number.
-
-\paragraph{Errata 20150226: Single entry codebooks}
-
-A 'single-entry codebook' is a codebook with one active codeword
-entry. A single-entry codebook may be either a fully populated
-codebook with only one declared entry, or a sparse codebook with only
-one entry marked used. The Vorbis I spec provides no means to specify
-a codeword length of zero, and as a result, a single-entry codebook is
-inherently malformed because it is underpopulated.  The original
-specification did not address directly the matter of single-entry
-codebooks; they were implicitly illegal as it was not possible to
-write such a codebook with a valid tree structure.
-
-In r14811 of the libvorbis reference implementation, Xiph added an
-additional check to the codebook implementation to reject
-underpopulated Huffman trees. This change led to the discovery of
-single-entry books used 'in the wild' when the new, stricter checks
-rejected a number of apparently working streams.
-
-In order to minimize breakage of deployed (if technically erroneous)
-streams, r16073 of the reference implementation explicitly
-special-cased single-entry codebooks to tolerate the single-entry
-case.  Commit r16073 also added the following to the specification:
-
-\blockquote{\sout{Take special care that a codebook with a single used
-    entry is handled properly; it consists of a single codework of
-    zero bits and ’reading’ a value out of such a codebook always
-    returns the single used value and sinks zero bits.
-}} 
-
-The intent was to clarify the spec and codify current practice.
-However, this addition is erroneously at odds with the intent of preserving
-usability of existing streams using single-entry codebooks, disagrees
-with the code changes that reinstated decoding, and does not address how
-single-entry codebooks should be encoded.
-
-As such, the above addition made in r16037 is struck from the
-specification and replaced by the following:
-
-\blockquote{It is possible to declare a Vorbis codebook containing a
-  single codework entry.  A single-entry codebook may be either a
-  fully populated codebook with \varname{[codebook\_entries]} set to
-  1, or a sparse codebook marking only one entry used.  Note that it
-  is not possible to also encode a \varname{[codeword\_length]} of
-  zero for the single used codeword, as the unsigned value written to
-  the stream is \varname{[codeword\_length]-1}.  Instead, encoder
-  implementations should indicate a \varname{[codeword\_length]} of 1
-  and 'write' the codeword to a stream during audio encoding by
-  writing a single zero bit.
-
-  Decoder implementations shall reject a codebook if it contains only
-  one used entry and the encoded \varname{[codeword\_length]} of that
-  entry is not 1.  'Reading' a value from single-entry codebook always
-  returns the single used codeword value and sinks one bit.  Decoders
-  should tolerate that the bit read from the stream be '1' instead of
-  '0'; both values shall return the single used codeword.}
-
-\paragraph{VQ lookup table vector representation}
-
-Unpacking the VQ lookup table vectors relies on the following values:
-\begin{programlisting}
-the [codebook\_multiplicands] array
-[codebook\_minimum\_value]
-[codebook\_delta\_value]
-[codebook\_sequence\_p]
-[codebook\_lookup\_type]
-[codebook\_entries]
-[codebook\_dimensions]
-[codebook\_lookup\_values]
-\end{programlisting}
-
-\bigskip
-
-Decoding (unpacking) a specific vector in the vector lookup table
-proceeds according to \varname{[codebook\_lookup\_type]}.  The unpacked
-vector values are what a codebook would return during audio packet
-decode in a VQ context.
-
-\paragraph{Vector value decode: Lookup type 1}
-
-Lookup type one specifies a lattice VQ lookup table built
-algorithmically from a list of scalar values.  Calculate (unpack) the
-final values of a codebook entry vector from the entries in
-\varname{[codebook\_multiplicands]} as follows (\varname{[value\_vector]}
-is the output vector representing the vector of values for entry number
-\varname{[lookup\_offset]} in this codebook):
-
-\begin{Verbatim}[commandchars=\\\{\}]
-  1) [last] = 0;
-  2) [index\_divisor] = 1;
-  3) iterate [i] over the range 0 ... [codebook\_dimensions]-1 (once for each scalar value in the value vector) \{
-
-       4) [multiplicand\_offset] = ( [lookup\_offset] divided by [index\_divisor] using integer
-          division ) integer modulo [codebook\_lookup\_values]
-
-       5) vector [value\_vector] element [i] =
-            ( [codebook\_multiplicands] array element number [multiplicand\_offset] ) *
-            [codebook\_delta\_value] + [codebook\_minimum\_value] + [last];
-
-       6) if ( [codebook\_sequence\_p] is set ) then set [last] = vector [value\_vector] element [i]
-
-       7) [index\_divisor] = [index\_divisor] * [codebook\_lookup\_values]
-
-     \}
-
-  8) vector calculation completed.
-\end{Verbatim}
-
-
-
-\paragraph{Vector value decode: Lookup type 2}
-
-Lookup type two specifies a VQ lookup table in which each scalar in
-each vector is explicitly set by the \varname{[codebook\_multiplicands]}
-array in a one-to-one mapping.  Calculate [unpack] the
-final values of a codebook entry vector from the entries in
-\varname{[codebook\_multiplicands]} as follows (\varname{[value\_vector]}
-is the output vector representing the vector of values for entry number
-\varname{[lookup\_offset]} in this codebook):
-
-\begin{Verbatim}[commandchars=\\\{\}]
-  1) [last] = 0;
-  2) [multiplicand\_offset] = [lookup\_offset] * [codebook\_dimensions]
-  3) iterate [i] over the range 0 ... [codebook\_dimensions]-1 (once for each scalar value in the value vector) \{
-
-       4) vector [value\_vector] element [i] =
-            ( [codebook\_multiplicands] array element number [multiplicand\_offset] ) *
-            [codebook\_delta\_value] + [codebook\_minimum\_value] + [last];
-
-       5) if ( [codebook\_sequence\_p] is set ) then set [last] = vector [value\_vector] element [i]
-
-       6) increment [multiplicand\_offset]
-
-     \}
-
-  7) vector calculation completed.
-\end{Verbatim}
-
-
-
-
-
-
-
-
-
-\subsection{Use of the codebook abstraction}
-
-The decoder uses the codebook abstraction much as it does the
-bit-unpacking convention; a specific codebook reads a
-codeword from the bitstream, decoding it into an entry number, and then
-returns that entry number to the decoder (when used in a scalar
-entropy coding context), or uses that entry number as an offset into
-the VQ lookup table, returning a vector of values (when used in a context
-desiring a VQ value). Scalar or VQ context is always explicit; any call
-to the codebook mechanism requests either a scalar entry number or a
-lookup vector.
-
-Note that VQ lookup type zero indicates that there is no lookup table;
-requesting decode using a codebook of lookup type 0 in any context
-expecting a vector return value (even in a case where a vector of
-dimension one) is forbidden.  If decoder setup or decode requests such
-an action, that is an error condition rendering the packet
-undecodable.
-
-Using a codebook to read from the packet bitstream consists first of
-reading and decoding the next codeword in the bitstream. The decoder
-reads bits until the accumulated bits match a codeword in the
-codebook.  This process can be though of as logically walking the
-Huffman decode tree by reading one bit at a time from the bitstream,
-and using the bit as a decision boolean to take the 0 branch (left in
-the above examples) or the 1 branch (right in the above examples).
-Walking the tree finishes when the decode process hits a leaf in the
-decision tree; the result is the entry number corresponding to that
-leaf.  Reading past the end of a packet propagates the 'end-of-stream'
-condition to the decoder.
-
-When used in a scalar context, the resulting codeword entry is the
-desired return value.
-
-When used in a VQ context, the codeword entry number is used as an
-offset into the VQ lookup table.  The value returned to the decoder is
-the vector of scalars corresponding to this offset.