Computer Interfacing
Discussions about interfacing and electronics
 

CRC calculation

Can't find the right way....

Goto page 1, 2  Next
 

       Computer Interfacing Forum Index -> Error detection and correction
Author Message
jojahn
New User



Joined: 29 Mar 2010
Posts: 4


Mar 29, 2010 11:40 am

Good day everybody,
I recorded a sequence of data with a CRC atthe end. Here is the sequence:
02 3F 00 00 00 00 00 00 A2 47
02 32 00 00 00 00 00 00 ED 69

The information I found so far:
CRC - CCITT x16+x12+X5+1
Initialize CRC_LOW = FF
Initialize CRC_High = FF

Negate bit by bit CRC_Low and CRC_High for final CRC

Can somebody explain to me, how it works and the concept of deriving the CRC?

I am really stuck!

Thank you all.
Josh
Gammatester
Guest







Mar 29, 2010 5:52 pm

This is CRC-16/X-25:
Code:
===== Checking for known algorithms =====
Checked data sets
CRC1: $A247,   Data1: 023F000000000000
CRC2: $ED69,   Data2: 0232000000000000
Found known algorithm: CRC-16/X-25
CRC=$47a2  Poly=$1021  init=$ffff  xorout=$ffff  refin=true   refout=true
 *** Second data set verified
===== done =====

The parameters are the so-called Rocksoft parameters, described in Ross Williams's text "A Painless Guide to CRC Error Detection Algorithms". His text contains an introduction into CRC calculation and C reference code. In this forum's thread "CRC on HNZ Protocol" by Tauchid from Feb. 17, 2010 I posted Pascal source code for X25.

For general info about CRC you should search/read Ross Williams' text or e.g. the Wikipedia article Cyclic_redundancy_check.

Hope that helps

Gammatester
jojahn
New User



Joined: 29 Mar 2010
Posts: 4


Mar 30, 2010 12:05 pm

Thank you very much for your help, Gammatester. It is working and the Pascal code produces the same results! Cool.
Now I am looking to the same code in VB and/or C. Any ideas?
Thanks again, Josh
Gammatester
Guest







Mar 30, 2010 5:55 pm

I don't know how to do it with VB, but C is easy. Here is a quick implementation translated from my Pascal code, the main function calculates the Rocksoft check value and the CRC of your first data set.
Code:
#include <stdio.h>
#include <stddef.h>
#include <stdint.h>

uint16_t crcx25(const uint8_t *data, size_t len) {
  uint16_t crc = 0xFFFF;
  int i;
  if (len) do {
    crc ^= *data++;
    for (i=0; i<8; i++) {
      if (crc & 1) crc = (crc >> 1) ^ 0x8408;
      else crc >>= 1;
    }
  } while (--len);
  return(~crc);
}

int main(int argc, char *argv[])
{
  uint8_t test1[9] = {0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39};
  uint8_t test2[8] = {0x02,0x3F,0x00,0x00,0x00,0x00,0x00,0x00};
  uint16_t crc;
  crc = crcx25(test1, sizeof(test1));
  printf("Rocksoft check value:  0x%04X\n", crc);
  crc = crcx25(test2, sizeof(test2));
  printf(" jojahn's data set 1:  0x%04X\n", crc);
  return 0;
}
The output is
Code:
Rocksoft check value:  0x906E
 jojahn's data set 1:  0x47A2
jojahn
New User



Joined: 29 Mar 2010
Posts: 4


Mar 31, 2010 1:31 am

Thank you so much for your reply!!
I don't want to bother you too much but, is there a simple way to explain what and how the software works?
I tried sooo many examples and did it on paper - nothing comes up with the correct CRC. Is there something wrong with the concept?
What I do on paper:





Code:
Private Sub Command1_Click()
  Dim crc As Long

  Dim test1(8) As Long
  test1(0) = &H2
  test1(1) = &H32
  test1(2) = &H0
  test1(3) = &H0
  test1(4) = &H0
  test1(5) = &H0
  test1(6) = &H0
  test1(7) = &H0
 

  Dim Temp As Long
  crc = &HFFFF&
  Const PolyX25 = &H8408&
 
  For j = 0 To 7
      Temp = test1(j) Xor PolyX25
    crc = crc Xor Temp
       
   
    For i = 0 To 7
      If (crc And &H8000&) <> 0 Then
          crc = ((crc And &H8000&) Xor PolyX25) And &HFFFF&
      Else
          crc = (crc And &H8000&) And &HFFFF&
    End If
    Next i
  Next j
 
  Ncrc = Not crc
Code:
   02       32        00       00      00      00 +2x
