csit/libraries/ipaddr.py

   1 #!/usr/bin/python
   2 #
   3 # Copyright 2007 Google Inc.
   4 #  Licensed to PSF under a Contributor Agreement.
   5 #
   6 # Licensed under the Apache License, Version 2.0 (the "License");
   7 # you may not use this file except in compliance with the License.
   8 # You may obtain a copy of the License at
   9 #
  10 #      http://www.apache.org/licenses/LICENSE-2.0
  11 #
  12 # Unless required by applicable law or agreed to in writing, software
  13 # distributed under the License is distributed on an "AS IS" BASIS,
  14 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
  15 # implied. See the License for the specific language governing
  16 # permissions and limitations under the License.
  17
  18 """A fast, lightweight IPv4/IPv6 manipulation library in Python.
  19
  20 This library is used to create/poke/manipulate IPv4 and IPv6 addresses
  21 and networks.
  22
  23 """
  24
  25 import struct
  26
  27
  28 __version__ = '2.1.11'
  29
  30
  31 IPV4LENGTH = 32
  32 IPV6LENGTH = 128
  33
  34
  35 class AddressValueError(ValueError):
  36     """A Value Error related to the address."""
  37
  38
  39 class NetmaskValueError(ValueError):
  40     """A Value Error related to the netmask."""
  41
  42
  43 def IPAddress(address, version=None):
  44     """Take an IP string/int and return an object of the correct type.
  45
  46     Args:
  47         address: A string or integer, the IP address.  Either IPv4 or
  48           IPv6 addresses may be supplied; integers less than 2**32 will
  49           be considered to be IPv4 by default.
  50         version: An Integer, 4 or 6. If set, don't try to automatically
  51           determine what the IP address type is. important for things
  52           like IPAddress(1), which could be IPv4, '0.0.0.1',  or IPv6,
  53           '::1'.
  54
  55     Returns:
  56         An IPv4Address or IPv6Address object.
  57
  58     Raises:
  59         ValueError: if the string passed isn't either a v4 or a v6
  60           address.
  61
  62     """
  63     if version:
  64         if version == 4:
  65             return IPv4Address(address)
  66         elif version == 6:
  67             return IPv6Address(address)
  68
  69     try:
  70         return IPv4Address(address)
  71     except (AddressValueError, NetmaskValueError):
  72         pass
  73
  74     try:
  75         return IPv6Address(address)
  76     except (AddressValueError, NetmaskValueError):
  77         pass
  78
  79     raise ValueError('%r does not appear to be an IPv4 or IPv6 address' %
  80                      address)
  81
  82
  83 def IPNetwork(address, version=None, strict=False):
  84     """Take an IP string/int and return an object of the correct type.
  85
  86     Args:
  87         address: A string or integer, the IP address.  Either IPv4 or
  88           IPv6 addresses may be supplied; integers less than 2**32 will
  89           be considered to be IPv4 by default.
  90         version: An Integer, if set, don't try to automatically
  91           determine what the IP address type is. important for things
  92           like IPNetwork(1), which could be IPv4, '0.0.0.1/32', or IPv6,
  93           '::1/128'.
  94
  95     Returns:
  96         An IPv4Network or IPv6Network object.
  97
  98     Raises:
  99         ValueError: if the string passed isn't either a v4 or a v6
 100           address. Or if a strict network was requested and a strict
 101           network wasn't given.
 102
 103     """
 104     if version:
 105         if version == 4:
 106             return IPv4Network(address, strict)
 107         elif version == 6:
 108             return IPv6Network(address, strict)
 109
 110     try:
 111         return IPv4Network(address, strict)
 112     except (AddressValueError, NetmaskValueError):
 113         pass
 114
 115     try:
 116         return IPv6Network(address, strict)
 117     except (AddressValueError, NetmaskValueError):
 118         pass
 119
 120     raise ValueError('%r does not appear to be an IPv4 or IPv6 network' %
 121                      address)
 122
 123
 124 def v4_int_to_packed(address):
 125     """The binary representation of this address.
 126
 127     Args:
 128         address: An integer representation of an IPv4 IP address.
 129
 130     Returns:
 131         The binary representation of this address.
 132
 133     Raises:
 134         ValueError: If the integer is too large to be an IPv4 IP
 135           address.
 136     """
 137     if address > _BaseV4._ALL_ONES:
 138         raise ValueError('Address too large for IPv4')
 139     return Bytes(struct.pack('!I', address))
 140
 141
 142 def v6_int_to_packed(address):
 143     """The binary representation of this address.
 144
 145     Args:
 146         address: An integer representation of an IPv6 IP address.
 147
 148     Returns:
 149         The binary representation of this address.
 150     """
 151     return Bytes(struct.pack('!QQ', address >> 64, address & (2**64 - 1)))
 152
 153
 154 def _find_address_range(addresses):
 155     """Find a sequence of addresses.
 156
 157     Args:
 158         addresses: a list of IPv4 or IPv6 addresses.
 159
 160     Returns:
 161         A tuple containing the first and last IP addresses in the sequence.
 162
 163     """
 164     first = last = addresses[0]
 165     for ip in addresses[1:]:
 166         if ip._ip == last._ip + 1:
 167             last = ip
 168         else:
 169             break
 170     return (first, last)
 171
 172
 173 def _get_prefix_length(number1, number2, bits):
 174     """Get the number of leading bits that are same for two numbers.
 175
 176     Args:
 177         number1: an integer.
 178         number2: another integer.
 179         bits: the maximum number of bits to compare.
 180
 181     Returns:
 182         The number of leading bits that are the same for two numbers.
 183
 184     """
 185     for i in range(bits):
 186         if number1 >> i == number2 >> i:
 187             return bits - i
 188     return 0
 189
 190
 191 def _count_righthand_zero_bits(number, bits):
 192     """Count the number of zero bits on the right hand side.
 193
 194     Args:
 195         number: an integer.
 196         bits: maximum number of bits to count.
 197
 198     Returns:
 199         The number of zero bits on the right hand side of the number.
 200
 201     """
 202     if number == 0:
 203         return bits
 204     for i in range(bits):
 205         if (number >> i) % 2:
 206             return i
 207
 208
 209 def summarize_address_range(first, last):
 210     """Summarize a network range given the first and last IP addresses.
 211
 212     Example:
 213         >>> summarize_address_range(IPv4Address('1.1.1.0'),
 214             IPv4Address('1.1.1.130'))
 215         [IPv4Network('1.1.1.0/25'), IPv4Network('1.1.1.128/31'),
 216         IPv4Network('1.1.1.130/32')]
 217
 218     Args:
 219         first: the first IPv4Address or IPv6Address in the range.
 220         last: the last IPv4Address or IPv6Address in the range.
 221
 222     Returns:
 223         The address range collapsed to a list of IPv4Network's or
 224         IPv6Network's.
 225
 226     Raise:
 227         TypeError:
 228             If the first and last objects are not IP addresses.
 229             If the first and last objects are not the same version.
 230         ValueError:
 231             If the last object is not greater than the first.
 232             If the version is not 4 or 6.
 233
 234     """
 235     if not (isinstance(first, _BaseIP) and isinstance(last, _BaseIP)):
 236         raise TypeError('first and last must be IP addresses, not networks')
 237     if first.version != last.version:
 238         raise TypeError("%s and %s are not of the same version" % (
 239                         str(first), str(last)))
 240     if first > last:
 241         raise ValueError('last IP address must be greater than first')
 242
 243     networks = []
 244
 245     if first.version == 4:
 246         ip = IPv4Network
 247     elif first.version == 6:
 248         ip = IPv6Network
 249     else:
 250         raise ValueError('unknown IP version')
 251
 252     ip_bits = first._max_prefixlen
 253     first_int = first._ip
 254     last_int = last._ip
 255     while first_int <= last_int:
 256         nbits = _count_righthand_zero_bits(first_int, ip_bits)
 257         current = None
 258         while nbits >= 0:
 259             addend = 2**nbits - 1
 260             current = first_int + addend
 261             nbits -= 1
 262             if current <= last_int:
 263                 break
 264         prefix = _get_prefix_length(first_int, current, ip_bits)
 265         net = ip('%s/%d' % (str(first), prefix))
 266         networks.append(net)
 267         if current == ip._ALL_ONES:
 268             break
 269         first_int = current + 1
 270         first = IPAddress(first_int, version=first._version)
 271     return networks
 272
 273
 274 def _collapse_address_list_recursive(addresses):
 275     """Loops through the addresses, collapsing concurrent netblocks.
 276
 277     Example:
 278
 279         ip1 = IPv4Network('1.1.0.0/24')
 280         ip2 = IPv4Network('1.1.1.0/24')
 281         ip3 = IPv4Network('1.1.2.0/24')
 282         ip4 = IPv4Network('1.1.3.0/24')
 283         ip5 = IPv4Network('1.1.4.0/24')
 284         ip6 = IPv4Network('1.1.0.1/22')
 285
 286         _collapse_address_list_recursive([ip1, ip2, ip3, ip4, ip5, ip6]) ->
 287           [IPv4Network('1.1.0.0/22'), IPv4Network('1.1.4.0/24')]
 288
 289         This shouldn't be called directly; it is called via
 290           collapse_address_list([]).
 291
 292     Args:
 293         addresses: A list of IPv4Network's or IPv6Network's
 294
 295     Returns:
 296         A list of IPv4Network's or IPv6Network's depending on what we were
 297         passed.
 298
 299     """
 300     ret_array = []
 301     optimized = False
 302
 303     for cur_addr in addresses:
 304         if not ret_array:
 305             ret_array.append(cur_addr)
 306             continue
 307         if cur_addr in ret_array[-1]:
 308             optimized = True
 309         elif cur_addr == ret_array[-1].supernet().subnet()[1]:
 310             ret_array.append(ret_array.pop().supernet())
 311             optimized = True
 312         else:
 313             ret_array.append(cur_addr)
 314
 315     if optimized:
 316         return _collapse_address_list_recursive(ret_array)
 317
 318     return ret_array
 319
 320
 321 def collapse_address_list(addresses):
 322     """Collapse a list of IP objects.
 323
 324     Example:
 325         collapse_address_list([IPv4('1.1.0.0/24'), IPv4('1.1.1.0/24')]) ->
 326           [IPv4('1.1.0.0/23')]
 327
 328     Args:
 329         addresses: A list of IPv4Network or IPv6Network objects.
 330
 331     Returns:
 332         A list of IPv4Network or IPv6Network objects depending on what we
 333         were passed.
 334
 335     Raises:
 336         TypeError: If passed a list of mixed version objects.
 337
 338     """
 339     i = 0
 340     addrs = []
 341     ips = []
 342     nets = []
 343
 344     # split IP addresses and networks
 345     for ip in addresses:
 346         if isinstance(ip, _BaseIP):
 347             if ips and ips[-1]._version != ip._version:
 348                 raise TypeError("%s and %s are not of the same version" % (
 349                                 str(ip), str(ips[-1])))
 350             ips.append(ip)
 351         elif ip._prefixlen == ip._max_prefixlen:
 352             if ips and ips[-1]._version != ip._version:
 353                 raise TypeError("%s and %s are not of the same version" % (
 354                                 str(ip), str(ips[-1])))
 355             ips.append(ip.ip)
 356         else:
 357             if nets and nets[-1]._version != ip._version:
 358                 raise TypeError("%s and %s are not of the same version" % (
 359                                 str(ip), str(nets[-1])))
 360             nets.append(ip)
 361
 362     # sort and dedup
 363     ips = sorted(set(ips))
 364     nets = sorted(set(nets))
 365
 366     while i < len(ips):
 367         (first, last) = _find_address_range(ips[i:])
 368         i = ips.index(last) + 1
 369         addrs.extend(summarize_address_range(first, last))
 370
 371     return _collapse_address_list_recursive(sorted(
 372         addrs + nets, key=_BaseNet._get_networks_key))
 373
 374 # backwards compatibility
 375 CollapseAddrList = collapse_address_list
 376
 377 # We need to distinguish between the string and packed-bytes representations
 378 # of an IP address.  For example, b'0::1' is the IPv4 address 48.58.58.49,
 379 # while '0::1' is an IPv6 address.
 380 #
 381 # In Python 3, the native 'bytes' type already provides this functionality,
 382 # so we use it directly.  For earlier implementations where bytes is not a
 383 # distinct type, we create a subclass of str to serve as a tag.
 384 #
 385 # Usage example (Python 2):
 386 #   ip = ipaddr.IPAddress(ipaddr.Bytes('xxxx'))
 387 #
 388 # Usage example (Python 3):
 389 #   ip = ipaddr.IPAddress(b'xxxx')
 390 try:
 391     if bytes is str:
 392         raise TypeError("bytes is not a distinct type")
 393     Bytes = bytes
 394 except (NameError, TypeError):
 395     class Bytes(str):
 396         def __repr__(self):
 397             return 'Bytes(%s)' % str.__repr__(self)
 398
 399
 400 def get_mixed_type_key(obj):
 401     """Return a key suitable for sorting between networks and addresses.
 402
 403     Address and Network objects are not sortable by default; they're
 404     fundamentally different so the expression
 405
 406         IPv4Address('1.1.1.1') <= IPv4Network('1.1.1.1/24')
 407
 408     doesn't make any sense.  There are some times however, where you may wish
 409     to have ipaddr sort these for you anyway. If you need to do this, you
 410     can use this function as the key= argument to sorted().
 411
 412     Args:
 413       obj: either a Network or Address object.
 414     Returns:
 415       appropriate key.
 416
 417     """
 418     if isinstance(obj, _BaseNet):
 419         return obj._get_networks_key()
 420     elif isinstance(obj, _BaseIP):
 421         return obj._get_address_key()
 422     return NotImplemented
 423
 424
 425 class _IPAddrBase(object):
 426
 427     """The mother class."""
 428
 429     def __index__(self):
 430         return self._ip
 431
 432     def __int__(self):
 433         return self._ip
 434
 435     def __hex__(self):
 436         return hex(self._ip)
 437
 438     @property
 439     def exploded(self):
 440         """Return the longhand version of the IP address as a string."""
 441         return self._explode_shorthand_ip_string()
 442
 443     @property
 444     def compressed(self):
 445         """Return the shorthand version of the IP address as a string."""
 446         return str(self)
 447
 448
 449 class _BaseIP(_IPAddrBase):
 450
 451     """A generic IP object.
 452
 453     This IP class contains the version independent methods which are
 454     used by single IP addresses.
 455
 456     """
 457
 458     def __eq__(self, other):
 459         try:
 460             return (self._ip == other._ip and
 461                     self._version == other._version)
 462         except AttributeError:
 463             return NotImplemented
 464
 465     def __ne__(self, other):
 466         eq = self.__eq__(other)
 467         if eq is NotImplemented:
 468             return NotImplemented
 469         return not eq
 470
 471     def __le__(self, other):
 472         gt = self.__gt__(other)
 473         if gt is NotImplemented:
 474             return NotImplemented
 475         return not gt
 476
 477     def __ge__(self, other):
 478         lt = self.__lt__(other)
 479         if lt is NotImplemented:
 480             return NotImplemented
 481         return not lt
 482
 483     def __lt__(self, other):
 484         if self._version != other._version:
 485             raise TypeError('%s and %s are not of the same version' % (
 486                             str(self), str(other)))
 487         if not isinstance(other, _BaseIP):
 488             raise TypeError('%s and %s are not of the same type' % (
 489                             str(self), str(other)))
 490         if self._ip != other._ip:
 491             return self._ip < other._ip
 492         return False
 493
 494     def __gt__(self, other):
 495         if self._version != other._version:
 496             raise TypeError('%s and %s are not of the same version' % (
 497                             str(self), str(other)))
 498         if not isinstance(other, _BaseIP):
 499             raise TypeError('%s and %s are not of the same type' % (
 500                             str(self), str(other)))
 501         if self._ip != other._ip:
 502             return self._ip > other._ip
 503         return False
 504
 505     # Shorthand for Integer addition and subtraction. This is not
 506     # meant to ever support addition/subtraction of addresses.
 507     def __add__(self, other):
 508         if not isinstance(other, int):
 509             return NotImplemented
 510         return IPAddress(int(self) + other, version=self._version)
 511
 512     def __sub__(self, other):
 513         if not isinstance(other, int):
 514             return NotImplemented
 515         return IPAddress(int(self) - other, version=self._version)
 516
 517     def __repr__(self):
 518         return '%s(%r)' % (self.__class__.__name__, str(self))
 519
 520     def __str__(self):
 521         return '%s' % self._string_from_ip_int(self._ip)
 522
 523     def __hash__(self):
 524         return hash(hex(long(self._ip)))
 525
 526     def _get_address_key(self):
 527         return (self._version, self)
 528
 529     @property
 530     def version(self):
 531         raise NotImplementedError('BaseIP has no version')
 532
 533
 534 class _BaseNet(_IPAddrBase):
 535
 536     """A generic IP object.
 537
 538     This IP class contains the version independent methods which are
 539     used by networks.
 540
 541     """
 542
 543     def __init__(self, address):
 544         self._cache = {}
 545
 546     def __repr__(self):
 547         return '%s(%r)' % (self.__class__.__name__, str(self))
 548
 549     def iterhosts(self):
 550         """Generate Iterator over usable hosts in a network.
 551
 552            This is like __iter__ except it doesn't return the network
 553            or broadcast addresses.
 554
 555         """
 556         cur = int(self.network) + 1
 557         bcast = int(self.broadcast) - 1
 558         while cur <= bcast:
 559             cur += 1
 560             yield IPAddress(cur - 1, version=self._version)
 561
 562     def __iter__(self):
 563         cur = int(self.network)
 564         bcast = int(self.broadcast)
 565         while cur <= bcast:
 566             cur += 1
 567             yield IPAddress(cur - 1, version=self._version)
 568
 569     def __getitem__(self, n):
 570         network = int(self.network)
 571         broadcast = int(self.broadcast)
 572         if n >= 0:
 573             if network + n > broadcast:
 574                 raise IndexError
 575             return IPAddress(network + n, version=self._version)
 576         else:
 577             n += 1
 578             if broadcast + n < network:
 579                 raise IndexError
 580             return IPAddress(broadcast + n, version=self._version)
 581
 582     def __lt__(self, other):
 583         if self._version != other._version:
 584             raise TypeError('%s and %s are not of the same version' % (
 585                             str(self), str(other)))
 586         if not isinstance(other, _BaseNet):
 587             raise TypeError('%s and %s are not of the same type' % (
 588                             str(self), str(other)))
 589         if self.network != other.network:
 590             return self.network < other.network
 591         if self.netmask != other.netmask:
 592             return self.netmask < other.netmask
 593         return False
 594
 595     def __gt__(self, other):
 596         if self._version != other._version:
 597             raise TypeError('%s and %s are not of the same version' % (
 598                             str(self), str(other)))
 599         if not isinstance(other, _BaseNet):
 600             raise TypeError('%s and %s are not of the same type' % (
 601                             str(self), str(other)))
 602         if self.network != other.network:
 603             return self.network > other.network
 604         if self.netmask != other.netmask:
 605             return self.netmask > other.netmask
 606         return False
 607
 608     def __le__(self, other):
 609         gt = self.__gt__(other)
 610         if gt is NotImplemented:
 611             return NotImplemented
 612         return not gt
 613
 614     def __ge__(self, other):
 615         lt = self.__lt__(other)
 616         if lt is NotImplemented:
 617             return NotImplemented
 618         return not lt
 619
 620     def __eq__(self, other):
 621         try:
 622             return (self._version == other._version and
 623                     self.network == other.network and
 624                     int(self.netmask) == int(other.netmask))
 625         except AttributeError:
 626             if isinstance(other, _BaseIP):
 627                 return (self._version == other._version and
 628                         self._ip == other._ip)
 629
 630     def __ne__(self, other):
 631         eq = self.__eq__(other)
 632         if eq is NotImplemented:
 633             return NotImplemented
 634         return not eq
 635
 636     def __str__(self):
 637         return '%s/%s' % (str(self.ip),
 638                           str(self._prefixlen))
 639
 640     def __hash__(self):
 641         return hash(int(self.network) ^ int(self.netmask))
 642
 643     def __contains__(self, other):
 644         # always false if one is v4 and the other is v6.
 645         if self._version != other._version:
 646             return False
 647         # dealing with another network.
 648         if isinstance(other, _BaseNet):
 649             return (self.network <= other.network and
 650                     self.broadcast >= other.broadcast)
 651         # dealing with another address
 652         else:
 653             return (int(self.network) <= int(other._ip) <=
 654                     int(self.broadcast))
 655
 656     def overlaps(self, other):
 657         """Tell if self is partly contained in other."""
 658         return self.network in other or self.broadcast in other or (
 659             other.network in self or other.broadcast in self)
 660
 661     @property
 662     def network(self):
 663         x = self._cache.get('network')
 664         if x is None:
 665             x = IPAddress(self._ip & int(self.netmask), version=self._version)
 666             self._cache['network'] = x
 667         return x
 668
 669     @property
 670     def broadcast(self):
 671         x = self._cache.get('broadcast')
 672         if x is None:
 673             x = IPAddress(self._ip | int(self.hostmask), version=self._version)
 674             self._cache['broadcast'] = x
 675         return x
 676
 677     @property
 678     def hostmask(self):
 679         x = self._cache.get('hostmask')
 680         if x is None:
 681             x = IPAddress(int(self.netmask) ^ self._ALL_ONES,
 682                           version=self._version)
 683             self._cache['hostmask'] = x
 684         return x
 685
 686     @property
 687     def with_prefixlen(self):
 688         return '%s/%d' % (str(self.ip), self._prefixlen)
 689
 690     @property
 691     def with_netmask(self):
 692         return '%s/%s' % (str(self.ip), str(self.netmask))
 693
 694     @property
 695     def with_hostmask(self):
 696         return '%s/%s' % (str(self.ip), str(self.hostmask))
 697
 698     @property
 699     def numhosts(self):
 700         """Number of hosts in the current subnet."""
 701         return int(self.broadcast) - int(self.network) + 1
 702
 703     @property
 704     def version(self):
 705         raise NotImplementedError('BaseNet has no version')
 706
 707     @property
 708     def prefixlen(self):
 709         return self._prefixlen
 710
 711     def address_exclude(self, other):
 712         """Remove an address from a larger block.
 713
 714         For example:
 715
 716             addr1 = IPNetwork('10.1.1.0/24')
 717             addr2 = IPNetwork('10.1.1.0/26')
 718             addr1.address_exclude(addr2) =
 719                 [IPNetwork('10.1.1.64/26'), IPNetwork('10.1.1.128/25')]
 720
 721         or IPv6:
 722
 723             addr1 = IPNetwork('::1/32')
 724             addr2 = IPNetwork('::1/128')
 725             addr1.address_exclude(addr2) = [IPNetwork('::0/128'),
 726                 IPNetwork('::2/127'),
 727                 IPNetwork('::4/126'),
 728                 IPNetwork('::8/125'),
 729                 ...
 730                 IPNetwork('0:0:8000::/33')]
 731
 732         Args:
 733             other: An IPvXNetwork object of the same type.
 734
 735         Returns:
 736             A sorted list of IPvXNetwork objects addresses which is self
 737             minus other.
 738
 739         Raises:
 740             TypeError: If self and other are of difffering address
 741               versions, or if other is not a network object.
 742             ValueError: If other is not completely contained by self.
 743
 744         """
 745         if not self._version == other._version:
 746             raise TypeError("%s and %s are not of the same version" % (
 747                 str(self), str(other)))
 748
 749         if not isinstance(other, _BaseNet):
 750             raise TypeError("%s is not a network object" % str(other))
 751
 752         if other not in self:
 753             raise ValueError('%s not contained in %s' % (str(other),
 754                                                          str(self)))
 755         if other == self:
 756             return []
 757
 758         ret_addrs = []
 759
 760         # Make sure we're comparing the network of other.
 761         other = IPNetwork('%s/%s' % (str(other.network), str(other.prefixlen)),
 762                           version=other._version)
 763
 764         s1, s2 = self.subnet()
 765         while s1 != other and s2 != other:
 766             if other in s1:
 767                 ret_addrs.append(s2)
 768                 s1, s2 = s1.subnet()
 769             elif other in s2:
 770                 ret_addrs.append(s1)
 771                 s1, s2 = s2.subnet()
 772             else:
 773                 # If we got here, there's a bug somewhere.
 774                 assert False, ('Error performing exclusion: '
 775                                's1: %s s2: %s other: %s' %
 776                                (str(s1), str(s2), str(other)))
 777         if s1 == other:
 778             ret_addrs.append(s2)
 779         elif s2 == other:
 780             ret_addrs.append(s1)
 781         else:
 782             # If we got here, there's a bug somewhere.
 783             assert False, ('Error performing exclusion: '
 784                            's1: %s s2: %s other: %s' %
 785                            (str(s1), str(s2), str(other)))
 786
 787         return sorted(ret_addrs, key=_BaseNet._get_networks_key)
 788
 789     def compare_networks(self, other):
 790         """Compare two IP objects.
 791
 792         This is only concerned about the comparison of the integer
 793         representation of the network addresses.  This means that the
 794         host bits aren't considered at all in this method.  If you want
 795         to compare host bits, you can easily enough do a
 796         'HostA._ip < HostB._ip'
 797
 798         Args:
 799             other: An IP object.
 800
 801         Returns:
 802             If the IP versions of self and other are the same, returns:
 803
 804             -1 if self < other:
 805               eg: IPv4('1.1.1.0/24') < IPv4('1.1.2.0/24')
 806               IPv6('1080::200C:417A') < IPv6('1080::200B:417B')
 807             0 if self == other
 808               eg: IPv4('1.1.1.1/24') == IPv4('1.1.1.2/24')
 809               IPv6('1080::200C:417A/96') == IPv6('1080::200C:417B/96')
 810             1 if self > other
 811               eg: IPv4('1.1.1.0/24') > IPv4('1.1.0.0/24')
 812               IPv6('1080::1:200C:417A/112') >
 813               IPv6('1080::0:200C:417A/112')
 814
 815             If the IP versions of self and other are different, returns:
 816
 817             -1 if self._version < other._version
 818               eg: IPv4('10.0.0.1/24') < IPv6('::1/128')
 819             1 if self._version > other._version
 820               eg: IPv6('::1/128') > IPv4('255.255.255.0/24')
 821
 822         """
 823         if self._version < other._version:
 824             return -1
 825         if self._version > other._version:
 826             return 1
 827         # self._version == other._version below here:
 828         if self.network < other.network:
 829             return -1
 830         if self.network > other.network:
 831             return 1
 832         # self.network == other.network below here:
 833         if self.netmask < other.netmask:
 834             return -1
 835         if self.netmask > other.netmask:
 836             return 1
 837         # self.network == other.network and self.netmask == other.netmask
 838         return 0
 839
 840     def _get_networks_key(self):
 841         """Network-only key function.
 842
 843         Returns an object that identifies this address' network and
 844         netmask. This function is a suitable "key" argument for sorted()
 845         and list.sort().
 846
 847         """
 848         return (self._version, self.network, self.netmask)
 849
 850     def _ip_int_from_prefix(self, prefixlen):
 851         """Turn the prefix length into a bitwise netmask.
 852
 853         Args:
 854             prefixlen: An integer, the prefix length.
 855
 856         Returns:
 857             An integer.
 858
 859         """
 860         return self._ALL_ONES ^ (self._ALL_ONES >> prefixlen)
 861
 862     def _prefix_from_ip_int(self, ip_int):
 863         """Return prefix length from a bitwise netmask.
 864
 865         Args:
 866             ip_int: An integer, the netmask in expanded bitwise format.
 867
 868         Returns:
 869             An integer, the prefix length.
 870
 871         Raises:
 872             NetmaskValueError: If the input is not a valid netmask.
 873
 874         """
 875         prefixlen = self._max_prefixlen
 876         while prefixlen:
 877             if ip_int & 1:
 878                 break
 879             ip_int >>= 1
 880             prefixlen -= 1
 881
 882         if ip_int == (1 << prefixlen) - 1:
 883             return prefixlen
 884         else:
 885             raise NetmaskValueError('Bit pattern does not match /1*0*/')
 886
 887     def _prefix_from_prefix_string(self, prefixlen_str):
 888         """Turn a prefix length string into an integer.
 889
 890         Args:
 891             prefixlen_str: A decimal string containing the prefix length.
 892
 893         Returns:
 894             The prefix length as an integer.
 895
 896         Raises:
 897             NetmaskValueError: If the input is malformed or out of range.
 898
 899         """
 900         try:
 901             if not _BaseV4._DECIMAL_DIGITS.issuperset(prefixlen_str):
 902                 raise ValueError
 903             prefixlen = int(prefixlen_str)
 904             if not (0 <= prefixlen <= self._max_prefixlen):
 905                 raise ValueError
 906         except ValueError:
 907             raise NetmaskValueError('%s is not a valid prefix length' %
 908                                     prefixlen_str)
 909         return prefixlen
 910
 911     def _prefix_from_ip_string(self, ip_str):
 912         """Turn a netmask/hostmask string into a prefix length.
 913
 914         Args:
 915             ip_str: A netmask or hostmask, formatted as an IP address.
 916
 917         Returns:
 918             The prefix length as an integer.
 919
 920         Raises:
 921             NetmaskValueError: If the input is not a netmask or hostmask.
 922
 923         """
 924         # Parse the netmask/hostmask like an IP address.
 925         try:
 926             ip_int = self._ip_int_from_string(ip_str)
 927         except AddressValueError:
 928             raise NetmaskValueError('%s is not a valid netmask' % ip_str)
 929
 930         # Try matching a netmask (this would be /1*0*/ as a bitwise regexp).
 931         # Note that the two ambiguous cases (all-ones and all-zeroes) are
 932         # treated as netmasks.
 933         try:
 934             return self._prefix_from_ip_int(ip_int)
 935         except NetmaskValueError:
 936             pass
 937
 938         # Invert the bits, and try matching a /0+1+/ hostmask instead.
 939         ip_int ^= self._ALL_ONES
 940         try:
 941             return self._prefix_from_ip_int(ip_int)
 942         except NetmaskValueError:
 943             raise NetmaskValueError('%s is not a valid netmask' % ip_str)
 944
 945     def iter_subnets(self, prefixlen_diff=1, new_prefix=None):
 946         """The subnets which join to make the current subnet.
 947
 948         In the case that self contains only one IP
 949         (self._prefixlen == 32 for IPv4 or self._prefixlen == 128
 950         for IPv6), return a list with just ourself.
 951
 952         Args:
 953             prefixlen_diff: An integer, the amount the prefix length
 954               should be increased by. This should not be set if
 955               new_prefix is also set.
 956             new_prefix: The desired new prefix length. This must be a
 957               larger number (smaller prefix) than the existing prefix.
 958               This should not be set if prefixlen_diff is also set.
 959
 960         Returns:
 961             An iterator of IPv(4|6) objects.
 962
 963         Raises:
 964             ValueError: The prefixlen_diff is too small or too large.
 965                 OR
 966             prefixlen_diff and new_prefix are both set or new_prefix
 967               is a smaller number than the current prefix (smaller
 968               number means a larger network)
 969
 970         """
 971         if self._prefixlen == self._max_prefixlen:
 972             yield self
 973             return
 974
 975         if new_prefix is not None:
 976             if new_prefix < self._prefixlen:
 977                 raise ValueError('new prefix must be longer')
 978             if prefixlen_diff != 1:
 979                 raise ValueError('cannot set prefixlen_diff and new_prefix')
 980             prefixlen_diff = new_prefix - self._prefixlen
 981
 982         if prefixlen_diff < 0:
 983             raise ValueError('prefix length diff must be > 0')
 984         new_prefixlen = self._prefixlen + prefixlen_diff
 985
 986         if new_prefixlen > self._max_prefixlen:
 987             raise ValueError(
 988                 'prefix length diff %d is invalid for netblock %s' % (
 989                     new_prefixlen, str(self)))
 990
 991         first = IPNetwork('%s/%s' % (str(self.network),
 992                                      str(self._prefixlen + prefixlen_diff)),
 993                           version=self._version)
 994
 995         yield first
 996         current = first
 997         while True:
 998             broadcast = current.broadcast
 999             if broadcast == self.broadcast:
