Rich-T-kid commented on code in PR #11322:
URL: https://github.com/apache/arrow-rs/pull/11322#discussion_r4233666716
##########
arrow-buffer/src/util/bit_util.rs:
##########
@@ -78,9 +104,76 @@ pub fn compress(value: u64, mask: u64) -> u64 {
mask = rest;
}
result
+ } else if kept >= 62 {
+ if kept == 64 {
+ return value;
+ }
+ // Remove the highest dropped bit first, so the lower ones stay put.
+ // With nothing left to drop a step keeps every bit, and each step
+ // shifts a zero in at the top.
+ let mut value = value;
+ let mut dropped = !mask;
+ for _ in 0..2 {
+ let below = if dropped == 0 {
+ u64::MAX
+ } else {
+ (1 << dropped.ilog2()) - 1
+ };
+ value = (value & below) | ((value >> 1) & !below);
+ dropped &= below;
+ }
+ value
+ } else {
+ compress_bytes(value, mask)
}
}
+/// `b` in every byte of a `u64`
+#[cfg(any(test, not(all(target_arch = "x86_64", target_feature = "bmi2"))))]
+const fn repeat_byte(b: u8) -> u64 {
+ b as u64 * 0x0101_0101_0101_0101
+}
+
+/// [`compress`] in constant time, a byte at a time and all bytes at once.
+///
+/// Within a byte each kept bit moves down by the number of dropped bits
+/// below it. Written in binary, that distance is at most 7, so three rounds
+/// move by 1, 2 and 4 the bits whose distance has that bit set (the parallel
+/// suffix network, Hacker's Delight 7-4); shifts are masked to stay within
+/// the byte. Byte `j` then lands at the sum of the kept counts of bytes
+/// `0..j`, all eight sums from one multiply by `0x0101..01`.
+#[cfg(any(test, not(all(target_arch = "x86_64", target_feature = "bmi2"))))]
+#[inline]
+fn compress_bytes(value: u64, mask: u64) -> u64 {
+ let mut x = value & mask;
+ let mut zeros = !mask;
+ let mut n = 1;
+ while n < 8 {
+ // The move mask of this round: the parity of the dropped bits
+ // below each bit, in strides of `n`
+ let mut parity = zeros;
+ let mut len = n;
+ while len < 8 {
+ parity ^= (parity << len) & repeat_byte(0xFF << len);
+ len <<= 1;
+ }
+ let q = x & parity;
+ x ^= q ^ ((q >> n) & repeat_byte(0xFF >> n));
+ zeros &= !parity;
+ zeros ^= (zeros >> n) & repeat_byte(0xFF >> n);
+ n <<= 1;
+ }
+ let c = mask - ((mask >> 1) & repeat_byte(0x55));
+ let c = (c & repeat_byte(0x33)) + ((c >> 2) & repeat_byte(0x33));
+ let kept = (c + (c >> 4)) & repeat_byte(0x0F);
+ let below = kept.wrapping_mul(repeat_byte(1)) << 8;
+ let mut result = 0;
+ for j in 0..8 {
+ result |= ((x >> (8 * j)) & 0xFF) << ((below >> (8 * j)) & 0xFF);
+ }
+ result
+}
+
Review Comment:
this is very cool, but can we use more descriptive variable names? bit
manipulation is pretty tricky to follow alone with all the bitwise operands so
variables that can provide context would be greatly appreciated here.
--
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]
