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