1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___RANDOM_LOG2_H
10#define _LIBCPP___RANDOM_LOG2_H
11
12#include <__config>
13#include <__cstddef/size_t.h>
14#include <__type_traits/conditional.h>
15
16#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
17# pragma GCC system_header
18#endif
19
20_LIBCPP_BEGIN_NAMESPACE_STD
21
22template <class _UIntType, _UIntType _Xp, size_t _Rp>
23struct __log2_imp;
24
25template <unsigned long long _Xp, size_t _Rp>
26struct __log2_imp<unsigned long long, _Xp, _Rp> {
27 static const size_t value =
28 _Xp & ((unsigned long long)(1) << _Rp) ? _Rp : __log2_imp<unsigned long long, _Xp, _Rp - 1>::value;
29};
30
31template <unsigned long long _Xp>
32struct __log2_imp<unsigned long long, _Xp, 0> {
33 static const size_t value = 0;
34};
35
36template <size_t _Rp>
37struct __log2_imp<unsigned long long, 0, _Rp> {
38 static const size_t value = _Rp + 1;
39};
40
41#if _LIBCPP_HAS_INT128
42
43template <__uint128_t _Xp, size_t _Rp>
44struct __log2_imp<__uint128_t, _Xp, _Rp> {
45 static const size_t value =
46 (_Xp >> 64) ? (64 + __log2_imp<unsigned long long, (_Xp >> 64), 63>::value)
47 : __log2_imp<unsigned long long, _Xp, 63>::value;
48};
49
50#endif // _LIBCPP_HAS_INT128
51
52template <class _UIntType, _UIntType _Xp>
53struct __log2 {
54 static const size_t value = __log2_imp<
55#if _LIBCPP_HAS_INT128
56 __conditional_t<sizeof(_UIntType) <= sizeof(unsigned long long), unsigned long long, __uint128_t>,
57#else
58 unsigned long long,
59#endif // _LIBCPP_HAS_INT128
60 _Xp,
61 sizeof(_UIntType) * __CHAR_BIT__ - 1>::value;
62};
63
64_LIBCPP_END_NAMESPACE_STD
65
66#endif // _LIBCPP___RANDOM_LOG2_H
67