gix_bitmap/
ewah.rs

1///
2pub mod decode {
3    /// The error returned by [`decode()`][super::decode()].
4    #[derive(Debug, thiserror::Error)]
5    #[allow(missing_docs)]
6    pub enum Error {
7        #[error("{}", message)]
8        Corrupt { message: &'static str },
9    }
10}
11
12/// Decode `data` as EWAH bitmap.
13pub fn decode(data: &[u8]) -> Result<(Vec, &[u8]), decode::Error> {
14    use self::decode::Error;
15    use crate::decode;
16
17    let (num_bits, data) = decode::u32(data).ok_or(Error::Corrupt {
18        message: "eof reading amount of bits",
19    })?;
20    let (len, data) = decode::u32(data).ok_or(Error::Corrupt {
21        message: "eof reading chunk length",
22    })?;
23    let len = len as usize;
24
25    // NOTE: git does this by copying all bytes first, and then it will change the endianness in a separate loop.
26    //       Maybe it's faster, but we can't do it without unsafe. Let's leave it to the optimizer and maybe
27    //       one day somebody will find out that it's worth it to use unsafe here.
28    let (mut bits, data) = decode::split_at_pos(data, len * std::mem::size_of::<u64>()).ok_or(Error::Corrupt {
29        message: "eof while reading bit data",
30    })?;
31    let mut buf = std::vec::Vec::<u64>::with_capacity(len);
32    for _ in 0..len {
33        let (bit_num, rest) = bits.split_at(std::mem::size_of::<u64>());
34        bits = rest;
35        buf.push(u64::from_be_bytes(bit_num.try_into().unwrap()));
36    }
37
38    let (rlw, data) = decode::u32(data).ok_or(Error::Corrupt {
39        message: "eof while reading run length width",
40    })?;
41
42    Ok((
43        Vec {
44            num_bits,
45            bits: buf,
46            rlw: rlw.into(),
47        },
48        data,
49    ))
50}
51
52mod access {
53    use super::Vec;
54
55    impl Vec {
56        /// Call `f(index)` for each bit that is true, given the index of the bit that identifies it uniquely within the bit array.
57        /// If `f` returns `None` the iteration will be stopped and `None` is returned.
58        ///
59        /// The index is sequential like in any other vector.
60        pub fn for_each_set_bit(&self, mut f: impl FnMut(usize) -> Option<()>) -> Option<()> {
61            let mut index = 0usize;
62            let mut iter = self.bits.iter();
63            while let Some(word) = iter.next() {
64                if rlw_runbit_is_set(word) {
65                    let len = rlw_running_len_bits(word);
66                    for _ in 0..len {
67                        f(index)?;
68                        index += 1;
69                    }
70                } else {
71                    index += usize::try_from(rlw_running_len_bits(word)).ok()?;
72                }
73
74                for _ in 0..rlw_literal_words(word) {
75                    let word = iter
76                        .next()
77                        .expect("BUG: ran out of words while going through uncompressed portion");
78                    for bit_index in 0..64 {
79                        if word & (1 << bit_index) != 0 {
80                            f(index)?;
81                        }
82                        index += 1;
83                    }
84                }
85            }
86            Some(())
87        }
88
89        /// The amount of bits we are currently holding.
90        pub fn num_bits(&self) -> usize {
91            self.num_bits.try_into().expect("we are not on 16 bit systems")
92        }
93    }
94
95    #[inline]
96    fn rlw_running_len_bits(w: &u64) -> u64 {
97        rlw_running_len(w) * 64
98    }
99
100    #[inline]
101    fn rlw_running_len(w: &u64) -> u64 {
102        (w >> 1) & RLW_LARGEST_RUNNING_COUNT
103    }
104
105    #[inline]
106    fn rlw_literal_words(w: &u64) -> u64 {
107        w >> (1 + RLW_RUNNING_BITS)
108    }
109
110    #[inline]
111    fn rlw_runbit_is_set(w: &u64) -> bool {
112        w & 1 == 1
113    }
114
115    const RLW_RUNNING_BITS: u64 = 4 * 8;
116    const RLW_LARGEST_RUNNING_COUNT: u64 = (1 << RLW_RUNNING_BITS) - 1;
117}
118
119/// A growable collection of u64 that are seen as stream of individual bits.
120#[allow(dead_code)]
121#[derive(Clone)]
122pub struct Vec {
123    num_bits: u32,
124    bits: std::vec::Vec<u64>,
125    /// RLW is an offset into the `bits` buffer, so `1` translates into &bits\[1] essentially.
126    rlw: u64,
127}
gix_bitmap/ewah.rs

gix_bitmap/
ewah.rs
