CSY/reowolf Changeset - 05d86428c367 · Centrum Wiskunde & Informatica (CWI)

Changeset - 05d86428c367

Parent rev.

Child rev.

[Not reviewed]

0 1 0

Christopher Esterhuyse - 5 years ago 2020-02-17 08:57:18
christopher.esterhuyse@gmail.com

newtypes

1 file changed with 26 insertions and 20 deletions:

src/runtime/bits.rs

0 comments (0 inline, 0 general)

src/runtime/bits.rs

➞

Show inline comments

 use crate::common::*;
 /// Converts an iterator over contiguous u32 chunks into an iterator over usize
 /// e.g. input [0b111000, 0b11] gives output [3, 4, 5, 32, 33]
 /// Given an iterator over BitChunk Items, iterates over the indices (each represented as a u32) for which the bit is SET,
 /// treating the bits in the BitChunk as a contiguous array.
 /// e.g. input [0b111000, 0b11] gives output [3, 4, 5, 32, 33].
 /// observe that the bits per chunk are ordered from least to most significant bits, yielding smaller to larger usizes.
-/// works by draining the inner u32 chunk iterator one u32 at a time, then draining that chunk until its 0.
+/// assumes chunk_iter will yield no more than std::u32::MAX / 32 chunks
 struct BitChunkIter<I: Iterator<Item = BitChunk>> {
     chunk_iter: I,
     next_bit_index: u32,
     cached: BitChunk,
+}
 impl<I: Iterator<Item = BitChunk>> BitChunkIter<I> {
     fn new(chunk_iter: I) -> Self {
-        // first chunk is always a dummy zero, as if chunk_iter yielded Some(0).
+        // first chunk is always a dummy zero, as if chunk_iter yielded Some(FALSE).
         // Consequences:
         // 1. our next_bit_index is always off by 32 (we correct for it in Self::next) (no additional overhead)
         // 2. we cache u32 and not Option<u32>, because chunk_iter.next() is only called in Self::next.
         // 1. our next_bit_index is always off by BitChunk::bits() (we correct for it in Self::next) (no additional overhead)
         // 2. we cache BitChunk and not Option<BitChunk>, because chunk_iter.next() is only called in Self::next.
         Self { chunk_iter, next_bit_index: 0, cached: BitChunk(0) }
+    }
+}
 impl<I: Iterator<Item = BitChunk>> Iterator for BitChunkIter<I> {
     type Item = u32;
     fn next(&mut self) -> Option<Self::Item> {
         let mut chunk = self.cached;
         // loop until either:
         // 1. there are no more Items to return, or
         // 2. chunk encodes 1+ Items, one of which we will return.
         while !chunk.any() {
-            // chunk is still empty! get the next one...
+            // chunk has no bits set! get the next one...
             chunk = self.chunk_iter.next()?;
             // ... and jump self.next_bit_index to the next multiple of BitChunk::chunk_bits().
             self.next_bit_index =
                 (self.next_bit_index + BitChunk::bits() as u32) & !(BitChunk::bits() as u32 - 1);
+        }
         // there exists 1+ set bits in chunk
         // assert(chunk > 0);
         // Shift the contents of chunk until the least significant bit is 1.
         // ... being sure to increment next_bit_index accordingly.
         #[inline(always)]
         fn skip_n_zeroes(chunk: &mut BitChunk, n: u32, next_bit_index: &mut u32) {
             if chunk.0 & ((1 << n) - 1) == 0 {
                 // n least significant bits are zero. skip n bits.
                 *next_bit_index += n;
         // Until the least significant bit of chunk is 1:
         // 1. shift chunk to the right,
         // 2. and increment self.next_bit_index accordingly
         // effectively performs a little binary search, shifting 32, then 16, ...
         // TODO perhaps there is a more efficient SIMD op for this?
         const N_INIT: u32 = BitChunk::bits() as u32 / 2;
         let mut n = N_INIT;
         while n >= 1 {
             // n is [32,16,8,4,2,1] on 64-bit machine
             // this loop is unrolled with release optimizations
             let n_least_significant_mask = (1 << n) - 1;
             if chunk.0 & n_least_significant_mask == 0 {
                 // no 1 set within 0..n least significant bits.
                 self.next_bit_index += n;
                 chunk.0 >>= n;
+            }
+        }
         let mut n = std::mem::size_of::<usize>() as u32 * 8 / 2;
         while n >= 1 {
             skip_n_zeroes(&mut chunk, n, &mut self.next_bit_index);
             n /= 2;
+        }
         // least significant bit of chunk is 1.
+        // least significant bit of chunk is 1. Item to return is known.
         // assert(chunk & 1 == 1)
         // prepare our state for the next time Self::next is called.
         // Overwrite self.cached such that its shifted state is retained,
         // and jump over the bit whose index we are about to return.
         self.next_bit_index += 1;
         self.cached = BitChunk(chunk.0 >> 1);
         // returned index is BitChunk::bits() smaller than self.next_bit_index because we use an
         // off-by-BitChunk::bits() encoding to avoid having to cache an Option<BitChunk>.
         Some(self.next_bit_index - 1 - BitChunk::bits() as u32)
+    }
+}
 /*  --properties-->
      ___ ___ ___ ___
     |___|___|___|___|
   | |___|___|___|___|
   | |___|___|___|___|
   | |___|___|___|___|
+  |
+  V
  entity chunks (groups of BitChunk::bits())
 */
 // TODO newtypes Entity and Property
 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
 struct Pair {
     entity: u32,
     property: u32,
+}
 impl From<[u32; 2]> for Pair {
     fn from([entity, property]: [u32; 2]) -> Self {
         Pair { entity, property }
+    }
+}
 struct BitMatrix {
     bounds: Pair,
     buffer: *mut BitChunk,
+}
 impl Drop for BitMatrix {
     fn drop(&mut self) {
         let total_chunks = Self::row_chunks(self.bounds.property as usize)
             * Self::column_chunks(self.bounds.entity as usize);
         let layout = Self::layout_for(total_chunks);
         unsafe {
             // ?
@@ @@ -267,83 +272,84 @@ impl BitMatrix { @@
             unsafe {
                 let slicey = std::slice::from_raw_parts(ptr, row_chunks);
                 slice = std::mem::transmute(slicey);
                 ptr = ptr.add(row_chunks);
+            }
             buf.push(fold_fn(slice));
+        }
         if let Some(mask) = Self::last_row_chunk_mask(self.bounds.entity) {
             *buf.iter_mut().last().unwrap() &= mask;
+        }
         BitChunkIter::new(buf.drain(buf_start..))
+    }
+}
 use derive_more::*;
 #[derive(
     Debug, Copy, Clone, BitAnd, Not, BitOr, BitXor, BitAndAssign, BitOrAssign, BitXorAssign,
 )]
 struct BitChunk(usize);
 impl BitChunk {
     const fn bits() -> usize {
         Self::bytes() * 8
+    }
     const fn bytes() -> usize {
         std::mem::size_of::<Self>()
+    }
     const fn any(self) -> bool {
         self.0 != FALSE.0
+    }
     const fn all(self) -> bool {
         self.0 == TRUE.0
+    }
+}
 const TRUE: BitChunk = BitChunk(!0);
 const FALSE: BitChunk = BitChunk(0);
 #[test]
 fn matrix_test() {
     let mut m = BitMatrix::new(Pair { entity: 70, property: 3 });
     m.set([2, 0].into());
     m.set([40, 1].into());
     m.set([40, 2].into());
     m.set([40, 0].into());
     println!("{:?}", &m);
     m.batch_mut(|p| p[0] = TRUE);
     println!("{:?}", &m);
-    for i in (0..70).step_by(7) {
+    for i in (0..40).step_by(7) {
         m.unset([i, 0].into());
+    }
     m.unset([62, 0].into());
     println!("{:?}", &m);
     m.batch_mut(move |p| p[1] = p[0] ^ TRUE);
     println!("{:?}", &m);
     let mut buf = vec![];
     for index in m.iter_entities_where(&mut buf, move |p| p[1]) {
         println!("index {}", index);
+    }
+}
 /*
 TODO
 . BitChunk newtype in matrix and bit iterator
 . make BitChunk a wrapper around usize, using mem::size_of for the shifting
     #[inline(always)]
     fn skip_n_zeroes(chunk: &mut usize, n: usize) {
         if *chunk & ((1 << n) - 1) == 0 {
             *chunk >>= n;
+        }
+    }
     let mut n = std::mem::size_of::<usize>() * 8 / 2;
     while n > 1 {
         if x & ((1 << n) - 1) == 0 {
             x >>= n;
+        }
         n /= 2;
+    }
 */

0 comments (0 inline, 0 general)