devanbenz commented on code in PR #11322:
URL: https://github.com/apache/arrow-rs/pull/11322#discussion_r4252223270
##########
arrow-buffer/src/util/bit_util.rs:
##########
@@ -78,9 +110,78 @@ 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
Review Comment:
Nice! Thanks for quoting Hacker's 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]
