This is just the first version and shows how I intend to orchestrate this. Future enhancements will:

track the portion of the bitmap required
track any resizing that might be required
actually preload something

R=bsalomon@google.com, mtklein@google.com

Author: robertphillips@google.com

Review URL: https://codereview.chromium.org/187833003

git-svn-id: http://skia.googlecode.com/svn/trunk@13704 2bbb7eff-a529-9590-31e7-b0007b416f81

6 files changed, 223 insertions, 21 deletions

diff --git a/gyp/core.gypi b/gyp/core.gypi
index e4f73e3d08..a1eed0a729 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -114,8 +114,7 @@
         '<(skia_src_path)/core/SkMessageBus.h',
         '<(skia_src_path)/core/SkMetaData.cpp',
         '<(skia_src_path)/core/SkMipMap.cpp',
-        '<(skia_src_path)/core/SkReadBuffer.cpp',
-        '<(skia_src_path)/core/SkWriteBuffer.cpp',
+        '<(skia_src_path)/core/SkOffsetTable.h',
         '<(skia_src_path)/core/SkPackBits.cpp',
         '<(skia_src_path)/core/SkPaint.cpp',
         '<(skia_src_path)/core/SkPaintOptionsAndroid.cpp',
@@ -148,6 +147,7 @@
         '<(skia_src_path)/core/SkQuadTreePicture.h',
         '<(skia_src_path)/core/SkRasterClip.cpp',
         '<(skia_src_path)/core/SkRasterizer.cpp',
+        '<(skia_src_path)/core/SkReadBuffer.cpp',
         '<(skia_src_path)/core/SkRect.cpp',
         '<(skia_src_path)/core/SkRefDict.cpp',
         '<(skia_src_path)/core/SkRegion.cpp',
@@ -196,6 +196,7 @@
         '<(skia_src_path)/core/SkUnPreMultiply.cpp',
         '<(skia_src_path)/core/SkUtils.cpp',
         '<(skia_src_path)/core/SkValidatingReadBuffer.cpp',
+        '<(skia_src_path)/core/SkWriteBuffer.cpp',
         '<(skia_src_path)/core/SkWriter32.cpp',
         '<(skia_src_path)/core/SkXfermode.cpp',
 
