C Checksum algorithm

Go To Last Post
7 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi All

In my new project I will use a RF interface to the ATMega16 in full duplex.

To check the transmitted data I would need a fast and easy to implement checksum algorithm.
Could you please tell me where to find one.

I started to implement my own, but I think there must be smarter,shorter and faster algorythms available.

Cheers
Rubi

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Search the forums here for "CRC".

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

IP Heaader checksum:

;***************************************************************
;* cksum
;*
;* In: Z - Packets address
;* X - Packet lenght
;*
;* Out: R17:R16 - Checksum
;*
; Calc checksum. Reads packet at offset Z for X bytes and calculates
; the checksum in R17:R16.
;

.def chksumL = R1
.def chksumM = R2
.def chksumH = R3
.def chksumHH= R4

cksum: clr R6
clr chksumL ;we do the arithmetic
clr chksumM
clr chksumH
clr chksumHH
ldi R17,2

cksuml: cp XL,R17
cpc XH,R6
brcs cksumEnd
cksum2:
ld R5,Z+ ;get high byte of 16-bit word
ld R16,Z+
add chksumL,R16 ;add to accum
adc chksumM,R5
adc chksumH,R6
adc chksumHH,R6
sbiw XL,2
rjmp cksuml

cksumEnd:
cpi XL,1 ;ha paratrlan a cim akkor az utolso byte is kell meg
brne cksumEnd1
ld R16,Z+ ;get high byte of 16-bit word
add chksumL,R16 ;add to last byte or zero
adc chksumM,R6
adc chksumH,R6
adc chksumHH,R6

cksumEnd1:
add chksumL,chksumH
adc chksumM,chksumHH ;chksum16= ~(hdr_chksum + ((hdr_chksum & 0xFFFF0000) >> 16));
mov R16,chksumL
mov R17,chksumM
com R16
com R17
ret

----------------------------------

Xmodem CRC calc:

;***************************************************************************
;** Calc & Update XMODEM CRC
;*
;* In: R0 - data byte

UpdateCRC: lds R17,CRC+1
mov R15,R17
swap R17
mov R16,R17

eor R17,R15
andi R17,0xF0
andi R16,0x0F
eor R15,R16

mov R14,R17
lsl R14
rol R16

eor R15, R14
eor R17,R16

lds R14,CRC+0
eor R15,R0
eor R17,R14

sts CRC+0,R15
sts CRC+1,R17
ret

VFX.
http://www.vfx.hu

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Alternatively you can use hamming codes. They give you error correction, at expense of size (actually generally best is a hybrid method).

following code converts between 8 bit bytes and 14-bit codes (actually 2 7-bit codes), and will correct 1 bit error every 4 bits:

hamming.c:

#include 

#include "hamming.h"

const static uint8_t codes[] = { 
		0x00, 0x70, 0x4c, 0x3c,
		0x2a, 0x5a, 0x66, 0x16, 
		0x69, 0x19, 0x25, 0x55, 
		0x43, 0x33, 0x0f, 0x7f
	};

static inline uint8_t ecc_hamming_encode_nybble(uint8_t n)
{
	return codes[n & 0x0f];
}

static inline uint8_t ecc_hamming_decode_nybble(uint8_t o)
{
	int8_t x = o & (1 << 6);
	int8_t y = o & (1 << 5);
	int8_t p = o & (1 << 4);
	int8_t z = o & (1 << 3);
	int8_t q = o & (1 << 2);
	int8_t r = o & (1 << 1);
	int8_t s = o & (1 << 0);
	int8_t e;


	e = (x >> 6) ^ (p >> 4) ^ (q >> 2) ^ (s >> 0);
	e |= (y >> 4) ^ (p >> 3) ^ (r >> 0) ^ (s << 1);
	e |= (z >> 0) ^ (q << 1) ^ (r << 2) ^ (s << 3);

	
	switch (e) {
		case 3:
			p ^= (1 << 4);
			break;
		case 5:
			q ^= (1 << 2);
			break;
		case 6:
			r ^= (1 << 1);
			break;
		case 7:
			s ^= (1 << 0);
			break;
	}
	
	return (p >> 4) | (q >> 1) | (r << 1) | (s << 3);
}


uint16_t ecc_hamming_encode_byte(uint8_t byte)
{
// 14-bit output


	return (ecc_hamming_encode_nybble(byte >> 4) << 7)
		| (ecc_hamming_encode_nybble(byte));
}


uint8_t ecc_hamming_decode_byte(uint16_t code)
{
// 14-bit input

	return (ecc_hamming_decode_nybble(code >> 7) << 4) 
	       | ecc_hamming_decode_nybble(code);	
}

hamming.h:

#ifndef __HAMMING_H__
#define __HAMMING_H__

/* Returns a hamming code for a byte; 14 bits,
 *  left-aligned (bottom 2 bits 0), for easy
 *  rotating out MSB first
 */

uint16_t ecc_hamming_encode_byte(uint8_t byte);

/* Returns original byte for the hamming code
 *  from above function
 */

uint8_t ecc_hamming_decode_byte(uint16_t code);

#endif /* #ifndef __HAMMING_H__ */

There's a lot of different code lengths, etc... for AVR driving, with less overhead / size I found the codes for 4-bits to be best for my usage... but there are lots of good papers on hamming codes, etc out there... and they're not that difficult.

Note with RF though while fixing single bit errors can really help prevent retransmissions and lost data in many cases, there are often consecutive bit errors, for which hamming codes won't generally help all that much, and checksums are still useful, or something like reed solomon codes, etc. which do very well with consecutive errors (at expense of computational work)... i still don't get reed-solomon codes :) but still have a lot of other things to learn before i spend much time on 'em.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

AFAIK

There are atleast 2 crc routines included in avrlib-c ...

Doesnt anyone ever look in the lib-c ref manual :wink: :wink:

/Bingo

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

First @Bingo600
I know there are routines in GCC with CRC, but first browsing through the forum I read that people had problem with porting them to their PC.
That is why I did not want to use them.
For AVR-AVR communication I would also recomend them, but what I need is PC to AVR.

Dear tymm and VFX

Thank you verry much for your code. I am now writing on the communication programm on the PC (server) side and will implement both routines, since space is not an issue there and both routines are looking verry interesting.
On the AVR I will check which routine needs less code space and if this routine does not work as expected I have a fallback.

"Programmers heart what which thou more"

Again thanks a lot!!!

Cheers
Rubi

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

@rubi

A search revealed this

https://www.avrfreaks.net/phpBB2/...

Edit: ... I can see you allready found it.

/Bingo