1/* Copyright 2015 The TensorFlow Authors. All Rights Reserved.
2
3Licensed under the Apache License, Version 2.0 (the "License");
4you may not use this file except in compliance with the License.
5You may obtain a copy of the License at
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
9Unless required by applicable law or agreed to in writing, software
10distributed under the License is distributed on an "AS IS" BASIS,
11WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12See the License for the specific language governing permissions and
13limitations 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
28namespace tsl {
29namespace strings {
30
31AlphaNum::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.
59static char *Append1(char *out, const AlphaNum &x) {
60 memcpy(out, x.data(), x.size());
61 return out + x.size();
62}
63
64static 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
72static 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
87string StrCat(const AlphaNum &a) { return string(a.data(), a.size()); }
88
89string 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
97string 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
106string 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
115namespace {
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.
120template <typename string_type, typename = void>
121struct 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.
127template <typename string_type>
128struct 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
137static 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.
146template <typename string_type>
147void 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.
159template <typename string_type>
160void STLStringResizeUninitializedAmortized(string_type *s, size_t new_size) {
161 STLStringReserveAmortized(s, new_size);
162 STLStringResizeUninitialized(s, new_size);
163}
164
165} // namespace
166namespace internal {
167
168// Do not call directly - these are not part of the public API.
169string 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
192void 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
213void StrAppend(string *result, const AlphaNum &a) {
214 DCHECK_NO_OVERLAP(*result, a);
215 result->append(a.data(), a.size());
216}
217
218void 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
228void 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
242void 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