byte aligning in serial communication

Question

So I am trying to define a communication protocol for serial communication, I want to be able to send 4 byte numbers to the device, but I'm unsure how to make sure that the device starts to pick it up on the right byte.

For instance if I want to send

0x1234abcd 0xabcd3f56 ...

how do I makes sure that the device doesn't start reading at the wrong spot and get the first word as:

0xabcdabcd

Is there a clever way of doing this? I thought of using a marker for the start of a message, but what if I want to send the number I choose as data?

Answer 1

netstring

For this application, perhaps the relatively simple "netstring" format is adequate.

For example, the text "hello world!" encodes as:

12:hello world!,

The empty string encodes as the three characters:

0:,

which can be represented as the series of bytes

'0' ':' ','

The word 0x1234abcd in one netstring (using network byte order), followed by the word 0xabcd3f56 in another netstring, encodes as the series of bytes

'\n' '4' ':' 0x12 0x34 0xab 0xcd ',' '\n'
'\n' '4' ':' 0xab 0xcd 0x3f 0x56 ',' '\n'

(The newline character '\n' before and after each netstring is optional, but makes it easier to test and debug).

frame synchronization

how do I makes sure that the device doesn't start reading at the wrong spot

The general solution to the frame synchronization problem is to read into a temporary buffer, hoping that we have started reading at the right spot. Later, we run some consistency checks on the message in the buffer. If the message fails the check, something has gone wrong, so we throw away the data in the buffer and start over. (If it was an important message, we hope that the transmitter will re-send it).

For example, if the serial cable is plugged in halfway through the first netstring, the receiver sees the byte string:

0xab 0xcd ',' '\n' '\n'  '4' ':' 0xab 0xcd 0x3f 0x56 ',' '\n'

Because the receiver is smart enough to wait for the ':' before expecting the next byte to be valid data, the receiver is able to ignore the first partial message and then receive the second message correctly.

In some cases, you know ahead of time what the valid message length(s) will be; that makes it even easier for the receiver to detect it has started reading at the wrong spot.

sending start-of-message marker as data

I thought of using a marker for the start of a message, but what if I want to send the number I choose as data?

After sending the netstring header, the transmitter sends the raw data as-is -- even if it happens to look like the start-of-message marker.

In the normal case, the reciever already has frame sync. The netstring parser has already read the "length" and the ":" header, so the netstring parser puts the raw data bytes directly into the correct location in the buffer -- even if those data bytes happen to look like the ":" header byte or the "," footer byte.

pseudocode

// netstring parser for receiver
// WARNING: untested pseudocode
// 2012-06-23: David Cary releases this pseudocode as public domain.

const int max_message_length = 9;
char buffer[1 + max_message_length]; // do we need room for a trailing NULL ?
long int latest_commanded_speed = 0;
int data_bytes_read = 0;

int bytes_read = 0;
int state = WAITING_FOR_LENGTH;

reset_buffer()
    bytes_read = 0; // reset buffer index to start-of-buffer
    state = WAITING_FOR_LENGTH;

void check_for_incoming_byte()
    if( inWaiting() ) // Has a new byte has come into the UART?
        // If so, then deal with this new byte.
        if( NEW_VALID_MESSAGE == state )
            // oh dear. We had an unhandled valid message,
            // and now another byte has come in.
            reset_buffer();
        char newbyte = read_serial(1); // pull out 1 new byte.
        buffer[ bytes_read++ ] = newbyte; // and store it in the buffer.
        if( max_message_length < bytes_read )
            reset_buffer(); // reset: avoid buffer overflow

        switch state:
            WAITING_FOR_LENGTH:
                // FIXME: currently only handles messages of 4 data bytes
                if( '4' != newbyte )
                    reset_buffer(); // doesn't look like a valid header.
                else
                    // otherwise, it looks good -- move to next state
                    state = WAITING_FOR_COLON;
            WAITING_FOR_COLON:
                if( ':' != newbyte )
                    reset_buffer(); // doesn't look like a valid header.
                else
                    // otherwise, it looks good -- move to next state
                    state = WAITING_FOR_DATA;
                    data_bytes_read = 0;
            WAITING_FOR_DATA:
                // FIXME: currently only handles messages of 4 data bytes
                data_bytes_read++;
                if( 4 >= data_bytes_read )
                    state = WAITING_FOR_COMMA;
            WAITING_FOR_COMMA:
                if( ',' != newbyte )
                    reset_buffer(); // doesn't look like a valid message.
                else
                    // otherwise, it looks good -- move to next state
                    state = NEW_VALID_MESSAGE;

