Comparing part of a QByteArray with quint16, how to do it best?



  • Hello everyone,

    I'm currently working on a QByteArray based communication between 2 devices. Per definition, the last 2 Bytes should always be the crc value, of everything before.

    I'm using QDatastream to write&read into/from the QByteArray.

    Everything work fine. But I think in the receiving part, I may have choosen a "slow" way to compare the send crc with the calcualted one.

    I know we're talking about ms improvments, if any, but as a matter of principle does anyone know a more elegant or faster way to do this?

    Take a look at my code:

    
    bool Datagram::isCorrectResponse(const QByteArray &data)
    {
         ....
         ....
         //Crc Part
         quint16 crcNew (calculateCrc(data.mid(0,data.length()-2));
         quint18 crcOld;
    
         QByteArray baCrc(data.mid(data.length()-2,2));
         QDataStream out(&baCrc, QIODevice::ReadOnly);
         out >> crcOld;
    
         if(crcNew != crcOld)
             return false;
         else
             return true;
    }
    
    //CRC calculation
    quint16 Datagram::calculateCrc(const QByteArray &data)
    {
        quint16 crc = 0xFFFF;
        for(int pos(0); pos < data.length(); pos++){
            crc ^=(uint16_t)data[pos];
            for(int i(8); i!= 0; i--){
                if((crc & 0x0001) != 0){
                    crc >>= 1;
                    crc ^= 0xA001;
                }else{
                    crc >>=1;
                }
            }
        }
        return qFromBigEndian(crc);
    }
    

  • Qt Champions 2017

    bool Datagram::isCorrectResponse(const QByteArray & data)
    {
         int offset = data.length() - sizeof(quint16);
    
         // Calculate the hash
         quint16 crcNew = calculateCrc(data.constBegin(), offset);
    
         // Read the received hash
         QDataStream out(data);
         if (out.skipRawData(offset) != offset)
             return false;
    
         quint18 crcOld;
         out >> crcOld;
    
         // Compare ...
         return out.status() == QDataStream::Ok && crcNew == crcOld;
    }
    
    quint16 Datagram::calculateCrc(QByteArray::const_iterator iterator, int length)
    {
        // ...
        quint16 crc = 0xFFFF;
        for(QByteArray::const_iterator end = iterator + length; iterator != end; ++iterator)  {
            char byteToHash = *iterator;
            // Use a lookup table here
            // ...
        }
        // ...
    }
    


  • hi @kshegunov ,
    I like your solution a lot, removes a lot of QByteArray-Copying/Constructing that botheres me in the my code. But for example I didn't know that QDataStream had a skipRawData function, I was looking for a backwards rollup ore something instead.

    So I'm defenitly adopting a good part of your example!
    However I'm not sure about the calculateCrc change, I actually tried to avoid a lookup table.


  • Qt Champions 2017

    @J.Hilk said in Comparing part of a QByteArray with quint16, how to do it best?:

    However I'm not sure about the calculateCrc change, I actually tried to avoid a lookup table.

    Why? Usually the tables are 256 entries a 16 Bit = 512 Byte, so size should not be a problem.

    If it really brings a performance boost can only be measured with a benchmark. One problem in the "non-table" code could be the if-condition. All other arithmetics should be rather fast.



  • @aha_1980 For me in this case, it's not a performance issue but rather a aesthetics one.
    I dislike huge and bulky definitions in my source code.

    0_1516953636657_embarrassedEmojii.jpg

    However I made the following changes to it:

    //CRC calculation
    quint16 Datagram::calculateCrc(const QByteArray &data, const uchar &offset)
    {
        quint16 crc = 0xFFFF;
        for(int pos(0); pos < data.length() - offset; pos++){
            crc ^=(uint16_t)data[pos];
            for(int i(8); i!= 0; i--){
                if((crc & 0x0001) != 0){
                    crc >>= 1;
                    crc ^= 0xA001;
                }else{
                    crc >>=1;
                }
            }
        }
        return qFromBigEndian(crc);
    }
    

    with a default for offset of 0, so the change doesn't break other parts of my code and calling it from
    isCorrectResponse this way:

    crcNew = calculateCrc(data,2);
    

  • Qt Champions 2017

    @J.Hilk said in Comparing part of a QByteArray with quint16, how to do it best?:

    However I made the following changes to it

    Well, I'd have used the crc16 Qt already provides, unless you're bent on a specific implementation (or Qt version).

    @aha_1980 said in Comparing part of a QByteArray with quint16, how to do it best?:

    If it really brings a performance boost can only be measured with a benchmark.

    I'd bet on the lookup table, almost every time. And the table is only 16 shorts (qbytearray.cpp @ 532 in Qt's source) - small enough to fit a single cache line ...



  • @kshegunov said in Comparing part of a QByteArray with quint16, how to do it best?:

    Well, I'd have used the crc16 Qt already provides, unless you're bent on a specific implementation (or Qt version).

    I'll have to use a crc16, the Datagram is based on Modbus.

    I' had some issues with my function, for some reasons, there were QByteArrays, that resulted in a wrong crc. Far from all, but some ( ca 1 in 20!?)

    So I looked up, what Qt does in the QModbus - Rtu class:

    /* Table of CRC values for high-order byte */
    static const uint8_t table_crc_hi[] = {
        0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
        0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
        0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
        0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,
        0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
        0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41,
        0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
        0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
        0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
        0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40,
        0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
        0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,
        0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
        0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40,
        0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
        0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,
        0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
        0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
        0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
        0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
        0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
        0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40,
        0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
        0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
        0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
        0x80, 0x41, 0x00, 0xC1, 0x81, 0x40
    };
    
    /* Table of CRC values for low-order byte */
    static const uint8_t table_crc_lo[] = {
        0x00, 0xC0, 0xC1, 0x01, 0xC3, 0x03, 0x02, 0xC2, 0xC6, 0x06,
        0x07, 0xC7, 0x05, 0xC5, 0xC4, 0x04, 0xCC, 0x0C, 0x0D, 0xCD,
        0x0F, 0xCF, 0xCE, 0x0E, 0x0A, 0xCA, 0xCB, 0x0B, 0xC9, 0x09,
        0x08, 0xC8, 0xD8, 0x18, 0x19, 0xD9, 0x1B, 0xDB, 0xDA, 0x1A,
        0x1E, 0xDE, 0xDF, 0x1F, 0xDD, 0x1D, 0x1C, 0xDC, 0x14, 0xD4,
        0xD5, 0x15, 0xD7, 0x17, 0x16, 0xD6, 0xD2, 0x12, 0x13, 0xD3,
        0x11, 0xD1, 0xD0, 0x10, 0xF0, 0x30, 0x31, 0xF1, 0x33, 0xF3,
        0xF2, 0x32, 0x36, 0xF6, 0xF7, 0x37, 0xF5, 0x35, 0x34, 0xF4,
        0x3C, 0xFC, 0xFD, 0x3D, 0xFF, 0x3F, 0x3E, 0xFE, 0xFA, 0x3A,
        0x3B, 0xFB, 0x39, 0xF9, 0xF8, 0x38, 0x28, 0xE8, 0xE9, 0x29,
        0xEB, 0x2B, 0x2A, 0xEA, 0xEE, 0x2E, 0x2F, 0xEF, 0x2D, 0xED,
        0xEC, 0x2C, 0xE4, 0x24, 0x25, 0xE5, 0x27, 0xE7, 0xE6, 0x26,
        0x22, 0xE2, 0xE3, 0x23, 0xE1, 0x21, 0x20, 0xE0, 0xA0, 0x60,
        0x61, 0xA1, 0x63, 0xA3, 0xA2, 0x62, 0x66, 0xA6, 0xA7, 0x67,
        0xA5, 0x65, 0x64, 0xA4, 0x6C, 0xAC, 0xAD, 0x6D, 0xAF, 0x6F,
        0x6E, 0xAE, 0xAA, 0x6A, 0x6B, 0xAB, 0x69, 0xA9, 0xA8, 0x68,
        0x78, 0xB8, 0xB9, 0x79, 0xBB, 0x7B, 0x7A, 0xBA, 0xBE, 0x7E,
        0x7F, 0xBF, 0x7D, 0xBD, 0xBC, 0x7C, 0xB4, 0x74, 0x75, 0xB5,
        0x77, 0xB7, 0xB6, 0x76, 0x72, 0xB2, 0xB3, 0x73, 0xB1, 0x71,
        0x70, 0xB0, 0x50, 0x90, 0x91, 0x51, 0x93, 0x53, 0x52, 0x92,
        0x96, 0x56, 0x57, 0x97, 0x55, 0x95, 0x94, 0x54, 0x9C, 0x5C,
        0x5D, 0x9D, 0x5F, 0x9F, 0x9E, 0x5E, 0x5A, 0x9A, 0x9B, 0x5B,
        0x99, 0x59, 0x58, 0x98, 0x88, 0x48, 0x49, 0x89, 0x4B, 0x8B,
        0x8A, 0x4A, 0x4E, 0x8E, 0x8F, 0x4F, 0x8D, 0x4D, 0x4C, 0x8C,
        0x44, 0x84, 0x85, 0x45, 0x87, 0x47, 0x46, 0x86, 0x82, 0x42,
        0x43, 0x83, 0x41, 0x81, 0x80, 0x40
    };
    
    static uint16_t crc16(uint8_t *buffer, uint16_t buffer_length)
    {
        uint8_t crc_hi = 0xFF; /* high CRC byte initialized */
        uint8_t crc_lo = 0xFF; /* low CRC byte initialized */
        unsigned int i; /* will index into CRC lookup */
    
        /* pass through message buffer */
        while (buffer_length--) {
            i = crc_hi ^ *buffer++; /* calculate the CRC  */
            crc_hi = crc_lo ^ table_crc_hi[i];
            crc_lo = table_crc_lo[i];
        }
    
        return (crc_hi << 8 | crc_lo);
    }
    
    //with this call in my class:
    quint16 crcNew = crc16((unsigned char *)(data.data()),offset);
    

    Seems to work fine.


  • Qt Champions 2017

    @J.Hilk said in Comparing part of a QByteArray with quint16, how to do it best?:

    I'll have to use a crc16

    qChecksum is crc16, or more-precisely one implementation out of the many.

    So I looked up, what Qt does in the QModbus - Rtu class

    Perhaps that code should be moved to QtBase ...


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.