1 /* 2 * Copyright (C) 2011 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 #include <assert.h> 18 #include <stdio.h> 19 #include <string> 20 21 #define LOG_TAG "LatinIME: proximity_info.cpp" 22 23 #include "additional_proximity_chars.h" 24 #include "defines.h" 25 #include "dictionary.h" 26 #include "proximity_info.h" 27 28 namespace latinime { 29 30 inline void copyOrFillZero(void *to, const void *from, size_t size) { 31 if (from) { 32 memcpy(to, from, size); 33 } else { 34 memset(to, 0, size); 35 } 36 } 37 38 ProximityInfo::ProximityInfo(const std::string localeStr, const int maxProximityCharsSize, 39 const int keyboardWidth, const int keyboardHeight, const int gridWidth, 40 const int gridHeight, const int mostCommonKeyWidth, 41 const int32_t *proximityCharsArray, const int keyCount, const int32_t *keyXCoordinates, 42 const int32_t *keyYCoordinates, const int32_t *keyWidths, const int32_t *keyHeights, 43 const int32_t *keyCharCodes, const float *sweetSpotCenterXs, const float *sweetSpotCenterYs, 44 const float *sweetSpotRadii) 45 : MAX_PROXIMITY_CHARS_SIZE(maxProximityCharsSize), KEYBOARD_WIDTH(keyboardWidth), 46 KEYBOARD_HEIGHT(keyboardHeight), GRID_WIDTH(gridWidth), GRID_HEIGHT(gridHeight), 47 MOST_COMMON_KEY_WIDTH_SQUARE(mostCommonKeyWidth * mostCommonKeyWidth), 48 CELL_WIDTH((keyboardWidth + gridWidth - 1) / gridWidth), 49 CELL_HEIGHT((keyboardHeight + gridHeight - 1) / gridHeight), 50 KEY_COUNT(min(keyCount, MAX_KEY_COUNT_IN_A_KEYBOARD)), 51 HAS_TOUCH_POSITION_CORRECTION_DATA(keyCount > 0 && keyXCoordinates && keyYCoordinates 52 && keyWidths && keyHeights && keyCharCodes && sweetSpotCenterXs 53 && sweetSpotCenterYs && sweetSpotRadii), 54 mLocaleStr(localeStr), 55 mInputXCoordinates(0), mInputYCoordinates(0), 56 mTouchPositionCorrectionEnabled(false) { 57 const int proximityGridLength = GRID_WIDTH * GRID_HEIGHT * MAX_PROXIMITY_CHARS_SIZE; 58 mProximityCharsArray = new int32_t[proximityGridLength]; 59 mInputCodes = new int32_t[MAX_PROXIMITY_CHARS_SIZE * MAX_WORD_LENGTH_INTERNAL]; 60 if (DEBUG_PROXIMITY_INFO) { 61 AKLOGI("Create proximity info array %d", proximityGridLength); 62 } 63 memcpy(mProximityCharsArray, proximityCharsArray, 64 proximityGridLength * sizeof(mProximityCharsArray[0])); 65 const int normalizedSquaredDistancesLength = 66 MAX_PROXIMITY_CHARS_SIZE * MAX_WORD_LENGTH_INTERNAL; 67 mNormalizedSquaredDistances = new int[normalizedSquaredDistancesLength]; 68 for (int i = 0; i < normalizedSquaredDistancesLength; ++i) { 69 mNormalizedSquaredDistances[i] = NOT_A_DISTANCE; 70 } 71 72 copyOrFillZero(mKeyXCoordinates, keyXCoordinates, KEY_COUNT * sizeof(mKeyXCoordinates[0])); 73 copyOrFillZero(mKeyYCoordinates, keyYCoordinates, KEY_COUNT * sizeof(mKeyYCoordinates[0])); 74 copyOrFillZero(mKeyWidths, keyWidths, KEY_COUNT * sizeof(mKeyWidths[0])); 75 copyOrFillZero(mKeyHeights, keyHeights, KEY_COUNT * sizeof(mKeyHeights[0])); 76 copyOrFillZero(mKeyCharCodes, keyCharCodes, KEY_COUNT * sizeof(mKeyCharCodes[0])); 77 copyOrFillZero(mSweetSpotCenterXs, sweetSpotCenterXs, 78 KEY_COUNT * sizeof(mSweetSpotCenterXs[0])); 79 copyOrFillZero(mSweetSpotCenterYs, sweetSpotCenterYs, 80 KEY_COUNT * sizeof(mSweetSpotCenterYs[0])); 81 copyOrFillZero(mSweetSpotRadii, sweetSpotRadii, KEY_COUNT * sizeof(mSweetSpotRadii[0])); 82 83 initializeCodeToKeyIndex(); 84 } 85 86 // Build the reversed look up table from the char code to the index in mKeyXCoordinates, 87 // mKeyYCoordinates, mKeyWidths, mKeyHeights, mKeyCharCodes. 88 void ProximityInfo::initializeCodeToKeyIndex() { 89 memset(mCodeToKeyIndex, -1, (MAX_CHAR_CODE + 1) * sizeof(mCodeToKeyIndex[0])); 90 for (int i = 0; i < KEY_COUNT; ++i) { 91 const int code = mKeyCharCodes[i]; 92 if (0 <= code && code <= MAX_CHAR_CODE) { 93 mCodeToKeyIndex[code] = i; 94 } 95 } 96 } 97 98 ProximityInfo::~ProximityInfo() { 99 delete[] mNormalizedSquaredDistances; 100 delete[] mProximityCharsArray; 101 delete[] mInputCodes; 102 } 103 104 inline int ProximityInfo::getStartIndexFromCoordinates(const int x, const int y) const { 105 return ((y / CELL_HEIGHT) * GRID_WIDTH + (x / CELL_WIDTH)) 106 * MAX_PROXIMITY_CHARS_SIZE; 107 } 108 109 bool ProximityInfo::hasSpaceProximity(const int x, const int y) const { 110 if (x < 0 || y < 0) { 111 if (DEBUG_DICT) { 112 AKLOGI("HasSpaceProximity: Illegal coordinates (%d, %d)", x, y); 113 assert(false); 114 } 115 return false; 116 } 117 118 const int startIndex = getStartIndexFromCoordinates(x, y); 119 if (DEBUG_PROXIMITY_INFO) { 120 AKLOGI("hasSpaceProximity: index %d, %d, %d", startIndex, x, y); 121 } 122 for (int i = 0; i < MAX_PROXIMITY_CHARS_SIZE; ++i) { 123 if (DEBUG_PROXIMITY_INFO) { 124 AKLOGI("Index: %d", mProximityCharsArray[startIndex + i]); 125 } 126 if (mProximityCharsArray[startIndex + i] == KEYCODE_SPACE) { 127 return true; 128 } 129 } 130 return false; 131 } 132 133 bool ProximityInfo::isOnKey(const int keyId, const int x, const int y) const { 134 if (keyId < 0) return true; // NOT_A_ID is -1, but return whenever < 0 just in case 135 const int left = mKeyXCoordinates[keyId]; 136 const int top = mKeyYCoordinates[keyId]; 137 const int right = left + mKeyWidths[keyId] + 1; 138 const int bottom = top + mKeyHeights[keyId]; 139 return left < right && top < bottom && x >= left && x < right && y >= top && y < bottom; 140 } 141 142 int ProximityInfo::squaredDistanceToEdge(const int keyId, const int x, const int y) const { 143 if (keyId < 0) return true; // NOT_A_ID is -1, but return whenever < 0 just in case 144 const int left = mKeyXCoordinates[keyId]; 145 const int top = mKeyYCoordinates[keyId]; 146 const int right = left + mKeyWidths[keyId]; 147 const int bottom = top + mKeyHeights[keyId]; 148 const int edgeX = x < left ? left : (x > right ? right : x); 149 const int edgeY = y < top ? top : (y > bottom ? bottom : y); 150 const int dx = x - edgeX; 151 const int dy = y - edgeY; 152 return dx * dx + dy * dy; 153 } 154 155 void ProximityInfo::calculateNearbyKeyCodes( 156 const int x, const int y, const int32_t primaryKey, int *inputCodes) const { 157 int insertPos = 0; 158 inputCodes[insertPos++] = primaryKey; 159 const int startIndex = getStartIndexFromCoordinates(x, y); 160 if (startIndex >= 0) { 161 for (int i = 0; i < MAX_PROXIMITY_CHARS_SIZE; ++i) { 162 const int32_t c = mProximityCharsArray[startIndex + i]; 163 if (c < KEYCODE_SPACE || c == primaryKey) { 164 continue; 165 } 166 const int keyIndex = getKeyIndex(c); 167 const bool onKey = isOnKey(keyIndex, x, y); 168 const int distance = squaredDistanceToEdge(keyIndex, x, y); 169 if (onKey || distance < MOST_COMMON_KEY_WIDTH_SQUARE) { 170 inputCodes[insertPos++] = c; 171 if (insertPos >= MAX_PROXIMITY_CHARS_SIZE) { 172 if (DEBUG_DICT) { 173 assert(false); 174 } 175 return; 176 } 177 } 178 } 179 const int additionalProximitySize = 180 AdditionalProximityChars::getAdditionalCharsSize(&mLocaleStr, primaryKey); 181 if (additionalProximitySize > 0) { 182 inputCodes[insertPos++] = ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE; 183 if (insertPos >= MAX_PROXIMITY_CHARS_SIZE) { 184 if (DEBUG_DICT) { 185 assert(false); 186 } 187 return; 188 } 189 190 const int32_t* additionalProximityChars = 191 AdditionalProximityChars::getAdditionalChars(&mLocaleStr, primaryKey); 192 for (int j = 0; j < additionalProximitySize; ++j) { 193 const int32_t ac = additionalProximityChars[j]; 194 int k = 0; 195 for (; k < insertPos; ++k) { 196 if ((int)ac == inputCodes[k]) { 197 break; 198 } 199 } 200 if (k < insertPos) { 201 continue; 202 } 203 inputCodes[insertPos++] = ac; 204 if (insertPos >= MAX_PROXIMITY_CHARS_SIZE) { 205 if (DEBUG_DICT) { 206 assert(false); 207 } 208 return; 209 } 210 } 211 } 212 } 213 // Add a delimiter for the proximity characters 214 for (int i = insertPos; i < MAX_PROXIMITY_CHARS_SIZE; ++i) { 215 inputCodes[i] = NOT_A_CODE; 216 } 217 } 218 219 void ProximityInfo::setInputParams(const int32_t* inputCodes, const int inputLength, 220 const int* xCoordinates, const int* yCoordinates) { 221 memset(mInputCodes, 0, 222 MAX_WORD_LENGTH_INTERNAL * MAX_PROXIMITY_CHARS_SIZE * sizeof(mInputCodes[0])); 223 224 for (int i = 0; i < inputLength; ++i) { 225 const int32_t primaryKey = inputCodes[i]; 226 const int x = xCoordinates[i]; 227 const int y = yCoordinates[i]; 228 int *proximities = &mInputCodes[i * MAX_PROXIMITY_CHARS_SIZE]; 229 calculateNearbyKeyCodes(x, y, primaryKey, proximities); 230 } 231 232 if (DEBUG_PROXIMITY_CHARS) { 233 for (int i = 0; i < inputLength; ++i) { 234 AKLOGI("---"); 235 for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE; ++j) { 236 int icc = mInputCodes[i * MAX_PROXIMITY_CHARS_SIZE + j]; 237 int icfjc = inputCodes[i * MAX_PROXIMITY_CHARS_SIZE + j]; 238 icc+= 0; 239 icfjc += 0; 240 AKLOGI("--- (%d)%c,%c", i, icc, icfjc); 241 AKLOGI("--- A<%d>,B<%d>", icc, icfjc); 242 } 243 } 244 } 245 //Keep for debug, sorry 246 //for (int i = 0; i < MAX_WORD_LENGTH_INTERNAL * MAX_PROXIMITY_CHARS_SIZE; ++i) { 247 //if (i < inputLength * MAX_PROXIMITY_CHARS_SIZE) { 248 //mInputCodes[i] = mInputCodesFromJava[i]; 249 //} else { 250 // mInputCodes[i] = 0; 251 // } 252 //} 253 mInputXCoordinates = xCoordinates; 254 mInputYCoordinates = yCoordinates; 255 mTouchPositionCorrectionEnabled = 256 HAS_TOUCH_POSITION_CORRECTION_DATA && xCoordinates && yCoordinates; 257 mInputLength = inputLength; 258 for (int i = 0; i < inputLength; ++i) { 259 mPrimaryInputWord[i] = getPrimaryCharAt(i); 260 } 261 mPrimaryInputWord[inputLength] = 0; 262 if (DEBUG_PROXIMITY_CHARS) { 263 AKLOGI("--- setInputParams"); 264 } 265 for (int i = 0; i < mInputLength; ++i) { 266 const int *proximityChars = getProximityCharsAt(i); 267 const int primaryKey = proximityChars[0]; 268 const int x = xCoordinates[i]; 269 const int y = yCoordinates[i]; 270 if (DEBUG_PROXIMITY_CHARS) { 271 int a = x + y + primaryKey; 272 a += 0; 273 AKLOGI("--- Primary = %c, x = %d, y = %d", primaryKey, x, y); 274 // Keep debug code just in case 275 //int proximities[50]; 276 //for (int m = 0; m < 50; ++m) { 277 //proximities[m] = 0; 278 //} 279 //calculateNearbyKeyCodes(x, y, primaryKey, proximities); 280 //for (int l = 0; l < 50 && proximities[l] > 0; ++l) { 281 //if (DEBUG_PROXIMITY_CHARS) { 282 //AKLOGI("--- native Proximity (%d) = %c", l, proximities[l]); 283 //} 284 //} 285 } 286 for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE && proximityChars[j] > 0; ++j) { 287 const int currentChar = proximityChars[j]; 288 const float squaredDistance = hasInputCoordinates() 289 ? calculateNormalizedSquaredDistance(getKeyIndex(currentChar), i) 290 : NOT_A_DISTANCE_FLOAT; 291 if (squaredDistance >= 0.0f) { 292 mNormalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] = 293 (int)(squaredDistance * NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR); 294 } else { 295 mNormalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE + j] = (j == 0) 296 ? EQUIVALENT_CHAR_WITHOUT_DISTANCE_INFO 297 : PROXIMITY_CHAR_WITHOUT_DISTANCE_INFO; 298 } 299 if (DEBUG_PROXIMITY_CHARS) { 300 AKLOGI("--- Proximity (%d) = %c", j, currentChar); 301 } 302 } 303 } 304 } 305 306 inline float square(const float x) { return x * x; } 307 308 float ProximityInfo::calculateNormalizedSquaredDistance( 309 const int keyIndex, const int inputIndex) const { 310 if (keyIndex == NOT_AN_INDEX) { 311 return NOT_A_DISTANCE_FLOAT; 312 } 313 if (!hasSweetSpotData(keyIndex)) { 314 return NOT_A_DISTANCE_FLOAT; 315 } 316 if (NOT_A_COORDINATE == mInputXCoordinates[inputIndex]) { 317 return NOT_A_DISTANCE_FLOAT; 318 } 319 const float squaredDistance = calculateSquaredDistanceFromSweetSpotCenter(keyIndex, inputIndex); 320 const float squaredRadius = square(mSweetSpotRadii[keyIndex]); 321 return squaredDistance / squaredRadius; 322 } 323 324 bool ProximityInfo::hasInputCoordinates() const { 325 return mInputXCoordinates && mInputYCoordinates; 326 } 327 328 int ProximityInfo::getKeyIndex(const int c) const { 329 if (KEY_COUNT == 0) { 330 // We do not have the coordinate data 331 return NOT_AN_INDEX; 332 } 333 const unsigned short baseLowerC = toBaseLowerCase(c); 334 if (baseLowerC > MAX_CHAR_CODE) { 335 return NOT_AN_INDEX; 336 } 337 return mCodeToKeyIndex[baseLowerC]; 338 } 339 340 float ProximityInfo::calculateSquaredDistanceFromSweetSpotCenter( 341 const int keyIndex, const int inputIndex) const { 342 const float sweetSpotCenterX = mSweetSpotCenterXs[keyIndex]; 343 const float sweetSpotCenterY = mSweetSpotCenterYs[keyIndex]; 344 const float inputX = (float)mInputXCoordinates[inputIndex]; 345 const float inputY = (float)mInputYCoordinates[inputIndex]; 346 return square(inputX - sweetSpotCenterX) + square(inputY - sweetSpotCenterY); 347 } 348 349 inline const int* ProximityInfo::getProximityCharsAt(const int index) const { 350 return mInputCodes + (index * MAX_PROXIMITY_CHARS_SIZE); 351 } 352 353 unsigned short ProximityInfo::getPrimaryCharAt(const int index) const { 354 return getProximityCharsAt(index)[0]; 355 } 356 357 inline bool ProximityInfo::existsCharInProximityAt(const int index, const int c) const { 358 const int *chars = getProximityCharsAt(index); 359 int i = 0; 360 while (chars[i] > 0 && i < MAX_PROXIMITY_CHARS_SIZE) { 361 if (chars[i++] == c) { 362 return true; 363 } 364 } 365 return false; 366 } 367 368 bool ProximityInfo::existsAdjacentProximityChars(const int index) const { 369 if (index < 0 || index >= mInputLength) return false; 370 const int currentChar = getPrimaryCharAt(index); 371 const int leftIndex = index - 1; 372 if (leftIndex >= 0 && existsCharInProximityAt(leftIndex, currentChar)) { 373 return true; 374 } 375 const int rightIndex = index + 1; 376 if (rightIndex < mInputLength && existsCharInProximityAt(rightIndex, currentChar)) { 377 return true; 378 } 379 return false; 380 } 381 382 // In the following function, c is the current character of the dictionary word 383 // currently examined. 384 // currentChars is an array containing the keys close to the character the 385 // user actually typed at the same position. We want to see if c is in it: if so, 386 // then the word contains at that position a character close to what the user 387 // typed. 388 // What the user typed is actually the first character of the array. 389 // proximityIndex is a pointer to the variable where getMatchedProximityId returns 390 // the index of c in the proximity chars of the input index. 391 // Notice : accented characters do not have a proximity list, so they are alone 392 // in their list. The non-accented version of the character should be considered 393 // "close", but not the other keys close to the non-accented version. 394 ProximityInfo::ProximityType ProximityInfo::getMatchedProximityId(const int index, 395 const unsigned short c, const bool checkProximityChars, int *proximityIndex) const { 396 const int *currentChars = getProximityCharsAt(index); 397 const int firstChar = currentChars[0]; 398 const unsigned short baseLowerC = toBaseLowerCase(c); 399 400 // The first char in the array is what user typed. If it matches right away, 401 // that means the user typed that same char for this pos. 402 if (firstChar == baseLowerC || firstChar == c) { 403 return EQUIVALENT_CHAR; 404 } 405 406 if (!checkProximityChars) return UNRELATED_CHAR; 407 408 // If the non-accented, lowercased version of that first character matches c, 409 // then we have a non-accented version of the accented character the user 410 // typed. Treat it as a close char. 411 if (toBaseLowerCase(firstChar) == baseLowerC) 412 return NEAR_PROXIMITY_CHAR; 413 414 // Not an exact nor an accent-alike match: search the list of close keys 415 int j = 1; 416 while (j < MAX_PROXIMITY_CHARS_SIZE 417 && currentChars[j] > ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE) { 418 const bool matched = (currentChars[j] == baseLowerC || currentChars[j] == c); 419 if (matched) { 420 if (proximityIndex) { 421 *proximityIndex = j; 422 } 423 return NEAR_PROXIMITY_CHAR; 424 } 425 ++j; 426 } 427 if (j < MAX_PROXIMITY_CHARS_SIZE 428 && currentChars[j] == ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE) { 429 ++j; 430 while (j < MAX_PROXIMITY_CHARS_SIZE 431 && currentChars[j] > ADDITIONAL_PROXIMITY_CHAR_DELIMITER_CODE) { 432 const bool matched = (currentChars[j] == baseLowerC || currentChars[j] == c); 433 if (matched) { 434 if (proximityIndex) { 435 *proximityIndex = j; 436 } 437 return ADDITIONAL_PROXIMITY_CHAR; 438 } 439 ++j; 440 } 441 } 442 443 // Was not included, signal this as an unrelated character. 444 return UNRELATED_CHAR; 445 } 446 447 bool ProximityInfo::sameAsTyped(const unsigned short *word, int length) const { 448 if (length != mInputLength) { 449 return false; 450 } 451 const int *inputCodes = mInputCodes; 452 while (length--) { 453 if ((unsigned int) *inputCodes != (unsigned int) *word) { 454 return false; 455 } 456 inputCodes += MAX_PROXIMITY_CHARS_SIZE; 457 word++; 458 } 459 return true; 460 } 461 462 const int ProximityInfo::NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR_LOG_2; 463 const int ProximityInfo::NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR; 464 const int ProximityInfo::MAX_KEY_COUNT_IN_A_KEYBOARD; 465 const int ProximityInfo::MAX_CHAR_CODE; 466 467 } // namespace latinime 468