Re: subnet calculations

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

On 7 Aug, 2013, at 02:50 , Emmanuel Dreyfus <manu%netbsd.org@localhost> wrote:
> Hi
> 
> What is the path of least resistance on NetBSD to determine if an
> address falls into a subnet given as net_address/cidr_mask.
> 
> IPv6 support would be a nice bonus. Standard function would be even
> better, but I doubt it exists.
> 
> I understand I can use strchr()  to cut the "/", then getaddrinfo() to
> store the mask in binary while taking IPv6 into account. Then I
> understand inet_net_pton() on the original mask could extract the number
> of bits in the mask, but then? 
> 
> For an IPv4 address, I guess I can turn the cidr mask into a binary
> address with thing like  ~((1 << 32-cidr) - 1) on an uint64_t, but for
> IPv6 it will be more subbtle. Similarly, doing bit-wise AND on IPv4
> address is just working on uint32_t, but it is more complex with IPv6.

I'm assuming that "CIDR mask" means an address prefix length.  When
doing this in a route lookup you can generally get a good result by
dealing with prefix lengths and using clz() (as in gcc's __builtin_clz()).
If the addresses are stored so that they can be accessed as an array of
uint32_t values (but, probably, in network byte order) you can use a
function roughly like

u_int
diff_bit (const uint32_t *ap0, const uint32_t *ap1, u_int plen)
{
        u_int i;
        uint32_t t;

        for (i = 0; i < plen; i += 32) {
                t = *ap0++ ^ *ap1++;
                if (t != 0) {
                        i += clz(ntohl(t));
                        break;
                }
        }

        return (i);
}

If the value returned is greater than or equal to the prefix length
they match, otherwise they don't.  If the addresses need to be treated
as byte arrays it still works but loops more times.  Tree-shaped route
lookups generally want the bit number back rather than a true-or-false
result since, if this prefix doesn't match, knowing the index of the
highest order bit which is different will unambiguously identify the
longest prefix which does match; only one prefix comparison needs to
be done no matter how many possible matches exist.

IP route tables which include multicast routes (and I think it is best
done if unicast and multicast routes are all stored in the same table,
rather than treating multicast as a bag-on-the-side wart) can have route
prefixes as long as /64 for IPv4 and /256 for IPv6, so it can't assume
that an IPv4 route prefix fits in a single 32 bit word and the best IPv4
code you can write is pretty much the same as the IPv6 code.

Dennis Ferguson