diff --git a/src/core/SkOffsetTable.h b/src/core/SkOffsetTable.h
new file mode 100644
index 0000000000..60c62642b2
--- /dev/null
+++ b/src/core/SkOffsetTable.h
@@ -0,0 +1,115 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkOffsetTable_DEFINED
+#define SkOffsetTable_DEFINED
+
+#include "SkRefCnt.h"
+#include "SkTDArray.h"
+
+// A 2D table of skp offsets. Each row is indexed by an int. This is used
+// to store the command offsets that reference a particular bitmap using
+// the bitmap's index in the bitmap heap as the 'id' here. It has to be
+// ref-countable so SkPicturePlayback can take ownership of it.
+// Note that this class assumes that the ids are densely packed.
+
+// TODO: This needs to be sped up. We could replace the offset table with
+// a hash table.
+class SkOffsetTable : public SkRefCnt {
+public:
+    SkOffsetTable() {}
+    ~SkOffsetTable() {
+        fOffsetArrays.deleteAll();
+    }
+
+    // Record that this 'id' is used by the command starting at this 'offset'.
+    // Offsets for a given 'id' should always be added in increasing order.
+    void add(int id, size_t offset) {
+        if (id >= fOffsetArrays.count()) {
+            int oldCount = fOffsetArrays.count();
+            fOffsetArrays.setCount(id+1);
+            for (int i = oldCount; i <= id; ++i) {
+                fOffsetArrays[i] = NULL;
+            }
+        }
+
+        if (NULL == fOffsetArrays[id]) {
+            fOffsetArrays[id] = SkNEW(OffsetArray);
+        }
+        fOffsetArrays[id]->add(offset);
+    }
+
+    int numIDs() const {
+        return fOffsetArrays.count(); 
+    }
+
+    // Do the offsets of any commands referencing this ID fall in the 
+    // range [min, max] (both inclusive)
+    bool overlap(int id, size_t min, size_t max) {
+        SkASSERT(id < fOffsetArrays.count());
+
+        if (NULL == fOffsetArrays[id]) {
+            return false;
+        }
+
+        // If this id has an offset array it should have at least one use
+        SkASSERT(fOffsetArrays[id]->count() > 0);
+        if (max < fOffsetArrays[id]->min() || min > fOffsetArrays[id]->max()) {
+            return false;
+        }
+
+        return true;
+    }
+
+    bool includes(int id, size_t offset) {
+        SkASSERT(id < fOffsetArrays.count());
+
+        OffsetArray* array = fOffsetArrays[id];
+
+        for (int i = 0; i < array->fOffsets.count(); ++i) {
+            if (array->fOffsets[i] == offset) {
+                return true;
+            } else if (array->fOffsets[i] > offset) {
+                return false;
+            }
+        }
+
+        // Calls to 'includes' should be gaurded by an overlap() call, so we
+        // should always find something.
+        SkASSERT(0);
+        return false;
+    }
+
+protected:
+    class OffsetArray {
+    public:
+        void add(size_t offset) { 
+            SkASSERT(fOffsets.count() == 0 || offset > this->max());
+            *fOffsets.append() = offset;  
+        }
+        size_t min() const { 
+            SkASSERT(fOffsets.count() > 0);
+            return fOffsets[0]; 
+        }
+        size_t max() const { 
+            SkASSERT(fOffsets.count() > 0);
+            return fOffsets[fOffsets.count()-1]; 
+        }
+        int count() const {
+            return fOffsets.count();
+        }
+
+        SkTDArray<size_t> fOffsets;
+    };
+
+    SkTDArray<OffsetArray*> fOffsetArrays;
+
+private:
+    typedef SkRefCnt INHERITED;
+};
+
+#endif
diff --git a/src/core/SkPicturePlayback.cpp b/src/core/SkPicturePlayback.cpp
index 967dfeea50..ab315c1148 100644
--- a/src/core/SkPicturePlayback.cpp
+++ b/src/core/SkPicturePlayback.cpp
@@ -5,15 +5,16 @@
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
-#include "SkPicturePlayback.h"
-#include "SkPictureRecord.h"
-#include "SkTypeface.h"
-#include "SkReadBuffer.h"
-#include "SkWriteBuffer.h"
 #include <new>
 #include "SkBBoxHierarchy.h"
+#include "SkOffsetTable.h"
+#include "SkPicturePlayback.h"
+#include "SkPictureRecord.h"
 #include "SkPictureStateTree.h"
+#include "SkReadBuffer.h"
+#include "SkTypeface.h"
 #include "SkTSort.h"
