[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