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