📄 crc16.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0066)http://homepage.ntlworld.com/matthew.rowe/micros/virbook/crc16.htm -->
<HTML><HEAD><TITLE>CRC16</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY background=CRC16.files/squared.gif><A
href="http://homepage.ntlworld.com/matthew.rowe/micros/virbook/index.htm"><IMG
src="CRC16.files/ring.gif" align=top border=0></A><BR>
<H1>Implementing some CRC16 routines and checksums </H1>
<P>Here is a program to calculate CRC-16 on a 16Cxx. The resulting CRC value is
identical to that calculated by common archive programs, such as ZOO. Fast
table-based CRC calculators for this polynomial are available as C
source.<BR><BR><PRE>----- C source --------------------------------------------------------
unsigned CRC;
unsigned crc_16(char c)
{
int i,j;
for(i=0;i!=8;c>>=1,i++)
{
j=(c^CRC)&1;
CRC>>=1;
if(j)
CRC^=0xa001;
}
return CRC;
}
----- 16CXX source ----------------------------------------------------
Temp = 0x20
Count = 0x21
CRC_High = 0x22
CRC_Low = 0x23
loop macro reg,label
decfsz reg
goto label
endm
movlw "h"
call CalcCRC
movlw "e"
call CalcCRC
movlw "l"
call CalcCRC
movlw "l"
call CalcCRC
movlw "o"
call CalcCRC
Halt goto Halt
; result=0x34d2 (you can check that with ZOO)
----- CRC subroutine --------------------------------------------------
CalcCRC movwf Temp ; about 125 cycles on average
movlw 8
movwf Count
CRC_Loop movf CRC_Low,w
xorwf Temp,w
clrc
rrf CRC_High
rrf CRC_Low
andlw 1
bz CRC_Skip
movlw 0xa0
xorwf CRC_High
movlw 0x01
xorwf CRC_Low
CRC_Skip rrf Temp
loop Count,CRC_Loop
return
</PRE>Thanks to Frank Vorstenbosch for this<BR><BR>
<HR>
<H3>Another alternative</H3>This routine from Andrew Warren uses the standard
X.25 (and XMODEM) polynomial: x^16+x^12+x^5+1.<BR><BR>It's not the fastest
possible, but it does the job and doesn't take much code. It takes your message,
one bit at a time (you have to write the code for that and put it at the LOOP
label, since I don't know how your data's organized), and exits with the CRC in
CRCHI:CRCLO. When I originally posted this code on the Microchip BBS, I wrote it
on-line, so I haven't assembled or tested it:<BR><PRE>
CRCHI EQU some register
CRCLO EQU another register
CLRF CRCHI
CLRF CRCLO
;Append 16 "0"s to your message here.
LOOP ;If there are no more bits in your message, go to
;"DONE". Otherwise, left-shift the next bit of your
;message into the carry here.
RLF CRCLO
RLF CRCHI
SKPC
GOTO LOOP
MOVLW 00100001B
XORWF CRCLO
MOVLW 00010000B
XORWF CRCHI
GOTO LOOP
DONE ;The CRC is in "CRCHI" and "CRCLO".
</PRE><BR>
<HR>
<H3>Even simpler checksums</H3>> A checksum can be just the sum of all the
data '1' s in the bytes of the string. The generic way to do this is:<BR><PRE> check_sum = 0;
for each byte in the string
check_sum = check_sum + sum of bits in byte
</PRE><BR>There are several ways to count the number 1's in a byte. The three
routines shown below are a few examples. The first is the one you typically see
in programs that count bits; every bit is individually checked to see if it is 0
or 1. Everytime you get a 1, increment a counter. You don't want to use this
routine.<BR><BR>The second routine only loops one time for each bit that is set;
e.g. 00101000B only will loop twice. It's based on a clever algorithm that can
clear the right most bit that is set in a byte.<BR><BR>The third one is based on
a look up table. Here, the byte is broken into two nibbles and the look up table
contains 16 entries. Each entry corresponds to the number of bits set in the
offset of the table.<BR><BR><PRE>buffer0 equ 0x20
bits_counted equ 0x21
a_byte equ 0x23
ORG 0 ;Reset Vector
MOVF a_byte,W
CALL RR_bitcount
MOVF a_byte,W
CALL bitcount
MOVF a_byte,W
CALL look_up_bits
stay goto stay
;*****************************************************
;RR_bitcount
; Brute force shift and count.
RR_bitcount
MOVWF buffer0
CLRF bits_counted
RR1 CLRC
RRF buffer0,F ;Get LSB and put in the carry
SKPNC ;If LSB (i.e. C) is set
INCF bits_counted,F ;then count it
MOVF buffer0,F
SKPZ
GOTO RR1
RETURN
;*****************************************************
;bitcount
;
; This algorithm loops one time for each bit that is set.
;It's based on an algorithm that deletes the right most
;bit in a byte. If the byte is 'b' then the algorithm is:
; b = b & (b-1)
; for example if
; b = xxxx1000
; b-1 = xxxx0111
; b & (b-1) = xxxx0000 ;The right most bit of b is deleted
;
;This algorithm comes from a book titled "Efficient C", by
;Thomas Plum and Jim Brodie. They credit Kernighan and Ritchie
;for the original insight.
;
; Inputs: W - contains the byte whose bits need counting
; Outputs: bits_counted - # of bits that were set in W
;Memory Used: buffer0
bitcount
MOVWF buffer0 ;Save a copy
CLRF bits_counted ;
BC1 MOVF buffer0,W ;Get the byte. (affects Z too)
SKPNZ ;If no more bits are set
RETURN ; then we're done
INCF bits_counted,F ;Found a bit
DECF buffer0,F ;"b-1"
ANDWF buffer0,F ;b = b & (b-1) Delete right most bit
GOTO BC1
;*****************************************************
;look_up_bits
;
; This routine breaks the byte into nibbles and then counts
;the number of bits in each nibble (via a look up table).
;
look_up_bits
MOVWF buffer0
CLRF bits_counted
ANDLW 0x0f
CALL look_up
ADDWF bits_counted,F
SWAPF buffer0,W
ANDLW 0x0f
CALL look_up
ADDWF bits_counted,F
RETURN
look_up
ADDWF PCL,F
RETLW 0 ;0
RETLW 1 ;1
RETLW 1 ;2 has only one bit set
RETLW 2 ;3 has two bits set
RETLW 1 ;4 ...
RETLW 2 ;5
RETLW 2 ;6
RETLW 3 ;7
RETLW 1 ;8
RETLW 2 ;9
RETLW 2 ;a
RETLW 3 ;b
RETLW 2 ;c
RETLW 3 ;d
RETLW 3 ;e
RETLW 4 ;f
END
</PRE><BR>For random data, the look up table is by far the fastest: 13
cycles.<BR><BR>The number of cycles the "bitcount" routine takes is 5 + 7*number
of bits that are set i.e. between 5 and 61 cycles, or on average about 33
cycles. While this is slower than the look up table, it uses less code space. A
typical compromise.<BR>
<HR>
<BR>Thanks to Scott Dattalo for this <BR><A
href="http://homepage.ntlworld.com/matthew.rowe/micros/virbook/hex.htm"><IMG
src="CRC16.files/turnover.gif" align=right border=0></A><BR></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -