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_type
 274 dname_query_hash(uint8_t* dname, hashvalue_type 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_type
 298 dname_pkt_hash(sldns_buffer* pkt, uint8_t* dname, hashvalue_type 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_lab_startswith(uint8_t* label, char* prefix, char** endptr)
 528 {
 529         size_t plen = strlen(prefix);
 530         size_t orig_plen = plen;
 531         size_t lablen = (size_t)*label;
 532         if(plen > lablen)
 533                 return 0;
 534         label++;
 535         while(plen--) {
 536                 if(*prefix != tolower((unsigned char)*label)) {
 537                         return 0;
 538                 }
 539                 prefix++; label++;
 540         }
 541         if(orig_plen < lablen)
 542                 *endptr = (char *)label;
 543         else
 544                 /* prefix length == label length */
 545                 *endptr = NULL;
 546         return 1;
 547 }
 548
 549 int
 550 dname_buffer_write(sldns_buffer* pkt, uint8_t* dname)
 551 {
 552         uint8_t lablen;
 553
 554         if(sldns_buffer_remaining(pkt) < 1)
 555                 return 0;
 556         lablen = *dname++;
 557         sldns_buffer_write_u8(pkt, lablen);
 558         while(lablen) {
 559                 if(sldns_buffer_remaining(pkt) < (size_t)lablen+1)
 560                         return 0;
 561                 sldns_buffer_write(pkt, dname, lablen);
 562                 dname += lablen;
 563                 lablen = *dname++;
 564                 sldns_buffer_write_u8(pkt, lablen);
 565         }
 566         return 1;
 567 }
 568
 569 void dname_str(uint8_t* dname, char* str)
 570 {
 571         size_t len = 0;
 572         uint8_t lablen = 0;
 573         char* s = str;
 574         if(!dname || !*dname) {
 575                 *s++ = '.';
 576                 *s = 0;
 577                 return;
 578         }
 579         lablen = *dname++;
 580         while(lablen) {
 581                 if(lablen > LDNS_MAX_LABELLEN) {
 582                         *s++ = '#';
 583                         *s = 0;
 584                         return;
 585                 }
 586                 len += lablen+1;
 587                 if(len >= LDNS_MAX_DOMAINLEN-1) {
 588                         *s++ = '&';
 589                         *s = 0;
 590                         return;
 591                 }
 592                 while(lablen--) {
 593                         if(isalnum((unsigned char)*dname)
 594                                 || *dname == '-' || *dname == '_'
 595                                 || *dname == '*')
 596                                 *s++ = *(char*)dname++;
 597                         else    {
 598                                 *s++ = '?';
 599                                 dname++;
 600                         }
 601                 }
 602                 *s++ = '.';
 603                 lablen = *dname++;
 604         }
 605         *s = 0;
 606 }
 607
 608 int
 609 dname_strict_subdomain(uint8_t* d1, int labs1, uint8_t* d2, int labs2)
 610 {
 611         int m;
 612         /* check subdomain: d1: www.example.com. and d2: example.com. */
 613         if(labs2 >= labs1)
 614                 return 0;
 615         if(dname_lab_cmp(d1, labs1, d2, labs2, &m) > 0) {
 616                 /* subdomain if all labels match */
 617                 return (m == labs2);
 618         }
 619         return 0;
 620 }
 621
 622 int
 623 dname_strict_subdomain_c(uint8_t* d1, uint8_t* d2)
 624 {
 625         return dname_strict_subdomain(d1, dname_count_labels(d1), d2,
 626                 dname_count_labels(d2));
 627 }
 628
 629 int
 630 dname_subdomain_c(uint8_t* d1, uint8_t* d2)
 631 {
 632         int m;
 633         /* check subdomain: d1: www.example.com. and d2: example.com. */
 634         /*      or          d1: example.com. and d2: example.com. */
 635         int labs1 = dname_count_labels(d1);
 636         int labs2 = dname_count_labels(d2);
 637         if(labs2 > labs1)
 638                 return 0;
 639         if(dname_lab_cmp(d1, labs1, d2, labs2, &m) < 0) {
 640                 /* must have been example.com , www.example.com - wrong */
 641                 /* or otherwise different dnames */
 642                 return 0;
 643         }
 644         return (m == labs2);
 645 }
 646
 647 int
 648 dname_is_root(uint8_t* dname)
 649 {
 650         uint8_t len;
 651         log_assert(dname);
 652         len = dname[0];
 653         log_assert(!LABEL_IS_PTR(len));
 654         return (len == 0);
 655 }
 656
 657 void
 658 dname_remove_label(uint8_t** dname, size_t* len)
 659 {
 660         size_t lablen;
 661         log_assert(dname && *dname && len);
 662         lablen = (*dname)[0];
 663         log_assert(!LABEL_IS_PTR(lablen));
 664         log_assert(*len > lablen);
 665         if(lablen == 0)
 666                 return; /* do not modify root label */
 667         *len -= lablen+1;
 668         *dname += lablen+1;
 669 }
 670
 671 void
 672 dname_remove_labels(uint8_t** dname, size_t* len, int n)
 673 {
 674         int i;
 675         for(i=0; i<n; i++)
 676                 dname_remove_label(dname, len);
 677 }
 678
 679 int
 680 dname_signame_label_count(uint8_t* dname)
 681 {
 682         uint8_t lablen;
 683         int count = 0;
 684         if(!*dname)
 685                 return 0;
 686         if(dname[0] == 1 && dname[1] == '*')
 687                 dname += 2;
 688         lablen = dname[0];
 689         while(lablen) {
 690                 count++;
 691                 dname += lablen;
 692                 dname += 1;
 693                 lablen = dname[0];
 694         }
 695         return count;
 696 }
 697
 698 int
 699 dname_is_wild(uint8_t* dname)
 700 {
 701         return (dname[0] == 1 && dname[1] == '*');
 702 }
 703
 704 /**
 705  * Compare labels in memory, lowercase while comparing.
 706  * Returns canonical order for labels. If all is equal, the
 707  * shortest is first.
 708  *
 709  * @param p1: label 1
 710  * @param len1: length of label 1.
 711  * @param p2: label 2
 712  * @param len2: length of label 2.
 713  * @return: 0, -1, +1 comparison result.
 714  */
 715 static int
 716 memcanoncmp(uint8_t* p1, uint8_t len1, uint8_t* p2, uint8_t len2)
 717 {
 718         uint8_t min = (len1<len2)?len1:len2;
 719         int c = memlowercmp(p1, p2, min);
 720         if(c != 0)
 721                 return c;
 722         /* equal, see who is shortest */
 723         if(len1 < len2)
 724                 return -1;
 725         if(len1 > len2)
 726                 return 1;
 727         return 0;
 728 }
 729
 730
 731 int
 732 dname_canon_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs)
 733 {
 734         /* like dname_lab_cmp, but with different label comparison,
 735          * empty character sorts before \000.
 736          * So   ylyly is before z. */
 737         uint8_t len1, len2;
 738         int atlabel = labs1;
 739         int lastmlabs;
 740         int lastdiff = 0;
 741         int c;
 742         /* first skip so that we compare same label. */
 743         if(labs1 > labs2) {
 744                 while(atlabel > labs2) {
 745                         len1 = *d1++;
 746                         d1 += len1;
 747                         atlabel--;
 748                 }
 749                 log_assert(atlabel == labs2);
 750         } else if(labs1 < labs2) {
 751                 atlabel = labs2;
 752                 while(atlabel > labs1) {
 753                         len2 = *d2++;
 754                         d2 += len2;
 755                         atlabel--;
 756                 }
 757                 log_assert(atlabel == labs1);
 758         }
 759         lastmlabs = atlabel+1;
 760         /* now at same label in d1 and d2, atlabel */
 761         /* www.example.com.                  */
 762         /* 4   3       2  1   atlabel number */
 763         /* repeat until at root label (which is always the same) */
 764         while(atlabel > 1) {
 765                 len1 = *d1++;
 766                 len2 = *d2++;
 767
 768                 if((c=memcanoncmp(d1, len1, d2, len2)) != 0) {
 769                         if(c<0)
 770                                 lastdiff = -1;
 771                         else    lastdiff = 1;
 772                         lastmlabs = atlabel;
 773                 }
 774
 775                 d1 += len1;
 776                 d2 += len2;
 777                 atlabel--;
 778         }
 779         /* last difference atlabel number, so number of labels matching,
 780          * at the right side, is one less. */
 781         *mlabs = lastmlabs-1;
 782         if(lastdiff == 0) {
 783                 /* all labels compared were equal, check if one has more
 784                  * labels, so that example.com. > com. */
 785                 if(labs1 > labs2)
 786                         return 1;
 787                 else if(labs1 < labs2)
 788                         return -1;
 789         }
 790         return lastdiff;
 791 }
 792
 793 int
 794 dname_canonical_compare(uint8_t* d1, uint8_t* d2)
 795 {
 796         int labs1, labs2, m;
 797         labs1 = dname_count_labels(d1);
 798         labs2 = dname_count_labels(d2);
 799         return dname_canon_lab_cmp(d1, labs1, d2, labs2, &m);
 800 }
 801
 802 uint8_t* dname_get_shared_topdomain(uint8_t* d1, uint8_t* d2)
 803 {
 804         int labs1, labs2, m;
 805         size_t len = LDNS_MAX_DOMAINLEN;
 806         labs1 = dname_count_labels(d1);
 807         labs2 = dname_count_labels(d2);
 808         (void)dname_lab_cmp(d1, labs1, d2, labs2, &m);
 809         dname_remove_labels(&d1, &len, labs1-m);
 810         return d1;
 811 }