Skip to main content

linkcell/
pairs.rs

1//! Cutoff pair list with integer cell shifts.
2//!
3//! [`knearest`](crate::knearest) unique-indexes the neighbour and
4//! drops the image. This walk keeps every atom-image pair whose
5//! squared distance is strictly below `cutoff²`, including periodic
6//! self-images. Each unordered pair is tested once. Hits from a bin
7//! are buffered, then the rows are written. A full list writes both
8//! `(i, j, S)` and `(j, i, -S)`. Displacement is `q - p + lattice_shift(S)`,
9//! which is [`Cell::dist2_shifted`](crate::Cell::dist2_shifted). This is
10//! not [`dist2_ortho_diffs`](crate::dist2_ortho_diffs): that Highway
11//! kernel wraps a raw difference into the central cell, and a second
12//! wrap on an already shifted delta changes which rows survive.
13
14use crate::bins::{self, axis_gap};
15use crate::cell::Cell;
16use crate::simd::Path;
17use crate::Error;
18
19#[path = "pair_wide.rs"]
20mod wide;
21
22const MAX_IMAGES: i64 = 1 << 24;
23
24/// One atom-image pair inside the cutoff.
25#[derive(Clone, Copy, Debug, PartialEq)]
26pub struct Pair {
27    /// Source index.
28    pub i: usize,
29    /// Target index.
30    pub j: usize,
31    /// Integer cell shift applied to the target (`S` in vesin/tonari).
32    pub shift: [i32; 3],
33    /// Squared distance after the shift.
34    pub dist2: f64,
35}
36
37pub(crate) fn keep_half(i: usize, j: usize, shift: [i32; 3]) -> bool {
38    if i != j {
39        return i < j;
40    }
41    for s in shift {
42        if s != 0 {
43            return s < 0;
44        }
45    }
46    true
47}
48
49/// Pairs with `dist2 < cutoff²`, one row per atom-image.
50///
51/// `half` keeps the canonical side of `(i, j, S)` vs `(j, i, -S)`.
52/// Zero-shift self pairs are omitted. Periodic self-images stay.
53/// Image count above 2^24 is [`Error::TooManyImages`].
54pub fn pairs_within(
55    xyz: &[[f64; 3]],
56    simbox: &Cell,
57    cutoff: f64,
58    mask: Option<&[bool]>,
59    cell_hint: Option<f64>,
60    half: bool,
61) -> Result<Vec<Pair>, Error> {
62    let est = hit_estimate(xyz.len(), simbox, cutoff);
63    if walk_threads(est) == 1 {
64        let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
65        #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
66        if let Some(words) = plan.fused().filter(|_| knobs::fused()) {
67            return Ok(plan.fused_rows(&words));
68        }
69        return Ok(plan.search().into_pairs());
70    }
71    // The buffer is reserved here, on the caller's thread, from the
72    // ideal-gas estimate; search and write then run in one pool entry.
73    let rows_guess = row_guess(est, half);
74    let mut out: Vec<Pair> = Vec::with_capacity(rows_guess);
75    advise_huge(&mut out);
76    let base = RowPtr(out.as_mut_ptr() as *mut std::mem::MaybeUninit<Pair>);
77    let (rows, rest) = in_pool(est, || -> Result<(usize, Option<Found>), Error> {
78        let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
79        // A full list on AVX-512 with each thread's rows past L2: each
80        // thread counts its bins' rows, then writes them from the tile
81        // kernel at their offset, so no hit is buffered. A short estimate
82        // falls back to buffered hits.
83        #[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
84        if let Some(words) = plan.fused_split().filter(|_| knobs::fused()) {
85            let ranges = cell_ranges(&plan.grid.offsets, plan.threads);
86            // The count costs a second search; it pays once each thread's
87            // rows outgrow L2 and their stores can run behind the tile.
88            let per = rows_guess / ranges.len().max(1);
89            if ranges.len() > 1
90                && ranges.len() <= crate::pool_width()
91                && ahead(per, std::mem::size_of::<Pair>())
92            {
93                let off = plan.fused_offsets(&words, &ranges);
94                let rows = off[ranges.len()];
95                if rows <= rows_guess {
96                    // Safety: `out` holds `rows_guess >= rows` rows.
97                    unsafe { plan.fused_fill(&words, base, &ranges, &off) };
98                    return Ok((rows, None));
99                }
100            }
101        }
102        let found = plan.search();
103        let rows = found.rows();
104        if rows > rows_guess {
105            return Ok((rows, Some(found)));
106        }
107        // Safety: `out` holds `rows_guess >= rows` rows.
108        unsafe { found.write_pairs(base.ptr()) };
109        Ok((rows, None))
110    })?;
111    if let Some(found) = rest {
112        out.reserve(rows);
113        // Safety: `out` now holds `rows` rows.
114        unsafe { found.write_pairs(out.as_mut_ptr()) };
115    }
116    // Safety: every row below `rows` is written.
117    unsafe { out.set_len(rows) };
118    Ok(out)
119}
120
121/// How many rows [`pairs_within`] would write, without writing them.
122///
123/// The tile still plans the bins and tests every candidate. It does not
124/// store a `Pair` row, so the time is the search rather than the row
125/// stream. The count matches `pairs_within(...).len()` for the same
126/// arguments.
127pub fn pairs_within_count(
128    xyz: &[[f64; 3]],
129    simbox: &Cell,
130    cutoff: f64,
131    mask: Option<&[bool]>,
132    cell_hint: Option<f64>,
133    half: bool,
134) -> Result<usize, Error> {
135    let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
136    #[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
137    if let Some(words) = plan.fused().filter(|_| knobs::fused()) {
138        return Ok(plan.count_rows(&words));
139    }
140    Ok(plan.search().rows())
141}
142
143/// Write [`pairs_within`] into `out`, keeping its allocation.
144///
145/// A rank that calls this twice reuses the pages from the first call.
146/// A fresh `Vec` on every call is unmapped and faulted again, which on
147/// a half-frame list costs more than walking the pairs.
148pub fn pairs_within_into(
149    xyz: &[[f64; 3]],
150    simbox: &Cell,
151    cutoff: f64,
152    mask: Option<&[bool]>,
153    cell_hint: Option<f64>,
154    half: bool,
155    out: &mut Vec<Pair>,
156) -> Result<(), Error> {
157    let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
158    #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
159    if let Some(words) = plan.fused().filter(|_| knobs::fused()) {
160        plan.fused_into_vec(&words, out);
161        return Ok(());
162    }
163    *out = plan.search().into_pairs();
164    Ok(())
165}
166
167/// Ask Linux to back the 2 MB-aligned interior of a large buffer this
168/// library allocated with transparent huge pages, so the row stores take
169/// one page walk per 2 MB rather than per 4 KB. It is advice: the system's
170/// policy decides, and nothing outside the buffer is touched.
171fn advise_huge<T>(buf: &mut Vec<T>) {
172    #[cfg(all(
173        target_os = "linux",
174        any(target_arch = "x86_64", target_arch = "aarch64")
175    ))]
176    {
177        const HUGE: usize = 1 << 21;
178        const MADV_HUGEPAGE: std::ffi::c_int = 14;
179        extern "C" {
180            fn madvise(
181                addr: *mut std::ffi::c_void,
182                len: usize,
183                advice: std::ffi::c_int,
184            ) -> std::ffi::c_int;
185        }
186        let bytes = buf.capacity().saturating_mul(std::mem::size_of::<T>());
187        if bytes < 2 * HUGE {
188            return;
189        }
190        let start = buf.as_mut_ptr() as usize;
191        let lo = (start + HUGE - 1) & !(HUGE - 1);
192        let hi = (start + bytes) & !(HUGE - 1);
193        if hi > lo {
194            // Safety: `lo..hi` lies inside the buffer's allocation, and the
195            // advice changes neither its contents nor its mapping.
196            unsafe { madvise(lo as *mut std::ffi::c_void, hi - lo, MADV_HUGEPAGE) };
197        }
198    }
199    #[cfg(not(all(
200        target_os = "linux",
201        any(target_arch = "x86_64", target_arch = "aarch64")
202    )))]
203    let _ = buf;
204}
205
206/// Rows to reserve for `hits` expected pairs: a quarter more than the
207/// ideal gas, two rows per pair on a full list.
208fn row_guess(hits: usize, half: bool) -> usize {
209    let rows = if half { hits } else { hits.saturating_mul(2) };
210    rows.saturating_add(rows / 4).saturating_add(64)
211}
212
213/// The same rows as [`pairs_within`], as four columns.
214///
215/// `i`, `j`, and `shift` are the vesin / tonari `ijS` layout and
216/// `dist2` is the squared distance. Row `t` of each column is one
217/// atom-image. The vectors are cleared, then filled once; their
218/// capacity is kept for the next call. An index above `i32::MAX` is
219/// [`Error::Overflow`].
220pub fn pairs_within_columns(
221    xyz: &[[f64; 3]],
222    simbox: &Cell,
223    cutoff: f64,
224    mask: Option<&[bool]>,
225    cell_hint: Option<f64>,
226    half: bool,
227    out: &mut PairColumns,
228) -> Result<(), Error> {
229    if xyz.len() > i32::MAX as usize {
230        return Err(Error::Overflow);
231    }
232    let est = hit_estimate(xyz.len(), simbox, cutoff);
233    if walk_threads(est) == 1 {
234        let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
235        #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
236        if plan.fused().is_some() && knobs::fused() {
237            plan.fused_columns(out);
238            return Ok(());
239        }
240        plan.search().fill_columns(out);
241        return Ok(());
242    }
243    // Columns are reserved on the caller's thread; search and write run
244    // in one pool entry.
245    let rows_guess = row_guess(est, half);
246    out.i.clear();
247    out.j.clear();
248    out.shift.clear();
249    out.dist2.clear();
250    out.i.reserve(rows_guess);
251    out.j.reserve(rows_guess);
252    out.shift.reserve(rows_guess);
253    out.dist2.reserve(rows_guess);
254    out.advise_huge();
255    let ptrs = ColumnPtrs {
256        i: RowPtr(out.i.as_mut_ptr() as *mut std::mem::MaybeUninit<i32>),
257        j: RowPtr(out.j.as_mut_ptr() as *mut std::mem::MaybeUninit<i32>),
258        shift: RowPtr(out.shift.as_mut_ptr() as *mut std::mem::MaybeUninit<i32>),
259        d2: RowPtr(out.dist2.as_mut_ptr() as *mut std::mem::MaybeUninit<f64>),
260    };
261    let (rows, rest) = in_pool(est, || -> Result<(usize, Option<Found>), Error> {
262        let plan = plan(xyz, simbox, cutoff, mask, cell_hint, half)?;
263        // Half lists buffer every hit and then copy it into the columns.
264        // Past L2 that copy is the slow part: count the rows of each bin
265        // range and write them from the tile kernel at their own offset.
266        #[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
267        if let Some(words) = plan.fused_split_columns().filter(|_| knobs::fused()) {
268            let ranges = cell_ranges(&plan.grid.offsets, plan.threads);
269            let per = rows_guess / ranges.len().max(1);
270            // A second walk pays when each atom has many neighbours and the
271            // buffered copy is the large traffic. A sparse list is faster
272            // written once.
273            let dense = est / xyz.len().max(1) >= 64;
274            if dense
275                && ranges.len() > 1
276                && ranges.len() <= crate::pool_width()
277                && ahead(per, COLUMN_BYTES)
278            {
279                let off = plan.fused_offsets(&words, &ranges);
280                let rows = off[ranges.len()];
281                if rows <= rows_guess {
282                    // Safety: every column holds `rows_guess >= rows` rows.
283                    unsafe { plan.fused_fill_columns(&words, ptrs, &ranges, &off) };
284                    return Ok((rows, None));
285                }
286            }
287        }
288        let found = plan.search();
289        let rows = found.rows();
290        if rows > rows_guess {
291            return Ok((rows, Some(found)));
292        }
293        // Safety: every column holds `rows_guess >= rows` rows.
294        unsafe { found.write_columns(ptrs.i.ptr(), ptrs.j.ptr(), ptrs.shift.ptr(), ptrs.d2.ptr()) };
295        Ok((rows, None))
296    })?;
297    match rest {
298        Some(found) => found.fill_columns(out),
299        // Safety: every row below `rows` is written in every column.
300        None => unsafe {
301            out.i.set_len(rows);
302            out.j.set_len(rows);
303            out.shift.set_len(rows);
304            out.dist2.set_len(rows);
305        },
306    }
307    Ok(())
308}
309
310/// Run `work` on a pool thread when the call will use several threads.
311///
312/// A caller outside the pool would otherwise run the serial steps while
313/// every worker spins, one thread more than the pool has cores. Inside
314/// the pool the caller sleeps on the join instead. Output buffers are
315/// still allocated on the caller's thread: glibc gives a large block on
316/// a worker its own heap and unmaps it when the block is freed, so the
317/// next call would fault every page again.
318pub(crate) fn in_pool<R: Send>(hits: usize, work: impl FnOnce() -> R + Send) -> R {
319    #[cfg(feature = "parallel")]
320    if walk_threads(hits) > 1 && rayon::current_thread_index().is_none() {
321        return rayon::scope(|_| work());
322    }
323    let _ = hits;
324    work()
325}
326
327/// Bin edge when the caller did not pass one.
328///
329/// One cell per cutoff sweeps a cube `6.4` times the cutoff ball. Splitting
330/// the cutoff into `k` cells, with `k` chosen the way vesin does,
331///
332/// `k = round((atoms_per_cell / (2 * 8))^(1/4))` clamped to `1..=6`,
333///
334/// cuts that volume when a cell would otherwise hold many atoms. `8` is
335/// the cell-visit cost in units of one candidate check. A caller `cell_hint`
336/// still wins: [`bins::target_edge`] uses the hint whenever it is positive.
337pub(crate) fn default_edge(simbox: &Cell, n: usize, cutoff: f64) -> f64 {
338    const VISIT_COST: f64 = 8.0;
339    let mut per = n as f64;
340    for width in simbox.widths() {
341        let cells = (width / cutoff).floor().clamp(1.0, 1.0e7);
342        per /= cells;
343    }
344    let k = (per / (2.0 * VISIT_COST)).powf(0.25);
345    let k = if k.is_finite() {
346        k.round().clamp(1.0, 6.0)
347    } else {
348        1.0
349    };
350    let edge = cutoff / k;
351    if edge.is_finite() && edge > 0.0 {
352        edge
353    } else {
354        cutoff
355    }
356}
357
358/// Ideal-gas count of unordered pairs within `cutoff` for `n` points.
359pub(crate) fn hit_estimate(n: usize, simbox: &Cell, cutoff: f64) -> usize {
360    let w = simbox.widths();
361    let volume = (w[0] * w[1] * w[2]).max(1.0e-30);
362    let shell = 4.1887902047863905 * cutoff * cutoff * cutoff;
363    let pairs = 0.5 * (n as f64) * (n as f64) * shell / volume;
364    if pairs.is_finite() {
365        pairs.min(usize::MAX as f64 / 2.0) as usize
366    } else {
367        0
368    }
369}
370
371/// Cutoff rows as columns: `i[t]`, `j[t]`, `shift[t]`, `dist2[t]`.
372#[derive(Clone, Debug, Default, PartialEq)]
373pub struct PairColumns {
374    /// Source index.
375    pub i: Vec<i32>,
376    /// Target index.
377    pub j: Vec<i32>,
378    /// Integer cell shift applied to the target (`S`).
379    pub shift: Vec<[i32; 3]>,
380    /// Squared distance after the shift.
381    pub dist2: Vec<f64>,
382}
383
384impl PairColumns {
385    /// Number of rows.
386    pub fn len(&self) -> usize {
387        self.i.len()
388    }
389
390    /// `true` when there are no rows.
391    pub fn is_empty(&self) -> bool {
392        self.i.is_empty()
393    }
394
395    /// [`advise_huge`] for every column.
396    fn advise_huge(&mut self) {
397        advise_huge(&mut self.i);
398        advise_huge(&mut self.j);
399        advise_huge(&mut self.shift);
400        advise_huge(&mut self.dist2);
401    }
402}
403
404/// Integer images removed when positions are wrapped into the search cell.
405/// Only relative images matter, so a common translation needs no storage.
406#[derive(Clone, Default)]
407struct ImageOffsets(Option<std::sync::Arc<Vec<[i64; 3]>>>);
408
409impl ImageOffsets {
410    fn new(
411        xyz: &[[f64; 3]],
412        cell: &Cell,
413        active: Option<&[usize]>,
414        repeats: [i32; 3],
415    ) -> Result<Self, Error> {
416        let inverse = cell.hinv();
417        let mut reference = None;
418        let mut images = Vec::new();
419        let mut low = [0i64; 3];
420        let mut high = [0i64; 3];
421        let count = active.map_or(xyz.len(), |indices| indices.len());
422        for at in 0..count {
423            let i = active.map_or(at, |indices| indices[at]);
424            let wrapped = cell.cartesian(cell.fractional(xyz[i]));
425            let delta = [
426                xyz[i][0] - wrapped[0],
427                xyz[i][1] - wrapped[1],
428                xyz[i][2] - wrapped[2],
429            ];
430            let image: [f64; 3] = std::array::from_fn(|a| {
431                (inverse[0][a] * delta[0] + inverse[1][a] * delta[1] + inverse[2][a] * delta[2])
432                    .round()
433            });
434            let base = reference.get_or_insert(image);
435            let mut relative = [0i64; 3];
436            for a in 0..3 {
437                let value = image[a] - base[a];
438                if !value.is_finite() || value.abs() > i32::MAX as f64 {
439                    return Err(Error::Overflow);
440                }
441                relative[a] = value as i64;
442                low[a] = low[a].min(relative[a]);
443                high[a] = high[a].max(relative[a]);
444                if high[a] - low[a] + i64::from(repeats[a]) > i64::from(i32::MAX) {
445                    return Err(Error::Overflow);
446                }
447            }
448            if images.is_empty() && relative != [0; 3] {
449                images.resize(xyz.len(), [0; 3]);
450            }
451            if !images.is_empty() {
452                images[i] = relative;
453            }
454        }
455        Ok(Self(
456            (!images.is_empty()).then(|| std::sync::Arc::new(images)),
457        ))
458    }
459
460    fn shift(&self, i: usize, j: usize, wrapped: [i32; 3]) -> [i32; 3] {
461        match &self.0 {
462            None => wrapped,
463            Some(images) => std::array::from_fn(|a| {
464                // The image span plus the stencil radius fits i32 in new().
465                (i64::from(wrapped[a]) + images[i][a] - images[j][a]) as i32
466            }),
467        }
468    }
469}
470
471/// The grid, stencil, and bounds of one cutoff search.
472pub(crate) struct Plan {
473    images: ImageOffsets,
474    grid: Grid,
475    partners: std::sync::Arc<PartnerList>,
476    cut2: f64,
477    margin: f64,
478    /// [`Path`] chosen once on the calling thread.
479    path: Path,
480    half: bool,
481    threads: usize,
482}
483
484impl Plan {
485    fn walk(&self) -> Walk<'_> {
486        Walk {
487            grid: &self.grid,
488            cut2: self.cut2,
489            margin: self.margin,
490            partners: &self.partners,
491            path: self.path,
492        }
493    }
494
495    /// Every hit, by cell range.
496    pub(crate) fn search(&self) -> Found {
497        Found {
498            images: self.images.clone(),
499            chunks: self.walk().collect(self.threads),
500            half: self.half,
501            path: self.path,
502        }
503    }
504
505    /// One thread and AVX-512: the rows, full or half, can be written
506    /// from the tile kernel in one pass.
507    #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
508    fn fused(&self) -> Option<RowWords> {
509        if self.threads == 1 && self.path == Path::Avx512 && self.images.0.is_none() {
510            RowWords::of_pair()
511        } else {
512            None
513        }
514    }
515}
516
517/// [`Plan::search`] after [`plan`].
518#[cfg_attr(not(feature = "capi"), allow(dead_code))]
519pub(crate) fn search(
520    xyz: &[[f64; 3]],
521    simbox: &Cell,
522    cutoff: f64,
523    mask: Option<&[bool]>,
524    cell_hint: Option<f64>,
525    half: bool,
526) -> Result<Found, Error> {
527    Ok(plan(xyz, simbox, cutoff, mask, cell_hint, half)?.search())
528}
529
530pub(crate) fn plan(
531    xyz: &[[f64; 3]],
532    simbox: &Cell,
533    cutoff: f64,
534    mask: Option<&[bool]>,
535    cell_hint: Option<f64>,
536    half: bool,
537) -> Result<Plan, Error> {
538    if !cutoff.is_finite() || cutoff <= 0.0 {
539        return Err(Error::BadCutoff);
540    }
541    if xyz.is_empty() {
542        return Err(Error::Empty);
543    }
544    let n = xyz.len();
545    if n > u32::MAX as usize {
546        return Err(Error::Overflow);
547    }
548    if let Some(m) = mask {
549        if m.len() != n {
550            return Err(Error::MaskLen);
551        }
552    }
553    let active: Option<Vec<usize>> = mask.map(|m| (0..n).filter(|&i| m[i]).collect());
554    let n_act = active.as_ref().map_or(n, |a| a.len());
555    if n_act == 0 {
556        return Ok(Plan {
557            images: ImageOffsets::default(),
558            grid: Grid::empty(),
559            partners: std::sync::Arc::new(PartnerList {
560                key: ([0; 12], [1, 1, 1], [0; 3], 0),
561                off: vec![0],
562                items: Vec::new(),
563                s_max: 0.0,
564                d_max: 0.0,
565            }),
566            cut2: cutoff * cutoff,
567            margin: 0.0,
568            path: Path::Scalar,
569            half,
570            threads: 1,
571        });
572    }
573    retain_pair_pages();
574
575    let w = simbox.widths();
576    let mut image_count: i64 = 1;
577    let mut repeats = [0i32; 3];
578    for a in 0..3 {
579        let r = (cutoff / w[a]).ceil();
580        if !r.is_finite() || r > i32::MAX as f64 {
581            return Err(Error::TooManyImages);
582        }
583        repeats[a] = r as i32;
584        let factor = 2 * i64::from(repeats[a]) + 1;
585        if image_count > MAX_IMAGES / factor {
586            return Err(Error::TooManyImages);
587        }
588        image_count *= factor;
589    }
590
591    let edge = bins::target_edge(simbox, cell_hint, default_edge(simbox, n_act, cutoff));
592    let dims = bins::grid_dims(simbox, edge)?;
593    let cell_min = (w[0] / f64::from(dims[0]))
594        .min(w[1] / f64::from(dims[1]))
595        .min(w[2] / f64::from(dims[2]));
596    let reach_cut = (cutoff / cell_min).ceil();
597    if !reach_cut.is_finite() || reach_cut > i32::MAX as f64 {
598        return Err(Error::TooManyImages);
599    }
600    let max_reach = (reach_cut as i32)
601        .max(repeats[0] * dims[0])
602        .max(repeats[1] * dims[1])
603        .max(repeats[2] * dims[2])
604        .max(1);
605    let cut2 = cutoff * cutoff;
606    // One reach for every atom: the shorter gap at either edge of a bin.
607    // The box is symmetric, so each unordered pair is visited from one
608    // side and written out in both shift directions when `half` is off.
609    let reach = uniform_reach(dims, w, cut2, max_reach);
610    let threads = walk_threads(hit_estimate(n_act, simbox, cutoff));
611    let grid_threads = if n_act >= knobs::grid_atoms() {
612        threads
613    } else {
614        1
615    };
616    // One path for the fold, the cull, the tile, and the writers.
617    // Read on this thread, before the grid's rayon fan-out.
618    let path = crate::simd::select();
619    let grid = Grid::build(xyz, simbox, active.as_deref(), dims, grid_threads, path);
620    let partners = partners_for(&grid, simbox, reach, cut2);
621    let margin = expanded_margin(&grid, &partners, cutoff);
622    Ok(Plan {
623        images: ImageOffsets::new(xyz, simbox, active.as_deref(), repeats)?,
624        grid,
625        partners,
626        cut2,
627        margin,
628        path,
629        half,
630        threads,
631    })
632}
633
634/// Threads for one search with `hits` expected pairs: one without
635/// `parallel`, or when the search is too short to pay for waking the pool.
636fn walk_threads(hits: usize) -> usize {
637    #[cfg(feature = "parallel")]
638    {
639        let threads = crate::pool_width().max(1);
640        if threads > 1 && hits >= knobs::split_pairs() {
641            return threads;
642        }
643    }
644    let _ = hits;
645    1
646}
647
648/// glibc drops a large free buffer (`MADV_DONTNEED`) and the next cutoff
649/// list faults every page. Keep those pages on the heap. The knobs are
650/// `M_TRIM_THRESHOLD` and `M_MMAP_THRESHOLD`. musl has no `mallopt`.
651fn retain_pair_pages() {
652    #[cfg(all(target_os = "linux", target_env = "gnu"))]
653    {
654        use std::sync::Once;
655        static ONCE: Once = Once::new();
656        ONCE.call_once(|| {
657            // Safety: mallopt is process-wide and these two knobs are integers.
658            unsafe {
659                extern "C" {
660                    fn mallopt(param: i32, value: i32) -> i32;
661                }
662                // M_TRIM_THRESHOLD: keep a freed pair buffer on the heap.
663                // M_MMAP_MAX: a large row buffer otherwise comes from mmap
664                // and disappears on free, so the next call faults every
665                // page. Zero mmap slots keeps the buffer in the arena,
666                // including a rank thread that allocates its own.
667                let _ = mallopt(-1, -1);
668                let _ = mallopt(-4, 0);
669            }
670        });
671    }
672}
673
674struct Partner {
675    /// Target bin.
676    jc: usize,
677    shift_s: [i32; 3],
678    shift: [f64; 3],
679    /// Source corner minus target corner minus `shift`: a source slot's
680    /// relative position plus this is its image relative to the target
681    /// corner.
682    delta: [f64; 3],
683}
684
685/// The bins each bin looks into, with their shifts. It depends on the
686/// box, the bin counts, the reach, and the cutoff, not on the atoms, so a
687/// search of the same box reuses it; the walk skips an empty target bin.
688struct PartnerList {
689    key: PartnerKey,
690    off: Vec<usize>,
691    items: Vec<Partner>,
692    /// Largest |component| of any shift and of any `delta`.
693    s_max: f64,
694    d_max: f64,
695}
696
697/// The box (edges and origin, as bits), the bin counts, the reach, and
698/// the squared cutoff.
699type PartnerKey = ([u64; 12], [i32; 3], [i32; 3], u64);
700
701static PARTNERS: std::sync::Mutex<Option<std::sync::Arc<PartnerList>>> =
702    std::sync::Mutex::new(None);
703
704/// [`build_partners`], or the last list when its key matches.
705fn partners_for(
706    grid: &Grid,
707    simbox: &Cell,
708    reach: [i32; 3],
709    cut2: f64,
710) -> std::sync::Arc<PartnerList> {
711    let h = simbox.h();
712    let o = simbox.origin();
713    let mut boxbits = [0u64; 12];
714    for a in 0..3 {
715        for b in 0..3 {
716            boxbits[3 * a + b] = h[a][b].to_bits();
717        }
718        boxbits[9 + a] = o[a].to_bits();
719    }
720    let key: PartnerKey = (boxbits, grid.n, reach, cut2.to_bits());
721    if let Ok(slot) = PARTNERS.lock() {
722        if let Some(list) = slot.as_ref() {
723            if list.key == key {
724                return std::sync::Arc::clone(list);
725            }
726        }
727    }
728    let built = std::sync::Arc::new(build_partners(grid, simbox, reach, cut2, key));
729    if let Ok(mut slot) = PARTNERS.lock() {
730        *slot = Some(std::sync::Arc::clone(&built));
731    }
732    built
733}
734
735fn bin_gap(src: i32, dst: i32, width: f64) -> f64 {
736    let lo_s = f64::from(src) * width;
737    let hi_s = f64::from(src + 1) * width;
738    let lo_d = f64::from(dst) * width;
739    let hi_d = f64::from(dst + 1) * width;
740    if hi_s <= lo_d {
741        lo_d - hi_s
742    } else if hi_d <= lo_s {
743        lo_s - hi_d
744    } else {
745        0.0
746    }
747}
748
749fn bins_too_far(ortho: bool, src: [i32; 3], dst: [i32; 3], width: [f64; 3], cut2: f64) -> bool {
750    let gap = [
751        bin_gap(src[0], dst[0], width[0]),
752        bin_gap(src[1], dst[1], width[1]),
753        bin_gap(src[2], dst[2], width[2]),
754    ];
755    let bound = if ortho {
756        let d = (gap[0] * gap[0] + gap[1] * gap[1] + gap[2] * gap[2]).sqrt();
757        let d = bins::certify(d);
758        d * d
759    } else {
760        let d = bins::certify(gap[0].max(gap[1]).max(gap[2]));
761        d * d
762    };
763    bound >= cut2
764}
765
766fn build_partners(
767    grid: &Grid,
768    simbox: &Cell,
769    reach: [i32; 3],
770    cut2: f64,
771    key: PartnerKey,
772) -> PartnerList {
773    let [nx, ny, nz] = grid.n;
774    let ncell = (nx as usize) * (ny as usize) * (nz as usize);
775    let width = [
776        grid.widths[0] / f64::from(nx),
777        grid.widths[1] / f64::from(ny),
778        grid.widths[2] / f64::from(nz),
779    ];
780    let ortho = simbox.is_ortho();
781    let [rx, ry, rz] = reach;
782    let mut off = vec![0usize; ncell + 1];
783    let mut items = Vec::new();
784    let (mut s_max, mut d_max) = (0.0f64, 0.0f64);
785    for iz in 0..nz {
786        for iy in 0..ny {
787            for ix in 0..nx {
788                let cell = ((iz * ny + iy) * nx + ix) as usize;
789                let src = [ix, iy, iz];
790                for dz in -rz..=rz {
791                    for dy in -ry..=ry {
792                        for dx in -rx..=rx {
793                            if !keep_dir(dx, dy, dz) {
794                                continue;
795                            }
796                            let dst = [ix + dx, iy + dy, iz + dz];
797                            if bins_too_far(ortho, src, dst, width, cut2) {
798                                continue;
799                            }
800                            let jc = bins::wrap_cell(dst, grid.n);
801                            let shift_s = [
802                                dst[0].div_euclid(nx),
803                                dst[1].div_euclid(ny),
804                                dst[2].div_euclid(nz),
805                            ];
806                            let shift = simbox.lattice_shift(shift_s[0], shift_s[1], shift_s[2]);
807                            let (a, b) = (grid.corners[cell], grid.corners[jc]);
808                            let delta = [
809                                a[0] - b[0] - shift[0],
810                                a[1] - b[1] - shift[1],
811                                a[2] - b[2] - shift[2],
812                            ];
813                            for k in 0..3 {
814                                s_max = s_max.max(shift[k].abs());
815                                d_max = d_max.max(delta[k].abs());
816                            }
817                            items.push(Partner {
818                                jc,
819                                shift_s,
820                                shift,
821                                delta,
822                            });
823                        }
824                    }
825                }
826                off[cell + 1] = items.len();
827            }
828        }
829    }
830    let list = PartnerList {
831        key,
832        off,
833        items,
834        s_max,
835        d_max,
836    };
837    crate::open_cell::note_stencil_build();
838    list
839}
840
841#[derive(Default)]
842struct Coords {
843    x: Vec<f64>,
844    y: Vec<f64>,
845    z: Vec<f64>,
846    /// Position relative to the corner of the slot's own bin.
847    rx: Vec<f64>,
848    ry: Vec<f64>,
849    rz: Vec<f64>,
850    /// `rx^2 + ry^2 + rz^2`.
851    r2: Vec<f64>,
852    /// Atom index of each slot.
853    id: Vec<u32>,
854}
855
856impl Coords {
857    /// Empty columns with room for `nslot` slots each.
858    fn clear_for(&mut self, nslot: usize) {
859        for v in [
860            &mut self.x,
861            &mut self.y,
862            &mut self.z,
863            &mut self.rx,
864            &mut self.ry,
865            &mut self.rz,
866            &mut self.r2,
867        ] {
868            v.clear();
869            v.reserve(nslot);
870        }
871        self.id.clear();
872        self.id.reserve(nslot);
873    }
874
875    /// # Safety
876    /// Every column holds `nslot` written slots.
877    unsafe fn set_len(&mut self, nslot: usize) {
878        for v in [
879            &mut self.x,
880            &mut self.y,
881            &mut self.z,
882            &mut self.rx,
883            &mut self.ry,
884            &mut self.rz,
885            &mut self.r2,
886        ] {
887            v.set_len(nslot);
888        }
889        self.id.set_len(nslot);
890    }
891}
892
893/// Buffers a grid lends back when it drops, so the next search of a
894/// similar size neither allocates nor faults them in.
895#[derive(Default)]
896struct GridBufs {
897    offsets: Vec<usize>,
898    corners: Vec<[f64; 3]>,
899    coords: Coords,
900    fold: FoldCols,
901    tally: Vec<u32>,
902    order: Vec<u32>,
903    boxes: Boxes,
904}
905
906/// Bounding boxes, in each bin's relative coordinates, of the slot runs
907/// the tile kernel reads together: runs of eight from a bin's first slot
908/// (targets) and runs of four (sources). A source run and a target run
909/// whose boxes are a cutoff apart hold no pair, so the kernel skips them
910/// (the cluster pairs of GROMACS, decided per search).
911#[derive(Default)]
912struct Boxes {
913    /// Whether the boxes are built: only for bins of [`CULL_RUNS`] runs of
914    /// eight on average. Without them every run start is zero.
915    on: bool,
916    /// First run of eight, and of four, of each bin; one more entry past
917    /// the last bin.
918    vstart: Vec<usize>,
919    gstart: Vec<usize>,
920    /// `lo x y z` then `hi x y z` per run of eight, with eight runs of
921    /// padding so a kernel can read eight runs from any bin's first.
922    v: [Vec<f64>; 6],
923    /// The same per run of four.
924    g: [Vec<f64>; 6],
925}
926
927impl Boxes {
928    /// Run starts of every bin, and room for every box, when `on`.
929    fn starts(&mut self, offsets: &[usize], on: bool) {
930        self.on = on;
931        self.vstart.clear();
932        self.gstart.clear();
933        if !on {
934            self.vstart.resize(offsets.len(), 0);
935            self.gstart.resize(offsets.len(), 0);
936            return;
937        }
938        let (mut v, mut g) = (0usize, 0usize);
939        for w in offsets.windows(2) {
940            self.vstart.push(v);
941            self.gstart.push(g);
942            let n = w[1] - w[0];
943            v += (n + 7) / 8;
944            g += (n + 3) / 4;
945        }
946        self.vstart.push(v);
947        self.gstart.push(g);
948        // The columns are read and written only through raw pointers, so
949        // they stay empty: `fill` writes every run, and the padding is
950        // written here.
951        for a in self.v.iter_mut() {
952            a.clear();
953            a.reserve(v + 8);
954            // Safety: the capacity covers the padding.
955            unsafe { std::ptr::write_bytes(a.as_mut_ptr().add(v), 0, 8) };
956        }
957        for a in self.g.iter_mut() {
958            a.clear();
959            a.reserve(g);
960        }
961    }
962
963    fn ptrs(&mut self) -> BoxPtrs {
964        let raw = |a: &mut Vec<f64>| RowPtr(a.as_mut_ptr() as *mut std::mem::MaybeUninit<f64>);
965        let [v0, v1, v2, v3, v4, v5] = &mut self.v;
966        let [g0, g1, g2, g3, g4, g5] = &mut self.g;
967        BoxPtrs {
968            v: [raw(v0), raw(v1), raw(v2), raw(v3), raw(v4), raw(v5)],
969            g: [raw(g0), raw(g1), raw(g2), raw(g3), raw(g4), raw(g5)],
970        }
971    }
972}
973
974/// Raw [`Boxes`] columns for writes at disjoint bins from several threads.
975#[derive(Clone, Copy)]
976struct BoxPtrs {
977    v: [RowPtr<f64>; 6],
978    g: [RowPtr<f64>; 6],
979}
980
981impl BoxPtrs {
982    /// Boxes of the runs of slots `lo..hi` (one bin), from run `v0` of
983    /// eight and `g0` of four.
984    ///
985    /// # Safety
986    /// This thread wrote the slots, the runs are in range, and no other
987    /// thread writes them.
988    unsafe fn fill(self, slots: SlotPtrs, lo: usize, hi: usize, v0: usize, g0: usize) {
989        let (rx, ry, rz) = (slots.rx.ptr(), slots.ry.ptr(), slots.rz.ptr());
990        // Runs of four, each run of eight the union of two of them.
991        let mut last = ([0.0f64; 3], [0.0f64; 3]);
992        for (m, a) in (lo..hi).step_by(4).enumerate() {
993            let (mut l, mut h) = ([f64::INFINITY; 3], [f64::NEG_INFINITY; 3]);
994            for s in a..(a + 4).min(hi) {
995                let r = [*rx.add(s), *ry.add(s), *rz.add(s)];
996                for ax in 0..3 {
997                    l[ax] = l[ax].min(r[ax]);
998                    h[ax] = h[ax].max(r[ax]);
999                }
1000            }
1001            for ax in 0..3 {
1002                (*self.g[ax].at(g0 + m)).write(l[ax]);
1003                (*self.g[3 + ax].at(g0 + m)).write(h[ax]);
1004            }
1005            let odd = m % 2 == 1;
1006            if odd {
1007                for ax in 0..3 {
1008                    l[ax] = l[ax].min(last.0[ax]);
1009                    h[ax] = h[ax].max(last.1[ax]);
1010                }
1011            }
1012            if odd || a + 4 >= hi {
1013                for ax in 0..3 {
1014                    (*self.v[ax].at(v0 + m / 2)).write(l[ax]);
1015                    (*self.v[3 + ax].at(v0 + m / 2)).write(h[ax]);
1016                }
1017            }
1018            last = (l, h);
1019        }
1020    }
1021}
1022
1023static GRID_POOL: std::sync::Mutex<Option<GridBufs>> = std::sync::Mutex::new(None);
1024
1025fn take_grid_bufs() -> GridBufs {
1026    GRID_POOL
1027        .lock()
1028        .ok()
1029        .and_then(|mut slot| slot.take())
1030        .unwrap_or_default()
1031}
1032
1033fn give_grid_bufs(bufs: GridBufs) {
1034    const MAX_KEEP: usize = 1 << 20;
1035    if bufs.coords.x.capacity() > MAX_KEEP || bufs.offsets.capacity() > MAX_KEEP {
1036        return;
1037    }
1038    if let Ok(mut slot) = GRID_POOL.lock() {
1039        if slot.is_none() {
1040            *slot = Some(bufs);
1041        }
1042    }
1043}
1044
1045/// Active atoms in bin order. The occupants of bin `c` are the slots
1046/// `offsets[c]..offsets[c + 1]`, ordered inside the bin by [`Keys`] and
1047/// then by atom index, so eight slots in a row are a compact block
1048/// whatever the input order.
1049struct Grid {
1050    n: [i32; 3],
1051    widths: [f64; 3],
1052    offsets: Vec<usize>,
1053    /// Cartesian corner of every bin, `H (ix/nx, iy/ny, iz/nz) + origin`.
1054    corners: Vec<[f64; 3]>,
1055    coords: Coords,
1056    /// Largest |component| of the folded and of the relative positions.
1057    max_abs: f64,
1058    max_rel: f64,
1059    /// The fold, the counts, and the slot order, kept for the next grid.
1060    fold: FoldCols,
1061    tally: Vec<u32>,
1062    order: Vec<u32>,
1063    boxes: Boxes,
1064}
1065
1066impl Drop for Grid {
1067    fn drop(&mut self) {
1068        give_grid_bufs(GridBufs {
1069            offsets: std::mem::take(&mut self.offsets),
1070            corners: std::mem::take(&mut self.corners),
1071            coords: std::mem::take(&mut self.coords),
1072            fold: std::mem::take(&mut self.fold),
1073            tally: std::mem::take(&mut self.tally),
1074            order: std::mem::take(&mut self.order),
1075            boxes: std::mem::take(&mut self.boxes),
1076        });
1077    }
1078}
1079
1080/// One atom in a thread's staging area: folded position, sub-cell inside
1081/// its bin, and atom index.
1082#[cfg(feature = "parallel")]
1083#[derive(Clone, Copy, Default)]
1084struct Staged {
1085    p: [f64; 3],
1086    sub: u32,
1087    atom: u32,
1088}
1089
1090/// Every active atom's folded position and key, between the passes.
1091#[derive(Default)]
1092struct FoldCols {
1093    x: Vec<f64>,
1094    y: Vec<f64>,
1095    z: Vec<f64>,
1096    key: Vec<u32>,
1097}
1098
1099impl FoldCols {
1100    fn clear_for(&mut self, n: usize) {
1101        for v in [&mut self.x, &mut self.y, &mut self.z] {
1102            v.clear();
1103            v.reserve(n);
1104        }
1105        self.key.clear();
1106        self.key.reserve(n);
1107    }
1108
1109    fn ptrs(&mut self) -> FoldPtrs {
1110        let raw = |v: &mut Vec<f64>| RowPtr(v.as_mut_ptr() as *mut std::mem::MaybeUninit<f64>);
1111        FoldPtrs {
1112            x: raw(&mut self.x),
1113            y: raw(&mut self.y),
1114            z: raw(&mut self.z),
1115            key: RowPtr(self.key.as_mut_ptr() as *mut std::mem::MaybeUninit<u32>),
1116        }
1117    }
1118}
1119
1120/// Raw [`FoldCols`] for writes at disjoint atoms from several threads.
1121#[derive(Clone, Copy)]
1122struct FoldPtrs {
1123    x: RowPtr<f64>,
1124    y: RowPtr<f64>,
1125    z: RowPtr<f64>,
1126    key: RowPtr<u32>,
1127}
1128
1129impl FoldPtrs {
1130    /// # Safety
1131    /// `k` is in range and no other thread touches it.
1132    #[inline(always)]
1133    unsafe fn put(self, k: usize, p: [f64; 3], key: usize) {
1134        (*self.x.at(k)).write(p[0]);
1135        (*self.y.at(k)).write(p[1]);
1136        (*self.z.at(k)).write(p[2]);
1137        (*self.key.at(k)).write(key as u32);
1138    }
1139
1140    /// # Safety
1141    /// Atom `k` is written.
1142    #[inline(always)]
1143    unsafe fn get(self, k: usize) -> ([f64; 3], usize) {
1144        (
1145            [
1146                (*self.x.at(k)).assume_init(),
1147                (*self.y.at(k)).assume_init(),
1148                (*self.z.at(k)).assume_init(),
1149            ],
1150            (*self.key.at(k)).assume_init() as usize,
1151        )
1152    }
1153}
1154
1155/// Sort keys of the slots: the bin, then a Morton code of the atom's
1156/// sub-cell, `sub` per axis (a power of two), so a run of slots inside a
1157/// bin covers a compact part of it.
1158#[derive(Clone, Copy)]
1159struct Keys {
1160    n: [i32; 3],
1161    sub: i32,
1162}
1163
1164impl Keys {
1165    /// Sub-cells per axis for `n_act` atoms in `ncell` bins: about one
1166    /// atom per sub-cell, so eight slots in a row are a compact block, and
1167    /// never more keys than atoms.
1168    fn sub_for(n_act: usize, ncell: usize) -> i32 {
1169        let per_bin = n_act / ncell.max(1);
1170        if per_bin >= 48 {
1171            4
1172        } else if per_bin >= 6 {
1173            2
1174        } else {
1175            1
1176        }
1177    }
1178
1179    /// Sub-cells per axis over the whole box.
1180    fn fine(self) -> [i32; 3] {
1181        [
1182            self.n[0] * self.sub,
1183            self.n[1] * self.sub,
1184            self.n[2] * self.sub,
1185        ]
1186    }
1187
1188    /// Keys per bin.
1189    fn per_bin(self) -> usize {
1190        (self.sub * self.sub * self.sub) as usize
1191    }
1192
1193    /// Key of the sub-cell `b`: the bin's flat index times
1194    /// [`Keys::per_bin`], plus the Morton code inside the bin.
1195    #[inline(always)]
1196    fn key(self, b: [i32; 3]) -> usize {
1197        let shift = self.sub.trailing_zeros();
1198        let low = self.sub - 1;
1199        let coarse = bins::flat_cell([b[0] >> shift, b[1] >> shift, b[2] >> shift], self.n);
1200        // Interleave the low bits of the three axes, x lowest.
1201        let spread = |v: i32| {
1202            let v = (v & low) as usize;
1203            (v & 1) | ((v & 2) << 2) | ((v & 4) << 4)
1204        };
1205        let m = spread(b[0]) | (spread(b[1]) << 1) | (spread(b[2]) << 2);
1206        coarse * self.per_bin() + m
1207    }
1208}
1209
1210/// Fold atoms `lo..hi` into `fold` and count each key (or each bin,
1211/// with `by_bin`), exactly as [`bins::fold_point`]: unmasked atoms go
1212/// eight at a time on AVX-512, with the same operations in the same order.
1213#[allow(clippy::too_many_arguments)]
1214fn fold_range(
1215    simbox: &Cell,
1216    xyz: &[[f64; 3]],
1217    active: Option<&[usize]>,
1218    keys: Keys,
1219    by_bin: bool,
1220    path: Path,
1221    lo: usize,
1222    hi: usize,
1223    fold: FoldPtrs,
1224    count: &mut [u32],
1225) {
1226    let shift = if by_bin {
1227        keys.per_bin().trailing_zeros()
1228    } else {
1229        0
1230    };
1231    #[allow(unused_mut)]
1232    let mut slot = lo;
1233    #[cfg(not(all(target_arch = "x86_64", linkcell_avx512)))]
1234    let _ = path;
1235    #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
1236    if active.is_none() && path == Path::Avx512 {
1237        // Safety: AVX-512F was detected, `lo..hi` indexes `xyz`, and this
1238        // caller owns `fold` over that range.
1239        slot = unsafe { fold_avx512(simbox, xyz, keys, shift, lo, hi, fold, count) };
1240    }
1241    let fine = keys.fine();
1242    for k in slot..hi {
1243        let i = active.map_or(k, |a| a[k]);
1244        let (q, b) = bins::fold_point(simbox, xyz[i], fine);
1245        let key = keys.key(b);
1246        count[key >> shift] += 1;
1247        // Safety: the caller owns `fold` over `lo..hi`.
1248        unsafe { fold.put(k, q, key) };
1249    }
1250}
1251
1252/// [`fold_range`] for eight unmasked atoms at a time, with [`Keys::key`]
1253/// in registers; returns the first slot left for the scalar fold.
1254///
1255/// # Safety
1256/// AVX-512F is available, `lo..hi` indexes `xyz`, and the caller owns
1257/// `fold` over that range.
1258#[allow(clippy::incompatible_msrv, clippy::too_many_arguments)]
1259#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
1260#[target_feature(enable = "avx512f")]
1261unsafe fn fold_avx512(
1262    simbox: &Cell,
1263    xyz: &[[f64; 3]],
1264    keys: Keys,
1265    shift: u32,
1266    lo: usize,
1267    hi: usize,
1268    fold: FoldPtrs,
1269    count: &mut [u32],
1270) -> usize {
1271    use std::arch::x86_64::{
1272        __m256i, _mm256_add_epi32, _mm256_and_si256, _mm256_mullo_epi32, _mm256_or_si256,
1273        _mm256_set1_epi32, _mm256_sll_epi32, _mm256_slli_epi32, _mm256_srl_epi32,
1274        _mm256_storeu_si256, _mm512_storeu_pd, _mm_cvtsi32_si128,
1275    };
1276    let f = bins::Fold8::new(simbox, keys.fine());
1277    let flat = xyz.as_ptr() as *const f64;
1278    let bits = keys.sub.trailing_zeros() as i32;
1279    let down = _mm_cvtsi32_si128(bits);
1280    let up = _mm_cvtsi32_si128(3 * bits);
1281    let (nx, ny) = (_mm256_set1_epi32(keys.n[0]), _mm256_set1_epi32(keys.n[1]));
1282    let low = _mm256_set1_epi32(keys.sub - 1);
1283    let (one, two, four) = (
1284        _mm256_set1_epi32(1),
1285        _mm256_set1_epi32(2),
1286        _mm256_set1_epi32(4),
1287    );
1288    let spread = |v: __m256i| {
1289        let v = _mm256_and_si256(v, low);
1290        _mm256_or_si256(
1291            _mm256_and_si256(v, one),
1292            _mm256_or_si256(
1293                _mm256_slli_epi32::<2>(_mm256_and_si256(v, two)),
1294                _mm256_slli_epi32::<4>(_mm256_and_si256(v, four)),
1295            ),
1296        )
1297    };
1298    let mut lane = [0u32; 8];
1299    let mut k = lo;
1300    while k + 8 <= hi {
1301        let (_, p, b) = bins::fold8_regs(&f, flat.add(3 * k));
1302        let coarse = _mm256_add_epi32(
1303            _mm256_mullo_epi32(
1304                _mm256_add_epi32(
1305                    _mm256_mullo_epi32(_mm256_srl_epi32(b[2], down), ny),
1306                    _mm256_srl_epi32(b[1], down),
1307                ),
1308                nx,
1309            ),
1310            _mm256_srl_epi32(b[0], down),
1311        );
1312        let m = _mm256_or_si256(
1313            spread(b[0]),
1314            _mm256_or_si256(
1315                _mm256_slli_epi32::<1>(spread(b[1])),
1316                _mm256_slli_epi32::<2>(spread(b[2])),
1317            ),
1318        );
1319        let key = _mm256_or_si256(_mm256_sll_epi32(coarse, up), m);
1320        _mm512_storeu_pd(fold.x.ptr().add(k), p[0]);
1321        _mm512_storeu_pd(fold.y.ptr().add(k), p[1]);
1322        _mm512_storeu_pd(fold.z.ptr().add(k), p[2]);
1323        _mm256_storeu_si256(fold.key.ptr().add(k) as *mut _, key);
1324        _mm256_storeu_si256(lane.as_mut_ptr() as *mut _, key);
1325        for &c in &lane {
1326            count[(c >> shift) as usize] += 1;
1327        }
1328        k += 8;
1329    }
1330    k
1331}
1332
1333/// Raw slot columns for writes at disjoint slots from several threads.
1334#[derive(Clone, Copy)]
1335struct SlotPtrs {
1336    x: RowPtr<f64>,
1337    y: RowPtr<f64>,
1338    z: RowPtr<f64>,
1339    rx: RowPtr<f64>,
1340    ry: RowPtr<f64>,
1341    rz: RowPtr<f64>,
1342    r2: RowPtr<f64>,
1343    id: RowPtr<u32>,
1344}
1345
1346impl SlotPtrs {
1347    fn of(c: &mut Coords) -> Self {
1348        let raw = |v: &mut Vec<f64>| RowPtr(v.as_mut_ptr() as *mut std::mem::MaybeUninit<f64>);
1349        SlotPtrs {
1350            x: raw(&mut c.x),
1351            y: raw(&mut c.y),
1352            z: raw(&mut c.z),
1353            rx: raw(&mut c.rx),
1354            ry: raw(&mut c.ry),
1355            rz: raw(&mut c.rz),
1356            r2: raw(&mut c.r2),
1357            id: RowPtr(c.id.as_mut_ptr() as *mut std::mem::MaybeUninit<u32>),
1358        }
1359    }
1360
1361    /// Write atom `i` at `slot`; returns the largest |component| of the
1362    /// folded and of the relative position.
1363    ///
1364    /// # Safety
1365    /// `slot` is in range and no other thread writes it.
1366    #[inline(always)]
1367    unsafe fn put(self, slot: usize, i: usize, p: [f64; 3], o: [f64; 3]) -> (f64, f64) {
1368        let (rx, ry, rz) = (p[0] - o[0], p[1] - o[1], p[2] - o[2]);
1369        (*self.x.at(slot)).write(p[0]);
1370        (*self.y.at(slot)).write(p[1]);
1371        (*self.z.at(slot)).write(p[2]);
1372        (*self.rx.at(slot)).write(rx);
1373        (*self.ry.at(slot)).write(ry);
1374        (*self.rz.at(slot)).write(rz);
1375        (*self.r2.at(slot)).write(rx * rx + ry * ry + rz * rz);
1376        (*self.id.at(slot)).write(i as u32);
1377        (
1378            p[0].abs().max(p[1].abs()).max(p[2].abs()),
1379            rx.abs().max(ry.abs()).max(rz.abs()),
1380        )
1381    }
1382}
1383
1384impl Grid {
1385    /// Fold every active atom, count each key, scan, then scatter into
1386    /// the slot columns. With several threads each thread folds one block
1387    /// of atoms (a block distribution) and groups it by bin in its own
1388    /// staging area; then each thread owns a run of bins, reads them from
1389    /// every staging area in thread order, sorts them by sub-cell, and
1390    /// writes its run of slots alone. The order is one thread's.
1391    fn build(
1392        xyz: &[[f64; 3]],
1393        simbox: &Cell,
1394        active: Option<&[usize]>,
1395        n: [i32; 3],
1396        threads: usize,
1397        path: Path,
1398    ) -> Grid {
1399        let ncell = (n[0] as usize) * (n[1] as usize) * (n[2] as usize);
1400        let n_act = active.map_or(xyz.len(), |a| a.len());
1401        let atom = |k: usize| active.map_or(k, |a| a[k]);
1402        // Buffers come from the last grid and are not zeroed: the fold
1403        // writes every atom, the corner pass every bin, and the scatter
1404        // every slot, before any of them is read.
1405        let GridBufs {
1406            mut offsets,
1407            mut corners,
1408            mut coords,
1409            mut fold,
1410            mut tally,
1411            mut order,
1412            mut boxes,
1413        } = take_grid_bufs();
1414        offsets.clear();
1415        offsets.reserve(ncell + 1);
1416        corners.clear();
1417        corners.reserve(ncell);
1418        coords.clear_for(n_act);
1419        // The fold is read only through `fp`; its vectors stay empty.
1420        fold.clear_for(n_act);
1421        let fp = fold.ptrs();
1422        let cp = RowPtr(corners.as_mut_ptr() as *mut std::mem::MaybeUninit<[f64; 3]>);
1423        let slots = SlotPtrs::of(&mut coords);
1424        // Corners of bins `lo..hi`, stepping the bin indices rather than
1425        // dividing the flat index.
1426        let corners_of = |lo: usize, hi: usize| {
1427            let (nx, ny) = (n[0] as usize, n[1] as usize);
1428            let (mut ix, mut iy, mut iz) = (lo % nx, (lo / nx) % ny, lo / (nx * ny));
1429            for c in lo..hi {
1430                let corner = simbox.cartesian([
1431                    f64::from(ix as i32) / f64::from(n[0]),
1432                    f64::from(iy as i32) / f64::from(n[1]),
1433                    f64::from(iz as i32) / f64::from(n[2]),
1434                ]);
1435                // Safety: the caller owns `corners` over `lo..hi`.
1436                unsafe { (*cp.at(c)).write(corner) };
1437                ix += 1;
1438                if ix == nx {
1439                    ix = 0;
1440                    iy += 1;
1441                    if iy == ny {
1442                        iy = 0;
1443                        iz += 1;
1444                    }
1445                }
1446            }
1447        };
1448        let (mut max_abs, mut max_rel) = (0.0f64, 0.0f64);
1449        let keys = Keys {
1450            n,
1451            sub: Keys::sub_for(n_act, ncell),
1452        };
1453        let per = keys.per_bin();
1454        let nkey = ncell * per;
1455        let cull = path != Path::Scalar && n_act >= 8 * CULL_RUNS * ncell && !no_cull();
1456        #[cfg(feature = "parallel")]
1457        let parallel = threads > 1;
1458        #[cfg(not(feature = "parallel"))]
1459        let parallel = {
1460            let _ = threads;
1461            false
1462        };
1463        if parallel {
1464            #[cfg(feature = "parallel")]
1465            {
1466                let p = crate::pool_width().max(1);
1467                let block = |k: usize, len: usize| (k * len / p, (k + 1) * len / p);
1468                let shift = per.trailing_zeros();
1469                // Pass 1: each thread folds a block of atoms, groups it by bin
1470                // in its own staging area (atom order inside a bin), and folds
1471                // a block of bin corners.
1472                let staged: Vec<(Vec<Staged>, Vec<usize>)> = rayon::broadcast(|ctx| {
1473                    let _timer = crate::pop::JobTimer::new();
1474                    let k = ctx.index();
1475                    let (lo, hi) = block(k, n_act);
1476                    let mut count = vec![0u32; ncell];
1477                    // Atom blocks are disjoint, so each thread owns its range.
1478                    fold_range(
1479                        simbox, xyz, active, keys, true, path, lo, hi, fp, &mut count,
1480                    );
1481                    let mut first = Vec::with_capacity(ncell + 1);
1482                    let mut at = 0usize;
1483                    for &c in &count {
1484                        first.push(at);
1485                        at += c as usize;
1486                    }
1487                    first.push(at);
1488                    let mut next = first.clone();
1489                    let mut stage = vec![Staged::default(); hi - lo];
1490                    for slot in lo..hi {
1491                        // Safety: the fold above wrote this thread's atoms.
1492                        let (p, key) = unsafe { fp.get(slot) };
1493                        let c = key >> shift;
1494                        stage[next[c]] = Staged {
1495                            p,
1496                            sub: (key & (per - 1)) as u32,
1497                            atom: atom(slot) as u32,
1498                        };
1499                        next[c] += 1;
1500                    }
1501                    let (clo, chi) = block(k, ncell);
1502                    // Corner blocks are disjoint.
1503                    corners_of(clo, chi);
1504                    (stage, first)
1505                });
1506                // Safety: pass 1 wrote every corner; the grid keeps no fold.
1507                unsafe { corners.set_len(ncell) };
1508                // Scan: bin `c` starts at `offsets[c]`.
1509                let mut at = 0usize;
1510                for c in 0..ncell {
1511                    offsets.push(at);
1512                    for (_, first) in &staged {
1513                        at += first[c + 1] - first[c];
1514                    }
1515                }
1516                offsets.push(at);
1517                boxes.starts(&offsets, cull);
1518                let bp = boxes.ptrs();
1519                let (vstart, gstart) = (&boxes.vstart, &boxes.gstart);
1520                // Pass 2: each thread owns a run of bins, balanced by atoms,
1521                // reads their atoms from every staging area in thread order
1522                // (so in atom order), sorts each bin by sub-cell with a stable
1523                // count, and writes that run of slots, and their boxes,
1524                // alone: the order is one thread's, and no cache line is
1525                // written by two threads.
1526                let ranges = cell_ranges(&offsets, p);
1527                let (staged, corners, offsets, ranges) = (&staged, &corners, &offsets, &ranges);
1528                let maxima: Vec<(f64, f64)> = rayon::broadcast(|ctx| {
1529                    let _timer = crate::pop::JobTimer::new();
1530                    let (mut ma, mut mr) = (0.0f64, 0.0f64);
1531                    let Some(&(clo, chi)) = ranges.get(ctx.index()) else {
1532                        return (ma, mr);
1533                    };
1534                    let mut bucket = vec![0usize; per + 1];
1535                    for c in clo..chi {
1536                        bucket.iter_mut().for_each(|b| *b = 0);
1537                        for (stage, first) in staged {
1538                            for e in &stage[first[c]..first[c + 1]] {
1539                                bucket[e.sub as usize + 1] += 1;
1540                            }
1541                        }
1542                        let mut acc = offsets[c];
1543                        for b in bucket.iter_mut() {
1544                            acc += *b;
1545                            *b = acc;
1546                        }
1547                        for (stage, first) in staged {
1548                            for e in &stage[first[c]..first[c + 1]] {
1549                                let dest = bucket[e.sub as usize];
1550                                bucket[e.sub as usize] += 1;
1551                                // Safety: bin `c`, and so its slots, belongs to
1552                                // this thread alone.
1553                                let (a, r) =
1554                                    unsafe { slots.put(dest, e.atom as usize, e.p, corners[c]) };
1555                                ma = ma.max(a);
1556                                mr = mr.max(r);
1557                            }
1558                        }
1559                        if cull {
1560                            // Safety: this thread wrote bin `c` and owns its runs.
1561                            unsafe {
1562                                bp.fill(slots, offsets[c], offsets[c + 1], vstart[c], gstart[c])
1563                            };
1564                        }
1565                    }
1566                    (ma, mr)
1567                });
1568                for (a, r) in maxima {
1569                    max_abs = max_abs.max(a);
1570                    max_rel = max_rel.max(r);
1571                }
1572            }
1573        } else {
1574            let _timer = crate::pop::JobTimer::new();
1575            tally.clear();
1576            tally.resize(nkey, 0);
1577            fold_range(
1578                simbox, xyz, active, keys, false, path, 0, n_act, fp, &mut tally,
1579            );
1580            corners_of(0, ncell);
1581            // Safety: `corners_of` wrote every corner.
1582            unsafe { corners.set_len(ncell) };
1583            // `tally` becomes the next free slot of each key.
1584            let mut at = 0usize;
1585            for bin in tally.chunks_exact_mut(per) {
1586                offsets.push(at);
1587                for t in bin {
1588                    let count = *t as usize;
1589                    *t = at as u32;
1590                    at += count;
1591                }
1592            }
1593            offsets.push(at);
1594            // Sort atom numbers by key, then fill the slot columns in slot
1595            // order: the random accesses are reads of the fold, and every
1596            // column is written front to back.
1597            order.clear();
1598            order.reserve(n_act);
1599            let op = order.as_mut_ptr();
1600            for k in 0..n_act {
1601                // Safety: the fold wrote atom `k`; `tally` keeps each
1602                // destination inside `0..n_act`.
1603                unsafe {
1604                    let key = (*fp.key.at(k)).assume_init() as usize;
1605                    let dest = tally[key] as usize;
1606                    tally[key] += 1;
1607                    op.add(dest).write(k as u32);
1608                }
1609            }
1610            boxes.starts(&offsets, cull);
1611            let bp = boxes.ptrs();
1612            for c in 0..ncell {
1613                let corner = corners[c];
1614                for dest in offsets[c]..offsets[c + 1] {
1615                    // Safety: every slot below `n_act` holds an atom number,
1616                    // the fold wrote that atom, and one thread writes.
1617                    let (a, r) = unsafe {
1618                        let k = *op.add(dest) as usize;
1619                        let (p, _) = fp.get(k);
1620                        slots.put(dest, atom(k), p, corner)
1621                    };
1622                    max_abs = max_abs.max(a);
1623                    max_rel = max_rel.max(r);
1624                }
1625                if cull {
1626                    // Safety: one thread, and bin `c` is written.
1627                    unsafe {
1628                        bp.fill(
1629                            slots,
1630                            offsets[c],
1631                            offsets[c + 1],
1632                            boxes.vstart[c],
1633                            boxes.gstart[c],
1634                        )
1635                    };
1636                }
1637            }
1638        }
1639        // Safety: the scatter wrote every slot of every column once.
1640        unsafe { coords.set_len(n_act) };
1641        Grid {
1642            n,
1643            widths: simbox.widths(),
1644            offsets,
1645            corners,
1646            coords,
1647            max_abs,
1648            max_rel,
1649            fold,
1650            tally,
1651            order,
1652            boxes,
1653        }
1654    }
1655
1656    fn atoms(&self) -> usize {
1657        self.coords.id.len()
1658    }
1659
1660    /// No bins and no atoms: every search on it is empty.
1661    fn empty() -> Grid {
1662        Grid {
1663            n: [1, 1, 1],
1664            widths: [0.0; 3],
1665            offsets: vec![0],
1666            corners: Vec::new(),
1667            coords: Coords::default(),
1668            max_abs: 0.0,
1669            max_rel: 0.0,
1670            fold: FoldCols::default(),
1671            tally: Vec::new(),
1672            order: Vec::new(),
1673            boxes: Boxes {
1674                vstart: vec![0],
1675                gstart: vec![0],
1676                ..Boxes::default()
1677            },
1678        }
1679    }
1680}
1681
1682/// Bound on the difference between the expanded squared distance
1683/// `|r_q|^2 - 2 r_q . r_p' + |r_p'|^2` and the direct one
1684/// `|q - (p - S)|^2`, both in double precision.
1685///
1686/// Each value is a short sum of terms no larger than the square of the
1687/// largest magnitude in it: absolute coordinates `A`, shifts `S`,
1688/// relative coordinates `R`, and block offsets `D`, per component. Every
1689/// rounding is at most `2^-53` of such a term, and there are fewer than
1690/// 32 of them per value; `192 = 64 * 3` covers both values and the
1691/// three components. A lane within this of `cutoff^2` is decided by the
1692/// direct formula, so the expanded form never changes a row.
1693fn expanded_margin(grid: &Grid, partners: &PartnerList, cutoff: f64) -> f64 {
1694    let (a, r) = (grid.max_abs, grid.max_rel);
1695    let (s, d) = (partners.s_max, partners.d_max);
1696    let span = 2.0 * a + s + 2.0 * r + d + cutoff;
1697    192.0 * f64::EPSILON * 0.5 * span * span
1698}
1699
1700/// `true` for exactly one of `(d)` and `(-d)`. The zero offset is the home cell.
1701fn keep_dir(dx: i32, dy: i32, dz: i32) -> bool {
1702    if dx != 0 {
1703        return dx > 0;
1704    }
1705    if dy != 0 {
1706        return dy > 0;
1707    }
1708    if dz != 0 {
1709        return dz > 0;
1710    }
1711    false
1712}
1713
1714fn uniform_reach(nbin: [i32; 3], widths: [f64; 3], cut2: f64, max_reach: i32) -> [i32; 3] {
1715    let mut reach = [1i32; 3];
1716    loop {
1717        let mut grew = false;
1718        for a in 0..3 {
1719            let n = nbin[a];
1720            let w = widths[a];
1721            let nf = f64::from(n);
1722            let s_hi = (1.0 - 1.0e-12) / nf;
1723            let gap = bins::certify(
1724                axis_gap(0.0, 0, reach[a], n, w).min(axis_gap(s_hi, 0, reach[a], n, w)),
1725            );
1726            let bound = if gap > 0.0 && gap.is_finite() {
1727                gap * gap
1728            } else {
1729                0.0
1730            };
1731            if bound < cut2 && reach[a] < max_reach {
1732                reach[a] += 1;
1733                grew = true;
1734            }
1735        }
1736        if !grew {
1737            break;
1738        }
1739    }
1740    reach
1741}
1742
1743struct Walk<'a> {
1744    grid: &'a Grid,
1745    cut2: f64,
1746    /// [`expanded_margin`] of this search.
1747    #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1748    margin: f64,
1749    partners: &'a PartnerList,
1750    /// [`Path`] chosen by the caller. Workers read this and do not call
1751    /// [`crate::simd::select`].
1752    path: Path,
1753}
1754
1755#[derive(Clone, Copy)]
1756struct Block {
1757    i_lo: usize,
1758    i_hi: usize,
1759    j_lo: usize,
1760    j_hi: usize,
1761    shift_s: [i32; 3],
1762    shift: [f64; 3],
1763    /// [`Partner::delta`]; zero for the home cell.
1764    #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1765    delta: [f64; 3],
1766    /// Home cell: source `s` only sees occupants `s + 1 ..`.
1767    tri: bool,
1768    /// [`Boxes`] of the target bin's first run of eight and the source
1769    /// bin's first run of four.
1770    #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1771    jv: usize,
1772    #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1773    ig: usize,
1774}
1775
1776/// Expected pairs where the walk splits across threads.
1777///
1778/// On this 8-core host, with the AVX-512 tile, one thread is faster at
1779/// about 1 thousand pairs (216 atoms, 3.5 Ă…) and eight threads are faster
1780/// from about 2 thousand pairs (512 atoms, 2.4 thousand pairs). Waking
1781/// the pool below that loses to a serial cell list, and on the smallest
1782/// cells it also loses to vesin.
1783#[cfg(feature = "parallel")]
1784const PARALLEL_PAIRS: usize = 2_000;
1785
1786/// Active atoms from which a split walk also builds its bins on several
1787/// threads. The fold then wakes the workers the search uses next; at 1024
1788/// atoms in an 18 Ă… cube on this 8-core host the two builds tie, and at
1789/// 4096 the threaded one is faster.
1790const PARALLEL_GRID: usize = 1_024;
1791
1792/// The walk's thresholds and paths as values an autotuner can set (the
1793/// `tune` feature, through `lc_tune_set`); otherwise each is its
1794/// constant. Every one is read once per call, outside the tiles.
1795pub(crate) mod knobs {
1796    // `lc_tune_set` keys.
1797    #[cfg(feature = "tune")]
1798    pub(crate) const SPLIT_PAIRS: usize = 0;
1799    #[cfg(feature = "tune")]
1800    pub(crate) const GRID_ATOMS: usize = 1;
1801    #[cfg(feature = "tune")]
1802    pub(crate) const FUSED: usize = 2;
1803    #[cfg(feature = "tune")]
1804    pub(crate) const CHUNKS: usize = 3;
1805    #[cfg(feature = "tune")]
1806    pub(crate) const AHEAD_FROM: usize = 4;
1807
1808    #[cfg(feature = "tune")]
1809    pub(crate) static VALUES: [std::sync::atomic::AtomicUsize; 5] = [
1810        std::sync::atomic::AtomicUsize::new(super::DEFAULT_SPLIT_PAIRS),
1811        std::sync::atomic::AtomicUsize::new(super::PARALLEL_GRID),
1812        std::sync::atomic::AtomicUsize::new(1),
1813        std::sync::atomic::AtomicUsize::new(1),
1814        std::sync::atomic::AtomicUsize::new(super::AHEAD_FROM),
1815    ];
1816
1817    #[cfg(feature = "tune")]
1818    fn get(key: usize) -> usize {
1819        VALUES[key].load(std::sync::atomic::Ordering::Relaxed)
1820    }
1821
1822    /// Expected pairs where the walk splits across threads.
1823    #[cfg(feature = "parallel")]
1824    pub(crate) fn split_pairs() -> usize {
1825        #[cfg(feature = "tune")]
1826        return get(SPLIT_PAIRS);
1827        #[cfg(not(feature = "tune"))]
1828        super::PARALLEL_PAIRS
1829    }
1830
1831    /// Active atoms from which a split walk builds its bins on several threads.
1832    pub(crate) fn grid_atoms() -> usize {
1833        #[cfg(feature = "tune")]
1834        return get(GRID_ATOMS);
1835        #[cfg(not(feature = "tune"))]
1836        super::PARALLEL_GRID
1837    }
1838
1839    /// One thread writes a full list straight from the tile.
1840    #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1841    pub(crate) fn fused() -> bool {
1842        #[cfg(feature = "tune")]
1843        return get(FUSED) != 0;
1844        #[cfg(not(feature = "tune"))]
1845        true
1846    }
1847
1848    /// Bin ranges per thread in a split search.
1849    #[cfg_attr(not(feature = "parallel"), allow(dead_code))]
1850    pub(crate) fn chunks() -> usize {
1851        #[cfg(feature = "tune")]
1852        return get(CHUNKS).max(1);
1853        #[cfg(not(feature = "tune"))]
1854        1
1855    }
1856
1857    /// Output bytes per thread from which the writers prefetch ahead.
1858    pub(crate) fn ahead_from() -> usize {
1859        #[cfg(feature = "tune")]
1860        return get(AHEAD_FROM);
1861        #[cfg(not(feature = "tune"))]
1862        super::AHEAD_FROM
1863    }
1864}
1865
1866/// The split knob's default: [`PARALLEL_PAIRS`], or never without `parallel`.
1867#[cfg(feature = "tune")]
1868#[cfg(feature = "parallel")]
1869const DEFAULT_SPLIT_PAIRS: usize = PARALLEL_PAIRS;
1870#[cfg(feature = "tune")]
1871#[cfg(not(feature = "parallel"))]
1872const DEFAULT_SPLIT_PAIRS: usize = usize::MAX;
1873
1874/// Hits for the whole chunk. The distance loop appends here, then one
1875/// pass writes the rows. Runs share a shift so the inner loop does not.
1876struct Scratch {
1877    atom: Vec<u32>,
1878    js: Vec<u32>,
1879    d2: Vec<f64>,
1880    run_shift: Vec<[i32; 3]>,
1881    run_end: Vec<usize>,
1882}
1883
1884impl Scratch {
1885    fn new() -> Self {
1886        Self {
1887            atom: Vec::new(),
1888            js: Vec::new(),
1889            d2: Vec::new(),
1890            run_shift: Vec::new(),
1891            run_end: Vec::new(),
1892        }
1893    }
1894
1895    fn reserve_more(&mut self, extra: usize) {
1896        let need = self.js.len().saturating_add(extra);
1897        if self.js.capacity() < need {
1898            self.atom.reserve(extra);
1899            self.js.reserve(extra);
1900            self.d2.reserve(extra);
1901        }
1902    }
1903
1904    #[cfg_attr(not(target_arch = "x86_64"), allow(dead_code))]
1905    fn finish(&mut self, n: usize) {
1906        debug_assert!(n <= self.js.capacity());
1907        unsafe {
1908            self.atom.set_len(n);
1909            self.js.set_len(n);
1910            self.d2.set_len(n);
1911        }
1912    }
1913
1914    fn push(&mut self, atom: u32, j: u32, d2: f64) {
1915        self.atom.push(atom);
1916        self.js.push(j);
1917        self.d2.push(d2);
1918    }
1919
1920    fn note(&mut self, before: usize, shift: [i32; 3]) {
1921        let after = self.js.len();
1922        if after > before {
1923            self.run_shift.push(shift);
1924            self.run_end.push(after);
1925        }
1926    }
1927}
1928
1929/// Every hit of one search, by cell range. Nothing is a row yet: each
1930/// caller expands these once into its own layout.
1931pub(crate) struct Found {
1932    images: ImageOffsets,
1933    chunks: Vec<Scratch>,
1934    half: bool,
1935    /// [`Path`] of the search. The AVX-512 writers use the same path.
1936    #[cfg_attr(not(all(target_arch = "x86_64", linkcell_avx512)), allow(dead_code))]
1937    path: Path,
1938}
1939
1940impl Found {
1941    fn rows_of(&self, chunk: &Scratch) -> usize {
1942        if self.half {
1943            chunk.js.len()
1944        } else {
1945            chunk.js.len() * 2
1946        }
1947    }
1948
1949    /// Output rows over every chunk.
1950    pub(crate) fn rows(&self) -> usize {
1951        self.chunks.iter().map(|c| self.rows_of(c)).sum()
1952    }
1953
1954    fn offsets(&self) -> Vec<usize> {
1955        let mut off = Vec::with_capacity(self.chunks.len() + 1);
1956        off.push(0usize);
1957        for chunk in &self.chunks {
1958            off.push(off.last().copied().unwrap_or(0) + self.rows_of(chunk));
1959        }
1960        off
1961    }
1962
1963    fn into_pairs(self) -> Vec<Pair> {
1964        let total = self.rows();
1965        let mut found: Vec<Pair> = Vec::with_capacity(total);
1966        // Safety: `total` slots are allocated.
1967        unsafe {
1968            self.write_pairs(found.as_mut_ptr());
1969            found.set_len(total);
1970        }
1971        found
1972    }
1973
1974    /// Every row, written at `out`.
1975    ///
1976    /// # Safety
1977    /// `out` has room for [`Found::rows`] rows.
1978    unsafe fn write_pairs(&self, out: *mut Pair) {
1979        if self.images.0.is_some() {
1980            unsafe {
1981                self.write_rows(out, |i, j, shift, dist2| Pair {
1982                    i: i as usize,
1983                    j: j as usize,
1984                    shift,
1985                    dist2,
1986                });
1987            }
1988            return;
1989        }
1990        #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
1991        let words = if self.path == Path::Avx512 {
1992            RowWords::of_pair()
1993        } else {
1994            None
1995        };
1996        let base = RowPtr(out as *mut std::mem::MaybeUninit<Pair>);
1997        // Chunk `t` writes the rows `off[t]..off[t + 1]`, which partition
1998        // `0..rows`, and nothing reads them before every chunk is done.
1999        self.each_chunk(|t, off, chunk| {
2000            let rows = self.rows_of(chunk);
2001            if rows == 0 {
2002                return;
2003            }
2004            let dst = unsafe { std::slice::from_raw_parts_mut(base.at(off[t]), rows) };
2005            let ahead = ahead(rows, std::mem::size_of::<Pair>());
2006            #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2007            if let Some(words) = words {
2008                let at = dst.as_mut_ptr();
2009                // Safety: AVX-512 was detected for this search, and `dst`
2010                // holds the rows of `chunk`, two per hit on a full list and
2011                // one on a half list.
2012                unsafe {
2013                    match (self.half, ahead) {
2014                        (false, true) => write_full_avx512::<true>(at, chunk, &words),
2015                        (false, false) => write_full_avx512::<false>(at, chunk, &words),
2016                        (true, true) => write_half_avx512::<true>(at, chunk, &words),
2017                        (true, false) => write_half_avx512::<false>(at, chunk, &words),
2018                    }
2019                };
2020                return;
2021            }
2022            if self.half {
2023                write_half(
2024                    dst,
2025                    &chunk.atom,
2026                    &chunk.js,
2027                    &chunk.d2,
2028                    &chunk.run_shift,
2029                    &chunk.run_end,
2030                    ahead,
2031                );
2032                return;
2033            }
2034            write_full(
2035                dst,
2036                &chunk.atom,
2037                &chunk.js,
2038                &chunk.d2,
2039                &chunk.run_shift,
2040                &chunk.run_end,
2041                ahead,
2042            );
2043        });
2044    }
2045
2046    /// Clear `out`, then write every row into its four columns.
2047    pub(crate) fn fill_columns(&self, out: &mut PairColumns) {
2048        let total = self.rows();
2049        out.i.clear();
2050        out.j.clear();
2051        out.shift.clear();
2052        out.dist2.clear();
2053        out.i.reserve(total);
2054        out.j.reserve(total);
2055        out.shift.reserve(total);
2056        out.dist2.reserve(total);
2057        // Safety: each column has room for `total` rows.
2058        unsafe {
2059            self.write_columns(
2060                out.i.as_mut_ptr(),
2061                out.j.as_mut_ptr(),
2062                out.shift.as_mut_ptr() as *mut i32,
2063                out.dist2.as_mut_ptr(),
2064            );
2065            out.i.set_len(total);
2066            out.j.set_len(total);
2067            out.shift.set_len(total);
2068            out.dist2.set_len(total);
2069        }
2070    }
2071
2072    /// # Safety
2073    /// `i`, `j`, and `d2` are writable for [`Found::rows`] values and
2074    /// `shift` for three times that.
2075    pub(crate) unsafe fn write_columns(
2076        &self,
2077        i: *mut i32,
2078        j: *mut i32,
2079        shift: *mut i32,
2080        d2: *mut f64,
2081    ) {
2082        let cols = ColumnPtrs {
2083            i: RowPtr(i as *mut std::mem::MaybeUninit<i32>),
2084            j: RowPtr(j as *mut std::mem::MaybeUninit<i32>),
2085            shift: RowPtr(shift as *mut std::mem::MaybeUninit<i32>),
2086            d2: RowPtr(d2 as *mut std::mem::MaybeUninit<f64>),
2087        };
2088        self.each_chunk(|t, off, chunk| {
2089            let rows = self.rows_of(chunk);
2090            if rows == 0 {
2091                return;
2092            }
2093            let at = off[t];
2094            let (ci, cj, cs, cd) = unsafe {
2095                (
2096                    std::slice::from_raw_parts_mut(cols.i.at(at), rows),
2097                    std::slice::from_raw_parts_mut(cols.j.at(at), rows),
2098                    std::slice::from_raw_parts_mut(cols.shift.at(3 * at), 3 * rows),
2099                    std::slice::from_raw_parts_mut(cols.d2.at(at), rows),
2100                )
2101            };
2102            let ahead = ahead(rows, COLUMN_BYTES);
2103            #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2104            if self.path == Path::Avx512 {
2105                // Safety: AVX-512 was detected, and each column holds the
2106                // rows of `chunk`, two per hit on a full list and one on a
2107                // half list (three values per row of shift).
2108                unsafe {
2109                    match (self.half, ahead) {
2110                        (false, true) => write_columns_avx512::<true>(ci, cj, cs, cd, chunk),
2111                        (false, false) => write_columns_avx512::<false>(ci, cj, cs, cd, chunk),
2112                        (true, true) => write_half_columns_avx512::<true>(ci, cj, cs, cd, chunk),
2113                        (true, false) => write_half_columns_avx512::<false>(ci, cj, cs, cd, chunk),
2114                    }
2115                };
2116                return;
2117            }
2118            write_columns(ci, cj, cs, cd, chunk, self.half, ahead);
2119        });
2120        if self.images.0.is_some() {
2121            for at in 0..self.rows() {
2122                // Every output entry is initialized by the completed chunk writes.
2123                unsafe {
2124                    let old = [
2125                        *shift.add(3 * at),
2126                        *shift.add(3 * at + 1),
2127                        *shift.add(3 * at + 2),
2128                    ];
2129                    let corrected =
2130                        self.images
2131                            .shift(*i.add(at) as usize, *j.add(at) as usize, old);
2132                    for (a, value) in corrected.into_iter().enumerate() {
2133                        *shift.add(3 * at + a) = value;
2134                    }
2135                }
2136            }
2137        }
2138    }
2139
2140    /// `out[t] = row(i, j, shift, dist2)` for every row `t`.
2141    ///
2142    /// # Safety
2143    /// `out` is writable for [`Found::rows`] values of `R`.
2144    #[cfg_attr(not(feature = "capi"), allow(dead_code))]
2145    pub(crate) unsafe fn write_rows<R, F>(&self, out: *mut R, row: F)
2146    where
2147        R: Send,
2148        F: Fn(i32, i32, [i32; 3], f64) -> R + Sync,
2149    {
2150        let base = RowPtr(out as *mut std::mem::MaybeUninit<R>);
2151        self.each_chunk(|t, off, chunk| {
2152            let rows = self.rows_of(chunk);
2153            if rows == 0 {
2154                return;
2155            }
2156            let dst = unsafe { std::slice::from_raw_parts_mut(base.at(off[t]), rows) };
2157            let ahead = ahead(rows, std::mem::size_of::<R>());
2158            let mut at = 0usize;
2159            let mut lo = 0usize;
2160            for (r, &hi) in chunk.run_end.iter().enumerate() {
2161                for k in lo..hi {
2162                    let a = chunk.atom[k] as i32;
2163                    let b = chunk.js[k] as i32;
2164                    let shift = self
2165                        .images
2166                        .shift(a as usize, b as usize, chunk.run_shift[r]);
2167                    let neg = [-shift[0], -shift[1], -shift[2]];
2168                    let d = chunk.d2[k];
2169                    if ahead {
2170                        prefetch(dst.as_ptr().wrapping_add(at + AHEAD_ROWS));
2171                        if !self.half {
2172                            prefetch(dst.as_ptr().wrapping_add(at + AHEAD_ROWS + 1));
2173                        }
2174                    }
2175                    if self.half {
2176                        if keep_half(a as usize, b as usize, shift) {
2177                            dst[at].write(row(a, b, shift, d));
2178                        } else {
2179                            dst[at].write(row(b, a, neg, d));
2180                        }
2181                        at += 1;
2182                    } else {
2183                        dst[at].write(row(a, b, shift, d));
2184                        dst[at + 1].write(row(b, a, neg, d));
2185                        at += 2;
2186                    }
2187                }
2188                lo = hi;
2189            }
2190        });
2191    }
2192
2193    /// `job(t, offsets, chunk)` for every chunk, on several threads when
2194    /// there is more than one chunk.
2195    fn each_chunk<F>(&self, job: F)
2196    where
2197        F: Fn(usize, &[usize], &Scratch) + Sync,
2198    {
2199        let off = self.offsets();
2200        #[cfg(feature = "parallel")]
2201        if self.chunks.len() > 1 {
2202            // Chunk `t` was searched on thread `t`; writing it there reads
2203            // that core's cache.
2204            if self.chunks.len() <= crate::pool_width() {
2205                rayon::broadcast(|ctx| {
2206                    if let Some(chunk) = self.chunks.get(ctx.index()) {
2207                        let _timer = crate::pop::JobTimer::new();
2208                        job(ctx.index(), &off, chunk);
2209                    }
2210                });
2211            } else {
2212                use rayon::prelude::*;
2213                self.chunks.par_iter().enumerate().for_each(|(t, chunk)| {
2214                    let _timer = crate::pop::JobTimer::new();
2215                    job(t, &off, chunk);
2216                });
2217            }
2218            return;
2219        }
2220        for (t, chunk) in self.chunks.iter().enumerate() {
2221            let _timer = crate::pop::JobTimer::new();
2222            job(t, &off, chunk);
2223        }
2224    }
2225}
2226
2227/// A destination several jobs write at disjoint offsets.
2228///
2229/// Safety: jobs write distinct slots and do not read a slot another job writes.
2230struct RowPtr<T>(*mut std::mem::MaybeUninit<T>);
2231impl<T> Clone for RowPtr<T> {
2232    fn clone(&self) -> Self {
2233        *self
2234    }
2235}
2236impl<T> Copy for RowPtr<T> {}
2237unsafe impl<T: Send> Send for RowPtr<T> {}
2238unsafe impl<T: Send> Sync for RowPtr<T> {}
2239impl<T> RowPtr<T> {
2240    unsafe fn at(self, index: usize) -> *mut std::mem::MaybeUninit<T> {
2241        self.0.add(index)
2242    }
2243
2244    /// The pointer itself; a closure that calls this captures the whole
2245    /// `RowPtr`, which is `Send`, not the raw field.
2246    fn ptr(self) -> *mut T {
2247        self.0 as *mut T
2248    }
2249}
2250
2251#[derive(Clone, Copy)]
2252struct ColumnPtrs {
2253    i: RowPtr<i32>,
2254    j: RowPtr<i32>,
2255    shift: RowPtr<i32>,
2256    d2: RowPtr<f64>,
2257}
2258
2259/// Rows past each store that the writers prefetch (about 2 KB of `Pair`
2260/// rows). A store whose line is out in L3 otherwise waits at the head of
2261/// the store buffer, and once the buffer fills the walk behind it stalls
2262/// too, so the walk and the row stream take turns instead of overlapping.
2263const AHEAD_ROWS: usize = 52;
2264
2265/// Output bytes per thread from which the writers prefetch: rows that
2266/// stay in a 2 MB L2 gain nothing, and the prefetches cost instructions.
2267const AHEAD_FROM: usize = 3 << 20;
2268
2269/// Tests force the prefetch off (1) or on (2) to compare the rows; on
2270/// also takes a split full list through [`Plan::fused_fill`].
2271#[cfg(test)]
2272static AHEAD_TEST: std::sync::atomic::AtomicU8 = std::sync::atomic::AtomicU8::new(0);
2273/// Fills through [`Plan::fused_fill`], counted for the tests.
2274#[cfg(test)]
2275static FUSED_FILLS: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
2276
2277/// Whether a writer of `rows` rows of `bytes` bytes prefetches ahead.
2278fn ahead(rows: usize, bytes: usize) -> bool {
2279    #[cfg(test)]
2280    match AHEAD_TEST.load(std::sync::atomic::Ordering::Relaxed) {
2281        1 => return false,
2282        2 => return true,
2283        _ => {}
2284    }
2285    rows.saturating_mul(bytes) >= knobs::ahead_from()
2286}
2287
2288/// Bytes of one row in the four columns.
2289const COLUMN_BYTES: usize =
2290    2 * std::mem::size_of::<i32>() + std::mem::size_of::<[i32; 3]>() + std::mem::size_of::<f64>();
2291
2292/// Prefetch the line holding `p`, which may lie past the end of its
2293/// buffer.
2294#[inline(always)]
2295fn prefetch<T>(p: *const T) {
2296    #[cfg(target_arch = "x86_64")]
2297    // Safety: a prefetch never faults and changes nothing the program
2298    // can read, wherever it points.
2299    unsafe {
2300        // The row stream is written once. A plain prefetch brings the line
2301        // in shared, and the store then waits on a second fetch for
2302        // ownership. This host has PREFETCHW (`3dnowprefetch`), so the
2303        // line arrives exclusive and the store does not fetch it again.
2304        std::arch::x86_64::_mm_prefetch::<{ std::arch::x86_64::_MM_HINT_ET0 }>(p as *const i8)
2305    };
2306    #[cfg(not(target_arch = "x86_64"))]
2307    let _ = p;
2308}
2309
2310#[inline(never)]
2311fn write_columns(
2312    ci: &mut [std::mem::MaybeUninit<i32>],
2313    cj: &mut [std::mem::MaybeUninit<i32>],
2314    cs: &mut [std::mem::MaybeUninit<i32>],
2315    cd: &mut [std::mem::MaybeUninit<f64>],
2316    chunk: &Scratch,
2317    half: bool,
2318    ahead: bool,
2319) {
2320    let mut out = 0usize;
2321    let mut lo = 0usize;
2322    for (r, &hi) in chunk.run_end.iter().enumerate() {
2323        let shift = chunk.run_shift[r];
2324        let neg = [-shift[0], -shift[1], -shift[2]];
2325        for k in lo..hi {
2326            let a = chunk.atom[k] as i32;
2327            let b = chunk.js[k] as i32;
2328            let d = chunk.d2[k];
2329            // Every eighth row: eight rows are under a line of `i`, `j`,
2330            // and `dist2`, and a line and a half of `shift`.
2331            if ahead && out % 8 == 0 {
2332                let at = out + AHEAD_ROWS;
2333                prefetch(ci.as_ptr().wrapping_add(at));
2334                prefetch(cj.as_ptr().wrapping_add(at));
2335                prefetch(cd.as_ptr().wrapping_add(at));
2336                prefetch(cs.as_ptr().wrapping_add(3 * at));
2337                prefetch(cs.as_ptr().wrapping_add(3 * at + 16));
2338            }
2339            if half {
2340                let (i, j, s) = if keep_half(a as usize, b as usize, shift) {
2341                    (a, b, shift)
2342                } else {
2343                    (b, a, neg)
2344                };
2345                ci[out].write(i);
2346                cj[out].write(j);
2347                cs[3 * out].write(s[0]);
2348                cs[3 * out + 1].write(s[1]);
2349                cs[3 * out + 2].write(s[2]);
2350                cd[out].write(d);
2351                out += 1;
2352            } else {
2353                ci[out].write(a);
2354                cj[out].write(b);
2355                cs[3 * out].write(shift[0]);
2356                cs[3 * out + 1].write(shift[1]);
2357                cs[3 * out + 2].write(shift[2]);
2358                cd[out].write(d);
2359                ci[out + 1].write(b);
2360                cj[out + 1].write(a);
2361                cs[3 * out + 3].write(neg[0]);
2362                cs[3 * out + 4].write(neg[1]);
2363                cs[3 * out + 5].write(neg[2]);
2364                cd[out + 1].write(d);
2365                out += 2;
2366            }
2367        }
2368        lo = hi;
2369    }
2370}
2371
2372/// Full-width stores past the last hit stay inside this many extra slots.
2373#[cfg_attr(not(target_arch = "x86_64"), allow(dead_code))]
2374const STORE_SLACK: usize = 16;
2375
2376/// Worst-case hits kept in the scratch buffer. Larger blocks use the scalar walk.
2377#[cfg_attr(not(target_arch = "x86_64"), allow(dead_code))]
2378const MAX_SCRATCH: usize = 1 << 20;
2379
2380#[inline(never)]
2381fn write_full(
2382    dst: &mut [std::mem::MaybeUninit<Pair>],
2383    atom: &[u32],
2384    js: &[u32],
2385    d2: &[f64],
2386    shifts: &[[i32; 3]],
2387    ends: &[usize],
2388    ahead: bool,
2389) {
2390    let dp = dst.as_mut_ptr();
2391    let ap = atom.as_ptr();
2392    let jp = js.as_ptr();
2393    let yp = d2.as_ptr();
2394    let mut out = 0usize;
2395    let mut lo = 0usize;
2396    for (r, &hi) in ends.iter().enumerate() {
2397        let shift = shifts[r];
2398        let neg = [-shift[0], -shift[1], -shift[2]];
2399        for k in lo..hi {
2400            unsafe {
2401                let i = (*ap.add(k)) as usize;
2402                let j = (*jp.add(k)) as usize;
2403                let dist2 = *yp.add(k);
2404                if ahead {
2405                    // Two rows are 80 bytes: one prefetch would skip a
2406                    // line in five.
2407                    prefetch(dp.add(out).wrapping_add(AHEAD_ROWS));
2408                    prefetch(dp.add(out).wrapping_add(AHEAD_ROWS + 1));
2409                }
2410                (*dp.add(out)).write(Pair { i, j, shift, dist2 });
2411                (*dp.add(out + 1)).write(Pair {
2412                    i: j,
2413                    j: i,
2414                    shift: neg,
2415                    dist2,
2416                });
2417            }
2418            out += 2;
2419        }
2420        lo = hi;
2421    }
2422}
2423
2424#[inline(never)]
2425fn write_half(
2426    dst: &mut [std::mem::MaybeUninit<Pair>],
2427    atom: &[u32],
2428    js: &[u32],
2429    d2: &[f64],
2430    shifts: &[[i32; 3]],
2431    ends: &[usize],
2432    ahead: bool,
2433) {
2434    let dp = dst.as_mut_ptr();
2435    let ap = atom.as_ptr();
2436    let jp = js.as_ptr();
2437    let yp = d2.as_ptr();
2438    let mut out = 0usize;
2439    let mut lo = 0usize;
2440    for (r, &hi) in ends.iter().enumerate() {
2441        let shift = shifts[r];
2442        let neg = [-shift[0], -shift[1], -shift[2]];
2443        for k in lo..hi {
2444            unsafe {
2445                let i = (*ap.add(k)) as usize;
2446                let j = (*jp.add(k)) as usize;
2447                let dist2 = *yp.add(k);
2448                if ahead {
2449                    prefetch(dp.add(out).wrapping_add(AHEAD_ROWS));
2450                }
2451                let pair = if keep_half(i, j, shift) {
2452                    Pair { i, j, shift, dist2 }
2453                } else {
2454                    Pair {
2455                        i: j,
2456                        j: i,
2457                        shift: neg,
2458                        dist2,
2459                    }
2460                };
2461                (*dp.add(out)).write(pair);
2462            }
2463            out += 1;
2464        }
2465        lo = hi;
2466    }
2467}
2468
2469/// Word slots of a 40-byte `Pair`: `i`, `j`, `dist2`, and the first of
2470/// the two words that hold `shift` and its padding.
2471#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2472#[derive(Clone, Copy)]
2473struct RowWords {
2474    /// Permute indices for four hits: eight rows, five registers.
2475    index: [[u64; 8]; 5],
2476    /// Dword permute indices for up to eight hits from two registers, one
2477    /// table of five registers per four hits.
2478    index32: [[[u32; 16]; 5]; 2],
2479    /// The same sources as `index32` for a half list, one row per hit in
2480    /// five registers for eight hits: `(i, j, S, d)` from table 0 and
2481    /// `(j, i, -S, d)` from table 1, picked per row by [`MIRROR32`].
2482    half32: [[[u32; 16]; 5]; 2],
2483    /// Buffered half rows, eight a time, from `[i0 .. i7, j0 .. j7]` and
2484    /// the eight distances: the dword of each row's `i`, `j`, and `dist2`
2485    /// in `rows_ij`, the dwords those fill in `rows_keep` (the high halves
2486    /// of `i` and `j` stay zero), and where `S` (dwords 0..3 of a source)
2487    /// or `-S` (dwords 3..6) go in `rows_s` and `rows_n` (dword 6, zero,
2488    /// elsewhere).
2489    rows_ij: [[u32; 16]; 5],
2490    rows_keep: [u16; 5],
2491    rows_s: [[u32; 16]; 5],
2492    rows_n: [[u32; 16]; 5],
2493}
2494
2495/// For each set of mirrored hits among eight (bit `h` for hit `h`), the
2496/// dwords of each of the five registers of half-list rows that come from
2497/// the mirrored table: row `h` is words `5 h .. 5 h + 5`.
2498#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2499static MIRROR32: [[u16; 5]; 256] = mirror_masks(10);
2500
2501/// The same for the `shift` column, three dwords a row: the first 16
2502/// dwords in the low half, the next eight above them.
2503#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2504static MIRROR3: [u32; 256] = {
2505    let m = mirror_masks(3);
2506    let mut out = [0u32; 256];
2507    let mut b = 0;
2508    while b < 256 {
2509        out[b] = m[b][0] as u32 | ((m[b][1] as u32 & 0xff) << 16);
2510        b += 1;
2511    }
2512    out
2513};
2514
2515/// Dword masks of rows `dwords` dwords long, five 16-dword registers, for
2516/// every set of mirrored rows among eight.
2517#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2518const fn mirror_masks(dwords: usize) -> [[u16; 5]; 256] {
2519    let mut out = [[0u16; 5]; 256];
2520    let mut b = 0;
2521    while b < 256 {
2522        let mut t = 0;
2523        while t < 80 {
2524            let row = t / dwords;
2525            if row < 8 && (b >> row) & 1 == 1 {
2526                out[b][t / 16] |= 1 << (t % 16);
2527            }
2528            t += 1;
2529        }
2530        b += 1;
2531    }
2532    out
2533}
2534
2535#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2536impl RowWords {
2537    /// `None` unless `Pair` is five whole words. The layout of a Rust
2538    /// struct is the compiler's choice, so it is read, not assumed.
2539    fn of_pair() -> Option<Self> {
2540        let p = Pair {
2541            i: 0,
2542            j: 0,
2543            shift: [0; 3],
2544            dist2: 0.0,
2545        };
2546        let base = &p as *const Pair as usize;
2547        let at = |a: usize| a - base;
2548        let off = [
2549            at(&p.i as *const usize as usize),
2550            at(&p.j as *const usize as usize),
2551            at(&p.dist2 as *const f64 as usize),
2552            at(&p.shift as *const [i32; 3] as usize),
2553        ];
2554        if std::mem::size_of::<Pair>() != 40 || off.iter().any(|o| o % 8 != 0) {
2555            return None;
2556        }
2557        let (wi, wj, wd, ws) = (off[0] / 8, off[1] / 8, off[2] / 8, off[3] / 8);
2558        let mut seen = [false; 5];
2559        for w in [wi, wj, wd, ws, ws + 1] {
2560            if w >= 5 || seen[w] {
2561                return None;
2562            }
2563            seen[w] = true;
2564        }
2565        // Sources: [a0 a1 a2 a3 b0 b1 b2 b3] then [d0 d1 d2 d3 S01 S2 N01 N2].
2566        // Row 2k is (a_k, b_k, S, d_k); row 2k + 1 is (b_k, a_k, -S, d_k).
2567        let mut index = [[0u64; 8]; 5];
2568        // Dword sources: [j0 .. j7, i, 0, s0, s1, s2, n0, n1, n2] then the
2569        // eight distances, two dwords each. Group `g` holds hits 4g..4g + 3.
2570        let mut index32 = [[[0u32; 16]; 5]; 2];
2571        for r in 0..8 {
2572            let (k, mirror) = ((r / 2) as u64, r % 2 == 1);
2573            let mut row = [0u64; 5];
2574            row[wi] = if mirror { 4 + k } else { k };
2575            row[wj] = if mirror { k } else { 4 + k };
2576            row[wd] = 8 + k;
2577            row[ws] = if mirror { 14 } else { 12 };
2578            row[ws + 1] = if mirror { 15 } else { 13 };
2579            for (w, &v) in row.iter().enumerate() {
2580                let t = 5 * r + w;
2581                index[t / 8][t % 8] = v;
2582            }
2583            for (g, table) in index32.iter_mut().enumerate() {
2584                let h = (4 * g + r / 2) as u32;
2585                let mut row = [[0u32; 2]; 5];
2586                row[wi] = if mirror { [h, 9] } else { [8, 9] };
2587                row[wj] = if mirror { [8, 9] } else { [h, 9] };
2588                row[wd] = [16 + 2 * h, 17 + 2 * h];
2589                row[ws] = if mirror { [13, 14] } else { [10, 11] };
2590                row[ws + 1] = if mirror { [15, 9] } else { [12, 9] };
2591                for (w, pair) in row.iter().enumerate() {
2592                    for (half, &v) in pair.iter().enumerate() {
2593                        let q = 10 * r + 2 * w + half;
2594                        table[q / 16][q % 16] = v;
2595                    }
2596                }
2597            }
2598        }
2599        // Half rows: row `h` is hit `h`, forward or mirrored.
2600        let mut half32 = [[[0u32; 16]; 5]; 2];
2601        for (side, table) in half32.iter_mut().enumerate() {
2602            let mirror = side == 1;
2603            for h in 0..8u32 {
2604                let mut row = [[0u32; 2]; 5];
2605                row[wi] = if mirror { [h, 9] } else { [8, 9] };
2606                row[wj] = if mirror { [8, 9] } else { [h, 9] };
2607                row[wd] = [16 + 2 * h, 17 + 2 * h];
2608                row[ws] = if mirror { [13, 14] } else { [10, 11] };
2609                row[ws + 1] = if mirror { [15, 9] } else { [12, 9] };
2610                for (w, pair) in row.iter().enumerate() {
2611                    for (half, &v) in pair.iter().enumerate() {
2612                        let q = 10 * h as usize + 2 * w + half;
2613                        table[q / 16][q % 16] = v;
2614                    }
2615                }
2616            }
2617        }
2618        let mut rows_ij = [[0u32; 16]; 5];
2619        let mut rows_keep = [0u16; 5];
2620        let mut rows_s = [[6u32; 16]; 5];
2621        let mut rows_n = [[6u32; 16]; 5];
2622        for h in 0..8u32 {
2623            let at = |w: usize, half: usize| {
2624                let q = 10 * h as usize + 2 * w + half;
2625                (q / 16, q % 16)
2626            };
2627            for (w, src) in [(wi, h), (wj, 8 + h)] {
2628                let (m, d) = at(w, 0);
2629                rows_ij[m][d] = src;
2630                rows_keep[m] |= 1 << d;
2631            }
2632            for half in 0..2 {
2633                let (m, d) = at(wd, half);
2634                rows_ij[m][d] = 16 + 2 * h + half as u32;
2635                rows_keep[m] |= 1 << d;
2636            }
2637            for (w, half, k) in [(ws, 0, 0u32), (ws, 1, 1), (ws + 1, 0, 2)] {
2638                let (m, d) = at(w, half);
2639                rows_s[m][d] = k;
2640                rows_n[m][d] = 3 + k;
2641            }
2642        }
2643        Some(Self {
2644            index,
2645            index32,
2646            half32,
2647            rows_ij,
2648            rows_keep,
2649            rows_s,
2650            rows_n,
2651        })
2652    }
2653}
2654
2655/// `shift` as the two little-endian words of a row: `(s0, s1)` and `(s2, 0)`.
2656#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2657fn shift_words(s: [i32; 3]) -> (u64, u64) {
2658    (
2659        u64::from(s[0] as u32) | (u64::from(s[1] as u32) << 32),
2660        u64::from(s[2] as u32),
2661    )
2662}
2663
2664/// [`write_full`] four hits at a time: eight rows are five permutes of two
2665/// registers and five stores.
2666///
2667/// # Safety
2668/// AVX-512F is available, and `dst` holds two rows per hit of `chunk`.
2669#[allow(clippy::incompatible_msrv)]
2670#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2671#[target_feature(enable = "avx512f")]
2672#[inline(never)]
2673unsafe fn write_full_avx512<const AHEAD: bool>(
2674    dst: *mut std::mem::MaybeUninit<Pair>,
2675    chunk: &Scratch,
2676    words: &RowWords,
2677) {
2678    use std::arch::x86_64::{
2679        __m128i, __m512i, _mm256_cvtepu32_epi64, _mm256_set_epi64x, _mm512_castsi256_si512,
2680        _mm512_inserti64x4, _mm512_loadu_si512, _mm512_permutex2var_epi64, _mm512_storeu_si512,
2681        _mm_loadu_si128,
2682    };
2683    let idx: [__m512i; 5] = [
2684        _mm512_loadu_si512(words.index[0].as_ptr() as *const _),
2685        _mm512_loadu_si512(words.index[1].as_ptr() as *const _),
2686        _mm512_loadu_si512(words.index[2].as_ptr() as *const _),
2687        _mm512_loadu_si512(words.index[3].as_ptr() as *const _),
2688        _mm512_loadu_si512(words.index[4].as_ptr() as *const _),
2689    ];
2690    let ap = chunk.atom.as_ptr();
2691    let jp = chunk.js.as_ptr();
2692    let dp = chunk.d2.as_ptr();
2693    let mut row = dst;
2694    let mut lo = 0usize;
2695    for (r, &hi) in chunk.run_end.iter().enumerate() {
2696        let shift = chunk.run_shift[r];
2697        let neg = [-shift[0], -shift[1], -shift[2]];
2698        let (s01, s2) = shift_words(shift);
2699        let (n01, n2) = shift_words(neg);
2700        let sh = _mm256_set_epi64x(n2 as i64, n01 as i64, s2 as i64, s01 as i64);
2701        let mut k = lo;
2702        while k + 4 <= hi {
2703            let a = _mm256_cvtepu32_epi64(_mm_loadu_si128(ap.add(k) as *const __m128i));
2704            let b = _mm256_cvtepu32_epi64(_mm_loadu_si128(jp.add(k) as *const __m128i));
2705            let ab = _mm512_inserti64x4(_mm512_castsi256_si512(a), b, 1);
2706            let d = _mm512_loadu_si512(dp.add(k) as *const _);
2707            let ds = _mm512_inserti64x4(d, sh, 1);
2708            let out = row as *mut u64;
2709            for (m, ix) in idx.iter().enumerate() {
2710                if AHEAD {
2711                    prefetch(out.add(8 * m).wrapping_add(5 * AHEAD_ROWS));
2712                }
2713                _mm512_storeu_si512(
2714                    out.add(8 * m) as *mut _,
2715                    _mm512_permutex2var_epi64(ab, *ix, ds),
2716                );
2717            }
2718            row = row.add(8);
2719            k += 4;
2720        }
2721        while k < hi {
2722            let i = *ap.add(k) as usize;
2723            let j = *jp.add(k) as usize;
2724            let dist2 = *dp.add(k);
2725            (*row).write(Pair { i, j, shift, dist2 });
2726            (*row.add(1)).write(Pair {
2727                i: j,
2728                j: i,
2729                shift: neg,
2730                dist2,
2731            });
2732            row = row.add(2);
2733            k += 1;
2734        }
2735        lo = hi;
2736    }
2737}
2738
2739/// [`write_columns`] for a full list, eight hits (sixteen rows) at a time.
2740///
2741/// # Safety
2742/// AVX-512F is available, and the columns hold two rows per hit of
2743/// `chunk`; `cs` holds three values per row.
2744#[allow(clippy::incompatible_msrv)]
2745#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2746#[target_feature(enable = "avx512f")]
2747#[inline(never)]
2748unsafe fn write_columns_avx512<const AHEAD: bool>(
2749    ci: &mut [std::mem::MaybeUninit<i32>],
2750    cj: &mut [std::mem::MaybeUninit<i32>],
2751    cs: &mut [std::mem::MaybeUninit<i32>],
2752    cd: &mut [std::mem::MaybeUninit<f64>],
2753    chunk: &Scratch,
2754) {
2755    use std::arch::x86_64::{
2756        __m256i, _mm256_loadu_si256, _mm512_castsi256_si512, _mm512_loadu_pd, _mm512_loadu_si512,
2757        _mm512_permutex2var_epi32, _mm512_permutexvar_epi32, _mm512_permutexvar_pd,
2758        _mm512_setr_epi32, _mm512_setr_epi64, _mm512_storeu_pd, _mm512_storeu_si512,
2759    };
2760    // Row 2k is (a_k, b_k, S, d_k); row 2k + 1 is (b_k, a_k, -S, d_k).
2761    let ab = _mm512_setr_epi32(0, 16, 1, 17, 2, 18, 3, 19, 4, 20, 5, 21, 6, 22, 7, 23);
2762    let ba = _mm512_setr_epi32(16, 0, 17, 1, 18, 2, 19, 3, 20, 4, 21, 5, 22, 6, 23, 7);
2763    let dup_lo = _mm512_setr_epi64(0, 0, 1, 1, 2, 2, 3, 3);
2764    let dup_hi = _mm512_setr_epi64(4, 4, 5, 5, 6, 6, 7, 7);
2765    // Shift column of sixteen rows: (S, -S) eight times, 48 values.
2766    let pat = [
2767        _mm512_setr_epi32(0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3),
2768        _mm512_setr_epi32(4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1),
2769        _mm512_setr_epi32(2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5),
2770    ];
2771    let ap = chunk.atom.as_ptr();
2772    let jp = chunk.js.as_ptr();
2773    let dp = chunk.d2.as_ptr();
2774    let ip = ci.as_mut_ptr() as *mut i32;
2775    let jo = cj.as_mut_ptr() as *mut i32;
2776    let sp = cs.as_mut_ptr() as *mut i32;
2777    let dq = cd.as_mut_ptr() as *mut f64;
2778    let mut out = 0usize;
2779    let mut lo = 0usize;
2780    for (r, &hi) in chunk.run_end.iter().enumerate() {
2781        let s = chunk.run_shift[r];
2782        let six = [
2783            s[0], s[1], s[2], -s[0], -s[1], -s[2], 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2784        ];
2785        let src = _mm512_loadu_si512(six.as_ptr() as *const _);
2786        let sv = [
2787            _mm512_permutexvar_epi32(pat[0], src),
2788            _mm512_permutexvar_epi32(pat[1], src),
2789            _mm512_permutexvar_epi32(pat[2], src),
2790        ];
2791        let mut k = lo;
2792        while k + 8 <= hi {
2793            if AHEAD {
2794                let at = out + AHEAD_ROWS;
2795                prefetch(ip.wrapping_add(at));
2796                prefetch(jo.wrapping_add(at));
2797                prefetch(dq.wrapping_add(at));
2798                prefetch(dq.wrapping_add(at + 8));
2799                prefetch(sp.wrapping_add(3 * at));
2800                prefetch(sp.wrapping_add(3 * at + 16));
2801                prefetch(sp.wrapping_add(3 * at + 32));
2802            }
2803            let a = _mm512_castsi256_si512(_mm256_loadu_si256(ap.add(k) as *const __m256i));
2804            let b = _mm512_castsi256_si512(_mm256_loadu_si256(jp.add(k) as *const __m256i));
2805            _mm512_storeu_si512(ip.add(out) as *mut _, _mm512_permutex2var_epi32(a, ab, b));
2806            _mm512_storeu_si512(jo.add(out) as *mut _, _mm512_permutex2var_epi32(a, ba, b));
2807            let d = _mm512_loadu_pd(dp.add(k));
2808            _mm512_storeu_pd(dq.add(out), _mm512_permutexvar_pd(dup_lo, d));
2809            _mm512_storeu_pd(dq.add(out + 8), _mm512_permutexvar_pd(dup_hi, d));
2810            let so = sp.add(3 * out);
2811            _mm512_storeu_si512(so as *mut _, sv[0]);
2812            _mm512_storeu_si512(so.add(16) as *mut _, sv[1]);
2813            _mm512_storeu_si512(so.add(32) as *mut _, sv[2]);
2814            out += 16;
2815            k += 8;
2816        }
2817        while k < hi {
2818            let a = *ap.add(k) as i32;
2819            let b = *jp.add(k) as i32;
2820            let d = *dp.add(k);
2821            *ip.add(out) = a;
2822            *jo.add(out) = b;
2823            *dq.add(out) = d;
2824            *ip.add(out + 1) = b;
2825            *jo.add(out + 1) = a;
2826            *dq.add(out + 1) = d;
2827            let so = sp.add(3 * out);
2828            *so = s[0];
2829            *so.add(1) = s[1];
2830            *so.add(2) = s[2];
2831            *so.add(3) = -s[0];
2832            *so.add(4) = -s[1];
2833            *so.add(5) = -s[2];
2834            out += 2;
2835            k += 1;
2836        }
2837        lo = hi;
2838    }
2839}
2840
2841/// [`write_half`] eight hits at a time: each register of rows is one
2842/// zero-masked permute of the hits' sides and distances, with `S` or `-S`
2843/// blended in per row.
2844///
2845/// # Safety
2846/// AVX-512F and AVX-512VL are available, and `dst` holds one row per hit
2847/// of `chunk`.
2848#[allow(clippy::incompatible_msrv)]
2849#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2850#[target_feature(enable = "avx512f,avx512vl")]
2851#[inline(never)]
2852unsafe fn write_half_avx512<const AHEAD: bool>(
2853    dst: *mut std::mem::MaybeUninit<Pair>,
2854    chunk: &Scratch,
2855    words: &RowWords,
2856) {
2857    use std::arch::x86_64::{
2858        __m256i, __m512i, _mm256_cmp_epu32_mask, _mm256_cmpeq_epi32_mask, _mm256_loadu_si256,
2859        _mm256_mask_blend_epi32, _mm512_castsi256_si512, _mm512_inserti64x4, _mm512_loadu_si512,
2860        _mm512_mask_blend_epi32, _mm512_maskz_permutex2var_epi32, _mm512_or_si512,
2861        _mm512_permutexvar_epi32, _mm512_setr_epi32, _mm512_storeu_si512, _MM_CMPINT_LT,
2862    };
2863    let load = |t: &[u32; 16]| _mm512_loadu_si512(t.as_ptr() as *const _);
2864    let ij: [__m512i; 5] = std::array::from_fn(|m| load(&words.rows_ij[m]));
2865    let ap = chunk.atom.as_ptr();
2866    let jp = chunk.js.as_ptr();
2867    let dp = chunk.d2.as_ptr();
2868    let mut out = 0usize;
2869    let mut lo = 0usize;
2870    for (r, &hi) in chunk.run_end.iter().enumerate() {
2871        let s = chunk.run_shift[r];
2872        let neg = [-s[0], -s[1], -s[2]];
2873        let self_fwd: u8 = if keep_half(0, 0, s) { 0xff } else { 0 };
2874        let six = _mm512_setr_epi32(
2875            s[0], s[1], s[2], neg[0], neg[1], neg[2], 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2876        );
2877        let fs: [__m512i; 5] =
2878            std::array::from_fn(|m| _mm512_permutexvar_epi32(load(&words.rows_s[m]), six));
2879        let ns: [__m512i; 5] =
2880            std::array::from_fn(|m| _mm512_permutexvar_epi32(load(&words.rows_n[m]), six));
2881        let mut k = lo;
2882        while k + 8 <= hi {
2883            let a = _mm256_loadu_si256(ap.add(k) as *const __m256i);
2884            let b = _mm256_loadu_si256(jp.add(k) as *const __m256i);
2885            // Row `h` keeps (a_h, b_h, S) when a_h < b_h, or for an atom's
2886            // own image when the shift says so; otherwise (b_h, a_h, -S).
2887            let fwd = _mm256_cmp_epu32_mask::<_MM_CMPINT_LT>(a, b)
2888                | (_mm256_cmpeq_epi32_mask(a, b) & self_fwd);
2889            let sides = _mm512_inserti64x4::<1>(
2890                _mm512_castsi256_si512(_mm256_mask_blend_epi32(fwd, b, a)),
2891                _mm256_mask_blend_epi32(fwd, a, b),
2892            );
2893            let d = _mm512_loadu_si512(dp.add(k) as *const _);
2894            let pick = &MIRROR32[!fwd as usize];
2895            let row = dst.add(out) as *mut u64;
2896            for m in 0..5 {
2897                if AHEAD {
2898                    prefetch(row.add(8 * m).wrapping_add(5 * AHEAD_ROWS));
2899                }
2900                let v = _mm512_maskz_permutex2var_epi32(words.rows_keep[m], sides, ij[m], d);
2901                let sh = _mm512_mask_blend_epi32(pick[m], fs[m], ns[m]);
2902                _mm512_storeu_si512(row.add(8 * m) as *mut _, _mm512_or_si512(v, sh));
2903            }
2904            out += 8;
2905            k += 8;
2906        }
2907        while k < hi {
2908            let (i, j, dist2) = (*ap.add(k) as usize, *jp.add(k) as usize, *dp.add(k));
2909            let pair = if keep_half(i, j, s) {
2910                Pair {
2911                    i,
2912                    j,
2913                    shift: s,
2914                    dist2,
2915                }
2916            } else {
2917                Pair {
2918                    i: j,
2919                    j: i,
2920                    shift: neg,
2921                    dist2,
2922                }
2923            };
2924            (*dst.add(out)).write(pair);
2925            out += 1;
2926            k += 1;
2927        }
2928        lo = hi;
2929    }
2930}
2931
2932/// [`write_columns`] for a half list, eight hits (eight rows) at a time:
2933/// one compare picks each hit's side, as in the tile kernel.
2934///
2935/// # Safety
2936/// AVX-512F and AVX-512VL are available, and the columns hold one row
2937/// per hit of `chunk`; `cs` holds three values per row.
2938#[allow(clippy::incompatible_msrv)]
2939#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
2940#[target_feature(enable = "avx512f,avx512vl")]
2941#[inline(never)]
2942unsafe fn write_half_columns_avx512<const AHEAD: bool>(
2943    ci: &mut [std::mem::MaybeUninit<i32>],
2944    cj: &mut [std::mem::MaybeUninit<i32>],
2945    cs: &mut [std::mem::MaybeUninit<i32>],
2946    cd: &mut [std::mem::MaybeUninit<f64>],
2947    chunk: &Scratch,
2948) {
2949    use std::arch::x86_64::{
2950        __m256i, _mm256_cmp_epu32_mask, _mm256_cmpeq_epi32_mask, _mm256_loadu_si256,
2951        _mm256_mask_blend_epi32, _mm256_storeu_si256, _mm512_castsi512_si256, _mm512_loadu_pd,
2952        _mm512_mask_blend_epi32, _mm512_permutexvar_epi32, _mm512_setr_epi32, _mm512_storeu_pd,
2953        _mm512_storeu_si512, _MM_CMPINT_LT,
2954    };
2955    let ap = chunk.atom.as_ptr();
2956    let jp = chunk.js.as_ptr();
2957    let dp = chunk.d2.as_ptr();
2958    let ip = ci.as_mut_ptr() as *mut i32;
2959    let jo = cj.as_mut_ptr() as *mut i32;
2960    let sp = cs.as_mut_ptr() as *mut i32;
2961    let dq = cd.as_mut_ptr() as *mut f64;
2962    let mut out = 0usize;
2963    let mut lo = 0usize;
2964    for (r, &hi) in chunk.run_end.iter().enumerate() {
2965        let s = chunk.run_shift[r];
2966        let neg = [-s[0], -s[1], -s[2]];
2967        let self_fwd: u8 = if keep_half(0, 0, s) { 0xff } else { 0 };
2968        let six = _mm512_setr_epi32(
2969            s[0], s[1], s[2], neg[0], neg[1], neg[2], 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2970        );
2971        // The shift column of eight rows, all S or all -S: dwords 0..16
2972        // and 16..24.
2973        let s_lo = _mm512_permutexvar_epi32(
2974            _mm512_setr_epi32(0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0),
2975            six,
2976        );
2977        let n_lo = _mm512_permutexvar_epi32(
2978            _mm512_setr_epi32(3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3),
2979            six,
2980        );
2981        let s_hi = _mm512_castsi512_si256(_mm512_permutexvar_epi32(
2982            _mm512_setr_epi32(1, 2, 0, 1, 2, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0),
2983            six,
2984        ));
2985        let n_hi = _mm512_castsi512_si256(_mm512_permutexvar_epi32(
2986            _mm512_setr_epi32(4, 5, 3, 4, 5, 3, 4, 5, 3, 3, 3, 3, 3, 3, 3, 3),
2987            six,
2988        ));
2989        let mut k = lo;
2990        while k + 8 <= hi {
2991            if AHEAD {
2992                let at = out + AHEAD_ROWS;
2993                prefetch(ip.wrapping_add(at));
2994                prefetch(jo.wrapping_add(at));
2995                prefetch(dq.wrapping_add(at));
2996                prefetch(sp.wrapping_add(3 * at));
2997                prefetch(sp.wrapping_add(3 * at + 16));
2998            }
2999            let a = _mm256_loadu_si256(ap.add(k) as *const __m256i);
3000            let b = _mm256_loadu_si256(jp.add(k) as *const __m256i);
3001            // Row `h` keeps (a_h, b_h, S) when a_h < b_h, or for an atom's
3002            // own image when the shift says so; otherwise (b_h, a_h, -S).
3003            let fwd = _mm256_cmp_epu32_mask::<_MM_CMPINT_LT>(a, b)
3004                | (_mm256_cmpeq_epi32_mask(a, b) & self_fwd);
3005            _mm256_storeu_si256(ip.add(out) as *mut _, _mm256_mask_blend_epi32(fwd, b, a));
3006            _mm256_storeu_si256(jo.add(out) as *mut _, _mm256_mask_blend_epi32(fwd, a, b));
3007            _mm512_storeu_pd(dq.add(out), _mm512_loadu_pd(dp.add(k)));
3008            let m3 = MIRROR3[!fwd as usize];
3009            _mm512_storeu_si512(
3010                sp.add(3 * out) as *mut _,
3011                _mm512_mask_blend_epi32(m3 as u16, s_lo, n_lo),
3012            );
3013            _mm256_storeu_si256(
3014                sp.add(3 * out + 16) as *mut _,
3015                _mm256_mask_blend_epi32((m3 >> 16) as u8, s_hi, n_hi),
3016            );
3017            out += 8;
3018            k += 8;
3019        }
3020        while k < hi {
3021            let (a, b, d) = (*ap.add(k), *jp.add(k), *dp.add(k));
3022            let (i, j, t) = if keep_half(a as usize, b as usize, s) {
3023                (a, b, s)
3024            } else {
3025                (b, a, neg)
3026            };
3027            *ip.add(out) = i as i32;
3028            *jo.add(out) = j as i32;
3029            *dq.add(out) = d;
3030            let so = sp.add(3 * out);
3031            *so = t[0];
3032            *so.add(1) = t[1];
3033            *so.add(2) = t[2];
3034            out += 1;
3035            k += 1;
3036        }
3037        lo = hi;
3038    }
3039}
3040
3041/// Target runs of eight a bin needs before the tile kernel tests boxes:
3042/// with fewer, the bin stencil has already done most of the culling and
3043/// the box test costs more than it skips.
3044const CULL_RUNS: usize = 4;
3045
3046/// Tests turn the box test off to compare against it, and count the
3047/// target runs it skips.
3048#[cfg(test)]
3049static NO_CULL: std::sync::atomic::AtomicBool = std::sync::atomic::AtomicBool::new(false);
3050#[cfg(test)]
3051static CULL_SKIPS: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
3052
3053fn no_cull() -> bool {
3054    #[cfg(test)]
3055    return NO_CULL.load(std::sync::atomic::Ordering::Relaxed);
3056    #[cfg(not(test))]
3057    false
3058}
3059
3060/// Run `$body` with `$slot` at the first slot of every target run of
3061/// eight in `$block` whose [`Boxes`] entry comes within `$cut` (squared)
3062/// of the box of the source run of four holding slot `$s`, moved by
3063/// `($ox, $oy, $oz)`; in slot order. Eight target boxes are tested at a
3064/// time.
3065///
3066/// A source in the run, moved, lies inside the moved box (rounding is
3067/// monotonic), and each target lies inside its own box, so a pair's
3068/// relative distance is at least the box gap. `$cut` is the cutoff plus
3069/// twice the expansion margin, so a skipped run holds no lane the tile
3070/// kernel would keep, and the rows and their order are unchanged.
3071#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3072macro_rules! near_runs {
3073    ($c:expr, $block:expr, $nvec:expr, $ox:expr, $oy:expr, $oz:expr, $cut:expr, $zero:expr,
3074     $s:expr, $slot:ident, $body:block) => {{
3075        use std::arch::x86_64::{
3076            _mm512_fmadd_pd, _mm512_loadu_pd, _mm512_mask_cmp_pd_mask, _mm512_max_pd,
3077            _mm512_set1_pd, _mm512_sub_pd, _CMP_LT_OQ,
3078        };
3079        let g = $block.ig + ($s - $block.i_lo) / 4;
3080        let lo = [
3081            _mm512_set1_pd(*$c.gb[0].add(g) + $ox),
3082            _mm512_set1_pd(*$c.gb[1].add(g) + $oy),
3083            _mm512_set1_pd(*$c.gb[2].add(g) + $oz),
3084        ];
3085        let hi = [
3086            _mm512_set1_pd(*$c.gb[3].add(g) + $ox),
3087            _mm512_set1_pd(*$c.gb[4].add(g) + $oy),
3088            _mm512_set1_pd(*$c.gb[5].add(g) + $oz),
3089        ];
3090        let mut m0 = 0usize;
3091        while m0 < $nvec {
3092            let v = $block.jv + m0;
3093            let mut d2 = $zero;
3094            for ax in 0..3 {
3095                let gap = _mm512_max_pd(
3096                    _mm512_max_pd(
3097                        _mm512_sub_pd(_mm512_loadu_pd($c.vb[ax].add(v)), hi[ax]),
3098                        _mm512_sub_pd(lo[ax], _mm512_loadu_pd($c.vb[3 + ax].add(v))),
3099                    ),
3100                    $zero,
3101                );
3102                d2 = _mm512_fmadd_pd(gap, gap, d2);
3103            }
3104            let valid: u8 = if $nvec - m0 >= 8 {
3105                0xff
3106            } else {
3107                ((1u32 << ($nvec - m0)) - 1) as u8
3108            };
3109            let mut near: u8 = _mm512_mask_cmp_pd_mask(valid, d2, $cut, _CMP_LT_OQ);
3110            #[cfg(test)]
3111            CULL_SKIPS.fetch_add(
3112                (valid & !near).count_ones() as usize,
3113                std::sync::atomic::Ordering::Relaxed,
3114            );
3115            while near != 0 {
3116                let $slot = $block.j_lo + 8 * (m0 + near.trailing_zeros() as usize);
3117                near &= near - 1;
3118                $body
3119            }
3120            m0 += 8;
3121        }
3122    }};
3123}
3124
3125/// Where the fused kernel writes: `Pair` rows as words, or four columns.
3126/// `n` is the row count so far. Each hit vector writes whole registers
3127/// past its last kept row; the next vector overwrites them, so every
3128/// buffer keeps [`FUSED_SLACK`] rows of room past `n`.
3129#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3130struct FusedOut {
3131    rows: *mut u64,
3132    ci: *mut i32,
3133    cj: *mut i32,
3134    cs: *mut i32,
3135    cd: *mut f64,
3136    n: usize,
3137    /// Rows no store may reach: rows past it belong to another thread, so
3138    /// a full list's last registers before it are stored under a mask.
3139    limit: usize,
3140}
3141
3142/// Mean atoms per bin under which one thread runs the tile inlined into
3143/// its block loop: with a few atoms a block, the call into the tile is
3144/// most of the block (256 atoms in the 18 Ă… cube, four a bin, 0.020 ->
3145/// 0.017 ms), while with full bins the tile's own register allocation is
3146/// a little better out of line.
3147#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3148const INLINE_BLOCKS: usize = 8;
3149
3150/// Where [`Plan::fused_into`] writes: room for `room` more rows past the
3151/// first `n`, on demand.
3152#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3153trait FusedSink {
3154    fn room(&mut self, n: usize, room: usize) -> FusedOut;
3155}
3156
3157#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3158impl FusedSink for Vec<Pair> {
3159    fn room(&mut self, n: usize, room: usize) -> FusedOut {
3160        if self.capacity() - n < room {
3161            // Safety: the first `n` rows are written.
3162            unsafe { self.set_len(n) };
3163            self.reserve(room);
3164        }
3165        FusedOut {
3166            rows: self.as_mut_ptr() as *mut u64,
3167            ci: std::ptr::null_mut(),
3168            cj: std::ptr::null_mut(),
3169            cs: std::ptr::null_mut(),
3170            cd: std::ptr::null_mut(),
3171            n,
3172            limit: usize::MAX,
3173        }
3174    }
3175}
3176
3177#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3178impl FusedSink for PairColumns {
3179    fn room(&mut self, n: usize, room: usize) -> FusedOut {
3180        let cap = self
3181            .i
3182            .capacity()
3183            .min(self.j.capacity())
3184            .min(self.shift.capacity())
3185            .min(self.dist2.capacity());
3186        if cap - n < room {
3187            // Safety: the first `n` rows of every column are written.
3188            unsafe {
3189                self.i.set_len(n);
3190                self.j.set_len(n);
3191                self.shift.set_len(n);
3192                self.dist2.set_len(n);
3193            }
3194            self.i.reserve(room);
3195            self.j.reserve(room);
3196            self.shift.reserve(room);
3197            self.dist2.reserve(room);
3198        }
3199        FusedOut {
3200            rows: std::ptr::null_mut(),
3201            ci: self.i.as_mut_ptr(),
3202            cj: self.j.as_mut_ptr(),
3203            cs: self.shift.as_mut_ptr() as *mut i32,
3204            cd: self.dist2.as_mut_ptr(),
3205            n,
3206            limit: usize::MAX,
3207        }
3208    }
3209}
3210
3211/// Counts rows: [`avx512_fused`] with `COUNT` writes nothing.
3212#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3213struct Counter;
3214
3215#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3216impl FusedSink for Counter {
3217    fn room(&mut self, n: usize, _room: usize) -> FusedOut {
3218        FusedOut {
3219            rows: std::ptr::null_mut(),
3220            ci: std::ptr::null_mut(),
3221            cj: std::ptr::null_mut(),
3222            cs: std::ptr::null_mut(),
3223            cd: std::ptr::null_mut(),
3224            n,
3225            limit: usize::MAX,
3226        }
3227    }
3228}
3229
3230/// Column slots below `limit`. Rows at `limit` and after belong to the
3231/// next thread, and a half-list tile must not store into them.
3232#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3233struct FixedCols {
3234    ci: *mut i32,
3235    cj: *mut i32,
3236    cs: *mut i32,
3237    cd: *mut f64,
3238    limit: usize,
3239}
3240
3241#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3242impl FusedSink for FixedCols {
3243    fn room(&mut self, n: usize, _room: usize) -> FusedOut {
3244        FusedOut {
3245            rows: std::ptr::null_mut(),
3246            ci: self.ci,
3247            cj: self.cj,
3248            cs: self.cs,
3249            cd: self.cd,
3250            n,
3251            limit: self.limit,
3252        }
3253    }
3254}
3255
3256/// The rows below `limit` of a buffer whose rows from `limit` on another
3257/// thread writes.
3258#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3259struct Fixed {
3260    rows: *mut u64,
3261    limit: usize,
3262}
3263
3264#[cfg(all(target_arch = "x86_64", linkcell_avx512, feature = "parallel"))]
3265impl FusedSink for Fixed {
3266    fn room(&mut self, n: usize, _room: usize) -> FusedOut {
3267        FusedOut {
3268            rows: self.rows,
3269            ci: std::ptr::null_mut(),
3270            cj: std::ptr::null_mut(),
3271            cs: std::ptr::null_mut(),
3272            cd: std::ptr::null_mut(),
3273            n,
3274            limit: self.limit,
3275        }
3276    }
3277}
3278
3279/// What [`avx512_fused`] does with its rows: write them with whole
3280/// registers, count them, or write them with the registers that would
3281/// pass the sink's limit stored under a mask.
3282#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3283const PLAIN: u8 = 0;
3284#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3285const COUNT: u8 = 1;
3286#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3287const BOUNDED: u8 = 2;
3288
3289/// Rows a hit vector may write past the last row it keeps.
3290#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3291const FUSED_SLACK: usize = 16;
3292
3293/// The AVX-512 tile kernel of [`avx512_scan`] with its list written in
3294/// place: `Pair` rows when `COLS` is false, the four columns when it is
3295/// true. Hit lanes are compressed, then four hits become eight rows (or
3296/// sixteen column entries) in whole registers; with `HALF`, each hit is
3297/// one row on the side [`keep_half`] keeps, so eight hits are five
3298/// registers. With `AHEAD`, each store first prefetches the line
3299/// [`AHEAD_ROWS`] rows on. `MODE` is [`PLAIN`], [`COUNT`] (rows counted,
3300/// nothing written), or [`BOUNDED`] (no store reaches `out.limit`).
3301///
3302/// # Safety
3303/// `block` indexes every column of `c`. Every buffer of `out` has room
3304/// for `out.n` plus every row of the block plus [`FUSED_SLACK`].
3305#[allow(clippy::incompatible_msrv)]
3306#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3307#[target_feature(enable = "avx512f,avx512vl,popcnt,fma")]
3308#[inline]
3309unsafe fn avx512_fused<
3310    const COLS: bool,
3311    const INLINED: bool,
3312    const AHEAD: bool,
3313    const HALF: bool,
3314    const MODE: u8,
3315>(
3316    c: TileCols,
3317    cut2: f64,
3318    margin: f64,
3319    block: &Block,
3320    words: &RowWords,
3321    out: &mut FusedOut,
3322) {
3323    use std::arch::x86_64::{
3324        __m256i, _mm256_cmp_epu32_mask, _mm256_cmpeq_epi32_mask, _mm256_loadu_si256,
3325        _mm256_mask_blend_epi32, _mm256_maskz_compress_epi32, _mm256_maskz_loadu_epi32,
3326        _mm256_set1_epi32, _mm256_storeu_si256, _mm512_add_pd, _mm512_castpd_si512,
3327        _mm512_castsi256_si512, _mm512_castsi512_si256, _mm512_loadu_pd, _mm512_loadu_si512,
3328        _mm512_mask_blend_epi32, _mm512_mask_cmp_pd_mask, _mm512_mask_set1_epi32,
3329        _mm512_mask_storeu_epi64, _mm512_maskz_compress_pd, _mm512_maskz_loadu_pd, _mm512_mul_pd,
3330        _mm512_permutex2var_epi32, _mm512_permutexvar_epi32, _mm512_permutexvar_pd,
3331        _mm512_set1_epi32, _mm512_set1_pd, _mm512_setr_epi32, _mm512_setr_epi64, _mm512_storeu_pd,
3332        _mm512_storeu_si512, _mm512_sub_pd, _CMP_LT_OQ, _MM_CMPINT_LT,
3333    };
3334    let [sx, sy, sz] = block.shift;
3335    let [ox, oy, oz] = block.delta;
3336    let shift_s = block.shift_s;
3337    let neg = [-shift_s[0], -shift_s[1], -shift_s[2]];
3338    // Dwords 8..16 of the row source: the source id, a zero, S, and -S.
3339    let consts = _mm512_setr_epi32(
3340        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, shift_s[0], shift_s[1], shift_s[2], neg[0], neg[1], neg[2],
3341    );
3342    // Columns: row 2k is (i, j_k, S, d_k) and row 2k + 1 is (j_k, i, -S, d_k).
3343    let ij = _mm512_setr_epi32(0, 16, 0, 17, 0, 18, 0, 19, 0, 20, 0, 21, 0, 22, 0, 23);
3344    let ji = _mm512_setr_epi32(16, 0, 17, 0, 18, 0, 19, 0, 20, 0, 21, 0, 22, 0, 23, 0);
3345    let dup_lo = _mm512_setr_epi64(0, 0, 1, 1, 2, 2, 3, 3);
3346    let dup_hi = _mm512_setr_epi64(4, 4, 5, 5, 6, 6, 7, 7);
3347    let six = [
3348        shift_s[0], shift_s[1], shift_s[2], neg[0], neg[1], neg[2], 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3349    ];
3350    let six = _mm512_loadu_si512(six.as_ptr() as *const _);
3351    let sv = [
3352        _mm512_permutexvar_epi32(
3353            _mm512_setr_epi32(0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3),
3354            six,
3355        ),
3356        _mm512_permutexvar_epi32(
3357            _mm512_setr_epi32(4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1),
3358            six,
3359        ),
3360        _mm512_permutexvar_epi32(
3361            _mm512_setr_epi32(2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5),
3362            six,
3363        ),
3364    ];
3365    let cut_exact = _mm512_set1_pd(cut2);
3366    let mut n = out.n;
3367    // Half list: a target with the source's own index, which only a
3368    // periodic image of the source's own bin holds, keeps the forward row
3369    // exactly when `keep_half` does for this shift.
3370    let own_image = !block.tri && block.j_lo == block.i_lo;
3371    let self_fwd: u8 = if own_image && keep_half(0, 0, shift_s) {
3372        0xff
3373    } else {
3374        0
3375    };
3376    // The shift column of eight half rows, S or -S three dwords a row:
3377    // dwords 0..16 and 16..24 of each pattern.
3378    let (s_lo, n_lo, s_hi, n_hi) = (
3379        _mm512_permutexvar_epi32(
3380            _mm512_setr_epi32(0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0),
3381            six,
3382        ),
3383        _mm512_permutexvar_epi32(
3384            _mm512_setr_epi32(3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3),
3385            six,
3386        ),
3387        _mm512_castsi512_si256(_mm512_permutexvar_epi32(
3388            _mm512_setr_epi32(1, 2, 0, 1, 2, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0),
3389            six,
3390        )),
3391        _mm512_castsi512_si256(_mm512_permutexvar_epi32(
3392            _mm512_setr_epi32(4, 5, 3, 4, 5, 3, 4, 5, 3, 3, 3, 3, 3, 3, 3, 3),
3393            six,
3394        )),
3395    );
3396
3397    macro_rules! emit {
3398        ($lo:expr, $iu:expr, $d2v:expr, $jids:expr) => {{
3399            let lo: u8 = $lo;
3400            let k = lo.count_ones() as usize;
3401            if MODE == COUNT {
3402                n += if HALF { k } else { 2 * k };
3403            } else {
3404                let dc = _mm512_maskz_compress_pd(lo, $d2v);
3405                let jc = _mm256_maskz_compress_epi32(lo, $jids);
3406                if HALF {
3407                    // Hit `h` keeps (i, j_h, S) when i < j_h, or for the source's
3408                    // own image when the shift says so; otherwise (j_h, i, -S).
3409                    let iv8 = _mm256_set1_epi32($iu as i32);
3410                    let mut fwd: u8 = _mm256_cmp_epu32_mask::<_MM_CMPINT_LT>(iv8, jc);
3411                    if self_fwd != 0 {
3412                        fwd |= _mm256_cmpeq_epi32_mask(iv8, jc);
3413                    }
3414                    let mir = !fwd;
3415                    if COLS {
3416                        if AHEAD {
3417                            let at = n + AHEAD_ROWS;
3418                            prefetch(out.ci.wrapping_add(at));
3419                            prefetch(out.cj.wrapping_add(at));
3420                            prefetch(out.cd.wrapping_add(at));
3421                            prefetch(out.cs.wrapping_add(3 * at));
3422                        }
3423                        let bi = _mm256_mask_blend_epi32(fwd, jc, iv8);
3424                        let bj = _mm256_mask_blend_epi32(fwd, iv8, jc);
3425                        let m3 = MIRROR3[mir as usize];
3426                        let slo = _mm512_mask_blend_epi32(m3 as u16, s_lo, n_lo);
3427                        let shi = _mm256_mask_blend_epi32((m3 >> 16) as u8, s_hi, n_hi);
3428                        // Eight-wide stores run past a short tail. Inside one
3429                        // thread the next tile overwrites that slack. On a
3430                        // split list the slack would land in the next thread's
3431                        // rows, so the last tiles copy only the `k` hits.
3432                        if MODE == BOUNDED && n + 8 > out.limit {
3433                            let mut ii = [0i32; 8];
3434                            let mut jj = [0i32; 8];
3435                            let mut dd = [0f64; 8];
3436                            let mut ss = [0i32; 24];
3437                            _mm256_storeu_si256(ii.as_mut_ptr() as *mut _, bi);
3438                            _mm256_storeu_si256(jj.as_mut_ptr() as *mut _, bj);
3439                            _mm512_storeu_pd(dd.as_mut_ptr(), dc);
3440                            _mm512_storeu_si512(ss.as_mut_ptr() as *mut _, slo);
3441                            _mm256_storeu_si256(ss.as_mut_ptr().add(16) as *mut _, shi);
3442                            let keep = k.min(out.limit.saturating_sub(n));
3443                            for h in 0..keep {
3444                                *out.ci.add(n + h) = ii[h];
3445                                *out.cj.add(n + h) = jj[h];
3446                                *out.cd.add(n + h) = dd[h];
3447                                let dst = out.cs.add(3 * (n + h));
3448                                *dst = ss[3 * h];
3449                                *dst.add(1) = ss[3 * h + 1];
3450                                *dst.add(2) = ss[3 * h + 2];
3451                            }
3452                        } else {
3453                            _mm256_storeu_si256(out.ci.add(n) as *mut _, bi);
3454                            _mm256_storeu_si256(out.cj.add(n) as *mut _, bj);
3455                            _mm512_storeu_pd(out.cd.add(n), dc);
3456                            _mm512_storeu_si512(out.cs.add(3 * n) as *mut _, slo);
3457                            _mm256_storeu_si256(out.cs.add(3 * n + 16) as *mut _, shi);
3458                        }
3459                    } else {
3460                        let at = out.rows.add(5 * n);
3461                        let a = _mm512_mask_blend_epi32(
3462                            0x00ff,
3463                            _mm512_mask_set1_epi32(consts, 0x0100, $iu as i32),
3464                            _mm512_castsi256_si512(jc),
3465                        );
3466                        let b = _mm512_castpd_si512(dc);
3467                        let pick = &MIRROR32[mir as usize];
3468                        let regs = (5 * k + 7) / 8;
3469                        for m in 0..regs {
3470                            if AHEAD {
3471                                prefetch(at.add(8 * m).wrapping_add(5 * AHEAD_ROWS));
3472                            }
3473                            let ix = _mm512_mask_blend_epi32(
3474                                pick[m],
3475                                _mm512_loadu_si512(words.half32[0][m].as_ptr() as *const _),
3476                                _mm512_loadu_si512(words.half32[1][m].as_ptr() as *const _),
3477                            );
3478                            _mm512_storeu_si512(
3479                                at.add(8 * m) as *mut _,
3480                                _mm512_permutex2var_epi32(a, ix, b),
3481                            );
3482                        }
3483                    }
3484                    n += k;
3485                } else {
3486                    if COLS {
3487                        let at = n + AHEAD_ROWS;
3488                        if AHEAD {
3489                            prefetch(out.ci.wrapping_add(at));
3490                            prefetch(out.cj.wrapping_add(at));
3491                            prefetch(out.cd.wrapping_add(at));
3492                            prefetch(out.cs.wrapping_add(3 * at));
3493                        }
3494                        let iv = _mm512_set1_epi32($iu as i32);
3495                        let jz = _mm512_castsi256_si512(jc);
3496                        _mm512_storeu_si512(
3497                            out.ci.add(n) as *mut _,
3498                            _mm512_permutex2var_epi32(iv, ij, jz),
3499                        );
3500                        _mm512_storeu_si512(
3501                            out.cj.add(n) as *mut _,
3502                            _mm512_permutex2var_epi32(iv, ji, jz),
3503                        );
3504                        _mm512_storeu_pd(out.cd.add(n), _mm512_permutexvar_pd(dup_lo, dc));
3505                        let so = out.cs.add(3 * n);
3506                        _mm512_storeu_si512(so as *mut _, sv[0]);
3507                        if k > 2 {
3508                            if AHEAD {
3509                                prefetch(out.cs.wrapping_add(3 * at + 16));
3510                            }
3511                            _mm512_storeu_si512(so.add(16) as *mut _, sv[1]);
3512                        }
3513                        if k > 4 {
3514                            if AHEAD {
3515                                prefetch(out.cd.wrapping_add(at + 8));
3516                            }
3517                            _mm512_storeu_pd(out.cd.add(n + 8), _mm512_permutexvar_pd(dup_hi, dc));
3518                        }
3519                        if k > 5 {
3520                            if AHEAD {
3521                                prefetch(out.cs.wrapping_add(3 * at + 32));
3522                            }
3523                            _mm512_storeu_si512(so.add(32) as *mut _, sv[2]);
3524                        }
3525                    } else {
3526                        // Dword sources, as in [`RowWords::index32`]: the eight ids
3527                        // and this source's constants, then the eight distances, so
3528                        // both groups of four hits permute from the same pair.
3529                        let at = out.rows.add(5 * n);
3530                        let a = _mm512_mask_blend_epi32(
3531                            0x00ff,
3532                            _mm512_mask_set1_epi32(consts, 0x0100, $iu as i32),
3533                            _mm512_castsi256_si512(jc),
3534                        );
3535                        let b = _mm512_castpd_si512(dc);
3536                        if MODE == BOUNDED && n + 2 * k + 2 > out.limit {
3537                            // Whole registers reach up to six words past the rows,
3538                            // into another thread's: store only the rows' words.
3539                            for g in 0..2 {
3540                                let words_left = (10 * k).saturating_sub(40 * g);
3541                                for (m, ix) in words.index32[g].iter().enumerate() {
3542                                    let valid = words_left.saturating_sub(8 * m).min(8);
3543                                    if valid == 0 {
3544                                        break;
3545                                    }
3546                                    _mm512_mask_storeu_epi64(
3547                                        at.add(40 * g + 8 * m) as *mut _,
3548                                        ((1u32 << valid) - 1) as u8,
3549                                        _mm512_permutex2var_epi32(
3550                                            a,
3551                                            _mm512_loadu_si512(ix.as_ptr() as *const _),
3552                                            b,
3553                                        ),
3554                                    );
3555                                }
3556                            }
3557                        } else {
3558                            // Two rows per hit are ten words: only the registers that
3559                            // hold them, so a lone hit takes two stores, not five.
3560                            let regs = if k >= 4 { 5 } else { (10 * k + 7) / 8 };
3561                            for (m, ix) in words.index32[0].iter().enumerate().take(regs) {
3562                                if AHEAD {
3563                                    prefetch(at.add(8 * m).wrapping_add(5 * AHEAD_ROWS));
3564                                }
3565                                _mm512_storeu_si512(
3566                                    at.add(8 * m) as *mut _,
3567                                    _mm512_permutex2var_epi32(
3568                                        a,
3569                                        _mm512_loadu_si512(ix.as_ptr() as *const _),
3570                                        b,
3571                                    ),
3572                                );
3573                            }
3574                            if k > 4 {
3575                                let at = at.add(40);
3576                                let regs = if k >= 8 { 5 } else { (10 * (k - 4) + 7) / 8 };
3577                                for (m, ix) in words.index32[1].iter().enumerate().take(regs) {
3578                                    if AHEAD {
3579                                        prefetch(at.add(8 * m).wrapping_add(5 * AHEAD_ROWS));
3580                                    }
3581                                    _mm512_storeu_si512(
3582                                        at.add(8 * m) as *mut _,
3583                                        _mm512_permutex2var_epi32(
3584                                            a,
3585                                            _mm512_loadu_si512(ix.as_ptr() as *const _),
3586                                            b,
3587                                        ),
3588                                    );
3589                                }
3590                            }
3591                        }
3592                    }
3593                    n += 2 * k;
3594                }
3595            }
3596        }};
3597    }
3598    // Direct `dx * dx + dy * dy + dz * dz` for the lanes `load!` just read.
3599    // Separate multiply and add, same association as [`Walk::scan_scalar`].
3600    macro_rules! direct_vec {
3601        ($s:expr, $slot:expr, $tm:expr) => {{
3602            let s = $s;
3603            let px = *c.x.add(s) - sx;
3604            let py = *c.y.add(s) - sy;
3605            let pz = *c.z.add(s) - sz;
3606            let (bx, by, bz) = (_mm512_set1_pd(px), _mm512_set1_pd(py), _mm512_set1_pd(pz));
3607            let (jx, jy, jz) = if $tm == 0xff {
3608                (
3609                    _mm512_loadu_pd(c.x.add($slot)),
3610                    _mm512_loadu_pd(c.y.add($slot)),
3611                    _mm512_loadu_pd(c.z.add($slot)),
3612                )
3613            } else {
3614                (
3615                    _mm512_maskz_loadu_pd($tm, c.x.add($slot)),
3616                    _mm512_maskz_loadu_pd($tm, c.y.add($slot)),
3617                    _mm512_maskz_loadu_pd($tm, c.z.add($slot)),
3618                )
3619            };
3620            let dx = _mm512_sub_pd(jx, bx);
3621            let dy = _mm512_sub_pd(jy, by);
3622            let dz = _mm512_sub_pd(jz, bz);
3623            _mm512_add_pd(
3624                _mm512_add_pd(_mm512_mul_pd(dx, dx), _mm512_mul_pd(dy, dy)),
3625                _mm512_mul_pd(dz, dz),
3626            )
3627        }};
3628    }
3629    // One exact distance, the same products as the scalar walk. The
3630    // expanded box test used to run first and then recompute this.
3631    macro_rules! lanes {
3632        ($s:expr, $slot:expr, $tm:expr, $jids:expr) => {{
3633            let d2v = direct_vec!($s, $slot, $tm);
3634            let lo: u8 = _mm512_mask_cmp_pd_mask($tm, d2v, cut_exact, _CMP_LT_OQ);
3635            if lo != 0 {
3636                let iu = *c.id.add($s);
3637                emit!(lo, iu, d2v, $jids);
3638            }
3639        }};
3640    }
3641    macro_rules! load {
3642        ($slot:expr, $j_hi:expr) => {{
3643            let slot = $slot;
3644            if slot + 8 <= $j_hi {
3645                (0xffu8, _mm256_loadu_si256(c.id.add(slot) as *const __m256i))
3646            } else {
3647                let tm: u8 = ((1u32 << ($j_hi - slot)) - 1) as u8;
3648                (
3649                    tm,
3650                    _mm256_maskz_loadu_epi32(tm, c.id.add(slot) as *const i32),
3651                )
3652            }
3653        }};
3654    }
3655    let j_hi = block.j_hi;
3656    let nvec = (j_hi - block.j_lo + 7) / 8;
3657    // Hits of one source stay together, in slot order, which is the
3658    // scalar walk's order. A run of four sources shares one target load.
3659    // The bin coordinates are three columns, and reading them once per
3660    // source misses L1 once a bin leaves the 48 KB data cache. Hits are
3661    // buffered, then written source by source, so the rows stay in order.
3662    // A bin longer than the buffer keeps the one-source loop.
3663    const QUAD: usize = 4;
3664    const QUAD_CAP: usize = 192;
3665    let quad = !block.tri && block.i_hi - block.i_lo >= QUAD && j_hi - block.j_lo <= QUAD_CAP;
3666    let cull_box = !block.tri && c.cull && nvec >= CULL_RUNS;
3667    /// One target run against `ns` sources. Distances use the same
3668    /// products as [`direct_vec`].
3669    macro_rules! quad_hits {
3670        ($s0:expr, $ns:expr, $slot:expr, $cnt:expr, $idb:expr, $d2b:expr) => {{
3671            let slot = $slot;
3672            let (tm, jx, jy, jz, jids) = if slot + 8 <= j_hi {
3673                (
3674                    0xffu8,
3675                    _mm512_loadu_pd(c.x.add(slot)),
3676                    _mm512_loadu_pd(c.y.add(slot)),
3677                    _mm512_loadu_pd(c.z.add(slot)),
3678                    _mm256_loadu_si256(c.id.add(slot) as *const __m256i),
3679                )
3680            } else {
3681                let tm: u8 = ((1u32 << (j_hi - slot)) - 1) as u8;
3682                (
3683                    tm,
3684                    _mm512_maskz_loadu_pd(tm, c.x.add(slot)),
3685                    _mm512_maskz_loadu_pd(tm, c.y.add(slot)),
3686                    _mm512_maskz_loadu_pd(tm, c.z.add(slot)),
3687                    _mm256_maskz_loadu_epi32(tm, c.id.add(slot) as *const i32),
3688                )
3689            };
3690            for k in 0..$ns {
3691                let sk = $s0 + k;
3692                let px = *c.x.add(sk) - sx;
3693                let py = *c.y.add(sk) - sy;
3694                let pz = *c.z.add(sk) - sz;
3695                let dx = _mm512_sub_pd(jx, _mm512_set1_pd(px));
3696                let dy = _mm512_sub_pd(jy, _mm512_set1_pd(py));
3697                let dz = _mm512_sub_pd(jz, _mm512_set1_pd(pz));
3698                let d2v = _mm512_add_pd(
3699                    _mm512_add_pd(_mm512_mul_pd(dx, dx), _mm512_mul_pd(dy, dy)),
3700                    _mm512_mul_pd(dz, dz),
3701                );
3702                let lo: u8 = _mm512_mask_cmp_pd_mask(tm, d2v, cut_exact, _CMP_LT_OQ);
3703                if lo != 0 {
3704                    let knt = lo.count_ones() as usize;
3705                    let at = $cnt[k];
3706                    _mm512_storeu_pd(
3707                        ($d2b[k].as_mut_ptr() as *mut f64).add(at),
3708                        _mm512_maskz_compress_pd(lo, d2v),
3709                    );
3710                    _mm256_storeu_si256(
3711                        ($idb[k].as_mut_ptr() as *mut i32).add(at) as *mut _,
3712                        _mm256_maskz_compress_epi32(lo, jids),
3713                    );
3714                    $cnt[k] = at + knt;
3715                }
3716            }
3717        }};
3718    }
3719    macro_rules! quad_flush {
3720        ($s0:expr, $ns:expr, $cnt:expr, $idb:expr, $d2b:expr) => {{
3721            for k in 0..$ns {
3722                let iu = *c.id.add($s0 + k);
3723                let mut h = 0usize;
3724                while h < $cnt[k] {
3725                    let m = ($cnt[k] - h).min(8);
3726                    let d2v = _mm512_loadu_pd(($d2b[k].as_ptr() as *const f64).add(h));
3727                    let jids = _mm256_loadu_si256(
3728                        ($idb[k].as_ptr() as *const i32).add(h) as *const __m256i
3729                    );
3730                    let mask = ((1u32 << m) - 1) as u8;
3731                    emit!(mask, iu, d2v, jids);
3732                    h += m;
3733                }
3734            }
3735        }};
3736    }
3737    if quad && cull_box {
3738        let cut_box = _mm512_set1_pd(cut2 + 2.0 * margin);
3739        let zero = std::arch::x86_64::_mm512_setzero_pd();
3740        let mut s = block.i_lo;
3741        while s + QUAD <= block.i_hi {
3742            let mut cnt = [0usize; QUAD];
3743            // Written before they are read. Zeroing them would be a second
3744            // store stream the size of the bin.
3745            let mut idb = [std::mem::MaybeUninit::<[i32; QUAD_CAP + 8]>::uninit(); QUAD];
3746            let mut d2b = [std::mem::MaybeUninit::<[f64; QUAD_CAP + 8]>::uninit(); QUAD];
3747            near_runs!(c, block, nvec, ox, oy, oz, cut_box, zero, s, slot, {
3748                quad_hits!(s, QUAD, slot, cnt, idb, d2b);
3749            });
3750            quad_flush!(s, QUAD, cnt, idb, d2b);
3751            s += QUAD;
3752        }
3753        for s in s..block.i_hi {
3754            near_runs!(c, block, nvec, ox, oy, oz, cut_box, zero, s, slot, {
3755                let (tm, jids) = load!(slot, j_hi);
3756                lanes!(s, slot, tm, jids);
3757            });
3758        }
3759    } else if cull_box {
3760        let cut_box = _mm512_set1_pd(cut2 + 2.0 * margin);
3761        let zero = std::arch::x86_64::_mm512_setzero_pd();
3762        for s in block.i_lo..block.i_hi {
3763            near_runs!(c, block, nvec, ox, oy, oz, cut_box, zero, s, slot, {
3764                let (tm, jids) = load!(slot, j_hi);
3765                lanes!(s, slot, tm, jids);
3766            });
3767        }
3768    } else if quad {
3769        let mut s = block.i_lo;
3770        while s + QUAD <= block.i_hi {
3771            let mut cnt = [0usize; QUAD];
3772            let mut idb = [std::mem::MaybeUninit::<[i32; QUAD_CAP + 8]>::uninit(); QUAD];
3773            let mut d2b = [std::mem::MaybeUninit::<[f64; QUAD_CAP + 8]>::uninit(); QUAD];
3774            let mut slot = block.j_lo;
3775            while slot < j_hi {
3776                quad_hits!(s, QUAD, slot, cnt, idb, d2b);
3777                slot += 8;
3778            }
3779            quad_flush!(s, QUAD, cnt, idb, d2b);
3780            s += QUAD;
3781        }
3782        for s in s..block.i_hi {
3783            let mut slot = block.j_lo;
3784            while slot < j_hi {
3785                let (tm, jids) = load!(slot, j_hi);
3786                lanes!(s, slot, tm, jids);
3787                slot += 8;
3788            }
3789        }
3790    } else if !block.tri {
3791        for s in block.i_lo..block.i_hi {
3792            let mut slot = block.j_lo;
3793            while slot < j_hi {
3794                let (tm, jids) = load!(slot, j_hi);
3795                lanes!(s, slot, tm, jids);
3796                slot += 8;
3797            }
3798        }
3799    } else {
3800        for s in block.i_lo..block.i_hi {
3801            let mut slot = s + 1;
3802            while slot < j_hi {
3803                let (tm, jids) = load!(slot, j_hi);
3804                lanes!(s, slot, tm, jids);
3805                slot += 8;
3806            }
3807        }
3808    }
3809    out.n = n;
3810}
3811
3812#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
3813impl Plan {
3814    fn tile_cols(&self) -> TileCols {
3815        TileCols::of(&self.grid)
3816    }
3817
3818    /// `visit(block)` for the home block and every partner of each bin in
3819    /// `c_lo..c_hi`, in bin order.
3820    fn each_block_in(&self, c_lo: usize, c_hi: usize, mut visit: impl FnMut(&Block)) {
3821        for cell in c_lo..c_hi {
3822            let lo = self.grid.offsets[cell];
3823            let hi = self.grid.offsets[cell + 1];
3824            if lo == hi {
3825                continue;
3826            }
3827            if hi - lo >= 2 {
3828                visit(&Block {
3829                    i_lo: lo,
3830                    i_hi: hi,
3831                    j_lo: lo,
3832                    j_hi: hi,
3833                    shift_s: [0, 0, 0],
3834                    shift: [0.0; 3],
3835                    delta: [0.0; 3],
3836                    tri: true,
3837                    jv: self.grid.boxes.vstart[cell],
3838                    ig: self.grid.boxes.gstart[cell],
3839                });
3840            }
3841            let (p0, p1) = (self.partners.off[cell], self.partners.off[cell + 1]);
3842            for p in &self.partners.items[p0..p1] {
3843                let (j_lo, j_hi) = (self.grid.offsets[p.jc], self.grid.offsets[p.jc + 1]);
3844                if j_lo == j_hi {
3845                    continue;
3846                }
3847                visit(&Block {
3848                    i_lo: lo,
3849                    i_hi: hi,
3850                    j_lo,
3851                    j_hi,
3852                    shift_s: p.shift_s,
3853                    shift: p.shift,
3854                    delta: p.delta,
3855                    tri: false,
3856                    jv: self.grid.boxes.vstart[p.jc],
3857                    ig: self.grid.boxes.gstart[cell],
3858                });
3859            }
3860        }
3861    }
3862
3863    /// Rows a block can add, plus the unkept registers past them.
3864    fn block_room<const HALF: bool>(block: &Block) -> usize {
3865        let pairs = (block.i_hi - block.i_lo) * (block.j_hi - block.j_lo);
3866        if HALF {
3867            pairs + FUSED_SLACK
3868        } else {
3869            2 * pairs + FUSED_SLACK
3870        }
3871    }
3872
3873    /// Rows to reserve before the tile kernel writes, from the walk's
3874    /// estimate; a short estimate grows block by block.
3875    fn fused_guess(&self) -> usize {
3876        let hits = self.walk().guess_hits(self.grid.atoms());
3877        if self.half {
3878            hits + FUSED_SLACK
3879        } else {
3880            2 * hits + FUSED_SLACK
3881        }
3882    }
3883
3884    /// [`Plan::fused`]: every row appended from the tile kernel.
3885    fn fused_rows(&self, words: &RowWords) -> Vec<Pair> {
3886        let _timer = crate::pop::JobTimer::new();
3887        let guess = self.fused_guess();
3888        let mut out: Vec<Pair> = Vec::with_capacity(guess);
3889        advise_huge(&mut out);
3890        let ahead = ahead(guess, std::mem::size_of::<Pair>());
3891        let n = self.fused_sink::<false, _>(words, &mut out, ahead);
3892        // Safety: every row below `n` is written.
3893        unsafe { out.set_len(n) };
3894        out
3895    }
3896
3897    /// [`pairs_within_into`]: fill `out`, growing it only when it is short.
3898    fn fused_into_vec(&self, words: &RowWords, out: &mut Vec<Pair>) {
3899        let _timer = crate::pop::JobTimer::new();
3900        let guess = self.fused_guess();
3901        out.clear();
3902        if out.capacity() < guess {
3903            out.reserve(guess - out.len());
3904        }
3905        advise_huge(out);
3906        let ahead = ahead(out.capacity(), std::mem::size_of::<Pair>());
3907        let n = self.fused_sink::<false, _>(words, out, ahead);
3908        // Safety: every row below `n` is written.
3909        unsafe { out.set_len(n) };
3910    }
3911
3912    /// [`pairs_within_count`]: the tile's row count, with no row stored.
3913    #[cfg(feature = "parallel")]
3914    fn count_rows(&self, words: &RowWords) -> usize {
3915        let mut counter = Counter;
3916        let all = (0, self.grid.offsets.len() - 1, 0);
3917        if self.half {
3918            self.fused_side::<false, true, COUNT, _>(words, &mut counter, false, all)
3919        } else {
3920            self.fused_side::<false, false, COUNT, _>(words, &mut counter, false, all)
3921        }
3922    }
3923
3924    /// The tile kernel over every block into `sink`, for a full or a half
3925    /// list: inlined into its block loop when bins are sparse, and
3926    /// prefetching ahead of its stores when `ahead`. Returns the rows
3927    /// written.
3928    fn fused_sink<const COLS: bool, S: FusedSink>(
3929        &self,
3930        words: &RowWords,
3931        sink: &mut S,
3932        ahead: bool,
3933    ) -> usize {
3934        let all = (0, self.grid.offsets.len() - 1, 0);
3935        if self.half {
3936            self.fused_side::<COLS, true, PLAIN, S>(words, sink, ahead, all)
3937        } else {
3938            self.fused_side::<COLS, false, PLAIN, S>(words, sink, ahead, all)
3939        }
3940    }
3941
3942    /// [`Plan::fused_sink`] for one kind of list, over the bins `range.0`
3943    /// up to `range.1` from row `range.2`, in [`avx512_fused`]'s `MODE`.
3944    fn fused_side<const COLS: bool, const HALF: bool, const MODE: u8, S: FusedSink>(
3945        &self,
3946        words: &RowWords,
3947        sink: &mut S,
3948        ahead: bool,
3949        range: (usize, usize, usize),
3950    ) -> usize {
3951        let cols = self.tile_cols();
3952        let inline = self.grid.atoms() < INLINE_BLOCKS * (self.grid.offsets.len() - 1);
3953        let r = range;
3954        // Safety: AVX-512 was detected for this plan.
3955        unsafe {
3956            match (inline, ahead) {
3957                (true, false) => {
3958                    self.fused_into::<COLS, false, HALF, MODE, S>(cols, words, sink, r)
3959                }
3960                (true, true) => self.fused_into::<COLS, true, HALF, MODE, S>(cols, words, sink, r),
3961                (false, false) => {
3962                    self.fused_blocks::<COLS, false, HALF, MODE, S>(cols, words, sink, r)
3963                }
3964                (false, true) => {
3965                    self.fused_blocks::<COLS, true, HALF, MODE, S>(cols, words, sink, r)
3966                }
3967            }
3968        }
3969    }
3970
3971    /// [`Plan::each_block_in`] with the tile kernel out of line.
3972    ///
3973    /// # Safety
3974    /// AVX-512F, AVX-512VL, POPCNT, and FMA are available.
3975    unsafe fn fused_blocks<
3976        const COLS: bool,
3977        const AHEAD: bool,
3978        const HALF: bool,
3979        const MODE: u8,
3980        S: FusedSink,
3981    >(
3982        &self,
3983        cols: TileCols,
3984        words: &RowWords,
3985        sink: &mut S,
3986        (c_lo, c_hi, n0): (usize, usize, usize),
3987    ) -> usize {
3988        let mut n = n0;
3989        self.each_block_in(c_lo, c_hi, |block| {
3990            let mut fo = sink.room(n, Self::block_room::<HALF>(block));
3991            // Safety: the sink has room for `n` plus the block plus the
3992            // slack, and the features are the caller's.
3993            unsafe {
3994                avx512_fused::<COLS, false, AHEAD, HALF, MODE>(
3995                    cols,
3996                    self.cut2,
3997                    self.margin,
3998                    block,
3999                    words,
4000                    &mut fo,
4001                )
4002            };
4003            n = fo.n;
4004        });
4005        n
4006    }
4007
4008    /// The block loop of [`Plan::fused_sink`] for sparse bins, compiled
4009    /// with the tile's target features so the tile inlines into it:
4010    /// [`Plan::each_block_in`]'s order, the home block of each bin and then
4011    /// its partners.
4012    ///
4013    /// # Safety
4014    /// AVX-512F, AVX-512VL, POPCNT, and FMA are available.
4015    #[allow(clippy::incompatible_msrv)]
4016    #[target_feature(enable = "avx512f,avx512vl,popcnt,fma")]
4017    unsafe fn fused_into<
4018        const COLS: bool,
4019        const AHEAD: bool,
4020        const HALF: bool,
4021        const MODE: u8,
4022        S: FusedSink,
4023    >(
4024        &self,
4025        cols: TileCols,
4026        words: &RowWords,
4027        sink: &mut S,
4028        (c_lo, c_hi, n0): (usize, usize, usize),
4029    ) -> usize {
4030        let mut n = n0;
4031        for cell in c_lo..c_hi {
4032            let (lo, hi) = (self.grid.offsets[cell], self.grid.offsets[cell + 1]);
4033            if lo == hi {
4034                continue;
4035            }
4036            let (p0, p1) = (self.partners.off[cell], self.partners.off[cell + 1]);
4037            for q in p0..=p1 {
4038                let block = if q == p0 {
4039                    if hi - lo < 2 {
4040                        continue;
4041                    }
4042                    Block {
4043                        i_lo: lo,
4044                        i_hi: hi,
4045                        j_lo: lo,
4046                        j_hi: hi,
4047                        shift_s: [0, 0, 0],
4048                        shift: [0.0; 3],
4049                        delta: [0.0; 3],
4050                        tri: true,
4051                        jv: self.grid.boxes.vstart[cell],
4052                        ig: self.grid.boxes.gstart[cell],
4053                    }
4054                } else {
4055                    let p = &self.partners.items[q - 1];
4056                    let (j_lo, j_hi) = (self.grid.offsets[p.jc], self.grid.offsets[p.jc + 1]);
4057                    if j_lo == j_hi {
4058                        continue;
4059                    }
4060                    Block {
4061                        i_lo: lo,
4062                        i_hi: hi,
4063                        j_lo,
4064                        j_hi,
4065                        shift_s: p.shift_s,
4066                        shift: p.shift,
4067                        delta: p.delta,
4068                        tri: false,
4069                        jv: self.grid.boxes.vstart[p.jc],
4070                        ig: self.grid.boxes.gstart[cell],
4071                    }
4072                };
4073                let mut fo = sink.room(n, Self::block_room::<HALF>(&block));
4074                // Safety: the sink has room for `n` plus the block plus the
4075                // slack, and the features are the caller's.
4076                avx512_fused::<COLS, true, AHEAD, HALF, MODE>(
4077                    cols,
4078                    self.cut2,
4079                    self.margin,
4080                    &block,
4081                    words,
4082                    &mut fo,
4083                );
4084                n = fo.n;
4085            }
4086        }
4087        n
4088    }
4089
4090    /// Several threads and a half list of columns. The tile writes eight
4091    /// rows even when fewer hits remain, so the fill uses [`BOUNDED`].
4092    #[cfg(feature = "parallel")]
4093    fn fused_split_columns(&self) -> Option<RowWords> {
4094        if self.threads > 1 && self.half && self.path == Path::Avx512 && self.images.0.is_none() {
4095            RowWords::of_pair()
4096        } else {
4097            None
4098        }
4099    }
4100
4101    /// Several threads, a full list, and AVX-512: each thread counts the
4102    /// rows of its bins, then writes them from the tile kernel in place.
4103    #[cfg(feature = "parallel")]
4104    fn fused_split(&self) -> Option<RowWords> {
4105        if self.threads > 1 && !self.half && self.path == Path::Avx512 && self.images.0.is_none() {
4106            RowWords::of_pair()
4107        } else {
4108            None
4109        }
4110    }
4111
4112    /// The first row of each range of bins in `ranges`, then the total,
4113    /// counted on one thread a range.
4114    #[cfg(feature = "parallel")]
4115    fn fused_offsets(&self, words: &RowWords, ranges: &[(usize, usize)]) -> Vec<usize> {
4116        let counts: Vec<usize> = rayon::broadcast(|ctx| {
4117            ranges.get(ctx.index()).map_or(0, |&(lo, hi)| {
4118                let _timer = crate::pop::JobTimer::new();
4119                if self.half {
4120                    self.fused_side::<false, true, COUNT, _>(
4121                        words,
4122                        &mut Counter,
4123                        false,
4124                        (lo, hi, 0),
4125                    )
4126                } else {
4127                    self.fused_side::<false, false, COUNT, _>(
4128                        words,
4129                        &mut Counter,
4130                        false,
4131                        (lo, hi, 0),
4132                    )
4133                }
4134            })
4135        });
4136        let mut off = Vec::with_capacity(ranges.len() + 1);
4137        off.push(0usize);
4138        for c in counts.iter().take(ranges.len()) {
4139            off.push(off[off.len() - 1] + c);
4140        }
4141        off
4142    }
4143
4144    /// The rows of `ranges[t]` at `off[t]..off[t + 1]` of `base`, written
4145    /// from the tile kernel on thread `t`.
4146    ///
4147    /// # Safety
4148    /// `base` holds `off[ranges.len()]` rows.
4149    #[cfg(feature = "parallel")]
4150    unsafe fn fused_fill(
4151        &self,
4152        words: &RowWords,
4153        base: RowPtr<Pair>,
4154        ranges: &[(usize, usize)],
4155        off: &[usize],
4156    ) {
4157        #[cfg(test)]
4158        FUSED_FILLS.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
4159        rayon::broadcast(|ctx| {
4160            let t = ctx.index();
4161            if let Some(&(lo, hi)) = ranges.get(t) {
4162                let _timer = crate::pop::JobTimer::new();
4163                let mut sink = Fixed {
4164                    rows: base.ptr() as *mut u64,
4165                    limit: off[t + 1],
4166                };
4167                let ahead = ahead(off[t + 1] - off[t], std::mem::size_of::<Pair>());
4168                let n = self.fused_side::<false, false, BOUNDED, _>(
4169                    words,
4170                    &mut sink,
4171                    ahead,
4172                    (lo, hi, off[t]),
4173                );
4174                debug_assert_eq!(n, off[t + 1]);
4175            }
4176        });
4177    }
4178
4179    /// Half-list columns, several threads: count each bin range, then write
4180    /// it from the tile kernel. The last tiles of a range store only the
4181    /// hits that belong to that range.
4182    ///
4183    /// # Safety
4184    /// Every column of `cols` holds `off[ranges.len()]` rows.
4185    #[cfg(feature = "parallel")]
4186    unsafe fn fused_fill_columns(
4187        &self,
4188        words: &RowWords,
4189        cols: ColumnPtrs,
4190        ranges: &[(usize, usize)],
4191        off: &[usize],
4192    ) {
4193        #[cfg(test)]
4194        FUSED_FILLS.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
4195        rayon::broadcast(|ctx| {
4196            let t = ctx.index();
4197            if let Some(&(lo, hi)) = ranges.get(t) {
4198                let _timer = crate::pop::JobTimer::new();
4199                let mut sink = FixedCols {
4200                    ci: cols.i.ptr(),
4201                    cj: cols.j.ptr(),
4202                    cs: cols.shift.ptr(),
4203                    cd: cols.d2.ptr(),
4204                    limit: off[t + 1],
4205                };
4206                let ahead = ahead(off[t + 1] - off[t], COLUMN_BYTES);
4207                let n = self.fused_side::<true, true, BOUNDED, _>(
4208                    words,
4209                    &mut sink,
4210                    ahead,
4211                    (lo, hi, off[t]),
4212                );
4213                debug_assert_eq!(n, off[t + 1]);
4214            }
4215        });
4216    }
4217
4218    /// [`Plan::fused`] into four columns.
4219    fn fused_columns(&self, out: &mut PairColumns) {
4220        let _timer = crate::pop::JobTimer::new();
4221        let words = match RowWords::of_pair() {
4222            Some(w) => w,
4223            None => return self.search().fill_columns(out),
4224        };
4225        out.i.clear();
4226        out.j.clear();
4227        out.shift.clear();
4228        out.dist2.clear();
4229        let guess = self.fused_guess();
4230        out.i.reserve(guess);
4231        out.j.reserve(guess);
4232        out.shift.reserve(guess);
4233        out.dist2.reserve(guess);
4234        out.advise_huge();
4235        let n = self.fused_sink::<true, _>(&words, out, ahead(guess, COLUMN_BYTES));
4236        // Safety: every row below `n` is written in every column.
4237        unsafe {
4238            out.i.set_len(n);
4239            out.j.set_len(n);
4240            out.shift.set_len(n);
4241            out.dist2.set_len(n);
4242        }
4243    }
4244}
4245
4246impl Walk<'_> {
4247    fn scan_block(&self, scratch: &mut Scratch, block: &Block) {
4248        if block.i_lo >= block.i_hi || block.j_lo >= block.j_hi {
4249            return;
4250        }
4251        let ns = block.i_hi - block.i_lo;
4252        let span = block.j_hi - block.j_lo;
4253        // A tile of four by eight is slower than the scalar loop when the
4254        // bin holds one or two atoms. Ice at 3.5 Ă… and the 4096-atom water
4255        // cell are in that regime; the wide tile stays for fuller bins.
4256        if span < 8 || ns < 4 || ns > MAX_SCRATCH / span {
4257            self.scan_scalar(scratch, block);
4258            return;
4259        }
4260        let before = scratch.js.len();
4261        scratch.reserve_more(ns * span + STORE_SLACK);
4262        match self.path {
4263            #[cfg(all(target_arch = "x86_64", linkcell_avx512))]
4264            Path::Avx512 => {
4265                let cols = TileCols::of(self.grid);
4266                // Safety: `select` returned AVX-512, so F, VL, POPCNT, and FMA are on.
4267                unsafe {
4268                    avx512_scan(cols, self.cut2, self.margin, block, scratch);
4269                }
4270            }
4271            #[cfg(target_arch = "x86_64")]
4272            Path::Avx2 => {
4273                let cols = TileCols::of(self.grid);
4274                // Safety: `select` returned AVX2, so AVX2 and FMA are on.
4275                unsafe {
4276                    wide::avx2_scan(cols, self.cut2, self.margin, block, scratch);
4277                }
4278            }
4279            #[cfg(target_arch = "aarch64")]
4280            Path::Neon => {
4281                let cols = TileCols::of(self.grid);
4282                // Safety: NEON is baseline on aarch64, and `select` returned it.
4283                unsafe {
4284                    wide::neon_scan(cols, self.cut2, self.margin, block, scratch);
4285                }
4286            }
4287            _ => {
4288                self.scan_scalar(scratch, block);
4289                return;
4290            }
4291        }
4292        scratch.note(before, block.shift_s);
4293    }
4294
4295    fn scan_scalar(&self, scratch: &mut Scratch, block: &Block) {
4296        let before = scratch.js.len();
4297        let sx = block.shift[0];
4298        let sy = block.shift[1];
4299        let sz = block.shift[2];
4300        for s in block.i_lo..block.i_hi {
4301            let j_lo = if block.tri { s + 1 } else { block.j_lo };
4302            if j_lo >= block.j_hi {
4303                continue;
4304            }
4305            let c = &self.grid.coords;
4306            let i = c.id[s];
4307            let px = c.x[s] - sx;
4308            let py = c.y[s] - sy;
4309            let pz = c.z[s] - sz;
4310            for slot in j_lo..block.j_hi {
4311                let dx = c.x[slot] - px;
4312                let dy = c.y[slot] - py;
4313                let dz = c.z[slot] - pz;
4314                let d2 = dx * dx + dy * dy + dz * dz;
4315                if d2 < self.cut2 {
4316                    let j = c.id[slot];
4317                    if j == i && block.shift_s == [0, 0, 0] {
4318                        continue;
4319                    }
4320                    scratch.push(i, j, d2);
4321                }
4322            }
4323        }
4324        scratch.note(before, block.shift_s);
4325    }
4326
4327    fn append_cell(&self, scratch: &mut Scratch, cell: usize) {
4328        let lo = self.grid.offsets[cell];
4329        let hi = self.grid.offsets[cell + 1];
4330        if lo == hi {
4331            return;
4332        }
4333        if hi - lo >= 2 {
4334            self.scan_block(
4335                scratch,
4336                &Block {
4337                    i_lo: lo,
4338                    i_hi: hi,
4339                    j_lo: lo,
4340                    j_hi: hi,
4341                    shift_s: [0, 0, 0],
4342                    shift: [0.0; 3],
4343                    delta: [0.0; 3],
4344                    tri: true,
4345                    jv: self.grid.boxes.vstart[cell],
4346                    ig: self.grid.boxes.gstart[cell],
4347                },
4348            );
4349        }
4350        let p0 = self.partners.off[cell];
4351        let p1 = self.partners.off[cell + 1];
4352        for partner in &self.partners.items[p0..p1] {
4353            let (j_lo, j_hi) = (
4354                self.grid.offsets[partner.jc],
4355                self.grid.offsets[partner.jc + 1],
4356            );
4357            if j_lo == j_hi {
4358                continue;
4359            }
4360            self.scan_block(
4361                scratch,
4362                &Block {
4363                    i_lo: lo,
4364                    i_hi: hi,
4365                    j_lo,
4366                    j_hi,
4367                    shift_s: partner.shift_s,
4368                    shift: partner.shift,
4369                    delta: partner.delta,
4370                    tri: false,
4371                    jv: self.grid.boxes.vstart[partner.jc],
4372                    ig: self.grid.boxes.gstart[cell],
4373                },
4374            );
4375        }
4376    }
4377
4378    /// Ideal-gas hit count for `n_src` sources, with a quarter more.
4379    /// A denser shell grows the buffer.
4380    fn guess_hits(&self, n_src: usize) -> usize {
4381        let w = self.grid.widths;
4382        let full = (w[0] * w[1] * w[2]).max(1.0e-30);
4383        let radius = self.cut2.sqrt();
4384        let shell = 4.1887902047863905 * radius * radius * radius;
4385        let n = self.grid.atoms().max(1) as f64;
4386        // A rank's atoms fill a block of bins, not the whole cell. The
4387        // gas count uses that block's volume, so the row buffer covers
4388        // the list on the first allocation.
4389        let volume = full * self.occupied_fraction();
4390        let neighbors = (n * shell / volume).ceil().max(1.0).min(n);
4391        ((n_src as f64) * neighbors * 0.5 * 1.25) as usize
4392    }
4393
4394    /// Share of the cell that holds at least one atom, from the bin
4395    /// bounding box. One means the atoms span every axis.
4396    fn occupied_fraction(&self) -> f64 {
4397        let nx = self.grid.n[0];
4398        let ny = self.grid.n[1];
4399        let nz = self.grid.n[2];
4400        if nx <= 0 || ny <= 0 || nz <= 0 {
4401            return 1.0;
4402        }
4403        let ncell = (nx as usize) * (ny as usize) * (nz as usize);
4404        let off = &self.grid.offsets;
4405        if off.len() != ncell + 1 {
4406            return 1.0;
4407        }
4408        let mut min = [i32::MAX; 3];
4409        let mut max = [i32::MIN; 3];
4410        let mut any = false;
4411        for c in 0..ncell {
4412            if off[c + 1] == off[c] {
4413                continue;
4414            }
4415            any = true;
4416            let ix = (c % nx as usize) as i32;
4417            let iy = ((c / nx as usize) % ny as usize) as i32;
4418            let iz = (c / (nx as usize * ny as usize)) as i32;
4419            min[0] = min[0].min(ix);
4420            min[1] = min[1].min(iy);
4421            min[2] = min[2].min(iz);
4422            max[0] = max[0].max(ix);
4423            max[1] = max[1].max(iy);
4424            max[2] = max[2].max(iz);
4425        }
4426        if !any {
4427            return 1.0;
4428        }
4429        let span = [
4430            (max[0] - min[0] + 1) as f64 / f64::from(nx),
4431            (max[1] - min[1] + 1) as f64 / f64::from(ny),
4432            (max[2] - min[2] + 1) as f64 / f64::from(nz),
4433        ];
4434        (span[0] * span[1] * span[2]).clamp(1.0 / ncell as f64, 1.0)
4435    }
4436
4437    fn fill_range(&self, start: usize, end: usize) -> Scratch {
4438        let _timer = crate::pop::JobTimer::new();
4439        let mut scratch = Scratch::new();
4440        let n_src = self.grid.offsets[end] - self.grid.offsets[start];
4441        scratch.reserve_more(self.guess_hits(n_src));
4442        for cell in start..end {
4443            self.append_cell(&mut scratch, cell);
4444        }
4445        scratch
4446    }
4447
4448    /// Hits by cell range: with several threads, thread `k` searches
4449    /// range `k`, so the writer on that thread reads its own cache.
4450    fn collect(&self, threads: usize) -> Vec<Scratch> {
4451        let ncell = self.grid.offsets.len() - 1;
4452        #[cfg(feature = "parallel")]
4453        if threads > 1 && ncell > 1 {
4454            let ranges = cell_ranges(&self.grid.offsets, threads * knobs::chunks());
4455            if ranges.len() > 1 && ranges.len() <= crate::pool_width() {
4456                let found: Vec<Option<Scratch>> = rayon::broadcast(|ctx| {
4457                    ranges
4458                        .get(ctx.index())
4459                        .map(|&(start, end)| self.fill_range(start, end))
4460                });
4461                return found.into_iter().flatten().collect();
4462            }
4463            if ranges.len() > 1 {
4464                use rayon::prelude::*;
4465                return ranges
4466                    .par_iter()
4467                    .map(|&(start, end)| self.fill_range(start, end))
4468                    .collect();
4469            }
4470        }
4471        let _ = threads;
4472        vec![self.fill_range(0, ncell)]
4473    }
4474}
4475
4476#[cfg(feature = "parallel")]
4477fn cell_ranges(offsets: &[usize], threads: usize) -> Vec<(usize, usize)> {
4478    let ncell = offsets.len() - 1;
4479    if ncell == 0 {
4480        return Vec::new();
4481    }
4482    let threads = threads.max(1).min(ncell);
4483    if threads == 1 {
4484        return vec![(0, ncell)];
4485    }
4486    let total = offsets[ncell];
4487    if total == 0 {
4488        return vec![(0, ncell)];
4489    }
4490    let mut ranges = Vec::with_capacity(threads);
4491    let mut start = 0usize;
4492    for t in 1..threads {
4493        let target = total * t / threads;
4494        let mut end = start;
4495        while end < ncell && offsets[end] < target {
4496            end += 1;
4497        }
4498        if end == start {
4499            end = (start + 1).min(ncell);
4500        }
4501        if end <= start {
4502            break;
4503        }
4504        ranges.push((start, end));
4505        start = end;
4506    }
4507    if start < ncell {
4508        ranges.push((start, ncell));
4509    }
4510    ranges
4511}
4512
4513/// Slot columns one wide tile reads, and the [`Boxes`] of its runs.
4514#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
4515#[derive(Clone, Copy)]
4516struct TileCols {
4517    x: *const f64,
4518    y: *const f64,
4519    z: *const f64,
4520    rx: *const f64,
4521    ry: *const f64,
4522    rz: *const f64,
4523    r2: *const f64,
4524    id: *const u32,
4525    cull: bool,
4526    vb: [*const f64; 6],
4527    gb: [*const f64; 6],
4528}
4529
4530#[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
4531impl TileCols {
4532    fn of(grid: &Grid) -> Self {
4533        let c = &grid.coords;
4534        let b = &grid.boxes;
4535        TileCols {
4536            x: c.x.as_ptr(),
4537            y: c.y.as_ptr(),
4538            z: c.z.as_ptr(),
4539            rx: c.rx.as_ptr(),
4540            ry: c.ry.as_ptr(),
4541            rz: c.rz.as_ptr(),
4542            r2: c.r2.as_ptr(),
4543            id: c.id.as_ptr(),
4544            cull: b.on,
4545            vb: std::array::from_fn(|k| b.v[k].as_ptr()),
4546            gb: std::array::from_fn(|k| b.g[k].as_ptr()),
4547        }
4548    }
4549}
4550
4551/// # Safety
4552/// `block` indexes every column of `c`. `scratch` has room for every
4553/// pair in the block plus [`STORE_SLACK`] slots.
4554///
4555/// A source `p` in the block, moved by `block.delta`, is `p'` relative
4556/// to the target bin's corner. Each lane forms
4557/// `t = |r_q|^2 - 2 r_q . p'` with three fused multiply-adds, and that
4558/// `t` only decides the screen. A lane within `margin` of `cut2` is
4559/// recomputed one at a time. Every stored value is the direct
4560/// `|q - (p - S)|^2` of [`Walk::scan_scalar`], separate multiply and add.
4561#[allow(clippy::incompatible_msrv)]
4562#[cfg(all(target_arch = "x86_64", linkcell_avx512))]
4563#[target_feature(enable = "avx512f,avx512vl,popcnt,fma")]
4564#[inline(never)]
4565unsafe fn avx512_scan(c: TileCols, cut2: f64, margin: f64, block: &Block, scratch: &mut Scratch) {
4566    use std::arch::x86_64::{
4567        __m256i, _mm256_loadu_si256, _mm256_maskz_compress_epi32, _mm256_maskz_loadu_epi32,
4568        _mm256_set1_epi32, _mm256_storeu_si256, _mm512_add_pd, _mm512_fmadd_pd, _mm512_loadu_pd,
4569        _mm512_mask_cmp_pd_mask, _mm512_maskz_compress_pd, _mm512_maskz_loadu_pd, _mm512_mul_pd,
4570        _mm512_set1_pd, _mm512_storeu_pd, _mm512_sub_pd, _CMP_LT_OQ,
4571    };
4572    let atom_p = scratch.atom.as_mut_ptr();
4573    let js_p = scratch.js.as_mut_ptr();
4574    let d2_p = scratch.d2.as_mut_ptr();
4575    let mut n = scratch.js.len();
4576    let [sx, sy, sz] = block.shift;
4577    let [ox, oy, oz] = block.delta;
4578    let cut_lo = _mm512_set1_pd(cut2 - margin);
4579    let cut_hi = cut2 + margin;
4580
4581    // Lanes of one source the expanded form cannot decide: the direct
4582    // formula, one lane at a time.
4583    macro_rules! direct {
4584        ($s:expr, $slot:expr, $mask:expr) => {{
4585            let s = $s;
4586            let iu = *c.id.add(s);
4587            let px = *c.x.add(s) - sx;
4588            let py = *c.y.add(s) - sy;
4589            let pz = *c.z.add(s) - sz;
4590            let mut bits: u32 = u32::from($mask);
4591            while bits != 0 {
4592                let slot = $slot + bits.trailing_zeros() as usize;
4593                bits &= bits - 1;
4594                let dx = *c.x.add(slot) - px;
4595                let dy = *c.y.add(slot) - py;
4596                let dz = *c.z.add(slot) - pz;
4597                let d2 = dx * dx + dy * dy + dz * dz;
4598                if d2 < cut2 {
4599                    atom_p.add(n).write(iu);
4600                    js_p.add(n).write(*c.id.add(slot));
4601                    d2_p.add(n).write(d2);
4602                    n += 1;
4603                }
4604            }
4605        }};
4606    }
4607    // A source: its id lane, -2 p', |p'|^2, and the threshold on `t`.
4608    macro_rules! source {
4609        ($s:expr) => {{
4610            let s = $s;
4611            let px = *c.rx.add(s) + ox;
4612            let py = *c.ry.add(s) + oy;
4613            let pz = *c.rz.add(s) + oz;
4614            let pp = px * px + py * py + pz * pz;
4615            (
4616                _mm256_set1_epi32(*c.id.add(s) as i32),
4617                _mm512_set1_pd(-2.0 * px),
4618                _mm512_set1_pd(-2.0 * py),
4619                _mm512_set1_pd(-2.0 * pz),
4620                _mm512_set1_pd(pp),
4621                _mm512_set1_pd(cut_hi - pp),
4622            )
4623        }};
4624    }
4625    // Hit lanes are compressed in a register and stored at full width.
4626    // Lanes past the hit count are scratch that the next store or
4627    // `finish` overwrites; `STORE_SLACK` keeps them inside capacity.
4628    // The occupants of a mesh are distinct atoms, so a zero-shift block
4629    // never pairs an atom with itself: the home cell starts at `s + 1`
4630    // and every partner is another bin.
4631    // Direct `dx * dx + dy * dy + dz * dz` for the lanes `load!` just read.
4632    macro_rules! direct_vec {
4633        ($s:expr, $slot:expr, $tm:expr) => {{
4634            let s = $s;
4635            let px = *c.x.add(s) - sx;
4636            let py = *c.y.add(s) - sy;
4637            let pz = *c.z.add(s) - sz;
4638            let (bx, by, bz) = (_mm512_set1_pd(px), _mm512_set1_pd(py), _mm512_set1_pd(pz));
4639            let (jx, jy, jz) = if $tm == 0xff {
4640                (
4641                    _mm512_loadu_pd(c.x.add($slot)),
4642                    _mm512_loadu_pd(c.y.add($slot)),
4643                    _mm512_loadu_pd(c.z.add($slot)),
4644                )
4645            } else {
4646                (
4647                    _mm512_maskz_loadu_pd($tm, c.x.add($slot)),
4648                    _mm512_maskz_loadu_pd($tm, c.y.add($slot)),
4649                    _mm512_maskz_loadu_pd($tm, c.z.add($slot)),
4650                )
4651            };
4652            let dx = _mm512_sub_pd(jx, bx);
4653            let dy = _mm512_sub_pd(jy, by);
4654            let dz = _mm512_sub_pd(jz, bz);
4655            _mm512_add_pd(
4656                _mm512_add_pd(_mm512_mul_pd(dx, dx), _mm512_mul_pd(dy, dy)),
4657                _mm512_mul_pd(dz, dz),
4658            )
4659        }};
4660    }
4661    macro_rules! lanes {
4662        ($s:expr, $slot:expr, $tm:expr, $src:expr, $jx:expr, $jy:expr, $jz:expr, $jr:expr, $jids:expr) => {{
4663            let (iv, ax, ay, az, pp, thr) = $src;
4664            let t = _mm512_fmadd_pd(
4665                $jz,
4666                az,
4667                _mm512_fmadd_pd($jy, ay, _mm512_fmadd_pd($jx, ax, $jr)),
4668            );
4669            let hi: u8 = _mm512_mask_cmp_pd_mask($tm, t, thr, _CMP_LT_OQ);
4670            if hi != 0 {
4671                let d2_exp = _mm512_add_pd(t, pp);
4672                let lo: u8 = _mm512_mask_cmp_pd_mask(hi, d2_exp, cut_lo, _CMP_LT_OQ);
4673                if lo == hi {
4674                    let d2v = direct_vec!($s, $slot, $tm);
4675                    _mm512_storeu_pd(d2_p.add(n), _mm512_maskz_compress_pd(lo, d2v));
4676                    _mm256_storeu_si256(
4677                        js_p.add(n) as *mut __m256i,
4678                        _mm256_maskz_compress_epi32(lo, $jids),
4679                    );
4680                    _mm256_storeu_si256(atom_p.add(n) as *mut __m256i, iv);
4681                    n += lo.count_ones() as usize;
4682                } else {
4683                    direct!($s, $slot, hi);
4684                }
4685            }
4686        }};
4687    }
4688    macro_rules! load {
4689        ($slot:expr, $j_hi:expr) => {{
4690            let slot = $slot;
4691            if slot + 8 <= $j_hi {
4692                (
4693                    0xffu8,
4694                    _mm512_loadu_pd(c.rx.add(slot)),
4695                    _mm512_loadu_pd(c.ry.add(slot)),
4696                    _mm512_loadu_pd(c.rz.add(slot)),
4697                    _mm512_loadu_pd(c.r2.add(slot)),
4698                    _mm256_loadu_si256(c.id.add(slot) as *const __m256i),
4699                )
4700            } else {
4701                let tm: u8 = ((1u32 << ($j_hi - slot)) - 1) as u8;
4702                (
4703                    tm,
4704                    _mm512_maskz_loadu_pd(tm, c.rx.add(slot)),
4705                    _mm512_maskz_loadu_pd(tm, c.ry.add(slot)),
4706                    _mm512_maskz_loadu_pd(tm, c.rz.add(slot)),
4707                    _mm512_maskz_loadu_pd(tm, c.r2.add(slot)),
4708                    _mm256_maskz_loadu_epi32(tm, c.id.add(slot) as *const i32),
4709                )
4710            }
4711        }};
4712    }
4713
4714    let j_hi = block.j_hi;
4715    let nvec = (j_hi - block.j_lo + 7) / 8;
4716    // One source at a time, then its targets in slot order. That is the
4717    // scalar walk's order. Four sources at once would interleave hits.
4718    let cull_box = !block.tri && c.cull && nvec >= CULL_RUNS;
4719    if cull_box {
4720        let cut_box = _mm512_set1_pd(cut2 + 2.0 * margin);
4721        let zero = std::arch::x86_64::_mm512_setzero_pd();
4722        for s in block.i_lo..block.i_hi {
4723            let s0 = source!(s);
4724            near_runs!(c, block, nvec, ox, oy, oz, cut_box, zero, s, slot, {
4725                let (tm, jx, jy, jz, jr, jids) = load!(slot, j_hi);
4726                lanes!(s, slot, tm, s0, jx, jy, jz, jr, jids);
4727            });
4728        }
4729    } else if !block.tri {
4730        for s in block.i_lo..block.i_hi {
4731            let s0 = source!(s);
4732            let mut slot = block.j_lo;
4733            while slot < j_hi {
4734                let (tm, jx, jy, jz, jr, jids) = load!(slot, j_hi);
4735                lanes!(s, slot, tm, s0, jx, jy, jz, jr, jids);
4736                slot += 8;
4737            }
4738        }
4739    } else {
4740        for s in block.i_lo..block.i_hi {
4741            let s0 = source!(s);
4742            let mut slot = s + 1;
4743            while slot < j_hi {
4744                let (tm, jx, jy, jz, jr, jids) = load!(slot, j_hi);
4745                lanes!(s, slot, tm, s0, jx, jy, jz, jr, jids);
4746                slot += 8;
4747            }
4748        }
4749    }
4750    scratch.finish(n);
4751}
4752
4753#[cfg(test)]
4754mod tests {
4755    use super::*;
4756    use crate::Cell;
4757
4758    #[test]
4759    fn tight_cluster_matches_brute_force() {
4760        // Every pair sits inside the cutoff, and the box is large, so the
4761        // ideal-gas row estimate is a handful. The walk still has to
4762        // return the full list. 520 is above the parallel split.
4763        let n = 520usize;
4764        let mut xyz = vec![[0.0f64; 3]; n];
4765        let g = 9i32;
4766        let mut k = 0usize;
4767        'fill: for z in 0..g {
4768            for y in 0..g {
4769                for x in 0..g {
4770                    if k >= n {
4771                        break 'fill;
4772                    }
4773                    xyz[k] = [x as f64 * 0.05, y as f64 * 0.05, z as f64 * 0.05];
4774                    k += 1;
4775                }
4776            }
4777        }
4778        let sim = Cell::ortho(80.0, 80.0, 80.0).unwrap();
4779        let cutoff = 2.0;
4780        let cut2 = cutoff * cutoff;
4781        let mut brute: Vec<(usize, usize, f64)> = Vec::new();
4782        for i in 0..n {
4783            for j in (i + 1)..n {
4784                let dx = xyz[j][0] - xyz[i][0];
4785                let dy = xyz[j][1] - xyz[i][1];
4786                let dz = xyz[j][2] - xyz[i][2];
4787                let d2 = dx * dx + dy * dy + dz * dz;
4788                if d2 < cut2 {
4789                    brute.push((i, j, d2));
4790                    brute.push((j, i, d2));
4791                }
4792            }
4793        }
4794        brute.sort_by_key(|a| (a.0, a.1));
4795        let run = || pairs_within(&xyz, &sim, cutoff, None, None, false).unwrap();
4796        #[cfg(feature = "parallel")]
4797        let got = {
4798            let pool = rayon::ThreadPoolBuilder::new()
4799                .num_threads(4)
4800                .build()
4801                .unwrap();
4802            pool.install(run)
4803        };
4804        #[cfg(not(feature = "parallel"))]
4805        let got = run();
4806        let mut rows: Vec<(usize, usize, f64)> = got.iter().map(|p| (p.i, p.j, p.dist2)).collect();
4807        rows.sort_by_key(|a| (a.0, a.1));
4808        assert_eq!(rows.len(), n * (n - 1));
4809        assert_eq!(rows.len(), brute.len());
4810        for (got_row, brute_row) in rows.iter().zip(brute.iter()) {
4811            assert_eq!(got_row.0, brute_row.0);
4812            assert_eq!(got_row.1, brute_row.1);
4813            assert!((got_row.2 - brute_row.2).abs() < 1e-9);
4814        }
4815    }
4816
4817    /// Run `f` on a pool of `threads` workers.
4818    fn on_threads<R: Send>(threads: usize, f: impl FnOnce() -> R + Send) -> R {
4819        #[cfg(feature = "parallel")]
4820        {
4821            rayon::ThreadPoolBuilder::new()
4822                .num_threads(threads)
4823                .build()
4824                .unwrap()
4825                .install(f)
4826        }
4827        #[cfg(not(feature = "parallel"))]
4828        {
4829            let _ = threads;
4830            f()
4831        }
4832    }
4833
4834    fn row_keys(rows: &[Pair]) -> Vec<(usize, usize, [i32; 3], u64)> {
4835        let mut k: Vec<_> = rows
4836            .iter()
4837            .map(|p| (p.i, p.j, p.shift, p.dist2.to_bits()))
4838            .collect();
4839        k.sort();
4840        k
4841    }
4842
4843    #[test]
4844    fn one_thread_and_eight_write_the_same_rows() {
4845        // 1000 jittered points: the one-thread call writes rows straight
4846        // from the tile kernel, the eight-thread call buffers hits first.
4847        let sim = Cell::ortho(18.0, 17.0, 19.0).unwrap();
4848        let mut xyz = Vec::new();
4849        let mut state = 0x9e37_79b9_7f4a_7c15u64;
4850        let mut next = || {
4851            state ^= state << 13;
4852            state ^= state >> 7;
4853            state ^= state << 17;
4854            (state >> 11) as f64 / (1u64 << 53) as f64
4855        };
4856        for iz in 0..10 {
4857            for iy in 0..10 {
4858                for ix in 0..10 {
4859                    xyz.push([
4860                        (ix as f64 + 0.3 * next()) * 1.8,
4861                        (iy as f64 + 0.3 * next()) * 1.7,
4862                        (iz as f64 + 0.3 * next()) * 1.9,
4863                    ]);
4864                }
4865            }
4866        }
4867        for half in [false, true] {
4868            let one = on_threads(1, || {
4869                pairs_within(&xyz, &sim, 4.0, None, None, half).unwrap()
4870            });
4871            let eight = on_threads(8, || {
4872                pairs_within(&xyz, &sim, 4.0, None, None, half).unwrap()
4873            });
4874            assert_eq!(row_keys(&one), row_keys(&eight), "half={half}");
4875            let mut c1 = PairColumns::default();
4876            let mut c8 = PairColumns::default();
4877            on_threads(1, || {
4878                pairs_within_columns(&xyz, &sim, 4.0, None, None, half, &mut c1).unwrap()
4879            });
4880            on_threads(8, || {
4881                pairs_within_columns(&xyz, &sim, 4.0, None, None, half, &mut c8).unwrap()
4882            });
4883            let cols = |c: &PairColumns| {
4884                let mut k: Vec<_> = (0..c.len())
4885                    .map(|t| {
4886                        (
4887                            c.i[t] as usize,
4888                            c.j[t] as usize,
4889                            c.shift[t],
4890                            c.dist2[t].to_bits(),
4891                        )
4892                    })
4893                    .collect();
4894                k.sort();
4895                k
4896            };
4897            assert_eq!(cols(&c1), row_keys(&one), "columns half={half}");
4898            assert_eq!(cols(&c8), row_keys(&one), "columns eight half={half}");
4899        }
4900    }
4901
4902    #[test]
4903    fn sub_cells_keep_the_same_rows_in_the_same_order_on_eight_threads() {
4904        // 64 atoms per bin, so each bin is sorted by 4x4x4 sub-cells, and
4905        // above the threaded-bins threshold, so eight threads sort them in
4906        // a third pass. Atom order is shuffled, so it does not follow position.
4907        let sim = Cell::ortho(18.0, 18.0, 18.0).unwrap();
4908        let mut state = 0x5851_f42d_4c95_7f2du64;
4909        let mut next = || {
4910            state ^= state << 13;
4911            state ^= state >> 7;
4912            state ^= state << 17;
4913            state
4914        };
4915        let mut xyz = Vec::new();
4916        for iz in 0..16 {
4917            for iy in 0..16 {
4918                for ix in 0..16 {
4919                    let j = |v: u64| 0.3 * ((v >> 11) as f64 / (1u64 << 53) as f64 - 0.5);
4920                    xyz.push([
4921                        (ix as f64 + 0.5 + j(next())) * 1.125,
4922                        (iy as f64 + 0.5 + j(next())) * 1.125,
4923                        (iz as f64 + 0.5 + j(next())) * 1.125,
4924                    ]);
4925                }
4926            }
4927        }
4928        for i in (1..xyz.len()).rev() {
4929            let k = (next() % (i as u64 + 1)) as usize;
4930            xyz.swap(i, k);
4931        }
4932        assert!(xyz.len() >= PARALLEL_GRID);
4933        for half in [false, true] {
4934            let one = on_threads(1, || {
4935                pairs_within(&xyz, &sim, 4.0, None, None, half).unwrap()
4936            });
4937            let eight = on_threads(8, || {
4938                pairs_within(&xyz, &sim, 4.0, None, None, half).unwrap()
4939            });
4940            assert_eq!(one.len(), eight.len(), "half={half}");
4941            assert!(one == eight, "half={half}: rows differ in content or order");
4942        }
4943    }
4944
4945    #[test]
4946    fn box_culling_keeps_every_row_in_order() {
4947        // 1100 random points in boxes three bins a side at a 3 Ă… cutoff:
4948        // about 40 atoms per bin, so the tile kernel tests run boxes, on
4949        // the threaded bins too. Then a 1 Ă… cubic lattice with the cutoff
4950        // on its sqrt(11) shell and every coordinate a few ulps off, so
4951        // thousands of pairs sit within the margin of the cutoff.
4952        let mut state = 0x2545_f491_4f6c_dd1du64;
4953        let mut next = || {
4954            state ^= state << 13;
4955            state ^= state >> 7;
4956            state ^= state << 17;
4957            state
4958        };
4959        let mut unit = || (next() >> 11) as f64 / (1u64 << 53) as f64;
4960        let mut systems = Vec::new();
4961        for sim in [
4962            Cell::ortho(9.3, 9.6, 9.9).unwrap(),
4963            Cell::from_vectors(
4964                [9.6, 0.0, 0.0],
4965                [1.2, 9.5, 0.0],
4966                [-0.8, 0.9, 9.7],
4967                [0.5, -0.3, 0.2],
4968            )
4969            .unwrap(),
4970        ] {
4971            let xyz: Vec<[f64; 3]> = (0..1100)
4972                .map(|_| sim.cartesian([1.2 * unit() - 0.1, unit(), 1.1 * unit() - 0.05]))
4973                .collect();
4974            systems.push((sim, xyz, 3.0));
4975        }
4976        let mut lattice = Vec::new();
4977        for iz in 0..10 {
4978            for iy in 0..10 {
4979                for ix in 0..10 {
4980                    let mut p = [ix as f64 + 0.5, iy as f64 + 0.5, iz as f64 + 0.5];
4981                    for v in p.iter_mut() {
4982                        let ulps = (next() % 13) as i64 - 6;
4983                        *v = f64::from_bits((v.to_bits() as i64 + ulps) as u64);
4984                    }
4985                    lattice.push(p);
4986                }
4987            }
4988        }
4989        let shell = 11.0f64.sqrt();
4990        systems.push((Cell::ortho(10.0, 10.0, 10.0).unwrap(), lattice, shell));
4991        let before = CULL_SKIPS.load(std::sync::atomic::Ordering::Relaxed);
4992        for (sim, xyz, cutoff) in &systems {
4993            let (sim, cutoff) = (sim, *cutoff);
4994            let mask: Vec<bool> = (0..xyz.len()).map(|k| k % 9 != 4).collect();
4995            if cutoff == shell {
4996                let rows = pairs_within(xyz, sim, cutoff, None, None, false).unwrap();
4997                let near = rows
4998                    .iter()
4999                    .filter(|p| (p.dist2 - cutoff * cutoff).abs() < 1e-12)
5000                    .count();
5001                assert!(near > 1000, "only {near} rows near the cutoff");
5002            }
5003            for threads in [1, 8] {
5004                for half in [false, true] {
5005                    for mask in [None, Some(mask.as_slice())] {
5006                        let run = |cull: bool| {
5007                            NO_CULL.store(!cull, std::sync::atomic::Ordering::Relaxed);
5008                            let (rows, cols) = on_threads(threads, || {
5009                                let rows =
5010                                    pairs_within(xyz, sim, cutoff, mask, None, half).unwrap();
5011                                let mut cols = PairColumns::default();
5012                                pairs_within_columns(xyz, sim, cutoff, mask, None, half, &mut cols)
5013                                    .unwrap();
5014                                (rows, cols)
5015                            });
5016                            NO_CULL.store(false, std::sync::atomic::Ordering::Relaxed);
5017                            (rows, cols)
5018                        };
5019                        let (culled, culled_cols) = run(true);
5020                        let (plain, plain_cols) = run(false);
5021                        let what = format!("threads={threads} half={half} mask={}", mask.is_some());
5022                        assert!(culled.len() > 1000, "{what}");
5023                        assert!(culled == plain, "{what}: rows differ in content or order");
5024                        assert_eq!(culled_cols.i, plain_cols.i, "{what}");
5025                        assert_eq!(culled_cols.j, plain_cols.j, "{what}");
5026                        assert_eq!(culled_cols.shift, plain_cols.shift, "{what}");
5027                        let bits = |c: &PairColumns| -> Vec<u64> {
5028                            c.dist2.iter().map(|d| d.to_bits()).collect()
5029                        };
5030                        assert_eq!(bits(&culled_cols), bits(&plain_cols), "{what}");
5031                    }
5032                }
5033            }
5034        }
5035        let _ = before;
5036        let (sim, xyz, cutoff) = &systems[0];
5037        for path in crate::simd::paths_to_compare() {
5038            if path == Path::Scalar {
5039                continue;
5040            }
5041            let at = CULL_SKIPS.load(std::sync::atomic::Ordering::Relaxed);
5042            on_threads(1, || {
5043                let _guard = crate::simd::force(path);
5044                let _ = pairs_within(xyz, sim, *cutoff, None, None, false).unwrap();
5045            });
5046            let skipped = CULL_SKIPS.load(std::sync::atomic::Ordering::Relaxed) - at;
5047            assert!(skipped > 0, "{path:?} skipped no target run");
5048        }
5049    }
5050
5051    #[test]
5052    fn vector_fold_matches_fold_point_bit_for_bit() {
5053        let cells = [
5054            Cell::ortho(18.0, 17.0, 19.0).unwrap(),
5055            Cell::from_vectors(
5056                [10.0, 0.0, 0.0],
5057                [5.0, 8.660254037844386, 0.0],
5058                [1.0, -2.0, 9.5],
5059                [0.3, -1.0, 2.0],
5060            )
5061            .unwrap(),
5062            Cell::from_vectors(
5063                [9.0, 3.0, 2.0],
5064                [1.0, 9.0, -2.0],
5065                [-1.5, 2.0, 9.5],
5066                [0.0; 3],
5067            )
5068            .unwrap(),
5069        ];
5070        let mut state = 0x2545_f491_4f6c_dd1du64;
5071        let mut next = || {
5072            state ^= state << 13;
5073            state ^= state >> 7;
5074            state ^= state << 17;
5075            (state >> 11) as f64 / (1u64 << 53) as f64
5076        };
5077        for sim in &cells {
5078            let mut xyz: Vec<[f64; 3]> = (0..203)
5079                .map(|_| {
5080                    [
5081                        (next() - 0.3) * 60.0,
5082                        (next() - 0.7) * 45.0,
5083                        (next() - 0.5) * 80.0,
5084                    ]
5085                })
5086                .collect();
5087            let w = sim.widths();
5088            xyz.extend_from_slice(&[
5089                [0.0; 3],
5090                [w[0], w[1], w[2]],
5091                [-0.0, -1e-300, 1e-300],
5092                [w[0] * 0.5, -w[1], 3.0 * w[2]],
5093            ]);
5094            let n = [5, 4, 7];
5095            for sub in [1, 2, 4] {
5096                let keys = Keys { n, sub };
5097                let nkey = 140 * keys.per_bin();
5098                let mut fold = FoldCols::default();
5099                fold.clear_for(xyz.len());
5100                let fp = fold.ptrs();
5101                let mut count = vec![0u32; nkey];
5102                fold_range(
5103                    sim,
5104                    &xyz,
5105                    None,
5106                    keys,
5107                    false,
5108                    crate::simd::select(),
5109                    0,
5110                    xyz.len(),
5111                    fp,
5112                    &mut count,
5113                );
5114                let mut want_count = vec![0u32; nkey];
5115                for (k, r) in xyz.iter().enumerate() {
5116                    let (q, b) = bins::fold_point(sim, *r, keys.fine());
5117                    let key = keys.key(b);
5118                    want_count[key] += 1;
5119                    // Safety: the fold wrote every atom.
5120                    let (p, got) = unsafe { fp.get(k) };
5121                    assert_eq!(got, key, "atom {k} sub {sub}");
5122                    for (a, (got, want)) in p.iter().zip(q).enumerate() {
5123                        assert_eq!(got.to_bits(), want.to_bits(), "atom {k} axis {a}");
5124                    }
5125                }
5126                assert_eq!(count, want_count);
5127            }
5128        }
5129    }
5130
5131    #[test]
5132    fn dense_cluster_on_several_threads_matches_one() {
5133        // The ideal-gas estimate sees 4520 atoms in a 20 Ă… box and splits
5134        // the walk; 520 of them sit inside 0.4 Ă…, so their bin holds far
5135        // more pairs than the estimate.
5136        let sim = Cell::ortho(20.0, 20.0, 20.0).unwrap();
5137        let mut xyz = Vec::new();
5138        'fill: for z in 0..9 {
5139            for y in 0..9 {
5140                for x in 0..9 {
5141                    if xyz.len() == 520 {
5142                        break 'fill;
5143                    }
5144                    xyz.push([
5145                        10.0 + x as f64 * 0.05,
5146                        10.0 + y as f64 * 0.05,
5147                        10.0 + z as f64 * 0.05,
5148                    ]);
5149                }
5150            }
5151        }
5152        for z in 0..16 {
5153            for y in 0..16 {
5154                for x in 0..16 {
5155                    if xyz.len() == 4520 {
5156                        break;
5157                    }
5158                    xyz.push([
5159                        x as f64 * 1.25 + 0.31,
5160                        y as f64 * 1.25 + 0.17,
5161                        z as f64 * 1.25 + 0.53,
5162                    ]);
5163                }
5164            }
5165        }
5166        #[cfg(feature = "parallel")]
5167        assert!(hit_estimate(xyz.len(), &sim, 2.0) >= PARALLEL_PAIRS);
5168        let one = on_threads(1, || {
5169            pairs_within(&xyz, &sim, 2.0, None, None, false).unwrap()
5170        });
5171        let eight = on_threads(8, || {
5172            pairs_within(&xyz, &sim, 2.0, None, None, false).unwrap()
5173        });
5174        assert_eq!(row_keys(&one), row_keys(&eight));
5175        let cluster = eight.iter().filter(|p| p.i < 520 && p.j < 520).count();
5176        assert_eq!(cluster, 520 * 519);
5177    }
5178
5179    #[test]
5180    fn one_thread_matches_the_shift_scan() {
5181        let sim = Cell::ortho(18.0, 18.0, 18.0).unwrap();
5182        let mut xyz = Vec::new();
5183        for iz in 0..9 {
5184            for iy in 0..9 {
5185                for ix in 0..9 {
5186                    xyz.push([
5187                        (ix as f64 + 0.5) * 2.0,
5188                        (iy as f64 + 0.5) * 2.0,
5189                        (iz as f64 + 0.5) * 2.0,
5190                    ]);
5191                }
5192            }
5193        }
5194        let cutoff = 4.0;
5195        let got = on_threads(1, || {
5196            pairs_within(&xyz, &sim, cutoff, None, None, false).unwrap()
5197        });
5198        let mut keys: Vec<_> = got.iter().map(|p| (p.i, p.j, p.shift)).collect();
5199        keys.sort();
5200        let mut want = Vec::new();
5201        for i in 0..xyz.len() {
5202            for j in 0..xyz.len() {
5203                for na in -1..=1 {
5204                    for nb in -1..=1 {
5205                        for nc in -1..=1 {
5206                            if i == j && na == 0 && nb == 0 && nc == 0 {
5207                                continue;
5208                            }
5209                            let d2 =
5210                                sim.dist2_shifted(xyz[i], xyz[j], sim.lattice_shift(na, nb, nc));
5211                            if d2 < cutoff * cutoff {
5212                                want.push((i, j, [na, nb, nc]));
5213                            }
5214                        }
5215                    }
5216                }
5217            }
5218        }
5219        want.sort();
5220        assert_eq!(keys, want);
5221        for p in &got {
5222            let d2 = sim.dist2_shifted(
5223                xyz[p.i],
5224                xyz[p.j],
5225                sim.lattice_shift(p.shift[0], p.shift[1], p.shift[2]),
5226            );
5227            assert!((p.dist2 - d2).abs() < 1e-9);
5228        }
5229    }
5230
5231    #[test]
5232    fn columns_hold_the_same_rows() {
5233        let sim = Cell::ortho(18.0, 18.0, 18.0).unwrap();
5234        let mut xyz = Vec::new();
5235        for iz in 0..9 {
5236            for iy in 0..9 {
5237                for ix in 0..9 {
5238                    xyz.push([
5239                        ix as f64 * 2.0 + 0.3,
5240                        iy as f64 * 2.0 + 0.1,
5241                        iz as f64 * 2.0 + 0.7,
5242                    ]);
5243                }
5244            }
5245        }
5246        let mut cols = PairColumns::default();
5247        for half in [false, true] {
5248            let rows = pairs_within(&xyz, &sim, 4.0, None, None, half).unwrap();
5249            pairs_within_columns(&xyz, &sim, 4.0, None, None, half, &mut cols).unwrap();
5250            assert_eq!(cols.len(), rows.len());
5251            let mut a: Vec<_> = rows
5252                .iter()
5253                .map(|p| (p.i as i32, p.j as i32, p.shift, p.dist2.to_bits()))
5254                .collect();
5255            let mut b: Vec<_> = (0..cols.len())
5256                .map(|t| (cols.i[t], cols.j[t], cols.shift[t], cols.dist2[t].to_bits()))
5257                .collect();
5258            a.sort();
5259            b.sort();
5260            assert_eq!(a, b, "half={half}");
5261        }
5262    }
5263
5264    #[test]
5265    fn sparse_bins_write_the_same_rows_on_one_thread_and_eight() {
5266        // Under eight atoms a bin, one thread runs the tile inlined into its
5267        // block loop, for rows and for columns; several threads buffer hits.
5268        // 3000 atoms in a 40 A cell: about three a bin, and enough pairs
5269        // that a wide pool splits the walk. A two-CPU machine has no
5270        // eight-wide pool, so the comparison uses the machine width.
5271        let cpus = std::thread::available_parallelism()
5272            .map(|n| n.get())
5273            .unwrap_or(1);
5274        let width = cpus.min(8);
5275        if width < 2 {
5276            return;
5277        }
5278        let cells = [
5279            Cell::ortho(40.0, 39.0, 41.0).unwrap(),
5280            Cell::from_vectors(
5281                [40.0, 0.0, 0.0],
5282                [6.0, 39.0, 0.0],
5283                [-4.0, 3.0, 40.5],
5284                [0.3, 0.0, -0.2],
5285            )
5286            .unwrap(),
5287        ];
5288        let mut state = 0x6a09_e667_f3bc_c908u64;
5289        let mut unit = || {
5290            state ^= state << 13;
5291            state ^= state >> 7;
5292            state ^= state << 17;
5293            (state >> 11) as f64 / (1u64 << 53) as f64
5294        };
5295        for sim in &cells {
5296            let xyz: Vec<[f64; 3]> = (0..3000)
5297                .map(|_| sim.cartesian([unit(), unit(), unit()]))
5298                .collect();
5299            let hits = hit_estimate(xyz.len(), sim, 4.0);
5300            if on_threads(width, || walk_threads(hits)) <= 1 {
5301                return;
5302            }
5303            for half in [false, true] {
5304                let (one, one_cols) = on_threads(1, || {
5305                    let rows = pairs_within(&xyz, sim, 4.0, None, None, half).unwrap();
5306                    let mut cols = PairColumns::default();
5307                    pairs_within_columns(&xyz, sim, 4.0, None, None, half, &mut cols).unwrap();
5308                    (rows, cols)
5309                });
5310                let eight = on_threads(width, || {
5311                    pairs_within(&xyz, sim, 4.0, None, None, half).unwrap()
5312                });
5313                assert!(one.len() > 10_000, "half={half}");
5314                assert!(one == eight, "half={half}: rows differ in content or order");
5315                assert_eq!(one_cols.len(), one.len());
5316                for (t, p) in one.iter().enumerate() {
5317                    assert_eq!(
5318                        (
5319                            one_cols.i[t],
5320                            one_cols.j[t],
5321                            one_cols.shift[t],
5322                            one_cols.dist2[t].to_bits()
5323                        ),
5324                        (p.i as i32, p.j as i32, p.shift, p.dist2.to_bits()),
5325                        "half={half} row {t}"
5326                    );
5327                }
5328            }
5329        }
5330    }
5331
5332    #[test]
5333    fn half_rows_keep_their_side_on_periodic_images() {
5334        // Cells narrower than the cutoff: every block is an image of the
5335        // source's own bin, so a target can carry the source's own index
5336        // and the shift picks the side. One thread writes the half list
5337        // from the tile; eight threads buffer hits; both must be the full
5338        // list's rows that `keep_half` keeps, bit for bit, in one order.
5339        let cells = [
5340            Cell::ortho(6.0, 6.5, 7.0).unwrap(),
5341            Cell::from_vectors(
5342                [6.5, 0.0, 0.0],
5343                [1.5, 6.0, 0.0],
5344                [-1.0, 0.8, 7.0],
5345                [0.1, 0.0, 0.0],
5346            )
5347            .unwrap(),
5348        ];
5349        let mut state = 0x3c6e_f372_fe94_f82bu64;
5350        let mut unit = || {
5351            state ^= state << 13;
5352            state ^= state >> 7;
5353            state ^= state << 17;
5354            (state >> 11) as f64 / (1u64 << 53) as f64
5355        };
5356        let key = |p: &Pair| (p.i, p.j, p.shift, p.dist2.to_bits());
5357        for sim in &cells {
5358            let xyz: Vec<[f64; 3]> = (0..250)
5359                .map(|_| sim.cartesian([unit(), unit(), unit()]))
5360                .collect();
5361            let one = on_threads(1, || {
5362                pairs_within(&xyz, sim, 7.5, None, None, true).unwrap()
5363            });
5364            let eight = on_threads(8, || {
5365                pairs_within(&xyz, sim, 7.5, None, None, true).unwrap()
5366            });
5367            let full = on_threads(1, || {
5368                pairs_within(&xyz, sim, 7.5, None, None, false).unwrap()
5369            });
5370            assert!(
5371                one.iter().any(|p| p.i == p.j),
5372                "no periodic self-image rows"
5373            );
5374            assert!(one == eight, "one thread and eight differ");
5375            let mut want: Vec<_> = full
5376                .iter()
5377                .filter(|p| keep_half(p.i, p.j, p.shift))
5378                .map(key)
5379                .collect();
5380            let mut got: Vec<_> = one.iter().map(key).collect();
5381            want.sort();
5382            got.sort();
5383            assert_eq!(got, want);
5384            let mut cols = PairColumns::default();
5385            on_threads(1, || {
5386                pairs_within_columns(&xyz, sim, 7.5, None, None, true, &mut cols).unwrap()
5387            });
5388            assert_eq!(cols.len(), one.len());
5389            for (t, p) in one.iter().enumerate() {
5390                assert_eq!(
5391                    (cols.i[t], cols.j[t], cols.shift[t], cols.dist2[t].to_bits()),
5392                    (p.i as i32, p.j as i32, p.shift, p.dist2.to_bits()),
5393                    "column row {t}"
5394                );
5395            }
5396        }
5397    }
5398
5399    /// Tests that set [`AHEAD_TEST`] take this, so one does not turn the
5400    /// other's forcing off.
5401    static AHEAD_LOCK: std::sync::Mutex<()> = std::sync::Mutex::new(());
5402
5403    #[test]
5404    fn split_tile_fill_writes_the_one_thread_rows() {
5405        let _held = AHEAD_LOCK.lock().unwrap_or_else(|e| e.into_inner());
5406        // Each thread counts its bins' rows, then the tile writes them at
5407        // their offset, under a mask at the end of each range: the rows,
5408        // their order, and their bits must be the one-thread tile's, on
5409        // full bins with box culling, sparse bins, a sheared cell, and a
5410        // mask.
5411        use std::sync::atomic::Ordering::Relaxed;
5412        let mut state = 0xa54f_f53a_5f1d_36f1u64;
5413        let mut unit = || {
5414            state ^= state << 13;
5415            state ^= state >> 7;
5416            state ^= state << 17;
5417            (state >> 11) as f64 / (1u64 << 53) as f64
5418        };
5419        let cells = [
5420            Cell::ortho(18.0, 17.0, 19.0).unwrap(),
5421            Cell::from_vectors(
5422                [18.0, 0.0, 0.0],
5423                [3.0, 17.5, 0.0],
5424                [-2.0, 1.5, 18.5],
5425                [0.2, -0.1, 0.0],
5426            )
5427            .unwrap(),
5428            Cell::ortho(40.0, 39.0, 41.0).unwrap(),
5429        ];
5430        // The fill needs the pool and AVX-512; elsewhere the rows still
5431        // match through the buffered writers.
5432        let split = cfg!(all(
5433            feature = "parallel",
5434            target_arch = "x86_64",
5435            linkcell_avx512
5436        )) && Path::Avx512.usable();
5437        for (c, sim) in cells.iter().enumerate() {
5438            let n = if c == 2 { 3000 } else { 4000 };
5439            let xyz: Vec<[f64; 3]> = (0..n)
5440                .map(|_| sim.cartesian([unit(), unit(), unit()]))
5441                .collect();
5442            let mask: Vec<bool> = (0..n).map(|k| k % 7 != 3).collect();
5443            for m in [None, Some(mask.as_slice())] {
5444                let one = on_threads(1, || pairs_within(&xyz, sim, 4.0, m, None, false).unwrap());
5445                let fills = FUSED_FILLS.load(Relaxed);
5446                AHEAD_TEST.store(2, Relaxed);
5447                let eight = on_threads(8, || pairs_within(&xyz, sim, 4.0, m, None, false).unwrap());
5448                AHEAD_TEST.store(0, Relaxed);
5449                assert!(
5450                    !split || FUSED_FILLS.load(Relaxed) > fills,
5451                    "cell {c}: the split fill did not run"
5452                );
5453                assert!(one.len() > 10_000);
5454                assert!(one == eight, "cell {c} mask={}", m.is_some());
5455            }
5456        }
5457    }
5458
5459    #[test]
5460    fn prefetching_writers_write_the_same_rows_in_order() {
5461        let _held = AHEAD_LOCK.lock().unwrap_or_else(|e| e.into_inner());
5462        // Every writer with its prefetch forced on and forced off: the
5463        // tile kernel (out of line with full bins, inlined with sparse
5464        // ones) for rows and columns on one thread, and the buffered
5465        // writers for rows, columns, and half lists on eight.
5466        use std::sync::atomic::Ordering::Relaxed;
5467        let mut state = 0xbb67_ae85_84ca_a73bu64;
5468        let mut unit = || {
5469            state ^= state << 13;
5470            state ^= state >> 7;
5471            state ^= state << 17;
5472            (state >> 11) as f64 / (1u64 << 53) as f64
5473        };
5474        let dense = Cell::ortho(18.0, 17.0, 19.0).unwrap();
5475        let sparse = Cell::ortho(40.0, 39.0, 41.0).unwrap();
5476        let sets: Vec<(Cell, Vec<[f64; 3]>)> = vec![
5477            (
5478                dense,
5479                (0..4000)
5480                    .map(|_| dense.cartesian([unit(), unit(), unit()]))
5481                    .collect(),
5482            ),
5483            (
5484                sparse,
5485                (0..3000)
5486                    .map(|_| sparse.cartesian([unit(), unit(), unit()]))
5487                    .collect(),
5488            ),
5489        ];
5490        let run = |sim: &Cell, xyz: &[[f64; 3]], threads: usize, half: bool| {
5491            on_threads(threads, || {
5492                let rows = pairs_within(xyz, sim, 4.0, None, None, half).unwrap();
5493                let mut cols = PairColumns::default();
5494                pairs_within_columns(xyz, sim, 4.0, None, None, half, &mut cols).unwrap();
5495                (rows, cols)
5496            })
5497        };
5498        for (sim, xyz) in &sets {
5499            for threads in [1, 8] {
5500                for half in [false, true] {
5501                    AHEAD_TEST.store(1, Relaxed);
5502                    let off = run(sim, xyz, threads, half);
5503                    AHEAD_TEST.store(2, Relaxed);
5504                    let on = run(sim, xyz, threads, half);
5505                    AHEAD_TEST.store(0, Relaxed);
5506                    assert!(off.0.len() > 10_000);
5507                    assert!(off.0 == on.0, "rows: threads={threads} half={half}");
5508                    assert!(off.1 == on.1, "columns: threads={threads} half={half}");
5509                    // The C rows (`lc_pairs_within_rows`).
5510                    #[cfg(feature = "capi")]
5511                    {
5512                        let c_rows = |mode: u8| {
5513                            AHEAD_TEST.store(mode, Relaxed);
5514                            on_threads(threads, || {
5515                                let found = search(xyz, sim, 4.0, None, None, half).unwrap();
5516                                let n = found.rows();
5517                                let mut out: Vec<(i32, i32, [i32; 3], u64)> = Vec::with_capacity(n);
5518                                // Safety: `out` holds `n` rows.
5519                                unsafe {
5520                                    found.write_rows(out.as_mut_ptr(), |i, j, s, d| {
5521                                        (i, j, s, d.to_bits())
5522                                    });
5523                                    out.set_len(n);
5524                                }
5525                                out
5526                            })
5527                        };
5528                        let (off, on) = (c_rows(1), c_rows(2));
5529                        AHEAD_TEST.store(0, Relaxed);
5530                        assert!(off == on, "C rows: threads={threads} half={half}");
5531                    }
5532                }
5533            }
5534        }
5535    }
5536
5537    #[test]
5538    fn far_image_is_not_rewrapped() {
5539        let sim = Cell::ortho(10.0, 10.0, 10.0).unwrap();
5540        let xyz = [[0.1, 0.0, 0.0], [0.2, 0.0, 0.0]];
5541        let pairs = pairs_within(&xyz, &sim, 3.0, None, Some(10.0), false).unwrap();
5542        assert_eq!(pairs.len(), 2);
5543        assert!(pairs.iter().all(|p| p.shift == [0, 0, 0]));
5544        assert!(pairs.iter().all(|p| (p.dist2 - 0.01).abs() < 1e-12));
5545    }
5546
5547    #[test]
5548    fn highway_mic_matches_wrap_pair_distance() {
5549        let sim = Cell::ortho(10.0, 10.0, 10.0).unwrap();
5550        let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
5551        let pairs = pairs_within(&xyz, &sim, 1.0, None, None, true).unwrap();
5552        let mut mic = [0.0];
5553        crate::dist2_ortho_diffs(
5554            &[xyz[1][0] - xyz[0][0]],
5555            &[xyz[1][1] - xyz[0][1]],
5556            &[xyz[1][2] - xyz[0][2]],
5557            10.0,
5558            10.0,
5559            10.0,
5560            &mut mic,
5561        )
5562        .unwrap();
5563        assert_eq!(pairs.len(), 1);
5564        assert_eq!(pairs[0].shift, [-1, 0, 0]);
5565        assert!((pairs[0].dist2 - mic[0]).abs() < 1e-12);
5566        assert!((mic[0] - 0.64).abs() < 1e-12);
5567    }
5568
5569    #[test]
5570    fn wrap_pair_keeps_shift() {
5571        let sim = Cell::ortho(10.0, 10.0, 10.0).unwrap();
5572        let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
5573        let pairs = pairs_within(&xyz, &sim, 1.0, None, None, false).unwrap();
5574        assert_eq!(pairs.len(), 2);
5575        let a = pairs.iter().find(|p| p.i == 0 && p.j == 1).unwrap();
5576        assert_eq!(a.shift, [-1, 0, 0]);
5577        assert!((a.dist2 - 0.64).abs() < 1e-12);
5578    }
5579
5580    #[test]
5581    fn half_list_is_canonical() {
5582        let sim = Cell::ortho(10.0, 10.0, 10.0).unwrap();
5583        let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
5584        let pairs = pairs_within(&xyz, &sim, 1.0, None, None, true).unwrap();
5585        assert_eq!(pairs.len(), 1);
5586        assert_eq!(pairs[0].i, 0);
5587        assert_eq!(pairs[0].j, 1);
5588    }
5589
5590    #[test]
5591    fn sheared_cutoff_matches_shift_scan() {
5592        let sim = Cell::from_vectors(
5593            [4.0, 0.0, 0.0],
5594            [1.5, 3.0, 0.0],
5595            [0.2, -0.4, 3.5],
5596            [0.0, 0.0, 0.0],
5597        )
5598        .unwrap();
5599        let xyz = [
5600            sim.cartesian([0.05, 0.10, 0.20]),
5601            sim.cartesian([0.90, 0.15, 0.80]),
5602            sim.cartesian([0.40, 0.70, 0.30]),
5603            sim.cartesian([0.12, 0.85, 0.05]),
5604        ];
5605        let cutoff = 2.5;
5606        let got = pairs_within(&xyz, &sim, cutoff, None, Some(1.0), false).unwrap();
5607        let mut want = Vec::new();
5608        let cut2 = cutoff * cutoff;
5609        for i in 0..xyz.len() {
5610            for j in 0..xyz.len() {
5611                for na in -2..=2 {
5612                    for nb in -2..=2 {
5613                        for nc in -2..=2 {
5614                            if i == j && na == 0 && nb == 0 && nc == 0 {
5615                                continue;
5616                            }
5617                            let shift = sim.lattice_shift(na, nb, nc);
5618                            let pi = sim.cartesian(sim.fractional(xyz[i]));
5619                            let pj = sim.cartesian(sim.fractional(xyz[j]));
5620                            let d2 = sim.dist2_shifted(pi, pj, shift);
5621                            if d2 < cut2 {
5622                                want.push((i, j, [na, nb, nc]));
5623                            }
5624                        }
5625                    }
5626                }
5627            }
5628        }
5629        let mut got_key: Vec<_> = got.iter().map(|p| (p.i, p.j, p.shift)).collect();
5630        got_key.sort();
5631        want.sort();
5632        assert_eq!(got_key, want);
5633    }
5634
5635    #[test]
5636    fn wide_cube_matches_shift_scan() {
5637        let sim = Cell::ortho(18.0, 18.0, 18.0).unwrap();
5638        let mut xyz = Vec::new();
5639        for iz in 0..8 {
5640            for iy in 0..8 {
5641                for ix in 0..8 {
5642                    xyz.push([
5643                        (ix as f64 + 0.5) * 18.0 / 8.0,
5644                        (iy as f64 + 0.5) * 18.0 / 8.0,
5645                        (iz as f64 + 0.5) * 18.0 / 8.0,
5646                    ]);
5647                }
5648            }
5649        }
5650        let cutoff = 4.0;
5651        let cut2 = cutoff * cutoff;
5652        for half in [false, true] {
5653            let got = pairs_within(&xyz, &sim, cutoff, None, None, half).unwrap();
5654            let mut want = Vec::new();
5655            for i in 0..xyz.len() {
5656                for j in 0..xyz.len() {
5657                    for na in -1..=1 {
5658                        for nb in -1..=1 {
5659                            for nc in -1..=1 {
5660                                if i == j && na == 0 && nb == 0 && nc == 0 {
5661                                    continue;
5662                                }
5663                                let shift = [na, nb, nc];
5664                                let d2 = sim.dist2_shifted(
5665                                    xyz[i],
5666                                    xyz[j],
5667                                    sim.lattice_shift(na, nb, nc),
5668                                );
5669                                if d2 < cut2 && (!half || keep_half(i, j, shift)) {
5670                                    want.push((i, j, shift));
5671                                }
5672                            }
5673                        }
5674                    }
5675                }
5676            }
5677            let mut got_key: Vec<_> = got.iter().map(|p| (p.i, p.j, p.shift)).collect();
5678            got_key.sort();
5679            want.sort();
5680            assert_eq!(got_key, want);
5681        }
5682    }
5683
5684    #[test]
5685    fn dense_cube_matches_shift_scan() {
5686        let sim = Cell::ortho(6.0, 6.0, 6.0).unwrap();
5687        let mut xyz = Vec::new();
5688        for iz in 0..5 {
5689            for iy in 0..5 {
5690                for ix in 0..5 {
5691                    xyz.push([
5692                        (ix as f64 + 0.5) * 1.2,
5693                        (iy as f64 + 0.5) * 1.2,
5694                        (iz as f64 + 0.5) * 1.2,
5695                    ]);
5696                }
5697            }
5698        }
5699        let cutoff = 2.0;
5700        let got = pairs_within(&xyz, &sim, cutoff, None, None, false).unwrap();
5701        let mut keys: Vec<_> = got.iter().map(|p| (p.i, p.j, p.shift)).collect();
5702        keys.sort();
5703        let cut2 = cutoff * cutoff;
5704        let mut want = Vec::new();
5705        for i in 0..xyz.len() {
5706            for j in 0..xyz.len() {
5707                for na in -1..=1 {
5708                    for nb in -1..=1 {
5709                        for nc in -1..=1 {
5710                            if i == j && na == 0 && nb == 0 && nc == 0 {
5711                                continue;
5712                            }
5713                            let shift = [na, nb, nc];
5714                            let pi = sim.cartesian(sim.fractional(xyz[i]));
5715                            let pj = sim.cartesian(sim.fractional(xyz[j]));
5716                            let d2 = sim.dist2_shifted(pi, pj, sim.lattice_shift(na, nb, nc));
5717                            if d2 < cut2 {
5718                                want.push((i, j, shift));
5719                            }
5720                        }
5721                    }
5722                }
5723            }
5724        }
5725        want.sort();
5726        assert_eq!(keys, want);
5727    }
5728
5729    #[test]
5730    fn bad_cutoff() {
5731        let sim = Cell::ortho(10.0, 10.0, 10.0).unwrap();
5732        let xyz = [[0.0, 0.0, 0.0]];
5733        assert_eq!(
5734            pairs_within(&xyz, &sim, 0.0, None, None, false).unwrap_err(),
5735            Error::BadCutoff
5736        );
5737    }
5738
5739    fn thread_counts() -> Vec<usize> {
5740        let mut counts = vec![1usize];
5741        #[cfg(feature = "parallel")]
5742        counts.extend([2usize, 3, 8]);
5743        counts.sort_unstable();
5744        counts.dedup();
5745        counts
5746    }
5747
5748    fn pair_rows(
5749        threads: usize,
5750        path: Path,
5751        xyz: &[[f64; 3]],
5752        cell: &Cell,
5753        cutoff: f64,
5754    ) -> Vec<(i32, i32, [i32; 3], u64)> {
5755        on_threads(threads, || {
5756            let _guard = crate::simd::force(path);
5757            let rows = pairs_within(xyz, cell, cutoff, None, None, false).unwrap();
5758            let mut cols = PairColumns::default();
5759            pairs_within_columns(xyz, cell, cutoff, None, None, false, &mut cols).unwrap();
5760            let from_rows: Vec<_> = rows
5761                .iter()
5762                .map(|p| (p.i as i32, p.j as i32, p.shift, p.dist2.to_bits()))
5763                .collect();
5764            let from_cols: Vec<_> = (0..cols.len())
5765                .map(|t| (cols.i[t], cols.j[t], cols.shift[t], cols.dist2[t].to_bits()))
5766                .collect();
5767            assert_eq!(from_rows, from_cols);
5768            from_rows
5769        })
5770    }
5771
5772    /// Jittered triclinic pairs stay bitwise identical to scalar, including order.
5773    #[test]
5774    fn rank_invariant_pairs_on_jittered_triclinic() {
5775        let cell = Cell::from_vectors(
5776            [36.0, 0.0, 0.0],
5777            [3.5, 34.0, 0.0],
5778            [-2.5, 2.0, 33.0],
5779            [0.3, -0.2, 0.15],
5780        )
5781        .unwrap();
5782        let n = 12usize;
5783        let mut state = 0x1234_5678_9abc_def0u64;
5784        let mut next = || {
5785            state ^= state << 13;
5786            state ^= state >> 7;
5787            state ^= state << 17;
5788            state
5789        };
5790        let mut xyz = Vec::new();
5791        for iz in 0..n {
5792            for iy in 0..n {
5793                for ix in 0..n {
5794                    let j = |v: u64| ((v >> 11) as f64 / (1u64 << 53) as f64 - 0.5) * 0.15;
5795                    xyz.push(cell.cartesian([
5796                        (ix as f64 + 0.5) / n as f64 + j(next()),
5797                        (iy as f64 + 0.5) / n as f64 + j(next()),
5798                        (iz as f64 + 0.5) / n as f64 + j(next()),
5799                    ]));
5800                }
5801            }
5802        }
5803        xyz[0][0] = -0.0;
5804        xyz[1][1] = f64::from_bits(xyz[1][1].to_bits().wrapping_add(1));
5805        xyz[2][2] = 1.0e-320;
5806        let reference = pair_rows(1, Path::Scalar, &xyz, &cell, 5.0);
5807        assert!(reference.len() > 1000, "only {} pairs", reference.len());
5808        for threads in thread_counts() {
5809            for path in crate::simd::paths_to_compare() {
5810                let got = pair_rows(threads, path, &xyz, &cell, 5.0);
5811                assert_eq!(
5812                    got,
5813                    reference,
5814                    "threads={threads} path={path:?} len {} vs {}",
5815                    got.len(),
5816                    reference.len()
5817                );
5818            }
5819        }
5820    }
5821
5822    #[test]
5823    fn simd_paths_exercised() {
5824        let names: Vec<_> = crate::simd::paths_to_compare()
5825            .iter()
5826            .map(|p| p.name())
5827            .collect();
5828        println!("exercised={}", names.join(","));
5829        println!("native={}", crate::simd::native().name());
5830        if let Ok(text) = std::fs::read_to_string("/proc/cpuinfo") {
5831            if let Some(flags) = text.lines().find(|line| line.starts_with("flags")) {
5832                println!("{flags}");
5833            }
5834            if let Some(model) = text.lines().find(|line| line.starts_with("model name")) {
5835                println!("{model}");
5836            }
5837        }
5838        assert!(names.contains(&"scalar"));
5839    }
5840
5841    fn sha256(data: &[u8]) -> [u8; 32] {
5842        const K: [u32; 64] = [
5843            0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4,
5844            0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe,
5845            0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f,
5846            0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
5847            0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc,
5848            0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b,
5849            0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116,
5850            0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
5851            0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7,
5852            0xc67178f2,
5853        ];
5854        let mut h = [
5855            0x6a09e667u32,
5856            0xbb67ae85,
5857            0x3c6ef372,
5858            0xa54ff53a,
5859            0x510e527f,
5860            0x9b05688c,
5861            0x1f83d9ab,
5862            0x5be0cd19,
5863        ];
5864        let bit_len = (data.len() as u64).wrapping_mul(8);
5865        let mut msg = data.to_vec();
5866        msg.push(0x80);
5867        while msg.len() % 64 != 56 {
5868            msg.push(0);
5869        }
5870        msg.extend_from_slice(&bit_len.to_be_bytes());
5871        for chunk in msg.chunks_exact(64) {
5872            let mut w = [0u32; 64];
5873            for i in 0..16 {
5874                w[i] = u32::from_be_bytes(chunk[i * 4..i * 4 + 4].try_into().unwrap());
5875            }
5876            for i in 16..64 {
5877                let s0 = w[i - 15].rotate_right(7) ^ w[i - 15].rotate_right(18) ^ (w[i - 15] >> 3);
5878                let s1 = w[i - 2].rotate_right(17) ^ w[i - 2].rotate_right(19) ^ (w[i - 2] >> 10);
5879                w[i] = w[i - 16]
5880                    .wrapping_add(s0)
5881                    .wrapping_add(w[i - 7])
5882                    .wrapping_add(s1);
5883            }
5884            let (mut a, mut b, mut c, mut d, mut e, mut f, mut g, mut hh) =
5885                (h[0], h[1], h[2], h[3], h[4], h[5], h[6], h[7]);
5886            for i in 0..64 {
5887                let s1 = e.rotate_right(6) ^ e.rotate_right(11) ^ e.rotate_right(25);
5888                let ch = (e & f) ^ (!e & g);
5889                let t1 = hh
5890                    .wrapping_add(s1)
5891                    .wrapping_add(ch)
5892                    .wrapping_add(K[i])
5893                    .wrapping_add(w[i]);
5894                let s0 = a.rotate_right(2) ^ a.rotate_right(13) ^ a.rotate_right(22);
5895                let maj = (a & b) ^ (a & c) ^ (b & c);
5896                let t2 = s0.wrapping_add(maj);
5897                hh = g;
5898                g = f;
5899                f = e;
5900                e = d.wrapping_add(t1);
5901                d = c;
5902                c = b;
5903                b = a;
5904                a = t1.wrapping_add(t2);
5905            }
5906            h[0] = h[0].wrapping_add(a);
5907            h[1] = h[1].wrapping_add(b);
5908            h[2] = h[2].wrapping_add(c);
5909            h[3] = h[3].wrapping_add(d);
5910            h[4] = h[4].wrapping_add(e);
5911            h[5] = h[5].wrapping_add(f);
5912            h[6] = h[6].wrapping_add(g);
5913            h[7] = h[7].wrapping_add(hh);
5914        }
5915        let mut out = [0u8; 32];
5916        for (i, word) in h.iter().enumerate() {
5917            out[i * 4..i * 4 + 4].copy_from_slice(&word.to_be_bytes());
5918        }
5919        out
5920    }
5921
5922    fn hex32(bytes: &[u8; 32]) -> String {
5923        const HEX: &[u8; 16] = b"0123456789abcdef";
5924        let mut s = String::with_capacity(64);
5925        for b in bytes {
5926            s.push(HEX[(b >> 4) as usize] as char);
5927            s.push(HEX[(b & 0xf) as usize] as char);
5928        }
5929        s
5930    }
5931
5932    /// 5^3 lattice, spacing 2.5, cutoff 4. The first point's x is -0,
5933    /// the second point's y is one ulp above its lattice value, and the
5934    /// third point's z is subnormal.
5935    fn golden_dist2_bytes() -> Vec<u8> {
5936        let n = 5usize;
5937        let a = 2.5f64;
5938        let boxl = n as f64 * a;
5939        let cell = Cell::ortho(boxl, boxl, boxl).unwrap();
5940        let mut xyz = Vec::new();
5941        for iz in 0..n {
5942            for iy in 0..n {
5943                for ix in 0..n {
5944                    xyz.push([ix as f64 * a, iy as f64 * a, iz as f64 * a]);
5945                }
5946            }
5947        }
5948        xyz[0][0] = -0.0;
5949        xyz[1][1] = f64::from_bits(xyz[1][1].to_bits().wrapping_add(1));
5950        xyz[2][2] = 1.0e-320;
5951        let rows = pair_rows(1, Path::Scalar, &xyz, &cell, 4.0);
5952        let mut bytes = Vec::with_capacity(rows.len() * 8);
5953        for (_, _, _, bits) in rows {
5954            bytes.extend_from_slice(&bits.to_le_bytes());
5955        }
5956        bytes
5957    }
5958
5959    #[test]
5960    fn golden_isa_hash_matches_scalar_dist2() {
5961        let empty = sha256(b"");
5962        assert_eq!(
5963            hex32(&empty),
5964            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
5965        );
5966        let bytes = golden_dist2_bytes();
5967        let got = hex32(&sha256(&bytes));
5968        for path in crate::simd::paths_to_compare() {
5969            let n = 5usize;
5970            let a = 2.5f64;
5971            let cell = Cell::ortho(n as f64 * a, n as f64 * a, n as f64 * a).unwrap();
5972            let mut xyz = Vec::new();
5973            for iz in 0..n {
5974                for iy in 0..n {
5975                    for ix in 0..n {
5976                        xyz.push([ix as f64 * a, iy as f64 * a, iz as f64 * a]);
5977                    }
5978                }
5979            }
5980            xyz[0][0] = -0.0;
5981            xyz[1][1] = f64::from_bits(xyz[1][1].to_bits().wrapping_add(1));
5982            xyz[2][2] = 1.0e-320;
5983            let rows = pair_rows(1, path, &xyz, &cell, 4.0);
5984            let mut raw = Vec::new();
5985            for (_, _, _, bits) in rows {
5986                raw.extend_from_slice(&bits.to_le_bytes());
5987            }
5988            assert_eq!(hex32(&sha256(&raw)), got, "{path:?}");
5989        }
5990        let file = include_str!("../tests/golden/isa-hashes.toml");
5991        let want = file
5992            .lines()
5993            .find_map(|line| {
5994                line.strip_prefix("sha256 = \"")
5995                    .map(|rest| rest.trim_end_matches('"'))
5996            })
5997            .expect("sha256 entry");
5998        assert_eq!(got, want, "update tests/golden/isa-hashes.toml");
5999    }
6000}