(Solved) Keyboard decoder logic

[Octacone]

Hello!

What would be the best approach for a keyboard decoder. I have one very specific concept in mind.
Couple of weeks ago I acquired all the scan code values myself.
It took me a while to write down every single key I found on my keyboard.

I have a structure that contains all the scan code values + corresponding characters + key names aka descriptions + booleans that state if that specific key is a keypad key.
Here it is:

Code: Select all

-snip-
	{0x9, '8', "Nine"},
	{0xA, '9', "Eight"},
	{0xB, '0', "Zero"},
	{0xC, '\'', "Question Mark"},
	{0xD, '+', "Times Plus"},
	{0xE, '\b', "Backspace"},
	{0x52, '\0', "Insert"},
	{0x47, '\0', "Home"},
	{0xE, '\0', "Page Up"},
	{0x45, '\0', "Keypad Lock"},
	{0x35, '/', "Slash"},
	{0x37, '*', "Times"},
	{0x4A, '-', "Minus"},
	{0xF, '\t', "Tab"},
	{0x10, 'q', "q"},
-snip-

Now, how to "decode" them? I know how to handle casual characters (123abc), but what about function keys, alt, shift, insert, delete, keypad etc...?
I need something like: shift + some key = another character. It is like really complex logic involved because I also need to keep an eye on characters such as enter, backspace, because they have to trigger some specific functions.
I tried iterating trough the entire list but it is not efficient and there are too many situations that need to be handled. Any logical help would be appreciated!

[Ch4ozz]

You build a table with all characters, the index is the (virtual?) keycode.
Alt, shift and control are offsets in your table.
Make sure someone cant get out of the table (index) by pressing all at the same time.
Now you put all of this into a keyboard layout file and thats it.

[Brendan]

Hi,

What would be the best approach for a keyboard decoder.

That depends a little on how you define "best" (most flexible, fastest, easiest, ...).

I would:

• Have "keyboard layout files" (up to one for each keyboard layout that exists) that contain tables and other metadata in a "standard for your OS" file format that you've researched and carefully designed
• Have a nice (graphical) utility that end users can use to create and edit "keyboard layout files"
• During keyboard driver initialisation; load and parse/pre-process the "keyboard layout file" (for whichever keyboard layout is being used) from file system

In the driver itself, I'd:

• Convert variable length scan-codes into some kind of fixed size integer "keycode" (that can be used for array indexing). Note that this can be done with a relatively simple state machine (if you let hardware determine your keycode format to make it easy to convert scan-code to keycode), but could also use the same state machine followed by a lookup table (where state machine creates "intermediate code" and the lookup table converts "intermediate code" into "keycode", so that you can define your keycode format however you like).
• Use the tables and other metadata from the "keyboard layout file" to handle any special keys (shift, capslock, etc) and to find the Unicode codepoint/s for a key (if any). Note that any table lookups are very fast (and don't involve searching or branches).

Note: I currently have a theory that it'd be nice to define "keycode" as (e.g.) an 8-bit unsigned integer where the lowest 5 bits determine the physical column of the key and the upper 3-bits determine the physical row of the key (so that you know that "(2<<5) | 8" is the 9th key on the left of the 3rd row). This would mean having the lookup table that converts "intermediate code" into "keycode" in the "keyboard layout file", and it would mean having many different keyboard layouts for (e.g.) "US QWERTY" reflecting different physical locations for some keys (e.g. the "media keys" are often different and/or in different locations for different "US QWERTY" keyboards, sometimes the "insert, delete, home, end, pageup, pagedown" group are arranged differently, etc). The benefit would be that it'd be easy to display exactly what the keyboard actually looks like (e.g. and highlight the right key in the right place in things like help systems and tutorials, etc). However I'm not sure if this idea is actually practical - it would involve a huge amount of work to create a huge number of "keyboard layout files", and it would increase end-user hassle (because end-user would have to choose their exact keyboard layout rather than just saying (e.g.) "US QWERTY" or having it auto-detected). However; it could be an optional thing; where you have "generic US QWERTY" (where keycode doesn't necessarily reflect the key's physical locations) plus specialised keyboard layout files (where keycode does reflex the key's physical location) if/when the user feels like setting that up.


