Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
checkers-inl.h
Go to the documentation of this file.
1
5#ifndef ADA_CHECKERS_INL_H
6#define ADA_CHECKERS_INL_H
7
8#include <bit>
9#include <cstddef>
10#include <cstdint>
11#include <string_view>
12#include "ada/checkers.h"
13#include "ada/common_defs.h"
14
15#if defined(ADA_AVX512) && defined(__AVX512VBMI2__)
16#include <immintrin.h>
17#endif
18
19namespace ada::checkers {
20
21constexpr bool is_digit(char x) noexcept { return (x >= '0') & (x <= '9'); }
22
23constexpr bool is_ipv4_number_char(char x) noexcept {
24 const unsigned char c = static_cast<unsigned char>(x);
25 return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') ||
26 (c >= 'A' && c <= 'F') || c == 'x' || c == 'X';
27}
28
29constexpr bool last_label_may_be_a_number(std::string_view view) noexcept {
30 if (view.empty()) {
31 return false;
32 }
33 const char* start = view.data();
34 const char* end = start + view.size();
35 if (end[-1] == '.') {
36 --end;
37 if (end == start) {
38 return false;
39 }
40 }
41 if (!is_ipv4_number_char(end[-1])) {
42 return false;
43 }
44 const char* label = end;
45 while (label != start && is_ipv4_number_char(label[-1])) {
46 --label;
47 }
48 if (label != start && label[-1] != '.') {
49 return false;
50 }
51 return label != end && is_digit(*label);
52}
53
54constexpr char to_lower(char x) noexcept { return (x | 0x20); }
55
56constexpr bool is_alpha(char x) noexcept {
57 return (to_lower(x) >= 'a') && (to_lower(x) <= 'z');
58}
59
60constexpr bool is_windows_drive_letter(std::string_view input) noexcept {
61 return input.size() >= 2 &&
62 (is_alpha(input[0]) && ((input[1] == ':') || (input[1] == '|'))) &&
63 ((input.size() == 2) || (input[2] == '/' || input[2] == '\\' ||
64 input[2] == '?' || input[2] == '#'));
65}
66
68 std::string_view input) noexcept {
69 return input.size() == 2 && (is_alpha(input[0]) && (input[1] == ':'));
70}
71
72namespace detail {
73
74// Unrolled pure-decimal IPv4. The common portable path for 7-16 byte hosts.
75ada_really_inline uint64_t
76parse_ipv4_decimal_scalar(const char* p, const char* pend) noexcept {
77 uint32_t ipv4 = 0;
78 for (int i = 0; i < 4; ++i) {
79 if (p == pend) [[unlikely]] {
80 return ipv4_fast_fail;
81 }
82 uint32_t val;
83 char c = *p;
84 if (c >= '0' && c <= '9') [[likely]] {
85 val = static_cast<uint32_t>(c - '0');
86 ++p;
87 } else {
88 return ipv4_fast_fail;
89 }
90 if (p < pend) {
91 c = *p;
92 if (c >= '0' && c <= '9') {
93 if (val == 0) [[unlikely]] {
94 return ipv4_fast_fail;
95 }
96 val = val * 10u + static_cast<uint32_t>(c - '0');
97 ++p;
98 if (p < pend) {
99 c = *p;
100 if (c >= '0' && c <= '9') {
101 val = val * 10u + static_cast<uint32_t>(c - '0');
102 ++p;
103 if (val > 255u) [[unlikely]] {
104 return ipv4_fast_fail;
105 }
106 }
107 }
108 }
109 }
110 ipv4 = (ipv4 << 8) | val;
111 if (i < 3) {
112 if (p == pend || *p != '.') [[unlikely]] {
113 return ipv4_fast_fail;
114 }
115 ++p;
116 }
117 }
118 if (p != pend) {
119 if (p == pend - 1 && *p == '.') {
120 return ipv4;
121 }
122 return ipv4_fast_fail;
123 }
124 return ipv4;
125}
126
127#if defined(ADA_AVX512) && defined(__AVX512VBMI2__)
128// Table-free AVX-512VL IPv4 parse (simdip parse_ipv4_avx512vl_notab5).
129// Needs VBMI2 for vpcompressb; ADA_AVX512 stays BW+VL (IPv6 does not use
130// VBMI2). Masked load of exactly `len` bytes (no over-read). Digit
131// placement is computed from compressed delimiter positions; octet > 255
132// is a dword compare on the zero-padded reversed digit group, in parallel
133// with the convert. Unusual-but-valid forms (octal, hex, leading zeros,
134// fewer than four parts) return ipv4_fast_fail so the general parser runs.
135ada_really_inline uint64_t try_parse_ipv4_avx512(const char* data,
136 size_t len) noexcept {
137 // One trailing dot is WHATWG-legal ("1.2.3.4."); the SIMD kernel is
138 // strict four-group dotted-decimal.
139 if (data[len - 1] == '.') {
140 --len;
141 }
142 if (len > 15) [[unlikely]] {
143 return ipv4_fast_fail;
144 }
145
146#if defined(__BMI2__)
147 const uint32_t len_mask = _bzhi_u32(0xFFFFFFFFu, static_cast<unsigned>(len));
148#else
149 const uint32_t len_mask = (1u << static_cast<unsigned>(len)) - 1u;
150#endif
151 const __mmask16 len_k = static_cast<__mmask16>(len_mask);
152 const __m128i dot = _mm_set1_epi8('.');
153 const __m128i v =
154 _mm_mask_loadu_epi8(dot, len_k, reinterpret_cast<const void*>(data));
155
156 const __mmask16 delim = _mm_cmpeq_epi8_mask(v, dot);
157 const uint32_t dots = static_cast<uint32_t>(delim) & len_mask;
158 const uint32_t keep = len_mask & ~dots;
159
160 const __m128i zero = _mm_set1_epi8('0');
161 const __m128i digits = _mm_sub_epi8(v, zero);
162 const __mmask16 is_digit = _mm_cmple_epu8_mask(digits, _mm_set1_epi8(9));
163 // Junk in a digit slot: inside [0, len) yet neither a digit nor a dot.
164 const __mmask16 hole = _kandn_mask16(_kor_mask16(delim, is_digit), len_k);
165 const __m128i v0 = _mm_maskz_mov_epi8(is_digit, digits);
166
167 const __m128i iota =
168 _mm_setr_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
169 const __m128i c = _mm_maskz_compress_epi8(delim, iota);
170 const __m128i k_rep =
171 _mm_setr_epi8(0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3);
172 const __m128i qi = _mm_shuffle_epi8(c, k_rep);
173 const __m128i prev =
174 _mm_shuffle_epi8(_mm_alignr_epi8(c, _mm_set1_epi8(-1), 15), k_rep);
175 // Reversed group order: lane 4i+j fetches q_i-(j+1), so the dword is
176 // ones | tens<<8 | hundreds<<16, monotone in the decimal value.
177 const __m128i offr = _mm_setr_epi8(-1, -2, -3, -4, -1, -2, -3, -4, -1, -2, -3,
178 -4, -1, -2, -3, -4);
179 const __m128i idx = _mm_max_epi8(_mm_add_epi8(qi, offr), prev);
180 const __m128i padded = _mm_shuffle_epi8(v0, idx);
181
182 const __m128i lim =
183 _mm_setr_epi8(5, 5, 2, 0, 5, 5, 2, 0, 5, 5, 2, 0, 5, 5, 2, 0);
184 const __mmask8 over = _mm_cmpgt_epu32_mask(padded, lim);
185 const __m128i wtsr =
186 _mm_setr_epi8(1, 10, 100, 0, 1, 10, 100, 0, 1, 10, 100, 0, 1, 10, 100, 0);
187#if defined(__AVX512VNNI__)
188 const __m128i res = _mm_dpbusd_epi32(_mm_setzero_si128(), padded, wtsr);
189#else
190 const __m128i res =
191 _mm_madd_epi16(_mm_maddubs_epi16(padded, wtsr), _mm_set1_epi16(1));
192#endif
193
194 const __m128i gmin =
195 _mm_setr_epi8(1, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
196 const __m128i gmax =
197 _mm_setr_epi8(2, 2, 2, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1);
198 const __m128i gap = _mm_sub_epi8(c, _mm_slli_si128(c, 1));
199 const __mmask16 bad_gap = _mm_cmpgt_epu8_mask(_mm_sub_epi8(gap, gmin), gmax);
200
201 const uint32_t zero_bits =
202 static_cast<uint32_t>(_mm_cmpeq_epi8_mask(v, zero));
203 const uint32_t start_bits = (dots << 1) | 1u;
204
205 const __mmask16 kerr =
206 _kor_mask16(_kor_mask16(hole, static_cast<__mmask16>(over)), bad_gap);
207 const uint32_t gerr = static_cast<uint32_t>(_mm_popcnt_u32(dots) ^ 3u) |
208 (zero_bits & start_bits & (keep >> 1));
209
210 if ((gerr | static_cast<uint32_t>(kerr)) == 0) [[likely]] {
211 const uint32_t packed =
212 static_cast<uint32_t>(_mm_cvtsi128_si32(_mm_cvtepi32_epi8(res)));
213#if defined(__GNUC__) || defined(__clang__)
214 return static_cast<uint64_t>(__builtin_bswap32(packed));
215#else
216 return static_cast<uint64_t>(_byteswap_ulong(packed));
217#endif
218 }
219 return ipv4_fast_fail;
220}
221#endif // ADA_AVX512 && __AVX512VBMI2__
222
223} // namespace detail
224
234ada_really_inline uint64_t
235try_parse_ipv4_fast(std::string_view input) noexcept {
236 const size_t len = input.size();
237 // Shortest pure decimal: "0.0.0.0" (7). Longest + trailing dot: 16.
238 if (len < 7 || len > 16) [[unlikely]] {
239 return ipv4_fast_fail;
240 }
241 const char* data = input.data();
242
243#if defined(ADA_AVX512) && defined(__AVX512VBMI2__)
244 return detail::try_parse_ipv4_avx512(data, len);
245#else
246 return detail::parse_ipv4_decimal_scalar(data, data + len);
247#endif
248}
249
250} // namespace ada::checkers
251
252#endif // ADA_CHECKERS_INL_H
Declarations for URL specific checkers used within Ada.
Cross-platform compiler macros and common definitions.
#define ada_really_inline
Definition common_defs.h:85
ada_really_inline uint64_t parse_ipv4_decimal_scalar(const char *p, const char *pend) noexcept
Includes the definitions for validation functions.
constexpr bool last_label_may_be_a_number(std::string_view view) noexcept
constexpr bool is_normalized_windows_drive_letter(std::string_view input) noexcept
constexpr bool is_windows_drive_letter(std::string_view input) noexcept
constexpr bool is_ipv4_number_char(char x) noexcept
constexpr char to_lower(char x) noexcept
constexpr uint64_t ipv4_fast_fail
Definition checkers.h:128
ada_really_inline uint64_t try_parse_ipv4_fast(std::string_view input) noexcept
constexpr bool is_alpha(char x) noexcept
constexpr bool is_digit(char x) noexcept