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