Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Контрольная сумма CRC
Форум разработчиков электроники ELECTRONIX.ru > Сайт и форум > В помощь начинающему > Программирование
zombi
Ув. форумчане, посоветуйте какой нибудь желательно не сложный но надежный и быстрый алгоритм рассчета CRC блока RAM.
Очень важна скорость расчета.
Размер блока может быть от 0.1 до 32 Кб.
Сейчас я планирую просто просуммировать весь блок ка 4-х байтные числа, в результате буду иметь КС 4 байта.
Но боюсь что такой метод не очень надежен.
Читал про алгоритмы типа MD5... др. прикинул сколько кода понадобится для его реализации на асме авра и понял что время расчета будет очень большим, а мне нужно чем побыстрее.
Nickolya_K
Application Note 27 от Dallas там есть расчет CRC-16
две таблицы по 256 байт и программа для расчета
_Pasha
Цитата(zombi @ Feb 2 2009, 19:44) *
Очень важна скорость расчета.

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

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


http://www.eagleairaust.com.au/code/crc16.htm - гугл, простенько и со вкусом smile.gif
zombi
Цитата(Nickolya_K @ Feb 2 2009, 20:23) *
Application Note 27 от Dallas там есть расчет CRC-16
две таблицы по 256 байт и программа для расчета


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

Цитата(_Pasha @ Feb 2 2009, 21:09) *
1. Побыстрей - это сколько (в тактах, хоть примерно?)

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


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


Код
// 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
Цитата(zombi @ Feb 2 2009, 21:33) *
Помогите разжевать вот эту запись плиз :
crc = (unsigned char)(crc >> 8) | (crc << 8);

боюсь ошибиться, но по-моему это обмен байт в слове, т. е. берем слово (16 бит) crc и старший байт ставим на место младшего, а младший соответственно на место старшего
zombi
Цитата(smac @ Feb 2 2009, 21:56) *
боюсь ошибиться, но по-моему это обмен байт в слове, т. е. берем слово (16 бит) crc и старший байт ставим на место младшего, а младший соответственно на место старшего

Мне тоже кажется что первая строчка это просто обмен местами старшего и младшего байта.
Но следующая строка :
crc ^= ser_data;
Это просто присвоение?
Если да, то нафига крутить вертеть в первой строке?

А что означает "^" перед знаком равенства?
demiurg_spb
Цитата(zombi @ Feb 2 2009, 22:10) *
crc ^= ser_data;
Это просто присвоение?
Если да, то нафига крутить вертеть в первой строке?
А что означает "^" перед знаком равенства?
crc ^= ser_data;
означает:
crc = crc ^ ser_data;
aaarrr
Цитата(demiurg_spb @ Feb 2 2009, 23:29) *
crc ^= ser_data;
означает:
crc = crc ^ ser_data;

Что в свою очередь означает: crc = crc :xor: ser_data
zombi
Цитата(aaarrr @ Feb 3 2009, 00:33) *
Что в свою очередь означает: crc = crc :xor: ser_data

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

Ув. программеры подскажите правильно ли я конвертировал этот код с си:
Код
    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;

Просто паскаль ближе мне для понимания.
А затем уже и на асме повторим.
demiurg_spb
Кстати, если используете avr-gcc (WinAVR), то уже всё написано за нас "include/util/crc16.h"
Baser
Цитата(zombi @ Feb 2 2009, 20:33) *
Но не силен я в СИ !
...
Помогите разжевать вот эту запись плиз...

Вот вам из моего старинного проекта, на асме.
На 100% не уверен, но на 98% cool.gif этот код дает то же значение 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)


CODE
#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
Исходник на СИ :
CODE
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;
};

Переписал на Паскале
CODE
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
Код
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
Цитата(zombi @ Feb 2 2009, 19:44) *
Ув. форумчане, посоветуйте какой нибудь желательно не сложный но надежный и быстрый алгоритм рассчета CRC блока RAM.
Очень важна скорость расчета.
Размер блока может быть от 0.1 до 32 Кб.
Сейчас я планирую просто просуммировать весь блок ка 4-х байтные числа, в результате буду иметь КС 4 байта.
Но боюсь что такой метод не очень надежен.
Читал про алгоритмы типа MD5... др. прикинул сколько кода понадобится для его реализации на асме авра и понял что время расчета будет очень большим, а мне нужно чем побыстрее.

Может поможет..
XVR
Посмотрите на Коды Флетчера. Очень быстрые и не требуют таблиц для подсчета
zombi
Спасибо Всем!

Но меня очень интересует Ваше мнение на мой вопрос в сообщении #12
XVR
Цитата(zombi @ Feb 3 2009, 13:41) *
Спасибо Всем!

Но меня очень интересует Ваше мнение на мой вопрос в сообщении #12

Все правильно, только одно но - массив crc_table обычно вычисляют заранее и вбивают в программу в виде констант
zombi
Цитата(XVR @ Feb 4 2009, 11:43) *
Все правильно, только одно но - массив crc_table обычно вычисляют заранее и вбивают в программу в виде констант

Спасибо XVR за проверку.
Понятно что таблицу можно и заранее сформировать.
Меня интересовало правильно ли я алгоритм формирования таблицы и рассчета срс на паскале повторил.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.