[ovs-dev] [PATCH ovn v3 2/5] util: Add more bitwise operations.

[Russell Bryant]

On 04/01/2015 12:52 AM, Ben Pfaff wrote:
> To be used in upcoming commits.
> 
> Signed-off-by: Ben Pfaff <blp at nicira.com>

I left a couple of comments, but they're not critical, so:

Acked-by: Russell Bryant <rbryant at redhat.com>

> ---
>  lib/util.c | 139 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
>  lib/util.h |   8 +++-
>  2 files changed, 139 insertions(+), 8 deletions(-)
> 
> diff --git a/lib/util.c b/lib/util.c
> index bcf7700..3293ca4 100644
> --- a/lib/util.c
> +++ b/lib/util.c
> @@ -1284,9 +1284,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
> @@ -1297,21 +1297,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, int len, bool target, int start, int end)
> +{

Should len by unsigned like len in the rest of the functions added?

Also, is there a reason not to use size_t for all of them instead?

> +    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.
> @@ -1361,6 +1388,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 'ofs', which is 'len'
> + * bytes long.

Did you mean 'ofs' in 'src' here?  The same "'ofs' in 'ofs'" exists in
other comments, as well.

-- 
Russell Bryant