rwhoisd/Cidr.py

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