Debian Codegraph @

libc-top-half/musl/src/string/strspn_simd.c

raw
1 #if defined(__wasm_simd128__) && defined(__wasilibc_simd_string)
2 // Skip Clang 19 and Clang 20 which have a bug (llvm/llvm-project#146574)
3 // which results in an ICE when inline assembly is used with a vector result.
4 #if __clang_major__ != 19 && __clang_major__ != 20
5
6 #include <stdint.h>
7 #include <string.h>
8 #include <wasm_simd128.h>
9
10 #if !defined(__wasm_relaxed_simd__) || !defined(__RELAXED_FN_ATTRS)
11 #define wasm_i8x16_relaxed_swizzle wasm_i8x16_swizzle
12 #endif
13
14 // SIMDized check which bytes are in a set (Geoff Langdale)
15 // http://0x80.pl/notesen/2018-10-18-simd-byte-lookup.html
16
17 // This is the same algorithm as truffle from Hyperscan:
18 // https://github.com/intel/hyperscan/blob/v5.4.2/src/nfa/truffle.c#L64-L81
19 // https://github.com/intel/hyperscan/blob/v5.4.2/src/nfa/trufflecompile.cpp
20
21 typedef struct {
22 __u8x16 lo;
23 __u8x16 hi;
24 } __wasm_v128_bitmap256_t;
25
26 __attribute__((always_inline))
27 static void __wasm_v128_setbit(__wasm_v128_bitmap256_t *bitmap, uint8_t i) {
28 uint8_t hi_nibble = i >> 4;
29 uint8_t lo_nibble = i & 0xf;
30 bitmap->lo[lo_nibble] |= (uint8_t)(1u << (hi_nibble - 0));
31 bitmap->hi[lo_nibble] |= (uint8_t)(1u << (hi_nibble - 8));
32 }
33
34 __attribute__((always_inline))
35 static v128_t __wasm_v128_chkbits(__wasm_v128_bitmap256_t bitmap, v128_t v) {
36 v128_t hi_nibbles = wasm_u8x16_shr(v, 4);
37 v128_t bitmask_lookup = wasm_u64x2_const_splat(0x8040201008040201);
38 v128_t bitmask = wasm_i8x16_relaxed_swizzle(bitmask_lookup, hi_nibbles);
39
40 v128_t indices_0_7 = v & wasm_u8x16_const_splat(0x8f);
41 v128_t indices_8_15 = indices_0_7 ^ wasm_u8x16_const_splat(0x80);
42
43 v128_t row_0_7 = wasm_i8x16_swizzle((v128_t)bitmap.lo, indices_0_7);
44 v128_t row_8_15 = wasm_i8x16_swizzle((v128_t)bitmap.hi, indices_8_15);
45
46 v128_t bitsets = row_0_7 | row_8_15;
47 return bitsets & bitmask;
48 }
49
50 size_t strspn(const char *s, const char *c)
51 {
52 // Note that reading before/after the allocation of a pointer is UB in
53 // C, so inline assembly is used to generate the exact machine
54 // instruction we want with opaque semantics to the compiler to avoid
55 // the UB.
56 uintptr_t align = (uintptr_t)s % sizeof(v128_t);
57 uintptr_t addr = (uintptr_t)s - align;
58
59 if (!c[0]) return 0;
60 if (!c[1]) {
61 v128_t vc = wasm_i8x16_splat(*c);
62 for (;;) {
63 v128_t v;
64 __asm__(
65 "local.get %1\n"
66 "v128.load 0\n"
67 "local.set %0\n"
68 : "=r"(v)
69 : "r"(addr)
70 : "memory");
71 v128_t cmp = wasm_i8x16_eq(v, vc);
72 // Bitmask is slow on AArch64, all_true is much faster.
73 if (!wasm_i8x16_all_true(cmp)) {
74 // Clear the bits corresponding to align (little-endian)
75 // so we can count trailing zeros.
76 int mask = (uint16_t)~wasm_i8x16_bitmask(cmp) >> align << align;
77 // At least one bit will be set, unless align cleared them.
78 // Knowing this helps the compiler if it unrolls the loop.
79 __builtin_assume(mask || align);
80 // If the mask became zero because of align,
81 // it's as if we didn't find anything.
82 if (mask) {
83 // Find the offset of the first one bit (little-endian).
84 return addr - (uintptr_t)s + __builtin_ctz(mask);
85 }
86 }
87 align = 0;
88 addr += sizeof(v128_t);
89 }
90 }
91
92 __wasm_v128_bitmap256_t bitmap = {};
93
94 for (; *c; c++) {
95 // Terminator IS NOT on the bitmap.
96 __wasm_v128_setbit(&bitmap, (uint8_t)*c);
97 }
98
99 for (;;) {
100 v128_t v;
101 __asm__(
102 "local.get %1\n"
103 "v128.load 0\n"
104 "local.set %0\n"
105 : "=r"(v)
106 : "r"(addr)
107 : "memory");
108 v128_t found = __wasm_v128_chkbits(bitmap, v);
109 // Bitmask is slow on AArch64, all_true is much faster.
110 if (!wasm_i8x16_all_true(found)) {
111 v128_t cmp = wasm_i8x16_eq(found, (v128_t){});
112 // Clear the bits corresponding to align (little-endian)
113 // so we can count trailing zeros.
114 int mask = wasm_i8x16_bitmask(cmp) >> align << align;
115 // At least one bit will be set, unless align cleared them.
116 // Knowing this helps the compiler if it unrolls the loop.
117 __builtin_assume(mask || align);
118 // If the mask became zero because of align,
119 // it's as if we didn't find anything.
120 if (mask) {
121 // Find the offset of the first one bit (little-endian).
122 return addr - (uintptr_t)s + __builtin_ctz(mask);
123 }
124 }
125 align = 0;
126 addr += sizeof(v128_t);
127 }
128 }
129
130 size_t strcspn(const char *s, const char *c)
131 {
132 if (!c[0] || !c[1]) return __strchrnul(s, *c) - s;
133
134 // Note that reading before/after the allocation of a pointer is UB in
135 // C, so inline assembly is used to generate the exact machine
136 // instruction we want with opaque semantics to the compiler to avoid
137 // the UB.
138 uintptr_t align = (uintptr_t)s % sizeof(v128_t);
139 uintptr_t addr = (uintptr_t)s - align;
140
141 __wasm_v128_bitmap256_t bitmap = {};
142
143 do {
144 // Terminator IS on the bitmap.
145 __wasm_v128_setbit(&bitmap, (uint8_t)*c);
146 } while (*c++);
147
148 for (;;) {
149 v128_t v;
150 __asm__(
151 "local.get %1\n"
152 "v128.load 0\n"
153 "local.set %0\n"
154 : "=r"(v)
155 : "r"(addr)
156 : "memory");
157 v128_t found = __wasm_v128_chkbits(bitmap, v);
158 // Bitmask is slow on AArch64, any_true is much faster.
159 if (wasm_v128_any_true(found)) {
160 v128_t cmp = wasm_i8x16_eq(found, (v128_t){});
161 // Clear the bits corresponding to align (little-endian)
162 // so we can count trailing zeros.
163 int mask = (uint16_t)~wasm_i8x16_bitmask(cmp) >> align << align;
164 // At least one bit will be set, unless align cleared them.
165 // Knowing this helps the compiler if it unrolls the loop.
166 __builtin_assume(mask || align);
167 // If the mask became zero because of align,
168 // it's as if we didn't find anything.
169 if (mask) {
170 // Find the offset of the first one bit (little-endian).
171 return addr - (uintptr_t)s + __builtin_ctz(mask);
172 }
173 }
174 align = 0;
175 addr += sizeof(v128_t);
176 }
177 }
178
179 #endif
180 #endif