doc/09-helper.tex

   1 % -*- mode: latex; TeX-master: "Vorbis_I_spec"; -*-
   2 %!TEX root = Vorbis_I_spec.tex
   3 \section{Helper equations} \label{vorbis:spec:helper}
   4
   5 \subsection{Overview}
   6
   7 The equations below are used in multiple places by the Vorbis codec
   8 specification.  Rather than cluttering up the main specification
   9 documents, they are defined here and referenced where appropriate.
  10
  11
  12 \subsection{Functions}
  13
  14 \subsubsection{ilog} \label{vorbis:spec:ilog}
  15
  16 The "ilog(x)" function returns the position number (1 through n) of the highest set bit in the two's complement integer value
  17 \varname{[x]}.  Values of \varname{[x]} less than zero are defined to return zero.
  18
  19 \begin{programlisting}
  20   1) [return\_value] = 0;
  21   2) if ( [x] is greater than zero ) {
  22
  23        3) increment [return\_value];
  24        4) logical shift [x] one bit to the right, padding the MSb with zero
  25        5) repeat at step 2)
  26
  27      }
  28
  29    6) done
  30 \end{programlisting}
  31
  32 Examples:
  33
  34 \begin{itemize}
  35  \item ilog(0) = 0;
  36  \item ilog(1) = 1;
  37  \item ilog(2) = 2;
  38  \item ilog(3) = 2;
  39  \item ilog(4) = 3;
  40  \item ilog(7) = 3;
  41  \item ilog(negative number) = 0;
  42 \end{itemize}
  43
  44
  45
  46
  47 \subsubsection{float32\_unpack} \label{vorbis:spec:float32:unpack}
  48
  49 "float32\_unpack(x)" is intended to translate the packed binary
  50 representation of a Vorbis codebook float value into the
  51 representation used by the decoder for floating point numbers.  For
  52 purposes of this example, we will unpack a Vorbis float32 into a
  53 host-native floating point number.
  54
  55 \begin{programlisting}
  56   1) [mantissa] = [x] bitwise AND 0x1fffff (unsigned result)
  57   2) [sign] = [x] bitwise AND 0x80000000 (unsigned result)
  58   3) [exponent] = ( [x] bitwise AND 0x7fe00000) shifted right 21 bits (unsigned result)
  59   4) if ( [sign] is nonzero ) then negate [mantissa]
  60   5) return [mantissa] * ( 2 ^ ( [exponent] - 788 ) )
  61 \end{programlisting}
  62
  63
  64
  65 \subsubsection{lookup1\_values} \label{vorbis:spec:lookup1:values}
  66
  67 "lookup1\_values(codebook\_entries,codebook\_dimensions)" is used to
  68 compute the correct length of the value index for a codebook VQ lookup
  69 table of lookup type 1.  The values on this list are permuted to
  70 construct the VQ vector lookup table of size
  71 \varname{[codebook\_entries]}.
  72
  73 The return value for this function is defined to be 'the greatest
  74 integer value for which \varname{[return\_value]} to the power of
  75 \varname{[codebook\_dimensions]} is less than or equal to
  76 \varname{[codebook\_entries]}'.
  77
  78
  79
  80 \subsubsection{low\_neighbor} \label{vorbis:spec:low:neighbor}
  81
  82 "low\_neighbor(v,x)" finds the position \varname{n} in vector \varname{[v]} of
  83 the greatest value scalar element for which \varname{n} is less than
  84 \varname{[x]} and vector \varname{[v]} element \varname{n} is less
  85 than vector \varname{[v]} element \varname{[x]}.
  86
  87 \subsubsection{high\_neighbor} \label{vorbis:spec:high:neighbor}
  88
  89 "high\_neighbor(v,x)" finds the position \varname{n} in vector [v] of
  90 the lowest value scalar element for which \varname{n} is less than
  91 \varname{[x]} and vector \varname{[v]} element \varname{n} is greater
  92 than vector \varname{[v]} element \varname{[x]}.
  93
  94
  95
  96 \subsubsection{render\_point} \label{vorbis:spec:render:point}
  97
  98 "render\_point(x0,y0,x1,y1,X)" is used to find the Y value at point X
  99 along the line specified by x0, x1, y0 and y1.  This function uses an
 100 integer algorithm to solve for the point directly without calculating
 101 intervening values along the line.
 102
 103 \begin{programlisting}
 104   1)  [dy] = [y1] - [y0]
 105   2) [adx] = [x1] - [x0]
 106   3) [ady] = absolute value of [dy]
 107   4) [err] = [ady] * ([X] - [x0])
 108   5) [off] = [err] / [adx] using integer division
 109   6) if ( [dy] is less than zero ) {
 110
 111        7) [Y] = [y0] - [off]
 112
 113      } else {
 114
 115        8) [Y] = [y0] + [off]
 116
 117      }
 118
 119   9) done
 120 \end{programlisting}
 121
 122
 123
 124 \subsubsection{render\_line} \label{vorbis:spec:render:line}
 125
 126 Floor decode type one uses the integer line drawing algorithm of
 127 "render\_line(x0, y0, x1, y1, v)" to construct an integer floor
 128 curve for contiguous piecewise line segments. Note that it has not
 129 been relevant elsewhere, but here we must define integer division as
 130 rounding division of both positive and negative numbers toward zero.
 131
 132
 133 \begin{programlisting}
 134   1)   [dy] = [y1] - [y0]
 135   2)  [adx] = [x1] - [x0]
 136   3)  [ady] = absolute value of [dy]
 137   4) [base] = [dy] / [adx] using integer division
 138   5)    [x] = [x0]
 139   6)    [y] = [y0]
 140   7)  [err] = 0
 141
 142   8) if ( [dy] is less than 0 ) {
 143
 144         9) [sy] = [base] - 1
 145
 146      } else {
 147
 148        10) [sy] = [base] + 1
 149
 150      }
 151
 152  11) [ady] = [ady] - (absolute value of [base]) * [adx]
 153  12) vector [v] element [x] = [y]
 154
 155  13) iterate [x] over the range [x0]+1 ... [x1]-1 {
 156
 157        14) [err] = [err] + [ady];
 158        15) if ( [err] >= [adx] ) {
 159
 160              16) [err] = [err] - [adx]
 161              17)   [y] = [y] + [sy]
 162
 163            } else {
 164
 165              18) [y] = [y] + [base]
 166
 167            }
 168
 169        19) vector [v] element [x] = [y]
 170
 171      }
 172 \end{programlisting}
 173
 174
 175
 176
 177
 178
 179
 180