ipaddr.py

   1 # ipaddr.py -- handle IP addresses and set of IP addresses.
   2 # Copyright (C) 1996-2000 Cendio Systems AB
   3 #
   4 # This program is free software; you can redistribute it and/or modify
   5 # it under the terms of the GNU General Public License as published by
   6 # the Free Software Foundation; either version 2 of the License, or
   7 # (at your option) any later version.
   8 #
   9 # This program is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 # GNU General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU General Public License
  15 # along with this program; if not, write to the Free Software
  16 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17
  18 """IP address manipulation.
  19
  20 This module is useful if you need to manipulate IP addresses or sets
  21 of IP addresses.
  22
  23 The main classes are:
  24
  25     ipaddr   -- a single IP address.
  26     netmask  -- a netmask.
  27     network  -- an IP address/netmask combination.  It is often, but
  28                 not always, better to use the ip_set class instead.
  29     ip_set   -- a set of IP addresses, that may or may not be adjacent.
  30
  31 So, what can you do with this module?  As a simple example of the kind
  32 of things this module can do, this code computes the set of all IP
  33 addresses except 127.0.0.0/8 and prints it, expressed as a union of
  34 network/netmask pairs.
  35
  36     import ipaddr
  37
  38     s = ipaddr.ip_set()
  39     s.add_network(ipaddr.network('127.0.0.0', '255.0.0.0',
  40                                  ipaddr.DEMAND_FILTER))
  41     for nw in s.complement().as_list_of_networks():
  42         print nw.ip_str() + '/' + nw.mask.netmask_bits_str
  43
  44 Errors are reported by raising an exception from the following
  45 exception hierarcy:
  46
  47 Exception       # The standard Python base exception class.
  48  |
  49  +-- BadType    # Only raised if the programmer makes an error.
  50  +-- IpError    # Base class for errors that depend on the data.
  51       |
  52       +-- SetNotRepresentable
  53       +-- BrokenIpAddress
  54       |    |
  55       |    +-- PartNegative
  56       |    +-- PartOverflow
  57       |
  58       +-- BrokenNetmask
  59       |    |
  60       |    +-- NeedOneBit
  61       |    +-- NeedMoreBits
  62       |    +-- NeedLessBits
  63       |
  64       +-- BrokenNetwork
  65             |
  66             +-- EmptyIpAddress
  67             +-- EmptyNetmask
  68             +-- BrokenNetworkAddress
  69             +-- NetworkAddressClash
  70             +-- BroadcastAddressClash
  71
  72 BadType may be raised at any time if the programmer makes an error
  73 (such as passing a dictionary to a function that expects a string).
  74 SetNotRepresentable may be raised by ip_set.as_str_range().  All other
  75 exceptions are raised from the constructors and helper functions only.
  76
  77 The following constants are present in this module:
  78
  79     DEMAND_NONE         See class network.
  80     DEMAND_FILTER       See class network.
  81     DEMAND_NETWORK      See class network.
  82     DEMAND_INTERFACE    See class network.
  83
  84     hostmask            A netmask object with all 32 bits set.
  85     complete_network    A network object representing all IP addresses.
  86     complete_set        An ip_set object representing all IP addresses.
  87     broadcast_network   A network object representing 255.255.255.255.
  88     broadcast_set       An ip_set object representing 255.255.255.255.
  89
  90 The as_ipaddr function can be used when you have an object that you
  91 know are an ipaddr or network, and you want to get the ipaddr part.
  92
  93 All the other functions in this module are internal helper functions,
  94 and they should not be used.
  95
  96 The internal representation used for IP addresses is currently a long
  97 number.  That may change in the future, so where the internal
  98 representation is visible, you should do nothing with it except
  99 compare it to None.
 100
 101 This module was developed by Cendio Systems AB for use in the Fuego
 102 Firewall.  Bug reports can be sent to Per Cederqvist <ceder@cendio.se>
 103 who is currently acting as maintainer for this module.
 104
 105 Brief history:
 106     1997-03-11      Module created, and used internally.
 107     2000-03-09 1.0: First non-public beta release outside of Cendio Systems.
 108     2000-03-17 1.1: First public release under the GNU GPL license.
 109
 110 """
 111
 112
 113 import copy
 114 import string
 115 import types
 116
 117 # The error messages are marked with a call to this function, so that
 118 # they can easily be found and translated.
 119 def _(s):
 120     return s
 121
 122 # The exception hierarchy.
 123 class IpError(Exception):
 124     """Base class for errors that are cause by errors in input data.
 125     """
 126     def __str__(self):
 127         return self.format % self.args
 128
 129 class SetNotRepresentable(IpError):
 130     format = _("The set of IP addresses cannot be represented "
 131                "as a single network range")
 132
 133 class BrokenIpAddress(IpError):
 134     format = _("Felaktigt IP-nummer")
 135
 136 class PartNegative(BrokenIpAddress):
 137     format = _("En komponent i IP-numret är negativ")
 138
 139 class PartOverflow(BrokenIpAddress):
 140     format = _("En komponent i IP-numret är större än 255")
 141
 142 class BrokenNetmask(IpError):
 143     format = _("Felaktig nätmask")
 144
 145 class NeedOneBit(BrokenNetmask):
 146     format = _("Minst en bit måste vara ettställd")
 147
 148 class NeedMoreBits(BrokenNetmask):
 149     format = _("Minst %d bitar måste vara ettställda")
 150
 151 class NeedLessBits(BrokenNetmask):
 152     format = _("Högst %d bitar får vara ettställda")
 153
 154 class BrokenNetwork(IpError):
 155     """Base class for errors regarding network objects.
 156     """
 157
 158 class EmptyIpAddress(BrokenNetwork):
 159     format = _("IP-nummer ej ifyllt")
 160
 161 class EmptyNetmask(BrokenNetwork):
 162     format = _("Nätmask ej ifylld")
 163
 164 class BrokenNetworkAddress(BrokenNetwork):
 165     format = _("Med denna nätmask är %s ett otillåtet nätverksnummer; "
 166                "menar du %s?")
 167
 168 class NetworkAddressClash(BrokenNetwork):
 169     format = _("Med denna nätmask krockar Fuegons adress med nätnumret")
 170
 171 class BroadcastAddressClash(BrokenNetwork):
 172     format = _("Med denna nätmask krockar Fuegons adress "
 173                "med broadcastadressen")
 174
 175 class BadType(Exception):
 176     """An object of an unexpected type was passed to a function.
 177     """
 178     pass
 179
 180 # These constants are used with netmasks and networks to specify what
 181 # the code expects.
 182 #
 183 #  DEMAND_NONE: netmask 0-32 (inclusive)
 184 #  DEMAND_FILTER: netmask 0-32, the host part must be all zeroes
 185 #  DEMAND_NETWORK: netmask 1-32, the host part must be all zeroes
 186 #  DEMAND_INTERFACE: netmask 1-30, the host part must *not* be all zeroes
 187
 188 DEMAND_NONE = 1
 189 DEMAND_FILTER = 2
 190 DEMAND_NETWORK = 3
 191 DEMAND_INTERFACE = 4
 192
 193 def bits_to_intrep(bits):
 194     """Convert BITS to the internal representation.
 195
 196     BITS should be a number in the range 0-32 (inclusive).
 197
 198     """
 199     return pow(2L, 32) - pow(2L, 32-bits)
 200
 201
 202 def intrep_with_bit_set(bit):
 203     """Return an internal representation with bit BIT set.
 204
 205     BIT should be a number in the range 1-32, where bit 1 is the
 206     leftmost.  Examples:
 207
 208       intrep_with_bit_set(1) --> the internal representation of 128.0.0.0
 209       intrep_with_bit_set(32) --> the internal representation of 0.0.0.1
 210     """
 211     assert 0 < bit and bit <= 32
 212
 213     return pow(2L, 32-bit)
 214
 215
 216 __ONES = {0:0, 128:1, 192:2, 224:3,
 217           240:4, 248:5, 252:6, 254:7}
 218
 219 def tuple_to_bits(mask):
 220     """Convert MASK to bits.
 221
 222     MASK should be a tuple of four integers in the range 0-255 (inclusive).
 223
 224     Raises BrokenNetmask if MASK is not a valid netmask.
 225     """
 226
 227     if mask == None:
 228         return None
 229     else:
 230         (a, b, c, d) = mask
 231
 232         if a == 255 and b == 255 and c == 255 and d == 255:
 233             return 32
 234
 235         try:
 236             if a == 255 and b == 255 and c == 255:
 237                 return 24 + __ONES[d]
 238             elif a == 255 and b == 255  and d == 0:
 239                 return 16 + __ONES[c]
 240             elif a == 255 and c == 0  and d == 0:
 241                 return 8 + __ONES[b]
 242             elif b == 0 and c == 0  and d == 0:
 243                 return __ONES[a]
 244         except KeyError:
 245             pass
 246
 247         raise BrokenNetmask()
 248
 249
 250 def intrep_to_dotted_decimal(t):
 251     """Convert T to dotted-decimal notation.
 252
 253     T should be the internal representation used py ipaddr.py.
 254     """
 255
 256     return (str(int(t>>24)) + '.' + str(int((t>>16) & 255))
 257             + '.' + str(int((t>>8) & 255)) + '.' + str(int(t & 255)))
 258
 259
 260 def as_ipaddr(nwip):
 261     """Return the IP address object of NWIP.
 262
 263     NWIP may be an ipaddr object, which is returned unchanged,
 264     or a network object, in which case the ipaddr part of it is
 265     returned.
 266     """
 267
 268     if isinstance(nwip, ipaddr):
 269         return nwip
 270     elif isinstance(nwip, network):
 271         return nwip.ip
 272     else:
 273         raise BadType('Expected a network or ipaddr object', nwip)
 274
 275
 276 class ipaddr:
 277     """Handle IP addresses.
 278
 279     Sample use:
 280
 281         ip1 = ipaddr('12.3.5.1')
 282         ip2 = ipaddr([12, 3, 5, 1])
 283         print ip1.ip_str()
 284         >>> '12.3.5.1'
 285         print ip1.intrep
 286         >>> 201524481L
 287         print ip2.ip_str()
 288         >>> '12.3.5.1'
 289         print ip2.intrep
 290         >>> 201524481L
 291
 292     An ipaddr object can have two states: empty or good.
 293     The status can be examined like this:
 294
 295         if ip.intrep == None:
 296             handle_empty(m.user_input())
 297         else:
 298             handle_good(ip)
 299
 300     All other members should only be used in the good state.  The
 301     value stored in the intrep member should only be compared against
 302     None.  The type and value of it is an internal detail that may
 303     change in the future.
 304
 305     """
 306
 307     def __init__(self, ip):
 308         """Create an ipaddr from IP (a string, tuple or list).
 309
 310         The empty string or None may be given; it is handled as the
 311         empty IP number.
 312         """
 313
 314         if type(ip) == types.StringType:
 315             self.__user_input = ip
 316             ip = string.strip(ip)
 317         else:
 318             self.__user_input = None
 319
 320         # The empty IP number?
 321
 322         if ip == '' or ip == None:
 323             self.__ip_str = ''
 324             self.intrep = None
 325             if ip == None:
 326                 self.__user_input = ''
 327             return
 328
 329         if type(ip) == types.StringType:
 330
 331             # Convert a string.
 332
 333             try:
 334                 [a, b, c, d] = map(string.atoi, string.splitfields(ip, '.'))
 335             except:
 336                 raise BrokenIpAddress()
 337
 338             if a < 0 or b < 0 or c < 0 or d < 0:
 339                 raise PartNegative()
 340
 341             if a > 255 or b > 255 or c > 255 or d > 255:
 342                 raise PartOverflow()
 343
 344             self.intrep = (long(a) << 24) + (b << 16) + (c << 8) + d
 345
 346         else:
 347             assert type(ip) == types.LongType
 348             self.intrep = ip
 349
 350         self.__ip_str = None
 351
 352     def ip_str(self):
 353         if self.__ip_str == None:
 354             self.__ip_str = intrep_to_dotted_decimal(self.intrep)
 355         return self.__ip_str
 356
 357     def user_input(self):
 358         if self.__user_input == None:
 359             # This object was constructed from a tuple.  Generate a string.
 360             self.__user_input = self.ip_str()
 361         return self.__user_input
 362
 363     def compare(self, other):
 364         """Compare this IP address with OTHER.
 365
 366         Returns -1, 0 or 1 if this IP address is less than, equal to,
 367         or greater than OTHER (which should be an ipaddr object).
 368         """
 369         # FIXME: should we rename this __cmp__?  It needs to handle
 370         # other types of the OTHER argument first.
 371
 372         if self.intrep == other.intrep:
 373             return 0
 374         if self.intrep < other.intrep:
 375             return -1
 376         else:
 377             return 1
 378
 379     def __str__(self):
 380         if self.intrep is None:
 381             return "<ipaddr empty>"
 382         else:
 383             return "<ipaddr %s>" % self.ip_str()
 384
 385     def __repr__(self):
 386         if self.intrep is None:
 387             return "ipaddr.ipaddr('')"
 388         else:
 389             return "ipaddr.ipaddr('%s')" % self.ip_str()
 390
 391
 392 class netmask:
 393     """Handle netmasks.
 394
 395     Sample use:
 396
 397         # Four ways to initialize a netmask.
 398         nm1 = netmask('255.255.128.0', DEMAND_NONE)
 399         nm2 = netmask([255, 255, 128, 0], DEMAND_NONE)
 400         nm3 = netmask('17', DEMAND_NONE)
 401         nm4 = netmask(17, DEMAND_NONE)
 402         print nm1.netmask_str()
 403         >>> '255.255.128.0'
 404         print nm1.intrep
 405         >>> (255, 255, 128, 0)
 406         print nm1.netmask_bits
 407         >>> 17
 408         print nm1.netmask_bits_str
 409         >>> '17'
 410
 411     A netmask can have two states: empty or good.  The state
 412     can be examined like this:
 413
 414         if m.intrep == None:
 415             handle_empty(m.user_input())
 416         else:
 417             handle_good(m)
 418
 419     All other members should be used only in the good state.
 420
 421     """
 422
 423     def __check_range(self, bits, minbits, maxbits):
 424         if bits < minbits:
 425             if minbits == 1:
 426                 raise NeedOneBit()
 427             else:
 428                 raise NeedMoreBits(minbits)
 429         elif bits > maxbits:
 430             raise NeedLessBits(maxbits)
 431
 432
 433     def __set_from_bits(self, bits, minbits, maxbits):
 434         self.__check_range(bits, minbits, maxbits)
 435         self.intrep = bits_to_intrep(bits)
 436         self.netmask_bits = bits
 437
 438
 439     def __set_from_tuple(self, tpl, minbits, maxbits):
 440         bits = tuple_to_bits(tpl)
 441         self.__check_range(bits, minbits, maxbits)
 442         self.intrep = bits_to_intrep(bits)
 443         self.netmask_bits = bits
 444
 445     DEMANDS = {DEMAND_NONE:(0,32),
 446                DEMAND_FILTER:(0,32),
 447                DEMAND_NETWORK:(1,32),
 448                DEMAND_INTERFACE:(1,30)}
 449
 450     def __init__(self, mask, demand):
 451         """Create a netmask from MASK (a string, tuple or number) and DEMAND.
 452
 453         The empty string or None may be given; it is handled as the
 454         empty netmask.
 455
 456         See class network for a description of the DEMAND parameter.
 457         """
 458
 459         (minbits, maxbits) = self.DEMANDS[demand]
 460         self.demand = demand
 461
 462         if type(mask) == types.StringType:
 463             self.__user_input = mask
 464             mask = string.strip(mask)
 465         else:
 466             self.__user_input = None
 467
 468         if mask == '' or mask == None:
 469
 470             # Handle empty netmasks.
 471
 472             self.__netmask_str = ''
 473             self.intrep = None
 474             self.netmask_bits_str = ''
 475             self.netmask_bits = None
 476             if self.__user_input == None:
 477                 self.input = ''
 478             return
 479
 480         # Decode the MASK argument and set self.netmask_bits
 481         # and self.intrep.
 482
 483         if type(mask) == types.StringType:
 484
 485             # Is this a string containing a single number?
 486             try:
 487                 bits = string.atoi(mask)
 488             except (OverflowError, ValueError):
 489                 bits = None
 490
 491             if bits != None:
 492
 493                 # This is a string containing a single number.
 494
 495                 self.__set_from_bits(bits, minbits, maxbits)
 496
 497             else:
 498
 499                 # Interpret the netmask as a dotted four-tuple.
 500                 try:
 501                     [a, b, c, d] = map(string.atoi,
 502                                        string.splitfields(mask, '.'))
 503                 except:
 504                     raise BrokenNetmask()
 505
 506                 self.__set_from_tuple((a, b, c, d), minbits, maxbits)
 507
 508         elif type(mask) == types.IntType:
 509
 510             # This is a number, representing the number of bits in the mask.
 511
 512             self.__set_from_bits(mask, minbits, maxbits)
 513
 514         else:
 515
 516             # This is a tuple or list.
 517
 518             if len(mask) != 4:
 519                 raise BadType('Wrong len of tuple/list')
 520
 521             (a, b, c, d) = (mask[0], mask[1], mask[2], mask[3])
 522
 523             self.__set_from_tuple((a, b, c, d), minbits, maxbits)
 524
 525         self.__netmask_str = None
 526         self.netmask_bits_str = repr(self.netmask_bits)
 527
 528     def netmask_str(self):
 529         if self.__netmask_str == None:
 530             self.__netmask_str = intrep_to_dotted_decimal(self.intrep)
 531         return self.__netmask_str
 532
 533     def user_input(self):
 534         if self.__user_input == None:
 535             # This object was constructed from a tuple or an integer.
 536             self.__user_input = self.ip_str()
 537         return self.__user_input
 538
 539     def __str__(self):
 540         if self.intrep is None:
 541             return "<netmask empty>"
 542         else:
 543             return "<netmask /%d>" % self.netmask_bits
 544
 545     def __repr__(self):
 546         if self.intrep is None:
 547             return "ipaddr.netmask('')"
 548         else:
 549             return "ipaddr.netmask(%d, %d)" % (self.netmask_bits, self.demand)
 550
 551
 552 hostmask = netmask(32, DEMAND_NONE)
 553
 554
 555 class network:
 556     """Designate a network or host.
 557
 558     The constructor takes three arguments: the IP number part, the
 559     netmask part, and a demand parameter.  See class ipaddr and class
 560     netmask for a description of the first two arguments.  The demand
 561     argument can be one of the following constants:
 562
 563     DEMAND_NONE
 564         No special demands.
 565     DEMAND_FILTER
 566         The host part must be all zeroes.
 567     DEMAND_NETWORK
 568         The netmask must be 1-32
 569         The host part must be all zeroes.
 570     DEMAND_INTERFACE
 571         The netmask must be 1-30
 572         The host part must *not* be all zeroes (the network address)
 573         or all ones (the broadcast address).
 574
 575     The following members exist and are set by the constructor:
 576
 577       ip.user_input()           # a caching function
 578       ip_str()                  # a caching function
 579       ip.intrep
 580       mask.user_input()         # a caching function
 581       mask.netmask_str()        # a caching function
 582       mask.intrep
 583       mask.netmask_bits
 584       mask.netmask_bits_str
 585       network_str()             # a caching function
 586       network_intrep
 587       broadcast_str()           # a caching function
 588       broadcast_intrep
 589       host_part_str()           # a caching function
 590       host_part_intrep
 591
 592     """
 593
 594     def __init__(self, ip, mask, demand):
 595         self.ip = ipaddr(ip)
 596         self.mask = netmask(mask, demand)
 597
 598         if self.ip.intrep == None:
 599             raise EmptyIpAddress()
 600
 601         if self.mask.intrep == None:
 602             raise EmptyNetmask()
 603
 604         self._precompute()
 605
 606     def _precompute(self):
 607         self.__lower_str = None
 608         self.__upper_str = None
 609
 610         self.network_intrep = self.ip.intrep & self.mask.intrep
 611         self.broadcast_intrep = (self.network_intrep |
 612                                 (pow(2L, 32)-1-self.mask.intrep))
 613         self.host_part_intrep = self.ip.intrep - self.network_intrep
 614
 615         self.__network_str = None
 616         self.__broadcast_str = None
 617         self.__host_part_str = None
 618
 619         demand = self.mask.demand
 620
 621         if demand == DEMAND_NONE:
 622             pass
 623         elif demand == DEMAND_FILTER or demand == DEMAND_NETWORK:
 624             if self.host_part_intrep != 0L:
 625                 raise BrokenNetworkAddress(self.ip_str(), self.network_str())
 626         elif demand == DEMAND_INTERFACE:
 627             if self.host_part_intrep == 0L:
 628                 raise NetworkAddressClash()
 629             elif self.broadcast_intrep == self.ip.intrep:
 630                 raise BroadcastAddressClash()
 631         else:
 632             raise BadType('Bad value for the demand parameter', demand)
 633
 634     def network_str(self):
 635         if self.__network_str == None:
 636             self.__network_str = intrep_to_dotted_decimal(self.network_intrep)
 637         return self.__network_str
 638
 639     def broadcast_str(self):
 640         if self.__broadcast_str == None:
 641             self.__broadcast_str = intrep_to_dotted_decimal(
 642                 self.broadcast_intrep)
 643         return self.__broadcast_str
 644
 645     def host_part_str(self):
 646         if self.__host_part_str == None:
 647             self.__host_part_str = intrep_to_dotted_decimal(
 648                 self.host_part_intrep)
 649         return self.__host_part_str
 650
 651     def overlaps(self, other):
 652         """Returns true if the network overlaps with OTHER.
 653
 654         OTHER must be a network object or an ipaddr object.  If it
 655         is empty this method will always return false.
 656
 657         """
 658
 659         if self.network_intrep == None:
 660             return 0
 661
 662         if isinstance(other, ipaddr):
 663
 664             if other.intrep == None:
 665                 return 0
 666
 667             return (self.mask.intrep & other.intrep) == self.network_intrep
 668         else:
 669             if other.network_intrep == None:
 670                 return 0
 671
 672             mask = self.mask.intrep & other.mask.intrep
 673             return (mask & self.ip.intrep) == (mask & other.ip.intrep)
 674
 675     def intersection(self, other):
 676         """Return the intersection of the network and OTHER.
 677
 678         The return value is a network object with DEMAND_FILTER.  If
 679         the intersection is empty this method will return None.
 680
 681         OTHER must be a network object or an ipaddr object.  The
 682         intersection will be empty if it is empty.
 683         """
 684
 685         if self.network_intrep == None:
 686             return None
 687
 688         if isinstance(other, ipaddr):
 689
 690             if other.intrep == None:
 691                 return None
 692
 693             prefix_mask = self.mask.intrep
 694             short_net = self.network_intrep
 695             long_ip = other.intrep
 696             result = network(other.intrep, 32, DEMAND_FILTER)
 697         else:
 698             if other.network_intrep == None:
 699                 return None
 700
 701             if self.mask.netmask_bits < other.mask.netmask_bits:
 702                 prefix_mask = self.mask.intrep
 703                 short_net = self.network_intrep
 704                 long_ip = other.network_intrep
 705                 result = network(other.network_intrep, other.mask.netmask_bits,
 706                                  DEMAND_FILTER)
 707             else:
 708                 prefix_mask = other.mask.intrep
 709                 short_net = other.network_intrep
 710                 long_ip = self.network_intrep
 711                 result = network(self.network_intrep, self.mask.netmask_bits,
 712                                  DEMAND_FILTER)
 713
 714         if (long_ip & prefix_mask) != (short_net & prefix_mask):
 715             return None
 716
 717         return result
 718
 719     def is_subset(self, nwip):
 720         """Return true if NWIP is a subset of this network.
 721
 722         NWIP must be a network object or an ipaddr object.
 723         """
 724
 725         if not self.overlaps(nwip):
 726             return 0
 727
 728         if isinstance(nwip, ipaddr):
 729             return 1
 730
 731         return nwip.mask.netmask_bits <= self.mask.netmask_bits
 732
 733     def is_same_set(self, nwip):
 734         """Return true if NWIP contains the same set as this network.
 735
 736         NWIP must be a network object or an ipaddr object.
 737         """
 738
 739         if isinstance(nwip, ipaddr):
 740             return (self.mask.netmask_bits == 32
 741                     and self.ip.intrep == nwip.intrep)
 742         else:
 743             return (self.mask.netmask_bits == nwip.mask.netmask_bits
 744                     and self.network_intrep == nwip.network_intrep)
 745
 746     def subtract(self, nwip):
 747         """Create a list of new network objects by subtracting NWIP from self.
 748
 749         The result consists of networks that together span all
 750         IP addresses that are present in self, except those that are
 751         present in NWIP.  (The result may be empty or contain several
 752         disjoint network objects.)
 753
 754         Don't use this!  This method is slow.  The ip_set class can do
 755         this kind of things in a more efficient way.
 756         """
 757
 758         if not self.overlaps(nwip):
 759             # No overlap at all, so NWIP cannot affect the result.
 760             return [self]
 761
 762         if isinstance(nwip, ipaddr):
 763             bits = 32
 764             intrep = nwip.intrep
 765         else:
 766             assert isinstance(nwip, network)
 767             bits = nwip.mask.netmask_bits
 768             intrep = nwip.ip.intrep
 769         nets = []
 770         while bits > self.mask.netmask_bits:
 771             nets.append(network(compute_neighbor(intrep, bits),
 772                                 bits, DEMAND_FILTER))
 773             bits = bits - 1
 774         return nets
 775
 776     def subtract_nwips(self, nwips):
 777         """Create a list of new network objects by subtracting NWIPS.
 778
 779         The result consists of networks that together span all
 780         IP addresses that are present in self, except those that are
 781         present in NWIPS.  (The result may be empty or contain
 782         several disjoint network objects.)  NWIPS should be a list
 783         of network or ipaddr objects.
 784
 785         Don't use this!  This method is slow.  The ip_set class can do
 786         this kind of things in a more efficient way.
 787         """
 788
 789         subtracted = [self]
 790         for s in nwips:
 791             # precondition<A>: SUBTRACTED is a list of networks
 792             tmp = []
 793             for nw in subtracted:
 794                 tmp = tmp + nw.subtract(s)
 795             subtracted = tmp
 796             # postcondition: SUBTRACTED is a list of networks that
 797             # spans all IP addresses that were present in
 798             # precondition<A>, except those that are present in S.
 799
 800         return subtracted
 801
 802     def __compute_lower_upper(self):
 803         if self.__lower_str != None:
 804             return
 805         assert self.network_intrep != None and self.broadcast_intrep != None
 806
 807         self.__lower_str = intrep_to_dotted_decimal(self.network_intrep + 1)
 808         self.__upper_str = intrep_to_dotted_decimal(self.broadcast_intrep - 1)
 809
 810     def lower_host(self):
 811         self.__compute_lower_upper()
 812         return self.__lower_str
 813
 814     def upper_host(self):
 815         self.__compute_lower_upper()
 816         return self.__upper_str
 817
 818     def __repr__(self):
 819         return _("{network %s/%d}") % (self.ip_str(), self.mask.netmask_bits)
 820
 821     def ip_str(self):
 822         return self.ip.ip_str()
 823
 824
 825 class ip_set:
 826     def __init__(self, nwip=None):
 827         """Create an ip_set.
 828
 829         If the optional argument NWIP is supplied, the set is
 830         initialized to it, otherwise the created set will be empty.
 831         NWIP must be a network or ipaddr object.
 832         """
 833
 834         # [[0L, 3L], [5L, 7L]] means 0.0.0.0/29 \ 0.0.0.4/32
 835         self.__set = []
 836
 837         if nwip != None:
 838             self.append(nwip)
 839
 840     def subtract_set(self, other):
 841         """Remove all IP-numbers in OTHER from this.
 842
 843         OTHER should be an ip_set object.
 844         """
 845
 846         self.subtract_list(other.__set)
 847
 848     def subtract_ips(self, ips):
 849         """Remove all IP-numbers in IPS from this.
 850
 851         IPS should be a list of ipaddr objects.
 852         """
 853
 854         for ip in ips:
 855             self.subtract_list([[ip.intrep, ip.intrep]])
 856
 857     def subtract_list(self, other):
 858         # Don't use this method directly, unless you are the test suite.
 859         ix = 0
 860         iy = 0
 861         while ix < len(self.__set) and iy < len(other):
 862             if self.__set[ix][1] < other[iy][0]:
 863                 # The entire range survived.
 864                 ix = ix + 1
 865             elif self.__set[ix][0] > other[iy][1]:
 866                 # The entire other range is unused, so discard it.
 867                 iy = iy + 1
 868             elif self.__set[ix][0] >= other[iy][0]:
 869                 if self.__set[ix][1] <= other[iy][1]:
 870                     # The entire range is subtracted.
 871                     del self.__set[ix]
 872                 else:
 873                     # The start of the range is subtracted, but
 874                     # the rest of the range may survive.  (As a matter
 875                     # of fact, at least one number *will* survive,
 876                     # since there should be a gap between other[iy][1]
 877                     # and other[iy+1][0], but we don't use that fact.)
 878                     self.__set[ix][0] = other[iy][1] + 1
 879                     iy = iy + 1
 880             else:
 881                 # The first part of the range survives.
 882                 end = self.__set[ix][1]
 883                 assert self.__set[ix][1] >= other[iy][0]
 884                 self.__set[ix][1] = other[iy][0] - 1
 885                 ix = ix + 1
 886                 if end > other[iy][1]:
 887                     # The part that extends past the subtractor may survive.
 888                     self.__set[ix:ix] = [[other[iy][1] + 1, end]]
 889                 # Retain the subtractor -- it may still kill some
 890                 # other range.
 891
 892     def add_set(self, other):
 893         """Add all IP-numbers in OTHER to this.
 894
 895         OTHER should be an ip_set object.
 896         """
 897
 898         self.add_list(other.__set)
 899
 900     def add_list(self, other):
 901         # Don't use this method directly, unless you are the test suite.
 902         ix = 0
 903         iy = 0
 904         res = []
 905         while ix < len(self.__set) or iy < len(other):
 906             # Remove the first range
 907             if ix < len(self.__set):
 908                 if iy < len(other):
 909                     if self.__set[ix][0] < other[iy][0]:
 910                         rng = self.__set[ix]
 911                         ix = ix + 1
 912                     else:
 913                         rng = other[iy]
 914                         iy = iy + 1
 915                 else:
 916                     rng = self.__set[ix]
 917                     ix = ix + 1
 918             else:
 919                 rng = other[iy]
 920                 iy = iy + 1
 921
 922             # Join this range to the list we already have collected.
 923             if len(res) == 0:
 924                 # This is the first element.
 925                 res.append(rng)
 926             elif rng[0] <= res[-1][1] + 1:
 927                 # This extends (or is consumed by) the last range.
 928                 res[-1][1] = max(res[-1][1], rng[1])
 929             else:
 930                 # There is a gap between the previous range and this one.
 931                 res.append(rng)
 932
 933         self.__set = res
 934
 935     def append(self, nwip):
 936         """Add NWIP to this.
 937
 938         NWIP should be a network object or ipaddr object.
 939         """
 940
 941         if isinstance(nwip, network):
 942             self.add_network(nwip)
 943         else:
 944             self.add_ipaddr(nwip)
 945
 946     def add_network(self, nw):
 947         """Add NW to this.
 948
 949         NW should be a network object.
 950         """
 951         self.add_list([[nw.network_intrep, nw.broadcast_intrep]])
 952
 953     def add_range(self, lo_ip, hi_ip):
 954         """Add the range of IP numbers specified by LO_IP and HI_IP to this.
 955
 956         LO_IP and HI_IP should be ipaddr objects.  They specify a
 957         range of IP numbers.  Both LO_IP and HI_IP are included in the
 958         range.
 959         """
 960
 961         assert lo_ip.intrep != None
 962         assert hi_ip.intrep != None
 963         assert lo_ip.intrep <= hi_ip.intrep
 964         self.add_list([[lo_ip.intrep, hi_ip.intrep]])
 965
 966     def add_ipaddr(self, ip):
 967         """Add IP to this.
 968
 969         IP should be an ipaddr object.
 970         """
 971
 972         assert ip.intrep != None
 973         self.add_list([[ip.intrep, ip.intrep]])
 974
 975     def complement(self):
 976         """Return everything not contained in this ip_set.
 977
 978         The return value is a new ip_set.  This is not modified.
 979         """
 980
 981         pre = -1L
 982         lst = []
 983         for [lo, hi] in self.__set:
 984             if lo != 0:
 985                 lst.append([pre+1, lo-1])
 986             pre = hi
 987         if pre < pow(2L, 32) - 1:
 988             lst.append([pre+1, pow(2L, 32) - 1])
 989         res = ip_set()
 990         res.add_list(lst)
 991         return res
 992
 993     def intersection(self, other):
 994         """Return the intersection of this and OTHER.
 995
 996         The return value is a new ip_set.  This is not modified.
 997         OTHER should be an ip_set, network or ipaddr object.
 998         """
 999
