name.c 48.4 KB
Newer Older
Bob Halley's avatar
Bob Halley committed
1
/*
Brian Wellington's avatar
Brian Wellington committed
2
 * Copyright (C) 1998-2001  Internet Software Consortium.
3
 *
Bob Halley's avatar
Bob Halley committed
4 5 6
 * 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.
7
 *
8 9 10 11 12 13 14 15
 * 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.
Bob Halley's avatar
Bob Halley committed
16
 */
Bob Halley's avatar
Bob Halley committed
17

Mark Andrews's avatar
Mark Andrews committed
18
/* $Id: name.c,v 1.141 2003/10/17 03:46:43 marka Exp $ */
David Lawrence's avatar
David Lawrence committed
19

Bob Halley's avatar
Bob Halley committed
20 21
#include <config.h>

Bob Halley's avatar
add  
Bob Halley committed
22 23
#include <ctype.h>

Andreas Gustafsson's avatar
Andreas Gustafsson committed
24
#include <isc/buffer.h>
25
#include <isc/hash.h>
26
#include <isc/mem.h>
27
#include <isc/print.h>
28
#include <isc/string.h>
Bob Halley's avatar
Bob Halley committed
29
#include <isc/util.h>
Bob Halley's avatar
add  
Bob Halley committed
30

31
#include <dns/compress.h>
Brian Wellington's avatar
Brian Wellington committed
32 33
#include <dns/name.h>
#include <dns/result.h>
Bob Halley's avatar
add  
Bob Halley committed
34

35
#define VALID_NAME(n)	ISC_MAGIC_VALID(n, DNS_NAME_MAGIC)
Bob Halley's avatar
add  
Bob Halley committed
36 37

typedef enum {
38 39 40 41 42 43
	ft_init = 0,
	ft_start,
	ft_ordinary,
	ft_initialescape,
	ft_escape,
	ft_escdecimal,
44
	ft_at
45 46 47 48 49 50
} ft_state;

typedef enum {
	fw_start = 0,
	fw_ordinary,
	fw_copy,
David Lawrence's avatar
David Lawrence committed
51
	fw_newcurrent
52
} fw_state;
Bob Halley's avatar
add  
Bob Halley committed
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107

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 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
};

108 109 110
#define CONVERTTOASCII(c)
#define CONVERTFROMASCII(c)

111 112 113 114 115 116 117 118 119 120 121
#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; \
David Lawrence's avatar
David Lawrence committed
122
		set_offsets(name, var, NULL); \
123 124
	}

125 126 127 128 129 130 131 132 133 134 135 136
/*
 * 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);

137 138 139 140 141 142 143 144
/*
 * 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)

David Lawrence's avatar
David Lawrence committed
145
/*
146 147 148
 * 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.
David Lawrence's avatar
David Lawrence committed
149
 */
150 151 152 153 154 155 156 157 158 159 160
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}
David Lawrence's avatar
David Lawrence committed
161
};
Bob Halley's avatar
add  
Bob Halley committed
162

David Lawrence's avatar
David Lawrence committed
163
/* XXXDCL make const? */
164
LIBDNS_EXTERNAL_DATA dns_name_t *dns_rootname = &root;
165 166 167 168 169 170 171 172 173 174 175 176

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}
Bob Halley's avatar
Bob Halley committed
177 178
};

David Lawrence's avatar
David Lawrence committed
179
/* XXXDCL make const? */
180
LIBDNS_EXTERNAL_DATA dns_name_t *dns_wildcardname = &wild;
Bob Halley's avatar
Bob Halley committed
181

David Lawrence's avatar
David Lawrence committed
182 183 184 185
static void
set_offsets(const dns_name_t *name, unsigned char *offsets,
	    dns_name_t *set_name);

Bob Halley's avatar
add  
Bob Halley committed
186
void
187
dns_name_init(dns_name_t *name, unsigned char *offsets) {
Bob Halley's avatar
add  
Bob Halley committed
188
	/*
189
	 * Initialize 'name'.
Bob Halley's avatar
add  
Bob Halley committed
190
	 */
Brian Wellington's avatar
Brian Wellington committed
191
	DNS_NAME_INIT(name, offsets);
192 193
}

194 195 196 197 198
void
dns_name_reset(dns_name_t *name) {
	REQUIRE(VALID_NAME(name));
	REQUIRE(BINDABLE(name));

Brian Wellington's avatar
Brian Wellington committed
199
	DNS_NAME_RESET(name);
200 201
}

202 203 204 205 206 207 208 209 210
void
dns_name_invalidate(dns_name_t *name) {
	/*
	 * Make 'name' invalid.
	 */

	REQUIRE(VALID_NAME(name));

	name->magic = 0;
Bob Halley's avatar
add  
Bob Halley committed
211 212 213
	name->ndata = NULL;
	name->length = 0;
	name->labels = 0;
214
	name->attributes = 0;
215
	name->offsets = NULL;
216
	name->buffer = NULL;
217
	ISC_LINK_INIT(name, link);
Bob Halley's avatar
add  
Bob Halley committed
218 219
}

220 221 222
void
dns_name_setbuffer(dns_name_t *name, isc_buffer_t *buffer) {
	/*
223
	 * Dedicate a buffer for use with 'name'.
224 225 226
	 */

	REQUIRE(VALID_NAME(name));
227
	REQUIRE((buffer != NULL && name->buffer == NULL) ||
228
		(buffer == NULL));
229 230 231 232 233

	name->buffer = buffer;
}

isc_boolean_t
David Lawrence's avatar
David Lawrence committed
234
dns_name_hasbuffer(const dns_name_t *name) {
235 236 237 238 239 240 241 242 243 244 245 246
	/*
	 * Does 'name' have a dedicated buffer?
	 */

	REQUIRE(VALID_NAME(name));

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

	return (ISC_FALSE);
}

247
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
248
dns_name_isabsolute(const dns_name_t *name) {
249

Bob Halley's avatar
add  
Bob Halley committed
250 251 252 253 254 255
	/*
	 * Does 'name' end in the root label?
	 */

	REQUIRE(VALID_NAME(name));

256
	if ((name->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
257 258
		return (ISC_TRUE);
	return (ISC_FALSE);
Bob Halley's avatar
add  
Bob Halley committed
259 260
}

Bob Halley's avatar
Bob Halley committed
261
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
262
dns_name_iswildcard(const dns_name_t *name) {
Bob Halley's avatar
Bob Halley committed
263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280
	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);
}

Bob Halley's avatar
Bob Halley committed
281
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
282
dns_name_requiresedns(const dns_name_t *name) {
Bob Halley's avatar
Bob Halley committed
283 284
	/*
	 * Does 'name' require EDNS for transmission?
Mark Andrews's avatar
Mark Andrews committed
285 286
	 * Since we dropped the support of bitstring labels, this function
	 * currently returns a constant value; ISC_FALSE.
Bob Halley's avatar
Bob Halley committed
287 288 289 290
	 */

	REQUIRE(VALID_NAME(name));
	REQUIRE(name->labels > 0);
Mark Andrews's avatar
Mark Andrews committed
291
	UNUSED(name);
Bob Halley's avatar
Bob Halley committed
292

Mark Andrews's avatar
Mark Andrews committed
293
	return (ISC_FALSE);
Bob Halley's avatar
Bob Halley committed
294 295
}

296 297
static inline unsigned int
name_hash(dns_name_t *name, isc_boolean_t case_sensitive) {
Bob Halley's avatar
Bob Halley committed
298
	unsigned int length;
Bob Halley's avatar
Bob Halley committed
299
	const unsigned char *s;
Bob Halley's avatar
Bob Halley committed
300
	unsigned int h = 0;
Bob Halley's avatar
Bob Halley committed
301
	unsigned char c;
Bob Halley's avatar
Bob Halley committed
302 303 304 305 306 307

	length = name->length;
	if (length > 16)
		length = 16;

	/*
308 309
	 * This hash function is similar to the one Ousterhout
	 * uses in Tcl.
Bob Halley's avatar
Bob Halley committed
310 311
	 */
	s = name->ndata;
Bob Halley's avatar
Bob Halley committed
312 313
	if (case_sensitive) {
		while (length > 0) {
314
			h += ( h << 3 ) + *s;
Bob Halley's avatar
Bob Halley committed
315 316 317 318 319 320
			s++;
			length--;
		}
	} else {
		while (length > 0) {
			c = maptolower[*s];
321
			h += ( h << 3 ) + c;
Bob Halley's avatar
Bob Halley committed
322 323
			s++;
			length--;
Bob Halley's avatar
Bob Halley committed
324 325 326 327 328 329
		}
	}

	return (h);
}

330 331 332 333 334 335 336 337 338 339 340 341 342
unsigned int
dns_name_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 (name_hash(name, case_sensitive));
}

