rwhoisd/Cidr.py

   1 import socket, types, copy, bisect, re
   2
   3 class Cidr:
   4     """A class representing a CIDRized IPv4 network value.
   5
   6     Specifically, it is representing contiguous IPv4 network blocks
   7     that can be expressed as a ip-address/network-length pair."""
   8
   9     # FIXME: we should probably actually make this class immutable and
  10     # add methods that generate copies of this class with different
  11     # netlens or whatever.
  12
  13     ip4addr_re = re.compile("^\d{1,3}(\.\d{1,3}){0,3}(/\d{1,2})?$")
  14
  15     def __init__(self, address, netlen = -1):
  16         """This takes either a formatted string in CIDR notation:
  17         (e.g., "127.0.0.1/32"), A tuple consisting of an formatting
  18         string IPv4 address and a numeric network length, or the same
  19         as two arguments."""
  20
  21         # if we are handing a numerical address and netlen, convert
  22         # them directly.
  23         if isinstance(address, int) and netlen >= 0:
  24             self.netlen = netlen
  25             self.numaddr = address
  26             mask = self._mask(netlen)
  27             self.numaddr &= mask
  28             self.addr = self._convert_ip4addr(self.numaddr)
  29             return
  30
  31         if not Cidr.ip4addr_re.search(address):
  32             raise ValueError, repr(address) + \
  33                   " is not a valid CIDR representation"
  34
  35         if netlen < 0:
  36             if type(address) == types.StringType:
  37                 if "/" in address:
  38                     self.addr, self.netlen = address.split("/", 1)
  39                 else:
  40                     self.addr, self.netlen = address, 32
  41             elif type(address) == types.TupleType:
  42                 self.addr, self.netlen = address
  43             else:
  44                 raise TypeError, "address must be a string or a tuple"
  45         else:
  46             self.addr = address
  47             self.netlen = netlen
  48
  49         # convert string network lengths to integer
  50         if type(self.netlen) == types.StringType:
  51             self.netlen = int(self.netlen)
  52
  53         self.calc()
  54
  55     def __cmp__(self, other):
  56         """One CIDR network block is less than another if the start
  57         address is numerically less or if the block is larger.  That
  58         is, supernets will sort before subnets.  This ordering allows
  59         for an effienct search for subnets of a given network."""
  60
  61         # FIXME: have to convert to longs to overcome signedness problems.
  62         #  There is probably a better way to do this.
  63         res = (self.numaddr & 0xFFFFFFFFL) - (other.numaddr & 0xFFFFFFFFL)
  64         if (res < 0 ): return -1
  65         if (res > 0): return 1
  66         res = self.netlen - other.netlen
  67         return res
  68
  69     def __str__(self):
  70         return self.addr + "/" + str(self.netlen)
  71
  72     def __repr__(self):
  73         return "<" + str(self) + ">"
  74
  75     def calc(self):
  76         """This method should be called after any change to the main
  77         internal state: netlen or numaddr."""
  78
  79         # make sure the network length is valid
  80         if self.netlen > 32 or self.netlen < 0:
  81             raise TypeError, "network length must be between 0 and 32"
  82
  83         # convert the string ipv4 address to a 32bit number
  84         self.numaddr = self._convert_ip4str(self.addr)
  85         # calculate our netmask
  86         self.mask = self._mask(self.netlen)
  87         # force the cidr address into correct masked notation
  88         self.numaddr &= self.mask
  89
  90         # convert the number back to a string to normalize the string
  91         self.addr = self._convert_ip4addr(self.numaddr)
  92
  93     def is_supernet(self, other):
  94         """returns True if the other Cidr object is a supernet (an
  95         enclosing network block) of this one.  A Cidr object is a
  96         supernet of itself."""
  97         return other.numaddr & self.mask == self.numaddr
  98
  99     def is_subnet(self, other):
 100         """returns True if the other Cidr object is a subnet (an
 101         enclosednetwork block) of this one.  A Cidr object is a
 102         subnet of itself."""
 103         return self.numaddr & other.mask == other.numaddr
 104
 105     def netmask(self):
 106         """return the netmask of this Cidr network"""
 107         return self._convert_ip4addr(self.mask)
 108
 109     def length(self):
 110         """return the length (in number of addresses) of this network block"""
 111         return netlen_to_length(self.netlen)
 112
 113     def end(self):
 114         """return the last IP address in this network block"""
 115         return self._convert_ip4addr(self.numaddr + self.length() - 1)
 116
 117     def to_netblock(self):
 118         return (self.addr, self.end())
 119
 120     def _convert_ip4str(self, addr):
 121         p = 3; a = 0
 122         for octet in addr.split(".", 3):
 123             o = int(octet);
 124             if (o & 0xFF != o):
 125                 raise SyntaxWarning, "octet " + str(o) + " isn't in range"
 126             a |= o << (p * 8)
 127             p -= 1
 128         return a
 129
 130     def _convert_ip4addr(self, numaddr):
 131         res = str((numaddr & 0xFF000000) >> 24 & 0xFF) + "." + \
 132               str((numaddr & 0x00FF0000) >> 16) + "." + \
 133               str((numaddr & 0x0000FF00) >> 8) + "." + \
 134               str(numaddr & 0x000000FF)
 135         return res
 136
 137     def _mask(self, len):
 138         return 0xFFFFFFFF << (32 - len)
 139
 140     def clone(self):
 141         # we can get away with a shallow copy (so far)
 142         return copy.copy(self)
 143
 144
 145 def valid_cidr(address):
 146     """Returns the converted Cidr object  if 'address' is valid
 147     CIDR notation, False if not.  For the purposes of this module,
 148     valid CIDR notation consists of 1 to 4 octets separated by '.'
 149     characters, with an optional trailing "/netlen"."""
 150
 151     if isinstance(address, Cidr): return address
 152     try:
 153         c = Cidr(address)
 154         return c
 155     except:
 156         return False
 157
 158
 159 def netlen_to_length(netlen):
 160     """Convert a network-length to the length of the block in ip
 161     addresses."""
 162
 163     return 1 << (32 - netlen);
 164
 165 def netblock_to_cidr(start, end):
 166     """Convert an arbitrary network block expressed as a start and end
 167     address (inclusive) into a series of valid CIDR blocks."""
 168
 169     def largest_prefix(length):
 170         # calculates the largest network length (smallest mask length)
 171         # that can fit within the block length.
 172         i = 1; v = length
 173         while i <= 32:
 174             if v & 0x80000000: break
 175             i += 1; v <<= 1
 176         return i
 177     def netlen_to_mask(n):
 178         # convert the network length into its netmask
 179         return ~((1 << (32 - n)) - 1)
 180
 181
 182     # convert the start and ending addresses of the netblock to Cidr
 183     # object, mostly so we can get the numeric versions of their
 184     # addresses.
 185     cs = valid_cidr(start)
 186     ce = valid_cidr(end)
 187
 188     # if either the start or ending addresses aren't valid ipv4
 189     # address, quit now.
 190     if not cs or not ce:
 191         return None
 192
 193     # calculate the number of IP address in the netblock
 194     block_len = ce.numaddr - cs.numaddr
 195
 196     # calcuate the largest CIDR block size that fits
 197     netlen = largest_prefix(block_len + 1)
 198
 199     res = []; s = cs.numaddr
 200     while block_len > 0:
 201         mask = netlen_to_mask(netlen)
 202         # check to see if our current network length is valid
 203         if (s & mask) != s:
 204             # if not, shrink the network block size
 205             netlen += 1
 206             continue
 207         # otherwise, we have a valid CIDR block, so add it to the list
 208         cv = Cidr(s, netlen)
 209         res.append(Cidr(s, netlen))
 210         # and setup for the next round:
 211         cur_len = netlen_to_length(netlen)
 212         s         += cur_len
 213         block_len -= cur_len
 214         netlen = largest_prefix(block_len + 1)
 215     return res
 216
 217 # test driver
 218 if __name__ == "__main__":
 219     a = Cidr("127.00.000.1/24")
 220     b = Cidr("127.0.0.1", 32)
 221     c = Cidr("24.232.119.192", 26)
 222     d = Cidr("24.232.119.0", 24)
 223     e = Cidr("24.224.0.0", 11)
 224     f = Cidr("216.168.111.0/27");
 225     g = Cidr("127.0.0.2/31");
 226     h = Cidr("127.0.0.16/32")
 227     print f.addr
 228
 229     try:
 230         bad = Cidr("24.261.119.0", 32)
 231     except Warning, x:
 232         print "warning:", x
 233
 234     print "cidr:", a, "num addresses:", a.length(), "ending address", \
 235           a.end(), "netmask", a.netmask()
 236
 237     clist = [a, b, c, d, e, f, g, h]
 238     print "unsorted list of cidr objects:\n  ", clist
 239
 240     clist.sort()
 241     print "sorted list of cidr object:\n  ", clist
 242
 243     netblocks = [ ("192.168.10.0", "192.168.10.255"),
 244                   ("192.168.10.0", "192.168.10.63"),
 245                   ("172.16.0.0", "172.16.127.255"),
 246                   ("24.33.41.22", "24.33.41.37"),
 247                   ("196.11.1.0", "196.11.30.255"),
 248                   ("192.247.1.0", "192.247.10.255")]
 249
 250     for start, end in netblocks:
 251         print "netblock %s - %s:" % (start, end)
 252         blocks = netblock_to_cidr(start, end)
 253         print blocks