src/Cidr.hs

   1 module Cidr
   2 ( Cidr(..),
   3   cidr_from_string,
   4   combine_all
   5 ) where
   6
   7 import IPv4Address
   8 import ListUtils
   9 import Maskable
  10 import Maskbits
  11 import Octet
  12
  13
  14 data Cidr = None | Cidr { ipv4address :: IPv4Address,
  15                           maskbits :: Maskbits }
  16             deriving (Eq)
  17
  18
  19 instance Show Cidr where
  20     show Cidr.None = "None"
  21     show cidr = (show (ipv4address cidr)) ++ "/" ++ (show (maskbits cidr))
  22
  23
  24 -- Returns the mask portion of a CIDR address. That is, everything
  25 -- after the trailing slash.
  26 maskbits_from_cidr_string :: String -> Maskbits
  27 maskbits_from_cidr_string s =
  28     maskbits_from_string ((splitWith (`elem` "/") s) !! 1)
  29
  30
  31 -- Takes an IP address String in CIDR notation, and returns a list of
  32 -- its octets (as Ints).
  33 octets_from_cidr_string :: String -> [Octet]
  34 octets_from_cidr_string s =
  35     map octet_from_string (take 4 (splitWith (`elem` "./") s))
  36
  37
  38 cidr_from_string :: String -> Cidr
  39 cidr_from_string s
  40     | addr  == IPv4Address.None = Cidr.None
  41     | mbits == Maskbits.None    = Cidr.None
  42     | otherwise = Cidr addr mbits
  43                where
  44                  addr = ipv4address_from_octets (oct1) (oct2) (oct3) (oct4)
  45                  oct1 = (octs !! 0)
  46                  oct2 = (octs !! 1)
  47                  oct3 = (octs !! 2)
  48                  oct4 = (octs !! 3)
  49                  octs  = octets_from_cidr_string s
  50                  mbits = maskbits_from_cidr_string s
  51
  52
  53
  54 -- Return true if the first argument (a CIDR range) contains the
  55 -- second (another CIDR range). There are a lot of ways we can be fed
  56 -- junk here. For lack of a better alternative, just return False when
  57 -- we are given nonsense.
  58 contains :: Cidr -> Cidr -> Bool
  59 contains Cidr.None _ = False
  60 contains _ Cidr.None = False
  61 contains (Cidr _ Maskbits.None) _    = False
  62 contains (Cidr IPv4Address.None _) _ = False
  63 contains _ (Cidr _ Maskbits.None)    = False
  64 contains _ (Cidr IPv4Address.None _) = False
  65
  66 -- If the number of bits in the network part of the first address is
  67 -- larger than the number of bits in the second, there is no way that
  68 -- the first range can contain the second. For, if the number of
  69 -- network bits is larger, then the number of host bits must be
  70 -- smaller, and if cidr1 has fewer hosts than cidr2, cidr1 most
  71 -- certainly does not contain cidr2.
  72 --
  73 -- On the other hand, if the first argument (cidr1) has fewer (or the
  74 -- same number of) network bits as the second, it can contain the
  75 -- second. In this case, we need to check that every host in cidr2 is
  76 -- contained in cidr1. If a host in cidr2 is contained in cidr1, then
  77 -- at least mbits1 of an address in cidr2 will match cidr1. For
  78 -- example,
  79 --
  80 -- cidr1 = 192.168.1.0/23, cidr2 = 192.168.1.100/24
  81 --
  82 -- Here, cidr2 contains all of 192.168.1.0 through
  83 -- 192.168.1.255. However, cidr1 contains BOTH 192.168.0.0 through
  84 -- 192.168.0.255 and 192.168.1.0 through 192.168.1.255. In essence,
  85 -- what we want to check is that cidr2 "begins with" something that
  86 -- cidr1 CAN begin with. Since cidr1 can begin with 192.168.1, and
  87 -- cidr2 DOES, cidr1 contains cidr2..
  88 --
  89 -- The way that we check this is to apply cidr1's mask to cidr2's
  90 -- address and see if the result is the same as cidr1's mask applied
  91 -- to cidr1's address.
  92 --
  93 contains (Cidr addr1 mbits1) (Cidr addr2 mbits2)
  94     | mbits1 > mbits2 = False
  95     | otherwise = addr1masked == addr2masked
  96     where
  97       addr1masked = apply_mask addr1 mbits1
  98       addr2masked = apply_mask addr2 mbits1
  99
 100
 101 contains_proper :: Cidr -> Cidr -> Bool
 102 contains_proper cidr1 cidr2 =
 103     (cidr1 `contains` cidr2) && (not (cidr1 == cidr2))
 104
 105
 106 -- A CIDR range is redundant (with respect to the given list) if
 107 -- another CIDR range in that list properly contains it.
 108 redundant :: [Cidr] -> Cidr -> Bool
 109 redundant cidrlist cidr = any ((flip contains_proper) cidr) cidrlist
 110
 111
 112 -- We want to get rid of all the Cidrs that are properly contained
 113 -- in some other Cidr.
 114 combine_all :: [Cidr] -> [Cidr]
 115 combine_all cidrs =
 116     filter (not . (redundant cidrs)) cidrs
 117
 118
 119 -- Determine whether or not two CIDR ranges are adjacent. If two
 120 -- ranges lie consecutively within the IP space, they can be
 121 -- combined. For example, 10.1.0.0/24 and 10.0.1.0/24 are adjacent,
 122 -- and can be combined in to 10.1.0.0/23.
 123 adjacent :: Cidr -> Cidr -> Bool
 124 adjacent Cidr.None _ = False
 125 adjacent _ Cidr.None = False
 126 adjacent cidr1 cidr2
 127   | mbits1 /= mbits2 = False
 128   | mbits1 == Maskbits.Zero = False -- They're equal.
 129   | otherwise = (mbits1 == (most_sig_bit_different addr1 addr2))
 130   where
 131     addr1 = ipv4address cidr1
 132     addr2 = ipv4address cidr2
 133     mbits1 = maskbits cidr1
 134     mbits2 = maskbits cidr2