Сокращение расчета CRC

Question

У меня есть один вопрос по математике и программированию о вычислениях CRC, чтобы избежать повторного вычисления полного CRC для блока, когда необходимо изменить только небольшую его часть.

Моя проблема заключается в следующем: у меня 1Kблок из 4 байтовых структур, каждая из которых представляет поле данных.Полный блок 1K имеет в конце блок CRC16, рассчитанный по полному 1K.Когда мне нужно изменить только 4-байтовую структуру, я должен пересчитать CRC полного блока, но я ищу более эффективное решение этой проблемы.Что-то где:

1. Я беру полный ток блока 1K CRC16

2. Я вычисляю что-то на старом 4-байтовом блоке

3. Я «вычитаю» что-то, полученное на шаге 2, из полного 1K CRC16

4. Я вычисляю что-то на новом 4-байтовом блоке

5. Я «добавляю» что-то, полученное на шаге 4, к результату, полученному на шаге 3

Подводя итог, я думаю о чем-то вроде этого:

CRC (new-full) = [CRC (old-full) - CRC (block-old) + CRC (block-new)]

Но мне не хватает математики и того, что нужно сделать, чтобы получить этот результат,учитывая также «общую формулу».

Заранее спасибо.

Answer 1

Возьмите ваш начальный 1024-байтовый блок A и ваш новый 1024-байтовый блок B. Исключительно - или их, чтобы получить блок C. Поскольку вы изменили только четыре байта, C будет набором нулей, четыре байта, которые являются эксклюзивными, -или из предыдущих и новых четырех байтов и еще нескольких нулей.

Теперь вычисляем CRC-16 блока C, но без какой-либо предварительной или последующей обработки.Мы будем называть это CRC-16 '.(Мне нужно было бы увидеть конкретный CRC-16, который вы используете, чтобы увидеть, что это за обработка, если что-нибудь.) Эксклюзивно - или CRC-16 блока A с CRC-16 'блока C, и теперь у вас естьCRC-16 блока B.

На первый взгляд, это может показаться не таким уж большим преимуществом по сравнению с простым вычислением CRC блока B. Однако есть и хитрости для быстрого вычисления CRC группынули.Прежде всего, нули , предшествующие четырем измененным байтам, дают ноль CRC-16 'независимо от того, сколько существует нулей.Таким образом, вы просто начинаете вычислять CRC-16 'с исключительным или из предыдущих и новых четырех байтов.

Теперь вы продолжаете вычислять CRC-16' на оставшихся n нуляхпосле измененных байтов.Обычно для вычисления CRC на n байтов требуется время O ( n ).Однако, если вы знаете, что все они - нули (или все некоторые постоянные значения), то это можно вычислить за время O (log n ).Вы можете увидеть пример того, как это делается в подпрограмме zlib crc32_combine() , и применить ее к своему CRC.

Учитывая ваши параметры CRC-16 / DNP, подпрограмма zeros()ниже будет применено запрошенное число нулевых байтов к CRC в O (log n ) времени.

// Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC
// polynomial, reflected. For speed, this requires that a not be zero.
uint16_t multmodp(uint16_t a, uint16_t b) {
    uint16_t m = (uint16_t)1 << 15;
    uint16_t p = 0;
    for (;;) {
        if (a & m) {
            p ^= b;
            if ((a & (m - 1)) == 0)
                break;
        }
        m >>= 1;
        b = b & 1 ? (b >> 1) ^ 0xa6bc : b >> 1;
    }
    return p;
}

// Table of x^2^n modulo p(x).
uint16_t const x2n_table[] = {
    0x4000, 0x2000, 0x0800, 0x0080, 0xa6bc, 0x55a7, 0xfc4f, 0x1f78,
    0xa31f, 0x78c1, 0xbe76, 0xac8f, 0xb26b, 0x3370, 0xb090
};

// Return x^(n*2^k) modulo p(x).
uint16_t x2nmodp(size_t n, unsigned k) {
    k %= 15;
    uint16_t p = (uint16_t)1 << 15;
    for (;;) {
        if (n & 1)
            p = multmodp(x2n_table[k], p);
        n >>= 1;
        if (n == 0)
            break;
        if (++k == 15)
            k = 0;
    }
    return p;
}

// Apply n zero bytes to crc.
uint16_t zeros(uint16_t crc, size_t n) {
    return multmodp(x2nmodp(n, 3), crc);
}

Answer 2

CRC на самом деле делает это легко.

Глядя на это, я уверен, что вы начали читать, что CRC рассчитываются с полиномами по GF (2), и, вероятно, пропустили эту часть, чтобы сразу же получить полезную информацию. Что ж, похоже, пришло время вам вернуться к этому материалу и перечитать его несколько раз, чтобы вы могли по-настоящему понять его.

Но все равно ...

Из-за способа расчета CRC они обладают свойством, которое при двух блоках A и B CRC (A xor B) = CRC (A) xor CRC (B)

Итак, первое упрощение, которое вы можете сделать, это то, что вам просто нужно вычислить CRC измененных битов. На самом деле вы могли бы заранее рассчитать CRC каждого бита в блоке, чтобы при изменении бита можно было просто переписать его CRC в CRC блока.

CRC также имеют свойство CRC (A * B) = CRC (A * CRC (B)), где это * - полиномиальное умножение над GF (2). Если вы заполняете блок нулями в конце, не делайте этого для CRC (B).

Это позволяет вам уйти с меньшего предварительно рассчитанного стола. «Полиномиальное умножение по GF (2)» является двоичной сверткой, поэтому умножение на 1000 равно сдвигу на 3 бита. С помощью этого правила вы можете предварительно рассчитать CRC смещения каждого поля. Затем просто умножьте (сверните) измененные биты на CRC смещения (рассчитанный без заполнения нулями), вычислите CRC этих 8 байтов и скопируйте их в CRC блока.

Answer 3

CRC - это остаток от длинного целого числа, образованного входным потоком, и короткого целого числа, соответствующего многочлену, скажем, p.

Если вы измените некоторые биты посередине, это будет равным возмущению дивиденда на n 2^k, где n имеет длину возмущенного участка, а k - это число следующих битов.

Следовательно, вам нужно вычислить возмущение остатка, (n 2^k) mod p. Вы можете решить эту проблему, используя

(n 2^k) mod p = (n mod p) (2^k mod p)

Первый фактор - это просто CRC16 n. Другой фактор может быть эффективно получен в Log k операциях с помощью алгоритма мощности, основанного на квадратурах.

Answer 4

CRC зависит от рассчитанного CRC данных ранее. Таким образом, единственная оптимизация состоит в том, чтобы логически разделить данные на N-сегмент и сохранить вычисленное CRC-состояние для каждого сегмента.

Тогда, например, изменив сегмент 6 (из 0..9), получите CRC-состояние сегмента 5 и продолжите вычисление CRC, начиная с сегмента 6 и заканчивая 9.

В любом случае, вычисления CRC очень быстрые. Вот и думай, если оно того стоит.