Forum - MCS Electronics

 

FAQFAQ SearchSearch RegisterRegister Log inLog in

Does CRC8 work with big strings?

 
Post new topic   Reply to topic    www.mcselec.com Forum Index -> BASCOM-AVR
View previous topic :: View next topic  
Author Message
hzz

Bascom Member



Joined: 20 Feb 2007
Posts: 270

spain.gif
PostPosted: Sat Oct 26, 2019 12:15 pm    Post subject: Does CRC8 work with big strings? Reply with quote

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
View user's profile
MWS

Bascom Member



Joined: 22 Aug 2009
Posts: 1813

blank.gif
PostPosted: Sat Oct 26, 2019 12:49 pm    Post subject: Re: Does CRC8 work with big strings? Reply with quote

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
View user's profile
hzz

Bascom Member



Joined: 20 Feb 2007
Posts: 270

spain.gif
PostPosted: Sat Oct 26, 2019 1:20 pm    Post subject: Reply with quote

Thanks!

I suggets BASCOM to mention it in the next version of the help file.
Regards
Back to top
View user's profile
MWS

Bascom Member



Joined: 22 Aug 2009
Posts: 1813

blank.gif
PostPosted: Sat Oct 26, 2019 3:12 pm    Post subject: Reply with quote

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
View user's profile
hzz

Bascom Member



Joined: 20 Feb 2007
Posts: 270

spain.gif
PostPosted: Sat Oct 26, 2019 8:52 pm    Post subject: ASM ten tiimes more efficient than BASIC!? Reply with quote

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
View user's profile
MWS

Bascom Member



Joined: 22 Aug 2009
Posts: 1813

blank.gif
PostPosted: Sat Oct 26, 2019 10:58 pm    Post subject: Reply with quote

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
View user's profile
hzz

Bascom Member



Joined: 20 Feb 2007
Posts: 270

spain.gif
PostPosted: Sun Oct 27, 2019 12:07 am    Post subject: Reply with quote

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
View user's profile
MWS

Bascom Member



Joined: 22 Aug 2009
Posts: 1813

blank.gif
PostPosted: Sun Oct 27, 2019 12:44 am    Post subject: Reply with quote

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
View user's profile
hzz

Bascom Member



Joined: 20 Feb 2007
Posts: 270

spain.gif
PostPosted: Sun Oct 27, 2019 10:27 am    Post subject: Reply with quote

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
View user's profile
MWS

Bascom Member



Joined: 22 Aug 2009
Posts: 1813

blank.gif
PostPosted: Sun Oct 27, 2019 1:27 pm    Post subject: Reply with quote

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:
Code:
  Inc R21

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
View user's profile
hzz

Bascom Member



Joined: 20 Feb 2007
Posts: 270

spain.gif
PostPosted: Sun Oct 27, 2019 8:48 pm    Post subject: Reply with quote

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:
Code:
        R21 = High(n)


I use:

Code:
        If N = 256 Then
            R21 = 0
        Else
            R21 = High(n)
        End If
 
Back to top
View user's profile
MWS

Bascom Member



Joined: 22 Aug 2009
Posts: 1813

blank.gif
PostPosted: Mon Oct 28, 2019 3:16 am    Post subject: Reply with quote

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:
Code:
  Inc R21

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
View user's profile
hzz

Bascom Member



Joined: 20 Feb 2007
Posts: 270

spain.gif
PostPosted: Mon Oct 28, 2019 10:12 am    Post subject: Reply with quote

Tested and working!
Thanks very much MWS
Back to top
View user's profile
hzz

Bascom Member



Joined: 20 Feb 2007
Posts: 270

spain.gif
PostPosted: Sun Aug 02, 2020 11:44 am    Post subject: CRC8 supports big strings in 2083. Reply with quote

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
View user's profile
Display posts from previous:   
Post new topic   Reply to topic    www.mcselec.com Forum Index -> BASCOM-AVR All times are GMT + 1 Hour
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum