name.c 49.6 KB
Newer Older
Bob Halley's avatar
Bob Halley committed
1
/*
Mark Andrews's avatar
Mark Andrews committed
2
 * Copyright (C) 2004, 2005  Internet Systems Consortium, Inc. ("ISC")
Mark Andrews's avatar
Mark Andrews committed
3
 * Copyright (C) 1998-2003  Internet Software Consortium.
4
 *
Bob Halley's avatar
Bob Halley committed
5 6 7
 * 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.
8
 *
Mark Andrews's avatar
Mark Andrews committed
9 10 11 12 13 14 15
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC 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.148 2005/01/10 23:43:22 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

182 183 184
unsigned int
dns_fullname_hash(dns_name_t *name, isc_boolean_t case_sensitive);

David Lawrence's avatar
David Lawrence committed
185 186 187 188
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
189
void
190
dns_name_init(dns_name_t *name, unsigned char *offsets) {
Bob Halley's avatar
add  
Bob Halley committed
191
	/*
192
	 * Initialize 'name'.
Bob Halley's avatar
add  
Bob Halley committed
193
	 */
Brian Wellington's avatar
Brian Wellington committed
194
	DNS_NAME_INIT(name, offsets);
195 196
}

197 198 199 200 201
void
dns_name_reset(dns_name_t *name) {
	REQUIRE(VALID_NAME(name));
	REQUIRE(BINDABLE(name));

Brian Wellington's avatar
Brian Wellington committed
202
	DNS_NAME_RESET(name);
203 204
}

205 206 207 208 209 210 211 212 213
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
214 215 216
	name->ndata = NULL;
	name->length = 0;
	name->labels = 0;
217
	name->attributes = 0;
218
	name->offsets = NULL;
219
	name->buffer = NULL;
220
	ISC_LINK_INIT(name, link);
Bob Halley's avatar
add  
Bob Halley committed
221 222
}

223 224 225
void
dns_name_setbuffer(dns_name_t *name, isc_buffer_t *buffer) {
	/*
226
	 * Dedicate a buffer for use with 'name'.
227 228 229
	 */

	REQUIRE(VALID_NAME(name));
230
	REQUIRE((buffer != NULL && name->buffer == NULL) ||
231
		(buffer == NULL));
232 233 234 235 236

	name->buffer = buffer;
}

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

	REQUIRE(VALID_NAME(name));

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

	return (ISC_FALSE);
}

250
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
251
dns_name_isabsolute(const dns_name_t *name) {
252

Bob Halley's avatar
add  
Bob Halley committed
253 254 255 256 257 258
	/*
	 * Does 'name' end in the root label?
	 */

	REQUIRE(VALID_NAME(name));

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

264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290
#define hyphenchar(c) ((c) == 0x2d)
#define asterchar(c) ((c) == 0x2a)
#define alphachar(c) (((c) >= 0x41 && (c) <= 0x5a) \
		      || ((c) >= 0x61 && (c) <= 0x7a))
#define digitchar(c) ((c) >= 0x30 && (c) <= 0x39)
#define borderchar(c) (alphachar(c) || digitchar(c))
#define middlechar(c) (borderchar(c) || hyphenchar(c))
#define domainchar(c) ((c) > 0x20 && (c) < 0x7f)

isc_boolean_t
dns_name_ismailbox(const dns_name_t *name) {
	unsigned char *ndata, ch;
	unsigned int n;
	isc_boolean_t first;

	REQUIRE(VALID_NAME(name));
	REQUIRE(name->labels > 0);
	REQUIRE(name->attributes & DNS_NAMEATTR_ABSOLUTE);

	/* 
	 * Root label.
	 */
	if (name->length == 1)
		return (ISC_TRUE);

	ndata = name->ndata;
	n = *ndata++;
291
	INSIST(n <= 63);
292 293 294 295 296 297 298 299 300 301 302 303 304 305
	while (n--) {
		ch = *ndata++;
		if (!domainchar(ch))
			return (ISC_FALSE);
	}
	
	if (ndata == name->ndata + name->length)
		return (ISC_FALSE);

	/*
	 * RFC292/RFC1123 hostname.
	 */
	while (ndata < (name->ndata + name->length)) {
		n = *ndata++;
306
		INSIST(n <= 63);
307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
		first = ISC_TRUE;
		while (n--) {
			ch = *ndata++;
			if (first || n == 0) {
				if (!borderchar(ch))
					return (ISC_FALSE);
			} else {
				if (!middlechar(ch))
					return (ISC_FALSE);
			}
			first = ISC_FALSE;
		}
	}
	return (ISC_TRUE);
}

