contrib/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 "sldns/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) < tolower((unsigned char)*d2))
 261                                         return -1;
 262                                 return 1;
 263                         }
 264                         d1++;
 265                         d2++;
 266                 }
 267                 len1 = *d1++;
 268                 len2 = *d2++;
 269         }
 270         return 0;
 271 }
 272
 273 hashvalue_t
 274 dname_query_hash(uint8_t* dname, hashvalue_t h)
 275 {
 276         uint8_t labuf[LDNS_MAX_LABELLEN+1];
 277         uint8_t lablen;
 278         int i;
 279
 280         /* preserve case of query, make hash label by label */
 281         lablen = *dname++;
 282         while(lablen) {
 283                 log_assert(lablen <= LDNS_MAX_LABELLEN);
 284                 labuf[0] = lablen;
 285                 i=0;
 286                 while(lablen--) {
 287                         labuf[++i] = (uint8_t)tolower((unsigned char)*dname);
 288                         dname++;
 289                 }
 290                 h = hashlittle(labuf, labuf[0] + 1, h);
 291                 lablen = *dname++;
 292         }
 293
 294         return h;
 295 }
 296
 297 hashvalue_t
 298 dname_pkt_hash(sldns_buffer* pkt, uint8_t* dname, hashvalue_t h)
 299 {
 300         uint8_t labuf[LDNS_MAX_LABELLEN+1];
 301         uint8_t lablen;
 302         int i;
 303
 304         /* preserve case of query, make hash label by label */
 305         lablen = *dname++;
 306         while(lablen) {
 307                 if(LABEL_IS_PTR(lablen)) {
 308                         /* follow pointer */
 309                         dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
 310                         lablen = *dname++;
 311                         continue;
 312                 }
 313                 log_assert(lablen <= LDNS_MAX_LABELLEN);
 314                 labuf[0] = lablen;
 315                 i=0;
 316                 while(lablen--) {
 317                         labuf[++i] = (uint8_t)tolower((unsigned char)*dname);
 318                         dname++;
 319                 }
 320                 h = hashlittle(labuf, labuf[0] + 1, h);
 321                 lablen = *dname++;
 322         }
 323
 324         return h;
 325 }
 326
 327 void dname_pkt_copy(sldns_buffer* pkt, uint8_t* to, uint8_t* dname)
 328 {
 329         /* copy over the dname and decompress it at the same time */
 330         size_t len = 0;
 331         uint8_t lablen;
 332         lablen = *dname++;
 333         while(lablen) {
 334                 if(LABEL_IS_PTR(lablen)) {
 335                         /* follow pointer */
 336                         dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
 337                         lablen = *dname++;
 338                         continue;
 339                 }
 340                 log_assert(lablen <= LDNS_MAX_LABELLEN);
 341                 len += (size_t)lablen+1;
 342                 if(len >= LDNS_MAX_DOMAINLEN) {
 343                         *to = 0; /* end the result prematurely */
 344                         log_err("bad dname in dname_pkt_copy");
 345                         return;
 346                 }
 347                 *to++ = lablen;
 348                 memmove(to, dname, lablen);
 349                 dname += lablen;
 350                 to += lablen;
 351                 lablen = *dname++;
 352         }
 353         /* copy last \0 */
 354         *to = 0;
 355 }
 356
 357 void dname_print(FILE* out, struct sldns_buffer* pkt, uint8_t* dname)
 358 {
 359         uint8_t lablen;
 360         if(!out) out = stdout;
 361         if(!dname) return;
 362
 363         lablen = *dname++;
 364         if(!lablen)
 365                 fputc('.', out);
 366         while(lablen) {
 367                 if(LABEL_IS_PTR(lablen)) {
 368                         /* follow pointer */
 369                         if(!pkt) {
 370                                 fputs("??compressionptr??", out);
 371                                 return;
 372                         }
 373                         dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
 374                         lablen = *dname++;
 375                         continue;
 376                 }
 377                 if(lablen > LDNS_MAX_LABELLEN) {
 378                         fputs("??extendedlabel??", out);
 379                         return;
 380                 }
 381                 while(lablen--)
 382                         fputc((int)*dname++, out);
 383                 fputc('.', out);
 384                 lablen = *dname++;
 385         }
 386 }
 387
 388 int
 389 dname_count_labels(uint8_t* dname)
 390 {
 391         uint8_t lablen;
 392         int labs = 1;
 393
 394         lablen = *dname++;
 395         while(lablen) {
 396                 labs++;
 397                 dname += lablen;
 398                 lablen = *dname++;
 399         }
 400         return labs;
 401 }
 402
 403 int
 404 dname_count_size_labels(uint8_t* dname, size_t* size)
 405 {
 406         uint8_t lablen;
 407         int labs = 1;
 408         size_t sz = 1;
 409
 410         lablen = *dname++;
 411         while(lablen) {
 412                 labs++;
 413                 sz += lablen+1;
 414                 dname += lablen;
 415                 lablen = *dname++;
 416         }
 417         *size = sz;
 418         return labs;
 419 }
 420
 421 /**
 422  * Compare labels in memory, lowercase while comparing.
 423  * @param p1: label 1
 424  * @param p2: label 2
 425  * @param len: number of bytes to compare.
 426  * @return: 0, -1, +1 comparison result.
 427  */
 428 static int
 429 memlowercmp(uint8_t* p1, uint8_t* p2, uint8_t len)
 430 {
 431         while(len--) {
 432                 if(*p1 != *p2 && tolower((unsigned char)*p1) != tolower((unsigned char)*p2)) {
 433                         if(tolower((unsigned char)*p1) < tolower((unsigned char)*p2))
 434                                 return -1;
 435                         return 1;
 436                 }
 437                 p1++;
 438                 p2++;
 439         }
 440         return 0;
 441 }
 442
 443 int
 444 dname_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs)
 445 {
 446         uint8_t len1, len2;
 447         int atlabel = labs1;
 448         int lastmlabs;
 449         int lastdiff = 0;
 450         /* first skip so that we compare same label. */
 451         if(labs1 > labs2) {
 452                 while(atlabel > labs2) {
 453                         len1 = *d1++;
 454                         d1 += len1;
 455                         atlabel--;
 456                 }
 457                 log_assert(atlabel == labs2);
 458         } else if(labs1 < labs2) {
 459                 atlabel = labs2;
 460                 while(atlabel > labs1) {
 461                         len2 = *d2++;
 462                         d2 += len2;
 463                         atlabel--;
 464                 }
 465                 log_assert(atlabel == labs1);
 466         }
 467         lastmlabs = atlabel+1;
 468         /* now at same label in d1 and d2, atlabel */
 469         /* www.example.com.                  */
 470         /* 4   3       2  1   atlabel number */
 471         /* repeat until at root label (which is always the same) */
 472         while(atlabel > 1) {
 473                 len1 = *d1++;
 474                 len2 = *d2++;
 475                 if(len1 != len2) {
 476                         log_assert(len1 != 0 && len2 != 0);
 477                         if(len1<len2)
 478                                 lastdiff = -1;
 479                         else    lastdiff = 1;
 480                         lastmlabs = atlabel;
 481                         d1 += len1;
 482                         d2 += len2;
 483                 } else {
 484                         /* memlowercmp is inlined here; or just like
 485                          * if((c=memlowercmp(d1, d2, len1)) != 0) {
 486                          *      lastdiff = c;
 487                          *      lastmlabs = atlabel; } apart from d1++,d2++ */
 488                         while(len1) {
 489                                 if(*d1 != *d2 && tolower((unsigned char)*d1)
 490                                         != tolower((unsigned char)*d2)) {
 491                                         if(tolower((unsigned char)*d1) <
 492                                                 tolower((unsigned char)*d2)) {
 493                                                 lastdiff = -1;
 494                                                 lastmlabs = atlabel;
 495                                                 d1 += len1;
 496                                                 d2 += len1;
 497                                                 break;
 498                                         }
 499                                         lastdiff = 1;
 500                                         lastmlabs = atlabel;
 501                                         d1 += len1;
 502                                         d2 += len1;
 503                                         break; /* out of memlowercmp */
 504                                 }
 505                                 d1++;
 506                                 d2++;
 507                                 len1--;
 508                         }
 509                 }
 510                 atlabel--;
 511         }
 512         /* last difference atlabel number, so number of labels matching,
 513          * at the right side, is one less. */
 514         *mlabs = lastmlabs-1;
 515         if(lastdiff == 0) {
 516                 /* all labels compared were equal, check if one has more
 517                  * labels, so that example.com. > com. */
 518                 if(labs1 > labs2)
 519                         return 1;
 520                 else if(labs1 < labs2)
 521                         return -1;
 522         }
 523         return lastdiff;
 524 }
 525
 526 int
 527 dname_buffer_write(sldns_buffer* pkt, uint8_t* dname)
 528 {
 529         uint8_t lablen;
 530
 531         if(sldns_buffer_remaining(pkt) < 1)
 532                 return 0;
 533         lablen = *dname++;
 534         sldns_buffer_write_u8(pkt, lablen);
 535         while(lablen) {
 536                 if(sldns_buffer_remaining(pkt) < (size_t)lablen+1)
 537                         return 0;
 538                 sldns_buffer_write(pkt, dname, lablen);
 539                 dname += lablen;
 540                 lablen = *dname++;
 541                 sldns_buffer_write_u8(pkt, lablen);
 542         }
 543         return 1;
 544 }
 545
 546 void dname_str(uint8_t* dname, char* str)
 547 {
 548         size_t len = 0;
 549         uint8_t lablen = 0;
 550         char* s = str;
 551         if(!dname || !*dname) {
 552                 *s++ = '.';
 553                 *s = 0;
 554                 return;
 555         }
 556         lablen = *dname++;
 557         while(lablen) {
 558                 if(lablen > LDNS_MAX_LABELLEN) {
 559                         *s++ = '#';
 560                         *s = 0;
 561                         return;
 562                 }
 563                 len += lablen+1;
 564                 if(len >= LDNS_MAX_DOMAINLEN-1) {
 565                         *s++ = '&';
 566                         *s = 0;
 567                         return;
 568                 }
 569                 while(lablen--) {
 570                         if(isalnum((unsigned char)*dname)
 571                                 || *dname == '-' || *dname == '_'
 572                                 || *dname == '*')
 573                                 *s++ = *(char*)dname++;
 574                         else    {
 575                                 *s++ = '?';
 576                                 dname++;
 577                         }
 578                 }
 579                 *s++ = '.';
 580                 lablen = *dname++;
 581         }
 582         *s = 0;
 583 }
 584
 585 int
 586 dname_strict_subdomain(uint8_t* d1, int labs1, uint8_t* d2, int labs2)
 587 {
 588         int m;
 589         /* check subdomain: d1: www.example.com. and d2: example.com. */
 590         if(labs2 >= labs1)
 591                 return 0;
 592         if(dname_lab_cmp(d1, labs1, d2, labs2, &m) > 0) {
 593                 /* subdomain if all labels match */
 594                 return (m == labs2);
 595         }
 596         return 0;
 597 }
 598
 599 int
 600 dname_strict_subdomain_c(uint8_t* d1, uint8_t* d2)
 601 {
 602         return dname_strict_subdomain(d1, dname_count_labels(d1), d2,
 603                 dname_count_labels(d2));
 604 }
 605
 606 int
 607 dname_subdomain_c(uint8_t* d1, uint8_t* d2)
 608 {
 609         int m;
 610         /* check subdomain: d1: www.example.com. and d2: example.com. */
 611         /*      or          d1: example.com. and d2: example.com. */
 612         int labs1 = dname_count_labels(d1);
 613         int labs2 = dname_count_labels(d2);
 614         if(labs2 > labs1)
 615                 return 0;
 616         if(dname_lab_cmp(d1, labs1, d2, labs2, &m) < 0) {
 617                 /* must have been example.com , www.example.com - wrong */
 618                 /* or otherwise different dnames */
 619                 return 0;
 620         }
 621         return (m == labs2);
 622 }
 623
 624 int
 625 dname_is_root(uint8_t* dname)
 626 {
 627         uint8_t len;
 628         log_assert(dname);
 629         len = dname[0];
 630         log_assert(!LABEL_IS_PTR(len));
 631         return (len == 0);
 632 }
 633
 634 void
 635 dname_remove_label(uint8_t** dname, size_t* len)
 636 {
 637         size_t lablen;
 638         log_assert(dname && *dname && len);
 639         lablen = (*dname)[0];
 640         log_assert(!LABEL_IS_PTR(lablen));
 641         log_assert(*len > lablen);
 642         if(lablen == 0)
 643                 return; /* do not modify root label */
 644         *len -= lablen+1;
 645         *dname += lablen+1;
 646 }
 647
 648 void
 649 dname_remove_labels(uint8_t** dname, size_t* len, int n)
 650 {
 651         int i;
 652         for(i=0; i<n; i++)
 653                 dname_remove_label(dname, len);
 654 }
 655
 656 int
 657 dname_signame_label_count(uint8_t* dname)
 658 {
 659         uint8_t lablen;
 660         int count = 0;
 661         if(!*dname)
 662                 return 0;
 663         if(dname[0] == 1 && dname[1] == '*')
 664                 dname += 2;
 665         lablen = dname[0];
 666         while(lablen) {
 667                 count++;
 668                 dname += lablen;
 669                 dname += 1;
 670                 lablen = dname[0];
 671         }
 672         return count;
 673 }
 674
 675 int
 676 dname_is_wild(uint8_t* dname)
 677 {
 678         return (dname[0] == 1 && dname[1] == '*');
 679 }
 680
 681 /**
 682  * Compare labels in memory, lowercase while comparing.
 683  * Returns canonical order for labels. If all is equal, the
 684  * shortest is first.
 685  *
 686  * @param p1: label 1
 687  * @param len1: length of label 1.
 688  * @param p2: label 2
 689  * @param len2: length of label 2.
 690  * @return: 0, -1, +1 comparison result.
 691  */
 692 static int
 693 memcanoncmp(uint8_t* p1, uint8_t len1, uint8_t* p2, uint8_t len2)
 694 {
 695         uint8_t min = (len1<len2)?len1:len2;
 696         int c = memlowercmp(p1, p2, min);
 697         if(c != 0)
 698                 return c;
 699         /* equal, see who is shortest */
 700         if(len1 < len2)
 701                 return -1;
 702         if(len1 > len2)
 703                 return 1;
 704         return 0;
 705 }
 706
 707
 708 int
 709 dname_canon_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs)
 710 {
 711         /* like dname_lab_cmp, but with different label comparison,
 712          * empty character sorts before \000.
 713          * So   ylyly is before z. */
 714         uint8_t len1, len2;
 715         int atlabel = labs1;
 716         int lastmlabs;
 717         int lastdiff = 0;
 718         int c;
 719         /* first skip so that we compare same label. */
 720         if(labs1 > labs2) {
 721                 while(atlabel > labs2) {
 722                         len1 = *d1++;
 723                         d1 += len1;
 724                         atlabel--;
 725                 }
 726                 log_assert(atlabel == labs2);
 727         } else if(labs1 < labs2) {
 728                 atlabel = labs2;
 729                 while(atlabel > labs1) {
 730                         len2 = *d2++;
 731                         d2 += len2;
 732                         atlabel--;
 733                 }
 734                 log_assert(atlabel == labs1);
 735         }
 736         lastmlabs = atlabel+1;
 737         /* now at same label in d1 and d2, atlabel */
 738         /* www.example.com.                  */
 739         /* 4   3       2  1   atlabel number */
 740         /* repeat until at root label (which is always the same) */
 741         while(atlabel > 1) {
 742                 len1 = *d1++;
 743                 len2 = *d2++;
 744
 745                 if((c=memcanoncmp(d1, len1, d2, len2)) != 0) {
 746                         if(c<0)
 747                                 lastdiff = -1;
 748                         else    lastdiff = 1;
 749                         lastmlabs = atlabel;
 750                 }
 751
 752                 d1 += len1;
 753                 d2 += len2;
 754                 atlabel--;
 755         }
 756         /* last difference atlabel number, so number of labels matching,
 757          * at the right side, is one less. */
 758         *mlabs = lastmlabs-1;
 759         if(lastdiff == 0) {
 760                 /* all labels compared were equal, check if one has more
 761                  * labels, so that example.com. > com. */
 762                 if(labs1 > labs2)
 763                         return 1;
 764                 else if(labs1 < labs2)
 765                         return -1;
 766         }
 767         return lastdiff;
 768 }
 769
 770 int
 771 dname_canonical_compare(uint8_t* d1, uint8_t* d2)
 772 {
 773         int labs1, labs2, m;
 774         labs1 = dname_count_labels(d1);
 775         labs2 = dname_count_labels(d2);
 776         return dname_canon_lab_cmp(d1, labs1, d2, labs2, &m);
 777 }
 778
 779 uint8_t* dname_get_shared_topdomain(uint8_t* d1, uint8_t* d2)
 780 {
 781         int labs1, labs2, m;
 782         size_t len = LDNS_MAX_DOMAINLEN;
 783         labs1 = dname_count_labels(d1);
 784         labs2 = dname_count_labels(d2);
 785         (void)dname_lab_cmp(d1, labs1, d2, labs2, &m);
 786         dname_remove_labels(&d1, &len, labs1-m);
 787         return d1;
 788 }