I don't know where that line came from, but thanks for correcting me. Why did you add a 0 byte at the end, to shift the remainder into?
I have my .net program mostly done, but it is outputting more polys than your code does, so something is wrong with it. In an attempt to debug and correct my program, I chose a random poly for my program (100000100) with the same hex string of 53D2C800E9. My program outputs 0101001111010010110010000000000011101001 (53D2C800E9) with the poly 100000100 equals 000000000. I believe it does this incorrectly, because when I do it by hand I also get 000000000, so it is wrong because of something flawed with the way I'm doing it? I've tried to follow your method and the wiki example and both ways I do not get the correct answer per the online calculator. Then I tried to reread about the CRC method to see if I could figure out on my own what I'm doing wrong, but to no success.
I have tried this at least 12 times today, to make sure I wasn't making the mistake of adding an extra line in again and I'm really not sure what is wrong.
I don't know where that line came from, but thanks for correcting me. Why did you add a 0 byte at the end, to shift the remainder into?
Which 0 byte did I add where?
One of the rules with crc polynomials is that they always begin and end with a set bit, as mentioned in the wikipedia article. The online calculator seems to assume that the lsb is set, as it produces the same result with %100000101 as it does with %100000100.
As for why you were getting 000000000 when doing it by hand, you're shifting too many places - stop after all of the bits have been shifted.
...
001010011_01001 ' 5 bits remain to be shifted
101001101_001 ' 3
100000100
001001001_001 ' 3
100100100_1 ' 1
100000100
000100000_1 ' 1
100000100 ' shifted too far - should've stopped at 001000001 = $41
100000100
000000000
A minor modification to my crc calculator routine - which doesn't assume anything about the polynomial - leaves $41 in the crc_result.
So the online calculator treats 100000100 as 100000101, as it sets the lsb to 1 in the code?
Seeing that the calculator says that using a poly of 100000100 or 100000101 = 11001100 ($cc), is it wrong?
I modified your code (I think correctly) and using a poly of 100000101, the remainder is 00111100 ($3c). Using a poly of 100000100, the remainder is 001000001 ($41). How did you know to stop at 001000001, because there were only 7 bits left when you do not, after removing the leading zeros?
I will reread the wiki page again to try and make sure I know all of the CRC polynomial rules.
Neither calculator is wrong, they just use slightly different rules. The online crc calculator automatically pads every string with enough bits to complete the calculation. My object requires the padded bits to be entered into the string.
With my object, $53D2C800E9_00 does come out to $CC with the polynomial $105, which is how the online one sees $104.
online: myobject: (using $113 as the poly)
$5 = $5F $500 = $5F
$55F = $00 $55F = $00
The reason why both work for verifying $55F = $00 is that a string which is valid after n bits is still going to be valid after n + x clear bits.
$55F000000000000000... also equals 0.
What the online thing is really converting is:
$500 = $5F
$55F00 = $00
How did you know to stop at 001000001, because there were only 7 bits left when you do not, after removing the leading zeros?
I knew to stop because there was only a single bit remaining to be shifted. Stop after all of the bits have been shifted, that's it. If the bits are a,b,c,d, shift them into the working register (crc_result) until d is in the lsb, not until a is in the msb.
000000000_abcd gets shifted to 00000abcd.
If it helps, count the number of bits in the bitstream: $55F has 12 bits.
|5-||--5F--| shift_counter
000000000_010101011111 start
000000000_10101011111 1
000000001_0101011111 2
000000010_101011111 3
000000101_01011111 4
000001010_1011111 5
000010101_011111 6
000101010_11111 7
001010101_1111 8
010101011_111 9
101010111_11 10
100010011
001000100_11
010001001_1 11
100010011_ 12 - all bits have been shifted, still need to check bit8 and xor if set
100010011
000000000_ Finished!
I'm still a little fuzzy on what the online calc is doing differently. Does the online calculator take hex converted to binary, count the length of the binary digits, divide it by 8 and then determine the number of zeros it needs to pad to the right of the original binary, to have no remainder for that division? I believe this is wrong based on what I have shown below.
So 5 (0101) would be converted to 01010000 by the online program or 01011111?
5 = 5f or 0101 = 01011111
f5 = 4e or 01011111 = 01001110
5ff = 4d or 010111111111 = 01001101
500 = 5f or 010100000000 = 010111111111
The good news is that I have the .net program matching outputs from your program in all of my tests ... and a much better understanding of what your code does
I have a decode method working with an indexer as to how frequent a poly comes up within a list of hex phrases, but I have not thoroughly tested it well. Is it correct (as a rule) that a crc8 has to start the polynomial xoring at 100000000 ?
I'm still a little fuzzy on what the online calc is doing differently. Does the online calculator take hex converted to binary, count the length of the binary digits, divide it by 8 and then determine the number of zeros it needs to pad to the right of the original binary, to have no remainder for that division? I believe this is wrong based on what I have shown below.
So 5 (0101) would be converted to 01010000 by the online program or 01011111?
Hex converted to binary divided by 8... I have no idea what you're asking there.
By converted do you mean the result of the computation? The result of $5 with with the polynomial $113 is $5F. Perhaps you mean the value with the padded bits? Since the polynomial is 9 bits, the result will be 8 bits, so the padded value would be $500. Wikipedia also explains that under the computation section. You can also see this on the online calculator, notice how the number of bits in the binary result is one less than the number of bits in the polynomial?
5 = 5f or 0101 = 01011111 - correct
f5 = 4e or 01011111 = 01001110 -correct
5ff = 4d or 010111111111 = 01001101 -correct
500 = 5f or 010100000000 = 010111111111 -???
The good news is that I have the .net program matching outputs from your program in all of my tests ... and a much better understanding of what your code does
I have a decode method working with an indexer as to how frequent a poly comes up within a list of hex phrases, but I have not thoroughly tested it well. Is it correct (as a rule) that a crc8 has to start the polynomial xoring at 100000000 ?
Right, a crc-8 is 9 bits - and only odd, so start from $101 and check every other poly up to $1FF.
Here's a new version of my calculator that behaves more like the online calculator; automatically pads the value depending on the length of the polynomial. CRC calculator 3.spin
Ok, so what I'm fuzzy on is with the different outputs. Does the online calculator always ensure the last polynomial bit is a 1? Is that what it is doing?
What is the difference between the outputs of your 1st calculator and 3rd?
5 with $113 / 100010011
OnlineCalc = 5f / 01011111
Crc calculator3 = 5f / 001011111
My program = 5 / 101
Cr calculator1 = 5 / 101
The difference between calculator 1 (& 2) and calculator 3 is that 1 & 2 require the padded bits to be entered into the string, calculator 3 automatically pads with the required number of bits.
In the get_crc method, after it has looped through all of the bits of all of the nibbles from all of the characters in the string, the program enters a second loop:
repeat >| poly - 1 ' repeat this loop for all bits in the polynomial - 1. For a 9-bit crc (crc-8), this repeats 8 times. Go ahead and replace this with [b]repeat 8[/b] if ya want.
crc_result <<= 1 ' The rest of this is just like the code that appends bits from nib, except here all we need to do is pad with 0's, which is what happens during a left shift.
if crc_result => $100 ' Check to see if bit 8 is set
crc_result ^= poly ' xor with the polynomial if it is
return crc_result
As for why calculator3 was giving different results than the online calculator, you're entering the hex digits in lower case. Modify the get_nibble method as:
It is, of course, entirely up to you how you want to handle the string formation regarding the padding. For my CANbus objects, I have separate routines for transmitting and receiving.
For transmitting, I have each field of the message stored in its own register. For BEAN, you’ll likely have priority and message length in one byte, message ID, destination ID, and up to 11 data bytes. To transmit that, I’d load one byte at a time, and in the same loop that transmits the bits, append those same bits to the working register (crc_result). After the final data byte is sent, finish up the crc calculation by left shifting / checking / xor’ing eight times, and then the crc field will be ready to transmit.
For receiving, parse every (non-stuffed) bit that comes in and also shift it into a working register. Parse the priority / message length, message ID, destination ID, and use the message length to initialize a loop counter for receiving data bytes. After the final data byte, parse the crc field. After the final bit of the crc field has been received, the working register should be empty – no padding required. $55F = 0, as does $55F00, as does $55F000000000000.
Your routine should work fine for verifying strings, it’s simply creating the crc field where padding is needed.
Ok, that makes sense now that it is case insensitive.
I'm still unsure as to why calculator 1/2 and calculator 3 have different values, I would have expected the end result to still be the same. With the padding and the answers being different, which technique is correct?
With my program, I can append a zero byte ("_00") to the input hex values and get the same answer as CRC Calculator 3.spin. (I know you know this already) I can also add the 8 zeros manually in CRC Calculator 1/2.spin and also get the same value as Crc Calculator 3.spin.
Ok, that makes sense now that it is case insensitive.
I'm still unsure as to why calculator 1/2 and calculator 3 have different values, I would have expected the end result to still be the same. With the padding and the answers being different, which technique is correct?
With my program, I can append a zero byte ("_00") to the input hex values and get the same answer as CRC Calculator 3.spin. (I know you know this already) I can also add the 8 zeros manually in CRC Calculator 1/2.spin and also get the same value as Crc Calculator 3.spin.
How can I know which way is correct?
What you said is precisely why calculator 1/2 and calculator 3 have different values. Calculator 1 & 2 need the padded bits to be explicitly entered into the text string in order for the calculation to work. Calculator 3 automatically pads the text string with the required number of bits. Neither way is correct or incorrect, as long as you know which method you're using. As I mentioned just a couple posts back, for my CANbus transmitter I use a calculator3 type procedure, for the CANbus receiver I use a calculator 1/2 procedure. If the message is received correctly, the crc_result register will be zero after the final bit of the crc field has been parsed. Padding is required for determining what the crc field is when transmitting, padding is not necessary for verifying the received message.
Comments
I have my .net program mostly done, but it is outputting more polys than your code does, so something is wrong with it. In an attempt to debug and correct my program, I chose a random poly for my program (100000100) with the same hex string of 53D2C800E9. My program outputs 0101001111010010110010000000000011101001 (53D2C800E9) with the poly 100000100 equals 000000000. I believe it does this incorrectly, because when I do it by hand I also get 000000000, so it is wrong because of something flawed with the way I'm doing it? I've tried to follow your method and the wiki example and both ways I do not get the correct answer per the online calculator. Then I tried to reread about the CRC method to see if I could figure out on my own what I'm doing wrong, but to no success.
I have tried this at least 12 times today, to make sure I wasn't making the mistake of adding an extra line in again and I'm really not sure what is wrong.
000000000_0101001111010010110010000000000011101001 000000000_101001111010010110010000000000011101001 000000001_01001111010010110010000000000011101001 000000010_1001111010010110010000000000011101001 000000101_001111010010110010000000000011101001 000001010_01111010010110010000000000011101001 000010100_1111010010110010000000000011101001 000101001_111010010110010000000000011101001 001010011_11010010110010000000000011101001 010100111_1010010110010000000000011101001 101001111_010010110010000000000011101001 100000100 001001011_010010110010000000000011101001 100101101_0010110010000000000011101001 100000100 000101001_0010110010000000000011101001 101001001_0110010000000000011101001 100000100 001001101_0110010000000000011101001 100110101_10010000000000011101001 100000100 000110001_10010000000000011101001 110001100_10000000000011101001 100000100 010001000_10000000000011101001 100010001_0000000000011101001 100000100 000010101_0000000000011101001 101010000_000000011101001 100000100 001010100_000000011101001 101010000_0000011101001 100000100 001010100_0000011101001 101010000_00011101001 100000100 001010100_00011101001 101010000_011101001 100000100 001010100_011101001 101010001_1101001 100000100 001010101_1101001 101010111_01001 100000100 001010011_01001 101001101_001 100000100 001001001_001 100100100_1 100000100 000100000_1 100000100 100000100 000000000One of the rules with crc polynomials is that they always begin and end with a set bit, as mentioned in the wikipedia article. The online calculator seems to assume that the lsb is set, as it produces the same result with %100000101 as it does with %100000100.
As for why you were getting 000000000 when doing it by hand, you're shifting too many places - stop after all of the bits have been shifted.
... 001010011_01001 ' 5 bits remain to be shifted 101001101_001 ' 3 100000100 001001001_001 ' 3 100100100_1 ' 1 100000100 000100000_1 ' 1 100000100 ' shifted too far - should've stopped at 001000001 = $41 100000100 000000000A minor modification to my crc calculator routine - which doesn't assume anything about the polynomial - leaves $41 in the crc_result.So the online calculator treats 100000100 as 100000101, as it sets the lsb to 1 in the code?
Seeing that the calculator says that using a poly of 100000100 or 100000101 = 11001100 ($cc), is it wrong?
I modified your code (I think correctly) and using a poly of 100000101, the remainder is 00111100 ($3c). Using a poly of 100000100, the remainder is 001000001 ($41). How did you know to stop at 001000001, because there were only 7 bits left when you do not, after removing the leading zeros?
I will reread the wiki page again to try and make sure I know all of the CRC polynomial rules.
With my object, $53D2C800E9_00 does come out to $CC with the polynomial $105, which is how the online one sees $104.
The reason why both work for verifying $55F = $00 is that a string which is valid after n bits is still going to be valid after n + x clear bits.
$55F000000000000000... also equals 0.
What the online thing is really converting is:
$500 = $5F
$55F00 = $00
I knew to stop because there was only a single bit remaining to be shifted. Stop after all of the bits have been shifted, that's it. If the bits are a,b,c,d, shift them into the working register (crc_result) until d is in the lsb, not until a is in the msb.
000000000_abcd gets shifted to 00000abcd.
If it helps, count the number of bits in the bitstream: $55F has 12 bits.
I'm still a little fuzzy on what the online calc is doing differently. Does the online calculator take hex converted to binary, count the length of the binary digits, divide it by 8 and then determine the number of zeros it needs to pad to the right of the original binary, to have no remainder for that division? I believe this is wrong based on what I have shown below.
So 5 (0101) would be converted to 01010000 by the online program or 01011111?
The good news is that I have the .net program matching outputs from your program in all of my tests ... and a much better understanding of what your code does
I have a decode method working with an indexer as to how frequent a poly comes up within a list of hex phrases, but I have not thoroughly tested it well. Is it correct (as a rule) that a crc8 has to start the polynomial xoring at 100000000 ?
By converted do you mean the result of the computation? The result of $5 with with the polynomial $113 is $5F. Perhaps you mean the value with the padded bits? Since the polynomial is 9 bits, the result will be 8 bits, so the padded value would be $500. Wikipedia also explains that under the computation section. You can also see this on the online calculator, notice how the number of bits in the binary result is one less than the number of bits in the polynomial?
Right, a crc-8 is 9 bits - and only odd, so start from $101 and check every other poly up to $1FF.
Here's a new version of my calculator that behaves more like the online calculator; automatically pads the value depending on the length of the polynomial.
CRC calculator 3.spin
What is the difference between the outputs of your 1st calculator and 3rd?
5 with $113 / 100010011
OnlineCalc = 5f / 01011111
Crc calculator3 = 5f / 001011111
My program = 5 / 101
Cr calculator1 = 5 / 101
000000101 5 100010011 [b] 100010110[/b] 00000010100000000 5 padded 100010011 00101001100 100010011 [b] 001011111[/b]5f with $113 / 100010011
OnlineCalc = 4e / 01001110
Crc calculator3 = 5f / 001011111
My program = 5f / 1011111
Cr calculator1 = 5f / 1011111
001011111 5f 100010011 [b]101001100[/b] 00101111100000000 5f padded 100010011 001101111000000 100010011 0101011110000 100010011 001001101000 100010011 [b] 0001001110[/b]5ff with $113 / 100010011
OnlineCalc = 4d / 01001101
Crc calculator3 = 5f / 001011111
My program = A0 / 10100000
Cr calculator1 = A0 / 010100000
By hand = 10100000
010111111111 5ff 100010011 00110110011 100010011 [b] 010100000[/b] 01011111111100000000 5ff padded 100010011 00110110011 100010011 01010000000000000 100010011 0010100110000000 100010011 00101111100000 100010011 001101111000 100010011 0101011110 100010011 [b] 001001101[/b]5fff with $113 / 100010011
OnlineCalc = 7d / 01111101
Crc calculator3 = 5f / 001011111
My program = B1 / 10110001
Cr calculator1 = B1 / 10110001
By hand = 10110001
0101111111111111 5fff 100010011 001101100111111 100010011 0101000001111 100010011 001010010111 100010011 [b] 0010110001[/b] 010111111111111100000000 5fff padded 100010011 001101100111111 100010011 0101000001111 100010011 001010010111 100010011 001011000100000000 100010011 0011100010000000 100010011 01101011100000 100010011 0101111010000 100010011 001101001000 100010011 0101101110 100010011 [b]001111101[/b]5fff5 with $113 / 100010011
OnlineCalc = f6 / 11110110
Crc calculator3 = F0 / 011110000
My program = B8 / 10111000
Cr calculator1 = B8 / 10111000
By hand = 010111000
01011111111111110101 5fff5 100010011 0011011001111110101 100010011 01010000011110101 100010011 0010100101110101 100010011 00101100010101 100010011 001110001101 100010011 0110101011 100010011 [b] 010111000[/b] 0101111111111111010100000000 5fff5 padded 100010011 0011011001111110101 100010011 01010000011110101 100010011 0010100101110101 100010011 00101100010101 100010011 001110001101 100010011 0110101011 100010011 01011100000000000 100010011 0011000110000000 100010011 01001111100000 100010011 0001011010000 100010011 [b]0011110110[/b]DEADBEEF with $113 / 100010011
OnlineCalc = D1 / 11010001
Crc calculator3 = D1 / 011010001
My program = 1E / 11110
Cr calculator1 = 1E / 11110
53_D2_C8_00_E9_00 with $105 / 100000101
OnlineCalc = F3 / 11110011
Crc calculator3 = F3 / 011110011
My program = CC / 11001100
Cr calculator1 = CC / 11001100
In the get_crc method, after it has looped through all of the bits of all of the nibbles from all of the characters in the string, the program enters a second loop:
repeat >| poly - 1 ' repeat this loop for all bits in the polynomial - 1. For a 9-bit crc (crc-8), this repeats 8 times. Go ahead and replace this with [b]repeat 8[/b] if ya want. crc_result <<= 1 ' The rest of this is just like the code that appends bits from nib, except here all we need to do is pad with 0's, which is what happens during a left shift. if crc_result => $100 ' Check to see if bit 8 is set crc_result ^= poly ' xor with the polynomial if it is return crc_resultAs for why calculator3 was giving different results than the online calculator, you're entering the hex digits in lower case. Modify the get_nibble method as:case [b]byte[/b][ptr] "0".."9" [b]: return byte[/b][ptr] - "0" "A".."F" [b]: return byte[/b][ptr] - "7" "a".."f" [b]: return byte[/b][ptr] - "W" other[b]: return[/b] -1It is, of course, entirely up to you how you want to handle the string formation regarding the padding. For my CANbus objects, I have separate routines for transmitting and receiving.
For transmitting, I have each field of the message stored in its own register. For BEAN, you’ll likely have priority and message length in one byte, message ID, destination ID, and up to 11 data bytes. To transmit that, I’d load one byte at a time, and in the same loop that transmits the bits, append those same bits to the working register (crc_result). After the final data byte is sent, finish up the crc calculation by left shifting / checking / xor’ing eight times, and then the crc field will be ready to transmit.
For receiving, parse every (non-stuffed) bit that comes in and also shift it into a working register. Parse the priority / message length, message ID, destination ID, and use the message length to initialize a loop counter for receiving data bytes. After the final data byte, parse the crc field. After the final bit of the crc field has been received, the working register should be empty – no padding required. $55F = 0, as does $55F00, as does $55F000000000000.
Your routine should work fine for verifying strings, it’s simply creating the crc field where padding is needed.
I'm still unsure as to why calculator 1/2 and calculator 3 have different values, I would have expected the end result to still be the same. With the padding and the answers being different, which technique is correct?
With my program, I can append a zero byte ("_00") to the input hex values and get the same answer as CRC Calculator 3.spin. (I know you know this already) I can also add the 8 zeros manually in CRC Calculator 1/2.spin and also get the same value as Crc Calculator 3.spin.
How can I know which way is correct?
[u]5f[/u] Calculator 1/2/Me = 5f / 1011111 Calculator 3 = 4e / 001001110 001011111 5f 100010011 101001100 00101111100000000 5f padded 100010011 001101111000000 100010011 0101011110000 100010011 001001101000 100010011 0001001110 000000000_00101111100000000 5f shifted left 000000000_0101111100000000 000000000_101111100000000 000000001_01111100000000 000000010_1111100000000 000000101_111100000000 000001011_11100000000 000010111_1100000000 000101111_100000000 001011111_00000000 010111110_0000000 101111100_000000 100010011 001101111_000000 110111100_0000 100010011 010101111_0000 101011110_000 100010011 001001101_000 100110100_0 100010011 000100111_0 [u]5ff[/u] Calculator 1/2/Me = A0 / 010100000 Calculator 3 = 7d / 001001101 010111111111 5ff 100010011 00110110011 100010011 010100000 01011111111100000000 5ff padded 100010011 00110110011 100010011 01010000000000000 100010011 0010100110000000 100010011 00101111100000 100010011 001101111000 100010011 0101011110 100010011 001001101 000000000_010111111111 5ff shifted left (may be wrong) 000000000_10111111111 000000001_0111111111 000000010_111111111 000000101_11111111 000001011_1111111 000010111_111111 000101111_11111 001011111_1111 010111111_111 101111111_11 100010011 001101100_11 110110011 100010011 010100000 [u]5fff[/u] Calculator 1/2/Me = B1 / 10110001 Calculator 3 = 7d / 001111101 0101111111111111 5fff 100010011 001101100111111 100010011 0101000001111 100010011 001010010111 100010011 0010110001 010111111111111100000000 5fff padded 100010011 001101100111111 100010011 0101000001111 100010011 001010010111 100010011 001011000100000000 100010011 0011100010000000 100010011 01101011100000 100010011 0101111010000 100010011 001101001000 100010011 0101101110 100010011 001111101 000000000_0101111111111111 5fff shifted left 000000000_101111111111111 000000001_01111111111111 000000010_1111111111111 000000101_111111111111 000001011_11111111111 000010111_1111111111 000101111_111111111 001011111_11111111 010111111_1111111 101111111_111111 100010011 001101100_111111 110110011_1111 100010011 010100000_1111 101000001_111 100010011 001010010_111 101001011_1 100010011 001011000_1 010110001 [u]5fff5[/u] Calculator 1/2/Me = B8 / 10111000 Calculator 3 = F6 / 011110110 01011111111111110101 5fff5 100010011 0011011001111110101 100010011 01010000011110101 100010011 0010100101110101 100010011 00101100010101 100010011 001110001101 100010011 0110101011 100010011 010111000 0101111111111111010100000000 5fff5 padded 100010011 0011011001111110101 100010011 01010000011110101 100010011 0010100101110101 100010011 00101100010101 100010011 001110001101 100010011 0110101011 100010011 01011100000000000 100010011 0011000110000000 100010011 01001111100000 100010011 0001011010000 100010011 0011110110 000000000_01011111111111110101 5fff5 shifted left 000000000_1011111111111110101 000000001_011111111111110101 000000010_11111111111110101 000000101_1111111111110101 000001011_111111111110101 000010111_11111111110101 000101111_1111111110101 001011111_111111110101 010111111-11111110101 101111111_1111110101 100010011 001101100_1111110101 011011001_111110101 110110011_11110101 100010011 010100000_11110101 101000001_1110101 100010011 001010010_1110101 010100101_110101 101001011_10101 100010011 001011000_10101 010110001_0101 \ 101100010_101 100010011 001110001_101 111000110_1 100010011 011010101_1 110101011 100010011 010111000