CRC Calculation

Discuss all aspects of programming here. From 8-bit through to modern architectures.
Post Reply
Coeus
Posts: 1402
Joined: Mon Jul 25, 2016 11:05 am
Contact:

CRC Calculation

Post by Coeus » Mon Jan 07, 2019 12:39 am

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?

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

Re: CRC Calculation

Post by sweh » Mon Jan 07, 2019 1:30 am

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

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

Re: CRC Calculation

Post by sweh » Mon Jan 07, 2019 1:53 am

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

User avatar
jgharston
Posts: 3753
Joined: Thu Sep 24, 2009 11:22 am
Location: Whitby/Sheffield
Contact:

Re: CRC Calculation

Post by jgharston » Mon Jan 07, 2019 8:44 am

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

Code: Select all

$ bbcbasic
PDP11 BBC BASIC IV Version 0.25
(C) Copyright J.G.Harston 1989,2005-2015
>_

User avatar
tricky
Posts: 3815
Joined: Tue Jun 21, 2011 8:25 am
Contact:

Re: CRC Calculation

Post by tricky » Mon Jan 07, 2019 12:38 pm

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

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

Re: CRC Calculation

Post by sweh » Mon Jan 07, 2019 2:34 pm

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: 155
Joined: Sun Jul 01, 2018 3:12 pm
Location: Toronto
Contact:

Re: CRC Calculation

Post by scruss » Mon Jan 07, 2019 2:46 pm

Digest::CRC does the right thing …

User avatar
BigEd
Posts: 2688
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: CRC Calculation

Post by BigEd » Mon Jan 07, 2019 3:02 pm

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

Code: Select all

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

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

Re: CRC Calculation

Post by sweh » Mon Jan 07, 2019 3:17 pm

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

User avatar
BigEd
Posts: 2688
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: CRC Calculation

Post by BigEd » Mon Jan 07, 2019 3:50 pm

Oh, of course! You're quite right.

Coeus
Posts: 1402
Joined: Mon Jul 25, 2016 11:05 am
Contact:

Re: CRC Calculation

Post by Coeus » Mon Jan 07, 2019 4:03 pm

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?

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

Re: CRC Calculation

Post by sweh » Mon Jan 07, 2019 4:27 pm

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

Post Reply