diff options
author | Herb Derby <herb@google.com> | 2018-07-09 17:06:09 -0400 |
---|---|---|
committer | Skia Commit-Bot <skia-commit-bot@chromium.org> | 2018-07-10 22:15:05 +0000 |
commit | 819f73c23cfd8471e1cbc77ee7c14d8150457765 (patch) | |
tree | 9c0a8097d37d7c022439de6fee4642a11fa062a3 /src/core/SkGlyphRun.cpp | |
parent | 02ca49fc466bc54831c3a8f03b1b3c6ab6bba498 (diff) |
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>
Diffstat (limited to 'src/core/SkGlyphRun.cpp')
-rw-r--r-- | src/core/SkGlyphRun.cpp | 216 |
1 files changed, 118 insertions, 98 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); } |