[ccan] [PATCH] maskn & bitops: add new modules
Cody P Schafer
dev at codyps.com
Wed Jul 9 09:23:41 EST 2014
'maskn' provides generation of n-bit masks from a given range.
'bitops' provides some generic bit operations that maskn needs.
Both operate on 32-bit values only (that's just what I needed at this
point).
bitops currently has some not-so-great detection of features to support
the the intrinsics provided by IAR's C compiler for ARM. Not sure how
we want to handle that. "HAVE_CLZ and HAVE_RBIT" doesn't seem like it
will be useful for other compilers, and we'll still end up with similar
ifdefs to generate the builtin_clz/builtin_ctz macros (not to mention
the need to include intrinsics.h).
Additionally, there is some overlap between ilog and bitops that would
be good to remove.
Signed-off-by: Cody P Schafer <dev at codyps.com>
---
Makefile-ccan | 2 +
ccan/bitops/LICENSE | 1 +
ccan/bitops/_info | 29 +++++++++++++
ccan/bitops/bitops.c | 86 +++++++++++++++++++++++++++++++++++++++
ccan/bitops/bitops.h | 19 +++++++++
ccan/bitops/test/run-no-builtin.c | 4 ++
ccan/bitops/test/run.c | 3 ++
ccan/bitops/test/run.h | 31 ++++++++++++++
ccan/maskn/LICENSE | 1 +
ccan/maskn/_info | 41 +++++++++++++++++++
ccan/maskn/maskn.c | 36 ++++++++++++++++
ccan/maskn/maskn.h | 30 ++++++++++++++
ccan/maskn/test/run.c | 37 +++++++++++++++++
13 files changed, 320 insertions(+)
create mode 120000 ccan/bitops/LICENSE
create mode 100644 ccan/bitops/_info
create mode 100644 ccan/bitops/bitops.c
create mode 100644 ccan/bitops/bitops.h
create mode 100644 ccan/bitops/test/run-no-builtin.c
create mode 100644 ccan/bitops/test/run.c
create mode 100644 ccan/bitops/test/run.h
create mode 120000 ccan/maskn/LICENSE
create mode 100644 ccan/maskn/_info
create mode 100644 ccan/maskn/maskn.c
create mode 100644 ccan/maskn/maskn.h
create mode 100644 ccan/maskn/test/run.c
diff --git a/Makefile-ccan b/Makefile-ccan
index 40d0389..6912924 100644
--- a/Makefile-ccan
+++ b/Makefile-ccan
@@ -37,6 +37,7 @@ MODS_WITH_SRC := antithread \
autodata \
avl \
bdelta \
+ bitops \
block_pool \
breakpoint \
btree \
@@ -68,6 +69,7 @@ MODS_WITH_SRC := antithread \
lbalance \
likely \
list \
+ maskn \
md4 \
memmem \
net \
diff --git a/ccan/bitops/LICENSE b/ccan/bitops/LICENSE
new file mode 120000
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
index 0000000..12e8f7f
--- /dev/null
+++ b/ccan/bitops/_info
@@ -0,0 +1,29 @@
+#include "config.h"
+#include <string.h>
+
+/**
+ * bitops - some basic bit operations
+ *
+ * These provide a few generic bit operations. Currently, only those needed for
+ * maskn were added.
+ *
+ * License: CC0 (Public Domain)
+ * Author: Cody P Schafer <dev at codyps.com>
+ */
+int main(int argc, char *argv[])
+{
+ /* Expect exactly one argument */
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ puts("ccan/compiler");
+ return 0;
+ }
+
+ if (strcmp(argv[1], "testdepends") == 0) {
+ return 0;
+ }
+
+ return 1;
+}
diff --git a/ccan/bitops/bitops.c b/ccan/bitops/bitops.c
new file mode 100644
index 0000000..f5e4fde
--- /dev/null
+++ b/ccan/bitops/bitops.c
@@ -0,0 +1,86 @@
+/* CC0 (Public Domain) - see LICENSE file for details */
+#include <ccan/bitops/bitops.h>
+#include <stdint.h>
+#include <limits.h>
+
+#if defined(__GNUC__) || (HAVE_BUILTIN_CLZ && HAVE_BUILTIN_CTZ)
+/* gcc's __builtin_{clz,ctz}() are undefined if v == 0 */
+# define builtin_clz(v) (v ? __builtin_clz(v) : (sizeof(v) * CHAR_BIT))
+# define builtin_ctz(v) (v ? __builtin_ctz(v) : (sizeof(v) * CHAR_BIT))
+#elif defined(__ICCARM__)
+# include <intrinsics.h>
+/* emits the ARM instruction, which returns 32 if no bits are set */
+# define builtin_clz(v) __CLZ(v)
+# define builtin_ctz(v) __CLZ(__RBIT(v))
+#endif
+
+/* from https://graphics.stanford.edu/~seander/bithacks.html */
+unsigned ctz_32(uint32_t v)
+{
+#ifdef builtin_ctz
+ return builtin_ctz(v);
+#else
+ unsigned c;
+ if (!v)
+ return 32;
+ if (v & 0x1)
+ return 0;
+ c = 1;
+ if ((v & 0xffff) == 0) {
+ v >>= 16;
+ c += 16;
+ }
+ if ((v & 0xff) == 0) {
+ v >>= 8;
+ c += 8;
+ }
+ if ((v & 0xf) == 0) {
+ v >>= 4;
+ c += 4;
+ }
+ if ((v & 0x3) == 0) {
+ v >>= 2;
+ c += 2;
+ }
+ c -= v & 0x1;
+ return c;
+#endif
+}
+
+unsigned clz_32(uint32_t v)
+{
+#ifdef builtin_clz
+ return builtin_clz(v);
+#else
+ unsigned c = 0;
+ if (!v)
+ return 32;
+ if ((v & 0xffff0000) == 0) {
+ c += 16;
+ v <<= 16;
+ }
+ if ((v & 0xff000000) == 0) {
+ c += 8;
+ v <<= 8;
+ }
+ if ((v & 0xf0000000) == 0) {
+ c += 4;
+ v <<= 4;
+ }
+ if ((v & 0xc0000000) == 0) {
+ c += 2;
+ v <<= 2;
+ }
+ if ((v & 0x80000000) == 0) {
+ c += 1;
+ }
+ return c;
+#endif
+}
+
+unsigned fls_m1_32(uint32_t v)
+{
+ if (!v)
+ return 32;
+ return ((CHAR_BIT * sizeof(v)) - clz_32(v)) - 1;
+}
diff --git a/ccan/bitops/bitops.h b/ccan/bitops/bitops.h
new file mode 100644
index 0000000..3863a86
--- /dev/null
+++ b/ccan/bitops/bitops.h
@@ -0,0 +1,19 @@
+/* CC0 (Public Domain) - see LICENSE file for details */
+#ifndef CCAN_BITOPS_H_
+#define CCAN_BITOPS_H_
+
+#include <stdint.h>
+#include <ccan/compiler/compiler.h>
+
+/* assert(bits > 0) */
+#define bit_mask_nz(bits) ((UINTMAX_C(1) << ((bits) - 1) << 1) - 1)
+static inline uintmax_t bit_mask(unsigned bits)
+{
+ return bits ? bit_mask_nz(bits) : 0;
+}
+
+unsigned fls_m1_32(uint32_t v) CONST_FUNCTION;
+unsigned clz_32(uint32_t v) CONST_FUNCTION;
+unsigned ctz_32(uint32_t v) CONST_FUNCTION;
+
+#endif
diff --git a/ccan/bitops/test/run-no-builtin.c b/ccan/bitops/test/run-no-builtin.c
new file mode 100644
index 0000000..5871a1f
--- /dev/null
+++ b/ccan/bitops/test/run-no-builtin.c
@@ -0,0 +1,4 @@
+#include <ccan/bitops/bitops.h>
+#undef builtin_clz
+#undef builtin_ctz
+#include "run.h"
diff --git a/ccan/bitops/test/run.c b/ccan/bitops/test/run.c
new file mode 100644
index 0000000..369a8e5
--- /dev/null
+++ b/ccan/bitops/test/run.c
@@ -0,0 +1,3 @@
+#include <ccan/bitops/bitops.h>
+#include "run.h"
+
diff --git a/ccan/bitops/test/run.h b/ccan/bitops/test/run.h
new file mode 100644
index 0000000..d663541
--- /dev/null
+++ b/ccan/bitops/test/run.h
@@ -0,0 +1,31 @@
+
+#include <ccan/bitops/bitops.c>
+#include <ccan/tap/tap.h>
+
+#define ok_eq(a, b) ok((a) == (b), "%s (%#jx) != %s (%#jx)", #a, (uintmax_t)(a), #b, (uintmax_t)(b))
+int main(void)
+{
+ plan_tests(16);
+
+ ok_eq(ctz_32(0), 32);
+ ok_eq(ctz_32(1), 0);
+ ok_eq(ctz_32(2), 1);
+ ok_eq(ctz_32(UINT32_MAX - 1), 1);
+ ok_eq(ctz_32(UINT32_MAX >> 1), 0);
+
+ ok_eq(clz_32(0), 32);
+ ok_eq(clz_32(1), 31);
+ ok_eq(clz_32(2), 30);
+ ok_eq(clz_32(UINT32_MAX - 1), 0);
+ ok_eq(clz_32(UINT32_MAX >> 1), 1);
+
+ ok_eq(bit_mask(0), 0);
+ ok_eq(bit_mask(1), 1);
+ ok_eq(bit_mask(32), UINT32_MAX);
+
+ ok_eq(fls_m1_32(0), 32);
+ ok_eq(fls_m1_32(1), 0);
+ ok_eq(fls_m1_32(UINT32_MAX), 31);
+
+ return exit_status();
+}
diff --git a/ccan/maskn/LICENSE b/ccan/maskn/LICENSE
new file mode 120000
index 0000000..7455044
--- /dev/null
+++ b/ccan/maskn/LICENSE
@@ -0,0 +1 @@
+../../licenses/LGPL-3
\ No newline at end of file
diff --git a/ccan/maskn/_info b/ccan/maskn/_info
new file mode 100644
index 0000000..2d44b6f
--- /dev/null
+++ b/ccan/maskn/_info
@@ -0,0 +1,41 @@
+#include "config.h"
+#include <string.h>
+
+/**
+ * maskn - generate masks of N bits for a given range
+ *
+ * Masks of N bits as opposed to arbitrary masks (where any bits can be 0 or
+ * 1), here only the trailing bits are 0, all others are 1.
+ *
+ * This ends up assisting in interfacing with hardware that has the ability to
+ * match via masks. The current functions generate the largest mask-ranges that
+ * are within the given range and are fixed to one edge.
+ *
+ * Future:
+ * - largest non-fixed mask-range within range
+ * - smallest non-fixed mask-range containing range
+ * - smallest fixed (to high or low) range containing range
+ * - provide a "fudge" amount to be applied to the fixed ranges to nudge them
+ * towards more optimal ranges.
+ *
+ * License: LGPL (v3 or any later version)
+ * Author: Cody P Schafer <dev at codyps.com>
+ */
+int main(int argc, char *argv[])
+{
+ /* Expect exactly one argument */
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ puts("ccan/compiler");
+ puts("ccan/bitops");
+ return 0;
+ }
+
+ if (strcmp(argv[1], "testdepends") == 0) {
+ return 0;
+ }
+
+ return 1;
+}
diff --git a/ccan/maskn/maskn.c b/ccan/maskn/maskn.c
new file mode 100644
index 0000000..1df4f8f
--- /dev/null
+++ b/ccan/maskn/maskn.c
@@ -0,0 +1,36 @@
+/* LGPLv3 or later - see LICENSE file for details */
+
+#include <ccan/maskn/maskn.h>
+#include <ccan/bitops/bitops.h>
+#include <stdint.h>
+#include <limits.h>
+#include <assert.h>
+
+unsigned maskn_from_range_low(uint32_t base, uint32_t max)
+{
+ assert(base <= max);
+ unsigned base_tz = ctz_32(base);
+ uint32_t mask_1 = bit_mask(base_tz);
+ uint32_t masked_max = max & mask_1;
+ unsigned log_of_max_masked = fls_m1_32(masked_max + 1);
+
+ return log_of_max_masked;
+}
+
+unsigned maskn_from_range_high(uint32_t base, uint32_t min)
+{
+ assert(base >= min);
+ unsigned base_ones = ctz_32(~base);
+ uint32_t diff = base - min;
+ uint32_t masked_diff = diff & bit_mask(base_ones);
+ unsigned mask_bits = fls_m1_32(masked_diff + 1);
+ return mask_bits;
+}
+
+unsigned maskn_from_range(uint32_t base, uint32_t limit)
+{
+ if (base < limit)
+ return maskn_from_range_low(base, limit);
+ else
+ return maskn_from_range_high(base, limit);
+}
diff --git a/ccan/maskn/maskn.h b/ccan/maskn/maskn.h
new file mode 100644
index 0000000..57d109a
--- /dev/null
+++ b/ccan/maskn/maskn.h
@@ -0,0 +1,30 @@
+#ifndef CCAN_MASKN_H_
+#define CCAN_MASKN_H_
+/* LGPLv3 or later - see LICENSE file for details */
+#include "config.h"
+#include <ccan/compiler/compiler.h>
+#include <ccan/bitops/bitops.h>
+#include <stdint.h>
+#include <stdbool.h>
+
+unsigned maskn_from_range_low(uint32_t base, uint32_t max) CONST_FUNCTION;
+unsigned maskn_from_range_high(uint32_t base, uint32_t min) CONST_FUNCTION;
+unsigned maskn_from_range(uint32_t base, uint32_t limit) CONST_FUNCTION;
+
+static inline bool maskn_matches(uint32_t base, unsigned mask_bits, uint32_t v)
+{
+ uint32_t m = ~bit_mask(mask_bits);
+ return (v & m) == (base & m);
+}
+
+static inline uint32_t maskn_max(uint32_t base, unsigned mask_bits)
+{
+ return base | bit_mask(mask_bits);
+}
+
+static inline uint32_t maskn_base(uint32_t base, unsigned mask_bits)
+{
+ return base & ~bit_mask(mask_bits);
+}
+
+#endif
diff --git a/ccan/maskn/test/run.c b/ccan/maskn/test/run.c
new file mode 100644
index 0000000..dd4f2ad
--- /dev/null
+++ b/ccan/maskn/test/run.c
@@ -0,0 +1,37 @@
+
+#include <ccan/maskn/maskn.c>
+#include <ccan/tap/tap.h>
+
+#define ok_eq(a, b) ok((a) == (b), "%s (%#jx) != %s (%#jx)", #a, (uintmax_t)(a), #b, (uintmax_t)(b))
+int main(void)
+{
+ plan_tests(17);
+
+ ok_eq(0, maskn_from_range_low(0xfff1, 0xfff1));
+
+#define MFRL(base, max) maskn_base(base, maskn_from_range_low(base, max)), maskn_from_range_low(base, max)
+ ok1( maskn_matches(MFRL(0xfff0, 0xfff1), 0xfff1));
+ ok1(!maskn_matches(MFRL(0xfff0, 0xfff1), 0xfff2));
+ ok1(!maskn_matches(MFRL(0xfff1, 0xfff1), 0xfff2));
+ ok1(!maskn_matches(MFRL(0xfff1, 0xfff1), 0xfff0));
+
+ ok_eq(4, maskn_from_range_low(0xffe0, 0xfff0));
+
+ ok_eq(5, maskn_from_range_low(0xffe0, 0xffff));
+ ok_eq(1, maskn_from_range_low(0xffe0, 0xffe1));
+
+ ok_eq(16, maskn_from_range_high(0xffff, 0));
+ ok_eq(15, maskn_from_range_high(0xffff, 1));
+ ok_eq(0, maskn_from_range_high(0xfffe, 1));
+
+ ok_eq(32, maskn_from_range_low(0, UINT32_MAX));
+
+ ok_eq(0, maskn_from_range(0, 0));
+ ok_eq(32, maskn_from_range(0, UINT32_MAX));
+ ok_eq(32, maskn_from_range(UINT32_MAX, 0));
+
+ ok_eq(0, maskn_from_range(UINT32_MAX & ~INT32_C(1), 0));
+ ok_eq(31, maskn_from_range(UINT32_MAX >> 1, 0));
+
+ return exit_status();
+}
--
2.0.1
More information about the ccan
mailing list