name.c

bind-3.2.

/*
 * Copyright (C) 1998-2003  Internet Software Consortium.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM
 * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
 * INTERNET SOFTWARE CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING
 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/* $Id: name.c,v 1.127.2.8 2003/10/09 07:32:37 marka Exp $ */

#include <config.h>

#include <ctype.h>

#include <isc/buffer.h>
#include <isc/hash.h>
#include <isc/mem.h>
#include <isc/print.h>
#include <isc/string.h>
#include <isc/util.h>

#include <dns/compress.h>
#include <dns/name.h>
#include <dns/result.h>

#define VALID_NAME(n)	ISC_MAGIC_VALID(n, DNS_NAME_MAGIC)

typedef enum {
	ft_init = 0,
	ft_start,
	ft_ordinary,
	ft_initialescape,
	ft_escape,
	ft_escdecimal,
	ft_bitstring,
	ft_binary,
	ft_octal,
	ft_hex,
	ft_dottedquad,
	ft_dqdecimal,
	ft_maybeslash,
	ft_finishbitstring,
	ft_bitlength,
	ft_eatdot,
	ft_at
} ft_state;

typedef enum {
	fw_start = 0,
	fw_ordinary,
	fw_copy,
	fw_bitstring,
	fw_newcurrent
} fw_state;

static char digitvalue[256] = {
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,	/*16*/
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*32*/
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*48*/
	 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, /*64*/
	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*80*/
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*96*/
	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*112*/
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*128*/
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*256*/
};

static char hexdigits[16] = {
	'0', '1', '2', '3', '4', '5', '6', '7',
	'8', '9', 'A', 'B', 'C', 'D', 'E', 'F'
};

static unsigned char maptolower[] = {
	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
	0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
	0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
	0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
	0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
	0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
	0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
	0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
	0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
	0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
	0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
	0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
	0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
	0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
	0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
	0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
	0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
	0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
	0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
	0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
	0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
	0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
	0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
	0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
	0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
	0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
	0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
	0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
	0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
	0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
	0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
};

#define CONVERTTOASCII(c)
#define CONVERTFROMASCII(c)

#define INIT_OFFSETS(name, var, default) \
	if (name->offsets != NULL) \
		var = name->offsets; \
	else \
		var = default;

#define SETUP_OFFSETS(name, var, default) \
	if (name->offsets != NULL) \
		var = name->offsets; \
	else { \
		var = default; \
		set_offsets(name, var, NULL); \
	}

/*
 * Note:  If additional attributes are added that should not be set for
 *	  empty names, MAKE_EMPTY() must be changed so it clears them.
 */
#define MAKE_EMPTY(name) \
do { \
	name->ndata = NULL; \
	name->length = 0; \
	name->labels = 0; \
	name->attributes &= ~DNS_NAMEATTR_ABSOLUTE; \
} while (0);

/*
 * A name is "bindable" if it can be set to point to a new value, i.e.
 * name->ndata and name->length may be changed.
 */
#define BINDABLE(name) \
	((name->attributes & (DNS_NAMEATTR_READONLY|DNS_NAMEATTR_DYNAMIC)) \
	 == 0)

/*
 * Note that the name data must be a char array, not a string
 * literal, to avoid compiler warnings about discarding
 * the const attribute of a string.
 */
static unsigned char root_ndata[] = { '\0' };
static unsigned char root_offsets[] = { 0 };

static dns_name_t root = 
{
	DNS_NAME_MAGIC,
	root_ndata, 1, 1,
	DNS_NAMEATTR_READONLY | DNS_NAMEATTR_ABSOLUTE,
	root_offsets, NULL,
	{(void *)-1, (void *)-1},
	{NULL, NULL}
};

/* XXXDCL make const? */
dns_name_t *dns_rootname = &root;

static unsigned char wild_ndata[] = { '\001', '*' };
static unsigned char wild_offsets[] = { 0 };

static dns_name_t wild =
{
	DNS_NAME_MAGIC,
	wild_ndata, 2, 1,
	DNS_NAMEATTR_READONLY,
	wild_offsets, NULL,
	{(void *)-1, (void *)-1},
	{NULL, NULL}
};

/* XXXDCL make const? */
dns_name_t *dns_wildcardname = &wild;

static void
set_offsets(const dns_name_t *name, unsigned char *offsets,
	    dns_name_t *set_name);

static void
compact(dns_name_t *name, unsigned char *offsets);

/*
 * Yes, get_bit and set_bit are lame.  We define them here so they can
 * be inlined by smart compilers.
 */

static inline unsigned int
get_bit(unsigned char *array, unsigned int idx) {
	unsigned int byte, shift;

	byte = array[idx / 8];
	shift = 7 - (idx % 8);

	return ((byte >> shift) & 0x01);
}

