crc32 хэш по умолчанию / неверное значение?

Question

Я строю простую систему идентификации строк с использованием crc32 для генерации 32-битных целочисленных дескрипторов из моих строк. Я хотел бы по умолчанию хэш внутри моего класса оболочки StringID на недопустимый индекс по умолчанию, есть ли значение, которое crc32 никогда не будет генерировать? Должен ли я использовать отдельный флаг?

Пояснение: меня не интересуют конкретные языковые ответы. Я просто хотел бы знать, существует ли целое число вне диапазона crc32, которое можно использовать для представления нехэшированного значения.

Спасибо!

Answer 1

Есть ли значение, которое crc32 никогда не сгенерирует?

Нет, он будет генерировать любые / все значения в диапазоне 32-разрядного целого числа.

Должен ли я использовать отдельный флаг?

Не обязательно.

Если вы решите, что (например) 0x00000000 означает "CRC не установлен" и ненулевое значение CRC; затем, после расчета CRC (но до его сохранения или проверки сохраненного значения), вы можете выполнить if(CRCvalue == 0) CRCvalue = 0xFFFFFFFF;,

Это ослабляет КПР очень малым количеством. В частности, для 2 случайных фрагментов данных для чистого CRC32 есть 1 шанс в 4294967296 совпадениях CRC, а при "нулевом значении не установлено" есть 1 шанс в 4294967295.000000000232830643654 совпадений CRC.

Answer 2

Нет. CRC-32 может быть любым 32-битным значением. Вам нужно будет указать неверный индекс где-то еще.

Мой поддельный код позволяет вам выбирать битовые местоположения в сообщении для изменения и желаемый CRC, а также решать, для каких из этих местоположений перевернуть, чтобы получить именно этот CRC.

Answer 3

Существует простая демонстрация того факта, что вы можете сгенерировать любое значение crc32, так как оно является делением mod P (где P - полином генератора) в поле Галуа (которое является полем, как действительные или комплексные числа)., вы можете вычесть (это операция XOR, так что сложение и вычитание действительно одно и то же) к вашему полиному с его модулем, давая остаток 0, затем вы можете добавить к этому кратному модулю любое из всех возможных значений crc32, чтобы это (поскольку они уже являются остатками подразделений, их crc32 - только они сами), чтобы получить любое из 2^32 возможных значений.

Обычной практикой является добавление столько нулевых битов, сколько необходимо для завершения полного 32-битного слова (это выглядит как умножение на постоянное значение). x^32), а затем вычтите (xor) остаток от этого, сделав результат, кратный модулю (помните, что сложение и вычитание одинаковы - операция xor) и сделав таким образом crc32(pol) = 0x0000;

редактировать (легче увидеть)

Действительно, каждое из возможных 2^32 значений для crc32, будучи разделенным на многочлен генератора, дает себя в результате (они взаимно просты с многочленом генератора, как и числа 1 .. N при выполнении арифметики по модулю N на целых числах) так что все они являются возможными результатами crc32() оператор.

Операция crc, реализованная во многих местах, не так проста... так как некоторые реализации инициализируют регистр остатка как 0xffffffff и искать 0xffffffff в конце (действительно, crc32 делает это).... Если вы выполните математические расчеты, вы угадаете причину этого: 0x11111111 эквивалентно наличию предыдущего остатка 0xffffffff в более длинной строке... и ищет 0xffffffff в конце, как добавление 0xffffffff к исходной строке. Это имеет эффект конкатенации битовой строки 0xffffffff до и после вашей строки, делая остаток разумным для добавления строки нулей до и после вычисляемой строки crc32 (изменение строки битов путем добавления нулей с обеих сторон). Во всяком случае, эта модификация не меняет оригинальный алгоритм вычисления остатка полинома, поэтому любой из 2**32 значения возможны и в этом случае.