int_finder.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 <limits>
#include <string_view>
#include <type_traits>
#include "ugmisc/bitops.hpp"
#include "ugmisc/features.hpp"
#include "ugmisc/member.hpp"
#include "ugmisc/quote.hpp"
 
 
namespace ugmisc {
 

enum int_sign { INVALID_SIGN = 0, UNSIGNED = 1, SIGNED = 2 };
 
 
 
 
constexpr int_sign flip( int_sign s ) {
    return static_cast<int_sign>(((unsigned)s) ^ 3);
}
 
 
 

enum sign_opt : std::uint8_t {
    SELECT_SIGN_OPTION_NONE = 0,
    SELECT_UNSIGNED   = 1,
    SELECT_SIGNED     = 2,
    SELECT_TYPE_SIGN  = 3, 
    SELECT_VALUE_SIGN = 4, 
 
    SELECT_SIGN_OPTION_MAX = SELECT_VALUE_SIGN,
    SELECT_SIGN_OPTION_MASK = 7,
};
 
 
 
 
constexpr std::string_view get_name(sign_opt opt) {
    switch( opt ) {
    case SELECT_SIGN_OPTION_NONE:
        return "NONE";
    case SELECT_UNSIGNED:
        return "SELECT_UNSIGNED";
    case SELECT_SIGNED:
        return "SELECT_SIGNED";
    case SELECT_TYPE_SIGN:
        return "SELECT_TYPE_SIGN";
    case SELECT_VALUE_SIGN:
        return "SELECT_VALUE_SIGN";
    default:
        return "INVALID";
    }
};
 
 
 
 
 
template<class T>
constexpr int_sign sign(sign_opt opt, T v) {
 
    switch( opt ) {
    case SELECT_UNSIGNED: return UNSIGNED;
    case SELECT_SIGNED: return SIGNED;
    case SELECT_TYPE_SIGN:
        return std::is_signed_v<T> ? SIGNED : UNSIGNED;
    case SELECT_VALUE_SIGN:
        return v < 0 ? SIGNED : UNSIGNED;
    default:
        return INVALID_SIGN;
    }
}
 
 
 
 
enum sign_flag : std::uint8_t {
    SELECT_SIGN_FLAGS_NONE,
    SELECT_SIGN_SMALLEST     = 1 << 3,

    SELECT_SIGN_ALLOW_VALUE_SIGN_LOSS = 1 << 4,
 