Cheers,

Brendan

[Korona]

Most OS seem to separate key decoding from key handling. The keyboard driver just maps device scan codes (e.g. from PS2 or USB keyboards, mice, joysticks, remote controls etc.) to virtual key codes. Some other program (usually the composer or display server or some library inside each application) decides how these virtual key codes map to application input. Not putting that logic into the keyboard driver allows you to have different windows with different languages or complex input schemes (e.g. for Asian languages) that require multiple key presses per character and thus some application-specific state of the input box.

Virtual key codes could be structured like Brendan proposed or you could just have constants like:
KEY_A, KEY_B, ..., KEY_LSHIFT, KEY_SPACE, ...
where KEY_A does not mean that an A will be generated but that the key that is located at the same spot as the A of an English keyboard was pressed.

[osdever]

Hello. You can use three (or more, but it's the bare minimum) of key layouts: regular, with Shift pressed and with CapsLock ON.

Basically this is what you should do in your keyboard interrupt handler:

• Get the scancode from port 0x60
  Check if it's a modifier key, if it's Shift then use your layout for Shift until it gets released, if it's CapsLock use your layour for CapsLock until it gets toggled off, etc
  If it's not use correspondant key layout and push the character into the keyboard buffer

Your internal getchar should either wait for keyboard interrupt to fire (if buffer is empty) or just pop last pressed character.

I personally use this:

Code: Select all

typedef struct {
    uint8_t scancode;
    char chr; //Character it corresponds to.
} kybd_scancode;

static kybd_scancode regular_scancodes[] = {
  /* Numerical keys */
  {0x02, '1'}, {0x03, '2'}, {0x04, '3'}, {0x05, '4'}, {0x06, '5'}, {0x07, '6'}, {0x08, '7'}, {0x09, '8'}, {0x0A, '9'}, {0x0B, '0'}, 
  /* Some characters after numerical keys */
  {0x0C, '-'}, {0x0D, '='}, {0x0E, '\b'}, {0x0F, '\t'},
  /* Alphabet! */
  {0x10, 'q'}, {0x11, 'w'}, {0x12, 'e'}, {0x13, 'r'}, {0x14, 't'}, {0x15, 'y'}, {0x16, 'u'}, {0x17, 'i'}, {0x18, 'o'}, {0x19, 'p'}, {0x1A, '['}, {0x1B, ']'}, {0x1C, '\n'},
  {0x1E, 'a'}, {0x1F, 's'}, {0x20, 'd'}, {0x21, 'f'}, {0x22, 'g'}, {0x23, 'h'}, {0x24, 'j'}, {0x25, 'k'}, {0x26, 'l'}, {0x27, ';'}, {0x28, '\''}, {0x29, '`'}, 
  {0x2B, '\\'}, {0x2C, 'z'}, {0x2D, 'x'}, {0x2E, 'c'}, {0x2F, 'v'}, {0x30, 'b'}, {0x31, 'n'}, {0x32, 'm'}, {0x33, ','}, {0x34, '.'}, {0x35, '/'}, {0x37, '*'}, 
  {0x39, ' '}, {0x47, '7'}, {0x48, '8'}, {0x49, '9'}, {0x4A, '-'},
               {0x4B, '4'}, {0x4C, '5'}, {0x4D, '6'}, {0x4E, '+'},
               {0x4F, '1'}, {0x50, '2'}, {0x51, '3'},
               {0x52, '0'}, {0x53, '.'}, {0x00, '\0'}
};
static kybd_scancode uppercase_scancodes[] = {
  /* Numerical keys */
  {0x02, '1'}, {0x03, '2'}, {0x04, '3'}, {0x05, '4'}, {0x06, '5'}, {0x07, '6'}, {0x08, '7'}, {0x09, '8'}, {0x0A, '9'}, {0x0B, '0'}, 
  /* Some characters after numerical keys */
  {0x0C, '-'}, {0x0D, '='}, {0x0E, '\b'}, {0x0F, '\t'},
  /* Alphabet! */
  {0x10, 'Q'}, {0x11, 'W'}, {0x12, 'E'}, {0x13, 'R'}, {0x14, 'T'}, {0x15, 'Y'}, {0x16, 'U'}, {0x17, 'I'}, {0x18, 'O'}, {0x19, 'P'}, {0x1A, '['}, {0x1B, ']'}, {0x1C, '\n'},
  {0x1E, 'A'}, {0x1F, 'S'}, {0x20, 'D'}, {0x21, 'F'}, {0x22, 'G'}, {0x23, 'H'}, {0x24, 'J'}, {0x25, 'K'}, {0x26, 'L'}, {0x27, ';'}, {0x28, '\''}, {0x29, '`'}, 
  {0x2B, '\\'}, {0x2C, 'Z'}, {0x2D, 'X'}, {0x2E, 'C'}, {0x2F, 'V'}, {0x30, 'B'}, {0x31, 'N'}, {0x32, 'M'}, {0x33, ','}, {0x34, '.'}, {0x35, '/'}, {0x37, '*'}, 
  {0x39, ' '}, {0x47, '7'}, {0x48, '8'}, {0x49, '9'}, {0x4A, '-'},
               {0x4B, '4'}, {0x4C, '5'}, {0x4D, '6'}, {0x4E, '+'},
               {0x4F, '1'}, {0x50, '2'}, {0x51, '3'},
               {0x52, '0'}, {0x53, '.'}, {0x00, '\0'}
};
static kybd_scancode shift_modified_scancodes[] = {
  /* Numerical keys */
  {0x02, '!'}, {0x03, '@'}, {0x04, '#'}, {0x05, '$'}, {0x06, '%'}, {0x07, '^'}, {0x08, '&'}, {0x09, '*'}, {0x0A, '('}, {0x0B, ')'}, 
  /* Some characters after numerical keys */
  {0x0C, '_'}, {0x0D, '+'}, {0x0E, '\b'}, {0x0F, '\t'},
  /* Alphabet! */
  {0x10, 'Q'}, {0x11, 'W'}, {0x12, 'E'}, {0x13, 'R'}, {0x14, 'T'}, {0x15, 'Y'}, {0x16, 'U'}, {0x17, 'I'}, {0x18, 'O'}, {0x19, 'P'}, {0x1A, '{'}, {0x1B, '}'}, {0x1C, '\n'},
  {0x1E, 'A'}, {0x1F, 'S'}, {0x20, 'D'}, {0x21, 'F'}, {0x22, 'G'}, {0x23, 'H'}, {0x24, 'J'}, {0x25, 'K'}, {0x26, 'L'}, {0x27, ':'}, {0x28, '"'}, {0x29, '~'}, 
  {0x2B, '\\'}, {0x2C, 'Z'}, {0x2D, 'X'}, {0x2E, 'C'}, {0x2F, 'V'}, {0x30, 'B'}, {0x31, 'N'}, {0x32, 'M'}, {0x33, '<'}, {0x34, '>'}, {0x35, '?'}, {0x37, '*'}, 
  {0x39, ' '}, {0x47, '7'}, {0x48, '8'}, {0x49, '9'}, {0x4A, '-'},
               {0x4B, '4'}, {0x4C, '5'}, {0x4D, '6'}, {0x4E, '+'},
               {0x4F, '1'}, {0x50, '2'}, {0x51, '3'},
               {0x52, '0'}, {0x53, '.'}, {0x00, '\0'}
};

typedef struct {
    int lshift : 1;
    int rshift : 1;
    int lctrl  : 1;
    int rctrl  : 1;
    int numlk  : 1;
    int capslk : 1;
    int scrllk : 1;
} kybd_modifier_key_states;
static kybd_modifier_key_states modifier_keys;

static char keyboard_buffer[256] = {};
static uint8_t kybd_buffer_current_position = 0; //0 to 255
static void kybd_buffer_push(char value)
{
    if(kybd_buffer_current_position != 255)
        keyboard_buffer[kybd_buffer_current_position++] = value;
    else
    {
        printk("Keyboard buffer overflow! Keypresses will NOT be processed before buffer will be freed. User hit the keys randomly in Flash speed, system is too slow, or BPS monkeys just mistaken?");
        return;
    }
}
static char kybd_buffer_pop()
{
    if(kybd_buffer_current_position > 0)
        return keyboard_buffer[--kybd_buffer_current_position];
    else
        return 0; //we have nothing in the buffer
}

//Interrupt part of the keyboard driver.
volatile bool kbd_irq_fired=false;
void kbd_wait_irq()
{
    //if(kbd_irq_fired){while(kbd_irq_fired);return;}
    while(!kbd_irq_fired);
    kbd_irq_fired=false;
}

char kbd_scancode_convert(uint8_t scancode)
{
    if(modifier_keys.capslk)
    {
        for(int i=0; uppercase_scancodes[i].scancode != 0x00; i++)
            if(uppercase_scancodes[i].scancode == scancode)
              return uppercase_scancodes[i].chr;
        return 0;
    }
    else if(modifier_keys.lshift || modifier_keys.rshift)
    {
        for(int i=0; shift_modified_scancodes[i].scancode != 0x00; i++)
            if(shift_modified_scancodes[i].scancode == scancode)
              return shift_modified_scancodes[i].chr;
        return 0;
    }
    else {
        for(int i=0; regular_scancodes[i].scancode != 0x00; i++)
            if(regular_scancodes[i].scancode == scancode)
              return regular_scancodes[i].chr;
        return 0;
    }
}

void kbd_handler(struct regs *UNUSED(r))
{
    kbd_irq_fired=true;
    //We need to put every pressed printable key to the buffer.
    uint8_t scancode = inb(KBD_DATA);
    switch(scancode)
    {
        case KEY_LSHIFT_P: modifier_keys.lshift = 1; break;
        case KEY_RSHIFT_P: modifier_keys.rshift = 1; break;
        case KEY_LSHIFT_R: modifier_keys.lshift = 0; break;
        case KEY_RSHIFT_R: modifier_keys.rshift = 0; break;
        default: kybd_buffer_push(kbd_scancode_convert(scancode)); break;
    }
}

uint8_t kbd_getchar()
{
    char ret=0;
    while(!ret)
    {
        sleep(1);
        kbd_wait_irq();
        ret = kybd_buffer_pop();
    }
    return ret;
}

You can even use that code as long as you'll leave a disclaimer that it's my code

[Kevin]

A problem of both your and octocone's code is that you make the scancode part of the array contents, so you have to search the whole array for the right scancode. Instead of this, you should rather use the scancode as the array index, then you can directly access the right element.

I know how to handle casual characters (123abc), but what about function keys, alt, shift, insert, delete, keypad etc...?

For shift and Alt Gr, you just use a different translation table. The type for the table looks like this on tyndur;

Code: Select all

typedef struct keymap_entry {
    wchar_t normal;
    wchar_t shift;
    wchar_t altgr;
    wchar_t ctrl;
} keymap_entry_t;

extern keymap_entry_t keymap[128];

For non-printable things like insert, delete, etc. you need to find a different representation, usually a multibyte one. DOS used to use a '\0' byte and then a one-byte code for the key, nowadays it's more common to use some vt100-based escape code starting with '\033' (the escape character, sometimes written as ^[) and then a variable-length code to describe the key. For example, when I just do 'cat' in a Linux console and press the delete key, what I get on the screen is ^[[3~.

[Octacone]

Sorry for not responding, I was very busy.
@Brendan
I actually quite like your idea. Having some separate files could be handy + they could contain all the tables that my OS requires.
The problem is, I can't read or write files at the moment, don't have a system for that. Can I maybe use tar to load them?
I don't think I will be doing anything as complex as virtual scan codes. Every keyboard is physically different so there is no guarantee.

@Ch4ooz
All the scan codes I have are real. What do you mean by offsets in my table? Like using them to search for corresponding characters? Something like current_table[0xB]
would immediately return a corresponding character.

@Korona
I don't know about that because I don't want to mess around with physical keyboard keys. I want to build that "decoder" into my keyboard driver to make it as compact as possible.
I don't want applications to handle internal key combinations. Imagine somebody trying to code something a having to make an entire system just to handler keys.
English keyboard is not really suitable for me. That is like using a potato instead of an onion. I could make it default doe. Also @Brendan and @Korona since you really like
virtual keys, what about laptops?

@osdeverr
I am not going to user your code, where is fun in that? I really really like your idea of having separate tables for each special key. Also I could combine that with Brendan's file format idea.
Also I don't have anything similar to "getchar", my keyboard handler directly prints pressed characters and puts them into a buffer (shell buffer). Other than that I don't use any buffers.
Should I make a circular ring buffer? FIFO?

@Kevin
Yeah, I agree with you about different lookup tables. For non printable characters I use '\0'. I think that is what @Ch4ooz was talking about, something like current_table[0xB] would immediately return a corresponding
character. Cat + delete returns ^[[3~, tried it out.

Thanks for responding folks! I guess I know what to do now.

[Brendan]

Hi,

@Brendan
I actually quite like your idea. Having some separate files could be handy + they could contain all the tables that my OS requires.
The problem is, I can't read or write files at the moment, don't have a system for that. Can I maybe use tar to load them?
I don't think I will be doing anything as complex as virtual scan codes. Every keyboard is physically different so there is no guarantee.

It's not unusual (and for micro-kernel, almost impossible to avoid) for an OS's boot loader to load some form of "initial RAM disk" containing any files that the OS will need before it has file systems up and running.

In my case, this "initial RAM disk" is compressed; and contains the kernel/s (so boot loader can auto-select best kernel for computer, which is nice when booting from "generic live CD", etc); and can be used to speed up boot times (so less has to wait for disk and file system to be initialised and more can be started in parallel); and is used for a little more fault tolerance (in case critical files are deleted in the file system, they can be restored during boot from the copy in the "initial RAM disk") and for OS installation (to install critical files in a new/empty file system).


Cheers,

Brendan

[Octacone]

Hi,

@Brendan
I actually quite like your idea. Having some separate files could be handy + they could contain all the tables that my OS requires.
The problem is, I can't read or write files at the moment, don't have a system for that. Can I maybe use tar to load them?
I don't think I will be doing anything as complex as virtual scan codes. Every keyboard is physically different so there is no guarantee.

It's not unusual (and for micro-kernel, almost impossible to avoid) for an OS's boot loader to load some form of "initial RAM disk" containing any files that the OS will need before it has file systems up and running.

In my case, this "initial RAM disk" is compressed; and contains the kernel/s (so boot loader can auto-select best kernel for computer, which is nice when booting from "generic live CD", etc); and can be used to speed up boot times (so less has to wait for disk and file system to be initialised and more can be started in parallel); and is used for a little more fault tolerance (in case critical files are deleted in the file system, they can be restored during boot from the copy in the "initial RAM disk") and for OS installation (to install critical files in a new/empty file system).


Cheers,

Brendan

Thanks for responding! But first I need to get my keyboard driver sorted out so I can start working on that.



Right now I can detect control/shift/alt/caps-lock/scroll-lock/keypad-lock being pressed or released but I can't differentiate alt from alt gr. I don't know how to handle an escape sequence (0xE0).
When I try to do something like

Code: Select all

else if(scancode == 0xE0 & 0xB8)

nothing happens better said normal (left) alt release sequence gets detected. Normal alt works just fine, but I can't figure out 0xE0 handling.

Edit: fixed! It was && instead of &...

Edit 2: another problem: now if I press any other key (not letters or shift or control) I get "right alt released" message.

[Octacone]

Let me clear something out. Is this the way it works?

Code: Select all

if(scancode & 0x80)
{
    //handle key releases
}
else
{
    //handle key presses
}

[Brendan]

Hi,

Let me clear something out. Is this the way it works?

Code: Select all

if(scancode & 0x80)
{
    //handle key releases
}
else
{
    //handle key presses
}

If you're using "scancode set 1", then yes.

However I'd recommend using scancode set 2 instead; because this is the default (for the keyboard) and it's the only scancode set that is guaranteed to be supported by all PS/2 keyboards.

Note that the default (for BIOS) is for keyboard to use scancode set 2, and for the PS/2 controller to translate "scancode set 2" into "scancode set 1" if the keyboard happens to be plugged into the 1st PS/2 port. This translation should probably be disabled in the PS/2 controller; because it trashes data if the device in the 1st PS/2 port is not a keyboard, and means that you can use the same keyboard driver regardless of which port you plug keyboard into.


Cheers,

Brendan

[Octacone]

Hi,

Let me clear something out. Is this the way it works?

Code: Select all

if(scancode & 0x80)
{
    //handle key releases
}
else
{
    //handle key presses
}

If you're using "scancode set 1", then yes.

However I'd recommend using scancode set 2 instead; because this is the default (for the keyboard) and it's the only scancode set that is guaranteed to be supported by all PS/2 keyboards.

Note that the default (for BIOS) is for keyboard to use scancode set 2, and for the PS/2 controller to translate "scancode set 2" into "scancode set 1" if the keyboard happens to be plugged into the 1st PS/2 port. This translation should probably be disabled in the PS/2 controller; because it trashes data if the device in the 1st PS/2 port is not a keyboard, and means that you can use the same keyboard driver regardless of which port you plug keyboard into.


Cheers,

Brendan

My keyboard is an USB keyboard, which means that I don't use that port at all. When I checked all the scan codes I got, they corresponded to the first keyboard layout set. Doesn't disabling it mean that I will get a whole other set of key codes that I will have to map, bummer. Also what is the procedure for the second key code layout set (releasing and pressing detection).

Onto my current problem:

kbdissues.png (8.17 KiB) Viewed 6605 times

Note: that arrow is showing what happens when I press alt gr.
Relevant code:

Code: Select all

if(scancode & 0x80)
	{
		if(scancode == 0xAA || scancode == 0xB6) 
		{
			shift_down = false;
			TTY_Put_String("\nShift released!", 0x01);
		}
		else if(scancode == 0x9D || scancode == 0xE0 && 0x9D)
		{
			control_down = false;
			TTY_Put_String("\nControl released!", 0x02);
		}
		else if(scancode == 0xB8 && scancode != 0xE0 && 0xB8)
		{
			alt_down = false;
			TTY_Put_String("\nAlt released!", 0x03);
		}
		else if(scancode == 0xE0 && 0xB8)
		{
			alt_gr_down = false;
			TTY_Put_String("\nRight alt released!", 0x04);
		}
	}
	else
	{
		...
		else if(scancode == 0x2A || scancode == 0x36)
		{
			shift_down = true;
			TTY_Put_String("\nShift down!", 0x0A);
		}
		else if(scancode == 0x1D || scancode == 0xE0 && 0x1D)
		{
			control_down = true;
			TTY_Put_String("\nControl down!", 0x0B);
		}
		else if(scancode == 0x38 && scancode != 0xE0 && 0x38)
		{
			alt_down = true;
			TTY_Put_String("\nAlt down!", 0x0C);
		}
		else if(scancode == 0xE0 && 0x38)
		{
			alt_gr_down = true;
			TTY_Put_String("\nRight alt down!", 0x0D);
		}
	}

There must be something I missed! Am I handling those multi bytes the right way?

[dozniak]

Code: Select all

&& 0x38)

these logical ands seems very pointless because they are always true; why do you add '&& true)' to each if statement?

[MichaelFarthing]

if(scancode == 0x9D || scancode == 0xE0 && 0x9D)

This means if ((scancode is 0x9d) or ((scancode is 0xE0) and 0x9d))

which means:

if ((scancode is 0x9d) or ((scancode is 0xE0) and True)) // 0x9d is non zero and therefore true

which means:

if ((scancode is 0x9d) or (scancode is 0xE0))

HTH

[Octocontrabass]

My keyboard is an USB keyboard, which means that I don't use that port at all.

USB legacy support. Every keyboard is a PS/2 keyboard, at least until you start writing your USB drivers.

Also what is the procedure for the second key code layout set (releasing and pressing detection).

In scan code set 1, key releases are signaled using the scan code from the key press except with the MSB set instead of clear. In scan code set 2, key releases are signaled by prefixing the scan code with 0xF0. (For extended keys, the 0xF0 prefix follows the 0xE0 or 0xE1 prefix.)

Am I handling those multi bytes the right way?

You aren't handling multiple bytes at all.