Subject: [PATCH v2] Input: atkbd - make repeat period more accurate.

Subject: [PATCH v2] Input: atkbd - make repeat period more accurate.

[George Spelvin]

This replaces some inaccurate lookup tables with an exact
computation.  Although the diff adds source comments,
it shrinks binary size.  (By only 50 bytes, but hey.)

AT keyboard repeat rates are multiples of 1/240 second
expressed in a 0.2.3 bit floating point format.  That
is, possible values are ({8..15} << {0..3}) / 240 s.

In addition to a slightly inaccurate lookup table, the
old code would round up to the next repeat period.
E.g. to get a period of 9/60 = 0.15 seconds, you had to
ask for no more than 149 ms; if you asked for 150, it
would round up to 167.  The new code rounds to nearest.

User-visible changes to the repeat periods reported by EVIOCGREP:

Old	 37	109	116	149	182	232
Exact	 37.50	108.33	116.66	150.00	183.33	233.33
New	 38	108	117	150	183	233

Old	270	303	370	435	470
Exact	266.66	300.00	366.66	433.33	466.66
New	267	300	367	433	467

This does not bother utilities like kbdrate(8).

Signed-off-by: George Spelvin <linux@horizon.com>
---
 drivers/input/keyboard/atkbd.c |   47 +++++++++++++++++++++++++++++++----------------
 1 file changed, 31 insertions(+), 16 deletions(-)

(Resend since no response after several weeks.)

Now that I've tweaked it (v1 had an error in rounding near exponent
range boundaries), I think it's ready for merging upstream.

Dmitry, you seem to be the one constant name in all recent changes to
this file, so I'm sending it to you directly as well as linux-input.


One possible bug I observed in the code that calls this:

Users of the KDKBDREP ioctl seem to assume that it returns the actual
values set, but I'm not sure it really works that way; I don't think
the command to change the parameters makes its way through the event
queue and atkbd's schedule_delayed_work() to actually set dev->rep[]
to the rounded values before kbd_rate_helper returns them to userspace.

If desired, the fix that's most obvious to me would be to split this
function in two: perform the conversion to a command byte synchronously,
and only defer the actual ps2_command().

diff --git a/drivers/input/keyboard/atkbd.c b/drivers/input/keyboard/atkbd.c
index e05a2e7..3181b86 100644
--- a/drivers/input/keyboard/atkbd.c
+++ b/drivers/input/keyboard/atkbd.c
@@ -524,27 +524,42 @@ out:
 	return IRQ_HANDLED;
 }
 
+/*
+ * AT keyboard repeat rates are set using a 2-bit initial repeat delay
+ * (250, 500, 750 or 1000 ms), and a 5-bit repeat period.  The latter
+ * is a 0.2.3-bit floating-point number (no sign, 2-bit exponent, and
+ * 3-bit mantissa), encoding a value from 8/240 to 120/240 of second.
+ *
+ * Given the requested delay and period in milliseconds, round to the
+ * nearest representable value, and convert the rounded values back to
+ * milliseconds to report the chosen values.
+ */
 static int atkbd_set_repeat_rate(struct atkbd *atkbd)
 {
-	const short period[32] =
-		{ 33,  37,  42,  46,  50,  54,  58,  63,  67,  75,  83,  92, 100, 109, 116, 125,
-		 133, 149, 167, 182, 200, 217, 232, 250, 270, 303, 333, 370, 400, 435, 470, 500 };
-	const short delay[4] =
-		{ 250, 500, 750, 1000 };
-
 	struct input_dev *dev = atkbd->dev;
 	unsigned char param;
-	int i = 0, j = 0;
-
-	while (i < ARRAY_SIZE(period) - 1 && period[i] < dev->rep[REP_PERIOD])
-		i++;
-	dev->rep[REP_PERIOD] = period[i];
-
-	while (j < ARRAY_SIZE(delay) - 1 && delay[j] < dev->rep[REP_DELAY])
-		j++;
-	dev->rep[REP_DELAY] = delay[j];
+	unsigned exp = 3;	/* Period exponent */
+	int period;		/* Period mantissa */
+	int delay = clamp(dev->rep[REP_DELAY], 125, 1000);
+
+	/* AT kbd delay is {1..4} * 250 ms.  Round to 2 bits. */
+	delay = (delay + 125) / 250u;
+	/* Store actual value back */
+	dev->rep[REP_DELAY] = delay * 250;
+
+	/* AT kbd period is ({8..15} << {0..3}) / 240 s. */
+	period = clamp(dev->rep[REP_PERIOD], 33, 500);
+	/* Get correct exponent.  Split is at 258.333 ms */
+	while (period < 259) {
+		period <<= 1;
+		exp--;
+	}
+	/* Convert from 259..516 ms to 8..15 30ths of a second */
+	period = (period * 3 + 50) / 100u;
+	/* Store actual value back.  x * 1000 / 240 = x * 25 / 6 */
+	dev->rep[REP_PERIOD] = ((period << exp) * 25 + 3) / 6u;
 
-	param = i | (j << 5);
+	param = (delay - 1) << 5 | exp << 3 | (period - 8);
 	return ps2_command(&atkbd->ps2dev, &param, ATKBD_CMD_SETREP);
 }
 

