util: New function bitwise_one().
authorBen Pfaff <blp@nicira.com>
Wed, 11 Apr 2012 19:07:51 +0000 (12:07 -0700)
committerBen Pfaff <blp@nicira.com>
Sat, 14 Apr 2012 03:43:37 +0000 (20:43 -0700)
It's the obvious counterpart to bitwise_zero().

Signed-off-by: Ben Pfaff <blp@nicira.com>
lib/util.c
lib/util.h
tests/library.at
tests/test-util.c

index 810d766dc7fbe0be9d93e2d2539f1e5b7e0467d3..14a97f24abf8e26224a4822cb1f332c800f5813c 100644 (file)
@@ -865,6 +865,54 @@ bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs,
     }
 }
 
+/* Sets to 1 all of the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.
+ * '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
+ */
+void
+bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
+            unsigned int n_bits)
+{
+    uint8_t *dst = dst_;
+
+    if (!n_bits) {
+        return;
+    }
+
+    dst += dst_len - (dst_ofs / 8 + 1);
+    dst_ofs %= 8;
+
+    if (dst_ofs) {
+        unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
+
+        *dst |= ((1 << chunk) - 1) << dst_ofs;
+
+        n_bits -= chunk;
+        if (!n_bits) {
+            return;
+        }
+
+        dst--;
+    }
+
+    while (n_bits >= 8) {
+        *dst-- = 0xff;
+        n_bits -= 8;
+    }
+
+    if (n_bits) {
+        *dst |= (1 << n_bits) - 1;
+    }
+}
+
 /* 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.
  *
index bdad501782b5c1db76c1f9e95a4dd09d2896c210..63f4a240a61b77c7ab705a11fe9e1fd10efbb62c 100644 (file)
@@ -228,6 +228,8 @@ void bitwise_copy(const void *src, unsigned int src_len, unsigned int src_ofs,
                   unsigned int n_bits);
 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);
 void bitwise_put(uint64_t value,
                  void *dst, unsigned int dst_len, unsigned int dst_ofs,
                  unsigned int n_bits);
index ca5f29ca8f16b9c3cec7ef9471fd45fd66f23a02..dce69dea07f29de056f5af84864065eb0f54637a 100644 (file)
@@ -100,7 +100,8 @@ nibble   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 ])
 AT_CLEANUP
 
-AT_SETUP([test log_2_floor])
+AT_SETUP([test utility functions])
+AT_KEYWORDS([util])
 AT_CHECK([test-util])
 AT_CLEANUP
 
index 82d08610d8ef7da1ccf9a907a55918af4e657482..ed98295bb1ae80bf6589196e88791830f3b53aa9 100644 (file)
@@ -143,6 +143,47 @@ check_bitwise_zero(void)
     }
 }
 
+static void
+check_bitwise_one(void)
+{
+    unsigned int n_loops;
+    int dst_ofs;
+    int n_bits;
+
+    n_loops = 0;
+    for (n_bits = 0; n_bits <= 64; n_bits++) {
+        for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
+            ovs_be64 dst = htonll(random_uint64());
+            ovs_be64 orig_dst = dst;
+            ovs_be64 expect;
+
+            if (n_bits == 64) {
+                expect = htonll(UINT64_MAX);
+            } else {
+                uint64_t mask = (UINT64_C(1) << n_bits) - 1;
+                expect = orig_dst | htonll(mask << dst_ofs);
+            }
+
+            bitwise_one(&dst, sizeof dst, dst_ofs, n_bits);
+            if (expect != dst) {
+                fprintf(stderr,"bitwise_one(0x%016"PRIx64",8,%d, %d) "
+                        "yielded 0x%016"PRIx64" "
+                        "instead of the expected 0x%016"PRIx64"\n",
+                        ntohll(orig_dst), dst_ofs,
+                        n_bits,
+                        ntohll(dst), ntohll(expect));
+                abort();
+            }
+
+            n_loops++;
+        }
+    }
+
+    if (n_loops != 64 * (64 + 1) / 2) {
+        abort();
+    }
+}
+
 int
 main(void)
 {
@@ -170,5 +211,7 @@ main(void)
 
     check_bitwise_zero();
 
+    check_bitwise_one();
+
     return 0;
 }