1/*
2 * Copyright 2019 Google Inc.
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 "modules/skottie/src/text/SkottieShaper.h"
9
10#include "include/core/SkFontMetrics.h"
11#include "include/core/SkFontMgr.h"
12#include "include/core/SkTextBlob.h"
13#include "include/private/SkTemplates.h"
14#include "modules/skshaper/include/SkShaper.h"
15#include "src/core/SkTLazy.h"
16#include "src/core/SkTextBlobPriv.h"
17#include "src/utils/SkUTF.h"
18
19#include <limits.h>
20
21namespace skottie {
22namespace {
23
24SkRect ComputeBlobBounds(const sk_sp<SkTextBlob>& blob) {
25 auto bounds = SkRect::MakeEmpty();
26
27 if (!blob) {
28 return bounds;
29 }
30
31 SkAutoSTArray<16, SkRect> glyphBounds;
32
33 SkTextBlobRunIterator it(blob.get());
34
35 for (SkTextBlobRunIterator it(blob.get()); !it.done(); it.next()) {
36 glyphBounds.reset(SkToInt(it.glyphCount()));
37 it.font().getBounds(it.glyphs(), it.glyphCount(), glyphBounds.get(), nullptr);
38
39 SkASSERT(it.positioning() == SkTextBlobRunIterator::kFull_Positioning);
40 for (uint32_t i = 0; i < it.glyphCount(); ++i) {
41 bounds.join(glyphBounds[i].makeOffset(it.pos()[i * 2 ],
42 it.pos()[i * 2 + 1]));
43 }
44 }
45
46 return bounds;
47}
48
49// Helper for interfacing with SkShaper: buffers shaper-fed runs and performs
50// per-line position adjustments (for external line breaking, horizontal alignment, etc).
51class BlobMaker final : public SkShaper::RunHandler {
52public:
53 BlobMaker(const Shaper::TextDesc& desc, const SkRect& box, const sk_sp<SkFontMgr>& fontmgr)
54 : fDesc(desc)
55 , fBox(box)
56 , fHAlignFactor(HAlignFactor(fDesc.fHAlign))
57 , fFont(fDesc.fTypeface, fDesc.fTextSize)
58 , fShaper(SkShaper::Make(fontmgr)) {
59 fFont.setHinting(SkFontHinting::kNone);
60 fFont.setSubpixel(true);
61 fFont.setLinearMetrics(true);
62 fFont.setBaselineSnap(false);
63 fFont.setEdging(SkFont::Edging::kAntiAlias);
64 }
65
66 void beginLine() override {
67 fLineGlyphs.reset(0);
68 fLinePos.reset(0);
69 fLineClusters.reset(0);
70 fLineRuns.reset();
71 fLineGlyphCount = 0;
72
73 fCurrentPosition = fOffset;
74 fPendingLineAdvance = { 0, 0 };
75
76 fLastLineDescent = 0;
77 }
78
79 void runInfo(const RunInfo& info) override {
80 fPendingLineAdvance += info.fAdvance;
81
82 SkFontMetrics metrics;
83 info.fFont.getMetrics(&metrics);
84 if (!fLineCount) {
85 fFirstLineAscent = std::min(fFirstLineAscent, metrics.fAscent);
86 }
87 fLastLineDescent = std::max(fLastLineDescent, metrics.fDescent);
88 }
89
90 void commitRunInfo() override {}
91
92 Buffer runBuffer(const RunInfo& info) override {
93 const auto run_start_index = fLineGlyphCount;
94 fLineGlyphCount += info.glyphCount;
95
96 fLineGlyphs.realloc(fLineGlyphCount);
97 fLinePos.realloc(fLineGlyphCount);
98 fLineClusters.realloc(fLineGlyphCount);
99 fLineRuns.push_back({info.fFont, info.glyphCount});
100
101 SkVector alignmentOffset { fHAlignFactor * (fPendingLineAdvance.x() - fBox.width()), 0 };
102
103 return {
104 fLineGlyphs.get() + run_start_index,
105 fLinePos.get() + run_start_index,
106 nullptr,
107 fLineClusters.get() + run_start_index,
108 fCurrentPosition + alignmentOffset
109 };
110 }
111
112 void commitRunBuffer(const RunInfo& info) override {
113 fCurrentPosition += info.fAdvance;
114 }
115
116 void commitLine() override {
117 fOffset.fY += fDesc.fLineHeight;
118
119 // TODO: justification adjustments
120
121 const auto commit_proc = (fDesc.fFlags & Shaper::Flags::kFragmentGlyphs)
122 ? &BlobMaker::commitFragementedRun
123 : &BlobMaker::commitConsolidatedRun;
124
125 size_t run_offset = 0;
126 for (const auto& rec : fLineRuns) {
127 SkASSERT(run_offset < fLineGlyphCount);
128 (this->*commit_proc)(rec,
129 fLineGlyphs.get() + run_offset,
130 fLinePos.get() + run_offset,
131 fLineClusters.get() + run_offset,
132 fLineCount);
133 run_offset += rec.fGlyphCount;
134 }
135
136 fLineCount++;
137 }
138
139 Shaper::Result finalize(SkSize* shaped_size) {
140 if (!(fDesc.fFlags & Shaper::Flags::kFragmentGlyphs)) {
141 // All glyphs are pending in a single blob.
142 SkASSERT(fResult.fFragments.empty());
143 fResult.fFragments.reserve(1);
144 fResult.fFragments.push_back({fBuilder.make(), {fBox.x(), fBox.y()}, 0, 0, 0, false});
145 }
146
147 const auto ascent = this->ascent();
148
149 // For visual VAlign modes, we use a hybrid extent box computed as the union of
150 // actual visual bounds and the vertical typographical extent.
151 //
152 // This ensures that
153 //
154 // a) text doesn't visually overflow the alignment boundaries
155 //
156 // b) leading/trailing empty lines are still taken into account for alignment purposes
157
158 auto extent_box = [&]() {
159 auto box = fResult.computeVisualBounds();
160
161 // By default, first line is vertically-aligned on a baseline of 0.
162 // The typographical height considered for vertical alignment is the distance between
163 // the first line top (ascent) to the last line bottom (descent).
164 const auto typographical_top = fBox.fTop + ascent,
165 typographical_bottom = fBox.fTop + fLastLineDescent + fDesc.fLineHeight *
166 (fLineCount > 0 ? fLineCount - 1 : 0ul);
167
168 box.fTop = std::min(box.fTop, typographical_top);
169 box.fBottom = std::max(box.fBottom, typographical_bottom);
170
171 return box;
172 };
173
174 // Only compute the extent box when needed.
175 SkTLazy<SkRect> ebox;
176
177 // Perform additional adjustments based on VAlign.
178 float v_offset = 0;
179 switch (fDesc.fVAlign) {
180 case Shaper::VAlign::kTop:
181 v_offset = -ascent;
182 break;
183 case Shaper::VAlign::kTopBaseline:
184 // Default behavior.
185 break;
186 case Shaper::VAlign::kVisualTop:
187 ebox.init(extent_box());
188 v_offset = fBox.fTop - ebox->fTop;
189 break;
190 case Shaper::VAlign::kVisualCenter:
191 ebox.init(extent_box());
192 v_offset = fBox.centerY() - ebox->centerY();
193 break;
194 case Shaper::VAlign::kVisualBottom:
195 ebox.init(extent_box());
196 v_offset = fBox.fBottom - ebox->fBottom;
197 break;
198 }
199
200 if (shaped_size) {
201 if (!ebox.isValid()) {
202 ebox.init(extent_box());
203 }
204 *shaped_size = SkSize::Make(ebox->width(), ebox->height());
205 }
206
207 if (v_offset) {
208 for (auto& fragment : fResult.fFragments) {
209 fragment.fPos.fY += v_offset;
210 }
211 }
212
213 return std::move(fResult);
214 }
215
216 void shapeLine(const char* start, const char* end) {
217 if (!fShaper) {
218 return;
219 }
220
221 SkASSERT(start <= end);
222 if (start == end) {
223 // SkShaper doesn't care for empty lines.
224 this->beginLine();
225 this->commitLine();
226 return;
227 }
228
229 // In default paragraph mode (VAlign::kTop), AE clips out lines when the baseline
230 // goes below the box lower edge.
231 if (fDesc.fVAlign == Shaper::VAlign::kTop) {
232 // fOffset is relative to the first line baseline.
233 const auto max_offset = fBox.height() + this->ascent(); // NB: ascent is negative
234 if (fOffset.y() > max_offset) {
235 return;
236 }
237 }
238
239 // When no text box is present, text is laid out on a single infinite line
240 // (modulo explicit line breaks).
241 const auto shape_width = fBox.isEmpty() ? SK_ScalarMax
242 : fBox.width();
243
244 fUTF8 = start;
245 fShaper->shape(start, SkToSizeT(end - start), fFont, true, shape_width, this);
246 fUTF8 = nullptr;
247 }
248
249private:
250 struct RunRec {
251 SkFont fFont;
252 size_t fGlyphCount;
253 };
254
255 void commitFragementedRun(const RunRec& rec,
256 const SkGlyphID* glyphs,
257 const SkPoint* pos,
258 const uint32_t* clusters,
259 uint32_t line_index) {
260
261 static const auto is_whitespace = [](char c) {
262 return c == ' ' || c == '\t' || c == '\r' || c == '\n';
263 };
264
265 float ascent = 0;
266
267 if (fDesc.fFlags & Shaper::Flags::kTrackFragmentAdvanceAscent) {
268 SkFontMetrics metrics;
269 rec.fFont.getMetrics(&metrics);
270 ascent = metrics.fAscent;
271
272 // Note: we use per-glyph advances for anchoring, but it's unclear whether this
273 // is exactly the same as AE. E.g. are 'acute' glyphs anchored separately for fonts
274 // in which they're distinct?
275 fAdvanceBuffer.resize(rec.fGlyphCount);
276 fFont.getWidths(glyphs, SkToInt(rec.fGlyphCount), fAdvanceBuffer.data());
277 }
278
279 // In fragmented mode we immediately push the glyphs to fResult,
280 // one fragment (blob) per glyph. Glyph positioning is externalized
281 // (positions returned in Fragment::fPos).
282 for (size_t i = 0; i < rec.fGlyphCount; ++i) {
283 const auto& blob_buffer = fBuilder.allocRunPos(rec.fFont, 1);
284 blob_buffer.glyphs[0] = glyphs[i];
285 blob_buffer.pos[0] = blob_buffer.pos[1] = 0;
286
287 const auto advance = (fDesc.fFlags & Shaper::Flags::kTrackFragmentAdvanceAscent)
288 ? fAdvanceBuffer[SkToInt(i)]
289 : 0.0f;
290
291 // Note: we only check the first code point in the cluster for whitespace.
292 // It's unclear whether thers's a saner approach.
293 fResult.fFragments.push_back({fBuilder.make(),
294 { fBox.x() + pos[i].fX, fBox.y() + pos[i].fY },
295 advance, ascent,
296 line_index, is_whitespace(fUTF8[clusters[i]])
297 });
298 fResult.fMissingGlyphCount += (glyphs[i] == kMissingGlyphID);
299 }
300 }
301
302 void commitConsolidatedRun(const RunRec& rec,
303 const SkGlyphID* glyphs,
304 const SkPoint* pos,
305 const uint32_t*,
306 uint32_t) {
307 // In consolidated mode we just accumulate glyphs to the blob builder, then push
308 // to fResult as a single blob in finalize(). Glyph positions are baked in the
309 // blob (Fragment::fPos only reflects the box origin).
310 const auto& blob_buffer = fBuilder.allocRunPos(rec.fFont, rec.fGlyphCount);
311 for (size_t i = 0; i < rec.fGlyphCount; ++i) {
312 blob_buffer.glyphs[i] = glyphs[i];
313 fResult.fMissingGlyphCount += (glyphs[i] == kMissingGlyphID);
314 }
315 sk_careful_memcpy(blob_buffer.pos , pos , rec.fGlyphCount * sizeof(SkPoint));
316 }
317
318 static float HAlignFactor(SkTextUtils::Align align) {
319 switch (align) {
320 case SkTextUtils::kLeft_Align: return 0.0f;
321 case SkTextUtils::kCenter_Align: return -0.5f;
322 case SkTextUtils::kRight_Align: return -1.0f;
323 }
324 return 0.0f; // go home, msvc...
325 }
326
327 SkScalar ascent() const {
328 // Use the explicit ascent, when specified.
329 // Note: ascent values are negative (relative to the baseline).
330 return fDesc.fAscent ? fDesc.fAscent : fFirstLineAscent;
331 }
332
333 static constexpr SkGlyphID kMissingGlyphID = 0;
334
335 const Shaper::TextDesc& fDesc;
336 const SkRect& fBox;
337 const float fHAlignFactor;
338
339 SkFont fFont;
340 SkTextBlobBuilder fBuilder;
341 std::unique_ptr<SkShaper> fShaper;
342
343 SkAutoSTMalloc<64, SkGlyphID> fLineGlyphs;
344 SkAutoSTMalloc<64, SkPoint> fLinePos;
345 SkAutoSTMalloc<64, uint32_t> fLineClusters;
346 SkSTArray<16, RunRec> fLineRuns;
347 size_t fLineGlyphCount = 0;
348
349 SkSTArray<64, float, true> fAdvanceBuffer;
350
351 SkPoint fCurrentPosition{ 0, 0 };
352 SkPoint fOffset{ 0, 0 };
353 SkVector fPendingLineAdvance{ 0, 0 };
354 uint32_t fLineCount = 0;
355 float fFirstLineAscent = 0,
356 fLastLineDescent = 0;
357
358 const char* fUTF8 = nullptr; // only valid during shapeLine() calls
359
360 Shaper::Result fResult;
361};
362
363Shaper::Result ShapeImpl(const SkString& txt, const Shaper::TextDesc& desc,
364 const SkRect& box, const sk_sp<SkFontMgr>& fontmgr,
365 SkSize* shaped_size = nullptr) {
366 const auto& is_line_break = [](SkUnichar uch) {
367 // TODO: other explicit breaks?
368 return uch == '\r';
369 };
370
371 const char* ptr = txt.c_str();
372 const char* line_start = ptr;
373 const char* end = ptr + txt.size();
374
375 BlobMaker blobMaker(desc, box, fontmgr);
376 while (ptr < end) {
377 if (is_line_break(SkUTF::NextUTF8(&ptr, end))) {
378 blobMaker.shapeLine(line_start, ptr - 1);
379 line_start = ptr;
380 }
381 }
382 blobMaker.shapeLine(line_start, ptr);
383
384 return blobMaker.finalize(shaped_size);
385}
386
387Shaper::Result ShapeToFit(const SkString& txt, const Shaper::TextDesc& orig_desc,
388 const SkRect& box, const sk_sp<SkFontMgr>& fontmgr) {
389 Shaper::Result best_result;
390
391 if (box.isEmpty() || orig_desc.fTextSize <= 0) {
392 return best_result;
393 }
394
395 auto desc = orig_desc;
396
397 float in_scale = 0, // maximum scale that fits inside
398 out_scale = std::numeric_limits<float>::max(), // minimum scale that doesn't fit
399 try_scale = 1; // current probe
400
401 // Perform a binary search for the best vertical fit (SkShaper already handles
402 // horizontal fitting), starting with the specified text size.
403 //
404 // This hybrid loop handles both the binary search (when in/out extremes are known), and an
405 // exponential search for the extremes.
406 static constexpr size_t kMaxIter = 16;
407 for (size_t i = 0; i < kMaxIter; ++i) {
408 SkASSERT(try_scale >= in_scale && try_scale <= out_scale);
409 desc.fTextSize = try_scale * orig_desc.fTextSize;
410 desc.fLineHeight = try_scale * orig_desc.fLineHeight;
411 desc.fAscent = try_scale * orig_desc.fAscent;
412
413 SkSize res_size = {0, 0};
414 auto res = ShapeImpl(txt, desc, box, fontmgr, &res_size);
415
416 if (res_size.width() > box.width() || res_size.height() > box.height()) {
417 out_scale = try_scale;
418 try_scale = (in_scale == 0)
419 ? try_scale * 0.5f // initial in_scale not found yet - search exponentially
420 : (in_scale + out_scale) * 0.5f; // in_scale found - binary search
421 } else {
422 // It fits - so it's a candidate.
423 best_result = std::move(res);
424
425 in_scale = try_scale;
426 try_scale = (out_scale == std::numeric_limits<float>::max())
427 ? try_scale * 2 // initial out_scale not found yet - search exponentially
428 : (in_scale + out_scale) * 0.5f; // out_scale found - binary search
429 }
430 }
431
432 return best_result;
433}
434
435} // namespace
436
437Shaper::Result Shaper::Shape(const SkString& txt, const TextDesc& desc, const SkPoint& point,
438 const sk_sp<SkFontMgr>& fontmgr) {
439 return (desc.fResize == ResizePolicy::kScaleToFit ||
440 desc.fResize == ResizePolicy::kDownscaleToFit) // makes no sense in point mode
441 ? Result()
442 : ShapeImpl(txt, desc, SkRect::MakeEmpty().makeOffset(point.x(), point.y()), fontmgr);
443}
444
445Shaper::Result Shaper::Shape(const SkString& txt, const TextDesc& desc, const SkRect& box,
446 const sk_sp<SkFontMgr>& fontmgr) {
447 switch(desc.fResize) {
448 case ResizePolicy::kNone:
449 return ShapeImpl(txt, desc, box, fontmgr);
450 case ResizePolicy::kScaleToFit:
451 return ShapeToFit(txt, desc, box, fontmgr);
452 case ResizePolicy::kDownscaleToFit: {
453 SkSize size;
454 auto result = ShapeImpl(txt, desc, box, fontmgr, &size);
455
456 return (size.width() <= box.width() && size.height() <= box.height())
457 ? result
458 : ShapeToFit(txt, desc, box, fontmgr);
459 }
460 }
461
462 SkUNREACHABLE;
463}
464
465SkRect Shaper::Result::computeVisualBounds() const {
466 auto bounds = SkRect::MakeEmpty();
467
468 for (const auto& fragment : fFragments) {
469 bounds.join(ComputeBlobBounds(fragment.fBlob).makeOffset(fragment.fPos.x(),
470 fragment.fPos.y()));
471 }
472
473 return bounds;
474}
475
476} // namespace skottie
477