CRC32 для 8бит, помогите найти медленные исходники Опции

[west329_]

Столкнулся с проблемой реализации CRC32 функции для контроллера на С. В сети множество исходников но они все используют так сказать быстрый расчет, обычно генерирую динамическую таблицу в озу 255 Long значений ? 1kb озу сразу седает, есть ещё вариант со статической таблицей промежуточных полиномов, но от этого тоже легче седается 1kb памяти прграммы . Но есть ещё медленная релизация алгоритма для 32бит полиномиальная, встречалась мне для crc16 и crc8? н о для crc32 так нигде и не нашол.

Подскажите если ктото сталкивался ?
С ув.

[MrYuran]

www.pavel.hut1.ru
1-я ссылка по гуглю (алгоритм CRC32)

извиняюсь, по яндексу

Сообщение отредактировал MrYuran - Apr 4 2008, 12:51

[aaarrr]

Если памяти жалко, то можно работать с двумя таблицами для полубайтов. Займут 128 байт.

"Медленная" реализация для CRC32 ничем не отличается от CRC16, кроме разрядности.

[MrYuran]

"Медленная" реализация для CRC32 ничем не отличается от CRC16, кроме разрядности.

... и полинома

[Сергей Борщ]

Подскажите если ктото сталкивался ?

Насколько я понимаю в 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 либо с крайним правым либо с крайним левым байтом. Зная полином, остается только выбрать нужный алгоритм.

[west329_]

Вот один из примеров медленного бщета 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 Сергей Борщ. Благодарю , попробую прописать.

Сообщение отредактировал west329_ - Apr 4 2008, 13:02

[MrYuran]

Код

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

я вот так думаю...

[aleksey_g]

Встретил вот такое:

Код

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;

[sysel]

Посмотрите в википедии

[xemul]

Код

#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 лишний и т.д.:)

Для CRC8 (цикл стОит развернуть), CRC16, CRCxx, ... аналогично.
Если время совсем не напрягает, то через сдвиги, как уже предлагали.

[west329_]

Всем учасника выражаю благодарность за ответы. будем компилировать, возникнут вопросы выложу