Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
helpers.cpp
Go to the documentation of this file.
1#include <array>
2#include <cstdint>
3#include <cstring>
4#include <optional>
5#include <sstream>
6#include <string>
7#include <string_view>
8#include <utility>
9
10#include "ada/checkers-inl.h"
11#include "ada/common_defs.h"
12#include "ada/helpers.h"
13#include "ada/scheme.h"
14#include "ada/state.h"
15#include "ada/unicode.h"
16
17#if ADA_SSSE3
18#include <tmmintrin.h>
19#endif
20
21namespace ada::helpers {
22
23template <typename out_iter>
24void encode_json(std::string_view view, out_iter out) {
25 // trivial implementation. could be faster.
26 const char* hexvalues =
27 "000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f";
28 for (uint8_t c : view) {
29 if (c == '\\') {
30 *out++ = '\\';
31 *out++ = '\\';
32 } else if (c == '"') {
33 *out++ = '\\';
34 *out++ = '"';
35 } else if (c <= 0x1f) {
36 *out++ = '\\';
37 *out++ = 'u';
38 *out++ = '0';
39 *out++ = '0';
40 *out++ = hexvalues[2 * c];
41 *out++ = hexvalues[2 * c + 1];
42 } else {
43 *out++ = c;
44 }
45 }
46}
47
49 switch (s) {
51 return "Authority";
53 return "Scheme Start";
55 return "Scheme";
57 return "Host";
59 return "No Scheme";
61 return "Fragment";
63 return "Relative Scheme";
65 return "Relative Slash";
67 return "File";
69 return "File Host";
71 return "File Slash";
73 return "Path or Authority";
75 return "Special Authority Ignore Slashes";
77 return "Special Authority Slashes";
79 return "Special Relative or Authority";
81 return "Query";
83 return "Path";
85 return "Path Start";
87 return "Opaque Path";
89 return "Port";
90 default:
91 return "unknown state";
92 }
93}
94
95ada_really_inline std::optional<std::string_view> prune_hash(
96 std::string_view& input) noexcept {
97 // compiles down to 20--30 instructions including a class to memchr (C
98 // function). this function should be quite fast.
99 size_t location_of_first = input.find('#');
100 if (location_of_first == std::string_view::npos) {
101 return std::nullopt;
102 }
103 std::string_view hash = input;
104 hash.remove_prefix(location_of_first + 1);
105 input.remove_suffix(input.size() - location_of_first);
106 return hash;
107}
108
109ada_really_inline bool shorten_path(std::string& path, ada::scheme::type type) {
110 // Let path be url's path.
111 // If url's scheme is "file", path's size is 1, and path[0] is a normalized
112 // Windows drive letter, then return.
113 if (type == ada::scheme::type::FILE &&
114 path.find('/', 1) == std::string_view::npos && !path.empty()) {
116 helpers::substring(path, 1))) {
117 return false;
118 }
119 }
120
121 // Remove path's last item, if any.
122 size_t last_delimiter = path.rfind('/');
123 if (last_delimiter != std::string::npos) {
124 path.erase(last_delimiter);
125 return true;
126 }
127
128 return false;
129}
130
131ada_really_inline bool shorten_path(std::string_view& path,
132 ada::scheme::type type) {
133 // Let path be url's path.
134 // If url's scheme is "file", path's size is 1, and path[0] is a normalized
135 // Windows drive letter, then return.
136 if (type == ada::scheme::type::FILE &&
137 path.find('/', 1) == std::string_view::npos && !path.empty()) {
139 helpers::substring(path, 1))) {
140 return false;
141 }
142 }
143
144 // Remove path's last item, if any.
145 if (!path.empty()) {
146 size_t slash_loc = path.rfind('/');
147 if (slash_loc != std::string_view::npos) {
148 path.remove_suffix(path.size() - slash_loc);
149 return true;
150 }
151 }
152
153 return false;
154}
155
156ada_really_inline void remove_ascii_tab_or_newline(std::string& input) {
157 // Fast path: inputs with no tab/newline (the common case) avoid the
158 // per-character erase_if scan. has_tabs_or_newline uses SIMD for inputs
159 // >= 16 bytes, making this check much cheaper than erase_if's scalar
160 // predicate walk when there is nothing to remove.
161 if (!ada::unicode::has_tabs_or_newline(input)) {
162 return;
163 }
164 std::erase_if(input, ada::unicode::is_ascii_tab_or_newline);
165}
166
167ada_really_inline constexpr std::string_view substring(std::string_view input,
168 size_t pos) {
169 ADA_ASSERT_TRUE(pos <= input.size());
170 // The following is safer but unneeded if we have the above line:
171 // return pos > input.size() ? std::string_view() : input.substr(pos);
172 return input.substr(pos);
173}
174
175ada_really_inline void resize(std::string_view& input, size_t pos) noexcept {
176 ADA_ASSERT_TRUE(pos <= input.size());
177 input.remove_suffix(input.size() - pos);
178}
179
180// computes the number of trailing zeroes
181// this is a private inline function only defined in this source file.
182ada_really_inline int trailing_zeroes(uint32_t input_num) noexcept {
183#ifdef ADA_REGULAR_VISUAL_STUDIO
184 unsigned long ret;
185 // Search the mask data from least significant bit (LSB)
186 // to the most significant bit (MSB) for a set bit (1).
187 _BitScanForward(&ret, input_num);
188 return (int)ret;
189#else // ADA_REGULAR_VISUAL_STUDIO
190 return __builtin_ctzl(input_num);
191#endif // ADA_REGULAR_VISUAL_STUDIO
192}
193
194#if ADA_NEON
195// computes the number of trailing zeroes of a 64-bit word
196// this is a private inline function only defined in this source file.
197ada_really_inline int trailing_zeroes64(uint64_t input_num) noexcept {
198#ifdef ADA_REGULAR_VISUAL_STUDIO
199 unsigned long ret;
200 _BitScanForward64(&ret, input_num);
201 return (int)ret;
202#else // ADA_REGULAR_VISUAL_STUDIO
203 return __builtin_ctzll(input_num);
204#endif // ADA_REGULAR_VISUAL_STUDIO
205}
206
207// Given a NEON register whose lanes are all either 0x00 or 0xFF (i.e., the
208// result of a comparison), produce a 64-bit value with four bits set per
209// matching input byte, and zero bits elsewhere. Narrowing by four bits per
210// 16-bit lane is cheaper than materializing a 16-bit bitmask.
211//
212// With ADA_NEON_SAFE_ZERO_CHECK set to 0, the "any match?" test instead
213// treats the nibble mask as an IEEE 754 double and compares it against zero,
214// avoiding a transfer to a general-purpose register on the common no-match
215// path. Negative zero cannot occur (each byte is 0x00, 0x0F, 0xF0 or 0xFF),
216// but a mask with only low bits set is a denormal: if flush-to-zero is
217// enabled, those compare equal to 0.0. Do not use this on arbitrary vectors.
218ada_really_inline uint8x8_t to_nibble_mask(uint8x16_t comparison) noexcept {
219 return vshrn_n_u16(vreinterpretq_u16_u8(comparison), 4);
220}
221
222ada_really_inline bool any_set(uint8x8_t nibble_mask) noexcept {
223#if ADA_NEON_SAFE_ZERO_CHECK
224 return vget_lane_u64(vreinterpret_u64_u8(nibble_mask), 0) != 0;
225#else
226 return vdupd_lane_f64(vreinterpret_f64_u8(nibble_mask), 0) != 0.0;
227#endif
228}
229
230// index of the first matching byte; only meaningful when any_set is true.
231ada_really_inline size_t first_set(uint8x8_t nibble_mask) noexcept {
232 return size_t(trailing_zeroes64(
233 vget_lane_u64(vreinterpret_u64_u8(nibble_mask), 0))) >>
234 2;
235}
236#endif // ADA_NEON
237
238// starting at index location, this finds the next location of a character
239// :, /, \\, ? or [. If none is found, view.size() is returned.
240// For use within get_host_delimiter_location.
241#if ADA_SSSE3
243 std::string_view view, size_t location) noexcept {
244 // first check for short strings in which case we do it naively.
245 if (view.size() - location < 16) { // slow path
246 for (size_t i = location; i < view.size(); i++) {
247 if (view[i] == ':' || view[i] == '/' || view[i] == '\\' ||
248 view[i] == '?' || view[i] == '[') {
249 return i;
250 }
251 }
252 return size_t(view.size());
253 }
254 // fast path for long strings (expected to be common)
255 // Using SSSE3's _mm_shuffle_epi8 for table lookup (same approach as NEON)
256 size_t i = location;
257 const __m128i low_mask =
258 _mm_setr_epi8(0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
259 0x01, 0x04, 0x04, 0x00, 0x00, 0x03);
260 const __m128i high_mask =
261 _mm_setr_epi8(0x00, 0x00, 0x02, 0x01, 0x00, 0x04, 0x00, 0x00, 0x00, 0x00,
262 0x00, 0x00, 0x00, 0x00, 0x00, 0x00);
263 const __m128i fmask = _mm_set1_epi8(0xf);
264 const __m128i zero = _mm_setzero_si128();
265 for (; i + 15 < view.size(); i += 16) {
266 __m128i word = _mm_loadu_si128((const __m128i*)(view.data() + i));
267 __m128i lowpart = _mm_shuffle_epi8(low_mask, _mm_and_si128(word, fmask));
268 __m128i highpart = _mm_shuffle_epi8(
269 high_mask, _mm_and_si128(_mm_srli_epi16(word, 4), fmask));
270 __m128i classify = _mm_and_si128(lowpart, highpart);
271 __m128i is_zero = _mm_cmpeq_epi8(classify, zero);
272 // _mm_movemask_epi8 returns a 16-bit mask in bits 0-15, with bits 16-31
273 // zero. After NOT (~), bits 16-31 become 1. We must mask to 16 bits to
274 // avoid false positives.
275 int mask = ~_mm_movemask_epi8(is_zero) & 0xFFFF;
276 if (mask != 0) {
277 return i + trailing_zeroes(static_cast<uint32_t>(mask));
278 }
279 }
280 if (i < view.size()) {
281 __m128i word =
282 _mm_loadu_si128((const __m128i*)(view.data() + view.length() - 16));
283 __m128i lowpart = _mm_shuffle_epi8(low_mask, _mm_and_si128(word, fmask));
284 __m128i highpart = _mm_shuffle_epi8(
285 high_mask, _mm_and_si128(_mm_srli_epi16(word, 4), fmask));
286 __m128i classify = _mm_and_si128(lowpart, highpart);
287 __m128i is_zero = _mm_cmpeq_epi8(classify, zero);
288 // _mm_movemask_epi8 returns a 16-bit mask in bits 0-15, with bits 16-31
289 // zero. After NOT (~), bits 16-31 become 1. We must mask to 16 bits to
290 // avoid false positives.
291 int mask = ~_mm_movemask_epi8(is_zero) & 0xFFFF;
292 if (mask != 0) {
293 return view.length() - 16 + trailing_zeroes(static_cast<uint32_t>(mask));
294 }
295 }
296 return size_t(view.size());
297}
298#elif ADA_NEON
299// The ada_make_uint8x16_t macro is necessary because Visual Studio does not
300// support direct initialization of uint8x16_t. See
301// https://developercommunity.visualstudio.com/t/error-C2078:-too-many-initializers-whe/402911?q=backend+neon
302#ifndef ada_make_uint8x16_t
303#define ada_make_uint8x16_t(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, \
304 x13, x14, x15, x16) \
305 ([=]() { \
306 static uint8_t array[16] = {x1, x2, x3, x4, x5, x6, x7, x8, \
307 x9, x10, x11, x12, x13, x14, x15, x16}; \
308 return vld1q_u8(array); \
309 }())
310#endif
311
313 std::string_view view, size_t location) noexcept {
314 // first check for short strings in which case we do it naively.
315 if (view.size() - location < 16) { // slow path
316 for (size_t i = location; i < view.size(); i++) {
317 if (view[i] == ':' || view[i] == '/' || view[i] == '\\' ||
318 view[i] == '?' || view[i] == '[') {
319 return i;
320 }
321 }
322 return size_t(view.size());
323 }
324 // fast path for long strings (expected to be common)
325 size_t i = location;
326 uint8x16_t low_mask =
327 ada_make_uint8x16_t(0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
328 0x00, 0x01, 0x04, 0x04, 0x00, 0x00, 0x03);
329 uint8x16_t high_mask =
330 ada_make_uint8x16_t(0x00, 0x00, 0x02, 0x01, 0x00, 0x04, 0x00, 0x00, 0x00,
331 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00);
332 uint8x16_t fmask = vmovq_n_u8(0xf);
333 for (; i + 15 < view.size(); i += 16) {
334 uint8x16_t word = vld1q_u8((const uint8_t*)view.data() + i);
335 uint8x16_t lowpart = vqtbl1q_u8(low_mask, vandq_u8(word, fmask));
336 uint8x16_t highpart = vqtbl1q_u8(high_mask, vshrq_n_u8(word, 4));
337 // vtstq_u8 gives us 0xFF where (lowpart & highpart) is non-zero and 0x00
338 // elsewhere: unlike the plain AND, that is a proper comparison mask, which
339 // is what to_nibble_mask requires.
340 uint8x8_t matches = to_nibble_mask(vtstq_u8(lowpart, highpart));
341 if (any_set(matches)) {
342 return i + first_set(matches);
343 }
344 }
345
346 if (i < view.size()) {
347 uint8x16_t word =
348 vld1q_u8((const uint8_t*)view.data() + view.length() - 16);
349 uint8x16_t lowpart = vqtbl1q_u8(low_mask, vandq_u8(word, fmask));
350 uint8x16_t highpart = vqtbl1q_u8(high_mask, vshrq_n_u8(word, 4));
351 uint8x8_t matches = to_nibble_mask(vtstq_u8(lowpart, highpart));
352 if (any_set(matches)) {
353 return view.length() - 16 + first_set(matches);
354 }
355 }
356 return size_t(view.size());
357}
358#elif ADA_SSE2
360 std::string_view view, size_t location) noexcept {
361 // first check for short strings in which case we do it naively.
362 if (view.size() - location < 16) { // slow path
363 for (size_t i = location; i < view.size(); i++) {
364 if (view[i] == ':' || view[i] == '/' || view[i] == '\\' ||
365 view[i] == '?' || view[i] == '[') {
366 return i;
367 }
368 }
369 return size_t(view.size());
370 }
371 // fast path for long strings (expected to be common)
372 size_t i = location;
373 const __m128i mask1 = _mm_set1_epi8(':');
374 const __m128i mask2 = _mm_set1_epi8('/');
375 const __m128i mask3 = _mm_set1_epi8('\\');
376 const __m128i mask4 = _mm_set1_epi8('?');
377 const __m128i mask5 = _mm_set1_epi8('[');
378
379 for (; i + 15 < view.size(); i += 16) {
380 __m128i word = _mm_loadu_si128((const __m128i*)(view.data() + i));
381 __m128i m1 = _mm_cmpeq_epi8(word, mask1);
382 __m128i m2 = _mm_cmpeq_epi8(word, mask2);
383 __m128i m3 = _mm_cmpeq_epi8(word, mask3);
384 __m128i m4 = _mm_cmpeq_epi8(word, mask4);
385 __m128i m5 = _mm_cmpeq_epi8(word, mask5);
386 __m128i m = _mm_or_si128(
387 _mm_or_si128(_mm_or_si128(m1, m2), _mm_or_si128(m3, m4)), m5);
388 int mask = _mm_movemask_epi8(m);
389 if (mask != 0) {
390 return i + trailing_zeroes(mask);
391 }
392 }
393 if (i < view.size()) {
394 __m128i word =
395 _mm_loadu_si128((const __m128i*)(view.data() + view.length() - 16));
396 __m128i m1 = _mm_cmpeq_epi8(word, mask1);
397 __m128i m2 = _mm_cmpeq_epi8(word, mask2);
398 __m128i m3 = _mm_cmpeq_epi8(word, mask3);
399 __m128i m4 = _mm_cmpeq_epi8(word, mask4);
400 __m128i m5 = _mm_cmpeq_epi8(word, mask5);
401 __m128i m = _mm_or_si128(
402 _mm_or_si128(_mm_or_si128(m1, m2), _mm_or_si128(m3, m4)), m5);
403 int mask = _mm_movemask_epi8(m);
404 if (mask != 0) {
405 return view.length() - 16 + trailing_zeroes(mask);
406 }
407 }
408 return size_t(view.length());
409}
410#elif ADA_LSX
412 std::string_view view, size_t location) noexcept {
413 // first check for short strings in which case we do it naively.
414 if (view.size() - location < 16) { // slow path
415 for (size_t i = location; i < view.size(); i++) {
416 if (view[i] == ':' || view[i] == '/' || view[i] == '\\' ||
417 view[i] == '?' || view[i] == '[') {
418 return i;
419 }
420 }
421 return size_t(view.size());
422 }
423 // fast path for long strings (expected to be common)
424 size_t i = location;
425 const __m128i mask1 = __lsx_vrepli_b(':');
426 const __m128i mask2 = __lsx_vrepli_b('/');
427 const __m128i mask3 = __lsx_vrepli_b('\\');
428 const __m128i mask4 = __lsx_vrepli_b('?');
429 const __m128i mask5 = __lsx_vrepli_b('[');
430
431 for (; i + 15 < view.size(); i += 16) {
432 __m128i word = __lsx_vld((const __m128i*)(view.data() + i), 0);
433 __m128i m1 = __lsx_vseq_b(word, mask1);
434 __m128i m2 = __lsx_vseq_b(word, mask2);
435 __m128i m3 = __lsx_vseq_b(word, mask3);
436 __m128i m4 = __lsx_vseq_b(word, mask4);
437 __m128i m5 = __lsx_vseq_b(word, mask5);
438 __m128i m =
439 __lsx_vor_v(__lsx_vor_v(__lsx_vor_v(m1, m2), __lsx_vor_v(m3, m4)), m5);
440 int mask = __lsx_vpickve2gr_hu(__lsx_vmsknz_b(m), 0);
441 if (mask != 0) {
442 return i + trailing_zeroes(mask);
443 }
444 }
445 if (i < view.size()) {
446 __m128i word =
447 __lsx_vld((const __m128i*)(view.data() + view.length() - 16), 0);
448 __m128i m1 = __lsx_vseq_b(word, mask1);
449 __m128i m2 = __lsx_vseq_b(word, mask2);
450 __m128i m3 = __lsx_vseq_b(word, mask3);
451 __m128i m4 = __lsx_vseq_b(word, mask4);
452 __m128i m5 = __lsx_vseq_b(word, mask5);
453 __m128i m =
454 __lsx_vor_v(__lsx_vor_v(__lsx_vor_v(m1, m2), __lsx_vor_v(m3, m4)), m5);
455 int mask = __lsx_vpickve2gr_hu(__lsx_vmsknz_b(m), 0);
456 if (mask != 0) {
457 return view.length() - 16 + trailing_zeroes(mask);
458 }
459 }
460 return size_t(view.length());
461}
462#elif ADA_RVV
464 std::string_view view, size_t location) noexcept {
465 // The LUT approach was a bit slower on the SpacemiT X60, but I could see it
466 // being faster on future hardware.
467#if 0
468 // LUT generated using: s=":/\\?["; list(zip([((ord(c)>>2)&0xF)for c in s],s))
469 static const uint8_t tbl[16] = {
470 0xF, 0, 0, 0, 0, 0, '[', '\\', 0, 0, 0, '/', 0, 0, ':', '?'
471 };
472 vuint8m1_t vtbl = __riscv_vle8_v_u8m1(tbl, 16);
473#endif
474 uint8_t* src = (uint8_t*)view.data() + location;
475 for (size_t vl, n = view.size() - location; n > 0;
476 n -= vl, src += vl, location += vl) {
477 vl = __riscv_vsetvl_e8m1(n);
478 vuint8m1_t v = __riscv_vle8_v_u8m1(src, vl);
479#if 0
480 vuint8m1_t vidx = __riscv_vand(__riscv_vsrl(v, 2, vl), 0xF, vl);
481 vuint8m1_t vlut = __riscv_vrgather(vtbl, vidx, vl);
482 vbool8_t m = __riscv_vmseq(v, vlut, vl);
483#else
484 vbool8_t m1 = __riscv_vmseq(v, ':', vl);
485 vbool8_t m2 = __riscv_vmseq(v, '/', vl);
486 vbool8_t m3 = __riscv_vmseq(v, '?', vl);
487 vbool8_t m4 = __riscv_vmseq(v, '[', vl);
488 vbool8_t m5 = __riscv_vmseq(v, '\\', vl);
489 vbool8_t m = __riscv_vmor(
490 __riscv_vmor(__riscv_vmor(m1, m2, vl), __riscv_vmor(m3, m4, vl), vl),
491 m5, vl);
492#endif
493 long idx = __riscv_vfirst(m, vl);
494 if (idx >= 0) return location + idx;
495 }
496 return size_t(view.size());
497}
498#else
499// : / [ \\ ?
500static constexpr std::array<uint8_t, 256> special_host_delimiters =
501 []() consteval {
502 std::array<uint8_t, 256> result{};
503 for (int i : {':', '/', '[', '\\', '?'}) {
504 result[i] = 1;
505 }
506 return result;
507 }();
508// credit: @the-moisrex recommended a table-based approach
510 std::string_view view, size_t location) noexcept {
511 auto const str = view.substr(location);
512 for (auto pos = str.begin(); pos != str.end(); ++pos) {
513 if (special_host_delimiters[(uint8_t)*pos]) {
514 return pos - str.begin() + location;
515 }
516 }
517 return size_t(view.size());
518}
519#endif
520
521// starting at index location, this finds the next location of a character
522// :, /, ? or [. If none is found, view.size() is returned.
523// For use within get_host_delimiter_location.
524#if ADA_SSSE3
525ada_really_inline size_t find_next_host_delimiter(std::string_view view,
526 size_t location) noexcept {
527 // first check for short strings in which case we do it naively.
528 if (view.size() - location < 16) { // slow path
529 for (size_t i = location; i < view.size(); i++) {
530 if (view[i] == ':' || view[i] == '/' || view[i] == '?' ||
531 view[i] == '[') {
532 return i;
533 }
534 }
535 return size_t(view.size());
536 }
537 // fast path for long strings (expected to be common)
538 size_t i = location;
539 // Lookup tables for bit classification:
540 // ':' (0x3A): low[0xA]=0x01, high[0x3]=0x01 -> match
541 // '/' (0x2F): low[0xF]=0x02, high[0x2]=0x02 -> match
542 // '?' (0x3F): low[0xF]=0x01, high[0x3]=0x01 -> match
543 // '[' (0x5B): low[0xB]=0x04, high[0x5]=0x04 -> match
544 const __m128i low_mask =
545 _mm_setr_epi8(0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
546 0x01, 0x04, 0x00, 0x00, 0x00, 0x03);
547 const __m128i high_mask =
548 _mm_setr_epi8(0x00, 0x00, 0x02, 0x01, 0x00, 0x04, 0x00, 0x00, 0x00, 0x00,
549 0x00, 0x00, 0x00, 0x00, 0x00, 0x00);
550 const __m128i fmask = _mm_set1_epi8(0xf);
551 const __m128i zero = _mm_setzero_si128();
552
553 for (; i + 15 < view.size(); i += 16) {
554 __m128i word = _mm_loadu_si128((const __m128i*)(view.data() + i));
555 __m128i lowpart = _mm_shuffle_epi8(low_mask, _mm_and_si128(word, fmask));
556 __m128i highpart = _mm_shuffle_epi8(
557 high_mask, _mm_and_si128(_mm_srli_epi16(word, 4), fmask));
558 __m128i classify = _mm_and_si128(lowpart, highpart);
559 __m128i is_zero = _mm_cmpeq_epi8(classify, zero);
560 // _mm_movemask_epi8 returns a 16-bit mask in bits 0-15, with bits 16-31
561 // zero. After NOT (~), bits 16-31 become 1. We must mask to 16 bits to
562 // avoid false positives.
563 int mask = ~_mm_movemask_epi8(is_zero) & 0xFFFF;
564 if (mask != 0) {
565 return i + trailing_zeroes(static_cast<uint32_t>(mask));
566 }
567 }
568
569 if (i < view.size()) {
570 __m128i word =
571 _mm_loadu_si128((const __m128i*)(view.data() + view.length() - 16));
572 __m128i lowpart = _mm_shuffle_epi8(low_mask, _mm_and_si128(word, fmask));
573 __m128i highpart = _mm_shuffle_epi8(
574 high_mask, _mm_and_si128(_mm_srli_epi16(word, 4), fmask));
575 __m128i classify = _mm_and_si128(lowpart, highpart);
576 __m128i is_zero = _mm_cmpeq_epi8(classify, zero);
577 // _mm_movemask_epi8 returns a 16-bit mask in bits 0-15, with bits 16-31
578 // zero. After NOT (~), bits 16-31 become 1. We must mask to 16 bits to
579 // avoid false positives.
580 int mask = ~_mm_movemask_epi8(is_zero) & 0xFFFF;
581 if (mask != 0) {
582 return view.length() - 16 + trailing_zeroes(static_cast<uint32_t>(mask));
583 }
584 }
585 return size_t(view.size());
586}
587#elif ADA_NEON
588ada_really_inline size_t find_next_host_delimiter(std::string_view view,
589 size_t location) noexcept {
590 // first check for short strings in which case we do it naively.
591 if (view.size() - location < 16) { // slow path
592 for (size_t i = location; i < view.size(); i++) {
593 if (view[i] == ':' || view[i] == '/' || view[i] == '?' ||
594 view[i] == '[') {
595 return i;
596 }
597 }
598 return size_t(view.size());
599 }
600 // fast path for long strings (expected to be common)
601 size_t i = location;
602 uint8x16_t low_mask =
603 ada_make_uint8x16_t(0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
604 0x00, 0x01, 0x04, 0x00, 0x00, 0x00, 0x03);
605 uint8x16_t high_mask =
606 ada_make_uint8x16_t(0x00, 0x00, 0x02, 0x01, 0x00, 0x04, 0x00, 0x00, 0x00,
607 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00);
608 uint8x16_t fmask = vmovq_n_u8(0xf);
609 for (; i + 15 < view.size(); i += 16) {
610 uint8x16_t word = vld1q_u8((const uint8_t*)view.data() + i);
611 uint8x16_t lowpart = vqtbl1q_u8(low_mask, vandq_u8(word, fmask));
612 uint8x16_t highpart = vqtbl1q_u8(high_mask, vshrq_n_u8(word, 4));
613 // vtstq_u8 gives us 0xFF where (lowpart & highpart) is non-zero and 0x00
614 // elsewhere: unlike the plain AND, that is a proper comparison mask, which
615 // is what to_nibble_mask requires.
616 uint8x8_t matches = to_nibble_mask(vtstq_u8(lowpart, highpart));
617 if (any_set(matches)) {
618 return i + first_set(matches);
619 }
620 }
621
622 if (i < view.size()) {
623 uint8x16_t word =
624 vld1q_u8((const uint8_t*)view.data() + view.length() - 16);
625 uint8x16_t lowpart = vqtbl1q_u8(low_mask, vandq_u8(word, fmask));
626 uint8x16_t highpart = vqtbl1q_u8(high_mask, vshrq_n_u8(word, 4));
627 uint8x8_t matches = to_nibble_mask(vtstq_u8(lowpart, highpart));
628 if (any_set(matches)) {
629 return view.length() - 16 + first_set(matches);
630 }
631 }
632 return size_t(view.size());
633}
634#elif ADA_SSE2
635ada_really_inline size_t find_next_host_delimiter(std::string_view view,
636 size_t location) noexcept {
637 // first check for short strings in which case we do it naively.
638 if (view.size() - location < 16) { // slow path
639 for (size_t i = location; i < view.size(); i++) {
640 if (view[i] == ':' || view[i] == '/' || view[i] == '?' ||
641 view[i] == '[') {
642 return i;
643 }
644 }
645 return size_t(view.size());
646 }
647 // fast path for long strings (expected to be common)
648 size_t i = location;
649 const __m128i mask1 = _mm_set1_epi8(':');
650 const __m128i mask2 = _mm_set1_epi8('/');
651 const __m128i mask4 = _mm_set1_epi8('?');
652 const __m128i mask5 = _mm_set1_epi8('[');
653
654 for (; i + 15 < view.size(); i += 16) {
655 __m128i word = _mm_loadu_si128((const __m128i*)(view.data() + i));
656 __m128i m1 = _mm_cmpeq_epi8(word, mask1);
657 __m128i m2 = _mm_cmpeq_epi8(word, mask2);
658 __m128i m4 = _mm_cmpeq_epi8(word, mask4);
659 __m128i m5 = _mm_cmpeq_epi8(word, mask5);
660 __m128i m = _mm_or_si128(_mm_or_si128(m1, m2), _mm_or_si128(m4, m5));
661 int mask = _mm_movemask_epi8(m);
662 if (mask != 0) {
663 return i + trailing_zeroes(mask);
664 }
665 }
666 if (i < view.size()) {
667 __m128i word =
668 _mm_loadu_si128((const __m128i*)(view.data() + view.length() - 16));
669 __m128i m1 = _mm_cmpeq_epi8(word, mask1);
670 __m128i m2 = _mm_cmpeq_epi8(word, mask2);
671 __m128i m4 = _mm_cmpeq_epi8(word, mask4);
672 __m128i m5 = _mm_cmpeq_epi8(word, mask5);
673 __m128i m = _mm_or_si128(_mm_or_si128(m1, m2), _mm_or_si128(m4, m5));
674 int mask = _mm_movemask_epi8(m);
675 if (mask != 0) {
676 return view.length() - 16 + trailing_zeroes(mask);
677 }
678 }
679 return size_t(view.length());
680}
681#elif ADA_LSX
682ada_really_inline size_t find_next_host_delimiter(std::string_view view,
683 size_t location) noexcept {
684 // first check for short strings in which case we do it naively.
685 if (view.size() - location < 16) { // slow path
686 for (size_t i = location; i < view.size(); i++) {
687 if (view[i] == ':' || view[i] == '/' || view[i] == '?' ||
688 view[i] == '[') {
689 return i;
690 }
691 }
692 return size_t(view.size());
693 }
694 // fast path for long strings (expected to be common)
695 size_t i = location;
696 const __m128i mask1 = __lsx_vrepli_b(':');
697 const __m128i mask2 = __lsx_vrepli_b('/');
698 const __m128i mask4 = __lsx_vrepli_b('?');
699 const __m128i mask5 = __lsx_vrepli_b('[');
700
701 for (; i + 15 < view.size(); i += 16) {
702 __m128i word = __lsx_vld((const __m128i*)(view.data() + i), 0);
703 __m128i m1 = __lsx_vseq_b(word, mask1);
704 __m128i m2 = __lsx_vseq_b(word, mask2);
705 __m128i m4 = __lsx_vseq_b(word, mask4);
706 __m128i m5 = __lsx_vseq_b(word, mask5);
707 __m128i m = __lsx_vor_v(__lsx_vor_v(m1, m2), __lsx_vor_v(m4, m5));
708 int mask = __lsx_vpickve2gr_hu(__lsx_vmsknz_b(m), 0);
709 if (mask != 0) {
710 return i + trailing_zeroes(mask);
711 }
712 }
713 if (i < view.size()) {
714 __m128i word =
715 __lsx_vld((const __m128i*)(view.data() + view.length() - 16), 0);
716 __m128i m1 = __lsx_vseq_b(word, mask1);
717 __m128i m2 = __lsx_vseq_b(word, mask2);
718 __m128i m4 = __lsx_vseq_b(word, mask4);
719 __m128i m5 = __lsx_vseq_b(word, mask5);
720 __m128i m = __lsx_vor_v(__lsx_vor_v(m1, m2), __lsx_vor_v(m4, m5));
721 int mask = __lsx_vpickve2gr_hu(__lsx_vmsknz_b(m), 0);
722 if (mask != 0) {
723 return view.length() - 16 + trailing_zeroes(mask);
724 }
725 }
726 return size_t(view.length());
727}
728#elif ADA_RVV
729ada_really_inline size_t find_next_host_delimiter(std::string_view view,
730 size_t location) noexcept {
731 uint8_t* src = (uint8_t*)view.data() + location;
732 for (size_t vl, n = view.size() - location; n > 0;
733 n -= vl, src += vl, location += vl) {
734 vl = __riscv_vsetvl_e8m1(n);
735 vuint8m1_t v = __riscv_vle8_v_u8m1(src, vl);
736 vbool8_t m1 = __riscv_vmseq(v, ':', vl);
737 vbool8_t m2 = __riscv_vmseq(v, '/', vl);
738 vbool8_t m3 = __riscv_vmseq(v, '?', vl);
739 vbool8_t m4 = __riscv_vmseq(v, '[', vl);
740 vbool8_t m =
741 __riscv_vmor(__riscv_vmor(m1, m2, vl), __riscv_vmor(m3, m4, vl), vl);
742 long idx = __riscv_vfirst(m, vl);
743 if (idx >= 0) return location + idx;
744 }
745 return size_t(view.size());
746}
747#else
748// : / [ ?
749static constexpr std::array<uint8_t, 256> host_delimiters = []() consteval {
750 std::array<uint8_t, 256> result{};
751 for (int i : {':', '/', '?', '['}) {
752 result[i] = 1;
753 }
754 return result;
755}();
756// credit: @the-moisrex recommended a table-based approach
757ada_really_inline size_t find_next_host_delimiter(std::string_view view,
758 size_t location) noexcept {
759 auto const str = view.substr(location);
760 for (auto pos = str.begin(); pos != str.end(); ++pos) {
761 if (host_delimiters[(uint8_t)*pos]) {
762 return pos - str.begin() + location;
763 }
764 }
765 return size_t(view.size());
766}
767#endif
768
769ada_really_inline std::pair<size_t, bool> get_host_delimiter_location(
770 const bool is_special, std::string_view& view) noexcept {
779 const size_t view_size = view.size();
780 size_t location = 0;
781 bool found_colon = false;
801 if (is_special) {
802 // We move to the next delimiter.
803 location = find_next_host_delimiter_special(view, location);
804 // Unless we find '[' then we are going only going to have to call
805 // find_next_host_delimiter_special once.
806 for (; location < view_size;
807 location = find_next_host_delimiter_special(view, location)) {
808 if (view[location] == '[') {
809 location = view.find(']', location);
810 if (location == std::string_view::npos) {
811 // performance: view.find might get translated to a memchr, which
812 // has no notion of std::string_view::npos, so the code does not
813 // reflect the assembly.
814 location = view_size;
815 break;
816 }
817 } else {
818 found_colon = view[location] == ':';
819 break;
820 }
821 }
822 } else {
823 // We move to the next delimiter.
824 location = find_next_host_delimiter(view, location);
825 // Unless we find '[' then we are going only going to have to call
826 // find_next_host_delimiter_special once.
827 for (; location < view_size;
828 location = find_next_host_delimiter(view, location)) {
829 if (view[location] == '[') {
830 location = view.find(']', location);
831 if (location == std::string_view::npos) {
832 // performance: view.find might get translated to a memchr, which
833 // has no notion of std::string_view::npos, so the code does not
834 // reflect the assembly.
835 location = view_size;
836 break;
837 }
838 } else {
839 found_colon = view[location] == ':';
840 break;
841 }
842 }
843 }
844 // performance: remove_suffix may translate into a single instruction.
845 view.remove_suffix(view_size - location);
846 return {location, found_colon};
847}
848
849void trim_c0_whitespace(std::string_view& input) noexcept {
850 while (!input.empty() &&
851 ada::unicode::is_c0_control_or_space(input.front())) {
852 input.remove_prefix(1);
853 }
854 while (!input.empty() && ada::unicode::is_c0_control_or_space(input.back())) {
855 input.remove_suffix(1);
856 }
857}
858
859ada_really_inline void parse_prepared_path(std::string_view input,
861 std::string& path) {
862 ada_log("parse_prepared_path ", input);
863 uint8_t accumulator = checkers::path_signature(input);
864 // Let us first detect a trivial case.
865 // If it is special, we check that we have no dot, no %, no \ and no
866 // character needing percent encoding. Otherwise, we check that we have no %,
867 // no dot, and no character needing percent encoding.
868 constexpr uint8_t need_encoding = 1;
869 constexpr uint8_t backslash_char = 2;
870 constexpr uint8_t dot_char = 4;
871 constexpr uint8_t percent_char = 8;
872 bool special = type != ada::scheme::NOT_SPECIAL;
873 bool may_need_slow_file_handling = (type == ada::scheme::type::FILE &&
875 bool trivial_path =
876 (special ? (accumulator == 0)
877 : ((accumulator & (need_encoding | dot_char | percent_char)) ==
878 0)) &&
879 (!may_need_slow_file_handling);
880 if (accumulator == dot_char && !may_need_slow_file_handling) {
881 // '4' means that we have at least one dot, but nothing that requires
882 // percent encoding or decoding. The only part that is not trivial is
883 // that we may have single dots and double dots path segments.
884 // If we have such segments, then we either have a path that begins
885 // with '.' (easy to check), or we have the sequence './'.
886 // Note: input cannot be empty, it must at least contain one character ('.')
887 // Note: we know that '\' is not present.
888 if (input[0] != '.') {
889 size_t slashdot = 0;
890 bool dot_is_file = true;
891 for (;;) {
892 slashdot = input.find("/.", slashdot);
893 if (slashdot == std::string_view::npos) { // common case
894 break;
895 } else { // uncommon
896 // only three cases matter: /./, /.. or a final /
897 slashdot += 2;
898 dot_is_file &= !(slashdot == input.size() || input[slashdot] == '.' ||
899 input[slashdot] == '/');
900 }
901 }
902 trivial_path = dot_is_file;
903 }
904 }
905 if (trivial_path) {
906 ada_log("parse_path trivial");
907 path += '/';
908 path += input;
909 return;
910 }
911 // We are going to need to look a bit at the path, but let us see if we can
912 // ignore percent encoding *and* backslashes *and* percent characters.
913 // Except for the trivial case, this is likely to capture 99% of paths out
914 // there.
915 bool fast_path =
916 (special &&
917 (accumulator & (need_encoding | backslash_char | percent_char)) == 0) &&
918 (type != ada::scheme::type::FILE);
919 if (fast_path) {
920 ada_log("parse_prepared_path fast");
921 // Here we don't need to worry about \ or percent encoding.
922 // We also do not have a file protocol. We might have dots, however,
923 // but dots must as appear as '.', and they cannot be encoded because
924 // the symbol '%' is not present.
925 size_t previous_location = 0; // We start at 0.
926 do {
927 size_t new_location = input.find('/', previous_location);
928 // std::string_view path_view = input;
929 // We process the last segment separately:
930 if (new_location == std::string_view::npos) {
931 std::string_view path_view = input.substr(previous_location);
932 if (path_view == "..") { // The path ends with ..
933 // e.g., if you receive ".." with an empty path, you go to "/".
934 if (path.empty()) {
935 path = '/';
936 return;
937 }
938 // Fast case where we have nothing to do:
939 if (path.back() == '/') {
940 return;
941 }
942 // If you have the path "/joe/myfriend",
943 // then you delete 'myfriend'.
944 path.resize(path.rfind('/') + 1);
945 return;
946 }
947 path += '/';
948 if (path_view != ".") {
949 path.append(path_view);
950 }
951 return;
952 } else {
953 // This is a non-final segment.
954 std::string_view path_view =
955 input.substr(previous_location, new_location - previous_location);
956 previous_location = new_location + 1;
957 if (path_view == "..") {
958 size_t last_delimiter = path.rfind('/');
959 if (last_delimiter != std::string::npos) {
960 path.erase(last_delimiter);
961 }
962 } else if (path_view != ".") {
963 path += '/';
964 path.append(path_view);
965 }
966 }
967 } while (true);
968 } else {
969 ada_log("parse_path slow");
970 // we have reached the general case
971 bool needs_percent_encoding = (accumulator & 1);
972 do {
973 size_t location = (special && (accumulator & 2))
974 ? input.find_first_of("/\\")
975 : input.find('/');
976 std::string_view path_view = input;
977 if (location != std::string_view::npos) {
978 path_view.remove_suffix(path_view.size() - location);
979 input.remove_prefix(location + 1);
980 }
981 // Path encoding preserves dots and percent signs, so normalize first.
982 if (unicode::is_double_dot_path_segment(path_view)) {
983 helpers::shorten_path(path, type);
984 if (location == std::string_view::npos) {
985 path += '/';
986 }
987 } else if (unicode::is_single_dot_path_segment(path_view) &&
988 (location == std::string_view::npos)) {
989 path += '/';
990 }
991 // Otherwise, if path_view is not a single-dot path segment, then:
992 else if (!unicode::is_single_dot_path_segment(path_view)) {
993 // If url's scheme is "file", url's path is empty, and path_view is a
994 // Windows drive letter, then replace the second code point in
995 // path_view with U+003A (:).
996 if (type == ada::scheme::type::FILE && path.empty() &&
997 path_view.size() == 2 &&
999 path += '/';
1000 path += path_view[0];
1001 path += ':';
1002 path_view.remove_prefix(2);
1003 path.append(path_view);
1004 } else {
1005 // Append encoded bytes directly to the pathname.
1006 path += '/';
1007 if (!needs_percent_encoding ||
1009 path_view, character_sets::PATH_PERCENT_ENCODE, path)) {
1010 path.append(path_view);
1011 }
1012 }
1013 }
1014 if (location == std::string_view::npos) {
1015 return;
1016 }
1017 } while (true);
1018 }
1019}
1020
1021bool overlaps(std::string_view input1, const std::string& input2) noexcept {
1022 ada_log("helpers::overlaps check if string_view '", input1, "' [",
1023 input1.size(), " bytes] is part of string '", input2, "' [",
1024 input2.size(), " bytes]");
1025 return !input1.empty() && !input2.empty() && input1.data() >= input2.data() &&
1026 input1.data() < input2.data() + input2.size();
1027}
1028
1029template <class url_type>
1030ada_really_inline void strip_trailing_spaces_from_opaque_path(url_type& url) {
1031 ada_log("helpers::strip_trailing_spaces_from_opaque_path");
1032 if (!url.has_opaque_path) return;
1033 if (url.has_hash()) return;
1034 if (url.has_search()) return;
1035
1036 auto path = std::string(url.get_pathname());
1037 while (!path.empty() && path.back() == ' ') {
1038 path.resize(path.size() - 1);
1039 }
1040 url.update_base_pathname(path);
1041}
1042
1043// @ / \\ ?
1044static constexpr std::array<uint8_t, 256> authority_delimiter_special =
1045 []() consteval {
1046 std::array<uint8_t, 256> result{};
1047 for (uint8_t i : {'@', '/', '\\', '?'}) {
1048 result[i] = 1;
1049 }
1050 return result;
1051 }();
1052// credit: @the-moisrex recommended a table-based approach
1053ada_really_inline size_t
1054find_authority_delimiter_special(std::string_view view) noexcept {
1055 // performance note: we might be able to gain further performance
1056 // with SIMD intrinsics.
1057 for (auto pos = view.begin(); pos != view.end(); ++pos) {
1058 if (authority_delimiter_special[(uint8_t)*pos]) {
1059 return pos - view.begin();
1060 }
1061 }
1062 return size_t(view.size());
1063}
1064
1065// @ / ?
1066static constexpr std::array<uint8_t, 256> authority_delimiter = []() consteval {
1067 std::array<uint8_t, 256> result{};
1068 for (uint8_t i : {'@', '/', '?'}) {
1069 result[i] = 1;
1070 }
1071 return result;
1072}();
1073// credit: @the-moisrex recommended a table-based approach
1074ada_really_inline size_t
1075find_authority_delimiter(std::string_view view) noexcept {
1076 // performance note: we might be able to gain further performance
1077 // with SIMD instrinsics.
1078 for (auto pos = view.begin(); pos != view.end(); ++pos) {
1079 if (authority_delimiter[(uint8_t)*pos]) {
1080 return pos - view.begin();
1081 }
1082 }
1083 return size_t(view.size());
1084}
1085
1086} // namespace ada::helpers
1087
1088namespace ada {
1092#undef ada_make_uint8x16_t
1093} // namespace ada
Definitions for URL specific checkers used within Ada.
Cross-platform compiler macros and common definitions.
#define ADA_ASSERT_TRUE(COND)
#define ada_unused
Definition common_defs.h:88
#define ada_warn_unused
Definition common_defs.h:89
#define ada_really_inline
Definition common_defs.h:85
Definitions for helper functions used within Ada.
constexpr uint8_t PATH_PERCENT_ENCODE[32]
constexpr bool is_normalized_windows_drive_letter(std::string_view input) noexcept
constexpr bool is_windows_drive_letter(std::string_view input) noexcept
Includes the definitions for helper functions.
ada_really_inline size_t find_next_host_delimiter(std::string_view view, size_t location) noexcept
Definition helpers.cpp:757
static constexpr std::array< uint8_t, 256 > authority_delimiter_special
Definition helpers.cpp:1044
static constexpr std::array< uint8_t, 256 > host_delimiters
Definition helpers.cpp:749
ada_really_inline size_t find_next_host_delimiter_special(std::string_view view, size_t location) noexcept
Definition helpers.cpp:509
ada_unused std::string get_state(ada::state s)
Definition helpers.cpp:48
static constexpr std::array< uint8_t, 256 > authority_delimiter
Definition helpers.cpp:1066
static constexpr std::array< uint8_t, 256 > special_host_delimiters
Definition helpers.cpp:500
ada_really_inline int trailing_zeroes(uint32_t input_num) noexcept
Definition helpers.cpp:182
ada_really_inline int trailing_zeroes64(uint64_t input_num) noexcept
Definition parser.cpp:228
type
Enumeration of URL scheme types.
Definition scheme.h:43
@ NOT_SPECIAL
Definition scheme.h:45
template bool percent_encode< true >(std::string_view input, const uint8_t character_set[], std::string &out)
state
States in the URL parsing state machine.
Definition state.h:27
@ SPECIAL_RELATIVE_OR_AUTHORITY
Definition state.h:101
@ FILE_SLASH
Definition state.h:81
@ SCHEME
Definition state.h:41
@ SPECIAL_AUTHORITY_SLASHES
Definition state.h:96
@ FRAGMENT
Definition state.h:56
@ FILE_HOST
Definition state.h:76
@ OPAQUE_PATH
Definition state.h:121
@ RELATIVE_SLASH
Definition state.h:66
@ NO_SCHEME
Definition state.h:51
@ PATH_START
Definition state.h:116
@ RELATIVE_SCHEME
Definition state.h:61
@ SPECIAL_AUTHORITY_IGNORE_SLASHES
Definition state.h:91
@ SCHEME_START
Definition state.h:36
@ AUTHORITY
Definition state.h:31
@ PATH_OR_AUTHORITY
Definition state.h:86
ada_warn_unused std::string_view to_string(encoding_type type)
tl::expected< result_type, ada::errors > result
URL scheme type definitions and utilities.
URL parser state machine states.
Definitions for all unicode specific functions.