OLD algorithms ( keyboard scan ) ...

Coders forum. Discuss techniques, swap code snippets, ask for help etc. relating to all forms of software development.
Post Reply
User avatar
gilesgoat
Sheepie Whore
Sheepie Whore
Posts: 27259
Joined: Wed Sep 03, 2003 7:54 am 0
Location: Monfalcone, Italy
Contact:

OLD algorithms ( keyboard scan ) ...

Post by gilesgoat »

"Because it's easy there's that lib that ..." ..

"NO NO I SWEAR it's REALLY EASY BECAUSE ... "

( it ISN'T )

"Have you EVER done THIS THING in particular ?" .. " .. erm .. NO .. but I HEARD that there's that lib .. "

( yes there's, it's "super crapola 0 documented" and does not do what I want plus it's from 2015 and apparently untouched ) ...

So .. that was more or less some conversation between me and my bro .. "that got me in getting my hands very dirty with something I kinda sworn I would have never touched" BUT I tought that "for this particular thing MAYBE it COULD be OK - cause 'everyone says it's so OK for' " ...

Must be said "I had already something better", some Cypress MCU/thing .. except that in that case "I cannot find a single worked sample about it" and "sure how hard it can be ?" .. .. REAL HARD if you don't know anything about it ..

So I have those Keyboard "too nice to be thrown away" .. and "too old to be of too much use" .. so .. hum .. "MAYBE I could add some <something> and be able to interface it via USB" ( I know NOTHING about USB , well I KNEW NOTHING until 4 days ago .. )

So my BRO SWEARS "use this is going to be so easy" .. made me buy for the increbile cheap sum of 7 quids or so an Arduino Pro Micro ..

Then made me install VS Code + PlattformIO which to be said "it's quite a thing considerting all the shit it does" ...

Then "flash a led" .. oh yes so trivial .. except that the "PRO MICRO" doesn't really have any "default LED" so takes a bit different effort ..

Then ok "read/write serial port", with NO interrupts .. really trivial .. ok .. we know that ..

So "how do you configure this as an HID device" .. ERM .. HUM .. ERM ... "I am not sure" .. "I heard there's this bootloader" ..

"What the heck does that bootloader ?" .. "I dunno"

"Who wrote it ?" .. "I dunno" ..

"Where's the source of it ?" .. "I have no idea ?"

"WHAT DOES IT REALLY AND HOW ?" .. "NO FUCKING IDEA" ..

So after MUCH reading the "So easy" turns out "NOT SO EASY AT ALL" and the "I don't want to read those 2000 pages of USB documentation" .. turns out "OK but you have to read at least 200 to get an idea about what's going on .. "

"That lib" .. "Is made using another much more complex lib" and it's not done for what I need ..

"Those numbers coming from thin air" that there are NOT those NOR these .. turns out they are defined in the "USB 1.1 HID specifications" ...

"That ()$*(£)$*" descriptor" .. "could not you made it more confusing that that and/or add some comments about" ...

"That other shit" .. turns out "kinda stolen from some Android sources" ...

So after MUCH searching/reading turns out that "OH it's SO SIMPLE there's LOT of stuff out there" .. "there's lot of stuff SO BADLY or NOTHING at all documented out there that you don't really know why it does what it does and how it does it" ..

SOME people "know the thing" but heck "they don't know how to explain it well" .. mind you "I could be one of them" ...

So after much stuff ( 2 days messing at late night ) studying deboucing algorithms and papers and stuff .. there's ONE THING I CANNOT FIND around.

I remember reading it "in some old Z80 coding book", probably, but can't find online it again ...

Does anyone rings a bell the "rows inversion and/or columns inversion" algorithm when scanning a keyboard matrix ?

IIRC has something to do with avoiding ( or trying to avoid ) the "ghost key" problem, I cannot remember how it works but I know it has something to do with first driving the rows as "outputs" and reading the columsn as "input" then reversing the thing but I cannot remember what else then has to be done and why it works ...

"Where I lost my head" in 2 nights and such it's been around this sort of shit, that hopefully I got it right, I still have to "validate" it and add an "USAGE PAGE OUTPUT" thing for the kb LEDs .. ( don't try to understand it, it's semi-voodoo, in essence it describes a data packet but how it gets 'in the right place with the correct meaning' I am not sure yet .. ) ..

Code: Select all

    USAGE_PAGE, GENERIC_DESKTOP_CONTROLS,
    USAGE, GENERIC_DEVICE_CONTROLS, // KEYBOARD_KEYPAD,
    COLLECTION, COLLECTION_APPLICATION,
    REPORT_ID, THE_REPORT_ID,
    USAGE_PAGE, KEYBOARD_KEYPAD,

    // this appear to say there are 8 bits of size '1' but with possible
    // logical value 0 or 1

    USAGE_MINIMUM, KEY_LEFTCTRL,
    USAGE_MAXIMUM, KEY_RIGHTMETA,
    LOGICAL_MINIMUM, 0x00,
    LOGICAL_MAXIMUM, 0x01,

    REPORT_SIZE, 0x01,
    REPORT_COUNT, 0x08,
    INPUT, 0x02,                    //   INPUT (Data,Var,Abs)
   
    REPORT_COUNT, 0x01,             //   This seems to be the reserved byte
    REPORT_SIZE, 0x08,              //   1 byte, 8 bits, constant var, absolute value 
    INPUT, 0x03,                    //   INPUT (Cnst,Var,Abs)
   
    REPORT_COUNT,0x06,              //   6 bytes report
    REPORT_SIZE, 0x08,              //   8 bits 
    LOGICAL_MINIMUM, KEY_NONE,
    LOGICAL_MAXIMUM, KEY_F24,
    USAGE_PAGE, KEYBOARD_KEYPAD,
    USAGE_MINIMUM, KEY_NONE,
    USAGE_MAXIMUM, KEY_F24,
    INPUT, 0x00,                    //   INPUT (Data,Ary,Abs)

    END_COLLECTION    
From the "little" I've seen so far I could say "whoever came out with the USB protocols/specifications was MAD !! " ..

Anyway if anyone remembers how that "rows inversions" works ...
Giles the billy goat
"Baa"
User avatar
gilesgoat
Sheepie Whore
Sheepie Whore
Posts: 27259
Joined: Wed Sep 03, 2003 7:54 am 0
Location: Monfalcone, Italy
Contact:

Re: OLD algorithms ( keyboard scan ) ...

Post by gilesgoat »

.. meanwhile .. bits by bits I am learning some more about USB protocols/etc. .. interesting ...
Giles the billy goat
"Baa"
User avatar
gilesgoat
Sheepie Whore
Sheepie Whore
Posts: 27259
Joined: Wed Sep 03, 2003 7:54 am 0
Location: Monfalcone, Italy
Contact:

Re: OLD algorithms ( keyboard scan ) ...

Post by gilesgoat »

From "not knowing a damn of all this never touched in my life" to "I have a shit of HW I can connect to Win10 and is seen as a HID keyboard that more or less works" ..

There's LOT of space for improvement, I still have to learn many things about USB/etc. I mean about how to handle the messages/"reports" I want some better configuration/etc. and be able to handle the LEDs status.

But it's something .. at least now I can say "I know a little about all this" .. interesting ..
Giles the billy goat
"Baa"
User avatar
toxibunny
Baaaaaaa!
Baaaaaaa!
Posts: 5906
Joined: Thu Jun 17, 2004 11:59 pm 0
Location: limb clock land

Re: OLD algorithms ( keyboard scan ) ...

Post by toxibunny »

When you do a keyboard matrix scan, you turn 1 pin of the ‘rows’ to active high, then check all the columns one by one. Then you move on to the next pin of the rows, turn that one high instead and check all the columns one by one. Ghosting is an false positive when more than one key is pressed at the same time. It can be completely eliminated by having a diode for each key, but that adds expense and is unnecessary most of the time for normal typing. There’s normally a diode per row and/or column, and some tweaking to make sure commonly used keys don’t clash.

Doing all this from memory and it was a while ago, so apologies if i’m wrong.

Is it possible that the ‘invert’ thing you’re talking about is that you go through the whole thing again, but drive the columns high this time, and do the detecting on the columns? And somehow that improves things? Maybe the ghosting shows up differently and you can detect and ignore it that way? Like I said, it’s been a while, and the ‘invert’ thing doesn’t ring any bells, but I’m guessing that’s what it might be…
I made a deviantart page.
'....The baron is a gay old rogue with an eye for the ladies....'
User avatar
gilesgoat
Sheepie Whore
Sheepie Whore
Posts: 27259
Joined: Wed Sep 03, 2003 7:54 am 0
Location: Monfalcone, Italy
Contact:

Re: OLD algorithms ( keyboard scan ) ...

Post by gilesgoat »

toxibunny wrote:When you do a keyboard matrix scan, you turn 1 pin of the ‘rows’ to active high, then check all the columns one by one. Then you move on to the next pin of the rows, turn that one high instead and check all the columns one by one. Ghosting is an false positive when more than one key is pressed at the same time. It can be completely eliminated by having a diode for each key, but that adds expense and is unnecessary most of the time for normal typing. There’s normally a diode per row and/or column, and some tweaking to make sure commonly used keys don’t clash.

Doing all this from memory and it was a while ago, so apologies if i’m wrong.

Is it possible that the ‘invert’ thing you’re talking about is that you go through the whole thing again, but drive the columns high this time, and do the detecting on the columns? And somehow that improves things? Maybe the ghosting shows up differently and you can detect and ignore it that way? Like I said, it’s been a while, and the ‘invert’ thing doesn’t ring any bells, but I’m guessing that’s what it might be…
Nobody puts those diodes "because it would increase costs too much", I did put some on the rows only because NOT having "open collector" ( or "open drain" ) outputs this would create otherwise a big problem when 2 keys the same column.

Actually "it's better to work with negated logic", you have let's say ( like in my case ) N columns as "pull up inputs" and you drive the rows with "a moving 0" ( i.e. '0' == selected row ) but without OC/diodes in the rows at least you'd get a proper short circuit if 2 keys the same column ar pressed because one could be in the row that has the '0' and one in the row that has the '1' connecting them together.

"Ghost key", so I read, is when you press two keys "on a corner of a matrix" and this creates a "phantom" 3rd key press that isn't there but electrically "it looks like it is".

This "inversion" as far as I remember was exactly saying something like :

1. drive the row, read the column
2. detect something
3. drive the column, read the row

But then I can't remember why/what you are supposed to do, someway by combining the two data you can figure out if it's the same key and/or if there's a phantom key in the middle.

Also, I AM NOT even sure ( I should analyze/think about ) if that's a problem that happens if "you read N columns at once" and/or does not happen if you read it one by one.

Suppose you have a matrix let's say 3 rows x 8 columns, you could to speed up things say "drive row X, read columns all as a single byte", if coulmns != 0xff then some key is pressed.

I think if you do that you get "some problem", if you read one column at time not, I am not sure.

What I am finding out is that debouncing/reading a kb/sending it to USB "it's a bit more complex than it sounds".

I got it so far working except I'll need to modify some of the "core USB lib" to be able to handle the "SET report" request, otherise I am not able to read when the PC wants to send me a "LED status packet" back.

Also I still haven't fully understood "how it really works or should work", in this case/example I have it's the thing that periodically sends a "status packet" to the PC ( which basically says "these keys are pressed" or not ) I was expecting the PC to poll at its own peace and say "give me a status" but that's not the case .. OR .. at least is "not the case in this case" I SUSPECT there's "some other mode" you can actually make it work the other way round.

Result is the speed at what you can keypress depends also on the frequency of "updates" you send to the PC but I also found out that "send too frequently" and "something goes crap on the USB" it seems also that "there's an USB message" that should set "an idle timer" or shit like that ..

In essence "what may look like a trivial problem" is FAR from being trivial, I've seen quite a few USB/SW write by others but they are all "so HW specific for a certain CPU/IDE/SDK" that are really hard to port withouth a 100% knowledge of the HW/IDE and USB protocol below.

For example I've seen a code where "at request of a certain 'setup packet' " ( that I am not sure if it happens only once and/or 'can happen anytime' and/or 'if there's some interrupt connected to that routine that someway gets called ') some stuff seems to reply '0' for saying 'no messages' and/or '0xff' to say 'there's going to be some function that in some mysterion way will be called any time you'll ask for me that'.

But in my "Platform.io stuff" I have only "one HID sample code written by someone in 2015" ( and probably never touched by anyone since ) that has a few "//TODO" in the middle left there with no explanations and such ..

So so far yeah it's a bit like "I kinda know what should happen I still have to figure out how to make it happen".

I am messing up/trying to understand sort of code to looks like this :

Code: Select all

/**
 * This function is called whenever we receive a setup request via USB.
 * \param data[8] eight bytes of data we received
 * \return number of bytes to use, or 0xff if usbFunctionWrite() should be
 * called
 */
uint8_t usbFunctionSetup(uint8_t data[8]) {
    usbRequest_t *rq = (void *)data;
    usbMsgPtr = reportBuffer;
    if ((rq->bmRequestType & USBRQ_TYPE_MASK) == USBRQ_TYPE_CLASS) {
        // class request type
        if (rq->bRequest == USBRQ_HID_GET_REPORT) {
            // wValue: ReportType (highbyte), ReportID (lowbyte)
            // we only have one report type, so don't look at wValue
            return sizeof(reportBuffer);
        } else if (rq->bRequest == USBRQ_HID_SET_REPORT) {
            if (rq->wLength.word == 1) {
                // We expect one byte reports
                expectReport = 1;
                return 0xff; // Call usbFunctionWrite with data
            }
        } else if (rq->bRequest == USBRQ_HID_GE ...

Problem is, that's made "for a totally different IDE/lib/etc/system" that it's not the one I use ..

( and even there it's absolutely NOT CLEAR AT ALL who/where/how that usbFunctionWrite() is called, what sets it, it's just there and someway gets called ! )

VS a thing like ..

Code: Select all

bool HID_::setup(USBSetup& setup)
{
	if (pluggedInterface != setup.wIndex) {
		return false;
	}

	uint8_t request = setup.bRequest;
	uint8_t requestType = setup.bmRequestType;

       ....


	if (requestType == REQUEST_HOSTTODEVICE_CLASS_INTERFACE)
	{
		if (request == HID_SET_PROTOCOL) {
			// The USB Host tells us if we are in boot or report mode.
			// This only works with a real boot compatible device.
			protocol = setup.wValueL;
			return true;
		}
		if (request == HID_SET_IDLE) {
			idle = setup.wValueL;
			return true;
		}
		if (request == HID_SET_REPORT)
		{
			//uint8_t reportID = setup.wValueL;
			//uint16_t length = setup.wLength;
			//uint8_t data[length];
			// Make sure to not read more data than USB_EP_SIZE.
			// You can read multiple times through a loop.
			// The first byte (may!) contain the reportID on a multreport.
			//USB_RecvControl(data, length);
		}
	}

	return false;
}


If I understood so far USB_EP_SIZE is actually 64 bytes is "the maximum size" a single USB packet can have, it would appear that in THIS case you use USB_RecvControl(data, length); which is a ( not sure ) non-blocking "USB read" to read that data packet ( which is actually 1 single byte of data ) but at this point I don't understand if that means that function is called "by magic" anytime an "USB SETUP" is sent and that function will lie there.

I have to investigate a bit all that.

Useless I say "documentation" found so far is "practically ZERO" ..

And just to get to that level of understanding of "what's going on here" I had to make a "mix and match" of different sources/projects because "other than the source like that you see" there's really no documentation of anything , you have to find it by your own.
Giles the billy goat
"Baa"
User avatar
gilesgoat
Sheepie Whore
Sheepie Whore
Posts: 27259
Joined: Wed Sep 03, 2003 7:54 am 0
Location: Monfalcone, Italy
Contact:

Re: OLD algorithms ( keyboard scan ) ...

Post by gilesgoat »

No kidding somewhere "more serious" once been "told off" when I mentioned some approach like "programming by nose" ..

Yet sometime "I am good at it" i.e. "make things works based on supposition/intuitions/etc." ..

So despite I don't know 100% how the heck this happens but "with a bit of this and a bit of that" I managed to make square pegs fit into round holes or such.

So "apparently" yes, any time you give a key like a capslock/numlock/stuff that would change an LED status you get a "setup message" or something that makes it call that HID_Setup() thing .. then again you get a 2 bytes "message" where the first byte is the "report ID" ( that in our case is 0x02) followed by a LED status byte according to these values :

Code: Select all

#define LED_NUM     0x01  ///< num LED on a boot-protocol keyboard
#define LED_CAPS    0x02  ///< caps LED on a boot-protocol keyboard
#define LED_SCROLL  0x04  ///< scroll LED on a boot-protocol keyboard
#define LED_COMPOSE 0x08  ///< compose LED on a boot-protocol keyboard
#define LED_KANA    0x10  ///< kana LED on a boot-protocol keyboard
So by adding a function there and a function here and a bit of debug and, most important THIS :

Code: Select all

    0x95, 0x05,   //   REPORT_COUNT (5)
    0x75, 0x01,   //   REPORT_SIZE (1)
    0x05, 0x08,   //   USAGE_PAGE (LEDs)
    0x19, 0x01,   //   USAGE_MINIMUM (Num Lock)
    0x29, 0x05,   //   USAGE_MAXIMUM (Kana)
    0x91, 0x02,   //   OUTPUT (Data,Var,Abs)
    0x95, 0x01,   //   REPORT_COUNT (1)
    0x75, 0x03,   //   REPORT_SIZE (3)
    0x91, 0x03,   //   OUTPUT (Cnst,Var,Abs)
It would appear I got "something that works" and reports keys and gets LEDs states ..

In theory now "I should be able to fix those broken KBs" :)

We'll see :) ..
Giles the billy goat
"Baa"
User avatar
gilesgoat
Sheepie Whore
Sheepie Whore
Posts: 27259
Joined: Wed Sep 03, 2003 7:54 am 0
Location: Monfalcone, Italy
Contact:

Re: OLD algorithms ( keyboard scan ) ...

Post by gilesgoat »

My "test board" now have 3 LEDs .. "Capslock" "Numlock" and "ScreenLock" .. and they all work according :D

.. so about that "inversion" I MAY have found something HERE : http://ww1.microchip.com/downloads/en/A ... oc2532.pdf

This story of "rows inversion" is shown in the flowchart at page 7 ..

.. yet .. I haven't fully understood what is supposed to do .. MAH ..

You'll never guess that reading a Keyboard is actually so tricky ...

My - C - code for the keyboard has about 500 lines .. plus another 100 for a certain class and if we consider all the USB/HID thing is probably another 1000 lines of code ..

Oh well .. it's USB after all ...
Giles the billy goat
"Baa"
User avatar
gilesgoat
Sheepie Whore
Sheepie Whore
Posts: 27259
Joined: Wed Sep 03, 2003 7:54 am 0
Location: Monfalcone, Italy
Contact:

Re: OLD algorithms ( keyboard scan ) ...

Post by gilesgoat »

Still a bit around this thing "in background" .. I am getting more and more to the conclusion that "keyboard scanning is some sort of obscure art" .. or at least it was in the 1980/90s or such ..

If you want to see "something out of this world" just read the VT100 Technical Manual chapter 4.4.1 onwards and you'll see "the madness" DEC engineers came from.

"OK" to use "some clock that was around" that turns out to be "some divisior of a master clock ALSO used for video synch signals" ..

But then you find out "the choice was NOT really random" because some routines/such are syncrhonized with video generation/intervals to be able to do "things with the kb while not doing things with the video" and such ..

But the "even more madness" comes to "how you put 4 bidirectional independent signals on a single wire ?" .. you invent some sort of "4 levels analog encoding" with 'modulated clock in it' so the data is actually bidirectional, independent and contains some clock that can be "recovered" from the receiver side ( the KB ) and used to re-transmit back some data and that also keeps into account the capacitance/lenght of the cable/etc. ...

But then ... why stop here ? A matrix of MxN keys are you going to send BYTES back ? "Are you mad ?" Too many bytes per scan ?

No you send ONE bit even N ms to start some counters that use the output both to address columns and rows and then a 8 to 1 demultiplxer that reads one bit at the time and a strange HW logic that I yet have to fully understand what it does ..

But then .. "no diodes are TOO EXPENSIVE we can't put those" .. so instead "you have some creepy algorithm" to understand false keys and rollovers and such ..

All this someway done by an 8080 cpu that meanwhile "manages all the rest" plus other communications to some serial ports at around 1Mhz cpu speed ... ( and I think maybe around 8K ram )

The keyboard has no CPU whatsoever, just a (particular) UART and some TTL logic ..

I am still trying to understand that chapter 4.4 in full to figure out exactly how to read that KB ...

They were "mad" back in the days :roll:
Giles the billy goat
"Baa"
Post Reply