SkCharToGlyphCache.cpp 3.7 KB

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