Computer Interfacing
Discussions about interfacing and electronics
 

Someone who can encode this one??

need help with crc


 

       Computer Interfacing Forum Index -> Error detection and correction
Author Message
Ranko
Guest







Oct 26, 2009 8:52 pm

Hi guys,

I'm working in a windpark and have to find out this Crc or Bcc (it's from an old windmill control system)

examples of the messages:

[SOH]3[GS]003[GS]0[ETX]53716[EOT]

[SOH]4[GS]003[GS]0[ETX]61897[EOT]

[SOH]5[GS]003[GS]0[ETX]04559[EOT]

[SOH]6[GS]003[GS]0[ETX]45504[EOT]

[SOH]3[GS]400[GS]0[ETX]20934[EOT]

[SOH]3[GS]009[GS]0[ETX]53750[EOT]

[SOH]1[GS]010[GS]0[ETX]04945[EOT]

Things I know so far:

- all char's are ASCII character (of course wirhout [SOH], [GS], [ETX], [EOT])

which means that e.g.
[SOH]1[GS]010[GS]0[ETX]04945[EOT]
means
01 31 1D 30 31 30 1d 30 03 30 34 39 34 35 04
in hex

- [SOH] Windmill-adress [GS] command [GS] subcommand[ETX]checksum[EOT] is the format

- Checksum must be a kind of crc 16, because value of checksum is NEVER higher or equal than 65535 (0xFFFF)

- Checksum is shown in dezimal Form and in clear text (Ascii), no crc value above 65535, no A,B,C,D,E in CRC/BCC

I would be grateful for EVERY kind of help; i try to figure it out since last month^^ but without any success.

Thank you in advance.
Ranko
regregex
Preferred Member



Joined: 30 Oct 2007
Posts: 184
Location: London, UK

Oct 30, 2009 5:50 pm

Hello Ranko, and thank you for your post.

Whichever way these lines are represented internally, if you XOR lines 1, 3 and 4 together you get a first parameter of 0. The resulting CRC (when treated as a 16 bit value, as you suggest) works out at 53716 ^ 04559 ^ 45504 = 29147 = 0x71DB.

If we Xor this residue with each CRC then we get
[SOH]3[GS]003[GS]0[ETX]53716[EOT] => 0xD1D4 ^ 0x71DB = 0xA00F
[SOH]4[GS]003[GS]0[ETX]61897[EOT] => 0xF1C9 ^ 0x71DB = 0x8012
[SOH]5[GS]003[GS]0[ETX]04559[EOT] => 0x11CF ^ 0x71DB = 0x6014
[SOH]6[GS]003[GS]0[ETX]45504[EOT] => 0xB1C0 ^ 0x71DB = 0xC01B
[SOH]3[GS]400[GS]0[ETX]20934[EOT] => 0x51C6 ^ 0x71DB = 0x201D
[SOH]3[GS]009[GS]0[ETX]53750[EOT] => 0xD1F6 ^ 0x71DB = 0xA02D
[SOH]1[GS]010[GS]0[ETX]04945[EOT] => 0x1351 ^ 0x71DB = 0x628A

As the first parameter increases, the CRC changes fairly simply. Combining lines 2 and 3, then 2 and 4 we can expect to see:

[SOH]1[GS]003[GS]0[ETX]37341[EOT] => 0x91DD ^ 0x71DB = 0xE006
[SOH]2[GS]003[GS]0[ETX]12754[EOT] => 0x31D2 ^ 0x71DB = 0x4009

Note that 0x4009 == (0xE006 << 1) ^ 0x18005, and 0x8012 == 0x4009 << 1. So this is definitely a CRC, with the common polynomial 0x8005 (MODBUS, ARC, IBM etc.) though I haven't worked out the internal representation and actual algorithm yet.

HTH

--Greg
regregex
Preferred Member



Joined: 30 Oct 2007
Posts: 184
Location: London, UK

Oct 30, 2009 11:56 pm

I'm now wondering if it's that b*stard CRC by Sick GmbH. To confirm this however I'd need to know the internal bitstream in advance.

--Greg
Ranko
Guest







Nov 02, 2009 7:04 am

Thanks you very much regregex,

your calculation of the CRC for [SOH]1.... and [SOH]2... is correct. This is really the crc for this commands.
Meanwhile i figured out that xor'ing gives me a key to calculate the Crc from changing the first option and also if second option changed. e.g.:

[SOH]1[GS]003[GS]0[ETX]37341[EOT]

[SOH]3[GS]003[GS]0[ETX]53716[EOT]

