Как реализовать хеш-функцию для строк в C, используя инструкцию CRC32C из расширения xse4.2 x86?

Question

проблема

Я пытаюсь реализовать хеш-функцию для простой хеш-таблицы, используя инструкцию crc32c в расширении sse4.2 x86. Однако я не очень доволен этими проблемами, поэтому у меня есть некоторые проблемы.

Я посмотрел, что есть функция unsigned int _mm_crc32_u8 (unsigned int crc, unsigned char v) (источник: https://software.intel.com/sites/landingpage/IntrinsicsGuide/#techs=SSE4_2&expand=1283), который принимает неподписанный символ и возвращает хэш. Согласно моему пониманию crc переменная предназначена для проверки ошибок для начальных битов, которые меня не касаются (я могу установить 0 или 0xffffffff и не заботиться об этом).

Однако у меня есть строка char *s и хочу вычислить хэш этого.

Вопросы

(в порядке важности)

1. Как пользоваться _mm_crc32_u8 хешировать всю строку? Должен ли я хэшировать все символы в s отдельно и поразрядно XOR результаты? Я действительно понятия не имею.
2. Функция _mm_crc32_u8 принимает неподписанные символы Разве это нормально, просто бросить неподписанный символ на символ, чтобы преобразовать его как (unsigned char)s[0] в данном контексте? Насколько я знаю, это потому, что символы ASCII имеют только значения от 0 до 127, поэтому они не переполняются в процессе приведения.
3. Есть также функции на нескольких байтах (_mm_crc32_u{16,32,64}), возможно, мне следует использовать их для лучшей производительности, поскольку они могут хэшировать до 4 байтов одновременно?

подробности

#include <nmmintrin.h> обеспечивает функции выше. Я собираю это с clang флаг -msse4.2

Answer 1

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

Но идея остается той же: сначала вы инициализируете CRC в 0, затем вызываете функцию CRC в цикле, давая предыдущее значение CRC в первом аргументе и хеширующее значение во втором. Вы сохраняете результат в CRC и сохраняете спокойствие и продолжаете.

Вот пример кода:

uint64_t byte_crc32(unsigned int crc, const char** buf, size_t len) {
    while (len > 0) {
        crc = _mm_crc32_u8(crc, *(const unsigned char*)(*buf));
        ++*buf;
        --len;
    }

    return crc;
}

uint64_t hw_crc32(unsigned int crc, const char** buf, size_t len) {
    while (len > 0) {
        crc = _mm_crc32_u16(crc, *(const uint16_t*)(*buf));
        *buf += 2;
        --len;
    }

    return crc;
}

uint64_t word_crc32(unsigned int crc, const char** buf, size_t len) {
    while (len > 0) {
        crc = _mm_crc32_u32(crc, *(const uint32_t*)(*buf));
        *buf += 4;
        --len;
    }

    return crc;
}

uint64_t dword_crc32(uint64_t crc, const char** buf, size_t len) {
    while (len > 0) {
        crc = _mm_crc32_u64(crc, *(const uint64_t*)(*buf));
        *buf += 8;
        --len;
    }

    return crc;
}


uint64_t crc(const char* buff, size_t len) {

    const size_t dword_chunks = len / 8;
    const size_t dword_diff = len % 8;

    const size_t word_chunks = dword_diff / 4;
    const size_t word_diff = dword_diff % 4;

    const size_t hw_chunks = word_diff / 2;
    const size_t hw_diff = word_diff % 2;

    uint64_t crc = byte_crc32(0, &buff, hw_diff);
    crc = hw_crc32(crc, &buff, hw_chunks);
    crc = word_crc32(crc, &buff, word_chunks);
    crc = dword_crc32(crc, &buff, dword_chunks);

    return crc;
}