    SELECT_SIGN_FLAGS_MASK = SELECT_SIGN_SMALLEST|SELECT_SIGN_ALLOW_VALUE_SIGN_LOSS
};
 
 
constexpr sign_flag operator~(sign_flag f) {
    return static_cast<sign_flag>((~(std::uint8_t)f)&(std::uint8_t)SELECT_SIGN_FLAGS_MASK);
}
 
 
constexpr sign_flag operator|(sign_flag a, sign_flag b) {
    return static_cast<sign_flag>((std::uint8_t)a | (std::uint8_t)b);
}
 
 
constexpr bool smallest(sign_flag s) {
    return (std::uint8_t)SELECT_SIGN_SMALLEST & (std::uint8_t)s;
}
 
 
constexpr bool allow_value_sign_loss(sign_flag s) {
    return (std::uint8_t)SELECT_SIGN_ALLOW_VALUE_SIGN_LOSS & (std::uint8_t)s;
}
 
 
/*
 * This might have to be a string instead of a string_view if we add more
 * flags, because we can't just special case every combination.
 *
 * Then we would have to ditch the constexpr too.
 */
constexpr std::string_view get_name(sign_flag flags) {
    bool smol     = smallest(flags);
    bool signloss = allow_value_sign_loss(flags);
    if ( smol && signloss ) {
        return "SELECT_SIGN_SMALLEST|SELECT_SIGN_ALLOW_VALUE_SIGN_LOSS";
    } else if ( smol ) {
        return "SELECT_SIGN_SMALLEST";
    } else if ( signloss ) {
        return "SELECT_SIGN_ALLOW_VALUE_SIGN_LOSS";
    } else {
        return "NONE";
    }
}
 
 
 

namespace intfind_ {
 
 
 
 
template<class T>
inline constexpr bool is_opt = std::is_convertible_v<T, sign_opt>;
 
template<class T>
inline constexpr bool is_flag = std::is_convertible_v<T, sign_flag>;
 
 
 

template< class T >
constexpr sign_opt sign_opt_or_not(T t) {
    if constexpr ( is_opt<T> ) {
        return static_cast<sign_opt>(t);
    } else if constexpr ( is_flag<T> ) {
        return SELECT_SIGN_OPTION_NONE;
    } else {
        static_assert( false );
    }
}
 
 
template<class T> constexpr bool is_non_null_opt(T t) {
    return (unsigned)sign_opt_or_not(t);
}
 
 
template<class T> constexpr sign_flag sign_flag_or_not(T t) {
    if constexpr ( is_flag<T> ) {
        return static_cast<sign_flag>(t);
    } else if constexpr ( is_opt<T> ) {
        return SELECT_SIGN_FLAGS_NONE;
    } else {
        static_assert(
                false,
                "sign_flag_or_not takes sign_flag and sign_opt, "
                "and types convertible to them."
                );
    }
}
 
 
 

template<auto...Opts>
constexpr sign_opt combine_sign_opts_f()
{
    constexpr sign_opt opt_array[sizeof...(Opts)] = { sign_opt_or_not(Opts)... };
    sign_opt found_opt = SELECT_SIGN_OPTION_NONE;
    for( sign_opt opt: opt_array ) {
        if ( opt == SELECT_SIGN_OPTION_NONE ) {
            continue;
        }
        if ( found_opt != SELECT_SIGN_OPTION_NONE && opt != found_opt ) {
            return SELECT_SIGN_OPTION_NONE;
        }
        found_opt = opt;
    }
    return found_opt;
}
 
 
 
 
template<auto...Opts> static constexpr sign_opt combined_sign_opts
    = combine_sign_opts_f<Opts...>();
 
 
template<auto...Flags> static constexpr sign_flag combined_sign_flags
    = (SELECT_SIGN_FLAGS_NONE | ... | sign_flag_or_not(Flags));
 
 
 
 
template<auto...Opt>
static constexpr bool valid_sign_opts = (unsigned)combined_sign_opts<Opt...>;
 
 
 
 
template<auto...Opt>
static constexpr bool any_sign_opts = (... || is_non_null_opt(Opt));
 
 
 

template<bool HasOpt>
class flag_opt_combo {
    const sign_flag m_flags;
 
public:
    flag_opt_combo(const flag_opt_combo&) = default;
    constexpr flag_opt_combo(sign_flag sflags) : m_flags(sflags) {}
 
    constexpr sign_flag flags() const { return m_flags; }
    constexpr sign_opt safe_opt() const { return SELECT_SIGN_OPTION_NONE; }
    constexpr sign_opt opt() const {
        static_assert(
                false,
                "This flag_opt_combo does not have an option."
                );
        return safe_opt();
    }
 
    constexpr operator sign_flag() const { return flags(); }
};
 
 
template<>
class flag_opt_combo<true> : public flag_opt_combo<false> {
    const sign_opt m_opt;
 
public:
    flag_opt_combo(const flag_opt_combo&) = default;
    constexpr flag_opt_combo(sign_opt sopt, sign_flag sflags)
        : flag_opt_combo<false>(sflags), m_opt(sopt)
    {}
 
    constexpr sign_opt opt() const { return m_opt; }
    constexpr sign_opt safe_opt() const { return opt(); }
 