1000                 return
1001             new_addr = IPAddress(int(broadcast) + 1, version=self._version)
1002             current = IPNetwork('%s/%s' % (str(new_addr), str(new_prefixlen)),
1003                                 version=self._version)
1004
1005             yield current
1006
1007     def masked(self):
1008         """Return the network object with the host bits masked out."""
1009         return IPNetwork('%s/%d' % (self.network, self._prefixlen),
1010                          version=self._version)
1011
1012     def subnet(self, prefixlen_diff=1, new_prefix=None):
1013         """Return a list of subnets, rather than an iterator."""
1014         return list(self.iter_subnets(prefixlen_diff, new_prefix))
1015
1016     def supernet(self, prefixlen_diff=1, new_prefix=None):
1017         """The supernet containing the current network.
1018
1019         Args:
1020             prefixlen_diff: An integer, the amount the prefix length of
1021               the network should be decreased by.  For example, given a
1022               /24 network and a prefixlen_diff of 3, a supernet with a
1023               /21 netmask is returned.
1024
1025         Returns:
1026             An IPv4 network object.
1027
1028         Raises:
1029             ValueError: If self.prefixlen - prefixlen_diff < 0. I.e., you have a
1030               negative prefix length.
1031                 OR
1032             If prefixlen_diff and new_prefix are both set or new_prefix is a
1033               larger number than the current prefix (larger number means a
1034               smaller network)
1035
1036         """
1037         if self._prefixlen == 0:
1038             return self
1039
1040         if new_prefix is not None:
1041             if new_prefix > self._prefixlen:
1042                 raise ValueError('new prefix must be shorter')
1043             if prefixlen_diff != 1:
1044                 raise ValueError('cannot set prefixlen_diff and new_prefix')
1045             prefixlen_diff = self._prefixlen - new_prefix
1046
1047         if self.prefixlen - prefixlen_diff < 0:
1048             raise ValueError(
1049                 'current prefixlen is %d, cannot have a prefixlen_diff of %d' %
1050                 (self.prefixlen, prefixlen_diff))
1051         return IPNetwork('%s/%s' % (str(self.network),
1052                                     str(self.prefixlen - prefixlen_diff)),
1053                          version=self._version)
1054
1055     # backwards compatibility
1056     Subnet = subnet
1057     Supernet = supernet
1058     AddressExclude = address_exclude
1059     CompareNetworks = compare_networks
1060     Contains = __contains__
1061
1062
1063 class _BaseV4(object):
1064
1065     """Base IPv4 object.
1066
1067     The following methods are used by IPv4 objects in both single IP
1068     addresses and networks.
1069
1070     """
1071
1072     # Equivalent to 255.255.255.255 or 32 bits of 1's.
1073     _ALL_ONES = (2**IPV4LENGTH) - 1
1074     _DECIMAL_DIGITS = frozenset('0123456789')
1075
1076     def __init__(self, address):
1077         self._version = 4
1078         self._max_prefixlen = IPV4LENGTH
1079
1080     def _explode_shorthand_ip_string(self):
1081         return str(self)
1082
1083     def _ip_int_from_string(self, ip_str):
1084         """Turn the given IP string into an integer for comparison.
1085
1086         Args:
1087             ip_str: A string, the IP ip_str.
1088
1089         Returns:
1090             The IP ip_str as an integer.
1091
1092         Raises:
1093             AddressValueError: if ip_str isn't a valid IPv4 Address.
1094
1095         """
1096         octets = ip_str.split('.')
1097         if len(octets) != 4:
1098             raise AddressValueError(ip_str)
1099
1100         packed_ip = 0
1101         for oc in octets:
1102             try:
1103                 packed_ip = (packed_ip << 8) | self._parse_octet(oc)
1104             except ValueError:
1105                 raise AddressValueError(ip_str)
1106         return packed_ip
1107
1108     def _parse_octet(self, octet_str):
1109         """Convert a decimal octet into an integer.
1110
1111         Args:
1112             octet_str: A string, the number to parse.
1113
1114         Returns:
1115             The octet as an integer.
1116
1117         Raises:
1118             ValueError: if the octet isn't strictly a decimal from [0..255].
1119
1120         """
1121         # Whitelist the characters, since int() allows a lot of bizarre stuff.
1122         if not self._DECIMAL_DIGITS.issuperset(octet_str):
1123             raise ValueError
1124         octet_int = int(octet_str, 10)
1125         # Disallow leading zeroes, because no clear standard exists on
1126         # whether these should be interpreted as decimal or octal.
1127         if octet_int > 255 or (octet_str[0] == '0' and len(octet_str) > 1):
1128             raise ValueError
1129         return octet_int
1130
1131     def _string_from_ip_int(self, ip_int):
1132         """Turns a 32-bit integer into dotted decimal notation.
1133
1134         Args:
1135             ip_int: An integer, the IP address.
1136
1137         Returns:
1138             The IP address as a string in dotted decimal notation.
1139
1140         """
1141         octets = []
1142         for _ in xrange(4):
1143             octets.insert(0, str(ip_int & 0xFF))
1144             ip_int >>= 8
1145         return '.'.join(octets)
1146
1147     @property
1148     def max_prefixlen(self):
1149         return self._max_prefixlen
1150
1151     @property
1152     def packed(self):
1153         """The binary representation of this address."""
1154         return v4_int_to_packed(self._ip)
1155
1156     @property
1157     def version(self):
1158         return self._version
1159
1160     @property
1161     def is_reserved(self):
1162         """Test if the address is otherwise IETF reserved.
1163
1164         Returns:
1165             A boolean, True if the address is within the
1166             reserved IPv4 Network range.
1167
1168         """
1169         return self in IPv4Network('240.0.0.0/4')
1170
1171     @property
1172     def is_private(self):
1173         """Test if this address is allocated for private networks.
1174
1175         Returns:
1176             A boolean, True if the address is reserved per RFC 1918.
1177
1178         """
1179         return (self in IPv4Network('10.0.0.0/8') or
1180                 self in IPv4Network('172.16.0.0/12') or
1181                 self in IPv4Network('192.168.0.0/16'))
1182
1183     @property
1184     def is_multicast(self):
1185         """Test if the address is reserved for multicast use.
1186
1187         Returns:
1188             A boolean, True if the address is multicast.
1189             See RFC 3171 for details.
1190
1191         """
1192         return self in IPv4Network('224.0.0.0/4')
1193
1194     @property
1195     def is_unspecified(self):
1196         """Test if the address is unspecified.
1197
1198         Returns:
1199             A boolean, True if this is the unspecified address as defined in
1200             RFC 5735 3.
1201
1202         """
1203         return self in IPv4Network('0.0.0.0')
1204
1205     @property
1206     def is_loopback(self):
1207         """Test if the address is a loopback address.
1208
1209         Returns:
1210             A boolean, True if the address is a loopback per RFC 3330.
1211
1212         """
1213         return self in IPv4Network('127.0.0.0/8')
1214
1215     @property
1216     def is_link_local(self):
1217         """Test if the address is reserved for link-local.
1218
1219         Returns:
1220             A boolean, True if the address is link-local per RFC 3927.
1221
1222         """
1223         return self in IPv4Network('169.254.0.0/16')
1224
1225
1226 class IPv4Address(_BaseV4, _BaseIP):
1227
1228     """Represent and manipulate single IPv4 Addresses."""
1229
1230     def __init__(self, address):
1231
1232         """
1233         Args:
1234             address: A string or integer representing the IP
1235               '192.168.1.1'
1236
1237               Additionally, an integer can be passed, so
1238               IPv4Address('192.168.1.1') == IPv4Address(3232235777).
1239               or, more generally
1240               IPv4Address(int(IPv4Address('192.168.1.1'))) ==
1241                 IPv4Address('192.168.1.1')
1242
1243         Raises:
1244             AddressValueError: If ipaddr isn't a valid IPv4 address.
1245
1246         """
1247         _BaseV4.__init__(self, address)
1248
1249         # Efficient constructor from integer.
1250         if isinstance(address, (int, long)):
1251             self._ip = address
1252             if address < 0 or address > self._ALL_ONES:
1253                 raise AddressValueError(address)
1254             return
1255
1256         # Constructing from a packed address
1257         if isinstance(address, Bytes):
1258             try:
1259                 self._ip, = struct.unpack('!I', address)
1260             except struct.error:
1261                 raise AddressValueError(address)  # Wrong length.
1262             return
1263
1264         # Assume input argument to be string or any object representation
1265         # which converts into a formatted IP string.
1266         addr_str = str(address)
1267         self._ip = self._ip_int_from_string(addr_str)
1268
1269
1270 class IPv4Network(_BaseV4, _BaseNet):
1271
1272     """This class represents and manipulates 32-bit IPv4 networks.
1273
1274     Attributes: [examples for IPv4Network('1.2.3.4/27')]
1275         ._ip: 16909060
1276         .ip: IPv4Address('1.2.3.4')
1277         .network: IPv4Address('1.2.3.0')
1278         .hostmask: IPv4Address('0.0.0.31')
1279         .broadcast: IPv4Address('1.2.3.31')
1280         .netmask: IPv4Address('255.255.255.224')
1281         .prefixlen: 27
1282
1283     """
1284
1285     def __init__(self, address, strict=False):
1286         """Instantiate a new IPv4 network object.
1287
1288         Args:
1289             address: A string or integer representing the IP [& network].
1290               '192.168.1.1/24'
1291               '192.168.1.1/255.255.255.0'
1292               '192.168.1.1/0.0.0.255'
1293               are all functionally the same in IPv4. Similarly,
1294               '192.168.1.1'
1295               '192.168.1.1/255.255.255.255'
1296               '192.168.1.1/32'
1297               are also functionaly equivalent. That is to say, failing to
1298               provide a subnetmask will create an object with a mask of /32.
1299
1300               If the mask (portion after the / in the argument) is given in
1301               dotted quad form, it is treated as a netmask if it starts with a
1302               non-zero field (e.g. /255.0.0.0 == /8) and as a hostmask if it
1303               starts with a zero field (e.g. 0.255.255.255 == /8), with the
1304               single exception of an all-zero mask which is treated as a
1305               netmask == /0. If no mask is given, a default of /32 is used.
1306
1307               Additionally, an integer can be passed, so
1308               IPv4Network('192.168.1.1') == IPv4Network(3232235777).
1309               or, more generally
1310               IPv4Network(int(IPv4Network('192.168.1.1'))) ==
1311                 IPv4Network('192.168.1.1')
1312
1313             strict: A boolean. If true, ensure that we have been passed
1314               A true network address, eg, 192.168.1.0/24 and not an
1315               IP address on a network, eg, 192.168.1.1/24.
1316
1317         Raises:
1318             AddressValueError: If ipaddr isn't a valid IPv4 address.
1319             NetmaskValueError: If the netmask isn't valid for
1320               an IPv4 address.
1321             ValueError: If strict was True and a network address was not
1322               supplied.
1323
1324         """
1325         _BaseNet.__init__(self, address)
1326         _BaseV4.__init__(self, address)
1327
1328         # Constructing from an integer or packed bytes.
1329         if isinstance(address, (int, long, Bytes)):
1330             self.ip = IPv4Address(address)
1331             self._ip = self.ip._ip
1332             self._prefixlen = self._max_prefixlen
1333             self.netmask = IPv4Address(self._ALL_ONES)
1334             return
1335
1336         # Assume input argument to be string or any object representation
1337         # which converts into a formatted IP prefix string.
1338         addr = str(address).split('/')
1339
1340         if len(addr) > 2:
1341             raise AddressValueError(address)
1342
1343         self._ip = self._ip_int_from_string(addr[0])
1344         self.ip = IPv4Address(self._ip)
1345
1346         if len(addr) == 2:
1347             try:
1348                 # Check for a netmask in prefix length form.
1349                 self._prefixlen = self._prefix_from_prefix_string(addr[1])
1350             except NetmaskValueError:
1351                 # Check for a netmask or hostmask in dotted-quad form.
1352                 # This may raise NetmaskValueError.
1353                 self._prefixlen = self._prefix_from_ip_string(addr[1])
1354         else:
1355             self._prefixlen = self._max_prefixlen
1356
1357         self.netmask = IPv4Address(self._ip_int_from_prefix(self._prefixlen))
1358
1359         if strict:
1360             if self.ip != self.network:
1361                 raise ValueError('%s has host bits set' %
1362                                  self.ip)
1363         if self._prefixlen == (self._max_prefixlen - 1):
1364             self.iterhosts = self.__iter__
1365
1366     # backwards compatibility
1367     def IsRFC1918(self):
1368         return self.is_private
1369
1370     def IsMulticast(self):
1371         return self.is_multicast
1372
1373     def IsLoopback(self):
1374         return self.is_loopback
1375
1376     def IsLinkLocal(self):
1377         return self.is_link_local
1378
1379
1380 class _BaseV6(object):
1381
1382     """Base IPv6 object.
1383
1384     The following methods are used by IPv6 objects in both single IP
1385     addresses and networks.
1386
1387     """
1388
1389     _ALL_ONES = (2**IPV6LENGTH) - 1
1390     _HEXTET_COUNT = 8
1391     _HEX_DIGITS = frozenset('0123456789ABCDEFabcdef')
1392
1393     def __init__(self, address):
1394         self._version = 6
1395         self._max_prefixlen = IPV6LENGTH
1396
1397     def _ip_int_from_string(self, ip_str):
1398         """Turn an IPv6 ip_str into an integer.
1399
1400         Args:
1401             ip_str: A string, the IPv6 ip_str.
1402
1403         Returns:
1404             A long, the IPv6 ip_str.
1405
1406         Raises:
1407             AddressValueError: if ip_str isn't a valid IPv6 Address.
1408
1409         """
1410         parts = ip_str.split(':')
1411
1412         # An IPv6 address needs at least 2 colons (3 parts).
1413         if len(parts) < 3:
1414             raise AddressValueError(ip_str)
1415
1416         # If the address has an IPv4-style suffix, convert it to hexadecimal.
1417         if '.' in parts[-1]:
1418             ipv4_int = IPv4Address(parts.pop())._ip
1419             parts.append('%x' % ((ipv4_int >> 16) & 0xFFFF))
1420             parts.append('%x' % (ipv4_int & 0xFFFF))
1421
1422         # An IPv6 address can't have more than 8 colons (9 parts).
1423         if len(parts) > self._HEXTET_COUNT + 1:
1424             raise AddressValueError(ip_str)
1425
1426         # Disregarding the endpoints, find '::' with nothing in between.
1427         # This indicates that a run of zeroes has been skipped.
1428         try:
1429             skip_index, = (
1430                 [i for i in xrange(1, len(parts) - 1) if not parts[i]] or
1431                 [None])
1432         except ValueError:
1433             # Can't have more than one '::'
1434             raise AddressValueError(ip_str)
1435
1436         # parts_hi is the number of parts to copy from above/before the '::'
1437         # parts_lo is the number of parts to copy from below/after the '::'
1438         if skip_index is not None:
1439             # If we found a '::', then check if it also covers the endpoints.
1440             parts_hi = skip_index
1441             parts_lo = len(parts) - skip_index - 1
1442             if not parts[0]:
1443                 parts_hi -= 1
1444                 if parts_hi:
1445                     raise AddressValueError(ip_str)  # ^: requires ^::
1446             if not parts[-1]:
1447                 parts_lo -= 1
1448                 if parts_lo:
1449                     raise AddressValueError(ip_str)  # :$ requires ::$
1450             parts_skipped = self._HEXTET_COUNT - (parts_hi + parts_lo)
1451             if parts_skipped < 1:
1452                 raise AddressValueError(ip_str)
1453         else:
1454             # Otherwise, allocate the entire address to parts_hi.  The endpoints
1455             # could still be empty, but _parse_hextet() will check for that.
1456             if len(parts) != self._HEXTET_COUNT:
1457                 raise AddressValueError(ip_str)
1458             parts_hi = len(parts)
1459             parts_lo = 0
1460             parts_skipped = 0
1461
1462         try:
1463             # Now, parse the hextets into a 128-bit integer.
1464             ip_int = 0L
1465             for i in xrange(parts_hi):
1466                 ip_int <<= 16
1467                 ip_int |= self._parse_hextet(parts[i])
1468             ip_int <<= 16 * parts_skipped
1469             for i in xrange(-parts_lo, 0):
1470                 ip_int <<= 16
1471                 ip_int |= self._parse_hextet(parts[i])
1472             return ip_int
1473         except ValueError:
1474             raise AddressValueError(ip_str)
1475
1476     def _parse_hextet(self, hextet_str):
1477         """Convert an IPv6 hextet string into an integer.
1478
1479         Args:
1480             hextet_str: A string, the number to parse.
1481
1482         Returns:
1483             The hextet as an integer.
1484
1485         Raises:
1486             ValueError: if the input isn't strictly a hex number from [0..FFFF].
1487
1488         """
1489         # Whitelist the characters, since int() allows a lot of bizarre stuff.
1490         if not self._HEX_DIGITS.issuperset(hextet_str):
1491             raise ValueError
1492         if len(hextet_str) > 4:
1493             raise ValueError
1494         hextet_int = int(hextet_str, 16)
1495         if hextet_int > 0xFFFF:
1496             raise ValueError
1497         return hextet_int
1498
1499     def _compress_hextets(self, hextets):
1500         """Compresses a list of hextets.
1501
1502         Compresses a list of strings, replacing the longest continuous
1503         sequence of "0" in the list with "" and adding empty strings at
1504         the beginning or at the end of the string such that subsequently
1505         calling ":".join(hextets) will produce the compressed version of
1506         the IPv6 address.
1507
1508         Args:
1509             hextets: A list of strings, the hextets to compress.
1510
1511         Returns:
1512             A list of strings.
1513
1514         """
1515         best_doublecolon_start = -1
1516         best_doublecolon_len = 0
1517         doublecolon_start = -1
1518         doublecolon_len = 0
1519         for index in range(len(hextets)):
1520             if hextets[index] == '0':
1521                 doublecolon_len += 1
1522                 if doublecolon_start == -1:
1523                     # Start of a sequence of zeros.
1524                     doublecolon_start = index
1525                 if doublecolon_len > best_doublecolon_len:
1526                     # This is the longest sequence of zeros so far.
1527                     best_doublecolon_len = doublecolon_len
1528                     best_doublecolon_start = doublecolon_start
1529             else:
1530                 doublecolon_len = 0
1531                 doublecolon_start = -1
1532
1533         if best_doublecolon_len > 1:
1534             best_doublecolon_end = (best_doublecolon_start +
1535                                     best_doublecolon_len)
1536             # For zeros at the end of the address.
1537             if best_doublecolon_end == len(hextets):
1538                 hextets += ['']
1539             hextets[best_doublecolon_start:best_doublecolon_end] = ['']
1540             # For zeros at the beginning of the address.
1541             if best_doublecolon_start == 0:
1542                 hextets = [''] + hextets
1543
1544         return hextets
1545
1546     def _string_from_ip_int(self, ip_int=None):
1547         """Turns a 128-bit integer into hexadecimal notation.
1548
1549         Args:
1550             ip_int: An integer, the IP address.
1551
1552         Returns:
1553             A string, the hexadecimal representation of the address.
1554
1555         Raises:
1556             ValueError: The address is bigger than 128 bits of all ones.
1557
1558         """
1559         if not ip_int and ip_int != 0:
1560             ip_int = int(self._ip)
1561
1562         if ip_int > self._ALL_ONES:
1563             raise ValueError('IPv6 address is too large')
1564
1565         hex_str = '%032x' % ip_int
1566         hextets = []
1567         for x in range(0, 32, 4):
1568             hextets.append('%x' % int(hex_str[x:x + 4], 16))
1569
1570         hextets = self._compress_hextets(hextets)
1571         return ':'.join(hextets)
1572
1573     def _explode_shorthand_ip_string(self):
1574         """Expand a shortened IPv6 address.
1575
1576         Args:
1577             ip_str: A string, the IPv6 address.
1578
1579         Returns:
1580             A string, the expanded IPv6 address.
1581
1582         """
1583         if isinstance(self, _BaseNet):
1584             ip_str = str(self.ip)
1585         else:
1586             ip_str = str(self)
1587
1588         ip_int = self._ip_int_from_string(ip_str)
1589         parts = []
1590         for i in xrange(self._HEXTET_COUNT):
1591             parts.append('%04x' % (ip_int & 0xFFFF))
1592             ip_int >>= 16
1593         parts.reverse()
1594         if isinstance(self, _BaseNet):
1595             return '%s/%d' % (':'.join(parts), self.prefixlen)
1596         return ':'.join(parts)
1597
1598     @property
1599     def max_prefixlen(self):
1600         return self._max_prefixlen
1601
1602     @property
1603     def packed(self):
1604         """The binary representation of this address."""
1605         return v6_int_to_packed(self._ip)
1606
1607     @property
1608     def version(self):
1609         return self._version
1610
1611     @property
1612     def is_multicast(self):
1613         """Test if the address is reserved for multicast use.
1614
1615         Returns:
1616             A boolean, True if the address is a multicast address.
1617             See RFC 2373 2.7 for details.
1618
1619         """
1620         return self in IPv6Network('ff00::/8')
1621
1622     @property
1623     def is_reserved(self):
1624         """Test if the address is otherwise IETF reserved.
1625
1626         Returns:
1627             A boolean, True if the address is within one of the
1628             reserved IPv6 Network ranges.
1629
1630         """
1631         return (self in IPv6Network('::/8') or
1632                 self in IPv6Network('100::/8') or
1633                 self in IPv6Network('200::/7') or
1634                 self in IPv6Network('400::/6') or
1635                 self in IPv6Network('800::/5') or
1636                 self in IPv6Network('1000::/4') or
1637                 self in IPv6Network('4000::/3') or
1638                 self in IPv6Network('6000::/3') or
1639                 self in IPv6Network('8000::/3') or
1640                 self in IPv6Network('A000::/3') or
1641                 self in IPv6Network('C000::/3') or
1642                 self in IPv6Network('E000::/4') or
1643                 self in IPv6Network('F000::/5') or
1644                 self in IPv6Network('F800::/6') or
1645                 self in IPv6Network('FE00::/9'))
1646
1647     @property
1648     def is_unspecified(self):
1649         """Test if the address is unspecified.
1650
1651         Returns:
1652             A boolean, True if this is the unspecified address as defined in
1653             RFC 2373 2.5.2.
1654
1655         """
1656         return self._ip == 0 and getattr(self, '_prefixlen', 128) == 128
1657
1658     @property
1659     def is_loopback(self):
1660         """Test if the address is a loopback address.
1661
1662         Returns:
1663             A boolean, True if the address is a loopback address as defined in
1664             RFC 2373 2.5.3.
1665
1666         """
1667         return self._ip == 1 and getattr(self, '_prefixlen', 128) == 128
1668
1669     @property
1670     def is_link_local(self):
1671         """Test if the address is reserved for link-local.
1672
1673         Returns:
1674             A boolean, True if the address is reserved per RFC 4291.
1675
1676         """
1677         return self in IPv6Network('fe80::/10')
1678
1679     @property
1680     def is_site_local(self):
1681         """Test if the address is reserved for site-local.
1682
1683         Note that the site-local address space has been deprecated by RFC 3879.
1684         Use is_private to test if this address is in the space of unique local
1685         addresses as defined by RFC 4193.
1686
1687         Returns:
1688             A boolean, True if the address is reserved per RFC 3513 2.5.6.
1689
1690         """
1691         return self in IPv6Network('fec0::/10')
1692
1693     @property
1694     def is_private(self):
1695         """Test if this address is allocated for private networks.
1696
1697         Returns:
1698             A boolean, True if the address is reserved per RFC 4193.
1699
1700         """
1701         return self in IPv6Network('fc00::/7')
1702
1703     @property
1704     def ipv4_mapped(self):
1705         """Return the IPv4 mapped address.
1706
1707         Returns:
1708             If the IPv6 address is a v4 mapped address, return the
1709             IPv4 mapped address. Return None otherwise.
1710
1711         """
1712         if (self._ip >> 32) != 0xFFFF:
1713             return None
1714         return IPv4Address(self._ip & 0xFFFFFFFF)
1715
1716     @property
1717     def teredo(self):
1718         """Tuple of embedded teredo IPs.
1719
1720         Returns:
1721             Tuple of the (server, client) IPs or None if the address
1722             doesn't appear to be a teredo address (doesn't start with
1723             2001::/32)
1724
1725         """
1726         if (self._ip >> 96) != 0x20010000:
1727             return None
1728         return (IPv4Address((self._ip >> 64) & 0xFFFFFFFF),
1729                 IPv4Address(~self._ip & 0xFFFFFFFF))
1730
1731     @property
1732     def sixtofour(self):
1733         """Return the IPv4 6to4 embedded address.
1734
1735         Returns:
1736             The IPv4 6to4-embedded address if present or None if the
1737             address doesn't appear to contain a 6to4 embedded address.
1738
1739         """
1740         if (self._ip >> 112) != 0x2002:
1741             return None
1742         return IPv4Address((self._ip >> 80) & 0xFFFFFFFF)
1743
1744
1745 class IPv6Address(_BaseV6, _BaseIP):
1746
1747     """Represent and manipulate single IPv6 Addresses.
1748     """
1749
1750     def __init__(self, address):
1751         """Instantiate a new IPv6 address object.
1752
1753         Args:
1754             address: A string or integer representing the IP
1755
1756               Additionally, an integer can be passed, so
1757               IPv6Address('2001:4860::') ==
1758                 IPv6Address(42541956101370907050197289607612071936L).
1759               or, more generally
1760               IPv6Address(IPv6Address('2001:4860::')._ip) ==
1761                 IPv6Address('2001:4860::')
1762
1763         Raises:
1764             AddressValueError: If address isn't a valid IPv6 address.
1765
1766         """
1767         _BaseV6.__init__(self, address)
1768
1769         # Efficient constructor from integer.
1770         if isinstance(address, (int, long)):
1771             self._ip = address
1772             if address < 0 or address > self._ALL_ONES:
1773                 raise AddressValueError(address)
1774             return
1775
1776         # Constructing from a packed address
1777         if isinstance(address, Bytes):
1778             try:
1779                 hi, lo = struct.unpack('!QQ', address)
1780             except struct.error:
1781                 raise AddressValueError(address)  # Wrong length.
1782             self._ip = (hi << 64) | lo
1783             return
1784
1785         # Assume input argument to be string or any object representation
1786         # which converts into a formatted IP string.
1787         addr_str = str(address)
1788         if not addr_str:
1789             raise AddressValueError('')
1790
1791         self._ip = self._ip_int_from_string(addr_str)
1792
1793
1794 class IPv6Network(_BaseV6, _BaseNet):
1795
1796     """This class represents and manipulates 128-bit IPv6 networks.
1797
1798     Attributes: [examples for IPv6('2001:658:22A:CAFE:200::1/64')]
1799         .ip: IPv6Address('2001:658:22a:cafe:200::1')
1800         .network: IPv6Address('2001:658:22a:cafe::')
1801         .hostmask: IPv6Address('::ffff:ffff:ffff:ffff')
1802         .broadcast: IPv6Address('2001:658:22a:cafe:ffff:ffff:ffff:ffff')
1803         .netmask: IPv6Address('ffff:ffff:ffff:ffff::')
1804         .prefixlen: 64
1805
1806     """
1807
1808     def __init__(self, address, strict=False):
1809         """Instantiate a new IPv6 Network object.
1810
1811         Args:
1812             address: A string or integer representing the IPv6 network or the IP
1813               and prefix/netmask.
1814               '2001:4860::/128'
1815               '2001:4860:0000:0000:0000:0000:0000:0000/128'
1816               '2001:4860::'
1817               are all functionally the same in IPv6.  That is to say,
1818               failing to provide a subnetmask will create an object with
1819               a mask of /128.
1820
1821               Additionally, an integer can be passed, so
1822               IPv6Network('2001:4860::') ==
1823                 IPv6Network(42541956101370907050197289607612071936L).
1824               or, more generally
1825               IPv6Network(IPv6Network('2001:4860::')._ip) ==
1826                 IPv6Network('2001:4860::')
1827
1828             strict: A boolean. If true, ensure that we have been passed
1829               A true network address, eg, 192.168.1.0/24 and not an
1830               IP address on a network, eg, 192.168.1.1/24.
1831
1832         Raises:
1833             AddressValueError: If address isn't a valid IPv6 address.
1834             NetmaskValueError: If the netmask isn't valid for
1835               an IPv6 address.
1836             ValueError: If strict was True and a network address was not
1837               supplied.
1838
1839         """
1840         _BaseNet.__init__(self, address)
1841         _BaseV6.__init__(self, address)
1842
1843         # Constructing from an integer or packed bytes.
1844         if isinstance(address, (int, long, Bytes)):
1845             self.ip = IPv6Address(address)
1846             self._ip = self.ip._ip
1847             self._prefixlen = self._max_prefixlen
1848             self.netmask = IPv6Address(self._ALL_ONES)
1849             return
1850
1851         # Assume input argument to be string or any object representation
1852         # which converts into a formatted IP prefix string.
1853         addr = str(address).split('/')
1854
1855         if len(addr) > 2:
1856             raise AddressValueError(address)
1857
1858         self._ip = self._ip_int_from_string(addr[0])
1859         self.ip = IPv6Address(self._ip)
1860
1861         if len(addr) == 2:
1862             # This may raise NetmaskValueError
1863             self._prefixlen = self._prefix_from_prefix_string(addr[1])
1864         else:
1865             self._prefixlen = self._max_prefixlen
1866
1867         self.netmask = IPv6Address(self._ip_int_from_prefix(self._prefixlen))
1868
1869         if strict:
1870             if self.ip != self.network:
1871                 raise ValueError('%s has host bits set' %
1872                                  self.ip)
1873         if self._prefixlen == (self._max_prefixlen - 1):
1874             self.iterhosts = self.__iter__
1875
1876     @property
1877     def with_netmask(self):
1878         return self.with_prefixlen