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; 31 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 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 50 static SkScalar scale_from_font_units(int16_t val, uint16_t emSize) { 51 return from_font_units(SkIntToScalar(val), emSize); 52 } 53 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 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 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 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. 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