D
In fact, the decision is for O(log(n) * 32)where n is the sequence length after the amended byte.
First of all, let's turn to https://stackoverflow.com/questions/34601950/how-to-recalculate-a-crc32-on-a-large-byte-array-when-replacing-a-small-number-o/ ♪ See the remarkable performance of the function crc32_combine from zlib♪ She's slow-- O(log(n) * 32 * 32) - Removing the matrix for a long time. For starters, we'll notice that each time we just multiply the same matrices, so we can take two sets of matrices that we prejudge in advance. Thus, the asymptomy of the decision is rapidly declining 32 times. First, I'll tell you what I'm doing. crc32_combine♪ She takes crc32 in the first sequence and moves. len2 Byte. So if we changed the white iand we know crc32 for cut [0; i] = crc1and we know a new crc32 for the same cut = crc2the answer will be crc32_combine(crc1 ^ crc2, original_crc, n - i - 1)where original_crc - original crc32 sequence. How do we predict the matrices? Let's emulate 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;
}
How quickly do we consider a new crc32 modified sequence for O (length sequence)? Let's prejudge crc32.
UPD: It is possible to halve the amount of memory by splitting the step into two when calculating the measure CRC.
