Solved

Checksum code in C

Posted on 2003-12-04
7
4,129 Views
Last Modified: 2008-02-01
Dear experts,

        I need to add a checksum to a frame that will be sent from client A to Client B thru protocol. Could someone please show me an example of checksum code to add a checksum to a frame before it is send, on client A side, and calculating the checksum for error detection on the receiver side (client B)?

Please reply asap.
Thank you.
0
Comment
Question by:erimay
7 Comments
 
LVL 45

Assisted Solution

by:sunnycoder
sunnycoder earned 40 total points
ID: 9873037
0
 
LVL 4

Expert Comment

by:void_main
ID: 9873304
Or you download the quake II source code from www.idsoftware.com and have a look into crc.c and crc.h. There is networking code for client/server too, but only if you download the full sourcecode (not the "game source")
I think that could help!
0
 
LVL 4

Assisted Solution

by:skypalae
skypalae earned 40 total points
ID: 9873593
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.

0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 4

Expert Comment

by:skypalae
ID: 9873626
Well. the example i've posted is not really using bytes, but half-bytes (nibbles). but you can easily modify it to bytes, words, whatever you want (and can XOR it).
S.
0
 
LVL 45

Accepted Solution

by:
Kdo earned 100 total points
ID: 9904477
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
0
 
LVL 7

Expert Comment

by:Big_Red_Dog
ID: 11053195
Kdo forgot to advance the pointer in the buffer...

Here's the corrected code:

/*
  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, Ptr++)
  {
    XORValue ^= *Ptr;
    SUMValue += (*Ptr * idx);
  }
  return (XORValue ^ SumValue);
}
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now