adapter: add _masked_scan_uint32

Add a reasonably optimized new gst_adapter_masked_scan_uint32() function
to scan the adapter for a pattern after applying a mask.

Add some unit tests.

API: GstAdapter::gst_adapter_masked_scan_uint32()

Fixes #583187

3 files changed, 259 insertions, 0 deletions

diff --git a/libs/gst/base/gstadapter.c b/libs/gst/base/gstadapter.c
index 1f0b8bbfcf..91082e5884 100644
--- a/libs/gst/base/gstadapter.c
+++ b/libs/gst/base/gstadapter.c
@@ -707,3 +707,80 @@ gst_adapter_prev_timestamp (GstAdapter * adapter, guint64 * distance)
 
   return adapter->priv->timestamp;
 }
+
+/**
+ * gst_adapter_masked_scan_uint32:
+ * @adapter: a #GstAdapter
+ * @mask: mask to apply to data before matching against @pattern
+ * @pattern: pattern to match (after mask is applied)
+ * @offset: offset into the adapter data from which to start scanning, returns
+ *          the last scanned position.
+ * @size: number of bytes to scan from offset
+ *
+ * Scan for pattern @pattern with applied mask @mask in the adapter data,
+ * starting from offset @offset.
+ *
+ * It is an error to call this function without making sure that there is
+ * enough data (offset+size bytes) in the adapter.
+ *
+ * Returns: offset of the first match, or -1 if no match was found.
+ *
+ * Since: 0.10.24
+ */
+guint
+gst_adapter_masked_scan_uint32 (GstAdapter * adapter, guint32 mask,
+    guint32 pattern, guint offset, guint size)
+{
+  GSList *g;
+  guint skip, bsize, i;
+  guint32 state;
+  guint8 *bdata;
+
+  g_return_val_if_fail (size > 0, -1);
+  g_return_val_if_fail (offset + size <= adapter->size, -1);
+
+  /* we can't find the pattern with less than 4 bytes */
+  if (G_UNLIKELY (size < 4))
+    return -1;
+
+  skip = offset + adapter->skip;
+
+  /* first step, do skipping and position on the first buffer */
+  g = adapter->buflist;
+  bsize = GST_BUFFER_SIZE (g->data);
+  while (skip >= bsize) {
+    skip -= bsize;
+    g = g_slist_next (g);
+    bsize = GST_BUFFER_SIZE (g->data);
+  }
+  /* get the data now */
+  bsize -= skip;
+  bdata = GST_BUFFER_DATA (g->data) + skip;
+
+  /* set the state to something that does not match */
+  state = ~pattern;
+
+  /* now find data */
+  while (size > 0) {
+    bsize = MIN (bsize, size);
+    for (i = bsize; i; i--) {
+      state = ((state << 8) | *bdata++);
+      if (G_UNLIKELY ((state & mask) == pattern)) {
+        offset += (bsize - i) - 3;
+        goto found;
+      }
+    }
+    size -= bsize;
+    if (size > 0) {
+      /* nothing found yet, go to next buffer */
+      offset += bsize;
+      g = g_slist_next (g);
+      bsize = GST_BUFFER_SIZE (g->data);
+      bdata = GST_BUFFER_DATA (g->data);
+    }
+  }
+  /* nothing found */
+  offset = -1;
+found:
+  return offset;
+}
diff --git a/libs/gst/base/gstadapter.h b/libs/gst/base/gstadapter.h
index af1c097dfc..49e408e0fa 100644
--- a/libs/gst/base/gstadapter.h
+++ b/libs/gst/base/gstadapter.h
@@ -95,6 +95,10 @@ guint			gst_adapter_available_fast    	(GstAdapter *adapter);
 
 GstClockTime            gst_adapter_prev_timestamp      (GstAdapter *adapter, guint64 *distance);
 
+guint                   gst_adapter_masked_scan_uint32  (GstAdapter * adapter, guint32 mask,
+                                                         guint32 pattern, guint offset, guint size);
+
+
 G_END_DECLS
 
 #endif /* __GST_ADAPTER_H__ */
diff --git a/tests/check/libs/adapter.c b/tests/check/libs/adapter.c
index 7a53120b9a..14dfc6b6b4 100644
--- a/tests/check/libs/adapter.c
+++ b/tests/check/libs/adapter.c
@@ -407,6 +407,183 @@ GST_START_TEST (test_timestamp)
 
 GST_END_TEST;
 
