Find the single smallest IP network with the given IP addresses

Question

I have a bunch of IP addresses. I want one IP network that has them all. ipaddr.collapse_address_list already exists, but that gives you a list of all the IP networks that identify your IP addresses, no more, no less, whereas I only need one IP network.

I tried at first using XOR, but that fails on some situations (say, 10.0.0.1, 10.0.0.2, 10.0.0.255, 10.0.0.251: bin(1 ^ 2 ^ 255 ^ 251) = 0b111). And'ing has similar problems. This is what I ended up writing.

#http://stackoverflow.com/a/3789000/13992
def _AllSame(items):
  it = iter(items)
  first = next(it, None)
  return all(x == first for x in it)


def _GetOneNetmaskForAllTheseIPs(ips):
  """Get the one IP network that covers all IPs in input.

  ipaddr.collapse_address_list is a little bit TOO smart and gives you the LIST
  of networks that describe a number of IP addreses. Ceph just wants one
  netmask. This function tries to get that one netmask.

  >>> _GetOneNetmaskForAllTheseIPs(("10.0.0.1", "10.0.0.2",
  ...   "10.0.0.251", "10.0.0.255"))
  10.0.0.0/24
  """

  #Turn each IP address in its binary representation, without 0b header
  num_ip_addresses = [int(ipaddr.IPAddress(ip)) for ip in ips]
  lowest_ip = ipaddr.IPAddress(min(num_ip_addresses))
  bin_ip_addresses = [bin(ip)[2:] for ip in num_ip_addresses]

  #"Transpose" the list (abc),(def) → (ad),(be),(cf)
  bit_comparison = zip(*bin_ip_addresses)

  differing_bits = len(bit_comparison)
  #Find the first different bit
  while _AllSame(bit_comparison[-differing_bits]):
    differing_bits -= 1

  #That's the no. of bits that differ. The mask is the number of bits that DON'T
  mask_length = lowest_ip.max_prefixlen - differing_bits

  #Return the network
  network_ip = ipaddr.IPNetwork("%s/%d" % (lowest_ip, mask_length)).network
  network = ipaddr.IPNetwork("%s/%d" % (network_ip, mask_length), strict = True)
  return str(network)

I tried to be as IP-version agnostic as possible here, but chances are I've overlooked a few more-or-less obvious things here — or, even more likely, there's already a better inbuilt solution somewhere in the python libraries or even ipaddr itself.

Answer 1

You don't have to look at all the IPs to catch 'em all. Just looking at the lowest and highest does the trick. This realisation comes in handy when you consider that ipaddr does have a (private) function that gives you the common prefix length between two IP addresses. The code can then be simplified to:

#with many thanks to gfalcon
def _GetOneNetmaskForAllTheseIPs(ips):
  """Get the one IP network that covers all IPs in input.

  ipaddr.collapse_address_list is a little bit TOO smart and gives you the LIST
  of networks that describe a number of IP addreses. Ceph just wants one
  netmask. This function tries to get that one netmask.

  >>> _GetOneNetmaskForAllTheseIPs(("10.0.0.1", "10.0.0.2",
  ...   "10.0.0.251","10.0.0.255"))
  10.0.0.0/24
  """

  #Look at larger and smaller IP addresses
  ips = [ipaddr.IPAddress(ip) for ip in ips]
  lowest_ip, highest_ip = min(ips), max(ips)

  mask_length = ipaddr._get_prefix_length(
    int(lowest_ip), int(highest_ip), lowest_ip.max_prefixlen)

  #Return the network
  network_ip = ipaddr.IPNetwork("%s/%d" % (lowest_ip, mask_length)).network
  network = ipaddr.IPNetwork("%s/%d" % (network_ip, mask_length), strict = True)
  return str(network)

You still can't use public functions like ipaddr.summarize_address_range, because the library will still painstakingly try to avoid any IP address ever so slightly off range.

>>> ipaddr.summarize_address_range(IPv4Address('10.0.0.1'), IPv4Address('10.0.0.255'))
[IPv4Network('10.0.0.1/32'),
 IPv4Network('10.0.0.2/31'),
 IPv4Network('10.0.0.4/30'),
 IPv4Network('10.0.0.8/29'),
 IPv4Network('10.0.0.16/28'),
 IPv4Network('10.0.0.32/27'),
 IPv4Network('10.0.0.64/26'),
 IPv4Network('10.0.0.128/25')]