Refactor: BLF Kerning Cache After Use

Optimization of font kerning by only caching kerning values after a
pair is encountered. Also saves unscaled values so they don't have to
be rebuilt between font size changes.

See D12274 for more details and speed comparison.

Differential Revision: https://developer.blender.org/D12274

Reviewed by Campbell Barton

5 files changed, 62 insertions, 98 deletions

diff --git a/source/blender/blenfont/intern/blf.c b/source/blender/blenfont/intern/blf.c
index 9168e7aa19c..2f9eb0753ac 100644
--- a/source/blender/blenfont/intern/blf.c
+++ b/source/blender/blenfont/intern/blf.c
@@ -108,7 +108,6 @@ void BLF_cache_clear(void)
     FontBLF *font = global_font[i];
     if (font) {
       blf_glyph_cache_clear(font);
-      blf_kerning_cache_clear(font);
     }
   }
 }
diff --git a/source/blender/blenfont/intern/blf_font.c b/source/blender/blenfont/intern/blf_font.c
index 00d3cfb09eb..02847b74df1 100644
--- a/source/blender/blenfont/intern/blf_font.c
+++ b/source/blender/blenfont/intern/blf_font.c
@@ -308,17 +308,6 @@ void blf_font_size(FontBLF *font, unsigned int size, unsigned int dpi)
   blf_glyph_cache_release(font);
 }
 
