// SPDX-FileCopyrightText: 2026 Filip Leonarski, Paul Scherrer Institute // SPDX-License-Identifier: GPL-3.0-only #include #include #include #include #include #include #include "../common/CpuFFT.h" #include "../image_analysis/structure_refinement/ModelFFT.h" // pocketfft (common/CpuFFT) on the shapes and layouts the call sites use, against a direct DFT in double // precision: the forward transforms to float rounding, the backward ones by a round trip (an unnormalised // forward + backward pair gives the input times the number of points). namespace { std::vector Random(size_t n, unsigned seed) { std::mt19937 rng(seed); std::normal_distribution g(0.0f, 1.0f); std::vector v(n); for (auto &x : v) x = g(rng); return v; } // Largest difference relative to the largest value of the reference. template double RelativeError(const std::vector &a, const std::vector &ref) { REQUIRE(a.size() == ref.size()); double diff = 0, scale = 0; for (size_t i = 0; i < a.size(); i++) { diff = std::max(diff, std::abs(std::complex(a[i]) - std::complex(ref[i]))); scale = std::max(scale, std::abs(std::complex(ref[i]))); } return diff / scale; } // Forward DFT of a row-major array along every axis, computed directly, in double precision. std::vector> DirectDFT(const std::vector &shape, const std::vector &in) { std::vector> a(in.begin(), in.end()); size_t stride = a.size(); for (size_t n : shape) { stride /= n; std::vector> line(n); for (size_t base = 0; base < a.size(); base++) { if ((base / stride) % n != 0) continue; // not the first element of a line along this axis for (size_t k = 0; k < n; k++) { std::complex s = 0; for (size_t j = 0; j < n; j++) s += a[base + j * stride] * std::polar(1.0, -2.0 * M_PI * static_cast(j * k % n) / n); line[k] = s; } for (size_t k = 0; k < n; k++) a[base + k * stride] = line[k]; } } return a; } // The half (n/2 + 1 values) of the last axis that a real transform keeps. std::vector> HalfLastAxis(const std::vector &shape, const std::vector> &full) { const size_t n = shape.back(), nc = n / 2 + 1; std::vector> half; for (size_t i = 0; i < full.size(); i++) if (i % n < nc) half.push_back(full[i]); return half; } std::vector Scaled(const std::vector &v, double s) { std::vector r(v.size()); for (size_t i = 0; i < v.size(); i++) r[i] = static_cast(v[i] * s); return r; } } // namespace TEST_CASE("CpuFFT_BatchedR2CMatchesDirectDFT", "[fft]") { // The FFT indexer's histograms: one transform per direction; 3142 = 2 x 1571 is a real length. for (size_t n : {3142, 3150, 1024}) { const size_t howmany = 5; const std::vector in = Random(howmany * n, n); std::vector> ours(howmany * (n / 2 + 1)); cpu_fft::R2C({howmany, n}, {1}, in.data(), ours.data()); // DirectDFT over the batch axis too would mix the lines: transform each line on its own. std::vector> ref; for (size_t i = 0; i < howmany; i++) { const std::vector line(in.begin() + i * n, in.begin() + (i + 1) * n); const auto r = HalfLastAxis({n}, DirectDFT({n}, line)); ref.insert(ref.end(), r.begin(), r.end()); } CHECK(RelativeError(ours, ref) < 1e-5); } } TEST_CASE("CpuFFT_2DRoundTrip", "[fft]") { // The beam-centre search: a 2D r2c and c2r on a 2-3-5-7-smooth padded size. const std::vector shape = {210, 336}; const std::vector in = Random(shape[0] * shape[1], 1); std::vector> ours(shape[0] * (shape[1] / 2 + 1)); cpu_fft::R2C(shape, {0, 1}, in.data(), ours.data()); CHECK(RelativeError(ours, HalfLastAxis(shape, DirectDFT(shape, in))) < 1e-5); std::vector back(in.size()); cpu_fft::C2R(shape, {0, 1}, ours.data(), back.data()); CHECK(RelativeError(back, Scaled(in, static_cast(in.size()))) < 1e-5); } TEST_CASE("CpuFFT_3DRoundTrip", "[fft]") { // The model maps (u fastest, w halved) and the tNCS Patterson (row-major, last axis halved) are both a // row-major 3D transform halving the last axis; an odd length and a factor 7 included. const std::vector shape = {70, 45, 54}; const std::vector in = Random(shape[0] * shape[1] * shape[2], 2); std::vector> ours(shape[0] * shape[1] * (shape[2] / 2 + 1)); cpu_fft::R2C(shape, {0, 1, 2}, in.data(), ours.data()); CHECK(RelativeError(ours, HalfLastAxis(shape, DirectDFT(shape, in))) < 1e-5); std::vector back(in.size()); cpu_fft::C2R(shape, {0, 1, 2}, ours.data(), back.data()); CHECK(RelativeError(back, Scaled(in, static_cast(in.size()))) < 1e-5); } TEST_CASE("CpuFFT_MapToFPhiInParallelMatchesMapToFPhi", "[fft]") { gemmi::Grid map; map.unit_cell.set(60, 50, 40, 90, 90, 90); map.spacegroup = gemmi::find_spacegroup_by_name("P1"); map.set_size(60, 50, 40); map.data = Random(map.data.size(), 3); const int reach = 12; const gemmi::FPhiGrid ref = CropHalfL(MapToFPhi(map), reach); for (size_t nthreads : {1, 4}) { const gemmi::FPhiGrid ours = MapToFPhiInParallel(map, reach, nthreads); CHECK(RelativeError(ours.data, ref.data) < 1e-5); } }