BLF: Perf: Add a kerning cache table for ascii chars.

This adds less than a megabyte of mem usage.
FT_Get_Kerning was the 2nd hotspot when profilling. This commit completly
remove this cost.

One concern though: I don't know if the kerning data is constant for every
sizes but it seems to be the case. I tested different fonts at different
dpi scalling and saw no differences.

5 files changed, 128 insertions, 7 deletions

diff --git a/source/blender/blenfont/intern/blf.c b/source/blender/blenfont/intern/blf.c
index 64a9f1739fd..df600feb1fe 100644
--- a/source/blender/blenfont/intern/blf.c
+++ b/source/blender/blenfont/intern/blf.c
@@ -144,8 +144,10 @@ void BLF_cache_clear(void)
 
 	for (i = 0; i < BLF_MAX_FONT; i++) {
 		font = global_font[i];
-		if (font)
+		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 2793689ff39..2c900e897ce 100644
--- a/source/blender/blenfont/intern/blf_font.c
+++ b/source/blender/blenfont/intern/blf_font.c
@@ -276,6 +276,20 @@ static void blf_font_ensure_ascii_table(FontBLF *font)
 	}
 }
 
+static void blf_font_ensure_ascii_kerning(FontBLF *font, const FT_UInt kern_mode)
+{
+	KerningCacheBLF *kc = font->kerning_cache;
+
+	font->kerning_mode = kern_mode;
+
+	if (!kc || kc->mode != kern_mode) {
+		font->kerning_cache = kc = blf_kerning_cache_find(font);
+		if (!kc) {
+			font->kerning_cache = kc = blf_kerning_cache_new(font);
+		}
+	}
+}
+
 /* Fast path for runs of ASCII characters. Given that common UTF-8
  * input will consist of an overwhelming majority of ASCII
  * characters.
@@ -303,6 +317,26 @@ static void blf_font_ensure_ascii_table(FontBLF *font)
 	                         (((_font)->flags & BLF_KERNING_DEFAULT) ?           \
 	                          ft_kerning_default : (FT_UInt)FT_KERNING_UNFITTED) \
 
+/* Note,
+ * blf_font_ensure_ascii_kerning(font, kern_mode); must be called before this macro */
+
+#define BLF_KERNING_STEP_FAST(_font, _kern_mode, _g_prev, _g, _c_prev, _c, _pen_x) \
+{                                                                                \
+	if (_g_prev) {                                                               \
+		FT_Vector _delta;                                                        \
+		if (_c_prev < 0x80 && _c < 0x80) {                                       \
+			_pen_x += (_font)->kerning_cache->table[_c][_c_prev];                 \
+		}                                                                        \
+		else if (FT_Get_Kerning((_font)->face,                                   \
+		                        (_g_prev)->idx,                                  \
+		                        (_g)->idx,                                       \
+		                        _kern_mode,                                      \
+		                        &(_delta)) == 0)                                 \
+		{                                                                        \
+			_pen_x += (int)_delta.x >> 6;                                        \
+		}                                                                        \
+	}                                                                            \
+} (void)0
 
 #define BLF_KERNING_STEP(_font, _kern_mode, _g_prev, _g, _delta, _pen_x)         \
 {                                                                                \
@@ -323,9 +357,8 @@ static void blf_font_draw_ex(
         FontBLF *font, const char *str, size_t len, struct ResultBLF *r_info,
         int pen_y)
 {
-	unsigned int c;
+	unsigned int c, c_prev = BLI_UTF8_ERR;
 	GlyphBLF *g, *g_prev = NULL;
-	FT_Vector delta;
 	int pen_x = 0;
 	size_t i = 0;
 	GlyphBLF **glyph_ascii_table = font->glyph_cache->glyph_ascii_table;
@@ -338,6 +371,7 @@ static void blf_font_draw_ex(
 	BLF_KERNING_VARS(font, has_kerning, kern_mode);
 
 	blf_font_ensure_ascii_table(font);
+	blf_font_ensure_ascii_kerning(font, kern_mode);
 
 	blf_batch_draw_begin(font);
 
@@ -349,13 +383,14 @@ static void blf_font_draw_ex(
 		if (UNLIKELY(g == NULL))
 			continue;
 		if (has_kerning)
-			BLF_KERNING_STEP(font, kern_mode, g_prev, g, delta, pen_x);
+			BLF_KERNING_STEP_FAST(font, kern_mode, g_prev, g, c_prev, c, pen_x);
 
 		/* do not return this loop if clipped, we want every character tested */
 		blf_glyph_render(font, g, (float)pen_x, (float)pen_y);
 
 		pen_x += g->advance_i;
 		g_prev = g;
+		c_prev = c;
 	}
 
 	blf_batch_draw_end();
@@ -734,9 +769,8 @@ static void blf_font_boundbox_ex(
         FontBLF *font, const char *str, size_t len, rctf *box, struct ResultBLF *r_info,
         int pen_y)
 {
-	unsigned int c;
+	unsigned int c, c_prev = BLI_UTF8_ERR;
 	GlyphBLF *g, *g_prev = NULL;
-	FT_Vector delta;
 	int pen_x = 0;
 	size_t i = 0;
 	GlyphBLF **glyph_ascii_table = font->glyph_cache->glyph_ascii_table;
@@ -751,6 +785,7 @@ static void blf_font_boundbox_ex(
 	box->ymax = -32000.0f;
 
 	blf_font_ensure_ascii_table(font);
+	blf_font_ensure_ascii_kerning(font, kern_mode);
 
 	while ((i < len) && str[i]) {
 		BLF_UTF8_NEXT_FAST(font, g, str, i, c, glyph_ascii_table);
@@ -760,7 +795,7 @@ static void blf_font_boundbox_ex(
 		if (UNLIKELY(g == NULL))
 			continue;
 		if (has_kerning)
-			BLF_KERNING_STEP(font, kern_mode, g_prev, g, delta, pen_x);
+			BLF_KERNING_STEP_FAST(font, kern_mode, g_prev, g, c_prev, c, pen_x);
 
 		gbox.xmin = (float)pen_x;
 		gbox.xmax = (float)pen_x + g->advance;
@@ -775,6 +810,7 @@ static void blf_font_boundbox_ex(
 
 		pen_x += g->advance_i;
 		g_prev = g;
+		c_prev = c;
 	}
 
 	if (box->xmin > box->xmax) {
@@ -1055,6 +1091,8 @@ void blf_font_free(FontBLF *font)
 		blf_glyph_cache_free(gc);
 	}
 
+	blf_kerning_cache_clear(font);
+
 	FT_Done_Face(font->face);
 	if (font->filename)
 		MEM_freeN(font->filename);
@@ -1089,7 +1127,9 @@ 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->glyph_cache = NULL;
+	font->kerning_cache = NULL;
 #if BLF_BLUR_ENABLE
 	font->blur = 0;
 #endif
diff --git a/source/blender/blenfont/intern/blf_glyph.c b/source/blender/blenfont/intern/blf_glyph.c
index d472825e940..f5a645af5e0 100644
--- a/source/blender/blenfont/intern/blf_glyph.c
+++ b/source/blender/blenfont/intern/blf_glyph.c
@@ -65,6 +65,61 @@
 #include "BLI_strict_flags.h"
 #include "BLI_math_vector.h"
 
+KerningCacheBLF *blf_kerning_cache_find(FontBLF *font)
+{
+	KerningCacheBLF *p;
+
+	p = (KerningCacheBLF *)font->kerning_caches.first;
+	while (p) {
+		if (p->mode == font->kerning_mode)
+			return p;
+		p = p->next;
+	}
+	return NULL;
+}
+
+/* Create a new glyph cache for the current kerning mode. */
+KerningCacheBLF *blf_kerning_cache_new(FontBLF *font)
+{
+	KerningCacheBLF *kc;
+
+	kc = (KerningCacheBLF *)MEM_callocN(sizeof(KerningCacheBLF), "blf_kerning_cache_new");
+	kc->next = NULL;
+	kc->prev = NULL;
+	kc->mode = font->kerning_mode;
+
+	unsigned int i, j;
+	for (i = 0; i < 0x80; i++) {
+		for (j = 0; j < 0x80; j++) {
+			GlyphBLF *g = blf_glyph_search(font->glyph_cache, i);
+			if (!g) {
+				FT_UInt glyph_index = FT_Get_Char_Index(font->face, i);
+				g = blf_glyph_add(font, glyph_index, i);
+			}
+			/* Cannot fail since it has been added just before. */
+			GlyphBLF *g_prev = blf_glyph_search(font->glyph_cache, j);
+
+			FT_Vector delta = {.x = 0, .y = 0};
+			if (FT_Get_Kerning(font->face, g_prev->idx, g->idx, kc->mode,
+			                   &delta) == 0) {
+				kc->table[i][j] = (int)delta.x >> 6;
+			}
+			else {
+				kc->table[i][j] = 0;
+			}
+		}
+	}
+
+	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 aa2b667d97f..b48bd2fbae7 100644
--- a/source/blender/blenfont/intern/blf_internal.h
+++ b/source/blender/blenfont/intern/blf_internal.h
@@ -78,6 +78,10 @@ int blf_font_count_missing_chars(struct FontBLF *font, const char *str, const si
 
 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);
+void blf_kerning_cache_clear(struct FontBLF *font);
+
 struct GlyphCacheBLF *blf_glyph_cache_find(struct FontBLF *font, unsigned int size, unsigned int dpi);
 struct GlyphCacheBLF *blf_glyph_cache_new(struct FontBLF *font);
 void blf_glyph_cache_clear(struct FontBLF *font);
diff --git a/source/blender/blenfont/intern/blf_internal_types.h b/source/blender/blenfont/intern/blf_internal_types.h
index a954cf22370..a34541f62bf 100644
--- a/source/blender/blenfont/intern/blf_internal_types.h
+++ b/source/blender/blenfont/intern/blf_internal_types.h
@@ -49,6 +49,17 @@ typedef struct BatchBLF{
 
 extern BatchBLF g_batch;
 
+typedef struct KerningCacheBLF {
+	struct KerningCacheBLF *next, *prev;
+
+	/* kerning mode. */
+	FT_UInt mode;
+
+	/* only cache a ascii glyph pairs. Only store the x
+	 * offset we are interested in, instead of the full FT_Vector. */
+	int table[0x80][0x80];
+} KerningCacheBLF;
+
 typedef struct GlyphCacheBLF {
 	struct GlyphCacheBLF *next;
 	struct GlyphCacheBLF *prev;
@@ -243,6 +254,12 @@ typedef struct FontBLF {
 	/* current glyph cache, size and dpi. */
 	GlyphCacheBLF *glyph_cache;
 
+	/* list of kerning cache for this font. */
+	ListBase kerning_caches;
+
+	/* current kerning cache for this font and kerning mode. */
+	KerningCacheBLF *kerning_cache;
+
 	/* freetype2 lib handle. */
 	FT_Library ft_lib;
 
@@ -252,6 +269,9 @@ typedef struct FontBLF {
 	/* freetype2 face. */
 	FT_Face face;
 
+	/* freetype kerning */
+	FT_UInt kerning_mode;
+
 	/* data for buffer usage (drawing into a texture buffer) */
 	FontBufInfoBLF buf_info;
 } FontBLF;