New more efficient run builder

A system for building glyph runs. In the future the builder will
only live in canvas, but it's internal structures facilitate
interacting with the cache a single glyph at a time. When all
the bulk code is in place, only runs will be passed around.

Passing the builder down the text draw stack is temporary.

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

1 files changed, 101 insertions, 138 deletions

diff --git a/src/core/SkGlyphRun.cpp b/src/core/SkGlyphRun.cpp
index 41f50134e9..ce4c907b5b 100644
--- a/src/core/SkGlyphRun.cpp
+++ b/src/core/SkGlyphRun.cpp
@@ -10,6 +10,7 @@
 #include <algorithm>
 #include <tuple>
 
+#include "SkDevice.h"
 #include "SkDraw.h"
 #include "SkGlyphCache.h"
 #include "SkMakeUnique.h"
@@ -19,8 +20,6 @@
 #include "SkStrikeCache.h"
 #include "SkUtils.h"
 
-namespace {
-
 static SkTypeface::Encoding convert_encoding(SkPaint::TextEncoding encoding) {
     switch (encoding) {
         case  SkPaint::kUTF8_TextEncoding: return SkTypeface::kUTF8_Encoding;
@@ -30,77 +29,68 @@ static SkTypeface::Encoding convert_encoding(SkPaint::TextEncoding encoding) {
     }
 }
 
-using Core = std::tuple<size_t,   std::unique_ptr<uint16_t[]>, std::vector<SkGlyphID>>;
-
-Core make_from_glyphids(
-        size_t glyphCount, const SkGlyphID* glyphs, SkGlyphID maxGlyphID, SkGlyphSet* glyphSet) {
-    if (glyphCount == 0) { return Core(0, nullptr, std::vector<SkGlyphID>()); }
-
-    glyphSet->reuse(maxGlyphID);
+// -- SkGlyphSet ----------------------------------------------------------------------------------
+uint16_t SkGlyphSet::add(SkGlyphID glyphID) {
+    static constexpr SkGlyphID  kUndefGlyph{0};
 
-    auto denseIndex = skstd::make_unique_default<uint16_t[]>(glyphCount);
-    for (size_t i = 0; i < glyphCount; i++) {
-        denseIndex[i] = glyphSet->add(glyphs[i]);
+    if (glyphID >= fUniverseSize) {
+        glyphID = kUndefGlyph;
     }
 
-    return Core(glyphCount, std::move(denseIndex), glyphSet->uniqueGlyphIDs());
-}
-
-Core make_from_utfn(size_t byteLength, const void* utfN, const SkTypeface& typeface,
-                    SkTypeface::Encoding encoding, SkGlyphSet* glyphSet) {
-    auto count = SkUTFN_CountUnichars(encoding, utfN, byteLength);
-
-    if (count <= 0) {
-        return Core(0, nullptr, std::vector<SkGlyphID>());
+    if (glyphID >= fIndices.size()) {
+        fIndices.resize(glyphID + 1);
     }
 
-    auto glyphs = skstd::make_unique_default<SkGlyphID[]>(count);
-
-    // TODO: move to using cached version.
-    typeface.charsToGlyphs(utfN, encoding, glyphs.get(), count);
+    auto index = fIndices[glyphID];
+    if (index < fUniqueGlyphIDs->size() && (*fUniqueGlyphIDs)[index] == glyphID) {
+        return index;
+    }
 
-    return make_from_glyphids(count, glyphs.get(), typeface.countGlyphs(), glyphSet);
+    uint16_t newIndex = SkTo<uint16_t>(fUniqueGlyphIDs->size());
+    fUniqueGlyphIDs->push_back(glyphID);
+    fIndices[glyphID] = newIndex;
+    return newIndex;
 }
 
-Core make_core(const SkPaint& paint, const void* bytes, size_t byteLength, SkGlyphSet* glyphSet) {
-    auto encoding = paint.getTextEncoding();
-    auto typeface = SkPaintPriv::GetTypefaceOrDefault(paint);
-    if (encoding == SkPaint::kGlyphID_TextEncoding) {
-        return make_from_glyphids(
-                byteLength / 2, reinterpret_cast<const SkGlyphID*>(bytes),
-                typeface->countGlyphs(), glyphSet);
-    } else {
-        return make_from_utfn(byteLength, bytes, *typeface, convert_encoding(encoding), glyphSet);
+void SkGlyphSet::reuse(uint32_t glyphUniverseSize, std::vector<SkGlyphID>* uniqueGlyphIDs) {
+    SkASSERT(glyphUniverseSize <= (1 << 16));
+    fUniverseSize = glyphUniverseSize;
+    fUniqueGlyphIDs = uniqueGlyphIDs;
+    // 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 more than 256 unique glyphs used in a run,
+    // or a typeface with more than 4096 possible glyphs.
+    if (fUniqueGlyphIDs->size() > 256) {
+        fUniqueGlyphIDs->resize(256);
+        fUniqueGlyphIDs->shrink_to_fit();
     }
-}
+    fUniqueGlyphIDs->clear();
 
-}  // namespace
+    if (glyphUniverseSize < 4096 && fIndices.size() > 4096) {
+        fIndices.resize(4096);
+        fIndices.shrink_to_fit();
+    }
 
-SkGlyphRun SkGlyphRun::MakeFromDrawText(
-        const SkPaint& paint, const void* bytes, size_t byteLength,
-        const SkPoint origin, SkGlyphSet* glyphSet) {
-    size_t runSize;
-    std::unique_ptr<uint16_t[]> denseIndex;
-    std::vector<SkGlyphID> uniqueGlyphIDs;
-    std::tie(runSize, denseIndex, uniqueGlyphIDs) = make_core(paint, bytes, byteLength, glyphSet);
+    // No need to clear fIndices here... SkGlyphSet's set insertion algorithm is designed to work
+    // correctly even when the fIndexes buffer is uninitialized!
+}
 
-    if (runSize == 0) { return SkGlyphRun{}; }
+// -- SkGlyphRunBuilder ----------------------------------------------------------------------------
+void SkGlyphRunBuilder::prepareDrawText(
+        const SkPaint& paint, const void* bytes, size_t byteLength, SkPoint origin) {
 
-    auto advances = skstd::make_unique_default<SkPoint[]>(uniqueGlyphIDs.size());
+    this->initializeDenseAndUnique(paint, bytes, byteLength);
 
+    fScratchAdvances.resize(this->uniqueSize());
     {
         auto cache = SkStrikeCache::FindOrCreateStrikeExclusive(paint);
-        cache->getAdvances(SkSpan<SkGlyphID>{uniqueGlyphIDs.data(),
-                                             uniqueGlyphIDs.size()}, advances.get());
+        cache->getAdvances(SkSpan<SkGlyphID>{fUniqueGlyphs}, fScratchAdvances.data());
     }
 
-    auto positions = skstd::make_unique_default<SkPoint[]>(runSize);
-
     SkPoint endOfLastGlyph = origin;
 
-    for (size_t i = 0; i < runSize; i++) {
-        positions[i] = endOfLastGlyph;
-        endOfLastGlyph += advances[denseIndex[i]];
+    for (size_t i = 0; i < this->runSize(); i++) {
+        fPositions.push_back(endOfLastGlyph);
+        endOfLastGlyph += fScratchAdvances[fDenseIndex[i]];
     }
 
     if (paint.getTextAlign() != SkPaint::kLeft_Align) {
@@ -108,115 +98,88 @@ SkGlyphRun SkGlyphRun::MakeFromDrawText(
         if (paint.getTextAlign() == SkPaint::kCenter_Align) {
             len.scale(SK_ScalarHalf);
         }
-        for (size_t i = 0; i < runSize; i++) {
-            positions[i] -= len;
+        for (size_t i = 0; i < this->runSize(); i++) {
+            fPositions[i] -= len;
         }
     }
 
-    return SkGlyphRun{
-        runSize, std::move(denseIndex), std::move(positions), std::move(uniqueGlyphIDs)};
 }
 
-SkGlyphRun SkGlyphRun::MakeFromDrawPosTextH(
-        const SkPaint& paint, const void* bytes, size_t byteLength,
-        const SkScalar xpos[], SkScalar constY, SkGlyphSet* glyphSet) {
-    size_t runSize;
-    std::unique_ptr<uint16_t[]> denseIndex;
-    std::vector<SkGlyphID> uniqueGlyphIDs;
-    std::tie(runSize, denseIndex, uniqueGlyphIDs) = make_core(paint, bytes, byteLength, glyphSet);
-
-    if (runSize == 0) { return SkGlyphRun{}; }
+void SkGlyphRunBuilder::prepareDrawPosTextH(const SkPaint& paint, const void* bytes,
+                                            size_t byteLength, const SkScalar* xpos,
+                                            SkScalar constY) {
 
-    auto positions = skstd::make_unique_default<SkPoint[]>(runSize);
+    this->initializeDenseAndUnique(paint, bytes, byteLength);
 
-    for (size_t i = 0; i < runSize; i++) {
-        positions[i] = SkPoint::Make(xpos[i], constY);
+    for (size_t i = 0; i < runSize(); i++) {
+        fPositions.push_back(SkPoint::Make(xpos[i], constY));
     }
-
-    return SkGlyphRun{
-        runSize, std::move(denseIndex), std::move(positions), std::move(uniqueGlyphIDs)};
 }
 
-SkGlyphRun SkGlyphRun::MakeFromDrawPosText(
-        const SkPaint& paint, const void* bytes, size_t byteLength,
-        const SkPoint pos[], SkGlyphSet* glyphSet) {
-    size_t runSize;
-    std::unique_ptr<uint16_t[]> denseIndex;
-    std::vector<SkGlyphID> uniqueGlyphIDs;
-    std::tie(runSize, denseIndex, uniqueGlyphIDs) = make_core(paint, bytes, byteLength, glyphSet);
+void SkGlyphRunBuilder::prepareDrawPosText(const SkPaint& paint, const void* bytes,
+                                           size_t byteLength, const SkPoint* pos) {
+    this->initializeDenseAndUnique(paint, bytes, byteLength);
 
-    if (runSize == 0) { return SkGlyphRun{}; }
-
-    auto positions = skstd::make_unique_default<SkPoint[]>(runSize);
-
-    memcpy(positions.get(), pos, sizeof(SkPoint) * runSize);
+    for (size_t i = 0; i < runSize(); i++) {
+        fPositions.push_back(pos[i]);
+    }
+}
 
-    return SkGlyphRun{
-        runSize, std::move(denseIndex), std::move(positions), std::move(uniqueGlyphIDs)};
+const SkGlyphRun& SkGlyphRunBuilder::useGlyphRun() const {
+    new ((void*)&fScratchGlyphRun) SkGlyphRun{SkSpan<uint16_t>(fDenseIndex),
+                                       SkSpan<SkPoint>(fPositions),
+                                       SkSpan<SkGlyphID>(fUniqueGlyphs)};
+    return fScratchGlyphRun;
 }
 
-std::unique_ptr<SkGlyphID[]> SkGlyphRun::copyGlyphIDs() const {
-    auto glyphs = skstd::make_unique_default<SkGlyphID[]>(fRunSize);
+void SkGlyphRunBuilder::temporaryShuntToDrawPosText(const SkPaint& paint, SkBaseDevice* device) {
 
-    for (size_t i = 0; i < fRunSize; i++) {
-        glyphs[i] = fUniqueGlyphs[fDenseIndex[i]];
-    }
+    auto pos = (const SkScalar*) fPositions.data();
 
-    return glyphs;
+    device->drawPosText(
+            fTemporaryShuntGlyphIDs, fDenseIndex.size() * 2,
+            pos, 2, SkPoint::Make(0, 0), paint);
 }
 
-SkGlyphRun::SkGlyphRun(size_t runSize,
-                       std::unique_ptr<uint16_t[]>&& denseIndex,
-                       std::unique_ptr<SkPoint[]>&& positions,
-                       std::vector<SkGlyphID>&& uniqueGlyphIDs)
-    : fDenseIndex{std::move(denseIndex)}
-    , fPositions{std::move(positions)}
-    , fUniqueGlyphs{std::move(uniqueGlyphIDs)}
-    , fRunSize{runSize} { }
-
-uint16_t SkGlyphSet::add(SkGlyphID glyphID) {
-    static constexpr SkGlyphID  kUndefGlyph{0};
+void SkGlyphRunBuilder::temporaryShuntToCallback(TemporaryShuntCallback callback) {
+    auto bytes = (const char *)fTemporaryShuntGlyphIDs;
+    auto pos = (const SkScalar*)fPositions.data();
+    callback(this->runSize(), bytes, pos);
+}
 
-    if (glyphID >= fUniverseSize) {
-        glyphID = kUndefGlyph;
-    }
+void SkGlyphRunBuilder::initializeDenseAndUnique(
+        const SkPaint& paint, const void* bytes, size_t byteLength) {
 
-    if (glyphID >= fIndices.size()) {
-        fIndices.resize(glyphID + 1);
-    }
+    fDenseIndex.clear();
+    fPositions.clear();
+    fUniqueGlyphs.clear();
+    fTemporaryShuntGlyphIDs = nullptr;
 
-    auto index = fIndices[glyphID];
-    if (index < fUniqueGlyphIDs.size() && fUniqueGlyphIDs[index] == glyphID) {
-        return index;
+    size_t runSize = 0;
+    const 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);
+            fScratchGlyphIDs.resize(runSize);
+            typeface->charsToGlyphs(bytes, tfEncoding, fScratchGlyphIDs.data(), runSize);
+            glyphIDs = fScratchGlyphIDs.data();
+        }
+    } else {
+        runSize = byteLength / 2;
+        glyphIDs = (const SkGlyphID*)bytes;
     }
 
-    uint16_t newIndex = SkTo<uint16_t>(fUniqueGlyphIDs.size());
-    fUniqueGlyphIDs.push_back(glyphID);
-    fIndices[glyphID] = newIndex;
-    return newIndex;
-}
-
-std::vector<SkGlyphID> SkGlyphSet::uniqueGlyphIDs() {
-    return fUniqueGlyphIDs;
-}
+    if (runSize == 0) { return; }
+    fTemporaryShuntGlyphIDs = glyphIDs;
 
-void SkGlyphSet::reuse(uint32_t glyphUniverseSize) {
-    SkASSERT(glyphUniverseSize <= (1 << 16));
-    fUniverseSize = glyphUniverseSize;
-    // 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 more than 256 unique glyphs used in a run,
-    // or a typeface with more than 4096 possible glyphs.
-    if (fUniqueGlyphIDs.size() > 256) {
-        fUniqueGlyphIDs.resize(256);
-        fUniqueGlyphIDs.shrink_to_fit();
+    fGlyphSet.reuse(typeface->countGlyphs(), &fUniqueGlyphs);
+    for (size_t i = 0; i < runSize; i++) {
+        fDenseIndex.push_back(fGlyphSet.add(glyphIDs[i]));
     }
-    fUniqueGlyphIDs.clear();
+}
 
-    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!
-}
\ No newline at end of file