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

[Ethan Jackson]

Sounds good, thanks.

Ethan

On Fri, Apr 13, 2012 at 21:15, Ben Pfaff <blp at nicira.com> wrote:
> 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
>