From 1b7e82be9dd80fbb67a5567cdf1d60d36dd40db2 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 13 May 2024 15:21:55 -0700 Subject: [PATCH] stdbit: redo clzll without lookcup table * lib/stdbit.c (__gl_stdbit_clztab): * lib/stdbit.in.h (__gl_stdbit_clzll): [!_GL_STDBIT_HAS_BUILTIN_CLZ && !_MSC_VER]: Rewrite to avoid the need for a lookup table in memory, and remove the lookup table. Do this by shrinking the table to 64 bits and puttiung in a 64-bit constant. Although this needs another round of shifts, it avoids the need for a multiplication and memory access a la de Bruijn, and is probably a win. --- ChangeLog | 12 ++++++++++++ lib/stdbit.c | 24 ------------------------ lib/stdbit.in.h | 5 ++--- 3 files changed, 14 insertions(+), 27 deletions(-) diff --git a/ChangeLog b/ChangeLog index 18aab772fc..3e4eba3796 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,15 @@ +2024-05-13 Paul Eggert + + stdbit: redo clzll without lookcup table + * lib/stdbit.c (__gl_stdbit_clztab): + * lib/stdbit.in.h (__gl_stdbit_clzll): + [!_GL_STDBIT_HAS_BUILTIN_CLZ && !_MSC_VER]: Rewrite to avoid the + need for a lookup table in memory, and remove the lookup table. + Do this by shrinking the table to 64 bits and puttiung in a 64-bit + constant. Although this needs another round of shifts, it avoids + the need for a multiplication and memory access a la de Bruijn, + and is probably a win. + 2024-05-13 Bruno Haible stdbit tests: Adhere better to Gnulib naming conventions. diff --git a/lib/stdbit.c b/lib/stdbit.c index f2a51b10f7..a9f0ef5074 100644 --- a/lib/stdbit.c +++ b/lib/stdbit.c @@ -22,30 +22,6 @@ #define _GL_STDBIT_INLINE _GL_EXTERN_INLINE #include -#if !defined _GL_STDBIT_HAS_BUILTIN_CLZ && !_MSC_VER -/* __gl_stdbit_clztab[B] is the number of leading zeros in - the 8-bit byte with value B. */ -char const __gl_stdbit_clztab[256] = - { - 8, - 7, - 6, 6, - 5, 5, 5, 5, - 4, 4, 4, 4, 4, 4, 4, 4, - 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, - - 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, - 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, - - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - - /* The rest is zero. */ - }; -#endif - #if 1500 <= _MSC_VER && (defined _M_IX86 || defined _M_X64) signed char __gl_stdbit_popcount_support; #endif diff --git a/lib/stdbit.in.h b/lib/stdbit.in.h index 15533dbbda..18efaf2d7c 100644 --- a/lib/stdbit.in.h +++ b/lib/stdbit.in.h @@ -122,8 +122,6 @@ __gl_stdbit_clzll (unsigned long long int n) #else /* !_MSC_VER */ -extern char const __gl_stdbit_clztab[256]; - _GL_STDBIT_INLINE int __gl_stdbit_clzll (unsigned long long int n) { @@ -135,7 +133,8 @@ __gl_stdbit_clzll (unsigned long long int n) int a5 = (0x00000000ffffffff < n) << 5; n >>= a5; r += a5; int a4 = (0x000000000000ffff < n) << 4; n >>= a4; r += a4; int a3 = (0x00000000000000ff < n) << 3; n >>= a3; r += a3; - return (8 * (sizeof n - 1) - r) + __gl_stdbit_clztab[n]; + int a2 = (0x000000000000000f < n) << 2; n >>= a2; r += a2; + return (8 * sizeof n - (1 << 2) - r) + ((0x11112234ull >> (n << 2)) & 0xf); } _GL_STDBIT_INLINE int __gl_stdbit_clz (unsigned int n) -- 2.39.5