. Но есть ещё медленная релизация алгоритма для 32бит полиномиальная, встречалась мне для crc16 и crc8? н о для crc32 так нигде и не нашол. Подскажите если ктото сталкивался ?
С ув.
Полная версия этой страницы: CRC32 для 8бит
Столкнулся с проблемой реализации CRC32 функции для контроллера на С. В сети множество исходников но они все используют так сказать быстрый расчет, обычно генерирую динамическую таблицу в озу 255 Long значений ? 1kb озу сразу седает, есть ещё вариант со статической таблицей промежуточных полиномов, но от этого тоже легче седается 1kb памяти прграммы . Но есть ещё медленная релизация алгоритма для 32бит полиномиальная, встречалась мне для crc16 и crc8? н о для crc32 так нигде и не нашол.
Подскажите если ктото сталкивался ?
С ув.
. Но есть ещё медленная релизация алгоритма для 32бит полиномиальная, встречалась мне для crc16 и crc8? н о для crc32 так нигде и не нашол. Подскажите если ктото сталкивался ?
С ув.
www.pavel.hut1.ru
1-я ссылка по гуглю (алгоритм CRC32)
извиняюсь, по яндексу
1-я ссылка по гуглю (алгоритм CRC32)
извиняюсь, по яндексу
Если памяти жалко, то можно работать с двумя таблицами для полубайтов. Займут 128 байт.
"Медленная" реализация для CRC32 ничем не отличается от CRC16, кроме разрядности.
"Медленная" реализация для CRC32 ничем не отличается от CRC16, кроме разрядности.
Цитата(aaarrr @ Apr 4 2008, 15:48) 
"Медленная" реализация для CRC32 ничем не отличается от CRC16, кроме разрядности.
... и полинома
Цитата(west329_ @ Apr 4 2008, 15:37)
Подскажите если ктото сталкивался ?
Насколько я понимаю в CRC, любой "медленный" расчет строится по одному из двух алгоритмов:Код
uintX_t CRC1(uintX_t crc, uint8_t byte)
{
crc ^= byte;
uint_fast8_t i = 8;
do
{
if (crc & (1 << 0)) { crc >>= 1; crc ^= CRC_POLYNOME; }
else crc >>= 1;
}
while(--i);
return crc;
}
uintX_t CRC2(uintX_t crc, uint8_t byte)
{
crc ^= (uintX_t)byte << N;
uint_fast8_t i = 8;
do
{
if (crc & (1 << K)) { crc <<= 1; crc ^= CRC_POLYNOME; }
else crc <<= 1;
}
while(--i);
return crc;
}
// N = 0 для CRC8, 8 для CRC16, 24 для CRC32
// K = 7 для CRC8, 15 для CRC16, 31 для CRC32
Где uintX_t - соответственно uint8_t, uint16_t или uint32_t. Как нетрудно увидеть, они отличаются только направлением сдвига и вытекающим из него анализом либо крайнего правого либо крайнего левого бита и начальным XOR либо с крайним правым либо с крайним левым байтом. Зная полином, остается только выбрать нужный алгоритм.
{
crc ^= byte;
uint_fast8_t i = 8;
do
{
if (crc & (1 << 0)) { crc >>= 1; crc ^= CRC_POLYNOME; }
else crc >>= 1;
}
while(--i);
return crc;
}
uintX_t CRC2(uintX_t crc, uint8_t byte)
{
crc ^= (uintX_t)byte << N;
uint_fast8_t i = 8;
do
{
if (crc & (1 << K)) { crc <<= 1; crc ^= CRC_POLYNOME; }
else crc <<= 1;
}
while(--i);
return crc;
}
// N = 0 для CRC8, 8 для CRC16, 24 для CRC32
// K = 7 для CRC8, 15 для CRC16, 31 для CRC32
Вот один из примеров медленного бщета crc правд для 16
/*------------------------------------------------------------------------------
CRC16SIZE.C
Расчёт CRC-16 с оптимизацией по длине
------------------------------------------------------------------------------*/
typedef unsigned char uchar;
typedef signed char schar;
typedef unsigned int uint;
typedef signed int sint;
uint wCRC;
void InitCRC16(void)
{
wCRC = 0xFFFF;
}
void CalcCRC16(uchar bT)
{
uchar i;
wCRC ^= bT;
for (i=0; i<8; i++)
{
wCRC >>= 1;
if (CY == 1) wCRC ^= 0xA001;
}
}
void MakeCRC16(uchar *pbData, uint wSize)
{
InitCRC();
while (wSize-- > 0) CalcCRC( *(pbData++) );
}
возможно ли его переписать для crc32? полином для 32 бит 0х04C11DB7
Насчет поисков я искал и гуглом и яндексом и нашол не мало реализаций, часть из которых даже работала но не так как хотелосьбы.
P/S/ пишу на форум когда уже выхода нету
to Сергей Борщ. Благодарю , попробую прописать.
/*------------------------------------------------------------------------------
CRC16SIZE.C
Расчёт CRC-16 с оптимизацией по длине
------------------------------------------------------------------------------*/
typedef unsigned char uchar;
typedef signed char schar;
typedef unsigned int uint;
typedef signed int sint;
uint wCRC;
void InitCRC16(void)
{
wCRC = 0xFFFF;
}
void CalcCRC16(uchar bT)
{
uchar i;
wCRC ^= bT;
for (i=0; i<8; i++)
{
wCRC >>= 1;
if (CY == 1) wCRC ^= 0xA001;
}
}
void MakeCRC16(uchar *pbData, uint wSize)
{
InitCRC();
while (wSize-- > 0) CalcCRC( *(pbData++) );
}
возможно ли его переписать для crc32? полином для 32 бит 0х04C11DB7
Насчет поисков я искал и гуглом и яндексом и нашол не мало реализаций, часть из которых даже работала но не так как хотелосьбы.
P/S/ пишу на форум когда уже выхода нету
to Сергей Борщ. Благодарю , попробую прописать.
Код
ulong wCRC;
void InitCRC32(void)
{
wCRC = 0xFFFFFFFF;
}
void CalcCRC32(uchar bT)
{
uchar i;
wCRC ^= bT;
for (i=0; i<8; i++)
{
wCRC >>= 1;
if (CY == 1) wCRC ^= POLY;
}
}
где POLY - ваш 0х04C11DB7
я вот так думаю...
Встретил вот такое:
Код
unsigned long CalcCRC32(unsigned long CRC, unsigned char Symbol)
{
unsigned long temp;
CRC ^= 0xFFFFFFFF ^ Symbol;
for(int k = 8; k--;)
{
temp = -(CRC & 1), CRC >>= 1, CRC ^= 0xEDB88320ul & temp;
}
CRC ^= 0xFFFFFFFF;
return CRC;
}
и на паскале
function calccr32(crc:longword;symbol:integer):longword;
var k:integer;
temp:longword;
begin
crc:= crc xor ($FFFFFFFF xor symbol);
for k:=0 to 7 do
begin
temp:= -(CRC and 1);
crc:=crc shr 1;
crc:=crc xor 3988292384 and temp;
end;
crc:=crc xor $FFFFFFFF;
calccr32:=crc;
end;
{
unsigned long temp;
CRC ^= 0xFFFFFFFF ^ Symbol;
for(int k = 8; k--;)
{
temp = -(CRC & 1), CRC >>= 1, CRC ^= 0xEDB88320ul & temp;
}
CRC ^= 0xFFFFFFFF;
return CRC;
}
и на паскале
function calccr32(crc:longword;symbol:integer):longword;
var k:integer;
temp:longword;
begin
crc:= crc xor ($FFFFFFFF xor symbol);
for k:=0 to 7 do
begin
temp:= -(CRC and 1);
crc:=crc shr 1;
crc:=crc xor 3988292384 and temp;
end;
crc:=crc xor $FFFFFFFF;
calccr32:=crc;
end;
Посмотрите в википедии
Код
#define CRC_LENGTH 32
#define POLY 0xblah-blah-blah
// коэффициенты CRC32_yy = crc32(yy, 0), где yy = {2^0, 2^1, ..., 2^(CRC_LENGTH-1)}
// считаются предварительно для требуемого полинома и CRC32_init = 0 через сдвиги
// (или берутся готовые :))
const uint32 CRC32_Table[CRC_LENGTH] = {CRC32_0, ..., CRC32_31};
uint32 crc32(uint32 x, uint32 CRC32_init)
{
uint i;
uint32 bitmask, y, CRC32 = 0;
y = x ^ CRC32_init;
for(i = 0, mask =1; i < CRC_LENGTH; i++, bitmask <<= 1)
if(y & bitmask) CRC32 ^= CRC32_Table[i];
return CRC32;
}
// или для экономии памяти
uint32 crc32(uint32 x, uint32 CRC32)
{
uint i;
uint32 bitmask;
x ^= CRC32; CRC32 = 0;
for(i = 0, mask =1; i < CRC_LENGTH; i++, bitmask <<= 1)
if(x & bitmask) CRC32 ^= CRC32_Table[i];
return CRC32;
}
// или для еще большей экономии памяти на 8-битниках
// выровнять таблицу по 0bx0000000, uint8 bitmask, i лишний и т.д.:)
#define POLY 0xblah-blah-blah
// коэффициенты CRC32_yy = crc32(yy, 0), где yy = {2^0, 2^1, ..., 2^(CRC_LENGTH-1)}
// считаются предварительно для требуемого полинома и CRC32_init = 0 через сдвиги
// (или берутся готовые :))
const uint32 CRC32_Table[CRC_LENGTH] = {CRC32_0, ..., CRC32_31};
uint32 crc32(uint32 x, uint32 CRC32_init)
{
uint i;
uint32 bitmask, y, CRC32 = 0;
y = x ^ CRC32_init;
for(i = 0, mask =1; i < CRC_LENGTH; i++, bitmask <<= 1)
if(y & bitmask) CRC32 ^= CRC32_Table[i];
return CRC32;
}
// или для экономии памяти
uint32 crc32(uint32 x, uint32 CRC32)
{
uint i;
uint32 bitmask;
x ^= CRC32; CRC32 = 0;
for(i = 0, mask =1; i < CRC_LENGTH; i++, bitmask <<= 1)
if(x & bitmask) CRC32 ^= CRC32_Table[i];
return CRC32;
}
// или для еще большей экономии памяти на 8-битниках
// выровнять таблицу по 0bx0000000, uint8 bitmask, i лишний и т.д.:)
Для CRC8 (цикл стОит развернуть), CRC16, CRCxx, ... аналогично.
Если время совсем не напрягает, то через сдвиги, как уже предлагали.
Всем учасника выражаю благодарность за ответы. будем компилировать, возникнут вопросы выложу
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.