Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
punycode.cpp
Go to the documentation of this file.
1#include "ada/idna/punycode.h"
2
3#include <cstdint>
4
5namespace ada::idna {
6
7constexpr int32_t base = 36;
8constexpr int32_t tmin = 1;
9constexpr int32_t tmax = 26;
10constexpr int32_t skew = 38;
11constexpr int32_t damp = 700;
12constexpr int32_t initial_bias = 72;
13constexpr uint32_t initial_n = 128;
14
15static constexpr int32_t char_to_digit_value(char value) {
16 if (value >= 'a' && value <= 'z') return value - 'a';
17 if (value >= '0' && value <= '9') return value - '0' + 26;
18 return -1;
19}
20
21static constexpr char digit_to_char(int32_t digit) {
22 return digit < 26 ? char(digit + 97) : char(digit + 22);
23}
24
25static constexpr int32_t adapt(int32_t d, int32_t n, bool firsttime) {
26 if (firsttime) {
27 d = d / damp;
28 } else {
29 d = d / 2;
30 }
31 d += d / n;
32 int32_t k = 0;
33 while (d > ((base - tmin) * tmax) / 2) {
34 d /= base - tmin;
35 k += base;
36 }
37 return k + (((base - tmin + 1) * d) / (d + skew));
38}
39
40bool punycode_to_utf32(std::string_view input, std::u32string &out) {
41 int32_t written_out{0};
42 out.reserve(out.size() + input.size());
43 uint32_t n = initial_n;
44 int32_t i = 0;
45 int32_t bias = initial_bias;
46 // grab ascii content
47 // RFC 3492 section 6.2: copy the code points before the last delimiter,
48 // then consume the delimiter only "if more than zero code points were
49 // consumed". With a leading delimiter, b == 0, decoding starts at the
50 // delimiter itself, which is not a digit, and fails. This matches the
51 // reference implementation in appendix C (`in = b > 0 ? b + 1 : 0`).
52 size_t end_of_ascii = input.find_last_of('-');
53 if (end_of_ascii != std::string_view::npos && end_of_ascii > 0) {
54 for (uint8_t c : input.substr(0, end_of_ascii)) {
55 if (c >= 0x80) {
56 return false;
57 }
58 out.push_back(c);
59 written_out++;
60 }
61 input.remove_prefix(end_of_ascii + 1);
62 }
63 while (!input.empty()) {
64 int32_t oldi = i;
65 int32_t w = 1;
66 for (int32_t k = base;; k += base) {
67 if (input.empty()) {
68 return false;
69 }
70 uint8_t code_point = input.front();
71 input.remove_prefix(1);
72 int32_t digit = char_to_digit_value(code_point);
73 if (digit < 0) {
74 return false;
75 }
76 if (digit > (0x7fffffff - i) / w) {
77 return false;
78 }
79 i = i + digit * w;
80 int32_t t = k <= bias ? tmin : k >= bias + tmax ? tmax : k - bias;
81 if (digit < t) {
82 break;
83 }
84 if (w > 0x7fffffff / (base - t)) {
85 return false;
86 }
87 w = w * (base - t);
88 }
89 bias = adapt(i - oldi, written_out + 1, oldi == 0);
90 if (i / (written_out + 1) > int32_t(0x7fffffff - n)) {
91 return false;
92 }
93 n = n + i / (written_out + 1);
94 i = i % (written_out + 1);
95 if (n < 0x80) {
96 return false;
97 }
98 out.insert(out.begin() + i, n);
99 written_out++;
100 ++i;
101 }
102 // See https://github.com/whatwg/url/issues/803
103 // Reject labels whose decoded form begins with "xn--" (double-encoded ACE).
104 if (out.size() >= 4 && out[0] == U'x' && out[1] == U'n' && out[2] == U'-' &&
105 out[3] == U'-') {
106 return false;
107 }
108 return true;
109}
110
111bool verify_punycode(std::string_view input) {
112 // Track only the first 4 decoded code points to check for the "xn--" prefix.
113 // This avoids heap allocation while still detecting double-encoded ACE
114 // labels.
115 uint32_t first4[4]{};
116 size_t written_out{0};
117 uint32_t n = initial_n;
118 int32_t i = 0;
119 int32_t bias = initial_bias;
120 // grab ascii content
121 size_t end_of_ascii = input.find_last_of('-');
122 if (end_of_ascii != std::string_view::npos) {
123 for (uint8_t c : input.substr(0, end_of_ascii)) {
124 if (c >= 0x80) {
125 return false;
126 }
127 if (written_out < 4) {
128 first4[written_out] = c;
129 }
130 written_out++;
131 }
132 input.remove_prefix(end_of_ascii + 1);
133 }
134 while (!input.empty()) {
135 int32_t oldi = i;
136 int32_t w = 1;
137 for (int32_t k = base;; k += base) {
138 if (input.empty()) {
139 return false;
140 }
141 uint8_t code_point = input.front();
142 input.remove_prefix(1);
143 int32_t digit = char_to_digit_value(code_point);
144 if (digit < 0) {
145 return false;
146 }
147 if (digit > (0x7fffffff - i) / w) {
148 return false;
149 }
150 i = i + digit * w;
151 int32_t t = k <= bias ? tmin : k >= bias + tmax ? tmax : k - bias;
152 if (digit < t) {
153 break;
154 }
155 if (w > 0x7fffffff / (base - t)) {
156 return false;
157 }
158 w = w * (base - t);
159 }
160 bias = adapt(i - oldi, int32_t(written_out + 1), oldi == 0);
161 if (i / (written_out + 1) > 0x7fffffff - n) {
162 return false;
163 }
164 n = n + i / int32_t(written_out + 1);
165 i = i % int32_t(written_out + 1);
166 if (n < 0x80) {
167 return false;
168 }
169 // Simulate insert at position i, maintaining only the first 4 slots.
170 size_t insert_pos = size_t(i);
171 if (insert_pos < 4) {
172 for (size_t j = 3; j > insert_pos; j--) {
173 first4[j] = first4[j - 1];
174 }
175 first4[insert_pos] = n;
176 }
177 written_out++;
178 ++i;
179 }
180 // See https://github.com/whatwg/url/issues/803
181 // Reject labels whose decoded form begins with "xn--" (double-encoded ACE).
182 if (written_out >= 4 && first4[0] == U'x' && first4[1] == U'n' &&
183 first4[2] == U'-' && first4[3] == U'-') {
184 return false;
185 }
186 return true;
187}
188
189bool utf32_to_punycode(std::u32string_view input, std::string &out) {
190 out.reserve(input.size() + out.size());
191 uint32_t n = initial_n;
192 int32_t d = 0;
193 int32_t bias = initial_bias;
194 size_t h = 0;
195 // first push the ascii content
196 for (uint32_t c : input) {
197 if (c < 0x80) {
198 ++h;
199 out.push_back(char(c));
200 }
201 if (c > 0x10ffff || (c >= 0xd800 && c < 0xe000)) {
202 return false;
203 }
204 }
205 size_t b = h;
206 if (b > 0) {
207 out.push_back('-');
208 }
209 while (h < input.size()) {
210 uint32_t m = 0x10FFFF;
211 for (auto code_point : input) {
212 if (code_point >= n && code_point < m) m = code_point;
213 }
214
215 if ((m - n) > (0x7fffffff - d) / (h + 1)) {
216 return false;
217 }
218 d = d + int32_t((m - n) * (h + 1));
219 n = m;
220 for (auto c : input) {
221 if (c < n) {
222 if (d == 0x7fffffff) {
223 return false;
224 }
225 ++d;
226 }
227 if (c == n) {
228 int32_t q = d;
229 for (int32_t k = base;; k += base) {
230 int32_t t = k <= bias ? tmin : k >= bias + tmax ? tmax : k - bias;
231
232 if (q < t) {
233 break;
234 }
235 out.push_back(digit_to_char(t + ((q - t) % (base - t))));
236 q = (q - t) / (base - t);
237 }
238 out.push_back(digit_to_char(q));
239 bias = adapt(d, int32_t(h + 1), h == b);
240 d = 0;
241 ++h;
242 }
243 }
244 ++d;
245 ++n;
246 }
247 return true;
248}
249
250} // namespace ada::idna
constexpr int32_t base
static constexpr char digit_to_char(int32_t digit)
static constexpr int32_t adapt(int32_t d, int32_t n, bool firsttime)
bool punycode_to_utf32(std::string_view input, std::u32string &out)
constexpr int32_t tmin
bool utf32_to_punycode(std::u32string_view input, std::string &out)
constexpr int32_t damp
constexpr int32_t skew
constexpr uint32_t initial_n
static constexpr int32_t char_to_digit_value(char value)
constexpr int32_t initial_bias
constexpr int32_t tmax
bool verify_punycode(std::string_view input)