0x91DD (37231) xor 0xD1D4 (53716)=
0xBFF6 (Key from Option 1 -> 3)

[SOH]3[GS]003[GS]0[ETX]53716[EOT]

[SOH]3[GS]009[GS]0[ETX]53750[EOT]

0xD1D4 (53716) xor 0xD1F6 (53750) =
0xFFDD (key from option 003 -> 009)

With this i can calculate the expected checksum for
[SOH]1[GS]009[GS]0[ETX]xxxxx[EOT]

xxxxx = 0xD1D4 XOR 0xBFF6 Xor 0xFFDD = 0x91FF (37375) =>

[SOH]1[GS]009[GS]0[ETX]37375[EOT]

This works for all windmills.
But i still need the algorithm because i have to check if the answer is correct :-(

The shortest message calculated with this checksumalgo i have found is:

?01 [ETX] 53413 [EOT]

Maybe that helps.
Thanks 4 your great work regregex!!!
Ranko
Guest







Nov 02, 2009 7:29 am

As far as the internal bitstream is concerned, i think all chars are ASCII Coded, so that e.g.:

?01[ETX] is equal to

0x3f 0x30 0x30 [0x03]

Ranko
Ranko
Guest







Nov 02, 2009 7:30 am

^^Damn mistyped...
?01[ETX] =

0x3f 0x30 0x31 [0x03]
regregex
Preferred Member



Joined: 30 Oct 2007
Posts: 184
Location: London, UK

Nov 02, 2009 10:37 pm

Found it. It's the Buypass or Verifone algorithm... on 7 bit ASCII characters. This was throwing me and so I suspected it was converting to binary but you're right, it does check the characters. The receiver discards the [SOH], then checks each character including digits and [GS], but discards the [ETX]. It then checks the result against the next 5 digits. This works on all the examples I've tried (except ?01, but if you replace it with [NUL]01, you get the CRC 53413 Wink )

If you have an 8-bit Buypass calculator, the string of bytes d4 eb 06 0c ce b0 is equivalent to the 5,003,0 message.
Code:
  "5"    [GS]     "0"     "0"     "3"    [GS]     "0"
 0x35    0x1d    0x30    0x30    0x33    0x1d    0x30
0110101 0011101 0110000 0110000 0110011 0011101 0110000
 \       |\       |\       |\       |\       |\       |
  11010100 11101011 00000110 00001100 11001110 10110000
    0xd4     0xeb     0x06     0x0c     0xce     0xb0
If you have an 8-bit ARC calculator, the bytewise reversed string 2b d7 60 30 73 0d produces the result 0xf388, which is 0x11cf (4559) in reverse... I can do a long division to demonstrate if needed.

In the Rocksoft model, the Buypass algorithm is (width=16, poly=8005, init=0000, refin=false, refout=false, xorout=0000, check=fee8).

Anything to keep green power working.

-- Greg

---
<for information only -- feel free to skip>

FWIW here are the notes I made while working this out, it was a shame to throw them out. First I was going to ask you for another message+CRC that would give me Init+XorOut, the text would need to be a combination of an even number of your earlier examples.
Code:
[greg@pavo greg]$ perl -e '@a=qw(3003 4003 5003 6003 3400 3009 1010);for$a
(2..126){unless(($a&1)+($a>>1&1)+($a>>2&1)+($a>>3&1)+($a>>4&1)+($a>>5&1)+
($a>>6&1)&1){$c=0;for$b(0..6){if($a&1<<$b){$c^=hex($a[$b]);}}$a{sprintf(
"%04x",$c)}.=sprintf("%02x ",$a);}}for$a(sort keys%a){printf("%s %s",$a,
$a{$a});}print"\n";'
000a 21 0013 4b 0019 6a 0403 11 0409 30 0410 5a 041a 7b 1000 06 100a 27 1013 4d
1019 6c 1403 17 1409 36 1410 5c 141a 7d 2000 0a 200a 2b 2013 41 2019 60 2403 1b
2409 3a 2410 50 241a 71 3000 0c 300a 2d 3013 47 3019 66 3403 1d 3409 3c 3410 56
341a 77 4000 0f 400a 2e 4013 44 4019 65 4403 1e 4409 3f 4410 55 441a 74 5000 09
500a 28 5013 42 5019 63 5403 18 5409 39 5410 53 541a 72 6000 05 600a 24 6013 4e
6019 6f 6403 14 6409 35 6410 5f 641a 7e 7000 03 700a 22 7013 48 7019 69 7403 12
7409 33 7410 59 741a 78
Then I realised this wouldn't tell me much right now, and the other ASCII bits would interfere anyway. Then it came to me that for very sparse messages, the actual input pattern could be recovered from the CRC itself. This would tell us how message characters mapped to the CRC input string. I spot 000a in the list and try that:
Code:
[greg@pavo greg]$ perl -e '$a=5;$b=0;while(!grep {$_==$a} (0x0022,0xffdd,
0x4400,0xbbff,0x2200,0xddff,0x0044,0xffbb)){++$b;$a<<=1;if($a&0x10000){$a^=
0x18005;}}printf"%04x %d\n",$a,$b;'
\\seeking a or 5, first occurrence only
0022 31
To do this seriously, first job was to reproduce the list of messages with their corresponding CRCs. The number of contributors must again be even, so that constant elements would cancel out:
Code:
[greg@pavo greg]$ perl -e '@a=qw(3003d1d4 4003f1c9 500311cf 6003b1c0 340051c6
3009d1f6 10101351);for$a(2..126){unless(($a&1)+($a>>1&1)+($a>>2&1)+($a>>3&1)+
($a>>4&1)+($a>>5&1)+($a>>6&1)&1){$c=0;for$b(0..6){if($a&1<<$b){$c^=hex($a[$b])
;}}$a{sprintf("%08x",$c)}.=sprintf("%02x ",$a);}}for$a(sort keys%a){printf(
"%s %s    ",$a,$a{$a});}print"\n";'
000a 0022 21    0013 828c 4b    0019 82ae 6a    0403 8012 11    0409 8030 30
0410 029e 5a    041a 02bc 7b    1000 e006 06    100a e024 27    1013 628a 4d
1019 62a8 6c    1403 6014 17    1409 6036 36    1410 e298 5c    141a e2ba 7d
2000 4009 0a    200a 402b 2b    2013 c285 41    2019 c2a7 60    2403 c01b 1b
2409 c039 3a    2410 4297 50    241a 42b5 71    3000 a00f 0c    300a a02d 2d
3013 2283 47    3019 22a1 66    3403 201d 1d    3409 203f 3c    3410 a291 56
341a a2b3 77    4000 8012 0f    400a 8030 2e    4013 029e 44    4019 02bc 65
4403 0000 1e    4409 0022 3f    4410 828c 55    441a 82ae 74    5000 6014 09
500a 6036 28    5013 e298 42    5019 e2ba 63    5403 e006 18    5409 e024 39
5410 628a 53    541a 62a8 72    6000 c01b 05    600a c039 24    6013 4297 4e
6019 42b5 6f    6403 4009 14    6409 402b 35    6410 c285 5f    641a c2a7 7e
7000 201d 03    700a 203f 22    7013 a291 48    7019 a2b3 69    7403 a00f 12
7409 a02d 33    7410 2283 59    741a 22a1 78
(For completeness, here are all combinations of odd numbers of messages:)
Code:
[greg@pavo greg]$ perl -e '@a=qw(3003d1d4 4003f1c9 500311cf 6003b1c0 340051c6
3009d1f6 10101351);for$a(1..127){if(($a&1)+($a>>1&1)+($a>>2&1)+($a>>3&1)+
($a>>4&1)+($a>>5&1)+($a>>6&1)&1){$c=0;for$b(0..6){if($a&1<<$b){$c^=hex($a[$b])
;}}$a{sprintf("%08x",$c)}.=sprintf("%02x ",$a);}}for$a(sort keys%a){printf(
"%s %s    ",$a,$a{$a});}print"\n";'
0003 71db 0d    0009 71f9 2c    0010 f357 46    001a f375 67    0400 f1c9 1c
040a f1eb 3d    0413 7345 57    0419 7367 76    1003 91dd 0b    1009 91ff 2a
1010 1351 40    101a 1373 61    1400 11cf 1a    140a 11ed 3b    1413 9343 51
1419 9361 70    2003 31d2 07    2009 31f0 26    2010 b35e 4c    201a b37c 6d
2400 b1c0 16    240a b1e2 37    2413 334c 5d    2419 336e 7c    3003 d1d4 01
3009 d1f6 20    3010 5358 4a    301a 537a 6b    3400 51c6 10    340a 51e4 31
3413 d34a 5b    3419 d368 7a    4003 f1c9 02    4009 f1eb 23    4010 7345 49
401a 7367 68    4400 71db 13    440a 71f9 32    4413 f357 58    4419 f375 79
5003 11cf 04    5009 11ed 25    5010 9343 4f    501a 9361 6e    5400 91dd 15
540a 91ff 34    5413 1351 5e    5419 1373 7f    6003 b1c0 08    6009 b1e2 29
6010 334c 43    601a 336e 62    6400 31d2 19    640a 31f0 38    6413 b35e 52
6419 b37c 73    7003 51c6 0e    7009 51e4 2f    7010 d34a 45    701a d368 64
7400 d1d4 1f    740a d1f6 3e    7413 5358 54    7419 537a 75
Then pick sparse examples from the first list to reverse engineer. The later code prints solutions with fewer than 3 bits, all less than 96 bits from the end of the CRC:
Code:
[greg@pavo greg]$ perl -e '$a=1;$b=0;while(!grep {$_==$a} (0xe006)){++$b;
$a<<=1;if($a&0x10000){$a^=0x18005;}}printf"%04x %d\n",$a,$b;'
e006 58 <<
[greg@pavo greg]$ perl -e '$a=1;$b=0;while(!grep {$_==$a} (0x4009)){++$b;
$a<<=1;if($a&0x10000){$a^=0x18005;}}printf"%04x %d\n",$a,$b;'
4009 59
[greg@pavo greg]$ perl -e '$a=5;$b=0;while(!grep {$_==$a} (0x6014)){++$b;
$a<<=1;if($a&0x10000){$a^=0x18005;}}printf"%04x %d\n",$a,$b;'
6014 58 <<
[greg@pavo greg]$ perl -e '$a=1;$b=0;while(!grep {$_==$a} (0x8012)){++$b;
$a<<=1;if($a&0x10000){$a^=0x18005;}}printf"%04x %d\n",$a,$b;'
8012 60
[greg@pavo greg]$ perl -e 'for$a0(0..65535){if(($_=unpack("B*",pack("N",$a0)))
=~y/1//>3){next;}$a=$a0;$b=0;while($b<96&&!grep {$_==$a} (0x828c,0x7d73,
0x3141,0xcebe,0x8c82,0x737d,0x4131,0xbece)){++$b;$a<<=1;if($a&0x10000){$a^=
0x18005;}}printf"%04x %04x %d\n",$a0,$a,$b if$b<96;}'
\\seeking 13 or c8
0083 828c 30 <<
0106 828c 29
020c 828c 28
0418 828c 27
0803 828c 86
0830 828c 26
1006 828c 85
1060 828c 25
200c 828c 84
20c0 828c 24
4018 828c 83
4081 828c 38
4180 828c 23
8030 828c 82
8102 828c 37
8201 828c 36
8300 828c 22
[greg@pavo greg]$ perl -e 'for$a0(0..65535){if(($_=unpack("B*",pack("N",$a0)))
=~y/1//>3){next;}$a=$a0;$b=0;while($b<96&&!grep {$_==$a} (0x029e,0x7940,
0xfd61,0x86bf,0x9e02,0x4079,0x61fd,0xbf86)){++$b;$a<<=1;if($a&0x10000){$a^=
0x18005;}}printf"%04x %04x %d\n",$a0,$a,$b if$b<96;}'
\\seeking 41 or 28
0201 029e 37 << !!!
0402 029e 36
0804 029e 35
1008 029e 34
2010 029e 33
4020 029e 32
8040 029e 31
[greg@pavo greg]$ perl -e 'for$a0(0..65535){if(($_=unpack("B*",pack("N",$a0)))
=~y/1//>3){next;}$a=$a0;$b=0;while($b<96&&!grep {$_==$a} (0x0022,0x4400,
0xffdd,0xbbff,0x2200,0x0044,0xddff,0xffbb)){++$b;$a<<=1;if($a&0x10000){$a^=
0x18005;}}printf"%04x %04x %d\n",$a0,$a,$b if$b<96;}'
\\seeking a or 5
0003 0022 46
0005 0022 31
0006 0022 45
000a 0022 30 <<
000c 0022 44
0011 0022 1
0014 0022 29
0018 0022 43
0022 0022 0
0028 0022 28
0030 0022 42
0044 0044 0
0050 0022 27
0060 0022 41
0088 2200 6
00a0 0022 26
00c0 0022 40
0110 2200 5
0140 0022 25
0180 0022 39
0220 2200 4
0280 0022 24
0300 0022 38
0440 2200 3
0500 0022 23
0600 0022 37
0880 2200 2
0a00 0022 22
0c00 0022 36
1100 2200 1
1400 0022 21
1800 0022 35
2200 2200 0
2800 0022 20
3000 0022 34
4001 0022 62
4400 4400 0
5000 0022 19
6000 0022 33
8001 0022 60
8002 0022 61
a000 0022 18
c000 0022 32
The arrowed matches show a pattern of 16+7n bits distance, indicating 7 bit ASCII, and all these match the original CRC, indicating the tests are already using the right function. Now to check the theory with a special 7-bit CRC function:
Code:
[greg@pavo greg]$ perl -ne 'chomp;$r=0;while($_ ne""){$c=hex(substr($_,0,2,""
))&0x7F;$r^=$c<<9;for$b(0..6){$r<<=1;if($r&0x10000){$r^=0x18005;}}}printf
"%04x %05d\n\n",$r,$r;'
01000000000000
e006 57350

