Searching \ for '[PIC] CRC algorithm for VPW ECU i/f'ing' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.sxlist.com/techref/method/errors.htm?key=crc
Search entire site for: 'CRC algorithm for VPW ECU i/f'ing'.

Exact match. Not showing close matches.
PICList Thread
'[PIC] CRC algorithm for VPW ECU i/f'ing'
2006\04\29@165720 by Harley Shanko

flavicon
face
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

2006\04\29@174337 by Mauricio Giovagnini

flavicon
face
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}

__________________________________________________
Correo Yahoo!
Espacio para todos tus mensajes, antivirus y antispam ¡gratis!
¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar

2006\04\29@180120 by Bob Axtell

face picon face
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

2006\04\29@214405 by Scott Dattalo

face
flavicon
face
On Sat, 2006-04-29 at 15:01 -0700, Bob Axtell wrote:

> Its in the PICLIST archive. You want CRC-16. I believe Scott Dattalo has
> a nice clean routine.

I have a few optimized CRC routines:

http://www.dattalo.com/technical/software/pic/crc.php

Scott

2006\04\30@004722 by Bob Blick
face picon face
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

2006\04\30@010931 by Scott Dattalo

face
flavicon
face
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

2006\04\30@025131 by Andrew Warren

face
flavicon
face
Scott Dattalo <spam_OUTpiclistTakeThisOuTspammit.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 - .....fastfwdKILLspamspam@spam@ix.netcom.com

2006\04\30@065659 by Jay Shroff

picon face


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


{Original Message removed}

2006\04\30@181128 by Harley Shanko

flavicon
face
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

2006\04\30@183450 by Scott Dattalo

face
flavicon
face
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


'[PIC] CRC algorithm for VPW ECU i/f'ing'
2006\05\01@121632 by Mark Samuels
picon face
part 1 1188 bytes content-type:text/plain; format=flowed; charset="iso-8859-1"; (decoded 7bit)

Here's a quick CRC routine in 18F assembly that I did for J1850 interfaces
(same for VPW and PWM)

-Mark

{Original Message removed}

2006\05\01@131227 by Jay Shroff

picon face
I have'nt had a chance to study scott's brilliant CRC code, but looks really impressive at 20 bytes or so... Hopefully will get to it today.

Scott I don't know how you do it :-)

Jay

{Original Message removed}

2006\05\01@132117 by Scott Dattalo

face
flavicon
face
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

2006\05\01@141158 by Bob Axtell

face picon face
Jay Shroff wrote:
> I have'nt had a chance to study scott's brilliant CRC code, but looks really impressive at 20 bytes or so... Hopefully will get to it today.
>
> Scott I don't know how you do it :-)
>
>  
I am also amazed. I've been studying Scott's math wizardry for a coupla
years now, but (as mentioned before)
Scott's CRC routines are even MORE wonderful.

Attaboy, Scott.

--Bob






> Jay
>
> {Original Message removed}

2006\05\02@130745 by Harley Shanko

flavicon
face
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
HShankospamKILLspamOregonsBest.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

More... (looser matching)
- Last day of these posts
- In 2006 , 2007 only
- Today
- New search...