Sounds good, thanks.
Ethan
On Fri, Apr 13, 2012 at 21:15, Ben Pfaff <b...@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 <b...@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 <b...@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
>
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
