2014-08-29 4 views
11

Мне интересно, если CRC32 sum и CRC32C, в частности, когда-либо возвращаются к 0? Простым ответом было бы «да» при достаточно большом наборе данных. Тем не менее, мне было интересно, есть ли какие-либо условия в стандарте CRC32C, которые явно предотвратили бы это.Может ли CRC32 (C) когда-либо вернуться к 0?

В этом случае я должен проверить, удаленный файл пуст, и все, что у меня есть, это его контрольная сумма CRC32C. Таким образом, другими словами, могу ли я сделать вывод, что если CRC32C равно 0, то файл гарантированно будет пустым.

Если возможно, укажите любую ссылку на стандарт, где это определено.

+1

Вы можете использовать свои собственные контрольные суммы? В этом случае определите нуль, который будет использоваться только для пустого файла. Если нуль возникает из-за хэш-функции, просто установите его на 1. – usr

+0

Вы знаете значение CRC32, но не длину файла? А? – kay

+0

@usr CRC32C алгоритм высоко оптимизирован для скорости и реализован в аппаратных средствах на процессорах Intel. Мне это нужно для расчетов на скорости передачи, поэтому обычная реализация не является вариантом. – dtoux

ответ

12

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

+0

Это мое настоящее понимание, но я все еще надеюсь, что кто-то докажет, что я не прав :-) – dtoux

17

@ Янек почти полностью правильный.

Просто для удовольствия, вот пятисимвольная последовательность, которая дает CRC-32C нуля: DYB|O. Вот четырехбайтная последовательность в шестнадцатеричном формате, которая дает ноль: ab 9b e0 9b. Фактически, это единственная четырехбайтовая последовательность, которая может это сделать. Нет трехбайтовых или более коротких последовательностей, которые дадут вам нуль. Именно здесь @Yanek не совсем прав, поскольку для трехбайтовых или более коротких последовательностей нуль не так вероятен. Вероятность получения нуля равна нулю в этих случаях.

+0

Для 3 байтовых входов имеется около 256 выходов, которые имеют нулевую вероятность. Насколько я могу сказать. – usr

+2

Должно быть больше _lot_. Есть только 2^24 возможных 3-байтовых входа, поэтому должно быть 2^32-2^24 == 4 278 190 080 выходов с вероятностью 0. Остальные имеют вероятность 2^-24. –

+0

Правильно, я по ошибке разделил числа вместо вычитания. – usr

0

Как об этом, а не 32-битный CRC, хотя:

1011 | 110011001010.000 
     1011 
     ---- 
     1111 
     1011 
     ---- 
     1001 
     1011 
     ---- 
      1000 
      1011 
      ---- 
      1110 
      1011 
      ---- 
       1011 
       1011 
       ---- 
        0000 (...) 
        1011 
        ---- 
        1011 
        1011 
        ---- 
        0000 

Или:

1100 | 11001010.000 
     1100 
     ---- 
      1010 
      1100 
      ---- 
      1100 
      1100 
      ---- 
      (...) 0 

 Смежные вопросы

  • Нет связанных вопросов^_^