static inline void
set_bit(unsigned char *array, unsigned int idx, unsigned int bit) {
	unsigned int shift, mask;

	shift = 7 - (idx % 8);
	mask = 1 << shift;

	if (bit != 0)
		array[idx / 8] |= mask;
	else
		array[idx / 8] &= (~mask & 0xFF);
}

dns_labeltype_t
dns_label_type(dns_label_t *label) {
	/*
	 * Get the type of 'label'.
	 */

	REQUIRE(label != NULL);
	REQUIRE(label->length > 0);
	REQUIRE(label->base[0] <= 63 ||
		label->base[0] == DNS_LABELTYPE_BITSTRING);

	if (label->base[0] <= 63)
		return (dns_labeltype_ordinary);
	else
		return (dns_labeltype_bitstring);
}

unsigned int
dns_label_countbits(dns_label_t *label) {
	unsigned int count;

	/*
	 * The number of bits in a bitstring label.
	 */

	REQUIRE(label != NULL);
	REQUIRE(label->length > 2);
	REQUIRE(label->base[0] == DNS_LABELTYPE_BITSTRING);

	count = label->base[1];
	if (count == 0)
		count = 256;

	return (count);
}

dns_bitlabel_t
dns_label_getbit(dns_label_t *label, unsigned int n) {
	unsigned int count, bit;

	/*
	 * The 'n'th most significant bit of 'label'.
	 *
	 * Notes:
	 *	Numbering starts at 0.
	 */

	REQUIRE(label != NULL);
	REQUIRE(label->length > 2);
	REQUIRE(label->base[0] == DNS_LABELTYPE_BITSTRING);

	count = label->base[1];
	if (count == 0)
		count = 256;

	REQUIRE(n < count);

	bit = get_bit(&label->base[2], n);
	if (bit == 0)
		return (dns_bitlabel_0);
	return (dns_bitlabel_1);
}

void
dns_name_init(dns_name_t *name, unsigned char *offsets) {
	/*
	 * Initialize 'name'.
	 */
	DNS_NAME_INIT(name, offsets);
}

void
dns_name_reset(dns_name_t *name) {
	REQUIRE(VALID_NAME(name));
	REQUIRE(BINDABLE(name));

	DNS_NAME_RESET(name);
}

void
dns_name_invalidate(dns_name_t *name) {
	/*
	 * Make 'name' invalid.
	 */

	REQUIRE(VALID_NAME(name));

	name->magic = 0;
	name->ndata = NULL;
	name->length = 0;
	name->labels = 0;
	name->attributes = 0;
	name->offsets = NULL;
	name->buffer = NULL;
	ISC_LINK_INIT(name, link);
}

void
dns_name_setbuffer(dns_name_t *name, isc_buffer_t *buffer) {
	/*
	 * Dedicate a buffer for use with 'name'.
	 */

	REQUIRE(VALID_NAME(name));
	REQUIRE((buffer != NULL && name->buffer == NULL) ||
		(buffer == NULL));

	name->buffer = buffer;
}

isc_boolean_t
dns_name_hasbuffer(const dns_name_t *name) {
	/*
	 * Does 'name' have a dedicated buffer?
	 */

	REQUIRE(VALID_NAME(name));

	if (name->buffer != NULL)
		return (ISC_TRUE);

	return (ISC_FALSE);
}

