Created
May 7, 2017 14:24
-
-
Save nlyan/d7adaca49140a39dc255e2dbfa57d674 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <type_traits> | |
#include <algorithm> | |
#include <iterator> | |
#include <stdexcept> | |
#include <cassert> | |
#include <cstring> | |
#include <endian.h> | |
// TODO: Add 2 byte, 4 byte read_le | |
// Check everything works with other word sizes. | |
// Resetable SipHash class? | |
unsigned flange = 0; | |
namespace { | |
template <typename T> inline | |
typename std::enable_if<std::is_same<T, unsigned char>::value, unsigned char>::type | |
to_u8 (T x) { | |
return x; | |
} | |
template <typename T> inline | |
typename std::enable_if<std::is_same<T, char>::value, unsigned char>::type | |
to_u8 (T x) { | |
return *(reinterpret_cast<unsigned char*>(&x)); | |
} | |
template <typename InputIterator> inline | |
typename std::enable_if< | |
std::is_same <typename std::iterator_traits<InputIterator>::value_type, | |
char>::value || | |
std::is_same <typename std::iterator_traits<InputIterator>::value_type, | |
unsigned char>::value, | |
InputIterator | |
>::type | |
read_le (InputIterator in, uint64_t* x) { | |
auto out = reinterpret_cast<unsigned char*>(x); | |
*out++ = to_u8 (*in++); // 1 | |
*out++ = to_u8 (*in++); // 2 | |
*out++ = to_u8 (*in++); // 3 | |
*out++ = to_u8 (*in++); // 4 | |
*out++ = to_u8 (*in++); // 5 | |
*out++ = to_u8 (*in++); // 6 | |
*out++ = to_u8 (*in++); // 7 | |
*out++ = to_u8 (*in++); // 8 | |
*x = le64toh (*x); | |
return std::move (in); | |
} | |
template <typename InputIterator> inline | |
typename std::enable_if< | |
std::is_same <typename std::iterator_traits<InputIterator>::value_type, | |
char>::value || | |
std::is_same <typename std::iterator_traits<InputIterator>::value_type, | |
unsigned char>::value, | |
InputIterator | |
>::type | |
read_le (InputIterator in, std::size_t n, uint64_t* x) { | |
/*while (n > sizeof(x)) { | |
in = read_le (in, x); | |
n -= sizeof(x); | |
++x; | |
}*/ | |
*x = 0; | |
assert (n <= sizeof(x)); | |
auto out = reinterpret_cast<unsigned char*>(x); | |
while (n) { | |
*out++ = to_u8 (*in++); | |
--n; | |
} | |
*x = le64toh (*x); | |
return std::move (in); | |
} | |
template <typename T> inline | |
typename std::enable_if< | |
std::is_same<T, char>::value || std::is_same<T, unsigned char>::value, | |
T* | |
>::type | |
read_le (T* in, std::size_t const n, uint64_t* out) { | |
*out = 0; | |
assert (n <= sizeof(*out)); | |
std::memcpy (out, in, n); | |
*out = le64toh (*out); | |
return (in + n); | |
} | |
template <typename T> inline | |
typename std::enable_if< | |
std::is_same<T, char>::value || std::is_same<T, unsigned char>::value, | |
T* | |
>::type | |
read_le (T* in, uint64_t* out) { | |
std::memcpy (out, in, sizeof(*out)); | |
*out = le64toh (*out); | |
return (in + sizeof(*out)); | |
} | |
template <unsigned N> inline | |
void | |
rotate_left (uint64_t& x) { | |
x = ((x << N) | (x >> (64 - N))); | |
} | |
} | |
namespace cppnews { | |
template <unsigned C, unsigned D> | |
class SipHash { | |
public: | |
//SipHash() = default; | |
template <typename Key> | |
explicit SipHash (Key const& key); | |
template <typename Key> | |
void reset (Key const& key); | |
template <typename InputIterator> | |
void update (InputIterator msg, std::size_t size); | |
// template <typename InputIterator> | |
// void update (InputIterator begin, InputIterator end); | |
template <typename... Args> | |
void final (Args&&...); | |
template <typename... Args> | |
uint64_t operator()(Args&&...); | |
// template <typename Key, typename... Args> | |
// uint64_t operator()(Key const&, Args&&...); | |
void inject (uint64_t); | |
void finalize(); | |
uint64_t value() const; | |
private: | |
void do_round(); | |
private: | |
uint64_t v0; | |
uint64_t v1; | |
uint64_t v2; | |
uint64_t v3; | |
uint64_t padding; | |
}; | |
template <unsigned C, unsigned D> | |
template <typename Key> inline | |
SipHash<C,D>::SipHash (Key const& key) { | |
reset(key); | |
} | |
template <unsigned C, unsigned D> | |
template <typename Key> | |
void | |
SipHash<C,D>::reset (Key const& key) { | |
using std::begin; | |
uint64_t k0; | |
uint64_t k1; | |
auto kit = read_le (begin(key), &k0); | |
kit = read_le (kit, &k1); | |
v0 = k0 ^ 0x736F6D6570736575ull; // "somepseu" | |
v1 = k1 ^ 0x646F72616E646F6Dull; // "dorandom" | |
v2 = k0 ^ 0x6C7967656E657261ull; // "lygenera" | |
v3 = k1 ^ 0x7465646279746573ull; // "tedbytes" | |
padding = 0; | |
} | |
template <unsigned C, unsigned D> | |
void | |
SipHash<C,D>::inject (uint64_t const m) { | |
v3 ^= m; | |
for (auto i = 0; i < C; ++i) { | |
do_round(); | |
} | |
v0 ^= m; | |
} | |
template <unsigned C, unsigned D> | |
template <typename InputIterator> | |
void | |
SipHash<C,D>::update (InputIterator msg, std::size_t size) { | |
if (!size) { | |
return; | |
} | |
uint64_t m; | |
uint64_t seen = padding >> 56; | |
uint64_t const have = seen % sizeof(m); | |
seen += size; | |
assert ((((size % 256) + seen) % 256) == ((size + seen) % 256)); | |
if (have) { | |
auto const need = sizeof(m) - have; | |
assert ((have >= 1) && (have < sizeof(m))); | |
assert ((need >= 1) && (need < sizeof(m))); | |
assert (size >= 1); | |
msg = read_le (msg, std::min(need, size), &m); | |
m <<= 8 * have; | |
m |= padding & 0x00FFFFFFFFFFFFFFull; | |
if (size < need) { | |
padding = m; | |
goto stash_padding; | |
} else { | |
padding = 0; | |
size -= need; | |
inject (m); | |
} | |
} | |
while (size >= sizeof(m)) { | |
msg = read_le (msg, &m); | |
size -= sizeof(m); | |
inject (m); | |
} | |
assert (size < sizeof(m)); | |
if (size) { | |
read_le (msg, size, &padding); | |
} | |
stash_padding: | |
padding |= (seen << 56); | |
} | |
template <unsigned C, unsigned D> | |
void | |
SipHash<C,D>::finalize() { | |
inject (padding); | |
v2 ^= 255; | |
for (auto i = 0; i < D; ++i) { | |
do_round(); | |
} | |
} | |
template <unsigned C, unsigned D> inline | |
uint64_t | |
SipHash<C,D>::value() const { | |
return (v0 ^ v1 ^ v2 ^ v3); | |
} | |
template <unsigned C, unsigned D> | |
template <typename... Args> inline | |
uint64_t SipHash<C,D>::operator()(Args&&... args) { | |
//reset() | |
update (std::forward<Args>(args)...); | |
finalize(); | |
return value(); | |
} | |
template <unsigned C, unsigned D> | |
template <typename... Args> inline | |
void SipHash<C,D>::final (Args&&... args) { | |
update (std::forward<Args>(args)...); | |
finalize(); | |
} | |
template <unsigned C, unsigned D> | |
void | |
SipHash<C,D>::do_round() { | |
++flange; | |
v0 += v1; | |
v2 += v3; | |
rotate_left<13>(v1); | |
rotate_left<16>(v3); | |
v1 ^= v0; | |
v3 ^= v2; | |
rotate_left<32>(v0); | |
std::swap(v0, v2); | |
v0 += v1; | |
v2 += v3; | |
rotate_left<17>(v1); | |
rotate_left<21>(v3); | |
v1 ^= v0; | |
v3 ^= v2; | |
rotate_left<32>(v0); | |
std::swap(v0, v2); | |
} | |
} | |
#include <iostream> | |
#include <boost/algorithm/hex.hpp> | |
namespace { | |
template <typename T> inline | |
typename std::enable_if<std::is_unsigned<T>::value, T>::type | |
high_bit (T x) { | |
return T (x >> ((8 * sizeof(x)) - 1)); | |
} | |
template <typename InputIterator, typename OutputIterator, typename HashFunction> | |
typename std::enable_if< | |
std::is_unsigned< | |
typename std::iterator_traits<InputIterator>::value_type | |
>::value, | |
OutputIterator | |
>::type | |
thorp_round (InputIterator const begin, InputIterator const end, OutputIterator out, | |
HashFunction hash) | |
{ | |
if (begin == end) { | |
return out; | |
} | |
auto it = begin; | |
using word_type = typename std::iterator_traits<InputIterator>::value_type; | |
word_type high = *it++; | |
word_type last = high_bit (high); | |
while (it != end) { | |
word_type low = *it++; | |
high = word_type (high << 1); | |
high = high | high_bit (low); | |
*out++ = high; | |
hash.update (&high, 1); | |
high = low; | |
} | |
high = word_type (high << 1); | |
hash.update (&high, 1); | |
hash.finalize(); | |
last = word_type (last ^ (hash.value() & 1)); | |
high |= last; | |
*out++ = high; | |
return std::move(out); | |
} | |
template <typename InputIterator, typename OutputIterator, | |
typename HashFunction> inline | |
OutputIterator | |
thorp_pass (InputIterator begin, InputIterator end, OutputIterator out, | |
HashFunction hash) | |
{ | |
using word_type = typename std::iterator_traits<InputIterator>::value_type; | |
auto const n = std::distance (begin, end); | |
assert (n >= 0); | |
if (!n) { | |
return out; | |
} | |
auto const n_rounds = (8 * sizeof(word_type) * static_cast<std::size_t>(n)); | |
auto end_out = thorp_round (begin, end, out, hash); | |
for (auto r = 1; r < n_rounds; ++r) { | |
end_out = thorp_round (out, std::move(end_out), out, hash); | |
// boost::algorithm::hex (out, endr, std::ostream_iterator<char>(std::cout)); | |
// std::cout << "\n"; | |
} | |
return end_out; | |
} | |
} | |
#if 0 | |
namespace cppnews { | |
template <typename Key> | |
void | |
mask (boost::asio::ip::address_v4 ip4, Key const& key) { | |
auto const bytes = ip4.to_bytes(); | |
std::cout << bytes.size() << std::endl; | |
} | |
template <typename Key> | |
void | |
mask (boost::asio::ip::address_v6 ip6, Key const& key) { | |
auto bytes = ip6.to_bytes(); | |
std::cout << bytes.size() << std::endl; | |
boost::algorithm::hex (begin(bytes), end(bytes), | |
std::ostream_iterator<char>(std::cout)); | |
std::cout << "\n"; | |
SipHash<2,4> hash(key); | |
for (auto i = 1; i <= 4; ++i) { | |
std::cout << "Pass " << i << "\n"; | |
thorp_pass (begin(bytes), end(bytes), begin(bytes), hash); | |
boost::algorithm::hex (begin(bytes), end(bytes), | |
std::ostream_iterator<char>(std::cout)); | |
std::cout << "\n"; | |
} | |
} | |
template <typename Key> | |
void | |
mask (ip_address const& ipaddr, Key const& key) { | |
if (ipaddr.is_v4()) { | |
return mask (ipaddr.to_v4(), key); | |
} else if (ipaddr.is_v6()) { | |
return mask (ipaddr.to_v6(), key); | |
} else { | |
throw std::runtime_error | |
("Encrypting non-standard IP addresses is currently unsupported"); | |
} | |
} | |
} | |
#endif | |
int | |
main (int const argc, char const* const argv[]) { | |
#if 0 | |
if (argc < 2) { | |
return EXIT_FAILURE; | |
} | |
using cppnews::SipHash; | |
std::cout << "Hash test: " << std::endl; | |
std::string key; | |
key.resize(16); | |
std::iota (begin(key), end(key), 0); | |
std::array<unsigned char, 64> msg; | |
std::iota (begin(msg), end(msg), 0); | |
for (unsigned i = 0; i < 64; ++i) { | |
SipHash<2,4> hash (key); | |
auto h = hash (begin(msg), i); | |
boost::algorithm::hex (reinterpret_cast<char*>(&h), | |
reinterpret_cast<char*>(&h) + sizeof(h), | |
std::ostream_iterator<char>(std::cout)); | |
std::cout << "\n"; | |
} | |
key = "aspoonfulofsugar"; | |
for (auto i = 1; i < argc; ++i) { | |
auto ip = cppnews::ip_address::from_string (argv[i]); | |
cppnews::mask (ip, key); | |
} | |
#endif | |
std::string key = "aspoonfulofsugar"; | |
cppnews::SipHash<2,8> hash (key); | |
std::vector<bool> reg; | |
reg.resize (1ull << 32, false); | |
uint32_t y; | |
for (uint64_t z = 0; z < std::numeric_limits<uint16_t>::max(); ++z) { | |
uint32_t x = uint32_t(z); | |
thorp_pass (reinterpret_cast<unsigned char*>(&x), | |
reinterpret_cast<unsigned char*>(&x + 1), | |
reinterpret_cast<unsigned char*>(&y), hash); | |
if (reg[y]) { | |
std::cerr << "collision: " << x << " -> " << y << "\n"; | |
} | |
reg[y] = true; | |
} | |
auto num_falsies = std::count (begin(reg), end(reg), false); | |
std::cout << "true : " << (reg.size() - std::size_t(num_falsies)) << std::endl; | |
std::cout << "false : " << num_falsies << std::endl; | |
while (true) { | |
auto found = std::find (begin(reg), end(reg), false); | |
if (found == end(reg)) { | |
break; | |
} | |
std::cout << std::distance(begin(reg), found) << std::endl; | |
} | |
std::cout << flange << std::endl; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment