bitops.hpp

Go to the documentation of this file.

/*
 * SPDX-Licence-Identifier: MIT
 *
 * Copyright 2025 Larry Chips
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the “Software”), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#pragma once

 
#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 {
 
 
 

template<class T> constexpr bitwise_uint_only<T> clz(T) noexcept;

template<class T> constexpr bitwise_uint_only<T> cl1(T) noexcept;

template<class T> constexpr bitwise_uint_only<T> crz(T) noexcept;

template<class T> constexpr bitwise_uint_only<T> cr1(T) noexcept;

template<class T> constexpr bitwise_uint_only<T> bitwidth(T) noexcept;
 
 
 
 
#ifdef UGMISC_HAVE_BITOPS
 
/*
 * We have all the functions in the standard library, so ours are simple wrappers.
 */
 
template<class T>
constexpr bitwise_uint_only<T> clz(T x) noexcept { return std::countl_zero(x); }
 
template<class T>
constexpr bitwise_uint_only<T> cl1(T x) noexcept { return std::countl_one(x); }
 
template<class T>
constexpr bitwise_uint_only<T> crz(T x) noexcept { return std::countr_zero(x); }
 
template<class T>
constexpr bitwise_uint_only<T> cr1(T x) noexcept { return std::countr_one(x); }
 
template<class T>
constexpr bitwise_uint_only<T> bitwidth(T x) noexcept {
    return std::bit_width(x);
}
 
 
#else
 
/*
 * We don't have std::countl_zero, std::countr_one etc.
 *
 * TODO: Detect or guess compiler intrinsics and use those.
 */
 
 
 

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, one the
 * left or right as required.
 */
template<BitFunc F, class T, T Bits = std::numeric_limits<T>::digits, T Shift = 0 >
static constexpr bitwise_uint_only<T> cxx(T v) noexcept {
    constexpr T 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 T left_partition_bits = Bits/2;
        constexpr T right_partition_bits = Bits - left_partition_bits;
        constexpr T left_partition_shift = Shift + right_partition_bits;
        constexpr T right_partition_shift = Shift;
 
        constexpr T first_partition_bits
            = from_left ? left_partition_bits : right_partition_bits;
        constexpr T second_partition_bits
            = from_left ? right_partition_bits : left_partition_bits;
 
        constexpr T first_partition_shift
            = from_left ? left_partition_shift : right_partition_shift;
        constexpr T second_partition_shift
            = from_left ? right_partition_shift : left_partition_shift;
 
        T first_result = cxx<F, T, first_partition_bits, first_partition_shift>(v);
 
        if ( first_result < first_partition_bits ) {
            return first_result;
        } else {
            T second_result = cxx<F, T, second_partition_bits, second_partition_shift>(v);
            return first_result + second_result;
        }
    }
}
 
} /* bitops_ (::ugmisc::bitops_) */
 
 
 
 
template<class T> constexpr bitwise_uint_only<T> clz(T v) noexcept {
    return bitops_::cxx<bitops_::CLZ, T>(v);
}
 
template<class T> constexpr bitwise_uint_only<T> cl1(T v) noexcept {
    return bitops_::cxx<bitops_::CL1, T>(v);
}
 
 
template<class T> constexpr bitwise_uint_only<T> crz(T v) noexcept {
    return bitops_::cxx<bitops_::CRZ, T>(v);
}
 
 
template<class T> constexpr bitwise_uint_only<T> cr1(T v) noexcept {
    return bitops_::cxx<bitops_::CR1, T>(v);
}
 
 
 
 
template<class T>
constexpr bitwise_uint_only<T> bitwidth(T x) noexcept {
    return std::numeric_limits<T>::digits - clz(x);
}
 
 
 
 
 
#endif /* No C++20 library bit funcs. */
 
 
 
 
} /* ::ugmisc */