]>
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 | ||
11 | use std::mem; | |
12 | ||
13 | /// `BitSlice` provides helper methods for treating a `[usize]` | |
14 | /// as a bitvector. | |
15 | pub trait BitSlice { | |
16 | fn clear_bit(&mut self, idx: usize) -> bool; | |
17 | fn set_bit(&mut self, idx: usize) -> bool; | |
18 | fn get_bit(&self, idx: usize) -> bool; | |
19 | } | |
20 | ||
21 | impl BitSlice for [usize] { | |
22 | /// Clears bit at `idx` to 0; returns true iff this changed `self.` | |
23 | fn clear_bit(&mut self, idx: usize) -> bool { | |
24 | let words = self; | |
25 | debug!("clear_bit: words={} idx={}", | |
26 | bits_to_string(words, words.len() * mem::size_of::<usize>()), bit_str(idx)); | |
27 | let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx); | |
28 | debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask); | |
29 | let oldv = words[word]; | |
30 | let newv = oldv & !bit_mask; | |
31 | words[word] = newv; | |
32 | oldv != newv | |
33 | } | |
34 | ||
35 | /// Sets bit at `idx` to 1; returns true iff this changed `self.` | |
36 | fn set_bit(&mut self, idx: usize) -> bool { | |
37 | let words = self; | |
38 | debug!("set_bit: words={} idx={}", | |
39 | bits_to_string(words, words.len() * mem::size_of::<usize>()), bit_str(idx)); | |
40 | let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx); | |
41 | debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask); | |
42 | let oldv = words[word]; | |
43 | let newv = oldv | bit_mask; | |
44 | words[word] = newv; | |
45 | oldv != newv | |
46 | } | |
47 | ||
48 | /// Extracts value of bit at `idx` in `self`. | |
49 | fn get_bit(&self, idx: usize) -> bool { | |
50 | let words = self; | |
51 | let BitLookup { word, bit_mask, .. } = bit_lookup(idx); | |
52 | (words[word] & bit_mask) != 0 | |
53 | } | |
54 | } | |
55 | ||
56 | struct BitLookup { | |
57 | /// An index of the word holding the bit in original `[usize]` of query. | |
58 | word: usize, | |
59 | /// Index of the particular bit within the word holding the bit. | |
60 | bit_in_word: usize, | |
61 | /// Word with single 1-bit set corresponding to where the bit is located. | |
62 | bit_mask: usize, | |
63 | } | |
64 | ||
65 | #[inline] | |
66 | fn bit_lookup(bit: usize) -> BitLookup { | |
67 | let usize_bits = mem::size_of::<usize>() * 8; | |
68 | let word = bit / usize_bits; | |
69 | let bit_in_word = bit % usize_bits; | |
70 | let bit_mask = 1 << bit_in_word; | |
71 | BitLookup { word: word, bit_in_word: bit_in_word, bit_mask: bit_mask } | |
72 | } | |
73 | ||
74 | ||
75 | fn bit_str(bit: usize) -> String { | |
76 | let byte = bit >> 8; | |
77 | let lobits = 1 << (bit & 0xFF); | |
78 | format!("[{}:{}-{:02x}]", bit, byte, lobits) | |
79 | } | |
80 | ||
81 | pub fn bits_to_string(words: &[usize], bytes: usize) -> String { | |
82 | let mut result = String::new(); | |
83 | let mut sep = '['; | |
84 | ||
85 | // Note: this is a little endian printout of bytes. | |
86 | ||
87 | let mut i = 0; | |
88 | for &word in words.iter() { | |
89 | let mut v = word; | |
90 | for _ in 0..mem::size_of::<usize>() { | |
91 | let byte = v & 0xFF; | |
92 | if i >= bytes { | |
93 | assert!(byte == 0); | |
94 | } else { | |
95 | result.push(sep); | |
96 | result.push_str(&format!("{:02x}", byte)); | |
97 | } | |
98 | v >>= 8; | |
99 | i += 1; | |
100 | sep = '-'; | |
101 | } | |
102 | } | |
103 | result.push(']'); | |
104 | return result | |
105 | } |