Debounce refactor / API (#3720)

* Added xeal60 via clone of lets split

* Delete removed other keymaps

* Basic keymap (no FN). Compiles.

* Removed NP_STAR and NP_SLSH.

* Removed "debounce_algo = manual" in all keyboards with CUSTOM_MATRIX = yes.

* Changed order of rules in TMK. Documented feature.

* Fixed missing whitespace in debounce documentation

Table wasn't working due to missing newline.

* Added bold in a few areas.

* DO NOT USE - Removed debounce from TMK.

* Remove accidental xeal60 commit

* DO NOT USE - debounce successfully compiled.

* DO NOT USE Revert back to original API to support split_keyboards.

* Working eager_pk

* Whitespace cleanup.

* Restored debounce.h since there wasnt any real change.

* Moved debouncing_time variable  to inside #if debounce

* Removed check for custom_matrix. We can safely include the debounce file for compilation when custom_matrix is used.

* Removed #include "matrix.h" from debounce.h

* Bug fix - was using MATRIX_ROWS instead of num_rows

* Fixed compilation error with debounce_sym_g

* Renamed DEBOUNCE_ALGO to DEBOUNCE_TYPE

* Malloc array in debounce_eager_pk, since split keyboards only use MATRIX_ROWS/2.

* Fix compile error in debounce_eager_pk

* Stricter, leaner DEBOUNCE_TYPE section in common_features.mk. Cleanup debounce_type.mk

10 files changed, 272 insertions, 100 deletions

diff --git a/common_features.mk b/common_features.mk
index b5fdb404b..6f02dbac6 100644
--- a/common_features.mk
+++ b/common_features.mk
@@ -282,10 +282,20 @@ ifneq ($(strip $(CUSTOM_MATRIX)), yes)
     endif
 endif
 
-# Include the standard debounce code if needed
-ifneq ($(strip $(CUSTOM_DEBOUNCE)), yes)
-    QUANTUM_SRC += $(QUANTUM_DIR)/debounce.c
+DEBOUNCE_DIR:= $(QUANTUM_DIR)/debounce
+# Debounce Modules. If implemented in matrix.c, don't use these.
+DEBOUNCE_TYPE?= sym_g
+VALID_DEBOUNCE_TYPES := sym_g eager_pk custom
+ifeq ($(filter $(DEBOUNCE_TYPE),$(VALID_DEBOUNCE_TYPES)),)
+    $(error DEBOUNCE_TYPE="$(DEBOUNCE_TYPE)" is not a valid debounce algorithm)
 endif
+ifeq ($(strip $(DEBOUNCE_TYPE)), sym_g)
+    QUANTUM_SRC += $(DEBOUNCE_DIR)/debounce_sym_g.c
+else ifeq ($(strip $(DEBOUNCE_TYPE)), eager_pk)
+    QUANTUM_SRC += $(DEBOUNCE_DIR)/debounce_eager_pk.c
+endif
+
+
 
 ifeq ($(strip $(SPLIT_KEYBOARD)), yes)
     OPT_DEFS += -DSPLIT_KEYBOARD
diff --git a/docs/feature_debounce_type.md b/docs/feature_debounce_type.md
new file mode 100644
index 000000000..82b3d7de1
--- /dev/null
+++ b/docs/feature_debounce_type.md
@@ -0,0 +1,46 @@
+# Debounce algorithm
+
+QMK supports multiple debounce algorithms through its debounce API.
+
+The underlying debounce algorithm is determined by which matrix.c file you are using.
+
+The logic for which debounce method called is below. It checks various defines that you have set in rules.mk
+
+```
+DEBOUNCE_TYPE?= sym_g
+VALID_DEBOUNCE_TYPES := sym_g eager_pk custom
+ifeq ($(filter $(DEBOUNCE_TYPE),$(VALID_DEBOUNCE_TYPES)),)
+    $(error DEBOUNCE_TYPE="$(DEBOUNCE_TYPE)" is not a valid debounce algorithm)
+endif
+ifeq ($(strip $(DEBOUNCE_TYPE)), sym_g)
+    QUANTUM_SRC += $(DEBOUNCE_DIR)/debounce_sym_g.c
+else ifeq ($(strip $(DEBOUNCE_TYPE)), eager_pk)
+    QUANTUM_SRC += $(DEBOUNCE_DIR)/debounce_eager_pk.c
+endif
+```
+
+# Debounce selection
+
+| DEBOUNCE_ALGO    | Description                                                 | What to do                    |
+| -------------    | ---------------------------------------------------         | ----------------------------- |
+| Not defined      | You are using the included matrix.c and debounce.c          | Nothing. Debounce_sym_g will be compiled, and used if necessary |
+| custom           | Use your own debounce.c                                     | ```SRC += debounce.c``` add your own debounce.c and implement necessary functions |
+| sym_g / eager_pk | You are using the included matrix.c and debounce.c          | Use an alternative debounce algorithm |
+
+**Regarding split keyboards**: 
+The debounce code is compatible with split keyboards.
+
+# Use your own debouncing code
+* Set ```DEBOUNCE_TYPE = custom ```.
+* Add ```SRC += debounce.c```
+* Add your own ```debounce.c```. Look at included ```debounce_sym_g.c```s for sample implementations.
+* Debouncing occurs after every raw matrix scan.
+* Use num_rows rather than MATRIX_ROWS, so that split keyboards are supported correctly.
+
+# Changing between included debouncing methods
+You can either use your own code, by including your own debounce.c, or switch to another included one.
+Included debounce methods are:
+* debounce_eager_pk - debouncing per key. On any state change, response is immediate, followed by ```DEBOUNCE_DELAY``` millseconds of no further input for that key
+* debounce_sym_g - debouncing per keyboard. On any state change, a global timer is set. When ```DEBOUNCE_DELAY``` milliseconds of no changes has occured, all input changes are pushed.
+
+
diff --git a/keyboards/handwired/xealous/rules.mk b/keyboards/handwired/xealous/rules.mk
index 07e1c875e..7d07c9aa5 100644
--- a/keyboards/handwired/xealous/rules.mk
+++ b/keyboards/handwired/xealous/rules.mk
@@ -68,7 +68,7 @@ SUBPROJECT_rev1 = yes
 SLEEP_LED_ENABLE = no    # Breathing sleep LED during USB suspend
 
 CUSTOM_MATRIX = no
-CUSTOM_DEBOUNCE = yes
+DEBOUNCE_TYPE = custom
 
 LAYOUTS = split60
 
diff --git a/quantum/debounce.c b/quantum/debounce.c
deleted file mode 100644
index 929023ab2..000000000
--- a/quantum/debounce.c
+++ /dev/null
@@ -1,52 +0,0 @@
-
-#include "matrix.h"
-#include "timer.h"
-#include "quantum.h"
-
-#ifndef DEBOUNCING_DELAY
-#  define DEBOUNCING_DELAY 5
-#endif
-
-void debounce_init(uint8_t num_rows) {
-}
-
-#if DEBOUNCING_DELAY > 0
-
-static bool debouncing = false;
-
-void debounce(matrix_row_t raw[], matrix_row_t cooked[], uint8_t num_rows, bool changed) {
-  static uint16_t debouncing_time;
-
-  if (changed) {
-    debouncing = true;
-    debouncing_time = timer_read();
-  }
-
-  if (debouncing && (timer_elapsed(debouncing_time) > DEBOUNCING_DELAY)) {
-    for (uint8_t i = 0; i < num_rows; i++) {
-      cooked[i] = raw[i];
-    }
-    debouncing = false;
-  }
-}
-
-bool debounce_active(void) {
-  return debouncing;
-}
-
-#else
-
-// no debounce
-void debounce(matrix_row_t raw[], matrix_row_t cooked[], uint8_t num_rows, bool changed) {
-  if (changed)
-  {
-  for (uint8_t i = 0; i < num_rows; i++) {
-      cooked[i] = raw[i];
-    }
-  }
-}
-
-bool debounce_active(void) {
-  return false;
-}
-#endif
diff --git a/quantum/debounce.h b/quantum/debounce.h
index 360af77e7..9ca05c682 100644
--- a/quantum/debounce.h
+++ b/quantum/debounce.h
@@ -8,4 +8,4 @@ void debounce(matrix_row_t raw[], matrix_row_t cooked[], uint8_t num_rows, bool
 
 bool debounce_active(void);
 
-void debounce_init(uint8_t num_rows);
\ No newline at end of file
+void debounce_init(uint8_t num_rows);
diff --git a/quantum/debounce/debounce_eager_pk.c b/quantum/debounce/debounce_eager_pk.c
new file mode 100644
index 000000000..b8ad09cee
--- /dev/null
+++ b/quantum/debounce/debounce_eager_pk.c
@@ -0,0 +1,121 @@
+/*
+Copyright 2017 Alex Ong<the.onga@gmail.com>
+This program is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 2 of the License, or
+(at your option) any later version.
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+You should have received a copy of the GNU General Public License
+along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+Basic per-key algorithm. Uses an 8-bit counter per key.
+After pressing a key, it immediately changes state, and sets a counter.
+No further inputs are accepted until DEBOUNCE milliseconds have occurred.
+*/
+
+#include "matrix.h"
+#include "timer.h"
+#include "quantum.h"
+#include <stdlib.h>
+
+#ifndef DEBOUNCE
+  #define DEBOUNCE 5
+#endif
+
+
+#if (MATRIX_COLS <= 8)
+#    define ROW_SHIFTER ((uint8_t)1)
+#elif (MATRIX_COLS <= 16)
+#    define ROW_SHIFTER ((uint16_t)1)
+#elif (MATRIX_COLS <= 32)
+#    define ROW_SHIFTER  ((uint32_t)1)
+#endif
+
+
+
+#define debounce_counter_t uint8_t
+
+static debounce_counter_t *debounce_counters;
+
+#define DEBOUNCE_ELAPSED 251
+#define MAX_DEBOUNCE (DEBOUNCE_ELAPSED - 1)
+
+void update_debounce_counters(uint8_t num_rows, uint8_t current_time);
+void transfer_matrix_values(matrix_row_t raw[], matrix_row_t cooked[], uint8_t num_rows, uint8_t current_time);
+
+//we use num_rows rather than MATRIX_ROWS to support split keyboards
+void debounce_init(uint8_t num_rows)
+{
+  debounce_counters = (debounce_counter_t*)malloc(num_rows*MATRIX_COLS * sizeof(debounce_counter_t));
+  int i = 0;
+  for (uint8_t r = 0; r < num_rows; r++)
+  {
+    for (uint8_t c = 0; c < MATRIX_COLS; c++)
+    {
+      debounce_counters[i++] = DEBOUNCE_ELAPSED;
+    }
+  }
+}
+
+void debounce(matrix_row_t raw[], matrix_row_t cooked[], uint8_t num_rows, bool changed)
+{
+  uint8_t current_time = timer_read() % MAX_DEBOUNCE;
+  update_debounce_counters(num_rows, current_time);
+  transfer_matrix_values(raw, cooked, num_rows, current_time);
+}
+
+//If the current time is > debounce counter, set the counter to enable input.
+void update_debounce_counters(uint8_t num_rows, uint8_t current_time)
+{
+  debounce_counter_t *debounce_pointer = debounce_counters;
+  for (uint8_t row = 0; row < num_rows; row++)
+  {
+    for (uint8_t col = 0; col < MATRIX_COLS; col++)
+    {
+      if (*debounce_pointer != DEBOUNCE_ELAPSED)
+      {
+        if (TIMER_DIFF(current_time, *debounce_pointer, MAX_DEBOUNCE) >= DEBOUNCE) {
+          *debounce_pointer = DEBOUNCE_ELAPSED;
+        }
+      }
+      debounce_pointer++;
+    }
+  }
+}
+
+// upload from raw_matrix to final matrix;
+void transfer_matrix_values(matrix_row_t raw[], matrix_row_t cooked[], uint8_t num_rows, uint8_t current_time)
+{
+  debounce_counter_t *debounce_pointer = debounce_counters;
+  for (uint8_t row = 0; row < num_rows; row++)
+  {
+    matrix_row_t existing_row = cooked[row]; 
+    matrix_row_t raw_row = raw[row];
+
+    for (uint8_t col = 0; col < MATRIX_COLS; col++)
+    {
+      matrix_row_t col_mask = (ROW_SHIFTER << col);
+      bool final_value = raw_row & col_mask;
+      bool existing_value = existing_row & col_mask;
+      if (*debounce_pointer == DEBOUNCE_ELAPSED &&
+          (existing_value != final_value))
+      {
+        *debounce_pointer = current_time;
+        existing_row ^= col_mask; //flip the bit.
+      }
+      debounce_pointer++;
+    }
+    cooked[row] = existing_row;
+  }  
+}
+
+bool debounce_active(void)
+{
+  return true;
+}
+
diff --git a/quantum/debounce/debounce_sym_g.c b/quantum/debounce/debounce_sym_g.c
new file mode 100644
index 000000000..c8ab34e1a
--- /dev/null
+++ b/quantum/debounce/debounce_sym_g.c
@@ -0,0 +1,57 @@
+/*
+Copyright 2017 Alex Ong<the.onga@gmail.com>
+This program is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 2 of the License, or
+(at your option) any later version.
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+You should have received a copy of the GNU General Public License
+along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+Basic global debounce algorithm. Used in 99% of keyboards at time of implementation
+When no state changes have occured for DEBOUNCE milliseconds, we push the state.
+*/
+#include "matrix.h"
+#include "timer.h"
+#include "quantum.h"
+#ifndef DEBOUNCE
+  #define DEBOUNCE 5
+#endif
+
+void debounce_init(uint8_t num_rows) {}
+static bool debouncing = false;
+
+#if DEBOUNCE > 0
+static uint16_t debouncing_time;
+void debounce(matrix_row_t raw[], matrix_row_t cooked[], uint8_t num_rows, bool changed)
+{
+  if (changed) {
+    debouncing = true;
+    debouncing_time = timer_read();
+  }
+
+  if (debouncing && timer_elapsed(debouncing_time) > DEBOUNCE) {
+    for (int i = 0; i < num_rows; i++) {
+      cooked[i] = raw[i];
+    }
+    debouncing = false;
+  }
+}
+#else //no debouncing.
+void debounce(matrix_row_t raw[], matrix_row_t cooked[], uint8_t num_rows, bool changed)
+{
+  for (int i = 0; i < num_rows; i++) {
+    cooked[i] = raw[i];
+  }
+}
+#endif
+
+bool debounce_active(void) {
+  return debouncing;
+}
+
diff --git a/quantum/debounce/readme.md b/quantum/debounce/readme.md
new file mode 100644
index 000000000..1a77d44df
--- /dev/null
+++ b/quantum/debounce/readme.md
@@ -0,0 +1,28 @@
+Debounce algorithms belong in this folder.
+Here are a few ideas
+
+1) Global vs Per-Key vs Per-Row
+ * Global - one timer for all keys. Any key change state affects global timer
+ * Per key - one timer per key
+ * Per row - one timer per row
+
+2) Eager vs symmetric vs assymetric
+ * Eager - any key change is reported immediately. All further inputs for DEBOUNCE ms are ignored.
+ * Symmetric - wait for no changes for DEBOUNCE ms before reporting change
+ * Assymetric - wait for different times depending on key-down/key-up. E.g. Eager key-down, DEBOUNCE ms key up.
+
+3) Timestamp vs cycles
+ * old old old code waits n cycles, decreasing count by one each matrix_scan
+ * newer code stores the millisecond the change occurred, and does subraction to figure out time elapsed.
+ * Timestamps are superior, i don't think cycles will ever be used again once upgraded.
+
+The default algorithm is symmetric and global.
+Here are a few that could be implemented:
+
+debounce_sym_g.c
+debounce_sym_pk.c 
+debounce_sym_pr.c 
+debounce_sym_pr_cycles.c //currently used in ergo-dox
+debounce_eager_g.c
+debounce_eager_pk.c
+debounce_eager_pr.c //could be used in ergo-dox!
diff --git a/quantum/matrix.c b/quantum/matrix.c
index d2b805d7f..f7cad1a0f 100644
--- a/quantum/matrix.c
+++ b/quantum/matrix.c
@@ -51,10 +51,8 @@ static const pin_t col_pins[MATRIX_COLS] = MATRIX_COL_PINS;
 #endif
 
 /* matrix state(1:on, 0:off) */
