1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
//! Provides the abstraction of a bit field, which allows for bit-level update and retrieval
//! operations.

#![no_std]

#[cfg(test)]
mod tests;

use core::ops::{Bound, Range, RangeBounds};

/// A generic trait which provides methods for extracting and setting specific bits or ranges of
/// bits.
pub trait BitField {
    /// The number of bits in this bit field.
    ///
    /// ```rust
    /// use bit_field::BitField;
    ///
    /// assert_eq!(u32::BIT_LENGTH, 32);
    /// assert_eq!(u64::BIT_LENGTH, 64);
    /// ```
    const BIT_LENGTH: usize;

    /// Obtains the bit at the index `bit`; note that index 0 is the least significant bit, while
    /// index `length() - 1` is the most significant bit.
    ///
    /// ```rust
    /// use bit_field::BitField;
    ///
    /// let value: u32 = 0b110101;
    ///
    /// assert_eq!(value.get_bit(1), false);
    /// assert_eq!(value.get_bit(2), true);
    /// ```
    ///
    /// ## Panics
    ///
    /// This method will panic if the bit index is out of bounds of the bit field.
    fn get_bit(&self, bit: usize) -> bool;

    /// Obtains the range of bits specified by `range`; note that index 0 is the least significant
    /// bit, while index `length() - 1` is the most significant bit.
    ///
    /// ```rust
    /// use bit_field::BitField;
    ///
    /// let value: u32 = 0b110101;
    ///
    /// assert_eq!(value.get_bits(0..3), 0b101);
    /// assert_eq!(value.get_bits(2..6), 0b1101);
    /// assert_eq!(value.get_bits(..), 0b110101);
    /// assert_eq!(value.get_bits(3..=3), value.get_bit(3) as u32);
    /// ```
    ///
    /// ## Panics
    ///
    /// This method will panic if the start or end indexes of the range are out of bounds of the
    /// bit field.
    fn get_bits<T: RangeBounds<usize>>(&self, range: T) -> Self;

    /// Sets the bit at the index `bit` to the value `value` (where true means a value of '1' and
    /// false means a value of '0'); note that index 0 is the least significant bit, while index
    /// `length() - 1` is the most significant bit.
    ///
    /// ```rust
    /// use bit_field::BitField;
    ///
    /// let mut value = 0u32;
    ///
    /// value.set_bit(1, true);
    /// assert_eq!(value, 2u32);
    ///
    /// value.set_bit(3, true);
    /// assert_eq!(value, 10u32);
    ///
    /// value.set_bit(1, false);
    /// assert_eq!(value, 8u32);
    /// ```
    ///
    /// ## Panics
    ///
    /// This method will panic if the bit index is out of the bounds of the bit field.
    fn set_bit(&mut self, bit: usize, value: bool) -> &mut Self;

    /// Sets the range of bits defined by the range `range` to the lower bits of `value`; to be
    /// specific, if the range is N bits long, the N lower bits of `value` will be used; if any of
    /// the other bits in `value` are set to 1, this function will panic.
    ///
    /// ```rust
    /// use bit_field::BitField;
    ///
    /// let mut value = 0u32;
    ///
    /// value.set_bits(0..2, 0b11);
    /// assert_eq!(value, 0b11);
    ///
    /// value.set_bits(2..=3, 0b11);
    /// assert_eq!(value, 0b1111);
    ///
    /// value.set_bits(..4, 0b1010);
    /// assert_eq!(value, 0b1010);
    /// ```
    ///
    /// ## Panics
    ///
    /// This method will panic if the range is out of bounds of the bit field, or if there are `1`s
    /// not in the lower N bits of `value`.
    fn set_bits<T: RangeBounds<usize>>(&mut self, range: T, value: Self) -> &mut Self;
}

pub trait BitArray<T: BitField> {
    /// Returns the length, eg number of bits, in this bit array.
    ///
    /// ```rust
    /// use bit_field::BitArray;
    ///
    /// assert_eq!([0u8, 4u8, 8u8].bit_length(), 24);
    /// assert_eq!([0u32, 5u32].bit_length(), 64);
    /// ```
    fn bit_length(&self) -> usize;