343 344 345 346 347 348 349 350 351 352 353 354 355 356
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));
}

357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390
unsigned int
dns_name_hashbylabel(dns_name_t *name, isc_boolean_t case_sensitive) {
	unsigned char *offsets;
	dns_offsets_t odata;
	dns_name_t tname;
	unsigned int h = 0;
	unsigned int i;

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

	if (name->labels == 0)
		return (0);
	else if (name->labels == 1)
		return (name_hash(name, case_sensitive));

	SETUP_OFFSETS(name, offsets, odata);
	DNS_NAME_INIT(&tname, NULL);
	tname.labels = 1;
	h = 0;
	for (i = 0; i < name->labels; i++) {
		tname.ndata = name->ndata + offsets[i];
		if (i == name->labels - 1)
			tname.length = name->length - offsets[i];
		else
			tname.length = offsets[i + 1] - offsets[i];
		h += name_hash(&tname, case_sensitive);
	}

	return (h);
}

391
dns_namereln_t
David Lawrence's avatar
David Lawrence committed
392
dns_name_fullcompare(const dns_name_t *name1, const dns_name_t *name2,
393 394 395
		     int *orderp,
		     unsigned int *nlabelsp, unsigned int *nbitsp)
{
Mark Andrews's avatar
Mark Andrews committed
396
	unsigned int l1, l2, l, count1, count2, count, nlabels;
Bob Halley's avatar
Bob Halley committed
397
	int cdiff, ldiff, chdiff;
Bob Halley's avatar
add  
Bob Halley committed
398
	unsigned char *label1, *label2;
399 400
	unsigned char *offsets1, *offsets2;
	dns_offsets_t odata1, odata2;
401
	dns_namereln_t namereln = dns_namereln_none;
Bob Halley's avatar
add  
Bob Halley committed
402 403 404

	/*
	 * Determine the relative ordering under the DNSSEC order relation of
405 406 407 408 409 410 411
	 * '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.
Bob Halley's avatar
add  
Bob Halley committed
412 413 414 415
	 */

	REQUIRE(VALID_NAME(name1));
	REQUIRE(VALID_NAME(name2));
416 417 418 419 420 421
	REQUIRE(orderp != NULL);
	REQUIRE(nlabelsp != NULL);
	REQUIRE(nbitsp != NULL);
	/*
	 * Either name1 is absolute and name2 is absolute, or neither is.
	 */
Bob Halley's avatar
Bob Halley committed
422 423
	REQUIRE((name1->attributes & DNS_NAMEATTR_ABSOLUTE) ==
		(name2->attributes & DNS_NAMEATTR_ABSOLUTE));
Bob Halley's avatar
add  
Bob Halley committed
424

425 426 427
	SETUP_OFFSETS(name1, offsets1, odata1);
	SETUP_OFFSETS(name2, offsets2, odata2);

428
	nlabels = 0;
Bob Halley's avatar
add  
Bob Halley committed
429 430
	l1 = name1->labels;
	l2 = name2->labels;
Bob Halley's avatar
Bob Halley committed
431 432
	ldiff = (int)l1 - (int)l2;
	if (ldiff < 0)
Bob Halley's avatar
add  
Bob Halley committed
433
		l = l1;
Bob Halley's avatar
Bob Halley committed
434
	else
Bob Halley's avatar
add  
Bob Halley committed
435 436 437 438 439 440
		l = l2;

	while (l > 0) {
		l--;
		l1--;
		l2--;
441 442
		label1 = &name1->ndata[offsets1[l1]];
		label2 = &name2->ndata[offsets2[l2]];
Bob Halley's avatar
add  
Bob Halley committed
443 444 445
		count1 = *label1++;
		count2 = *label2++;

Mark Andrews's avatar
Mark Andrews committed
446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462
		/*
		 * We dropped bitstring labels, and we don't support any
		 * other extended label types.
		 */
		INSIST(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;
463 464
				goto done;
			}
Mark Andrews's avatar
Mark Andrews committed
465 466 467 468 469 470
			count--;
			label1++;
			label2++;
		}
		if (cdiff != 0) {
			*orderp = cdiff;
471
			goto done;
Bob Halley's avatar
add  
Bob Halley committed
472
		}
Mark Andrews's avatar
Mark Andrews committed
473
		nlabels++;
Bob Halley's avatar
add  
Bob Halley committed
474 475
	}

