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