1#[cfg(target_arch = "aarch64")]
8use crate::ToByteSlice;
9use crate::util::bit_util::ceil;
10use std::fmt::Debug;
11
12#[derive(Debug)]
20pub struct UnalignedBitChunk<'a> {
21 lead_padding: usize,
22 trailing_padding: usize,
23
24 prefix: Option<u64>,
25 chunks: &'a [u64],
26 suffix: Option<u64>,
27}
28
29impl<'a> UnalignedBitChunk<'a> {
30 pub fn new(buffer: &'a [u8], offset: usize, len: usize) -> Self {
32 if len == 0 {
33 return Self {
34 lead_padding: 0,
35 trailing_padding: 0,
36 prefix: None,
37 chunks: &[],
38 suffix: None,
39 };
40 }
41
42 let byte_offset = offset / 8;
43 let offset_padding = offset % 8;
44
45 let bytes_len = (len + offset_padding).div_ceil(8);
46 let buffer = &buffer[byte_offset..byte_offset + bytes_len];
47
48 let prefix_mask = compute_prefix_mask(offset_padding);
49
50 if buffer.len() <= 8 {
52 let (suffix_mask, trailing_padding) = compute_suffix_mask(len, offset_padding);
53 let prefix = read_u64(buffer) & suffix_mask & prefix_mask;
54
55 return Self {
56 lead_padding: offset_padding,
57 trailing_padding,
58 prefix: Some(prefix),
59 chunks: &[],
60 suffix: None,
61 };
62 }
63
64 if buffer.len() <= 16 {
66 let (suffix_mask, trailing_padding) = compute_suffix_mask(len, offset_padding);
67 let prefix = read_u64(&buffer[..8]) & prefix_mask;
68 let suffix = read_u64(&buffer[8..]) & suffix_mask;
69
70 return Self {
71 lead_padding: offset_padding,
72 trailing_padding,
73 prefix: Some(prefix),
74 chunks: &[],
75 suffix: Some(suffix),
76 };
77 }
78
79 let (prefix, mut chunks, suffix) = unsafe { buffer.align_to::<u64>() };
82 assert!(
83 prefix.len() < 8 && suffix.len() < 8,
84 "align_to did not return largest possible aligned slice"
85 );
86
87 let (alignment_padding, prefix) = match (offset_padding, prefix.is_empty()) {
88 (0, true) => (0, None),
89 (_, true) => {
90 let prefix = chunks[0] & prefix_mask;
91 chunks = &chunks[1..];
92 (0, Some(prefix))
93 }
94 (_, false) => {
95 let alignment_padding = (8 - prefix.len()) * 8;
96
97 let prefix = (read_u64(prefix) & prefix_mask) << alignment_padding;
98 (alignment_padding, Some(prefix))
99 }
100 };
101
102 let lead_padding = offset_padding + alignment_padding;
103 let (suffix_mask, trailing_padding) = compute_suffix_mask(len, lead_padding);
104
105 let suffix = match (trailing_padding, suffix.is_empty()) {
106 (0, _) => None,
107 (_, true) => {
108 let suffix = chunks[chunks.len() - 1] & suffix_mask;
109 chunks = &chunks[..chunks.len() - 1];
110 Some(suffix)
111 }
112 (_, false) => Some(read_u64(suffix) & suffix_mask),
113 };
114
115 Self {
116 lead_padding,
117 trailing_padding,
118 prefix,
119 chunks,
120 suffix,
121 }
122 }
123
124 pub fn lead_padding(&self) -> usize {
126 self.lead_padding
127 }
128
129 pub fn trailing_padding(&self) -> usize {
131 self.trailing_padding
132 }
133
134 pub fn prefix(&self) -> Option<u64> {
136 self.prefix
137 }
138
139 pub fn suffix(&self) -> Option<u64> {
141 self.suffix
142 }
143
144 pub fn chunks(&self) -> &'a [u64] {
146 self.chunks
147 }
148
149 #[inline]
151 pub fn iter(&self) -> UnalignedBitChunkIterator<'a> {
152 self.prefix
153 .into_iter()
154 .chain(self.chunks.iter().copied())
155 .chain(self.suffix)
156 }
157
158 pub fn count_ones(&self) -> usize {
160 let edges = self.prefix.into_iter().chain(self.suffix);
161 edges.map(|x| x.count_ones() as usize).sum::<usize>() + count_ones_words(self.chunks)
162 }
163}
164
165#[cfg(not(target_arch = "aarch64"))]
166fn count_ones_words(words: &[u64]) -> usize {
167 words.iter().map(|x| x.count_ones() as usize).sum()
168}
169
170#[cfg(target_arch = "aarch64")]
174fn count_ones_words(words: &[u64]) -> usize {
175 let (blocks, tail) = words.as_chunks::<8>();
177 let mut total = 0;
178 const BLOCKS_PER_FLUSH: usize = (u16::MAX / 32) as usize;
182 for flush_group in blocks.chunks(BLOCKS_PER_FLUSH) {
183 let mut lane_counts = [0u16; 16];
184 for block in flush_group {
185 let bytes = block.as_slice().to_byte_slice();
186 for lane in 0..16 {
188 let count = bytes[lane].count_ones() as u8
189 + bytes[16 + lane].count_ones() as u8
190 + bytes[32 + lane].count_ones() as u8
191 + bytes[48 + lane].count_ones() as u8;
192 lane_counts[lane] += count as u16;
193 }
194 }
195 total += lane_counts.iter().copied().map(usize::from).sum::<usize>();
196 }
197 total + tail.iter().map(|w| w.count_ones() as usize).sum::<usize>()
199}
200
201impl<'a> IntoIterator for &UnalignedBitChunk<'a> {
202 type Item = u64;
203 type IntoIter = UnalignedBitChunkIterator<'a>;
204
205 fn into_iter(self) -> Self::IntoIter {
206 self.iter()
207 }
208}
209
210pub type UnalignedBitChunkIterator<'a> = std::iter::Chain<
212 std::iter::Chain<std::option::IntoIter<u64>, std::iter::Copied<std::slice::Iter<'a, u64>>>,
213 std::option::IntoIter<u64>,
214>;
215
216#[inline]
217fn read_u64(input: &[u8]) -> u64 {
218 let len = input.len().min(8);
219 let mut buf = [0_u8; 8];
220 buf[..len].copy_from_slice(input);
221 u64::from_le_bytes(buf)
222}
223
224#[inline]
225fn compute_prefix_mask(lead_padding: usize) -> u64 {
226 !((1 << lead_padding) - 1)
227}
228
229#[inline]
230fn compute_suffix_mask(len: usize, lead_padding: usize) -> (u64, usize) {
231 let trailing_bits = (len + lead_padding) % 64;
232
233 if trailing_bits == 0 {
234 return (u64::MAX, 0);
235 }
236
237 let trailing_padding = 64 - trailing_bits;
238 let suffix_mask = (1 << trailing_bits) - 1;
239 (suffix_mask, trailing_padding)
240}
241
242#[derive(Debug)]
247pub struct BitChunks<'a> {
248 buffer: &'a [u8],
249 bit_offset: usize,
251 chunk_len: usize,
253 remainder_len: usize,
255}
256
257impl<'a> BitChunks<'a> {
258 pub fn new(buffer: &'a [u8], offset: usize, len: usize) -> Self {
260 let end = offset.checked_add(len).expect("offset + len out of bounds");
261 assert!(ceil(end, 8) <= buffer.len(), "offset + len out of bounds");
262
263 let byte_offset = offset / 8;
264 let bit_offset = offset % 8;
265
266 let chunk_len = len / 64;
268 let remainder_len = len % 64;
270
271 BitChunks::<'a> {
272 buffer: &buffer[byte_offset..],
273 bit_offset,
274 chunk_len,
275 remainder_len,
276 }
277 }
278}
279
280#[derive(Debug)]
282pub struct BitChunkIterator<'a> {
283 buffer: &'a [u8],
284 bit_offset: usize,
285 chunk_len: usize,
286 index: usize,
287}
288
289impl<'a> BitChunks<'a> {
290 #[inline]
292 pub const fn remainder_len(&self) -> usize {
293 self.remainder_len
294 }
295
296 #[inline]
298 pub const fn chunk_len(&self) -> usize {
299 self.chunk_len
300 }
301
302 #[inline]
304 pub fn remainder_bits(&self) -> u64 {
305 let bit_len = self.remainder_len;
306 if bit_len == 0 {
307 0
308 } else {
309 let bit_offset = self.bit_offset;
310 let byte_len = ceil(bit_len + bit_offset, 8);
313 let base = unsafe {
317 self.buffer
318 .as_ptr()
319 .add(self.chunk_len * std::mem::size_of::<u64>())
320 };
321
322 let mut bits = unsafe { std::ptr::read(base) } as u64 >> bit_offset;
323 for i in 1..byte_len {
324 let byte = unsafe { std::ptr::read(base.add(i)) };
325 bits |= (byte as u64) << (i * 8 - bit_offset);
326 }
327
328 bits & ((1 << bit_len) - 1)
329 }
330 }
331
332 #[inline]
338 pub fn num_u64s(&self) -> usize {
339 if self.remainder_len == 0 {
340 self.chunk_len
341 } else {
342 self.chunk_len + 1
343 }
344 }
345
346 #[inline]
349 pub fn num_bytes(&self) -> usize {
350 ceil(self.chunk_len * 64 + self.remainder_len, 8)
351 }
352
353 #[inline]
372 pub fn chunk(&self, index: usize) -> u64 {
373 assert!(index < self.chunk_len, "chunk index out of bounds");
374 unsafe { read_chunk(self.buffer, self.bit_offset, index) }
377 }
378
379 #[inline]
381 pub const fn iter(&self) -> BitChunkIterator<'a> {
382 BitChunkIterator::<'a> {
383 buffer: self.buffer,
384 bit_offset: self.bit_offset,
385 chunk_len: self.chunk_len,
386 index: 0,
387 }
388 }
389
390 #[inline]
392 pub fn iter_padded(&self) -> impl Iterator<Item = u64> + 'a {
393 self.iter().chain(std::iter::once(self.remainder_bits()))
394 }
395}
396
397impl<'a> IntoIterator for BitChunks<'a> {
398 type Item = u64;
399 type IntoIter = BitChunkIterator<'a>;
400
401 fn into_iter(self) -> Self::IntoIter {
402 self.iter()
403 }
404}
405
406impl<'a> IntoIterator for &BitChunks<'a> {
407 type Item = u64;
408 type IntoIter = BitChunkIterator<'a>;
409
410 fn into_iter(self) -> Self::IntoIter {
411 self.iter()
412 }
413}
414
415#[inline]
424unsafe fn read_chunk(buffer: &[u8], bit_offset: usize, index: usize) -> u64 {
425 debug_assert!(bit_offset < 8);
426 debug_assert!(buffer.len() >= index * 8 + 8 + usize::from(bit_offset != 0));
427 #[expect(clippy::cast_ptr_alignment)]
429 let raw_data = buffer.as_ptr().cast::<u64>();
430
431 let current = unsafe { std::ptr::read_unaligned(raw_data.add(index)).to_le() };
436
437 if bit_offset == 0 {
438 current
439 } else {
440 let next = unsafe { std::ptr::read_unaligned(raw_data.add(index + 1).cast::<u8>()) as u64 };
444
445 (current >> bit_offset) | (next << (64 - bit_offset))
446 }
447}
448
449impl Iterator for BitChunkIterator<'_> {
450 type Item = u64;
451
452 #[inline]
453 fn next(&mut self) -> Option<u64> {
454 let index = self.index;
455 if index >= self.chunk_len {
456 return None;
457 }
458
459 let combined = unsafe { read_chunk(self.buffer, self.bit_offset, index) };
462
463 self.index = index + 1;
464
465 Some(combined)
466 }
467
468 #[inline]
469 fn size_hint(&self) -> (usize, Option<usize>) {
470 (
471 self.chunk_len - self.index,
472 Some(self.chunk_len - self.index),
473 )
474 }
475}
476
477impl ExactSizeIterator for BitChunkIterator<'_> {
478 #[inline]
479 fn len(&self) -> usize {
480 self.chunk_len - self.index
481 }
482}
483
484#[cfg(test)]
485mod tests {
486 use rand::distr::uniform::UniformSampler;
487 use rand::distr::uniform::UniformUsize;
488 use rand::prelude::*;
489 use rand::rng;
490
491 use crate::buffer::Buffer;
492 use crate::util::bit_chunk_iterator::UnalignedBitChunk;
493 use crate::util::bit_util::get_bit;
494
495 #[test]
496 fn test_iter_aligned() {
497 let input: &[u8] = &[0, 1, 2, 3, 4, 5, 6, 7];
498 let buffer: Buffer = Buffer::from(input);
499
500 let bitchunks = buffer.bit_chunks(0, 64);
501 let result = bitchunks.into_iter().collect::<Vec<_>>();
502
503 assert_eq!(vec![0x0706050403020100], result);
504 }
505
506 #[test]
507 fn test_iter_unaligned() {
508 let input: &[u8] = &[
509 0b00000000, 0b00000001, 0b00000010, 0b00000100, 0b00001000, 0b00010000, 0b00100000,
510 0b01000000, 0b11111111,
511 ];
512 let buffer: Buffer = Buffer::from(input);
513
514 let bitchunks = buffer.bit_chunks(4, 64);
515
516 assert_eq!(0, bitchunks.remainder_len());
517 assert_eq!(0, bitchunks.remainder_bits());
518
519 let result = bitchunks.into_iter().collect::<Vec<_>>();
520
521 assert_eq!(
522 vec![0b1111010000000010000000010000000010000000010000000010000000010000],
523 result
524 );
525 }
526
527 #[test]
528 fn test_iter_unaligned_remainder_1_byte() {
529 let input: &[u8] = &[
530 0b00000000, 0b00000001, 0b00000010, 0b00000100, 0b00001000, 0b00010000, 0b00100000,
531 0b01000000, 0b11111111,
532 ];
533 let buffer: Buffer = Buffer::from(input);
534
535 let bitchunks = buffer.bit_chunks(4, 66);
536
537 assert_eq!(2, bitchunks.remainder_len());
538 assert_eq!(0b00000011, bitchunks.remainder_bits());
539
540 let result = bitchunks.into_iter().collect::<Vec<_>>();
541
542 assert_eq!(
543 vec![0b1111010000000010000000010000000010000000010000000010000000010000],
544 result
545 );
546 }
547
548 #[test]
549 fn test_iter_unaligned_remainder_bits_across_bytes() {
550 let input: &[u8] = &[0b00111111, 0b11111100];
551 let buffer: Buffer = Buffer::from(input);
552
553 let bitchunks = buffer.bit_chunks(6, 7);
556
557 assert_eq!(7, bitchunks.remainder_len());
558 assert_eq!(0b1110000, bitchunks.remainder_bits());
559 }
560
561 #[test]
562 fn test_iter_unaligned_remainder_bits_large() {
563 let input: &[u8] = &[
564 0b11111111, 0b00000000, 0b11111111, 0b00000000, 0b11111111, 0b00000000, 0b11111111,
565 0b00000000, 0b11111111,
566 ];
567 let buffer: Buffer = Buffer::from(input);
568
569 let bitchunks = buffer.bit_chunks(2, 63);
570
571 assert_eq!(63, bitchunks.remainder_len());
572 assert_eq!(
573 0b100_0000_0011_1111_1100_0000_0011_1111_1100_0000_0011_1111_1100_0000_0011_1111,
574 bitchunks.remainder_bits()
575 );
576 }
577
578 #[test]
579 fn test_chunk_aligned() {
580 let input: Vec<u8> = (0..24).collect();
581 let buffer = Buffer::from(input);
582
583 let bitchunks = buffer.bit_chunks(0, 24 * 8);
584 assert_eq!(3, bitchunks.chunk_len());
585 assert_eq!(0x0706050403020100, bitchunks.chunk(0));
586 assert_eq!(0x0f0e0d0c0b0a0908, bitchunks.chunk(1));
587 assert_eq!(0x1716151413121110, bitchunks.chunk(2));
588 }
589
590 #[test]
591 fn test_chunk_matches_iter() {
592 let input: Vec<u8> = (0..26_u8).map(|i| i.wrapping_mul(13)).collect();
596 let buffer = Buffer::from(input);
597
598 for offset in (0..8).chain([8, 13]) {
601 for len in [64, 65, 128, 130, 191, 192] {
602 let bitchunks = buffer.bit_chunks(offset, len);
603 assert_eq!(len / 64, bitchunks.chunk_len());
604 for index in 0..bitchunks.chunk_len() {
605 assert_eq!(
606 bitchunks.iter().nth(index),
607 Some(bitchunks.chunk(index)),
608 "offset {offset} len {len} chunk {index}"
609 );
610 }
611 }
612 }
613 }
614
615 #[test]
616 #[should_panic(expected = "chunk index out of bounds")]
617 fn test_chunk_out_of_bounds() {
618 let buffer = Buffer::from(vec![0xFF_u8; 16]);
619 let bitchunks = buffer.bit_chunks(0, 128);
620 assert_eq!(2, bitchunks.chunk_len());
621 bitchunks.chunk(2);
622 }
623
624 #[test]
625 #[should_panic(expected = "chunk index out of bounds")]
626 fn test_chunk_out_of_bounds_no_complete_chunk() {
627 let buffer = Buffer::from(vec![0xFF_u8; 8]);
628 let bitchunks = buffer.bit_chunks(1, 63);
629 assert_eq!(0, bitchunks.chunk_len());
630 bitchunks.chunk(0);
631 }
632
633 #[test]
634 fn test_iter_remainder_out_of_bounds() {
635 const ALLOC_SIZE: usize = 4 * 1024;
637 let input = vec![0xFF_u8; ALLOC_SIZE];
638
639 let buffer: Buffer = Buffer::from_vec(input);
640
641 let bitchunks = buffer.bit_chunks(57, ALLOC_SIZE * 8 - 57);
642
643 assert_eq!(u64::MAX, bitchunks.iter().last().unwrap());
644 assert_eq!(0x7F, bitchunks.remainder_bits());
645 }
646
647 #[test]
648 #[should_panic(expected = "offset + len out of bounds")]
649 fn test_out_of_bound_should_panic_length_is_more_than_buffer_length() {
650 const ALLOC_SIZE: usize = 4 * 1024;
651 let input = vec![0xFF_u8; ALLOC_SIZE];
652
653 let buffer: Buffer = Buffer::from_vec(input);
654
655 buffer.bit_chunks(0, (ALLOC_SIZE + 1) * 8);
657 }
658
659 #[test]
660 #[should_panic(expected = "offset + len out of bounds")]
661 fn test_out_of_bound_should_panic_length_is_more_than_buffer_length_but_not_when_not_using_ceil()
662 {
663 const ALLOC_SIZE: usize = 4 * 1024;
664 let input = vec![0xFF_u8; ALLOC_SIZE];
665
666 let buffer: Buffer = Buffer::from_vec(input);
667
668 buffer.bit_chunks(0, (ALLOC_SIZE * 8) + 1);
670 }
671
672 #[test]
673 #[should_panic(expected = "offset + len out of bounds")]
674 fn test_out_of_bound_should_panic_when_offset_is_not_zero_and_length_is_the_entire_buffer_length()
675 {
676 const ALLOC_SIZE: usize = 4 * 1024;
677 let input = vec![0xFF_u8; ALLOC_SIZE];
678
679 let buffer: Buffer = Buffer::from_vec(input);
680
681 buffer.bit_chunks(8, ALLOC_SIZE * 8);
683 }
684
685 #[test]
686 #[should_panic(expected = "offset + len out of bounds")]
687 fn test_out_of_bound_should_panic_when_offset_is_not_zero_and_length_is_the_entire_buffer_length_with_ceil()
688 {
689 const ALLOC_SIZE: usize = 4 * 1024;
690 let input = vec![0xFF_u8; ALLOC_SIZE];
691
692 let buffer: Buffer = Buffer::from_vec(input);
693
694 buffer.bit_chunks(1, ALLOC_SIZE * 8);
696 }
697
698 #[test]
699 #[should_panic(expected = "offset + len out of bounds")]
700 fn test_out_of_bound_should_panic_when_offset_and_length_overflow() {
701 let buffer = Buffer::from(vec![0xFF_u8; 8]);
702 buffer.bit_chunks(1, usize::MAX);
703 }
704
705 #[test]
706 fn test_unaligned_bit_chunk_iterator() {
707 let buffer = Buffer::from(&[0xFF; 5]);
708 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 40);
709
710 assert!(unaligned.chunks().is_empty()); assert_eq!(unaligned.lead_padding(), 0);
712 assert_eq!(unaligned.trailing_padding(), 24);
713 assert_eq!(
715 unaligned.prefix(),
716 Some(0b0000000000000000000000001111111111111111111111111111111111111111)
717 );
718 assert_eq!(unaligned.suffix(), None);
719
720 let buffer = buffer.slice(1);
721 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 32);
722
723 assert!(unaligned.chunks().is_empty()); assert_eq!(unaligned.lead_padding(), 0);
725 assert_eq!(unaligned.trailing_padding(), 32);
726 assert_eq!(
728 unaligned.prefix(),
729 Some(0b0000000000000000000000000000000011111111111111111111111111111111)
730 );
731 assert_eq!(unaligned.suffix(), None);
732
733 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 5, 27);
734
735 assert!(unaligned.chunks().is_empty()); assert_eq!(unaligned.lead_padding(), 5); assert_eq!(unaligned.trailing_padding(), 32);
738 assert_eq!(
740 unaligned.prefix(),
741 Some(0b0000000000000000000000000000000011111111111111111111111111100000)
742 );
743 assert_eq!(unaligned.suffix(), None);
744
745 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 12, 20);
746
747 assert!(unaligned.chunks().is_empty()); assert_eq!(unaligned.lead_padding(), 4); assert_eq!(unaligned.trailing_padding(), 40);
750 assert_eq!(
752 unaligned.prefix(),
753 Some(0b0000000000000000000000000000000000000000111111111111111111110000)
754 );
755 assert_eq!(unaligned.suffix(), None);
756
757 let buffer = Buffer::from(&[0xFF; 14]);
758
759 let (prefix, aligned, suffix) = unsafe { buffer.as_slice().align_to::<u64>() };
761 assert_eq!(prefix.len(), 0);
762 assert_eq!(aligned.len(), 1);
763 assert_eq!(suffix.len(), 6);
764
765 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 112);
766
767 assert!(unaligned.chunks().is_empty()); assert_eq!(unaligned.lead_padding(), 0); assert_eq!(unaligned.trailing_padding(), 16);
770 assert_eq!(unaligned.prefix(), Some(u64::MAX));
771 assert_eq!(unaligned.suffix(), Some((1 << 48) - 1));
772
773 let buffer = Buffer::from(&[0xFF; 16]);
774
775 let (prefix, aligned, suffix) = unsafe { buffer.as_slice().align_to::<u64>() };
777 assert_eq!(prefix.len(), 0);
778 assert_eq!(aligned.len(), 2);
779 assert_eq!(suffix.len(), 0);
780
781 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 128);
782
783 assert_eq!(unaligned.prefix(), Some(u64::MAX));
784 assert_eq!(unaligned.suffix(), Some(u64::MAX));
785 assert!(unaligned.chunks().is_empty()); let buffer = Buffer::from(&[0xFF; 64]);
788
789 let (prefix, aligned, suffix) = unsafe { buffer.as_slice().align_to::<u64>() };
791 assert_eq!(prefix.len(), 0);
792 assert_eq!(aligned.len(), 8);
793 assert_eq!(suffix.len(), 0);
794
795 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 512);
796
797 assert_eq!(unaligned.suffix(), None);
799 assert_eq!(unaligned.prefix(), None);
800 assert_eq!(unaligned.chunks(), [u64::MAX; 8].as_slice());
801 assert_eq!(unaligned.lead_padding(), 0);
802 assert_eq!(unaligned.trailing_padding(), 0);
803
804 let buffer = buffer.slice(1); let (prefix, aligned, suffix) = unsafe { buffer.as_slice().align_to::<u64>() };
808 assert_eq!(prefix.len(), 7);
809 assert_eq!(aligned.len(), 7);
810 assert_eq!(suffix.len(), 0);
811
812 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 504);
813
814 assert_eq!(unaligned.prefix(), Some(u64::MAX - 0xFF));
816 assert_eq!(unaligned.suffix(), None);
817 assert_eq!(unaligned.chunks(), [u64::MAX; 7].as_slice());
818 assert_eq!(unaligned.lead_padding(), 8);
819 assert_eq!(unaligned.trailing_padding(), 0);
820
821 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 17, 300);
822
823 assert_eq!(unaligned.lead_padding(), 25);
830 assert_eq!(unaligned.trailing_padding(), 59);
831 assert_eq!(unaligned.prefix(), Some(u64::MAX - (1 << 25) + 1));
832 assert_eq!(unaligned.suffix(), Some(0b11111));
833 assert_eq!(unaligned.chunks(), [u64::MAX; 4].as_slice());
834
835 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 17, 0);
836
837 assert_eq!(unaligned.prefix(), None);
838 assert_eq!(unaligned.suffix(), None);
839 assert!(unaligned.chunks().is_empty());
840 assert_eq!(unaligned.lead_padding(), 0);
841 assert_eq!(unaligned.trailing_padding(), 0);
842
843 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 17, 1);
844
845 assert_eq!(unaligned.prefix(), Some(2));
846 assert_eq!(unaligned.suffix(), None);
847 assert!(unaligned.chunks().is_empty());
848 assert_eq!(unaligned.lead_padding(), 1);
849 assert_eq!(unaligned.trailing_padding(), 62);
850 }
851
852 #[test]
853 fn test_unaligned_bit_chunk_count_ones() {
854 let sizes = [
859 0, 1, 7, 8, 63, 64, 65, 72, 136, 131_008, 131_072, 131_136, 131_207,
860 ];
861 let mut rng = StdRng::seed_from_u64(42);
862 for size in sizes {
863 for byte in [Some(0xFF_u8), Some(0xA5), Some(0x00), None] {
864 let bytes = match byte {
865 Some(byte) => vec![byte; size],
866 None => (0..size).map(|_| rng.random()).collect(),
867 };
868 let buffer = Buffer::from(bytes);
869 let bits = size * 8;
870 for offset in [0, 3.min(bits), 64.min(bits)] {
871 let len = bits - offset;
872 let unaligned = UnalignedBitChunk::new(buffer.as_slice(), offset, len);
873 let expected = (offset..bits)
874 .filter(|i| get_bit(buffer.as_slice(), *i))
875 .count();
876 assert_eq!(
877 unaligned.count_ones(),
878 expected,
879 "{size} {byte:#x?} {offset}"
880 );
881 }
882 }
883 }
884 }
885
886 #[test]
887 fn fuzz_unaligned_bit_chunk_iterator() {
888 let mut rng = rng();
889
890 let uusize = UniformUsize::new(usize::MIN, usize::MAX).unwrap();
891 for _ in 0..100 {
892 let mask_len = rng.random_range(0..1024);
893 let bools: Vec<_> = std::iter::from_fn(|| Some(rng.random()))
894 .take(mask_len)
895 .collect();
896
897 let buffer = Buffer::from_iter(bools.iter().copied());
898
899 let max_offset = 64.min(mask_len);
900 let offset = uusize.sample(&mut rng).checked_rem(max_offset).unwrap_or(0);
901
902 let max_truncate = 128.min(mask_len - offset);
903 let truncate = uusize
904 .sample(&mut rng)
905 .checked_rem(max_truncate)
906 .unwrap_or(0);
907
908 let unaligned =
909 UnalignedBitChunk::new(buffer.as_slice(), offset, mask_len - offset - truncate);
910
911 let bool_slice = &bools[offset..mask_len - truncate];
912
913 let count = unaligned.count_ones();
914 let expected_count = bool_slice.iter().filter(|x| **x).count();
915
916 assert_eq!(count, expected_count);
917
918 let collected: Vec<u64> = unaligned.iter().collect();
919
920 let get_bit = |idx: usize| -> bool {
921 let padded_index = idx + unaligned.lead_padding();
922 let byte_idx = padded_index / 64;
923 let bit_idx = padded_index % 64;
924 (collected[byte_idx] & (1 << bit_idx)) != 0
925 };
926
927 for (idx, b) in bool_slice.iter().enumerate() {
928 assert_eq!(*b, get_bit(idx))
929 }
930 }
931 }
932}