How can I subtract two IPv6 addresses (128bit numb

问题:

I'm storing the IP address in sockaddr_in6 which supports an array of four 32-bit, addr[4]. Essentially a 128 bit number.

I'm trying to calculate number of IPs in a given IPv6 range (how many IPs between). So it's a matter of subtracting one from another using two arrays with a length of four.

The problem is since there's no 128bit data type, I can't convert into decimal.

Thanks a ton!

回答1:

You could use some kind of big-int library (if you can tolerate LGPL, GMP is the choice). Fortunately, 128 bit subtraction is easy to simulate by hand if necessary. Here is a quick and dirty demonstration of computing the absolute value of (a-b), for 128 bit values:

#include <iostream>
#include <iomanip>

struct U128
{
    unsigned long long hi;
    unsigned long long lo;
};

bool subtract(U128& a, U128 b)
{
    unsigned long long carry = b.lo > a.lo;
    a.lo -= b.lo;
    unsigned long long carry2 = b.hi > a.hi || a.hi == b.hi && carry;
    a.hi -= carry;
    a.hi -= b.hi;
    return carry2 != 0;
}

int main()
{
    U128 ipAddressA = { 45345, 345345 };
    U128 ipAddressB = { 45345, 345346 };

    bool carry = subtract(ipAddressA, ipAddressB);

    // Carry being set means that we underflowed; that ipAddressB was > ipAddressA.
    // Lets just compute 0 - ipAddressA as a means to calculate the negation 
    // (0-x) of our current value. This gives us the absolute value of the
    // difference.
    if (carry)
    {
        ipAddressB = ipAddressA;
        ipAddressA = { 0, 0 };
        subtract(ipAddressA, ipAddressB);
    }

    // Print gigantic hex string of the 128-bit value
    std::cout.fill ('0');
    std::cout << std::hex << std::setw(16) << ipAddressA.hi << std::setw(16) << ipAddressA.lo << std::endl; 
}

This gives you the absolute value of the difference. If the range is not huge (64 bits or less), then ipAddressA.lo can be your answer as a simple unsigned long long.

If you have perf concerns, you can make use of compiler intrinsics for taking advantage of certain architectures, such as amd64 if you want it to be optimal on that processor. _subborrow_u64 is the amd64 intrinsic for the necessary subtraction work.

回答2:

The in6_addr structure stores the address in network byte order - or 'big endian' - with the most significant byte @ s6_addr[0]. You can't count on the other union members being consistently named, or defined. Even If you accessed the union through a (non-portable) uint32_t field, the values would have to be converted with ntohl. So a portable method of finding the difference needs some work.

You can convert the in6_addr to uint64_t[2]. Sticking with typical 'bignum' conventions, we use [0] for the low 64-bits and [1] for the high 64-bits:

static inline void
in6_to_u64 (uint64_t dst[2], const struct in6_addr *src)
{
    uint64_t hi = 0, lo = 0;

    for (unsigned int i = 0; i < 8; i++)
    {
        hi = (hi << 8) | src->s6_addr[i];
        lo = (lo << 8) | src->s6_addr[i + 8];
    }

    dst[0] = lo, dst[1] = hi;
}

and the difference:

static inline unsigned int
u64_diff (uint64_t d[2], const uint64_t x[2], const uint64_t y[2])
{
    unsigned int b = 0, bi;

    for (unsigned int i = 0; i < 2; i++)
    {
        uint64_t di, xi, yi, tmp;

        xi = x[i], yi = y[i];
        tmp = xi - yi;
        di = tmp - b, bi = tmp > xi;
        d[i] = di, b = bi | (di > tmp);
    }

    return b; /* borrow flag = (x < y) */
}