## CRC Calculation

bbc micro/electron/atom/risc os coding queries and routines
Coeus
Posts: 1772
Joined: Mon Jul 25, 2016 12:05 pm
Contact:

### CRC Calculation

I am slightly puzzled by a piece of code to calculate CRCs. In sweh's TubeHost there is this routine, Perl:

Code: Select all

``````sub CalcCRC(\$)
{
my \$crc=0;

foreach my \$c (split(//,\$_[0]))
{
\$crc ^= (256*ord(\$c));
foreach my \$x (0..7)
{
\$crc *= 2;
if (\$crc > 65535)
{
\$crc-=65535; \$crc ^= 0x1020;
}
}
}
return(\$crc);
}``````
That is, I believe, iterating over the characters of string so the core bit is this:

Code: Select all

``````    \$crc ^= (256*ord(\$c));
foreach my \$x (0..7)
{
\$crc *= 2;
if (\$crc > 65535)
{
\$crc-=65535; \$crc ^= 0x1020;
}
}
``````
So it seemed to me that this, translated into 6502 assembler, would be:

Code: Select all

``````        EOR     crc+1	; equivalent to \$crc ^= (256*ord(\$c));
STA     crc+1
LDX     #\$08	; loop as per foreach my \$x (0..7)
txcrcl: ASL     crc	; \$crc *= 2;
ROL     crc+1
BCC     txcrcs	; carry would be set if number was > 65535, i.e. needed 17 bits.
LDA     #\$20	; low half of \$crc ^= 0x1020;
EOR     crc
STA     crc
LDA     #\$10	; high half of \$crc ^= 0x1020;
EOR     crc+1
STA     crc+1
txcrcs: DEX
BNE     txcrcl
RTS
``````
with comments explaining how I see the 6502 code as relating to the Perl code. The only line not translated is the:

Code: Select all

``\$crc-=65535``
only because I assumed not holding the value to more than 16 bits would effectively do this.

But, when I tried running it I noticed that the last hex digit as printed, i.e. the lower nybble of the lower byte of the CRC was always zero and, looking at the 6502 code, it seems plain to me that nothing ever puts bits into that. The same does not seem to be true of the Perl original, though, based on its output so maybe that -= 65535 is doing something else too?

I have found another 6502 version:

Code: Select all

``````TXA
EOR     crc+1
STA     crc+1
LSR     A
LSR     A
LSR     A
LSR     A
TAX
ASL     A
EOR     crc
STA     crc
TXA
EOR     crc+1
STA     crc+1
ASL     A
ASL     A
ASL     A
TAX
ASL     A
ASL     A
EOR     crc+1
STA     crc+1
TXA
ROL     A
EOR     crc
LDX     crc+1
STA     crc+1
STX     crc
RTS
``````
and I have a table-based one too. The non-table-based version is somewhat more complex than the simple translation from the Perl, though quite fast enough on the Beeb. Also, in the documentation the hex value for the value EORed in seems to usually be 0x1021, not 0x1020.

So, either that Perl code is really clever, or does not produce "standard" CRC-16 output. Anyone have any idea as to why?

sweh
Posts: 2238
Joined: Sat Mar 10, 2012 12:05 pm
Location: New York, New York
Contact:

### Re: CRC Calculation

The user guide (page 399 says)
The header CRC acts on all bytes from the filename to the spare bytes inclusive. The data CRC acts on the data only. CRCs are stored high byte first and are calculated as follows. In the following C represents the character and H and L represent the high and low bytes of the CRC.

Code: Select all

``````H=C EOR H
FOR X=1 TO 8
T=0
IF (bit 7 of H=1) THEN HL=HL EOR &0810: T=1
HL=(HL*2+T) AND &FFFF
NEXT X
``````
The above algorithm is not a BASIC program!
The "65535" is meant to take into account the "T=1" part, and &1020 is 2*&810.

But... the more I look at it, the less I'm convinced the perl version matches that algorithm! There may be a bug... I'll need to look at that!
Last edited by sweh on Mon Jan 07, 2019 1:34 am, edited 1 time in total.
Rgds
Stephen

sweh
Posts: 2238
Joined: Sat Mar 10, 2012 12:05 pm
Location: New York, New York
Contact:

### Re: CRC Calculation

So I coded up a test program which I _think_ follows the algorithm more closely...

Code: Select all

``````sub Calc2(\$)
{
my \$hl=0;

foreach my \$c (split(//,\$_[0]))
{
\$hl=(256*ord(\$c)) ^ \$hl;
foreach my \$x (0..7)
{
my \$t=0;
if (\$hl & 32768)
{
\$hl ^= 0x810;
\$t=1;
}
\$hl=(\$hl*2+\$t) & 0xffff
}
}
return \$hl;
}
``````
I then compared the two results with thousands of random strings of random length (but all from upper case characters)

Code: Select all

``````foreach my \$y (0..10000)
{
my \$len=rand(256);
my \$string="";
for (0..\$len) { \$string .= chr( int(rand(25) + 65) ); }

my \$mine=CalcCRC(\$y);
my \$v2=Calc2(\$y);
if (\$mine != \$v2)
{
printf "%04X %04X %s\n",\$mine,\$v2,\$string;
}
}
``````
And the result of the two algorithms is identical.
Rgds
Stephen

jgharston
Posts: 4084
Joined: Thu Sep 24, 2009 12:22 pm
Location: Whitby/Sheffield
Contact:

### Re: CRC Calculation

Optimised 6502 code here (plus loads of other CPUs).

Code: Select all

``````\$ bbcbasic
PDP11 BBC BASIC IV Version 0.32
(C) Copyright J.G.Harston 1989,2005-2020
>_``````

tricky
Posts: 4578
Joined: Tue Jun 21, 2011 9:25 am
Contact:

### Re: CRC Calculation

Subtracting 65535 is the same as adding 1 (T=1?) In 16 bit.

sweh
Posts: 2238
Joined: Sat Mar 10, 2012 12:05 pm
Location: New York, New York
Contact:

### Re: CRC Calculation

tricky wrote:
Mon Jan 07, 2019 12:38 pm
Subtracting 65535 is the same as adding 1 (T=1?) In 16 bit.
Yes, but I had to convince myself that changing the order of operations didn't cause any impact; that is "( crc EOR &810) * 2 + 1" was the same as "(crc *2 -65535) EOR &1020". It was late, last night, but this morning (after my first coffee) I'm feeling happier 'cos the EOR doesn't touch the low bit
Rgds
Stephen

scruss
Posts: 270
Joined: Sun Jul 01, 2018 4:12 pm
Location: Toronto
Contact:

### Re: CRC Calculation

Digest::CRC does the right thing …

BigEd
Posts: 3356
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

### Re: CRC Calculation

Hmm, I'm not sure about that sweh...

Code: Select all

``````(0x1f + 1) EOR 2 = 0x22
(0x1f EOR 2) + 1 = 0x1E
``````

sweh
Posts: 2238
Joined: Sat Mar 10, 2012 12:05 pm
Location: New York, New York
Contact:

### Re: CRC Calculation

You forgot the *2 so the number is always even; (0x1f * 2 +1) EOR 2 and (0x1f *2) EOR 2 + 1 are both 61
Rgds
Stephen

BigEd
Posts: 3356
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

### Re: CRC Calculation

Oh, of course! You're quite right.

Coeus
Posts: 1772
Joined: Mon Jul 25, 2016 12:05 pm
Contact:

### Re: CRC Calculation

I read the replies with interest this morning but not have a chance to reply until now. So, first of all, sorry for wasting your time to prove that the Perl was indeed correct due to a wrong assumption on my part. I hope, though, it has been an interesting discussion for others besides me.

So to be equivalent to a left shift of a 16 bit register the Perl would need to subtract 65536, rather than 65535 and the result of subtracting only 65535 would be equivalent to a 16bit shift and then adding one, and as the LSB is known to be zero, this would indeed be equivalent to EORing a 1 into that position later on, as in the optimised 6502 version JGH linked to which effectively uses &1021. In fact, that version is almost what I had got from translating it from Perl except for me neglecting to use &21 istead of &20, though the JGH version has used the Y register to avoid some/store ops.

So looking at the optimised 6502 version and your Perl version both, seem a little more elegant than the pseudo-BASIC which looks as it has been designed to be implemented in a high level language on a machine with 16 bit words where it is therefore not possible to examine the carry flag and one must thus examine the MSB before it is shifted out rather than after.

BTW, which is the user guide to which you refer which contains this description?

sweh
Posts: 2238
Joined: Sat Mar 10, 2012 12:05 pm
Location: New York, New York
Contact:

### Re: CRC Calculation

Coeus wrote:
Mon Jan 07, 2019 4:03 pm
BTW, which is the user guide to which you refer which contains this description?
The BBC MIcrocomputer User Guide; the one that came with the Beeb
Rgds
Stephen