+GST_START_TEST (test_scan)
+{
+  GstAdapter *adapter;
+  GstBuffer *buffer;
+  guint8 *data;
+  guint offset;
+  guint i;
+
+  adapter = gst_adapter_new ();
+  fail_unless (adapter != NULL);
+
+  buffer = gst_buffer_new_and_alloc (100);
+  data = GST_BUFFER_DATA (buffer);
+  /* fill with pattern */
+  for (i = 0; i < 100; i++)
+    data[i] = i;
+
+  gst_adapter_push (adapter, buffer);
+
+  /* find first bytes */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x00010203, 0, 100);
+  fail_unless (offset == 0);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x01020304, 0, 100);
+  fail_unless (offset == 1);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x01020304, 1, 99);
+  fail_unless (offset == 1);
+  /* offset is past the pattern start */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x01020304, 2, 98);
+  fail_unless (offset == -1);
+  /* not enough bytes to find the pattern */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x02030405, 2, 3);
+  fail_unless (offset == -1);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x02030405, 2, 4);
+  fail_unless (offset == 2);
+  /* size does not include the last scanned byte */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x40414243, 0, 0x41);
+  fail_unless (offset == -1);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x40414243, 0, 0x43);
+  fail_unless (offset == -1);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x40414243, 0, 0x44);
+  fail_unless (offset == 0x40);
+  /* past the start */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x40414243, 65, 10);
+  fail_unless (offset == -1);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x40414243, 64, 5);
+  fail_unless (offset == 64);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x60616263, 65, 35);
+  fail_unless (offset == 0x60);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x60616263, 0x60, 4);
+  fail_unless (offset == 0x60);
+  /* past the start */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x60616263, 0x61, 3);
+  fail_unless (offset == -1);
+
+  /* add another buffer */
+  buffer = gst_buffer_new_and_alloc (100);
+  data = GST_BUFFER_DATA (buffer);
+  /* fill with pattern */
+  for (i = 0; i < 100; i++)
+    data[i] = i + 100;
+
+  gst_adapter_push (adapter, buffer);
+
+  /* past the start */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x60616263, 0x61, 6);
+  fail_unless (offset == -1);
+  /* this should work */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x61626364, 0x61, 4);
+  fail_unless (offset == 0x61);
+  /* not enough data */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x62636465, 0x61, 4);
+  fail_unless (offset == -1);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x62636465, 0x61, 5);
+  fail_unless (offset == 0x62);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x62636465, 0, 120);
+  fail_unless (offset == 0x62);
+
+  /* border conditions */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x62636465, 0, 200);
+  fail_unless (offset == 0x62);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x63646566, 0, 200);
+  fail_unless (offset == 0x63);
+  /* we completely searched the first list */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x64656667, 0, 200);
+  fail_unless (offset == 0x64);
+  /* skip first buffer */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x64656667, 0x64,
+      100);
+  fail_unless (offset == 0x64);
+  /* past the start */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x64656667, 0x65,
+      10);
+  fail_unless (offset == -1);
+  /* not enough data to scan */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x64656667, 0x63, 4);
+  fail_unless (offset == -1);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x64656667, 0x63, 5);
+  fail_unless (offset == 0x64);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0xc4c5c6c7, 0, 199);
+  fail_unless (offset == -1);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0xc4c5c6c7, 0x62,
+      102);
+  fail_unless (offset == 0xc4);
+  /* different masks */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0x00ffffff, 0x00656667, 0x64,
+      100);
+  fail_unless (offset == 0x64);
+  /* does not even exist */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0x00ffffff, 0xffffffff, 0x65,
+      99);
+  fail_unless (offset == -1);
+
+  /* flush some bytes */
+  gst_adapter_flush (adapter, 0x20);
+
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x20212223, 0, 100);
+  fail_unless (offset == 0);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0x20212223, 0, 4);
+  fail_unless (offset == 0);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0xc4c5c6c7, 0x62,
+      70);
+  fail_unless (offset == 0xa4);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0xc4c5c6c7, 0, 168);
+  fail_unless (offset == 0xa4);
+
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0xc4c5c6c7, 164, 4);
+  fail_unless (offset == 0xa4);
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0xc4c5c6c7, 0x44,
+      100);
+  fail_unless (offset == 0xa4);
+  /* not enough bytes */
+  offset =
+      gst_adapter_masked_scan_uint32 (adapter, 0xffffffff, 0xc4c5c6c7, 0x44,
+      99);
+  fail_unless (offset == -1);
+
+  g_object_unref (adapter);
+}
+
+GST_END_TEST;
+
 static Suite *
 gst_adapter_suite (void)
 {
@@ -423,6 +600,7 @@ gst_adapter_suite (void)
   tcase_add_test (tc_chain, test_take_order);
   tcase_add_test (tc_chain, test_take_buf_order);
   tcase_add_test (tc_chain, test_timestamp);
+  tcase_add_test (tc_chain, test_scan);
 
   return s;
 }