CIDR bitwise operations - could I be a bit wiser?

Question

I am building a class to represent an IPv4 subnet. I am storing the network address and the subnet mask as 4 byte binary strings, which are built during the constructor based on the arguments. One of the representations I would like the constructor to accept is CIDR notation.

My bitwise operations are a little rusty, and where I have got stuck is in converting a decimal integer CIDR representation of the subnet mask into a 4 byte binary string, and vice versa. I have also found I am unable to perform left/right shifts on string - which I'm sure I have successfully done before?

---

I have managed to get the conversion to the binary string to work with the following code:

// An example input value.
$mask = 24; // 255.255.255.0

if ($mask < 0 || $mask > 32) {
  // Invalid prefix size
  throw new RangeException('Invalid CIDR prefix size');
} else if ($mask === 0) {
  // Handle 0
  $mask = "\x00\x00\x00\x00";
} else {
  // Left-pad a 4-byte string with $mask set bits
  $mask = pack('N', (0x01 << 31) >> ($mask - 1));
}

I don't like this logic for two reasons:

• I don't like treating 0 as a special case
• I don't like the right-shift followed by a left-shift

I feel sure there is a way to do this more efficiently in a way that will handle 0 correctly without treating it as a special case.

---

When converting a binary string back to the decimal representation of a CIDR prefix size, I am currently using the code below. I have another very similar block of code when validating a subnet mask provided in other formats to ensure the set bits are contiguous.

// An example input value.
$mask = "\xff\xff\xff\x00"; // /24

// Convert the binary string to an int so bit shifts will work
$mask = current(unpack('N', $mask));

// A counter to represent the CIDR
$cidr = 0;

// Loop and check each bit
for ($i = 31; $i > 0; $i--) {
  if (($mask >> $i) & 0x01) {
    $cidr++;
  } else {
    break;
  }
}

// Return the result
return $cidr;

I don't like this because of the loop - I feel sure there is a more intelligent bitwise way to do it.

---

Is there a more intelligent way to do either of these tasks?

Thoughts/suggestions/general abuse please...

---

EDIT:

Any solutions need to work on PHP 4.3.10 and upwards, and must work on both 32- and 64-bit platforms. Please keep in mind that all integers in PHP are signed, and on a 32-bit platform anything >= 0x80000000 will be stored as a double (and will therefore not play nice with bitwise operations).

Answer 1

Your second problem can be alternatively seen as finding the first set bit in the inverted number (instead of finding the first not set bit in the non-inverted number), which is equivalent to finding the integer log2 of the number.

This is a fairly common problem in the bitwise world and there are numerous speed-optimized algorithms for it. You are using the (slow) obvious algorithm: http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

But I assume that you don't really care about speed, but rather about brevity, in that case you could do something like this:

$cidr = (int) (32 - log(~current(unpack('N', $mask)) & 0xffffffff, 2));

The & 0xffffffff is necessary to be compatible with 64 bit integers.

Answer 2

The second problem may be solved by a textual approach:

$mask = "\xff\xff\xff\x00";

$cidr = strspn(sprintf('%b', current(unpack('N', $mask))), 1);

It uses sprintf() to convert the integer into binary text representation and strspn() counts the number of initial ones.

Update

On 64-bit machines, the binary text representation is left-padded with 32 zeroes, so the code needs to be patched with ltrim() like so:

$cidr = strspn(ltrim(sprintf('%b', current(unpack('N', $mask))), 0), 1);

Update 2

The first problem can be solved with a textual approach as well, albeit necessitating the use of str_split() (which doesn't work in PHP 4.x):

$mask = vsprintf('%c%c%c%c', array_map('bindec', str_split(str_pad(str_repeat(1, $mask), 32, 0), 8)));

Update 3

What works for me is the following (tested on both 32 and 64 bit):

$mask = pack('N', 0xffffffff << (32 - $mask));

In the process, the number becomes a float but retains enough accuracy to deal with the bit shifting.

Answer 3

Why not do:

$netmask = ( (1<<32) -1 ) << ( 32 - $cidr);

You said you don't like the left then right shifts, how about two left shifts ;)

After this, I toss it into ip2long or long2ip. To go from mask to CIDR, I'll do:

$mask = ip2long($mask);
$base = ( ( 1 << 32 ) - 1 );
$cidr = 32 - log( ( $mask ^ $base ) + 1 , 2);

Of course, you can pack or dechex, or unpack the above as needed to fit your storage type.

Answer 4

Why compute it at all? Just create an array of 32 subnet masks.

$cidr2mask = array( "\x00\x00\x00\x00", "\x80\x00\x00\x00", "\xc0\x00\x00\x00", "\xe0\x00\x00\x00",
                    "\xf0\x00\x00\x00", "\xf8\x00\x00\x00", "\xfc\x00\x00\x00", "\xfe\x00\x00\x00", 
                    "\xff\x00\x00\x00", "\xff\x80\x00\x00", "\xff\xc0\x00\x00", "\xff\xe0\x00\x00", 
                    "\xff\xf0\x00\x00", "\xff\xf8\x00\x00", "\xff\xfc\x00\x00", "\xff\xfe\x00\x00", 
                    "\xff\xff\x00\x00", "\xff\xff\x80\x00", "\xff\xff\xc0\x00", "\xff\xff\xe0\x00", 
                    "\xff\xff\xf0\x00", "\xff\xff\xf8\x00", "\xff\xff\xfc\x00", "\xff\xff\xfe\x00", 
                    "\xff\xff\xff\x00", "\xff\xff\xff\x80", "\xff\xff\xff\xc0", "\xff\xff\xff\xe0", 
                    "\xff\xff\xff\xf0", "\xff\xff\xff\xf8", "\xff\xff\xff\xfc", "\xff\xff\xff\xfe");

$mask2cidr = array_flip($cidr2mask);

Then just use $cidr2mask[$cidr]; and $mask2cidr[$mask].

Answer 5

(Shameless self promotion)

I've built a PHP library which does very similar things for IP addresses.

Here's how I build an IPv4 subnetmask:

<?php
$mask = (~0) << (32 - $cidr);
$binary_mask = pack('N', $mask);
echo implode('.', unpack('C4', $binary_mask));

It won't work on older versions of PHP due to namespaces, but have branches from before their addition to which I'd be happy to accept pull requests to fix compatibility issues. The code is (almost) 100% covered by unit tests :)

The only dependency is the pear Math_BigInteger package.