Merge "master" into "ovn".

[cascardo/ovs.git] / lib / util.c

diff --git a/lib/util.c b/lib/util.c
index a7e0279..f06dee5 100644 (file)
--- a/lib/util.c
+++ b/lib/util.c
@@ -1354,9 +1354,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
@@ -1367,21 +1367,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, unsigned 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.
@@ -1431,6 +1458,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 'src', 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 'dst', which is 'len' bytes long, to 0.
+ *
+ * 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_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 'dst', 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 'dst', 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 'dst', 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);
+}
 \f
 /* ovs_scan */