release/src/router/libvorbis/doc/07-floor1.tex

   1 % -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*-
   2 %!TEX root = Vorbis_I_spec.tex
   3 % $Id$
   4 \section{Floor type 1 setup and decode} \label{vorbis:spec:floor1}
   5
   6 \subsection{Overview}
   7
   8 Vorbis floor type one uses a piecewise straight-line representation to
   9 encode a spectral envelope curve. The representation plots this curve
  10 mechanically on a linear frequency axis and a logarithmic (dB)
  11 amplitude axis. The integer plotting algorithm used is similar to
  12 Bresenham's algorithm.
  13
  14
  15
  16 \subsection{Floor 1 format}
  17
  18 \subsubsection{model}
  19
  20 Floor type one represents a spectral curve as a series of
  21 line segments.  Synthesis constructs a floor curve using iterative
  22 prediction in a process roughly equivalent to the following simplified
  23 description:
  24
  25 \begin{itemize}
  26  \item  the first line segment (base case) is a logical line spanning
  27 from x_0,y_0 to x_1,y_1 where in the base case x_0=0 and x_1=[n], the
  28 full range of the spectral floor to be computed.
  29
  30 \item the induction step chooses a point x_new within an existing
  31 logical line segment and produces a y_new value at that point computed
  32 from the existing line's y value at x_new (as plotted by the line) and
  33 a difference value decoded from the bitstream packet.
  34
  35 \item floor computation produces two new line segments, one running from
  36 x_0,y_0 to x_new,y_new and from x_new,y_new to x_1,y_1. This step is
  37 performed logically even if y_new represents no change to the
  38 amplitude value at x_new so that later refinement is additionally
  39 bounded at x_new.
  40
  41 \item the induction step repeats, using a list of x values specified in
  42 the codec setup header at floor 1 initialization time.  Computation
  43 is completed at the end of the x value list.
  44
  45 \end{itemize}
  46
  47
  48 Consider the following example, with values chosen for ease of
  49 understanding rather than representing typical configuration:
  50
  51 For the below example, we assume a floor setup with an [n] of 128.
  52 The list of selected X values in increasing order is
  53 0,16,32,48,64,80,96,112 and 128.  In list order, the values interleave
  54 as 0, 128, 64, 32, 96, 16, 48, 80 and 112.  The corresponding
  55 list-order Y values as decoded from an example packet are 110, 20, -5,
  56 -45, 0, -25, -10, 30 and -10.  We compute the floor in the following
  57 way, beginning with the first line:
  58
  59 \begin{center}
  60 \includegraphics[width=8cm]{floor1-1}
  61 \captionof{figure}{graph of example floor}
  62 \end{center}
  63
  64 We now draw new logical lines to reflect the correction to new_Y, and
  65 iterate for X positions 32 and 96:
  66
  67 \begin{center}
  68 \includegraphics[width=8cm]{floor1-2}
  69 \captionof{figure}{graph of example floor}
  70 \end{center}
  71
  72 Although the new Y value at X position 96 is unchanged, it is still
  73 used later as an endpoint for further refinement.  From here on, the
  74 pattern should be clear; we complete the floor computation as follows:
  75
  76 \begin{center}
  77 \includegraphics[width=8cm]{floor1-3}
  78 \captionof{figure}{graph of example floor}
  79 \end{center}
  80
  81 \begin{center}
  82 \includegraphics[width=8cm]{floor1-4}
  83 \captionof{figure}{graph of example floor}
  84 \end{center}
  85
  86 A more efficient algorithm with carefully defined integer rounding
  87 behavior is used for actual decode, as described later.  The actual
  88 algorithm splits Y value computation and line plotting into two steps
  89 with modifications to the above algorithm to eliminate noise
  90 accumulation through integer roundoff/truncation.
  91
  92
  93
  94 \subsubsection{header decode}
  95
  96 A list of floor X values is stored in the packet header in interleaved
  97 format (used in list order during packet decode and synthesis).  This
  98 list is split into partitions, and each partition is assigned to a
  99 partition class.  X positions 0 and [n] are implicit and do not belong
 100 to an explicit partition or partition class.
 101
 102 A partition class consists of a representation vector width (the
 103 number of Y values which the partition class encodes at once), a
 104 'subclass' value representing the number of alternate entropy books
 105 the partition class may use in representing Y values, the list of
 106 [subclass] books and a master book used to encode which alternate
 107 books were chosen for representation in a given packet.  The
 108 master/subclass mechanism is meant to be used as a flexible
 109 representation cascade while still using codebooks only in a scalar
 110 context.
 111
 112 \begin{Verbatim}[commandchars=\\\{\}]
 113
 114   1) [floor1_partitions] = read 5 bits as unsigned integer
 115   2) [maximum_class] = -1
 116   3) iterate [i] over the range 0 ... [floor1_partitions]-1 \{
 117
 118         4) vector [floor1_partition_class_list] element [i] = read 4 bits as unsigned integer
 119
 120      \}
 121
 122   5) [maximum_class] = largest integer scalar value in vector [floor1_partition_class_list]
 123   6) iterate [i] over the range 0 ... [maximum_class] \{
 124
 125         7) vector [floor1_class_dimensions] element [i] = read 3 bits as unsigned integer and add 1
 126         8) vector [floor1_class_subclasses] element [i] = read 2 bits as unsigned integer
 127         9) if ( vector [floor1_class_subclasses] element [i] is nonzero ) \{
 128
 129              10) vector [floor1_class_masterbooks] element [i] = read 8 bits as unsigned integer
 130
 131            \}
 132
 133        11) iterate [j] over the range 0 ... (2 exponent [floor1_class_subclasses] element [i]) - 1 \{
 134
 135              12) array [floor1_subclass_books] element [i],[j] =
 136                  read 8 bits as unsigned integer and subtract one
 137            \}
 138       \}
 139
 140  13) [floor1_multiplier] = read 2 bits as unsigned integer and add one
 141  14) [rangebits] = read 4 bits as unsigned integer
 142  15) vector [floor1_X_list] element [0] = 0
 143  16) vector [floor1_X_list] element [1] = 2 exponent [rangebits];
 144  17) [floor1_values] = 2
 145  18) iterate [i] over the range 0 ... [floor1_partitions]-1 \{
 146
 147        19) [current_class_number] = vector [floor1_partition_class_list] element [i]
 148        20) iterate [j] over the range 0 ... ([floor1_class_dimensions] element [current_class_number])-1 \{
 149              21) vector [floor1_X_list] element ([floor1_values]) =
 150                  read [rangebits] bits as unsigned integer
 151              22) increment [floor1_values] by one
 152            \}
 153      \}
 154
 155  23) done
 156 \end{Verbatim}
 157
 158 An end-of-packet condition while reading any aspect of a floor 1
 159 configuration during setup renders a stream undecodable.  In addition,
 160 a \varname{[floor1_class_masterbooks]} or
 161 \varname{[floor1_subclass_books]} scalar element greater than the
 162 highest numbered codebook configured in this stream is an error
 163 condition that renders the stream undecodable.  All vector
 164 [floor1_x_list] element values must be unique within the vector; a
 165 non-unique value renders the stream undecodable.
 166
 167 \paragraph{packet decode} \label{vorbis:spec:floor1-decode}
 168
 169 Packet decode begins by checking the \varname{[nonzero]} flag:
 170
 171 \begin{Verbatim}[commandchars=\\\{\}]
 172   1) [nonzero] = read 1 bit as boolean
 173 \end{Verbatim}
 174
 175 If \varname{[nonzero]} is unset, that indicates this channel contained
 176 no audio energy in this frame.  Decode immediately returns a status
 177 indicating this floor curve (and thus this channel) is unused this
 178 frame.  (A return status of 'unused' is different from decoding a
 179 floor that has all points set to minimum representation amplitude,
 180 which happens to be approximately -140dB).
 181
 182
 183 Assuming \varname{[nonzero]} is set, decode proceeds as follows:
 184
 185 \begin{Verbatim}[commandchars=\\\{\}]
 186   1) [range] = vector \{ 256, 128, 86, 64 \} element ([floor1_multiplier]-1)
 187   2) vector [floor1_Y] element [0] = read \link{vorbis:spec:ilog}{ilog}([range]-1) bits as unsigned integer
 188   3) vector [floor1_Y] element [1] = read \link{vorbis:spec:ilog}{ilog}([range]-1) bits as unsigned integer
 189   4) [offset] = 2;
 190   5) iterate [i] over the range 0 ... [floor1_partitions]-1 \{
 191
 192        6) [class] = vector [floor1_partition_class]  element [i]
 193        7) [cdim]  = vector [floor1_class_dimensions] element [class]
 194        8) [cbits] = vector [floor1_class_subclasses] element [class]
 195        9) [csub]  = (2 exponent [cbits])-1
 196       10) [cval]  = 0
 197       11) if ( [cbits] is greater than zero ) \{
 198
 199              12) [cval] = read from packet using codebook number
 200                  (vector [floor1_class_masterbooks] element [class]) in scalar context
 201           \}
 202
 203       13) iterate [j] over the range 0 ... [cdim]-1 \{
 204
 205              14) [book] = array [floor1_subclass_books] element [class],([cval] bitwise AND [csub])
 206              15) [cval] = [cval] right shifted [cbits] bits
 207              16) if ( [book] is not less than zero ) \{
 208
 209                    17) vector [floor1_Y] element ([j]+[offset]) = read from packet using codebook
 210                        [book] in scalar context
 211
 212                  \} else [book] is less than zero \{
 213
 214                    18) vector [floor1_Y] element ([j]+[offset]) = 0
 215
 216                  \}
 217           \}
 218
 219       19) [offset] = [offset] + [cdim]
 220
 221      \}
 222
 223  20) done
 224 \end{Verbatim}
 225
 226 An end-of-packet condition during curve decode should be considered a
 227 nominal occurrence; if end-of-packet is reached during any read
 228 operation above, floor decode is to return 'unused' status as if the
 229 \varname{[nonzero]} flag had been unset at the beginning of decode.
 230
 231
 232 Vector \varname{[floor1_Y]} contains the values from packet decode
 233 needed for floor 1 synthesis.
 234
 235
 236
 237 \paragraph{curve computation} \label{vorbis:spec:floor1-synth}
 238
 239 Curve computation is split into two logical steps; the first step
 240 derives final Y amplitude values from the encoded, wrapped difference
 241 values taken from the bitstream.  The second step plots the curve
 242 lines.  Also, although zero-difference values are used in the
 243 iterative prediction to find final Y values, these points are
 244 conditionally skipped during final line computation in step two.
 245 Skipping zero-difference values allows a smoother line fit.
 246
 247 Although some aspects of the below algorithm look like inconsequential
 248 optimizations, implementors are warned to follow the details closely.
 249 Deviation from implementing a strictly equivalent algorithm can result
 250 in serious decoding errors.
 251
 252 \begin{description}
 253 \item[step 1: amplitude value synthesis]
 254
 255 Unwrap the always-positive-or-zero values read from the packet into
 256 +/- difference values, then apply to line prediction.
 257
 258 \begin{Verbatim}[commandchars=\\\{\}]
 259   1) [range] = vector \{ 256, 128, 86, 64 \} element ([floor1_multiplier]-1)
 260   2) vector [floor1_step2_flag] element [0] = set
 261   3) vector [floor1_step2_flag] element [1] = set
 262   4) vector [floor1_final_Y] element [0] = vector [floor1_Y] element [0]
 263   5) vector [floor1_final_Y] element [1] = vector [floor1_Y] element [1]
 264   6) iterate [i] over the range 2 ... [floor1_values]-1 \{
 265
 266        7) [low_neighbor_offset] = \link{vorbis:spec:low:neighbor}{low_neighbor}([floor1_X_list],[i])
 267        8) [high_neighbor_offset] = \link{vorbis:spec:high:neighbor}{high_neighbor}([floor1_X_list],[i])
 268
 269        9) [predicted] = \link{vorbis:spec:render:point}{render_point}( vector [floor1_X_list] element [low_neighbor_offset],
 270                                       vector [floor1_final_Y] element [low_neighbor_offset],
 271                                       vector [floor1_X_list] element [high_neighbor_offset],
 272                                       vector [floor1_final_Y] element [high_neighbor_offset],
 273                                       vector [floor1_X_list] element [i] )
 274
 275       10) [val] = vector [floor1_Y] element [i]
 276       11) [highroom] = [range] - [predicted]
 277       12) [lowroom]  = [predicted]
 278       13) if ( [highroom] is less than [lowroom] ) \{
 279
 280             14) [room] = [highroom] * 2
 281
 282           \} else [highroom] is not less than [lowroom] \{
 283
 284             15) [room] = [lowroom] * 2
 285
 286           \}
 287
 288       16) if ( [val] is nonzero ) \{
 289
 290             17) vector [floor1_step2_flag] element [low_neighbor_offset] = set
 291             18) vector [floor1_step2_flag] element [high_neighbor_offset] = set
 292             19) vector [floor1_step2_flag] element [i] = set
 293             20) if ( [val] is greater than or equal to [room] ) \{
 294
 295                   21) if ( [highroom] is greater than [lowroom] ) \{
 296
 297                         22) vector [floor1_final_Y] element [i] = [val] - [lowroom] + [predicted]
 298
 299                       \} else [highroom] is not greater than [lowroom] \{
 300
 301                         23) vector [floor1_final_Y] element [i] = [predicted] - [val] + [highroom] - 1
 302
 303                       \}
 304
 305                 \} else [val] is less than [room] \{
 306
 307                   24) if ([val] is odd) \{
 308
 309                         25) vector [floor1_final_Y] element [i] =
 310                             [predicted] - (([val] + 1) divided by  2 using integer division)
 311
 312                       \} else [val] is even \{
 313
 314                         26) vector [floor1_final_Y] element [i] =
 315                             [predicted] + ([val] / 2 using integer division)
 316
 317                       \}
 318
 319                 \}
 320
 321           \} else [val] is zero \{
 322
 323             27) vector [floor1_step2_flag] element [i] = unset
 324             28) vector [floor1_final_Y] element [i] = [predicted]
 325
 326           \}
 327
 328      \}
 329
 330  29) done
 331
 332 \end{Verbatim}
 333
 334
 335
 336 \item[step 2: curve synthesis]
 337
 338 Curve synthesis generates a return vector \varname{[floor]} of length
 339 \varname{[n]} (where \varname{[n]} is provided by the decode process
 340 calling to floor decode).  Floor 1 curve synthesis makes use of the
 341 \varname{[floor1_X_list]}, \varname{[floor1_final_Y]} and
 342 \varname{[floor1_step2_flag]} vectors, as well as [floor1_multiplier]
 343 and [floor1_values] values.
 344
 345 Decode begins by sorting the scalars from vectors
 346 \varname{[floor1_X_list]}, \varname{[floor1_final_Y]} and
 347 \varname{[floor1_step2_flag]} together into new vectors
 348 \varname{[floor1_X_list]'}, \varname{[floor1_final_Y]'} and
 349 \varname{[floor1_step2_flag]'} according to ascending sort order of the
 350 values in \varname{[floor1_X_list]}.  That is, sort the values of
 351 \varname{[floor1_X_list]} and then apply the same permutation to
 352 elements of the other two vectors so that the X, Y and step2_flag
 353 values still match.
 354
 355 Then compute the final curve in one pass:
 356
 357 \begin{Verbatim}[commandchars=\\\{\}]
 358   1) [hx] = 0
 359   2) [lx] = 0
 360   3) [ly] = vector [floor1_final_Y]' element [0] * [floor1_multiplier]
 361   4) iterate [i] over the range 1 ... [floor1_values]-1 \{
 362
 363        5) if ( [floor1_step2_flag]' element [i] is set ) \{
 364
 365              6) [hy] = [floor1_final_Y]' element [i] * [floor1_multiplier]
 366              7) [hx] = [floor1_X_list]' element [i]
 367              8) \link{vorbis:spec:render:line}{render_line}( [lx], [ly], [hx], [hy], [floor] )
 368              9) [lx] = [hx]
 369             10) [ly] = [hy]
 370           \}
 371      \}
 372
 373  11) if ( [hx] is less than [n] ) \{
 374
 375         12) \link{vorbis:spec:render:line}{render_line}( [hx], [hy], [n], [hy], [floor] )
 376
 377      \}
 378
 379  13) if ( [hx] is greater than [n] ) \{
 380
 381             14) truncate vector [floor] to [n] elements
 382
 383      \}
 384
 385  15) for each scalar in vector [floor], perform a lookup substitution using
 386      the scalar value from [floor] as an offset into the vector \link{vorbis:spec:floor1:inverse:dB:table}{[floor1_inverse_dB_static_table]}
 387
 388  16) done
 389
 390 \end{Verbatim}
 391
 392 \end{description}