-static matrix_row_t raw_matrix[MATRIX_ROWS];
-
-static matrix_row_t matrix[MATRIX_ROWS];
-
+static matrix_row_t raw_matrix[MATRIX_ROWS]; //raw values
+static matrix_row_t matrix[MATRIX_ROWS]; //debounced values
 
 #if (DIODE_DIRECTION == COL2ROW)
     static void init_cols(void);
@@ -108,30 +106,6 @@ uint8_t matrix_cols(void) {
     return MATRIX_COLS;
 }
 
-// void matrix_power_up(void) {
-// #if (DIODE_DIRECTION == COL2ROW)
-//     for (int8_t r = MATRIX_ROWS - 1; r >= 0; --r) {
-//         /* DDRxn */
-//         _SFR_IO8((row_pins[r] >> 4) + 1) |= _BV(row_pins[r] & 0xF);
-//         toggle_row(r);
-//     }
-//     for (int8_t c = MATRIX_COLS - 1; c >= 0; --c) {
-//         /* PORTxn */
-//         _SFR_IO8((col_pins[c] >> 4) + 2) |= _BV(col_pins[c] & 0xF);
-//     }
-// #elif (DIODE_DIRECTION == ROW2COL)
-//     for (int8_t c = MATRIX_COLS - 1; c >= 0; --c) {
-//         /* DDRxn */
-//         _SFR_IO8((col_pins[c] >> 4) + 1) |= _BV(col_pins[c] & 0xF);
-//         toggle_col(c);
-//     }
-//     for (int8_t r = MATRIX_ROWS - 1; r >= 0; --r) {
-//         /* PORTxn */
-//         _SFR_IO8((row_pins[r] >> 4) + 2) |= _BV(row_pins[r] & 0xF);
-//     }
-// #endif
-// }
-
 void matrix_init(void) {
 
     // initialize row and col
@@ -175,6 +149,7 @@ uint8_t matrix_scan(void)
   return 1;
 }
 
