Update to ldns-1.6.7
[dragonfly.git] / contrib / ldns / dname.c
1 /*
2  * dname.c
3  *
4  * dname specific rdata implementations
5  * A dname is a rdf structure with type LDNS_RDF_TYPE_DNAME
6  * It is not a /real/ type! All function must therefor check
7  * for LDNS_RDF_TYPE_DNAME.
8  *
9  * a Net::DNS like library for C
10  *
11  * (c) NLnet Labs, 2004-2006
12  *
13  * See the file LICENSE for the license
14  */
15
16 #include <ldns/config.h>
17
18 #include <ldns/ldns.h>
19
20 #ifdef HAVE_NETINET_IN_H
21 #include <netinet/in.h>
22 #endif
23 #ifdef HAVE_SYS_SOCKET_H
24 #include <sys/socket.h>
25 #endif
26 #ifdef HAVE_NETDB_H
27 #include <netdb.h>
28 #endif
29 #ifdef HAVE_ARPA_INET_H
30 #include <arpa/inet.h>
31 #endif
32
33 ldns_rdf *
34 ldns_dname_cat_clone(const ldns_rdf *rd1, const ldns_rdf *rd2)
35 {
36         ldns_rdf *new;
37         uint16_t new_size;
38         uint8_t *buf;
39         uint16_t left_size;
40
41         if (ldns_rdf_get_type(rd1) != LDNS_RDF_TYPE_DNAME ||
42                         ldns_rdf_get_type(rd2) != LDNS_RDF_TYPE_DNAME) {
43                 return NULL;
44         }
45
46         /* remove root label if it is present at the end of the left
47          * rd, by reducing the size with 1
48          */
49         left_size = ldns_rdf_size(rd1);
50         if (left_size > 0 &&ldns_rdf_data(rd1)[left_size - 1] == 0) {
51                 left_size--;
52         }
53
54         /* we overwrite the nullbyte of rd1 */
55         new_size = left_size + ldns_rdf_size(rd2);
56         buf = LDNS_XMALLOC(uint8_t, new_size);
57         if (!buf) {
58                 return NULL;
59         }
60
61         /* put the two dname's after each other */
62         memcpy(buf, ldns_rdf_data(rd1), left_size);
63         memcpy(buf + left_size, ldns_rdf_data(rd2), ldns_rdf_size(rd2));
64
65         new = ldns_rdf_new_frm_data(LDNS_RDF_TYPE_DNAME, new_size, buf);
66
67         LDNS_FREE(buf);
68         return new;
69 }
70
71 ldns_status
72 ldns_dname_cat(ldns_rdf *rd1, ldns_rdf *rd2)
73 {
74         uint16_t left_size;
75         uint16_t size;
76         uint8_t* newd;
77
78         if (ldns_rdf_get_type(rd1) != LDNS_RDF_TYPE_DNAME ||
79                         ldns_rdf_get_type(rd2) != LDNS_RDF_TYPE_DNAME) {
80                 return LDNS_STATUS_ERR;
81         }
82
83         /* remove root label if it is present at the end of the left
84          * rd, by reducing the size with 1
85          */
86         left_size = ldns_rdf_size(rd1);
87         if (left_size > 0 &&ldns_rdf_data(rd1)[left_size - 1] == 0) {
88                 left_size--;
89         }
90         if(left_size == 0) {
91                 return LDNS_STATUS_OK;
92         }
93
94         size = left_size + ldns_rdf_size(rd2);
95         newd = LDNS_XREALLOC(ldns_rdf_data(rd1), uint8_t, size);
96         if(!newd) {
97                 return LDNS_STATUS_MEM_ERR;
98         }
99
100         ldns_rdf_set_data(rd1, newd);
101         memcpy(ldns_rdf_data(rd1) + left_size, ldns_rdf_data(rd2),
102                         ldns_rdf_size(rd2));
103         ldns_rdf_set_size(rd1, size);
104
105         return LDNS_STATUS_OK;
106 }
107
108 ldns_rdf *
109 ldns_dname_reverse(const ldns_rdf *d)
110 {
111         ldns_rdf *new;
112         ldns_rdf *tmp;
113         ldns_rdf *d_tmp;
114         ldns_status status;
115
116         d_tmp = ldns_rdf_clone(d);
117
118         new = ldns_dname_new_frm_str(".");
119         if(!new)
120                 return NULL;
121
122         while(ldns_dname_label_count(d_tmp) > 0) {
123                 tmp = ldns_dname_label(d_tmp, 0);
124                 status = ldns_dname_cat(tmp, new);
125                 if(status != LDNS_STATUS_OK) {
126                         ldns_rdf_deep_free(new);
127                         ldns_rdf_deep_free(d_tmp);
128                         return NULL;
129                 }
130                 ldns_rdf_deep_free(new);
131                 new = tmp;
132                 tmp = ldns_dname_left_chop(d_tmp);
133                 ldns_rdf_deep_free(d_tmp);
134                 d_tmp = tmp;
135         }
136         ldns_rdf_deep_free(d_tmp);
137
138         return new;
139 }
140
141 ldns_rdf *
142 ldns_dname_clone_from(const ldns_rdf *d, uint16_t n)
143 {
144         uint8_t *data;
145         uint8_t label_size;
146         size_t data_size;
147
148         if (!d ||
149             ldns_rdf_get_type(d) != LDNS_RDF_TYPE_DNAME ||
150             ldns_dname_label_count(d) < n) {
151                 return NULL;
152         }
153
154         data = ldns_rdf_data(d);
155         data_size = ldns_rdf_size(d);
156         while (n > 0) {
157                 label_size = data[0] + 1;
158                 data += label_size;
159                 if (data_size < label_size) {
160                         /* this label is very broken */
161                         return NULL;
162                 }
163                 data_size -= label_size;
164                 n--;
165         }
166
167         return ldns_dname_new_frm_data(data_size, data);
168 }
169
170 ldns_rdf *
171 ldns_dname_left_chop(const ldns_rdf *d)
172 {
173         uint8_t label_pos;
174         ldns_rdf *chop;
175
176         if (!d) {
177                 return NULL;
178         }
179
180         if (ldns_rdf_get_type(d) != LDNS_RDF_TYPE_DNAME) {
181                 return NULL;
182         }
183         if (ldns_dname_label_count(d) == 0) {
184                 /* root label */
185                 return NULL;
186         }
187         /* 05blaat02nl00 */
188         label_pos = ldns_rdf_data(d)[0];
189
190         chop = ldns_dname_new_frm_data(ldns_rdf_size(d) - label_pos - 1,
191                         ldns_rdf_data(d) + label_pos + 1);
192         return chop;
193 }
194
195 uint8_t
196 ldns_dname_label_count(const ldns_rdf *r)
197 {
198         uint16_t src_pos;
199         uint16_t len;
200         uint8_t i;
201         size_t r_size;
202
203         if (!r) {
204                 return 0;
205         }
206
207         i = 0;
208         src_pos = 0;
209         r_size = ldns_rdf_size(r);
210
211         if (ldns_rdf_get_type(r) != LDNS_RDF_TYPE_DNAME) {
212                 return 0;
213         } else {
214                 len = ldns_rdf_data(r)[src_pos]; /* start of the label */
215
216                 /* single root label */
217                 if (1 == r_size) {
218                         return 0;
219                 } else {
220                         while ((len > 0) && src_pos < r_size) {
221                                 src_pos++;
222                                 src_pos += len;
223                                 len = ldns_rdf_data(r)[src_pos];
224                                 i++;
225                         }
226                 }
227         }
228         return i;
229 }
230
231 ldns_rdf *
232 ldns_dname_new(uint16_t s, void *d)
233 {
234         ldns_rdf *rd;
235
236         rd = LDNS_MALLOC(ldns_rdf);
237         if (!rd) {
238                 return NULL;
239         }
240         ldns_rdf_set_size(rd, s);
241         ldns_rdf_set_type(rd, LDNS_RDF_TYPE_DNAME);
242         ldns_rdf_set_data(rd, d);
243         return rd;
244 }
245
246 ldns_rdf *
247 ldns_dname_new_frm_str(const char *str)
248 {
249         return ldns_rdf_new_frm_str(LDNS_RDF_TYPE_DNAME, str);
250 }
251
252 ldns_rdf *
253 ldns_dname_new_frm_data(uint16_t size, const void *data)
254 {
255         return ldns_rdf_new_frm_data(LDNS_RDF_TYPE_DNAME, size, data);
256 }
257
258 void
259 ldns_dname2canonical(const ldns_rdf *rd)
260 {
261         uint8_t *rdd;
262         uint16_t i;
263
264         if (ldns_rdf_get_type(rd) != LDNS_RDF_TYPE_DNAME) {
265                 return;
266         }
267
268         rdd = (uint8_t*)ldns_rdf_data(rd);
269         for (i = 0; i < ldns_rdf_size(rd); i++, rdd++) {
270                 *rdd = (uint8_t)LDNS_DNAME_NORMALIZE((int)*rdd);
271         }
272 }
273
274 bool
275 ldns_dname_is_subdomain(const ldns_rdf *sub, const ldns_rdf *parent)
276 {
277         uint8_t sub_lab;
278         uint8_t par_lab;
279         int8_t i, j;
280         ldns_rdf *tmp_sub = NULL;
281         ldns_rdf *tmp_par = NULL;
282     ldns_rdf *sub_clone;
283     ldns_rdf *parent_clone;
284     bool result = true;
285
286         if (ldns_rdf_get_type(sub) != LDNS_RDF_TYPE_DNAME ||
287                         ldns_rdf_get_type(parent) != LDNS_RDF_TYPE_DNAME ||
288                         ldns_rdf_compare(sub, parent) == 0) {
289                 return false;
290         }
291
292     /* would be nicer if we do not have to clone... */
293     sub_clone = ldns_dname_clone_from(sub, 0);
294     parent_clone = ldns_dname_clone_from(parent, 0);
295     ldns_dname2canonical(sub_clone);
296     ldns_dname2canonical(parent_clone);
297
298         sub_lab = ldns_dname_label_count(sub_clone);
299         par_lab = ldns_dname_label_count(parent_clone);
300
301         /* if sub sits above parent, it cannot be a child/sub domain */
302         if (sub_lab < par_lab) {
303                 result = false;
304         } else {
305                 /* check all labels the from the parent labels, from right to left.
306                  * When they /all/ match we have found a subdomain
307                  */
308                 j = sub_lab - 1; /* we count from zero, thank you */
309                 for (i = par_lab -1; i >= 0; i--) {
310                         tmp_sub = ldns_dname_label(sub_clone, j);
311                         tmp_par = ldns_dname_label(parent_clone, i);
312                         if (!tmp_sub || !tmp_par) {
313                                 /* deep free does null check */
314                                 ldns_rdf_deep_free(tmp_sub);
315                                 ldns_rdf_deep_free(tmp_par);
316                                 result = false;
317                                 break;
318                         }
319
320                         if (ldns_rdf_compare(tmp_sub, tmp_par) != 0) {
321                                 /* they are not equal */
322                                 ldns_rdf_deep_free(tmp_sub);
323                                 ldns_rdf_deep_free(tmp_par);
324                                 result = false;
325                                 break;
326                         }
327                         ldns_rdf_deep_free(tmp_sub);
328                         ldns_rdf_deep_free(tmp_par);
329                         j--;
330                 }
331         }
332         ldns_rdf_deep_free(sub_clone);
333         ldns_rdf_deep_free(parent_clone);
334         return result;
335 }
336
337 int
338 ldns_dname_compare(const ldns_rdf *dname1, const ldns_rdf *dname2)
339 {
340         size_t lc1, lc2, lc1f, lc2f;
341         size_t i;
342         int result = 0;
343         uint8_t *lp1, *lp2;
344
345         /* see RFC4034 for this algorithm */
346         /* this algorithm assumes the names are normalized to case */
347
348         /* only when both are not NULL we can say anything about them */
349         if (!dname1 && !dname2) {
350                 return 0;
351         }
352         if (!dname1 || !dname2) {
353                 return -1;
354         }
355         /* asserts must happen later as we are looking in the
356          * dname, which could be NULL. But this case is handled
357          * above
358          */
359         assert(ldns_rdf_get_type(dname1) == LDNS_RDF_TYPE_DNAME);
360         assert(ldns_rdf_get_type(dname2) == LDNS_RDF_TYPE_DNAME);
361
362         lc1 = ldns_dname_label_count(dname1);
363         lc2 = ldns_dname_label_count(dname2);
364
365         if (lc1 == 0 && lc2 == 0) {
366                 return 0;
367         }
368         if (lc1 == 0) {
369                 return -1;
370         }
371         if (lc2 == 0) {
372                 return 1;
373         }
374         lc1--;
375         lc2--;
376         /* we start at the last label */
377         while (true) {
378                 /* find the label first */
379                 lc1f = lc1;
380                 lp1 = ldns_rdf_data(dname1);
381                 while (lc1f > 0) {
382                         lp1 += *lp1 + 1;
383                         lc1f--;
384                 }
385
386                 /* and find the other one */
387                 lc2f = lc2;
388                 lp2 = ldns_rdf_data(dname2);
389                 while (lc2f > 0) {
390                         lp2 += *lp2 + 1;
391                         lc2f--;
392                 }
393
394                 /* now check the label character for character. */
395                 for (i = 1; i < (size_t)(*lp1 + 1); i++) {
396                         if (i > *lp2) {
397                                 /* apparently label 1 is larger */
398                                 result = 1;
399                                 goto done;
400                         }
401                         if (LDNS_DNAME_NORMALIZE((int) *(lp1 + i)) <
402                             LDNS_DNAME_NORMALIZE((int) *(lp2 + i))) {
403                             result = -1;
404                             goto done;
405                         } else if (LDNS_DNAME_NORMALIZE((int) *(lp1 + i)) >
406                             LDNS_DNAME_NORMALIZE((int) *(lp2 + i))) {
407                             result = 1;
408                             goto done;
409                         }
410                 }
411                 if (*lp1 < *lp2) {
412                         /* apparently label 2 is larger */
413                         result = -1;
414                         goto done;
415                 }
416                 if (lc1 == 0 && lc2 > 0) {
417                         result = -1;
418                         goto done;
419                 } else if (lc1 > 0 && lc2 == 0) {
420                         result = 1;
421                         goto done;
422                 } else if (lc1 == 0 && lc2 == 0) {
423                         result = 0;
424                         goto done;
425                 }
426                 lc1--;
427                 lc2--;
428         }
429
430         done:
431         return result;
432 }
433
434 int
435 ldns_dname_is_wildcard(const ldns_rdf* dname)
436 {
437         return ( ldns_dname_label_count(dname) > 0 &&
438                  ldns_rdf_data(dname)[0] == 1 &&
439                  ldns_rdf_data(dname)[1] == '*');
440 }
441
442 int
443 ldns_dname_match_wildcard(const ldns_rdf *dname, const ldns_rdf *wildcard)
444 {
445         ldns_rdf *wc_chopped;
446         int result;
447         /* check whether it really is a wildcard */
448         if (ldns_dname_is_wildcard(wildcard)) {
449                 /* ok, so the dname needs to be a subdomain of the wildcard
450                  * without the *
451                  */
452                 wc_chopped = ldns_dname_left_chop(wildcard);
453                 result = (int) ldns_dname_is_subdomain(dname, wc_chopped);
454                 ldns_rdf_deep_free(wc_chopped);
455         } else {
456                 result = (ldns_dname_compare(dname, wildcard) == 0);
457         }
458         return result;
459 }
460
461 /* nsec test: does prev <= middle < next
462  * -1 = yes
463  * 0 = error/can't tell
464  * 1 = no
465  */
466 int
467 ldns_dname_interval(const ldns_rdf *prev, const ldns_rdf *middle,
468                 const ldns_rdf *next)
469 {
470         int prev_check, next_check;
471
472         assert(ldns_rdf_get_type(prev) == LDNS_RDF_TYPE_DNAME);
473         assert(ldns_rdf_get_type(middle) == LDNS_RDF_TYPE_DNAME);
474         assert(ldns_rdf_get_type(next) == LDNS_RDF_TYPE_DNAME);
475
476         prev_check = ldns_dname_compare(prev, middle);
477         next_check = ldns_dname_compare(middle, next);
478         /* <= next. This cannot be the case for nsec, because then we would
479          * have gotten the nsec of next...
480          */
481         if (next_check == 0) {
482                 return 0;
483         }
484
485                         /* <= */
486         if ((prev_check == -1 || prev_check == 0) &&
487                         /* < */
488                         next_check == -1) {
489                 return -1;
490         } else {
491                 return 1;
492         }
493 }
494
495
496 bool
497 ldns_dname_str_absolute(const char *dname_str)
498 {
499         const char* s;
500         if(dname_str && strcmp(dname_str, ".") == 0)
501                 return 1;
502         if(!dname_str || strlen(dname_str) < 2)
503                 return 0;
504         if(dname_str[strlen(dname_str) - 1] != '.')
505                 return 0;
506         if(dname_str[strlen(dname_str) - 2] != '\\')
507                 return 1; /* ends in . and no \ before it */
508         /* so we have the case of ends in . and there is \ before it */
509         for(s=dname_str; *s; s++) {
510                 if(*s == '\\') {
511                         if(s[1] && s[2] && s[3] /* check length */
512                                 && isdigit(s[1]) && isdigit(s[2]) && 
513                                 isdigit(s[3]))
514                                 s += 3;
515                         else if(!s[1] || isdigit(s[1])) /* escape of nul,0-9 */
516                                 return 0; /* parse error */
517                         else s++; /* another character escaped */
518                 }
519                 else if(!*(s+1) && *s == '.')
520                         return 1; /* trailing dot, unescaped */
521         }
522         return 0;
523 }
524
525 ldns_rdf *
526 ldns_dname_label(const ldns_rdf *rdf, uint8_t labelpos)
527 {
528         uint8_t labelcnt;
529         uint16_t src_pos;
530         uint16_t len;
531         ldns_rdf *tmpnew;
532         size_t s;
533
534         if (ldns_rdf_get_type(rdf) != LDNS_RDF_TYPE_DNAME) {
535                 return NULL;
536         }
537
538         labelcnt = 0;
539         src_pos = 0;
540         s = ldns_rdf_size(rdf);
541
542         len = ldns_rdf_data(rdf)[src_pos]; /* label start */
543         while ((len > 0) && src_pos < s) {
544                 if (labelcnt == labelpos) {
545                         /* found our label */
546                         tmpnew = LDNS_MALLOC(ldns_rdf);
547                         if (!tmpnew) {
548                                 return NULL;
549                         }
550                         tmpnew->_type = LDNS_RDF_TYPE_DNAME;
551                         tmpnew->_data = LDNS_XMALLOC(uint8_t, len + 2);
552                         if (!tmpnew->_data) {
553                                 LDNS_FREE(tmpnew);
554                                 return NULL;
555                         }
556                         memset(tmpnew->_data, 0, len + 2);
557                         memcpy(tmpnew->_data, ldns_rdf_data(rdf) + src_pos, len + 1);
558                         tmpnew->_size = len + 2;
559                         return tmpnew;
560                 }
561                 src_pos++;
562                 src_pos += len;
563                 len = ldns_rdf_data(rdf)[src_pos];
564                 labelcnt++;
565         }
566         return NULL;
567 }