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
 160 addition, 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.
 164
 165 \paragraph{packet decode} \label{vorbis:spec:floor1-decode}
 166
 167 Packet decode begins by checking the \varname{[nonzero]} flag:
 168
 169 \begin{Verbatim}[commandchars=\\\{\}]
 170   1) [nonzero] = read 1 bit as boolean
 171 \end{Verbatim}
 172
 173 If \varname{[nonzero]} is unset, that indicates this channel contained
 174 no audio energy in this frame.  Decode immediately returns a status
 175 indicating this floor curve (and thus this channel) is unused this
 176 frame.  (A return status of 'unused' is different from decoding a
 177 floor that has all points set to minimum representation amplitude,
 178 which happens to be approximately -140dB).
 179
 180
 181 Assuming \varname{[nonzero]} is set, decode proceeds as follows:
 182
 183 \begin{Verbatim}[commandchars=\\\{\}]
 184   1) [range] = vector \{ 256, 128, 86, 64 \} element ([floor1_multiplier]-1)
 185   2) vector [floor1_Y] element [0] = read \link{vorbis:spec:ilog}{ilog}([range]-1) bits as unsigned integer
 186   3) vector [floor1_Y] element [1] = read \link{vorbis:spec:ilog}{ilog}([range]-1) bits as unsigned integer
 187   4) [offset] = 2;
 188   5) iterate [i] over the range 0 ... [floor1_partitions]-1 \{
 189
 190        6) [class] = vector [floor1_partition_class]  element [i]
 191        7) [cdim]  = vector [floor1_class_dimensions] element [class]
 192        8) [cbits] = vector [floor1_class_subclasses] element [class]
 193        9) [csub]  = (2 exponent [cbits])-1
 194       10) [cval]  = 0
 195       11) if ( [cbits] is greater than zero ) \{
 196
 197              12) [cval] = read from packet using codebook number
 198                  (vector [floor1_class_masterbooks] element [class]) in scalar context
 199           \}
 200
 201       13) iterate [j] over the range 0 ... [cdim]-1 \{
 202
 203              14) [book] = array [floor1_subclass_books] element [class],([cval] bitwise AND [csub])
 204              15) [cval] = [cval] right shifted [cbits] bits
 205              16) if ( [book] is not less than zero ) \{
 206
 207                    17) vector [floor1_Y] element ([j]+[offset]) = read from packet using codebook
 208                        [book] in scalar context
 209
 210                  \} else [book] is less than zero \{
 211
 212                    18) vector [floor1_Y] element ([j]+[offset]) = 0
 213
 214                  \}
 215           \}
 216
 217       19) [offset] = [offset] + [cdim]
 218
 219      \}
 220
 221  20) done
 222 \end{Verbatim}
 223
 224 An end-of-packet condition during curve decode should be considered a
 225 nominal occurrence; if end-of-packet is reached during any read
 226 operation above, floor decode is to return 'unused' status as if the
 227 \varname{[nonzero]} flag had been unset at the beginning of decode.
 228
 229
 230 Vector \varname{[floor1_Y]} contains the values from packet decode
 231 needed for floor 1 synthesis.
 232
 233
 234
 235 \paragraph{curve computation} \label{vorbis:spec:floor1-synth}
 236
 237 Curve computation is split into two logical steps; the first step
 238 derives final Y amplitude values from the encoded, wrapped difference
 239 values taken from the bitstream.  The second step plots the curve
 240 lines.  Also, although zero-difference values are used in the
 241 iterative prediction to find final Y values, these points are
 242 conditionally skipped during final line computation in step two.
 243 Skipping zero-difference values allows a smoother line fit.
 244
 245 Although some aspects of the below algorithm look like inconsequential
 246 optimizations, implementors are warned to follow the details closely.
 247 Deviation from implementing a strictly equivalent algorithm can result
 248 in serious decoding errors.
 249
 250 \begin{description}
 251 \item[step 1: amplitude value synthesis]
 252
 253 Unwrap the always-positive-or-zero values read from the packet into
 254 +/- difference values, then apply to line prediction.
 255
 256 \begin{Verbatim}[commandchars=\\\{\}]
 257   1) [range] = vector \{ 256, 128, 86, 64 \} element ([floor1_multiplier]-1)
 258   2) vector [floor1_step2_flag] element [0] = set
 259   3) vector [floor1_step2_flag] element [1] = set
 260   4) vector [floor1_final_Y] element [0] = vector [floor1_Y] element [0]
 261   5) vector [floor1_final_Y] element [1] = vector [floor1_Y] element [1]
 262   6) iterate [i] over the range 2 ... [floor1_values]-1 \{
 263
 264        7) [low_neighbor_offset] = \link{vorbis:spec:low:neighbor}{low_neighbor}([floor1_X_list],[i])
 265        8) [high_neighbor_offset] = \link{vorbis:spec:high:neighbor}{high_neighbor}([floor1_X_list],[i])
 266
 267        9) [predicted] = \link{vorbis:spec:render:point}{render_point}( vector [floor1_X_list] element [low_neighbor_offset],
 268                                       vector [floor1_final_Y] element [low_neighbor_offset],
 269                                       vector [floor1_X_list] element [high_neighbor_offset],
 270                                       vector [floor1_final_Y] element [high_neighbor_offset],
 271                                       vector [floor1_X_list] element [i] )
 272
 273       10) [val] = vector [floor1_Y] element [i]
 274       11) [highroom] = [range] - [predicted]
 275       12) [lowroom]  = [predicted]
 276       13) if ( [highroom] is less than [lowroom] ) \{
 277
 278             14) [room] = [highroom] * 2
 279
 280           \} else [highroom] is not less than [lowroom] \{
 281
 282             15) [room] = [lowroom] * 2
 283
 284           \}
 285
 286       16) if ( [val] is nonzero ) \{
 287
 288             17) vector [floor1_step2_flag] element [low_neighbor_offset] = set
 289             18) vector [floor1_step2_flag] element [high_neighbor_offset] = set
 290             19) vector [floor1_step2_flag] element [i] = set
 291             20) if ( [val] is greater than or equal to [room] ) \{
 292
 293                   21) if ( [highroom] is greater than [lowroom] ) \{
 294
 295                         22) vector [floor1_final_Y] element [i] = [val] - [lowroom] + [predicted]
 296
 297                       \} else [highroom] is not greater than [lowroom] \{
 298
 299                         23) vector [floor1_final_Y] element [i] = [predicted] - [val] + [highroom] - 1
 300
 301                       \}
 302
 303                 \} else [val] is less than [room] \{
 304
 305                   24) if ([val] is odd) \{
 306
 307                         25) vector [floor1_final_Y] element [i] =
 308                             [predicted] - (([val] + 1) divided by  2 using integer division)
 309
 310                       \} else [val] is even \{
 311
 312                         26) vector [floor1_final_Y] element [i] =
 313                             [predicted] + ([val] / 2 using integer division)
 314
 315                       \}
 316
 317                 \}
 318
 319           \} else [val] is zero \{
 320
 321             27) vector [floor1_step2_flag] element [i] = unset
 322             28) vector [floor1_final_Y] element [i] = [predicted]
 323
 324           \}
 325
 326      \}
 327
 328  29) done
 329
 330 \end{Verbatim}
 331
 332
 333
 334 \item[step 2: curve synthesis]
 335
 336 Curve synthesis generates a return vector \varname{[floor]} of length
 337 \varname{[n]} (where \varname{[n]} is provided by the decode process
 338 calling to floor decode).  Floor 1 curve synthesis makes use of the
 339 \varname{[floor1_X_list]}, \varname{[floor1_final_Y]} and
 340 \varname{[floor1_step2_flag]} vectors, as well as [floor1_multiplier]
 341 and [floor1_values] values.
 342
 343 Decode begins by sorting the scalars from vectors
 344 \varname{[floor1_X_list]}, \varname{[floor1_final_Y]} and
 345 \varname{[floor1_step2_flag]} together into new vectors
 346 \varname{[floor1_X_list]'}, \varname{[floor1_final_Y]'} and
 347 \varname{[floor1_step2_flag]'} according to ascending sort order of the
 348 values in \varname{[floor1_X_list]}.  That is, sort the values of
 349 \varname{[floor1_X_list]} and then apply the same permutation to
 350 elements of the other two vectors so that the X, Y and step2_flag
 351 values still match.
 352
 353 Then compute the final curve in one pass:
 354
 355 \begin{Verbatim}[commandchars=\\\{\}]
 356   1) [hx] = 0
 357   2) [lx] = 0
 358   3) [ly] = vector [floor1_final_Y]' element [0] * [floor1_multiplier]
 359   4) iterate [i] over the range 1 ... [floor1_values]-1 \{
 360
 361        5) if ( [floor1_step2_flag]' element [i] is set ) \{
 362
 363              6) [hy] = [floor1_final_Y]' element [i] * [floor1_multiplier]
 364              7) [hx] = [floor1_X_list]' element [i]
 365              8) \link{vorbis:spec:render:line}{render_line}( [lx], [ly], [hx], [hy], [floor] )
 366              9) [lx] = [hx]
 367             10) [ly] = [hy]
 368           \}
 369      \}
 370
 371  11) if ( [hx] is less than [n] ) \{
 372
 373         12) \link{vorbis:spec:render:line}{render_line}( [hx], [hy], [n], [hy], [floor] )
 374
 375      \}
 376
 377  13) if ( [hx] is greater than [n] ) \{
 378
 379             14) truncate vector [floor] to [n] elements
 380
 381      \}
 382
 383  15) for each scalar in vector [floor], perform a lookup substitution using
 384      the scalar value from [floor] as an offset into the vector \link{vorbis:spec:floor1:inverse:dB:table}{[floor1_inverse_dB_static_table]}
 385
 386  16) done
 387
 388 \end{Verbatim}
 389
 390 \end{description}