1 /* 2 * Copyright © 2007,2008,2009 Red Hat, Inc. 3 * Copyright © 2011,2012 Google, Inc. 4 * 5 * This is part of HarfBuzz, a text shaping library. 6 * 7 * Permission is hereby granted, without written agreement and without 8 * license or royalty fees, to use, copy, modify, and distribute this 9 * software and its documentation for any purpose, provided that the 10 * above copyright notice and the following two paragraphs appear in 11 * all copies of this software. 12 * 13 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 14 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 15 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 16 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 17 * DAMAGE. 18 * 19 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 20 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 21 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 22 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 23 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 24 * 25 * Red Hat Author(s): Behdad Esfahbod 26 * Google Author(s): Behdad Esfahbod 27 */ 28 29 #ifndef HB_PRIVATE_HH 30 #define HB_PRIVATE_HH 31 32 #define _GNU_SOURCE 1 33 34 #ifdef HAVE_CONFIG_H 35 #include "config.h" 36 #endif 37 38 #include "hb.h" 39 #define HB_H_IN 40 #ifdef HAVE_OT 41 #include "hb-ot.h" 42 #define HB_OT_H_IN 43 #endif 44 45 #include <math.h> 46 #include <stdlib.h> 47 #include <stddef.h> 48 #include <string.h> 49 #include <assert.h> 50 #include <errno.h> 51 #include <stdio.h> 52 #include <stdarg.h> 53 54 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || defined(__MINGW32__) 55 #include <intrin.h> 56 #endif 57 58 #define HB_PASTE1(a,b) a##b 59 #define HB_PASTE(a,b) HB_PASTE1(a,b) 60 61 /* Compile-time custom allocator support. */ 62 63 #if defined(hb_malloc_impl) \ 64 && defined(hb_calloc_impl) \ 65 && defined(hb_realloc_impl) \ 66 && defined(hb_free_impl) 67 extern "C" void* hb_malloc_impl(size_t size); 68 extern "C" void* hb_calloc_impl(size_t nmemb, size_t size); 69 extern "C" void* hb_realloc_impl(void *ptr, size_t size); 70 extern "C" void hb_free_impl(void *ptr); 71 #define malloc hb_malloc_impl 72 #define calloc hb_calloc_impl 73 #define realloc hb_realloc_impl 74 #define free hb_free_impl 75 #endif 76 77 78 /* Compiler attributes */ 79 80 81 #if __cplusplus < 201103L 82 83 #ifndef nullptr 84 #define nullptr NULL 85 #endif 86 87 // Static assertions 88 #ifndef static_assert 89 #define static_assert(e, msg) \ 90 HB_UNUSED typedef int HB_PASTE(static_assertion_failed_at_line_, __LINE__) [(e) ? 1 : -1] 91 #endif // static_assert 92 93 #ifdef __GNUC__ 94 #if (__GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 8)) 95 #define thread_local __thread 96 #endif 97 #else 98 #define thread_local 99 #endif 100 101 #endif // __cplusplus < 201103L 102 103 #if (defined(__GNUC__) || defined(__clang__)) && defined(__OPTIMIZE__) 104 #define likely(expr) (__builtin_expect (!!(expr), 1)) 105 #define unlikely(expr) (__builtin_expect (!!(expr), 0)) 106 #else 107 #define likely(expr) (expr) 108 #define unlikely(expr) (expr) 109 #endif 110 111 #if !defined(__GNUC__) && !defined(__clang__) 112 #undef __attribute__ 113 #define __attribute__(x) 114 #endif 115 116 #if __GNUC__ >= 3 117 #define HB_PURE_FUNC __attribute__((pure)) 118 #define HB_CONST_FUNC __attribute__((const)) 119 #define HB_PRINTF_FUNC(format_idx, arg_idx) __attribute__((__format__ (__printf__, format_idx, arg_idx))) 120 #else 121 #define HB_PURE_FUNC 122 #define HB_CONST_FUNC 123 #define HB_PRINTF_FUNC(format_idx, arg_idx) 124 #endif 125 #if __GNUC__ >= 4 126 #define HB_UNUSED __attribute__((unused)) 127 #elif defined(_MSC_VER) /* https://github.com/harfbuzz/harfbuzz/issues/635 */ 128 #define HB_UNUSED __pragma(warning(suppress: 4100 4101)) 129 #else 130 #define HB_UNUSED 131 #endif 132 133 #ifndef HB_INTERNAL 134 # if !defined(HB_NO_VISIBILITY) && !defined(__MINGW32__) && !defined(__CYGWIN__) && !defined(_MSC_VER) && !defined(__SUNPRO_CC) 135 # define HB_INTERNAL __attribute__((__visibility__("hidden"))) 136 # else 137 # define HB_INTERNAL 138 # define HB_NO_VISIBILITY 1 139 # endif 140 #endif 141 142 #if __GNUC__ >= 3 143 #define HB_FUNC __PRETTY_FUNCTION__ 144 #elif defined(_MSC_VER) 145 #define HB_FUNC __FUNCSIG__ 146 #else 147 #define HB_FUNC __func__ 148 #endif 149 150 #if defined(__SUNPRO_CC) && (__SUNPRO_CC < 0x5140) 151 /* https://github.com/harfbuzz/harfbuzz/issues/630 */ 152 #define __restrict 153 #endif 154 155 /* 156 * Borrowed from https://bugzilla.mozilla.org/show_bug.cgi?id=1215411 157 * HB_FALLTHROUGH is an annotation to suppress compiler warnings about switch 158 * cases that fall through without a break or return statement. HB_FALLTHROUGH 159 * is only needed on cases that have code: 160 * 161 * switch (foo) { 162 * case 1: // These cases have no code. No fallthrough annotations are needed. 163 * case 2: 164 * case 3: 165 * foo = 4; // This case has code, so a fallthrough annotation is needed: 166 * HB_FALLTHROUGH; 167 * default: 168 * return foo; 169 * } 170 */ 171 #if defined(__clang__) && __cplusplus >= 201103L 172 /* clang's fallthrough annotations are only available starting in C++11. */ 173 # define HB_FALLTHROUGH [[clang::fallthrough]] 174 #elif __GNUC__ >= 7 175 /* GNU fallthrough attribute is available from GCC7 */ 176 # define HB_FALLTHROUGH __attribute__((fallthrough)) 177 #elif defined(_MSC_VER) 178 /* 179 * MSVC's __fallthrough annotations are checked by /analyze (Code Analysis): 180 * https://msdn.microsoft.com/en-us/library/ms235402%28VS.80%29.aspx 181 */ 182 # include <sal.h> 183 # define HB_FALLTHROUGH __fallthrough 184 #else 185 # define HB_FALLTHROUGH /* FALLTHROUGH */ 186 #endif 187 188 #if defined(_WIN32) || defined(__CYGWIN__) 189 /* We need Windows Vista for both Uniscribe backend and for 190 * MemoryBarrier. We don't support compiling on Windows XP, 191 * though we run on it fine. */ 192 # if defined(_WIN32_WINNT) && _WIN32_WINNT < 0x0600 193 # undef _WIN32_WINNT 194 # endif 195 # ifndef _WIN32_WINNT 196 # define _WIN32_WINNT 0x0600 197 # endif 198 # ifndef WIN32_LEAN_AND_MEAN 199 # define WIN32_LEAN_AND_MEAN 1 200 # endif 201 # ifndef STRICT 202 # define STRICT 1 203 # endif 204 205 # if defined(_WIN32_WCE) 206 /* Some things not defined on Windows CE. */ 207 # define vsnprintf _vsnprintf 208 # define getenv(Name) nullptr 209 # if _WIN32_WCE < 0x800 210 # define setlocale(Category, Locale) "C" 211 static int errno = 0; /* Use something better? */ 212 # endif 213 # elif defined(WINAPI_FAMILY) && (WINAPI_FAMILY==WINAPI_FAMILY_PC_APP || WINAPI_FAMILY==WINAPI_FAMILY_PHONE_APP) 214 # define getenv(Name) nullptr 215 # endif 216 # if defined(_MSC_VER) && _MSC_VER < 1900 217 # define snprintf _snprintf 218 # endif 219 #endif 220 221 #if HAVE_ATEXIT 222 /* atexit() is only safe to be called from shared libraries on certain 223 * platforms. Whitelist. 224 * https://bugs.freedesktop.org/show_bug.cgi?id=82246 */ 225 # if defined(__linux) && defined(__GLIBC_PREREQ) 226 # if __GLIBC_PREREQ(2,3) 227 /* From atexit() manpage, it's safe with glibc 2.2.3 on Linux. */ 228 # define HB_USE_ATEXIT 1 229 # endif 230 # elif defined(_MSC_VER) || defined(__MINGW32__) 231 /* For MSVC: 232 * https://msdn.microsoft.com/en-us/library/tze57ck3.aspx 233 * https://msdn.microsoft.com/en-us/library/zk17ww08.aspx 234 * mingw32 headers say atexit is safe to use in shared libraries. 235 */ 236 # define HB_USE_ATEXIT 1 237 # elif defined(__ANDROID__) 238 /* This is available since Android NKD r8 or r8b: 239 * https://issuetracker.google.com/code/p/android/issues/detail?id=6455 240 */ 241 # define HB_USE_ATEXIT 1 242 # elif defined(__APPLE__) 243 /* For macOS and related platforms, the atexit man page indicates 244 * that it will be invoked when the library is unloaded, not only 245 * at application exit. 246 */ 247 # define HB_USE_ATEXIT 1 248 # endif 249 #endif 250 #ifdef HB_NO_ATEXIT 251 # undef HB_USE_ATEXIT 252 #endif 253 254 /* Basics */ 255 256 #undef MIN 257 template <typename Type> 258 static inline Type MIN (const Type &a, const Type &b) { return a < b ? a : b; } 259 260 #undef MAX 261 template <typename Type> 262 static inline Type MAX (const Type &a, const Type &b) { return a > b ? a : b; } 263 264 static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b) 265 { return (a + (b - 1)) / b; } 266 267 268 #undef ARRAY_LENGTH 269 template <typename Type, unsigned int n> 270 static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; } 271 /* A const version, but does not detect erratically being called on pointers. */ 272 #define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0]))) 273 274 #define HB_STMT_START do 275 #define HB_STMT_END while (0) 276 277 template <unsigned int cond> class hb_assert_constant_t; 278 template <> class hb_assert_constant_t<1> {}; 279 280 #define ASSERT_STATIC_EXPR_ZERO(_cond) (0 * (unsigned int) sizeof (hb_assert_constant_t<_cond>)) 281 282 /* Lets assert int types. Saves trouble down the road. */ 283 284 static_assert ((sizeof (int8_t) == 1), ""); 285 static_assert ((sizeof (uint8_t) == 1), ""); 286 static_assert ((sizeof (int16_t) == 2), ""); 287 static_assert ((sizeof (uint16_t) == 2), ""); 288 static_assert ((sizeof (int32_t) == 4), ""); 289 static_assert ((sizeof (uint32_t) == 4), ""); 290 static_assert ((sizeof (int64_t) == 8), ""); 291 static_assert ((sizeof (uint64_t) == 8), ""); 292 293 static_assert ((sizeof (hb_codepoint_t) == 4), ""); 294 static_assert ((sizeof (hb_position_t) == 4), ""); 295 static_assert ((sizeof (hb_mask_t) == 4), ""); 296 static_assert ((sizeof (hb_var_int_t) == 4), ""); 297 298 299 /* We like our types POD */ 300 301 #define _ASSERT_TYPE_POD1(_line, _type) union _type_##_type##_on_line_##_line##_is_not_POD { _type instance; } 302 #define _ASSERT_TYPE_POD0(_line, _type) _ASSERT_TYPE_POD1 (_line, _type) 303 #define ASSERT_TYPE_POD(_type) _ASSERT_TYPE_POD0 (__LINE__, _type) 304 305 #ifdef __GNUC__ 306 # define _ASSERT_INSTANCE_POD1(_line, _instance) \ 307 HB_STMT_START { \ 308 typedef __typeof__(_instance) _type_##_line; \ 309 _ASSERT_TYPE_POD1 (_line, _type_##_line); \ 310 } HB_STMT_END 311 #else 312 # define _ASSERT_INSTANCE_POD1(_line, _instance) typedef int _assertion_on_line_##_line##_not_tested 313 #endif 314 # define _ASSERT_INSTANCE_POD0(_line, _instance) _ASSERT_INSTANCE_POD1 (_line, _instance) 315 # define ASSERT_INSTANCE_POD(_instance) _ASSERT_INSTANCE_POD0 (__LINE__, _instance) 316 317 /* Check _assertion in a method environment */ 318 #define _ASSERT_POD1(_line) \ 319 HB_UNUSED inline void _static_assertion_on_line_##_line (void) const \ 320 { _ASSERT_INSTANCE_POD1 (_line, *this); /* Make sure it's POD. */ } 321 # define _ASSERT_POD0(_line) _ASSERT_POD1 (_line) 322 # define ASSERT_POD() _ASSERT_POD0 (__LINE__) 323 324 325 326 /* Tiny functions */ 327 328 /* 329 * Void! 330 */ 331 typedef const struct _hb_void_t *hb_void_t; 332 #define HB_VOID ((const _hb_void_t *) nullptr) 333 334 /* Return the number of 1 bits in v. */ 335 template <typename T> 336 static inline HB_CONST_FUNC unsigned int 337 _hb_popcount (T v) 338 { 339 #if (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) && defined(__OPTIMIZE__) 340 if (sizeof (T) <= sizeof (unsigned int)) 341 return __builtin_popcount (v); 342 343 if (sizeof (T) <= sizeof (unsigned long)) 344 return __builtin_popcountl (v); 345 346 if (sizeof (T) <= sizeof (unsigned long long)) 347 return __builtin_popcountll (v); 348 #endif 349 350 if (sizeof (T) <= 4) 351 { 352 /* "HACKMEM 169" */ 353 uint32_t y; 354 y = (v >> 1) &033333333333; 355 y = v - y - ((y >>1) & 033333333333); 356 return (((y + (y >> 3)) & 030707070707) % 077); 357 } 358 359 if (sizeof (T) == 8) 360 { 361 unsigned int shift = 32; 362 return _hb_popcount<uint32_t> ((uint32_t) v) + _hb_popcount ((uint32_t) (v >> shift)); 363 } 364 365 if (sizeof (T) == 16) 366 { 367 unsigned int shift = 64; 368 return _hb_popcount<uint64_t> ((uint64_t) v) + _hb_popcount ((uint64_t) (v >> shift)); 369 } 370 371 assert (0); 372 return 0; /* Shut up stupid compiler. */ 373 } 374 375 /* Returns the number of bits needed to store number */ 376 template <typename T> 377 static inline HB_CONST_FUNC unsigned int 378 _hb_bit_storage (T v) 379 { 380 if (unlikely (!v)) return 0; 381 382 #if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__) 383 if (sizeof (T) <= sizeof (unsigned int)) 384 return sizeof (unsigned int) * 8 - __builtin_clz (v); 385 386 if (sizeof (T) <= sizeof (unsigned long)) 387 return sizeof (unsigned long) * 8 - __builtin_clzl (v); 388 389 if (sizeof (T) <= sizeof (unsigned long long)) 390 return sizeof (unsigned long long) * 8 - __builtin_clzll (v); 391 #endif 392 393 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || defined(__MINGW32__) 394 if (sizeof (T) <= sizeof (unsigned int)) 395 { 396 unsigned long where; 397 _BitScanReverse (&where, v); 398 return 1 + where; 399 } 400 # if _WIN64 401 if (sizeof (T) <= 8) 402 { 403 unsigned long where; 404 _BitScanReverse64 (&where, v); 405 return 1 + where; 406 } 407 # endif 408 #endif 409 410 if (sizeof (T) <= 4) 411 { 412 /* "bithacks" */ 413 const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000}; 414 const unsigned int S[] = {1, 2, 4, 8, 16}; 415 unsigned int r = 0; 416 for (int i = 4; i >= 0; i--) 417 if (v & b[i]) 418 { 419 v >>= S[i]; 420 r |= S[i]; 421 } 422 return r + 1; 423 } 424 if (sizeof (T) <= 8) 425 { 426 /* "bithacks" */ 427 const uint64_t b[] = {0x2ULL, 0xCULL, 0xF0ULL, 0xFF00ULL, 0xFFFF0000ULL, 0xFFFFFFFF00000000ULL}; 428 const unsigned int S[] = {1, 2, 4, 8, 16, 32}; 429 unsigned int r = 0; 430 for (int i = 5; i >= 0; i--) 431 if (v & b[i]) 432 { 433 v >>= S[i]; 434 r |= S[i]; 435 } 436 return r + 1; 437 } 438 if (sizeof (T) == 16) 439 { 440 unsigned int shift = 64; 441 return (v >> shift) ? _hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift : 442 _hb_bit_storage<uint64_t> ((uint64_t) v); 443 } 444 445 assert (0); 446 return 0; /* Shut up stupid compiler. */ 447 } 448 449 /* Returns the number of zero bits in the least significant side of v */ 450 template <typename T> 451 static inline HB_CONST_FUNC unsigned int 452 _hb_ctz (T v) 453 { 454 if (unlikely (!v)) return 0; 455 456 #if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__) 457 if (sizeof (T) <= sizeof (unsigned int)) 458 return __builtin_ctz (v); 459 460 if (sizeof (T) <= sizeof (unsigned long)) 461 return __builtin_ctzl (v); 462 463 if (sizeof (T) <= sizeof (unsigned long long)) 464 return __builtin_ctzll (v); 465 #endif 466 467 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || defined(__MINGW32__) 468 if (sizeof (T) <= sizeof (unsigned int)) 469 { 470 unsigned long where; 471 _BitScanForward (&where, v); 472 return where; 473 } 474 # if _WIN64 475 if (sizeof (T) <= 8) 476 { 477 unsigned long where; 478 _BitScanForward64 (&where, v); 479 return where; 480 } 481 # endif 482 #endif 483 484 if (sizeof (T) <= 4) 485 { 486 /* "bithacks" */ 487 unsigned int c = 32; 488 v &= - (int32_t) v; 489 if (v) c--; 490 if (v & 0x0000FFFF) c -= 16; 491 if (v & 0x00FF00FF) c -= 8; 492 if (v & 0x0F0F0F0F) c -= 4; 493 if (v & 0x33333333) c -= 2; 494 if (v & 0x55555555) c -= 1; 495 return c; 496 } 497 if (sizeof (T) <= 8) 498 { 499 /* "bithacks" */ 500 unsigned int c = 64; 501 v &= - (int64_t) (v); 502 if (v) c--; 503 if (v & 0x00000000FFFFFFFFULL) c -= 32; 504 if (v & 0x0000FFFF0000FFFFULL) c -= 16; 505 if (v & 0x00FF00FF00FF00FFULL) c -= 8; 506 if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4; 507 if (v & 0x3333333333333333ULL) c -= 2; 508 if (v & 0x5555555555555555ULL) c -= 1; 509 return c; 510 } 511 if (sizeof (T) == 16) 512 { 513 unsigned int shift = 64; 514 return (uint64_t) v ? _hb_bit_storage<uint64_t> ((uint64_t) v) : 515 _hb_bit_storage<uint64_t> ((uint64_t) v >> shift) + shift; 516 } 517 518 assert (0); 519 return 0; /* Shut up stupid compiler. */ 520 } 521 522 static inline bool 523 _hb_unsigned_int_mul_overflows (unsigned int count, unsigned int size) 524 { 525 return (size > 0) && (count >= ((unsigned int) -1) / size); 526 } 527 528 static inline unsigned int 529 _hb_ceil_to_4 (unsigned int v) 530 { 531 return ((v - 1) | 3) + 1; 532 } 533 534 535 536 /* 537 * 538 * Utility types 539 * 540 */ 541 542 #define HB_DISALLOW_COPY_AND_ASSIGN(TypeName) \ 543 TypeName(const TypeName&); \ 544 void operator=(const TypeName&) 545 546 /* 547 * Static pools 548 */ 549 550 /* Global nul-content Null pool. Enlarge as necessary. */ 551 552 #define HB_NULL_POOL_SIZE 264 553 static_assert (HB_NULL_POOL_SIZE % sizeof (void *) == 0, "Align HB_NULL_POOL_SIZE."); 554 555 #ifdef HB_NO_VISIBILITY 556 static 557 #else 558 extern HB_INTERNAL 559 #endif 560 void * const _hb_NullPool[HB_NULL_POOL_SIZE / sizeof (void *)] 561 #ifdef HB_NO_VISIBILITY 562 = {} 563 #endif 564 ; 565 /* Generic nul-content Null objects. */ 566 template <typename Type> 567 static inline Type const & Null (void) { 568 static_assert (sizeof (Type) <= HB_NULL_POOL_SIZE, "Increase HB_NULL_POOL_SIZE."); 569 return *reinterpret_cast<Type const *> (_hb_NullPool); 570 } 571 #define Null(Type) Null<Type>() 572 573 /* Specializaiton for arbitrary-content arbitrary-sized Null objects. */ 574 #define DEFINE_NULL_DATA(Namespace, Type, data) \ 575 } /* Close namespace. */ \ 576 static const char _Null##Type[sizeof (Namespace::Type) + 1] = data; /* +1 is for nul-termination in data */ \ 577 template <> \ 578 /*static*/ inline const Namespace::Type& Null<Namespace::Type> (void) { \ 579 return *reinterpret_cast<const Namespace::Type *> (_Null##Type); \ 580 } \ 581 namespace Namespace { \ 582 /* The following line really exists such that we end in a place needing semicolon */ \ 583 static_assert (Namespace::Type::min_size + 1 <= sizeof (_Null##Type), "Null pool too small. Enlarge.") 584 585 586 /* Global writable pool. Enlarge as necessary. */ 587 588 /* To be fully correct, CrapPool must be thread_local. However, we do not rely on CrapPool 589 * for correct operation. It only exist to catch and divert program logic bugs instead of 590 * causing bad memory access. So, races there are not actually introducing incorrectness 591 * in the code. Has ~12kb binary size overhead to have it, also clang build fails with it. */ 592 #ifdef HB_NO_VISIBILITY 593 static 594 #else 595 extern HB_INTERNAL 596 #endif 597 /*thread_local*/ void * _hb_CrapPool[HB_NULL_POOL_SIZE / sizeof (void *)] 598 #ifdef HB_NO_VISIBILITY 599 = {} 600 #endif 601 ; 602 /* CRAP pool: Common Region for Access Protection. */ 603 template <typename Type> 604 static inline Type& Crap (void) { 605 static_assert (sizeof (Type) <= HB_NULL_POOL_SIZE, "Increase HB_NULL_POOL_SIZE."); 606 Type *obj = reinterpret_cast<Type *> (_hb_CrapPool); 607 *obj = Null(Type); 608 return *obj; 609 } 610 #define Crap(Type) Crap<Type>() 611 612 template <typename Type> 613 struct CrapOrNull { 614 static inline Type & get (void) { return Crap(Type); } 615 }; 616 template <typename Type> 617 struct CrapOrNull<const Type> { 618 static inline Type const & get (void) { return Null(Type); } 619 }; 620 #define CrapOrNull(Type) CrapOrNull<Type>::get () 621 622 623 624 /* arrays and maps */ 625 626 627 #define HB_PREALLOCED_ARRAY_INIT {0, 0, nullptr} 628 template <typename Type, unsigned int StaticSize=8> 629 struct hb_vector_t 630 { 631 unsigned int len; 632 unsigned int allocated; 633 bool successful; 634 Type *arrayZ; 635 Type static_array[StaticSize]; 636 637 void init (void) 638 { 639 len = 0; 640 allocated = ARRAY_LENGTH (static_array); 641 successful = true; 642 arrayZ = static_array; 643 } 644 645 inline Type& operator [] (unsigned int i) 646 { 647 if (unlikely (i >= len)) 648 return Crap (Type); 649 return arrayZ[i]; 650 } 651 inline const Type& operator [] (unsigned int i) const 652 { 653 if (unlikely (i >= len)) 654 return Null(Type); 655 return arrayZ[i]; 656 } 657 658 inline Type *push (void) 659 { 660 if (unlikely (!resize (len + 1))) 661 return &Crap(Type); 662 return &arrayZ[len - 1]; 663 } 664 inline Type *push (const Type& v) 665 { 666 Type *p = push (); 667 *p = v; 668 return p; 669 } 670 671 /* Allocate for size but don't adjust len. */ 672 inline bool alloc (unsigned int size) 673 { 674 if (unlikely (!successful)) 675 return false; 676 677 if (likely (size <= allocated)) 678 return true; 679 680 /* Reallocate */ 681 682 unsigned int new_allocated = allocated; 683 while (size >= new_allocated) 684 new_allocated += (new_allocated >> 1) + 8; 685 686 Type *new_array = nullptr; 687 688 if (arrayZ == static_array) 689 { 690 new_array = (Type *) calloc (new_allocated, sizeof (Type)); 691 if (new_array) 692 memcpy (new_array, arrayZ, len * sizeof (Type)); 693 } 694 else 695 { 696 bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type)); 697 if (likely (!overflows)) 698 new_array = (Type *) realloc (arrayZ, new_allocated * sizeof (Type)); 699 } 700 701 if (unlikely (!new_array)) 702 { 703 successful = false; 704 return false; 705 } 706 707 arrayZ = new_array; 708 allocated = new_allocated; 709 710 return true; 711 } 712 713 inline bool resize (int size_) 714 { 715 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 716 if (!alloc (size)) 717 return false; 718 719 if (size > len) 720 memset (arrayZ + len, 0, (size - len) * sizeof (*arrayZ)); 721 722 len = size; 723 return true; 724 } 725 726 inline void pop (void) 727 { 728 if (!len) return; 729 len--; 730 } 731 732 inline void remove (unsigned int i) 733 { 734 if (unlikely (i >= len)) 735 return; 736 memmove (static_cast<void *> (&arrayZ[i]), 737 static_cast<void *> (&arrayZ[i + 1]), 738 (len - i - 1) * sizeof (Type)); 739 len--; 740 } 741 742 inline void shrink (int size_) 743 { 744 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 745 if (size < len) 746 len = size; 747 } 748 749 template <typename T> 750 inline Type *find (T v) { 751 for (unsigned int i = 0; i < len; i++) 752 if (arrayZ[i] == v) 753 return &arrayZ[i]; 754 return nullptr; 755 } 756 template <typename T> 757 inline const Type *find (T v) const { 758 for (unsigned int i = 0; i < len; i++) 759 if (arrayZ[i] == v) 760 return &arrayZ[i]; 761 return nullptr; 762 } 763 764 inline void qsort (int (*cmp)(const void*, const void*)) 765 { 766 ::qsort (arrayZ, len, sizeof (Type), cmp); 767 } 768 769 inline void qsort (void) 770 { 771 ::qsort (arrayZ, len, sizeof (Type), Type::cmp); 772 } 773 774 inline void qsort (unsigned int start, unsigned int end) 775 { 776 ::qsort (arrayZ + start, end - start, sizeof (Type), Type::cmp); 777 } 778 779 template <typename T> 780 inline Type *lsearch (const T &x) 781 { 782 for (unsigned int i = 0; i < len; i++) 783 if (0 == this->arrayZ[i].cmp (&x)) 784 return &arrayZ[i]; 785 return nullptr; 786 } 787 788 template <typename T> 789 inline Type *bsearch (const T &x) 790 { 791 unsigned int i; 792 return bfind (x, &i) ? &arrayZ[i] : nullptr; 793 } 794 template <typename T> 795 inline const Type *bsearch (const T &x) const 796 { 797 unsigned int i; 798 return bfind (x, &i) ? &arrayZ[i] : nullptr; 799 } 800 template <typename T> 801 inline bool bfind (const T &x, unsigned int *i) const 802 { 803 int min = 0, max = (int) this->len - 1; 804 while (min <= max) 805 { 806 int mid = (min + max) / 2; 807 int c = this->arrayZ[mid].cmp (&x); 808 if (c < 0) 809 max = mid - 1; 810 else if (c > 0) 811 min = mid + 1; 812 else 813 { 814 *i = mid; 815 return true; 816 } 817 } 818 if (max < 0 || (max < (int) this->len && this->arrayZ[max].cmp (&x) > 0)) 819 max++; 820 *i = max; 821 return false; 822 } 823 824 inline void fini (void) 825 { 826 if (arrayZ != static_array) 827 free (arrayZ); 828 arrayZ = nullptr; 829 allocated = len = 0; 830 } 831 }; 832 833 template <typename Type> 834 struct hb_auto_t : Type 835 { 836 hb_auto_t (void) { Type::init (); } 837 ~hb_auto_t (void) { Type::fini (); } 838 private: /* Hide */ 839 void init (void) {} 840 void fini (void) {} 841 }; 842 template <typename Type> 843 struct hb_auto_array_t : hb_auto_t <hb_vector_t <Type> > {}; 844 845 846 #define HB_LOCKABLE_SET_INIT {HB_PREALLOCED_ARRAY_INIT} 847 template <typename item_t, typename lock_t> 848 struct hb_lockable_set_t 849 { 850 hb_vector_t <item_t, 1> items; 851 852 inline void init (void) { items.init (); } 853 854 template <typename T> 855 inline item_t *replace_or_insert (T v, lock_t &l, bool replace) 856 { 857 l.lock (); 858 item_t *item = items.find (v); 859 if (item) { 860 if (replace) { 861 item_t old = *item; 862 *item = v; 863 l.unlock (); 864 old.fini (); 865 } 866 else { 867 item = nullptr; 868 l.unlock (); 869 } 870 } else { 871 item = items.push (v); 872 l.unlock (); 873 } 874 return item; 875 } 876 877 template <typename T> 878 inline void remove (T v, lock_t &l) 879 { 880 l.lock (); 881 item_t *item = items.find (v); 882 if (item) { 883 item_t old = *item; 884 *item = items[items.len - 1]; 885 items.pop (); 886 l.unlock (); 887 old.fini (); 888 } else { 889 l.unlock (); 890 } 891 } 892 893 template <typename T> 894 inline bool find (T v, item_t *i, lock_t &l) 895 { 896 l.lock (); 897 item_t *item = items.find (v); 898 if (item) 899 *i = *item; 900 l.unlock (); 901 return !!item; 902 } 903 904 template <typename T> 905 inline item_t *find_or_insert (T v, lock_t &l) 906 { 907 l.lock (); 908 item_t *item = items.find (v); 909 if (!item) { 910 item = items.push (v); 911 } 912 l.unlock (); 913 return item; 914 } 915 916 inline void fini (lock_t &l) 917 { 918 if (!items.len) { 919 /* No need for locking. */ 920 items.fini (); 921 return; 922 } 923 l.lock (); 924 while (items.len) { 925 item_t old = items[items.len - 1]; 926 items.pop (); 927 l.unlock (); 928 old.fini (); 929 l.lock (); 930 } 931 items.fini (); 932 l.unlock (); 933 } 934 935 }; 936 937 938 /* ASCII tag/character handling */ 939 940 static inline bool ISALPHA (unsigned char c) 941 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); } 942 static inline bool ISALNUM (unsigned char c) 943 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); } 944 static inline bool ISSPACE (unsigned char c) 945 { return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; } 946 static inline unsigned char TOUPPER (unsigned char c) 947 { return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; } 948 static inline unsigned char TOLOWER (unsigned char c) 949 { return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; } 950 951 952 /* HB_NDEBUG disables some sanity checks that are very safe to disable and 953 * should be disabled in production systems. If NDEBUG is defined, enable 954 * HB_NDEBUG; but if it's desirable that normal assert()s (which are very 955 * light-weight) to be enabled, then HB_DEBUG can be defined to disable 956 * the costlier checks. */ 957 #ifdef NDEBUG 958 #define HB_NDEBUG 1 959 #endif 960 961 962 /* Misc */ 963 964 template <typename T> class hb_assert_unsigned_t; 965 template <> class hb_assert_unsigned_t<unsigned char> {}; 966 template <> class hb_assert_unsigned_t<unsigned short> {}; 967 template <> class hb_assert_unsigned_t<unsigned int> {}; 968 template <> class hb_assert_unsigned_t<unsigned long> {}; 969 970 template <typename T> static inline bool 971 hb_in_range (T u, T lo, T hi) 972 { 973 /* The sizeof() is here to force template instantiation. 974 * I'm sure there are better ways to do this but can't think of 975 * one right now. Declaring a variable won't work as HB_UNUSED 976 * is unusable on some platforms and unused types are less likely 977 * to generate a warning than unused variables. */ 978 static_assert ((sizeof (hb_assert_unsigned_t<T>) >= 0), ""); 979 980 /* The casts below are important as if T is smaller than int, 981 * the subtract results will become a signed int! */ 982 return (T)(u - lo) <= (T)(hi - lo); 983 } 984 985 template <typename T> static inline bool 986 hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2) 987 { 988 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2); 989 } 990 991 template <typename T> static inline bool 992 hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3) 993 { 994 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2) || hb_in_range (u, lo3, hi3); 995 } 996 997 998 /* Enable bitwise ops on enums marked as flags_t */ 999 /* To my surprise, looks like the function resolver is happy to silently cast 1000 * one enum to another... So this doesn't provide the type-checking that I 1001 * originally had in mind... :(. 1002 * 1003 * For MSVC warnings, see: https://github.com/harfbuzz/harfbuzz/pull/163 1004 */ 1005 #ifdef _MSC_VER 1006 # pragma warning(disable:4200) 1007 # pragma warning(disable:4800) 1008 #endif 1009 #define HB_MARK_AS_FLAG_T(T) \ 1010 extern "C++" { \ 1011 static inline T operator | (T l, T r) { return T ((unsigned) l | (unsigned) r); } \ 1012 static inline T operator & (T l, T r) { return T ((unsigned) l & (unsigned) r); } \ 1013 static inline T operator ^ (T l, T r) { return T ((unsigned) l ^ (unsigned) r); } \ 1014 static inline T operator ~ (T r) { return T (~(unsigned int) r); } \ 1015 static inline T& operator |= (T &l, T r) { l = l | r; return l; } \ 1016 static inline T& operator &= (T& l, T r) { l = l & r; return l; } \ 1017 static inline T& operator ^= (T& l, T r) { l = l ^ r; return l; } \ 1018 } 1019 1020 1021 /* Useful for set-operations on small enums. 1022 * For example, for testing "x ∈ {x1, x2, x3}" use: 1023 * (FLAG_UNSAFE(x) & (FLAG(x1) | FLAG(x2) | FLAG(x3))) 1024 */ 1025 #define FLAG(x) (ASSERT_STATIC_EXPR_ZERO ((unsigned int)(x) < 32) + (1U << (unsigned int)(x))) 1026 #define FLAG_UNSAFE(x) ((unsigned int)(x) < 32 ? (1U << (unsigned int)(x)) : 0) 1027 #define FLAG_RANGE(x,y) (ASSERT_STATIC_EXPR_ZERO ((x) < (y)) + FLAG(y+1) - FLAG(x)) 1028 1029 1030 template <typename T, typename T2> static inline void 1031 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *), T2 *array2) 1032 { 1033 for (unsigned int i = 1; i < len; i++) 1034 { 1035 unsigned int j = i; 1036 while (j && compar (&array[j - 1], &array[i]) > 0) 1037 j--; 1038 if (i == j) 1039 continue; 1040 /* Move item i to occupy place for item j, shift what's in between. */ 1041 { 1042 T t = array[i]; 1043 memmove (&array[j + 1], &array[j], (i - j) * sizeof (T)); 1044 array[j] = t; 1045 } 1046 if (array2) 1047 { 1048 T2 t = array2[i]; 1049 memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T2)); 1050 array2[j] = t; 1051 } 1052 } 1053 } 1054 1055 template <typename T> static inline void 1056 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *)) 1057 { 1058 hb_stable_sort (array, len, compar, (int *) nullptr); 1059 } 1060 1061 static inline hb_bool_t 1062 hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out) 1063 { 1064 /* Pain because we don't know whether s is nul-terminated. */ 1065 char buf[64]; 1066 len = MIN (ARRAY_LENGTH (buf) - 1, len); 1067 strncpy (buf, s, len); 1068 buf[len] = '\0'; 1069 1070 char *end; 1071 errno = 0; 1072 unsigned long v = strtoul (buf, &end, base); 1073 if (errno) return false; 1074 if (*end) return false; 1075 *out = v; 1076 return true; 1077 } 1078 1079 1080 /* Vectorization */ 1081 1082 struct HbOpOr 1083 { 1084 static const bool passthru_left = true; 1085 static const bool passthru_right = true; 1086 template <typename T> static void process (T &o, const T &a, const T &b) { o = a | b; } 1087 }; 1088 struct HbOpAnd 1089 { 1090 static const bool passthru_left = false; 1091 static const bool passthru_right = false; 1092 template <typename T> static void process (T &o, const T &a, const T &b) { o = a & b; } 1093 }; 1094 struct HbOpMinus 1095 { 1096 static const bool passthru_left = true; 1097 static const bool passthru_right = false; 1098 template <typename T> static void process (T &o, const T &a, const T &b) { o = a & ~b; } 1099 }; 1100 struct HbOpXor 1101 { 1102 static const bool passthru_left = true; 1103 static const bool passthru_right = true; 1104 template <typename T> static void process (T &o, const T &a, const T &b) { o = a ^ b; } 1105 }; 1106 1107 1108 /* Compiler-assisted vectorization. */ 1109 1110 /* The `vector_size' attribute was introduced in gcc 3.1. */ 1111 #if defined( __GNUC__ ) && ( __GNUC__ >= 4 ) 1112 #define HB_VECTOR_SIZE 128 1113 #elif !defined(HB_VECTOR_SIZE) 1114 #define HB_VECTOR_SIZE 0 1115 #endif 1116 1117 /* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))). */ 1118 template <typename elt_t, unsigned int byte_size> 1119 struct hb_vector_size_t 1120 { 1121 elt_t& operator [] (unsigned int i) { return u.v[i]; } 1122 const elt_t& operator [] (unsigned int i) const { return u.v[i]; } 1123 1124 template <class Op> 1125 inline hb_vector_size_t process (const hb_vector_size_t &o) const 1126 { 1127 hb_vector_size_t r; 1128 #if HB_VECTOR_SIZE 1129 if (HB_VECTOR_SIZE && 0 == (byte_size * 8) % HB_VECTOR_SIZE) 1130 for (unsigned int i = 0; i < ARRAY_LENGTH (u.vec); i++) 1131 Op::process (r.u.vec[i], u.vec[i], o.u.vec[i]); 1132 else 1133 #endif 1134 for (unsigned int i = 0; i < ARRAY_LENGTH (u.v); i++) 1135 Op::process (r.u.v[i], u.v[i], o.u.v[i]); 1136 return r; 1137 } 1138 inline hb_vector_size_t operator | (const hb_vector_size_t &o) const 1139 { return process<HbOpOr> (o); } 1140 inline hb_vector_size_t operator & (const hb_vector_size_t &o) const 1141 { return process<HbOpAnd> (o); } 1142 inline hb_vector_size_t operator ^ (const hb_vector_size_t &o) const 1143 { return process<HbOpXor> (o); } 1144 inline hb_vector_size_t operator ~ () const 1145 { 1146 hb_vector_size_t r; 1147 #if HB_VECTOR_SIZE && 0 1148 if (HB_VECTOR_SIZE && 0 == (byte_size * 8) % HB_VECTOR_SIZE) 1149 for (unsigned int i = 0; i < ARRAY_LENGTH (u.vec); i++) 1150 r.u.vec[i] = ~u.vec[i]; 1151 else 1152 #endif 1153 for (unsigned int i = 0; i < ARRAY_LENGTH (u.v); i++) 1154 r.u.v[i] = ~u.v[i]; 1155 return r; 1156 } 1157 1158 private: 1159 static_assert (byte_size / sizeof (elt_t) * sizeof (elt_t) == byte_size, ""); 1160 union { 1161 elt_t v[byte_size / sizeof (elt_t)]; 1162 #if HB_VECTOR_SIZE 1163 typedef unsigned long vec_t __attribute__((vector_size (HB_VECTOR_SIZE / 8))); 1164 vec_t vec[byte_size / sizeof (vec_t)]; 1165 #endif 1166 } u; 1167 }; 1168 1169 1170 /* Global runtime options. */ 1171 1172 struct hb_options_t 1173 { 1174 unsigned int initialized : 1; 1175 unsigned int uniscribe_bug_compatible : 1; 1176 }; 1177 1178 union hb_options_union_t { 1179 unsigned int i; 1180 hb_options_t opts; 1181 }; 1182 static_assert ((sizeof (int) == sizeof (hb_options_union_t)), ""); 1183 1184 HB_INTERNAL void 1185 _hb_options_init (void); 1186 1187 extern HB_INTERNAL hb_options_union_t _hb_options; 1188 1189 static inline hb_options_t 1190 hb_options (void) 1191 { 1192 if (unlikely (!_hb_options.i)) 1193 _hb_options_init (); 1194 1195 return _hb_options.opts; 1196 } 1197 1198 /* Size signifying variable-sized array */ 1199 #define VAR 1 1200 1201 1202 /* String type. */ 1203 1204 struct hb_bytes_t 1205 { 1206 inline hb_bytes_t (void) : bytes (nullptr), len (0) {} 1207 inline hb_bytes_t (const char *bytes_, unsigned int len_) : bytes (bytes_), len (len_) {} 1208 1209 inline int cmp (const hb_bytes_t &a) const 1210 { 1211 if (len != a.len) 1212 return (int) a.len - (int) len; 1213 1214 return memcmp (a.bytes, bytes, len); 1215 } 1216 static inline int cmp (const void *pa, const void *pb) 1217 { 1218 hb_bytes_t *a = (hb_bytes_t *) pa; 1219 hb_bytes_t *b = (hb_bytes_t *) pb; 1220 return b->cmp (*a); 1221 } 1222 1223 const char *bytes; 1224 unsigned int len; 1225 }; 1226 1227 1228 /* fallback for round() */ 1229 #if !defined (HAVE_ROUND) && !defined (HAVE_DECL_ROUND) 1230 static inline double 1231 _hb_round (double x) 1232 { 1233 if (x >= 0) 1234 return floor (x + 0.5); 1235 else 1236 return ceil (x - 0.5); 1237 } 1238 #define round(x) _hb_round(x) 1239 #endif 1240 1241 1242 #endif /* HB_PRIVATE_HH */