Augment CmdMessenger with Forward Error Correction

[jptech]

CmdMessenger should be resilient to communication faults. We should try adding some low overhead error correction or detection scheme (like crc)

[xxAtrain223]

Would you want to have this in time for the competition? I found this implementation, I could probably implement this tonight, and have it ready to test tomorrow.

[jptech]

I am not sure if it worth changing a critical component right now. Obviously feel free to play around with it on a branch if you aren't doing anything else, but it really wasn't planned for competition.

[xxAtrain223]

Since we have plans for making a new communication protocol after the competition, it would probably be a wasted effort, except for the research value.

[jptech]

Yes, that has been discussed, but that new communication protocol (or cmd messenger) should have FEC of some sort.

it would probably be a wasted effort, except for the research value.

I think it is fairly obvious that we wouldn't update cmd messenger AND then just replace it. It is an either/or scenario of either we update cmd messenger with some changes OR make a totally new system.

[amessing]

And the correct answer is make a totally new system. One that we can easily test.

[xxAtrain223]

This is what i've made so far. I'm looking into generating the lookup table at compile time. This is based off of the tutorial here

#include <cstdint>
#include <type_traits>
#include <iterator>

#include <vector>
#include <cassert>

template<typename T, T generator, typename std::enable_if< std::is_unsigned<T>::value>::type* = nullptr>
class Crc
{
private:
    T table[256];

public:
    typedef T type;
    static const size_t typeSize = sizeof(T);

    Crc()
    {
        // Generate Look up table

        /* iterate over all byte values 0 - 255 */
        for (uint16_t divident = 0; divident < 256; divident++)
        {
            T currByte = (T)(divident << ((sizeof(T) - 1) * 8));
            /* calculate the CRC-8 value for current byte */
            for (uint8_t bit = 0; bit < 8; bit++)
            {
                if ((currByte & (0x80 << ((sizeof(T) - 1) * 8))) != 0)
                {
                    currByte <<= 1;
                    currByte ^= generator;
                }
                else
                {
                    currByte <<= 1;
                }
            }
            /* store CRC value in lookup table */
            table[divident] = currByte;
        }
    }

    T Calculate(uint8_t data[], size_t length)
    {
        T crc = 0;

        for (size_t i = 0; i < length; i++)
        {
            /* XOR-in next input byte */
            uint8_t pos = (uint8_t)((crc ^ (data[i] << ((sizeof(T) - 1) * 8))) >> ((sizeof(T) - 1) * 8));

            /* get current CRC value = remainder */
            crc = ((sizeof(T) > 1) ? (crc << 8) : 0) ^ (T)table[pos];
        }

        return crc;
    }

#pragma warning(push)
#pragma warning(error : 4244)
    template<typename Container>
    T Calculate(const Container& cont)
    {
        T crc = 0;

        for (const unsigned char& byte : cont)
        {
            /* XOR-in next input byte */
            uint8_t pos = (uint8_t)((crc ^ (byte << ((sizeof(T) - 1) * 8))) >> ((sizeof(T) - 1) * 8));

            /* get current CRC value = remainder */
            crc = ((sizeof(T) > 1) ? (crc << 8) : 0) ^ (T)table[pos];
        }

        return crc;
    }
#pragma warning(pop)
};

typedef Crc<uint8_t, 0x1D> Crc8;
typedef Crc<uint16_t, 0x1021> Crc16;
typedef Crc<uint32_t, 0x04C11DB7> Crc32;

int main()
{
    unsigned char data[] = { 0x01, 0x02 };
    assert(Crc8().Calculate(data, 2) == 0x76);
    assert(Crc16().Calculate(data, 2) == 0x1373);
    assert(Crc32().Calculate(data, 2) == 0xDB9BFAB2);

    std::vector<uint8_t> data2 = { 0x01, 0x02 };
    assert(Crc8().Calculate(data2) == 0x76);
    assert(Crc16().Calculate(data2) == 0x1373);
    assert(Crc32().Calculate(data2) == 0xDB9BFAB2);

    return 0;
}

The template version of Calculate can be used with any container whose value type can be converted to unsigned char without loss of data, e.g. std::list<uint8_t> and std::string, but not std::vector<uint16_t>.