Использование алгоритма CRC32 для хеширования строки во время компиляции

Вот решение, которое полностью работает во время компиляции, но также может использоваться во время выполнения. Это смесь constexpr, шаблонов и макросов. Вы можете изменить некоторые имена или поместить их в отдельный файл, поскольку они довольно короткие.

Обратите внимание, что я повторно использовал код из этого ответа для создания таблицы CRC, и я основывался на коде из эту страницу для реализации.

Я не тестировал его на MSVC, так как в настоящее время он не установлен в моей виртуальной машине Windows, но я считаю, что он должен работать или, по крайней мере, работать с тривиальными изменениями.

Вот код, вы можете использовать функцию crc32 напрямую или функцию WSID, которая более точно соответствует вашему вопросу:

#include <cstring>
#include <cstdint>
#include <iostream>

// Generate CRC lookup table
template <unsigned c, int k = 8>
struct f : f<((c & 1) ? 0xedb88320 : 0) ^ (c >> 1), k - 1> {};
template <unsigned c> struct f<c, 0>{enum {value = c};};

#define A(x) B(x) B(x + 128)
#define B(x) C(x) C(x +  64)
#define C(x) D(x) D(x +  32)
#define D(x) E(x) E(x +  16)
#define E(x) F(x) F(x +   8)
#define F(x) G(x) G(x +   4)
#define G(x) H(x) H(x +   2)
#define H(x) I(x) I(x +   1)
#define I(x) f<x>::value ,

constexpr unsigned crc_table[] = { A(0) };

// Constexpr implementation and helpers
constexpr uint32_t crc32_impl(const uint8_t* p, size_t len, uint32_t crc) {
    return len ?
            crc32_impl(p+1,len-1,(crc>>8)^crc_table[(crc&0xFF)^*p])
            : crc;
}

constexpr uint32_t crc32(const uint8_t* data, size_t length) {
    return ~crc32_impl(data, length, ~0);
}

constexpr size_t strlen_c(const char* str) {
    return *str ? 1+strlen_c(str+1) : 0;
}

constexpr int WSID(const char* str) {
    return crc32((uint8_t*)str, strlen_c(str));
}

// Example usage
using namespace std;

int main() {
    cout << "The CRC32 is: " << hex << WSID("some-id") << endl;
}

Первая часть заботится о создании таблицы констант, а crc32_impl - это стандартная реализация CRC32, преобразованная в рекурсивный стиль, который работает с constexpr C ++ 11. Тогда crc32 и WSID - просто простые оболочки для удобства.

Если кому-то интересно, я закодировал функцию генератора таблиц CRC-32 и функцию генератора кода, используя функции constexpr в стиле C ++ 14. В результате, на мой взгляд, получается гораздо более обслуживаемый код, чем многие другие попытки, которые я видел в Интернете, и он находится далеко-далеко от препроцессора.

Теперь он использует специальный std :: array 'clone', называемый cexp :: array, потому что G ++, похоже, не добавил ключевое слово constexpr к своему оператору доступа / записи неконстантного ссылочного индекса.

Однако он довольно легкий, и, надеюсь, ключевое слово будет добавлено в std :: array в ближайшем будущем. Но пока очень простая реализация массива выглядит следующим образом:

namespace cexp
{

    // Small implementation of std::array, needed until constexpr
    // is added to the function 'reference operator[](size_type)'
    template <typename T, std::size_t N>
    struct array {
        T m_data[N];

        using value_type = T;
        using reference = value_type &;
        using const_reference = const value_type &;
        using size_type = std::size_t;

        // This is NOT constexpr in std::array until C++17
        constexpr reference operator[](size_type i) noexcept {
            return m_data[i];
        }

        constexpr const_reference operator[](size_type i) const noexcept {
            return m_data[i];
        }

        constexpr size_type size() const noexcept {
            return N;
        }
    };

}

Теперь нам нужно сгенерировать таблицу CRC-32. Я основал алгоритм на некотором коде Hacker's Delight, и его, вероятно, можно расширить для поддержки многих других алгоритмов CRC. Но, увы, мне потребовалась только стандартная реализация, так что вот она:

// Generates CRC-32 table, algorithm based from this link:
// http://www.hackersdelight.org/hdcodetxt/crc.c.txt
constexpr auto gen_crc32_table() {
    constexpr auto num_bytes = 256;
    constexpr auto num_iterations = 8;
    constexpr auto polynomial = 0xEDB88320;

    auto crc32_table = cexp::array<uint32_t, num_bytes>{};

    for (auto byte = 0u; byte < num_bytes; ++byte) {
        auto crc = byte;

        for (auto i = 0; i < num_iterations; ++i) {
            auto mask = -(crc & 1);
            crc = (crc >> 1) ^ (polynomial & mask);
        }

        crc32_table[byte] = crc;
    }

    return crc32_table;
}

