[Bug 749653] dashdemux: Implement binary search for stream_sidx_seek

[GStreamer (GNOME Bugzilla)]

https://bugzilla.gnome.org/show_bug.cgi?id=749653

Edward Hervey <bilboed at bilboed.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bilboed at bilboed.com

--- Comment #3 from Edward Hervey <bilboed at bilboed.com> ---
Note that a slightly better algorithm could be to assume an even distribution
of the entries, and weigh the mid-point evaluation. This is called
interpolation search.

Example:
low value = entry 0 (ts : 0s)
high value = entry 100 (ts : 600s (10min))
target = 30s

Instead of using:
  mid = (high - low) / 2 (which would give you mid entry 50)

You weigh it:
  difference in entries : high - low : 100
  difference in values : high ts - low ts : 600s
  mid = (target ts) / (difference in values) * (difference in entries)
      = 30 / 600 * 100
      = 5

  If you're lucky it's in that entry (yay, found the entry in one go), if not,
you re-adjust either high or low (juste like in steps 3.1 and 3.2 above) and
repeat.

sidx entries are likely to be roughly the same duration, so this could allow
very fast entry search.

-- 
You are receiving this mail because:
You are the QA Contact for the bug.
You are the assignee for the bug.