Home | History | Annotate | Line # | Download | only in generic 
      1 /*
      2  * name.h -- domain name parser
      3  *
      4  * Copyright (c) 2022-2023, NLnet Labs. All rights reserved.
      5  *
      6  * SPDX-License-Identifier: BSD-3-Clause
      7  *
      8  */
      9 #ifndef NAME_H
     10 #define NAME_H
     11 
     12 typedef struct name_block name_block_t;
     13 struct name_block {
     14   uint64_t backslashes;
     15   uint64_t dots;
     16 };
     17 
     18 nonnull_all
     19 static really_inline void copy_name_block(
     20   name_block_t *block, const char *text, uint8_t *wire)
     21 {
     22   simd_8x32_t input;
     23   simd_loadu_8x32(&input, text);
     24   simd_storeu_8x32(wire, &input);
     25   block->backslashes = simd_find_8x32(&input, '\\');
     26   block->dots = simd_find_8x32(&input, '.');
     27 }
     28 
     29 nonnull_all
     30 static really_inline int32_t scan_name(
     31   const char *data,
     32   size_t tlength,
     33   uint8_t octets[255 + ZONE_BLOCK_SIZE],
     34   size_t *lengthp)
     35 {
     36   uint64_t label = 0;
     37   const char *text = data;
     38   uint8_t *wire = octets + 1;
     39   name_block_t block;
     40 
     41   octets[0] = 0;
     42 
     43   // real world domain names quickly exceed 16 octets (www.example.com is
     44   // encoded as 3www7example3com0, or 18 octets), but rarely exceed 32
     45   // octets. encode in 32-byte blocks.
     46   copy_name_block(&block, text, wire);
     47 
     48   uint64_t count = 32, length = 0, base = 0, left = tlength;
     49   uint64_t carry = 0;
     50   if (tlength < 32)
     51     count = tlength;
     52   uint64_t mask = (1llu << count) - 1u;
     53 
     54   // check for escape sequences
     55   if (unlikely(block.backslashes & mask))
     56     goto escaped;
     57 
     58   // check for root, i.e. "."
     59   if (unlikely(block.dots & 1llu))
     60     return ((*lengthp = tlength) == 1 ? 0 : -1);
     61 
     62   length = count;
     63   block.dots &= mask;
     64   carry = (block.dots >> (length - 1));
     65 
     66   // check for null labels, i.e. ".."
     67   if (unlikely(block.dots & (block.dots >> 1)))
     68     return -1;
     69 
     70   if (likely(block.dots)) {
     71     count = trailing_zeroes(block.dots);
     72     block.dots = clear_lowest_bit(block.dots);
     73     octets[label] = (uint8_t)count;
     74     label = count + 1;
     75     while (block.dots) {
     76       count = trailing_zeroes(block.dots);
     77       block.dots = clear_lowest_bit(block.dots);
     78       octets[label] = (uint8_t)(count - label);
     79       label = count + 1;
     80     }
     81   }
     82 
     83   octets[label] = (uint8_t)(length - label);
     84 
     85   if (tlength <= 32)
     86     return (void)(*lengthp = length + 1), carry == 0;
     87 
     88   text += length;
     89   wire += length;
     90   left -= length;
     91 
     92   do {
     93     copy_name_block(&block, text, wire);
     94     count = 32;
     95     if (left < 32)
     96       count = left;
     97     mask = (1llu << count) - 1u;
     98     base = length;
     99 
    100     // check for escape sequences
    101     if (unlikely(block.backslashes & mask)) {
    102 escaped:
    103       block.backslashes &= -block.backslashes;
    104       mask = block.backslashes - 1;
    105       block.dots &= mask;
    106       count = count_ones(mask);
    107       const uint32_t octet = unescape(text+count, wire+count);
    108       if (!octet)
    109         return -1;
    110       text += count + octet;
    111       wire += count + 1;
    112       length += count + 1;
    113       left -= count + octet;
    114       count += 1; // for correct carry
    115     } else {
    116       block.dots &= mask;
    117       text += count;
    118       wire += count;
    119       length += count;
    120       left -= count;
    121     }
    122 
    123     // check for null labels, i.e. ".."
    124     if (unlikely(block.dots & ((block.dots >> 1) | carry)))
    125       return -1;
    126     carry = block.dots >> (count - 1);
    127 
    128     if (likely(block.dots)) {
    129       count = trailing_zeroes(block.dots) + base;
    130       block.dots = clear_lowest_bit(block.dots);
    131       octets[label] = (uint8_t)(count - label);
    132       // check if label exceeds 63 octets
    133       if (unlikely(count - label > 63))
    134         return -1;
    135       label = count + 1;
    136       while (block.dots) {
    137         count = trailing_zeroes(block.dots) + base;
    138         block.dots = clear_lowest_bit(block.dots);
    139         octets[label] = (uint8_t)(count - label);
    140         label = count + 1;
    141       }
    142     } else {
    143       // check if label exceeds 63 octets
    144       if (length - label > 63)
    145         return -1;
    146     }
    147 
    148     octets[label] = (uint8_t)(length - label);
    149   } while (left && length < 255);
    150 
    151   if (length >= 255)
    152     return -1;
    153 
    154   *lengthp = length + 1;
    155   return carry == 0;
    156 }
    157 
    158 #endif // NAME_H
    159