isc_boolean_t
dns_name_ishostname(const dns_name_t *name, isc_boolean_t wildcard) {
	unsigned char *ndata, ch;
	unsigned int n;
	isc_boolean_t first;

	REQUIRE(VALID_NAME(name));
	REQUIRE(name->labels > 0);
	REQUIRE(name->attributes & DNS_NAMEATTR_ABSOLUTE);
	
	/* 
	 * Root label.
	 */
	if (name->length == 1)
		return (ISC_TRUE);

	/*
	 * Skip wildcard if this is a ownername.
	 */
	ndata = name->ndata;
	if (wildcard && ndata[0] == 1 && ndata[1] == '*')
		ndata += 2;

	/*
	 * RFC292/RFC1123 hostname.
	 */
	while (ndata < (name->ndata + name->length)) {
		n = *ndata++;
351
		INSIST(n <= 63);
352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367
		first = ISC_TRUE;
		while (n--) {
			ch = *ndata++;
			if (first || n == 0) {
				if (!borderchar(ch))
					return (ISC_FALSE);
			} else {
				if (!middlechar(ch))
					return (ISC_FALSE);
			}
			first = ISC_FALSE;
		}
	}
	return (ISC_TRUE);
}

Bob Halley's avatar
Bob Halley committed
368
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
369
dns_name_iswildcard(const dns_name_t *name) {
Bob Halley's avatar
Bob Halley committed
370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387
	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);
}

388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422
isc_boolean_t
dns_name_internalwildcard(const dns_name_t *name) {
	unsigned char *ndata;
	unsigned int count;
	unsigned int label;

	/*
	 * Does 'name' contain a internal wildcard?
	 */

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

	/*
	 * Skip first label.
	 */
	ndata = name->ndata;
	count = *ndata++;
	INSIST(count <= 63);
	ndata += count;
	label = 1;
	/*
	 * Check all but the last of the remaining labels.
	 */
	while (label + 1 < name->labels) {
		count = *ndata++;
		INSIST(count <= 63);
		if (count == 1 && *ndata == '*')
			return (ISC_TRUE);
		ndata += count;
		label++;
	}
	return (ISC_FALSE);
}

423 424
static inline unsigned int
name_hash(dns_name_t *name, isc_boolean_t case_sensitive) {
Bob Halley's avatar
Bob Halley committed
425
	unsigned int length;
Bob Halley's avatar
Bob Halley committed
426
	const unsigned char *s;
Bob Halley's avatar
Bob Halley committed
427
	unsigned int h = 0;
Bob Halley's avatar
Bob Halley committed
428
	unsigned char c;
Bob Halley's avatar
Bob Halley committed
429 430 431 432 433 434

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

	/*
435 436
	 * This hash function is similar to the one Ousterhout
	 * uses in Tcl.
Bob Halley's avatar
Bob Halley committed
437 438
	 */
	s = name->ndata;
Bob Halley's avatar
Bob Halley committed
439 440
	if (case_sensitive) {
		while (length > 0) {
441
			h += ( h << 3 ) + *s;
Bob Halley's avatar
Bob Halley committed
442 443 444 445 446 447
			s++;
			length--;
		}
	} else {
		while (length > 0) {
			c = maptolower[*s];
448
			h += ( h << 3 ) + c;
Bob Halley's avatar
Bob Halley committed
449 450
			s++;
			length--;
Bob Halley's avatar
Bob Halley committed
451 452 453 454 455 456
		}
	}

	return (h);
}

457 458 459 460 461 462 463 464 465 466 467 468 469
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));
}