+//Deprecated.
 bool matrix_is_modified(void)
 {
     if (debounce_active()) return false;
diff --git a/tmk_core/common/keyboard.c b/tmk_core/common/keyboard.c
index 15652276b..849d74aa1 100644
--- a/tmk_core/common/keyboard.c
+++ b/tmk_core/common/keyboard.c
@@ -252,9 +252,6 @@ void keyboard_init(void) {
 void keyboard_task(void)
 {
     static matrix_row_t matrix_prev[MATRIX_ROWS];
-#ifdef MATRIX_HAS_GHOST
-  //  static matrix_row_t matrix_ghost[MATRIX_ROWS];
-#endif
     static uint8_t led_status = 0;
     matrix_row_t matrix_row = 0;
     matrix_row_t matrix_change = 0;
@@ -263,24 +260,14 @@ void keyboard_task(void)
 #endif
 
     matrix_scan();
+
     if (is_keyboard_master()) {
         for (uint8_t r = 0; r < MATRIX_ROWS; r++) {
             matrix_row = matrix_get_row(r);
             matrix_change = matrix_row ^ matrix_prev[r];
             if (matrix_change) {
 #ifdef MATRIX_HAS_GHOST
-                if (has_ghost_in_row(r, matrix_row)) {
-                    /* Keep track of whether ghosted status has changed for
-                    * debugging. But don't update matrix_prev until un-ghosted, or
-                    * the last key would be lost.
-                    */
-                    //if (debug_matrix && matrix_ghost[r] != matrix_row) {
-                    //    matrix_print();
-                    //}
-                    //matrix_ghost[r] = matrix_row;
-                    continue;
-                }
-                //matrix_ghost[r] = matrix_row;
+                if (has_ghost_in_row(r, matrix_row)) { continue; }
 #endif
                 if (debug_matrix) matrix_print();
                 for (uint8_t c = 0; c < MATRIX_COLS; c++) {