[ovs-dev] [PATCH v2 02/12] util: New function bitwise_scan().

[Ben Pfaff]

This will acquire its first user in an upcoming commit.

This implementation is not optimized at all but it doesn't matter for the
purpose for which I intend to initially use it.

Signed-off-by: Ben Pfaff <blp at nicira.com>
Acked-by: YAMAMOTO Takashi <yamamoto at valinux.co.jp>
---
 lib/util.c |   29 +++++++++++++++++++++++++++++
 lib/util.h |    2 ++
 2 files changed, 31 insertions(+)

diff --git a/lib/util.c b/lib/util.c
index f3e47b1..01e8a0e 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -1273,6 +1273,35 @@ 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.
+ *
+ * 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.
+ *
+ * Required invariant:
+ *   start <= end
+ */
+unsigned int
+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) {
+            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.
  *
diff --git a/lib/util.h b/lib/util.h
index 7da7aa8..ea9bcfa 100644
--- a/lib/util.h
+++ b/lib/util.h
@@ -503,6 +503,8 @@ void bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
                  unsigned int n_bits);
 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);
 void bitwise_put(uint64_t value,
                  void *dst, unsigned int dst_len, unsigned int dst_ofs,
                  unsigned int n_bits);
-- 
1.7.10.4