competitive/data_structure/
simd.rs

1#![allow(unsafe_op_in_unsafe_fn)] // SIMD intrinsics are confined to feature-gated functions.
2
3#[cfg(target_arch = "x86_64")]
4use std::arch::x86_64::*;
5
6#[cfg(target_arch = "x86_64")]
7#[target_feature(enable = "avx2")]
8#[inline]
9pub unsafe fn first_ge_u16x32_avx2(values: &[u16; 32], key: u16) -> usize {
10    let sign = _mm256_set1_epi16(i16::MIN);
11    let key = _mm256_xor_si256(_mm256_set1_epi16(key as i16), sign);
12    let low = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().cast()), sign);
13    let high = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().add(16).cast()), sign);
14    let low = _mm256_movemask_epi8(_mm256_cmpgt_epi16(key, low)) as u32 as u64;
15    let high = _mm256_movemask_epi8(_mm256_cmpgt_epi16(key, high)) as u32 as u64;
16    (!(low | high << 32)).trailing_zeros() as usize / 2
17}
18
19#[cfg(target_arch = "x86_64")]
20#[target_feature(enable = "avx2")]
21#[inline]
22pub unsafe fn first_gt_u16x32_avx2(values: &[u16; 32], key: u16) -> usize {
23    let sign = _mm256_set1_epi16(i16::MIN);
24    let key = _mm256_xor_si256(_mm256_set1_epi16(key as i16), sign);
25    let low = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().cast()), sign);
26    let high = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().add(16).cast()), sign);
27    let low = _mm256_movemask_epi8(_mm256_cmpgt_epi16(low, key)) as u32 as u64;
28    let high = _mm256_movemask_epi8(_mm256_cmpgt_epi16(high, key)) as u32 as u64;
29    (low | high << 32).trailing_zeros() as usize / 2
30}
31
32#[cfg(target_arch = "x86_64")]
33#[target_feature(enable = "avx2")]
34#[inline]
35pub unsafe fn first_ge_u32x16_avx2(values: &[u32; 16], key: u32) -> usize {
36    let sign = _mm256_set1_epi32(i32::MIN);
37    let key = _mm256_xor_si256(_mm256_set1_epi32(key as i32), sign);
38    let low = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().cast()), sign);
39    let high = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().add(8).cast()), sign);
40    let low = _mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(key, low)));
41    let high = _mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(key, high)));
42    let mask = ((!low as u32) & 0xff) | (((!high as u32) & 0xff) << 8);
43    (mask as u16).trailing_zeros() as usize
44}
45
46#[cfg(target_arch = "x86_64")]
47#[target_feature(enable = "avx2")]
48#[inline]
49pub unsafe fn first_gt_u32x16_avx2(values: &[u32; 16], key: u32) -> usize {
50    let sign = _mm256_set1_epi32(i32::MIN);
51    let key = _mm256_xor_si256(_mm256_set1_epi32(key as i32), sign);
52    let low = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().cast()), sign);
53    let high = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().add(8).cast()), sign);
54    let low = _mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(low, key)));
55    let high = _mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(high, key)));
56    let mask = low as u32 | ((high as u32) << 8);
57    (mask as u16).trailing_zeros() as usize
58}
59
60#[cfg(target_arch = "x86_64")]
61#[target_feature(enable = "avx2")]
62#[inline]
63pub unsafe fn first_ge_u64x8_avx2(values: &[u64; 8], key: u64) -> usize {
64    let sign = _mm256_set1_epi64x(i64::MIN);
65    let key = _mm256_xor_si256(_mm256_set1_epi64x(key as i64), sign);
66    let low = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().cast()), sign);
67    let high = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().add(4).cast()), sign);
68    let low = _mm256_movemask_pd(_mm256_castsi256_pd(_mm256_cmpgt_epi64(key, low)));
69    let high = _mm256_movemask_pd(_mm256_castsi256_pd(_mm256_cmpgt_epi64(key, high)));
70    let mask = ((!low as u32) & 0x0f) | (((!high as u32) & 0x0f) << 4);
71    (mask as u8).trailing_zeros() as usize
72}
73
74#[cfg(target_arch = "x86_64")]
75#[target_feature(enable = "avx2")]
76#[inline]
77pub unsafe fn first_gt_u64x8_avx2(values: &[u64; 8], key: u64) -> usize {
78    let sign = _mm256_set1_epi64x(i64::MIN);
79    let key = _mm256_xor_si256(_mm256_set1_epi64x(key as i64), sign);
80    let low = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().cast()), sign);
81    let high = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().add(4).cast()), sign);
82    let low = _mm256_movemask_pd(_mm256_castsi256_pd(_mm256_cmpgt_epi64(low, key)));
83    let high = _mm256_movemask_pd(_mm256_castsi256_pd(_mm256_cmpgt_epi64(high, key)));
84    let mask = low as u32 | ((high as u32) << 4);
85    (mask as u8).trailing_zeros() as usize
86}
87
88#[cfg(target_arch = "x86_64")]
89#[target_feature(enable = "avx512f,avx512bw")]
90#[inline]
91pub unsafe fn first_ge_u16x32_avx512(values: &[u16; 32], key: u16) -> usize {
92    let values = _mm512_loadu_si512(values.as_ptr().cast());
93    let key = _mm512_set1_epi16(key as i16);
94    (!_mm512_cmplt_epu16_mask(values, key)).trailing_zeros() as usize
95}
96
97#[cfg(target_arch = "x86_64")]
98#[target_feature(enable = "avx512f,avx512bw")]
99#[inline]
100pub unsafe fn first_gt_u16x32_avx512(values: &[u16; 32], key: u16) -> usize {
101    let values = _mm512_loadu_si512(values.as_ptr().cast());
102    let key = _mm512_set1_epi16(key as i16);
103    _mm512_cmpgt_epu16_mask(values, key).trailing_zeros() as usize
104}
105
106#[cfg(target_arch = "x86_64")]
107#[target_feature(enable = "avx512f")]
108#[inline]
109pub unsafe fn first_ge_u32x16_avx512(values: &[u32; 16], key: u32) -> usize {
110    let values = _mm512_loadu_si512(values.as_ptr().cast());
111    let key = _mm512_set1_epi32(key as i32);
112    (!_mm512_cmplt_epu32_mask(values, key)).trailing_zeros() as usize
113}
114
115#[cfg(target_arch = "x86_64")]
116#[target_feature(enable = "avx512f")]
117#[inline]
118pub unsafe fn first_gt_u32x16_avx512(values: &[u32; 16], key: u32) -> usize {
119    let values = _mm512_loadu_si512(values.as_ptr().cast());
120    let key = _mm512_set1_epi32(key as i32);
121    _mm512_cmpgt_epu32_mask(values, key).trailing_zeros() as usize
122}
123
124#[cfg(target_arch = "x86_64")]
125#[target_feature(enable = "avx512f")]
126#[inline]
127pub unsafe fn first_ge_u64x8_avx512(values: &[u64; 8], key: u64) -> usize {
128    let values = _mm512_loadu_si512(values.as_ptr().cast());
129    let key = _mm512_set1_epi64(key as i64);
130    (!_mm512_cmplt_epu64_mask(values, key)).trailing_zeros() as usize
131}
132
133#[cfg(target_arch = "x86_64")]
134#[target_feature(enable = "avx512f")]
135#[inline]
136pub unsafe fn first_gt_u64x8_avx512(values: &[u64; 8], key: u64) -> usize {
137    let values = _mm512_loadu_si512(values.as_ptr().cast());
138    let key = _mm512_set1_epi64(key as i64);
139    _mm512_cmpgt_epu64_mask(values, key).trailing_zeros() as usize
140}
141
142#[cfg(target_arch = "x86_64")]
143#[target_feature(enable = "avx2")]
144#[inline]
145pub unsafe fn add_suffix_u32x16_avx2(values: &mut [u32; 16], index: usize, delta: u32) {
146    let index = _mm256_set1_epi32(index as i32 - 1);
147    let delta = _mm256_set1_epi32(delta as i32);
148    let low_mask = _mm256_cmpgt_epi32(_mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7), index);
149    let high_mask = _mm256_cmpgt_epi32(_mm256_setr_epi32(8, 9, 10, 11, 12, 13, 14, 15), index);
150    let low = _mm256_add_epi32(
151        _mm256_loadu_si256(values.as_ptr().cast()),
152        _mm256_and_si256(delta, low_mask),
153    );
154    let high = _mm256_add_epi32(
155        _mm256_loadu_si256(values.as_ptr().add(8).cast()),
156        _mm256_and_si256(delta, high_mask),
157    );
158    _mm256_storeu_si256(values.as_mut_ptr().cast(), low);
159    _mm256_storeu_si256(values.as_mut_ptr().add(8).cast(), high);
160}
161
162#[cfg(target_arch = "x86_64")]
163#[target_feature(enable = "avx2")]
164#[inline]
165pub unsafe fn add_suffix_u64x8_avx2(values: &mut [u64; 8], index: usize, delta: u64) {
166    let index = _mm256_set1_epi64x(index as i64 - 1);
167    let delta = _mm256_set1_epi64x(delta as i64);
168    let low_mask = _mm256_cmpgt_epi64(_mm256_setr_epi64x(0, 1, 2, 3), index);
169    let high_mask = _mm256_cmpgt_epi64(_mm256_setr_epi64x(4, 5, 6, 7), index);
170    let low = _mm256_add_epi64(
171        _mm256_loadu_si256(values.as_ptr().cast()),
172        _mm256_and_si256(delta, low_mask),
173    );
174    let high = _mm256_add_epi64(
175        _mm256_loadu_si256(values.as_ptr().add(4).cast()),
176        _mm256_and_si256(delta, high_mask),
177    );
178    _mm256_storeu_si256(values.as_mut_ptr().cast(), low);
179    _mm256_storeu_si256(values.as_mut_ptr().add(4).cast(), high);
180}
181
182#[cfg(target_arch = "x86_64")]
183#[target_feature(enable = "avx512f")]
184#[inline]
185pub unsafe fn add_suffix_u32x16_avx512(values: &mut [u32; 16], index: usize, delta: u32) {
186    let values_vector = _mm512_loadu_si512(values.as_ptr().cast());
187    let values_vector = _mm512_mask_add_epi32(
188        values_vector,
189        u16::MAX << index,
190        values_vector,
191        _mm512_set1_epi32(delta as i32),
192    );
193    _mm512_storeu_si512(values.as_mut_ptr().cast(), values_vector);
194}
195
196#[cfg(target_arch = "x86_64")]
197#[target_feature(enable = "avx512f")]
198#[inline]
199pub unsafe fn add_suffix_u64x8_avx512(values: &mut [u64; 8], index: usize, delta: u64) {
200    let values_vector = _mm512_loadu_si512(values.as_ptr().cast());
201    let values_vector = _mm512_mask_add_epi64(
202        values_vector,
203        u8::MAX << index,
204        values_vector,
205        _mm512_set1_epi64(delta as i64),
206    );
207    _mm512_storeu_si512(values.as_mut_ptr().cast(), values_vector);
208}
209
210#[cfg(target_arch = "x86_64")]
211#[target_feature(enable = "avx2")]
212#[inline]
213pub unsafe fn max_index_u32x16_avx2(values: &[u32; 16]) -> usize {
214    let low = _mm256_loadu_si256(values.as_ptr().cast());
215    let high = _mm256_loadu_si256(values.as_ptr().add(8).cast());
216    let mut maximum = _mm256_max_epu32(low, high);
217    maximum = _mm256_max_epu32(maximum, _mm256_permute2x128_si256::<0x01>(maximum, maximum));
218    maximum = _mm256_max_epu32(maximum, _mm256_shuffle_epi32::<0x4e>(maximum));
219    maximum = _mm256_max_epu32(maximum, _mm256_shuffle_epi32::<0xb1>(maximum));
220    let maximum = _mm256_set1_epi32(_mm256_extract_epi32::<0>(maximum));
221    let low = _mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpeq_epi32(low, maximum)));
222    let high = _mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpeq_epi32(high, maximum)));
223    ((low as u32 | ((high as u32) << 8)) as u16).trailing_zeros() as usize
224}
225
226#[cfg(target_arch = "x86_64")]
227#[target_feature(enable = "avx512f")]
228#[inline]
229pub unsafe fn max_index_u32x16_avx512(values: &[u32; 16]) -> usize {
230    let values = _mm512_loadu_si512(values.as_ptr().cast());
231    let maximum = _mm512_set1_epi32(_mm512_reduce_max_epu32(values) as i32);
232    _mm512_cmpeq_epi32_mask(values, maximum).trailing_zeros() as usize
233}
234
235#[cfg(target_arch = "x86_64")]
236#[target_feature(enable = "avx2")]
237#[inline]
238unsafe fn max_epu64(left: __m256i, right: __m256i) -> __m256i {
239    let sign = _mm256_set1_epi64x(i64::MIN);
240    let greater = _mm256_cmpgt_epi64(_mm256_xor_si256(left, sign), _mm256_xor_si256(right, sign));
241    _mm256_blendv_epi8(right, left, greater)
242}
243
244#[cfg(target_arch = "x86_64")]
245#[target_feature(enable = "avx2")]
246#[inline]
247pub unsafe fn max_index_u64x8_avx2(values: &[u64; 8]) -> usize {
248    let sign = _mm256_set1_epi64x(i64::MIN);
249    let low = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().cast()), sign);
250    let high = _mm256_xor_si256(_mm256_loadu_si256(values.as_ptr().add(4).cast()), sign);
251    let mut maximum = max_i64x4(low, high);
252    maximum = max_i64x4(maximum, _mm256_permute4x64_epi64::<0x4e>(maximum));
253    maximum = max_i64x4(maximum, _mm256_permute4x64_epi64::<0xb1>(maximum));
254    let low = _mm256_movemask_pd(_mm256_castsi256_pd(_mm256_cmpeq_epi64(low, maximum)));
255    let high = _mm256_movemask_pd(_mm256_castsi256_pd(_mm256_cmpeq_epi64(high, maximum)));
256    ((low as u32 | ((high as u32) << 4)) as u8).trailing_zeros() as usize
257}
258
259#[cfg(target_arch = "x86_64")]
260#[target_feature(enable = "avx512f")]
261#[inline]
262pub unsafe fn max_index_u64x8_avx512(values: &[u64; 8]) -> usize {
263    let values = _mm512_loadu_si512(values.as_ptr().cast());
264    let maximum = _mm512_set1_epi64(_mm512_reduce_max_epu64(values) as i64);
265    _mm512_cmpeq_epi64_mask(values, maximum).trailing_zeros() as usize
266}
267
268#[cfg(target_arch = "x86_64")]
269#[target_feature(enable = "avx2")]
270#[inline]
271pub unsafe fn max_index_u128x4_avx2(low: &[u64; 4], high: &[u64; 4]) -> usize {
272    let low = _mm256_loadu_si256(low.as_ptr().cast());
273    let high = _mm256_loadu_si256(high.as_ptr().cast());
274    let mut maximum_high = high;
275    maximum_high = max_epu64(maximum_high, _mm256_permute4x64_epi64::<0x4e>(maximum_high));
276    maximum_high = max_epu64(maximum_high, _mm256_permute4x64_epi64::<0xb1>(maximum_high));
277    let high_equal = _mm256_cmpeq_epi64(high, maximum_high);
278    let high_mask = _mm256_movemask_pd(_mm256_castsi256_pd(high_equal)) as u32 & 15;
279    if high_mask.is_power_of_two() {
280        return high_mask.trailing_zeros() as usize;
281    }
282    let mut maximum_low = _mm256_and_si256(low, high_equal);
283    maximum_low = max_epu64(maximum_low, _mm256_permute4x64_epi64::<0x4e>(maximum_low));
284    maximum_low = max_epu64(maximum_low, _mm256_permute4x64_epi64::<0xb1>(maximum_low));
285    let both = _mm256_and_si256(high_equal, _mm256_cmpeq_epi64(low, maximum_low));
286    (_mm256_movemask_pd(_mm256_castsi256_pd(both)) as u32 & 15).trailing_zeros() as usize
287}
288
289#[cfg(target_arch = "x86_64")]
290#[target_feature(enable = "avx2,avx512f,avx512vl")]
291#[inline]
292pub unsafe fn max_index_u128x4_avx512(low: &[u64; 4], high: &[u64; 4]) -> usize {
293    let low = _mm256_loadu_si256(low.as_ptr().cast());
294    let high = _mm256_loadu_si256(high.as_ptr().cast());
295    let mut maximum_high = high;
296    maximum_high = _mm256_max_epu64(maximum_high, _mm256_permute4x64_epi64::<0x4e>(maximum_high));
297    maximum_high = _mm256_max_epu64(maximum_high, _mm256_permute4x64_epi64::<0xb1>(maximum_high));
298    let high_equal = _mm256_cmpeq_epi64(high, maximum_high);
299    let high_mask = _mm256_movemask_pd(_mm256_castsi256_pd(high_equal)) as u32 & 15;
300    if high_mask.is_power_of_two() {
301        return high_mask.trailing_zeros() as usize;
302    }
303    let mut maximum_low = _mm256_and_si256(low, high_equal);
304    maximum_low = _mm256_max_epu64(maximum_low, _mm256_permute4x64_epi64::<0x4e>(maximum_low));
305    maximum_low = _mm256_max_epu64(maximum_low, _mm256_permute4x64_epi64::<0xb1>(maximum_low));
306    let both = _mm256_and_si256(high_equal, _mm256_cmpeq_epi64(low, maximum_low));
307    (_mm256_movemask_pd(_mm256_castsi256_pd(both)) as u32 & 15).trailing_zeros() as usize
308}
309
310#[cfg(target_arch = "x86_64")]
311#[target_feature(enable = "avx2")]
312#[inline]
313unsafe fn reduce_min_i32x8(mut values: __m256i) -> i32 {
314    values = _mm256_min_epi32(values, _mm256_permute2x128_si256::<0x01>(values, values));
315    values = _mm256_min_epi32(values, _mm256_shuffle_epi32::<0x4e>(values));
316    values = _mm256_min_epi32(values, _mm256_shuffle_epi32::<0xb1>(values));
317    _mm256_extract_epi32::<0>(values)
318}
319
320#[cfg(target_arch = "x86_64")]
321#[target_feature(enable = "avx2")]
322#[inline]
323unsafe fn reduce_max_i32x8(mut values: __m256i) -> i32 {
324    values = _mm256_max_epi32(values, _mm256_permute2x128_si256::<0x01>(values, values));
325    values = _mm256_max_epi32(values, _mm256_shuffle_epi32::<0x4e>(values));
326    values = _mm256_max_epi32(values, _mm256_shuffle_epi32::<0xb1>(values));
327    _mm256_extract_epi32::<0>(values)
328}
329
330#[cfg(target_arch = "x86_64")]
331#[target_feature(enable = "avx2")]
332#[inline]
333unsafe fn reduce_sum_i32x8(mut values: __m256i) -> i32 {
334    values = _mm256_add_epi32(values, _mm256_permute2x128_si256::<0x01>(values, values));
335    values = _mm256_add_epi32(values, _mm256_shuffle_epi32::<0x4e>(values));
336    values = _mm256_add_epi32(values, _mm256_shuffle_epi32::<0xb1>(values));
337    _mm256_extract_epi32::<0>(values)
338}
339
340#[cfg(target_arch = "x86_64")]
341#[target_feature(enable = "avx2")]
342#[inline]
343pub unsafe fn minimum_i32x16_avx2(values: &[i32; 16]) -> i32 {
344    let low = _mm256_loadu_si256(values.as_ptr().cast());
345    let high = _mm256_loadu_si256(values.as_ptr().add(8).cast());
346    reduce_min_i32x8(_mm256_min_epi32(low, high))
347}
348
349#[cfg(target_arch = "x86_64")]
350#[target_feature(enable = "avx2")]
351#[inline]
352pub unsafe fn maximum_i32x16_avx2(values: &[i32; 16]) -> i32 {
353    let low = _mm256_loadu_si256(values.as_ptr().cast());
354    let high = _mm256_loadu_si256(values.as_ptr().add(8).cast());
355    reduce_max_i32x8(_mm256_max_epi32(low, high))
356}
357
358#[cfg(target_arch = "x86_64")]
359#[target_feature(enable = "avx2")]
360#[inline]
361pub unsafe fn sum_i32x16_avx2(values: &[i32; 16]) -> i32 {
362    let low = _mm256_loadu_si256(values.as_ptr().cast());
363    let high = _mm256_loadu_si256(values.as_ptr().add(8).cast());
364    reduce_sum_i32x8(_mm256_add_epi32(low, high))
365}
366
367#[cfg(target_arch = "x86_64")]
368#[target_feature(enable = "avx2")]
369#[inline]
370unsafe fn range_mask_i32x8(start: usize, end: usize, offset: i32) -> __m256i {
371    let lanes = _mm256_setr_epi32(
372        offset,
373        offset + 1,
374        offset + 2,
375        offset + 3,
376        offset + 4,
377        offset + 5,
378        offset + 6,
379        offset + 7,
380    );
381    _mm256_and_si256(
382        _mm256_cmpgt_epi32(lanes, _mm256_set1_epi32(start as i32 - 1)),
383        _mm256_cmpgt_epi32(_mm256_set1_epi32(end as i32), lanes),
384    )
385}
386
387#[cfg(target_arch = "x86_64")]
388#[target_feature(enable = "avx2")]
389#[inline]
390pub unsafe fn minimum_range_i32x16_avx2(values: &[i32; 16], start: usize, end: usize) -> i32 {
391    let unit = _mm256_set1_epi32(i32::MAX);
392    let low = _mm256_blendv_epi8(
393        unit,
394        _mm256_loadu_si256(values.as_ptr().cast()),
395        range_mask_i32x8(start, end, 0),
396    );
397    let high = _mm256_blendv_epi8(
398        unit,
399        _mm256_loadu_si256(values.as_ptr().add(8).cast()),
400        range_mask_i32x8(start, end, 8),
401    );
402    reduce_min_i32x8(_mm256_min_epi32(low, high))
403}
404
405#[cfg(target_arch = "x86_64")]
406#[target_feature(enable = "avx2")]
407#[inline]
408pub unsafe fn maximum_range_i32x16_avx2(values: &[i32; 16], start: usize, end: usize) -> i32 {
409    let unit = _mm256_set1_epi32(i32::MIN);
410    let low = _mm256_blendv_epi8(
411        unit,
412        _mm256_loadu_si256(values.as_ptr().cast()),
413        range_mask_i32x8(start, end, 0),
414    );
415    let high = _mm256_blendv_epi8(
416        unit,
417        _mm256_loadu_si256(values.as_ptr().add(8).cast()),
418        range_mask_i32x8(start, end, 8),
419    );
420    reduce_max_i32x8(_mm256_max_epi32(low, high))
421}
422
423#[cfg(target_arch = "x86_64")]
424#[target_feature(enable = "avx2")]
425#[inline]
426pub unsafe fn sum_range_i32x16_avx2(values: &[i32; 16], start: usize, end: usize) -> i32 {
427    let low = _mm256_and_si256(
428        _mm256_loadu_si256(values.as_ptr().cast()),
429        range_mask_i32x8(start, end, 0),
430    );
431    let high = _mm256_and_si256(
432        _mm256_loadu_si256(values.as_ptr().add(8).cast()),
433        range_mask_i32x8(start, end, 8),
434    );
435    reduce_sum_i32x8(_mm256_add_epi32(low, high))
436}
437
438#[cfg(target_arch = "x86_64")]
439#[target_feature(enable = "avx512f")]
440#[inline]
441pub unsafe fn minimum_i32x16_avx512(values: &[i32; 16]) -> i32 {
442    _mm512_reduce_min_epi32(_mm512_loadu_si512(values.as_ptr().cast()))
443}
444
445#[cfg(target_arch = "x86_64")]
446#[target_feature(enable = "avx512f")]
447#[inline]
448pub unsafe fn maximum_i32x16_avx512(values: &[i32; 16]) -> i32 {
449    _mm512_reduce_max_epi32(_mm512_loadu_si512(values.as_ptr().cast()))
450}
451
452#[cfg(target_arch = "x86_64")]
453#[target_feature(enable = "avx512f")]
454#[inline]
455pub unsafe fn sum_i32x16_avx512(values: &[i32; 16]) -> i32 {
456    _mm512_reduce_add_epi32(_mm512_loadu_si512(values.as_ptr().cast()))
457}
458
459#[cfg(target_arch = "x86_64")]
460#[target_feature(enable = "avx512f")]
461#[inline]
462pub unsafe fn minimum_range_i32x16_avx512(values: &[i32; 16], start: usize, end: usize) -> i32 {
463    let mask = (u16::MAX << start) & (u16::MAX >> (16 - end));
464    _mm512_mask_reduce_min_epi32(mask, _mm512_loadu_si512(values.as_ptr().cast()))
465}
466
467#[cfg(target_arch = "x86_64")]
468#[target_feature(enable = "avx512f")]
469#[inline]
470pub unsafe fn maximum_range_i32x16_avx512(values: &[i32; 16], start: usize, end: usize) -> i32 {
471    let mask = (u16::MAX << start) & (u16::MAX >> (16 - end));
472    _mm512_mask_reduce_max_epi32(mask, _mm512_loadu_si512(values.as_ptr().cast()))
473}
474
475#[cfg(target_arch = "x86_64")]
476#[target_feature(enable = "avx512f")]
477#[inline]
478pub unsafe fn sum_range_i32x16_avx512(values: &[i32; 16], start: usize, end: usize) -> i32 {
479    let mask = (u16::MAX << start) & (u16::MAX >> (16 - end));
480    _mm512_mask_reduce_add_epi32(mask, _mm512_loadu_si512(values.as_ptr().cast()))
481}
482
483#[cfg(target_arch = "x86_64")]
484#[target_feature(enable = "avx2")]
485#[inline]
486unsafe fn min_i64x4(left: __m256i, right: __m256i) -> __m256i {
487    _mm256_blendv_epi8(left, right, _mm256_cmpgt_epi64(left, right))
488}
489
490#[cfg(target_arch = "x86_64")]
491#[target_feature(enable = "avx2")]
492#[inline]
493unsafe fn max_i64x4(left: __m256i, right: __m256i) -> __m256i {
494    _mm256_blendv_epi8(right, left, _mm256_cmpgt_epi64(left, right))
495}
496
497#[cfg(target_arch = "x86_64")]
498#[target_feature(enable = "avx2")]
499#[inline]
500unsafe fn reduce_min_i64x4(mut values: __m256i) -> i64 {
501    values = min_i64x4(values, _mm256_permute4x64_epi64::<0x4e>(values));
502    values = min_i64x4(values, _mm256_permute4x64_epi64::<0xb1>(values));
503    _mm256_extract_epi64::<0>(values)
504}
505
506#[cfg(target_arch = "x86_64")]
507#[target_feature(enable = "avx2")]
508#[inline]
509unsafe fn reduce_max_i64x4(mut values: __m256i) -> i64 {
510    values = max_i64x4(values, _mm256_permute4x64_epi64::<0x4e>(values));
511    values = max_i64x4(values, _mm256_permute4x64_epi64::<0xb1>(values));
512    _mm256_extract_epi64::<0>(values)
513}
514
515#[cfg(target_arch = "x86_64")]
516#[target_feature(enable = "avx2")]
517#[inline]
518unsafe fn reduce_sum_i64x4(mut values: __m256i) -> i64 {
519    values = _mm256_add_epi64(values, _mm256_permute4x64_epi64::<0x4e>(values));
520    values = _mm256_add_epi64(values, _mm256_permute4x64_epi64::<0xb1>(values));
521    _mm256_extract_epi64::<0>(values)
522}
523
524#[cfg(target_arch = "x86_64")]
525#[target_feature(enable = "avx2")]
526#[inline]
527pub unsafe fn minimum_i64x8_avx2(values: &[i64; 8]) -> i64 {
528    let low = _mm256_loadu_si256(values.as_ptr().cast());
529    let high = _mm256_loadu_si256(values.as_ptr().add(4).cast());
530    reduce_min_i64x4(min_i64x4(low, high))
531}
532
533#[cfg(target_arch = "x86_64")]
534#[target_feature(enable = "avx2")]
535#[inline]
536pub unsafe fn maximum_i64x8_avx2(values: &[i64; 8]) -> i64 {
537    let low = _mm256_loadu_si256(values.as_ptr().cast());
538    let high = _mm256_loadu_si256(values.as_ptr().add(4).cast());
539    reduce_max_i64x4(max_i64x4(low, high))
540}
541
542#[cfg(target_arch = "x86_64")]
543#[target_feature(enable = "avx2")]
544#[inline]
545pub unsafe fn sum_i64x8_avx2(values: &[i64; 8]) -> i64 {
546    let low = _mm256_loadu_si256(values.as_ptr().cast());
547    let high = _mm256_loadu_si256(values.as_ptr().add(4).cast());
548    reduce_sum_i64x4(_mm256_add_epi64(low, high))
549}
550
551#[cfg(target_arch = "x86_64")]
552#[target_feature(enable = "avx2")]
553#[inline]
554unsafe fn range_mask_i64x4(start: usize, end: usize, offset: i64) -> __m256i {
555    let lanes = _mm256_setr_epi64x(offset, offset + 1, offset + 2, offset + 3);
556    _mm256_and_si256(
557        _mm256_cmpgt_epi64(lanes, _mm256_set1_epi64x(start as i64 - 1)),
558        _mm256_cmpgt_epi64(_mm256_set1_epi64x(end as i64), lanes),
559    )
560}
561
562#[cfg(target_arch = "x86_64")]
563#[target_feature(enable = "avx2")]
564#[inline]
565pub unsafe fn minimum_range_i64x8_avx2(values: &[i64; 8], start: usize, end: usize) -> i64 {
566    let unit = _mm256_set1_epi64x(i64::MAX);
567    let low = _mm256_blendv_epi8(
568        unit,
569        _mm256_loadu_si256(values.as_ptr().cast()),
570        range_mask_i64x4(start, end, 0),
571    );
572    let high = _mm256_blendv_epi8(
573        unit,
574        _mm256_loadu_si256(values.as_ptr().add(4).cast()),
575        range_mask_i64x4(start, end, 4),
576    );
577    reduce_min_i64x4(min_i64x4(low, high))
578}
579
580#[cfg(target_arch = "x86_64")]
581#[target_feature(enable = "avx2")]
582#[inline]
583pub unsafe fn maximum_range_i64x8_avx2(values: &[i64; 8], start: usize, end: usize) -> i64 {
584    let unit = _mm256_set1_epi64x(i64::MIN);
585    let low = _mm256_blendv_epi8(
586        unit,
587        _mm256_loadu_si256(values.as_ptr().cast()),
588        range_mask_i64x4(start, end, 0),
589    );
590    let high = _mm256_blendv_epi8(
591        unit,
592        _mm256_loadu_si256(values.as_ptr().add(4).cast()),
593        range_mask_i64x4(start, end, 4),
594    );
595    reduce_max_i64x4(max_i64x4(low, high))
596}
597
598#[cfg(target_arch = "x86_64")]
599#[target_feature(enable = "avx2")]
600#[inline]
601pub unsafe fn sum_range_i64x8_avx2(values: &[i64; 8], start: usize, end: usize) -> i64 {
602    let low = _mm256_and_si256(
603        _mm256_loadu_si256(values.as_ptr().cast()),
604        range_mask_i64x4(start, end, 0),
605    );
606    let high = _mm256_and_si256(
607        _mm256_loadu_si256(values.as_ptr().add(4).cast()),
608        range_mask_i64x4(start, end, 4),
609    );
610    reduce_sum_i64x4(_mm256_add_epi64(low, high))
611}
612
613#[cfg(target_arch = "x86_64")]
614#[target_feature(enable = "avx512f")]
615#[inline]
616pub unsafe fn minimum_i64x8_avx512(values: &[i64; 8]) -> i64 {
617    _mm512_reduce_min_epi64(_mm512_loadu_si512(values.as_ptr().cast()))
618}
619
620#[cfg(target_arch = "x86_64")]
621#[target_feature(enable = "avx512f")]
622#[inline]
623pub unsafe fn maximum_i64x8_avx512(values: &[i64; 8]) -> i64 {
624    _mm512_reduce_max_epi64(_mm512_loadu_si512(values.as_ptr().cast()))
625}
626
627#[cfg(target_arch = "x86_64")]
628#[target_feature(enable = "avx512f")]
629#[inline]
630pub unsafe fn sum_i64x8_avx512(values: &[i64; 8]) -> i64 {
631    _mm512_reduce_add_epi64(_mm512_loadu_si512(values.as_ptr().cast()))
632}
633
634#[cfg(target_arch = "x86_64")]
635#[target_feature(enable = "avx512f")]
636#[inline]
637pub unsafe fn minimum_range_i64x8_avx512(values: &[i64; 8], start: usize, end: usize) -> i64 {
638    let mask = (u8::MAX << start) & (u8::MAX >> (8 - end));
639    _mm512_mask_reduce_min_epi64(mask, _mm512_loadu_si512(values.as_ptr().cast()))
640}
641
642#[cfg(target_arch = "x86_64")]
643#[target_feature(enable = "avx512f")]
644#[inline]
645pub unsafe fn maximum_range_i64x8_avx512(values: &[i64; 8], start: usize, end: usize) -> i64 {
646    let mask = (u8::MAX << start) & (u8::MAX >> (8 - end));
647    _mm512_mask_reduce_max_epi64(mask, _mm512_loadu_si512(values.as_ptr().cast()))
648}
649
650#[cfg(target_arch = "x86_64")]
651#[target_feature(enable = "avx512f")]
652#[inline]
653pub unsafe fn sum_range_i64x8_avx512(values: &[i64; 8], start: usize, end: usize) -> i64 {
654    let mask = (u8::MAX << start) & (u8::MAX >> (8 - end));
655    _mm512_mask_reduce_add_epi64(mask, _mm512_loadu_si512(values.as_ptr().cast()))
656}
competitive/data_structure/simd.rs

competitive/data_structure/
simd.rs
