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