CRC32, uint32_t Опции

[toweroff]

Добрый день!

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

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

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

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

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

[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 в примере понятно. Осталось понять, как эти выражения для каждого бита свернуть в общую формулу.