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 */
51size_t
52query_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
73size_t
74dname_valid(uint8_t* dname, size_t maxlen)
75{
76	size_t len = 0;
77	size_t labellen;
78	if(maxlen == 0)
79		return 0; /* too short, shortest is '0' root label */
80	labellen = *dname++;
81	while(labellen) {
82		if(labellen&0xc0)
83			return 0; /* no compression ptrs allowed */
84		len += labellen + 1;
85		if(len >= LDNS_MAX_DOMAINLEN)
86			return 0; /* too long */
87		if(len > maxlen)
88			return 0; /* does not fit in memory allocation */
89		dname += labellen;
90		labellen = *dname++;
91	}
92	len += 1;
93	if(len > maxlen)
94		return 0; /* does not fit in memory allocation */
95	return len;
96}
97
98/** compare uncompressed, noncanonical, registers are hints for speed */
99int
100query_dname_compare(register uint8_t* d1, register uint8_t* d2)
101{
102	register uint8_t lab1, lab2;
103	log_assert(d1 && d2);
104	lab1 = *d1++;
105	lab2 = *d2++;
106	while( lab1 != 0 || lab2 != 0 ) {
107		/* compare label length */
108		/* if one dname ends, it has labellength 0 */
109		if(lab1 != lab2) {
110			if(lab1 < lab2)
111				return -1;
112			return 1;
113		}
114		log_assert(lab1 == lab2 && lab1 != 0);
115		/* compare lowercased labels. */
116		while(lab1--) {
117			/* compare bytes first for speed */
118			if(*d1 != *d2 &&
119				tolower((unsigned char)*d1) != tolower((unsigned char)*d2)) {
120				if(tolower((unsigned char)*d1) < tolower((unsigned char)*d2))
121					return -1;
122				return 1;
123			}
124			d1++;
125			d2++;
126		}
127		/* next pair of labels. */
128		lab1 = *d1++;
129		lab2 = *d2++;
130	}
131	return 0;
132}
133
134void
135query_dname_tolower(uint8_t* dname)
136{
137	/* the dname is stored uncompressed */
138	uint8_t labellen;
139	labellen = *dname;
140	while(labellen) {
141		dname++;
142		while(labellen--) {
143			*dname = (uint8_t)tolower((unsigned char)*dname);
144			dname++;
145		}
146		labellen = *dname;
147	}
148}
149
150void
151pkt_dname_tolower(sldns_buffer* pkt, uint8_t* dname)
152{
153	uint8_t lablen;
154	int count = 0;
155	if(dname >= sldns_buffer_end(pkt))
156		return;
157	lablen = *dname++;
158	while(lablen) {
159		if(LABEL_IS_PTR(lablen)) {
160			if((size_t)PTR_OFFSET(lablen, *dname)
161				>= sldns_buffer_limit(pkt))
162				return;
163			dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
164			lablen = *dname++;
165			if(count++ > MAX_COMPRESS_PTRS)
166				return;
167			continue;
168		}
169		if(dname+lablen >= sldns_buffer_end(pkt))
170			return;
171		while(lablen--) {
172			*dname = (uint8_t)tolower((unsigned char)*dname);
173			dname++;
174		}
175		if(dname >= sldns_buffer_end(pkt))
176			return;
177		lablen = *dname++;
178	}
179}
180
181
182size_t
183pkt_dname_len(sldns_buffer* pkt)
184{
185	size_t len = 0;
186	int ptrcount = 0;
187	uint8_t labellen;
188	size_t endpos = 0;
189
190	/* read dname and determine length */
191	/* check compression pointers, loops, out of bounds */
192	while(1) {
193		/* read next label */
194		if(sldns_buffer_remaining(pkt) < 1)
195			return 0;
196		labellen = sldns_buffer_read_u8(pkt);
197		if(LABEL_IS_PTR(labellen)) {
198			/* compression ptr */
199			uint16_t ptr;
200			if(sldns_buffer_remaining(pkt) < 1)
201				return 0;
202			ptr = PTR_OFFSET(labellen, sldns_buffer_read_u8(pkt));
203			if(ptrcount++ > MAX_COMPRESS_PTRS)
204				return 0; /* loop! */
205			if(sldns_buffer_limit(pkt) <= ptr)
206				return 0; /* out of bounds! */
207			if(!endpos)
208				endpos = sldns_buffer_position(pkt);
209			sldns_buffer_set_position(pkt, ptr);
210		} else {
211			/* label contents */
212			if(labellen > 0x3f)
213				return 0; /* label too long */
214			len += 1 + labellen;
215			if(len > LDNS_MAX_DOMAINLEN)
216				return 0;
217			if(labellen == 0) {
218				/* end of dname */
219				break;
220			}
221			if(sldns_buffer_remaining(pkt) < labellen)
222				return 0;
223			sldns_buffer_skip(pkt, (ssize_t)labellen);
224		}
225	}
226	if(endpos)
227		sldns_buffer_set_position(pkt, endpos);
228
229	return len;
230}
231
232int
233dname_pkt_compare(sldns_buffer* pkt, uint8_t* d1, uint8_t* d2)
234{
235	uint8_t len1, len2;
236	int count1 = 0, count2 = 0;
237	log_assert(pkt && d1 && d2);
238	len1 = *d1++;
239	len2 = *d2++;
240	while( len1 != 0 || len2 != 0 ) {
241		/* resolve ptrs */
242		if(LABEL_IS_PTR(len1)) {
243			if((size_t)PTR_OFFSET(len1, *d1)
244				>= sldns_buffer_limit(pkt))
245				return -1;
246			if(count1++ > MAX_COMPRESS_PTRS)
247				return -1;
248			d1 = sldns_buffer_at(pkt, PTR_OFFSET(len1, *d1));
249			len1 = *d1++;
250			continue;
251		}
252		if(LABEL_IS_PTR(len2)) {
253			if((size_t)PTR_OFFSET(len2, *d2)
254				>= sldns_buffer_limit(pkt))
255				return 1;
256			if(count2++ > MAX_COMPRESS_PTRS)
257				return 1;
258			d2 = sldns_buffer_at(pkt, PTR_OFFSET(len2, *d2));
259			len2 = *d2++;
260			continue;
261		}
262		/* check label length */
263		log_assert(len1 <= LDNS_MAX_LABELLEN);
264		log_assert(len2 <= LDNS_MAX_LABELLEN);
265		if(len1 != len2) {
266			if(len1 < len2) return -1;
267			return 1;
268		}
269		log_assert(len1 == len2 && len1 != 0);
270		/* compare labels */
271		while(len1--) {
272			if(tolower((unsigned char)*d1) != tolower((unsigned char)*d2)) {
273				if(tolower((unsigned char)*d1) < tolower((unsigned char)*d2))
274					return -1;
275				return 1;
276			}
277			d1++;
278			d2++;
279		}
280		len1 = *d1++;
281		len2 = *d2++;
282	}
283	return 0;
284}
285
286hashvalue_type
287dname_query_hash(uint8_t* dname, hashvalue_type h)
288{
289	uint8_t labuf[LDNS_MAX_LABELLEN+1];
290	uint8_t lablen;
291	int i;
292
293	/* preserve case of query, make hash label by label */
294	lablen = *dname++;
295	while(lablen) {
296		log_assert(lablen <= LDNS_MAX_LABELLEN);
297		labuf[0] = lablen;
298		i=0;
299		while(lablen--) {
300			labuf[++i] = (uint8_t)tolower((unsigned char)*dname);
301			dname++;
302		}
303		h = hashlittle(labuf, labuf[0] + 1, h);
304		lablen = *dname++;
305	}
306
307	return h;
308}
309
310hashvalue_type
311dname_pkt_hash(sldns_buffer* pkt, uint8_t* dname, hashvalue_type h)
312{
313	uint8_t labuf[LDNS_MAX_LABELLEN+1];
314	uint8_t lablen;
315	int i;
316	int count = 0;
317
318	/* preserve case of query, make hash label by label */
319	lablen = *dname++;
320	while(lablen) {
321		if(LABEL_IS_PTR(lablen)) {
322			/* follow pointer */
323			if((size_t)PTR_OFFSET(lablen, *dname)
324				>= sldns_buffer_limit(pkt))
325				return h;
326			if(count++ > MAX_COMPRESS_PTRS)
327				return h;
328			dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
329			lablen = *dname++;
330			continue;
331		}
332		log_assert(lablen <= LDNS_MAX_LABELLEN);
333		labuf[0] = lablen;
334		i=0;
335		while(lablen--) {
336			labuf[++i] = (uint8_t)tolower((unsigned char)*dname);
337			dname++;
338		}
339		h = hashlittle(labuf, labuf[0] + 1, h);
340		lablen = *dname++;
341	}
342
343	return h;
344}
345
346void dname_pkt_copy(sldns_buffer* pkt, uint8_t* to, uint8_t* dname)
347{
348	/* copy over the dname and decompress it at the same time */
349	size_t comprcount = 0;
350	size_t len = 0;
351	uint8_t lablen;
352	lablen = *dname++;
353	while(lablen) {
354		if(LABEL_IS_PTR(lablen)) {
355			if(comprcount++ > MAX_COMPRESS_PTRS) {
356				/* too many compression pointers */
357				*to = 0; /* end the result prematurely */
358				return;
359			}
360			/* follow pointer */
361			if((size_t)PTR_OFFSET(lablen, *dname)
362				>= sldns_buffer_limit(pkt))
363				return;
364			dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
365			lablen = *dname++;
366			continue;
367		}
368		if(lablen > LDNS_MAX_LABELLEN) {
369			*to = 0; /* end the result prematurely */
370			return;
371		}
372		log_assert(lablen <= LDNS_MAX_LABELLEN);
373		len += (size_t)lablen+1;
374		if(len >= LDNS_MAX_DOMAINLEN) {
375			*to = 0; /* end the result prematurely */
376			log_err("bad dname in dname_pkt_copy");
377			return;
378		}
379		*to++ = lablen;
380		memmove(to, dname, lablen);
381		dname += lablen;
382		to += lablen;
383		lablen = *dname++;
384	}
385	/* copy last \0 */
386	*to = 0;
387}
388
389void dname_print(FILE* out, struct sldns_buffer* pkt, uint8_t* dname)
390{
391	uint8_t lablen;
392	int count = 0;
393	if(!out) out = stdout;
394	if(!dname) return;
395
396	lablen = *dname++;
397	if(!lablen)
398		fputc('.', out);
399	while(lablen) {
400		if(LABEL_IS_PTR(lablen)) {
401			/* follow pointer */
402			if(!pkt) {
403				fputs("??compressionptr??", out);
404				return;
405			}
406			if((size_t)PTR_OFFSET(lablen, *dname)
407				>= sldns_buffer_limit(pkt)) {
408				fputs("??compressionptr??", out);
409				return;
410			}
411			if(count++ > MAX_COMPRESS_PTRS) {
412				fputs("??compressionptr??", out);
413				return;
414			}
415			dname = sldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname));
416			lablen = *dname++;
417			continue;
418		}
419		if(lablen > LDNS_MAX_LABELLEN) {
420			fputs("??extendedlabel??", out);
421			return;
422		}
423		while(lablen--)
424			fputc((int)*dname++, out);
425		fputc('.', out);
426		lablen = *dname++;
427	}
428}
429
430int
431dname_count_labels(uint8_t* dname)
432{
433	uint8_t lablen;
434	int labs = 1;
435
436	lablen = *dname++;
437	while(lablen) {
438		labs++;
439		dname += lablen;
440		lablen = *dname++;
441	}
442	return labs;
443}
444
445int
446dname_count_size_labels(uint8_t* dname, size_t* size)
447{
448	uint8_t lablen;
449	int labs = 1;
450	size_t sz = 1;
451
452	lablen = *dname++;
453	while(lablen) {
454		labs++;
455		sz += lablen+1;
456		dname += lablen;
457		lablen = *dname++;
458	}
459	*size = sz;
460	return labs;
461}
462
463/**
464 * Compare labels in memory, lowercase while comparing.
465 * @param p1: label 1
466 * @param p2: label 2
467 * @param len: number of bytes to compare.
468 * @return: 0, -1, +1 comparison result.
469 */
470static int
471memlowercmp(uint8_t* p1, uint8_t* p2, uint8_t len)
472{
473	while(len--) {
474		if(*p1 != *p2 && tolower((unsigned char)*p1) != tolower((unsigned char)*p2)) {
475			if(tolower((unsigned char)*p1) < tolower((unsigned char)*p2))
476				return -1;
477			return 1;
478		}
479		p1++;
480		p2++;
481	}
482	return 0;
483}
484
485int
486dname_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs)
487{
488	uint8_t len1, len2;
489	int atlabel = labs1;
490	int lastmlabs;
491	int lastdiff = 0;
492	/* first skip so that we compare same label. */
493	if(labs1 > labs2) {
494		while(atlabel > labs2) {
495			len1 = *d1++;
496			d1 += len1;
497			atlabel--;
498		}
499		log_assert(atlabel == labs2);
500	} else if(labs1 < labs2) {
501		atlabel = labs2;
502		while(atlabel > labs1) {
503			len2 = *d2++;
504			d2 += len2;
505			atlabel--;
506		}
507		log_assert(atlabel == labs1);
508	}
509	lastmlabs = atlabel+1;
510	/* now at same label in d1 and d2, atlabel */
511	/* www.example.com.                  */
512	/* 4   3       2  1   atlabel number */
513	/* repeat until at root label (which is always the same) */
514	while(atlabel > 1) {
515		len1 = *d1++;
516		len2 = *d2++;
517		if(len1 != len2) {
518			log_assert(len1 != 0 && len2 != 0);
519			if(len1<len2)
520				lastdiff = -1;
521			else	lastdiff = 1;
522			lastmlabs = atlabel;
523			d1 += len1;
524			d2 += len2;
525		} else {
526			/* memlowercmp is inlined here; or just like
527			 * if((c=memlowercmp(d1, d2, len1)) != 0) {
528			 *	lastdiff = c;
529			 *	lastmlabs = atlabel; } apart from d1++,d2++ */
530			while(len1) {
531				if(*d1 != *d2 && tolower((unsigned char)*d1)
532					!= tolower((unsigned char)*d2)) {
533					if(tolower((unsigned char)*d1) <
534						tolower((unsigned char)*d2)) {
535						lastdiff = -1;
536						lastmlabs = atlabel;
537						d1 += len1;
538						d2 += len1;
539						break;
540					}
541					lastdiff = 1;
542					lastmlabs = atlabel;
543					d1 += len1;
544					d2 += len1;
545					break; /* out of memlowercmp */
546				}
547				d1++;
548				d2++;
549				len1--;
550			}
551		}
552		atlabel--;
553	}
554	/* last difference atlabel number, so number of labels matching,
555	 * at the right side, is one less. */
556	*mlabs = lastmlabs-1;
557	if(lastdiff == 0) {
558		/* all labels compared were equal, check if one has more
559		 * labels, so that example.com. > com. */
560		if(labs1 > labs2)
561			return 1;
562		else if(labs1 < labs2)
563			return -1;
564	}
565	return lastdiff;
566}
567
568int
569dname_lab_startswith(uint8_t* label, char* prefix, char** endptr)
570{
571	size_t plen = strlen(prefix);
572	size_t orig_plen = plen;
573	size_t lablen = (size_t)*label;
574	if(plen > lablen)
575		return 0;
576	label++;
577	while(plen--) {
578		if(*prefix != tolower((unsigned char)*label)) {
579			return 0;
580		}
581		prefix++; label++;
582	}
583	if(orig_plen < lablen)
584		*endptr = (char *)label;
585	else
586		/* prefix length == label length */
587		*endptr = NULL;
588	return 1;
589}
590
591int
592dname_has_label(uint8_t* dname, size_t dnamelen, uint8_t* label)
593{
594	size_t len;
595
596	/* 1 byte needed for the label length */
597	if(dnamelen < 1)
598		return 0;
599
600	len = *dname;
601	while(len <= dnamelen) {
602		if(!(*dname)) {
603			if(*dname == *label)
604				return 1; /* empty label match */
605			/* termination label found, stop iterating */
606			return 0;
607		}
608		if(*dname == *label && *label &&
609			memlowercmp(dname+1, label+1, *dname) == 0)
610			return 1;
611		len += *dname;
612		dname += *dname;
613		dname++;
614		len++;
615	}
616	return 0;
617}
618
619int
620dname_buffer_write(sldns_buffer* pkt, uint8_t* dname)
621{
622	uint8_t lablen;
623
624	if(sldns_buffer_remaining(pkt) < 1)
625		return 0;
626	lablen = *dname++;
627	sldns_buffer_write_u8(pkt, lablen);
628	while(lablen) {
629		if(sldns_buffer_remaining(pkt) < (size_t)lablen+1)
630			return 0;
631		sldns_buffer_write(pkt, dname, lablen);
632		dname += lablen;
633		lablen = *dname++;
634		sldns_buffer_write_u8(pkt, lablen);
635	}
636	return 1;
637}
638
639void dname_str(uint8_t* dname, char* str)
640{
641	size_t len = 0;
642	uint8_t lablen = 0;
643	char* s = str;
644	if(!dname || !*dname) {
645		*s++ = '.';
646		*s = 0;
647		return;
648	}
649	lablen = *dname++;
650	while(lablen) {
651		if(lablen > LDNS_MAX_LABELLEN) {
652			*s++ = '#';
653			*s = 0;
654			return;
655		}
656		len += lablen+1;
657		if(len >= LDNS_MAX_DOMAINLEN-1) {
658			*s++ = '&';
659			*s = 0;
660			return;
661		}
662		while(lablen--) {
663			if(isalnum((unsigned char)*dname)
664				|| *dname == '-' || *dname == '_'
665				|| *dname == '*')
666				*s++ = *(char*)dname++;
667			else	{
668				*s++ = '?';
669				dname++;
670			}
671		}
672		*s++ = '.';
673		lablen = *dname++;
674	}
675	*s = 0;
676}
677
678int
679dname_strict_subdomain(uint8_t* d1, int labs1, uint8_t* d2, int labs2)
680{
681	int m;
682	/* check subdomain: d1: www.example.com. and d2: example.com. */
683	if(labs2 >= labs1)
684		return 0;
685	if(dname_lab_cmp(d1, labs1, d2, labs2, &m) > 0) {
686		/* subdomain if all labels match */
687		return (m == labs2);
688	}
689	return 0;
690}
691
692int
693dname_strict_subdomain_c(uint8_t* d1, uint8_t* d2)
694{
695	return dname_strict_subdomain(d1, dname_count_labels(d1), d2,
696		dname_count_labels(d2));
697}
698
699int
700dname_subdomain_c(uint8_t* d1, uint8_t* d2)
701{
702	int m;
703	/* check subdomain: d1: www.example.com. and d2: example.com. */
704	/*  	or 	    d1: example.com. and d2: example.com. */
705	int labs1 = dname_count_labels(d1);
706	int labs2 = dname_count_labels(d2);
707	if(labs2 > labs1)
708		return 0;
709	if(dname_lab_cmp(d1, labs1, d2, labs2, &m) < 0) {
710		/* must have been example.com , www.example.com - wrong */
711		/* or otherwise different dnames */
712		return 0;
713	}
714	return (m == labs2);
715}
716
717int
718dname_is_root(uint8_t* dname)
719{
720	uint8_t len;
721	log_assert(dname);
722	len = dname[0];
723	log_assert(!LABEL_IS_PTR(len));
724	return (len == 0);
725}
726
727void
728dname_remove_label(uint8_t** dname, size_t* len)
729{
730	size_t lablen;
731	log_assert(dname && *dname && len);
732	lablen = (*dname)[0];
733	log_assert(!LABEL_IS_PTR(lablen));
734	log_assert(*len > lablen);
735	if(lablen == 0)
736		return; /* do not modify root label */
737	*len -= lablen+1;
738	*dname += lablen+1;
739}
740
741void
742dname_remove_labels(uint8_t** dname, size_t* len, int n)
743{
744	int i;
745	for(i=0; i<n; i++)
746		dname_remove_label(dname, len);
747}
748
749int
750dname_signame_label_count(uint8_t* dname)
751{
752	uint8_t lablen;
753	int count = 0;
754	if(!*dname)
755		return 0;
756	if(dname[0] == 1 && dname[1] == '*')
757		dname += 2;
758	lablen = dname[0];
759	while(lablen) {
760		count++;
761		dname += lablen;
762		dname += 1;
763		lablen = dname[0];
764	}
765	return count;
766}
767
768int
769dname_is_wild(uint8_t* dname)
770{
771	return (dname[0] == 1 && dname[1] == '*');
772}
773
774/**
775 * Compare labels in memory, lowercase while comparing.
776 * Returns canonical order for labels. If all is equal, the
777 * shortest is first.
778 *
779 * @param p1: label 1
780 * @param len1: length of label 1.
781 * @param p2: label 2
782 * @param len2: length of label 2.
783 * @return: 0, -1, +1 comparison result.
784 */
785static int
786memcanoncmp(uint8_t* p1, uint8_t len1, uint8_t* p2, uint8_t len2)
787{
788	uint8_t min = (len1<len2)?len1:len2;
789	int c = memlowercmp(p1, p2, min);
790	if(c != 0)
791		return c;
792	/* equal, see who is shortest */
793	if(len1 < len2)
794		return -1;
795	if(len1 > len2)
796		return 1;
797	return 0;
798}
799
800
801int
802dname_canon_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs)
803{
804	/* like dname_lab_cmp, but with different label comparison,
805	 * empty character sorts before \000.
806	 * So   ylyly is before z. */
807	uint8_t len1, len2;
808	int atlabel = labs1;
809	int lastmlabs;
810	int lastdiff = 0;
811	int c;
812	/* first skip so that we compare same label. */
813	if(labs1 > labs2) {
814		while(atlabel > labs2) {
815			len1 = *d1++;
816			d1 += len1;
817			atlabel--;
818		}
819		log_assert(atlabel == labs2);
820	} else if(labs1 < labs2) {
821		atlabel = labs2;
822		while(atlabel > labs1) {
823			len2 = *d2++;
824			d2 += len2;
825			atlabel--;
826		}
827		log_assert(atlabel == labs1);
828	}
829	lastmlabs = atlabel+1;
830	/* now at same label in d1 and d2, atlabel */
831	/* www.example.com.                  */
832	/* 4   3       2  1   atlabel number */
833	/* repeat until at root label (which is always the same) */
834	while(atlabel > 1) {
835		len1 = *d1++;
836		len2 = *d2++;
837
838		if((c=memcanoncmp(d1, len1, d2, len2)) != 0) {
839			if(c<0)
840				lastdiff = -1;
841			else	lastdiff = 1;
842			lastmlabs = atlabel;
843		}
844
845		d1 += len1;
846		d2 += len2;
847		atlabel--;
848	}
849	/* last difference atlabel number, so number of labels matching,
850	 * at the right side, is one less. */
851	*mlabs = lastmlabs-1;
852	if(lastdiff == 0) {
853		/* all labels compared were equal, check if one has more
854		 * labels, so that example.com. > com. */
855		if(labs1 > labs2)
856			return 1;
857		else if(labs1 < labs2)
858			return -1;
859	}
860	return lastdiff;
861}
862
863int
864dname_canonical_compare(uint8_t* d1, uint8_t* d2)
865{
866	int labs1, labs2, m;
867	labs1 = dname_count_labels(d1);
868	labs2 = dname_count_labels(d2);
869	return dname_canon_lab_cmp(d1, labs1, d2, labs2, &m);
870}
871
872uint8_t* dname_get_shared_topdomain(uint8_t* d1, uint8_t* d2)
873{
874	int labs1, labs2, m;
875	size_t len = LDNS_MAX_DOMAINLEN;
876	labs1 = dname_count_labels(d1);
877	labs2 = dname_count_labels(d2);
878	(void)dname_lab_cmp(d1, labs1, d2, labs2, &m);
879	dname_remove_labels(&d1, &len, labs1-m);
880	return d1;
881}
882