A Simple Serial Packetization Protocol - The Wire Protocol

Tue, Mar 29, 2016

I was having a chat with a friend the other day about reliable serial data transfer, and I want to share a scheme that has worked well for me in the past. It’s split into two layers: I’ll call them the “wire protocol” and the “command protocol”. One of the great things about this protocol is that it is really simple for a low-memory microcontroller to implement.

The wire protocol is used to encode the start and end of packets in the serial data stream. In this scheme, these are single bytes. You can use whatever you want, so long as it’s consistent on both ends. For the rest of this example, I’ll use 0x02 (“start of text” in ASCII) and 0x03 (“end of text”). Let’s say the packet you’re going to transmit is “Hello”. The resulting output is going to be:

0x02 H e l l o 0x03

Super simple! The microcontroller can sit and read bytes from the UART, and when it sees 0x02 it knows that a new packet is being received. There’s a problem with this scheme though: what to do when the packet contains 0x02 or 0x03? This would confuse the receiver, since they’ll be half-way through receiving a packet and will either terminate prematurely, or think that a new packet is starting.

The solution is an escape character. I’ll use ASCII ESC (0x1B). The escape character is used to indicate to the receiver that the next character should be used as-is and not be treated as a control character. This must be applied to any instances of the start byte, end byte, or escape byte in the data to be transmitted. A simple approach is to pass through the following character untouched. So transmitting a packet of

0x32 0x02 0x1B

would result in this output:

0x02 0x32 0x1B 0x02 0x1B 0x1B 0x03

That’s pretty decent, and straightforward to decode, but it makes me uncomfortable that 0x02 and 0x1B are transmitted multiple times, and have different meanings depending on where they are relative to escape bytes. One of the rules that I have about serial data streams is that it’s quite possible for them to be in an unknown state (e.g. a power glitch while a data stream is running, or someone bumps a cable, etc). If the microcontroller missed the first byte in this example, it would still lock on to the following start byte (0x02) and decide that a packet of (0x1B) had been transmitted.

A simple tweak to that algorithm is to give the escape character the following meaning: the byte that follows the escape character is the bitwise-not of the byte to be written. We still escape the same three characters (start, end, and escape), but they only ever appear in the data stream when they have their intended meaning. For reference, ~0x02 = 0xFD, ~0x03 = 0xFC, and ~0x1B = 0xE4. Going off the previous example, encoding:

0x32 0x02 0x1B

results in this output:

0x02 0x32 0x1B 0xFD 0x1B 0xE4 0x03

In this example, no matter where the receiver starts receiving, it will never inadvertently receive a start, end, or escape character unless the transmitted byte has that intended meaning. And that’s it!

Summary

To summarize, this protocol has 3 special bytes:

• A start byte (0x02) to indicate the start of a data packet
• An end byte (0x03) to indicate the end of a data packet
• An escape byte (0x1B), which is used when the data packet contains one of the three special bytes. The escape byte is followed by the bitwise-not of the special byte, to ensure that the special bytes only ever appear in the data stream in positions where their special behaviour is warranted.

Pseudocode

Here’s some C-ish pseudocode for a transmitter:

#define START_BYTE 0x02
#define END_BYTE 0x03
#define ESCAPE_BYTE 0x1B

void tx(char* buf, int len) {
  putchar_uart(START_BYTE);
  for(int i = 0; i < len; i++) {
    if((buf[i] == START_BYTE) || (buf[i] == END_BYTE) || (buf[i] == ESCAPE_BYTE)) {
      putchar_uart(ESCAPE_BYTE);
      putchar_uart(~buf[i]);
    } else {
      putchar_uart(buf[i]);
    }
  }
  putchar_uart(END_BYTE);
}

And here’s some receiver code:

int rx(char* buf, int maxlen) {
  int i = 0;
  bool started = false;
  bool flip_next = false;
  char c;

  while(1) {
    c = getc_uart();
    if (c == START_BYTE) {
      i = 0;
      started = true;
      continue;
    }
    if (c == END_BYTE) {
      if (started) {
        break;
      } else {
        continue;
      }   
    }
    if (c == ESCAPE_BYTE) {
      flip_next = true;
      continue;
    }
   
    if (flip_next) {
      c = ~c;
      flip_next = false;
    }
    buf[i] = c;
    i++;
    if (i == maxlen) { break; }
  }
  return i;
}

I just typed that in by hand and haven’t tried compiling it. Let me know if there’s something wrong with it.