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