Fast table driven crc in forth

[Whammo]

\ fast table driven crc in forth

: ftab 8 0 do dup 1 and if
1 rshift $8408 xor \ CRC-16-CCITT Polynomial
else 1 rshift then loop ;

: tomem $ff 0 do
i ftab $c000 \ address of table
i 2* + ! loop ;

tomem

: crctab 2* $c000 + @ ; \ return table entry

: crc_each ( crc c -- newcrc  )     \ init crc to $ffff
over xor $ff and crctab             \ calculate on each char of string 
swap 8 rshift xor ;

: output_crc ( crc -- msb lsb )     \ this returns crc  
dup invert 8 rshift
swap invert $ff and ;

: calc_crc ( addr length -- crc )
over c@ $ffff  \ addr length char $ffff \ init
swap crc_each  \ addr length crc
swap           \ addr crc length
1 do over      \ addr crc addr
i + c@         \ addr crc char  
crc_each loop  \ addr crc
nip output_crc ;

[burnsauce]

Cool! I have a framework I've been using to check for collisions, I'll see how this fares.

[Whammo]

It's missing something..

Nah- it's okay tomem one word

[burnsauce]

Okay, let me know when it's ready. Alternately I can share my collision check code.

[burnsauce]

I might be missing something here, is this a 32-bit crc? I'm getting a double as the output of calc_crc. Or is a 16-bit crc 32-bits long?

[Whammo]

Treat them as bytes. None should be over FF Get Outlook for Android<https://aka.ms/ghei36>

…

________________________________ From: Poindexter Frink ***@***.***> Sent: Tuesday, January 11, 2022 2:22:55 PM To: jkotlinski/durexforth ***@***.***> Cc: Whammo ***@***.***>; Author ***@***.***> Subject: Re: [jkotlinski/durexforth] Fast table driven crc in forth (Discussion #430) I might be missing something here, is this a 32-bit crc? I'm getting a double as the output of calc_crc. — Reply to this email directly, view it on GitHub<#430 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AJEFWZ7QTMFO47DEAH2OJULUVSUT7ANCNFSM5LXJGBJQ>. Triage notifications on the go with GitHub Mobile for iOS<https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android<https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you authored the thread.Message ID: ***@***.***>

[burnsauce]

Can I just combine them together into a 16-bit int instead?

[Whammo]

You may but this is a special checksum. Run the string, and save the checksum Then run the string again followed by the individual two bytes of the saved checksum That checksum will be the same as any unchanged strings checksum. $f0b8 Get Outlook for Android<https://aka.ms/ghei36>

…

________________________________ From: Poindexter Frink ***@***.***> Sent: Tuesday, January 11, 2022 2:28:09 PM To: jkotlinski/durexforth ***@***.***> Cc: Whammo ***@***.***>; Author ***@***.***> Subject: Re: [jkotlinski/durexforth] Fast table driven crc in forth (Discussion #430) Can I just combine them together into a 16-bit int instead? — Reply to this email directly, view it on GitHub<#430 (reply in thread)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AJEFWZ6CJ6ICEBB6ZAZCG73UVSVHTANCNFSM5LXJGBJQ>. Triage notifications on the go with GitHub Mobile for iOS<https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android<https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you authored the thread.Message ID: ***@***.***>

[Whammo]

Just change the two addresses as you please. Get Outlook for Android<https://aka.ms/ghei36>

…

________________________________ From: Poindexter Frink ***@***.***> Sent: Tuesday, January 11, 2022 2:56:01 PM To: jkotlinski/durexforth ***@***.***> Cc: Whammo ***@***.***>; Author ***@***.***> Subject: Re: [jkotlinski/durexforth] Fast table driven crc in forth (Discussion #430) Is there a way to move this out of $c000 or is that the magic of $8408 xor? — Reply to this email directly, view it on GitHub<#430 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AJEFWZZMAQHK23XYZNQ7HZLUVSYQDANCNFSM5LXJGBJQ>. Triage notifications on the go with GitHub Mobile for iOS<https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android<https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you authored the thread.Message ID: ***@***.***>

[burnsauce]

Unfortunately this will not work as a hash. lda, and included produce the same crc.

Good code for error detection though!

[Whammo]

It's the PPP CRC Rfc 1661

[Whammo]

You might have better results if you pad the strings to a fixed length with a repeatable sequence.

[burnsauce]

Is there a magic string that makes for good padding? Whatever I try isn't helping.

[burnsauce]

Wait, no I had a bug.

[burnsauce]

There's going to have to be some magic in the padded data.

Unsurprisingly, the crc of lit and litc are the same when the pad string is AbBcCdD...

Unprintable characters maybe?

[Whammo]

Primes?

[burnsauce]

Using the 31 largest primes below 255 in sequence produces collisions just as quickly.

[Whammo]

EOR with the colliding string.

[Whammo]

But... you would have to keep track of that.... 1 128 ...

[Whammo]

Last char rshift lshift or 1 lshift lshift lshift... Any operations that are reproduceable.

[Whammo]

Or go back to the collisions, pad them equally or inversely 'til they don't match anything anymore.

[Whammo]

Then there is not resetting the CRC for each word, or resetting every word, or every other word...
Sorry, just brimming with bad ideas.

[burnsauce]

NO COLLUSION!

Sorry, couldn't help myself.

[Whammo]

What was it?

[burnsauce]

I haven't tried any of those yet. I was making a joke about your typo.

[Whammo]

Typo? Heh!