gistfile1.txt

#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;
}