Efficient way to test if bitwise IPv6 netmask is contiguous

I came across the following solution:

Split the IPV6 bytes in four chunks of 32 bits and create three parts in the following manner:

uint64_t netmask1, netmask2, netmask3; netmask1 = (netmask.s6_addr32[0] << 32) + in6_netmask.s6_addr32[1]; netmask2 = (netmask.s6_addr32[1] << 32) + in6_netmask.s6_addr32[2]; netmask3 = (netmask.s6_addr32[2] << 32) + in6_netmask.s6_addr32[3]; 

If one of this parts is not contiguous, then the netmask is not contiguous.

 if ((((~address1 + 1) & (~address1)) != 0) || (((~address2 + 1) & (~address2)) != 0) || ((~address3 + 1) & (~address3)) != 0))) { // Netmask is not valid! } 

Some compilers have 128 bit integers. I have used __uint128_t in code which was compiled using gcc on an AMD64 architecture.

If you are using a compiler with 128 bit integers, you can simply reuse your existing code, since it makes no assumptions about the word size.

If you need to perform the calculation with a smaller word size, it naturally gets more complicated, but not much. First run a pointer through the words of the mask to find the first word with a zero bit (for example):

for (i = 0; i < 4 && netmask[i] != 0xffffffff; ++i) 

Next you can apply your original test to netmask[i], finally you need to test that any remaining words are zero.

A different approach is to apply your original test to each individual word and moreover test that every pair of words has the first be all ones or the second be all zeros:

int contiguous(uint32_t **netmask) { int i; for (i = 0; i < 4; ++i) { if ((~netmask[i] + 1) & (~netmask[i])) return 0; } for (i = 0; i < 3; ++i) { if ((netmask[i] != 0xffffffff) && (netmask[i+1] != 0)) return 0; } return 1; } 

You can also take the more common approach and not take a mask as input but instead take a prefix length specified as an integer in the range 0 through 128 as the input. Then you can construct the bitmask yourself and know that it is contiguous.