Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
InverseSize4.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2001 Intel Corporation
5// Copyright (C) 2010 Gael Guennebaud <gael.guennebaud@inria.fr>
6// Copyright (C) 2009 Benoit Jacob <jacob.benoit.1@gmail.com>
7//
8// This Source Code Form is subject to the terms of the Mozilla
9// Public License v. 2.0. If a copy of the MPL was not distributed
10// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
11//
12// The algorithm below is a reimplementation of former \src\LU\Inverse_SSE.h using PacketMath.
13// inv(M) = M#/|M|, where inv(M), M# and |M| denote the inverse of M,
14// adjugate of M and determinant of M respectively. M# is computed block-wise
15// using specific formulae. For proof, see:
16// https://lxjk.github.io/2017/09/03/Fast-4x4-Matrix-Inverse-with-SSE-SIMD-Explained.html
17// Variable names are adopted from \src\LU\Inverse_SSE.h.
18//
19// The SSE code for the 4x4 float and double matrix inverse in former (deprecated) \src\LU\Inverse_SSE.h
20// comes from the following Intel's library:
21// http://software.intel.com/en-us/articles/optimized-matrix-library-for-use-with-the-intel-pentiumr-4-processors-sse2-instructions/
22//
23// Here is the respective copyright and license statement:
24//
25// Copyright (c) 2001 Intel Corporation.
26//
27// Permission is granted to use, copy, distribute and prepare derivative works
28// of this library for any purpose and without fee, provided, that the above
29// copyright notice and this statement appear in all copies.
30// Intel makes no representations about the suitability of this software for
31// any purpose, and specifically disclaims all warranties.
32// See LEGAL.TXT for all the legal information.
33//
34// TODO: Unify implementations of different data types (i.e. float and double).
35// SPDX-License-Identifier: MPL-2.0
36#ifndef EIGEN_INVERSE_SIZE_4_H
37#define EIGEN_INVERSE_SIZE_4_H
38
39// IWYU pragma: private
40#include "../InternalHeaderCheck.h"
41
42#if EIGEN_COMP_GNUC_STRICT
43// These routines requires bit manipulation of the sign, which is not compatible
44// with fastmath.
45#pragma GCC push_options
46#pragma GCC optimize("no-fast-math")
47#endif
48
49namespace Eigen {
50namespace internal {
51
52// The packet kernels below store whole packets along the inner dimension of the result, so they require a unit inner
53// stride. Other destinations are computed into a contiguous temporary and copied.
54template <typename ResultType>
55EIGEN_STRONG_INLINE bool inverse_size4_has_unit_inner_stride(const ResultType &result) {
56 return ResultType::InnerStrideAtCompileTime == 1 || result.innerStride() == 1;
57}
58
59template <typename Scalar, typename ResultType>
60using inverse_size4_contiguous_result_t = Matrix<Scalar, 4, 4, (ResultType::Flags & RowMajorBit) ? RowMajor : ColMajor>;
61
62template <typename MatrixType, typename ResultType>
63struct compute_inverse_size4<Architecture::Target, float, MatrixType, ResultType> {
64 enum {
65 MatrixAlignment = traits<MatrixType>::Alignment,
66 ResultAlignment = traits<ResultType>::Alignment,
67 StorageOrdersMatch = (MatrixType::Flags & RowMajorBit) == (ResultType::Flags & RowMajorBit)
68 };
69 using ActualMatrixType =
70 std::conditional_t<(MatrixType::Flags & LinearAccessBit), const MatrixType &, typename MatrixType::PlainObject>;
71
72 static void run(const MatrixType &mat, ResultType &result) {
73 if (EIGEN_PREDICT_FALSE(!inverse_size4_has_unit_inner_stride(result))) {
74 run_strided_result(mat, result);
75 } else {
76 run_unit_inner_stride(mat, result);
77 }
78 }
79
80 static EIGEN_DONT_INLINE void run_strided_result(const MatrixType &mat, ResultType &result) {
81 inverse_size4_contiguous_result_t<float, ResultType> contiguous;
82 compute_inverse_size4<Architecture::Target, float, MatrixType, decltype(contiguous)>::run(mat, contiguous);
83 result = contiguous;
84 }
85
86 static void run_unit_inner_stride(const MatrixType &mat, ResultType &result) {
87 ActualMatrixType matrix(mat);
88
89 const float *data = matrix.data();
90 const Index stride = matrix.innerStride();
91 Packet4f L1 = ploadt<Packet4f, MatrixAlignment>(data);
92 Packet4f L2 = ploadt<Packet4f, MatrixAlignment>(data + stride * 4);
93 Packet4f L3 = ploadt<Packet4f, MatrixAlignment>(data + stride * 8);
94 Packet4f L4 = ploadt<Packet4f, MatrixAlignment>(data + stride * 12);
95
96 // Four 2x2 sub-matrices of the input matrix
97 // input = [[A, B],
98 // [C, D]]
99 Packet4f A, B, C, D;
100
101 EIGEN_IF_CONSTEXPR (!StorageOrdersMatch) {
102 A = vec4f_unpacklo(L1, L2);
103 B = vec4f_unpacklo(L3, L4);
104 C = vec4f_unpackhi(L1, L2);
105 D = vec4f_unpackhi(L3, L4);
106 } else {
107 A = vec4f_movelh(L1, L2);
108 B = vec4f_movehl(L2, L1);
109 C = vec4f_movelh(L3, L4);
110 D = vec4f_movehl(L4, L3);
111 }
112
113 Packet4f AB, DC;
114
115 // AB = A# * B, where A# denotes the adjugate of A, and * denotes matrix product.
116 AB = pmul(vec4f_swizzle2(A, A, 3, 3, 0, 0), B);
117 AB = pnmadd(vec4f_swizzle2(A, A, 1, 1, 2, 2), vec4f_swizzle2(B, B, 2, 3, 0, 1), AB);
118
119 // DC = D#*C
120 DC = pmul(vec4f_swizzle2(D, D, 3, 3, 0, 0), C);
121 DC = pnmadd(vec4f_swizzle2(D, D, 1, 1, 2, 2), vec4f_swizzle2(C, C, 2, 3, 0, 1), DC);
122
123 // determinants of the sub-matrices
124 Packet4f dA, dB, dC, dD;
125
126 dA = pmul(vec4f_swizzle2(A, A, 3, 3, 1, 1), A);
127 dA = psub(dA, vec4f_movehl(dA, dA));
128
129 dB = pmul(vec4f_swizzle2(B, B, 3, 3, 1, 1), B);
130 dB = psub(dB, vec4f_movehl(dB, dB));
131
132 dC = pmul(vec4f_swizzle2(C, C, 3, 3, 1, 1), C);
133 dC = psub(dC, vec4f_movehl(dC, dC));
134
135 dD = pmul(vec4f_swizzle2(D, D, 3, 3, 1, 1), D);
136 dD = psub(dD, vec4f_movehl(dD, dD));
137
138 Packet4f d, d1, d2;
139
140 d = pmul(vec4f_swizzle2(DC, DC, 0, 2, 1, 3), AB);
141 d = padd(d, vec4f_movehl(d, d));
142 d = padd(d, vec4f_swizzle2(d, d, 1, 0, 0, 0));
143 d1 = pmul(dA, dD);
144 d2 = pmul(dB, dC);
145
146 // determinant of the input matrix, det = |A||D| + |B||C| - trace(A#*B*D#*C)
147 Packet4f det = vec4f_duplane(psub(padd(d1, d2), d), 0);
148
149 // reciprocal of the determinant of the input matrix, rd = 1/det
150 Packet4f rd = preciprocal(det);
151
152 // Four sub-matrices of the inverse
153 Packet4f iA, iB, iC, iD;
154
155 // iD = D*|A| - C*A#*B
156 iD = pmul(vec4f_swizzle2(C, C, 0, 0, 2, 2), vec4f_movelh(AB, AB));
157 iD = pmadd(vec4f_swizzle2(C, C, 1, 1, 3, 3), vec4f_movehl(AB, AB), iD);
158 iD = pmsub(D, vec4f_duplane(dA, 0), iD);
159
160 // iA = A*|D| - B*D#*C
161 iA = pmul(vec4f_swizzle2(B, B, 0, 0, 2, 2), vec4f_movelh(DC, DC));
162 iA = pmadd(vec4f_swizzle2(B, B, 1, 1, 3, 3), vec4f_movehl(DC, DC), iA);
163 iA = pmsub(A, vec4f_duplane(dD, 0), iA);
164
165 // iB = C*|B| - D * (A#B)# = C*|B| - D*B#*A
166 iB = pmul(D, vec4f_swizzle2(AB, AB, 3, 0, 3, 0));
167 iB = pnmadd(vec4f_swizzle2(D, D, 1, 0, 3, 2), vec4f_swizzle2(AB, AB, 2, 1, 2, 1), iB);
168 iB = pmsub(C, vec4f_duplane(dB, 0), iB);
169
170 // iC = B*|C| - A * (D#C)# = B*|C| - A*C#*D
171 iC = pmul(A, vec4f_swizzle2(DC, DC, 3, 0, 3, 0));
172 iC = pnmadd(vec4f_swizzle2(A, A, 1, 0, 3, 2), vec4f_swizzle2(DC, DC, 2, 1, 2, 1), iC);
173 iC = pmsub(B, vec4f_duplane(dC, 0), iC);
174
175 // Built from integer bits: a -0.0f literal may be replaced by +0.0f under fast-math.
176 const float neg_zero = numext::bit_cast<float>(0x80000000u);
177 EIGEN_ALIGN_TO_BOUNDARY(unpacket_traits<Packet4f>::alignment)
178 const float sign_mask[4] = {0.0f, neg_zero, neg_zero, 0.0f};
179 const Packet4f p4f_sign_PNNP = pload<Packet4f>(sign_mask);
180 rd = pxor(rd, p4f_sign_PNNP);
181 iA = pmul(iA, rd);
182 iB = pmul(iB, rd);
183 iC = pmul(iC, rd);
184 iD = pmul(iD, rd);
185
186 Index res_stride = result.outerStride();
187 float *res = result.data();
188
189 pstoret<float, Packet4f, ResultAlignment>(res + 0, vec4f_swizzle2(iA, iB, 3, 1, 3, 1));
190 pstoret<float, Packet4f, ResultAlignment>(res + res_stride, vec4f_swizzle2(iA, iB, 2, 0, 2, 0));
191 pstoret<float, Packet4f, ResultAlignment>(res + 2 * res_stride, vec4f_swizzle2(iC, iD, 3, 1, 3, 1));
192 pstoret<float, Packet4f, ResultAlignment>(res + 3 * res_stride, vec4f_swizzle2(iC, iD, 2, 0, 2, 0));
193 }
194};
195
196#if !defined(EIGEN_VECTORIZE_NEON) || EIGEN_ARCH_ARM64
197// same algorithm as above, except that each operand is split into
198// halves for two registers to hold.
199template <typename MatrixType, typename ResultType>
200struct compute_inverse_size4<Architecture::Target, double, MatrixType, ResultType> {
201 enum {
202 MatrixAlignment = traits<MatrixType>::Alignment,
203 ResultAlignment = traits<ResultType>::Alignment,
204 StorageOrdersMatch = (MatrixType::Flags & RowMajorBit) == (ResultType::Flags & RowMajorBit)
205 };
206 using ActualMatrixType =
207 std::conditional_t<(MatrixType::Flags & LinearAccessBit), const MatrixType &, typename MatrixType::PlainObject>;
208
209 static void run(const MatrixType &mat, ResultType &result) {
210 if (EIGEN_PREDICT_FALSE(!inverse_size4_has_unit_inner_stride(result))) {
211 run_strided_result(mat, result);
212 } else {
213 run_unit_inner_stride(mat, result);
214 }
215 }
216
217 static EIGEN_DONT_INLINE void run_strided_result(const MatrixType &mat, ResultType &result) {
218 inverse_size4_contiguous_result_t<double, ResultType> contiguous;
219 compute_inverse_size4<Architecture::Target, double, MatrixType, decltype(contiguous)>::run(mat, contiguous);
220 result = contiguous;
221 }
222
223 static void run_unit_inner_stride(const MatrixType &mat, ResultType &result) {
224 ActualMatrixType matrix(mat);
225
226 // Four 2x2 sub-matrices of the input matrix, each is further divided into upper and lower
227 // row e.g. A1, upper row of A, A2, lower row of A
228 // input = [[A, B], = [[[A1, [B1,
229 // [C, D]] A2], B2]],
230 // [[C1, [D1,
231 // C2], D2]]]
232
233 Packet2d A1, A2, B1, B2, C1, C2, D1, D2;
234
235 const double *data = matrix.data();
236 const Index stride = matrix.innerStride();
237 EIGEN_IF_CONSTEXPR (StorageOrdersMatch) {
238 A1 = ploadt<Packet2d, MatrixAlignment>(data + stride * 0);
239 B1 = ploadt<Packet2d, MatrixAlignment>(data + stride * 2);
240 A2 = ploadt<Packet2d, MatrixAlignment>(data + stride * 4);
241 B2 = ploadt<Packet2d, MatrixAlignment>(data + stride * 6);
242 C1 = ploadt<Packet2d, MatrixAlignment>(data + stride * 8);
243 D1 = ploadt<Packet2d, MatrixAlignment>(data + stride * 10);
244 C2 = ploadt<Packet2d, MatrixAlignment>(data + stride * 12);
245 D2 = ploadt<Packet2d, MatrixAlignment>(data + stride * 14);
246 } else {
247 Packet2d temp;
248 A1 = ploadt<Packet2d, MatrixAlignment>(data + stride * 0);
249 C1 = ploadt<Packet2d, MatrixAlignment>(data + stride * 2);
250 A2 = ploadt<Packet2d, MatrixAlignment>(data + stride * 4);
251 C2 = ploadt<Packet2d, MatrixAlignment>(data + stride * 6);
252 temp = A1;
253 A1 = vec2d_unpacklo(A1, A2);
254 A2 = vec2d_unpackhi(temp, A2);
255
256 temp = C1;
257 C1 = vec2d_unpacklo(C1, C2);
258 C2 = vec2d_unpackhi(temp, C2);
259
260 B1 = ploadt<Packet2d, MatrixAlignment>(data + stride * 8);
261 D1 = ploadt<Packet2d, MatrixAlignment>(data + stride * 10);
262 B2 = ploadt<Packet2d, MatrixAlignment>(data + stride * 12);
263 D2 = ploadt<Packet2d, MatrixAlignment>(data + stride * 14);
264
265 temp = B1;
266 B1 = vec2d_unpacklo(B1, B2);
267 B2 = vec2d_unpackhi(temp, B2);
268
269 temp = D1;
270 D1 = vec2d_unpacklo(D1, D2);
271 D2 = vec2d_unpackhi(temp, D2);
272 }
273
274 // determinants of the sub-matrices
275 Packet2d dA, dB, dC, dD;
276
277 dA = vec2d_swizzle2(A2, A2, 1);
278 dA = pmul(A1, dA);
279 dA = psub(dA, vec2d_duplane(dA, 1));
280
281 dB = vec2d_swizzle2(B2, B2, 1);
282 dB = pmul(B1, dB);
283 dB = psub(dB, vec2d_duplane(dB, 1));
284
285 dC = vec2d_swizzle2(C2, C2, 1);
286 dC = pmul(C1, dC);
287 dC = psub(dC, vec2d_duplane(dC, 1));
288
289 dD = vec2d_swizzle2(D2, D2, 1);
290 dD = pmul(D1, dD);
291 dD = psub(dD, vec2d_duplane(dD, 1));
292
293 Packet2d DC1, DC2, AB1, AB2;
294
295 // AB = A# * B, where A# denotes the adjugate of A, and * denotes matrix product.
296 AB1 = pmul(B1, vec2d_duplane(A2, 1));
297 AB2 = pmul(B2, vec2d_duplane(A1, 0));
298 AB1 = pnmadd(B2, vec2d_duplane(A1, 1), AB1);
299 AB2 = pnmadd(B1, vec2d_duplane(A2, 0), AB2);
300
301 // DC = D#*C
302 DC1 = pmul(C1, vec2d_duplane(D2, 1));
303 DC2 = pmul(C2, vec2d_duplane(D1, 0));
304 DC1 = pnmadd(C2, vec2d_duplane(D1, 1), DC1);
305 DC2 = pnmadd(C1, vec2d_duplane(D2, 0), DC2);
306
307 Packet2d d1, d2;
308
309 // determinant of the input matrix, det = |A||D| + |B||C| - trace(A#*B*D#*C)
310 Packet2d det;
311
312 // reciprocal of the determinant of the input matrix, rd = 1/det
313 Packet2d rd;
314
315 d1 = pmul(AB1, vec2d_swizzle2(DC1, DC2, 0));
316 d2 = pmul(AB2, vec2d_swizzle2(DC1, DC2, 3));
317 rd = padd(d1, d2);
318 rd = padd(rd, vec2d_duplane(rd, 1));
319
320 d1 = pmul(dA, dD);
321 d2 = pmul(dB, dC);
322
323 det = padd(d1, d2);
324 det = psub(det, rd);
325 det = vec2d_duplane(det, 0);
326 rd = pdiv(pset1<Packet2d>(1.0), det);
327
328 // rows of four sub-matrices of the inverse
329 Packet2d iA1, iA2, iB1, iB2, iC1, iC2, iD1, iD2;
330
331 // iD = D*|A| - C*A#*B
332 iD1 = pmul(AB1, vec2d_duplane(C1, 0));
333 iD2 = pmul(AB1, vec2d_duplane(C2, 0));
334 iD1 = pmadd(AB2, vec2d_duplane(C1, 1), iD1);
335 iD2 = pmadd(AB2, vec2d_duplane(C2, 1), iD2);
336 dA = vec2d_duplane(dA, 0);
337 iD1 = pmsub(D1, dA, iD1);
338 iD2 = pmsub(D2, dA, iD2);
339
340 // iA = A*|D| - B*D#*C
341 iA1 = pmul(DC1, vec2d_duplane(B1, 0));
342 iA2 = pmul(DC1, vec2d_duplane(B2, 0));
343 iA1 = pmadd(DC2, vec2d_duplane(B1, 1), iA1);
344 iA2 = pmadd(DC2, vec2d_duplane(B2, 1), iA2);
345 dD = vec2d_duplane(dD, 0);
346 iA1 = pmsub(A1, dD, iA1);
347 iA2 = pmsub(A2, dD, iA2);
348
349 // iB = C*|B| - D * (A#B)# = C*|B| - D*B#*A
350 iB1 = pmul(D1, vec2d_swizzle2(AB2, AB1, 1));
351 iB2 = pmul(D2, vec2d_swizzle2(AB2, AB1, 1));
352 iB1 = pnmadd(vec2d_swizzle2(D1, D1, 1), vec2d_swizzle2(AB2, AB1, 2), iB1);
353 iB2 = pnmadd(vec2d_swizzle2(D2, D2, 1), vec2d_swizzle2(AB2, AB1, 2), iB2);
354 dB = vec2d_duplane(dB, 0);
355 iB1 = pmsub(C1, dB, iB1);
356 iB2 = pmsub(C2, dB, iB2);
357
358 // iC = B*|C| - A * (D#C)# = B*|C| - A*C#*D
359 iC1 = pmul(A1, vec2d_swizzle2(DC2, DC1, 1));
360 iC2 = pmul(A2, vec2d_swizzle2(DC2, DC1, 1));
361 iC1 = pnmadd(vec2d_swizzle2(A1, A1, 1), vec2d_swizzle2(DC2, DC1, 2), iC1);
362 iC2 = pnmadd(vec2d_swizzle2(A2, A2, 1), vec2d_swizzle2(DC2, DC1, 2), iC2);
363 dC = vec2d_duplane(dC, 0);
364 iC1 = pmsub(B1, dC, iC1);
365 iC2 = pmsub(B2, dC, iC2);
366
367 // Built from integer bits: a -0.0 literal may be replaced by +0.0 under fast-math.
368 const double neg_zero = numext::bit_cast<double>(0x8000000000000000ull);
369 EIGEN_ALIGN_TO_BOUNDARY(unpacket_traits<Packet2d>::alignment) const double sign_mask1[2] = {0.0, neg_zero};
370 EIGEN_ALIGN_TO_BOUNDARY(unpacket_traits<Packet2d>::alignment) const double sign_mask2[2] = {neg_zero, 0.0};
371 const Packet2d sign_PN = pload<Packet2d>(sign_mask1);
372 const Packet2d sign_NP = pload<Packet2d>(sign_mask2);
373 d1 = pxor(rd, sign_PN);
374 d2 = pxor(rd, sign_NP);
375
376 Index res_stride = result.outerStride();
377 double *res = result.data();
378 pstoret<double, Packet2d, ResultAlignment>(res + 0, pmul(vec2d_swizzle2(iA2, iA1, 3), d1));
379 pstoret<double, Packet2d, ResultAlignment>(res + res_stride, pmul(vec2d_swizzle2(iA2, iA1, 0), d2));
380 pstoret<double, Packet2d, ResultAlignment>(res + 2, pmul(vec2d_swizzle2(iB2, iB1, 3), d1));
381 pstoret<double, Packet2d, ResultAlignment>(res + res_stride + 2, pmul(vec2d_swizzle2(iB2, iB1, 0), d2));
382 pstoret<double, Packet2d, ResultAlignment>(res + 2 * res_stride, pmul(vec2d_swizzle2(iC2, iC1, 3), d1));
383 pstoret<double, Packet2d, ResultAlignment>(res + 3 * res_stride, pmul(vec2d_swizzle2(iC2, iC1, 0), d2));
384 pstoret<double, Packet2d, ResultAlignment>(res + 2 * res_stride + 2, pmul(vec2d_swizzle2(iD2, iD1, 3), d1));
385 pstoret<double, Packet2d, ResultAlignment>(res + 3 * res_stride + 2, pmul(vec2d_swizzle2(iD2, iD1, 0), d2));
386 }
387};
388#endif
389} // namespace internal
390} // namespace Eigen
391
392#if EIGEN_COMP_GNUC_STRICT
393#pragma GCC pop_options
394#endif
395
396#endif
@ ColMajor
Definition Constants.h:319
@ RowMajor
Definition Constants.h:321
constexpr unsigned int LinearAccessBit
Definition Constants.h:134
constexpr unsigned int RowMajorBit
Definition Constants.h:71