01000001030000
628a 25226

351d3030331d30
11cf 04559
Q.E.D.
Ranko
Guest







Nov 04, 2009 8:38 am

AMAZING!

Greg, you're a genius!!!

I'm going to cross check it right now. If you're interested here are some longer examples:

Request:
01 31 32 1D 30 32 30 1D 30 03 32 30 37 33 33 04
Answer:
01 31 32 02 32 30 1D 31 39 39 34 31 31 38 20 30 31 31 30 31 30 31 39 39 31 31 31 39 20 39 37 31 30 32
32 31 39 39 34 31 31 39 20 30 31 31 30 31 30 31 39 38 39 31 32 31 20 39 36 30 39 31 38 20 20 20 20 20
20 20 20 20 20 20 20 20 20 31 39 39 30 31 30 31 20 39 36 30 39 31 38 03 35 38 35 31 30 04

or another ASCII example:
request:
[SOH]12[GS]003[GS]0[ETX]54769[EOT]
Answer:
[SOH]12[STX]3[GS]000101648090423[ ][ ]000000027-0001-000300000000000000000000000000000000000[ETX]177
40[EOT]
([ ] means Spacechar)

It would be perfect to me , if you can e-mail me a long division. Pls send to:
michael.junkers@leineweb.de

I have to make a C-code which checks the CRC. If i'm right you make all the calculations in only one single line:

