]>
Commit | Line | Data |
---|---|---|
54a0048b SL |
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. | |
4 | // | |
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. | |
10 | ||
c30ab7b3 | 11 | // FIXME: merge with `bitvec` |
3157f602 | 12 | |
54a0048b SL |
13 | use std::mem; |
14 | ||
3157f602 XL |
15 | pub type Word = usize; |
16 | ||
17 | /// `BitSlice` provides helper methods for treating a `[Word]` | |
54a0048b SL |
18 | /// as a bitvector. |
19 | pub trait BitSlice { | |
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; | |
23 | } | |
24 | ||
3157f602 | 25 | impl BitSlice for [Word] { |
54a0048b | 26 | /// Clears bit at `idx` to 0; returns true iff this changed `self.` |
0531ce1d | 27 | #[inline] |
54a0048b SL |
28 | fn clear_bit(&mut self, idx: usize) -> bool { |
29 | let words = self; | |
30 | debug!("clear_bit: words={} idx={}", | |
3157f602 | 31 | bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx)); |
54a0048b SL |
32 | let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx); |
33 | debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask); | |
34 | let oldv = words[word]; | |
35 | let newv = oldv & !bit_mask; | |
36 | words[word] = newv; | |
37 | oldv != newv | |
38 | } | |
39 | ||
40 | /// Sets bit at `idx` to 1; returns true iff this changed `self.` | |
0531ce1d | 41 | #[inline] |
54a0048b SL |
42 | fn set_bit(&mut self, idx: usize) -> bool { |
43 | let words = self; | |
44 | debug!("set_bit: words={} idx={}", | |
3157f602 | 45 | bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx)); |
54a0048b SL |
46 | let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx); |
47 | debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask); | |
48 | let oldv = words[word]; | |
49 | let newv = oldv | bit_mask; | |
50 | words[word] = newv; | |
51 | oldv != newv | |
52 | } | |
53 | ||
54 | /// Extracts value of bit at `idx` in `self`. | |
0531ce1d | 55 | #[inline] |
54a0048b SL |
56 | fn get_bit(&self, idx: usize) -> bool { |
57 | let words = self; | |
58 | let BitLookup { word, bit_mask, .. } = bit_lookup(idx); | |
59 | (words[word] & bit_mask) != 0 | |
60 | } | |
61 | } | |
62 | ||
63 | struct BitLookup { | |
3157f602 | 64 | /// An index of the word holding the bit in original `[Word]` of query. |
54a0048b SL |
65 | word: usize, |
66 | /// Index of the particular bit within the word holding the bit. | |
67 | bit_in_word: usize, | |
68 | /// Word with single 1-bit set corresponding to where the bit is located. | |
3157f602 | 69 | bit_mask: Word, |
54a0048b SL |
70 | } |
71 | ||
72 | #[inline] | |
73 | fn bit_lookup(bit: usize) -> BitLookup { | |
3157f602 XL |
74 | let word_bits = mem::size_of::<Word>() * 8; |
75 | let word = bit / word_bits; | |
76 | let bit_in_word = bit % word_bits; | |
54a0048b SL |
77 | let bit_mask = 1 << bit_in_word; |
78 | BitLookup { word: word, bit_in_word: bit_in_word, bit_mask: bit_mask } | |
79 | } | |
80 | ||
81 | ||
3157f602 XL |
82 | fn bit_str(bit: Word) -> String { |
83 | let byte = bit >> 3; | |
84 | let lobits = 1 << (bit & 0b111); | |
54a0048b SL |
85 | format!("[{}:{}-{:02x}]", bit, byte, lobits) |
86 | } | |
87 | ||
3157f602 | 88 | pub fn bits_to_string(words: &[Word], bits: usize) -> String { |
54a0048b SL |
89 | let mut result = String::new(); |
90 | let mut sep = '['; | |
91 | ||
92 | // Note: this is a little endian printout of bytes. | |
93 | ||
3157f602 | 94 | // i tracks how many bits we have printed so far. |
54a0048b SL |
95 | let mut i = 0; |
96 | for &word in words.iter() { | |
97 | let mut v = word; | |
3157f602 XL |
98 | loop { // for each byte in `v`: |
99 | let remain = bits - i; | |
100 | // If less than a byte remains, then mask just that many bits. | |
101 | let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF }; | |
102 | assert!(mask <= 0xFF); | |
103 | let byte = v & mask; | |
104 | ||
105 | result.push(sep); | |
106 | result.push_str(&format!("{:02x}", byte)); | |
107 | ||
108 | if remain <= 8 { break; } | |
54a0048b | 109 | v >>= 8; |
3157f602 | 110 | i += 8; |
54a0048b SL |
111 | sep = '-'; |
112 | } | |
113 | } | |
114 | result.push(']'); | |
115 | return result | |
116 | } | |
3157f602 XL |
117 | |
118 | #[inline] | |
119 | pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize], | |
120 | in_vec: &[usize], | |
121 | op: &Op) -> bool { | |
122 | assert_eq!(out_vec.len(), in_vec.len()); | |
123 | let mut changed = false; | |
124 | for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) { | |
125 | let old_val = *out_elt; | |
126 | let new_val = op.join(old_val, *in_elt); | |
127 | *out_elt = new_val; | |
128 | changed |= old_val != new_val; | |
129 | } | |
130 | changed | |
131 | } | |
132 | ||
133 | pub trait BitwiseOperator { | |
134 | /// Applies some bit-operation pointwise to each of the bits in the two inputs. | |
135 | fn join(&self, pred1: usize, pred2: usize) -> usize; | |
136 | } | |
137 | ||
ea8adc8c XL |
138 | pub struct Intersect; |
139 | impl BitwiseOperator for Intersect { | |
140 | #[inline] | |
141 | fn join(&self, a: usize, b: usize) -> usize { a & b } | |
142 | } | |
3157f602 XL |
143 | pub struct Union; |
144 | impl BitwiseOperator for Union { | |
3b2f2976 | 145 | #[inline] |
3157f602 XL |
146 | fn join(&self, a: usize, b: usize) -> usize { a | b } |
147 | } | |
148 | pub struct Subtract; | |
149 | impl BitwiseOperator for Subtract { | |
3b2f2976 | 150 | #[inline] |
3157f602 XL |
151 | fn join(&self, a: usize, b: usize) -> usize { a & !b } |
152 | } |