001 /*
002 Copyright (c) 1996-2011, Damon Hart-Davis
003 All rights reserved.
004
005 Redistribution and use in source and binary forms, with or without
006 modification, are permitted provided that the following conditions are
007 met:
008
009 * Redistributions of source code must retain the above copyright
010 notice, this list of conditions and the following disclaimer.
011
012 * Redistributions in binary form must reproduce the above copyright
013 notice, this list of conditions and the following disclaimer in the
014 documentation and/or other materials provided with the
015 distribution.
016
017 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
018 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
019 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
020 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
021 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
022 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
023 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
024 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
025 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
026 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
027 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028 */
029 package org.hd.d.pg2k.svrCore;
030
031 import java.lang.ref.SoftReference;
032 import java.net.InetAddress;
033 import java.net.UnknownHostException;
034 import java.util.ArrayList;
035 import java.util.Arrays;
036 import java.util.Collection;
037 import java.util.Collections;
038 import java.util.Iterator;
039 import java.util.List;
040 import java.util.concurrent.Callable;
041 import java.util.concurrent.Future;
042
043 import org.xbill.DNS.ARecord;
044 import org.xbill.DNS.Cache;
045 import org.xbill.DNS.DClass;
046 import org.xbill.DNS.ExtendedResolver;
047 import org.xbill.DNS.Lookup;
048 import org.xbill.DNS.Name;
049 import org.xbill.DNS.PTRRecord;
050 import org.xbill.DNS.Record;
051 import org.xbill.DNS.ReverseMap;
052 import org.xbill.DNS.TextParseException;
053 import org.xbill.DNS.Type;
054
055 /**This class has tools for IP-address and DNS manipulation.
056 *
057 * @author Damon Hart-Davis
058 */
059 public final class AddrTools
060 {
061 /**Prevent creation of instances of this class. */
062 private AddrTools() { }
063
064 /**If true, use DNSJava to do DNS lookups where possible, else use Java's built-in DNS resolver.
065 * DNSJava does not retain all results indefinitely unlike Java's DNS resolver,
066 * and allows us to use separate caches with different characteristics for different query types
067 * which can make it much more robust for our purposes.
068 */
069 public static final boolean USE_DNSJAVA = true;
070
071 /**Fixed empty search path for lookups. */
072 private static final Name[] EMPTY_SEARCH_PATH = new Name[0];
073
074 /**Approximate total maximum timeout for DNS resolution in seconds; strictly positive.
075 * Quite short for the the geo-lookup (etc)
076 * as we usually only get limited value from a small number of lookups,
077 * and we do not want to block interactive activity for an extended period.
078 * <p>
079 * A value of a few seconds to a few tens of seconds should normally suffice,
080 * and puts a reasonable cap on the cost of a "full" lookup.
081 */
082 private static final int RESOLVER_QUICK_TIMEOUT_S = 5 + Rnd.fastRnd.nextInt(2);
083
084 /**Maximum retries of resolution against each DNS server/resolver; strictly positive.
085 * A value greater than 1 is more robust,
086 * ie allows for the odd lost packet,
087 * and may get good results because the retry may gain the benefit
088 * of async cacheing upstream between calls on one particular resolver.
089 * <p>
090 * A value of 1 or 2 is typical.
091 */
092 private static final int RESOLVER_QUICK_RETRIES = 2;
093
094 /**SoftReference to our shared DNS cache (for IN records); never null though referent may be.
095 * This may be created and set up on first use,
096 * and is tuned for our purposes
097 * (for example shorter timeouts and longer negative cacheing than default).
098 * It may be discarded and recreated if we are short of memory;
099 * hopefully caching by boundary DNS resolvers should minimise
100 * the impact if we do this.
101 * <p>
102 * We don't hand this out to other users,
103 * but they can give us a Lookup object and we will set the cache
104 * and other relevant parameters,
105 * and return the result to them.
106 * <p>
107 * This is intended to be highly threadable for many concurrent lookups.
108 * <p>
109 * Get/set access to this value is synchronised on the _cacheIN_SR_lock.
110 */
111 private static SoftReference<Cache> _cacheIN_SR = new SoftReference<Cache>(null);
112
113 /**Lock for get/set access to _cacheIN_SR SoftReference value. */
114 private static final Object _cacheIN_SR_lock = new Object();
115
116 /**Default maximum time to positively cache a record for (seconds); strictly positive.
117 * Limiting this to a few hours at most can limit memory load
118 * when there are many users.
119 */
120 private static final int DEFAULT_DNS_CACHE_S = 3601 + Rnd.fastRnd.nextInt(3600);
121
122 /**Default maximum time to negatively cache a record for (seconds); strictly positive.
123 * Setting this to a few tens of seconds
124 * (plus a few interleaved "failed lookup" intervals)
125 * can improve performance.
126 */
127 private static final int DEFAULT_DNS_NCACHE_S = 31 + Rnd.fastRnd.nextInt(23) +
128 (7 * RESOLVER_QUICK_TIMEOUT_S);
129
130 /**Our ExtendedResolver with the normal servers but a short timeout.
131 * The DNS servers will be deduced once at initialisation.
132 */
133 private static final ExtendedResolver RESOLVER_QUICK;
134
135 /**Initialise our resolver. */
136 static
137 {
138 try {
139 RESOLVER_QUICK = new ExtendedResolver();
140 RESOLVER_QUICK.setLoadBalance(true); // Be nice to upstream resolvers.
141 RESOLVER_QUICK.setRetries(RESOLVER_QUICK_RETRIES);
142 final int resolverCount = RESOLVER_QUICK.getResolvers().length; // Resolvers found.
143 // Set the timeout per resolver to get the approximate maximum time specified.
144 RESOLVER_QUICK.setTimeout(Math.max(1, RESOLVER_QUICK_TIMEOUT_S /
145 (RESOLVER_QUICK_RETRIES * Math.max(1, resolverCount))));
146 }
147 catch(final UnknownHostException e)
148 {
149 e.printStackTrace();
150 throw new Error(e);
151 }
152 }
153
154 /**If true then we randomise the order in which we do RBL lookups.
155 * We do this to better spread the load if several of them could
156 * answer the question.
157 * <p>
158 * This does not have to be "very" random,
159 * indeed, round-robin would probably do just as well.
160 */
161 private static final boolean RANDOMISE_RBL_LOOKUP_ORDER = true;
162
163
164 /**Return access to the DNS cache, creating and initialising it if necessary; never null.
165 * If we are short of memory then we may automatically discard this entire cache.
166 * <p>
167 * This cache may have several parameters tuned for geo-lookup purposes,
168 * such as negative/positive cache time-limits.
169 */
170 private static Cache _getDNSCache()
171 {
172 synchronized(_cacheIN_SR_lock)
173 {
174 Cache result = _cacheIN_SR.get();
175 if(result == null)
176 {
177 result = new Cache(DClass.IN);
178 result.setMaxCache(DEFAULT_DNS_CACHE_S);
179 result.setMaxNCache(DEFAULT_DNS_NCACHE_S);
180 result.setMaxEntries(Math.min(10101, // Limit the cache size to something bearable since our upstream resolvers should cache stuff for us too.
181 (int) Math.max(1024, (Runtime.getRuntime().totalMemory() / (1<<16))))); // Adjust to total memory size...
182 // result.setCleanInterval(Math.max(5, DEFAULT_DNS_CACHE_S / 60)); // Set to match +ve cacheing time...
183 _cacheIN_SR = new SoftReference<Cache>(result);
184 }
185 return(result);
186 }
187 }
188
189 /**Do (quick) blocking lookup in our shared and tuned cache and resolver.
190 * This should work better for us than the built-in Java implementation
191 * and we should build a useful but size-bounded cache unless
192 * the JVM gets very low on memory, in which case we may discard it and start again.
193 * <p>
194 * The caller should <em>not</em> extract/sequester/inspect
195 * the cache/resolver/etc properties that we set in the Lookup parameter,
196 * so this routine is only package-visible.
197 * <p>
198 * FIXME: As of 20060703: most expensive consumer of time for doHTML.jsp.
199 */
200 static Record[] doQuickLookupWithTunedCache(final Lookup lookup)
201 {
202 //final long startTime = System.currentTimeMillis();
203
204 lookup.setCache(_getDNSCache());
205 lookup.setSearchPath(EMPTY_SEARCH_PATH);
206 lookup.setResolver(RESOLVER_QUICK);
207 final Record[] result = lookup.run();
208
209 //final long time = System.currentTimeMillis() - startTime;
210 //if(time > 1) /* Ignore noise. */ { (new Throwable("time: "+time+"ms")).printStackTrace(); }
211
212 return(result);
213 }
214
215 // /**Do local lookup in our shared and tuned cache only; never null.
216 // * Do not do DNS resolution; return nothing if there is nothing in cache.
217 // * <p>
218 // * The Name supplied is looked up exactly as-is,
219 // * so had better be absolute for example.
220 // * <p>
221 // * We only make this package-visible in case the DNS java classes
222 // * can leak state.
223 // */
224 // static SetResponse doLookupInTunedCacheOnly(final Name name,
225 // final int type,
226 // final byte minCred)
227 // {
228 // return(_getDNSCache().lookupRecords(name, type, minCred));
229 // }
230
231 /**Return true if we can find an A record for the given name quickly.
232 * Uses our shared/tuned cache and does a quick lookup
233 * (ie times out quickly).
234 *
235 * @throws IllegalArgumentException if argument is null or unparsable.
236 */
237 public static boolean hasARecordQuick(final String name)
238 {
239 if(name == null)
240 { throw new IllegalArgumentException(); }
241
242 try
243 {
244 final Lookup lookup = new Lookup(name, Type.A);
245 final Record[] result = doQuickLookupWithTunedCache(lookup);
246
247 // If we got some results, there is an A record..
248 return((result != null) && (result.length > 0));
249 }
250 catch(final TextParseException e)
251 {
252 throw new IllegalArgumentException("bad DNS name: " + name);
253 }
254 }
255
256 // /**Convert an (IPv4) InetAddress to dotted-quad form.
257 // * Avoid doing any DNS lookup if at all possible.
258 // *
259 // * @param addr parameter to convert to dotted-quad;
260 // * must be non-null IPv4 address
261 // *
262 // * @throws IllegalArgumentException if addr is null or not an IPv4 address
263 // */
264 // public static String toStringDottedQuad(final InetAddress addr)
265 // throws IllegalArgumentException
266 // {
267 // if(addr == null)
268 // { throw new IllegalArgumentException(); }
269 //
270 // final byte raw[] = addr.getAddress();
271 //
272 // if(raw.length != 4)
273 // { throw new IllegalArgumentException("not an IPv4 address"); }
274 //
275 // final StringBuilder sb = new StringBuilder(15);
276 // for(int i = 0; i < 4; ++i)
277 // {
278 // if(sb.length() != 0) { sb.append('.'); }
279 // sb.append(raw[i] & 0xff);
280 // }
281 //
282 // return(sb.toString());
283 // }
284
285 /**Convert an (IPv4) InetAddress to reverse dotted-quad form with a trailing dot.
286 * This can be useful for RBL and reverse lookups.
287 * <p>
288 * Avoid doing any DNS lookup if at all possible.
289 *
290 * @param addr parameter to convert to reverse dotted-quad;
291 * must be non-null IPv4 address
292 *
293 * @throws IllegalArgumentException if addr is null or not an IPv4 address
294 */
295 public static String toStringReverseDottedQuad(final InetAddress addr)
296 throws IllegalArgumentException
297 {
298 if(addr == null)
299 { throw new IllegalArgumentException(); }
300
301 final byte raw[] = addr.getAddress();
302
303 if(raw.length != 4)
304 { throw new IllegalArgumentException("not an IPv4 address"); }
305
306 final StringBuilder sb = new StringBuilder(16);
307 for(int i = raw.length; --i >= 0; )
308 {
309 sb.append(raw[i] & 0xff).append('.');
310 }
311
312 return(sb.toString());
313 }
314
315 /**Do reverse lookup on IP address to get the name, returns null if lookup fails.
316 * This can optionally verify the name by trying to look up the name it
317 * found and making sure that at least one of the IPs returned matches.
318 * <p>
319 * This avoids the built-in JVM lookup routines to avoid the default
320 * infinite cacheing that it does for class-loading safety.
321 * <p>
322 * Blocks until it has an answer or times out.
323 *
324 * @param addr IP address to look up as numeric address; never null
325 * @param verify if true, attempt to verify with forward lookup of
326 * the putative result, returning null if no suitable match is found
327 */
328 public static String doReverseLookup(final String addr,
329 final boolean verify)
330 {
331 if(addr == null)
332 { throw new IllegalArgumentException(); }
333
334 try { return(doReverseLookup(InetAddress.getByName(addr), verify)); }
335 // Return null for an unparsable address.
336 catch(final UnknownHostException e) { return(null); }
337 }
338
339 /**Do reverse lookup on IP address to get the name, returns null if lookup fails.
340 * This can optionally verify the name by trying to look up the name it
341 * found and making sure that at least one of the IPs returned matches.
342 * <p>
343 * This avoids the built-in JVM lookup routines to avoid the default
344 * infinite cacheing that it does for class-loading safety.
345 * <p>
346 * Blocks until it has an answer or times out.
347 *
348 * @param addr IP address to look up; never null
349 * @param verify if true, attempt to verify with forward lookup of
350 * the putative result, returning null if no suitable match is found
351 */
352 public static String doReverseLookup(final InetAddress addr,
353 final boolean verify)
354 {
355 if(addr == null)
356 { throw new IllegalArgumentException(); }
357
358 // // Special case for loopback address
359 // // to avoid going to DNS
360 // // which should enhance speed and robustness.
361 // //
362 // // This does not need verification.
363 // if(isLoopbackAddress(addr))
364 // { return(DEFAULT_IPV4_LOOPBACK_CANON_NAME); }
365
366 // Options.set("verbose"); // Make DNS java talkative.
367
368 //System.err.println("Doing reverse lookup for address: " + toStringDottedQuad(addr));
369 try
370 {
371 // Do the reverse lookupRev...
372 // final String result = Address.getHostName(addr);
373 // Use our tuned cache to do it.
374 final Name name = ReverseMap.fromAddress(addr);
375 final Lookup lookupRev = new Lookup(name, Type.PTR);
376 final Record recordsRev[] = doQuickLookupWithTunedCache(lookupRev);
377 if((recordsRev == null) || (recordsRev.length < 1))
378 { throw new UnknownHostException("unknown address: " + addr.getHostAddress()); }
379 final PTRRecord ptr = (PTRRecord) recordsRev[0];
380 final String result = ptr.getTarget().toString();
381
382 //System.err.println(" Reverse lookupRev result was: " + result);
383
384 // If not verifying, return the result immediately.
385 if(!verify) { return(result); }
386
387 // If verifying, check against all addresses for the forward lookup.
388 // final InetAddress addrs[] = Address.getAllByName(result);
389 // Use our tuned cache.
390 final Lookup lookupFwd = new Lookup(result, Type.A);
391 final Record recordsFwd[] = doQuickLookupWithTunedCache(lookupFwd);
392 if((recordsFwd == null) || (recordsFwd.length < 1))
393 { throw new UnknownHostException("unknown host: " + result); }
394 final InetAddress[] addrs = new InetAddress[recordsFwd.length];
395 for(int i = addrs.length; --i >= 0; )
396 {
397 final ARecord a = (ARecord) recordsFwd[i];
398 addrs[i] = a.getAddress();
399 }
400 //System.err.println(" Verifying, forward lookupRev answers: " + addrs.length);
401 for(int i = addrs.length; --i >= 0; )
402 {
403 // If an address matched then the address is verified.
404 if(addr.equals(addrs[i])) { return(result); }
405 }
406
407 return(null); // Failed to verify the address.
408 }
409 catch(final UnknownHostException e)
410 {
411 // Lookup failed.
412 //System.err.println(" Lookup failed: " + e.getMessage());
413 return(null);
414 }
415 catch(final TextParseException e)
416 {
417 //System.err.println(" Lookup failed: " + e.getMessage());
418 return(null);
419 }
420 }
421
422 /**Check an (IPv4) IP address with the RBL servers for being "black-holed".
423 * For an IPv4 address of the numerical form a.b.c.d,
424 * list does a lookup for an A record for d.c.b.a.RBL.domain,
425 * and if it finds one, the client address is "bad".
426 * <p>
427 * We may do these checks serially, or in parallel for speed.
428 * We may pick one RBL server at random each time for speed.
429 * The first suitable A record returned stops the search.
430 * <p>
431 * We may randomise the order in which we do lookup to spread
432 * the load amongst the RBL servers more fairly.
433 * <p>
434 * FIXME: For now, always returns null for non-IPv4 addresses.
435 *
436 * @param quick if true, check just one of the BLs at random
437 *
438 * @return name of one BL server that black-holed address if so,
439 * null if address is OK
440 *
441 * @throws IllegalArgumentException if given a null address
442 */
443 public static final String isAddrBlackholed(final Collection<String> extantRBLServers,
444 final InetAddress addr,
445 final boolean quick)
446 throws IllegalArgumentException
447 {
448 if((addr == null) || (extantRBLServers == null))
449 { throw new IllegalArgumentException(); }
450
451 final byte rawAddr[] = addr.getAddress();
452
453 // Can only do this for IPv4 addresses for now.
454 if(rawAddr.length != 4)
455 { return(null); }
456
457 // Return null immediately if no servers available.
458 final int nServers = extantRBLServers.size();
459 if(nServers == 0) { return(null); }
460
461 // Create the reverse dotted-quad address plus trailing dot.
462 final String prefix = toStringReverseDottedQuad(addr);
463
464 // If there is exactly one DNS BL server then check it immediately.
465 if(nServers == 1) { return(_checkOneAddrInDNSBL(prefix, extantRBLServers.iterator().next())); }
466
467 // The iterator for the RBL servers to test.
468 final Iterator<String> serverIt;
469
470 if(quick)
471 {
472 // Try just one of the RBL servers at random for speed.
473 serverIt = Collections.singletonList(
474 ((extantRBLServers instanceof List) ? (List<String>)extantRBLServers : new ArrayList<String>(extantRBLServers)).
475 get(Rnd.fastRnd.nextInt(nServers))).iterator();
476 return(_checkOneAddrInDNSBL(prefix, serverIt.next()));
477 }
478 else if(RANDOMISE_RBL_LOOKUP_ORDER)
479 {
480 // Try all RBL servers, but in a random order.
481 final List<String> l = new ArrayList<String>(extantRBLServers);
482 Collections.shuffle(l, Rnd.fastRnd);
483 serverIt = l.iterator();
484 }
485 else
486 {
487 // Try all RBL servers in the order given.
488 serverIt = extantRBLServers.iterator();
489 }
490
491 // Check the DNS BL servers concurrently using our I/O-bound thread pool.
492 final List<Future<String>> pending = new ArrayList<Future<String>>(nServers);
493 while(serverIt.hasNext())
494 {
495 final String server = serverIt.next();
496 ThreadUtils.nonCPUThreadPool.submit(new Callable<String>(){
497 public final String call() throws Exception
498 { return(_checkOneAddrInDNSBL(prefix, server)); }
499 });
500 }
501
502 // Collect the results.
503 for(final Future<String> f : pending)
504 {
505 try
506 {
507 final String server = f.get();
508 // As soon as we find a DNS BL that lists this client,
509 // stop and return the DNS BL server name,
510 // since the client is blacklisted!
511 if(null != server) { return(server); }
512 }
513 catch(final Exception e)
514 {
515 // Log the error, but absorb/ignore it.
516 e.printStackTrace();
517 }
518 }
519
520 return(null); // No, this address is fine.
521 }
522
523 /**Look up one address in DNSBL.
524 */
525 private static String _checkOneAddrInDNSBL(final String prefix, final String server)
526 {
527 final String fqdn = prefix + server + '.'; // Make absolute.
528
529 // If we can find an A record,
530 // then this address is black-holed.
531 return(hasARecordQuick(fqdn) ? server : null);
532 }
533
534
535 /**Immutable store of a non-null, non-zero-length unsigned-byte IP(v4) address prefix.
536 */
537 public static final class AddrPrefix implements Comparable<AddrPrefix>,
538 MemoryTools.Internable
539 {
540 /**Create an instance from a non-null, non-zero-length byte array.
541 * Takes a copy of the prefix data.
542 * @param addrPrefix prefix of address; non-null
543 */
544 public AddrPrefix(final byte addrPrefix[])
545 {
546 if((addrPrefix == null) || (addrPrefix.length < 1))
547 { throw new IllegalArgumentException(); }
548 prefix = addrPrefix.clone();
549 }
550
551 /**Create an instance from the prefix of a non-null, non-zero-length byte array. */
552 public AddrPrefix(final byte addrPrefix[], final int len)
553 {
554 if((addrPrefix == null) ||
555 (len < 1) || (len > addrPrefix.length))
556 { throw new IllegalArgumentException(); }
557 prefix = new byte[len];
558 for(int i = len; --i >= 0; ) { prefix[i] = addrPrefix[i]; }
559 }
560
561 /**Create a shorter (but non-zero-length) instance from an existing prefix. */
562 public AddrPrefix(final AddrPrefix ap, final int len)
563 {
564 if((ap == null) ||
565 (len < 1) || (len >= ap.prefix.length))
566 { throw new IllegalArgumentException(); }
567 prefix = new byte[len];
568 for(int i = len; --i >= 0; ) { prefix[i] = ap.prefix[i]; }
569 }
570
571 /**Create an instance by parsing a padded dotted prefix format.
572 * This is tolerant and does not insist that the octets
573 * are padded with zeros on the left.
574 * <p>
575 * Can be performance-critical, especially at start-up,
576 * so hand-crafted for speed and to avoid creating unnecessary objects.
577 *
578 * @param s dotted prefix of form n(.n)* eg 127.0.0 or 10.0 or 10.000;
579 * there must be at least one octet,
580 * and each octet must be between 1 and 3 digits long
581 *
582 * @throws IllegalArgumentException if the value is unparsable
583 * or not at least one octet
584 */
585 public AddrPrefix(final String s)
586 throws IllegalArgumentException
587 {
588 if(s == null)
589 { throw new IllegalArgumentException(); }
590 final int sl = s.length();
591 if(sl < 1)
592 { throw new IllegalArgumentException(); }
593
594 // Count the internal delimiter dots.
595 // (There should not be dots in the first or last positions,
596 // nor adjacent to one another.)
597 int nDots = 0;
598 for(int i = sl-1; --i > 0; )
599 { if('.' == s.charAt(i)) { ++nDots; --i; } }
600 final int prefixLength = 1 + nDots;
601 final byte[] d = new byte[prefixLength];
602
603 // Work backwards through the array
604 // collecting one octet per loop.
605 int index = prefixLength;
606 for(int i = sl; --i >= 0; )
607 {
608 final char lastDigit = s.charAt(i--);
609 if((lastDigit < '0') || (lastDigit > '9'))
610 { throw new IllegalArgumentException("last octet digit invalid: '" + lastDigit + "' at index " +(i+1) + " in \"" + s + "\" with prefixLength="+prefixLength); }
611 int octet = lastDigit - '0';
612
613 // We're done if we run out of input String
614 // (and this must be the first octet).
615 if(i < 0) { d[0] = (byte)octet; break; }
616 final char digit2 = s.charAt(i);
617 // We're done for this this octet if we hit a dot.
618 if('.' == digit2) { d[--index] = (byte)octet; continue; }
619 if((digit2 < '0') || (digit2 > '9'))
620 { throw new IllegalArgumentException("digit2 invalid"); }
621 octet += 10 * (digit2 - '0');
622
623 // We're done if we run out of input String
624 // (and this must be the first octet).
625 if(i <= 0) { d[0] = (byte)octet; break; }
626 final char digit3 = s.charAt(--i);
627 // We're done for this this octet if we hit a dot.
628 if('.' == digit3) { d[--index] = (byte)octet; continue; }
629 if((digit3 < '0') || (digit3 > '2'))
630 { throw new IllegalArgumentException("digit3 invalid"); }
631 octet += 100 * (digit3 - '0');
632 if(octet > 255)
633 { throw new IllegalArgumentException("octet > 255"); }
634 d[--index] = (byte)octet;
635
636 // Check for presence of delimiter dot if input not finished.
637 if((i > 1) && ('.' != s.charAt(--i)))
638 { throw new IllegalArgumentException("missing ."); }
639 }
640
641 prefix = d;
642 }
643
644 /**Address prefix, non-zero-length, non-null. */
645 private final byte prefix[];
646
647 /**Get the prefix length, in bytes; strictly positive. */
648 public int length()
649 { return(prefix.length); }
650
651 /**Returns true if the argument is a strict prefix of this value. */
652 public boolean isStrictPrefix(final AddrPrefix other)
653 {
654 final int apLen = other.prefix.length;
655 if(apLen >= prefix.length) { return(false); }
656 for(int i = apLen; --i >= 0; )
657 { if(other.prefix[i] != prefix[i]) { return(false); } }
658 return(true);
659 }
660
661 /**Sorted as if in a dictionary with the bytes treated as unsigned. */
662 public int compareTo(final AddrPrefix other)
663 {
664 final int minLen = Math.min(prefix.length, other.prefix.length);
665 for(int i = 0; i < minLen; ++i)
666 {
667 final int diff = (prefix[i] & 0xff) - (other.prefix[i] & 0xff);
668 if(diff != 0) { return(diff); }
669 }
670
671 // Equal in their common portion, so the shorter one sorts first.
672 return(prefix.length - other.prefix.length);
673 }
674
675 /**Compute hash based on the assumption that most prefixes are 1--3 bytes long.
676 * All bytes should be involved in the hash for it to be effective
677 * since prefixes are likely to be dense in maps, etc.
678 */
679 @Override
680 public int hashCode()
681 {
682 final int length = prefix.length;
683 // For CPU efficiency, and for the quality of the generated hash,
684 // deal with the common short prefixes specially.
685 // In each case, we assume that the last byte is the most "noisy".
686 switch(length)
687 {
688 case 1: { return(prefix[0]); }
689 case 2: { return(prefix[1] ^ ((131+prefix[0]) * 271)); }
690 case 3: { return(prefix[2] + ((prefix[0]-129) * 82193) + (prefix[1] * 263)); }
691 }
692 // Default (general) case, using all prefix bytes.
693 return(Arrays.hashCode(prefix));
694 }
695
696 /**Equal if the prefixes are the same length and have the same content. */
697 @Override
698 public boolean equals(final Object obj)
699 {
700 if(this == obj) { return(true); }
701 if(!(obj instanceof AddrPrefix)) { return(false); }
702 final AddrPrefix other = ((AddrPrefix)obj);
703 final int length = prefix.length;
704 if(length != other.prefix.length) { return(false); }
705 for(int i = length; --i >= 0; )
706 { if(prefix[i] != other.prefix[i]) { return(false); } }
707 return(true); // Identical.
708 }
709
710 /**Get a copy of the byte[] prefix data; never null. */
711 public byte[] toByteArray()
712 { return(prefix.clone()); }
713
714 /**Print as padded dotted prefix; never null. */
715 public String toPaddedDottedPrefix()
716 {
717 final StringBuilder sb = new StringBuilder(prefix.length * 4);
718 final StringBuilder octet = new StringBuilder(3);
719 for(int i = 0; i < prefix.length; ++i)
720 {
721 octet.setLength(0);
722 octet.append(prefix[i] & 0xff);
723 while(octet.length() < 3) { octet.insert(0, '0'); }
724 if(sb.length() > 0) { sb.append('.'); }
725 sb.append(octet);
726 }
727 return(sb.toString());
728 }
729
730 /**Human-readable representation; currently equivalent to toPaddedDottedPrefix(); never null. */
731 @Override
732 public String toString()
733 { return(toPaddedDottedPrefix()); }
734 }
735 }