[Bug] Debounce can happen at (DEBOUNCE - 1)ms due to >= check

[andrebrait]

Describe the Bug

(From #21667, opening this as an issue to discuss it separately without interfering with that PR more than it already has)

It seems that, for most platforms, we get the time from ISRs or hardware clocks and we (or the platform) integer-divide them to get the number of milliseconds the clock is currently at.

Using AVR as an example, and considering the usage of prescalers and integer division, we have a timing problem, because the current checks are basically (in all algorithms) timer_elapsed >= DEBOUNCE, and that >= will possibly be true anywhere starting from DEBOUNCE - 1 + (1 clock cycle above the prescaler), not at DEBOUNCE milliseconds or greater.

As an example (frequency of 16MHz and prescaler of 64, getting us 1 interrupt every 1ms, or 1 interrupt every 250 CPU cycles, and a DEBOUNCE of 5).

1. During debounce, we check (and store) the timer at clock 10 * 250 + 230 getting (for example) a value of 10.
2. On another matrix scan, during debounce, we read the timer at exactly 15 * 250 + 10 clock cycles, meaning we get 15 as return.
3. We consider 15 >= 10 + 5, and send the matrix update.
4. The total debouncing time was thus 4.001875ms (4 * 250 + 30 cycles), not 5

We finished debouncing at less than 5 ms here. Currently, our approach only guarantees the debounce will happen at >= DEBOUNCE -1 time.

So we have two choices here:

1. Move the checks back to >
2. Let go of the timer being in ms and count in either us or ns, and bit-shift the value gotten from the interrupts if necessary, and then the check becomes more precise since we'll have the actual time. 32-bit should be enough for the purposes of debouncing, so even in ns precision we're talking about 4 seconds before it rolls over.

Originally posted by @andrebrait in #21667 (comment)

Keyboard Used

No response

Link to product page (if applicable)

No response

Operating System

No response

qmk doctor Output

No response

Is AutoHotKey / Karabiner installed

• AutoHotKey (Windows)
• Karabiner (macOS)

Other keyboard-related software installed

No response

Additional Context

Not keyboard related. It's a core bug.

[andrebrait]

Proposal for a high precision timer based on the current value of DEBOUNCE

Currently we use 8 (or 7, for asym_eager_defer_pk) bits for storing counters, and operating on them, and fast_timer_t, which can be either an uint16_t or uint32_t, to operate/get the time difference between two times.

In order to reduce the margin of error, we could use the full available precision up to the given amount of bits, relative to the desired DEBOUNCE. That would not lead to perfect precision, but the idea here is to operate on a "margin of error" that is proportional to the DEBOUNCE value used. A 1ms error is a lot worse if DEBOUNCE == 2 -> 50% error then it is if DEBOUNCE == 16 -> 6.25% error, etc.

By using all available bits for the counters and by using higher precision timers (instead of always targeting 1ms steps, we can target 1/8 or 1/16, 1/32, etc. of a ms), we can reduce the error margin by a lot.

We can use timer that is still uint8_t and the first X bits to represent the (binary) integer places, and the rest as the fractions of a millisecond (in base 2, of course), by left-shifting the DEBOUNCE by a factor (derived by how big the integer part of the target DEBOUNCE is), on counter initialization, and subtracting from it using the high precision timer at the desired scale. We can also get away with 1 extra bit by not using DEBOUNCE itself, but DEBOUNCE << scale - 1, as that will give us (e.g. if DEBOUNCE is 8ms) 7.96875ms instead of 8ms, and we change the evaluation criteria from >= to >.

Examples:

• if DEBOUNCE is 2ms:
  • XYYYYYYY where X is 0 .. 1, so 0 through 1, and YYYYYYY the remaining fractions of a millisecond (here up to 1/128ms). We initialize the counter with YYYYYYY as all ones, to approximate the target debounce as best as we can.
  • We can now represent a maximum of 1.9921875ms.
  • The maximum error is now reduced from 1ms (50%) to 7.81us (0.39% of 2ms).
• If DEBOUNCE is between 5 and 8ms:
  • XXXYYYYY where XXX is 000 .. 111, so 0 through 7, and YYYYY the remaining fractions of a millisecond (here up to 1/32ms). We initialize the counter with YYYYY as all ones, to approximate the target debounce as best as we can.
  • We can now represent a maximum of DEBOUNCE - 1 + 0.96875ms.
  • The maximum error is now reduced from 1ms (12.5% at 8ms) to 31.25us (0.39% of 8ms).
• If DEBOUNCE is between 9 and 16ms:
  • XXXXYYYY where XXXX is 0000 .. 1111, so 0 through 15, and YYYY the remaining fractions of a millisecond (here up to 1/16ms)
  • We can now represent a maximum of DEBOUNCE - 1 + 0.9375ms.
  • The maximum error is now reduced from 1ms (6.25% at 16ms) to 62.5us (0.39% of 16ms).

Alternatively, we can forgo that 1 bit and just use the value itself and keep the >= condition, though the precision will take a tiny hit:

Examples:

• if DEBOUNCE is 2ms:
  • XXYYYYYY where X is 00 .. 11, so 0 through 3, and YYYYYY the remaining fractions of a millisecond (here up to 1/64ms). We initialize the counter with YYYYYY as all ones, to approximate the target debounce as best as we can.
  • We can now detect the changing starting at 2.015625ms.
  • The maximum error is now reduced from 1ms (50%) to 15.63us (0.78% of 2ms).
• If DEBOUNCE is between 5 and 8ms:
  • XXXXYYYY where XXXX is 0000 .. 1111, so 0 through 15, and YYYY the remaining fractions of a millisecond (here up to 1/16ms). We initialize the counter with YYYY as all ones, to approximate the target debounce as best as we can.
  • We can now detect the changing starting at DEBOUNCE + 0.0625ms.
  • The maximum error is now reduced from 1ms (12.5% at 8ms) to 62.5us (0.78% of 8ms).
• If DEBOUNCE is between 9 and 16ms:
  • XXXXXYYY where XXXXX is 00000 .. 11111, so 0 through 31, and YYY the remaining fractions of a millisecond (here up to 1/8ms)
  • We can now represent a maximum of DEBOUNCE + 0.125ms.
  • The maximum error is now reduced from 1ms (6.25% at 16ms) to 125us (0.78% of 16ms).

High precision timer and fast_timer_t

I need help figuring that one out for each specific platform, as some of them use event generation and bumping a counter 1 by 1, and that can't happen on every single cycle, of course.

However, barring platform limitations (and we can't get over those anyway), with our time now consisting of fractions of a millisecond, we can still reliably represent elapsed times between checks of up to:

• uint16_t: the clock will flip every 65536 ticks, so that gives us a maximum interval of 65535 >> scaling_factor ms. So if we're talking about using e.g. 7 bits for the timer fraction, 511ms. So as long as the timer subtraction intervals don't go above that, we should be good (and I would find it very weird if it did).
• uint32_t: the clock will flip every 4294967296 ticks, so with the same condition as above, we have a maximum interval of 33554432ms, or 559 minutes, which I think is enough for most people 🤡

Now it's up to figuring out how to get the high precision timer without killing the boards.

[andrebrait]

@drashna (tagging you just so you can maybe let me know who can take a better look at this and read my proposal / help with the HW part)

[andrebrait]

Closing this, as I have collected some evidence yesterday that showed that this does not actually happen or that, when it does, it's not significant.

[boessu]

I'm not quite sure that this has "not significant" effect. There are way too many reports in keyboard chatter on reddit on different QMK hardware that there is NO issue in debouncing. "Spacebar double tap, happening all 20 minutes or so" is a classic. Often reported on brown switches (Cherry or Gateron, doesn't really matter) Is there really no chance to have a look again on your proposal?

[andrebrait]

@boessu by all means, go ahead and check it, but at least on my boards (two versions of the Glorious GMMK Pro), I found that the evaluation happens at each millisecond anyways and never twice on the same millisecond nor skipping milliseconds. I don't know if that goes for every board, though.

And mine was pretty rudimentary debugging with printing information and whatnot. Perhaps more refined debugging could uncover other details.