CODEWITHSUNDEEP
crc
Artem Shaban
Artem Shaban

Reputation: 176

CRC implementation (order of bit shifting)

I can't understand why theory and implementation of CRC not indentical? I mean in implementations I find first perform bitshift and then xor. But first bit will not be xored. And in explanation xor starting from first bit. Here my code for CRC4

public enum CRC4_POLY
{
    CRC4 = 0x0B //1011
};

public class CRC4Calc
{
    private byte[] table = new byte[16];

    public byte Checksum(params byte[] val)
    {
        if (val == null)
            throw new ArgumentNullException("val");

        byte c = 0;

        foreach (byte b in val)
        {
            c = table[c ^ b];
        }

        return c;
    }

    public byte[] Table
    {
        get
        {
            return this.table;
        }
        set
        {
            this.table = value;
        }
    }

    public byte[] GenerateTable(CRC4_POLY polynomial)
    {
        byte[] csTable = new byte[16];

        for (int i = 0; i < 16; ++i)
        {
            int curr = i;

            for (int j = 0; j < 4; ++j)
            {
                if ((curr & 0x8) != 0)
                {
                    curr = ((curr << 1) & 0x0F) ^ (int)polynomial; // why not?: curr = ((curr ^ (int)polynomial) <<1) & 0x0F;
                }
                else
                {
                    curr <<= 1;
                }
            }

            csTable[i] = (byte)curr;
        }

        return csTable;
    }

    public CRC4Calc(CRC4_POLY polynomial)
    {
        this.table = this.GenerateTable(polynomial);
    }
}

Upvotes: 1

Views: 1296

Answers (1)

Mark Adler
Mark Adler

Reputation: 112404

The top bit of the register before shifting out, i.e. the bit being shifted out, determines whether the polynomial is exclusive-or'ed with what remains after shifting. This is precisely the classic shift register implementation.

shift register implementation

Upvotes: 2

Related Questions