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#ifndef SkGlyphBuffer_DEFINED
9#define SkGlyphBuffer_DEFINED
10
11#include "src/core/SkEnumerate.h"
12#include "src/core/SkGlyph.h"
13#include "src/core/SkZip.h"
14
15class SkStrikeForGPU;
16struct SkGlyphPositionRoundingSpec;
17
18// SkSourceGlyphBuffer is the source of glyphs between the different stages of character drawing.
19// It starts with the glyphs and positions from the SkGlyphRun as the first source. When glyphs
20// are reject by a stage they become the source for the next stage.
21class SkSourceGlyphBuffer {
22public:
23 SkSourceGlyphBuffer() = default;
24
25 void setSource(SkZip<const SkGlyphID, const SkPoint> source) {
26 this->~SkSourceGlyphBuffer();
27 new (this) SkSourceGlyphBuffer{source};
28 }
29
30 void reset();
31
32 void reject(size_t index) {
33 SkASSERT(index < fSource.size());
34 if (!this->sourceIsRejectBuffers()) {
35 // Need to expand the buffers for first use. All other reject sets will be fewer than
36 // this one.
37 auto [glyphID, pos] = fSource[index];
38 fRejectedGlyphIDs.push_back(glyphID);
39 fRejectedPositions.push_back(pos);
40 fRejectSize++;
41 } else {
42 SkASSERT(fRejectSize < fRejects.size());
43 fRejects[fRejectSize++] = fSource[index];
44 }
45 }
46
47 void reject(size_t index, int rejectedMaxDimension) {
48 fRejectedMaxDimension = std::max(fRejectedMaxDimension, rejectedMaxDimension);
49 this->reject(index);
50 }
51
52 SkZip<const SkGlyphID, const SkPoint> flipRejectsToSource() {
53 fRejects = SkMakeZip(fRejectedGlyphIDs, fRejectedPositions).first(fRejectSize);
54 fSource = fRejects;
55 fRejectSize = 0;
56 fSourceMaxDimension = fRejectedMaxDimension;
57 fRejectedMaxDimension = 0;
58 return fSource;
59 }
60
61 SkZip<const SkGlyphID, const SkPoint> source() const { return fSource; }
62
63 int rejectedMaxDimension() const { return fSourceMaxDimension; }
64
65private:
66 SkSourceGlyphBuffer(const SkZip<const SkGlyphID, const SkPoint>& source) {
67 fSource = source;
68 }
69 bool sourceIsRejectBuffers() const {
70 return fSource.get<0>().data() == fRejectedGlyphIDs.data();
71 }
72
73 SkZip<const SkGlyphID, const SkPoint> fSource;
74 size_t fRejectSize{0};
75 int fSourceMaxDimension{0};
76 int fRejectedMaxDimension{0};
77 SkZip<SkGlyphID, SkPoint> fRejects;
78 SkSTArray<4, SkGlyphID> fRejectedGlyphIDs;
79 SkSTArray<4, SkPoint> fRejectedPositions;
80};
81
82// A memory format that allows an SkPackedGlyphID, SkGlyph*, and SkPath* to occupy the same
83// memory. This allows SkPackedGlyphIDs as input, and SkGlyph*/SkPath* as output using the same
84// memory.
85class SkGlyphVariant {
86public:
87 SkGlyphVariant() : fV{nullptr} { }
88 SkGlyphVariant& operator= (SkPackedGlyphID packedID) {
89 fV.packedID = packedID;
90 SkDEBUGCODE(fTag = kPackedID);
91 return *this;
92 }
93 SkGlyphVariant& operator= (SkGlyph* glyph) {
94 fV.glyph = glyph;
95 SkDEBUGCODE(fTag = kGlyph);
96 return *this;
97
98 }
99 SkGlyphVariant& operator= (const SkPath* path) {
100 fV.path = path;
101 SkDEBUGCODE(fTag = kPath);
102 return *this;
103 }
104
105 SkGlyph* glyph() const {
106 SkASSERT(fTag == kGlyph);
107 return fV.glyph;
108 }
109 const SkPath* path() const {
110 SkASSERT(fTag == kPath);
111 return fV.path;
112 }
113 SkPackedGlyphID packedID() const {
114 SkASSERT(fTag == kPackedID);
115 return fV.packedID;
116 }
117
118 operator SkPackedGlyphID() const { return this->packedID(); }
119 operator SkGlyph*() const { return this->glyph(); }
120 operator const SkPath*() const { return this->path(); }
121
122private:
123 union {
124 SkGlyph* glyph;
125 const SkPath* path;
126 SkPackedGlyphID packedID;
127 } fV;
128
129#ifdef SK_DEBUG
130 enum {
131 kEmpty,
132 kPackedID,
133 kGlyph,
134 kPath
135 } fTag{kEmpty};
136#endif
137};
138
139// A buffer for converting SkPackedGlyph to SkGlyph* or SkPath*. Initially the buffer contains
140// SkPackedGlyphIDs, but those are used to lookup SkGlyph*/SkPath* which are then copied over the
141// SkPackedGlyphIDs.
142class SkDrawableGlyphBuffer {
143public:
144 void ensureSize(size_t size);
145
146 // Load the buffer with SkPackedGlyphIDs and positions at (0, 0) ready to finish positioning
147 // during drawing.
148 void startSource(const SkZip<const SkGlyphID, const SkPoint>& source);
149
150 // Load the buffer with SkPackedGlyphIDs and positions using the device transform.
151 void startBitmapDevice(
152 const SkZip<const SkGlyphID, const SkPoint>& source,
153 SkPoint origin, const SkMatrix& viewMatrix,
154 const SkGlyphPositionRoundingSpec& roundingSpec);
155
156 // Load the buffer with SkPackedGlyphIDs, calculating positions so they can be constant.
157 //
158 // We are looking for constant values for the x,y positions for all the glyphs that are not
159 // dependant on the device origin mapping Q such that we can just add a new value to translate
160 // all the glyph positions to a new device origin mapping Q'. We want (cx,cy,0) + [Q'](0,0,1)
161 // draw the blob with device origin Q'. Ultimately we show there is an integer solution for
162 // the glyph positions where (ix,iy,0) + ([Q'](0,0,1) + (sx,sy,0)) both parts of the top
163 // level + are integers, and preserve all the flooring properties.
164 //
165 // Given (px,py) the glyph origin in source space. The glyph origin in device space (x,y) is:
166 // (x,y,1) = Floor([R][V][O](px,py,1))
167 // where:
168 // * R - is the rounding matrix given as translate(sampling_freq_x/2, sampling_freq_y/2).
169 // * V - is the mapping from source space to device space.
170 // * O - is the blob origin given, as translate(origin.x(), origin.y()).
171 // * (px,py,1) - is the vector of the glyph origin in source space. There is a position for
172 // each glyph.
173 //
174 // It is given that if there is a change in position from V to V', and O to O' that the upper
175 // 2x2 of V and V' are the same.
176 //
177 // The three matrices R,V, and O constitute the device mapping [Q] = [R][V][O], and the
178 // device origin is given by q = [Q](0,0,1). Thus,
179 // (x,y,1) = Floor([Q](0,0,1) + [V](px,py,0)) = Floor(q + [V](px,py,0))
180 // Note: [V](px,py,0) is the vector transformed without the translation portion of V. That
181 // translation of V is accounted for in q.
182 //
183 // If we want to translate the blob from the device mapping Q to the device mapping
184 // [Q'] = [R'][V'][O], we can use the following translation. Restate as q' - q.
185 // (x',y',1) = Floor(q + [V](px,py,0) + q' - q).
186 //
187 // We are given that q' - q is an integer translation. We can move the integer translation out
188 // from the Floor expression as:
189 // (x',y',1) = Floor(q + [V](px,py,0)) + q' - q (1)
190 //
191 // We can now see that (cx,cy,0) is constructed by dropping q' from above.
192 // (cx,cy,0) = Floor(q + [V](px,py,0)) - q
193 //
194 // Notice that cx and cy are not guaranteed to be integers because q is not
195 // constrained to be integer; only q' - q is constrained to be an integer.
196 //
197 // Let Floor(q) be the integer portion the vector elements and {q} be the fractional portion
198 // which is calculated as q - Floor(q). This vector has a zero in the third place due to the
199 // subtraction.
200 // Rewriting (1) with this substitution of Floor(q) + {q} for q.
201 // (x',y',1) = Floor(q + [V](px,py,0)) + q' - q
202 // becomes,
203 // (x',y',1) = Floor(Floor(q) + {q} + [V](px,py,0)) + q' - (q + {q})
204 // simplifying by moving Floor(q) out of the Floor() because it is integer,
205 // (x',y',1) = Floor({q} + [V](px,py,0)) + q' + Floor(q) - Floor(q) - {q}
206 // removing terms that result in zero gives,
207 // (x',y',1) = Floor({q} + [V](px,py,0)) + q' - {q}
208 // Notice that q' - {q} and Floor({q} + [V](px,py,0)) are integer.
209 // Let,
210 // (ix,iy,0) = Floor({q} + [V](px,py,0)),
211 // (sx,sy,0) = -{q}.
212 // I call the (sx,sy,0) value the residual.
213 // Thus,
214 // (x',y',1) = (ix,iy,0) + (q' + (sx,sy,0)). (2)
215 //
216 // As a matter of practicality, we have the following already calculated for sub-pixel
217 // positioning, and use it to calculate (ix,iy,0):
218 // (fx,fy,1) = [R][V][O](px,py,1)
219 // = [Q](0,0,1) + [V](px,py,0)
220 // = q + [V](px,py,0)
221 // = Floor(q) + {q} + [V](px,py,0)
222 // So,
223 // (ix,iy,0) = Floor((fx,fy,1) - Floor(q)).
224 //
225 // When calculating [Q'] = [R][V'][O'] we don't have the values for [R]. Notice that [R] is a
226 // post translation to [V'][O']. This means that the values of R are added directly to the
227 // translation values of [V'][O']. So, if [V'][O'](0,0,1) results in the vector (tx,ty,1)
228 // then [R](tx,ty,0) = (tx + rx, ty + ry, 0). So, in practice we don't have the full [Q'] what
229 // is available is [Q''] = [V'][O']. We can add the rounding terms to the residual
230 // to account for not having [R]. Substituting -{q} for (sx,sy,0) in (2), gives:
231 // (x',y',1) = (ix,iy,0) + (q' - {q}).
232 // = (ix,iy,0) + ([Q'](0,0,1) - {q})
233 // = (ix,iy,0) + ([R][V'][O'](0,0,1) - {q})
234 // = (ix,iy,0) + ((rx,ry,0) + [V'][O'](0,0,1) - {q})
235 // = (ix,iy,0) + ([V'][O'](0,0,1) + (rx,ry,0) - {q}.
236 // So we redefine the residual to include the needed rounding terms.
237 // (sx',sy',0) = (rx,ry,0) - (q - Floor(q))
238 // = (rx,ry,0) + Floor(q) - q.
239 //
240 // Putting it all together:
241 // Q'' = [V'][O'](0,0,1)
242 // q'' = Q''(0, 0, 1)
243 // (x',y',1) = (ix,iy,0) + (q'' + (sx',sy',0)).
244
245
246 // Returns the residual -- (sx',sy',0).
247 SkPoint startGPUDevice(
248 const SkZip<const SkGlyphID, const SkPoint>& source,
249 SkPoint origin, const SkMatrix& viewMatrix,
250 const SkGlyphPositionRoundingSpec& roundingSpec);
251
252 // The input of SkPackedGlyphIDs
253 SkZip<SkGlyphVariant, SkPoint> input() {
254 SkASSERT(fPhase == kInput);
255 SkDEBUGCODE(fPhase = kProcess);
256 return SkZip<SkGlyphVariant, SkPoint>{fInputSize, fMultiBuffer, fPositions};
257 }
258
259 // Store the glyph in the next drawable slot, using the position information located at index
260 // from.
261 void push_back(SkGlyph* glyph, size_t from) {
262 SkASSERT(fPhase == kProcess);
263 SkASSERT(fDrawableSize <= from);
264 fPositions[fDrawableSize] = fPositions[from];
265 fMultiBuffer[fDrawableSize] = glyph;
266 fDrawableSize++;
267 }
268
269 // Store the path in the next drawable slot, using the position information located at index
270 // from.
271 void push_back(const SkPath* path, size_t from) {
272 SkASSERT(fPhase == kProcess);
273 SkASSERT(fDrawableSize <= from);
274 fPositions[fDrawableSize] = fPositions[from];
275 fMultiBuffer[fDrawableSize] = path;
276 fDrawableSize++;
277 }
278
279 // The result after a series of push_backs of drawable SkGlyph* or SkPath*.
280 SkZip<SkGlyphVariant, SkPoint> drawable() {
281 SkASSERT(fPhase == kProcess);
282 SkDEBUGCODE(fPhase = kDraw);
283 return SkZip<SkGlyphVariant, SkPoint>{fDrawableSize, fMultiBuffer, fPositions};
284 }
285
286 bool drawableIsEmpty() const {
287 SkASSERT(fPhase == kProcess || fPhase == kDraw);
288 return fDrawableSize == 0;
289 }
290
291 void reset();
292
293 template <typename Fn>
294 void forEachGlyphID(Fn&& fn) {
295 for (auto [i, packedID, pos] : SkMakeEnumerate(this->input())) {
296 fn(i, packedID.packedID(), pos);
297 }
298 }
299
300private:
301 size_t fMaxSize{0};
302 size_t fInputSize{0};
303 size_t fDrawableSize{0};
304 SkAutoTMalloc<SkGlyphVariant> fMultiBuffer;
305 SkAutoTMalloc<SkPoint> fPositions;
306
307#ifdef SK_DEBUG
308 enum {
309 kReset,
310 kInput,
311 kProcess,
312 kDraw
313 } fPhase{kReset};
314#endif
315};
316#endif // SkGlyphBuffer_DEFINED
317