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

Я как раз для 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 0]

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

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

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

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

 

[SM 0]

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

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

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

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

Да.

 

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

 

 

// обсчет одного байта "в лоб":
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 0]

в общем, объясню на примере 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.

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

Такс. Я разобрался. 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 0]

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

Не реализуемо из-за единицы в 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-битным входом.

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

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

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

 

[SM 0]

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

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

То есть, 0x8408 - это 0x1021, но через зад. То есть, это один и тот же полином, реализации разные.

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

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

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

[toweroff 1]

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

 

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

С CRC32 такое не прокатывает, сама сумма получается верной, но расчет вместе с самой суммой ноль не выдает

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

 

[SM 0]

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

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

[toweroff 1]

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

 

[sTART]

[LEN]

[bODY]

[CRC]

 

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

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

 

[SM 0]

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

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