diff options
-rw-r--r-- | src/core/SkGlyphRun.cpp | 216 | ||||
-rw-r--r-- | src/core/SkGlyphRun.h | 51 | ||||
-rw-r--r-- | tests/GlyphRunTest.cpp | 45 |
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) { |