contrib/bind-9.2.4rc7/lib/dns/name.c

   1 /*
   2  * Copyright (C) 2004  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1998-2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id: name.c,v 1.127.2.9 2004/03/09 06:11:03 marka Exp $ */
  19
  20 #include <config.h>
  21
  22 #include <ctype.h>
  23
  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>
  29 #include <isc/util.h>
  30
  31 #include <dns/compress.h>
  32 #include <dns/name.h>
  33 #include <dns/result.h>
  34
  35 #define VALID_NAME(n)   ISC_MAGIC_VALID(n, DNS_NAME_MAGIC)
  36
  37 typedef enum {
  38         ft_init = 0,
  39         ft_start,
  40         ft_ordinary,
  41         ft_initialescape,
  42         ft_escape,
  43         ft_escdecimal,
  44         ft_bitstring,
  45         ft_binary,
  46         ft_octal,
  47         ft_hex,
  48         ft_dottedquad,
  49         ft_dqdecimal,
  50         ft_maybeslash,
  51         ft_finishbitstring,
  52         ft_bitlength,
  53         ft_eatdot,
  54         ft_at
  55 } ft_state;
  56
  57 typedef enum {
  58         fw_start = 0,
  59         fw_ordinary,
  60         fw_copy,
  61         fw_bitstring,
  62         fw_newcurrent
  63 } fw_state;
  64
  65 static char digitvalue[256] = {
  66         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*16*/
  67         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*32*/
  68         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*48*/
  69          0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, /*64*/
  70         -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*80*/
  71         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*96*/
  72         -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*112*/
  73         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*128*/
  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,
  76         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  77         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  78         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  79         -1, -1, -1, -1, -1, -1, -1, -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,
  81         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*256*/
  82 };
  83
  84 static char hexdigits[16] = {
  85         '0', '1', '2', '3', '4', '5', '6', '7',
  86         '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'
  87 };
  88
  89 static unsigned char maptolower[] = {
  90         0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
  91         0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
  92         0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
  93         0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
  94         0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
  95         0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
  96         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  97         0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
  98         0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
  99         0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
 100         0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
 101         0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
 102         0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
 103         0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
 104         0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
 105         0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
 106         0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
 107         0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
 108         0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
 109         0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
 110         0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
 111         0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
 112         0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
 113         0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
 114         0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
 115         0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
 116         0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
 117         0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
 118         0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
 119         0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
 120         0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
 121         0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
 122 };
 123
 124 #define CONVERTTOASCII(c)
 125 #define CONVERTFROMASCII(c)
 126
 127 #define INIT_OFFSETS(name, var, default) \
 128         if (name->offsets != NULL) \
 129                 var = name->offsets; \
 130         else \
 131                 var = default;
 132
 133 #define SETUP_OFFSETS(name, var, default) \
 134         if (name->offsets != NULL) \
 135                 var = name->offsets; \
 136         else { \
 137                 var = default; \
 138                 set_offsets(name, var, NULL); \
 139         }
 140
 141 /*
 142  * Note:  If additional attributes are added that should not be set for
 143  *        empty names, MAKE_EMPTY() must be changed so it clears them.
 144  */
 145 #define MAKE_EMPTY(name) \
 146 do { \
 147         name->ndata = NULL; \
 148         name->length = 0; \
 149         name->labels = 0; \
 150         name->attributes &= ~DNS_NAMEATTR_ABSOLUTE; \
 151 } while (0);
 152
 153 /*
 154  * A name is "bindable" if it can be set to point to a new value, i.e.
 155  * name->ndata and name->length may be changed.
 156  */
 157 #define BINDABLE(name) \
 158         ((name->attributes & (DNS_NAMEATTR_READONLY|DNS_NAMEATTR_DYNAMIC)) \
 159          == 0)
 160
 161 /*
 162  * Note that the name data must be a char array, not a string
 163  * literal, to avoid compiler warnings about discarding
 164  * the const attribute of a string.
 165  */
 166 static unsigned char root_ndata[] = { '\0' };
 167 static unsigned char root_offsets[] = { 0 };
 168
 169 static dns_name_t root =
 170 {
 171         DNS_NAME_MAGIC,
 172         root_ndata, 1, 1,
 173         DNS_NAMEATTR_READONLY | DNS_NAMEATTR_ABSOLUTE,
 174         root_offsets, NULL,
 175         {(void *)-1, (void *)-1},
 176         {NULL, NULL}
 177 };
 178
 179 /* XXXDCL make const? */
 180 dns_name_t *dns_rootname = &root;
 181
 182 static unsigned char wild_ndata[] = { '\001', '*' };
 183 static unsigned char wild_offsets[] = { 0 };
 184
 185 static dns_name_t wild =
 186 {
 187         DNS_NAME_MAGIC,
 188         wild_ndata, 2, 1,
 189         DNS_NAMEATTR_READONLY,
 190         wild_offsets, NULL,
 191         {(void *)-1, (void *)-1},
 192         {NULL, NULL}
 193 };
 194
 195 /* XXXDCL make const? */
 196 dns_name_t *dns_wildcardname = &wild;
 197
 198 static void
 199 set_offsets(const dns_name_t *name, unsigned char *offsets,
 200             dns_name_t *set_name);
 201
 202 static void
 203 compact(dns_name_t *name, unsigned char *offsets);
 204
 205 /*
 206  * Yes, get_bit and set_bit are lame.  We define them here so they can
 207  * be inlined by smart compilers.
 208  */
 209
 210 static inline unsigned int
 211 get_bit(unsigned char *array, unsigned int idx) {
 212         unsigned int byte, shift;
 213
 214         byte = array[idx / 8];
 215         shift = 7 - (idx % 8);
 216
 217         return ((byte >> shift) & 0x01);
 218 }
 219
 220 static inline void
 221 set_bit(unsigned char *array, unsigned int idx, unsigned int bit) {
 222         unsigned int shift, mask;
 223
 224         shift = 7 - (idx % 8);
 225         mask = 1 << shift;
 226
 227         if (bit != 0)
 228                 array[idx / 8] |= mask;
 229         else
 230                 array[idx / 8] &= (~mask & 0xFF);
 231 }
 232
 233 dns_labeltype_t
 234 dns_label_type(dns_label_t *label) {
 235         /*
 236          * Get the type of 'label'.
 237          */
 238
 239         REQUIRE(label != NULL);
 240         REQUIRE(label->length > 0);
 241         REQUIRE(label->base[0] <= 63 ||
 242                 label->base[0] == DNS_LABELTYPE_BITSTRING);
 243
 244         if (label->base[0] <= 63)
 245                 return (dns_labeltype_ordinary);
 246         else
 247                 return (dns_labeltype_bitstring);
 248 }
 249
 250 unsigned int
 251 dns_label_countbits(dns_label_t *label) {
 252         unsigned int count;
 253
 254         /*
 255          * The number of bits in a bitstring label.
 256          */
 257
 258         REQUIRE(label != NULL);
 259         REQUIRE(label->length > 2);
 260         REQUIRE(label->base[0] == DNS_LABELTYPE_BITSTRING);
 261
 262         count = label->base[1];
 263         if (count == 0)
 264                 count = 256;
 265
 266         return (count);
 267 }
 268
 269 dns_bitlabel_t
 270 dns_label_getbit(dns_label_t *label, unsigned int n) {
 271         unsigned int count, bit;
 272
 273         /*
 274          * The 'n'th most significant bit of 'label'.
 275          *
 276          * Notes:
 277          *      Numbering starts at 0.
 278          */
 279
 280         REQUIRE(label != NULL);
 281         REQUIRE(label->length > 2);
 282         REQUIRE(label->base[0] == DNS_LABELTYPE_BITSTRING);
 283
 284         count = label->base[1];
 285         if (count == 0)
 286                 count = 256;
 287
 288         REQUIRE(n < count);
 289
 290         bit = get_bit(&label->base[2], n);
 291         if (bit == 0)
 292                 return (dns_bitlabel_0);
 293         return (dns_bitlabel_1);
 294 }
 295
 296 void
 297 dns_name_init(dns_name_t *name, unsigned char *offsets) {
 298         /*
 299          * Initialize 'name'.
 300          */
 301         DNS_NAME_INIT(name, offsets);
 302 }
 303
 304 void
 305 dns_name_reset(dns_name_t *name) {
 306         REQUIRE(VALID_NAME(name));
 307         REQUIRE(BINDABLE(name));
 308
 309         DNS_NAME_RESET(name);
 310 }
 311
 312 void
 313 dns_name_invalidate(dns_name_t *name) {
 314         /*
 315          * Make 'name' invalid.
 316          */
 317
 318         REQUIRE(VALID_NAME(name));
 319
 320         name->magic = 0;
 321         name->ndata = NULL;
 322         name->length = 0;
 323         name->labels = 0;
 324         name->attributes = 0;
 325         name->offsets = NULL;
 326         name->buffer = NULL;
 327         ISC_LINK_INIT(name, link);
 328 }
 329
 330 void
 331 dns_name_setbuffer(dns_name_t *name, isc_buffer_t *buffer) {
 332         /*
 333          * Dedicate a buffer for use with 'name'.
 334          */
 335
 336         REQUIRE(VALID_NAME(name));
 337         REQUIRE((buffer != NULL && name->buffer == NULL) ||
 338                 (buffer == NULL));
 339
 340         name->buffer = buffer;
 341 }
 342
 343 isc_boolean_t
 344 dns_name_hasbuffer(const dns_name_t *name) {
 345         /*
 346          * Does 'name' have a dedicated buffer?
 347          */
 348
 349         REQUIRE(VALID_NAME(name));
 350
 351         if (name->buffer != NULL)
 352                 return (ISC_TRUE);
 353
 354         return (ISC_FALSE);
 355 }
 356
 357 isc_boolean_t
 358 dns_name_isabsolute(const dns_name_t *name) {
 359
 360         /*
 361          * Does 'name' end in the root label?
 362          */
 363
 364         REQUIRE(VALID_NAME(name));
 365
 366         if ((name->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
 367                 return (ISC_TRUE);
 368         return (ISC_FALSE);
 369 }
 370
 371 isc_boolean_t
 372 dns_name_iswildcard(const dns_name_t *name) {
 373         unsigned char *ndata;
 374
 375         /*
 376          * Is 'name' a wildcard name?
 377          */
 378
 379         REQUIRE(VALID_NAME(name));
 380         REQUIRE(name->labels > 0);
 381
 382         if (name->length >= 2) {
 383                 ndata = name->ndata;
 384                 if (ndata[0] == 1 && ndata[1] == '*')
 385                         return (ISC_TRUE);
 386         }
 387
 388         return (ISC_FALSE);
 389 }
 390
 391 isc_boolean_t
 392 dns_name_requiresedns(const dns_name_t *name) {
 393         unsigned int count, nrem;
 394         unsigned char *ndata;
 395         isc_boolean_t requiresedns = ISC_FALSE;
 396
 397         /*
 398          * Does 'name' require EDNS for transmission?
 399          */
 400
 401         REQUIRE(VALID_NAME(name));
 402         REQUIRE(name->labels > 0);
 403
 404         ndata = name->ndata;
 405         nrem = name->length;
 406         while (nrem > 0) {
 407                 count = *ndata++;
 408                 nrem--;
 409                 if (count == 0)
 410                         break;
 411                 if (count > 63) {
 412                         INSIST(count == DNS_LABELTYPE_BITSTRING);
 413                         requiresedns = ISC_TRUE;
 414                         break;
 415                 }
 416                 INSIST(nrem >= count);
 417                 nrem -= count;
 418                 ndata += count;
 419         }
 420
 421         return (requiresedns);
 422 }
 423
 424 unsigned int
 425 dns_name_hash(dns_name_t *name, isc_boolean_t case_sensitive) {
 426         unsigned int length;
 427         const unsigned char *s;
 428         unsigned int h = 0;
 429         unsigned char c;
 430
 431         /*
 432          * Provide a hash value for 'name'.
 433          */
 434         REQUIRE(VALID_NAME(name));
 435
 436         if (name->labels == 0)
 437                 return (0);
 438         length = name->length;
 439         if (length > 16)
 440                 length = 16;
 441
 442         /*
 443          * This hash function is similar to the one Ousterhout
 444          * uses in Tcl.
 445          */
 446         s = name->ndata;
 447         if (case_sensitive) {
 448                 while (length > 0) {
 449                         h += ( h << 3 ) + *s;
 450                         s++;
 451                         length--;
 452                 }
 453         } else {
 454                 while (length > 0) {
 455                         c = maptolower[*s];
 456                         h += ( h << 3 ) + c;
 457                         s++;
 458                         length--;
 459                 }
 460         }
 461
 462         return (h);
 463 }
 464
 465 unsigned int
 466 dns_fullname_hash(dns_name_t *name, isc_boolean_t case_sensitive) {
 467         /*
 468          * Provide a hash value for 'name'.
 469          */
 470         REQUIRE(VALID_NAME(name));
 471
 472         if (name->labels == 0)
 473                 return (0);
 474
 475         return (isc_hash_calc((const unsigned char *)name->ndata,
 476                               name->length, case_sensitive));
 477 }
 478
 479 dns_namereln_t
 480 dns_name_fullcompare(const dns_name_t *name1, const dns_name_t *name2,
 481                      int *orderp,
 482                      unsigned int *nlabelsp, unsigned int *nbitsp)
 483 {
 484         unsigned int l1, l2, l, count1, count2, count;
 485         unsigned int b1, b2, n, nlabels, nbits;
 486         int cdiff, ldiff, chdiff;
 487         unsigned char *label1, *label2;
 488         unsigned char *offsets1, *offsets2;
 489         dns_offsets_t odata1, odata2;
 490         dns_namereln_t namereln = dns_namereln_none;
 491
 492         /*
 493          * Determine the relative ordering under the DNSSEC order relation of
 494          * 'name1' and 'name2', and also determine the hierarchical
 495          * relationship of the names.
 496          *
 497          * Note: It makes no sense for one of the names to be relative and the
 498          * other absolute.  If both names are relative, then to be meaningfully
 499          * compared the caller must ensure that they are both relative to the
 500          * same domain.
 501          */
 502
 503         REQUIRE(VALID_NAME(name1));
 504         REQUIRE(VALID_NAME(name2));
 505         REQUIRE(orderp != NULL);
 506         REQUIRE(nlabelsp != NULL);
 507         REQUIRE(nbitsp != NULL);
 508         /*
 509          * Either name1 is absolute and name2 is absolute, or neither is.
 510          */
 511         REQUIRE((name1->attributes & DNS_NAMEATTR_ABSOLUTE) ==
 512                 (name2->attributes & DNS_NAMEATTR_ABSOLUTE));
 513
 514         SETUP_OFFSETS(name1, offsets1, odata1);
 515         SETUP_OFFSETS(name2, offsets2, odata2);
 516
 517         nlabels = 0;
 518         nbits = 0;
 519         l1 = name1->labels;
 520         l2 = name2->labels;
 521         ldiff = (int)l1 - (int)l2;
 522         if (ldiff < 0)
 523                 l = l1;
 524         else
 525                 l = l2;
 526
 527         while (l > 0) {
 528                 l--;
 529                 l1--;
 530                 l2--;
 531                 label1 = &name1->ndata[offsets1[l1]];
 532                 label2 = &name2->ndata[offsets2[l2]];
 533                 count1 = *label1++;
 534                 count2 = *label2++;
 535                 if (count1 <= 63 && count2 <= 63) {
 536                         cdiff = (int)count1 - (int)count2;
 537                         if (cdiff < 0)
 538                                 count = count1;
 539                         else
 540                                 count = count2;
 541
 542                         while (count > 0) {
 543                                 chdiff = (int)maptolower[*label1] -
 544                                         (int)maptolower[*label2];
 545                                 if (chdiff != 0) {
 546                                         *orderp = chdiff;
 547                                         goto done;
 548                                 }
 549                                 count--;
 550                                 label1++;
 551                                 label2++;
 552                         }
 553                         if (cdiff != 0) {
 554                                 *orderp = cdiff;
 555                                 goto done;
 556                         }
 557                         nlabels++;
 558                 } else if (count1 == DNS_LABELTYPE_BITSTRING && count2 <= 63) {
 559                         if (count2 == 0)
 560                                 *orderp = 1;
 561                         else
 562                                 *orderp = -1;
 563                         goto done;
 564                 } else if (count2 == DNS_LABELTYPE_BITSTRING && count1 <= 63) {
 565                         if (count1 == 0)
 566                                 *orderp = -1;
 567                         else
 568                                 *orderp = 1;
 569                         goto done;
 570                 } else {
 571                         INSIST(count1 == DNS_LABELTYPE_BITSTRING &&
 572                                count2 == DNS_LABELTYPE_BITSTRING);
 573                         count1 = *label1++;
 574                         if (count1 == 0)
 575                                 count1 = 256;
 576                         count2 = *label2++;
 577                         if (count2 == 0)
 578                                 count2 = 256;
 579                         if (count1 < count2) {
 580                                 cdiff = -1;
 581                                 count = count1;
 582                         } else {
 583                                 count = count2;
 584                                 if (count1 > count2)
 585                                         cdiff = 1;
 586                                 else
 587                                         cdiff = 0;
 588                         }
 589                         /* Yes, this loop is really slow! */
 590                         for (n = 0; n < count; n++) {
 591                                 b1 = get_bit(label1, n);
 592                                 b2 = get_bit(label2, n);
 593                                 if (b1 < b2) {
 594                                         *orderp = -1;
 595                                         goto done;
 596                                 } else if (b1 > b2) {
 597                                         *orderp = 1;
 598                                         goto done;
 599                                 }
 600                                 if (nbits == 0)
 601                                         nlabels++;
 602                                 nbits++;
 603                         }
 604                         if (cdiff != 0) {
 605                                 /*
 606                                  * If we're here, then we have two bitstrings
 607                                  * of differing length.
 608                                  *
 609                                  * If the name with the shorter bitstring
 610                                  * has any labels, then it must be greater
 611                                  * than the longer bitstring.  This is a bit
 612                                  * counterintuitive.  If the name with the
 613                                  * shorter bitstring has any more labels, then
 614                                  * the next label must be an ordinary label.
 615                                  * It can't be a bitstring label because if it
 616                                  * were, then there would be room for it in
 617                                  * the current bitstring label (since all
 618                                  * bitstrings are canonicalized).  Since
 619                                  * there's at least one more bit in the
 620                                  * name with the longer bitstring, and since
 621                                  * a bitlabel sorts before any ordinary label,
 622                                  * the name with the longer bitstring must
 623                                  * be lexically before the one with the shorter
 624                                  * bitstring.
 625                                  *
 626                                  * On the other hand, if there are no more
 627                                  * labels in the name with the shorter
 628                                  * bitstring, then that name contains the
 629                                  * other name.
 630                                  */
 631                                 namereln = dns_namereln_commonancestor;
 632                                 if (cdiff < 0) {
 633                                         if (l1 > 0)
 634                                                 *orderp = 1;
 635                                         else {
 636                                                 *orderp = -1;
 637                                                 namereln =
 638                                                         dns_namereln_contains;
 639                                         }
 640                                 } else {
 641                                         if (l2 > 0)
 642                                                 *orderp = -1;
 643                                         else {
 644                                                 *orderp = 1;
 645                                                 namereln =
 646                                                         dns_namereln_subdomain;
 647                                         }
 648                                 }
 649                                 goto done;
 650                         }
 651                         nbits = 0;
 652                 }
 653         }
 654
 655         *orderp = ldiff;
 656         if (ldiff < 0)
 657                 namereln = dns_namereln_contains;
 658         else if (ldiff > 0)
 659                 namereln = dns_namereln_subdomain;
 660         else
 661                 namereln = dns_namereln_equal;
 662
 663  done:
 664         *nlabelsp = nlabels;
 665         *nbitsp = nbits;
 666
 667         if (nlabels > 0 && namereln == dns_namereln_none)
 668                 namereln = dns_namereln_commonancestor;
 669
 670         return (namereln);
 671 }
 672
 673 int
 674 dns_name_compare(const dns_name_t *name1, const dns_name_t *name2) {
 675         int order;
 676         unsigned int nlabels, nbits;
 677
 678         /*
 679          * Determine the relative ordering under the DNSSEC order relation of
 680          * 'name1' and 'name2'.
 681          *
 682          * Note: It makes no sense for one of the names to be relative and the
 683          * other absolute.  If both names are relative, then to be meaningfully
 684          * compared the caller must ensure that they are both relative to the
 685          * same domain.
 686          */
 687
 688         (void)dns_name_fullcompare(name1, name2, &order, &nlabels, &nbits);
 689
 690         return (order);
 691 }
 692
 693 isc_boolean_t
 694 dns_name_equal(const dns_name_t *name1, const dns_name_t *name2) {
 695         unsigned int l, count;
 696         unsigned char c;
 697         unsigned char *label1, *label2;
 698
 699         /*
 700          * Are 'name1' and 'name2' equal?
 701          *
 702          * Note: It makes no sense for one of the names to be relative and the
 703          * other absolute.  If both names are relative, then to be meaningfully
 704          * compared the caller must ensure that they are both relative to the
 705          * same domain.
 706          */
 707
 708         REQUIRE(VALID_NAME(name1));
 709         REQUIRE(VALID_NAME(name2));
 710         /*
 711          * Either name1 is absolute and name2 is absolute, or neither is.
 712          */
 713         REQUIRE((name1->attributes & DNS_NAMEATTR_ABSOLUTE) ==
 714                 (name2->attributes & DNS_NAMEATTR_ABSOLUTE));
 715
 716         if (name1->length != name2->length)
 717                 return (ISC_FALSE);
 718
 719         l = name1->labels;
 720
 721         if (l != name2->labels)
 722                 return (ISC_FALSE);
 723
 724         label1 = name1->ndata;
 725         label2 = name2->ndata;
 726         while (l > 0) {
 727                 l--;
 728                 count = *label1++;
 729                 if (count != *label2++)
 730                         return (ISC_FALSE);
 731                 if (count <= 63) {
 732                         while (count > 0) {
 733                                 count--;
 734                                 c = maptolower[*label1++];
 735                                 if (c != maptolower[*label2++])
 736                                         return (ISC_FALSE);
 737                         }
 738                 } else {
 739                         INSIST(count == DNS_LABELTYPE_BITSTRING);
 740                         count = *label1++;
 741                         if (count != *label2++)
 742                                 return (ISC_FALSE);
 743                         if (count == 0)
 744                                 count = 256;
 745                         /*
 746                          * Number of bytes.
 747                          */
 748                         count = (count + 7) / 8;
 749                         while (count > 0) {
 750                                 count--;
 751                                 c = *label1++;
 752                                 if (c != *label2++)
 753                                         return (ISC_FALSE);
 754                         }
 755                 }
 756         }
 757
 758         return (ISC_TRUE);
 759 }
 760
 761 int
 762 dns_name_rdatacompare(const dns_name_t *name1, const dns_name_t *name2) {
 763         unsigned int l1, l2, l, count1, count2, count;
 764         unsigned char c1, c2;
 765         unsigned char *label1, *label2;
 766
 767         /*
 768          * Compare two absolute names as rdata.
 769          */
 770
 771         REQUIRE(VALID_NAME(name1));
 772         REQUIRE(name1->labels > 0);
 773         REQUIRE((name1->attributes & DNS_NAMEATTR_ABSOLUTE) != 0);
 774         REQUIRE(VALID_NAME(name2));
 775         REQUIRE(name2->labels > 0);
 776         REQUIRE((name2->attributes & DNS_NAMEATTR_ABSOLUTE) != 0);
 777
 778         l1 = name1->labels;
 779         l2 = name2->labels;
 780
 781         l = (l1 < l2) ? l1 : l2;
 782
 783         label1 = name1->ndata;
 784         label2 = name2->ndata;
 785         while (l > 0) {
 786                 l--;
 787                 count1 = *label1++;
 788                 count2 = *label2++;
 789                 if (count1 <= 63 && count2 <= 63) {
 790                         if (count1 != count2)
 791                                 return ((count1 < count2) ? -1 : 1);
 792                         count = count1;
 793                         while (count > 0) {
 794                                 count--;
 795                                 c1 = maptolower[*label1++];
 796                                 c2 = maptolower[*label2++];
 797                                 if (c1 < c2)
 798                                         return (-1);
 799                                 else if (c1 > c2)
 800                                         return (1);
 801                         }
 802                 } else if (count1 == DNS_LABELTYPE_BITSTRING && count2 <= 63) {
 803                         return (1);
 804                 } else if (count2 == DNS_LABELTYPE_BITSTRING && count1 <= 63) {
 805                         return (-1);
 806                 } else {
 807                         INSIST(count1 == DNS_LABELTYPE_BITSTRING &&
 808                                count2 == DNS_LABELTYPE_BITSTRING);
 809                         count2 = *label2++;
 810                         count1 = *label1++;
 811                         if (count1 != count2)
 812                                 return ((count1 < count2) ? -1 : 1);
 813                         if (count1 == 0)
 814                                 count1 = 256;
 815                         if (count2 == 0)
 816                                 count2 = 256;
 817                         /* number of bytes */
 818                         count = (count1 + 7) / 8;
 819                         while (count > 0) {
 820                                 count--;
 821                                 c1 = *label1++;
 822                                 c2 = *label2++;
 823                                 if (c1 != c2)
 824                                         return ((c1 < c2) ? -1 : 1);
 825                         }
 826                 }
 827         }
 828
 829         /*
 830          * If one name had more labels than the other, their common
 831          * prefix must have been different because the shorter name
 832          * ended with the root label and the longer one can't have
 833          * a root label in the middle of it.  Therefore, if we get
 834          * to this point, the lengths must be equal.
 835          */
 836         INSIST(l1 == l2);
 837
 838         return (0);
 839 }
 840
 841 isc_boolean_t
 842 dns_name_issubdomain(const dns_name_t *name1, const dns_name_t *name2) {
 843         int order;
 844         unsigned int nlabels, nbits;
 845         dns_namereln_t namereln;
 846
 847         /*
 848          * Is 'name1' a subdomain of 'name2'?
 849          *
 850          * Note: It makes no sense for one of the names to be relative and the
 851          * other absolute.  If both names are relative, then to be meaningfully
 852          * compared the caller must ensure that they are both relative to the
 853          * same domain.
 854          */
 855
 856         namereln = dns_name_fullcompare(name1, name2, &order, &nlabels,
 857                                         &nbits);
 858         if (namereln == dns_namereln_subdomain ||
 859             namereln == dns_namereln_equal)
 860                 return (ISC_TRUE);
 861
 862         return (ISC_FALSE);
 863 }
 864
 865 isc_boolean_t
 866 dns_name_matcheswildcard(const dns_name_t *name, const dns_name_t *wname) {
 867         int order;
 868         unsigned int nlabels, nbits, labels;
 869         dns_name_t tname;
 870
 871         REQUIRE(VALID_NAME(name));
 872         REQUIRE(name->labels > 0);
 873         REQUIRE(VALID_NAME(wname));
 874         labels = wname->labels;
 875         REQUIRE(labels > 0);
 876         REQUIRE(dns_name_iswildcard(wname));
 877
 878         DNS_NAME_INIT(&tname, NULL);
 879         dns_name_getlabelsequence(wname, 1, labels - 1, &tname);
 880         if (dns_name_fullcompare(name, &tname, &order, &nlabels, &nbits) ==
 881             dns_namereln_subdomain)
 882                 return (ISC_TRUE);
 883         return (ISC_FALSE);
 884 }
 885
 886 unsigned int
 887 dns_name_depth(const dns_name_t *name) {
 888         unsigned int depth, count, nrem, n;
 889         unsigned char *ndata;
 890
 891         /*
 892          * The depth of 'name'.
 893          */
 894
 895         REQUIRE(VALID_NAME(name));
 896
 897         if (name->labels == 0)
 898                 return (0);
 899
 900         depth = 0;
 901         ndata = name->ndata;
 902         nrem = name->length;
 903         while (nrem > 0) {
 904                 count = *ndata++;
 905                 nrem--;
 906                 if (count > 63) {
 907                         INSIST(count == DNS_LABELTYPE_BITSTRING);
 908                         INSIST(nrem != 0);
 909                         n = *ndata++;
 910                         nrem--;
 911                         if (n == 0)
 912                                 n = 256;
 913                         depth += n;
 914                         count = n / 8;
 915                         if (n % 8 != 0)
 916                                 count++;
 917                 } else {
 918                         depth++;
 919                         if (count == 0)
 920                                 break;
 921                 }
 922                 INSIST(nrem >= count);
 923                 nrem -= count;
 924                 ndata += count;
 925         }
 926
 927         return (depth);
 928 }
 929
 930 unsigned int
 931 dns_name_countlabels(const dns_name_t *name) {
 932         /*
 933          * How many labels does 'name' have?
 934          */
 935
 936         REQUIRE(VALID_NAME(name));
 937
 938         ENSURE(name->labels <= 128);
 939
 940         return (name->labels);
 941 }
 942
 943 void
 944 dns_name_getlabel(const dns_name_t *name, unsigned int n, dns_label_t *label) {
 945         unsigned char *offsets;
 946         dns_offsets_t odata;
 947
 948         /*
 949          * Make 'label' refer to the 'n'th least significant label of 'name'.
 950          */
 951
 952         REQUIRE(VALID_NAME(name));
 953         REQUIRE(name->labels > 0);
 954         REQUIRE(n < name->labels);
 955         REQUIRE(label != NULL);
 956
 957         SETUP_OFFSETS(name, offsets, odata);
 958
 959         label->base = &name->ndata[offsets[n]];
 960         if (n == name->labels - 1)
 961                 label->length = name->length - offsets[n];
 962         else
 963                 label->length = offsets[n + 1] - offsets[n];
 964 }
 965
 966 void
 967 dns_name_getlabelsequence(const dns_name_t *source,
 968                           unsigned int first, unsigned int n,
 969                           dns_name_t *target)
 970 {
 971         unsigned char *offsets;
 972         dns_offsets_t odata;
 973         unsigned int firstoffset, endoffset;
 974
 975         /*
 976          * Make 'target' refer to the 'n' labels including and following
 977          * 'first' in 'source'.
 978          */
 979
 980         REQUIRE(VALID_NAME(source));
 981         REQUIRE(VALID_NAME(target));
 982         REQUIRE(first <= source->labels);
 983         REQUIRE(first + n <= source->labels);
 984         REQUIRE(BINDABLE(target));
 985
 986         SETUP_OFFSETS(source, offsets, odata);
 987
 988         if (first == source->labels)
 989                 firstoffset = source->length;
 990         else
 991                 firstoffset = offsets[first];
 992
 993         if (first + n == source->labels)
 994                 endoffset = source->length;
 995         else
 996                 endoffset = offsets[first + n];
 997
 998         target->ndata = &source->ndata[firstoffset];
 999         target->length = endoffset - firstoffset;
1000
1001         if (first + n == source->labels && n > 0 &&
1002             (source->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
1003                 target->attributes |= DNS_NAMEATTR_ABSOLUTE;
1004         else
1005                 target->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
1006
1007         target->labels = n;
1008
1009         /*
1010          * If source and target are the same, and we're making target
1011          * a prefix of source, the offsets table is correct already
1012          * so we don't need to call set_offsets().
1013          */
1014         if (target->offsets != NULL &&
1015             (target != source || first != 0))
1016                 set_offsets(target, target->offsets, NULL);
1017 }
1018
1019 void
1020 dns_name_clone(dns_name_t *source, dns_name_t *target) {
1021
1022         /*
1023          * Make 'target' refer to the same name as 'source'.
1024          */
1025
1026         REQUIRE(VALID_NAME(source));
1027         REQUIRE(VALID_NAME(target));
1028         REQUIRE(BINDABLE(target));
1029
1030         target->ndata = source->ndata;
1031         target->length = source->length;
1032         target->labels = source->labels;
1033         target->attributes = source->attributes &
1034                 (unsigned int)~(DNS_NAMEATTR_READONLY | DNS_NAMEATTR_DYNAMIC |
1035                                 DNS_NAMEATTR_DYNOFFSETS);
1036         if (target->offsets != NULL && source->labels > 0) {
1037                 if (source->offsets != NULL)
1038                         memcpy(target->offsets, source->offsets,
1039                                source->labels);
1040                 else
1041                         set_offsets(target, target->offsets, NULL);
1042         }
1043 }
1044
1045 void
1046 dns_name_fromregion(dns_name_t *name, isc_region_t *r) {
1047         unsigned char *offsets;
1048         dns_offsets_t odata;
1049         unsigned int len;
1050         isc_region_t r2;
1051
1052         /*
1053          * Make 'name' refer to region 'r'.
1054          */
1055
1056         REQUIRE(VALID_NAME(name));
1057         REQUIRE(r != NULL);
1058         REQUIRE(BINDABLE(name));
1059
1060         INIT_OFFSETS(name, offsets, odata);
1061
1062         if (name->buffer != NULL) {
1063                 isc_buffer_clear(name->buffer);
1064                 isc_buffer_availableregion(name->buffer, &r2);
1065                 len = (r->length < r2.length) ? r->length : r2.length;
1066                 if (len > DNS_NAME_MAXWIRE)
1067                         len = DNS_NAME_MAXWIRE;
1068                 memcpy(r2.base, r->base, len);
1069                 name->ndata = r2.base;
1070                 name->length = len;
1071         } else {
1072                 name->ndata = r->base;
1073                 name->length = (r->length <= DNS_NAME_MAXWIRE) ?
1074                         r->length : DNS_NAME_MAXWIRE;
1075         }
1076
1077         if (r->length > 0)
1078                 set_offsets(name, offsets, name);
1079         else {
1080                 name->labels = 0;
1081                 name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
1082         }
1083
1084         if (name->buffer != NULL)
1085                 isc_buffer_add(name->buffer, name->length);
1086 }
1087
1088 void
1089 dns_name_toregion(dns_name_t *name, isc_region_t *r) {
1090         /*
1091          * Make 'r' refer to 'name'.
1092          */
1093
1094         REQUIRE(VALID_NAME(name));
1095         REQUIRE(r != NULL);
1096
1097         DNS_NAME_TOREGION(name, r);
1098 }
1099
1100
1101 isc_result_t
1102 dns_name_fromtext(dns_name_t *name, isc_buffer_t *source,
1103                   dns_name_t *origin, isc_boolean_t downcase,
1104                   isc_buffer_t *target)
1105 {
1106         unsigned char *ndata, *label;
1107         char *tdata;
1108         char c;
1109         ft_state state, kind;
1110         unsigned int value, count, tbcount, bitlength, maxlength;
1111         unsigned int n1, n2, vlen, tlen, nrem, nused, digits, labels, tused;
1112         isc_boolean_t done, saw_bitstring;
1113         unsigned char dqchars[4];
1114         unsigned char *offsets;
1115         dns_offsets_t odata;
1116
1117         /*
1118          * Convert the textual representation of a DNS name at source
1119          * into uncompressed wire form stored in target.
1120          *
1121          * Notes:
1122          *      Relative domain names will have 'origin' appended to them
1123          *      unless 'origin' is NULL, in which case relative domain names
1124          *      will remain relative.
1125          */
1126
1127         REQUIRE(VALID_NAME(name));
1128         REQUIRE(ISC_BUFFER_VALID(source));
1129         REQUIRE((target != NULL && ISC_BUFFER_VALID(target)) ||
1130                 (target == NULL && ISC_BUFFER_VALID(name->buffer)));
1131
1132         if (target == NULL && name->buffer != NULL) {
1133                 target = name->buffer;
1134                 isc_buffer_clear(target);
1135         }
1136
1137         REQUIRE(BINDABLE(name));
1138
1139         INIT_OFFSETS(name, offsets, odata);
1140         offsets[0] = 0;
1141
1142         /*
1143          * Initialize things to make the compiler happy; they're not required.
1144          */
1145         n1 = 0;
1146         n2 = 0;
1147         vlen = 0;
1148         label = NULL;
1149         digits = 0;
1150         value = 0;
1151         count = 0;
1152         tbcount = 0;
1153         bitlength = 0;
1154         maxlength = 0;
1155         kind = ft_init;
1156
1157         /*
1158          * Make 'name' empty in case of failure.
1159          */
1160         MAKE_EMPTY(name);
1161
1162         /*
1163          * Set up the state machine.
1164          */
1165         tdata = (char *)source->base + source->current;
1166         tlen = isc_buffer_remaininglength(source);
1167         tused = 0;
1168         ndata = isc_buffer_used(target);
1169         nrem = isc_buffer_availablelength(target);
1170         if (nrem > 255)
1171                 nrem = 255;
1172         nused = 0;
1173         labels = 0;
1174         done = ISC_FALSE;
1175         saw_bitstring = ISC_FALSE;
1176         state = ft_init;
1177
1178         while (nrem > 0 && tlen > 0 && !done) {
1179                 c = *tdata++;
1180                 tlen--;
1181                 tused++;
1182
1183         no_read:
1184                 switch (state) {
1185                 case ft_init:
1186                         /*
1187                          * Is this the root name?
1188                          */
1189                         if (c == '.') {
1190                                 if (tlen != 0)
1191                                         return (DNS_R_EMPTYLABEL);
1192                                 labels++;
1193                                 *ndata++ = 0;
1194                                 nrem--;
1195                                 nused++;
1196                                 done = ISC_TRUE;
1197                                 break;
1198                         }
1199                         if (c == '@' && tlen == 0) {
1200                                 state = ft_at;
1201                                 break;
1202                         }
1203
1204                         /* FALLTHROUGH */
1205                 case ft_start:
1206                         label = ndata;
1207                         ndata++;
1208                         nrem--;
1209                         nused++;
1210                         count = 0;
1211                         if (c == '\\') {
1212                                 state = ft_initialescape;
1213                                 break;
1214                         }
1215                         kind = ft_ordinary;
1216                         state = ft_ordinary;
1217                         if (nrem == 0)
1218                                 return (ISC_R_NOSPACE);
1219                         /* FALLTHROUGH */
1220                 case ft_ordinary:
1221                         if (c == '.') {
1222                                 if (count == 0)
1223                                         return (DNS_R_EMPTYLABEL);
1224                                 *label = count;
1225                                 labels++;
1226                                 INSIST(labels <= 127);
1227                                 offsets[labels] = nused;
1228                                 if (tlen == 0) {
1229                                         labels++;
1230                                         *ndata++ = 0;
1231                                         nrem--;
1232                                         nused++;
1233                                         done = ISC_TRUE;
1234                                 }
1235                                 state = ft_start;
1236                         } else if (c == '\\') {
1237                                 state = ft_escape;
1238                         } else {
1239                                 if (count >= 63)
1240                                         return (DNS_R_LABELTOOLONG);
1241                                 count++;
1242                                 CONVERTTOASCII(c);
1243                                 if (downcase)
1244                                         c = maptolower[(int)c];
1245                                 *ndata++ = c;
1246                                 nrem--;
1247                                 nused++;
1248                         }
1249                         break;
1250                 case ft_initialescape:
1251                         if (c == '[') {
1252                                 saw_bitstring = ISC_TRUE;
1253                                 kind = ft_bitstring;
1254                                 state = ft_bitstring;
1255                                 *label = DNS_LABELTYPE_BITSTRING;
1256                                 label = ndata;
1257                                 ndata++;
1258                                 nrem--;
1259                                 nused++;
1260                                 break;
1261                         }
1262                         kind = ft_ordinary;
1263                         state = ft_escape;
1264                         /* FALLTHROUGH */
1265                 case ft_escape:
1266                         if (!isdigit(c & 0xff)) {
1267                                 if (count >= 63)
1268                                         return (DNS_R_LABELTOOLONG);
1269                                 count++;
1270                                 CONVERTTOASCII(c);
1271                                 if (downcase)
1272                                         c = maptolower[(int)c];
1273                                 *ndata++ = c;
1274                                 nrem--;
1275                                 nused++;
1276                                 state = ft_ordinary;
1277                                 break;
1278                         }
1279                         digits = 0;
1280                         value = 0;
1281                         state = ft_escdecimal;
1282                         /* FALLTHROUGH */
1283                 case ft_escdecimal:
1284                         if (!isdigit(c & 0xff))
1285                                 return (DNS_R_BADESCAPE);
1286                         value *= 10;
1287                         value += digitvalue[(int)c];
1288                         digits++;
1289                         if (digits == 3) {
1290                                 if (value > 255)
1291                                         return (DNS_R_BADESCAPE);
1292                                 if (count >= 63)
1293                                         return (DNS_R_LABELTOOLONG);
1294                                 count++;
1295                                 if (downcase)
1296                                         value = maptolower[value];
1297                                 *ndata++ = value;
1298                                 nrem--;
1299                                 nused++;
1300                                 state = ft_ordinary;
1301                         }
1302                         break;
1303                 case ft_bitstring:
1304                         /* count is zero */
1305                         tbcount = 0;
1306                         value = 0;
1307                         if (c == 'b') {
1308                                 vlen = 8;
1309                                 maxlength = 256;
1310                                 kind = ft_binary;
1311                                 state = ft_binary;
1312                         } else if (c == 'o') {
1313                                 vlen = 8;
1314                                 maxlength = 256;
1315                                 kind = ft_octal;
1316                                 state = ft_octal;
1317                         } else if (c == 'x') {
1318                                 vlen = 8;
1319                                 maxlength = 256;
1320                                 kind = ft_hex;
1321                                 state = ft_hex;
1322                         } else if (isdigit(c & 0xff)) {
1323                                 vlen = 32;
1324                                 maxlength = 32;
1325                                 n1 = 0;
1326                                 n2 = 0;
1327                                 digits = 0;
1328                                 kind = ft_dottedquad;
1329                                 state = ft_dqdecimal;
1330                                 goto no_read;
1331                         } else
1332                                 return (DNS_R_BADBITSTRING);
1333                         break;
1334                 case ft_binary:
1335                         if (c != '0' && c != '1') {
1336                                 state = ft_maybeslash;
1337                                 goto no_read;
1338                         }
1339                         value <<= 1;
1340                         if (c == '1')
1341                                 value |= 1;
1342                         count++;
1343                         tbcount++;
1344                         if (tbcount > 256)
1345                                 return (DNS_R_BITSTRINGTOOLONG);
1346                         if (count == 8) {
1347                                 *ndata++ = value;
1348                                 nrem--;
1349                                 nused++;
1350                                 count = 0;
1351                         }
1352                         break;
1353                 case ft_octal:
1354                         if (!isdigit(c & 0xff) || c == '9' || c == '8') {
1355                                 state = ft_maybeslash;
1356                                 goto no_read;
1357                         }
1358                         value <<= 3;
1359                         value += digitvalue[(int)c];
1360                         count += 3;
1361                         tbcount += 3;
1362                         /*
1363                          * The total bit count is tested against 258 instead
1364                          * of 256 because of the possibility that the bitstring
1365                          * label is exactly 256 bits long; on the last octal
1366                          * digit (which must be 4) tbcount is incremented
1367                          * from 255 to 258.  This case is adequately handled
1368                          * later.
1369                          */
1370                         if (tbcount > 258)
1371                                 return (DNS_R_BITSTRINGTOOLONG);
1372                         if (count == 8) {
1373                                 *ndata++ = value;
1374                                 nrem--;
1375                                 nused++;
1376                                 count = 0;
1377                         } else if (count == 9) {
1378                                 *ndata++ = (value >> 1);
1379                                 nrem--;
1380                                 nused++;
1381                                 value &= 1;
1382                                 count = 1;
1383                         } else if (count == 10) {
1384                                 *ndata++ = (value >> 2);
1385                                 nrem--;
1386                                 nused++;
1387                                 value &= 3;
1388                                 count = 2;
1389                         }
1390                         break;
1391                 case ft_hex:
1392                         if (!isxdigit(c & 0xff)) {
1393                                 state = ft_maybeslash;
1394                                 goto no_read;
1395                         }
1396                         value <<= 4;
1397                         value += digitvalue[(int)c];
1398                         count += 4;
1399                         tbcount += 4;
1400                         if (tbcount > 256)
1401                                 return (DNS_R_BITSTRINGTOOLONG);
1402                         if (count == 8) {
1403                                 *ndata++ = value;
1404                                 nrem--;
1405                                 nused++;
1406                                 count = 0;
1407                         }
1408                         break;
1409                 case ft_dottedquad:
1410                         if (c != '.' && n1 < 3)
1411                                 return (DNS_R_BADDOTTEDQUAD);
1412                         dqchars[n1] = value;
1413                         n2 *= 256;
1414                         n2 += value;
1415                         n1++;
1416                         if (n1 == 4) {
1417                                 tbcount = 32;
1418                                 value = n2;
1419                                 state = ft_maybeslash;
1420                                 goto no_read;
1421                         }
1422                         value = 0;
1423                         digits = 0;
1424                         state = ft_dqdecimal;
1425                         break;
1426                 case ft_dqdecimal:
1427                         if (!isdigit(c & 0xff)) {
1428                                 if (digits == 0 || value > 255)
1429                                         return (DNS_R_BADDOTTEDQUAD);
1430                                 state = ft_dottedquad;
1431                                 goto no_read;
1432                         }
1433                         digits++;
1434                         if (digits > 3)
1435                                 return (DNS_R_BADDOTTEDQUAD);
1436                         value *= 10;
1437                         value += digitvalue[(int)c];
1438                         break;
1439                 case ft_maybeslash:
1440                         bitlength = 0;
1441                         if (c == '/') {
1442                                 state = ft_bitlength;
1443                                 break;
1444                         }
1445                         /* FALLTHROUGH */
1446                 case ft_finishbitstring:
1447                         if (c == ']') {
1448                                 if (tbcount == 0)
1449                                         return (DNS_R_BADBITSTRING);
1450
1451                                 if (count > 0) {
1452                                         n1 = count % 8;
1453                                         if (n1 != 0)
1454                                                 value <<= (8 - n1);
1455                                 }
1456
1457                                 if (bitlength != 0) {
1458                                         if (bitlength > tbcount)
1459                                                 return (DNS_R_BADBITSTRING);
1460                                         if (kind == ft_binary &&
1461                                             bitlength != tbcount) {
1462                                                 return (DNS_R_BADBITSTRING);
1463                                         } else if (kind == ft_octal) {
1464                                                 /*
1465                                                  * Figure out correct number
1466                                                  * of octal digits for the
1467                                                  * bitlength, and compare to
1468                                                  * what was given.
1469                                                  */
1470                                                 n1 = bitlength / 3;
1471                                                 if (bitlength % 3 != 0)
1472                                                         n1++;
1473                                                 n2 = tbcount / 3;
1474                                                 /* tbcount % 3 == 0 */
1475                                                 if (n1 != n2)
1476                                                   return (DNS_R_BADBITSTRING);
1477
1478                                                 /*
1479                                                  * Check that no bits extend
1480                                                  * past the end of the last
1481                                                  * byte that is included in
1482                                                  * the bitlength.  Example:
1483                                                  * \[o036/8] == \[b00001111],
1484                                                  * which fits into just one
1485                                                  * byte, but the three octal
1486                                                  * digits actually specified
1487                                                  * two bytes worth of data,
1488                                                  * 9 bits, before the bitlength
1489                                                  * limited it back to one byte.
1490                                                  *
1491                                                  * n1 is the number of bytes
1492                                                  * necessary for the bitlength.
1493                                                  * n2 is the number of bytes
1494                                                  * encompassed by the octal
1495                                                  * digits.  If they are not
1496                                                  * equal, then "value" holds
1497                                                  * the excess bits, which
1498                                                  * must be zero.  If the bits
1499                                                  * are zero, then "count" is
1500                                                  * zero'ed to prevent the
1501                                                  * addition of another byte
1502                                                  * below.
1503                                                  */
1504                                                 n1 = (bitlength - 1) / 8;
1505                                                 n2 = (tbcount - 1) / 8;
1506                                                 if (n1 != n2) {
1507                                                     if (value != 0)
1508                                                        return
1509                                                           (DNS_R_BADBITSTRING);
1510                                                     else
1511                                                        count = 0;
1512                                                 }
1513                                         } else if (kind == ft_hex) {
1514                                                 /*
1515                                                  * Figure out correct number
1516                                                  * of hex digits for the
1517                                                  * bitlength, and compare to
1518                                                  * what was given.
1519                                                  */
1520                                                 n1 = bitlength / 4;
1521                                                 if (bitlength % 4 != 0)
1522                                                         n1++;
1523                                                 n2 = tbcount / 4;
1524                                                 /* tbcount % 4 == 0 */
1525                                                 if (n1 != n2)
1526                                                   return (DNS_R_BADBITSTRING);
1527                                         }
1528                                         n1 = bitlength % vlen;
1529                                         if (n1 != 0) {
1530                                                 /*
1531                                                  * Are the pad bits in the
1532                                                  * last 'vlen' bits zero?
1533                                                  */
1534                                                 if ((value &
1535                                                     ~((~0) << (vlen-n1))) != 0)
1536                                                   return (DNS_R_BADBITSTRING);
1537                                         }
1538                                 } else if (kind == ft_dottedquad)
1539                                         bitlength = 32;
1540                                 else if (tbcount > 256)
1541                                         /*
1542                                          * This can happen when an octal
1543                                          * bitstring label of 86 octal digits
1544                                          * is specified; tbcount will be 258.
1545                                          * This is not trapped above because
1546                                          * the bitstring label might be limited
1547                                          * by a "/256" modifier.
1548                                          */
1549                                         return (DNS_R_BADBITSTRING);
1550                                 else
1551                                         bitlength = tbcount;
1552
1553                                 if (count > 0) {
1554                                         *ndata++ = value;
1555                                         nrem--;
1556                                         nused++;
1557                                 }
1558
1559                                 if (kind == ft_dottedquad) {
1560                                         n1 = bitlength / 8;
1561                                         if (bitlength % 8 != 0)
1562                                                 n1++;
1563                                         if (nrem < n1)
1564                                                 return (ISC_R_NOSPACE);
1565                                         for (n2 = 0; n2 < n1; n2++) {
1566                                                 *ndata++ = dqchars[n2];
1567                                                 nrem--;
1568                                                 nused++;
1569                                         }
1570                                 }
1571                                 if (bitlength == 256)
1572                                         *label = 0;
1573                                 else
1574                                         *label = bitlength;
1575                                 labels++;
1576                                 INSIST(labels <= 127);
1577                                 offsets[labels] = nused;
1578                         } else
1579                                 return (DNS_R_BADBITSTRING);
1580                         state = ft_eatdot;
1581                         break;
1582                 case ft_bitlength:
1583                         if (!isdigit(c & 0xff)) {
1584                                 if (bitlength == 0)
1585                                         return (DNS_R_BADBITSTRING);
1586                                 state = ft_finishbitstring;
1587                                 goto no_read;
1588                         }
1589                         bitlength *= 10;
1590                         bitlength += digitvalue[(int)c];
1591                         if (bitlength > maxlength)
1592                                 return (DNS_R_BADBITSTRING);
1593                         break;
1594                 case ft_eatdot:
1595                         if (c != '.')
1596                                 return (DNS_R_BADBITSTRING);
1597                         if (tlen == 0) {
1598                                 labels++;
1599                                 *ndata++ = 0;
1600                                 nrem--;
1601                                 nused++;
1602                                 done = ISC_TRUE;
1603                         }
1604                         state = ft_start;
1605                         break;
1606                 default:
1607                         FATAL_ERROR(__FILE__, __LINE__,
1608                                     "Unexpected state %d", state);
1609                         /* Does not return. */
1610                 }
1611         }
1612
1613         if (!done) {
1614                 if (nrem == 0)
1615                         return (ISC_R_NOSPACE);
1616                 INSIST(tlen == 0);
1617                 if (state != ft_ordinary && state != ft_eatdot &&
1618                     state != ft_at)
1619                         return (ISC_R_UNEXPECTEDEND);
1620                 if (state == ft_ordinary) {
1621                         INSIST(count != 0);
1622                         *label = count;
1623                         labels++;
1624                         INSIST(labels <= 127);
1625                         offsets[labels] = nused;
1626                 }
1627                 if (origin != NULL) {
1628                         if (nrem < origin->length)
1629                                 return (ISC_R_NOSPACE);
1630                         label = origin->ndata;
1631                         n1 = origin->length;
1632                         nrem -= n1;
1633                         while (n1 > 0) {
1634                                 n2 = *label++;
1635                                 if (n2 <= 63) {
1636                                         *ndata++ = n2;
1637                                         n1 -= n2 + 1;
1638                                         nused += n2 + 1;
1639                                         while (n2 > 0) {
1640                                                 c = *label++;
1641                                                 if (downcase)
1642                                                         c = maptolower[(int)c];
1643                                                 *ndata++ = c;
1644                                                 n2--;
1645                                         }
1646                                 } else {
1647                                         INSIST(n2 == DNS_LABELTYPE_BITSTRING);
1648                                         *ndata++ = n2;
1649                                         bitlength = *label++;
1650                                         *ndata++ = bitlength;
1651                                         if (bitlength == 0)
1652                                                 bitlength = 256;
1653                                         n2 = bitlength / 8;
1654                                         if (bitlength % 8 != 0)
1655                                                 n2++;
1656                                         n1 -= n2 + 2;
1657                                         nused += n2 + 2;
1658                                         while (n2 > 0) {
1659                                                 *ndata++ = *label++;
1660                                                 n2--;
1661                                         }
1662                                 }
1663                                 labels++;
1664                                 if (n1 > 0) {
1665                                         INSIST(labels <= 127);
1666                                         offsets[labels] = nused;
1667                                 }
1668                         }
1669                         if ((origin->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
1670                                 name->attributes |= DNS_NAMEATTR_ABSOLUTE;
1671                 }
1672         } else
1673                 name->attributes |= DNS_NAMEATTR_ABSOLUTE;
1674
1675         name->ndata = (unsigned char *)target->base + target->used;
1676         name->labels = labels;
1677         name->length = nused;
1678
1679         if (saw_bitstring)
1680                 compact(name, offsets);
1681
1682         isc_buffer_forward(source, tused);
1683         isc_buffer_add(target, name->length);
1684
1685         return (ISC_R_SUCCESS);
1686 }
1687
1688 isc_result_t
1689 dns_name_totext(dns_name_t *name, isc_boolean_t omit_final_dot,
1690                 isc_buffer_t *target)
1691 {
1692         unsigned char *ndata;
1693         char *tdata;
1694         unsigned int nlen, tlen;
1695         unsigned char c;
1696         unsigned int trem, count;
1697         unsigned int bytes, nibbles;
1698         size_t i, len;
1699         unsigned int labels;
1700         isc_boolean_t saw_root = ISC_FALSE;
1701         char num[4];
1702
1703         /*
1704          * This function assumes the name is in proper uncompressed
1705          * wire format.
1706          */
1707         REQUIRE(VALID_NAME(name));
1708         REQUIRE(ISC_BUFFER_VALID(target));
1709
1710         ndata = name->ndata;
1711         nlen = name->length;
1712         labels = name->labels;
1713         tdata = isc_buffer_used(target);
1714         tlen = isc_buffer_availablelength(target);
1715
1716         trem = tlen;
1717
1718         if (labels == 0 && nlen == 0) {
1719                 /*
1720                  * Special handling for an empty name.
1721                  */
1722                 if (trem == 0)
1723                         return (ISC_R_NOSPACE);
1724
1725                 /*
1726                  * The names of these booleans are misleading in this case.
1727                  * This empty name is not necessarily from the root node of
1728                  * the DNS root zone, nor is a final dot going to be included.
1729                  * They need to be set this way, though, to keep the "@"
1730                  * from being trounced.
1731                  */
1732                 saw_root = ISC_TRUE;
1733                 omit_final_dot = ISC_FALSE;
1734                 *tdata++ = '@';
1735                 trem--;
1736
1737                 /*
1738                  * Skip the while() loop.
1739                  */
1740                 nlen = 0;
1741         } else if (nlen == 1 && labels == 1 && *ndata == '\0') {
1742                 /*
1743                  * Special handling for the root label.
1744                  */
1745                 if (trem == 0)
1746                         return (ISC_R_NOSPACE);
1747
1748                 saw_root = ISC_TRUE;
1749                 omit_final_dot = ISC_FALSE;
1750                 *tdata++ = '.';
1751                 trem--;
1752
1753                 /*
1754                  * Skip the while() loop.
1755                  */
1756                 nlen = 0;
1757         }
1758
1759         while (labels > 0 && nlen > 0 && trem > 0) {
1760                 labels--;
1761                 count = *ndata++;
1762                 nlen--;
1763                 if (count == 0) {
1764                         saw_root = ISC_TRUE;
1765                         break;
1766                 }
1767                 if (count < 64) {
1768                         INSIST(nlen >= count);
1769                         while (count > 0) {
1770                                 c = *ndata;
1771                                 switch (c) {
1772                                 case 0x22: /* '"' */
1773                                 case 0x28: /* '(' */
1774                                 case 0x29: /* ')' */
1775                                 case 0x2E: /* '.' */
1776                                 case 0x3B: /* ';' */
1777                                 case 0x5C: /* '\\' */
1778                                 /* Special modifiers in zone files. */
1779                                 case 0x40: /* '@' */
1780                                 case 0x24: /* '$' */
1781                                         if (trem < 2)
1782                                                 return (ISC_R_NOSPACE);
1783                                         *tdata++ = '\\';
1784                                         CONVERTFROMASCII(c);
1785                                         *tdata++ = c;
1786                                         ndata++;
1787                                         trem -= 2;
1788                                         nlen--;
1789                                         break;
1790                                 default:
1791                                         if (c > 0x20 && c < 0x7f) {
1792                                                 if (trem == 0)
1793                                                         return (ISC_R_NOSPACE);
1794                                                 CONVERTFROMASCII(c);
1795                                                 *tdata++ = c;
1796                                                 ndata++;
1797                                                 trem--;
1798                                                 nlen--;
1799                                         } else {
1800                                                 if (trem < 4)
1801                                                         return (ISC_R_NOSPACE);
1802                                                 sprintf(tdata, "\\%03u",
1803                                                         c);
1804                                                 tdata += 4;
1805                                                 trem -= 4;
1806                                                 ndata++;
1807                                                 nlen--;
1808                                         }
1809                                 }
1810                                 count--;
1811                         }
1812                 } else if (count == DNS_LABELTYPE_BITSTRING) {
1813                         if (trem < 3)
1814                                 return (ISC_R_NOSPACE);
1815                         *tdata++ = '\\';
1816                         *tdata++ = '[';
1817                         *tdata++ = 'x';
1818                         trem -= 3;
1819                         INSIST(nlen > 0);
1820                         count = *ndata++;
1821                         if (count == 0)
1822                                 count = 256;
1823                         nlen--;
1824                         len = sprintf(num, "%u", count);        /* XXX */
1825                         INSIST(len <= 4U);
1826                         bytes = count / 8;
1827                         if (count % 8 != 0)
1828                                 bytes++;
1829                         INSIST(nlen >= bytes);
1830                         nibbles = count / 4;
1831                         if (count % 4 != 0)
1832                                 nibbles++;
1833                         if (trem < nibbles)
1834                                 return (ISC_R_NOSPACE);
1835                         trem -= nibbles;
1836                         nlen -= bytes;
1837                         while (nibbles > 0) {
1838                                 c = *ndata++;
1839                                 *tdata++ = hexdigits[(c >> 4)];
1840                                 nibbles--;
1841                                 if (nibbles != 0) {
1842                                         *tdata++ = hexdigits[c & 0xf];
1843                                         nibbles--;
1844                                 }
1845                         }
1846                         if (trem < 2 + len)
1847                                 return (ISC_R_NOSPACE);
1848                         *tdata++ = '/';
1849                         for (i = 0; i < len; i++)
1850                                 *tdata++ = num[i];
1851                         *tdata++ = ']';
1852                         trem -= 2 + len;
1853                 } else {
1854                         FATAL_ERROR(__FILE__, __LINE__,
1855                                     "Unexpected label type %02x", count);
1856                         /* NOTREACHED */
1857                 }
1858
1859                 /*
1860                  * The following assumes names are absolute.  If not, we
1861                  * fix things up later.  Note that this means that in some
1862                  * cases one more byte of text buffer is required than is
1863                  * needed in the final output.
1864                  */
1865                 if (trem == 0)
1866                         return (ISC_R_NOSPACE);
1867                 *tdata++ = '.';
1868                 trem--;
1869         }
1870
1871         if (nlen != 0 && trem == 0)
1872                 return (ISC_R_NOSPACE);
1873
1874         if (!saw_root || omit_final_dot)
1875                 trem++;
1876
1877         isc_buffer_add(target, tlen - trem);
1878
1879         return (ISC_R_SUCCESS);
1880 }
1881
1882 isc_result_t
1883 dns_name_tofilenametext(dns_name_t *name, isc_boolean_t omit_final_dot,
1884                         isc_buffer_t *target)
1885 {
1886         unsigned char *ndata;
1887         char *tdata;
1888         unsigned int nlen, tlen;
1889         unsigned char c;
1890         unsigned int trem, count;
1891         unsigned int bytes, nibbles;
1892         size_t i, len;
1893         unsigned int labels;
1894         char num[4];
1895
1896         /*
1897          * This function assumes the name is in proper uncompressed
1898          * wire format.
1899          */
1900         REQUIRE(VALID_NAME(name));
1901         REQUIRE((name->attributes & DNS_NAMEATTR_ABSOLUTE) != 0);
1902         REQUIRE(ISC_BUFFER_VALID(target));
1903
1904         ndata = name->ndata;
1905         nlen = name->length;
1906         labels = name->labels;
1907         tdata = isc_buffer_used(target);
1908         tlen = isc_buffer_availablelength(target);
1909
1910         trem = tlen;
1911
1912         if (nlen == 1 && labels == 1 && *ndata == '\0') {
1913                 /*
1914                  * Special handling for the root label.
1915                  */
1916                 if (trem == 0)
1917                         return (ISC_R_NOSPACE);
1918
1919                 omit_final_dot = ISC_FALSE;
1920                 *tdata++ = '.';
1921                 trem--;
1922
1923                 /*
1924                  * Skip the while() loop.
1925                  */
1926                 nlen = 0;
1927         }
1928
1929         while (labels > 0 && nlen > 0 && trem > 0) {
1930                 labels--;
1931                 count = *ndata++;
1932                 nlen--;
1933                 if (count == 0)
1934                         break;
1935                 if (count < 64) {
1936                         INSIST(nlen >= count);
1937                         while (count > 0) {
1938                                 c = *ndata;
1939                                 if ((c >= 0x30 && c <= 0x39) || /* digit */
1940                                     (c >= 0x41 && c <= 0x5A) || /* uppercase */
1941                                     (c >= 0x61 && c <= 0x7A) || /* lowercase */
1942                                     c == 0x2D ||                /* hyphen */
1943                                     c == 0x5F)                  /* underscore */
1944                                 {
1945                                         if (trem == 0)
1946                                                 return (ISC_R_NOSPACE);
1947                                         /* downcase */
1948                                         if (c >= 0x41 && c <= 0x5A)
1949                                                 c += 0x20;
1950                                         CONVERTFROMASCII(c);
1951                                         *tdata++ = c;
1952                                         ndata++;
1953                                         trem--;
1954                                         nlen--;
1955                                 } else {
1956                                         if (trem < 3)
1957                                                 return (ISC_R_NOSPACE);
1958                                         sprintf(tdata, "%%%02X", c);
1959                                         tdata += 3;
1960                                         trem -= 3;
1961                                         ndata++;
1962                                         nlen--;
1963                                 }
1964                                 count--;
1965                         }
1966                 } else if (count == DNS_LABELTYPE_BITSTRING) {
1967                         if (trem < 3)
1968                                 return (ISC_R_NOSPACE);
1969                         *tdata++ = '%';
1970                         *tdata++ = 'x';
1971                         trem -= 2;
1972                         INSIST(nlen > 0);
1973                         count = *ndata++;
1974                         if (count == 0)
1975                                 count = 256;
1976                         nlen--;
1977                         len = sprintf(num, "%u", count);        /* XXX */
1978                         INSIST(len <= 4U);
1979                         bytes = count / 8;
1980                         if (count % 8 != 0)
1981                                 bytes++;
1982                         INSIST(nlen >= bytes);
1983                         nibbles = count / 4;
1984                         if (count % 4 != 0)
1985                                 nibbles++;
1986                         if (trem < nibbles)
1987                                 return (ISC_R_NOSPACE);
1988                         trem -= nibbles;
1989                         nlen -= bytes;
1990                         while (nibbles > 0) {
1991                                 c = *ndata++;
1992                                 *tdata++ = hexdigits[(c >> 4)];
1993                                 nibbles--;
1994                                 if (nibbles != 0) {
1995                                         *tdata++ = hexdigits[c & 0xf];
1996                                         i++;
1997                                         nibbles--;
1998                                 }
1999                         }
2000                         if (trem < 2 + len)
2001                                 return (ISC_R_NOSPACE);
2002                         *tdata++ = '%';
2003                         for (i = 0; i < len; i++)
2004                                 *tdata++ = num[i];
2005                         *tdata++ = '%';
2006                         trem -= 2 + len;
2007                 } else {
2008                         FATAL_ERROR(__FILE__, __LINE__,
2009                                     "Unexpected label type %02x", count);
2010                         /* NOTREACHED */
2011                 }
2012
2013                 /*
2014                  * The following assumes names are absolute.  If not, we
2015                  * fix things up later.  Note that this means that in some
2016                  * cases one more byte of text buffer is required than is
2017                  * needed in the final output.
2018                  */
2019                 if (trem == 0)
2020                         return (ISC_R_NOSPACE);
2021                 *tdata++ = '.';
2022                 trem--;
2023         }
2024
2025         if (nlen != 0 && trem == 0)
2026                 return (ISC_R_NOSPACE);
2027
2028         if (omit_final_dot)
2029                 trem++;
2030
2031         isc_buffer_add(target, tlen - trem);
2032
2033         return (ISC_R_SUCCESS);
2034 }
2035
2036 isc_result_t
2037 dns_name_downcase(dns_name_t *source, dns_name_t *name, isc_buffer_t *target) {
2038         unsigned char *sndata, *ndata;
2039         unsigned int nlen, count, bytes, labels;
2040         isc_buffer_t buffer;
2041
2042         /*
2043          * Downcase 'source'.
2044          */
2045
2046         REQUIRE(VALID_NAME(source));
2047         REQUIRE(VALID_NAME(name));
2048         if (source == name) {
2049                 REQUIRE((name->attributes & DNS_NAMEATTR_READONLY) == 0);
2050                 isc_buffer_init(&buffer, source->ndata, source->length);
2051                 target = &buffer;
2052                 ndata = source->ndata;
2053         } else {
2054                 REQUIRE(BINDABLE(name));
2055                 REQUIRE((target != NULL && ISC_BUFFER_VALID(target)) ||
2056                         (target == NULL && ISC_BUFFER_VALID(name->buffer)));
2057                 if (target == NULL) {
2058                         target = name->buffer;
2059                         isc_buffer_clear(name->buffer);
2060                 }
2061                 ndata = (unsigned char *)target->base + target->used;
2062                 name->ndata = ndata;
2063         }
2064
2065         sndata = source->ndata;
2066         nlen = source->length;
2067         labels = source->labels;
2068
2069         if (nlen > (target->length - target->used)) {
2070                 MAKE_EMPTY(name);
2071                 return (ISC_R_NOSPACE);
2072         }
2073
2074         while (labels > 0 && nlen > 0) {
2075                 labels--;
2076                 count = *sndata++;
2077                 *ndata++ = count;
2078                 nlen--;
2079                 if (count < 64) {
2080                         INSIST(nlen >= count);
2081                         while (count > 0) {
2082                                 *ndata++ = maptolower[(*sndata++)];
2083                                 nlen--;
2084                                 count--;
2085                         }
2086                 } else if (count == DNS_LABELTYPE_BITSTRING) {
2087                         INSIST(nlen > 0);
2088                         count = *sndata++;
2089                         *ndata++ = count;
2090                         if (count == 0)
2091                                 count = 256;
2092                         nlen--;
2093
2094                         bytes = count / 8;
2095                         if (count % 8 != 0)
2096                                 bytes++;
2097
2098                         INSIST(nlen >= bytes);
2099                         nlen -= bytes;
2100                         while (bytes > 0) {
2101                                 *ndata++ = *sndata++;
2102                                 bytes--;
2103                         }
2104                 } else {
2105                         FATAL_ERROR(__FILE__, __LINE__,
2106                                     "Unexpected label type %02x", count);
2107                         /* Does not return. */
2108                 }
2109         }
2110
2111         if (source != name) {
2112                 name->labels = source->labels;
2113                 name->length = source->length;
2114                 if ((source->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
2115                         name->attributes = DNS_NAMEATTR_ABSOLUTE;
2116                 else
2117                         name->attributes = 0;
2118                 if (name->labels > 0 && name->offsets != NULL)
2119                         set_offsets(name, name->offsets, NULL);
2120         }
2121
2122         isc_buffer_add(target, name->length);
2123
2124         return (ISC_R_SUCCESS);
2125 }
2126
2127 static void
2128 set_offsets(const dns_name_t *name, unsigned char *offsets,
2129             dns_name_t *set_name)
2130 {
2131         unsigned int offset, count, length, nlabels, n;
2132         unsigned char *ndata;
2133         isc_boolean_t absolute;
2134
2135         ndata = name->ndata;
2136         length = name->length;
2137         offset = 0;
2138         nlabels = 0;
2139         absolute = ISC_FALSE;
2140         while (offset != length) {
2141                 INSIST(nlabels < 128);
2142                 offsets[nlabels++] = offset;
2143                 count = *ndata++;
2144                 offset++;
2145                 if (count <= 63) {
2146                         offset += count;
2147                         ndata += count;
2148                         INSIST(offset <= length);
2149                         if (count == 0) {
2150                                 absolute = ISC_TRUE;
2151                                 break;
2152                         }
2153                 } else {
2154                         INSIST(count == DNS_LABELTYPE_BITSTRING);
2155                         n = *ndata++;
2156                         offset++;
2157                         if (n == 0)
2158                                 n = 256;
2159                         count = n / 8;
2160                         if (n % 8 != 0)
2161                                 count++;
2162                         offset += count;
2163                         ndata += count;
2164                         INSIST(offset <= length);
2165                 }
2166         }
2167         if (set_name != NULL) {
2168                 INSIST(set_name == name);
2169
2170                 set_name->labels = nlabels;
2171                 set_name->length = offset;
2172                 if (absolute)
2173                         set_name->attributes |= DNS_NAMEATTR_ABSOLUTE;
2174                 else
2175                         set_name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
2176         }
2177         INSIST(nlabels == name->labels);
2178         INSIST(offset == name->length);
2179 }
2180
2181 static void
2182 compact(dns_name_t *name, unsigned char *offsets) {
2183         unsigned char *head, *curr, *last;
2184         unsigned int count, n, bit;
2185         unsigned int headbits, currbits, tailbits, newbits;
2186         unsigned int headrem, newrem;
2187         unsigned int headindex, currindex, tailindex, newindex;
2188         unsigned char tail[32];
2189
2190         /*
2191          * The caller MUST ensure that all bitstrings are correctly formatted
2192          * and that the offsets table is valid.
2193          */
2194
2195  again:
2196         memset(tail, 0, sizeof tail);
2197         INSIST(name->labels != 0);
2198         n = name->labels - 1;
2199
2200         while (n > 0) {
2201                 head = &name->ndata[offsets[n]];
2202                 if (head[0] == DNS_LABELTYPE_BITSTRING && head[1] != 0) {
2203                         if (n != 0) {
2204                                 n--;
2205                                 curr = &name->ndata[offsets[n]];
2206                                 if (curr[0] != DNS_LABELTYPE_BITSTRING)
2207                                         continue;
2208                                 /*
2209                                  * We have consecutive bitstrings labels, and
2210                                  * the more significant label ('head') has
2211                                  * space.
2212                                  */
2213                                 currbits = curr[1];
2214                                 if (currbits == 0)
2215                                         currbits = 256;
2216                                 currindex = 0;
2217                                 headbits = head[1];
2218                                 if (headbits == 0)
2219                                         headbits = 256;
2220                                 headindex = headbits;
2221                                 count = 256 - headbits;
2222                                 if (count > currbits)
2223                                         count = currbits;
2224                                 headrem = headbits % 8;
2225                                 if (headrem != 0)
2226                                         headrem = 8 - headrem;
2227                                 if (headrem != 0) {
2228                                         if (headrem > count)
2229                                                 headrem = count;
2230                                         do {
2231                                                 bit = get_bit(&curr[2],
2232                                                               currindex);
2233                                                 set_bit(&head[2], headindex,
2234                                                         bit);
2235                                                 currindex++;
2236                                                 headindex++;
2237                                                 headbits++;
2238                                                 count--;
2239                                                 headrem--;
2240                                         } while (headrem != 0);
2241                                 }
2242                                 tailindex = 0;
2243                                 tailbits = 0;
2244                                 while (count > 0) {
2245                                         bit = get_bit(&curr[2], currindex);
2246                                         set_bit(tail, tailindex, bit);
2247                                         currindex++;
2248                                         tailindex++;
2249                                         tailbits++;
2250                                         count--;
2251                                 }
2252                                 newbits = 0;
2253                                 newindex = 0;
2254                                 if (currindex < currbits) {
2255                                         while (currindex < currbits) {
2256                                                 bit = get_bit(&curr[2],
2257                                                               currindex);
2258                                                 set_bit(&curr[2], newindex,
2259                                                         bit);
2260                                                 currindex++;
2261                                                 newindex++;
2262                                                 newbits++;
2263                                         }
2264                                         INSIST(newbits < 256);
2265                                         curr[1] = newbits;
2266                                         count = newbits / 8;
2267                                         newrem = newbits % 8;
2268                                         /* Zero remaining pad bits, if any. */
2269                                         if (newrem != 0) {
2270                                                 count++;
2271                                                 newrem = 8 - newrem;
2272                                                 while (newrem > 0) {
2273                                                         set_bit(&curr[2],
2274                                                                 newindex,
2275                                                                 0);
2276                                                         newrem--;
2277                                                         newindex++;
2278                                                 }
2279                                         }
2280                                         curr += count + 2;
2281                                 } else {
2282                                         /* We got rid of curr. */
2283                                         name->labels--;
2284                                 }
2285                                 /* copy head, then tail, then rest to curr. */
2286                                 count = headbits + tailbits;
2287                                 INSIST(count <= 256);
2288                                 curr[0] = DNS_LABELTYPE_BITSTRING;
2289                                 if (count == 256)
2290                                         curr[1] = 0;
2291                                 else
2292                                         curr[1] = count;
2293                                 curr += 2;
2294                                 head += 2;
2295                                 count = headbits / 8;
2296                                 if (headbits % 8 != 0)
2297                                         count++;
2298                                 while (count > 0) {
2299                                         *curr++ = *head++;
2300                                         count--;
2301                                 }
2302                                 count = tailbits / 8;
2303                                 if (tailbits % 8 != 0)
2304                                         count++;
2305                                 last = tail;
2306                                 while (count > 0) {
2307                                         *curr++ = *last++;
2308                                         count--;
2309                                 }
2310                                 last = name->ndata + name->length;
2311                                 while (head != last)
2312                                         *curr++ = *head++;
2313                                 name->length = (curr - name->ndata);
2314                                 /*
2315                                  * The offsets table may now be invalid.
2316                                  */
2317                                 set_offsets(name, offsets, NULL);
2318                                 goto again;
2319                         }
2320                 }
2321                 n--;
2322         }
2323 }
2324
2325 isc_result_t
2326 dns_name_fromwire(dns_name_t *name, isc_buffer_t *source,
2327                   dns_decompress_t *dctx, isc_boolean_t downcase,
2328                   isc_buffer_t *target)
2329 {
2330         unsigned char *cdata, *ndata;
2331         unsigned int cused; /* Bytes of compressed name data used */
2332         unsigned int hops,  nused, labels, n, nmax;
2333         unsigned int current, new_current, biggest_pointer;
2334         isc_boolean_t saw_bitstring, done;
2335         fw_state state = fw_start;
2336         unsigned int c;
2337         unsigned char *offsets;
2338         dns_offsets_t odata;
2339
2340         /*
2341          * Copy the possibly-compressed name at source into target,
2342          * decompressing it.
2343          */
2344
2345         REQUIRE(VALID_NAME(name));
2346         REQUIRE((target != NULL && ISC_BUFFER_VALID(target)) ||
2347                 (target == NULL && ISC_BUFFER_VALID(name->buffer)));
2348
2349         if (target == NULL && name->buffer != NULL) {
2350                 target = name->buffer;
2351                 isc_buffer_clear(target);
2352         }
2353
2354         REQUIRE(dctx != NULL);
2355         REQUIRE(BINDABLE(name));
2356
2357         INIT_OFFSETS(name, offsets, odata);
2358
2359         /*
2360          * Make 'name' empty in case of failure.
2361          */
2362         MAKE_EMPTY(name);
2363
2364         /*
2365          * Initialize things to make the compiler happy; they're not required.
2366          */
2367         n = 0;
2368         new_current = 0;
2369
2370         /*
2371          * Set up.
2372          */
2373         labels = 0;
2374         hops = 0;
2375         saw_bitstring = ISC_FALSE;
2376         done = ISC_FALSE;
2377
2378         ndata = isc_buffer_used(target);
2379         nused = 0;
2380
2381         /*
2382          * Find the maximum number of uncompressed target name
2383          * bytes we are willing to generate.  This is the smaller
2384          * of the available target buffer length and the
2385          * maximum legal domain name length (255).
2386          */
2387         nmax = isc_buffer_availablelength(target);
2388         if (nmax > DNS_NAME_MAXWIRE)
2389                 nmax = DNS_NAME_MAXWIRE;
2390
2391         cdata = isc_buffer_current(source);
2392         cused = 0;
2393
2394         current = source->current;
2395         biggest_pointer = current;
2396
2397         /*
2398          * Note:  The following code is not optimized for speed, but
2399          * rather for correctness.  Speed will be addressed in the future.
2400          */
2401
2402         while (current < source->active && !done) {
2403                 c = *cdata++;
2404                 current++;
2405                 if (hops == 0)
2406                         cused++;
2407
2408                 switch (state) {
2409                 case fw_start:
2410                         if (c < 64) {
2411                                 offsets[labels] = nused;
2412                                 labels++;
2413                                 if (nused + c + 1 > nmax)
2414                                         goto full;
2415                                 nused += c + 1;
2416                                 *ndata++ = c;
2417                                 if (c == 0)
2418                                         done = ISC_TRUE;
2419                                 n = c;
2420                                 state = fw_ordinary;
2421                         } else if (c >= 128 && c < 192) {
2422                                 /*
2423                                  * 14 bit local compression pointer.
2424                                  * Local compression is no longer an
2425                                  * IETF draft.
2426                                  */
2427                                 return (DNS_R_BADLABELTYPE);
2428                         } else if (c >= 192) {
2429                                 /*
2430                                  * Ordinary 14-bit pointer.
2431                                  */
2432                                 if ((dctx->allowed & DNS_COMPRESS_GLOBAL14) ==
2433                                     0)
2434                                         return (DNS_R_DISALLOWED);
2435                                 new_current = c & 0x3F;
2436                                 n = 1;
2437                                 state = fw_newcurrent;
2438                         } else if (c == DNS_LABELTYPE_BITSTRING) {
2439                                 offsets[labels] = nused;
2440                                 labels++;
2441                                 if (nused == nmax)
2442                                         goto full;
2443                                 nused++;
2444                                 *ndata++ = c;
2445                                 saw_bitstring = ISC_TRUE;
2446                                 state = fw_bitstring;
2447                         } else
2448                                 return (DNS_R_BADLABELTYPE);
2449                         break;
2450                 case fw_ordinary:
2451                         if (downcase)
2452                                 c = maptolower[c];
2453                         /* FALLTHROUGH */
2454                 case fw_copy:
2455                         *ndata++ = c;
2456                         n--;
2457                         if (n == 0)
2458                                 state = fw_start;
2459                         break;
2460                 case fw_bitstring:
2461                         if (c == 0)
2462                                 n = 256 / 8;
2463                         else
2464                                 n = c / 8;
2465                         if ((c % 8) != 0)
2466                                 n++;
2467                         if (nused + n + 1 > nmax)
2468                                 goto full;
2469                         nused += n + 1;
2470                         *ndata++ = c;
2471                         state = fw_copy;
2472                         break;
2473                 case fw_newcurrent:
2474                         new_current *= 256;
2475                         new_current += c;
2476                         n--;
2477                         if (n != 0)
2478                                 break;
2479                         if (new_current >= biggest_pointer)
2480                                 return (DNS_R_BADPOINTER);
2481                         biggest_pointer = new_current;
2482                         current = new_current;
2483                         cdata = (unsigned char *)source->base +
2484                                 current;
2485                         hops++;
2486                         if (hops > DNS_POINTER_MAXHOPS)
2487                                 return (DNS_R_TOOMANYHOPS);
2488                         state = fw_start;
2489                         break;
2490                 default:
2491                         FATAL_ERROR(__FILE__, __LINE__,
2492                                     "Unknown state %d", state);
2493                         /* Does not return. */
2494                 }
2495         }
2496
2497         if (!done)
2498                 return (ISC_R_UNEXPECTEDEND);
2499
2500         name->ndata = (unsigned char *)target->base + target->used;
2501         name->labels = labels;
2502         name->length = nused;
2503         name->attributes |= DNS_NAMEATTR_ABSOLUTE;
2504
2505         if (saw_bitstring)
2506                 compact(name, offsets);
2507
2508         isc_buffer_forward(source, cused);
2509         isc_buffer_add(target, name->length);
2510
2511         return (ISC_R_SUCCESS);
2512
2513  full:
2514         if (nmax == DNS_NAME_MAXWIRE)
2515                 /*
2516                  * The name did not fit even though we had a buffer
2517                  * big enough to fit a maximum-length name.
2518                  */
2519                 return (DNS_R_NAMETOOLONG);
2520         else
2521                 /*
2522                  * The name might fit if only the caller could give us a
2523                  * big enough buffer.
2524                  */
2525                 return (ISC_R_NOSPACE);
2526
2527 }
2528
2529 isc_result_t
2530 dns_name_towire(dns_name_t *name, dns_compress_t *cctx, isc_buffer_t *target) {
2531         unsigned int methods;
2532         isc_uint16_t offset;
2533         dns_name_t gp;  /* Global compression prefix */
2534         isc_boolean_t gf;       /* Global compression target found */
2535         isc_uint16_t go;        /* Global compression offset */
2536         dns_offsets_t clo;
2537         dns_name_t clname;
2538
2539         /*
2540          * Convert 'name' into wire format, compressing it as specified by the
2541          * compression context 'cctx', and storing the result in 'target'.
2542          */
2543
2544         REQUIRE(VALID_NAME(name));
2545         REQUIRE(cctx != NULL);
2546         REQUIRE(ISC_BUFFER_VALID(target));
2547
2548         /*
2549          * If 'name' doesn't have an offsets table, make a clone which
2550          * has one.
2551          */
2552         if (name->offsets == NULL) {
2553                 DNS_NAME_INIT(&clname, clo);
2554                 dns_name_clone(name, &clname);
2555                 name = &clname;
2556         }
2557         DNS_NAME_INIT(&gp, NULL);
2558
2559         offset = target->used;  /*XXX*/
2560
2561         methods = dns_compress_getmethods(cctx);
2562
2563         if ((methods & DNS_COMPRESS_GLOBAL14) != 0)
2564                 gf = dns_compress_findglobal(cctx, name, &gp, &go);
2565         else
2566                 gf = ISC_FALSE;
2567
2568         /*
2569          * If the offset is too high for 14 bit global compression, we're
2570          * out of luck.
2571          */
2572         if (gf && go >= 0x4000)
2573                 gf = ISC_FALSE;
2574
2575         /*
2576          * Will the compression pointer reduce the message size?
2577          */
2578         if (gf && (gp.length + 2) >= name->length)
2579                 gf = ISC_FALSE;
2580
2581         if (gf) {
2582                 if (target->length - target->used < gp.length)
2583                         return (ISC_R_NOSPACE);
2584                 (void)memcpy((unsigned char *)target->base + target->used,
2585                              gp.ndata, (size_t)gp.length);
2586                 isc_buffer_add(target, gp.length);
2587                 go |= 0xc000;
2588                 if (target->length - target->used < 2)
2589                         return (ISC_R_NOSPACE);
2590                 isc_buffer_putuint16(target, go);
2591                 if (gp.length != 0)
2592                         dns_compress_add(cctx, name, &gp, offset);
2593         } else {
2594                 if (target->length - target->used < name->length)
2595                         return (ISC_R_NOSPACE);
2596                 (void)memcpy((unsigned char *)target->base + target->used,
2597                              name->ndata, (size_t)name->length);
2598                 isc_buffer_add(target, name->length);
2599                 dns_compress_add(cctx, name, name, offset);
2600         }
2601         return (ISC_R_SUCCESS);
2602 }
2603
2604 isc_result_t
2605 dns_name_concatenate(dns_name_t *prefix, dns_name_t *suffix, dns_name_t *name,
2606                      isc_buffer_t *target)
2607 {
2608         unsigned char *ndata, *offsets;
2609         unsigned int nrem, labels, prefix_length, length, offset;
2610         isc_boolean_t copy_prefix = ISC_TRUE;
2611         isc_boolean_t copy_suffix = ISC_TRUE;
2612         isc_boolean_t saw_bitstring = ISC_FALSE;
2613         isc_boolean_t absolute = ISC_FALSE;
2614         dns_name_t tmp_name;
2615         dns_offsets_t odata;
2616
2617         /*
2618          * Concatenate 'prefix' and 'suffix'.
2619          */
2620
2621         REQUIRE(prefix == NULL || VALID_NAME(prefix));
2622         REQUIRE(suffix == NULL || VALID_NAME(suffix));
2623         REQUIRE(name == NULL || VALID_NAME(name));
2624         REQUIRE((target != NULL && ISC_BUFFER_VALID(target)) ||
2625                 (target == NULL && name != NULL && ISC_BUFFER_VALID(name->buffer)));
2626         if (prefix == NULL || prefix->labels == 0)
2627                 copy_prefix = ISC_FALSE;
2628         if (suffix == NULL || suffix->labels == 0)
2629                 copy_suffix = ISC_FALSE;
2630         if (copy_prefix &&
2631             (prefix->attributes & DNS_NAMEATTR_ABSOLUTE) != 0) {
2632                 absolute = ISC_TRUE;
2633                 REQUIRE(!copy_suffix);
2634         }
2635         if (name == NULL) {
2636                 DNS_NAME_INIT(&tmp_name, odata);
2637                 name = &tmp_name;
2638         }
2639         if (target == NULL) {
2640                 INSIST(name->buffer != NULL);
2641                 target = name->buffer;
2642                 isc_buffer_clear(name->buffer);
2643         }
2644
2645         REQUIRE(BINDABLE(name));
2646
2647         /*
2648          * XXX IMPORTANT NOTE
2649          *
2650          * If the most-signficant label in prefix is a bitstring,
2651          * and the least-signficant label in suffix is a bitstring,
2652          * it's possible that compaction could convert them into
2653          * one label.  If this happens, then the final size will
2654          * be three bytes less than nrem.
2655          *
2656          * We do not check for this special case, and handling it is
2657          * a little messy; we can't just concatenate and compact,
2658          * because we may only have 255 bytes but might need 258 bytes
2659          * temporarily.  There are ways to do this with only 255 bytes,
2660          * which will be implemented later.
2661          *
2662          * For now, we simply reject these few cases as being too
2663          * long.
2664          */
2665
2666         /*
2667          * Set up.
2668          */
2669         nrem = target->length - target->used;
2670         ndata = (unsigned char *)target->base + target->used;
2671         if (nrem > DNS_NAME_MAXWIRE)
2672                 nrem = DNS_NAME_MAXWIRE;
2673         length = 0;
2674         prefix_length = 0;
2675         labels = 0;
2676         if (copy_prefix) {
2677                 prefix_length = prefix->length;
2678                 length += prefix_length;
2679                 labels += prefix->labels;
2680         }
2681         if (copy_suffix) {
2682                 length += suffix->length;
2683                 labels += suffix->labels;
2684         }
2685         if (length > DNS_NAME_MAXWIRE) {
2686                 MAKE_EMPTY(name);
2687                 return (DNS_R_NAMETOOLONG);
2688         }
2689         if (length > nrem) {
2690                 MAKE_EMPTY(name);
2691                 return (ISC_R_NOSPACE);
2692         }
2693
2694         if (copy_suffix) {
2695                 if ((suffix->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
2696                         absolute = ISC_TRUE;
2697                 if (copy_prefix &&
2698                     suffix->ndata[0] == DNS_LABELTYPE_BITSTRING) {
2699                         /*
2700                          * We only need to call compact() if both the
2701                          * least-significant label of the suffix and the
2702                          * most-significant label of the prefix are both
2703                          * bitstrings.
2704                          *
2705                          * A further possible optimization, which we don't do,
2706                          * is to not compact() if the suffix bitstring is
2707                          * full.  It will usually not be full, so I don't
2708                          * think this is worth it.
2709                          */
2710                         if (prefix->offsets != NULL) {
2711                                 offset = prefix->offsets[prefix->labels - 1];
2712                                 if (prefix->ndata[offset] ==
2713                                     DNS_LABELTYPE_BITSTRING)
2714                                         saw_bitstring = ISC_TRUE;
2715                         } else {
2716                                 /*
2717                                  * We don't have an offsets table for prefix,
2718                                  * and rather than spend the effort to make it
2719                                  * we'll just compact(), which doesn't cost
2720                                  * more than computing the offsets table if
2721                                  * there is no bitstring in prefix.
2722                                  */
2723                                 saw_bitstring = ISC_TRUE;
2724                         }
2725                 }
2726                 if (suffix == name && suffix->buffer == target)
2727                         memmove(ndata + prefix_length, suffix->ndata,
2728                                 suffix->length);
2729                 else
2730                         memcpy(ndata + prefix_length, suffix->ndata,
2731                                suffix->length);
2732         }
2733
2734         /*
2735          * If 'prefix' and 'name' are the same object, and the object has
2736          * a dedicated buffer, and we're using it, then we don't have to
2737          * copy anything.
2738          */
2739         if (copy_prefix && (prefix != name || prefix->buffer != target))
2740                 memcpy(ndata, prefix->ndata, prefix_length);
2741
2742         name->ndata = ndata;
2743         name->labels = labels;
2744         name->length = length;
2745         if (absolute)
2746                 name->attributes = DNS_NAMEATTR_ABSOLUTE;
2747         else
2748                 name->attributes = 0;
2749
2750         if (name->labels > 0 && (name->offsets != NULL || saw_bitstring)) {
2751                 INIT_OFFSETS(name, offsets, odata);
2752                 set_offsets(name, offsets, NULL);
2753                 if (saw_bitstring)
2754                         compact(name, offsets);
2755         }
2756
2757         isc_buffer_add(target, name->length);
2758
2759         return (ISC_R_SUCCESS);
2760 }
2761
2762 isc_result_t
2763 dns_name_split(dns_name_t *name,
2764                unsigned int suffixlabels, unsigned int nbits,
2765                dns_name_t *prefix, dns_name_t *suffix)
2766
2767 {
2768         dns_offsets_t name_odata, prefix_odata, suffix_odata;
2769         unsigned char *offsets, *prefix_offsets = NULL, *suffix_offsets;
2770         isc_result_t result = ISC_R_SUCCESS;
2771         unsigned int splitlabel, bitbytes, mod, len;
2772         unsigned char *p, *src, *dst;
2773         isc_boolean_t maybe_compact_prefix = ISC_FALSE;
2774
2775         REQUIRE(VALID_NAME(name));
2776         REQUIRE(suffixlabels > 0);
2777         REQUIRE((nbits == 0 && suffixlabels < name->labels) ||
2778                 (nbits != 0 && suffixlabels <= name->labels));
2779         REQUIRE(prefix != NULL || suffix != NULL);
2780         REQUIRE(prefix == NULL ||
2781                 (VALID_NAME(prefix) &&
2782                  prefix->buffer != NULL &&
2783                  BINDABLE(prefix)));
2784         REQUIRE(suffix == NULL ||
2785                 (VALID_NAME(suffix) &&
2786                  suffix->buffer != NULL &&
2787                  BINDABLE(suffix)));
2788
2789         /*
2790          * When splitting bitstring labels, if prefix and suffix have the same
2791          * buffer, suffix will overwrite the ndata of prefix, corrupting it.
2792          * If prefix has the ndata of name, then it modifies the bitstring
2793          * label and suffix doesn't have the original available.  This latter
2794          * problem could be worked around if it is ever deemed desirable.
2795          */
2796         REQUIRE(nbits == 0 || prefix == NULL || suffix == NULL ||
2797                 (prefix->buffer->base != suffix->buffer->base &&
2798                  prefix->buffer->base != name->ndata));
2799
2800         SETUP_OFFSETS(name, offsets, name_odata);
2801
2802         splitlabel = name->labels - suffixlabels;
2803
2804         /*
2805          * Make p point at the count byte of the bitstring label,
2806          * if there is one (p will not be used if we are not
2807          * splitting bits).
2808          */
2809         p = &name->ndata[offsets[splitlabel] + 1];
2810
2811         /*
2812          * When a bit count is specified, ensure that the label is a bitstring
2813          * label and it has more bits than the requested slice.
2814          */
2815         REQUIRE(nbits == 0 ||
2816                 (*(p - 1) == DNS_LABELTYPE_BITSTRING && nbits < 256 &&
2817                  (*p == 0 || *p > nbits)));
2818
2819         mod = nbits % 8;
2820
2821         if (prefix != NULL) {
2822                 if (nbits > 0) {
2823                         isc_buffer_clear(prefix->buffer);
2824
2825                         /*
2826                          * '2' is for the DNS_LABELTYPE_BITSTRING id
2827                          * plus the existing number of bits byte.
2828                          */
2829                         len = offsets[splitlabel] + 2;
2830                         src = name->ndata;
2831                         dst = prefix->buffer->base;
2832
2833                         if (src != dst) {
2834                                 /*
2835                                  * If these are overlapping names ...
2836                                  * wow.  How bizarre could that be?
2837                                  */
2838                                 INSIST(! (src <= dst && src + len > dst) ||
2839                                          (dst <= src && dst + len > src));
2840
2841                                 memcpy(dst, src, len);
2842
2843                                 p = dst + len - 1;
2844                         }
2845
2846                         /*
2847                          * Set the new bit count.  Also, when a bitstring
2848                          * label being split is maximal length, compaction
2849                          * might be necessary on the prefix.
2850                          */
2851                         if (*p == 0) {
2852                                 maybe_compact_prefix = ISC_TRUE;
2853                                 *p = 256 - nbits;
2854                         } else
2855                                 *p = *p - nbits;
2856
2857                         /*
2858                          * Calculate the number of bytes necessary to hold
2859                          * all of the bits left in the prefix.
2860                          */
2861                         bitbytes = (*p - 1) / 8 + 1;
2862
2863                         prefix->length = len + bitbytes;
2864
2865                         if (prefix->length > prefix->buffer->length ) {
2866                                 dns_name_invalidate(prefix);
2867                                 return (ISC_R_NOSPACE);
2868                         }
2869
2870                         /*
2871                          * All of the bits now need to be shifted to the left
2872                          * to fill in the space taken by the removed bits.
2873                          * This is wonderfully easy when the number of removed
2874                          * bits is an integral multiple of 8, but of course
2875                          * life isn't always that easy.
2876                          */
2877                         src += len + nbits / 8;
2878                         dst = p + 1;
2879                         len = bitbytes;
2880
2881                         if (mod == 0) {
2882                                 memmove(dst, src, len);
2883                         } else {
2884                                 /*
2885                                  * p is adjusted to point to the last byte of
2886                                  * the starting bitstring label to make it
2887                                  * cheap to determine when bits from the next
2888                                  * byte should be shifted into the low order
2889                                  * bits of the current byte.
2890                                  */
2891                                 p = src + (mod + *p - 1) / 8;
2892
2893                                 while (len--) {
2894                                         *dst = *src++ << mod;
2895                                         /*
2896                                          * The 0xff subexpression guards
2897                                          * against arithmetic sign extension
2898                                          * by the right shift.
2899                                          */
2900                                         if (src <= p)
2901                                                 *dst++ |=
2902                                                         (*src >> (8 - mod)) &
2903                                                         ~(0xFF << mod);
2904                                 }
2905
2906                                 /*
2907                                  * Et voila, the very last byte has
2908                                  * automatically already had its padding
2909                                  * fixed by the left shift.
2910                                  */
2911                         }
2912
2913                         prefix->buffer->used = prefix->length;
2914                         prefix->ndata = prefix->buffer->base;
2915
2916                         /*
2917                          * Yes, = is meant here, not ==.  The intent is
2918                          * to have it set only when INSISTs are turned on,
2919                          * to doublecheck the result of set_offsets.
2920                          */
2921                         INSIST(len = prefix->length);
2922
2923                         INIT_OFFSETS(prefix, prefix_offsets, prefix_odata);
2924                         set_offsets(prefix, prefix_offsets, prefix);
2925
2926                         INSIST(prefix->labels == splitlabel + 1 &&
2927                                prefix->length == len);
2928
2929                 } else
2930                         dns_name_getlabelsequence(name, 0, splitlabel,
2931                                                   prefix);
2932
2933         }
2934
2935         if (suffix != NULL && result == ISC_R_SUCCESS) {
2936                 if (nbits > 0) {
2937                         bitbytes = (nbits - 1) / 8 + 1;
2938
2939                         isc_buffer_clear(suffix->buffer);
2940
2941                         /*
2942                          * The existing bitcount is in src.
2943                          * Set len to the number of bytes to be removed,
2944                          * and the suffix length to the number of bytes in
2945                          * the new name.
2946                          */
2947                         src = &name->ndata[offsets[splitlabel] + 1];
2948                         len = ((*src == 0 ? 256 : *src) - 1) / 8;
2949                         len -= (bitbytes - 1);
2950                         src++;
2951
2952                         suffix->length = name->length -
2953                                 offsets[splitlabel] - len;
2954
2955                         INSIST(suffix->length > 0);
2956                         if (suffix->length > suffix->buffer->length) {
2957                                 dns_name_invalidate(suffix);
2958                                 return (ISC_R_NOSPACE);
2959                         }
2960
2961                         /*
2962                          * First set up the bitstring label.
2963                          */
2964                         dst = suffix->buffer->base;
2965                         *dst++ = DNS_LABELTYPE_BITSTRING;
2966                         *dst++ = nbits;
2967
2968                         if (len > 0) {
2969                                 /*
2970                                  * Remember where the next label starts.
2971                                  */
2972                                 p = src + bitbytes + len;
2973
2974                                 /*
2975                                  * Some bytes are being removed from the
2976                                  * middle of the name because of the truncation
2977                                  * of bits in the bitstring label.  Copy
2978                                  * the bytes (whether full with 8 bits or not)
2979                                  * that are being kept.
2980                                  */
2981                                 for (len = bitbytes; len > 0; len--)
2982                                         *dst++ = *src++;
2983
2984                                 /*
2985                                  * Now just copy the rest of the labels of
2986                                  * the name by adjusting src to point to
2987                                  * the next label.
2988                                  *
2989                                  * 2 == label type byte + bitcount byte.
2990                                  */
2991                                 len = suffix->length - bitbytes - 2;
2992                                 src = p;
2993                         } else
2994                                 len = suffix->length - 2;
2995
2996                         if (len > 0)
2997                                 memmove(dst, src, len);
2998
2999                         suffix->buffer->used = suffix->length;
3000                         suffix->ndata = suffix->buffer->base;
3001
3002                         /*
3003                          * The byte that contains the end of the
3004                          * bitstring has its pad bits (if any) masked
3005                          * to zero.
3006                          */
3007                         if (mod != 0)
3008                                 suffix->ndata[bitbytes + 1] &=
3009                                         0xFF << (8 - mod);
3010
3011                         /*
3012                          * Yes, = is meant here, not ==.  The intent is
3013                          * to have it set only when INSISTs are turned on,
3014                          * to doublecheck the result of set_offsets.
3015                          */
3016                         INSIST(len = suffix->length);
3017
3018                         INIT_OFFSETS(suffix, suffix_offsets, suffix_odata);
3019                         set_offsets(suffix, suffix_offsets, suffix);
3020
3021                         INSIST(suffix->labels == suffixlabels &&
3022                                suffix->length == len);
3023
3024                 } else
3025                         dns_name_getlabelsequence(name, splitlabel,
3026                                                   suffixlabels, suffix);
3027
3028         }
3029
3030         /*
3031          * Compacting the prefix can't be done until after the suffix is
3032          * set, because it would screw up the offsets table of 'name'
3033          * when 'name' == 'prefix'.
3034          */
3035         if (maybe_compact_prefix && splitlabel > 0 &&
3036             prefix->ndata[prefix_offsets[splitlabel - 1]] ==
3037             DNS_LABELTYPE_BITSTRING)
3038                 compact(prefix, prefix_offsets);
3039
3040         return (result);
3041 }
3042
3043 isc_result_t
3044 dns_name_splitatdepth(dns_name_t *name, unsigned int depth,
3045                       dns_name_t *prefix, dns_name_t *suffix)
3046 {
3047         unsigned int suffixlabels, nbits, label, count, n;
3048         unsigned char *offsets, *ndata;
3049         dns_offsets_t odata;
3050
3051         /*
3052          * Split 'name' into two pieces at a certain depth.
3053          */
3054
3055         REQUIRE(VALID_NAME(name));
3056         REQUIRE(name->labels > 0);
3057         REQUIRE(depth > 0);
3058
3059         SETUP_OFFSETS(name, offsets, odata);
3060
3061         suffixlabels = 0;
3062         nbits = 0;
3063         label = name->labels;
3064         do {
3065                 label--;
3066                 ndata = &name->ndata[offsets[label]];
3067                 count = *ndata++;
3068                 if (count > 63) {
3069                         INSIST(count == DNS_LABELTYPE_BITSTRING);
3070                         /*
3071                          * Get the number of bits in the bitstring label.
3072                          */
3073                         n = *ndata++;
3074                         if (n == 0)
3075                                 n = 256;
3076                         suffixlabels++;
3077                         if (n <= depth) {
3078                                 /*
3079                                  * This entire bitstring is in the suffix.
3080                                  */
3081                                 depth -= n;
3082                         } else {
3083                                 /*
3084                                  * Only the first 'depth' bits of this
3085                                  * bitstring are in the suffix.
3086                                  */
3087                                 nbits = depth;
3088                                 depth = 0;
3089                         }
3090                 } else {
3091                         suffixlabels++;
3092                         depth--;
3093                 }
3094         } while (depth != 0 && label != 0);
3095
3096         /*
3097          * If depth is not zero, then the caller violated the requirement
3098          * that depth <= dns_name_depth(name).
3099          */
3100         if (depth != 0) {
3101                 REQUIRE(depth <= dns_name_depth(name));
3102                 /*
3103                  * We should never get here!
3104                  */
3105                 INSIST(0);
3106         }
3107
3108         return (dns_name_split(name, suffixlabels, nbits, prefix, suffix));
3109 }
3110
3111 isc_result_t
3112 dns_name_dup(dns_name_t *source, isc_mem_t *mctx, dns_name_t *target) {
3113         /*
3114          * Make 'target' a dynamically allocated copy of 'source'.
3115          */
3116
3117         REQUIRE(VALID_NAME(source));
3118         REQUIRE(source->length > 0);
3119         REQUIRE(VALID_NAME(target));
3120         REQUIRE(BINDABLE(target));
3121
3122         /*
3123          * Make 'target' empty in case of failure.
3124          */
3125         MAKE_EMPTY(target);
3126
3127         target->ndata = isc_mem_get(mctx, source->length);
3128         if (target->ndata == NULL)
3129                 return (ISC_R_NOMEMORY);
3130
3131         memcpy(target->ndata, source->ndata, source->length);
3132
3133         target->length = source->length;
3134         target->labels = source->labels;
3135         target->attributes = DNS_NAMEATTR_DYNAMIC;
3136         if ((source->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
3137                 target->attributes |= DNS_NAMEATTR_ABSOLUTE;
3138         if (target->offsets != NULL) {
3139                 if (source->offsets != NULL)
3140                         memcpy(target->offsets, source->offsets,
3141                                source->labels);
3142                 else
3143                         set_offsets(target, target->offsets, NULL);
3144         }
3145
3146         return (ISC_R_SUCCESS);
3147 }
3148
3149 isc_result_t
3150 dns_name_dupwithoffsets(dns_name_t *source, isc_mem_t *mctx,
3151                         dns_name_t *target)
3152 {
3153         /*
3154          * Make 'target' a read-only dynamically allocated copy of 'source'.
3155          * 'target' will also have a dynamically allocated offsets table.
3156          */
3157
3158         REQUIRE(VALID_NAME(source));
3159         REQUIRE(source->length > 0);
3160         REQUIRE(VALID_NAME(target));
3161         REQUIRE(BINDABLE(target));
3162         REQUIRE(target->offsets == NULL);
3163
3164         /*
3165          * Make 'target' empty in case of failure.
3166          */
3167         MAKE_EMPTY(target);
3168
3169         target->ndata = isc_mem_get(mctx, source->length + source->labels);
3170         if (target->ndata == NULL)
3171                 return (ISC_R_NOMEMORY);
3172
3173         memcpy(target->ndata, source->ndata, source->length);
3174
3175         target->length = source->length;
3176         target->labels = source->labels;
3177         target->attributes = DNS_NAMEATTR_DYNAMIC | DNS_NAMEATTR_DYNOFFSETS |
3178                 DNS_NAMEATTR_READONLY;
3179         if ((source->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
3180                 target->attributes |= DNS_NAMEATTR_ABSOLUTE;
3181         target->offsets = target->ndata + source->length;
3182         if (source->offsets != NULL)
3183                 memcpy(target->offsets, source->offsets, source->labels);
3184         else
3185                 set_offsets(target, target->offsets, NULL);
3186
3187         return (ISC_R_SUCCESS);
3188 }
3189
3190 void
3191 dns_name_free(dns_name_t *name, isc_mem_t *mctx) {
3192         size_t size;
3193
3194         /*
3195          * Free 'name'.
3196          */
3197
3198         REQUIRE(VALID_NAME(name));
3199         REQUIRE((name->attributes & DNS_NAMEATTR_DYNAMIC) != 0);
3200
3201         size = name->length;
3202         if ((name->attributes & DNS_NAMEATTR_DYNOFFSETS) != 0)
3203                 size += name->labels;
3204         isc_mem_put(mctx, name->ndata, size);
3205         dns_name_invalidate(name);
3206 }
3207
3208 isc_result_t
3209 dns_name_digest(dns_name_t *name, dns_digestfunc_t digest, void *arg) {
3210         dns_name_t downname;
3211         unsigned char data[256];
3212         isc_buffer_t buffer;
3213         isc_result_t result;
3214         isc_region_t r;
3215
3216         /*
3217          * Send 'name' in DNSSEC canonical form to 'digest'.
3218          */
3219
3220         REQUIRE(VALID_NAME(name));
3221         REQUIRE(digest != NULL);
3222
3223         DNS_NAME_INIT(&downname, NULL);
3224         isc_buffer_init(&buffer, data, sizeof(data));
3225
3226         result = dns_name_downcase(name, &downname, &buffer);
3227         if (result != ISC_R_SUCCESS)
3228                 return (result);
3229
3230         isc_buffer_usedregion(&buffer, &r);
3231
3232         return ((digest)(arg, &r));
3233 }
3234
3235 isc_boolean_t
3236 dns_name_dynamic(dns_name_t *name) {
3237         REQUIRE(VALID_NAME(name));
3238
3239         /*
3240          * Returns whether there is dynamic memory associated with this name.
3241          */
3242
3243         return ((name->attributes & DNS_NAMEATTR_DYNAMIC) != 0 ?
3244                 ISC_TRUE : ISC_FALSE);
3245 }
3246
3247 isc_result_t
3248 dns_name_print(dns_name_t *name, FILE *stream) {
3249         isc_result_t result;
3250         isc_buffer_t b;
3251         isc_region_t r;
3252         char t[1024];
3253
3254         /*
3255          * Print 'name' on 'stream'.
3256          */
3257
3258         REQUIRE(VALID_NAME(name));
3259
3260         isc_buffer_init(&b, t, sizeof(t));
3261         result = dns_name_totext(name, ISC_FALSE, &b);
3262         if (result != ISC_R_SUCCESS)
3263                 return (result);
3264         isc_buffer_usedregion(&b, &r);
3265         fprintf(stream, "%.*s", (int)r.length, (char *)r.base);
3266
3267         return (ISC_R_SUCCESS);
3268 }
3269
3270 void
3271 dns_name_format(dns_name_t *name, char *cp, unsigned int size) {
3272         isc_result_t result;
3273         isc_buffer_t buf;
3274
3275         REQUIRE(size > 0);
3276
3277         /*
3278          * Leave room for null termination after buffer.
3279          */
3280         isc_buffer_init(&buf, cp, size - 1);
3281         result = dns_name_totext(name, ISC_TRUE, &buf);
3282         if (result == ISC_R_SUCCESS) {
3283                 /*
3284                  * Null terminate.
3285                  */
3286                 isc_region_t r;
3287                 isc_buffer_usedregion(&buf, &r);
3288                 ((char *) r.base)[r.length] = '\0';
3289
3290         } else
3291                 snprintf(cp, size, "<unknown>");
3292 }
3293
3294 isc_result_t
3295 dns_name_copy(dns_name_t *source, dns_name_t *dest, isc_buffer_t *target) {
3296         unsigned char *ndata, *offsets;
3297         dns_offsets_t odata;
3298
3299         /*
3300          * Make dest a copy of source.
3301          */
3302
3303         REQUIRE(VALID_NAME(source));
3304         REQUIRE(VALID_NAME(dest));
3305         REQUIRE(target != NULL || dest->buffer != NULL);
3306
3307         if (target == NULL) {
3308                 target = dest->buffer;
3309                 isc_buffer_clear(dest->buffer);
3310         }
3311
3312         REQUIRE(BINDABLE(dest));
3313
3314         /*
3315          * Set up.
3316          */
3317         if (target->length - target->used < source->length)
3318                 return (ISC_R_NOSPACE);
3319
3320         ndata = (unsigned char *)target->base + target->used;
3321         dest->ndata = target->base;
3322
3323         memcpy(ndata, source->ndata, source->length);
3324
3325         dest->ndata = ndata;
3326         dest->labels = source->labels;
3327         dest->length = source->length;
3328         if ((source->attributes & DNS_NAMEATTR_ABSOLUTE) != 0)
3329                 dest->attributes = DNS_NAMEATTR_ABSOLUTE;
3330         else
3331                 dest->attributes = 0;
3332
3333         if (dest->labels > 0 && dest->offsets != NULL) {
3334                 INIT_OFFSETS(dest, offsets, odata);
3335                 set_offsets(dest, offsets, NULL);
3336         }
3337
3338         isc_buffer_add(target, dest->length);
3339
3340         return (ISC_R_SUCCESS);
3341 }
3342