Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
url_ip-inl.h
Go to the documentation of this file.
1
8#ifndef ADA_URL_IP_INL_H
9#define ADA_URL_IP_INL_H
10
11#include "ada/common_defs.h"
12
13#include <array>
14#include <cstddef>
15#include <cstdint>
16
17// The IPv6 kernel needs vpermi2b/vpermb (VBMI) and vpcompressb/vpexpandb
18// (VBMI2) on top of ADA_AVX512's BW+VL.
19#if defined(ADA_AVX512) && defined(__AVX512VBMI__) && defined(__AVX512VBMI2__)
20#define ADA_AVX512_IPV6 1
21#endif
22
23#if defined(ADA_AVX512)
24#include <immintrin.h>
25#endif
26
27namespace ada::detail {
28
29// 256-entry: 0xff = not hex, else nibble value.
30inline constexpr std::array<uint8_t, 256> make_hex_nibble_table() noexcept {
31 std::array<uint8_t, 256> t{};
32 for (size_t i = 0; i < 256; ++i) {
33 t[i] = 0xff;
34 }
35 for (size_t d = 0; d < 10; ++d) {
36 t[size_t{'0'} + d] = static_cast<uint8_t>(d);
37 }
38 for (size_t d = 0; d < 6; ++d) {
39 t[size_t{'a'} + d] = static_cast<uint8_t>(10 + d);
40 t[size_t{'A'} + d] = static_cast<uint8_t>(10 + d);
41 }
42 return t;
43}
44
45inline constexpr auto hex_nibble = make_hex_nibble_table();
46
47inline bool parse_ipv4_number(const char*& p, const char* end, uint64_t& value,
48 bool& is_pure_decimal) noexcept {
49 is_pure_decimal = false;
50 if (p >= end) [[unlikely]] {
51 return false;
52 }
53 if (end - p >= 2 && p[0] == '0' && ((p[1] | 0x20) == 'x')) {
54 p += 2;
55 if (p == end || *p == '.') {
56 value = 0;
57 return true;
58 }
59 uint64_t v = 0;
60 int digits = 0;
61 while (p < end && *p != '.') {
62 const uint8_t nib = hex_nibble[static_cast<unsigned char>(*p)];
63 if (nib == 0xff) [[unlikely]] {
64 return false;
65 }
66 if (v > (0xFFFFFFFFULL >> 4)) [[unlikely]] {
67 return false;
68 }
69 v = (v << 4) | nib;
70 ++p;
71 ++digits;
72 }
73 if (digits == 0) [[unlikely]] {
74 return false;
75 }
76 value = v;
77 return true;
78 }
79 if (end - p >= 2 && p[0] == '0' && p[1] >= '0' && p[1] <= '9') {
80 ++p;
81 uint64_t v = 0;
82 while (p < end && *p != '.') {
83 const char c = *p;
84 if (c < '0' || c > '7') [[unlikely]] {
85 return false;
86 }
87 if (v > (0xFFFFFFFFULL >> 3)) [[unlikely]] {
88 return false;
89 }
90 v = (v << 3) | static_cast<uint64_t>(c - '0');
91 ++p;
92 }
93 value = v;
94 return true;
95 }
96 if (*p < '0' || *p > '9') [[unlikely]] {
97 return false;
98 }
99 is_pure_decimal = true;
100 uint64_t v = static_cast<uint64_t>(*p - '0');
101 ++p;
102 while (p < end && *p != '.') {
103 const char c = *p;
104 if (c < '0' || c > '9') [[unlikely]] {
105 return false;
106 }
107 if (v > 429496729ULL) [[unlikely]] {
108 return false;
109 }
110 v = v * 10u + static_cast<uint64_t>(c - '0');
111 if (v > 0xFFFFFFFFULL) [[unlikely]] {
112 return false;
113 }
114 ++p;
115 }
116 value = v;
117 return true;
118}
119
120// Parse up to 4 hex digits. Returns digit count (0 if none).
121inline int parse_hex_piece(const char*& pointer, const char* end,
122 uint16_t& value) noexcept {
123 if (pointer == end) {
124 return 0;
125 }
126 const uint8_t n0 = hex_nibble[static_cast<unsigned char>(*pointer)];
127 if (n0 == 0xff) {
128 return 0;
129 }
130 uint32_t v = n0;
131 ++pointer;
132 int length = 1;
133 if (pointer != end) {
134 const uint8_t n1 = hex_nibble[static_cast<unsigned char>(*pointer)];
135 if (n1 != 0xff) {
136 v = (v << 4) | n1;
137 ++pointer;
138 ++length;
139 if (pointer != end) {
140 const uint8_t n2 = hex_nibble[static_cast<unsigned char>(*pointer)];
141 if (n2 != 0xff) {
142 v = (v << 4) | n2;
143 ++pointer;
144 ++length;
145 if (pointer != end) {
146 const uint8_t n3 = hex_nibble[static_cast<unsigned char>(*pointer)];
147 if (n3 != 0xff) {
148 v = (v << 4) | n3;
149 ++pointer;
150 ++length;
151 }
152 }
153 }
154 }
155 }
156 }
157 value = static_cast<uint16_t>(v);
158 return length;
159}
160
161#if defined(ADA_AVX512_IPV6)
162// Gather each group's up-to-four nibbles and fold them into eight hextets.
163// `prev` is the byte before each group, so an index that runs off the front of
164// a short group clamps onto a colon, which translates to zero: no write mask.
165ada_really_inline void ipv6_gather(__m128i ends, __m128i prev, __m512i nib,
166 std::array<uint16_t, 8>& address) noexcept {
167 const __m256i grp =
168 _mm256_setr_epi8(0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
169 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7);
170 const __m256i off = _mm256_setr_epi8(
171 -4, -3, -2, -1, -4, -3, -2, -1, -4, -3, -2, -1, -4, -3, -2, -1, -4, -3,
172 -2, -1, -4, -3, -2, -1, -4, -3, -2, -1, -4, -3, -2, -1);
173 const __m256i idx = _mm256_max_epi8(
174 _mm256_add_epi8(
175 _mm256_permutexvar_epi8(grp, _mm256_castsi128_si256(ends)), off),
176 _mm256_permutexvar_epi8(grp, _mm256_castsi128_si256(prev)));
177 const __m256i gathered = _mm512_castsi512_si256(
178 _mm512_permutexvar_epi8(_mm512_castsi256_si512(idx), nib));
179 // (a,b) -> 16a+b are the sixteen address bytes; 256*hi+lo pairs them.
180 const __m256i hextets = _mm256_madd_epi16(
181 _mm256_maddubs_epi16(gathered, _mm256_set1_epi16(0x0110)),
182 _mm256_set1_epi32(0x00010100));
183 _mm_storeu_si128(reinterpret_cast<__m128i*>(address.data()),
184 _mm256_cvtepi32_epi16(hextets));
185}
186
187// Parse an IPv6 host with one masked 512-bit load. Derived from
188// vtlmks/ipv6-avx512 (Peter Fors, MIT).
189//
190// Returns false when the input is outside this kernel's grammar and the caller
191// must run the scalar parser. Otherwise `valid` receives the verdict, and
192// `address` the eight hextets when valid.
193ada_really_inline bool try_parse_ipv6_avx512(const char* data, size_t len,
194 std::array<uint16_t, 8>& address,
195 bool& valid) noexcept {
196 if (len < 2 || len > 45) [[unlikely]] {
197 return false;
198 }
199 // ':' rather than 0x80 for the colon, so a clamped index reads a zero nibble.
200 alignas(64) static constexpr uint8_t hex_lo[64] = {
201 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
202 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
203 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
204 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
205 0x80, 0x80, 0x80, 0x80, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
206 0x07, 0x08, 0x09, 0x00, 0x80, 0x80, 0x80, 0x80, 0x80};
207 alignas(64) static constexpr uint8_t hex_hi[64] = {
208 0x80, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x80, 0x80, 0x80, 0x80,
209 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
210 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
211 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x80, 0x80, 0x80, 0x80, 0x80,
212 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
213 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80};
214 alignas(64) static constexpr uint8_t iota[64] = {
215 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
216 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
217 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
218 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63};
219
220 const __mmask64 active =
221 static_cast<__mmask64>(_bzhi_u64(~0ULL, static_cast<uint32_t>(len)));
222 const __m512i colon = _mm512_set1_epi8(':');
223 // Merging ':' into the tail makes the terminator at `len` a real colon, so
224 // the compress mask below never has to be rebuilt in a general register.
225 const __m512i v = _mm512_mask_loadu_epi8(colon, active, data);
226 const __mmask64 mcolon = _mm512_cmpeq_epi8_mask(v, colon);
227
228 // An embedded dotted quad is the one valid form this kernel does not cover.
229 // Because that is the only gap, every other input it does not accept is
230 // invalid, which is what makes `valid = false` below safe.
231 if (_mm512_cmpeq_epi8_mask(v, _mm512_set1_epi8('.'))) [[unlikely]] {
232 return false;
233 }
234
235 const __m512i nib = _mm512_permutex2var_epi8(_mm512_load_si512(hex_lo), v,
236 _mm512_load_si512(hex_hi));
237 const __m128i comp = _mm512_castsi512_si128(
238 _mm512_maskz_compress_epi8(mcolon, _mm512_load_si512(iota)));
239 const __m128i lane0 =
240 _mm_setr_epi8(-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
241 const __m128i prev = _mm_or_si128(_mm_bslli_si128(comp, 1), lane0);
242 const __m128i width = _mm_sub_epi8(comp, prev); // one too large
243
244 const uint64_t mc = static_cast<uint64_t>(mcolon);
245 const uint64_t act = static_cast<uint64_t>(active);
246 const uint64_t dc = mc & (mc >> 1) & (act >> 1); // a "::" inside [0, len)
247
248 if (!dc) {
249 ipv6_gather(comp, prev, nib, address);
250 // nib | (v & 0x80): one scan for non-hex bytes and for bytes whose high
251 // bit made vpermi2b alias a legal one.
252 const __m512i fused = _mm512_ternarylogic_epi32(
253 nib, v, _mm512_set1_epi8(static_cast<char>(0x80)), 0xf8);
254 // Lanes 8..15 bound against 255, which an unsigned byte cannot exceed.
255 const __m128i wmax =
256 _mm_setr_epi8(3, 3, 3, 3, 3, 3, 3, 3, -1, -1, -1, -1, -1, -1, -1, -1);
257 __mmask64 err = _kandn_mask64(mcolon, _mm512_movepi8_mask(fused));
258 err = _kor_mask64(
259 err, static_cast<__mmask64>(static_cast<uint16_t>(_mm_cmpgt_epu8_mask(
260 _mm_sub_epi8(width, _mm_set1_epi8(2)), wmax))));
261 valid = (_mm_popcnt_u64(mc & act) == 7) && !err;
262 return true;
263 }
264
265 // Drop the zero-width gap field(s), then expand the surviving head and tail
266 // fields into eight slots with all-zero groups inserted at the gap.
267 const uint32_t head = static_cast<uint32_t>(_mm_popcnt_u64(mc & (dc - 1))) +
268 static_cast<uint32_t>(dc > 1);
269 const __mmask16 keep = _mm_cmpgt_epi8_mask(width, _mm_set1_epi8(1));
270 const uint32_t kept = static_cast<uint32_t>(_mm_popcnt_u32(keep));
271 const __mmask16 slots = static_cast<__mmask16>(
272 ~(_bzhi_u32(0xFFFFFFFFu, 8 - kept) << head) & 0xFFu);
273 // Inserted groups take prev = -1, so their indices clamp to byte 63, a tail
274 // colon, and read zero.
275 ipv6_gather(_mm_maskz_expand_epi8(slots, _mm_maskz_compress_epi8(keep, comp)),
276 _mm_mask_expand_epi8(_mm_set1_epi8(-1), slots,
277 _mm_maskz_compress_epi8(keep, prev)),
278 nib, address);
279
280 uint64_t err = _mm512_movepi8_mask(v); // high-bit bytes
281 err |= _mm512_movepi8_mask(nib) & ~mc; // non-hex
282 err |= _blsr_u64(dc); // a second "::"
283 err |= static_cast<uint64_t>(kept >= 8); // "::" elides nothing
284 err |= _mm_cmpgt_epu8_mask(width, _mm_set1_epi8(5)) & keep; // group > 4
285 err |= (mc & 1ULL) & ~dc; // leading lone ':'
286 err |= ((mc >> (len - 1)) & 1ULL) & ~(dc >> (len - 2)); // trailing lone ':'
287 valid = !err;
288 return true;
289}
290#endif // ADA_AVX512_IPV6
291
292} // namespace ada::detail
293
294#endif // ADA_URL_IP_INL_H
Cross-platform compiler macros and common definitions.
#define ada_really_inline
Definition common_defs.h:85
bool parse_ipv4_number(const char *&p, const char *end, uint64_t &value, bool &is_pure_decimal) noexcept
Definition url_ip-inl.h:47
int parse_hex_piece(const char *&pointer, const char *end, uint16_t &value) noexcept
Definition url_ip-inl.h:121
constexpr std::array< uint8_t, 256 > make_hex_nibble_table() noexcept
Definition url_ip-inl.h:30
constexpr auto hex_nibble
Definition url_ip-inl.h:45