00000010'00110010'00000000'00000000'0000000'000000etc
      10 00010000 001000
   ---------------------
      00 00100010 001000
           100001 00000010 00
          ---------------------
           000011 00100010 00
               10 00010000 001000
             ---------------------
                1 00110010 001000
                1 00001000 0001000
               ---------------------
                    111010 0011000
                    100001 00000010 00
                    ---------------------           
                     11011 00110010 00
                     10000 10000001 000
                     ---------------------
                      1011 10110011 000

etc....
Gammatester
Guest







Mar 31, 2010 8:47 am

The main problems with your code are, that you do not use any shifts and that you mix concepts from reflected and non-reflected versions. Remember that X25 has Rocksoft parameters refin=true and refout=true. That means: you can use the "normal" algorithm if you reflect each input byte, ie your second data set {0x02,0x32,0x00,0x00,0x00,0x00,0x00,0x00} is reflected to {0x40,0x4c,0x00,0x00,0x00,0x00,0x00,0x00}. After processing all 8 bytes you get 0x4869. The reflected value of 0x4869 is 0x9612, and if you xor this with 0xffff you get your final CRC 0x69ed.

Here is a Pascal version with this concept that works with your and the Rocksoft test data:
Code:
function crcx25(const b: array of byte): word;
  {-CRC16/X-25 using unreflected poly and reflected input bytes}
const
  PolyX25 = $1021;
var
  crc: word;
  i,j: integer;
begin
   crc := $FFFF;
   for i:=low(b) to high(b) do begin
     crc := crc xor (cm_reflect(b[i],8) shl 8);
     for j:=1 to 8 do begin
       if (crc and $8000 = 0) then crc := (crc shl 1)
       else crc := (crc shl 1) xor PolyX25
     end;
   end;
   crcx25 := cm_reflect(crc,16) xor $FFFF;
end;
But instead of reflecting each input byte, my and most other implementation use the reflected poly, test the lowest bit, and shift in the other direction.

Without much knowledge about Basic, here is a version derived from your post which should work. The right shift by 1 is replaced integer division by 2 (which is IIRC the operator "\"). A final note: I guess the variable crc is a 32 bit (long) integer during your code, there for you have to mask the final (Not crc).
Code:
Private Sub Command1_Click()
  Dim crc As Long

  Dim test1(8) As Long
  test1(0) = &H2
  test1(1) = &H32
  test1(2) = &H0
  test1(3) = &H0
  test1(4) = &H0
  test1(5) = &H0
  test1(6) = &H0
  test1(7) = &H0

  crc = &HFFFF&
  Const RefPolyX25 = &H8408&

  For j = 0 To 7
    crc = crc Xor test(j)
    For i = 0 To 7
      If (crc And 1) <> 0 Then
          crc = ((crc \ 2) Xor RefPolyX25) And &HFFFF&
      Else
          crc = (crc \ 2) And &HFFFF&
    End If
    Next i
  Next j

  Ncrc = (Not crc) And &HFFFF&
For more info you should study Ross Williams' text and the C reference code (especially the functions cm_nxt and reflect).
jojahn
New User



Joined: 29 Mar 2010
Posts: 4


Mar 31, 2010 10:06 am

Gammatester,
I thank you so much for your help. I read the articles you are refering to but, I couldn't figure it out. The compact code of C didn't make it easier, either.

Now I got it - finally!

Thank's again
Josh
xenoion
New User



Joined: 09 Dec 2010
Posts: 7
Location: Jakarta, Indonesia

Dec 09, 2010 8:39 am

hi Gammatester, i just wondering why my PHP code doesn't show the same output like your C code?

this is my code (i just copy paste your code and change it a little):
Code:

function crcx25($data, $len) {
  $crc = 0xFFFF;
  if ($len) do {
    $crc ^= $data++;
    for ($i=0; $i<8; $i++) {
      if ($crc & 1) $crc = ($crc >> 1) ^ 0x8408;
      else $crc >>= 1;
    }
  } while (--$len);
  return(~$crc);
}

$data = '31 32 33 34 35 36 37 38 39' ;
$test = crcx25($data,5) ;
echo $test.'<br>' ;
echo 'test = '.dechex($test).'<br>' ;
echo 'test = '.base_convert($test,10,16).'<br>' ;

and this is the output :
Code:

-44562
test = ffff51ee
test = ae12


please help me, i still don't understand with this.
Gammatester
Guest







Dec 09, 2010 10:31 am

I guess you show a typical drawback of wanna-be programming languages without strong typing. Obviously $len shall be an integer, but what does your function expect in the parameter $data? A string of characters? A sequence of bytes? A string of Hex encoded bytes? Or what?
Quote:
$data = '31 32 33 34 35 36 37 38 39' ;
$test = crcx25($data,5) ;
Anyway, the last line of the quote indicates a lenth of 5 (bytes, chars, ....). But even with a very generous interpretation $data has at least 9 units, definitely it has 26 characters.

If your 'programming language' is not able to handle byte strings directly, you have to split and convert the data input inline in the byte processing loop.
xenoion
New User



Joined: 09 Dec 2010
Posts: 7
Location: Jakarta, Indonesia

Dec 09, 2010 11:18 am

let's straight to my problem. Smile actually I'm receiving data from GPS device and the communications protocols says that uses CRC ITU checksum.

2 Examples (Hex Values):
Data from device: 78 78 0D 01 03 53 41 90 30 08 01 59 00 01 -->CRC= 5C BC
Reply from server: 78 78 05 01 00 01 -->CRC= D9 DC

so the $data from the previous post is refer to data that will send from server to device.
can you give me a function to calculate the CRC?

thanks before,
Aditya
regregex
Preferred Member



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

Dec 09, 2010 4:14 pm

Hello Aditya,

Your CRC function is correct except, as Gammatester points out, for the interpretation of $data. 0x51ee is the right CRC of the wrong string: PHP is treating $data as a numeric and taking the first numeric it finds, i.e. '31'. So it is calculating the CRC of five '\x1f' characters.

Also, whereas *data++ is the usual way to step through a C string, ++ on a string variable in PHP does something *completely* different Wink

You'll need to use something like:
Code:
    $crc ^= ord(substr($data, -$len));

(Aside: Sure, scripting languages aren't rigorous: Larry Wall's magic odometer is ueber-crufty. But I would hate to have to wrangle with strong-typing on every occasion where I currently use Perl one-liners.)

--Greg
xenoion
New User



Joined: 09 Dec 2010
Posts: 7
Location: Jakarta, Indonesia

Dec 10, 2010 4:23 am

thanks regregex... i will try it first.. Smile

if you don't mind, please visit my topic in t=1630 (i don't have rights to post link yet). i have write down all my problem there.. Smile
xenoion
New User



