[ccan] [PATCH v4 2/2] maskn & bitops: add new modules

Cody P Schafer dev at codyps.com
Fri Jul 18 12:30:30 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).

There is some overlap between ilog and bitops that would
be good to remove (fls).

Signed-off-by: Cody P Schafer <dev at codyps.com>
---
 Makefile-ccan          |  2 +
 ccan/bitops/LICENSE    |  1 +
 ccan/bitops/_info      | 30 +++++++++++++++
 ccan/bitops/bitops.c   |  8 ++++
 ccan/bitops/bitops.h   | 66 +++++++++++++++++++++++++++++++++
 ccan/bitops/builtin.h  | 30 +++++++++++++++
 ccan/bitops/internal.h | 99 ++++++++++++++++++++++++++++++++++++++++++++++++++
 ccan/bitops/test/run.c | 35 ++++++++++++++++++
 ccan/maskn/LICENSE     |  1 +
 ccan/maskn/_info       | 44 ++++++++++++++++++++++
 ccan/maskn/maskn.c     | 36 ++++++++++++++++++
 ccan/maskn/maskn.h     | 70 +++++++++++++++++++++++++++++++++++
 ccan/maskn/test/run.c  | 37 +++++++++++++++++++
 13 files changed, 459 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/builtin.h
 create mode 100644 ccan/bitops/internal.h
 create mode 100644 ccan/bitops/test/run.c
 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..8a8c706
