forked from NLnetLabs/nsd
-
Notifications
You must be signed in to change notification settings - Fork 3
/
qp-bits.c
77 lines (68 loc) · 2.08 KB
/
qp-bits.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
* qp-trie - a DNS-specific quelques-bits popcount trie for NSD
*
* Generate the table that maps bytes in DNS names to bit positions.
*
* Written by Tony Finch <dot@dotat.at>
* See LICENSE for the license.
*/
#include "config.h"
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include "dname.h"
#include "qp-trie.h"
#include "qp-bits.h"
/*
* Generate the table that maps bytes in DNS names to bit positions.
*
* The bit positions have to be between SHIFT_BITMAP and SHIFT_OFFSET.
* Escaped byte ranges mostly fit in this space, except for those
* above 'z', so when we reach the max we roll over to the next escape
* character. After filling the table we ensure that the bit positions
* for hostname characters and escape characters all fit.
*
* A few non-hostname characters (between '-' and the digits, and
* between '_' and lower case letters) are treated the same way as
* hostname characters so that the escaped ranges are simpler.
*/
int main(void) {
qp_shift bit_one = SHIFT_BITMAP;
qp_shift bit_two = SHIFT_BITMAP;
bool escaping = true;
printf("/*\n"
" * Lookup table mapping bytes in DNS names to bit positions\n"
" * generated by qp-bits.c\n"
" */\n"
"static const uint16_t byte_to_bits[256] = {\n");
for(unsigned byte = 0; byte < 256; byte++) {
if (('-' <= byte && byte <= '9') ||
('_' <= byte && byte <= 'z')) {
// common characters
escaping = false;
bit_one++;
printf("\t 0x%02x,", bit_one);
} else if('A' <= byte && byte <= 'Z') {
// map upper case to lower case
printf("\t 0x%02x,",
(bit_one + 1) + // bump past escape character
('a' - '_') + // and skip non-letters
(byte - 'A')); // count the alphabet
} else {
// non-hostname characters need to be escaped
if(!escaping || bit_two >= SHIFT_OFFSET) {
escaping = true;
bit_one++;
bit_two = SHIFT_BITMAP;
}
printf("\t0x%04x,", bit_two << 8 | bit_one);
bit_two++;
}
if((byte & 7) == 7)
printf("\n");
}
assert(bit_one < SHIFT_OFFSET);
printf("};\n");
return(0);
}