matroskademux: Improve/optimize seeking

First of all a keyframe seek should be done to the
keyframe right before the requested position and not
to the keyframe that is nearest to the requested position.

Use per track index arrays and use our new binary search function
from core to speed up the search.

2 files changed, 57 insertions, 51 deletions

diff --git a/gst/matroska/matroska-demux.c b/gst/matroska/matroska-demux.c
index 1ae44339..ec07d96b 100644
--- a/gst/matroska/matroska-demux.c
+++ b/gst/matroska/matroska-demux.c
@@ -271,6 +271,9 @@ gst_matroska_track_free (GstMatroskaTrackContext * track)
   if (track->pending_tags)
     gst_tag_list_free (track->pending_tags);
 
+  if (track->index_table)
+    g_array_free (track->index_table, TRUE);
+
   g_free (track);
 }
 
@@ -1932,60 +1935,40 @@ gst_matroska_demux_handle_src_query (GstPad * pad, GstQuery * query)
   return ret;
 }
 
+static gint
+gst_matroska_index_seek_find (GstMatroskaIndex * i1, GstClockTime * time,
+    gpointer user_data)
+{
+  if (i1->time < *time)
+    return -1;
+  else if (i1->time > *time)
+    return 1;
+  else
+    return 0;
+}
+
 static GstMatroskaIndex *
-gst_matroskademux_do_index_seek (GstMatroskaDemux * demux, guint track,
-    gint64 seek_pos, gint64 segment_stop, gboolean keyunit)
+gst_matroskademux_do_index_seek (GstMatroskaDemux * demux,
+    GstMatroskaTrackContext * track, gint64 seek_pos, gint64 segment_stop,
+    gboolean keyunit)
 {
   GstMatroskaIndex *entry = NULL;
-  guint n;
+  GArray *index;
 
   if (!demux->index || !demux->index->len)
     return NULL;
 
   /* find entry just before or at the requested position */
-  for (n = 0; n < demux->index->len; n++) {
-    GstMatroskaIndex *index;
-
-    index = &g_array_index (demux->index, GstMatroskaIndex, n);
-
-    if (index->time <= seek_pos && ((track && index->track == track) || !track))
-      entry = index;
-    else
-      break;
-  }
-
-  if (keyunit) {
-    /* find index entry closest to the requested position.
-     * n contains the index of the GstMatroskaIndex after
-     * entry
-     */
-    if (entry && n < demux->index->len) {
-      GstMatroskaIndex *index;
-      GstClockTimeDiff d_this, d_entry;
-
-      do {
-        index = &g_array_index (demux->index, GstMatroskaIndex, n);
-      } while (n++ < demux->index->len && ((track && index->track == track)
-              || !track));
-
-      d_entry = GST_CLOCK_DIFF (entry->time, seek_pos);
-      if (d_entry < 0)
-        d_entry = -d_entry;
-
-      d_this = GST_CLOCK_DIFF (index->time, seek_pos);
-      if (d_this < 0)
-        d_this = -d_this;
-
-      if (d_this < d_entry &&
-          (index->time < segment_stop || segment_stop == -1)) {
-        entry = index;
-      }
-    }
-  }
+  if (track && track->index_table)
+    index = track->index_table;
+  else
+    index = demux->index;
 
-  if (entry == NULL && track)
-    entry = gst_matroskademux_do_index_seek (demux, 0,
-        seek_pos, segment_stop, keyunit);
+  entry =
+      gst_util_array_binary_search (index->data, index->len,
+      sizeof (GstMatroskaIndex),
+      (GCompareDataFunc) gst_matroska_index_seek_find, GST_SEARCH_MODE_BEFORE,
+      &seek_pos, NULL);
 
   return entry;
 }
@@ -2054,12 +2037,10 @@ gst_matroska_demux_handle_seek_event (GstMatroskaDemux * demux,
   gint64 cur, stop;
   gint64 segment_start, segment_stop;
   gint i;
-  guint track = 0;
+  GstMatroskaTrackContext *track = NULL;
 
-  if (pad) {
-    GstMatroskaTrackContext *context = gst_pad_get_element_private (pad);
-    track = context->num;
-  }
+  if (pad)
+    track = gst_pad_get_element_private (pad);
 
   gst_event_parse_seek (event, &rate, &format, &flags, &cur_type, &cur,
       &stop_type, &stop);
@@ -2079,7 +2060,7 @@ gst_matroska_demux_handle_seek_event (GstMatroskaDemux * demux,
   /* check sanity before we start flushing and all that */
   if (cur_type == GST_SEEK_TYPE_SET) {
     GST_OBJECT_LOCK (demux);
-    if (!gst_matroskademux_do_index_seek (demux, 0, cur, -1, FALSE)) {
+    if (!gst_matroskademux_do_index_seek (demux, track, cur, -1, FALSE)) {
       GST_DEBUG_OBJECT (demux, "No matching seek entry in index");
       GST_OBJECT_UNLOCK (demux);
       return FALSE;
@@ -2605,6 +2586,7 @@ gst_matroska_demux_parse_index (GstMatroskaDemux * demux)
   GstEbmlRead *ebml = GST_EBML_READ (demux);
   guint32 id;
   GstFlowReturn ret = GST_FLOW_OK;
+  guint i;
 
   if (demux->index)
     g_array_free (demux->index, TRUE);
@@ -2649,6 +2631,28 @@ gst_matroska_demux_parse_index (GstMatroskaDemux * demux)
   /* Sort index by time, smallest time first, for easier searching */
   g_array_sort (demux->index, (GCompareFunc) gst_matroska_index_compare);
 
+  /* Now sort the track specific index entries into their own arrays */
+  for (i = 0; i < demux->index->len; i++) {
+    GstMatroskaIndex *idx = &g_array_index (demux->index, GstMatroskaIndex, i);
+    gint track_num;
+    GstMatroskaTrackContext *ctx;
+
+    if (idx->track == 0)
+      continue;
+
+    track_num = gst_matroska_demux_stream_from_num (demux, idx->track);
+    if (track_num == -1)
+      continue;
+
+    ctx = g_ptr_array_index (demux->src, track_num);
+
+    if (ctx->index_table == NULL)
+      ctx->index_table =
+          g_array_sized_new (FALSE, FALSE, sizeof (GstMatroskaIndex), 128);
+
+    g_array_append_vals (ctx->index_table, idx, 1);
+  }
+
   demux->index_parsed = TRUE;
 
   return ret;
diff --git a/gst/matroska/matroska-ids.h b/gst/matroska/matroska-ids.h
index 0ea880af..ae4eed02 100644
--- a/gst/matroska/matroska-ids.h
+++ b/gst/matroska/matroska-ids.h
@@ -465,6 +465,8 @@ struct _GstMatroskaTrackContext {
   guint         index;
   GstFlowReturn last_flow;
 
+  GArray       *index_table;
+
   /* some often-used info */
   gchar        *codec_id, *codec_name, *name, *language;
   gpointer      codec_priv;