ianhenderson.org / 2024 september 10

sending balanced events over a lossy channel

For a recent project, I found myself wanting to send keyboard events over UDP. Since UDP doesn't guarantee delivery, sending each event as a UDP message isn't sufficient: keystrokes can be lost. Even worse, if a key down event is transmitted but the corresponding key up event is lost, a key can get "stuck down" until the key is pressed again.

The solution I arrived at is to send a fixed-length queue of events in each UDP message. New events appear at the front of the queue, and older events are shifted off of the end. Event timestamps allow the receiver to tell which events it hasn't seen yet.

Key down events are treated specially—they remain in the queue until the key is released. This lets the receiver compare the keys it thinks are held with the keys that are held according to the incoming queue, dispatching key up events for any discrepancies. Keeping key down events in the queue prevents key up events from being sent while the key is still held.

The sender maintains a single queue. When a key is pressed, the sender adds the event to the queue and sends the queue as a UDP message. The steps for adding an event are described below. The process is complicated slightly by the need to ensure lone key down events are kept in the queue. The fixed queue length will be denoted N. The queue is initialized with events that are neither key up events nor key down events and that have a timestamp in the past.

The sender adds an event being added to the queue by following these steps:

1. Set the last shift index to N - 1.
2. While the last shift index is greater than or equal to zero and the event in the queue at the last shift index is a key down event with a different keycode than the keycode of the event being added:
   1. Subtract one from the last shift index.
3. Set the seen keycodes set to the empty set.
4. For each index i between 0 and N - 1:
   1. If the keycode of the event in the queue at i is in the seen keycodes set and i is greater than the last shift index, set the last shift index to i.
   2. Add the keycode of the event in the queue at i to the seen keycodes set.
5. If the last shift index is less than zero, there's no room left in the queue. Skip the rest of these steps—the event is dropped.
6. For each index i between 0 and the last shift index - 1:
   1. Shift the event in the queue at i over to index i + 1.
7. Set the event in the queue at 0 to the event being added.

On the receiving side, the previous queue is kept and compared with the incoming queue as it arrives over the network. To dispatch key events from the incoming queue, key up events are first generated for previously-held keys which do not have any events in the incoming queue. Then any newly-seen events in the incoming queue are dispatched.

More precisely, the receiver dispatches events by following these steps:

1. Set the previous timestamp to the timestamp of the event at index 0 in the previous queue.
2. Set the held keycodes set to the empty set.
3. Set the incoming keycodes set to the empty set.
4. For each index i between N - 1 and 0:
   1. If the event in the previous queue at i is a key down event, add its keycode to the held keycodes set.
   2. If the event in the previous queue at i is a key up event, remove its keycode from the held keycodes set.
   3. If the event in the incoming queue at i is either a key down event or a key up event, add its keycode to the incoming keycodes set.
5. For each keycode in the held keycodes set which is not in the incoming keycodes set:
   1. Dispatch a new key up event with that keycode and a timestamp equal to the previous timestamp.
6. For each index i between N - 1 and 0:
   1. If the event in the incoming queue at i is a key up event, its timestamp is greater than the previous timestamp, and its keycode is in the held keycodes set:
      1. Dispatch the event.
      2. Remove its keycode from the held keycodes set.
   2. If the event in the incoming queue at i is a key down event and its timestamp is greater than the previous timestamp:
      1. Dispatch the event.
      2. Add its keycode to the held keycodes set.
7. Set the previous queue to the incoming queue.

Note that it's possible for multiple key down events to be dispatched without a key up in between. This can happen when you hold down a key with key repeat enabled. If you want to have truly balanced events, check the held keycodes set before dispatching key down events. If the sender is always sending balanced events, this situation can only happen if the receiver missed a key up event, so it would also be possible to generate the missing event in this case.

Here is a JavaScript implementation you can play around with. Pressing keys will add them to the sender's buffer. The buffer is sent every 100ms.