widebits 0.0.1

An experimental bit sequence library with bitwise operations and SIMD acceleration.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

#[cfg(target_arch = "x86_64")]
use core::arch::x86_64::*;

use crate::{WBLH, WideBits};

#[cfg(target_arch = "x86_64")]
type Avx2BinOp = unsafe fn(__m256i, __m256i) -> __m256i;

#[cfg(target_arch = "x86_64")]
impl WideBits {
    #[target_feature(enable = "avx2")]
    unsafe fn binary_op_avx2_words_to<F>(
        lhs: *const u64,
        rhs: *const u64,
        dst: *mut u64,
        word_len: usize,
        simd_op: Avx2BinOp,
        scalar_op: F,
    ) where
        F: Fn(u64, u64) -> u64,
    {
        let chunks = word_len / 4;
        let simd_words = chunks * 4;

        for i in 0..chunks {
            let off = i * 4;
            let a = unsafe { _mm256_loadu_si256(lhs.add(off) as *const __m256i) };
            let b = unsafe { _mm256_loadu_si256(rhs.add(off) as *const __m256i) };
            let r = unsafe { simd_op(a, b) };
            unsafe { _mm256_storeu_si256(dst.add(off) as *mut __m256i, r) };
        }

        for i in simd_words..word_len {
            unsafe {
                *dst.add(i) = scalar_op(*lhs.add(i), *rhs.add(i));
            }
        }
    }

    #[target_feature(enable = "avx2")]
    unsafe fn binary_op_avx2_kernel<F>(
        lhs: &Self,
        rhs: &Self,
        simd_op: Avx2BinOp,
        scalar_op: F,
    ) -> (usize, Box<[u64]>)
    where
        F: Fn(u64, u64) -> u64,
    {
        let len = lhs.len.min(rhs.len);
        let word_len = WBLH::required_word_len(len);
        let mut data = vec![0u64; word_len];

        unsafe {
            Self::binary_op_avx2_words_to(
                lhs.data.as_ptr(),
                rhs.data.as_ptr(),
                data.as_mut_ptr(),
                word_len,
                simd_op,
                scalar_op,
            );
        }

        let mut data = data.into_boxed_slice();
        WBLH::sanitize_last_word(&mut data, len);
        (len, data)
    }

    #[target_feature(enable = "avx2")]
    unsafe fn binary_op_avx2<F>(&self, rhs: &Self, simd_op: Avx2BinOp, scalar_op: F) -> Self
    where
        F: Fn(u64, u64) -> u64,
    {
        let (len, data) = unsafe { Self::binary_op_avx2_kernel(self, rhs, simd_op, scalar_op) };
        Self::new_unchecked(len, data)
    }

    #[target_feature(enable = "avx2")]
    unsafe fn binary_op_assign_avx2<F>(&mut self, rhs: &Self, simd_op: Avx2BinOp, scalar_op: F)
    where
        F: Fn(u64, u64) -> u64,
    {
        let (len, data) = unsafe { Self::binary_op_avx2_kernel(self, rhs, simd_op, scalar_op) };
        self.len = len;
        self.data = data;
    }
}

#[cfg(target_arch = "x86_64")]
impl WideBits {
    #[target_feature(enable = "avx2")]
    pub(super) unsafe fn and_avx2(&self, rhs: &Self) -> Self {
        unsafe { self.binary_op_avx2(rhs, _mm256_and_si256, |x, y| x & y) }
    }

    #[target_feature(enable = "avx2")]
    pub(super) unsafe fn and_assign_avx2(&mut self, rhs: &Self) {
        unsafe { self.binary_op_assign_avx2(rhs, _mm256_and_si256, |x, y| x & y) }
    }

    #[target_feature(enable = "avx2")]
    pub(super) unsafe fn or_avx2(&self, rhs: &Self) -> Self {
        unsafe { self.binary_op_avx2(rhs, _mm256_or_si256, |x, y| x | y) }
    }

    #[target_feature(enable = "avx2")]
    pub(super) unsafe fn or_assign_avx2(&mut self, rhs: &Self) {
        unsafe { self.binary_op_assign_avx2(rhs, _mm256_or_si256, |x, y| x | y) }
    }

    #[target_feature(enable = "avx2")]
    pub(super) unsafe fn xor_avx2(&self, rhs: &Self) -> Self {
        unsafe { self.binary_op_avx2(rhs, _mm256_xor_si256, |x, y| x ^ y) }
    }

    #[target_feature(enable = "avx2")]
    pub(super) unsafe fn xor_assign_avx2(&mut self, rhs: &Self) {
        unsafe { self.binary_op_assign_avx2(rhs, _mm256_xor_si256, |x, y| x ^ y) }
    }

    #[target_feature(enable = "avx2")]
    pub(super) unsafe fn andnot_avx2(&self, rhs: &Self) -> Self {
        unsafe {
            self.binary_op_avx2(
                rhs,
                // _mm256_andnot_si256(a, b) == (!a) & b
                |a, b| _mm256_andnot_si256(b, a), // self & !rhs == (!rhs) & self
                |x, y| x & !y,
            )
        }
    }

    #[target_feature(enable = "avx2")]
    pub(super) unsafe fn andnot_assign_avx2(&mut self, rhs: &Self) {
        unsafe {
            self.binary_op_assign_avx2(
                rhs,
                // _mm256_andnot_si256(a, b) == (!a) & b
                |a, b| _mm256_andnot_si256(b, a), // self & !rhs == (!rhs) & self
                |x, y| x & !y,
            )
        }
    }
}