Skip to main content

xingo_extprec/
simd.rs

1//! # Chapter 11.6 — SIMD kernels (`pulp`)
2//!
3//! ## Purpose
4//! The kernels of Chapter 11.5 on vector registers, with **the same
5//! results bit for bit** (invariant K1). Nothing here defines a kernel: the
6//! definitions are Algorithms C and B of Chapter 11.5 and their scalar
7//! reference; this chapter says how four of those scalar computations are
8//! carried side by side, and why nothing changes when they are.
9//!
10//! ## Notation
11//! As in Chapters 11.1, 11.2 and 11.5. `W = 4`. A *quad* is four `f64`
12//! values `v = (v_0, v_1, v_2, v_3)`, its *lanes*; an operation on quads
13//! (`+`, `−`, `·`, the fused `a b + c`, negation) is the `f64` operation of
14//! the same name on each lane, correctly rounded — what NEON and AVX2 + FMA
15//! provide. A *double-double quad* is a pair of quads `(h, ℓ)`. `2Sum`,
16//! `Fast2Sum`, `2Prod` and the algorithms A2, M1, M2 of Chapter 11.2 **on
17//! quads** are the same sequences of operations with every `f64` operation
18//! replaced by the quad one, and **without step E**. A slice is cut into
19//! *chunks* of four consecutive elements (element `4c + k` of the slice is
20//! lane `k` of chunk `c`) and a *tail* of fewer than four.
21//!
22//! A quad is one 256-bit register on x86 (AVX2) and two 128-bit registers
23//! on `aarch64` (NEON): `W = 4` on every target, the narrower one emulating
24//! it (Chapter 11.5).
25//!
26//! ## Algorithm V (vectorized accumulation: `sum2`, `dot2`, `dot2_err`)
27//! V1. \[Lanes.\] `p ← 0`, `s ← 0`, `e ← 0` (quads).
28//! V2. \[Chunks.\] For each chunk `x` (and `y`): step C2 on quads — `sum2`:
29//!     `(p, q) ← 2Sum(p, x)`, `t ← q + 0`; `dot2`: `(g, r) ← 2Prod(x, y)`,
30//!     `(p, q) ← 2Sum(p, g)`, `t ← q + r` — then `s ← s + t` and, for
31//!     `dot2_err` only, `e ← e + |t|`.
32//! V3. \[Tail and result.\] Store the quads as the lanes `p_k`, `s_k`, `e_k`
33//!     of Algorithm C, run step C2 on the tail (element `j` of the tail in
34//!     lane `j`) and steps C3–C5, all in the scalar code of Chapter 11.5.
35//!
36//! Lane `k` of the quads goes through exactly the operations that the
37//! reference applies to the elements `i ≡ k (mod 4)`, in the same order,
38//! each correctly rounded: the lanes hold the same bits after V2, and V3
39//! *is* the reference. (`sum2` and `dot2` do not compute `e`, which their
40//! result does not use.)
41//!
42//! ## Algorithm W (vectorized double-double BLAS)
43//! W1. \[`axpy`, the column update `c ← c ⊖ a ⊗ t`.\] For each chunk:
44//!     compute `z ← y ⊕ (α ⊗ x)` (resp. `c ⊕ (−(a ⊗ t))`) on quads; if
45//!     every lane of `z_h` and of `z_ℓ` is finite, store `z`; otherwise
46//!     compute the four elements of the chunk with the scalar operations
47//!     of Chapter 11.2 (from the operands, which were not yet
48//!     overwritten). The tail is scalar.
49//! W2. \[`dot`, `dot_mixed`, `dot4`.\] `a ← 0` (a double-double quad);
50//!     for each chunk `a ← a ⊕ (x ⊗ y)` on quads. If some lane of `a_h` or
51//!     `a_ℓ` is not finite, discard everything and run the reference kernel
52//!     on the whole input. Otherwise store `a` as the four accumulators of
53//!     step B1 (B4) and finish in scalar code: the tail, then `((a_0 ⊕ a_1)
54//!     ⊕ a_2) ⊕ a_3` (B4: the fifth accumulator over the tail and `((a_0 ⊕
55//!     a_1) ⊕ (a_2 ⊕ a_3)) ⊕ t`).
56//!
57//! **Why step E can be left out (the proof of K1 for Algorithm W).** The
58//! scalar operations end in step E, which is the identity when the
59//! leading and the trailing component of the result are both finite, and
60//! which is the only place where the scalar code branches. Two facts about
61//! A2, M1 and M2 *without* step E, for arbitrary `f64` operands:
62//!
63//! (N1) *Finite out, finite inside.* If `z_h` and `z_ℓ` are finite, every
64//!      intermediate quantity was finite. (Every intermediate enters the
65//!      result through additions, subtractions and products only; none of
66//!      those maps a non-finite operand to a finite result.)
67//! (N2) *Non-finite is absorbing.* If an operand has a non-finite
68//!      component, or an intermediate quantity is not finite, then `z_h`
69//!      is not finite. (In A2: a non-finite `s_h` makes `s_ℓ` a NaN, a
70//!      non-finite `t_h` or `s_ℓ` makes `c`, then `v_h`, then `z_h`
71//!      non-finite; an overflow of `v_h` gives `v_ℓ = −∞` or NaN and `z_h`
72//!      a NaN. In M1 and M2: every term enters `c_ℓ3`, and `z_h = c_h +
73//!      c_ℓ3`.)
74//!
75//! Now compare the quad computation of one chunk with the scalar one,
76//! operation by operation. As long as the scalar code meets no non-finite
77//! value, each of its step E is the identity and the two computations are
78//! the same sequence of correctly rounded operations: the same bits. At
79//! the first non-finite value of the scalar computation the quad
80//! computation holds the same non-finite value, and by (N2), applied to
81//! the operation where it occurs and to every later one that consumes its
82//! result, the quad result of that lane is not finite: W1 then recomputes
83//! the chunk, and W2 the whole kernel, *with the scalar code itself*.
84//! Conversely, if the quad result is finite then by (N1) no non-finite
85//! value occurred. In W2 "later operations" are the accumulations `a ← a ⊕
86//! …` of the following chunks: a lane of `a` that became non-finite stays
87//! so until the test. Hence the stored result is always the reference's —
88//! NaN signs and payloads included in Algorithm W, since those results
89//! come from the scalar code. In Algorithm V a NaN is produced by the
90//! vector instruction, and only "NaN where the reference has a NaN" is
91//! claimed (invariant K1 of Chapter 11.5).
92//!
93//! The argument does not use normalization (D1). The tests nevertheless
94//! use valid double-doubles only: on other pairs the reference itself is
95//! outside its contract (its `Fast2Sum` asserts its precondition in debug
96//! builds).
97//!
98//! ## The vector arithmetic: [`Lanes`]
99//! The algorithms are written once, over the trait [`Lanes`] — a quad type
100//! and its operations — with two implementations on `pulp`'s safe
101//! interface: [`X4`] (one four-lane register; `pulp::x86::V3`) and [`X2`]
102//! (two two-lane registers; `pulp::aarch64::Neon`). The fused
103//! multiply-add is `pulp`'s `mul_add_f64s`, which is `vfmaq_f64` on NEON
104//! and `_mm256_fmadd_pd` on x86 — a true FMA on both, never a
105//! multiplication followed by an addition (`mul_add_e_f64s` is the one
106//! that may be either, and is not used). A double-double slice is read
107//! and written through the accessors of [`DoubleDouble`], four elements at
108//! a time: the crate has no `unsafe`, so there is no reinterpretation of
109//! `&[DoubleDouble]` as `&[f64]`; the compiler turns the gathers into
110//! shuffles.
111//!
112//! ## Invariants
113//! (K1) of Chapter 11.5, tested there against the reference on random and
114//!      exceptional inputs of every length `0..=67` and some large ones.
115//! (L1) A [`Lanes`] operation is the correctly rounded `f64` operation on
116//!      each lane; `mul_add` is fused. (The contract of the two
117//!      implementations; checked lane by lane against `f64`, on the
118//!      backend of the machine, by the test of this module.)
119//! (L2) [`X4`] is built only on a four-lane backend and [`X2`] only on a
120//!      two-lane one: checked at compile time by their constructors.
121//!
122//! ## What was run where
123//! The NEON path is the one tested and measured (Apple M2). The AVX2 path
124//! is the same generic code instantiated with [`X4`]; it has been
125//! type-checked only as generic code and **has not been compiled for, or
126//! run on, an x86 target** in this cycle — the tests of Chapter 11.5 run
127//! it wherever `backend()` is `"avx2"`.
128//!
129//! ## References
130//! Chapter 11.5 (the definitions) and Chapter 11.2 (A2, M1, M2, step E).
131//! Ogita, Rump & Oishi (2005), §8 (they note that Sum2 and Dot2 use only
132//! `+`, `−`, `·` and so vectorize). `pulp` 0.22.3: `Simd`, `WithSimd`,
133//! `aarch64::Neon`, `x86::V3` (the API, read: `src/aarch64.rs`,
134//! `src/x86/v3.rs`).
135
136#![allow(clippy::float_cmp)]
137// the finiteness test compares an exact zero
138// `pulp` enables the target features (AVX2, FMA) for the code *inlined*
139// into `vectorize`: a kernel that is not inlined there would be compiled
140// without them. Every function of this module is on that path.
141#![allow(clippy::inline_always)]
142// On a target with neither backend (s390x, wasm32, ...) `dispatch!` expands
143// to nothing, so the generic kernels are compiled (and type-checked) but
144// never called: step X3, the scalar reference, is the only path there.
145#![cfg_attr(
146    not(any(target_arch = "aarch64", target_arch = "x86", target_arch = "x86_64")),
147    allow(dead_code)
148)]
149
150use pulp::Simd;
151
152use crate::dd::DoubleDouble;
153use crate::eft::two_prod;
154use crate::kernels::{ColumnUpdate, Compensated, LANES, reference};
155
156/// Four `f64` lanes and their arithmetic (invariant L1).
157pub(crate) trait Lanes: Copy {
158    /// A quad.
159    type V: Copy;
160    /// `(x, x, x, x)`.
161    fn splat(self, x: f64) -> Self::V;
162    /// The quad with lanes `a`.
163    fn load(self, a: [f64; LANES]) -> Self::V;
164    /// The lanes of `v`.
165    fn store(self, v: Self::V) -> [f64; LANES];
166    /// `RN(a + b)` on each lane.
167    fn add(self, a: Self::V, b: Self::V) -> Self::V;
168    /// `RN(a − b)` on each lane.
169    fn sub(self, a: Self::V, b: Self::V) -> Self::V;
170    /// `RN(a b)` on each lane.
171    fn mul(self, a: Self::V, b: Self::V) -> Self::V;
172    /// `RN(a b + c)` on each lane, fused.
173    fn mul_add(self, a: Self::V, b: Self::V, c: Self::V) -> Self::V;
174    /// `−a` on each lane (exact).
175    fn neg(self, a: Self::V) -> Self::V;
176    /// `|a|` on each lane (exact).
177    fn abs(self, a: Self::V) -> Self::V;
178    /// Every lane of `a` and of `b` is finite.
179    fn all_finite(self, a: Self::V, b: Self::V) -> bool;
180}
181
182/// A quad in one four-lane register of the backend `S` (AVX2).
183#[derive(Clone, Copy, Debug)]
184pub(crate) struct X4<S: Simd>(S);
185
186impl<S: Simd> X4<S> {
187    /// Invariant (L2): `S` has four `f64` lanes.
188    #[inline(always)]
189    #[cfg_attr(
190        not(any(target_arch = "x86", target_arch = "x86_64")),
191        allow(dead_code)
192    )]
193    pub(crate) fn new(simd: S) -> Self {
194        const { assert!(S::F64_LANES == LANES) };
195        Self(simd)
196    }
197}
198
199impl<S: Simd> Lanes for X4<S> {
200    type V = S::f64s;
201
202    #[inline(always)]
203    fn splat(self, x: f64) -> Self::V {
204        self.0.splat_f64s(x)
205    }
206    #[inline(always)]
207    fn load(self, a: [f64; LANES]) -> Self::V {
208        pulp::cast(a)
209    }
210    #[inline(always)]
211    fn store(self, v: Self::V) -> [f64; LANES] {
212        pulp::cast(v)
213    }
214    #[inline(always)]
215    fn add(self, a: Self::V, b: Self::V) -> Self::V {
216        self.0.add_f64s(a, b)
217    }
218    #[inline(always)]
219    fn sub(self, a: Self::V, b: Self::V) -> Self::V {
220        self.0.sub_f64s(a, b)
221    }
222    #[inline(always)]
223    fn mul(self, a: Self::V, b: Self::V) -> Self::V {
224        self.0.mul_f64s(a, b)
225    }
226    #[inline(always)]
227    fn mul_add(self, a: Self::V, b: Self::V, c: Self::V) -> Self::V {
228        self.0.mul_add_f64s(a, b, c)
229    }
230    #[inline(always)]
231    fn neg(self, a: Self::V) -> Self::V {
232        self.0.neg_f64s(a)
233    }
234    #[inline(always)]
235    fn abs(self, a: Self::V) -> Self::V {
236        self.0.abs_f64s(a)
237    }
238    #[inline(always)]
239    fn all_finite(self, a: Self::V, b: Self::V) -> bool {
240        // x − x is +0 for a finite x and NaN otherwise.
241        let s = self.0;
242        let z = s.add_f64s(s.sub_f64s(a, a), s.sub_f64s(b, b));
243        s.reduce_sum_f64s(z) == 0.0
244    }
245}
246
247/// A quad in two two-lane registers of the backend `S` (NEON): lanes 0–1
248/// and lanes 2–3.
249#[derive(Clone, Copy, Debug)]
250pub(crate) struct X2<S: Simd>(S);
251
252impl<S: Simd> X2<S> {
253    /// Invariant (L2): `S` has two `f64` lanes.
254    #[inline(always)]
255    #[cfg_attr(not(target_arch = "aarch64"), allow(dead_code))]
256    pub(crate) fn new(simd: S) -> Self {
257        const { assert!(2 * S::F64_LANES == LANES) };
258        Self(simd)
259    }
260}
261
262impl<S: Simd> Lanes for X2<S> {
263    type V = [S::f64s; 2];
264
265    #[inline(always)]
266    fn splat(self, x: f64) -> Self::V {
267        [self.0.splat_f64s(x); 2]
268    }
269    #[inline(always)]
270    fn load(self, a: [f64; LANES]) -> Self::V {
271        [pulp::cast([a[0], a[1]]), pulp::cast([a[2], a[3]])]
272    }
273    #[inline(always)]
274    fn store(self, v: Self::V) -> [f64; LANES] {
275        let (lo, hi): ([f64; 2], [f64; 2]) = (pulp::cast(v[0]), pulp::cast(v[1]));
276        [lo[0], lo[1], hi[0], hi[1]]
277    }
278    #[inline(always)]
279    fn add(self, a: Self::V, b: Self::V) -> Self::V {
280        [self.0.add_f64s(a[0], b[0]), self.0.add_f64s(a[1], b[1])]
281    }
282    #[inline(always)]
283    fn sub(self, a: Self::V, b: Self::V) -> Self::V {
284        [self.0.sub_f64s(a[0], b[0]), self.0.sub_f64s(a[1], b[1])]
285    }
286    #[inline(always)]
287    fn mul(self, a: Self::V, b: Self::V) -> Self::V {
288        [self.0.mul_f64s(a[0], b[0]), self.0.mul_f64s(a[1], b[1])]
289    }
290    #[inline(always)]
291    fn mul_add(self, a: Self::V, b: Self::V, c: Self::V) -> Self::V {
292        [
293            self.0.mul_add_f64s(a[0], b[0], c[0]),
294            self.0.mul_add_f64s(a[1], b[1], c[1]),
295        ]
296    }
297    #[inline(always)]
298    fn neg(self, a: Self::V) -> Self::V {
299        [self.0.neg_f64s(a[0]), self.0.neg_f64s(a[1])]
300    }
301    #[inline(always)]
302    fn abs(self, a: Self::V) -> Self::V {
303        [self.0.abs_f64s(a[0]), self.0.abs_f64s(a[1])]
304    }
305    #[inline(always)]
306    fn all_finite(self, a: Self::V, b: Self::V) -> bool {
307        // x − x is +0 for a finite x and NaN otherwise.
308        let s = self.0;
309        let z0 = s.add_f64s(s.sub_f64s(a[0], a[0]), s.sub_f64s(b[0], b[0]));
310        let z1 = s.add_f64s(s.sub_f64s(a[1], a[1]), s.sub_f64s(b[1], b[1]));
311        s.reduce_sum_f64s(s.add_f64s(z0, z1)) == 0.0
312    }
313}
314
315/// A double-double quad `(h, ℓ)`.
316type Dq<L> = (<L as Lanes>::V, <L as Lanes>::V);
317
318/// Algorithm S of Chapter 11.1 on quads.
319#[inline(always)]
320fn two_sum_q<L: Lanes>(l: L, a: L::V, b: L::V) -> (L::V, L::V) {
321    let s = l.add(a, b);
322    let a1 = l.sub(s, b);
323    let b1 = l.sub(s, a1);
324    let da = l.sub(a, a1);
325    let db = l.sub(b, b1);
326    (s, l.add(da, db))
327}
328
329/// Algorithm F of Chapter 11.1 on quads.
330#[inline(always)]
331fn fast_two_sum_q<L: Lanes>(l: L, a: L::V, b: L::V) -> (L::V, L::V) {
332    let s = l.add(a, b);
333    let z = l.sub(s, a);
334    (s, l.sub(b, z))
335}
336
337/// Algorithm P of Chapter 11.1 on quads.
338#[inline(always)]
339fn two_prod_q<L: Lanes>(l: L, a: L::V, b: L::V) -> (L::V, L::V) {
340    let p = l.mul(a, b);
341    (p, l.mul_add(a, b, l.neg(p)))
342}
343
344/// Algorithm A2 of Chapter 11.2 on quads, without step E.
345#[inline(always)]
346fn add_q<L: Lanes>(l: L, x: Dq<L>, y: Dq<L>) -> Dq<L> {
347    let (sh, sl) = two_sum_q(l, x.0, y.0);
348    let (th, tl) = two_sum_q(l, x.1, y.1);
349    let c = l.add(sl, th);
350    let (vh, vl) = fast_two_sum_q(l, sh, c);
351    let w = l.add(tl, vl);
352    fast_two_sum_q(l, vh, w)
353}
354
355/// Algorithm M2 of Chapter 11.2 on quads, without step E.
356#[inline(always)]
357fn mul_q<L: Lanes>(l: L, x: Dq<L>, y: Dq<L>) -> Dq<L> {
358    let (ch, cl1) = two_prod_q(l, x.0, y.0);
359    let tl0 = l.mul(x.1, y.1);
360    let tl1 = l.mul_add(x.0, y.1, tl0);
361    let cl2 = l.mul_add(x.1, y.0, tl1);
362    let cl3 = l.add(cl1, cl2);
363    fast_two_sum_q(l, ch, cl3)
364}
365
366/// Algorithm M1 of Chapter 11.2 on quads, without step E.
367#[inline(always)]
368fn mul_f64_q<L: Lanes>(l: L, x: Dq<L>, y: L::V) -> Dq<L> {
369    let (ch, cl1) = two_prod_q(l, x.0, y);
370    let cl3 = l.mul_add(x.1, y, cl1);
371    fast_two_sum_q(l, ch, cl3)
372}
373
374/// The double-double quad of a chunk.
375#[inline(always)]
376fn load_dd<L: Lanes>(l: L, c: &[DoubleDouble; LANES]) -> Dq<L> {
377    (
378        l.load([c[0].hi(), c[1].hi(), c[2].hi(), c[3].hi()]),
379        l.load([c[0].lo(), c[1].lo(), c[2].lo(), c[3].lo()]),
380    )
381}
382
383/// The four double-doubles of a quad (finite, hence the pairs the scalar
384/// operations return: no invariant is re-checked).
385#[inline(always)]
386fn store_dd<L: Lanes>(l: L, z: Dq<L>) -> [DoubleDouble; LANES] {
387    let (h, lo) = (l.store(z.0), l.store(z.1));
388    [
389        DoubleDouble::from_raw(h[0], lo[0]),
390        DoubleDouble::from_raw(h[1], lo[1]),
391        DoubleDouble::from_raw(h[2], lo[2]),
392        DoubleDouble::from_raw(h[3], lo[3]),
393    ]
394}
395
396/// The double-double quad `(x, x, x, x)`.
397#[inline(always)]
398fn splat_dd<L: Lanes>(l: L, x: DoubleDouble) -> Dq<L> {
399    (l.splat(x.hi()), l.splat(x.lo()))
400}
401
402/// Algorithm V for `sum2`: the lanes after steps V1–V3 (C1–C2).
403#[inline(always)]
404pub(crate) fn sum2<L: Lanes>(l: L, x: &[f64]) -> Compensated {
405    let (chunks, tail) = x.as_chunks::<LANES>();
406    let zero = l.splat(0.0);
407    let (mut p, mut s) = (zero, zero);
408    for c in chunks {
409        let (pn, q) = two_sum_q(l, p, l.load(*c));
410        p = pn;
411        s = l.add(s, l.add(q, zero));
412    }
413    let mut acc = Compensated {
414        p: l.store(p),
415        s: l.store(s),
416        e: [0.0; LANES],
417    };
418    for (j, &xi) in tail.iter().enumerate() {
419        acc.push(j, xi, 0.0);
420    }
421    acc
422}
423
424/// Algorithm V for `dot2` (`BOUND = false`: the lanes `e` are not
425/// computed) and `dot2_err` (`BOUND = true`).
426#[inline(always)]
427pub(crate) fn dot2<L: Lanes, const BOUND: bool>(l: L, x: &[f64], y: &[f64]) -> Compensated {
428    debug_assert_eq!(x.len(), y.len(), "dot2: the lengths differ");
429    let (cx, tx) = x.as_chunks::<LANES>();
430    let (cy, ty) = y.as_chunks::<LANES>();
431    let zero = l.splat(0.0);
432    let (mut p, mut s, mut e) = (zero, zero, zero);
433    for (a, b) in cx.iter().zip(cy) {
434        let (g, r) = two_prod_q(l, l.load(*a), l.load(*b));
435        let (pn, q) = two_sum_q(l, p, g);
436        let t = l.add(q, r);
437        p = pn;
438        s = l.add(s, t);
439        if BOUND {
440            e = l.add(e, l.abs(t));
441        }
442    }
443    let mut acc = Compensated {
444        p: l.store(p),
445        s: l.store(s),
446        e: l.store(e),
447    };
448    for (j, (&xi, &yi)) in tx.iter().zip(ty).enumerate() {
449        let (h, r) = two_prod(xi, yi);
450        acc.push(j, h, r);
451    }
452    acc
453}
454
455/// Step W2 for `dot`.
456#[inline(always)]
457pub(crate) fn dot<L: Lanes>(l: L, x: &[DoubleDouble], y: &[DoubleDouble]) -> DoubleDouble {
458    debug_assert_eq!(x.len(), y.len(), "dot: the lengths differ");
459    let (cx, tx) = x.as_chunks::<LANES>();
460    let (cy, ty) = y.as_chunks::<LANES>();
461    let mut a = splat_dd(l, DoubleDouble::ZERO);
462    for (p, q) in cx.iter().zip(cy) {
463        a = add_q(l, a, mul_q(l, load_dd(l, p), load_dd(l, q)));
464    }
465    if !l.all_finite(a.0, a.1) {
466        return reference::dot(x, y);
467    }
468    let mut acc = store_dd(l, a);
469    for (j, (&xi, &yi)) in tx.iter().zip(ty).enumerate() {
470        acc[j] += xi * yi;
471    }
472    ((acc[0] + acc[1]) + acc[2]) + acc[3]
473}
474
475/// Step W2 for `dot4` (step B4 of Chapter 11.5): the chunks on quads, the
476/// tail and the pairwise combination in scalar code, as the reference.
477#[inline(always)]
478#[cfg_attr(not(feature = "sparse"), allow(dead_code))]
479pub(crate) fn dot4<L: Lanes>(l: L, x: &[DoubleDouble], y: &[DoubleDouble]) -> DoubleDouble {
480    debug_assert_eq!(x.len(), y.len(), "dot4: the lengths differ");
481    let (cx, tx) = x.as_chunks::<LANES>();
482    let (cy, ty) = y.as_chunks::<LANES>();
483    let mut a = splat_dd(l, DoubleDouble::ZERO);
484    for (p, q) in cx.iter().zip(cy) {
485        a = add_q(l, a, mul_q(l, load_dd(l, p), load_dd(l, q)));
486    }
487    if !l.all_finite(a.0, a.1) {
488        return reference::dot4(x, y);
489    }
490    let acc = store_dd(l, a);
491    let mut t = DoubleDouble::ZERO;
492    for (&p, &q) in tx.iter().zip(ty) {
493        t += p * q;
494    }
495    (acc[0] + acc[1]) + (acc[2] + acc[3]) + t
496}
497
498/// Step W2 for `dot_mixed`.
499#[inline(always)]
500pub(crate) fn dot_mixed<L: Lanes>(l: L, x: &[DoubleDouble], y: &[f64]) -> DoubleDouble {
501    debug_assert_eq!(x.len(), y.len(), "dot_mixed: the lengths differ");
502    let (cx, tx) = x.as_chunks::<LANES>();
503    let (cy, ty) = y.as_chunks::<LANES>();
504    let mut a = splat_dd(l, DoubleDouble::ZERO);
505    for (p, q) in cx.iter().zip(cy) {
506        a = add_q(l, a, mul_f64_q(l, load_dd(l, p), l.load(*q)));
507    }
508    if !l.all_finite(a.0, a.1) {
509        return reference::dot_mixed(x, y);
510    }
511    let mut acc = store_dd(l, a);
512    for (j, (&xi, &yi)) in tx.iter().zip(ty).enumerate() {
513        acc[j] += xi * yi;
514    }
515    ((acc[0] + acc[1]) + acc[2]) + acc[3]
516}
517
518/// Step W1 for `axpy`.
519#[inline(always)]
520pub(crate) fn axpy<L: Lanes>(
521    l: L,
522    alpha: DoubleDouble,
523    x: &[DoubleDouble],
524    y: &mut [DoubleDouble],
525) {
526    debug_assert_eq!(x.len(), y.len(), "axpy: the lengths differ");
527    let (cx, tx) = x.as_chunks::<LANES>();
528    let (cy, ty) = y.as_chunks_mut::<LANES>();
529    let al = splat_dd(l, alpha);
530    for (p, q) in cx.iter().zip(cy) {
531        let z = add_q(l, load_dd(l, q), mul_q(l, al, load_dd(l, p)));
532        if l.all_finite(z.0, z.1) {
533            *q = store_dd(l, z);
534        } else {
535            reference::axpy(alpha, p, q);
536        }
537    }
538    reference::axpy(alpha, tx, ty);
539}
540
541/// Step W1 for the column update of `gemm_sub` (step B3 of Chapter 11.5).
542impl<L: Lanes> ColumnUpdate for L {
543    #[inline(always)]
544    fn column_sub(self, c: &mut [DoubleDouble], a: &[DoubleDouble], t: DoubleDouble) {
545        debug_assert_eq!(c.len(), a.len(), "column_sub: the lengths differ");
546        let l = self;
547        let (cc, tc) = c.as_chunks_mut::<LANES>();
548        let (ca, ta) = a.as_chunks::<LANES>();
549        let tq = splat_dd(l, t);
550        for (q, p) in cc.iter_mut().zip(ca) {
551            let prod = mul_q(l, load_dd(l, p), tq);
552            let z = add_q(l, load_dd(l, q), (l.neg(prod.0), l.neg(prod.1)));
553            if l.all_finite(z.0, z.1) {
554                *q = store_dd(l, z);
555            } else {
556                reference::Reference.column_sub(q, p, t);
557            }
558        }
559        reference::Reference.column_sub(tc, ta, t);
560    }
561}
562
563#[cfg(test)]
564mod tests {
565    use super::*;
566
567    /// Invariant (L1) for a backend: every operation, lane by lane, against
568    /// `f64`.
569    fn lanes_follow_f64<L: Lanes>(l: L) {
570        let a = [1.0 + f64::EPSILON, -3.5e200, 1e-310, f64::INFINITY];
571        let b = [1.0 - f64::EPSILON / 2.0, 2.25e150, -7.0, 1.0];
572        let c = [-1.0, f64::MAX, 3e-320, f64::NAN];
573        let (va, vb, vc) = (l.load(a), l.load(b), l.load(c));
574        let same = |v: L::V, f: &dyn Fn(usize) -> f64| {
575            for (k, got) in l.store(v).into_iter().enumerate() {
576                let want = f(k);
577                assert!(
578                    got.to_bits() == want.to_bits() || (got.is_nan() && want.is_nan()),
579                    "lane {k}: {got:e} != {want:e}"
580                );
581            }
582        };
583        same(va, &|k| a[k]);
584        same(l.splat(0.1), &|_| 0.1);
585        same(l.add(va, vb), &|k| a[k] + b[k]);
586        same(l.sub(va, vb), &|k| a[k] - b[k]);
587        same(l.mul(va, vb), &|k| a[k] * b[k]);
588        same(l.mul_add(va, vb, vc), &|k| a[k].mul_add(b[k], c[k]));
589        same(l.neg(vc), &|k| -c[k]);
590        same(l.abs(vb), &|k| b[k].abs());
591        // The FMA is fused: (1 + ε)(1 − ε/2) − 1 has a term ε²/2 that a
592        // rounded product loses.
593        let fused = l.store(l.mul_add(va, vb, l.splat(-1.0)))[0];
594        assert_eq!(fused, a[0].mul_add(b[0], -1.0));
595        assert_ne!(fused, a[0] * b[0] - 1.0);
596        assert!(l.all_finite(l.splat(1.0), l.load([0.0, -0.0, f64::MAX, 5e-324])));
597        for bad in [f64::INFINITY, f64::NEG_INFINITY, f64::NAN] {
598            for k in 0..LANES {
599                let mut v = [1.0; LANES];
600                v[k] = bad;
601                assert!(!l.all_finite(l.load(v), l.splat(0.0)));
602                assert!(!l.all_finite(l.splat(0.0), l.load(v)));
603            }
604        }
605    }
606
607    #[test]
608    fn the_native_backend_follows_f64() {
609        #[cfg(target_arch = "aarch64")]
610        if let Some(token) = pulp::aarch64::Neon::try_new() {
611            token.vectorize(|| lanes_follow_f64(X2::new(token)));
612        }
613        #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
614        if let Some(token) = pulp::x86::V3::try_new() {
615            token.vectorize(|| lanes_follow_f64(X4::new(token)));
616        }
617    }
618}