Use new SkGlyphIDSet

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

3 files changed, 168 insertions, 144 deletions

diff --git a/src/core/SkGlyphRun.cpp b/src/core/SkGlyphRun.cpp
index e7bab33ad8..a9ba900881 100644
--- a/src/core/SkGlyphRun.cpp
+++ b/src/core/SkGlyphRun.cpp
@@ -35,55 +35,6 @@ static SkTypeface::Encoding convert_encoding(SkPaint::TextEncoding encoding) {
 }
 }  // namespace
 
-// -- SkGlyphSet ----------------------------------------------------------------------------------
-uint32_t SkGlyphSet::uniqueSize() {
-    // The size is how big the vector is grown since being passed into reuse.
-    return fUniqueGlyphIDs->size() - fStartOfUniqueIDs;
-}
-
-uint16_t SkGlyphSet::add(SkGlyphID glyphID) {
-    static constexpr SkGlyphID  kUndefGlyph{0};
-
-    if (glyphID >= fUniverseSize) {
-        glyphID = kUndefGlyph;
-    }
-
-    if (glyphID >= fIndices.size()) {
-        fIndices.resize(glyphID + 1);
-    }
-
-    auto index = fIndices[glyphID];
-
-    // Remember we start at the end of what ever was passed in.
-    if (index < this->uniqueSize() && (*fUniqueGlyphIDs)[fStartOfUniqueIDs + index] == glyphID) {
-        return index;
-    }
-
-    uint16_t newIndex = SkTo<uint16_t>(this->uniqueSize());
-    fUniqueGlyphIDs->push_back(glyphID);
-    fIndices[glyphID] = newIndex;
-    return newIndex;
-}
-
-void SkGlyphSet::reuse(uint32_t glyphUniverseSize, std::vector<SkGlyphID>* uniqueGlyphIDs) {
-    SkASSERT(glyphUniverseSize <= (1 << 16));
-    fUniverseSize = glyphUniverseSize;
-    fUniqueGlyphIDs = uniqueGlyphIDs;
-
-    // Capture the vector end to act as the start of a new unique id vector.
-    fStartOfUniqueIDs = uniqueGlyphIDs->size();
-
-    // If we're hanging onto these arrays for a long time, we don't want their size to drift
-    // endlessly upwards. It's unusual to see a typeface with more than 4096 possible glyphs.
-    if (glyphUniverseSize < 4096 && fIndices.size() > 4096) {
-        fIndices.resize(4096);
-        fIndices.shrink_to_fit();
-    }
-
-    // No need to clear fIndices here... SkGlyphSet's set insertion algorithm is designed to work
-    // correctly even when the fIndexes buffer is uninitialized!
-}
-
 // -- SkGlyphRun -----------------------------------------------------------------------------------
 SkGlyphRun::SkGlyphRun(SkPaint&& runPaint,
                        SkSpan<const uint16_t> denseIndices,
@@ -118,83 +69,146 @@ void SkGlyphRun::temporaryShuntToCallback(TemporaryShuntCallback callback) {
     callback(fTemporaryShuntGlyphIDs.size(), bytes, pos);
 }
 
+// -- SkGlyphIDSet ---------------------------------------------------------------------------------
+// A faster set implementation that does not need any initialization, and reading the set items
+// is order the number of items, and not the size of the universe.
+// This implementation is based on the paper by Briggs and Torczon, "An Efficient Representation
+// for Sparse Sets"
+//
+// This implementation assumes that the unique glyphs added are appended to a vector that may
+// already have unique glyph from a previous computation. This allows the packing of multiple
+// UniqueID sequences in a single vector.
+SkSpan<const SkGlyphID> SkGlyphIDSet::uniquifyGlyphIDs(
+        uint32_t universeSize,
+        SkSpan<const SkGlyphID> glyphIDs,
+        SkGlyphID* uniqueGlyphIDs,
+        uint16_t* denseIndices) {
+    static constexpr SkGlyphID  kUndefGlyph{0};
+
+    if (universeSize > fUniverseToUniqueSize) {
+        fUniverseToUnique.reset(universeSize);
+        fUniverseToUniqueSize = universeSize;
+    }
+
+    // No need to clear fUniverseToUnique here... the set insertion algorithm is designed to work
+    // correctly even when the fUniverseToUnique buffer is uninitialized!
+
+    size_t uniqueSize = 0;
+    size_t denseIndicesCursor = 0;
+    for (auto glyphID : glyphIDs) {
+
+        // If the glyphID is not in range then it is the undefined glyph.
+        if (glyphID >= universeSize) {
+            glyphID = kUndefGlyph;
+        }
+
+        // The index into the unique ID vector.
+        auto uniqueIndex = fUniverseToUnique[glyphID];
+
+        if (uniqueIndex >= uniqueSize || uniqueGlyphIDs[uniqueIndex] != glyphID) {
+            uniqueIndex = SkTo<uint16_t>(uniqueSize);
+            uniqueGlyphIDs[uniqueSize] = glyphID;
+            fUniverseToUnique[glyphID] = uniqueIndex;
+            uniqueSize += 1;
+        }
+
+        denseIndices[denseIndicesCursor++] = uniqueIndex;
+    }
+
+    // If we're hanging onto these arrays for a long time, we don't want their size to drift
+    // endlessly upwards. It's unusual to see a typeface with more than 4096 possible glyphs.
+    if (fUniverseToUniqueSize > 4096) {
+        fUniverseToUnique.reset(4096);
+        fUniverseToUniqueSize = 4096;
+    }
+
+    return SkSpan<const SkGlyphID>(uniqueGlyphIDs, uniqueSize);
+}
+
 // -- SkGlyphRunBuilder ----------------------------------------------------------------------------
 void SkGlyphRunBuilder::prepareDrawText(
         const SkPaint& paint, const void* bytes, size_t byteLength, SkPoint origin) {
-    this->initialize();
+    auto glyphIDs = textToGlyphIDs(paint, bytes, byteLength);
+    this->initialize(glyphIDs.size());
     SkSpan<const char> originalText((const char*)bytes, byteLength);
     if (paint.getTextEncoding() != SkPaint::kUTF8_TextEncoding) {
         originalText = SkSpan<const char>();
     }
-    this->drawText(paint, bytes, byteLength, origin, originalText, SkSpan<const uint32_t>());
+    this->drawText(paint, glyphIDs, origin, originalText, SkSpan<const uint32_t>());
 }
 
 void SkGlyphRunBuilder::prepareDrawPosTextH(const SkPaint& paint, const void* bytes,
                                             size_t byteLength, const SkScalar* xpos,
                                             SkScalar constY) {
-    this->initialize();
+    auto glyphIDs = textToGlyphIDs(paint, bytes, byteLength);
+    this->initialize(glyphIDs.size());
     this->drawPosTextH(
-            paint, bytes, byteLength, xpos, constY, SkSpan<const char>(), SkSpan<const uint32_t>());
+            paint, glyphIDs, xpos, constY, SkSpan<const char>(), SkSpan<const uint32_t>());
 }
 
 void SkGlyphRunBuilder::prepareDrawPosText(const SkPaint& paint, const void* bytes,
                                            size_t byteLength, const SkPoint* pos) {
-    this->initialize();
-    this->drawPosText(paint, bytes, byteLength, pos,
-            SkSpan<const char>(), SkSpan<const uint32_t>());
+    auto glyphIDs = textToGlyphIDs(paint, bytes, byteLength);
+    this->initialize(glyphIDs.size());
+    this->drawPosText(paint, glyphIDs, pos, SkSpan<const char>(), SkSpan<const uint32_t>());
 }
 
 SkGlyphRun* SkGlyphRunBuilder::useGlyphRun() {
     return &fScratchGlyphRun;
 }
 
