KERNAL CRC call (not sure if right)

[Xiphod]

I was trying to put together an example of using the X16 KERNAL CRC16 call.

I do get a result that varies with different strings. But have a question down below...

Here's the setup I used (BASLOAD):

EDIT/NOTE: The following sample is revised from the original. The issue was found and the correction is now applied to this example. The issue was that the KERNAL CRC call operates "in reverse" for small data under 256 bytes, which all BASIC strings can be at most is 256 bytes. BASIC strings aren't restricted to ASCII/PETSCII sequences, and can any character value 0-255 (and other characteristics like a normal array).

Code: Select all

SAMPLE$=CHR$(1)+CHR$(2)+CHR$(3)+CHR$(4)

REM AS OF R48 IT WAS DETERMINED THAT THE KERNAL CRC CALCULATION
REM OPERATES "IN REVERSE" FOR DATA UNDER 256 BYTES.  THEREFORE,
REM TO BE COMPATIBLE WITH EXTERNAL SYSTEMS THAT ARE UNAWARE OF THIS,
REM IT WOULD BE PRUDENT TO REVERSE THE STRING SO THAT THE KERNAL CRC
REM RESULT WILL BE CONSISTENT WITH THOSE EXTERNAL SYSTEMS.

REM ONE PROPOSED WAY TO REVERSE THE STRING:
SAMPLE.REVERSE$ = ""
FOR I = LEN(SAMPLE$) TO 1 STEP -1
  SAMPLE.REVERSE$ = SAMPLE.REVERSE$ + MID$(SAMPLE$,I,1)
NEXT I

AD=POINTER(SAMPLE.REVERSE$)

STR.SZ=PEEK(AD)    : REM SIZE(LENGTH) IS FIRST BYTE
STR.LO=PEEK(AD+1)
STR.HI=PEEK(AD+2)
STR.ADDR=(STR.HI*256)+STR.LO

PRINT "STR @ [";HEX$(STR.ADDR);"]",STR.SZ
FOR I = STR.ADDR TO STR.ADDR+(STR.SZ-1)
  V = PEEK(I)
  PRINT HEX$(V);" ";
NEXT I
PRINT

REM ---------------------

REG.R0.LO=$02
REG.R0.HI=$03

REG.R1.LO=$04
REG.R1.HI=$05

REG.R2.LO=$06
REG.R2.HI=$07

KERNAL.CRC = $FEEA

REM ---------------------

POKE REG.R0.HI, STR.HI
POKE REG.R0.LO, STR.LO

POKE REG.R1.HI, $00
POKE REG.R1.LO, 4 : REM STR.SZ   : REM BASIC STRINGS LIMITED TO 256 BYTES MAX.

SYS $FEEA : REM KERNAL.CRC

CRC.HI = PEEK(REG.R2.HI)
CRC.LO = PEEK(REG.R2.LO)

CRC.VALUE = CRC.HI*256+CRC.LO

PRINT HEX$(CRC.VALUE)

Here's some notes from the call in the KERNAL code:

Code: Select all

;---------------------------------------------------------------
; memory_crc
;
; Function:  Calculate the CRC16 of a memory region.
;
; Pass:      r0   address
;            r1   number of bytes
;
; Return:    r2   CRC16 result
;---------------------------------------------------------------
memory_crc:
	lda #$ff
	sta r2L
	sta r2H
.....
@4:	rts

; This is taken from
; http://www.6502.org/source/integers/crc-more.html
; (November 23rd, 2004, "alternate ending" version, preserving .Y)
crc16_f:
	eor r2H         ; A contained the data
	sta r2H         ; XOR it into high byte
....

I went to the 6502.org reference link mentioned in the code. Spot checking the code, it does seem Steil followed that reference exactly (the alternate part that preserves Y). But in that reference, it has this note:

Code: Select all

With a starting CRC of $FFFF, the binary string $01 $02 $03 $04 should evaluate to $89C3.

But, when I use this - I think I'm giving a string as described above, but the CRC result is $6122 instead of $89C3. So, not 100% sure if I'm using this right.


EDIT: Tentatively, it looks like the KERNAL code is "seeding" the CRC with $FFFF ? Just based on the first few lines the LDA #$FF and storing those into R2 (which is the output register).

crc.jpg (139.1 KiB) Viewed 6833 times

And, I have reason to believe the $89C3 might be correct, based on this site that does a bunch of variety of CRC16 results (it matches the old IBM3740 version). There are a bunch of different ways to do CRC16 (I mean constants to plugin), and I wanted to understand which variation the KERNAL is doing - which then from Python or C# or Java or something I'll need an equivalent CRC16 calculator {or write one}).

crc2.jpg (238.47 KiB) Viewed 6833 times

[Eirik Stople]

Yes, KERNAL generates a CRC-16 that matches "CRC-16/IBM-3740". I used this online calculator to simplify the task of precompute the checksums for different versions of the SMC bootloader, ref https://github.com/X16Community/x16-smc ... r-tools.md

Here is how the bootloader dumper computes the checksum, using KERNAL:

https://github.com/X16Community/x16-smc ... D8.BAS#L25

[Xiphod]

For reference, here is how Python can be used to also make this style of CRC16:

Code: Select all

import crcmod
...
    ascii_values = [1, 2, 3, 4] 
    data = ''.join(chr(value) for value in ascii_values)
    crc16 = crcmod.mkCrcFun(0x11021, 0xffff, False, 0x0000)
    crc_value = crc16(data.encode())
    print(hex(crc_value))

Which this example results in showing 0x89c3

[Xiphod]

Here is how the bootloader dumper computes the checksum, using KERNAL:

