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 "include/private/SkTFitsIn.h"
9#include "src/utils/SkCharToGlyphCache.h"
10
11SkCharToGlyphCache::SkCharToGlyphCache() {
12 this->reset();
13}
14
15SkCharToGlyphCache::~SkCharToGlyphCache() {}
16
17void SkCharToGlyphCache::reset() {
18 fK32.reset();
19 fV16.reset();
20
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
30// Determined experimentally. For N much larger, the slope technique is faster.
31// For N much smaller, a simple search is faster.
32//
33constexpr int kSmallCountLimit = 16;
34
35// To use slope technique we need at least 2 real entries (+2 sentinels) hence the min of 4
36//
37constexpr int kMinCountForSlope = 4;
38
39static int find_simple(const SkUnichar base[], int count, SkUnichar value) {
40 int index;
41 for (index = 0;; ++index) {
42 if (value <= base[index]) {
43 if (value < base[index]) {
44 index = ~index; // not found
45 }
46 break;
47 }
48 }
49 return index;
50}
51
52static int find_with_slope(const SkUnichar base[], int count, SkUnichar value, double denom) {
53 SkASSERT(count >= kMinCountForSlope);
54
55 int index;
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);
65 }
66 } else {
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 }
91 }
92 }
93 return index;
94}
95
96int 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 }
107 return index;
108}
109
110void SkCharToGlyphCache::insertCharAndGlyph(int index, SkUnichar unichar, SkGlyphID glyph) {
111 SkASSERT(fK32.size() == fV16.size());
112 SkASSERT((unsigned)index < fK32.size());
113 SkASSERT(unichar < fK32[index]);
114
115 *fK32.insert(index) = unichar;
116 *fV16.insert(index) = glyph;
117
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]);
123 }
124
125#ifdef SK_DEBUG
126 for (int i = 1; i < fK32.count(); ++i) {
127 SkASSERT(fK32[i-1] < fK32[i]);
128 }
129#endif
130}
131