Searching \ for '[PIC] CRC algorithm for VPW ECU i/f'ing' in subject line. ()
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.
'[PIC] CRC algorithm for VPW ECU i/f'ing'
2006\04\29@165720 by

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

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

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

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 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
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 <piclistmit.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 - fastfwdix.netcom.com

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}
Thanks to everyone (Mauricio, Bob A, Gerhard, Scott, Bob B, Andrew, Jay) for
their responses.

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

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

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
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}
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
HShankoOregonsBest.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...