isc_boolean_t
dns_name_isabsolute(const dns_name_t *name) {

	/*
	 * Does 'name' end in the root label?
	 */

	REQUIRE(VALID_NAME(name));

	if ((name->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
		return (ISC_TRUE);
	return (ISC_FALSE);
}

isc_boolean_t
dns_name_iswildcard(const dns_name_t *name) {
	unsigned char *ndata;

	/*
	 * Is 'name' a wildcard name?
	 */

	REQUIRE(VALID_NAME(name));
	REQUIRE(name->labels > 0);

	if (name->length >= 2) {
		ndata = name->ndata;
		if (ndata[0] == 1 && ndata[1] == '*')
			return (ISC_TRUE);
	}

	return (ISC_FALSE);
}

isc_boolean_t
dns_name_requiresedns(const dns_name_t *name) {
	unsigned int count, nrem;
	unsigned char *ndata;
	isc_boolean_t requiresedns = ISC_FALSE;

	/*
	 * Does 'name' require EDNS for transmission?
	 */

	REQUIRE(VALID_NAME(name));
	REQUIRE(name->labels > 0);

	ndata = name->ndata;
	nrem = name->length;
	while (nrem > 0) {
		count = *ndata++;
		nrem--;
		if (count == 0)
			break;
		if (count > 63) {
			INSIST(count == DNS_LABELTYPE_BITSTRING);
			requiresedns = ISC_TRUE;
			break;
		}
		INSIST(nrem >= count);
		nrem -= count;
		ndata += count;
	}

	return (requiresedns);
}

unsigned int
dns_name_hash(dns_name_t *name, isc_boolean_t case_sensitive) {
	unsigned int length;
	const unsigned char *s;
	unsigned int h = 0;
	unsigned char c;

	/*
	 * Provide a hash value for 'name'.
	 */
	REQUIRE(VALID_NAME(name));

	if (name->labels == 0)
		return (0);
	length = name->length;
	if (length > 16)
		length = 16;

	/*
	 * This hash function is similar to the one Ousterhout
	 * uses in Tcl.
	 */
	s = name->ndata;
	if (case_sensitive) {
		while (length > 0) {
			h += ( h << 3 ) + *s;
			s++;
			length--;
		}
	} else {
		while (length > 0) {
			c = maptolower[*s];
			h += ( h << 3 ) + c;
			s++;
			length--;
		}
	}

	return (h);
}

unsigned int
dns_fullname_hash(dns_name_t *name, isc_boolean_t case_sensitive) {
	/*
	 * Provide a hash value for 'name'.
	 */
	REQUIRE(VALID_NAME(name));

	if (name->labels == 0)
		return (0);

	return (isc_hash_calc((const unsigned char *)name->ndata,
			      name->length, case_sensitive));
}

dns_namereln_t
dns_name_fullcompare(const dns_name_t *name1, const dns_name_t *name2,
		     int *orderp,
		     unsigned int *nlabelsp, unsigned int *nbitsp)
{
	unsigned int l1, l2, l, count1, count2, count;
	unsigned int b1, b2, n, nlabels, nbits;
	int cdiff, ldiff, chdiff;
	unsigned char *label1, *label2;
	unsigned char *offsets1, *offsets2;
	dns_offsets_t odata1, odata2;
	dns_namereln_t namereln = dns_namereln_none;

	/*
	 * Determine the relative ordering under the DNSSEC order relation of
	 * 'name1' and 'name2', and also determine the hierarchical
	 * relationship of the names.
	 *
	 * Note: It makes no sense for one of the names to be relative and the
	 * other absolute.  If both names are relative, then to be meaningfully
	 * compared the caller must ensure that they are both relative to the
	 * same domain.
	 */

	REQUIRE(VALID_NAME(name1));
	REQUIRE(VALID_NAME(name2));
	REQUIRE(orderp != NULL);
	REQUIRE(nlabelsp != NULL);
	REQUIRE(nbitsp != NULL);
	/*
	 * Either name1 is absolute and name2 is absolute, or neither is.
	 */
	REQUIRE((name1->attributes & DNS_NAMEATTR_ABSOLUTE) ==
		(name2->attributes & DNS_NAMEATTR_ABSOLUTE));

	SETUP_OFFSETS(name1, offsets1, odata1);
	SETUP_OFFSETS(name2, offsets2, odata2);

	nlabels = 0;
	nbits = 0;
	l1 = name1->labels;
	l2 = name2->labels;
	ldiff = (int)l1 - (int)l2;
	if (ldiff < 0)
		l = l1;
	else
		l = l2;

	while (l > 0) {
		l--;
		l1--;
		l2--;
		label1 = &name1->ndata[offsets1[l1]];
		label2 = &name2->ndata[offsets2[l2]];
		count1 = *label1++;
		count2 = *label2++;
		if (count1 <= 63 && count2 <= 63) {
			cdiff = (int)count1 - (int)count2;
			if (cdiff < 0)
				count = count1;
			else
				count = count2;

			while (count > 0) {
				chdiff = (int)maptolower[*label1] -
					(int)maptolower[*label2];
				if (chdiff != 0) {
					*orderp = chdiff;
					goto done;
				}
				count--;
				label1++;
				label2++;
			}
			if (cdiff != 0) {
				*orderp = cdiff;
				goto done;
			}
			nlabels++;
		} else if (count1 == DNS_LABELTYPE_BITSTRING && count2 <= 63) {
			if (count2 == 0)
				*orderp = 1;
			else
				*orderp = -1;
			goto done;
		} else if (count2 == DNS_LABELTYPE_BITSTRING && count1 <= 63) {
			if (count1 == 0)
				*orderp = -1;
			else
				*orderp = 1;
			goto done;
		} else {
			INSIST(count1 == DNS_LABELTYPE_BITSTRING &&
			       count2 == DNS_LABELTYPE_BITSTRING);
			count1 = *label1++;
			if (count1 == 0)
				count1 = 256;