Vorbis dev - May 2004 - granulepos start/end revisited

Hi all,

I noticed the following Subversion commit today:

   r6719 | xiphmont | 2004-05-18 16:04:53 +1000 (Tue, 18 May 2004) | 11 
lines

   Updated doc to reflect current proposal...

   Not as much a proposal at this point actually; this is the way I'm now
   implementing it.  Although we're still in the 'RFC'/'look for
horrible
   lossage' stage, this is close to being set in stone unless we find
   something horribly wrong with it.

   Doc is still very light on detailed rationale and examples; I'd like
   to subcontract that part of the writing and get on with code.

I'm a bit concerned about some of the multiplexing changes, 
specifically these paragraphs:

     A granule position represents the instantaneous time location 
between two pages. However, continuous streams and discontinuous 
streams differ on whether the granulepos represents the end-time of the 
data on a page or the start-time. Continuous streams are 'end-time' 
encoded; the granulepos represents the point in time immediately after 
the last data decoded from a page. Discontinuous streams are 
'start-time' encoded; the granulepos represents the point in time of 
the first data decoded from the page.

     An Ogg stream type is declared continuous or discontinuous by its 
codec. A given codec may support both continuous and discontinuous 
operation so long as any given logical stream is continuous or 
discontinuous for its entirety and the codec is able to ascertain (and 
inform the Ogg layer) as to which after decoding the initial stream 
header. The majority of codecs will always be continuous (such as 
Vorbis) or discontinuous (such as Writ).

     Start- and end-time encoding do not affect multiplexing sort-order; 
pages are still sorted by the absolute time a given granulepos maps to 
regardless of whether that granulepos prepresents start- or end-time.

A simple question (with a complex answer, no doubt): what's the 
rationale for having a start-time encoded granulepos?  It adds (1) 
another dependency, and (2) the need for mode core to handle both start 
times and end times, which will also touch many parts of Ogg and 
possibly affect the code base of the codecs as well.

To frame the question another way, what's wrong with the current 
end-time granulepos scheme?  I've read through all the discussions and 
IRC meeting logs, and still don't understand the necessity for it.

Thanks,

<p>
-- 
% Andre Pang : trust.in.love.to.save

--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to
'vorbis-dev-request@xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is
needed.
Unsubscribe messages sent to the list will be ignored/filtered.

> I noticed the following Subversion commit today:
> 
>   r6719 | xiphmont | 2004-05-18 16:04:53 +1000 (Tue, 18 May 2004) | 11 
> lines
> 
>   Updated doc to reflect current proposal...
...
> A simple question (with a complex answer, no doubt): what's the 
> rationale for having a start-time encoded granulepos?  It adds (1) 
> another dependency, and (2) the need for mode core to handle both start 
> times and end times, which will also touch many parts of Ogg and 
> possibly affect the code base of the codecs as well.
> 
> To frame the question another way, what's wrong with the current 
> end-time granulepos scheme?  I've read through all the discussions and 
> IRC meeting logs, and still don't understand the necessity for it.
The discussion is currently mostly going on on theora-dev, for those
that are interested in reading more.

jack.
--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to
'vorbis-dev-request@xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is
needed.
Unsubscribe messages sent to the list will be ignored/filtered.

On Tue, May 18, 2004 at 05:49:35PM +1000, Andr? Pang
wrote:
> 
> A simple question (with a complex answer, no doubt): what's the 
> rationale for having a start-time encoded granulepos?  It adds (1) 
> another dependency, and (2) the need for mode core to handle both start 
> times and end times, which will also touch many parts of Ogg and 
> possibly affect the code base of the codecs as well.
The answer is actually simple.

The whole definition of "continuous" is that one sample follows
another
in a continuous stream of granules.  You know that the endpos + 1 = the 
startpos of the next page.  You know that when you get a page of a 
continuous stream with a granulepos of 59391 that it has enough data to 
play from the granulepos of the previous page until this one.  
Everything muxes well, and all is well with the world.

Then this Writ thing came along and smashed all the rules.  With Writ, 
the granules provided by one page may *GASP* overlap with the granules 
of the next!  What's more, a single page may span in time several 
minutes into the future!  If we order by end time, we'd have two 
choices; we would either need to read ahead some absurd amount to make 
sure we have enough data from the Writ stream to start displaying the 
subtitles on time, or we would need to break Ogg by ordering the pages 
by start-time while storing them with end-time granulepos (this is what 
OggMIDI currently does).

