Расчет CRC32 для буфера / файла с нулевым заполнением

Сложность по времени может быть уменьшена до O (1) с помощью поиска в таблице с последующим умножением. Объяснение и пример кода показаны в третьем разделе этого ответа.

Если 1000 является константой, предварительно вычисленная таблица из 32 значений, каждое из которых представляет может использоваться каждый бит CRC до 8000-й степени mod poly. Набор матриц (один набор на байт CRC) может использоваться для работы с байтом за раз. Оба метода будут иметь постоянное время (фиксированное количество петель) O (1).

Как отмечалось выше, если 1000 не является константой, то можно использовать возведение в степень возведением в квадрат, что будет иметь временную сложность O (log2 (n)) или комбинацию предварительно вычисленных таблиц для некоторого постоянного числа нулевых битов, например 256, с последующим возведением в степень и возведением в квадрат, чтобы конечный шаг был O (log2 (n% 256)).

Оптимизация в целом: для обычных данных с нулевыми и ненулевыми элементами на современной X86 с pclmulqdq (использует регистры xmm) может быть реализован быстрый crc32 (или crc16), хотя он близок к 500 строкам ассемблерного кода. Документ Intel: crc с использованием pclmulqdq. Пример исходного кода для github fast crc16. Для 32-битной CRC требуется другой набор констант. Если интересно, я преобразовал исходный код для работы с Visual Studio ML64.EXE (64-битный MASM) и создал примеры для 32-битных CRC со сдвигом влево и вправо, каждый с двумя наборами констант для двух самых популярных 32-битных полиномов CRC. (полисы сдвига влево: crc32: 0x104C11DB7 и crc32c: 0x11EDC6F41, полисы сдвига вправо меняются местами).

Пример кода для быстрой настройки CRC с использованием программного обеспечения умножения без переноса по модулю полиномиального CRC. Это будет намного быстрее, чем использование матричного умножения 32 x 32. CRC вычисляется для ненулевых данных: crf = GenCrc (msg, ...). Константа регулировки вычисляется для n нулевых байтов: pmc = pow (2 ^ (8 * n))% poly (с использованием возведения в степень путем повторного возведения в квадрат). Затем CRC корректируется для нулевых байтов: crf = (crf * pmc)% poly.

Обратите внимание, что временная сложность может быть уменьшена до O (1) с помощью создания таблицы констант pow (2 ^ (8 * i))% poly для i = от 1 до n. Затем выполняется поиск по таблице и фиксированная итерация (32 цикла) умножения% poly.

#include <stdio.h>
#include <stdlib.h>

typedef unsigned char       uint8_t;
typedef unsigned int       uint32_t;

static uint32_t crctbl[256];

void GenTbl(void)                       /* generate crc table */
{
uint32_t crc;
uint32_t c;
uint32_t i;
    for(c = 0; c < 0x100; c++){
        crc = c<<24;
        for(i = 0; i < 8; i++)
            crc = (crc<<1)^((0-(crc>>31))&0x04c11db7);
        crctbl[c] = crc;
    }
}

uint32_t GenCrc(uint8_t * bfr, size_t size) /* generate crc */
{
uint32_t crc = 0u;
    while(size--)
        crc = (crc<<8)^crctbl[(crc>>24)^*bfr++];
    return(crc);
}

/* carryless multiply modulo crc */
uint32_t MpyModCrc(uint32_t a, uint32_t b) /* (a*b)%crc */
{
uint32_t pd = 0;
uint32_t i;
    for(i = 0; i < 32; i++){
        pd = (pd<<1)^((0-(pd>>31))&0x04c11db7u);
        pd ^= (0-(b>>31))&a;
        b <<= 1;
    }
    return pd;
}

/* exponentiate by repeated squaring modulo crc */
uint32_t PowModCrc(uint32_t p)          /* pow(2,p)%crc */
{
uint32_t prd = 0x1u;                    /* current product */
uint32_t sqr = 0x2u;                    /* current square */
    while(p){
        if (p&1)
            prd = MpyModCrc(prd, sqr);
        sqr = MpyModCrc(sqr, sqr);
        p >>= 1;
    }
    return prd;
}

