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