Change the kernel dev_t, representing a pointer to a specinfo structure,
[dragonfly.git] / contrib / bind-9.2.4rc7 / lib / bind / nameser / ns_name.c
1 /*
2  * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
3  * Copyright (c) 1996,1999 by Internet Software Consortium.
4  *
5  * Permission to use, copy, modify, and distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11  * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
15  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16  */
17
18 #ifndef lint
19 static const char rcsid[] = "$Id: ns_name.c,v 1.3.2.6 2004/05/04 03:26:16 marka Exp $";
20 #endif
21
22 #include "port_before.h"
23
24 #include <sys/types.h>
25
26 #include <netinet/in.h>
27 #include <arpa/nameser.h>
28
29 #include <errno.h>
30 #include <resolv.h>
31 #include <string.h>
32 #include <ctype.h>
33 #include <stdlib.h>
34 #include <limits.h>
35
36 #include "port_after.h"
37
38 #ifdef SPRINTF_CHAR
39 # define SPRINTF(x) strlen(sprintf/**/x)
40 #else
41 # define SPRINTF(x) ((size_t)sprintf x)
42 #endif
43
44 #define NS_TYPE_ELT                     0x40 /* EDNS0 extended label type */
45 #define DNS_LABELTYPE_BITSTRING         0x41
46
47 /* Data. */
48
49 static const char       digits[] = "0123456789";
50
51 static const char digitvalue[256] = {
52         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*16*/
53         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*32*/
54         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*48*/
55          0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, /*64*/
56         -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*80*/
57         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*96*/
58         -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*112*/
59         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*128*/
60         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
61         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
62         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
63         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
64         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
65         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
66         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
67         -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*256*/
68 };
69
70 /* Forward. */
71
72 static int              special(int);
73 static int              printable(int);
74 static int              dn_find(const u_char *, const u_char *,
75                                 const u_char * const *,
76                                 const u_char * const *);
77 static int              encode_bitsring(const char **, const char *,
78                                         unsigned char **, unsigned char **,
79                                         unsigned const char *);
80 static int              labellen(const u_char *);
81 static int              decode_bitstring(const unsigned char **,
82                                          char *, const char *);
83
84 /* Public. */
85
86 /*
87  * ns_name_ntop(src, dst, dstsiz)
88  *      Convert an encoded domain name to printable ascii as per RFC1035.
89  * return:
90  *      Number of bytes written to buffer, or -1 (with errno set)
91  * notes:
92  *      The root is returned as "."
93  *      All other domains are returned in non absolute form
94  */
95 int
96 ns_name_ntop(const u_char *src, char *dst, size_t dstsiz)
97 {
98         const u_char *cp;
99         char *dn, *eom;
100         u_char c;
101         u_int n;
102         int l;
103
104         cp = src;
105         dn = dst;
106         eom = dst + dstsiz;
107
108         while ((n = *cp++) != 0) {
109                 if ((n & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
110                         /* Some kind of compression pointer. */
111                         errno = EMSGSIZE;
112                         return (-1);
113                 }
114                 if (dn != dst) {
115                         if (dn >= eom) {
116                                 errno = EMSGSIZE;
117                                 return (-1);
118                         }
119                         *dn++ = '.';
120                 }
121                 if ((l = labellen(cp - 1)) < 0) {
122                         errno = EMSGSIZE; /* XXX */
123                         return(-1);
124                 }
125                 if (dn + l >= eom) {
126                         errno = EMSGSIZE;
127                         return (-1);
128                 }
129                 if ((n & NS_CMPRSFLGS) == NS_TYPE_ELT) {
130                         int m;
131
132                         if (n != DNS_LABELTYPE_BITSTRING) {
133                                 /* XXX: labellen should reject this case */
134                                 errno = EINVAL;
135                                 return(-1);
136                         }
137                         if ((m = decode_bitstring(&cp, dn, eom)) < 0)
138                         {
139                                 errno = EMSGSIZE;
140                                 return(-1);
141                         }
142                         dn += m; 
143                         continue;
144                 }
145                 for ((void)NULL; l > 0; l--) {
146                         c = *cp++;
147                         if (special(c)) {
148                                 if (dn + 1 >= eom) {
149                                         errno = EMSGSIZE;
150                                         return (-1);
151                                 }
152                                 *dn++ = '\\';
153                                 *dn++ = (char)c;
154                         } else if (!printable(c)) {
155                                 if (dn + 3 >= eom) {
156                                         errno = EMSGSIZE;
157                                         return (-1);
158                                 }
159                                 *dn++ = '\\';
160                                 *dn++ = digits[c / 100];
161                                 *dn++ = digits[(c % 100) / 10];
162                                 *dn++ = digits[c % 10];
163                         } else {
164                                 if (dn >= eom) {
165                                         errno = EMSGSIZE;
166                                         return (-1);
167                                 }
168                                 *dn++ = (char)c;
169                         }
170                 }
171         }
172         if (dn == dst) {
173                 if (dn >= eom) {
174                         errno = EMSGSIZE;
175                         return (-1);
176                 }
177                 *dn++ = '.';
178         }
179         if (dn >= eom) {
180                 errno = EMSGSIZE;
181                 return (-1);
182         }
183         *dn++ = '\0';
184         return (dn - dst);
185 }
186
187 /*
188  * ns_name_pton(src, dst, dstsiz)
189  *      Convert a ascii string into an encoded domain name as per RFC1035.
190  * return:
191  *      -1 if it fails
192  *      1 if string was fully qualified
193  *      0 is string was not fully qualified
194  * notes:
195  *      Enforces label and domain length limits.
196  */
197
198 int
199 ns_name_pton(const char *src, u_char *dst, size_t dstsiz)
200 {
201         u_char *label, *bp, *eom;
202         int c, n, escaped, e = 0;
203         char *cp;
204
205         escaped = 0;
206         bp = dst;
207         eom = dst + dstsiz;
208         label = bp++;
209
210         while ((c = *src++) != 0) {
211                 if (escaped) {
212                         if (c == '[') { /* start a bit string label */
213                                 if ((cp = strchr(src, ']')) == NULL) {
214                                         errno = EINVAL; /* ??? */
215                                         return(-1);
216                                 }
217                                 if ((e = encode_bitsring(&src, cp + 2,
218                                                          &label, &bp, eom))
219                                     != 0) {
220                                         errno = e;
221                                         return(-1);
222                                 }
223                                 escaped = 0;
224                                 label = bp++;
225                                 if ((c = *src++) == 0)
226                                         goto done;
227                                 else if (c != '.') {
228                                         errno = EINVAL;
229                                         return(-1);
230                                 }
231                                 continue;
232                         }
233                         else if ((cp = strchr(digits, c)) != NULL) {
234                                 n = (cp - digits) * 100;
235                                 if ((c = *src++) == 0 ||
236                                     (cp = strchr(digits, c)) == NULL) {
237                                         errno = EMSGSIZE;
238                                         return (-1);
239                                 }
240                                 n += (cp - digits) * 10;
241                                 if ((c = *src++) == 0 ||
242                                     (cp = strchr(digits, c)) == NULL) {
243                                         errno = EMSGSIZE;
244                                         return (-1);
245                                 }
246                                 n += (cp - digits);
247                                 if (n > 255) {
248                                         errno = EMSGSIZE;
249                                         return (-1);
250                                 }
251                                 c = n;
252                         }
253                         escaped = 0;
254                 } else if (c == '\\') {
255                         escaped = 1;
256                         continue;
257                 } else if (c == '.') {
258                         c = (bp - label - 1);
259                         if ((c & NS_CMPRSFLGS) != 0) {  /* Label too big. */
260                                 errno = EMSGSIZE;
261                                 return (-1);
262                         }
263                         if (label >= eom) {
264                                 errno = EMSGSIZE;
265                                 return (-1);
266                         }
267                         *label = c;
268                         /* Fully qualified ? */
269                         if (*src == '\0') {
270                                 if (c != 0) {
271                                         if (bp >= eom) {
272                                                 errno = EMSGSIZE;
273                                                 return (-1);
274                                         }
275                                         *bp++ = '\0';
276                                 }
277                                 if ((bp - dst) > MAXCDNAME) {
278                                         errno = EMSGSIZE;
279                                         return (-1);
280                                 }
281                                 return (1);
282                         }
283                         if (c == 0 || *src == '.') {
284                                 errno = EMSGSIZE;
285                                 return (-1);
286                         }
287                         label = bp++;
288                         continue;
289                 }
290                 if (bp >= eom) {
291                         errno = EMSGSIZE;
292                         return (-1);
293                 }
294                 *bp++ = (u_char)c;
295         }
296         c = (bp - label - 1);
297         if ((c & NS_CMPRSFLGS) != 0) {          /* Label too big. */
298                 errno = EMSGSIZE;
299                 return (-1);
300         }
301   done:
302         if (label >= eom) {
303                 errno = EMSGSIZE;
304                 return (-1);
305         }
306         *label = c;
307         if (c != 0) {
308                 if (bp >= eom) {
309                         errno = EMSGSIZE;
310                         return (-1);
311                 }
312                 *bp++ = 0;
313         }
314         if ((bp - dst) > MAXCDNAME) {   /* src too big */
315                 errno = EMSGSIZE;
316                 return (-1);
317         }
318         return (0);
319 }
320
321 /*
322  * ns_name_ntol(src, dst, dstsiz)
323  *      Convert a network strings labels into all lowercase.
324  * return:
325  *      Number of bytes written to buffer, or -1 (with errno set)
326  * notes:
327  *      Enforces label and domain length limits.
328  */
329
330 int
331 ns_name_ntol(const u_char *src, u_char *dst, size_t dstsiz)
332 {
333         const u_char *cp;
334         u_char *dn, *eom;
335         u_char c;
336         u_int n;
337         int l;
338
339         cp = src;
340         dn = dst;
341         eom = dst + dstsiz;
342
343         if (dn >= eom) {
344                 errno = EMSGSIZE;
345                 return (-1);
346         }
347         while ((n = *cp++) != 0) {
348                 if ((n & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
349                         /* Some kind of compression pointer. */
350                         errno = EMSGSIZE;
351                         return (-1);
352                 }
353                 *dn++ = n;
354                 if ((l = labellen(cp - 1)) < 0) {
355                         errno = EMSGSIZE;
356                         return (-1);
357                 }
358                 if (dn + l >= eom) {
359                         errno = EMSGSIZE;
360                         return (-1);
361                 }
362                 for ((void)NULL; l > 0; l--) {
363                         c = *cp++;
364                         if (isupper(c))
365                                 *dn++ = tolower(c);
366                         else
367                                 *dn++ = c;
368                 }
369         }
370         *dn++ = '\0';
371         return (dn - dst);
372 }
373
374 /*
375  * ns_name_unpack(msg, eom, src, dst, dstsiz)
376  *      Unpack a domain name from a message, source may be compressed.
377  * return:
378  *      -1 if it fails, or consumed octets if it succeeds.
379  */
380 int
381 ns_name_unpack(const u_char *msg, const u_char *eom, const u_char *src,
382                u_char *dst, size_t dstsiz)
383 {
384         const u_char *srcp, *dstlim;
385         u_char *dstp;
386         int n, len, checked, l;
387
388         len = -1;
389         checked = 0;
390         dstp = dst;
391         srcp = src;
392         dstlim = dst + dstsiz;
393         if (srcp < msg || srcp >= eom) {
394                 errno = EMSGSIZE;
395                 return (-1);
396         }
397         /* Fetch next label in domain name. */
398         while ((n = *srcp++) != 0) {
399                 /* Check for indirection. */
400                 switch (n & NS_CMPRSFLGS) {
401                 case 0:
402                 case NS_TYPE_ELT:
403                         /* Limit checks. */
404                         if ((l = labellen(srcp - 1)) < 0) {
405                                 errno = EMSGSIZE;
406                                 return(-1);
407                         }
408                         if (dstp + l + 1 >= dstlim || srcp + l >= eom) {
409                                 errno = EMSGSIZE;
410                                 return (-1);
411                         }
412                         checked += l + 1;
413                         *dstp++ = n;
414                         memcpy(dstp, srcp, l);
415                         dstp += l;
416                         srcp += l;
417                         break;
418
419                 case NS_CMPRSFLGS:
420                         if (srcp >= eom) {
421                                 errno = EMSGSIZE;
422                                 return (-1);
423                         }
424                         if (len < 0)
425                                 len = srcp - src + 1;
426                         srcp = msg + (((n & 0x3f) << 8) | (*srcp & 0xff));
427                         if (srcp < msg || srcp >= eom) {  /* Out of range. */
428                                 errno = EMSGSIZE;
429                                 return (-1);
430                         }
431                         checked += 2;
432                         /*
433                          * Check for loops in the compressed name;
434                          * if we've looked at the whole message,
435                          * there must be a loop.
436                          */
437                         if (checked >= eom - msg) {
438                                 errno = EMSGSIZE;
439                                 return (-1);
440                         }
441                         break;
442
443                 default:
444                         errno = EMSGSIZE;
445                         return (-1);                    /* flag error */
446                 }
447         }
448         *dstp = '\0';
449         if (len < 0)
450                 len = srcp - src;
451         return (len);
452 }
453
454 /*
455  * ns_name_pack(src, dst, dstsiz, dnptrs, lastdnptr)
456  *      Pack domain name 'domain' into 'comp_dn'.
457  * return:
458  *      Size of the compressed name, or -1.
459  * notes:
460  *      'dnptrs' is an array of pointers to previous compressed names.
461  *      dnptrs[0] is a pointer to the beginning of the message. The array
462  *      ends with NULL.
463  *      'lastdnptr' is a pointer to the end of the array pointed to
464  *      by 'dnptrs'.
465  * Side effects:
466  *      The list of pointers in dnptrs is updated for labels inserted into
467  *      the message as we compress the name.  If 'dnptr' is NULL, we don't
468  *      try to compress names. If 'lastdnptr' is NULL, we don't update the
469  *      list.
470  */
471 int
472 ns_name_pack(const u_char *src, u_char *dst, int dstsiz,
473              const u_char **dnptrs, const u_char **lastdnptr)
474 {
475         u_char *dstp;
476         const u_char **cpp, **lpp, *eob, *msg;
477         const u_char *srcp;
478         int n, l, first = 1;
479
480         srcp = src;
481         dstp = dst;
482         eob = dstp + dstsiz;
483         lpp = cpp = NULL;
484         if (dnptrs != NULL) {
485                 if ((msg = *dnptrs++) != NULL) {
486                         for (cpp = dnptrs; *cpp != NULL; cpp++)
487                                 (void)NULL;
488                         lpp = cpp;      /* end of list to search */
489                 }
490         } else
491                 msg = NULL;
492
493         /* make sure the domain we are about to add is legal */
494         l = 0;
495         do {
496                 int l0;
497
498                 n = *srcp;
499                 if ((n & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
500                         errno = EMSGSIZE;
501                         return (-1);
502                 }
503                 if ((l0 = labellen(srcp)) < 0) {
504                         errno = EINVAL;
505                         return(-1);
506                 }
507                 l += l0 + 1;
508                 if (l > MAXCDNAME) {
509                         errno = EMSGSIZE;
510                         return (-1);
511                 }
512                 srcp += l0 + 1;
513         } while (n != 0);
514
515         /* from here on we need to reset compression pointer array on error */
516         srcp = src;
517         do {
518                 /* Look to see if we can use pointers. */
519                 n = *srcp;
520                 if (n != 0 && msg != NULL) {
521                         l = dn_find(srcp, msg, (const u_char * const *)dnptrs,
522                                     (const u_char * const *)lpp);
523                         if (l >= 0) {
524                                 if (dstp + 1 >= eob) {
525                                         goto cleanup;
526                                 }
527                                 *dstp++ = (l >> 8) | NS_CMPRSFLGS;
528                                 *dstp++ = l % 256;
529                                 return (dstp - dst);
530                         }
531                         /* Not found, save it. */
532                         if (lastdnptr != NULL && cpp < lastdnptr - 1 &&
533                             (dstp - msg) < 0x4000 && first) {
534                                 *cpp++ = dstp;
535                                 *cpp = NULL;
536                                 first = 0;
537                         }
538                 }
539                 /* copy label to buffer */
540                 if ((n & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
541                         /* Should not happen. */
542                         goto cleanup;
543                 }
544                 n = labellen(srcp);
545                 if (dstp + 1 + n >= eob) {
546                         goto cleanup;
547                 }
548                 memcpy(dstp, srcp, n + 1);
549                 srcp += n + 1;
550                 dstp += n + 1;
551         } while (n != 0);
552
553         if (dstp > eob) {
554 cleanup:
555                 if (msg != NULL)
556                         *lpp = NULL;
557                 errno = EMSGSIZE;
558                 return (-1);
559         } 
560         return (dstp - dst);
561 }
562
563 /*
564  * ns_name_uncompress(msg, eom, src, dst, dstsiz)
565  *      Expand compressed domain name to presentation format.
566  * return:
567  *      Number of bytes read out of `src', or -1 (with errno set).
568  * note:
569  *      Root domain returns as "." not "".
570  */
571 int
572 ns_name_uncompress(const u_char *msg, const u_char *eom, const u_char *src,
573                    char *dst, size_t dstsiz)
574 {
575         u_char tmp[NS_MAXCDNAME];
576         int n;
577         
578         if ((n = ns_name_unpack(msg, eom, src, tmp, sizeof tmp)) == -1)
579                 return (-1);
580         if (ns_name_ntop(tmp, dst, dstsiz) == -1)
581                 return (-1);
582         return (n);
583 }
584
585 /*
586  * ns_name_compress(src, dst, dstsiz, dnptrs, lastdnptr)
587  *      Compress a domain name into wire format, using compression pointers.
588  * return:
589  *      Number of bytes consumed in `dst' or -1 (with errno set).
590  * notes:
591  *      'dnptrs' is an array of pointers to previous compressed names.
592  *      dnptrs[0] is a pointer to the beginning of the message.
593  *      The list ends with NULL.  'lastdnptr' is a pointer to the end of the
594  *      array pointed to by 'dnptrs'. Side effect is to update the list of
595  *      pointers for labels inserted into the message as we compress the name.
596  *      If 'dnptr' is NULL, we don't try to compress names. If 'lastdnptr'
597  *      is NULL, we don't update the list.
598  */
599 int
600 ns_name_compress(const char *src, u_char *dst, size_t dstsiz,
601                  const u_char **dnptrs, const u_char **lastdnptr)
602 {
603         u_char tmp[NS_MAXCDNAME];
604
605         if (ns_name_pton(src, tmp, sizeof tmp) == -1)
606                 return (-1);
607         return (ns_name_pack(tmp, dst, dstsiz, dnptrs, lastdnptr));
608 }
609
610 /*
611  * Reset dnptrs so that there are no active references to pointers at or
612  * after src.
613  */
614 void
615 ns_name_rollback(const u_char *src, const u_char **dnptrs,
616                  const u_char **lastdnptr)
617 {
618         while (dnptrs < lastdnptr && *dnptrs != NULL) {
619                 if (*dnptrs >= src) {
620                         *dnptrs = NULL;
621                         break;
622                 }
623                 dnptrs++;
624         }
625 }
626
627 /*
628  * ns_name_skip(ptrptr, eom)
629  *      Advance *ptrptr to skip over the compressed name it points at.
630  * return:
631  *      0 on success, -1 (with errno set) on failure.
632  */
633 int
634 ns_name_skip(const u_char **ptrptr, const u_char *eom)
635 {
636         const u_char *cp;
637         u_int n;
638         int l;
639
640         cp = *ptrptr;
641         while (cp < eom && (n = *cp++) != 0) {
642                 /* Check for indirection. */
643                 switch (n & NS_CMPRSFLGS) {
644                 case 0:                 /* normal case, n == len */
645                         cp += n;
646                         continue;
647                 case NS_TYPE_ELT: /* EDNS0 extended label */
648                         if ((l = labellen(cp - 1)) < 0) {
649                                 errno = EMSGSIZE; /* XXX */
650                                 return(-1);
651                         }
652                         cp += l;
653                         continue;
654                 case NS_CMPRSFLGS:      /* indirection */
655                         cp++;
656                         break;
657                 default:                /* illegal type */
658                         errno = EMSGSIZE;
659                         return (-1);
660                 }
661                 break;
662         }
663         if (cp > eom) {
664                 errno = EMSGSIZE;
665                 return (-1);
666         }
667         *ptrptr = cp;
668         return (0);
669 }
670
671 /* Private. */
672
673 /*
674  * special(ch)
675  *      Thinking in noninternationalized USASCII (per the DNS spec),
676  *      is this characted special ("in need of quoting") ?
677  * return:
678  *      boolean.
679  */
680 static int
681 special(int ch) {
682         switch (ch) {
683         case 0x22: /* '"' */
684         case 0x2E: /* '.' */
685         case 0x3B: /* ';' */
686         case 0x5C: /* '\\' */
687         case 0x28: /* '(' */
688         case 0x29: /* ')' */
689         /* Special modifiers in zone files. */
690         case 0x40: /* '@' */
691         case 0x24: /* '$' */
692                 return (1);
693         default:
694                 return (0);
695         }
696 }
697
698 /*
699  * printable(ch)
700  *      Thinking in noninternationalized USASCII (per the DNS spec),
701  *      is this character visible and not a space when printed ?
702  * return:
703  *      boolean.
704  */
705 static int
706 printable(int ch) {
707         return (ch > 0x20 && ch < 0x7f);
708 }
709
710 /*
711  *      Thinking in noninternationalized USASCII (per the DNS spec),
712  *      convert this character to lower case if it's upper case.
713  */
714 static int
715 mklower(int ch) {
716         if (ch >= 0x41 && ch <= 0x5A)
717                 return (ch + 0x20);
718         return (ch);
719 }
720
721 /*
722  * dn_find(domain, msg, dnptrs, lastdnptr)
723  *      Search for the counted-label name in an array of compressed names.
724  * return:
725  *      offset from msg if found, or -1.
726  * notes:
727  *      dnptrs is the pointer to the first name on the list,
728  *      not the pointer to the start of the message.
729  */
730 static int
731 dn_find(const u_char *domain, const u_char *msg,
732         const u_char * const *dnptrs,
733         const u_char * const *lastdnptr)
734 {
735         const u_char *dn, *cp, *sp;
736         const u_char * const *cpp;
737         u_int n;
738
739         for (cpp = dnptrs; cpp < lastdnptr; cpp++) {
740                 sp = *cpp;
741                 /*
742                  * terminate search on:
743                  * root label
744                  * compression pointer
745                  * unusable offset
746                  */
747                 while (*sp != 0 && (*sp & NS_CMPRSFLGS) == 0 &&
748                        (sp - msg) < 0x4000) {
749                         dn = domain;
750                         cp = sp;
751                         while ((n = *cp++) != 0) {
752                                 /*
753                                  * check for indirection
754                                  */
755                                 switch (n & NS_CMPRSFLGS) {
756                                 case 0:         /* normal case, n == len */
757                                         n = labellen(cp - 1); /* XXX */
758
759                                         if (n != *dn++)
760                                                 goto next;
761
762                                         for ((void)NULL; n > 0; n--)
763                                                 if (mklower(*dn++) !=
764                                                     mklower(*cp++))
765                                                         goto next;
766                                         /* Is next root for both ? */
767                                         if (*dn == '\0' && *cp == '\0')
768                                                 return (sp - msg);
769                                         if (*dn)
770                                                 continue;
771                                         goto next;
772                                 case NS_CMPRSFLGS:      /* indirection */
773                                         cp = msg + (((n & 0x3f) << 8) | *cp);
774                                         break;
775
776                                 default:        /* illegal type */
777                                         errno = EMSGSIZE;
778                                         return (-1);
779                                 }
780                         }
781  next: ;
782                         sp += *sp + 1;
783                 }
784         }
785         errno = ENOENT;
786         return (-1);
787 }
788
789 static int
790 decode_bitstring(const unsigned char **cpp, char *dn, const char *eom)
791 {
792         const unsigned char *cp = *cpp;
793         char *beg = dn, tc;
794         int b, blen, plen, i;
795
796         if ((blen = (*cp & 0xff)) == 0)
797                 blen = 256;
798         plen = (blen + 3) / 4;
799         plen += sizeof("\\[x/]") + (blen > 99 ? 3 : (blen > 9) ? 2 : 1);
800         if (dn + plen >= eom)
801                 return(-1);
802
803         cp++;
804         i = SPRINTF((dn, "\\[x"));
805         if (i < 0)
806                 return (-1);
807         dn += i;
808         for (b = blen; b > 7; b -= 8, cp++) {
809                 i = SPRINTF((dn, "%02x", *cp & 0xff));
810                 if (i < 0)
811                         return (-1);
812                 dn += i;
813         }
814         if (b > 4) {
815                 tc = *cp++;
816                 i = SPRINTF((dn, "%02x", tc & (0xff << (8 - b))));
817                 if (i < 0)
818                         return (-1);
819                 dn += i;
820         } else if (b > 0) {
821                 tc = *cp++;
822                 i = SPRINTF((dn, "%1x",
823                                ((tc >> 4) & 0x0f) & (0x0f << (4 - b)))); 
824                 if (i < 0)
825                         return (-1);
826                 dn += i;
827         }
828         i = SPRINTF((dn, "/%d]", blen));
829         if (i < 0)
830                 return (-1);
831         dn += i;
832
833         *cpp = cp;
834         return(dn - beg);
835 }
836
837 static int
838 encode_bitsring(const char **bp, const char *end, unsigned char **labelp,
839                 unsigned char ** dst, unsigned const char *eom)
840 {
841         int afterslash = 0;
842         const char *cp = *bp;
843         unsigned char *tp;
844         char c;
845         const char *beg_blen;
846         char *end_blen = NULL;
847         int value = 0, count = 0, tbcount = 0, blen = 0;
848
849         beg_blen = end_blen = NULL;
850
851         /* a bitstring must contain at least 2 characters */
852         if (end - cp < 2)
853                 return(EINVAL);
854
855         /* XXX: currently, only hex strings are supported */
856         if (*cp++ != 'x')
857                 return(EINVAL);
858         if (!isxdigit((*cp) & 0xff)) /* reject '\[x/BLEN]' */
859                 return(EINVAL);
860
861         for (tp = *dst + 1; cp < end && tp < eom; cp++) {
862                 switch((c = *cp)) {
863                 case ']':       /* end of the bitstring */
864                         if (afterslash) {
865                                 if (beg_blen == NULL)
866                                         return(EINVAL);
867                                 blen = (int)strtol(beg_blen, &end_blen, 10);
868                                 if (*end_blen != ']')
869                                         return(EINVAL);
870                         }
871                         if (count)
872                                 *tp++ = ((value << 4) & 0xff);
873                         cp++;   /* skip ']' */
874                         goto done;
875                 case '/':
876                         afterslash = 1;
877                         break;
878                 default:
879                         if (afterslash) {
880                                 if (!isdigit(c&0xff))
881                                         return(EINVAL);
882                                 if (beg_blen == NULL) {
883                                         
884                                         if (c == '0') {
885                                                 /* blen never begings with 0 */
886                                                 return(EINVAL);
887                                         }
888                                         beg_blen = cp;
889                                 }
890                         } else {
891                                 if (!isxdigit(c&0xff))
892                                         return(EINVAL);
893                                 value <<= 4;
894                                 value += digitvalue[(int)c];
895                                 count += 4;
896                                 tbcount += 4;
897                                 if (tbcount > 256)
898                                         return(EINVAL);
899                                 if (count == 8) {
900                                         *tp++ = value;
901                                         count = 0;
902                                 }
903                         }
904                         break;
905                 }
906         }
907   done:
908         if (cp >= end || tp >= eom)
909                 return(EMSGSIZE);
910
911         /*
912          * bit length validation:
913          * If a <length> is present, the number of digits in the <bit-data>
914          * MUST be just sufficient to contain the number of bits specified
915          * by the <length>. If there are insignificant bits in a final
916          * hexadecimal or octal digit, they MUST be zero.
917          * RFC 2673, Section 3.2.
918          */
919         if (blen > 0) {
920                 int traillen;
921
922                 if (((blen + 3) & ~3) != tbcount)
923                         return(EINVAL);
924                 traillen = tbcount - blen; /* between 0 and 3 */
925                 if (((value << (8 - traillen)) & 0xff) != 0)
926                         return(EINVAL);
927         }
928         else
929                 blen = tbcount;
930         if (blen == 256)
931                 blen = 0;
932
933         /* encode the type and the significant bit fields */
934         **labelp = DNS_LABELTYPE_BITSTRING;
935         **dst = blen;
936
937         *bp = cp;
938         *dst = tp;
939
940         return(0);
941 }
942
943 static int
944 labellen(const u_char *lp)
945 {
946         int bitlen;
947         u_char l = *lp;
948
949         if ((l & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
950                 /* should be avoided by the caller */
951                 return(-1);
952         }
953
954         if ((l & NS_CMPRSFLGS) == NS_TYPE_ELT) {
955                 if (l == DNS_LABELTYPE_BITSTRING) {
956                         if ((bitlen = *(lp + 1)) == 0)
957                                 bitlen = 256;
958                         return((bitlen + 7 ) / 8 + 1);
959                 }
960                 return(-1);     /* unknwon ELT */
961         }
962         return(l);
963 }