use super::BitPosition;
use super::ewah::Ewah;
use knot_git::GitError;
#[derive(Clone)]
pub(crate) struct Bitset {
words: Vec<u64>,
}
impl Bitset {
pub(crate) fn zeros(num_bits: usize) -> Self {
Self {
words: vec![0u64; num_bits.div_ceil(64)],
}
}
pub(crate) fn set(&mut self, index: BitPosition) {
let index = index.get() as usize;
self.words[index / 64] |= 1u64 << (index % 64);
}
pub(crate) fn get(&self, index: BitPosition) -> bool {
let index = index.get() as usize;
self.words[index / 64] & (1u64 << (index % 64)) != 0
}
pub(crate) fn union_ewah(&mut self, vector: &Ewah, num_bits: usize) -> Result<(), GitError> {
self.apply_ewah(vector, num_bits, |word, mask| *word |= mask)
}
pub(crate) fn xor_ewah(&mut self, vector: &Ewah, num_bits: usize) -> Result<(), GitError> {
self.apply_ewah(vector, num_bits, |word, mask| *word ^= mask)
}
fn apply_ewah(
&mut self,
vector: &Ewah,
num_bits: usize,
op: impl Fn(&mut u64, u64),
) -> Result<(), GitError> {
vector.for_each_word(|index, word| {
if word == 0 {
return Ok(());
}
let valid = match index.cmp(&(num_bits / 64)) {
std::cmp::Ordering::Less => !0,
std::cmp::Ordering::Equal => (1u64 << (num_bits % 64)) - 1,
std::cmp::Ordering::Greater => 0,
};
if word & !valid != 0 {
return Err(GitError::Backend(
"bitmap entry is wider than the object count".to_string(),
));
}
op(&mut self.words[index], word);
Ok(())
})
}
pub(crate) fn xor(&self, other: &Bitset) -> Bitset {
Bitset {
words: self
.words
.iter()
.zip(&other.words)
.map(|(a, b)| a ^ b)
.collect(),
}
}
pub(crate) fn to_ewah(&self, num_bits: usize) -> Result<Ewah, GitError> {
Ewah::compress(&self.words, num_bits)
}
pub(crate) fn union_with(&mut self, other: &Bitset) {
self.words
.iter_mut()
.zip(&other.words)
.for_each(|(slot, bits)| *slot |= *bits);
}
pub(crate) fn count_common(&self, other: &Bitset) -> u64 {
self.words
.iter()
.zip(&other.words)
.map(|(a, b)| u64::from((a & b).count_ones()))
.sum()
}
pub(crate) fn ones(&self) -> impl Iterator<Item = BitPosition> + '_ {
self.words
.iter()
.enumerate()
.flat_map(|(word, bits)| WordBits {
remaining: *bits,
base: (word as u32) * 64,
})
}
pub(crate) fn difference_indices<'a>(
&'a self,
other: &'a Bitset,
) -> impl Iterator<Item = BitPosition> + 'a {
self.words
.iter()
.zip(&other.words)
.enumerate()
.flat_map(|(word, (present, absent))| WordBits {
remaining: present & !absent,
base: (word as u32) * 64,
})
}
}
struct WordBits {
remaining: u64,
base: u32,
}
impl Iterator for WordBits {
type Item = BitPosition;
fn next(&mut self) -> Option<BitPosition> {
(self.remaining != 0).then(|| {
let offset = self.remaining.trailing_zeros();
self.remaining &= self.remaining - 1;
BitPosition::new(self.base + offset)
})
}
}
#[cfg(test)]
mod tests {
use super::*;
fn set_bits(bits: &Bitset, other: &Bitset) -> Vec<u32> {
bits.difference_indices(other)
.map(BitPosition::get)
.collect()
}
#[test]
fn difference_yields_ascending_set_minus_set() {
let mut want = Bitset::zeros(130);
[1u32, 64, 65, 129]
.into_iter()
.for_each(|bit| want.set(BitPosition::new(bit)));
let mut have = Bitset::zeros(130);
[64u32, 129]
.into_iter()
.for_each(|bit| have.set(BitPosition::new(bit)));
assert_eq!(set_bits(&want, &have), vec![1, 65]);
}
#[test]
fn union_accumulates_both_operands() {
let mut acc = Bitset::zeros(70);
let mut other = Bitset::zeros(70);
acc.set(BitPosition::new(3));
other.set(BitPosition::new(3));
other.set(BitPosition::new(69));
acc.union_with(&other);
let empty = Bitset::zeros(70);
assert_eq!(set_bits(&acc, &empty), vec![3, 69]);
}
#[test]
fn ewah_round_trips_runs_literals_and_a_partial_tail() {
let num_bits = 64 * 200 + 10;
let mut bits = Bitset::zeros(num_bits);
(64 * 50..64 * 120)
.chain([3, 64 * 130 + 7, num_bits - 1])
.for_each(|bit| bits.set(BitPosition::new(bit as u32)));
let mut encoded = Vec::new();
bits.to_ewah(num_bits).unwrap().write_to(&mut encoded);
assert!(
encoded.len() < 100,
"runs collapse: {} bytes",
encoded.len()
);
let (vector, rest) = Ewah::decode(&encoded).unwrap();
assert!(rest.is_empty());
let mut decoded = Bitset::zeros(num_bits);
decoded.xor_ewah(&vector, num_bits).unwrap();
let empty = Bitset::zeros(num_bits);
assert_eq!(set_bits(&decoded, &empty), set_bits(&bits, &empty));
}
}