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 #pragma once
15
16 // This file provides functions for writing string representations of a few
17 // types to character buffers. Generally, the generic ToString function defined
18 // in "pw_string/to_string.h" should be used instead of these functions.
19
20 #include <array>
21 #include <cstdint>
22 #include <string_view>
23 #include <type_traits>
24
25 #include "lib/stdcompat/bit.h"
26 #include "pw_span/span.h"
27 #include "pw_status/status_with_size.h"
28 #include "pw_string/util.h"
29
30 namespace pw::string {
31
32 // Returns the number of digits in the decimal representation of the provided
33 // non-negative integer. Returns 1 for 0 or 1 + log base 10 for other numbers.
34 constexpr uint_fast8_t DecimalDigitCount(uint64_t integer);
35
36 // Returns the number of digits in the hexadecimal representation of the
37 // provided non-negative integer.
HexDigitCount(uint64_t integer)38 constexpr uint_fast8_t HexDigitCount(uint64_t integer) {
39 return static_cast<uint_fast8_t>((64 - __builtin_clzll(integer | 1u) + 3) /
40 4);
41 }
42
43 // Writes an integer as a null-terminated string in base 10. Returns the number
44 // of characters written, excluding the null terminator, and the status.
45 //
46 // Numbers are never truncated; if the entire number does not fit, only a null
47 // terminator is written and the status is RESOURCE_EXHAUSTED.
48 //
49 // IntToString is templated, but a single 64-bit integer implementation is used
50 // for all integer types. The template is used for two reasons:
51 //
52 // 1. IntToString(int64_t) and IntToString(uint64_t) overloads are ambiguous
53 // when called with types other than int64_t or uint64_t. Using the
54 // template allows IntToString to be called with any integral type.
55 //
56 // 2. Templating IntToString allows the compiler to emit small functions like
57 // IntToString<int> or IntToString<short> that perform casting / sign
58 // extension on the various integer types. This saves code size, since call
59 // sites pass their arguments directly and casting instructions are shared.
60 //
61 template <typename T>
IntToString(T value,span<char> buffer)62 constexpr StatusWithSize IntToString(T value, span<char> buffer) {
63 if constexpr (std::is_signed_v<T>) {
64 return IntToString<int64_t>(value, buffer);
65 } else {
66 return IntToString<uint64_t>(value, buffer);
67 }
68 }
69
70 // Writes an integer as a hexadecimal string. Semantics match IntToString. The
71 // output is lowercase without a leading 0x. min_width adds leading zeroes such
72 // that the final string is at least the specified number of characters wide.
73 StatusWithSize IntToHexString(uint64_t value,
74 span<char> buffer,
75 uint_fast8_t min_width = 0);
76
77 // Rounds a floating point number to an integer and writes it as a
78 // null-terminated string. Returns the number of characters written, excluding
79 // the null terminator, and the status.
80 //
81 // Numbers are never truncated; if the entire number does not fit, only a null
82 // terminator is written and the status is RESOURCE_EXHAUSTED.
83 //
84 // WARNING: This is NOT a fully-functioning float-printing implementation! It
85 // simply outputs the closest integer, "inf", or "NaN". Floating point numbers
86 // too large to represent as a 64-bit int are treated as infinite.
87 //
88 // Examples:
89 //
90 // FloatAsIntToString(1.25, buffer) -> writes "1" to the buffer
91 // FloatAsIntToString(-4.9, buffer) -> writes "-5" to the buffer
92 // FloatAsIntToString(3.5e20, buffer) -> writes "inf" to the buffer
93 // FloatAsIntToString(INFINITY, buffer) -> writes "-inf" to the buffer
94 // FloatAsIntToString(-NAN, buffer) -> writes "-NaN" to the buffer
95 //
96 StatusWithSize FloatAsIntToString(float value, span<char> buffer);
97
98 // Writes a bool as "true" or "false". Semantics match CopyEntireString.
99 StatusWithSize BoolToString(bool value, span<char> buffer);
100
101 // String used to represent null pointers.
102 inline constexpr std::string_view kNullPointerString("(null)");
103
104 // Writes the pointer's address or kNullPointerString. Semantics match
105 // CopyEntireString.
106 StatusWithSize PointerToString(const void* pointer, span<char> buffer);
107
108 // Specialized form of pw::string::Copy which supports nullptr values.
109 //
110 // Copies the string to the buffer, truncating if the full string does not fit.
111 // Always null terminates if buffer.size() > 0.
112 //
113 // If value is a nullptr, then "(null)" is used as a fallback.
114 //
115 // Returns the number of characters written, excluding the null terminator. If
116 // the string is truncated, the status is RESOURCE_EXHAUSTED.
CopyStringOrNull(std::string_view value,span<char> buffer)117 inline StatusWithSize CopyStringOrNull(std::string_view value,
118 span<char> buffer) {
119 return Copy(value, buffer);
120 }
CopyStringOrNull(const char * value,span<char> buffer)121 inline StatusWithSize CopyStringOrNull(const char* value, span<char> buffer) {
122 if (value == nullptr) {
123 return PointerToString(value, buffer);
124 }
125 return Copy(value, buffer);
126 }
127
128 // Copies the string to the buffer, if the entire string fits. Always null
129 // terminates if buffer.size() > 0.
130 //
131 // If value is a nullptr, then "(null)" is used as a fallback.
132 //
133 // Returns the number of characters written, excluding the null terminator. If
134 // the full string does not fit, only a null terminator is written and the
135 // status is RESOURCE_EXHAUSTED.
136 StatusWithSize CopyEntireStringOrNull(std::string_view value,
137 span<char> buffer);
138
139 // Same as the string_view form of CopyEntireString, except that if value is a
140 // nullptr, then "(null)" is used as a fallback.
CopyEntireStringOrNull(const char * value,span<char> buffer)141 inline StatusWithSize CopyEntireStringOrNull(const char* value,
142 span<char> buffer) {
143 if (value == nullptr) {
144 return PointerToString(value, buffer);
145 }
146 return CopyEntireStringOrNull(std::string_view(value), buffer);
147 }
148
149 // This function is a fallback that is called if by ToString if no overload
150 // matches. No definition is provided, so attempting to print an unsupported
151 // type causes a linker error.
152 //
153 // Applications may define pw::string::UnknownTypeToString to support generic
154 // printing for unknown types, if desired. Implementations must follow the
155 // ToString semantics.
156 template <typename T>
157 StatusWithSize UnknownTypeToString(const T& value, span<char> buffer);
158
159 // Implementations
160 namespace internal {
161
162 // Powers of 10 (except 0) as an array. This table is fairly large (160 B), but
163 // avoids having to recalculate these values for each DecimalDigitCount call.
164 inline constexpr std::array<uint64_t, 20> kPowersOf10{
165 0ull,
166 10ull, // 10^1
167 100ull, // 10^2
168 1000ull, // 10^3
169 10000ull, // 10^4
170 100000ull, // 10^5
171 1000000ull, // 10^6
172 10000000ull, // 10^7
173 100000000ull, // 10^8
174 1000000000ull, // 10^9
175 10000000000ull, // 10^10
176 100000000000ull, // 10^11
177 1000000000000ull, // 10^12
178 10000000000000ull, // 10^13
179 100000000000000ull, // 10^14
180 1000000000000000ull, // 10^15
181 10000000000000000ull, // 10^16
182 100000000000000000ull, // 10^17
183 1000000000000000000ull, // 10^18
184 10000000000000000000ull, // 10^19
185 };
186
HandleExhaustedBuffer(span<char> buffer)187 constexpr StatusWithSize HandleExhaustedBuffer(span<char> buffer) {
188 if (!buffer.empty()) {
189 buffer[0] = '\0';
190 }
191 return StatusWithSize::ResourceExhausted();
192 }
193
194 } // namespace internal
195
DecimalDigitCount(uint64_t integer)196 constexpr uint_fast8_t DecimalDigitCount(uint64_t integer) {
197 // This fancy piece of code takes the log base 2, then approximates the
198 // change-of-base formula by multiplying by 1233 / 4096.
199 const uint_fast8_t log_10 = static_cast<uint_fast8_t>(
200 (64 - cpp20::countl_zero(integer | 1)) * 1233 >> 12);
201
202 // Adjust the estimated log base 10 by comparing against the power of 10.
203 return static_cast<uint_fast8_t>(
204 log_10 + (integer < internal::kPowersOf10[log_10] ? 0u : 1u));
205 }
206
207 // std::to_chars is available for integers in recent versions of GCC. I looked
208 // into switching to std::to_chars instead of this implementation. std::to_chars
209 // increased binary size by 160 B on an -Os build (even after removing
210 // DecimalDigitCount and its table). I didn't measure performance, but I don't
211 // think std::to_chars will be faster, so I kept this implementation for now.
212 template <>
IntToString(uint64_t value,span<char> buffer)213 constexpr StatusWithSize IntToString(uint64_t value, span<char> buffer) {
214 constexpr uint32_t base = 10;
215 constexpr uint32_t max_uint32_base_power = 1'000'000'000;
216 constexpr uint_fast8_t max_uint32_base_power_exponent = 9;
217
218 const uint_fast8_t total_digits = DecimalDigitCount(value);
219
220 if (total_digits >= buffer.size()) {
221 return internal::HandleExhaustedBuffer(buffer);
222 }
223
224 buffer[total_digits] = '\0';
225
226 uint_fast8_t remaining = total_digits;
227 while (remaining > 0u) {
228 uint32_t lower_digits = 0; // the value of the lower digits to write
229 uint_fast8_t digit_count = 0; // the number of lower digits to write
230
231 // 64-bit division is slow on 32-bit platforms, so print large numbers in
232 // 32-bit chunks to minimize the number of 64-bit divisions.
233 if (value <= std::numeric_limits<uint32_t>::max()) {
234 lower_digits = static_cast<uint32_t>(value);
235 digit_count = remaining;
236 } else {
237 lower_digits = static_cast<uint32_t>(value % max_uint32_base_power);
238 digit_count = max_uint32_base_power_exponent;
239 value /= max_uint32_base_power;
240 }
241
242 // Write the specified number of digits, with leading 0s.
243 for (uint_fast8_t i = 0; i < digit_count; ++i) {
244 buffer[--remaining] = static_cast<char>(lower_digits % base + '0');
245 lower_digits /= base;
246 }
247 }
248 return StatusWithSize(total_digits);
249 }
250
251 template <>
252 constexpr StatusWithSize IntToString(int64_t value, span<char> buffer) {
253 if (value >= 0) {
254 return IntToString<uint64_t>(static_cast<uint64_t>(value), buffer);
255 }
256
257 // Write as an unsigned number, but leave room for the leading minus sign.
258 // Do not use std::abs since it fails for the minimum value integer.
259 const uint64_t absolute_value = -static_cast<uint64_t>(value);
260 auto result = IntToString<uint64_t>(
261 absolute_value, buffer.empty() ? buffer : buffer.subspan(1));
262
263 if (result.ok()) {
264 buffer[0] = '-';
265 return StatusWithSize(result.size() + 1);
266 }
267
268 return internal::HandleExhaustedBuffer(buffer);
269 }
270
271 } // namespace pw::string
272