Author Topic: Parsing UART packets / state machines / packed structs  (Read 7900 times)

0 Members and 1 Guest are viewing this topic.

Online uer166Topic starter

  • Frequent Contributor
  • **
  • Posts: 872
  • Country: us
Parsing UART packets / state machines / packed structs
« on: December 03, 2022, 10:35:21 pm »
I am in need to parse some UART packets in a format I have no control over. The format is something like:
|0x55|0xAA|LENGTH|ADDRESS|0x01|CMD|DATA0....DATAn|CHKSUM|.

The easiest way seems to be a switch/case state machine, to basically go byte by byte per invocation. It's to be called at a rate higher than the incoming bytes of course to not miss anything, or alternatively use the hardware 8-byte FIFO to call this every 8 bytes, reducing ISR rate. After a packet data is read and validated, it is then memcpy-d into a packed struct based on the command byte which defines the data format, therefore automatically getting the right bits in place. Something like:

Code: [Select]
/* Data structure declarations */
volatile struct BMS_batstat bms_batstat;

/* UART state machine state for reading/parsing packets */
static uint8_t length = 0;
static uint16_t chksum = 0;
static uint8_t cmdreq = 0;
static uint8_t databuf[255] = {0};
static uint8_t databuf_i = 0;

void BMS_UART_ParseData(void)
{
if(cmdreq == CMDREQ_BATSTAT)
{
memcpy(&bms_batstat, databuf, sizeof(bms_batstat));
}
else
{
// unknown packet, TODO
}
}

void BMS_UART_StateMachine_Rx(uint8_t rx)
{
switch(bms_uart_state)
{
case UART_wait_0x55:
if(rx == 0x55) { bms_uart_state = UART_wait_0xAA; } else { bms_uart_state = UART_wait_0x55; }
break;

case UART_wait_0xAA:
if(rx == 0xAA) { bms_uart_state = UART_read_length; } else { bms_uart_state = UART_wait_0x55; }
break;

case UART_read_length:
length = rx;
databuf_i = 0;
bms_uart_state = UART_wait_0x25;
break;

case UART_wait_0x25:
if(rx == 0x25) { bms_uart_state = UART_wait_0x01; } else { bms_uart_state = UART_wait_0x55; }
break;

case UART_wait_0x01:
if(rx == 0x01) {bms_uart_state = UART_read_cmdreq; } else { bms_uart_state = UART_wait_0x55; }
break;

case UART_read_cmdreq:
cmdreq = rx;
bms_uart_state = UART_read_data;
break;

case UART_read_data:
databuf[databuf_i] = rx;
databuf_i++;
if(databuf_i == (length - 2)) {bms_uart_state = UART_read_checksumLSB;} /* Data length without including extras */
break;

case UART_read_checksumLSB:
chksum = (uint16_t)rx;
bms_uart_state = UART_read_checksumMSB;

break;

case UART_read_checksumMSB:
chksum |= ((uint16_t)rx) << 8;

uint16_t chksum_data = 0;
chksum_data = length + 0x25 + 0x01 + cmdreq; /* Need to add extras to checksum */

/* Data length without including extras */
for(uint8_t i = 0; i < (length - 2); i++)
{
chksum_data += databuf[i];
}

if(chksum == (0xFFFF - chksum_data))
{
BMS_UART_ParseData();
}

bms_uart_state = UART_wait_0x55;
break;

default:
asm("bkpt");
break;
}
}

I've seen some implementations of such a state machine with function pointers, separating each state into a function, although I didn't think it was particularly readable or safe. Are there more ways to do this in a more obvious or maybe safe manner? The only complication I see here is the need to debug these variables in the foreground in a shell-like environment, and the packed structs are not atomic, therefore I need to unpack/copy all these variable into atomic types such as float or uint32_t so that there is no data consistency issues.
 

Offline krish2487

  • Frequent Contributor
  • **
  • Posts: 500
  • Country: dk
Re: Parsing UART packets / state machines / packed structs
« Reply #1 on: December 04, 2022, 08:02:25 am »
which mcu??
One approach I can think of is to use DMA to copy all the incoming data to a buffer and then invoke the parser once the buffer is full..
Then the parsing can happen at a much slower rate than byte invocation..
I dont know about other MCUs but STM32 have a UART IDLE line detection which is essentially an interrupt that fires if there is no data on the UART line for a clock cycle or two. This is nice because you dont need to know the length of the data you need to store.. just wait for the interrupt to fire, set a flag inside the ISR to trigger the parser and do the parsing in the main loop once you return from the ISR..
If god made us in his image,
and we are this stupid
then....
 

Offline Siwastaja

  • Super Contributor
  • ***
  • Posts: 8106
  • Country: fi
Re: Parsing UART packets / state machines / packed structs
« Reply #2 on: December 04, 2022, 09:22:56 am »
Some pseudocode (not tested), just to give idea how I have done this in recent times:

Code: [Select]
// .h
typedef struct PACK
{
   ...
} msg1_t;

typedef struct PACK
{
   ...
} msg_2_t;

typedef union
{
    struct PACK
    {
        uint16_t magic;
        uint8_t len;
        uint8_t msgid;
        union  // all payload types
        {
            msg1_t msg1;
            msg2_t msg2;
            uint8_t pay_u8[MAX_PAYLOAD_LEN];
        };
    };

    uint8_t whole_u8[MAX_PAYLOAD_LEN+4];
} msg_t;

extern msg_t* latest_msg;

// .c
static msg_t msg_a, msg_b;
msg_t* latest_msg;
static msg_t* accum;

init():
  accum = msg_a;
  latest_msg = msg_b;


accumulation in UART character ISR:
{
  accum.whole_u8[idx++] = c;
  update_crc(c);
  if(idx > offsetof(accum.len)+sizeof(accu .len) // len field already received
     && idx >= accum.len + HEADER_LENS_WHATEVER) // complete packet received
  {
     if(processing_running) error(57); // previous processing func did not finish in time
     if(!verify_crc())
        // ignore message and log error
     else
     {
       SWAP(accum, latest_msg);
       processing_running = 1;
       NVIC->STIR = PROCESSING_IRQn; // with lower priority than current interrupt handler
     }
  }
}

static volatile int processing_running;

processing_handler()
{
    // access latest_msg as you wish.
    // if msg_id==1, access latest_msg->msg1, and so on.
    // switch-case is fine, or a table which contains msgids and function pointers for the handlers; loop through the table here and call the correct handler.

   // last thing to do:
   processing_running = 0;
}


No memory copying here. Not saying it's usually a big problem, but why do it when it's not needed? You still have the same constraints: memory footprint of two buffers, and needing to get processing the data finished before the end of the next packet.
« Last Edit: December 04, 2022, 09:25:32 am by Siwastaja »
 
The following users thanked this post: Doctorandus_P

Offline DavidAlfa

  • Super Contributor
  • ***
  • Posts: 5836
  • Country: es
Re: Parsing UART packets / state machines / packed structs
« Reply #3 on: December 04, 2022, 10:20:44 am »
For normal 115.200baud, interrupt-based routine shouldn't be a problem.
Add some sort of timeout handling to avoid stalling!

Code: [Select]
typedef struct{
    uint8_t  len;
    uint8_t  addr;
    uint8_t  cmd;
    uint8_t  buf[255];
    uint16_t chksum;
} uart_data_t;

typedef enum{
    uart_magic_55   = 0,
    uart_magic_AA   = 1,   
    uart_len        = 2,   
    uart_adr        = 3,   
    uart_flag       = 4,
    uart_cmd        = 5,   
    uart_data       = 6,   
    uart_chksum     = 7,   
    uart_done       = 8,
   
    uart_chksum_bytes  = 2,
}uart_states_t;

static volatile uart_states_t uart_state;
volatile uart_data_t uart_data;

// |0x55|0xAA|LENGTH|ADDRESS|0x01|CMD|DATA0....DATAn|CHKSUM|.

void reset_state(void){                         // Called by the user after parsing the packet, or by the timeout routine.
    uart_state = uart_magic_55;
}

