001: // Copyright (c) 1999-2004 Brian Wellington (bwelling@xbill.org)
002:
003: package org.xbill.DNS;
004:
005: import java.io.*;
006: import java.text.*;
007:
008: /**
009: * A representation of a domain name. It may either be absolute (fully
010: * qualified) or relative.
011: *
012: * @author Brian Wellington
013: */
014:
015: public class Name implements Comparable {
016:
017: private static final int LABEL_NORMAL = 0;
018: private static final int LABEL_COMPRESSION = 0xC0;
019: private static final int LABEL_MASK = 0xC0;
020:
021: /* The name data */
022: private byte[] name;
023:
024: /*
025: * Effectively an 8 byte array, where the low order byte stores the number
026: * of labels and the 7 higher order bytes store per-label offsets.
027: */
028: private long offsets;
029:
030: /* Precomputed hashcode. */
031: private int hashcode;
032:
033: private static final byte[] emptyLabel = new byte[] { (byte) 0 };
034: private static final byte[] wildLabel = new byte[] { (byte) 1,
035: (byte) '*' };
036:
037: /** The root name */
038: public static final Name root;
039:
040: /** The root name */
041: public static final Name empty;
042:
043: /** The maximum length of a Name */
044: private static final int MAXNAME = 255;
045:
046: /** The maximum length of a label a Name */
047: private static final int MAXLABEL = 63;
048:
049: /** The maximum number of labels in a Name */
050: private static final int MAXLABELS = 128;
051:
052: /** The maximum number of cached offsets */
053: private static final int MAXOFFSETS = 7;
054:
055: /* Used for printing non-printable characters */
056: private static final DecimalFormat byteFormat = new DecimalFormat();
057:
058: /* Used to efficiently convert bytes to lowercase */
059: private static final byte lowercase[] = new byte[256];
060:
061: /* Used in wildcard names. */
062: private static final Name wild;
063:
064: static {
065: byteFormat.setMinimumIntegerDigits(3);
066: for (int i = 0; i < lowercase.length; i++) {
067: if (i < 'A' || i > 'Z')
068: lowercase[i] = (byte) i;
069: else
070: lowercase[i] = (byte) (i - 'A' + 'a');
071: }
072: root = new Name();
073: root.appendSafe(emptyLabel, 0, 1);
074: empty = new Name();
075: empty.name = new byte[0];
076: wild = new Name();
077: wild.appendSafe(wildLabel, 0, 1);
078: }
079:
080: private Name() {
081: }
082:
083: private final void dump(String prefix) {
084: String s;
085: try {
086: s = toString();
087: } catch (Exception e) {
088: s = "<unprintable>";
089: }
090: System.out.println(prefix + ": " + s);
091:
092: int labels = labels();
093: for (int i = 0; i < labels; i++)
094: System.out.print(offset(i) + " ");
095: System.out.println("");
096:
097: for (int i = 0; name != null && i < name.length; i++)
098: System.out.print((name[i] & 0xFF) + " ");
099: System.out.println("");
100: }
101:
102: private final void setoffset(int n, int offset) {
103: if (n >= MAXOFFSETS)
104: return;
105: int shift = 8 * (7 - n);
106: offsets &= (~(0xFFL << shift));
107: offsets |= ((long) offset << shift);
108: }
109:
110: private final int offset(int n) {
111: if (n == 0 && getlabels() == 0)
112: return 0;
113: if (n < 0 || n >= getlabels())
114: throw new IllegalArgumentException("label out of range");
115: if (n < MAXOFFSETS) {
116: int shift = 8 * (7 - n);
117: return ((int) (offsets >>> shift) & 0xFF);
118: } else {
119: int pos = offset(MAXOFFSETS - 1);
120: for (int i = MAXOFFSETS - 1; i < n; i++)
121: pos += (name[pos] + 1);
122: return (pos);
123: }
124: }
125:
126: private final void setlabels(int labels) {
127: offsets &= ~(0xFF);
128: offsets |= labels;
129: }
130:
131: private final int getlabels() {
132: return (int) (offsets & 0xFF);
133: }
134:
135: private static final void copy(Name src, Name dst) {
136: if (src.offset(0) == 0) {
137: dst.name = src.name;
138: dst.offsets = src.offsets;
139: } else {
140: int offset0 = src.offset(0);
141: int namelen = src.name.length - offset0;
142: int labels = src.labels();
143: dst.name = new byte[namelen];
144: System.arraycopy(src.name, offset0, dst.name, 0, namelen);
145: for (int i = 0; i < labels && i < MAXOFFSETS; i++)
146: dst.setoffset(i, src.offset(i) - offset0);
147: dst.setlabels(labels);
148: }
149: }
150:
151: private final void append(byte[] array, int start, int n)
152: throws NameTooLongException {
153: int length = (name == null ? 0 : (name.length - offset(0)));
154: int alength = 0;
155: for (int i = 0, pos = start; i < n; i++) {
156: int len = array[pos];
157: if (len > MAXLABEL)
158: throw new IllegalStateException("invalid label");
159: len++;
160: pos += len;
161: alength += len;
162: }
163: int newlength = length + alength;
164: if (newlength > MAXNAME)
165: throw new NameTooLongException();
166: int labels = getlabels();
167: int newlabels = labels + n;
168: if (newlabels > MAXLABELS)
169: throw new IllegalStateException("too many labels");
170: byte[] newname = new byte[newlength];
171: if (length != 0)
172: System.arraycopy(name, offset(0), newname, 0, length);
173: System.arraycopy(array, start, newname, length, alength);
174: name = newname;
175: for (int i = 0, pos = length; i < n; i++) {
176: setoffset(labels + i, pos);
177: pos += (newname[pos] + 1);
178: }
179: setlabels(newlabels);
180: }
181:
182: private static TextParseException parseException(String str,
183: String message) {
184: return new TextParseException("'" + str + "': " + message);
185: }
186:
187: private final void appendFromString(String fullName, byte[] array,
188: int start, int n) throws TextParseException {
189: try {
190: append(array, start, n);
191: } catch (NameTooLongException e) {
192: throw parseException(fullName, "Name too long");
193: }
194: }
195:
196: private final void appendSafe(byte[] array, int start, int n) {
197: try {
198: append(array, start, n);
199: } catch (NameTooLongException e) {
200: }
201: }
202:
203: /**
204: * Create a new name from a string and an origin. This does not automatically
205: * make the name absolute; it will be absolute if it has a trailing dot or an
206: * absolute origin is appended.
207: * @param s The string to be converted
208: * @param origin If the name is not absolute, the origin to be appended.
209: * @throws TextParseException The name is invalid.
210: */
211: public Name(String s, Name origin) throws TextParseException {
212: if (s.equals(""))
213: throw parseException(s, "empty name");
214: else if (s.equals("@")) {
215: if (origin == null)
216: copy(empty, this );
217: else
218: copy(origin, this );
219: return;
220: } else if (s.equals(".")) {
221: copy(root, this );
222: return;
223: }
224: int labelstart = -1;
225: int pos = 1;
226: byte[] label = new byte[MAXLABEL + 1];
227: boolean escaped = false;
228: int digits = 0;
229: int intval = 0;
230: boolean absolute = false;
231: for (int i = 0; i < s.length(); i++) {
232: byte b = (byte) s.charAt(i);
233: if (escaped) {
234: if (b >= '0' && b <= '9' && digits < 3) {
235: digits++;
236: intval *= 10;
237: intval += (b - '0');
238: if (intval > 255)
239: throw parseException(s, "bad escape");
240: if (digits < 3)
241: continue;
242: b = (byte) intval;
243: } else if (digits > 0 && digits < 3)
244: throw parseException(s, "bad escape");
245: if (pos > MAXLABEL)
246: throw parseException(s, "label too long");
247: labelstart = pos;
248: label[pos++] = b;
249: escaped = false;
250: } else if (b == '\\') {
251: escaped = true;
252: digits = 0;
253: intval = 0;
254: } else if (b == '.') {
255: if (labelstart == -1)
256: throw parseException(s, "invalid empty label");
257: label[0] = (byte) (pos - 1);
258: appendFromString(s, label, 0, 1);
259: labelstart = -1;
260: pos = 1;
261: } else {
262: if (labelstart == -1)
263: labelstart = i;
264: if (pos > MAXLABEL)
265: throw parseException(s, "label too long");
266: label[pos++] = b;
267: }
268: }
269: if (digits > 0 && digits < 3)
270: throw parseException(s, "bad escape");
271: if (escaped)
272: throw parseException(s, "bad escape");
273: if (labelstart == -1) {
274: appendFromString(s, emptyLabel, 0, 1);
275: absolute = true;
276: } else {
277: label[0] = (byte) (pos - 1);
278: appendFromString(s, label, 0, 1);
279: }
280: if (origin != null && !absolute)
281: appendFromString(s, origin.name, 0, origin.getlabels());
282: }
283:
284: /**
285: * Create a new name from a string. This does not automatically make the name
286: * absolute; it will be absolute if it has a trailing dot.
287: * @param s The string to be converted
288: * @throws TextParseException The name is invalid.
289: */
290: public Name(String s) throws TextParseException {
291: this (s, null);
292: }
293:
294: /**
295: * Create a new name from a string and an origin. This does not automatically
296: * make the name absolute; it will be absolute if it has a trailing dot or an
297: * absolute origin is appended. This is identical to the constructor, except
298: * that it will avoid creating new objects in some cases.
299: * @param s The string to be converted
300: * @param origin If the name is not absolute, the origin to be appended.
301: * @throws TextParseException The name is invalid.
302: */
303: public static Name fromString(String s, Name origin)
304: throws TextParseException {
305: if (s.equals("@") && origin != null)
306: return origin;
307: else if (s.equals("."))
308: return (root);
309:
310: return new Name(s, origin);
311: }
312:
313: /**
314: * Create a new name from a string. This does not automatically make the name
315: * absolute; it will be absolute if it has a trailing dot. This is identical
316: * to the constructor, except that it will avoid creating new objects in some
317: * cases.
318: * @param s The string to be converted
319: * @throws TextParseException The name is invalid.
320: */
321: public static Name fromString(String s) throws TextParseException {
322: return fromString(s, null);
323: }
324:
325: /**
326: * Create a new name from a constant string. This should only be used when
327: the name is known to be good - that is, when it is constant.
328: * @param s The string to be converted
329: * @throws IllegalArgumentException The name is invalid.
330: */
331: public static Name fromConstantString(String s) {
332: try {
333: return fromString(s, null);
334: } catch (TextParseException e) {
335: throw new IllegalArgumentException("Invalid name '" + s
336: + "'");
337: }
338: }
339:
340: /**
341: * Create a new name from DNS a wire format message
342: * @param in A stream containing the DNS message which is currently
343: * positioned at the start of the name to be read.
344: */
345: public Name(DNSInput in) throws WireParseException {
346: int len, pos, currentpos;
347: Name name2;
348: boolean done = false;
349: byte[] label = new byte[MAXLABEL + 1];
350: boolean savedState = false;
351:
352: while (!done) {
353: len = in.readU8();
354: switch (len & LABEL_MASK) {
355: case LABEL_NORMAL:
356: if (getlabels() >= MAXLABELS)
357: throw new WireParseException("too many labels");
358: if (len == 0) {
359: append(emptyLabel, 0, 1);
360: done = true;
361: } else {
362: label[0] = (byte) len;
363: in.readByteArray(label, 1, len);
364: append(label, 0, 1);
365: }
366: break;
367: case LABEL_COMPRESSION:
368: pos = in.readU8();
369: pos += ((len & ~LABEL_MASK) << 8);
370: if (Options.check("verbosecompression"))
371: System.err.println("currently " + in.current()
372: + ", pointer to " + pos);
373:
374: if (pos >= in.current() - 2)
375: throw new WireParseException("bad compression");
376: if (!savedState) {
377: in.save();
378: savedState = true;
379: }
380: in.jump(pos);
381: if (Options.check("verbosecompression"))
382: System.err.println("current name '" + this
383: + "', seeking to " + pos);
384: break;
385: default:
386: throw new WireParseException("bad label type");
387: }
388: }
389: if (savedState) {
390: in.restore();
391: }
392: }
393:
394: /**
395: * Create a new name from DNS wire format
396: * @param b A byte array containing the wire format of the name.
397: */
398: public Name(byte[] b) throws IOException {
399: this (new DNSInput(b));
400: }
401:
402: /**
403: * Create a new name by removing labels from the beginning of an existing Name
404: * @param src An existing Name
405: * @param n The number of labels to remove from the beginning in the copy
406: */
407: public Name(Name src, int n) {
408: int slabels = src.labels();
409: if (n > slabels)
410: throw new IllegalArgumentException(
411: "attempted to remove too " + "many labels");
412: name = src.name;
413: setlabels(slabels - n);
414: for (int i = 0; i < MAXOFFSETS && i < slabels - n; i++)
415: setoffset(i, src.offset(i + n));
416: }
417:
418: /**
419: * Creates a new name by concatenating two existing names.
420: * @param prefix The prefix name.
421: * @param suffix The suffix name.
422: * @return The concatenated name.
423: * @throws NameTooLongException The name is too long.
424: */
425: public static Name concatenate(Name prefix, Name suffix)
426: throws NameTooLongException {
427: if (prefix.isAbsolute())
428: return (prefix);
429: Name newname = new Name();
430: copy(prefix, newname);
431: newname.append(suffix.name, suffix.offset(0), suffix
432: .getlabels());
433: return newname;
434: }
435:
436: /**
437: * If this name is a subdomain of origin, return a new name relative to
438: * origin with the same value. Otherwise, return the existing name.
439: * @param origin The origin to remove.
440: * @return The possibly relativized name.
441: */
442: public Name relativize(Name origin) {
443: if (origin == null || !subdomain(origin))
444: return this ;
445: Name newname = new Name();
446: copy(this , newname);
447: int length = length() - origin.length();
448: int labels = newname.labels() - origin.labels();
449: newname.setlabels(labels);
450: newname.name = new byte[length];
451: System.arraycopy(name, offset(0), newname.name, 0, length);
452: return newname;
453: }
454:
455: /**
456: * Generates a new Name with the first n labels replaced by a wildcard
457: * @return The wildcard name
458: */
459: public Name wild(int n) {
460: if (n < 1)
461: throw new IllegalArgumentException(
462: "must replace 1 or more " + "labels");
463: try {
464: Name newname = new Name();
465: copy(wild, newname);
466: newname.append(name, offset(n), getlabels() - n);
467: return newname;
468: } catch (NameTooLongException e) {
469: throw new IllegalStateException(
470: "Name.wild: concatenate failed");
471: }
472: }
473:
474: /**
475: * Generates a new Name to be used when following a DNAME.
476: * @param dname The DNAME record to follow.
477: * @return The constructed name.
478: * @throws NameTooLongException The resulting name is too long.
479: */
480: public Name fromDNAME(DNAMERecord dname)
481: throws NameTooLongException {
482: Name dnameowner = dname.getName();
483: Name dnametarget = dname.getTarget();
484: if (!subdomain(dnameowner))
485: return null;
486:
487: int plabels = labels() - dnameowner.labels();
488: int plength = length() - dnameowner.length();
489: int pstart = offset(0);
490:
491: int dlabels = dnametarget.labels();
492: int dlength = dnametarget.length();
493:
494: if (plength + dlength > MAXNAME)
495: throw new NameTooLongException();
496:
497: Name newname = new Name();
498: newname.setlabels(plabels + dlabels);
499: newname.name = new byte[plength + dlength];
500: System.arraycopy(name, pstart, newname.name, 0, plength);
501: System.arraycopy(dnametarget.name, 0, newname.name, plength,
502: dlength);
503:
504: for (int i = 0, pos = 0; i < MAXOFFSETS
505: && i < plabels + dlabels; i++) {
506: newname.setoffset(i, pos);
507: pos += (newname.name[pos] + 1);
508: }
509: return newname;
510: }
511:
512: /**
513: * Is this name a wildcard?
514: */
515: public boolean isWild() {
516: if (labels() == 0)
517: return false;
518: return (name[0] == (byte) 1 && name[1] == (byte) '*');
519: }
520:
521: /**
522: * Is this name absolute?
523: */
524: public boolean isAbsolute() {
525: if (labels() == 0)
526: return false;
527: return (name[name.length - 1] == 0);
528: }
529:
530: /**
531: * The length of the name.
532: */
533: public short length() {
534: if (getlabels() == 0)
535: return 0;
536: return (short) (name.length - offset(0));
537: }
538:
539: /**
540: * The number of labels in the name.
541: */
542: public int labels() {
543: return getlabels();
544: }
545:
546: /**
547: * Is the current Name a subdomain of the specified name?
548: */
549: public boolean subdomain(Name domain) {
550: int labels = labels();
551: int dlabels = domain.labels();
552: if (dlabels > labels)
553: return false;
554: if (dlabels == labels)
555: return equals(domain);
556: return domain.equals(name, offset(labels - dlabels));
557: }
558:
559: private String byteString(byte[] array, int pos) {
560: StringBuffer sb = new StringBuffer();
561: int len = array[pos++];
562: for (int i = pos; i < pos + len; i++) {
563: int b = array[i] & 0xFF;
564: if (b <= 0x20 || b >= 0x7f) {
565: sb.append('\\');
566: sb.append(byteFormat.format(b));
567: } else if (b == '"' || b == '(' || b == ')' || b == '.'
568: || b == ';' || b == '\\' || b == '@' || b == '$') {
569: sb.append('\\');
570: sb.append((char) b);
571: } else
572: sb.append((char) b);
573: }
574: return sb.toString();
575: }
576:
577: /**
578: * Convert a Name to a String
579: * @return The representation of this name as a (printable) String.
580: */
581: public String toString() {
582: int labels = labels();
583: if (labels == 0)
584: return "@";
585: else if (labels == 1 && name[offset(0)] == 0)
586: return ".";
587: StringBuffer sb = new StringBuffer();
588: for (int i = 0, pos = offset(0); i < labels; i++) {
589: int len = name[pos];
590: if (len > MAXLABEL)
591: throw new IllegalStateException("invalid label");
592: if (len == 0)
593: break;
594: sb.append(byteString(name, pos));
595: sb.append('.');
596: pos += (1 + len);
597: }
598: if (!isAbsolute())
599: sb.deleteCharAt(sb.length() - 1);
600: return sb.toString();
601: }
602:
603: /**
604: * Retrieve the nth label of a Name. This makes a copy of the label; changing
605: * this does not change the Name.
606: * @param n The label to be retrieved. The first label is 0.
607: */
608: public byte[] getLabel(int n) {
609: int pos = offset(n);
610: byte len = (byte) (name[pos] + 1);
611: byte[] label = new byte[len];
612: System.arraycopy(name, pos, label, 0, len);
613: return label;
614: }
615:
616: /**
617: * Convert the nth label in a Name to a String
618: * @param n The label to be converted to a (printable) String. The first
619: * label is 0.
620: */
621: public String getLabelString(int n) {
622: int pos = offset(n);
623: return byteString(name, pos);
624: }
625:
626: /**
627: * Emit a Name in DNS wire format
628: * @param out The output stream containing the DNS message.
629: * @param c The compression context, or null of no compression is desired.
630: * @throws IllegalArgumentException The name is not absolute.
631: */
632: public void toWire(DNSOutput out, Compression c) {
633: if (!isAbsolute())
634: throw new IllegalArgumentException("toWire() called on "
635: + "non-absolute name");
636:
637: int labels = labels();
638: for (int i = 0; i < labels - 1; i++) {
639: Name tname;
640: if (i == 0)
641: tname = this ;
642: else
643: tname = new Name(this , i);
644: int pos = -1;
645: if (c != null)
646: pos = c.get(tname);
647: if (pos >= 0) {
648: pos |= (LABEL_MASK << 8);
649: out.writeU16(pos);
650: return;
651: } else {
652: if (c != null)
653: c.add(out.current(), tname);
654: int off = offset(i);
655: out.writeByteArray(name, off, name[off] + 1);
656: }
657: }
658: out.writeU8(0);
659: }
660:
661: /**
662: * Emit a Name in DNS wire format
663: * @throws IllegalArgumentException The name is not absolute.
664: */
665: public byte[] toWire() {
666: DNSOutput out = new DNSOutput();
667: toWire(out, null);
668: return out.toByteArray();
669: }
670:
671: /**
672: * Emit a Name in canonical DNS wire format (all lowercase)
673: * @param out The output stream to which the message is written.
674: */
675: public void toWireCanonical(DNSOutput out) {
676: byte[] b = toWireCanonical();
677: out.writeByteArray(b);
678: }
679:
680: /**
681: * Emit a Name in canonical DNS wire format (all lowercase)
682: * @return The canonical form of the name.
683: */
684: public byte[] toWireCanonical() {
685: int labels = labels();
686: if (labels == 0)
687: return (new byte[0]);
688: byte[] b = new byte[name.length - offset(0)];
689: for (int i = 0, spos = offset(0), dpos = 0; i < labels; i++) {
690: int len = name[spos];
691: if (len > MAXLABEL)
692: throw new IllegalStateException("invalid label");
693: b[dpos++] = name[spos++];
694: for (int j = 0; j < len; j++)
695: b[dpos++] = lowercase[(name[spos++] & 0xFF)];
696: }
697: return b;
698: }
699:
700: /**
701: * Emit a Name in DNS wire format
702: * @param out The output stream containing the DNS message.
703: * @param c The compression context, or null of no compression is desired.
704: * @param canonical If true, emit the name in canonicalized form
705: * (all lowercase).
706: * @throws IllegalArgumentException The name is not absolute.
707: */
708: public void toWire(DNSOutput out, Compression c, boolean canonical) {
709: if (canonical)
710: toWireCanonical(out);
711: else
712: toWire(out, c);
713: }
714:
715: private final boolean equals(byte[] b, int bpos) {
716: int labels = labels();
717: for (int i = 0, pos = offset(0); i < labels; i++) {
718: if (name[pos] != b[bpos])
719: return false;
720: int len = name[pos++];
721: bpos++;
722: if (len > MAXLABEL)
723: throw new IllegalStateException("invalid label");
724: for (int j = 0; j < len; j++)
725: if (lowercase[(name[pos++] & 0xFF)] != lowercase[(b[bpos++] & 0xFF)])
726: return false;
727: }
728: return true;
729: }
730:
731: /**
732: * Are these two Names equivalent?
733: */
734: public boolean equals(Object arg) {
735: if (arg == this )
736: return true;
737: if (arg == null || !(arg instanceof Name))
738: return false;
739: Name d = (Name) arg;
740: if (d.hashcode == 0)
741: d.hashCode();
742: if (hashcode == 0)
743: hashCode();
744: if (d.hashcode != hashcode)
745: return false;
746: if (d.labels() != labels())
747: return false;
748: return equals(d.name, d.offset(0));
749: }
750:
751: /**
752: * Computes a hashcode based on the value
753: */
754: public int hashCode() {
755: if (hashcode != 0)
756: return (hashcode);
757: int code = 0;
758: for (int i = offset(0); i < name.length; i++)
759: code += ((code << 3) + lowercase[(name[i] & 0xFF)]);
760: hashcode = code;
761: return hashcode;
762: }
763:
764: /**
765: * Compares this Name to another Object.
766: * @param o The Object to be compared.
767: * @return The value 0 if the argument is a name equivalent to this name;
768: * a value less than 0 if the argument is less than this name in the canonical
769: * ordering, and a value greater than 0 if the argument is greater than this
770: * name in the canonical ordering.
771: * @throws ClassCastException if the argument is not a Name.
772: */
773: public int compareTo(Object o) {
774: Name arg = (Name) o;
775:
776: if (this == arg)
777: return (0);
778:
779: int labels = labels();
780: int alabels = arg.labels();
781: int compares = labels > alabels ? alabels : labels;
782:
783: for (int i = 1; i <= compares; i++) {
784: int start = offset(labels - i);
785: int astart = arg.offset(alabels - i);
786: int length = name[start];
787: int alength = arg.name[astart];
788: for (int j = 0; j < length && j < alength; j++) {
789: int n = lowercase[(name[j + start + 1]) & 0xFF]
790: - lowercase[(arg.name[j + astart + 1]) & 0xFF];
791: if (n != 0)
792: return (n);
793: }
794: if (length != alength)
795: return (length - alength);
796: }
797: return (labels - alabels);
798: }
799:
800: }
|