1000         res = []
1001         ix = 0
1002         iy = 0
1003         x = copy.deepcopy(self.__set)
1004
1005         if isinstance(other, ip_set):
1006             y = copy.deepcopy(other.__set)
1007         elif isinstance(other, network):
1008             y = [[other.network_intrep, other.broadcast_intrep]]
1009         elif isinstance(other, ipaddr):
1010             y = [[other.intrep, other.intrep]]
1011         else:
1012             raise BadType('expected an ip_set, network or ipaddr argument')
1013
1014         while ix < len(x) and iy < len(y):
1015             if x[ix][1] < y[iy][0]:
1016                 # The first entry on x doesn't overlap with anything on y.
1017                 ix = ix + 1
1018             elif x[ix][0] > y[iy][1]:
1019                 # The first entry on y doesn't overlap with anything on x.
1020                 iy = iy + 1
1021             else:
1022                 # Some overlap exists.
1023
1024                 # Trim away any leading edges.
1025                 if x[ix][0] < y[iy][0]:
1026                     # x starts before y
1027                     x[ix][0] = y[iy][0]
1028                 elif x[ix][0] > y[iy][0]:
1029                     # y starts before x
1030                     y[iy][0] = x[ix][0]
1031
1032                 # The ranges start at the same point (at least after
1033                 # the trimming).
1034                 if x[ix][1] == y[iy][1]:
1035                     # The ranges are equal.
1036                     res.append(x[ix])
1037                     ix = ix + 1
1038                     iy = iy + 1
1039                 elif x[ix][1] < y[iy][1]:
1040                     # x is the smaller range
1041                     res.append(x[ix])
1042                     ix = ix + 1
1043                 else:
1044                     # y is the smaller range
1045                     res.append(y[iy])
1046                     iy = iy + 1
1047
1048         result = ip_set()
1049         result.add_list(res)
1050         return result
1051
1052
1053     def as_list_of_networks(self):
1054         """Return this set as a list of networks.
1055
1056         The returned value is a list of network objects, that are
1057         created with DEMAND_FILTER.  This method may be expensive, so
1058         it should only be used when necessary.
1059         """
1060
1061         bm = []
1062         for [a, b] in self.__set:
1063
1064             lomask = 1L
1065             lobit = 1L
1066             himask = pow(2L, 32)-2
1067             bits = 32
1068             while a <= b:
1069                 if a & lomask != 0L:
1070                     bm.append((bits, a))
1071                     a = a + lobit
1072                 elif b & lomask != lomask:
1073                     bm.append((bits, b & himask))
1074                     b = b - lobit
1075                 else:
1076                     lomask = (lomask << 1) | 1
1077                     lobit = lobit << 1
1078                     himask = himask ^ lobit
1079                     bits = bits - 1
1080                     assert(bits >= 0)
1081         bm.sort()
1082         res = []
1083         for (mask, ip) in bm:
1084             res.append(network(ip, mask, DEMAND_FILTER))
1085         return res
1086
1087     def as_list_of_ranges(self):
1088         """Return the set of IP addresses as a list of ranges.
1089
1090         Each range is a list of two long numbers.  Sample return
1091         value: [[1L, 3L], [0x7f000001L, 0x7f000001L]], meaning
1092         the set 0.0.0.1, 0.0.0.2, 0.0.0.3, 127.0.0.1.
1093         """
1094
1095         # This method is currently very cheap, since this is the
1096         # current internal representation.
1097
1098         return self.__set
1099
1100     def as_str_range(self):
1101         """Return the set as a string, such as "1.2.3.4-1.2.3.8".
1102
1103         The returned value always has the form a.b.c.d-e.f.g.h.
1104         Raises SetNotRepresentable if the set cannot be represented as a
1105         single interval, or if it is the empty set.
1106         """
1107         if len(self.__set) != 1:
1108             raise SetNotRepresentable()
1109         return "%s-%s" % (intrep_to_dotted_decimal(self.__set[0][0]),
1110                           intrep_to_dotted_decimal(self.__set[0][1]))
1111
1112     def contains(self, ip):
1113         """Return true if IP is contained in the set.
1114
1115         IP should be an ipaddr object.  The empty ipaddr is never contained.
1116         """
1117
1118         if ip.intrep == None:
1119             return 0
1120
1121         for [lo, hi] in self.__set:
1122             if lo <= ip.intrep <= hi:
1123                 return 1
1124         return 0
1125
1126     def overlaps(self, nwip):
1127         """Return true if NWIP overlaps the set of IP addresses.
1128
1129         NWIP may be an ipaddr, network or ip_set object.
1130         """
1131
1132         if isinstance(nwip, ipaddr):
1133             return self.contains(nwip)
1134         elif isinstance(nwip, ip_set):
1135             # This could be optimized -- we don't really need
1136             # to compute the intersection.
1137             return not self.intersection(nwip).is_empty()
1138         elif isinstance(nwip, network):
1139             wanted_low = nwip.network_intrep
1140             wanted_high = nwip.broadcast_intrep
1141             if wanted_low == None or wanted_high == None:
1142                 return 0
1143             for [lo, hi] in self.__set:
1144                 if lo > wanted_high:
1145                     # We are past the interresting interval.
1146                     return 0
1147                 if lo >= wanted_low or hi >= wanted_low:
1148                     return 1
1149             return 0
1150         else:
1151             raise BadType('Expected an ipaddr, ip_set or network instance')
1152
1153     def is_empty(self):
1154         """Return true if this ip_set is empty.
1155         """
1156
1157         return len(self.__set) == 0
1158
1159     def any_ip(self):
1160         """Return one of the IP addresses contained in ip_set.
1161
1162         This method may only be called if the set is non-empty.  You
1163         can use the is_empty method to test for emptiness.
1164
1165         This picks an IP address from the set and returns it as an
1166         ipaddr object.  Given the same set of IP addresses, this
1167         method will always return the same IP address, but which IP
1168         address it chooses is explicitly undocumented and may change
1169         if the underlying implementation of ip_set ever changes.
1170         """
1171
1172         assert not self.is_empty()
1173         return ipaddr(self.__set[0][0])
1174
1175     def __str__(self):
1176         res = []
1177         for rng in self.__set:
1178             if rng[0] == rng[1]:
1179                 res.append(intrep_to_dotted_decimal(rng[0]))
1180             else:
1181                 res.append('%s-%s' % (intrep_to_dotted_decimal(rng[0]),
1182                                       intrep_to_dotted_decimal(rng[1])))
1183         return '<ipaddr.ip_set(%s)>' % string.join(res, ', ')
1184
1185 complete_network = network(0L, 0, DEMAND_FILTER)
1186 complete_set = ip_set(complete_network)
1187 broadcast_network = network('255.255.255.255', 32, DEMAND_FILTER)
1188 broadcast_set = ip_set(broadcast_network)
1189
1190 def compute_neighbor(intrep, bits):
1191     xor_mask = intrep_with_bit_set(bits)
1192     and_mask = bits_to_intrep(bits)
1193     return (intrep ^ xor_mask) & and_mask
1194
1195
1196 if __name__ == '__main__':
1197     # Test/demo code.  With no arguments, this will print a page
1198     # of data that can be useful when trying to interpret an
1199     # ipnumber/netmask pair.  With two arguments, it will print some
1200     # information about the IP number and netmask that was entered.
1201
1202     import sys
1203     if len(sys.argv) == 1:
1204         print "Netmasks\n========"
1205         for i in range(0, 17):
1206             if i != 16:
1207                 print '%2d' % i,
1208                 print '%-13s' % netmask(i, DEMAND_NONE).netmask_str(),
1209             else:
1210                 print ' ' * 16,
1211             print i + 16, '%-16s' % netmask(i + 16, DEMAND_NONE).netmask_str()
1212         print _("\n\nIP intervals\n============")
1213         for i in range(9):
1214             for j in range(0, 4):
1215                 print '%2d' % (8*j + i),
1216             print '%3d' % (netmask(i, DEMAND_NONE).intrep >> 24),
1217             x = 0
1218             need_break = 0
1219             if i < 8:
1220                 for j in range(0, 256, pow(2, 8-i)):
1221                     if need_break:
1222                         print
1223                         print ' ' * 15,
1224                         need_break = 0
1225                     print '%3d-%-3d' % (j, j + pow(2, 8-i)-1),
1226                     x = x + 1
1227                     if x % 8 == 0:
1228                         need_break = 1
1229             else:
1230                 print '0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13...',
1231             print
1232         sys.exit(0)
1233
1234     if len(sys.argv) != 3:
1235         sys.stderr.write(_("Usage: python ipaddr.py IP_ADDRESS NETMASK\n"))
1236         sys.exit(1)
1237     nw = network(sys.argv[1], sys.argv[2], DEMAND_NONE)
1238     print nw
1239     print "IP address:       ", nw.ip.ip_str()
1240     print "Netmask:          ", nw.mask.netmask_str(),
1241     print " (/" + nw.mask.netmask_bits_str + ")"
1242     print "Network address:  ", nw.network_str()
1243     print "Broadcast address:", nw.broadcast_str()