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
use std::mem;
pub type Word = usize;
pub trait BitSlice {
fn clear_bit(&mut self, idx: usize) -> bool;
fn set_bit(&mut self, idx: usize) -> bool;
fn get_bit(&self, idx: usize) -> bool;
}
impl BitSlice for [Word] {
#[inline]
fn clear_bit(&mut self, idx: usize) -> bool {
let words = self;
debug!("clear_bit: words={} idx={}",
bits_to_string(words, words.len() * mem::size_of::<Word>() * 8), idx);
let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
debug!("word={} bit_in_word={} bit_mask=0x{:x}", word, bit_in_word, bit_mask);
let oldv = words[word];
let newv = oldv & !bit_mask;
words[word] = newv;
oldv != newv
}
#[inline]
fn set_bit(&mut self, idx: usize) -> bool {
let words = self;
debug!("set_bit: words={} idx={}",
bits_to_string(words, words.len() * mem::size_of::<Word>() * 8), idx);
let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
let oldv = words[word];
let newv = oldv | bit_mask;
words[word] = newv;
oldv != newv
}
#[inline]
fn get_bit(&self, idx: usize) -> bool {
let words = self;
let BitLookup { word, bit_mask, .. } = bit_lookup(idx);
(words[word] & bit_mask) != 0
}
}
struct BitLookup {
word: usize,
bit_in_word: usize,
bit_mask: Word,
}
#[inline]
fn bit_lookup(bit: usize) -> BitLookup {
let word_bits = mem::size_of::<Word>() * 8;
let word = bit / word_bits;
let bit_in_word = bit % word_bits;
let bit_mask = 1 << bit_in_word;
BitLookup { word, bit_in_word, bit_mask }
}
pub fn bits_to_string(words: &[Word], bits: usize) -> String {
let mut result = String::new();
let mut sep = '[';
let mut i = 0;
for &word in words.iter() {
let mut v = word;
for _ in 0..mem::size_of::<Word>() {
let remain = bits - i;
let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
assert!(mask <= 0xFF);
let byte = v & mask;
result.push_str(&format!("{}{:02x}", sep, byte));
if remain <= 8 { break; }
v >>= 8;
i += 8;
sep = '-';
}
sep = '|';
}
result.push(']');
result
}
#[inline]
pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [Word],
in_vec: &[Word],
op: &Op) -> bool {
assert_eq!(out_vec.len(), in_vec.len());
let mut changed = false;
for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) {
let old_val = *out_elt;
let new_val = op.join(old_val, *in_elt);
*out_elt = new_val;
changed |= old_val != new_val;
}
changed
}
pub trait BitwiseOperator {
fn join(&self, pred1: Word, pred2: Word) -> Word;
}
pub struct Intersect;
impl BitwiseOperator for Intersect {
#[inline]
fn join(&self, a: Word, b: Word) -> Word { a & b }
}
pub struct Union;
impl BitwiseOperator for Union {
#[inline]
fn join(&self, a: Word, b: Word) -> Word { a | b }
}
pub struct Subtract;
impl BitwiseOperator for Subtract {
#[inline]
fn join(&self, a: Word, b: Word) -> Word { a & !b }
}