src/librustc_data_structures/bitslice.rs

   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 // FIXME: merge with `bitvec`
  12
  13 use std::mem;
  14
  15 pub type Word = usize;
  16
  17 /// `BitSlice` provides helper methods for treating a `[Word]`
  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
  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 {
  28         let words = self;
  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;
  35         words[word] = newv;
  36         oldv != newv
  37     }
  38
  39     /// Sets bit at `idx` to 1; returns true iff this changed `self.`
  40     fn set_bit(&mut self, idx: usize) -> bool {
  41         let words = self;
  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;
  48         words[word] = newv;
  49         oldv != newv
  50     }
  51
  52     /// Extracts value of bit at `idx` in `self`.
  53     fn get_bit(&self, idx: usize) -> bool {
  54         let words = self;
  55         let BitLookup { word, bit_mask, .. } = bit_lookup(idx);
  56         (words[word] & bit_mask) != 0
  57     }
  58 }
  59
  60 struct BitLookup {
  61     /// An index of the word holding the bit in original `[Word]` of query.
  62     word: usize,
  63     /// Index of the particular bit within the word holding the bit.
  64     bit_in_word: usize,
  65     /// Word with single 1-bit set corresponding to where the bit is located.
  66     bit_mask: Word,
  67 }
  68
  69 #[inline]
  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 }
  76 }
  77
  78
  79 fn bit_str(bit: Word) -> String {
  80     let byte = bit >> 3;
  81     let lobits = 1 << (bit & 0b111);
  82     format!("[{}:{}-{:02x}]", bit, byte, lobits)
  83 }
  84
  85 pub fn bits_to_string(words: &[Word], bits: usize) -> String {
  86     let mut result = String::new();
  87     let mut sep = '[';
  88
  89     // Note: this is a little endian printout of bytes.
  90
  91     // i tracks how many bits we have printed so far.
  92     let mut i = 0;
  93     for &word in words.iter() {
  94         let mut v = word;
  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);
 100             let byte = v & mask;
 101
 102             result.push(sep);
 103             result.push_str(&format!("{:02x}", byte));
 104
 105             if remain <= 8 { break; }
 106             v >>= 8;
 107             i += 8;
 108             sep = '-';
 109         }
 110     }
 111     result.push(']');
 112     return result
 113 }
 114
 115 #[inline]
 116 pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
 117                                    in_vec: &[usize],
 118                                    op: &Op) -> bool {
 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);
 124         *out_elt = new_val;
 125         changed |= old_val != new_val;
 126     }
 127     changed
 128 }
 129
 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;
 133 }
 134
 135 pub struct Union;
 136 impl BitwiseOperator for Union {
 137     fn join(&self, a: usize, b: usize) -> usize { a | b }
 138 }
 139 pub struct Subtract;
 140 impl BitwiseOperator for Subtract {
 141     fn join(&self, a: usize, b: usize) -> usize { a & !b }
 142 }