[REPOST #2 PATCH v2] Input: atkbd - make repeat period more accurate.

[George Spelvin]

This replaces some inaccurate lookup tables with an exact
computation.  Although the diff adds source comments,
it shrinks binary size.  (By only 50 bytes, but hey.)

AT keyboard repeat rates are multiples of 1/240 second
expressed in a 0.2.3 bit floating point format.  That
is, possible values are ({8..15} << {0..3}) / 240 s.

In addition to a slightly inaccurate lookup table, the
old code would round up to the next repeat period.
E.g. to get a period of 9/60 = 0.15 seconds, you had to
ask for no more than 149 ms; if you asked for 150, it
would round up to 167.  The new code rounds to nearest.

User-visible changes to the repeat periods reported by EVIOCGREP:

Old	 37	109	116	149	182	232
Exact	 37.50	108.33	116.66	150.00	183.33	233.33
New	 38	108	117	150	183	233

Old	270	303	370	435	470
Exact	266.66	300.00	366.66	433.33	466.66
New	267	300	367	433	467

This does not bother utilities like kbdrate(8).

Signed-off-by: George Spelvin <linux@horizon.com>
---
 drivers/input/keyboard/atkbd.c |   47 +++++++++++++++++++++++++++++++----------------
 1 file changed, 31 insertions(+), 16 deletions(-)

Posted once 7 weeks ago and again 2 weeks ago.
So far, feedback has been crickets.
Since 3.5 is coming to a close and the 3.6 merge window is about
to open, I'd like to solicit *some* feedback of any sort with
increased urgency.


Now that I've tweaked it (v1 had an error in rounding near exponent
range boundaries), I think it's ready for merging upstream.


One possible bug I observed in the code that calls this:

Users of the KDKBDREP ioctl seem to assume that it returns the actual
values set, but I'm not sure it really works that way; I don't think
the command to change the parameters makes its way through the event
queue and atkbd's schedule_delayed_work() to actually set dev->rep[]
to the rounded values before kbd_rate_helper returns them to userspace.

If desired, the fix that's most obvious to me would be to split this
function in two: perform the conversion to a command byte synchronously,
and only defer the actual ps2_command().

diff --git a/drivers/input/keyboard/atkbd.c b/drivers/input/keyboard/atkbd.c
index e05a2e7..3181b86 100644
--- a/drivers/input/keyboard/atkbd.c
+++ b/drivers/input/keyboard/atkbd.c
@@ -524,27 +524,42 @@ out:
 	return IRQ_HANDLED;
 }
 
