Use new SkGlyphIDSet - v2

Add bzero to make msan and valgrind happy.

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

1 files changed, 124 insertions, 98 deletions

diff --git a/src/core/SkGlyphRun.cpp b/src/core/SkGlyphRun.cpp
index e7bab33ad8..6791cf3ab2 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,152 @@ 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;
+        // If the following bzero becomes a performance problem, the memory can be marked as
+        // initialized for valgrind and msan.
+        // valgrind = VALGRIND_MAKE_MEM_DEFINED(fUniverseToUnique, universeSize * sizeof(SkGlyphID))
+        // msan = sk_msan_assert_initialized(fUniverseToUnique, universeSize * sizeof(SkGlyphID))
+        sk_bzero(fUniverseToUnique, universeSize * sizeof(SkGlyphID));
+    }
+
+    // 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);
+        sk_bzero(fUniverseToUnique, 4096 * sizeof(SkGlyphID));
+        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 +225,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 +235,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 +263,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);
 }