1 //! Provides the abstraction of a bit field, which allows for bit-level update and retrieval
2 //! operations.
3
4 #![no_std]
5
6 #[cfg(test)]
7 mod tests;
8
9 use core::ops::{Bound, Range, RangeBounds};
10
11 /// A generic trait which provides methods for extracting and setting specific bits or ranges of
12 /// bits.
13 pub trait BitField {
14 /// The number of bits in this bit field.
15 ///
16 /// ```rust
17 /// use bit_field::BitField;
18 ///
19 /// assert_eq!(u32::BIT_LENGTH, 32);
20 /// assert_eq!(u64::BIT_LENGTH, 64);
21 /// ```
22 const BIT_LENGTH: usize;
23
24 /// Obtains the bit at the index `bit`; note that index 0 is the least significant bit, while
25 /// index `length() - 1` is the most significant bit.
26 ///
27 /// ```rust
28 /// use bit_field::BitField;
29 ///
30 /// let value: u32 = 0b110101;
31 ///
32 /// assert_eq!(value.get_bit(1), false);
33 /// assert_eq!(value.get_bit(2), true);
34 /// ```
35 ///
36 /// ## Panics
37 ///
38 /// This method will panic if the bit index is out of bounds of the bit field.
get_bit(&self, bit: usize) -> bool39 fn get_bit(&self, bit: usize) -> bool;
40
41 /// Obtains the range of bits specified by `range`; note that index 0 is the least significant
42 /// bit, while index `length() - 1` is the most significant bit.
43 ///
44 /// ```rust
45 /// use bit_field::BitField;
46 ///
47 /// let value: u32 = 0b110101;
48 ///
49 /// assert_eq!(value.get_bits(0..3), 0b101);
50 /// assert_eq!(value.get_bits(2..6), 0b1101);
51 /// assert_eq!(value.get_bits(..), 0b110101);
52 /// assert_eq!(value.get_bits(3..=3), value.get_bit(3) as u32);
53 /// ```
54 ///
55 /// ## Panics
56 ///
57 /// This method will panic if the start or end indexes of the range are out of bounds of the
58 /// bit field.
get_bits<T: RangeBounds<usize>>(&self, range: T) -> Self59 fn get_bits<T: RangeBounds<usize>>(&self, range: T) -> Self;
60
61 /// Sets the bit at the index `bit` to the value `value` (where true means a value of '1' and
62 /// false means a value of '0'); note that index 0 is the least significant bit, while index
63 /// `length() - 1` is the most significant bit.
64 ///
65 /// ```rust
66 /// use bit_field::BitField;
67 ///
68 /// let mut value = 0u32;
69 ///
70 /// value.set_bit(1, true);
71 /// assert_eq!(value, 2u32);
72 ///
73 /// value.set_bit(3, true);
74 /// assert_eq!(value, 10u32);
75 ///
76 /// value.set_bit(1, false);
77 /// assert_eq!(value, 8u32);
78 /// ```
79 ///
80 /// ## Panics
81 ///
82 /// This method will panic if the bit index is out of the bounds of the bit field.
set_bit(&mut self, bit: usize, value: bool) -> &mut Self83 fn set_bit(&mut self, bit: usize, value: bool) -> &mut Self;
84
85 /// Sets the range of bits defined by the range `range` to the lower bits of `value`; to be
86 /// specific, if the range is N bits long, the N lower bits of `value` will be used; if any of
87 /// the other bits in `value` are set to 1, this function will panic.
88 ///
89 /// ```rust
90 /// use bit_field::BitField;
91 ///
92 /// let mut value = 0u32;
93 ///
94 /// value.set_bits(0..2, 0b11);
95 /// assert_eq!(value, 0b11);
96 ///
97 /// value.set_bits(2..=3, 0b11);
98 /// assert_eq!(value, 0b1111);
99 ///
100 /// value.set_bits(..4, 0b1010);
101 /// assert_eq!(value, 0b1010);
102 /// ```
103 ///
104 /// ## Panics
105 ///
106 /// This method will panic if the range is out of bounds of the bit field, or if there are `1`s
107 /// not in the lower N bits of `value`.
set_bits<T: RangeBounds<usize>>(&mut self, range: T, value: Self) -> &mut Self108 fn set_bits<T: RangeBounds<usize>>(&mut self, range: T, value: Self) -> &mut Self;
109 }
110
111 pub trait BitArray<T: BitField> {
112 /// Returns the length, eg number of bits, in this bit array.
113 ///
114 /// ```rust
115 /// use bit_field::BitArray;
116 ///
117 /// assert_eq!([0u8, 4u8, 8u8].bit_length(), 24);
118 /// assert_eq!([0u32, 5u32].bit_length(), 64);
119 /// ```
bit_length(&self) -> usize120 fn bit_length(&self) -> usize;
121
122 /// Obtains the bit at the index `bit`; note that index 0 is the least significant bit, while
123 /// index `length() - 1` is the most significant bit.
124 ///
125 /// ```rust
126 /// use bit_field::BitArray;
127 ///
128 /// let value: [u32; 1] = [0b110101];
129 ///
130 /// assert_eq!(value.get_bit(1), false);
131 /// assert_eq!(value.get_bit(2), true);
132 /// ```
133 ///
134 /// ## Panics
135 ///
136 /// This method will panic if the bit index is out of bounds of the bit array.
get_bit(&self, bit: usize) -> bool137 fn get_bit(&self, bit: usize) -> bool;
138
139 /// Obtains the range of bits specified by `range`; note that index 0 is the least significant
140 /// bit, while index `length() - 1` is the most significant bit.
141 ///
142 /// ```rust
143 /// use bit_field::BitArray;
144 ///
145 /// let value: [u32; 2] = [0b110101, 0b11];
146 ///
147 /// assert_eq!(value.get_bits(0..3), 0b101);
148 /// assert_eq!(value.get_bits(..6), 0b110101);
149 /// assert_eq!(value.get_bits(31..33), 0b10);
150 /// assert_eq!(value.get_bits(5..=32), 0b1_0000_0000_0000_0000_0000_0000_001);
151 /// assert_eq!(value.get_bits(34..), 0);
152 /// ```
153 ///
154 /// ## Panics
155 ///
156 /// This method will panic if the start or end indexes of the range are out of bounds of the
157 /// bit array, or if the range can't be contained by the bit field T.
get_bits<U: RangeBounds<usize>>(&self, range: U) -> T158 fn get_bits<U: RangeBounds<usize>>(&self, range: U) -> T;
159
160 /// Sets the bit at the index `bit` to the value `value` (where true means a value of '1' and
161 /// false means a value of '0'); note that index 0 is the least significant bit, while index
162 /// `length() - 1` is the most significant bit.
163 ///
164 /// ```rust
165 /// use bit_field::BitArray;
166 ///
167 /// let mut value = [0u32];
168 ///
169 /// value.set_bit(1, true);
170 /// assert_eq!(value, [2u32]);
171 ///
172 /// value.set_bit(3, true);
173 /// assert_eq!(value, [10u32]);
174 ///
175 /// value.set_bit(1, false);
176 /// assert_eq!(value, [8u32]);
177 /// ```
178 ///
179 /// ## Panics
180 ///
181 /// This method will panic if the bit index is out of the bounds of the bit array.
set_bit(&mut self, bit: usize, value: bool)182 fn set_bit(&mut self, bit: usize, value: bool);
183
184 /// Sets the range of bits defined by the range `range` to the lower bits of `value`; to be
185 /// specific, if the range is N bits long, the N lower bits of `value` will be used; if any of
186 /// the other bits in `value` are set to 1, this function will panic.
187 ///
188 /// ```rust
189 /// use bit_field::BitArray;
190 ///
191 /// let mut value = [0u32, 0u32];
192 ///
193 /// value.set_bits(0..2, 0b11);
194 /// assert_eq!(value, [0b11, 0u32]);
195 ///
196 /// value.set_bits(31..35, 0b1010);
197 /// assert_eq!(value, [0x0003, 0b101]);
198 /// ```
199 ///
200 /// ## Panics
201 ///
202 /// This method will panic if the range is out of bounds of the bit array,
203 /// if the range can't be contained by the bit field T, or if there are `1`s
204 /// not in the lower N bits of `value`.
set_bits<U: RangeBounds<usize>>(&mut self, range: U, value: T)205 fn set_bits<U: RangeBounds<usize>>(&mut self, range: U, value: T);
206 }
207
208 /// An internal macro used for implementing BitField on the standard integral types.
209 macro_rules! bitfield_numeric_impl {
210 ($($t:ty)*) => ($(
211 impl BitField for $t {
212 const BIT_LENGTH: usize = ::core::mem::size_of::<Self>() as usize * 8;
213
214 #[track_caller]
215 #[inline]
216 fn get_bit(&self, bit: usize) -> bool {
217 assert!(bit < Self::BIT_LENGTH);
218
219 (*self & (1 << bit)) != 0
220 }
221
222 #[track_caller]
223 #[inline]
224 fn get_bits<T: RangeBounds<usize>>(&self, range: T) -> Self {
225 let range = to_regular_range(&range, Self::BIT_LENGTH);
226
227 assert!(range.start < Self::BIT_LENGTH);
228 assert!(range.end <= Self::BIT_LENGTH);
229 assert!(range.start < range.end);
230
231 // shift away high bits
232 let bits = *self << (Self::BIT_LENGTH - range.end) >> (Self::BIT_LENGTH - range.end);
233
234 // shift away low bits
235 bits >> range.start
236 }
237
238 #[track_caller]
239 #[inline]
240 fn set_bit(&mut self, bit: usize, value: bool) -> &mut Self {
241 assert!(bit < Self::BIT_LENGTH);
242
243 if value {
244 *self |= 1 << bit;
245 } else {
246 *self &= !(1 << bit);
247 }
248
249 self
250 }
251
252 #[track_caller]
253 #[inline]
254 fn set_bits<T: RangeBounds<usize>>(&mut self, range: T, value: Self) -> &mut Self {
255 let range = to_regular_range(&range, Self::BIT_LENGTH);
256
257 assert!(range.start < Self::BIT_LENGTH);
258 assert!(range.end <= Self::BIT_LENGTH);
259 assert!(range.start < range.end);
260 assert!(value << (Self::BIT_LENGTH - (range.end - range.start)) >>
261 (Self::BIT_LENGTH - (range.end - range.start)) == value,
262 "value does not fit into bit range");
263
264 let bitmask: Self = !(!0 << (Self::BIT_LENGTH - range.end) >>
265 (Self::BIT_LENGTH - range.end) >>
266 range.start << range.start);
267
268 // set bits
269 *self = (*self & bitmask) | (value << range.start);
270
271 self
272 }
273 }
274 )*)
275 }
276
277 bitfield_numeric_impl! { u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize }
278
279 impl<T: BitField> BitArray<T> for [T] {
280 #[inline]
bit_length(&self) -> usize281 fn bit_length(&self) -> usize {
282 self.len() * T::BIT_LENGTH
283 }
284
285 #[track_caller]
286 #[inline]
get_bit(&self, bit: usize) -> bool287 fn get_bit(&self, bit: usize) -> bool {
288 let slice_index = bit / T::BIT_LENGTH;
289 let bit_index = bit % T::BIT_LENGTH;
290 self[slice_index].get_bit(bit_index)
291 }
292
293 #[track_caller]
294 #[inline]
get_bits<U: RangeBounds<usize>>(&self, range: U) -> T295 fn get_bits<U: RangeBounds<usize>>(&self, range: U) -> T {
296 let range = to_regular_range(&range, self.bit_length());
297
298 assert!(range.len() <= T::BIT_LENGTH);
299
300 let slice_start = range.start / T::BIT_LENGTH;
301 let slice_end = range.end / T::BIT_LENGTH;
302 let bit_start = range.start % T::BIT_LENGTH;
303 let bit_end = range.end % T::BIT_LENGTH;
304 let len = range.len();
305
306 assert!(slice_end - slice_start <= 1);
307
308 if slice_start == slice_end {
309 self[slice_start].get_bits(bit_start..bit_end)
310 } else if bit_end == 0 {
311 self[slice_start].get_bits(bit_start..T::BIT_LENGTH)
312 } else {
313 let mut ret = self[slice_start].get_bits(bit_start..T::BIT_LENGTH);
314 ret.set_bits(
315 (T::BIT_LENGTH - bit_start)..len,
316 self[slice_end].get_bits(0..bit_end),
317 );
318 ret
319 }
320 }
321
322 #[track_caller]
323 #[inline]
set_bit(&mut self, bit: usize, value: bool)324 fn set_bit(&mut self, bit: usize, value: bool) {
325 let slice_index = bit / T::BIT_LENGTH;
326 let bit_index = bit % T::BIT_LENGTH;
327 self[slice_index].set_bit(bit_index, value);
328 }
329
330 #[track_caller]
331 #[inline]
set_bits<U: RangeBounds<usize>>(&mut self, range: U, value: T)332 fn set_bits<U: RangeBounds<usize>>(&mut self, range: U, value: T) {
333 let range = to_regular_range(&range, self.bit_length());
334
335 assert!(range.len() <= T::BIT_LENGTH);
336
337 let slice_start = range.start / T::BIT_LENGTH;
338 let slice_end = range.end / T::BIT_LENGTH;
339 let bit_start = range.start % T::BIT_LENGTH;
340 let bit_end = range.end % T::BIT_LENGTH;
341
342 assert!(slice_end - slice_start <= 1);
343
344 if slice_start == slice_end {
345 self[slice_start].set_bits(bit_start..bit_end, value);
346 } else if bit_end == 0 {
347 self[slice_start].set_bits(bit_start..T::BIT_LENGTH, value);
348 } else {
349 self[slice_start].set_bits(
350 bit_start..T::BIT_LENGTH,
351 value.get_bits(0..T::BIT_LENGTH - bit_start),
352 );
353 self[slice_end].set_bits(
354 0..bit_end,
355 value.get_bits(T::BIT_LENGTH - bit_start..T::BIT_LENGTH),
356 );
357 }
358 }
359 }
360
to_regular_range<T: RangeBounds<usize>>(generic_rage: &T, bit_length: usize) -> Range<usize>361 fn to_regular_range<T: RangeBounds<usize>>(generic_rage: &T, bit_length: usize) -> Range<usize> {
362 let start = match generic_rage.start_bound() {
363 Bound::Excluded(&value) => value + 1,
364 Bound::Included(&value) => value,
365 Bound::Unbounded => 0,
366 };
367 let end = match generic_rage.end_bound() {
368 Bound::Excluded(&value) => value,
369 Bound::Included(&value) => value + 1,
370 Bound::Unbounded => bit_length,
371 };
372
373 start..end
374 }
375