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
 375 # backwards compatibility
 376 CollapseAddrList = collapse_address_list
 377
 378 # We need to distinguish between the string and packed-bytes representations
 379 # of an IP address.  For example, b'0::1' is the IPv4 address 48.58.58.49,
 380 # while '0::1' is an IPv6 address.
 381 #
 382 # In Python 3, the native 'bytes' type already provides this functionality,
 383 # so we use it directly.  For earlier implementations where bytes is not a
 384 # distinct type, we create a subclass of str to serve as a tag.
 385 #
 386 # Usage example (Python 2):
 387 #   ip = ipaddr.IPAddress(ipaddr.Bytes('xxxx'))
 388 #
 389 # Usage example (Python 3):
 390 #   ip = ipaddr.IPAddress(b'xxxx')
 391 try:
 392     if bytes is str:
 393         raise TypeError("bytes is not a distinct type")
 394     Bytes = bytes
 395 except (NameError, TypeError):
 396     class Bytes(str):
 397         def __repr__(self):
 398             return 'Bytes(%s)' % str.__repr__(self)
 399
 400
 401 def get_mixed_type_key(obj):
 402     """Return a key suitable for sorting between networks and addresses.
 403
 404     Address and Network objects are not sortable by default; they're
 405     fundamentally different so the expression
 406
 407         IPv4Address('1.1.1.1') <= IPv4Network('1.1.1.1/24')
 408
 409     doesn't make any sense.  There are some times however, where you may wish
 410     to have ipaddr sort these for you anyway. If you need to do this, you
 411     can use this function as the key= argument to sorted().
 412
 413     Args:
 414       obj: either a Network or Address object.
 415     Returns:
 416       appropriate key.
 417
 418     """
 419     if isinstance(obj, _BaseNet):
 420         return obj._get_networks_key()
 421     elif isinstance(obj, _BaseIP):
 422         return obj._get_address_key()
 423     return NotImplemented
 424
 425
 426 class _IPAddrBase(object):
 427
 428     """The mother class."""
 429
 430     def __index__(self):
 431         return self._ip
 432
 433     def __int__(self):
 434         return self._ip
 435
 436     def __hex__(self):
 437         return hex(self._ip)
 438
 439     @property
 440     def exploded(self):
 441         """Return the longhand version of the IP address as a string."""
 442         return self._explode_shorthand_ip_string()
 443
 444     @property
 445     def compressed(self):
 446         """Return the shorthand version of the IP address as a string."""
 447         return str(self)
 448
 449
 450 class _BaseIP(_IPAddrBase):
 451
 452     """A generic IP object.
 453
 454     This IP class contains the version independent methods which are
 455     used by single IP addresses.
 456
 457     """
 458
 459     def __eq__(self, other):
 460         try:
 461             return (self._ip == other._ip and
 462                     self._version == other._version)
 463         except AttributeError:
 464             return NotImplemented
 465
 466     def __ne__(self, other):
 467         eq = self.__eq__(other)
 468         if eq is NotImplemented:
 469             return NotImplemented
 470         return not eq
 471
 472     def __le__(self, other):
 473         gt = self.__gt__(other)
 474         if gt is NotImplemented:
 475             return NotImplemented
 476         return not gt
 477
 478     def __ge__(self, other):
 479         lt = self.__lt__(other)
 480         if lt is NotImplemented:
 481             return NotImplemented
 482         return not lt
 483
 484     def __lt__(self, other):
 485         if self._version != other._version:
 486             raise TypeError('%s and %s are not of the same version' % (
 487                             str(self), str(other)))
 488         if not isinstance(other, _BaseIP):
 489             raise TypeError('%s and %s are not of the same type' % (
 490                             str(self), str(other)))
 491         if self._ip != other._ip:
 492             return self._ip < other._ip
 493         return False
 494
 495     def __gt__(self, other):
 496         if self._version != other._version:
 497             raise TypeError('%s and %s are not of the same version' % (
 498                             str(self), str(other)))
 499         if not isinstance(other, _BaseIP):
 500             raise TypeError('%s and %s are not of the same type' % (
 501                             str(self), str(other)))
 502         if self._ip != other._ip:
 503             return self._ip > other._ip
 504         return False
 505
 506     # Shorthand for Integer addition and subtraction. This is not
 507     # meant to ever support addition/subtraction of addresses.
 508     def __add__(self, other):
 509         if not isinstance(other, int):
 510             return NotImplemented
 511         return IPAddress(int(self) + other, version=self._version)
 512
 513     def __sub__(self, other):
 514         if not isinstance(other, int):
 515             return NotImplemented
 516         return IPAddress(int(self) - other, version=self._version)
 517
 518     def __repr__(self):
 519         return '%s(%r)' % (self.__class__.__name__, str(self))
 520
 521     def __str__(self):
 522         return '%s' % self._string_from_ip_int(self._ip)
 523
 524     def __hash__(self):
 525         return hash(hex(long(self._ip)))
 526
 527     def _get_address_key(self):
 528         return (self._version, self)
 529
 530     @property
 531     def version(self):
 532         raise NotImplementedError('BaseIP has no version')
 533
 534
 535 class _BaseNet(_IPAddrBase):
 536
 537     """A generic IP object.
 538
 539     This IP class contains the version independent methods which are
 540     used by networks.
 541
 542     """
 543
 544     def __init__(self, address):
 545         self._cache = {}
 546
 547     def __repr__(self):
 548         return '%s(%r)' % (self.__class__.__name__, str(self))
 549
 550     def iterhosts(self):
 551         """Generate Iterator over usable hosts in a network.
 552
 553            This is like __iter__ except it doesn't return the network
 554            or broadcast addresses.
 555
 556         """
 557         cur = int(self.network) + 1
 558         bcast = int(self.broadcast) - 1
 559         while cur <= bcast:
 560             cur += 1
 561             yield IPAddress(cur - 1, version=self._version)
 562
 563     def __iter__(self):
 564         cur = int(self.network)
 565         bcast = int(self.broadcast)
 566         while cur <= bcast:
 567             cur += 1
 568             yield IPAddress(cur - 1, version=self._version)
 569
 570     def __getitem__(self, n):
 571         network = int(self.network)
 572         broadcast = int(self.broadcast)
 573         if n >= 0:
 574             if network + n > broadcast:
 575                 raise IndexError
 576             return IPAddress(network + n, version=self._version)
 577         else:
 578             n += 1
 579             if broadcast + n < network:
 580                 raise IndexError
 581             return IPAddress(broadcast + n, version=self._version)
 582
 583     def __lt__(self, other):
 584         if self._version != other._version:
 585             raise TypeError('%s and %s are not of the same version' % (
 586                             str(self), str(other)))
 587         if not isinstance(other, _BaseNet):
 588             raise TypeError('%s and %s are not of the same type' % (
 589                             str(self), str(other)))
 590         if self.network != other.network:
 591             return self.network < other.network
 592         if self.netmask != other.netmask:
 593             return self.netmask < other.netmask
 594         return False
 595
 596     def __gt__(self, other):
 597         if self._version != other._version:
 598             raise TypeError('%s and %s are not of the same version' % (
 599                             str(self), str(other)))
 600         if not isinstance(other, _BaseNet):
 601             raise TypeError('%s and %s are not of the same type' % (
 602                             str(self), str(other)))
 603         if self.network != other.network:
 604             return self.network > other.network
 605         if self.netmask != other.netmask:
 606             return self.netmask > other.netmask
 607         return False
 608
 609     def __le__(self, other):
 610         gt = self.__gt__(other)
 611         if gt is NotImplemented:
 612             return NotImplemented
 613         return not gt
 614
 615     def __ge__(self, other):
 616         lt = self.__lt__(other)
 617         if lt is NotImplemented:
 618             return NotImplemented
 619         return not lt
 620
 621     def __eq__(self, other):
 622         try:
 623             return (self._version == other._version and
 624                     self.network == other.network and
 625                     int(self.netmask) == int(other.netmask))
 626         except AttributeError:
 627             if isinstance(other, _BaseIP):
 628                 return (self._version == other._version and
 629                         self._ip == other._ip)
 630
 631     def __ne__(self, other):
 632         eq = self.__eq__(other)
 633         if eq is NotImplemented:
 634             return NotImplemented
 635         return not eq
 636
 637     def __str__(self):
 638         return '%s/%s' % (str(self.ip),
 639                           str(self._prefixlen))
 640
 641     def __hash__(self):
 642         return hash(int(self.network) ^ int(self.netmask))
 643
 644     def __contains__(self, other):
 645         # always false if one is v4 and the other is v6.
 646         if self._version != other._version:
 647             return False
 648         # dealing with another network.
 649         if isinstance(other, _BaseNet):
 650             return (self.network <= other.network and
 651                     self.broadcast >= other.broadcast)
 652         # dealing with another address
 653         else:
 654             return (int(self.network) <= int(other._ip) <=
 655                     int(self.broadcast))
 656
 657     def overlaps(self, other):
 658         """Tell if self is partly contained in other."""
 659         return self.network in other or self.broadcast in other or (
 660             other.network in self or other.broadcast in self)
 661
 662     @property
 663     def network(self):
 664         x = self._cache.get('network')
 665         if x is None:
 666             x = IPAddress(self._ip & int(self.netmask), version=self._version)
 667             self._cache['network'] = x
 668         return x
 669
 670     @property
 671     def broadcast(self):
 672         x = self._cache.get('broadcast')
 673         if x is None:
 674             x = IPAddress(self._ip | int(self.hostmask), version=self._version)
 675             self._cache['broadcast'] = x
 676         return x
 677
 678     @property
 679     def hostmask(self):
 680         x = self._cache.get('hostmask')
 681         if x is None:
 682             x = IPAddress(int(self.netmask) ^ self._ALL_ONES,
 683                           version=self._version)
 684             self._cache['hostmask'] = x
 685         return x
 686
 687     @property
 688     def with_prefixlen(self):
 689         return '%s/%d' % (str(self.ip), self._prefixlen)
 690
 691     @property
 692     def with_netmask(self):
 693         return '%s/%s' % (str(self.ip), str(self.netmask))
 694
 695     @property
 696     def with_hostmask(self):
 697         return '%s/%s' % (str(self.ip), str(self.hostmask))
 698
 699     @property
 700     def numhosts(self):
 701         """Number of hosts in the current subnet."""
 702         return int(self.broadcast) - int(self.network) + 1
 703
 704     @property
 705     def version(self):
 706         raise NotImplementedError('BaseNet has no version')
 707
 708     @property
 709     def prefixlen(self):
 710         return self._prefixlen
 711
 712     def address_exclude(self, other):
 713         """Remove an address from a larger block.
 714
 715         For example:
 716
 717             addr1 = IPNetwork('10.1.1.0/24')
 718             addr2 = IPNetwork('10.1.1.0/26')
 719             addr1.address_exclude(addr2) =
 720                 [IPNetwork('10.1.1.64/26'), IPNetwork('10.1.1.128/25')]
 721
 722         or IPv6:
 723
 724             addr1 = IPNetwork('::1/32')
 725             addr2 = IPNetwork('::1/128')
 726             addr1.address_exclude(addr2) = [IPNetwork('::0/128'),
 727                 IPNetwork('::2/127'),
 728                 IPNetwork('::4/126'),
 729                 IPNetwork('::8/125'),
 730                 ...
 731                 IPNetwork('0:0:8000::/33')]
 732
 733         Args:
 734             other: An IPvXNetwork object of the same type.
 735
 736         Returns:
 737             A sorted list of IPvXNetwork objects addresses which is self
 738             minus other.
 739
 740         Raises:
 741             TypeError: If self and other are of difffering address
 742               versions, or if other is not a network object.
 743             ValueError: If other is not completely contained by self.
 744
 745         """
 746         if not self._version == other._version:
 747             raise TypeError("%s and %s are not of the same version" % (
 748                 str(self), str(other)))
 749
 750         if not isinstance(other, _BaseNet):
 751             raise TypeError("%s is not a network object" % str(other))
 752
 753         if other not in self:
 754             raise ValueError('%s not contained in %s' % (str(other),
 755                                                          str(self)))
 756         if other == self:
 757             return []
 758
 759         ret_addrs = []
 760
 761         # Make sure we're comparing the network of other.
 762         other = IPNetwork('%s/%s' % (str(other.network), str(other.prefixlen)),
 763                           version=other._version)
 764
 765         s1, s2 = self.subnet()
 766         while s1 != other and s2 != other:
 767             if other in s1:
 768                 ret_addrs.append(s2)
 769                 s1, s2 = s1.subnet()
 770             elif other in s2:
 771                 ret_addrs.append(s1)
 772                 s1, s2 = s2.subnet()
 773             else:
 774                 # If we got here, there's a bug somewhere.
 775                 assert False, ('Error performing exclusion: '
 776                                's1: %s s2: %s other: %s' %
 777                                (str(s1), str(s2), str(other)))
 778         if s1 == other:
 779             ret_addrs.append(s2)
 780         elif s2 == other:
 781             ret_addrs.append(s1)
 782         else:
 783             # If we got here, there's a bug somewhere.
 784             assert False, ('Error performing exclusion: '
 785                            's1: %s s2: %s other: %s' %
 786                            (str(s1), str(s2), str(other)))
 787
 788         return sorted(ret_addrs, key=_BaseNet._get_networks_key)
 789
 790     def compare_networks(self, other):
 791         """Compare two IP objects.
 792
 793         This is only concerned about the comparison of the integer
 794         representation of the network addresses.  This means that the
 795         host bits aren't considered at all in this method.  If you want
 796         to compare host bits, you can easily enough do a
 797         'HostA._ip < HostB._ip'
 798
 799         Args:
 800             other: An IP object.
 801
 802         Returns:
 803             If the IP versions of self and other are the same, returns:
 804
 805             -1 if self < other:
 806               eg: IPv4('1.1.1.0/24') < IPv4('1.1.2.0/24')
 807               IPv6('1080::200C:417A') < IPv6('1080::200B:417B')
 808             0 if self == other
 809               eg: IPv4('1.1.1.1/24') == IPv4('1.1.1.2/24')
 810               IPv6('1080::200C:417A/96') == IPv6('1080::200C:417B/96')
 811             1 if self > other
 812               eg: IPv4('1.1.1.0/24') > IPv4('1.1.0.0/24')
 813               IPv6('1080::1:200C:417A/112') >
 814               IPv6('1080::0:200C:417A/112')
 815
 816             If the IP versions of self and other are different, returns:
 817
 818             -1 if self._version < other._version
 819               eg: IPv4('10.0.0.1/24') < IPv6('::1/128')
 820             1 if self._version > other._version
 821               eg: IPv6('::1/128') > IPv4('255.255.255.0/24')
 822
 823         """
 824         if self._version < other._version:
 825             return -1
 826         if self._version > other._version:
 827             return 1
 828         # self._version == other._version below here:
 829         if self.network < other.network:
 830             return -1
 831         if self.network > other.network:
 832             return 1
 833         # self.network == other.network below here:
 834         if self.netmask < other.netmask:
 835             return -1
 836         if self.netmask > other.netmask:
 837             return 1
 838         # self.network == other.network and self.netmask == other.netmask
 839         return 0
 840
 841     def _get_networks_key(self):
 842         """Network-only key function.
 843
 844         Returns an object that identifies this address' network and
 845         netmask. This function is a suitable "key" argument for sorted()
 846         and list.sort().
 847
 848         """
 849         return (self._version, self.network, self.netmask)
 850
 851     def _ip_int_from_prefix(self, prefixlen):
 852         """Turn the prefix length into a bitwise netmask.
 853
 854         Args:
 855             prefixlen: An integer, the prefix length.
 856
 857         Returns:
 858             An integer.
 859
 860         """
 861         return self._ALL_ONES ^ (self._ALL_ONES >> prefixlen)
 862
 863     def _prefix_from_ip_int(self, ip_int):
 864         """Return prefix length from a bitwise netmask.
 865
 866         Args:
 867             ip_int: An integer, the netmask in expanded bitwise format.
 868
 869         Returns:
 870             An integer, the prefix length.
 871
 872         Raises:
 873             NetmaskValueError: If the input is not a valid netmask.
 874
 875         """
 876         prefixlen = self._max_prefixlen
 877         while prefixlen:
 878             if ip_int & 1:
 879                 break
 880             ip_int >>= 1
 881             prefixlen -= 1
 882
 883         if ip_int == (1 << prefixlen) - 1:
 884             return prefixlen
 885         else:
 886             raise NetmaskValueError('Bit pattern does not match /1*0*/')
 887
 888     def _prefix_from_prefix_string(self, prefixlen_str):
 889         """Turn a prefix length string into an integer.
 890
 891         Args:
 892             prefixlen_str: A decimal string containing the prefix length.
 893
 894         Returns:
 895             The prefix length as an integer.
 896
 897         Raises:
 898             NetmaskValueError: If the input is malformed or out of range.
 899
 900         """
 901         try:
 902             if not _BaseV4._DECIMAL_DIGITS.issuperset(prefixlen_str):
 903                 raise ValueError
 904             prefixlen = int(prefixlen_str)
 905             if not (0 <= prefixlen <= self._max_prefixlen):
 906                 raise ValueError
 907         except ValueError:
 908             raise NetmaskValueError('%s is not a valid prefix length' %
 909                                     prefixlen_str)
 910         return prefixlen
 911
 912     def _prefix_from_ip_string(self, ip_str):
 913         """Turn a netmask/hostmask string into a prefix length.
 914
 915         Args:
 916             ip_str: A netmask or hostmask, formatted as an IP address.
 917
 918         Returns:
 919             The prefix length as an integer.
 920
 921         Raises:
 922             NetmaskValueError: If the input is not a netmask or hostmask.
 923
 924         """
 925         # Parse the netmask/hostmask like an IP address.
 926         try:
 927             ip_int = self._ip_int_from_string(ip_str)
 928         except AddressValueError:
 929             raise NetmaskValueError('%s is not a valid netmask' % ip_str)
 930
 931         # Try matching a netmask (this would be /1*0*/ as a bitwise regexp).
 932         # Note that the two ambiguous cases (all-ones and all-zeroes) are
 933         # treated as netmasks.
 934         try:
 935             return self._prefix_from_ip_int(ip_int)
 936         except NetmaskValueError:
 937             pass
 938
 939         # Invert the bits, and try matching a /0+1+/ hostmask instead.
 940         ip_int ^= self._ALL_ONES
 941         try:
 942             return self._prefix_from_ip_int(ip_int)
 943         except NetmaskValueError:
 944             raise NetmaskValueError('%s is not a valid netmask' % ip_str)
 945
 946     def iter_subnets(self, prefixlen_diff=1, new_prefix=None):
 947         """The subnets which join to make the current subnet.
 948
 949         In the case that self contains only one IP
 950         (self._prefixlen == 32 for IPv4 or self._prefixlen == 128
 951         for IPv6), return a list with just ourself.
 952
 953         Args:
 954             prefixlen_diff: An integer, the amount the prefix length
 955               should be increased by. This should not be set if
 956               new_prefix is also set.
 957             new_prefix: The desired new prefix length. This must be a
 958               larger number (smaller prefix) than the existing prefix.
 959               This should not be set if prefixlen_diff is also set.
 960
 961         Returns:
 962             An iterator of IPv(4|6) objects.
 963
 964         Raises:
 965             ValueError: The prefixlen_diff is too small or too large.
 966                 OR
 967             prefixlen_diff and new_prefix are both set or new_prefix
 968               is a smaller number than the current prefix (smaller
 969               number means a larger network)
 970
 971         """
 972         if self._prefixlen == self._max_prefixlen:
 973             yield self
 974             return
 975
 976         if new_prefix is not None:
 977             if new_prefix < self._prefixlen:
 978                 raise ValueError('new prefix must be longer')
 979             if prefixlen_diff != 1:
 980                 raise ValueError('cannot set prefixlen_diff and new_prefix')
 981             prefixlen_diff = new_prefix - self._prefixlen
 982
 983         if prefixlen_diff < 0:
 984             raise ValueError('prefix length diff must be > 0')
 985         new_prefixlen = self._prefixlen + prefixlen_diff
 986
 987         if new_prefixlen > self._max_prefixlen:
 988             raise ValueError(
 989                 'prefix length diff %d is invalid for netblock %s' % (
 990                     new_prefixlen, str(self)))
 991
 992         first = IPNetwork('%s/%s' % (str(self.network),
 993                                      str(self._prefixlen + prefixlen_diff)),
 994                           version=self._version)
 995
 996         yield first
 997         current = first
 998         while True:
 999             broadcast = current.broadcast
