alamb commented on code in PR #11055:
URL: https://github.com/apache/arrow-rs/pull/11055#discussion_r4207958219
##########
arrow-buffer/src/util/bit_util.rs:
##########
@@ -64,23 +64,113 @@ pub fn compress(value: u64, mask: u64) -> u64 {
#[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
{
- let mut mask = mask;
- let mut result = 0_u64;
- let mut dest_bit = 1_u64;
- while mask != 0 {
- // Clear the lowest set bit; the loop-carried dependency is only
- // this two-operation chain, everything else hangs off it
- let rest = mask & (mask - 1);
- let lowest = mask ^ rest;
- let keep = ((value & lowest) != 0) as u64;
- result |= dest_bit & keep.wrapping_neg();
- dest_bit <<= 1;
- mask = rest;
+ compress_with_count(value, mask, mask.count_ones())
+ }
+}
+
+/// Precomputed PEXT for all 4-bit mask/value combinations (256 bytes, one
cache line).
+/// `NIBBLE_PEXT[mask_nibble][value_nibble]` = bits of `value_nibble` at
positions set
+/// in `mask_nibble`, packed into the low bits of the result.
+const NIBBLE_PEXT: [[u8; 16]; 16] = {
+ let mut table = [[0u8; 16]; 16];
+ let mut mask_nibble = 0usize;
+ while mask_nibble < 16 {
+ let mut value_nibble = 0usize;
+ while value_nibble < 16 {
+ let mut packed = 0u8;
+ let mut output_bit = 0u8;
+ let mut remaining_mask = mask_nibble as u8;
+ while remaining_mask != 0 {
+ let selected_bit = remaining_mask &
remaining_mask.wrapping_neg();
+ if value_nibble as u8 & selected_bit != 0 {
+ packed |= 1 << output_bit;
+ }
+ output_bit += 1;
+ remaining_mask &= remaining_mask - 1;
+ }
+ table[mask_nibble][value_nibble] = packed;
+ value_nibble += 1;
+ }
+ mask_nibble += 1;
+ }
+ table
+};
Review Comment:
I think claude got it from https://en.wikipedia.org/wiki/Hacker%27s_Delight
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
