11// SPDX-License-Identifier: Apache-2.0
22// SPDX-FileCopyrightText: Copyright the Vortex contributors
33
4+ use fearless_simd:: Level ;
5+ use fearless_simd:: Simd ;
6+ use fearless_simd:: dispatch;
7+ use fearless_simd:: prelude:: * ;
8+ use fearless_simd:: u8x64;
9+ use fearless_simd:: u64x8;
10+ use fearless_simd_macros:: simd;
11+ use vortex_error:: VortexExpect ;
12+
413use super :: count_ones:: align_offset_len;
514use crate :: dispatch:: CpuKernel ;
615
@@ -10,12 +19,8 @@ use crate::dispatch::CpuKernel;
1019/// The returned position is relative to the logical start (i.e., 0-indexed from `offset`).
1120/// Returns `None` if `nth` is out of bounds.
1221///
13- /// Uses architecture-specific optimizations:
14- /// - **aarch64**: NEON `vcnt`-based popcount for the 64-byte chunk scan.
15- /// - **x86_64 + AVX-512 VPOPCNTDQ**: 64-byte chunk scan.
16- /// - **x86_64 + AVX-512 VBMI2**: byte-lane compress for the final in-word select.
17- /// - **x86_64 + BMI2**: `pdep` + `tzcnt` for the final in-word select.
18- /// - **Scalar fallback**: 4× unrolled word scan with `count_ones`, byte-level narrowing.
22+ /// 64-byte chunks are scanned and selected with SIMD popcounts. The final in-word select uses
23+ /// `pdep` + `tzcnt` on x86_64 with BMI2, and a scalar fallback elsewhere.
1924#[ inline]
2025pub fn bit_select ( bytes : & [ u8 ] , offset : usize , len : usize , nth : usize ) -> Option < usize > {
2126 let ( head, middle, tail) = align_offset_len ( bytes, offset, len) ;
@@ -83,140 +88,28 @@ pub fn bit_select(bytes: &[u8], offset: usize, len: usize, nth: usize) -> Option
8388///
8489/// If `chunk_index < chunks.len()`, the target bit is inside that chunk and `remaining`
8590/// is the rank *within* that chunk. Otherwise all chunks were consumed.
86- type ScanChunks = unsafe fn ( & [ [ u8 ; 64 ] ] , usize , usize ) -> ( usize , usize , usize ) ;
87-
8891#[ inline]
8992fn scan_chunks ( chunks : & [ [ u8 ; 64 ] ] , remaining : usize , pos : usize ) -> ( usize , usize , usize ) {
90- // Scans of a couple of chunks don't amortize the dispatch indirection: call the
91- // per-architecture unconditional kernel directly so it stays inlinable (see the
92- // size-gating note in the CpuKernel docs).
93- if chunks. len ( ) <= 2 {
94- #[ cfg( target_arch = "aarch64" ) ]
95- return scan_chunks_neon ( chunks, remaining, pos) ;
96- #[ allow( unreachable_code) ]
97- {
98- return scan_chunks_scalar ( chunks, remaining, pos) ;
99- }
100- }
101-
102- static KERNEL : CpuKernel < ScanChunks > = CpuKernel :: new ( || {
103- #[ cfg( target_arch = "x86_64" ) ]
104- {
105- if is_x86_feature_detected ! ( "avx512f" ) && is_x86_feature_detected ! ( "avx512vpopcntdq" ) {
106- return scan_chunks_avx512_vpopcnt;
107- }
108- }
109- #[ cfg( target_arch = "aarch64" ) ]
110- return scan_chunks_neon;
111- // The aarch64 arm above returns unconditionally (NEON needs no probe), making
112- // this portable default unreachable there.
113- #[ allow( unreachable_code) ]
114- {
115- scan_chunks_scalar
116- }
117- } ) ;
118- // SAFETY: the selector only returns kernels that are safe or whose required CPU
119- // features were probed before selection.
120- unsafe { KERNEL . get ( ) ( chunks, remaining, pos) }
121- }
122-
123- #[ cfg( target_arch = "aarch64" ) ]
124- #[ allow( clippy:: cast_possible_truncation) ] // u64 → usize is lossless on aarch64 (64-bit)
125- #[ inline]
126- fn scan_chunks_neon (
127- chunks : & [ [ u8 ; 64 ] ] ,
128- mut remaining : usize ,
129- mut pos : usize ,
130- ) -> ( usize , usize , usize ) {
131- use std:: arch:: aarch64:: vcntq_u8;
132- use std:: arch:: aarch64:: vgetq_lane_u64;
133- use std:: arch:: aarch64:: vld1q_u8;
134- use std:: arch:: aarch64:: vpaddlq_u8;
135- use std:: arch:: aarch64:: vpaddlq_u16;
136- use std:: arch:: aarch64:: vpaddlq_u32;
137-
138- for ( idx, chunk) in chunks. iter ( ) . enumerate ( ) {
139- let ptr = chunk. as_ptr ( ) ;
140- // SAFETY: chunk is exactly 64 bytes split across four 128-bit NEON loads.
141- // NEON vld1q_u8 supports unaligned access.
142- let total = unsafe {
143- let pop_0 = vcntq_u8 ( vld1q_u8 ( ptr) ) ;
144- let pop_1 = vcntq_u8 ( vld1q_u8 ( ptr. add ( 16 ) ) ) ;
145- let pop_2 = vcntq_u8 ( vld1q_u8 ( ptr. add ( 32 ) ) ) ;
146- let pop_3 = vcntq_u8 ( vld1q_u8 ( ptr. add ( 48 ) ) ) ;
147- let sums_0 = vpaddlq_u32 ( vpaddlq_u16 ( vpaddlq_u8 ( pop_0) ) ) ;
148- let sums_1 = vpaddlq_u32 ( vpaddlq_u16 ( vpaddlq_u8 ( pop_1) ) ) ;
149- let sums_2 = vpaddlq_u32 ( vpaddlq_u16 ( vpaddlq_u8 ( pop_2) ) ) ;
150- let sums_3 = vpaddlq_u32 ( vpaddlq_u16 ( vpaddlq_u8 ( pop_3) ) ) ;
151-
152- ( vgetq_lane_u64 :: < 0 > ( sums_0)
153- + vgetq_lane_u64 :: < 1 > ( sums_0)
154- + vgetq_lane_u64 :: < 0 > ( sums_1)
155- + vgetq_lane_u64 :: < 1 > ( sums_1)
156- + vgetq_lane_u64 :: < 0 > ( sums_2)
157- + vgetq_lane_u64 :: < 1 > ( sums_2)
158- + vgetq_lane_u64 :: < 0 > ( sums_3)
159- + vgetq_lane_u64 :: < 1 > ( sums_3) ) as usize
160- } ;
161-
162- if remaining < total {
163- return ( remaining, pos, idx) ;
164- }
165-
166- remaining -= total;
167- pos += 512 ;
168- }
169-
170- ( remaining, pos, chunks. len ( ) )
171- }
172-
173- #[ cfg( target_arch = "x86_64" ) ]
174- #[ target_feature( enable = "avx512f,avx512vpopcntdq" ) ]
175- unsafe fn scan_chunks_avx512_vpopcnt (
176- chunks : & [ [ u8 ; 64 ] ] ,
177- mut remaining : usize ,
178- mut pos : usize ,
179- ) -> ( usize , usize , usize ) {
180- use std:: arch:: x86_64:: _mm512_loadu_si512;
181- use std:: arch:: x86_64:: _mm512_popcnt_epi64;
182- use std:: arch:: x86_64:: _mm512_reduce_add_epi64;
183-
184- use vortex_error:: VortexExpect ;
185-
186- for ( idx, chunk) in chunks. iter ( ) . enumerate ( ) {
187- // SAFETY: chunk is exactly 64 bytes. `_mm512_loadu_si512` supports unaligned access.
188- let block = unsafe { _mm512_loadu_si512 ( chunk. as_ptr ( ) . cast ( ) ) } ;
189- let counts = _mm512_popcnt_epi64 ( block) ;
190- let total =
191- usize:: try_from ( _mm512_reduce_add_epi64 ( counts) ) . vortex_expect ( "must fit in usize" ) ;
192-
193- if remaining < total {
194- return ( remaining, pos, idx) ;
195- }
196-
197- remaining -= total;
198- pos += 512 ;
199- }
200-
201- ( remaining, pos, chunks. len ( ) )
93+ dispatch ! ( Level :: new( ) , simd => scan_chunks_simd( simd, chunks, remaining, pos) )
20294}
20395
204- #[ inline]
205- fn scan_chunks_scalar (
96+ #[ simd]
97+ fn scan_chunks_simd < S : Simd > (
98+ simd : S ,
20699 chunks : & [ [ u8 ; 64 ] ] ,
207100 mut remaining : usize ,
208101 mut pos : usize ,
209102) -> ( usize , usize , usize ) {
210103 for ( idx, chunk) in chunks. iter ( ) . enumerate ( ) {
211- let total = count_ones_chunk ( chunk) ;
104+ let words: u64x8 < S > = u8x64:: from_slice ( simd, chunk) . bitcast ( ) ;
105+ let total = usize:: try_from ( words. count_ones ( ) . reduce_sum ( ) )
106+ . vortex_expect ( "chunk popcount fits in usize" ) ;
212107 if remaining < total {
213108 return ( remaining, pos, idx) ;
214109 }
215-
216110 remaining -= total;
217111 pos += 512 ;
218112 }
219-
220113 ( remaining, pos, chunks. len ( ) )
221114}
222115
@@ -295,87 +188,27 @@ fn scan_words_scalar(
295188
296189// ── In-chunk select ─────────────────────────────────────────────────────
297190
298- type SelectInChunk = unsafe fn ( & [ u8 ; 64 ] , usize ) -> usize ;
299-
300191/// Position of the `nth` set bit inside a 64-byte chunk (0-indexed).
301192#[ inline]
302193fn select_in_chunk ( chunk : & [ u8 ; 64 ] , nth : usize ) -> usize {
303- static KERNEL : CpuKernel < SelectInChunk > = CpuKernel :: new ( || {
304- #[ cfg( target_arch = "x86_64" ) ]
305- {
306- if is_x86_feature_detected ! ( "avx512f" )
307- && is_x86_feature_detected ! ( "avx512vpopcntdq" )
308- && is_x86_feature_detected ! ( "avx512vbmi2" )
309- {
310- return select_in_chunk_vbmi2;
311- }
312- }
313- select_in_chunk_scalar
314- } ) ;
315- // SAFETY: the selector only returns kernels that are safe or whose required CPU
316- // features were probed before selection.
317- unsafe { KERNEL . get ( ) ( chunk, nth) }
194+ dispatch ! ( Level :: new( ) , simd => select_in_chunk_simd( simd, chunk, nth) )
318195}
319196
320- #[ cfg( target_arch = "x86_64" ) ]
321- #[ target_feature( enable = "avx512f,avx512vpopcntdq,avx512vbmi2" ) ]
322- unsafe fn select_in_chunk_vbmi2 ( chunk : & [ u8 ; 64 ] , mut nth : usize ) -> usize {
323- use std:: arch:: x86_64:: _mm512_loadu_si512;
324- use std:: arch:: x86_64:: _mm512_popcnt_epi64;
325- use std:: arch:: x86_64:: _mm512_storeu_epi64;
326-
327- use vortex_error:: VortexExpect ;
328-
329- let words = chunk. as_chunks :: < 8 > ( ) . 0 ;
330-
331- // SAFETY: chunk is exactly 64 bytes. `_mm512_loadu_si512` supports unaligned access.
332- let block = unsafe { _mm512_loadu_si512 ( chunk. as_ptr ( ) . cast ( ) ) } ;
333- let counts = _mm512_popcnt_epi64 ( block) ;
334- let mut lane_counts = [ 0_i64 ; 8 ] ;
335-
336- // SAFETY: `lane_counts` has room for all eight i64 lanes.
337- unsafe { _mm512_storeu_epi64 ( lane_counts. as_mut_ptr ( ) , counts) } ;
338-
339- for ( idx, count) in lane_counts. into_iter ( ) . enumerate ( ) {
340- let count = usize:: try_from ( count) . vortex_expect ( "must fit in usize" ) ;
341- if nth < count {
342- return idx * 64 + select_in_word ( u64:: from_le_bytes ( words[ idx] ) , nth) ;
343- }
344- nth -= count;
345- }
346-
347- unreachable ! ( "select_in_chunk: nth exceeds popcount" )
348- }
349-
350- #[ inline]
351- fn select_in_chunk_scalar ( chunk : & [ u8 ; 64 ] , mut nth : usize ) -> usize {
352- let words = chunk. as_chunks :: < 8 > ( ) . 0 ;
353-
354- for ( idx, word) in words. iter ( ) . enumerate ( ) {
355- let word = u64:: from_le_bytes ( * word) ;
356- let count = word. count_ones ( ) as usize ;
197+ #[ simd]
198+ fn select_in_chunk_simd < S : Simd > ( simd : S , chunk : & [ u8 ; 64 ] , mut nth : usize ) -> usize {
199+ let words: [ u64 ; 8 ] = std:: array:: from_fn ( |i| u64:: from_le_bytes ( chunk. as_chunks :: < 8 > ( ) . 0 [ i] ) ) ;
200+ let counts = u64x8:: from_slice ( simd, & words) . count_ones ( ) . to_array ( ) ;
201+ for ( idx, count) in counts. into_iter ( ) . enumerate ( ) {
202+ // Each lane is the popcount of a u64, hence at most 64.
203+ let count = usize:: try_from ( count) . vortex_expect ( "u64 popcount fits in usize" ) ;
357204 if nth < count {
358- return idx * 64 + select_in_word ( word , nth) ;
205+ return idx * 64 + select_in_word ( words [ idx ] , nth) ;
359206 }
360207 nth -= count;
361208 }
362-
363209 unreachable ! ( "select_in_chunk: nth exceeds popcount" )
364210}
365211
366- #[ inline]
367- fn count_ones_chunk ( chunk : & [ u8 ; 64 ] ) -> usize {
368- let words = chunk. as_chunks :: < 8 > ( ) . 0 ;
369- u64:: from_le_bytes ( words[ 0 ] ) . count_ones ( ) as usize
370- + u64:: from_le_bytes ( words[ 1 ] ) . count_ones ( ) as usize
371- + u64:: from_le_bytes ( words[ 2 ] ) . count_ones ( ) as usize
372- + u64:: from_le_bytes ( words[ 3 ] ) . count_ones ( ) as usize
373- + u64:: from_le_bytes ( words[ 4 ] ) . count_ones ( ) as usize
374- + u64:: from_le_bytes ( words[ 5 ] ) . count_ones ( ) as usize
375- + u64:: from_le_bytes ( words[ 6 ] ) . count_ones ( ) as usize
376- + u64:: from_le_bytes ( words[ 7 ] ) . count_ones ( ) as usize
377- }
378-
379212// ── In-word select ──────────────────────────────────────────────────────
380213
381214type SelectInWord = unsafe fn ( u64 , usize ) -> usize ;
0 commit comments