There was a lengthy discussion about this last fall where the solution 
was found.  Change discontinuous streams to start-time ordering.  When 
compaired to a Vorbis or Theora stream, it's phrases will be in the 
stream at exactly the right time and since Writ pages may overlap in 
their durations, the end-time doesn't matter to Ogg anyways (only to 
Writ, and the end-time is stored within the body of every data packet).
>From here the whole tangent of "well, should we ALSO switch all 
continuous bitstreams too?".  The answer is no, because that results in 
less optimal muxing.  Discontinuous streams don't matter for muxing 
because they're, well atleast Writ is, very low bandwidth.

Hope this answers your question.

Check out Writ at http://wiki.xiph.org/OggWrit

--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to
'vorbis-dev-request@xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is
needed.
Unsubscribe messages sent to the list will be ignored/filtered.

On Tue, May 18, 2004 at 05:49:35PM +1000, Andr? Pang
wrote:
> A simple question (with a complex answer, no doubt): what's the 
> rationale for having a start-time encoded granulepos?
Start-time is used for discontinuous streams.  Discontinuous streams are mostly
intended to be treated like a string of randomly spaced events.  By having a
start-time encoded page, you guarantee that from any seek point:

1) all events that happen after the seek are ahead of you.

2) any event will 'fall out' of stream buffering before its needed,
without the buffering algorithm needing to look ahead for an
arbitrary/unbounded period of time.

The example is simple; suppose the 'event' is a subtitle intended to
be on screen for 10 seconds.  If the event was encoded and multiplexed
by end-time, you would need to buffer ahead a minimum of ten seconds
to see the 'event' in time.
> It adds (1) 
> another dependency
Actually it doesn't.
> and (2) the need for mode core to handle both start 
> times and end times, which will also touch many parts of Ogg and 
> possibly affect the code base of the codecs as well.
The codecs are not really concerned at all by this.  The OggFile glue
might be, but none of that actually exists yet.

Nor does this complicate seeking at all; both cases are treated as a
marker of time between pages, one just happens to signify beginning of
page, the other the end.  In fact, having the two seperate cases and a
strict monotonically increasing sort does a great deal to keep seeking
simple.
> To frame the question another way, what's wrong with the current 
> end-time granulepos scheme?  I've read through all the discussions and 
> IRC meeting logs, and still don't understand the necessity for it.
It's all about buffering of a multiplexed stream, and making that
buffering algorithm as simple as possible.  Having two stream types
(and two sort orders) eliminates a raft of special cases you'd need to
smash it all down into one master type.

It all boils down to 'this way, discontinuous streams are ignored in
managing buffers, but can still be used to seek.'

Monty
--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to
'vorbis-dev-request@xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is
needed.
Unsubscribe messages sent to the list will be ignored/filtered.

On Tue, May 18, 2004 at 05:49:35PM +1000, Andr? Pang wrote:
> A simple question (with a complex answer, no doubt): what's the 
> rationale for having a start-time encoded granulepos?  It adds (1) 
> another dependency, and (2) the need for mode core to handle both start 
> times and end times, which will also touch many parts of Ogg and 
> possibly affect the code base of the codecs as well.
Well, aside from ogm, there's not been too much deployment of 
multiplexed streams.
> To frame the question another way, what's wrong with the current 
> end-time granulepos scheme?  I've read through all the discussions and 
> IRC meeting logs, and still don't understand the necessity for it.
Another way to think about it is a kludge for keeping relevent data
together when you're interleaving bitstreams of significantly different 
data rates. A page from a low bitrate stream may cover the same interval
of time as many pages from a high-bitrate stream. If the pages are 
sorted by their end-times, that means the page for the low bitrate 
stream comes at the end of the sequence of pages from the high-bitrate 
stream.

This is the opposite of what you want: you must either buffer all that 
high bitrate data until you get to the low bitrate data and can begin 
decoding, or you have to seek each stream individually like avi.

What you want is the low-bitrate stream's page at the beginning instead.
 
So you can't sort pages by their end times. Monty's proposal wants to 
use any page's granulepos as a seeking signpost, so the rule became 
'order by granulepos time' rather than 'order by end time' and
you
adjust what the granulepos describes to get around the sorting problem.

The tradeoff is that seeking is harder in streams sorted by start time,
because it is paradoxically more difficult to determine if all the data 
you need is ahead of the time you've jumped to. I believe the idea is 
to only require proper decode from the seekpoint for streams that use
end-time granulepos (and hence sorting).

 -r
--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to
'vorbis-dev-request@xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is
needed.
Unsubscribe messages sent to the list will be ignored/filtered.