1 /*
2 * Copyright 2006 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 #ifndef SkGlyph_DEFINED
9 #define SkGlyph_DEFINED
10
11 #include "include/core/SkPath.h"
12 #include "include/core/SkTypes.h"
13 #include "include/private/SkChecksum.h"
14 #include "include/private/SkFixed.h"
15 #include "include/private/SkTo.h"
16 #include "include/private/SkVx.h"
17 #include "src/core/SkMask.h"
18 #include "src/core/SkMathPriv.h"
19 #include "src/core/SkStrikeForGPU.h"
20
21 class SkArenaAlloc;
22 class SkDrawable;
23 class SkScalerContext;
24
25 // A combination of SkGlyphID and sub-pixel position information.
26 struct SkPackedGlyphID {
27 inline static constexpr uint32_t kImpossibleID = ~0u;
28 enum {
29 // Lengths
30 kGlyphIDLen = 16u,
31 kSubPixelPosLen = 2u,
32
33 // Bit positions
34 kSubPixelX = 0u,
35 kGlyphID = kSubPixelPosLen,
36 kSubPixelY = kGlyphIDLen + kSubPixelPosLen,
37 kEndData = kGlyphIDLen + 2 * kSubPixelPosLen,
38
39 // Masks
40 kGlyphIDMask = (1u << kGlyphIDLen) - 1,
41 kSubPixelPosMask = (1u << kSubPixelPosLen) - 1,
42 kMaskAll = (1u << kEndData) - 1,
43
44 // Location of sub pixel info in a fixed pointer number.
45 kFixedPointBinaryPointPos = 16u,
46 kFixedPointSubPixelPosBits = kFixedPointBinaryPointPos - kSubPixelPosLen,
47 };
48
49 inline static constexpr SkScalar kSubpixelRound =
50 1.f / (1u << (SkPackedGlyphID::kSubPixelPosLen + 1));
51
52 inline static constexpr SkIPoint kXYFieldMask{kSubPixelPosMask << kSubPixelX,
53 kSubPixelPosMask << kSubPixelY};
54
SkPackedGlyphIDSkPackedGlyphID55 constexpr explicit SkPackedGlyphID(SkGlyphID glyphID)
56 : fID{(uint32_t)glyphID << kGlyphID} { }
57
SkPackedGlyphIDSkPackedGlyphID58 constexpr SkPackedGlyphID(SkGlyphID glyphID, SkFixed x, SkFixed y)
59 : fID {PackIDXY(glyphID, x, y)} { }
60
SkPackedGlyphIDSkPackedGlyphID61 constexpr SkPackedGlyphID(SkGlyphID glyphID, uint32_t x, uint32_t y)
62 : fID {PackIDSubXSubY(glyphID, x, y)} { }
63
SkPackedGlyphIDSkPackedGlyphID64 SkPackedGlyphID(SkGlyphID glyphID, SkPoint pt, SkIPoint mask)
65 : fID{PackIDSkPoint(glyphID, pt, mask)} { }
66
SkPackedGlyphIDSkPackedGlyphID67 constexpr explicit SkPackedGlyphID(uint32_t v) : fID{v & kMaskAll} { }
SkPackedGlyphIDSkPackedGlyphID68 constexpr SkPackedGlyphID() : fID{kImpossibleID} {}
69
70 bool operator==(const SkPackedGlyphID& that) const {
71 return fID == that.fID;
72 }
73 bool operator!=(const SkPackedGlyphID& that) const {
74 return !(*this == that);
75 }
76 bool operator<(SkPackedGlyphID that) const {
77 return this->fID < that.fID;
78 }
79
glyphIDSkPackedGlyphID80 SkGlyphID glyphID() const {
81 return (fID >> kGlyphID) & kGlyphIDMask;
82 }
83
valueSkPackedGlyphID84 uint32_t value() const {
85 return fID;
86 }
87
getSubXFixedSkPackedGlyphID88 SkFixed getSubXFixed() const {
89 return this->subToFixed(kSubPixelX);
90 }
91
getSubYFixedSkPackedGlyphID92 SkFixed getSubYFixed() const {
93 return this->subToFixed(kSubPixelY);
94 }
95
hashSkPackedGlyphID96 uint32_t hash() const {
97 return SkChecksum::CheapMix(fID);
98 }
99
dumpSkPackedGlyphID100 SkString dump() const {
101 SkString str;
102 str.appendf("glyphID: %d, x: %d, y:%d", glyphID(), getSubXFixed(), getSubYFixed());
103 return str;
104 }
105
shortDumpSkPackedGlyphID106 SkString shortDump() const {
107 SkString str;
108 str.appendf("0x%x|%1d|%1d", this->glyphID(),
109 this->subPixelField(kSubPixelX),
110 this->subPixelField(kSubPixelY));
111 return str;
112 }
113
114 private:
PackIDSubXSubYSkPackedGlyphID115 static constexpr uint32_t PackIDSubXSubY(SkGlyphID glyphID, uint32_t x, uint32_t y) {
116 SkASSERT(x < (1u << kSubPixelPosLen));
117 SkASSERT(y < (1u << kSubPixelPosLen));
118
119 return (x << kSubPixelX) | (y << kSubPixelY) | (glyphID << kGlyphID);
120 }
121
122 // Assumptions: pt is properly rounded. mask is set for the x or y fields.
123 //
124 // A sub-pixel field is a number on the interval [2^kSubPixel, 2^(kSubPixel + kSubPixelPosLen)).
125 // Where kSubPixel is either kSubPixelX or kSubPixelY. Given a number x on [0, 1) we can
126 // generate a sub-pixel field using:
127 // sub-pixel-field = x * 2^(kSubPixel + kSubPixelPosLen)
128 //
129 // We can generate the integer sub-pixel field by &-ing the integer part of sub-filed with the
130 // sub-pixel field mask.
131 // int-sub-pixel-field = int(sub-pixel-field) & (kSubPixelPosMask << kSubPixel)
132 //
133 // The last trick is to extend the range from [0, 1) to [0, 2). The extend range is
134 // necessary because the modulo 1 calculation (pt - floor(pt)) generates numbers on [-1, 1).
135 // This does not round (floor) properly when converting to integer. Adding one to the range
136 // causes truncation and floor to be the same. Coincidentally, masking to produce the field also
137 // removes the +1.
PackIDSkPointSkPackedGlyphID138 static uint32_t PackIDSkPoint(SkGlyphID glyphID, SkPoint pt, SkIPoint mask) {
139 #if 0
140 // TODO: why does this code not work on GCC 8.3 x86 Debug builds?
141 using namespace skvx;
142 using XY = Vec<2, float>;
143 using SubXY = Vec<2, int>;
144
145 const XY magic = {1.f * (1u << (kSubPixelPosLen + kSubPixelX)),
146 1.f * (1u << (kSubPixelPosLen + kSubPixelY))};
147 XY pos{pt.x(), pt.y()};
148 XY subPos = (pos - floor(pos)) + 1.0f;
149 SubXY sub = cast<int>(subPos * magic) & SubXY{mask.x(), mask.y()};
150 #else
151 const float magicX = 1.f * (1u << (kSubPixelPosLen + kSubPixelX)),
152 magicY = 1.f * (1u << (kSubPixelPosLen + kSubPixelY));
153
154 float x = pt.x(),
155 y = pt.y();
156 x = (x - floorf(x)) + 1.0f;
157 y = (y - floorf(y)) + 1.0f;
158 int sub[] = {
159 (int)(x * magicX) & mask.x(),
160 (int)(y * magicY) & mask.y(),
161 };
162 #endif
163
164 SkASSERT(sub[0] / (1u << kSubPixelX) < (1u << kSubPixelPosLen));
165 SkASSERT(sub[1] / (1u << kSubPixelY) < (1u << kSubPixelPosLen));
166 return (glyphID << kGlyphID) | sub[0] | sub[1];
167 }
168
PackIDXYSkPackedGlyphID169 static constexpr uint32_t PackIDXY(SkGlyphID glyphID, SkFixed x, SkFixed y) {
170 return PackIDSubXSubY(glyphID, FixedToSub(x), FixedToSub(y));
171 }
172
FixedToSubSkPackedGlyphID173 static constexpr uint32_t FixedToSub(SkFixed n) {
174 return ((uint32_t)n >> kFixedPointSubPixelPosBits) & kSubPixelPosMask;
175 }
176
subPixelFieldSkPackedGlyphID177 constexpr uint32_t subPixelField(uint32_t subPixelPosBit) const {
178 return (fID >> subPixelPosBit) & kSubPixelPosMask;
179 }
180
subToFixedSkPackedGlyphID181 constexpr SkFixed subToFixed(uint32_t subPixelPosBit) const {
182 uint32_t subPixelPosition = this->subPixelField(subPixelPosBit);
183 return subPixelPosition << kFixedPointSubPixelPosBits;
184 }
185
186 uint32_t fID;
187 };
188
189 class SkGlyphRect;
190 namespace skglyph {
191 SkGlyphRect rect_union(SkGlyphRect, SkGlyphRect);
192 SkGlyphRect rect_intersection(SkGlyphRect, SkGlyphRect);
193 } // namespace skglyph
194
195 // SkGlyphRect encodes rectangles with coordinates on [-32767, 32767]. It is specialized for
196 // rectangle union and intersection operations.
197 class SkGlyphRect {
198 public:
199 SkGlyphRect() = default;
SkGlyphRect(int16_t left,int16_t top,int16_t right,int16_t bottom)200 SkGlyphRect(int16_t left, int16_t top, int16_t right, int16_t bottom)
201 : fRect{left, top, (int16_t)-right, (int16_t)-bottom} {
202 SkDEBUGCODE(const int32_t min = std::numeric_limits<int16_t>::min());
203 SkASSERT(left != min && top != min && right != min && bottom != min);
204 }
empty()205 bool empty() const {
206 return fRect[0] >= -fRect[2] || fRect[1] >= -fRect[3];
207 }
rect()208 SkRect rect() const {
209 return SkRect::MakeLTRB(fRect[0], fRect[1], -fRect[2], -fRect[3]);
210 }
iRect()211 SkIRect iRect() const {
212 return SkIRect::MakeLTRB(fRect[0], fRect[1], -fRect[2], -fRect[3]);
213 }
offset(int16_t x,int16_t y)214 SkGlyphRect offset(int16_t x, int16_t y) const {
215 return SkGlyphRect{fRect + Storage{x, y, SkTo<int16_t>(-x), SkTo<int16_t>(-y)}};
216 }
topLeft()217 skvx::Vec<2, int16_t> topLeft() const { return {fRect[0], fRect[1]}; }
218 friend SkGlyphRect skglyph::rect_union(SkGlyphRect, SkGlyphRect);
219 friend SkGlyphRect skglyph::rect_intersection(SkGlyphRect, SkGlyphRect);
220
221 private:
222 using Storage = skvx::Vec<4, int16_t>;
SkGlyphRect(Storage rect)223 SkGlyphRect(Storage rect) : fRect{rect} { }
224 Storage fRect;
225 };
226
227 namespace skglyph {
empty_rect()228 inline SkGlyphRect empty_rect() {
229 constexpr int16_t max = std::numeric_limits<int16_t>::max();
230 return {max, max, -max, -max};
231 }
full_rect()232 inline SkGlyphRect full_rect() {
233 constexpr int16_t max = std::numeric_limits<int16_t>::max();
234 return {-max, -max, max, max};
235 }
rect_union(SkGlyphRect a,SkGlyphRect b)236 inline SkGlyphRect rect_union(SkGlyphRect a, SkGlyphRect b) {
237 return skvx::min(a.fRect, b.fRect);
238 }
rect_intersection(SkGlyphRect a,SkGlyphRect b)239 inline SkGlyphRect rect_intersection(SkGlyphRect a, SkGlyphRect b) {
240 return skvx::max(a.fRect, b.fRect);
241 }
242 } // namespace skglyph
243
244 class SkGlyph;
245
246 // SkGlyphDigest contains a digest of information for making GPU drawing decisions. It can be
247 // referenced instead of the glyph itself in many situations. In the remote glyphs cache the
248 // SkGlyphDigest is the only information that needs to be stored in the cache.
249 class SkGlyphDigest {
250 public:
251 // Default ctor is only needed for the hash table.
252 SkGlyphDigest() = default;
253 SkGlyphDigest(size_t index, const SkGlyph& glyph);
index()254 int index() const {return fIndex; }
isEmpty()255 bool isEmpty() const {return fIsEmpty; }
isColor()256 bool isColor() const {return fIsColor; }
canDrawAsMask()257 bool canDrawAsMask() const {return fCanDrawAsMask;}
canDrawAsSDFT()258 bool canDrawAsSDFT() const {return fCanDrawAsSDFT;}
packedGlyphID()259 uint32_t packedGlyphID() const {return fPackedGlyphID;}
maxDimension()260 uint16_t maxDimension() const {return fMaxDimension; }
261
262 // Support mapping from SkPackedGlyphID stored in the digest.
GetKey(SkGlyphDigest digest)263 static uint32_t GetKey(SkGlyphDigest digest) {
264 return digest.packedGlyphID();
265 }
Hash(uint32_t packedGlyphID)266 static uint32_t Hash(uint32_t packedGlyphID) {
267 return SkGoodHash()(packedGlyphID);
268 }
269
270 private:
271 static_assert(SkPackedGlyphID::kEndData == 20);
272 uint64_t fPackedGlyphID : SkPackedGlyphID::kEndData;
273 uint64_t fIndex : SkPackedGlyphID::kEndData;
274 uint64_t fIsEmpty : 1;
275 uint64_t fIsColor : 1;
276 uint64_t fCanDrawAsMask : 1;
277 uint64_t fCanDrawAsSDFT : 1;
278 uint64_t fMaxDimension : 16;
279 };
280
281 class SkGlyph {
282 public:
283 // SkGlyph() is used for testing.
SkGlyph()284 constexpr SkGlyph() : SkGlyph{SkPackedGlyphID()} { }
285 SkGlyph(const SkGlyph&);
286 SkGlyph& operator=(const SkGlyph&);
287 SkGlyph(SkGlyph&&);
288 SkGlyph& operator=(SkGlyph&&);
289 ~SkGlyph();
SkGlyph(SkPackedGlyphID id)290 constexpr explicit SkGlyph(SkPackedGlyphID id) : fID{id} { }
291
advanceVector()292 SkVector advanceVector() const { return SkVector{fAdvanceX, fAdvanceY}; }
advanceX()293 SkScalar advanceX() const { return fAdvanceX; }
advanceY()294 SkScalar advanceY() const { return fAdvanceY; }
295
getGlyphID()296 SkGlyphID getGlyphID() const { return fID.glyphID(); }
getPackedID()297 SkPackedGlyphID getPackedID() const { return fID; }
getSubXFixed()298 SkFixed getSubXFixed() const { return fID.getSubXFixed(); }
getSubYFixed()299 SkFixed getSubYFixed() const { return fID.getSubYFixed(); }
300
301 size_t rowBytes() const;
302 size_t rowBytesUsingFormat(SkMask::Format format) const;
303
304 // Call this to set all of the metrics fields to 0 (e.g. if the scaler
305 // encounters an error measuring a glyph). Note: this does not alter the
306 // fImage, fPath, fID, fMaskFormat fields.
307 void zeroMetrics();
308
309 SkMask mask() const;
310
311 SkMask mask(SkPoint position) const;
312
313 // Image
314 // If we haven't already tried to associate an image with this glyph
315 // (i.e. setImageHasBeenCalled() returns false), then use the
316 // SkScalerContext or const void* argument to set the image.
317 bool setImage(SkArenaAlloc* alloc, SkScalerContext* scalerContext);
318 bool setImage(SkArenaAlloc* alloc, const void* image);
319
320 // Merge the from glyph into this glyph using alloc to allocate image data. Return the number
321 // of bytes allocated. Copy the width, height, top, left, format, and image into this glyph
322 // making a copy of the image using the alloc.
323 size_t setMetricsAndImage(SkArenaAlloc* alloc, const SkGlyph& from);
324
325 // Returns true if the image has been set.
setImageHasBeenCalled()326 bool setImageHasBeenCalled() const {
327 return fImage != nullptr || this->isEmpty() || this->imageTooLarge();
328 }
329
330 // Return a pointer to the path if the image exists, otherwise return nullptr.
image()331 const void* image() const { SkASSERT(this->setImageHasBeenCalled()); return fImage; }
332
333 // Return the size of the image.
334 size_t imageSize() const;
335
336 // Path
337 // If we haven't already tried to associate a path to this glyph
338 // (i.e. setPathHasBeenCalled() returns false), then use the
339 // SkScalerContext or SkPath argument to try to do so. N.B. this
340 // may still result in no path being associated with this glyph,
341 // e.g. if you pass a null SkPath or the typeface is bitmap-only.
342 //
343 // This setPath() call is sticky... once you call it, the glyph
344 // stays in its state permanently, ignoring any future calls.
345 //
346 // Returns true if this is the first time you called setPath()
347 // and there actually is a path; call path() to get it.
348 bool setPath(SkArenaAlloc* alloc, SkScalerContext* scalerContext);
349 bool setPath(SkArenaAlloc* alloc, const SkPath* path, bool hairline);
350
351 // Returns true if that path has been set.
setPathHasBeenCalled()352 bool setPathHasBeenCalled() const { return fPathData != nullptr; }
353
354 // Return a pointer to the path if it exists, otherwise return nullptr. Only works if the
355 // path was previously set.
356 const SkPath* path() const;
357 bool pathIsHairline() const;
358
359 bool setDrawable(SkArenaAlloc* alloc, SkScalerContext* scalerContext);
360 bool setDrawable(SkArenaAlloc* alloc, sk_sp<SkDrawable> drawable);
setDrawableHasBeenCalled()361 bool setDrawableHasBeenCalled() const { return fDrawableData != nullptr; }
362 SkDrawable* drawable() const;
363
364 // Format
isColor()365 bool isColor() const { return fMaskFormat == SkMask::kARGB32_Format; }
maskFormat()366 SkMask::Format maskFormat() const { return fMaskFormat; }
367 size_t formatAlignment() const;
368
369 // Bounds
maxDimension()370 int maxDimension() const { return std::max(fWidth, fHeight); }
iRect()371 SkIRect iRect() const { return SkIRect::MakeXYWH(fLeft, fTop, fWidth, fHeight); }
rect()372 SkRect rect() const { return SkRect::MakeXYWH(fLeft, fTop, fWidth, fHeight); }
glyphRect()373 SkGlyphRect glyphRect() const {
374 return {fLeft, fTop,
375 SkTo<int16_t>(fLeft + fWidth), SkTo<int16_t>(fTop + fHeight)};
376 }
left()377 int left() const { return fLeft; }
top()378 int top() const { return fTop; }
width()379 int width() const { return fWidth; }
height()380 int height() const { return fHeight; }
isEmpty()381 bool isEmpty() const {
382 // fHeight == 0 -> fWidth == 0;
383 SkASSERT(fHeight != 0 || fWidth == 0);
384 return fWidth == 0;
385 }
imageTooLarge()386 bool imageTooLarge() const { return fWidth >= kMaxGlyphWidth; }
387
388 // Make sure that the intercept information is on the glyph and return it, or return it if it
389 // already exists.
390 // * bounds - either end of the gap for the character.
391 // * scale, xPos - information about how wide the gap is.
392 // * array - accumulated gaps for many characters if not null.
393 // * count - the number of gaps.
394 void ensureIntercepts(const SkScalar bounds[2], SkScalar scale, SkScalar xPos,
395 SkScalar* array, int* count, SkArenaAlloc* alloc);
396
setImage(void * image)397 void setImage(void* image) { fImage = image; }
398
399 private:
400 // There are two sides to an SkGlyph, the scaler side (things that create glyph data) have
401 // access to all the fields. Scalers are assumed to maintain all the SkGlyph invariants. The
402 // consumer side has a tighter interface.
403 friend class RandomScalerContext;
404 friend class SkScalerContext;
405 friend class SkScalerContextProxy;
406 friend class SkScalerContext_Empty;
407 friend class SkScalerContext_FreeType;
408 friend class SkScalerContext_FreeType_Base;
409 friend class SkScalerContext_DW;
410 friend class SkScalerContext_GDI;
411 friend class SkScalerContext_Mac;
412 friend class SkStrikeClientImpl;
413 friend class SkTestScalerContext;
414 friend class SkTestSVGScalerContext;
415 friend class SkUserScalerContext;
416 friend class TestSVGTypeface;
417 friend class TestTypeface;
418
419 inline static constexpr uint16_t kMaxGlyphWidth = 1u << 13u;
420
421 // Support horizontal and vertical skipping strike-through / underlines.
422 // The caller walks the linked list looking for a match. For a horizontal underline,
423 // the fBounds contains the top and bottom of the underline. The fInterval pair contains the
424 // beginning and end of the intersection of the bounds and the glyph's path.
425 // If interval[0] >= interval[1], no intersection was found.
426 struct Intercept {
427 Intercept* fNext;
428 SkScalar fBounds[2]; // for horz underlines, the boundaries in Y
429 SkScalar fInterval[2]; // the outside intersections of the axis and the glyph
430 };
431
432 struct PathData {
433 Intercept* fIntercept{nullptr};
434 SkPath fPath;
435 bool fHasPath{false};
436 // A normal user-path will have patheffects applied to it and eventually become a dev-path.
437 // A dev-path is always a fill-path, except when it is hairline.
438 // The fPath is a dev-path, so sidecar the paths hairline status.
439 // This allows the user to avoid filling paths which should not be filled.
440 bool fHairline{false};
441 };
442
443 struct DrawableData {
444 Intercept* fIntercept{nullptr};
445 sk_sp<SkDrawable> fDrawable;
446 bool fHasDrawable{false};
447 };
448
449 size_t allocImage(SkArenaAlloc* alloc);
450
451 // path == nullptr indicates that there is no path.
452 void installPath(SkArenaAlloc* alloc, const SkPath* path, bool hairline);
453
454 // drawable == nullptr indicates that there is no path.
455 void installDrawable(SkArenaAlloc* alloc, sk_sp<SkDrawable> drawable);
456
457 // The width and height of the glyph mask.
458 uint16_t fWidth = 0,
459 fHeight = 0;
460
461 // The offset from the glyphs origin on the baseline to the top left of the glyph mask.
462 int16_t fTop = 0,
463 fLeft = 0;
464
465 // fImage must remain null if the glyph is empty or if width > kMaxGlyphWidth.
466 void* fImage = nullptr;
467
468 // Path data has tricky state. If the glyph isEmpty, then fPathData should always be nullptr,
469 // else if fPathData is not null, then a path has been requested. The fPath field of fPathData
470 // may still be null after the request meaning that there is no path for this glyph.
471 PathData* fPathData = nullptr;
472 DrawableData* fDrawableData = nullptr;
473
474 // The advance for this glyph.
475 float fAdvanceX = 0,
476 fAdvanceY = 0;
477
478 SkMask::Format fMaskFormat{SkMask::kBW_Format};
479
480 // Used by the DirectWrite scaler to track state.
481 int8_t fForceBW = 0;
482
483 // An SkGlyph can be created with just a packedID, but generally speaking some glyph factory
484 // needs to actually fill out the glyph before it can be used as part of that system.
485 SkDEBUGCODE(bool fAdvancesBoundsFormatAndInitialPathDone{false};)
486
487 SkPackedGlyphID fID;
488 };
489
490 #endif
491