476 477 478 479 480 481 482 483 484 485
	*orderp = ldiff;
	if (ldiff < 0)
		namereln = dns_namereln_contains;
	else if (ldiff > 0)
		namereln = dns_namereln_subdomain;
	else
		namereln = dns_namereln_equal;

 done:
	*nlabelsp = nlabels;
Mark Andrews's avatar
Mark Andrews committed
486
	*nbitsp = 0;
487 488 489 490 491 492 493 494

	if (nlabels > 0 && namereln == dns_namereln_none)
		namereln = dns_namereln_commonancestor;

	return (namereln);
}

int
David Lawrence's avatar
David Lawrence committed
495
dns_name_compare(const dns_name_t *name1, const dns_name_t *name2) {
496 497 498 499 500 501 502 503 504 505 506 507
	int order;
	unsigned int nlabels, nbits;

	/*
	 * Determine the relative ordering under the DNSSEC order relation of
	 * 'name1' and 'name2'.
	 *
	 * 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.
	 */
508

509 510 511
	(void)dns_name_fullcompare(name1, name2, &order, &nlabels, &nbits);

	return (order);
Bob Halley's avatar
add  
Bob Halley committed
512 513
}

Bob Halley's avatar
Bob Halley committed
514
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
515
dns_name_equal(const dns_name_t *name1, const dns_name_t *name2) {
Bob Halley's avatar
Bob Halley committed
516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551
	unsigned int l, count;
	unsigned char c;
	unsigned char *label1, *label2;

	/*
	 * Are 'name1' and 'name2' equal?
	 *
	 * 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));
	/*
	 * Either name1 is absolute and name2 is absolute, or neither is.
	 */
	REQUIRE((name1->attributes & DNS_NAMEATTR_ABSOLUTE) ==
		(name2->attributes & DNS_NAMEATTR_ABSOLUTE));

	if (name1->length != name2->length)
		return (ISC_FALSE);

	l = name1->labels;

	if (l != name2->labels)
		return (ISC_FALSE);

	label1 = name1->ndata;
	label2 = name2->ndata;
	while (l > 0) {
		l--;
		count = *label1++;
		if (count != *label2++)
			return (ISC_FALSE);
Mark Andrews's avatar
Mark Andrews committed
552 553 554 555 556 557 558

		INSIST(count <= 63); /* no bitstring support */

		while (count > 0) {
			count--;
			c = maptolower[*label1++];
			if (c != maptolower[*label2++])
Bob Halley's avatar
Bob Halley committed
559 560 561 562 563 564 565
				return (ISC_FALSE);
		}
	}

	return (ISC_TRUE);
}

566
int
David Lawrence's avatar
David Lawrence committed
567
dns_name_rdatacompare(const dns_name_t *name1, const dns_name_t *name2) {
568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593
	unsigned int l1, l2, l, count1, count2, count;
	unsigned char c1, c2;
	unsigned char *label1, *label2;

	/*
	 * Compare two absolute names as rdata.
	 */

	REQUIRE(VALID_NAME(name1));
	REQUIRE(name1->labels > 0);
	REQUIRE((name1->attributes & DNS_NAMEATTR_ABSOLUTE) != 0);
	REQUIRE(VALID_NAME(name2));
	REQUIRE(name2->labels > 0);
	REQUIRE((name2->attributes & DNS_NAMEATTR_ABSOLUTE) != 0);

	l1 = name1->labels;
	l2 = name2->labels;

	l = (l1 < l2) ? l1 : l2;

	label1 = name1->ndata;
	label2 = name2->ndata;
	while (l > 0) {
		l--;
		count1 = *label1++;
		count2 = *label2++;
Mark Andrews's avatar
Mark Andrews committed
594 595 596 597 598 599 600 601 602 603 604 605 606 607 608

		/* no bitstring support */
		INSIST(count1 <= 63 && count2 <= 63);

		if (count1 != count2)
			return ((count1 < count2) ? -1 : 1);
		count = count1;
		while (count > 0) {
			count--;
			c1 = maptolower[*label1++];
			c2 = maptolower[*label2++];
			if (c1 < c2)
				return (-1);
			else if (c1 > c2)
				return (1);
609 610 611
		}
	}

612 613 614 615 616 617 618
	/*
	 * If one name had more labels than the other, their common
	 * prefix must have been different because the shorter name
	 * ended with the root label and the longer one can't have
	 * a root label in the middle of it.  Therefore, if we get
	 * to this point, the lengths must be equal.
	 */
619 620 621 622 623
	INSIST(l1 == l2);

	return (0);
}

