From 1181f74d19f6f9e881b539ed9fdb8cc17d03f7bf Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Fri, 24 Jan 2025 09:52:57 +0100 Subject: composed: re-factor: break out key calculation from vt.c --- composed.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) (limited to 'composed.c') diff --git a/composed.c b/composed.c index 442325ea..7a36275e 100644 --- a/composed.c +++ b/composed.c @@ -4,6 +4,52 @@ #include #include "debug.h" +#include "terminal.h" + +uint32_t +composed_key_from_chars(const uint32_t chars[], size_t count) +{ + if (count == 0) + return 0; + + uint32_t key = chars[0]; + for (size_t i = 1; i < count; i++) + key = composed_key_from_key(key, chars[i]); + + return key; +} + +uint32_t +composed_key_from_key(uint32_t prev_key, uint32_t next_char) +{ + unsigned bits = 32 - __builtin_clz(CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO); + + /* Rotate old key 8 bits */ + uint32_t new_key = (prev_key << 8) | (prev_key >> (bits - 8)); + + /* xor with new char */ + new_key ^= next_char; + + /* Multiply with magic hash constant */ + new_key *= 2654435761ul; + + /* And mask, to ensure the new value is within range */ + new_key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO; + return new_key; +} + +UNITTEST +{ + const char32_t chars[] = U"abcdef"; + + uint32_t k1 = composed_key_from_key(chars[0], chars[1]); + uint32_t k2 = composed_key_from_chars(chars, 2); + xassert(k1 == k2); + + uint32_t k3 = composed_key_from_key(k2, chars[2]); + uint32_t k4 = composed_key_from_chars(chars, 3); + xassert(k3 == k4); +} struct composed * composed_lookup(struct composed *root, uint32_t key) -- cgit v1.3 From e248e73753d61bfd24f1af8e824231434db63c53 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Fri, 24 Jan 2025 14:15:01 +0100 Subject: composed: refactor: break out lookup with collision detection --- composed.c | 37 ++++++++++++++++++++++++++++++++++- composed.h | 6 +++++- vt.c | 66 +++++++++++++------------------------------------------------- 3 files changed, 55 insertions(+), 54 deletions(-) (limited to 'composed.c') diff --git a/composed.c b/composed.c index 7a36275e..2d9ed47d 100644 --- a/composed.c +++ b/composed.c @@ -51,7 +51,7 @@ UNITTEST xassert(k3 == k4); } -struct composed * +const struct composed * composed_lookup(struct composed *root, uint32_t key) { struct composed *node = root; @@ -66,6 +66,41 @@ composed_lookup(struct composed *root, uint32_t key) return NULL; } +const struct composed * +composed_lookup_without_collision(struct composed *root, uint32_t *key, + const char32_t *prefix_text, size_t prefix_len, + char32_t wc, int forced_width) +{ + while (true) { + const struct composed *cc = composed_lookup(root, *key); + if (cc == NULL) + return NULL; + + bool match = cc->count == prefix_len + 1 && + cc->forced_width == forced_width && + cc->chars[prefix_len] == wc; + + if (match) { + for (size_t i = 0; i < prefix_len; i++) { + if (cc->chars[i] != prefix_text[i]) { + match = false; + break; + } + } + } + + if (match) + return cc; + + (*key)++; + *key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO; + + /* TODO: this will loop infinitly if the composed table is full */ + } + + return NULL; +} + void composed_insert(struct composed **root, struct composed *node) { diff --git a/composed.h b/composed.h index fcaf87d4..18afb146 100644 --- a/composed.h +++ b/composed.h @@ -10,12 +10,16 @@ struct composed { uint32_t key; uint8_t count; uint8_t width; + uint8_t forced_width; }; uint32_t composed_key_from_chars(const uint32_t chars[], size_t count); uint32_t composed_key_from_key(uint32_t prev_key, uint32_t next_char); -struct composed *composed_lookup(struct composed *root, uint32_t key); +const struct composed *composed_lookup(struct composed *root, uint32_t key); +const struct composed *composed_lookup_without_collision( + struct composed *root, uint32_t *key, + const char32_t *prefix, size_t prefix_len, char32_t wc, int forced_width); void composed_insert(struct composed **root, struct composed *node); void composed_free(struct composed *root); diff --git a/vt.c b/vt.c index 8f5d27d9..5447493a 100644 --- a/vt.c +++ b/vt.c @@ -793,60 +793,21 @@ action_utf8_print(struct terminal *term, char32_t wc) xassert(wanted_count <= 255); - size_t collision_count = 0; - - /* Look for existing combining chain */ - while (true) { - if (unlikely(collision_count > 128)) { - static bool have_warned = false; - if (!have_warned) { - have_warned = true; - LOG_WARN("ignoring composed character: " - "too many collisions in hash table"); - } - return; - } - - const struct composed *cc = composed_lookup(term->composed, key); - if (cc == NULL) - break; - - /* - * We may have a key collisison, so need to check that - * it's a true match. If not, bump the key and try - * again. - */ - - xassert(key == cc->key); - if (cc->chars[0] != base || - 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++; - key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO; - collision_count++; - continue; - } - - bool match = composed != NULL - ? memcmp(&cc->chars[1], &composed->chars[1], - (wanted_count - 2) * sizeof(cc->chars[0])) == 0 - : true; - - if (!match) { - key++; - key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO; - collision_count++; - continue; - } - + /* Check if we already have a match for the entire compose chain */ + const struct composed *cc = + composed_lookup_without_collision( + term->composed, &key, + composed != NULL ? composed->chars : &(char32_t){base}, + composed != NULL ? composed->count : 1, + wc, 0); + + if (cc != NULL) { + /* We *do* have a match! */ wc = CELL_COMB_CHARS_LO + cc->key; width = cc->width; goto out; + } else { + /* No match - allocate a new chain below */ } if (unlikely(term->composed_count >= @@ -867,6 +828,7 @@ action_utf8_print(struct terminal *term, char32_t wc) new_cc->count = wanted_count; new_cc->chars[0] = base; new_cc->chars[wanted_count - 1] = wc; + new_cc->forced_width = 0; if (composed != NULL) { memcpy(&new_cc->chars[1], &composed->chars[1], @@ -923,7 +885,7 @@ action_utf8_print(struct terminal *term, char32_t wc) term->composed_count++; composed_insert(&term->composed, new_cc); - wc = CELL_COMB_CHARS_LO + key; + wc = CELL_COMB_CHARS_LO + new_cc->key; width = new_cc->width; xassert(wc >= CELL_COMB_CHARS_LO); -- cgit v1.3 From 3998f8570caaf7d92cecc3b29b76c3351087930b Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Mon, 27 Jan 2025 07:35:10 +0100 Subject: composed: codespell: infinitely --- composed.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'composed.c') diff --git a/composed.c b/composed.c index 2d9ed47d..fc7dfa00 100644 --- a/composed.c +++ b/composed.c @@ -95,7 +95,7 @@ composed_lookup_without_collision(struct composed *root, uint32_t *key, (*key)++; *key &= CELL_COMB_CHARS_HI - CELL_COMB_CHARS_LO; - /* TODO: this will loop infinitly if the composed table is full */ + /* TODO: this will loop infinitely if the composed table is full */ } return NULL; -- cgit v1.3