Joined: 09 Dec 2010
Posts: 7
Location: Jakarta, Indonesia

Dec 13, 2010 10:39 am

hello all, i have tried to rebuild my function with some change..
Code:
function crcx25($data) {
   //i explode() $data and make $content array
   $content = explode(' ',$data) ;
   //i count() the array to get data length
   $len = count($content) ;
   $n = 0 ;
   
   $crc = 0xFFFF;   
   while ($len > 0)
   {
      $crc ^= $content[$n] ;
      for ($i=0; $i<8; $i++) {
         if ($crc & 1) $crc = ($crc >> 1) ^ 0x8408;
         else $crc >>= 1;
      }
      $n++ ;
      $len-- ;
   }
   
   return(~$crc);
}
//$data is substr() result from hexadecimal converted binary data using bin2hex() and i put 'space' in it.
$data = '05 01 00 01' ;
$crc25 = crcx25($data) ;

echo $crc25.'<br>' ;
echo 'crc25 = '.dechex($crc25).'<br>' ;
echo 'crc25 = '.str_replace('ffff','',dechex($crc25)).'<br>' ;
i got this result with this function
Code:
-9764
crc25 = ffffd9dc
crc25 = d9dc
it means that i have got the right crc, because it is same with the example from the communication protocol document.
Code:
//example from communication protocol
05 01 00 01 -> D9 DC
BUT, if i change the $data with other value like '05 13 00 03' or '05 13 00 11', it doesn't same with the example from the communication protocol.
Code:
//example from communication protocol
05 13 00 03 -> CA E3
05 13 00 11 -> F9 70

//the function result
05 13 00 03 -> 5f 6d
05 13 00 11 -> d3 25
anyone can tell me what happen? is my function correct?

thanks,
Aditya
Gammatester
Guest







Dec 13, 2010 11:51 am

Quote:
anyone can tell me what happen? is my function correct?
No, your function is not correct, because the examples from the communication protocol give valid X25 CRCs. The error is, that your function treats the input "05 13 00 03" as decimal values, actually calculating the correct CRC value "5f 6d" for "05 0D 00 03". As already said, if you want to calculate CRCs of hex strings, you have to split and convert the input. Splitting seems to work, it remains to find a PHP function for converting the units from Hex to decimal.
xenoion
New User



Joined: 09 Dec 2010
Posts: 7
Location: Jakarta, Indonesia

Dec 14, 2010 2:43 am

Wooohoo..!! thanks a lot Gammatester your answer save my day.. Smile

thanks for all guys.. !!

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



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