android: Change format of address ranges and print sets
[strongswan.git] / src / frontends / android / app / src / main / java / org / strongswan / android / utils / IPRange.java
1 /*
2 * Copyright (C) 2012-2017 Tobias Brunner
3 * HSR Hochschule fuer Technik Rapperswil
4 *
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation; either version 2 of the License, or (at your
8 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * for more details.
14 */
15
16 package org.strongswan.android.utils;
17
18 import android.support.annotation.NonNull;
19
20 import java.net.InetAddress;
21 import java.net.UnknownHostException;
22 import java.util.ArrayList;
23 import java.util.Arrays;
24 import java.util.Collections;
25 import java.util.List;
26
27 /**
28 * Class that represents a range of IP addresses. This range could be a proper subnet, but that's
29 * not necessarily the case (see {@code getPrefix} and {@code toSubnets}).
30 */
31 public class IPRange implements Comparable<IPRange>
32 {
33 private final byte[] mBitmask = { (byte)0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
34 private byte[] mFrom;
35 private byte[] mTo;
36 private Integer mPrefix;
37
38 /**
39 * Determine if the range is a proper subnet and, if so, what the network prefix is.
40 */
41 private void determinePrefix()
42 {
43 boolean matching = true;
44
45 mPrefix = mFrom.length * 8;
46 for (int i = 0; i < mFrom.length; i++)
47 {
48 for (int bit = 0; bit < 8; bit++)
49 {
50 if (matching)
51 {
52 if ((mFrom[i] & mBitmask[bit]) != (mTo[i] & mBitmask[bit]))
53 {
54 mPrefix = (i * 8) + bit;
55 matching = false;
56 }
57 }
58 else
59 {
60 if ((mFrom[i] & mBitmask[bit]) != 0 || (mTo[i] & mBitmask[bit]) == 0)
61 {
62 mPrefix = null;
63 return;
64 }
65 }
66 }
67 }
68 }
69
70 private IPRange(byte[] from, byte[] to)
71 {
72 mFrom = from;
73 mTo = to;
74 determinePrefix();
75 }
76
77 public IPRange(String from, String to) throws UnknownHostException
78 {
79 this(InetAddress.getByName(from), InetAddress.getByName(to));
80 }
81
82 public IPRange(InetAddress from, InetAddress to)
83 {
84 initializeFromRange(from, to);
85 }
86
87 private void initializeFromRange(InetAddress from, InetAddress to)
88 {
89 byte[] fa = from.getAddress(), ta = to.getAddress();
90 if (fa.length != ta.length)
91 {
92 throw new IllegalArgumentException("Invalid range");
93 }
94 if (compareAddr(fa, ta) < 0)
95 {
96 mFrom = fa;
97 mTo = ta;
98 }
99 else
100 {
101 mTo = fa;
102 mFrom = ta;
103 }
104 determinePrefix();
105 }
106
107 public IPRange(String base, int prefix) throws UnknownHostException
108 {
109 this(InetAddress.getByName(base), prefix);
110 }
111
112 public IPRange(InetAddress base, int prefix)
113 {
114 this(base.getAddress(), prefix);
115 }
116
117 private IPRange(byte[] from, int prefix)
118 {
119 initializeFromCIDR(from, prefix);
120 }
121
122 private void initializeFromCIDR(byte[] from, int prefix)
123 {
124 if (from.length != 4 && from.length != 16)
125 {
126 throw new IllegalArgumentException("Invalid address");
127 }
128 if (prefix < 0 || prefix > from.length * 8)
129 {
130 throw new IllegalArgumentException("Invalid prefix");
131 }
132 byte[] to = from.clone();
133 byte mask = (byte)(0xff << (8 - prefix % 8));
134 int i = prefix / 8;
135
136 if (i < from.length)
137 {
138 from[i] = (byte)(from[i] & mask);
139 to[i] = (byte)(to[i] | ~mask);
140 Arrays.fill(from, i+1, from.length, (byte)0);
141 Arrays.fill(to, i+1, to.length, (byte)0xff);
142 }
143 mFrom = from;
144 mTo = to;
145 mPrefix = prefix;
146 }
147
148 public IPRange(String cidr) throws UnknownHostException
149 {
150 /* only verify the basic structure */
151 if (!cidr.matches("(?i)^(([0-9.]+)|([0-9a-f:]+))(-(([0-9.]+)|([0-9a-f:]+))|(/\\d+))?$"))
152 {
153 throw new IllegalArgumentException("Invalid CIDR or range notation");
154 }
155 if (cidr.contains("-"))
156 {
157 String[] parts = cidr.split("-");
158 InetAddress from = InetAddress.getByName(parts[0]);
159 InetAddress to = InetAddress.getByName(parts[1]);
160 initializeFromRange(from, to);
161 }
162 else
163 {
164 String[] parts = cidr.split("/");
165 InetAddress addr = InetAddress.getByName(parts[0]);
166 byte[] base = addr.getAddress();
167 int prefix = base.length * 8;
168 if (parts.length > 1)
169 {
170 prefix = Integer.parseInt(parts[1]);
171 }
172 initializeFromCIDR(base, prefix);
173 }
174 }
175
176 /**
177 * Returns the first address of the range. The network ID in case this is a proper subnet.
178 */
179 public InetAddress getFrom()
180 {
181 try
182 {
183 return InetAddress.getByAddress(mFrom);
184 }
185 catch (UnknownHostException ignored)
186 {
187 return null;
188 }
189 }
190
191 /**
192 * Returns the last address of the range.
193 */
194 public InetAddress getTo()
195 {
196 try
197 {
198 return InetAddress.getByAddress(mTo);
199 }
200 catch (UnknownHostException ignored)
201 {
202 return null;
203 }
204 }
205
206 /**
207 * If this range is a proper subnet returns its prefix, otherwise returns null.
208 */
209 public Integer getPrefix()
210 {
211 return mPrefix;
212 }
213
214 @Override
215 public int compareTo(@NonNull IPRange other)
216 {
217 int cmp = compareAddr(mFrom, other.mFrom);
218 if (cmp == 0)
219 { /* smaller ranges first */
220 cmp = compareAddr(mTo, other.mTo);
221 }
222 return cmp;
223 }
224
225 @Override
226 public boolean equals(Object o)
227 {
228 if (o == null || !(o instanceof IPRange))
229 {
230 return false;
231 }
232 return this == o || compareTo((IPRange)o) == 0;
233 }
234
235 @Override
236 public String toString()
237 {
238 try
239 {
240 if (mPrefix != null)
241 {
242 return InetAddress.getByAddress(mFrom).getHostAddress() + "/" + mPrefix;
243 }
244 return InetAddress.getByAddress(mFrom).getHostAddress() + "-" +
245 InetAddress.getByAddress(mTo).getHostAddress();
246 }
247 catch (UnknownHostException ignored)
248 {
249 return super.toString();
250 }
251 }
252
253 private int compareAddr(byte a[], byte b[])
254 {
255 if (a.length != b.length)
256 {
257 return (a.length < b.length) ? -1 : 1;
258 }
259 for (int i = 0; i < a.length; i++)
260 {
261 if (a[i] != b[i])
262 {
263 if (((int)a[i] & 0xff) < ((int)b[i] & 0xff))
264 {
265 return -1;
266 }
267 else
268 {
269 return 1;
270 }
271 }
272 }
273 return 0;
274 }
275
276 /**
277 * Check if this range fully contains the given range.
278 */
279 public boolean contains(IPRange range)
280 {
281 return compareAddr(mFrom, range.mFrom) <= 0 && compareAddr(range.mTo, mTo) <= 0;
282 }
283
284 /**
285 * Check if this and the given range overlap.
286 */
287 public boolean overlaps(IPRange range)
288 {
289 return !(compareAddr(mTo, range.mFrom) < 0 || compareAddr(range.mTo, mFrom) < 0);
290 }
291
292 private byte[] dec(byte[] addr)
293 {
294 for (int i = addr.length - 1; i >= 0; i--)
295 {
296 if (--addr[i] != (byte)0xff)
297 {
298 break;
299 }
300 }
301 return addr;
302 }
303
304 private byte[] inc(byte[] addr)
305 {
306 for (int i = addr.length - 1; i >= 0; i--)
307 {
308 if (++addr[i] != 0)
309 {
310 break;
311 }
312 }
313 return addr;
314 }
315
316 /**
317 * Remove the given range from the current range. Returns a list of resulting ranges (these are
318 * not proper subnets). At most two ranges are returned, in case the given range is contained in
319 * this but does not equal it, which would result in an empty list (which is also the case if
320 * this range is fully contained in the given range).
321 */
322 public List<IPRange> remove(IPRange range)
323 {
324 ArrayList<IPRange> list = new ArrayList<>();
325 if (!overlaps(range))
326 { /* | this | or | this |
327 * | range | | range | */
328 list.add(this);
329 }
330 else if (!range.contains(this))
331 { /* we are not completely removed, so none of these cases applies:
332 * | this | or | this | or | this |
333 * | range | | range | | range | */
334 if (compareAddr(mFrom, range.mFrom) < 0 && compareAddr(range.mTo, mTo) < 0)
335 { /* the removed range is completely within our boundaries:
336 * | this |
337 * | range | */
338 list.add(new IPRange(mFrom, dec(range.mFrom.clone())));
339 list.add(new IPRange(inc(range.mTo.clone()), mTo));
340 }
341 else
342 { /* one end is within our boundaries the other at or outside it:
343 * | this | or | this | or | this | or | this |
344 * | range | | range | | range | | range | */
345 byte[] from = compareAddr(mFrom, range.mFrom) < 0 ? mFrom : inc(range.mTo.clone());
346 byte[] to = compareAddr(mTo, range.mTo) > 0 ? mTo : dec(range.mFrom.clone());
347 list.add(new IPRange(from, to));
348 }
349 }
350 return list;
351 }
352
353 private boolean adjacent(IPRange range)
354 {
355 if (compareAddr(mTo, range.mFrom) < 0)
356 {
357 byte[] to = inc(mTo.clone());
358 return compareAddr(to, range.mFrom) == 0;
359 }
360 byte[] from = dec(mFrom.clone());
361 return compareAddr(from, range.mTo) == 0;
362 }
363
364 /**
365 * Merge two adjacent or overlapping ranges, returns null if it's not possible to merge them.
366 */
367 public IPRange merge(IPRange range)
368 {
369 if (overlaps(range))
370 {
371 if (contains(range))
372 {
373 return this;
374 }
375 else if (range.contains(this))
376 {
377 return range;
378 }
379 }
380 else if (!adjacent(range))
381 {
382 return null;
383 }
384 byte[] from = compareAddr(mFrom, range.mFrom) < 0 ? mFrom : range.mFrom;
385 byte[] to = compareAddr(mTo, range.mTo) > 0 ? mTo : range.mTo;
386 return new IPRange(from, to);
387 }
388
389 /**
390 * Split the given range into a sorted list of proper subnets.
391 */
392 public List<IPRange> toSubnets()
393 {
394 ArrayList<IPRange> list = new ArrayList<>();
395 if (mPrefix != null)
396 {
397 list.add(this);
398 }
399 else
400 {
401 int i = 0, bit = 0, prefix, netmask, common_byte, common_bit;
402 int from_cur, from_prev = 0, to_cur, to_prev = 1;
403 boolean from_full = true, to_full = true;
404
405 byte[] from = mFrom.clone();
406 byte[] to = mTo.clone();
407
408 /* find a common prefix */
409 while (i < from.length && (from[i] & mBitmask[bit]) == (to[i] & mBitmask[bit]))
410 {
411 if (++bit == 8)
412 {
413 bit = 0;
414 i++;
415 }
416 }
417 prefix = i * 8 + bit;
418
419 /* at this point we know that the addresses are either equal, or that the
420 * current bits in the 'from' and 'to' addresses are 0 and 1, respectively.
421 * we now look at the rest of the bits as two binary trees (0=left, 1=right)
422 * where 'from' and 'to' are both leaf nodes. all leaf nodes between these
423 * nodes are addresses contained in the range. to collect them as subnets
424 * we follow the trees from both leaf nodes to their root node and record
425 * all complete subtrees (right for from, left for to) we come across as
426 * subnets. in that process host bits are zeroed out. if both addresses
427 * are equal we won't enter the loop below.
428 * 0_____|_____1 for the 'from' address we assume we start on a
429 * 0__|__ 1 0__|__1 left subtree (0) and follow the left edges until
430 * _|_ _|_ _|_ _|_ we reach the root of this subtree, which is
431 * | | | | | | | | either the root of this whole 'from'-subtree
432 * 0 1 0 1 0 1 0 1 (causing us to leave the loop) or the root node
433 * of the right subtree (1) of another node (which actually could be the
434 * leaf node we start from). that whole subtree gets recorded as subnet.
435 * next we follow the right edges to the root of that subtree which again is
436 * either the 'from'-root or the root node in the left subtree (0) of
437 * another node. the complete right subtree of that node is the next subnet
438 * we record. from there we assume that we are in that right subtree and
439 * recursively follow right edges to its root. for the 'to' address the
440 * procedure is exactly the same but with left and right reversed.
441 */
442 if (++bit == 8)
443 {
444 bit = 0;
445 i++;
446 }
447 common_byte = i;
448 common_bit = bit;
449 netmask = from.length * 8;
450 for (i = from.length - 1; i >= common_byte; i--)
451 {
452 int bit_min = (i == common_byte) ? common_bit : 0;
453 for (bit = 7; bit >= bit_min; bit--)
454 {
455 byte mask = mBitmask[bit];
456
457 from_cur = from[i] & mask;
458 if (from_prev == 0 && from_cur != 0)
459 { /* 0 -> 1: subnet is the whole current (right) subtree */
460 list.add(new IPRange(from.clone(), netmask));
461 from_full = false;
462 }
463 else if (from_prev != 0 && from_cur == 0)
464 { /* 1 -> 0: invert bit to switch to right subtree and add it */
465 from[i] ^= mask;
466 list.add(new IPRange(from.clone(), netmask));
467 from_cur = 1;
468 }
469 /* clear the current bit */
470 from[i] &= ~mask;
471 from_prev = from_cur;
472
473 to_cur = to[i] & mask;
474 if (to_prev != 0 && to_cur == 0)
475 { /* 1 -> 0: subnet is the whole current (left) subtree */
476 list.add(new IPRange(to.clone(), netmask));
477 to_full = false;
478 }
479 else if (to_prev == 0 && to_cur != 0)
480 { /* 0 -> 1: invert bit to switch to left subtree and add it */
481 to[i] ^= mask;
482 list.add(new IPRange(to.clone(), netmask));
483 to_cur = 0;
484 }
485 /* clear the current bit */
486 to[i] &= ~mask;
487 to_prev = to_cur;
488 netmask--;
489 }
490 }
491
492 if (from_full && to_full)
493 { /* full subnet (from=to or from=0.. and to=1.. after common prefix) - not reachable
494 * due to the shortcut at the top */
495 list.add(new IPRange(from.clone(), prefix));
496 }
497 else if (from_full)
498 { /* full from subnet (from=0.. after prefix) */
499 list.add(new IPRange(from.clone(), prefix + 1));
500 }
501 else if (to_full)
502 { /* full to subnet (to=1.. after prefix) */
503 list.add(new IPRange(to.clone(), prefix + 1));
504 }
505 }
506 Collections.sort(list);
507 return list;
508 }
509 }