1/* Copyright 2019 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#ifndef TENSORFLOW_TSL_PLATFORM_CTSTRING_INTERNAL_H_
17#define TENSORFLOW_TSL_PLATFORM_CTSTRING_INTERNAL_H_
18
19#include <limits.h>
20#include <stdint.h>
21#include <stdlib.h>
22#include <string.h>
23
24#if (defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && \
25 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) || \
26 defined(_WIN32)
27#define TF_TSTRING_LITTLE_ENDIAN 1
28#elif defined(__BYTE_ORDER__) && defined(__ORDER_BIG_ENDIAN__) && \
29 __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
30#define TF_TSTRING_LITTLE_ENDIAN 0
31#else
32#error "Unable to detect endianness."
33#endif
34
35#if defined(__clang__) || \
36 (defined(__GNUC__) && \
37 ((__GNUC__ == 4 && __GNUC_MINOR__ >= 8) || __GNUC__ >= 5))
38static inline uint32_t TF_swap32(uint32_t host_int) {
39 return __builtin_bswap32(host_int);
40}
41
42#elif defined(_MSC_VER)
43static inline uint32_t TF_swap32(uint32_t host_int) {
44 return _byteswap_ulong(host_int);
45}
46
47#elif defined(__APPLE__)
48static inline uint32_t TF_swap32(uint32_t host_int) {
49 return OSSwapInt32(host_int);
50}
51
52#else
53static inline uint32_t TF_swap32(uint32_t host_int) {
54#if defined(__GLIBC__)
55 return bswap_32(host_int);
56#else // defined(__GLIBC__)
57 return (((host_int & uint32_t{0xFF}) << 24) |
58 ((host_int & uint32_t{0xFF00}) << 8) |
59 ((host_int & uint32_t{0xFF0000}) >> 8) |
60 ((host_int & uint32_t{0xFF000000}) >> 24));
61#endif // defined(__GLIBC__)
62}
63#endif
64
65#if TF_TSTRING_LITTLE_ENDIAN
66#define TF_le32toh(x) x
67#else // TF_TSTRING_LITTLE_ENDIAN
68#define TF_le32toh(x) TF_swap32(x)
69#endif // TF_TSTRING_LITTLE_ENDIAN
70
71static inline size_t TF_align16(size_t i) { return (i + 0xF) & ~0xF; }
72
73static inline size_t TF_max(size_t a, size_t b) { return a > b ? a : b; }
74static inline size_t TF_min(size_t a, size_t b) { return a < b ? a : b; }
75
76typedef enum TF_TString_Type { // NOLINT
77 TF_TSTR_SMALL = 0x00,
78 TF_TSTR_LARGE = 0x01,
79 TF_TSTR_OFFSET = 0x02,
80 TF_TSTR_VIEW = 0x03,
81 TF_TSTR_TYPE_MASK = 0x03
82} TF_TString_Type;
83
84typedef struct TF_TString_Large { // NOLINT
85 size_t size;
86 size_t cap;
87 char *ptr;
88} TF_TString_Large;
89
90typedef struct TF_TString_Offset { // NOLINT
91 uint32_t size;
92 uint32_t offset;
93 uint32_t count;
94} TF_TString_Offset;
95
96typedef struct TF_TString_View { // NOLINT
97 size_t size;
98 const char *ptr;
99} TF_TString_View;
100
101typedef struct TF_TString_Raw { // NOLINT
102 uint8_t raw[24];
103} TF_TString_Raw;
104
105typedef union TF_TString_Union { // NOLINT
106 TF_TString_Large large;
107 TF_TString_Offset offset;
108 TF_TString_View view;
109 TF_TString_Raw raw;
110} TF_TString_Union;
111
112enum {
113 TF_TString_SmallCapacity =
114 (sizeof(TF_TString_Union) - sizeof(/* null delim */ char) -
115 sizeof(/* uint8_t size */ uint8_t)),
116};
117
118typedef struct TF_TString_Small { // NOLINT
119 uint8_t size;
120 char str[TF_TString_SmallCapacity + sizeof(/* null delim */ char)];
121} TF_TString_Small;
122
123typedef struct TF_TString { // NOLINT
124 union {
125 // small conflicts with '#define small char' in RpcNdr.h for MSVC, so we use
126 // smll instead.
127 TF_TString_Small smll;
128 TF_TString_Large large;
129 TF_TString_Offset offset;
130 TF_TString_View view;
131 TF_TString_Raw raw;
132 } u;
133} TF_TString;
134
135// TODO(dero): Fix for OSS, and add C only build test.
136// _Static_assert(CHAR_BIT == 8);
137// _Static_assert(sizeof(TF_TString) == 24);
138
139static inline TF_TString_Type TF_TString_GetType(const TF_TString *str) {
140 return (TF_TString_Type)(str->u.raw.raw[0] & TF_TSTR_TYPE_MASK); // NOLINT
141}
142
143// XXX(dero): For the big-endian case, this function could potentially be more
144// performant and readable by always storing the string size as little-endian
145// and always byte-swapping on big endian, resulting in a simple 'bswap'+'shr'
146// (for architectures that have a bswap op).
147static inline size_t TF_TString_ToActualSizeT(size_t size) {
148#if TF_TSTRING_LITTLE_ENDIAN
149 return size >> 2;
150#else // TF_TSTRING_LITTLE_ENDIAN
151 // 0xFF000000 or 0xFF00000000000000 depending on platform
152 static const size_t mask = ~((~(size_t)0) >> 8);
153
154 return (((mask << 2) & size) >> 2) | (~mask & size);
155#endif // TF_TSTRING_LITTLE_ENDIAN
156}
157
158static inline size_t TF_TString_ToInternalSizeT(size_t size,
159 TF_TString_Type type) {
160#if TF_TSTRING_LITTLE_ENDIAN
161 return (size << 2) | type;
162#else // TF_TSTRING_LITTLE_ENDIAN
163 // 0xFF000000 or 0xFF00000000000000 depending on platform
164 static const size_t mask = ~((~(size_t)0) >> 8);
165
166 return (mask & (size << 2)) | (~mask & size) |
167 ((size_t)type << ((sizeof(size_t) - 1) * 8)); // NOLINT
168#endif // TF_TSTRING_LITTLE_ENDIAN
169}
170
171static inline void TF_TString_Init(TF_TString *str) {
172 memset(str->u.raw.raw, 0, sizeof(TF_TString_Raw));
173}
174
175static inline void TF_TString_Dealloc(TF_TString *str) {
176 if (TF_TString_GetType(str) == TF_TSTR_LARGE &&
177 str->u.large.ptr != NULL) { // NOLINT
178 free(str->u.large.ptr);
179 TF_TString_Init(str);
180 }
181}
182
183static inline size_t TF_TString_GetSize(const TF_TString *str) {
184 switch (TF_TString_GetType(str)) {
185 case TF_TSTR_SMALL:
186 return str->u.smll.size >> 2;
187 case TF_TSTR_LARGE:
188 return TF_TString_ToActualSizeT(str->u.large.size);
189 case TF_TSTR_OFFSET:
190 return TF_le32toh(str->u.offset.size) >> 2;
191 case TF_TSTR_VIEW:
192 return TF_TString_ToActualSizeT(str->u.view.size);
193 default:
194 return 0; // Unreachable.
195 }
196}
197
198static inline size_t TF_TString_GetCapacity(const TF_TString *str) {
199 switch (TF_TString_GetType(str)) {
200 case TF_TSTR_SMALL:
201 return TF_TString_SmallCapacity;
202 case TF_TSTR_LARGE:
203 return str->u.large.cap;
204 case TF_TSTR_OFFSET:
205 case TF_TSTR_VIEW:
206 default:
207 return 0;
208 }
209}
210
211static inline const char *TF_TString_GetDataPointer(const TF_TString *str) {
212 switch (TF_TString_GetType(str)) {
213 case TF_TSTR_SMALL:
214 return str->u.smll.str;
215 case TF_TSTR_LARGE:
216 return str->u.large.ptr;
217 case TF_TSTR_OFFSET:
218 return (const char *)str + TF_le32toh(str->u.offset.offset); // NOLINT
219 case TF_TSTR_VIEW:
220 return str->u.view.ptr;
221 default:
222 // Unreachable.
223 return NULL; // NOLINT
224 }
225}
226
227static inline char *TF_TString_ResizeUninitialized(TF_TString *str,
228 size_t new_size) {
229 size_t curr_size = TF_TString_GetSize(str);
230 size_t copy_size = TF_min(new_size, curr_size);
231
232 TF_TString_Type curr_type = TF_TString_GetType(str);
233 const char *curr_ptr = TF_TString_GetDataPointer(str);
234
235 // Case: SMALL/LARGE/VIEW/OFFSET -> SMALL
236 if (new_size <= TF_TString_SmallCapacity) {
237 str->u.smll.size = (uint8_t)((new_size << 2) | TF_TSTR_SMALL); // NOLINT
238 str->u.smll.str[new_size] = '\0';
239
240 if (curr_type != TF_TSTR_SMALL && copy_size) {
241 memcpy(str->u.smll.str, curr_ptr, copy_size);
242 }
243
244 if (curr_type == TF_TSTR_LARGE) {
245 free((void *)curr_ptr); // NOLINT
246 }
247
248 // We do not clear out the newly excluded region.
249
250 return str->u.smll.str;
251 }
252
253 // Case: SMALL/LARGE/VIEW/OFFSET -> LARGE
254 size_t new_cap;
255 size_t curr_cap = TF_TString_GetCapacity(str);
256
257 if (new_size < curr_size && new_size < curr_cap / 2) {
258 // TODO(dero): Replace with shrink_to_fit flag.
259 new_cap = TF_align16(curr_cap / 2 + 1) - 1;
260 } else if (new_size > curr_cap) {
261 new_cap = TF_align16(new_size + 1) - 1;
262 } else {
263 new_cap = curr_cap;
264 }
265
266 char *new_ptr;
267 if (new_cap == curr_cap) {
268 new_ptr = str->u.large.ptr;
269 } else if (curr_type == TF_TSTR_LARGE) {
270 new_ptr = (char *)realloc(str->u.large.ptr, new_cap + 1); // NOLINT
271 } else {
272 new_ptr = (char *)malloc(new_cap + 1); // NOLINT
273 if (copy_size) {
274 memcpy(new_ptr, curr_ptr, copy_size);
275 }
276 }
277
278 str->u.large.size = TF_TString_ToInternalSizeT(new_size, TF_TSTR_LARGE);
279 str->u.large.ptr = new_ptr;
280 str->u.large.ptr[new_size] = '\0';
281 str->u.large.cap = new_cap;
282
283 return str->u.large.ptr;
284}
285
286static inline char *TF_TString_GetMutableDataPointer(TF_TString *str) {
287 switch (TF_TString_GetType(str)) {
288 case TF_TSTR_SMALL:
289 return str->u.smll.str;
290 case TF_TSTR_OFFSET:
291 case TF_TSTR_VIEW:
292 // Convert OFFSET/VIEW to SMALL/LARGE
293 TF_TString_ResizeUninitialized(str, TF_TString_GetSize(str));
294 return (TF_TString_GetType(str) == TF_TSTR_SMALL) ? str->u.smll.str
295 : str->u.large.ptr;
296 case TF_TSTR_LARGE:
297 return str->u.large.ptr;
298 default:
299 // Unreachable.
300 return NULL; // NOLINT
301 }
302}
303
304static inline void TF_TString_Reserve(TF_TString *str, size_t new_cap) {
305 TF_TString_Type curr_type = TF_TString_GetType(str);
306
307 if (new_cap <= TF_TString_SmallCapacity) {
308 // We do nothing, we let Resize/GetMutableDataPointer handle the
309 // conversion to SMALL from VIEW/OFFSET when the need arises.
310 // In the degenerate case, where new_cap <= TF_TString_SmallCapacity,
311 // curr_size > TF_TString_SmallCapacity, and the type is VIEW/OFFSET, we
312 // defer the malloc to Resize/GetMutableDataPointer.
313 return;
314 }
315
316 if (curr_type == TF_TSTR_LARGE && new_cap <= str->u.large.cap) {
317 // We handle reduced cap in resize.
318 return;
319 }
320
321 // Case: VIEW/OFFSET -> LARGE or grow an existing LARGE type
322 size_t curr_size = TF_TString_GetSize(str);
323 const char *curr_ptr = TF_TString_GetDataPointer(str);
324
325 // Since VIEW and OFFSET types are read-only, their capacity is effectively 0.
326 // So we make sure we have enough room in the VIEW and OFFSET cases.
327 new_cap = TF_align16(TF_max(new_cap, curr_size) + 1) - 1;
328
329 if (curr_type == TF_TSTR_LARGE) {
330 str->u.large.ptr =
331 (char *)realloc(str->u.large.ptr, new_cap + 1); // NOLINT
332 } else {
333 // Convert to Large
334 char *new_ptr = (char *)malloc(new_cap + 1); // NOLINT
335 memcpy(new_ptr, curr_ptr, curr_size);
336
337 str->u.large.size = TF_TString_ToInternalSizeT(curr_size, TF_TSTR_LARGE);
338 str->u.large.ptr = new_ptr;
339 str->u.large.ptr[curr_size] = '\0';
340 }
341
342 str->u.large.cap = new_cap;
343}
344
345static inline void TF_TString_ReserveAmortized(TF_TString *str,
346 size_t new_cap) {
347 const size_t curr_cap = TF_TString_GetCapacity(str);
348 if (new_cap > curr_cap) {
349 TF_TString_Reserve(str, new_cap > 2 * curr_cap ? new_cap : 2 * curr_cap);
350 }
351}
352
353static inline char *TF_TString_Resize(TF_TString *str, size_t new_size,
354 char c) {
355 size_t curr_size = TF_TString_GetSize(str);
356 char *cstr = TF_TString_ResizeUninitialized(str, new_size);
357
358 if (new_size > curr_size) {
359 memset(cstr + curr_size, c, new_size - curr_size);
360 }
361
362 return cstr;
363}
364
365static inline void TF_TString_AssignView(TF_TString *dst, const char *src,
366 size_t size) {
367 TF_TString_Dealloc(dst);
368
369 dst->u.view.size = TF_TString_ToInternalSizeT(size, TF_TSTR_VIEW);
370 dst->u.view.ptr = src;
371}
372
373static inline void TF_TString_AppendN(TF_TString *dst, const char *src,
374 size_t src_size) {
375 if (!src_size) return;
376
377 size_t dst_size = TF_TString_GetSize(dst);
378
379 // For append use cases, we want to ensure amortized growth.
380 TF_TString_ReserveAmortized(dst, dst_size + src_size);
381 char *dst_c = TF_TString_ResizeUninitialized(dst, dst_size + src_size);
382
383 memcpy(dst_c + dst_size, src, src_size);
384}
385
386static inline void TF_TString_Append(TF_TString *dst, const TF_TString *src) {
387 const char *src_c = TF_TString_GetDataPointer(src);
388 size_t size = TF_TString_GetSize(src);
389
390 TF_TString_AppendN(dst, src_c, size);
391}
392
393static inline void TF_TString_Copy(TF_TString *dst, const char *src,
394 size_t size) {
395 char *dst_c = TF_TString_ResizeUninitialized(dst, size);
396
397 if (size) memcpy(dst_c, src, size);
398}
399
400static inline void TF_TString_Assign(TF_TString *dst, const TF_TString *src) {
401 if (dst == src) return;
402
403 TF_TString_Dealloc(dst);
404
405 switch (TF_TString_GetType(src)) {
406 case TF_TSTR_SMALL:
407 case TF_TSTR_VIEW:
408 *dst = *src;
409 return;
410 case TF_TSTR_LARGE: {
411 const char *src_c = TF_TString_GetDataPointer(src);
412 size_t size = TF_TString_GetSize(src);
413
414 TF_TString_Copy(dst, src_c, size);
415 }
416 return;
417 case TF_TSTR_OFFSET: {
418 const char *src_c = TF_TString_GetDataPointer(src);
419 size_t size = TF_TString_GetSize(src);
420
421 TF_TString_AssignView(dst, src_c, size);
422 }
423 return;
424 default:
425 return; // Unreachable.
426 }
427}
428
429static inline void TF_TString_Move(TF_TString *dst, TF_TString *src) {
430 if (dst == src) return;
431
432 TF_TString_Dealloc(dst);
433
434 switch (TF_TString_GetType(src)) {
435 case TF_TSTR_SMALL:
436 case TF_TSTR_VIEW:
437 *dst = *src;
438 return;
439 case TF_TSTR_LARGE:
440 *dst = *src;
441 TF_TString_Init(src);
442 return;
443 case TF_TSTR_OFFSET: {
444 const char *src_c = TF_TString_GetDataPointer(src);
445 size_t size = TF_TString_GetSize(src);
446
447 TF_TString_AssignView(dst, src_c, size);
448 }
449 return;
450 default:
451 return; // Unreachable.
452 }
453}
454
455#endif // TENSORFLOW_TSL_PLATFORM_CTSTRING_INTERNAL_H_
456