bitm/
lib.rs

1#![doc = include_str!("../README.md")]
2
3mod rank_select;
4
5pub use rank_select::{RankSimple, ArrayWithRankSimple, RankSelect101111, ArrayWithRank101111,
6     Rank, Select, Select0, SelectForRank101111, Select0ForRank101111, select64, optimal_combined_sampling,
7     BinaryRankSearch, CombinedSampling, ConstCombinedSamplingDensity, AdaptiveCombinedSamplingDensity};
8
9mod bitvec;
10pub use bitvec::*;
11
12/// Returns ceil of `n/d`.
13#[inline(always)] pub const fn ceiling_div(n: usize, d: usize) -> usize { (n+d-1)/d }
14
15/// Returns the largest `how_many`-bit number, i.e. 0..01..1 mask with `how_many` ones. `how_many` must be in range [0, 63].
16#[inline(always)] pub const fn n_lowest_bits(how_many: u8) -> u64 { (1u64 << how_many).wrapping_sub(1) }
17
18/// Returns the largest `how_many`-bit number, i.e. 0..01..1 mask with `how_many` ones. `how_many` must be in range [1, 64].
19#[inline(always)] pub const fn n_lowest_bits_1_64(how_many: u8) -> u64 { u64::MAX >> (64-how_many) }
20
21/// Returns the largest `how_many`-bit number, i.e. 0..01..1 mask with `how_many` ones. `how_many` must be in range [0, 64].
22/// 
23/// It is a bit slower than [`n_lowest_bits`] and [`n_lowest_bits_1_64`].
24#[inline(always)] pub const fn n_lowest_bits_0_64(how_many: u8) -> u64 {
25    // 1u64.checked_shl(how_many as u32).unwrap_or(0).wrapping_sub(1) gives the same assembly (as version with how_many >= 64) but is not allowed in const fn
26    // version with how_many == 64 gives a bit different, very similar assembly
27    if how_many >= 64 { return u64::MAX; }
28    n_lowest_bits(how_many)
29}
30
31/// Calculates the minimal number of bits needed to store values from `0` to given `max_value`.
32///
33/// # Example
34///
35/// ```
36/// use bitm::bits_to_store;
37///
38/// assert_eq!(bits_to_store(0u8), 0);
39/// assert_eq!(bits_to_store(1u16), 1);
40/// assert_eq!(bits_to_store(7u32), 3);
41/// assert_eq!(bits_to_store(8u64), 4);
42/// ```
43#[inline] pub fn bits_to_store<V: Into<u64>>(max_value: V) -> u8 {
44    /*let max_value: u64 = max_value.into();
45    (if max_value.is_power_of_two() {
46        max_value.trailing_zeros()+1
47    } else {
48        max_value.checked_next_power_of_two().unwrap_or(0).trailing_zeros()
49    }) as u8*/
50    max_value.into().checked_ilog2().map_or(0, |v| v as u8+1)
51}
52
53/// Read at least 57 bits from `ptr`, beginning from `first_bit`.
54#[inline(always)]
55pub unsafe fn get_bits57(ptr: *const u8, first_bit: usize) -> u64 {
56    let ptr = ptr.add(first_bit / 8) as *const u64;
57    let v = ptr.read_unaligned();
58    v >> (first_bit % 8)
59}
60
61/// Write at least 57 lowest `value` bits to `ptr` buffer, beginning from `first_bit`, using bit-or operation.
62/// Appropriate fragment of buffer should be zeroed.
63#[inline(always)]
64pub unsafe fn init_bits57(ptr: *mut u8, first_bit: usize, value: u64) {
65    let ptr = ptr.add(first_bit / 8) as *mut u64;
66    let mut v = ptr.read_unaligned();
67    v |= value << (first_bit % 8);
68    ptr.write_unaligned(v);
69}
70
71/// Write desired number, at most 57 lowest `value` bits to `ptr`, beginning from `first_bit`, using bit-or operation.
72/// Before write, appropriate fragment of buffer is zeroed by bit-andn with `len_mask`
73/// (which should be of type 0..01..1, with desired number of bit ones).
74/// The most significant bits of `value` should be zeros.
75#[inline(always)]
76pub unsafe fn set_bits57(ptr: *mut u8, first_bit: usize, value: u64, len_mask: u64) {
77    let ptr = ptr.add(first_bit / 8) as *mut u64;
78    let mut v = ptr.read_unaligned();
79    let shift = first_bit % 8;
80    v &= !(len_mask << shift);
81    v |= value << shift;
82    ptr.write_unaligned(v);
83}
84
85/// Read at least 25 bits from `ptr`, beginning from `first_bit`.
86#[inline(always)]
87pub unsafe fn get_bits25(ptr: *const u8, first_bit: usize) -> u32 {
88    let ptr = ptr.add(first_bit / 8) as *const u32;
89    let v = ptr.read_unaligned();
90    v >> (first_bit % 8)
91}
92
93/// Write at least 25 lowest `value` bits to `ptr` buffer, beginning from `first_bit`, using bit-or operation.
94/// Appropriate fragment of buffer should be zeroed.
95#[inline(always)]
96pub unsafe fn init_bits25(ptr: *mut u8, first_bit: usize, value: u32) {
97    let ptr = ptr.add(first_bit / 8) as *mut u32;
98    let mut v = ptr.read_unaligned();
99    v |= value << (first_bit % 8);
100    ptr.write_unaligned(v);
101}
102
103/// Write desired number, at most 25 lowest `value` bits to `ptr`, beginning from `first_bit`, using bit-or operation.
104/// Before write, appropriate fragment of buffer is zeroed by bit-andn with `len_mask`
105/// (which should be of type 0..01..1, with desired number of bit ones).
106/// The most significant bits of `value` should be zeros.
107#[inline(always)]
108pub unsafe fn set_bits25(ptr: *mut u8, first_bit: usize, value: u32, len_mask: u32) {
109    let ptr = ptr.add(first_bit / 8) as *mut u32;
110    let mut v = ptr.read_unaligned();
111    let shift = first_bit % 8;
112    v &= !(len_mask << shift);
113    v |= value << shift;
114    ptr.write_unaligned(v);
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120
121    #[test]
122    fn test_div_up() {
123        assert_eq!(ceiling_div(7, 2), 4);
124        assert_eq!(ceiling_div(8, 2), 4);
125        assert_eq!(ceiling_div(9, 2), 5);
126        assert_eq!(ceiling_div(10, 3), 4);
127    }
128
129    #[test]
130    fn test_n_lowest() {
131        assert_eq!(n_lowest_bits(63), u64::MAX>>1);
132        assert_eq!(n_lowest_bits(3), 0b111);
133        assert_eq!(n_lowest_bits(1), 0b1);
134        assert_eq!(n_lowest_bits(0), 0);
135    }
136
137    #[test]
138    fn test_bits_to_store() {
139        assert_eq!(bits_to_store(0u32), 0);
140        assert_eq!(bits_to_store(1u32), 1);
141        assert_eq!(bits_to_store(2u32), 2);
142        assert_eq!(bits_to_store(3u32), 2);
143        assert_eq!(bits_to_store(4u32), 3);
144        assert_eq!(bits_to_store(7u32), 3);
145        assert_eq!(bits_to_store(8u32), 4);
146        assert_eq!(bits_to_store(9u32), 4);
147        assert_eq!(bits_to_store(15u32), 4);
148        assert_eq!(bits_to_store(16u32), 5);
149        assert_eq!(bits_to_store(u32::MAX-1), 32);
150        assert_eq!(bits_to_store(u32::MAX), 32);
151        assert_eq!(bits_to_store(u64::MAX), 64);
152    }
153}
bitm/lib.rs

bitm/
lib.rs