void RX_ISR(void){
    static uint16_t count;
    uint8_t rx = RX_BF;
   
    reset_timeout();   // Reset the timeout as long as data keeps coming.

    switch(uart_state){
   
        case uart_magic_55:
            if(rx==0x55){
                enable_timeout();  // Enable timeout ISR or whatever
                uart_state++;
            }
            break;
           
        case uart_magic_AA:
            if(rx==0xAA){
                uart_state++;
            }
            else{
                uart_state = uart_magic_55;
            }
            break;

        case uart_len:
            uart_data.len = rx;
            uart_state++;
            break;
           
        case uart_adr:
            uart_data.adr = rx;
            uart_state++;
            break;
       
        case uart_flag:
            if(rx == 1){
                uart_state++;
            }
            else{           
                uart_state = uart_magic_55;
            }
            break;
       
        case uart_cmd:
            uart_data.cmd = rx;
            count = 0;
            uart_state++;
            break;

        case uart_data:
            uart_data.buffer[count++] = rx;
            if (uart_data.len == count){
                count = 0;
                uart_data.checksum = 0;
                uart_state++;
            }
            break;
           
        case uart_chksum:
            uart_data.checksum |= rx<<(8*count++);
            if(count == uart_chksum_bytes){
                disable_timeout();  // Disable timeout ISR, received full frame, wait for processing
                uart_state++;
            }
            break;
       
        case uart_done:                // Do nothing, wait for processing
        default:
            break;
}

« Last Edit: December 04, 2022, 10:26:31 am by DavidAlfa »
Hantek DSO2x1x            Drive        FAQ          DON'T BUY HANTEK! (Aka HALF-MADE)
Stm32 Soldering FW      Forum      Github      Donate
 

Offline Doctorandus_P

  • Super Contributor
  • ***
  • Posts: 3321
  • Country: nl
Re: Parsing UART packets / state machines / packed structs
« Reply #4 on: December 04, 2022, 10:41:06 am »
I agree with the above.
You can make a union with a bunch of structures in it (Including a byte array to write the "raw" data from the uart to.

C compilers do keep the data in the same order, but they may add padding if your processor has a 16bit or larger word size.
To be able to use the same header file for both my 8-bit uC and my gazillion bit monster PC I had to add an:


#ifdef __linux__
   #pragma pack(push)
   #pragma pack(1)         // Alignment for my big 64 bit monster.
#endif

// Union definition goes here.

#ifdef __linux__
   #pragma pack(pop)      // Restore alignment to normal
#endif


to make GCC happy on both platforms. The PC needed the pack to prevent padding, while the compiler for the 8-bitter choked on the pack.
 
The following users thanked this post: bingo600

Online uer166Topic starter

  • Frequent Contributor
  • **
  • Posts: 872
  • Country: us
Re: Parsing UART packets / state machines / packed structs
« Reply #5 on: December 04, 2022, 07:48:33 pm »
Some pseudocode (not tested), just to give idea how I have done this in recent times:

Code: [Select]
// .h
typedef struct PACK
{
   ...
} msg1_t;

typedef struct PACK
{
   ...
} msg_2_t;

typedef union
{
    struct PACK
    {
        uint16_t magic;
        uint8_t len;
        uint8_t msgid;
        union  // all payload types
        {
            msg1_t msg1;
            msg2_t msg2;
            uint8_t pay_u8[MAX_PAYLOAD_LEN];
        };
    };

    uint8_t whole_u8[MAX_PAYLOAD_LEN+4];
} msg_t;

extern msg_t* latest_msg;

// .c
static msg_t msg_a, msg_b;
msg_t* latest_msg;
static msg_t* accum;

init():
  accum = msg_a;
  latest_msg = msg_b;


accumulation in UART character ISR:
{
  accum.whole_u8[idx++] = c;
  update_crc(c);
  if(idx > offsetof(accum.len)+sizeof(accu .len) // len field already received
     && idx >= accum.len + HEADER_LENS_WHATEVER) // complete packet received
  {
     if(processing_running) error(57); // previous processing func did not finish in time
     if(!verify_crc())
        // ignore message and log error
     else
     {
       SWAP(accum, latest_msg);
       processing_running = 1;
       NVIC->STIR = PROCESSING_IRQn; // with lower priority than current interrupt handler
     }
  }
}

static volatile int processing_running;

processing_handler()
{
    // access latest_msg as you wish.
    // if msg_id==1, access latest_msg->msg1, and so on.
    // switch-case is fine, or a table which contains msgids and function pointers for the handlers; loop through the table here and call the correct handler.

   // last thing to do:
   processing_running = 0;
}


No memory copying here. Not saying it's usually a big problem, but why do it when it's not needed? You still have the same constraints: memory footprint of two buffers, and needing to get processing the data finished before the end of the next packet.

Decent way to do it, I forgot about unions. The reason I copy data is because of data consistency: I have a single timer interrupt system that runs at 20kHz, and ideally everything is done in that ISR. If I were to copy directly to the struct the data would be inconsistent, so need to either double buffer or some kind of a valid flag. Honestly I may switch to those if it proves to be an issue, although a memcpy call is a one-liner..
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 14297
  • Country: fr
Re: Parsing UART packets / state machines / packed structs
« Reply #6 on: December 04, 2022, 07:55:24 pm »
Using unions is fine for this. Just beware of alignment issues.

As to using switch constructs or a table of function pointers, it's up to you. I don't have strong feelings either way. Both can work plenty fine if done right.
I've most often used switch/case, and, unless each case is very simple and short, call a different function inside each case to deal with this specific "state" or "command".
Might look clearer and less error-prone than declaring an array of function pointers and indexing it, but the latter can work too.

I recommend factoring stuff in helper functions in any case as I said above. Avoid gigantic switch constructs with each case handling a lot of code. It becomes quickly unreadable. Call functions inside each case, at least if whatever has to be done for a given case exceeds a couple statements.


 

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 26751
  • Country: nl
    • NCT Developments
Re: Parsing UART packets / state machines / packed structs
« Reply #7 on: December 04, 2022, 08:13:24 pm »
I'd avoid mapping packets onto structs. A lot can go wrong due to alignment issues. And your code won't be byte order agnostic.

IMHO the statemachine approach is a good one. It's intended function is very clear and thus easy to follow / alter if necessary. In the end you don't need that many states to handle a message.

Create a function for each command that takes the data (and length) as a parameter and go from there. If there are many commands with little or no gaps in between, then a table with function pointers can be efficient.
« Last Edit: December 04, 2022, 08:16:30 pm by nctnico »
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Online PCB.Wiz

  • Super Contributor
  • ***
  • Posts: 1473
  • Country: au
Re: Parsing UART packets / state machines / packed structs
« Reply #8 on: December 04, 2022, 10:13:09 pm »
I am in need to parse some UART packets in a format I have no control over. The format is something like:
|0x55|0xAA|LENGTH|ADDRESS|0x01|CMD|DATA0....DATAn|CHKSUM|.
...
I've seen some implementations of such a state machine with function pointers, separating each state into a function, although I didn't think it was particularly readable or safe. Are there more ways to do this in a more obvious or maybe safe manner?
Function pointers can be useful if you have a 'tangled state machine', with multiple paths, that a case statement can find hard to manage.
For most simple state machines, CASE is fine

You may also need to add error handling, as a system might start mid-packet.
Can the data payload ever contain the 0x55.0xAA trigger ?  If not, you can use that pattern for hard sync.

Another point of consideration, is designs often use two data buffers, so one is fully stable, whilst the other one is being built from new data.
If the system is half duplex with a ACK on done, you might get away with a single buffer.

 

Offline artag

  • Super Contributor
  • ***
  • Posts: 1061
  • Country: gb
Re: Parsing UART packets / state machines / packed structs
« Reply #9 on: December 05, 2022, 12:40:26 am »
Be wary of using the content of he packet before verifying the checksum.

This most often occurs when you use the length value to find the end of packet and hence the checksum.  There is some defence against this in the examples posted above where the packet can be timed out if length is read with errors and would otherwise result in waiting forever for a packet which is not as long as you are expecting.

I appreciate that you said you can't change the format and that you're stuck with this, but it's a very poor - albeit common - design. If you lose a character or misread the length and you don't have a sufficient gap  between packets to recover with a timeout, all you can do is attempt to resynchronise using every possible 55 aa, and since it's not clear if that can occur in the data you can end up retrying forever (so don't just throw away a packet with a bad checksum .. reparse it from any other 55 aa that might be in the discarded data).

A much better practice is to reserve some characters for start-of-packet and end-of-packet (or just for end-of-packet) and use escaping (aka byte-stuffing) to keep those characters out of the data and formatting scheme.
 

Online uer166Topic starter

  • Frequent Contributor
  • **
  • Posts: 872
  • Country: us
Re: Parsing UART packets / state machines / packed structs
« Reply #10 on: December 05, 2022, 12:48:44 am »
If you lose a character or misread the length and you don't have a sufficient gap  between packets to recover with a timeout, all you can do is attempt to resynchronise using every possible 55 aa, and since it's not clear if that can occur in the data you can end up retrying forever (so don't just throw away a packet with a bad checksum .. reparse it from any other 55 aa that might be in the discarded data).
That if a fabulous point, here is my thought process:
  • The length byte may be corrupt, and may be either too short or too long up to 255 (this is why data buffer is that size)
  • In the worst case it may be say 255, which means that the next 255 bytes will make the state machine stuck in that loop reading the bytes
  • After the 255 bytes have been read, the CRC calc will of course fails, and the code then goes back to waiting for 0x55, 0xAA, which it will see at the start of the next valid packet and it'll re-sync, assuming that 0x55/0xAA wasn't part of data.
  • If it was part of data, I'm basically relying on it being unlikely to be a repeating sequence, although I admit that an edge case may be constructed here.
  • To fix last bullet point, I am relying on a timeout feature: in all states, I will be adding a "go back to waiting for sync bytes" if the lines has been idle for a long time

I'm personally not a fan of reserved characters and stuffing due to overhead being variable. One way I thought of solving it is via use of "special" characters like a LIN break, that aren't a valid byte at all. That should work well assuming hardware can support it. This us a M365 scooter BMS though and it's a reverse engineered protocol. Food for thought regardless though.
 

Offline ledtester

  • Super Contributor
  • ***
  • Posts: 3032
  • Country: us
Re: Parsing UART packets / state machines / packed structs
« Reply #11 on: December 05, 2022, 01:02:45 am »
For normal 115.200baud, interrupt-based routine shouldn't be a problem.
Add some sort of timeout handling to avoid stalling!

...code...

One little critique about the code...

if you are in the expect_AA state and get a 0x55 you might want to go back to the expect_AA state.

 

Offline artag

  • Super Contributor
  • ***
  • Posts: 1061
  • Country: gb
Re: Parsing UART packets / state machines / packed structs
« Reply #12 on: December 05, 2022, 01:18:04 am »
  • If it was part of data, I'm basically relying on it being unlikely to be a repeating sequence, although I admit that an edge case may be constructed here.
  • To fix last bullet point, I am relying on a timeout feature: in all states, I will be adding a "go back to waiting for sync bytes" if the lines has been idle for a long time
You're essentially then saying that there's a gap between packets which is greater than a defined timeout value. Which is fine, but a) your preexisting protocol might not have that, and b) it's overhead (unusable transmission time) just like reserved characters.

