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 "src/pdf/SkPDFMakeCIDGlyphWidthsArray.h"
9
10#include "include/core/SkPaint.h"
11#include "include/private/SkTo.h"
12#include "src/core/SkScalerCache.h"
13#include "src/core/SkStrikeSpec.h"
14#include "src/pdf/SkPDFGlyphUse.h"
15
16#include <algorithm>
17#include <vector>
18
19// TODO(halcanary): Write unit tests for SkPDFMakeCIDGlyphWidthsArray().
20
21// TODO(halcanary): The logic in this file originated in several
22// disparate places.  I feel sure that someone could simplify this
23// down to a single easy-to-read function.
24
25namespace {
26
27// scale from em-units to base-1000, returning as a SkScalar
28SkScalar from_font_units(SkScalar scaled, uint16_t emSize) {
29    if (emSize == 1000) {
30        return scaled;
31    } else {
32        return scaled * 1000 / emSize;
33    }
34}
35
36SkScalar scale_from_font_units(int16_t val, uint16_t emSize) {
37    return from_font_units(SkIntToScalar(val), emSize);
38}
39
40// Unfortunately poppler does not appear to respect the default width setting.
41#if defined(SK_PDF_CAN_USE_DW)
42int16_t findMode(SkSpan<const int16_t> advances) {
43    if (advances.empty()) {
44        return 0;
45    }
46
47    int16_t previousAdvance = advances[0];
48    int16_t currentModeAdvance = advances[0];
49    size_t currentCount = 1;
50    size_t currentModeCount = 1;
51
52    for (size_t i = 1; i < advances.size(); ++i) {
53        if (advances[i] == previousAdvance) {
54            ++currentCount;
55        } else {
56            if (currentCount > currentModeCount) {
57                currentModeAdvance = previousAdvance;
58                currentModeCount = currentCount;
59            }
60            previousAdvance = advances[i];
61            currentCount = 1;
62        }
63    }
64
65    return currentCount > currentModeCount ? previousAdvance : currentModeAdvance;
66}
67#endif
68} // namespace
69
70/** Retrieve advance data for glyphs. Used by the PDF backend. */
71// TODO(halcanary): this function is complex enough to need its logic
72// tested with unit tests.
73std::unique_ptr<SkPDFArray> SkPDFMakeCIDGlyphWidthsArray(const SkTypeface& typeface,
74                                                         const SkPDFGlyphUse& subset,
75                                                         SkScalar* defaultAdvance) {
76    // There are two ways of expressing advances
77    //
78    // range: " gfid [adv.ances adv.ances ... adv.ances]"
79    //   run: " gfid gfid adv.ances"
80    //
81    // Assuming that on average
82    // the ASCII representation of an advance plus a space is 10 characters
83    // the ASCII representation of a glyph id plus a space is 4 characters
84    // the ASCII representation of unused gid plus a space in a range is 2 characters
85    //
86    // When not in a range or run
87    //  a. Skipping don't cares or defaults is a win (trivial)
88    //  b. Run wins for 2+ repeats " gid gid adv.ances"
89    //                             " gid [adv.ances adv.ances]"
90    //     rule: 2+ repeats create run as long as possible, else start range
91    //
92    // When in a range
93    // Cost of stopping and starting a range is 8 characters  "] gid ["
94    //  c. Skipping defaults is always a win                  " adv.ances"
95    //     rule: end range if default seen
96    //  d. Skipping 4+ don't cares is a win                   " 0 0 0 0"
97    //     rule: end range if 4+ don't cares
98    // Cost of stop and start range plus run is 28 characters "] gid gid adv.ances gid ["
99    //  e. Switching for 2+ repeats and 4+ don't cares wins   " 0 0 adv.ances 0 0 adv.ances"
100    //     rule: end range for 2+ repeats with 4+ don't cares
101    //  f. Switching for 3+ repeats wins                      " adv.ances adv.ances adv.ances"
102    //     rule: end range for 3+ repeats
103
104    int emSize;
105    SkStrikeSpec strikeSpec = SkStrikeSpec::MakePDFVector(typeface, &emSize);
106    SkBulkGlyphMetricsAndPaths paths{strikeSpec};
107
108    auto result = SkPDFMakeArray();
109
110    std::vector<SkGlyphID> glyphIDs;
111    subset.getSetValues([&](unsigned index) {
112        glyphIDs.push_back(SkToU16(index));
113    });
114    auto glyphs = paths.glyphs(SkMakeSpan(glyphIDs));
115
116#if defined(SK_PDF_CAN_USE_DW)
117    std::vector<int16_t> advances;
118    advances.reserve_back(glyphs.size());
119    for (const SkGlyph* glyph : glyphs) {
120        advances.push_back((int16_t)glyph->advanceX());
121    }
122    std::sort(advances.begin(), advances.end());
123    int16_t modeAdvance = findMode(SkMakeSpan(advances));
124    *defaultAdvance = scale_from_font_units(modeAdvance, emSize);
125#else
126    *defaultAdvance = 0;
127#endif
128
129    for (size_t i = 0; i < glyphs.size(); ++i) {
130        int16_t advance = (int16_t)glyphs[i]->advanceX();
131
132#if defined(SK_PDF_CAN_USE_DW)
133        // a. Skipping don't cares or defaults is a win (trivial)
134        if (advance == modeAdvance) {
135            continue;
136        }
137#endif
138
139        // b. 2+ repeats create run as long as possible, else start range
140        {
141            size_t j = i + 1; // j is always one past the last known repeat
142            for (; j < glyphs.size(); ++j) {
143                int16_t next_advance = (int16_t)glyphs[j]->advanceX();
144                if (advance != next_advance) {
145                    break;
146                }
147            }
148            if (j - i >= 2) {
149                result->appendInt(glyphs[i]->getGlyphID());
150                result->appendInt(glyphs[j - 1]->getGlyphID());
151                result->appendScalar(scale_from_font_units(advance, emSize));
152                i = j - 1;
153                continue;
154            }
155        }
156
157        {
158            result->appendInt(glyphs[i]->getGlyphID());
159            auto advanceArray = SkPDFMakeArray();
160            advanceArray->appendScalar(scale_from_font_units(advance, emSize));
161            size_t j = i + 1; // j is always one past the last output
162            for (; j < glyphs.size(); ++j) {
163                advance = (int16_t)glyphs[j]->advanceX();
164#if defined(SK_PDF_CAN_USE_DW)
165                // c. end range if default seen
166                if (advance == modeAdvance) {
167                    break;
168                }
169#endif
170
171                int dontCares = glyphs[j]->getGlyphID() - glyphs[j - 1]->getGlyphID() - 1;
172                // d. end range if 4+ don't cares
173                if (dontCares >= 4) {
174                    break;
175                }
176
177                int16_t next_advance = 0;
178                // e. end range for 2+ repeats with 4+ don't cares
179                if (j + 1 < glyphs.size()) {
180                    next_advance = (int16_t)glyphs[j+1]->advanceX();
181                    int next_dontCares = glyphs[j+1]->getGlyphID() - glyphs[j]->getGlyphID() - 1;
182                    if (advance == next_advance && dontCares + next_dontCares >= 4) {
183                        break;
184                    }
185                }
186
187                // f. end range for 3+ repeats
188                if (j + 2 < glyphs.size() && advance == next_advance) {
189                    next_advance = (int16_t)glyphs[j+2]->advanceX();
190                    if (advance == next_advance) {
191                        break;
192                    }
193                }
194
195                while (dontCares --> 0) {
196                    advanceArray->appendScalar(0);
197                }
198                advanceArray->appendScalar(scale_from_font_units(advance, emSize));
199            }
200            result->appendObject(std::move(advanceArray));
201            i = j - 1;
202        }
203    }
204
205    return result;
206}
207