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
Search the forums here for "CRC".
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
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.
AFAIK
There are atleast 2 crc routines included in avrlib-c ...
Doesnt anyone ever look in the lib-c ref manual :wink: :wink:
/Bingo
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
@rubi
A search revealed this
https://www.avrfreaks.net/phpBB2/...
Edit: ... I can see you allready found it.
/Bingo