Затем мы сохраняем таблицу в глобале и выполняем элементарную статическую проверку. Скорее всего, эту проверку можно улучшить, и нет необходимости хранить ее в глобальном.

// Stores CRC-32 table and softly validates it.
static constexpr auto crc32_table = gen_crc32_table();
static_assert(
    crc32_table.size() == 256 &&
    crc32_table[1] == 0x77073096 &&
    crc32_table[255] == 0x2D02EF8D,
    "gen_crc32_table generated unexpected result."
);

Теперь, когда таблица сгенерирована, пора сгенерировать коды CRC-32. Я снова основал алгоритм на ссылке Hacker's Delight, и на данный момент он поддерживает только ввод из c-строки.

// Generates CRC-32 code from null-terminated, c-string,
// algorithm based from this link:
// http://www.hackersdelight.org/hdcodetxt/crc.c.txt 
constexpr auto crc32(const char *in) {
    auto crc = 0xFFFFFFFFu;

    for (auto i = 0u; auto c = in[i]; ++i) {
        crc = crc32_table[(crc ^ c) & 0xFF] ^ (crc >> 8);
    }

    return ~crc;
}

Для завершения я генерирую один код CRC-32 ниже и статически проверяю, имеет ли он ожидаемый результат, а затем распечатываю его в поток вывода.

int main() {
    constexpr auto crc_code = crc32("some-id");
    static_assert(crc_code == 0x1A61BC96, "crc32 generated unexpected result.");

    std::cout << std::hex << crc_code << std::endl;
}

Надеюсь, это поможет всем, кто хотел добиться генерации CRC-32 во время компиляции или даже в целом.

Ответ @ tux3 довольно приятный! Однако сложно поддерживать, потому что вы в основном пишете свою собственную реализацию CRC32 в командах препроцессора.

Другой способ решить ваш вопрос - сначала вернуться и понять необходимость требования. Если я вас правильно понимаю, похоже, дело в производительности. В этом случае есть второй момент времени, когда вы можете вызвать свою функцию без ущерба для производительности: во время загрузки программы. В этом случае вы будете обращаться к глобальной переменной вместо передачи константы. С точки зрения производительности, после инициализации оба должны быть идентичными (const извлекает 32 бита из вашего кода, глобальная переменная извлекает 32 бита из обычного места в памяти).

Вы можете сделать что-то вроде этого:

static int myWSID = 0;

// don't call this directly
static int WSID(const char* str) {
  boost::crc_32_type result;
  result.process_bytes(str,sizeof(str));
  return result.checksum();
}

// Put this early into your program into the
// initialization code.
...
myWSID = WSID('some-id');

В зависимости от вашей общей программы вам может потребоваться встроенный метод доступа для извлечения значения.

Если незначительное влияние на производительность допустимо, вы также должны написать свою функцию таким образом, в основном используя шаблон singleton.

// don't call this directly
int WSID(const char* str) {
  boost::crc_32_type result;
  result.process_bytes(str,sizeof(str));
  return result.checksum();
}

// call this instead. Note the hard-coded ID string.
// Create one such function for each ID you need to
// have available.
static int myWSID() {
   // Note: not thread safe!
   static int computedId = 0;
   if (computedId == 0)
      computedId = WSID('some-id');
   return computedId;
}

Конечно, если причиной запроса оценки времени компиляции является нечто иное (например, нежелание появления некоторого идентификатора в скомпилированном коде), эти методы не помогут.

Другой вариант - использовать предложение Джейсона Грегори о настраиваемом препроцессоре. Это можно сделать довольно чисто, если собрать все IDS в отдельный файл. Этот файл не обязательно должен иметь синтаксис C. Я бы дал ему расширение, например .wsid. Пользовательский препроцессор генерирует из него файл .H.

Вот как это могло выглядеть:

idcollection.wsid (перед пользовательским препроцессором):

some_id1
some_id2
some_id3

Ваш препроцессор сгенерирует следующий idcollection.h:

#define WSID_some_id1 0xabcdef12
#define WSID_some_id2 0xbcdef123
#define WSID_some_id3 0xcdef1234

И в своем коде вы бы назвали

Engine.getById(WSID_some_id1);

Несколько замечаний по этому поводу:

• Это предполагает, что все исходные идентификаторы могут быть преобразованы в действительные идентификаторы. Если они содержат специальные символы, вашему препроцессору может потребоваться дополнительная настройка.
• Я заметил несоответствие в вашем исходном вопросе. Ваша функция возвращает int, но Engine.getById, похоже, принимает строку. Предлагаемый мной код всегда будет использовать int (легко изменить, если вы хотите всегда строку).