1 /*
2 * Copyright 2018 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "SkGlyphRun.h"
9
10 #include "SkDevice.h"
11 #include "SkFont.h"
12 #include "SkFontPriv.h"
13 #include "SkPaint.h"
14 #include "SkStrike.h"
15 #include "SkStrikeCache.h"
16 #include "SkTextBlob.h"
17 #include "SkTextBlobPriv.h"
18 #include "SkTo.h"
19 #include "SkUtils.h"
20
21 // -- SkGlyphRun -----------------------------------------------------------------------------------
SkGlyphRun(const SkFont & font,SkSpan<const SkPoint> positions,SkSpan<const SkGlyphID> glyphIDs,SkSpan<const char> text,SkSpan<const uint32_t> clusters)22 SkGlyphRun::SkGlyphRun(const SkFont& font,
23 SkSpan<const SkPoint> positions,
24 SkSpan<const SkGlyphID> glyphIDs,
25 SkSpan<const char> text,
26 SkSpan<const uint32_t> clusters)
27 : fPositions{positions}
28 , fGlyphIDs{glyphIDs}
29 , fText{text}
30 , fClusters{clusters}
31 , fFont{font} {}
32
SkGlyphRun(const SkGlyphRun & that,const SkFont & font)33 SkGlyphRun::SkGlyphRun(const SkGlyphRun& that, const SkFont& font)
34 : fPositions{that.fPositions}
35 , fGlyphIDs{that.fGlyphIDs}
36 , fText{that.fText}
37 , fClusters{that.fClusters}
38 , fFont{font} {}
39
filloutGlyphsAndPositions(SkGlyphID * glyphIDs,SkPoint * positions)40 void SkGlyphRun::filloutGlyphsAndPositions(SkGlyphID* glyphIDs, SkPoint* positions) {
41 memcpy(glyphIDs, fGlyphIDs.data(), fGlyphIDs.size_bytes());
42 memcpy(positions, fPositions.data(), fPositions.size_bytes());
43 }
44
45 // -- SkGlyphRunList -------------------------------------------------------------------------------
46 SkGlyphRunList::SkGlyphRunList() = default;
SkGlyphRunList(const SkPaint & paint,const SkTextBlob * blob,SkPoint origin,SkSpan<const SkGlyphRun> glyphRunList)47 SkGlyphRunList::SkGlyphRunList(
48 const SkPaint& paint,
49 const SkTextBlob* blob,
50 SkPoint origin,
51 SkSpan<const SkGlyphRun> glyphRunList)
52 : fOriginalPaint{&paint}
53 , fOriginalTextBlob{blob}
54 , fOrigin{origin}
55 , fGlyphRuns{glyphRunList} { }
56
SkGlyphRunList(const SkGlyphRun & glyphRun,const SkPaint & paint)57 SkGlyphRunList::SkGlyphRunList(const SkGlyphRun& glyphRun, const SkPaint& paint)
58 : fOriginalPaint{&paint}
59 , fOriginalTextBlob{nullptr}
60 , fOrigin{SkPoint::Make(0, 0)}
61 , fGlyphRuns{SkSpan<const SkGlyphRun>{&glyphRun, 1}} {}
62
uniqueID() const63 uint64_t SkGlyphRunList::uniqueID() const {
64 return fOriginalTextBlob != nullptr ? fOriginalTextBlob->uniqueID()
65 : SK_InvalidUniqueID;
66 }
67
anyRunsLCD() const68 bool SkGlyphRunList::anyRunsLCD() const {
69 for (const auto& r : fGlyphRuns) {
70 if (r.font().getEdging() == SkFont::Edging::kSubpixelAntiAlias) {
71 return true;
72 }
73 }
74 return false;
75 }
76
anyRunsSubpixelPositioned() const77 bool SkGlyphRunList::anyRunsSubpixelPositioned() const {
78 for (const auto& r : fGlyphRuns) {
79 if (r.font().isSubpixel()) {
80 return true;
81 }
82 }
83 return false;
84 }
85
allFontsFinite() const86 bool SkGlyphRunList::allFontsFinite() const {
87 for (const auto& r : fGlyphRuns) {
88 if (!SkFontPriv::IsFinite(r.font())) {
89 return false;
90 }
91 }
92 return true;
93 }
94
temporaryShuntBlobNotifyAddedToCache(uint32_t cacheID) const95 void SkGlyphRunList::temporaryShuntBlobNotifyAddedToCache(uint32_t cacheID) const {
96 SkASSERT(fOriginalTextBlob != nullptr);
97 fOriginalTextBlob->notifyAddedToCache(cacheID);
98 }
99
100 // -- SkGlyphIDSet ---------------------------------------------------------------------------------
101 // A faster set implementation that does not need any initialization, and reading the set items
102 // is order the number of items, and not the size of the universe.
103 // This implementation is based on the paper by Briggs and Torczon, "An Efficient Representation
104 // for Sparse Sets"
105 //
106 // This implementation assumes that the unique glyphs added are appended to a vector that may
107 // already have unique glyph from a previous computation. This allows the packing of multiple
108 // UniqueID sequences in a single vector.
uniquifyGlyphIDs(uint32_t universeSize,SkSpan<const SkGlyphID> glyphIDs,SkGlyphID * uniqueGlyphIDs,uint16_t * denseIndices)109 SkSpan<const SkGlyphID> SkGlyphIDSet::uniquifyGlyphIDs(
110 uint32_t universeSize,
111 SkSpan<const SkGlyphID> glyphIDs,
112 SkGlyphID* uniqueGlyphIDs,
113 uint16_t* denseIndices) {
114 static constexpr SkGlyphID kUndefGlyph{0};
115
116 if (universeSize > fUniverseToUniqueSize) {
117 fUniverseToUnique.reset(universeSize);
118 fUniverseToUniqueSize = universeSize;
119 // If the following bzero becomes a performance problem, the memory can be marked as
120 // initialized for valgrind and msan.
121 // valgrind = VALGRIND_MAKE_MEM_DEFINED(fUniverseToUnique, universeSize * sizeof(SkGlyphID))
122 // msan = sk_msan_mark_initialized(fUniverseToUnique, universeSize * sizeof(SkGlyphID))
123 sk_bzero(fUniverseToUnique, universeSize * sizeof(SkGlyphID));
124 }
125
126 // No need to clear fUniverseToUnique here... the set insertion algorithm is designed to work
127 // correctly even when the fUniverseToUnique buffer is uninitialized!
128
129 size_t uniqueSize = 0;
130 size_t denseIndicesCursor = 0;
131 for (auto glyphID : glyphIDs) {
132
133 // If the glyphID is not in range then it is the undefined glyph.
134 if (glyphID >= universeSize) {
135 glyphID = kUndefGlyph;
136 }
137
138 // The index into the unique ID vector.
139 auto uniqueIndex = fUniverseToUnique[glyphID];
140
141 if (uniqueIndex >= uniqueSize || uniqueGlyphIDs[uniqueIndex] != glyphID) {
142 uniqueIndex = SkTo<uint16_t>(uniqueSize);
143 uniqueGlyphIDs[uniqueSize] = glyphID;
144 fUniverseToUnique[glyphID] = uniqueIndex;
145 uniqueSize += 1;
146 }
147
148 denseIndices[denseIndicesCursor++] = uniqueIndex;
149 }
150
151 // If we're hanging onto these arrays for a long time, we don't want their size to drift
152 // endlessly upwards. It's unusual to see a typeface with more than 4096 possible glyphs.
153 if (fUniverseToUniqueSize > 4096) {
154 fUniverseToUnique.reset(4096);
155 sk_bzero(fUniverseToUnique, 4096 * sizeof(SkGlyphID));
156 fUniverseToUniqueSize = 4096;
157 }
158
159 return SkSpan<const SkGlyphID>(uniqueGlyphIDs, uniqueSize);
160 }
161
162 // -- SkGlyphRunBuilder ----------------------------------------------------------------------------
drawTextUTF8(const SkPaint & paint,const SkFont & font,const void * bytes,size_t byteLength,SkPoint origin)163 void SkGlyphRunBuilder::drawTextUTF8(const SkPaint& paint, const SkFont& font, const void* bytes,
164 size_t byteLength, SkPoint origin) {
165 auto glyphIDs = textToGlyphIDs(font, bytes, byteLength, kUTF8_SkTextEncoding);
166 if (!glyphIDs.empty()) {
167 this->initialize(glyphIDs.size());
168 this->simplifyDrawText(font, glyphIDs, origin, fPositions);
169 }
170
171 this->makeGlyphRunList(paint, nullptr, SkPoint::Make(0, 0));
172 }
173
drawTextBlob(const SkPaint & paint,const SkTextBlob & blob,SkPoint origin,SkBaseDevice * device)174 void SkGlyphRunBuilder::drawTextBlob(const SkPaint& paint, const SkTextBlob& blob, SkPoint origin,
175 SkBaseDevice* device) {
176 // Figure out all the storage needed to pre-size everything below.
177 size_t totalGlyphs = 0;
178 for (SkTextBlobRunIterator it(&blob); !it.done(); it.next()) {
179 totalGlyphs += it.glyphCount();
180 }
181
182 // Pre-size all the buffers so they don't move during processing.
183 this->initialize(totalGlyphs);
184
185 SkPoint* positions = fPositions;
186
187 for (SkTextBlobRunIterator it(&blob); !it.done(); it.next()) {
188 // applyFontToPaint() always overwrites the exact same attributes,
189 // so it is safe to not re-seed the paint for this reason.
190 size_t runSize = it.glyphCount();
191
192 auto text = SkSpan<const char>(it.text(), it.textSize());
193 auto clusters = SkSpan<const uint32_t>(it.clusters(), runSize);
194 const SkPoint& offset = it.offset();
195 auto glyphIDs = SkSpan<const SkGlyphID>{it.glyphs(), runSize};
196
197 switch (it.positioning()) {
198 case SkTextBlobRunIterator::kDefault_Positioning: {
199 this->simplifyDrawText(
200 it.font(), glyphIDs, offset, positions, text, clusters);
201 }
202 break;
203 case SkTextBlobRunIterator::kHorizontal_Positioning: {
204 auto constY = offset.y();
205 this->simplifyDrawPosTextH(
206 it.font(), glyphIDs, it.pos(), constY, positions, text, clusters);
207 }
208 break;
209 case SkTextBlobRunIterator::kFull_Positioning:
210 this->simplifyDrawPosText(
211 it.font(), glyphIDs, (const SkPoint*)it.pos(), text, clusters);
212 break;
213 case SkTextBlobRunIterator::kRSXform_Positioning: {
214 if (!this->empty()) {
215 this->makeGlyphRunList(paint, &blob, origin);
216 device->drawGlyphRunList(this->useGlyphRunList());
217 }
218
219 device->drawGlyphRunRSXform(it.font(), it.glyphs(), (const SkRSXform*)it.pos(),
220 runSize, origin, paint);
221
222 // re-init in case we keep looping and need the builder again
223 this->initialize(totalGlyphs);
224 } break;
225 }
226
227 positions += runSize;
228 }
229
230 if (!this->empty()) {
231 this->makeGlyphRunList(paint, &blob, origin);
232 device->drawGlyphRunList(this->useGlyphRunList());
233 }
234 }
235
drawGlyphsWithPositions(const SkPaint & paint,const SkFont & font,SkSpan<const SkGlyphID> glyphIDs,const SkPoint * pos)236 void SkGlyphRunBuilder::drawGlyphsWithPositions(const SkPaint& paint, const SkFont& font,
237 SkSpan<const SkGlyphID> glyphIDs, const SkPoint* pos) {
238 if (!glyphIDs.empty()) {
239 this->initialize(glyphIDs.size());
240 this->simplifyDrawPosText(font, glyphIDs, pos);
241 this->makeGlyphRunList(paint, nullptr, SkPoint::Make(0, 0));
242 }
243 }
244
useGlyphRunList()245 const SkGlyphRunList& SkGlyphRunBuilder::useGlyphRunList() {
246 return fGlyphRunList;
247 }
248
initialize(size_t totalRunSize)249 void SkGlyphRunBuilder::initialize(size_t totalRunSize) {
250
251 if (totalRunSize > fMaxTotalRunSize) {
252 fMaxTotalRunSize = totalRunSize;
253 fPositions.reset(fMaxTotalRunSize);
254 }
255
256 fGlyphRunListStorage.clear();
257 }
258
textToGlyphIDs(const SkFont & font,const void * bytes,size_t byteLength,SkTextEncoding encoding)259 SkSpan<const SkGlyphID> SkGlyphRunBuilder::textToGlyphIDs(
260 const SkFont& font, const void* bytes, size_t byteLength, SkTextEncoding encoding) {
261 if (encoding != kGlyphID_SkTextEncoding) {
262 int count = font.countText(bytes, byteLength, encoding);
263 if (count > 0) {
264 fScratchGlyphIDs.resize(count);
265 font.textToGlyphs(bytes, byteLength, encoding, fScratchGlyphIDs.data(), count);
266 return SkSpan<const SkGlyphID>{fScratchGlyphIDs};
267 } else {
268 return SkSpan<const SkGlyphID>();
269 }
270 } else {
271 return SkSpan<const SkGlyphID>((const SkGlyphID*)bytes, byteLength / 2);
272 }
273 }
274
makeGlyphRun(const SkFont & font,SkSpan<const SkGlyphID> glyphIDs,SkSpan<const SkPoint> positions,SkSpan<const char> text,SkSpan<const uint32_t> clusters)275 void SkGlyphRunBuilder::makeGlyphRun(
276 const SkFont& font,
277 SkSpan<const SkGlyphID> glyphIDs,
278 SkSpan<const SkPoint> positions,
279 SkSpan<const char> text,
280 SkSpan<const uint32_t> clusters) {
281
282 // Ignore empty runs.
283 if (!glyphIDs.empty()) {
284 fGlyphRunListStorage.emplace_back(
285 font,
286 positions,
287 glyphIDs,
288 text,
289 clusters);
290 }
291 }
292
makeGlyphRunList(const SkPaint & paint,const SkTextBlob * blob,SkPoint origin)293 void SkGlyphRunBuilder::makeGlyphRunList(
294 const SkPaint& paint, const SkTextBlob* blob, SkPoint origin) {
295
296 fGlyphRunList.~SkGlyphRunList();
297 new (&fGlyphRunList) SkGlyphRunList{
298 paint, blob, origin, SkSpan<const SkGlyphRun>{fGlyphRunListStorage}};
299 }
300
simplifyDrawText(const SkFont & font,SkSpan<const SkGlyphID> glyphIDs,SkPoint origin,SkPoint * positions,SkSpan<const char> text,SkSpan<const uint32_t> clusters)301 void SkGlyphRunBuilder::simplifyDrawText(
302 const SkFont& font, SkSpan<const SkGlyphID> glyphIDs,
303 SkPoint origin, SkPoint* positions,
304 SkSpan<const char> text, SkSpan<const uint32_t> clusters) {
305 SkASSERT(!glyphIDs.empty());
306
307 auto runSize = glyphIDs.size();
308
309 if (!glyphIDs.empty()) {
310 fScratchAdvances.resize(runSize);
311 {
312 auto cache = SkStrikeCache::FindOrCreateStrikeWithNoDeviceExclusive(font);
313 cache->getAdvances(glyphIDs, fScratchAdvances.data());
314 }
315
316 SkPoint endOfLastGlyph = origin;
317
318 for (size_t i = 0; i < runSize; i++) {
319 positions[i] = endOfLastGlyph;
320 endOfLastGlyph += fScratchAdvances[i];
321 }
322
323 this->makeGlyphRun(
324 font,
325 glyphIDs,
326 SkSpan<const SkPoint>{positions, runSize},
327 text,
328 clusters);
329 }
330 }
331
simplifyDrawPosTextH(const SkFont & font,SkSpan<const SkGlyphID> glyphIDs,const SkScalar * xpos,SkScalar constY,SkPoint * positions,SkSpan<const char> text,SkSpan<const uint32_t> clusters)332 void SkGlyphRunBuilder::simplifyDrawPosTextH(
333 const SkFont& font, SkSpan<const SkGlyphID> glyphIDs,
334 const SkScalar* xpos, SkScalar constY, SkPoint* positions,
335 SkSpan<const char> text, SkSpan<const uint32_t> clusters) {
336
337 auto posCursor = positions;
338 for (auto x : SkSpan<const SkScalar>{xpos, glyphIDs.size()}) {
339 *posCursor++ = SkPoint::Make(x, constY);
340 }
341
342 simplifyDrawPosText(font, glyphIDs, positions, text, clusters);
343 }
344
simplifyDrawPosText(const SkFont & font,SkSpan<const SkGlyphID> glyphIDs,const SkPoint * pos,SkSpan<const char> text,SkSpan<const uint32_t> clusters)345 void SkGlyphRunBuilder::simplifyDrawPosText(
346 const SkFont& font, SkSpan<const SkGlyphID> glyphIDs,
347 const SkPoint* pos,
348 SkSpan<const char> text, SkSpan<const uint32_t> clusters) {
349 auto runSize = glyphIDs.size();
350
351 this->makeGlyphRun(
352 font,
353 glyphIDs,
354 SkSpan<const SkPoint>{pos, runSize},
355 text,
356 clusters);
357 }
358