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