1 | /* Copyright 2019 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 | #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)) |
38 | static inline uint32_t TF_swap32(uint32_t host_int) { |
39 | return __builtin_bswap32(host_int); |
40 | } |
41 | |
42 | #elif defined(_MSC_VER) |
43 | static inline uint32_t TF_swap32(uint32_t host_int) { |
44 | return _byteswap_ulong(host_int); |
45 | } |
46 | |
47 | #elif defined(__APPLE__) |
48 | static inline uint32_t TF_swap32(uint32_t host_int) { |
49 | return OSSwapInt32(host_int); |
50 | } |
51 | |
52 | #else |
53 | static 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 | |
71 | static inline size_t TF_align16(size_t i) { return (i + 0xF) & ~0xF; } |
72 | |
73 | static inline size_t TF_max(size_t a, size_t b) { return a > b ? a : b; } |
74 | static inline size_t TF_min(size_t a, size_t b) { return a < b ? a : b; } |
75 | |
76 | typedef 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 | |
84 | typedef struct TF_TString_Large { // NOLINT |
85 | size_t size; |
86 | size_t cap; |
87 | char *ptr; |
88 | } TF_TString_Large; |
89 | |
90 | typedef struct TF_TString_Offset { // NOLINT |
91 | uint32_t size; |
92 | uint32_t offset; |
93 | uint32_t count; |
94 | } TF_TString_Offset; |
95 | |
96 | typedef struct TF_TString_View { // NOLINT |
97 | size_t size; |
98 | const char *ptr; |
99 | } TF_TString_View; |
100 | |
101 | typedef struct TF_TString_Raw { // NOLINT |
102 | uint8_t raw[24]; |
103 | } TF_TString_Raw; |
104 | |
105 | typedef 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 | |
112 | enum { |
113 | TF_TString_SmallCapacity = |
114 | (sizeof(TF_TString_Union) - sizeof(/* null delim */ char) - |
115 | sizeof(/* uint8_t size */ uint8_t)), |
116 | }; |
117 | |
118 | typedef struct TF_TString_Small { // NOLINT |
119 | uint8_t size; |
120 | char str[TF_TString_SmallCapacity + sizeof(/* null delim */ char)]; |
121 | } TF_TString_Small; |
122 | |
123 | typedef 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 | |
139 | static 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). |
147 | static 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 | |
158 | static 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 | |
171 | static inline void TF_TString_Init(TF_TString *str) { |
172 | memset(str->u.raw.raw, 0, sizeof(TF_TString_Raw)); |
173 | } |
174 | |
175 | static 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 | |
183 | static 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 | |
198 | static 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 | |
211 | static 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 | |
227 | static 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 | |
286 | static 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 | |
304 | static 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 | |
345 | static 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 | |
353 | static 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 | |
365 | static 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 | |
373 | static 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 | |
386 | static 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 | |
393 | static 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 | |
400 | static 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 | |
429 | static 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 | |