1 // Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 // FIXME: merge with `bitvec`
15 pub type Word = usize;
17 /// `BitSlice` provides helper methods for treating a `[Word]`
20 fn clear_bit(&mut self, idx: usize) -> bool;
21 fn set_bit(&mut self, idx: usize) -> bool;
22 fn get_bit(&self, idx: usize) -> bool;
25 impl BitSlice for [Word] {
26 /// Clears bit at `idx` to 0; returns true iff this changed `self.`
27 fn clear_bit(&mut self, idx: usize) -> bool {
29 debug!("clear_bit: words={} idx={}",
30 bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx));
31 let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
32 debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
33 let oldv = words[word];
34 let newv = oldv & !bit_mask;
39 /// Sets bit at `idx` to 1; returns true iff this changed `self.`
40 fn set_bit(&mut self, idx: usize) -> bool {
42 debug!("set_bit: words={} idx={}",
43 bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx));
44 let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
45 debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
46 let oldv = words[word];
47 let newv = oldv | bit_mask;
52 /// Extracts value of bit at `idx` in `self`.
53 fn get_bit(&self, idx: usize) -> bool {
55 let BitLookup { word, bit_mask, .. } = bit_lookup(idx);
56 (words[word] & bit_mask) != 0
61 /// An index of the word holding the bit in original `[Word]` of query.
63 /// Index of the particular bit within the word holding the bit.
65 /// Word with single 1-bit set corresponding to where the bit is located.
70 fn bit_lookup(bit: usize) -> BitLookup {
71 let word_bits = mem::size_of::<Word>() * 8;
72 let word = bit / word_bits;
73 let bit_in_word = bit % word_bits;
74 let bit_mask = 1 << bit_in_word;
75 BitLookup { word: word, bit_in_word: bit_in_word, bit_mask: bit_mask }
79 fn bit_str(bit: Word) -> String {
81 let lobits = 1 << (bit & 0b111);
82 format!("[{}:{}-{:02x}]", bit, byte, lobits)
85 pub fn bits_to_string(words: &[Word], bits: usize) -> String {
86 let mut result = String::new();
89 // Note: this is a little endian printout of bytes.
91 // i tracks how many bits we have printed so far.
93 for &word in words.iter() {
95 loop { // for each byte in `v`:
96 let remain = bits - i;
97 // If less than a byte remains, then mask just that many bits.
98 let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
99 assert!(mask <= 0xFF);
103 result.push_str(&format!("{:02x}", byte));
105 if remain <= 8 { break; }
116 pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
119 assert_eq!(out_vec.len(), in_vec.len());
120 let mut changed = false;
121 for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) {
122 let old_val = *out_elt;
123 let new_val = op.join(old_val, *in_elt);
125 changed |= old_val != new_val;
130 pub trait BitwiseOperator {
131 /// Applies some bit-operation pointwise to each of the bits in the two inputs.
132 fn join(&self, pred1: usize, pred2: usize) -> usize;
136 impl BitwiseOperator for Union {
137 fn join(&self, a: usize, b: usize) -> usize { a | b }
140 impl BitwiseOperator for Subtract {
141 fn join(&self, a: usize, b: usize) -> usize { a & !b }