+/*
+ * AT keyboard repeat rates are set using a 2-bit initial repeat delay
+ * (250, 500, 750 or 1000 ms), and a 5-bit repeat period.  The latter
+ * is a 0.2.3-bit floating-point number (no sign, 2-bit exponent, and
+ * 3-bit mantissa), encoding a value from 8/240 to 120/240 of second.
+ *
+ * Given the requested delay and period in milliseconds, round to the
+ * nearest representable value, and convert the rounded values back to
+ * milliseconds to report the chosen values.
+ */
 static int atkbd_set_repeat_rate(struct atkbd *atkbd)
 {
-	const short period[32] =
-		{ 33,  37,  42,  46,  50,  54,  58,  63,  67,  75,  83,  92, 100, 109, 116, 125,
-		 133, 149, 167, 182, 200, 217, 232, 250, 270, 303, 333, 370, 400, 435, 470, 500 };
-	const short delay[4] =
-		{ 250, 500, 750, 1000 };
-
 	struct input_dev *dev = atkbd->dev;
 	unsigned char param;
-	int i = 0, j = 0;
-
-	while (i < ARRAY_SIZE(period) - 1 && period[i] < dev->rep[REP_PERIOD])
-		i++;
-	dev->rep[REP_PERIOD] = period[i];
-
-	while (j < ARRAY_SIZE(delay) - 1 && delay[j] < dev->rep[REP_DELAY])
-		j++;
-	dev->rep[REP_DELAY] = delay[j];
+	unsigned exp = 3;	/* Period exponent */
+	int period;		/* Period mantissa */
+	int delay = clamp(dev->rep[REP_DELAY], 125, 1000);
+
+	/* AT kbd delay is {1..4} * 250 ms.  Round to 2 bits. */
+	delay = (delay + 125) / 250u;
+	/* Store actual value back */
+	dev->rep[REP_DELAY] = delay * 250;
+
+	/* AT kbd period is ({8..15} << {0..3}) / 240 s. */
+	period = clamp(dev->rep[REP_PERIOD], 33, 500);
+	/* Get correct exponent.  Split is at 258.333 ms */
+	while (period < 259) {
+		period <<= 1;
+		exp--;
+	}
+	/* Convert from 259..516 ms to 8..15 30ths of a second */
+	period = (period * 3 + 50) / 100u;
+	/* Store actual value back.  x * 1000 / 240 = x * 25 / 6 */
+	dev->rep[REP_PERIOD] = ((period << exp) * 25 + 3) / 6u;
 
-	param = i | (j << 5);
+	param = (delay - 1) << 5 | exp << 3 | (period - 8);
 	return ps2_command(&atkbd->ps2dev, &param, ATKBD_CMD_SETREP);
 }
 

[REPOST #3 PATCH v2] Input: atkbd - make repeat period more accurate.

[George Spelvin]

This replaces some inaccurate lookup tables with an exact
computation.  Although the diff adds source comments,
it shrinks binary size.  (By only 50 bytes, but hey.)

AT keyboard repeat rates are multiples of 1/240 second
expressed in a 0.2.3 bit floating point format.  That
is, possible values are ({8..15} << {0..3}) / 240 s.

In addition to a slightly inaccurate lookup table, the
old code would round up to the next repeat period.
E.g. to get a period of 9/60 = 0.15 seconds, you had to
ask for no more than 149 ms; if you asked for 150, it
would round up to 167.  The new code rounds to nearest.

User-visible changes to the repeat periods reported by EVIOCGREP:

Old	 37	109	116	149	182	232
Exact	 37.50	108.33	116.66	150.00	183.33	233.33
New	 38	108	117	150	183	233

Old	270	303	370	435	470
Exact	266.66	300.00	366.66	433.33	466.66
New	267	300	367	433	467

This does not bother utilities like kbdrate(8).

Signed-off-by: George Spelvin <linux@horizon.com>
---
 drivers/input/keyboard/atkbd.c |   47 +++++++++++++++++++++++++++++++----------------
 1 file changed, 31 insertions(+), 16 deletions(-)

Now that 3.5 is out, I'm posting this for a FOURTH time,
hoping for some comments of any sort.


Now that I've tweaked it (v1 had an error in rounding near exponent
range boundaries), I think it's ready for merging upstream.


One possible bug I observed in the code that calls this:

Users of the KDKBDREP ioctl seem to assume that it returns the actual
values set, but I'm not sure it really works that way; I don't think
the command to change the parameters makes its way through the event
queue and atkbd's schedule_delayed_work() to actually set dev->rep[]
to the rounded values before kbd_rate_helper returns them to userspace.

