CRC32, uint32_t Опции

[toweroff]

Добрый день!

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

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

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

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

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

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

Такс. Я разобрался. 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, но через зад.

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