1 /*! A dynamically-allocated, fixed-size, buffer containing a `BitSlice` region. 2 3 You can read the standard library’s [`alloc::boxed` module documentation][std] 4 here. 5 6 This module defines the [`BitBox`] buffer, and all of its associated support 7 code. 8 9 `BitBox` is equivalent to `Box<[bool]>`, in its operation and in its 10 relationship to the `BitSlice` and [`BitVec`] types. Most of the interesting 11 work to be done on a bit-sequence is implemented in `BitSlice`, to which 12 `BitBox` dereferences, and the box container itself only exists to maintain 13 wonership and provide some specializations that cannot safely be done on 14 `BitSlice` alone. 15 16 There is almost never a reason to use this type, as it is a mixture of 17 [`BitArray`]’s fixed width and [`BitVec`]’s heap allocation. You should only use 18 it when you have a bit-sequence whose width is either unknowable at compile-time 19 or inexpressable in `BitArray`, and are constructing the sequence in a `BitVec` 20 before freezing it. 21 22 [`BitArray`]: ../array/struct.BitArray.html 23 [`BitBox`]: struct.BitBox.html 24 [`BitSlice`]: ../slice/struct.BitSlice.html 25 [`BitVec`]: ../vec/struct.BitVec.html 26 [std]: https://doc.rust-lang.org/alloc/boxed 27 !*/ 28 29 #![cfg(feature = "alloc")] 30 31 use crate::{ 32 index::BitIdx, 33 mem::BitMemory, 34 order::{ 35 BitOrder, 36 Lsb0, 37 }, 38 pointer::BitPtr, 39 slice::BitSlice, 40 store::BitStore, 41 }; 42 43 use alloc::boxed::Box; 44 45 use core::{ 46 mem::ManuallyDrop, 47 ptr::NonNull, 48 slice, 49 }; 50 51 use wyz::pipe::{ 52 Pipe, 53 PipeRef, 54 }; 55 56 /** A frozen heap-allocated buffer of individual bits. 57 58 This is essentially a [`BitVec`] that has frozen its allocation, and given up 59 the ability to change size. It is analagous to `Box<[bool]>`, and is written to 60 be as close as possible to drop-in replacable for it. This type contains almost 61 no interesting behavior in its own right; it dereferences to [`BitSlice`] to 62 manipulate its contents, and it converts to and from `BitVec` for allocation 63 control. 64 65 If you know the length of your bit sequence at compile-time, and it is 66 expressible within the limits of [`BitArray`], you should prefer that type 67 instead. Large `BitArray`s can be `Box`ed normally as desired. 68 69 # Documentation 70 71 All APIs that mirror something in the standard library will have an `Original` 72 section linking to the corresponding item. All APIs that have a different 73 signature or behavior than the original will have an `API Differences` section 74 explaining what has changed, and how to adapt your existing code to the change. 75 76 These sections look like this: 77 78 # Original 79 80 [`Box<[T]>`](https://doc.rust-lang.org/alloc/boxed/struct.Box.html) 81 82 # API Differences 83 84 The buffer type `Box<[bool]>` has no type parameters. `BitBox<O, T>` has the 85 same two type parameters as `BitSlice<O, T>`. Otherwise, `BitBox` is able to 86 implement the full API surface of `Box<[bool]>`. 87 88 # Behavior 89 90 Because `BitBox` is a fully-owned buffer, it is able to operate on its memory 91 without concern for any other views that may alias. This enables it to 92 specialize some `BitSlice` behavior to be faster or more efficient. 93 94 # Type Parameters 95 96 This takes the same two type parameters, `O: BitOrder` and `T: BitStore`, as 97 `BitSlice`. 98 99 # Safety 100 101 Like `BitSlice`, `BitBox` is exactly equal in size to `Box<[bool]>`, and is also 102 absolutely representation-incompatible with it. You must never attempt to 103 type-cast between `Box<[bool]>` and `BitBox` in any way, nor attempt to modify 104 the memory value of a `BitBox` handle. Doing so will cause allocator and memory 105 errors in your program, likely inducing a panic. 106 107 Everything in the `BitBox` public API, even the `unsafe` parts, are guaranteed 108 to have no more unsafety than their equivalent items in the standard library. 109 All `unsafe` APIs will have documentation explicitly detailing what the API 110 requires you to uphold in order for it to function safely and correctly. All 111 safe APIs will do so themselves. 112 113 # Performance 114 115 Iteration over the buffer is governed by the `BitSlice` characteristics on the 116 type parameter. You are generally better off using larger types when your buffer 117 is a data collection rather than a specific I/O protocol buffer. 118 119 # Macro Construction 120 121 Heap allocation can only occur at runtime, but the [`bitbox!`] macro will 122 construct an appropriate `BitSlice` buffer at compile-time, and at run-time, 123 only copy the buffer into a heap allocation. 124 125 [`BitArray`]: ../array/struct.BitArray.html 126 [`BitSlice`]: ../slice/struct.BitSlice.html 127 [`BitVec`]: ../vec/struct.BitVec.html 128 [`bitbox!`]: ../macro.bitbox.html 129 **/ 130 #[repr(transparent)] 131 pub struct BitBox<O = Lsb0, T = usize> 132 where 133 O: BitOrder, 134 T: BitStore, 135 { 136 pointer: NonNull<BitSlice<O, T>>, 137 } 138 139 /// Methods specific to `BitBox<_, T>`, and not present on `Box<[T]>`. 140 impl<O, T> BitBox<O, T> 141 where 142 O: BitOrder, 143 T: BitStore, 144 { 145 /// Clones a `&BitSlice` into a `BitVec`. 146 /// 147 /// # Original 148 /// 149 /// [`<Box<T: Clone> as Clone>::clone`](https://doc.rust-lang.org/alloc/boxed/struct.Box.html#impl-Clone) 150 /// 151 /// # Effects 152 /// 153 /// This performs a direct element-wise copy from the source slice to the 154 /// newly-allocated buffer, then sets the box to have the same starting bit 155 /// as the slice did. This allows for faster behavior. 156 /// 157 /// # Examples 158 /// 159 /// ```rust 160 /// use bitvec::prelude::*; 161 /// 162 /// let bits = bits![0, 1, 0, 1, 1, 0, 1, 1]; 163 /// let bb = BitBox::from_bitslice(&bits[2 ..]); 164 /// assert_eq!(bb, bits[2 ..]); 165 /// ``` 166 #[inline] 167 #[cfg(not(tarpaulin_include))] from_bitslice(slice: &BitSlice<O, T>) -> Self168 pub fn from_bitslice(slice: &BitSlice<O, T>) -> Self { 169 slice.to_bitvec().into_boxed_bitslice() 170 } 171 172 /// Converts a `Box<[T]>` into a `BitBox`<O, T>` without copying its buffer. 173 /// 174 /// # Parameters 175 /// 176 /// - `boxed`: A boxed slice to view as bits. 177 /// 178 /// # Returns 179 /// 180 /// A `BitBox` over the `boxed` buffer. 181 /// 182 /// # Panics 183 /// 184 /// This panics if `boxed` is too long to convert into a `BitBox`. See 185 /// [`BitSlice::MAX_ELTS`]. 186 /// 187 /// # Examples 188 /// 189 /// ```rust 190 /// use bitvec::prelude::*; 191 /// 192 /// let boxed: Box<[u8]> = Box::new([0; 4]); 193 /// let bb = BitBox::<LocalBits, _>::from_boxed_slice(boxed); 194 /// assert_eq!(bb, bits![0; 32]); 195 /// ``` 196 /// 197 /// [`BitSlice::MAX_ELTS`]: 198 /// ../slice/struct.BitSlice.html#associatedconstant.MAX_ELTS 199 #[inline] from_boxed_slice(boxed: Box<[T]>) -> Self200 pub fn from_boxed_slice(boxed: Box<[T]>) -> Self { 201 Self::try_from_boxed_slice(boxed) 202 .expect("Slice was too long to be converted into a `BitBox`") 203 } 204 205 /// Converts a `Box<[T]>` into a `BitBox<O, T>` without copying its buffer. 206 /// 207 /// This method takes ownership of a memory buffer and enables it to be used 208 /// as a bit-box. Because `Box<[T]>` can be longer than `BitBox`es, this is 209 /// a fallible method, and the original box will be returned if it cannot be 210 /// converted. 211 /// 212 /// # Parameters 213 /// 214 /// - `boxed`: Some boxed slice of memory, to be viewed as bits. 215 /// 216 /// # Returns 217 /// 218 /// If `boxed` is short enough to be viewed as a `BitBox`, then this returns 219 /// a `BitBox` over the `boxed` buffer. If `boxed` is too long, then this 220 /// returns `boxed` unmodified. 221 /// 222 /// # Examples 223 /// 224 /// ```rust 225 /// use bitvec::prelude::*; 226 /// 227 /// let boxed: Box<[u8]> = Box::new([0; 4]); 228 /// let bb = BitBox::<LocalBits, _>::try_from_boxed_slice(boxed).unwrap(); 229 /// assert_eq!(bb[..], bits![0; 32]); 230 /// ``` 231 #[inline] try_from_boxed_slice(boxed: Box<[T]>) -> Result<Self, Box<[T]>>232 pub fn try_from_boxed_slice(boxed: Box<[T]>) -> Result<Self, Box<[T]>> { 233 let len = boxed.len(); 234 if len > BitSlice::<O, T>::MAX_ELTS { 235 return Err(boxed); 236 } 237 238 let boxed = ManuallyDrop::new(boxed); 239 let base = boxed.as_ptr(); 240 Ok(Self { 241 pointer: unsafe { 242 BitPtr::new_unchecked( 243 base, 244 BitIdx::ZERO, 245 len * T::Mem::BITS as usize, 246 ) 247 } 248 .to_nonnull(), 249 }) 250 } 251 252 /// Converts the slice back into an ordinary slice of memory elements. 253 /// 254 /// This does not affect the slice’s buffer, only the handle used to control 255 /// it. 256 /// 257 /// # Parameters 258 /// 259 /// - `self` 260 /// 261 /// # Returns 262 /// 263 /// An ordinary boxed slice containing all of the bit-slice’s memory buffer. 264 /// 265 /// # Examples 266 /// 267 /// ```rust 268 /// use bitvec::prelude::*; 269 /// 270 /// let bb = bitbox![0; 5]; 271 /// let boxed = bb.into_boxed_slice(); 272 /// assert_eq!(boxed[..], [0][..]); 273 /// ``` 274 #[inline] into_boxed_slice(self) -> Box<[T]>275 pub fn into_boxed_slice(self) -> Box<[T]> { 276 let mut this = ManuallyDrop::new(self); 277 unsafe { Box::from_raw(this.as_mut_slice()) } 278 } 279 280 /// Views the buffer’s contents as a `BitSlice`. 281 /// 282 /// This is equivalent to `&bb[..]`. 283 /// 284 /// # Original 285 /// 286 /// [`<Box<[T]> as AsRef<[T]>>::as_ref`](https://doc.rust-lang.org/alloc/boxed/struct.Box.html#impl-AsRef%3CT%3E) 287 /// 288 /// # Examples 289 /// 290 /// ```rust 291 /// use bitvec::prelude::*; 292 /// 293 /// let bb = bitbox![0, 1, 1, 0]; 294 /// let bits = bb.as_bitslice(); 295 /// ``` 296 #[inline] 297 #[cfg(not(tarpaulin_include))] as_bitslice(&self) -> &BitSlice<O, T>298 pub fn as_bitslice(&self) -> &BitSlice<O, T> { 299 self.bitptr().to_bitslice_ref() 300 } 301 302 /// Extracts a mutable bit-slice of the entire vector. 303 /// 304 /// Equivalent to `&mut bv[..]`. 305 /// 306 /// # Original 307 /// 308 /// [`<Box<[T]> as AsMut<[T]>>::as_mut`](https://doc.rust-lang.org/alloc/boxed/struct.Box.html#impl-AsMut%3CT%3E) 309 /// 310 /// # Examples 311 /// 312 /// ```rust 313 /// use bitvec::prelude::*; 314 /// 315 /// let mut bv = bitvec![0, 1, 0, 1]; 316 /// let bits = bv.as_mut_bitslice(); 317 /// bits.set(0, true); 318 /// ``` 319 #[inline] 320 #[cfg(not(tarpaulin_include))] as_mut_bitslice(&mut self) -> &mut BitSlice<O, T>321 pub fn as_mut_bitslice(&mut self) -> &mut BitSlice<O, T> { 322 self.bitptr().to_bitslice_mut() 323 } 324 325 /// Extracts an element slice containing the entire box. 326 /// 327 /// # Original 328 /// 329 /// [`<Box<[T]> as AsRef<[T]>>::as_ref`](https://doc.rust-lang.org/alloc/boxed/struct.Box.html#impl-AsRef%3CT%3E) 330 /// 331 /// # Analogue 332 /// 333 /// See [`as_bitslice`] for a `&BitBox -> &BitSlice` transform. 334 /// 335 /// # Examples 336 /// 337 /// ```rust 338 /// # #[cfg(feature = "std")] { 339 /// use bitvec::prelude::*; 340 /// use std::io::{self, Write}; 341 /// let buffer = bitbox![Msb0, u8; 0, 1, 0, 1, 1, 0, 0, 0]; 342 /// io::sink().write(buffer.as_slice()).unwrap(); 343 /// # } 344 /// ``` 345 /// 346 /// [`as_bitslice`]: #method.as_bitslice 347 #[inline] as_slice(&self) -> &[T]348 pub fn as_slice(&self) -> &[T] { 349 let bitptr = self.bitptr(); 350 let (base, elts) = (bitptr.pointer().to_const(), bitptr.elements()); 351 unsafe { slice::from_raw_parts(base, elts) } 352 } 353 354 /// Extracts a mutable slice of the entire box. 355 /// 356 /// # Original 357 /// 358 /// [`<Box<[T]> as AsMut<[T]>>::as_mut`](https://doc.rust-lang.org/alloc/boxed/struct.Box.html#impl-AsMut%3CT%3E) 359 /// 360 /// # Analogue 361 /// 362 /// See [`as_mut_bitslice`] for a `&mut BitBox -> &mut BitSlice` transform. 363 /// 364 /// # Examples 365 /// 366 /// ```rust 367 /// # #[cfg(feature = "std")] { 368 /// use bitvec::prelude::*; 369 /// use std::io::{self, Read}; 370 /// let mut buffer = bitbox![Msb0, u8; 0; 24]; 371 /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap(); 372 /// # } 373 /// ``` 374 /// 375 /// [`as_mut_bitslice`]: #method.as_mut_bitslice 376 #[inline] as_mut_slice(&mut self) -> &mut [T]377 pub fn as_mut_slice(&mut self) -> &mut [T] { 378 let bitptr = self.bitptr(); 379 let (base, elts) = (bitptr.pointer().to_mut(), bitptr.elements()); 380 unsafe { slice::from_raw_parts_mut(base, elts) } 381 } 382 383 /// Sets the uninitialized bits of the vector to a fixed value. 384 /// 385 /// This method modifies all bits in the allocated buffer that are outside 386 /// the `self.as_bitslice()` view so that they have a consistent value. This 387 /// can be used to zero the uninitialized memory so that when viewed as a 388 /// raw memory slice, bits outside the live region have a predictable value. 389 /// 390 /// # Examples 391 /// 392 /// ```rust 393 /// use bitvec::prelude::*; 394 /// 395 /// let mut bb = BitBox::new(&220u8.view_bits::<Lsb0>()[.. 4]); 396 /// assert_eq!(bb.count_ones(), 2); 397 /// assert_eq!(bb.as_slice(), &[220u8]); 398 /// 399 /// bb.set_uninitialized(false); 400 /// assert_eq!(bb.as_slice(), &[12u8]); 401 /// 402 /// bb.set_uninitialized(true); 403 /// assert_eq!(bb.as_slice(), &[!3u8]); 404 /// ``` 405 #[inline] set_uninitialized(&mut self, value: bool)406 pub fn set_uninitialized(&mut self, value: bool) { 407 let head = self.bitptr().head().value() as usize; 408 let tail = head + self.len(); 409 let elts = self.bitptr().elements() * T::Mem::BITS as usize; 410 let mut bp = self.bitptr(); 411 unsafe { 412 bp.set_head(BitIdx::ZERO); 413 bp.set_len(elts); 414 let bits = bp.to_bitslice_mut::<O>(); 415 bits.get_unchecked_mut(.. head).set_all(value); 416 bits.get_unchecked_mut(tail ..).set_all(value); 417 } 418 } 419 420 #[inline] bitptr(&self) -> BitPtr<T>421 pub(crate) fn bitptr(&self) -> BitPtr<T> { 422 self.pointer.as_ptr().pipe(BitPtr::from_bitslice_ptr_mut) 423 } 424 425 /// Permits a function to modify the `Box<[T]>` backing storage of a 426 /// `BitBox<_, T>`. 427 /// 428 /// This produces a temporary `Box<[T::Mem]>` structure governing the 429 /// `BitBox`’s buffer and allows a function to view it mutably. After the 430 /// callback returns, the `Box` is written back into `self` and forgotten. 431 /// 432 /// # Type Parameters 433 /// 434 /// - `F`: A function which operates on a mutable borrow of a 435 /// `Box<[T::Mem]>` buffer controller. 436 /// - `R`: The return type of the `F` function. 437 /// 438 /// # Parameters 439 /// 440 /// - `&mut self` 441 /// - `func`: A function which receives a mutable borrow of a 442 /// `Box<[T::Mem]>` controlling `self`’s buffer. 443 /// 444 /// # Returns 445 /// 446 /// The return value of `func`. `func` is forbidden from borrowing any part 447 /// of the `Box<[T::Mem]>` temporary view. with_box<F, R>(&mut self, func: F) -> R where F: FnOnce(&mut ManuallyDrop<Box<[T::Mem]>>) -> R448 fn with_box<F, R>(&mut self, func: F) -> R 449 where F: FnOnce(&mut ManuallyDrop<Box<[T::Mem]>>) -> R { 450 self.as_mut_slice() 451 .pipe(|s| s as *mut [T] as *mut [T::Mem]) 452 .pipe(|raw| unsafe { Box::from_raw(raw) }) 453 .pipe(ManuallyDrop::new) 454 .pipe_mut(func) 455 } 456 } 457 458 mod api; 459 mod ops; 460 mod traits; 461 462 #[cfg(test)] 463 mod tests; 464