Tuesday, May 3, 2011

Byte Stuffing

I occasionally need to write programs to send and receive data bytes from one device to another. That is why I arbitrarily choose a simple variant of byte stuffing methods to build frames to send and receive data. To delimit the frame, control characters - 0x02 and 0x03- are defined as start of text (STX) and end of text (ETX) respectively. For error detection, exclusive-or of data bytes is appended after the ETX as a checksum. If you need better error detection, CRC as described at

CRC Calculation in VB and C

can also be used.

For example, if we want to send two bytes of data -
0x30 0x31,
the resulting frame will be
0x02 0x30 0x31 0x03 0x01
,where 0x02 at the start is added as STX, followed by data bytes and the byte before the last one, 0x03, is added as ETX. Since the exclusive-or of data bytes, 0x02^0x03, is 0x01, it is appended at the end as checksum. How can we send data that contains 0x02 or 0x03 which were already used as control characters? We need to define another control character 0x10 as Data Link Escape (DLE) to mark data that are not control characters. As an another example, let us build a frame for five data bytes -
0x30 0x02 0x65 0x10 0x03.
We will do byte stuffing by putting DLE in front of every data byte that conflicts with STX, ETX, or DLE. And
0x02 0x30 0x10 0x02 0x65 0x10 0x10 0x10 0x03 0x03 0x44
will be the resulting frame. I have developed a few programs in C and LabVIEW. Example programs can be downloaded at the following links.

Byte Stuffing on GitHub


The following is the C++ code to build, send and receive a frame.
// Byte stuffing- sending and receiving frames
// Author: Yan Naing Aye

#ifndef  FRAME_H
#define FRAME_H

#include 
#define STX 0x02
#define ETX 0x03
#define DLE 0x10

#define TX_BUF_SIZE 128
#define RX_BUF_SIZE 128
enum RX_STATE { IGNORE,RECEIVING,ESCAPE,RXCRC1,RXCRC2 };
//-----------------------------------------------------------------------------
class Frame {    
    RX_STATE rState;
protected:
    int TxN;//number of transmitting bytes
    int RxN;//number of receiving bytes
    char tb[TX_BUF_SIZE];//transmit buffer
    char rb[RX_BUF_SIZE];//receiving data
public:
    Frame();
    int setTxFrame(char* d,int n);
    unsigned int CRC16CCITT_Calculate(char* s,unsigned char len,unsigned int crc);
    int getTxN();
    int getRxN();
    int receiveRxFrame(char c);//get receiving frame from received char
    char* getTxBuf();
    char* getRxBuf();
};
//-----------------------------------------------------------------------------
Frame::Frame():TxN(0),RxN(0),rState(IGNORE){}
//-----------------------------------------------------------------------------
char* Frame::getTxBuf(){
    return tb;
}
//-----------------------------------------------------------------------------
char* Frame::getRxBuf(){
    return rb;
}
//-----------------------------------------------------------------------------
//Prepare transmitting frame
int Frame::setTxFrame(char* d,int n)
{
    unsigned int txcrc=0xFFFF;//initialize crc
    char c;
    int i=0,j=0;
    tb[i++]=STX;//start of frame
    for(j=0;j < n;j++) {
        c=d[j];
        if((c==STX)||(c==ETX)||(c==DLE)) tb[i++]=(DLE);
        tb[i++]=c;
    }
    tb[i++]=(ETX);//end of frame

    txcrc=CRC16CCITT_Calculate(d,n,txcrc);//calculate crc
    tb[i++]=txcrc & 0xFF;
    tb[i++]=(txcrc >> 8) & 0xFF;
    TxN=i;
    return TxN;
}
//-----------------------------------------------------------------------------
//Inputs
//s : pointer to input char string
//len: string len (maximum 255)
//crc: initial CRC value