From a BMS a repeating value is very easily common. Something like a 16-bit temperature value ? And, amazingly, it always seems to be those 'very unlikely' values that happen once in a blue moon, cause some hideous failure, and can't be repeated to prove it. 

You can improve that strategy slightly by doing everything you said, but in addition, don't toss the input data as you process it - keep it, even if it's only in the circular recieve buffer. Just mark where you read 55 aa. Then, after detecting a bad checksum, go back to the byte after the initial 55 aa and start looking for another pair. When you find one, repeat the verify.

Imagine if there is a regular 55 aa in the data due to some slow-changing physical value, and that you have have a corrupt length byte that results in you looking for the checksum a couple of bytes too late. You've now absorbed the NEXT 55 aa thinking it was the last couple of bytes of data. The next one you find really is data and perhaps the data following it - which can also be slowly changing - is misinterpreted as a length byte. It's not hard to see how you could grab a whole run of bad packets all synced up on the 5 aa in the data.

I've worked on an actual implementation of a logging system accepting data in this form from an ECU. There was an adaptable system to select one of several ECU manufacturers (these were on specialist vehicles, not common car ECUs, some designed before CAN was so common). It did generally recover by using the above rather painful resync procedure. I was appalled to discover how common such a poor implementation was, and I always use byte-stuffing on my own designs. It may be wasteful but it never does worse than halve the capacity (which is also a reasonable overhead for a gap between packets) and you can at least calculate and design for the worst-case.



 
 
The following users thanked this post: uer166

Online uer166Topic starter

  • Frequent Contributor
  • **
  • Posts: 872
  • Country: us
Re: Parsing UART packets / state machines / packed structs
« Reply #13 on: December 05, 2022, 03:43:18 am »
  • If it was part of data, I'm basically relying on it being unlikely to be a repeating sequence, although I admit that an edge case may be constructed here.
  • To fix last bullet point, I am relying on a timeout feature: in all states, I will be adding a "go back to waiting for sync bytes" if the lines has been idle for a long time
