Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2019 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 "SkCharToGlyphCache.h" |
| 9 | #include "../private/SkTFitsIn.h" |
| 10 | |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 11 | SkCharToGlyphCache::SkCharToGlyphCache() { |
Mike Reed | b07e9a8 | 2019-04-19 10:02:10 -0400 | [diff] [blame] | 12 | this->reset(); |
| 13 | } |
| 14 | |
| 15 | SkCharToGlyphCache::~SkCharToGlyphCache() {} |
| 16 | |
| 17 | void SkCharToGlyphCache::reset() { |
| 18 | fK32.reset(); |
| 19 | fV16.reset(); |
| 20 | |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 21 | // Add sentinels so we can always rely on these to stop linear searches (in either direction) |
| 22 | // Neither is a legal unichar, so we don't care what glyphID we use. |
| 23 | // |
| 24 | *fK32.append() = 0x80000000; *fV16.append() = 0; |
| 25 | *fK32.append() = 0x7FFFFFFF; *fV16.append() = 0; |
| 26 | |
| 27 | fDenom = 0; |
| 28 | } |
| 29 | |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 30 | // Determined experimentally. For N much larger, the slope technique is faster. |
| 31 | // For N much smaller, a simple search is faster. |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 32 | // |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 33 | constexpr int kSmallCountLimit = 16; |
| 34 | |
| 35 | // To use slope technique we need at least 2 real entries (+2 sentinels) hence the min of 4 |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 36 | // |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 37 | constexpr int kMinCountForSlope = 4; |
| 38 | |
| 39 | static int find_simple(const SkUnichar base[], int count, SkUnichar value) { |
| 40 | int index; |
| 41 | for (index = 0;; ++index) { |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 42 | if (value <= base[index]) { |
| 43 | if (value < base[index]) { |
| 44 | index = ~index; // not found |
| 45 | } |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 46 | break; |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 47 | } |
| 48 | } |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 49 | return index; |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 50 | } |
| 51 | |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 52 | static int find_with_slope(const SkUnichar base[], int count, SkUnichar value, double denom) { |
| 53 | SkASSERT(count >= kMinCountForSlope); |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 54 | |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 55 | int index; |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 56 | if (value <= base[1]) { |
| 57 | index = 1; |
| 58 | if (value < base[index]) { |
| 59 | index = ~index; |
| 60 | } |
| 61 | } else if (value >= base[count - 2]) { |
| 62 | index = count - 2; |
| 63 | if (value > base[index]) { |
| 64 | index = ~(index + 1); |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 65 | } |
| 66 | } else { |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 67 | // make our guess based on the "slope" of the current values |
| 68 | // index = 1 + (int64_t)(count - 2) * (value - base[1]) / (base[count - 2] - base[1]); |
| 69 | index = 1 + (int)(denom * (count - 2) * (value - base[1])); |
| 70 | SkASSERT(index >= 1 && index <= count - 2); |
| 71 | |
| 72 | if (value >= base[index]) { |
| 73 | for (;; ++index) { |
| 74 | if (value <= base[index]) { |
| 75 | if (value < base[index]) { |
| 76 | index = ~index; // not found |
| 77 | } |
| 78 | break; |
| 79 | } |
| 80 | } |
| 81 | } else { |
| 82 | for (--index;; --index) { |
| 83 | SkASSERT(index >= 0); |
| 84 | if (value >= base[index]) { |
| 85 | if (value > base[index]) { |
| 86 | index = ~(index + 1); |
| 87 | } |
| 88 | break; |
| 89 | } |
| 90 | } |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 91 | } |
| 92 | } |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 93 | return index; |
| 94 | } |
| 95 | |
| 96 | int SkCharToGlyphCache::findGlyphIndex(SkUnichar unichar) const { |
| 97 | const int count = fK32.count(); |
| 98 | int index; |
| 99 | if (count <= kSmallCountLimit) { |
| 100 | index = find_simple(fK32.begin(), count, unichar); |
| 101 | } else { |
| 102 | index = find_with_slope(fK32.begin(), count, unichar, fDenom); |
| 103 | } |
| 104 | if (index >= 0) { |
| 105 | return fV16[index]; |
| 106 | } |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 107 | return index; |
| 108 | } |
| 109 | |
| 110 | void SkCharToGlyphCache::insertCharAndGlyph(int index, SkUnichar unichar, SkGlyphID glyph) { |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 111 | SkASSERT(fK32.size() == fV16.size()); |
| 112 | SkASSERT((unsigned)index < fK32.size()); |
| 113 | SkASSERT(unichar < fK32[index]); |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 114 | |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 115 | *fK32.insert(index) = unichar; |
| 116 | *fV16.insert(index) = glyph; |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 117 | |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 118 | // if we've changed the first [1] or last [count-2] entry, recompute our slope |
| 119 | const int count = fK32.count(); |
| 120 | if (count >= kMinCountForSlope && (index == 1 || index == count - 2)) { |
| 121 | SkASSERT(index >= 1 && index <= count - 2); |
| 122 | fDenom = 1.0 / ((double)fK32[count - 2] - fK32[1]); |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 123 | } |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 124 | |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 125 | #ifdef SK_DEBUG |
Mike Reed | 194cab0 | 2019-04-15 12:07:19 -0400 | [diff] [blame] | 126 | for (int i = 1; i < fK32.count(); ++i) { |
| 127 | SkASSERT(fK32[i-1] < fK32[i]); |
Mike Reed | 0c60708 | 2019-04-11 17:10:17 -0400 | [diff] [blame] | 128 | } |
| 129 | #endif |
| 130 | } |