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