This CL doesn't radically change the behavior of the matrix\clip stack reducer. It just cleans up the matrix handling a bit.

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

Author: robertphillips@google.com

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

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

2 files changed, 130 insertions, 50 deletions

diff --git a/src/core/SkMatrixClipStateMgr.cpp b/src/core/SkMatrixClipStateMgr.cpp
index 9ff56c2e8e..63c89918fe 100644
--- a/src/core/SkMatrixClipStateMgr.cpp
+++ b/src/core/SkMatrixClipStateMgr.cpp
@@ -12,7 +12,7 @@ bool SkMatrixClipStateMgr::MatrixClipState::ClipInfo::clipPath(SkPictureRecord*
                                                                const SkPath& path,
                                                                SkRegion::Op op,
                                                                bool doAA,
-                                                               const SkMatrix& matrix) {
+                                                               int matrixID) {
     int pathID = picRecord->addPathToHeap(path);
 
     ClipOp& newClip = fClips.push_back();
@@ -20,7 +20,7 @@ bool SkMatrixClipStateMgr::MatrixClipState::ClipInfo::clipPath(SkPictureRecord*
     newClip.fGeom.fPathID = pathID;
     newClip.fOp = op;
     newClip.fDoAA = doAA;
-    newClip.fMatrix = matrix;
+    newClip.fMatrixID = matrixID;
     newClip.fOffset = kInvalidJumpOffset;
     return false;
 }
@@ -28,33 +28,34 @@ bool SkMatrixClipStateMgr::MatrixClipState::ClipInfo::clipPath(SkPictureRecord*
 bool SkMatrixClipStateMgr::MatrixClipState::ClipInfo::clipRegion(SkPictureRecord* picRecord,
                                                                  const SkRegion& region,
                                                                  SkRegion::Op op,
-                                                                 const SkMatrix& matrix) {
+                                                                 int matrixID) {
     // TODO: add a region dictionary so we don't have to copy the region in here
     ClipOp& newClip = fClips.push_back();
     newClip.fClipType = kRegion_ClipType;
     newClip.fGeom.fRegion = SkNEW(SkRegion(region));
     newClip.fOp = op;
     newClip.fDoAA = true;      // not necessary but sanity preserving
-    newClip.fMatrix = matrix;
+    newClip.fMatrixID = matrixID;
     newClip.fOffset = kInvalidJumpOffset;
     return false;
 }
 
-void SkMatrixClipStateMgr::WriteDeltaMat(SkPictureRecord* picRecord,
-                                         const SkMatrix& current,
-                                         const SkMatrix& desired) {
+void SkMatrixClipStateMgr::writeDeltaMat(int currentMatID, int desiredMatID) {
+    const SkMatrix& current = this->lookupMat(currentMatID);
+    const SkMatrix& desired = this->lookupMat(desiredMatID);
+
     SkMatrix delta;
     bool result = current.invert(&delta);
     if (result) {
         delta.preConcat(desired);
     }
-    picRecord->recordConcat(delta);
+    fPicRecord->recordConcat(delta);
 }
 
 // Note: this only writes out the clips for the current save state. To get the
 // entire clip stack requires iterating of the entire matrix/clip stack.
-void SkMatrixClipStateMgr::MatrixClipState::ClipInfo::writeClip(SkMatrix* curMat,
-                                                                SkPictureRecord* picRecord,
+void SkMatrixClipStateMgr::MatrixClipState::ClipInfo::writeClip(int* curMatID, 
+                                                                SkMatrixClipStateMgr* mgr,
                                                                 bool* overrideFirstOp) {
     for (int i = 0; i < fClips.count(); ++i) {
         ClipOp& curClip = fClips[i];
@@ -65,29 +66,34 @@ void SkMatrixClipStateMgr::MatrixClipState::ClipInfo::writeClip(SkMatrix* curMat
             *overrideFirstOp = false;
         }
 
-        // TODO: re-add an internal matrix dictionary to not write out
-        // redundant matrices.
+        // TODO: use the matrix ID to skip writing the identity matrix
+        // over and over, i.e.:
+        //  if (*curMatID != curClip.fMatrixID) {
+        //      mgr->writeDeltaMat...
+        //      *curMatID...
+        //  }
+        // Right now this optimization would throw off the testing harness.
         // TODO: right now we're writing out the delta matrix from the prior
         // matrix state. This is a side-effect of writing out the entire
         // clip stack and should be resolved when that is fixed.
-        SkMatrixClipStateMgr::WriteDeltaMat(picRecord, *curMat, curClip.fMatrix);
-        *curMat = curClip.fMatrix;
+        mgr->writeDeltaMat(*curMatID, curClip.fMatrixID);
+        *curMatID = curClip.fMatrixID;
 
         switch (curClip.fClipType) {
         case kRect_ClipType:
-            curClip.fOffset = picRecord->recordClipRect(curClip.fGeom.fRRect.rect(),
-                                                        op, curClip.fDoAA);
+            curClip.fOffset = mgr->getPicRecord()->recordClipRect(curClip.fGeom.fRRect.rect(), 
+                                                                  op, curClip.fDoAA);
             break;
         case kRRect_ClipType:
-            curClip.fOffset = picRecord->recordClipRRect(curClip.fGeom.fRRect, op,
-                                                         curClip.fDoAA);
+            curClip.fOffset = mgr->getPicRecord()->recordClipRRect(curClip.fGeom.fRRect, op, 
+                                                                   curClip.fDoAA);
             break;
         case kPath_ClipType:
-            curClip.fOffset = picRecord->recordClipPath(curClip.fGeom.fPathID, op,
-                                                        curClip.fDoAA);
+            curClip.fOffset = mgr->getPicRecord()->recordClipPath(curClip.fGeom.fPathID, op, 
+                                                                  curClip.fDoAA);
             break;
         case kRegion_ClipType:
-            curClip.fOffset = picRecord->recordClipRegion(*curClip.fGeom.fRegion, op);
+            curClip.fOffset = mgr->getPicRecord()->recordClipRegion(*curClip.fGeom.fRegion, op);
             break;
         default:
             SkASSERT(0);
@@ -117,6 +123,10 @@ SkMatrixClipStateMgr::SkMatrixClipStateMgr()
                        fMatrixClipStackStorage,
                        sizeof(fMatrixClipStackStorage))
     , fCurOpenStateID(kIdentityWideOpenStateID) {
+
+    // The first slot in the matrix dictionary is reserved for the identity matrix
+    fMatrixDict.append()->reset();
+
     fCurMCState = (MatrixClipState*)fMatrixClipStack.push_back();
     new (fCurMCState) MatrixClipState(NULL, 0);    // balanced in restore()
 }
@@ -215,19 +225,19 @@ bool SkMatrixClipStateMgr::call(CallType callType) {
     SkDeque::F2BIter iter(fMatrixClipStack);
     bool firstClip = true;
 
-    SkMatrix curMat = SkMatrix::I();
+    int curMatID = kIdentityMatID;
     for (const MatrixClipState* state = (const MatrixClipState*) iter.next();
          state != NULL;
          state = (const MatrixClipState*) iter.next()) {
-         state->fClipInfo->writeClip(&curMat, fPicRecord, &firstClip);
+         state->fClipInfo->writeClip(&curMatID, this, &firstClip);
     }
 
     // write out matrix
-    if (!fCurMCState->fMatrixInfo->fMatrix.isIdentity()) {
+    if (kIdentityMatID != fCurMCState->fMatrixInfo->getID(this)) {
         // TODO: writing out the delta matrix here is an artifact of the writing
         // out of the entire clip stack (with its matrices). Ultimately we will
         // write out the CTM here when the clip state is collapsed to a single path.
-        WriteDeltaMat(fPicRecord, curMat, fCurMCState->fMatrixInfo->fMatrix);
+        this->writeDeltaMat(curMatID, fCurMCState->fMatrixInfo->getID(this));
     }
 
     SkDEBUGCODE(this->validate();)
@@ -257,3 +267,12 @@ void SkMatrixClipStateMgr::validate() {
     }
 }
 #endif
+
+int SkMatrixClipStateMgr::addMatToDict(const SkMatrix& mat) {
+    if (mat.isIdentity()) {
+        return kIdentityMatID;
+    }
+
+    *fMatrixDict.append() = mat;
+    return fMatrixDict.count()-1;
+}
diff --git a/src/core/SkMatrixClipStateMgr.h b/src/core/SkMatrixClipStateMgr.h
index 1f1d52cf4b..f74491d2ab 100644
--- a/src/core/SkMatrixClipStateMgr.h
+++ b/src/core/SkMatrixClipStateMgr.h
@@ -13,6 +13,7 @@
 #include "SkRRect.h"
 #include "SkTypes.h"
 #include "SkTArray.h"
+#include "SkTDArray.h"
 
 class SkPictureRecord;
 class SkWriter32;
@@ -51,13 +52,59 @@ class SkWriter32;
 class SkMatrixClipStateMgr {
 public:
     static const int32_t kIdentityWideOpenStateID = 0;
+    static const int kIdentityMatID = 0;
 
     class MatrixClipState {
     public:
         class MatrixInfo {
         public:
+            void reset() {
+                fMatrixID = kIdentityMatID;
+                fMatrix.reset();
+            }
+
+            bool preTranslate(SkScalar dx, SkScalar dy) {
+                fMatrixID = -1;
+                return fMatrix.preTranslate(dx, dy);
+            }
+
+            bool preScale(SkScalar sx, SkScalar sy) {
+                fMatrixID = -1;
+                return fMatrix.preScale(sx, sy);
+            }
+
+            bool preRotate(SkScalar degrees) {
+                fMatrixID = -1;
+                return fMatrix.preRotate(degrees);
+            }
+
+            bool preSkew(SkScalar sx, SkScalar sy) {
+                fMatrixID = -1;
+                return fMatrix.preSkew(sx, sy);
+            }
+
+            bool preConcat(const SkMatrix& matrix) {
+                fMatrixID = -1;
+                return fMatrix.preConcat(matrix);
+            }
+
+            void setMatrix(const SkMatrix& matrix) {
+                fMatrixID = -1;
+                fMatrix = matrix;
+            }
+
+            int getID(SkMatrixClipStateMgr* mgr) {
+                if (fMatrixID >= 0) {
+                    return fMatrixID;
+                }
+
+                fMatrixID = mgr->addMatToDict(fMatrix);
+                return fMatrixID;
+            }
+
+        private:
             SkMatrix fMatrix;
-            // TODO: add an internal dictionary and an ID here
+            int      fMatrixID;
         };
 
         class ClipInfo : public SkNoncopyable {
@@ -67,13 +114,13 @@ public:
             bool clipRect(const SkRect& rect,
                           SkRegion::Op op,
                           bool doAA,
-                          const SkMatrix& matrix) {
+                          int matrixID) {
                 ClipOp& newClip = fClips.push_back();
                 newClip.fClipType = kRect_ClipType;
                 newClip.fGeom.fRRect.setRect(rect);   // storing the clipRect in the RRect
                 newClip.fOp = op;
                 newClip.fDoAA = doAA;
-                newClip.fMatrix = matrix;
+                newClip.fMatrixID = matrixID;
                 newClip.fOffset = kInvalidJumpOffset;
                 return false;
             }
@@ -81,13 +128,13 @@ public:
             bool clipRRect(const SkRRect& rrect,
                            SkRegion::Op op,
                            bool doAA,
-                           const SkMatrix& matrix) {
+                           int matrixID) {
                 ClipOp& newClip = fClips.push_back();
                 newClip.fClipType = kRRect_ClipType;
                 newClip.fGeom.fRRect = rrect;
                 newClip.fOp = op;
                 newClip.fDoAA = doAA;
-                newClip.fMatrix = matrix;
+                newClip.fMatrixID = matrixID;
                 newClip.fOffset = kInvalidJumpOffset;
                 return false;
             }
@@ -96,13 +143,13 @@ public:
                           const SkPath& path,
                           SkRegion::Op op,
                           bool doAA,
-                          const SkMatrix& matrix);
+                          int matrixID);
             bool clipRegion(SkPictureRecord* picRecord,
                             const SkRegion& region,
                             SkRegion::Op op,
-                            const SkMatrix& matrix);
-            void writeClip(SkMatrix* curMat,
-                           SkPictureRecord* picRecord,
+                            int matrixID);
+            void writeClip(int* curMatID, 
+                           SkMatrixClipStateMgr* mgr,
                            bool* overrideFirstOp);
             void fillInSkips(SkWriter32* writer, int32_t restoreOffset);
 
@@ -148,8 +195,7 @@ public:
                 SkRegion::Op fOp;
 
                 // The CTM in effect when this clip call was issued
-                // TODO: add an internal dictionary and replace with ID
-                SkMatrix     fMatrix;
+                int          fMatrixID;
 
                 // The offset of this clipOp's "jump-to-offset" location in the skp.
                 // -1 means the offset hasn't been written.
@@ -169,7 +215,7 @@ public:
             if (NULL == prev) {
                 fLayerID = 0;
 
-                fMatrixInfoStorage.fMatrix.reset();
+                fMatrixInfoStorage.reset();
                 fMatrixInfo = &fMatrixInfoStorage;
                 fClipInfo = &fClipInfoStorage;  // ctor handles init of fClipInfoStorage
 
@@ -237,6 +283,8 @@ public:
         fPicRecord = picRecord;
     }
 
+    SkPictureRecord* getPicRecord() { return fPicRecord; }
+
     // TODO: need to override canvas' getSaveCount. Right now we pass the
     // save* and restore calls on to the base SkCanvas in SkPictureRecord but
     // this duplicates effort.
@@ -254,56 +302,56 @@ public:
 
     bool translate(SkScalar dx, SkScalar dy) {
         this->call(kMatrix_CallType);
-        return fCurMCState->fMatrixInfo->fMatrix.preTranslate(dx, dy);
+        return fCurMCState->fMatrixInfo->preTranslate(dx, dy);
     }
 
     bool scale(SkScalar sx, SkScalar sy) {
         this->call(kMatrix_CallType);
-        return fCurMCState->fMatrixInfo->fMatrix.preScale(sx, sy);
+        return fCurMCState->fMatrixInfo->preScale(sx, sy);
     }
 
     bool rotate(SkScalar degrees) {
         this->call(kMatrix_CallType);
-        return fCurMCState->fMatrixInfo->fMatrix.preRotate(degrees);
+        return fCurMCState->fMatrixInfo->preRotate(degrees);
     }
 
     bool skew(SkScalar sx, SkScalar sy) {
         this->call(kMatrix_CallType);
-        return fCurMCState->fMatrixInfo->fMatrix.preSkew(sx, sy);
+        return fCurMCState->fMatrixInfo->preSkew(sx, sy);
     }
 
     bool concat(const SkMatrix& matrix) {
         this->call(kMatrix_CallType);
-        return fCurMCState->fMatrixInfo->fMatrix.preConcat(matrix);
+        return fCurMCState->fMatrixInfo->preConcat(matrix);
     }
 
     void setMatrix(const SkMatrix& matrix) {
         this->call(kMatrix_CallType);
-        fCurMCState->fMatrixInfo->fMatrix = matrix;
+        fCurMCState->fMatrixInfo->setMatrix(matrix);
     }
 
     bool clipRect(const SkRect& rect, SkRegion::Op op, bool doAA) {
         this->call(SkMatrixClipStateMgr::kClip_CallType);
         return fCurMCState->fClipInfo->clipRect(rect, op, doAA,
-                                                fCurMCState->fMatrixInfo->fMatrix);
+                                                fCurMCState->fMatrixInfo->getID(this));
     }
 
     bool clipRRect(const SkRRect& rrect, SkRegion::Op op, bool doAA) {
         this->call(SkMatrixClipStateMgr::kClip_CallType);
         return fCurMCState->fClipInfo->clipRRect(rrect, op, doAA,
-                                                 fCurMCState->fMatrixInfo->fMatrix);
+                                                 fCurMCState->fMatrixInfo->getID(this));
     }
 
     bool clipPath(const SkPath& path, SkRegion::Op op, bool doAA) {
         this->call(SkMatrixClipStateMgr::kClip_CallType);
         return fCurMCState->fClipInfo->clipPath(fPicRecord, path, op, doAA,
-                                                fCurMCState->fMatrixInfo->fMatrix);
+                                                fCurMCState->fMatrixInfo->getID(this));
     }
 
     bool clipRegion(const SkRegion& region, SkRegion::Op op) {
         this->call(SkMatrixClipStateMgr::kClip_CallType);
         return fCurMCState->fClipInfo->clipRegion(fPicRecord, region, op,
-                                                  fCurMCState->fMatrixInfo->fMatrix);
+                                                  fCurMCState->fMatrixInfo->getID(this));
     }
 
     bool call(CallType callType);
@@ -329,15 +377,28 @@ protected:
     SkDeque          fMatrixClipStack;
     MatrixClipState* fCurMCState;
 
+    // This dictionary doesn't actually de-duplicate the matrices (except for the
+    // identity matrix). It merely stores the matrices and allows them to be looked
+    // up by ID later. The de-duplication mainly falls upon the matrix/clip stack 
+    // which stores the ID so a revisited clip/matrix (via popping the stack) will 
+    // use the same ID.
+    SkTDArray<SkMatrix> fMatrixDict;
+
     // The MCStateID of the state currently in effect in the byte stream. 0 if none.
     int32_t          fCurOpenStateID;
 
     SkDEBUGCODE(void validate();)
 
-    static void WriteDeltaMat(SkPictureRecord* picRecord,
-                              const SkMatrix& current,
-                              const SkMatrix& desired);
+    void writeDeltaMat(int currentMatID, int desiredMatID);
     static int32_t   NewMCStateID();
+
+    // TODO: add stats to check if the dictionary really does
+    // reduce the size of the SkPicture.
+    int addMatToDict(const SkMatrix& mat);
+    const SkMatrix& lookupMat(int index) {
+        SkASSERT(index >= 0 && index < fMatrixDict.count());
+        return fMatrixDict[index];
+    }
 };
 
 #endif