1000             if broadcast == self.broadcast:
1001                 return
1002             new_addr = IPAddress(int(broadcast) + 1, version=self._version)
1003             current = IPNetwork('%s/%s' % (str(new_addr), str(new_prefixlen)),
1004                                 version=self._version)
1005
1006             yield current
1007
1008     def masked(self):
1009         """Return the network object with the host bits masked out."""
1010         return IPNetwork('%s/%d' % (self.network, self._prefixlen),
1011                          version=self._version)
1012
1013     def subnet(self, prefixlen_diff=1, new_prefix=None):
1014         """Return a list of subnets, rather than an iterator."""
1015         return list(self.iter_subnets(prefixlen_diff, new_prefix))
1016
1017     def supernet(self, prefixlen_diff=1, new_prefix=None):
1018         """The supernet containing the current network.
1019
1020         Args:
1021             prefixlen_diff: An integer, the amount the prefix length of
1022               the network should be decreased by.  For example, given a
1023               /24 network and a prefixlen_diff of 3, a supernet with a
1024               /21 netmask is returned.
1025
1026         Returns:
1027             An IPv4 network object.
1028
1029         Raises:
1030             ValueError: If self.prefixlen - prefixlen_diff < 0. I.e., you have a
1031               negative prefix length.
1032                 OR
1033             If prefixlen_diff and new_prefix are both set or new_prefix is a
1034               larger number than the current prefix (larger number means a
1035               smaller network)
1036
1037         """
1038         if self._prefixlen == 0:
1039             return self
1040
1041         if new_prefix is not None:
1042             if new_prefix > self._prefixlen:
1043                 raise ValueError('new prefix must be shorter')
1044             if prefixlen_diff != 1:
1045                 raise ValueError('cannot set prefixlen_diff and new_prefix')
1046             prefixlen_diff = self._prefixlen - new_prefix
1047
1048         if self.prefixlen - prefixlen_diff < 0:
1049             raise ValueError(
1050                 'current prefixlen is %d, cannot have a prefixlen_diff of %d' %
1051                 (self.prefixlen, prefixlen_diff))
1052         return IPNetwork('%s/%s' % (str(self.network),
1053                                     str(self.prefixlen - prefixlen_diff)),
1054                          version=self._version)
1055
1056     # backwards compatibility
1057     Subnet = subnet
1058     Supernet = supernet
1059     AddressExclude = address_exclude
1060     CompareNetworks = compare_networks
1061     Contains = __contains__
1062
1063
1064 class _BaseV4(object):
1065
1066     """Base IPv4 object.
1067
1068     The following methods are used by IPv4 objects in both single IP
1069     addresses and networks.
1070
1071     """
1072
1073     # Equivalent to 255.255.255.255 or 32 bits of 1's.
1074     _ALL_ONES = (2**IPV4LENGTH) - 1
1075     _DECIMAL_DIGITS = frozenset('0123456789')
1076
1077     def __init__(self, address):
1078         self._version = 4
1079         self._max_prefixlen = IPV4LENGTH
1080
1081     def _explode_shorthand_ip_string(self):
1082         return str(self)
1083
1084     def _ip_int_from_string(self, ip_str):
1085         """Turn the given IP string into an integer for comparison.
1086
1087         Args:
1088             ip_str: A string, the IP ip_str.
1089
1090         Returns:
1091             The IP ip_str as an integer.
1092
1093         Raises:
1094             AddressValueError: if ip_str isn't a valid IPv4 Address.
1095
1096         """
1097         octets = ip_str.split('.')
1098         if len(octets) != 4:
1099             raise AddressValueError(ip_str)
1100
1101         packed_ip = 0
1102         for oc in octets:
1103             try:
1104                 packed_ip = (packed_ip << 8) | self._parse_octet(oc)
1105             except ValueError:
1106                 raise AddressValueError(ip_str)
1107         return packed_ip
1108
1109     def _parse_octet(self, octet_str):
1110         """Convert a decimal octet into an integer.
1111
1112         Args:
1113             octet_str: A string, the number to parse.
1114
1115         Returns:
1116             The octet as an integer.
1117
1118         Raises:
1119             ValueError: if the octet isn't strictly a decimal from [0..255].
1120
1121         """
1122         # Whitelist the characters, since int() allows a lot of bizarre stuff.
1123         if not self._DECIMAL_DIGITS.issuperset(octet_str):
1124             raise ValueError
1125         octet_int = int(octet_str, 10)
1126         # Disallow leading zeroes, because no clear standard exists on
1127         # whether these should be interpreted as decimal or octal.
1128         if octet_int > 255 or (octet_str[0] == '0' and len(octet_str) > 1):
1129             raise ValueError
1130         return octet_int
1131
1132     def _string_from_ip_int(self, ip_int):
1133         """Turns a 32-bit integer into dotted decimal notation.
1134
1135         Args:
1136             ip_int: An integer, the IP address.
1137
1138         Returns:
1139             The IP address as a string in dotted decimal notation.
1140
1141         """
1142         octets = []
1143         for _ in xrange(4):
1144             octets.insert(0, str(ip_int & 0xFF))
1145             ip_int >>= 8
1146         return '.'.join(octets)
1147
1148     @property
1149     def max_prefixlen(self):
1150         return self._max_prefixlen
1151
1152     @property
1153     def packed(self):
1154         """The binary representation of this address."""
1155         return v4_int_to_packed(self._ip)
1156
1157     @property
1158     def version(self):
1159         return self._version
1160
1161     @property
1162     def is_reserved(self):
1163         """Test if the address is otherwise IETF reserved.
1164
1165         Returns:
1166             A boolean, True if the address is within the
1167             reserved IPv4 Network range.
1168
1169         """
1170         return self in IPv4Network('240.0.0.0/4')
1171
1172     @property
1173     def is_private(self):
1174         """Test if this address is allocated for private networks.
1175
1176         Returns:
1177             A boolean, True if the address is reserved per RFC 1918.
1178
1179         """
1180         return (self in IPv4Network('10.0.0.0/8') or
1181                 self in IPv4Network('172.16.0.0/12') or
1182                 self in IPv4Network('192.168.0.0/16'))
1183
1184     @property
1185     def is_multicast(self):
1186         """Test if the address is reserved for multicast use.
1187
1188         Returns:
1189             A boolean, True if the address is multicast.
1190             See RFC 3171 for details.
1191
1192         """
1193         return self in IPv4Network('224.0.0.0/4')
1194
1195     @property
1196     def is_unspecified(self):
1197         """Test if the address is unspecified.
1198
1199         Returns:
1200             A boolean, True if this is the unspecified address as defined in
1201             RFC 5735 3.
1202
1203         """
1204         return self in IPv4Network('0.0.0.0')
1205
1206     @property
1207     def is_loopback(self):
1208         """Test if the address is a loopback address.
1209
1210         Returns:
1211             A boolean, True if the address is a loopback per RFC 3330.
1212
1213         """
1214         return self in IPv4Network('127.0.0.0/8')
1215
1216     @property
1217     def is_link_local(self):
1218         """Test if the address is reserved for link-local.
1219
1220         Returns:
1221             A boolean, True if the address is link-local per RFC 3927.
1222
1223         """
1224         return self in IPv4Network('169.254.0.0/16')
1225
1226
1227 class IPv4Address(_BaseV4, _BaseIP):
1228
1229     """Represent and manipulate single IPv4 Addresses."""
1230
1231     def __init__(self, address):
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