[gst-devel] GstTimeCache intro

[Erik Walthinsen]

An object I've been working on lately as part of the seek support is the
TimeCache.  This is an object that brentb and I designed a few months
back, and I'm finally getting around to writing it...

The idea is that it provides a cache for an element to keep track of the
mapping between time and space.  It's got some very cool features to
handle fuzzy seeking and so on, assuming I can flesh them all out...

The basic unit is the 'event', which is just a gint64 timestamp and
guint64 location.  These can be added with gst_timecache_add_event(), and
are exactly the size in memory you'd think: 16 bytes (currently there's
significant overhead of the controlling structures, but eventually it'll
be quite efficient).

All events are contained within a 'group', which is a numbered entity
within the TimeCache.  Each group contains a list of entries, a certainty
value, and some bookkeeping info.

The certainty value is the major feature of this object.  It defines
whether the timestamp, location, or both, are not accurate (fuzzy).  For
example, when playing an mp3 through, events would be added for every N
(N>=1) frames, which would be certain in both time and space (frame time
and byte position are positively known).  But if you seek into a VBR mp3
file, you have to guess at the byte position, and you could argue that
you're guessing at the timestamp as well.

When circumstances change, you can create a new group within the
timecache, with an int identifier, set its certainty level, and start
adding events.

Now, the part that hasn't been fully designed or spec'd out yet is the
ability of the timecache to realign groups when they start to overlap.
If you start with a VBR file that has a VBR header (each 100th of the file
in time has a byte representing the 256ths of the file size in bytes), and
jump straight to the middle of it, you'll end up with both the completely
fuzzy VBR-table group and the partially-fuzzy frame-accurate group that
you build up as you play.

If you then seek to the beginning of the file and start playing, you can
create a new group that's totally certain of both time and bytes.  When
this group overlaps with the existing groups, the timecache would be able
to rewrite those groups and possibly merge them into the main group,
allowing a massive savings of work in parsing through the whole file
again.

The thought I just had is to optionally associate each group with a more
certain group, under a certain policy.  For instance, the VBR-table group
would point to the mid-point time-accurate group as more accurate, and
that group would eventually point to the master group, which is totally
accurate.  Each would have a policy such that when they overlap in either
time, bytes, or both, a certain mechanism would be used to align the less
certain group with the more certain group.  The list of policies would be
quite short, so this might work quite well.

And of course, the whole thing is useless without query support.  I have
routines to find a specific timestamp and location in any existing group,
so far, and intend to add routines that mask what certainty levels are
acceptable, as well as functions to interpolate between the closest two
points.

Comments?

      Erik Walthinsen <omega at temple-baptist.com> - System Administrator
        __
       /  \                GStreamer - The only way to stream!
      |    | M E G A        ***** http://gstreamer.net/ *****
      _\  /_