bitops: new module.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/ccan/bitops/LICENSE b/ccan/bitops/LICENSE
new file mode 120000 (symlink)
index 0000000..b7951da
--- /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 (file)
index 0000000..d47fe7b
--- /dev/null
+++ b/ccan/bitops/_info
@@ -0,0 +1,43 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * bitops - bit counting routines
+ *
+ * These offer convenience wrappers around (and, as necessary,
+ * replacements for) the builtin bit testing/counting routines.
+ *
+ * Example:
+ * #include <ccan/bitops/bitops.h>
+ * #include <stdio.h>
+ *
+ * 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 <rusty@rustcorp.com.au>
+ */
+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 (file)
index 0000000..fef857a
--- /dev/null
+++ b/ccan/bitops/bitops.c
@@ -0,0 +1,79 @@
+/* CC0 license (public domain) - see LICENSE file for details */
+#include <ccan/bitops/bitops.h>
+#include <stdlib.h>
+
+/* 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 (file)
index 0000000..899b915
--- /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 <stdint.h>
+
+#if defined(CCAN_DEBUG) || defined(CCAN_BITOPS_DEBUG)
+#include <assert.h>
+#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 (file)
index 0000000..c3b3d2c
--- /dev/null
+++ b/ccan/bitops/test/run-selftest.c
@@ -0,0 +1,89 @@
+#include <ccan/bitops/bitops.c>
+#include <ccan/tap/tap.h>
+
+/* 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 <ccan/bitops/bitops.c>
+
+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 (file)
index 0000000..5dba932
--- /dev/null
+++ b/ccan/bitops/test/run.c
@@ -0,0 +1,113 @@
+#define CCAN_BITOPS_DEBUG 1
+#include <ccan/bitops/bitops.c>
+#include <ccan/tap/tap.h>
+
+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();
+}