[console] Update genkeymap to work with current databases

Rewrite genkeymap.pl in Python with added sanity checks, and update
the list of keyboard mappings to remove those no longer supported by
the underlying "loadkeys" tool.

Signed-off-by: Michael Brown <mcb30@ipxe.org>

2 files changed, 346 insertions, 238 deletions

diff --git a/src/util/genkeymap.pl b/src/util/genkeymap.pl
deleted file mode 100755
index 7a5024bf8..000000000
--- a/src/util/genkeymap.pl
+++ /dev/null
@@ -1,238 +0,0 @@
-#!/usr/bin/perl -w
-#
-# Copyright (C) 2011 Michael Brown <mbrown@fensystems.co.uk>.
-#
-# 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 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, write to the Free Software
-# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
-# 02110-1301, USA.
-
-=head1 NAME
-
-genkeymap.pl
-
-=head1 SYNOPSIS
-
-genkeymap.pl [options] <keymap name>
-
-Options:
-
-    -f,--from=<name>	Set BIOS keymap name (default "us")
-    -h,--help		Display brief help message
-    -v,--verbose	Increase verbosity
-    -q,--quiet		Decrease verbosity
-
-=cut
-
-# With reference to:
-#
-# http://gunnarwrobel.de/wiki/Linux-and-the-keyboard.html
-
-use Getopt::Long;
-use Pod::Usage;
-use strict;
-use warnings;
-
-use constant BIOS_KEYMAP => "us";
-use constant BKEYMAP_MAGIC => "bkeymap";
-use constant MAX_NR_KEYMAPS => 256;
-use constant NR_KEYS => 128;
-use constant KG_SHIFT => 0;
-use constant KG_ALTGR => 1;
-use constant KG_CTRL => 2;
-use constant KG_ALT => 3;
-use constant KG_SHIFTL => 4;
-use constant KG_KANASHIFT => 4;
-use constant KG_SHIFTR => 5;
-use constant KG_CTRLL => 6;
-use constant KG_CTRLR => 7;
-use constant KG_CAPSSHIFT => 8;
-use constant KT_LATIN => 0;
-use constant KT_FN => 1;
-use constant KT_SPEC => 2;
-use constant KT_PAD => 3;
-use constant KT_DEAD => 4;
-use constant KT_CONS => 5;
-use constant KT_CUR => 6;
-use constant KT_SHIFT => 7;
-use constant KT_META => 8;
-use constant KT_ASCII => 9;
-use constant KT_LOCK => 10;
-use constant KT_LETTER => 11;
-use constant KT_SLOCK => 12;
-use constant KT_SPKUP => 14;
-
-my $verbosity = 1;
-my $from_name = BIOS_KEYMAP;
-
-# Read named keymaps using "loadkeys -b"
-#
-sub read_keymaps {
-  my $name = shift;
-  my $keymaps = [];
-
-  # Generate binary keymap
-  open my $pipe, "-|", "loadkeys", "-b", $name
-      or die "Could not load keymap \"".$name."\": $!\n";
-
-  # Check magic
-  read $pipe, my $magic, length BKEYMAP_MAGIC
-      or die "Could not read from \"".$name."\": $!\n";
-  die "Bad magic value from \"".$name."\"\n"
-      unless $magic eq BKEYMAP_MAGIC;
-
-  # Read list of included keymaps
-  read $pipe, my $included, MAX_NR_KEYMAPS
-      or die "Could not read from \"".$name."\": $!\n";
-  my @included = unpack ( "C*", $included );
-  die "Missing or truncated keymap list from \"".$name."\"\n"
-      unless @included == MAX_NR_KEYMAPS;
-
-  # Read each keymap in turn
-  for ( my $keymap = 0 ; $keymap < MAX_NR_KEYMAPS ; $keymap++ ) {
-    if ( $included[$keymap] ) {
-      read $pipe, my $keysyms, ( NR_KEYS * 2 )
-	  or die "Could not read from \"".$name."\": $!\n";
-      my @keysyms = unpack ( "S*", $keysyms );
-      die "Missing or truncated keymap ".$keymap." from \"".$name."\"\n"
-	  unless @keysyms == NR_KEYS;
-      push @$keymaps, \@keysyms;
-    } else {
-      push @$keymaps, undef;
-    }
-  }
-
-  close $pipe;
-  return $keymaps;
-}
-
-# Translate keysym value to ASCII
-#
-sub keysym_to_ascii {
-  my $keysym = shift;
-
-  # Non-existent keysyms have no ASCII equivalent
-  return unless $keysym;
-
-  # Sanity check
-  if ( $keysym & 0xf000 ) {
-    warn "Unexpected keysym ".sprintf ( "0x%04x", $keysym )."\n";
-    return;
-  }
-
-  # Extract type and value
-  my $type = ( $keysym >> 8 );
-  my $value = ( $keysym & 0xff );
-
-  # Non-simple types have no ASCII equivalent
-  return unless ( ( $type == KT_LATIN ) || ( $type == KT_ASCII ) ||
-		  ( $type == KT_LETTER ) );
-
-  # High-bit-set characters cannot be generated on a US keyboard
-  return if $value & 0x80;
-
-  return $value;
-}
-
-# Translate ASCII to descriptive name
-#
-sub ascii_to_name {
-  my $ascii = shift;
-
-  if ( $ascii == 0x5c ) {
-    return "'\\\\'";
-  } elsif ( $ascii == 0x27 ) {
-    return "'\\\''";
-  } elsif ( ( $ascii >= 0x20 ) && ( $ascii <= 0x7e ) ) {
-    return sprintf ( "'%c'", $ascii );
-  } elsif ( $ascii <= 0x1a ) {
-    return sprintf ( "Ctrl-%c", ( 0x40 + $ascii ) );
-  } else {
-    return sprintf ( "0x%02x", $ascii );
-  }
-}
-
-# Produce translation table between two keymaps
-#
-sub translate_keymaps {
-  my $from = shift;
-  my $to = shift;
-  my $map = {};
-
-  foreach my $keymap ( 0, 1 << KG_SHIFT, 1 << KG_CTRL ) {
-    for ( my $keycode = 0 ; $keycode < NR_KEYS ; $keycode++ ) {
-      my $from_ascii = keysym_to_ascii ( $from->[$keymap]->[$keycode] )
-	  or next;
-      my $to_ascii = keysym_to_ascii ( $to->[$keymap]->[$keycode] )
-	  or next;
-      my $new_map = ( ! exists $map->{$from_ascii} );
-      my $update_map =
-	  ( $new_map || ( $keycode < $map->{$from_ascii}->{keycode} ) );
-      if ( ( $verbosity > 1 ) &&
-	   ( ( $from_ascii != $to_ascii ) ||
-	     ( $update_map && ! $new_map ) ) ) {
-	printf STDERR "In keymap %d: %s => %s%s\n", $keymap,
-	       ascii_to_name ( $from_ascii ), ascii_to_name ( $to_ascii ),
-	       ( $update_map ? ( $new_map ? "" : " (override)" )
-			     : " (ignored)" );
-      }
-      if ( $update_map ) {
-	$map->{$from_ascii} = {
-	  to_ascii => $to_ascii,
-	  keycode => $keycode,
-	};
-      }
-    }
-  }
-  return { map { $_ => $map->{$_}->{to_ascii} } keys %$map };
-}
-
-# Parse command-line options
-Getopt::Long::Configure ( 'bundling', 'auto_abbrev' );
-GetOptions (
-  'verbose|v+' => sub { $verbosity++; },
-  'quiet|q+' => sub { $verbosity--; },
-  'from|f=s' => sub { shift; $from_name = shift; },
-  'help|h' => sub { pod2usage ( 1 ); },
-) or die "Could not parse command-line options\n";
-pod2usage ( 1 ) unless @ARGV == 1;
-my $to_name = shift;
-
-# Read and translate keymaps
-my $from = read_keymaps ( $from_name );
-my $to = read_keymaps ( $to_name );
-my $map = translate_keymaps ( $from, $to );
-
-# Generate output
-( my $to_name_c = $to_name ) =~ s/\W/_/g;
-printf "/** \@file\n";
-printf " *\n";
-printf " * \"".$to_name."\" keyboard mapping\n";
-printf " *\n";
-printf " * This file is automatically generated; do not edit\n";
-printf " *\n";
-printf " */\n";
-printf "\n";
-printf "FILE_LICENCE ( PUBLIC_DOMAIN );\n";
-printf "\n";
-printf "#include <ipxe/keymap.h>\n";
-printf "\n";
-printf "/** \"".$to_name."\" keyboard mapping */\n";
-printf "struct key_mapping ".$to_name_c."_mapping[] __keymap = {\n";
-foreach my $from_sym ( sort { $a <=> $b } keys %$map ) {
-  my $to_sym = $map->{$from_sym};
-  next if $from_sym == $to_sym;
-  printf "\t{ 0x%02x, 0x%02x },\t/* %s => %s */\n", $from_sym, $to_sym,
-	 ascii_to_name ( $from_sym ), ascii_to_name ( $to_sym );
-}
-printf "};\n";
diff --git a/src/util/genkeymap.py b/src/util/genkeymap.py
new file mode 100755
index 000000000..1bb494f83
--- /dev/null
+++ b/src/util/genkeymap.py
@@ -0,0 +1,346 @@
+#!/usr/bin/env python3
+#
+# Copyright (C) 2022 Michael Brown <mbrown@fensystems.co.uk>.
+#
+# 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 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, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+# 02110-1301, USA.
+
+"""Generate iPXE keymaps"""
+
+from __future__ import annotations
+
+import argparse
+from collections import UserDict
+from collections.abc import Sequence, Mapping, MutableMapping
+from dataclasses import dataclass
+from enum import Flag, IntEnum
+import re
+import subprocess
+from struct import Struct
+import textwrap
+from typing import ClassVar, Optional
+
+
+class KeyType(IntEnum):
+    """Key types"""
+
+    LATIN = 0
+    FN = 1
+    SPEC = 2
+    PAD = 3
+    DEAD = 4
+    CONS = 5
+    CUR = 6
+    SHIFT = 7
+    META = 8
+    ASCII = 9
+    LOCK = 10
+    LETTER = 11
+    SLOCK = 12
+    DEAD2 = 13
+    BRL = 14
+    UNKNOWN = 0xf0
+
+
+class KeyModifiers(Flag):
+    """Key modifiers"""
+
+    NONE = 0
+    SHIFT = 1
+    ALTGR = 2
+    CTRL = 4
+    ALT = 8
+    SHIFTL = 16
+    SHIFTR = 32
+    CTRLL = 64
+    CTRLR = 128
+
+    @property
+    def complexity(self) -> int:
+        """Get complexity value of applied modifiers"""
+        if self == self.NONE:
+            return 0
+        if self == self.SHIFT:
+            return 1
+        if self == self.CTRL:
+            return 2
+        return 3 + bin(self.value).count('1')
+
+
+@dataclass
+class Key:
+    """A single key definition"""
+
+    keycode: int
+    """Opaque keycode"""
+
+    keysym: int
+    """Key symbol"""
+
+    modifiers: KeyModifiers
+    """Applied modifiers"""
+
+    ASCII_TYPES: ClassVar[set[KeyType]] = {KeyType.LATIN, KeyType.ASCII,
+                                           KeyType.LETTER}
+    """Key types with direct ASCII values"""
+
+    @property
+    def keytype(self) -> Optional[KeyType]:
+        """Key type"""
+        try:
+            return KeyType(self.keysym >> 8)
+        except ValueError:
+            return None
+
+    @property
+    def value(self) -> int:
+        """Key value"""
+        return self.keysym & 0xff
+
+    @property
+    def ascii(self) -> Optional[str]:
+        """ASCII character"""
+        if self.keytype in self.ASCII_TYPES:
+            value = self.value
+            char = chr(value)
+            if value and char.isascii():
+                return char
+        return None
+
+
+class KeyMapping(UserDict[KeyModifiers, Sequence[Key]]):
+    """A keyboard mapping"""
+
+    BKEYMAP_MAGIC: ClassVar[bytes] = b'bkeymap'
+    """Magic signature for output produced by 'loadkeys -b'"""
+
+    MAX_NR_KEYMAPS: ClassVar[int] = 256
+    """Maximum number of keymaps produced by 'loadkeys -b'"""
+
+    NR_KEYS: ClassVar[int] = 128
+    """Number of keys in each keymap produced by 'loadkeys -b'"""
+
+    KEY_BACKSPACE: ClassVar[int] = 14
+    """Key code for backspace
+
+    Keyboard maps seem to somewhat arbitrarily pick an interpretation
+    for the backspace key and its various modifiers, according to the
+    personal preference of the keyboard map transcriber.
+    """
+
+    KEY_NON_US: ClassVar[int] = 86
+    """Key code 86
+
+    Key code 86 is somewhat bizarre.  It doesn't physically exist on
+    most US keyboards.  The database used by "loadkeys" defines it as
+    "<>", while most other databases either define it as a duplicate
+    "\\|" or omit it entirely.
+    """
+
+    FIXUPS: ClassVar[Mapping[str, Mapping[KeyModifiers,
+                                          Sequence[tuple[int, int]]]]] = {
+        'us': {
+            # Redefine erroneous key 86 as generating "\\|"
+            KeyModifiers.NONE: [(KEY_NON_US, ord('\\'))],
+            KeyModifiers.SHIFT: [(KEY_NON_US, ord('|'))],
+            # Treat Ctrl-Backspace as producing Backspace rather than Ctrl-H
+            KeyModifiers.CTRL: [(KEY_BACKSPACE, 0x7f)],
+        },
+    }
+    """Fixups for erroneous keymappings produced by 'loadkeys -b'"""
+
+    @property
+    def unshifted(self):
+        """Basic unshifted key mapping"""
+        return self[KeyModifiers.NONE]
+
+    @property
+    def shifted(self):
+        """Basic shifted key mapping"""
+        return self[KeyModifiers.SHIFT]
+
+    @classmethod
+    def load(cls, name: str) -> KeyMapping:
+        """Load keymap using 'loadkeys -b'"""
+        bkeymap = subprocess.check_output(["loadkeys", "-u", "-b", name])
+        if not bkeymap.startswith(cls.BKEYMAP_MAGIC):
+            raise ValueError("Invalid bkeymap magic signature")
+        bkeymap = bkeymap[len(cls.BKEYMAP_MAGIC):]
+        included = bkeymap[:cls.MAX_NR_KEYMAPS]
+        if len(included) != cls.MAX_NR_KEYMAPS:
+            raise ValueError("Invalid bkeymap inclusion list")
+        keymaps = bkeymap[cls.MAX_NR_KEYMAPS:]
+        keys = {}
+        for modifiers in map(KeyModifiers, range(cls.MAX_NR_KEYMAPS)):
+            if included[modifiers.value]:
+                fmt = Struct('<%dH' % cls.NR_KEYS)
+                keymap = keymaps[:fmt.size]
+                if len(keymap) != fmt.size:
+                    raise ValueError("Invalid bkeymap map %#x" %
+                                     modifiers.value)
+                keys[modifiers] = [
+                    Key(modifiers=modifiers, keycode=keycode, keysym=keysym)
+                    for keycode, keysym in enumerate(fmt.unpack(keymap))
+                ]
+                keymaps = keymaps[len(keymap):]
+        if keymaps:
+            raise ValueError("Trailing bkeymap data")
+        for modifiers, fixups in cls.FIXUPS.get(name, {}).items():
+            for keycode, keysym in fixups:
+                keys[modifiers][keycode] = Key(modifiers=modifiers,
+                                               keycode=keycode, keysym=keysym)
+        return cls(keys)
+
+    @property
+    def inverse(self) -> MutableMapping[str, Key]:
+        """Construct inverse mapping from ASCII value to key"""
+        return {
+            key.ascii: key
+            # Give priority to simplest modifier for a given ASCII code
+            for modifiers in sorted(self.keys(), reverse=True,
+                                    key=lambda x: (x.complexity, x.value))
+            # Give priority to lowest keycode for a given ASCII code
+            for key in reversed(self[modifiers])
+            # Ignore keys with no ASCII value
+            if key.ascii
+        }
+
+
+class BiosKeyMapping(KeyMapping):
+    """Keyboard mapping as used by the BIOS"""
+
+    @property
+    def inverse(self) -> MutableMapping[str, Key]:
+        inverse = super().inverse
+        assert len(inverse) == 0x7f
+        assert all(x.modifiers in {KeyModifiers.NONE, KeyModifiers.SHIFT,
+                                   KeyModifiers.CTRL}
+                   for x in inverse.values())
+        return inverse
+
+
+@dataclass
+class KeyRemapping:
+    """A keyboard remapping"""
+
+    name: str
+    """Mapping name"""
+
+    source: KeyMapping
+    """Source keyboard mapping"""
+
+    target: KeyMapping
+    """Target keyboard mapping"""
+
+    @property
+    def ascii(self) -> MutableMapping[str, str]:
+        """Remapped ASCII key table"""
+        # Construct raw mapping from source ASCII to target ASCII
+        raw = {source: self.target[key.modifiers][key.keycode].ascii
+               for source, key in self.source.inverse.items()}
+        # Eliminate any null mappings, mappings that attempt to remap
+        # the backspace key, or identity mappings
+        table = {source: target for source, target in raw.items()
+                 if target
+                 and ord(source) != 0x7f
+                 and ord(target) != 0x7f
+                 and ord(source) != ord(target)}
+        # Recursively delete any mappings that would produce
+        # unreachable alphanumerics (e.g. the "il" keymap, which maps
+        # away the whole lower-case alphabet)
+        while True:
+            unreachable = set(table.keys()) - set(table.values())
+            delete = {x for x in unreachable if x.isascii() and x.isalnum()}
+            if not delete:
+                break
+            table = {k: v for k, v in table.items() if k not in delete}
+        # Sanity check: ensure that all numerics are reachable using
+        # the same shift state
+        digits = '1234567890'
+        unshifted = ''.join(table.get(x, x) for x in '1234567890')
+        shifted = ''.join(table.get(x, x) for x in '!@#$%^&*()')
+        if digits not in (shifted, unshifted):
+            raise ValueError("Inconsistent numeric remapping %s / %s" %
+                             (unshifted, shifted))
+        return dict(sorted(table.items()))
+
+    @property
+    def cname(self) -> str:
+        """C variable name"""
+        return re.sub(r'\W', '_', self.name) + "_mapping"
+
+    @staticmethod
+    def ascii_name(char: str) -> str:
+        """ASCII character name"""
+        if char == '\\':
+            name = "'\\\\'"
+        elif char == '\'':
+            name = "'\\\''"
+        elif char.isprintable():
+            name = "'%s'" % char
+        elif ord(char) <= 0x1a:
+            name = "Ctrl-%c" % (ord(char) + 0x40)
+        else:
+            name = "0x%02x" % ord(char)
+        return name
+
+    @property
+    def code(self) -> str:
+        """Generated source code"""
+        code = textwrap.dedent(f"""
+        /** @file
+         *
+         * "{self.name}" keyboard mapping
+         *
+         * This file is automatically generated; do not edit
+         *
+         */
+
+        FILE_LICENCE ( PUBLIC_DOMAIN );
+
+        #include <ipxe/keymap.h>
+
+        /** "{self.name}" keyboard mapping */
+        struct key_mapping {self.cname}[] __keymap = {{
+        """).lstrip() + ''.join(
+            '\t{ 0x%02x, 0x%02x },\t/* %s => %s */\n' % (
+                ord(source), ord(target),
+                self.ascii_name(source), self.ascii_name(target)
+            )
+            for source, target in self.ascii.items()
+        ) + textwrap.dedent("""
+        };
+        """).strip()
+        return code
+
+
+if __name__ == '__main__':
+
+    # Parse command-line arguments
+    parser = argparse.ArgumentParser(description="Generate iPXE keymaps")
+    parser.add_argument('--verbose', '-v', action='count', default=0,
+                        help="Increase verbosity")
+    parser.add_argument('layout', help="Target keyboard layout")
+    args = parser.parse_args()
+
+    # Load source and target keymaps
+    source = BiosKeyMapping.load('us')
+    target = KeyMapping.load(args.layout)
+
+    # Construct remapping
+    remap = KeyRemapping(name=args.layout, source=source, target=target)
+
+    # Output generated code
+    print(remap.code)