    constexpr operator sign_opt() const { return opt(); }
};
 
 
 
 
template<auto...args>
constexpr auto combine_flags_opts()
{
    constexpr sign_flag flags = combined_sign_flags<args...>;
    constexpr sign_opt opt  = combined_sign_opts<args...>;
    constexpr bool valid_opts = valid_sign_opts<args...>;
    constexpr bool any_opts = any_sign_opts<args...>;
 
    if constexpr ( any_opts ) {
        static_assert( valid_opts );
        return flag_opt_combo<true>{opt, flags};
    } else {
        return flag_opt_combo<false>{flags};
    }
}
 
 
 
 
 
} /* intfind_ */
// INTERNAL
 
 
 
 
#ifndef UGMISC_INT_FINDER_MAX_INT_WIDTH
# define UGMISC_INT_FINDER_MAX_INT_WIDTH (1U << 12);
#endif
inline constexpr unsigned max_int_width = UGMISC_INT_FINDER_MAX_INT_WIDTH;
 
 
 

template<unsigned N> struct get_int_types {};
 

template<> struct get_int_types<8> {
    using unsigned_type = std::uint8_t;
    using signed_type = std::int8_t;
};
 

template<> struct get_int_types<16> {
    using unsigned_type = std::uint16_t;
    using signed_type = std::int16_t;
};
 

template<> struct get_int_types<32> {
#ifndef UGMISC_TEST_INT_FINDER_SKIP_U32
    using unsigned_type = std::uint32_t;
#endif
    using signed_type = std::int32_t;
};
 

template<> struct get_int_types<64> {
    using unsigned_type = std::uint64_t;
    using signed_type = std::int64_t;
};
 
 
 

namespace intfind_ {
 
 
 
 
constexpr unsigned round_up_to_pow2(unsigned x) {
    unsigned hi = 1U << bitwidth(x);
    unsigned lo = hi >> 1;
    return x ? (lo == x ? lo : hi) : 1;
}
 
 
 
 
/*
 * This allows us to test the existence of a type easily.
 *
 * Resulting declarations are listed below for clarity.
 */
UGMISC_MEMBER_TYPE_TEST(unsigned_type);
UGMISC_MEMBER_TYPE_TEST(signed_type);
// has_member_type_unsigned_type< T >; // T can be a type_list.
// member_type_unsigned_type< T, D (optional) > // T can be type_list,
                                                // D is a default type.
// member_type_test_unsigned_type< T > // Usually not used directly.
// has_member_type_signed_type< T >; // T can be a type_list.
// member_type_signed_type< T, D (optional) > // T can be type_list,
                                              // D is a default type.
// member_type_test_signed_type< T > // Usually not used directly.
 
 
 
template<unsigned N>
constexpr bool check_member_int_types(get_int_types<N> t) {
    static_assert( N <= max_int_width,
           "Integer width must be no more than "
           UGMISC_QQ(UGMISC_INT_FINDER_MAX_INT_WIDTH)
           " bits."
           );
    using T = decltype(t);
 
    if constexpr ( has_member_type_unsigned_type<T> ) {
        using I = typename T::unsigned_type;
        using limits = std::numeric_limits<I>;
        constexpr unsigned bits = limits::digits;
        static_assert( limits::radix == 2 );
        static_assert( limits::is_integer );
        static_assert( ! limits::is_signed );
        static_assert( bits == N );
    }
 
    if constexpr ( has_member_type_signed_type<T> ) {
        using I = typename T::signed_type;
        using limits = std::numeric_limits<I>;
        constexpr unsigned bits = limits::digits + 1; // Sign bit.
        static_assert( limits::radix == 2 );
        static_assert( limits::is_integer );
        static_assert( limits::is_signed );
        static_assert( bits == N );
    }
 
    return true;
}
 
 
 

template<unsigned N> struct get_int_types : public ::ugmisc::get_int_types<N> {
private:
    static constexpr bool _check =
        check_member_int_types(::ugmisc::get_int_types<N>{});
};
 
 
 
 
} /* intfind_ (::ugmisc::intfind_) */
// INTERNAL
 
 
 

template<unsigned N, int_sign Sign>
inline constexpr bool has_int_type =
    Sign == UNSIGNED
    ? intfind_::has_member_type_unsigned_type< intfind_::get_int_types<N> >
    : intfind_::has_member_type_signed_type< intfind_::get_int_types<N> >
    ;
 

template<unsigned N> inline constexpr bool has_unsigned_type =
    has_int_type<N, UNSIGNED>;

template<unsigned N> inline constexpr bool has_signed_type = has_int_type<N, SIGNED>;

template<unsigned N> inline constexpr bool has_both_int_types =
    has_unsigned_type<N> && has_signed_type<N>;

template<unsigned N> inline constexpr bool  has_either_int_type =
    has_unsigned_type<N> || has_signed_type<N>;
 
 
 

template<unsigned N> using exact_unsigned_type = typename intfind_::get_int_types<N>::unsigned_type;

template<unsigned N> using exact_signed_type = typename intfind_::get_int_types<N>::signed_type;
 
 
 

namespace intfind_ {
 

template<unsigned N, int_sign S> struct get_exact_int_type;
 
 
template<unsigned N>
struct get_exact_int_type<N, UNSIGNED> {
    using type = typename get_int_types<N>::unsigned_type;
};
 
template<unsigned N>
struct get_exact_int_type<N, SIGNED> {
    using type = typename get_int_types<N>::signed_type;
};
 
 
} /* intfind_ */
// INTERNAL
 

template<unsigned N, int_sign S> using exact_int_type =
    typename intfind_::get_exact_int_type<N, S>::type;
 
 
 

namespace intfind_ {
 
 
 
 
#ifdef UGMISC_TEST_INT_FINDER_INNER_LOOP_MAX
static constexpr unsigned find_inner_loop_max = UGMISC_TEST_INT_FINDER_INNER_LOOP_MAX;
#else
static constexpr unsigned find_inner_loop_max = 100;
#endif
 
 
 

template<unsigned Min, int_sign Sign, unsigned Max>
constexpr auto find_type_100() {
    static_assert( Max - Min < find_inner_loop_max );
    static_assert( Max <= max_int_width );
    static_assert( Min <= Max );
    static_assert( Sign == UNSIGNED || Sign == SIGNED );
 
    if constexpr ( has_int_type<Min, Sign> ) {
        return (exact_int_type<Min, Sign>)1;
    } else if constexpr ( Min == Max ) {
        return false;
    } else {
        return find_type_100<Min+1, Sign, Max>();
    }
}
 
 
 

template<unsigned Min, int_sign Sign, unsigned Max = max_int_width>
constexpr auto find_type() {
    static_assert(Max <= max_int_width);
    static_assert(Max >= Min);
    static_assert( Sign == UNSIGNED || Sign == SIGNED );
 
    constexpr unsigned near_max = std::min(Min+find_inner_loop_max-1, Max);
    constexpr bool last_iter = near_max == Max;
 
    if constexpr ( find_type_100<Min, Sign, near_max>() ) {
        return find_type_100<Min, Sign, near_max>();
    } else if constexpr ( last_iter ) {
        return false;
    } else {
        return find_type<near_max+1, Sign, Max>();
    }
}
 
 
 
 
}
// INTERNAL
 
 
 

template<unsigned N, int_sign S>
using least_int_type =
    std::enable_if_t<
        intfind_::find_type<N, S>(),
        decltype(intfind_::find_type<N, S>())
    >;
 

template<unsigned N>
using least_unsigned_type = least_int_type<N, UNSIGNED>;
 

template<unsigned N>
using least_signed_type = least_int_type<N, SIGNED>;
 
 
 

template< bool IncludingSignBit, class T >
constexpr int_only<T, unsigned> signed_bitwidth(T v) {
    using U = least_unsigned_type<std::numeric_limits<T>::digits>;
    constexpr bool use_sign_bit = std::is_signed_v<T> && IncludingSignBit;
    constexpr unsigned extra_bits = use_sign_bit ? 1 : 0;
    const U w = v >= 0 ? (U)v : ~(U)v;
    return bitwidth(w) + extra_bits;
}
 
 
 

namespace intfind_ {
 
 
 
 
template<class T>
struct range_result_compare {
    const T value;
    range_result_compare(const range_result_compare&) = default;
    constexpr range_result_compare(T v) : value(v) {}
    constexpr bool valid() const { return value; }
    constexpr unsigned size() const { return sizeof(T); }
    constexpr unsigned used_bits() const {
        unsigned sign_bit = std::numeric_limits<T>::is_signed ? 1 : 0;
        return std::numeric_limits<T>::digits + sign_bit;
    }
};
 
 
 
 
/*
 * When looking for a smaller result type, a valid one always wins if the other
 * is invalid.  We care most about storage size, then used bits.
 */
template<class T, class U>
constexpr bool operator < (range_result_compare<T> a, range_result_compare<U> b) {
    if ( !a.valid() ) { return false; }
    if ( !b.valid() ) { return true; }
    if ( a.size() < b.size() ) { return true; }
    if ( a.size() > b.size() ) { return false; }
    return a.used_bits() < b.used_bits();
}
 
 
 
 
template<auto V, auto...SelectArgs>
constexpr auto as_least_required_type() {
    constexpr auto S = intfind_::combine_flags_opts<SelectArgs...>();
    constexpr int_sign pref_sign = sign(S, V);
    constexpr int_sign other_sign = flip(pref_sign);
    constexpr int_sign value_sign = V < 0 ? SIGNED : UNSIGNED;
 
    constexpr bool may_be_unsigned =
        value_sign == UNSIGNED
        || allow_value_sign_loss(S)
        ;
 
    constexpr unsigned value_bits = signed_bitwidth<true>(V);
    constexpr bool choose_smaller = smallest(S);
 
    // pref_value is a value which converts to true in boolean context if a
    // type was found, and whose type (in that case) is the type found.
    // Otherwise it will be false, and its type will be bool.
    constexpr auto pref_value =
        intfind_::find_type<value_bits, pref_sign>();
    constexpr auto other_value =
        intfind_::find_type<value_bits, other_sign>();
 
    using pref_t = decltype(pref_value);
    using other_t = decltype(other_value);
 
    constexpr bool pref_valid = pref_value && (std::numeric_limits<pref_t>::is_signed || may_be_unsigned);
 
    /*
     * We never treat the sign select option as a mere suggestion unless
     * allowing a smaller type of the other sign to be chosen.
     */
    constexpr bool other_valid = other_value && (std::numeric_limits<other_t>::is_signed || may_be_unsigned) && choose_smaller;
 
    static_assert(
            pref_valid || other_valid,
            "least_required_type could not find a type that satisfies all "
            "requirements."
            );
 
 
    constexpr bool use_pref = [=]() -> bool {
        // Find out whether to use the found type (if any) of the preferred
        // sign, or the other one.  Usually there will always be a pair of
        // types of one size available, signed and unsigned, so most of these
        // cases will not be matched.
        if constexpr ( ! other_valid ) {
            // We have a valid type of preferred sign, and no type of other sign.
            return true;
        } else if constexpr ( ! pref_valid ) {
            // No preferred sign available, but the other sign is available.
            return false;
        } else if constexpr (
                choose_smaller && other_valid
                &&
                range_result_compare{other_value} < range_result_compare{pref_value}
                )
        {
            // There is a smaller type available that is large enough but not
            // of the preferred type.
            return false;
        } else {
            // Special cases have been exhausted (probably not really, sorry).
            return true;
        }
    }();
 
    if constexpr ( use_pref ) {
        static_assert(
                pref_valid,
                "This is Larry's fault."
                " An earlier static assertion should have failed already."
                );
        return static_cast<pref_t>(V);
    } else {
        static_assert(
                other_valid,
                "This is Larry's fault."
                " An earlier static assertion should have failed already."
                );
        return static_cast<other_t>(V);
    }
}
 
 
 
 
} /* intfind_ (::ugmisc::intfind_) */
// INTERNAL
 
 
 

template<auto V, auto...S>
inline constexpr auto as_least_required_int_type =
    intfind_::as_least_required_type<V, S...>();
 
 
 

template<auto V, auto...S>
using least_required_int_type = decltype(as_least_required_int_type<V, S...>);
 
 
 
 
} /* ugmisc */