From: Todd Broch Date: Fri, 19 Apr 2013 23:48:03 +0000 (-0700) Subject: CHROMIUM: mkbp: Optimize ghosting algorithm. X-Git-Url: http://git.cascardo.eti.br/?p=cascardo%2Flinux.git;a=commitdiff_plain;h=ed9cf9b07c960582178ac75dee407e801739725a CHROMIUM: mkbp: Optimize ghosting algorithm. Previous algorithm was a bit conservative and complicating with respect to identifying key ghosting. This CL uses the bitops hamming weight function (hweight8) to count the number of matching rows for colM & colN. If that number is > 1 ghosting is present. Additionally it removes NULL keys and our one virtual keypress KEY_BATTERY from consideration as these inputs are never physical keypresses. Signed-off-by: Todd Broch BUG=chrome-os-partner:18354 TEST=manual 1. using evtest I now see ctrl-U 2. escape sequence ctrl-U correctly display 'webpage source' 3. w/ #define DEBUG in mkbp.c no longer see below when ctrl-U pressed chromeos-ec-i2c 4-001e: ghost found ... Change-Id: Ifc98b527c3ee4daffa9d8c726429fdd1b35970fa Reviewed-on: https://gerrit.chromium.org/gerrit/48789 Reviewed-by: Vincent Palatin Reviewed-by: Luigi Semenzato Commit-Queue: Todd Broch Tested-by: Todd Broch --- diff --git a/drivers/input/keyboard/mkbp.c b/drivers/input/keyboard/mkbp.c index ab7e47d6e4b6..88093bf78242 100644 --- a/drivers/input/keyboard/mkbp.c +++ b/drivers/input/keyboard/mkbp.c @@ -28,6 +28,7 @@ */ #include +#include #include #include #include @@ -38,15 +39,6 @@ #include #include -struct mkbp_device { - struct device *dev; - struct input_dev *idev; - struct chromeos_ec_device *ec; - struct notifier_block notifier; - struct notifier_block wake_notifier; -}; - - /* * The standard MKBP keyboard matrix table. * @@ -56,6 +48,15 @@ struct mkbp_device { #define MKBP_NUM_ROWS 8 #define MKBP_NUM_COLS 13 +struct mkbp_device { + struct device *dev; + struct input_dev *idev; + struct chromeos_ec_device *ec; + struct notifier_block notifier; + struct notifier_block wake_notifier; + uint8_t valid_keys[MKBP_NUM_COLS]; +}; + /* We will read this table from the Device Tree when we have one. */ static uint16_t mkbp_keycodes[MKBP_NUM_ROWS][MKBP_NUM_COLS] = { { 0x0, KEY_LEFTMETA, KEY_F1, KEY_B, @@ -117,15 +118,12 @@ static inline void mkbp_send_key_event(struct mkbp_device *mkbp_dev, * Returns true when there is at least one combination of pressed keys that * results in ghosting. */ -static bool mkbp_has_ghosting(struct device *dev, uint8_t *buf) +static bool mkbp_has_ghosting(struct mkbp_device *mkbp_dev, uint8_t *buf) { - int col, row; - int mask; - int pressed_in_row[MKBP_NUM_ROWS]; - int row_has_teeth[MKBP_NUM_ROWS]; + int col1, col2, buf1, buf2; + struct device *dev = mkbp_dev->dev; + uint8_t *valid_keys = mkbp_dev->valid_keys; - memset(pressed_in_row, 0, sizeof(pressed_in_row)); - memset(row_has_teeth, 0, sizeof(row_has_teeth)); /* * Ghosting happens if for any pressed key X there are other keys * pressed both in the same row and column of X as, for instance, @@ -138,35 +136,16 @@ static bool mkbp_has_ghosting(struct device *dev, uint8_t *buf) * * In this case only X, Y, and Z are pressed, but g appears to be * pressed too (see Wikipedia). - * - * We can detect ghosting in a single pass (*) over the keyboard state - * by maintaining two arrays. pressed_in_row counts how many pressed - * keys we have found in a row. row_has_teeth is true if any of the - * pressed keys for this row has other pressed keys in its column. If - * at any point of the scan we find that a row has multiple pressed - * keys, and at least one of them is at the intersection with a column - * with multiple pressed keys, we're sure there is ghosting. - * Conversely, if there is ghosting, we will detect such situation for - * at least one key during the pass. - * - * (*) This looks linear in the number of keys, but it's not. We can - * cheat because the number of rows is small. */ - for (row = 0; row < MKBP_NUM_ROWS; row++) { - mask = 1 << row; - for (col = 0; col < MKBP_NUM_COLS; col++) { - if (buf[col] & mask) { - pressed_in_row[row] += 1; - row_has_teeth[row] |= buf[col] & ~mask; - if (pressed_in_row[row] > 1 && - row_has_teeth[row]) { - /* ghosting */ - dev_dbg(dev, "ghost found at: r%d c%d," - " pressed %d, teeth 0x%x\n", - row, col, pressed_in_row[row], - row_has_teeth[row]); - return true; - } + for (col1 = 0; col1 < MKBP_NUM_COLS; col1++) { + buf1 = buf[col1] & valid_keys[col1]; + for (col2 = col1 + 1; col2 < MKBP_NUM_COLS; col2++) { + buf2 = buf[col2] & valid_keys[col2]; + if (hweight8(buf1 & buf2) > 1) { + dev_dbg(dev, "ghost found at: B[%02d]:0x%02x & " + "B[%02d]:0x%02x", col1, buf1, col2, + buf2); + return true; } } } @@ -194,7 +173,7 @@ static void mkbp_process(struct mkbp_device *mkbp_dev, num_cols = len; - if (mkbp_has_ghosting(mkbp_dev->dev, kb_state)) { + if (mkbp_has_ghosting(mkbp_dev, kb_state)) { /* * Simple-minded solution: ignore this state. The obvious * improvement is to only ignore changes to keys involved in @@ -311,6 +290,28 @@ static int mkbp_clear_keyboard(struct notifier_block *nb, return 0; } +/* + * Walks keycodes flipping bit in buffer COLUMNS deep where bit is ROW. Used by + * ghosting logic to ignore NULL or virtual keys. + */ +static void __devinit mkbp_compute_valid_keys(struct mkbp_device *mkbp_dev) +{ + int row, col; + uint16_t code; + + BUILD_BUG_ON(MKBP_NUM_ROWS > sizeof(mkbp_dev->valid_keys)); + + for (col = 0; col < MKBP_NUM_COLS; col++) { + for (row = 0; row < MKBP_NUM_ROWS; row++) { + code = mkbp_keycodes[row][col]; + if (code && (code != KEY_BATTERY)) + mkbp_dev->valid_keys[col] |= 1 << row; + } + dev_dbg(mkbp_dev->dev, "valid_keys[%02d] = 0x%02x\n", + col, mkbp_dev->valid_keys[col]); + } +} + static int __devinit mkbp_probe(struct platform_device *pdev) { struct chromeos_ec_device *ec = dev_get_drvdata(pdev->dev.parent); @@ -334,6 +335,7 @@ static int __devinit mkbp_probe(struct platform_device *pdev) mkbp_dev->notifier.notifier_call = mkbp_work; mkbp_dev->wake_notifier.notifier_call = mkbp_clear_keyboard; mkbp_dev->dev = dev; + mkbp_compute_valid_keys(mkbp_dev); idev->name = ec->get_name(ec); idev->phys = ec->get_phys_name(ec);