unbound/util/data/dname.c

   1 /*
   2  * util/data/dname.h - domain name handling
   3  *
   4  * Copyright (c) 2007, NLnet Labs. All rights reserved.
   5  *
   6  * This software is open source.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * Redistributions of source code must retain the above copyright notice,
  13  * this list of conditions and the following disclaimer.
  14  *
  15  * Redistributions in binary form must reproduce the above copyright notice,
  16  * this list of conditions and the following disclaimer in the documentation
  17  * and/or other materials provided with the distribution.
  18  *
  19  * Neither the name of the NLNET LABS nor the names of its contributors may
  20  * be used to endorse or promote products derived from this software without
  21  * specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 /**
  37  * \file
  38  *
  39  * This file contains domain name handling functions.
  40  */
  41
  42 #include "config.h"
  43 #include <ctype.h>
  44 #include "util/data/dname.h"
  45 #include "util/data/msgparse.h"
  46 #include "util/log.h"
  47 #include "util/storage/lookup3.h"
  48 #include "ldns/sbuffer.h"
  49
  50 /* determine length of a dname in buffer, no compression pointers allowed */
  51 size_t
  52 query_dname_len(sldns_buffer* query)
  53 {
  54         size_t len = 0;
  55         size_t labellen;
  56         while(1) {
  57                 if(sldns_buffer_remaining(query) < 1)
  58                         return 0; /* parse error, need label len */
  59                 labellen = sldns_buffer_read_u8(query);
  60                 if(labellen&0xc0)
  61                         return 0; /* no compression allowed in queries */
  62                 len += labellen + 1;
  63                 if(len > LDNS_MAX_DOMAINLEN)
  64                         return 0; /* too long */
  65                 if(labellen == 0)
  66                         return len;
  67                 if(sldns_buffer_remaining(query) < labellen)
  68                         return 0; /* parse error, need content */
  69                 sldns_buffer_skip(query, (ssize_t)labellen);
  70         }
  71 }
  72
  73 size_t
  74 dname_valid(uint8_t* dname, size_t maxlen)
  75 {
  76         size_t len = 0;
  77         size_t labellen;
  78         labellen = *dname++;
  79         while(labellen) {
  80                 if(labellen&0xc0)
  81                         return 0; /* no compression ptrs allowed */
  82                 len += labellen + 1;
  83                 if(len >= LDNS_MAX_DOMAINLEN)
  84                         return 0; /* too long */
  85                 if(len > maxlen)
  86                         return 0; /* does not fit in memory allocation */
  87                 dname += labellen;
  88                 labellen = *dname++;
  89         }
  90         len += 1;
  91         if(len > maxlen)
  92                 return 0; /* does not fit in memory allocation */
  93         return len;
  94 }
  95
  96 /** compare uncompressed, noncanonical, registers are hints for speed */
  97 int
  98 query_dname_compare(register uint8_t* d1, register uint8_t* d2)
  99 {
 100         register uint8_t lab1, lab2;
 101         log_assert(d1 && d2);
 102         lab1 = *d1++;
 103         lab2 = *d2++;
 104         while( lab1 != 0 || lab2 != 0 ) {
 105                 /* compare label length */
 106                 /* if one dname ends, it has labellength 0 */
 107                 if(lab1 != lab2) {
 108                         if(lab1 < lab2)
 109                                 return -1;
 110                         return 1;
 111                 }
 112                 log_assert(lab1 == lab2 && lab1 != 0);
 113                 /* compare lowercased labels. */
 114                 while(lab1--) {
 115                         /* compare bytes first for speed */
 116                         if(*d1 != *d2 &&
 117                                 tolower((unsigned char)*d1) != tolower((unsigned char)*d2)) {
 118                                 if(tolower((unsigned char)*d1) < tolower((unsigned char)*d2))
 119                                         return -1;
 120                                 return 1;
 121                         }
 122                         d1++;
 123                         d2++;
 124                 }
 125                 /* next pair of labels. */
 126                 lab1 = *d1++;
 127                 lab2 = *d2++;
 128         }
 129         return 0;
 130 }
 131
 132 void
 133 query_dname_tolower(uint8_t* dname)
 134 {
 135         /* the dname is stored uncompressed */
 136         uint8_t labellen;
 137         labellen = *dname;
 138         while(labellen) {
 139                 dname++;
 140                 while(labellen--) {
 141                         *dname = (uint8_t)tolower((unsigned char)*dname);
 142                         dname++;
 143                 }
 144                 labellen = *dname;
 145         }
 146 }
 147
 148 void
 149 pkt_dname_tolower(sldns_buffer* pkt, uint8_t* dname)
 150 {
 151         uint8_t lablen;
 152         int count = 0;
 153         if(dname >= sldns_buffer_end(pkt))
 154                 return;
 155         lablen = *dname++;
 156         while(lablen) {
 157                 if(LABEL_IS_PTR(lablen)) {
 158                         if((size_t)PTR_OFFSET(lablen, *dname)
 159                                 >= sldns_buffer_limit(pkt))
 160                                 return;
 161                         dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
 162                         lablen = *dname++;
 163                         if(count++ > MAX_COMPRESS_PTRS)
 164                                 return;
 165                         continue;
 166                 }
 167                 if(dname+lablen >= sldns_buffer_end(pkt))
 168                         return;
 169                 while(lablen--) {
 170                         *dname = (uint8_t)tolower((unsigned char)*dname);
 171                         dname++;
 172                 }
 173                 if(dname >= sldns_buffer_end(pkt))
 174                         return;
 175                 lablen = *dname++;
 176         }
 177 }
 178
 179
 180 size_t
 181 pkt_dname_len(sldns_buffer* pkt)
 182 {
 183         size_t len = 0;
 184         int ptrcount = 0;
 185         uint8_t labellen;
 186         size_t endpos = 0;
 187
 188         /* read dname and determine length */
 189         /* check compression pointers, loops, out of bounds */
 190         while(1) {
 191                 /* read next label */
 192                 if(sldns_buffer_remaining(pkt) < 1)
 193                         return 0;
 194                 labellen = sldns_buffer_read_u8(pkt);
 195                 if(LABEL_IS_PTR(labellen)) {
 196                         /* compression ptr */
 197                         uint16_t ptr;
 198                         if(sldns_buffer_remaining(pkt) < 1)
 199                                 return 0;
 200                         ptr = PTR_OFFSET(labellen, sldns_buffer_read_u8(pkt));
 201                         if(ptrcount++ > MAX_COMPRESS_PTRS)
 202                                 return 0; /* loop! */
 203                         if(sldns_buffer_limit(pkt) <= ptr)
 204                                 return 0; /* out of bounds! */
 205                         if(!endpos)
 206                                 endpos = sldns_buffer_position(pkt);
 207                         sldns_buffer_set_position(pkt, ptr);
 208                 } else {
 209                         /* label contents */
 210                         if(labellen > 0x3f)
 211                                 return 0; /* label too long */
 212                         len += 1 + labellen;
 213                         if(len > LDNS_MAX_DOMAINLEN)
 214                                 return 0;
 215                         if(labellen == 0) {
 216                                 /* end of dname */
 217                                 break;
 218                         }
 219                         if(sldns_buffer_remaining(pkt) < labellen)
 220                                 return 0;
 221                         sldns_buffer_skip(pkt, (ssize_t)labellen);
 222                 }
 223         }
 224         if(endpos)
 225                 sldns_buffer_set_position(pkt, endpos);
 226
 227         return len;
 228 }
 229
 230 int
 231 dname_pkt_compare(sldns_buffer* pkt, uint8_t* d1, uint8_t* d2)
 232 {
 233         uint8_t len1, len2;
 234         log_assert(pkt && d1 && d2);
 235         len1 = *d1++;
 236         len2 = *d2++;
 237         while( len1 != 0 || len2 != 0 ) {
 238                 /* resolve ptrs */
 239                 if(LABEL_IS_PTR(len1)) {
 240                         d1 = sldns_buffer_at(pkt, PTR_OFFSET(len1, *d1));
 241                         len1 = *d1++;
 242                         continue;
 243                 }
 244                 if(LABEL_IS_PTR(len2)) {
 245                         d2 = sldns_buffer_at(pkt, PTR_OFFSET(len2, *d2));
 246                         len2 = *d2++;
 247                         continue;
 248                 }
 249                 /* check label length */
 250                 log_assert(len1 <= LDNS_MAX_LABELLEN);
 251                 log_assert(len2 <= LDNS_MAX_LABELLEN);
 252                 if(len1 != len2) {
 253                         if(len1 < len2) return -1;
 254                         return 1;
 255                 }
 256                 log_assert(len1 == len2 && len1 != 0);
 257                 /* compare labels */
 258                 while(len1--) {
 259                         if(tolower((unsigned char)*d1++) != tolower((unsigned char)*d2++)) {
 260                                 if(tolower((unsigned char)d1[-1]) < tolower((unsigned char)d2[-1]))
 261                                         return -1;
 262                                 return 1;
 263                         }
 264                 }
 265                 len1 = *d1++;
 266                 len2 = *d2++;
 267         }
 268         return 0;
 269 }
 270
 271 hashvalue_t
 272 dname_query_hash(uint8_t* dname, hashvalue_t h)
 273 {
 274         uint8_t labuf[LDNS_MAX_LABELLEN+1];
 275         uint8_t lablen;
 276         int i;
 277
 278         /* preserve case of query, make hash label by label */
 279         lablen = *dname++;
 280         while(lablen) {
 281                 log_assert(lablen <= LDNS_MAX_LABELLEN);
 282                 labuf[0] = lablen;
 283                 i=0;
 284                 while(lablen--)
 285                         labuf[++i] = (uint8_t)tolower((unsigned char)*dname++);
 286                 h = hashlittle(labuf, labuf[0] + 1, h);
 287                 lablen = *dname++;
 288         }
 289
 290         return h;
 291 }
 292
 293 hashvalue_t
 294 dname_pkt_hash(sldns_buffer* pkt, uint8_t* dname, hashvalue_t h)
 295 {
 296         uint8_t labuf[LDNS_MAX_LABELLEN+1];
 297         uint8_t lablen;
 298         int i;
 299
 300         /* preserve case of query, make hash label by label */
 301         lablen = *dname++;
 302         while(lablen) {
 303                 if(LABEL_IS_PTR(lablen)) {
 304                         /* follow pointer */
 305                         dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
 306                         lablen = *dname++;
 307                         continue;
 308                 }
 309                 log_assert(lablen <= LDNS_MAX_LABELLEN);
 310                 labuf[0] = lablen;
 311                 i=0;
 312                 while(lablen--)
 313                         labuf[++i] = (uint8_t)tolower((unsigned char)*dname++);
 314                 h = hashlittle(labuf, labuf[0] + 1, h);
 315                 lablen = *dname++;
 316         }
 317
 318         return h;
 319 }
 320
 321 void dname_pkt_copy(sldns_buffer* pkt, uint8_t* to, uint8_t* dname)
 322 {
 323         /* copy over the dname and decompress it at the same time */
 324         size_t len = 0;
 325         uint8_t lablen;
 326         lablen = *dname++;
 327         while(lablen) {
 328                 if(LABEL_IS_PTR(lablen)) {
 329                         /* follow pointer */
 330                         dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
 331                         lablen = *dname++;
 332                         continue;
 333                 }
 334                 log_assert(lablen <= LDNS_MAX_LABELLEN);
 335                 len += (size_t)lablen+1;
 336                 if(len >= LDNS_MAX_DOMAINLEN) {
 337                         *to = 0; /* end the result prematurely */
 338                         log_err("bad dname in dname_pkt_copy");
 339                         return;
 340                 }
 341                 *to++ = lablen;
 342                 memmove(to, dname, lablen);
 343                 dname += lablen;
 344                 to += lablen;
 345                 lablen = *dname++;
 346         }
 347         /* copy last \0 */
 348         *to = 0;
 349 }
 350
 351 void dname_print(FILE* out, struct sldns_buffer* pkt, uint8_t* dname)
 352 {
 353         uint8_t lablen;
 354         if(!out) out = stdout;
 355         if(!dname) return;
 356
 357         lablen = *dname++;
 358         if(!lablen)
 359                 fputc('.', out);
 360         while(lablen) {
 361                 if(LABEL_IS_PTR(lablen)) {
 362                         /* follow pointer */
 363                         if(!pkt) {
 364                                 fputs("??compressionptr??", out);
 365                                 return;
 366                         }
 367                         dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
 368                         lablen = *dname++;
 369                         continue;
 370                 }
 371                 if(lablen > LDNS_MAX_LABELLEN) {
 372                         fputs("??extendedlabel??", out);
 373                         return;
 374                 }
 375                 while(lablen--)
 376                         fputc((int)*dname++, out);
 377                 fputc('.', out);
 378                 lablen = *dname++;
 379         }
 380 }
 381
 382 int
 383 dname_count_labels(uint8_t* dname)
 384 {
 385         uint8_t lablen;
 386         int labs = 1;
 387
 388         lablen = *dname++;
 389         while(lablen) {
 390                 labs++;
 391                 dname += lablen;
 392                 lablen = *dname++;
 393         }
 394         return labs;
 395 }
 396
 397 int
 398 dname_count_size_labels(uint8_t* dname, size_t* size)
 399 {
 400         uint8_t lablen;
 401         int labs = 1;
 402         size_t sz = 1;
 403
 404         lablen = *dname++;
 405         while(lablen) {
 406                 labs++;
 407                 sz += lablen+1;
 408                 dname += lablen;
 409                 lablen = *dname++;
 410         }
 411         *size = sz;
 412         return labs;
 413 }
 414
 415 /**
 416  * Compare labels in memory, lowercase while comparing.
 417  * @param p1: label 1
 418  * @param p2: label 2
 419  * @param len: number of bytes to compare.
 420  * @return: 0, -1, +1 comparison result.
 421  */
 422 static int
 423 memlowercmp(uint8_t* p1, uint8_t* p2, uint8_t len)
 424 {
 425         while(len--) {
 426                 if(*p1 != *p2 && tolower((unsigned char)*p1) != tolower((unsigned char)*p2)) {
 427                         if(tolower((unsigned char)*p1) < tolower((unsigned char)*p2))
 428                                 return -1;
 429                         return 1;
 430                 }
 431                 p1++;
 432                 p2++;
 433         }
 434         return 0;
 435 }
 436
 437 int
 438 dname_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs)
 439 {
 440         uint8_t len1, len2;
 441         int atlabel = labs1;
 442         int lastmlabs;
 443         int lastdiff = 0;
 444         /* first skip so that we compare same label. */
 445         if(labs1 > labs2) {
 446                 while(atlabel > labs2) {
 447                         len1 = *d1++;
 448                         d1 += len1;
 449                         atlabel--;
 450                 }
 451                 log_assert(atlabel == labs2);
 452         } else if(labs1 < labs2) {
 453                 atlabel = labs2;
 454                 while(atlabel > labs1) {
 455                         len2 = *d2++;
 456                         d2 += len2;
 457                         atlabel--;
 458                 }
 459                 log_assert(atlabel == labs1);
 460         }
 461         lastmlabs = atlabel+1;
 462         /* now at same label in d1 and d2, atlabel */
 463         /* www.example.com.                  */
 464         /* 4   3       2  1   atlabel number */
 465         /* repeat until at root label (which is always the same) */
 466         while(atlabel > 1) {
 467                 len1 = *d1++;
 468                 len2 = *d2++;
 469                 if(len1 != len2) {
 470                         log_assert(len1 != 0 && len2 != 0);
 471                         if(len1<len2)
 472                                 lastdiff = -1;
 473                         else    lastdiff = 1;
 474                         lastmlabs = atlabel;
 475                         d1 += len1;
 476                         d2 += len2;
 477                 } else {
 478                         /* memlowercmp is inlined here; or just like
 479                          * if((c=memlowercmp(d1, d2, len1)) != 0) {
 480                          *      lastdiff = c;
 481                          *      lastmlabs = atlabel; } apart from d1++,d2++ */
 482                         while(len1) {
 483                                 if(*d1 != *d2 && tolower((unsigned char)*d1)
 484                                         != tolower((unsigned char)*d2)) {
 485                                         if(tolower((unsigned char)*d1) <
 486                                                 tolower((unsigned char)*d2)) {
 487                                                 lastdiff = -1;
 488                                                 lastmlabs = atlabel;
 489                                                 d1 += len1;
 490                                                 d2 += len1;
 491                                                 break;
 492                                         }
 493                                         lastdiff = 1;
 494                                         lastmlabs = atlabel;
 495                                         d1 += len1;
 496                                         d2 += len1;
 497                                         break; /* out of memlowercmp */
 498                                 }
 499                                 d1++;
 500                                 d2++;
 501                                 len1--;
 502                         }
 503                 }
 504                 atlabel--;
 505         }
 506         /* last difference atlabel number, so number of labels matching,
 507          * at the right side, is one less. */
 508         *mlabs = lastmlabs-1;
 509         if(lastdiff == 0) {
 510                 /* all labels compared were equal, check if one has more
 511                  * labels, so that example.com. > com. */
 512                 if(labs1 > labs2)
 513                         return 1;
 514                 else if(labs1 < labs2)
 515                         return -1;
 516         }
 517         return lastdiff;
 518 }
 519
 520 int
 521 dname_buffer_write(sldns_buffer* pkt, uint8_t* dname)
 522 {
 523         uint8_t lablen;
 524
 525         if(sldns_buffer_remaining(pkt) < 1)
 526                 return 0;
 527         lablen = *dname++;
 528         sldns_buffer_write_u8(pkt, lablen);
 529         while(lablen) {
 530                 if(sldns_buffer_remaining(pkt) < (size_t)lablen+1)
 531                         return 0;
 532                 sldns_buffer_write(pkt, dname, lablen);
 533                 dname += lablen;
 534                 lablen = *dname++;
 535                 sldns_buffer_write_u8(pkt, lablen);
 536         }
 537         return 1;
 538 }
 539
 540 void dname_str(uint8_t* dname, char* str)
 541 {
 542         size_t len = 0;
 543         uint8_t lablen = 0;
 544         char* s = str;
 545         if(!dname || !*dname) {
 546                 *s++ = '.';
 547                 *s = 0;
 548                 return;
 549         }
 550         lablen = *dname++;
 551         while(lablen) {
 552                 if(lablen > LDNS_MAX_LABELLEN) {
 553                         *s++ = '#';
 554                         *s = 0;
 555                         return;
 556                 }
 557                 len += lablen+1;
 558                 if(len >= LDNS_MAX_DOMAINLEN-1) {
 559                         *s++ = '&';
 560                         *s = 0;
 561                         return;
 562                 }
 563                 while(lablen--) {
 564                         if(isalnum((unsigned char)*dname)
 565                                 || *dname == '-' || *dname == '_'
 566                                 || *dname == '*')
 567                                 *s++ = *(char*)dname++;
 568                         else    {
 569                                 *s++ = '?';
 570                                 dname++;
 571                         }
 572                 }
 573                 *s++ = '.';
 574                 lablen = *dname++;
 575         }
 576         *s = 0;
 577 }
 578
 579 int
 580 dname_strict_subdomain(uint8_t* d1, int labs1, uint8_t* d2, int labs2)
 581 {
 582         int m;
 583         /* check subdomain: d1: www.example.com. and d2: example.com. */
 584         if(labs2 >= labs1)
 585                 return 0;
 586         if(dname_lab_cmp(d1, labs1, d2, labs2, &m) > 0) {
 587                 /* subdomain if all labels match */
 588                 return (m == labs2);
 589         }
 590         return 0;
 591 }
 592
 593 int
 594 dname_strict_subdomain_c(uint8_t* d1, uint8_t* d2)
 595 {
 596         return dname_strict_subdomain(d1, dname_count_labels(d1), d2,
 597                 dname_count_labels(d2));
 598 }
 599
 600 int
 601 dname_subdomain_c(uint8_t* d1, uint8_t* d2)
 602 {
 603         int m;
 604         /* check subdomain: d1: www.example.com. and d2: example.com. */
 605         /*      or          d1: example.com. and d2: example.com. */
 606         int labs1 = dname_count_labels(d1);
 607         int labs2 = dname_count_labels(d2);
 608         if(labs2 > labs1)
 609                 return 0;
 610         if(dname_lab_cmp(d1, labs1, d2, labs2, &m) < 0) {
 611                 /* must have been example.com , www.example.com - wrong */
 612                 /* or otherwise different dnames */
 613                 return 0;
 614         }
 615         return (m == labs2);
 616 }
 617
 618 int
 619 dname_is_root(uint8_t* dname)
 620 {
 621         uint8_t len;
 622         log_assert(dname);
 623         len = dname[0];
 624         log_assert(!LABEL_IS_PTR(len));
 625         return (len == 0);
 626 }
 627
 628 void
 629 dname_remove_label(uint8_t** dname, size_t* len)
 630 {
 631         size_t lablen;
 632         log_assert(dname && *dname && len);
 633         lablen = (*dname)[0];
 634         log_assert(!LABEL_IS_PTR(lablen));
 635         log_assert(*len > lablen);
 636         if(lablen == 0)
 637                 return; /* do not modify root label */
 638         *len -= lablen+1;
 639         *dname += lablen+1;
 640 }
 641
 642 void
 643 dname_remove_labels(uint8_t** dname, size_t* len, int n)
 644 {
 645         int i;
 646         for(i=0; i<n; i++)
 647                 dname_remove_label(dname, len);
 648 }
 649
 650 int
 651 dname_signame_label_count(uint8_t* dname)
 652 {
 653         uint8_t lablen;
 654         int count = 0;
 655         if(!*dname)
 656                 return 0;
 657         if(dname[0] == 1 && dname[1] == '*')
 658                 dname += 2;
 659         lablen = dname[0];
 660         while(lablen) {
 661                 count++;
 662                 dname += lablen;
 663                 dname += 1;
 664                 lablen = dname[0];
 665         }
 666         return count;
 667 }
 668
 669 int
 670 dname_is_wild(uint8_t* dname)
 671 {
 672         return (dname[0] == 1 && dname[1] == '*');
 673 }
 674
 675 /**
 676  * Compare labels in memory, lowercase while comparing.
 677  * Returns canonical order for labels. If all is equal, the
 678  * shortest is first.
 679  *
 680  * @param p1: label 1
 681  * @param len1: length of label 1.
 682  * @param p2: label 2
 683  * @param len2: length of label 2.
 684  * @return: 0, -1, +1 comparison result.
 685  */
 686 static int
 687 memcanoncmp(uint8_t* p1, uint8_t len1, uint8_t* p2, uint8_t len2)
 688 {
 689         uint8_t min = (len1<len2)?len1:len2;
 690         int c = memlowercmp(p1, p2, min);
 691         if(c != 0)
 692                 return c;
 693         /* equal, see who is shortest */
 694         if(len1 < len2)
 695                 return -1;
 696         if(len1 > len2)
 697                 return 1;
 698         return 0;
 699 }
 700
 701
 702 int
 703 dname_canon_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs)
 704 {
 705         /* like dname_lab_cmp, but with different label comparison,
 706          * empty character sorts before \000.
 707          * So   ylyly is before z. */
 708         uint8_t len1, len2;
 709         int atlabel = labs1;
 710         int lastmlabs;
 711         int lastdiff = 0;
 712         int c;
 713         /* first skip so that we compare same label. */
 714         if(labs1 > labs2) {
 715                 while(atlabel > labs2) {
 716                         len1 = *d1++;
 717                         d1 += len1;
 718                         atlabel--;
 719                 }
 720                 log_assert(atlabel == labs2);
 721         } else if(labs1 < labs2) {
 722                 atlabel = labs2;
 723                 while(atlabel > labs1) {
 724                         len2 = *d2++;
 725                         d2 += len2;
 726                         atlabel--;
 727                 }
 728                 log_assert(atlabel == labs1);
 729         }
 730         lastmlabs = atlabel+1;
 731         /* now at same label in d1 and d2, atlabel */
 732         /* www.example.com.                  */
 733         /* 4   3       2  1   atlabel number */
 734         /* repeat until at root label (which is always the same) */
 735         while(atlabel > 1) {
 736                 len1 = *d1++;
 737                 len2 = *d2++;
 738
 739                 if((c=memcanoncmp(d1, len1, d2, len2)) != 0) {
 740                         if(c<0)
 741                                 lastdiff = -1;
 742                         else    lastdiff = 1;
 743                         lastmlabs = atlabel;
 744                 }
 745
 746                 d1 += len1;
 747                 d2 += len2;
 748                 atlabel--;
 749         }
 750         /* last difference atlabel number, so number of labels matching,
 751          * at the right side, is one less. */
 752         *mlabs = lastmlabs-1;
 753         if(lastdiff == 0) {
 754                 /* all labels compared were equal, check if one has more
 755                  * labels, so that example.com. > com. */
 756                 if(labs1 > labs2)
 757                         return 1;
 758                 else if(labs1 < labs2)
 759                         return -1;
 760         }
 761         return lastdiff;
 762 }
 763
 764 int
 765 dname_canonical_compare(uint8_t* d1, uint8_t* d2)
 766 {
 767         int labs1, labs2, m;
 768         labs1 = dname_count_labels(d1);
 769         labs2 = dname_count_labels(d2);
 770         return dname_canon_lab_cmp(d1, labs1, d2, labs2, &m);
 771 }
 772
 773 uint8_t* dname_get_shared_topdomain(uint8_t* d1, uint8_t* d2)
 774 {
 775         int labs1, labs2, m;
 776         size_t len = LDNS_MAX_DOMAINLEN;
 777         labs1 = dname_count_labels(d1);
 778         labs2 = dname_count_labels(d2);
 779         (void)dname_lab_cmp(d1, labs1, d2, labs2, &m);
 780         dname_remove_labels(&d1, &len, labs1-m);
 781         return d1;
 782 }