1 // Copyright 2019 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_string/type_to_string.h"
16
17 #include <cmath>
18 #include <cstddef>
19 #include <cstring>
20 #include <limits>
21
22 namespace pw::string {
23 namespace {
24
25 // Powers of 10 (except 0) as an array. This table is fairly large (160 B), but
26 // avoids having to recalculate these values for each DecimalDigitCount call.
27 constexpr std::array<uint64_t, 20> kPowersOf10{
28 0ull,
29 10ull, // 10^1
30 100ull, // 10^2
31 1000ull, // 10^3
32 10000ull, // 10^4
33 100000ull, // 10^5
34 1000000ull, // 10^6
35 10000000ull, // 10^7
36 100000000ull, // 10^8
37 1000000000ull, // 10^9
38 10000000000ull, // 10^10
39 100000000000ull, // 10^11
40 1000000000000ull, // 10^12
41 10000000000000ull, // 10^13
42 100000000000000ull, // 10^14
43 1000000000000000ull, // 10^15
44 10000000000000000ull, // 10^16
45 100000000000000000ull, // 10^17
46 1000000000000000000ull, // 10^18
47 10000000000000000000ull, // 10^19
48 };
49
HandleExhaustedBuffer(std::span<char> buffer)50 StatusWithSize HandleExhaustedBuffer(std::span<char> buffer) {
51 if (!buffer.empty()) {
52 buffer[0] = '\0';
53 }
54 return StatusWithSize::ResourceExhausted();
55 }
56
57 } // namespace
58
DecimalDigitCount(uint64_t integer)59 uint_fast8_t DecimalDigitCount(uint64_t integer) {
60 // This fancy piece of code takes the log base 2, then approximates the
61 // change-of-base formula by multiplying by 1233 / 4096.
62 // TODO(hepler): Replace __builtin_clzll with std::countl_zeros in C++20.
63 const uint_fast8_t log_10 = (64 - __builtin_clzll(integer | 1)) * 1233 >> 12;
64
65 // Adjust the estimated log base 10 by comparing against the power of 10.
66 return log_10 + (integer < kPowersOf10[log_10] ? 0u : 1u);
67 }
68
69 // std::to_chars is available for integers in recent versions of GCC. I looked
70 // into switching to std::to_chars instead of this implementation. std::to_chars
71 // increased binary size by 160 B on an -Os build (even after removing
72 // DecimalDigitCount and its table). I didn't measure performance, but I don't
73 // think std::to_chars will be faster, so I kept this implementation for now.
74 template <>
IntToString(uint64_t value,std::span<char> buffer)75 StatusWithSize IntToString(uint64_t value, std::span<char> buffer) {
76 constexpr uint32_t base = 10;
77 constexpr uint32_t max_uint32_base_power = 1'000'000'000;
78 constexpr uint_fast8_t max_uint32_base_power_exponent = 9;
79
80 const uint_fast8_t total_digits = DecimalDigitCount(value);
81
82 if (total_digits >= buffer.size()) {
83 return HandleExhaustedBuffer(buffer);
84 }
85
86 buffer[total_digits] = '\0';
87
88 uint_fast8_t remaining = total_digits;
89 while (remaining > 0u) {
90 uint32_t lower_digits; // the value of the lower digits to write
91 uint_fast8_t digit_count; // the number of lower digits to write
92
93 // 64-bit division is slow on 32-bit platforms, so print large numbers in
94 // 32-bit chunks to minimize the number of 64-bit divisions.
95 if (value <= std::numeric_limits<uint32_t>::max()) {
96 lower_digits = value;
97 digit_count = remaining;
98 } else {
99 lower_digits = value % max_uint32_base_power;
100 digit_count = max_uint32_base_power_exponent;
101 value /= max_uint32_base_power;
102 }
103
104 // Write the specified number of digits, with leading 0s.
105 for (uint_fast8_t i = 0; i < digit_count; ++i) {
106 buffer[--remaining] = lower_digits % base + '0';
107 lower_digits /= base;
108 }
109 }
110 return StatusWithSize(total_digits);
111 }
112
IntToHexString(uint64_t value,std::span<char> buffer,uint_fast8_t min_width)113 StatusWithSize IntToHexString(uint64_t value,
114 std::span<char> buffer,
115 uint_fast8_t min_width) {
116 const uint_fast8_t digits = std::max(HexDigitCount(value), min_width);
117
118 if (digits >= buffer.size()) {
119 return HandleExhaustedBuffer(buffer);
120 }
121
122 for (int i = digits - 1; i >= 0; --i) {
123 buffer[i] = "0123456789abcdef"[value & 0xF];
124 value >>= 4;
125 }
126
127 buffer[digits] = '\0';
128 return StatusWithSize(digits);
129 }
130
131 template <>
IntToString(int64_t value,std::span<char> buffer)132 StatusWithSize IntToString(int64_t value, std::span<char> buffer) {
133 if (value >= 0) {
134 return IntToString<uint64_t>(value, buffer);
135 }
136
137 // Write as an unsigned number, but leave room for the leading minus sign.
138 auto result = IntToString<uint64_t>(
139 std::abs(value), buffer.empty() ? buffer : buffer.subspan(1));
140
141 if (result.ok()) {
142 buffer[0] = '-';
143 return StatusWithSize(result.size() + 1);
144 }
145
146 return HandleExhaustedBuffer(buffer);
147 }
148
149 // TODO(hepler): Look into using the float overload of std::to_chars when it is
150 // available.
FloatAsIntToString(float value,std::span<char> buffer)151 StatusWithSize FloatAsIntToString(float value, std::span<char> buffer) {
152 // If it's finite and fits in an int64_t, print it as a rounded integer.
153 if (std::isfinite(value) &&
154 std::abs(value) <
155 static_cast<float>(std::numeric_limits<int64_t>::max())) {
156 return IntToString<int64_t>(static_cast<int64_t>(std::roundf(value)),
157 buffer);
158 }
159
160 // Otherwise, print inf or NaN, if they fit.
161 if (const size_t written = 3 + std::signbit(value); written < buffer.size()) {
162 char* out = buffer.data();
163 if (std::signbit(value)) {
164 *out++ = '-';
165 }
166 std::memcpy(out, std::isnan(value) ? "NaN" : "inf", sizeof("NaN"));
167 return StatusWithSize(written);
168 }
169
170 return HandleExhaustedBuffer(buffer);
171 }
172
BoolToString(bool value,std::span<char> buffer)173 StatusWithSize BoolToString(bool value, std::span<char> buffer) {
174 return CopyEntireStringOrNull(value ? "true" : "false", buffer);
175 }
176
PointerToString(const void * pointer,std::span<char> buffer)177 StatusWithSize PointerToString(const void* pointer, std::span<char> buffer) {
178 if (pointer == nullptr) {
179 return CopyEntireStringOrNull(kNullPointerString, buffer);
180 }
181 return IntToHexString(reinterpret_cast<uintptr_t>(pointer), buffer);
182 }
183
CopyEntireStringOrNull(const std::string_view & value,std::span<char> buffer)184 StatusWithSize CopyEntireStringOrNull(const std::string_view& value,
185 std::span<char> buffer) {
186 if (value.size() >= buffer.size()) {
187 return HandleExhaustedBuffer(buffer);
188 }
189
190 std::memcpy(buffer.data(), value.data(), value.size());
191 buffer[value.size()] = '\0';
192 return StatusWithSize(value.size());
193 }
194
195 } // namespace pw::string
196