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>.