CRC32, uint32_t Опции

[toweroff]

Добрый день!

Нужна софтовая реализация. Не проблема, гугел их находит не задумываясь

Но из того, что я находил, даже табличная реализация считает по 1 байту

А хотелось бы найти подсчет сразу по 32 бита, не по 8. Благо мой массив данных всегда кратен 4 байтам, а аппаратного CRC на борту контроллера нет
По идее, это же должно увеличить производительность?

UPD
что-то нашел от Интела

черт... там используются 4 таблицы из uint32_t[256]
места в оперативке нет, во флеше тоже... придется побайтно считать

[VAI]

Вот 2 функции, одна "железная" для STM32, а вторая программная, из википедии. Результат одинаков. Единственное условие - размер массива в байтах должен быть кратен 4-м.
Проверял и сейчас использую первую в "железке" на STM32F205, а вторую в компе.

Код

/* --- crc32() -------------------------------------------------------------------------------------------- **
*  Контрольная сумма crc32 с использованием "железного" "Блока расчета CRC" STM32F2xx.
*  Poly  : 0x04c11db7    x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
*  Init  : 0xffffffff
*  Revert: true
*  XorOut: 0xffffffff
*  Check : 0x5d34eb96 ("123456789012" или { 0x34333231, 0x38373635, 0x32313039 })
*  - обнаружение одинарных, двойных, пакетных и всех нечетных ошибок
*    uint32_t arr[]   - указатель на массив 32-х битных слов
*    unsigned int num - размер массива в словах!!!
*  Возвращает
*    unsigned long crc32 массива
*  Результат совпадает со стандартной функцией crc32 при условии кратности размера массива 4-м байтам (32-м битам)
* -------------------------------------------------------------------------------------------------------- */
unsigned long crc32( uint32_t *arr, uint32_t num )
{
  CRC->CR = CRC_CR_RESET;                                         // Reset CRC generator
  while ( num-- )
    CRC->DR = __rbit( *arr++ );
  return( __rbit( CRC->DR ) ^ 0xffffffffUL );
}

CODE

/* --- crc32() -------------------------------------------------------------------------------------------- **
* Контрольная сумма crc32
* Poly : 0x04c11db7 x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
* Init : 0xffffffff
* Revert: true
* XorOut: 0xffffffff
* Check : 0xcbf43926 ("123456789")
* MaxLen: 268 435 455 байт (2 147 483 647 бит) - обнаружение одинарных, двойных, пакетных и всех нечетных ошибок
* uint32_t arr[] - указатель на массив 32-х битных слов
* unsigned int num - размер массива в словах!!!
* Возвращает
* unsigned long crc32 буфера
* -------------------------------------------------------------------------------------------------------- */
unsigned long crc32( uint32_t *arr, uint32_t num )
{
static const uint32_t crc32table[256] =
{ 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
};

unsigned long crc = 0xffffffff;
BYTE *buf = (BYTE *)arr;

num *= 4; // Для совместимости с "железной" функцией crc32
while ( num-- )
crc = ( crc >> 8 ) ^ crc32table[( crc ^ *buf++ ) & 0xff];
return( crc ^ 0xffffffffUL );
}

[toweroff]

Спасибо!

У меня не STM и не старшие кортексы NXP, так что про аппаратную можно забыть
А вторая да, ее пока и использую. Только таблицу генерю в RAM, во флеше места нет
Эта реализация обрабатывает массив данных побайтно, я-то хотел обработку сразу по uint32_t, но, видать, в моем, жестко ужатом ресурсами случае, - не судьба
Это бутлоадер, который нужно уложить в 4К, там еще шифрование AES и код располагается в RAM, которой всего 8К
Сейчас погоняю, посмотрю на скорость выполнения, возможно что-то получится убрать из оперативки и оставить выполнение из флеши, тогда появится возможность отдать половину под таблицы

[blackfin]

Эта реализация обрабатывает массив данных побайтно, я-то хотел обработку сразу по uint32_t, но, видать, в моем, жестко ужатом ресурсами случае, - не судьба

На заметку: Polynomial rotation accelerates CRC calculations.
Там, правда, примеры кода для PIC'а, но, возможно, пригодится как источник идей..

