From ddc4f8e27f231b35df0c73a16bacc17396fb00f3 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Tue, 17 Jan 2012 16:38:23 -0800 Subject: [PATCH] util: Move bitwise_copy() here, add new bitwise functions, add a test. bitwise_copy() is generally useful so make it a general utility function. Also add a comment. Upcoming commits will introduce users for the new functions. Signed-off-by: Ben Pfaff --- lib/nx-match.c | 54 +-------------------- lib/random.c | 14 +++++- lib/random.h | 3 +- lib/util.c | 120 +++++++++++++++++++++++++++++++++++++++++++++- lib/util.h | 8 ++++ tests/test-util.c | 62 +++++++++++++++++++++++- 6 files changed, 204 insertions(+), 57 deletions(-) diff --git a/lib/nx-match.c b/lib/nx-match.c index 63e5e5bef..ef166c792 100644 --- a/lib/nx-match.c +++ b/lib/nx-match.c @@ -29,6 +29,7 @@ #include "openflow/nicira-ext.h" #include "packets.h" #include "unaligned.h" +#include "util.h" #include "vlog.h" VLOG_DEFINE_THIS_MODULE(nx_match); @@ -1044,59 +1045,6 @@ nxm_check_reg_load(const struct nx_action_reg_load *action, /* nxm_execute_reg_move(), nxm_execute_reg_load(). */ -static void -bitwise_copy(const void *src_, unsigned int src_len, unsigned int src_ofs, - void *dst_, unsigned int dst_len, unsigned int dst_ofs, - unsigned int n_bits) -{ - const uint8_t *src = src_; - uint8_t *dst = dst_; - - src += src_len - (src_ofs / 8 + 1); - src_ofs %= 8; - - dst += dst_len - (dst_ofs / 8 + 1); - dst_ofs %= 8; - - if (src_ofs == 0 && dst_ofs == 0) { - unsigned int n_bytes = n_bits / 8; - if (n_bytes) { - dst -= n_bytes - 1; - src -= n_bytes - 1; - memcpy(dst, src, n_bytes); - - n_bits %= 8; - src--; - dst--; - } - if (n_bits) { - uint8_t mask = (1 << n_bits) - 1; - *dst = (*dst & ~mask) | (*src & mask); - } - } else { - while (n_bits > 0) { - unsigned int max_copy = 8 - MAX(src_ofs, dst_ofs); - unsigned int chunk = MIN(n_bits, max_copy); - uint8_t mask = ((1 << chunk) - 1) << dst_ofs; - - *dst &= ~mask; - *dst |= ((*src >> src_ofs) << dst_ofs) & mask; - - src_ofs += chunk; - if (src_ofs == 8) { - src--; - src_ofs = 0; - } - dst_ofs += chunk; - if (dst_ofs == 8) { - dst--; - dst_ofs = 0; - } - n_bits -= chunk; - } - } -} - /* Returns the value of the NXM field corresponding to 'header' at 'ofs_nbits' * in 'flow'. */ uint64_t diff --git a/lib/random.c b/lib/random.c index a802bc743..911ebf304 100644 --- a/lib/random.c +++ b/lib/random.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009, 2010, 2011 Nicira Networks. + * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira Networks. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -100,6 +100,18 @@ random_uint32(void) return random_next(); } +uint64_t +random_uint64(void) +{ + uint64_t x; + + random_init(); + + x = random_next(); + x |= (uint64_t) random_next() << 32; + return x; +} + int random_range(int max) { diff --git a/lib/random.h b/lib/random.h index c69863859..5bb041e5e 100644 --- a/lib/random.h +++ b/lib/random.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009, 2010 Nicira Networks. + * Copyright (c) 2008, 2009, 2010, 2012 Nicira Networks. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -27,6 +27,7 @@ void random_bytes(void *, size_t); uint8_t random_uint8(void); uint16_t random_uint16(void); uint32_t random_uint32(void); +uint64_t random_uint64(void); int random_range(int max); #endif /* random.h */ diff --git a/lib/util.c b/lib/util.c index 8379c9ac5..811902afb 100644 --- a/lib/util.c +++ b/lib/util.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009, 2010, 2011 Nicira Networks. + * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira Networks. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -25,7 +25,9 @@ #include #include #include +#include "byte-order.h" #include "coverage.h" +#include "openvswitch/types.h" #include "vlog.h" VLOG_DEFINE_THIS_MODULE(util); @@ -733,3 +735,119 @@ is_all_ones(const uint8_t *p, size_t n) return true; } +/* Copies 'n_bits' bits starting from bit 'src_ofs' in 'src' to the 'n_bits' + * starting from bit 'dst_ofs' in 'dst'. 'src' is 'src_len' bytes long and + * 'dst' is 'dst_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[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[src_len - + * 2], and so on. Similarly for 'dst'. + * + * Required invariants: + * src_ofs + n_bits <= src_len * 8 + * dst_ofs + n_bits <= dst_len * 8 + * 'src' and 'dst' must not overlap. + */ +void +bitwise_copy(const void *src_, unsigned int src_len, unsigned int src_ofs, + void *dst_, unsigned int dst_len, unsigned int dst_ofs, + unsigned int n_bits) +{ + const uint8_t *src = src_; + uint8_t *dst = dst_; + + src += src_len - (src_ofs / 8 + 1); + src_ofs %= 8; + + dst += dst_len - (dst_ofs / 8 + 1); + dst_ofs %= 8; + + if (src_ofs == 0 && dst_ofs == 0) { + unsigned int n_bytes = n_bits / 8; + if (n_bytes) { + dst -= n_bytes - 1; + src -= n_bytes - 1; + memcpy(dst, src, n_bytes); + + n_bits %= 8; + src--; + dst--; + } + if (n_bits) { + uint8_t mask = (1 << n_bits) - 1; + *dst = (*dst & ~mask) | (*src & mask); + } + } else { + while (n_bits > 0) { + unsigned int max_copy = 8 - MAX(src_ofs, dst_ofs); + unsigned int chunk = MIN(n_bits, max_copy); + uint8_t mask = ((1 << chunk) - 1) << dst_ofs; + + *dst &= ~mask; + *dst |= ((*src >> src_ofs) << dst_ofs) & mask; + + src_ofs += chunk; + if (src_ofs == 8) { + src--; + src_ofs = 0; + } + dst_ofs += chunk; + if (dst_ofs == 8) { + dst--; + dst_ofs = 0; + } + n_bits -= chunk; + } + } +} + +/* 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. + * + * 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 invariants: + * dst_ofs + n_bits <= dst_len * 8 + * n_bits <= 64 + */ +void +bitwise_put(uint64_t value, + void *dst, unsigned int dst_len, unsigned int dst_ofs, + unsigned int n_bits) +{ + ovs_be64 n_value = htonll(value); + bitwise_copy(&n_value, sizeof n_value, 0, + dst, dst_len, dst_ofs, + n_bits); +} + +/* Returns the value of the 'n_bits' bits starting at bit 'src_ofs' in 'src', + * which is 'src_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[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[src_len - + * 2], and so on. + * + * Required invariants: + * src_ofs + n_bits <= src_len * 8 + * n_bits <= 64 + */ +uint64_t +bitwise_get(const void *src, unsigned int src_len, + unsigned int src_ofs, unsigned int n_bits) +{ + ovs_be64 value = htonll(0); + + bitwise_copy(src, src_len, src_ofs, + &value, sizeof value, 0, + n_bits); + return ntohll(value); +} diff --git a/lib/util.h b/lib/util.h index b2052f364..c8eb0046d 100644 --- a/lib/util.h +++ b/lib/util.h @@ -208,6 +208,14 @@ int ctz(uint32_t); bool is_all_zeros(const uint8_t *, size_t); bool is_all_ones(const uint8_t *, size_t); +void bitwise_copy(const void *src, unsigned int src_len, unsigned int src_ofs, + void *dst, unsigned int dst_len, unsigned int 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); +uint64_t bitwise_get(const void *src, unsigned int src_len, + unsigned int src_ofs, unsigned int n_bits); #ifdef __cplusplus } diff --git a/tests/test-util.c b/tests/test-util.c index bc4af2356..45ea8f29f 100644 --- a/tests/test-util.c +++ b/tests/test-util.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011 Nicira Networks. + * Copyright (c) 2011, 2012 Nicira Networks. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -21,6 +21,7 @@ #include #include +#include "byte-order.h" #include "random.h" #include "util.h" @@ -44,6 +45,63 @@ check_ctz(uint32_t x, int n) } } +/* Returns the sum of the squares of the first 'n' positive integers. */ +static unsigned int +sum_of_squares(int n) +{ + return n * (n + 1) * (2 * n + 1) / 6; +} + +static void +check_bitwise_copy(void) +{ + unsigned int n_loops; + int src_ofs; + int dst_ofs; + int n_bits; + + n_loops = 0; + for (n_bits = 0; n_bits <= 64; n_bits++) { + for (src_ofs = 0; src_ofs < 64 - n_bits; src_ofs++) { + for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) { + ovs_be64 src = htonll(random_uint64()); + ovs_be64 dst = htonll(random_uint64()); + ovs_be64 orig_dst = dst; + ovs_be64 expect; + + if (n_bits == 64) { + expect = dst; + } else { + uint64_t mask = (UINT64_C(1) << n_bits) - 1; + expect = orig_dst & ~htonll(mask << dst_ofs); + expect |= htonll(((ntohll(src) >> src_ofs) & mask) + << dst_ofs); + } + + bitwise_copy(&src, sizeof src, src_ofs, + &dst, sizeof dst, dst_ofs, + n_bits); + if (expect != dst) { + fprintf(stderr,"copy_bits(0x%016"PRIx64",8,%d, " + "0x%016"PRIx64",8,%d, %d) yielded 0x%016"PRIx64" " + "instead of the expected 0x%016"PRIx64"\n", + ntohll(src), src_ofs, + ntohll(orig_dst), dst_ofs, + n_bits, + ntohll(dst), ntohll(expect)); + abort(); + } + + n_loops++; + } + } + } + + if (n_loops != sum_of_squares(64)) { + abort(); + } +} + int main(void) { @@ -67,5 +125,7 @@ main(void) * (log_2_floor(0) is undefined.) */ check_ctz(0, 32); + check_bitwise_copy(); + return 0; } -- 2.43.0