Лучший способ генерировать CRC8 / 16, когда ввод нечетного числа битов (не байтов)?C или Python

Question

Так что я застрял с протоколом, который добавляет CRC8 / CRC16 к нечетному числу битов. (т.е. это не делится на 8) Каков наилучший метод для генерации CRC для него в программном обеспечении?

Существует множество алгоритмов CRC, в которых используется таблица, но они ищут по байту. Конечно, есть «отказоустойчивый» способ делать это по одному. Но есть ли лучший подход? Может быть, делать это в основном путем поиска таблиц, а затем закончить делать это по очереди?

В настоящее время я использую bitarray в python для обработки этого. Но решение в C также будет работать. Спасибо!

РЕДАКТИРОВАТЬ: обратите внимание, что я взаимодействую с существующим оборудованием, которое вычисляет CRC по нечетному количеству битов. (Это легко для HW, так как они просто используют LFSR - 1 бит за раз!) Так что, хотя заполнение с известным шаблоном будет работать ради проверки целостности, это нарушит совместимость hw.

Answer 1

Заполнение нулями спереди не должно изменить результат.Вычисление CRC является по существу двоичным длинным делением.К сожалению, это включает в себя разделение каждого байта.Это легко сделать с помощью операторов сдвига и побитового или.

Заполнение нулями в конце намного проще, и в зависимости от вашей причины для вычисления CRC, вполне разумная вещь.Например, если вы используете CRC для проверки целостности.

Редактировать Используя мой пример из моего комментария.Если у вас есть 11 битов 11101110111 и вы хотите вычислить CRC, добавьте их, чтобы получить 00000111 01110111 = 0x777, не добавляйте их, чтобы получить 0x7770, так как это будет иметь другой CRC.

Причина, по которой это работает, заключается в том, что CRC является по существу двоичным длинным делением

                    1 0 1 = 5
            -------------
1 0 0 1 1 / 1 1 0 1 1 0 1
            1 0 0 1 1 | |
            --------- | |
              1 0 0 0 0 |
              0 0 0 0 0 |
              --------- |
              1 0 0 0 0 1
                1 0 0 1 1
                ---------
                  1 1 1 0 = 14 = remainder

Имеет точно такой же результат, как

                      1 0 1 = 5
            ---------------
1 0 0 1 1 / 0 1 1 0 1 1 0 1
              1 0 0 1 1 | |
              --------- | |
                1 0 0 0 0 |
                0 0 0 0 0 |
                --------- |
                1 0 0 0 0 1
                  1 0 0 1 1
                  ---------
                    1 1 1 0 = 14 = remainder

и аналогично для любого числа ведущихнули.

Примечание на данный момент, если вы не психиатр, ищущий полевую работу, хотите стать им или тайно хотите увидеть его, это может стоить вашего времени, чтобыперейдите к Супер двойному секретному испытательному редактированию

Дальнейшее редактирование В связи с изменением вопроса

Если у вас нетривиальный начальный вектор, вы можете сделатьследующий.Скажем, мы хотим вычислить CRC-CCITT CRC из приведенной выше строки с инициализатором FFFF.Мы дополняем строку, чтобы получить 0x0FFF, вычисляем CRC-CCIT с инициализатором 0, чтобы получить 0x0ECE, затем вычисляем CRC-CCIT с инициализатором 0xFFFF, равным 0x0000, чтобы получить 0x1D0F, и xor их 0x0ECE xor 0x1D0F = 0x13C1.

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

СутьТехника заключается в том, что мы можем рассматривать состояние регистра сдвига как полином.Если мы инициализируем его с n единицами, это то же самое, что и исходный полином: p (x) = x ^ (n - 1) + x ^ (n - 2) ... + x + 1 ,Вычисление CRC строки из k нулей эквивалентно нахождению p (x) x ^ k mod CRC. x ^ k мод CRC легко найти путем повторного возведения в квадрат и уменьшения.Любая библиотека для полиномиальной арифметики над GF (2) должна сделать это.

Еще больше Edit Вероятно, имеет смысл в случае ненулевых инициализаторов заполнять нулями и изменять инициализатор назначение такое, что после чтения | pad |число нулей в регистре сдвига FFFF (или любое другое значение, которое вы хотели. Они могут быть предварительно вычислены, и вам нужно сохранить только 16 или 32 из них (или сколько битов содержится в вашем полиноме crc.

Например, с CRC-CCIT с инициализатором 0xFFFF и заполнением одного бита 0 мы захотим использовать инициализатор 0xF7EF. Они могут быть вычислены путем нахождения x ^ (- 1) mod CRC с использованием расширенного евклидового алгоритма, а затем вычисления инициализатора * x^ (- k) мод CRC для различной длины заполнения. Опять же, любой пакет GF (2) polynomail должен упростить это. Я использовал NTL в прошлом и нашел его довольно гибким, но это, вероятно, излишнездесь. Даже для 32-битного crcs, exhjaustive search, вероятно, найдет инициализаторы быстрее, чем вы можете написать код.

Супер-двойной секретный испытательный срок

Хорошо, все на самом делезначительно проще, чем я думал. Общая идея верна, мы хотим дополнить строку нулями вфронт, чтобы расширить размер до кратного 8, 16 или 32, в зависимости от того, что хочет наша программная реализация, и мы хотим изменить наш начальный вектор, чтобы установить наше состояние в нечто такое, что после чтения нулей заполнения LFSR будет установлен вначальный вектор, который мы хотели.Мы, конечно, могли бы использовать арифметику поля Галуа для этого, но есть более простой способ: просто запустить LFSR в обратном направлении.

Например, если мы хотим вычислить CRC-CCITT (0xFFFF) из 11 битов 11 битов 11101110111, мы заполняем их 5 0, чтобы получить 00000111 01110111, а затем возвращаем LFSR на пять пробелов, чтобы получить начальный вектор 0xF060. (Я сделал вычисления вручную, так что будьте осторожны). Поэтому, если вы запускаете LSFR (или программную реализацию) с IV, равным 0xF060, и запускаете его с 0x0fff, вы должны получить тот же результат, что и запуск LFSR с IV, равным 0xFFFF для исходных 11 бит.