/src/croaring/src/containers/bitset.c
Line | Count | Source |
1 | | /* |
2 | | * bitset.c |
3 | | * |
4 | | */ |
5 | | #include <assert.h> |
6 | | #include <stdio.h> |
7 | | #include <stdlib.h> |
8 | | #include <string.h> |
9 | | |
10 | | #include <roaring/bitset_util.h> |
11 | | #include <roaring/containers/array.h> |
12 | | #include <roaring/containers/bitset.h> |
13 | | #include <roaring/memory.h> |
14 | | #include <roaring/portability.h> |
15 | | #include <roaring/utilasm.h> |
16 | | |
17 | | #if CROARING_IS_X64 |
18 | | #ifndef CROARING_COMPILER_SUPPORTS_AVX512 |
19 | | #error "CROARING_COMPILER_SUPPORTS_AVX512 needs to be defined." |
20 | | #endif // CROARING_COMPILER_SUPPORTS_AVX512 |
21 | | #endif |
22 | | |
23 | | #if defined(__GNUC__) && !defined(__clang__) |
24 | | #pragma GCC diagnostic push |
25 | | #pragma GCC diagnostic ignored "-Wuninitialized" |
26 | | #pragma GCC diagnostic ignored "-Wmaybe-uninitialized" |
27 | | #endif |
28 | | #ifdef __cplusplus |
29 | | extern "C" { |
30 | | namespace roaring { |
31 | | namespace internal { |
32 | | #endif |
33 | | |
34 | | extern inline int bitset_container_cardinality( |
35 | | const bitset_container_t *bitset); |
36 | | extern inline void bitset_container_set(bitset_container_t *bitset, |
37 | | uint16_t pos); |
38 | | // unused at this time: |
39 | | // extern inline void bitset_container_unset(bitset_container_t *bitset, |
40 | | // uint16_t pos); |
41 | | extern inline bool bitset_container_get(const bitset_container_t *bitset, |
42 | | uint16_t pos); |
43 | | extern inline int32_t bitset_container_serialized_size_in_bytes(void); |
44 | | extern inline bool bitset_container_add(bitset_container_t *bitset, |
45 | | uint16_t pos); |
46 | | extern inline bool bitset_container_remove(bitset_container_t *bitset, |
47 | | uint16_t pos); |
48 | | extern inline bool bitset_container_contains(const bitset_container_t *bitset, |
49 | | uint16_t pos); |
50 | | |
51 | 0 | void bitset_container_clear(bitset_container_t *bitset) { |
52 | 0 | memset(bitset->words, 0, sizeof(uint64_t) * BITSET_CONTAINER_SIZE_IN_WORDS); |
53 | 0 | bitset->cardinality = 0; |
54 | 0 | } |
55 | | |
56 | 0 | void bitset_container_set_all(bitset_container_t *bitset) { |
57 | 0 | memset(bitset->words, INT64_C(-1), |
58 | 0 | sizeof(uint64_t) * BITSET_CONTAINER_SIZE_IN_WORDS); |
59 | 0 | bitset->cardinality = (1 << 16); |
60 | 0 | } |
61 | | |
62 | 954 | static bitset_container_t *bitset_container_allocate(void) { |
63 | 954 | bitset_container_t *bitset = |
64 | 954 | (bitset_container_t *)roaring_malloc(sizeof(bitset_container_t)); |
65 | | |
66 | 954 | if (!bitset) { |
67 | 0 | return NULL; |
68 | 0 | } |
69 | | |
70 | 954 | size_t align_size = 32; |
71 | 954 | #if CROARING_IS_X64 |
72 | 954 | int support = croaring_hardware_support(); |
73 | 954 | if (support & ROARING_SUPPORTS_AVX512) { |
74 | | // sizeof(__m512i) == 64 |
75 | 0 | align_size = 64; |
76 | 954 | } else { |
77 | | // sizeof(__m256i) == 32 |
78 | 954 | align_size = 32; |
79 | 954 | } |
80 | 954 | #endif |
81 | 954 | bitset->words = (uint64_t *)roaring_aligned_malloc( |
82 | 954 | align_size, sizeof(uint64_t) * BITSET_CONTAINER_SIZE_IN_WORDS); |
83 | 954 | if (!bitset->words) { |
84 | 0 | roaring_free(bitset); |
85 | 0 | return NULL; |
86 | 0 | } |
87 | 954 | return bitset; |
88 | 954 | } |
89 | | |
90 | | /* Create a new bitset. Return NULL in case of failure. */ |
91 | 0 | bitset_container_t *bitset_container_create(void) { |
92 | 0 | bitset_container_t *bitset = bitset_container_allocate(); |
93 | 0 | if (bitset) { |
94 | 0 | bitset_container_clear(bitset); |
95 | 0 | } |
96 | 0 | return bitset; |
97 | 0 | } |
98 | | |
99 | 954 | bitset_container_t *bitset_container_create_uninitialized(void) { |
100 | 954 | bitset_container_t *bitset = bitset_container_allocate(); |
101 | 954 | if (bitset) { |
102 | 954 | bitset->cardinality = 0; |
103 | 954 | } |
104 | 954 | return bitset; |
105 | 954 | } |
106 | | |
107 | | /* Copy one container into another. We assume that they are distinct. */ |
108 | | void bitset_container_copy(const bitset_container_t *source, |
109 | 0 | bitset_container_t *dest) { |
110 | 0 | dest->cardinality = source->cardinality; |
111 | 0 | memcpy(dest->words, source->words, |
112 | 0 | sizeof(uint64_t) * BITSET_CONTAINER_SIZE_IN_WORDS); |
113 | 0 | } |
114 | | |
115 | | void bitset_container_add_from_range(bitset_container_t *bitset, uint32_t min, |
116 | 0 | uint32_t max, uint16_t step) { |
117 | 0 | if (step == 0) return; // refuse to crash |
118 | 0 | if ((64 % step) == 0) { // step divides 64 |
119 | 0 | uint64_t mask = 0; // construct the repeated mask |
120 | 0 | for (uint32_t value = (min % step); value < 64; value += step) { |
121 | 0 | mask |= ((uint64_t)1 << value); |
122 | 0 | } |
123 | 0 | uint32_t firstword = min / 64; |
124 | 0 | uint32_t endword = (max - 1) / 64; |
125 | 0 | bitset->cardinality = (max - min + step - 1) / step; |
126 | 0 | if (firstword == endword) { |
127 | 0 | bitset->words[firstword] |= |
128 | 0 | mask & (((~UINT64_C(0)) << (min % 64)) & |
129 | 0 | ((~UINT64_C(0)) >> ((~max + 1) % 64))); |
130 | 0 | return; |
131 | 0 | } |
132 | 0 | bitset->words[firstword] = mask & ((~UINT64_C(0)) << (min % 64)); |
133 | 0 | for (uint32_t i = firstword + 1; i < endword; i++) |
134 | 0 | bitset->words[i] = mask; |
135 | 0 | bitset->words[endword] = mask & ((~UINT64_C(0)) >> ((~max + 1) % 64)); |
136 | 0 | } else { |
137 | 0 | for (uint32_t value = min; value < max; value += step) { |
138 | 0 | bitset_container_add(bitset, value); |
139 | 0 | } |
140 | 0 | } |
141 | 0 | } |
142 | | |
143 | | /* Free memory. */ |
144 | 954 | void bitset_container_free(bitset_container_t *bitset) { |
145 | 954 | if (bitset == NULL) return; |
146 | 954 | roaring_aligned_free(bitset->words); |
147 | 954 | roaring_free(bitset); |
148 | 954 | } |
149 | | |
150 | | /* duplicate container. */ |
151 | | CROARING_ALLOW_UNALIGNED |
152 | 0 | bitset_container_t *bitset_container_clone(const bitset_container_t *src) { |
153 | 0 | bitset_container_t *bitset = |
154 | 0 | (bitset_container_t *)roaring_malloc(sizeof(bitset_container_t)); |
155 | |
|
156 | 0 | if (!bitset) { |
157 | 0 | return NULL; |
158 | 0 | } |
159 | | |
160 | 0 | size_t align_size = 32; |
161 | 0 | #if CROARING_IS_X64 |
162 | 0 | if (croaring_hardware_support() & ROARING_SUPPORTS_AVX512) { |
163 | | // sizeof(__m512i) == 64 |
164 | 0 | align_size = 64; |
165 | 0 | } else { |
166 | | // sizeof(__m256i) == 32 |
167 | 0 | align_size = 32; |
168 | 0 | } |
169 | 0 | #endif |
170 | 0 | bitset->words = (uint64_t *)roaring_aligned_malloc( |
171 | 0 | align_size, sizeof(uint64_t) * BITSET_CONTAINER_SIZE_IN_WORDS); |
172 | 0 | if (!bitset->words) { |
173 | 0 | roaring_free(bitset); |
174 | 0 | return NULL; |
175 | 0 | } |
176 | 0 | bitset->cardinality = src->cardinality; |
177 | 0 | memcpy(bitset->words, src->words, |
178 | 0 | sizeof(uint64_t) * BITSET_CONTAINER_SIZE_IN_WORDS); |
179 | 0 | return bitset; |
180 | 0 | } |
181 | | |
182 | | void bitset_container_offset(const bitset_container_t *c, container_t **loc, |
183 | 0 | container_t **hic, uint16_t offset) { |
184 | 0 | bitset_container_t *bc = NULL; |
185 | 0 | uint64_t val; |
186 | 0 | uint16_t b, i, end; |
187 | |
|
188 | 0 | b = offset >> 6; |
189 | 0 | i = offset % 64; |
190 | 0 | end = 1024 - b; |
191 | |
|
192 | 0 | if (loc != NULL) { |
193 | 0 | bc = bitset_container_create(); |
194 | 0 | if (i == 0) { |
195 | 0 | memcpy(bc->words + b, c->words, 8 * end); |
196 | 0 | } else { |
197 | 0 | bc->words[b] = c->words[0] << i; |
198 | 0 | for (uint32_t k = 1; k < end; ++k) { |
199 | 0 | val = c->words[k] << i; |
200 | 0 | val |= c->words[k - 1] >> (64 - i); |
201 | 0 | bc->words[b + k] = val; |
202 | 0 | } |
203 | 0 | } |
204 | |
|
205 | 0 | bc->cardinality = bitset_container_compute_cardinality(bc); |
206 | 0 | if (bc->cardinality != 0) { |
207 | 0 | *loc = bc; |
208 | 0 | } |
209 | 0 | if (bc->cardinality == c->cardinality) { |
210 | 0 | return; |
211 | 0 | } |
212 | 0 | } |
213 | | |
214 | 0 | if (hic == NULL) { |
215 | | // Both hic and loc can't be NULL, so bc is never NULL here |
216 | 0 | if (bc->cardinality == 0) { |
217 | 0 | bitset_container_free(bc); |
218 | 0 | } |
219 | 0 | return; |
220 | 0 | } |
221 | | |
222 | 0 | if (bc == NULL || bc->cardinality != 0) { |
223 | 0 | bc = bitset_container_create(); |
224 | 0 | } |
225 | |
|
226 | 0 | if (i == 0) { |
227 | 0 | memcpy(bc->words, c->words + end, 8 * b); |
228 | 0 | } else { |
229 | 0 | for (uint32_t k = end; k < 1024; ++k) { |
230 | 0 | val = c->words[k] << i; |
231 | 0 | val |= c->words[k - 1] >> (64 - i); |
232 | 0 | bc->words[k - end] = val; |
233 | 0 | } |
234 | 0 | bc->words[b] = c->words[1023] >> (64 - i); |
235 | 0 | } |
236 | |
|
237 | 0 | bc->cardinality = bitset_container_compute_cardinality(bc); |
238 | 0 | if (bc->cardinality == 0) { |
239 | 0 | bitset_container_free(bc); |
240 | 0 | return; |
241 | 0 | } |
242 | 0 | *hic = bc; |
243 | 0 | } |
244 | | |
245 | | void bitset_container_set_range(bitset_container_t *bitset, uint32_t begin, |
246 | 0 | uint32_t end) { |
247 | 0 | bitset_set_range(bitset->words, begin, end); |
248 | 0 | bitset->cardinality = |
249 | 0 | bitset_container_compute_cardinality(bitset); // could be smarter |
250 | 0 | } |
251 | | |
252 | | bool bitset_container_intersect(const bitset_container_t *src_1, |
253 | 0 | const bitset_container_t *src_2) { |
254 | | // could vectorize, but this is probably already quite fast in practice |
255 | 0 | const uint64_t *__restrict__ words_1 = src_1->words; |
256 | 0 | const uint64_t *__restrict__ words_2 = src_2->words; |
257 | 0 | for (int i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i++) { |
258 | 0 | if ((words_1[i] & words_2[i]) != 0) return true; |
259 | 0 | } |
260 | 0 | return false; |
261 | 0 | } |
262 | | |
263 | | #if CROARING_IS_X64 |
264 | | #ifndef CROARING_WORDS_IN_AVX2_REG |
265 | 65 | #define CROARING_WORDS_IN_AVX2_REG sizeof(__m256i) / sizeof(uint64_t) |
266 | | #endif |
267 | | #ifndef WORDS_IN_AVX512_REG |
268 | 0 | #define WORDS_IN_AVX512_REG sizeof(__m512i) / sizeof(uint64_t) |
269 | | #endif |
270 | | /* Get the number of bits set (force computation) */ |
271 | | static inline int _scalar_bitset_container_compute_cardinality( |
272 | 0 | const bitset_container_t *bitset) { |
273 | 0 | const uint64_t *words = bitset->words; |
274 | 0 | int32_t sum = 0; |
275 | 0 | for (int i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 4) { |
276 | 0 | sum += roaring_hamming(words[i]); |
277 | 0 | sum += roaring_hamming(words[i + 1]); |
278 | 0 | sum += roaring_hamming(words[i + 2]); |
279 | 0 | sum += roaring_hamming(words[i + 3]); |
280 | 0 | } |
281 | 0 | return sum; |
282 | 0 | } |
283 | | /* Get the number of bits set (force computation) */ |
284 | 65 | int bitset_container_compute_cardinality(const bitset_container_t *bitset) { |
285 | 65 | int support = croaring_hardware_support(); |
286 | 65 | #if CROARING_COMPILER_SUPPORTS_AVX512 |
287 | 65 | if (support & ROARING_SUPPORTS_AVX512) { |
288 | 0 | return (int)avx512_vpopcount( |
289 | 0 | (const __m512i *)bitset->words, |
290 | 0 | BITSET_CONTAINER_SIZE_IN_WORDS / (WORDS_IN_AVX512_REG)); |
291 | 0 | } else |
292 | 65 | #endif // CROARING_COMPILER_SUPPORTS_AVX512 |
293 | 65 | if (support & ROARING_SUPPORTS_AVX2) { |
294 | 65 | return (int)avx2_harley_seal_popcount256( |
295 | 65 | (const __m256i *)bitset->words, |
296 | 65 | BITSET_CONTAINER_SIZE_IN_WORDS / (CROARING_WORDS_IN_AVX2_REG)); |
297 | 65 | } else { |
298 | 0 | return _scalar_bitset_container_compute_cardinality(bitset); |
299 | 0 | } |
300 | 65 | } |
301 | | |
302 | | #elif defined(CROARING_USENEON) |
303 | | int bitset_container_compute_cardinality(const bitset_container_t *bitset) { |
304 | | uint16x8_t n0 = vdupq_n_u16(0); |
305 | | uint16x8_t n1 = vdupq_n_u16(0); |
306 | | uint16x8_t n2 = vdupq_n_u16(0); |
307 | | uint16x8_t n3 = vdupq_n_u16(0); |
308 | | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 8) { |
309 | | uint64x2_t c0 = vld1q_u64(&bitset->words[i + 0]); |
310 | | n0 = vaddq_u16(n0, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c0)))); |
311 | | uint64x2_t c1 = vld1q_u64(&bitset->words[i + 2]); |
312 | | n1 = vaddq_u16(n1, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c1)))); |
313 | | uint64x2_t c2 = vld1q_u64(&bitset->words[i + 4]); |
314 | | n2 = vaddq_u16(n2, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c2)))); |
315 | | uint64x2_t c3 = vld1q_u64(&bitset->words[i + 6]); |
316 | | n3 = vaddq_u16(n3, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c3)))); |
317 | | } |
318 | | uint64x2_t n = vdupq_n_u64(0); |
319 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n0))); |
320 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n1))); |
321 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n2))); |
322 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n3))); |
323 | | return vgetq_lane_u64(n, 0) + vgetq_lane_u64(n, 1); |
324 | | } |
325 | | |
326 | | #else // CROARING_IS_X64 |
327 | | |
328 | | /* Get the number of bits set (force computation) */ |
329 | | int bitset_container_compute_cardinality(const bitset_container_t *bitset) { |
330 | | const uint64_t *words = bitset->words; |
331 | | int32_t sum = 0; |
332 | | for (int i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 4) { |
333 | | sum += roaring_hamming(words[i]); |
334 | | sum += roaring_hamming(words[i + 1]); |
335 | | sum += roaring_hamming(words[i + 2]); |
336 | | sum += roaring_hamming(words[i + 3]); |
337 | | } |
338 | | return sum; |
339 | | } |
340 | | |
341 | | #endif // CROARING_IS_X64 |
342 | | |
343 | | #if CROARING_IS_X64 |
344 | | |
345 | | #define CROARING_BITSET_CONTAINER_FN_REPEAT 8 |
346 | | #ifndef WORDS_IN_AVX512_REG |
347 | | #define WORDS_IN_AVX512_REG sizeof(__m512i) / sizeof(uint64_t) |
348 | | #endif // WORDS_IN_AVX512_REG |
349 | | |
350 | | /* Computes a binary operation (eg union) on bitset1 and bitset2 and write the |
351 | | result to bitsetout */ |
352 | | // clang-format off |
353 | | #define CROARING_AVX512_BITSET_CONTAINER_FN1(before, opname, opsymbol, avx_intrinsic, \ |
354 | | neon_intrinsic, after) \ |
355 | | static inline int _avx512_bitset_container_##opname##_nocard( \ |
356 | | const bitset_container_t *src_1, const bitset_container_t *src_2, \ |
357 | 0 | bitset_container_t *dst) { \ |
358 | 0 | const uint8_t * __restrict__ words_1 = (const uint8_t *)src_1->words; \ |
359 | 0 | const uint8_t * __restrict__ words_2 = (const uint8_t *)src_2->words; \ |
360 | 0 | /* not using the blocking optimization for some reason*/ \ |
361 | 0 | uint8_t *out = (uint8_t*)dst->words; \ |
362 | 0 | const int innerloop = 8; \ |
363 | 0 | for (size_t i = 0; \ |
364 | 0 | i < BITSET_CONTAINER_SIZE_IN_WORDS / (WORDS_IN_AVX512_REG); \ |
365 | 0 | i+=innerloop) { \ |
366 | 0 | __m512i A1, A2, AO; \ |
367 | 0 | A1 = _mm512_loadu_si512((const __m512i *)(words_1)); \ |
368 | 0 | A2 = _mm512_loadu_si512((const __m512i *)(words_2)); \ |
369 | 0 | AO = avx_intrinsic(A2, A1); \ |
370 | 0 | _mm512_storeu_si512((__m512i *)out, AO); \ |
371 | 0 | A1 = _mm512_loadu_si512((const __m512i *)(words_1 + 64)); \ |
372 | 0 | A2 = _mm512_loadu_si512((const __m512i *)(words_2 + 64)); \ |
373 | 0 | AO = avx_intrinsic(A2, A1); \ |
374 | 0 | _mm512_storeu_si512((__m512i *)(out+64), AO); \ |
375 | 0 | A1 = _mm512_loadu_si512((const __m512i *)(words_1 + 128)); \ |
376 | 0 | A2 = _mm512_loadu_si512((const __m512i *)(words_2 + 128)); \ |
377 | 0 | AO = avx_intrinsic(A2, A1); \ |
378 | 0 | _mm512_storeu_si512((__m512i *)(out+128), AO); \ |
379 | 0 | A1 = _mm512_loadu_si512((const __m512i *)(words_1 + 192)); \ |
380 | 0 | A2 = _mm512_loadu_si512((const __m512i *)(words_2 + 192)); \ |
381 | 0 | AO = avx_intrinsic(A2, A1); \ |
382 | 0 | _mm512_storeu_si512((__m512i *)(out+192), AO); \ |
383 | 0 | A1 = _mm512_loadu_si512((const __m512i *)(words_1 + 256)); \ |
384 | 0 | A2 = _mm512_loadu_si512((const __m512i *)(words_2 + 256)); \ |
385 | 0 | AO = avx_intrinsic(A2, A1); \ |
386 | 0 | _mm512_storeu_si512((__m512i *)(out+256), AO); \ |
387 | 0 | A1 = _mm512_loadu_si512((const __m512i *)(words_1 + 320)); \ |
388 | 0 | A2 = _mm512_loadu_si512((const __m512i *)(words_2 + 320)); \ |
389 | 0 | AO = avx_intrinsic(A2, A1); \ |
390 | 0 | _mm512_storeu_si512((__m512i *)(out+320), AO); \ |
391 | 0 | A1 = _mm512_loadu_si512((const __m512i *)(words_1 + 384)); \ |
392 | 0 | A2 = _mm512_loadu_si512((const __m512i *)(words_2 + 384)); \ |
393 | 0 | AO = avx_intrinsic(A2, A1); \ |
394 | 0 | _mm512_storeu_si512((__m512i *)(out+384), AO); \ |
395 | 0 | A1 = _mm512_loadu_si512((const __m512i *)(words_1 + 448)); \ |
396 | 0 | A2 = _mm512_loadu_si512((const __m512i *)(words_2 + 448)); \ |
397 | 0 | AO = avx_intrinsic(A2, A1); \ |
398 | 0 | _mm512_storeu_si512((__m512i *)(out+448), AO); \ |
399 | 0 | out+=512; \ |
400 | 0 | words_1 += 512; \ |
401 | 0 | words_2 += 512; \ |
402 | 0 | } \ |
403 | 0 | dst->cardinality = BITSET_UNKNOWN_CARDINALITY; \ |
404 | 0 | return dst->cardinality; \ |
405 | 0 | } Unexecuted instantiation: bitset.c:_avx512_bitset_container_or_nocard Unexecuted instantiation: bitset.c:_avx512_bitset_container_union_nocard Unexecuted instantiation: bitset.c:_avx512_bitset_container_and_nocard Unexecuted instantiation: bitset.c:_avx512_bitset_container_intersection_nocard Unexecuted instantiation: bitset.c:_avx512_bitset_container_xor_nocard Unexecuted instantiation: bitset.c:_avx512_bitset_container_andnot_nocard |
406 | | |
407 | | #define CROARING_AVX512_BITSET_CONTAINER_FN2(before, opname, opsymbol, avx_intrinsic, \ |
408 | | neon_intrinsic, after) \ |
409 | | /* next, a version that updates cardinality*/ \ |
410 | | static inline int _avx512_bitset_container_##opname(const bitset_container_t *src_1, \ |
411 | | const bitset_container_t *src_2, \ |
412 | 0 | bitset_container_t *dst) { \ |
413 | 0 | const __m512i * __restrict__ words_1 = (const __m512i *) src_1->words; \ |
414 | 0 | const __m512i * __restrict__ words_2 = (const __m512i *) src_2->words; \ |
415 | 0 | __m512i *out = (__m512i *) dst->words; \ |
416 | 0 | dst->cardinality = (int32_t)avx512_harley_seal_popcount512andstore_##opname(words_2,\ |
417 | 0 | words_1, out,BITSET_CONTAINER_SIZE_IN_WORDS / (WORDS_IN_AVX512_REG)); \ |
418 | 0 | return dst->cardinality; \ |
419 | 0 | } Unexecuted instantiation: bitset.c:_avx512_bitset_container_or Unexecuted instantiation: bitset.c:_avx512_bitset_container_union Unexecuted instantiation: bitset.c:_avx512_bitset_container_and Unexecuted instantiation: bitset.c:_avx512_bitset_container_intersection Unexecuted instantiation: bitset.c:_avx512_bitset_container_xor Unexecuted instantiation: bitset.c:_avx512_bitset_container_andnot |
420 | | |
421 | | #define CROARING_AVX512_BITSET_CONTAINER_FN3(before, opname, opsymbol, avx_intrinsic, \ |
422 | | neon_intrinsic, after) \ |
423 | | /* next, a version that just computes the cardinality*/ \ |
424 | | static inline int _avx512_bitset_container_##opname##_justcard( \ |
425 | 0 | const bitset_container_t *src_1, const bitset_container_t *src_2) { \ |
426 | 0 | const __m512i * __restrict__ data1 = (const __m512i *) src_1->words; \ |
427 | 0 | const __m512i * __restrict__ data2 = (const __m512i *) src_2->words; \ |
428 | 0 | return (int)avx512_harley_seal_popcount512_##opname(data2, \ |
429 | 0 | data1, BITSET_CONTAINER_SIZE_IN_WORDS / (WORDS_IN_AVX512_REG)); \ |
430 | 0 | } Unexecuted instantiation: bitset.c:_avx512_bitset_container_or_justcard Unexecuted instantiation: bitset.c:_avx512_bitset_container_union_justcard Unexecuted instantiation: bitset.c:_avx512_bitset_container_and_justcard Unexecuted instantiation: bitset.c:_avx512_bitset_container_intersection_justcard Unexecuted instantiation: bitset.c:_avx512_bitset_container_xor_justcard Unexecuted instantiation: bitset.c:_avx512_bitset_container_andnot_justcard |
431 | | |
432 | | |
433 | | // we duplicate the function because other containers use the "or" term, makes API more consistent |
434 | | #if CROARING_COMPILER_SUPPORTS_AVX512 |
435 | | CROARING_TARGET_AVX512 |
436 | | CROARING_AVX512_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX512, or, |, _mm512_or_si512, vorrq_u64, CROARING_UNTARGET_AVX512) |
437 | | CROARING_UNTARGET_AVX512 |
438 | | CROARING_TARGET_AVX512 |
439 | | CROARING_AVX512_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX512, union, |, _mm512_or_si512, vorrq_u64, CROARING_UNTARGET_AVX512) |
440 | | CROARING_UNTARGET_AVX512 |
441 | | |
442 | | // we duplicate the function because other containers use the "intersection" term, makes API more consistent |
443 | | CROARING_TARGET_AVX512 |
444 | | CROARING_AVX512_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX512, and, &, _mm512_and_si512, vandq_u64, CROARING_UNTARGET_AVX512) |
445 | | CROARING_UNTARGET_AVX512 |
446 | | CROARING_TARGET_AVX512 |
447 | | CROARING_AVX512_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX512, intersection, &, _mm512_and_si512, vandq_u64, CROARING_UNTARGET_AVX512) |
448 | | CROARING_UNTARGET_AVX512 |
449 | | |
450 | | CROARING_TARGET_AVX512 |
451 | | CROARING_AVX512_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX512, xor, ^, _mm512_xor_si512, veorq_u64, CROARING_UNTARGET_AVX512) |
452 | | CROARING_UNTARGET_AVX512 |
453 | | CROARING_TARGET_AVX512 |
454 | | CROARING_AVX512_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX512, andnot, &~, _mm512_andnot_si512, vbicq_u64, CROARING_UNTARGET_AVX512) |
455 | | CROARING_UNTARGET_AVX512 |
456 | | |
457 | | // we duplicate the function because other containers use the "or" term, makes API more consistent |
458 | | CROARING_TARGET_AVX512 |
459 | | CROARING_AVX512_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX512, or, |, _mm512_or_si512, vorrq_u64, CROARING_UNTARGET_AVX512) |
460 | | CROARING_UNTARGET_AVX512 |
461 | | CROARING_TARGET_AVX512 |
462 | | CROARING_AVX512_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX512, union, |, _mm512_or_si512, vorrq_u64, CROARING_UNTARGET_AVX512) |
463 | | CROARING_UNTARGET_AVX512 |
464 | | |
465 | | // we duplicate the function because other containers use the "intersection" term, makes API more consistent |
466 | | CROARING_TARGET_AVX512 |
467 | | CROARING_AVX512_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX512, and, &, _mm512_and_si512, vandq_u64, CROARING_UNTARGET_AVX512) |
468 | | CROARING_UNTARGET_AVX512 |
469 | | CROARING_TARGET_AVX512 |
470 | | CROARING_AVX512_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX512, intersection, &, _mm512_and_si512, vandq_u64, CROARING_UNTARGET_AVX512) |
471 | | CROARING_UNTARGET_AVX512 |
472 | | |
473 | | CROARING_TARGET_AVX512 |
474 | | CROARING_AVX512_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX512, xor, ^, _mm512_xor_si512, veorq_u64, CROARING_UNTARGET_AVX512) |
475 | | CROARING_UNTARGET_AVX512 |
476 | | CROARING_TARGET_AVX512 |
477 | | CROARING_AVX512_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX512, andnot, &~, _mm512_andnot_si512, vbicq_u64, CROARING_UNTARGET_AVX512) |
478 | | CROARING_UNTARGET_AVX512 |
479 | | |
480 | | // we duplicate the function because other containers use the "or" term, makes API more consistent |
481 | | CROARING_TARGET_AVX512 |
482 | | CROARING_AVX512_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX512, or, |, _mm512_or_si512, vorrq_u64, CROARING_UNTARGET_AVX512) |
483 | | CROARING_UNTARGET_AVX512 |
484 | | CROARING_TARGET_AVX512 |
485 | | CROARING_AVX512_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX512, union, |, _mm512_or_si512, vorrq_u64, CROARING_UNTARGET_AVX512) |
486 | | CROARING_UNTARGET_AVX512 |
487 | | |
488 | | // we duplicate the function because other containers use the "intersection" term, makes API more consistent |
489 | | CROARING_TARGET_AVX512 |
490 | | CROARING_AVX512_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX512, and, &, _mm512_and_si512, vandq_u64, CROARING_UNTARGET_AVX512) |
491 | | CROARING_UNTARGET_AVX512 |
492 | | CROARING_TARGET_AVX512 |
493 | | CROARING_AVX512_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX512, intersection, &, _mm512_and_si512, vandq_u64, CROARING_UNTARGET_AVX512) |
494 | | CROARING_UNTARGET_AVX512 |
495 | | |
496 | | CROARING_TARGET_AVX512 |
497 | | CROARING_AVX512_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX512, xor, ^, _mm512_xor_si512, veorq_u64, CROARING_UNTARGET_AVX512) |
498 | | CROARING_UNTARGET_AVX512 |
499 | | CROARING_TARGET_AVX512 |
500 | | CROARING_AVX512_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX512, andnot, &~, _mm512_andnot_si512, vbicq_u64, CROARING_UNTARGET_AVX512) |
501 | | CROARING_UNTARGET_AVX512 |
502 | | #endif // CROARING_COMPILER_SUPPORTS_AVX512 |
503 | | |
504 | | #ifndef CROARING_WORDS_IN_AVX2_REG |
505 | | #define CROARING_WORDS_IN_AVX2_REG sizeof(__m256i) / sizeof(uint64_t) |
506 | | #endif // CROARING_WORDS_IN_AVX2_REG |
507 | | #define CROARING_LOOP_SIZE \ |
508 | | BITSET_CONTAINER_SIZE_IN_WORDS / \ |
509 | | ((CROARING_WORDS_IN_AVX2_REG)*CROARING_BITSET_CONTAINER_FN_REPEAT) |
510 | | |
511 | | /* Computes a binary operation (eg union) on bitset1 and bitset2 and write the |
512 | | result to bitsetout */ |
513 | | // clang-format off |
514 | | #define CROARING_AVX_BITSET_CONTAINER_FN1(before, opname, opsymbol, avx_intrinsic, \ |
515 | | neon_intrinsic, after) \ |
516 | | static inline int _avx2_bitset_container_##opname##_nocard( \ |
517 | | const bitset_container_t *src_1, const bitset_container_t *src_2, \ |
518 | 0 | bitset_container_t *dst) { \ |
519 | 0 | const uint8_t *__restrict__ words_1 = (const uint8_t *)src_1->words; \ |
520 | 0 | const uint8_t *__restrict__ words_2 = (const uint8_t *)src_2->words; \ |
521 | 0 | /* not using the blocking optimization for some reason*/ \ |
522 | 0 | uint8_t *out = (uint8_t *)dst->words; \ |
523 | 0 | const int innerloop = 8; \ |
524 | 0 | for (size_t i = 0; \ |
525 | 0 | i < BITSET_CONTAINER_SIZE_IN_WORDS / (CROARING_WORDS_IN_AVX2_REG); \ |
526 | 0 | i += innerloop) { \ |
527 | 0 | __m256i A1, A2, AO; \ |
528 | 0 | A1 = _mm256_lddqu_si256((const __m256i *)(words_1)); \ |
529 | 0 | A2 = _mm256_lddqu_si256((const __m256i *)(words_2)); \ |
530 | 0 | AO = avx_intrinsic(A2, A1); \ |
531 | 0 | _mm256_storeu_si256((__m256i *)out, AO); \ |
532 | 0 | A1 = _mm256_lddqu_si256((const __m256i *)(words_1 + 32)); \ |
533 | 0 | A2 = _mm256_lddqu_si256((const __m256i *)(words_2 + 32)); \ |
534 | 0 | AO = avx_intrinsic(A2, A1); \ |
535 | 0 | _mm256_storeu_si256((__m256i *)(out + 32), AO); \ |
536 | 0 | A1 = _mm256_lddqu_si256((const __m256i *)(words_1 + 64)); \ |
537 | 0 | A2 = _mm256_lddqu_si256((const __m256i *)(words_2 + 64)); \ |
538 | 0 | AO = avx_intrinsic(A2, A1); \ |
539 | 0 | _mm256_storeu_si256((__m256i *)(out + 64), AO); \ |
540 | 0 | A1 = _mm256_lddqu_si256((const __m256i *)(words_1 + 96)); \ |
541 | 0 | A2 = _mm256_lddqu_si256((const __m256i *)(words_2 + 96)); \ |
542 | 0 | AO = avx_intrinsic(A2, A1); \ |
543 | 0 | _mm256_storeu_si256((__m256i *)(out + 96), AO); \ |
544 | 0 | A1 = _mm256_lddqu_si256((const __m256i *)(words_1 + 128)); \ |
545 | 0 | A2 = _mm256_lddqu_si256((const __m256i *)(words_2 + 128)); \ |
546 | 0 | AO = avx_intrinsic(A2, A1); \ |
547 | 0 | _mm256_storeu_si256((__m256i *)(out + 128), AO); \ |
548 | 0 | A1 = _mm256_lddqu_si256((const __m256i *)(words_1 + 160)); \ |
549 | 0 | A2 = _mm256_lddqu_si256((const __m256i *)(words_2 + 160)); \ |
550 | 0 | AO = avx_intrinsic(A2, A1); \ |
551 | 0 | _mm256_storeu_si256((__m256i *)(out + 160), AO); \ |
552 | 0 | A1 = _mm256_lddqu_si256((const __m256i *)(words_1 + 192)); \ |
553 | 0 | A2 = _mm256_lddqu_si256((const __m256i *)(words_2 + 192)); \ |
554 | 0 | AO = avx_intrinsic(A2, A1); \ |
555 | 0 | _mm256_storeu_si256((__m256i *)(out + 192), AO); \ |
556 | 0 | A1 = _mm256_lddqu_si256((const __m256i *)(words_1 + 224)); \ |
557 | 0 | A2 = _mm256_lddqu_si256((const __m256i *)(words_2 + 224)); \ |
558 | 0 | AO = avx_intrinsic(A2, A1); \ |
559 | 0 | _mm256_storeu_si256((__m256i *)(out + 224), AO); \ |
560 | 0 | out += 256; \ |
561 | 0 | words_1 += 256; \ |
562 | 0 | words_2 += 256; \ |
563 | 0 | } \ |
564 | 0 | dst->cardinality = BITSET_UNKNOWN_CARDINALITY; \ |
565 | 0 | return dst->cardinality; \ |
566 | 0 | } Unexecuted instantiation: bitset.c:_avx2_bitset_container_or_nocard Unexecuted instantiation: bitset.c:_avx2_bitset_container_union_nocard Unexecuted instantiation: bitset.c:_avx2_bitset_container_and_nocard Unexecuted instantiation: bitset.c:_avx2_bitset_container_intersection_nocard Unexecuted instantiation: bitset.c:_avx2_bitset_container_xor_nocard Unexecuted instantiation: bitset.c:_avx2_bitset_container_andnot_nocard |
567 | | |
568 | | #define CROARING_AVX_BITSET_CONTAINER_FN2(before, opname, opsymbol, avx_intrinsic, \ |
569 | | neon_intrinsic, after) \ |
570 | | /* next, a version that updates cardinality*/ \ |
571 | | static inline int _avx2_bitset_container_##opname(const bitset_container_t *src_1, \ |
572 | | const bitset_container_t *src_2, \ |
573 | 0 | bitset_container_t *dst) { \ |
574 | 0 | const __m256i *__restrict__ words_1 = (const __m256i *)src_1->words; \ |
575 | 0 | const __m256i *__restrict__ words_2 = (const __m256i *)src_2->words; \ |
576 | 0 | __m256i *out = (__m256i *)dst->words; \ |
577 | 0 | dst->cardinality = (int32_t)avx2_harley_seal_popcount256andstore_##opname( \ |
578 | 0 | words_2, words_1, out, \ |
579 | 0 | BITSET_CONTAINER_SIZE_IN_WORDS / (CROARING_WORDS_IN_AVX2_REG)); \ |
580 | 0 | return dst->cardinality; \ |
581 | 0 | } \ Unexecuted instantiation: bitset.c:_avx2_bitset_container_or Unexecuted instantiation: bitset.c:_avx2_bitset_container_union Unexecuted instantiation: bitset.c:_avx2_bitset_container_and Unexecuted instantiation: bitset.c:_avx2_bitset_container_intersection Unexecuted instantiation: bitset.c:_avx2_bitset_container_xor Unexecuted instantiation: bitset.c:_avx2_bitset_container_andnot |
582 | | |
583 | | #define CROARING_AVX_BITSET_CONTAINER_FN3(before, opname, opsymbol, avx_intrinsic, \ |
584 | | neon_intrinsic, after) \ |
585 | | /* next, a version that just computes the cardinality*/ \ |
586 | | static inline int _avx2_bitset_container_##opname##_justcard( \ |
587 | 0 | const bitset_container_t *src_1, const bitset_container_t *src_2) { \ |
588 | 0 | const __m256i *__restrict__ data1 = (const __m256i *)src_1->words; \ |
589 | 0 | const __m256i *__restrict__ data2 = (const __m256i *)src_2->words; \ |
590 | 0 | return (int)avx2_harley_seal_popcount256_##opname( \ |
591 | 0 | data2, data1, BITSET_CONTAINER_SIZE_IN_WORDS / (CROARING_WORDS_IN_AVX2_REG)); \ |
592 | 0 | } Unexecuted instantiation: bitset.c:_avx2_bitset_container_or_justcard Unexecuted instantiation: bitset.c:_avx2_bitset_container_union_justcard Unexecuted instantiation: bitset.c:_avx2_bitset_container_and_justcard Unexecuted instantiation: bitset.c:_avx2_bitset_container_intersection_justcard Unexecuted instantiation: bitset.c:_avx2_bitset_container_xor_justcard Unexecuted instantiation: bitset.c:_avx2_bitset_container_andnot_justcard |
593 | | |
594 | | |
595 | | // we duplicate the function because other containers use the "or" term, makes API more consistent |
596 | | CROARING_TARGET_AVX2 |
597 | | CROARING_AVX_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX2, or, |, _mm256_or_si256, vorrq_u64, CROARING_UNTARGET_AVX2) |
598 | | CROARING_UNTARGET_AVX2 |
599 | | CROARING_TARGET_AVX2 |
600 | | CROARING_AVX_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX2, union, |, _mm256_or_si256, vorrq_u64, CROARING_UNTARGET_AVX2) |
601 | | CROARING_UNTARGET_AVX2 |
602 | | |
603 | | // we duplicate the function because other containers use the "intersection" term, makes API more consistent |
604 | | CROARING_TARGET_AVX2 |
605 | | CROARING_AVX_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX2, and, &, _mm256_and_si256, vandq_u64, CROARING_UNTARGET_AVX2) |
606 | | CROARING_UNTARGET_AVX2 |
607 | | CROARING_TARGET_AVX2 |
608 | | CROARING_AVX_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX2, intersection, &, _mm256_and_si256, vandq_u64, CROARING_UNTARGET_AVX2) |
609 | | CROARING_UNTARGET_AVX2 |
610 | | |
611 | | CROARING_TARGET_AVX2 |
612 | | CROARING_AVX_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX2, xor, ^, _mm256_xor_si256, veorq_u64, CROARING_UNTARGET_AVX2) |
613 | | CROARING_UNTARGET_AVX2 |
614 | | CROARING_TARGET_AVX2 |
615 | | CROARING_AVX_BITSET_CONTAINER_FN1(CROARING_TARGET_AVX2, andnot, &~, _mm256_andnot_si256, vbicq_u64, CROARING_UNTARGET_AVX2) |
616 | | CROARING_UNTARGET_AVX2 |
617 | | |
618 | | // we duplicate the function because other containers use the "or" term, makes API more consistent |
619 | | CROARING_TARGET_AVX2 |
620 | | CROARING_AVX_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX2, or, |, _mm256_or_si256, vorrq_u64, CROARING_UNTARGET_AVX2) |
621 | | CROARING_UNTARGET_AVX2 |
622 | | CROARING_TARGET_AVX2 |
623 | | CROARING_AVX_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX2, union, |, _mm256_or_si256, vorrq_u64, CROARING_UNTARGET_AVX2) |
624 | | CROARING_UNTARGET_AVX2 |
625 | | |
626 | | // we duplicate the function because other containers use the "intersection" term, makes API more consistent |
627 | | CROARING_TARGET_AVX2 |
628 | | CROARING_AVX_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX2, and, &, _mm256_and_si256, vandq_u64, CROARING_UNTARGET_AVX2) |
629 | | CROARING_UNTARGET_AVX2 |
630 | | CROARING_TARGET_AVX2 |
631 | | CROARING_AVX_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX2, intersection, &, _mm256_and_si256, vandq_u64, CROARING_UNTARGET_AVX2) |
632 | | CROARING_UNTARGET_AVX2 |
633 | | |
634 | | CROARING_TARGET_AVX2 |
635 | | CROARING_AVX_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX2, xor, ^, _mm256_xor_si256, veorq_u64, CROARING_UNTARGET_AVX2) |
636 | | CROARING_UNTARGET_AVX2 |
637 | | CROARING_TARGET_AVX2 |
638 | | CROARING_AVX_BITSET_CONTAINER_FN2(CROARING_TARGET_AVX2, andnot, &~, _mm256_andnot_si256, vbicq_u64, CROARING_UNTARGET_AVX2) |
639 | | CROARING_UNTARGET_AVX2 |
640 | | |
641 | | // we duplicate the function because other containers use the "or" term, makes API more consistent |
642 | | CROARING_TARGET_AVX2 |
643 | | CROARING_AVX_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX2, or, |, _mm256_or_si256, vorrq_u64, CROARING_UNTARGET_AVX2) |
644 | | CROARING_UNTARGET_AVX2 |
645 | | CROARING_TARGET_AVX2 |
646 | | CROARING_AVX_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX2, union, |, _mm256_or_si256, vorrq_u64, CROARING_UNTARGET_AVX2) |
647 | | CROARING_UNTARGET_AVX2 |
648 | | |
649 | | // we duplicate the function because other containers use the "intersection" term, makes API more consistent |
650 | | CROARING_TARGET_AVX2 |
651 | | CROARING_AVX_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX2, and, &, _mm256_and_si256, vandq_u64, CROARING_UNTARGET_AVX2) |
652 | | CROARING_UNTARGET_AVX2 |
653 | | CROARING_TARGET_AVX2 |
654 | | CROARING_AVX_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX2, intersection, &, _mm256_and_si256, vandq_u64, CROARING_UNTARGET_AVX2) |
655 | | CROARING_UNTARGET_AVX2 |
656 | | |
657 | | CROARING_TARGET_AVX2 |
658 | | CROARING_AVX_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX2, xor, ^, _mm256_xor_si256, veorq_u64, CROARING_UNTARGET_AVX2) |
659 | | CROARING_UNTARGET_AVX2 |
660 | | CROARING_TARGET_AVX2 |
661 | | CROARING_AVX_BITSET_CONTAINER_FN3(CROARING_TARGET_AVX2, andnot, &~, _mm256_andnot_si256, vbicq_u64, CROARING_UNTARGET_AVX2) |
662 | | CROARING_UNTARGET_AVX2 |
663 | | |
664 | | |
665 | | #define SCALAR_BITSET_CONTAINER_FN(opname, opsymbol, avx_intrinsic, \ |
666 | | neon_intrinsic) \ |
667 | | static inline int _scalar_bitset_container_##opname(const bitset_container_t *src_1, \ |
668 | | const bitset_container_t *src_2, \ |
669 | 0 | bitset_container_t *dst) { \ |
670 | 0 | const uint64_t *__restrict__ words_1 = src_1->words; \ |
671 | 0 | const uint64_t *__restrict__ words_2 = src_2->words; \ |
672 | 0 | uint64_t *out = dst->words; \ |
673 | 0 | int32_t sum = 0; \ |
674 | 0 | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 2) { \ |
675 | 0 | const uint64_t word_1 = (words_1[i])opsymbol(words_2[i]), \ |
676 | 0 | word_2 = (words_1[i + 1]) opsymbol(words_2[i + 1]); \ |
677 | 0 | out[i] = word_1; \ |
678 | 0 | out[i + 1] = word_2; \ |
679 | 0 | sum += roaring_hamming(word_1); \ |
680 | 0 | sum += roaring_hamming(word_2); \ |
681 | 0 | } \ |
682 | 0 | dst->cardinality = sum; \ |
683 | 0 | return dst->cardinality; \ |
684 | 0 | } \ Unexecuted instantiation: bitset.c:_scalar_bitset_container_or Unexecuted instantiation: bitset.c:_scalar_bitset_container_union Unexecuted instantiation: bitset.c:_scalar_bitset_container_and Unexecuted instantiation: bitset.c:_scalar_bitset_container_intersection Unexecuted instantiation: bitset.c:_scalar_bitset_container_xor Unexecuted instantiation: bitset.c:_scalar_bitset_container_andnot |
685 | | static inline int _scalar_bitset_container_##opname##_nocard( \ |
686 | | const bitset_container_t *src_1, const bitset_container_t *src_2, \ |
687 | 0 | bitset_container_t *dst) { \ |
688 | 0 | const uint64_t *__restrict__ words_1 = src_1->words; \ |
689 | 0 | const uint64_t *__restrict__ words_2 = src_2->words; \ |
690 | 0 | uint64_t *out = dst->words; \ |
691 | 0 | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i++) { \ |
692 | 0 | out[i] = (words_1[i])opsymbol(words_2[i]); \ |
693 | 0 | } \ |
694 | 0 | dst->cardinality = BITSET_UNKNOWN_CARDINALITY; \ |
695 | 0 | return dst->cardinality; \ |
696 | 0 | } \ Unexecuted instantiation: bitset.c:_scalar_bitset_container_or_nocard Unexecuted instantiation: bitset.c:_scalar_bitset_container_union_nocard Unexecuted instantiation: bitset.c:_scalar_bitset_container_and_nocard Unexecuted instantiation: bitset.c:_scalar_bitset_container_intersection_nocard Unexecuted instantiation: bitset.c:_scalar_bitset_container_xor_nocard Unexecuted instantiation: bitset.c:_scalar_bitset_container_andnot_nocard |
697 | | static inline int _scalar_bitset_container_##opname##_justcard( \ |
698 | 0 | const bitset_container_t *src_1, const bitset_container_t *src_2) { \ |
699 | 0 | const uint64_t *__restrict__ words_1 = src_1->words; \ |
700 | 0 | const uint64_t *__restrict__ words_2 = src_2->words; \ |
701 | 0 | int32_t sum = 0; \ |
702 | 0 | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 2) { \ |
703 | 0 | const uint64_t word_1 = (words_1[i])opsymbol(words_2[i]), \ |
704 | 0 | word_2 = (words_1[i + 1]) opsymbol(words_2[i + 1]); \ |
705 | 0 | sum += roaring_hamming(word_1); \ |
706 | 0 | sum += roaring_hamming(word_2); \ |
707 | 0 | } \ |
708 | 0 | return sum; \ |
709 | 0 | } Unexecuted instantiation: bitset.c:_scalar_bitset_container_or_justcard Unexecuted instantiation: bitset.c:_scalar_bitset_container_union_justcard Unexecuted instantiation: bitset.c:_scalar_bitset_container_and_justcard Unexecuted instantiation: bitset.c:_scalar_bitset_container_intersection_justcard Unexecuted instantiation: bitset.c:_scalar_bitset_container_xor_justcard Unexecuted instantiation: bitset.c:_scalar_bitset_container_andnot_justcard |
710 | | |
711 | | // we duplicate the function because other containers use the "or" term, makes API more consistent |
712 | | SCALAR_BITSET_CONTAINER_FN(or, |, _mm256_or_si256, vorrq_u64) |
713 | | SCALAR_BITSET_CONTAINER_FN(union, |, _mm256_or_si256, vorrq_u64) |
714 | | |
715 | | // we duplicate the function because other containers use the "intersection" term, makes API more consistent |
716 | | SCALAR_BITSET_CONTAINER_FN(and, &, _mm256_and_si256, vandq_u64) |
717 | | SCALAR_BITSET_CONTAINER_FN(intersection, &, _mm256_and_si256, vandq_u64) |
718 | | |
719 | | SCALAR_BITSET_CONTAINER_FN(xor, ^, _mm256_xor_si256, veorq_u64) |
720 | | SCALAR_BITSET_CONTAINER_FN(andnot, &~, _mm256_andnot_si256, vbicq_u64) |
721 | | |
722 | | #if CROARING_COMPILER_SUPPORTS_AVX512 |
723 | | #define CROARING_BITSET_CONTAINER_FN(opname, opsymbol, avx_intrinsic, neon_intrinsic) \ |
724 | | int bitset_container_##opname(const bitset_container_t *src_1, \ |
725 | | const bitset_container_t *src_2, \ |
726 | 0 | bitset_container_t *dst) { \ |
727 | 0 | int support = croaring_hardware_support(); \ |
728 | 0 | if ( support & ROARING_SUPPORTS_AVX512 ) { \ |
729 | 0 | return _avx512_bitset_container_##opname(src_1, src_2, dst); \ |
730 | 0 | } \ |
731 | 0 | else if ( support & ROARING_SUPPORTS_AVX2 ) { \ |
732 | 0 | return _avx2_bitset_container_##opname(src_1, src_2, dst); \ |
733 | 0 | } else { \ |
734 | 0 | return _scalar_bitset_container_##opname(src_1, src_2, dst); \ |
735 | 0 | } \ |
736 | 0 | } \ Unexecuted instantiation: bitset_container_or Unexecuted instantiation: bitset_container_union Unexecuted instantiation: bitset_container_and Unexecuted instantiation: bitset_container_intersection Unexecuted instantiation: bitset_container_xor Unexecuted instantiation: bitset_container_andnot |
737 | | int bitset_container_##opname##_nocard(const bitset_container_t *src_1, \ |
738 | | const bitset_container_t *src_2, \ |
739 | 0 | bitset_container_t *dst) { \ |
740 | 0 | int support = croaring_hardware_support(); \ |
741 | 0 | if ( support & ROARING_SUPPORTS_AVX512 ) { \ |
742 | 0 | return _avx512_bitset_container_##opname##_nocard(src_1, src_2, dst); \ |
743 | 0 | } \ |
744 | 0 | else if ( support & ROARING_SUPPORTS_AVX2 ) { \ |
745 | 0 | return _avx2_bitset_container_##opname##_nocard(src_1, src_2, dst); \ |
746 | 0 | } else { \ |
747 | 0 | return _scalar_bitset_container_##opname##_nocard(src_1, src_2, dst); \ |
748 | 0 | } \ |
749 | 0 | } \ Unexecuted instantiation: bitset_container_or_nocard Unexecuted instantiation: bitset_container_union_nocard Unexecuted instantiation: bitset_container_and_nocard Unexecuted instantiation: bitset_container_intersection_nocard Unexecuted instantiation: bitset_container_xor_nocard Unexecuted instantiation: bitset_container_andnot_nocard |
750 | | int bitset_container_##opname##_justcard(const bitset_container_t *src_1, \ |
751 | 0 | const bitset_container_t *src_2) { \ |
752 | 0 | int support = croaring_hardware_support(); \ |
753 | 0 | if ( support & ROARING_SUPPORTS_AVX512 ) { \ |
754 | 0 | return _avx512_bitset_container_##opname##_justcard(src_1, src_2); \ |
755 | 0 | } \ |
756 | 0 | else if ( support & ROARING_SUPPORTS_AVX2 ) { \ |
757 | 0 | return _avx2_bitset_container_##opname##_justcard(src_1, src_2); \ |
758 | 0 | } else { \ |
759 | 0 | return _scalar_bitset_container_##opname##_justcard(src_1, src_2); \ |
760 | 0 | } \ |
761 | 0 | } Unexecuted instantiation: bitset_container_or_justcard Unexecuted instantiation: bitset_container_union_justcard Unexecuted instantiation: bitset_container_and_justcard Unexecuted instantiation: bitset_container_intersection_justcard Unexecuted instantiation: bitset_container_xor_justcard Unexecuted instantiation: bitset_container_andnot_justcard |
762 | | |
763 | | #else // CROARING_COMPILER_SUPPORTS_AVX512 |
764 | | |
765 | | |
766 | | #define CROARING_BITSET_CONTAINER_FN(opname, opsymbol, avx_intrinsic, neon_intrinsic) \ |
767 | | int bitset_container_##opname(const bitset_container_t *src_1, \ |
768 | | const bitset_container_t *src_2, \ |
769 | | bitset_container_t *dst) { \ |
770 | | if ( croaring_hardware_support() & ROARING_SUPPORTS_AVX2 ) { \ |
771 | | return _avx2_bitset_container_##opname(src_1, src_2, dst); \ |
772 | | } else { \ |
773 | | return _scalar_bitset_container_##opname(src_1, src_2, dst); \ |
774 | | } \ |
775 | | } \ |
776 | | int bitset_container_##opname##_nocard(const bitset_container_t *src_1, \ |
777 | | const bitset_container_t *src_2, \ |
778 | | bitset_container_t *dst) { \ |
779 | | if ( croaring_hardware_support() & ROARING_SUPPORTS_AVX2 ) { \ |
780 | | return _avx2_bitset_container_##opname##_nocard(src_1, src_2, dst); \ |
781 | | } else { \ |
782 | | return _scalar_bitset_container_##opname##_nocard(src_1, src_2, dst); \ |
783 | | } \ |
784 | | } \ |
785 | | int bitset_container_##opname##_justcard(const bitset_container_t *src_1, \ |
786 | | const bitset_container_t *src_2) { \ |
787 | | if ( croaring_hardware_support() & ROARING_SUPPORTS_AVX2 ) { \ |
788 | | return _avx2_bitset_container_##opname##_justcard(src_1, src_2); \ |
789 | | } else { \ |
790 | | return _scalar_bitset_container_##opname##_justcard(src_1, src_2); \ |
791 | | } \ |
792 | | } |
793 | | |
794 | | #endif // CROARING_COMPILER_SUPPORTS_AVX512 |
795 | | |
796 | | #elif defined(CROARING_USENEON) |
797 | | |
798 | | #define CROARING_BITSET_CONTAINER_FN(opname, opsymbol, avx_intrinsic, neon_intrinsic) \ |
799 | | int bitset_container_##opname(const bitset_container_t *src_1, \ |
800 | | const bitset_container_t *src_2, \ |
801 | | bitset_container_t *dst) { \ |
802 | | const uint64_t * __restrict__ words_1 = src_1->words; \ |
803 | | const uint64_t * __restrict__ words_2 = src_2->words; \ |
804 | | uint64_t *out = dst->words; \ |
805 | | uint16x8_t n0 = vdupq_n_u16(0); \ |
806 | | uint16x8_t n1 = vdupq_n_u16(0); \ |
807 | | uint16x8_t n2 = vdupq_n_u16(0); \ |
808 | | uint16x8_t n3 = vdupq_n_u16(0); \ |
809 | | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 8) { \ |
810 | | uint64x2_t c0 = neon_intrinsic(vld1q_u64(&words_1[i + 0]), \ |
811 | | vld1q_u64(&words_2[i + 0])); \ |
812 | | n0 = vaddq_u16(n0, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c0)))); \ |
813 | | vst1q_u64(&out[i + 0], c0); \ |
814 | | uint64x2_t c1 = neon_intrinsic(vld1q_u64(&words_1[i + 2]), \ |
815 | | vld1q_u64(&words_2[i + 2])); \ |
816 | | n1 = vaddq_u16(n1, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c1)))); \ |
817 | | vst1q_u64(&out[i + 2], c1); \ |
818 | | uint64x2_t c2 = neon_intrinsic(vld1q_u64(&words_1[i + 4]), \ |
819 | | vld1q_u64(&words_2[i + 4])); \ |
820 | | n2 = vaddq_u16(n2, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c2)))); \ |
821 | | vst1q_u64(&out[i + 4], c2); \ |
822 | | uint64x2_t c3 = neon_intrinsic(vld1q_u64(&words_1[i + 6]), \ |
823 | | vld1q_u64(&words_2[i + 6])); \ |
824 | | n3 = vaddq_u16(n3, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c3)))); \ |
825 | | vst1q_u64(&out[i + 6], c3); \ |
826 | | } \ |
827 | | uint64x2_t n = vdupq_n_u64(0); \ |
828 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n0))); \ |
829 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n1))); \ |
830 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n2))); \ |
831 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n3))); \ |
832 | | dst->cardinality = vgetq_lane_u64(n, 0) + vgetq_lane_u64(n, 1); \ |
833 | | return dst->cardinality; \ |
834 | | } \ |
835 | | int bitset_container_##opname##_nocard(const bitset_container_t *src_1, \ |
836 | | const bitset_container_t *src_2, \ |
837 | | bitset_container_t *dst) { \ |
838 | | const uint64_t * __restrict__ words_1 = src_1->words; \ |
839 | | const uint64_t * __restrict__ words_2 = src_2->words; \ |
840 | | uint64_t *out = dst->words; \ |
841 | | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 8) { \ |
842 | | vst1q_u64(&out[i + 0], neon_intrinsic(vld1q_u64(&words_1[i + 0]), \ |
843 | | vld1q_u64(&words_2[i + 0]))); \ |
844 | | vst1q_u64(&out[i + 2], neon_intrinsic(vld1q_u64(&words_1[i + 2]), \ |
845 | | vld1q_u64(&words_2[i + 2]))); \ |
846 | | vst1q_u64(&out[i + 4], neon_intrinsic(vld1q_u64(&words_1[i + 4]), \ |
847 | | vld1q_u64(&words_2[i + 4]))); \ |
848 | | vst1q_u64(&out[i + 6], neon_intrinsic(vld1q_u64(&words_1[i + 6]), \ |
849 | | vld1q_u64(&words_2[i + 6]))); \ |
850 | | } \ |
851 | | dst->cardinality = BITSET_UNKNOWN_CARDINALITY; \ |
852 | | return dst->cardinality; \ |
853 | | } \ |
854 | | int bitset_container_##opname##_justcard(const bitset_container_t *src_1, \ |
855 | | const bitset_container_t *src_2) { \ |
856 | | const uint64_t * __restrict__ words_1 = src_1->words; \ |
857 | | const uint64_t * __restrict__ words_2 = src_2->words; \ |
858 | | uint16x8_t n0 = vdupq_n_u16(0); \ |
859 | | uint16x8_t n1 = vdupq_n_u16(0); \ |
860 | | uint16x8_t n2 = vdupq_n_u16(0); \ |
861 | | uint16x8_t n3 = vdupq_n_u16(0); \ |
862 | | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 8) { \ |
863 | | uint64x2_t c0 = neon_intrinsic(vld1q_u64(&words_1[i + 0]), \ |
864 | | vld1q_u64(&words_2[i + 0])); \ |
865 | | n0 = vaddq_u16(n0, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c0)))); \ |
866 | | uint64x2_t c1 = neon_intrinsic(vld1q_u64(&words_1[i + 2]), \ |
867 | | vld1q_u64(&words_2[i + 2])); \ |
868 | | n1 = vaddq_u16(n1, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c1)))); \ |
869 | | uint64x2_t c2 = neon_intrinsic(vld1q_u64(&words_1[i + 4]), \ |
870 | | vld1q_u64(&words_2[i + 4])); \ |
871 | | n2 = vaddq_u16(n2, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c2)))); \ |
872 | | uint64x2_t c3 = neon_intrinsic(vld1q_u64(&words_1[i + 6]), \ |
873 | | vld1q_u64(&words_2[i + 6])); \ |
874 | | n3 = vaddq_u16(n3, vpaddlq_u8(vcntq_u8(vreinterpretq_u8_u64(c3)))); \ |
875 | | } \ |
876 | | uint64x2_t n = vdupq_n_u64(0); \ |
877 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n0))); \ |
878 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n1))); \ |
879 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n2))); \ |
880 | | n = vaddq_u64(n, vpaddlq_u32(vpaddlq_u16(n3))); \ |
881 | | return vgetq_lane_u64(n, 0) + vgetq_lane_u64(n, 1); \ |
882 | | } |
883 | | |
884 | | #else |
885 | | |
886 | | #define CROARING_BITSET_CONTAINER_FN(opname, opsymbol, avx_intrinsic, neon_intrinsic) \ |
887 | | int bitset_container_##opname(const bitset_container_t *src_1, \ |
888 | | const bitset_container_t *src_2, \ |
889 | | bitset_container_t *dst) { \ |
890 | | const uint64_t * __restrict__ words_1 = src_1->words; \ |
891 | | const uint64_t * __restrict__ words_2 = src_2->words; \ |
892 | | uint64_t *out = dst->words; \ |
893 | | int32_t sum = 0; \ |
894 | | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 2) { \ |
895 | | const uint64_t word_1 = (words_1[i])opsymbol(words_2[i]), \ |
896 | | word_2 = (words_1[i + 1])opsymbol(words_2[i + 1]); \ |
897 | | out[i] = word_1; \ |
898 | | out[i + 1] = word_2; \ |
899 | | sum += roaring_hamming(word_1); \ |
900 | | sum += roaring_hamming(word_2); \ |
901 | | } \ |
902 | | dst->cardinality = sum; \ |
903 | | return dst->cardinality; \ |
904 | | } \ |
905 | | int bitset_container_##opname##_nocard(const bitset_container_t *src_1, \ |
906 | | const bitset_container_t *src_2, \ |
907 | | bitset_container_t *dst) { \ |
908 | | const uint64_t * __restrict__ words_1 = src_1->words; \ |
909 | | const uint64_t * __restrict__ words_2 = src_2->words; \ |
910 | | uint64_t *out = dst->words; \ |
911 | | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i++) { \ |
912 | | out[i] = (words_1[i])opsymbol(words_2[i]); \ |
913 | | } \ |
914 | | dst->cardinality = BITSET_UNKNOWN_CARDINALITY; \ |
915 | | return dst->cardinality; \ |
916 | | } \ |
917 | | int bitset_container_##opname##_justcard(const bitset_container_t *src_1, \ |
918 | | const bitset_container_t *src_2) { \ |
919 | | const uint64_t * __restrict__ words_1 = src_1->words; \ |
920 | | const uint64_t * __restrict__ words_2 = src_2->words; \ |
921 | | int32_t sum = 0; \ |
922 | | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 2) { \ |
923 | | const uint64_t word_1 = (words_1[i])opsymbol(words_2[i]), \ |
924 | | word_2 = (words_1[i + 1])opsymbol(words_2[i + 1]); \ |
925 | | sum += roaring_hamming(word_1); \ |
926 | | sum += roaring_hamming(word_2); \ |
927 | | } \ |
928 | | return sum; \ |
929 | | } |
930 | | |
931 | | #endif // CROARING_IS_X64 |
932 | | |
933 | | // we duplicate the function because other containers use the "or" term, makes API more consistent |
934 | | CROARING_BITSET_CONTAINER_FN(or, |, _mm256_or_si256, vorrq_u64) |
935 | | CROARING_BITSET_CONTAINER_FN(union, |, _mm256_or_si256, vorrq_u64) |
936 | | |
937 | | // we duplicate the function because other containers use the "intersection" term, makes API more consistent |
938 | | CROARING_BITSET_CONTAINER_FN(and, &, _mm256_and_si256, vandq_u64) |
939 | | CROARING_BITSET_CONTAINER_FN(intersection, &, _mm256_and_si256, vandq_u64) |
940 | | |
941 | | CROARING_BITSET_CONTAINER_FN(xor, ^, _mm256_xor_si256, veorq_u64) |
942 | | CROARING_BITSET_CONTAINER_FN(andnot, &~, _mm256_andnot_si256, vbicq_u64) |
943 | | // clang-format On |
944 | | |
945 | | |
946 | | CROARING_ALLOW_UNALIGNED |
947 | | int bitset_container_to_uint32_array( |
948 | | uint32_t *out, |
949 | | const bitset_container_t *bc, |
950 | | uint32_t base |
951 | 0 | ){ |
952 | 0 | #if CROARING_IS_X64 |
953 | 0 | int support = croaring_hardware_support(); |
954 | 0 | #if CROARING_COMPILER_SUPPORTS_AVX512 |
955 | | // Unlike the AVX2 kernel, the AVX-512 one needs no cardinality heuristic: |
956 | | // it skips empty words and only stores the blocks that carry a value, so it |
957 | | // beat the scalar loop at every cardinality measured from 16 to 65536 (on |
958 | | // an Emerald Rapids Xeon, 1.3x at 512 values, 6x at 4096, 7.5x at 8192). |
959 | 0 | if( support & ROARING_SUPPORTS_AVX512 ) |
960 | 0 | return (int) bitset_extract_setbits_avx512(bc->words, |
961 | 0 | BITSET_CONTAINER_SIZE_IN_WORDS, out, bc->cardinality, base); |
962 | 0 | else |
963 | 0 | #endif |
964 | 0 | if(( support & ROARING_SUPPORTS_AVX2 ) && (bc->cardinality >= 8192)) // heuristic |
965 | 0 | return (int) bitset_extract_setbits_avx2(bc->words, |
966 | 0 | BITSET_CONTAINER_SIZE_IN_WORDS, out, bc->cardinality, base); |
967 | 0 | else |
968 | 0 | return (int) bitset_extract_setbits(bc->words, |
969 | 0 | BITSET_CONTAINER_SIZE_IN_WORDS, out, base); |
970 | | #else |
971 | | return (int) bitset_extract_setbits(bc->words, |
972 | | BITSET_CONTAINER_SIZE_IN_WORDS, out, base); |
973 | | #endif |
974 | 0 | } |
975 | | |
976 | | /* |
977 | | * Print this container using printf (useful for debugging). |
978 | | */ |
979 | 0 | void bitset_container_printf(const bitset_container_t * v) { |
980 | 0 | printf("{"); |
981 | 0 | uint32_t base = 0; |
982 | 0 | bool iamfirst = true;// TODO: rework so that this is not necessary yet still readable |
983 | 0 | for (int i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; ++i) { |
984 | 0 | uint64_t w = v->words[i]; |
985 | 0 | while (w != 0) { |
986 | 0 | uint64_t t = w & (~w + 1); |
987 | 0 | int r = roaring_trailing_zeroes(w); |
988 | 0 | if(iamfirst) {// predicted to be false |
989 | 0 | printf("%u",base + r); |
990 | 0 | iamfirst = false; |
991 | 0 | } else { |
992 | 0 | printf(",%u",base + r); |
993 | 0 | } |
994 | 0 | w ^= t; |
995 | 0 | } |
996 | 0 | base += 64; |
997 | 0 | } |
998 | 0 | printf("}"); |
999 | 0 | } |
1000 | | |
1001 | | |
1002 | | /* |
1003 | | * Print this container using printf as a comma-separated list of 32-bit integers starting at base. |
1004 | | */ |
1005 | 0 | void bitset_container_printf_as_uint32_array(const bitset_container_t * v, uint32_t base) { |
1006 | 0 | bool iamfirst = true;// TODO: rework so that this is not necessary yet still readable |
1007 | 0 | for (int i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; ++i) { |
1008 | 0 | uint64_t w = v->words[i]; |
1009 | 0 | while (w != 0) { |
1010 | 0 | uint64_t t = w & (~w + 1); |
1011 | 0 | int r = roaring_trailing_zeroes(w); |
1012 | 0 | if(iamfirst) {// predicted to be false |
1013 | 0 | printf("%u", r + base); |
1014 | 0 | iamfirst = false; |
1015 | 0 | } else { |
1016 | 0 | printf(",%u",r + base); |
1017 | 0 | } |
1018 | 0 | w ^= t; |
1019 | 0 | } |
1020 | 0 | base += 64; |
1021 | 0 | } |
1022 | 0 | } |
1023 | | |
1024 | | /* |
1025 | | * Validate the container. Returns true if valid. |
1026 | | */ |
1027 | 65 | bool bitset_container_validate(const bitset_container_t *v, const char **reason) { |
1028 | 65 | if (v->words == NULL) { |
1029 | 0 | *reason = "words is NULL"; |
1030 | 0 | return false; |
1031 | 0 | } |
1032 | 65 | if (v->cardinality != bitset_container_compute_cardinality(v)) { |
1033 | 33 | *reason = "cardinality is incorrect"; |
1034 | 33 | return false; |
1035 | 33 | } |
1036 | 32 | if (v->cardinality <= DEFAULT_MAX_SIZE) { |
1037 | 0 | *reason = "cardinality is too small for a bitmap container"; |
1038 | 0 | return false; |
1039 | 0 | } |
1040 | | // Attempt to forcibly load the first and last words, hopefully causing |
1041 | | // a segfault or an address sanitizer error if words is not allocated. |
1042 | 32 | volatile uint64_t *words = v->words; |
1043 | 32 | (void) words[0]; |
1044 | 32 | (void) words[BITSET_CONTAINER_SIZE_IN_WORDS - 1]; |
1045 | 32 | return true; |
1046 | 32 | } |
1047 | | |
1048 | | |
1049 | | // TODO: use the fast lower bound, also |
1050 | 0 | int bitset_container_number_of_runs(bitset_container_t *bc) { |
1051 | 0 | int num_runs = 0; |
1052 | 0 | uint64_t next_word = bc->words[0]; |
1053 | |
|
1054 | 0 | for (int i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS-1; ++i) { |
1055 | 0 | uint64_t word = next_word; |
1056 | 0 | next_word = bc->words[i+1]; |
1057 | 0 | num_runs += roaring_hamming((~word) & (word << 1)) + ( (word >> 63) & ~next_word); |
1058 | 0 | } |
1059 | |
|
1060 | 0 | uint64_t word = next_word; |
1061 | 0 | num_runs += roaring_hamming((~word) & (word << 1)); |
1062 | 0 | if((word & 0x8000000000000000ULL) != 0) |
1063 | 0 | num_runs++; |
1064 | 0 | return num_runs; |
1065 | 0 | } |
1066 | | |
1067 | | |
1068 | | int32_t bitset_container_write(const bitset_container_t *container, |
1069 | 0 | char *buf) { |
1070 | | #if CROARING_IS_BIG_ENDIAN |
1071 | | for (int32_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; ++i) { |
1072 | | uint64_t w_le = croaring_htole64(container->words[i]); |
1073 | | memcpy(buf + i * sizeof(uint64_t), &w_le, sizeof(uint64_t)); |
1074 | | } |
1075 | | #else |
1076 | 0 | memcpy(buf, container->words, BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t)); |
1077 | 0 | #endif |
1078 | 0 | return bitset_container_size_in_bytes(container); |
1079 | 0 | } |
1080 | | |
1081 | | |
1082 | | int32_t bitset_container_read(int32_t cardinality, bitset_container_t *container, |
1083 | 954 | const char *buf) { |
1084 | 954 | container->cardinality = cardinality; |
1085 | | #if CROARING_IS_BIG_ENDIAN |
1086 | | for (int32_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; ++i) { |
1087 | | uint64_t w_le; |
1088 | | memcpy(&w_le, buf + i * sizeof(uint64_t), sizeof(uint64_t)); |
1089 | | container->words[i] = croaring_letoh64(w_le); |
1090 | | } |
1091 | | #else |
1092 | 954 | memcpy(container->words, buf, BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t)); |
1093 | 954 | #endif |
1094 | 954 | return bitset_container_size_in_bytes(container); |
1095 | 954 | } |
1096 | | |
1097 | 0 | bool bitset_container_iterate(const bitset_container_t *cont, uint32_t base, roaring_iterator iterator, void *ptr) { |
1098 | 0 | for (int32_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; ++i ) { |
1099 | 0 | uint64_t w = cont->words[i]; |
1100 | 0 | while (w != 0) { |
1101 | 0 | uint64_t t = w & (~w + 1); |
1102 | 0 | int r = roaring_trailing_zeroes(w); |
1103 | 0 | if(!iterator(r + base, ptr)) return false; |
1104 | 0 | w ^= t; |
1105 | 0 | } |
1106 | 0 | base += 64; |
1107 | 0 | } |
1108 | 0 | return true; |
1109 | 0 | } |
1110 | | |
1111 | 0 | bool bitset_container_iterate64(const bitset_container_t *cont, uint32_t base, roaring_iterator64 iterator, uint64_t high_bits, void *ptr) { |
1112 | 0 | for (int32_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; ++i ) { |
1113 | 0 | uint64_t w = cont->words[i]; |
1114 | 0 | while (w != 0) { |
1115 | 0 | uint64_t t = w & (~w + 1); |
1116 | 0 | int r = roaring_trailing_zeroes(w); |
1117 | 0 | if(!iterator(high_bits | (uint64_t)(r + base), ptr)) return false; |
1118 | 0 | w ^= t; |
1119 | 0 | } |
1120 | 0 | base += 64; |
1121 | 0 | } |
1122 | 0 | return true; |
1123 | 0 | } |
1124 | | |
1125 | | #if CROARING_IS_X64 |
1126 | | #if CROARING_COMPILER_SUPPORTS_AVX512 |
1127 | | CROARING_TARGET_AVX512 |
1128 | | CROARING_ALLOW_UNALIGNED |
1129 | 0 | static inline bool _avx512_bitset_container_equals(const bitset_container_t *container1, const bitset_container_t *container2) { |
1130 | 0 | const __m512i *ptr1 = (const __m512i*)container1->words; |
1131 | 0 | const __m512i *ptr2 = (const __m512i*)container2->words; |
1132 | 0 | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS*sizeof(uint64_t)/64; i++) { |
1133 | 0 | __m512i r1 = _mm512_loadu_si512(ptr1+i); |
1134 | 0 | __m512i r2 = _mm512_loadu_si512(ptr2+i); |
1135 | 0 | __mmask64 mask = _mm512_cmpeq_epi8_mask(r1, r2); |
1136 | 0 | if ((uint64_t)mask != UINT64_MAX) { |
1137 | 0 | return false; |
1138 | 0 | } |
1139 | 0 | } |
1140 | 0 | return true; |
1141 | 0 | } |
1142 | | CROARING_UNTARGET_AVX512 |
1143 | | #endif // CROARING_COMPILER_SUPPORTS_AVX512 |
1144 | | CROARING_TARGET_AVX2 |
1145 | | CROARING_ALLOW_UNALIGNED |
1146 | 0 | static inline bool _avx2_bitset_container_equals(const bitset_container_t *container1, const bitset_container_t *container2) { |
1147 | 0 | const __m256i *ptr1 = (const __m256i*)container1->words; |
1148 | 0 | const __m256i *ptr2 = (const __m256i*)container2->words; |
1149 | 0 | for (size_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS*sizeof(uint64_t)/32; i++) { |
1150 | 0 | __m256i r1 = _mm256_loadu_si256(ptr1+i); |
1151 | 0 | __m256i r2 = _mm256_loadu_si256(ptr2+i); |
1152 | 0 | int mask = _mm256_movemask_epi8(_mm256_cmpeq_epi8(r1, r2)); |
1153 | 0 | if ((uint32_t)mask != UINT32_MAX) { |
1154 | 0 | return false; |
1155 | 0 | } |
1156 | 0 | } |
1157 | 0 | return true; |
1158 | 0 | } |
1159 | | CROARING_UNTARGET_AVX2 |
1160 | | #endif // CROARING_IS_X64 |
1161 | | |
1162 | | CROARING_ALLOW_UNALIGNED |
1163 | 0 | bool bitset_container_equals(const bitset_container_t *container1, const bitset_container_t *container2) { |
1164 | 0 | if((container1->cardinality != BITSET_UNKNOWN_CARDINALITY) && (container2->cardinality != BITSET_UNKNOWN_CARDINALITY)) { |
1165 | 0 | if(container1->cardinality != container2->cardinality) { |
1166 | 0 | return false; |
1167 | 0 | } |
1168 | 0 | if (container1->cardinality == INT32_C(0x10000)) { |
1169 | 0 | return true; |
1170 | 0 | } |
1171 | 0 | } |
1172 | 0 | #if CROARING_IS_X64 |
1173 | 0 | int support = croaring_hardware_support(); |
1174 | 0 | #if CROARING_COMPILER_SUPPORTS_AVX512 |
1175 | 0 | if( support & ROARING_SUPPORTS_AVX512 ) { |
1176 | 0 | return _avx512_bitset_container_equals(container1, container2); |
1177 | 0 | } |
1178 | 0 | else |
1179 | 0 | #endif |
1180 | 0 | if( support & ROARING_SUPPORTS_AVX2 ) { |
1181 | 0 | return _avx2_bitset_container_equals(container1, container2); |
1182 | 0 | } |
1183 | 0 | #endif |
1184 | 0 | return memcmp(container1->words, |
1185 | 0 | container2->words, |
1186 | 0 | BITSET_CONTAINER_SIZE_IN_WORDS*sizeof(uint64_t)) == 0; |
1187 | 0 | } |
1188 | | |
1189 | | bool bitset_container_is_subset(const bitset_container_t *container1, |
1190 | 0 | const bitset_container_t *container2) { |
1191 | 0 | if((container1->cardinality != BITSET_UNKNOWN_CARDINALITY) && (container2->cardinality != BITSET_UNKNOWN_CARDINALITY)) { |
1192 | 0 | if(container1->cardinality > container2->cardinality) { |
1193 | 0 | return false; |
1194 | 0 | } |
1195 | 0 | } |
1196 | 0 | for(int32_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; ++i ) { |
1197 | 0 | if((container1->words[i] & container2->words[i]) != container1->words[i]) { |
1198 | 0 | return false; |
1199 | 0 | } |
1200 | 0 | } |
1201 | 0 | return true; |
1202 | 0 | } |
1203 | | |
1204 | 0 | bool bitset_container_select(const bitset_container_t *container, uint32_t *start_rank, uint32_t rank, uint32_t *element) { |
1205 | 0 | int card = bitset_container_cardinality(container); |
1206 | 0 | if(rank >= *start_rank + card) { |
1207 | 0 | *start_rank += card; |
1208 | 0 | return false; |
1209 | 0 | } |
1210 | 0 | const uint64_t *words = container->words; |
1211 | 0 | int32_t size; |
1212 | 0 | for (int i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i += 1) { |
1213 | 0 | size = roaring_hamming(words[i]); |
1214 | 0 | if(rank <= *start_rank + size) { |
1215 | 0 | uint64_t w = container->words[i]; |
1216 | 0 | uint16_t base = i*64; |
1217 | 0 | while (w != 0) { |
1218 | 0 | uint64_t t = w & (~w + 1); |
1219 | 0 | int r = roaring_trailing_zeroes(w); |
1220 | 0 | if(*start_rank == rank) { |
1221 | 0 | *element = r+base; |
1222 | 0 | return true; |
1223 | 0 | } |
1224 | 0 | w ^= t; |
1225 | 0 | *start_rank += 1; |
1226 | 0 | } |
1227 | 0 | } |
1228 | 0 | else |
1229 | 0 | *start_rank += size; |
1230 | 0 | } |
1231 | 0 | assert(false); |
1232 | 0 | roaring_unreachable; |
1233 | 0 | } |
1234 | | |
1235 | | |
1236 | | /* Returns the smallest value (assumes not empty) */ |
1237 | 0 | uint16_t bitset_container_minimum(const bitset_container_t *container) { |
1238 | 0 | for (int32_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; ++i ) { |
1239 | 0 | uint64_t w = container->words[i]; |
1240 | 0 | if (w != 0) { |
1241 | 0 | int r = roaring_trailing_zeroes(w); |
1242 | 0 | return r + i * 64; |
1243 | 0 | } |
1244 | 0 | } |
1245 | 0 | return UINT16_MAX; |
1246 | 0 | } |
1247 | | |
1248 | | /* Returns the largest value (assumes not empty) */ |
1249 | 0 | uint16_t bitset_container_maximum(const bitset_container_t *container) { |
1250 | 0 | for (int32_t i = BITSET_CONTAINER_SIZE_IN_WORDS - 1; i > 0; --i ) { |
1251 | 0 | uint64_t w = container->words[i]; |
1252 | 0 | if (w != 0) { |
1253 | 0 | int r = roaring_leading_zeroes(w); |
1254 | 0 | return i * 64 + 63 - r; |
1255 | 0 | } |
1256 | 0 | } |
1257 | 0 | return 0; |
1258 | 0 | } |
1259 | | |
1260 | | /* Returns the number of values equal or smaller than x */ |
1261 | 0 | int bitset_container_rank(const bitset_container_t *container, uint16_t x) { |
1262 | | // credit: aqrit |
1263 | 0 | int sum = 0; |
1264 | 0 | int i = 0; |
1265 | 0 | for (int end = x / 64; i < end; i++){ |
1266 | 0 | sum += roaring_hamming(container->words[i]); |
1267 | 0 | } |
1268 | 0 | uint64_t lastword = container->words[i]; |
1269 | 0 | uint64_t lastpos = UINT64_C(1) << (x % 64); |
1270 | 0 | uint64_t mask = lastpos + lastpos - 1; // smear right |
1271 | 0 | sum += roaring_hamming(lastword & mask); |
1272 | 0 | return sum; |
1273 | 0 | } |
1274 | | |
1275 | 0 | uint32_t bitset_container_rank_many(const bitset_container_t *container, uint64_t start_rank, const uint32_t* begin, const uint32_t* end, uint64_t* ans){ |
1276 | 0 | const uint16_t high = (uint16_t)((*begin) >> 16); |
1277 | 0 | int i = 0; |
1278 | 0 | int sum = 0; |
1279 | 0 | const uint32_t* iter = begin; |
1280 | 0 | for(; iter != end; iter++) { |
1281 | 0 | uint32_t x = *iter; |
1282 | 0 | uint16_t xhigh = (uint16_t)(x >> 16); |
1283 | 0 | if(xhigh != high) return iter - begin; // stop at next container |
1284 | | |
1285 | 0 | uint16_t xlow = (uint16_t)x; |
1286 | 0 | for(int count = xlow / 64; i < count; i++){ |
1287 | 0 | sum += roaring_hamming(container->words[i]); |
1288 | 0 | } |
1289 | 0 | uint64_t lastword = container->words[i]; |
1290 | 0 | uint64_t lastpos = UINT64_C(1) << (xlow % 64); |
1291 | 0 | uint64_t mask = lastpos + lastpos - 1; // smear right |
1292 | 0 | *(ans++) = start_rank + sum + roaring_hamming(lastword & mask); |
1293 | 0 | } |
1294 | 0 | return iter - begin; |
1295 | 0 | } |
1296 | | |
1297 | | |
1298 | | /* Returns the index of x , if not exsist return -1 */ |
1299 | 0 | int bitset_container_get_index(const bitset_container_t *container, uint16_t x) { |
1300 | 0 | if (bitset_container_get(container, x)) { |
1301 | | // credit: aqrit |
1302 | 0 | int sum = 0; |
1303 | 0 | int i = 0; |
1304 | 0 | for (int end = x / 64; i < end; i++){ |
1305 | 0 | sum += roaring_hamming(container->words[i]); |
1306 | 0 | } |
1307 | 0 | uint64_t lastword = container->words[i]; |
1308 | 0 | uint64_t lastpos = UINT64_C(1) << (x % 64); |
1309 | 0 | uint64_t mask = lastpos + lastpos - 1; // smear right |
1310 | 0 | sum += roaring_hamming(lastword & mask); |
1311 | 0 | return sum - 1; |
1312 | 0 | } else { |
1313 | 0 | return -1; |
1314 | 0 | } |
1315 | 0 | } |
1316 | | |
1317 | | /* Returns the index of the first value equal or larger than x, or -1 */ |
1318 | 0 | int bitset_container_index_equalorlarger(const bitset_container_t *container, uint16_t x) { |
1319 | 0 | uint32_t x32 = x; |
1320 | 0 | uint32_t k = x32 / 64; |
1321 | 0 | uint64_t word = container->words[k]; |
1322 | 0 | const int diff = x32 - k * 64; // in [0,64) |
1323 | 0 | word = (word >> diff) << diff; // a mask is faster, but we don't care |
1324 | 0 | while(word == 0) { |
1325 | 0 | k++; |
1326 | 0 | if(k == BITSET_CONTAINER_SIZE_IN_WORDS) return -1; |
1327 | 0 | word = container->words[k]; |
1328 | 0 | } |
1329 | 0 | return k * 64 + roaring_trailing_zeroes(word); |
1330 | 0 | } |
1331 | | |
1332 | | #ifdef __cplusplus |
1333 | | } } } // extern "C" { namespace roaring { namespace internal { |
1334 | | #endif |
1335 | | #if defined(__GNUC__) && !defined(__clang__) |
1336 | | #pragma GCC diagnostic pop |
1337 | | #endif |