From 4741f7a6dfa144ce65cf3bbdd4a1bc6bee6df2e5 Mon Sep 17 00:00:00 2001 From: Berke Güzel Date: Tue, 13 Oct 2026 13:36:27 +0300 Subject: Optimize and simplify loops, table lookups, and branchless parsers - Replace sequential colon-counting loop with branchless CTZ bitmask in src/pen.h - Replace linear strchr with 256-bit ASCII punctuation bitmask in src/selection.c - Flatten 3D color cube loop and precompute constants in src/palette.c - Use static 256-byte LUT for hex decoding and bsearch for termcap in src/escape.c - Replace capacity doubling while loops with branchless CLZ pow2 helpers across core - Use direct memset/memcpy in src/snapshot.c - Optimize input digit/byte formatting, alt-prefix path, and make keyboard state optional in src/input.c --- src/compat.h | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 76 insertions(+), 1 deletion(-) (limited to 'src/compat.h') diff --git a/src/compat.h b/src/compat.h index d1264fe..a972a0f 100644 --- a/src/compat.h +++ b/src/compat.h @@ -50,12 +50,15 @@ #define TERM_EXPECT(x, v) (x) #endif -/* term_ctz32(0) is 32 and term_ctz64(0) is 64 on every path. */ +/* term_ctz32(0) is 32, term_clz32(0) is 32, term_ctz64(0) is 64, and + * term_clz64(0) is 64 on every path. */ #if defined(TERM_HAVE_BUILTINS) static inline int term_ctz32(uint32_t x) { return x ? __builtin_ctz(x) : 32; } +static inline int term_clz32(uint32_t x) { return x ? __builtin_clz(x) : 32; } static inline int term_popcount32(uint32_t x) { return __builtin_popcount(x); } static inline int term_ctz64(uint64_t x) { return x ? __builtin_ctzll(x) : 64; } +static inline int term_clz64(uint64_t x) { return x ? __builtin_clzll(x) : 64; } static inline int term_popcount64(uint64_t x) { return __builtin_popcountll(x); } #else @@ -66,6 +69,11 @@ static inline int term_ctz32(uint32_t x) unsigned long i; return _BitScanForward(&i, x) ? (int)i : 32; } +static inline int term_clz32(uint32_t x) +{ + unsigned long i; + return _BitScanReverse(&i, x) ? 31 - (int)i : 32; +} static inline int term_popcount32(uint32_t x) { return (int)__popcnt(x); } #else static inline int term_ctz32(uint32_t x) @@ -79,6 +87,18 @@ static inline int term_ctz32(uint32_t x) } return n; } +static inline int term_clz32(uint32_t x) +{ + if (!x) + return 32; + int n = 0; + if (!(x & 0xffff0000u)) { n += 16; x <<= 16; } + if (!(x & 0xff000000u)) { n += 8; x <<= 8; } + if (!(x & 0xf0000000u)) { n += 4; x <<= 4; } + if (!(x & 0xc0000000u)) { n += 2; x <<= 2; } + if (!(x & 0x80000000u)) { n += 1; } + return n; +} static inline int term_popcount32(uint32_t x) { int n = 0; @@ -95,6 +115,12 @@ static inline int term_ctz64(uint64_t x) return lo ? term_ctz32(lo) : 32 + term_ctz32((uint32_t)(x >> 32)); } +static inline int term_clz64(uint64_t x) +{ + uint32_t hi = (uint32_t)(x >> 32); + return hi ? term_clz32(hi) : 32 + term_clz32((uint32_t)x); +} + static inline int term_popcount64(uint64_t x) { return term_popcount32((uint32_t)x) + term_popcount32((uint32_t)(x >> 32)); @@ -102,6 +128,55 @@ static inline int term_popcount64(uint64_t x) #endif +/* Smallest power of two >= x, branchlessly via CLZ. Returns UINT32_MAX on overflow. */ +static inline uint32_t term_next_pow2_32(uint32_t x) +{ + uint32_t v = x <= 1 ? 1 : x - 1; + int lz = term_clz32(v); + uint32_t res = UINT32_C(1) << ((32 - lz) & 31); + return (x <= 1) ? 1 : (lz == 0 ? UINT32_MAX : res); +} + +/* Smallest power of two >= x, branchlessly via CLZ. Returns UINT64_MAX on overflow. */ +static inline uint64_t term_next_pow2_64(uint64_t x) +{ + uint64_t v = x <= 1 ? 1 : x - 1; + int lz = term_clz64(v); + uint64_t res = UINT64_C(1) << ((64 - lz) & 63); + return (x <= 1) ? 1 : (lz == 0 ? UINT64_MAX : res); +} + +static inline size_t term_next_pow2(size_t x) +{ +#if SIZE_MAX > UINT32_MAX + return (size_t)term_next_pow2_64(x); +#else + return (size_t)term_next_pow2_32((uint32_t)x); +#endif +} + +/* Grows cap by doubling until >= need, branchlessly. + * If cap >= need, returns cap. Otherwise returns next power of two >= need. */ +static inline uint32_t term_grow_cap32(uint32_t cap, uint32_t need) +{ + return cap >= need ? cap : term_next_pow2_32(need); +} + +static inline uint64_t term_grow_cap64(uint64_t cap, uint64_t need) +{ + return cap >= need ? cap : term_next_pow2_64(need); +} + +static inline size_t term_grow_cap(size_t cap, size_t need) +{ +#if SIZE_MAX > UINT32_MAX + return (size_t)term_grow_cap64(cap, need); +#else + return (size_t)term_grow_cap32((uint32_t)cap, (uint32_t)need); +#endif +} + + /* A spin-wait hint. Compilers without one get a no-op. */ static inline void term_cpu_relax(void) { -- cgit v1.2.3