Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
mapping.cpp
Go to the documentation of this file.
1#include "ada/idna/mapping.h"
2
3#include <array>
4#include <cstring>
5#include <cstdint>
6#include <string>
7
8#include "table_store.hpp"
9#include "mapping_tables.cpp"
10
11namespace ada::idna {
12
13// --- O(1) two-level table lookup ---------------------------------------------
14//
15// Returns one of:
16// IDNA_VALID - keep code point in output unchanged
17// IDNA_DISALLOWED - code point is not allowed (map() returns error)
18// IDNA_IGNORED - code point is ignored (index 0 = empty UTF-8 entry)
19// other - byte offset into idna_utf8_mappings[] (null-terminated)
20//
21// Assumes ensure_tables() has already been called by the public entry point.
22static uint16_t idna_lookup(uint32_t cp) noexcept {
23 if (cp < IDNA_LOW_RANGE_END) {
24 uint16_t ref = idna_stage1[cp >> IDNA_BLOCK_BITS];
25 if (ref & IDNA_BOOL_FLAG) {
26 uint32_t bit_idx =
27 static_cast<uint32_t>(ref & ~IDNA_BOOL_FLAG) * IDNA_BLOCK_SIZE +
28 (cp & IDNA_BLOCK_MASK);
29 bool is_valid = (idna_bool_blocks[bit_idx >> 6] >> (bit_idx & 63u)) & 1u;
30 return is_valid ? IDNA_VALID : IDNA_DISALLOWED;
31 }
32 return idna_stage2[ref + (cp & IDNA_BLOCK_MASK)];
33 }
34
36 return IDNA_IGNORED;
37 }
38
39 return IDNA_DISALLOWED;
40}
41
42// Advances *ptr past one well-formed UTF-8 code point from the mapping table.
43static char32_t utf8_next(const uint8_t*& ptr) noexcept {
44 uint8_t b0 = *ptr++;
45 if (b0 < 0x80u) return static_cast<char32_t>(b0);
46 if (b0 < 0xE0u) {
47 uint32_t cp = (b0 & 0x1Fu) << 6;
48 cp |= (*ptr++ & 0x3Fu);
49 return static_cast<char32_t>(cp);
50 }
51 if (b0 < 0xF0u) {
52 uint32_t cp = (b0 & 0x0Fu) << 12;
53 cp |= ((*ptr++ & 0x3Fu) << 6);
54 cp |= (*ptr++ & 0x3Fu);
55 return static_cast<char32_t>(cp);
56 }
57 uint32_t cp = (b0 & 0x07u) << 18;
58 cp |= ((*ptr++ & 0x3Fu) << 12);
59 cp |= ((*ptr++ & 0x3Fu) << 6);
60 cp |= (*ptr++ & 0x3Fu);
61 return static_cast<char32_t>(cp);
62}
63
64// Count UTF-8 code points in a null-terminated mapping string (trusted table).
65static size_t utf8_count_codepoints(const uint8_t* ptr) noexcept {
66 size_t n = 0;
67 while (*ptr != 0) {
68 ++n;
69 if (*ptr < 0x80u) {
70 ++ptr;
71 } else if (*ptr < 0xE0u) {
72 ptr += 2;
73 } else if (*ptr < 0xF0u) {
74 ptr += 3;
75 } else {
76 ptr += 4;
77 }
78 }
79 return n;
80}
81
82// --- ASCII fast path ---------------------------------------------------------
83void ascii_map(char* input, size_t length) {
84 auto broadcast = [](uint8_t v) -> uint64_t {
85 return 0x101010101010101ull * v;
86 };
87 uint64_t broadcast_80 = broadcast(0x80);
88 uint64_t broadcast_Ap = broadcast(128 - 'A');
89 uint64_t broadcast_Zp = broadcast(128 - 'Z' - 1);
90 size_t i = 0;
91
92 for (; i + 7 < length; i += 8) {
93 uint64_t word{};
94 std::memcpy(&word, input + i, sizeof(word));
95 word ^=
96 (((word + broadcast_Ap) ^ (word + broadcast_Zp)) & broadcast_80) >> 2;
97 std::memcpy(input + i, &word, sizeof(word));
98 }
99 if (i < length) {
100 uint64_t word{};
101 std::memcpy(&word, input + i, length - i);
102 word ^=
103 (((word + broadcast_Ap) ^ (word + broadcast_Zp)) & broadcast_80) >> 2;
104 std::memcpy(input + i, &word, length - i);
105 }
106}
107
108// Two-pass map: first validate + exact size, then write once (no growth
109// realloc).
110bool map(std::u32string_view input, std::u32string& out) {
111 // [Map](https://www.unicode.org/reports/tr46/#ProcessingStepMap).
112 out.clear();
113 if (!ensure_tables()) {
114 return false;
115 }
116
117 // Pass 1: validate and compute exact output length.
118 size_t out_size = 0;
119 for (char32_t x : input) {
120 uint16_t status = idna_lookup(static_cast<uint32_t>(x));
121 if (status == IDNA_DISALLOWED) {
122 return false;
123 }
124 if (status == IDNA_VALID) {
125 ++out_size;
126 continue;
127 }
128 if (static_cast<size_t>(status) >= idna_utf8_mappings_size) {
129 return false;
130 }
131 out_size += utf8_count_codepoints(idna_utf8_mappings + status);
132 }
133
134 // Pass 2: write into a single allocation.
135 out.resize(out_size);
136 size_t w = 0;
137 for (char32_t x : input) {
138 uint16_t status = idna_lookup(static_cast<uint32_t>(x));
139 if (status == IDNA_VALID) {
140 out[w++] = x;
141 continue;
142 }
143 // IGNORED or mapped (status already validated in pass 1).
144 const uint8_t* ptr = idna_utf8_mappings + status;
145 while (*ptr != 0) {
146 out[w++] = utf8_next(ptr);
147 }
148 }
149 return true;
150}
151
152std::u32string map(std::u32string_view input) {
153 std::u32string answer;
154 if (!map(input, answer)) {
155 return {};
156 }
157 return answer;
158}
159
160} // namespace ada::idna
void ascii_map(char *input, size_t length)
constexpr uint32_t IDNA_BLOCK_MASK
constexpr uint16_t IDNA_BOOL_FLAG
constexpr uint32_t IDNA_BLOCK_BITS
static uint16_t idna_lookup(uint32_t cp) noexcept
constexpr uint32_t IDNA_BLOCK_SIZE
constexpr uint16_t IDNA_VALID
static size_t utf8_count_codepoints(const uint8_t *ptr) noexcept
const uint16_t * idna_stage2
const uint16_t * idna_stage1
constexpr uint32_t IDNA_HIGH_IGNORED_START
bool ensure_tables() noexcept
constexpr uint32_t IDNA_LOW_RANGE_END
constexpr uint16_t IDNA_IGNORED
static char32_t utf8_next(const uint8_t *&ptr) noexcept
constexpr uint32_t IDNA_HIGH_IGNORED_END
std::u32string map(std::u32string_view input)
constexpr size_t idna_utf8_mappings_size
const uint8_t * idna_utf8_mappings
constexpr uint16_t IDNA_DISALLOWED
const uint64_t * idna_bool_blocks