[ovs-dev] [prelearning 1/5] packets: Add more utility functions for IPv4 and IPv6 addresses.
Ben Pfaff
blp at nicira.com
Wed Aug 17 17:59:19 UTC 2011
On Tue, Aug 16, 2011 at 05:41:46PM -0700, Ethan Jackson wrote:
> I would be inclined to implement a "clz" function similar to what
> log_2_floor() does in util. We could use it both for log_2_floor()
> and ip_count_cidr_bits(). That way we would only have to deal with
> the ugly GNUC ifdefing in one place.
It's a good idea, but ip_count_cidr_bits() actually wants ctz(), not
clz().
Here's a revised version.
--8<--------------------------cut here-------------------------->8--
From: Ben Pfaff <blp at nicira.com>
Date: Wed, 17 Aug 2011 10:55:15 -0700
Subject: [PATCH] packets: Add more utility functions for IPv4 and IPv6
addresses.
We had these functions scattered around the source tree anyway. packets.h
is a good place to centralize them.
I do plan to introduce some additional callers.
---
lib/classifier.c | 22 ++------------------
lib/ofp-util.c | 16 ++------------
lib/packets.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++-----
lib/packets.h | 4 +++
lib/util.c | 33 +++++++++++++++++++++++++++++++
lib/util.h | 3 +-
tests/test-util.c | 31 ++++++++++++++++++++++++-----
7 files changed, 119 insertions(+), 45 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index d1f9d5d..9c71b85 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -421,15 +421,8 @@ format_ip_netmask(struct ds *s, const char *name, ovs_be32 ip,
ovs_be32 netmask)
{
if (netmask) {
- ds_put_format(s, "%s="IP_FMT, name, IP_ARGS(&ip));
- if (netmask != htonl(UINT32_MAX)) {
- if (ip_is_cidr(netmask)) {
- int wcbits = ofputil_netmask_to_wcbits(netmask);
- ds_put_format(s, "/%d", 32 - wcbits);
- } else {
- ds_put_format(s, "/"IP_FMT, IP_ARGS(&netmask));
- }
- }
+ ds_put_format(s, "%s=", name);
+ ip_format_masked(ip, netmask, s);
ds_put_char(s, ',');
}
}
@@ -441,16 +434,7 @@ format_ipv6_netmask(struct ds *s, const char *name,
{
if (!ipv6_mask_is_any(netmask)) {
ds_put_format(s, "%s=", name);
- print_ipv6_addr(s, addr);
- if (!ipv6_mask_is_exact(netmask)) {
- if (ipv6_is_cidr(netmask)) {
- int cidr_bits = ipv6_count_cidr_bits(netmask);
- ds_put_format(s, "/%d", cidr_bits);
- } else {
- ds_put_char(s, '/');
- print_ipv6_addr(s, netmask);
- }
- }
+ print_ipv6_masked(s, addr, netmask);
ds_put_char(s, ',');
}
}
diff --git a/lib/ofp-util.c b/lib/ofp-util.c
index b0e7405..cdb12e6 100644
--- a/lib/ofp-util.c
+++ b/lib/ofp-util.c
@@ -59,22 +59,12 @@ ofputil_wcbits_to_netmask(int wcbits)
}
/* Given the IP netmask 'netmask', returns the number of bits of the IP address
- * that it wildcards. 'netmask' must be a CIDR netmask (see ip_is_cidr()). */
+ * that it wildcards, that is, the number of 0-bits in 'netmask'. 'netmask'
+ * must be a CIDR netmask (see ip_is_cidr()). */
int
ofputil_netmask_to_wcbits(ovs_be32 netmask)
{
- assert(ip_is_cidr(netmask));
-#if __GNUC__ >= 4
- return netmask == htonl(0) ? 32 : __builtin_ctz(ntohl(netmask));
-#else
- int wcbits;
-
- for (wcbits = 32; netmask; wcbits--) {
- netmask &= netmask - 1;
- }
-
- return wcbits;
-#endif
+ return 32 - ip_count_cidr_bits(netmask);
}
/* A list of the FWW_* and OFPFW_ bits that have the same value, meaning, and
diff --git a/lib/packets.c b/lib/packets.c
index e05e3eb..881ef45 100644
--- a/lib/packets.c
+++ b/lib/packets.c
@@ -105,6 +105,30 @@ eth_set_vlan_tci(struct ofpbuf *packet, ovs_be16 tci)
packet->l2 = packet->data;
}
+/* Given the IP netmask 'netmask', returns the number of bits of the IP address
+ * that it specifies, that is, the number of 1-bits in 'netmask'. 'netmask'
+ * must be a CIDR netmask (see ip_is_cidr()). */
+int
+ip_count_cidr_bits(ovs_be32 netmask)
+{
+ assert(ip_is_cidr(netmask));
+ return 32 - ctz(ntohl(netmask));
+}
+
+void
+ip_format_masked(ovs_be32 ip, ovs_be32 mask, struct ds *s)
+{
+ ds_put_format(s, IP_FMT, IP_ARGS(&ip));
+ if (mask != htonl(UINT32_MAX)) {
+ if (ip_is_cidr(mask)) {
+ ds_put_format(s, "/%d", ip_count_cidr_bits(mask));
+ } else {
+ ds_put_format(s, "/"IP_FMT, IP_ARGS(&mask));
+ }
+ }
+}
+
+
/* Stores the string representation of the IPv6 address 'addr' into the
* character array 'addr_str', which must be at least INET6_ADDRSTRLEN
* bytes long. */
@@ -117,10 +141,29 @@ format_ipv6_addr(char *addr_str, const struct in6_addr *addr)
void
print_ipv6_addr(struct ds *string, const struct in6_addr *addr)
{
- char addr_str[INET6_ADDRSTRLEN];
+ char *dst;
+
+ ds_reserve(string, string->length + INET6_ADDRSTRLEN);
+
+ dst = string->string + string->length;
+ format_ipv6_addr(dst, addr);
+ string->length += strlen(dst);
+}
- format_ipv6_addr(addr_str, addr);
- ds_put_format(string, "%s", addr_str);
+void
+print_ipv6_masked(struct ds *s, const struct in6_addr *addr,
+ const struct in6_addr *mask)
+{
+ print_ipv6_addr(s, addr);
+ if (mask && !ipv6_mask_is_exact(mask)) {
+ if (ipv6_is_cidr(mask)) {
+ int cidr_bits = ipv6_count_cidr_bits(mask);
+ ds_put_format(s, "/%d", cidr_bits);
+ } else {
+ ds_put_char(s, '/');
+ print_ipv6_addr(s, mask);
+ }
+ }
}
struct in6_addr ipv6_addr_bitand(const struct in6_addr *a,
@@ -164,9 +207,9 @@ ipv6_create_mask(int mask)
return netmask;
}
-/* Given the IPv6 netmask 'netmask', returns the number of bits of the
- * IPv6 address that it wildcards. 'netmask' must be a CIDR netmask (see
- * ipv6_is_cidr()). */
+/* Given the IPv6 netmask 'netmask', returns the number of bits of the IPv6
+ * address that it specifies, that is, the number of 1-bits in 'netmask'.
+ * 'netmask' must be a CIDR netmask (see ipv6_is_cidr()). */
int
ipv6_count_cidr_bits(const struct in6_addr *netmask)
{
diff --git a/lib/packets.h b/lib/packets.h
index a389e6a..304cd9d 100644
--- a/lib/packets.h
+++ b/lib/packets.h
@@ -291,6 +291,8 @@ ip_is_cidr(ovs_be32 netmask)
uint32_t x = ~ntohl(netmask);
return !(x & (x + 1));
}
+int ip_count_cidr_bits(ovs_be32 netmask);
+void ip_format_masked(ovs_be32 ip, ovs_be32 mask, struct ds *);
#define IP_VER(ip_ihl_ver) ((ip_ihl_ver) >> 4)
#define IP_IHL(ip_ihl_ver) ((ip_ihl_ver) & 15)
@@ -423,6 +425,8 @@ static inline bool ipv6_mask_is_exact(const struct in6_addr *mask) {
void format_ipv6_addr(char *addr_str, const struct in6_addr *addr);
void print_ipv6_addr(struct ds *string, const struct in6_addr *addr);
+void print_ipv6_masked(struct ds *string, const struct in6_addr *addr,
+ const struct in6_addr *mask);
struct in6_addr ipv6_addr_bitand(const struct in6_addr *src,
const struct in6_addr *mask);
struct in6_addr ipv6_create_mask(int mask);
diff --git a/lib/util.c b/lib/util.c
index e6d57da..5e90ecb 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -663,3 +663,36 @@ log_2_floor(uint32_t n)
}
#endif
}
+
+/* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
+int
+ctz(uint32_t n)
+{
+ if (!n) {
+ return 32;
+ } else {
+#if !defined(UINT_MAX) || !defined(UINT32_MAX)
+#error "Someone screwed up the #includes."
+#elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
+ return __builtin_ctz(n);
+#else
+ unsigned int k;
+ int count = 31;
+
+#define CTZ_STEP(X) \
+ k = n << (X); \
+ if (k) { \
+ count -= X; \
+ n = k; \
+ }
+ CTZ_STEP(16);
+ CTZ_STEP(8);
+ CTZ_STEP(4);
+ CTZ_STEP(2);
+ CTZ_STEP(1);
+#undef CTZ_STEP
+
+ return count;
+#endif
+ }
+}
diff --git a/lib/util.h b/lib/util.h
index 1649c59..5c8618d 100644
--- a/lib/util.h
+++ b/lib/util.h
@@ -194,7 +194,8 @@ char *base_name(const char *file_name);
char *abs_file_name(const char *dir, const char *file_name);
void ignore(bool x OVS_UNUSED);
-int log_2_floor(uint32_t n);
+int log_2_floor(uint32_t);
+int ctz(uint32_t);
#ifdef __cplusplus
}
diff --git a/tests/test-util.c b/tests/test-util.c
index e9a827a..bc4af23 100644
--- a/tests/test-util.c
+++ b/tests/test-util.c
@@ -17,6 +17,7 @@
#include <config.h>
#include <inttypes.h>
+#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
@@ -24,7 +25,7 @@
#include "util.h"
static void
-check(uint32_t x, int n)
+check_log_2_floor(uint32_t x, int n)
{
if (log_2_floor(x) != n) {
fprintf(stderr, "log_2_floor(%"PRIu32") is %d but should be %d\n",
@@ -33,20 +34,38 @@ check(uint32_t x, int n)
}
}
+static void
+check_ctz(uint32_t x, int n)
+{
+ if (ctz(x) != n) {
+ fprintf(stderr, "ctz(%"PRIu32") is %d but should be %d\n",
+ x, ctz(x), n);
+ abort();
+ }
+}
+
int
main(void)
{
int n;
for (n = 0; n < 32; n++) {
- /* Check minimum x that has log2(x) == n. */
- check(1 << n, n);
+ /* Check minimum x such that f(x) == n. */
+ check_log_2_floor(1 << n, n);
+ check_ctz(1 << n, n);
- /* Check maximum x that has log2(x) == n. */
- check((1 << n) | ((1 << n) - 1), n);
+ /* Check maximum x such that f(x) == n. */
+ check_log_2_floor((1 << n) | ((1 << n) - 1), n);
+ check_ctz(UINT32_MAX << n, n);
/* Check a random value in the middle. */
- check((random_uint32() & ((1 << n) - 1)) | (1 << n), n);
+ check_log_2_floor((random_uint32() & ((1 << n) - 1)) | (1 << n), n);
+ check_ctz((random_uint32() | 1) << n, n);
}
+
+ /* Check ctz(0).
+ * (log_2_floor(0) is undefined.) */
+ check_ctz(0, 32);
+
return 0;
}
--
1.7.4.4
More information about the dev
mailing list