You're essentially then saying that there's a gap between packets which is greater than a defined timeout value.

Yup, in fact I am in control for the request packets. I.e. I can expect silence until the time where I send out a formatted "give me cell voltages" or whatever. I can see your point about efficiency loss here being similar to overhead, maybe something like Consistent Overhead Byte Stuffing would help.
 

Offline Siwastaja

  • Super Contributor
  • ***
  • Posts: 8106
  • Country: fi
Re: Parsing UART packets / state machines / packed structs
« Reply #14 on: December 05, 2022, 07:20:36 am »
Decent way to do it, I forgot about unions. The reason I copy data is because of data consistency: I have a single timer interrupt system that runs at 20kHz, and ideally everything is done in that ISR. If I were to copy directly to the struct the data would be inconsistent, so need to either double buffer

My example was a double buffer solution. It is not much longer than memcpy version (a few extra lines swapping and initializing the pointers). The advantage is, you get rid of the fundamental problem "do you have time to call memcpy"? Let's say bytes arrive at frequency of 1/tb, and packets at 1/tp, so you have tb to process one byte and tp to process one packet. Now the memcpy solution has to copy the whole packet in the same time, tb, unless you can guarantee by design that there is an extra delay between packets.

The double buffer version has same memory footprint as the memcpy version - two buffers - but it's completely free of that issue. You have full tp to process the packet. All you need to do is to process the packet either in main thread (by setting a flag), or as I prefer, a lower priority software interrupt. During the processing, as new bytes arrive, the UART ISR pre-empts the processing and writes to the other buffer.

memcpy idea has no advantages IMHO. Timing-wise, it's even worse than the simplest "single buffer - validity flag - packet delay" solution, yet it requires the same (or actually longer) packet delay. If you can provide enough delay between packets and are sure you can process the packet during that, then just go for single buffer with validity flag.
« Last Edit: December 05, 2022, 07:25:26 am by Siwastaja »
 

Offline Siwastaja

  • Super Contributor
  • ***
  • Posts: 8106
  • Country: fi
Re: Parsing UART packets / state machines / packed structs
« Reply #15 on: December 05, 2022, 07:30:44 am »
Be wary of using the content of he packet before verifying the checksum.

Yes. If messages are of variable lengths, there is a risk of misunderstanding the length field. Especially if the length field is wide and unbounded, you may read a lot larger number than any of the packets actually are. Then the state machine will ignore a lot of messages before it finally realizes the error (by CRC calculation not matching) and can start to resynchronize.

Of course, if you have decent signal integrity, such errors are rare. If you can accept the consequence of losing a few messages before self-recovering, then doing no more than constraining the length field to something sensible (without messing up the future-proofing, which is why the length field exists in the first place) is needed.

For quicker recovery during data corruption, one can add another CRC for just the header. As header is fixed size, getting CRC error there allows the code to start resynchronizing right there and only miss the corrupted packet and not more.

"CRC for header" also makes the synchronization start sequence effectively longer. If you just have say uint16 0xacdc as your magic number, there is a risk of missynchronization into data that accidentally contains this 16-bit sequence. But if you have 0xacdc + uint8 msgid + uint8 len + crc8, the data would need to have this 40-bit sequence in it for accidental synchronization.

If one is in control of both sender and receiver and works with them in sync, there is no need to overthink the protocol. If this is a BMS, maybe one packet type with all information fields (cell voltage, temperature, balancer status) is the best solution, so you get rid of both len and msgid. If you have different types of messages, len has no other use but to allow mixing different versions of devices so that the older version ignores new types of messages. If you do not need this functionality, you can just create a const table of lengths per msgid by using sizeof, and just keep the same header file over both parties, and make sure they use the same version.
« Last Edit: December 05, 2022, 07:38:42 am by Siwastaja »
 

Offline Siwastaja

  • Super Contributor
  • ***
  • Posts: 8106
  • Country: fi
Re: Parsing UART packets / state machines / packed structs
« Reply #16 on: December 05, 2022, 08:39:23 am »
I'd avoid mapping packets onto structs. A lot can go wrong due to alignment issues.

And, nctnico is wrong about this again.

I have never seen any issue with mapping packets onto structs. Actually, the whole internet (BSD, linux) works on C code written that way. Endianness is handled with simple swapping macros which are conditionally defined based on the architecture. Alignment is not an issue at all as I will explain below.

On the contrary, large parsers, when written by a human, almost always contain mistakes. It's not just one or two times someone got wrong the amount of shift, forgot parantheses, stepped into integer promotion rule traps or got some type cast wrong, typed < instead of <<, or, most usually, just forgot to update the damn parser when the interface changed. If the type changed but variable name did not, you don't even get a warning!

Then, alignment. When using normal struct, compiler pads the variables so they are self-aligning. This becomes a problem when different types of architectures with different padding rules communicate with each other. Solution: packed attribute.

With packed attribute, padding is removed and fields of the struct may not be self-aligned, except by luck. But contrary to what nctnico repeatedly claims, being corrected, but nevertheless continuing to supply the same wrong information, this is not a problem. nctnico's mistake happens when he thinks packed attribute only controls the padding when the struct is created and that's it. This is not true. packed attribute is part of the type qualification, so compiler knows the struct is packed everywhere it is used, and can always create correct access instructions. And trust me, compilers are nearly bug-free and will create correct code much more likely than nctnico writing low-level bit manipulation code by hand, trying to outsmart the compiler.

