Skip to main content

meshoptimizer_rs/
analyze.rs

1//! Scalar cache and fetch analyzers from pinned `indexanalyzer.cpp`.
2use crate::workspace::{checked_bytes, topology};
3use crate::{Error, Workspace};
4
5/// Result of upstream `meshopt_analyzeVertexCache`.
6#[derive(Clone, Copy, Debug, Default, PartialEq)]
7pub struct VertexCacheStatistics {
8    /// Number of vertex shader transforms.
9    pub vertices_transformed: u32,
10    /// Number of nonempty simulated warps.
11    pub warps_executed: u32,
12    /// Transforms divided by triangle count.
13    pub acmr: f32,
14    /// Transforms divided by unique vertex count.
15    pub atvr: f32,
16}
17
18/// Result of upstream `meshopt_analyzeVertexFetch`.
19#[derive(Clone, Copy, Debug, Default, PartialEq)]
20pub struct VertexFetchStatistics {
21    /// Bytes read by the simulated cache.
22    pub bytes_fetched: u32,
23    /// Bytes fetched divided by referenced vertex bytes.
24    pub overfetch: f32,
25}
26
27#[allow(clippy::too_many_arguments)]
28fn cache_run<const WARP: bool, const GROUP: bool, const CHARGE: bool>(
29    indices: &[u32],
30    timestamps: &mut [u32],
31    cache_size: u32,
32    warp_size: u32,
33    primgroup_size: u32,
34    work: &mut crate::workspace::Work,
35) -> Result<(VertexCacheStatistics, u32), Error> {
36    let mut result = VertexCacheStatistics::default();
37    let mut timestamp = cache_size.wrapping_add(1);
38    let (mut warp_offset, mut primgroup_offset) = (0u32, 0u32);
39    for triangle in indices.as_chunks::<3>().0 {
40        if CHARGE {
41            work.add(3)?;
42        }
43        let [a, b, c] = *triangle;
44        let misses = if WARP {
45            u32::from(timestamp.wrapping_sub(timestamps[a as usize]) > cache_size)
46                + u32::from(timestamp.wrapping_sub(timestamps[b as usize]) > cache_size)
47                + u32::from(timestamp.wrapping_sub(timestamps[c as usize]) > cache_size)
48        } else {
49            0
50        };
51        if (GROUP && primgroup_offset == primgroup_size)
52            || (WARP && warp_offset + misses > warp_size)
53        {
54            result.warps_executed += u32::from(warp_offset > 0);
55            warp_offset = 0;
56            primgroup_offset = 0;
57            timestamp = timestamp.wrapping_add(cache_size).wrapping_add(1);
58        }
59        for index in [a, b, c] {
60            let entry = &mut timestamps[index as usize];
61            if timestamp.wrapping_sub(*entry) > cache_size {
62                *entry = timestamp;
63                timestamp = timestamp.wrapping_add(1);
64                // topology limits the index stream to u32::MAX entries;
65                // one entry can trigger at most one transform here.
66                result.vertices_transformed += 1;
67                warp_offset += 1;
68            }
69        }
70        if GROUP {
71            primgroup_offset += 1;
72        }
73    }
74    Ok((result, warp_offset))
75}
76
77#[inline(always)]
78fn cache_simple(
79    indices: &[u32],
80    timestamps: &mut [u32],
81    cache_size: u32,
82) -> (VertexCacheStatistics, u32) {
83    let mut result = VertexCacheStatistics::default();
84    let mut timestamp = cache_size.wrapping_add(1);
85    for &index in indices {
86        let entry = &mut timestamps[index as usize];
87        if timestamp.wrapping_sub(*entry) > cache_size {
88            *entry = timestamp;
89            timestamp = timestamp.wrapping_add(1);
90            result.vertices_transformed += 1;
91        }
92    }
93    let present = u32::from(result.vertices_transformed > 0);
94    (result, present)
95}
96
97/// Analyze a triangle list using upstream's simplified FIFO transform cache.
98///
99/// # Errors
100/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
101/// `InvalidParameter` for unsupported analyzer settings; `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
102#[inline(always)]
103pub fn analyze_vertex_cache(
104    indices: &[u32],
105    vertex_count: usize,
106    cache_size: u32,
107    warp_size: u32,
108    primgroup_size: u32,
109    workspace: &mut Workspace,
110) -> Result<VertexCacheStatistics, Error> {
111    let mut work = workspace.begin();
112    let result = vertex_cache_impl(
113        indices,
114        vertex_count,
115        cache_size,
116        warp_size,
117        primgroup_size,
118        workspace,
119        &mut work,
120    );
121    workspace.finish(&work);
122    result
123}
124
125#[inline(always)]
126#[allow(clippy::too_many_arguments)]
127fn vertex_cache_impl(
128    indices: &[u32],
129    vertex_count: usize,
130    cache_size: u32,
131    warp_size: u32,
132    primgroup_size: u32,
133    workspace: &mut Workspace,
134    work: &mut crate::workspace::Work,
135) -> Result<VertexCacheStatistics, Error> {
136    if cache_size < 3 || (warp_size != 0 && warp_size < 3) {
137        return Err(Error::InvalidParameter);
138    }
139    topology(indices, vertex_count, work)?;
140    checked_bytes(vertex_count, 4)?;
141    let retained = workspace.integers.len().min(vertex_count);
142    workspace.prepare_timestamps(vertex_count)?;
143    let timestamps = &mut workspace.integers[..vertex_count];
144    // prepare zero-initializes newly added entries; only retained values
145    // can contain timestamps from a previous call.
146    timestamps[..retained].fill(0);
147    let bulk_work = work.covers(indices.len())?;
148    if bulk_work {
149        work.add(indices.len())?;
150    }
151    let (mut result, warp_offset) = match (warp_size != 0, primgroup_size != 0, bulk_work) {
152        (false, false, false) => cache_run::<false, false, true>(
153            indices,
154            timestamps,
155            cache_size,
156            warp_size,
157            primgroup_size,
158            work,
159        )?,
160        (false, false, true) => cache_simple(indices, timestamps, cache_size),
161        (false, true, false) => cache_run::<false, true, true>(
162            indices,
163            timestamps,
164            cache_size,
165            warp_size,
166            primgroup_size,
167            work,
168        )?,
169        (false, true, true) => cache_run::<false, true, false>(
170            indices,
171            timestamps,
172            cache_size,
173            warp_size,
174            primgroup_size,
175            work,
176        )?,
177        (true, false, false) => cache_run::<true, false, true>(
178            indices,
179            timestamps,
180            cache_size,
181            warp_size,
182            primgroup_size,
183            work,
184        )?,
185        (true, false, true) => cache_run::<true, false, false>(
186            indices,
187            timestamps,
188            cache_size,
189            warp_size,
190            primgroup_size,
191            work,
192        )?,
193        (true, true, false) => cache_run::<true, true, true>(
194            indices,
195            timestamps,
196            cache_size,
197            warp_size,
198            primgroup_size,
199            work,
200        )?,
201        (true, true, true) => cache_run::<true, true, false>(
202            indices,
203            timestamps,
204            cache_size,
205            warp_size,
206            primgroup_size,
207            work,
208        )?,
209    };
210    let unique = timestamps.iter().filter(|&&value| value > 0).count();
211    work.add(vertex_count)?;
212    result.warps_executed += u32::from(warp_offset > 0);
213    result.acmr = if indices.is_empty() {
214        0.0
215    } else {
216        result.vertices_transformed as f32 / (indices.len() / 3) as f32
217    };
218    result.atvr = if unique == 0 {
219        0.0
220    } else {
221        result.vertices_transformed as f32 / unique as f32
222    };
223    Ok(result)
224}
225
226// With <=64-byte vertices and the proven fuel/u32 bounds, an index
227// touches one or two lines. Avoid a general range loop for that common case.
228fn fetch_small(
229    indices: &[u32],
230    visited: &mut [u8],
231    vertex_size: usize,
232    cache: &mut [usize; 2048],
233    work: &mut crate::workspace::Work,
234) -> Result<u32, Error> {
235    let mut bytes_fetched = 0;
236    let mut extra_lines = 0;
237    for &index in indices {
238        visited[index as usize] = 1;
239        let start = index as usize * vertex_size;
240        let tag = start / 64;
241        let first = &mut cache[tag % 2048];
242        bytes_fetched += u32::from(*first != tag + 1) * 64;
243        *first = tag + 1;
244        if (start & 63) + vertex_size > 64 {
245            let second = &mut cache[(tag + 1) % 2048];
246            bytes_fetched += u32::from(*second != tag + 2) * 64;
247            *second = tag + 2;
248            extra_lines += 1;
249        }
250    }
251    // The caller proved 6*len visits fit, so this <=3*len count cannot overflow.
252    work.add(indices.len() * 2 + extra_lines)?;
253    Ok(bytes_fetched)
254}
255
256fn fetch_run<const CHARGE: bool, const CHECK: bool>(
257    indices: &[u32],
258    visited: &mut [u8],
259    vertex_size: usize,
260    cache: &mut [usize; 2048],
261    work: &mut crate::workspace::Work,
262) -> Result<u32, Error> {
263    let mut bytes_fetched = 0u32;
264    let mut visits = if CHECK { 0 } else { indices.len() };
265    for &index in indices {
266        if CHARGE {
267            work.add(1)?;
268        }
269        if CHECK {
270            visits += 1;
271        }
272        visited[index as usize] = 1;
273        let start = index as usize * vertex_size;
274        let end = start + vertex_size;
275        // The validated vertex byte extent is at most isize::MAX, so
276        // adding 63 cannot overflow usize on either supported word size.
277        let start_tag = start / 64;
278        #[allow(clippy::manual_div_ceil)] // Proven non-overflowing add has cheaper codegen.
279        let end_tag = (end + 63) / 64;
280        if !CHECK {
281            visits += end_tag - start_tag;
282        }
283        for tag in start_tag..end_tag {
284            if CHARGE {
285                work.add(1)?;
286            }
287            if CHECK {
288                visits += 1;
289            }
290            let line = &mut cache[tag % 2048];
291            if CHECK {
292                if *line != tag + 1 {
293                    bytes_fetched = match bytes_fetched.checked_add(64) {
294                        Some(bytes) => bytes,
295                        None => {
296                            if !CHARGE {
297                                work.add(visits)?;
298                            }
299                            return Err(Error::SizeOverflow);
300                        }
301                    };
302                }
303            } else {
304                bytes_fetched += u32::from(*line != tag + 1) * 64;
305            }
306            *line = tag + 1;
307        }
308    }
309    if !CHARGE {
310        work.add(visits)?;
311    }
312    Ok(bytes_fetched)
313}
314
315/// Analyze index order with upstream's direct-mapped 128 KiB fetch-cache model.
316///
317/// # Errors
318/// `IndexOutOfBounds` for invalid vertex references;
319/// `InvalidParameter` for unsupported analyzer settings; `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
320pub fn analyze_vertex_fetch(
321    indices: &[u32],
322    vertex_count: usize,
323    vertex_size: usize,
324    workspace: &mut Workspace,
325) -> Result<VertexFetchStatistics, Error> {
326    let mut work = workspace.begin();
327    let result = (|| {
328        if !(1..=256).contains(&vertex_size) {
329            return Err(Error::InvalidParameter);
330        }
331        if vertex_count > u32::MAX as usize {
332            return Err(Error::SizeOverflow);
333        }
334        checked_bytes(vertex_count, vertex_size)?;
335        work.indices(indices, vertex_count)?;
336        let retained = workspace.flags.len().min(vertex_count);
337        workspace.prepare([0, 0, vertex_count, 0], 0)?;
338        let visited = &mut workspace.flags[..vertex_count];
339        visited[..retained].fill(0);
340        let mut cache = [0usize; 2048];
341        let mut result = VertexFetchStatistics::default();
342        // An index visits at most five cache lines. With sufficient fuel,
343        // count the visits locally and charge once; the fallback keeps the
344        // exact exhaustion point and partial usage for low limits.
345        let bulk_work = match indices.len().checked_mul(6) {
346            Some(max_visits) => work.covers(max_visits)?,
347            None => false,
348        };
349        // A vertex spans at most five 64-byte lines. This upper bound proves
350        // u32 accumulation safe without weakening the overflow error contract.
351        let bounded_bytes = indices.len() <= u32::MAX as usize / (5 * 64);
352        result.bytes_fetched = if bulk_work && bounded_bytes && vertex_size <= 64 {
353            fetch_small(indices, visited, vertex_size, &mut cache, &mut work)?
354        } else {
355            match (bulk_work, bounded_bytes) {
356                (true, true) => {
357                    fetch_run::<false, false>(indices, visited, vertex_size, &mut cache, &mut work)?
358                }
359                (true, false) => {
360                    fetch_run::<false, true>(indices, visited, vertex_size, &mut cache, &mut work)?
361                }
362                (false, true) => {
363                    fetch_run::<true, false>(indices, visited, vertex_size, &mut cache, &mut work)?
364                }
365                (false, false) => {
366                    fetch_run::<true, true>(indices, visited, vertex_size, &mut cache, &mut work)?
367                }
368            }
369        };
370        // Every visited flag was initialized to zero and is written only as one.
371        let unique: usize = visited.iter().map(|&value| usize::from(value)).sum();
372        work.add(vertex_count)?;
373        result.overfetch = if unique == 0 {
374            0.0
375        } else {
376            result.bytes_fetched as f32 / (unique * vertex_size) as f32
377        };
378        Ok(result)
379    })();
380    workspace.finish(&work);
381    result
382}