1 | /* Copyright 2015 The TensorFlow Authors. All Rights Reserved. |
2 | |
3 | Licensed under the Apache License, Version 2.0 (the "License"); |
4 | you may not use this file except in compliance with the License. |
5 | You may obtain a copy of the License at |
6 | |
7 | http://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, |
11 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | See the License for the specific language governing permissions and |
13 | limitations under the License. |
14 | ==============================================================================*/ |
15 | |
16 | #include "tensorflow/tsl/platform/strcat.h" |
17 | |
18 | #include <stdarg.h> |
19 | #include <stdint.h> |
20 | #include <stdio.h> |
21 | #include <string.h> |
22 | |
23 | #include <algorithm> |
24 | |
25 | #include "absl/meta/type_traits.h" |
26 | #include "tensorflow/tsl/platform/logging.h" |
27 | |
28 | namespace tsl { |
29 | namespace strings { |
30 | |
31 | AlphaNum::AlphaNum(Hex hex) { |
32 | char *const end = &digits_[kFastToBufferSize]; |
33 | char *writer = end; |
34 | uint64 value = hex.value; |
35 | uint64 width = hex.spec; |
36 | // We accomplish minimum width by OR'ing in 0x10000 to the user's value, |
37 | // where 0x10000 is the smallest hex number that is as wide as the user |
38 | // asked for. |
39 | uint64 mask = (static_cast<uint64>(1) << (width - 1) * 4) | value; |
40 | static const char hexdigits[] = "0123456789abcdef" ; |
41 | do { |
42 | *--writer = hexdigits[value & 0xF]; |
43 | value >>= 4; |
44 | mask >>= 4; |
45 | } while (mask != 0); |
46 | piece_ = StringPiece(writer, end - writer); |
47 | } |
48 | |
49 | // ---------------------------------------------------------------------- |
50 | // StrCat() |
51 | // This merges the given strings or integers, with no delimiter. This |
52 | // is designed to be the fastest possible way to construct a string out |
53 | // of a mix of raw C strings, StringPieces, strings, and integer values. |
54 | // ---------------------------------------------------------------------- |
55 | |
56 | // Append is merely a version of memcpy that returns the address of the byte |
57 | // after the area just overwritten. It comes in multiple flavors to minimize |
58 | // call overhead. |
59 | static char *Append1(char *out, const AlphaNum &x) { |
60 | memcpy(out, x.data(), x.size()); |
61 | return out + x.size(); |
62 | } |
63 | |
64 | static char *Append2(char *out, const AlphaNum &x1, const AlphaNum &x2) { |
65 | memcpy(out, x1.data(), x1.size()); |
66 | out += x1.size(); |
67 | |
68 | memcpy(out, x2.data(), x2.size()); |
69 | return out + x2.size(); |
70 | } |
71 | |
72 | static char *Append4(char *out, const AlphaNum &x1, const AlphaNum &x2, |
73 | const AlphaNum &x3, const AlphaNum &x4) { |
74 | memcpy(out, x1.data(), x1.size()); |
75 | out += x1.size(); |
76 | |
77 | memcpy(out, x2.data(), x2.size()); |
78 | out += x2.size(); |
79 | |
80 | memcpy(out, x3.data(), x3.size()); |
81 | out += x3.size(); |
82 | |
83 | memcpy(out, x4.data(), x4.size()); |
84 | return out + x4.size(); |
85 | } |
86 | |
87 | string StrCat(const AlphaNum &a) { return string(a.data(), a.size()); } |
88 | |
89 | string StrCat(const AlphaNum &a, const AlphaNum &b) { |
90 | string result(a.size() + b.size(), '\0'); |
91 | char *const begin = &*result.begin(); |
92 | char *out = Append2(begin, a, b); |
93 | DCHECK_EQ(out, begin + result.size()); |
94 | return result; |
95 | } |
96 | |
97 | string StrCat(const AlphaNum &a, const AlphaNum &b, const AlphaNum &c) { |
98 | string result(a.size() + b.size() + c.size(), '\0'); |
99 | char *const begin = &*result.begin(); |
100 | char *out = Append2(begin, a, b); |
101 | out = Append1(out, c); |
102 | DCHECK_EQ(out, begin + result.size()); |
103 | return result; |
104 | } |
105 | |
106 | string StrCat(const AlphaNum &a, const AlphaNum &b, const AlphaNum &c, |
107 | const AlphaNum &d) { |
108 | string result(a.size() + b.size() + c.size() + d.size(), '\0'); |
109 | char *const begin = &*result.begin(); |
110 | char *out = Append4(begin, a, b, c, d); |
111 | DCHECK_EQ(out, begin + result.size()); |
112 | return result; |
113 | } |
114 | |
115 | namespace { |
116 | // HasMember is true_type or false_type, depending on whether or not |
117 | // T has a __resize_default_init member. Resize will call the |
118 | // __resize_default_init member if it exists, and will call the resize |
119 | // member otherwise. |
120 | template <typename string_type, typename = void> |
121 | struct ResizeUninitializedTraits { |
122 | using HasMember = std::false_type; |
123 | static void Resize(string_type *s, size_t new_size) { s->resize(new_size); } |
124 | }; |
125 | |
126 | // __resize_default_init is provided by libc++ >= 8.0. |
127 | template <typename string_type> |
128 | struct ResizeUninitializedTraits< |
129 | string_type, absl::void_t<decltype(std::declval<string_type &>() |
130 | .__resize_default_init(237))> > { |
131 | using HasMember = std::true_type; |
132 | static void Resize(string_type *s, size_t new_size) { |
133 | s->__resize_default_init(new_size); |
134 | } |
135 | }; |
136 | |
137 | static inline void STLStringResizeUninitialized(string *s, size_t new_size) { |
138 | ResizeUninitializedTraits<string>::Resize(s, new_size); |
139 | } |
140 | |
141 | // Used to ensure exponential growth so that the amortized complexity of |
142 | // increasing the string size by a small amount is O(1), in contrast to |
143 | // O(str->size()) in the case of precise growth. |
144 | // TODO(b/217943845): Would be better to use absl::strings so we don't need to |
145 | // keep cherry-picking performance fixes. |
146 | template <typename string_type> |
147 | void STLStringReserveAmortized(string_type *s, size_t new_size) { |
148 | const size_t cap = s->capacity(); |
149 | if (new_size > cap) { |
150 | // Make sure to always grow by at least a factor of 2x. |
151 | s->reserve((std::max)(new_size, 2 * cap)); |
152 | } |
153 | } |
154 | |
155 | // Like STLStringResizeUninitialized(str, new_size), except guaranteed to use |
156 | // exponential growth so that the amortized complexity of increasing the string |
157 | // size by a small amount is O(1), in contrast to O(str->size()) in the case of |
158 | // precise growth. |
159 | template <typename string_type> |
160 | void STLStringResizeUninitializedAmortized(string_type *s, size_t new_size) { |
161 | STLStringReserveAmortized(s, new_size); |
162 | STLStringResizeUninitialized(s, new_size); |
163 | } |
164 | |
165 | } // namespace |
166 | namespace internal { |
167 | |
168 | // Do not call directly - these are not part of the public API. |
169 | string CatPieces(std::initializer_list<StringPiece> pieces) { |
170 | size_t total_size = 0; |
171 | for (const StringPiece piece : pieces) total_size += piece.size(); |
172 | string result(total_size, '\0'); |
173 | |
174 | char *const begin = &*result.begin(); |
175 | char *out = begin; |
176 | for (const StringPiece piece : pieces) { |
177 | const size_t this_size = piece.size(); |
178 | memcpy(out, piece.data(), this_size); |
179 | out += this_size; |
180 | } |
181 | DCHECK_EQ(out, begin + result.size()); |
182 | return result; |
183 | } |
184 | |
185 | // It's possible to call StrAppend with a StringPiece that is itself a fragment |
186 | // of the string we're appending to. However the results of this are random. |
187 | // Therefore, check for this in debug mode. Use unsigned math so we only have |
188 | // to do one comparison. |
189 | #define DCHECK_NO_OVERLAP(dest, src) \ |
190 | DCHECK_GE(uintptr_t((src).data() - (dest).data()), uintptr_t((dest).size())) |
191 | |
192 | void AppendPieces(string *result, std::initializer_list<StringPiece> pieces) { |
193 | size_t old_size = result->size(); |
194 | size_t total_size = old_size; |
195 | for (const StringPiece piece : pieces) { |
196 | DCHECK_NO_OVERLAP(*result, piece); |
197 | total_size += piece.size(); |
198 | } |
199 | STLStringResizeUninitializedAmortized(result, total_size); |
200 | |
201 | char *const begin = &*result->begin(); |
202 | char *out = begin + old_size; |
203 | for (const StringPiece piece : pieces) { |
204 | const size_t this_size = piece.size(); |
205 | memcpy(out, piece.data(), this_size); |
206 | out += this_size; |
207 | } |
208 | DCHECK_EQ(out, begin + result->size()); |
209 | } |
210 | |
211 | } // namespace internal |
212 | |
213 | void StrAppend(string *result, const AlphaNum &a) { |
214 | DCHECK_NO_OVERLAP(*result, a); |
215 | result->append(a.data(), a.size()); |
216 | } |
217 | |
218 | void StrAppend(string *result, const AlphaNum &a, const AlphaNum &b) { |
219 | DCHECK_NO_OVERLAP(*result, a); |
220 | DCHECK_NO_OVERLAP(*result, b); |
221 | string::size_type old_size = result->size(); |
222 | STLStringResizeUninitializedAmortized(result, old_size + a.size() + b.size()); |
223 | char *const begin = &*result->begin(); |
224 | char *out = Append2(begin + old_size, a, b); |
225 | DCHECK_EQ(out, begin + result->size()); |
226 | } |
227 | |
228 | void StrAppend(string *result, const AlphaNum &a, const AlphaNum &b, |
229 | const AlphaNum &c) { |
230 | DCHECK_NO_OVERLAP(*result, a); |
231 | DCHECK_NO_OVERLAP(*result, b); |
232 | DCHECK_NO_OVERLAP(*result, c); |
233 | string::size_type old_size = result->size(); |
234 | STLStringResizeUninitializedAmortized( |
235 | result, old_size + a.size() + b.size() + c.size()); |
236 | char *const begin = &*result->begin(); |
237 | char *out = Append2(begin + old_size, a, b); |
238 | out = Append1(out, c); |
239 | DCHECK_EQ(out, begin + result->size()); |
240 | } |
241 | |
242 | void StrAppend(string *result, const AlphaNum &a, const AlphaNum &b, |
243 | const AlphaNum &c, const AlphaNum &d) { |
244 | DCHECK_NO_OVERLAP(*result, a); |
245 | DCHECK_NO_OVERLAP(*result, b); |
246 | DCHECK_NO_OVERLAP(*result, c); |
247 | DCHECK_NO_OVERLAP(*result, d); |
248 | string::size_type old_size = result->size(); |
249 | STLStringResizeUninitializedAmortized( |
250 | result, old_size + a.size() + b.size() + c.size() + d.size()); |
251 | char *const begin = &*result->begin(); |
252 | char *out = Append4(begin + old_size, a, b, c, d); |
253 | DCHECK_EQ(out, begin + result->size()); |
254 | } |
255 | |
256 | } // namespace strings |
257 | } // namespace tsl |
258 | |