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

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

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

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

Да.

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


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


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

в общем, объясню на примере 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) получается следующим образом:
Итого, на выходе имеем:
Сошлось.

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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