470
unsigned int
471
dns_name_fullhash(dns_name_t *name, isc_boolean_t case_sensitive) {
472 473 474 475 476 477 478 479 480 481 482 483
	/*
	 * 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));
}

484 485 486 487 488 489 490 491 492 493 494 495
unsigned int
dns_fullname_hash(dns_name_t *name, isc_boolean_t case_sensitive) {
	/*
	 * This function was deprecated due to the breakage of the name space
	 * convention.  We only keep this internally to provide binary backward
	 * compatibility.
	 */
	REQUIRE(VALID_NAME(name));

	return (dns_name_fullhash(name, case_sensitive));
}

496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529
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);
}

530
dns_namereln_t
David Lawrence's avatar
David Lawrence committed
531
dns_name_fullcompare(const dns_name_t *name1, const dns_name_t *name2,
532
		     int *orderp, unsigned int *nlabelsp)
533
{
Mark Andrews's avatar
Mark Andrews committed
534
	unsigned int l1, l2, l, count1, count2, count, nlabels;
Bob Halley's avatar
Bob Halley committed
535
	int cdiff, ldiff, chdiff;
Bob Halley's avatar
add  
Bob Halley committed
536
	unsigned char *label1, *label2;
537 538
	unsigned char *offsets1, *offsets2;
	dns_offsets_t odata1, odata2;
539
	dns_namereln_t namereln = dns_namereln_none;
Bob Halley's avatar
add  
Bob Halley committed
540 541 542

	/*
	 * Determine the relative ordering under the DNSSEC order relation of
543 544 545 546 547 548 549
	 * '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
550 551 552 553
	 */

	REQUIRE(VALID_NAME(name1));
	REQUIRE(VALID_NAME(name2));
554 555 556 557 558
	REQUIRE(orderp != NULL);
	REQUIRE(nlabelsp != NULL);
	/*
	 * Either name1 is absolute and name2 is absolute, or neither is.
	 */
Bob Halley's avatar
Bob Halley committed
559 560
	REQUIRE((name1->attributes & DNS_NAMEATTR_ABSOLUTE) ==
		(name2->attributes & DNS_NAMEATTR_ABSOLUTE));
Bob Halley's avatar
add  
Bob Halley committed
561

562 563 564
	SETUP_OFFSETS(name1, offsets1, odata1);
	SETUP_OFFSETS(name2, offsets2, odata2);

565
	nlabels = 0;
Bob Halley's avatar
add  
Bob Halley committed
566 567
	l1 = name1->labels;
	l2 = name2->labels;
Bob Halley's avatar
Bob Halley committed
568 569
	ldiff = (int)l1 - (int)l2;
	if (ldiff < 0)
Bob Halley's avatar
add  
Bob Halley committed
570
		l = l1;
Bob Halley's avatar
Bob Halley committed
571
	else
Bob Halley's avatar
add  
Bob Halley committed
572 573 574 575 576 577
		l = l2;

	while (l > 0) {
		l--;
		l1--;
		l2--;
578 579
		label1 = &name1->ndata[offsets1[l1]];
		label2 = &name2->ndata[offsets2[l2]];
Bob Halley's avatar
add  
Bob Halley committed
580 581 582
		count1 = *label1++;
		count2 = *label2++;

Mark Andrews's avatar
Mark Andrews committed
583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599
		/*
		 * 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;
600 601
				goto done;
			}
Mark Andrews's avatar
Mark Andrews committed
602 603 604 605 606 607
			count--;
			label1++;
			label2++;
		}
		if (cdiff != 0) {
			*orderp = cdiff;
608
			goto done;
Bob Halley's avatar
add  
Bob Halley committed
609
		}
Mark Andrews's avatar
Mark Andrews committed
610
		nlabels++;
Bob Halley's avatar
add  
Bob Halley committed
611 612
	}

613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630
	*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;

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

	return (namereln);
}

int
David Lawrence's avatar
David Lawrence committed
631
dns_name_compare(const dns_name_t *name1, const dns_name_t *name2) {
632
	int order;
633
	unsigned int nlabels;
634 635 636 637 638 639 640 641 642 643

	/*
	 * 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.
	 */
644

645
	(void)dns_name_fullcompare(name1, name2, &order, &nlabels);
646 647

	return (order);
Bob Halley's avatar
add  
Bob Halley committed
648 649
}

Bob Halley's avatar
Bob Halley committed
650
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
651
dns_name_equal(const dns_name_t *name1, const dns_name_t *name2) {
Bob Halley's avatar
Bob Halley committed
652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687
	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
688 689 690 691 692 693 694

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

		while (count > 0) {
			count--;
			c = maptolower[*label1++];
			if (c != maptolower[*label2++])
Bob Halley's avatar
Bob Halley committed
695 696 697 698 699 700 701
				return (ISC_FALSE);
		}
	}

	return (ISC_TRUE);
}

