Быстрый пересчет CRC32

20 декабря 2021, 06:20

имеется такая проблема: надо быстро (худший вариант за O(log N)) пересчитать CRC32 массива. Дан массив и 4 измененных ПОСЛЕДОВАТЕЛЬНЫХ байта. Где-то вычитал идею с бинарным возведением в степень, но так и не смог развить. Было бы замечательно, если бы вы привели пример на псевдокоде или ЯП, с пояснением что и как. Заранее спасибо!

UPD: Мы умеем это делать быстрее, чем за линейное время(для последовательности длины > 400), одна проблема: это слишком медленно.

Как это можно сделать? Давайте предположим, что за log(n) * const мы умеем мержить два CRC32 в один. В таком случае, давайте построим ДО, и массив префиксов изначальных CRC32. В таком случае, за O(4) мы получим значение CRC32 на отрезке [0; i+3], за log^2*const на отрезке [i+4; n-1]. И смержим их в один. Смежная проблема: можно ли как-то быстро посчитать массив суффиксов CRC32 для данной последовательности? Формально, такой массив suff, что suff[i]=CRC32(a, i, n-1), где CRC32(array, left, right) - CRC32 на отрезке от left до right в массиве array.

Answer 1

Собственно, решение за O(log(n) * 32), где n - длина последовательности после измененных байт. Для начала, давайте обратимся к ответу. Посмотрим замечательную реализацию функции crc32_combine от zlib. Она медленная - O(log(n) * 32 * 32) - перемножение матриц долгое. Для начала, заметим, что мы каждый раз просто перемножаем одни и те же матрицы, таким образом, мы можем взять два массива матриц, которые мы предпосчитаем заранее. Таким образом, асимптотика решения быстро сокращается в 32 раза. Для начала, расскажу, что делает crc32_combine. Она берет crc32 первой последовательности и "сдвигает" её на len2 байт. Таким образом, если мы меняли байт i, и знаем crc32 для отрезка [0; i] = crc1, и знаем новый crc32 для того же отрезка = crc2, ответом будет являться crc32_combine(crc1 ^ crc2, original_crc, n - i - 1), где original_crc - оригинальный crc32 последовательности. Каким образом предпосчитать массивы матриц? Давайте эмулировать crc32_combine.

#define GF2_DIM 32 
uint32_t odd[32][32];
uint32_t even[32][32];
unsigned long gf2_matrix_times(
    uint32_t* mat,
    uint32_t vec)
{
    uint32_t sum = 0;
    while (vec) {
        if (vec & 1)
            sum ^= *mat;
        vec >>= 1;
        ++mat;
    }
    return sum;
}

void gf2_matrix_square(
    uint32_t* square,
    uint32_t* mat)
{
    int n;
    for (n = 0; n < GF2_DIM; n++)
        square[n] = gf2_matrix_times(mat, mat[n]);
}
void precalc() {
    uint32_t even1[GF2_DIM] = { 1996959894, 3993919788, 124634137, 249268274, 498536548, 997073096, 1994146192, 3988292384, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, };    /* even-power-of-two zeros operator */
    uint32_t odd1[GF2_DIM] = { 498536548, 997073096, 1994146192, 3988292384, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, };     /* odd-power-of-two zeros operator */
    uint32_t i = 0;
    do {
        if (i)
            gf2_matrix_square(even1, odd1);
        for (int j = 0; j < GF2_DIM; j++) 
            even[i][j] = even1[j];
        gf2_matrix_square(odd1, even1);
        i++;
        for (int j = 0; j < GF2_DIM; j++)
            odd[i][j] = odd1[j];
        i++;
    } while (i < 32);
}
uint32_t crc32_update(
    uint32_t crc1,
    uint32_t crc2,
    size_t len2)
{
    uint32_t n;
    uint32_t row;
    int step = 0;
    do {
        if (len2 & 1)
            crc1 = gf2_matrix_times(even[step], crc1);
        len2 >>= 1;
        step++;
        if (!len2)
            break;
        if (len2 & 1)
            crc1 = gf2_matrix_times(odd[step], crc1);
        len2 >>= 1;
        step++;
    } while (len2);
    return crc1 ^ crc2;
}

Как быстро считать новый crc32 измененной последовательности за O(длина последовательности)? Давайте предпосчитаем префиксы crc32. UPD: можно сократить объем памяти в два раза, путём деление шага на два при подсчете мержа CRC32.