1/*	$NetBSD: ns_name.c,v 1.9 2012/03/13 21:13:39 christos Exp $	*/
2
3/*
4 * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
5 * Copyright (c) 1996,1999 by Internet Software Consortium.
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
17 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19
20#include <sys/cdefs.h>
21#ifndef lint
22#ifdef notdef
23static const char rcsid[] = "Id: ns_name.c,v 1.11 2009/01/23 19:59:16 each Exp";
24#else
25__RCSID("$NetBSD: ns_name.c,v 1.9 2012/03/13 21:13:39 christos Exp $");
26#endif
27#endif
28
29#include <sys/types.h>
30
31#include <netinet/in.h>
32#include <arpa/nameser.h>
33
34#include <assert.h>
35#include <errno.h>
36#ifdef ANDROID_CHANGES
37#include "resolv_private.h"
38#else
39#include <resolv.h>
40#endif
41#include <string.h>
42#include <ctype.h>
43#include <stdlib.h>
44#include <limits.h>
45
46#define NS_TYPE_ELT			0x40 /* EDNS0 extended label type */
47#define DNS_LABELTYPE_BITSTRING		0x41
48
49/* Data. */
50
51static const char	digits[] = "0123456789";
52
53static const char digitvalue[256] = {
54	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,	/*16*/
55	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*32*/
56	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*48*/
57	 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, /*64*/
58	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*80*/
59	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*96*/
60	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*112*/
61	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*128*/
62	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
63	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
64	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
65	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
66	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
67	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
68	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
69	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*256*/
70};
71
72/* Forward. */
73
74static int		special(int);
75static int		printable(int);
76static int		dn_find(const u_char *, const u_char *,
77				const u_char * const *,
78				const u_char * const *);
79static int		encode_bitsring(const char **, const char *,
80					unsigned char **, unsigned char **,
81					unsigned const char *);
82static int		labellen(const u_char *);
83static int		decode_bitstring(const unsigned char **,
84					 char *, const char *);
85
86/* Public. */
87
88/*
89 *	Convert an encoded domain name to printable ascii as per RFC1035.
90 * return:
91 *	Number of bytes written to buffer, or -1 (with errno set)
92 *
93 * notes:
94 *	The root is returned as "."
95 *	All other domains are returned in non absolute form
96 */
97int
98ns_name_ntop(const u_char *src, char *dst, size_t dstsiz)
99{
100	const u_char *cp;
101	char *dn, *eom;
102	u_char c;
103	u_int n;
104	int l;
105
106	cp = src;
107	dn = dst;
108	eom = dst + dstsiz;
109
110	while ((n = *cp++) != 0) {
111		if ((n & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
112			/* Some kind of compression pointer. */
113			errno = EMSGSIZE;
114			return (-1);
115		}
116		if (dn != dst) {
117			if (dn >= eom) {
118				errno = EMSGSIZE;
119				return (-1);
120			}
121			*dn++ = '.';
122		}
123		if ((l = labellen(cp - 1)) < 0) {
124			errno = EMSGSIZE; /* XXX */
125			return(-1);
126		}
127		if (dn + l >= eom) {
128			errno = EMSGSIZE;
129			return (-1);
130		}
131		if ((n & NS_CMPRSFLGS) == NS_TYPE_ELT) {
132			int m;
133
134			if (n != DNS_LABELTYPE_BITSTRING) {
135				/* XXX: labellen should reject this case */
136				errno = EINVAL;
137				return(-1);
138			}
139			if ((m = decode_bitstring(&cp, dn, eom)) < 0)
140			{
141				errno = EMSGSIZE;
142				return(-1);
143			}
144			dn += m;
145			continue;
146		}
147		for (; l > 0; l--) {
148			c = *cp++;
149			if (special(c)) {
150				if (dn + 1 >= eom) {
151					errno = EMSGSIZE;
152					return (-1);
153				}
154				*dn++ = '\\';
155				*dn++ = (char)c;
156			} else if (!printable(c)) {
157				if (dn + 3 >= eom) {
158					errno = EMSGSIZE;
159					return (-1);
160				}
161				*dn++ = '\\';
162				*dn++ = digits[c / 100];
163				*dn++ = digits[(c % 100) / 10];
164				*dn++ = digits[c % 10];
165			} else {
166				if (dn >= eom) {
167					errno = EMSGSIZE;
168					return (-1);
169				}
170				*dn++ = (char)c;
171			}
172		}
173	}
174	if (dn == dst) {
175		if (dn >= eom) {
176			errno = EMSGSIZE;
177			return (-1);
178		}
179		*dn++ = '.';
180	}
181	if (dn >= eom) {
182		errno = EMSGSIZE;
183		return (-1);
184	}
185	*dn++ = '\0';
186	_DIAGASSERT(__type_fit(int, dn - dst));
187	return (int)(dn - dst);
188}
189
190/*
191 *	Convert a ascii string into an encoded domain name as per RFC1035.
192 *
193 * return:
194 *
195 *	-1 if it fails
196 *	1 if string was fully qualified
197 *	0 is string was not fully qualified
198 *
199 * notes:
200 *	Enforces label and domain length limits.
201 */
202int
203ns_name_pton(const char *src, u_char *dst, size_t dstsiz) {
204	return (ns_name_pton2(src, dst, dstsiz, NULL));
205}
206
207/*
208 * ns_name_pton2(src, dst, dstsiz, *dstlen)
209 *	Convert a ascii string into an encoded domain name as per RFC1035.
210 * return:
211 *	-1 if it fails
212 *	1 if string was fully qualified
213 *	0 is string was not fully qualified
214 * side effects:
215 *	fills in *dstlen (if non-NULL)
216 * notes:
217 *	Enforces label and domain length limits.
218 */
219
220int
221ns_name_pton2(const char *src, u_char *dst, size_t dstsiz, size_t *dstlen) {
222	u_char *label, *bp, *eom;
223	int c, n, escaped, e = 0;
224	char *cp;
225
226	escaped = 0;
227	bp = dst;
228	eom = dst + dstsiz;
229	label = bp++;
230
231	while ((c = *src++) != 0) {
232		if (escaped) {
233			if (c == '[') { /* start a bit string label */
234				if ((cp = strchr(src, ']')) == NULL) {
235					errno = EINVAL; /* ??? */
236					return(-1);
237				}
238				if ((e = encode_bitsring(&src, cp + 2,
239							 &label, &bp, eom))
240				    != 0) {
241					errno = e;
242					return(-1);
243				}
244				escaped = 0;
245				label = bp++;
246				if ((c = *src++) == 0)
247					goto done;
248				else if (c != '.') {
249					errno = EINVAL;
250					return(-1);
251				}
252				continue;
253			}
254			else if ((cp = strchr(digits, c)) != NULL) {
255				n = (int)(cp - digits) * 100;
256				if ((c = *src++) == 0 ||
257				    (cp = strchr(digits, c)) == NULL) {
258					errno = EMSGSIZE;
259					return (-1);
260				}
261				n += (int)(cp - digits) * 10;
262				if ((c = *src++) == 0 ||
263				    (cp = strchr(digits, c)) == NULL) {
264					errno = EMSGSIZE;
265					return (-1);
266				}
267				n += (int)(cp - digits);
268				if (n > 255) {
269					errno = EMSGSIZE;
270					return (-1);
271				}
272				c = n;
273			}
274			escaped = 0;
275		} else if (c == '\\') {
276			escaped = 1;
277			continue;
278		} else if (c == '.') {
279			c = (int)(bp - label - 1);
280			if ((c & NS_CMPRSFLGS) != 0) {	/* Label too big. */
281				errno = EMSGSIZE;
282				return (-1);
283			}
284			if (label >= eom) {
285				errno = EMSGSIZE;
286				return (-1);
287			}
288			*label = c;
289			/* Fully qualified ? */
290			if (*src == '\0') {
291				if (c != 0) {
292					if (bp >= eom) {
293						errno = EMSGSIZE;
294						return (-1);
295					}
296					*bp++ = '\0';
297				}
298				if ((bp - dst) > MAXCDNAME) {
299					errno = EMSGSIZE;
300					return (-1);
301				}
302				if (dstlen != NULL)
303					*dstlen = (bp - dst);
304				return (1);
305			}
306			if (c == 0 || *src == '.') {
307				errno = EMSGSIZE;
308				return (-1);
309			}
310			label = bp++;
311			continue;
312		}
313		if (bp >= eom) {
314			errno = EMSGSIZE;
315			return (-1);
316		}
317		*bp++ = (u_char)c;
318	}
319	c = (int)(bp - label - 1);
320	if ((c & NS_CMPRSFLGS) != 0) {		/* Label too big. */
321		errno = EMSGSIZE;
322		return (-1);
323	}
324  done:
325	if (label >= eom) {
326		errno = EMSGSIZE;
327		return (-1);
328	}
329	*label = c;
330	if (c != 0) {
331		if (bp >= eom) {
332			errno = EMSGSIZE;
333			return (-1);
334		}
335		*bp++ = 0;
336	}
337	if ((bp - dst) > MAXCDNAME) {	/* src too big */
338		errno = EMSGSIZE;
339		return (-1);
340	}
341	if (dstlen != NULL)
342		*dstlen = (bp - dst);
343	return (0);
344}
345
346/*
347 *	Convert a network strings labels into all lowercase.
348 *
349 * return:
350 *	Number of bytes written to buffer, or -1 (with errno set)
351 *
352 * notes:
353 *	Enforces label and domain length limits.
354 */
355
356int
357ns_name_ntol(const u_char *src, u_char *dst, size_t dstsiz)
358{
359	const u_char *cp;
360	u_char *dn, *eom;
361	u_char c;
362	u_int n;
363	int l;
364
365	cp = src;
366	dn = dst;
367	eom = dst + dstsiz;
368
369	if (dn >= eom) {
370		errno = EMSGSIZE;
371		return (-1);
372	}
373	while ((n = *cp++) != 0) {
374		if ((n & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
375			/* Some kind of compression pointer. */
376			errno = EMSGSIZE;
377			return (-1);
378		}
379		*dn++ = n;
380		if ((l = labellen(cp - 1)) < 0) {
381			errno = EMSGSIZE;
382			return (-1);
383		}
384		if (dn + l >= eom) {
385			errno = EMSGSIZE;
386			return (-1);
387		}
388		for (; l > 0; l--) {
389			c = *cp++;
390			if (isascii(c) && isupper(c))
391				*dn++ = tolower(c);
392			else
393				*dn++ = c;
394		}
395	}
396	*dn++ = '\0';
397	_DIAGASSERT(__type_fit(int, dn - dst));
398	return (int)(dn - dst);
399}
400
401/*
402 *	Unpack a domain name from a message, source may be compressed.
403 *
404 * return:
405 *	-1 if it fails, or consumed octets if it succeeds.
406 */
407int
408ns_name_unpack(const u_char *msg, const u_char *eom, const u_char *src,
409	       u_char *dst, size_t dstsiz)
410{
411	return (ns_name_unpack2(msg, eom, src, dst, dstsiz, NULL));
412}
413
414/*
415 * ns_name_unpack2(msg, eom, src, dst, dstsiz, *dstlen)
416 *	Unpack a domain name from a message, source may be compressed.
417 * return:
418 *	-1 if it fails, or consumed octets if it succeeds.
419 * side effect:
420 *	fills in *dstlen (if non-NULL).
421 */
422int
423ns_name_unpack2(const u_char *msg, const u_char *eom, const u_char *src,
424		u_char *dst, size_t dstsiz, size_t *dstlen)
425{
426	const u_char *srcp, *dstlim;
427	u_char *dstp;
428	int n, len, checked, l;
429
430	len = -1;
431	checked = 0;
432	dstp = dst;
433	srcp = src;
434	dstlim = dst + dstsiz;
435	if (srcp < msg || srcp >= eom) {
436		errno = EMSGSIZE;
437		return (-1);
438	}
439	/* Fetch next label in domain name. */
440	while ((n = *srcp++) != 0) {
441		/* Check for indirection. */
442		switch (n & NS_CMPRSFLGS) {
443		case 0:
444		case NS_TYPE_ELT:
445			/* Limit checks. */
446			if ((l = labellen(srcp - 1)) < 0) {
447				errno = EMSGSIZE;
448				return(-1);
449			}
450			if (dstp + l + 1 >= dstlim || srcp + l >= eom) {
451				errno = EMSGSIZE;
452				return (-1);
453			}
454			checked += l + 1;
455			*dstp++ = n;
456			memcpy(dstp, srcp, (size_t)l);
457			dstp += l;
458			srcp += l;
459			break;
460
461		case NS_CMPRSFLGS:
462			if (srcp >= eom) {
463				errno = EMSGSIZE;
464				return (-1);
465			}
466			if (len < 0) {
467				_DIAGASSERT(__type_fit(int, srcp - src + 1));
468				len = (int)(srcp - src + 1);
469			}
470			// BEGIN android-changed: safer pointer overflow check
471			l = (((n & 0x3f) << 8) | (*srcp & 0xff));
472			if (l >= eom - msg) {  /* Out of range. */
473				errno = EMSGSIZE;
474				return (-1);
475			}
476			srcp = msg + l;
477			// END android-changed
478			checked += 2;
479			/*
480			 * Check for loops in the compressed name;
481			 * if we've looked at the whole message,
482			 * there must be a loop.
483			 */
484			if (checked >= eom - msg) {
485				errno = EMSGSIZE;
486				return (-1);
487			}
488			break;
489
490		default:
491			errno = EMSGSIZE;
492			return (-1);			/* flag error */
493		}
494	}
495	*dstp++ = 0;
496	if (dstlen != NULL)
497		*dstlen = dstp - dst;
498	if (len < 0) {
499		_DIAGASSERT(__type_fit(int, srcp - src));
500		len = (int)(srcp - src);
501	}
502	return len;
503}
504
505/*
506 *	Pack domain name 'domain' into 'comp_dn'.
507 *
508 * return:
509 *	Size of the compressed name, or -1.
510 *
511 * notes:
512 *	'dnptrs' is an array of pointers to previous compressed names.
513 *	dnptrs[0] is a pointer to the beginning of the message. The array
514 *	ends with NULL.
515 *	'lastdnptr' is a pointer to the end of the array pointed to
516 *	by 'dnptrs'.
517 *
518 * Side effects:
519 *	The list of pointers in dnptrs is updated for labels inserted into
520 *	the message as we compress the name.  If 'dnptr' is NULL, we don't
521 *	try to compress names. If 'lastdnptr' is NULL, we don't update the
522 *	list.
523 */
524int
525ns_name_pack(const u_char *src, u_char *dst, int dstsiz,
526	     const u_char **dnptrs, const u_char **lastdnptr)
527{
528	u_char *dstp;
529	const u_char **cpp, **lpp, *eob, *msg;
530	const u_char *srcp;
531	int n, l, first = 1;
532
533	srcp = src;
534	dstp = dst;
535	eob = dstp + dstsiz;
536	lpp = cpp = NULL;
537	if (dnptrs != NULL) {
538		if ((msg = *dnptrs++) != NULL) {
539			for (cpp = dnptrs; *cpp != NULL; cpp++)
540				continue;
541			lpp = cpp;	/* end of list to search */
542		}
543	} else
544		msg = NULL;
545
546	/* make sure the domain we are about to add is legal */
547	l = 0;
548	do {
549		int l0;
550
551		n = *srcp;
552		if ((n & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
553			errno = EMSGSIZE;
554			return (-1);
555		}
556		if ((l0 = labellen(srcp)) < 0) {
557			errno = EINVAL;
558			return(-1);
559		}
560		l += l0 + 1;
561		if (l > MAXCDNAME) {
562			errno = EMSGSIZE;
563			return (-1);
564		}
565		srcp += l0 + 1;
566	} while (n != 0);
567
568	/* from here on we need to reset compression pointer array on error */
569	srcp = src;
570	do {
571		/* Look to see if we can use pointers. */
572		n = *srcp;
573		if (n != 0 && msg != NULL) {
574			l = dn_find(srcp, msg, (const u_char * const *)dnptrs,
575				    (const u_char * const *)lpp);
576			if (l >= 0) {
577				if (dstp + 1 >= eob) {
578					goto cleanup;
579				}
580				*dstp++ = ((u_int32_t)l >> 8) | NS_CMPRSFLGS;
581				*dstp++ = l % 256;
582				_DIAGASSERT(__type_fit(int, dstp - dst));
583				return (int)(dstp - dst);
584			}
585			/* Not found, save it. */
586			if (lastdnptr != NULL && cpp < lastdnptr - 1 &&
587			    (dstp - msg) < 0x4000 && first) {
588				*cpp++ = dstp;
589				*cpp = NULL;
590				first = 0;
591			}
592		}
593		/* copy label to buffer */
594		if ((n & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
595			/* Should not happen. */
596			goto cleanup;
597		}
598		n = labellen(srcp);
599		if (dstp + 1 + n >= eob) {
600			goto cleanup;
601		}
602		memcpy(dstp, srcp, (size_t)(n + 1));
603		srcp += n + 1;
604		dstp += n + 1;
605	} while (n != 0);
606
607	if (dstp > eob) {
608cleanup:
609		if (msg != NULL)
610			*lpp = NULL;
611		errno = EMSGSIZE;
612		return (-1);
613	}
614	_DIAGASSERT(__type_fit(int, dstp - dst));
615	return (int)(dstp - dst);
616}
617
618/*
619 *	Expand compressed domain name to presentation format.
620 *
621 * return:
622 *	Number of bytes read out of `src', or -1 (with errno set).
623 *
624 * note:
625 *	Root domain returns as "." not "".
626 */
627int
628ns_name_uncompress(const u_char *msg, const u_char *eom, const u_char *src,
629		   char *dst, size_t dstsiz)
630{
631	u_char tmp[NS_MAXCDNAME];
632	int n;
633
634	if ((n = ns_name_unpack(msg, eom, src, tmp, sizeof tmp)) == -1)
635		return (-1);
636	if (ns_name_ntop(tmp, dst, dstsiz) == -1)
637		return (-1);
638	return (n);
639}
640
641/*
642 *	Compress a domain name into wire format, using compression pointers.
643 *
644 * return:
645 *	Number of bytes consumed in `dst' or -1 (with errno set).
646 *
647 * notes:
648 *	'dnptrs' is an array of pointers to previous compressed names.
649 *	dnptrs[0] is a pointer to the beginning of the message.
650 *	The list ends with NULL.  'lastdnptr' is a pointer to the end of the
651 *	array pointed to by 'dnptrs'. Side effect is to update the list of
652 *	pointers for labels inserted into the message as we compress the name.
653 *	If 'dnptr' is NULL, we don't try to compress names. If 'lastdnptr'
654 *	is NULL, we don't update the list.
655 */
656int
657ns_name_compress(const char *src, u_char *dst, size_t dstsiz,
658		 const u_char **dnptrs, const u_char **lastdnptr)
659{
660	u_char tmp[NS_MAXCDNAME];
661
662	if (ns_name_pton(src, tmp, sizeof tmp) == -1)
663		return (-1);
664	return (ns_name_pack(tmp, dst, (int)dstsiz, dnptrs, lastdnptr));
665}
666
667/*
668 * Reset dnptrs so that there are no active references to pointers at or
669 * after src.
670 */
671void
672ns_name_rollback(const u_char *src, const u_char **dnptrs,
673		 const u_char **lastdnptr)
674{
675	while (dnptrs < lastdnptr && *dnptrs != NULL) {
676		if (*dnptrs >= src) {
677			*dnptrs = NULL;
678			break;
679		}
680		dnptrs++;
681	}
682}
683
684/*
685 *	Advance *ptrptr to skip over the compressed name it points at.
686 *
687 * return:
688 *	0 on success, -1 (with errno set) on failure.
689 */
690int
691ns_name_skip(const u_char **ptrptr, const u_char *eom)
692{
693	const u_char *cp;
694	u_int n;
695	int l;
696
697	cp = *ptrptr;
698	while (cp < eom && (n = *cp++) != 0) {
699		/* Check for indirection. */
700		switch (n & NS_CMPRSFLGS) {
701		case 0:			/* normal case, n == len */
702			cp += n;
703			continue;
704		case NS_TYPE_ELT: /* EDNS0 extended label */
705			if ((l = labellen(cp - 1)) < 0) {
706				errno = EMSGSIZE; /* XXX */
707				return(-1);
708			}
709			cp += l;
710			continue;
711		case NS_CMPRSFLGS:	/* indirection */
712			cp++;
713			break;
714		default:		/* illegal type */
715			errno = EMSGSIZE;
716			return (-1);
717		}
718		break;
719	}
720	if (cp > eom) {
721		errno = EMSGSIZE;
722		return (-1);
723	}
724	*ptrptr = cp;
725	return (0);
726}
727
728/* Find the number of octets an nname takes up, including the root label.
729 * (This is basically ns_name_skip() without compression-pointer support.)
730 * ((NOTE: can only return zero if passed-in namesiz argument is zero.))
731 */
732ssize_t
733ns_name_length(ns_nname_ct nname, size_t namesiz) {
734	ns_nname_ct orig = nname;
735	u_int n;
736
737	while (namesiz-- > 0 && (n = *nname++) != 0) {
738		if ((n & NS_CMPRSFLGS) != 0) {
739			errno = EISDIR;
740			return (-1);
741		}
742		if (n > namesiz) {
743			errno = EMSGSIZE;
744			return (-1);
745		}
746		nname += n;
747		namesiz -= n;
748	}
749	return (nname - orig);
750}
751
752/* Compare two nname's for equality.  Return -1 on error (setting errno).
753 */
754int
755ns_name_eq(ns_nname_ct a, size_t as, ns_nname_ct b, size_t bs) {
756	ns_nname_ct ae = a + as, be = b + bs;
757	int ac, bc;
758
759	while (ac = *a, bc = *b, ac != 0 && bc != 0) {
760		if ((ac & NS_CMPRSFLGS) != 0 || (bc & NS_CMPRSFLGS) != 0) {
761			errno = EISDIR;
762			return (-1);
763		}
764		if (a + ac >= ae || b + bc >= be) {
765			errno = EMSGSIZE;
766			return (-1);
767		}
768		if (ac != bc || strncasecmp((const char *) ++a,
769					    (const char *) ++b,
770					    (size_t)ac) != 0)
771			return (0);
772		a += ac, b += bc;
773	}
774	return (ac == 0 && bc == 0);
775}
776
777/* Is domain "A" owned by (at or below) domain "B"?
778 */
779int
780ns_name_owned(ns_namemap_ct a, int an, ns_namemap_ct b, int bn) {
781	/* If A is shorter, it cannot be owned by B. */
782	if (an < bn)
783		return (0);
784
785	/* If they are unequal before the length of the shorter, A cannot... */
786	while (bn > 0) {
787		if (a->len != b->len ||
788		    strncasecmp((const char *) a->base,
789				(const char *) b->base, (size_t)a->len) != 0)
790			return (0);
791		a++, an--;
792		b++, bn--;
793	}
794
795	/* A might be longer or not, but either way, B owns it. */
796	return (1);
797}
798
799/* Build an array of <base,len> tuples from an nname, top-down order.
800 * Return the number of tuples (labels) thus discovered.
801 */
802int
803ns_name_map(ns_nname_ct nname, size_t namelen, ns_namemap_t map, int mapsize) {
804	u_int n;
805	int l;
806
807	n = *nname++;
808	namelen--;
809
810	/* Root zone? */
811	if (n == 0) {
812		/* Extra data follows name? */
813		if (namelen > 0) {
814			errno = EMSGSIZE;
815			return (-1);
816		}
817		return (0);
818	}
819
820	/* Compression pointer? */
821	if ((n & NS_CMPRSFLGS) != 0) {
822		errno = EISDIR;
823		return (-1);
824	}
825
826	/* Label too long? */
827	if (n > namelen) {
828		errno = EMSGSIZE;
829		return (-1);
830	}
831
832	/* Recurse to get rest of name done first. */
833	l = ns_name_map(nname + n, namelen - n, map, mapsize);
834	if (l < 0)
835		return (-1);
836
837	/* Too many labels? */
838	if (l >= mapsize) {
839		errno = ENAMETOOLONG;
840		return (-1);
841	}
842
843	/* We're on our way back up-stack, store current map data. */
844	map[l].base = nname;
845	map[l].len = n;
846	return (l + 1);
847}
848
849/* Count the labels in a domain name.  Root counts, so COM. has two.  This
850 * is to make the result comparable to the result of ns_name_map().
851 */
852int
853ns_name_labels(ns_nname_ct nname, size_t namesiz) {
854	int ret = 0;
855	u_int n;
856
857	while (namesiz-- > 0 && (n = *nname++) != 0) {
858		if ((n & NS_CMPRSFLGS) != 0) {
859			errno = EISDIR;
860			return (-1);
861		}
862		if (n > namesiz) {
863			errno = EMSGSIZE;
864			return (-1);
865		}
866		nname += n;
867		namesiz -= n;
868		ret++;
869	}
870	return (ret + 1);
871}
872/* Private. */
873
874/*
875 *	Thinking in noninternationalized USASCII (per the DNS spec),
876 *	is this characted special ("in need of quoting") ?
877 *
878 * return:
879 *	boolean.
880 */
881static int
882special(int ch) {
883	switch (ch) {
884	case 0x22: /* '"' */
885	case 0x2E: /* '.' */
886	case 0x3B: /* ';' */
887	case 0x5C: /* '\\' */
888	case 0x28: /* '(' */
889	case 0x29: /* ')' */
890	/* Special modifiers in zone files. */
891	case 0x40: /* '@' */
892	case 0x24: /* '$' */
893		return (1);
894	default:
895		return (0);
896	}
897}
898
899/*
900 *	Thinking in noninternationalized USASCII (per the DNS spec),
901 *	is this character visible and not a space when printed ?
902 *
903 * return:
904 *	boolean.
905 */
906static int
907printable(int ch) {
908	return (ch > 0x20 && ch < 0x7f);
909}
910
911/*
912 *	Thinking in noninternationalized USASCII (per the DNS spec),
913 *	convert this character to lower case if it's upper case.
914 */
915static int
916mklower(int ch) {
917	if (ch >= 0x41 && ch <= 0x5A)
918		return (ch + 0x20);
919	return (ch);
920}
921
922/*
923 *	Search for the counted-label name in an array of compressed names.
924 *
925 * return:
926 *	offset from msg if found, or -1.
927 *
928 * notes:
929 *	dnptrs is the pointer to the first name on the list,
930 *	not the pointer to the start of the message.
931 */
932static int
933dn_find(const u_char *domain, const u_char *msg,
934	const u_char * const *dnptrs,
935	const u_char * const *lastdnptr)
936{
937	const u_char *dn, *cp, *sp;
938	const u_char * const *cpp;
939	u_int n;
940
941	for (cpp = dnptrs; cpp < lastdnptr; cpp++) {
942		sp = *cpp;
943		/*
944		 * terminate search on:
945		 * root label
946		 * compression pointer
947		 * unusable offset
948		 */
949		while (*sp != 0 && (*sp & NS_CMPRSFLGS) == 0 &&
950		       (sp - msg) < 0x4000) {
951			dn = domain;
952			cp = sp;
953			while ((n = *cp++) != 0) {
954				/*
955				 * check for indirection
956				 */
957				switch (n & NS_CMPRSFLGS) {
958				case 0:		/* normal case, n == len */
959					n = labellen(cp - 1); /* XXX */
960
961					if (n != *dn++)
962						goto next;
963
964					for (; n > 0; n--)
965						if (mklower(*dn++) !=
966						    mklower(*cp++))
967							goto next;
968					/* Is next root for both ? */
969					if (*dn == '\0' && *cp == '\0') {
970						_DIAGASSERT(__type_fit(int,
971						    sp - msg));
972						return (int)(sp - msg);
973					}
974					if (*dn)
975						continue;
976					goto next;
977				case NS_CMPRSFLGS:	/* indirection */
978					cp = msg + (((n & 0x3f) << 8) | *cp);
979					break;
980
981				default:	/* illegal type */
982					errno = EMSGSIZE;
983					return (-1);
984				}
985			}
986 next: ;
987			sp += *sp + 1;
988		}
989	}
990	errno = ENOENT;
991	return (-1);
992}
993
994static int
995decode_bitstring(const unsigned char **cpp, char *dn, const char *eom)
996{
997	const unsigned char *cp = *cpp;
998	char *beg = dn, tc;
999	int b, blen, plen, i;
1000
1001	if ((blen = (*cp & 0xff)) == 0)
1002		blen = 256;
1003	plen = (blen + 3) / 4;
1004	plen += (int)sizeof("\\[x/]") + (blen > 99 ? 3 : (blen > 9) ? 2 : 1);
1005	if (dn + plen >= eom)
1006		return(-1);
1007
1008	cp++;
1009	i = snprintf(dn, eom - dn, "\\[x");
1010	if (i < 0)
1011		return (-1);
1012	dn += i;
1013	for (b = blen; b > 7; b -= 8, cp++) {
1014		i = snprintf(dn, eom - dn, "%02x", *cp & 0xff);
1015		if (i < 0)
1016			return (-1);
1017		dn += i;
1018	}
1019	if (b > 4) {
1020		tc = *cp++;
1021		i = snprintf(dn, eom - dn, "%02x", tc & (0xff << (8 - b)));
1022		if (i < 0)
1023			return (-1);
1024		dn += i;
1025	} else if (b > 0) {
1026		tc = *cp++;
1027		i = snprintf(dn, eom - dn, "%1x",
1028			       (((u_int32_t)tc >> 4) & 0x0f) & (0x0f << (4 - b)));
1029		if (i < 0)
1030			return (-1);
1031		dn += i;
1032	}
1033	i = snprintf(dn, eom - dn, "/%d]", blen);
1034	if (i < 0)
1035		return (-1);
1036	dn += i;
1037
1038	*cpp = cp;
1039	_DIAGASSERT(__type_fit(int, dn - beg));
1040	return (int)(dn - beg);
1041}
1042
1043static int
1044encode_bitsring(const char **bp, const char *end, unsigned char **labelp,
1045	        unsigned char ** dst, unsigned const char *eom)
1046{
1047	int afterslash = 0;
1048	const char *cp = *bp;
1049	unsigned char *tp;
1050	char c;
1051	const char *beg_blen;
1052	char *end_blen = NULL;
1053	int value = 0, count = 0, tbcount = 0, blen = 0;
1054
1055	beg_blen = end_blen = NULL;
1056
1057	/* a bitstring must contain at least 2 characters */
1058	if (end - cp < 2)
1059		return(EINVAL);
1060
1061	/* XXX: currently, only hex strings are supported */
1062	if (*cp++ != 'x')
1063		return(EINVAL);
1064	if (!isxdigit((*cp) & 0xff)) /* reject '\[x/BLEN]' */
1065		return(EINVAL);
1066
1067	for (tp = *dst + 1; cp < end && tp < eom; cp++) {
1068		switch((c = *cp)) {
1069		case ']':	/* end of the bitstring */
1070			if (afterslash) {
1071				if (beg_blen == NULL)
1072					return(EINVAL);
1073				blen = (int)strtol(beg_blen, &end_blen, 10);
1074				if (*end_blen != ']')
1075					return(EINVAL);
1076			}
1077			if (count)
1078				*tp++ = ((value << 4) & 0xff);
1079			cp++;	/* skip ']' */
1080			goto done;
1081		case '/':
1082			afterslash = 1;
1083			break;
1084		default:
1085			if (afterslash) {
1086				if (!isdigit(c&0xff))
1087					return(EINVAL);
1088				if (beg_blen == NULL) {
1089
1090					if (c == '0') {
1091						/* blen never begings with 0 */
1092						return(EINVAL);
1093					}
1094					beg_blen = cp;
1095				}
1096			} else {
1097				if (!isxdigit(c&0xff))
1098					return(EINVAL);
1099				value <<= 4;
1100				value += digitvalue[(int)c];
1101				count += 4;
1102				tbcount += 4;
1103				if (tbcount > 256)
1104					return(EINVAL);
1105				if (count == 8) {
1106					*tp++ = value;
1107					count = 0;
1108				}
1109			}
1110			break;
1111		}
1112	}
1113  done:
1114	if (cp >= end || tp >= eom)
1115		return(EMSGSIZE);
1116
1117	/*
1118	 * bit length validation:
1119	 * If a <length> is present, the number of digits in the <bit-data>
1120	 * MUST be just sufficient to contain the number of bits specified
1121	 * by the <length>. If there are insignificant bits in a final
1122	 * hexadecimal or octal digit, they MUST be zero.
1123	 * RFC 2673, Section 3.2.
1124	 */
1125	if (blen > 0) {
1126		int traillen;
1127
1128		if (((blen + 3) & ~3) != tbcount)
1129			return(EINVAL);
1130		traillen = tbcount - blen; /* between 0 and 3 */
1131		if (((value << (8 - traillen)) & 0xff) != 0)
1132			return(EINVAL);
1133	}
1134	else
1135		blen = tbcount;
1136	if (blen == 256)
1137		blen = 0;
1138
1139	/* encode the type and the significant bit fields */
1140	**labelp = DNS_LABELTYPE_BITSTRING;
1141	**dst = blen;
1142
1143	*bp = cp;
1144	*dst = tp;
1145
1146	return(0);
1147}
1148
1149static int
1150labellen(const u_char *lp)
1151{
1152	int bitlen;
1153	u_char l = *lp;
1154
1155	if ((l & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
1156		/* should be avoided by the caller */
1157		return(-1);
1158	}
1159
1160	if ((l & NS_CMPRSFLGS) == NS_TYPE_ELT) {
1161		if (l == DNS_LABELTYPE_BITSTRING) {
1162			if ((bitlen = *(lp + 1)) == 0)
1163				bitlen = 256;
1164			return((bitlen + 7 ) / 8 + 1);
1165		}
1166		return(-1);	/* unknwon ELT */
1167	}
1168	return(l);
1169}
1170