+#include "SkWriteBuffer.h"
 
 template <typename T> int SafeCount(const T* obj) {
     return obj ? obj->count() : 0;
@@ -101,6 +102,8 @@ SkPicturePlayback::SkPicturePlayback(const SkPictureRecord& record, bool deepCop
     fBitmapHeap.reset(SkSafeRef(record.fBitmapHeap));
     fPathHeap.reset(SkSafeRef(record.fPathHeap));
 
+    fBitmapUseOffsets.reset(SkSafeRef(record.fBitmapUseOffsets.get()));
+
     // ensure that the paths bounds are pre-computed
     if (fPathHeap.get()) {
         for (int i = 0; i < fPathHeap->count(); i++) {
@@ -719,6 +722,50 @@ static DrawType read_op_and_size(SkReader32* reader, uint32_t* size) {
     return (DrawType) op;
 }
 
+// The activeOps parameter is actually "const SkTDArray<SkPictureStateTree::Draw*>&".
+// It represents the operations about to be drawn, as generated by some spatial
+// subdivision helper class. It should already be in 'fOffset' sorted order.
+void SkPicturePlayback::preLoadBitmaps(const SkTDArray<void*>& activeOps) {
+    if (0 == activeOps.count() || NULL == fBitmapUseOffsets) {
+        return;
+    }
+
+    SkTDArray<int> active;
+
+    SkAutoTDeleteArray<bool> needToCheck(new bool[fBitmapUseOffsets->numIDs()]);
+    for (int i = 0; i < fBitmapUseOffsets->numIDs(); ++i) {
+        needToCheck.get()[i] = true;
+    }
+
+    uint32_t max = ((SkPictureStateTree::Draw*)activeOps[activeOps.count()-1])->fOffset;
+
+    for (int i = 0; i < activeOps.count(); ++i) {
+        SkPictureStateTree::Draw* draw = (SkPictureStateTree::Draw*) activeOps[i];
+
+        for (int j = 0; j < fBitmapUseOffsets->numIDs(); ++j) {
+            if (!needToCheck.get()[j]) {
+                continue;
+            }
+
+            if (!fBitmapUseOffsets->overlap(j, draw->fOffset, max)) {
+                needToCheck.get()[j] = false;
+                continue;
+            }
+
+            if (!fBitmapUseOffsets->includes(j, draw->fOffset)) {
+                continue;
+            }
+
+            *active.append() = j;
+            needToCheck.get()[j] = false;
+        }
+    }
+
+    for (int i = 0; i < active.count(); ++i) {
+        SkDebugf("preload texture %d\n", active[i]);
+    }
+}
+
 void SkPicturePlayback::draw(SkCanvas& canvas, SkDrawPictureCallback* callback) {
 #ifdef ENABLE_TIME_DRAW
     SkAutoTime  at("SkPicture::draw", 50);
@@ -739,26 +786,26 @@ void SkPicturePlayback::draw(SkCanvas& canvas, SkDrawPictureCallback* callback)
 
     SkReader32 reader(fOpData->bytes(), fOpData->size());
     TextContainer text;
-    SkTDArray<void*> results;
+    SkTDArray<void*> activeOps;
 
     if (NULL != fStateTree && NULL != fBoundingHierarchy) {
         SkRect clipBounds;
         if (canvas.getClipBounds(&clipBounds)) {
             SkIRect query;
             clipBounds.roundOut(&query);
-            fBoundingHierarchy->search(query, &results);
-            if (results.count() == 0) {
+            fBoundingHierarchy->search(query, &activeOps);
+            if (activeOps.count() == 0) {
                 return;
             }
             SkTQSort<SkPictureStateTree::Draw>(
-                reinterpret_cast<SkPictureStateTree::Draw**>(results.begin()),
-                reinterpret_cast<SkPictureStateTree::Draw**>(results.end()-1));
+                reinterpret_cast<SkPictureStateTree::Draw**>(activeOps.begin()),
+                reinterpret_cast<SkPictureStateTree::Draw**>(activeOps.end()-1));
         }
     }
 
     SkPictureStateTree::Iterator it = (NULL == fStateTree) ?
         SkPictureStateTree::Iterator() :
-        fStateTree->getIterator(results, &canvas);
+        fStateTree->getIterator(activeOps, &canvas);
 
     if (it.isValid()) {
         uint32_t skipTo = it.draw();
@@ -768,6 +815,8 @@ void SkPicturePlayback::draw(SkCanvas& canvas, SkDrawPictureCallback* callback)
         reader.setOffset(skipTo);
     }
 
+    this->preLoadBitmaps(activeOps);
+
     // Record this, so we can concat w/ it if we encounter a setMatrix()
     SkMatrix initialMatrix = canvas.getTotalMatrix();
     int originalSaveCount = canvas.getSaveCount();
diff --git a/src/core/SkPicturePlayback.h b/src/core/SkPicturePlayback.h
index 48d782696d..178a408aee 100644
--- a/src/core/SkPicturePlayback.h
+++ b/src/core/SkPicturePlayback.h
@@ -31,6 +31,7 @@ class SkStream;
 class SkWStream;
 class SkBBoxHierarchy;
 class SkPictureStateTree;
+class SkOffsetTable;
 
 struct SkPictInfo {
     enum Flags {
@@ -107,6 +108,8 @@ protected:
     virtual void postDraw(int opIndex);
 #endif
 
+    void preLoadBitmaps(const SkTDArray<void*>& results);
+
 private:
     class TextContainer {
     public:
@@ -225,6 +228,7 @@ private:
     SkTRefArray<SkPaint>* fPaints;
 
     SkData* fOpData;    // opcodes and parameters
+    SkAutoTUnref<SkOffsetTable> fBitmapUseOffsets;
 
     SkPicture** fPictureRefs;
     int fPictureCount;
diff --git a/src/core/SkPictureRecord.cpp b/src/core/SkPictureRecord.cpp
index 213d1aa454..b9e8b93843 100644
--- a/src/core/SkPictureRecord.cpp
+++ b/src/core/SkPictureRecord.cpp
@@ -11,6 +11,7 @@
 #include "SkRRect.h"
 #include "SkBBoxHierarchy.h"
 #include "SkDevice.h"
+#include "SkOffsetTable.h"
 #include "SkPictureStateTree.h"
 #include "SkSurface.h"
 
@@ -44,6 +45,7 @@ SkPictureRecord::SkPictureRecord(const SkISize& dimensions, uint32_t flags)
     fBitmapHeap = SkNEW(SkBitmapHeap);
     fFlattenableHeap.setBitmapStorage(fBitmapHeap);
     fPathHeap = NULL;   // lazy allocate
+
 #ifndef SK_COLLAPSE_MATRIX_CLIP_STATE
     fFirstSavedLayerIndex = kNoSavedLayerIndex;
 #endif
@@ -1125,10 +1127,11 @@ void SkPictureRecord::drawBitmap(const SkBitmap& bitmap, SkScalar left, SkScalar
     size_t initialOffset = this->addDraw(DRAW_BITMAP, &size);
     SkASSERT(initialOffset+getPaintOffset(DRAW_BITMAP, size) == fWriter.bytesWritten());
     this->addPaintPtr(paint);
-    this->addBitmap(bitmap);
+    int bitmapID = this->addBitmap(bitmap);
     this->addScalar(left);
     this->addScalar(top);
     this->validate(initialOffset, size);
+    this->trackBitmapUse(bitmapID, initialOffset);
 }
 
 void SkPictureRecord::drawBitmapRectToRect(const SkBitmap& bitmap, const SkRect* src,
@@ -1152,11 +1155,12 @@ void SkPictureRecord::drawBitmapRectToRect(const SkBitmap& bitmap, const SkRect*
     SkASSERT(initialOffset+getPaintOffset(DRAW_BITMAP_RECT_TO_RECT, size)
              == fWriter.bytesWritten());
     this->addPaintPtr(paint);
-    this->addBitmap(bitmap);
+    int bitmapID = this->addBitmap(bitmap);
     this->addRectPtr(src);  // may be null
     this->addRect(dst);
     this->addInt(flags);
     this->validate(initialOffset, size);
+    this->trackBitmapUse(bitmapID, initialOffset);
 }
 
 void SkPictureRecord::drawBitmapMatrix(const SkBitmap& bitmap, const SkMatrix& matrix,
@@ -1174,9 +1178,10 @@ void SkPictureRecord::drawBitmapMatrix(const SkBitmap& bitmap, const SkMatrix& m
     size_t initialOffset = this->addDraw(DRAW_BITMAP_MATRIX, &size);
     SkASSERT(initialOffset+getPaintOffset(DRAW_BITMAP_MATRIX, size) == fWriter.bytesWritten());
     this->addPaintPtr(paint);
-    this->addBitmap(bitmap);
+    int bitmapID = this->addBitmap(bitmap);
     this->addMatrix(matrix);
     this->validate(initialOffset, size);
+    this->trackBitmapUse(bitmapID, initialOffset);
 }
 
 void SkPictureRecord::drawBitmapNine(const SkBitmap& bitmap, const SkIRect& center,
@@ -1194,10 +1199,11 @@ void SkPictureRecord::drawBitmapNine(const SkBitmap& bitmap, const SkIRect& cent
     size_t initialOffset = this->addDraw(DRAW_BITMAP_NINE, &size);
     SkASSERT(initialOffset+getPaintOffset(DRAW_BITMAP_NINE, size) == fWriter.bytesWritten());
     this->addPaintPtr(paint);
-    this->addBitmap(bitmap);
+    int bitmapID = this->addBitmap(bitmap);
     this->addIRect(center);
     this->addRect(dst);
     this->validate(initialOffset, size);
+    this->trackBitmapUse(bitmapID, initialOffset);
 }
 
 void SkPictureRecord::drawSprite(const SkBitmap& bitmap, int left, int top,
@@ -1215,10 +1221,11 @@ void SkPictureRecord::drawSprite(const SkBitmap& bitmap, int left, int top,
     size_t initialOffset = this->addDraw(DRAW_SPRITE, &size);
     SkASSERT(initialOffset+getPaintOffset(DRAW_SPRITE, size) == fWriter.bytesWritten());
     this->addPaintPtr(paint);
-    this->addBitmap(bitmap);
+    int bitmapID = this->addBitmap(bitmap);
     this->addInt(left);
     this->addInt(top);
     this->validate(initialOffset, size);
+    this->trackBitmapUse(bitmapID, initialOffset);
 }
 
 void SkPictureRecord::ComputeFontMetricsTopBottom(const SkPaint& paint, SkScalar topbot[2]) {
@@ -1612,13 +1619,34 @@ SkSurface* SkPictureRecord::onNewSurface(const SkImageInfo& info) {
     return SkSurface::NewPicture(info.fWidth, info.fHeight);
 }
 
-void SkPictureRecord::addBitmap(const SkBitmap& bitmap) {
+void SkPictureRecord::trackBitmapUse(int bitmapID, size_t offset) {
+#ifndef SK_ALLOW_BITMAP_TRACKING
+    return;
+#endif
+
+    if (!(fRecordFlags & SkPicture::kOptimizeForClippedPlayback_RecordingFlag)) {
+        return;
+    }
+
+    if (SkBitmapHeap::INVALID_SLOT == bitmapID) {
+        return;
+    }
+
+    if (NULL == fBitmapUseOffsets) {
+        fBitmapUseOffsets.reset(SkNEW(SkOffsetTable));
+    }
+
+    fBitmapUseOffsets->add(bitmapID, offset);
+}
+
+int SkPictureRecord::addBitmap(const SkBitmap& bitmap) {
     const int index = fBitmapHeap->insert(bitmap);
     // In debug builds, a bad return value from insert() will crash, allowing for debugging. In
     // release builds, the invalid value will be recorded so that the reader will know that there
     // was a problem.
     SkASSERT(index != SkBitmapHeap::INVALID_SLOT);
     this->addInt(index);
+    return index;
 }
 
 void SkPictureRecord::addMatrix(const SkMatrix& matrix) {
diff --git a/src/core/SkPictureRecord.h b/src/core/SkPictureRecord.h
index e7c6d7f343..e91c1c5c12 100644
--- a/src/core/SkPictureRecord.h
+++ b/src/core/SkPictureRecord.h
@@ -19,8 +19,9 @@
 #include "SkTemplates.h"
 #include "SkWriter32.h"
 
-class SkPictureStateTree;
 class SkBBoxHierarchy;
+class SkOffsetTable;
+class SkPictureStateTree;
 
 // These macros help with packing and unpacking a single byte value and
 // a 3 byte value into/out of a uint32_t
@@ -164,7 +165,9 @@ private:
         fWriter.writeScalar(scalar);
     }
 
-    void addBitmap(const SkBitmap& bitmap);
+    // The command at 'offset' in the skp uses the specified bitmap
+    void trackBitmapUse(int bitmapID, size_t offset);
+    int addBitmap(const SkBitmap& bitmap);
     void addMatrix(const SkMatrix& matrix);
     const SkFlatData* addPaint(const SkPaint& paint) { return this->addPaintPtr(&paint); }
     const SkFlatData* addPaintPtr(const SkPaint* paint);
@@ -294,6 +297,8 @@ private:
     bool     fOptsEnabled;
     int      fInitialSaveCount;
 
+    SkAutoTUnref<SkOffsetTable> fBitmapUseOffsets;
+
     friend class SkPicturePlayback;
     friend class SkPictureTester; // for unit testing