libcxx/include/__charconv/traits.h

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP___CHARCONV_TRAITS
  11 #define _LIBCPP___CHARCONV_TRAITS
  12
  13 #include <__bit/countl.h>
  14 #include <__charconv/tables.h>
  15 #include <__charconv/to_chars_base_10.h>
  16 #include <__config>
  17 #include <__type_traits/enable_if.h>
  18 #include <__type_traits/is_unsigned.h>
  19 #include <cstdint>
  20 #include <limits>
  21
  22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  23 #  pragma GCC system_header
  24 #endif
  25
  26 _LIBCPP_PUSH_MACROS
  27 #include <__undef_macros>
  28
  29 _LIBCPP_BEGIN_NAMESPACE_STD
  30
  31 #if _LIBCPP_STD_VER >= 17
  32
  33 namespace __itoa {
  34
  35 template <typename _Tp, typename = void>
  36 struct _LIBCPP_HIDDEN __traits_base;
  37
  38 template <typename _Tp>
  39 struct _LIBCPP_HIDDEN __traits_base<_Tp, __enable_if_t<sizeof(_Tp) <= sizeof(uint32_t)>> {
  40   using type = uint32_t;
  41
  42   /// The width estimation using a log10 algorithm.
  43   ///
  44   /// The algorithm is based on
  45   /// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
  46   /// Instead of using IntegerLogBase2 it uses __libcpp_clz. Since that
  47   /// function requires its input to have at least one bit set the value of
  48   /// zero is set to one. This means the first element of the lookup table is
  49   /// zero.
  50   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI int __width(_Tp __v) {
  51     auto __t = (32 - std::__libcpp_clz(static_cast<type>(__v | 1))) * 1233 >> 12;
  52     return __t - (__v < __itoa::__pow10_32[__t]) + 1;
  53   }
  54
  55   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI char* __convert(char* __p, _Tp __v) {
  56     return __itoa::__base_10_u32(__p, __v);
  57   }
  58
  59   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI decltype(__pow10_32)& __pow() {
  60     return __itoa::__pow10_32;
  61   }
  62 };
  63
  64 template <typename _Tp>
  65 struct _LIBCPP_HIDDEN __traits_base<_Tp, __enable_if_t<sizeof(_Tp) == sizeof(uint64_t)>> {
  66   using type = uint64_t;
  67
  68   /// The width estimation using a log10 algorithm.
  69   ///
  70   /// The algorithm is based on
  71   /// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
  72   /// Instead of using IntegerLogBase2 it uses __libcpp_clz. Since that
  73   /// function requires its input to have at least one bit set the value of
  74   /// zero is set to one. This means the first element of the lookup table is
  75   /// zero.
  76   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI int __width(_Tp __v) {
  77     auto __t = (64 - std::__libcpp_clz(static_cast<type>(__v | 1))) * 1233 >> 12;
  78     return __t - (__v < __itoa::__pow10_64[__t]) + 1;
  79   }
  80
  81   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI char* __convert(char* __p, _Tp __v) {
  82     return __itoa::__base_10_u64(__p, __v);
  83   }
  84
  85   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI decltype(__pow10_64)& __pow() {
  86     return __itoa::__pow10_64;
  87   }
  88 };
  89
  90 #  ifndef _LIBCPP_HAS_NO_INT128
  91 template <typename _Tp>
  92 struct _LIBCPP_HIDDEN __traits_base<_Tp, __enable_if_t<sizeof(_Tp) == sizeof(__uint128_t)> > {
  93   using type = __uint128_t;
  94
  95   /// The width estimation using a log10 algorithm.
  96   ///
  97   /// The algorithm is based on
  98   /// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
  99   /// Instead of using IntegerLogBase2 it uses __libcpp_clz. Since that
 100   /// function requires its input to have at least one bit set the value of
 101   /// zero is set to one. This means the first element of the lookup table is
 102   /// zero.
 103   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI int __width(_Tp __v) {
 104     _LIBCPP_ASSERT_UNCATEGORIZED(
 105         __v > numeric_limits<uint64_t>::max(), "The optimizations for this algorithm fail when this isn't true.");
 106     // There's always a bit set in the upper 64-bits.
 107     auto __t = (128 - std::__libcpp_clz(static_cast<uint64_t>(__v >> 64))) * 1233 >> 12;
 108     _LIBCPP_ASSERT_UNCATEGORIZED(__t >= __itoa::__pow10_128_offset, "Index out of bounds");
 109     // __t is adjusted since the lookup table misses the lower entries.
 110     return __t - (__v < __itoa::__pow10_128[__t - __itoa::__pow10_128_offset]) + 1;
 111   }
 112
 113   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI char* __convert(char* __p, _Tp __v) {
 114     return __itoa::__base_10_u128(__p, __v);
 115   }
 116
 117   // TODO FMT This pow function should get an index.
 118   // By moving this to its own header it can be reused by the pow function in to_chars_base_10.
 119   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI decltype(__pow10_128)& __pow() {
 120     return __itoa::__pow10_128;
 121   }
 122 };
 123 #  endif
 124
 125 template <typename _Tp>
 126 inline _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI bool
 127 __mul_overflowed(unsigned char __a, _Tp __b, unsigned char& __r) {
 128   auto __c = __a * __b;
 129   __r      = __c;
 130   return __c > numeric_limits<unsigned char>::max();
 131 }
 132
 133 template <typename _Tp>
 134 inline _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI bool
 135 __mul_overflowed(unsigned short __a, _Tp __b, unsigned short& __r) {
 136   auto __c = __a * __b;
 137   __r      = __c;
 138   return __c > numeric_limits<unsigned short>::max();
 139 }
 140
 141 template <typename _Tp>
 142 inline _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI bool __mul_overflowed(_Tp __a, _Tp __b, _Tp& __r) {
 143   static_assert(is_unsigned<_Tp>::value, "");
 144   return __builtin_mul_overflow(__a, __b, &__r);
 145 }
 146
 147 template <typename _Tp, typename _Up>
 148 inline _LIBCPP_HIDE_FROM_ABI bool _LIBCPP_CONSTEXPR_SINCE_CXX23 __mul_overflowed(_Tp __a, _Up __b, _Tp& __r) {
 149   return __itoa::__mul_overflowed(__a, static_cast<_Tp>(__b), __r);
 150 }
 151
 152 template <typename _Tp>
 153 struct _LIBCPP_HIDDEN __traits : __traits_base<_Tp> {
 154   static constexpr int digits = numeric_limits<_Tp>::digits10 + 1;
 155   using __traits_base<_Tp>::__pow;
 156   using typename __traits_base<_Tp>::type;
 157
 158   // precondition: at least one non-zero character available
 159   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI char const*
 160   __read(char const* __p, char const* __ep, type& __a, type& __b) {
 161     type __cprod[digits];
 162     int __j = digits - 1;
 163     int __i = digits;
 164     do {
 165       if (*__p < '0' || *__p > '9')
 166         break;
 167       __cprod[--__i] = *__p++ - '0';
 168     } while (__p != __ep && __i != 0);
 169
 170     __a = __inner_product(__cprod + __i + 1, __cprod + __j, __pow() + 1, __cprod[__i]);
 171     if (__itoa::__mul_overflowed(__cprod[__j], __pow()[__j - __i], __b))
 172       --__p;
 173     return __p;
 174   }
 175
 176   template <typename _It1, typename _It2, class _Up>
 177   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI _Up
 178   __inner_product(_It1 __first1, _It1 __last1, _It2 __first2, _Up __init) {
 179     for (; __first1 < __last1; ++__first1, ++__first2)
 180       __init = __init + *__first1 * *__first2;
 181     return __init;
 182   }
 183 };
 184
 185 } // namespace __itoa
 186
 187 template <typename _Tp>
 188 inline _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI _Tp __complement(_Tp __x) {
 189   static_assert(is_unsigned<_Tp>::value, "cast to unsigned first");
 190   return _Tp(~__x + 1);
 191 }
 192
 193 #endif // _LIBCPP_STD_VER >= 17
 194
 195 _LIBCPP_END_NAMESPACE_STD
 196
 197 _LIBCPP_POP_MACROS
 198
 199 #endif // _LIBCPP___CHARCONV_TRAITS