Canonicalize CIDR: Difference between revisions
(→{{header|Wren}}: Changed to cope with the extra examples.) |
m (→{{header|Wren}}: Removed an unnecessary space.) |
||
Line 551:
"62.62.197.11/29",
"67.137.119.181/4",
"161.214.74.21/24"
"184.232.176.184/18"
]
|
Revision as of 08:06, 15 July 2020
You are encouraged to solve this task according to the task description, using any language you may know.
- 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
C
This solution uses only the standard library. On POSIX platforms one can use the functions inet_pton/inet_ntop to parse/format IPv4 addresses. <lang c>#include <stdbool.h>
- include <stdio.h>
- include <stdint.h>
typedef struct cidr_tag {
uint32_t address; unsigned int mask_length;
} cidr_t;
// Convert a string in CIDR format to an IPv4 address and netmask, // if possible. Also performs CIDR canonicalization. bool cidr_parse(const char* str, cidr_t* cidr) {
int a, b, c, d, m; if (sscanf(str, "%d.%d.%d.%d/%d", &a, &b, &c, &d, &m) != 5) return false; if (m < 1 || m > 32 || a < 0 || a > UINT8_MAX || b < 0 || b > UINT8_MAX || c < 0 || c > UINT8_MAX || d < 0 || d > UINT8_MAX) return false; uint32_t mask = ~((1 << (32 - m)) - 1); uint32_t address = (a << 24) + (b << 16) + (c << 8) + d; address &= mask; cidr->address = address; cidr->mask_length = m; return true;
}
// Write a string in CIDR notation into the supplied buffer. void cidr_format(const cidr_t* cidr, char* str, size_t size) {
uint32_t address = cidr->address; unsigned int d = address & UINT8_MAX; address >>= 8; unsigned int c = address & UINT8_MAX; address >>= 8; unsigned int b = address & UINT8_MAX; address >>= 8; unsigned int a = address & UINT8_MAX; snprintf(str, size, "%u.%u.%u.%u/%u", a, b, c, d, cidr->mask_length);
}
int main(int argc, char** argv) {
for (int i = 1; i < argc; ++i) { cidr_t cidr; if (cidr_parse(argv[i], &cidr)) { char out[32]; cidr_format(&cidr, out, sizeof(out)); puts(out); } else { fprintf(stderr, "%s: invalid CIDR\n", argv[i]); } } return 0;
}</lang>
- Output:
$ ./canonicalize_cidr 87.70.141.1/22 87.70.140.0/22
C++
<lang cpp>#include <cstdint>
- include <iomanip>
- include <iostream>
- include <sstream>
// Class representing an IPv4 address + netmask length class ipv4_cidr { public:
ipv4_cidr() {} ipv4_cidr(std::uint32_t address, unsigned int mask_length) : address_(address), mask_length_(mask_length) {} std::uint32_t address() const { return address_; } unsigned int mask_length() const { return mask_length_; } friend std::istream& operator>>(std::istream&, ipv4_cidr&);
private:
std::uint32_t address_ = 0; unsigned int mask_length_ = 0;
};
// Stream extraction operator, also performs canonicalization std::istream& operator>>(std::istream& in, ipv4_cidr& cidr) {
int a, b, c, d, m; char ch; if (!(in >> a >> std::noskipws >> ch) || a < 0 || a > UINT8_MAX || ch != '.' || !(in >> b >> ch) || b < 0 || b > UINT8_MAX || ch != '.' || !(in >> c >> ch) || c < 0 || c > UINT8_MAX || ch != '.' || !(in >> d >> ch) || d < 0 || d > UINT8_MAX || ch != '/' || !(in >> m) || m < 1 || m > 32) { in.setstate(std::ios_base::failbit); return in; } uint32_t mask = ~((1 << (32 - m)) - 1); uint32_t address = (a << 24) + (b << 16) + (c << 8) + d; address &= mask; cidr.address_ = address; cidr.mask_length_ = m; return in;
}
// Stream insertion operator std::ostream& operator<<(std::ostream& out, const ipv4_cidr& cidr) {
uint32_t address = cidr.address(); unsigned int d = address & UINT8_MAX; address >>= 8; unsigned int c = address & UINT8_MAX; address >>= 8; unsigned int b = address & UINT8_MAX; address >>= 8; unsigned int a = address & UINT8_MAX; out << a << '.' << b << '.' << c << '.' << d << '/' << cidr.mask_length(); return out;
}
int main(int argc, char** argv) {
for (int i = 1; i < argc; ++i) { std::istringstream in(argv[i]); ipv4_cidr cidr; if (in >> cidr) std::cout << cidr << '\n'; else std::cerr << argv[i] << ": invalid CIDR\n"; } return 0;
}</lang>
- Output:
$ ./canonicalize_cidr 87.70.141.1/22 87.70.140.0/22
Factor
<lang factor>USING: command-line formatting grouping io kernel math.parser namespaces prettyprint sequences splitting ; IN: rosetta-code.canonicalize-cidr
! canonicalize a CIDR block: make sure none of the host bits are set command-line get [ lines ] when-empty [
! ( CIDR-IP -- bits-in-network-part dotted-decimal ) "/" split first2 string>number swap
! get IP as binary string "." split [ string>number "%08b" sprintf ] map "" join
! replace the host part with all zeros over cut length [ CHAR: 0 ] "" replicate-as append
! convert back to dotted-decimal 8 group [ bin> number>string ] map "." join swap
! and output "%s/%d\n" printf
] each</lang>
- Output:
$ canonicalize-cidr.factor 87.70.141.1/22 87.70.140.0/22
Go
<lang go>package main
import (
"fmt" "log" "os" "strconv" "strings"
)
func check(err error) {
if err != nil { log.Fatal(err) }
}
func main() {
// canonicalize a CIDR block: make sure none of the host bits are set var cidr string if len(os.Args) > 1 { cidr = os.Args[1] } else { log.Fatal("Please pass the CIDR to be canonicalized.") }
// dotted-decimal / bits in network part split := strings.Split(cidr, "/") dotted := split[0] size, err := strconv.Atoi(split[1]) check(err)
// get IP as binary string var bin []string for _, n := range strings.Split(dotted, ".") { i, err := strconv.Atoi(n) check(err) bin = append(bin, fmt.Sprintf("%08b", i)) } binary := strings.Join(bin, "")
// replace the host part with all zeros binary = binary[0:size] + strings.Repeat("0", 32-size)
// convert back to dotted-decimal var canon []string for i := 0; i < len(binary); i += 8 { num, err := strconv.ParseInt(binary[i:i+8], 2, 64) check(err) canon = append(canon, fmt.Sprintf("%d", num)) }
// and output fmt.Printf("%s/%s\n", strings.Join(canon, "."), split[1])
}</lang>
- Output:
$ go run canonicalize_cidr.go 87.70.141.1/22 87.70.140.0/22
Julia
Julia has a Sockets library as a builtin, which has the types IPv4 and IPv6 for single IP addresses. <lang julia>using Sockets
function canonCIDR(cidr::String)
cidr = replace(cidr, r"\.(\.|\/)" => s".0\1") # handle .. cidr = replace(cidr, r"\.(\.|\/)" => s".0\1") # handle ... ip = split(cidr, "/") dig = length(ip) > 1 ? 2^(32 - parse(UInt8, ip[2])) : 1 ip4 = IPv4(UInt64(IPv4(ip[1])) & (0xffffffff - dig + 1)) return length(ip) == 1 ? "$ip4/32" : "$ip4/$(ip[2])"
end
println(canonCIDR("87.70.141.1/22")) println(canonCIDR("100.68.0.18/18")) println(canonCIDR("10.4.30.77/30")) println(canonCIDR("10.207.219.251/32")) println(canonCIDR("10.207.219.251")) println(canonCIDR("110.200.21/4")) println(canonCIDR("10..55/8")) println(canonCIDR("10.../8"))
</lang>
- Output:
87.70.140.0/22 100.68.0.0/18 10.4.30.76/30 10.207.219.251/32 10.207.219.251/32 96.0.0.0/4 10.0.0.0/8 10.0.0.0/8
Perl
<lang perl>#!/usr/bin/env perl use v5.16; use Socket qw(inet_aton inet_ntoa);
- canonicalize a CIDR block: make sure none of the host bits are set
if (!@ARGV) {
chomp(@ARGV = <>);
}
for (@ARGV) {
# dotted-decimal / bits in network part my ($dotted, $size) = split m#/#;
# get IP as binary string my $binary = sprintf "%032b", unpack('N', inet_aton $dotted);
# Replace the host part with all zeroes substr($binary, $size) = 0 x (32 - $size);
# Convert back to dotted-decimal $dotted = inet_ntoa(pack 'B32', $binary);
# And output say "$dotted/$size";
}</lang>
- Output:
$ canonicalize_cidr.pl 87.70.141.1/22 87.70.140.0/22
Python
<lang python>#!/usr/bin/env python
- canonicalize a CIDR block specification:
- make sure none of the host bits are set
import sys from socket import inet_aton, inet_ntoa from struct import pack, unpack
args = sys.argv[1:] if len(args) == 0:
args = sys.stdin.readlines()
for cidr in args:
# IP in dotted-decimal / bits in network part dotted, size_str = cidr.split('/') size = int(size_str)
numeric = unpack('!I', inet_aton(dotted))[0] # IP as an integer binary = f'{numeric:#034b}' # then as a padded binary string prefix = binary[:size + 2] # just the network part # (34 and +2 are to account # for leading '0b')
canon_binary = prefix + '0' * (32 - size) # replace host part with all zeroes canon_numeric = int(canon_binary, 2) # convert back to integer canon_dotted = inet_ntoa(pack('!I', (canon_numeric))) # and then to dotted-decimal print(f'{canon_dotted}/{size}') # output result</lang>
- Output:
$ canonicalize_cidr.py 87.70.141.1/22 87.70.140.0/22
Raku
String manipulation
<lang perl6>#!/usr/bin/env raku
- canonicalize a CIDR block: make sure none of the host bits are set
if (!@*ARGS) {
@*ARGS = $*IN.lines;
}
for @*ARGS -> $cidr {
# dotted-decimal / bits in network part my ($dotted, $size) = $cidr.split('/');
# get IP as binary string my $binary = $dotted.split('.').map(*.fmt("%08b")).join;
# Replace the host part with all zeroes $binary.substr-rw($size) = 0 x (32 - $size);
# Convert back to dotted-decimal my $canon = $binary.comb(8).map(*.join.parse-base(2)).join('.');
# And output say "$canon/$size";
}</lang>
- Output:
$ canonicalize_cidr.raku 87.70.141.1/22 87.70.140.0/22
Bit mask and shift
<lang perl6># canonicalize a IP4 CIDR block sub CIDR-IP4-canonicalize ($address) {
constant @mask = 24, 16, 8, 0;
# dotted-decimal / subnet size my ($dotted, $size) = |$address.split('/'), 32;
# get IP as binary address my $binary = sum $dotted.comb(/\d+/) Z+< @mask;
# mask off subnet $binary +&= (2 ** $size - 1) +< (32 - $size);
# Return dotted-decimal notation (@mask.map($binary +> * +& 0xFF).join('.'), $size)
}
my @tests = <
87.70.141.1/22 100.68.0.18/18 10.4.30.77/30 10.207.219.251/32 10.207.219.251 110.200.21/4 10.11.12.13/8 10.../8
>;
printf "CIDR: %18s Routing prefix: %s/%s\n", $_, |.&CIDR-IP4-canonicalize
for @*ARGS || @tests».trim;</lang>
- Output:
CIDR: 87.70.141.1/22 Routing prefix: 87.70.140.0/22 CIDR: 100.68.0.18/18 Routing prefix: 100.68.0.0/18 CIDR: 10.4.30.77/30 Routing prefix: 10.4.30.76/30 CIDR: 10.207.219.251/32 Routing prefix: 10.207.219.251/32 CIDR: 10.207.219.251 Routing prefix: 10.207.219.251/32 CIDR: 110.200.21/4 Routing prefix: 96.0.0.0/4 CIDR: 10.11.12.13/8 Routing prefix: 10.0.0.0/8 CIDR: 10.../8 Routing prefix: 10.0.0.0/8
REXX
<lang rexx>/*REXX pgm canonicalizes IPv4 addresses that are in CIDR notation (dotted─dec/network).*/ parse arg a . /*obtain optional argument from the CL.*/ if a== | a=="," then a= '87.70.141.1/22' , /*Not specified? Then use the defaults*/
'36.18.154.103/12' , '62.62.197.11/29' , '67.137.119.181/4' , '161.214.74.21/24' , '184.232.176.184/18'
do i=1 for words(a); z= word(a, i) /*process each IPv4 address in the list*/ parse var z # '/' -0 mask /*get the address nodes & network mask.*/ #= subword( translate(#, , .) 0 0 0, 1, 4) /*elide dots from addr, ensure 4 nodes.*/ $= # /*use original node address (for now). */ hb= 32 - substr(word(mask .32, 1), 2) /*obtain the size of the host bits. */ $=; ##= /*crop the host bits only if mask ≤ 32.*/ do k=1 for 4; _= word(#, k) /*create a 32-bit (binary) IPv4 address*/ ##= ## || right(d2b(_), 8, 0) /*append eight bits of the " " */ end /*k*/ /* [↑] ... and ensure a node is 8 bits.*/ ##= left(##, 32-hb, 0) /*crop bits in host part of IPv4 addr. */ ##= left(##, 32, 0) /*replace cropped bits with binary '0's*/ do j=8 by 8 for 4 /* [↓] parse the four nodes of address*/ $= $ || . || b2d(substr(##, j-7, 8)) /*reconstitute the decimal nodes. */ end /*j*/ /* [↑] and insert a dot between nodes.*/ say /*introduce a blank line between IPv4's*/ $= substr($, 2) /*elid the leading decimal point in $ */ say ' original IPv4 address: ' z /*display the original IPv4 address. */ say ' canonicalized address: ' translate( space($), ., " ")mask /*canonicalized.*/ end /*i*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ b2d: return x2d( b2x( arg(1) ) ) + 0 /*convert binary ───► decimal number.*/ d2b: return x2b( d2x( arg(1) ) ) + 0 /* " decimal ───► binary " */</lang>
- output when using the default input:
original IPv4 address: 87.70.141.1/22 canonicalized address: 87.70.140.0/22 original IPv4 address: 36.18.154.103/12 canonicalized address: 36.16.0.0/12 original IPv4 address: 62.62.197.11/29 canonicalized address: 62.62.197.8/29 original IPv4 address: 67.137.119.181/4 canonicalized address: 64.0.0.0/4 original IPv4 address: 161.214.74.21/24 canonicalized address: 161.214.74.0/24 original IPv4 address: 184.232.176.184/18 canonicalized address: 184.232.128.0/18
Ruby
<lang ruby>#!/usr/bin/env ruby
- canonicalize a CIDR block: make sure none of the host bits are set
if ARGV.length == 0 then
ARGV = $stdin.readlines.map(&:chomp)
end
ARGV.each do |cidr|
# dotted-decimal / bits in network part dotted, size_str = cidr.split('/') size = size_str.to_i
# get IP as binary string binary = dotted.split('.').map { |o| "%08b" % o }.join
# Replace the host part with all zeroes binary[size .. -1] = '0' * (32 - size)
# Convert back to dotted-decimal canon = binary.chars.each_slice(8).map { |a| a.join.to_i(2) }.join('.')
# And output puts "#{canon}/#{size}"
end</lang>
- Output:
$ canonicalize_cidr.rb 87.70.141.1/22 87.70.140.0/22
Wren
<lang ecmascript>import "/fmt" for Fmt, Conv import "/str" for Str
// canonicalize a CIDR block: make sure none of the host bits are set var canonicalize = Fn.new { |cidr|
// dotted-decimal / bits in network part var split = cidr.split("/") var dotted = split[0] var size = Num.fromString(split[1])
// get IP as binary string var binary = dotted.split(".").map { |n| Fmt.swrite("$08b", Num.fromString(n)) }.join()
// replace the host part with all zeros binary = binary[0...size] + "0" * (32 - size)
// convert back to dotted-decimal var chunks = Str.chunks(binary, 8) var canon = chunks.map { |c| Conv.atoi(c, 2) }.join(".")
// and return return canon + "/" + split[1]
}
var tests = [
"87.70.141.1/22", "36.18.154.103/12", "62.62.197.11/29", "67.137.119.181/4", "161.214.74.21/24", "184.232.176.184/18"
]
for (test in tests) {
Fmt.print("$-18s -> $s", test, canonicalize.call(test))
}</lang>
- Output:
87.70.141.1/22 -> 87.70.140.0/22 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