Parsing a Circular Buffer

Question

I'm implementing a small Zigbee library for Atmel's XMEGA devices. The Zigbee radio communicates with the MCU using the internal USART.

When I started writing the library I was using the simple approach of a fixed array along with interrupts for received data. Once I had the complete command (I know I have a complete command because the Zigbee states the frame length - minus the starting delimiter and checksum at the end), I set a flag in the interrupt service routine and copied the array into another array in my main().

Once I had the array copied, another routine ZBProcessFrame takes over and parses the frame and takes appropriate action.

The potential issue with this approach is that while I'm copying the array another message could come and change this shared variable.

By reading online, it seems I can either switch off my interrupts while copying the array or I should use a circular buffer, as then I can avoid copying the array entirely. I've successfully implemented a 32 byte circular buffer but now my issue is, how do I tell where the actual data began and how many bytes have come since the starting delimiter. My ISR only has the following:

ISR(Receiver Interrupt)
{
     ring->add(USART_Data);
}

Should I check for the starting delimiter here and set a flag incase there's a valid command here? The main() can then look at the flag continuously and if raised, it implies there's a valid command present.

Is this a valid approach or should I look for an alternative?

Answer 1

The circular buffer is a good design. I would leave the ISR as simple as possible, like you have it. If your main is a super-loop then I would add a call to a new routine like ZBReceiveFrame, which reads the next available byte (up to all available bytes individually) from the ring buffer and processes it in a state-machine. For example, the first state expects the start-of-frame delimiter and advances to the next state when it's received. The next state receives and interprets the frame length. The next state receives the frame body and the final state validates the frame CRC (all just examples). The states could all be implemented within ZBReceiveFrame using a switch statement. The state variable used within ZBReceiveFrame should be static so that the state is remembered from one call to the next. When the final state identifies a valid frame it sets the flag to prompt main to call ZBProcessFrame. Whether ZBReceiveFrame processes one or all available chars depends on how time-critical is the other stuff in the main super-loop.

This technique creates loose coupling, which is desirable. The ISR is only responsible for receiving the byte into the ring buffer and has no knowledge of what a frame is. ZBReceiveFrame only knows how to read from the ring buffer and delimit a frame but doesn't know how to interpret the data. And ZBProcessFrame is responsible for interpreting the data within a frame but has no knowledge of the ring buffer.

Answer 2

Your circular buffer needs to have read and write positions. WR points to next empty space, and RD to oldest received byte.

But this means that you need to manipulate these 2 variables at the same time: RD should never exceed WR for example. And since you cannot do this with single instruction, you need to disable interrupts when either one is read or written.

I have usually done it like this:

• Have a putByte function which is used from interrupt routine. Nothing else is done from ISR.

• Have a getByte function which is used from main program. This function will temporarily disable interrupts. Returns special value (-1 or similar) if buffer is empty.

• On each main loop iteration, copy available bytes from circular buffer to main buffer. Check received data after circular buffer is empty, or main buffer is full. If there is not enough bytes, copy more on next main loop iteration. Otherwise, process frame.

Time in ISR should be short (only copy bytes to circular buffer), and time blocking ISR should be short (no error checking when reading circular buffer, only copy to main buffer)