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

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

0 голосов
/ 20 декабря 2018

Проблема

Я пытаюсь реализовать хеш-функцию для простой хеш-таблицы, используя инструкцию 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 flag -msse4.2

1 Ответ

0 голосов
/ 20 декабря 2018

Я думаю, вы неправильно понимаете, как работают эти функции.Предполагается, что они будут вызываться последовательно для каждого символа в строке, для которой необходимо рассчитать 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;
}
...