If desired, the fix that's most obvious to me would be to split this
function in two: perform the conversion to a command byte synchronously,
and only defer the actual ps2_command().

diff --git a/drivers/input/keyboard/atkbd.c b/drivers/input/keyboard/atkbd.c
index e05a2e7..3181b86 100644
--- a/drivers/input/keyboard/atkbd.c
+++ b/drivers/input/keyboard/atkbd.c
@@ -524,27 +524,42 @@ out:
 	return IRQ_HANDLED;
 }
 
+/*
+ * AT keyboard repeat rates are set using a 2-bit initial repeat delay
+ * (250, 500, 750 or 1000 ms), and a 5-bit repeat period.  The latter
+ * is a 0.2.3-bit floating-point number (no sign, 2-bit exponent, and
+ * 3-bit mantissa), encoding a value from 8/240 to 120/240 of second.
+ *
+ * Given the requested delay and period in milliseconds, round to the
+ * nearest representable value, and convert the rounded values back to
+ * milliseconds to report the chosen values.
+ */
 static int atkbd_set_repeat_rate(struct atkbd *atkbd)
 {
-	const short period[32] =
-		{ 33,  37,  42,  46,  50,  54,  58,  63,  67,  75,  83,  92, 100, 109, 116, 125,
-		 133, 149, 167, 182, 200, 217, 232, 250, 270, 303, 333, 370, 400, 435, 470, 500 };
-	const short delay[4] =
-		{ 250, 500, 750, 1000 };
-
 	struct input_dev *dev = atkbd->dev;
 	unsigned char param;
-	int i = 0, j = 0;
-
-	while (i < ARRAY_SIZE(period) - 1 && period[i] < dev->rep[REP_PERIOD])
-		i++;
-	dev->rep[REP_PERIOD] = period[i];
-
-	while (j < ARRAY_SIZE(delay) - 1 && delay[j] < dev->rep[REP_DELAY])
-		j++;
-	dev->rep[REP_DELAY] = delay[j];
+	unsigned exp = 3;	/* Period exponent */
+	int period;		/* Period mantissa */
+	int delay = clamp(dev->rep[REP_DELAY], 125, 1000);
+
+	/* AT kbd delay is {1..4} * 250 ms.  Round to 2 bits. */
+	delay = (delay + 125) / 250u;
+	/* Store actual value back */
+	dev->rep[REP_DELAY] = delay * 250;
+
+	/* AT kbd period is ({8..15} << {0..3}) / 240 s. */
+	period = clamp(dev->rep[REP_PERIOD], 33, 500);
+	/* Get correct exponent.  Split is at 258.333 ms */
+	while (period < 259) {
+		period <<= 1;
+		exp--;
+	}
+	/* Convert from 259..516 ms to 8..15 30ths of a second */
+	period = (period * 3 + 50) / 100u;
+	/* Store actual value back.  x * 1000 / 240 = x * 25 / 6 */
+	dev->rep[REP_PERIOD] = ((period << exp) * 25 + 3) / 6u;
 
-	param = i | (j << 5);
+	param = (delay - 1) << 5 | exp << 3 | (period - 8);
 	return ps2_command(&atkbd->ps2dev, &param, ATKBD_CMD_SETREP);
 }
 

