Post by thread:[PIC] CRC algorithm for VPW ECU i/f'ing

I can't help you with the precise algorithm cars use but I can help you with CRC. The CRC is an unique alghorithm but can vary some aspects on the implementation. * Width = 16 bits * The generator polynom * The Initial value * If input data is reflected or not * If output data is reflected or not * XOR value on output * Augmented or not augmented version I can give you this links to start with A "must" read http://www.ross.net/crc/crcpaper.html http://www.joegeluso.com/software/articles/ccitt.htm One of my favourites simple implementations http://www.digitalnemesis.com/info/codesamples/embeddedcrc16/ Simple code http://www.riccibitti.com/crc_c.htm A little more deep explanation http://www.ciphersbyritter.com/ARTS/CRCMYST.HTM The problem is that some do an augmented implementation and some don't. On the other hand, the CRC alghorithm is non intuitive, you should know how its implemented on the device or at least have a list of values with its corresoponding CRC in order to 'guess' which CRC alghorithm parameters they are using. By 'non intuitive' I mean that a single change on any of the parameters i mentioned above of this mail can give you results that are not even similar. For example a simple checksum if you change increment one byte of the list of values you have, ,the checksum will change its value in 1. The CRC you can change a value of one byte and the result can vary a lot!. I hope this helps. Harley Shanko wrote: {Quote hidden}> Being new to working with CRCs, I Googled for information on the subject, > especially looking for what's needed for 'car computer reader' design. > Found nothing specific. > > Seems to be a dozen or more types of CRC. Confusing. And they talk of > dividing. HELP! My design is using a PIC12F629/675 (because it was > in-hand) and there is no divide instruction. > > Does anyone happen to know what the CRC algorithm is used with ECUs with VPW > protocol? > > Harley Shanko > __________________________________________________ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar

Harley Shanko wrote: > Being new to working with CRCs, I Googled for information on the subject, > especially looking for what's needed for 'car computer reader' design. > Found nothing specific. > > Seems to be a dozen or more types of CRC. Confusing. And they talk of > dividing. HELP! My design is using a PIC12F629/675 (because it was > in-hand) and there is no divide instruction. > > Does anyone happen to know what the CRC algorithm is used with ECUs with VPW > protocol? > > Harley Shanko > Its in the PICLIST archive. You want CRC-16. I believe Scott Dattalo has a nice clean routine. --Bob

On 29 Apr 2006 at 14:00, Harley Shanko wrote: > Seems to be a dozen or more types of CRC. Confusing. And they talk of > dividing. HELP! My design is using a PIC12F629/675 (because it was > in-hand) and there is no divide instruction. You don't need a divide. > Does anyone happen to know what the CRC algorithm is used with ECUs with VPW > protocol? I made an interface about 5 or 6 years ago. It's an 8-bit CRC. I forget the polynomial but I can probably put my hand on it in the next few days. You'll need to be pretty tricky to do the CRC in realtime along with banging the bus at 4 (or 8) MHz. Cheers, Bob

On Sat, 2006-04-29 at 21:45 -0700, Bob Blick wrote: > I made an interface about 5 or 6 years ago. It's an 8-bit CRC. I > forget the polynomial but I can probably put my hand on it in the next > few days. > > You'll need to be pretty tricky to do the CRC in realtime along with > banging the bus at 4 (or 8) MHz. Hi Bob, If you tell me the polynomial and provide a few examples of CRC'd data, then I'll take a whack at an efficient implementation. An 8-bit polynomial should take no more than about 20 instruction cycles. If there's symmetry that can be exploited, then it may take fewer. Scott

Scott Dattalo <spam_OUTpiclistTakeThisOuTmit.edu> wrote: > > You'll need to be pretty tricky to do the CRC in realtime along > > with banging the bus at 4 (or 8) MHz. > > If you tell me the polynomial and provide a few examples of CRC'd > data, then I'll take a whack at an efficient implementation. An > 8-bit polynomial should take no more than about 20 instruction > cycles. If there's symmetry that can be exploited, then it may take > fewer. ... And if you're bit-banging a serial interface so you already have access to your data one bit at a time, you can do it in 4 cycles per bit (RLF CRC / MOVLW poly / SKPNC / XORWF CRC) -- or maybe 3 cycles per bit if you can avoid having to reload W for every bit. It's slower than doing it a whole byte at a time, but it takes less code space and might make the timing a lot easier. -Andrew === Andrew Warren - .....fastfwdKILLspam@spam@ix.netcom.com

