Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
unicode_percent_encode.cpp
Go to the documentation of this file.
1#include <cstdint>
2
3#include "ada/unicode.h"
4
7#include "ada/common_defs.h"
8
9#include <cstring>
10#include <string>
11#if ADA_SSSE3
12#include <tmmintrin.h>
13#define ADA_UNICODE_SSSE3 1
14#elif ADA_NEON
15#include <arm_neon.h>
16#elif ADA_RVV
17#include <riscv_vector.h>
18#endif
19
20// gcc/clang honor target("ssse3") on an SSE2 translation unit. clang-cl and
21// MSVC do not: they still compile the function as SSE2, then reject
22// always_inline _mm_shuffle_epi8. Same approach as parser.cpp.
23#if !ADA_UNICODE_SSSE3 && (defined(__x86_64__) || defined(__amd64__)) && \
24 defined(__GNUC__) && !defined(_MSC_VER)
25#include <tmmintrin.h>
26#define ADA_UNICODE_SSSE3 1
27#define ADA_UNICODE_NEED_SSSE3_TARGET 1
28#endif
29#ifndef ADA_UNICODE_SSSE3
30#define ADA_UNICODE_SSSE3 0
31#endif
32#ifdef ADA_UNICODE_NEED_SSSE3_TARGET
33// noinline: these functions must not be inlined into a caller that also
34// contains the CPU check. A target("ssse3") function can use SSSE3 in its
35// prologue, before any check inside it would run.
36#define ADA_UNICODE_SIMD __attribute__((target("ssse3"), noinline))
37#else
38#define ADA_UNICODE_SIMD ada_really_inline
39#endif
40
41#ifdef ADA_REGULAR_VISUAL_STUDIO
42#include <intrin.h>
43#endif
44
45namespace ada::unicode {
46namespace {
47
48#if ADA_UNICODE_SSSE3 || ADA_NEON
49ada_really_inline int trailing_zeroes32(uint32_t input_num) noexcept {
50#ifdef ADA_REGULAR_VISUAL_STUDIO
51 unsigned long ret;
52 _BitScanForward(&ret, input_num);
53 return static_cast<int>(ret);
54#else
55 return __builtin_ctz(input_num);
56#endif
57}
58
59// Append one window whose set bits mark bytes that need encoding.
60ada_really_inline void encode_mask_window(const char* p, uint32_t mask,
61 size_t width, std::string& out) {
62 uint64_t bits = mask;
63 size_t off = 0;
64 while (bits != 0) {
65 const int zero_run = trailing_zeroes32(static_cast<uint32_t>(bits));
66 if (zero_run != 0) {
67 out.append(p + off, static_cast<size_t>(zero_run));
68 }
69 off += static_cast<size_t>(zero_run);
70 out.append(character_sets::hex + uint8_t(p[off]) * 4, 3);
71 ++off;
72 bits >>= static_cast<unsigned>(zero_run + 1);
73 }
74 if (off < width) {
75 out.append(p + off, width - off);
76 }
77}
78#endif // ADA_UNICODE_SSSE3 || ADA_NEON
79
80ada_really_inline void percent_encode_to_scalar(const char* p, const char* end,
81 const uint8_t character_set[],
82 std::string& out) {
83 for (; p != end; ++p) {
84 if (character_sets::bit_at(character_set, *p)) {
85 out.append(character_sets::hex + uint8_t(*p) * 4, 3);
86 } else {
87 out += *p;
88 }
89 }
90}
91
92#if ADA_UNICODE_SSSE3
93// Classify 16 input bytes against the 32-byte character_set bitmap:
94// bit_at(cs, b) == cs[b >> 3] & (1 << (b & 7)). pshufb looks up the two
95// 16-byte halves of that bitmap; no per-call nibble table is built.
96struct ssse3_percent_tables {
97 __m128i cs_lo;
98 __m128i cs_hi;
99 __m128i pow2;
100 __m128i mask_0f;
101 __m128i mask_07;
102 __m128i zero;
103};
104
105ADA_UNICODE_SIMD ssse3_percent_tables
106load_ssse3_percent_tables(const uint8_t character_set[]) noexcept {
107 ssse3_percent_tables t{};
108 t.cs_lo = _mm_loadu_si128(reinterpret_cast<const __m128i*>(character_set));
109 t.cs_hi =
110 _mm_loadu_si128(reinterpret_cast<const __m128i*>(character_set + 16));
111 // 1 << (0..7), duplicated so pshufb(index & 7) works for every lane.
112 t.pow2 =
113 _mm_setr_epi8(1, 2, 4, 8, 16, 32, 64, -128, 1, 2, 4, 8, 16, 32, 64, -128);
114 t.mask_0f = _mm_set1_epi8(0x0F);
115 t.mask_07 = _mm_set1_epi8(0x07);
116 t.zero = _mm_setzero_si128();
117 return t;
118}
119
120ADA_UNICODE_SIMD int ssse3_percent_mask(
121 __m128i word, const ssse3_percent_tables& tables) noexcept {
122 const __m128i idx = _mm_and_si128(_mm_srli_epi16(word, 3), tables.mask_0f);
123 const __m128i lo = _mm_shuffle_epi8(tables.cs_lo, idx);
124 const __m128i hi = _mm_shuffle_epi8(tables.cs_hi, idx);
125 // Bytes 0x80-0xFF are signed-negative; select the high half of the bitmap.
126 const __m128i high_byte = _mm_cmpgt_epi8(tables.zero, word);
127 const __m128i cs_byte = _mm_or_si128(_mm_and_si128(hi, high_byte),
128 _mm_andnot_si128(high_byte, lo));
129 const __m128i bits =
130 _mm_shuffle_epi8(tables.pow2, _mm_and_si128(word, tables.mask_07));
131 const __m128i hits = _mm_and_si128(cs_byte, bits);
132 return _mm_movemask_epi8(_mm_cmpeq_epi8(hits, tables.zero)) ^ 0xFFFF;
133}
134
135ADA_UNICODE_SIMD void percent_encode_to_ssse3(
136 const char* p, const char* end, const uint8_t character_set[],
137 const ssse3_percent_tables& tables, std::string& out) {
138 // Pair 16-byte windows so a fully clean 32-byte run is one append.
139 while (p + 32 <= end) {
140 const __m128i word0 = _mm_loadu_si128(reinterpret_cast<const __m128i*>(p));
141 const __m128i word1 =
142 _mm_loadu_si128(reinterpret_cast<const __m128i*>(p + 16));
143 const int mask0 = ssse3_percent_mask(word0, tables);
144 const int mask1 = ssse3_percent_mask(word1, tables);
145 if ((mask0 | mask1) == 0) {
146 out.append(p, 32);
147 } else {
148 if (mask0 == 0) {
149 out.append(p, 16);
150 } else {
151 encode_mask_window(p, static_cast<uint32_t>(mask0), 16, out);
152 }
153 if (mask1 == 0) {
154 out.append(p + 16, 16);
155 } else {
156 encode_mask_window(p + 16, static_cast<uint32_t>(mask1), 16, out);
157 }
158 }
159 p += 32;
160 }
161 if (p + 16 <= end) {
162 const __m128i word = _mm_loadu_si128(reinterpret_cast<const __m128i*>(p));
163 const int mask = ssse3_percent_mask(word, tables);
164 if (mask == 0) {
165 out.append(p, 16);
166 } else {
167 encode_mask_window(p, static_cast<uint32_t>(mask), 16, out);
168 }
169 p += 16;
170 }
171 percent_encode_to_scalar(p, end, character_set, out);
172}
173#endif // ADA_UNICODE_SSSE3
174
175#if ADA_NEON
176ada_really_inline uint8x16x2_t
177load_neon_percent_table(const uint8_t character_set[]) noexcept {
178 uint8x16x2_t table{};
179 table.val[0] = vld1q_u8(character_set);
180 table.val[1] = vld1q_u8(character_set + 16);
181 return table;
182}
183
184ada_really_inline uint8x16_t neon_percent_hits(uint8x16_t word,
185 uint8x16x2_t table) noexcept {
186 const uint8x16_t cs_bytes = vqtbl2q_u8(table, vshrq_n_u8(word, 3));
187 const uint8x16_t bit_mask = vshlq_u8(
188 vdupq_n_u8(1), vreinterpretq_s8_u8(vandq_u8(word, vdupq_n_u8(7))));
189 return vandq_u8(cs_bytes, bit_mask);
190}
191
192ada_really_inline uint32_t neon_percent_mask(uint8x16_t hits) noexcept {
193 const uint8x16_t cmp = vcgtq_u8(hits, vdupq_n_u8(0));
194 const uint8x16_t bit = {1, 2, 4, 8, 16, 32, 64, 128,
195 1, 2, 4, 8, 16, 32, 64, 128};
196 const uint8x16_t masked = vandq_u8(cmp, bit);
197 return static_cast<uint32_t>(vaddv_u8(vget_low_u8(masked))) |
198 (static_cast<uint32_t>(vaddv_u8(vget_high_u8(masked))) << 8);
199}
200
201ada_really_inline void percent_encode_to_neon(const char* p, const char* end,
202 const uint8_t character_set[],
203 uint8x16x2_t table,
204 std::string& out) {
205 while (p + 32 <= end) {
206 const uint8x16_t hits0 =
207 neon_percent_hits(vld1q_u8(reinterpret_cast<const uint8_t*>(p)), table);
208 const uint8x16_t hits1 = neon_percent_hits(
209 vld1q_u8(reinterpret_cast<const uint8_t*>(p + 16)), table);
210 const bool clean0 = vmaxvq_u32(vreinterpretq_u32_u8(hits0)) == 0;
211 const bool clean1 = vmaxvq_u32(vreinterpretq_u32_u8(hits1)) == 0;
212 if (clean0 && clean1) {
213 out.append(p, 32);
214 } else {
215 if (clean0) {
216 out.append(p, 16);
217 } else {
218 encode_mask_window(p, neon_percent_mask(hits0), 16, out);
219 }
220 if (clean1) {
221 out.append(p + 16, 16);
222 } else {
223 encode_mask_window(p + 16, neon_percent_mask(hits1), 16, out);
224 }
225 }
226 p += 32;
227 }
228 if (p + 16 <= end) {
229 const uint8x16_t hits =
230 neon_percent_hits(vld1q_u8(reinterpret_cast<const uint8_t*>(p)), table);
231 if (vmaxvq_u32(vreinterpretq_u32_u8(hits)) == 0) {
232 out.append(p, 16);
233 } else {
234 encode_mask_window(p, neon_percent_mask(hits), 16, out);
235 }
236 p += 16;
237 }
238 percent_encode_to_scalar(p, end, character_set, out);
239}
240#endif // ADA_NEON
241
242#if ADA_RVV
243ada_really_inline void percent_encode_to_rvv(const char* p, const char* end,
244 const uint8_t character_set[],
245 std::string& out) {
246 while (p < end) {
247 const size_t remaining = static_cast<size_t>(end - p);
248 const size_t vl = __riscv_vsetvl_e8m1(remaining);
249 const vuint8m1_t word =
250 __riscv_vle8_v_u8m1(reinterpret_cast<const uint8_t*>(p), vl);
251 const vuint8m1_t cs_bytes =
252 __riscv_vluxei8(character_set, __riscv_vsrl(word, 3, vl), vl);
253 const vuint8m1_t bit_mask = __riscv_vsll(__riscv_vmv_v_x_u8m1(1, vl),
254 __riscv_vand(word, 7, vl), vl);
255 const long idx = __riscv_vfirst(
256 __riscv_vmsne(__riscv_vand(cs_bytes, bit_mask, vl), 0, vl), vl);
257 if (idx < 0) {
258 out.append(p, vl);
259 p += vl;
260 continue;
261 }
262 if (idx > 0) {
263 out.append(p, static_cast<size_t>(idx));
264 p += idx;
265 }
266 out.append(character_sets::hex + uint8_t(*p) * 4, 3);
267 ++p;
268 }
269}
270#endif // ADA_RVV
271
272#if ADA_UNICODE_SSSE3 || ADA_NEON || ADA_RVV
273// Setter and existing percent_encode benches are 2-44 bytes. Table setup
274// plus mask walking costs more instructions than bit_at on those inputs
275// (especially dense USERINFO). SIMD pays off on the remaining suffix.
276static constexpr size_t kPercentEncodeSimdMin = 48;
277
278void percent_encode_to_wide(const char* p, const char* end,
279 const uint8_t character_set[], std::string& out) {
280 // Worst case every byte becomes %XX. Avoids realloc while walking windows.
281 out.reserve(out.size() + static_cast<size_t>(end - p) * 3);
282#if ADA_UNICODE_SSSE3
283 const ssse3_percent_tables tables = load_ssse3_percent_tables(character_set);
284 percent_encode_to_ssse3(p, end, character_set, tables, out);
285#elif ADA_NEON
286 percent_encode_to_neon(p, end, character_set,
287 load_neon_percent_table(character_set), out);
288#elif ADA_RVV
289 percent_encode_to_rvv(p, end, character_set, out);
290#endif
291}
292#endif
293
294} // namespace
295
296void percent_encode_suffix(const char* p, const char* end,
297 const uint8_t character_set[], std::string& out) {
298#if ADA_UNICODE_SSSE3 || ADA_NEON || ADA_RVV
299#ifdef ADA_UNICODE_NEED_SSSE3_TARGET
300 static const bool ssse3_supported = __builtin_cpu_supports("ssse3") != 0;
301 const bool use_wide = ssse3_supported;
302#else
303 const bool use_wide = true;
304#endif
305 if (use_wide && static_cast<size_t>(end - p) >= kPercentEncodeSimdMin) {
306 percent_encode_to_wide(p, end, character_set, out);
307 return;
308 }
309#endif
310 percent_encode_to_scalar(p, end, character_set, out);
311}
312
313} // namespace ada::unicode
Definitions of the character sets used by unicode functions.
Declaration of the character sets used by unicode functions.
Cross-platform compiler macros and common definitions.
#define ada_really_inline
Definition common_defs.h:85
ada_really_inline constexpr bool bit_at(const uint8_t a[], const uint8_t i)
constexpr char hex[1024]
ada_really_inline void percent_encode_to_scalar(const char *p, const char *end, const uint8_t character_set[], std::string &out)
Includes the declarations for unicode operations.
void percent_encode_suffix(const char *p, const char *end, const uint8_t character_set[], std::string &out)
Definitions for all unicode specific functions.
#define ADA_UNICODE_SIMD