Re: [REPOST #3 PATCH v2] Input: atkbd - make repeat period more accurate.

[Dmitry Torokhov]

Hi George,

On Sat, Jul 21, 2012 at 11:42:28PM -0400, George Spelvin wrote:
> This replaces some inaccurate lookup tables with an exact
> computation.  Although the diff adds source comments,
> it shrinks binary size.  (By only 50 bytes, but hey.)
> 
> AT keyboard repeat rates are multiples of 1/240 second
> expressed in a 0.2.3 bit floating point format.  That
> is, possible values are ({8..15} << {0..3}) / 240 s.

OK.

> 
> In addition to a slightly inaccurate lookup table, the
> old code would round up to the next repeat period.
> E.g. to get a period of 9/60 = 0.15 seconds, you had to
> ask for no more than 149 ms; if you asked for 150, it
> would round up to 167.

This works as intended - it was designed to never have faster than
requested.

>  The new code rounds to nearest.
> 
> User-visible changes to the repeat periods reported by EVIOCGREP:
> 
> Old	 37	109	116	149	182	232
> Exact	 37.50	108.33	116.66	150.00	183.33	233.33
> New	 38	108	117	150	183	233
> 
> Old	270	303	370	435	470
> Exact	266.66	300.00	366.66	433.33	466.66
> New	267	300	367	433	467
> 
> This does not bother utilities like kbdrate(8).
> 
> Signed-off-by: George Spelvin <linux@horizon.com>

I am sorry but I have to ask - is this your real name?

> ---
>  drivers/input/keyboard/atkbd.c |   47 +++++++++++++++++++++++++++++++----------------
>  1 file changed, 31 insertions(+), 16 deletions(-)
> 
> Now that 3.5 is out, I'm posting this for a FOURTH time,
> hoping for some comments of any sort.
> 
> 
> Now that I've tweaked it (v1 had an error in rounding near exponent
> range boundaries), I think it's ready for merging upstream.
> 
> 
> One possible bug I observed in the code that calls this:
> 
> Users of the KDKBDREP ioctl seem to assume that it returns the actual
> values set, but I'm not sure it really works that way; I don't think
> the command to change the parameters makes its way through the event
> queue and atkbd's schedule_delayed_work() to actually set dev->rep[]
> to the rounded values before kbd_rate_helper returns them to userspace.
> 
> If desired, the fix that's most obvious to me would be to split this
> function in two: perform the conversion to a command byte synchronously,
> and only defer the actual ps2_command().

Yes, I agree, this is a problem.

Thanks.

-- 
Dmitry

