simplify bit storage

5 files changed, 117 insertions, 93 deletions

diff --git a/Cargo.lock b/Cargo.lock
index c06072fb..675cfbc1 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -587,7 +587,6 @@ dependencies = [
 name = "azalea-world"
 version = "0.15.0+mc1.21.11"
 dependencies = [
- "azalea",
  "azalea-block",
  "azalea-buf",
  "azalea-core",
@@ -597,6 +596,7 @@ dependencies = [
  "derive_more",
  "nohash-hasher",
  "parking_lot",
+ "rand 0.10.0-rc.7",
  "rustc-hash",
  "serde",
  "tracing",
diff --git a/azalea-world/Cargo.toml b/azalea-world/Cargo.toml
index 9e1a2729..73b2d3a8 100644
--- a/azalea-world/Cargo.toml
+++ b/azalea-world/Cargo.toml
@@ -7,8 +7,8 @@ license.workspace = true
 repository.workspace = true
 
 [dev-dependencies]
-azalea.path = "../azalea"
 criterion.workspace = true
+rand.workspace = true
 
 [dependencies]
 azalea-block.workspace = true
diff --git a/azalea-world/benches/chunks.rs b/azalea-world/benches/chunks.rs
index 64924fec..e1ca94a6 100644
--- a/azalea-world/benches/chunks.rs
+++ b/azalea-world/benches/chunks.rs
@@ -3,7 +3,7 @@ use std::hint::black_box;
 use azalea_core::position::ChunkBlockPos;
 use azalea_registry::builtin::BlockKind;
 use azalea_world::{BitStorage, Chunk};
-use criterion::{Criterion, criterion_group, criterion_main};
+use criterion::{BatchSize, Bencher, Criterion, criterion_group, criterion_main};
 
 fn bench_chunks(c: &mut Criterion) {
     c.bench_function("Chunk::set", |b| {
@@ -25,13 +25,36 @@ fn bench_chunks(c: &mut Criterion) {
     });
 }
 
+fn bench_bitstorage_with(b: &mut Bencher, bits: usize, size: usize) {
+    let mut storage = BitStorage::new(bits, size, None).unwrap();
+    b.iter_batched(
+        || {
+            // let index = rand
+            let mut vec = Vec::with_capacity(size);
+            for _ in 0..size {
+                vec.push(rand::random_range(0..size));
+            }
+            vec
+        },
+        |indices| {
+            for index in indices {
+                storage.set(index, 1);
+            }
+        },
+        BatchSize::SmallInput,
+    );
+    black_box(storage);
+}
+
 fn bench_bitstorage(c: &mut Criterion) {
-    c.bench_function("BitStorage::set", |b| {
-        let mut storage = BitStorage::new(1, 4096, None).unwrap();
-        b.iter(|| {
-            storage.set(136, 1);
-        });
-        black_box(storage);
+    c.bench_function("BitStorage::set (1 bit per entry)", |b| {
+        bench_bitstorage_with(b, 1, 4096)
+    });
+    c.bench_function("BitStorage::set (2 bits per entry)", |b| {
+        bench_bitstorage_with(b, 2, 4096)
+    });
+    c.bench_function("BitStorage::set (3 bits per entry)", |b| {
+        bench_bitstorage_with(b, 3, 4096)
     });
 }
 
diff --git a/azalea-world/src/bit_storage.rs b/azalea-world/src/bit_storage.rs
index daad9202..44705f88 100644
--- a/azalea-world/src/bit_storage.rs
+++ b/azalea-world/src/bit_storage.rs
@@ -1,72 +1,73 @@
 use std::{error::Error, fmt};
 
+// fast constant division
 #[rustfmt::skip]
-const MAGIC: [(i32, i32, i32); 64] = [
-    // divide_mul, divide_add, divide_shift
-    (-1, -1, 0),
-    (-0b10000000000000000000000000000000, 0, 0),
-    (0b1010101010101010101010101010101, 0b1010101010101010101010101010101, 0),
-    (-0b10000000000000000000000000000000, 0, 1),
-    (0b110011001100110011001100110011, 0b110011001100110011001100110011, 0),
-    (0b101010101010101010101010101010, 0b101010101010101010101010101010, 0),
-    (0b100100100100100100100100100100, 0b100100100100100100100100100100, 0),
-    (-0b10000000000000000000000000000000, 0, 2),
-    (0b11100011100011100011100011100, 0b11100011100011100011100011100, 0),
-    (0b11001100110011001100110011001, 0b11001100110011001100110011001, 0),
-    (0b10111010001011101000101110100, 0b10111010001011101000101110100, 0),
-    (0b10101010101010101010101010101, 0b10101010101010101010101010101, 0),
-    (0b10011101100010011101100010011, 0b10011101100010011101100010011, 0),
-    (0b10010010010010010010010010010, 0b10010010010010010010010010010, 0),
-    (0b10001000100010001000100010001, 0b10001000100010001000100010001, 0),
-    (-0b10000000000000000000000000000000, 0, 3),
-    (0b1111000011110000111100001111, 0b1111000011110000111100001111, 0),
-    (0b1110001110001110001110001110, 0b1110001110001110001110001110, 0),
-    (0b1101011110010100001101011110, 0b1101011110010100001101011110, 0),
-    (0b1111111111111111111111111111000, 0b1111111111111111111111111111000, 0),
-    (0b1100001100001100001100001100, 0b1100001100001100001100001100, 0),
-    (0b1011101000101110100010111010, 0b1011101000101110100010111010, 0),
-    (0b1011001000010110010000101100, 0b1011001000010110010000101100, 0),
-    (0b1010101010101010101010101010, 0b1010101010101010101010101010, 0),
-    (0b1010001111010111000010100011, 0b1010001111010111000010100011, 0),
-    (0b1001110110001001110110001001, 0b1001110110001001110110001001, 0),
-    (0b1001011110110100001001011110, 0b1001011110110100001001011110, 0),
-    (0b1001001001001001001001001001, 0b1001001001001001001001001001, 0),
-    (0b1000110100111101110010110000, 0b1000110100111101110010110000, 0),
-    (0b1000100010001000100010001000, 0b1000100010001000100010001000, 0),
-    (0b1000010000100001000010000100, 0b1000010000100001000010000100, 0),
-    (-0b10000000000000000000000000000000, 0, 4),
-    (0b111110000011111000001111100, 0b111110000011111000001111100, 0),
-    (0b111100001111000011110000111, 0b111100001111000011110000111, 0),
-    (0b111010100000111010100000111, 0b111010100000111010100000111, 0),
-    (0b111000111000111000111000111, 0b111000111000111000111000111, 0),
-    (0b110111010110011111001000101, 0b110111010110011111001000101, 0),
-    (0b110101111001010000110101111, 0b110101111001010000110101111, 0),
-    (0b110100100000110100100000110, 0b110100100000110100100000110, 0),
-    (0b110011001100110011001100110, 0b110011001100110011001100110, 0),
-    (0b110001111100111000001100011, 0b110001111100111000001100011, 0),
-    (0b110000110000110000110000110, 0b110000110000110000110000110, 0),
-    (0b101111101000001011111010000, 0b101111101000001011111010000, 0),
-    (0b101110100010111010001011101, 0b101110100010111010001011101, 0),
-    (0b101101100000101101100000101, 0b101101100000101101100000101, 0),
-    (0b101100100001011001000010110, 0b101100100001011001000010110, 0),
-    (0b101011100100110001000001010, 0b101011100100110001000001010, 0),
-    (0b101010101010101010101010101, 0b101010101010101010101010101, 0),
-    (0b101001110010111100000101001, 0b101001110010111100000101001, 0),
-    (0b101000111101011100001010001, 0b101000111101011100001010001, 0),
-    (0b101000001010000010100000101, 0b101000001010000010100000101, 0),
-    (0b100111011000100111011000100, 0b100111011000100111011000100, 0),
-    (0b100110101001000011100111110, 0b100110101001000011100111110, 0),
-    (0b100101111011010000100101111, 0b100101111011010000100101111, 0),
-    (0b100101001111001000001001010, 0b100101001111001000001001010, 0),
-    (0b100100100100100100100100100, 0b100100100100100100100100100, 0),
-    (0b100011111011100000100011111, 0b100011111011100000100011111, 0),
-    (0b100011010011110111001011000, 0b100011010011110111001011000, 0),
-    (0b100010101101100011110010111, 0b100010101101100011110010111, 0),
-    (0b100010001000100010001000100, 0b100010001000100010001000100, 0),
-    (0b100001100100101110001010011, 0b100001100100101110001010011, 0),
-    (0b100001000010000100001000010, 0b100001000010000100001000010, 0),
-    (0b100000100000100000100000100, 0b100000100000100000100000100, 0),
-    (-0b10000000000000000000000000000000, 0, 5),
+const MAGIC: [(i32, i32, u32); 64] = [
+    // mul, add, shift
+    (1, 0, 0), // divide by 1
+    (1, 0, 1), // divide by 2, etc
+    (0x55555555, 0x55555555, 32),
+    (1, 0, 2),
+    (0x33333333, 0x33333333, 32),
+    (0x2AAAAAAA, 0x2AAAAAAA, 32),
+    (0x24924924, 0x24924924, 32),
+    (1, 0, 3),
+    (0x1C71C71C, 0x1C71C71C, 32),
+    (0x19999999, 0x19999999, 32),
+    (0x1745D174, 0x1745D174, 32),
+    (0x15555555, 0x15555555, 32),
+    (0x13B13B13, 0x13B13B13, 32),
+    (0x12492492, 0x12492492, 32),
+    (0x11111111, 0x11111111, 32),
+    (1, 0, 4),
+    (0xF0F0F0F, 0xF0F0F0F, 32),
+    (0xE38E38E, 0xE38E38E, 32),
+    (0xD79435E, 0xD79435E, 32),
+    (0x7FFFFFF8, 0x7FFFFFF8, 32),
+    (0xC30C30C, 0xC30C30C, 32),
+    (0xBA2E8BA, 0xBA2E8BA, 32),
+    (0xB21642C, 0xB21642C, 32),
+    (0xAAAAAAA, 0xAAAAAAA, 32),
+    (0xA3D70A3, 0xA3D70A3, 32),
+    (0x9D89D89, 0x9D89D89, 32),
+    (0x97B425E, 0x97B425E, 32),
+    (0x9249249, 0x9249249, 32),
+    (0x8D3DCB0, 0x8D3DCB0, 32),
+    (0x8888888, 0x8888888, 32),
+    (0x8421084, 0x8421084, 32),
+    (1, 0, 5),
+    (0x7C1F07C, 0x7C1F07C, 32),
+    (0x7878787, 0x7878787, 32),
+    (0x7507507, 0x7507507, 32),
+    (0x71C71C7, 0x71C71C7, 32),
+    (0x6EB3E45, 0x6EB3E45, 32),
+    (0x6BCA1AF, 0x6BCA1AF, 32),
+    (0x6906906, 0x6906906, 32),
+    (0x6666666, 0x6666666, 32),
+    (0x63E7063, 0x63E7063, 32),
+    (0x6186186, 0x6186186, 32),
+    (0x5F417D0, 0x5F417D0, 32),
+    (0x5D1745D, 0x5D1745D, 32),
+    (0x5B05B05, 0x5B05B05, 32),
+    (0x590B216, 0x590B216, 32),
+    (0x572620A, 0x572620A, 32),
+    (0x5555555, 0x5555555, 32),
+    (0x5397829, 0x5397829, 32),
+    (0x51EB851, 0x51EB851, 32),
+    (0x5050505, 0x5050505, 32),
+    (0x4EC4EC4, 0x4EC4EC4, 32),
+    (0x4D4873E, 0x4D4873E, 32),
+    (0x4BDA12F, 0x4BDA12F, 32),
+    (0x4A7904A, 0x4A7904A, 32),
+    (0x4924924, 0x4924924, 32),
+    (0x47DC11F, 0x47DC11F, 32),
+    (0x469EE58, 0x469EE58, 32),
+    (0x456C797, 0x456C797, 32),
+    (0x4444444, 0x4444444, 32),
+    (0x4325C53, 0x4325C53, 32),
+    (0x4210842, 0x4210842, 32),
+    (0x4104104, 0x4104104, 32),
+    (1, 0, 6),
 ];
 
 /// A compact list of integers with the given number of bits per entry.
@@ -77,9 +78,9 @@ pub struct BitStorage {
     mask: u64,
     size: usize,
     values_per_long: usize,
-    divide_mul: u64,
-    divide_add: u64,
-    divide_shift: i32,
+    divide_mul: i32,
+    divide_add: i32,
+    divide_shift: u32,
 }
 
 #[derive(Debug)]
@@ -99,8 +100,8 @@ impl fmt::Display for BitStorageError {
 impl Error for BitStorageError {}
 
 impl BitStorage {
-    /// Create a new BitStorage with the given number of bits per entry.
-    /// `size` is the number of entries in the BitStorage.
+    /// Create a new BitStorage with the given number of bits per entry. `size`
+    /// is the number of entries in the BitStorage.
     pub fn new(
         bits: usize,
         size: usize,
@@ -145,18 +146,19 @@ impl BitStorage {
             mask,
             size,
             values_per_long,
-            divide_mul: divide_mul as u32 as u64,
-            divide_add: divide_add as u32 as u64,
+            divide_mul,
+            divide_add,
             divide_shift,
         })
     }
 
-    pub fn cell_index(&self, index: u64) -> usize {
-        // as unsigned wrap
-        let first = self.divide_mul;
-        let second = self.divide_add;
+    #[inline]
+    fn cell_index(&self, index: u64) -> usize {
+        let mul = self.divide_mul as u32 as u64;
+        let add = self.divide_add as u32 as u64;
+        let shift = self.divide_shift;
 
-        (((index * first) + second) >> 32 >> self.divide_shift) as usize
+        (((index * mul) + add) >> shift) as usize
     }
 
     /// Get the data at the given index.
@@ -254,7 +256,9 @@ mod tests {
     use super::*;
 
     #[test]
-    fn test_wikivg_example() {
+    fn test_protocol_wiki_example() {
+        // https://minecraft.wiki/w/Java_Edition_protocol/Chunk_format#Visual_example
+
         let data = [
             1, 2, 2, 3, 4, 4, 5, 6, 6, 4, 8, 0, 7, 4, 3, 13, 15, 16, 9, 14, 10, 12, 0, 2,
         ];
diff --git a/azalea-world/src/find_blocks.rs b/azalea-world/src/find_blocks.rs
index f8f1fd91..0980e825 100644
--- a/azalea-world/src/find_blocks.rs
+++ b/azalea-world/src/find_blocks.rs
@@ -11,11 +11,8 @@ impl World {
     ///
     /// ```
     /// # use azalea_registry::builtin::BlockKind;
-    /// # fn example(client: &azalea::Client) {
-    /// client
-    ///     .world()
-    ///     .read()
-    ///     .find_block(client.position(), &BlockKind::Chest.into());
+    /// # fn example(world: &World) {
+    /// let pos = world.find_block(client.position(), &BlockKind::Chest.into());
     /// # }
     /// ```
     pub fn find_block(