ipaddr.py

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