Glyph search of desperation

Change-Id: I0ae768c5517c3ee3f6822fea0926b3f27214a0e4
Reviewed-on: https://skia-review.googlesource.com/132260
Commit-Queue: Herb Derby <herb@google.com>
Reviewed-by: Mike Klein <mtklein@google.com>

5 files changed, 150 insertions, 2 deletions

diff --git a/src/core/SkGlyph.h b/src/core/SkGlyph.h
index 307042f724..2381c3e9bc 100644
--- a/src/core/SkGlyph.h
+++ b/src/core/SkGlyph.h
@@ -195,6 +195,20 @@ public:
 
     void toMask(SkMask* mask) const;
 
+    void copyImageData(const SkGlyph& from, SkArenaAlloc* alloc) {
+        fMaskFormat = from.fMaskFormat;
+        fWidth = from.fWidth;
+        fHeight = from.fHeight;
+        fLeft = from.fLeft;
+        fTop = from.fTop;
+        fForceBW = from.fForceBW;
+
+        if (from.fImage != nullptr) {
+            auto imageSize = this->allocImage(alloc);
+            memcpy(fImage, from.fImage, imageSize);
+        }
+    }
+
     class HashTraits {
     public:
         static SkPackedGlyphID GetKey(const SkGlyph& glyph) {
diff --git a/src/core/SkGlyphCache.cpp b/src/core/SkGlyphCache.cpp
index 3734b96ee2..79e714758c 100644
--- a/src/core/SkGlyphCache.cpp
+++ b/src/core/SkGlyphCache.cpp
@@ -155,6 +155,12 @@ SkGlyph* SkGlyphCache::lookupByPackedGlyphID(SkPackedGlyphID packedGlyphID, Metr
     } else {
         if (type == kFull_MetricsType && glyph->isJustAdvance()) {
            fScalerContext->getMetrics(glyph);
+
+           // Just in case someone allocated an image in the getMetrics call, be sure to account
+           // for the memory used.
+           if (glyph->fImage != nullptr) {
+               fMemoryUsed += glyph->computeImageSize();
+           }
         }
     }
     return glyph;
diff --git a/src/core/SkStrikeCache.cpp b/src/core/SkStrikeCache.cpp
index 2e5bd89b79..20ed6e772c 100644
--- a/src/core/SkStrikeCache.cpp
+++ b/src/core/SkStrikeCache.cpp
@@ -101,6 +101,16 @@ SkExclusiveStrikePtr SkStrikeCache::FindStrikeExclusive(const SkDescriptor& desc
     return get_globals().findStrikeExclusive(desc);
 }
 
+bool SkStrikeCache::DesperationSearchForImage(
+        const SkDescriptor& desc, SkGlyph* glyph, SkArenaAlloc* arena) {
+    return get_globals().desperationSearchForImage(desc, glyph, arena);
+}
+
+bool SkStrikeCache::DesperationSearchForPath(
+        const SkDescriptor& desc, SkGlyphID glyphID, SkPath* path) {
+    return get_globals().desperationSearchForPath(desc, glyphID, path);
+}
+
 std::unique_ptr<SkScalerContext> SkStrikeCache::CreateScalerContext(
         const SkDescriptor& desc,
         const SkScalerContextEffects& effects,
@@ -255,6 +265,98 @@ SkExclusiveStrikePtr SkStrikeCache::findStrikeExclusive(const SkDescriptor& desc
     return SkExclusiveStrikePtr(nullptr);
 }
 
+static bool loose_compare (const SkDescriptor& lhs, const SkDescriptor& rhs) {
+    uint32_t size;
+    auto ptr = lhs.findEntry(kRec_SkDescriptorTag, &size);
+    SkScalerContextRec lhsRec;
+    std::memcpy(&lhsRec, ptr, size);
+
+    ptr = rhs.findEntry(kRec_SkDescriptorTag, &size);
+    SkScalerContextRec rhsRec;
+    std::memcpy(&rhsRec, ptr, size);
+
+    // If these don't match, there's no way we can use these strikes interchangeably.
+    // TODO: make sure we don't search other renderer's caches.
+    return
+        lhsRec.fFontID == rhsRec.fFontID &&
+        lhsRec.fTextSize == rhsRec.fTextSize &&
+        lhsRec.fPreScaleX == rhsRec.fPreScaleX &&
+        lhsRec.fPreSkewX == rhsRec.fPreSkewX &&
+        lhsRec.fPost2x2[0][0] == rhsRec.fPost2x2[0][0] &&
+        lhsRec.fPost2x2[0][1] == rhsRec.fPost2x2[0][1] &&
+        lhsRec.fPost2x2[1][0] == rhsRec.fPost2x2[1][0] &&
+        lhsRec.fPost2x2[1][1] == rhsRec.fPost2x2[1][1];
+}
+
+bool SkStrikeCache::desperationSearchForImage(
+        const SkDescriptor& desc, SkGlyph* glyph, SkArenaAlloc* alloc) {
+    SkAutoExclusive ac(fLock);
+
+    SkGlyphID glyphID = glyph->getGlyphID();
+    SkFixed targetSubX = glyph->getSubXFixed(),
+            targetSubY = glyph->getSubYFixed();
+
+    // We don't have this glyph with the exact subpixel positioning,
+    // but we might have this glyph with another subpixel position... search them all.
+    for (Node* node = internalGetHead(); node != nullptr; node = node->fNext) {
+        if (loose_compare(node->fCache.getDescriptor(), desc)) {
+            auto targetGlyphID = SkPackedGlyphID(glyphID, targetSubX, targetSubY);
+            if (node->fCache.isGlyphCached(glyphID, targetSubX, targetSubY)) {
+                SkGlyph* from = node->fCache.getRawGlyphByID(targetGlyphID);
+                if (from->fImage != nullptr) {
+                    // This desperate-match node may disappear as soon as we drop fLock, so we
+                    // need to copy the glyph from node into this strike, including a
+                    // deep copy of the mask.
+                    glyph->copyImageData(*from, alloc);
+                    return true;
+                }
+            }
+
+            // We don't have this glyph with the exact subpixel positioning,
+            // but we might have this glyph with another subpixel position... search them all.
+            for (SkFixed subY = 0; subY < SK_Fixed1; subY += SK_FixedQuarter) {
+                for (SkFixed subX = 0; subX < SK_Fixed1; subX += SK_FixedQuarter) {
+                    if (node->fCache.isGlyphCached(glyphID, subX, subY)) {
+                        SkGlyph* from =
+                                node->fCache.getRawGlyphByID(SkPackedGlyphID(glyphID, subX, subY));
+                        if (from->fImage != nullptr) {
+                            glyph->copyImageData(*from, alloc);
+                            return true;
+                        }
+                    }
+                }
+            }
+        }
+    }
+    return false;
+}
+
+bool SkStrikeCache::desperationSearchForPath(
+        const SkDescriptor& desc, SkGlyphID glyphID, SkPath* path) {
+    SkAutoExclusive ac(fLock);
+
+    // The following is wrong there is subpixel positioning with paths...
+    // Paths are only ever at sub-pixel position (0,0), so we can just try that directly rather
+    // than try our packed position first then search all others on failure like for masks.
+    //
+    // This will have to search the sub-pixel positions too.
+    // There is also a problem with accounting for cache size with shared path data.
+    for (Node* node = internalGetHead(); node != nullptr; node = node->fNext) {
+        if (loose_compare(node->fCache.getDescriptor(), desc)) {
+            if (node->fCache.isGlyphCached(glyphID, 0, 0)) {
+                SkGlyph* from = node->fCache.getRawGlyphByID(SkPackedGlyphID(glyphID));
+                if (from->fPathData->fPath != nullptr) {
+                    // We can just copy the path out by value here, so no need to worry
+                    // about the lifetime of this desperate-match node.
+                    *path = *from->fPathData->fPath;
+                    return true;
+                }
+            }
+        }
+    }
+    return false;
+}
+
 SkExclusiveStrikePtr SkStrikeCache::CreateStrikeExclusive(
         const SkDescriptor& desc,
         std::unique_ptr<SkScalerContext> scaler,
diff --git a/src/core/SkStrikeCache.h b/src/core/SkStrikeCache.h
index f2c9820799..da984cce13 100644
--- a/src/core/SkStrikeCache.h
+++ b/src/core/SkStrikeCache.h
@@ -67,8 +67,15 @@ public:
         Node* fNode;
     };
 
+
     static ExclusiveStrikePtr FindStrikeExclusive(const SkDescriptor&);
 
+    static bool DesperationSearchForImage(
+            const SkDescriptor& desc, SkGlyph* glyph, SkArenaAlloc* arena);
+
+    static bool DesperationSearchForPath(
+            const SkDescriptor& desc, SkGlyphID glyphID, SkPath* path);
+
     static ExclusiveStrikePtr CreateStrikeExclusive(
             const SkDescriptor& desc,
             std::unique_ptr<SkScalerContext> scaler,
@@ -103,6 +110,11 @@ public:
     void attachNode(Node* node);
     ExclusiveStrikePtr findStrikeExclusive(const SkDescriptor&);
 
+    // Routines to find suitable data when working in a remote cache situation. These are
+    // suitable as substitutes for similar calls in SkScalerContext.
+    bool desperationSearchForImage(const SkDescriptor& desc, SkGlyph* glyph, SkArenaAlloc* alloc);
+    bool desperationSearchForPath(const SkDescriptor& desc, SkGlyphID glyphID, SkPath* path);
+
     void purgeAll(); // does not change budget
 
     int getCacheCountLimit() const;
diff --git a/src/core/SkTypeface_remote.cpp b/src/core/SkTypeface_remote.cpp
index 472c009dcc..9388b16ef4 100644
--- a/src/core/SkTypeface_remote.cpp
+++ b/src/core/SkTypeface_remote.cpp
@@ -38,8 +38,15 @@ void SkScalerContextProxy::generateMetrics(SkGlyph* glyph) {
         SkDebugf("GlyphCacheMiss generateMetrics: %s\n", this->getRec().dump().c_str());
     }
 
+    // Since the scaler context is being called, we don't have the needed data. Go look through
+    // looking for a suitable substitute before failing.
+    auto desc = SkScalerContext::DescriptorGivenRecAndEffects(this->getRec(), this->getEffects());
+    SkStrikeCache::DesperationSearchForImage(*desc, glyph, &fAlloc);
+
+    if (glyph->fMaskFormat == MASK_FORMAT_UNKNOWN) {
+        glyph->zeroMetrics();
+    }
     fDiscardableManager->notifyCacheMiss(SkStrikeClient::CacheMissType::kGlyphMetrics);
-    glyph->zeroMetrics();
 }
 
 void SkScalerContextProxy::generateImage(const SkGlyph& glyph) {
@@ -48,6 +55,8 @@ void SkScalerContextProxy::generateImage(const SkGlyph& glyph) {
         SkDebugf("GlyphCacheMiss generateImage: %s\n", this->getRec().dump().c_str());
     }
 
+    // There is no desperation search here, because if there was an image to be found it was
+    // copied over with the metrics search.
     fDiscardableManager->notifyCacheMiss(SkStrikeClient::CacheMissType::kGlyphImage);
 }
 
@@ -56,9 +65,13 @@ bool SkScalerContextProxy::generatePath(SkGlyphID glyphID, SkPath* path) {
     if (this->getProxyTypeface()->isLogging()) {
         SkDebugf("GlyphCacheMiss generatePath: %s\n", this->getRec().dump().c_str());
     }
+    // Since the scaler context is being called, we don't have the needed data. Go look through
+    // looking for a suitable substitute before failing.
+    auto desc = SkScalerContext::DescriptorGivenRecAndEffects(this->getRec(), this->getEffects());
+    bool foundPath = SkStrikeCache::DesperationSearchForPath(*desc, glyphID, path);
 
     fDiscardableManager->notifyCacheMiss(SkStrikeClient::CacheMissType::kGlyphPath);
-    return false;
+    return foundPath;
 }
 
 void SkScalerContextProxy::generateFontMetrics(SkPaint::FontMetrics* metrics) {
@@ -69,6 +82,7 @@ void SkScalerContextProxy::generateFontMetrics(SkPaint::FontMetrics* metrics) {
         SkDEBUGCODE(SkStrikeCache::Dump());
     }
 
+    // Font metrics aren't really used for render, so just zero out the data and return.
     fDiscardableManager->notifyCacheMiss(SkStrikeClient::CacheMissType::kFontMetrics);
     sk_bzero(metrics, sizeof(*metrics));
 }