702
int
David Lawrence's avatar
David Lawrence committed
703
dns_name_rdatacompare(const dns_name_t *name1, const dns_name_t *name2) {
704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729
	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
730 731 732 733 734 735 736 737 738 739 740 741 742 743 744

		/* 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);
745 746 747
		}
	}

748 749 750 751 752 753 754
	/*
	 * 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.
	 */
755 756 757 758 759
	INSIST(l1 == l2);

	return (0);
}

760
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
761
dns_name_issubdomain(const dns_name_t *name1, const dns_name_t *name2) {
762
	int order;
763
	unsigned int nlabels;
764
	dns_namereln_t namereln;
Bob Halley's avatar
add  
Bob Halley committed
765 766 767 768 769 770 771 772 773 774

	/*
	 * 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.
	 */

775
	namereln = dns_name_fullcompare(name1, name2, &order, &nlabels);
776 777 778
	if (namereln == dns_namereln_subdomain ||
	    namereln == dns_namereln_equal)
		return (ISC_TRUE);
Bob Halley's avatar
add  
Bob Halley committed
779

780
	return (ISC_FALSE);
Bob Halley's avatar
add  
Bob Halley committed
781 782
}

783
isc_boolean_t
David Lawrence's avatar
David Lawrence committed
784
dns_name_matcheswildcard(const dns_name_t *name, const dns_name_t *wname) {
785
	int order;
786
	unsigned int nlabels, labels;
787 788 789
	dns_name_t tname;

	REQUIRE(VALID_NAME(name));
790
	REQUIRE(name->labels > 0);
791
	REQUIRE(VALID_NAME(wname));
792 793
	labels = wname->labels;
	REQUIRE(labels > 0);
794 795
	REQUIRE(dns_name_iswildcard(wname));

Brian Wellington's avatar
Brian Wellington committed
796
	DNS_NAME_INIT(&tname, NULL);
797
	dns_name_getlabelsequence(wname, 1, labels - 1, &tname);
798
	if (dns_name_fullcompare(name, &tname, &order, &nlabels) ==
799 800 801
	    dns_namereln_subdomain)
		return (ISC_TRUE);
	return (ISC_FALSE);
802 803
}

Bob Halley's avatar
add  
Bob Halley committed
804
unsigned int
David Lawrence's avatar
David Lawrence committed
805
dns_name_countlabels(const dns_name_t *name) {
Bob Halley's avatar
add  
Bob Halley committed
806 807 808 809 810 811 812 813 814 815 816 817
	/*
	 * 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
818
dns_name_getlabel(const dns_name_t *name, unsigned int n, dns_label_t *label) {
819 820 821
	unsigned char *offsets;
	dns_offsets_t odata;

Bob Halley's avatar
add  
Bob Halley committed
822 823 824
	/*
	 * Make 'label' refer to the 'n'th least significant label of 'name'.
	 */
825

Bob Halley's avatar
add  
Bob Halley committed
826
	REQUIRE(VALID_NAME(name));
827
	REQUIRE(name->labels > 0);
Bob Halley's avatar
add  
Bob Halley committed
828 829
	REQUIRE(n < name->labels);
	REQUIRE(label != NULL);
830

831 832 833
	SETUP_OFFSETS(name, offsets, odata);

	label->base = &name->ndata[offsets[n]];
Bob Halley's avatar
add  
Bob Halley committed
834
	if (n == name->labels - 1)
835
		label->length = name->length - offsets[n];
Bob Halley's avatar
add  
Bob Halley committed
836
	else
837
		label->length = offsets[n + 1] - offsets[n];
Bob Halley's avatar
add  
Bob Halley committed
838 839 840
}

void
David Lawrence's avatar
David Lawrence committed
841
dns_name_getlabelsequence(const dns_name_t *source,
Bob Halley's avatar
add  
Bob Halley committed
842
			  unsigned int first, unsigned int n,
Bob Halley's avatar
Bob Halley committed
843
			  dns_name_t *target)
