Another set of UI messages fixes and tweaks! No functional changes.
[blender.git] / extern / Eigen3 / Eigen / src / Core / Redux.h
1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
5 // Copyright (C) 2006-2008 Benoit Jacob <jacob.benoit.1@gmail.com>
6 //
7 // Eigen is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU Lesser General Public
9 // License as published by the Free Software Foundation; either
10 // version 3 of the License, or (at your option) any later version.
11 //
12 // Alternatively, you can redistribute it and/or
13 // modify it under the terms of the GNU General Public License as
14 // published by the Free Software Foundation; either version 2 of
15 // the License, or (at your option) any later version.
16 //
17 // Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
18 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
19 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
20 // GNU General Public License for more details.
21 //
22 // You should have received a copy of the GNU Lesser General Public
23 // License and a copy of the GNU General Public License along with
24 // Eigen. If not, see <http://www.gnu.org/licenses/>.
25
26 #ifndef EIGEN_REDUX_H
27 #define EIGEN_REDUX_H
28
29 namespace internal {
30
31 // TODO
32 //  * implement other kind of vectorization
33 //  * factorize code
34
35 /***************************************************************************
36 * Part 1 : the logic deciding a strategy for vectorization and unrolling
37 ***************************************************************************/
38
39 template<typename Func, typename Derived>
40 struct redux_traits
41 {
42 public:
43   enum {
44     PacketSize = packet_traits<typename Derived::Scalar>::size,
45     InnerMaxSize = int(Derived::IsRowMajor)
46                  ? Derived::MaxColsAtCompileTime
47                  : Derived::MaxRowsAtCompileTime
48   };
49
50   enum {
51     MightVectorize = (int(Derived::Flags)&ActualPacketAccessBit)
52                   && (functor_traits<Func>::PacketAccess),
53     MayLinearVectorize = MightVectorize && (int(Derived::Flags)&LinearAccessBit),
54     MaySliceVectorize  = MightVectorize && int(InnerMaxSize)>=3*PacketSize
55   };
56
57 public:
58   enum {
59     Traversal = int(MayLinearVectorize) ? int(LinearVectorizedTraversal)
60               : int(MaySliceVectorize)  ? int(SliceVectorizedTraversal)
61                                         : int(DefaultTraversal)
62   };
63
64 public:
65   enum {
66     Cost = (  Derived::SizeAtCompileTime == Dynamic
67            || Derived::CoeffReadCost == Dynamic
68            || (Derived::SizeAtCompileTime!=1 && functor_traits<Func>::Cost == Dynamic)
69            ) ? Dynamic
70            : Derived::SizeAtCompileTime * Derived::CoeffReadCost
71                + (Derived::SizeAtCompileTime-1) * functor_traits<Func>::Cost,
72     UnrollingLimit = EIGEN_UNROLLING_LIMIT * (int(Traversal) == int(DefaultTraversal) ? 1 : int(PacketSize))
73   };
74
75 public:
76   enum {
77     Unrolling = Cost != Dynamic && Cost <= UnrollingLimit
78               ? CompleteUnrolling
79               : NoUnrolling
80   };
81 };
82
83 /***************************************************************************
84 * Part 2 : unrollers
85 ***************************************************************************/
86
87 /*** no vectorization ***/
88
89 template<typename Func, typename Derived, int Start, int Length>
90 struct redux_novec_unroller
91 {
92   enum {
93     HalfLength = Length/2
94   };
95
96   typedef typename Derived::Scalar Scalar;
97
98   EIGEN_STRONG_INLINE static Scalar run(const Derived &mat, const Func& func)
99   {
100     return func(redux_novec_unroller<Func, Derived, Start, HalfLength>::run(mat,func),
101                 redux_novec_unroller<Func, Derived, Start+HalfLength, Length-HalfLength>::run(mat,func));
102   }
103 };
104
105 template<typename Func, typename Derived, int Start>
106 struct redux_novec_unroller<Func, Derived, Start, 1>
107 {
108   enum {
109     outer = Start / Derived::InnerSizeAtCompileTime,
110     inner = Start % Derived::InnerSizeAtCompileTime
111   };
112
113   typedef typename Derived::Scalar Scalar;
114
115   EIGEN_STRONG_INLINE static Scalar run(const Derived &mat, const Func&)
116   {
117     return mat.coeffByOuterInner(outer, inner);
118   }
119 };
120
121 // This is actually dead code and will never be called. It is required
122 // to prevent false warnings regarding failed inlining though
123 // for 0 length run() will never be called at all.
124 template<typename Func, typename Derived, int Start>
125 struct redux_novec_unroller<Func, Derived, Start, 0>
126 {
127   typedef typename Derived::Scalar Scalar;
128   EIGEN_STRONG_INLINE static Scalar run(const Derived&, const Func&) { return Scalar(); }
129 };
130
131 /*** vectorization ***/
132
133 template<typename Func, typename Derived, int Start, int Length>
134 struct redux_vec_unroller
135 {
136   enum {
137     PacketSize = packet_traits<typename Derived::Scalar>::size,
138     HalfLength = Length/2
139   };
140
141   typedef typename Derived::Scalar Scalar;
142   typedef typename packet_traits<Scalar>::type PacketScalar;
143
144   EIGEN_STRONG_INLINE static PacketScalar run(const Derived &mat, const Func& func)
145   {
146     return func.packetOp(
147             redux_vec_unroller<Func, Derived, Start, HalfLength>::run(mat,func),
148             redux_vec_unroller<Func, Derived, Start+HalfLength, Length-HalfLength>::run(mat,func) );
149   }
150 };
151
152 template<typename Func, typename Derived, int Start>
153 struct redux_vec_unroller<Func, Derived, Start, 1>
154 {
155   enum {
156     index = Start * packet_traits<typename Derived::Scalar>::size,
157     outer = index / int(Derived::InnerSizeAtCompileTime),
158     inner = index % int(Derived::InnerSizeAtCompileTime),
159     alignment = (Derived::Flags & AlignedBit) ? Aligned : Unaligned
160   };
161
162   typedef typename Derived::Scalar Scalar;
163   typedef typename packet_traits<Scalar>::type PacketScalar;
164
165   EIGEN_STRONG_INLINE static PacketScalar run(const Derived &mat, const Func&)
166   {
167     return mat.template packetByOuterInner<alignment>(outer, inner);
168   }
169 };
170
171 /***************************************************************************
172 * Part 3 : implementation of all cases
173 ***************************************************************************/
174
175 template<typename Func, typename Derived,
176          int Traversal = redux_traits<Func, Derived>::Traversal,
177          int Unrolling = redux_traits<Func, Derived>::Unrolling
178 >
179 struct redux_impl;
180
181 template<typename Func, typename Derived>
182 struct redux_impl<Func, Derived, DefaultTraversal, NoUnrolling>
183 {
184   typedef typename Derived::Scalar Scalar;
185   typedef typename Derived::Index Index;
186   static EIGEN_STRONG_INLINE Scalar run(const Derived& mat, const Func& func)
187   {
188     eigen_assert(mat.rows()>0 && mat.cols()>0 && "you are using an empty matrix");
189     Scalar res;
190     res = mat.coeffByOuterInner(0, 0);
191     for(Index i = 1; i < mat.innerSize(); ++i)
192       res = func(res, mat.coeffByOuterInner(0, i));
193     for(Index i = 1; i < mat.outerSize(); ++i)
194       for(Index j = 0; j < mat.innerSize(); ++j)
195         res = func(res, mat.coeffByOuterInner(i, j));
196     return res;
197   }
198 };
199
200 template<typename Func, typename Derived>
201 struct redux_impl<Func,Derived, DefaultTraversal, CompleteUnrolling>
202   : public redux_novec_unroller<Func,Derived, 0, Derived::SizeAtCompileTime>
203 {};
204
205 template<typename Func, typename Derived>
206 struct redux_impl<Func, Derived, LinearVectorizedTraversal, NoUnrolling>
207 {
208   typedef typename Derived::Scalar Scalar;
209   typedef typename packet_traits<Scalar>::type PacketScalar;
210   typedef typename Derived::Index Index;
211
212   static Scalar run(const Derived& mat, const Func& func)
213   {
214     const Index size = mat.size();
215     eigen_assert(size && "you are using an empty matrix");
216     const Index packetSize = packet_traits<Scalar>::size;
217     const Index alignedStart = first_aligned(mat);
218     enum {
219       alignment = bool(Derived::Flags & DirectAccessBit) || bool(Derived::Flags & AlignedBit)
220                 ? Aligned : Unaligned
221     };
222     const Index alignedSize = ((size-alignedStart)/packetSize)*packetSize;
223     const Index alignedEnd = alignedStart + alignedSize;
224     Scalar res;
225     if(alignedSize)
226     {
227       PacketScalar packet_res = mat.template packet<alignment>(alignedStart);
228       for(Index index = alignedStart + packetSize; index < alignedEnd; index += packetSize)
229         packet_res = func.packetOp(packet_res, mat.template packet<alignment>(index));
230       res = func.predux(packet_res);
231
232       for(Index index = 0; index < alignedStart; ++index)
233         res = func(res,mat.coeff(index));
234
235       for(Index index = alignedEnd; index < size; ++index)
236         res = func(res,mat.coeff(index));
237     }
238     else // too small to vectorize anything.
239          // since this is dynamic-size hence inefficient anyway for such small sizes, don't try to optimize.
240     {
241       res = mat.coeff(0);
242       for(Index index = 1; index < size; ++index)
243         res = func(res,mat.coeff(index));
244     }
245
246     return res;
247   }
248 };
249
250 template<typename Func, typename Derived>
251 struct redux_impl<Func, Derived, SliceVectorizedTraversal, NoUnrolling>
252 {
253   typedef typename Derived::Scalar Scalar;
254   typedef typename packet_traits<Scalar>::type PacketScalar;
255   typedef typename Derived::Index Index;
256
257   static Scalar run(const Derived& mat, const Func& func)
258   {
259     eigen_assert(mat.rows()>0 && mat.cols()>0 && "you are using an empty matrix");
260     const Index innerSize = mat.innerSize();
261     const Index outerSize = mat.outerSize();
262     enum {
263       packetSize = packet_traits<Scalar>::size
264     };
265     const Index packetedInnerSize = ((innerSize)/packetSize)*packetSize;
266     Scalar res;
267     if(packetedInnerSize)
268     {
269       PacketScalar packet_res = mat.template packet<Unaligned>(0,0);
270       for(Index j=0; j<outerSize; ++j)
271         for(Index i=(j==0?packetSize:0); i<packetedInnerSize; i+=Index(packetSize))
272           packet_res = func.packetOp(packet_res, mat.template packetByOuterInner<Unaligned>(j,i));
273
274       res = func.predux(packet_res);
275       for(Index j=0; j<outerSize; ++j)
276         for(Index i=packetedInnerSize; i<innerSize; ++i)
277           res = func(res, mat.coeffByOuterInner(j,i));
278     }
279     else // too small to vectorize anything.
280          // since this is dynamic-size hence inefficient anyway for such small sizes, don't try to optimize.
281     {
282       res = redux_impl<Func, Derived, DefaultTraversal, NoUnrolling>::run(mat, func);
283     }
284
285     return res;
286   }
287 };
288
289 template<typename Func, typename Derived>
290 struct redux_impl<Func, Derived, LinearVectorizedTraversal, CompleteUnrolling>
291 {
292   typedef typename Derived::Scalar Scalar;
293   typedef typename packet_traits<Scalar>::type PacketScalar;
294   enum {
295     PacketSize = packet_traits<Scalar>::size,
296     Size = Derived::SizeAtCompileTime,
297     VectorizedSize = (Size / PacketSize) * PacketSize
298   };
299   EIGEN_STRONG_INLINE static Scalar run(const Derived& mat, const Func& func)
300   {
301     eigen_assert(mat.rows()>0 && mat.cols()>0 && "you are using an empty matrix");
302     Scalar res = func.predux(redux_vec_unroller<Func, Derived, 0, Size / PacketSize>::run(mat,func));
303     if (VectorizedSize != Size)
304       res = func(res,redux_novec_unroller<Func, Derived, VectorizedSize, Size-VectorizedSize>::run(mat,func));
305     return res;
306   }
307 };
308
309 } // end namespace internal
310
311 /***************************************************************************
312 * Part 4 : public API
313 ***************************************************************************/
314
315
316 /** \returns the result of a full redux operation on the whole matrix or vector using \a func
317   *
318   * The template parameter \a BinaryOp is the type of the functor \a func which must be
319   * an associative operator. Both current STL and TR1 functor styles are handled.
320   *
321   * \sa DenseBase::sum(), DenseBase::minCoeff(), DenseBase::maxCoeff(), MatrixBase::colwise(), MatrixBase::rowwise()
322   */
323 template<typename Derived>
324 template<typename Func>
325 EIGEN_STRONG_INLINE typename internal::result_of<Func(typename internal::traits<Derived>::Scalar)>::type
326 DenseBase<Derived>::redux(const Func& func) const
327 {
328   typedef typename internal::remove_all<typename Derived::Nested>::type ThisNested;
329   return internal::redux_impl<Func, ThisNested>
330             ::run(derived(), func);
331 }
332
333 /** \returns the minimum of all coefficients of *this
334   */
335 template<typename Derived>
336 EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar
337 DenseBase<Derived>::minCoeff() const
338 {
339   return this->redux(Eigen::internal::scalar_min_op<Scalar>());
340 }
341
342 /** \returns the maximum of all coefficients of *this
343   */
344 template<typename Derived>
345 EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar
346 DenseBase<Derived>::maxCoeff() const
347 {
348   return this->redux(Eigen::internal::scalar_max_op<Scalar>());
349 }
350
351 /** \returns the sum of all coefficients of *this
352   *
353   * \sa trace(), prod(), mean()
354   */
355 template<typename Derived>
356 EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar
357 DenseBase<Derived>::sum() const
358 {
359   if(SizeAtCompileTime==0 || (SizeAtCompileTime==Dynamic && size()==0))
360     return Scalar(0);
361   return this->redux(Eigen::internal::scalar_sum_op<Scalar>());
362 }
363
364 /** \returns the mean of all coefficients of *this
365 *
366 * \sa trace(), prod(), sum()
367 */
368 template<typename Derived>
369 EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar
370 DenseBase<Derived>::mean() const
371 {
372   return Scalar(this->redux(Eigen::internal::scalar_sum_op<Scalar>())) / Scalar(this->size());
373 }
374
375 /** \returns the product of all coefficients of *this
376   *
377   * Example: \include MatrixBase_prod.cpp
378   * Output: \verbinclude MatrixBase_prod.out
379   *
380   * \sa sum(), mean(), trace()
381   */
382 template<typename Derived>
383 EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar
384 DenseBase<Derived>::prod() const
385 {
386   if(SizeAtCompileTime==0 || (SizeAtCompileTime==Dynamic && size()==0))
387     return Scalar(1);
388   return this->redux(Eigen::internal::scalar_product_op<Scalar>());
389 }
390
391 /** \returns the trace of \c *this, i.e. the sum of the coefficients on the main diagonal.
392   *
393   * \c *this can be any matrix, not necessarily square.
394   *
395   * \sa diagonal(), sum()
396   */
397 template<typename Derived>
398 EIGEN_STRONG_INLINE typename internal::traits<Derived>::Scalar
399 MatrixBase<Derived>::trace() const
400 {
401   return derived().diagonal().sum();
402 }
403
404 #endif // EIGEN_REDUX_H