624
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
625
dns_name_issubdomain(const dns_name_t *name1, const dns_name_t *name2) {
626 627 628
	int order;
	unsigned int nlabels, nbits;
	dns_namereln_t namereln;
Bob Halley's avatar
add  
Bob Halley committed
629 630 631 632 633 634 635 636 637 638

	/*
	 * Is 'name1' a subdomain of 'name2'?
	 *
	 * 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.
	 */

639 640 641 642 643
	namereln = dns_name_fullcompare(name1, name2, &order, &nlabels,
					&nbits);
	if (namereln == dns_namereln_subdomain ||
	    namereln == dns_namereln_equal)
		return (ISC_TRUE);
Bob Halley's avatar
add  
Bob Halley committed
644

645
	return (ISC_FALSE);
Bob Halley's avatar
add  
Bob Halley committed
646 647
}

648
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
649
dns_name_matcheswildcard(const dns_name_t *name, const dns_name_t *wname) {
650 651
	int order;
	unsigned int nlabels, nbits, labels;
652 653 654
	dns_name_t tname;

	REQUIRE(VALID_NAME(name));
655
	REQUIRE(name->labels > 0);
656
	REQUIRE(VALID_NAME(wname));
657 658
	labels = wname->labels;
	REQUIRE(labels > 0);
659 660
	REQUIRE(dns_name_iswildcard(wname));

Brian Wellington's avatar
Brian Wellington committed
661
	DNS_NAME_INIT(&tname, NULL);
662
	dns_name_getlabelsequence(wname, 1, labels - 1, &tname);
663 664 665 666
	if (dns_name_fullcompare(name, &tname, &order, &nlabels, &nbits) ==
	    dns_namereln_subdomain)
		return (ISC_TRUE);
	return (ISC_FALSE);
667 668
}

669
unsigned int
David Lawrence's avatar
David Lawrence committed
670
dns_name_depth(const dns_name_t *name) {
Mark Andrews's avatar
Mark Andrews committed
671
	unsigned int depth, count, nrem;
672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687
	unsigned char *ndata;

	/*
	 * The depth of 'name'.
	 */

	REQUIRE(VALID_NAME(name));

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

	depth = 0;
	ndata = name->ndata;
	nrem = name->length;
	while (nrem > 0) {
		count = *ndata++;
Mark Andrews's avatar
Mark Andrews committed
688 689
		INSIST(count <= 63); /* no bitstring support */

690
		nrem--;
Mark Andrews's avatar
Mark Andrews committed
691 692 693 694
		depth++;
		if (count == 0)
			break;

695 696 697 698 699 700 701 702
		INSIST(nrem >= count);
		nrem -= count;
		ndata += count;
	}

	return (depth);
}

Bob Halley's avatar
add  
Bob Halley committed
703
unsigned int
David Lawrence's avatar
David Lawrence committed
704
dns_name_countlabels(const dns_name_t *name) {
Bob Halley's avatar
add  
Bob Halley committed
705 706 707 708 709 710 711 712 713 714 715 716
	/*
	 * How many labels does 'name' have?
	 */

	REQUIRE(VALID_NAME(name));

	ENSURE(name->labels <= 128);

	return (name->labels);
}

void
David Lawrence's avatar
David Lawrence committed
717
dns_name_getlabel(const dns_name_t *name, unsigned int n, dns_label_t *label) {
718 719 720
	unsigned char *offsets;
	dns_offsets_t odata;

Bob Halley's avatar
add  
Bob Halley committed
721 722 723
	/*
	 * Make 'label' refer to the 'n'th least significant label of 'name'.
	 */
724

Bob Halley's avatar
add  
Bob Halley committed
725
	REQUIRE(VALID_NAME(name));
726
	REQUIRE(name->labels > 0);
Bob Halley's avatar
add  
Bob Halley committed
727 728
	REQUIRE(n < name->labels);
	REQUIRE(label != NULL);
729

730 731 732
	SETUP_OFFSETS(name, offsets, odata);

	label->base = &name->ndata[offsets[n]];
Bob Halley's avatar
add  
Bob Halley committed
733
	if (n == name->labels - 1)
734
		label->length = name->length - offsets[n];
Bob Halley's avatar
add  
Bob Halley committed
735
	else
736
		label->length = offsets[n + 1] - offsets[n];
Bob Halley's avatar
add  
Bob Halley committed
737 738 739
}

