blob: 6d6ecc1376e718dd0b68917057bb104ae41b69fe [file] [log] [blame]
/*
* 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 "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.size();
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(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.size();
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.size(); ++i) {
SkASSERT(fK32[i-1] < fK32[i]);
}
#endif
}