はじめに

背景

説明

マキシムの1-Wire CRC

1. 64ビット数値内の任意の場所にある奇数個のエラーのすべて
2. 64ビット数値内の任意の場所にあるダブルビットエラーのすべて
3. 8ビットの｢ウィンドウ｣内に含まれる任意のエラー群(1～8ビットの誤り)
4. これより大きなエラー群のほとんど

例1. アセンブリ言語による手順

DO_CRC:	PUSH ACC	;save accumulator
	PUSH B	;save the B register
	PUSH ACC	;save bits to be shifted
	MOV B,#8	;set shift = 8 bits ;

CRC_LOOP:	XRL A,CRC	;calculate CRC
	RRC A	;move it to the carry
	MOV A,CRC	;get the last CRC value
	JNC ZERO	;skip if data = 0
	XRL A,#18H	;update the CRC value
;
ZERO:	RRC A	;position the new CRC
	MOV CRC,A	;store the new CRC
	POP ACC	;get the remaining bits
	RR A	;position the next bit
	PUSH ACC	;save the remaining bits
	DJNZ B,CRC_LOOP	;repeat for eight bits
	POP ACC	;clean up the stack
	POP B	;restore the B register
	POP ACC	;restore the accumulator
	RET

例2. DOW CRCの計算例

例3. DOW CRCのルックアップ機能

Var
	CRC : Byte;
Procedure Do_CRC(X: Byte);
{
	This procedure calculates the cumulative Maxim 1-Wire CRC of all bytes passed to it. The result
	accumulates in the global variable CRC.
}
Const
	Table : Array[0..255] of Byte = (
	
	0, 94, 188, 226, 97, 63, 221, 131, 194, 156, 126, 32, 163, 253, 31, 65,
	157, 195, 33, 127, 252, 162, 64, 30, 95, 1, 227, 189, 62, 96, 130, 220,
	35, 125, 159, 193, 66, 28, 254, 160, 225, 191, 93, 3, 128, 222, 60, 98,
	190, 224, 2, 92, 223, 129, 99, 61, 124, 34, 192, 158, 29, 67, 161, 255,
	70, 24, 250, 164, 39, 121, 155, 197, 132, 218, 56, 102, 229, 187, 89, 7,
	219, 133, 103, 57, 186, 228, 6, 88, 25, 71, 165, 251, 120, 38, 196, 154,
	101, 59, 217, 135, 4, 90, 184, 230, 167, 249, 27, 69, 198, 152, 122, 36,
	248, 166, 68, 26, 153, 199, 37, 123, 58, 100, 134, 216, 91, 5, 231, 185,
	140, 210, 48, 110, 237, 179, 81, 15, 78, 16, 242, 172, 47, 113, 147, 205,
	17, 79, 173, 243, 112, 46, 204, 146, 211, 141, 111, 49, 178, 236, 14, 80,
	175, 241, 19, 77, 206, 144, 114, 44, 109, 51, 209, 143, 12, 82, 176, 238,
	50, 108, 142, 208, 83, 13, 239, 177, 240, 174, 76, 18, 145, 207, 45, 115,
	202, 148, 118, 40, 171, 245, 23, 73, 8, 86, 180, 234, 105, 55, 213, 139,
	87, 9, 235, 181, 54, 104, 138, 212, 149, 203, 41, 119, 244, 170, 72, 22,
	233, 183, 85, 11, 136, 214, 52, 106, 43, 117, 151, 201, 74, 20, 246, 168,
	116, 42, 200, 150, 21, 75, 169, 247, 182, 232, 10, 84, 215, 137, 107, 53);
	
Begin
	CRC := Table[CRC xor X];
End;

CRCレジスタとその1の補数の組み合わせ

iButton内でのRAMレコード用のCRC-16の計算

1. データレコード内の任意の場所にある奇数個のエラーのすべて
2. データレコード内の任意の場所にあるダブルビットエラーのすべて
3. 16ビットの｢ウィンドウ｣内に含まれる任意のエラー群(1～16ビットの誤り)
4. これより大きなエラー群のほとんど

例4. CRC-16を計算するためのアセンブリ言語

crc_lo data 20h ; lo byte of crc calculation (bit addressable)
crc_hi data 21h ; hi part of crc calculation



;---------------------------------------------------------------------------
;	CRC16 subroutine.
;	- accumulator is assumed to have byte to be crc'ed
;	- two direct variables are used crc_hi and crc_lo
;	- crc_hi and crc_lo contain the CRC16 result
;---------------------------------------------------------------------------
crc16:			; calculate crc with accumulator
	push b	; save value of b
	mov b, #08h	; number of bits to crc.
crc_get_bit:
	rrc a	; get low order bit into carry
	push acc	; save a for later use
	jc crc_in_1	;got a 1 input to crc
	mov c, crc_lo.0	;xor with a 0 input bit is bit
	sjmp crc_cont	;continue
crc_in_1:
	mov c, crc_lo.0	;xor with a 1 input bit
	cpl c	;is not bit.
crc_cont:
	jnc crc_shift	; if carry set, just shift
	cpl crc_hi.6	;complement bit 15 of crc
	cpl crc_lo.1	;complement bit 2 of crc
crc_shift
	mov a, crc_hi	; carry is in appropriate setting
	rrc a ; rotate	it
	mov crc_hi, a	; and save it
	mov a, crc_lo	; again, carry is okay
	rrc a ; rotate	it
	mov crc_lo, a	; and save it
	pop acc	; get acc back
	djnz b, crc_get_bit	; go get the next bit
	pop b	; restore b
	ret
	end

