From patchwork Mon Jul 28 12:19:27 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Javier Martinez Canillas X-Patchwork-Id: 4633871 Return-Path: X-Original-To: patchwork-linux-input@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork1.web.kernel.org (Postfix) with ESMTP id 786B29F36A for ; Mon, 28 Jul 2014 12:20:00 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 7B1402017E for ; Mon, 28 Jul 2014 12:19:58 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 6E8962018E for ; Mon, 28 Jul 2014 12:19:57 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752890AbaG1MTy (ORCPT ); Mon, 28 Jul 2014 08:19:54 -0400 Received: from bhuna.collabora.co.uk ([93.93.135.160]:57570 "EHLO bhuna.collabora.co.uk" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752549AbaG1MTw (ORCPT ); Mon, 28 Jul 2014 08:19:52 -0400 Received: from [127.0.0.1] (localhost [127.0.0.1]) (Authenticated sender: javier) with ESMTPSA id 5E3C2602D4B From: Javier Martinez Canillas To: Lee Jones Cc: Wolfram Sang , Dmitry Torokhov , Doug Anderson , Simon Glass , Bill Richardson , Andrew Bresticker , Derek Basehore , Todd Broch , Olof Johansson , linux-i2c@vger.kernel.org, linux-input@vger.kernel.org, linux-samsung-soc@vger.kernel.org Subject: [PATCH 7/7] Input: cros_ec_keyb: Optimize ghosting algorithm. Date: Mon, 28 Jul 2014 14:19:27 +0200 Message-Id: <1406549967-21291-8-git-send-email-javier.martinez@collabora.co.uk> X-Mailer: git-send-email 2.0.0.rc2 In-Reply-To: <1406549967-21291-1-git-send-email-javier.martinez@collabora.co.uk> References: <1406549967-21291-1-git-send-email-javier.martinez@collabora.co.uk> Sender: linux-input-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-input@vger.kernel.org X-Spam-Status: No, score=-7.6 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Todd Broch 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 Reviewed-by: Vincent Palatin Reviewed-by: Luigi Semenzato Tested-by: Andreas Färber --- drivers/input/keyboard/cros_ec_keyb.c | 92 +++++++++++++++++++---------------- 1 file changed, 49 insertions(+), 43 deletions(-) diff --git a/drivers/input/keyboard/cros_ec_keyb.c b/drivers/input/keyboard/cros_ec_keyb.c index 93111d1..5d773d2 100644 --- a/drivers/input/keyboard/cros_ec_keyb.c +++ b/drivers/input/keyboard/cros_ec_keyb.c @@ -22,6 +22,7 @@ */ #include +#include #include #include #include @@ -38,6 +39,7 @@ * @row_shift: log2 or number of rows, rounded up * @keymap_data: Matrix keymap data used to convert to keyscan values * @ghost_filter: true to enable the matrix key-ghosting filter + * @valid_keys: bitmap of existing keys for each matrix column * @old_kb_state: bitmap of keys pressed last scan * @dev: Device pointer * @idev: Input device @@ -49,6 +51,7 @@ struct cros_ec_keyb { int row_shift; const struct matrix_keymap_data *keymap_data; bool ghost_filter; + uint8_t *valid_keys; uint8_t *old_kb_state; struct device *dev; @@ -57,39 +60,15 @@ struct cros_ec_keyb { }; -static bool cros_ec_keyb_row_has_ghosting(struct cros_ec_keyb *ckdev, - uint8_t *buf, int row) -{ - int pressed_in_row = 0; - int row_has_teeth = 0; - int col, mask; - - mask = 1 << row; - for (col = 0; col < ckdev->cols; col++) { - if (buf[col] & mask) { - pressed_in_row++; - row_has_teeth |= buf[col] & ~mask; - if (pressed_in_row > 1 && row_has_teeth) { - /* ghosting */ - dev_dbg(ckdev->dev, - "ghost found at: r%d c%d, pressed %d, teeth 0x%x\n", - row, col, pressed_in_row, - row_has_teeth); - return true; - } - } - } - - return false; -} - /* * Returns true when there is at least one combination of pressed keys that * results in ghosting. */ static bool cros_ec_keyb_has_ghosting(struct cros_ec_keyb *ckdev, uint8_t *buf) { - int row; + int col1, col2, buf1, buf2; + struct device *dev = ckdev->dev; + uint8_t *valid_keys = ckdev->valid_keys; /* * Ghosting happens if for any pressed key X there are other keys @@ -103,27 +82,23 @@ static bool cros_ec_keyb_has_ghosting(struct cros_ec_keyb *ckdev, 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 < ckdev->rows; row++) - if (cros_ec_keyb_row_has_ghosting(ckdev, buf, row)) - return true; + for (col1 = 0; col1 < ckdev->cols; col1++) { + buf1 = buf[col1] & valid_keys[col1]; + for (col2 = col1 + 1; col2 < ckdev->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; + } + } + } return false; } + /* * Compares the new keyboard state to the old one and produces key * press/release events accordingly. The keyboard state is 13 bytes (one byte @@ -222,6 +197,30 @@ static void cros_ec_keyb_close(struct input_dev *dev) free_irq(ec->irq, ckdev); } +/* + * Walks keycodes flipping bit in buffer COLUMNS deep where bit is ROW. Used by + * ghosting logic to ignore NULL or virtual keys. + */ +static void cros_ec_keyb_compute_valid_keys(struct cros_ec_keyb *ckdev) +{ + int row, col; + int row_shift = ckdev->row_shift; + unsigned short *keymap = ckdev->idev->keycode; + unsigned short code; + + BUG_ON(ckdev->idev->keycodesize != sizeof(*keymap)); + + for (col = 0; col < ckdev->cols; col++) { + for (row = 0; row < ckdev->rows; row++) { + code = keymap[MATRIX_SCAN_CODE(row, col, row_shift)]; + if (code && (code != KEY_BATTERY)) + ckdev->valid_keys[col] |= 1 << row; + } + dev_dbg(ckdev->dev, "valid_keys[%02d] = 0x%02x\n", + col, ckdev->valid_keys[col]); + } +} + static int cros_ec_keyb_probe(struct platform_device *pdev) { struct cros_ec_device *ec = dev_get_drvdata(pdev->dev.parent); @@ -242,6 +241,11 @@ static int cros_ec_keyb_probe(struct platform_device *pdev) &ckdev->cols); if (err) return err; + + ckdev->valid_keys = devm_kzalloc(&pdev->dev, ckdev->cols, GFP_KERNEL); + if (!ckdev->valid_keys) + return -ENOMEM; + ckdev->old_kb_state = devm_kzalloc(&pdev->dev, ckdev->cols, GFP_KERNEL); if (!ckdev->old_kb_state) return -ENOMEM; @@ -285,6 +289,8 @@ static int cros_ec_keyb_probe(struct platform_device *pdev) input_set_capability(idev, EV_MSC, MSC_SCAN); input_set_drvdata(idev, ckdev); ckdev->idev = idev; + cros_ec_keyb_compute_valid_keys(ckdev); + err = input_register_device(ckdev->idev); if (err) { dev_err(dev, "cannot register input device\n");