[ovs-dev] [bug10576 5/5] learn: Make it possible to parse "load" actions wider than 64 bits.

[Ben Pfaff]

On Fri, Apr 13, 2012 at 06:06:47PM -0700, Ethan Jackson wrote:
> I would think that bitwise_is_all_zeros() belongs in it's own patch
> just line bitwise_one(), but I don't think it matters much.

I was lazy.

I broke this out as a new patch just after patch 1, and I added a test.
Good thing, too, because bitwise_is_all_zeros() was buggy.

Here's the new patch.  The incremental for the last patch should be
obvious (just don't add the new code).

--8<--------------------------cut here-------------------------->8--

From: Ben Pfaff <blp at nicira.com>
Date: Fri, 13 Apr 2012 21:12:37 -0700
Subject: [PATCH] util: New function bitwise_is_all_zeros().

Signed-off-by: Ben Pfaff <blp at nicira.com>
---
 lib/util.c        |   56 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/util.h        |    2 +
 tests/test-util.c |   47 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 105 insertions(+), 0 deletions(-)

diff --git a/lib/util.c b/lib/util.c
index 14a97f2..f9880f3 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -913,6 +913,62 @@ bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
     }
 }
 
+/* Scans the 'n_bits' bits starting from bit 'dst_ofs' in 'dst' for 1-bits.
+ * Returns false if any 1-bits are found, otherwise true.  'dst' is 'dst_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[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[dst_len -
+ * 2], and so on.
+ *
+ * Required invariant:
+ *   dst_ofs + n_bits <= dst_len * 8
+ */
+bool
+bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs,
+                     unsigned int n_bits)
+{
+    const uint8_t *p = p_;
+
+    if (!n_bits) {
+        return true;
+    }
+
+    p += len - (ofs / 8 + 1);
+    ofs %= 8;
+
+    if (ofs) {
+        unsigned int chunk = MIN(n_bits, 8 - ofs);
+
+        if (*p & (((1 << chunk) - 1) << ofs)) {
+            return false;
+        }
+
+        n_bits -= chunk;
+        if (!n_bits) {
+            return true;
+        }
+
+        p--;
+    }
+
+    while (n_bits >= 8) {
+        if (*p) {
+            return false;
+        }
+        n_bits -= 8;
+        p--;
+    }
+
+    if (n_bits && *p & ((1 << n_bits) - 1)) {
+        return false;
+    }
+
+    return true;
+}
+
 /* 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 63f4a24..e5d1c3a 100644
--- a/lib/util.h
+++ b/lib/util.h
@@ -230,6 +230,8 @@ void bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs,
                   unsigned int n_bits);
 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);
 void bitwise_put(uint64_t value,
                  void *dst, unsigned int dst_len, unsigned int dst_ofs,
                  unsigned int n_bits);
diff --git a/tests/test-util.c b/tests/test-util.c
index ed98295..23b86e8 100644
--- a/tests/test-util.c
+++ b/tests/test-util.c
@@ -184,6 +184,51 @@ check_bitwise_one(void)
     }
 }
 
+static void
+check_bitwise_is_all_zeros(void)
+{
+    int n_loops;
+
+    n_loops = 0;
+    for (n_loops = 0; n_loops < 100; n_loops++) {
+        ovs_be64 x = htonll(0);
+        int i;
+
+        for (i = 0; i < 64; i++) {
+            ovs_be64 bit;
+            int ofs, n;
+
+            /* Change a random 0-bit into a 1-bit. */
+            do {
+                bit = htonll(UINT64_C(1) << (random_uint32() % 64));
+            } while (x & bit);
+            x |= bit;
+
+            for (ofs = 0; ofs < 64; ofs++) {
+                for (n = 0; n <= 64 - ofs; n++) {
+                    bool expect;
+                    bool answer;
+
+                    expect = (n == 64
+                              ? x == 0
+                              : !(x & htonll(((UINT64_C(1) << n) - 1)
+                                             << ofs)));
+                    answer = bitwise_is_all_zeros(&x, sizeof x, ofs, n);
+                    if (expect != answer) {
+                        fprintf(stderr,
+                                "bitwise_is_all_zeros(0x%016"PRIx64",8,%d,%d "
+                                "returned %s instead of %s\n",
+                                ntohll(x), ofs, n,
+                                answer ? "true" : "false",
+                                expect ? "true" : "false");
+                        abort();
+                    }
+                }
+            }
+        }
+    }
+}
+
 int
 main(void)
 {
@@ -213,5 +258,7 @@ main(void)
 
     check_bitwise_one();
 
+    check_bitwise_is_all_zeros();
+
     return 0;
 }
-- 
1.7.2.5