diff --git a/IP.pm b/IP.pm index fac167f..5572b51 100644 --- a/IP.pm +++ b/IP.pm @@ -32,7 +32,7 @@ ); require Exporter; -@EXPORT_OK = qw(Compact Coalesce Zero Zeros Ones V4mask V4net netlimit); +@EXPORT_OK = qw(Compact Coalesce Zero Zeros Ones V4mask V4net Subtract Exclude netlimit); @EXPORT_FAIL = qw($_netlimit); @ISA = qw(Exporter NetAddr::IP::Lite); @@ -58,6 +58,8 @@ Ones V4mask V4net + Subtract + Exclude netlimit :aton DEPRECATED :lower @@ -421,6 +423,69 @@ return &coalesce; } +=head2 Subtract + + Title : Subtract + Usage : my $remaining_networks = Subtract(\@list_of_networks,\@networks_to_subtract); + Function : computes the network definitions resulting from subtracting @networks_to_subtract from @list_of_networks + Returns : reference to a sorted list of NetAddr::IP objects representing the remaining networks + Args : reference to a sorted list of NetAddr::IP objects (the list must be sorted! eg. by using Compact) + : reference to a sorted list of NetAddr::IP objects to subtract (the list must be sorted! eg. by using Compact) + +=cut +sub Subtract { + my @add = ref $_[0] eq __PACKAGE__ ? ($_[0]) : @{$_[0]}; + my @sub = @{$_[1]}; + my @ret; + while (@add && @sub) { + if ($add[0]->within($sub[0])) { + shift @add; + } elsif ($sub[0]->within($add[0])) { + my ($low,$up) = Exclude(shift @add,shift @sub); + push @ret, @$low; + unshift @add, @$up; + } else { + if ($add[0]->bigint < $sub[0]->bigint) { + push @ret, shift @add; + } else { + shift @sub; + } + } + } + push @ret, @add; + return \@ret; +} + +=head2 Exclude + + Title : Exclude + Usage : my ($remaining_lower_networks,$remaining_upper_networks) = Exclude($original_network,$network_to_exclude); + Function : computes the network definitions resulting from removing the $network_to_exclude from $original_network. + Returns : two list references containing the sorted network definitions 'below' and 'above' the excluded network + Args : NetAddr::IP object of the original network + : NetAddr::IP object of the network to exclude + +=cut +sub Exclude { + return ([],[]) if $_[0] == $_[1]; + return ([$_[0]],[]) unless $_[1]->within($_[0]); + my @low; + my @up; + my ($s1,$s2) = $_[0]->split($_[0]->masklen+1); + while ($s1 != $_[1] && $s2 != $_[1]) { + if ($_[1]->within($s1)) { + unshift @up, $s2; + ($s1,$s2) = $s1->split($s1->masklen+1); + } else { + push @low, $s1; + ($s1,$s2) = $s2->split($s2->masklen+1); + } + } + push @low, $s1 if $s2 == $_[1]; + unshift @up, $s2 if $s1 == $_[1]; + return (\@low,\@up); +} + sub hostenumref($) { my $r = _splitref(0,$_[0]); unless ((notcontiguous($_[0]->{mask}))[1] == 128 || diff --git a/t/v4-exclude.t b/t/v4-exclude.t new file mode 100644 index 0000000..101e5a2 --- /dev/null +++ b/t/v4-exclude.t @@ -0,0 +1,31 @@ +use Test::More; +use NetAddr::IP qw(Exclude); + +my @r = ( + ['10.0.0.0/8','10.0.0.0/9', [], ['10.128.0.0/9']], + ['10.0.0.0/8','10.0.0.0/8', [], []], + ['10.0.0.0/8','10.128.0.0/9', ['10.0.0.0/9'], []], + ['10.0.0.0/8','10.128.0.0/10', ['10.0.0.0/9'], ['10.192.0.0/10']], + ['10.0.0.0/8','10.0.0.0/32', [], ['10.0.0.1/32','10.0.0.2/31','10.0.0.4/30','10.0.0.8/29','10.0.0.16/28','10.0.0.32/27','10.0.0.64/26','10.0.0.128/25','10.0.1.0/24','10.0.2.0/23','10.0.4.0/22','10.0.8.0/21','10.0.16.0/20','10.0.32.0/19','10.0.64.0/18','10.0.128.0/17','10.1.0.0/16','10.2.0.0/15','10.4.0.0/14','10.8.0.0/13','10.16.0.0/12','10.32.0.0/11','10.64.0.0/10','10.128.0.0/9']], + ['192.168.0.0/24','192.168.0.255/32',['192.168.0.0/25','192.168.0.128/26','192.168.0.192/27','192.168.0.224/28','192.168.0.240/29','192.168.0.248/30','192.168.0.252/31','192.168.0.254/32'],[]], + ['192.168.0.0/23','192.168.0.127/32',['192.168.0.0/26','192.168.0.64/27','192.168.0.96/28','192.168.0.112/29','192.168.0.120/30','192.168.0.124/31','192.168.0.126/32'],['192.168.0.128/25','192.168.1.0/24']], + ['1.2.3.4/32','1.2.3.4/32',[],[]], + ['0.0.0.0/0','0.0.0.0/32',[],['0.0.0.1/32','0.0.0.2/31','0.0.0.4/30','0.0.0.8/29','0.0.0.16/28','0.0.0.32/27','0.0.0.64/26','0.0.0.128/25','0.0.1.0/24','0.0.2.0/23','0.0.4.0/22','0.0.8.0/21','0.0.16.0/20','0.0.32.0/19','0.0.64.0/18','0.0.128.0/17','0.1.0.0/16','0.2.0.0/15','0.4.0.0/14','0.8.0.0/13','0.16.0.0/12','0.32.0.0/11','0.64.0.0/10','0.128.0.0/9','1.0.0.0/8','2.0.0.0/7','4.0.0.0/6','8.0.0.0/5','16.0.0.0/4','32.0.0.0/3','64.0.0.0/2','128.0.0.0/1']], + ['1.2.3.4/32','1.2.3.5/32',['1.2.3.4/32'],[]], +); + +plan tests => 4 * scalar @r; + +SKIP: { + foreach my $case (@r) { + my ($low, $up) = Exclude(NetAddr::IP->new($case->[0]), NetAddr::IP->new($case->[1])); + my $ex_low = [map { NetAddr::IP->new($_) } @{$case->[2]}]; + my $ex_up = [map { NetAddr::IP->new($_) } @{$case->[3]}]; + is("@$up", "@$ex_up", "Upper half of Exclude($case->[0],$case->[1]) is @$ex_up"); + is("@$low", "@$ex_low", "Lower half of Exclude($case->[0],$case->[1]) is @$ex_low"); + + ($low, $up) = NetAddr::IP->new($case->[0])->Exclude(NetAddr::IP->new($case->[1])); + is("@$up", "@$ex_up", "Upper half of ($case->[0])->Exclude($case->[1]) is @$ex_up"); + is("@$low", "@$ex_low", "Lower half of ($case->[0])->Exclude($case->[1]) is @$ex_low"); + } +} diff --git a/t/v4-subtract.t b/t/v4-subtract.t new file mode 100644 index 0000000..113934c --- /dev/null +++ b/t/v4-subtract.t @@ -0,0 +1,86 @@ +use Test::More; +use NetAddr::IP qw(Exclude Subtract); + +my @r = ( + ['10.0.0.0/8','10.0.0.0/9'], + ['10.0.0.0/8','10.0.0.0/8'], + ['10.0.0.0/8','10.128.0.0/9'], + ['10.0.0.0/8','10.128.0.0/10'], + ['10.0.0.0/8','10.0.0.0/32'], + ['192.168.0.0/24','192.168.0.255/32'], + ['192.168.0.0/23','192.168.0.127/32'], + ['1.2.3.4/32','1.2.3.4/32'], + ['0.0.0.0/0','0.0.0.0/32'], +); + +plan tests => 1 + 19 * scalar @r; + +SKIP: { + my $res = Subtract([],[]); + is("@$res", "", "Subtract([],[]) returns an empty list"); + + foreach my $case (@r) { + my $whole = [NetAddr::IP->new($case->[0])]; + my $part1 = [NetAddr::IP->new($case->[1])]; + my ($low,$up) = Exclude($whole->[0],$part1->[0]); + my $part2 = [@{$low},@{$up}]; + my $res = []; + + $res = Subtract($whole,$part1); + is("@$res", "@$part2", "Subtract(@$whole,@$part1) returns @$part2"); + + $res = $whole->[0]->Subtract($part1); + is("@$res", "@$part2", "($whole->[0])->Subtract(@$part1) returns @$part2"); + + $res = Subtract($whole,$part2); + is("@$res", "@$part1", "Subtract(@$whole,@$part2) returns @$part1"); + + $res = $whole->[0]->Subtract($part2); + is("@$res", "@$part1", "($whole->[0])->Subtract(@$part2) returns @$part1"); + + $res = Subtract($part1,$part2); + is("@$res", "@$part1", "Subtract(@$part1,@$part2) returns @$part1"); + + $res = $part1->[0]->Subtract($part2); + is("@$res", "@$part1", "($part1->[0])->Subtract(@$part2) returns @$part1"); + + $res = Subtract($part2,$part1); + is("@$res", "@$part2", "Subtract(@$part2,@$part1) returns @$part2"); + + $res = Subtract(Subtract($whole,$part1),$part2); + is("@$res", "", "Subtract(Subtract(@$whole,@$part1),$part2) returns an empty list"); + + $res = Subtract($whole->[0]->Subtract($part1),$part2); + is("@$res", "", "Subtract(($whole->[0])->Subtract(@$part1),$part2) returns an empty list"); + + $res = Subtract(Subtract($whole,$part2),$part1); + is("@$res", "", "Subtract(Subtract(@$whole,@$part2),$part1) returns an empty list"); + + $res = Subtract($whole->[0]->Subtract($part2),$part1); + is("@$res", "", "Subtract(($whole->[0])->Subtract(@$part2),$part1) returns an empty list"); + + $res = Subtract($whole,$whole); + is("@$res", "", "Subtract(@$whole,@$whole) returns an empty list"); + + $res = $whole->[0]->Subtract($whole); + is("@$res", "", "($whole->[0])->Subtract(@$whole) returns an empty list"); + + $res = Subtract($part1,$part1); + is("@$res", "", "Subtract(@$part1,@$part1) returns an empty list"); + + $res = $part1->[0]->Subtract($part1); + is("@$res", "", "($part1->[0])->Subract(@$part1) returns an empty list"); + + $res = Subtract($part2,$part2); + is("@$res", "", "Subtract(@$part2,@$part2) returns an empty list"); + + $res = Subtract($part1,$whole); + is("@$res", "", "Subtract(@$part1,@$whole) returns an empty list"); + + $res = $part1->[0]->Subtract($whole); + is("@$res", "", "($part1->[0])->Subtract(@$whole) returns an empty list"); + + $res = Subtract($part2,$whole); + is("@$res", "", "Subtract(@$part2,@$whole) returns an empty list"); + } +} diff --git a/t/v6-exclude.t b/t/v6-exclude.t new file mode 100644 index 0000000..53aadd6 --- /dev/null +++ b/t/v6-exclude.t @@ -0,0 +1,28 @@ +use Test::More; +use NetAddr::IP qw(:lower Exclude); + +my @r = ( + ['2001:db8::/32','2001:db8::/33', [], ['2001:db8:8000::/33']], + ['2001:db8::/64','2001:db8::/64', [], []], + ['2001:db8::/128','2001:db8::/128', [], []], + ['2001:db8::/32','2001:db8:8000::/33', ['2001:db8::/33'], []], + ['2001:db8::/32','2001:db8:8000::/34', ['2001:db8::/33'], ['2001:db8:c000::/34']], + ['::/0','::/128', [], ['0:0:0:0:0:0:0:1/128','0:0:0:0:0:0:0:2/127','0:0:0:0:0:0:0:4/126','0:0:0:0:0:0:0:8/125','0:0:0:0:0:0:0:10/124','0:0:0:0:0:0:0:20/123','0:0:0:0:0:0:0:40/122','0:0:0:0:0:0:0:80/121','0:0:0:0:0:0:0:100/120','0:0:0:0:0:0:0:200/119','0:0:0:0:0:0:0:400/118','0:0:0:0:0:0:0:800/117','0:0:0:0:0:0:0:1000/116','0:0:0:0:0:0:0:2000/115','0:0:0:0:0:0:0:4000/114','0:0:0:0:0:0:0:8000/113','0:0:0:0:0:0:1:0/112','0:0:0:0:0:0:2:0/111','0:0:0:0:0:0:4:0/110','0:0:0:0:0:0:8:0/109','0:0:0:0:0:0:10:0/108','0:0:0:0:0:0:20:0/107','0:0:0:0:0:0:40:0/106','0:0:0:0:0:0:80:0/105','0:0:0:0:0:0:100:0/104','0:0:0:0:0:0:200:0/103','0:0:0:0:0:0:400:0/102','0:0:0:0:0:0:800:0/101','0:0:0:0:0:0:1000:0/100','0:0:0:0:0:0:2000:0/99','0:0:0:0:0:0:4000:0/98','0:0:0:0:0:0:8000:0/97','0:0:0:0:0:1:0:0/96','0:0:0:0:0:2:0:0/95','0:0:0:0:0:4:0:0/94','0:0:0:0:0:8:0:0/93','0:0:0:0:0:10:0:0/92','0:0:0:0:0:20:0:0/91','0:0:0:0:0:40:0:0/90','0:0:0:0:0:80:0:0/89','0:0:0:0:0:100:0:0/88','0:0:0:0:0:200:0:0/87','0:0:0:0:0:400:0:0/86','0:0:0:0:0:800:0:0/85','0:0:0:0:0:1000:0:0/84','0:0:0:0:0:2000:0:0/83','0:0:0:0:0:4000:0:0/82','0:0:0:0:0:8000:0:0/81','0:0:0:0:1:0:0:0/80','0:0:0:0:2:0:0:0/79','0:0:0:0:4:0:0:0/78','0:0:0:0:8:0:0:0/77','0:0:0:0:10:0:0:0/76','0:0:0:0:20:0:0:0/75','0:0:0:0:40:0:0:0/74','0:0:0:0:80:0:0:0/73','0:0:0:0:100:0:0:0/72','0:0:0:0:200:0:0:0/71','0:0:0:0:400:0:0:0/70','0:0:0:0:800:0:0:0/69','0:0:0:0:1000:0:0:0/68','0:0:0:0:2000:0:0:0/67','0:0:0:0:4000:0:0:0/66','0:0:0:0:8000:0:0:0/65','0:0:0:1:0:0:0:0/64','0:0:0:2:0:0:0:0/63','0:0:0:4:0:0:0:0/62','0:0:0:8:0:0:0:0/61','0:0:0:10:0:0:0:0/60','0:0:0:20:0:0:0:0/59','0:0:0:40:0:0:0:0/58','0:0:0:80:0:0:0:0/57','0:0:0:100:0:0:0:0/56','0:0:0:200:0:0:0:0/55','0:0:0:400:0:0:0:0/54','0:0:0:800:0:0:0:0/53','0:0:0:1000:0:0:0:0/52','0:0:0:2000:0:0:0:0/51','0:0:0:4000:0:0:0:0/50','0:0:0:8000:0:0:0:0/49','0:0:1:0:0:0:0:0/48','0:0:2:0:0:0:0:0/47','0:0:4:0:0:0:0:0/46','0:0:8:0:0:0:0:0/45','0:0:10:0:0:0:0:0/44','0:0:20:0:0:0:0:0/43','0:0:40:0:0:0:0:0/42','0:0:80:0:0:0:0:0/41','0:0:100:0:0:0:0:0/40','0:0:200:0:0:0:0:0/39','0:0:400:0:0:0:0:0/38','0:0:800:0:0:0:0:0/37','0:0:1000:0:0:0:0:0/36','0:0:2000:0:0:0:0:0/35','0:0:4000:0:0:0:0:0/34','0:0:8000:0:0:0:0:0/33','0:1:0:0:0:0:0:0/32','0:2:0:0:0:0:0:0/31','0:4:0:0:0:0:0:0/30','0:8:0:0:0:0:0:0/29','0:10:0:0:0:0:0:0/28','0:20:0:0:0:0:0:0/27','0:40:0:0:0:0:0:0/26','0:80:0:0:0:0:0:0/25','0:100:0:0:0:0:0:0/24','0:200:0:0:0:0:0:0/23','0:400:0:0:0:0:0:0/22','0:800:0:0:0:0:0:0/21','0:1000:0:0:0:0:0:0/20','0:2000:0:0:0:0:0:0/19','0:4000:0:0:0:0:0:0/18','0:8000:0:0:0:0:0:0/17','1:0:0:0:0:0:0:0/16','2:0:0:0:0:0:0:0/15','4:0:0:0:0:0:0:0/14','8:0:0:0:0:0:0:0/13','10:0:0:0:0:0:0:0/12','20:0:0:0:0:0:0:0/11','40:0:0:0:0:0:0:0/10','80:0:0:0:0:0:0:0/9','100:0:0:0:0:0:0:0/8','200:0:0:0:0:0:0:0/7','400:0:0:0:0:0:0:0/6','800:0:0:0:0:0:0:0/5','1000:0:0:0:0:0:0:0/4','2000:0:0:0:0:0:0:0/3','4000:0:0:0:0:0:0:0/2','8000:0:0:0:0:0:0:0/1']], + ['2001:db8::/128','2001:db8:1::/128', ['2001:db8::/128'], []], +); + +plan tests => 4 * scalar @r; + +SKIP: { + foreach my $case (@r) { + my ($low, $up) = Exclude(NetAddr::IP->new($case->[0]), NetAddr::IP->new($case->[1])); + my $ex_low = [map { NetAddr::IP->new($_) } @{$case->[2]}]; + my $ex_up = [map { NetAddr::IP->new($_) } @{$case->[3]}]; + is("@$up", "@$ex_up", "Upper half of Exclude($case->[0],$case->[1]) is @$ex_up"); + is("@$low", "@$ex_low", "Lower half of Exclude($case->[0],$case->[1]) is @$ex_low"); + + ($low, $up) = NetAddr::IP->new($case->[0])->Exclude(NetAddr::IP->new($case->[1])); + is("@$up", "@$ex_up", "Upper half of ($case->[0])->Exclude($case->[1]) is @$ex_up"); + is("@$low", "@$ex_low", "Lower half of ($case->[0])->Exclude($case->[1]) is @$ex_low"); + } +} diff --git a/t/v6-subtract.t b/t/v6-subtract.t new file mode 100644 index 0000000..9274688 --- /dev/null +++ b/t/v6-subtract.t @@ -0,0 +1,82 @@ +use Test::More; +use NetAddr::IP qw(:lower Exclude Subtract); + +my @r = ( + ['2001:db8::/32','2001:db8::/33'], + ['2001:db8::/64','2001:db8::/64'], + ['2001:db8::/128','2001:db8::/128'], + ['2001:db8::/32','2001:db8:8000::/33'], + ['2001:db8::/32','2001:db8:8000::/34'], +); + +plan tests => 1 + 19 * scalar @r; + +SKIP: { + my $res = Subtract([],[]); + is("@$res", "", "Subtract([],[]) returns an empty list"); + + foreach my $case (@r) { + my $whole = [NetAddr::IP->new($case->[0])]; + my $part1 = [NetAddr::IP->new($case->[1])]; + my ($low,$up) = Exclude($whole->[0],$part1->[0]); + my $part2 = [@{$low},@{$up}]; + my $res = []; + + $res = Subtract($whole,$part1); + is("@$res", "@$part2", "Subtract(@$whole,@$part1) returns @$part2"); + + $res = $whole->[0]->Subtract($part1); + is("@$res", "@$part2", "($whole->[0])->Subtract(@$part1) returns @$part2"); + + $res = Subtract($whole,$part2); + is("@$res", "@$part1", "Subtract(@$whole,@$part2) returns @$part1"); + + $res = $whole->[0]->Subtract($part2); + is("@$res", "@$part1", "($whole->[0])->Subtract(@$part2) returns @$part1"); + + $res = Subtract($part1,$part2); + is("@$res", "@$part1", "Subtract(@$part1,@$part2) returns @$part1"); + + $res = $part1->[0]->Subtract($part2); + is("@$res", "@$part1", "($part1->[0])->Subtract(@$part2) returns @$part1"); + + $res = Subtract($part2,$part1); + is("@$res", "@$part2", "Subtract(@$part2,@$part1) returns @$part2"); + + $res = Subtract(Subtract($whole,$part1),$part2); + is("@$res", "", "Subtract(Subtract(@$whole,@$part1),$part2) returns an empty list"); + + $res = Subtract($whole->[0]->Subtract($part1),$part2); + is("@$res", "", "Subtract(($whole->[0])->Subtract(@$part1),$part2) returns an empty list"); + + $res = Subtract(Subtract($whole,$part2),$part1); + is("@$res", "", "Subtract(Subtract(@$whole,@$part2),$part1) returns an empty list"); + + $res = Subtract($whole->[0]->Subtract($part2),$part1); + is("@$res", "", "Subtract(($whole->[0])->Subtract(@$part2),$part1) returns an empty list"); + + $res = Subtract($whole,$whole); + is("@$res", "", "Subtract(@$whole,@$whole) returns an empty list"); + + $res = $whole->[0]->Subtract($whole); + is("@$res", "", "($whole->[0])->Subtract(@$whole) returns an empty list"); + + $res = Subtract($part1,$part1); + is("@$res", "", "Subtract(@$part1,@$part1) returns an empty list"); + + $res = $part1->[0]->Subtract($part1); + is("@$res", "", "($part1->[0])->Subract(@$part1) returns an empty list"); + + $res = Subtract($part2,$part2); + is("@$res", "", "Subtract(@$part2,@$part2) returns an empty list"); + + $res = Subtract($part1,$whole); + is("@$res", "", "Subtract(@$part1,@$whole) returns an empty list"); + + $res = $part1->[0]->Subtract($whole); + is("@$res", "", "($part1->[0])->Subtract(@$whole) returns an empty list"); + + $res = Subtract($part2,$whole); + is("@$res", "", "Subtract(@$part2,@$whole) returns an empty list"); + } +}