Merge pull request #2151 from stilez/patch-11

1 files changed, 104 insertions, 55 deletions

diff --git a/src/etc/inc/util.inc b/src/etc/inc/util.inc
index 4f13187..523dcf3 100644
--- a/src/etc/inc/util.inc
+++ b/src/etc/inc/util.inc
@@ -527,73 +527,122 @@ function ip_range_to_address_array($startip, $endip, $max_size = 5000) {
 	return $rangeaddresses;
 }
 
-/* Convert a range of IPv4 addresses to an array of subnets which can contain the range. */
-/* Note: IPv6 ranges are not yet supported here. */
-function ip_range_to_subnet_array($startip, $endip) {
-	if (!is_ipaddrv4($startip) || !is_ipaddrv4($endip)) {
-		return array();
-	}
-
-	if (ip_greater_than($startip, $endip)) {
-		// Swap start and end so we can process sensibly.
-		$temp = $startip;
-		$startip = $endip;
-		$endip = $temp;
-	}
+/* 	Convert an IPv4 or IPv6 IP range to an array of subnets which can contain the range.
+	Algorithm and embodying code PD'ed by Stilez - enjoy as you like :-)
+
+	Documented on pfsense dev list 19-20 May 2013. Summary:
+
+	The algorithm looks at patterns of 0's and 1's in the least significant bit(s), whether IPv4 or IPv6.
+	These are all that needs checking to identify a _guaranteed_ correct, minimal and optimal subnet array.
+	
+	As a result, string/binary pattern matching of the binary IP is very efficient. It uses just 2 pattern-matching rules 
+	to chop off increasingly larger subnets at both ends that can't be part of larger subnets, until nothing's left.
+
+	(a) If any range has EITHER low bit 1 (in startip) or 0 (in endip), that end-point  is _always guaranteed_ to be optimally 
+	represented by its own 'single IP' CIDR; the remaining range then shrinks by one IP up or down, causing the new end-point's 
+	low bit to change from 1->0 (startip) or 0->1 (endip). Only one edge case needs checking: if a range contains exactly 2 
+	adjacent IPs of this format, then the two IPs themselves are required to span it, and we're done.
+	Once this rule is applied, the remaining range is _guaranteed_ to end in 0's and 1's so rule (b) can now be used, and its 
+	low bits can now be ignored.
+	
+	(b) If any range has BOTH startip and endip ending in some number of 0's and 1's respectively, these low bits can 
+	*always* be ignored and "bit-shifted" for subnet spanning. So provided we remember the bits we've place-shifted, we can 
+	_always_ right-shift and chop off those bits, leaving a smaller range that has EITHER startip ending in 1 or endip ending 
+	in 0 (ie can now apply (a) again) or the entire range has vanished and we're done. 
+	We then loop to redo (a) again on the remaining (place shifted) range until after a few loops, the remaining (place shifted) 
+	range 'vanishes' by meeting the exit criteria of (a) or (b), and we're done.
+*/
 
-	// Container for subnets within this range.
-	$rangesubnets = array();
+function ip_range_to_subnet_array($ip1, $ip2) {
 
-	// Figure out what the smallest subnet is that holds the number of IPs in the given range.
-	$cidr = find_smallest_cidr_v4(ip_range_size_v4($startip, $endip));
+	if (is_ipaddrv4($ip1) && is_ipaddrv4($ip2)) {
+		$proto = 'ipv4';  // for clarity
+		$bits = 32;
+		$ip1bin = decbin(ip2long32($ip1));
+		$ip2bin = decbin(ip2long32($ip2));
+	} elseif (is_ipaddrv6($ip1) && is_ipaddrv6($ip2)) {
+		$proto = 'ipv6';
+		$bits = 128;
+		$ip1bin = Net_IPv6::_ip2Bin($ip1);
+		$ip2bin = Net_IPv6::_ip2Bin($ip2);
+	} else
+		return array();
 
-	// Loop here to reduce subnet size and retest as needed. We need to make sure
-	//   that the target subnet is wholly contained between $startip and $endip.
-	for ($cidr; $cidr <= 32; $cidr++) {
-		// Find the network and broadcast addresses for the subnet being tested.
-		$targetsub_min = gen_subnet($startip, $cidr);
-		$targetsub_max = gen_subnet_max($startip, $cidr);
+	// it's *crucial* that binary strings are guaranteed the expected length;  do this for certainty even though for IPv6 it's redundant
+	$ip1bin = str_pad($ip1bin, $bits, '0', STR_PAD_LEFT);
+	$ip2bin = str_pad($ip2bin, $bits, '0', STR_PAD_LEFT);
 
-		// Check best case where the range is exactly one subnet.
-		if (($targetsub_min == $startip) && ($targetsub_max == $endip)) {
-			// Hooray, the range is exactly this subnet!
-			return array("{$startip}/{$cidr}");
-		}
+	if ($ip1bin == $ip2bin)
+		return array($ip1 . '/' . $bits); // exit if ip1=ip2 (trivial case)
+	
+	if ($ip1bin > $ip2bin))
+		list ($ip1bin, $ip2bin) = array($ip2bin, $ip1bin);  // swap if needed (ensures ip1 < ip2)
 
-		// These remaining scenarios will find a subnet that uses the largest
-		//  chunk possible of the range being tested, and leave the rest to be
-		//  tested recursively after the loop.
+	$rangesubnets = array();
+	$netsize = 0;
+
+	do {
+		// at loop start, $ip1 is guaranteed strictly less than $ip2 (important for edge case trapping and preventing accidental binary wrapround)
+		// which means the assignments $ip1 += 1 and $ip2 -= 1 will always be "binary-wrapround-safe"
+
+		// step #1 if start ip (as shifted) ends in any '1's, then it must have a single cidr to itself (any cidr would include the '0' below it)
+		
+		if (substr($ip1bin, -1, 1) == '1') {
+			// the start ip must be in a separate one-IP cidr range
+			$new_subnet_ip = substr($ip1bin, $netsize, $bits - $netsize) . str_repeat('0', $netsize);
+			$rangesubnets[$new_subnet_ip] = $bits - $netsize;
+			$n = strrpos($ip1bin, '0');  //can't be all 1's
+			$ip1bin = ($n == 0 ? '' : substr($ip1bin, 0, $n)) . '1' . str_repeat('0', $bits - $n - 1);  // BINARY VERSION OF $ip1 += 1
+		} 
+
+		// step #2, if end ip (as shifted) ends in any zeros then that must have a cidr to itself (as cidr cant span the 1->0 gap)
+		
+		if (substr($ip2bin, -1, 1) == '0') {
+			// the end ip must be in a separate one-IP cidr range
+			$new_subnet_ip = substr($ip2bin, $netsize, $bits - $netsize) . str_repeat('0', $netsize);
+			$rangesubnets[$new_subnet_ip] = $bits - $netsize;
+			$n = strrpos($ip2bin, '1');  //can't be all 0's
+			$ip2bin = ($n == 0 ? '' : substr($ip2bin, 0, $n)) . '0' . str_repeat('1', $bits - $n - 1);  // BINARY VERSION OF $ip2 -= 1
+			// already checked for the edge case where end = start+1 and start ends in 0x1, above, so it's safe
+		}
+
+		// this is the only edge case arising from increment/decrement. 
+		// it happens if the range at start of loop is exactly 2 adjacent ips, that spanned the 1->0 gap. (we will have enumerated both by now)
+		
+		if ($ip2bin < $ip1bin)
+			continue;
 
-		// Check if the subnet begins with $startip and ends before $endip
-		if (($targetsub_min == $startip) && ip_less_than($targetsub_max, $endip)) {
-			break;
+		// step #3 the start and end ip MUST now end in '0's and '1's respectively
+		// so we have a non-trivial range AND the last N bits are no longer important for CIDR purposes.
+
+		$shift = $bits - max(strrpos($ip1bin, '0'), strrpos($ip2bin, '1'));  // num of low bits which are '0' in ip1 and '1' in ip2
+		$ip1bin = str_repeat('0', $shift) . substr($ip1bin, 0, $bits - $shift);
+		$ip2bin = str_repeat('0', $shift) . substr($ip2bin, 0, $bits - $shift);
+		$netsize += $shift;
+		if ($ip1bin == $ip2bin) {
+			// we're done.
+			$new_subnet_ip = substr($ip1bin, $netsize, $bits - $netsize) . str_repeat('0', $netsize);
+			$rangesubnets[$new_subnet_ip] = $bits - $netsize;
+			continue;
 		}
+		
+		// at this point there's still a remaining range, and either startip ends with '1', or endip ends with '0'. So repeat cycle.
+	} while ($ip1bin < $ip2bin);
 
-		// Check if the subnet ends at $endip and starts after $startip
-		if (ip_greater_than($targetsub_min, $startip) && ($targetsub_max == $endip)) {
-			break;
-		}
+	// subnets are ordered by bit size. Re sort by IP ("naturally") and convert back to IPv4/IPv6
 
-		// Check if the subnet is between $startip and $endip
-		if (ip_greater_than($targetsub_min, $startip) && ip_less_than($targetsub_max, $endip)) {
-			break;
-		}
-	}
+	ksort($rangesubnets, SORT_STRING);
+	$out = array();
 
-	// Some logic that will recursively search from $startip to the first IP before the start of the subnet we just found.
-	// NOTE: This may never be hit, the way the above algo turned out, but is left for completeness.
-	if ($startip != $targetsub_min) {
-		$rangesubnets = array_merge($rangesubnets, ip_range_to_subnet_array($startip, ip_before($targetsub_min)));
+	foreach ($rangesubnets as $ip => $netmask) {
+		if ($proto == 'ipv4') {
+			$i = str_split($ip, 8);
+			$out[] = implode('.', array( bindec($i[0]),bindec($i[1]),bindec($i[2]),bindec($i[3]))) . '/' . $netmask;
+		} else
+			$out[] = Net_IPv6::compress(Net_IPv6::_bin2Ip($ip)) . '/' . $netmask;
 	}
 
-	// Add in the subnet we found before, to preserve ordering
-	$rangesubnets[] = "{$targetsub_min}/{$cidr}";
-
-	// And some more logic that will search after the subnet we found to fill in to the end of the range.
-	if ($endip != $targetsub_max) {
-		$rangesubnets = array_merge($rangesubnets, ip_range_to_subnet_array(ip_after($targetsub_max), $endip));
-	}
-	return $rangesubnets;
+	return $out;
 }
 
 /* returns true if $range is a valid pair of IPv4 or IPv6 addresses separated by a "-"