//Output
//Returns calculated CRC
unsigned int Frame::CRC16CCITT_Calculate(char* s,unsigned char len,unsigned int crc)
{
    //CRC Order: 16
    //CCITT(recommendation) : F(x)= x16 + x12 + x5 + 1
    //CRC Poly: 0x1021
    //Operational initial value:  0xFFFF
    //Final xor value: 0
    unsigned char i,j;
    for(i=0;i < len;i++,s++) {
        crc^=((unsigned int)(*s) & 0xFF) << 8;
        for(j=0;j<8;j++) {
            if(crc & 0x8000) crc=(crc << 1)^0x1021;
            else crc <<=1;
        }
    }
    return (crc & 0xFFFF);//truncate last 16 bit
}
//-----------------------------------------------------------------------------
//get number of transmitting bytes
int Frame::getTxN()
{
    return TxN;
}
//-----------------------------------------------------------------------------
//get number of transmitting bytes
int Frame::getRxN()
{
    return RxN;
}
//-----------------------------------------------------------------------------
//process receiving char
int Frame::receiveRxFrame(char c)
{
    static char b;
    unsigned int crc;
    unsigned int rxcrc=0xFFFF;//initialize CRC
    switch(rState){
        case IGNORE:
            if(c==STX) { rState=RECEIVING;RxN=0;}
            break;
        case RECEIVING:
            if(c==STX) { rState=RECEIVING;RxN=0;}
            else if(c==ETX){rState=RXCRC1;}
            else if(c==DLE){ rState=ESCAPE; }
            else { rb[RxN++]=c; }
            break;
        case ESCAPE:
            rb[RxN++]=c; rState=RECEIVING;
            break;
        case RXCRC1:
            b=c; rState=RXCRC2;
            break;
        case RXCRC2:
            rState=IGNORE;
            crc=( (int)c << 8 | ((int)b & 0xFF) ) & 0xFFFF;//get received crc
            rxcrc=CRC16CCITT_Calculate(rb,RxN,rxcrc);//calculate crc
            //printf("crc: %x  rxcrc:%x \n",crc,rxcrc);
            if(rxcrc==crc){return RxN;}//if crc is correct            
            else {RxN=0;}//discard the frame

            break;
    }
    return 0;
}

//-----------------------------------------------------------------------------

//#############################################################################

class Frame2:public Frame {
    char Dt[20];//transmitting data
public:
    Frame2();
    void printTxFrame();
    void printRxFrame();
    void printRxData();
    void setTxData(float x,float y,float z,float b,float t);
};
//-----------------------------------------------------------------------------
Frame2::Frame2():Frame(),Dt(""){}
//-----------------------------------------------------------------------------
//Print out frame content
void Frame2::printTxFrame()
{
    printf("Tx frame buffer: ");
    for(int j=0;j < TxN;j++) printf("%02X ",(unsigned char)tb[j]);
    printf("\n");
}
//-----------------------------------------------------------------------------
//Print out frame content
void Frame2::printRxFrame()
{
    printf("Rx data buffer: ");
    for(int j=0;j < RxN;j++) printf("%02X ",(unsigned char)rb[j]);
    printf("\n");
}
//-----------------------------------------------------------------------------
//Set transmitting data
void Frame2::setTxData(float x,float y,float z,float b,float t)
{
    *(float*)(Dt)=x;
    *(float*)(Dt+4)=y;
    *(float*)(Dt+8)=z;
    *(float*)(Dt+12)=b;
    *(float*)(Dt+16)=t;
    Frame::setTxFrame(Dt,20);
}
//-----------------------------------------------------------------------------
//Print out received data
void Frame2::printRxData()
{
    float x,y,z,b,t;
    x=*(float*)(Dt);
    y=*(float*)(Dt+4);
    z=*(float*)(Dt+8);
    b=*(float*)(Dt+12);
    t=*(float*)(Dt+16);
    printf("Rx data: %f %f %f %f %f \n",x,y,z,b,t);
}
//-----------------------------------------------------------------------------

#endif // FRAME_H

2 comments:

  1. The read part of the code does not seem to work. If I pass the same data array into the Byte stuff 'encoding' and then into the 'decode' (read) portion of the code...the output array returns all zero's with a reported frame size of 0?!?!?

    ReplyDelete
    Replies
    1. Are you using LabVIEW or C? Could you please tell us more details? These modules are tested and they work well in our case.

      Delete

Comments are moderated and don't be surprised if your comment does not appear promptly.