例5. 参照テーブルを用いたCRC-16用のアセンブリ言語

crc_lo data 40h	; any direct address is okay
crc_hi data 41h
tmp data 42h



;---------------------------------------------------------------------------
;	CRC16 subroutine.
;	- accumulator is assumed to have byte to be crc'ed
;	- three direct variables are used, tmp, crc_hi and crc_lo
;	- crc_hi and crc_lo contain the CRC16 result
;	- this CRC16 algorithm uses a table lookup
;---------------------------------------------------------------------------
crc16:
	xrl a, crc_lo	; create index into tables
	mov tmp, a	; save index
	push dph	; save dptr
	push dpl	;
	mov dptr, #crc16_tablo	; low part of table address
	movc a, @a+dptr	; get low byte
	xrl a, crc_hi	;
	mov crc_lo, a	; save of low result
	mov dptr, #crc16_tabhi	; high part of table address
	mov a, tmp	; index
	movc a, @a+dptr	;
	mov crc_hi, a	; save high result
	pop dpl	; restore pointer
	pop dph	;
	ret	; all done with calculation
crc16_tablo:
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
	db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
crc16_tabhi:
	db 000h, 0c0h, 0c1h, 001h, 0c3h, 003h, 002h, 0c2h
	db 0c6h, 006h, 007h, 0c7h, 005h, 0c5h, 0c4h, 004h
	db 0cch, 00ch, 00dh, 0cdh, 00fh, 0cfh, 0ceh, 00eh
	db 00ah, 0cah, 0cbh, 00bh, 0c9h, 009h, 008h, 0c8h
	db 0d8h, 018h, 019h, 0d9h, 01bh, 0dbh, 0dah, 01ah
	db 01eh, 0deh, 0dfh, 01fh, 0ddh, 01dh, 01ch, 0dch
	db 014h, 0d4h, 0d5h, 015h, 0d7h, 017h, 016h, 0d6h
	db 0d2h, 012h, 013h, 0d3h, 011h, 0d1h, 0d0h, 010h
	db 0f0h, 030h, 031h, 0f1h, 033h, 0f3h, 0f2h, 032h
	db 036h, 0f6h, 0f7h, 037h, 0f5h, 035h, 034h, 0f4h
	db 03ch, 0fch, 0fdh, 03dh, 0ffh, 03fh, 03eh, 0feh
	db 0fah, 03ah, 03bh, 0fbh, 039h, 0f9h, 0f8h, 038h
	db 028h, 0e8h, 0e9h, 029h, 0ebh, 02bh, 02ah, 0eah
	db 0eeh, 02eh, 02fh, 0efh, 02dh, 0edh, 0ech, 02ch
	db 0e4h, 024h, 025h, 0e5h, 027h, 0e7h, 0e6h, 026h
	db 022h, 0e2h, 0e3h, 023h, 0e1h, 021h, 020h, 0e0h
	db 0a0h, 060h, 061h, 0a1h, 063h, 0a3h, 0a2h, 062h
	db 066h, 0a6h, 0a7h, 067h, 0a5h, 065h, 064h, 0a4h
	db 06ch, 0ach, 0adh, 06dh, 0afh, 06fh, 06eh, 0aeh
	db 0aah, 06ah, 06bh, 0abh, 069h, 0a9h, 0a8h, 068h
	db 078h, 0b8h, 0b9h, 079h, 0bbh, 07bh, 07ah, 0bah
	db 0beh, 07eh, 07fh, 0bfh, 07dh, 0bdh, 0bch, 07ch
	db 0b4h, 074h, 075h, 0b5h, 077h, 0b7h, 0b6h, 076h
	db 072h, 0b2h, 0b3h, 073h, 0b1h, 071h, 070h, 0b0h
	db 050h, 090h, 091h, 051h, 093h, 053h, 052h, 092h
	db 096h, 056h, 057h, 097h, 055h, 095h, 094h, 054h
	db 09ch, 05ch, 05dh, 09dh, 05fh, 09fh, 09eh, 05eh
	db 05ah, 09ah, 09bh, 05bh, 099h, 059h, 058h, 098h
	db 088h, 048h, 049h, 089h, 04bh, 08bh, 08ah, 04ah
	db 04eh, 08eh, 08fh, 04fh, 08dh, 04dh, 04ch, 08ch
	db 044h, 084h, 085h, 045h, 087h, 047h, 046h, 086h
	db 082h, 042h, 043h, 083h, 041h, 081h, 080h, 040h

例6. CRC-16の高速計算用のアセンブリ言語の手順

lo equ 40h ; low byte of CRC
hi equ 41h ; high byte of CRC



crc16:
	push acc	; save the accumulator.
	xrl a, lo
	mov lo, hi	; move the high byte of the CRC.
	mov hi, a	; save data xor low(crc) for later
	mov c, p
	jnc crc0
	xrl lo, #01h	; add the parity to CRC bit 0
crc0:
	rrc a	; get the low bit in c
	jnc crc1
	xrl lo, #40h	; need to fix bit 6 of the result
crc1:
	mov c, acc.7
	xrl a, hi	; compute the results for other bits.
	rrc a	; shift them into place
	mov hi, a	; and save them
	jnc crc2
	xrl lo, #80h	; now clean up bit 7
crc2:
	pop acc	; restore everything and return
	ret

詳細画像