1#[cfg(target_arch = "x86_64")]
17pub mod x86;
18
19pub mod portable;
20
21#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
28pub enum Backend {
29 Avx512,
31 Avx2,
33 Portable,
35}
36
37impl Backend {
38 #[must_use]
40 pub const fn lanes_64bit(self) -> usize {
41 match self {
42 Self::Avx512 => 8,
43 Self::Avx2 => 4,
44 Self::Portable => 1,
45 }
46 }
47
48 #[must_use]
50 pub const fn as_str(self) -> &'static str {
51 match self {
52 Self::Avx512 => "avx512",
53 Self::Avx2 => "avx2",
54 Self::Portable => "portable",
55 }
56 }
57}
58
59#[must_use]
61pub fn detect_backend() -> Backend {
62 #[cfg(target_arch = "x86_64")]
63 {
64 if std::arch::is_x86_feature_detected!("avx512f") {
65 return Backend::Avx512;
66 }
67 if std::arch::is_x86_feature_detected!("avx2") {
68 return Backend::Avx2;
69 }
70 }
71 Backend::Portable
72}
73
74#[must_use]
80pub fn scan_greater_than_i64(data: &[i64], target: i64) -> usize {
81 scan_greater_than_i64_with(data, target, detect_backend())
82}
83
84#[must_use]
91pub fn scan_greater_than_i64_with(data: &[i64], target: i64, backend: Backend) -> usize {
92 match backend {
93 #[cfg(target_arch = "x86_64")]
94 Backend::Avx512 if std::arch::is_x86_feature_detected!("avx512f") => {
95 unsafe { x86::scan_gt_i64_avx512(data, target) }
98 }
99 #[cfg(target_arch = "x86_64")]
100 Backend::Avx2 if std::arch::is_x86_feature_detected!("avx2") => {
101 unsafe { x86::scan_gt_i64_avx2(data, target) }
104 }
105 _ => portable::scan_gt_i64(data, target),
106 }
107}
108
109#[cfg(test)]
110mod tests {
111 use super::*;
112
113 fn oracle(data: &[i64], target: i64) -> usize {
115 data.iter().filter(|&&x| x > target).count()
116 }
117
118 fn all_backends() -> Vec<Backend> {
119 let mut v = vec![Backend::Portable];
120 #[cfg(target_arch = "x86_64")]
121 {
122 if std::arch::is_x86_feature_detected!("avx2") {
123 v.push(Backend::Avx2);
124 }
125 if std::arch::is_x86_feature_detected!("avx512f") {
126 v.push(Backend::Avx512);
127 }
128 }
129 v
130 }
131
132 #[test]
136 fn matches_oracle_across_all_lengths_and_backends() {
137 for backend in all_backends() {
138 for len in 0..=257_usize {
139 let data: Vec<i64> = (0..len).map(|i| (i % 50) as i64).collect();
140 let target = 24;
141 let expected = oracle(&data, target);
142 let got = scan_greater_than_i64_with(&data, target, backend);
143 assert_eq!(
144 got, expected,
145 "backend {backend:?} disagreed at len {len}: got {got}, want {expected}",
146 );
147 }
148 }
149 }
150
151 #[test]
152 fn all_match_and_no_match_boundaries() {
153 for backend in all_backends() {
154 for len in [0_usize, 1, 7, 8, 9, 63, 64, 65, 257] {
155 let data = vec![10_i64; len];
156
157 assert_eq!(
158 scan_greater_than_i64_with(&data, 9, backend),
159 len,
160 "backend {backend:?}: all elements should match at len {len}",
161 );
162 assert_eq!(
164 scan_greater_than_i64_with(&data, 10, backend),
165 0,
166 "backend {backend:?}: equal target must not match at len {len}",
167 );
168 assert_eq!(
169 scan_greater_than_i64_with(&data, 11, backend),
170 0,
171 "backend {backend:?}: larger target must not match at len {len}",
172 );
173 }
174 }
175 }
176
177 #[test]
178 fn handles_extremes_without_overflow() {
179 let data = [i64::MIN, -1, 0, 1, i64::MAX];
180 for backend in all_backends() {
181 for target in [i64::MIN, -1, 0, 1, i64::MAX] {
182 assert_eq!(
183 scan_greater_than_i64_with(&data, target, backend),
184 oracle(&data, target),
185 "backend {backend:?} disagreed for target {target}",
186 );
187 }
188 }
189 }
190
191 #[test]
192 fn backends_agree_with_each_other() {
193 let mut state: i64 = 0x2545_F491;
196 let data: Vec<i64> = (0..10_000)
197 .map(|_| {
198 state = state
199 .wrapping_mul(6_364_136_223_846_793_005)
200 .wrapping_add(1_442_695_040_888_963_407);
201 state.rem_euclid(1000)
202 })
203 .collect();
204 let reference = portable::scan_gt_i64(&data, 500);
205 for backend in all_backends() {
206 assert_eq!(
207 scan_greater_than_i64_with(&data, 500, backend),
208 reference,
209 "backend {backend:?} disagreed with the portable reference",
210 );
211 }
212 }
213}