Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

Differential D96221 Diff 321994 libcxx/include/__format_itoa

Changeset View

Standalone View

View Options

libcxx/include/__format_itoa

  • This file was added.
// -*- C++ -*-
//===------------------------ __format_itoa -------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef _LIBCPP___FORMAT_ITOA
#define _LIBCPP___FORMAT_ITOA
/**
* Helper header for convertion integrals to strings.
*
* This duplicates some of the effort of std::to_chars but this version has a
* slightly different goal. The goal is to offer routines to aid the format
* header. The header requires C++20 support due to using the bit header.
*
* The unit test can be found there. (libcxx/test/std/utilities/format/__itoa)
*
* The number of digits available for the various base types are:
* type | digits full | digits partial
* ------------------------------------------
* int32_t* | 9 | 10
* uint32_t | 9 | 10
* int64_t* | 18 | 19
* uint64_t | 19 | 20
* __int128_t* | 38 | 39
* __uint128_t | 38 | 39
*
* *) An additional character may be required for the sign.
*
* TODO FMT Try to merge this code with the code used for std::to_chars and
* std::to_string.
*/
#include <__config>
#include <array>
#include <bit>
#include <concepts>
#include <iterator>
#include <string>
#include <type_traits>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#pragma GCC system_header
#endif
_LIBCPP_PUSH_MACROS
#include <__undef_macros>
_LIBCPP_BEGIN_NAMESPACE_STD
#if _LIBCPP_STD_VER > 17
//
//
// TODO FMT Copy the fixes from D93166 to avoid building on older Clang versions.
//
//
/** The unsigned integral types supported for the __itoa related functions. */
template <class _Tp>
concept __uintX_t =
_VSTD::same_as<_Tp, uint8_t> || _VSTD::same_as<_Tp, uint16_t> ||
_VSTD::same_as<_Tp, uint32_t> || _VSTD::same_as<_Tp, uint64_t>
#ifndef _LIBCPP_HAS_NO_INT128
|| _VSTD::same_as<_Tp, __uint128_t>
#endif
;
/** The signed integral types supported for the __itoa related functions. */
template <class _Tp>
concept __intX_t =
_VSTD::same_as<_Tp, int8_t> || _VSTD::same_as<_Tp, int16_t> ||
_VSTD::same_as<_Tp, int32_t> || _VSTD::same_as<_Tp, int64_t>
#ifndef _LIBCPP_HAS_NO_INT128
|| _VSTD::same_as<_Tp, __int128_t>
#endif
;
/**
* Used to determine the noexcept state of the output functions.
*
* Several functions in this header can be noexcept iff the output operations
* don't throw.
*/
template <class _OutIt>
concept __output_iterator_noexcept =
_VSTD::is_nothrow_move_constructible_v<_OutIt>&&
_VSTD::is_nothrow_copy_constructible_v<_OutIt>&&
requires(_OutIt __out_it) {
noexcept(*__out_it);
noexcept(__out_it++);
noexcept(++__out_it);
};
namespace __itoa {
/**
* Types that are allowed to instantiate in this namespace.
*
* Since several of these functions are optimized for certain types do not
* allow every type in this namespace to be instantiated. The functions in
* the std namespace should cast the types to an appropriate internal type.
*/
template <class _Tp>
concept __internal_integral =
_VSTD::same_as<_Tp, uint32_t> || _VSTD::same_as<_Tp, uint64_t>
#ifndef _LIBCPP_HAS_NO_INT128
|| _VSTD::same_as<_Tp, __uint128_t>
#endif
;
/** Types that should be converted to a uint32_t. */
template <class _Tp>
concept __integral_to_uint32_t =
_VSTD::same_as<_Tp, uint8_t> || _VSTD::same_as<_Tp, uint16_t>;
/** Creates a lookup table with all powers of 10. */
template <__internal_integral _Tp>
consteval auto __create_lut_pow10() {
// _VSTD::numeric_limits<_Tp>::digits10 is rounded down so add 1.
_VSTD::array<_Tp, _VSTD::numeric_limits<_Tp>::digits10 + 1> __result;
__result[0] = 1;
for (size_t __i = 1; __i < __result.size(); ++__i)
__result[__i] = 10 * __result[__i - 1];
return __result;
}
/**
* Creates a lookup table with the bit width mapped to the character width.
*
* The maximum of digits required is based on the first zero bit of a value.
*
* The table for uint8_t would look like:
* _VSTD::array<uint8_t, 9> {
* 1, // zero bit = 0 -> 0
* 1, // zero bit = 1 -> 1
* 1, // zero bit = 2 -> 3
* 1, // zero bit = 3 -> 7
* 2, // zero bit = 4 -> 15
* 2, // zero bit = 5 -> 31
* 2, // zero bit = 6 -> 63
* 3, // zero bit = 7 -> 127
* 3, // zero bit = 8 -> 255
* };
* As can be seen the number of digits is numberic_limits<uint8_t>::digits + 1.
* If an 8 bit value has its leading (7th) bit set the first zero bit would be
* bit 8. That bit isn't available in a 8 bit value, but that doesn't matter
* for this algorithm.
*/
consteval auto __create_lut_character_width_base_10() {
#ifndef _LIBCPP_HAS_NO_INT128
using _Tp = __uint128_t;
#else
using _Tp = uint64_t;
#endif
_VSTD::array<uint8_t, _VSTD::numeric_limits<_Tp>::digits + 1> __result;
_Tp __value = 0;
_Tp __max = 10;
uint8_t __digits = 1;
// Avoid setting the last element, it will fail due to __max overflowing.
for (size_t __i = 0; __i < __result.size() - 1; ++__i) {
if (__value >= __max) {
++__digits;
__max *= 10;
}
__result[__i] = __digits;
__value <<= 1;
__value |= 1;
}
// _VSTD::numeric_limits<_Tp>::digits10 is rounded down so add 1.
__result[__result.size() - 1] = _VSTD::numeric_limits<_Tp>::digits10 + 1;
return __result;
}
template <__internal_integral _Tp>
_LIBCPP_HIDDEN constexpr int __character_width_base_10(_Tp __value) noexcept {
constexpr auto __character_width = __create_lut_character_width_base_10();
constexpr auto __pow10 = __create_lut_pow10<_Tp>();
if (__value == _Tp(0))
return 1;
int __result = __character_width[_VSTD::bit_width(__value)];
_LIBCPP_ASSERT(__result > 0, "No bits set should required 1 digit.");
// Using this branch free code instead of
// if (__value < __pow10[__result - 1]) --__result;
// gives better performance.
__result -= __value < __pow10[__result - 1];
_LIBCPP_ASSERT(__result > 0, "No bits set should required 1 digit.");
return __result;
}
template <__integral_to_uint32_t _Tp>
_LIBCPP_HIDDEN constexpr int __character_width_base_10(_Tp __value) noexcept {
return __character_width_base_10(static_cast<uint32_t>(__value));
}
template <class _CharT>
consteval auto __create_lut_to_buffer_digits_2() {
std::array<_CharT, 200> __result;
_CharT* __ptr = &__result[0];
for (int __i = 0; __i < 10; ++__i)
for (int __j = 0; __j < 10; ++__j) {
*__ptr++ = _CharT('0' + __i);
*__ptr++ = _CharT('0' + __j);
}
return __result;
}
template <class _CharT>
_LIBCPP_HIDDEN constexpr void
__to_buffer_digits_2_base_10(_CharT* __out_it, uint32_t __value) noexcept {
_LIBCPP_ASSERT(__value < 100,
"This function requires only 2 digits in the value.");
constexpr auto __lut = __create_lut_to_buffer_digits_2<_CharT>();
_VSTD::copy_n(&__lut[__value * 2], 2, __out_it);
}
template <class _CharT, _VSTD::same_as<uint32_t> _Tp>
_LIBCPP_HIDDEN constexpr _CharT*
__to_buffer_base_10(_CharT* __out_it, _Tp __value, int __digits) noexcept {
while (__digits >= 2) {
__out_it -= 2;
__digits -= 2;
__to_buffer_digits_2_base_10(__out_it, __value % 100);
__value /= 100;
}
if (__digits)
*--__out_it = _CharT('0' + __value);
return __out_it;
}
template <class _CharT, _VSTD::same_as<uint64_t> _Tp>
_LIBCPP_HIDDEN constexpr _CharT*
__to_buffer_base_10(_CharT* __out_it, _Tp __value, int __digits) noexcept {
// Process the largest fully supported number of digits to the 32 bit version.
// The odd number leads to outputting a single value but that has no
// performance impact.
constexpr int __dispatch_size = 9;
constexpr _Tp __dispatch_value = __create_lut_pow10<_Tp>()[__dispatch_size];
while (__digits >= __dispatch_size) {
__digits -= __dispatch_size;
__out_it = __to_buffer_base_10(
__out_it, static_cast<uint32_t>(__value % __dispatch_value),
__dispatch_size);
__value /= __dispatch_value;
}
if (__digits)
__out_it =
__to_buffer_base_10(__out_it, static_cast<uint32_t>(__value), __digits);
return __out_it;
}
#ifndef _LIBCPP_HAS_NO_INT128
template <class _CharT, _VSTD::same_as<__uint128_t> _Tp>
_LIBCPP_HIDDEN constexpr void __to_buffer_base_10(_CharT* __out_it, _Tp __value,
int __digits) noexcept {
// Process the largest fully supported number of digits to the 64 bit version.
// The odd number leads to outputting a single value but that has no
// performance impact.
constexpr int __dispatch_size = 19;
constexpr _Tp __dispatch_value = __create_lut_pow10<_Tp>()[__dispatch_size];
while (__digits >= __dispatch_size) {
__digits -= __dispatch_size;
__out_it = __to_buffer_base_10(
__out_it, static_cast<uint64_t>(__value % __dispatch_value),
__dispatch_size);
__value /= __dispatch_value;
}
if (__digits)
__to_buffer_base_10(__out_it, static_cast<uint64_t>(__value), __digits);
}
#endif
template <class _CharT, __integral_to_uint32_t _Tp>
_LIBCPP_HIDDEN constexpr void __to_buffer_base_10(_CharT* __out_it, _Tp __value,
int __digits) noexcept {
__to_buffer_base_10(__out_it, static_cast<uint32_t>(__value), __digits);
}
} // namespace __itoa
/**
* Determines the number of characters needed to store a value as a string.
*
* The number of characters doesn't take the locale into account and stores no
* thousands separator.
*
* This version handles non-negative values and doesn't take a character for a
* sign into account.
*
* @returns The number of characters to store the @a __value.
*/
template <__uintX_t _Tp>
_LIBCPP_INLINE_VISIBILITY constexpr int
__character_width_base_10(_Tp __value) noexcept {
return __itoa::__character_width_base_10(__value);
}
/**
* @overload for signed integral values.
*
* When the value is negative it adds one character for the sign.
*/
template <__intX_t _Tp>
_LIBCPP_INLINE_VISIBILITY constexpr int
__character_width_base_10(_Tp __value) noexcept {
if (__value < 0)
return 1 + __itoa::__character_width_base_10(
static_cast<_VSTD::make_unsigned_t<_Tp> >(-__value));
return __itoa::__character_width_base_10(
static_cast<_VSTD::make_unsigned_t<_Tp> >(__value));
}
/**
* An alternative for std::to_chars.
*
* An locale-independent, non-allocating function to convert an integral to its
* text representation. Unlike std::to_chars it has no "last" argument, making
* it easier to use with std::format_to.
*
* This version is specialized for a character output iterator. This avoids
* creating a temporary stack buffer.
*
* @param ___out_it The output iterator to write the text to.
* @param __value The value to write.
*
* @returns An iterator one past the end of the last written character.
*
* @note This implements only the unsigned integral implementation.
*/
template <class _CharT, __uintX_t _Tp>
_LIBCPP_INLINE_VISIBILITY constexpr _CharT*
__to_chars_base_10(_CharT* __out_it, _Tp __value) noexcept {
if (__value == _Tp(0)) {
*__out_it++ = _CharT('0');
return __out_it;
}
int __size = __character_width_base_10(__value);
__out_it += __size;
__itoa::__to_buffer_base_10(__out_it, __value, __size);
return __out_it;
}
/** The unsigned integral implementation for generic output iterators. */
// TODO FMT Use concept _VSTD::output_iterator<_OutIt>
template <class _OutIt, __uintX_t _Tp>
_LIBCPP_INLINE_VISIBILITY constexpr _OutIt __to_chars_base_10(_OutIt __out_it,
_Tp __value)
noexcept(__output_iterator_noexcept<_OutIt>) {
using _CharT = typename _VSTD::iterator_traits<_OutIt>::value_type;
// _VSTD::numeric_limits<_Tp>::digits10 is rounded down so add 1
_CharT __buffer[_VSTD::numeric_limits<_Tp>::digits10 + 1];
auto __last = __to_chars_base_10(__buffer, __value);
return _VSTD::copy(__buffer, __last, __out_it);
}
/** The signed integral implementation of __to_chars_base_10. */
// TODO FMT Use concept _VSTD::output_iterator<_OutIt>
template <class _OutIt, __intX_t _Tp>
_LIBCPP_INLINE_VISIBILITY constexpr _OutIt __to_chars_base_10(_OutIt __out_it,
_Tp __value)
noexcept(__output_iterator_noexcept<_OutIt>) {
using _CharT = typename _VSTD::iterator_traits<_OutIt>::value_type;
if (__value < _Tp(0)) {
*__out_it++ = _CharT('-');
__value = -__value;
}
return __to_chars_base_10(__out_it,
static_cast<_VSTD::make_unsigned_t<_Tp> >(__value));
}
/**
* An alternative for std::to_string and std::to_wstring.
*
* An locale-independent, function to convert an integral to std::basic_string.
* Unlike std::to_string the function is templated on the character type.
* Making it possible to return basic_string types with the character other
* than @c char or @c wchar_t.
*
* @param __value The value to convert.
*
* @returns A std::basic_string with the converted value.
*
* @throws std::bad_alloc from the std::basic_string's constructor.
*/
template <class _CharT, class _Tp>
requires(__uintX_t<_Tp> || __intX_t<_Tp>) _LIBCPP_INLINE_VISIBILITY constexpr
_VSTD::basic_string<_CharT> __to_basic_string(_Tp __value) {
// _VSTD::numeric_limits<_Tp>::digits10 is rounded down so add 1
_CharT __buffer[_VSTD::numeric_limits<_Tp>::digits10 + 2];
auto __last = __to_chars_base_10(__buffer, __value);
return _VSTD::basic_string(__buffer, __last);
}
#endif //_LIBCPP_STD_VER > 17
_LIBCPP_END_NAMESPACE_STD
_LIBCPP_POP_MACROS
#endif // _LIBCPP___FORMAT_ITOA