Re: [REPOST #3 PATCH v2] Input: atkbd - make repeat period more accurate.

[George Spelvin]

Thanks for the response!  I'd been checking mailing list archive sites
to see if my submissions were making it out to the list.

>> In addition to a slightly inaccurate lookup table, the
>> old code would round up to the next repeat period.
>> E.g. to get a period of 9/60 = 0.15 seconds, you had to
>> ask for no more than 149 ms; if you asked for 150, it
>> would round up to 167.

> This works as intended - it was designed to never have faster than
> requested.

The old code didn't do *that* correctly, either.  If you asked for 370
or 470 ms, it would give you 366.66 or 466.66 ms, respectively.

I can amend the code to do the same, but this leads to some questions:

Should the reported values be rounded down so that setting the repeat
period to the reported value is always safe?  Or should it allow rounding
down by <= 0.5 ms, so that asking for 117 ms will give you 166.66
without complaint?

And what do you do if the requested delay or period is longer than can
be supported (1000 and 500 ms, respectively)?

Finally, is this rounding documented clearly anywhere?  I thought rounding
to nearest gave the least surprising results for someone using various
slightly-inaccurate lists of the repeatable keyboard rates.  Including,
particularly, the previous code's values.

>> Signed-off-by: George Spelvin <linux@horizon.com>

> I am sorry but I have to ask - is this your real name?

Well, it's meant to be an obvious pen name, but since I use it
consistently and live in a common-law country, it's a "real"
as any other.

>> One possible bug I observed in the code that calls this:
>> 
>> Users of the KDKBDREP ioctl seem to assume that it returns the actual
>> values set, but I'm not sure it really works that way; I don't think
>> the command to change the parameters makes its way through the event
>> queue and atkbd's schedule_delayed_work() to actually set dev->rep[]
>> to the rounded values before kbd_rate_helper returns them to userspace.
>> 
>> If desired, the fix that's most obvious to me would be to split this
>> function in two: perform the conversion to a command byte synchronously,
>> and only defer the actual ps2_command().

> Yes, I agree, this is a problem.

I was trying to start simple, since this is a separate issue,
but I could make an attempt at this fix, too.

The *big* problsm is what if there's a peripheral that actually requires
a USB transaction to set the rate before being able to determine what
the rounded rate to report is, it'll require a major overhaul of the
in-kernel interfaces.


Another thing that would be possible is supporting an arbitrary repeat
rate, as long as it's slower than the maximum autorepeat rate.  Just set
the hardware repeat slightly faster than the software repeat rate and
buffer the autorepeat reports until the correct software-repeat time.

I don't know if it's worth bothering, though.

Re: [REPOST #3 PATCH v2] Input: atkbd - make repeat period more accurate.

[Dmitry Torokhov]

On Thu, Jul 26, 2012 at 11:15:24AM -0400, George Spelvin wrote:
> Thanks for the response!  I'd been checking mailing list archive sites
> to see if my submissions were making it out to the list.
> 
> >> In addition to a slightly inaccurate lookup table, the
> >> old code would round up to the next repeat period.
> >> E.g. to get a period of 9/60 = 0.15 seconds, you had to
> >> ask for no more than 149 ms; if you asked for 150, it
> >> would round up to 167.
> 
> > This works as intended - it was designed to never have faster than
> > requested.
> 
> The old code didn't do *that* correctly, either.  If you asked for 370
> or 470 ms, it would give you 366.66 or 466.66 ms, respectively.
> 
> I can amend the code to do the same, but this leads to some questions:
> 
> Should the reported values be rounded down so that setting the repeat
> period to the reported value is always safe?  Or should it allow rounding
> down by <= 0.5 ms, so that asking for 117 ms will give you 166.66
> without complaint?
> 
> And what do you do if the requested delay or period is longer than can
> be supported (1000 and 500 ms, respectively)?
> 
> Finally, is this rounding documented clearly anywhere?  I thought rounding
> to nearest gave the least surprising results for someone using various
> slightly-inaccurate lists of the repeatable keyboard rates.  Including,
> particularly, the previous code's values.

I do not believe rounding is documented anywhere; the rates are
mentioned in kbdrate manpage.

Frankly at this time I'd just leave this all as is since there were no
complaints from users about repeat rates on keyboards and most clients
(X) implement their own, software-based, rate control.

> 
> >> Signed-off-by: George Spelvin <linux@horizon.com>
> 
> > I am sorry but I have to ask - is this your real name?
> 
> Well, it's meant to be an obvious pen name,

I do not think it is that obvious to anyone who is not living in the US.
The only reason I paid attention to the name is I recognized your e-mail
from LKML as one never signing your name.

> but since I use it
> consistently and live in a common-law country, it's a "real"
> as any other.

I am not sure whether common law countries allow anyone pick any name of
their choosing and use it as their legal name; I know that we had to
refuse submission from another developer wishing to use a pen name
(HDAPS driver).

> 
> >> One possible bug I observed in the code that calls this:
> >> 
> >> Users of the KDKBDREP ioctl seem to assume that it returns the actual
> >> values set, but I'm not sure it really works that way; I don't think
> >> the command to change the parameters makes its way through the event
> >> queue and atkbd's schedule_delayed_work() to actually set dev->rep[]
> >> to the rounded values before kbd_rate_helper returns them to userspace.
> >> 
> >> If desired, the fix that's most obvious to me would be to split this
> >> function in two: perform the conversion to a command byte synchronously,
> >> and only defer the actual ps2_command().
> 
> > Yes, I agree, this is a problem.
> 
> I was trying to start simple, since this is a separate issue,
> but I could make an attempt at this fix, too.
> 
> The *big* problsm is what if there's a peripheral that actually requires
> a USB transaction to set the rate before being able to determine what
> the rounded rate to report is, it'll require a major overhaul of the
> in-kernel interfaces.

Luckily we are using software based repeat on USB (and most other input
devices).

> 
> 
> Another thing that would be possible is supporting an arbitrary repeat
> rate, as long as it's slower than the maximum autorepeat rate.  Just set
> the hardware repeat slightly faster than the software repeat rate and
> buffer the autorepeat reports until the correct software-repeat time.
> 
> I don't know if it's worth bothering, though.

No, I do not think it's worth it as we have software-based repeat
implementation that allows arbitrary rates.

Thanks.

-- 
Dmitry