diff --git a/src/runtime/retired/experimental/bits.rs b/src/runtime/retired/experimental/bits.rs new file mode 100644 index 0000000000000000000000000000000000000000..03166bd28f37e82ebc65c230be5a794f6ae4143e --- /dev/null +++ b/src/runtime/retired/experimental/bits.rs @@ -0,0 +1,457 @@ +use crate::common::*; +use std::alloc::Layout; + +/// 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. +/// assumes chunk_iter will yield no more than std::u32::MAX / 32 chunks + +pub const fn usize_bytes() -> usize { + std::mem::size_of::() +} +pub const fn usize_bits() -> usize { + usize_bytes() * 8 +} +pub const fn usizes_for_bits(bits: usize) -> usize { + (bits + (usize_bits() - 1)) / usize_bits() +} + +type Chunk = usize; +type BitIndex = usize; + +pub(crate) struct BitChunkIter> { + cached: usize, + chunk_iter: I, + next_bit_index: BitIndex, +} +impl> BitChunkIter { + pub fn new(chunk_iter: I) -> Self { + // first chunk is always a dummy zero, as if chunk_iter yielded Some(FALSE_CHUNK). + // Consequences: + // 1. our next_bit_index is always off by usize_bits() (we correct for it in Self::next) (no additional overhead) + // 2. we cache Chunk and not Option, because chunk_iter.next() is only called in Self::next. + Self { chunk_iter, next_bit_index: 0, cached: 0 } + } +} +impl> Iterator for BitChunkIter { + type Item = BitIndex; + fn next(&mut self) -> Option { + 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 == 0 { + // 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 usize_bits(). + self.next_bit_index = (self.next_bit_index + usize_bits()) & !(usize_bits() - 1); + } + // there exists 1+ set bits in chunk + // assert(chunk > 0); + + // 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: BitIndex = usize_bits() / 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 & n_least_significant_mask == 0 { + // no 1 set within 0..n least significant bits. + self.next_bit_index += n; + chunk >>= n; + } + n /= 2; + } + // 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 = chunk >> 1; + + // returned index is usize_bits() smaller than self.next_bit_index because we use an + // off-by-usize_bits() encoding to avoid having to cache an Option. + Some(self.next_bit_index - 1 - usize_bits()) + } +} + +pub(crate) struct BitChunkIterRev> { + cached: usize, + chunk_iter: I, + next_bit_index: BitIndex, +} +impl> BitChunkIterRev { + pub fn new(chunk_iter: I) -> Self { + let next_bit_index = chunk_iter.len() * usize_bits(); + Self { chunk_iter, next_bit_index, cached: 0 } + } +} +impl> Iterator for BitChunkIterRev { + type Item = BitIndex; + fn next(&mut self) -> Option { + let mut chunk = self.cached; + if chunk == 0 { + self.next_bit_index += usize_bits(); + loop { + self.next_bit_index -= usize_bits(); + chunk = self.chunk_iter.next()?; + if chunk != 0 { + break; + } + } + } + const N_INIT: BitIndex = usize_bits() / 2; + let mut n = N_INIT; + while n >= 1 { + let n_most_significant_mask = !0 << (usize_bits() - n); + if chunk & n_most_significant_mask == 0 { + self.next_bit_index -= n; + chunk <<= n; + } + n /= 2; + } + self.cached = chunk << 1; + self.next_bit_index -= 1; + Some(self.next_bit_index) + } +} + +/* --properties--> + ___ ___ ___ ___ + |___|___|___|___| + | |___|___|___|___| + | |___|___|___|___| + | |___|___|___|___| + | + V + entity chunks (groups of size usize_bits()) +*/ + +// TODO newtypes Entity and Property + +#[derive(Debug, Copy, Clone, Eq, PartialEq)] +pub struct Pair { + pub entity: u32, + pub property: u32, +} +impl From<[u32; 2]> for Pair { + fn from([entity, property]: [u32; 2]) -> Self { + Pair { entity, property } + } +} +impl Default for BitMatrix { + fn default() -> Self { + Self::new(Pair { entity: 0, property: 0 }) + } +} +pub struct BitMatrix { + buffer: *mut usize, + bounds: Pair, + layout: Layout, // layout of the currently-allocated buffer +} +impl Drop for BitMatrix { + fn drop(&mut self) { + unsafe { + // ? + std::alloc::dealloc(self.buffer as *mut u8, self.layout); + } + } +} +impl Debug for BitMatrix { + fn fmt(&self, f: &mut Formatter) -> std::fmt::Result { + struct FmtRow<'a> { + me: &'a BitMatrix, + property: usize, + }; + impl Debug for FmtRow<'_> { + fn fmt(&self, f: &mut Formatter) -> std::fmt::Result { + let row_chunks = BitMatrix::row_chunks(self.me.bounds.property as usize); + let column_chunks = BitMatrix::column_chunks(self.me.bounds.entity as usize); + write!(f, "|")?; + for entity_chunk in 0..column_chunks { + let mut chunk = + unsafe { *self.me.buffer.add(row_chunks * entity_chunk + self.property) }; + let end = if entity_chunk + 1 == column_chunks { + self.me.bounds.entity % usize_bits() as u32 + } else { + usize_bits() as u32 + }; + for _ in 0..end { + let c = match chunk & 1 { + 0 => '0', + _ => '1', + }; + write!(f, "{}", c)?; + chunk >>= 1; + } + write!(f, "_")?; + } + Ok(()) + } + } + let row_chunks = BitMatrix::row_chunks(self.bounds.property as usize); + let iter = (0..row_chunks).map(move |property| FmtRow { me: self, property }); + f.debug_list().entries(iter).finish() + } +} +impl BitMatrix { + #[inline] + const fn row_of(entity: usize) -> usize { + entity / usize_bits() + } + #[inline] + const fn row_chunks(property_bound: usize) -> usize { + property_bound + } + #[inline] + const fn column_chunks(entity_bound: usize) -> usize { + usizes_for_bits(entity_bound) + } + #[inline] + fn offsets_unchecked(&self, at: Pair) -> [usize; 2] { + let o_in = at.entity as usize % usize_bits(); + let row = Self::row_of(at.entity as usize); + let row_chunks = self.bounds.property as usize; + let o_of = row * row_chunks + at.property as usize; + [o_of, o_in] + } + // returns a u32 which has bits 000...000111...111 + // for the last JAGGED chunk given the column size + // if the last chunk is not jagged (when entity_bound % 32 == 0) + // None is returned, + // otherwise Some(x) is returned such that x & chunk would mask out + // the bits NOT in 0..entity_bound + fn last_row_chunk_mask(entity_bound: u32) -> Option { + let zero_prefix_len = entity_bound as usize % usize_bits(); + if zero_prefix_len == 0 { + None + } else { + Some(!0 >> (usize_bits() - zero_prefix_len)) + } + } + fn assert_within_bounds(&self, at: Pair) { + assert!(at.entity < self.bounds.entity); + assert!(at.property < self.bounds.property); + } + + fn layout_for(total_chunks: usize) -> std::alloc::Layout { + unsafe { + // this layout is ALWAYS valid: + // 1. size is always nonzero + // 2. size is always a multiple of 4 and 4-aligned + Layout::from_size_align_unchecked(usize_bytes() * total_chunks.max(1), usize_bytes()) + } + } + ///////// + pub fn get_bounds(&self) -> &Pair { + &self.bounds + } + pub fn grow_to(&mut self, bounds: Pair) { + assert!(bounds.entity >= self.bounds.entity); + assert!(bounds.property >= self.bounds.property); + + let old_row_chunks = Self::row_chunks(self.bounds.property as usize); + let old_col_chunks = Self::column_chunks(self.bounds.entity as usize); + let new_row_chunks = Self::row_chunks(bounds.property as usize); + let new_col_chunks = Self::column_chunks(bounds.entity as usize); + + let new_layout = Self::layout_for(new_row_chunks * new_col_chunks); + let new_buffer = unsafe { + let new_buffer = std::alloc::alloc(new_layout) as *mut usize; + let mut src: *mut usize = self.buffer; + let mut dest: *mut usize = new_buffer; + let row_chunk_diff = new_row_chunks - old_row_chunks; + for _col_idx in 0..old_col_chunks { + src.copy_to_nonoverlapping(dest, old_row_chunks); + src = src.add(old_row_chunks); + dest = dest.add(old_row_chunks); + if row_chunk_diff > 0 { + dest.write_bytes(0u8, row_chunk_diff); + dest = dest.add(row_chunk_diff); + } + } + let last_zero_chunks = (new_col_chunks - old_col_chunks) * new_row_chunks; + dest.write_bytes(0u8, last_zero_chunks); + new_buffer + }; + self.layout = new_layout; + self.buffer = new_buffer; + self.bounds = bounds; + } + pub fn clear(&mut self) { + let total_chunks = Self::row_chunks(self.bounds.property as usize) + * Self::column_chunks(self.bounds.entity as usize); + unsafe { + self.buffer.write_bytes(0u8, total_chunks); + } + } + pub fn new(bounds: Pair) -> Self { + let total_chunks = Self::row_chunks(bounds.property as usize) + * Self::column_chunks(bounds.entity as usize); + let layout = Self::layout_for(total_chunks); + let buffer; + unsafe { + buffer = std::alloc::alloc(layout) as *mut usize; + buffer.write_bytes(0u8, total_chunks); + }; + Self { buffer, bounds, layout } + } + pub fn set(&mut self, at: Pair) { + self.assert_within_bounds(at); + let [o_of, o_in] = self.offsets_unchecked(at); + unsafe { *self.buffer.add(o_of) |= 1 << o_in }; + } + pub fn unset(&mut self, at: Pair) { + self.assert_within_bounds(at); + let [o_of, o_in] = self.offsets_unchecked(at); + unsafe { *self.buffer.add(o_of) &= !(1 << o_in) }; + } + pub fn test(&self, at: Pair) -> bool { + self.assert_within_bounds(at); + let [o_of, o_in] = self.offsets_unchecked(at); + unsafe { *self.buffer.add(o_of) & 1 << o_in != 0 } + } + + pub fn batch_mut<'a, 'b>(&mut self, mut chunk_mut_fn: impl FnMut(&'b mut [BitChunk])) { + let row_chunks = Self::row_chunks(self.bounds.property as usize); + let column_chunks = Self::column_chunks(self.bounds.entity as usize); + let mut ptr = self.buffer; + for _row in 0..column_chunks { + let slice; + unsafe { + let slicey = std::slice::from_raw_parts_mut(ptr, row_chunks); + slice = std::mem::transmute(slicey); + ptr = ptr.add(row_chunks); + } + chunk_mut_fn(slice); + } + if let Some(mask) = Self::last_row_chunk_mask(self.bounds.entity) { + // TODO TEST + let mut ptr = unsafe { self.buffer.add((column_chunks - 1) * row_chunks) }; + for _ in 0..row_chunks { + unsafe { + *ptr &= mask; + ptr = ptr.add(1); + } + } + } + } + + /// given: + /// 1. a buffer to work with + /// 2. a _fold function_ for combining the properties of a given entity + /// and returning a new derived property (working ) + pub fn iter_entities_where<'a, 'b>( + &'a self, + buf: &'b mut Vec, + mut fold_fn: impl FnMut(&'b [BitChunk]) -> BitChunk, + ) -> impl Iterator + 'b { + let buf_start = buf.len(); + let row_chunks = Self::row_chunks(self.bounds.property as usize); + let column_chunks = Self::column_chunks(self.bounds.entity as usize); + let mut ptr = self.buffer; + for _row in 0..column_chunks { + let slice; + unsafe { + let slicey = std::slice::from_raw_parts(ptr, row_chunks); + slice = std::mem::transmute(slicey); + ptr = ptr.add(row_chunks); + } + let chunk = fold_fn(slice); + buf.push(chunk.0); + } + if let Some(mask) = Self::last_row_chunk_mask(self.bounds.entity) { + *buf.iter_mut().last().unwrap() &= mask; + } + BitChunkIter::new(buf.drain(buf_start..)).map(|x| x as u32) + } + pub fn iter_entities_where_rev<'a, 'b>( + &'a self, + buf: &'b mut Vec, + mut fold_fn: impl FnMut(&'b [BitChunk]) -> BitChunk, + ) -> impl Iterator + 'b { + let buf_start = buf.len(); + let row_chunks = Self::row_chunks(self.bounds.property as usize); + let column_chunks = Self::column_chunks(self.bounds.entity as usize); + let mut ptr = self.buffer; + for _row in 0..column_chunks { + let slice; + unsafe { + let slicey = std::slice::from_raw_parts(ptr, row_chunks); + slice = std::mem::transmute(slicey); + ptr = ptr.add(row_chunks); + } + let chunk = fold_fn(slice); + buf.push(chunk.0); + } + if let Some(mask) = Self::last_row_chunk_mask(self.bounds.entity) { + *buf.iter_mut().last().unwrap() &= mask; + } + BitChunkIterRev::new(buf.drain(buf_start..).rev()).map(|x| x as u32) + } +} + +use derive_more::*; +#[derive( + Debug, Copy, Clone, BitAnd, Not, BitOr, BitXor, BitAndAssign, BitOrAssign, BitXorAssign, +)] +#[repr(transparent)] +pub struct BitChunk(usize); +impl BitChunk { + const fn any(self) -> bool { + self.0 != FALSE_CHUNK.0 + } + const fn all(self) -> bool { + self.0 == TRUE_CHUNK.0 + } +} +pub const TRUE_CHUNK: BitChunk = BitChunk(!0); +pub const FALSE_CHUNK: 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_CHUNK); + println!("{:#?}", &m); + + 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_CHUNK); + println!("{:#?}", &m); + + let mut buf = vec![]; + for index in m.iter_entities_where(&mut buf, move |p| p[1]) { + println!("index {}", index); + } + for index in m.iter_entities_where_rev(&mut buf, move |p| p[1]) { + println!("index {}", index); + } +} + +#[test] +fn bit_chunk_iter_rev() { + let x = &[0b1, 0b1000011, 0, 0, 0b101]; + for i in BitChunkIterRev::new(x.iter().copied()) { + println!("i = {:?}", i); + } +}