    /// Obtains the bit at the index `bit`; note that index 0 is the least significant bit, while
    /// index `length() - 1` is the most significant bit.
    ///
    /// ```rust
    /// use bit_field::BitArray;
    ///
    /// let value: [u32; 1] = [0b110101];
    ///
    /// assert_eq!(value.get_bit(1), false);
    /// assert_eq!(value.get_bit(2), true);
    /// ```
    ///
    /// ## Panics
    ///
    /// This method will panic if the bit index is out of bounds of the bit array.
    fn get_bit(&self, bit: usize) -> bool;

    /// Obtains the range of bits specified by `range`; note that index 0 is the least significant
    /// bit, while index `length() - 1` is the most significant bit.
    ///
    /// ```rust
    /// use bit_field::BitArray;
    ///
    /// let value: [u32; 2] = [0b110101, 0b11];
    ///
    /// assert_eq!(value.get_bits(0..3), 0b101);
    /// assert_eq!(value.get_bits(..6), 0b110101);
    /// assert_eq!(value.get_bits(31..33), 0b10);
    /// assert_eq!(value.get_bits(5..=32), 0b1_0000_0000_0000_0000_0000_0000_001);
    /// assert_eq!(value.get_bits(34..), 0);
    /// ```
    ///
    /// ## Panics
    ///
    /// This method will panic if the start or end indexes of the range are out of bounds of the
    /// bit array, or if the range can't be contained by the bit field T.
    fn get_bits<U: RangeBounds<usize>>(&self, range: U) -> T;

    /// Sets the bit at the index `bit` to the value `value` (where true means a value of '1' and
    /// false means a value of '0'); note that index 0 is the least significant bit, while index
    /// `length() - 1` is the most significant bit.
    ///
    /// ```rust
    /// use bit_field::BitArray;
    ///
    /// let mut value = [0u32];
    ///
    /// value.set_bit(1, true);
    /// assert_eq!(value, [2u32]);
    ///
    /// value.set_bit(3, true);
    /// assert_eq!(value, [10u32]);
    ///
    /// value.set_bit(1, false);
    /// assert_eq!(value, [8u32]);
    /// ```
    ///
    /// ## Panics
    ///
    /// This method will panic if the bit index is out of the bounds of the bit array.
    fn set_bit(&mut self, bit: usize, value: bool);

    /// Sets the range of bits defined by the range `range` to the lower bits of `value`; to be
    /// specific, if the range is N bits long, the N lower bits of `value` will be used; if any of
    /// the other bits in `value` are set to 1, this function will panic.
    ///
    /// ```rust
    /// use bit_field::BitArray;
    ///
    /// let mut value = [0u32, 0u32];
    ///
    /// value.set_bits(0..2, 0b11);
    /// assert_eq!(value, [0b11, 0u32]);
    ///
    /// value.set_bits(31..35, 0b1010);
    /// assert_eq!(value, [0x0003, 0b101]);
    /// ```
    ///
    /// ## Panics
    ///
    /// This method will panic if the range is out of bounds of the bit array,
    /// if the range can't be contained by the bit field T, or if there are `1`s
    /// not in the lower N bits of `value`.
    fn set_bits<U: RangeBounds<usize>>(&mut self, range: U, value: T);
}

/// An internal macro used for implementing BitField on the standard integral types.
macro_rules! bitfield_numeric_impl {
    ($($t:ty)*) => ($(
        impl BitField for $t {
            const BIT_LENGTH: usize = ::core::mem::size_of::<Self>() as usize * 8;

            #[inline]
            fn get_bit(&self, bit: usize) -> bool {
                assert!(bit < Self::BIT_LENGTH);

                (*self & (1 << bit)) != 0
            }

            #[inline]
            fn get_bits<T: RangeBounds<usize>>(&self, range: T) -> Self {
                let range = to_regular_range(&range, Self::BIT_LENGTH);

                assert!(range.start < Self::BIT_LENGTH);
                assert!(range.end <= Self::BIT_LENGTH);
                assert!(range.start < range.end);

                // shift away high bits
                let bits = *self << (Self::BIT_LENGTH - range.end) >> (Self::BIT_LENGTH - range.end);

                // shift away low bits
                bits >> range.start
            }

            #[inline]
            fn set_bit(&mut self, bit: usize, value: bool) -> &mut Self {
                assert!(bit < Self::BIT_LENGTH);

                if value {
                    *self |= 1 << bit;
                } else {
                    *self &= !(1 << bit);
                }

                self
            }

            #[inline]
            fn set_bits<T: RangeBounds<usize>>(&mut self, range: T, value: Self) -> &mut Self {
                let range = to_regular_range(&range, Self::BIT_LENGTH);

                assert!(range.start < Self::BIT_LENGTH);
                assert!(range.end <= Self::BIT_LENGTH);
                assert!(range.start < range.end);
                assert!(value << (Self::BIT_LENGTH - (range.end - range.start)) >>
                        (Self::BIT_LENGTH - (range.end - range.start)) == value,
                        "value does not fit into bit range");

                let bitmask: Self = !(!0 << (Self::BIT_LENGTH - range.end) >>
                                    (Self::BIT_LENGTH - range.end) >>
                                    range.start << range.start);

                // set bits
                *self = (*self & bitmask) | (value << range.start);

                self
            }
        }
    )*)
}

