I have been debating someone recently about whether physical keyboards are faster than touchscreen keyboards. I have a lot of CS knowledge, but not a lot of Android knowledge. Therefore, during this debate, I have been reading up on how the Android system processes touchscreen events into keyboard events[1]. At this point, my understanding is this:

  • With a physical keyboard, the keyboard hardware itself can send a scancode that can be translated to an actual keycode at the kernal level through a simple lookup.
  • With a touchscreen, the hardware device is sending an X/Y position (along with some other data, but not a scancode), which then needs to usually be translated into a scancode by a previously exported virtual key map file. Then that scancode can be translated as expected.

This translation can happen either at the driver level or the software level. I cannot find any source code for driver level, but I found this Java file[2] which seems to do the translation at the software level. However, its implementation is absolutely not what I would expect. It seems as though the virtual key map file is loaded into memory as an ArrayList, where the VirtualKey is a simple static class with some helper methods. Essentially, the VirtualKey class has the bounding box and can determine if a given X/Y point would fall into that bounding box. When the system is checking a virtual key (findVirtualKey, line 786), it simply iterates through the list and uses a helper method to linearly search for the relevant key (it doesn't even bother to precompute the math on the bounding box, allowing it to happen each time).

Am I looking at the wrong place to understand the algorithm used in my phone's virtual key translation? I genuinely expected some kind of spatial data structure like a QuadTree. Is the dumb linear search on an arraylist more effective in practice despite the presumably terrible Big Oh? Have people tested the runtimes? Does anyone know where I can read more about this?

[1] https://source.android.com/devices/input/touch-devices

[2] https://android.googlesource.com/platform/frameworks/base/+/f0e697839a7de4eb080430fd83d44c0b436fdc88/services/java/com/android/server/KeyInputQueue.java

  • 1
    Android itself does not translate any key codes at all from display based keyboards. That is the job of the active keyboard app. You should better check the AOSP keyboard app. – Robert Dec 12 '20 at 22:39
  • Other than perhaps a difficulty in typing on a small virtual keyboard, dumb linear search is fine as long as the user cannot type more than 100 characters per second though..? Has this become a real problem? – Andrew T. Dec 13 '20 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.