On Apr 16, 12:49=A0am, Lasse Langwadt Christensen <llcn...@fonz.dk>
wrote:
[...]
> the pseudo in c would be something like this:
> (untestet, inefficient, written in 30 seconds ...)
>
> unsigned shortCRC(unsigned short input) // input only one bit !!!
> {
> =A0 =A0 =A0 =A0 static unsigned short crc_rg; // shiftregister
>
> =A0 =A0 =A0 =A0 crc_rg =3D crc_rg << 1; =A0 =A0 // leftshift 1 bit
>
> =A0 =A0 =A0 =A0 if((input & 1) ^ ((crc_rg>>14)&1)) =A0 =A0 =A0 =A0
> =A0 =A0 =A0 =A0 {
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 crc_rg =3D crc_rg ^ 0x4599;
> =A0 =A0 =A0 =A0 }
>
> =A0 =A0 =A0 =A0 crc_rg =3D crc_rg & 0x7fff; // only 15 bits
>
> =A0 =A0 =A0 =A0 return crc_rg;
>
> }
>
Hi,
This code is buggy I think. The input message bit should be XORed to
bit 14 of the CRC register *before* it is shifted (so >>14 should be
changed to >>15).
Anyway, here is code that updates the CRC register for a whole input
byte at once:
static inline uint16_t crc_next(uint16_t crc, uint8_t data)
{
uint16_t eor;
unsigned int i =3D 8;
crc ^=3D (uint16_t)data << 7;
do {
/* This might produce branchless code */
eor =3D crc & 0x4000 ? 0x4599 : 0;
crc <<=3D 1;
crc ^=3D eor;
} while (--i);
return crc & 0x7fff;
}
Use it like this:
uint16_t crc_reg =3D 0;
crc_reg =3D crc_next(crc_reg, msg[0]);
crc_reg =3D crc_next(crc_reg, msg[1]);
=2E..
After crc_next has been called for all message bytes crc_reg will
contain the correct CRC value of the message.
Best regards,
Danjel McGougan
Reply by Danjel McGougan●May 2, 20082008-05-02
On Apr 15, 8:08=A0pm, larkmore@aol.com wrote:
> Can anyone out there explain how to calculate the 15 bitCRCfield for
> a Controller Area Network message (specifically the extended frame
> format)? =A0I don't understand the code given in the Bosch specification
> (not even sure which language it's written in) and the only other
> example I found was very obfuscated C code. =A0Any takers?
> -Will
Hi,
You can try my CRC code generator:
http://mcgougan.se/universal_crc
As someone pointed out the polynomial for the CAN CRC is apparently:
x^15 + x^14 + x^10 + x^8 + x^7 + x^4 + x^3 + 1
This polynomial can be represented as 0x4599 (x^0 maps to LSB, x^15 is
implied 1). Knowing this my utility can then be invoked like this:
universal_crc --bits=3D15 --poly=3D0x4599
This will produce ANSI C code for calculating the CRC and print it to
stdout. The utility has various other options that you might need
depending on how the CAN CRC is defined (initial value of the CRC
register, final XOR, reversed mode, etc.). There are also different
CRC algorithms to choose from that have various performance
characteristics.
Let me know if you found this useful!
Best regards,
Danjel McGougan
Reply by ●April 21, 20082008-04-21
/Bump
Anyone know why the example code provided by Lasse does not match the
CRC generated by the hardware I'm using? If it matters (shouldn't)
I'm using an Atmel AT90CAN128 chip. But any CAN controller should
generate the same bit patterns unless I am wildly mistaken, which does
happen sometimes...
-Will
Reply by ●April 17, 20082008-04-17
On Apr 17, 2:47 am, Neil <NeilKu...@worldnet.att.net> wrote:
> The Polynomial must be different
>
> Should it be 0xC599 ?
Well, the number 0x4599 seems to be popping up in a lot of the CAN
examples, and 0xC599 is 16 bits, not 15 so I don't know how that would
change anything since the results are always truncated to 15 bits. :
( Anyone?? Is there a bug in the example code that Lasse provided?
-Will
Reply by Neil●April 17, 20082008-04-17
larkmore@aol.com wrote:
>> the pseudo in c would be something like this:
>> (untestet, inefficient, written in 30 seconds ...)
>>
>> unsigned short CRC(unsigned short input) // input only one bit !!!
>> {
>> static unsigned short crc_rg; // shiftregister
>>
>> crc_rg = crc_rg << 1; // leftshift 1 bit
>>
>> if((input & 1) ^ ((crc_rg>>14)&1))
>> {
>> crc_rg = crc_rg ^ 0x4599;
>> }
>>
>> crc_rg = crc_rg & 0x7fff; // only 15 bits
>>
>> return crc_rg;
>>
>> }
>>
>> -Lasse
>
> Ah!!! This I can understand. Thank you very much. Unfortunately,
> when I run the above code I get a different CRC result than the one
> that shows up on the o-scope from my hardware :( Anyone know what
> I'm doing wrong? For what it's worth I also tried the inversion value
> to 0x4599 of 0x4CD1 as listed on the Wikipedia page for
> Cyclic_redundancy_check and it didn't work either. ???
> -Will
>
> CAN Message as it appears on o-scope:
> 00010000010001100000110000010010000010000011000001001100101010011001101111111
> bit stuffing removed:
> 00010000000011000001000000010000000000100000001100101010011001101111111
> separated into fields:
> SOF IDT[28:18] SRR IDE IDT[17:0] RTR r1 r0 DLC Data(1 byte) CRC
> CRC_del. ACK ACK_del. EOF
> 0 00100000000 1 1 000001000000010000 0 0 0 0001 00000001
> 100101010011001 1 0 1 111111
>
> so the hardware CRC for the above message is 100101010011001 or 19,097
>
> All of my bits on the software (after stuffing) match the o-scope
> picture until the CRC, which does not match
>
> My software crc after each bit passes through:
> 000000000000000 = 0
> 000000000000000 = 0
> 000000000000000 = 0
> 100010110011001 = 17,817
> 001100110100010 = 6,562
> 011001101000100 = 13,124
> 010001100010001 = 8,977
> 001000100101011 = 4,395
> 011000011000110 = 12,486
> 010010000010101 = 9,237
> 001111100100011 = 7,971
> 010110011010110 = 11,478
> 101100110101100 = 22,956
> 111011011000001 = 30,401
> 011101010001011 = 14,987
> 010001000011111 = 8,735
> 001001100110111 = 4,919
> 011010011111110 = 13,566
> 010110001100101 = 11,365
> 100101001011010 = 19,034
> 001010010110100 = 5,300
> 010100101101000 = 10,600
> 001011101001001 = 5,961
> 011110000000010 = 15,362
> 011110110011101 = 15,773
> 010110000110011 = 11,315
> 000111101101111 = 3,951
> 100100111010111 = 18,903
> 000000100111110 = 318
> 000001001111100 = 636
> 000010011111000 = 1,272
> 000100111110000 = 2,544
> 001001111100000 = 5,088
> 010011111000000 = 10,176
> 000101000011001 = 2,585
> 000011010100010 = 1,698
> 000110101000100 = 3,396
> 001101010001000 = 6,792
> 111000010001001 = 28,809
> 011011000011011 = 13,851
> 011101100111111 = 15,167
> 010000101110111 = 8,567
> 001010111100111 = 5,607
> 011100101011110 = 14,686
> 011011100100101 = 14,117
> 011100101000011 = 14,659
> 110000000010110 = 24,598
The Polynomial must be different
Should it be 0xC599 ?
Reply by ●April 16, 20082008-04-16
> the pseudo in c would be something like this:
> (untestet, inefficient, written in 30 seconds ...)
>
> unsigned short CRC(unsigned short input) // input only one bit !!!
> {
> static unsigned short crc_rg; // shiftregister
>
> crc_rg = crc_rg << 1; // leftshift 1 bit
>
> if((input & 1) ^ ((crc_rg>>14)&1))
> {
> crc_rg = crc_rg ^ 0x4599;
> }
>
> crc_rg = crc_rg & 0x7fff; // only 15 bits
>
> return crc_rg;
>
> }
>
> -Lasse
Ah!!! This I can understand. Thank you very much. Unfortunately,
when I run the above code I get a different CRC result than the one
that shows up on the o-scope from my hardware :( Anyone know what
I'm doing wrong? For what it's worth I also tried the inversion value
to 0x4599 of 0x4CD1 as listed on the Wikipedia page for
Cyclic_redundancy_check and it didn't work either. ???
-Will
CAN Message as it appears on o-scope:
00010000010001100000110000010010000010000011000001001100101010011001101111111
bit stuffing removed:
00010000000011000001000000010000000000100000001100101010011001101111111
separated into fields:
SOF IDT[28:18] SRR IDE IDT[17:0] RTR r1 r0 DLC Data(1 byte) CRC
CRC_del. ACK ACK_del. EOF
0 00100000000 1 1 000001000000010000 0 0 0 0001 00000001
100101010011001 1 0 1 111111
so the hardware CRC for the above message is 100101010011001 or 19,097
All of my bits on the software (after stuffing) match the o-scope
picture until the CRC, which does not match
My software crc after each bit passes through:
000000000000000 = 0
000000000000000 = 0
000000000000000 = 0
100010110011001 = 17,817
001100110100010 = 6,562
011001101000100 = 13,124
010001100010001 = 8,977
001000100101011 = 4,395
011000011000110 = 12,486
010010000010101 = 9,237
001111100100011 = 7,971
010110011010110 = 11,478
101100110101100 = 22,956
111011011000001 = 30,401
011101010001011 = 14,987
010001000011111 = 8,735
001001100110111 = 4,919
011010011111110 = 13,566
010110001100101 = 11,365
100101001011010 = 19,034
001010010110100 = 5,300
010100101101000 = 10,600
001011101001001 = 5,961
011110000000010 = 15,362
011110110011101 = 15,773
010110000110011 = 11,315
000111101101111 = 3,951
100100111010111 = 18,903
000000100111110 = 318
000001001111100 = 636
000010011111000 = 1,272
000100111110000 = 2,544
001001111100000 = 5,088
010011111000000 = 10,176
000101000011001 = 2,585
000011010100010 = 1,698
000110101000100 = 3,396
001101010001000 = 6,792
111000010001001 = 28,809
011011000011011 = 13,851
011101100111111 = 15,167
010000101110111 = 8,567
001010111100111 = 5,607
011100101011110 = 14,686
011011100100101 = 14,117
011100101000011 = 14,659
110000000010110 = 24,598
Reply by Lasse Langwadt Christensen●April 15, 20082008-04-15
>Lasse Langwadt Christensen wrote:
>
>>> Heinz-J�rgen Oertel wrote:
>
>>>> X15 + X14 + X10 + X8 + X7 + X4 + X3 + 1.
>
>> though I can't really get the numbers and the 0x4599 in the code to match up
>
>Why not? 0x4599 has bits number 0, 3, 4, 7, 8, 10 and 14 set. Ring a
>bell now?
yes, kept seeing 1 as bit 1, it is ofcourse bit 0
-Lasse
Reply by ●April 15, 20082008-04-15
Lasse Langwadt Christensen wrote:
>> Heinz-J�rgen Oertel wrote:
>>> X15 + X14 + X10 + X8 + X7 + X4 + X3 + 1.
> though I can't really get the numbers and the 0x4599 in the code to match up
Why not? 0x4599 has bits number 0, 3, 4, 7, 8, 10 and 14 set. Ring a
bell now?
Reply by Lasse Langwadt Christensen●April 15, 20082008-04-15
larkmore@aol.com wrote:
>Heinz-J�rgen Oertel wrote:
>> What is your problem with the formula given there for the coefficients of
>> the generator-polynomial?
>>
>> X15 + X14 + X10 + X8 + X7 + X4 + X3 + 1.
>>
>> that is what I would call a mathematical description. The other code given
>> there I know under the name of pseudo code.
>> If that is something like the names of Bohemian villages for you, please
>> search for "CRC calculation". Most literature you will find can explain it
>> better than I can.
>
>I do not understand what "X" is in this case. Is it just a
>concatenation of all the bits in the SOF, Arbitration, Control and
>Data fields? If yes, then the resulting number would be much larger
>than 15 bits. Hence my confusion. The term "generator-polynomial" is
>also unfamiliar to me. I have searched extensively for CRC
>calculation and all the articles I have found to date say it is really
>nice thing to have, talk about the format in very vague and hand wavy
>terms that I guess they assume everyone already knows (like "generator-
>polynomial"!!!) and usually wind up saying that there are many
>different ways to derive one. Great. _WHICH_ method is the one used
>for CAN messages specifically?? As mentioned, only the Bosch
>specification and a really incomprehensible C code actually refer to
>CAN by name.
>
its a mathematical way of describing something that boils down to
shiftregisters and xor gates
in short X is the shift register, the numbers are bit positions.
though I can't really get the numbers and the 0x4599 in the code to match up
>I am very familiar with pseudo code in general but the specific flavor
>used in the Bosch document makes no sense to me.
looks a bit weird, helps if you know verilog or vhdl I guess.
the pseudo in c would be something like this:
(untestet, inefficient, written in 30 seconds ...)
unsigned short CRC(unsigned short input) // input only one bit !!!
{
static unsigned short crc_rg; // shiftregister
crc_rg = crc_rg << 1; // leftshift 1 bit
if((input & 1) ^ ((crc_rg>>14)&1))
{
crc_rg = crc_rg ^ 0x4599;
}
crc_rg = crc_rg & 0x7fff; // only 15 bits
return crc_rg;
}
-Lasse
Reply by msg●April 15, 20082008-04-15
larkmore@aol.com wrote:
> Heinz-J�rgen Oertel wrote:
>
>>What is your problem with the formula given there for the coefficients of
>>the generator-polynomial?
>>
>> X15 + X14 + X10 + X8 + X7 + X4 + X3 + 1.
>>
>>that is what I would call a mathematical description. The other code given
>>there I know under the name of pseudo code.
>>If that is something like the names of Bohemian villages for you, please
>>search for "CRC calculation". Most literature you will find can explain it
>>better than I can.
>
>
> I do not understand what "X" is in this case. Is it just a
> concatenation of all the bits in the SOF, Arbitration, Control and
> Data fields? If yes, then the resulting number would be much larger
> than 15 bits. Hence my confusion. The term "generator-polynomial" is
> also unfamiliar to me.
A concise but readable description of the mathematics of CRC is in
this article:
http://en.wikipedia.org/wiki/Mathematics_of_CRC
An implementation of CRC-CCITT calculation using shift registers and
XOR gates (mistakenly labeled as CRC-16) is here:
http://www.erg.abdn.ac.uk/users/gorry/course/dl-pages/crc.html
These sites were just the top hits in a quick net search...
You should be able to see how to implement the polynomial you cited
in your original post from this information.
Michael