18e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels% -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*- 28e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels%!TEX root = Vorbis_I_spec.tex 38e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels% $Id$ 48e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\section{Helper equations} \label{vorbis:spec:helper} 58e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 68e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsection{Overview} 78e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 88e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsThe equations below are used in multiple places by the Vorbis codec 98e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsspecification. Rather than cluttering up the main specification 108e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsdocuments, they are defined here and referenced where appropriate. 118e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 128e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 138e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsection{Functions} 148e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 158e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsubsection{ilog} \label{vorbis:spec:ilog} 168e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 178e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsThe "ilog(x)" function returns the position number (1 through n) of the highest set bit in the two's complement integer value 188e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[x]}. Values of \varname{[x]} less than zero are defined to return zero. 198e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 208e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{programlisting} 218e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1) [return_value] = 0; 228e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2) if ( [x] is greater than zero ) { 238e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 248e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3) increment [return_value]; 258e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4) logical shift [x] one bit to the right, padding the MSb with zero 268e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 5) repeat at step 2) 278e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 288e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 298e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 308e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 6) done 318e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{programlisting} 328e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 338e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsExamples: 348e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 358e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{itemize} 368e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \item ilog(0) = 0; 378e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \item ilog(1) = 1; 388e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \item ilog(2) = 2; 398e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \item ilog(3) = 2; 408e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \item ilog(4) = 3; 418e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \item ilog(7) = 3; 428e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels \item ilog(negative number) = 0; 438e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{itemize} 448e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 458e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 468e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 478e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 488e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsubsection{float32_unpack} \label{vorbis:spec:float32:unpack} 498e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 508e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels"float32_unpack(x)" is intended to translate the packed binary 518e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsrepresentation of a Vorbis codebook float value into the 528e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsrepresentation used by the decoder for floating point numbers. For 538e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelspurposes of this example, we will unpack a Vorbis float32 into a 548e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelshost-native floating point number. 558e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 568e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{programlisting} 578e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1) [mantissa] = [x] bitwise AND 0x1fffff (unsigned result) 588e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2) [sign] = [x] bitwise AND 0x80000000 (unsigned result) 598e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3) [exponent] = ( [x] bitwise AND 0x7fe00000) shifted right 21 bits (unsigned result) 608e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4) if ( [sign] is nonzero ) then negate [mantissa] 618e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 5) return [mantissa] * ( 2 ^ ( [exponent] - 788 ) ) 628e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{programlisting} 638e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 648e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 658e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 668e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsubsection{lookup1_values} \label{vorbis:spec:lookup1:values} 678e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 688e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels"lookup1_values(codebook_entries,codebook_dimensions)" is used to 698e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelscompute the correct length of the value index for a codebook VQ lookup 708e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelstable of lookup type 1. The values on this list are permuted to 718e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsconstruct the VQ vector lookup table of size 728e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[codebook_entries]}. 738e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 748e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsThe return value for this function is defined to be 'the greatest 758e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsinteger value for which \varname{[return_value]} to the power of 768e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[codebook_dimensions]} is less than or equal to 778e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[codebook_entries]}'. 788e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 798e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 808e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 818e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsubsection{low_neighbor} \label{vorbis:spec:low:neighbor} 828e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 838e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels"low_neighbor(v,x)" finds the position \varname{n} in vector \varname{[v]} of 848e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthe greatest value scalar element for which \varname{n} is less than 858e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[x]} and vector \varname{[v]} element \varname{n} is less 868e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthan vector \varname{[v]} element \varname{[x]}. 878e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 888e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsubsection{high_neighbor} \label{vorbis:spec:high:neighbor} 898e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 908e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels"high_neighbor(v,x)" finds the position \varname{n} in vector [v] of 918e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthe lowest value scalar element for which \varname{n} is less than 928e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\varname{[x]} and vector \varname{[v]} element \varname{n} is greater 938e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsthan vector \varname{[v]} element \varname{[x]}. 948e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 958e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 968e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 978e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsubsection{render_point} \label{vorbis:spec:render:point} 988e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 998e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels"render_point(x0,y0,x1,y1,X)" is used to find the Y value at point X 1008e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsalong the line specified by x0, x1, y0 and y1. This function uses an 1018e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsinteger algorithm to solve for the point directly without calculating 1028e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsintervening values along the line. 1038e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1048e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{programlisting} 1058e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1) [dy] = [y1] - [y0] 1068e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2) [adx] = [x1] - [x0] 1078e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3) [ady] = absolute value of [dy] 1088e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4) [err] = [ady] * ([X] - [x0]) 1098e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 5) [off] = [err] / [adx] using integer division 1108e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 6) if ( [dy] is less than zero ) { 1118e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1128e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 7) [Y] = [y0] - [off] 1138e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1148e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } else { 1158e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1168e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 8) [Y] = [y0] + [off] 1178e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1188e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1198e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1208e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 9) done 1218e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{programlisting} 1228e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1238e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1248e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1258e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\subsubsection{render_line} \label{vorbis:spec:render:line} 1268e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1278e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas EckelsFloor decode type one uses the integer line drawing algorithm of 1288e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels"render_line(x0, y0, x1, y1, v)" to construct an integer floor 1298e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelscurve for contiguous piecewise line segments. Note that it has not 1308e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsbeen relevant elsewhere, but here we must define integer division as 1318e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckelsrounding division of both positive and negative numbers toward zero. 1328e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1338e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1348e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\begin{programlisting} 1358e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1) [dy] = [y1] - [y0] 1368e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 2) [adx] = [x1] - [x0] 1378e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 3) [ady] = absolute value of [dy] 1388e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 4) [base] = [dy] / [adx] using integer division 1398e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 5) [x] = [x0] 1408e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 6) [y] = [y0] 1418e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 7) [err] = 0 1428e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1438e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 8) if ( [dy] is less than 0 ) { 1448e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1458e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 9) [sy] = [base] - 1 1468e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1478e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } else { 1488e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1498e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 10) [sy] = [base] + 1 1508e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1518e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1528e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1538e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 11) [ady] = [ady] - (absolute value of [base]) * [adx] 1548e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 12) vector [v] element [x] = [y] 1558e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1568e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 13) iterate [x] over the range [x0]+1 ... [x1]-1 { 1578e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1588e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 14) [err] = [err] + [ady]; 1598e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 15) if ( [err] >= [adx] ) { 1608e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1618e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 16) [err] = [err] - [adx] 1628e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 17) [y] = [y] + [sy] 1638e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1648e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } else { 1658e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1668e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 18) [y] = [y] + [base] 1678e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1688e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1698e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1708e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 19) vector [v] element [x] = [y] 1718e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1728e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels } 1738e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels\end{programlisting} 1748e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1758e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1768e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1778e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1788e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1798e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1808e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 1818e01cdce135d5d816f92d7bb83f9a930aa1b45aeLucas Eckels 182