cannam@86: % -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*-
cannam@86: %!TEX root = Vorbis_I_spec.tex
cannam@86: % $Id$
cannam@86: \section{Floor type 1 setup and decode} \label{vorbis:spec:floor1}
cannam@86: 
cannam@86: \subsection{Overview}
cannam@86: 
cannam@86: Vorbis floor type one uses a piecewise straight-line representation to
cannam@86: encode a spectral envelope curve. The representation plots this curve
cannam@86: mechanically on a linear frequency axis and a logarithmic (dB)
cannam@86: amplitude axis. The integer plotting algorithm used is similar to
cannam@86: Bresenham's algorithm.
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \subsection{Floor 1 format}
cannam@86: 
cannam@86: \subsubsection{model}
cannam@86: 
cannam@86: Floor type one represents a spectral curve as a series of
cannam@86: line segments.  Synthesis constructs a floor curve using iterative
cannam@86: prediction in a process roughly equivalent to the following simplified
cannam@86: description:
cannam@86: 
cannam@86: \begin{itemize}
cannam@86:  \item  the first line segment (base case) is a logical line spanning
cannam@86: from x_0,y_0 to x_1,y_1 where in the base case x_0=0 and x_1=[n], the
cannam@86: full range of the spectral floor to be computed.
cannam@86: 
cannam@86: \item the induction step chooses a point x_new within an existing
cannam@86: logical line segment and produces a y_new value at that point computed
cannam@86: from the existing line's y value at x_new (as plotted by the line) and
cannam@86: a difference value decoded from the bitstream packet.
cannam@86: 
cannam@86: \item floor computation produces two new line segments, one running from
cannam@86: x_0,y_0 to x_new,y_new and from x_new,y_new to x_1,y_1. This step is
cannam@86: performed logically even if y_new represents no change to the
cannam@86: amplitude value at x_new so that later refinement is additionally
cannam@86: bounded at x_new.
cannam@86: 
cannam@86: \item the induction step repeats, using a list of x values specified in
cannam@86: the codec setup header at floor 1 initialization time.  Computation
cannam@86: is completed at the end of the x value list.
cannam@86: 
cannam@86: \end{itemize}
cannam@86: 
cannam@86: 
cannam@86: Consider the following example, with values chosen for ease of
cannam@86: understanding rather than representing typical configuration:
cannam@86: 
cannam@86: For the below example, we assume a floor setup with an [n] of 128.
cannam@86: The list of selected X values in increasing order is
cannam@86: 0,16,32,48,64,80,96,112 and 128.  In list order, the values interleave
cannam@86: as 0, 128, 64, 32, 96, 16, 48, 80 and 112.  The corresponding
cannam@86: list-order Y values as decoded from an example packet are 110, 20, -5,
cannam@86: -45, 0, -25, -10, 30 and -10.  We compute the floor in the following
cannam@86: way, beginning with the first line:
cannam@86: 
cannam@86: \begin{center}
cannam@86: \includegraphics[width=8cm]{floor1-1}
cannam@86: \captionof{figure}{graph of example floor}
cannam@86: \end{center}
cannam@86: 
cannam@86: We now draw new logical lines to reflect the correction to new_Y, and
cannam@86: iterate for X positions 32 and 96:
cannam@86: 
cannam@86: \begin{center}
cannam@86: \includegraphics[width=8cm]{floor1-2}
cannam@86: \captionof{figure}{graph of example floor}
cannam@86: \end{center}
cannam@86: 
cannam@86: Although the new Y value at X position 96 is unchanged, it is still
cannam@86: used later as an endpoint for further refinement.  From here on, the
cannam@86: pattern should be clear; we complete the floor computation as follows:
cannam@86: 
cannam@86: \begin{center}
cannam@86: \includegraphics[width=8cm]{floor1-3}
cannam@86: \captionof{figure}{graph of example floor}
cannam@86: \end{center}
cannam@86: 
cannam@86: \begin{center}
cannam@86: \includegraphics[width=8cm]{floor1-4}
cannam@86: \captionof{figure}{graph of example floor}
cannam@86: \end{center}
cannam@86: 
cannam@86: A more efficient algorithm with carefully defined integer rounding
cannam@86: behavior is used for actual decode, as described later.  The actual
cannam@86: algorithm splits Y value computation and line plotting into two steps
cannam@86: with modifications to the above algorithm to eliminate noise
cannam@86: accumulation through integer roundoff/truncation.
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \subsubsection{header decode}
cannam@86: 
cannam@86: A list of floor X values is stored in the packet header in interleaved
cannam@86: format (used in list order during packet decode and synthesis).  This
cannam@86: list is split into partitions, and each partition is assigned to a
cannam@86: partition class.  X positions 0 and [n] are implicit and do not belong
cannam@86: to an explicit partition or partition class.
cannam@86: 
cannam@86: A partition class consists of a representation vector width (the
cannam@86: number of Y values which the partition class encodes at once), a
cannam@86: 'subclass' value representing the number of alternate entropy books
cannam@86: the partition class may use in representing Y values, the list of
cannam@86: [subclass] books and a master book used to encode which alternate
cannam@86: books were chosen for representation in a given packet.  The
cannam@86: master/subclass mechanism is meant to be used as a flexible
cannam@86: representation cascade while still using codebooks only in a scalar
cannam@86: context.
cannam@86: 
cannam@86: \begin{Verbatim}[commandchars=\\\{\}]
cannam@86: 
cannam@86:   1) [floor1\_partitions] = read 5 bits as unsigned integer
cannam@86:   2) [maximum\_class] = -1
cannam@86:   3) iterate [i] over the range 0 ... [floor1\_partitions]-1 \{
cannam@86: 
cannam@86:         4) vector [floor1\_partition\_class\_list] element [i] = read 4 bits as unsigned integer
cannam@86: 
cannam@86:      \}
cannam@86: 
cannam@86:   5) [maximum\_class] = largest integer scalar value in vector [floor1\_partition\_class\_list]
cannam@86:   6) iterate [i] over the range 0 ... [maximum\_class] \{
cannam@86: 
cannam@86:         7) vector [floor1\_class\_dimensions] element [i] = read 3 bits as unsigned integer and add 1
cannam@86: 	8) vector [floor1\_class\_subclasses] element [i] = read 2 bits as unsigned integer
cannam@86:         9) if ( vector [floor1\_class\_subclasses] element [i] is nonzero ) \{
cannam@86: 
cannam@86:              10) vector [floor1\_class\_masterbooks] element [i] = read 8 bits as unsigned integer
cannam@86: 
cannam@86:            \}
cannam@86: 
cannam@86:        11) iterate [j] over the range 0 ... (2 exponent [floor1\_class\_subclasses] element [i]) - 1 \{
cannam@86: 
cannam@86:              12) array [floor1\_subclass\_books] element [i],[j] =
cannam@86:                  read 8 bits as unsigned integer and subtract one
cannam@86:            \}
cannam@86:       \}
cannam@86: 
cannam@86:  13) [floor1\_multiplier] = read 2 bits as unsigned integer and add one
cannam@86:  14) [rangebits] = read 4 bits as unsigned integer
cannam@86:  15) vector [floor1\_X\_list] element [0] = 0
cannam@86:  16) vector [floor1\_X\_list] element [1] = 2 exponent [rangebits];
cannam@86:  17) [floor1\_values] = 2
cannam@86:  18) iterate [i] over the range 0 ... [floor1\_partitions]-1 \{
cannam@86: 
cannam@86:        19) [current\_class\_number] = vector [floor1\_partition\_class\_list] element [i]
cannam@86:        20) iterate [j] over the range 0 ... ([floor1\_class\_dimensions] element [current\_class\_number])-1 \{
cannam@86:              21) vector [floor1\_X\_list] element ([floor1\_values]) =
cannam@86:                  read [rangebits] bits as unsigned integer
cannam@86:              22) increment [floor1\_values] by one
cannam@86:            \}
cannam@86:      \}
cannam@86: 
cannam@86:  23) done
cannam@86: \end{Verbatim}
cannam@86: 
cannam@86: An end-of-packet condition while reading any aspect of a floor 1
cannam@86: configuration during setup renders a stream undecodable.  In addition,
cannam@86: a \varname{[floor1\_class\_masterbooks]} or
cannam@86: \varname{[floor1\_subclass\_books]} scalar element greater than the
cannam@86: highest numbered codebook configured in this stream is an error
cannam@86: condition that renders the stream undecodable.  Vector
cannam@86: [floor1\_x\_list] is limited to a maximum length of 65 elements; a
cannam@86: setup indicating more than 65 total elements (including elements 0 and
cannam@86: 1 set prior to the read loop) renders the stream undecodable.  All
cannam@86: vector [floor1\_x\_list] element values must be unique within the
cannam@86: vector; a non-unique value renders the stream undecodable.
cannam@86: 
cannam@86: \subsubsection{packet decode} \label{vorbis:spec:floor1-decode}
cannam@86: 
cannam@86: Packet decode begins by checking the \varname{[nonzero]} flag:
cannam@86: 
cannam@86: \begin{Verbatim}[commandchars=\\\{\}]
cannam@86:   1) [nonzero] = read 1 bit as boolean
cannam@86: \end{Verbatim}
cannam@86: 
cannam@86: If \varname{[nonzero]} is unset, that indicates this channel contained
cannam@86: no audio energy in this frame.  Decode immediately returns a status
cannam@86: indicating this floor curve (and thus this channel) is unused this
cannam@86: frame.  (A return status of 'unused' is different from decoding a
cannam@86: floor that has all points set to minimum representation amplitude,
cannam@86: which happens to be approximately -140dB).
cannam@86: 
cannam@86: 
cannam@86: Assuming \varname{[nonzero]} is set, decode proceeds as follows:
cannam@86: 
cannam@86: \begin{Verbatim}[commandchars=\\\{\}]
cannam@86:   1) [range] = vector \{ 256, 128, 86, 64 \} element ([floor1\_multiplier]-1)
cannam@86:   2) vector [floor1\_Y] element [0] = read \link{vorbis:spec:ilog}{ilog}([range]-1) bits as unsigned integer
cannam@86:   3) vector [floor1\_Y] element [1] = read \link{vorbis:spec:ilog}{ilog}([range]-1) bits as unsigned integer
cannam@86:   4) [offset] = 2;
cannam@86:   5) iterate [i] over the range 0 ... [floor1\_partitions]-1 \{
cannam@86: 
cannam@86:        6) [class] = vector [floor1\_partition\_class]  element [i]
cannam@86:        7) [cdim]  = vector [floor1\_class\_dimensions] element [class]
cannam@86:        8) [cbits] = vector [floor1\_class\_subclasses] element [class]
cannam@86:        9) [csub]  = (2 exponent [cbits])-1
cannam@86:       10) [cval]  = 0
cannam@86:       11) if ( [cbits] is greater than zero ) \{
cannam@86: 
cannam@86:              12) [cval] = read from packet using codebook number
cannam@86:                  (vector [floor1\_class\_masterbooks] element [class]) in scalar context
cannam@86:           \}
cannam@86: 
cannam@86:       13) iterate [j] over the range 0 ... [cdim]-1 \{
cannam@86: 
cannam@86:              14) [book] = array [floor1\_subclass\_books] element [class],([cval] bitwise AND [csub])
cannam@86:              15) [cval] = [cval] right shifted [cbits] bits
cannam@86: 	     16) if ( [book] is not less than zero ) \{
cannam@86: 
cannam@86: 	           17) vector [floor1\_Y] element ([j]+[offset]) = read from packet using codebook
cannam@86:                        [book] in scalar context
cannam@86: 
cannam@86:                  \} else [book] is less than zero \{
cannam@86: 
cannam@86: 	           18) vector [floor1\_Y] element ([j]+[offset]) = 0
cannam@86: 
cannam@86:                  \}
cannam@86:           \}
cannam@86: 
cannam@86:       19) [offset] = [offset] + [cdim]
cannam@86: 
cannam@86:      \}
cannam@86: 
cannam@86:  20) done
cannam@86: \end{Verbatim}
cannam@86: 
cannam@86: An end-of-packet condition during curve decode should be considered a
cannam@86: nominal occurrence; if end-of-packet is reached during any read
cannam@86: operation above, floor decode is to return 'unused' status as if the
cannam@86: \varname{[nonzero]} flag had been unset at the beginning of decode.
cannam@86: 
cannam@86: 
cannam@86: Vector \varname{[floor1\_Y]} contains the values from packet decode
cannam@86: needed for floor 1 synthesis.
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \subsubsection{curve computation} \label{vorbis:spec:floor1-synth}
cannam@86: 
cannam@86: Curve computation is split into two logical steps; the first step
cannam@86: derives final Y amplitude values from the encoded, wrapped difference
cannam@86: values taken from the bitstream.  The second step plots the curve
cannam@86: lines.  Also, although zero-difference values are used in the
cannam@86: iterative prediction to find final Y values, these points are
cannam@86: conditionally skipped during final line computation in step two.
cannam@86: Skipping zero-difference values allows a smoother line fit.
cannam@86: 
cannam@86: Although some aspects of the below algorithm look like inconsequential
cannam@86: optimizations, implementors are warned to follow the details closely.
cannam@86: Deviation from implementing a strictly equivalent algorithm can result
cannam@86: in serious decoding errors.
cannam@86: 
cannam@86: {\em Additional note:} Although \varname{[floor1\_final\_Y]} values in
cannam@86: the prediction loop and at the end of step 1 are inherently limited by
cannam@86: the prediction algorithm to [0, \varname{[range]}), it is possible to
cannam@86:   abuse the setup and codebook machinery to produce negative or
cannam@86:   over-range results.  We suggest that decoder implementations guard
cannam@86:   the values in vector \varname{[floor1\_final\_Y]} by clamping each
cannam@86:   element to [0, \varname{[range]}) after step 1.  Variants of this
cannam@86:     suggestion are acceptable as valid floor1 setups cannot produce
cannam@86:     out of range values.
cannam@86: 
cannam@86: \begin{description}
cannam@86: \item[step 1: amplitude value synthesis]
cannam@86: 
cannam@86: Unwrap the always-positive-or-zero values read from the packet into
cannam@86: +/- difference values, then apply to line prediction.
cannam@86: 
cannam@86: \begin{Verbatim}[commandchars=\\\{\}]
cannam@86:   1) [range] = vector \{ 256, 128, 86, 64 \} element ([floor1\_multiplier]-1)
cannam@86:   2) vector [floor1\_step2\_flag] element [0] = set
cannam@86:   3) vector [floor1\_step2\_flag] element [1] = set
cannam@86:   4) vector [floor1\_final\_Y] element [0] = vector [floor1\_Y] element [0]
cannam@86:   5) vector [floor1\_final\_Y] element [1] = vector [floor1\_Y] element [1]
cannam@86:   6) iterate [i] over the range 2 ... [floor1\_values]-1 \{
cannam@86: 
cannam@86:        7) [low\_neighbor\_offset] = \link{vorbis:spec:low:neighbor}{low\_neighbor}([floor1\_X\_list],[i])
cannam@86:        8) [high\_neighbor\_offset] = \link{vorbis:spec:high:neighbor}{high\_neighbor}([floor1\_X\_list],[i])
cannam@86: 
cannam@86:        9) [predicted] = \link{vorbis:spec:render:point}{render\_point}( vector [floor1\_X\_list] element [low\_neighbor\_offset],
cannam@86: 				      vector [floor1\_final\_Y] element [low\_neighbor\_offset],
cannam@86:                                       vector [floor1\_X\_list] element [high\_neighbor\_offset],
cannam@86: 				      vector [floor1\_final\_Y] element [high\_neighbor\_offset],
cannam@86:                                       vector [floor1\_X\_list] element [i] )
cannam@86: 
cannam@86:       10) [val] = vector [floor1\_Y] element [i]
cannam@86:       11) [highroom] = [range] - [predicted]
cannam@86:       12) [lowroom]  = [predicted]
cannam@86:       13) if ( [highroom] is less than [lowroom] ) \{
cannam@86: 
cannam@86:             14) [room] = [highroom] * 2
cannam@86: 
cannam@86:           \} else [highroom] is not less than [lowroom] \{
cannam@86: 
cannam@86:             15) [room] = [lowroom] * 2
cannam@86: 
cannam@86:           \}
cannam@86: 
cannam@86:       16) if ( [val] is nonzero ) \{
cannam@86: 
cannam@86:             17) vector [floor1\_step2\_flag] element [low\_neighbor\_offset] = set
cannam@86:             18) vector [floor1\_step2\_flag] element [high\_neighbor\_offset] = set
cannam@86:             19) vector [floor1\_step2\_flag] element [i] = set
cannam@86:             20) if ( [val] is greater than or equal to [room] ) \{
cannam@86: 
cannam@86:                   21) if ( [highroom] is greater than [lowroom] ) \{
cannam@86: 
cannam@86:                         22) vector [floor1\_final\_Y] element [i] = [val] - [lowroom] + [predicted]
cannam@86: 
cannam@86: 		      \} else [highroom] is not greater than [lowroom] \{
cannam@86: 
cannam@86:                         23) vector [floor1\_final\_Y] element [i] = [predicted] - [val] + [highroom] - 1
cannam@86: 
cannam@86:                       \}
cannam@86: 
cannam@86:                 \} else [val] is less than [room] \{
cannam@86: 
cannam@86:                     24) if ([val] is odd) \{
cannam@86: 
cannam@86:                         25) vector [floor1\_final\_Y] element [i] =
cannam@86:                             [predicted] - (([val] + 1) divided by  2 using integer division)
cannam@86: 
cannam@86:                       \} else [val] is even \{
cannam@86: 
cannam@86:                         26) vector [floor1\_final\_Y] element [i] =
cannam@86:                             [predicted] + ([val] / 2 using integer division)
cannam@86: 
cannam@86:                       \}
cannam@86: 
cannam@86:                 \}
cannam@86: 
cannam@86:           \} else [val] is zero \{
cannam@86: 
cannam@86:             27) vector [floor1\_step2\_flag] element [i] = unset
cannam@86:             28) vector [floor1\_final\_Y] element [i] = [predicted]
cannam@86: 
cannam@86:           \}
cannam@86: 
cannam@86:      \}
cannam@86: 
cannam@86:  29) done
cannam@86: 
cannam@86: \end{Verbatim}
cannam@86: 
cannam@86: 
cannam@86: 
cannam@86: \item[step 2: curve synthesis]
cannam@86: 
cannam@86: Curve synthesis generates a return vector \varname{[floor]} of length
cannam@86: \varname{[n]} (where \varname{[n]} is provided by the decode process
cannam@86: calling to floor decode).  Floor 1 curve synthesis makes use of the
cannam@86: \varname{[floor1\_X\_list]}, \varname{[floor1\_final\_Y]} and
cannam@86: \varname{[floor1\_step2\_flag]} vectors, as well as [floor1\_multiplier]
cannam@86: and [floor1\_values] values.
cannam@86: 
cannam@86: Decode begins by sorting the scalars from vectors
cannam@86: \varname{[floor1\_X\_list]}, \varname{[floor1\_final\_Y]} and
cannam@86: \varname{[floor1\_step2\_flag]} together into new vectors
cannam@86: \varname{[floor1\_X\_list]'}, \varname{[floor1\_final\_Y]'} and
cannam@86: \varname{[floor1\_step2\_flag]'} according to ascending sort order of the
cannam@86: values in \varname{[floor1\_X\_list]}.  That is, sort the values of
cannam@86: \varname{[floor1\_X\_list]} and then apply the same permutation to
cannam@86: elements of the other two vectors so that the X, Y and step2\_flag
cannam@86: values still match.
cannam@86: 
cannam@86: Then compute the final curve in one pass:
cannam@86: 
cannam@86: \begin{Verbatim}[commandchars=\\\{\}]
cannam@86:   1) [hx] = 0
cannam@86:   2) [lx] = 0
cannam@86:   3) [ly] = vector [floor1\_final\_Y]' element [0] * [floor1\_multiplier]
cannam@86:   4) iterate [i] over the range 1 ... [floor1\_values]-1 \{
cannam@86: 
cannam@86:        5) if ( [floor1\_step2\_flag]' element [i] is set ) \{
cannam@86: 
cannam@86:              6) [hy] = [floor1\_final\_Y]' element [i] * [floor1\_multiplier]
cannam@86:  	     7) [hx] = [floor1\_X\_list]' element [i]
cannam@86:              8) \link{vorbis:spec:render:line}{render\_line}( [lx], [ly], [hx], [hy], [floor] )
cannam@86:              9) [lx] = [hx]
cannam@86: 	    10) [ly] = [hy]
cannam@86:           \}
cannam@86:      \}
cannam@86: 
cannam@86:  11) if ( [hx] is less than [n] ) \{
cannam@86: 
cannam@86:         12) \link{vorbis:spec:render:line}{render\_line}( [hx], [hy], [n], [hy], [floor] )
cannam@86: 
cannam@86:      \}
cannam@86: 
cannam@86:  13) if ( [hx] is greater than [n] ) \{
cannam@86: 
cannam@86:             14) truncate vector [floor] to [n] elements
cannam@86: 
cannam@86:      \}
cannam@86: 
cannam@86:  15) for each scalar in vector [floor], perform a lookup substitution using
cannam@86:      the scalar value from [floor] as an offset into the vector \link{vorbis:spec:floor1:inverse:dB:table}{[floor1\_inverse\_dB\_static\_table]}
cannam@86: 
cannam@86:  16) done
cannam@86: 
cannam@86: \end{Verbatim}
cannam@86: 
cannam@86: \end{description}