Универсальный подход для расчета CRC
Всем привет. Решил написать свою небольшую header-only библиотечку для расчета Cyclic Redundancy Code с использованием С++17. Все работает как часы, за исключением одного:
Каждая спецификация хэш-суммы CRC имеет такие отличительные черты, как параметры refIn и refOut, связанные с отражением байтов/битов или чего-то - я так и не понял. В абсолютном большинстве случаев, их значения эквивалентны друг другу (оба или true, или false), поэтому я решил сделать для них одну переменную bool вместо двух.
В своем коде я использовал шаблоны ради статического полиморфизма, дабы не плодить кучу наследников, и лишнего кода в вообще. Все базовые полиномы были взяты в Википедии, а алгоритм расчета самого CRC я откопал на Хабре. Код библиотеки представлен ниже.
Изначально в константы зашиты нормальные (не зеркаленные) базовые полиномы. Когда ref равен true я тупо зеркалю базовый полином 0x04C11D7, и уже с отзеркаленным полиномом (0хEDB88320) строю таблицу, и произвожу с нею необходимые вычисления. Но как только ref равен false, я упираюсь в тупик. Что я только не пробовал, я не могу получить необходимый результат, который я проверяю в онлайн-калькуляторе CRC - crccalc.com.
Получается проблема, в которой корректные вычисления хэшей получаются только для тех спецификаций CRC, где ref равен true. Для той же BZIP2 (ref == false) я уже не могу ничего подсчитать. И да, код тестировался пока только для 32-хбитных CRC, по другим пока не гонял.
Вопрос к Вам, уважаемые друзья. На каком этапе мне нужно изменить вычисляемое значение, и что именно нужно поменять, чтобы представленный код работал универсально с минимальными изменениями, для спецификаций с ref как true, так и false?
Код:
#pragma once
#include <type_traits>
#include <stdint.h>
#include <array>
#include <string>
namespace Crc
{
/*Template function for mirror bits of the integral values-----
*/
template<typename IntT>
inline IntT mirrorIntegerBits(const IntT& value)
{
static_assert(std::is_integral_v<IntT>, "IntT is not an integral type");
uint32_t _x = (uint32_t)value;
_x = (_x & 0x55555555) << 1 | (_x & 0xAAAAAAAA) >> 1;
_x = (_x & 0x33333333) << 2 | (_x & 0xCCCCCCCC) >> 2;
_x = (_x & 0x0F0F0F0F) << 4 | (_x & 0xF0F0F0F0) >> 4;
_x = (_x & 0x00FF00FF) << 8 | (_x & 0xFF00FF00) >> 8;
_x = (_x & 0x0000FFFF) << 16 | (_x & 0xFFFF0000) >> 16;
return (IntT)_x >> ((4 - sizeof(IntT)) * 8);
}
/*Template function for mirror bytes in integral values (0xAABBCCDD -> 0xDDCCBBAA)-----
*/
template<typename IntT>
inline IntT reverseBytes(IntT src)
{
static_assert(std::is_integral_v<IntT>, "IntT is not an integral type");
IntT _result = 0x0;
uint8_t _elem = 0x0;
size_t _cnt = sizeof(IntT);
while(_cnt)
{
_elem = src >> (sizeof(IntT) * 8 - (_cnt * 8));
_result = _result << 8 | _elem;
--_cnt;
}
return _result;
}
/*CRC specification ID-----
*
* Provide number of specification version for compile-time check
*/
template<uint8_t id>
struct SpecID { static constexpr uint8_t value = id; };
/* CRC traits structure-----
*
* Provide information about polynomial and other variadic values for every CRC specification
* */
template<class id, uint32_t _poly, uint32_t _init, uint32_t _xor, bool _ref>
struct Traits
{
constexpr inline Traits()
{
static_assert(std::is_same_v<id, SpecID>, "class 'id' isn't SpecID");
}
static constexpr uint8_t specID = id::value;
static constexpr uint32_t polynome = _poly;
static constexpr uint32_t initValue = _init;
static constexpr uint32_t xorOut = _xor;
static constexpr bool ref = _ref;
};
/*CRC polynomial table-----
* */
template<class TraitT, typename CrcInt, size_t size = 256>
class Table
{
public:
inline Table() : m_polynome((CrcInt)TraitT::polynome)
{
static_assert(std::is_integral_v<CrcInt>, "CrcInt isn't an integral type");
m_table.fill(0);
if (TraitT::ref) m_polynome = mirrorIntegerBits(m_polynome);
calculateTable();
}
inline CrcInt getValueFor(CrcInt value) { return m_table[value]; }
private:
// polynomial calculating for current cell
inline CrcInt calculatePolynome(CrcInt value) { return (CrcInt)value & 1 ? (value >> 1) ^ m_polynome : value >> 1; }
inline void calculateTable()
{
CrcInt _cell = 0;
for(size_t i = 0; i < size; ++i)
{
_cell = i;
for (size_t bitIdx = 0; bitIdx < 8; ++bitIdx)
_cell = calculatePolynome(_cell);
m_table[i] = _cell;
}
}
CrcInt m_polynome;
std::array<CrcInt, size> m_table;
};
/*Cyclic Redundancy Code (CRC) computer-----
*
* Provide CRC-hash of specified string value for concrete CRC-specification algorythm
* */
template<class Spec, class TraitT, class ComputeMethod, typename CrcInt>
class Computer
{
public:
inline Computer(std::string_view source) : m_value(0x0)
{
static_assert(Spec::value == TraitT::specID, "invalid CRC specification");
static_assert(std::is_same_v<Table<TraitT, CrcInt>, ComputeMethod>, "invalid compute method");
calculate(source.data(), source.size());
}
~Computer() = default;
inline CrcInt value() const { return m_value; }
inline std::string toString() const
{
char _buf[12];
sprintf(_buf, "%X", m_value);
return std::string(_buf);
}
private:
inline void calculate(const char* buf, size_t len)
{
m_value = TraitT::initValue;
while(len--)
{
size_t index = (m_value >> 24 ^ *buf++) & 0xFF;
m_value >>= 8;
m_value ^= m_method.getValueFor(index);
}
m_value ^= TraitT::xorOut;
}
ComputeMethod m_method;
CrcInt m_value;
};
}
/*CRC specification aliases-----
*/
/*CRC-32 specifications:*/
using Crc32_IEEE = Crc::Traits<Crc::SpecID<32>, 0x4C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true>;
using Crc32_BZIP2 = Crc::Traits<Crc::SpecID<32>, 0x4C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, false>;
using Crc32_C = Crc::Traits<Crc::SpecID<32>, 0x1EDC6F41, 0xFFFFFFFF, 0xFFFFFFFF, true>;
using Crc32_D = Crc::Traits<Crc::SpecID<32>, 0xA833982B, 0xFFFFFFFF, 0xFFFFFFFF, true>;
using Crc32_JAMCRC = Crc::Traits<Crc::SpecID<32>, 0x4C11DB7, 0xFFFFFFFF, 0x0, true>;
using Crc32_MPEG2 = Crc::Traits<Crc::SpecID<32>, 0x4C11DB7, 0xFFFFFFFF, 0x0, false>;
using Crc32_POSIX = Crc::Traits<Crc::SpecID<32>, 0x4C11DB7, 0x0, 0xFFFFFFFF, false>;
using Crc32_Q = Crc::Traits<Crc::SpecID<32>, 0x814141AB, 0x0, 0x0, false>;
using Crc32_XFER = Crc::Traits<Crc::SpecID<32>, 0xAF, 0x0, 0x0, false>;
/*CRC-hash computers aliases-----
* */
template<class TraitT>
using Crc32 = Crc::Computer<Crc::SpecID<32>, TraitT, Crc::Table<TraitT, uint32_t>, uint32_t>;
Конечное использование:
Crc32<Crc32_IEEE> hash("Hello World!"); // instance for CRC-32/IEEE 802.3
std::cout << hash.value() << std::endl; // sink for integral value
std::cout << hash.toString().data() << std::endl; // sink for string value (std::string)