Bob Halley's avatar
add  
Bob Halley committed
844
{
845 846
	unsigned char *offsets;
	dns_offsets_t odata;
847
	unsigned int firstoffset, endoffset;
848

Bob Halley's avatar
add  
Bob Halley committed
849 850 851 852 853 854
	/*
	 * Make 'target' refer to the 'n' labels including and following
	 * 'first' in 'source'.
	 */

	REQUIRE(VALID_NAME(source));
855
	REQUIRE(VALID_NAME(target));
856
	REQUIRE(first <= source->labels);
Bob Halley's avatar
add  
Bob Halley committed
857
	REQUIRE(first + n <= source->labels);
858
	REQUIRE(BINDABLE(target));
Bob Halley's avatar
add  
Bob Halley committed
859

860 861
	SETUP_OFFSETS(source, offsets, odata);

862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878
	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
879
		target->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
880

Bob Halley's avatar
add  
Bob Halley committed
881 882
	target->labels = n;

Bob Halley's avatar
Bob Halley committed
883 884 885 886 887 888 889
	/*
	 * 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
890
		set_offsets(target, target->offsets, NULL);
Bob Halley's avatar
add  
Bob Halley committed
891 892
}

Bob Halley's avatar
Bob Halley committed
893 894 895 896 897 898 899 900 901
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));
902
	REQUIRE(BINDABLE(target));
Bob Halley's avatar
Bob Halley committed
903 904 905 906

	target->ndata = source->ndata;
	target->length = source->length;
	target->labels = source->labels;
907
	target->attributes = source->attributes &
David Lawrence's avatar
David Lawrence committed
908 909
		(unsigned int)~(DNS_NAMEATTR_READONLY | DNS_NAMEATTR_DYNAMIC |
				DNS_NAMEATTR_DYNOFFSETS);
Bob Halley's avatar
Bob Halley committed
910 911 912 913 914
	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
915
			set_offsets(target, target->offsets, NULL);
Bob Halley's avatar
Bob Halley committed
916 917 918
	}
}

Bob Halley's avatar
add  
Bob Halley committed
919
void
920
dns_name_fromregion(dns_name_t *name, const isc_region_t *r) {
921 922
	unsigned char *offsets;
	dns_offsets_t odata;
923 924
	unsigned int len;
	isc_region_t r2;
925

Bob Halley's avatar
add  
Bob Halley committed
926 927 928 929
	/*
	 * Make 'name' refer to region 'r'.
	 */

930
	REQUIRE(VALID_NAME(name));
Bob Halley's avatar
add  
Bob Halley committed
931
	REQUIRE(r != NULL);
932
	REQUIRE(BINDABLE(name));
Bob Halley's avatar
add  
Bob Halley committed
933

934 935
	INIT_OFFSETS(name, offsets, odata);

936 937
	if (name->buffer != NULL) {
		isc_buffer_clear(name->buffer);
938
		isc_buffer_availableregion(name->buffer, &r2);
939
		len = (r->length < r2.length) ? r->length : r2.length;
940 941
		if (len > DNS_NAME_MAXWIRE)
			len = DNS_NAME_MAXWIRE;
942 943 944 945 946
		memcpy(r2.base, r->base, len);
		name->ndata = r2.base;
		name->length = len;
	} else {
		name->ndata = r->base;
947 948
		name->length = (r->length <= DNS_NAME_MAXWIRE) ? 
			r->length : DNS_NAME_MAXWIRE;
949
	}
Bob Halley's avatar
add  
Bob Halley committed
950 951

	if (r->length > 0)
David Lawrence's avatar
David Lawrence committed
952
		set_offsets(name, offsets, name);
953
	else {
Bob Halley's avatar
add  
Bob Halley committed
954
		name->labels = 0;
955 956
		name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
	}
957 958 959

	if (name->buffer != NULL)
		isc_buffer_add(name->buffer, name->length);
Bob Halley's avatar
add  
Bob Halley committed
960 961 962
}

void
963
dns_name_toregion(dns_name_t *name, isc_region_t *r) {
Bob Halley's avatar
add  
Bob Halley committed
964 965 966 967 968 969 970
	/*
	 * Make 'r' refer to 'name'.
	 */

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

971
	DNS_NAME_TOREGION(name, r);
Bob Halley's avatar
add  
Bob Halley committed
972 973 974
}


