Blender V5.3
lexit.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Clement Foucault
2 *
3 * SPDX-License-Identifier: MIT */
4
5#include "lexit.hh"
6#include "identifier.hh"
7#include "simd.hh"
8
9#include <algorithm>
10#include <cassert>
11#include <cstring>
12#ifdef _MSC_VER
13# include <intrin.h>
14#endif
15
16#if defined(__clang__) || defined(__GNUC__)
17# define count_bits_i(i) __builtin_popcount(i)
18#elif defined(_MSC_VER)
19# define count_bits_i(i) __popcnt(i)
20#else
21# include <bitset>
22# define count_bits_i(i) (std::bitset<8>{i}.count())
23#endif
24
25namespace lexit {
26
28{
29#ifdef _MSC_VER
30 unsigned long ctz;
31 _BitScanForward64(&ctz, a);
32 return ctz;
33#else
34 return __builtin_ctzll(a);
35#endif
36} // namespace lexit
37
38static uint32_t divide_ceil(uint32_t a, uint32_t b)
39{
40 return (a + b - 1) / b;
41}
42
43/* Helper function to realloc aligned array keeping elem_count data. */
44template<typename T>
45void realloc_aligned_array(AlignedArrayPtr<T> &ptr, size_t elem_count, size_t new_size)
46{
47 assert(new_size >= elem_count);
48 AlignedArrayPtr<T> new_ptr(new_size);
49 if (ptr.get()) {
50 std::memcpy(new_ptr.get(), ptr.get(), elem_count * sizeof(T));
51 }
52 ptr = std::move(new_ptr);
53}
54
56{
57 size_ = 0;
58}
59
72
73#if defined(USE_NEON) || defined(USE_SSE4_2)
74
75/* Shuffle table used for stream compaction.
76 * For a given 8bit pattern (where each 1 bit represents an element to keep)
77 * encode the index of the source register for each of the 8 destination registers.
78 * Every 0 bit (representing a discarded element) will be sourced from the 0th element.
79 * This is to be used with table. */
80alignas(16) static const uint8_t shuffle_table_8[256][8] = {
81 /* [0b00000000] = */ {0, 0, 0, 0, 0, 0, 0, 0},
82 /* [0b00000001] = */ {0, 0, 0, 0, 0, 0, 0, 0},
83 /* [0b00000010] = */ {1, 0, 0, 0, 0, 0, 0, 0},
84 /* [0b00000011] = */ {0, 1, 0, 0, 0, 0, 0, 0},
85 /* [0b00000100] = */ {2, 0, 0, 0, 0, 0, 0, 0},
86 /* [0b00000101] = */ {0, 2, 0, 0, 0, 0, 0, 0},
87 /* [0b00000110] = */ {1, 2, 0, 0, 0, 0, 0, 0},
88 /* [0b00000111] = */ {0, 1, 2, 0, 0, 0, 0, 0},
89 /* [0b00001000] = */ {3, 0, 0, 0, 0, 0, 0, 0},
90 /* [0b00001001] = */ {0, 3, 0, 0, 0, 0, 0, 0},
91 /* [0b00001010] = */ {1, 3, 0, 0, 0, 0, 0, 0},
92 /* [0b00001011] = */ {0, 1, 3, 0, 0, 0, 0, 0},
93 /* [0b00001100] = */ {2, 3, 0, 0, 0, 0, 0, 0},
94 /* [0b00001101] = */ {0, 2, 3, 0, 0, 0, 0, 0},
95 /* [0b00001110] = */ {1, 2, 3, 0, 0, 0, 0, 0},
96 /* [0b00001111] = */ {0, 1, 2, 3, 0, 0, 0, 0},
97 /* [0b00010000] = */ {4, 0, 0, 0, 0, 0, 0, 0},
98 /* [0b00010001] = */ {0, 4, 0, 0, 0, 0, 0, 0},
99 /* [0b00010010] = */ {1, 4, 0, 0, 0, 0, 0, 0},
100 /* [0b00010011] = */ {0, 1, 4, 0, 0, 0, 0, 0},
101 /* [0b00010100] = */ {2, 4, 0, 0, 0, 0, 0, 0},
102 /* [0b00010101] = */ {0, 2, 4, 0, 0, 0, 0, 0},
103 /* [0b00010110] = */ {1, 2, 4, 0, 0, 0, 0, 0},
104 /* [0b00010111] = */ {0, 1, 2, 4, 0, 0, 0, 0},
105 /* [0b00011000] = */ {3, 4, 0, 0, 0, 0, 0, 0},
106 /* [0b00011001] = */ {0, 3, 4, 0, 0, 0, 0, 0},
107 /* [0b00011010] = */ {1, 3, 4, 0, 0, 0, 0, 0},
108 /* [0b00011011] = */ {0, 1, 3, 4, 0, 0, 0, 0},
109 /* [0b00011100] = */ {2, 3, 4, 0, 0, 0, 0, 0},
110 /* [0b00011101] = */ {0, 2, 3, 4, 0, 0, 0, 0},
111 /* [0b00011110] = */ {1, 2, 3, 4, 0, 0, 0, 0},
112 /* [0b00011111] = */ {0, 1, 2, 3, 4, 0, 0, 0},
113 /* [0b00100000] = */ {5, 0, 0, 0, 0, 0, 0, 0},
114 /* [0b00100001] = */ {0, 5, 0, 0, 0, 0, 0, 0},
115 /* [0b00100010] = */ {1, 5, 0, 0, 0, 0, 0, 0},
116 /* [0b00100011] = */ {0, 1, 5, 0, 0, 0, 0, 0},
117 /* [0b00100100] = */ {2, 5, 0, 0, 0, 0, 0, 0},
118 /* [0b00100101] = */ {0, 2, 5, 0, 0, 0, 0, 0},
119 /* [0b00100110] = */ {1, 2, 5, 0, 0, 0, 0, 0},
120 /* [0b00100111] = */ {0, 1, 2, 5, 0, 0, 0, 0},
121 /* [0b00101000] = */ {3, 5, 0, 0, 0, 0, 0, 0},
122 /* [0b00101001] = */ {0, 3, 5, 0, 0, 0, 0, 0},
123 /* [0b00101010] = */ {1, 3, 5, 0, 0, 0, 0, 0},
124 /* [0b00101011] = */ {0, 1, 3, 5, 0, 0, 0, 0},
125 /* [0b00101100] = */ {2, 3, 5, 0, 0, 0, 0, 0},
126 /* [0b00101101] = */ {0, 2, 3, 5, 0, 0, 0, 0},
127 /* [0b00101110] = */ {1, 2, 3, 5, 0, 0, 0, 0},
128 /* [0b00101111] = */ {0, 1, 2, 3, 5, 0, 0, 0},
129 /* [0b00110000] = */ {4, 5, 0, 0, 0, 0, 0, 0},
130 /* [0b00110001] = */ {0, 4, 5, 0, 0, 0, 0, 0},
131 /* [0b00110010] = */ {1, 4, 5, 0, 0, 0, 0, 0},
132 /* [0b00110011] = */ {0, 1, 4, 5, 0, 0, 0, 0},
133 /* [0b00110100] = */ {2, 4, 5, 0, 0, 0, 0, 0},
134 /* [0b00110101] = */ {0, 2, 4, 5, 0, 0, 0, 0},
135 /* [0b00110110] = */ {1, 2, 4, 5, 0, 0, 0, 0},
136 /* [0b00110111] = */ {0, 1, 2, 4, 5, 0, 0, 0},
137 /* [0b00111000] = */ {3, 4, 5, 0, 0, 0, 0, 0},
138 /* [0b00111001] = */ {0, 3, 4, 5, 0, 0, 0, 0},
139 /* [0b00111010] = */ {1, 3, 4, 5, 0, 0, 0, 0},
140 /* [0b00111011] = */ {0, 1, 3, 4, 5, 0, 0, 0},
141 /* [0b00111100] = */ {2, 3, 4, 5, 0, 0, 0, 0},
142 /* [0b00111101] = */ {0, 2, 3, 4, 5, 0, 0, 0},
143 /* [0b00111110] = */ {1, 2, 3, 4, 5, 0, 0, 0},
144 /* [0b00111111] = */ {0, 1, 2, 3, 4, 5, 0, 0},
145 /* [0b01000000] = */ {6, 0, 0, 0, 0, 0, 0, 0},
146 /* [0b01000001] = */ {0, 6, 0, 0, 0, 0, 0, 0},
147 /* [0b01000010] = */ {1, 6, 0, 0, 0, 0, 0, 0},
148 /* [0b01000011] = */ {0, 1, 6, 0, 0, 0, 0, 0},
149 /* [0b01000100] = */ {2, 6, 0, 0, 0, 0, 0, 0},
150 /* [0b01000101] = */ {0, 2, 6, 0, 0, 0, 0, 0},
151 /* [0b01000110] = */ {1, 2, 6, 0, 0, 0, 0, 0},
152 /* [0b01000111] = */ {0, 1, 2, 6, 0, 0, 0, 0},
153 /* [0b01001000] = */ {3, 6, 0, 0, 0, 0, 0, 0},
154 /* [0b01001001] = */ {0, 3, 6, 0, 0, 0, 0, 0},
155 /* [0b01001010] = */ {1, 3, 6, 0, 0, 0, 0, 0},
156 /* [0b01001011] = */ {0, 1, 3, 6, 0, 0, 0, 0},
157 /* [0b01001100] = */ {2, 3, 6, 0, 0, 0, 0, 0},
158 /* [0b01001101] = */ {0, 2, 3, 6, 0, 0, 0, 0},
159 /* [0b01001110] = */ {1, 2, 3, 6, 0, 0, 0, 0},
160 /* [0b01001111] = */ {0, 1, 2, 3, 6, 0, 0, 0},
161 /* [0b01010000] = */ {4, 6, 0, 0, 0, 0, 0, 0},
162 /* [0b01010001] = */ {0, 4, 6, 0, 0, 0, 0, 0},
163 /* [0b01010010] = */ {1, 4, 6, 0, 0, 0, 0, 0},
164 /* [0b01010011] = */ {0, 1, 4, 6, 0, 0, 0, 0},
165 /* [0b01010100] = */ {2, 4, 6, 0, 0, 0, 0, 0},
166 /* [0b01010101] = */ {0, 2, 4, 6, 0, 0, 0, 0},
167 /* [0b01010110] = */ {1, 2, 4, 6, 0, 0, 0, 0},
168 /* [0b01010111] = */ {0, 1, 2, 4, 6, 0, 0, 0},
169 /* [0b01011000] = */ {3, 4, 6, 0, 0, 0, 0, 0},
170 /* [0b01011001] = */ {0, 3, 4, 6, 0, 0, 0, 0},
171 /* [0b01011010] = */ {1, 3, 4, 6, 0, 0, 0, 0},
172 /* [0b01011011] = */ {0, 1, 3, 4, 6, 0, 0, 0},
173 /* [0b01011100] = */ {2, 3, 4, 6, 0, 0, 0, 0},
174 /* [0b01011101] = */ {0, 2, 3, 4, 6, 0, 0, 0},
175 /* [0b01011110] = */ {1, 2, 3, 4, 6, 0, 0, 0},
176 /* [0b01011111] = */ {0, 1, 2, 3, 4, 6, 0, 0},
177 /* [0b01100000] = */ {5, 6, 0, 0, 0, 0, 0, 0},
178 /* [0b01100001] = */ {0, 5, 6, 0, 0, 0, 0, 0},
179 /* [0b01100010] = */ {1, 5, 6, 0, 0, 0, 0, 0},
180 /* [0b01100011] = */ {0, 1, 5, 6, 0, 0, 0, 0},
181 /* [0b01100100] = */ {2, 5, 6, 0, 0, 0, 0, 0},
182 /* [0b01100101] = */ {0, 2, 5, 6, 0, 0, 0, 0},
183 /* [0b01100110] = */ {1, 2, 5, 6, 0, 0, 0, 0},
184 /* [0b01100111] = */ {0, 1, 2, 5, 6, 0, 0, 0},
185 /* [0b01101000] = */ {3, 5, 6, 0, 0, 0, 0, 0},
186 /* [0b01101001] = */ {0, 3, 5, 6, 0, 0, 0, 0},
187 /* [0b01101010] = */ {1, 3, 5, 6, 0, 0, 0, 0},
188 /* [0b01101011] = */ {0, 1, 3, 5, 6, 0, 0, 0},
189 /* [0b01101100] = */ {2, 3, 5, 6, 0, 0, 0, 0},
190 /* [0b01101101] = */ {0, 2, 3, 5, 6, 0, 0, 0},
191 /* [0b01101110] = */ {1, 2, 3, 5, 6, 0, 0, 0},
192 /* [0b01101111] = */ {0, 1, 2, 3, 5, 6, 0, 0},
193 /* [0b01110000] = */ {4, 5, 6, 0, 0, 0, 0, 0},
194 /* [0b01110001] = */ {0, 4, 5, 6, 0, 0, 0, 0},
195 /* [0b01110010] = */ {1, 4, 5, 6, 0, 0, 0, 0},
196 /* [0b01110011] = */ {0, 1, 4, 5, 6, 0, 0, 0},
197 /* [0b01110100] = */ {2, 4, 5, 6, 0, 0, 0, 0},
198 /* [0b01110101] = */ {0, 2, 4, 5, 6, 0, 0, 0},
199 /* [0b01110110] = */ {1, 2, 4, 5, 6, 0, 0, 0},
200 /* [0b01110111] = */ {0, 1, 2, 4, 5, 6, 0, 0},
201 /* [0b01111000] = */ {3, 4, 5, 6, 0, 0, 0, 0},
202 /* [0b01111001] = */ {0, 3, 4, 5, 6, 0, 0, 0},
203 /* [0b01111010] = */ {1, 3, 4, 5, 6, 0, 0, 0},
204 /* [0b01111011] = */ {0, 1, 3, 4, 5, 6, 0, 0},
205 /* [0b01111100] = */ {2, 3, 4, 5, 6, 0, 0, 0},
206 /* [0b01111101] = */ {0, 2, 3, 4, 5, 6, 0, 0},
207 /* [0b01111110] = */ {1, 2, 3, 4, 5, 6, 0, 0},
208 /* [0b01111111] = */ {0, 1, 2, 3, 4, 5, 6, 0},
209 /* [0b10000000] = */ {7, 0, 0, 0, 0, 0, 0, 0},
210 /* [0b10000001] = */ {0, 7, 0, 0, 0, 0, 0, 0},
211 /* [0b10000010] = */ {1, 7, 0, 0, 0, 0, 0, 0},
212 /* [0b10000011] = */ {0, 1, 7, 0, 0, 0, 0, 0},
213 /* [0b10000100] = */ {2, 7, 0, 0, 0, 0, 0, 0},
214 /* [0b10000101] = */ {0, 2, 7, 0, 0, 0, 0, 0},
215 /* [0b10000110] = */ {1, 2, 7, 0, 0, 0, 0, 0},
216 /* [0b10000111] = */ {0, 1, 2, 7, 0, 0, 0, 0},
217 /* [0b10001000] = */ {3, 7, 0, 0, 0, 0, 0, 0},
218 /* [0b10001001] = */ {0, 3, 7, 0, 0, 0, 0, 0},
219 /* [0b10001010] = */ {1, 3, 7, 0, 0, 0, 0, 0},
220 /* [0b10001011] = */ {0, 1, 3, 7, 0, 0, 0, 0},
221 /* [0b10001100] = */ {2, 3, 7, 0, 0, 0, 0, 0},
222 /* [0b10001101] = */ {0, 2, 3, 7, 0, 0, 0, 0},
223 /* [0b10001110] = */ {1, 2, 3, 7, 0, 0, 0, 0},
224 /* [0b10001111] = */ {0, 1, 2, 3, 7, 0, 0, 0},
225 /* [0b10010000] = */ {4, 7, 0, 0, 0, 0, 0, 0},
226 /* [0b10010001] = */ {0, 4, 7, 0, 0, 0, 0, 0},
227 /* [0b10010010] = */ {1, 4, 7, 0, 0, 0, 0, 0},
228 /* [0b10010011] = */ {0, 1, 4, 7, 0, 0, 0, 0},
229 /* [0b10010100] = */ {2, 4, 7, 0, 0, 0, 0, 0},
230 /* [0b10010101] = */ {0, 2, 4, 7, 0, 0, 0, 0},
231 /* [0b10010110] = */ {1, 2, 4, 7, 0, 0, 0, 0},
232 /* [0b10010111] = */ {0, 1, 2, 4, 7, 0, 0, 0},
233 /* [0b10011000] = */ {3, 4, 7, 0, 0, 0, 0, 0},
234 /* [0b10011001] = */ {0, 3, 4, 7, 0, 0, 0, 0},
235 /* [0b10011010] = */ {1, 3, 4, 7, 0, 0, 0, 0},
236 /* [0b10011011] = */ {0, 1, 3, 4, 7, 0, 0, 0},
237 /* [0b10011100] = */ {2, 3, 4, 7, 0, 0, 0, 0},
238 /* [0b10011101] = */ {0, 2, 3, 4, 7, 0, 0, 0},
239 /* [0b10011110] = */ {1, 2, 3, 4, 7, 0, 0, 0},
240 /* [0b10011111] = */ {0, 1, 2, 3, 4, 7, 0, 0},
241 /* [0b10100000] = */ {5, 7, 0, 0, 0, 0, 0, 0},
242 /* [0b10100001] = */ {0, 5, 7, 0, 0, 0, 0, 0},
243 /* [0b10100010] = */ {1, 5, 7, 0, 0, 0, 0, 0},
244 /* [0b10100011] = */ {0, 1, 5, 7, 0, 0, 0, 0},
245 /* [0b10100100] = */ {2, 5, 7, 0, 0, 0, 0, 0},
246 /* [0b10100101] = */ {0, 2, 5, 7, 0, 0, 0, 0},
247 /* [0b10100110] = */ {1, 2, 5, 7, 0, 0, 0, 0},
248 /* [0b10100111] = */ {0, 1, 2, 5, 7, 0, 0, 0},
249 /* [0b10101000] = */ {3, 5, 7, 0, 0, 0, 0, 0},
250 /* [0b10101001] = */ {0, 3, 5, 7, 0, 0, 0, 0},
251 /* [0b10101010] = */ {1, 3, 5, 7, 0, 0, 0, 0},
252 /* [0b10101011] = */ {0, 1, 3, 5, 7, 0, 0, 0},
253 /* [0b10101100] = */ {2, 3, 5, 7, 0, 0, 0, 0},
254 /* [0b10101101] = */ {0, 2, 3, 5, 7, 0, 0, 0},
255 /* [0b10101110] = */ {1, 2, 3, 5, 7, 0, 0, 0},
256 /* [0b10101111] = */ {0, 1, 2, 3, 5, 7, 0, 0},
257 /* [0b10110000] = */ {4, 5, 7, 0, 0, 0, 0, 0},
258 /* [0b10110001] = */ {0, 4, 5, 7, 0, 0, 0, 0},
259 /* [0b10110010] = */ {1, 4, 5, 7, 0, 0, 0, 0},
260 /* [0b10110011] = */ {0, 1, 4, 5, 7, 0, 0, 0},
261 /* [0b10110100] = */ {2, 4, 5, 7, 0, 0, 0, 0},
262 /* [0b10110101] = */ {0, 2, 4, 5, 7, 0, 0, 0},
263 /* [0b10110110] = */ {1, 2, 4, 5, 7, 0, 0, 0},
264 /* [0b10110111] = */ {0, 1, 2, 4, 5, 7, 0, 0},
265 /* [0b10111000] = */ {3, 4, 5, 7, 0, 0, 0, 0},
266 /* [0b10111001] = */ {0, 3, 4, 5, 7, 0, 0, 0},
267 /* [0b10111010] = */ {1, 3, 4, 5, 7, 0, 0, 0},
268 /* [0b10111011] = */ {0, 1, 3, 4, 5, 7, 0, 0},
269 /* [0b10111100] = */ {2, 3, 4, 5, 7, 0, 0, 0},
270 /* [0b10111101] = */ {0, 2, 3, 4, 5, 7, 0, 0},
271 /* [0b10111110] = */ {1, 2, 3, 4, 5, 7, 0, 0},
272 /* [0b10111111] = */ {0, 1, 2, 3, 4, 5, 7, 0},
273 /* [0b11000000] = */ {6, 7, 0, 0, 0, 0, 0, 0},
274 /* [0b11000001] = */ {0, 6, 7, 0, 0, 0, 0, 0},
275 /* [0b11000010] = */ {1, 6, 7, 0, 0, 0, 0, 0},
276 /* [0b11000011] = */ {0, 1, 6, 7, 0, 0, 0, 0},
277 /* [0b11000100] = */ {2, 6, 7, 0, 0, 0, 0, 0},
278 /* [0b11000101] = */ {0, 2, 6, 7, 0, 0, 0, 0},
279 /* [0b11000110] = */ {1, 2, 6, 7, 0, 0, 0, 0},
280 /* [0b11000111] = */ {0, 1, 2, 6, 7, 0, 0, 0},
281 /* [0b11001000] = */ {3, 6, 7, 0, 0, 0, 0, 0},
282 /* [0b11001001] = */ {0, 3, 6, 7, 0, 0, 0, 0},
283 /* [0b11001010] = */ {1, 3, 6, 7, 0, 0, 0, 0},
284 /* [0b11001011] = */ {0, 1, 3, 6, 7, 0, 0, 0},
285 /* [0b11001100] = */ {2, 3, 6, 7, 0, 0, 0, 0},
286 /* [0b11001101] = */ {0, 2, 3, 6, 7, 0, 0, 0},
287 /* [0b11001110] = */ {1, 2, 3, 6, 7, 0, 0, 0},
288 /* [0b11001111] = */ {0, 1, 2, 3, 6, 7, 0, 0},
289 /* [0b11010000] = */ {4, 6, 7, 0, 0, 0, 0, 0},
290 /* [0b11010001] = */ {0, 4, 6, 7, 0, 0, 0, 0},
291 /* [0b11010010] = */ {1, 4, 6, 7, 0, 0, 0, 0},
292 /* [0b11010011] = */ {0, 1, 4, 6, 7, 0, 0, 0},
293 /* [0b11010100] = */ {2, 4, 6, 7, 0, 0, 0, 0},
294 /* [0b11010101] = */ {0, 2, 4, 6, 7, 0, 0, 0},
295 /* [0b11010110] = */ {1, 2, 4, 6, 7, 0, 0, 0},
296 /* [0b11010111] = */ {0, 1, 2, 4, 6, 7, 0, 0},
297 /* [0b11011000] = */ {3, 4, 6, 7, 0, 0, 0, 0},
298 /* [0b11011001] = */ {0, 3, 4, 6, 7, 0, 0, 0},
299 /* [0b11011010] = */ {1, 3, 4, 6, 7, 0, 0, 0},
300 /* [0b11011011] = */ {0, 1, 3, 4, 6, 7, 0, 0},
301 /* [0b11011100] = */ {2, 3, 4, 6, 7, 0, 0, 0},
302 /* [0b11011101] = */ {0, 2, 3, 4, 6, 7, 0, 0},
303 /* [0b11011110] = */ {1, 2, 3, 4, 6, 7, 0, 0},
304 /* [0b11011111] = */ {0, 1, 2, 3, 4, 6, 7, 0},
305 /* [0b11100000] = */ {5, 6, 7, 0, 0, 0, 0, 0},
306 /* [0b11100001] = */ {0, 5, 6, 7, 0, 0, 0, 0},
307 /* [0b11100010] = */ {1, 5, 6, 7, 0, 0, 0, 0},
308 /* [0b11100011] = */ {0, 1, 5, 6, 7, 0, 0, 0},
309 /* [0b11100100] = */ {2, 5, 6, 7, 0, 0, 0, 0},
310 /* [0b11100101] = */ {0, 2, 5, 6, 7, 0, 0, 0},
311 /* [0b11100110] = */ {1, 2, 5, 6, 7, 0, 0, 0},
312 /* [0b11100111] = */ {0, 1, 2, 5, 6, 7, 0, 0},
313 /* [0b11101000] = */ {3, 5, 6, 7, 0, 0, 0, 0},
314 /* [0b11101001] = */ {0, 3, 5, 6, 7, 0, 0, 0},
315 /* [0b11101010] = */ {1, 3, 5, 6, 7, 0, 0, 0},
316 /* [0b11101011] = */ {0, 1, 3, 5, 6, 7, 0, 0},
317 /* [0b11101100] = */ {2, 3, 5, 6, 7, 0, 0, 0},
318 /* [0b11101101] = */ {0, 2, 3, 5, 6, 7, 0, 0},
319 /* [0b11101110] = */ {1, 2, 3, 5, 6, 7, 0, 0},
320 /* [0b11101111] = */ {0, 1, 2, 3, 5, 6, 7, 0},
321 /* [0b11110000] = */ {4, 5, 6, 7, 0, 0, 0, 0},
322 /* [0b11110001] = */ {0, 4, 5, 6, 7, 0, 0, 0},
323 /* [0b11110010] = */ {1, 4, 5, 6, 7, 0, 0, 0},
324 /* [0b11110011] = */ {0, 1, 4, 5, 6, 7, 0, 0},
325 /* [0b11110100] = */ {2, 4, 5, 6, 7, 0, 0, 0},
326 /* [0b11110101] = */ {0, 2, 4, 5, 6, 7, 0, 0},
327 /* [0b11110110] = */ {1, 2, 4, 5, 6, 7, 0, 0},
328 /* [0b11110111] = */ {0, 1, 2, 4, 5, 6, 7, 0},
329 /* [0b11111000] = */ {3, 4, 5, 6, 7, 0, 0, 0},
330 /* [0b11111001] = */ {0, 3, 4, 5, 6, 7, 0, 0},
331 /* [0b11111010] = */ {1, 3, 4, 5, 6, 7, 0, 0},
332 /* [0b11111011] = */ {0, 1, 3, 4, 5, 6, 7, 0},
333 /* [0b11111100] = */ {2, 3, 4, 5, 6, 7, 0, 0},
334 /* [0b11111101] = */ {0, 2, 3, 4, 5, 6, 7, 0},
335 /* [0b11111110] = */ {1, 2, 3, 4, 5, 6, 7, 0},
336 /* [0b11111111] = */ {0, 1, 2, 3, 4, 5, 6, 7},
337};
338
339/* Popcount for a uint8_t. */
340alignas(16) static const uint8_t mask_popcount[256] = {
341 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3,
342 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4,
343 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,
344 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5,
345 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2,
346 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5,
347 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4,
348 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6,
349 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
350
351template<int Size> struct ShuffleIndicesResult {
352 simd::u8_base<Size> indices;
353 int popcount;
354};
355
356inline ShuffleIndicesResult<1> shuffle_indices_from_emit_mask(uint16_t emit_mask)
357{
358 const uint8_t emit_mask_lo = emit_mask & 0xFFu;
359 const uint8_t emit_mask_hi = emit_mask >> 8;
360 const uint8_t mask_popcount_lo = mask_popcount[emit_mask_lo];
361 const uint8_t mask_popcount_hi = mask_popcount[emit_mask_hi];
362 /* Lookup the shuffle vector in 2 halves. */
363 uint64_t v0 = *(uint64_t *)shuffle_table_8[emit_mask_lo];
364 uint64_t v1 = *(uint64_t *)shuffle_table_8[emit_mask_hi] | uint64_t(0x0808080808080808);
365 /* Combine the two halves into one contiguous index array.
366 * We don't care about values after the last valid index. */
367 alignas(16) uint8_t combined[16];
368 *(uint64_t *)combined = v0;
369 *(uint64_t *)(combined + mask_popcount_lo) = v1;
370
371 return {simd::u8x16::load((const uint8_t *)&combined), mask_popcount_lo + mask_popcount_hi};
372}
373
374inline ShuffleIndicesResult<4> shuffle_indices_from_emit_mask(uint64_t emit_mask)
375{
376 const uint8_t emit_mask_0 = (emit_mask >> 0) & 0xFFu;
377 const uint8_t emit_mask_1 = (emit_mask >> 8) & 0xFFu;
378 const uint8_t emit_mask_2 = (emit_mask >> 16) & 0xFFu;
379 const uint8_t emit_mask_3 = (emit_mask >> 24) & 0xFFu;
380 const uint8_t emit_mask_4 = (emit_mask >> 32) & 0xFFu;
381 const uint8_t emit_mask_5 = (emit_mask >> 40) & 0xFFu;
382 const uint8_t emit_mask_6 = (emit_mask >> 48) & 0xFFu;
383 const uint8_t emit_mask_7 = (emit_mask >> 56) & 0xFFu;
384 const uint8_t mask_popcount_0 = mask_popcount[emit_mask_0];
385 const uint8_t mask_popcount_1 = mask_popcount[emit_mask_1];
386 const uint8_t mask_popcount_2 = mask_popcount[emit_mask_2];
387 const uint8_t mask_popcount_3 = mask_popcount[emit_mask_3];
388 const uint8_t mask_popcount_4 = mask_popcount[emit_mask_4];
389 const uint8_t mask_popcount_5 = mask_popcount[emit_mask_5];
390 const uint8_t mask_popcount_6 = mask_popcount[emit_mask_6];
391 const uint8_t mask_popcount_7 = mask_popcount[emit_mask_7];
392 /* Lookup the shuffle vector in multiple part. */
393 uint64_t v0 = *(uint64_t *)shuffle_table_8[emit_mask_0];
394 uint64_t v1 = *(uint64_t *)shuffle_table_8[emit_mask_1] | uint64_t(0x0808080808080808);
395 uint64_t v2 = *(uint64_t *)shuffle_table_8[emit_mask_2] | uint64_t(0x1010101010101010);
396 uint64_t v3 = *(uint64_t *)shuffle_table_8[emit_mask_3] | uint64_t(0x1818181818181818);
397 uint64_t v4 = *(uint64_t *)shuffle_table_8[emit_mask_4] | uint64_t(0x2020202020202020);
398 uint64_t v5 = *(uint64_t *)shuffle_table_8[emit_mask_5] | uint64_t(0x2828282828282828);
399 uint64_t v6 = *(uint64_t *)shuffle_table_8[emit_mask_6] | uint64_t(0x3030303030303030);
400 uint64_t v7 = *(uint64_t *)shuffle_table_8[emit_mask_7] | uint64_t(0x3838383838383838);
401 /* Combine the parts into one contiguous index array.
402 * We don't care about values after the last valid index. */
403 alignas(64) uint8_t combined[64];
404 int popcount = 0;
405 std::memcpy(combined + popcount, &v0, sizeof(uint64_t)), popcount += mask_popcount_0;
406 std::memcpy(combined + popcount, &v1, sizeof(uint64_t)), popcount += mask_popcount_1;
407 std::memcpy(combined + popcount, &v2, sizeof(uint64_t)), popcount += mask_popcount_2;
408 std::memcpy(combined + popcount, &v3, sizeof(uint64_t)), popcount += mask_popcount_3;
409 std::memcpy(combined + popcount, &v4, sizeof(uint64_t)), popcount += mask_popcount_4;
410 std::memcpy(combined + popcount, &v5, sizeof(uint64_t)), popcount += mask_popcount_5;
411 std::memcpy(combined + popcount, &v6, sizeof(uint64_t)), popcount += mask_popcount_6;
412 std::memcpy(combined + popcount, &v7, sizeof(uint64_t)), popcount += mask_popcount_7;
413
414 return {simd::u8x64::load((const uint8_t *)&combined), popcount};
415}
416#endif
417
418inline TokenType select(char char_value, char char_class, bool cond)
419{
420 return TokenType((cond) ? char_class : char_value);
421}
422
423inline void TokenBuffer::tokenize_scalar(uint32_t &__restrict offset,
424 uint32_t &__restrict cursor_begin,
425 uint32_t &__restrict cursor_end,
426 CharClass &__restrict prev_char_class,
427 bool &__restrict prev_whitespace,
428 uint32_t end,
429 const CharClass char_class_table[128])
430{
431 for (; offset < end; offset += 1) {
432 const char c = str_[offset];
433 const CharClass curr_char_class = char_class_table[c];
434 const TokenType curr_tok_type = select(
435 c, char(curr_char_class), curr_char_class > CharClass::ClassToTypeThreshold);
436 /* It is faster to overwrite the previous value with the same value
437 * as having a condition. */
438 types_[cursor_begin] = curr_tok_type;
439 offsets_[cursor_begin] = offset;
440 offsets_end_[cursor_end] = offset;
447 const bool emit = (uint8_t(curr_char_class) & uint8_t(prev_char_class) &
448 uint8_t(CharClass::CanMerge)) == 0;
449 prev_char_class = curr_char_class;
450
457 /* : 1 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 */
458 const bool curr_ws = (curr_char_class == CharClass::WhiteSpace);
459 /* : 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 */
460 const bool emit_ws = emit && curr_ws;
461 /* : 1 0 0 0 1 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 */
462 const bool emit_start = emit && !curr_ws;
463 /* : 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 */
464 const bool follow_non_ws = emit_start && !prev_whitespace;
465 /* : 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 */
466 const bool emit_end = emit_ws || follow_non_ws;
467
468 prev_whitespace = curr_ws;
469
470#ifdef LEXIT_DEBUG
471 if (emit_start) {
472 int start = offsets_[cursor_begin - 1];
473 int end = offsets_[cursor_begin];
474 token_str_with_whitespace_debug_.emplace_back(str_.data() + start, end - start);
475 }
476 if (emit_end) {
477 int start = offsets_[cursor_end];
478 int end = offsets_end_[cursor_end];
479 token_str_debug_.emplace_back(str_.data() + start, end - start);
480 }
481#endif
482
483 cursor_begin += emit_start;
484 cursor_end += emit_end;
485 }
486}
487
489{
490 /* Ensure enough space for the worse scenario, which is one token per character.
491 * This is done in order to avoid allocation and check inside the hot loop. */
492 reserve(str_.size());
493
494 if (str_.empty()) {
495 size_ = 0;
496 types_[0] = EndOfFile;
497 return;
498 }
499
522
523 CharClass prev_value = CharClass::None;
524 bool prev_whitespace;
525 {
526 /* First iteration needs to always emit start of the token. */
527 const CharClass curr = char_class_table[str_[0]];
528 types_[0] = select(str_[0], char(curr), curr > CharClass::ClassToTypeThreshold);
529 offsets_[0] = 0;
530 offsets_end_[0] = 0;
531 prev_value = curr;
532 prev_whitespace = curr == CharClass::WhiteSpace;
533 }
534
535 uint32_t offset = 1, cursor = 1, cursor_end = prev_whitespace ? 1 : 0;
536
537 int stride = 64;
538
539 /* Process until alignment to SIMD size is met. */
540 size_t index_at_align = ((stride - (uintptr_t(str_.data() + 1) & (stride - 1))) & (stride - 1)) +
541 1;
542 tokenize_scalar(offset,
543 cursor,
544 cursor_end,
545 prev_value,
546 prev_whitespace,
547 str_.size() > index_at_align ? index_at_align : str_.size(),
549
550#if defined(USE_NEON) || defined(USE_SSE4_2)
551 using namespace lexit::simd;
552 const uint8_t *str = (const uint8_t *)str_.data();
553 const u8x128_table char_to_class = u8x128_table::load((const uint8_t *)char_class_table);
554
555 for (; offset + stride <= str_.size(); offset += stride) {
556# ifdef LEXIT_DEBUG
557 const std::string_view char_simd{str_.data() + offset, size_t(stride)};
558# endif
559 const u8x64 c = u8x64::load(str + offset);
560 const u8x64 curr_char_class = char_to_class[c];
561 /* Shift and add the last iteration end token at the start of the vector. */
562 const u8x64 prev_char_class = shift_lanes_right<1>(curr_char_class, uint8_t(prev_value));
563
564 const u8x64 to_type_threshold{uint8_t(CharClass::ClassToTypeThreshold)};
565 const u8x64 can_merge{uint8_t(CharClass::CanMerge)};
566 const u8x64 curr_tok_type = select(c, curr_char_class, curr_char_class > to_type_threshold);
567 const u8x64 emit = is_zero(curr_char_class & prev_char_class & can_merge);
568 /* Store for next iteration. */
569 prev_value = CharClass(curr_char_class.last());
570 /* Start and end of token. See scalar version for documentation. */
571 const u8x64 curr_ws = (curr_char_class == uint8_t(CharClass::WhiteSpace));
572 const u8x64 curr_non_ws = ~curr_ws;
573 const u8x64 emit_ws = emit & curr_ws;
574 const u8x64 emit_start = emit & curr_non_ws;
575 const u8x64 prev_non_ws = shift_lanes_right<1>(curr_non_ws, prev_whitespace ? 0x0 : 0xFF);
576 const u8x64 follow_non_ws = emit_start & prev_non_ws;
577 const u8x64 emit_end = emit_ws | follow_non_ws;
578 /* Store for next iteration. */
579 prev_whitespace = !curr_non_ws.last();
580 uint64_t emit_end_mask = movemask(emit_end);
581 uint64_t emit_start_mask = movemask(emit_start);
582
583 /* Stream compaction of data based on the emit mask (0xFF == emit, 0x00 == skip).
584 * Stores `data` compacted inside `data_out` starting from `data_out + cursor` and advance
585 * `cursor` by the number of element compacted. */
586 {
587 auto [shuffle, popcount] = shuffle_indices_from_emit_mask(emit_start_mask);
588 /* Move data to destination elements (compaction). */
589 const u8x64 data_packed = u8x64_table(curr_tok_type)[shuffle];
590 /* Write 16 types in the stream. */
591 data_packed.store_unaligned((uint8_t *)&types_[cursor]);
592 /* The offsets are contained inside the 8 bit shuffle vector.
593 * We need to promote it to 32 bit before adding the base offset. */
594 (u32x16(shuffle.lane(0)) + offset).store_unaligned(&offsets_[cursor + 0]);
595 (u32x16(shuffle.lane(1)) + offset).store_unaligned(&offsets_[cursor + 16]);
596 (u32x16(shuffle.lane(2)) + offset).store_unaligned(&offsets_[cursor + 32]);
597 (u32x16(shuffle.lane(3)) + offset).store_unaligned(&offsets_[cursor + 48]);
598# ifdef LEXIT_DEBUG
599 for (int i = cursor; i < cursor + popcount; i++) {
600 int start = offsets_[i - 1];
601 int end = offsets_[i];
602 token_str_with_whitespace_debug_.emplace_back(str_.data() + start, end - start);
603 }
604# endif
605 cursor += popcount;
606 }
607 {
608 auto [shuffle, popcount] = shuffle_indices_from_emit_mask(emit_end_mask);
609 /* The offsets are contained inside the 8 bit shuffle vector.
610 * We need to promote it to 32 bit before adding the base offset. */
611 (u32x16(shuffle.lane(0)) + offset).store_unaligned(&offsets_end_[cursor_end + 0]);
612 (u32x16(shuffle.lane(1)) + offset).store_unaligned(&offsets_end_[cursor_end + 16]);
613 (u32x16(shuffle.lane(2)) + offset).store_unaligned(&offsets_end_[cursor_end + 32]);
614 (u32x16(shuffle.lane(3)) + offset).store_unaligned(&offsets_end_[cursor_end + 48]);
615# ifdef LEXIT_DEBUG
616 for (int i = cursor_end; i < cursor_end + popcount; i++) {
617 int start = offsets_[i];
618 int end = offsets_end_[i];
619 token_str_debug_.emplace_back(str_.data() + start, end - start);
620 }
621# endif
622 cursor_end += popcount;
623 }
624 assert(cursor_end == cursor || cursor_end + 1 == cursor);
625 }
626#endif
627
628 assert(cursor_end == cursor || cursor_end + 1 == cursor);
629
630 /* Finish tail using scalar loop. */
631 tokenize_scalar(
632 offset, cursor, cursor_end, prev_value, prev_whitespace, str_.size(), char_class_table);
633
634 assert(cursor_end == cursor || cursor_end + 1 == cursor);
635
636 /* Set end of last token. */
637 offsets_[cursor] = str_.size();
638 offsets_end_[cursor_end] = str_.size();
639 /* Set end of file token. */
640 types_[cursor] = EndOfFile;
641 size_ = cursor;
642}
643
645{
646 uint32_t tok_id = 0;
647#if defined(USE_NEON) || defined(USE_SSE4_2)
648 using namespace simd;
649 static constexpr int stride = 64;
650 for (; tok_id + stride <= size_; tok_id += stride) {
651 const u32x64 str_start = u32x64::load(&offsets_[tok_id]);
652 const u32x64 str_end = u32x64::load(&offsets_end_[tok_id]);
653 const u32x64 str_size_32 = str_end - str_start;
654 const u8x64 str_large = u8x64(str_size_32 > 127);
655 /* Saturate the size to max int8_t since SSE comparison is signed. */
656 const u8x64 str_size = select(u8x64(str_size_32), u8x64(127), str_large);
657 str_size.store(&lengths_[tok_id]);
658 }
659 /* Finish tail using scalar loop. */
660#endif
661 for (; tok_id < size_; ++tok_id) {
662 const uint32_t str_start = offsets_[tok_id];
663 const uint32_t str_end = offsets_end_[tok_id];
664 const uint32_t str_size_32 = str_end - str_start;
665 /* Saturate the size to max int8_t since SSE comparison is signed. */
666 const uint8_t str_size = select(uint8_t(str_size_32), 127, str_size_32 > 127);
667 lengths_[tok_id] = str_size;
668 }
669}
670
671void TokenBuffer::atomize_words(IdentifierMap &identifiers, const KeywordTable &keywords)
672{
673 static constexpr int stride = 64;
674
675 struct Masks {
676 uint64_t mask8, mask16, mask24, mask32;
677 };
678 /* First scan to create a bitmap of potential matches to avoid wasting cycles iterating over
679 * non-words. */
680 lexit::Vector<Masks> masks_small_id;
681 lexit::Vector<uint64_t> masks_large_id;
682 masks_small_id.resize(divide_ceil(size_, stride));
683 masks_large_id.resize(divide_ceil(size_, stride));
684
685 {
686 uint32_t chunk_id = 0;
687 uint32_t tok_id = 0;
688#if defined(USE_NEON) || defined(USE_SSE4_2)
689 using namespace simd;
690 for (; tok_id + stride <= size_; tok_id += stride, ++chunk_id) {
691 const u8x64 size = u8x64::load(&lengths_[tok_id]);
692 const u8x64 type = u8x64::load((uint8_t *)&types_[tok_id]);
693 const uint64_t is_word = movemask(type == Word);
694 const uint64_t less_8 = movemask(size < 9);
695 const uint64_t less_16 = movemask(size < 17);
696 const uint64_t less_24 = movemask(size < 25);
697 const uint64_t less_32 = movemask(size < 33);
698
699 Masks small;
700 small.mask8 = is_word & less_8;
701 small.mask16 = is_word & less_16 & ~less_8;
702 small.mask24 = is_word & less_24 & ~less_16;
703 small.mask32 = is_word & less_32 & ~less_24;
704 masks_small_id[chunk_id] = small;
705 masks_large_id[chunk_id] = is_word & ~less_32;
706 }
707#endif
708 for (; tok_id < size_; tok_id += stride, ++chunk_id) {
709 uint64_t is_word = 0, less_8 = 0, less_16 = 0, less_24 = 0, less_32 = 0;
710
711 for (int i = 0; i < stride && tok_id + i < size_; ++i) {
712 const uint8_t size = lengths_[tok_id + i];
713 const TokenType type = types_[tok_id + i];
714 const uint64_t bit = uint64_t(1) << i;
715 /* Generate a masks of all 1s if true, all 0s if false. */
716 is_word |= bit & -uint64_t(type == Word);
717 less_8 |= bit & -uint64_t(size < 9);
718 less_16 |= bit & -uint64_t(size < 17);
719 less_24 |= bit & -uint64_t(size < 25);
720 less_32 |= bit & -uint64_t(size < 33);
721 }
722
723 Masks small;
724 small.mask8 = is_word & less_8;
725 small.mask16 = is_word & less_16 & ~less_8;
726 small.mask24 = is_word & less_24 & ~less_16;
727 small.mask32 = is_word & less_32 & ~less_24;
728 masks_small_id[chunk_id] = small;
729 masks_large_id[chunk_id] = is_word & ~less_32;
730 }
731 }
732 {
733 /* Iterate over the bitmasks. */
734 const int end = divide_ceil(size_, stride);
735 /* The atomize_short_tokens_in_mask can read past the end of each token by 8 bytes.
736 * For this reason we process the last chunks that contains the last 8 tokens separately. */
737 const int end_safe = divide_ceil(int(size_) - 8, stride) - 1;
738 int chunk = 0;
739 for (; chunk < end_safe; ++chunk) {
740 const Masks small = masks_small_id[chunk];
741 atomize_short_tokens_in_mask<1>(small.mask8, chunk * stride, identifiers, keywords);
742 atomize_short_tokens_in_mask<2>(small.mask16, chunk * stride, identifiers, keywords);
743 atomize_short_tokens_in_mask<3>(small.mask24, chunk * stride, identifiers, keywords);
744 atomize_short_tokens_in_mask<4>(small.mask32, chunk * stride, identifiers, keywords);
745 atomize_tokens_in_mask(masks_large_id[chunk], chunk * stride, identifiers, keywords);
746 }
747 for (; chunk < end; ++chunk) {
748 const Masks small = masks_small_id[chunk];
749 atomize_tokens_in_mask(small.mask8, chunk * stride, identifiers, keywords);
750 atomize_tokens_in_mask(small.mask16, chunk * stride, identifiers, keywords);
751 atomize_tokens_in_mask(small.mask24, chunk * stride, identifiers, keywords);
752 atomize_tokens_in_mask(small.mask32, chunk * stride, identifiers, keywords);
753 atomize_tokens_in_mask(masks_large_id[chunk], chunk * stride, identifiers, keywords);
754 }
755 }
756}
757
758INLINE_METHOD void TokenBuffer::atomize_tokens_in_mask(uint64_t mask,
759 uint32_t tok_id_base,
761 const KeywordTable &kw_table)
762{
763 if (mask == 0) [[likely]] {
764 return;
765 }
766 while (mask != 0) {
767 const int index = builtin_ctzll(mask);
768 const int tok_id = tok_id_base + index;
769
770 const int str_start = offsets_[tok_id];
771 const int str_size = offsets_end_[tok_id] - str_start;
772 const std::string_view str = {str_.data() + str_start, size_t(str_size)};
773
774 const TokenAtom atom = id_map.lookup_or_add(str);
775 atoms_[tok_id] = atom;
776 types_[tok_id] = kw_table[atom];
777 /* Pop last bit. */
778 mask &= (mask - 1);
779 }
780}
781
782template<int Size>
783INLINE_METHOD void TokenBuffer::atomize_short_tokens_in_mask(uint64_t mask,
784 uint32_t tok_id_base,
785 IdentifierMap &id_map,
786 const KeywordTable &kw_table)
787{
788 while (mask != 0) {
789 const int index = builtin_ctzll(mask);
790 const int tok_id = tok_id_base + index;
791
792 const int str_start = offsets_[tok_id];
793 const int str_size = lengths_[tok_id]; /* PaddedString is for small identifier. */
794
795 const std::string_view str = {str_.data() + str_start, size_t(str_size)};
796 const PaddedString<Size> padded_str(str);
797
798 const TokenAtom atom = id_map.lookup_or_add(padded_str);
799 atoms_[tok_id] = atom;
800 types_[tok_id] = kw_table[atom];
801 /* Pop last bit. */
802 mask &= (mask - 1);
803 }
804}
805
806template void TokenBuffer::atomize_short_tokens_in_mask<1>(uint64_t,
807 uint32_t,
809 const KeywordTable &);
810template void TokenBuffer::atomize_short_tokens_in_mask<2>(uint64_t,
811 uint32_t,
813 const KeywordTable &);
814template void TokenBuffer::atomize_short_tokens_in_mask<3>(uint64_t,
815 uint32_t,
817 const KeywordTable &);
818template void TokenBuffer::atomize_short_tokens_in_mask<4>(uint64_t,
819 uint32_t,
821 const KeywordTable &);
822
823static void lex_string(const TokenType *types, uint32_t &cursor)
824{
825 const TokenType *ptr = types + cursor;
826 while (true) {
827 cursor++;
828 ptr++;
829 if (*ptr == '\\') {
830 /* Escaped character. Skip next. */
831 cursor++;
832 ptr++;
833 continue;
834 }
835 if (*ptr == String || *ptr == EndOfFile) {
836 return;
837 }
838 }
839}
840
841static void lex_float(const std::string_view str,
842 const TokenType *types,
843 const uint32_t *offsets,
844 const uint32_t *offsets_end_,
845 uint32_t &cursor)
846{
847 const TokenType *type = types + cursor;
848 const uint32_t *offset = offsets + cursor;
849 const uint32_t *offset_end_ = offsets_end_ + cursor;
850
851 /* If number is followed by whitespace itself. */
852 const bool followed_by_whitespace = offset_end_[0] != offset[1];
853 if (followed_by_whitespace) {
854 return;
855 }
856
857 while (true) {
858 cursor++;
859 type++;
860 offset++;
861 offset_end_++;
862
863 /* Check if the previous char was an exponent "e" char. */
864 if ((*type == '+' || *type == '-') && str[*offset - 1] != 'e') {
865 break;
866 }
867 if (!(*type == Word || *type == Number || *type == '.' || *type == '+' || *type == '-')) {
868 break;
869 }
870 /* Break if this token is part of the number but followed by a whitespace. */
871 const bool followed_by_whitespace = offset_end_[0] != offset[1];
872 if (followed_by_whitespace) {
873 /* Note: we don't want to do the cursor roll back since we want to merge this token. */
874 return;
875 }
876 }
877 /* We need to evaluate the token we broke on. */
878 cursor--;
879}
880
881static void lex_comment(const std::string_view str,
882 const TokenType *types,
883 const uint32_t *offsets,
884 uint32_t &cursor,
885 TokenType &out_type)
886{
887 const uint32_t start = offsets[cursor];
888 const TokenType *type = types + cursor;
889 const char c = str[start + 1];
890
891 size_t end_pos;
892 if (c == '/') {
893 /* Single-line comment. Search for end of line. */
894 end_pos = str.find('\n', start + 2);
895 }
896 else if (c == '*') {
897 /* Multi-line comment. Search for termination. */
898 end_pos = str.find("*/", start + 2);
899 /* Search for the closing slash. */
900 end_pos += (end_pos != std::string::npos) ? 1 : 0;
901 }
902 else {
903 /* Not a comment. */
904 return;
905 }
906
907 out_type = Comment;
908
909 while (*type != EndOfFile) {
910 const uint32_t tok_start = offsets[cursor];
911 /* Skip tokens until we find the one that starts after the end of the comment. */
912 if (tok_start > end_pos) {
913 break;
914 }
915 cursor++;
916 type++;
917 }
918 /* We need to evaluate the token we broke on. */
919 cursor--;
920}
921
922static bool is_whitespace(char c)
923{
924 return (c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\v' || c == '\f');
925}
926
927static void lex_angle(const std::string_view str,
928 const TokenType *types,
929 const uint32_t *offsets,
930 const uint32_t *offsets_end,
931 uint32_t &cursor,
932 TokenType &out_type)
933{
934 /* If this is the very first token, it cannot be preceded by anything. */
935 if (static_cast<const TokenType *>(&out_type) == types) {
936 return;
937 }
938 /* Extract the previously processed token type directly from the output stream. */
939 const TokenType prev = *(&out_type - 1);
940
941 /* Detect if preceded by whitespace by checking the literal char right before this token. */
942 bool preceded_by_space = false;
943 const uint32_t start = offsets[cursor];
944 if (start > 0) {
945 preceded_by_space = is_whitespace(str[start - 1]);
946 }
947
948 /* Mimic the template token identification logic. */
949 if (out_type == LThan) {
950 if (!preceded_by_space && prev != AngleOpen) {
951 /* TODO(fclem): Can't mutate them here because the whole legacy compiler depends on template
952 * token being AngleOpen. */
953 // out_type = TemplateOpen;
954 return;
955 }
956 /* Merge back split multi-tokens. */
957 {
958 const bool not_followed_by_whitespace = offsets_end[cursor] == offsets[cursor + 1];
959 if (types[cursor + 1] == LThan && not_followed_by_whitespace) {
960 cursor += 1; /* `<<` */
961 }
962 }
963 {
964 const bool not_followed_by_whitespace = offsets_end[cursor] == offsets[cursor + 1];
965 if (types[cursor + 1] == Assign && not_followed_by_whitespace) {
966 cursor += 1; /* `<<=` or `<=` */
967 }
968 }
969 }
970 else if (out_type == GThan) {
971 if (!preceded_by_space && prev != Minus
972 /* && prev != AngleClose // Only possible if we tag as TemplateClose. See below. */)
973 {
974 /* TODO(fclem): Can't mutate them here because the whole legacy compiler depends on template
975 * token being AngleClose. */
976 // out_type = TemplateClose;
977 if (prev != AngleClose) {
978 return;
979 }
980 /* WORKAROUND: Because the previous token cannot have been tagged as TemplateClose, we have
981 * to backtrack to check them. */
982 uint32_t curr = offsets[cursor];
983 while (--curr) {
984 if (str[curr] != '>') {
985 if (!is_whitespace(str[curr])) {
986 return; /* This is a TemplateClose. */
987 }
988 break;
989 }
990 }
991 }
992 /* Merge back split multi-tokens. */
993 {
994 const bool not_followed_by_whitespace = offsets_end[cursor] == offsets[cursor + 1];
995 if (types[cursor + 1] == GThan && not_followed_by_whitespace) {
996 cursor += 1; /* `>>` */
997 }
998 }
999 {
1000 const bool not_followed_by_whitespace = offsets_end[cursor] == offsets[cursor + 1];
1001 if (types[cursor + 1] == Assign && not_followed_by_whitespace) {
1002 cursor += 1; /* `>>=` or `>=` */
1003 }
1004 }
1005 }
1006}
1007
1008/* Ideally this should not be needed and the `tokenize` step should just parse them correctly.
1009 * But this would much harder to implement. */
1010void TokenBuffer::merge_complex_literals(bool bsl_template_angle_bracket_lexing)
1011{
1012 const TokenType *in_types = types_.get();
1013 TokenType *out_type = types_.get();
1014 const uint32_t *in_offsets = offsets_.get();
1015 const uint32_t *in_offset_end = offsets_end_.get();
1016 uint32_t *out_offset = offsets_.get();
1017 uint32_t *out_offset_end = offsets_end_.get();
1018
1019 for (uint32_t i = 0; i < size_; i++, out_type++, out_offset++, out_offset_end++) {
1020 const TokenType type = in_types[i];
1021 const uint32_t offset = in_offsets[i];
1022 const uint32_t offset_end = in_offset_end[i];
1023 *out_type = type;
1024 *out_offset = offset;
1025 *out_offset_end = offset_end;
1026
1027 switch (type) {
1028 case String:
1029 lex_string(in_types, i);
1030 break;
1031 case Number:
1032 lex_float(str_, in_types, in_offsets, in_offset_end, i);
1033 break;
1034 case Slash:
1035 lex_comment(str_, in_types, in_offsets, i, *out_type);
1036 break;
1037 case GThan:
1038 case LThan:
1039 if (bsl_template_angle_bracket_lexing) {
1040 lex_angle(str_, in_types, in_offsets, in_offset_end, i, *out_type);
1041 }
1042 break;
1043 default:
1044 continue;
1045 }
1046 /* Set the correct end for the complex token that have just been lexed. */
1047 *out_offset_end = in_offset_end[i];
1048 }
1049
1050 assert(in_types <= out_type);
1051 assert(out_type - in_types < 0xFFFFFFFFu);
1052 size_ = out_type - in_types;
1054 offsets_[size_] = str_.size();
1055}
1056
1057} // namespace lexit
unsigned long long int uint64_t
#define str(s)
#define assert(assertion)
#define index(i)
#define select(A, B, C)
bool is_zero(float3x3 a)
#define INLINE_METHOD
Definition identifier.hh:19
ccl_device_inline uint popcount(const uint x)
Definition math_base.h:734
ccl_device_inline float2 mask(const MaskType mask, const float2 a)
#define T
unsigned char uint8_t
Definition BKE_text.h:79
ATTR_WARN_UNUSED_RESULT const BMVert * v2
uint16_t TokenAtom
Definition types.hh:159
TokenType
Definition types.hh:41
@ GThan
Definition types.hh:149
@ Slash
Definition types.hh:155
@ EndOfFile
Definition types.hh:77
@ LThan
Definition types.hh:150
@ String
Definition types.hh:154
@ Number
Definition types.hh:44
@ Comment
Definition types.hh:132
@ Assign
Definition types.hh:61
@ Minus
Definition types.hh:69
@ AngleOpen
Definition types.hh:59
@ Word
Definition types.hh:43
@ AngleClose
Definition types.hh:60
static void lex_comment(const std::string_view str, const TokenType *types, const uint32_t *offsets, uint32_t &cursor, TokenType &out_type)
Definition lexit.cc:881
static void lex_float(const std::string_view str, const TokenType *types, const uint32_t *offsets, const uint32_t *offsets_end_, uint32_t &cursor)
Definition lexit.cc:841
void realloc_aligned_array(AlignedArrayPtr< T > &ptr, size_t elem_count, size_t new_size)
Definition lexit.cc:45
static void lex_angle(const std::string_view str, const TokenType *types, const uint32_t *offsets, const uint32_t *offsets_end, uint32_t &cursor, TokenType &out_type)
Definition lexit.cc:927
static uint32_t divide_ceil(uint32_t a, uint32_t b)
Definition lexit.cc:38
const CharClass char_class_table[128]
Definition tables.hh:12
static void lex_string(const TokenType *types, uint32_t &cursor)
Definition lexit.cc:823
static bool is_whitespace(char c)
Definition lexit.cc:922
CharClass
Definition types.hh:20
@ ClassToTypeThreshold
Definition types.hh:36
TokenType select(char char_value, char char_class, bool cond)
Definition lexit.cc:418
static int builtin_ctzll(uint64_t a)
Definition lexit.cc:27
INLINE_METHOD TokenAtom lookup_or_add(StringT str)
std::string_view str_
Definition lexit.hh:123
AlignedArrayPtr< uint32_t > offsets_
Definition lexit.hh:127
TokenIt end()
Definition lexit.hh:302
void merge_complex_literals(bool bsl_template_angle_bracket_lexing=false)
Merge complex literals such as floats, strings and comments.
Definition lexit.cc:1010
uint32_t allocated_size_
Definition lexit.hh:137
void compute_lengths()
Compute small token length for speeding up certain tasks.
Definition lexit.cc:644
void atomize_words(IdentifierMap &identifiers, const KeywordTable &keywords)
Assign keyword types and atoms for a small set of identifier.
Definition lexit.cc:671
void clear()
Discard all currently held data. Does not reallocate.
Definition lexit.cc:55
uint32_t size() const
Return the amount of token inside the buffer.
Definition lexit.hh:214
AlignedArrayPtr< uint8_t > lengths_
Definition lexit.hh:131
void reserve(const uint32_t count)
Allocate backing memory for the given number of tokens and move currently held data.
Definition lexit.cc:60
AlignedArrayPtr< TokenType > types_
Definition lexit.hh:125
void tokenize(const CharClass char_class_table[128])
Tokenizes the input string by grouping contiguous characters of the same class.
Definition lexit.cc:488
AlignedArrayPtr< uint32_t > offsets_end_
Definition lexit.hh:129
AlignedArrayPtr< TokenAtom > atoms_
Definition lexit.hh:133
uint32_t size_
Definition lexit.hh:135
void resize(int new_size)
Definition vector.hh:94