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