[zombi 0]

Ув. форумчане, посоветуйте какой нибудь желательно не сложный но надежный и быстрый алгоритм рассчета CRC блока RAM.

Очень важна скорость расчета.

Размер блока может быть от 0.1 до 32 Кб.

Сейчас я планирую просто просуммировать весь блок ка 4-х байтные числа, в результате буду иметь КС 4 байта.

Но боюсь что такой метод не очень надежен.

Читал про алгоритмы типа MD5... др. прикинул сколько кода понадобится для его реализации на асме авра и понял что время расчета будет очень большим, а мне нужно чем побыстрее.

[Nickolya_K 0]

Application Note 27 от Dallas там есть расчет CRC-16

две таблицы по 256 байт и программа для расчета

[_Pasha 0]

Очень важна скорость расчета.

1. Побыстрей - это сколько (в тактах, хоть примерно?)

 

2. Контрольную сумму городить не надо - действительно мучения.

 

 

http://www.eagleairaust.com.au/code/crc16.htm - гугл, простенько и со вкусом :)

[zombi 0]

Application Note 27 от Dallas там есть расчет CRC-16

две таблицы по 256 байт и программа для расчета

 

Спасибо Nickolya_K.

А дай пожалуйста ссылочку на Application Note 27 от Dallas!

 

1. Побыстрей - это сколько (в тактах, хоть примерно?)

 

2. Контрольную сумму городить не надо - действительно мучения.

 

 

http://www.eagleairaust.com.au/code/crc16.htm - гугл, простенько и со вкусом :)

 

// Update the CRC for transmitted and received data using
// the CCITT 16bit algorithm (X^16 + X^12 + X^5 + 1).

    unsigned char ser_data;
    static unsigned int crc;

    crc  = (unsigned char)(crc >> 8) | (crc << 8);
    crc ^= ser_data;
    crc ^= (unsigned char)(crc & 0xff) >> 4;
    crc ^= (crc << 8) << 4;
    crc ^= ((crc & 0xff) << 4) << 1;

 

Спасибо Pasha.

Но не силен я в СИ !

Я тока понял что на входе "unsigned char"-байт на выходе "unsigned int"-слово тобиш CRC16, или нет!?

Помогите разжевать вот эту запись плиз :

crc = (unsigned char)(crc >> 8) | (crc << 8);

[smac 0]

Помогите разжевать вот эту запись плиз :

crc = (unsigned char)(crc >> 8) | (crc << 8);

боюсь ошибиться, но по-моему это обмен байт в слове, т. е. берем слово (16 бит) crc и старший байт ставим на место младшего, а младший соответственно на место старшего

[zombi 0]

боюсь ошибиться, но по-моему это обмен байт в слове, т. е. берем слово (16 бит) crc и старший байт ставим на место младшего, а младший соответственно на место старшего

Мне тоже кажется что первая строчка это просто обмен местами старшего и младшего байта.

Но следующая строка :

crc ^= ser_data;

Это просто присвоение?

Если да, то нафига крутить вертеть в первой строке?

 

А что означает "^" перед знаком равенства?

Изменено 2 февраля, 2009 пользователем zombi

[demiurg_spb 0]

crc ^= ser_data;

Это просто присвоение?

Если да, то нафига крутить вертеть в первой строке?

А что означает "^" перед знаком равенства?

crc ^= ser_data;

означает:

crc = crc ^ ser_data;

[aaarrr 63]

crc ^= ser_data;

означает:

crc = crc ^ ser_data;

Что в свою очередь означает: crc = crc :xor: ser_data

[zombi 0]

Что в свою очередь означает: crc = crc :xor: ser_data

Спасибо aaarrr, теперь все понятно :yeah:

 

Ув. программеры подскажите правильно ли я конвертировал этот код с си:

    unsigned char ser_data;
    static unsigned int crc;

    crc  = (unsigned char)(crc >> 8) | (crc << 8);
    crc ^= ser_data;
    crc ^= (unsigned char)(crc & 0xff) >> 4;
    crc ^= (crc << 8) << 4;
    crc ^= ((crc & 0xff) << 4) << 1;

на паскаль

var ser_data:byte;
    crc:word;

begin
  crc:=(crc shr 8) or (crc shl 8);
  crc:=crc xor ser_data;
  crc:=crc xor ((crc and $00f0) shr 4);
  crc:=crc xor (crc shl 12);
  crc:=crc xor ((crc and $00ff) shl 5);
end;

Просто паскаль ближе мне для понимания.

А затем уже и на асме повторим.

Изменено 2 февраля, 2009 пользователем zombi

[demiurg_spb 0]