One rule results from this: casting away the packed attribute is dangerous. This happens if you take a pointer of a packed struct member and use that. But this is also why compilers warn about this. Seemingly gcc does this even with minimal warnings enabled (no -Wall):

Code: [Select]
typedef struct __attribute__((packed))
{
        char c1;
        int  i;
        char c2;
} s_t;

int main()
{
        extern void f1(s_t * s);
        extern void f2(int * i);

        s_t s = {0};

        f1(&s);   // correct use
        f2(&s.i); // possible alignment error
        return 0;
}

hrst@jorma:~$ gcc t3.c
t3.c: In function ‘main’:
t3.c:17:5: warning: taking address of packed member of ‘struct <anonymous>’ may result in an unaligned pointer value [-Waddress-of-packed-member]
   17 |  f2(&s.i);
      |     ^~~~

This is not a reason not to use packed structs. With similar reasoning, any qualifier like volatile is dangerous because you can cast it away (and compiler will warn you, too).

TLDR:
* use data types to convey the intent and let the compiler generate the memory access code for you.
* do not try to outsmart the compiler by manipulating bits, unless you really have to. While popular decades ago, it is prone to error.
* C is higher level language than many think. Use this to your advantage.
* packed struct does automatically exactly what nctnico is doing manually. This is a compromise in performance compared to normal struct, as compiler cannot and will not make unsafe assumptions about alignment.
« Last Edit: December 05, 2022, 09:02:01 am by Siwastaja »
 

Offline Nominal Animal

  • Super Contributor
  • ***
  • Posts: 6171
  • Country: fi
    • My home page and email address
Re: Parsing UART packets / state machines / packed structs
« Reply #17 on: December 05, 2022, 09:06:43 am »
I think it is best to draw the states out –– say, each state corresponding to a case in the UART interrupt handler –– and examine carefully what should happen at each stage.  Attached is an image that Graphviz generates from the following:
Code: [Select]
digraph {
    b0 [ label=<<table border="0" cellborder="1"><tr><td port="top" colspan="2"><b>Wait55</b></td></tr><tr><td port="v55">0x55</td><td port="other">*</td></tr></table>>, shape=none ];
    b0:v55:s -> b1:n;
    b0:other:s -> error:n;

    error [ label=<<table border="0" cellborder="1"><tr><td port="top" colspan="2"><b>Error</b></td></tr><tr><td port="v55">0x55</td><td port="other">*</td></tr></table>>, shape=none ];
    error:v55:s -> b1:n;
    error:other:s -> error:ne;

    b1 [ label=<<table border="0" cellborder="1"><tr><td port="top" colspan="3"><b>WaitAA</b></td></tr><tr><td port="vAA">0xAA</td><td port="v55">0x55</td><td port="other">*</td></tr></table>>, shape=none ];
    b1:v55:s -> b1:ne;
    b1:vAA:s -> b2:n;
    b1:other:s -> error:n;

    b2 [ label=<<table border="0" cellborder="1"><tr><td port="top"><b>WaitLen</b></td></tr><tr><td port="other">Len</td></tr></table>>, shape=none ];
    b2:other:s -> b3:n;

    b3 [ label=<<table border="0" cellborder="1"><tr><td port="top"><b>WaitAddr</b></td></tr><tr><td port="other">Addr</td></tr></table>>, shape=none ];
    b3:other:s -> b4:n;

    b4 [ label=<<table border="0" cellborder="1"><tr><td port="top" colspan="2"><b>Wait01</b></td></tr><tr><td port="v01">0x01</td><td port="other">*</td></tr></table>>, shape=none ];
    b4:v01:s -> b5:n;
    b4:other:s -> error:n;

    b5 [ label=<<table border="0" cellborder="1"><tr><td port="top"><b>WaitCMD</b></td></tr><tr><td port="other">CMD</td></tr></table>>, shape=none ];
    b5:other:s -> b6:n;

    b6 [ label=<<table border="0" cellborder="1"><tr><td port="top" colspan="3"><b>WaitData</b></td></tr><tr><td colspan="2">Checksum</td><td port="data">Data</td></tr><tr><td port="good">Good</td><td port="bad">Bad</td></tr></table>>, shape=none ];
    b6:data:s -> b6:n;
    b6:good:s -> b0:nw;
    b6:bad:s -> error:n;
}
The label code is a bit ugly, because I wanted to do nice-looking state blocks.  It is just simplified HTML within < and >, though.
 

Offline Sherlock Holmes

  • Frequent Contributor
  • **
  • !
  • Posts: 570
  • Country: us
Re: Parsing UART packets / state machines / packed structs
« Reply #18 on: December 05, 2022, 03:26:29 pm »
I am in need to parse some UART packets in a format I have no control over. The format is something like:
|0x55|0xAA|LENGTH|ADDRESS|0x01|CMD|DATA0....DATAn|CHKSUM|.

The easiest way seems to be a switch/case state machine, to basically go byte by byte per invocation. It's to be called at a rate higher than the incoming bytes of course to not miss anything, or alternatively use the hardware 8-byte FIFO to call this every 8 bytes, reducing ISR rate. After a packet data is read and validated, it is then memcpy-d into a packed struct based on the command byte which defines the data format, therefore automatically getting the right bits in place. Something like:

Code: [Select]
/* Data structure declarations */
volatile struct BMS_batstat bms_batstat;

