1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
namespace AndrewAndante\SubMuncher; |
4
|
|
|
|
5
|
|
|
class SubMuncher |
6
|
|
|
{ |
7
|
|
|
/** |
8
|
|
|
* This class should not be instantiated. |
9
|
|
|
*/ |
10
|
|
|
private function __construct() |
11
|
|
|
{ |
12
|
|
|
} |
13
|
|
|
|
14
|
|
|
/** |
15
|
|
|
* @param array $ipsArray |
16
|
|
|
* @param int $max max number of rules returned |
17
|
|
|
* @return array |
18
|
|
|
*/ |
19
|
|
|
public static function consolidate($ipsArray, $max = null, $alreadyProcessed = null) |
20
|
|
|
{ |
21
|
|
|
$consolidatedSubnets = []; |
22
|
|
|
$subnetStart = null; |
23
|
|
|
|
24
|
|
|
$ips = array_unique($ipsArray); |
25
|
|
|
$sortedIPs = Util::sort_addresses($ips); |
26
|
|
|
|
27
|
|
|
foreach ($sortedIPs as $index => $ipv4) { |
28
|
|
|
// If not last and the next IP is the next sequential one, we are at the beginning of a subnet |
29
|
|
|
if (isset($sortedIPs[$index + 1]) && $sortedIPs[$index + 1] == Util::ip_after($ipv4)) { |
30
|
|
|
// if we've already started, just keep going, else kick one off |
31
|
|
|
$subnetStart = $subnetStart ?: $ipv4; |
32
|
|
|
// if not the first IP and the previous IP is sequential, we're at the end of a subnet |
33
|
|
|
} elseif (isset($sortedIPs[$index - 1]) && $subnetStart !== null) { |
34
|
|
|
$result = self::ip_range_to_subnet_array($subnetStart, $ipv4); |
35
|
|
|
$consolidatedSubnets = array_merge($consolidatedSubnets, $result); |
36
|
|
|
$subnetStart = null; |
37
|
|
|
// otherwise we are a lone /32, so add it straight in |
38
|
|
|
} else { |
39
|
|
|
$consolidatedSubnets[]= $ipv4.'/32'; |
40
|
|
|
$subnetStart = null; |
41
|
|
|
} |
42
|
|
|
} |
43
|
|
|
|
44
|
|
|
if ($alreadyProcessed !== null) { |
45
|
|
|
$totalSubnets = array_merge($consolidatedSubnets, $alreadyProcessed); |
46
|
|
|
} else { |
47
|
|
|
$totalSubnets = $consolidatedSubnets; |
48
|
|
|
} |
49
|
|
|
|
50
|
|
|
if ($max === null || count($totalSubnets) <= $max) { |
51
|
|
|
return $totalSubnets; |
52
|
|
|
} |
53
|
|
|
|
54
|
|
|
return self::consolidate_subnets($consolidatedSubnets, $max, $alreadyProcessed); |
55
|
|
|
} |
56
|
|
|
|
57
|
|
|
/** |
58
|
|
|
* @param string $startip an IPv4 address |
59
|
|
|
* @param string $endip an IPv4 address |
60
|
|
|
* |
61
|
|
|
* @return string[] list of subnets that cover the ip range specified |
62
|
|
|
*/ |
63
|
|
|
public static function ip_range_to_subnet_array($startip, $endip) |
64
|
|
|
{ |
65
|
|
|
|
66
|
|
|
if (!Util::is_ipaddr($startip) || !Util::is_ipaddr($endip)) { |
67
|
|
|
return []; |
68
|
|
|
} |
69
|
|
|
|
70
|
|
|
// Container for subnets within this range. |
71
|
|
|
$rangesubnets = []; |
72
|
|
|
|
73
|
|
|
// Figure out what the smallest subnet is that holds the number of IPs in the |
74
|
|
|
// given range. |
75
|
|
|
$cidr = Util::find_smallest_cidr(Util::ip_range_size($startip, $endip)); |
76
|
|
|
|
77
|
|
|
// Loop here to reduce subnet size and retest as needed. We need to make sure |
78
|
|
|
// that the target subnet is wholly contained between $startip and $endip. |
79
|
|
|
for ($cidr; $cidr <= 32; $cidr++) { |
80
|
|
|
// Find the network and broadcast addresses for the subnet being tested. |
81
|
|
|
$targetsub_min = Util::gen_subnet($startip, $cidr); |
82
|
|
|
$targetsub_max = Util::gen_subnet_max($startip, $cidr); |
83
|
|
|
|
84
|
|
|
// Check best case where the range is exactly one subnet. |
85
|
|
|
if (($targetsub_min == $startip) && ($targetsub_max == $endip)) { |
86
|
|
|
// Hooray, the range is exactly this subnet! |
87
|
|
|
return ["{$startip}/{$cidr}"]; |
88
|
|
|
} |
89
|
|
|
|
90
|
|
|
// These remaining scenarios will find a subnet that uses the largest |
91
|
|
|
// chunk possible of the range being tested, and leave the rest to be |
92
|
|
|
// tested recursively after the loop. |
93
|
|
|
|
94
|
|
|
// Check if the subnet begins with $startip and ends before $endip |
95
|
|
|
if (($targetsub_min == $startip) && Util::ip_less_than($targetsub_max, $endip)) { |
96
|
|
|
break; |
97
|
|
|
} |
98
|
|
|
|
99
|
|
|
// Check if the subnet ends at $endip and starts after $startip |
100
|
|
|
if (Util::ip_greater_than($targetsub_min, $startip) && ($targetsub_max == $endip)) { |
101
|
|
|
break; |
102
|
|
|
} |
103
|
|
|
|
104
|
|
|
// Check if the subnet is between $startip and $endip |
105
|
|
|
if (Util::ip_greater_than($targetsub_min, $startip) && Util::ip_less_than($targetsub_max, $endip)) { |
106
|
|
|
break; |
107
|
|
|
} |
108
|
|
|
} |
109
|
|
|
|
110
|
|
|
// Some logic that will recursively search from $startip to the first IP before |
111
|
|
|
// the start of the subnet we just found. |
112
|
|
|
// NOTE: This may never be hit, the way the above algo turned out, but is left |
113
|
|
|
// for completeness. |
114
|
|
|
if ($startip != $targetsub_min) { |
115
|
|
|
$rangesubnets = array_merge( |
116
|
|
|
$rangesubnets, |
117
|
|
|
self::ip_range_to_subnet_array($startip, Util::ip_before($targetsub_min)) |
|
|
|
|
118
|
|
|
); |
119
|
|
|
} |
120
|
|
|
|
121
|
|
|
// Add in the subnet we found before, to preserve ordering |
122
|
|
|
$rangesubnets[] = "{$targetsub_min}/{$cidr}"; |
123
|
|
|
|
124
|
|
|
// And some more logic that will search after the subnet we found to fill in |
125
|
|
|
// to the end of the range. |
126
|
|
|
if ($endip != $targetsub_max) { |
127
|
|
|
$rangesubnets = array_merge( |
128
|
|
|
$rangesubnets, |
129
|
|
|
self::ip_range_to_subnet_array(Util::ip_after($targetsub_max), $endip) |
|
|
|
|
130
|
|
|
); |
131
|
|
|
} |
132
|
|
|
|
133
|
|
|
return $rangesubnets; |
134
|
|
|
} |
135
|
|
|
|
136
|
|
|
/** |
137
|
|
|
* Function to figure out the least problematic subnets to combine based on |
138
|
|
|
* fewest additional IPs introduced. Then combines them as such, and runs |
139
|
|
|
* it back through the consolidator with one less subnet - until we have |
140
|
|
|
* reduced it down to the maximum number of rules |
141
|
|
|
* |
142
|
|
|
* @param array $subnetsArray array of cidrs |
143
|
|
|
* @param int $max |
144
|
|
|
* |
145
|
|
|
* @return array |
146
|
|
|
*/ |
147
|
|
|
public static function consolidate_subnets($subnetsArray, $max = null, $alreadyProcessed = null) |
148
|
|
|
{ |
149
|
|
|
|
150
|
|
|
$subnetsArray = Util::sort_cidrs($subnetsArray); |
151
|
|
|
|
152
|
|
|
do { |
153
|
|
|
$countSubnetsArray = count($subnetsArray); |
154
|
|
|
$newSubnetsArray = []; |
155
|
|
|
$subnetToMaskMap = []; |
156
|
|
|
$ipReductionBySubnet = []; |
157
|
|
|
reset($subnetsArray); |
158
|
|
|
do { |
159
|
|
|
$cidr = current($subnetsArray); |
160
|
|
|
list($currentIP, $currentMask) = explode('/', $cidr); |
161
|
|
|
$nextIP = null; |
162
|
|
|
$nextMask = null; |
163
|
|
|
|
164
|
|
|
if (next($subnetsArray) !== false) { |
165
|
|
|
list($nextIP, $nextMask) = explode('/', current($subnetsArray)); |
166
|
|
|
prev($subnetsArray); |
167
|
|
|
} else { |
168
|
|
|
end($subnetsArray); |
169
|
|
|
} |
170
|
|
|
|
171
|
|
|
$endIP = Util::gen_subnet_max($currentIP, $currentMask); |
172
|
|
|
while (isset($nextIP) && Util::ip_after($endIP) == $nextIP) { |
173
|
|
|
$nextEndIP = Util::gen_subnet_max($nextIP, $nextMask); |
174
|
|
|
$consolidated = self::ip_range_to_subnet_array($currentIP, $nextEndIP); |
175
|
|
|
if (count($consolidated) == 1) { |
176
|
|
|
$endIP = $nextEndIP; |
177
|
|
|
list($currentIP, $currentMask) = explode('/', $consolidated[0]); |
178
|
|
|
if (next($subnetsArray) !== false) { |
179
|
|
|
list($nextIP, $nextMask) = explode('/', current($subnetsArray)); |
180
|
|
|
} else { |
181
|
|
|
end($subnetsArray); |
182
|
|
|
$nextIP = null; |
183
|
|
|
$nextMask = null; |
184
|
|
|
} |
185
|
|
|
} else { |
186
|
|
|
break; |
187
|
|
|
} |
188
|
|
|
} |
189
|
|
|
|
190
|
|
|
$newSubnetsArray[] = $currentIP . '/' . $currentMask; |
191
|
|
|
|
192
|
|
|
$subnetToMaskMap[$currentIP] = [ |
193
|
|
|
'startIP' => $currentIP, |
194
|
|
|
'endIP' => $endIP, |
195
|
|
|
'mask' => $currentMask, |
196
|
|
|
'next' => isset($nextIP) ? $nextIP : 'none', |
197
|
|
|
]; |
198
|
|
|
|
199
|
|
|
$toJoin = Util::get_single_subnet($currentIP, Util::gen_subnet_max($nextIP, $nextMask)); |
200
|
|
|
if (!$toJoin) { |
|
|
|
|
201
|
|
|
continue; |
202
|
|
|
} |
203
|
|
|
list($joinIP, $joinMask) = explode('/', $toJoin); |
204
|
|
|
$diff = abs(Util::subnet_range_size($currentMask) - Util::subnet_range_size($joinMask)); |
205
|
|
|
|
206
|
|
|
$ipReductionBySubnet[$joinIP] = [ |
207
|
|
|
'mask' => $joinMask, |
208
|
|
|
'diff' => $diff, |
209
|
|
|
'original' => $currentIP, |
210
|
|
|
]; |
211
|
|
|
} while (next($subnetsArray) !== false); |
212
|
|
|
$subnetsArray = $newSubnetsArray; |
213
|
|
|
} while (count($subnetsArray) !== $countSubnetsArray); |
214
|
|
|
|
215
|
|
|
// sort array by number of additional IPs introduced |
216
|
|
|
uasort($ipReductionBySubnet, function ($a, $b) { |
217
|
|
|
return $a['diff'] - $b['diff']; |
218
|
|
|
}); |
219
|
|
|
|
220
|
|
|
$returnCIDRs = []; |
221
|
|
|
foreach ($subnetToMaskMap as $ip => $config) { |
222
|
|
|
$returnCIDRs[] = $ip.'/'.$config['mask']; |
223
|
|
|
} |
224
|
|
|
|
225
|
|
|
if ($alreadyProcessed !== null) { |
226
|
|
|
$totalSubnets = array_merge($returnCIDRs, $alreadyProcessed); |
227
|
|
|
} else { |
228
|
|
|
$totalSubnets = $returnCIDRs; |
229
|
|
|
} |
230
|
|
|
|
231
|
|
|
if ($max === null || count($totalSubnets) <= $max) { |
232
|
|
|
return $totalSubnets; |
233
|
|
|
} |
234
|
|
|
|
235
|
|
|
reset($ipReductionBySubnet); |
236
|
|
|
do { |
237
|
|
|
current($ipReductionBySubnet); |
238
|
|
|
$injectedIP = key($ipReductionBySubnet); |
239
|
|
|
|
240
|
|
|
$toUpdate = $ipReductionBySubnet[$injectedIP]['original']; |
241
|
|
|
$next = $subnetToMaskMap[$toUpdate]['next']; |
242
|
|
|
|
243
|
|
|
// remove the two subnets we've just mushed |
244
|
|
|
unset($subnetToMaskMap[$toUpdate]); |
245
|
|
|
unset($subnetToMaskMap[$next]); |
246
|
|
|
|
247
|
|
|
// chuck in the new one |
248
|
|
|
$alreadyProcessed[] = $injectedIP . '/' . $ipReductionBySubnet[$injectedIP]['mask']; |
249
|
|
|
|
250
|
|
|
$returnCIDRs = []; |
251
|
|
|
foreach ($subnetToMaskMap as $ip => $config) { |
252
|
|
|
$returnCIDRs[] = $ip . '/' . $config['mask']; |
253
|
|
|
} |
254
|
|
|
|
255
|
|
|
if ($alreadyProcessed !== null) { |
256
|
|
|
$totalSubnets = array_merge($returnCIDRs, $alreadyProcessed); |
257
|
|
|
} else { |
258
|
|
|
$totalSubnets = $returnCIDRs; |
259
|
|
|
} |
260
|
|
|
|
261
|
|
|
$totalSubnets = Util::sort_cidrs($totalSubnets); |
262
|
|
|
next($ipReductionBySubnet); |
263
|
|
|
} while (count($totalSubnets) > $max); |
264
|
|
|
|
265
|
|
|
return $totalSubnets; |
266
|
|
|
} |
267
|
|
|
|
268
|
|
|
/** |
269
|
|
|
* @param string[] $ipsArray |
270
|
|
|
* @param int|null $max |
271
|
|
|
* @return array |
272
|
|
|
*/ |
273
|
|
|
public static function consolidate_verbose($ipsArray, $max = null, $alreadyProcessed = null) |
274
|
|
|
{ |
275
|
|
|
$consolidateResults = self::consolidate($ipsArray, $max, $alreadyProcessed); |
276
|
|
|
$totalIPs = []; |
277
|
|
|
foreach ($consolidateResults as $cidr) { |
278
|
|
|
$totalIPs = array_merge($totalIPs, Util::cidr_to_ips_array($cidr)); |
279
|
|
|
} |
280
|
|
|
|
281
|
|
|
return [ |
282
|
|
|
'consolidated_subnets' => $consolidateResults, |
283
|
|
|
'initial_IPs' => Util::sort_addresses($ipsArray), |
284
|
|
|
'total_IPs' => $totalIPs |
285
|
|
|
]; |
286
|
|
|
} |
287
|
|
|
|
288
|
|
|
/** |
289
|
|
|
* @param string[] $subnetsArray |
290
|
|
|
* @param int|null $max |
291
|
|
|
* @return array |
292
|
|
|
*/ |
293
|
|
|
public static function consolidate_subnets_verbose($subnetsArray, $max = null, $alreadyProcessed = null) |
294
|
|
|
{ |
295
|
|
|
$ips = []; |
296
|
|
|
foreach ($subnetsArray as $subnet) { |
297
|
|
|
$ips = array_merge($ips, Util::cidr_to_ips_array($subnet)); |
298
|
|
|
} |
299
|
|
|
|
300
|
|
|
return self::consolidate_verbose($ips, $max, $alreadyProcessed); |
301
|
|
|
} |
302
|
|
|
} |
303
|
|
|
|
If you define a variable conditionally, it can happen that it is not defined for all execution paths.
Let’s take a look at an example:
In the above example, the variable $x is defined if you pass “foo” or “bar” as argument for $a. However, since the switch statement has no default case statement, if you pass any other value, the variable $x would be undefined.
Available Fixes
Check for existence of the variable explicitly:
Define a default value for the variable:
Add a value for the missing path: