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} 393
