Skip to main content

dayzmake_core/navmesh/detour/
set.rs

1//! The `TESM` tile mesh set file (spec 9.1, 9.2, 9.4, 9.6) and the 64-bit polygon reference
2//! (spec 8.1).
3
4use std::collections::BTreeMap;
5use std::fs;
6use std::io::{self, BufWriter, Read, Write};
7use std::path::Path;
8
9use crate::error::ErrorExt;
10use crate::navmesh::bytes::Reader;
11use crate::navmesh::detour::tile::TileData;
12
13/// The set file magic: the bytes `TESM`.
14pub const SET_MAGIC: i32 = i32::from_le_bytes(*b"TESM");
15/// The set version DayZ 1.30 accepts; the only one written.
16pub const SET_VERSION: i32 = 9;
17/// The set version of DayZ 1.29 and earlier. Same layout; accepted when reading.
18pub const SET_VERSION_OLD: i32 = 7;
19
20const SET_HEADER_LEN: usize = 48;
21const RECORD_HEADER_LEN: usize = 16;
22const EMPTY_SLOT: u32 = 0xFFFF_FFFF;
23/// Reads of a record blob grow the buffer in steps of at most this size.
24const READ_CHUNK: usize = 1 << 20;
25
26const SALT_MASK: u32 = 0xFFFF;
27const TILE_MASK: u32 = 0x0FFF_FFFF;
28const POLY_MASK: u32 = 0x000F_FFFF;
29
30/// Packs a 64-bit polygon reference: `salt << 48 | tile << 20 | poly` (16, 28 and 20 bits; wider
31/// values are masked).
32#[must_use]
33pub fn encode_poly_ref(salt: u32, tile: u32, poly: u32) -> u64 {
34    (u64::from(salt & SALT_MASK) << 48)
35        | (u64::from(tile & TILE_MASK) << 20)
36        | u64::from(poly & POLY_MASK)
37}
38
39/// Splits a polygon reference into `(salt, tile, poly)`.
40#[must_use]
41pub fn decode_poly_ref(r: u64) -> (u32, u32, u32) {
42    let field = |shift: u32, mask: u32| u32::try_from((r >> shift) & u64::from(mask)).unwrap_or(0);
43    (
44        field(48, SALT_MASK),
45        field(20, TILE_MASK),
46        field(0, POLY_MASK),
47    )
48}
49
50/// `dtNavMeshParams` as stored in the set header.
51#[derive(Debug, Clone, Default, PartialEq)]
52#[non_exhaustive]
53pub struct NavMeshParams {
54    /// Origin (0, 0, 0).
55    pub orig: [f32; 3],
56    /// Tile width, metres.
57    pub tile_width: f32,
58    /// Tile height (depth), metres.
59    pub tile_height: f32,
60    /// Number of tile slots.
61    pub max_tiles: i32,
62    /// Polygon limit per tile (`1 << 20`).
63    pub max_polys: i32,
64}
65
66/// One tile record of a set file (spec 9.2).
67#[derive(Debug, Clone, Default, PartialEq)]
68#[non_exhaustive]
69pub struct SetTile {
70    /// `salt << 48 | slot << 20`.
71    pub tile_ref: u64,
72    /// The padding word of the record: 0 in shipped maps, preserved on rewrite.
73    pub padding: u32,
74    /// The Detour tile.
75    pub data: TileData,
76}
77
78/// A `.nm` file: the mesh parameters and the tile records in file order.
79///
80/// Reading is sequential, as the game does it: the offset table is skipped (its size comes from
81/// `maxTiles`) and its entries are not used, and `numTiles` records follow back to back. Writing
82/// always produces version [`SET_VERSION`] and recomputes the offset table.
83#[derive(Debug, Clone, Default, PartialEq)]
84#[non_exhaustive]
85pub struct NavMeshSet {
86    /// The set version read from the file (7 or 9). Writing ignores this field and always writes
87    /// [`SET_VERSION`].
88    pub version: i32,
89    /// Grid width in tiles.
90    pub tiles_x: i32,
91    /// Grid depth in tiles.
92    pub tiles_z: i32,
93    /// The mesh parameters.
94    pub params: NavMeshParams,
95    /// The tile records, in file order.
96    pub tiles: Vec<SetTile>,
97}
98
99fn file_truncated() -> io::Error {
100    error!("navmesh file truncated")
101}
102
103/// Reads `len` bytes, growing the buffer in chunks, so that a length field larger than the file
104/// cannot make the reader allocate more than the file holds.
105fn read_chunked(r: &mut impl Read, len: usize) -> io::Result<Option<Vec<u8>>> {
106    let mut buf = Vec::new();
107    while buf.len() < len {
108        let start = buf.len();
109        let end = start.saturating_add(READ_CHUNK).min(len);
110        buf.resize(end, 0);
111        let Some(chunk) = buf.get_mut(start..end) else {
112            return Ok(None);
113        };
114        match r.read_exact(chunk) {
115            Ok(()) => {}
116            Err(e) if e.kind() == io::ErrorKind::UnexpectedEof => return Ok(None),
117            Err(e) => return Err(e),
118        }
119    }
120    Ok(Some(buf))
121}
122
123impl NavMeshSet {
124    /// Reads a set file. Rejects a bad magic, a version other than 7 or 9, `numTiles > maxTiles`,
125    /// negative counts, a record with `tileRef == 0` or `dataSize <= 0`, a record running past the
126    /// end of the input, and any tile blob that [`TileData::parse`] rejects (spec 9.4).
127    ///
128    /// The input is consumed up to the end of the last record; nothing is allocated from a length
129    /// field before the input has delivered that many bytes.
130    ///
131    /// # Errors
132    ///
133    /// Returns an error for any of the rejections above, or when the reader fails.
134    pub fn read(r: &mut impl Read) -> io::Result<Self> {
135        let mut head = [0u8; SET_HEADER_LEN];
136        r.read_exact(&mut head).map_err(|e| {
137            if e.kind() == io::ErrorKind::UnexpectedEof {
138                file_truncated()
139            } else {
140                e
141            }
142        })?;
143        let mut h = Reader::new(&head);
144        let magic = h.i32()?;
145        if magic != SET_MAGIC {
146            return Err(error!("Invalid header format (bad magic)"));
147        }
148        let version = h.i32()?;
149        if version != SET_VERSION && version != SET_VERSION_OLD {
150            return Err(error!("Invalid version {version}"));
151        }
152        let num_tiles = h.i32()?;
153        let tiles_x = h.i32()?;
154        let tiles_z = h.i32()?;
155        let params = NavMeshParams {
156            orig: h.f32x3()?,
157            tile_width: h.f32()?,
158            tile_height: h.f32()?,
159            max_tiles: h.i32()?,
160            max_polys: h.i32()?,
161        };
162        let max_tiles = u32::try_from(params.max_tiles)
163            .map_err(|_| error!("negative maxTiles {}", params.max_tiles))?;
164        let num_tiles =
165            u32::try_from(num_tiles).map_err(|_| error!("negative numTiles {num_tiles}"))?;
166        if num_tiles > max_tiles {
167            return Err(error!("numTiles {num_tiles} exceeds maxTiles {max_tiles}"));
168        }
169
170        // The offset table is not needed: the records follow back to back. Skip it without
171        // allocating; a file shorter than the table is rejected.
172        let table = u64::from(max_tiles) * 4;
173        let skipped = io::copy(&mut r.by_ref().take(table), &mut io::sink())?;
174        if skipped != table {
175            return Err(file_truncated());
176        }
177
178        let mut tiles = Vec::new();
179        for i in 0..num_tiles {
180            let mut rec = [0u8; RECORD_HEADER_LEN];
181            r.read_exact(&mut rec).map_err(|e| {
182                if e.kind() == io::ErrorKind::UnexpectedEof {
183                    error!("tile record {i} runs past the end of the file")
184                } else {
185                    e
186                }
187            })?;
188            let mut rh = Reader::new(&rec);
189            let tile_ref = rh.u64()?;
190            let data_size = rh.i32()?;
191            let padding = rh.u32()?;
192            if tile_ref == 0 {
193                return Err(error!("tile record {i} has tileRef 0"));
194            }
195            let size = usize::try_from(data_size)
196                .ok()
197                .filter(|&n| n > 0)
198                .ok_or_else(|| error!("tile record {i} has dataSize {data_size}"))?;
199            let blob = read_chunked(r, size)?
200                .ok_or_else(|| error!("tile record {i} runs past the end of the file"))?;
201            let data = TileData::parse(&blob).prepend_error(format!("tile record {i}:"))?;
202            tiles.push(SetTile {
203                tile_ref,
204                padding,
205                data,
206            });
207        }
208        Ok(Self {
209            version,
210            tiles_x,
211            tiles_z,
212            params,
213            tiles,
214        })
215    }
216
217    /// Writes the file: version [`SET_VERSION`], the offset table of spec 9.1 (offsets relative to
218    /// the first record, `0xFFFFFFFF` for empty slots) and the records in `tiles` order.
219    ///
220    /// # Errors
221    ///
222    /// Returns an error, before writing anything, for a negative `maxTiles`, more tiles than
223    /// `maxTiles`, a `tile_ref` of 0, a tile whose slot is `>= maxTiles` or used twice, or offsets
224    /// above `0xFFFFFFFE`; or when the writer fails.
225    pub fn write(&self, w: &mut impl Write) -> io::Result<()> {
226        let max_tiles = u32::try_from(self.params.max_tiles)
227            .map_err(|_| error!("negative maxTiles {}", self.params.max_tiles))?;
228        let too_many = || error!("{} tiles exceed maxTiles {max_tiles}", self.tiles.len());
229        let num_tiles = u32::try_from(self.tiles.len()).map_err(|_| too_many())?;
230        if num_tiles > max_tiles {
231            return Err(too_many());
232        }
233        let mut offsets: BTreeMap<u32, u32> = BTreeMap::new();
234        let mut sizes = Vec::with_capacity(self.tiles.len());
235        let mut offset: u64 = 0;
236        for t in &self.tiles {
237            if t.tile_ref == 0 {
238                return Err(error!("tile with tileRef 0"));
239            }
240            let slot = decode_poly_ref(t.tile_ref).1;
241            if slot >= max_tiles {
242                return Err(error!("tile slot {slot} is not below maxTiles {max_tiles}"));
243            }
244            let size = t
245                .data
246                .blob_len()
247                .and_then(|n| i32::try_from(n).ok())
248                .ok_or_else(|| error!("tile in slot {slot} is too large"))?;
249            let at = u32::try_from(offset)
250                .ok()
251                .filter(|&o| o != EMPTY_SLOT)
252                .ok_or_else(|| error!("tile offset {offset} does not fit the offset table"))?;
253            if offsets.insert(slot, at).is_some() {
254                return Err(error!("two tiles in slot {slot}"));
255            }
256            sizes.push(size);
257            offset +=
258                u64::try_from(RECORD_HEADER_LEN).unwrap_or(16) + u64::from(size.unsigned_abs());
259        }
260
261        let mut head = Vec::with_capacity(SET_HEADER_LEN);
262        head.extend_from_slice(&SET_MAGIC.to_le_bytes());
263        head.extend_from_slice(&SET_VERSION.to_le_bytes());
264        head.extend_from_slice(&num_tiles.to_le_bytes());
265        head.extend_from_slice(&self.tiles_x.to_le_bytes());
266        head.extend_from_slice(&self.tiles_z.to_le_bytes());
267        for f in self.params.orig {
268            head.extend_from_slice(&f.to_le_bytes());
269        }
270        head.extend_from_slice(&self.params.tile_width.to_le_bytes());
271        head.extend_from_slice(&self.params.tile_height.to_le_bytes());
272        head.extend_from_slice(&self.params.max_tiles.to_le_bytes());
273        head.extend_from_slice(&self.params.max_polys.to_le_bytes());
274        w.write_all(&head)?;
275
276        // The table, in chunks: maxTiles can be large even when few tiles are present.
277        let mut chunk = Vec::with_capacity(16 * 1024);
278        for slot in 0..max_tiles {
279            let v = offsets.get(&slot).copied().unwrap_or(EMPTY_SLOT);
280            chunk.extend_from_slice(&v.to_le_bytes());
281            if chunk.len() >= 16 * 1024 {
282                w.write_all(&chunk)?;
283                chunk.clear();
284            }
285        }
286        w.write_all(&chunk)?;
287
288        for (t, size) in self.tiles.iter().zip(sizes) {
289            let blob = t.data.to_bytes();
290            if i32::try_from(blob.len()).ok() != Some(size) {
291                return Err(error!("tile blob size changed while writing"));
292            }
293            w.write_all(&t.tile_ref.to_le_bytes())?;
294            w.write_all(&size.to_le_bytes())?;
295            w.write_all(&t.padding.to_le_bytes())?;
296            w.write_all(&blob)?;
297        }
298        Ok(())
299    }
300
301    /// Writes the file atomically (spec 9.6, ruling 11): into a uniquely named temporary file in the
302    /// target's directory, then `sync_all`, then a rename over `path`. An interrupted or failed
303    /// write leaves the previous file untouched and removes the temporary file.
304    ///
305    /// # Errors
306    ///
307    /// Returns an error when [`NavMeshSet::write`] fails or the file cannot be created, synced or
308    /// renamed.
309    pub fn write_atomic(&self, path: &Path) -> io::Result<()> {
310        let name = path
311            .file_name()
312            .ok_or_else(|| error!("{} has no file name", path.display()))?
313            .to_string_lossy()
314            .into_owned();
315        let dir = match path.parent() {
316            Some(p) if !p.as_os_str().is_empty() => p,
317            _ => Path::new("."),
318        };
319        let pid = std::process::id();
320        let mut n = 0u32;
321        let (tmp, file) = loop {
322            let tmp = dir.join(format!(".{name}.{pid}.{n}.tmp"));
323            match fs::OpenOptions::new()
324                .write(true)
325                .create_new(true)
326                .open(&tmp)
327            {
328                Ok(f) => break (tmp, f),
329                Err(e) if e.kind() == io::ErrorKind::AlreadyExists && n < 1000 => n += 1,
330                Err(e) => return Err(e),
331            }
332        };
333        let result = (|| {
334            let mut w = BufWriter::new(file);
335            self.write(&mut w)?;
336            let file = w.into_inner().map_err(io::IntoInnerError::into_error)?;
337            file.sync_all()?;
338            fs::rename(&tmp, path)
339        })();
340        if result.is_err() {
341            // Best effort: the original error is what the caller needs.
342            let _ = fs::remove_file(&tmp);
343        }
344        result.prepend_error(format!("writing {}:", path.display()))
345    }
346}