[toweroff]

Там, правда, примеры кода для PIC'а

вообще-то, для 8051

кстати, может я сам себе придумал геморрой проблему?
размер блока 32К, сколько там достаточно бит в CRC? может и в 16 уложусь, тогда все вопросы сами собой пропадут

[ViKo]

А вы перешлите второй раз прошивку для верификации. Никакая контрольная сумма не даст полной гарантии.

[toweroff]

А вы перешлите второй раз прошивку для верификации. Никакая контрольная сумма не даст полной гарантии.

да куда ж я ее там дену-то? ее один-то раз только кусками, да сразу во флеш

я в самом хвосте прошивки "руками" размещаю CRC и перед стартом считаю всю область, отведенную под приложение. Ноль - значит все в порядке и перехожу туда по entry_point

[VAI]

А вы перешлите второй раз прошивку для верификации. Никакая контрольная сумма не даст полной гарантии.

Запись же делаете блоками. В бутлоадере функция записи блока номер N.
Принимаете структуру "номер блока" и сам блок, записываете, посылаете назад, читая из флэшь.
На том конце сравнивается и принимается решение опять этот блок пульнуть или следующий...

[adnega]

Типичный кусок кода для бестабличного вычисления:

Код

for (j = 0; j < 8; j++) ...;

Не вижу причин для ускорения даже если заменить 8 на 32. Расчет-то все равно побитный.
Считайте в лоб, без таблиц - минимум по расходу памяти.
Подсчет можно вести во время получения порции данных, а не когда весь образ будет готов - вряд ли канал обновления сравниться со скоростью вычисления CRC и записи во flash. Лучше вообще считать во время записи во flash. Финальная задержка порядка времени обработки одного блока.

[ViKo]

Кусками или целиком - какая разница? Сначала записали (блоками) всё, потом то же самое, только сравниваете с flash.
Это если вычислять CRC трудно.
Я буду делать примерно так. Но не потому, что CRC лень считать, а чтобы в любой терминальной программе послать прошивку в один конец, безответно.

[toweroff]

Запись же делаете блоками. В бутлоадере функция записи блока номер N.
Принимаете структуру "номер блока" и сам блок, записываете, посылаете назад, читая из флэшь.
На том конце сравнивается и принимается решение опять этот блок пульнуть или следующий...

в бутлоадер отдается шифрованный блок. Он расшифровывается и записывается. Предлагаете гнать назад расшифрованный блок?

[jcxz]

Типичный кусок кода для бестабличного вычисления:

Код

for (j = 0; j < 8; j++) ...;

Не вижу причин для ускорения даже если заменить 8 на 32. Расчет-то все равно побитный.

Кроме побитного и табличного есть и другие способы.
Например - табличный не по-байтный, а по-тетрадный: размер таблицы в 8 раз меньше, действий только чуть больше.
Также можно считать CRC за один проход для целого байта (без таблиц) по формуле. Но этот способ знаю только для CRC16.

кстати, может я сам себе придумал геморрой проблему?
размер блока 32К, сколько там достаточно бит в CRC? может и в 16 уложусь, тогда все вопросы сами собой пропадут

Неужто Ваш МК не может справиться с таким небольшим объёмом??
Я думал - Вы мегабайты считаете....
У нас бутлоадер тоже считает CRC32 (Cortex-M на 12МГц без PLL).
Таблично. CRC32. При каждом старте ПО. На глаз задержки старта не заметно. Даже PLL не стали включать.
Размер прошивки == почти 200кБ.

[toweroff]

У нас бутлоадер тоже считает CRC32 (Cortex-M на 12МГц без PLL).
Таблично. CRC32. При каждом старте ПО. На глаз задержки старта не заметно. Даже PLL не стали включать.
Размер прошивки == почти 200кБ.

ну вот и ответ
оставляю таблицу и не заморачиваюсь, да и кварц на 16МГц

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

Также можно считать CRC за один проход для целого байта (без таблиц) по формуле. Но этот способ знаю только для CRC16.

Я знаю для CCITT (полином 0x8408), XMODEM (полином 0x1021). Давайте меняться? В примере применения от первых scenix (виртуальная периферия IrDA) было вскользь упомянуто как они получили такую формулу для 0x8408, но тогда я эту методику не осилил, а сейчас то описание потерялось и не гуглится

