Programming for Robotics 1, Chapter 2: Challenge 3 solution (a framed UART sensor with a CRC and resynchronisation)

Frame: 0xAA, high byte, low byte, CRC-8 of the two data bytes (polynomial 0x07, start value 0x00). Four bytes, so at 8N1:
        time per frame = 4 x 10 / baud            115 200 baud:  40 / 115 200 = 347.2 us         at most 115 200 / 40 = 2880 frames per second
                                                    9600 baud:   40 / 9600 = 4166.7 us            at most 9600 / 40 = 240 frames per second
        bytes arriving per 20 ms pass = baud / 10 x 0.020:   230.4 at 115 200 baud,   19.2 at 9600 baud
    A loop that reads 'whatever has arrived' each pass must therefore be ready for up to 57 frames per pass at 115 200 baud (230.4 / 4), and about 5 at 9600 baud.

Parser logic (one byte at a time, so it never waits):
        1. add the byte to a small buffer
        2. throw away bytes at the front until the front is 0xAA (the header)
        3. fewer than 4 bytes? return nothing yet
        4. CRC of bytes 1 and 2 equals byte 3?  then the frame is good: remove its 4 bytes and return the value (high x 256 + low)
        5. otherwise count a bad CRC, drop only the header byte, and go back to step 2 (the damaged frame's other bytes may contain the start of the next real frame)

Worked values:  1000 = 0x03E8, CRC-8 of (0x03, 0xE8) = 0xA9, so the frame is  AA 03 E8 A9.
The test stream is the frame for 1000, two noise bytes (0x13, 0x77), the frame for 2000 with one bit flipped, then the frame for 3000: 4 + 2 + 4 + 4 = 14 bytes.
Expected: the values 1000 and 3000, one bad CRC (the damaged frame), and 5 skipped bytes (the 2 noise bytes and the 3 leftover bytes of the damaged frame after its header was dropped).

The code was run, and the output below is what it printed:

CODE:
def crc8(data, poly=0x07, init=0x00):
    crc = init
    for byte in data:
        crc ^= byte
        for _ in range(8):
            if crc & 0x80:
                crc = ((crc << 1) ^ poly) & 0xFF
            else:
                crc = (crc << 1) & 0xFF
    return crc


def make_frame(value):
    hi, lo = value >> 8, value & 0xFF
    return bytes([0xAA, hi, lo, crc8([hi, lo])])


class FrameParser:
    """Frames of 4 bytes: 0xAA, high, low, CRC-8 of high and low. Feed it one byte at a time."""

    def __init__(self):
        self.buf = bytearray()
        self.bad_crc = 0
        self.skipped = 0

    def feed(self, byte):
        self.buf.append(byte)
        while True:
            while self.buf and self.buf[0] != 0xAA:        # hunt for a header: throw away anything else
                self.buf.pop(0)
                self.skipped += 1
            if len(self.buf) < 4:
                return None
            if crc8(self.buf[1:3]) == self.buf[3]:
                value = (self.buf[1] << 8) | self.buf[2]
                del self.buf[:4]
                return value
            self.bad_crc += 1                              # a false or damaged frame: drop its header, look again
            self.buf.pop(0)


stream = bytearray()
stream += make_frame(1000)
stream += bytes([0x13, 0x77])                              # two bytes of line noise
damaged = bytearray(make_frame(2000))
damaged[1] ^= 0x01                                         # one bit flipped in transit
stream += damaged
stream += make_frame(3000)

parser = FrameParser()
values = [v for v in (parser.feed(b) for b in stream) if v is not None]
print("stream of %d bytes -> values %s, bad CRC %d, bytes skipped %d" % (len(stream), values, parser.bad_crc, parser.skipped))
print("frame for 1000: %s" % make_frame(1000).hex())
for baud in (115200, 9600):
    t_frame = 4 * 10 / baud
    print("%6d baud: %.1f us per frame, at most %.0f frames/s, %.1f bytes arrive per 20 ms pass" % (baud, t_frame * 1e6, 1 / t_frame, baud / 10 * 0.020))
END CODE
OUTPUT:
stream of 14 bytes -> values [1000, 3000], bad CRC 1, bytes skipped 5
frame for 1000: aa03e8a9
115200 baud: 347.2 us per frame, at most 2880 frames/s, 230.4 bytes arrive per 20 ms pass
  9600 baud: 4166.7 us per frame, at most 240 frames/s, 19.2 bytes arrive per 20 ms pass
END OUTPUT

Check on method: the damaged frame was rejected, and the parser recovered by itself, with no reset and no waiting. The classic mistake is to throw away the whole 4-byte window on a bad CRC: if a good header happened to sit inside the damaged frame, that frame would be lost as well. Dropping only the header byte and searching again is slower to write and never loses a good frame. A one-byte header is weak (0xAA can also appear inside the data, and a rare accidental pass of the CRC is possible, 1 in 256 for a random 8-bit check), so real protocols add a length field and a longer check, and the program should still treat a value that jumps impossibly as suspect (Programming for Robotics 1 section 11).