bitops.hpp

Go to the documentation of this file.

/*
 * SPDX-FileCopyrightText: © 2025 Larry Chips <larry@larrychips.net>
 * SPDX-Licence-Identifier: MIT
 */
#ifndef UGMISC_BITOPS_HPP
#define UGMISC_BITOPS_HPP

 
#include <cstdint>
#include <type_traits>
#include <utility>
 
#include "ugmisc/features.hpp"
#include "ugmisc/sfinae_helpers.hpp"
 
#ifdef UGMISC_HAVE_BITOPS
# include <bit>
#endif
 
 
namespace ugmisc {
 
 
 
 
/*
 * Forward declarations.
 *
 * We declare these two ways:
 *
 * 1. With concepts if concepts are supported OR if we are building the docs.
 * 2. With enable_if based return types otherwise.
 *
 * This is accomplished using the UGMISC_BITWISE_UINT_RETURN macro from the
 * sfinae_helpers.hpp header.
 */

template<class T> constexpr auto clz(T) noexcept -> UGMISC_BITWISE_UINT_RETURN(T, int);

template<class T> constexpr auto cl1(T) noexcept -> UGMISC_BITWISE_UINT_RETURN(T, int);

template<class T> constexpr auto crz(T) noexcept -> UGMISC_BITWISE_UINT_RETURN(T, int);

template<class T> constexpr auto cr1(T) noexcept -> UGMISC_BITWISE_UINT_RETURN(T, int);

template<class T> constexpr auto bitwidth(T) noexcept -> UGMISC_BITWISE_UINT_RETURN(T, int);
 
 
 

namespace _bitops {
 
 
enum BitFunc { CLZ, CR1, CL1, CRZ };
 
 
 
 
/*
 * In the absence of std bitops functions, this generic function partitions the
 * word into big chunks until it finds one with all ones or all zeros, on the
 * left or right as required.
 */
template<BitFunc F, class T, int Bits = std::numeric_limits<T>::digits, int Shift = 0 >
static constexpr auto cxx(T v) noexcept
-> UGMISC_BITWISE_UINT_RETURN(T, int)
{
    constexpr int max_bits = std::numeric_limits<T>::digits;
    constexpr T all_ones = ~((T)0);
    constexpr T mask_rightshifted = (all_ones >> (max_bits - Bits));
 
    static_assert( Bits >= 1 );
    static_assert( Bits + Shift <= max_bits );
 
    constexpr bool from_left   = F == CLZ || F == CL1;
    constexpr bool count_ones  = F == CL1 || F == CR1;
    constexpr bool count_zeros = ! count_ones;
    constexpr    T mask        = mask_rightshifted << Shift;
 
    bool all_set = (mask & v) == mask;
    bool all_clear = (mask & v) == 0;
    bool all_bits_of_counted_state = (count_ones && all_set) || (count_zeros && all_clear);
    bool all_bits_of_uncounted_state = (count_ones && all_clear) || (count_ones && all_set);
    bool trivial_result = all_bits_of_counted_state || all_bits_of_uncounted_state;
 
    /*
     * First we want to know if all the bits were set or all clear, so we can
     * trivially return a result.  If that fails we delegate to two functions
     * which examine a smaller part of the word each.  Each function is an
     * instance of this function template.
     *
     * These functions cannot be instantiated if either of them will have 0
     * Bits.  So we must keep the delegating part of our function shielded by a
     * constexpr if condition.
     */
 
    if constexpr ( Bits == 1 ) {
        return all_bits_of_counted_state ? 1 : 0;
    } else {
        if ( trivial_result ) {
            return all_bits_of_counted_state ? Bits : 0;
        }
 
        constexpr int left_partition_bits = Bits/2;
        constexpr int right_partition_bits = Bits - left_partition_bits;
        constexpr int left_partition_shift = Shift + right_partition_bits;
        constexpr int right_partition_shift = Shift;
 
        constexpr int first_partition_bits
            = from_left ? left_partition_bits : right_partition_bits;
        constexpr int second_partition_bits
            = from_left ? right_partition_bits : left_partition_bits;
 
        constexpr int first_partition_shift
            = from_left ? left_partition_shift : right_partition_shift;
        constexpr int second_partition_shift
            = from_left ? right_partition_shift : left_partition_shift;
 
        int first_result = cxx<F, T, first_partition_bits, first_partition_shift>(v);
 
        if ( first_result < first_partition_bits ) {
            return first_result;
        } else {
            int second_result = cxx<F, T, second_partition_bits, second_partition_shift>(v);
            return first_result + second_result;
        }
    }
}

template<class T, class=int> constexpr bool is_std_clz_type = false;
template<class T, class=int> constexpr bool is_std_crz_type = false;
template<class T, class=int> constexpr bool is_std_cl1_type = false;
template<class T, class=int> constexpr bool is_std_cr1_type = false;
template<class T, class=int> constexpr bool is_std_bitwidth_type = false;
#ifdef UGMISC_HAVE_BITOPS
template<class T>
constexpr bool
is_std_clz_type<T, decltype(::std::countl_zero(std::declval<T>()))>
= true;
 
template<class T>
constexpr bool
is_std_crz_type<T, decltype(::std::countr_zero(std::declval<T>()))>
= true;
 
template<class T>
constexpr bool
is_std_cl1_type<T, decltype(::std::countl_one(std::declval<T>()))>
= true;
 
template<class T>
constexpr bool
is_std_cr1_type<T, decltype(::std::countr_one(std::declval<T>()))>
= true;
 
template<class T>
constexpr bool
is_std_bitwidth_type<T, decltype(::std::bit_width(std::declval<T>()))>
= true;
#endif

 
/*
 * The generic call_* templates call cxx.  The partially specialised ones call
 * std functions.
 */
template<class T, bool=true>
struct call_clz {
    constexpr int operator()(T x) const noexcept {
        return cxx<_bitops::CLZ, T>(x);
    }
};
 
template<class T, bool=true>
struct call_cl1 {
    constexpr int operator()(T x) const noexcept {
        return cxx<_bitops::CL1, T>(x);
    }
};
 
template<class T, bool=true>
struct call_crz {
    constexpr int operator()(T x) const noexcept {
        return cxx<_bitops::CRZ, T>(x);
    }
};
 
template<class T, bool=true>
struct call_cr1 {
    constexpr int operator()(T x) const noexcept {
        return cxx<_bitops::CR1, T>(x);
    }
};
 
template<class T, bool=true>
struct call_bitwidth {
    constexpr int operator()(T x) const noexcept {
        return std::numeric_limits<T>::digits - clz(x);
    }
};
 
#ifdef UGMISC_HAVE_BITOPS
template<class T>
struct call_clz<T, is_std_clz_type<T>> {
    constexpr int operator()(T x) const noexcept {
        return ::std::countl_zero(x);
    }
};
 
template<class T>
struct call_cl1<T, is_std_clz_type<T>> {
    constexpr int operator()(T x) const noexcept {
        return ::std::countl_one(x);
    }
};
 
template<class T>
struct call_crz<T, is_std_clz_type<T>> {
    constexpr int operator()(T x) const noexcept {
        return ::std::countr_zero(x);
    }
};
 
template<class T>
struct call_cr1<T, is_std_clz_type<T>> {
    constexpr int operator()(T x) const noexcept {
        return ::std::countr_one(x);
    }
};
 
template<class T>
struct call_bitwidth<T, is_std_clz_type<T>> {
    constexpr int operator()(T x) const noexcept {
        return ::std::bit_width(x);
    }
};
#endif
} /* _bitops (::ugmisc::_bitops) */
 
 
 
 
/*
 * Definitions.
 */
template<class T>
constexpr auto clz(T x) noexcept -> UGMISC_BITWISE_UINT_RETURN(T, int) {
    return _bitops::call_clz<T>{}(x);
}
 
template<class T>
constexpr auto cl1(T x) noexcept -> UGMISC_BITWISE_UINT_RETURN(T, int) {
    return _bitops::call_cl1<T>{}(x);
}
 
template<class T>
constexpr auto crz(T x) noexcept -> UGMISC_BITWISE_UINT_RETURN(T, int) {
    return _bitops::call_crz<T>{}(x);
}
 
template<class T>
constexpr auto cr1(T x) noexcept -> UGMISC_BITWISE_UINT_RETURN(T, int) {
    return _bitops::call_cr1<T>{}(x);
}
 
template<class T>
constexpr auto bitwidth(T x) noexcept -> UGMISC_BITWISE_UINT_RETURN(T, int) {
    return _bitops::call_bitwidth<T>{}(x);
}
} /* ::ugmisc */
 
#endif /* UGMISC_BITOPS_HPP */