Added a new Maskable typeclass with instances Octet and IPv4Address.

Export octet[1-4] from IPv4Address.
Implemented a new 'contains' function for Cidrs using the Maskable class' apply_mask function.

diff --git a/src/Cidr.hs b/src/Cidr.hs
index ac242784b98903a10145dac934dbead5b3f4f2e0..ab1ef51cce7af37bb5e3bdbec269a512ca59976f 100644 (file)
--- a/src/Cidr.hs
+++ b/src/Cidr.hs
@@ -1,10 +1,12 @@
 module Cidr
 ( Cidr(..),
-  cidr_from_string
+  cidr_from_string,
+  contains
 ) where
 
 import IPv4Address
 import ListUtils
+import Maskable
 import Maskbits
 import Octet
 
@@ -41,3 +43,51 @@ cidr_from_string s
                  oct4 = (octs !! 3)
                  octs  = octets_from_cidr_string s
                  mbits = maskbits_from_cidr_string s
+
+
+
+-- Return true if the first argument (a CIDR range) contains the
+-- second (another CIDR range). There are a lot of ways we can be fed
+-- junk here. For lack of a better alternative, just return False when
+-- we are given nonsense.
+contains :: Cidr -> Cidr -> Bool
+contains Cidr.None _ = False
+contains _ Cidr.None = False
+contains (Cidr _ Maskbits.None) _    = False
+contains (Cidr IPv4Address.None _) _ = False
+contains _ (Cidr _ Maskbits.None)    = False
+contains _ (Cidr IPv4Address.None _) = False
+
+-- If the number of bits in the network part of the first address is
+-- larger than the number of bits in the second, there is no way that
+-- the first range can contain the second. For, if the number of
+-- network bits is larger, then the number of host bits must be
+-- smaller, and if cidr1 has fewer hosts than cidr2, cidr1 most
+-- certainly does not contain cidr2.
+--
+-- On the other hand, if the first argument (cidr1) has fewer (or the
+-- same number of) network bits as the second, it can contain the
+-- second. In this case, we need to check that every host in cidr2 is
+-- contained in cidr1. If a host in cidr2 is contained in cidr1, then
+-- at least mbits1 of an address in cidr2 will match cidr1. For
+-- example,
+--
+-- cidr1 = 192.168.1.0/23, cidr2 = 192.168.1.100/24
+--
+-- Here, cidr2 contains all of 192.168.1.0 through
+-- 192.168.1.255. However, cidr1 contains BOTH 192.168.0.0 through
+-- 192.168.0.255 and 192.168.1.0 through 192.168.1.255. In essence,
+-- what we want to check is that cidr2 "begins with" something that
+-- cidr1 CAN begin with. Since cidr1 can begin with 192.168.1, and
+-- cidr2 DOES, cidr1 contains cidr2..
+--
+-- The way that we check this is to apply cidr1's mask to cidr2's
+-- address and see if the result is the same as cidr1's mask applied
+-- to cidr1's address.
+--
+contains (Cidr addr1 (Maskbits mbits1)) (Cidr addr2 (Maskbits mbits2))
+    | mbits1 > mbits2 = False
+    | otherwise = addr1masked == addr2masked
+    where
+      addr1masked = apply_mask addr1 (Maskbits mbits1)
+      addr2masked = apply_mask addr2 (Maskbits mbits1)

diff --git a/src/IPv4Address.hs b/src/IPv4Address.hs
index 037698a0eafc8c9ba88b95c08f669a045d38fa91..01bf36e63126ef51ebb8aae4aec301a8db97c43b 100644 (file)
--- a/src/IPv4Address.hs
+++ b/src/IPv4Address.hs
@@ -8,7 +8,11 @@ module IPv4Address
   min_octet1,
   min_octet2,
   min_octet3,
-  min_octet4
+  min_octet4,
+  octet1,
+  octet2,
+  octet3,
+  octet4
 )
   where
 