void
David Lawrence's avatar
David Lawrence committed
740
dns_name_getlabelsequence(const dns_name_t *source,
Bob Halley's avatar
add  
Bob Halley committed
741
			  unsigned int first, unsigned int n,
Bob Halley's avatar
Bob Halley committed
742
			  dns_name_t *target)
Bob Halley's avatar
add  
Bob Halley committed
743
{
744 745
	unsigned char *offsets;
	dns_offsets_t odata;
746
	unsigned int firstoffset, endoffset;
747

Bob Halley's avatar
add  
Bob Halley committed
748 749 750 751 752 753
	/*
	 * Make 'target' refer to the 'n' labels including and following
	 * 'first' in 'source'.
	 */

	REQUIRE(VALID_NAME(source));
754
	REQUIRE(VALID_NAME(target));
755
	REQUIRE(first <= source->labels);
Bob Halley's avatar
add  
Bob Halley committed
756
	REQUIRE(first + n <= source->labels);
757
	REQUIRE(BINDABLE(target));
Bob Halley's avatar
add  
Bob Halley committed
758

759 760
	SETUP_OFFSETS(source, offsets, odata);

761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777
	if (first == source->labels)
		firstoffset = source->length;
	else
		firstoffset = offsets[first];

	if (first + n == source->labels)
		endoffset = source->length;
	else
		endoffset = offsets[first + n];

	target->ndata = &source->ndata[firstoffset];
	target->length = endoffset - firstoffset;
	
	if (first + n == source->labels && n > 0 &&
	    (source->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
		target->attributes |= DNS_NAMEATTR_ABSOLUTE;
	else
778
		target->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
779

Bob Halley's avatar
add  
Bob Halley committed
780 781
	target->labels = n;

Bob Halley's avatar
Bob Halley committed
782 783 784 785 786 787 788
	/*
	 * If source and target are the same, and we're making target
	 * a prefix of source, the offsets table is correct already
	 * so we don't need to call set_offsets().
	 */
	if (target->offsets != NULL &&
	    (target != source || first != 0))
David Lawrence's avatar
David Lawrence committed
789
		set_offsets(target, target->offsets, NULL);
Bob Halley's avatar
add  
Bob Halley committed
790 791
}

Bob Halley's avatar
Bob Halley committed
792 793 794 795 796 797 798 799 800
void
dns_name_clone(dns_name_t *source, dns_name_t *target) {

	/*
	 * Make 'target' refer to the same name as 'source'.
	 */

	REQUIRE(VALID_NAME(source));
	REQUIRE(VALID_NAME(target));
801
	REQUIRE(BINDABLE(target));
Bob Halley's avatar
Bob Halley committed
802 803 804 805

	target->ndata = source->ndata;
	target->length = source->length;
	target->labels = source->labels;
806
	target->attributes = source->attributes &
David Lawrence's avatar
David Lawrence committed
807 808
		(unsigned int)~(DNS_NAMEATTR_READONLY | DNS_NAMEATTR_DYNAMIC |
				DNS_NAMEATTR_DYNOFFSETS);
Bob Halley's avatar
Bob Halley committed
809 810 811 812 813
	if (target->offsets != NULL && source->labels > 0) {
		if (source->offsets != NULL)
			memcpy(target->offsets, source->offsets,
			       source->labels);
		else
David Lawrence's avatar
David Lawrence committed
814
			set_offsets(target, target->offsets, NULL);
Bob Halley's avatar
Bob Halley committed
815 816 817
	}
}

Bob Halley's avatar
add  
Bob Halley committed
818
void
819
dns_name_fromregion(dns_name_t *name, const isc_region_t *r) {
820 821
	unsigned char *offsets;
	dns_offsets_t odata;
822 823
	unsigned int len;
	isc_region_t r2;
824

Bob Halley's avatar
add  
Bob Halley committed
825 826 827 828
	/*
	 * Make 'name' refer to region 'r'.
	 */

829
	REQUIRE(VALID_NAME(name));
Bob Halley's avatar
add  
Bob Halley committed
830
	REQUIRE(r != NULL);
831
	REQUIRE(BINDABLE(name));
Bob Halley's avatar
add  
Bob Halley committed
832

833 834
	INIT_OFFSETS(name, offsets, odata);

835 836
	if (name->buffer != NULL) {
		isc_buffer_clear(name->buffer);
837
		isc_buffer_availableregion(name->buffer, &r2);
838
		len = (r->length < r2.length) ? r->length : r2.length;
839 840
		if (len > DNS_NAME_MAXWIRE)
			len = DNS_NAME_MAXWIRE;
841 842 843 844 845
		memcpy(r2.base, r->base, len);
		name->ndata = r2.base;
		name->length = len;
	} else {
		name->ndata = r->base;
846 847
		name->length = (r->length <= DNS_NAME_MAXWIRE) ? 
			r->length : DNS_NAME_MAXWIRE;
848
	}
Bob Halley's avatar
add  
Bob Halley committed
849 850

	if (r->length > 0)
David Lawrence's avatar
David Lawrence committed
851
		set_offsets(name, offsets, name);
852
	else {
Bob Halley's avatar
add  
Bob Halley committed
853
		name->labels = 0;
854 855
		name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
	}
856 857 858

	if (name->buffer != NULL)
		isc_buffer_add(name->buffer, name->length);
Bob Halley's avatar
add  
Bob Halley committed
859 860 861
}

void
862
dns_name_toregion(dns_name_t *name, isc_region_t *r) {
Bob Halley's avatar
add  
Bob Halley committed
863 864 865 866 867 868 869
	/*
	 * Make 'r' refer to 'name'.
	 */

	REQUIRE(VALID_NAME(name));
	REQUIRE(r != NULL);

870
	DNS_NAME_TOREGION(name, r);
Bob Halley's avatar
add  
Bob Halley committed
871 872 873
}


874
isc_result_t
875
dns_name_fromtext(dns_name_t *name, isc_buffer_t *source,
876
		  dns_name_t *origin, isc_boolean_t downcase,
877
		  isc_buffer_t *target)
Bob Halley's avatar
add  
Bob Halley committed
878 879 880 881
{
	unsigned char *ndata, *label;
	char *tdata;
	char c;
882
	ft_state state, kind;
Bob Halley's avatar
add  
Bob Halley committed
883
	unsigned int value, count, tbcount, bitlength, maxlength;
Bob Halley's avatar
Bob Halley committed
884
	unsigned int n1, n2, vlen, tlen, nrem, nused, digits, labels, tused;
Mark Andrews's avatar
Mark Andrews committed
885
	isc_boolean_t done;
886 887
	unsigned char *offsets;
	dns_offsets_t odata;
Bob Halley's avatar
add  
Bob Halley committed
888 889 890 891 892 893 894 895 896 897 898

	/*
	 * Convert the textual representation of a DNS name at source
	 * into uncompressed wire form stored in target.
	 *
	 * Notes:
	 *	Relative domain names will have 'origin' appended to them
	 *	unless 'origin' is NULL, in which case relative domain names
	 *	will remain relative.
	 */

899
	REQUIRE(VALID_NAME(name));
900 901
	REQUIRE(ISC_BUFFER_VALID(source));
	REQUIRE((target != NULL && ISC_BUFFER_VALID(target)) ||
902
		(target == NULL && ISC_BUFFER_VALID(name->buffer)));
903

904 905 906 907
	if (target == NULL && name->buffer != NULL) {
		target = name->buffer;
		isc_buffer_clear(target);
	}
908

909
	REQUIRE(BINDABLE(name));
910

911
	INIT_OFFSETS(name, offsets, odata);
912
	offsets[0] = 0;
913

Bob Halley's avatar
add  
Bob Halley committed
914 915 916 917 918 919 920 921 922 923 924 925 926
	/*
	 * Initialize things to make the compiler happy; they're not required.
	 */
	n1 = 0;
	n2 = 0;
	vlen = 0;
	label = NULL;
	digits = 0;
	value = 0;
	count = 0;
	tbcount = 0;
	bitlength = 0;
	maxlength = 0;
927
	kind = ft_init;
Bob Halley's avatar
add  
Bob Halley committed
928 929

	/*
930
	 * Make 'name' empty in case of failure.
Bob Halley's avatar
add  
Bob Halley committed
931
	 */
932
	MAKE_EMPTY(name);
Bob Halley's avatar
add  
Bob Halley committed
933 934 935 936

	/*
	 * Set up the state machine.
	 */
937
	tdata = (char *)source->base + source->current;
938
	tlen = isc_buffer_remaininglength(source);
939
	tused = 0;
940 941
	ndata = isc_buffer_used(target);
	nrem = isc_buffer_availablelength(target);
Bob Halley's avatar
add  
Bob Halley committed
942 943
	if (nrem > 255)
		nrem = 255;
Bob Halley's avatar
Bob Halley committed
944
	nused = 0;
Bob Halley's avatar
add  
Bob Halley committed
945
	labels = 0;
946
	done = ISC_FALSE;
947
	state = ft_init;
Bob Halley's avatar
add  
Bob Halley committed
948 949 950 951

	while (nrem > 0 && tlen > 0 && !done) {
		c = *tdata++;
		tlen--;
952
		tused++;
Bob Halley's avatar
add  
Bob Halley committed
953 954

		switch (state) {
955
		case ft_init:
Bob Halley's avatar
add  
Bob Halley committed
956 957 958 959 960 961 962 963 964
			/*
			 * Is this the root name?
			 */
			if (c == '.') {
				if (tlen != 0)
					return (DNS_R_EMPTYLABEL);
				labels++;
				*ndata++ = 0;
				nrem--;
Bob Halley's avatar
Bob Halley committed
965
				nused++;
966
				done = ISC_TRUE;
Bob Halley's avatar
add  
Bob Halley committed
967 968
				break;
			}
969 970 971
			if (c == '@' && tlen == 0) {
				state = ft_at;
				break;
972
			}
973

Bob Halley's avatar
add  
Bob Halley committed
974
			/* FALLTHROUGH */
975
		case ft_start:
Bob Halley's avatar
add  
Bob Halley committed
976 977 978
			label = ndata;
			ndata++;
			nrem--;
Bob Halley's avatar
Bob Halley committed
979
			nused++;
Bob Halley's avatar
add  
Bob Halley committed
980 981
			count = 0;
			if (c == '\\') {
982
				state = ft_initialescape;
Bob Halley's avatar
add  
Bob Halley committed
983 984
				break;
			}
985 986
			kind = ft_ordinary;
			state = ft_ordinary;
987 988
			if (nrem == 0)
				return (ISC_R_NOSPACE);
Bob Halley's avatar
add  
Bob Halley committed
989
			/* FALLTHROUGH */
990
		case ft_ordinary:
Bob Halley's avatar
add  
Bob Halley committed
991 992 993 994 995
			if (c == '.') {
				if (count == 0)
					return (DNS_R_EMPTYLABEL);
				*label = count;
				labels++;
996 997
				INSIST(labels <= 127);
				offsets[labels] = nused;
Bob Halley's avatar
add  
Bob Halley committed
998 999 1000 1001
				if (tlen == 0) {
					labels++;
					*ndata++ = 0;
					nrem--;
Bob Halley's avatar
Bob Halley committed
1002
					nused++;
1003
					done = ISC_TRUE;
Bob Halley's avatar
add  
Bob Halley committed
1004
				}
1005
				state = ft_start;
Bob Halley's avatar
add  
Bob Halley committed
1006
			} else if (c == '\\') {
1007
				state = ft_escape;
Bob Halley's avatar
add  
Bob Halley committed
1008 1009 1010 1011
			} else {
				if (count >= 63)
					return (DNS_R_LABELTOOLONG);
				count++;
1012
				CONVERTTOASCII(c);
Bob Halley's avatar
add  
Bob Halley committed
1013 1014 1015 1016
				if (downcase)
					c = maptolower[(int)c];
				*ndata++ = c;
				nrem--;
Bob Halley's avatar
Bob Halley committed
1017
				nused++;
Bob Halley's avatar
add  
Bob Halley committed
1018 1019
			}
			break;
1020
		case ft_initialescape:
Bob Halley's avatar
add  
Bob Halley committed
1021
			if (c == '[') {
Mark Andrews's avatar
Mark Andrews committed
1022 1023 1024 1025 1026
				/*
				 * This looks like a bitstring label, which
				 * was deprecated.  Intentionally drop it.
				 */
				return (DNS_R_BADLABELTYPE);
Bob Halley's avatar
add  
Bob Halley committed
1027
			}
1028 1029
			kind = ft_ordinary;
			state = ft_escape;
Bob Halley's avatar
add  
Bob Halley committed
1030
			/* FALLTHROUGH */
1031
		case ft_escape: