CRC generation — Parallax Forums

# CRC generation

Posts: 18,063
edited 2017-12-14 02:10
Attached is a simple spin program for the P1 to calculate any CRC.
There are various polynomials, number of bits, lsb/msb first, preset crc initial value, xor final value, send LSB/MSB crc byte first.
But a general purpose CRC is better.

Would some of you please test/modify this program and check it works?

What I would like to do is ask Chip for a single-bit CRC instruction for the P2. IMHO the best format for this would be that the data-bit would be in the C flag. Because we only have P2 instructions available with a single operand [#]D style, I thought that the polynomial could be written to the ACCA (perhaps or ACCB?) and that D would point to the CRC register in cog memory.

This is the CRC calculation in spin for a byte...
```    d := DATA & \$FF
repeat i from 0 to 7
c := (d ^ crc) & \$01                              ' data bit 0 XOR crc bit 0
d := d >> 1                                       ' data >> 1
crc := crc >> 1                                   ' crc  >> 1
if c
crc := crc ^ poly                               ' if c==1: crc xor poly
```

Postedit 29May2015
This is the corrected code for a single bit (msb first)...
```poly=\$8005 and initially crc16=0

c := (d ^ (crc16>>15)) & \$0001 ' data-bit xor crc16[15]

crc16 := (crc16 << 1) & \$FFFF  ' crc16 << 1
if c                           ' c==1?
crc16 := crc16 ^ poly        ' c==1: crc xor poly

```

This is a possible P2 CRC bit accumulate instruction format...
CRCBIT D
where D = CRC Register, C = current data bit, ACCA = polynomial
The CRCBIT instruction performs the following...
(1) X := C XOR D[0]
(2) D := D >> 1
(3) if X == 1 then D := D XOR ACCA

The idea is that for bit-banging, the CRCBIT instruction would be called for each bit sent/received, and the bit would already be in C.
I expect CRCBIT should be capable of being a 1 clock instruction.

So, to accumulate an 8 bit byte (disregarding any reversals and initialisation) the following could be used...
This would take 2+16 clocks per byte, or for 4 bytes in a passed long 2+64 clocks.
```        REPS    #2,#8           '\\ 2 instructions x 8 loops
NOP                     '|| spacer
SHR     DATA, #1  WC    '\\ C:=DATA[0]
CRCBIT  CRC             '// accumulate 1bit into crc
```
This method does not require the CRCBIT instruction to know the number of bits in the algorithm.

CRC6-5MHz.spin

• Posts: 13,853
edited 2013-11-29 16:11
Cluso99,

Implementing an atomic CRC instruction would be easy to do and a good use of resources. Let's do it, along with the special pin instructions to facilitate USB. These are really good ideas that result in almost no silicon growth, but will cut bit-period processing requirements in half for many protocols.
• Posts: 6,445
edited 2013-11-29 16:22
Excellent!!!
cgracey wrote: »
cluso99,

implementing an atomic crc instruction would be easy to do and a good use of resources. Let's do it, along with the special pin instructions to facilitate usb. These are really good ideas that result in almost no silicon growth, but will cut bit-period processing requirements in half for many protocols.
• Posts: 18,063
edited 2013-11-29 16:34
Excellent! Thankks Chip.

BTW How was thatturkey?