Добавлено: нагуглил. Да, и тогда не понял, и сейчас не осиливаю.

[jcxz]

Я знаю для CCITT (полином 0x8408), XMODEM (полином 0x1021). Давайте меняться? В примере применения от первых scenix (виртуальная периферия IrDA) было вскользь упомянуто как они получили такую формулу для 0x8408, но тогда я эту методику не осилил, а сейчас то описание потерялось

Я как раз для 0x1021 и знаю только

Код

//Расчёт CRC16 полином == 0x1021
u32 CRC16(void const *buf, int len, u32 crc)
{
  u8 const *p = (u8 const *)buf;
  while (--len >= 0) {
    u32 c = crc << 16 >> 24 ^ *p++;
    c ^= c >> 4;
    crc = crc << 8 ^ c ^ c << 5 ^ c << 12;
  }
  return crc & 65535;
}

на вход crc - начальное значение (0 или ~0) или результат от CRC16() предыдущего региона в цепочке регионов

Вот-бы для CRC32 найти!

PS: Хотя нет - знаю ещё одну формулу для другого CRC16, но не знаю какой полином (данная CRC используется в наших устройствах работающих по нашему собственному протоколу).

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

Я как раз для 0x1021 и знаю только

Ну да, у меня такая же:

Код

void crc::ccitt::calculate(uint8_t byte)
{
    base Current_tmp = Current ^ byte;

    uint_fast8_t Tmp= (Current_tmp ^ (Current_tmp << 4)) & 0xff;
    Current = (Current_tmp >> 8) ^ (Tmp << 8) ^ ( Tmp << 3) ^ ( Tmp >> 4);
}

void crc::xmodem::calculate(uint8_t byte)
{
    base Current_tmp = Current;
    uint_fast8_t Tmp = ((Current_tmp >> 8) ^ byte) & 0xFF;
    Tmp ^= Tmp >> 4;
    Current = (Current_tmp << 8) ^ (Tmp << 12) ^ (Tmp << 5) ^ Tmp;
}

[SM]

Для CRC-32 такие конструкции категорически не выгодны, так как там полиномы имеют кол-во бит, установленных в 1, больше чем 8 - следовательно и сдвигов с ксорами будет по кол-ву бит, что не выгодно по сравнению с реализацией в лоб, с циклом на 8 условных ксоров с полиномом.

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

Для CRC-32 такие конструкции категорически не выгодны,

Существует куча других циклических контрольных сумм, 16- и 8-битных. Серега, ты можешь объяснить саму методику, как получаются такие формулы? В хозяйстве обязательно сгодится! Скажем, на примере полинома 0xA001 (modbus), обработка младшим битом вперед.

[SM]

обработка младшим битом вперед.

Это что значит? Новый бит данных задвигается со старшего разряда сдвигом вправо, или с младшего, сдвигом влево?

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

Это что значит? Новый бит данных задвигается со старшего разряда сдвигом вправо,

Да.

Потихоньку начал сам разбираться с примером из приложенного мной выше примера применения:

Код

// обсчет одного байта "в лоб":
void crc::ccitt:calculate(uint8_t byte)
{
    uint_fast8_t Counter = 8;
    uint_fast16_t Tmp = Current;
    Tmp ^= byte;
    do
    {
        if (Tmp & (1<<0))
        {
            Tmp >>= 1;
            Tmp ^= POLYNOME;
        }
        else
            Tmp >>= 1;
    }
    while(--Counter);
    Current = Tmp;
}

результат для байта с одним установленным битом:
/*
    0x01 -> 0x1189
    0x02 -> 0x2312
    0x04 -> 0x4624
    0x08 -> 0x8C48
    0x10 -> 0x1081
    0x20 -> 0x2102
    0x40 -> 0x4204
    0x80 -> 0x8408
// то же в двоичном виде:
0: 0000 0001 -> 0001 0001 1000 1001
1: 0000 0010 -> 0010 0011 0001 0010
2: 0000 0100 -> 0100 0110 0010 0100
3: 0000 1000 -> 1000 1100 0100 1000
4: 0001 0000 -> 0001 0000 1000 0001
5: 0010 0000 -> 0010 0001 0000 0010
6: 0100 0000 -> 0100 0010 0000 0100
7: 1000 0000 -> 1000 0100 0000 1000
// зависимость каждого бита результата от входных:
                ^^
y15 = x3 ^ x7 --+|
y14 = x2 ^ x6 ---+
y13 = x1 ^ x5
y12 = x0 ^ x4
y11 = x3
.....
*/