Thanks to everyone (Mauricio, Bob A, Gerhard, Scott, Bob B, Andrew, Jay) for their responses. Looks like I have a larger task ahead than expected; that of reading all the supplied info and figuring out just what I really need to implement. In assembly, not C. I don't really need to do CRC on the fly/realtime. Planned is to do it prior to sending; have the time then. Have been reading the Piclist for months. Sometime OT subjects are of interest; sometimes way out matters. Thanks for the interesting reading. Have also been reading 8052.com forum, but some of them sure do lots of flaming (if that is the proper word). Had an interest in the -52 for a while. Will stick with the PIC and MPLAB/ICD2 for my 'fun'. Harley

On Sun, 2006-04-30 at 06:56 -0400, Jay Shroff wrote: > The CRC division polynomial for VPW is X8 + X4 + X3 + X2 + 1. > > Some examples from the SAE doc... (Last byte is the CRC) > 00 00 00 00 59 > F2 01 83 37 > 0F AA 00 55 79 > 00 FF 55 11 B8 > 33 22 55 AA BB CC DD EE FF CB > 92 6B 55 8C > FF FF FF FF 74 Jay, I didn't get a chance to work on this too much so I don't have time to explain how it works. But, here is a 20 instruction or so version: http://www.dattalo.com/technical/software/pic/crc-sae.asm I'll probably add a few comments and place a link here http://www.dattalo.com/technical/software/pic/crc.php The all 0's and all ff's messages are illustrated in the code. Scott

Mark Samuels wrote: > Here's a quick CRC routine in 18F assembly that I did for J1850 > interfaces (same for VPW and PWM) Hi Mark, I took a look at your code and it looks as though if you and the author of http://obddiagnostics.com/obdinfo/CRC.txt are working from similar sources. I used this C-implementation to verify that it can successfully CRC the CRC'd test messages Jay posted (and the answer is it does). Rather than converting this algorithm directly into assembly, I decided instead to see if it can be optimized. The answer is it can: http://www.dattalo.com/technical/software/pic/crc-sae.asm The way I approached this problem was to create a 256 element CRC table i = 0..255 crcTable[i] = crc_one_byte_of_message(i); Once you have this table, then you can compute the crc of a message by: crc = crcTable[ *message++ ^ crc ] In other words, starting with your current crc byte, exclusive or this with the next message byte. This produces an index into the crcTable where the new crc can be found. This algorithm is very efficient (time wise). However, for only a very slight increase in execution time it's possible to dynamically compute the table's contents. CRC tables generated in the way I describe have the property that single bit indices changes are all related by: crcTable[i ^ (1<<n)] = crcTable[i] ^ K_n for n<8 In other words, if you change just one bit in the index then it's related to another table entry by XORing with a constant. For example, crcTable[1] = crcTable[0] ^ 0x1d and similarly crcTable[9] = crcTable[8] ^ 0x1d. The similarity in these is that only the least significant bit of the index is changed in both cases. For this particular polynomial, I found: crcTable[0] = 0x3b crcTable[0]^crcTable[1] = 0x1d crcTable[0]^crcTable[2] = 0x3a crcTable[0]^crcTable[4] = 0x74 crcTable[0]^crcTable[8] = 0xe8 crcTable[0]^crcTable[16] = 0xcd crcTable[0]^crcTable[32] = 0x87 crcTable[0]^crcTable[64] = 0x13 crcTable[0]^crcTable[128] = 0x26 This explains the constants in my assembly routine. The next optimization would be to find relationships in these constants that allow them to be easily computed (based on the effective index). While I can see several patterns, none of them are easily exploited. BTW, the rest of the OBD page is: http://obddiagnostics.com/obdinfo/info.html Scott

Mark Samuels, For some reason your file did NOT show up, but there was a note that it was 'not available'; see below the 'next part' note. Was it meant to be provided? Would appreciate it if it can be supplied. If desire, email at HShankoKILLspamOregonsBest.com Harley -------------- next part -------------- A non-text attachment was scrubbed... Name: crc_routine.asm Type: application/octet-stream Size: 1115 bytes Desc: not available Url : mailman.mit.edu/mailman/private/piclist/attachments/20060501/9bf2a7bc /crc_routine.obj