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_generic<I: crate::Index>(
104    indices: &[I],
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    I::with_input(indices, workspace, |indices, workspace| {
112        analyze_vertex_cache_u32(
113            indices,
114            vertex_count,
115            cache_size,
116            warp_size,
117            primgroup_size,
118            workspace,
119        )
120    })
121}
122
123fn analyze_vertex_cache_u32(
124    indices: &[u32],
125    vertex_count: usize,
126    cache_size: u32,
127    warp_size: u32,
128    primgroup_size: u32,
129    workspace: &mut Workspace,
130) -> Result<VertexCacheStatistics, Error> {
131    let mut work = workspace.begin();
132    let result = vertex_cache_impl(
133        indices,
134        vertex_count,
135        cache_size,
136        warp_size,
137        primgroup_size,
138        workspace,
139        &mut work,
140    );
141    workspace.finish(&work);
142    result
143}
144
145#[inline(always)]
146#[allow(clippy::too_many_arguments)]
147fn vertex_cache_impl(
148    indices: &[u32],
149    vertex_count: usize,
150    cache_size: u32,
151    warp_size: u32,
152    primgroup_size: u32,
153    workspace: &mut Workspace,
154    work: &mut crate::workspace::Work,
155) -> Result<VertexCacheStatistics, Error> {
156    if cache_size < 3 || (warp_size != 0 && warp_size < 3) {
157        return Err(Error::InvalidParameter);
158    }
159    topology(indices, vertex_count, work)?;
160    checked_bytes(vertex_count, 4)?;
161    let retained = workspace.integers.len().min(vertex_count);
162    workspace.prepare_timestamps(vertex_count)?;
163    let timestamps = &mut workspace.integers[..vertex_count];
164    // prepare zero-initializes newly added entries; only retained values
165    // can contain timestamps from a previous call.
166    timestamps[..retained].fill(0);
167    let bulk_work = work.covers(indices.len())?;
168    if bulk_work {
169        work.add(indices.len())?;
170    }
171    let (mut result, warp_offset) = match (warp_size != 0, primgroup_size != 0, bulk_work) {
172        (false, false, false) => cache_run::<false, false, true>(
173            indices,
174            timestamps,
175            cache_size,
176            warp_size,
177            primgroup_size,
178            work,
179        )?,
180        (false, false, true) => cache_simple(indices, timestamps, cache_size),
181        (false, true, false) => cache_run::<false, true, true>(
182            indices,
183            timestamps,
184            cache_size,
185            warp_size,
186            primgroup_size,
187            work,
188        )?,
189        (false, true, true) => cache_run::<false, true, false>(
190            indices,
191            timestamps,
192            cache_size,
193            warp_size,
194            primgroup_size,
195            work,
196        )?,
197        (true, false, false) => cache_run::<true, false, true>(
198            indices,
199            timestamps,
200            cache_size,
201            warp_size,
202            primgroup_size,
203            work,
204        )?,
205        (true, false, true) => cache_run::<true, false, false>(
206            indices,
207            timestamps,
208            cache_size,
209            warp_size,
210            primgroup_size,
211            work,
212        )?,
213        (true, true, false) => cache_run::<true, true, true>(
214            indices,
215            timestamps,
216            cache_size,
217            warp_size,
218            primgroup_size,
219            work,
220        )?,
221        (true, true, true) => cache_run::<true, true, false>(
222            indices,
223            timestamps,
224            cache_size,
225            warp_size,
226            primgroup_size,
227            work,
228        )?,
229    };
230    let unique = timestamps.iter().filter(|&&value| value > 0).count();
231    work.add(vertex_count)?;
232    result.warps_executed += u32::from(warp_offset > 0);
233    result.acmr = if indices.is_empty() {
234        0.0
235    } else {
236        result.vertices_transformed as f32 / (indices.len() / 3) as f32
237    };
238    result.atvr = if unique == 0 {
239        0.0
240    } else {
241        result.vertices_transformed as f32 / unique as f32
242    };
243    Ok(result)
244}
245
246// With <=64-byte vertices and the proven fuel/u32 bounds, an index
247// touches one or two lines. Avoid a general range loop for that common case.
248fn fetch_small(
249    indices: &[u32],
250    visited: &mut [u8],
251    vertex_size: usize,
252    cache: &mut [usize; 2048],
253    work: &mut crate::workspace::Work,
254) -> Result<u32, Error> {
255    let mut bytes_fetched = 0;
256    let mut extra_lines = 0;
257    for &index in indices {
258        visited[index as usize] = 1;
259        let start = index as usize * vertex_size;
260        let tag = start / 64;
261        let first = &mut cache[tag % 2048];
262        bytes_fetched += u32::from(*first != tag + 1) * 64;
263        *first = tag + 1;
264        if (start & 63) + vertex_size > 64 {
265            let second = &mut cache[(tag + 1) % 2048];
266            bytes_fetched += u32::from(*second != tag + 2) * 64;
267            *second = tag + 2;
268            extra_lines += 1;
269        }
270    }
271    // The caller proved 6*len visits fit, so this <=3*len count cannot overflow.
272    work.add(indices.len() * 2 + extra_lines)?;
273    Ok(bytes_fetched)
274}
275
276fn fetch_run<const CHARGE: bool, const CHECK: bool>(
277    indices: &[u32],
278    visited: &mut [u8],
279    vertex_size: usize,
280    cache: &mut [usize; 2048],
281    work: &mut crate::workspace::Work,
282) -> Result<u32, Error> {
283    let mut bytes_fetched = 0u32;
284    let mut visits = if CHECK { 0 } else { indices.len() };
285    for &index in indices {
286        if CHARGE {
287            work.add(1)?;
288        }
289        if CHECK {
290            visits += 1;
291        }
292        visited[index as usize] = 1;
293        let start = index as usize * vertex_size;
294        let end = start + vertex_size;
295        // The validated vertex byte extent is at most isize::MAX, so
296        // adding 63 cannot overflow usize on either supported word size.
297        let start_tag = start / 64;
298        #[allow(clippy::manual_div_ceil)] // Proven non-overflowing add has cheaper codegen.
299        let end_tag = (end + 63) / 64;
300        if !CHECK {
301            visits += end_tag - start_tag;
302        }
303        for tag in start_tag..end_tag {
304            if CHARGE {
305                work.add(1)?;
306            }
307            if CHECK {
308                visits += 1;
309            }
310            let line = &mut cache[tag % 2048];
311            if CHECK {
312                if *line != tag + 1 {
313                    bytes_fetched = match bytes_fetched.checked_add(64) {
314                        Some(bytes) => bytes,
315                        None => {
316                            if !CHARGE {
317                                work.add(visits)?;
318                            }
319                            return Err(Error::SizeOverflow);
320                        }
321                    };
322                }
323            } else {
324                bytes_fetched += u32::from(*line != tag + 1) * 64;
325            }
326            *line = tag + 1;
327        }
328    }
329    if !CHARGE {
330        work.add(visits)?;
331    }
332    Ok(bytes_fetched)
333}
334
335/// Analyze index order with upstream's direct-mapped 128 KiB fetch-cache model.
336///
337/// # Errors
338/// `IndexOutOfBounds` for invalid vertex references;
339/// `InvalidParameter` for unsupported analyzer settings; `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
340#[inline]
341pub fn analyze_vertex_fetch_generic<I: crate::Index>(
342    indices: &[I],
343    vertex_count: usize,
344    vertex_size: usize,
345    workspace: &mut Workspace,
346) -> Result<VertexFetchStatistics, Error> {
347    I::with_input(indices, workspace, |indices, workspace| {
348        analyze_vertex_fetch_u32(indices, vertex_count, vertex_size, workspace)
349    })
350}
351
352fn analyze_vertex_fetch_u32(
353    indices: &[u32],
354    vertex_count: usize,
355    vertex_size: usize,
356    workspace: &mut Workspace,
357) -> Result<VertexFetchStatistics, Error> {
358    let mut work = workspace.begin();
359    let result = (|| {
360        if !(1..=256).contains(&vertex_size) {
361            return Err(Error::InvalidParameter);
362        }
363        if vertex_count > u32::MAX as usize {
364            return Err(Error::SizeOverflow);
365        }
366        checked_bytes(vertex_count, vertex_size)?;
367        work.indices(indices, vertex_count)?;
368        let retained = workspace.flags.len().min(vertex_count);
369        workspace.prepare([0, 0, vertex_count, 0], 0)?;
370        let visited = &mut workspace.flags[..vertex_count];
371        visited[..retained].fill(0);
372        let mut cache = [0usize; 2048];
373        let mut result = VertexFetchStatistics::default();
374        // An index visits at most five cache lines. With sufficient fuel,
375        // count the visits locally and charge once; the fallback keeps the
376        // exact exhaustion point and partial usage for low limits.
377        let bulk_work = match indices.len().checked_mul(6) {
378            Some(max_visits) => work.covers(max_visits)?,
379            None => false,
380        };
381        // A vertex spans at most five 64-byte lines. This upper bound proves
382        // u32 accumulation safe without weakening the overflow error contract.
383        let bounded_bytes = indices.len() <= u32::MAX as usize / (5 * 64);
384        result.bytes_fetched = if bulk_work && bounded_bytes && vertex_size <= 64 {
385            fetch_small(indices, visited, vertex_size, &mut cache, &mut work)?
386        } else {
387            match (bulk_work, bounded_bytes) {
388                (true, true) => {
389                    fetch_run::<false, false>(indices, visited, vertex_size, &mut cache, &mut work)?
390                }
391                (true, false) => {
392                    fetch_run::<false, true>(indices, visited, vertex_size, &mut cache, &mut work)?
393                }
394                (false, true) => {
395                    fetch_run::<true, false>(indices, visited, vertex_size, &mut cache, &mut work)?
396                }
397                (false, false) => {
398                    fetch_run::<true, true>(indices, visited, vertex_size, &mut cache, &mut work)?
399                }
400            }
401        };
402        // Every visited flag was initialized to zero and is written only as one.
403        let unique: usize = visited.iter().map(|&value| usize::from(value)).sum();
404        work.add(vertex_count)?;
405        result.overfetch = if unique == 0 {
406            0.0
407        } else {
408            result.bytes_fetched as f32 / (unique * vertex_size) as f32
409        };
410        Ok(result)
411    })();
412    workspace.finish(&work);
413    result
414}
415
416/// The source-compatible u32 entry point; see [`analyze_vertex_cache_generic`] for selectable index widths.
417#[inline]
418pub fn analyze_vertex_cache(
419    indices: &[u32],
420    vertex_count: usize,
421    cache_size: u32,
422    warp_size: u32,
423    primgroup_size: u32,
424    workspace: &mut Workspace,
425) -> Result<VertexCacheStatistics, Error> {
426    analyze_vertex_cache_generic::<u32>(
427        indices,
428        vertex_count,
429        cache_size,
430        warp_size,
431        primgroup_size,
432        workspace,
433    )
434}
435
436/// The source-compatible u32 entry point; see [`analyze_vertex_fetch_generic`] for selectable index widths.
437#[inline]
438pub fn analyze_vertex_fetch(
439    indices: &[u32],
440    vertex_count: usize,
441    vertex_size: usize,
442    workspace: &mut Workspace,
443) -> Result<VertexFetchStatistics, Error> {
444    analyze_vertex_fetch_generic::<u32>(indices, vertex_count, vertex_size, workspace)
445}