X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=src%2FCidr.hs;h=d772d5bcd5f469d48cda8ee396add0aba353d34a;hb=266b4e80cdde311563da66fa14f7abe6ffa7e859;hp=ac242784b98903a10145dac934dbead5b3f4f2e0;hpb=1e7731c84546a25daed6bbfb3d9c733b334667bd;p=hath.git diff --git a/src/Cidr.hs b/src/Cidr.hs index ac24278..d772d5b 100644 --- a/src/Cidr.hs +++ b/src/Cidr.hs @@ -1,18 +1,38 @@ module Cidr ( Cidr(..), - cidr_from_string + cidr_from_string, + cidr_tests, + combine_all ) where +import Data.List (nubBy) +import Test.HUnit + import IPv4Address import ListUtils +import Maskable import Maskbits import Octet data Cidr = None | Cidr { ipv4address :: IPv4Address, maskbits :: Maskbits } - deriving (Eq, Show) + deriving (Eq) + + +instance Show Cidr where + show Cidr.None = "None" + show cidr = (show (ipv4address cidr)) ++ "/" ++ (show (maskbits cidr)) + +-- Two CIDR ranges are equivalent if they have the same network bits +-- and the masks are the same. +equivalent :: Cidr -> Cidr -> Bool +equivalent Cidr.None Cidr.None = True +equivalent Cidr.None _ = False +equivalent _ Cidr.None = False +equivalent (Cidr addr1 mbits1) (Cidr addr2 mbits2) = + (mbits1 == mbits2) && ((apply_mask addr1 mbits1) == (apply_mask addr2 mbits2)) -- Returns the mask portion of a CIDR address. That is, everything -- after the trailing slash. @@ -41,3 +61,129 @@ 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 mbits1) (Cidr addr2 mbits2) + | mbits1 > mbits2 = False + | otherwise = addr1masked == addr2masked + where + addr1masked = apply_mask addr1 mbits1 + addr2masked = apply_mask addr2 mbits1 + + +contains_proper :: Cidr -> Cidr -> Bool +contains_proper cidr1 cidr2 = + (cidr1 `contains` cidr2) && (not (cidr1 == cidr2)) + + +-- A CIDR range is redundant (with respect to the given list) if +-- another CIDR range in that list properly contains it. +redundant :: [Cidr] -> Cidr -> Bool +redundant cidrlist cidr = any ((flip contains_proper) cidr) cidrlist + + +-- First, we look at all possible pairs of cidrs, and combine the +-- adjacent ones in to a new list. Then, we concatenate that list with +-- the original one, and filter out all of the redundancies. If two +-- adjacent Cidrs are combined into a larger one, they will be removed +-- in the second step since the larger Cidr must contain the smaller +-- two. +combine_all :: [Cidr] -> [Cidr] +combine_all cidrs = + combine_contained unique_cidrs + where + unique_cidrs = nubBy equivalent valid_cidr_combinations + valid_cidr_combinations = filter (/= Cidr.None) cidr_combinations + cidr_combinations = + cidrs ++ [ (combine_adjacent x y) | x <- cidrs, y <- cidrs ] + + +-- Take a list of CIDR ranges and filter out all of the ones that are +-- contained entirelt within some other range in the list. +combine_contained :: [Cidr] -> [Cidr] +combine_contained cidrs = + filter (not . (redundant cidrs)) cidrs + + +-- If the two Cidrs are not adjacent, return Cidr.None. Otherwise, +-- decrement the maskbits of cidr1 and return that; it will contain +-- both cidr1 and cidr2. +combine_adjacent :: Cidr -> Cidr -> Cidr +combine_adjacent cidr1 cidr2 + | not (adjacent cidr1 cidr2) = Cidr.None + | (maskbits cidr1 == Zero) = Cidr.None + | otherwise = cidr1 { maskbits = decrement (maskbits cidr1) } + + + +-- Determine whether or not two CIDR ranges are adjacent. If two +-- ranges lie consecutively within the IP space, they can be +-- combined. For example, 10.1.0.0/24 and 10.0.1.0/24 are adjacent, +-- and can be combined in to 10.1.0.0/23. +adjacent :: Cidr -> Cidr -> Bool +adjacent Cidr.None _ = False +adjacent _ Cidr.None = False +adjacent cidr1 cidr2 + | mbits1 /= mbits2 = False + | mbits1 == Maskbits.Zero = False -- They're equal. + | otherwise = (mbits1 == (most_sig_bit_different addr1 addr2)) + where + addr1 = ipv4address cidr1 + addr2 = ipv4address cidr2 + mbits1 = maskbits cidr1 + mbits2 = maskbits cidr2 + + + + + +-- HUnit Tests + +test_contains = + TestCase $ assertEqual "10.1.1.0/23 contains 10.1.1.0/24" (cidr1 `contains` cidr2) True + where + cidr1 = cidr_from_string "10.1.1.0/23" + cidr2 = cidr_from_string "10.1.1.0/24" + + +cidr_tests = [ test_contains ]