From 89aa8fe4cb00d2f24260005b008602232d678684 Mon Sep 17 00:00:00 2001
From: Andreas Huber <andih@google.com>
Date: Mon, 19 Sep 2011 12:18:47 -0700
Subject: [PATCH] Remove an O(n^2) algorithm in MPEG4Extractor.cpp to speed up
 seeks in long streams

containing B-frames.

Change-Id: Ie4dc734d2c2d5a5ce84674bb883f4b27e2278642
related-to-bug: 5336497
---
 media/libstagefright/SampleTable.cpp       | 101 +++++++++++++++++++++++------
 media/libstagefright/include/SampleTable.h |   6 +-
 2 files changed, 84 insertions(+), 23 deletions(-)

diff --git a/media/libstagefright/SampleTable.cpp b/media/libstagefright/SampleTable.cpp
index 2b9d99bdf5..ebad321580 100644
--- a/media/libstagefright/SampleTable.cpp
+++ b/media/libstagefright/SampleTable.cpp
@@ -23,8 +23,8 @@
 
 #include <arpa/inet.h>
 
+#include <media/stagefright/foundation/ADebug.h>
 #include <media/stagefright/DataSource.h>
-#include <media/stagefright/MediaDebug.h>
 #include <media/stagefright/Utils.h>
 
 namespace android {
@@ -40,6 +40,71 @@ const uint32_t SampleTable::kSampleSizeTypeCompact = FOURCC('s', 't', 'z', '2');
 
 ////////////////////////////////////////////////////////////////////////////////
 
+struct SampleTable::CompositionDeltaLookup {
+    CompositionDeltaLookup();
+
+    void setEntries(
+            const uint32_t *deltaEntries, size_t numDeltaEntries);
+
+    uint32_t getCompositionTimeOffset(uint32_t sampleIndex);
+
+private:
+    Mutex mLock;
+
+    const uint32_t *mDeltaEntries;
+    size_t mNumDeltaEntries;
+
+    size_t mCurrentDeltaEntry;
+    size_t mCurrentEntrySampleIndex;
+
+    DISALLOW_EVIL_CONSTRUCTORS(CompositionDeltaLookup);
+};
+
+SampleTable::CompositionDeltaLookup::CompositionDeltaLookup()
+    : mDeltaEntries(NULL),
+      mNumDeltaEntries(0),
+      mCurrentDeltaEntry(0),
+      mCurrentEntrySampleIndex(0) {
+}
+
+void SampleTable::CompositionDeltaLookup::setEntries(
+        const uint32_t *deltaEntries, size_t numDeltaEntries) {
+    Mutex::Autolock autolock(mLock);
+
+    mDeltaEntries = deltaEntries;
+    mNumDeltaEntries = numDeltaEntries;
+    mCurrentDeltaEntry = 0;
+    mCurrentEntrySampleIndex = 0;
+}
+
+uint32_t SampleTable::CompositionDeltaLookup::getCompositionTimeOffset(
+        uint32_t sampleIndex) {
+    Mutex::Autolock autolock(mLock);
+
+    if (mDeltaEntries == NULL) {
+        return 0;
+    }
+
+    if (sampleIndex < mCurrentEntrySampleIndex) {
+        mCurrentDeltaEntry = 0;
+        mCurrentEntrySampleIndex = 0;
+    }
+
+    while (mCurrentDeltaEntry < mNumDeltaEntries) {
+        uint32_t sampleCount = mDeltaEntries[2 * mCurrentDeltaEntry];
+        if (sampleIndex < mCurrentEntrySampleIndex + sampleCount) {
+            return mDeltaEntries[2 * mCurrentDeltaEntry + 1];
+        }
+
+        mCurrentEntrySampleIndex += sampleCount;
+        ++mCurrentDeltaEntry;
+    }
+
+    return 0;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
 SampleTable::SampleTable(const sp<DataSource> &source)
     : mDataSource(source),
       mChunkOffsetOffset(-1),
@@ -56,6 +121,7 @@ SampleTable::SampleTable(const sp<DataSource> &source)
       mSampleTimeEntries(NULL),
       mCompositionTimeDeltaEntries(NULL),
       mNumCompositionTimeDeltaEntries(0),
+      mCompositionDeltaLookup(new CompositionDeltaLookup),
       mSyncSampleOffset(-1),
       mNumSyncSamples(0),
       mSyncSamples(NULL),
@@ -71,6 +137,9 @@ SampleTable::~SampleTable() {
     delete[] mSyncSamples;
     mSyncSamples = NULL;
 
+    delete mCompositionDeltaLookup;
+    mCompositionDeltaLookup = NULL;
+
     delete[] mCompositionTimeDeltaEntries;
     mCompositionTimeDeltaEntries = NULL;
 
@@ -318,6 +387,9 @@ status_t SampleTable::setCompositionTimeToSampleParams(
         mCompositionTimeDeltaEntries[i] = ntohl(mCompositionTimeDeltaEntries[i]);
     }
 
+    mCompositionDeltaLookup->setEntries(
+            mCompositionTimeDeltaEntries, mNumCompositionTimeDeltaEntries);
+
     return OK;
 }
 
@@ -430,8 +502,12 @@ void SampleTable::buildSampleEntriesTable() {
 
                 mSampleTimeEntries[sampleIndex].mSampleIndex = sampleIndex;
 
+                uint32_t compTimeDelta =
+                    mCompositionDeltaLookup->getCompositionTimeOffset(
+                            sampleIndex);
+
                 mSampleTimeEntries[sampleIndex].mCompositionTime =
-                    sampleTime + getCompositionTimeOffset(sampleIndex);
+                    sampleTime + compTimeDelta;
             }
 
             ++sampleIndex;
@@ -739,25 +815,8 @@ status_t SampleTable::getMetaDataForSample(
     return OK;
 }
 
-uint32_t SampleTable::getCompositionTimeOffset(uint32_t sampleIndex) const {
-    if (mCompositionTimeDeltaEntries == NULL) {
-        return 0;
-    }
-
-    uint32_t curSample = 0;
-    for (size_t i = 0; i < mNumCompositionTimeDeltaEntries; ++i) {
-        uint32_t sampleCount = mCompositionTimeDeltaEntries[2 * i];
-
-        if (sampleIndex < curSample + sampleCount) {
-            uint32_t sampleDelta = mCompositionTimeDeltaEntries[2 * i + 1];
-
-            return sampleDelta;
-        }
-
-        curSample += sampleCount;
-    }
-
-    return 0;
+uint32_t SampleTable::getCompositionTimeOffset(uint32_t sampleIndex) {
+    return mCompositionDeltaLookup->getCompositionTimeOffset(sampleIndex);
 }
 
 }  // namespace android
diff --git a/media/libstagefright/include/SampleTable.h b/media/libstagefright/include/SampleTable.h
index a6a6524c06..847dff70bf 100644
--- a/media/libstagefright/include/SampleTable.h
+++ b/media/libstagefright/include/SampleTable.h
@@ -86,6 +86,8 @@ protected:
     ~SampleTable();
 
 private:
+    struct CompositionDeltaLookup;
+
     static const uint32_t kChunkOffsetType32;
     static const uint32_t kChunkOffsetType64;
     static const uint32_t kSampleSizeType32;
@@ -117,6 +119,7 @@ private:
 
     uint32_t *mCompositionTimeDeltaEntries;
     size_t mNumCompositionTimeDeltaEntries;
+    CompositionDeltaLookup *mCompositionDeltaLookup;
 
     off64_t mSyncSampleOffset;
     uint32_t mNumSyncSamples;
@@ -135,8 +138,7 @@ private:
     friend struct SampleIterator;
 
     status_t getSampleSize_l(uint32_t sample_index, size_t *sample_size);
-
-    uint32_t getCompositionTimeOffset(uint32_t sampleIndex) const;
+    uint32_t getCompositionTimeOffset(uint32_t sampleIndex);
 
     static int CompareIncreasingTime(const void *, const void *);
 
-- 
2.11.0