[Bug 749653] dashdemux: Implement binary search for stream_sidx_seek

[GStreamer (GNOME Bugzilla)]

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

--- Comment #6 from Jimmy Ohn <yongjin.ohn at lge.com> ---
(In reply to Edward Hervey from comment #3)
> 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.

It's very helpful for me. Thanks for your comment:)
I'll attach new patch.

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