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>(std::round(value), 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,std::span<char> buffer)172 StatusWithSize BoolToString(bool value, std::span<char> buffer) {
173 return CopyEntireString(value ? "true" : "false", buffer);
174 }
175
PointerToString(const void * pointer,std::span<char> buffer)176 StatusWithSize PointerToString(const void* pointer, std::span<char> buffer) {
177 if (pointer == nullptr) {
178 return CopyEntireString(kNullPointerString, buffer);
179 }
180 return IntToHexString(reinterpret_cast<uintptr_t>(pointer), buffer);
181 }
182
CopyString(const std::string_view & value,std::span<char> buffer)183 StatusWithSize CopyString(const std::string_view& value,
184 std::span<char> buffer) {
185 if (buffer.empty()) {
186 return StatusWithSize::ResourceExhausted();
187 }
188
189 const size_t copied = value.copy(buffer.data(), buffer.size() - 1);
190 buffer[copied] = '\0';
191
192 return StatusWithSize(
193 copied == value.size() ? OkStatus() : Status::ResourceExhausted(),
194 copied);
195 }
196
CopyEntireString(const std::string_view & value,std::span<char> buffer)197 StatusWithSize CopyEntireString(const std::string_view& value,
198 std::span<char> buffer) {
199 if (value.size() >= buffer.size()) {
200 return HandleExhaustedBuffer(buffer);
201 }
202
203 std::memcpy(buffer.data(), value.data(), value.size());
204 buffer[value.size()] = '\0';
205 return StatusWithSize(value.size());
206 }
207
208 } // namespace pw::string
209