Пока с примером совпадает. В принципе уже можно написать такой вариант:

Код

тут была фигня

Каким образом заполнена таблица 7-1 в примере понятно. Осталось понять, как эти выражения для каждого бита свернуть в общую формулу.

[SM]

в общем, объясню на примере 0x8408:

1)
byte ^= crc; // XOR младшего байта с входными данными. С этого начинается любой CRC (это "скрытый" бит полинома, который младше младшего, реверс от X^16)
2)
byte ^= byte << 4; // XOR, обусловленный битом полинома 0x8408, для данных, которые выдвинутся за пределы 16 бит. 4 влево = номер бита 0x0008 (3) + 1
3)
crc = (byte << 8) | (crc >> 8); // сдвиг 8 раз вправо, и задвиг свежих битов, обеспечиваемых битом полинома 0x8408 (15 - 8 + 1 = влево на +8)
4)
crc ^= byte >> 4; // XOR, обусловленный битом 0x8408 для остатка данных, не выдвинутых за пределы 16 бит. 4 вправо = номер бита 0x0008 (3) - 8 + 1 = -4
5)
crc ^= byte << 3; // XOR, обусловленный битом 0x8408 (3 влево = номер бита 0x0400 (это 10) - 8 + 1)

Собственно, все.


UPD:
Вдогонку. Для 0xA001, подозреваю, что такое разложение на сдвиги и XORы невозможно, по причине слишком близкой обратной связи (в младшем бите регистра). То есть, для реализуемости такого подхода (для направления сдвига вправо), надо, чтобы в полиноме не было бит, установленных в 1, на позициях, меньших, чем половина ширины входного слова минус 1.

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

Такс. Я разобрался. 0x8408, сдвиг вправо. За время обработки одного байта у нас предыдущее значение CRC сдвинется на 8 бит вправо. При этим "выпавшие" вправо биты проXORятся с исходным байтом. Отсюда byte ^= CRC и CRC >>= 8. Получившийся byte ^ CRC даст после всех обратных связей некий результат f(byte ^ CRC), который будет проXORен с получившимся CRC >>= 8. Это нам дает X = byte ^ CRC и CRC = (CRC >>8) ^ f(X).
f(X) получается следующим образом:

Код

0: 0000 0001 -> 0001 0001 1000 1001
1: 0000 0010 -> 0010 0011 0001 0010
2: 0000 0100 -> 0100 0110 0010 0100
3: 0000 1000 -> 1000 1100 0100 1000
4: 0001 0000 -> 0001 0000 1000 0001
5: 0010 0000 -> 0010 0001 0000 0010
6: 0100 0000 -> 0100 0010 0000 0100
7: 1000 0000 -> 1000 0100 0000 1000
                yy
                11
                54
y15 = x3 ^ x7 --+|
y14 = x2 ^ x6 ---+
y13 = x1 ^ x5
y12 = x0 ^ x4
y11 =      x3
y10 =      x2 ^ x3 ^ x7
y9  =      x1 ^ x2 ^ x6
y8  =      x0 ^ x1 ^ x5
y7  =           x0 ^ x4
y6  =                x3
y5  =                x2
y4  =                x1
y3  =                x0 ^ x3 ^ x7
y2  =                     x2 ^ x6
y1  =                     x1 ^ x5
y0  =                     x0 ^ x4
      \-----/   \-----/   \-----/
      A << 8    A << 3    A >> 4
      
      A = (X ^ (X << 4)) & 0xFF
  f(x) = (A << 8) ^ (A << 3) ^ (A >> 4)

Итого, на выходе имеем:

Код