/* UART state machine state for reading/parsing packets */
static uint8_t length = 0;
static uint16_t chksum = 0;
static uint8_t cmdreq = 0;
static uint8_t databuf[255] = {0};
static uint8_t databuf_i = 0;

void BMS_UART_ParseData(void)
{
if(cmdreq == CMDREQ_BATSTAT)
{
memcpy(&bms_batstat, databuf, sizeof(bms_batstat));
}
else
{
// unknown packet, TODO
}
}

void BMS_UART_StateMachine_Rx(uint8_t rx)
{
switch(bms_uart_state)
{
case UART_wait_0x55:
if(rx == 0x55) { bms_uart_state = UART_wait_0xAA; } else { bms_uart_state = UART_wait_0x55; }
break;

case UART_wait_0xAA:
if(rx == 0xAA) { bms_uart_state = UART_read_length; } else { bms_uart_state = UART_wait_0x55; }
break;

case UART_read_length:
length = rx;
databuf_i = 0;
bms_uart_state = UART_wait_0x25;
break;

case UART_wait_0x25:
if(rx == 0x25) { bms_uart_state = UART_wait_0x01; } else { bms_uart_state = UART_wait_0x55; }
break;

case UART_wait_0x01:
if(rx == 0x01) {bms_uart_state = UART_read_cmdreq; } else { bms_uart_state = UART_wait_0x55; }
break;

case UART_read_cmdreq:
cmdreq = rx;
bms_uart_state = UART_read_data;
break;

case UART_read_data:
databuf[databuf_i] = rx;
databuf_i++;
if(databuf_i == (length - 2)) {bms_uart_state = UART_read_checksumLSB;} /* Data length without including extras */
break;

case UART_read_checksumLSB:
chksum = (uint16_t)rx;
bms_uart_state = UART_read_checksumMSB;

break;

case UART_read_checksumMSB:
chksum |= ((uint16_t)rx) << 8;

uint16_t chksum_data = 0;
chksum_data = length + 0x25 + 0x01 + cmdreq; /* Need to add extras to checksum */

/* Data length without including extras */
for(uint8_t i = 0; i < (length - 2); i++)
{
chksum_data += databuf[i];
}

if(chksum == (0xFFFF - chksum_data))
{
BMS_UART_ParseData();
}

bms_uart_state = UART_wait_0x55;
break;

default:
asm("bkpt");
break;
}
}

I've seen some implementations of such a state machine with function pointers, separating each state into a function, although I didn't think it was particularly readable or safe. Are there more ways to do this in a more obvious or maybe safe manner? The only complication I see here is the need to debug these variables in the foreground in a shell-like environment, and the packed structs are not atomic, therefore I need to unpack/copy all these variable into atomic types such as float or uint32_t so that there is no data consistency issues.

Hi,

An FSM based on pointers is an excellent design choice, there's a small cost consideration as a function call is involved but that might be negligible.

Create a 1D array of function pointers, invoked like this

Code: [Select]

STATE = INITIAL; // e.g. 0, some enum element...

while (whatever)
   {
   CHAR = get_next_byte();
   STATE = process_event[STATE](CHAR);
   }


One can use a 2D map but not in cases like yours, you have fixed set of states but not a fixed set of incoming bytes.

Each handler is then pretty simple, it performs some simple, single, well defined action and returns a new (or unchanged) state.

Once the array is initialized you're good to go and debugging this is much easier than explicit switch based designs.

Also if the data is corrupt, you can sometimes handle that within a handler and consuming bytes until some safe recognizable sentinel is seen and continue on, yes you've lost some data but at least you can recover to a degree and log the loss.






« Last Edit: December 05, 2022, 03:32:21 pm by Sherlock Holmes »
“When you have eliminated all which is impossible, then whatever remains, however improbable, must be the truth.” ~ Arthur Conan Doyle, The Case-Book of Sherlock Holmes
 
The following users thanked this post: uer166

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 26751
  • Country: nl
    • NCT Developments
Re: Parsing UART packets / state machines / packed structs
« Reply #19 on: December 05, 2022, 03:48:19 pm »
I'd avoid mapping packets onto structs. A lot can go wrong due to alignment issues.

And, nctnico is wrong about this again.

I have never seen any issue with mapping packets onto structs. Actually, the whole internet (BSD, linux) works on C code written that way. Endianness is handled with simple swapping macros which are conditionally defined based on the architecture. Alignment is not an issue at all as I will explain below.
That is because most big CPUs don't care about aligment. Go into the microcontroller world and things are different. Just count yourself lucky you never had to spend days looking for an alignment problem that caused silent data corruption.

Another disadvantage of using structs is that you need to do work for fields you don't need. In many protocols you don't need the contents of all fields. And how about when the protocol changes where fields suddenly are placed at a different offset?

A set of simple functions that get a certain type from a certain offset (which is also how protocols are typically specified so field offset verification is easy) in the right byte order is much easier and future proof to work with. In the end not mapping structs onto buffers will make your life easier.
« Last Edit: December 05, 2022, 03:55:00 pm by nctnico »
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Offline Siwastaja

  • Super Contributor
  • ***
  • Posts: 8106
  • Country: fi
Re: Parsing UART packets / state machines / packed structs
« Reply #20 on: December 05, 2022, 04:10:49 pm »
That is because most big CPUs don't care about aligment. Go into the microcontroller world and things are different. Just count yourself lucky you never had to spend days looking for an alignment problem that caused silent data corruption.

