1 
2 /*
3  * Copyright 2011 Google Inc.
4  *
5  * Use of this source code is governed by a BSD-style license that can be
6  * found in the LICENSE file.
7  */
8 
9 
10 #include "SkAdvancedTypefaceMetrics.h"
11 #include "SkTypes.h"
12 
13 #if defined(SK_BUILD_FOR_WIN)
14 #include <dwrite.h>
15 #endif
16 
17 #if defined(SK_BUILD_FOR_UNIX) || defined(SK_BUILD_FOR_ANDROID)
18 // forward declare structs needed for getAdvanceData() template for freetype
19 struct FT_FaceRec_;
20 typedef struct FT_FaceRec_* FT_Face;
21 #endif
22 
23 #ifdef SK_BUILD_FOR_MAC
24 #import <ApplicationServices/ApplicationServices.h>
25 #endif
26 
27 #ifdef SK_BUILD_FOR_IOS
28 #include <CoreText/CoreText.h>
29 #include <CoreGraphics/CoreGraphics.h>
30 #include <CoreFoundation/CoreFoundation.h>
31 #endif
32 
33 namespace skia_advanced_typeface_metrics_utils {
34 
35 const int16_t kInvalidAdvance = SK_MinS16;
36 const int16_t kDontCareAdvance = SK_MinS16 + 1;
37 
38 template <typename Data>
stripUninterestingTrailingAdvancesFromRange(SkAdvancedTypefaceMetrics::AdvanceMetric<Data> * range)39 void stripUninterestingTrailingAdvancesFromRange(
40                                                  SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* range) {
41     SkASSERT(false);
42 }
43 
44 template <>
stripUninterestingTrailingAdvancesFromRange(SkAdvancedTypefaceMetrics::AdvanceMetric<int16_t> * range)45 void stripUninterestingTrailingAdvancesFromRange<int16_t>(
46                                                           SkAdvancedTypefaceMetrics::AdvanceMetric<int16_t>* range) {
47     SkASSERT(range);
48 
49     int expectedAdvanceCount = range->fEndId - range->fStartId + 1;
50     if (range->fAdvance.count() < expectedAdvanceCount) {
51         return;
52     }
53 
54     for (int i = expectedAdvanceCount - 1; i >= 0; --i) {
55         if (range->fAdvance[i] != kDontCareAdvance &&
56             range->fAdvance[i] != kInvalidAdvance &&
57             range->fAdvance[i] != 0) {
58             range->fEndId = range->fStartId + i;
59             break;
60         }
61     }
62 }
63 
64 template <typename Data>
resetRange(SkAdvancedTypefaceMetrics::AdvanceMetric<Data> * range,int startId)65 void resetRange(SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* range,
66                 int startId) {
67     range->fStartId = startId;
68     range->fAdvance.setCount(0);
69 }
70 
71 template <typename Data>
appendRange(SkAutoTDelete<SkAdvancedTypefaceMetrics::AdvanceMetric<Data>> * nextSlot,int startId)72 SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* appendRange(
73         SkAutoTDelete<SkAdvancedTypefaceMetrics::AdvanceMetric<Data> >* nextSlot,
74         int startId) {
75     nextSlot->reset(new SkAdvancedTypefaceMetrics::AdvanceMetric<Data>);
76     resetRange(nextSlot->get(), startId);
77     return nextSlot->get();
78 }
79 
80 template <typename Data>
zeroWildcardsInRange(SkAdvancedTypefaceMetrics::AdvanceMetric<Data> * range)81 void zeroWildcardsInRange(
82                           SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* range) {
83     SkASSERT(false);
84 }
85 
86 template <>
zeroWildcardsInRange(SkAdvancedTypefaceMetrics::AdvanceMetric<int16_t> * range)87 void zeroWildcardsInRange<int16_t>(
88                                    SkAdvancedTypefaceMetrics::AdvanceMetric<int16_t>* range) {
89     SkASSERT(range);
90     if (range->fType != SkAdvancedTypefaceMetrics::WidthRange::kRange) {
91         return;
92     }
93     SkASSERT(range->fAdvance.count() == range->fEndId - range->fStartId + 1);
94 
95     // Zero out wildcards.
96     for (int i = 0; i < range->fAdvance.count(); ++i) {
97         if (range->fAdvance[i] == kDontCareAdvance) {
98             range->fAdvance[i] = 0;
99         }
100     }
101 }
102 
103 template <typename Data>
finishRange(SkAdvancedTypefaceMetrics::AdvanceMetric<Data> * range,int endId,typename SkAdvancedTypefaceMetrics::AdvanceMetric<Data>::MetricType type)104 void finishRange(
105         SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* range,
106         int endId,
107         typename SkAdvancedTypefaceMetrics::AdvanceMetric<Data>::MetricType
108                 type) {
109     range->fEndId = endId;
110     range->fType = type;
111     stripUninterestingTrailingAdvancesFromRange(range);
112     int newLength;
113     if (type == SkAdvancedTypefaceMetrics::AdvanceMetric<Data>::kRange) {
114         newLength = range->fEndId - range->fStartId + 1;
115     } else {
116         if (range->fEndId == range->fStartId) {
117             range->fType =
118                 SkAdvancedTypefaceMetrics::AdvanceMetric<Data>::kRange;
119         }
120         newLength = 1;
121     }
122     SkASSERT(range->fAdvance.count() >= newLength);
123     range->fAdvance.setCount(newLength);
124     zeroWildcardsInRange(range);
125 }
126 
127 template <typename Data, typename FontHandle>
getAdvanceData(FontHandle fontHandle,int num_glyphs,const uint32_t * subsetGlyphIDs,uint32_t subsetGlyphIDsLength,bool (* getAdvance)(FontHandle fontHandle,int gId,Data * data))128 SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* getAdvanceData(
129         FontHandle fontHandle,
130         int num_glyphs,
131         const uint32_t* subsetGlyphIDs,
132         uint32_t subsetGlyphIDsLength,
133         bool (*getAdvance)(FontHandle fontHandle, int gId, Data* data)) {
134     // Assuming that on average, the ASCII representation of an advance plus
135     // a space is 8 characters and the ASCII representation of a glyph id is 3
136     // characters, then the following cut offs for using different range types
137     // apply:
138     // The cost of stopping and starting the range is 7 characers
139     //  a. Removing 4 0's or don't care's is a win
140     // The cost of stopping and starting the range plus a run is 22
141     // characters
142     //  b. Removing 3 repeating advances is a win
143     //  c. Removing 2 repeating advances and 3 don't cares is a win
144     // When not currently in a range the cost of a run over a range is 16
145     // characaters, so:
146     //  d. Removing a leading 0/don't cares is a win because it is omitted
147     //  e. Removing 2 repeating advances is a win
148 
149     SkAutoTDelete<SkAdvancedTypefaceMetrics::AdvanceMetric<Data> > result;
150     SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* curRange;
151     SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* prevRange = nullptr;
152     Data lastAdvance = kInvalidAdvance;
153     int repeatedAdvances = 0;
154     int wildCardsInRun = 0;
155     int trailingWildCards = 0;
156     uint32_t subsetIndex = 0;
157 
158     // Limit the loop count to glyph id ranges provided.
159     int firstIndex = 0;
160     int lastIndex = num_glyphs;
161     if (subsetGlyphIDs) {
162         firstIndex = static_cast<int>(subsetGlyphIDs[0]);
163         lastIndex =
164                 static_cast<int>(subsetGlyphIDs[subsetGlyphIDsLength - 1]) + 1;
165     }
166     curRange = appendRange(&result, firstIndex);
167 
168     for (int gId = firstIndex; gId <= lastIndex; gId++) {
169         Data advance = kInvalidAdvance;
170         if (gId < lastIndex) {
171             // Get glyph id only when subset is nullptr, or the id is in subset.
172             SkASSERT(!subsetGlyphIDs || (subsetIndex < subsetGlyphIDsLength &&
173                     static_cast<uint32_t>(gId) <= subsetGlyphIDs[subsetIndex]));
174             if (!subsetGlyphIDs ||
175                 (subsetIndex < subsetGlyphIDsLength &&
176                  static_cast<uint32_t>(gId) == subsetGlyphIDs[subsetIndex])) {
177                 SkAssertResult(getAdvance(fontHandle, gId, &advance));
178                 ++subsetIndex;
179             } else {
180                 advance = kDontCareAdvance;
181             }
182         }
183         if (advance == lastAdvance) {
184             repeatedAdvances++;
185             trailingWildCards = 0;
186         } else if (advance == kDontCareAdvance) {
187             wildCardsInRun++;
188             trailingWildCards++;
189         } else if (curRange->fAdvance.count() ==
190                    repeatedAdvances + 1 + wildCardsInRun) {  // All in run.
191             if (lastAdvance == 0) {
192                 resetRange(curRange, gId);
193                 trailingWildCards = 0;
194             } else if (repeatedAdvances + 1 >= 2 || trailingWildCards >= 4) {
195                 finishRange(curRange, gId - 1,
196                             SkAdvancedTypefaceMetrics::WidthRange::kRun);
197                 prevRange = curRange;
198                 curRange = appendRange(&curRange->fNext, gId);
199                 trailingWildCards = 0;
200             }
201             repeatedAdvances = 0;
202             wildCardsInRun = trailingWildCards;
203             trailingWildCards = 0;
204         } else {
205             if (lastAdvance == 0 &&
206                     repeatedAdvances + 1 + wildCardsInRun >= 4) {
207                 finishRange(curRange,
208                             gId - repeatedAdvances - wildCardsInRun - 2,
209                             SkAdvancedTypefaceMetrics::WidthRange::kRange);
210                 prevRange = curRange;
211                 curRange = appendRange(&curRange->fNext, gId);
212                 trailingWildCards = 0;
213             } else if (trailingWildCards >= 4 && repeatedAdvances + 1 < 2) {
214                 finishRange(curRange,
215                             gId - trailingWildCards - 1,
216                             SkAdvancedTypefaceMetrics::WidthRange::kRange);
217                 prevRange = curRange;
218                 curRange = appendRange(&curRange->fNext, gId);
219                 trailingWildCards = 0;
220             } else if (lastAdvance != 0 &&
221                        (repeatedAdvances + 1 >= 3 ||
222                         (repeatedAdvances + 1 >= 2 && wildCardsInRun >= 3))) {
223                 finishRange(curRange,
224                             gId - repeatedAdvances - wildCardsInRun - 2,
225                             SkAdvancedTypefaceMetrics::WidthRange::kRange);
226                 curRange =
227                     appendRange(&curRange->fNext,
228                                 gId - repeatedAdvances - wildCardsInRun - 1);
229                 curRange->fAdvance.append(1, &lastAdvance);
230                 finishRange(curRange, gId - 1,
231                             SkAdvancedTypefaceMetrics::WidthRange::kRun);
232                 prevRange = curRange;
233                 curRange = appendRange(&curRange->fNext, gId);
234                 trailingWildCards = 0;
235             }
236             repeatedAdvances = 0;
237             wildCardsInRun = trailingWildCards;
238             trailingWildCards = 0;
239         }
240         curRange->fAdvance.append(1, &advance);
241         if (advance != kDontCareAdvance) {
242             lastAdvance = advance;
243         }
244     }
245     if (curRange->fStartId == lastIndex) {
246         SkASSERT(prevRange);
247         SkASSERT(prevRange->fNext->fStartId == lastIndex);
248         prevRange->fNext.free();
249     } else {
250         finishRange(curRange, lastIndex - 1,
251                     SkAdvancedTypefaceMetrics::WidthRange::kRange);
252     }
253     return result.detach();
254 }
255 
256 // Make AdvanceMetric template functions available for linking with typename
257 // WidthRange and VerticalAdvanceRange.
258 #if defined(SK_BUILD_FOR_WIN)
259 template SkAdvancedTypefaceMetrics::WidthRange* getAdvanceData(
260         HDC hdc,
261         int num_glyphs,
262         const uint32_t* subsetGlyphIDs,
263         uint32_t subsetGlyphIDsLength,
264         bool (*getAdvance)(HDC hdc, int gId, int16_t* data));
265 template SkAdvancedTypefaceMetrics::WidthRange* getAdvanceData(
266         IDWriteFontFace* fontFace,
267         int num_glyphs,
268         const uint32_t* subsetGlyphIDs,
269         uint32_t subsetGlyphIDsLength,
270         bool (*getAdvance)(IDWriteFontFace* fontFace, int gId, int16_t* data));
271 #elif defined(SK_BUILD_FOR_UNIX) || defined(SK_BUILD_FOR_ANDROID)
272 template SkAdvancedTypefaceMetrics::WidthRange* getAdvanceData(
273         FT_Face face,
274         int num_glyphs,
275         const uint32_t* subsetGlyphIDs,
276         uint32_t subsetGlyphIDsLength,
277         bool (*getAdvance)(FT_Face face, int gId, int16_t* data));
278 #elif defined(SK_BUILD_FOR_MAC) || defined(SK_BUILD_FOR_IOS)
279 template SkAdvancedTypefaceMetrics::WidthRange* getAdvanceData(
280         CTFontRef ctFont,
281         int num_glyphs,
282         const uint32_t* subsetGlyphIDs,
283         uint32_t subsetGlyphIDsLength,
284         bool (*getAdvance)(CTFontRef ctFont, int gId, int16_t* data));
285 #endif
286 template void resetRange(
287         SkAdvancedTypefaceMetrics::WidthRange* range,
288         int startId);
289 template SkAdvancedTypefaceMetrics::WidthRange* appendRange(
290         SkAutoTDelete<SkAdvancedTypefaceMetrics::WidthRange >* nextSlot,
291         int startId);
292 template void finishRange<int16_t>(
293         SkAdvancedTypefaceMetrics::WidthRange* range,
294         int endId,
295         SkAdvancedTypefaceMetrics::WidthRange::MetricType type);
296 
297 template void resetRange(
298         SkAdvancedTypefaceMetrics::VerticalAdvanceRange* range,
299         int startId);
300 template SkAdvancedTypefaceMetrics::VerticalAdvanceRange* appendRange(
301         SkAutoTDelete<SkAdvancedTypefaceMetrics::VerticalAdvanceRange >*
302             nextSlot,
303         int startId);
304 template void finishRange<SkAdvancedTypefaceMetrics::VerticalMetric>(
305         SkAdvancedTypefaceMetrics::VerticalAdvanceRange* range,
306         int endId,
307         SkAdvancedTypefaceMetrics::VerticalAdvanceRange::MetricType type);
308 
309 // additional declaration needed for testing with a face of an unknown type
310 template SkAdvancedTypefaceMetrics::WidthRange* getAdvanceData(
311         void* fontData,
312         int num_glyphs,
313         const uint32_t* subsetGlyphIDs,
314         uint32_t subsetGlyphIDsLength,
315         bool (*getAdvance)(void* fontData, int gId, int16_t* data));
316 
317 } // namespace skia_advanced_typeface_metrics_utils
318