1/*
2 * Copyright 2013 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef TMAT_IMPLEMENTATION
18#error "Don't include TMatHelpers.h directly. use ui/mat*.h instead"
19#else
20#undef TMAT_IMPLEMENTATION
21#endif
22
23
24#ifndef UI_TMAT_HELPERS_H
25#define UI_TMAT_HELPERS_H
26
27#include <stdint.h>
28#include <sys/types.h>
29#include <math.h>
30#include <utils/Debug.h>
31#include <utils/String8.h>
32
33#define PURE __attribute__((pure))
34
35namespace android {
36// -------------------------------------------------------------------------------------
37
38/*
39 * No user serviceable parts here.
40 *
41 * Don't use this file directly, instead include ui/mat*.h
42 */
43
44
45/*
46 * Matrix utilities
47 */
48
49namespace matrix {
50
51inline int     PURE transpose(int v)    { return v; }
52inline float   PURE transpose(float v)  { return v; }
53inline double  PURE transpose(double v) { return v; }
54
55inline int     PURE trace(int v)    { return v; }
56inline float   PURE trace(float v)  { return v; }
57inline double  PURE trace(double v) { return v; }
58
59template<typename MATRIX>
60MATRIX PURE inverse(const MATRIX& src) {
61
62    COMPILE_TIME_ASSERT_FUNCTION_SCOPE( MATRIX::COL_SIZE == MATRIX::ROW_SIZE );
63
64    typename MATRIX::value_type t;
65    const size_t N = MATRIX::col_size();
66    size_t swap;
67    MATRIX tmp(src);
68    MATRIX inverse(1);
69
70    for (size_t i=0 ; i<N ; i++) {
71        // look for largest element in column
72        swap = i;
73        for (size_t j=i+1 ; j<N ; j++) {
74            if (fabs(tmp[j][i]) > fabs(tmp[i][i])) {
75                swap = j;
76            }
77        }
78
79        if (swap != i) {
80            /* swap rows. */
81            for (size_t k=0 ; k<N ; k++) {
82                t = tmp[i][k];
83                tmp[i][k] = tmp[swap][k];
84                tmp[swap][k] = t;
85
86                t = inverse[i][k];
87                inverse[i][k] = inverse[swap][k];
88                inverse[swap][k] = t;
89            }
90        }
91
92        t = 1 / tmp[i][i];
93        for (size_t k=0 ; k<N ; k++) {
94            tmp[i][k] *= t;
95            inverse[i][k] *= t;
96        }
97        for (size_t j=0 ; j<N ; j++) {
98            if (j != i) {
99                t = tmp[j][i];
100                for (size_t k=0 ; k<N ; k++) {
101                    tmp[j][k] -= tmp[i][k] * t;
102                    inverse[j][k] -= inverse[i][k] * t;
103                }
104            }
105        }
106    }
107    return inverse;
108}
109
110template<typename MATRIX_R, typename MATRIX_A, typename MATRIX_B>
111MATRIX_R PURE multiply(const MATRIX_A& lhs, const MATRIX_B& rhs) {
112    // pre-requisite:
113    //  lhs : D columns, R rows
114    //  rhs : C columns, D rows
115    //  res : C columns, R rows
116
117    COMPILE_TIME_ASSERT_FUNCTION_SCOPE( MATRIX_A::ROW_SIZE == MATRIX_B::COL_SIZE );
118    COMPILE_TIME_ASSERT_FUNCTION_SCOPE( MATRIX_R::ROW_SIZE == MATRIX_B::ROW_SIZE );
119    COMPILE_TIME_ASSERT_FUNCTION_SCOPE( MATRIX_R::COL_SIZE == MATRIX_A::COL_SIZE );
120
121    MATRIX_R res(MATRIX_R::NO_INIT);
122    for (size_t r=0 ; r<MATRIX_R::row_size() ; r++) {
123        res[r] = lhs * rhs[r];
124    }
125    return res;
126}
127
128// transpose. this handles matrices of matrices
129template <typename MATRIX>
130MATRIX PURE transpose(const MATRIX& m) {
131    // for now we only handle square matrix transpose
132    COMPILE_TIME_ASSERT_FUNCTION_SCOPE( MATRIX::ROW_SIZE == MATRIX::COL_SIZE );
133    MATRIX result(MATRIX::NO_INIT);
134    for (size_t r=0 ; r<MATRIX::row_size() ; r++)
135        for (size_t c=0 ; c<MATRIX::col_size() ; c++)
136            result[c][r] = transpose(m[r][c]);
137    return result;
138}
139
140// trace. this handles matrices of matrices
141template <typename MATRIX>
142typename MATRIX::value_type PURE trace(const MATRIX& m) {
143    COMPILE_TIME_ASSERT_FUNCTION_SCOPE( MATRIX::ROW_SIZE == MATRIX::COL_SIZE );
144    typename MATRIX::value_type result(0);
145    for (size_t r=0 ; r<MATRIX::row_size() ; r++)
146        result += trace(m[r][r]);
147    return result;
148}
149
150// trace. this handles matrices of matrices
151template <typename MATRIX>
152typename MATRIX::col_type PURE diag(const MATRIX& m) {
153    COMPILE_TIME_ASSERT_FUNCTION_SCOPE( MATRIX::ROW_SIZE == MATRIX::COL_SIZE );
154    typename MATRIX::col_type result(MATRIX::col_type::NO_INIT);
155    for (size_t r=0 ; r<MATRIX::row_size() ; r++)
156        result[r] = m[r][r];
157    return result;
158}
159
160template <typename MATRIX>
161String8 asString(const MATRIX& m) {
162    String8 s;
163    for (size_t c=0 ; c<MATRIX::col_size() ; c++) {
164        s.append("|  ");
165        for (size_t r=0 ; r<MATRIX::row_size() ; r++) {
166            s.appendFormat("%7.2f  ", m[r][c]);
167        }
168        s.append("|\n");
169    }
170    return s;
171}
172
173}; // namespace matrix
174
175// -------------------------------------------------------------------------------------
176
177/*
178 * TMatProductOperators implements basic arithmetic and basic compound assignments
179 * operators on a vector of type BASE<T>.
180 *
181 * BASE only needs to implement operator[] and size().
182 * By simply inheriting from TMatProductOperators<BASE, T> BASE will automatically
183 * get all the functionality here.
184 */
185
186template <template<typename T> class BASE, typename T>
187class TMatProductOperators {
188public:
189    // multiply by a scalar
190    BASE<T>& operator *= (T v) {
191        BASE<T>& lhs(static_cast< BASE<T>& >(*this));
192        for (size_t r=0 ; r<lhs.row_size() ; r++) {
193            lhs[r] *= v;
194        }
195        return lhs;
196    }
197
198    // divide by a scalar
199    BASE<T>& operator /= (T v) {
200        BASE<T>& lhs(static_cast< BASE<T>& >(*this));
201        for (size_t r=0 ; r<lhs.row_size() ; r++) {
202            lhs[r] /= v;
203        }
204        return lhs;
205    }
206
207    // matrix * matrix, result is a matrix of the same type than the lhs matrix
208    template<typename U>
209    friend BASE<T> PURE operator *(const BASE<T>& lhs, const BASE<U>& rhs) {
210        return matrix::multiply<BASE<T> >(lhs, rhs);
211    }
212};
213
214
215/*
216 * TMatSquareFunctions implements functions on a matrix of type BASE<T>.
217 *
218 * BASE only needs to implement:
219 *  - operator[]
220 *  - col_type
221 *  - row_type
222 *  - COL_SIZE
223 *  - ROW_SIZE
224 *
225 * By simply inheriting from TMatSquareFunctions<BASE, T> BASE will automatically
226 * get all the functionality here.
227 */
228
229template<template<typename U> class BASE, typename T>
230class TMatSquareFunctions {
231public:
232    /*
233     * NOTE: the functions below ARE NOT member methods. They are friend functions
234     * with they definition inlined with their declaration. This makes these
235     * template functions available to the compiler when (and only when) this class
236     * is instantiated, at which point they're only templated on the 2nd parameter
237     * (the first one, BASE<T> being known).
238     */
239    friend BASE<T> PURE inverse(const BASE<T>& m)   { return matrix::inverse(m); }
240    friend BASE<T> PURE transpose(const BASE<T>& m) { return matrix::transpose(m); }
241    friend T       PURE trace(const BASE<T>& m)     { return matrix::trace(m); }
242};
243
244template <template<typename T> class BASE, typename T>
245class TMatDebug {
246public:
247    String8 asString() const {
248        return matrix::asString( static_cast< const BASE<T>& >(*this) );
249    }
250};
251
252// -------------------------------------------------------------------------------------
253}; // namespace android
254
255#undef PURE
256
257#endif /* UI_TMAT_HELPERS_H */
258