bit_op.h

Go to the documentation of this file.

 
 
#ifndef THEORETICA_BIT_OP_H
#define THEORETICA_BIT_OP_H
 
#include <cstdint>
 
 
namespace theoretica {
 
 
    inline void mul_uint128(
        uint64_t a, uint64_t b,
        uint64_t& c_low, uint64_t& c_high) {
 
        // Lowest and highest 32 bits of a and b
        const uint64_t a_low = a & 0xffffffff;
        const uint64_t a_high = a >> 32;
 
        const uint64_t b_low = b & 0xffffffff;
        const uint64_t b_high = b >> 32;
 
        uint64_t m[4];
 
        // Multiplication terms for (a_l + a_h) * (b_l + b_h)
        m[0] = a_low * b_low;
        m[1] = a_low * b_high;
        m[2] = a_high * b_low;
        m[3] = a_high * b_high;
 
        // Multiplication carry for c_high
        uint64_t carry = (
            (m[0] >> 32) +
            (m[1] & 0xffffffff) +
            (m[2] & 0xffffffff)) >> 32;
 
        c_low = m[0] + (m[1] << 32) + (m[2] << 32);
        c_high = m[3] + (m[1] >> 32) + (m[2] >> 32) + carry;
    }
 
 
    inline uint64_t mix_mum(uint64_t a, uint64_t b) {
 
        uint64_t c_low, c_high;
        mul_uint128(a, b, c_low, c_high);
 
        return c_high ^ c_low;
    }
 
 
    template<typename UnsignedIntType>
    inline TH_CONSTEXPR UnsignedIntType
    bit_rotate(UnsignedIntType x, unsigned int i) {
 
        return (x << i) | (x >> ((sizeof(UnsignedIntType) * 8) - i));
    }
 
 
    template<typename Vector, enable_vector<Vector> = true>
    inline void swap_bit_reverse(Vector& x, unsigned int m) {
 
        if (x.size() < (uint64_t(1) << m)) {
            TH_MATH_ERROR("swap_bit_reverse", x.size(), INVALID_ARGUMENT);
            return;
        }
 
        for (unsigned int i = 0; i < x.size(); i++) {
 
            unsigned int j = 0;
 
            for (unsigned int k = 0; k < m; k++)
                j = (j << 1) | ((i >> k) & 0x01);
 
            if (j > i)
                std::swap(x[i], x[j]);
        }
    }
}
 
 
#endif