steel_core/chunk/
paletted_container.rs

1//! A paletted container is a container that can be either homogeneous or heterogeneous.
2use std::{
3    fmt::Debug,
4    hash::Hash,
5    io::{Result, Write},
6    mem, slice,
7    sync::OnceLock,
8};
9
10use steel_registry::blocks::block_state_ext::BlockStateExt;
11use steel_registry::{REGISTRY, RegistryExt as _};
12use steel_utils::{BlockStateId, codec::VarInt, mth::ceil_log2, serial::WriteTo};
13
14mod encode;
15
16/// A trait for converting a value to a global ID.
17pub trait ToGlobalId {
18    /// Converts the value to a global ID.
19    fn to_global_id(&self) -> u32;
20}
21
22impl ToGlobalId for BlockStateId {
23    fn to_global_id(&self) -> u32 {
24        u32::from(self.0)
25    }
26}
27
28impl ToGlobalId for u16 {
29    fn to_global_id(&self) -> u32 {
30        u32::from(*self)
31    }
32}
33
34/// 3d array indexed by y,z,x
35type Cube<T, const DIM: usize> = [[[T; DIM]; DIM]; DIM];
36
37/// A heterogeneous palette container.
38///
39/// Every value in the cube appears exactly once in the palette. The fields are private so
40/// only this module can change the cube and palette together.
41#[derive(Debug, Clone)]
42pub struct HeterogeneousPalette<V: Hash + Eq + Copy, const DIM: usize> {
43    cube: Box<Cube<V, DIM>>,
44    // Keeps track of how many different times each value appears in the cube. (value, count)
45    palette: Vec<(V, u16)>,
46}
47
48impl<V: Hash + Eq + Copy, const DIM: usize> HeterogeneousPalette<V, DIM> {
49    /// The distinct values in the cube, each with the number of cells holding it.
50    pub(crate) fn palette(&self) -> &[(V, u16)] {
51        &self.palette
52    }
53
54    /// All values in y, z, x order.
55    pub(crate) fn values(&self) -> &[V] {
56        self.cube.as_flattened().as_flattened()
57    }
58
59    fn get(&self, x: usize, y: usize, z: usize) -> V {
60        debug_assert!(x < DIM);
61        debug_assert!(y < DIM);
62        debug_assert!(z < DIM);
63
64        self.cube[y][z][x]
65    }
66
67    fn get_at_index(&self, index: usize) -> V {
68        debug_assert!(index < DIM * DIM * DIM);
69
70        let y = index / (DIM * DIM);
71        let z = (index / DIM) % DIM;
72        let x = index % DIM;
73        self.cube[y][z][x]
74    }
75
76    /// Returns an iterator over all values in the cube in y, z, x order.
77    pub fn iter_values(&self) -> impl Iterator<Item = &V> {
78        self.values().iter()
79    }
80
81    fn set(&mut self, x: usize, y: usize, z: usize, value: V) -> V {
82        debug_assert!(x < DIM);
83        debug_assert!(y < DIM);
84        debug_assert!(z < DIM);
85
86        let old_value = self.cube[y][z][x];
87
88        if let Some((_, count)) = self.palette.iter_mut().find(|(v, _)| *v == value) {
89            *count += 1;
90        } else {
91            self.palette.push((value, 1));
92        }
93
94        if let Some((index, (_, count))) = self
95            .palette
96            .iter_mut()
97            .enumerate()
98            .find(|(_, (v, _))| *v == old_value)
99        {
100            *count -= 1;
101            if *count == 0 {
102                self.palette.swap_remove(index);
103            }
104        }
105
106        self.cube[y][z][x] = value;
107
108        old_value
109    }
110}
111
112/// A paletted container.
113///
114/// `Building` is a transient mode used during worldgen: it's a raw cube without
115/// palette tracking, so writes are O(1) stores. Must be finalized via
116/// [`Self::finalize_building`] (or implicitly when the parent section recalculates
117/// its counters) before any serialization or paletted access. Mirrors
118/// `FastNoise`'s `FastChunkSection` write-only fill mode.
119#[derive(Debug, Clone)]
120pub enum PalettedContainer<V: Hash + Eq + Copy + Default, const DIM: usize> {
121    /// A homogeneous container, where all values are the same.
122    Homogeneous(V),
123    /// A heterogeneous container, where values can be different.
124    Heterogeneous(HeterogeneousPalette<V, DIM>),
125    /// Write-only build mode: raw cube without palette tracking.
126    /// `set` is a single store; `get` is a direct read.
127    /// Convert back via [`Self::finalize_building`].
128    Building(Box<Cube<V, DIM>>),
129}
130
131enum PaletteMode {
132    Linear,
133    Hash,
134    Global,
135}
136
137impl<V: Hash + Eq + Copy + Default + Debug, const DIM: usize> PalettedContainer<V, DIM> {
138    /// The size of the container in one dimension.
139    pub const SIZE: usize = DIM;
140    /// The volume of the container.
141    pub const VOLUME: usize = DIM * DIM * DIM;
142
143    /// Creates a `PalettedContainer` from a pre-built cube.
144    ///
145    /// Will automatically determine if the result should be homogeneous or heterogeneous.
146    ///
147    /// Walks the cube as a flat slice (it's `[[[V; DIM]; DIM]; DIM]` so memory
148    /// is contiguous) and counts identical cells in runs. The inner "find run
149    /// end" loop is a vectorizable equality scan, so long stone columns collapse
150    /// to a single palette increment.
151    #[must_use]
152    pub fn from_cube(cube: Box<Cube<V, DIM>>) -> Self {
153        let mut palette: Vec<(V, u16)> = Vec::new();
154        let total = DIM * DIM * DIM;
155        // SAFETY: `[[[V; DIM]; DIM]; DIM]` is a fully-contiguous array of
156        // `DIM*DIM*DIM` `V`s, so casting its base pointer to `*const V` and
157        // building a slice of that length is sound. `cube` is a live `Box`, so
158        // the pointer is valid for the lifetime of the slice.
159        let flat: &[V] = unsafe { slice::from_raw_parts(cube.as_ptr().cast::<V>(), total) };
160
161        let mut i = 0;
162        while i < total {
163            let v = flat[i];
164            let mut j = i + 1;
165            while j < total && flat[j] == v {
166                j += 1;
167            }
168            let run_len = (j - i) as u16;
169            if let Some(pos) = palette.iter().position(|(value, _)| *value == v) {
170                palette[pos].1 += run_len;
171            } else {
172                palette.push((v, run_len));
173            }
174            i = j;
175        }
176
177        if palette.len() == 1 {
178            Self::Homogeneous(palette[0].0)
179        } else {
180            Self::Heterogeneous(HeterogeneousPalette { cube, palette })
181        }
182    }
183
184    /// Gets the value at the given coordinates.
185    pub fn get(&self, x: usize, y: usize, z: usize) -> V {
186        match self {
187            Self::Homogeneous(value) => *value,
188            Self::Heterogeneous(data) => data.get(x, y, z),
189            Self::Building(cube) => {
190                debug_assert!(x < DIM);
191                debug_assert!(y < DIM);
192                debug_assert!(z < DIM);
193                cube[y][z][x]
194            }
195        }
196    }
197
198    /// Gets the value at a y,z,x linear index.
199    ///
200    /// The index layout is `x + z * DIM + y * DIM * DIM`, matching the flat
201    /// order used when serializing palette data and by `ScalableLux` light propagation.
202    pub fn get_at_index(&self, index: usize) -> V {
203        debug_assert!(index < Self::VOLUME);
204
205        match self {
206            Self::Homogeneous(value) => *value,
207            Self::Heterogeneous(data) => data.get_at_index(index),
208            Self::Building(cube) => {
209                let y = index / (DIM * DIM);
210                let z = (index / DIM) % DIM;
211                let x = index % DIM;
212                cube[y][z][x]
213            }
214        }
215    }
216
217    /// Copies the full vertical column at `(x, z)` into `out`.
218    pub(crate) fn copy_column_into(&self, x: usize, z: usize, out: &mut [V]) {
219        debug_assert!(x < DIM);
220        debug_assert!(z < DIM);
221        debug_assert!(out.len() >= DIM);
222
223        match self {
224            Self::Homogeneous(value) => {
225                for slot in &mut out[..DIM] {
226                    *slot = *value;
227                }
228            }
229            Self::Heterogeneous(data) => {
230                for (y, slot) in out[..DIM].iter_mut().enumerate() {
231                    *slot = data.cube[y][z][x];
232                }
233            }
234            Self::Building(cube) => {
235                for (y, slot) in out[..DIM].iter_mut().enumerate() {
236                    *slot = cube[y][z][x];
237                }
238            }
239        }
240    }
241
242    /// Returns whether this container's palette may contain a matching value.
243    ///
244    /// This checks palette entries instead of every cell, matching vanilla and
245    /// `ScalableLux`'s fast pre-scan before doing a full section pass.
246    #[must_use]
247    pub fn maybe_has(&self, mut predicate: impl FnMut(V) -> bool) -> bool {
248        match self {
249            Self::Homogeneous(value) => predicate(*value),
250            Self::Heterogeneous(data) => data.palette.iter().any(|(value, _)| predicate(*value)),
251            Self::Building(cube) => cube
252                .iter()
253                .flatten()
254                .flatten()
255                .any(|value| predicate(*value)),
256        }
257    }
258
259    /// Collects all values in the container in y, z, x order.
260    #[must_use]
261    pub fn collect_values(&self) -> Vec<V> {
262        match self {
263            Self::Homogeneous(value) => vec![*value; Self::VOLUME],
264            Self::Heterogeneous(data) => data.iter_values().copied().collect(),
265            Self::Building(cube) => cube.iter().flatten().flatten().copied().collect(),
266        }
267    }
268
269    /// Switches the container into write-only build mode for fast bulk writes.
270    /// Idempotent: a no-op if already in [`Self::Building`].
271    ///
272    /// Allocates a `Cube` if currently `Homogeneous`. For `Heterogeneous` it
273    /// reuses the existing cube allocation.
274    pub fn enter_building_mode(&mut self) {
275        match self {
276            Self::Building(_) => {}
277            Self::Homogeneous(value) => {
278                let cube: Box<Cube<V, DIM>> = Box::new([[[*value; DIM]; DIM]; DIM]);
279                *self = Self::Building(cube);
280            }
281            Self::Heterogeneous(_) => {
282                let taken = mem::replace(self, Self::Homogeneous(V::default()));
283                let Self::Heterogeneous(data) = taken else {
284                    unreachable!()
285                };
286                *self = Self::Building(data.cube);
287            }
288        }
289    }
290
291    /// Returns the raw cube backing this container as a flat mutable slice if
292    /// it's currently in [`Self::Building`] mode. Indexing is `[y * DIM*DIM + z * DIM + x]`.
293    ///
294    /// Used by the chunk fill path to bypass the 3-arm `set` dispatch and the
295    /// unused old-value load — write-only worldgen never reads back what it
296    /// just wrote, so the read in `set` is wasted memory traffic.
297    #[inline]
298    pub fn as_building_slice_mut(&mut self) -> Option<&mut [V]> {
299        if let Self::Building(cube) = self {
300            // SAFETY: `[[[V; DIM]; DIM]; DIM]` is a contiguous array of
301            // `DIM*DIM*DIM` `V`s; the cast preserves the live `&mut Box`'s
302            // borrow because the returned slice cannot outlive `self`.
303            Some(unsafe {
304                slice::from_raw_parts_mut(cube.as_mut_ptr().cast::<V>(), DIM * DIM * DIM)
305            })
306        } else {
307            None
308        }
309    }
310
311    /// Finalizes a [`Self::Building`] container back to `Homogeneous` or
312    /// `Heterogeneous` by scanning the cube once and constructing the palette.
313    /// No-op if not in build mode.
314    pub fn finalize_building(&mut self) {
315        if !matches!(self, Self::Building(_)) {
316            return;
317        }
318        let taken = mem::replace(self, Self::Homogeneous(V::default()));
319        let Self::Building(cube) = taken else {
320            unreachable!()
321        };
322        *self = Self::from_cube(cube);
323    }
324
325    /// Writes `value` without updating the palette, breaking its invariant for tests.
326    #[cfg(test)]
327    pub(crate) fn set_without_palette_for_test(&mut self, x: usize, y: usize, z: usize, value: V) {
328        if let Self::Heterogeneous(data) = self {
329            data.cube[y][z][x] = value;
330        }
331    }
332
333    /// Sets the value at the given coordinates.
334    pub fn set(&mut self, x: usize, y: usize, z: usize, value: V) -> V {
335        debug_assert!(x < Self::SIZE);
336        debug_assert!(y < Self::SIZE);
337        debug_assert!(z < Self::SIZE);
338
339        match self {
340            Self::Homogeneous(original) => {
341                let original = *original;
342                if value != original {
343                    let mut cube = Box::new([[[original; DIM]; DIM]; DIM]);
344                    cube[y][z][x] = value;
345                    *self = Self::from_cube(cube);
346                }
347                original
348            }
349            Self::Heterogeneous(data) => {
350                let original = data.set(x, y, z, value);
351                if data.palette.len() == 1 {
352                    *self = Self::Homogeneous(data.palette[0].0);
353                }
354                original
355            }
356            Self::Building(cube) => {
357                let old = cube[y][z][x];
358                cube[y][z][x] = value;
359                old
360            }
361        }
362    }
363
364    /// Writes the container to the given writer.
365    ///
366    /// # Errors
367    /// - If the writer fails to write.
368    /// - If the container holds a value its palette cannot encode: one missing from its
369    ///   section palette, or a global id too wide for the global palette. Nothing is
370    ///   written then.
371    ///
372    /// # Panics
373    /// - If the container is in [`Self::Building`] mode.
374    pub fn write(&self, writer: &mut impl Write) -> Result<()>
375    where
376        V: ToGlobalId,
377    {
378        match self {
379            Self::Homogeneous(value) => {
380                // bits per entry = 0 (ZeroBitStorage)
381                0u8.write(writer)?;
382                // Single-value palette
383                VarInt(value.to_global_id() as i32).write(writer)?;
384                // writeFixedSizeLongArray(new long[0]) writes nothing
385            }
386            Self::Heterogeneous(data) => {
387                let (bits, mode) = Self::calculate_strategy(data.palette.len());
388                // Packed first, so a broken palette fails before anything is written.
389                let mut buffer = [0; encode::MAX_PACKED_BYTES];
390                let packed = match mode {
391                    PaletteMode::Global => {
392                        encode::pack_global_ids(data.values(), bits, &mut buffer)?
393                    }
394                    PaletteMode::Linear | PaletteMode::Hash => encode::pack_palette_indices(
395                        data.values(),
396                        &data.palette,
397                        bits,
398                        &mut buffer,
399                    )?,
400                };
401
402                // Write bits per entry
403                bits.write(writer)?;
404
405                // Write Palette
406                match mode {
407                    PaletteMode::Linear | PaletteMode::Hash => {
408                        VarInt(data.palette.len() as i32).write(writer)?;
409                        for (val, _) in &data.palette {
410                            VarInt(val.to_global_id() as i32).write(writer)?;
411                        }
412                    }
413                    PaletteMode::Global => {}
414                }
415
416                // writeFixedSizeLongArray: raw longs, no VarInt length prefix
417                writer.write_all(packed)?;
418            }
419            Self::Building(_) => {
420                panic!(
421                    "PalettedContainer in Building mode cannot be serialized; \
422                     call finalize_building() first"
423                );
424            }
425        }
426        Ok(())
427    }
428
429    fn calculate_strategy(count: usize) -> (u8, PaletteMode) {
430        if DIM == 16 {
431            // Block states
432            match count {
433                0..=1 => unreachable!("Homogeneous handled separately"),
434                2..=16 => (4, PaletteMode::Linear),
435                17..=32 => (5, PaletteMode::Hash),
436                33..=64 => (6, PaletteMode::Hash),
437                65..=128 => (7, PaletteMode::Hash),
438                129..=256 => (8, PaletteMode::Hash),
439                _ => (block_state_global_bits(), PaletteMode::Global),
440            }
441        } else {
442            // Biomes
443            match count {
444                0..=1 => unreachable!("Homogeneous handled separately"),
445                2 => (1, PaletteMode::Linear),
446                3..=4 => (2, PaletteMode::Linear),
447                5..=8 => (3, PaletteMode::Hash),
448                _ => (biome_global_bits(), PaletteMode::Global),
449            }
450        }
451    }
452}
453
454/// Bits per entry for the block-state global palette.
455///
456/// Derived from the registered block-state count and cached on first use, so a
457/// version bump that changes the state count doesn't need a matching hardcoded
458/// constant here. Matches vanilla, which sizes the global palette from the
459/// registry rather than a fixed width.
460fn block_state_global_bits() -> u8 {
461    ceil_log2(usize::from(REGISTRY.blocks.next_state_id))
462}
463
464/// Bits per entry for the biome global palette. See [`block_state_global_bits`].
465fn biome_global_bits() -> u8 {
466    static BITS: OnceLock<u8> = OnceLock::new();
467    *BITS.get_or_init(|| ceil_log2(REGISTRY.biomes.len()))
468}
469
470/// A palette container for blocks.
471pub type BlockPalette = PalettedContainer<BlockStateId, 16>;
472/// A palette container for biomes.
473pub type BiomePalette = PalettedContainer<u16, 4>;
474
475impl BlockPalette {
476    /// Gets the number of non-empty blocks in the container.
477    #[must_use]
478    pub fn non_empty_block_count(&self) -> u16 {
479        match self {
480            Self::Homogeneous(v) => {
481                if v.0 == 0 {
482                    0
483                } else {
484                    #[expect(
485                        clippy::cast_possible_truncation,
486                        reason = "VOLUME = 16^3 = 4096, fits in u16"
487                    )]
488                    {
489                        Self::VOLUME as u16
490                    }
491                }
492            }
493            Self::Heterogeneous(data) => {
494                let mut count = 0;
495                for (v, c) in &data.palette {
496                    if v.0 != 0 {
497                        count += c;
498                    }
499                }
500                count
501            }
502            Self::Building(cube) => {
503                let mut count: u16 = 0;
504                for slab in cube {
505                    for row in slab {
506                        for v in row {
507                            if v.0 != 0 {
508                                count += 1;
509                            }
510                        }
511                    }
512                }
513                count
514            }
515        }
516    }
517
518    /// Returns `true` if this palette contains only air blocks.
519    #[must_use]
520    pub fn has_only_air(&self) -> bool {
521        match self {
522            Self::Homogeneous(v) => v.is_air(),
523            //TODO: Use a nonEmpty counter?
524            Self::Heterogeneous(_data) => false,
525            Self::Building(cube) => cube
526                .iter()
527                .flatten()
528                .flatten()
529                .all(steel_utils::BlockStateId::is_air),
530        }
531    }
532}
533
534#[cfg(test)]
535mod tests {
536    use std::io::{Cursor, ErrorKind};
537
538    use super::{
539        BiomePalette, BlockPalette, ToGlobalId, biome_global_bits, block_state_global_bits,
540    };
541    use steel_registry::init_vanilla_registry;
542    use steel_utils::{BlockStateId, codec::VarInt, serial::ReadFrom as _};
543
544    fn assert_column_matches_get(container: &BlockPalette, x: usize, z: usize) {
545        let mut column = [BlockStateId::default(); 16];
546        container.copy_column_into(x, z, &mut column);
547        for (y, state) in column.into_iter().enumerate() {
548            assert_eq!(state, container.get(x, y, z));
549        }
550    }
551
552    #[test]
553    fn get_at_index_reads_homogeneous_palette_values() {
554        let container = BlockPalette::Homogeneous(BlockStateId(42));
555
556        assert_eq!(container.get_at_index(0), BlockStateId(42));
557        assert_eq!(
558            container.get_at_index(BlockPalette::VOLUME - 1),
559            BlockStateId(42)
560        );
561    }
562
563    #[test]
564    fn get_at_index_uses_y_z_x_linear_order_for_blocks() {
565        let mut container = BlockPalette::Homogeneous(BlockStateId(0));
566
567        container.set(3, 4, 5, BlockStateId(99));
568
569        assert_eq!(
570            container.get_at_index(3 + 5 * 16 + 4 * 16 * 16),
571            BlockStateId(99)
572        );
573    }
574
575    #[test]
576    fn maybe_has_checks_palette_values_without_scanning_cells() {
577        let mut container = BlockPalette::Homogeneous(BlockStateId(0));
578        assert!(!container.maybe_has(|state| state == BlockStateId(7)));
579
580        container.set(1, 2, 3, BlockStateId(7));
581        assert!(container.maybe_has(|state| state == BlockStateId(7)));
582        assert!(!container.maybe_has(|state| state == BlockStateId(9)));
583    }
584
585    #[test]
586    fn copy_column_into_matches_get_for_homogeneous_container() {
587        let container = BlockPalette::Homogeneous(BlockStateId(7));
588        assert_column_matches_get(&container, 3, 12);
589    }
590
591    #[test]
592    fn copy_column_into_matches_get_for_heterogeneous_container() {
593        let x = 5;
594        let z = 9;
595        let mut cube = Box::new([[[BlockStateId::default(); 16]; 16]; 16]);
596        for y in 0..16 {
597            cube[y][z][x] = BlockStateId((y + 1) as u16);
598        }
599
600        let container = BlockPalette::from_cube(cube);
601        assert_column_matches_get(&container, x, z);
602    }
603
604    #[test]
605    fn copy_column_into_matches_get_for_building_container() {
606        let x = 11;
607        let z = 2;
608        let mut container = BlockPalette::Homogeneous(BlockStateId(3));
609        container.enter_building_mode();
610        for y in 0..16 {
611            container.set(x, y, z, BlockStateId((31 + y) as u16));
612        }
613
614        assert_column_matches_get(&container, x, z);
615    }
616
617    /// The written long array has no length prefix, so a wrong bit width
618    /// desyncs every section parsed after this one.
619    #[test]
620    fn block_global_palette_uses_registry_derived_bit_width_and_long_count() {
621        init_vanilla_registry();
622        let mut cube = Box::new([[[BlockStateId::default(); 16]; 16]; 16]);
623        let mut next_id = 1u16;
624        for slab in &mut cube {
625            for row in slab.iter_mut() {
626                for value in row.iter_mut() {
627                    *value = BlockStateId(next_id);
628                    next_id = next_id.wrapping_add(1);
629                }
630            }
631        }
632        let container = BlockPalette::from_cube(cube);
633
634        let mut written = Vec::new();
635        container
636            .write(&mut written)
637            .expect("writing a global-palette container should not fail");
638
639        let expected_bits = block_state_global_bits();
640        assert_eq!(written[0], expected_bits);
641        let values_per_long = 64 / usize::from(expected_bits);
642        let expected_longs = BlockPalette::VOLUME.div_ceil(values_per_long);
643        assert_eq!(written.len(), 1 + expected_longs * 8);
644    }
645
646    #[test]
647    fn biome_global_palette_uses_registry_derived_bit_width_and_long_count() {
648        init_vanilla_registry();
649        let mut cube = Box::new([[[0u16; 4]; 4]; 4]);
650        let mut next_id = 1u16;
651        for slab in &mut cube {
652            for row in slab.iter_mut() {
653                for value in row.iter_mut() {
654                    *value = next_id;
655                    next_id += 1;
656                }
657            }
658        }
659        let container = BiomePalette::from_cube(cube);
660
661        let mut written = Vec::new();
662        container
663            .write(&mut written)
664            .expect("writing a global-palette container should not fail");
665
666        let expected_bits = biome_global_bits();
667        assert_eq!(written[0], expected_bits);
668        let values_per_long = 64 / usize::from(expected_bits);
669        let expected_longs = BiomePalette::VOLUME.div_ceil(values_per_long);
670        assert_eq!(written.len(), 1 + expected_longs * 8);
671    }
672
673    /// Reads `write` output the way the vanilla client does: a bits byte, the palette
674    /// (absent for the global palette), then `64 / bits` entries per big-endian long.
675    /// Returns each entry's global id.
676    fn decode_written(bytes: &[u8], volume: usize, max_paletted_bits: u8) -> Vec<u32> {
677        let bits = bytes[0];
678        let mut cursor = Cursor::new(bytes);
679        cursor.set_position(1);
680        if bits == 0 {
681            let value = VarInt::read(&mut cursor).expect("single value").0 as u32;
682            assert_eq!(cursor.position() as usize, bytes.len());
683            return vec![value; volume];
684        }
685        let palette = (bits <= max_paletted_bits).then(|| {
686            let len = VarInt::read(&mut cursor).expect("palette length").0 as u32;
687            (0..len)
688                .map(|_| VarInt::read(&mut cursor).expect("palette entry").0 as u32)
689                .collect::<Vec<_>>()
690        });
691        let bits = usize::from(bits);
692        let values_per_long = 64 / bits;
693        let longs: Vec<u64> = bytes[cursor.position() as usize..]
694            .as_chunks::<8>()
695            .0
696            .iter()
697            .map(|long| u64::from_be_bytes(*long))
698            .collect();
699        assert_eq!(longs.len(), volume.div_ceil(values_per_long));
700        (0..volume)
701            .map(|index| {
702                let long = longs[index / values_per_long];
703                let entry = (long >> ((index % values_per_long) * bits)) & ((1 << bits) - 1);
704                match &palette {
705                    Some(palette) => palette[entry as usize],
706                    None => entry as u32,
707                }
708            })
709            .collect()
710    }
711
712    fn xorshift(state: &mut u64) -> u64 {
713        *state ^= *state << 13;
714        *state ^= *state >> 7;
715        *state ^= *state << 17;
716        *state
717    }
718
719    /// Covers each block palette strategy, including the widths where a long holds a
720    /// partial final group (5, 6 and 7 bits).
721    #[test]
722    fn written_block_sections_decode_to_their_values_for_every_strategy() {
723        init_vanilla_registry();
724        let mut rng = 0x9E37_79B9_7F4A_7C15_u64;
725        for distinct in [2u16, 16, 17, 33, 65, 129, 256, 257] {
726            let mut cube = Box::new([[[BlockStateId::default(); 16]; 16]; 16]);
727            for (index, value) in cube.iter_mut().flatten().flatten().enumerate() {
728                // Every state appears at least once, the rest are random.
729                let state = if index < usize::from(distinct) {
730                    index as u16
731                } else {
732                    (xorshift(&mut rng) % u64::from(distinct)) as u16
733                };
734                *value = BlockStateId(1 + state);
735            }
736            let container = BlockPalette::from_cube(cube);
737            let mut written = Vec::new();
738            container
739                .write(&mut written)
740                .expect("a valid container should encode");
741
742            let expected: Vec<u32> = container
743                .collect_values()
744                .iter()
745                .map(ToGlobalId::to_global_id)
746                .collect();
747            assert_eq!(
748                decode_written(&written, BlockPalette::VOLUME, 8),
749                expected,
750                "{distinct} distinct states"
751            );
752        }
753    }
754
755    #[test]
756    fn written_biome_sections_decode_to_their_values_for_every_strategy() {
757        init_vanilla_registry();
758        for distinct in [2u16, 3, 5, 9] {
759            let mut cube = Box::new([[[0u16; 4]; 4]; 4]);
760            for (index, value) in cube.iter_mut().flatten().flatten().enumerate() {
761                *value = index as u16 % distinct;
762            }
763            let container = BiomePalette::from_cube(cube);
764            let mut written = Vec::new();
765            container
766                .write(&mut written)
767                .expect("a valid container should encode");
768
769            let expected: Vec<u32> = container
770                .collect_values()
771                .iter()
772                .map(|v| u32::from(*v))
773                .collect();
774            assert_eq!(
775                decode_written(&written, BiomePalette::VOLUME, 3),
776                expected,
777                "{distinct} distinct biomes"
778            );
779        }
780    }
781
782    /// Global-palette ids are written without a section palette, so an id wider than the
783    /// global width would spill into the neighboring entry instead of being rejected.
784    #[test]
785    fn write_rejects_global_id_too_wide_for_the_global_palette() {
786        init_vanilla_registry();
787        let global_bits = biome_global_bits();
788        let mut cube = Box::new([[[0u16; 4]; 4]; 4]);
789        for (index, value) in cube.iter_mut().flatten().flatten().enumerate() {
790            *value = index as u16;
791        }
792        cube[0][0][0] = 1 << global_bits;
793        let container = BiomePalette::from_cube(cube);
794
795        let mut written = Vec::new();
796        let error = container
797            .write(&mut written)
798            .expect_err("an id too wide for the global palette must not encode");
799        assert_eq!(error.kind(), ErrorKind::InvalidData);
800        assert!(written.is_empty(), "nothing should be written on failure");
801    }
802
803    /// The encoder reuses a per-thread index table. A section holding a value missing from
804    /// its palette must be rejected even when an earlier section indexed that value.
805    #[test]
806    fn write_rejects_value_missing_from_palette_after_it_was_indexed_elsewhere() {
807        let stray = BlockStateId(7);
808        let mut primer_cube = Box::new([[[BlockStateId(1); 16]; 16]; 16]);
809        primer_cube[0][0][1] = stray;
810        let mut written = Vec::new();
811        BlockPalette::from_cube(primer_cube)
812            .write(&mut written)
813            .expect("a valid container should encode");
814
815        let mut cube = Box::new([[[BlockStateId(1); 16]; 16]; 16]);
816        cube[0][0][1] = BlockStateId(2);
817        let mut corrupt = BlockPalette::from_cube(cube);
818        corrupt.set_without_palette_for_test(0, 0, 0, stray);
819
820        let mut written = Vec::new();
821        let error = corrupt
822            .write(&mut written)
823            .expect_err("a value missing from the palette must not encode");
824        assert_eq!(error.kind(), ErrorKind::InvalidData);
825        assert!(written.is_empty(), "nothing should be written on failure");
826    }
827}
steel_core/chunk/paletted_container.rs

steel_core/chunk/
paletted_container.rs
