1 /*
2 * Copyright 2016 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 "SkBitSet.h"
9 #include "SkPDFMakeCIDGlyphWidthsArray.h"
10 #include "SkPaint.h"
11 #include "SkGlyphCache.h"
12
13 // TODO(halcanary): Write unit tests for SkPDFMakeCIDGlyphWidthsArray().
14
15 // TODO(halcanary): The logic in this file originated in several
16 // disparate places. I feel sure that someone could simplify this
17 // down to a single easy-to-read function.
18
19 namespace {
20
21 struct AdvanceMetric {
22 enum MetricType {
23 kDefault, // Default advance: fAdvance.count = 1
24 kRange, // Advances for a range: fAdvance.count = fEndID-fStartID
25 kRun // fStartID-fEndID have same advance: fAdvance.count = 1
26 };
27 MetricType fType;
28 uint16_t fStartId;
29 uint16_t fEndId;
30 SkTDArray<int16_t> fAdvance;
AdvanceMetric__anon52d149140111::AdvanceMetric31 AdvanceMetric(uint16_t startId) : fStartId(startId) {}
32 AdvanceMetric(AdvanceMetric&&) = default;
33 AdvanceMetric& operator=(AdvanceMetric&& other) = default;
34 AdvanceMetric(const AdvanceMetric&) = delete;
35 AdvanceMetric& operator=(const AdvanceMetric&) = delete;
36 };
37 const int16_t kInvalidAdvance = SK_MinS16;
38 const int16_t kDontCareAdvance = SK_MinS16 + 1;
39 } // namespace
40
41 // scale from em-units to base-1000, returning as a SkScalar
from_font_units(SkScalar scaled,uint16_t emSize)42 static SkScalar from_font_units(SkScalar scaled, uint16_t emSize) {
43 if (emSize == 1000) {
44 return scaled;
45 } else {
46 return scaled * 1000 / emSize;
47 }
48 }
49
scale_from_font_units(int16_t val,uint16_t emSize)50 static SkScalar scale_from_font_units(int16_t val, uint16_t emSize) {
51 return from_font_units(SkIntToScalar(val), emSize);
52 }
53
strip_uninteresting_trailing_advances_from_range(AdvanceMetric * range)54 static void strip_uninteresting_trailing_advances_from_range(
55 AdvanceMetric* range) {
56 SkASSERT(range);
57
58 int expectedAdvanceCount = range->fEndId - range->fStartId + 1;
59 if (range->fAdvance.count() < expectedAdvanceCount) {
60 return;
61 }
62
63 for (int i = expectedAdvanceCount - 1; i >= 0; --i) {
64 if (range->fAdvance[i] != kDontCareAdvance &&
65 range->fAdvance[i] != kInvalidAdvance &&
66 range->fAdvance[i] != 0) {
67 range->fEndId = range->fStartId + i;
68 break;
69 }
70 }
71 }
72
zero_wildcards_in_range(AdvanceMetric * range)73 static void zero_wildcards_in_range(AdvanceMetric* range) {
74 SkASSERT(range);
75 if (range->fType != AdvanceMetric::kRange) {
76 return;
77 }
78 SkASSERT(range->fAdvance.count() == range->fEndId - range->fStartId + 1);
79
80 // Zero out wildcards.
81 for (int i = 0; i < range->fAdvance.count(); ++i) {
82 if (range->fAdvance[i] == kDontCareAdvance) {
83 range->fAdvance[i] = 0;
84 }
85 }
86 }
87
finish_range(AdvanceMetric * range,int endId,AdvanceMetric::MetricType type)88 static void finish_range(
89 AdvanceMetric* range,
90 int endId,
91 AdvanceMetric::MetricType type) {
92 range->fEndId = endId;
93 range->fType = type;
94 strip_uninteresting_trailing_advances_from_range(range);
95 int newLength;
96 if (type == AdvanceMetric::kRange) {
97 newLength = range->fEndId - range->fStartId + 1;
98 } else {
99 if (range->fEndId == range->fStartId) {
100 range->fType = AdvanceMetric::kRange;
101 }
102 newLength = 1;
103 }
104 SkASSERT(range->fAdvance.count() >= newLength);
105 range->fAdvance.setCount(newLength);
106 zero_wildcards_in_range(range);
107 }
108
compose_advance_data(const AdvanceMetric & range,uint16_t emSize,int16_t * defaultAdvance,SkPDFArray * result)109 static void compose_advance_data(const AdvanceMetric& range,
110 uint16_t emSize,
111 int16_t* defaultAdvance,
112 SkPDFArray* result) {
113 switch (range.fType) {
114 case AdvanceMetric::kDefault: {
115 SkASSERT(range.fAdvance.count() == 1);
116 *defaultAdvance = range.fAdvance[0];
117 break;
118 }
119 case AdvanceMetric::kRange: {
120 auto advanceArray = sk_make_sp<SkPDFArray>();
121 for (int j = 0; j < range.fAdvance.count(); j++)
122 advanceArray->appendScalar(
123 scale_from_font_units(range.fAdvance[j], emSize));
124 result->appendInt(range.fStartId);
125 result->appendObject(std::move(advanceArray));
126 break;
127 }
128 case AdvanceMetric::kRun: {
129 SkASSERT(range.fAdvance.count() == 1);
130 result->appendInt(range.fStartId);
131 result->appendInt(range.fEndId);
132 result->appendScalar(
133 scale_from_font_units(range.fAdvance[0], emSize));
134 break;
135 }
136 }
137 }
138
139 /** Retrieve advance data for glyphs. Used by the PDF backend. */
140 // TODO(halcanary): this function is complex enough to need its logic
141 // tested with unit tests.
SkPDFMakeCIDGlyphWidthsArray(SkGlyphCache * cache,const SkBitSet * subset,uint16_t emSize,int16_t * defaultAdvance)142 sk_sp<SkPDFArray> SkPDFMakeCIDGlyphWidthsArray(SkGlyphCache* cache,
143 const SkBitSet* subset,
144 uint16_t emSize,
145 int16_t* defaultAdvance) {
146 // Assuming that on average, the ASCII representation of an advance plus
147 // a space is 8 characters and the ASCII representation of a glyph id is 3
148 // characters, then the following cut offs for using different range types
149 // apply:
150 // The cost of stopping and starting the range is 7 characers
151 // a. Removing 4 0's or don't care's is a win
152 // The cost of stopping and starting the range plus a run is 22
153 // characters
154 // b. Removing 3 repeating advances is a win
155 // c. Removing 2 repeating advances and 3 don't cares is a win
156 // When not currently in a range the cost of a run over a range is 16
157 // characaters, so:
158 // d. Removing a leading 0/don't cares is a win because it is omitted
159 // e. Removing 2 repeating advances is a win
160
161 auto result = sk_make_sp<SkPDFArray>();
162 int num_glyphs = SkToInt(cache->getGlyphCount());
163
164 bool prevRange = false;
165
166 int16_t lastAdvance = kInvalidAdvance;
167 int repeatedAdvances = 0;
168 int wildCardsInRun = 0;
169 int trailingWildCards = 0;
170
171 // Limit the loop count to glyph id ranges provided.
172 int lastIndex = num_glyphs;
173 if (subset) {
174 while (!subset->has(lastIndex - 1) && lastIndex > 0) {
175 --lastIndex;
176 }
177 }
178 AdvanceMetric curRange(0);
179
180 for (int gId = 0; gId <= lastIndex; gId++) {
181 int16_t advance = kInvalidAdvance;
182 if (gId < lastIndex) {
183 if (!subset || 0 == gId || subset->has(gId)) {
184 advance = (int16_t)cache->getGlyphIDAdvance(gId).fAdvanceX;
185 } else {
186 advance = kDontCareAdvance;
187 }
188 }
189 if (advance == lastAdvance) {
190 repeatedAdvances++;
191 trailingWildCards = 0;
192 } else if (advance == kDontCareAdvance) {
193 wildCardsInRun++;
194 trailingWildCards++;
195 } else if (curRange.fAdvance.count() ==
196 repeatedAdvances + 1 + wildCardsInRun) { // All in run.
197 if (lastAdvance == 0) {
198 curRange.fStartId = gId; // reset
199 curRange.fAdvance.setCount(0);
200 trailingWildCards = 0;
201 } else if (repeatedAdvances + 1 >= 2 || trailingWildCards >= 4) {
202 finish_range(&curRange, gId - 1, AdvanceMetric::kRun);
203 compose_advance_data(curRange, emSize, defaultAdvance, result.get());
204 prevRange = true;
205 curRange = AdvanceMetric(gId);
206 trailingWildCards = 0;
207 }
208 repeatedAdvances = 0;
209 wildCardsInRun = trailingWildCards;
210 trailingWildCards = 0;
211 } else {
212 if (lastAdvance == 0 &&
213 repeatedAdvances + 1 + wildCardsInRun >= 4) {
214 finish_range(&curRange,
215 gId - repeatedAdvances - wildCardsInRun - 2,
216 AdvanceMetric::kRange);
217 compose_advance_data(curRange, emSize, defaultAdvance, result.get());
218 prevRange = true;
219 curRange = AdvanceMetric(gId);
220 trailingWildCards = 0;
221 } else if (trailingWildCards >= 4 && repeatedAdvances + 1 < 2) {
222 finish_range(&curRange, gId - trailingWildCards - 1,
223 AdvanceMetric::kRange);
224 compose_advance_data(curRange, emSize, defaultAdvance, result.get());
225 prevRange = true;
226 curRange = AdvanceMetric(gId);
227 trailingWildCards = 0;
228 } else if (lastAdvance != 0 &&
229 (repeatedAdvances + 1 >= 3 ||
230 (repeatedAdvances + 1 >= 2 && wildCardsInRun >= 3))) {
231 finish_range(&curRange,
232 gId - repeatedAdvances - wildCardsInRun - 2,
233 AdvanceMetric::kRange);
234 compose_advance_data(curRange, emSize, defaultAdvance, result.get());
235 curRange =
236 AdvanceMetric(gId - repeatedAdvances - wildCardsInRun - 1);
237 curRange.fAdvance.append(1, &lastAdvance);
238 finish_range(&curRange, gId - 1, AdvanceMetric::kRun);
239 compose_advance_data(curRange, emSize, defaultAdvance, result.get());
240 prevRange = true;
241 curRange = AdvanceMetric(gId);
242 trailingWildCards = 0;
243 }
244 repeatedAdvances = 0;
245 wildCardsInRun = trailingWildCards;
246 trailingWildCards = 0;
247 }
248 curRange.fAdvance.append(1, &advance);
249 if (advance != kDontCareAdvance) {
250 lastAdvance = advance;
251 }
252 }
253 if (curRange.fStartId == lastIndex) {
254 if (!prevRange) {
255 return nullptr; // https://crbug.com/567031
256 }
257 } else {
258 finish_range(&curRange, lastIndex - 1, AdvanceMetric::kRange);
259 compose_advance_data(curRange, emSize, defaultAdvance, result.get());
260 }
261 return result;
262 }
263