1use crate::bit_util::ceil;
8
9pub fn set_bits(
21 write_data: &mut [u8],
22 data: &[u8],
23 offset_write: usize,
24 offset_read: usize,
25 len: usize,
26) -> usize {
27 assert!(
28 offset_write
29 .checked_add(len)
30 .expect("operation will overflow write buffer")
31 <= write_data.len() * 8
32 );
33 assert!(
34 offset_read
35 .checked_add(len)
36 .expect("operation will overflow read buffer")
37 <= data.len() * 8
38 );
39 let mut null_count = 0;
40 let mut acc = 0;
41 while len > acc {
42 let (n, len_set) = unsafe {
46 set_upto_64bits(
47 write_data,
48 data,
49 offset_write + acc,
50 offset_read + acc,
51 len - acc,
52 )
53 };
54 null_count += n;
55 acc += len_set;
56 }
57
58 null_count
59}
60
61#[inline]
67unsafe fn set_upto_64bits(
68 write_data: &mut [u8],
69 data: &[u8],
70 offset_write: usize,
71 offset_read: usize,
72 len: usize,
73) -> (usize, usize) {
74 let read_byte = offset_read / 8;
75 let read_shift = offset_read % 8;
76 let write_byte = offset_write / 8;
77 let write_shift = offset_write % 8;
78
79 if len >= 64 {
80 let chunk = unsafe { data.as_ptr().add(read_byte).cast::<u64>().read_unaligned() };
81 if read_shift == 0 {
82 if write_shift == 0 {
83 let len = 64;
85 let null_count = chunk.count_zeros() as usize;
86 unsafe { write_u64_bytes(write_data, write_byte, chunk) };
87 (null_count, len)
88 } else {
89 let len = 64 - write_shift;
91 let chunk = chunk << write_shift;
92 let null_count = len - chunk.count_ones() as usize;
93 unsafe { or_write_u64_bytes(write_data, write_byte, chunk) };
94 (null_count, len)
95 }
96 } else if write_shift == 0 {
97 let len = 64 - 8; let chunk = (chunk >> read_shift) & 0x00FFFFFFFFFFFFFF; let null_count = len - chunk.count_ones() as usize;
101 unsafe { write_u64_bytes(write_data, write_byte, chunk) };
102 (null_count, len)
103 } else {
104 let len = 64 - std::cmp::max(read_shift, write_shift);
105 let chunk = (chunk >> read_shift) << write_shift;
106 let null_count = len - chunk.count_ones() as usize;
107 unsafe { or_write_u64_bytes(write_data, write_byte, chunk) };
108 (null_count, len)
109 }
110 } else if len == 1 {
111 let byte_chunk = (unsafe { data.get_unchecked(read_byte) } >> read_shift) & 1;
112 unsafe { *write_data.get_unchecked_mut(write_byte) |= byte_chunk << write_shift };
113 ((byte_chunk ^ 1) as usize, 1)
114 } else {
115 let len = std::cmp::min(len, 64 - std::cmp::max(read_shift, write_shift));
116 let bytes = ceil(len + read_shift, 8);
117 let chunk = unsafe { read_bytes_to_u64(data, read_byte, bytes) };
119 let mask = u64::MAX >> (64 - len);
120 let chunk = (chunk >> read_shift) & mask; let chunk = chunk << write_shift; let null_count = len - chunk.count_ones() as usize;
123 let bytes = ceil(len + write_shift, 8);
124 for (i, c) in chunk.to_le_bytes().iter().enumerate().take(bytes) {
125 unsafe { *write_data.get_unchecked_mut(write_byte + i) |= c };
126 }
127 (null_count, len)
128 }
129}
130
131#[inline]
134unsafe fn read_bytes_to_u64(data: &[u8], offset: usize, count: usize) -> u64 {
135 debug_assert!(count <= 8);
136 let mut tmp: u64 = 0;
137 let src = unsafe { data.as_ptr().add(offset) };
138 unsafe { std::ptr::copy_nonoverlapping(src, std::ptr::from_mut(&mut tmp).cast::<u8>(), count) };
139 tmp
140}
141
142#[inline]
145unsafe fn write_u64_bytes(data: &mut [u8], offset: usize, chunk: u64) {
146 #[expect(
147 clippy::cast_ptr_alignment,
148 reason = "the pointer is only written through `write_unaligned`"
149 )]
150 let ptr = unsafe { data.as_mut_ptr().add(offset) }.cast::<u64>();
151 unsafe { ptr.write_unaligned(chunk) };
152}
153
154#[inline]
160unsafe fn or_write_u64_bytes(data: &mut [u8], offset: usize, chunk: u64) {
161 let ptr = unsafe { data.as_mut_ptr().add(offset) };
162 let chunk = chunk | (unsafe { *ptr }) as u64;
163 unsafe { ptr.cast::<u64>().write_unaligned(chunk) };
164}
165
166#[cfg(test)]
167mod tests {
168 use super::*;
169 use crate::bit_util::{get_bit, set_bit, unset_bit};
170 use rand::prelude::StdRng;
171 use rand::{RngExt, SeedableRng, TryRng};
172 use std::fmt::Display;
173
174 #[test]
175 fn test_set_bits_aligned() {
176 SetBitsTest {
177 write_data: vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
178 data: vec![
179 0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011, 0b11100111,
180 0b10100101,
181 ],
182 offset_write: 8,
183 offset_read: 0,
184 len: 64,
185 expected_data: vec![
186 0, 0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011,
187 0b11100111, 0b10100101, 0,
188 ],
189 expected_null_count: 24,
190 }
191 .verify();
192 }
193
194 #[test]
195 fn test_set_bits_unaligned_destination_start() {
196 SetBitsTest {
197 write_data: vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
198 data: vec![
199 0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011, 0b11100111,
200 0b10100101,
201 ],
202 offset_write: 3,
203 offset_read: 0,
204 len: 64,
205 expected_data: vec![
206 0b00111000, 0b00101111, 0b11001101, 0b11011100, 0b01011110, 0b00011111, 0b00111110,
207 0b00101111, 0b00000101, 0b00000000,
208 ],
209 expected_null_count: 24,
210 }
211 .verify();
212 }
213
214 #[test]
215 fn test_set_bits_unaligned_destination_end() {
216 SetBitsTest {
217 write_data: vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
218 data: vec![
219 0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011, 0b11100111,
220 0b10100101,
221 ],
222 offset_write: 8,
223 offset_read: 0,
224 len: 62,
225 expected_data: vec![
226 0, 0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011,
227 0b11100111, 0b00100101, 0,
228 ],
229 expected_null_count: 23,
230 }
231 .verify();
232 }
233
234 #[test]
235 fn test_set_bits_unaligned() {
236 SetBitsTest {
237 write_data: vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
238 data: vec![
239 0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011, 0b11100111,
240 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011, 0b11100111, 0b10100101,
241 0b10011001, 0b11011011, 0b11101011, 0b11000011,
242 ],
243 offset_write: 3,
244 offset_read: 5,
245 len: 95,
246 expected_data: vec![
247 0b01111000, 0b01101001, 0b11100110, 0b11110110, 0b11111010, 0b11110000, 0b01111001,
248 0b01101001, 0b11100110, 0b11110110, 0b11111010, 0b11110000, 0b00000001,
249 ],
250 expected_null_count: 35,
251 }
252 .verify();
253 }
254
255 #[test]
256 fn set_bits_fuzz() {
257 let mut rng = StdRng::seed_from_u64(42);
258 let mut data = SetBitsTest::new();
259 for _ in 0..100 {
260 data.regen(&mut rng);
261 data.verify();
262 }
263 }
264
265 #[derive(Debug, Default)]
266 struct SetBitsTest {
267 write_data: Vec<u8>,
269 data: Vec<u8>,
271 offset_write: usize,
272 offset_read: usize,
273 len: usize,
274 expected_data: Vec<u8>,
276 expected_null_count: usize,
278 }
279
280 struct BinaryFormatter<'a>(&'a [u8]);
282 impl Display for BinaryFormatter<'_> {
283 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
284 for byte in self.0 {
285 write!(f, "{byte:08b} ")?;
286 }
287 write!(f, " ")?;
288 Ok(())
289 }
290 }
291
292 impl Display for SetBitsTest {
293 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
294 writeln!(f, "SetBitsTest {{")?;
295 writeln!(f, " write_data: {}", BinaryFormatter(&self.write_data))?;
296 writeln!(f, " data: {}", BinaryFormatter(&self.data))?;
297 writeln!(
298 f,
299 " expected_data: {}",
300 BinaryFormatter(&self.expected_data)
301 )?;
302 writeln!(f, " offset_write: {}", self.offset_write)?;
303 writeln!(f, " offset_read: {}", self.offset_read)?;
304 writeln!(f, " len: {}", self.len)?;
305 writeln!(f, " expected_null_count: {}", self.expected_null_count)?;
306 writeln!(f, "}}")
307 }
308 }
309
310 impl SetBitsTest {
311 fn new() -> Self {
313 Self::default()
314 }
315
316 fn regen(&mut self, rng: &mut StdRng) {
318 let len = rng.random_range(0..=200);
330
331 let offset_write_bits = rng.random_range(0..=200);
333 let offset_write_bytes = if offset_write_bits % 8 == 0 {
334 offset_write_bits / 8
335 } else {
336 (offset_write_bits / 8) + 1
337 };
338 let extra_write_data_bytes = rng.random_range(0..=5); let extra_read_data_bytes = rng.random_range(0..=5); let offset_read_bits = rng.random_range(0..=200);
343 let offset_read_bytes = if offset_read_bits % 8 != 0 {
344 (offset_read_bits / 8) + 1
345 } else {
346 offset_read_bits / 8
347 };
348
349 self.write_data.clear();
351 self.write_data
352 .resize(offset_write_bytes + len + extra_write_data_bytes, 0);
353
354 self.offset_write = offset_write_bits;
358
359 self.data
361 .resize(offset_read_bytes + len + extra_read_data_bytes, 0);
362 rng.try_fill_bytes(self.data.as_mut_slice()).unwrap();
364 self.offset_read = offset_read_bits;
365
366 self.len = len;
367
368 self.expected_data.resize(self.write_data.len(), 0);
370 self.expected_data.copy_from_slice(&self.write_data);
371
372 self.expected_null_count = 0;
373 for i in 0..self.len {
374 let bit = get_bit(&self.data, self.offset_read + i);
375 if bit {
376 set_bit(&mut self.expected_data, self.offset_write + i);
377 } else {
378 unset_bit(&mut self.expected_data, self.offset_write + i);
379 self.expected_null_count += 1;
380 }
381 }
382 }
383
384 fn verify(&self) {
386 let mut actual = self.write_data.clone();
388 let null_count = set_bits(
389 &mut actual,
390 &self.data,
391 self.offset_write,
392 self.offset_read,
393 self.len,
394 );
395
396 assert_eq!(actual, self.expected_data, "self: {self}");
397 assert_eq!(null_count, self.expected_null_count, "self: {self}");
398 }
399 }
400
401 #[test]
402 fn test_set_upto_64bits() {
403 let write_data: &mut [u8] = &mut [0; 9];
405 let data: &[u8] = &[
406 0b00000001, 0b00000001, 0b00000001, 0b00000001, 0b00000001, 0b00000001, 0b00000001,
407 0b00000001, 0b00000001,
408 ];
409 let offset_write = 1;
410 let offset_read = 0;
411 let len = 65;
412 let (n, len_set) =
413 unsafe { set_upto_64bits(write_data, data, offset_write, offset_read, len) };
414 assert_eq!(n, 55);
415 assert_eq!(len_set, 63);
416 assert_eq!(
417 write_data,
418 &[
419 0b00000010, 0b00000010, 0b00000010, 0b00000010, 0b00000010, 0b00000010, 0b00000010,
420 0b00000010, 0b00000000
421 ]
422 );
423
424 let write_data: &mut [u8] = &mut [0b00000000];
426 let data: &[u8] = &[0b00000001];
427 let offset_write = 1;
428 let offset_read = 0;
429 let len = 1;
430 let (n, len_set) =
431 unsafe { set_upto_64bits(write_data, data, offset_write, offset_read, len) };
432 assert_eq!(n, 0);
433 assert_eq!(len_set, 1);
434 assert_eq!(write_data, &[0b00000010]);
435 }
436
437 #[test]
438 #[should_panic(expected = "operation will overflow read buffer")]
439 fn test_overflow_read_buffer_bounds() {
440 let data = [0u8; 1];
442 let mut write_data = [0u8; 1];
443
444 let offset_write: usize = 0;
448 let offset_read: usize = usize::MAX - 7;
449 let len: usize = 8;
450
451 let _nulls = set_bits(&mut write_data, &data, offset_write, offset_read, len);
453 }
454
455 #[test]
456 #[should_panic(expected = "operation will overflow write buffer")]
457 fn test_overflow_write_buffer_bounds() {
458 let data = [0u8; 1];
460 let mut write_data = [0u8; 1];
461
462 let offset_write: usize = usize::MAX - 7;
466 let offset_read: usize = 0;
467 let len: usize = 8;
468
469 let _nulls = set_bits(&mut write_data, &data, offset_write, offset_read, len);
471 }
472}