Кстати, если используете avr-gcc (WinAVR), то уже всё написано за нас "include/util/crc16.h"

[Baser 5]

Но не силен я в СИ !

...

Помогите разжевать вот эту запись плиз...

Вот вам из моего старинного проекта, на асме.

На 100% не уверен, но на 98% B) этот код дает то же значение CRC, что и вышеприведенный на Си

Для проверки:

01 05 FF 11 22 33 00 00 82 13  (CRC = 82 13)
FF 04 11 22 33 00 00 4B 08     (CRC = 4b 08)

 

	#include	"io8515.h"
RSEG	CHECKSUM(1)
RSEG	DEBUG(1)
;===============================================================;
;	   Calculate Flash code XModem CRC-CCITT				  ;
;===============================================================;	
;	EXTERN  ByteCRC
CalcFlashCRC:
	clr	 Z0
	clr	 Z1
	clr	 r16
	clr	 r17

cal1:   lpm					; Calculate CRC for next byte
	mov	 r20,r0
	rcall   ByteCRC
	adiw	Z0,0x01
	cpi	 Z0,low(SFB(CHECKSUM))
	ldi	 r20,high(SFB(CHECKSUM))		
	cpc	 Z1,r20
	brlo	cal1				

cal2:   rjmp	cal2		   ; Flash CRC = DW  0x(r16:r17)

;---------------------------------------------------------------;
;	   Calculate one byte of XModem CRC-CCITT				 ;
; Function: int ByteCRC (int XmCRC,char Byte);				 ;				   
; Input:	r17:r16 = Old value CRC-CCITT					  ;
;		   r20	 = input byte							   ;
; Output:   r17:r16 = New value CRC-CCITT					  ;
;---------------------------------------------------------------;
;	PUBLIC  ByteCRC
ByteCRC:eor	 r17,r20
	ldi	 r21,8

bci1:   lsl	 r16
	rol	 r17
	brcc	bci2
	ldi	 r20,0x10
	eor	 r17,r20
	ldi	 r20,0x21
	eor	 r16,r20
bci2:   dec	 r21
	brne	bci1		
	ret
;===============================================================;
END

[zombi 0]

Исходник на СИ :

unsigned long Crc32(unsigned char *buf, unsigned long len)
{
unsigned long crc_table[256];
unsigned long crc;

for (int i = 0; i < 256; i++)
{
	crc = i;
	for (int j = 0; j < 8; j++)
		crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;

	crc_table[i] = crc;
};

crc = 0xFFFFFFFFUL;

while (len--) 
	crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);

return crc ^ 0xFFFFFFFFUL;
};

Переписал на Паскале

var data:array[0..$ffff] of byte;

{
подготовка массива data[]
}


{ Считает crc в массиве data[] от start до endd }
procedure CRC32(start,endd:word):dword;
var
 crc_table:array [0..255] of dword;
 crc:dword;
 i,j:word;
begin
 for i:=0 to 255 do begin
crc:=i;
for j:=0 to 7 do if (crc and 1)=1 then crc:=((crc shr 1) xor $EDB88320)
								  else crc:=crc shr 1;
crc_table[i]:=crc;
 end;
 crc:=$FFFFFFFF;
 for i:=start to endd do begin
crc:=(crc_table[(crc xor data[i]) and $ff]) xor (crc shr 8);
 end;
 CRC32:=crc xor $FFFFFFFF;
end;

 

Поправьте меня если ошибся.

[Harbour 0]

u16 r5_sum(unsigned char *b, u32 len)
{
register u32 i;
register u16 csum = 0;
for(i = 0; i < len; i++) {
   csum += (b[i] << 4);
   csum += (b[i] >> 4);
   csum *= 11;
}
  return csum;
}

 

Выдрал в свое время из какой-то файловой системы вот такой вот сердитый csum - нравится скорость.

[tolik1 0]

Ув. форумчане, посоветуйте какой нибудь желательно не сложный но надежный и быстрый алгоритм рассчета CRC блока RAM.

Очень важна скорость расчета.

Размер блока может быть от 0.1 до 32 Кб.

Сейчас я планирую просто просуммировать весь блок ка 4-х байтные числа, в результате буду иметь КС 4 байта.

Но боюсь что такой метод не очень надежен.

Читал про алгоритмы типа MD5... др. прикинул сколько кода понадобится для его реализации на асме авра и понял что время расчета будет очень большим, а мне нужно чем побыстрее.

Может поможет..

crcguide.pdf

crcrevrs.pdf

[Nickolya_K 0]

http://www.microshadow.com/files/files8051/app27.pdf