-static void blf_font_ensure_ascii_kerning(FontBLF *font, GlyphCacheBLF *gc)
-{
-  if (font->kerning_cache || !FT_HAS_KERNING(font->face)) {
-    return;
-  }
-  font->kerning_cache = blf_kerning_cache_find(font);
-  if (!font->kerning_cache) {
-    font->kerning_cache = blf_kerning_cache_new(font, gc);
-  }
-}
-
 /* Fast path for runs of ASCII characters. Given that common UTF-8
  * input will consist of an overwhelming majority of ASCII
  * characters.
@@ -348,6 +337,31 @@ BLI_INLINE GlyphBLF *blf_utf8_next_fast(
   return g;
 }
 
+/* Convert a FreeType 26.6 value representing an unscaled design size to pixels.
+ * This is an exact copy of the scaling done inside FT_Get_Kerning when called
+ * with FT_KERNING_DEFAULT, including arbitrary resizing for small fonts.
+ */
+static int blf_unscaled_F26Dot6_to_pixels(FontBLF *font, FT_Pos value)
+{
+  /* Scale value by font size using integer-optimized multiplication. */
+  FT_Long scaled = FT_MulFix(value, font->face->size->metrics.x_scale);
+
+  /* FreeType states that this '25' has been determined heuristically. */
+  if (font->face->size->metrics.x_ppem < 25) {
+    scaled = FT_MulDiv(scaled, font->face->size->metrics.x_ppem, 25);
+  }
+
+  /* Copies of internal FreeType macros needed here. */
+#define FT_PIX_FLOOR(x) ((x) & ~FT_TYPEOF(x) 63)
+#define FT_PIX_ROUND(x) FT_PIX_FLOOR((x) + 32)
+
+  /* Round to even 64ths, then divide by 64. */
+  return FT_PIX_ROUND(scaled) >> 6;
+
+#undef FT_PIX_FLOOR
+#undef FT_PIX_ROUND
+}
+
 BLI_INLINE void blf_kerning_step_fast(FontBLF *font,
                                       const GlyphBLF *g_prev,
                                       const GlyphBLF *g,
@@ -355,18 +369,28 @@ BLI_INLINE void blf_kerning_step_fast(FontBLF *font,
                                       const uint c,
                                       int *pen_x_p)
 {
-  /* `blf_font_ensure_ascii_kerning(font, gc);` must be called before this function. */
-  BLI_assert(font->kerning_cache != NULL || !FT_HAS_KERNING(font->face));
+  if (FT_HAS_KERNING(font->face) && g_prev != NULL) {
+    FT_Vector delta = {KERNING_ENTRY_UNSET};
 
-  if (g_prev != NULL && FT_HAS_KERNING(font->face)) {
+    /* Get unscaled kerning value from our cache if ASCII. */
     if ((c_prev < KERNING_CACHE_TABLE_SIZE) && (c < GLYPH_ASCII_TABLE_SIZE)) {
-      *pen_x_p += font->kerning_cache->ascii_table[c][c_prev];
+      delta.x = font->kerning_cache->ascii_table[c][c_prev];
     }
-    else {
-      FT_Vector delta;
-      if (FT_Get_Kerning(font->face, g_prev->idx, g->idx, FT_KERNING_DEFAULT, &delta) == 0) {
-        *pen_x_p += (int)delta.x >> 6;
-      }
+
+    /* If not ASCII or not found in cache, ask FreeType for kerning. */
+    if (UNLIKELY(delta.x == KERNING_ENTRY_UNSET)) {
+      /* Note that this function sets delta values to zero on any error. */
+      FT_Get_Kerning(font->face, g_prev->idx, g->idx, FT_KERNING_UNSCALED, &delta);
+    }
+
+    /* If ASCII we save this value to our cache for quicker access next time. */
+    if ((c_prev < KERNING_CACHE_TABLE_SIZE) && (c < GLYPH_ASCII_TABLE_SIZE)) {
+      font->kerning_cache->ascii_table[c][c_prev] = delta.x;
+    }
+
+    if (delta.x != 0) {
+      /* Convert unscaled design units to pixels and move pen. */
+      *pen_x_p += blf_unscaled_F26Dot6_to_pixels(font, delta.x);
     }
   }
 }
@@ -388,8 +412,6 @@ static void blf_font_draw_ex(FontBLF *font,
     return;
   }
 
-  blf_font_ensure_ascii_kerning(font, gc);
-
   blf_batch_draw_begin(font);
 
   while ((i < len) && str[i]) {
@@ -435,8 +457,6 @@ static void blf_font_draw_ascii_ex(
 
   GlyphCacheBLF *gc = blf_glyph_cache_acquire(font);
 
-  blf_font_ensure_ascii_kerning(font, gc);
-
   blf_batch_draw_begin(font);
 
   while ((c = *(str++)) && len--) {
@@ -536,8 +556,6 @@ static void blf_font_draw_buffer_ex(FontBLF *font,
   int chx, chy;
   int y, x;
 
-  blf_font_ensure_ascii_kerning(font, gc);
-
   /* another buffer specific call for color conversion */
 
   while ((i < len) && str[i]) {
@@ -694,8 +712,6 @@ size_t blf_font_width_to_strlen(
   GlyphCacheBLF *gc = blf_glyph_cache_acquire(font);
   const int width_i = (int)width;
 
-  blf_font_ensure_ascii_kerning(font, gc);
-
   for (i_prev = i = 0, width_new = pen_x = 0, g_prev = NULL, c_prev = 0; (i < len) && str[i];
        i_prev = i, width_new = pen_x, c_prev = c, g_prev = g) {
     g = blf_utf8_next_fast(font, gc, str, &i, &c);
@@ -725,8 +741,6 @@ size_t blf_font_width_to_rstrlen(
   GlyphCacheBLF *gc = blf_glyph_cache_acquire(font);
   const int width_i = (int)width;
 
-  blf_font_ensure_ascii_kerning(font, gc);
-
   i = BLI_strnlen(str, len);
   s = BLI_str_find_prev_char_utf8(str, &str[i]);
   i = (size_t)((s != NULL) ? s - str : 0);
@@ -778,8 +792,6 @@ static void blf_font_boundbox_ex(FontBLF *font,
   box->ymin = 32000.0f;
   box->ymax = -32000.0f;
 
-  blf_font_ensure_ascii_kerning(font, gc);
-
   while ((i < len) && str[i]) {
     g = blf_utf8_next_fast(font, gc, str, &i, &c);
 
@@ -869,8 +881,6 @@ static void blf_font_wrap_apply(FontBLF *font,
 
   GlyphCacheBLF *gc = blf_glyph_cache_acquire(font);
 
-  blf_font_ensure_ascii_kerning(font, gc);
-
   struct WordWrapVars {
     int wrap_width;
     size_t start, last[2];
@@ -1123,8 +1133,6 @@ static void blf_font_boundbox_foreach_glyph_ex(FontBLF *font,
     return;
   }
 
-  blf_font_ensure_ascii_kerning(font, gc);
-
   while ((i < len) && str[i]) {
     i_curr = i;
     g = blf_utf8_next_fast(font, gc, str, &i, &c);
@@ -1205,7 +1213,9 @@ void blf_font_free(FontBLF *font)
     blf_glyph_cache_free(gc);
   }
 
-  blf_kerning_cache_clear(font);
+  if (font->kerning_cache) {
+    MEM_freeN(font->kerning_cache);
+  }
 
   FT_Done_Face(font->face);
   if (font->filename) {
@@ -1246,7 +1256,6 @@ static void blf_font_fill(FontBLF *font)
   font->dpi = 0;
   font->size = 0;
   BLI_listbase_clear(&font->cache);
-  BLI_listbase_clear(&font->kerning_caches);
   font->kerning_cache = NULL;
 #if BLF_BLUR_ENABLE
   font->blur = 0;
@@ -1307,6 +1316,17 @@ FontBLF *blf_font_new(const char *name, const char *filename)
   font->name = BLI_strdup(name);
   font->filename = BLI_strdup(filename);
   blf_font_fill(font);
+
+  if (FT_HAS_KERNING(font->face)) {
+    /* Create kerning cache table and fill with value indicating "unset". */
+    font->kerning_cache = MEM_mallocN(sizeof(KerningCacheBLF), __func__);
+    for (uint i = 0; i < KERNING_CACHE_TABLE_SIZE; i++) {
+      for (uint j = 0; j < KERNING_CACHE_TABLE_SIZE; j++) {
+        font->kerning_cache->ascii_table[i][j] = KERNING_ENTRY_UNSET;
+      }
+    }
+  }
+
   return font;
 }
 
diff --git a/source/blender/blenfont/intern/blf_glyph.c b/source/blender/blenfont/intern/blf_glyph.c
index 5fb69251466..6cdf5fc5996 100644
--- a/source/blender/blenfont/intern/blf_glyph.c
+++ b/source/blender/blenfont/intern/blf_glyph.c
@@ -55,56 +55,6 @@
 #include "BLI_math_vector.h"
 #include "BLI_strict_flags.h"
 
-KerningCacheBLF *blf_kerning_cache_find(FontBLF *font)
-{
-  return (KerningCacheBLF *)font->kerning_caches.first;
-}
-
-/* Create a new glyph cache for the current kerning mode. */
-KerningCacheBLF *blf_kerning_cache_new(FontBLF *font, GlyphCacheBLF *gc)
-{
-  KerningCacheBLF *kc = MEM_mallocN(sizeof(KerningCacheBLF), __func__);
-  kc->next = NULL;
-  kc->prev = NULL;
-
-  GlyphBLF *g_table[KERNING_CACHE_TABLE_SIZE];
-  for (uint i = 0; i < KERNING_CACHE_TABLE_SIZE; i++) {
-    GlyphBLF *g = blf_glyph_search(gc, i);
-    if (UNLIKELY(g == NULL)) {
-      FT_UInt glyph_index = FT_Get_Char_Index(font->face, i);
-      g = blf_glyph_add(font, gc, glyph_index, i);
-    }
-    g_table[i] = g;
-  }
-
-  memset(kc->ascii_table, 0, sizeof(kc->ascii_table));
-  for (uint i = 0; i < KERNING_CACHE_TABLE_SIZE; i++) {
-    GlyphBLF *g = g_table[i];
-    if (g == NULL) {
-      continue;
-    }
-    for (uint j = 0; j < KERNING_CACHE_TABLE_SIZE; j++) {
-      GlyphBLF *g_prev = g_table[j];
-      if (g_prev == NULL) {
-        continue;
-      }
-      FT_Vector delta;
-      if (FT_Get_Kerning(font->face, g_prev->idx, g->idx, FT_KERNING_DEFAULT, &delta) == 0) {
-        kc->ascii_table[i][j] = (int)delta.x >> 6;
-      }
-    }
-  }
-
-  BLI_addhead(&font->kerning_caches, kc);
-  return kc;
-}
-
-void blf_kerning_cache_clear(FontBLF *font)
-{
-  font->kerning_cache = NULL;
-  BLI_freelistN(&font->kerning_caches);
-}
-
 GlyphCacheBLF *blf_glyph_cache_find(FontBLF *font, unsigned int size, unsigned int dpi)
 {
   GlyphCacheBLF *p;
diff --git a/source/blender/blenfont/intern/blf_internal.h b/source/blender/blenfont/intern/blf_internal.h
index 35a6d019eac..ab2a26b1e06 100644
--- a/source/blender/blenfont/intern/blf_internal.h
+++ b/source/blender/blenfont/intern/blf_internal.h
@@ -121,10 +121,6 @@ int blf_font_count_missing_chars(struct FontBLF *font,
 
 void blf_font_free(struct FontBLF *font);
 
-struct KerningCacheBLF *blf_kerning_cache_find(struct FontBLF *font);
-struct KerningCacheBLF *blf_kerning_cache_new(struct FontBLF *font, struct GlyphCacheBLF *gc);
-void blf_kerning_cache_clear(struct FontBLF *font);
-
 struct GlyphCacheBLF *blf_glyph_cache_find(struct FontBLF *font,
                                            unsigned int size,
                                            unsigned int dpi);
diff --git a/source/blender/blenfont/intern/blf_internal_types.h b/source/blender/blenfont/intern/blf_internal_types.h
index caa10b2b125..38d7d7b6e21 100644
--- a/source/blender/blenfont/intern/blf_internal_types.h
+++ b/source/blender/blenfont/intern/blf_internal_types.h
@@ -34,6 +34,9 @@
 /* Number of characters in KerningCacheBLF.table. */
 #define KERNING_CACHE_TABLE_SIZE 128
 
+/* A value in the kerning cache that indicates it is not yet set. */
+#define KERNING_ENTRY_UNSET INT_MAX
+
 typedef struct BatchBLF {
   struct FontBLF *font; /* can only batch glyph from the same font */
   struct GPUBatch *batch;
@@ -50,7 +53,6 @@ typedef struct BatchBLF {
 extern BatchBLF g_batch;
 
 typedef struct KerningCacheBLF {
-  struct KerningCacheBLF *next, *prev;
   /**
    * Cache a ascii glyph pairs. Only store the x offset we are interested in,
    * instead of the full #FT_Vector since it's not used for drawing at the moment.
@@ -223,10 +225,7 @@ typedef struct FontBLF {
    */
   ListBase cache;
 
-  /* list of kerning cache for this font. */
-  ListBase kerning_caches;
-
-  /* current kerning cache for this font and kerning mode. */
+  /* Cache of unscaled kerning values. Will be NULL if font does not have kerning. */
   KerningCacheBLF *kerning_cache;
 
   /* freetype2 lib handle. */