byte ^= CRC;
uint8_t Tmp = byte ^ (byte << 4);
CRC = (CRC >> 8) ^ (Tmp << 8) ^ (Tmp << 3) ^ (Tmp >> 4);

Сошлось.

Аналогичным образом ищем f(X) для полинома 0xA001. Получается уже не так красиво:

Код

0: 0000 0001 -> 1100 0000 1100 0001
1: 0000 0010 -> 1100 0001 1000 0001
2: 0000 0100 -> 1100 0011 0000 0001
3: 0000 1000 -> 1100 0110 0000 0000
4: 0001 0000 -> 1100 1100 0000 0001
5: 0010 0000 -> 1101 1000 0000 0001
6: 0100 0000 -> 1111 0000 0000 0001
7: 1000 0000 -> 1010 0000 0000 0001

y15 =           x7 ^ x6 ^ x5 ^ x4 ^ x3 ^ x2 ^ x1 ^ x0
y14 =      x7 ^ x6 ^ x5 ^ x4 ^ x3 ^ x2 ^ x1
y13 = x7 ^ x6
y12 = x6 ^ x5
y11 = x5 ^ x4
y10 = x4 ^ x3
y9  = x3 ^ x2
y8  = x2 ^ x1
y7  = x1 ^ x0
y6  = x0
y5  = 0
y4  = 0
y3  = 0
y2  = 0
y1  = 0
y0  =               x7 ^ x6 ^ x5 ^ x4 ^ x2 ^ x1 ^ x0

То есть технически реализуемо, но сдвигов будет больше.

[SM]

То есть технически реализуемо, но сдвигов будет больше.

Не реализуемо из-за единицы в A001. Эта единица дает близкую обратную связь (2^0 = 1) - таким образом такая схема реализуема, но только не для 8-битных входных данных, а лишь для двухбитных - а это никакой экономии не даст (для байта придется сделать 4 итерации). А вот в 8408 - младшая единица - 8 (2^3), что как раз разрешает такую реализацию для кусков данных до 8 бит включительно.

Не надо эту F(x) ИСКАТЬ! Она составляется просто из позиций единичных бит в полиноме. В первой части, до основного сдвига вправо, в XOR-ах в количествах сдвигов участвуют биты полинома от самого младшего и до последнего, перекрываемого по ширине входного слова, а во второй части, после сдвига - все биты полинома.

То есть, вот она, реализация для A001, но она не эффективна, из-за двухбитного ограничения, из-за этой самой A001

Код

static USHORT crc;
void update_CRC_A001_2bit(unsigned char byte)
{
   USHORT t;

   byte ^= crc;
   byte ^= byte << 1; // bit 0 of poly (0 + 1)
   byte &= 0x3;

   t = crc >> 2; // shift for -2 bits
   t ^= byte << 14; // bit 15 of poly (15 - 2 + 1)
   t ^= byte << 12; // bit 13 of poly (13 - 2 + 1)
   t ^= byte >> 1; // bit 0 of poly (0 - 2 +1)

   crc = t;

}

void update_CRC_A001(unsigned char byte)
{
  update_CRC_A001_2bit(byte);
  update_CRC_A001_2bit(byte>>2);
  update_CRC_A001_2bit(byte>>4);
  update_CRC_A001_2bit(byte>>6);
}

UPD:
Короче, имея на входе 0xFF, как его не ксорь со сдвигами, 0x55 не получишь... Вот поэтому, и нельзя реализовать A001 с 8-битным входом.

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

Короче, имея на входе 0xFF, как его не ксорь со сдвигами, 0x55 не получишь... Вот поэтому, и нельзя реализовать A001 с 8-битным входом.

Не, как говорит один коллега, "не вкуриваю". У 0x1021 тоже единица в младшем разряде, но для него формула есть и работает.

[SM]

Не, как говорит один коллега, "не вкуриваю". У 0x1021 тоже единица в младшем разряде, но для него формула есть и работает.

А там вся хитрость в том, что сдвиг-то в обратную сторону. А если все привести к сдвигу вправо... Получим знакомый 0x8408! То есть, для влево двигающихся CRC, ограничение вводит близость самого старшего бита полинома, установленного в 1, к старшему разряду. А для вправо двигающихся - младшей 1 к младшему оазряду.
То есть, 0x8408 - это 0x1021, но через зад. То есть, это один и тот же полином, реализации разные.

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