void handle_message()
    // FIXME: currently only handles messages of 4 data bytes
    long int temp = 0;
    temp = (temp << 8) | buffer[2];
    temp = (temp << 8) | buffer[3];
    temp = (temp << 8) | buffer[4];
    temp = (temp << 8) | buffer[5];
    reset_buffer();
    latest_commanded_speed = temp;
    print( "commanded speed has been set to: " & latest_commanded_speed );
}

void loop () # main loop, repeated forever
    # then check to see if a byte has arrived yet
    check_for_incoming_byte();
    if( NEW_VALID_MESSAGE == state ) handle_message();
    # While we're waiting for bytes to come in, do other main loop stuff.
    do_other_main_loop_stuff();

more tips

When defining a serial communication protocol, I find it makes testing and debugging much easier if the protocol always uses human-readable ASCII text characters, rather than any arbitrary binary values.

frame synchronization (again)

I thought of using a marker for the start of a message, but what if I want to send the number I choose as data?

We already covered the case where the reciever already has frame sync. The case where the receiver does not yet have frame sync is pretty messy.

The simplest solution is for the transmitter to send a series of harmless bytes (perhaps newlines or space characters), the length of the maximum possible valid message, as a preamble just before each netstring. No matter what state the receiver is in when the serial cable is plugged in, those harmless bytes eventually drive the receiver into the "WAITING_FOR_LENGTH" state. And then when the tranmitter sends the packet header (length followed by ":"), the receiver correctly recognizes it as a packet header and has recovered frame sync.

(It's not really necessary for the transmitter to send that preamble before every packet. Perhaps the transmitter could send it for 1 out of 20 packets; then the receiver is guaranteed to recover frame sync in 20 packets (usually less) after the serial cable is plugged in).

other protocols

Other systems use a simple Fletcher-32 checksum or something more complicated to detect many kinds of errors that the netstring format can't detect ( a, b ), and can synchronize even without a preamble.

Many protocols use a special "start of packet" marker, and use a variety of "escaping" techniques to avoid actually sending a literal "start of packet" byte in the transmitted data, even if the real data we want to send happens to have that value. ( Consistent Overhead Byte Stuffing, bit stuffing, quoted-printable and other kinds of binary-to-text encoding, etc.).

Those protocols have the advantage that the reciever can be sure that when we see the "start of packet" marker, it is the actual start of packet (and not some data byte that coincidentally happens to have the same value). This makes handling loss of synchronization much easier -- simply discard bytes until the next "start of packet" marker.

Many other formats, including the netstring format, allow any possible byte value to be transmitted as data. So receivers have to be smarter about handling the start-of-header byte that might be an actual start-of-header, or might be a data byte -- but at least they don't have to deal with "escaping" or the surprisingly large buffer required, in the worst case, to hold a "fixed 64-byte data message" after escaping.

Choosing one approach really isn't any simpler than the other -- it just pushes the complexity to another place, as predicted by waterbed theory.

Would you mind skimming over the discussion of various ways of handling the start-of-header byte, including these two ways, at the Serial Programming Wikibook, and editing that book to make it better?

Answer 2

Why not send a start-of-message byte followed by a length-of-data byte if you know how big the data is going to be?

Alternatively, do as other binary protocols and only send fixed sizes of packages with a fixed header. Say that you will only send 4 bytes, then you know that you'll have one or more bytes of header before the actual data content.

Edit: I think you're misunderstanding me. What I mean is that the client is supposed to always regard bytes as either header or data, not based on value but rather based on the position in the stream. Say you're sending four bytes of data, then one byte would be the header byte.

+-+-+-+-+-+
|H|D|D|D|D|
+-+-+-+-+-+

The client would then be a pretty basic state machine, along the lines of:

int state = READ_HEADER;
int nDataBytesRead = 0;
while (true) {
  byte read = readInput();
  if (state == READ_HEADER) {
    // process the byte as a header byte
    state = READ_DATA;
    nDataBytesRead = 0;
  } else {
    // Process the byte as incoming data
    ++nDataBytesRead;
    if (nDataBytesRead == 4) 
    {
      state = READ_HEADER;
    }
  }
} 

The thing about this setup is that what determines if the byte is a header byte is not the actual content of a byte, but rather the position in the stream. If you want to have a variable number of data bytes, add another byte to the header to indicate the number of data bytes following it. This way, it will not matter if you are sending the same value as the header in the data stream since your client will never interpret it as anything but data.