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 <tbroch@chromium.org>
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 <vpalatin@chromium.org>
Reviewed-by: Luigi Semenzato <semenzato@chromium.org>
Commit-Queue: Todd Broch <tbroch@chromium.org>
Tested-by: Todd Broch <tbroch@chromium.org>

diff --git a/drivers/input/keyboard/mkbp.c b/drivers/input/keyboard/mkbp.c
index ab7e47d..88093bf 100644 (file)
--- a/drivers/input/keyboard/mkbp.c
+++ b/drivers/input/keyboard/mkbp.c
@@ -28,6 +28,7 @@
  */
 
 #include <linux/module.h>
+#include <linux/bitops.h>
 #include <linux/i2c.h>
 #include <linux/input.h>
 #include <linux/kernel.h>
@@ -38,15 +39,6 @@
 #include <linux/power_supply.h>
 #include <linux/slab.h>
 
-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);