То есть, 0x8408 - это 0x1021, но через зад.

Да, пока домой ехал сам понял.

[toweroff]

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

Когда пользовался CRC16, вычислял для всего блока, вместе с контрольной суммой в конце. Если не ноль - ошибка
С CRC32 такое не прокатывает, сама сумма получается верной, но расчет вместе с самой суммой ноль не выдает
Это, я так понимаю, связано с инвертированием суммы до и после расчета. А есть алгоритмы расчета CRC32, которые бы и сумму давали верную, и ноль вместе с ней получался?

[SM]

но расчет вместе с самой суммой ноль не выдает

Ну некую константу зато выдает. Разница совершенно не принципиальна, проверять на ноль, или на константу. Зато, снимается проблема, что, если после сообщения, в результате ошибки добавилось N нулевых бит, то, без инверсии, CRC останется нулем, и пройдет, как будто ошибок нет. С инверсией этого не произойдет. Для этого же инициализируют регистр в FFFFFFFF, только, защищаясь от добавленных нулевых бит в начале.

[toweroff]

Да суть-то не в этом - с нулем или константой сравнивать, просто если пакет вида:

[START]
[LEN]
[BODY]
[CRC]

где LEN - общая длина, включая заголовок и сумму, расчитать все это дело и сравнить с нулем без лишних телодвижений
Если же сравнивать конкретно с суммой, то нужно каждый раз корректировать длину на размер uint32_t, вычислять и сравнивать уже с тем, что в пакете

[SM]

Если же сравнивать конкретно с суммой, то нужно каждый раз корректировать длину на размер uint32_t, вычислять и сравнивать уже с тем, что в пакете

Зачем? Просчитывается весь пакет, вместе с инверсной CRC, только результат сравнивается с некой константой, а не с нулем. Эту константу можно получить, обсчитав один заведомо безошибочный пакет.

[toweroff]

Эту константу можно получить, обсчитав один заведомо безошибочный пакет.

хмм.. получается, что эта константа и есть именно константа? при разных данных меняться не будет?

[SM]

хмм.. получается, что эта константа и есть именно константа? при разных данных меняться не будет?

Да.
Короче, если проинициализировать регистр-аккумулятор CRC неким числом, и пропустить через CRC после этой инициализации это же число, но проинвертированное, по разрядности равное разрядности самой CRC, то получится всегда одна и та же константа, которая зависит только от полинома, а не от этого числа. Аналогично и с Вашим нулем - если проинициализировать регистр числом, и потом пропустить это же число, получится всегда ноль.

PS
Разумеется, это если еще и разряды не переставлены через зад в шахматном порядке, как в LCRC/ECRC PCI Express-а, например.

[toweroff]

Так.
Не получается у меня, или я не так понял.

[BODY1]
[VALID_CRC1]

[BODY2]
[VALID_CRC2]

расчет CRC32 для обоих случаев блоков [BODY1+CRC1] и [BODY2+CRC2] должен дать одинаковый результат, который есть константа для данного полинома?

[ViKo]

Пользуюсь аппаратным CRC32 в STM32, никаких перестановок битов не делаю. Дописываю ее в конец суперструктуры. При расчете CRC вместе с дописанной получаю 0.

[toweroff]

Пользуюсь аппаратным CRC32 в STM32, никаких перестановок битов не делаю. Дописываю ее в конец суперструктуры. При расчете CRC вместе с дописанной получаю 0.

ну вот я тоже так думаю, что должен быть 0

взял WinHex, посчитал CRC32 сгенеренного блока. Увеличил блок на 4 байта, дописал туда эту CRC32 - не получается 0, хоть тресни! Ни инвертирование, ни замена байтов для всяких Big/Little endian не помогли. НЕ ноль и все тут

[ViKo]

В аппаратном CRC STM32 перед началом расчета нужно сбросить устройство CRC, при этом регистр CRC_DR устанавливается в 0xFFFFFFFF.

[SM]

расчет CRC32 для обоих случаев блоков [BODY1+CRC1] и [BODY2+CRC2] должен дать одинаковый результат, который есть константа для данного полинома?

