1use crate::bit_chunk_iterator::BitChunks;
8
9#[inline]
53pub fn compress(value: u64, mask: u64) -> u64 {
54 #[cfg(all(target_arch = "x86_64", target_feature = "bmi2"))]
55 {
56 unsafe { std::arch::x86_64::_pext_u64(value, mask) }
59 }
60
61 #[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
62 {
63 compress_portable(value, mask)
64 }
65}
66
67#[cfg(any(test, not(all(target_arch = "x86_64", target_feature = "bmi2"))))]
78#[inline(always)]
79fn compress_portable(value: u64, mask: u64) -> u64 {
80 let kept = mask.count_ones();
81 if kept <= 2 {
82 let lowest = mask & mask.wrapping_neg();
83 let second = mask ^ lowest;
84 u64::from(value & lowest != 0) | (u64::from(value & second != 0) << 1)
85 } else if kept <= 16 {
86 let mut mask = mask;
87 let mut result = 0_u64;
88 let mut dest_bit = 1_u64;
89 while mask != 0 {
90 let rest = mask & (mask - 1);
93 let lowest = mask ^ rest;
94 let keep = ((value & lowest) != 0) as u64;
95 result |= dest_bit & keep.wrapping_neg();
96 dest_bit <<= 1;
97 mask = rest;
98 }
99 result
100 } else if kept >= 62 {
101 if kept == 64 {
102 return value;
103 }
104 let mut value = value;
108 let mut dropped = !mask;
109 for _ in 0..2 {
110 let below = if dropped == 0 {
111 u64::MAX
112 } else {
113 (1 << dropped.ilog2()) - 1
114 };
115 value = (value & below) | ((value >> 1) & !below);
116 dropped &= below;
117 }
118 value
119 } else {
120 compress_bytes(value, mask)
121 }
122}
123
124#[cfg(any(test, not(all(target_arch = "x86_64", target_feature = "bmi2"))))]
126const fn repeat_byte(b: u8) -> u64 {
127 b as u64 * 0x0101_0101_0101_0101
128}
129
130#[cfg(any(test, not(all(target_arch = "x86_64", target_feature = "bmi2"))))]
139#[inline]
140fn compress_bytes(value: u64, mask: u64) -> u64 {
141 let mut packed = value & mask;
142 let mut dropped = !mask;
143 let mut shift = 1;
144 while shift < 8 {
145 let mut move_mask = dropped;
148 let mut step = shift;
149 while step < 8 {
150 move_mask ^= (move_mask << step) & repeat_byte(0xFF << step);
151 step <<= 1;
152 }
153 let moving = packed & move_mask;
154 packed ^= moving ^ ((moving >> shift) & repeat_byte(0xFF >> shift));
155 dropped &= !move_mask;
156 dropped ^= (dropped >> shift) & repeat_byte(0xFF >> shift);
157 shift <<= 1;
158 }
159 let pairs = mask - ((mask >> 1) & repeat_byte(0x55));
161 let nibbles = (pairs & repeat_byte(0x33)) + ((pairs >> 2) & repeat_byte(0x33));
162 let kept = (nibbles + (nibbles >> 4)) & repeat_byte(0x0F);
163 let dest = kept.wrapping_mul(repeat_byte(1)) << 8;
165 let mut result = 0;
166 for j in 0..8 {
167 result |= ((packed >> (8 * j)) & 0xFF) << ((dest >> (8 * j)) & 0xFF);
168 }
169 result
170}
171
172#[inline]
207pub fn expand(value: u64, mask: u64) -> u64 {
208 #[cfg(all(target_arch = "x86_64", target_feature = "bmi2"))]
209 {
210 unsafe { std::arch::x86_64::_pdep_u64(value, mask) }
213 }
214
215 #[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
216 {
217 let mut value = value;
218 if value == 0 {
219 return 0;
220 }
221
222 let mut zeros = !mask;
223 if zeros.count_ones() <= 32 {
224 while zeros != 0 {
226 let lower = (1_u64 << zeros.trailing_zeros()) - 1;
227 value = (value & lower) | ((value & !lower) << 1);
228 zeros &= zeros - 1;
229 }
230 value
231 } else {
232 let mut output = 0;
233 let mut ones = mask;
234 while ones != 0 {
235 output |= (value & 1) << ones.trailing_zeros();
236 value >>= 1;
237 ones &= ones - 1;
238 }
239 output
240 }
241 }
242}
243
244#[inline]
250pub fn round_upto_multiple_of_64(num: usize) -> usize {
251 num.checked_next_multiple_of(64)
252 .expect("failed to round upto multiple of 64")
253}
254
255pub fn round_upto_power_of_2(num: usize, factor: usize) -> usize {
262 debug_assert!(factor > 0 && factor.is_power_of_two());
263 num.checked_add(factor - 1)
264 .expect("failed to round to next highest power of 2")
265 & !(factor - 1)
266}
267
268#[inline]
274pub fn get_bit(data: &[u8], i: usize) -> bool {
275 data[i / 8] & (1 << (i % 8)) != 0
276}
277
278#[inline]
285pub unsafe fn get_bit_raw(data: *const u8, i: usize) -> bool {
286 unsafe { (*data.add(i / 8) & (1 << (i % 8))) != 0 }
287}
288
289#[inline]
295pub fn set_bit(data: &mut [u8], i: usize) {
296 data[i / 8] |= 1 << (i % 8);
297}
298
299#[inline]
306pub unsafe fn set_bit_raw(data: *mut u8, i: usize) {
307 unsafe {
308 *data.add(i / 8) |= 1 << (i % 8);
309 }
310}
311
312#[inline]
318pub fn unset_bit(data: &mut [u8], i: usize) {
319 data[i / 8] &= !(1 << (i % 8));
320}
321
322#[inline]
329pub unsafe fn unset_bit_raw(data: *mut u8, i: usize) {
330 unsafe {
331 *data.add(i / 8) &= !(1 << (i % 8));
332 }
333}
334
335#[inline]
337pub fn ceil(value: usize, divisor: usize) -> usize {
338 value.div_ceil(divisor)
339}
340
341#[inline]
343pub(crate) fn read_u64(input: &[u8]) -> u64 {
344 let len = input.len().min(8);
345 let mut buf = [0_u8; 8];
346 buf[..len].copy_from_slice(input);
347 u64::from_le_bytes(buf)
348}
349
350#[inline]
368pub(crate) fn read_up_to_byte_from_offset(
369 slice: &[u8],
370 number_of_bits_to_read: usize,
371 bit_offset: usize,
372) -> u8 {
373 assert!(number_of_bits_to_read < 8, "can read up to 8 bits only");
374 assert!(bit_offset < 8, "bit offset must be less than 8");
375 assert_ne!(
376 number_of_bits_to_read, 0,
377 "number of bits to read must be greater than 0"
378 );
379 assert_ne!(slice.len(), 0, "slice must not be empty");
380
381 let number_of_bytes_to_read = ceil(number_of_bits_to_read + bit_offset, 8);
382
383 assert!(slice.len() >= number_of_bytes_to_read, "slice is too small");
385
386 let mut bits = slice[0] >> bit_offset;
387 for (i, &byte) in slice
388 .iter()
389 .take(number_of_bytes_to_read)
390 .enumerate()
391 .skip(1)
392 {
393 bits |= byte << (i * 8 - bit_offset);
394 }
395
396 bits & ((1 << number_of_bits_to_read) - 1)
397}
398
399pub fn apply_bitwise_binary_op<F>(
446 left: &mut [u8],
447 left_offset_in_bits: usize,
448 right: impl AsRef<[u8]>,
449 right_offset_in_bits: usize,
450 len_in_bits: usize,
451 mut op: F,
452) where
453 F: FnMut(u64, u64) -> u64,
454{
455 if len_in_bits == 0 {
456 return;
457 }
458
459 let bit_offset = left_offset_in_bits % 8;
461
462 let is_mutable_buffer_byte_aligned = bit_offset == 0;
463
464 if is_mutable_buffer_byte_aligned {
465 byte_aligned_bitwise_bin_op_helper(
466 left,
467 left_offset_in_bits,
468 right,
469 right_offset_in_bits,
470 len_in_bits,
471 op,
472 );
473 } else {
474 let bits_to_next_byte = (8 - bit_offset)
476 .min(len_in_bits);
479
480 {
481 let right_byte_offset = right_offset_in_bits / 8;
482
483 let right_first_byte = crate::util::bit_util::read_up_to_byte_from_offset(
485 &right.as_ref()[right_byte_offset..],
486 bits_to_next_byte,
487 right_offset_in_bits % 8,
489 );
490
491 align_to_byte(
492 left,
493 &mut |left| op(left, right_first_byte as u64),
495 left_offset_in_bits,
496 bits_to_next_byte,
497 );
498 }
499
500 let offset_in_bits = left_offset_in_bits + bits_to_next_byte;
501 let right_offset_in_bits = right_offset_in_bits + bits_to_next_byte;
502 let len_in_bits = len_in_bits.saturating_sub(bits_to_next_byte);
503
504 if len_in_bits == 0 {
505 return;
506 }
507
508 byte_aligned_bitwise_bin_op_helper(
510 left,
511 offset_in_bits,
512 right,
513 right_offset_in_bits,
514 len_in_bits,
515 op,
516 );
517 }
518}
519
520pub fn apply_bitwise_unary_op<F>(
560 buffer: &mut [u8],
561 offset_in_bits: usize,
562 len_in_bits: usize,
563 mut op: F,
564) where
565 F: FnMut(u64) -> u64,
566{
567 if len_in_bits == 0 {
568 return;
569 }
570
571 let left_bit_offset = offset_in_bits % 8;
573
574 let is_mutable_buffer_byte_aligned = left_bit_offset == 0;
575
576 if is_mutable_buffer_byte_aligned {
577 byte_aligned_bitwise_unary_op_helper(buffer, offset_in_bits, len_in_bits, op);
578 } else {
579 align_to_byte(buffer, &mut op, offset_in_bits, len_in_bits);
580
581 let bits_to_next_byte = 8 - left_bit_offset;
583
584 let offset_in_bits = offset_in_bits + bits_to_next_byte;
585 let len_in_bits = len_in_bits.saturating_sub(bits_to_next_byte);
586
587 if len_in_bits == 0 {
588 return;
589 }
590
591 byte_aligned_bitwise_unary_op_helper(buffer, offset_in_bits, len_in_bits, op);
593 }
594}
595
596#[inline]
610fn byte_aligned_bitwise_bin_op_helper<F>(
611 left: &mut [u8],
612 left_offset_in_bits: usize,
613 right: impl AsRef<[u8]>,
614 right_offset_in_bits: usize,
615 len_in_bits: usize,
616 mut op: F,
617) where
618 F: FnMut(u64, u64) -> u64,
619{
620 assert_eq!(
622 left_offset_in_bits % 8,
623 0,
624 "offset_in_bits must be byte aligned"
625 );
626
627 let (complete_u64_chunks, remainder_bytes) =
629 U64UnalignedSlice::split(left, left_offset_in_bits, len_in_bits);
630
631 let right_chunks = BitChunks::new(right.as_ref(), right_offset_in_bits, len_in_bits);
632 assert_eq!(
633 self::ceil(right_chunks.remainder_len(), 8),
634 remainder_bytes.len()
635 );
636
637 let right_chunks_iter = right_chunks.iter();
638 assert_eq!(right_chunks_iter.len(), complete_u64_chunks.len());
639
640 complete_u64_chunks.zip_modify(right_chunks_iter, &mut op);
642
643 if right_chunks.remainder_len() > 0 {
645 handle_mutable_buffer_remainder(
646 &mut op,
647 remainder_bytes,
648 right_chunks.remainder_bits(),
649 right_chunks.remainder_len(),
650 )
651 }
652}
653
654#[inline]
666fn byte_aligned_bitwise_unary_op_helper<F>(
667 buffer: &mut [u8],
668 offset_in_bits: usize,
669 len_in_bits: usize,
670 mut op: F,
671) where
672 F: FnMut(u64) -> u64,
673{
674 assert_eq!(offset_in_bits % 8, 0, "offset_in_bits must be byte aligned");
676
677 let remainder_len = len_in_bits % 64;
678
679 let (complete_u64_chunks, remainder_bytes) =
680 U64UnalignedSlice::split(buffer, offset_in_bits, len_in_bits);
681
682 assert_eq!(self::ceil(remainder_len, 8), remainder_bytes.len());
683
684 complete_u64_chunks.apply_unary_op(&mut op);
686
687 if remainder_len > 0 {
689 handle_mutable_buffer_remainder_unary(&mut op, remainder_bytes, remainder_len)
690 }
691}
692
693fn align_to_byte<F>(
707 buffer: &mut [u8],
708 op: &mut F,
709 offset_in_bits: usize,
710 remaining_len_in_bits: usize,
711) where
712 F: FnMut(u64) -> u64,
713{
714 let byte_offset = offset_in_bits / 8;
715 let bit_offset = offset_in_bits % 8;
716
717 debug_assert_ne!(bit_offset, 0, "offset_in_bits must not be byte aligned");
719
720 let first_byte: u8 = buffer[byte_offset];
722
723 let relevant_first_byte = first_byte >> bit_offset;
725
726 let result_first_byte = op(relevant_first_byte as u64) as u8;
728
729 let result_first_byte = result_first_byte << bit_offset;
731
732 let bits_in_this_byte = (8 - bit_offset).min(remaining_len_in_bits);
739 let write_mask = ((1u8 << bits_in_this_byte) - 1) << bit_offset;
740
741 let result_first_byte = (first_byte & !write_mask) | (result_first_byte & write_mask);
742
743 buffer[byte_offset] = result_first_byte;
745}
746
747struct U64UnalignedSlice<'a> {
759 ptr: *mut u64,
763
764 len: usize,
766
767 _marker: std::marker::PhantomData<&'a u8>,
769}
770
771impl<'a> U64UnalignedSlice<'a> {
772 fn split(
777 buffer: &'a mut [u8],
778 offset_in_bits: usize,
779 len_in_bits: usize,
780 ) -> (Self, &'a mut [u8]) {
781 let left_buffer_mut: &mut [u8] = {
783 let last_offset = self::ceil(offset_in_bits + len_in_bits, 8);
784 assert!(last_offset <= buffer.len());
785
786 let byte_offset = offset_in_bits / 8;
787
788 &mut buffer[byte_offset..last_offset]
789 };
790
791 let number_of_u64_we_can_fit = len_in_bits / (u64::BITS as usize);
792
793 let u64_len_in_bytes = number_of_u64_we_can_fit * size_of::<u64>();
795
796 assert!(u64_len_in_bytes <= left_buffer_mut.len());
797 let (bytes_for_u64, remainder) = left_buffer_mut.split_at_mut(u64_len_in_bytes);
798
799 #[expect(
800 clippy::cast_ptr_alignment,
801 reason = "`U64UnalignedSlice` only reads and writes through the unaligned methods"
802 )]
803 let ptr = bytes_for_u64.as_mut_ptr().cast::<u64>();
804
805 let this = Self {
806 ptr,
807 len: number_of_u64_we_can_fit,
808 _marker: std::marker::PhantomData,
809 };
810
811 (this, remainder)
812 }
813
814 fn len(&self) -> usize {
815 self.len
816 }
817
818 fn zip_modify(
821 mut self,
822 mut zip_iter: impl ExactSizeIterator<Item = u64>,
823 mut map: impl FnMut(u64, u64) -> u64,
824 ) {
825 assert_eq!(self.len, zip_iter.len());
826
827 if let Some(right) = zip_iter.next() {
832 unsafe {
835 self.apply_bin_op(right, &mut map);
836 }
837
838 }
840
841 for right in zip_iter {
842 self.ptr = unsafe { self.ptr.add(1) };
846
847 unsafe {
849 self.apply_bin_op(right, &mut map);
850 }
851
852 }
854 }
855
856 #[inline]
862 unsafe fn apply_bin_op(&mut self, right: u64, mut map: impl FnMut(u64, u64) -> u64) {
863 let current_input = unsafe {
866 self.ptr
867 .read_unaligned()
869 .to_le()
872 };
873
874 let combined = map(current_input, right);
875
876 unsafe { self.ptr.write_unaligned(combined) }
881 }
882
883 fn apply_unary_op(mut self, mut map: impl FnMut(u64) -> u64) {
885 if self.len == 0 {
886 return;
887 }
888
889 unsafe {
896 self.apply_bin_op(0, &mut |left, _| map(left));
898
899 }
901
902 for _ in 1..self.len {
903 self.ptr = unsafe { self.ptr.add(1) };
907
908 unsafe {
910 self.apply_bin_op(0, &mut |left, _| map(left));
912 }
913
914 }
916 }
917}
918
919#[inline]
932fn handle_mutable_buffer_remainder<F>(
933 op: &mut F,
934 start_remainder_mut_slice: &mut [u8],
935 right_remainder_bits: u64,
936 remainder_len: usize,
937) where
938 F: FnMut(u64, u64) -> u64,
939{
940 let left_remainder_bits = get_remainder_bits(start_remainder_mut_slice, remainder_len);
942
943 let rem = op(left_remainder_bits, right_remainder_bits);
945
946 set_remainder_bits(start_remainder_mut_slice, rem, remainder_len);
948}
949
950#[inline]
962fn set_remainder_bits(start_remainder_mut_slice: &mut [u8], rem: u64, remainder_len: usize) {
963 assert_ne!(
964 start_remainder_mut_slice.len(),
965 0,
966 "start_remainder_mut_slice must not be empty"
967 );
968 assert!(remainder_len < 64, "remainder_len must be less than 64");
969
970 assert_eq!(
973 start_remainder_mut_slice.len(),
974 self::ceil(remainder_len, 8),
975 "start_remainder_mut_slice length must be equal to ceil(remainder_len, 8)"
976 );
977
978 let rem = {
984 let current = start_remainder_mut_slice
989 .last()
990 .unwrap();
992
993 let current = (*current as u64) << ((start_remainder_mut_slice.len() - 1) * 8);
996
997 let inside_remainder_mask = (1 << remainder_len) - 1;
1000 let outside_remainder_mask = !inside_remainder_mask;
1003
1004 let current = current & outside_remainder_mask;
1006
1007 let rem = rem & inside_remainder_mask;
1009
1010 current | rem
1012 };
1013
1014 {
1016 let remainder_bytes = start_remainder_mut_slice.len();
1017
1018 let rem = &rem.to_le_bytes()[0..remainder_bytes];
1020
1021 let src = rem.as_ptr();
1025 unsafe {
1029 std::ptr::copy_nonoverlapping(
1030 src,
1031 start_remainder_mut_slice.as_mut_ptr(),
1032 remainder_bytes,
1033 )
1034 };
1035 }
1036}
1037
1038#[inline]
1051fn get_remainder_bits(remainder: &[u8], remainder_len: usize) -> u64 {
1052 assert!(remainder.len() < 64, "remainder_len must be less than 64");
1053 assert_eq!(
1054 remainder.len(),
1055 self::ceil(remainder_len, 8),
1056 "remainder and remainder len ceil must be the same"
1057 );
1058
1059 let bits = remainder
1060 .iter()
1061 .enumerate()
1062 .fold(0_u64, |acc, (index, &byte)| {
1063 acc | ((byte as u64) << (index * 8))
1064 });
1065
1066 bits & ((1 << remainder_len) - 1)
1067}
1068
1069#[inline]
1080fn handle_mutable_buffer_remainder_unary<F>(
1081 op: &mut F,
1082 start_remainder_mut: &mut [u8],
1083 remainder_len: usize,
1084) where
1085 F: FnMut(u64) -> u64,
1086{
1087 let left_remainder_bits = get_remainder_bits(start_remainder_mut, remainder_len);
1089
1090 let rem = op(left_remainder_bits);
1092
1093 set_remainder_bits(start_remainder_mut, rem, remainder_len);
1095}
1096
1097#[cfg(test)]
1098mod tests {
1099 use std::collections::HashSet;
1100
1101 use super::*;
1102 use crate::bit_iterator::BitIterator;
1103 use crate::{BooleanBuffer, BooleanBufferBuilder, MutableBuffer};
1104 use rand::rngs::StdRng;
1105 use rand::{RngExt, SeedableRng};
1106
1107 fn compress_reference(value: u64, mask: u64) -> u64 {
1110 (0..64)
1111 .filter(|&i| (mask >> i) & 1 == 1)
1112 .enumerate()
1113 .map(|(dest, i)| ((value >> i) & 1) << dest)
1114 .sum()
1115 }
1116
1117 #[test]
1118 fn test_compress() {
1119 assert_eq!(compress(0b1010, 0b1111), 0b1010);
1120 assert_eq!(compress(0b1010, 0b1010), 0b11);
1121 assert_eq!(compress(0b1010, 0b0101), 0);
1122 assert_eq!(compress(u64::MAX, 0), 0);
1123 assert_eq!(compress(0, u64::MAX), 0);
1124 assert_eq!(compress(u64::MAX, u64::MAX), u64::MAX);
1125
1126 let mut rng = StdRng::seed_from_u64(42);
1129 for _ in 0..1024 {
1130 let (value, mask): (u64, u64) = rng.random();
1131 assert_eq!(
1132 compress(value, mask),
1133 compress_reference(value, mask),
1134 "value={value:#x} mask={mask:#x}"
1135 );
1136 }
1137 }
1138
1139 #[test]
1140 fn test_compress_portable() {
1141 let check = |value: u64, mask: u64| {
1145 let want = compress_reference(value, mask);
1146 let kept = mask.count_ones();
1147 assert_eq!(
1148 compress_portable(value, mask),
1149 want,
1150 "value={value:#x} mask={mask:#x} kept={kept}"
1151 );
1152 };
1153 let mut rng = StdRng::seed_from_u64(42);
1154
1155 let value: u64 = rng.random();
1157 check(value, 0);
1158 check(value, u64::MAX);
1159 for i in 0..64 {
1160 check(value, 1 << i);
1161 check(value, !(1 << i));
1162 for j in i + 1..64 {
1163 let two = (1 << i) | (1 << j);
1164 check(value, two);
1165 check(value, !two);
1166 }
1167 }
1168
1169 for _ in 0..4096 {
1172 let value: u64 = rng.random();
1173 let mut sparse = u64::MAX;
1174 let mut dense = 0;
1175 for _ in 0..8 {
1176 let word: u64 = rng.random();
1177 sparse &= word;
1178 dense |= word;
1179 check(value, sparse);
1180 check(value, dense);
1181 }
1182 let kept = rng.random_range(0..=64);
1184 let mut mask = 0_u64;
1185 while mask.count_ones() < kept {
1186 mask |= 1 << rng.random_range(0..64);
1187 }
1188 check(value, mask);
1189 }
1190 }
1191
1192 #[test]
1193 fn test_expand() {
1194 fn reference(values: u64, mask: u64) -> u64 {
1195 let mut expected = 0;
1196 let mut input_idx = 0;
1197 for output_idx in 0..64 {
1198 if mask & (1 << output_idx) != 0 {
1199 expected |= ((values >> input_idx) & 1) << output_idx;
1200 input_idx += 1;
1201 }
1202 }
1203 expected
1204 }
1205
1206 assert_eq!(expand(0b1010, 0b1111), 0b1010);
1207 assert_eq!(expand(0b11, 0b1010), 0b1010);
1208 assert_eq!(expand(u64::MAX, 0), 0);
1209 assert_eq!(expand(0, u64::MAX), 0);
1210 assert_eq!(expand(0, 0x5555_5555_5555_5555), 0);
1211 assert_eq!(expand(u64::MAX, u64::MAX), u64::MAX);
1212
1213 let mut rng = StdRng::seed_from_u64(0x2b7e_1516_28ae_d2a6);
1214
1215 for bit in 0..64 {
1217 for mask in [u64::MAX, !(1 << bit), 1 << bit, 0] {
1218 for _ in 0..16 {
1219 let values = rng.random::<u64>();
1220 assert_eq!(expand(values, mask), reference(values, mask), "{mask:#x}");
1221 }
1222 }
1223 }
1224
1225 for _ in 0..20_000 {
1228 let density = rng.random_range(0.0..=1.0);
1229 let mask = (0..64).fold(0_u64, |mask, bit| {
1230 mask | ((rng.random_bool(density) as u64) << bit)
1231 });
1232 let values = rng.random::<u64>();
1233 assert_eq!(expand(compress(values, mask), mask), values & mask);
1234 assert_eq!(expand(values, mask), reference(values, mask), "{mask:#x}");
1235 }
1236 }
1237
1238 #[test]
1239 fn test_round_upto_multiple_of_64() {
1240 assert_eq!(0, round_upto_multiple_of_64(0));
1241 assert_eq!(64, round_upto_multiple_of_64(1));
1242 assert_eq!(64, round_upto_multiple_of_64(63));
1243 assert_eq!(64, round_upto_multiple_of_64(64));
1244 assert_eq!(128, round_upto_multiple_of_64(65));
1245 assert_eq!(192, round_upto_multiple_of_64(129));
1246 }
1247
1248 #[test]
1249 #[should_panic(expected = "failed to round upto multiple of 64")]
1250 fn test_round_upto_multiple_of_64_panic() {
1251 let _ = round_upto_multiple_of_64(usize::MAX);
1252 }
1253
1254 #[test]
1255 #[should_panic(expected = "failed to round to next highest power of 2")]
1256 fn test_round_upto_panic() {
1257 let _ = round_upto_power_of_2(usize::MAX, 2);
1258 }
1259
1260 #[test]
1261 fn test_get_bit() {
1262 assert!(get_bit(&[0b00001101], 0));
1264 assert!(!get_bit(&[0b00001101], 1));
1265 assert!(get_bit(&[0b00001101], 2));
1266 assert!(get_bit(&[0b00001101], 3));
1267
1268 assert!(get_bit(&[0b01001001, 0b01010010], 0));
1270 assert!(!get_bit(&[0b01001001, 0b01010010], 1));
1271 assert!(!get_bit(&[0b01001001, 0b01010010], 2));
1272 assert!(get_bit(&[0b01001001, 0b01010010], 3));
1273 assert!(!get_bit(&[0b01001001, 0b01010010], 4));
1274 assert!(!get_bit(&[0b01001001, 0b01010010], 5));
1275 assert!(get_bit(&[0b01001001, 0b01010010], 6));
1276 assert!(!get_bit(&[0b01001001, 0b01010010], 7));
1277 assert!(!get_bit(&[0b01001001, 0b01010010], 8));
1278 assert!(get_bit(&[0b01001001, 0b01010010], 9));
1279 assert!(!get_bit(&[0b01001001, 0b01010010], 10));
1280 assert!(!get_bit(&[0b01001001, 0b01010010], 11));
1281 assert!(get_bit(&[0b01001001, 0b01010010], 12));
1282 assert!(!get_bit(&[0b01001001, 0b01010010], 13));
1283 assert!(get_bit(&[0b01001001, 0b01010010], 14));
1284 assert!(!get_bit(&[0b01001001, 0b01010010], 15));
1285 }
1286
1287 pub fn seedable_rng() -> StdRng {
1288 StdRng::seed_from_u64(42)
1289 }
1290
1291 #[test]
1292 fn test_get_bit_raw() {
1293 const NUM_BYTE: usize = 10;
1294 let mut buf = [0; NUM_BYTE];
1295 let mut expected = vec![];
1296 let mut rng = seedable_rng();
1297 for i in 0..8 * NUM_BYTE {
1298 let b = rng.random_bool(0.5);
1299 expected.push(b);
1300 if b {
1301 set_bit(&mut buf[..], i)
1302 }
1303 }
1304
1305 let raw_ptr = buf.as_ptr();
1306 for (i, b) in expected.iter().enumerate() {
1307 unsafe {
1308 assert_eq!(*b, get_bit_raw(raw_ptr, i));
1309 }
1310 }
1311 }
1312
1313 #[test]
1314 fn test_set_bit() {
1315 let mut b = [0b00000010];
1316 set_bit(&mut b, 0);
1317 assert_eq!([0b00000011], b);
1318 set_bit(&mut b, 1);
1319 assert_eq!([0b00000011], b);
1320 set_bit(&mut b, 7);
1321 assert_eq!([0b10000011], b);
1322 }
1323
1324 #[test]
1325 fn test_unset_bit() {
1326 let mut b = [0b11111101];
1327 unset_bit(&mut b, 0);
1328 assert_eq!([0b11111100], b);
1329 unset_bit(&mut b, 1);
1330 assert_eq!([0b11111100], b);
1331 unset_bit(&mut b, 7);
1332 assert_eq!([0b01111100], b);
1333 }
1334
1335 #[test]
1336 fn test_set_bit_raw() {
1337 const NUM_BYTE: usize = 10;
1338 let mut buf = vec![0; NUM_BYTE];
1339 let mut expected = vec![];
1340 let mut rng = seedable_rng();
1341 for i in 0..8 * NUM_BYTE {
1342 let b = rng.random_bool(0.5);
1343 expected.push(b);
1344 if b {
1345 unsafe {
1346 set_bit_raw(buf.as_mut_ptr(), i);
1347 }
1348 }
1349 }
1350
1351 let raw_ptr = buf.as_ptr();
1352 for (i, b) in expected.iter().enumerate() {
1353 unsafe {
1354 assert_eq!(*b, get_bit_raw(raw_ptr, i));
1355 }
1356 }
1357 }
1358
1359 #[test]
1360 fn test_unset_bit_raw() {
1361 const NUM_BYTE: usize = 10;
1362 let mut buf = vec![255; NUM_BYTE];
1363 let mut expected = vec![];
1364 let mut rng = seedable_rng();
1365 for i in 0..8 * NUM_BYTE {
1366 let b = rng.random_bool(0.5);
1367 expected.push(b);
1368 if !b {
1369 unsafe {
1370 unset_bit_raw(buf.as_mut_ptr(), i);
1371 }
1372 }
1373 }
1374
1375 let raw_ptr = buf.as_ptr();
1376 for (i, b) in expected.iter().enumerate() {
1377 unsafe {
1378 assert_eq!(*b, get_bit_raw(raw_ptr, i));
1379 }
1380 }
1381 }
1382
1383 #[test]
1384 fn test_get_set_bit_roundtrip() {
1385 const NUM_BYTES: usize = 10;
1386 const NUM_SETS: usize = 10;
1387
1388 let mut buffer: [u8; NUM_BYTES * 8] = [0; NUM_BYTES * 8];
1389 let mut v = HashSet::new();
1390 let mut rng = seedable_rng();
1391 for _ in 0..NUM_SETS {
1392 let offset = rng.random_range(0..8 * NUM_BYTES);
1393 v.insert(offset);
1394 set_bit(&mut buffer[..], offset);
1395 }
1396 for i in 0..NUM_BYTES * 8 {
1397 assert_eq!(v.contains(&i), get_bit(&buffer[..], i));
1398 }
1399 }
1400
1401 #[test]
1402 fn test_ceil() {
1403 assert_eq!(ceil(0, 1), 0);
1404 assert_eq!(ceil(1, 1), 1);
1405 assert_eq!(ceil(1, 2), 1);
1406 assert_eq!(ceil(1, 8), 1);
1407 assert_eq!(ceil(7, 8), 1);
1408 assert_eq!(ceil(8, 8), 1);
1409 assert_eq!(ceil(9, 8), 2);
1410 assert_eq!(ceil(9, 9), 1);
1411 assert_eq!(ceil(10000000000, 10), 1000000000);
1412 assert_eq!(ceil(10, 10000000000), 1);
1413 assert_eq!(ceil(10000000000, 1000000000), 10);
1414 }
1415
1416 #[test]
1417 fn test_read_up_to() {
1418 let all_ones = &[0b10111001, 0b10001100];
1419
1420 for (bit_offset, expected) in [
1421 (0, 0b00000001),
1422 (1, 0b00000000),
1423 (2, 0b00000000),
1424 (3, 0b00000001),
1425 (4, 0b00000001),
1426 (5, 0b00000001),
1427 (6, 0b00000000),
1428 (7, 0b00000001),
1429 ] {
1430 let result = read_up_to_byte_from_offset(all_ones, 1, bit_offset);
1431 assert_eq!(
1432 result, expected,
1433 "failed at bit_offset {bit_offset}. result, expected:\n{result:08b}\n{expected:08b}"
1434 );
1435 }
1436
1437 for (bit_offset, expected) in [
1438 (0, 0b00000001),
1439 (1, 0b00000000),
1440 (2, 0b00000010),
1441 (3, 0b00000011),
1442 (4, 0b00000011),
1443 (5, 0b00000001),
1444 (6, 0b00000010),
1445 (7, 0b00000001),
1446 ] {
1447 let result = read_up_to_byte_from_offset(all_ones, 2, bit_offset);
1448 assert_eq!(
1449 result, expected,
1450 "failed at bit_offset {bit_offset}. result, expected:\n{result:08b}\n{expected:08b}"
1451 );
1452 }
1453
1454 for (bit_offset, expected) in [
1455 (0, 0b00111001),
1456 (1, 0b00011100),
1457 (2, 0b00101110),
1458 (3, 0b00010111),
1459 (4, 0b00001011),
1460 (5, 0b00100101),
1461 (6, 0b00110010),
1462 (7, 0b00011001),
1463 ] {
1464 let result = read_up_to_byte_from_offset(all_ones, 6, bit_offset);
1465 assert_eq!(
1466 result, expected,
1467 "failed at bit_offset {bit_offset}. result, expected:\n{result:08b}\n{expected:08b}"
1468 );
1469 }
1470
1471 for (bit_offset, expected) in [
1472 (0, 0b00111001),
1473 (1, 0b01011100),
1474 (2, 0b00101110),
1475 (3, 0b00010111),
1476 (4, 0b01001011),
1477 (5, 0b01100101),
1478 (6, 0b00110010),
1479 (7, 0b00011001),
1480 ] {
1481 let result = read_up_to_byte_from_offset(all_ones, 7, bit_offset);
1482 assert_eq!(
1483 result, expected,
1484 "failed at bit_offset {bit_offset}. result, expected:\n{result:08b}\n{expected:08b}"
1485 );
1486 }
1487 }
1488
1489 fn test_mutable_buffer_bin_op_helper<F, G>(
1492 left_data: &[bool],
1493 right_data: &[bool],
1494 left_offset_in_bits: usize,
1495 right_offset_in_bits: usize,
1496 len_in_bits: usize,
1497 op: F,
1498 mut expected_op: G,
1499 ) where
1500 F: FnMut(u64, u64) -> u64,
1501 G: FnMut(bool, bool) -> bool,
1502 {
1503 let mut left_buffer = BooleanBufferBuilder::new(len_in_bits);
1504 left_buffer.append_slice(left_data);
1505 let right_buffer = BooleanBuffer::from(right_data);
1506
1507 let expected: Vec<bool> = left_data
1508 .iter()
1509 .skip(left_offset_in_bits)
1510 .zip(right_data.iter().skip(right_offset_in_bits))
1511 .take(len_in_bits)
1512 .map(|(l, r)| expected_op(*l, *r))
1513 .collect();
1514
1515 let before = left_buffer.as_slice().to_vec();
1516
1517 apply_bitwise_binary_op(
1518 left_buffer.as_slice_mut(),
1519 left_offset_in_bits,
1520 right_buffer.inner(),
1521 right_offset_in_bits,
1522 len_in_bits,
1523 op,
1524 );
1525
1526 let result: Vec<bool> =
1527 BitIterator::new(left_buffer.as_slice(), left_offset_in_bits, len_in_bits).collect();
1528
1529 assert_eq!(
1530 result, expected,
1531 "Failed with left_offset={left_offset_in_bits}, right_offset={right_offset_in_bits}, len={len_in_bits}"
1532 );
1533
1534 assert_bits_outside_range_preserved(
1535 &before,
1536 left_buffer.as_slice(),
1537 left_offset_in_bits,
1538 len_in_bits,
1539 &format!(
1540 "left_offset={left_offset_in_bits}, right_offset={right_offset_in_bits}, len={len_in_bits}"
1541 ),
1542 );
1543 }
1544
1545 fn assert_bits_outside_range_preserved(
1548 before: &[u8],
1549 after: &[u8],
1550 offset_in_bits: usize,
1551 len_in_bits: usize,
1552 context: &str,
1553 ) {
1554 assert_eq!(before.len(), after.len());
1555 for i in 0..before.len() * 8 {
1556 if i >= offset_in_bits && i < offset_in_bits + len_in_bits {
1557 continue;
1558 }
1559 assert_eq!(
1560 get_bit(before, i),
1561 get_bit(after, i),
1562 "bit {i} outside the requested range was modified ({context})"
1563 );
1564 }
1565 }
1566
1567 fn test_mutable_buffer_unary_op_helper<F, G>(
1570 data: &[bool],
1571 offset_in_bits: usize,
1572 len_in_bits: usize,
1573 op: F,
1574 mut expected_op: G,
1575 ) where
1576 F: FnMut(u64) -> u64,
1577 G: FnMut(bool) -> bool,
1578 {
1579 let mut buffer = BooleanBufferBuilder::new(len_in_bits);
1580 buffer.append_slice(data);
1581
1582 let expected: Vec<bool> = data
1583 .iter()
1584 .skip(offset_in_bits)
1585 .take(len_in_bits)
1586 .map(|b| expected_op(*b))
1587 .collect();
1588
1589 let before = buffer.as_slice().to_vec();
1590
1591 apply_bitwise_unary_op(buffer.as_slice_mut(), offset_in_bits, len_in_bits, op);
1592
1593 let result: Vec<bool> =
1594 BitIterator::new(buffer.as_slice(), offset_in_bits, len_in_bits).collect();
1595
1596 assert_eq!(
1597 result, expected,
1598 "Failed with offset={offset_in_bits}, len={len_in_bits}"
1599 );
1600
1601 assert_bits_outside_range_preserved(
1602 &before,
1603 buffer.as_slice(),
1604 offset_in_bits,
1605 len_in_bits,
1606 &format!("offset={offset_in_bits}, len={len_in_bits}"),
1607 );
1608 }
1609
1610 fn create_test_data(len: usize) -> (Vec<bool>, Vec<bool>) {
1612 let mut rng = rand::rng();
1613 let left: Vec<bool> = (0..len).map(|_| rng.random_bool(0.5)).collect();
1614 let right: Vec<bool> = (0..len).map(|_| rng.random_bool(0.5)).collect();
1615 (left, right)
1616 }
1617
1618 fn test_all_binary_ops(
1620 left_data: &[bool],
1621 right_data: &[bool],
1622 left_offset_in_bits: usize,
1623 right_offset_in_bits: usize,
1624 len_in_bits: usize,
1625 ) {
1626 test_mutable_buffer_bin_op_helper(
1628 left_data,
1629 right_data,
1630 left_offset_in_bits,
1631 right_offset_in_bits,
1632 len_in_bits,
1633 |a, b| a & b,
1634 |a, b| a & b,
1635 );
1636
1637 test_mutable_buffer_bin_op_helper(
1639 left_data,
1640 right_data,
1641 left_offset_in_bits,
1642 right_offset_in_bits,
1643 len_in_bits,
1644 |a, b| a | b,
1645 |a, b| a | b,
1646 );
1647
1648 test_mutable_buffer_bin_op_helper(
1650 left_data,
1651 right_data,
1652 left_offset_in_bits,
1653 right_offset_in_bits,
1654 len_in_bits,
1655 |a, b| a ^ b,
1656 |a, b| a ^ b,
1657 );
1658 }
1659
1660 #[test]
1663 fn test_binary_ops_less_than_byte() {
1664 let (left, right) = create_test_data(4);
1665 test_all_binary_ops(&left, &right, 0, 0, 4);
1666 }
1667
1668 #[test]
1669 fn test_binary_ops_less_than_byte_across_boundary() {
1670 let (left, right) = create_test_data(16);
1671 test_all_binary_ops(&left, &right, 6, 6, 4);
1672 }
1673
1674 #[test]
1675 fn test_binary_ops_exactly_byte() {
1676 let (left, right) = create_test_data(16);
1677 test_all_binary_ops(&left, &right, 0, 0, 8);
1678 }
1679
1680 #[test]
1681 fn test_binary_ops_more_than_byte_less_than_u64() {
1682 let (left, right) = create_test_data(64);
1683 test_all_binary_ops(&left, &right, 0, 0, 32);
1684 }
1685
1686 #[test]
1687 fn test_binary_ops_exactly_u64() {
1688 let (left, right) = create_test_data(180);
1689 test_all_binary_ops(&left, &right, 0, 0, 64);
1690 test_all_binary_ops(&left, &right, 64, 9, 64);
1691 test_all_binary_ops(&left, &right, 8, 100, 64);
1692 test_all_binary_ops(&left, &right, 1, 15, 64);
1693 test_all_binary_ops(&left, &right, 12, 10, 64);
1694 test_all_binary_ops(&left, &right, 180 - 64, 2, 64);
1695 }
1696
1697 #[test]
1698 fn test_binary_ops_more_than_u64_not_multiple() {
1699 let (left, right) = create_test_data(200);
1700 test_all_binary_ops(&left, &right, 0, 0, 100);
1701 }
1702
1703 #[test]
1704 fn test_binary_ops_exactly_multiple_u64() {
1705 let (left, right) = create_test_data(256);
1706 test_all_binary_ops(&left, &right, 0, 0, 128);
1707 }
1708
1709 #[test]
1710 fn test_binary_ops_more_than_multiple_u64() {
1711 let (left, right) = create_test_data(300);
1712 test_all_binary_ops(&left, &right, 0, 0, 200);
1713 }
1714
1715 #[test]
1716 fn test_binary_ops_byte_aligned_no_remainder() {
1717 let (left, right) = create_test_data(200);
1718 test_all_binary_ops(&left, &right, 0, 0, 128);
1719 }
1720
1721 #[test]
1722 fn test_binary_ops_byte_aligned_with_remainder() {
1723 let (left, right) = create_test_data(200);
1724 test_all_binary_ops(&left, &right, 0, 0, 100);
1725 }
1726
1727 #[test]
1728 fn test_binary_ops_not_byte_aligned_no_remainder() {
1729 let (left, right) = create_test_data(200);
1730 test_all_binary_ops(&left, &right, 3, 3, 128);
1731 }
1732
1733 #[test]
1734 fn test_binary_ops_not_byte_aligned_with_remainder() {
1735 let (left, right) = create_test_data(200);
1736 test_all_binary_ops(&left, &right, 5, 5, 100);
1737 }
1738
1739 #[test]
1740 fn test_binary_ops_different_offsets() {
1741 let (left, right) = create_test_data(200);
1742 test_all_binary_ops(&left, &right, 3, 7, 50);
1743 }
1744
1745 #[test]
1746 fn test_binary_ops_offsets_greater_than_8_less_than_64() {
1747 let (left, right) = create_test_data(200);
1748 test_all_binary_ops(&left, &right, 13, 27, 100);
1749 }
1750
1751 #[test]
1754 fn test_not_less_than_byte() {
1755 let data = vec![true, false, true, false];
1756 test_mutable_buffer_unary_op_helper(&data, 0, 4, |a| !a, |a| !a);
1757 }
1758
1759 #[test]
1760 fn test_not_less_than_byte_across_boundary() {
1761 let data: Vec<bool> = (0..16).map(|i| i % 2 == 0).collect();
1762 test_mutable_buffer_unary_op_helper(&data, 6, 4, |a| !a, |a| !a);
1763 }
1764
1765 #[test]
1766 fn test_not_exactly_byte() {
1767 let data: Vec<bool> = (0..16).map(|i| i % 2 == 0).collect();
1768 test_mutable_buffer_unary_op_helper(&data, 0, 8, |a| !a, |a| !a);
1769 }
1770
1771 #[test]
1772 fn test_not_more_than_byte_less_than_u64() {
1773 let data: Vec<bool> = (0..64).map(|i| i % 2 == 0).collect();
1774 test_mutable_buffer_unary_op_helper(&data, 0, 32, |a| !a, |a| !a);
1775 }
1776
1777 #[test]
1778 fn test_not_exactly_u64() {
1779 let data: Vec<bool> = (0..128).map(|i| i % 2 == 0).collect();
1780 test_mutable_buffer_unary_op_helper(&data, 0, 64, |a| !a, |a| !a);
1781 }
1782
1783 #[test]
1784 fn test_not_more_than_u64_not_multiple() {
1785 let data: Vec<bool> = (0..200).map(|i| i % 2 == 0).collect();
1786 test_mutable_buffer_unary_op_helper(&data, 0, 100, |a| !a, |a| !a);
1787 }
1788
1789 #[test]
1790 fn test_not_exactly_multiple_u64() {
1791 let data: Vec<bool> = (0..256).map(|i| i % 2 == 0).collect();
1792 test_mutable_buffer_unary_op_helper(&data, 0, 128, |a| !a, |a| !a);
1793 }
1794
1795 #[test]
1796 fn test_not_more_than_multiple_u64() {
1797 let data: Vec<bool> = (0..300).map(|i| i % 2 == 0).collect();
1798 test_mutable_buffer_unary_op_helper(&data, 0, 200, |a| !a, |a| !a);
1799 }
1800
1801 #[test]
1802 fn test_not_byte_aligned_no_remainder() {
1803 let data: Vec<bool> = (0..200).map(|i| i % 2 == 0).collect();
1804 test_mutable_buffer_unary_op_helper(&data, 0, 128, |a| !a, |a| !a);
1805 }
1806
1807 #[test]
1808 fn test_not_byte_aligned_with_remainder() {
1809 let data: Vec<bool> = (0..200).map(|i| i % 2 == 0).collect();
1810 test_mutable_buffer_unary_op_helper(&data, 0, 100, |a| !a, |a| !a);
1811 }
1812
1813 #[test]
1814 fn test_not_not_byte_aligned_no_remainder() {
1815 let data: Vec<bool> = (0..200).map(|i| i % 2 == 0).collect();
1816 test_mutable_buffer_unary_op_helper(&data, 3, 128, |a| !a, |a| !a);
1817 }
1818
1819 #[test]
1820 fn test_not_not_byte_aligned_with_remainder() {
1821 let data: Vec<bool> = (0..200).map(|i| i % 2 == 0).collect();
1822 test_mutable_buffer_unary_op_helper(&data, 5, 100, |a| !a, |a| !a);
1823 }
1824
1825 #[test]
1828 fn test_empty_length() {
1829 let (left, right) = create_test_data(16);
1830 test_all_binary_ops(&left, &right, 0, 0, 0);
1831 }
1832
1833 #[test]
1834 fn test_single_bit() {
1835 let (left, right) = create_test_data(16);
1836 test_all_binary_ops(&left, &right, 0, 0, 1);
1837 }
1838
1839 #[test]
1840 fn test_single_bit_at_offset() {
1841 let (left, right) = create_test_data(16);
1842 test_all_binary_ops(&left, &right, 7, 7, 1);
1843 }
1844
1845 #[test]
1846 fn test_not_single_bit() {
1847 let data = vec![true, false, true, false];
1848 test_mutable_buffer_unary_op_helper(&data, 0, 1, |a| !a, |a| !a);
1849 }
1850
1851 #[test]
1852 fn test_not_empty_length() {
1853 let data = vec![true, false, true, false];
1854 test_mutable_buffer_unary_op_helper(&data, 0, 0, |a| !a, |a| !a);
1855 }
1856
1857 #[test]
1858 fn test_less_than_byte_unaligned_and_not_enough_bits() {
1859 let left_offset_in_bits = 2;
1860 let right_offset_in_bits = 4;
1861 let len_in_bits = 1;
1862
1863 let right = (0..8).map(|i| (i / 2) % 2 == 0).collect::<Vec<_>>();
1865 let left = (0..3).map(|i| i % 2 == 0).collect::<Vec<_>>();
1867 test_all_binary_ops(
1868 &left,
1869 &right,
1870 left_offset_in_bits,
1871 right_offset_in_bits,
1872 len_in_bits,
1873 );
1874 }
1875
1876 #[test]
1879 fn test_ops_ending_inside_the_first_partial_byte() {
1880 let (left, right) = create_test_data(32);
1881 for offset in 1..8 {
1882 for len in 1..=(8 - offset) {
1884 test_all_binary_ops(&left, &right, offset, offset, len);
1885 test_all_binary_ops(&left, &right, offset, (offset + 3) % 8, len);
1886 test_mutable_buffer_unary_op_helper(&left, offset, len, |a| !a, |a| !a);
1887 }
1888 }
1889 }
1890
1891 #[test]
1892 fn test_and_within_first_partial_byte_preserves_trailing_bits() {
1893 let mut left = vec![0b11111111u8, 0b11111111u8];
1894 let right = vec![0b00000000u8, 0b00000000u8];
1895 apply_bitwise_binary_op(&mut left, 1, &right, 0, 1, |a, b| a & b);
1897 assert_eq!(left, vec![0b11111101u8, 0b11111111u8]);
1898 }
1899
1900 #[test]
1901 fn test_not_within_first_partial_byte_preserves_trailing_bits() {
1902 let mut buffer = vec![0b00000000u8];
1903 apply_bitwise_unary_op(&mut buffer, 3, 2, |a| !a);
1905 assert_eq!(buffer, vec![0b00011000u8]);
1906 }
1907
1908 #[test]
1912 fn test_or_with_multi_byte_remainder_preserves_boundary_bits() {
1913 let mut left = vec![0b00000000u8, 0b00000000u8, 0b11110000u8];
1914 let right = vec![0b11111111u8, 0b11111111u8, 0b11111111u8];
1915 apply_bitwise_binary_op(&mut left, 0, &right, 0, 20, |a, b| a | b);
1917 assert_eq!(
1918 left,
1919 vec![0b11111111u8, 0b11111111u8, 0b11111111u8],
1920 "the boundary byte lost its out-of-range bits"
1921 );
1922 }
1923
1924 #[test]
1925 fn test_not_with_multi_byte_remainder_preserves_boundary_bits() {
1926 let mut buffer = vec![0b00000000u8, 0b00000000u8, 0b11111111u8];
1927 apply_bitwise_unary_op(&mut buffer, 0, 20, |a| !a);
1929 assert_eq!(
1930 buffer,
1931 vec![0b11111111u8, 0b11111111u8, 0b11110000u8],
1932 "the boundary byte lost its out-of-range bits"
1933 );
1934 }
1935
1936 #[test]
1937 fn test_bitwise_binary_op_offset_out_of_bounds() {
1938 let input = vec![0b10101010u8, 0b01010101u8];
1939 let mut buffer = MutableBuffer::new(2); buffer.extend_from_slice(&input); apply_bitwise_binary_op(
1942 buffer.as_slice_mut(),
1943 100, [0b11110000u8, 0b00001111u8],
1945 0,
1946 0,
1947 |a, b| a & b,
1948 );
1949 assert_eq!(buffer.as_slice(), &input);
1950 }
1951
1952 #[test]
1953 #[should_panic(expected = "assertion failed: last_offset <= buffer.len()")]
1954 fn test_bitwise_binary_op_length_out_of_bounds() {
1955 let mut buffer = MutableBuffer::new(2); buffer.extend_from_slice(&[0b10101010u8, 0b01010101u8]); apply_bitwise_binary_op(
1958 buffer.as_slice_mut(),
1959 0, [0b11110000u8, 0b00001111u8],
1961 0,
1962 100,
1963 |a, b| a & b,
1964 );
1965 assert_eq!(buffer.as_slice(), &[0b10101010u8, 0b01010101u8]);
1966 }
1967
1968 #[test]
1969 #[should_panic(expected = "offset + len out of bounds")]
1970 fn test_bitwise_binary_op_right_len_out_of_bounds() {
1971 let mut buffer = MutableBuffer::new(2); buffer.extend_from_slice(&[0b10101010u8, 0b01010101u8]); apply_bitwise_binary_op(
1974 buffer.as_slice_mut(),
1975 0, [0b11110000u8, 0b00001111u8],
1977 1000,
1978 16,
1979 |a, b| a & b,
1980 );
1981 assert_eq!(buffer.as_slice(), &[0b10101010u8, 0b01010101u8]);
1982 }
1983
1984 #[test]
1985 #[should_panic(expected = "the len is 2 but the index is 12")]
1986 fn test_bitwise_unary_op_offset_out_of_bounds() {
1987 let input = vec![0b10101010u8, 0b01010101u8];
1988 let mut buffer = MutableBuffer::new(2); buffer.extend_from_slice(&input); apply_bitwise_unary_op(
1991 buffer.as_slice_mut(),
1992 100, 8,
1994 |a| !a,
1995 );
1996 assert_eq!(buffer.as_slice(), &input);
1997 }
1998
1999 #[test]
2000 #[should_panic(expected = "assertion failed: last_offset <= buffer.len()")]
2001 fn test_bitwise_unary_op_length_out_of_bounds2() {
2002 let input = vec![0b10101010u8, 0b01010101u8];
2003 let mut buffer = MutableBuffer::new(2); buffer.extend_from_slice(&input); apply_bitwise_unary_op(
2006 buffer.as_slice_mut(),
2007 3, 100, |a| !a,
2010 );
2011 assert_eq!(buffer.as_slice(), &input);
2012 }
2013}