[Vorbis-dev] intro + specification remarks + some questions

[xiphmont at xiph.org]

On 12/5/06, Bram de Jong <bram at splicemusic.com> wrote:

>  > "low_neighbor(v,x)" finds the position n in vector [v] of the greatest
>  > value scalar element for which n is less than [x] and vector [v]
>  > element n is less than vector [v] element [x].

Yes, this wording is... tough... but so is the encoding optimization
it's trying to express.  Vector [v] is essentially a map and the
values in vector [v] are integer positions; they're offsets into a
another vector.  Vector [v]'s values are these offsets listed in
encoded order.  It's a progressive 'tree' encoding where positions are
listed in multiple passes of increasing resolution.  Given a value
from the mapping, the low neighbor is the closest value preceeding
that in the encoding up to that point (there may be a closer value if
the vector is scanned in its entirety, but we're only interested in
values that have already been decoded).

So, low_neigbor finds the position in [v] of the mapping value
immediately preceeding vector [v] element [x], but only up to the
current point of decoding, that is [x].  This is why the return value
must be A) less than [x] (only up to the current decode point), B)
less than vector [v] element [x] (must be a lower value) and the value
at the returned position must be the largest of the values that
otherwise satisfy A) and B) (that is, it not only preceeds vector [v]
element [x] in the mapping, but is in fact the mapping value
immediately preceeding it, if vector [v] was sorted)

> I'm thoroughly confused by this definition... Does this mean:
>
> A)
>    for (n=x-1; n>=0; n--) if (v[n]<v[x]) return n;

no.

> B)
> low_neighbor(v, x)
> {
>      max_pos = 0;
>
>      for (n=0...x-1)
>          if (v[n] < v[x])
>              if (v[n] >= v[max_pos])
>                  max_pos = n;
>
>      return max_pos;
> }

yes.

> In case of B), doesn't this mean that,
> depending on the loop and last if( ) one can get different results as in:
>
> http://bram.smartelectronix.com/tmp/low_neighbor.png
>
> ( line = vector values, red cross = x, green dots = possible values of n )

low_neighbor is not well defined if each value in vector[v] is not
unique, however a [v] with non-unique values is not allowed.

> I.e. a bit more highlevel structure to the docs would be cool and
> provide a lot of clarity. The lowlevel pseudocode is great and highly
> readable, but I did notice that somewhere halfway (after decoding the
> headers) the style changed quite a bit leading me to suspect two authors
> at work.

The original spec was written entirely by me.  I do recall needing to
shift style slightly to capture a concept that I couldn't encode int
he original style, but I thought I'd gone back and updated the
previous code to all reflect the 'newer' style.

[I've not commented on several other points that are good suggestions]

Monty