submodule/skia/src/utils/SkCharToGlyphCache.cpp

   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
  10 SkCharToGlyphCache::SkCharToGlyphCache() {
  11     this->reset();
  12 }
  13
  14 SkCharToGlyphCache::~SkCharToGlyphCache() {}
  15
  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
  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
  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
  95 int SkCharToGlyphCache::findGlyphIndex(SkUnichar unichar) const {
  96     const int count = fK32.count();
  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
 109 void SkCharToGlyphCache::insertCharAndGlyph(int index, SkUnichar unichar, SkGlyphID glyph) {
 110     SkASSERT(fK32.size() == fV16.size());
 111     SkASSERT((unsigned)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.count();
 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.count(); ++i) {
 126         SkASSERT(fK32[i-1] < fK32[i]);
 127     }
 128 #endif
 129 }