View previous topic :: View next topic |
Author |
Message |
hzz
Joined: 20 Feb 2007 Posts: 314
|
Posted: Sat Oct 26, 2019 12:15 pm Post subject: Does CRC8 work with big strings? |
|
|
I have compared the results of BASCOM CRC8 function with the CRC-8/MAXIM function in https://crccalc.com/ which I normally use to test.
The results are the same with strings up to 254 characters but are different for strings larger than 256 characters
Does CRC8 work with big strings?
If YES Does anyone know a web CRC8 calculator that works with big strings? (as it seems CRC-8/MAXIM function in https://crccalc.com/ doesn't)
If NOT Is there a workaround?
Here are some values obtained
Length......Value obtained with CRC8......Value obtained with crccalc.com
1............................ 164............................ 164
2............................ 106............................ 106
3............................ 191............................ 191
4............................ 215............................ 215
255......................... 164............................ 164 same as with lenght 1
256......................... 106............................ 106 same as with lenght 2
257......................... 164............................ 191 different!
258......................... 106............................ 215 different!
259......................... 191............................ 112 different!
260......................... 215............................ 92 different!
This is the BASCOM program I used
Code: | '____________________________________________________________________________________
$regfile = "xm256a3Udef.dat" ' ATxmega256A3U
'____________________________________________________________________________________
$hwstack = 256
$swstack = 128
$framesize = 128
'____________________________________________________________________________________
' CONFIG SYSTEM CLOCK
Config Osc = Disabled , Extosc = Enabled , Range = 12mhz_16mhz , Startup = Xtal_16kclk , 32khzosc = Enabled , Pllosc = Enabled , Pllsource = Extclock , Pllmul = 2 ' 16x2=32MHz
Config Sysclock = Pll , Prescalea = 1 , Prescalebc = 1_1 ' 32/1=32 MHz
$crystal = 32000000
Const Fclock = 32000000
'____________________________________________________________________________________
$bigstrings
'____________________________________________________________________________________
' VARIABLES
Dim Test_string As String * 300
Dim N As Word
Dim Btemp As Byte
'____________________________________________________________________________________
For N = 1 To 300
Test_string = Test_string + "C"
Next N
For N = 254 To 300
Btemp = Crc8(test_string , N)
Next N
|
(BASCOM-AVR version : 2.0.8.1 , Latest : 2.0.8.2 ) |
|
Back to top |
|
|
MWS
Joined: 22 Aug 2009 Posts: 2262
|
Posted: Sat Oct 26, 2019 12:49 pm Post subject: Re: Does CRC8 work with big strings? |
|
|
hzz wrote: | Does CRC8 work with big strings? |
No. In assembly only the lower byte of N is used for CRC8 as forwarded parameter. |
|
Back to top |
|
|
hzz
Joined: 20 Feb 2007 Posts: 314
|
Posted: Sat Oct 26, 2019 1:20 pm Post subject: |
|
|
Thanks!
I suggets BASCOM to mention it in the next version of the help file.
Regards |
|
Back to top |
|
|
MWS
Joined: 22 Aug 2009 Posts: 2262
|
Posted: Sat Oct 26, 2019 3:12 pm Post subject: |
|
|
hzz wrote: | I suggets BASCOM to mention it in the next version of the help file. |
It actually is, however indirectly:
Quote: | ASM
...
The routine must be called with Z pointing to the data and R24 must contain the number of bytes to check. |
If you know that we have an 8bit processor and registers are 8bit wide, you will know how big the value in R24 can be. |
|
Back to top |
|
|
hzz
Joined: 20 Feb 2007 Posts: 314
|
Posted: Sat Oct 26, 2019 8:52 pm Post subject: ASM ten tiimes more efficient than BASIC!? |
|
|
Thanks,
The beauty of BASCOM is that you do not have to know anything about ASM; lets keep it!
In order to be able to work with strings larger than 255 Bytes I have implemented a CRC8 routine as indicated in the help file. It works fine but it is so much slower than the ASM routine.
Calculating the CRC8 of a 250 Bytes string takes 0,64ms with BASCOM's CRC8 ASM routine and 6,7ms with the BASIC routine implemented in BASCOM,
Is it because the CRC8 is a better routine or because ASM itself is ten times more efficient than BASIC? (I hope not the later) |
|
Back to top |
|
|
MWS
Joined: 22 Aug 2009 Posts: 2262
|
Posted: Sat Oct 26, 2019 10:58 pm Post subject: |
|
|
I do not know your routine, thus I do not know if it is worse or less effective.
Part of slower execution results of how the compiler translates commands into assembler.
A for/next loop will have a few operations to load/compare/modify/save the counter variable from/to SRam, in assembler one can keep the counter variable within register/s, keeping SRam access at a minimum.
The loop can be made in the easiest case with one conditional branch, that very much speeds it up.
Assembler routines are tailored to the purpose, makes them fast and perfect for reusable routines, libs a.s.o., however it's comparably harder to use assembler for complex/custom code.
Somebody doing assembler a whole live will of course disagree, while others like you may be with me. |
|
Back to top |
|
|
hzz
Joined: 20 Feb 2007 Posts: 314
|
Posted: Sun Oct 27, 2019 12:07 am Post subject: |
|
|
Thanks again!
I'm almost sure I have compared in the past functions made in BASCOM BASIC with the same BASCOM function in ASM and the diffrerence in execution time was not that much (not ten times faster as it happens with CRC and I doubt it was even twice faster) so there must be a specific reason for the CRC ASM function being so fast.
The following is my working code for a CRC8 routine that works with big strings.
Code: | '________________________________________________________________________________
' CALCULAR CRC8 RX OK
' INPUTS:
' Trama_rx7() = STX + Message type + Data bytes
' Nbytes_crc Number of bytes to use to calculate the CRC8 (all excepct STX)
' ' OUTPUTS
' Crc_calculado
' It takes 6,7ms for a 250 character string
'________________________________________________________________________________
Calcular_crc8_rx:
Dim Jcrc As Byte
Dim Kcrc As Byte
Dim Mcrc As Word
Dim Xcrc As Byte
Dim Crc_last_byte As Word
Crc_last_byte = Nbytes_crc + 1 ' Last byte position
Crc_calculado = 0
For Mcrc = 2 To Crc_last_byte ' We want to calculate the CRC8 from the second byte to the Last byte position
Xcrc = Trama_rx7(mcrc)
For Kcrc = 0 To 7
Btemp = Xcrc Xor Crc_calculado
Jcrc = 1 And Btemp
Shift Crc_calculado , Right
Crc_calculado = Crc_calculado And &HFF
Shift Xcrc , Right
Xcrc = Xcrc And &HFF
If Jcrc <> 0 Then
Crc_calculado = Crc_calculado Xor &H8C
End If
Next Kcrc
Next Mcrc
Return |
I have seen in Internet that there is a way to make it faster using a lookup table, I wonder if someone have impmemented it in BASCOM.
Regards |
|
Back to top |
|
|
MWS
Joined: 22 Aug 2009 Posts: 2262
|
Posted: Sun Oct 27, 2019 12:44 am Post subject: |
|
|
You can find out which lines eat up the most computing power by doing a simulation.
Also I think the easiest way for a fast solution is to borrow the CRC-function from mcs.lib and extend the counter R24 to R24/R25. |
|
Back to top |
|
|
hzz
Joined: 20 Feb 2007 Posts: 314
|
Posted: Sun Oct 27, 2019 10:27 am Post subject: |
|
|
hanks again,
Quote: | You can find out which lines eat up the most computing power by doing a simulation. |
All instructions are simple, running all of them takes little more than 3,3us, the problem is that a 300 bytes long strings take 300x8=2400 iterations @3,3us is already ~8ms
Quote: | Also I think the easiest way for a fast solution is to borrow the CRC-function from mcs.lib and extend the counter R24 to R24/R25. |
Yes, it will be the best solution but I don't trust myself in ASM |
|
Back to top |
|
|
MWS
Joined: 22 Aug 2009 Posts: 2262
|
Posted: Sun Oct 27, 2019 1:27 pm Post subject: |
|
|
hzz wrote: | All instructions are simple |
The Shift is a bit more hungry for cycles.
Quote: | Yes, it will be the best solution but I don't trust myself in ASM |
Oh, in this case it is pretty easy.
Assuming it is not desired to publish parts of mcs.lib to the forum, I will describe only the modifications.
Open mcs.lib, search for [_CRC8], copy the complete routine included [_CRC8] and [END] to a text file.
Rename the text file to crc8_extd.lib and put it into Bascom's lib directory which can be found under Bascom's installation directory.
Immediately after _Crc8: insert:
Immediately in front of Ret insert:
Code: | Dec R21 ; decrease high byte of number of bytes to check
Brne _Crc8_Bytes ; loop bytes |
Use the following code to test:
Code: | '____________________________________________________________________________________
$regfile = "xm256a3Udef.dat" ' ATxmega256A3U
'____________________________________________________________________________________
$hwstack = 256
$swstack = 128
$framesize = 128
$lib "crc8_extd.lib"
'____________________________________________________________________________________
' CONFIG SYSTEM CLOCK
Config Osc = Disabled , Extosc = Enabled , Range = 12mhz_16mhz , Startup = Xtal_16kclk , 32khzosc = Enabled , Pllosc = Enabled , Pllsource = Extclock , Pllmul = 2 ' 16x2=32MHz
Config Sysclock = Pll , Prescalea = 1 , Prescalebc = 1_1 ' 32/1=32 MHz
$crystal = 32000000
Const Fclock = 32000000
'____________________________________________________________________________________
$bigstrings
'____________________________________________________________________________________
' VARIABLES
Dim Test_string As String * 300
Dim N As Word
Dim Btemp As Byte
'____________________________________________________________________________________
For N = 1 To 15
Test_string = Test_string + "ABCDEFGHIJKLMNOPQRST"
Next N
For N = 1 To 300
R21 = high(N)
Btemp = Crc8(test_string , N)
Print N; " "; Btemp
Next N |
Make sure that every call to Crc8(test_string , N) is immediately preceded by R21 = high(N).
The $lib "crc8_extd.lib" overrides the CRC8 function from mcs.lib, this way you don't need to alter mcs.lib and code not including the extd lib behaves as before. |
|
Back to top |
|
|
hzz
Joined: 20 Feb 2007 Posts: 314
|
Posted: Sun Oct 27, 2019 8:48 pm Post subject: |
|
|
Thanks!
It is fast and gives correct results except for strings 256 characters long ¿!? . For longer or smaller strings it works great
I have solved it as follows
Instead of:
I use:
Code: | If N = 256 Then
R21 = 0
Else
R21 = High(n)
End If
|
|
|
Back to top |
|
|
MWS
Joined: 22 Aug 2009 Posts: 2262
|
Posted: Mon Oct 28, 2019 3:16 am Post subject: |
|
|
hzz wrote: |
I use:
Code: | If N = 256 Then
R21 = 0
Else
R21 = High(n)
End If
|
|
It's a botchery only required because there was a flaw in my counting down code.
Can be done better and cleanly.
Alter crc8_extd.lib as follows, remove:
Replace the lower block against:
Code: | _Crc8_NoPoly:
Dec R25 ; dec bit counter
Brne _Crc8_Bits ; loop bits
Subi R24, 1 ; dec counter low byte
Sbci R21, 0 ; apply carry to counter high byte
Brne _Crc8_Bytes ; loop bytes
Ret
[END] |
|
|
Back to top |
|
|
hzz
Joined: 20 Feb 2007 Posts: 314
|
Posted: Mon Oct 28, 2019 10:12 am Post subject: |
|
|
Tested and working!
Thanks very much MWS |
|
Back to top |
|
|
hzz
Joined: 20 Feb 2007 Posts: 314
|
Posted: Sun Aug 02, 2020 11:44 am Post subject: CRC8 supports big strings in 2083. |
|
|
In BASCOM version 2083 big strings are supported by CRC8; thererore, there is no need to use crc8_extd.lib anymore. Thanks BASCOM! |
|
Back to top |
|
|
|