aboutsummaryrefslogtreecommitdiff
path: root/vt.c
diff options
context:
space:
mode:
authorDaniel Eklöf <daniel@ekloef.se>2022-06-13 11:11:56 +0000
committerDaniel Eklöf <daniel@ekloef.se>2022-06-15 17:25:00 +0000
commitfbcb30bf9870aa2b4d75376b3a02703576a715e4 (patch)
tree57f387a25e3b48ccc431b1aacdc38476c31ac74b /vt.c
parentvt: prevent potential endless loop when finding a slot for a composed character (diff)
vt: improve key calculation for compose sequences
* Don’t assume 32 bits when rotating the old key. Use the number of actual bits available, as determined by CELL_COMB_CHARS_{HI,LO} * Multiply with magic hash constant This greatly reduces the number of collisions seen. For example, the Emoji test file (from the Unicode specification), now has zero collisions.
Diffstat (limited to 'vt.c')
-rw-r--r--vt.c23
1 files changed, 19 insertions, 4 deletions
diff --git a/vt.c b/vt.c
index 9746364b..54fd643c 100644
--- a/vt.c
+++ b/vt.c
@@ -622,8 +622,21 @@ action_put(struct terminal *term, uint8_t c)
static inline uint32_t
chain_key(uint32_t old_key, uint32_t new_wc)
{
- /* Rotate left 8 bits, xor with new char */
- return ((old_key << 8) | (old_key >> (32 - 8))) ^ new_wc;
+ unsigned bits = 32 - __builtin_clz(CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO);
+
+ /* Rotate old key 8 bits */
+ uint32_t new_key = (old_key << 8) | (old_key >> (bits - 8));
+
+ /* xor with new char */
+ new_key ^= new_wc;
+
+ /* Multiply with magic hash constant */
+ new_key *= 2654435761;
+
+ /* And mask, to ensure the new value is within range */
+ new_key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO;
+
+ return new_key;
}
static void
@@ -668,8 +681,6 @@ action_utf8_print(struct terminal *term, char32_t wc)
} else
key = chain_key(base, wc);
- key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO;
-
#if defined(FOOT_GRAPHEME_CLUSTERING)
if (grapheme_clustering) {
/* Check if we're on a grapheme cluster break */
@@ -767,6 +778,10 @@ action_utf8_print(struct terminal *term, char32_t wc)
cc->count != wanted_count ||
cc->chars[wanted_count - 1] != wc)
{
+#if 0
+ LOG_WARN("COLLISION: base: %04x/%04x, count: %d/%zu, last: %04x/%04x",
+ cc->chars[0], base, cc->count, wanted_count, cc->chars[wanted_count - 1], wc);
+#endif
key++;
collision_count++;
continue;