--- /dev/null
+++ b/ccan/bitops/_info
@@ -0,0 +1,30 @@
+#include "config.h"
+#include <string.h>
+#include <stdio.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..8709b30
--- /dev/null
+++ b/ccan/bitops/bitops.c
@@ -0,0 +1,8 @@
+/* CC0 (Public Domain) - see LICENSE file for details */
+#include <ccan/bitops/bitops.h>
+
+extern inline uintmax_t bit_mask(unsigned bits);
+extern inline unsigned clz_32(uint32_t v);
+extern inline unsigned ctz_32(uint32_t v);
+extern inline unsigned fls_32(uint32_t v);
+extern inline unsigned fls_r1_32(uint32_t v);
diff --git a/ccan/bitops/bitops.h b/ccan/bitops/bitops.h
new file mode 100644
index 0000000..05de0f4
--- /dev/null
+++ b/ccan/bitops/bitops.h
@@ -0,0 +1,66 @@
+/* CC0 (Public Domain) - see LICENSE file for details */
+#ifndef CCAN_BITOPS_H_
+#define CCAN_BITOPS_H_
+
+#include "config.h"
+#include <ccan/compiler/compiler.h>
+#include <stdint.h>
+
+/**
+ * bit_mask - given a number of bits, returns a right (LSB) justified bit mask
+ *            with that many bits set
+ *
+ * Note that the number of bits must be less than or equal to CHAR_BIT *
+ * sizeof(uintmax_t), ie: the number of bits in a uintmax_t.
+ */
+CONST_FUNCTION
+inline uintmax_t bit_mask(unsigned bits);
+
+/**
+ * ctz_32 - count trailing zeros
+ *
+ * Returns the number of 'trailing' zeros in v, counting from the least
+ * significant bit until the first set (non-zero, one) bit.
+ *
+ * If no bits are set, returns 32
+ */
+CONST_FUNCTION
+inline unsigned ctz_32(uint32_t v);
+
+/**
+ * clz_32 - count leading zeros
+ *
+ * Returns the number of 'leading' zeros in v, counting from the most
+ * significant bit until the first set (non-zero, one) bit.
+ *
+ * If no bits are set, returns 32 (CHAR_BIT * sizeof(uint32_t))
+ */
+CONST_FUNCTION
+inline unsigned clz_32(uint32_t v);
+
+/**
+ * fls_32 - find last set
+ *
+ * Returns the bit index of the last set bit (last when scanning from LSB to
+ * MSB), where 1 is the least significant bit and 32 is the most significant
+ * bit. If no bits are set, returns 0.
+ */
+CONST_FUNCTION
+inline unsigned fls_32(uint32_t v);
+
+/**
+ * fls_r1_32 - find last set bit index, with the bit indexes renumbered
+ *
+ * This is the same as fls but rotates the output by 1.
+ *
+ * Bit indexes are named as follows: LSB = 0, MSB = 31
+ * If no bits being set, returns 32
+ *
+ * This amounts to (fls_32(v) - 1) % 33
+ */
+CONST_FUNCTION
+inline unsigned fls_r1_32(uint32_t v);
+
+#include <ccan/bitops/internal.h>
+
+#endif /* CCAN_BITOPS_H_ */
diff --git a/ccan/bitops/builtin.h b/ccan/bitops/builtin.h
new file mode 100644
index 0000000..ee68326
--- /dev/null
+++ b/ccan/bitops/builtin.h
@@ -0,0 +1,30 @@
+/* CC0 (Public Domain) - see LICENSE file for details */
+#ifndef CCAN_BITOPS_BUILTIN_H_
+#define CCAN_BITOPS_BUILTIN_H_
+
+/* FIXME: right now we assume sizeof(unsigned) == sizeof(uint32_t) */
+
+#if HAVE_BUILTIN_CLZ
+# define builtin_clz_32(v) (v ? __builtin_clz(v) : 32)
+#endif
+
+#if HAVE_BUILTIN_CTZ
+# define builtin_ctz_32(v) (v ? __builtin_ctz(v) : 32)
+#endif
+
+#if HAVE_ICCARM_INTRINSICS
+# include <intrinsics.h>
+/* emits the ARM instruction, which returns 32 if no bits are set */
+# define builtin_clz_32(v) __CLZ(v)
+# define builtin_reverse_32(v) __RBIT(v)
+#endif
+
+#ifndef builtin_ctz_32
+# ifdef builtin_reverse_32
+#  ifdef builtin_clz_32
+#   define builtin_ctz_32(v) builtin_clz_32(builtin_reverse_32(v))
+#  endif
+# endif
+#endif
+
+#endif
diff --git a/ccan/bitops/internal.h b/ccan/bitops/internal.h
new file mode 100644
index 0000000..df49cf6
--- /dev/null
+++ b/ccan/bitops/internal.h
@@ -0,0 +1,99 @@
+/* CC0 (Public Domain) - see LICENSE file for details */
+#ifndef CCAN_BITOPS_INTERNAL_H_
+#define CCAN_BITOPS_INTERNAL_H_
+
+#include "config.h"
+#include <stdint.h>
+#include <limits.h>
+#include <ccan/bitops/builtin.h>
+#include <ccan/compiler/compiler.h>
+
+CONST_FUNCTION
+inline uintmax_t bit_mask(unsigned bits)
+{
+        if (bits >= CHAR_BIT * sizeof(uintmax_t))
+                return UINTMAX_C(-1);
+        else
+                return ~(UINTMAX_MAX << bits);
+}
+
+CONST_FUNCTION
+inline unsigned ctz_32(uint32_t v)
+{
+#ifdef builtin_ctz_32
+	return builtin_ctz_32(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
+}
+
+CONST_FUNCTION
+inline unsigned clz_32(uint32_t v)
+{
+#ifdef builtin_clz_32
+	return builtin_clz_32(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
+}
+
+CONST_FUNCTION
+inline unsigned fls_32(uint32_t v)
+{
+	return ((CHAR_BIT * sizeof(v)) - clz_32(v));
+}
+
+CONST_FUNCTION
+inline unsigned fls_r1_32(uint32_t v)
+{
+	if (!v)
+		return 32;
+	return fls_32(v) - 1;
+}
+
+#endif
diff --git a/ccan/bitops/test/run.c b/ccan/bitops/test/run.c
new file mode 100644
index 0000000..5c95946
--- /dev/null
+++ b/ccan/bitops/test/run.c
@@ -0,0 +1,35 @@
+
+#include <ccan/bitops/bitops.h>
+#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(19);
+
+	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(bit_mask(UINT_MAX), UINTMAX_MAX);
+	ok_eq(bit_mask(UINT_MAX-1), UINTMAX_MAX);
+
+	ok_eq(fls_r1_32(0), 32);
+	ok_eq(fls_r1_32(1), 0);
+	ok_eq(fls_r1_32(UINT32_MAX), 31);
+	ok_eq(fls_r1_32(UINT32_MAX >> 1), 30);
+
+	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..ee3da8d
--- /dev/null
+++ b/ccan/maskn/_info
@@ -0,0 +1,44 @@
+#include "config.h"
+#include <string.h>
+#include <stdio.h>
+
+/**
+ * maskn - generate masks of N bits for a given range
+ *
+ * This module generates masks of N bits, as opposed to arbitrary masks where
+ * any bits can be 0 or * 1. In this module, only the trailing bits are 0, all
+ * others are 1.
+ *
+ * This mask generation is useful in interfacing with hardware that only
+ * provides limited matching capabilities. An example is the cortex-m3 DWT
+ * hardware module, which can be given a comparison value and a number of bits
+ * to mask off the lower bits of anything compared against it.
+ *
+ * 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..1ec5234
--- /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_r1_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_r1_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..da0e2f3
--- /dev/null
+++ b/ccan/maskn/maskn.h
@@ -0,0 +1,70 @@
+#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>
+
+/**
+ * maskn_from_range_low - mask bits given a lower base than limit
+ *
+ * @base: the start of a range [@base, @max]
+ * @max: the end of a range [@base, @max]
+ *
+ * Returns the number of mask bits suitable to form a mask contained within
+ * [@base, at max]. Specifically, always includes @base, attempts to select a mask
+ * that includes as much of (@base, at max] as possible. Never includes any of
+ * (@max,infinity).
+ */
+unsigned maskn_from_range_low(uint32_t base, uint32_t max) CONST_FUNCTION;
+
+/**
+ * maskn_from_range_high - mask bits given a higher base than limit.
+ *
+ * @base: the end of a range [@min, at base]
+ * @min: the start of a range [@min, @base]
+ *
+ * Returns the number of mask bits suitable to form a mask contained within
+ * [@max, at base]. Specifically, always includes @base, attempts to select a mask
+ * that includes as much of [@min, at base) as possible. Never includes any of
+ * (infinity, at min).
+ */
+unsigned maskn_from_range_high(uint32_t base, uint32_t min) CONST_FUNCTION;
+
+/**
+ * maskn_from_range - generalization of maskn_from_range_{high,low}
+ *
+ * Calls the apropriate maskn_from_range_{high,low} given the value of the parameters.
+ */
+unsigned maskn_from_range(uint32_t base, uint32_t limit) CONST_FUNCTION;
+
+/**
+ * maskn_matches - given a base and mask bits (as returned by
+ *                 maskn_from_range*()), determine whether the given value @v
+ *                 matches.
+ */
+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);
+}
+
+/**
+ * maskn_max - return the maximum value the base & mask_bits pair will match.
+ */
+static inline uint32_t maskn_max(uint32_t base, unsigned mask_bits)
+{
+	return base | bit_mask(mask_bits);
+}
+
+/**
+ * maskn_min - return the minimum value the base & mask_bits pair will match.
+ */
+static inline uint32_t maskn_min(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..8f6c781
--- /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_min(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