Checksum code in C

Hi,

there are3 many algorithms calculating checksums. You only have to choose which will you use. One more thing you should think of. And it is what type of check code do you want to send. Will it only detect error? Or will it be able to correct an error? Or 2 or more errors? Every code is slightly different, but generally calculating the more self repairing codes takes more time, more memory and larger code to send. And if you check the code and you find out that there are more errors because of transmission than the code can repair, you have to ask for whole packet again. Especially if the error is in the code.

The most easy is simple checksum. Just take your packet byte by byte and add those bytes (never mind overflowing ... or you can XOR them). In the end you have a code. Reciever then adds every byte and if the sum is same as the last one the packet os OK. (In case of XORing, you process the code too and result must be 0). This code is very fast and efficient until you get 2 errors. If they appear and they are same (like one byte will be 1 bigger and other byte will be 1 lower), the code gives good result, but there are errors. in the trasmitted data. In that case you can enlarge the code to word or long, but the same thing may happen too.

The error repairing codes are slightly different. I can't remember how classis CRC works, but it has something to do with polynomial division, modulo of that. The code was quite complicated to calculate, but when checked (in case of error) it gave exact position of the error (as far as i remember, you can enlarge the code to check 2 or more errors)

...

The other self repairing code is quite simple and it checks for exact error position too. First arrange all your data into rectangle areas (i'll use 4x4 rectangles in my example)

so imagine data

1001010110000011

like this

1001
0101
1000
0011

now do the XOR on each line and on each column now you get this:

0110
--------
1001 | 0
0101 | 0
1000 | 1
0011 | 0

and return everything into linear again

data: 1001010110000011 col_codes: 0110 row_codes: 0010

so after every 2 bytes you send 1 byte of code. If you use larger rectangles, the relative size of code will be smaller, but it will catch less errors .. you decide what ratio you want. The reciever side does exactly the same and then it compares the codes. If there are differencies, (in case of one error) the positions of the differencies give you exact position (column, row) of bit changed.

same can be dane with bytes .. i'll write simple steps (includeng error)

packet :
1fe03a83b24573a1

rectangle:
1fe0
3a83
b245
73a1

coded recnagle:
e487
------
1fe0 | 0
3a83 | 2
b245 | 8
73a1 | f

coded packet:
1fe03a83b24573a1 e487 028f

........

recieved packed:
1fe03a83b44573a1 e487 028f

rectangle packet (coded)

e287
------
1fe0 | 0
3a83 | 2
b445 | e
73a1 | f

compare codes and find ERROR!!
2.column (sent code 4, calculated code 2)
3.row (sent code 8, calculated e)

2 XOR 4 -> 6
8 XOR e -> 6
seems, that codes are ok, error is in the packet. if the result differ, the error might be in the codes.

recieved value 4, error correction 6

4 XOR 6 -> 2

new value 2




Is it clear enough? I'm sure you don't need source. You can writye your own :)
S.

Hi erimay,

There's been no activity here for a few days and I'm feeling "talkative".

Checksums.  The word has been around a long time and has come to mean "a series of calculations on a dataset that offers reasonable protection against data change".  But the protection that it offers is often a false sense of security.

Some of the oldest checksum algorithms simply XOR all of the values in the dataset and produce a final result.  (One was shown earlier in this thread.)  While this does offer some protection over single bit changes, it no longer offers adequate data protection.  (The days when read/write errors or communications errors result in a single bit changing are pretty well behind us.)  Besides, there are so many calculcations that produce a single value, that a better algorithm was/is needed.

'A' = 0x41
'B' = 0x42
-----------
        0x03  Checksum using the XOR method.

If any one value in the region being checksummed is to change, the checksum value will also change.  (Simple algebra here.  A = B ^ C.  If two of the values are known, the third is also known.)

But if both values change, then the new checksum value may or may not be the original checksum value.

'E' = 0x45
'F' = 0x46
-----------
        0x03 Checksum using the XOR method.  The same as checksumming 'A' and 'B'

So a complete change of the data may not be caught, but if any one bit, or byte (including the checksum value) is changed then recalcuating the checksum will detect the change.  Anyone with malicious intent should be able change a value in the data and correctly adjust the checksum with little effort.

Clearly a better form of checksum calculation is required.  The next generation of checksum algorithms offered somewhat better security by performing two sets of calculations on the data and merging the result.  The oldest duel-calculation algorithm that I know of generated one result by an XOR of all of the data values.  It generated a second result simply by adding all of the bytes together.  The two results were then XORed to produce a final checksum.  But this too proved too little.

'A' = 0x41
'B' = 0x42
-----------
      0x003 Checksum value using XOR
      0x083 Checksum value using + (add)
-----------
      0x080 Final Checksum

But again the mathematics breaks down when you simply swap two bytes.  Algebra's basic rules of A+B=B+A and A*B=B*A are pretty hard to get around.

Not only is this pretty low hurdle for someone with malicious intent, it offers no protection over one of the most simple human errors -- transposing digits.  Transpose two digits when someone is entering a telephone number and the worst thing that happens is some yelling and screaming when you dial the wrong number at 4:00AM.  Transpose two digits when entering a Credit Card Number can be disastrous.  (Credit card numbers have very robust validity algorithms to protect against single digit change, side-by-side digit transposition, random digit transposition, and other data changes.)

Checksum algorithms generation 2.1 modified the addition half of the calculation by multiplying the character value by its position in the dataset.  Suddenly, it became much harder to randomly change data and adjust the checksum.

'A' = 0x41
'B' = 0x42
-----------
      0x003 Checksum value using XOR
      0x0C5 Checksum value using + (add)  0x41 * 1 + 0x42 * 2
-----------
      0x0C6 Final Checksum

'B' = 0x42
'A' = 0x41
-----------
      0x003 Checksum value using XOR
      0x0C4 Checksum value using + (add)  0x42 * 1 + 0x41 * 2
-----------
      0x0C7 Final Checksum

Many forms of checksums still exist today.  A Cyclic Redundancy Check is a modern version of a checksum.  It's more secure than any of the algorithm mentioned so far.  It's also more compute intensive since there a numerous calculations performed on each byte.  Still, for your application a simple and secure checksum algorithm should do just fine.

/*
  ChecksumRegion -- Calculate a checksum over a memory region
    Buffer - Start address of region to checksum
    Length - Number of bytes to checksum
*/

int ChecksumRegion (void *Buffer, int Length)
{
  unsigned char *Ptr;
  int   idx;
  int   XORValue;
  int   SUMValue;

  Ptr = (unsigned char *)Buffer;
  XORValue = 0;
  SUMValue = 0;
  for (idx = 1; idx <= Length; ++idx)
  {
    XORValue ^= *Ptr;
    SUMValue += (*Ptr * idx);
  }
  return (XORValue ^ SumValue);
}

Ok.  I guess that I'm over this 'talkative' mood this morning.

Good Luck with your program,
Kent