1 /* 2 * Copyright 2017 Google, Inc. 3 * 4 * This is part of HarfBuzz, a text shaping library. 5 * 6 * Permission is hereby granted, without written agreement and without 7 * license or royalty fees, to use, copy, modify, and distribute this 8 * software and its documentation for any purpose, provided that the 9 * above copyright notice and the following two paragraphs appear in 10 * all copies of this software. 11 * 12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 16 * DAMAGE. 17 * 18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 23 * 24 * Google Author(s): Behdad Esfahbod 25 */ 26 27 #ifndef HB_DSALGS_HH 28 #define HB_DSALGS_HH 29 30 #include "hb.hh" 31 32 #include "hb-null.hh" 33 34 35 /* Void! For when we need a expression-type of void. */ 36 typedef const struct _hb_void_t *hb_void_t; 37 #define HB_VOID ((const _hb_void_t *) nullptr) 38 39 40 /* 41 * Bithacks. 42 */ 43 44 /* Return the number of 1 bits in v. */ 45 template <typename T> 46 static inline HB_CONST_FUNC unsigned int 47 hb_popcount (T v) 48 { 49 #if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__) 50 if (sizeof (T) <= sizeof (unsigned int)) 51 return __builtin_popcount (v); 52 53 if (sizeof (T) <= sizeof (unsigned long)) 54 return __builtin_popcountl (v); 55 56 if (sizeof (T) <= sizeof (unsigned long long)) 57 return __builtin_popcountll (v); 58 #endif 59 60 if (sizeof (T) <= 4) 61 { 62 /* "HACKMEM 169" */ 63 uint32_t y; 64 y = (v >> 1) &033333333333; 65 y = v - y - ((y >>1) & 033333333333); 66 return (((y + (y >> 3)) & 030707070707) % 077); 67 } 68 69 if (sizeof (T) == 8) 70 { 71 unsigned int shift = 32; 72 return hb_popcount<uint32_t> ((uint32_t) v) + hb_popcount ((uint32_t) (v >> shift)); 73 } 74 75 if (sizeof (T) == 16) 76 { 77 unsigned int shift = 64; 78 return hb_popcount<uint64_t> ((uint64_t) v) + hb_popcount ((uint64_t) (v >> shift)); 79 } 80 81 assert (0); 82 return 0; /* Shut up stupid compiler. */ 83 } 84 85 /* Returns the number of bits needed to store number */ 86 template <typename T> 87 static inline HB_CONST_FUNC unsigned int 88 hb_bit_storage (T v) 89 { 90 if (unlikely (!v)) return 0; 91 92 #if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__) 93 if (sizeof (T) <= sizeof (unsigned int)) 94 return sizeof (unsigned int) * 8 - __builtin_clz (v); 95 96 if (sizeof (T) <= sizeof (unsigned long)) 97 return sizeof (unsigned long) * 8 - __builtin_clzl (v); 98 99 if (sizeof (T) <= sizeof (unsigned long long)) 100 return sizeof (unsigned long long) * 8 - __builtin_clzll (v); 101 #endif 102 103 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || defined(__MINGW32__) 104 if (sizeof (T) <= sizeof (unsigned int)) 105 { 106 unsigned long where; 107 _BitScanReverse (&where, v); 108 return 1 + where; 109 } 110 # if _WIN64 111 if (sizeof (T) <= 8) 112 { 113 unsigned long where; 114 _BitScanReverse64 (&where, v); 115 return 1 + where; 116 } 117 # endif 118 #endif 119 120 if (sizeof (T) <= 4) 121 { 122 /* "bithacks" */ 123 const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000}; 124 const unsigned int S[] = {1, 2, 4, 8, 16}; 125 unsigned int r = 0; 126 for (int i = 4; i >= 0; i--) 127 if (v & b[i]) 128 { 129 v >>= S[i]; 130 r |= S[i]; 131 } 132 return r + 1; 133 } 134 if (sizeof (T) <= 8) 135 { 136 /* "bithacks" */ 137 const uint64_t b[] = {0x2ULL, 0xCULL, 0xF0ULL, 0xFF00ULL, 0xFFFF0000ULL, 0xFFFFFFFF00000000ULL}; 138 const unsigned int S[] = {1, 2, 4, 8, 16, 32}; 139 unsigned int r = 0; 140 for (int i = 5; i >= 0; i--) 141 if (v & b[i]) 142 { 143 v >>= S[i]; 144 r |= S[i]; 145 } 146 return r + 1; 147 } 148 if (sizeof (T) == 16) 149 { 150 unsigned int shift = 64; 151 return (v >> shift) ? hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift : 152 hb_bit_storage<uint64_t> ((uint64_t) v); 153 } 154 155 assert (0); 156 return 0; /* Shut up stupid compiler. */ 157 } 158 159 /* Returns the number of zero bits in the least significant side of v */ 160 template <typename T> 161 static inline HB_CONST_FUNC unsigned int 162 hb_ctz (T v) 163 { 164 if (unlikely (!v)) return 0; 165 166 #if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__) 167 if (sizeof (T) <= sizeof (unsigned int)) 168 return __builtin_ctz (v); 169 170 if (sizeof (T) <= sizeof (unsigned long)) 171 return __builtin_ctzl (v); 172 173 if (sizeof (T) <= sizeof (unsigned long long)) 174 return __builtin_ctzll (v); 175 #endif 176 177 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || defined(__MINGW32__) 178 if (sizeof (T) <= sizeof (unsigned int)) 179 { 180 unsigned long where; 181 _BitScanForward (&where, v); 182 return where; 183 } 184 # if _WIN64 185 if (sizeof (T) <= 8) 186 { 187 unsigned long where; 188 _BitScanForward64 (&where, v); 189 return where; 190 } 191 # endif 192 #endif 193 194 if (sizeof (T) <= 4) 195 { 196 /* "bithacks" */ 197 unsigned int c = 32; 198 v &= - (int32_t) v; 199 if (v) c--; 200 if (v & 0x0000FFFF) c -= 16; 201 if (v & 0x00FF00FF) c -= 8; 202 if (v & 0x0F0F0F0F) c -= 4; 203 if (v & 0x33333333) c -= 2; 204 if (v & 0x55555555) c -= 1; 205 return c; 206 } 207 if (sizeof (T) <= 8) 208 { 209 /* "bithacks" */ 210 unsigned int c = 64; 211 v &= - (int64_t) (v); 212 if (v) c--; 213 if (v & 0x00000000FFFFFFFFULL) c -= 32; 214 if (v & 0x0000FFFF0000FFFFULL) c -= 16; 215 if (v & 0x00FF00FF00FF00FFULL) c -= 8; 216 if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4; 217 if (v & 0x3333333333333333ULL) c -= 2; 218 if (v & 0x5555555555555555ULL) c -= 1; 219 return c; 220 } 221 if (sizeof (T) == 16) 222 { 223 unsigned int shift = 64; 224 return (uint64_t) v ? hb_bit_storage<uint64_t> ((uint64_t) v) : 225 hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift; 226 } 227 228 assert (0); 229 return 0; /* Shut up stupid compiler. */ 230 } 231 232 233 /* 234 * Tiny stuff. 235 */ 236 237 template <typename T> 238 static inline T* hb_addressof (T& arg) 239 { 240 /* https://en.cppreference.com/w/cpp/memory/addressof */ 241 return reinterpret_cast<T*>( 242 &const_cast<char&>( 243 reinterpret_cast<const volatile char&>(arg))); 244 } 245 246 /* ASCII tag/character handling */ 247 static inline bool ISALPHA (unsigned char c) 248 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); } 249 static inline bool ISALNUM (unsigned char c) 250 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); } 251 static inline bool ISSPACE (unsigned char c) 252 { return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; } 253 static inline unsigned char TOUPPER (unsigned char c) 254 { return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; } 255 static inline unsigned char TOLOWER (unsigned char c) 256 { return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; } 257 258 #undef MIN 259 template <typename Type> 260 static inline Type MIN (const Type &a, const Type &b) { return a < b ? a : b; } 261 262 #undef MAX 263 template <typename Type> 264 static inline Type MAX (const Type &a, const Type &b) { return a > b ? a : b; } 265 266 static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b) 267 { return (a + (b - 1)) / b; } 268 269 270 #undef ARRAY_LENGTH 271 template <typename Type, unsigned int n> 272 static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; } 273 /* A const version, but does not detect erratically being called on pointers. */ 274 #define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0]))) 275 276 277 static inline int 278 hb_memcmp (const void *a, const void *b, unsigned int len) 279 { 280 /* It's illegal to pass NULL to memcmp(), even if len is zero. 281 * So, wrap it. 282 * https://sourceware.org/bugzilla/show_bug.cgi?id=23878 */ 283 if (!len) return 0; 284 return memcmp (a, b, len); 285 } 286 287 static inline bool 288 hb_unsigned_mul_overflows (unsigned int count, unsigned int size) 289 { 290 return (size > 0) && (count >= ((unsigned int) -1) / size); 291 } 292 293 static inline unsigned int 294 hb_ceil_to_4 (unsigned int v) 295 { 296 return ((v - 1) | 3) + 1; 297 } 298 299 template <typename T> struct hb_is_signed; 300 template <> struct hb_is_signed<signed char> { enum { value = true }; }; 301 template <> struct hb_is_signed<signed short> { enum { value = true }; }; 302 template <> struct hb_is_signed<signed int> { enum { value = true }; }; 303 template <> struct hb_is_signed<signed long> { enum { value = true }; }; 304 template <> struct hb_is_signed<unsigned char> { enum { value = false }; }; 305 template <> struct hb_is_signed<unsigned short> { enum { value = false }; }; 306 template <> struct hb_is_signed<unsigned int> { enum { value = false }; }; 307 template <> struct hb_is_signed<unsigned long> { enum { value = false }; }; 308 /* We need to define hb_is_signed for the typedefs we use on pre-Visual 309 * Studio 2010 for the int8_t type, since __int8/__int64 is not considered 310 * the same as char/long. The previous lines will suffice for the other 311 * types, though. Note that somehow, unsigned __int8 is considered same 312 * as unsigned char. 313 * https://github.com/harfbuzz/harfbuzz/pull/1499 314 */ 315 #if defined(_MSC_VER) && (_MSC_VER < 1600) 316 template <> struct hb_is_signed<__int8> { enum { value = true }; }; 317 #endif 318 319 template <typename T> static inline bool 320 hb_in_range (T u, T lo, T hi) 321 { 322 /* The sizeof() is here to force template instantiation. 323 * I'm sure there are better ways to do this but can't think of 324 * one right now. Declaring a variable won't work as HB_UNUSED 325 * is unusable on some platforms and unused types are less likely 326 * to generate a warning than unused variables. */ 327 static_assert (!hb_is_signed<T>::value, ""); 328 329 /* The casts below are important as if T is smaller than int, 330 * the subtract results will become a signed int! */ 331 return (T)(u - lo) <= (T)(hi - lo); 332 } 333 template <typename T> static inline bool 334 hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2) 335 { 336 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2); 337 } 338 template <typename T> static inline bool 339 hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3) 340 { 341 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2) || hb_in_range (u, lo3, hi3); 342 } 343 344 345 /* 346 * Sort and search. 347 */ 348 349 static inline void * 350 hb_bsearch (const void *key, const void *base, 351 size_t nmemb, size_t size, 352 int (*compar)(const void *_key, const void *_item)) 353 { 354 int min = 0, max = (int) nmemb - 1; 355 while (min <= max) 356 { 357 int mid = (min + max) / 2; 358 const void *p = (const void *) (((const char *) base) + (mid * size)); 359 int c = compar (key, p); 360 if (c < 0) 361 max = mid - 1; 362 else if (c > 0) 363 min = mid + 1; 364 else 365 return (void *) p; 366 } 367 return nullptr; 368 } 369 370 static inline void * 371 hb_bsearch_r (const void *key, const void *base, 372 size_t nmemb, size_t size, 373 int (*compar)(const void *_key, const void *_item, void *_arg), 374 void *arg) 375 { 376 int min = 0, max = (int) nmemb - 1; 377 while (min <= max) 378 { 379 int mid = ((unsigned int) min + (unsigned int) max) / 2; 380 const void *p = (const void *) (((const char *) base) + (mid * size)); 381 int c = compar (key, p, arg); 382 if (c < 0) 383 max = mid - 1; 384 else if (c > 0) 385 min = mid + 1; 386 else 387 return (void *) p; 388 } 389 return nullptr; 390 } 391 392 393 /* From https://github.com/noporpoise/sort_r 394 * With following modifications: 395 * 396 * 10 November 2018: 397 * https://github.com/noporpoise/sort_r/issues/7 398 */ 399 400 /* Isaac Turner 29 April 2014 Public Domain */ 401 402 /* 403 404 hb_sort_r function to be exported. 405 406 Parameters: 407 base is the array to be sorted 408 nel is the number of elements in the array 409 width is the size in bytes of each element of the array 410 compar is the comparison function 411 arg is a pointer to be passed to the comparison function 412 413 void hb_sort_r(void *base, size_t nel, size_t width, 414 int (*compar)(const void *_a, const void *_b, void *_arg), 415 void *arg); 416 */ 417 418 419 /* swap a, b iff a>b */ 420 /* __restrict is same as restrict but better support on old machines */ 421 static int sort_r_cmpswap(char *__restrict a, char *__restrict b, size_t w, 422 int (*compar)(const void *_a, const void *_b, 423 void *_arg), 424 void *arg) 425 { 426 char tmp, *end = a+w; 427 if(compar(a, b, arg) > 0) { 428 for(; a < end; a++, b++) { tmp = *a; *a = *b; *b = tmp; } 429 return 1; 430 } 431 return 0; 432 } 433 434 /* Note: quicksort is not stable, equivalent values may be swapped */ 435 static inline void sort_r_simple(void *base, size_t nel, size_t w, 436 int (*compar)(const void *_a, const void *_b, 437 void *_arg), 438 void *arg) 439 { 440 char *b = (char *)base, *end = b + nel*w; 441 if(nel < 7) { 442 /* Insertion sort for arbitrarily small inputs */ 443 char *pi, *pj; 444 for(pi = b+w; pi < end; pi += w) { 445 for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,arg); pj -= w) {} 446 } 447 } 448 else 449 { 450 /* nel > 6; Quicksort */ 451 452 /* Use median of first, middle and last items as pivot */ 453 char *x, *y, *xend, ch; 454 char *pl, *pm, *pr; 455 char *last = b+w*(nel-1), *tmp; 456 char *l[3]; 457 l[0] = b; 458 l[1] = b+w*(nel/2); 459 l[2] = last; 460 461 if(compar(l[0],l[1],arg) > 0) { tmp=l[0]; l[0]=l[1]; l[1]=tmp; } 462 if(compar(l[1],l[2],arg) > 0) { 463 tmp=l[1]; l[1]=l[2]; l[2]=tmp; /* swap(l[1],l[2]) */ 464 if(compar(l[0],l[1],arg) > 0) { tmp=l[0]; l[0]=l[1]; l[1]=tmp; } 465 } 466 467 /* swap l[id], l[2] to put pivot as last element */ 468 for(x = l[1], y = last, xend = x+w; x<xend; x++, y++) { 469 ch = *x; *x = *y; *y = ch; 470 } 471 472 pl = b; 473 pr = last; 474 475 while(pl < pr) { 476 pm = pl+((pr-pl+1)>>1); 477 for(; pl < pm; pl += w) { 478 if(sort_r_cmpswap(pl, pr, w, compar, arg)) { 479 pr -= w; /* pivot now at pl */ 480 break; 481 } 482 } 483 pm = pl+((pr-pl)>>1); 484 for(; pm < pr; pr -= w) { 485 if(sort_r_cmpswap(pl, pr, w, compar, arg)) { 486 pl += w; /* pivot now at pr */ 487 break; 488 } 489 } 490 } 491 492 sort_r_simple(b, (pl-b)/w, w, compar, arg); 493 sort_r_simple(pl+w, (end-(pl+w))/w, w, compar, arg); 494 } 495 } 496 497 static inline void hb_sort_r(void *base, size_t nel, size_t width, 498 int (*compar)(const void *_a, const void *_b, void *_arg), 499 void *arg) 500 { 501 sort_r_simple(base, nel, width, compar, arg); 502 } 503 504 505 template <typename T, typename T2> static inline void 506 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *), T2 *array2) 507 { 508 for (unsigned int i = 1; i < len; i++) 509 { 510 unsigned int j = i; 511 while (j && compar (&array[j - 1], &array[i]) > 0) 512 j--; 513 if (i == j) 514 continue; 515 /* Move item i to occupy place for item j, shift what's in between. */ 516 { 517 T t = array[i]; 518 memmove (&array[j + 1], &array[j], (i - j) * sizeof (T)); 519 array[j] = t; 520 } 521 if (array2) 522 { 523 T2 t = array2[i]; 524 memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T2)); 525 array2[j] = t; 526 } 527 } 528 } 529 530 template <typename T> static inline void 531 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *)) 532 { 533 hb_stable_sort (array, len, compar, (int *) nullptr); 534 } 535 536 static inline hb_bool_t 537 hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out) 538 { 539 /* Pain because we don't know whether s is nul-terminated. */ 540 char buf[64]; 541 len = MIN (ARRAY_LENGTH (buf) - 1, len); 542 strncpy (buf, s, len); 543 buf[len] = '\0'; 544 545 char *end; 546 errno = 0; 547 unsigned long v = strtoul (buf, &end, base); 548 if (errno) return false; 549 if (*end) return false; 550 *out = v; 551 return true; 552 } 553 554 555 struct HbOpOr 556 { 557 enum { passthru_left = true }; 558 enum { passthru_right = true }; 559 template <typename T> static void process (T &o, const T &a, const T &b) { o = a | b; } 560 }; 561 struct HbOpAnd 562 { 563 enum { passthru_left = false }; 564 enum { passthru_right = false }; 565 template <typename T> static void process (T &o, const T &a, const T &b) { o = a & b; } 566 }; 567 struct HbOpMinus 568 { 569 enum { passthru_left = true }; 570 enum { passthru_right = false }; 571 template <typename T> static void process (T &o, const T &a, const T &b) { o = a & ~b; } 572 }; 573 struct HbOpXor 574 { 575 enum { passthru_left = true }; 576 enum { passthru_right = true }; 577 template <typename T> static void process (T &o, const T &a, const T &b) { o = a ^ b; } 578 }; 579 580 581 /* Compiler-assisted vectorization. */ 582 583 /* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))), 584 * using vectorized operations if HB_VECTOR_SIZE is set to **bit** numbers (eg 128). 585 * Define that to 0 to disable. */ 586 template <typename elt_t, unsigned int byte_size> 587 struct hb_vector_size_t 588 { 589 elt_t& operator [] (unsigned int i) { return u.v[i]; } 590 const elt_t& operator [] (unsigned int i) const { return u.v[i]; } 591 592 void clear (unsigned char v = 0) { memset (this, v, sizeof (*this)); } 593 594 template <class Op> 595 hb_vector_size_t process (const hb_vector_size_t &o) const 596 { 597 hb_vector_size_t r; 598 #if HB_VECTOR_SIZE 599 if (HB_VECTOR_SIZE && 0 == (byte_size * 8) % HB_VECTOR_SIZE) 600 for (unsigned int i = 0; i < ARRAY_LENGTH (u.vec); i++) 601 Op::process (r.u.vec[i], u.vec[i], o.u.vec[i]); 602 else 603 #endif 604 for (unsigned int i = 0; i < ARRAY_LENGTH (u.v); i++) 605 Op::process (r.u.v[i], u.v[i], o.u.v[i]); 606 return r; 607 } 608 hb_vector_size_t operator | (const hb_vector_size_t &o) const 609 { return process<HbOpOr> (o); } 610 hb_vector_size_t operator & (const hb_vector_size_t &o) const 611 { return process<HbOpAnd> (o); } 612 hb_vector_size_t operator ^ (const hb_vector_size_t &o) const 613 { return process<HbOpXor> (o); } 614 hb_vector_size_t operator ~ () const 615 { 616 hb_vector_size_t r; 617 #if HB_VECTOR_SIZE && 0 618 if (HB_VECTOR_SIZE && 0 == (byte_size * 8) % HB_VECTOR_SIZE) 619 for (unsigned int i = 0; i < ARRAY_LENGTH (u.vec); i++) 620 r.u.vec[i] = ~u.vec[i]; 621 else 622 #endif 623 for (unsigned int i = 0; i < ARRAY_LENGTH (u.v); i++) 624 r.u.v[i] = ~u.v[i]; 625 return r; 626 } 627 628 private: 629 static_assert (byte_size / sizeof (elt_t) * sizeof (elt_t) == byte_size, ""); 630 union { 631 elt_t v[byte_size / sizeof (elt_t)]; 632 #if HB_VECTOR_SIZE 633 hb_vector_size_impl_t vec[byte_size / sizeof (hb_vector_size_impl_t)]; 634 #endif 635 } u; 636 }; 637 638 639 #endif /* HB_DSALGS_HH */ 640