-void SkGlyphRunBuilder::initialize() {
+void SkGlyphRunBuilder::initialize(size_t totalRunSize) {
     fUniqueID = 0;
-    fDenseIndex.clear();
-    fPositions.clear();
-    fUniqueGlyphIDs.clear();
+
+    // Using resize is temporary until simpler buffers are in place.
+    fDenseIndex.resize(totalRunSize);
+    fPositions.resize(totalRunSize);
+    fUniqueGlyphIDs.resize(totalRunSize);
 
     // Be sure to clean up the last run before we reuse it.
     fScratchGlyphRun.~SkGlyphRun();
 }
 
-void SkGlyphRunBuilder::addDenseAndUnique(
+SkSpan<const SkGlyphID> SkGlyphRunBuilder::textToGlyphIDs(
         const SkPaint& paint, const void* bytes, size_t byteLength) {
-
-    size_t runSize = 0;
-    SkGlyphID* glyphIDs = nullptr;
     auto encoding = paint.getTextEncoding();
-    auto typeface = SkPaintPriv::GetTypefaceOrDefault(paint);
     if (encoding != SkPaint::kGlyphID_TextEncoding) {
         auto tfEncoding = convert_encoding(encoding);
         int utfSize = SkUTFN_CountUnichars(tfEncoding, bytes, byteLength);
         if (utfSize > 0) {
-            runSize = SkTo<size_t>(utfSize);
+            size_t runSize = SkTo<size_t>(utfSize);
             fScratchGlyphIDs.resize(runSize);
+            auto typeface = SkPaintPriv::GetTypefaceOrDefault(paint);
             typeface->charsToGlyphs(bytes, tfEncoding, fScratchGlyphIDs.data(), runSize);
-            glyphIDs = fScratchGlyphIDs.data();
+            return SkSpan<const SkGlyphID>{fScratchGlyphIDs};
+        } else {
+            return SkSpan<const SkGlyphID>();
         }
     } else {
-        runSize = byteLength / 2;
-        glyphIDs = (SkGlyphID*)bytes;
+        return SkSpan<const SkGlyphID>((const SkGlyphID*)bytes, byteLength / 2);
     }
+}
 
-    // TODO: Remove when glyphIds are passed back.
-    fGlyphIDs = glyphIDs;
-
-    SkASSERT(glyphIDs != nullptr);
-
-    if (runSize > 0) {
-        fGlyphSet.reuse(typeface->countGlyphs(), &fUniqueGlyphIDs);
-        for (size_t i = 0; i < runSize; i++) {
-            fDenseIndex.push_back(fGlyphSet.add(glyphIDs[i]));
-        }
+SkSpan<const SkGlyphID> SkGlyphRunBuilder::addDenseAndUnique(
+        const SkPaint& paint,
+        SkSpan<const SkGlyphID> glyphIDs) {
+    SkSpan<const SkGlyphID> uniquifiedGlyphIDs;
+    if (!glyphIDs.empty()) {
+        auto typeface = SkPaintPriv::GetTypefaceOrDefault(paint);
+        auto glyphUniverseSize = typeface->countGlyphs();
+        uniquifiedGlyphIDs = fGlyphIDSet.uniquifyGlyphIDs(
+                glyphUniverseSize, glyphIDs, fUniqueGlyphIDs.data(), fDenseIndex.data());
     }
+
+    return uniquifiedGlyphIDs;
 }
 
 void SkGlyphRunBuilder::makeGlyphRun(
         const SkPaint& runPaint,
-        SkSpan<const char> text, SkSpan<const uint32_t> clusters) {
+        SkSpan<const SkGlyphID> glyphIDs,
+        SkSpan<const SkPoint> positions,
+        SkSpan<const char> text,
+        SkSpan<const uint32_t> clusters) {
 
     // Ignore empty runs.
     if (!fDenseIndex.empty()) {
@@ -205,8 +219,8 @@ void SkGlyphRunBuilder::makeGlyphRun(
         new ((void*)&fScratchGlyphRun) SkGlyphRun{
                 std::move(glyphRunPaint),
                 SkSpan<const uint16_t>{fDenseIndex},
-                SkSpan<const SkPoint>{fPositions},
-                SkSpan<const SkGlyphID>{fGlyphIDs, SkTo<ptrdiff_t>(fDenseIndex.size())},
+                positions,
+                glyphIDs,
                 SkSpan<const SkGlyphID>{fUniqueGlyphIDs},
                 text,
                 clusters
@@ -215,21 +229,21 @@ void SkGlyphRunBuilder::makeGlyphRun(
 }
 
 void SkGlyphRunBuilder::drawText(
-        const SkPaint& paint, const void* bytes, size_t byteLength, SkPoint origin,
+        const SkPaint& paint, SkSpan<const SkGlyphID> glyphIDs, SkPoint origin,
         SkSpan<const char> text, SkSpan<const uint32_t> clusters) {
 
-    this->addDenseAndUnique(paint, bytes, byteLength);
+    auto unqiueGlyphIDs = this->addDenseAndUnique(paint, glyphIDs);
 
     fScratchAdvances.resize(fUniqueGlyphIDs.size());
     {
         auto cache = SkStrikeCache::FindOrCreateStrikeExclusive(paint);
-        cache->getAdvances(SkSpan<const SkGlyphID>{fUniqueGlyphIDs}, fScratchAdvances.data());
+        cache->getAdvances(unqiueGlyphIDs, fScratchAdvances.data());
     }
 
     SkPoint endOfLastGlyph = origin;
 
     for (size_t i = 0; i < fDenseIndex.size(); i++) {
-        fPositions.push_back(endOfLastGlyph);
+        fPositions[i] = endOfLastGlyph;
         endOfLastGlyph += fScratchAdvances[fDenseIndex[i]];
     }
 
@@ -243,33 +257,39 @@ void SkGlyphRunBuilder::drawText(
         }
     }
 
-    this->makeGlyphRun(paint, text, clusters);
+    this->makeGlyphRun(paint, glyphIDs, SkSpan<const SkPoint>{fPositions}, text, clusters);
 }
 
-void SkGlyphRunBuilder::drawPosTextH(const SkPaint& paint, const void* bytes,
-                                     size_t byteLength, const SkScalar* xpos,
-                                     SkScalar constY,
+void SkGlyphRunBuilder::drawPosTextH(const SkPaint& paint, SkSpan<const SkGlyphID> glyphIDs,
+                                     const SkScalar* xpos, SkScalar constY,
                                      SkSpan<const char> text, SkSpan<const uint32_t> clusters) {
 
-    this->addDenseAndUnique(paint, bytes, byteLength);
+    // The dense indices are not used by the rest of the stack yet.
+    #ifdef SK_DEBUG
+        this->addDenseAndUnique(paint, glyphIDs);
+    #endif
 
     for (size_t i = 0; i < fDenseIndex.size(); i++) {
-        fPositions.push_back(SkPoint::Make(xpos[i], constY));
+        fPositions[i] = SkPoint::Make(xpos[i], constY);
     }
 
-    this->makeGlyphRun(paint, text, clusters);
+    this->makeGlyphRun(paint, glyphIDs, SkSpan<const SkPoint>{fPositions}, text, clusters);
 }
 
-void SkGlyphRunBuilder::drawPosText(const SkPaint& paint, const void* bytes,
-                                    size_t byteLength, const SkPoint* pos,
+void SkGlyphRunBuilder::drawPosText(const SkPaint& paint, SkSpan<const SkGlyphID> glyphIDs,
+                                    const SkPoint* pos,
                                     SkSpan<const char> text, SkSpan<const uint32_t> clusters) {
-    this->addDenseAndUnique(paint, bytes, byteLength);
+
+    // The dense indices are not used by the rest of the stack yet.
+    #ifdef SK_DEBUG
+        this->addDenseAndUnique(paint, glyphIDs);
+    #endif
 
     for (size_t i = 0; i < fDenseIndex.size(); i++) {
-        fPositions.push_back(pos[i]);
+        fPositions[i] = pos[i];
     }
 
-    this->makeGlyphRun(paint, text, clusters);
+    this->makeGlyphRun(paint, glyphIDs, SkSpan<const SkPoint>{fPositions}, text, clusters);
 }
 
 
diff --git a/src/core/SkGlyphRun.h b/src/core/SkGlyphRun.h
index 7788376c70..7c3a74860c 100644
--- a/src/core/SkGlyphRun.h
+++ b/src/core/SkGlyphRun.h
@@ -83,26 +83,14 @@ private:
     const SkPaint fRunPaint;
 };
 
-// A faster set implementation that does not need any initialization, and reading the set items
-// is order the number of items, and not the size of the universe.
-// This implementation is based on the paper by Briggs and Torczon, "An Efficient Representation
-// for Sparse Sets"
-//
-// This implementation assumes that the unique glyphs added are appended to a vector that may
-// already have unique glyph from a previous computation. This allows the packing of multiple
-// UniqueID sequences in a single vector.
-class SkGlyphSet {
+class SkGlyphIDSet {
 public:
-    SkGlyphSet() = default;
-    uint16_t add(SkGlyphID glyphID);
-    void reuse(uint32_t glyphUniverseSize, std::vector<SkGlyphID>* uniqueGlyphIDs);
-
+    SkSpan<const SkGlyphID> uniquifyGlyphIDs(
+            uint32_t universeSize, SkSpan<const SkGlyphID> glyphIDs,
+            SkGlyphID* uniqueGlyphIDs, uint16_t* denseindices);
 private:
-    uint32_t uniqueSize();
-    uint32_t                    fUniverseSize{0};
-    size_t                      fStartOfUniqueIDs{0};
-    std::vector<uint16_t>       fIndices;
-    std::vector<SkGlyphID>*     fUniqueGlyphIDs{nullptr};
+    size_t fUniverseToUniqueSize{0};
+    SkAutoTMalloc<uint16_t> fUniverseToUnique;
 };
 
 class SkGlyphRunBuilder {
@@ -115,25 +103,35 @@ public:
             const SkScalar xpos[], SkScalar constY);
     void prepareDrawPosText(
             const SkPaint& paint, const void* bytes, size_t byteLength, const SkPoint pos[]);
-    void prepareTextBlob(const SkPaint& paint, const SkTextBlob& blob, SkPoint origin);
 
     SkGlyphRun* useGlyphRun();
 
 private:
-    void initialize();
-    void addDenseAndUnique(const SkPaint& paint, const void* bytes, size_t byteLength);
+    void initialize(size_t totalRunSize);
+    SkSpan<const SkGlyphID> textToGlyphIDs(
+            const SkPaint& paint, const void* bytes, size_t byteLength);
+
+    // Returns the span of unique glyph IDs.
+    SkSpan<const SkGlyphID> addDenseAndUnique(
+            const SkPaint& paint,
+            SkSpan<const SkGlyphID> glyphIDs);
+
     void makeGlyphRun(
-            const SkPaint& runPaint, SkSpan<const char> text, SkSpan<const uint32_t> clusters);
+            const SkPaint& runPaint,
+            SkSpan<const SkGlyphID> glyphIDs,
+            SkSpan<const SkPoint> positions,
+            SkSpan<const char> text,
+            SkSpan<const uint32_t> clusters);
 
     void drawText(
-            const SkPaint& paint, const void* bytes, size_t byteLength, SkPoint origin,
+            const SkPaint& paint, SkSpan<const SkGlyphID> glyphIDs, SkPoint origin,
             SkSpan<const char> text, SkSpan<const uint32_t> clusters);
     void drawPosTextH(
-            const SkPaint& paint, const void* bytes, size_t byteLength,
+            const SkPaint& paint, SkSpan<const SkGlyphID> glyphIDs,
             const SkScalar* xpos, SkScalar constY,
             SkSpan<const char> text, SkSpan<const uint32_t> clusters);
     void drawPosText(
-            const SkPaint& paint, const void* bytes, size_t byteLength, const SkPoint* pos,
+            const SkPaint& paint, SkSpan<const SkGlyphID> glyphIDs, const SkPoint* pos,
             SkSpan<const char> text, SkSpan<const uint32_t> clusters);
 
     uint64_t fUniqueID{0};
@@ -141,7 +139,6 @@ private:
     std::vector<uint16_t> fDenseIndex;
     std::vector<SkPoint> fPositions;
     std::vector<SkGlyphID> fUniqueGlyphIDs;
-    SkGlyphID* fGlyphIDs{nullptr};
 
     // Used as a temporary for preparing using utfN text. This implies that only one run of
     // glyph ids will ever be needed because blobs are already glyph based.
@@ -155,7 +152,7 @@ private:
     SkGlyphRun fScratchGlyphRun;
 
     // Used for collecting the set of unique glyphs.
-    SkGlyphSet fGlyphSet;
+    SkGlyphIDSet fGlyphIDSet;
 };
 
 #endif  // SkGlyphRunInfo_DEFINED
diff --git a/tests/GlyphRunTest.cpp b/tests/GlyphRunTest.cpp
index 46b4715c61..0e0c441b75 100644
--- a/tests/GlyphRunTest.cpp
+++ b/tests/GlyphRunTest.cpp
@@ -11,25 +11,32 @@
 
 #include "Test.h"
 
-DEF_TEST(GlyphSetBasic, reporter) {
-    SkGlyphSet set;
-
-    std::vector<SkGlyphID> unique;
-
-    set.reuse(10, &unique);
-    REPORTER_ASSERT(reporter, set.add(7) == 0);
-    REPORTER_ASSERT(reporter, set.add(3) == 1);
-    set.reuse(10, &unique);
-    REPORTER_ASSERT(reporter, set.add(5) == 0);
-    REPORTER_ASSERT(reporter, set.add(8) == 1);
-    REPORTER_ASSERT(reporter, set.add(3) == 2);
-
-    REPORTER_ASSERT(reporter, unique.size() == 5);
-    REPORTER_ASSERT(reporter, unique[0] == 7);
-    REPORTER_ASSERT(reporter, unique[1] == 3);
-    REPORTER_ASSERT(reporter, unique[2] == 5);
-    REPORTER_ASSERT(reporter, unique[3] == 8);
-    REPORTER_ASSERT(reporter, unique[4] == 3);
+DEF_TEST(GlyphRunGlyphIDSetBasic, reporter) {
+    SkGlyphID glyphs[] = {100, 3, 240, 3, 234};
+    auto glyphIDs = SkSpan<const SkGlyphID>(glyphs, SK_ARRAY_COUNT(glyphs));
+    int universeSize = 1000;
+    SkGlyphID uniqueGlyphs[SK_ARRAY_COUNT(glyphs)];
+    uint16_t denseIndices[SK_ARRAY_COUNT(glyphs)];
+
+    SkGlyphIDSet gs;
+    auto uniqueGlyphIDs = gs.uniquifyGlyphIDs(universeSize, glyphIDs, uniqueGlyphs, denseIndices);
+
+    std::vector<SkGlyphID> test{uniqueGlyphIDs.begin(), uniqueGlyphIDs.end()};
+    std::sort(test.begin(), test.end());
+    auto newEnd = std::unique(test.begin(), test.end());
+    REPORTER_ASSERT(reporter, uniqueGlyphIDs.size() == newEnd - test.begin());
+    REPORTER_ASSERT(reporter, uniqueGlyphIDs.size() == 4);
+    {
+        uint16_t answer[] = {0, 1, 2, 1, 3};
+        REPORTER_ASSERT(reporter,
+                        std::equal(answer, std::end(answer), denseIndices));
+    }
+
+    {
+        SkGlyphID answer[] = {100, 3, 240, 234};
+        REPORTER_ASSERT(reporter,
+                        std::equal(answer, std::end(answer), uniqueGlyphs));
+    }
 }
 
 DEF_TEST(GlyphRunBasic, reporter) {