Да. Именно так. При условии, что последовательность бит в CRC не перевернута и не переставлена. Для неинвертированной CRC - ноль. Для инвертированной - некая ненулевая константа. Ищите ошибки у себя. В WinHex, возможно, порядок следования байт неверный сделали, little/big endian, когда CRC добавляли к блоку. Или сдвиг при подсчете CRC был не в ту сторону, чтобы добавлять CRC к блоку, не переворачивая биты задом наперед.

А чтобы лучше искалось, где ошибка - вот:

CODE

#include "memory.h"
#include "stdio.h"

typedef unsigned short USHORT;
typedef unsigned int UINT;

UINT CRC_EDB88320(char *buf, int len, UINT init)
{
UINT crc = init;

for (int pos = 0; pos < len; pos++) {

crc ^= (UINT)((unsigned char)(buf[pos]));

for (int i = 8; i != 0; i--) {
if ((crc & 1) != 0) {
crc >>= 1;
crc ^= 0xEDB88320;
}
else
crc >>= 1;
}
}
return crc;
}

int main(int argc, char* argv[])
{
char data[32];
UINT crc;

memcpy( data, "0123456", 7);
printf ("CRC=%08X\n", crc=CRC_EDB88320(data,7,0xFFFFFFFF));
crc = ~crc; memcpy( data+7, &crc, 4);
printf ("CONST=%08X\n", crc=CRC_EDB88320(data,11,0xFFFFFFFF));

memcpy( data, "235547welbxdgu", 14);
printf ("CRC=%08X\n", crc=CRC_EDB88320(data,14,0xFFFFFFFF));
crc=~crc; memcpy( data+14, &crc, 4);
printf ("CONST=%08X\n", crc=CRC_EDB88320(data,18,0xFFFFFFFF));

memcpy( data, "0123456", 7);
printf ("CRC=%08X\n", crc=CRC_EDB88320(data,7,0xFFFFFFFF));
memcpy( data+7, &crc, 4);
printf ("CONST=%08X\n", crc=CRC_EDB88320(data,11,0xFFFFFFFF));

memcpy( data, "235547welbxdgu", 14);
printf ("CRC=%08X\n", crc=CRC_EDB88320(data,14,0xFFFFFFFF));
memcpy( data+14, &crc, 4);
printf ("CONST=%08X\n", crc=CRC_EDB88320(data,18,0xFFFFFFFF));

return 0;
}

Вывод этой программы:

CRC=7240F711
CONST=DEBB20E3
CRC=28E92D48
CONST=DEBB20E3
CRC=7240F711
CONST=00000000
CRC=28E92D48
CONST=00000000

[toweroff]

Вот о чем я и говорил - если не инвертировать, то все сходится. Но не сходится с "кошерными" результатами (которые вычисляются с инверсией начальной CRC и выходного результата)

[SM]

Вот о чем я и говорил - если не инвертировать, то все сходится. Но не сходится с "кошерными" результатами

Не... Это именно, о чем я говорил - если не инвертировать, то проверять надо на ноль. Если инвертировать (кошерно) - то на 0xDEBB20E3 (для полинома 0xEDB88320). Что, по сути, без разницы - и то, и это, просто сравнение с константой, и ресурс занимает одинаковый. Вам, вообще, шашечки (чтобы константа была нулем?), или ехать (просто какая-то любая константа?)? Я даже больший секрет раскрою - значение на выходе остается константой (разумеется другой какой-то) при инверсии любого кол-ва любых бит CRC, а не только инверсии ее целиком.

А начальная инверсия, и, вообще, начальное значение, на это никак не влияют.


Добавлю. Константу, на которую надо проверять при подсчете с инверсной CRC, определить можно еще одним способом - это CRC числа ноль длиной в кол-во разрядов CRC при тех же начальных условиях (инициализации в 0xFFFFFFFF), как считается эта CRC.

[toweroff]

Просто может возникнуть необходимость проверить "на коленках" какой-то кусок данных внешними инструментами и получается, что, вроде как, сумма другая, хотя, на самом деле, - просто инвертированная
А так оно да, уже все работает и мне абсолютно фиолетово с чем сравнивать - с нулем или константой