1 /*
2  * Copyright (C) 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 package com.android.inputmethod.keyboard.internal;
18 
19 import com.android.inputmethod.annotations.UsedForTesting;
20 
21 import android.util.Log;
22 
23 import java.util.Arrays;
24 
25 /**
26  * Utilities for matrix operations. Don't instantiate objects inside this class to prevent
27  * unexpected performance regressions.
28  */
29 @UsedForTesting
30 public class MatrixUtils {
31     static final String TAG = MatrixUtils.class.getSimpleName();
32 
33     public static class MatrixOperationFailedException extends Exception {
34         private static final long serialVersionUID = 4384485606788583829L;
35 
MatrixOperationFailedException(String msg)36         public MatrixOperationFailedException(String msg) {
37             super(msg);
38             Log.d(TAG, msg);
39         }
40     }
41 
42     /**
43      * A utility function to inverse matrix.
44      * Find a pivot and swap the row of squareMatrix0 and squareMatrix1
45      */
findPivotAndSwapRow(final int row, final float[][] squareMatrix0, final float[][] squareMatrix1, final int size)46     private static void findPivotAndSwapRow(final int row, final float[][] squareMatrix0,
47             final float[][] squareMatrix1, final int size) {
48         int ip = row;
49         float pivot = Math.abs(squareMatrix0[row][row]);
50         for (int i = row + 1; i < size; ++i) {
51             if (pivot < Math.abs(squareMatrix0[i][row])) {
52                 ip = i;
53                 pivot = Math.abs(squareMatrix0[i][row]);
54             }
55         }
56         if (ip != row) {
57             for (int j = 0; j < size; ++j) {
58                 final float temp0 = squareMatrix0[ip][j];
59                 squareMatrix0[ip][j] = squareMatrix0[row][j];
60                 squareMatrix0[row][j] = temp0;
61                 final float temp1 = squareMatrix1[ip][j];
62                 squareMatrix1[ip][j] = squareMatrix1[row][j];
63                 squareMatrix1[row][j] = temp1;
64             }
65         }
66     }
67 
68     /**
69      * A utility function to inverse matrix. This function calculates answer for each row by
70      * sweeping method of Gauss Jordan elimination
71      */
sweep(final int row, final float[][] squareMatrix0, final float[][] squareMatrix1, final int size)72     private static void sweep(final int row, final float[][] squareMatrix0,
73             final float[][] squareMatrix1, final int size) throws MatrixOperationFailedException {
74         final float pivot = squareMatrix0[row][row];
75         if (pivot == 0) {
76             throw new MatrixOperationFailedException("Inverse failed. Invalid pivot");
77         }
78         for (int j = 0; j < size; ++j) {
79             squareMatrix0[row][j] /= pivot;
80             squareMatrix1[row][j] /= pivot;
81         }
82         for (int i = 0; i < size; i++) {
83             final float sweepTargetValue = squareMatrix0[i][row];
84             if (i != row) {
85                 for (int j = row; j < size; ++j) {
86                     squareMatrix0[i][j] -= sweepTargetValue * squareMatrix0[row][j];
87                 }
88                 for (int j = 0; j < size; ++j) {
89                     squareMatrix1[i][j] -= sweepTargetValue * squareMatrix1[row][j];
90                 }
91             }
92         }
93     }
94 
95     /**
96      * A function to inverse matrix.
97      * The inverse matrix of squareMatrix will be output to inverseMatrix. Please notice that
98      * the value of squareMatrix is modified in this function and can't be resuable.
99      */
100     @UsedForTesting
inverse(final float[][] squareMatrix, final float[][] inverseMatrix)101     public static void inverse(final float[][] squareMatrix,
102             final float[][] inverseMatrix) throws MatrixOperationFailedException {
103         final int size = squareMatrix.length;
104         if (squareMatrix[0].length != size || inverseMatrix.length != size
105                 || inverseMatrix[0].length != size) {
106             throw new MatrixOperationFailedException(
107                     "--- invalid length. column should be 2 times larger than row.");
108         }
109         for (int i = 0; i < size; ++i) {
110             Arrays.fill(inverseMatrix[i], 0.0f);
111             inverseMatrix[i][i] = 1.0f;
112         }
113         for (int i = 0; i < size; ++i) {
114             findPivotAndSwapRow(i, squareMatrix, inverseMatrix, size);
115             sweep(i, squareMatrix, inverseMatrix, size);
116         }
117     }
118 
119     /**
120      * A matrix operation to multiply m0 and m1.
121      */
122     @UsedForTesting
multiply(final float[][] m0, final float[][] m1, final float[][] retval)123     public static void multiply(final float[][] m0, final float[][] m1,
124             final float[][] retval) throws MatrixOperationFailedException {
125         if (m0[0].length != m1.length) {
126             throw new MatrixOperationFailedException(
127                     "--- invalid length for multiply " + m0[0].length + ", " + m1.length);
128         }
129         final int m0h = m0.length;
130         final int m0w = m0[0].length;
131         final int m1w = m1[0].length;
132         if (retval.length != m0h || retval[0].length != m1w) {
133             throw new MatrixOperationFailedException(
134                     "--- invalid length of retval " + retval.length + ", " + retval[0].length);
135         }
136 
137         for (int i = 0; i < m0h; i++) {
138             Arrays.fill(retval[i], 0);
139             for (int j = 0; j < m1w; j++) {
140                 for (int k = 0; k < m0w; k++) {
141                     retval[i][j] += m0[i][k] * m1[k][j];
142                 }
143             }
144         }
145     }
146 
147     /**
148      * A utility function to dump the specified matrix in a readable way
149      */
150     @UsedForTesting
dump(final String title, final float[][] a)151     public static void dump(final String title, final float[][] a) {
152         final int column = a[0].length;
153         final int row = a.length;
154         Log.d(TAG, "Dump matrix: " + title);
155         Log.d(TAG, "/*---------------------");
156         final StringBuilder sb = new StringBuilder();
157         for (int i = 0; i < row; ++i) {
158             sb.setLength(0);
159             for (int j = 0; j < column; ++j) {
160                 sb.append(String.format("%4f", a[i][j])).append(' ');
161             }
162             Log.d(TAG, sb.toString());
163         }
164         Log.d(TAG, "---------------------*/");
165     }
166 }
167