diff --git a/src/Maskable.hs b/src/Maskable.hs
new file mode 100644 (file)
index 0000000..a0f0764
--- /dev/null
+++ b/src/Maskable.hs
@@ -0,0 +1,79 @@
+module Maskable where
+
+import Bit
+import IPv4Address
+import Maskbits
+import Octet
+
+-- Any string of bits should be maskable by some number of netmask
+-- bits. The convention of the Maskable typeclass follows CIDR
+-- notation, where the number of mask bits (the number after the
+-- slash) denotes how many bits are reserved for the network.
+--
+-- So, a mask of 32 applied to an address of 127.0.0.1 will again
+-- return 127.0.0.1. Likewise, 31 mask bits applied to 127.0.0.1
+-- should return 127.0.0.0, since 127.0.0.1/31 matches both 127.0.0.0
+-- and 127.0.0.1. In this case, the final '0' or '1' is the host
+-- part of the address. The '127.0.0' is thus the network part.
+class Maskable a where
+    apply_mask :: a -> Maskbits -> a
+
+
+instance Maskable Octet where
+    apply_mask _ Maskbits.None = Octet.None
+    apply_mask oct (Maskbits maskbits)
+        | maskbits == 8 = oct
+        | maskbits == 7 = oct { b8 = Zero }
+        | maskbits == 6 = oct { b8 = Zero, b7 = Zero }
+        | maskbits == 5 = oct { b8 = Zero, b7 = Zero, b6 = Zero }
+        | maskbits == 4 = oct { b8 = Zero, b7 = Zero, b6 = Zero, b5 = Zero }
+        | maskbits == 3 = oct { b8 = Zero, b7 = Zero, b6 = Zero, b5 = Zero, b4 = Zero }
+        | maskbits == 2 = oct { b8 = Zero, b7 = Zero, b6 = Zero, b5 = Zero, b4 = Zero, b3 = Zero }
+        | maskbits == 1 = oct { b8 = Zero, b7 = Zero, b6 = Zero, b5 = Zero, b4 = Zero, b3 = Zero, b2 = Zero }
+        | maskbits == 0 = min_octet
+        | otherwise = Octet.None
+
+
+
+instance Maskable IPv4Address where
+    apply_mask _ Maskbits.None = IPv4Address.None
+    apply_mask addr (Maskbits mask)
+        | mask == 32 = ipv4address_from_octets oct1 oct2 oct3 oct4
+        | mask == 31 = ipv4address_from_octets oct1 oct2 oct3 (apply_mask oct4 (Maskbits 1))
+        | mask == 30 = ipv4address_from_octets oct1 oct2 oct3 (apply_mask oct4 (Maskbits 2))
+        | mask == 29 = ipv4address_from_octets oct1 oct2 oct3 (apply_mask oct4 (Maskbits 3))
+        | mask == 28 = ipv4address_from_octets oct1 oct2 oct3 (apply_mask oct4 (Maskbits 4))
+        | mask == 27 = ipv4address_from_octets oct1 oct2 oct3 (apply_mask oct4 (Maskbits 5))
+        | mask == 26 = ipv4address_from_octets oct1 oct2 oct3 (apply_mask oct4 (Maskbits 6))
+        | mask == 25 = ipv4address_from_octets oct1 oct2 oct3 (apply_mask oct4 (Maskbits 7))
+        | mask == 24 = ipv4address_from_octets oct1 oct2 oct3 (min_octet)
+        | mask == 23 = ipv4address_from_octets oct1 oct2 (apply_mask oct3 (Maskbits 1)) (min_octet)
+        | mask == 22 = ipv4address_from_octets oct1 oct2 (apply_mask oct3 (Maskbits 2)) (min_octet)
+        | mask == 21 = ipv4address_from_octets oct1 oct2 (apply_mask oct3 (Maskbits 3)) (min_octet)
+        | mask == 20 = ipv4address_from_octets oct1 oct2 (apply_mask oct3 (Maskbits 4)) (min_octet)
+        | mask == 19 = ipv4address_from_octets oct1 oct2 (apply_mask oct3 (Maskbits 5)) (min_octet)
+        | mask == 18 = ipv4address_from_octets oct1 oct2 (apply_mask oct3 (Maskbits 6)) (min_octet)
+        | mask == 17 = ipv4address_from_octets oct1 oct2 (apply_mask oct3 (Maskbits 7)) (min_octet)
+        | mask == 16 = ipv4address_from_octets oct1 oct2 (min_octet) (min_octet)
+        | mask == 15 = ipv4address_from_octets oct1 (apply_mask oct2 (Maskbits 1)) (min_octet) (min_octet)
+        | mask == 14 = ipv4address_from_octets oct1 (apply_mask oct2 (Maskbits 2)) (min_octet) (min_octet)
+        | mask == 13 = ipv4address_from_octets oct1 (apply_mask oct2 (Maskbits 3)) (min_octet) (min_octet)
+        | mask == 12 = ipv4address_from_octets oct1 (apply_mask oct2 (Maskbits 4)) (min_octet) (min_octet)
+        | mask == 11 = ipv4address_from_octets oct1 (apply_mask oct2 (Maskbits 5)) (min_octet) (min_octet)
+        | mask == 10 = ipv4address_from_octets oct1 (apply_mask oct2 (Maskbits 6)) (min_octet) (min_octet)
+        | mask == 9 = ipv4address_from_octets oct1 (apply_mask oct2 (Maskbits 7)) (min_octet) (min_octet)
+        | mask == 8 = ipv4address_from_octets oct1 (min_octet) (min_octet) (min_octet)
+        | mask == 7 = ipv4address_from_octets (apply_mask oct1 (Maskbits 1)) (min_octet) (min_octet) (min_octet)
+        | mask == 6 = ipv4address_from_octets (apply_mask oct1 (Maskbits 2)) (min_octet) (min_octet) (min_octet)
+        | mask == 5 = ipv4address_from_octets (apply_mask oct1 (Maskbits 3)) (min_octet) (min_octet) (min_octet)
+        | mask == 4 =  ipv4address_from_octets (apply_mask oct1 (Maskbits 4)) (min_octet) (min_octet) (min_octet)
+        | mask == 3 = ipv4address_from_octets (apply_mask oct1 (Maskbits 5)) (min_octet) (min_octet) (min_octet)
+        | mask == 2 = ipv4address_from_octets (apply_mask oct1 (Maskbits 6)) (min_octet) (min_octet) (min_octet)
+        | mask == 1 = ipv4address_from_octets (apply_mask oct1 (Maskbits 7)) (min_octet) (min_octet) (min_octet)
+        | mask == 0 = ipv4address_from_octets (min_octet) (min_octet) (min_octet) (min_octet)
+        | otherwise = IPv4Address.None
+        where
+          oct1 = (octet1 addr)
+          oct2 = (octet2 addr)
+          oct3 = (octet3 addr)
+          oct4 = (octet4 addr)