Skip to main content

linkcell/
bins.rs

1//! Cell-major bins and the certified index-box frontier.
2//!
3//! Occupants of one bin sit in a contiguous slice (HOOMD / vesin), so the
4//! stencil walk is a sequential read. The visited set is a rectangular
5//! box in bin index. Every unvisited image lies beyond one of six lattice
6//! planes. The perpendicular distance to the nearest of those planes is a
7//! lower bound on the unvisited distance, and it is safe to stop once the
8//! k-th neighbour is inside it.
9
10use std::sync::Mutex;
11
12use crate::cell::Cell;
13use crate::Error;
14
15/// Below this many active points the mesh stays serial. The cubic hot
16/// path is 4096 points, and a parallel histogram there costs more than
17/// the fold. The fused team query starts at the same count.
18#[cfg(all(feature = "parallel", linkcell_openmp))]
19pub(crate) const PARALLEL_MESH: usize = 8_192;
20
21const MAX_CELLS: i64 = 16_777_216;
22/// Shrink a cutoff slab so a rounded-up plane cannot drop a pair.
23const CERT_REL: f64 = 1.0e-8;
24const CERT_ABS: f64 = 1.0e-12;
25
26#[derive(Default)]
27pub(crate) struct Recycled {
28    pub(crate) frac: Vec<[f64; 3]>,
29    pub(crate) folded: Vec<[f64; 3]>,
30    pub(crate) slot_frac: Vec<[f64; 3]>,
31    pub(crate) slot_folded: Vec<[f64; 3]>,
32    pub(crate) key: Vec<u32>,
33    pub(crate) offsets: Vec<usize>,
34    pub(crate) occupants: Vec<usize>,
35    pub(crate) counts: Vec<usize>,
36    pub(crate) next_slot: Vec<usize>,
37    pub(crate) hist: Vec<std::sync::atomic::AtomicUsize>,
38}
39
40/// One set of buffers for the process. A search inside a thread pool
41/// builds its mesh on whichever worker took the job, so a pool per
42/// thread missed on most calls and the next mesh paged in new buffers.
43static MESH_POOL: Mutex<Option<Recycled>> = Mutex::new(None);
44
45pub(crate) fn take_recycled() -> Recycled {
46    MESH_POOL
47        .lock()
48        .unwrap_or_else(|err| err.into_inner())
49        .take()
50        .unwrap_or_default()
51}
52
53fn recycle(buf: Recycled) {
54    const MAX_KEEP: usize = 1 << 20;
55    if buf.frac.capacity() > MAX_KEEP || buf.offsets.capacity() > MAX_KEEP {
56        return;
57    }
58    let mut guard = MESH_POOL.lock().unwrap_or_else(|err| err.into_inner());
59    if guard.is_none() {
60        *guard = Some(buf);
61    }
62}
63
64/// Fractional bins with cell-major occupants.
65pub(crate) struct Mesh {
66    pub nx: i32,
67    pub ny: i32,
68    pub nz: i32,
69    pub widths: [f64; 3],
70    pub frac: Vec<[f64; 3]>,
71    pub folded: Vec<[f64; 3]>,
72    /// `frac` and `folded` of each slot's occupant, in slot order: a walk
73    /// in bin order reads them in runs whatever order the atoms came in.
74    pub(crate) slot_frac: Vec<[f64; 3]>,
75    pub(crate) slot_folded: Vec<[f64; 3]>,
76    /// Flat bin of each point, in point order.
77    pub(crate) key: Vec<u32>,
78    pub(crate) offsets: Vec<usize>,
79    pub(crate) occupants: Vec<usize>,
80    pub(crate) counts: Vec<usize>,
81    pub(crate) next_slot: Vec<usize>,
82    pub(crate) hist: Vec<std::sync::atomic::AtomicUsize>,
83}
84
85impl Drop for Mesh {
86    fn drop(&mut self) {
87        recycle(Recycled {
88            frac: std::mem::take(&mut self.frac),
89            folded: std::mem::take(&mut self.folded),
90            slot_frac: std::mem::take(&mut self.slot_frac),
91            slot_folded: std::mem::take(&mut self.slot_folded),
92            key: std::mem::take(&mut self.key),
93            offsets: std::mem::take(&mut self.offsets),
94            occupants: std::mem::take(&mut self.occupants),
95            counts: std::mem::take(&mut self.counts),
96            next_slot: std::mem::take(&mut self.next_slot),
97            hist: std::mem::take(&mut self.hist),
98        });
99    }
100}
101
102impl Mesh {
103    pub(crate) fn build(
104        xyz: &[[f64; 3]],
105        simbox: &Cell,
106        active: Option<&[usize]>,
107        edge: f64,
108    ) -> Result<Self, Error> {
109        let ids = match active {
110            Some(list) => Active::List(list),
111            None => Active::All(xyz.len()),
112        };
113        Self::assemble(xyz, simbox, edge, ids)
114    }
115
116    fn assemble(
117        xyz: &[[f64; 3]],
118        simbox: &Cell,
119        edge: f64,
120        ids: Active<'_>,
121    ) -> Result<Self, Error> {
122        let widths = simbox.widths();
123        let nx = bins_1d(widths[0], edge)?;
124        let ny = bins_1d(widths[1], edge)?;
125        let nz = bins_1d(widths[2], edge)?;
126        let ncell = (i64::from(nx))
127            .checked_mul(i64::from(ny))
128            .and_then(|v| v.checked_mul(i64::from(nz)))
129            .filter(|&v| v > 0 && v <= MAX_CELLS)
130            .ok_or(Error::TooManyCells)? as usize;
131
132        let n = xyz.len();
133        let n_active = ids.len();
134        let mut buf = take_recycled();
135        if buf.frac.len() != n {
136            buf.frac.resize(n, [0.0; 3]);
137            buf.folded.resize(n, [0.0; 3]);
138            buf.key.resize(n, 0);
139        }
140        if buf.offsets.len() != ncell + 1 {
141            buf.offsets.clear();
142            buf.offsets.resize(ncell + 1, 0);
143        }
144        buf.occupants.resize(n_active, 0);
145        buf.slot_frac.resize(n_active, [0.0; 3]);
146        buf.slot_folded.resize(n_active, [0.0; 3]);
147        buf.counts.clear();
148        buf.counts.resize(ncell, 0);
149        buf.next_slot.resize(ncell, 0);
150
151        let _pop = crate::pop::JobTimer::new();
152        let mut start = 0usize;
153        if let Active::All(len) = ids {
154            let path = crate::simd::select();
155            let counts = &mut buf.counts;
156            start = fold_mesh_at(
157                path,
158                simbox,
159                xyz,
160                [nx, ny, nz],
161                0,
162                len,
163                (&mut buf.frac, &mut buf.folded, &mut buf.key),
164                |c| counts[c] += 1,
165            );
166        }
167        for slot in start..n_active {
168            let i = ids.get(slot);
169            let s = simbox.fractional(xyz[i]);
170            let b = [
171                bin_coord(s[0], nx),
172                bin_coord(s[1], ny),
173                bin_coord(s[2], nz),
174            ];
175            let c = flat_cell(b, [nx, ny, nz]);
176            buf.frac[i] = s;
177            buf.folded[i] = simbox.cartesian(s);
178            buf.key[i] = c as u32;
179            buf.counts[c] += 1;
180        }
181        buf.offsets[0] = 0;
182        for c in 0..ncell {
183            buf.offsets[c + 1] = buf.offsets[c] + buf.counts[c];
184        }
185        buf.next_slot.copy_from_slice(&buf.offsets[..ncell]);
186        for slot in 0..n_active {
187            let i = ids.get(slot);
188            let c = buf.key[i] as usize;
189            let dest = buf.next_slot[c];
190            buf.occupants[dest] = i;
191            buf.slot_frac[dest] = buf.frac[i];
192            buf.slot_folded[dest] = buf.folded[i];
193            buf.next_slot[c] = dest + 1;
194        }
195
196        Ok(Self {
197            nx,
198            ny,
199            nz,
200            widths,
201            frac: buf.frac,
202            folded: buf.folded,
203            slot_frac: buf.slot_frac,
204            slot_folded: buf.slot_folded,
205            key: buf.key,
206            offsets: buf.offsets,
207            occupants: buf.occupants,
208            counts: buf.counts,
209            next_slot: buf.next_slot,
210            hist: buf.hist,
211        })
212    }
213
214    /// Bin index plus the integer image `(na, nb, nc)` of an unfolded cell.
215    #[inline(always)]
216    pub(crate) fn locate(&self, ix: i32, iy: i32, iz: i32) -> (usize, i32, i32, i32) {
217        let (cx, na) = split_axis(ix, self.nx);
218        let (cy, nb) = split_axis(iy, self.ny);
219        let (cz, nc) = split_axis(iz, self.nz);
220        let cell = ((cz * self.ny + cy) * self.nx + cx) as usize;
221        (cell, na, nb, nc)
222    }
223
224    /// Half-box of bins. The search cap is at least this, and at least
225    /// the space diagonal in cell heights.
226    pub(crate) fn image_reach(&self) -> i32 {
227        self.nx.max(self.ny).max(self.nz) / 2 + 2
228    }
229}
230
231/// Points per [`MeshStages::fold`] chunk.
232const FOLD_CHUNK: usize = 4096;
233
234/// A pointer the stages of one region share. Each stage writes indices
235/// no other chunk of that stage writes.
236#[derive(Clone, Copy)]
237struct Raw<T>(*mut T);
238
239unsafe impl<T> Send for Raw<T> {}
240unsafe impl<T> Sync for Raw<T> {}
241
242/// [`Mesh::build`] as stages of one [`crate::team`] region: [`fold`]
243/// per chunk of points, [`prefix`] once, [`scatter`] per run of bins.
244/// The bins, slots, and occupant order are the serial build's: each run
245/// of bins is placed by one worker walking the points in order.
246///
247/// [`fold`]: MeshStages::fold
248/// [`prefix`]: MeshStages::prefix
249/// [`scatter`]: MeshStages::scatter
250pub(crate) struct MeshStages<'a> {
251    mesh: Mesh,
252    xyz: &'a [[f64; 3]],
253    simbox: &'a Cell,
254    ids: Active<'a>,
255    path: crate::simd::Path,
256    parts: usize,
257    frac: Raw<[f64; 3]>,
258    folded: Raw<[f64; 3]>,
259    key: Raw<u32>,
260    counts: Raw<usize>,
261    offsets: Raw<usize>,
262    next: Raw<usize>,
263    occupants: Raw<usize>,
264    slot_frac: Raw<[f64; 3]>,
265    slot_folded: Raw<[f64; 3]>,
266    cuts: Raw<usize>,
267    _cuts: Vec<usize>,
268}
269
270impl<'a> MeshStages<'a> {
271    /// Size the buffers. `parts` is the number of scatter runs.
272    pub(crate) fn new(
273        xyz: &'a [[f64; 3]],
274        simbox: &'a Cell,
275        active: Option<&'a [usize]>,
276        edge: f64,
277        parts: usize,
278    ) -> Result<Self, Error> {
279        let ids = match active {
280            Some(list) => Active::List(list),
281            None => Active::All(xyz.len()),
282        };
283        let widths = simbox.widths();
284        let nx = bins_1d(widths[0], edge)?;
285        let ny = bins_1d(widths[1], edge)?;
286        let nz = bins_1d(widths[2], edge)?;
287        let ncell = (i64::from(nx))
288            .checked_mul(i64::from(ny))
289            .and_then(|v| v.checked_mul(i64::from(nz)))
290            .filter(|&v| v > 0 && v <= MAX_CELLS)
291            .ok_or(Error::TooManyCells)? as usize;
292        let n = xyz.len();
293        let n_active = ids.len();
294        let mut buf = take_recycled();
295        if buf.frac.len() != n {
296            buf.frac.resize(n, [0.0; 3]);
297            buf.folded.resize(n, [0.0; 3]);
298            buf.key.resize(n, 0);
299        }
300        if buf.offsets.len() != ncell + 1 {
301            buf.offsets.clear();
302            buf.offsets.resize(ncell + 1, 0);
303        }
304        buf.occupants.resize(n_active, 0);
305        buf.slot_frac.resize(n_active, [0.0; 3]);
306        buf.slot_folded.resize(n_active, [0.0; 3]);
307        buf.counts.clear();
308        buf.counts.resize(ncell, 0);
309        buf.next_slot.resize(ncell, 0);
310        let mut mesh = Mesh {
311            nx,
312            ny,
313            nz,
314            widths,
315            frac: buf.frac,
316            folded: buf.folded,
317            slot_frac: buf.slot_frac,
318            slot_folded: buf.slot_folded,
319            key: buf.key,
320            offsets: buf.offsets,
321            occupants: buf.occupants,
322            counts: buf.counts,
323            next_slot: buf.next_slot,
324            hist: buf.hist,
325        };
326        let parts = parts.clamp(1, 32).min(ncell);
327        let mut cuts = vec![0usize; parts + 1];
328        Ok(MeshStages {
329            xyz,
330            simbox,
331            ids,
332            path: crate::simd::select(),
333            parts,
334            frac: Raw(mesh.frac.as_mut_ptr()),
335            folded: Raw(mesh.folded.as_mut_ptr()),
336            key: Raw(mesh.key.as_mut_ptr()),
337            counts: Raw(mesh.counts.as_mut_ptr()),
338            offsets: Raw(mesh.offsets.as_mut_ptr()),
339            next: Raw(mesh.next_slot.as_mut_ptr()),
340            occupants: Raw(mesh.occupants.as_mut_ptr()),
341            slot_frac: Raw(mesh.slot_frac.as_mut_ptr()),
342            slot_folded: Raw(mesh.slot_folded.as_mut_ptr()),
343            cuts: Raw(cuts.as_mut_ptr()),
344            _cuts: cuts,
345            mesh,
346        })
347    }
348
349    /// Bins per axis.
350    pub(crate) fn nbin(&self) -> [i32; 3] {
351        [self.mesh.nx, self.mesh.ny, self.mesh.nz]
352    }
353
354    pub(crate) fn widths(&self) -> [f64; 3] {
355        self.mesh.widths
356    }
357
358    pub(crate) fn ncell(&self) -> usize {
359        self.mesh.counts.len()
360    }
361
362    pub(crate) fn n_active(&self) -> usize {
363        self.ids.len()
364    }
365
366    pub(crate) fn fold_chunks(&self) -> usize {
367        (self.ids.len() + FOLD_CHUNK - 1) / FOLD_CHUNK
368    }
369
370    pub(crate) fn scatter_chunks(&self) -> usize {
371        self.parts
372    }
373
374    /// Fractional, folded, and bin of the points of chunk `c`, each bin
375    /// counted with an atomic add.
376    pub(crate) fn fold(&self, c: usize) {
377        let n_active = self.ids.len();
378        let lo = c * FOLD_CHUNK;
379        let hi = (lo + FOLD_CHUNK).min(n_active);
380        if lo >= hi {
381            return;
382        }
383        let nbin = self.nbin();
384        let [nx, ny, nz] = nbin;
385        // SAFETY: `counts` has `ncell` entries and `AtomicUsize` has the
386        // layout of `usize`; every write in this stage is atomic.
387        let counts = unsafe {
388            std::slice::from_raw_parts(
389                self.counts.0 as *const std::sync::atomic::AtomicUsize,
390                self.ncell(),
391            )
392        };
393        let add = |b: usize| {
394            counts[b].fetch_add(1, std::sync::atomic::Ordering::Relaxed);
395        };
396        let simbox = self.simbox;
397        match self.ids {
398            Active::All(_) => {
399                let len = hi - lo;
400                let p = &self.xyz[lo..hi];
401                // SAFETY: chunk `c` owns points `lo..hi` of these arrays.
402                let (f, fold, b) = unsafe {
403                    (
404                        std::slice::from_raw_parts_mut(self.frac.0.add(lo), len),
405                        std::slice::from_raw_parts_mut(self.folded.0.add(lo), len),
406                        std::slice::from_raw_parts_mut(self.key.0.add(lo), len),
407                    )
408                };
409                let start = fold_mesh_at(
410                    self.path,
411                    simbox,
412                    p,
413                    nbin,
414                    0,
415                    len,
416                    (&mut *f, &mut *fold, &mut *b),
417                    add,
418                );
419                for t in start..len {
420                    let s = simbox.fractional(p[t]);
421                    let cell = flat_cell(
422                        [
423                            bin_coord(s[0], nx),
424                            bin_coord(s[1], ny),
425                            bin_coord(s[2], nz),
426                        ],
427                        nbin,
428                    );
429                    f[t] = s;
430                    fold[t] = simbox.cartesian(s);
431                    b[t] = cell as u32;
432                    add(cell);
433                }
434            }
435            Active::List(list) => {
436                for &i in &list[lo..hi] {
437                    let s = simbox.fractional(self.xyz[i]);
438                    let cell = flat_cell(
439                        [
440                            bin_coord(s[0], nx),
441                            bin_coord(s[1], ny),
442                            bin_coord(s[2], nz),
443                        ],
444                        nbin,
445                    );
446                    // SAFETY: the list holds each point once.
447                    unsafe {
448                        self.frac.0.add(i).write(s);
449                        self.folded.0.add(i).write(simbox.cartesian(s));
450                        self.key.0.add(i).write(cell as u32);
451                    }
452                    add(cell);
453                }
454            }
455        }
456    }
457
458    /// Bin offsets, and the runs of bins each [`MeshStages::scatter`]
459    /// chunk owns: about `n / parts` points each.
460    pub(crate) fn prefix(&self) {
461        let ncell = self.ncell();
462        let n_active = self.ids.len();
463        // SAFETY: one chunk; the fold stage has finished.
464        let (counts, offsets, cuts) = unsafe {
465            (
466                std::slice::from_raw_parts(self.counts.0, ncell),
467                std::slice::from_raw_parts_mut(self.offsets.0, ncell + 1),
468                std::slice::from_raw_parts_mut(self.cuts.0, self.parts + 1),
469            )
470        };
471        let mut acc = 0usize;
472        for c in 0..ncell {
473            offsets[c] = acc;
474            acc += counts[c];
475        }
476        offsets[ncell] = acc;
477        cuts[0] = 0;
478        for t in 1..self.parts {
479            let want = n_active * t / self.parts;
480            let c = offsets[..ncell].partition_point(|&o| o < want);
481            cuts[t] = c.max(cuts[t - 1]);
482        }
483        cuts[self.parts] = ncell;
484    }
485
486    /// Place the points of run `t` of bins, in point order.
487    pub(crate) fn scatter(&self, t: usize) {
488        let ncell = self.ncell();
489        // SAFETY: the prefix stage has finished; run `t` owns bins
490        // `lo..hi`, the next free slot of each, and their slots.
491        let (lo, hi, offsets, key, frac, folded) = unsafe {
492            let cuts = std::slice::from_raw_parts(self.cuts.0, self.parts + 1);
493            let n = self.xyz.len();
494            (
495                cuts[t],
496                cuts[t + 1],
497                std::slice::from_raw_parts(self.offsets.0, ncell + 1),
498                std::slice::from_raw_parts(self.key.0, n),
499                std::slice::from_raw_parts(self.frac.0, n),
500                std::slice::from_raw_parts(self.folded.0, n),
501            )
502        };
503        if lo >= hi {
504            return;
505        }
506        let own = unsafe { std::slice::from_raw_parts_mut(self.next.0.add(lo), hi - lo) };
507        own.copy_from_slice(&offsets[lo..hi]);
508        let mut place = |i: usize| {
509            let c = key[i] as usize;
510            if c >= lo && c < hi {
511                let dest = own[c - lo];
512                own[c - lo] = dest + 1;
513                // SAFETY: slot `dest` lies in this run's bins.
514                unsafe {
515                    self.occupants.0.add(dest).write(i);
516                    self.slot_frac.0.add(dest).write(frac[i]);
517                    self.slot_folded.0.add(dest).write(folded[i]);
518                }
519            }
520        };
521        match self.ids {
522            Active::All(n) => (0..n).for_each(&mut place),
523            Active::List(list) => list.iter().for_each(|&i| place(i)),
524        }
525    }
526
527    /// The mesh, for reads after the scatter stage.
528    pub(crate) fn mesh(&self) -> &Mesh {
529        &self.mesh
530    }
531}
532
533pub(crate) fn target_edge(simbox: &Cell, hint: Option<f64>, fallback: f64) -> f64 {
534    let mut edge = hint.unwrap_or(fallback);
535    if !edge.is_finite() || edge <= 0.0 {
536        edge = fallback;
537    }
538    let w = simbox.widths();
539    edge.min(w[0]).min(w[1]).min(w[2])
540}
541
542/// Index box grown from `prev` to `reach`. `prev` of `-1` visits the
543/// whole box, including the home cell. Later calls visit only the new
544/// faces, so a short axis can grow while a long axis stays put.
545pub(crate) fn for_new_layer(prev: [i32; 3], reach: [i32; 3], mut visit: impl FnMut(i32, i32, i32)) {
546    let [px, py, pz] = prev;
547    let [rx, ry, rz] = reach;
548    for dz in -rz..=rz {
549        for dy in -ry..=ry {
550            for dx in -rx..=rx {
551                if dx.abs() <= px && dy.abs() <= py && dz.abs() <= pz {
552                    continue;
553                }
554                visit(dx, dy, dz);
555            }
556        }
557    }
558}
559
560/// Perpendicular gap from fractional coordinate `s` to the nearest
561/// plane just outside an index interval of radius `reach`.
562///
563/// Bins are half-open, so an unvisited point lies past this plane. A
564/// neighbour sitting on the plane is still inside the visited interval.
565pub(crate) fn axis_gap(s: f64, bin: i32, reach: i32, n: i32, w: f64) -> f64 {
566    let nf = f64::from(n);
567    let plus = (f64::from(bin + reach + 1) / nf - s) * w;
568    let minus = (s - f64::from(bin - reach) / nf) * w;
569    plus.min(minus)
570}
571
572/// Squared lower bound on the distance from `s` to an image bin.
573pub(crate) fn slab_dist2(s: [f64; 3], unfolded: [i32; 3], n: [i32; 3], w: [f64; 3]) -> f64 {
574    let mut gap = 0.0_f64;
575    for a in 0..3 {
576        let nf = f64::from(n[a]);
577        let lo = f64::from(unfolded[a]) / nf;
578        let hi = f64::from(unfolded[a] + 1) / nf;
579        let axis = if s[a] < lo {
580            (lo - s[a]) * w[a]
581        } else if s[a] > hi {
582            (s[a] - hi) * w[a]
583        } else {
584            0.0
585        };
586        gap = gap.max(axis);
587    }
588    let d = certify(gap);
589    d * d
590}
591
592/// Active ids. `All` is `0..n` without a side buffer. `List` is a mask
593/// filter. Each index appears once; the parallel fill writes `frac[i]`
594/// from one slot only.
595#[derive(Clone, Copy)]
596enum Active<'a> {
597    All(usize),
598    List(&'a [usize]),
599}
600
601impl Active<'_> {
602    fn len(self) -> usize {
603        match self {
604            Active::All(n) => n,
605            Active::List(list) => list.len(),
606        }
607    }
608
609    fn get(self, slot: usize) -> usize {
610        match self {
611            Active::All(_) => slot,
612            Active::List(list) => list[slot],
613        }
614    }
615}
616
617fn bins_1d(width: f64, edge: f64) -> Result<i32, Error> {
618    let n = (width / edge).floor().max(1.0);
619    if !n.is_finite() || n > 1_000_000.0 {
620        return Err(Error::TooManyCells);
621    }
622    Ok(n as i32)
623}
624
625/// Box constants of the wide fold. AVX-512 uses eight lanes, AVX2 four,
626/// NEON two. The values are the scalar cell's.
627#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
628pub(crate) struct Fold8 {
629    origin: [f64; 3],
630    widths: [f64; 3],
631    h: [[f64; 3]; 3],
632    hinv: [[f64; 3]; 3],
633    ortho: bool,
634    n: [i32; 3],
635}
636
637#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
638impl Fold8 {
639    pub(crate) fn new(simbox: &Cell, n: [i32; 3]) -> Self {
640        Fold8 {
641            origin: simbox.origin(),
642            widths: simbox.widths(),
643            h: simbox.h(),
644            hinv: simbox.hinv(),
645            ortho: simbox.is_ortho(),
646            n,
647        }
648    }
649}
650
651/// Fractional coordinates, folded positions, and bins of the eight
652/// packed `x y z` rows at `base`, with [`Cell::fractional`],
653/// [`Cell::cartesian`], and the bin truncation of [`Mesh::build`] done
654/// lane by lane in the same order (a division, or the `Hinv` product,
655/// then `wrap01`; `H` then the origin), so every value is the same bits.
656///
657/// # Safety
658/// AVX-512F is available and `base` is readable for 24 doubles.
659#[allow(clippy::incompatible_msrv, clippy::type_complexity)]
660#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
661#[target_feature(enable = "avx512f")]
662#[inline]
663pub(crate) unsafe fn fold8(
664    f: &Fold8,
665    base: *const f64,
666) -> ([[f64; 8]; 3], [[f64; 8]; 3], [[i32; 8]; 3]) {
667    use std::arch::x86_64::{_mm256_storeu_si256, _mm512_storeu_pd};
668    let (s, p, b) = fold8_regs(f, base);
669    let mut so = [[0.0f64; 8]; 3];
670    let mut po = [[0.0f64; 8]; 3];
671    let mut bo = [[0i32; 8]; 3];
672    for ax in 0..3 {
673        _mm512_storeu_pd(so[ax].as_mut_ptr(), s[ax]);
674        _mm512_storeu_pd(po[ax].as_mut_ptr(), p[ax]);
675        _mm256_storeu_si256(bo[ax].as_mut_ptr() as *mut _, b[ax]);
676    }
677    (so, po, bo)
678}
679
680/// [`fold8`] in registers.
681///
682/// # Safety
683/// AVX-512F is available and `base` is readable for 24 doubles.
684#[allow(clippy::incompatible_msrv, clippy::type_complexity)]
685#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
686#[target_feature(enable = "avx512f")]
687#[inline]
688pub(crate) unsafe fn fold8_regs(
689    f: &Fold8,
690    base: *const f64,
691) -> (
692    [std::arch::x86_64::__m512d; 3],
693    [std::arch::x86_64::__m512d; 3],
694    [std::arch::x86_64::__m256i; 3],
695) {
696    use std::arch::x86_64::{
697        __m512d, _mm256_max_epi32, _mm256_min_epi32, _mm256_set1_epi32, _mm256_setzero_si256,
698        _mm512_add_pd, _mm512_cmp_pd_mask, _mm512_cvttpd_epi32, _mm512_div_pd, _mm512_loadu_pd,
699        _mm512_mask_blend_pd, _mm512_mask_permutex2var_pd, _mm512_mul_pd, _mm512_permutex2var_pd,
700        _mm512_roundscale_pd, _mm512_set1_pd, _mm512_setr_epi64, _mm512_setzero_pd, _mm512_sub_pd,
701        _CMP_EQ_OQ, _CMP_GE_OQ, _CMP_GT_OQ,
702    };
703    let bc = |v: f64| _mm512_set1_pd(v);
704    let one = bc(1.0);
705    let (o, w, h, hinv, n) = (f.origin, f.widths, f.h, f.hinv, f.n);
706    // `wrap01` follows minimage `floor_fast` on x86_64: trunc toward
707    // zero, `-0` becomes `+0`, then one less when that trunc is above
708    // the input. A result that rounds to one is zero. The previous
709    // round-toward-minus-infinity floor mapped an input of `-0` to a
710    // fraction of `+0`. Scalar `floor_fast` keeps that input as `-0`.
711    let wrap01 = |s: __m512d| {
712        let zero = _mm512_setzero_pd();
713        let trunc = _mm512_roundscale_pd::<0x0b>(s);
714        let trunc =
715            _mm512_mask_blend_pd(_mm512_cmp_pd_mask::<_CMP_EQ_OQ>(trunc, zero), trunc, zero);
716        let floor = _mm512_mask_blend_pd(
717            _mm512_cmp_pd_mask::<_CMP_GT_OQ>(trunc, s),
718            trunc,
719            _mm512_sub_pd(trunc, one),
720        );
721        let t = _mm512_sub_pd(s, floor);
722        _mm512_mask_blend_pd(_mm512_cmp_pd_mask::<_CMP_GE_OQ>(t, one), t, zero)
723    };
724    let a = _mm512_loadu_pd(base);
725    let b = _mm512_loadu_pd(base.add(8));
726    let c = _mm512_loadu_pd(base.add(16));
727    let x = _mm512_mask_permutex2var_pd(
728        _mm512_permutex2var_pd(a, _mm512_setr_epi64(0, 3, 6, 9, 12, 15, 0, 0), b),
729        0xc0,
730        _mm512_setr_epi64(0, 0, 0, 0, 0, 0, 10, 13),
731        c,
732    );
733    let y = _mm512_mask_permutex2var_pd(
734        _mm512_permutex2var_pd(a, _mm512_setr_epi64(1, 4, 7, 10, 13, 0, 0, 0), b),
735        0xe0,
736        _mm512_setr_epi64(0, 0, 0, 0, 0, 8, 11, 14),
737        c,
738    );
739    let z = _mm512_mask_permutex2var_pd(
740        _mm512_permutex2var_pd(a, _mm512_setr_epi64(2, 5, 8, 11, 14, 0, 0, 0), b),
741        0xe0,
742        _mm512_setr_epi64(0, 0, 0, 0, 0, 9, 12, 15),
743        c,
744    );
745    let d = [
746        _mm512_sub_pd(x, bc(o[0])),
747        _mm512_sub_pd(y, bc(o[1])),
748        _mm512_sub_pd(z, bc(o[2])),
749    ];
750    let s = if f.ortho {
751        [
752            wrap01(_mm512_div_pd(d[0], bc(w[0]))),
753            wrap01(_mm512_div_pd(d[1], bc(w[1]))),
754            wrap01(_mm512_div_pd(d[2], bc(w[2]))),
755        ]
756    } else {
757        let row = |r: usize| {
758            _mm512_add_pd(
759                _mm512_add_pd(
760                    _mm512_mul_pd(bc(hinv[0][r]), d[0]),
761                    _mm512_mul_pd(bc(hinv[1][r]), d[1]),
762                ),
763                _mm512_mul_pd(bc(hinv[2][r]), d[2]),
764            )
765        };
766        [wrap01(row(0)), wrap01(row(1)), wrap01(row(2))]
767    };
768    let cart = |r: usize| {
769        _mm512_add_pd(
770            _mm512_add_pd(
771                _mm512_add_pd(
772                    _mm512_mul_pd(bc(h[0][r]), s[0]),
773                    _mm512_mul_pd(bc(h[1][r]), s[1]),
774                ),
775                _mm512_mul_pd(bc(h[2][r]), s[2]),
776            ),
777            bc(o[r]),
778        )
779    };
780    let bin = |ax: usize| {
781        let t = _mm512_cvttpd_epi32(_mm512_mul_pd(s[ax], bc(f64::from(n[ax]))));
782        _mm256_min_epi32(
783            _mm256_max_epi32(t, _mm256_setzero_si256()),
784            _mm256_set1_epi32(n[ax] - 1),
785        )
786    };
787    (s, [cart(0), cart(1), cart(2)], [bin(0), bin(1), bin(2)])
788}
789
790/// The three per-point arrays of a mesh: fractional, folded, flat bin.
791type MeshOut<'a> = (&'a mut [[f64; 3]], &'a mut [[f64; 3]], &'a mut [u32]);
792
793/// Fold one thread's chunk into the matching slices and that thread's histogram.
794///
795/// `xyz` and `out` cover only this chunk, in the same order. `hist` is the
796/// full bin count. `path` was chosen on the calling thread.
797#[cfg(all(feature = "parallel", linkcell_openmp))]
798pub(crate) fn fold_chunk(
799    simbox: &Cell,
800    xyz: &[[f64; 3]],
801    nbin: [i32; 3],
802    out: MeshOut<'_>,
803    hist: &mut [usize],
804    path: crate::simd::Path,
805) {
806    let n = xyz.len();
807    let [nx, ny, nz] = nbin;
808    let (frac, folded, key) = out;
809    let start = fold_mesh_at(path, simbox, xyz, nbin, 0, n, (frac, folded, key), |c| {
810        hist[c] += 1
811    });
812    for i in start..n {
813        let s = simbox.fractional(xyz[i]);
814        let b = [
815            bin_coord(s[0], nx),
816            bin_coord(s[1], ny),
817            bin_coord(s[2], nz),
818        ];
819        let c = flat_cell(b, nbin);
820        frac[i] = s;
821        folded[i] = simbox.cartesian(s);
822        key[i] = c as u32;
823        hist[c] += 1;
824    }
825}
826
827/// Bin counts and perpendicular widths for `edge`.
828#[cfg(all(feature = "parallel", linkcell_openmp))]
829pub(crate) fn grid(simbox: &Cell, edge: f64) -> Result<([i32; 3], [f64; 3], usize), Error> {
830    let widths = simbox.widths();
831    let nx = bins_1d(widths[0], edge)?;
832    let ny = bins_1d(widths[1], edge)?;
833    let nz = bins_1d(widths[2], edge)?;
834    let ncell = (i64::from(nx))
835        .checked_mul(i64::from(ny))
836        .and_then(|v| v.checked_mul(i64::from(nz)))
837        .filter(|&v| v > 0 && v <= MAX_CELLS)
838        .ok_or(Error::TooManyCells)? as usize;
839    Ok(([nx, ny, nz], widths, ncell))
840}
841
842/// Fold `xyz[lo..hi]` with `path`, and add each bin to `count`.
843/// Returns the first index left for the scalar fold.
844#[allow(clippy::too_many_arguments)]
845fn fold_mesh_at(
846    path: crate::simd::Path,
847    simbox: &Cell,
848    xyz: &[[f64; 3]],
849    n: [i32; 3],
850    lo: usize,
851    hi: usize,
852    out: MeshOut<'_>,
853    count: impl FnMut(usize),
854) -> usize {
855    match path {
856        #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
857        crate::simd::Path::Avx512 => fold_mesh_avx512(simbox, xyz, n, lo, hi, out, count),
858        #[cfg(target_arch = "x86_64")]
859        crate::simd::Path::Avx2 => fold_mesh_avx2(simbox, xyz, n, lo, hi, out, count),
860        #[cfg(target_arch = "aarch64")]
861        crate::simd::Path::Neon => fold_mesh_neon(simbox, xyz, n, lo, hi, out, count),
862        _ => lo,
863    }
864}
865
866/// Fold `xyz[lo..hi]` into `frac`, `folded`, and `key` at the same
867/// indices, eight at a time on AVX-512, and add each to `counts`;
868/// returns the first index left for the scalar fold.
869#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
870fn fold_mesh_avx512(
871    simbox: &Cell,
872    xyz: &[[f64; 3]],
873    n: [i32; 3],
874    lo: usize,
875    hi: usize,
876    out: MeshOut<'_>,
877    mut count: impl FnMut(usize),
878) -> usize {
879    if !std::is_x86_feature_detected!("avx512f") {
880        return lo;
881    }
882    let (frac, folded, key) = out;
883    let f = Fold8::new(simbox, n);
884    let flat = xyz.as_ptr() as *const f64;
885    let mut k = lo;
886    while k + 8 <= hi {
887        // Safety: AVX-512F was detected and rows `k..k + 8` are in `xyz`.
888        let (s, p, b) = unsafe { fold8(&f, flat.add(3 * k)) };
889        for l in 0..8 {
890            let i = k + l;
891            frac[i] = [s[0][l], s[1][l], s[2][l]];
892            folded[i] = [p[0][l], p[1][l], p[2][l]];
893            let c = flat_cell([b[0][l], b[1][l], b[2][l]], n);
894            key[i] = c as u32;
895            count(c);
896        }
897        k += 8;
898    }
899    k
900}
901
902/// Fractional coordinates, folded positions, and bins of the four
903/// packed `x y z` rows at `base`. Lane order matches [`fold8`]: a
904/// division, or the `Hinv` product, then `wrap01`; `H` then the origin.
905/// Sums are separate multiplies and adds.
906///
907/// The shuffle control is lane sources, low lane in the low bits:
908/// `x` is `(a0, a3, b2, c1)`, `y` is `(a1, b0, b3, c2)`, `z` is
909/// `(a2, b1, c0, c3)`, with `a` the first four doubles.
910///
911/// # Safety
912/// AVX2 is available and `base` is readable for 12 doubles.
913/// FMA is a selection gate in [`crate::simd`] and is not enabled here.
914#[allow(clippy::incompatible_msrv, clippy::type_complexity)]
915#[cfg(target_arch = "x86_64")]
916#[target_feature(enable = "avx,avx2")]
917#[inline]
918unsafe fn fold4(f: &Fold8, base: *const f64) -> ([[f64; 4]; 3], [[f64; 4]; 3], [[i32; 4]; 3]) {
919    use std::arch::x86_64::{
920        __m256d, _mm256_add_pd, _mm256_blend_pd, _mm256_blendv_pd, _mm256_cmp_pd,
921        _mm256_cvttpd_epi32, _mm256_div_pd, _mm256_loadu_pd, _mm256_mul_pd, _mm256_permute4x64_pd,
922        _mm256_round_pd, _mm256_set1_pd, _mm256_setzero_pd, _mm256_storeu_pd, _mm256_sub_pd,
923        _mm_max_epi32, _mm_min_epi32, _mm_set1_epi32, _mm_setzero_si128, _mm_storeu_si128,
924        _CMP_EQ_OQ, _CMP_GE_OQ, _CMP_GT_OQ,
925    };
926    let bc = |v: f64| _mm256_set1_pd(v);
927    let one = bc(1.0);
928    let (o, w, h, hinv, n) = (f.origin, f.widths, f.h, f.hinv, f.n);
929    // `wrap01` follows minimage `floor_fast` on x86_64: trunc toward
930    // zero, `-0` becomes `+0`, then one less when that trunc is above
931    // the input. A result that rounds to one is zero.
932    let wrap01 = |s: __m256d| {
933        let zero = _mm256_setzero_pd();
934        let trunc = _mm256_round_pd::<0x0b>(s);
935        let trunc = _mm256_blendv_pd(trunc, zero, _mm256_cmp_pd::<_CMP_EQ_OQ>(trunc, zero));
936        let floor = _mm256_blendv_pd(
937            trunc,
938            _mm256_sub_pd(trunc, one),
939            _mm256_cmp_pd::<_CMP_GT_OQ>(trunc, s),
940        );
941        let t = _mm256_sub_pd(s, floor);
942        _mm256_blendv_pd(t, zero, _mm256_cmp_pd::<_CMP_GE_OQ>(t, one))
943    };
944    let a = _mm256_loadu_pd(base);
945    let b = _mm256_loadu_pd(base.add(4));
946    let c = _mm256_loadu_pd(base.add(8));
947    // a = x0 y0 z0 x1, b = y1 z1 x2 y2, c = z2 x3 y3 z3.
948    let x = _mm256_blend_pd::<0b1000>(
949        _mm256_blend_pd::<0b0100>(
950            _mm256_permute4x64_pd::<0x0c>(a),
951            _mm256_permute4x64_pd::<0x20>(b),
952        ),
953        _mm256_permute4x64_pd::<0x40>(c),
954    );
955    let y = _mm256_blend_pd::<0b1000>(
956        _mm256_blend_pd::<0b0110>(
957            _mm256_permute4x64_pd::<0x01>(a),
958            _mm256_permute4x64_pd::<0x30>(b),
959        ),
960        _mm256_permute4x64_pd::<0x80>(c),
961    );
962    let z = _mm256_blend_pd::<0b1100>(
963        _mm256_blend_pd::<0b0010>(
964            _mm256_permute4x64_pd::<0x02>(a),
965            _mm256_permute4x64_pd::<0x04>(b),
966        ),
967        _mm256_permute4x64_pd::<0xc5>(c),
968    );
969    let d = [
970        _mm256_sub_pd(x, bc(o[0])),
971        _mm256_sub_pd(y, bc(o[1])),
972        _mm256_sub_pd(z, bc(o[2])),
973    ];
974    let s = if f.ortho {
975        [
976            wrap01(_mm256_div_pd(d[0], bc(w[0]))),
977            wrap01(_mm256_div_pd(d[1], bc(w[1]))),
978            wrap01(_mm256_div_pd(d[2], bc(w[2]))),
979        ]
980    } else {
981        let row = |r: usize| {
982            _mm256_add_pd(
983                _mm256_add_pd(
984                    _mm256_mul_pd(bc(hinv[0][r]), d[0]),
985                    _mm256_mul_pd(bc(hinv[1][r]), d[1]),
986                ),
987                _mm256_mul_pd(bc(hinv[2][r]), d[2]),
988            )
989        };
990        [wrap01(row(0)), wrap01(row(1)), wrap01(row(2))]
991    };
992    let cart = |r: usize| {
993        _mm256_add_pd(
994            _mm256_add_pd(
995                _mm256_add_pd(
996                    _mm256_mul_pd(bc(h[0][r]), s[0]),
997                    _mm256_mul_pd(bc(h[1][r]), s[1]),
998                ),
999                _mm256_mul_pd(bc(h[2][r]), s[2]),
1000            ),
1001            bc(o[r]),
1002        )
1003    };
1004    let bin = |ax: usize| {
1005        let t = _mm256_cvttpd_epi32(_mm256_mul_pd(s[ax], bc(f64::from(n[ax]))));
1006        _mm_min_epi32(
1007            _mm_max_epi32(t, _mm_setzero_si128()),
1008            _mm_set1_epi32(n[ax] - 1),
1009        )
1010    };
1011    let mut so = [[0.0f64; 4]; 3];
1012    let mut po = [[0.0f64; 4]; 3];
1013    let mut bo = [[0i32; 4]; 3];
1014    let p = [cart(0), cart(1), cart(2)];
1015    let bins = [bin(0), bin(1), bin(2)];
1016    for ax in 0..3 {
1017        _mm256_storeu_pd(so[ax].as_mut_ptr(), s[ax]);
1018        _mm256_storeu_pd(po[ax].as_mut_ptr(), p[ax]);
1019        _mm_storeu_si128(bo[ax].as_mut_ptr().cast(), bins[ax]);
1020    }
1021    (so, po, bo)
1022}
1023
1024/// [`fold_mesh_avx512`] four points at a time.
1025#[cfg(target_arch = "x86_64")]
1026fn fold_mesh_avx2(
1027    simbox: &Cell,
1028    xyz: &[[f64; 3]],
1029    n: [i32; 3],
1030    lo: usize,
1031    hi: usize,
1032    out: MeshOut<'_>,
1033    mut count: impl FnMut(usize),
1034) -> usize {
1035    if !std::is_x86_feature_detected!("avx2") || !std::is_x86_feature_detected!("fma") {
1036        return lo;
1037    }
1038    let (frac, folded, key) = out;
1039    let f = Fold8::new(simbox, n);
1040    let flat = xyz.as_ptr() as *const f64;
1041    let mut k = lo;
1042    while k + 4 <= hi {
1043        // Safety: AVX2 was detected and rows `k..k + 4` are in `xyz`.
1044        // FMA gates selection only. It is not enabled on `fold4`.
1045        let (s, p, b) = unsafe { fold4(&f, flat.add(3 * k)) };
1046        for l in 0..4 {
1047            let i = k + l;
1048            frac[i] = [s[0][l], s[1][l], s[2][l]];
1049            folded[i] = [p[0][l], p[1][l], p[2][l]];
1050            let c = flat_cell([b[0][l], b[1][l], b[2][l]], n);
1051            key[i] = c as u32;
1052            count(c);
1053        }
1054        k += 4;
1055    }
1056    k
1057}
1058
1059/// [`fold4`] for two points. `a` is `x0 y0`, `b` is `z0 x1`, `c` is `y1 z1`.
1060///
1061/// # Safety
1062/// NEON is available and `base` is readable for 6 doubles.
1063#[allow(clippy::type_complexity)]
1064#[cfg(target_arch = "aarch64")]
1065#[target_feature(enable = "neon")]
1066#[inline]
1067unsafe fn fold2(f: &Fold8, base: *const f64) -> ([[f64; 2]; 3], [[f64; 2]; 3], [[i32; 2]; 3]) {
1068    use std::arch::aarch64::{
1069        float64x2_t, vaddq_f64, vbslq_f64, vceqq_f64, vcgeq_f64, vcgtq_f64, vcombine_f64,
1070        vcvtq_s64_f64, vdivq_f64, vdupq_n_f64, vget_high_f64, vget_low_f64, vgetq_lane_s64,
1071        vld1q_f64, vmulq_f64, vrndq_f64, vst1q_f64, vsubq_f64,
1072    };
1073    let a = vld1q_f64(base);
1074    let b = vld1q_f64(base.add(2));
1075    let c = vld1q_f64(base.add(4));
1076    let x = vcombine_f64(vget_low_f64(a), vget_high_f64(b));
1077    let y = vcombine_f64(vget_high_f64(a), vget_low_f64(c));
1078    let z = vcombine_f64(vget_low_f64(b), vget_high_f64(c));
1079    let bc = |v: f64| vdupq_n_f64(v);
1080    let one = bc(1.0);
1081    let zero = vdupq_n_f64(0.0);
1082    let (o, w, h, hinv, nbin) = (f.origin, f.widths, f.h, f.hinv, f.n);
1083    // `wrap01` follows minimage `floor_fast`, which truncates on every
1084    // architecture: trunc toward zero (`vrndq`), `-0` becomes `+0`, then
1085    // one less when that trunc is above the input. An input of `-0`
1086    // keeps a fraction of `-0`. A result that rounds to one is zero.
1087    let wrap01 = |s: float64x2_t| {
1088        let trunc = vrndq_f64(s);
1089        let trunc = vbslq_f64(vceqq_f64(trunc, zero), zero, trunc);
1090        let floor = vbslq_f64(vcgtq_f64(trunc, s), vsubq_f64(trunc, one), trunc);
1091        let t = vsubq_f64(s, floor);
1092        vbslq_f64(vcgeq_f64(t, one), zero, t)
1093    };
1094    let d = [
1095        vsubq_f64(x, bc(o[0])),
1096        vsubq_f64(y, bc(o[1])),
1097        vsubq_f64(z, bc(o[2])),
1098    ];
1099    let s = if f.ortho {
1100        [
1101            wrap01(vdivq_f64(d[0], bc(w[0]))),
1102            wrap01(vdivq_f64(d[1], bc(w[1]))),
1103            wrap01(vdivq_f64(d[2], bc(w[2]))),
1104        ]
1105    } else {
1106        let row = |r: usize| {
1107            vaddq_f64(
1108                vaddq_f64(
1109                    vmulq_f64(bc(hinv[0][r]), d[0]),
1110                    vmulq_f64(bc(hinv[1][r]), d[1]),
1111                ),
1112                vmulq_f64(bc(hinv[2][r]), d[2]),
1113            )
1114        };
1115        [wrap01(row(0)), wrap01(row(1)), wrap01(row(2))]
1116    };
1117    let cart = |r: usize| {
1118        vaddq_f64(
1119            vaddq_f64(
1120                vaddq_f64(vmulq_f64(bc(h[0][r]), s[0]), vmulq_f64(bc(h[1][r]), s[1])),
1121                vmulq_f64(bc(h[2][r]), s[2]),
1122            ),
1123            bc(o[r]),
1124        )
1125    };
1126    let mut so = [[0.0f64; 2]; 3];
1127    let mut po = [[0.0f64; 2]; 3];
1128    let mut bo = [[0i32; 2]; 3];
1129    let p = [cart(0), cart(1), cart(2)];
1130    for ax in 0..3 {
1131        vst1q_f64(so[ax].as_mut_ptr(), s[ax]);
1132        vst1q_f64(po[ax].as_mut_ptr(), p[ax]);
1133        let raw = vcvtq_s64_f64(vmulq_f64(s[ax], bc(f64::from(nbin[ax]))));
1134        bo[ax][0] = bin_i64(vgetq_lane_s64::<0>(raw), nbin[ax]);
1135        bo[ax][1] = bin_i64(vgetq_lane_s64::<1>(raw), nbin[ax]);
1136    }
1137    (so, po, bo)
1138}
1139
1140/// `(s * n) as i32` for a truncated lane, then the [`bin_coord`] clamp.
1141#[cfg(target_arch = "aarch64")]
1142fn bin_i64(v: i64, n: i32) -> i32 {
1143    let mut c = if v > i64::from(i32::MAX) {
1144        i32::MAX
1145    } else if v < i64::from(i32::MIN) {
1146        i32::MIN
1147    } else {
1148        v as i32
1149    };
1150    if c < 0 {
1151        c = 0;
1152    }
1153    if c >= n {
1154        c = n - 1;
1155    }
1156    c
1157}
1158
1159/// [`fold_mesh_avx512`] two points at a time.
1160#[cfg(target_arch = "aarch64")]
1161fn fold_mesh_neon(
1162    simbox: &Cell,
1163    xyz: &[[f64; 3]],
1164    n: [i32; 3],
1165    lo: usize,
1166    hi: usize,
1167    out: MeshOut<'_>,
1168    mut count: impl FnMut(usize),
1169) -> usize {
1170    // NEON is baseline on aarch64. A runtime check would not change this.
1171    if !cfg!(target_feature = "neon") {
1172        return lo;
1173    }
1174    let (frac, folded, key) = out;
1175    let f = Fold8::new(simbox, n);
1176    let flat = xyz.as_ptr() as *const f64;
1177    let mut k = lo;
1178    while k + 2 <= hi {
1179        // Safety: NEON is a target feature and rows `k..k + 2` are in `xyz`.
1180        let (s, p, b) = unsafe { fold2(&f, flat.add(3 * k)) };
1181        for l in 0..2 {
1182            let i = k + l;
1183            frac[i] = [s[0][l], s[1][l], s[2][l]];
1184            folded[i] = [p[0][l], p[1][l], p[2][l]];
1185            let c = flat_cell([b[0][l], b[1][l], b[2][l]], n);
1186            key[i] = c as u32;
1187            count(c);
1188        }
1189        k += 2;
1190    }
1191    k
1192}
1193
1194/// Bins per axis for `edge`, with the same cell cap as [`Mesh::build`].
1195pub(crate) fn grid_dims(simbox: &Cell, edge: f64) -> Result<[i32; 3], Error> {
1196    let w = simbox.widths();
1197    let n = [
1198        bins_1d(w[0], edge)?,
1199        bins_1d(w[1], edge)?,
1200        bins_1d(w[2], edge)?,
1201    ];
1202    i64::from(n[0])
1203        .checked_mul(i64::from(n[1]))
1204        .and_then(|v| v.checked_mul(i64::from(n[2])))
1205        .filter(|&v| v > 0 && v <= MAX_CELLS)
1206        .ok_or(Error::TooManyCells)?;
1207    Ok(n)
1208}
1209
1210/// Folded Cartesian position and bin of `r`, the values [`Mesh::build`]
1211/// stores, so a cutoff row sees the same coordinates.
1212#[inline]
1213pub(crate) fn fold_point(simbox: &Cell, r: [f64; 3], n: [i32; 3]) -> ([f64; 3], [i32; 3]) {
1214    let s = simbox.fractional(r);
1215    let b = [
1216        bin_coord(s[0], n[0]),
1217        bin_coord(s[1], n[1]),
1218        bin_coord(s[2], n[2]),
1219    ];
1220    (simbox.cartesian(s), b)
1221}
1222
1223/// Flat index of an in-range bin.
1224#[inline]
1225pub(crate) fn flat_cell(b: [i32; 3], n: [i32; 3]) -> usize {
1226    ((b[2] * n[1] + b[1]) * n[0] + b[0]) as usize
1227}
1228
1229/// Flat index of any bin, folded into the box.
1230pub(crate) fn wrap_cell(b: [i32; 3], n: [i32; 3]) -> usize {
1231    cell_index(b[0], b[1], b[2], n[0], n[1], n[2])
1232}
1233
1234fn bin_coord(s: f64, n: i32) -> i32 {
1235    let mut c = (s * f64::from(n)) as i32;
1236    if c < 0 {
1237        c = 0;
1238    }
1239    if c >= n {
1240        c = n - 1;
1241    }
1242    c
1243}
1244
1245#[inline(always)]
1246fn split_axis(i: i32, n: i32) -> (i32, i32) {
1247    if i >= 0 && i < n {
1248        (i, 0)
1249    } else {
1250        (i.rem_euclid(n), i.div_euclid(n))
1251    }
1252}
1253
1254fn cell_index(ix: i32, iy: i32, iz: i32, nx: i32, ny: i32, nz: i32) -> usize {
1255    let (cx, _) = split_axis(ix, nx);
1256    let (cy, _) = split_axis(iy, ny);
1257    let (cz, _) = split_axis(iz, nz);
1258    ((cz * ny + cy) * nx + cx) as usize
1259}
1260
1261pub(crate) fn certify(dist: f64) -> f64 {
1262    if dist <= 0.0 || !dist.is_finite() {
1263        return 0.0;
1264    }
1265    let d = dist - dist * CERT_REL - CERT_ABS;
1266    if d > 0.0 {
1267        d
1268    } else {
1269        0.0
1270    }
1271}
1272
1273#[cfg(test)]
1274mod tests {
1275    use super::*;
1276
1277    #[test]
1278    fn parallel_fill_keeps_every_point_once() {
1279        let nside = 22usize;
1280        let a = 3.125;
1281        let boxl = nside as f64 * a;
1282        let cell = crate::Cell::ortho(boxl, boxl, boxl).unwrap();
1283        let mut xyz = Vec::with_capacity(nside * nside * nside);
1284        for iz in 0..nside {
1285            for iy in 0..nside {
1286                for ix in 0..nside {
1287                    xyz.push([ix as f64 * a, iy as f64 * a, iz as f64 * a]);
1288                }
1289            }
1290        }
1291        let mesh = Mesh::build(&xyz, &cell, None, 3.0).unwrap();
1292        assert_eq!(mesh.offsets[mesh.offsets.len() - 1], xyz.len());
1293        let mut occ = mesh.occupants.clone();
1294        occ.sort_unstable();
1295        occ.dedup();
1296        assert_eq!(occ.len(), xyz.len());
1297        let all: Vec<usize> = (0..xyz.len()).collect();
1298        let listed = Mesh::build(&xyz, &cell, Some(&all), 3.0).unwrap();
1299        let mut listed_occ = listed.occupants.clone();
1300        listed_occ.sort_unstable();
1301        assert_eq!(listed_occ, all);
1302    }
1303
1304    /// The staged build bins the points as the serial build does at every
1305    /// width: the same offsets, the same occupants in ascending order
1306    /// within each bin, and the same slot coordinates, for clustered points
1307    /// in shuffled order, with and without an active list, and with more
1308    /// bins than points.
1309    #[cfg(feature = "parallel")]
1310    #[test]
1311    fn every_pool_width_bins_like_one_thread() {
1312        let cell = crate::Cell::ortho(61.0, 47.0, 53.0).unwrap();
1313        let mut state = 0x9e37_79b9_7f4a_7c15u64;
1314        let mut xyz = sample_points(&cell, 30_000, &mut state);
1315        for p in xyz.iter_mut().take(12_000) {
1316            p[0] *= 0.1;
1317            p[1] *= 0.2;
1318        }
1319        for i in (1..xyz.len()).rev() {
1320            let j = (xorshift(&mut state) % (i as u64 + 1)) as usize;
1321            xyz.swap(i, j);
1322        }
1323        let list: Vec<usize> = (0..xyz.len()).filter(|i| i % 3 != 1).collect();
1324        let take = |mesh: &Mesh| {
1325            (
1326                mesh.offsets.clone(),
1327                mesh.occupants.clone(),
1328                mesh.slot_frac
1329                    .iter()
1330                    .copied()
1331                    .map(bits3)
1332                    .collect::<Vec<_>>(),
1333                mesh.slot_folded
1334                    .iter()
1335                    .copied()
1336                    .map(bits3)
1337                    .collect::<Vec<_>>(),
1338            )
1339        };
1340        let build = |width: usize, active: Option<&[usize]>, edge: f64| {
1341            if width == 1 {
1342                return take(&Mesh::build(&xyz, &cell, active, edge).unwrap());
1343            }
1344            let pool = rayon::ThreadPoolBuilder::new()
1345                .num_threads(width)
1346                .build()
1347                .unwrap();
1348            let stages = MeshStages::new(&xyz, &cell, active, edge, width).unwrap();
1349            let fold = |_: &mut (), c: usize| stages.fold(c);
1350            let prefix = |_: &mut (), _: usize| stages.prefix();
1351            let scatter = |_: &mut (), t: usize| stages.scatter(t);
1352            let spawn = |job: Box<dyn FnOnce() + Send + 'static>| pool.spawn(job);
1353            crate::team::run(
1354                width,
1355                Some(&spawn),
1356                &[
1357                    crate::team::Stage {
1358                        chunks: stages.fold_chunks(),
1359                        run: &fold,
1360                    },
1361                    crate::team::Stage {
1362                        chunks: 1,
1363                        run: &prefix,
1364                    },
1365                    crate::team::Stage {
1366                        chunks: stages.scatter_chunks(),
1367                        run: &scatter,
1368                    },
1369                ],
1370            );
1371            take(stages.mesh())
1372        };
1373        for edge in [3.0, 0.9] {
1374            for active in [None, Some(&list[..])] {
1375                let one = build(1, active, edge);
1376                for c in 0..one.0.len() - 1 {
1377                    let bin = &one.1[one.0[c]..one.0[c + 1]];
1378                    assert!(bin.windows(2).all(|w| w[0] < w[1]), "bin {c} order");
1379                }
1380                for width in [2, 3, 8] {
1381                    assert!(
1382                        build(width, active, edge) == one,
1383                        "width {width} edge {edge}"
1384                    );
1385                }
1386            }
1387        }
1388    }
1389
1390    #[test]
1391    fn new_layer_is_the_cube_then_one_face() {
1392        let mut first = Vec::new();
1393        for_new_layer([-1, -1, -1], [1, 1, 1], |dx, dy, dz| {
1394            first.push((dx, dy, dz));
1395        });
1396        assert_eq!(first.len(), 27);
1397        let mut grown = Vec::new();
1398        for_new_layer([1, 1, 1], [1, 2, 1], |dx, dy, dz| {
1399            grown.push((dx, dy, dz));
1400        });
1401        assert_eq!(grown.len(), 2 * 3 * 3);
1402        assert!(grown.iter().all(|(_, y, _)| y.abs() == 2));
1403    }
1404
1405    fn bits3(v: [f64; 3]) -> [u64; 3] {
1406        [v[0].to_bits(), v[1].to_bits(), v[2].to_bits()]
1407    }
1408
1409    fn xorshift(state: &mut u64) -> u64 {
1410        let mut s = *state;
1411        s ^= s << 13;
1412        s ^= s >> 7;
1413        s ^= s << 17;
1414        *state = s;
1415        s
1416    }
1417
1418    fn sample_points(cell: &crate::Cell, n: usize, state: &mut u64) -> Vec<[f64; 3]> {
1419        let mut xyz = Vec::with_capacity(n);
1420        for i in 0..n {
1421            let unit = |state: &mut u64| (xorshift(state) >> 11) as f64 / (1u64 << 53) as f64;
1422            let s = [unit(state), unit(state), unit(state)];
1423            let mut p = cell.cartesian(s);
1424            if i % 11 == 0 {
1425                p[0] -= cell.widths()[0];
1426            }
1427            if i % 13 == 0 {
1428                p[1] += 2.0 * cell.widths()[1];
1429            }
1430            if i % 17 == 0 {
1431                p[2] = -0.0;
1432            }
1433            xyz.push(p);
1434        }
1435        if n > 0 {
1436            xyz[0] = [0.0, 0.0, 0.0];
1437        }
1438        xyz
1439    }
1440
1441    #[test]
1442    fn every_simd_path_folds_like_scalar() {
1443        let cells = [
1444            crate::Cell::ortho(25.0, 18.0, 30.0).unwrap(),
1445            crate::Cell::ortho_origin(25.0, 18.0, 30.0, [1.5, -2.0, 0.25]).unwrap(),
1446            crate::Cell::from_vectors(
1447                [25.0, 0.0, 0.0],
1448                [4.0, 24.0, 0.0],
1449                [-3.0, 2.0, 24.5],
1450                [0.5, -0.5, 1.0],
1451            )
1452            .unwrap(),
1453            crate::Cell::from_vectors(
1454                [24.0, 3.0, -2.0],
1455                [2.5, 23.5, 3.0],
1456                [-1.5, 2.0, 24.0],
1457                [0.0; 3],
1458            )
1459            .unwrap(),
1460        ];
1461        let mut state = 0x853c_49e6_748f_ea9bu64;
1462        for cell in &cells {
1463            for &n in &[1usize, 3, 7, 8, 17, 64, 257] {
1464                let xyz = sample_points(cell, n, &mut state);
1465                compare_mesh(cell, &xyz);
1466            }
1467        }
1468        let big = sample_points(&cells[0], 9_000, &mut state);
1469        compare_mesh(&cells[0], &big);
1470    }
1471
1472    fn compare_mesh(cell: &crate::Cell, xyz: &[[f64; 3]]) {
1473        let scalar = {
1474            let _guard = crate::simd::force(crate::simd::Path::Scalar);
1475            Mesh::build(xyz, cell, None, 3.0).unwrap()
1476        };
1477        for path in crate::simd::paths_to_compare() {
1478            let got = {
1479                let _guard = crate::simd::force(path);
1480                Mesh::build(xyz, cell, None, 3.0).unwrap()
1481            };
1482            assert_eq!((got.nx, got.ny, got.nz), (scalar.nx, scalar.ny, scalar.nz));
1483            for i in 0..xyz.len() {
1484                assert_eq!(
1485                    bits3(got.frac[i]),
1486                    bits3(scalar.frac[i]),
1487                    "{path:?} frac {i}"
1488                );
1489                assert_eq!(
1490                    bits3(got.folded[i]),
1491                    bits3(scalar.folded[i]),
1492                    "{path:?} folded {i}"
1493                );
1494                assert_eq!(got.key[i], scalar.key[i], "{path:?} key {i}");
1495            }
1496            assert_eq!(got.offsets, scalar.offsets, "{path:?} offsets");
1497            assert_eq!(got.occupants, scalar.occupants, "{path:?} occupants");
1498        }
1499    }
1500
1501    /// `s = -0`, a tiny negative, one ulp below 1, `2^52`, and NaN.
1502    /// Each wide path must match scalar `floor_fast`.
1503    #[test]
1504    fn fold_edges_match_scalar_on_every_path() {
1505        let cell = crate::Cell::ortho(1.0, 1.0, 1.0).unwrap();
1506        let neg0 = -0.0f64;
1507        let frac = cell.fractional([neg0, 0.0, 0.0]);
1508        assert_eq!(frac[0].to_bits(), neg0.to_bits());
1509        let tiny = -1.0e-20;
1510        let below1 = f64::from_bits(1.0f64.to_bits() - 1);
1511        let big = 4_503_599_627_370_496.0;
1512        let nan = f64::NAN;
1513        let edges = [neg0, tiny, below1, big, nan, 0.25, neg0, below1];
1514        let xyz: Vec<[f64; 3]> = edges.iter().map(|&s| [s, 0.5, s]).collect();
1515        compare_mesh(&cell, &xyz);
1516    }
1517
1518    #[test]
1519    fn frontier_is_at_least_the_min_cell_bound() {
1520        // Bin 2 of 8 covers fractional [0.25, 0.375). The source sits inside it.
1521        let s = [0.30, 0.30, 0.30];
1522        let bin = [2, 2, 2];
1523        let n = [8, 8, 8];
1524        let w = [10.0, 10.0, 10.0];
1525        let h = w[0] / f64::from(n[0]);
1526        for reach in 1..=3 {
1527            let gap = axis_gap(s[0], bin[0], reach, n[0], w[0])
1528                .min(axis_gap(s[1], bin[1], reach, n[1], w[1]))
1529                .min(axis_gap(s[2], bin[2], reach, n[2], w[2]));
1530            let bound = gap * gap;
1531            let loose = (f64::from(reach) * h) * (f64::from(reach) * h);
1532            assert!(
1533                bound + 1e-9 >= loose * (1.0 - 2.0 * CERT_REL),
1534                "reach {reach}: {bound} vs {loose}"
1535            );
1536        }
1537    }
1538}