Гарантирован ли CRC-32 генерировать 4 миллиарда уникальных значений? - PullRequest
Новая
       41

Гарантирован ли CRC-32 генерировать 4 миллиарда уникальных значений?

0 голосов
/ 25 июня 2019

Я просто хочу знать, для хэш-функции CRC32, в частности для PHP crc, получу ли я 2 ^ 32 (4 миллиарда) различных значений для входного значения (целое число), которое гарантированно будет последовательно увеличиваться от 1до 4 миллиардов?

Ответы [ 2 ]

1 голос
/ 25 июня 2019

Я не думаю, что CRC32 был специально разработан, чтобы не было коллизий для всех возможных четырехбайтовых входов.Тем не менее, похоже, что это работает.Вы можете проверить это самостоятельно, просто проверив все возможные результаты.Чтобы ускорить процесс, я использовал следующую программу на C: 

/* Compile: cc crc_check.c -O3 -lz -o crc_check */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <zlib.h>

int main() {
    uint32_t x, y, d;
    uint64_t i, *seen, mask;

    seen = calloc(0x4000000, 8);
    if (!seen) return -1;

    /* Make sure we're calculating the same values as PHP's crc32 function */
    printf("crc32(\"ABCD\") = %lu\n", crc32(0, (unsigned char*)"ABCD", 4));

    for (i=x=0; i<0x100000000ULL; i++) {
        y = crc32(0, (unsigned char*)(&x), 4);
        mask = 1ULL << (y & 0x003fULL);
        d = y >> 6;
        if (seen[d] & mask) {
            printf("Collision detected (x=%u, y=%u)\n", x, y);
            return 0;
        }
        seen[d] |= mask;
        x++;
    }
    puts("No collisions detected");
    return 0;
}

/*
   Output:
   crc32("ABCD") = 3675725989
   No collisions detected
*/

Чтобы убедиться, что zlib использует ту же функцию, я добавил строку для вывода контрольной суммы CRC32 строки "ABCD".PHP выдает то же значение: 

$ php -r 'echo crc32("ABCD");'
3675725989

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

0 голосов
/ 03 июля 2019

CRC делает плохие хеш-функции.Вот отличная краткая статья на эту тему: https://eklitzke.org/crcs-vs-hash-functions

...