bitfield_numeric_impl! { u8 u16 u32 u64 usize i8 i16 i32 i64 isize }

impl<T: BitField> BitArray<T> for [T] {
    #[inline]
    fn bit_length(&self) -> usize {
        self.len() * T::BIT_LENGTH
    }

    #[inline]
    fn get_bit(&self, bit: usize) -> bool {
        let slice_index = bit / T::BIT_LENGTH;
        let bit_index = bit % T::BIT_LENGTH;
        self[slice_index].get_bit(bit_index)
    }

    #[inline]
    fn get_bits<U: RangeBounds<usize>>(&self, range: U) -> T {
        let range = to_regular_range(&range, self.bit_length());

        assert!(range.len() <= T::BIT_LENGTH);

        let slice_start = range.start / T::BIT_LENGTH;
        let slice_end = range.end / T::BIT_LENGTH;
        let bit_start = range.start % T::BIT_LENGTH;
        let bit_end = range.end % T::BIT_LENGTH;
        let len = range.len();

        assert!(slice_end - slice_start <= 1);

        if slice_start == slice_end {
            self[slice_start].get_bits(bit_start..bit_end)
        } else if bit_end == 0 {
            self[slice_start].get_bits(bit_start..T::BIT_LENGTH)
        } else {
            let mut ret = self[slice_start].get_bits(bit_start..T::BIT_LENGTH);
            ret.set_bits(
                (T::BIT_LENGTH - bit_start)..len,
                self[slice_end].get_bits(0..bit_end),
            );
            ret
        }
    }

    #[inline]
    fn set_bit(&mut self, bit: usize, value: bool) {
        let slice_index = bit / T::BIT_LENGTH;
        let bit_index = bit % T::BIT_LENGTH;
        self[slice_index].set_bit(bit_index, value);
    }

    #[inline]
    fn set_bits<U: RangeBounds<usize>>(&mut self, range: U, value: T) {
        let range = to_regular_range(&range, self.bit_length());

        assert!(range.len() <= T::BIT_LENGTH);

        let slice_start = range.start / T::BIT_LENGTH;
        let slice_end = range.end / T::BIT_LENGTH;
        let bit_start = range.start % T::BIT_LENGTH;
        let bit_end = range.end % T::BIT_LENGTH;

        assert!(slice_end - slice_start <= 1);

        if slice_start == slice_end {
            self[slice_start].set_bits(bit_start..bit_end, value);
        } else if bit_end == 0 {
            self[slice_start].set_bits(bit_start..T::BIT_LENGTH, value);
        } else {
            self[slice_start].set_bits(
                bit_start..T::BIT_LENGTH,
                value.get_bits(0..T::BIT_LENGTH - bit_start),
            );
            self[slice_end].set_bits(
                0..bit_end,
                value.get_bits(T::BIT_LENGTH - bit_start..T::BIT_LENGTH),
            );
        }
    }
}

fn to_regular_range<T: RangeBounds<usize>>(generic_rage: &T, bit_length: usize) -> Range<usize> {
    let start = match generic_rage.start_bound() {
        Bound::Excluded(&value) => value + 1,
        Bound::Included(&value) => value,
        Bound::Unbounded => 0,
    };
    let end = match generic_rage.end_bound() {
        Bound::Excluded(&value) => value,
        Bound::Included(&value) => value + 1,
        Bound::Unbounded => bit_length,
    };

    start..end
}