Task

Implement a function or program that, given a range of IPv4 addresses in CIDR notation (dotted-decimal/network-bits), will return/output the same range in canonical form.

That is, the IP address portion of the output CIDR block must not contain any set (1) bits in the host part of the address.



Example

Given   87.70.141.1/22,   your code should output   87.70.140.0/22



Explanation

An Internet Protocol version 4 address is a 32-bit value, conventionally represented as a number in base 256 using dotted-decimal notation, where each base-256 "digit" is represented by the digit value in decimal and the digits are separated by periods. Logically, this 32-bit value represents two components: the leftmost (most-significant) bits determine the "network" portion of the address, while the rightmost (least-significant) bits determine the "host" portion. Classless Internet Domain Routing block notation indicates where the boundary between these two components is for a given address by adding a slash followed by the number of bits in the network portion.

In general, CIDR blocks stand in for the entire set of IP addresses sharing the same "network" component; it's common to see access control lists specify a single IP address using CIDR with /32 to indicate that only the one address is included. Often, the tools using this notation expect the address to be entered in canonical form, in which the "host" bits are all zeroes in the binary representation. But careless network admins may provide CIDR blocks without canonicalizing them first. This task handles the canonicalization.

The example address, 87.70.141.1, translates into 01010111010001101000110100000001 in binary notation zero-padded to 32 bits. The /22 means that the first 22 of those bits determine the match; the final 10 bits should be 0. But they instead include two 1 bits: 0100000001. So to canonicalize the address, change those 1's to 0's to yield 01010111010001101000110000000000, which in dotted-decimal is 87.70.140.0.



More examples for testing
        36.18.154.103/12    →  36.16.0.0/12
        62.62.197.11/29     →  62.62.197.8/29
        67.137.119.181/4    →  64.0.0.0/4
        161.214.74.21/24    →  161.214.74.0/24
        184.232.176.184/18  →  184.232.128.0/18



import Control.Monad (guard)
import Data.Bits ((.|.), (.&.), complement, shiftL, shiftR, zeroBits)
import Data.Maybe (listToMaybe)
import Data.Word (Word32, Word8)
import Text.ParserCombinators.ReadP (ReadP, char, readP_to_S)
import Text.Printf (printf)
import Text.Read.Lex (readDecP)
 
-- A 32-bit IPv4 address, with a netmask applied, and the number of leading bits
-- that are in the network portion of the address.
data CIDR = CIDR Word32 Word8
 
-- Convert a string to a CIDR, or nothing if it's invalid.
cidrRead :: String -> Maybe CIDR
cidrRead = listToMaybe . map fst . readP_to_S cidrP
 
-- Convert the CIDR to a string.
cidrShow :: CIDR -> String
cidrShow (CIDR addr n) = let (a, b, c, d) = octetsFrom addr
                         in printf "%u.%u.%u.%u/%u" a b c d n
 
-- Parser for the string representation of a CIDR.  For a successful parse the
-- string must have the form a.b.c.d/n, where each of a, b, c and d are decimal
-- numbers in the range [0, 255] and n is a decimal number in the range [0, 32].
cidrP :: ReadP CIDR
cidrP = do a <- octetP <* char '.'
           b <- octetP <* char '.'
           c <- octetP <* char '.'
           d <- octetP <* char '/'
           n <- netBitsP
           return $ CIDR (addrFrom a b c d .&. netmask n) n
  where octetP   = wordP 255
        netBitsP = wordP  32
 
-- Parser for a decimal string, whose value is in the range [0, lim].
-- 
-- We want the limit argument to be an Integer, so that we can detect values
-- that are too large, rather than having them silently wrap.
wordP :: Integral a => Integer -> ReadP a
wordP lim = do n <- readDecP
               guard $ n <= lim
               return $ fi n
 
-- The octets of an IPv4 address.
octetsFrom :: Word32 -> (Word8, Word8, Word8, Word8)
octetsFrom addr = (oct addr 3, oct addr 2, oct addr 1, oct addr 0)
  where oct w n = fi $ w `shiftR` (8*n) .&. 0xff
 
-- An IPv4 address from four octets.  `ipAddr4 1 2 3 4' is the address 1.2.3.4.
addrFrom :: Word8 -> Word8 -> Word8 -> Word8 -> Word32
addrFrom a b c d = 0 <<+ a <<+ b <<+ c <<+ d
  where w <<+ o = w `shiftL` 8 .|. fi o
 
-- The value `netmask n' is the netmask whose leftmost n bits are 1, and the
-- remainder are 0.
netmask :: Word8 -> Word32
netmask n = complement $ complement zeroBits `shiftR` fi n
 
fi :: (Integral a, Num b) => a -> b
fi = fromIntegral
 
test :: String -> IO ()
test str = do
  let cidrStr = maybe "invalid CIDR string" cidrShow (cidrRead str)
  printf "%-18s -> %s\n" str cidrStr
 
main :: IO ()
main = do
  test "87.70.141.1/22"
  test "36.18.154.103/12"
  test "62.62.197.11/29"
  test "67.137.119.181/4"
  test "161.214.74.21/24"
  test "184.232.176.184/18"
 
  test "184.256.176.184/12" -- octet value is too large
  test "184.232.176.184/33" -- netmask size is too large
  test "184.232.184/18"     -- too few components