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
19struct FT_FaceRec;
20typedef 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
33namespace skia_advanced_typeface_metrics_utils {
34
35const int16_t kInvalidAdvance = SK_MinS16;
36const int16_t kDontCareAdvance = SK_MinS16 + 1;
37
38template <typename Data>
39void stripUninterestingTrailingAdvancesFromRange(
40                                                 SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* range) {
41    SkASSERT(false);
42}
43
44template <>
45void 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
64template <typename Data>
65void resetRange(SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* range,
66                int startId) {
67    range->fStartId = startId;
68    range->fAdvance.setCount(0);
69}
70
71template <typename Data>
72SkAdvancedTypefaceMetrics::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
80template <typename Data>
81void zeroWildcardsInRange(
82                          SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* range) {
83    SkASSERT(false);
84}
85
86template <>
87void 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
103template <typename Data>
104void 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
127template <typename Data, typename FontHandle>
128SkAdvancedTypefaceMetrics::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 = NULL;
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 NULL, 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)
259template 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));
265template 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)
272template 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)
279template 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
286template void resetRange(
287        SkAdvancedTypefaceMetrics::WidthRange* range,
288        int startId);
289template SkAdvancedTypefaceMetrics::WidthRange* appendRange(
290        SkAutoTDelete<SkAdvancedTypefaceMetrics::WidthRange >* nextSlot,
291        int startId);
292template void finishRange<int16_t>(
293        SkAdvancedTypefaceMetrics::WidthRange* range,
294        int endId,
295        SkAdvancedTypefaceMetrics::WidthRange::MetricType type);
296
297template void resetRange(
298        SkAdvancedTypefaceMetrics::VerticalAdvanceRange* range,
299        int startId);
300template SkAdvancedTypefaceMetrics::VerticalAdvanceRange* appendRange(
301        SkAutoTDelete<SkAdvancedTypefaceMetrics::VerticalAdvanceRange >*
302            nextSlot,
303        int startId);
304template 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
310template 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