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     #[inline]
  28     fn clear_bit(&mut self, idx: usize) -> bool {
  29         let words = self;
  30         debug!("clear_bit: words={} idx={}",
  31                bits_to_string(words, words.len() * mem::size_of::<Word>() * 8), idx);
  32         let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
  33         debug!("word={} bit_in_word={} bit_mask=0x{:x}", 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.`
  41     #[inline]
  42     fn set_bit(&mut self, idx: usize) -> bool {
  43         let words = self;
  44         debug!("set_bit: words={} idx={}",
  45                bits_to_string(words, words.len() * mem::size_of::<Word>() * 8), idx);
  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`.
  55     #[inline]
  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 {
  64     /// An index of the word holding the bit in original `[Word]` of query.
  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.
  69     bit_mask: Word,
  70 }
  71
  72 #[inline]
  73 fn bit_lookup(bit: usize) -> BitLookup {
  74     let word_bits = mem::size_of::<Word>() * 8;
  75     let word = bit / word_bits;
  76     let bit_in_word = bit % word_bits;
  77     let bit_mask = 1 << bit_in_word;
  78     BitLookup { word, bit_in_word, bit_mask }
  79 }
  80
  81 pub fn bits_to_string(words: &[Word], bits: 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     // i tracks how many bits we have printed so far.
  88     let mut i = 0;
  89     for &word in words.iter() {
  90         let mut v = word;
  91         for _ in 0..mem::size_of::<Word>() { // for each byte in `v`:
  92             let remain = bits - i;
  93             // If less than a byte remains, then mask just that many bits.
  94             let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
  95             assert!(mask <= 0xFF);
  96             let byte = v & mask;
  97
  98             result.push_str(&format!("{}{:02x}", sep, byte));
  99
 100             if remain <= 8 { break; }
 101             v >>= 8;
 102             i += 8;
 103             sep = '-';
 104         }
 105         sep = '|';
 106     }
 107     result.push(']');
 108
 109     result
 110 }
 111
 112 #[inline]
 113 pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [Word],
 114                                    in_vec: &[Word],
 115                                    op: &Op) -> bool {
 116     assert_eq!(out_vec.len(), in_vec.len());
 117     let mut changed = false;
 118     for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) {
 119         let old_val = *out_elt;
 120         let new_val = op.join(old_val, *in_elt);
 121         *out_elt = new_val;
 122         changed |= old_val != new_val;
 123     }
 124     changed
 125 }
 126
 127 pub trait BitwiseOperator {
 128     /// Applies some bit-operation pointwise to each of the bits in the two inputs.
 129     fn join(&self, pred1: Word, pred2: Word) -> Word;
 130 }
 131
 132 pub struct Intersect;
 133 impl BitwiseOperator for Intersect {
 134     #[inline]
 135     fn join(&self, a: Word, b: Word) -> Word { a & b }
 136 }
 137 pub struct Union;
 138 impl BitwiseOperator for Union {
 139     #[inline]
 140     fn join(&self, a: Word, b: Word) -> Word { a | b }
 141 }
 142 pub struct Subtract;
 143 impl BitwiseOperator for Subtract {
 144     #[inline]
 145     fn join(&self, a: Word, b: Word) -> Word { a & !b }
 146 }