rwhoisd/Cidr.py

   1 # This file is part of python-rwhoisd
   2 #
   3 # Copyright (C) 2003, 2008 David E. Blacka
   4 #
   5 # This program is free software; you can redistribute it and/or modify
   6 # it under the terms of the GNU General Public License as published by
   7 # the Free Software Foundation; either version 2 of the License, or
   8 # (at your option) any later version.
   9 #
  10 # This program is distributed in the hope that it will be useful, but
  11 # WITHOUT ANY WARRANTY; without even the implied warranty of
  12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 # General Public License for more details.
  14 #
  15 # You should have received a copy of the GNU General Public License
  16 # along with this program; if not, write to the Free Software
  17 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  18 # USA
  19
  20 import socket, types, copy, bisect, re, struct
  21
  22 class Cidr:
  23     """A class representing a generic CIDRized network value."""
  24
  25     def __str__(self):
  26         return self.addr + "/" + str(self.netlen)
  27
  28     def __repr__(self):
  29         return "<" + str(self) + ">"
  30
  31     def __cmp__(self, other):
  32         """One CIDR network block is less than another if the start
  33         address is numerically less or if the block is larger.  That
  34         is, supernets will sort before subnets.  This ordering allows
  35         for an efficient search for subnets of a given network."""
  36
  37         res = self._base_mask(self.numaddr) - self._base_mask(other.numaddr)
  38         if res == 0: res = self.netlen - other.netlen
  39         if res < 0: return -1
  40         if res > 0: return 1
  41         return 0
  42
  43     def calc(self):
  44         """This method should be called after any change to the main
  45         internal state: netlen or numaddr."""
  46
  47         # make sure the network length is valid
  48         if not self._is_valid_netlen(netlen):
  49             raise TypeError, "network length must be between 0 and %d" % (_max_netlen())
  50
  51         # convert the string ipv4 address to a 32bit number
  52         self.numaddr = self._convert_ipstr(self.addr)
  53         # calculate our netmask
  54         self.mask = self._mask(self.netlen)
  55         # force the cidr address into correct masked notation
  56         self.numaddr &= self.mask
  57
  58         # convert the number back to a string to normalize the string
  59         self.addr = self._convert_ipaddr(self.numaddr)
  60
  61     def is_supernet(self, other):
  62         """returns True if the other Cidr object is a supernet (an
  63         enclosing network block) of this one.  A Cidr object is a
  64         supernet of itself."""
  65         return other.numaddr & self.mask == self.numaddr
  66
  67     def is_subnet(self, other):
  68         """returns True if the other Cidr object is a subnet (an
  69         enclosednetwork block) of this one.  A Cidr object is a
  70         subnet of itself."""
  71         return self.numaddr & other.mask == other.numaddr
  72
  73     def netmask(self):
  74         """return the netmask of this Cidr network"""
  75         return self._convert_ipaddr(self.mask)
  76
  77     def length(self):
  78         """return the length (in number of addresses) of this network block"""
  79         return netlen_to_length(self.netlen)
  80
  81     def end(self):
  82         """return the last IP address in this network block"""
  83         return self._convert_ipaddr(self.numaddr + self.length() - 1)
  84
  85     def to_netblock(self):
  86         return (self.addr, self.end())
  87
  88     def clone(self):
  89         # we can get away with a shallow copy (so far)
  90         return copy.copy(self)
  91
  92 class CidrV4(Cidr):
  93     """A class representing a CIDRized IPv4 network value.
  94
  95     Specifically, it is representing a contiguous IPv4 network block
  96     that can be expressed as a ip-address/network-length pair."""
  97
  98     # FIXME: we should probably actually make this class immutable and
  99     # add methods that generate copies of this class with different
 100     # netlens or whatever.
 101
 102     ip4addr_re = re.compile("^\d{1,3}(\.\d{1,3}){0,3}(/\d{1,2})?$")
 103
 104     def __init__(self, address, netlen = -1):
 105         """This takes either a formatted string in CIDR notation:
 106         (e.g., "127.0.0.1/32"), A tuple consisting of an formatting
 107         string IPv4 address and a numeric network length, or the same
 108         as two arguments."""
 109
 110         # if we are handing a numerical address and netlen, convert
 111         # them directly.
 112         if isinstance(address, int) and netlen >= 0:
 113             self.netlen = netlen
 114             self.numaddr = address
 115             self.addr = self._convert_ipaddr(self.numaddr);
 116             self.calc()
 117             return
 118
 119         if not CidrV4.ip4addr_re.search(address):
 120             raise ValueError, repr(address) + \
 121                   " is not a valid CIDR representation"
 122
 123         if netlen < 0:
 124             if type(address) == types.StringType:
 125                 if "/" in address:
 126                     self.addr, self.netlen = address.split("/", 1)
 127                 else:
 128                     self.addr, self.netlen = address, 32
 129             elif type(address) == types.TupleType:
 130                 self.addr, self.netlen = address
 131             else:
 132                 raise TypeError, "address must be a string or a tuple"
 133         else:
 134             self.addr = address
 135             self.netlen = netlen
 136
 137         # convert string network lengths to integer
 138         if type(self.netlen) == types.StringType:
 139             self.netlen = int(self.netlen)
 140
 141         self.calc()
 142
 143     def _base_mask(self, numaddr):
 144         return numaddr & 0xFFFFFFFFL
 145
 146     def _max_netlen(self):
 147         return 32
 148
 149     def _is_valid_netlen(self, netlen):
 150         if self.netlen < 0: return False
 151         if self.netlen > _max_netlen(): return False
 152         return True
 153
 154     def _convert_ipstr(self, addr):
 155         return socket.inet_aton(addr)
 156
 157     def _convert_ipaddr(self, numaddr):
 158         res = str((numaddr & 0xFF000000) >> 24 & 0xFF) + "." + \
 159               str((numaddr & 0x00FF0000) >> 16) + "." + \
 160               str((numaddr & 0x0000FF00) >> 8) + "." + \
 161               str(numaddr & 0x000000FF)
 162         return res
 163
 164     def _mask(self, len):
 165         return 0xFFFFFFFF << (32 - len)
 166
 167 class CidrV6(Cidr):
 168     """A class representing a CIDRized IPv6 network value.
 169
 170     Specifically, it is representing a contiguous IPv6 network block
 171     that can be expressed as a ipv6-address/network-length pair."""
 172
 173     ip6addr_re = re.compile("^[\da-f]{1,4}(:[\da-f]{1,4}){0,7}(::[\da-f])?(/\d{1,3})?$", re.I)
 174     ip6_base_mask = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFL # 128-bits of all ones.
 175
 176     def __init__(self, address, netlen = -1):
 177
 178         if isinstance(address, long) and netlen >= 0:
 179             self.netlen = netlen
 180             self.numaddr = address
 181             self.addr = self._convert_ipaddr(address)
 182             self.calc()
 183             return
 184
 185         if not CidrV6.ip6addr_re.search(address):
 186             raise ValueError, repr(address) + \
 187                 "is not a valid CIDR representation"
 188
 189         if netlen < 0:
 190             if type(address) == types.StringType:
 191                 if "/" in address:
 192                     self.addr, self.netlen = address.split("/", 1)
 193                 else:
 194                     self.addr, self.netlen = address, 128
 195             elif type(address) == types.TupleType:
 196                 self.addr, self.netlen = address
 197             else:
 198                 raise TypeError, "address must be a string or a tuple"
 199         else:
 200             self.addr = address
 201             self.netlen = netlen
 202
 203         if type(self.netlen) == type.StringType:
 204             self.netlen = int(self.netlen)
 205
 206         self.calc()
 207
 208     def _base_mask(self, numaddr):
 209         return numaddr & CidrV6.ip6_base_mask
 210
 211     def _convert_ipstr(self, addr):
 212         packed_numaddr = socket.inet_pton(socket.AF_INET6, addr)
 213         upper, lower = struct.unpack("!QQ", packed_numaddr);
 214         numaddr = (upper << 64) | lower
 215
 216     def _convert_ipaddr(self, numaddr):
 217         upper = (numaddr & (ip6_base_mask << 64)) >> 64;
 218         lower = numaddr & (ip6_base_mask >> 64)
 219         packed_numaddr = struct.pack("!QQ", upper, lower)
 220         return socket.inet_ntop(socket.AF_INET6, packed_numaddr)
 221
 222     def _mask(self, len):
 223         return ip6_base_mask << (128 - len)
 224
 225
 226 def valid_cidr(address):
 227     """Returns the converted Cidr object  if 'address' is valid
 228     CIDR notation, False if not.  For the purposes of this module,
 229     valid CIDR notation consists of 1 to 4 octets separated by '.'
 230     characters, with an optional trailing "/netlen"."""
 231
 232     if isinstance(address, Cidr): return address
 233     try:
 234         c = Cidr(address)
 235         return c
 236     except:
 237         return False
 238
 239
 240 def netlen_to_length(netlen):
 241     """Convert a network-length to the length of the block in ip
 242     addresses."""
 243
 244     return 1 << (32 - netlen);
 245
 246 def netblock_to_cidr(start, end):
 247     """Convert an arbitrary network block expressed as a start and end
 248     address (inclusive) into a series of valid CIDR blocks."""
 249
 250     def largest_prefix(length):
 251         # calculates the largest network length (smallest mask length)
 252         # that can fit within the block length.
 253         i = 1; v = length
 254         while i <= 32:
 255             if v & 0x80000000: break
 256             i += 1; v <<= 1
 257         return i
 258     def netlen_to_mask(n):
 259         # convert the network length into its netmask
 260         return ~((1 << (32 - n)) - 1)
 261
 262
 263     # convert the start and ending addresses of the netblock to Cidr
 264     # object, mostly so we can get the numeric versions of their
 265     # addresses.
 266     cs = valid_cidr(start)
 267     ce = valid_cidr(end)
 268
 269     # if either the start or ending addresses aren't valid ipv4
 270     # address, quit now.
 271     if not cs or not ce:
 272         return None
 273
 274     # calculate the number of IP address in the netblock
 275     block_len = ce.numaddr - cs.numaddr
 276
 277     # calcuate the largest CIDR block size that fits
 278     netlen = largest_prefix(block_len + 1)
 279
 280     res = []; s = cs.numaddr
 281     while block_len > 0:
 282         mask = netlen_to_mask(netlen)
 283         # check to see if our current network length is valid
 284         if (s & mask) != s:
 285             # if not, shrink the network block size
 286             netlen += 1
 287             continue
 288         # otherwise, we have a valid CIDR block, so add it to the list
 289         cv = Cidr(s, netlen)
 290         res.append(Cidr(s, netlen))
 291         # and setup for the next round:
 292         cur_len = netlen_to_length(netlen)
 293         s         += cur_len
 294         block_len -= cur_len
 295         netlen = largest_prefix(block_len + 1)
 296     return res
 297
 298 # test driver
 299 if __name__ == "__main__":
 300     a = Cidr("127.00.000.1/24")
 301     b = Cidr("127.0.0.1", 32)
 302     c = Cidr("24.232.119.192", 26)
 303     d = Cidr("24.232.119.0", 24)
 304     e = Cidr("24.224.0.0", 11)
 305     f = Cidr("216.168.111.0/27");
 306     g = Cidr("127.0.0.2/31");
 307     h = Cidr("127.0.0.16/32")
 308     print f.addr
 309
 310     try:
 311         bad = Cidr("24.261.119.0", 32)
 312     except Warning, x:
 313         print "warning:", x
 314
 315     print "cidr:", a, "num addresses:", a.length(), "ending address", \
 316           a.end(), "netmask", a.netmask()
 317
 318     clist = [a, b, c, d, e, f, g, h]
 319     print "unsorted list of cidr objects:\n  ", clist
 320
 321     clist.sort()
 322     print "sorted list of cidr object:\n  ", clist
 323
 324     netblocks = [ ("192.168.10.0", "192.168.10.255"),
 325                   ("192.168.10.0", "192.168.10.63"),
 326                   ("172.16.0.0", "172.16.127.255"),
 327                   ("24.33.41.22", "24.33.41.37"),
 328                   ("196.11.1.0", "196.11.30.255"),
 329                   ("192.247.1.0", "192.247.10.255")]
 330
 331     for start, end in netblocks:
 332         print "netblock %s - %s:" % (start, end)
 333         blocks = netblock_to_cidr(start, end)
 334         print blocks