Page 1 of 1

CRC Calculation

Posted: Mon Jan 07, 2019 12:39 am
by Coeus
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?

Re: CRC Calculation

Posted: Mon Jan 07, 2019 1:30 am
by sweh
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!

Re: CRC Calculation

Posted: Mon Jan 07, 2019 1:53 am
by sweh
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.

Re: CRC Calculation

Posted: Mon Jan 07, 2019 8:44 am
by jgharston
Optimised 6502 code here (plus loads of other CPUs).

Re: CRC Calculation

Posted: Mon Jan 07, 2019 12:38 pm
by tricky
Subtracting 65535 is the same as adding 1 (T=1?) In 16 bit.

Re: CRC Calculation

Posted: Mon Jan 07, 2019 2:34 pm
by sweh
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

Re: CRC Calculation

Posted: Mon Jan 07, 2019 2:46 pm
by scruss
Digest::CRC does the right thing …

Re: CRC Calculation

Posted: Mon Jan 07, 2019 3:02 pm
by BigEd
Hmm, I'm not sure about that sweh...

Code: Select all

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

Re: CRC Calculation

Posted: Mon Jan 07, 2019 3:17 pm
by sweh
You forgot the *2 so the number is always even; (0x1f * 2 +1) EOR 2 and (0x1f *2) EOR 2 + 1 are both 61

Re: CRC Calculation

Posted: Mon Jan 07, 2019 3:50 pm
by BigEd
Oh, of course! You're quite right.

Re: CRC Calculation

Posted: Mon Jan 07, 2019 4:03 pm
by Coeus
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?

Re: CRC Calculation

Posted: Mon Jan 07, 2019 4:27 pm
by sweh
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 :-)