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 8Vorbis floor type one uses a piecewise straight-line representation to 9encode a spectral envelope curve. The representation plots this curve 10mechanically on a linear frequency axis and a logarithmic (dB) 11amplitude axis. The integer plotting algorithm used is similar to 12Bresenham's algorithm. 13 14 15 16\subsection{Floor 1 format} 17 18\subsubsection{model} 19 20Floor type one represents a spectral curve as a series of 21line segments. Synthesis constructs a floor curve using iterative 22prediction in a process roughly equivalent to the following simplified 23description: 24 25\begin{itemize} 26 \item the first line segment (base case) is a logical line spanning 27from x_0,y_0 to x_1,y_1 where in the base case x_0=0 and x_1=[n], the 28full range of the spectral floor to be computed. 29 30\item the induction step chooses a point x_new within an existing 31logical line segment and produces a y_new value at that point computed 32from the existing line's y value at x_new (as plotted by the line) and 33a difference value decoded from the bitstream packet. 34 35\item floor computation produces two new line segments, one running from 36x_0,y_0 to x_new,y_new and from x_new,y_new to x_1,y_1. This step is 37performed logically even if y_new represents no change to the 38amplitude value at x_new so that later refinement is additionally 39bounded at x_new. 40 41\item the induction step repeats, using a list of x values specified in 42the codec setup header at floor 1 initialization time. Computation 43is completed at the end of the x value list. 44 45\end{itemize} 46 47 48Consider the following example, with values chosen for ease of 49understanding rather than representing typical configuration: 50 51For the below example, we assume a floor setup with an [n] of 128. 52The list of selected X values in increasing order is 530,16,32,48,64,80,96,112 and 128. In list order, the values interleave 54as 0, 128, 64, 32, 96, 16, 48, 80 and 112. The corresponding 55list-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 57way, 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 64We now draw new logical lines to reflect the correction to new_Y, and 65iterate 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 72Although the new Y value at X position 96 is unchanged, it is still 73used later as an endpoint for further refinement. From here on, the 74pattern 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 86A more efficient algorithm with carefully defined integer rounding 87behavior is used for actual decode, as described later. The actual 88algorithm splits Y value computation and line plotting into two steps 89with modifications to the above algorithm to eliminate noise 90accumulation through integer roundoff/truncation. 91 92 93 94\subsubsection{header decode} 95 96A list of floor X values is stored in the packet header in interleaved 97format (used in list order during packet decode and synthesis). This 98list is split into partitions, and each partition is assigned to a 99partition class. X positions 0 and [n] are implicit and do not belong 100to an explicit partition or partition class. 101 102A partition class consists of a representation vector width (the 103number of Y values which the partition class encodes at once), a 104'subclass' value representing the number of alternate entropy books 105the partition class may use in representing Y values, the list of 106[subclass] books and a master book used to encode which alternate 107books were chosen for representation in a given packet. The 108master/subclass mechanism is meant to be used as a flexible 109representation cascade while still using codebooks only in a scalar 110context. 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 158An end-of-packet condition while reading any aspect of a floor 1 159configuration during setup renders a stream undecodable. In addition, 160a \varname{[floor1_class_masterbooks]} or 161\varname{[floor1_subclass_books]} scalar element greater than the 162highest numbered codebook configured in this stream is an error 163condition that renders the stream undecodable. All vector 164[floor1_x_list] element values must be unique within the vector; a 165non-unique value renders the stream undecodable. 166 167\paragraph{packet decode} \label{vorbis:spec:floor1-decode} 168 169Packet 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 175If \varname{[nonzero]} is unset, that indicates this channel contained 176no audio energy in this frame. Decode immediately returns a status 177indicating this floor curve (and thus this channel) is unused this 178frame. (A return status of 'unused' is different from decoding a 179floor that has all points set to minimum representation amplitude, 180which happens to be approximately -140dB). 181 182 183Assuming \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 226An end-of-packet condition during curve decode should be considered a 227nominal occurrence; if end-of-packet is reached during any read 228operation 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 232Vector \varname{[floor1_Y]} contains the values from packet decode 233needed for floor 1 synthesis. 234 235 236 237\paragraph{curve computation} \label{vorbis:spec:floor1-synth} 238 239Curve computation is split into two logical steps; the first step 240derives final Y amplitude values from the encoded, wrapped difference 241values taken from the bitstream. The second step plots the curve 242lines. Also, although zero-difference values are used in the 243iterative prediction to find final Y values, these points are 244conditionally skipped during final line computation in step two. 245Skipping zero-difference values allows a smoother line fit. 246 247Although some aspects of the below algorithm look like inconsequential 248optimizations, implementors are warned to follow the details closely. 249Deviation from implementing a strictly equivalent algorithm can result 250in serious decoding errors. 251 252\begin{description} 253\item[step 1: amplitude value synthesis] 254 255Unwrap 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 338Curve synthesis generates a return vector \varname{[floor]} of length 339\varname{[n]} (where \varname{[n]} is provided by the decode process 340calling 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] 343and [floor1_values] values. 344 345Decode 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 350values in \varname{[floor1_X_list]}. That is, sort the values of 351\varname{[floor1_X_list]} and then apply the same permutation to 352elements of the other two vectors so that the X, Y and step2_flag 353values still match. 354 355Then 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