Thanks - so far it seems we're consistent on how we're using the $FEEA CRC call.

Still stumped on why I'm getting $6122 instead of $89C3 for this example. I verified the string is at the address stated, and it does have the expected content (i.e. numeric 1 2 3 4 in sequence, not the ASCII equivalent of '1' '2' '3' '4'). And I simplified the calls on the thought that maybe extraneous BASIC calls stomp over R2 (like explicitly using PEEK(7)*256+PEEK(6) like you did), but still same result.

[Stefan]

I created a simple CRC calculating function used in the X16 Upgrade program. Its output matches the Kernal's:

Code: Select all

def crc16(crc, data):
    p = 0x1021
    crc ^= (data << 8)
    for i in range(8):
        if crc & 0x8000:
            crc = (crc << 1) ^ p
        else:
            crc = crc << 1
    return (crc & 0xffff)

This functions takes the current CRC value as input, one byte of data, and returns the updated CRC value. When calling the function the first time, you give it the initial CRC value of 0xffff.

I'm not familiar with python crcmod, but the param 0x11021 (polynom?) looks suspicious; shouldn't it be 0x1021 in order to match the Kernal function?

[Xiphod]

In the Python using crcmod, when just using 0x1021 I would get this error:
"ValueError: The degree of the polynomial must be 8, 16, 24, 32 or 64"

So then I came across this note by the author of that crcmod:

"Ray Buvel - 2006-08-05
Some applications like to leave off the leading coefficient of the generator polynomial since it is always 1 and doesn't get used in the internals of the algorithm. However, when they do this, the user is required to specify another parameter that determines the width of the CRC. I chose to require the specification of the entire polynomial and derive the size from this input.

If you go to the site referenced, you will see that they list the polynomial corresponding to 0x8005 as x^16+x^15+x^2+1. The full encoding of this polynomial is 0x18005 and this is what you need to enter. So the input line should be changed to

crc16 = crcmod.mkCrcFun(0x18005,0x0000,True)

Then everything will work as expected."

So apparently it is a quirk of the crcmod library that the "1" prefix is necessary. I didn't look into if there is any more recent CRC library for Python, just went with the first one found. Thanks for the other code- I'm thinking of adding CRC checks to my GETFILESN project. I probably won't do "file-resume downloading", but I can at least abort a transfer if something doesn't checksum part way through. So I'll need an equivalent function outside of the X16 KERNAL to put in the send-file utility to produce those checksums and prepend them to each transferred block.



To Eirik Stople's BASIC code - running that on the X16 emulator, I get "BOOTLOADER MISSING" which is not surprising.

When I run it on my R48 upgraded hardware (PR15), I get $15C7 BOOT LOADER V2 (not surprising).

But when I run it on my other R47 hardware (PR17), it just gets $FF's and also outputs "BOOTLOADER MISSING". Curious on how to interpret that.

[Xiphod]

Let's make it simpler. The following is equivalent to the earlier BASLOAD, in that the CRC of the sequence 1234 is evaluated to $6122

Code: Select all

5 REM SET SOME DATA SEQUENCE TO CRC
10 POKE $0400,1
20 POKE $0401,2
30 POKE $0402,3
40 POKE $0403,4

45 REM SET R0 TO $0400
50 POKE 2,$00
60 POKE 3,$04

65 REM SET R1 TO $0004 (4 BYTE COUNT OF THE DATA SET EARLIER)
70 POKE 5,0 : REM HI
80 POKE 4,4 : REM LO

90 SYS $FEEA   : REM CALCULATE CRC USING 4 BYTES STARTING AT $0400

100 C=PEEK(7)*256+PEEK(6)  : REM COMBINE HI/LO OF KERNAL CALL RESULT IN R2 TO A 16-BIT CRC RESULT

110 PRINT HEX$(C)

I've run this across three X16's and each one (different ROMs) is giving a different CRC result (none of which is the expected value of $89c3) (edit update: this has been fixed)

[Stefan]

POKE 5,4 => lenght is $0400, isn’t it?

[Xiphod]

That's probably it, Hi/Lo backwards and would explain the different results (different memory content in startup).
I'll try it in a bit. TY!
EDIT: Ya, ok each system matching the $6122.

Ok, whatever the KERNAL is doing, it's "seeded" by $FFFF but isn't quite the same as that IBM3740 result ?

[Xiphod]

For reference, the C version of Stefan's example earlier.

Code: Select all

#include <stdio.h>

typedef unsigned short CRC16TYPE;
void crc16(CRC16TYPE* crc, char data)
{
  CRC16TYPE p = 0x1021;
  (*crc) ^= (data << 8);
  for (unsigned char i = 0; i < 8; ++i)
  {
    if ((*crc) & 0x8000)
    {
      (*crc) = ((*crc) << 1) ^ p;
    }
    else
    {
      (*crc) = (*crc) << 1;
    }    
  }  
}

int main()
{ 
  CRC16TYPE crc = 0xffff;  
  crc16(&crc, 1);  printf("%X\n", crc);
  crc16(&crc, 2);  printf("%X\n", crc);
  crc16(&crc, 3);  printf("%X\n", crc);
  crc16(&crc, 4);  printf("%X\n", crc);  
}

Which yes, is getting the expected $89C3 result. But I'm still saying that the KERNAL $FEEA CRC16 call isn't giving me the this same result (I get $6122 instead; at least, when I do so from BASIC). I guess I can try to POKE in a more direct raw assembly call of it, that might tell if the "BASIC-engine" is the cause of some kind of interference (is it guaranteed nothing in KERNAL BASIC uses the Rx 16-bit registers?)