From 9768940fbd11558b8dab3453aa419a3433933d50 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 13 May 2024 01:18:53 -0700 Subject: [PATCH] stdbit: port to theoretical platforms Port to theoretical platforms that C and POSIX allow but are not likely to ever exist. This is mostly just to document the existing source code: when optimizing, the machine code should be largely unchanged even on platforms lacking __builtin_clz etc. * lib/stdbit.in.h: Omit static_assert that checks for 8-bit bits. stdbit-tests checks for this, and omitting the static_assert here removes a module dependency. (__gl_stdbit_clzll): Do not limit word size to 128 bits. (__gl_stdbit_popcount255): Rename from __gl_stdbit_popcount255. All uses changed. Do not limit word size to 255 bits. Correct bugs on odd theoretical platforms where the word size is not a power of 2. * modules/stdbit (Depends-on): Remove assert-h. --- ChangeLog | 17 ++++++++++ lib/stdbit.in.h | 88 ++++++++++++++++++++++++++++++++----------------- modules/stdbit | 1 - 3 files changed, 74 insertions(+), 32 deletions(-) diff --git a/ChangeLog b/ChangeLog index e14eedd9c7..b1cc7ffcf0 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,20 @@ +2024-05-13 Paul Eggert + + stdbit: port to theoretical platforms + Port to theoretical platforms that C and POSIX allow but are not + likely to ever exist. This is mostly just to document the existing + source code: when optimizing, the machine code should be largely + unchanged even on platforms lacking __builtin_clz etc. + * lib/stdbit.in.h: Omit static_assert that checks for 8-bit bits. + stdbit-tests checks for this, and omitting the static_assert here + removes a module dependency. + (__gl_stdbit_clzll): Do not limit word size to 128 bits. + (__gl_stdbit_popcount255): Rename from __gl_stdbit_popcount255. + All uses changed. Do not limit word size to 255 bits. Correct + bugs on odd theoretical platforms where the word size is not a + power of 2. + * modules/stdbit (Depends-on): Remove assert-h. + 2024-05-12 Paul Eggert stdbit-tests: make GNULIB_TEST_STDBIT work standalone diff --git a/lib/stdbit.in.h b/lib/stdbit.in.h index ed68bd6513..36349af1fd 100644 --- a/lib/stdbit.in.h +++ b/lib/stdbit.in.h @@ -34,10 +34,6 @@ _GL_INLINE_HEADER_BEGIN extern "C" { #endif -/* Bytes must be 8 bits, as POSIX requires. This implementation uses - 8 instead of CHAR_BIT to avoid namespace pollution. */ -static_assert ((unsigned char) -1 == (1 << 8) - 1); - /* An expression, preferably with the type of A, that has the value of B. */ #if ((defined __GNUC__ && 2 <= __GNUC__) \ || (defined __clang_major__ && 4 <= __clang_major__) \ @@ -131,13 +127,15 @@ extern char const __gl_stdbit_clztab[256]; _GL_STDBIT_INLINE int __gl_stdbit_clzll (unsigned long long int n) { - static_assert (8 * sizeof n <= 1 << 7); int r = 0; - int a6 = (0xffffffffffffffff < n) << 6; n >>= a6; r |= a6; - 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]; + for (int i = 8 * sizeof n >> 1; 1 << 6 <= i; i >>= 1) + { + int a = (1ull << i <= n) * i; n >>= a; r += a; + } + 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]; } _GL_STDBIT_INLINE int __gl_stdbit_clz (unsigned int n) @@ -212,22 +210,50 @@ __gl_stdbit_ctzll (unsigned long long int n) #else /* Count the number of 1 bits in N. */ _GL_STDBIT_INLINE int -__gl_stdbit_popcount255 (unsigned long long int n) +__gl_stdbit_popcount_wide (unsigned long long int n) { - unsigned long long int - max = -1ull, - x555555 = max / (1 << 1 | 1), /* 0x555555... */ - x333333 = max / (1 << 2 | 1), /* 0x333333... */ - x0f0f0f = max / (1 << 4 | 1), /* 0x0f0f0f... */ - x010101 = max / ((1 << 8) - 1); /* 0x010101... */ - n -= (n >> 1) & x555555; - n = (n & x333333) + ((n >> 2) & x333333); - n = (n + (n >> 4)) & x0f0f0f; - - /* The multiplication means the popcount should fit in the leading 8 - bits of the product, so N should be narrower than 256 bits. */ - static_assert (8 * sizeof n < 1 << 8); - return n * x010101 >> 8 * (sizeof n - 1); + if (sizeof n & (sizeof n - 1)) + { + /* Use a simple O(log N) loop on theoretical platforms where N's + width is not a power of 2. */ + int count = 0; + for (int i = 0; i < 8 * sizeof n; i++, n >>= 1) + count += n & 1; + return count; + } + else + { + /* N's width is a power of 2; count in parallel. */ + unsigned long long int + max = -1ull, + x555555 = max / (1 << 1 | 1), /* 0x555555... */ + x333333 = max / (1 << 2 | 1), /* 0x333333... */ + x0f0f0f = max / (1 << 4 | 1), /* 0x0f0f0f... */ + x010101 = max / ((1 << 8) - 1), /* 0x010101... */ + x000_7f = max / 0xffffffffffffffff * 0x7f; /* 0x000000000000007f... */ + n -= (n >> 1) & x555555; + n = (n & x333333) + ((n >> 2) & x333333); + n = (n + (n >> 4)) & x0f0f0f; + + /* If the popcount always fits in 8 bits, multiply so that the + popcount is in the leading 8 bits of the product; these days + this is typically faster than the alternative below. */ + if (8 * sizeof n < 1 << 8) + return n * x010101 >> 8 * (sizeof n - 1); + + /* N is at least 256 bits wide! Fall back on an O(log log N) + loop that a compiler could unroll. Unroll the first three + iterations by hand, to skip some division and masking. This + is the most we can easily do without hassling with constants + that a typical-platform compiler would reject. */ + n += n >> (1 << 3); + n += n >> (1 << 4); + n += n >> (1 << 5); + n &= x000_7f; + for (int i = 64; i < 8 * sizeof n; i <<= 1) + n = (n + (n >> i)) & max / (1ull << i | 1); + return n; + } } # ifdef _MSC_VER @@ -268,26 +294,26 @@ __gl_stdbit_popcount (unsigned int n) { return (__gl_stdbit_popcount_supported () ? __popcnt (n) - : __gl_stdbit_popcount255 (n)); + : __gl_stdbit_popcount_wide (n)); } _GL_STDBIT_INLINE int __gl_stdbit_popcountl (unsigned long int n) { return (__gl_stdbit_popcount_supported () ? __popcnt (n) - : __gl_stdbit_popcount255 (n)); + : __gl_stdbit_popcount_wide (n)); } _GL_STDBIT_INLINE int __gl_stdbit_popcountll (unsigned long long int n) { return (__gl_stdbit_popcount_supported () ? __popcnt64 (n) - : __gl_stdbit_popcount255 (n)); + : __gl_stdbit_popcount_wide (n)); } # else /* !_MSC_VER */ -# define __gl_stdbit_popcount __gl_stdbit_popcount255 -# define __gl_stdbit_popcountl __gl_stdbit_popcount255 -# define __gl_stdbit_popcountll __gl_stdbit_popcount255 +# define __gl_stdbit_popcount __gl_stdbit_popcount_wide +# define __gl_stdbit_popcountl __gl_stdbit_popcount_wide +# define __gl_stdbit_popcountll __gl_stdbit_popcount_wide # endif #endif diff --git a/modules/stdbit b/modules/stdbit index e8144ab71a..f70386566b 100644 --- a/modules/stdbit +++ b/modules/stdbit @@ -7,7 +7,6 @@ lib/stdbit.in.h m4/stdbit_h.m4 Depends-on: -assert-h [$GL_GENERATE_STDBIT_H] stdbool [$GL_GENERATE_STDBIT_H] configure.ac: -- 2.39.5