From: Rusty Russell Date: Mon, 26 Mar 2018 05:03:11 +0000 (+1030) Subject: bitops: new module. X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=eb10bf9f4e37a73bae203dab71a4daffa2c96229 bitops: new module. Signed-off-by: Rusty Russell --- diff --git a/ccan/bitops/LICENSE b/ccan/bitops/LICENSE new file mode 120000 index 00000000..b7951dab --- /dev/null +++ b/ccan/bitops/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0 \ No newline at end of file diff --git a/ccan/bitops/_info b/ccan/bitops/_info new file mode 100644 index 00000000..d47fe7b2 --- /dev/null +++ b/ccan/bitops/_info @@ -0,0 +1,43 @@ +#include "config.h" +#include +#include + +/** + * bitops - bit counting routines + * + * These offer convenience wrappers around (and, as necessary, + * replacements for) the builtin bit testing/counting routines. + * + * Example: + * #include + * #include + * + * int main(int argc, char *argv[]) + * { + * unsigned int v = atoi(argv[1]); + * + * printf("Number of 1 bits: %i\n", bitops_weight32(v)); + * if (v != 0) { + * printf("Least-significant set bit: %i\n", bitops_ls32(v)); + * printf("Most-significant set bit: %i\n", bitops_hs32(v)); + * printf("Least-significant clear bit: %i\n", bitops_lc32(v)); + * printf("Most-significant clear bit: %i\n", bitops_hc32(v)); + * } + * return 0; + * } + * + * License: CC0 (Public Domain) + * Author: Rusty Russell + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + return 0; + } + + return 1; +} diff --git a/ccan/bitops/bitops.c b/ccan/bitops/bitops.c new file mode 100644 index 00000000..fef857a4 --- /dev/null +++ b/ccan/bitops/bitops.c @@ -0,0 +1,79 @@ +/* CC0 license (public domain) - see LICENSE file for details */ +#include +#include + +/* We do naive replacement versions: good for testing, and really your + * compiler should do better. */ +#ifdef BITOPS_NEED_FFS +int bitops_ffs32(uint32_t u) +{ + int i; + for (i = 0; i < 32; i++) + if (u & ((uint32_t)1 << i)) + return i + 1; + return 0; +} + +int bitops_ffs64(uint64_t u) +{ + int i; + for (i = 0; i < 64; i++) + if (u & ((uint64_t)1 << i)) + return i + 1; + return 0; +} +#endif + +#ifdef BITOPS_NEED_CLZ +int bitops_clz32(uint32_t u) +{ + int i; + for (i = 0; i < 32; i++) + if (u & ((uint32_t)1 << (31 - i))) + return i; + abort(); +} + +int bitops_clz64(uint64_t u) +{ + int i; + for (i = 0; i < 64; i++) + if (u & ((uint64_t)1 << (63 - i))) + return i; + abort(); +} +#endif + +#ifdef BITOPS_NEED_CTZ +int bitops_ctz32(uint32_t u) +{ + BITOPS_ASSERT_NONZERO(u); + return bitops_ffs32(u) - 1; +} + +int bitops_ctz64(uint64_t u) +{ + BITOPS_ASSERT_NONZERO(u); + return bitops_ffs64(u) - 1; +} +#endif + +#ifdef BITOPS_NEED_WEIGHT +int bitops_weight32(uint32_t u) +{ + int i, num = 0; + for (i = 0; i < 32; i++) + if (u & ((uint32_t)1 << i)) + num++; + return num; +} + +int bitops_weight64(uint64_t u) +{ + int i, num = 0; + for (i = 0; i < 64; i++) + if (u & ((uint64_t)1 << i)) + num++; + return num; +} +#endif diff --git a/ccan/bitops/bitops.h b/ccan/bitops/bitops.h new file mode 100644 index 00000000..899b9150 --- /dev/null +++ b/ccan/bitops/bitops.h @@ -0,0 +1,223 @@ +/* CC0 license (public domain) - see LICENSE file for details */ +#ifndef CCAN_BITOPS_H +#define CCAN_BITOPS_H +#include "config.h" +#include + +#if defined(CCAN_DEBUG) || defined(CCAN_BITOPS_DEBUG) +#include +#define BITOPS_ASSERT_NONZERO(u) assert((u) != 0) +#else +#define BITOPS_ASSERT_NONZERO(u) +#endif + +#if HAVE_BUILTIN_FFS && HAVE_BUILTIN_FFSL && HAVE_BUILTIN_FFSLL +/** + * bitops_ffs32: find first set bit in a uint32_t + * + * Returns 1 for least signficant bit, 32 for most significant bit, 0 + * for no bits set. + */ +static inline int bitops_ffs32(uint32_t u) +{ + return __builtin_ffs(u); +} + +/** + * bitops_ffs64: find lowest set bit in a uint64_t + * + * Returns 1 for least signficant bit, 32 for most significant bit, 0 + * for no bits set. + */ +static inline int bitops_ffs64(uint64_t u) +{ + if (sizeof(u) == sizeof(long)) + return __builtin_ffsl(u); + else + return __builtin_ffsll(u); +} +#else +int bitops_ffs32(uint32_t u); +int bitops_ffs64(uint64_t u); +#define BITOPS_NEED_FFS 1 +#endif + +#if HAVE_BUILTIN_CLZ && HAVE_BUILTIN_CLZL && HAVE_BUILTIN_CLZLL +/** + * bitops_clz32: count leading zeros in a uint32_t (must not be 0) + * + * Returns 0 if most signficant bit is set, 31 if only least + * signficant bit is set. + */ +static inline int bitops_clz32(uint32_t u) +{ + BITOPS_ASSERT_NONZERO(u); + return __builtin_clz(u); +} + +/** + * bitops_clz64: count leading zeros in a uint64_t (must not be 0) + * + * Returns 0 if most signficant bit is set, 63 if only least + * signficant bit is set. + */ +static inline int bitops_clz64(uint64_t u) +{ + BITOPS_ASSERT_NONZERO(u); + if (sizeof(u) == sizeof(long)) + return __builtin_clzl(u); + else + return __builtin_clzll(u); +} +#else +int bitops_clz32(uint32_t u); +int bitops_clz64(uint64_t u); +#define BITOPS_NEED_CLZ 1 +#endif + +#if HAVE_BUILTIN_CTZ && HAVE_BUILTIN_CTZL && HAVE_BUILTIN_CTZLL +/** + * bitops_ctz32: count trailing zeros in a uint32_t (must not be 0) + * + * Returns 0 if least signficant bit is set, 31 if only most + * signficant bit is set. + */ +static inline int bitops_ctz32(uint32_t u) +{ + BITOPS_ASSERT_NONZERO(u); + return __builtin_ctz(u); +} + +/** + * bitops_ctz64: count trailing zeros in a uint64_t (must not be 0) + * + * Returns 0 if least signficant bit is set, 63 if only most + * signficant bit is set. + */ +static inline int bitops_ctz64(uint64_t u) +{ + BITOPS_ASSERT_NONZERO(u); + if (sizeof(u) == sizeof(long)) + return __builtin_ctzl(u); + else + return __builtin_ctzll(u); +} +#else +int bitops_ctz32(uint32_t u); +int bitops_ctz64(uint64_t u); +#define BITOPS_NEED_CTZ 1 +#endif + +/** + * bitops_ls32: find lowest set bit in a uint32_t (must not be zero) + * + * Returns 0 for least signficant bit, 31 for most significant bit. + */ +static inline int bitops_ls32(uint32_t u) +{ + BITOPS_ASSERT_NONZERO(u); + return bitops_ffs32(u) - 1; +} + +/** + * bitops_ls64: find lowest set bit in a uint64_t (must not be zero) + * + * Returns 0 for least signficant bit, 63 for most significant bit. + */ +static inline int bitops_ls64(uint64_t u) +{ + BITOPS_ASSERT_NONZERO(u); + return bitops_ffs64(u) - 1; +} + +/** + * bitops_hs32: find highest set bit in a uint32_t (must not be zero) + * + * Returns 0 for least signficant bit, 31 for most significant bit. + */ +static inline int bitops_hs32(uint32_t u) +{ + BITOPS_ASSERT_NONZERO(u); + return 31 - bitops_clz32(u); +} + +/** + * bitops_hs64: find highest set bit in a uint64_t (must not be zero) + * + * Returns 0 for least signficant bit, 63 for most significant bit. + */ +static inline int bitops_hs64(uint64_t u) +{ + BITOPS_ASSERT_NONZERO(u); + return 63 - bitops_clz64(u); +} + +/** + * bitops_lc32: find lowest clear bit in a uint32_t (must not be 0xFFFFFFFF) + * + * Returns 0 for least signficant bit, 31 for most significant bit. + */ +static inline int bitops_lc32(uint32_t u) +{ + return bitops_ctz32(~u); +} + +/** + * bitops_lc64: find lowest clear bit in a uint64_t (must not be 0xFFFFFFFFFFFFFFFF) + * + * Returns 0 for least signficant bit, 63 for most significant bit. + */ +static inline int bitops_lc64(uint64_t u) +{ + return bitops_ctz64(~u); +} + +/** + * bitops_hc32: find highest clear bit in a uint32_t (must not be 0xFFFFFFFF) + * + * Returns 0 for least signficant bit, 31 for most significant bit. + */ +static inline int bitops_hc32(uint32_t u) +{ + return 31 - bitops_clz32(~u); +} + +/** + * bitops_hc64: find highest clear bit in a uint64_t (must not be 0xFFFFFFFFFFFFFFFF) + * + * Returns 0 for least signficant bit, 63 for most significant bit. + */ +static inline int bitops_hc64(uint64_t u) +{ + return 63 - bitops_clz64(~u); +} + +#if HAVE_BUILTIN_POPCOUNT && HAVE_BUILTIN_POPCOUNTL && HAVE_BUILTIN_POPCOUNTLL +/** + * bitops_weight32: count number of bits set in a uint32_t + * + * Returns 0 to 32. + */ +static inline int bitops_weight32(uint32_t u) +{ + return __builtin_popcount(u); +} + +/** + * bitops_weight64: count number of bits set in a uint64_t + * + * Returns 0 to 64. + */ +static inline int bitops_weight64(uint64_t u) +{ + if (sizeof(u) == sizeof(long)) + return __builtin_popcountl(u); + else + return __builtin_popcountll(u); +} +#else +int bitops_weight32(uint32_t u); +int bitops_weight64(uint64_t u); +#define BITOPS_NEED_WEIGHT 1 +#endif +#endif /* CCAN_BITOPS_H */ diff --git a/ccan/bitops/test/run-selftest.c b/ccan/bitops/test/run-selftest.c new file mode 100644 index 00000000..c3b3d2c1 --- /dev/null +++ b/ccan/bitops/test/run-selftest.c @@ -0,0 +1,89 @@ +#include +#include + +/* Get naive versions */ +#ifndef BITOPS_NEED_FFS +#define BITOPS_NEED_FFS +#endif + +#ifndef BITOPS_NEED_CLZ +#define BITOPS_NEED_CLZ +#endif + +#ifndef BITOPS_NEED_CTZ +#define BITOPS_NEED_CTZ +#endif + +#ifndef BITOPS_NEED_WEIGHT +#define BITOPS_NEED_WEIGHT +#endif + +int naive_bitops_ffs32(uint32_t u); +int naive_bitops_ffs64(uint64_t u); +int naive_bitops_clz32(uint32_t u); +int naive_bitops_clz64(uint64_t u); +int naive_bitops_ctz32(uint32_t u); +int naive_bitops_ctz64(uint64_t u); +int naive_bitops_weight32(uint32_t u); +int naive_bitops_weight64(uint64_t u); + +#define bitops_ffs32 naive_bitops_ffs32 +#define bitops_ffs64 naive_bitops_ffs64 +#define bitops_clz32 naive_bitops_clz32 +#define bitops_clz64 naive_bitops_clz64 +#define bitops_ctz32 naive_bitops_ctz32 +#define bitops_ctz64 naive_bitops_ctz64 +#define bitops_weight32 naive_bitops_weight32 +#define bitops_weight64 naive_bitops_weight64 +#include + +static void test_against_naive32(uint32_t v) +{ + ok1(bitops_ffs32(v) == naive_bitops_ffs32(v)); + ok1(bitops_clz32(v) == naive_bitops_clz32(v)); + ok1(bitops_ctz32(v) == naive_bitops_ctz32(v)); + ok1(bitops_weight32(v) == naive_bitops_weight32(v)); +} + +static void test_against_naive64(uint64_t v) +{ + ok1(bitops_ffs64(v) == naive_bitops_ffs64(v)); + ok1(bitops_clz64(v) == naive_bitops_clz64(v)); + ok1(bitops_ctz64(v) == naive_bitops_ctz64(v)); + ok1(bitops_weight64(v) == naive_bitops_weight64(v)); +} + +int main(void) +{ + int i, j; + uint64_t v; + + /* This is how many tests you plan to run */ + plan_tests(32 * 32 * 8 + (64 * 64) * 8 + 4 + 4); + + /* Various comparisons with any one or two bits set */ + for (i = 0; i < 32; i++) { + for (j = 0; j < 32; j++) { + v = ((uint64_t)1 << i) | ((uint64_t)1 << j); + test_against_naive32(v); + test_against_naive32(~v); + } + } + + for (i = 0; i < 64; i++) { + for (j = 0; j < 64; j++) { + v = ((uint64_t)1 << i) | ((uint64_t)1 << j); + test_against_naive64(v); + test_against_naive64(~v); + } + } + + test_against_naive64(0xFFFFFFFFFFFFFFFFULL); + ok1(bitops_ffs32(0) == naive_bitops_ffs32(0)); + ok1(bitops_ffs64(0) == naive_bitops_ffs64(0)); + ok1(bitops_weight32(0) == naive_bitops_weight32(0)); + ok1(bitops_weight64(0) == naive_bitops_weight64(0)); + + /* This exits depending on whether all tests passed */ + return exit_status(); +} diff --git a/ccan/bitops/test/run.c b/ccan/bitops/test/run.c new file mode 100644 index 00000000..5dba932d --- /dev/null +++ b/ccan/bitops/test/run.c @@ -0,0 +1,113 @@ +#define CCAN_BITOPS_DEBUG 1 +#include +#include + +int main(void) +{ + int i; + + /* This is how many tests you plan to run */ + plan_tests(68 + 6 * (31 + 63)); + + for (i = 0; i < 32; i++) + ok1(bitops_ffs32(1 << i) == i+1); + ok1(bitops_ffs32(0) == 0); + for (i = 0; i < 64; i++) + ok1(bitops_ffs64((uint64_t)1 << i) == i+1); + ok1(bitops_ffs64(0) == 0); + + /* Higher bits don't affect result */ + for (i = 0; i < 32; i++) + ok1(bitops_ffs32(0xFFFFFFFFFFFFFFFFULL << i) == i+1); + ok1(bitops_ffs32(0) == 0); + for (i = 0; i < 64; i++) + ok1(bitops_ffs64(0xFFFFFFFFFFFFFFFFULL << i) == i+1); + ok1(bitops_ffs64(0) == 0); + + for (i = 0; i < 32; i++) + ok1(bitops_clz32(1 << i) == 31 - i); + for (i = 0; i < 64; i++) + ok1(bitops_clz64((uint64_t)1 << i) == 63 - i); + + /* Lower bits don't effect results */ + for (i = 0; i < 32; i++) + ok1(bitops_clz32((1 << i) + (1 << i)-1) == 31 - i); + for (i = 0; i < 64; i++) + ok1(bitops_clz64(((uint64_t)1 << i) + ((uint64_t)1 << i)-1) + == 63 - i); + + for (i = 0; i < 32; i++) + ok1(bitops_ctz32(1 << i) == i); + for (i = 0; i < 64; i++) + ok1(bitops_ctz64((uint64_t)1 << i) == i); + + /* Higher bits don't affect result */ + for (i = 0; i < 32; i++) + ok1(bitops_ctz32(0xFFFFFFFFFFFFFFFFULL << i) == i); + for (i = 0; i < 64; i++) + ok1(bitops_ctz64(0xFFFFFFFFFFFFFFFFULL << i) == i); + + /* Now we've tested low-level, test higher ones */ + ok1(bitops_ls32(1U) == 0); + ok1(bitops_ls32(0xFFFFFFFF) == 0); + ok1(bitops_ls32(1U << 31) == 31); + ok1(bitops_ls32(0xFFFF0000) == 16); + + ok1(bitops_ls64(1U) == 0); + ok1(bitops_ls64(0xFFFFFFFF) == 0); + ok1(bitops_ls64(1U << 31) == 31); + ok1(bitops_ls64(0xFFFF0000) == 16); + ok1(bitops_ls64((uint64_t)1 << 32) == 32); + ok1(bitops_ls64((uint64_t)1 << 63) == 63); + ok1(bitops_ls64(0xFFFFFFFFFFFF0000ULL) == 16); + ok1(bitops_ls64(0xFFFF000000000000ULL) == 48); + + ok1(bitops_hs32(1U) == 0); + ok1(bitops_hs32(0xFFFFFFFF) == 31); + ok1(bitops_hs32(1U << 31) == 31); + ok1(bitops_hs32(0xFFFF0000) == 31); + ok1(bitops_hs32(0x0000FFFF) == 15); + + ok1(bitops_hs64(1U) == 0); + ok1(bitops_hs64(0xFFFFFFFF) == 31); + ok1(bitops_hs64(1U << 31) == 31); + ok1(bitops_hs64(0xFFFF0000) == 31); + ok1(bitops_hs32(0x0000FFFF) == 15); + ok1(bitops_hs64((uint64_t)1 << 32) == 32); + ok1(bitops_hs64((uint64_t)1 << 63) == 63); + ok1(bitops_hs64(0xFFFFFFFFFFFF0000ULL) == 63); + ok1(bitops_hs64(0x0000FFFF00000000ULL) == 47); + + ok1(bitops_lc32(~(1U)) == 0); + ok1(bitops_lc32(~(0xFFFFFFFF)) == 0); + ok1(bitops_lc32(~(1U << 31)) == 31); + ok1(bitops_lc32(~(0xFFFF0000)) == 16); + + ok1(bitops_lc64(~(1U)) == 0); + ok1(bitops_lc64(~(0xFFFFFFFF)) == 0); + ok1(bitops_lc64(~(1U << 31)) == 31); + ok1(bitops_lc64(~(0xFFFF0000)) == 16); + ok1(bitops_lc64(~((uint64_t)1 << 32)) == 32); + ok1(bitops_lc64(~((uint64_t)1 << 63)) == 63); + ok1(bitops_lc64(~(0xFFFFFFFFFFFF0000ULL)) == 16); + ok1(bitops_lc64(~(0xFFFF000000000000ULL)) == 48); + + ok1(bitops_hc32(~(1U)) == 0); + ok1(bitops_hc32(~(0xFFFFFFFF)) == 31); + ok1(bitops_hc32(~(1U << 31)) == 31); + ok1(bitops_hc32(~(0xFFFF0000)) == 31); + ok1(bitops_hc32(~(0x0000FFFF)) == 15); + + ok1(bitops_hc64(~(1ULL)) == 0); + ok1(bitops_hc64(~(0xFFFFFFFFULL)) == 31); + ok1(bitops_hc64(~(1ULL << 31)) == 31); + ok1(bitops_hc64(~(0xFFFF0000ULL)) == 31); + ok1(bitops_hc64(~(0x0000FFFFULL)) == 15); + ok1(bitops_hc64(~((uint64_t)1 << 32)) == 32); + ok1(bitops_hc64(~((uint64_t)1 << 63)) == 63); + ok1(bitops_hc64(~(0xFFFFFFFFFFFF0000ULL)) == 63); + ok1(bitops_hc64(~(0x0000FFFF00000000ULL)) == 47); + + /* This exits depending on whether all tests passed */ + return exit_status(); +}