Как работает оптимизация поиска таблицы CRC? - PullRequest
Новая
       43

Как работает оптимизация поиска таблицы CRC?

0 голосов
/ 07 сентября 2018

Я пытаюсь понять оптимизацию поиска в таблице CRC, выполнив: http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html#ch5, в частности: 

public static ushort Compute_CRC16(byte[] bytes)
{
    ushort crc = 0;
    foreach (byte b in bytes)
    {
        /* XOR-in next input byte into MSB of crc, that's our new intermediate divident */
        byte pos = (byte)( (crc >> 8) ^ b); /* equal: ((crc ^ (b << 8)) >> 8) */
        /* Shift out the MSB used for division per lookuptable and XOR with the remainder */
        crc = (ushort)((crc << 8) ^ (ushort)(crctable16[pos]));
    }
    return crc;
}

Я понимаю базовый побитовый подход и метод поиска, но мне трудно поймать эту строку:

crc = (ushort)((crc << 8) ^ (ushort)(crctable16[pos])); Почему существующий CRC должен быть смещен? Почему этот трюк работает? На чем он основан?

Спасибо.

PS: да, я читаю эту ветку: Как вычисляется контрольная сумма CRC32? (это не обман, потому что описывает базовый метод)

1 Ответ

0 голосов
/ 08 сентября 2018

Это пример CRC смещения влево. Байт данных XOR связан с старшим байтом CRC. Чтобы выполнить поиск в таблице (индексировать массив), результат должен быть смещен вправо, или сначала может быть смещен байт старшего разряда CRC, а затем XOR с байтом данных для получения нового промежуточного байта старшего разряда. CRC, то это должно быть циклировано 8 раз, чтобы получить результат циклирования CRC 8, или это может быть сделано заранее для всех 256 возможных 8-битных значений, чтобы сгенерировать таблицу, и можно использовать поиск по таблице. вместо того, чтобы ездить на велосипеде 8 раз. После этого цикла младший байт необходимо будет сдвинуть влево, чтобы вы получили код, показанный на рисунке.

Сдвиг влево CRC аналогичен выполнению длинного ручного деления в двоичном коде с использованием полинома CRC в качестве делителя и данных в качестве длинного дивиденда, за исключением того, что вместо вычитания используется XOR, а последний остаток - CRC , Оказывается, что одновременное выполнение XOR 8 битов данных (дивидендов) не влияет на результат, поскольку каждый факторный бит основан только на старшем значащем бите полинома CRC и текущем старшем значащем бите рабочего дивиденда (данных ), что позволяет оптимизировать использование таблицы.

...