Можно ли использовать механизм CRC32 для вычисления хэшей CRC16?
Я работаю с микроконтроллером с собственными функциями HW для вычисления хэшей CRC32 из кусков памяти, где полином можно свободно определять. Оказывается, что система имеет разные каналы передачи данных с разной длиной битов для CRC, например, 16 и 8 бит, и я намерен использовать для этого аппаратный движок.
В простых тестах с онлайн-инструментами я пришел к выводу, что можно найти 32-битный полином, который имеет тот же результат, что и 8-битный CRC, например:
- хэширование "образца строки" с 8-битным движком и поли 0xb7 дает результат 0x97
- хэширование "образца строки" с 16-битным движком и поли 0xb700 дает результат 0x9700
- ... 32-битный движок и поли 0xb7000000 дают результат 0x97000000 (с нулевым начальным значением и нулевым конечным xor, без отражений)
Таким образом, заполнение поли нулями и сдвиг вправо результатов, кажется, работает. Но "всегда" можно найти набор параметров, которые делают 32-битные движки работающими как 16 или 8-битные? (включая poly, final xor, init val и инверсии)
Чтобы обеспечить больше контекста и предотвратить "обходные ответы", такие как "не использовать собственный механизм": у меня есть сценарий в критической для безопасности системе, где необходимо предотвратить распространение общей ошибки проектирования на избыточные узлы обработки. Одним из решений для этого является программный CRC-расчет в одном узле и аппаратный в его паре.
2 ответа
Да, то, что вы делаете, будет работать в целом для CRC, которые не отражены. Предварительная и последующая обработка могут быть выполнены очень просто с помощью кода вокруг цикла аппаратных инструкций.
Предполагая, что аппаратный CRC не имеет возможности для этого, чтобы сделать отраженный CRC, вам нужно будет отразить каждый входной байт, а затем отразить конечный результат. Это может победить цель использования аппаратного CRC. (Хотя, если ваша цель просто иметь другую реализацию, то, возможно, это не так.)
Вам не нужно гадать. Вы можете вычислить его. Поскольку CRC является остатком от деления на неприводимый многочлен, это функция 1-к-1 в своей области определения.
Так, CRC16, например, должен выдать 65536 (64k) уникальных результатов, если вы запустите его от 0 до 65536.
Чтобы увидеть, получите ли вы тот же результат, взяв части CRC32, запустите его от 0 до 65535, оставьте 2 байта, которые вы хотите сохранить, а затем посмотрите, есть ли какие-либо коллизии.
Если в ваших данных 32 бита, то это не должно быть проблемой. Проблема возникает, если у вас меньше 32-битных чисел, и вы перемешиваете их в 32-битном пространстве. Равномерное распределение их первого и последнего байта не гарантируется.