Code:
[greg@pavo greg]$ perl -ne 'chomp;$r=0;while($_ ne""){$c=hex(substr($_,0,2,""
))&0x7F;$r^=$c<<9;for$b(0..6){$r<<=1;if($r&0x10000){$r^=0x18005;}}}printf
"%04x %05d\n\n",$r,$r;

I'm unfortunately not into Perl, so if you can help me what "chomp" and "substr" does, it would be a big help for me to implement the code.

But big thanks for your really great work!!
I talked to my boss about your research and he was impressed also. He would like to give you a little credit, so plz mail me.

Hope to hear/read you soon...
Greets Michael
regregex
Preferred Member



Joined: 30 Oct 2007
Posts: 184
Location: London, UK

Nov 05, 2009 4:56 pm

Thanks for your reply. I have sent you a mail.

--Greg
Guest








Feb 06, 2013 12:23 pm

I have tried to write a code as per Greg's Input but not working is byte size is more than 7

static unsigned short CRC16_BUYPASS(unsigned char *data, size_t len) {
unsigned short crc = 0x0000;
size_t j;
int i;
int k;
unsigned char byte = 0;
unsigned char nbyte;
unsigned char bytemap[] = {0x01,0x03,0x07,0x0f,0x1f,0x3f,0x7f,0xff};
unsigned char byteShiftmap[] = {7,6,5,4,3,2,1,0};
printf("\n\rData at entry: ");
for(i = 0; i < len; i++){
printf(" 0x%02X",data[i]);
}
j = 0;
k = 7;
for (i = len-1; i > 0; i--) {

if (((j % 7) == 0) && (j>1)){
for(k = i; k > 1;k--){
data[k] = data[k-1];
}
data[0] = 0;
//i--;
}
k = j % 7;
byte = data[ i ]; //take current byte
nbyte = data[ i - 1];

nbyte &= bytemap[k];
nbyte = nbyte << byteShiftmap[k];
data[i] = (byte & 0x7F) | nbyte;

nbyte = data[i-1] & (0xff ^ bytemap[k]);
data[i-1] = nbyte >> ((k) + 1);
j++;

}
printf("\n\rData after BUYPASS: ");
for(i = 0; i < len; i++){
printf(" 0x%02X",data[i]);
data[i] = reverse(data[i]);
}
crc_value = crc;
printf("\n\rData at exit: ");
for(i = 0; i < len; i++){
printf(" 0x%02X",data[i]);
crc_chr(data[i]);
}
crc = crc_value;
return (crc);
}

       Computer Interfacing Forum Index -> Error detection and correction
Page 1 of 1



Running on php BB © 2001, 2009 php BB Group
   Lammert Bies     Interfacing     Sitemap     Forum