It's not luck - it's understanding the language, the tools and documentation. As expected, you completely ignored all the facts again.

The fact that using correct, robust, test&tried language constructs does not cause problems in practice is completely unsurprising to everyone else except someone who has just decided they are bad, without ever being able to explain why, except bogus, made-up reasons like "alignment", which is shown to be wrong time after time.

Again, we are talking about a construct where compiler guarantees correct alignment, but somehow you don't like it "because of alignment".

And yes, I have debugged alignment problems (e.g. with DMA) but never with a packed struct - exactly because the packed attribute removes the assumptions about self-alignment |O.
« Last Edit: December 05, 2022, 04:15:22 pm by Siwastaja »
 

Offline ledtester

  • Super Contributor
  • ***
  • Posts: 3032
  • Country: us
Re: Parsing UART packets / state machines / packed structs
« Reply #21 on: December 05, 2022, 04:12:53 pm »
I have a feeling that the BMS only sends packets every so often.

Therefore there will be a long pause between packets and you can use this pause as a way of synchronizing the start of a packet.
 

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 26751
  • Country: nl
    • NCT Developments
Re: Parsing UART packets / state machines / packed structs
« Reply #22 on: December 05, 2022, 04:16:44 pm »
That is because most big CPUs don't care about aligment. Go into the microcontroller world and things are different. Just count yourself lucky you never had to spend days looking for an alignment problem that caused silent data corruption.

It's not luck - it's understanding the language, the tools and documentation. As expected, you completely ignored all the facts again.

The fact that using correct, robust, test&tried language constructs does not cause problems in practice is completely unsurprising to everyone else except someone who has just decided they are bad, without ever being able to explain why, except bogus, made-up reasons like "alignment", which is shown to be wrong time after time.
I already explained precisely why mapping structs on buffer is bad: not all platforms support it  AND it doesn't solve byte order (many protocols use big endian byte order while many CPUs nowadays are little endian). It is not much simpler than that.

Using getters / setters to deal with a buffer make sure alignment never comes around to bite you AND it gets you the right byte order without needing to do post-processing / keep track on whether you already swapped the bytes or need to that later on. Everything is neatly packed into a single -call it layer if you like- that deals with formatting the fields in the buffer properly.

I don't care about compiler / language constructs; they don't have to work for all situations. And to be more precise: struct packing is not really a C language construct either. You need to use a compiler specific attribute or pragma to tell the compiler the struct is somehow 'special'.
« Last Edit: December 05, 2022, 04:20:21 pm by nctnico »
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Offline Siwastaja

  • Super Contributor
  • ***
  • Posts: 8106
  • Country: fi
Re: Parsing UART packets / state machines / packed structs
« Reply #23 on: December 05, 2022, 04:24:25 pm »
I already explained precisely why mapping structs on buffer is bad: not all platforms support it

What do you mean by "mapping"? Pointer casting?

Why not do it properly (as per C99, plus packing compiler extension):
union
{
   struct PACKED
   {
      ...
   };
   uint8_t u8[...];
};

I already showed this, but of course you ignored it.

Avoiding pointer manipulation is a good idea when it can be avoided. Type-punning via unions is extremely robust, compiler HAS to make it work (for example, if you have a uin32_t form in the union, compiler aligns the whole object by 4, and you can fill the data efficiently from a 32-bit data register or DMA). But the struct, being packed, is still accessed with correct instructions and never unaligned.

Plus it's super readable, you document directly into the datatype all the forms the objects will be used in. No messy code; no casting to different type of pointer then dereferencing it. No bit manipulation gymnastics. Just well defined language construct, plus:

Quote
And to be more precise: struct packing is not really a C language construct either. You need to use a compiler specific attribute

Which is implemented by every practical compiler available, because so much code depends on
1) having it available,
2) having it operate correctly (not generate unaligned access, that's the whole point)

C programming often uses compiler extensions, especially on embedded (MCU). Some are quite special snowflakes; others like packed is realistically always available. Get used to it and stop complaining about it and start writing better code.

Oh god I wish C standard folks would have added the packed keyword to the language. Not that it's a big problem, because every compiler implements it anyway and it's not a problem with practical people who can wrap it in a #define macro for portable code. But I would like to see all the needless complaining go away.
« Last Edit: December 05, 2022, 04:33:24 pm by Siwastaja »
 

Online uer166Topic starter

  • Frequent Contributor
  • **
  • Posts: 872
  • Country: us
Re: Parsing UART packets / state machines / packed structs
« Reply #24 on: December 05, 2022, 06:11:30 pm »

"CRC for header" also makes the synchronization start sequence effectively longer. If you just have say uint16 0xacdc as your magic number, there is a risk of missynchronization into data that accidentally contains this 16-bit sequence. But if you have 0xacdc + uint8 msgid + uint8 len + crc8, the data would need to have this 40-bit sequence in it for accidental synchronization.

The above opened my eyes a little bit, since the first few bytes:
|0x55|0xAA|LENGTH|ADDRESS|0x01|CMD|

Are actually predictable and are all the same given a specific CMD. the CMD defines the length, and the ADDRESS is always a fixed number. This means I can easily sync on the first 6 bytes, which gives a nice 48-bit sequence. This would avoid the need for a 255-byte buffer and any re-sync should be pretty quick. This is kinda like having a CRC since the length and address is always a unique fixed pair in the messages that I care about.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf