bits.h

Go to the documentation of this file.

 
#ifndef THEORETICA_BITS_H
#define THEORETICA_BITS_H
 
#include <cstdint>
#include "./core_traits.h"
 
 
namespace theoretica {

namespace bits {
 

    inline constexpr 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;
 
        // Multiplication terms for (a_l + a_h) * (b_l + b_h)
        const uint64_t m[4] = {
            a_low * b_low,
            a_low * b_high,
            a_high * b_low,
            a_high * b_high
        };
 
        // Multiplication carry for c_high
        const 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 constexpr uint64_t mix_mum(uint64_t a, uint64_t b) {
 
        uint64_t c_low = 0;
        uint64_t c_high = 0;
        mul_uint128(a, b, c_low, c_high);
 
        return c_high ^ c_low;
    }
 

    template<typename UnsignedIntType>
    inline 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 constexpr void swap_bit_reverse(Vector& x, unsigned int m) {
 
        if (x.size() < (uint64_t(1) << m)) {
            TH_MATH_ERROR("swap_bit_reverse", x.size(), MathError::InvalidArgument);
            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