Finding largest netmask for given set of hosts

[Steve Holden]

"Edvard Majakari" <edvard.majakari at staselog.com> wrote in message
news:873ctotgvw.fsf at titan.staselog.com...
>
> I'm trying to construct a class method which returns the smallest possible
> network (largest netmask) for given set of hosts.
>
> Now, I have list of ip addresses in object variable self._list. Each IP
> address is in binary format (32-bit long)
>
> The algorithm is below:
>
>     def gen_mask(self):
>
>         nw = self._list[0]      # initialise network to first ip address
>         nm = 0xFFFFFFFFL        # initialise netmask to 255.255.255.255
(32)
>
>         # for every other ip in the list
>         for ip in self._list[1:]:
>             nw = nw & nm  # AND network with netmask
>
>             # XOR the network with ip address. All differing bits
>             # should be ones after XOR, and all bits that are same should
>             # be ones
>
>             x = nw ^ ip
>
>             # now, if nw was 192.128.11.12 and first ip was 192.128.11.20,
>             # result of x should be 24L, which is corresponds to bitmask
of
>             # 00000000000000000000000000011000. However, this is
>             # undesirable - we need a bitmask that has ones for the
>             # constant parts of the ip addresses and zeroes for the rest.
>             # by inverting x (~ x) we get
>             # 11111111111111111111111111100111, which still contains
>             # one at the end of the bitstring. We get rid of this bit
>             # by calling a function that zeroes all the rest bits after
>             # the first zero bit:
>
>             nm = zero_after_first_zero(dec2bin(~x))
>
>             # now nm (according to the example) is
>             # 11111111111111111111111111100000. We use this to
>             # to recalculate new network:
>             nw = nw & nm
>
>             # now nw should be 192.128.11.0 and netmask is 27
>
>         return nw
>
>
> The problem is that in Python, it seems quite difficult to create a
> routine dec2bin that would handle binary digits. I also doubt the
> algorithm is the best for this kind of thing.
>
> I wonder is there any existing Python modules that would do this kind of
> thing? I searched one for days (using Google), but didn't find any..
>

The first thing to note is that (version 4) IP addresses are 32-bit numbers,
which means that most Python implementations can handle them as integers and
use the bit-wise operations on them. Consequently, if all addresses are
converted before use, you won't need dec2bin. A naiive implementation will
end up producing long integers for anything above the class A space,
however. Unless efficiency is *really* important I'd overlook this as long
as your Python is recent enough to implicitly convert. You could even
explicitly use longs if you wanted.

Here's a simple implementation using these ideas. I haven't tested it
thoroughly, and it certainly hasn't been written for efficiency, but it
should give you something to play with.

def iptonum(s):
    l = s.split('.')
    addr = 0
    for byte in l:
        addr = 256*addr+int(byte)
    return long(addr)

def numtoip(a):
    l = []
    for i in range(4):
        l.append(str(a & 0xFF))
        a >>= 8
    l.reverse()
    return ".".join(l)

addlist = [iptonum(x) for x in
   ['192.168.10.23',
    '192.168.10.15',
    '192.168.14.15',
    '192.168.12.25']
]

mask = iptonum('255.255.255.255')
net = addlist[0]

for add in addlist[1:]:
    mask = net ^ ~add
    net = net & mask

#
# Now set all bits to the right of
# the leftmost zero to zero for the correct
# netmask, and use the mask to derive the
# correct network number.
#
zeros = 0
for bit in range(32, 0, -1):
    pos = bit -1
    zeros = zeros | (~mask & (1<< pos))
    if zeros:
        mask = mask & ~(1 << pos)

net = net & mask

print "Mask:   ", numtoip(mask)
print "Network:", numtoip(net)

regards
-----------------------------------------------------------------------
Steve Holden                                 http://www.holdenweb.com/
Python Web Programming                http://pydish.holdenweb.com/pwp/
-----------------------------------------------------------------------