-
-
Save Sam-Belliveau/72ba4a8710324ce7a1ac1789d64ec831 to your computer and use it in GitHub Desktop.
/** | |
* Copyright 2019 Sam Robert Belliveau | |
* | |
* Permission is hereby granted, free of charge, to any person | |
* obtaining a copy of this software and associated documentation | |
* files (the "Software"), to deal in the Software without restriction, | |
* including without limitation the rights to use, copy, modify, merge, | |
* publish, distribute, sublicense, and/or sell copies of the Software, | |
* and to permit persons to whom the Software is furnished to do so, | |
* subject to the following conditions: | |
* | |
* The above copyright notice and this permission notice shall | |
* be included in all copies or substantial portions of the Software. | |
* | |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | |
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES | |
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. | |
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY | |
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, | |
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE | |
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |
*/ | |
#ifndef SAM_BELLIVEAUS_CRC_IMPLEMENTATION_HPP | |
#define SAM_BELLIVEAUS_CRC_IMPLEMENTATION_HPP 1 | |
#include <type_traits> // get information about type | |
#include <iterator> // Iterator traits | |
#include <cstdint> // fixed width ints | |
#include <utility> // SFINAE | |
namespace crc | |
{ | |
// Underlying types for calculations | |
using byte = std::uint8_t; | |
using u8 = std::uint8_t; | |
using u16 = std::uint16_t; | |
using u32 = std::uint32_t; | |
using u64 = std::uint64_t; | |
using size = std::size_t; | |
// Takes a function and precalculates all | |
// of the possible 8-bit inputs for it | |
template<class Generator> | |
class MemTable | |
{ | |
public: | |
// type in which the MemTable takes inpus | |
using input_type = const byte; | |
// max value for MemTable | |
static constexpr size max = 0x100; | |
// get return type of generator | |
using return_type = typename std::result_of<Generator(const byte)>::type; | |
private: | |
// store PolyTable | |
return_type table_[max]; | |
public: | |
// generate PolyTable | |
constexpr MemTable() noexcept | |
{ | |
Generator gen; | |
for(size i = 0; i < max; ++i) | |
{ table_[i] = gen(i); } | |
} | |
// access mem_array | |
constexpr return_type operator()(input_type index) const noexcept | |
{ return table_[index]; } | |
}; | |
// Takes return type and polynomial | |
// and makes a crc PolyTable generator | |
template<class ReturnType, ReturnType Polynomial> | |
struct CRCTableGenerator | |
{ | |
constexpr CRCTableGenerator() noexcept {} | |
constexpr ReturnType operator()(const byte index) const noexcept | |
{ | |
ReturnType out = index; | |
for(size bit = 0; bit < 8; ++bit) | |
out = (out >> 1) ^ ((out & 1) ? (Polynomial) : (0)); | |
return out; | |
} | |
}; | |
// CRCEngine that takes in a | |
// polynomial generator as a template | |
template<class MTable> | |
class CRCBaseEngine | |
{ | |
public: | |
using size_type = size; | |
using return_type = typename MTable::return_type; | |
private: // Create Memorization Table | |
static constexpr MTable PolyTable = MTable(); | |
static constexpr return_type InitState = 0; | |
static constexpr return_type FinalXOR = 0; | |
private: | |
// Add Single Byte | |
template<class T, std::enable_if_t<(sizeof(T) == 1), int> Size = 1> | |
static constexpr inline return_type AddData(const return_type state, const T data) | |
{ return (state >> 8) ^ PolyTable(static_cast<byte>(state ^ data)); } | |
// Add Integer | |
template< | |
class T, std::enable_if_t< | |
(sizeof(T) > 1) && std::is_integral<T>::value, | |
int> Size = sizeof(T) | |
> static constexpr inline return_type AddData(return_type state, const T data) | |
{ | |
state = AddData(state, static_cast<byte>(data & static_cast<T>(0xff))); | |
for(int i = 1; i < Size; ++i) | |
{ | |
data >>= 8; | |
state = AddData(state, static_cast<byte>(data & static_cast<T>(0xff))); | |
} | |
return state; | |
} | |
// Add Range Type | |
template<class T, class BT = decltype(std::cbegin(T())), class ET = decltype(std::cend(T()))> | |
static constexpr inline return_type AddData(const return_type state, const T& data) | |
{ return AddDataArray(state, std::cbegin(data), std::cend(data)); } | |
// Add C String | |
static inline return_type AddData(const return_type state, const char* str) | |
{ | |
// Look for null pointer | |
const char* end = str; | |
for(; *end != '\0'; ++end) {} | |
return AddDataArray(state, str, end); | |
} | |
// Add Multiple Data Types | |
// This allows for the hash to recursively hash stuff | |
template<class Iterator> | |
static constexpr inline return_type AddDataArray(return_type state, Iterator begin, const Iterator end) | |
{ | |
for(; begin < end; ++begin) | |
{ state = AddData(state, *begin); } | |
return state; | |
} | |
private: | |
// Finalize State | |
static constexpr inline return_type Finalize(return_type state) | |
{ return FinalXOR ^ state; } | |
public: // Static Hashing Methods | |
// Compute hash on fundamental type | |
template<class T> | |
constexpr return_type operator()(const T& data) const noexcept | |
{ return Finalize(AddData(InitState, data)); } | |
// Compute Hash on generic types | |
template<class Iterator> // (begin, end) | |
constexpr return_type operator()(const Iterator begin, const Iterator end) const noexcept | |
{ return Finalize(AddDataArray(InitState, begin, end)); } | |
template<class Iterator> // (begin, size) | |
constexpr return_type operator()(const Iterator data, const size_type size) const noexcept | |
{ return Finalize(AddDataArray(InitState, data, data + size)); } | |
}; | |
// Initialize static MemTable outside of class | |
template<class MTable> | |
constexpr MTable CRCBaseEngine<MTable>::PolyTable; | |
// Makes CRCBaseEngine with Generator instead of MemTable | |
template<class Generator> | |
using CRCBaseEngineMem = CRCBaseEngine<MemTable<Generator>>; | |
// Makes CRCBaseEngine with ReturnType and Polynomial | |
template<class ReturnType, ReturnType Polynomial> | |
using CRCBase = CRCBaseEngineMem<CRCTableGenerator<ReturnType, Polynomial>>; | |
// CRC Bases for each CRC Type | |
template<u8 Polynomial> | |
using CRC8Base = CRCBase<u8, Polynomial>; | |
template<u16 Polynomial> | |
using CRC16Base = CRCBase<u16, Polynomial>; | |
template<u32 Polynomial> | |
using CRC32Base = CRCBase<u32, Polynomial>; | |
template<u64 Polynomial> | |
using CRC64Base = CRCBase<u64, Polynomial>; | |
// CRC Engines with Polynomials | |
// The Polynomials from | |
// https://en.wikipedia.org/wiki/Cyclic_redundancy_check | |
using CRC8 = CRC8Base<0xE5>; // CRC-8-Bluetooth | |
using CRC16 = CRC16Base<0x8408>; // CRC-16-CCITT | |
using CRC32 = CRC32Base<0xEDB88320>; // CRC-32 | |
using CRC32C = CRC32Base<0x82F63B78>; // CRC-32C (Castagnoli) | |
using CRC32K = CRC32Base<0xEB31D82E>; // CRC-32K (Koopman) | |
using CRC32K2 = CRC32Base<0x992C1A4C>; // CRC-32K2 (Koopman) | |
using CRC64 = CRC64Base<0xC96C5795D7870F42>; // CRC-64-ECMA | |
} | |
#endif // SAM_BELLIVEAUS_CRC_IMPLEMENTATION_HPP |
What is AddTypes? There are no definition for such function
It seems to have been a typo from the old code. I'm not sure why I don't get compile-time errors from it? It's fixed now.
Nice idea! I would like to use this. Have you tested it?
It would be great to see an example of an instantiated algorithm with the options changed, e.g. InitState and FinalXor
As @clythersHackers stated, I also required a version where InitState
and FinalXor
are different from 0. (mainly for the CRC-32K Koopman. I hope to see an improved version of this in the future, thanks anyway for this gist 💯
In the meantime I've updated it myself (forked gist for c++17) as follow:
I removed the private static variables InitState
and FinalXor
, and added them as optional parameters to the AddData* functions:
// Compute hash on fundamental type
template<class T>
constexpr return_type operator()(const T& data, const return_type& initState = static_cast<return_type>(0), const return_type& finalXOR = static_cast<return_type>(0)) const noexcept
{
return Finalize(AddData(initState, data), finalXOR);
}
// Compute Hash on generic types
template<class Iterator> // (begin, end)
constexpr return_type operator()(const Iterator begin, const Iterator end, const return_type& initState = static_cast<return_type>(0), const return_type& finalXOR = static_cast<return_type>(0)) const noexcept
{
return Finalize(AddDataArray(initState, begin, end), finalXOR);
}
template<class Iterator> // (begin, size)
constexpr return_type operator()(const Iterator data, const size_type size, const return_type& initState = static_cast<return_type>(0), const return_type& finalXOR = static_cast<return_type>(0)) const noexcept
{
return Finalize(AddDataArray(initState, data, data + size), finalXOR);
}
In order to account for this, I had to change the signature of the Finalize
function too:
// Finalize State
static constexpr inline return_type Finalize(return_type state, return_type finalXOR)
{
return finalXOR ^ state;
}
Very usefull snippet!
I have also (see my fork)
- Added usage examples (in the end of snippet)
- Added parameter pack support, so now you can call
crc64("str", 1, <whatever>, ...)
constexpr return_type operator()(const Iterator begin, const Iterator end)
replaced withconstexpr return_type array(const Iterator begin, const Iterator end)
What is AddTypes? There are no definition for such function