975
isc_result_t
976
dns_name_fromtext(dns_name_t *name, isc_buffer_t *source,
977
		  dns_name_t *origin, unsigned int options,
978
		  isc_buffer_t *target)
Bob Halley's avatar
add  
Bob Halley committed
979 980 981 982
{
	unsigned char *ndata, *label;
	char *tdata;
	char c;
983
	ft_state state, kind;
Bob Halley's avatar
add  
Bob Halley committed
984
	unsigned int value, count, tbcount, bitlength, maxlength;
Bob Halley's avatar
Bob Halley committed
985
	unsigned int n1, n2, vlen, tlen, nrem, nused, digits, labels, tused;
Mark Andrews's avatar
Mark Andrews committed
986
	isc_boolean_t done;
987 988
	unsigned char *offsets;
	dns_offsets_t odata;
989
	isc_boolean_t downcase;
Bob Halley's avatar
add  
Bob Halley committed
990 991 992 993 994 995 996 997 998 999 1000

	/*
	 * 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.
	 */

1001
	REQUIRE(VALID_NAME(name));
1002 1003
	REQUIRE(ISC_BUFFER_VALID(source));
	REQUIRE((target != NULL && ISC_BUFFER_VALID(target)) ||
1004
		(target == NULL && ISC_BUFFER_VALID(name->buffer)));
1005 1006
	
	downcase = ISC_TF((options & DNS_NAME_DOWNCASE) != 0);
1007

1008 1009 1010 1011
	if (target == NULL && name->buffer != NULL) {
		target = name->buffer;
		isc_buffer_clear(target);
	}
1012

1013
	REQUIRE(BINDABLE(name));
1014

1015
	INIT_OFFSETS(name, offsets, odata);
1016
	offsets[0] = 0;
1017

Bob Halley's avatar
add  
Bob Halley committed
1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030
	/*
	 * 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;
1031
	kind = ft_init;
Bob Halley's avatar
add  
Bob Halley committed
1032 1033

	/*
1034
	 * Make 'name' empty in case of failure.
Bob Halley's avatar
add  
Bob Halley committed
1035
	 */
1036
	MAKE_EMPTY(name);
Bob Halley's avatar
add  
Bob Halley committed
1037 1038 1039 1040

	/*
	 * Set up the state machine.
	 */
1041
	tdata = (char *)source->base + source->current;
1042
	tlen = isc_buffer_remaininglength(source);
1043
	tused = 0;
1044 1045
	ndata = isc_buffer_used(target);
	nrem = isc_buffer_availablelength(target);
Bob Halley's avatar
add  
Bob Halley committed
1046 1047
	if (nrem > 255)
		nrem = 255;
Bob Halley's avatar
Bob Halley committed
1048
	nused = 0;
Bob Halley's avatar
add  
Bob Halley committed
1049
	labels = 0;
1050
	done = ISC_FALSE;
1051
	state = ft_init;
Bob Halley's avatar
add  
Bob Halley committed
1052 1053 1054 1055

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

		switch (state) {
1059
		case ft_init:
Bob Halley's avatar
add  
Bob Halley committed
1060 1061 1062 1063 1064 1065 1066 1067 1068
			/*
			 * 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
1069
				nused++;
1070
				done = ISC_TRUE;
Bob Halley's avatar
add  
Bob Halley committed
1071 1072
				break;
			}
1073 1074 1075
			if (c == '@' && tlen == 0) {
				state = ft_at;
				break;
1076
			}
1077

Bob Halley's avatar
add  
Bob Halley committed
1078
			/* FALLTHROUGH */
1079
		case ft_start:
Bob Halley's avatar
add  
Bob Halley committed
1080 1081 1082
			label = ndata;
			ndata++;
			nrem--;
Bob Halley's avatar
Bob Halley committed
1083
			nused++;
Bob Halley's avatar
add  
Bob Halley committed
1084 1085
			count = 0;
			if (c == '\\') {
1086
				state = ft_initialescape;
Bob Halley's avatar
add  
Bob Halley committed
1087 1088
				break;
			}
Bob Halley's avatar