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(span<char> buffer)50 StatusWithSize HandleExhaustedBuffer(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 = static_cast<uint_fast8_t>(
64 (64 - __builtin_clzll(integer | 1)) * 1233 >> 12);
65
66 // Adjust the estimated log base 10 by comparing against the power of 10.
67 return log_10 + (integer < kPowersOf10[log_10] ? 0u : 1u);
68 }
69
70 // std::to_chars is available for integers in recent versions of GCC. I looked
71 // into switching to std::to_chars instead of this implementation. std::to_chars
72 // increased binary size by 160 B on an -Os build (even after removing
73 // DecimalDigitCount and its table). I didn't measure performance, but I don't
74 // think std::to_chars will be faster, so I kept this implementation for now.
75 template <>
IntToString(uint64_t value,span<char> buffer)76 StatusWithSize IntToString(uint64_t value, span<char> buffer) {
77 constexpr uint32_t base = 10;
78 constexpr uint32_t max_uint32_base_power = 1'000'000'000;
79 constexpr uint_fast8_t max_uint32_base_power_exponent = 9;
80
81 const uint_fast8_t total_digits = DecimalDigitCount(value);
82
83 if (total_digits >= buffer.size()) {
84 return HandleExhaustedBuffer(buffer);
85 }
86
87 buffer[total_digits] = '\0';
88
89 uint_fast8_t remaining = total_digits;
90 while (remaining > 0u) {
91 uint32_t lower_digits; // the value of the lower digits to write
92 uint_fast8_t digit_count; // the number of lower digits to write
93
94 // 64-bit division is slow on 32-bit platforms, so print large numbers in
95 // 32-bit chunks to minimize the number of 64-bit divisions.
96 if (value <= std::numeric_limits<uint32_t>::max()) {
97 lower_digits = static_cast<uint32_t>(value);
98 digit_count = remaining;
99 } else {
100 lower_digits = value % max_uint32_base_power;
101 digit_count = max_uint32_base_power_exponent;
102 value /= max_uint32_base_power;
103 }
104
105 // Write the specified number of digits, with leading 0s.
106 for (uint_fast8_t i = 0; i < digit_count; ++i) {
107 buffer[--remaining] = lower_digits % base + '0';
108 lower_digits /= base;
109 }
110 }
111 return StatusWithSize(total_digits);
112 }
113
IntToHexString(uint64_t value,span<char> buffer,uint_fast8_t min_width)114 StatusWithSize IntToHexString(uint64_t value,
115 span<char> buffer,
116 uint_fast8_t min_width) {
117 const uint_fast8_t digits = std::max(HexDigitCount(value), min_width);
118
119 if (digits >= buffer.size()) {
120 return HandleExhaustedBuffer(buffer);
121 }
122
123 for (int i = digits - 1; i >= 0; --i) {
124 buffer[i] = "0123456789abcdef"[value & 0xF];
125 value >>= 4;
126 }
127
128 buffer[digits] = '\0';
129 return StatusWithSize(digits);
130 }
131
132 template <>
IntToString(int64_t value,span<char> buffer)133 StatusWithSize IntToString(int64_t value, span<char> buffer) {
134 if (value >= 0) {
135 return IntToString<uint64_t>(value, buffer);
136 }
137
138 // Write as an unsigned number, but leave room for the leading minus sign.
139 auto result = IntToString<uint64_t>(
140 std::abs(value), buffer.empty() ? buffer : buffer.subspan(1));
141
142 if (result.ok()) {
143 buffer[0] = '-';
144 return StatusWithSize(result.size() + 1);
145 }
146
147 return HandleExhaustedBuffer(buffer);
148 }
149
FloatAsIntToString(float value,span<char> buffer)150 StatusWithSize FloatAsIntToString(float value, span<char> buffer) {
151 // If it's finite and fits in an int64_t, print it as a rounded integer.
152 if (std::isfinite(value) &&
153 std::abs(value) <
154 static_cast<float>(std::numeric_limits<int64_t>::max())) {
155 return IntToString<int64_t>(static_cast<int64_t>(std::roundf(value)),
156 buffer);
157 }
158
159 // Otherwise, print inf or NaN, if they fit.
160 if (const size_t written = 3 + std::signbit(value); written < buffer.size()) {
161 char* out = buffer.data();
162 if (std::signbit(value)) {
163 *out++ = '-';
164 }
165 std::memcpy(out, std::isnan(value) ? "NaN" : "inf", sizeof("NaN"));
166 return StatusWithSize(written);
167 }
168
169 return HandleExhaustedBuffer(buffer);
170 }
171
BoolToString(bool value,span<char> buffer)172 StatusWithSize BoolToString(bool value, span<char> buffer) {
173 return CopyEntireStringOrNull(value ? "true" : "false", buffer);
174 }
175
PointerToString(const void * pointer,span<char> buffer)176 StatusWithSize PointerToString(const void* pointer, span<char> buffer) {
177 if (pointer == nullptr) {
178 return CopyEntireStringOrNull(kNullPointerString, buffer);
179 }
180 return IntToHexString(reinterpret_cast<uintptr_t>(pointer), buffer);
181 }
182
CopyEntireStringOrNull(const std::string_view & value,span<char> buffer)183 StatusWithSize CopyEntireStringOrNull(const std::string_view& value,
184 span<char> buffer) {
185 if (value.size() >= buffer.size()) {
186 return HandleExhaustedBuffer(buffer);
187 }
188
189 std::memcpy(buffer.data(), value.data(), value.size());
190 buffer[value.size()] = '\0';
191 return StatusWithSize(value.size());
192 }
193
194 } // namespace pw::string
195