1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2014 Benoit Steiner <benoit.steiner.goog@gmail.com>
5 //
6 // This Source Code Form is subject to the terms of the Mozilla
7 // Public License v. 2.0. If a copy of the MPL was not distributed
8 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9 
10 #ifndef EIGEN_CXX11_TENSOR_TENSOR_PADDING_H
11 #define EIGEN_CXX11_TENSOR_TENSOR_PADDING_H
12 
13 namespace Eigen {
14 
15 /** \class TensorPadding
16   * \ingroup CXX11_Tensor_Module
17   *
18   * \brief Tensor padding class.
19   * At the moment only padding with a constant value is supported.
20   *
21   */
22 namespace internal {
23 template<typename PaddingDimensions, typename XprType>
24 struct traits<TensorPaddingOp<PaddingDimensions, XprType> > : public traits<XprType>
25 {
26   typedef typename XprType::Scalar Scalar;
27   typedef traits<XprType> XprTraits;
28   typedef typename XprTraits::StorageKind StorageKind;
29   typedef typename XprTraits::Index Index;
30   typedef typename XprType::Nested Nested;
31   typedef typename remove_reference<Nested>::type _Nested;
32   static const int NumDimensions = XprTraits::NumDimensions;
33   static const int Layout = XprTraits::Layout;
34 };
35 
36 template<typename PaddingDimensions, typename XprType>
37 struct eval<TensorPaddingOp<PaddingDimensions, XprType>, Eigen::Dense>
38 {
39   typedef const TensorPaddingOp<PaddingDimensions, XprType>& type;
40 };
41 
42 template<typename PaddingDimensions, typename XprType>
43 struct nested<TensorPaddingOp<PaddingDimensions, XprType>, 1, typename eval<TensorPaddingOp<PaddingDimensions, XprType> >::type>
44 {
45   typedef TensorPaddingOp<PaddingDimensions, XprType> type;
46 };
47 
48 }  // end namespace internal
49 
50 
51 
52 template<typename PaddingDimensions, typename XprType>
53 class TensorPaddingOp : public TensorBase<TensorPaddingOp<PaddingDimensions, XprType>, ReadOnlyAccessors>
54 {
55   public:
56   typedef typename Eigen::internal::traits<TensorPaddingOp>::Scalar Scalar;
57   typedef typename Eigen::NumTraits<Scalar>::Real RealScalar;
58   typedef typename XprType::CoeffReturnType CoeffReturnType;
59   typedef typename Eigen::internal::nested<TensorPaddingOp>::type Nested;
60   typedef typename Eigen::internal::traits<TensorPaddingOp>::StorageKind StorageKind;
61   typedef typename Eigen::internal::traits<TensorPaddingOp>::Index Index;
62 
63   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE TensorPaddingOp(const XprType& expr, const PaddingDimensions& padding_dims, const Scalar padding_value)
64       : m_xpr(expr), m_padding_dims(padding_dims), m_padding_value(padding_value) {}
65 
66     EIGEN_DEVICE_FUNC
67     const PaddingDimensions& padding() const { return m_padding_dims; }
68     EIGEN_DEVICE_FUNC
69     Scalar padding_value() const { return m_padding_value; }
70 
71     EIGEN_DEVICE_FUNC
72     const typename internal::remove_all<typename XprType::Nested>::type&
73     expression() const { return m_xpr; }
74 
75   protected:
76     typename XprType::Nested m_xpr;
77     const PaddingDimensions m_padding_dims;
78     const Scalar m_padding_value;
79 };
80 
81 
82 // Eval as rvalue
83 template<typename PaddingDimensions, typename ArgType, typename Device>
84 struct TensorEvaluator<const TensorPaddingOp<PaddingDimensions, ArgType>, Device>
85 {
86   typedef TensorPaddingOp<PaddingDimensions, ArgType> XprType;
87   typedef typename XprType::Index Index;
88   static const int NumDims = internal::array_size<PaddingDimensions>::value;
89   typedef DSizes<Index, NumDims> Dimensions;
90   typedef typename XprType::Scalar Scalar;
91   typedef typename XprType::CoeffReturnType CoeffReturnType;
92   typedef typename PacketType<CoeffReturnType, Device>::type PacketReturnType;
93   static const int PacketSize = internal::unpacket_traits<PacketReturnType>::size;
94 
95   enum {
96     IsAligned = true,
97     PacketAccess = TensorEvaluator<ArgType, Device>::PacketAccess,
98     Layout = TensorEvaluator<ArgType, Device>::Layout,
99     CoordAccess = true,
100     RawAccess = false
101   };
102 
103   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE TensorEvaluator(const XprType& op, const Device& device)
104       : m_impl(op.expression(), device), m_padding(op.padding()), m_paddingValue(op.padding_value())
105   {
106     // The padding op doesn't change the rank of the tensor. Directly padding a scalar would lead
107     // to a vector, which doesn't make sense. Instead one should reshape the scalar into a vector
108     // of 1 element first and then pad.
109     EIGEN_STATIC_ASSERT((NumDims > 0), YOU_MADE_A_PROGRAMMING_MISTAKE);
110 
111     // Compute dimensions
112     m_dimensions = m_impl.dimensions();
113     for (int i = 0; i < NumDims; ++i) {
114       m_dimensions[i] += m_padding[i].first + m_padding[i].second;
115     }
116     const typename TensorEvaluator<ArgType, Device>::Dimensions& input_dims = m_impl.dimensions();
117     if (static_cast<int>(Layout) == static_cast<int>(ColMajor)) {
118       m_inputStrides[0] = 1;
119       m_outputStrides[0] = 1;
120       for (int i = 1; i < NumDims; ++i) {
121         m_inputStrides[i] = m_inputStrides[i-1] * input_dims[i-1];
122         m_outputStrides[i] = m_outputStrides[i-1] * m_dimensions[i-1];
123       }
124       m_outputStrides[NumDims] = m_outputStrides[NumDims-1] * m_dimensions[NumDims-1];
125     } else {
126       m_inputStrides[NumDims - 1] = 1;
127       m_outputStrides[NumDims] = 1;
128       for (int i = NumDims - 2; i >= 0; --i) {
129         m_inputStrides[i] = m_inputStrides[i+1] * input_dims[i+1];
130         m_outputStrides[i+1] = m_outputStrides[i+2] * m_dimensions[i+1];
131       }
132       m_outputStrides[0] = m_outputStrides[1] * m_dimensions[0];
133     }
134   }
135 
136   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE const Dimensions& dimensions() const { return m_dimensions; }
137 
138   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE bool evalSubExprsIfNeeded(Scalar*) {
139     m_impl.evalSubExprsIfNeeded(NULL);
140     return true;
141   }
142   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void cleanup() {
143     m_impl.cleanup();
144   }
145 
146   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE CoeffReturnType coeff(Index index) const
147   {
148     eigen_assert(index < dimensions().TotalSize());
149     Index inputIndex = 0;
150     if (static_cast<int>(Layout) == static_cast<int>(ColMajor)) {
151       for (int i = NumDims - 1; i > 0; --i) {
152         const Index idx = index / m_outputStrides[i];
153         if (isPaddingAtIndexForDim(idx, i)) {
154           return m_paddingValue;
155         }
156         inputIndex += (idx - m_padding[i].first) * m_inputStrides[i];
157         index -= idx * m_outputStrides[i];
158       }
159       if (isPaddingAtIndexForDim(index, 0)) {
160         return m_paddingValue;
161       }
162       inputIndex += (index - m_padding[0].first);
163     } else {
164       for (int i = 0; i < NumDims - 1; ++i) {
165         const Index idx = index / m_outputStrides[i+1];
166         if (isPaddingAtIndexForDim(idx, i)) {
167           return m_paddingValue;
168         }
169         inputIndex += (idx - m_padding[i].first) * m_inputStrides[i];
170         index -= idx * m_outputStrides[i+1];
171       }
172       if (isPaddingAtIndexForDim(index, NumDims-1)) {
173         return m_paddingValue;
174       }
175       inputIndex += (index - m_padding[NumDims-1].first);
176     }
177     return m_impl.coeff(inputIndex);
178   }
179 
180   template<int LoadMode>
181   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE PacketReturnType packet(Index index) const
182   {
183     if (static_cast<int>(Layout) == static_cast<int>(ColMajor)) {
184       return packetColMajor(index);
185     }
186     return packetRowMajor(index);
187   }
188 
189   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE TensorOpCost costPerCoeff(bool vectorized) const {
190     TensorOpCost cost = m_impl.costPerCoeff(vectorized);
191     if (static_cast<int>(Layout) == static_cast<int>(ColMajor)) {
192       for (int i = 0; i < NumDims; ++i)
193         updateCostPerDimension(cost, i, i == 0);
194     } else {
195       for (int i = NumDims - 1; i >= 0; --i)
196         updateCostPerDimension(cost, i, i == NumDims - 1);
197     }
198     return cost;
199   }
200 
201   EIGEN_DEVICE_FUNC Scalar* data() const { return NULL; }
202 
203  private:
204   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool isPaddingAtIndexForDim(
205       Index index, int dim_index) const {
206 #if defined(EIGEN_HAS_INDEX_LIST)
207     return (!internal::index_pair_first_statically_eq<PaddingDimensions>(dim_index, 0) &&
208             index < m_padding[dim_index].first) ||
209         (!internal::index_pair_second_statically_eq<PaddingDimensions>(dim_index, 0) &&
210          index >= m_dimensions[dim_index] - m_padding[dim_index].second);
211 #else
212     return (index < m_padding[dim_index].first) ||
213            (index >= m_dimensions[dim_index] - m_padding[dim_index].second);
214 #endif
215   }
216 
217   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool isLeftPaddingCompileTimeZero(
218       int dim_index) const {
219 #if defined(EIGEN_HAS_INDEX_LIST)
220     return internal::index_pair_first_statically_eq<PaddingDimensions>(dim_index, 0);
221 #else
222     EIGEN_UNUSED_VARIABLE(dim_index);
223     return false;
224 #endif
225   }
226 
227   EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE bool isRightPaddingCompileTimeZero(
228       int dim_index) const {
229 #if defined(EIGEN_HAS_INDEX_LIST)
230     return internal::index_pair_second_statically_eq<PaddingDimensions>(dim_index, 0);
231 #else
232     EIGEN_UNUSED_VARIABLE(dim_index);
233     return false;
234 #endif
235   }
236 
237 
238   void updateCostPerDimension(TensorOpCost& cost, int i, bool first) const {
239     const double in = static_cast<double>(m_impl.dimensions()[i]);
240     const double out = in + m_padding[i].first + m_padding[i].second;
241     if (out == 0)
242       return;
243     const double reduction = in / out;
244     cost *= reduction;
245     if (first) {
246       cost += TensorOpCost(0, 0, 2 * TensorOpCost::AddCost<Index>() +
247                     reduction * (1 * TensorOpCost::AddCost<Index>()));
248     } else {
249       cost += TensorOpCost(0, 0, 2 * TensorOpCost::AddCost<Index>() +
250                                  2 * TensorOpCost::MulCost<Index>() +
251                     reduction * (2 * TensorOpCost::MulCost<Index>() +
252                                  1 * TensorOpCost::DivCost<Index>()));
253     }
254   }
255 
256  protected:
257 
258   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE PacketReturnType packetColMajor(Index index) const
259   {
260     EIGEN_STATIC_ASSERT((PacketSize > 1), YOU_MADE_A_PROGRAMMING_MISTAKE)
261     eigen_assert(index+PacketSize-1 < dimensions().TotalSize());
262 
263     const Index initialIndex = index;
264     Index inputIndex = 0;
265     for (int i = NumDims - 1; i > 0; --i) {
266       const Index first = index;
267       const Index last = index + PacketSize - 1;
268       const Index lastPaddedLeft = m_padding[i].first * m_outputStrides[i];
269       const Index firstPaddedRight = (m_dimensions[i] - m_padding[i].second) * m_outputStrides[i];
270       const Index lastPaddedRight = m_outputStrides[i+1];
271 
272       if (!isLeftPaddingCompileTimeZero(i) && last < lastPaddedLeft) {
273         // all the coefficient are in the padding zone.
274         return internal::pset1<PacketReturnType>(m_paddingValue);
275       }
276       else if (!isRightPaddingCompileTimeZero(i) && first >= firstPaddedRight && last < lastPaddedRight) {
277         // all the coefficient are in the padding zone.
278         return internal::pset1<PacketReturnType>(m_paddingValue);
279       }
280       else if ((isLeftPaddingCompileTimeZero(i) && isRightPaddingCompileTimeZero(i)) || (first >= lastPaddedLeft && last < firstPaddedRight)) {
281         // all the coefficient are between the 2 padding zones.
282         const Index idx = index / m_outputStrides[i];
283         inputIndex += (idx - m_padding[i].first) * m_inputStrides[i];
284         index -= idx * m_outputStrides[i];
285       }
286       else {
287         // Every other case
288         return packetWithPossibleZero(initialIndex);
289       }
290     }
291 
292     const Index last = index + PacketSize - 1;
293     const Index first = index;
294     const Index lastPaddedLeft = m_padding[0].first;
295     const Index firstPaddedRight = (m_dimensions[0] - m_padding[0].second);
296     const Index lastPaddedRight = m_outputStrides[1];
297 
298     if (!isLeftPaddingCompileTimeZero(0) && last < lastPaddedLeft) {
299       // all the coefficient are in the padding zone.
300       return internal::pset1<PacketReturnType>(m_paddingValue);
301     }
302     else if (!isRightPaddingCompileTimeZero(0) && first >= firstPaddedRight && last < lastPaddedRight) {
303       // all the coefficient are in the padding zone.
304       return internal::pset1<PacketReturnType>(m_paddingValue);
305     }
306     else if ((isLeftPaddingCompileTimeZero(0) && isRightPaddingCompileTimeZero(0)) || (first >= lastPaddedLeft && last < firstPaddedRight)) {
307       // all the coefficient are between the 2 padding zones.
308       inputIndex += (index - m_padding[0].first);
309       return m_impl.template packet<Unaligned>(inputIndex);
310     }
311     // Every other case
312     return packetWithPossibleZero(initialIndex);
313   }
314 
315   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE PacketReturnType packetRowMajor(Index index) const
316   {
317     EIGEN_STATIC_ASSERT((PacketSize > 1), YOU_MADE_A_PROGRAMMING_MISTAKE)
318     eigen_assert(index+PacketSize-1 < dimensions().TotalSize());
319 
320     const Index initialIndex = index;
321     Index inputIndex = 0;
322 
323     for (int i = 0; i < NumDims - 1; ++i) {
324       const Index first = index;
325       const Index last = index + PacketSize - 1;
326       const Index lastPaddedLeft = m_padding[i].first * m_outputStrides[i+1];
327       const Index firstPaddedRight = (m_dimensions[i] - m_padding[i].second) * m_outputStrides[i+1];
328       const Index lastPaddedRight = m_outputStrides[i];
329 
330       if (!isLeftPaddingCompileTimeZero(i) && last < lastPaddedLeft) {
331         // all the coefficient are in the padding zone.
332         return internal::pset1<PacketReturnType>(m_paddingValue);
333       }
334       else if (!isRightPaddingCompileTimeZero(i) && first >= firstPaddedRight && last < lastPaddedRight) {
335         // all the coefficient are in the padding zone.
336         return internal::pset1<PacketReturnType>(m_paddingValue);
337       }
338       else if ((isLeftPaddingCompileTimeZero(i) && isRightPaddingCompileTimeZero(i)) || (first >= lastPaddedLeft && last < firstPaddedRight)) {
339         // all the coefficient are between the 2 padding zones.
340         const Index idx = index / m_outputStrides[i+1];
341         inputIndex += (idx - m_padding[i].first) * m_inputStrides[i];
342         index -= idx * m_outputStrides[i+1];
343       }
344       else {
345         // Every other case
346         return packetWithPossibleZero(initialIndex);
347       }
348     }
349 
350     const Index last = index + PacketSize - 1;
351     const Index first = index;
352     const Index lastPaddedLeft = m_padding[NumDims-1].first;
353     const Index firstPaddedRight = (m_dimensions[NumDims-1] - m_padding[NumDims-1].second);
354     const Index lastPaddedRight = m_outputStrides[NumDims-1];
355 
356     if (!isLeftPaddingCompileTimeZero(NumDims-1) && last < lastPaddedLeft) {
357       // all the coefficient are in the padding zone.
358       return internal::pset1<PacketReturnType>(m_paddingValue);
359     }
360     else if (!isRightPaddingCompileTimeZero(NumDims-1) && first >= firstPaddedRight && last < lastPaddedRight) {
361       // all the coefficient are in the padding zone.
362       return internal::pset1<PacketReturnType>(m_paddingValue);
363     }
364     else if ((isLeftPaddingCompileTimeZero(NumDims-1) && isRightPaddingCompileTimeZero(NumDims-1)) || (first >= lastPaddedLeft && last < firstPaddedRight)) {
365       // all the coefficient are between the 2 padding zones.
366       inputIndex += (index - m_padding[NumDims-1].first);
367       return m_impl.template packet<Unaligned>(inputIndex);
368     }
369     // Every other case
370     return packetWithPossibleZero(initialIndex);
371   }
372 
373   EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE PacketReturnType packetWithPossibleZero(Index index) const
374   {
375     EIGEN_ALIGN_MAX typename internal::remove_const<CoeffReturnType>::type values[PacketSize];
376     for (int i = 0; i < PacketSize; ++i) {
377       values[i] = coeff(index+i);
378     }
379     PacketReturnType rslt = internal::pload<PacketReturnType>(values);
380     return rslt;
381   }
382 
383   Dimensions m_dimensions;
384   array<Index, NumDims+1> m_outputStrides;
385   array<Index, NumDims> m_inputStrides;
386   TensorEvaluator<ArgType, Device> m_impl;
387   PaddingDimensions m_padding;
388 
389   Scalar m_paddingValue;
390 };
391 
392 
393 
394 
395 } // end namespace Eigen
396 
397 #endif // EIGEN_CXX11_TENSOR_TENSOR_PADDING_H
398