Skip to main content

core_simd/
masks.rs

1//! Types and traits associated with masking elements of vectors.
2//! Types representing
3#![allow(non_camel_case_types)]
4
5use crate::simd::{Select, Simd, SimdCast, SimdElement};
6use core::cmp::Ordering;
7use core::{fmt, mem};
8
9pub(crate) trait FixEndianness {
10    fn fix_endianness(self) -> Self;
11}
12
13macro_rules! impl_fix_endianness {
14    { $($int:ty),* } => {
15        $(
16        impl FixEndianness for $int {
17            #[inline(always)]
18            fn fix_endianness(self) -> Self {
19                if cfg!(target_endian = "big") {
20                    <$int>::reverse_bits(self)
21                } else {
22                    self
23                }
24            }
25        }
26        )*
27    }
28}
29
30impl_fix_endianness! { u8, u16, u32, u64 }
31
32mod private_methods {
33    use super::*;
34
35    /// Not only does this seal the `MaskElement` trait, but these functions prevent other traits
36    /// from bleeding into the parent bounds.
37    ///
38    /// For example, `eq` could be provided by requiring `MaskElement: PartialEq`, but that would
39    /// prevent us from ever removing that bound, or from implementing `MaskElement` on
40    /// non-`PartialEq` types in the future.
41    pub impl(super) trait PrivateMethods {
42        fn valid<const N: usize>(values: Simd<Self, N>) -> bool
43        where
44            Self: SimdElement;
45
46        fn eq(self, other: Self) -> bool;
47
48        fn to_usize(self) -> usize;
49        fn max_unsigned() -> u64;
50
51        type Unsigned: SimdElement;
52
53        const TRUE: Self;
54
55        const FALSE: Self;
56    }
57}
58use private_methods::PrivateMethods;
59
60/// Marker trait for types that may be used as SIMD mask elements.
61///
62/// # Safety
63/// Type must be a signed integer.
64pub impl(self) unsafe trait MaskElement:
65    SimdElement<Mask = Self> + SimdCast + PrivateMethods
66{
67}
68
69macro_rules! impl_element {
70    { $ty:ty, $unsigned:ty } => {
71        impl PrivateMethods for $ty {
72            #[inline]
73            fn valid<const N: usize>(value: Simd<Self, N>) -> bool
74            {
75                // We can't use `Simd` directly, because `Simd`'s functions call this function and
76                // we will end up with an infinite loop.
77                // Safety: `value` is an integer vector
78                unsafe {
79                    use core::intrinsics::simd;
80                    let falses: Simd<Self, N> = simd::simd_eq(value, Simd::splat(0 as _));
81                    let trues: Simd<Self, N> = simd::simd_eq(value, Simd::splat(-1 as _));
82                    let valid: Simd<Self, N> = simd::simd_or(falses, trues);
83                    simd::simd_reduce_all(valid)
84                }
85            }
86
87            #[inline]
88            fn eq(self, other: Self) -> bool { self == other }
89
90            #[inline]
91            fn to_usize(self) -> usize {
92                self as usize
93            }
94
95            #[inline]
96            fn max_unsigned() -> u64 {
97                <$unsigned>::MAX as u64
98            }
99
100            type Unsigned = $unsigned;
101
102            const TRUE: Self = -1;
103            const FALSE: Self = 0;
104        }
105
106        // Safety: this is a valid mask element type
107        unsafe impl MaskElement for $ty {}
108    }
109}
110
111impl_element! { i8, u8 }
112impl_element! { i16, u16 }
113impl_element! { i32, u32 }
114impl_element! { i64, u64 }
115impl_element! { isize, usize }
116
117/// A SIMD vector mask for `N` elements of width specified by `Element`.
118///
119/// Masks represent boolean inclusion/exclusion on a per-element basis.
120///
121/// The layout of this type is unspecified, and may change between platforms
122/// and/or Rust versions, and code should not assume that it is equivalent to
123/// `[T; N]`.
124///
125/// `N` cannot be 0 and may be at most 64. This limit may be increased in
126/// the future.
127#[repr(transparent)]
128pub struct Mask<T, const N: usize>(Simd<T, N>)
129where
130    T: MaskElement;
131
132impl<T, const N: usize> Copy for Mask<T, N> where T: MaskElement {}
133
134impl<T, const N: usize> Clone for Mask<T, N>
135where
136    T: MaskElement,
137{
138    #[inline]
139    fn clone(&self) -> Self {
140        *self
141    }
142}
143
144impl<T, const N: usize> Mask<T, N>
145where
146    T: MaskElement,
147{
148    /// Constructs a mask by setting all elements to the given value.
149    #[inline]
150    #[rustc_const_unstable(feature = "portable_simd", issue = "86656")]
151    pub const fn splat(value: bool) -> Self {
152        Self(Simd::splat(if value { T::TRUE } else { T::FALSE }))
153    }
154
155    /// Converts an array of bools to a SIMD mask.
156    #[inline]
157    pub fn from_array(array: [bool; N]) -> Self {
158        // SAFETY: Rust's bool has a layout of 1 byte (u8) with a value of
159        //     true:    0b_0000_0001
160        //     false:   0b_0000_0000
161        // Thus, an array of bools is also a valid array of bytes: [u8; N]
162        // This would be hypothetically valid as an "in-place" transmute,
163        // but these are "dependently-sized" types, so copy elision it is!
164        unsafe {
165            let bytes: [u8; N] = mem::transmute_copy(&array);
166            let bools: Simd<i8, N> =
167                core::intrinsics::simd::simd_ne(Simd::from_array(bytes), Simd::splat(0u8));
168            Mask::from_simd_unchecked(core::intrinsics::simd::simd_cast(bools))
169        }
170    }
171
172    /// Converts a SIMD mask to an array of bools.
173    #[inline]
174    pub fn to_array(self) -> [bool; N] {
175        // This follows mostly the same logic as from_array.
176        // SAFETY: Rust's bool has a layout of 1 byte (u8) with a value of
177        //     true:    0b_0000_0001
178        //     false:   0b_0000_0000
179        // Thus, an array of bools is also a valid array of bytes: [u8; N]
180        // Since our masks are equal to integers where all bits are set,
181        // we can simply convert them to i8s, and then bitand them by the
182        // bitpattern for Rust's "true" bool.
183        // This would be hypothetically valid as an "in-place" transmute,
184        // but these are "dependently-sized" types, so copy elision it is!
185        unsafe {
186            let mut bytes: Simd<i8, N> = core::intrinsics::simd::simd_cast(self.to_simd());
187            bytes &= Simd::splat(1i8);
188            mem::transmute_copy(&bytes)
189        }
190    }
191
192    /// Converts a vector of integers to a mask, where 0 represents `false` and -1
193    /// represents `true`.
194    ///
195    /// # Safety
196    /// All elements must be either 0 or -1.
197    #[inline]
198    #[must_use = "method returns a new mask and does not mutate the original value"]
199    pub unsafe fn from_simd_unchecked(value: Simd<T, N>) -> Self {
200        // Safety: the caller must confirm this invariant
201        unsafe {
202            core::intrinsics::assume(<T as PrivateMethods>::valid(value));
203        }
204        Self(value)
205    }
206
207    /// Converts a vector of integers to a mask, where 0 represents `false` and -1
208    /// represents `true`.
209    ///
210    /// # Panics
211    /// Panics if any element is not 0 or -1.
212    #[inline]
213    #[must_use = "method returns a new mask and does not mutate the original value"]
214    #[track_caller]
215    pub fn from_simd(value: Simd<T, N>) -> Self {
216        assert!(T::valid(value), "all values must be either 0 or -1",);
217        // Safety: the validity has been checked
218        unsafe { Self::from_simd_unchecked(value) }
219    }
220
221    /// Converts the mask to a vector of integers, where 0 represents `false` and -1
222    /// represents `true`.
223    #[inline]
224    #[must_use = "method returns a new vector and does not mutate the original value"]
225    pub fn to_simd(self) -> Simd<T, N> {
226        self.0
227    }
228
229    /// Converts the mask to a mask of any other element size.
230    #[inline]
231    #[must_use = "method returns a new mask and does not mutate the original value"]
232    pub fn cast<U: MaskElement>(self) -> Mask<U, N> {
233        // Safety: mask elements are integers
234        unsafe { Mask(core::intrinsics::simd::simd_as(self.0)) }
235    }
236
237    /// Tests the value of the specified element.
238    ///
239    /// # Safety
240    /// `index` must be less than `self.len()`.
241    #[inline]
242    #[must_use = "method returns a new bool and does not mutate the original value"]
243    pub unsafe fn test_unchecked(&self, index: usize) -> bool {
244        // Safety: the caller must confirm this invariant
245        unsafe { T::eq(self.0.get_unchecked(index), T::TRUE) }
246    }
247
248    /// Tests the value of the specified element.
249    ///
250    /// # Panics
251    /// Panics if `index` is greater than or equal to the number of elements in the vector.
252    #[inline]
253    #[must_use = "method returns a new bool and does not mutate the original value"]
254    #[track_caller]
255    pub fn test(&self, index: usize) -> bool {
256        T::eq(self.0.get(index), T::TRUE)
257    }
258
259    /// Sets the value of the specified element.
260    ///
261    /// # Safety
262    /// `index` must be less than `self.len()`.
263    #[inline]
264    pub unsafe fn set_unchecked(&mut self, index: usize, value: bool) {
265        // Safety: the caller must confirm this invariant
266        unsafe {
267            self.0
268                .set_unchecked(index, if value { T::TRUE } else { T::FALSE });
269        }
270    }
271
272    /// Sets the value of the specified element.
273    ///
274    /// # Panics
275    /// Panics if `index` is greater than or equal to the number of elements in the vector.
276    #[inline]
277    #[track_caller]
278    pub fn set(&mut self, index: usize, value: bool) {
279        self.0.set(index, if value { T::TRUE } else { T::FALSE });
280    }
281
282    /// Returns true if any element is set, or false otherwise.
283    #[inline]
284    #[must_use = "method returns a new bool and does not mutate the original value"]
285    pub fn any(self) -> bool {
286        // Safety: `self` is a mask vector
287        unsafe { core::intrinsics::simd::simd_reduce_any(self.0) }
288    }
289
290    /// Returns true if all elements are set, or false otherwise.
291    #[inline]
292    #[must_use = "method returns a new bool and does not mutate the original value"]
293    pub fn all(self) -> bool {
294        // Safety: `self` is a mask vector
295        unsafe { core::intrinsics::simd::simd_reduce_all(self.0) }
296    }
297
298    /// Creates a bitmask from a mask.
299    ///
300    /// Each bit is set if the corresponding element in the mask is `true`.
301    #[inline]
302    #[must_use = "method returns a new integer and does not mutate the original value"]
303    pub fn to_bitmask(self) -> u64 {
304        const {
305            assert!(N <= 64, "number of elements can't be greater than 64");
306        }
307
308        #[inline]
309        unsafe fn to_bitmask_impl<T, U: FixEndianness, const M: usize, const N: usize>(
310            mask: Mask<T, N>,
311        ) -> U
312        where
313            T: MaskElement,
314        {
315            let resized = mask.resize::<M>(false);
316
317            // Safety: `resized` is an integer vector with length M, which must match T
318            let bitmask: U = unsafe { core::intrinsics::simd::simd_bitmask(resized.0) };
319
320            // LLVM assumes bit order should match endianness
321            bitmask.fix_endianness()
322        }
323
324        // TODO modify simd_bitmask to zero-extend output, making this unnecessary
325        if N <= 8 {
326            // Safety: bitmask matches length
327            unsafe { to_bitmask_impl::<T, u8, 8, N>(self) as u64 }
328        } else if N <= 16 {
329            // Safety: bitmask matches length
330            unsafe { to_bitmask_impl::<T, u16, 16, N>(self) as u64 }
331        } else if N <= 32 {
332            // Safety: bitmask matches length
333            unsafe { to_bitmask_impl::<T, u32, 32, N>(self) as u64 }
334        } else {
335            // Safety: bitmask matches length
336            unsafe { to_bitmask_impl::<T, u64, 64, N>(self) }
337        }
338    }
339
340    /// Creates a mask from a bitmask.
341    ///
342    /// For each bit, if it is set, the corresponding element in the mask is set to `true`.
343    /// If the mask contains more than 64 elements, the remainder are set to `false`.
344    #[inline]
345    #[must_use = "method returns a new mask and does not mutate the original value"]
346    pub fn from_bitmask(bitmask: u64) -> Self {
347        Self(bitmask.select(Simd::splat(T::TRUE), Simd::splat(T::FALSE)))
348    }
349
350    /// Finds the index of the first set element.
351    ///
352    /// ```
353    /// # #![feature(portable_simd)]
354    /// # #[cfg(feature = "as_crate")] use core_simd::simd;
355    /// # #[cfg(not(feature = "as_crate"))] use core::simd;
356    /// # use simd::mask32x8;
357    /// assert_eq!(mask32x8::splat(false).first_set(), None);
358    /// assert_eq!(mask32x8::splat(true).first_set(), Some(0));
359    ///
360    /// let mask = mask32x8::from_array([false, true, false, false, true, false, false, true]);
361    /// assert_eq!(mask.first_set(), Some(1));
362    /// ```
363    #[inline]
364    #[must_use = "method returns the index and does not mutate the original value"]
365    pub fn first_set(self) -> Option<usize> {
366        // If bitmasks are efficient, using them is better
367        if cfg!(target_feature = "sse") && N <= 64 {
368            return self.to_bitmask().lowest_one().map(|i| i as usize);
369        }
370
371        // To find the first set index:
372        // * create a vector 0..N
373        // * replace unset mask elements in that vector with -1
374        // * perform _unsigned_ reduce-min
375        // * check if the result is -1 or an index
376
377        let index: Simd<T, N> = const {
378            let mut index = [0; N];
379            let mut i = 0;
380            while i < N {
381                index[i] = i;
382                i += 1;
383            }
384            // Safety: the input and output are integer vectors
385            unsafe { core::intrinsics::simd::simd_cast(Simd::from_array(index)) }
386        };
387
388        // Safety: the input and output are integer vectors
389        let masked_index: Simd<T, N> =
390            unsafe { core::intrinsics::simd::simd_or((!self).to_simd(), index) };
391
392        // Safety: the input and output are integer vectors
393        let masked_index: Simd<T::Unsigned, N> =
394            unsafe { core::intrinsics::simd::simd_cast(masked_index) };
395
396        // Safety: the input is an integer vector
397        let min_index: T::Unsigned =
398            unsafe { core::intrinsics::simd::simd_reduce_min(masked_index) };
399
400        // Safety: the return value is the unsigned version of T
401        let min_index: T = unsafe { core::mem::transmute_copy(&min_index) };
402
403        if min_index.eq(T::TRUE) {
404            None
405        } else {
406            let min_index = min_index.to_usize();
407
408            // Allow eliminating bounds checks when using the index
409            // Safety: the index can't exceed the number of elements in the vector
410            unsafe {
411                core::hint::assert_unchecked(min_index < N);
412            }
413
414            Some(min_index)
415        }
416    }
417
418    /// Finds the index of the last set element.
419    ///
420    /// ```
421    /// # #![feature(portable_simd)]
422    /// # #[cfg(feature = "as_crate")] use core_simd::simd;
423    /// # #[cfg(not(feature = "as_crate"))] use core::simd;
424    /// # use simd::mask32x8;
425    /// assert_eq!(mask32x8::splat(false).last_set(), None);
426    /// assert_eq!(mask32x8::splat(true).last_set(), Some(7));
427    ///
428    /// let mask = mask32x8::from_array([false, true, false, false, true, false, true, false]);
429    /// assert_eq!(mask.last_set(), Some(6));
430    /// ```
431    #[inline]
432    #[must_use = "method returns the index and does not mutate the original value"]
433    pub fn last_set(self) -> Option<usize> {
434        // If bitmasks are efficient, using them is better
435        if cfg!(target_feature = "sse") && N <= 64 {
436            return self.to_bitmask().highest_one().map(|i| i as usize);
437        }
438
439        // To find the first set index:
440        // * create a vector 0..N
441        // * replace unset mask elements in that vector with -1
442        // * perform _signed_ reduce-max
443        // * check if the result is -1 or an index
444
445        let index: Simd<T, N> = const {
446            let mut index = [0; N];
447            let mut i = 0;
448            while i < N {
449                index[i] = i;
450                i += 1;
451            }
452            // Safety: the input and output are integer vectors
453            unsafe { core::intrinsics::simd::simd_cast(Simd::from_array(index)) }
454        };
455
456        // Safety: the input and output are integer vectors
457        let masked_index: Simd<T, N> =
458            unsafe { core::intrinsics::simd::simd_or((!self).to_simd(), index) };
459
460        // Safety: the input is an integer vector
461        let max_index: T = unsafe { core::intrinsics::simd::simd_reduce_max(masked_index) };
462
463        if max_index.eq(T::TRUE) {
464            None
465        } else {
466            let max_index = max_index.to_usize();
467
468            // Allow eliminating bounds checks when using the index
469            // Safety: the index can't exceed the number of elements in the vector
470            unsafe {
471                core::hint::assert_unchecked(max_index < N);
472            }
473
474            Some(max_index)
475        }
476    }
477}
478
479// vector/array conversion
480impl<T, const N: usize> From<[bool; N]> for Mask<T, N>
481where
482    T: MaskElement,
483{
484    #[inline]
485    fn from(array: [bool; N]) -> Self {
486        Self::from_array(array)
487    }
488}
489
490impl<T, const N: usize> From<Mask<T, N>> for [bool; N]
491where
492    T: MaskElement,
493{
494    #[inline]
495    fn from(vector: Mask<T, N>) -> Self {
496        vector.to_array()
497    }
498}
499
500impl<T, const N: usize> Default for Mask<T, N>
501where
502    T: MaskElement,
503{
504    #[inline]
505    fn default() -> Self {
506        Self::splat(false)
507    }
508}
509
510impl<T, const N: usize> PartialEq for Mask<T, N>
511where
512    T: MaskElement + PartialEq,
513{
514    #[inline]
515    fn eq(&self, other: &Self) -> bool {
516        self.0 == other.0
517    }
518}
519
520impl<T, const N: usize> PartialOrd for Mask<T, N>
521where
522    T: MaskElement + PartialOrd,
523{
524    #[inline]
525    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
526        self.0.partial_cmp(&other.0)
527    }
528}
529
530impl<T, const N: usize> fmt::Debug for Mask<T, N>
531where
532    T: MaskElement + fmt::Debug,
533{
534    #[inline]
535    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
536        f.debug_list()
537            .entries((0..N).map(|i| self.test(i)))
538            .finish()
539    }
540}
541
542impl<T, const N: usize> core::ops::BitAnd for Mask<T, N>
543where
544    T: MaskElement,
545{
546    type Output = Self;
547    #[inline]
548    fn bitand(self, rhs: Self) -> Self {
549        // Safety: `self` is an integer vector
550        unsafe { Self(core::intrinsics::simd::simd_and(self.0, rhs.0)) }
551    }
552}
553
554impl<T, const N: usize> core::ops::BitAnd<bool> for Mask<T, N>
555where
556    T: MaskElement,
557{
558    type Output = Self;
559    #[inline]
560    fn bitand(self, rhs: bool) -> Self {
561        self & Self::splat(rhs)
562    }
563}
564
565impl<T, const N: usize> core::ops::BitAnd<Mask<T, N>> for bool
566where
567    T: MaskElement,
568{
569    type Output = Mask<T, N>;
570    #[inline]
571    fn bitand(self, rhs: Mask<T, N>) -> Mask<T, N> {
572        Mask::splat(self) & rhs
573    }
574}
575
576impl<T, const N: usize> core::ops::BitOr for Mask<T, N>
577where
578    T: MaskElement,
579{
580    type Output = Self;
581    #[inline]
582    fn bitor(self, rhs: Self) -> Self {
583        // Safety: `self` is an integer vector
584        unsafe { Self(core::intrinsics::simd::simd_or(self.0, rhs.0)) }
585    }
586}
587
588impl<T, const N: usize> core::ops::BitOr<bool> for Mask<T, N>
589where
590    T: MaskElement,
591{
592    type Output = Self;
593    #[inline]
594    fn bitor(self, rhs: bool) -> Self {
595        self | Self::splat(rhs)
596    }
597}
598
599impl<T, const N: usize> core::ops::BitOr<Mask<T, N>> for bool
600where
601    T: MaskElement,
602{
603    type Output = Mask<T, N>;
604    #[inline]
605    fn bitor(self, rhs: Mask<T, N>) -> Mask<T, N> {
606        Mask::splat(self) | rhs
607    }
608}
609
610impl<T, const N: usize> core::ops::BitXor for Mask<T, N>
611where
612    T: MaskElement,
613{
614    type Output = Self;
615    #[inline]
616    fn bitxor(self, rhs: Self) -> Self::Output {
617        // Safety: `self` is an integer vector
618        unsafe { Self(core::intrinsics::simd::simd_xor(self.0, rhs.0)) }
619    }
620}
621
622impl<T, const N: usize> core::ops::BitXor<bool> for Mask<T, N>
623where
624    T: MaskElement,
625{
626    type Output = Self;
627    #[inline]
628    fn bitxor(self, rhs: bool) -> Self::Output {
629        self ^ Self::splat(rhs)
630    }
631}
632
633impl<T, const N: usize> core::ops::BitXor<Mask<T, N>> for bool
634where
635    T: MaskElement,
636{
637    type Output = Mask<T, N>;
638    #[inline]
639    fn bitxor(self, rhs: Mask<T, N>) -> Self::Output {
640        Mask::splat(self) ^ rhs
641    }
642}
643
644impl<T, const N: usize> core::ops::Not for Mask<T, N>
645where
646    T: MaskElement,
647{
648    type Output = Mask<T, N>;
649    #[inline]
650    fn not(self) -> Self::Output {
651        Self::splat(true) ^ self
652    }
653}
654
655impl<T, const N: usize> core::ops::BitAndAssign for Mask<T, N>
656where
657    T: MaskElement,
658{
659    #[inline]
660    fn bitand_assign(&mut self, rhs: Self) {
661        *self = *self & rhs;
662    }
663}
664
665impl<T, const N: usize> core::ops::BitAndAssign<bool> for Mask<T, N>
666where
667    T: MaskElement,
668{
669    #[inline]
670    fn bitand_assign(&mut self, rhs: bool) {
671        *self &= Self::splat(rhs);
672    }
673}
674
675impl<T, const N: usize> core::ops::BitOrAssign for Mask<T, N>
676where
677    T: MaskElement,
678{
679    #[inline]
680    fn bitor_assign(&mut self, rhs: Self) {
681        *self = *self | rhs;
682    }
683}
684
685impl<T, const N: usize> core::ops::BitOrAssign<bool> for Mask<T, N>
686where
687    T: MaskElement,
688{
689    #[inline]
690    fn bitor_assign(&mut self, rhs: bool) {
691        *self |= Self::splat(rhs);
692    }
693}
694
695impl<T, const N: usize> core::ops::BitXorAssign for Mask<T, N>
696where
697    T: MaskElement,
698{
699    #[inline]
700    fn bitxor_assign(&mut self, rhs: Self) {
701        *self = *self ^ rhs;
702    }
703}
704
705impl<T, const N: usize> core::ops::BitXorAssign<bool> for Mask<T, N>
706where
707    T: MaskElement,
708{
709    #[inline]
710    fn bitxor_assign(&mut self, rhs: bool) {
711        *self ^= Self::splat(rhs);
712    }
713}
714
715macro_rules! impl_from {
716    { $from:ty  => $($to:ty),* } => {
717        $(
718        impl<const N: usize> From<Mask<$from, N>> for Mask<$to, N>
719        {
720            #[inline]
721            fn from(value: Mask<$from, N>) -> Self {
722                value.cast()
723            }
724        }
725        )*
726    }
727}
728impl_from! { i8 => i16, i32, i64, isize }
729impl_from! { i16 => i32, i64, isize, i8 }
730impl_from! { i32 => i64, isize, i8, i16 }
731impl_from! { i64 => isize, i8, i16, i32 }
732impl_from! { isize => i8, i16, i32, i64 }