All block shapes & collisions (#22)

* start adding shapes

* add more collision stuff

* DiscreteCubeMerger

* more mergers

* start adding BitSetDiscreteVoxelShape::join

* i love rust :smiley: :smiley: :smiley:

* r

* IT COMPILES????

* fix warning

* fix error

* fix more clippy issues

* add box_shape

* more shape stuff

* make DiscreteVoxelShape an enum

* Update shape.rs

* also make VoxelShape an enum

* implement BitSet::clear

* add more missing things

* it compiles

W

* start block shape codegen

* optimize shape codegen

* make az-block/blocks.rs look better (broken)

* almost new block macro

* make the codegen not generate 'type'

* try to fix

* work more on the blocks macro

* wait it compiles

* fix clippy issues

* shapes codegen works

* well it's almost working

* simplify some shape codegen

* enum type names are correct

* W it compiles

* cargo check no longer warns

* fix some clippy issues

* start making it so the shape impl is on BlockStates

* insane code

* new impl compiles

* fix wrong find_bits + TESTS PASS!

* add a test for slab collision

* fix clippy issues

* ok rust

* fix error that happens when on stairs

* add test for top slabs

* start adding join_is_not_empty

* add more to join_is_not_empty

* top slabs still don't work!!

* x..=0 doesn't work in rust :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley:

* remove comment since i added more useful names

* remove some printlns

* fix walls in some configurations erroring

* fix some warnings

* change comment to \`\`\`ignore instead of \`\`\`no_run

* players are .6 wide not .8

* fix clippy's complaints

* i missed one clippy warning

3 files changed, 122 insertions, 55 deletions

diff --git a/azalea-core/src/bitset.rs b/azalea-core/src/bitset.rs
index 6f0a27ca..270ea837 100644
--- a/azalea-core/src/bitset.rs
+++ b/azalea-core/src/bitset.rs
@@ -1,8 +1,7 @@
-use azalea_buf::{BufReadError, McBufReadable, McBufWritable};
-use std::io::{Read, Write};
+use azalea_buf::McBuf;
 
 /// Represents Java's BitSet, a list of bits.
-#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash, Default, McBuf)]
 pub struct BitSet {
     data: Vec<u64>,
 }
@@ -21,70 +20,84 @@ impl BitSet {
         (self.data[index / 64] & (1u64 << (index % 64))) != 0
     }
 
-    // private static int wordIndex(int bitIndex) {
-    //     return bitIndex >> ADDRESS_BITS_PER_WORD;
-    // }
-    pub fn word_index(bit_index: usize) -> usize {
+    fn check_range(&self, from_index: usize, to_index: usize) {
+        assert!(
+            from_index <= to_index,
+            "fromIndex: {} > toIndex: {}",
+            from_index,
+            to_index
+        );
+    }
+
+    fn word_index(&self, bit_index: usize) -> usize {
         bit_index >> ADDRESS_BITS_PER_WORD
     }
 
-    pub fn clear_from_to(&mut self, from: usize, to: usize) {
-        assert!(from <= to);
-        assert!(to <= self.data.len() * 64);
-        assert!(to > 0);
+    pub fn clear(&mut self, from_index: usize, mut to_index: usize) {
+        self.check_range(from_index, to_index);
+
+        if from_index == to_index {
+            return;
+        }
 
-        if from == to {
+        let start_word_index = self.word_index(from_index);
+        if start_word_index >= self.data.len() {
             return;
         }
 
-        // int startWordIndex = wordIndex(fromIndex);
-        // if (startWordIndex >= wordsInUse)
-        //     return;
-
-        // int endWordIndex = wordIndex(toIndex - 1);
-        // if (endWordIndex >= wordsInUse) {
-        //     toIndex = length();
-        //     endWordIndex = wordsInUse - 1;
-        // }
-
-        // long firstWordMask = WORD_MASK << fromIndex;
-        // long lastWordMask  = WORD_MASK >>> -toIndex;
-        // if (startWordIndex == endWordIndex) {
-        //     // Case 1: One word
-        //     words[startWordIndex] &= ~(firstWordMask & lastWordMask);
-        // } else {
-        //     // Case 2: Multiple words
-        //     // Handle first word
-        //     words[startWordIndex] &= ~firstWordMask;
-
-        //     // Handle intermediate words, if any
-        //     for (int i = startWordIndex+1; i < endWordIndex; i++)
-        //         words[i] = 0;
-
-        //     // Handle last word
-        //     words[endWordIndex] &= ~lastWordMask;
-        // }
-
-        // recalculateWordsInUse();
-        // checkInvariants();
+        let mut end_word_index = self.word_index(to_index - 1);
+        if end_word_index >= self.data.len() {
+            to_index = self.len();
+            end_word_index = self.data.len() - 1;
+        }
+
+        let first_word_mask = u64::MAX << from_index;
+        let last_word_mask = u64::MAX >> (64 - (to_index % 64));
+        if start_word_index == end_word_index {
+            // Case 1: One word
+            self.data[start_word_index] &= !(first_word_mask & last_word_mask);
+        } else {
+            // Case 2: Multiple words
+            // Handle first word
+            self.data[start_word_index] &= !first_word_mask;
+
+            // Handle intermediate words, if any
+            for i in start_word_index + 1..end_word_index {
+                self.data[i] = 0;
+            }
+
+            // Handle last word
+            self.data[end_word_index] &= !last_word_mask;
+        }
     }
-}
 
-impl McBufReadable for BitSet {
-    fn read_from(buf: &mut impl Read) -> Result<Self, BufReadError> {
-        Ok(Self {
-            data: Vec::<u64>::read_from(buf)?,
-        })
+    /// Returns the maximum potential items in the BitSet. This will be divisible by 64.
+    fn len(&self) -> usize {
+        self.data.len() * 64
     }
-}
 
-impl McBufWritable for BitSet {
-    fn write_into(&self, buf: &mut impl Write) -> Result<(), std::io::Error> {
-        self.data.write_into(buf)
+    /// Returns the index of the first bit that is set to `false`
+    /// that occurs on or after the specified starting index.
+    pub fn next_clear_bit(&self, from_index: usize) -> usize {
+        let mut u = self.word_index(from_index);
+        if u >= self.data.len() {
+            return from_index;
+        }
+
+        let mut word = !self.data[u] & (u64::MAX << from_index);
+
+        loop {
+            if word != 0 {
+                return (u * 64) + word.trailing_zeros() as usize;
+            }
+            u += 1;
+            if u == self.data.len() {
+                return self.data.len() * 64;
+            }
+            word = !self.data[u];
+        }
     }
-}
 
-impl BitSet {
     pub fn set(&mut self, bit_index: usize) {
         self.data[bit_index / 64] |= 1u64 << (bit_index % 64);
     }
@@ -105,4 +118,22 @@ mod tests {
         assert_eq!(bitset.index(1), true);
         assert_eq!(bitset.index(2), false);
     }
+
+    #[test]
+    fn test_clear() {
+        let mut bitset = BitSet::new(128);
+        bitset.set(62);
+        bitset.set(63);
+        bitset.set(64);
+        bitset.set(65);
+        bitset.set(66);
+
+        bitset.clear(63, 65);
+
+        assert_eq!(bitset.index(62), true);
+        assert_eq!(bitset.index(63), false);
+        assert_eq!(bitset.index(64), false);
+        assert_eq!(bitset.index(65), true);
+        assert_eq!(bitset.index(66), true);
+    }
 }
diff --git a/azalea-core/src/direction.rs b/azalea-core/src/direction.rs
index 96d20a10..dcc9a654 100644
--- a/azalea-core/src/direction.rs
+++ b/azalea-core/src/direction.rs
@@ -73,7 +73,7 @@ impl AxisCycle {
             Self::Backward => Axis::from_ordinal(floor_mod(axis as i32 - 1, 3)),
         }
     }
-    pub fn cycle_xyz(self, x: u32, y: u32, z: u32, axis: Axis) -> u32 {
+    pub fn cycle_xyz(self, x: i32, y: i32, z: i32, axis: Axis) -> i32 {
         match self {
             Self::None => axis.choose(x, y, z),
             Self::Forward => axis.choose(z, x, y),
diff --git a/azalea-core/src/lib.rs b/azalea-core/src/lib.rs
index 66d9a2ea..f7726a38 100755
--- a/azalea-core/src/lib.rs
+++ b/azalea-core/src/lib.rs
@@ -64,3 +64,39 @@ pub fn binary_search(mut min: i32, max: i32, predicate: &dyn Fn(i32) -> bool) ->
 
     min
 }
+
+pub fn lcm(a: u32, b: u32) -> u64 {
+    let gcd = gcd(a, b);
+    (a as u64) * (b / gcd) as u64
+}
+pub fn gcd(mut a: u32, mut b: u32) -> u32 {
+    while b != 0 {
+        let t = b;
+        b = a % b;
+        a = t;
+    }
+    a
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_gcd() {
+        assert_eq!(gcd(0, 0), 0);
+        assert_eq!(gcd(1, 1), 1);
+
+        assert_eq!(gcd(0, 1), 1);
+        assert_eq!(gcd(1, 0), 1);
+
+        assert_eq!(gcd(12, 8), 4);
+        assert_eq!(gcd(8, 12), 4);
+
+        assert_eq!(gcd(12, 9), 3);
+        assert_eq!(gcd(9, 12), 3);
+
+        assert_eq!(gcd(12, 7), 1);
+        assert_eq!(gcd(7, 12), 1);
+    }
+}