[ovs-dev] [PATCH ovn 3/5] util: Add more bitwise operations.
Ben Pfaff
blp at nicira.com
Tue Mar 31 03:57:21 UTC 2015
To be used in upcoming commits.
Signed-off-by: Ben Pfaff <blp at nicira.com>
---
lib/util.c | 139 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
lib/util.h | 8 +++-
2 files changed, 139 insertions(+), 8 deletions(-)
diff --git a/lib/util.c b/lib/util.c
index bcf7700..3293ca4 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -1284,9 +1284,9 @@ bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs,
return true;
}
-/* Scans the bits in 'p' that have bit offsets 'start' through 'end'
- * (inclusive) for the first bit with value 'target'. If one is found, returns
- * its offset, otherwise 'end'. 'p' is 'len' bytes long.
+/* Scans the bits in 'p' that have bit offsets 'start' (inclusive) through
+ * 'end' (exclusive) for the first bit with value 'target'. If one is found,
+ * returns its offset, otherwise 'end'. 'p' is 'len' bytes long.
*
* If you consider all of 'p' to be a single unsigned integer in network byte
* order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
@@ -1297,21 +1297,48 @@ bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs,
* start <= end
*/
unsigned int
-bitwise_scan(const void *p_, unsigned int len, bool target, unsigned int start,
+bitwise_scan(const void *p, unsigned int len, bool target, unsigned int start,
unsigned int end)
{
- const uint8_t *p = p_;
unsigned int ofs;
for (ofs = start; ofs < end; ofs++) {
- bool bit = (p[len - (ofs / 8 + 1)] & (1u << (ofs % 8))) != 0;
- if (bit == target) {
+ if (bitwise_get_bit(p, len, ofs) == target) {
break;
}
}
return ofs;
}
+/* Scans the bits in 'p' that have bit offsets 'start' (inclusive) through
+ * 'end' (exclusive) for the first bit with value 'target', in reverse order.
+ * If one is found, returns its offset, otherwise 'end'. 'p' is 'len' bytes
+ * long.
+ *
+ * If you consider all of 'p' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in p[len - 1], bit 1 is the bit with value 2, bit 2 is the bit
+ * with value 4, ..., bit 8 is the bit with value 1 in p[len - 2], and so on.
+ *
+ * To scan an entire bit array in reverse order, specify start == len * 8 - 1
+ * and end == -1, in which case the return value is nonnegative if successful
+ * and -1 if no 'target' match is found.
+ *
+ * Required invariant:
+ * start >= end
+ */
+int
+bitwise_rscan(const void *p, int len, bool target, int start, int end)
+{
+ int ofs;
+
+ for (ofs = start; ofs > end; ofs--) {
+ if (bitwise_get_bit(p, len, ofs) == target) {
+ break;
+ }
+ }
+ return ofs;
+}
/* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits
* starting at bit 'dst_ofs' in 'dst', which is 'dst_len' bytes long.
@@ -1361,6 +1388,104 @@ bitwise_get(const void *src, unsigned int src_len,
n_bits);
return ntohll(value);
}
+
+/* Returns the value of the bit with offset 'ofs' in 'ofs', which is 'len'
+ * bytes long.
+ *
+ * If you consider all of 'src' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in src[len - 1], bit 1 is the bit with value 2, bit 2 is the
+ * bit with value 4, ..., bit 8 is the bit with value 1 in src[len - 2], and so
+ * on.
+ *
+ * Required invariants:
+ * ofs < len * 8
+ */
+bool
+bitwise_get_bit(const void *src_, unsigned int len, unsigned int ofs)
+{
+ const uint8_t *src = src_;
+
+ return (src[len - (ofs / 8 + 1)] & (1u << (ofs % 8))) != 0;
+}
+
+/* Sets the bit with offset 'ofs' in 'ofs', which is 'len' bytes long, to 0.
+ *
+ * If you consider all of 'src' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in src[len - 1], bit 1 is the bit with value 2, bit 2 is the
+ * bit with value 4, ..., bit 8 is the bit with value 1 in src[len - 2], and so
+ * on.
+ *
+ * Required invariants:
+ * ofs < len * 8
+ */
+void
+bitwise_put0(void *dst_, unsigned int len, unsigned int ofs)
+{
+ uint8_t *dst = dst_;
+
+ dst[len - (ofs / 8 + 1)] &= ~(1u << (ofs % 8));
+}
+
+/* Sets the bit with offset 'ofs' in 'ofs', which is 'len' bytes long, to 1.
+ *
+ * If you consider all of 'dst' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in dst[len - 1], bit 1 is the bit with value 2, bit 2 is the
+ * bit with value 4, ..., bit 8 is the bit with value 1 in dst[len - 2], and so
+ * on.
+ *
+ * Required invariants:
+ * ofs < len * 8
+ */
+void
+bitwise_put1(void *dst_, unsigned int len, unsigned int ofs)
+{
+ uint8_t *dst = dst_;
+
+ dst[len - (ofs / 8 + 1)] |= 1u << (ofs % 8);
+}
+
+/* Sets the bit with offset 'ofs' in 'ofs', which is 'len' bytes long, to 'b'.
+ *
+ * If you consider all of 'dst' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in dst[len - 1], bit 1 is the bit with value 2, bit 2 is the
+ * bit with value 4, ..., bit 8 is the bit with value 1 in dst[len - 2], and so
+ * on.
+ *
+ * Required invariants:
+ * ofs < len * 8
+ */
+void
+bitwise_put_bit(void *dst, unsigned int len, unsigned int ofs, bool b)
+{
+ if (b) {
+ bitwise_put1(dst, len, ofs);
+ } else {
+ bitwise_put0(dst, len, ofs);
+ }
+}
+
+/* Flips the bit with offset 'ofs' in 'ofs', which is 'len' bytes long.
+ *
+ * If you consider all of 'dst' to be a single unsigned integer in network byte
+ * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit
+ * with value 1 in dst[len - 1], bit 1 is the bit with value 2, bit 2 is the
+ * bit with value 4, ..., bit 8 is the bit with value 1 in dst[len - 2], and so
+ * on.
+ *
+ * Required invariants:
+ * ofs < len * 8
+ */
+void
+bitwise_toggle_bit(void *dst_, unsigned int len, unsigned int ofs)
+{
+ uint8_t *dst = dst_;
+
+ dst[len - (ofs / 8 + 1)] ^= 1u << (ofs % 8);
+}
/* ovs_scan */
diff --git a/lib/util.h b/lib/util.h
index 276edb5..e1470e0 100644
--- a/lib/util.h
+++ b/lib/util.h
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
+ * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -542,11 +542,17 @@ bool bitwise_is_all_zeros(const void *, unsigned int len, unsigned int ofs,
unsigned int n_bits);
unsigned int bitwise_scan(const void *, unsigned int len,
bool target, unsigned int start, unsigned int end);
+int bitwise_rscan(const void *, int len, bool target, int start, int end);
void bitwise_put(uint64_t value,
void *dst, unsigned int dst_len, unsigned int dst_ofs,
unsigned int n_bits);
uint64_t bitwise_get(const void *src, unsigned int src_len,
unsigned int src_ofs, unsigned int n_bits);
+bool bitwise_get_bit(const void *src, unsigned int len, unsigned int ofs);
+void bitwise_put0(void *dst, unsigned int len, unsigned int ofs);
+void bitwise_put1(void *dst, unsigned int len, unsigned int ofs);
+void bitwise_put_bit(void *dst, unsigned int len, unsigned int ofs, bool);
+void bitwise_toggle_bit(void *dst, unsigned int len, unsigned int ofs);
void xsleep(unsigned int seconds);
--
2.1.3
More information about the dev
mailing list