/* # data bytes */
#define DAT  ( 32)
/* # zero bytes */
#define PAD  (992)
/* DATA+PAD */
#define CNT (1024)

int main()
{
uint32_t pmc;
uint32_t crc;
uint32_t crf;
uint32_t i;
uint8_t *msg = malloc(CNT);

    for(i = 0; i < DAT; i++)           /* generate msg */
        msg[i] = (uint8_t)rand();
    for( ; i < CNT; i++)
        msg[i] = 0;
    GenTbl();                           /* generate crc table */
    crc = GenCrc(msg, CNT);             /* generate crc normally */
    crf = GenCrc(msg, DAT);             /* generate crc for data */
    pmc = PowModCrc(PAD*8);             /* pmc = pow(2,PAD*8)%crc */
    crf = MpyModCrc(crf, pmc);          /* crf = (crf*pmc)%crc */
    printf("%08x %08x\n", crc, crf);    /* crf == crc */
    free(msg);
    return 0;
}

Вы можете вычислить результат применения нулей п не за время O (1), а за время O (log п). Это делается в crc32_combine() zlib. Создается двоичная матрица, которая представляет операцию применения одного нулевого бита к CRC. Матрица 32x32 умножает 32-битный CRC на GF (2), где сложение заменяется на исключающее ИЛИ (^), а умножение заменяется на и (&), бит за битом.

Затем эту матрицу можно возвести в квадрат, чтобы получить оператор для двух нулей. Это возведено в квадрат, чтобы получить оператор для четырех нулей. Третье возводится в квадрат, чтобы получить оператор для восьми нулей. И так далее по мере необходимости.

Теперь этот набор операторов может быть применен к CRC на основе единичных битов в числе п нулевых битов, для которых вы хотите вычислить CRC.

Вы можете предварительно вычислить результирующий матричный оператор для любого количества нулевых битов, если вы знаете, что часто будете применять именно такое количество нулей. Тогда это всего лишь одно умножение матрицы на вектор, который на самом деле равен O (1).

Вам не нужно использовать инструкцию pclmulqdq, предложенную в другом ответе здесь, но это было бы немного быстрее, если бы она у вас была. Это не изменит O () операции.

CRC32 основан на умножении в GF (2) [X] по модулю некоторого многочлена, который является мультипликативным. Сложная часть - это отделение неумножительного от мультипликативного.

Сначала определите разреженный файл со следующей структурой (в Go):

type SparseFile struct {
    FileBytes []SparseByte
    Size      uint64
}
type SparseByte struct {
    Position uint64
    Value    byte
}

В вашем случае это будет SparseFile{[]FileByte{}, 1000}

Тогда функция будет такой:

func IEEESparse (file SparseFile) uint32 {
    position2Index := map[uint64]int{}
    for i , v := range(file.FileBytes) {
        file.FileBytes[i].Value = bits.Reverse8(v.Value)
        position2Index[v.Position] = i
    }
    for i := 0; i < 4; i++ {
        index, ok := position2Index[uint64(i)]
        if !ok {
            file.FileBytes = append(file.FileBytes, SparseByte{Position: uint64(i), Value: 0xFF})
        } else {
            file.FileBytes[index].Value ^= 0xFF
        }
    }

    // Add padding
    file.Size += 4
    newReminder := bits.Reverse32(reminderIEEESparse(file))

    return newReminder ^ 0xFFFFFFFF
}

Так что обратите внимание, что:

1. Деление выполняется по битам в обратном порядке (по байтам).
2. Первые четыре байта имеют значение 0xFF.
3. Файл дополняется 4 байтами.
4. Напоминание снова отменено.
5. Напоминание снова зафиксировано.

Внутренняя функция reminderIEEESparse является настоящим напоминанием, и ее легко реализовать в O(log n), где n - размер файла.

Вы можете найти полную реализацию здесь.