src/hb-algs.hh

   1 /*
   2  * Copyright © 2017  Google, Inc.
   3  * Copyright © 2019  Facebook, 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  * Google Author(s): Behdad Esfahbod
  26  * Facebook Author(s): Behdad Esfahbod
  27  */
  28
  29 #ifndef HB_ALGS_HH
  30 #define HB_ALGS_HH
  31
  32 #include "hb.hh"
  33 #include "hb-meta.hh"
  34 #include "hb-null.hh"
  35 #include "hb-number.hh"
  36
  37
  38 /* Encodes three unsigned integers in one 64-bit number.  If the inputs have more than 21 bits,
  39  * values will be truncated / overlap, and might not decode exactly. */
  40 #define HB_CODEPOINT_ENCODE3(x,y,z) (((uint64_t) (x) << 42) | ((uint64_t) (y) << 21) | (uint64_t) (z))
  41 #define HB_CODEPOINT_DECODE3_1(v) ((hb_codepoint_t) ((v) >> 42))
  42 #define HB_CODEPOINT_DECODE3_2(v) ((hb_codepoint_t) ((v) >> 21) & 0x1FFFFFu)
  43 #define HB_CODEPOINT_DECODE3_3(v) ((hb_codepoint_t) (v) & 0x1FFFFFu)
  44
  45 /* Custom encoding used by hb-ucd. */
  46 #define HB_CODEPOINT_ENCODE3_11_7_14(x,y,z) (((uint32_t) ((x) & 0x07FFu) << 21) | (((uint32_t) (y) & 0x007Fu) << 14) | (uint32_t) ((z) & 0x3FFFu))
  47 #define HB_CODEPOINT_DECODE3_11_7_14_1(v) ((hb_codepoint_t) ((v) >> 21))
  48 #define HB_CODEPOINT_DECODE3_11_7_14_2(v) ((hb_codepoint_t) (((v) >> 14) & 0x007Fu) | 0x0300)
  49 #define HB_CODEPOINT_DECODE3_11_7_14_3(v) ((hb_codepoint_t) (v) & 0x3FFFu)
  50
  51 struct
  52 {
  53   /* Note.  This is dangerous in that if it's passed an rvalue, it returns rvalue-reference. */
  54   template <typename T> constexpr auto
  55   operator () (T&& v) const HB_AUTO_RETURN ( hb_forward<T> (v) )
  56 }
  57 HB_FUNCOBJ (hb_identity);
  58 struct
  59 {
  60   /* Like identity(), but only retains lvalue-references.  Rvalues are returned as rvalues. */
  61   template <typename T> constexpr T&
  62   operator () (T& v) const { return v; }
  63
  64   template <typename T> constexpr hb_remove_reference<T>
  65   operator () (T&& v) const { return v; }
  66 }
  67 HB_FUNCOBJ (hb_lidentity);
  68 struct
  69 {
  70   /* Like identity(), but always returns rvalue. */
  71   template <typename T> constexpr hb_remove_reference<T>
  72   operator () (T&& v) const { return v; }
  73 }
  74 HB_FUNCOBJ (hb_ridentity);
  75
  76 struct
  77 {
  78   template <typename T> constexpr bool
  79   operator () (T&& v) const { return bool (hb_forward<T> (v)); }
  80 }
  81 HB_FUNCOBJ (hb_bool);
  82
  83 struct
  84 {
  85   private:
  86
  87   template <typename T> constexpr auto
  88   impl (const T& v, hb_priority<1>) const HB_RETURN (uint32_t, hb_deref (v).hash ())
  89
  90   template <typename T,
  91             hb_enable_if (hb_is_integral (T))> constexpr auto
  92   impl (const T& v, hb_priority<0>) const HB_AUTO_RETURN
  93   (
  94     /* Knuth's multiplicative method: */
  95     (uint32_t) v * 2654435761u
  96   )
  97
  98   public:
  99
 100   template <typename T> constexpr auto
 101   operator () (const T& v) const HB_RETURN (uint32_t, impl (v, hb_prioritize))
 102 }
 103 HB_FUNCOBJ (hb_hash);
 104
 105
 106 struct
 107 {
 108   private:
 109
 110   /* Pointer-to-member-function. */
 111   template <typename Appl, typename T, typename ...Ts> auto
 112   impl (Appl&& a, hb_priority<2>, T &&v, Ts&&... ds) const HB_AUTO_RETURN
 113   ((hb_deref (hb_forward<T> (v)).*hb_forward<Appl> (a)) (hb_forward<Ts> (ds)...))
 114
 115   /* Pointer-to-member. */
 116   template <typename Appl, typename T> auto
 117   impl (Appl&& a, hb_priority<1>, T &&v) const HB_AUTO_RETURN
 118   ((hb_deref (hb_forward<T> (v))).*hb_forward<Appl> (a))
 119
 120   /* Operator(). */
 121   template <typename Appl, typename ...Ts> auto
 122   impl (Appl&& a, hb_priority<0>, Ts&&... ds) const HB_AUTO_RETURN
 123   (hb_deref (hb_forward<Appl> (a)) (hb_forward<Ts> (ds)...))
 124
 125   public:
 126
 127   template <typename Appl, typename ...Ts> auto
 128   operator () (Appl&& a, Ts&&... ds) const HB_AUTO_RETURN
 129   (
 130     impl (hb_forward<Appl> (a),
 131           hb_prioritize,
 132           hb_forward<Ts> (ds)...)
 133   )
 134 }
 135 HB_FUNCOBJ (hb_invoke);
 136
 137 template <unsigned Pos, typename Appl, typename V>
 138 struct hb_partial_t
 139 {
 140   hb_partial_t (Appl a, V v) : a (a), v (v) {}
 141
 142   static_assert (Pos > 0, "");
 143
 144   template <typename ...Ts,
 145             unsigned P = Pos,
 146             hb_enable_if (P == 1)> auto
 147   operator () (Ts&& ...ds) -> decltype (hb_invoke (hb_declval (Appl),
 148                                                    hb_declval (V),
 149                                                    hb_declval (Ts)...))
 150   {
 151     return hb_invoke (hb_forward<Appl> (a),
 152                       hb_forward<V> (v),
 153                       hb_forward<Ts> (ds)...);
 154   }
 155   template <typename T0, typename ...Ts,
 156             unsigned P = Pos,
 157             hb_enable_if (P == 2)> auto
 158   operator () (T0&& d0, Ts&& ...ds) -> decltype (hb_invoke (hb_declval (Appl),
 159                                                             hb_declval (T0),
 160                                                             hb_declval (V),
 161                                                             hb_declval (Ts)...))
 162   {
 163     return hb_invoke (hb_forward<Appl> (a),
 164                       hb_forward<T0> (d0),
 165                       hb_forward<V> (v),
 166                       hb_forward<Ts> (ds)...);
 167   }
 168
 169   private:
 170   hb_reference_wrapper<Appl> a;
 171   V v;
 172 };
 173 template <unsigned Pos=1, typename Appl, typename V>
 174 auto hb_partial (Appl&& a, V&& v) HB_AUTO_RETURN
 175 (( hb_partial_t<Pos, Appl, V> (a, v) ))
 176
 177 /* The following, HB_PARTIALIZE, macro uses a particular corner-case
 178  * of C++11 that is not particularly well-supported by all compilers.
 179  * What's happening is that it's using "this" in a trailing return-type
 180  * via decltype().  Broken compilers deduce the type of "this" pointer
 181  * in that context differently from what it resolves to in the body
 182  * of the function.
 183  *
 184  * One probable cause of this is that at the time of trailing return
 185  * type declaration, "this" points to an incomplete type, whereas in
 186  * the function body the type is complete.  That doesn't justify the
 187  * error in any way, but is probably what's happening.
 188  *
 189  * In the case of MSVC, we get around this by using C++14 "decltype(auto)"
 190  * which deduces the type from the actual return statement.  For gcc 4.8
 191  * we use "+this" instead of "this" which produces an rvalue that seems
 192  * to be deduced as the same type with this particular compiler, and seem
 193  * to be fine as default code path as well.
 194  */
 195 #ifdef _MSC_VER
 196 /* https://github.com/harfbuzz/harfbuzz/issues/1730 */ \
 197 #define HB_PARTIALIZE(Pos) \
 198   template <typename _T> \
 199   decltype(auto) operator () (_T&& _v) const \
 200   { return hb_partial<Pos> (this, hb_forward<_T> (_v)); } \
 201   static_assert (true, "")
 202 #else
 203 /* https://github.com/harfbuzz/harfbuzz/issues/1724 */
 204 #define HB_PARTIALIZE(Pos) \
 205   template <typename _T> \
 206   auto operator () (_T&& _v) const HB_AUTO_RETURN \
 207   (hb_partial<Pos> (+this, hb_forward<_T> (_v))) \
 208   static_assert (true, "")
 209 #endif
 210
 211
 212 struct
 213 {
 214   private:
 215
 216   template <typename Pred, typename Val> auto
 217   impl (Pred&& p, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
 218   (hb_deref (hb_forward<Pred> (p)).has (hb_forward<Val> (v)))
 219
 220   template <typename Pred, typename Val> auto
 221   impl (Pred&& p, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
 222   (
 223     hb_invoke (hb_forward<Pred> (p),
 224                hb_forward<Val> (v))
 225   )
 226
 227   public:
 228
 229   template <typename Pred, typename Val> auto
 230   operator () (Pred&& p, Val &&v) const HB_RETURN (bool,
 231     impl (hb_forward<Pred> (p),
 232           hb_forward<Val> (v),
 233           hb_prioritize)
 234   )
 235 }
 236 HB_FUNCOBJ (hb_has);
 237
 238 struct
 239 {
 240   private:
 241
 242   template <typename Pred, typename Val> auto
 243   impl (Pred&& p, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
 244   (
 245     hb_has (hb_forward<Pred> (p),
 246             hb_forward<Val> (v))
 247   )
 248
 249   template <typename Pred, typename Val> auto
 250   impl (Pred&& p, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
 251   (
 252     hb_forward<Pred> (p) == hb_forward<Val> (v)
 253   )
 254
 255   public:
 256
 257   template <typename Pred, typename Val> auto
 258   operator () (Pred&& p, Val &&v) const HB_RETURN (bool,
 259     impl (hb_forward<Pred> (p),
 260           hb_forward<Val> (v),
 261           hb_prioritize)
 262   )
 263 }
 264 HB_FUNCOBJ (hb_match);
 265
 266 struct
 267 {
 268   private:
 269
 270   template <typename Proj, typename Val> auto
 271   impl (Proj&& f, Val &&v, hb_priority<2>) const HB_AUTO_RETURN
 272   (hb_deref (hb_forward<Proj> (f)).get (hb_forward<Val> (v)))
 273
 274   template <typename Proj, typename Val> auto
 275   impl (Proj&& f, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
 276   (
 277     hb_invoke (hb_forward<Proj> (f),
 278                hb_forward<Val> (v))
 279   )
 280
 281   template <typename Proj, typename Val> auto
 282   impl (Proj&& f, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
 283   (
 284     hb_forward<Proj> (f)[hb_forward<Val> (v)]
 285   )
 286
 287   public:
 288
 289   template <typename Proj, typename Val> auto
 290   operator () (Proj&& f, Val &&v) const HB_AUTO_RETURN
 291   (
 292     impl (hb_forward<Proj> (f),
 293           hb_forward<Val> (v),
 294           hb_prioritize)
 295   )
 296 }
 297 HB_FUNCOBJ (hb_get);
 298
 299
 300 template <typename T1, typename T2>
 301 struct hb_pair_t
 302 {
 303   typedef T1 first_t;
 304   typedef T2 second_t;
 305   typedef hb_pair_t<T1, T2> pair_t;
 306
 307   hb_pair_t (T1 a, T2 b) : first (a), second (b) {}
 308
 309   template <typename Q1, typename Q2,
 310             hb_enable_if (hb_is_convertible (T1, Q1) &&
 311                           hb_is_convertible (T2, T2))>
 312   operator hb_pair_t<Q1, Q2> () { return hb_pair_t<Q1, Q2> (first, second); }
 313
 314   hb_pair_t<T1, T2> reverse () const
 315   { return hb_pair_t<T1, T2> (second, first); }
 316
 317   bool operator == (const pair_t& o) const { return first == o.first && second == o.second; }
 318   bool operator != (const pair_t& o) const { return !(*this == o); }
 319   bool operator < (const pair_t& o) const { return first < o.first || (first == o.first && second < o.second); }
 320   bool operator >= (const pair_t& o) const { return !(*this < o); }
 321   bool operator > (const pair_t& o) const { return first > o.first || (first == o.first && second > o.second); }
 322   bool operator <= (const pair_t& o) const { return !(*this > o); }
 323
 324   T1 first;
 325   T2 second;
 326 };
 327 #define hb_pair_t(T1,T2) hb_pair_t<T1, T2>
 328 template <typename T1, typename T2> static inline hb_pair_t<T1, T2>
 329 hb_pair (T1&& a, T2&& b) { return hb_pair_t<T1, T2> (a, b); }
 330
 331 struct
 332 {
 333   template <typename Pair> constexpr typename Pair::first_t
 334   operator () (const Pair& pair) const { return pair.first; }
 335 }
 336 HB_FUNCOBJ (hb_first);
 337
 338 struct
 339 {
 340   template <typename Pair> constexpr typename Pair::second_t
 341   operator () (const Pair& pair) const { return pair.second; }
 342 }
 343 HB_FUNCOBJ (hb_second);
 344
 345 /* Note.  In min/max impl, we can use hb_type_identity<T> for second argument.
 346  * However, that would silently convert between different-signedness integers.
 347  * Instead we accept two different types, such that compiler can err if
 348  * comparing integers of different signedness. */
 349 struct
 350 {
 351   template <typename T, typename T2> constexpr auto
 352   operator () (T&& a, T2&& b) const HB_AUTO_RETURN
 353   (hb_forward<T> (a) <= hb_forward<T2> (b) ? hb_forward<T> (a) : hb_forward<T2> (b))
 354 }
 355 HB_FUNCOBJ (hb_min);
 356 struct
 357 {
 358   template <typename T, typename T2> constexpr auto
 359   operator () (T&& a, T2&& b) const HB_AUTO_RETURN
 360   (hb_forward<T> (a) >= hb_forward<T2> (b) ? hb_forward<T> (a) : hb_forward<T2> (b))
 361 }
 362 HB_FUNCOBJ (hb_max);
 363 struct
 364 {
 365   template <typename T, typename T2, typename T3> constexpr auto
 366   operator () (T&& x, T2&& min, T3&& max) const HB_AUTO_RETURN
 367   (hb_min (hb_max (hb_forward<T> (x), hb_forward<T2> (min)), hb_forward<T3> (max)))
 368 }
 369 HB_FUNCOBJ (hb_clamp);
 370
 371
 372 /*
 373  * Bithacks.
 374  */
 375
 376 /* Return the number of 1 bits in v. */
 377 template <typename T>
 378 static inline HB_CONST_FUNC unsigned int
 379 hb_popcount (T v)
 380 {
 381 #if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
 382   if (sizeof (T) <= sizeof (unsigned int))
 383     return __builtin_popcount (v);
 384
 385   if (sizeof (T) <= sizeof (unsigned long))
 386     return __builtin_popcountl (v);
 387
 388   if (sizeof (T) <= sizeof (unsigned long long))
 389     return __builtin_popcountll (v);
 390 #endif
 391
 392   if (sizeof (T) <= 4)
 393   {
 394     /* "HACKMEM 169" */
 395     uint32_t y;
 396     y = (v >> 1) &033333333333;
 397     y = v - y - ((y >>1) & 033333333333);
 398     return (((y + (y >> 3)) & 030707070707) % 077);
 399   }
 400
 401   if (sizeof (T) == 8)
 402   {
 403     unsigned int shift = 32;
 404     return hb_popcount<uint32_t> ((uint32_t) v) + hb_popcount ((uint32_t) (v >> shift));
 405   }
 406
 407   if (sizeof (T) == 16)
 408   {
 409     unsigned int shift = 64;
 410     return hb_popcount<uint64_t> ((uint64_t) v) + hb_popcount ((uint64_t) (v >> shift));
 411   }
 412
 413   assert (0);
 414   return 0; /* Shut up stupid compiler. */
 415 }
 416
 417 /* Returns the number of bits needed to store number */
 418 template <typename T>
 419 static inline HB_CONST_FUNC unsigned int
 420 hb_bit_storage (T v)
 421 {
 422   if (unlikely (!v)) return 0;
 423
 424 #if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
 425   if (sizeof (T) <= sizeof (unsigned int))
 426     return sizeof (unsigned int) * 8 - __builtin_clz (v);
 427
 428   if (sizeof (T) <= sizeof (unsigned long))
 429     return sizeof (unsigned long) * 8 - __builtin_clzl (v);
 430
 431   if (sizeof (T) <= sizeof (unsigned long long))
 432     return sizeof (unsigned long long) * 8 - __builtin_clzll (v);
 433 #endif
 434
 435 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
 436   if (sizeof (T) <= sizeof (unsigned int))
 437   {
 438     unsigned long where;
 439     _BitScanReverse (&where, v);
 440     return 1 + where;
 441   }
 442 # if defined(_WIN64)
 443   if (sizeof (T) <= 8)
 444   {
 445     unsigned long where;
 446     _BitScanReverse64 (&where, v);
 447     return 1 + where;
 448   }
 449 # endif
 450 #endif
 451
 452   if (sizeof (T) <= 4)
 453   {
 454     /* "bithacks" */
 455     const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
 456     const unsigned int S[] = {1, 2, 4, 8, 16};
 457     unsigned int r = 0;
 458     for (int i = 4; i >= 0; i--)
 459       if (v & b[i])
 460       {
 461         v >>= S[i];
 462         r |= S[i];
 463       }
 464     return r + 1;
 465   }
 466   if (sizeof (T) <= 8)
 467   {
 468     /* "bithacks" */
 469     const uint64_t b[] = {0x2ULL, 0xCULL, 0xF0ULL, 0xFF00ULL, 0xFFFF0000ULL, 0xFFFFFFFF00000000ULL};
 470     const unsigned int S[] = {1, 2, 4, 8, 16, 32};
 471     unsigned int r = 0;
 472     for (int i = 5; i >= 0; i--)
 473       if (v & b[i])
 474       {
 475         v >>= S[i];
 476         r |= S[i];
 477       }
 478     return r + 1;
 479   }
 480   if (sizeof (T) == 16)
 481   {
 482     unsigned int shift = 64;
 483     return (v >> shift) ? hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift :
 484                           hb_bit_storage<uint64_t> ((uint64_t) v);
 485   }
 486
 487   assert (0);
 488   return 0; /* Shut up stupid compiler. */
 489 }
 490
 491 /* Returns the number of zero bits in the least significant side of v */
 492 template <typename T>
 493 static inline HB_CONST_FUNC unsigned int
 494 hb_ctz (T v)
 495 {
 496   if (unlikely (!v)) return 8 * sizeof (T);
 497
 498 #if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
 499   if (sizeof (T) <= sizeof (unsigned int))
 500     return __builtin_ctz (v);
 501
 502   if (sizeof (T) <= sizeof (unsigned long))
 503     return __builtin_ctzl (v);
 504
 505   if (sizeof (T) <= sizeof (unsigned long long))
 506     return __builtin_ctzll (v);
 507 #endif
 508
 509 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
 510   if (sizeof (T) <= sizeof (unsigned int))
 511   {
 512     unsigned long where;
 513     _BitScanForward (&where, v);
 514     return where;
 515   }
 516 # if defined(_WIN64)
 517   if (sizeof (T) <= 8)
 518   {
 519     unsigned long where;
 520     _BitScanForward64 (&where, v);
 521     return where;
 522   }
 523 # endif
 524 #endif
 525
 526   if (sizeof (T) <= 4)
 527   {
 528     /* "bithacks" */
 529     unsigned int c = 32;
 530     v &= - (int32_t) v;
 531     if (v) c--;
 532     if (v & 0x0000FFFF) c -= 16;
 533     if (v & 0x00FF00FF) c -= 8;
 534     if (v & 0x0F0F0F0F) c -= 4;
 535     if (v & 0x33333333) c -= 2;
 536     if (v & 0x55555555) c -= 1;
 537     return c;
 538   }
 539   if (sizeof (T) <= 8)
 540   {
 541     /* "bithacks" */
 542     unsigned int c = 64;
 543     v &= - (int64_t) (v);
 544     if (v) c--;
 545     if (v & 0x00000000FFFFFFFFULL) c -= 32;
 546     if (v & 0x0000FFFF0000FFFFULL) c -= 16;
 547     if (v & 0x00FF00FF00FF00FFULL) c -= 8;
 548     if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4;
 549     if (v & 0x3333333333333333ULL) c -= 2;
 550     if (v & 0x5555555555555555ULL) c -= 1;
 551     return c;
 552   }
 553   if (sizeof (T) == 16)
 554   {
 555     unsigned int shift = 64;
 556     return (uint64_t) v ? hb_bit_storage<uint64_t> ((uint64_t) v) :
 557                           hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift;
 558   }
 559
 560   assert (0);
 561   return 0; /* Shut up stupid compiler. */
 562 }
 563
 564
 565 /*
 566  * Tiny stuff.
 567  */
 568
 569 /* ASCII tag/character handling */
 570 static inline bool ISALPHA (unsigned char c)
 571 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); }
 572 static inline bool ISALNUM (unsigned char c)
 573 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); }
 574 static inline bool ISSPACE (unsigned char c)
 575 { return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; }
 576 static inline unsigned char TOUPPER (unsigned char c)
 577 { return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; }
 578 static inline unsigned char TOLOWER (unsigned char c)
 579 { return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; }
 580 static inline bool ISHEX (unsigned char c)
 581 { return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'); }
 582 static inline unsigned char TOHEX (uint8_t c)
 583 { return (c & 0xF) <= 9 ? (c & 0xF) + '0' : (c & 0xF) + 'a' - 10; }
 584 static inline uint8_t FROMHEX (unsigned char c)
 585 { return (c >= '0' && c <= '9') ? c - '0' : TOLOWER (c) - 'a' + 10; }
 586
 587 static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)
 588 { return (a + (b - 1)) / b; }
 589
 590
 591 #undef  ARRAY_LENGTH
 592 template <typename Type, unsigned int n>
 593 static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }
 594 /* A const version, but does not detect erratically being called on pointers. */
 595 #define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
 596
 597
 598 static inline int
 599 hb_memcmp (const void *a, const void *b, unsigned int len)
 600 {
 601   /* It's illegal to pass NULL to memcmp(), even if len is zero.
 602    * So, wrap it.
 603    * https://sourceware.org/bugzilla/show_bug.cgi?id=23878 */
 604   if (unlikely (!len)) return 0;
 605   return memcmp (a, b, len);
 606 }
 607
 608 static inline void *
 609 hb_memset (void *s, int c, unsigned int n)
 610 {
 611   /* It's illegal to pass NULL to memset(), even if n is zero. */
 612   if (unlikely (!n)) return 0;
 613   return memset (s, c, n);
 614 }
 615
 616 static inline unsigned int
 617 hb_ceil_to_4 (unsigned int v)
 618 {
 619   return ((v - 1) | 3) + 1;
 620 }
 621
 622 template <typename T> static inline bool
 623 hb_in_range (T u, T lo, T hi)
 624 {
 625   static_assert (!hb_is_signed<T>::value, "");
 626
 627   /* The casts below are important as if T is smaller than int,
 628    * the subtract results will become a signed int! */
 629   return (T)(u - lo) <= (T)(hi - lo);
 630 }
 631 template <typename T> static inline bool
 632 hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2)
 633 {
 634   return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2);
 635 }
 636 template <typename T> static inline bool
 637 hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3)
 638 {
 639   return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2) || hb_in_range (u, lo3, hi3);
 640 }
 641
 642
 643 /*
 644  * Overflow checking.
 645  */
 646
 647 /* Consider __builtin_mul_overflow use here also */
 648 static inline bool
 649 hb_unsigned_mul_overflows (unsigned int count, unsigned int size)
 650 {
 651   return (size > 0) && (count >= ((unsigned int) -1) / size);
 652 }
 653
 654
 655 /*
 656  * Sort and search.
 657  */
 658
 659 template <typename K, typename V, typename ...Ts>
 660 static int
 661 _hb_cmp_method (const void *pkey, const void *pval, Ts... ds)
 662 {
 663   const K& key = * (const K*) pkey;
 664   const V& val = * (const V*) pval;
 665
 666   return val.cmp (key, ds...);
 667 }
 668
 669 template <typename V, typename K, typename ...Ts>
 670 static inline bool
 671 hb_bsearch_impl (unsigned *pos, /* Out */
 672                  const K& key,
 673                  V* base, size_t nmemb, size_t stride,
 674                  int (*compar)(const void *_key, const void *_item, Ts... _ds),
 675                  Ts... ds)
 676 {
 677   /* This is our *only* bsearch implementation. */
 678
 679   int min = 0, max = (int) nmemb - 1;
 680   while (min <= max)
 681   {
 682     int mid = ((unsigned int) min + (unsigned int) max) / 2;
 683 #pragma GCC diagnostic push
 684 #pragma GCC diagnostic ignored "-Wcast-align"
 685     V* p = (V*) (((const char *) base) + (mid * stride));
 686 #pragma GCC diagnostic pop
 687     int c = compar ((const void *) hb_addressof (key), (const void *) p, ds...);
 688     if (c < 0)
 689       max = mid - 1;
 690     else if (c > 0)
 691       min = mid + 1;
 692     else
 693     {
 694       *pos = mid;
 695       return true;
 696     }
 697   }
 698   *pos = min;
 699   return false;
 700 }
 701
 702 template <typename V, typename K>
 703 static inline V*
 704 hb_bsearch (const K& key, V* base,
 705             size_t nmemb, size_t stride = sizeof (V),
 706             int (*compar)(const void *_key, const void *_item) = _hb_cmp_method<K, V>)
 707 {
 708   unsigned pos;
 709 #pragma GCC diagnostic push
 710 #pragma GCC diagnostic ignored "-Wcast-align"
 711   return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar) ?
 712          (V*) (((const char *) base) + (pos * stride)) : nullptr;
 713 #pragma GCC diagnostic pop
 714 }
 715 template <typename V, typename K, typename ...Ts>
 716 static inline V*
 717 hb_bsearch (const K& key, V* base,
 718             size_t nmemb, size_t stride,
 719             int (*compar)(const void *_key, const void *_item, Ts... _ds),
 720             Ts... ds)
 721 {
 722   unsigned pos;
 723 #pragma GCC diagnostic push
 724 #pragma GCC diagnostic ignored "-Wcast-align"
 725   return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar, ds...) ?
 726          (V*) (((const char *) base) + (pos * stride)) : nullptr;
 727 #pragma GCC diagnostic pop
 728 }
 729
 730
 731 /* From https://github.com/noporpoise/sort_r
 732    Feb 5, 2019 (c8c65c1e)
 733    Modified to support optional argument using templates */
 734
 735 /* Isaac Turner 29 April 2014 Public Domain */
 736
 737 /*
 738 hb_qsort function to be exported.
 739 Parameters:
 740   base is the array to be sorted
 741   nel is the number of elements in the array
 742   width is the size in bytes of each element of the array
 743   compar is the comparison function
 744   arg (optional) is a pointer to be passed to the comparison function
 745
 746 void hb_qsort(void *base, size_t nel, size_t width,
 747               int (*compar)(const void *_a, const void *_b, [void *_arg]),
 748               [void *arg]);
 749 */
 750
 751 #define SORT_R_SWAP(a,b,tmp) ((tmp) = (a), (a) = (b), (b) = (tmp))
 752
 753 /* swap a and b */
 754 /* a and b must not be equal! */
 755 static inline void sort_r_swap(char *__restrict a, char *__restrict b,
 756                                size_t w)
 757 {
 758   char tmp, *end = a+w;
 759   for(; a < end; a++, b++) { SORT_R_SWAP(*a, *b, tmp); }
 760 }
 761
 762 /* swap a, b iff a>b */
 763 /* a and b must not be equal! */
 764 /* __restrict is same as restrict but better support on old machines */
 765 template <typename ...Ts>
 766 static inline int sort_r_cmpswap(char *__restrict a,
 767                                  char *__restrict b, size_t w,
 768                                  int (*compar)(const void *_a,
 769                                                const void *_b,
 770                                                Ts... _ds),
 771                                  Ts... ds)
 772 {
 773   if(compar(a, b, ds...) > 0) {
 774     sort_r_swap(a, b, w);
 775     return 1;
 776   }
 777   return 0;
 778 }
 779
 780 /*
 781 Swap consecutive blocks of bytes of size na and nb starting at memory addr ptr,
 782 with the smallest swap so that the blocks are in the opposite order. Blocks may
 783 be internally re-ordered e.g.
 784   12345ab  ->   ab34512
 785   123abc   ->   abc123
 786   12abcde  ->   deabc12
 787 */
 788 static inline void sort_r_swap_blocks(char *ptr, size_t na, size_t nb)
 789 {
 790   if(na > 0 && nb > 0) {
 791     if(na > nb) { sort_r_swap(ptr, ptr+na, nb); }
 792     else { sort_r_swap(ptr, ptr+nb, na); }
 793   }
 794 }
 795
 796 /* Implement recursive quicksort ourselves */
 797 /* Note: quicksort is not stable, equivalent values may be swapped */
 798 template <typename ...Ts>
 799 static inline void sort_r_simple(void *base, size_t nel, size_t w,
 800                                  int (*compar)(const void *_a,
 801                                                const void *_b,
 802                                                Ts... _ds),
 803                                  Ts... ds)
 804 {
 805   char *b = (char *)base, *end = b + nel*w;
 806
 807   /* for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
 808   printf("\n"); */
 809
 810   if(nel < 10) {
 811     /* Insertion sort for arbitrarily small inputs */
 812     char *pi, *pj;
 813     for(pi = b+w; pi < end; pi += w) {
 814       for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,ds...); pj -= w) {}
 815     }
 816   }
 817   else
 818   {
 819     /* nel > 9; Quicksort */
 820
 821     int cmp;
 822     char *pl, *ple, *pr, *pre, *pivot;
 823     char *last = b+w*(nel-1), *tmp;
 824
 825     /*
 826     Use median of second, middle and second-last items as pivot.
 827     First and last may have been swapped with pivot and therefore be extreme
 828     */
 829     char *l[3];
 830     l[0] = b + w;
 831     l[1] = b+w*(nel/2);
 832     l[2] = last - w;
 833
 834     /* printf("pivots: %i, %i, %i\n", *(int*)l[0], *(int*)l[1], *(int*)l[2]); */
 835
 836     if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
 837     if(compar(l[1],l[2],ds...) > 0) {
 838       SORT_R_SWAP(l[1], l[2], tmp);
 839       if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
 840     }
 841
 842     /* swap mid value (l[1]), and last element to put pivot as last element */
 843     if(l[1] != last) { sort_r_swap(l[1], last, w); }
 844
 845     /*
 846     pl is the next item on the left to be compared to the pivot
 847     pr is the last item on the right that was compared to the pivot
 848     ple is the left position to put the next item that equals the pivot
 849     ple is the last right position where we put an item that equals the pivot
 850                                            v- end (beyond the array)
 851       EEEEEELLLLLLLLuuuuuuuuGGGGGGGEEEEEEEE.
 852       ^- b  ^- ple  ^- pl   ^- pr  ^- pre ^- last (where the pivot is)
 853     Pivot comparison key:
 854       E = equal, L = less than, u = unknown, G = greater than, E = equal
 855     */
 856     pivot = last;
 857     ple = pl = b;
 858     pre = pr = last;
 859
 860     /*
 861     Strategy:
 862     Loop into the list from the left and right at the same time to find:
 863     - an item on the left that is greater than the pivot
 864     - an item on the right that is less than the pivot
 865     Once found, they are swapped and the loop continues.
 866     Meanwhile items that are equal to the pivot are moved to the edges of the
 867     array.
 868     */
 869     while(pl < pr) {
 870       /* Move left hand items which are equal to the pivot to the far left.
 871          break when we find an item that is greater than the pivot */
 872       for(; pl < pr; pl += w) {
 873         cmp = compar(pl, pivot, ds...);
 874         if(cmp > 0) { break; }
 875         else if(cmp == 0) {
 876           if(ple < pl) { sort_r_swap(ple, pl, w); }
 877           ple += w;
 878         }
 879       }
 880       /* break if last batch of left hand items were equal to pivot */
 881       if(pl >= pr) { break; }
 882       /* Move right hand items which are equal to the pivot to the far right.
 883          break when we find an item that is less than the pivot */
 884       for(; pl < pr; ) {
 885         pr -= w; /* Move right pointer onto an unprocessed item */
 886         cmp = compar(pr, pivot, ds...);
 887         if(cmp == 0) {
 888           pre -= w;
 889           if(pr < pre) { sort_r_swap(pr, pre, w); }
 890         }
 891         else if(cmp < 0) {
 892           if(pl < pr) { sort_r_swap(pl, pr, w); }
 893           pl += w;
 894           break;
 895         }
 896       }
 897     }
 898
 899     pl = pr; /* pr may have gone below pl */
 900
 901     /*
 902     Now we need to go from: EEELLLGGGGEEEE
 903                         to: LLLEEEEEEEGGGG
 904     Pivot comparison key:
 905       E = equal, L = less than, u = unknown, G = greater than, E = equal
 906     */
 907     sort_r_swap_blocks(b, ple-b, pl-ple);
 908     sort_r_swap_blocks(pr, pre-pr, end-pre);
 909
 910     /*for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
 911     printf("\n");*/
 912
 913     sort_r_simple(b, (pl-ple)/w, w, compar, ds...);
 914     sort_r_simple(end-(pre-pr), (pre-pr)/w, w, compar, ds...);
 915   }
 916 }
 917
 918 static inline void
 919 hb_qsort (void *base, size_t nel, size_t width,
 920           int (*compar)(const void *_a, const void *_b))
 921 {
 922 #if defined(__OPTIMIZE_SIZE__) && !defined(HB_USE_INTERNAL_QSORT)
 923   qsort (base, nel, width, compar);
 924 #else
 925   sort_r_simple (base, nel, width, compar);
 926 #endif
 927 }
 928
 929 static inline void
 930 hb_qsort (void *base, size_t nel, size_t width,
 931           int (*compar)(const void *_a, const void *_b, void *_arg),
 932           void *arg)
 933 {
 934 #ifdef HAVE_GNU_QSORT_R
 935   qsort_r (base, nel, width, compar, arg);
 936 #else
 937   sort_r_simple (base, nel, width, compar, arg);
 938 #endif
 939 }
 940
 941
 942 template <typename T, typename T2, typename T3> static inline void
 943 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T2 *, const T2 *), T3 *array2)
 944 {
 945   for (unsigned int i = 1; i < len; i++)
 946   {
 947     unsigned int j = i;
 948     while (j && compar (&array[j - 1], &array[i]) > 0)
 949       j--;
 950     if (i == j)
 951       continue;
 952     /* Move item i to occupy place for item j, shift what's in between. */
 953     {
 954       T t = array[i];
 955       memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
 956       array[j] = t;
 957     }
 958     if (array2)
 959     {
 960       T3 t = array2[i];
 961       memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T3));
 962       array2[j] = t;
 963     }
 964   }
 965 }
 966
 967 template <typename T> static inline void
 968 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
 969 {
 970   hb_stable_sort (array, len, compar, (int *) nullptr);
 971 }
 972
 973 static inline hb_bool_t
 974 hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out)
 975 {
 976   unsigned int v;
 977   const char *p = s;
 978   const char *end = p + len;
 979   if (unlikely (!hb_parse_uint (&p, end, &v, true/* whole buffer */, base)))
 980     return false;
 981
 982   *out = v;
 983   return true;
 984 }
 985
 986
 987 /* Operators. */
 988
 989 struct hb_bitwise_and
 990 { HB_PARTIALIZE(2);
 991   static constexpr bool passthru_left = false;
 992   static constexpr bool passthru_right = false;
 993   template <typename T> constexpr auto
 994   operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & b)
 995 }
 996 HB_FUNCOBJ (hb_bitwise_and);
 997 struct hb_bitwise_or
 998 { HB_PARTIALIZE(2);
 999   static constexpr bool passthru_left = true;
1000   static constexpr bool passthru_right = true;
1001   template <typename T> constexpr auto
1002   operator () (const T &a, const T &b) const HB_AUTO_RETURN (a | b)
1003 }
1004 HB_FUNCOBJ (hb_bitwise_or);
1005 struct hb_bitwise_xor
1006 { HB_PARTIALIZE(2);
1007   static constexpr bool passthru_left = true;
1008   static constexpr bool passthru_right = true;
1009   template <typename T> constexpr auto
1010   operator () (const T &a, const T &b) const HB_AUTO_RETURN (a ^ b)
1011 }
1012 HB_FUNCOBJ (hb_bitwise_xor);
1013 struct hb_bitwise_sub
1014 { HB_PARTIALIZE(2);
1015   static constexpr bool passthru_left = true;
1016   static constexpr bool passthru_right = false;
1017   template <typename T> constexpr auto
1018   operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & ~b)
1019 }
1020 HB_FUNCOBJ (hb_bitwise_sub);
1021 struct
1022 {
1023   template <typename T> constexpr auto
1024   operator () (const T &a) const HB_AUTO_RETURN (~a)
1025 }
1026 HB_FUNCOBJ (hb_bitwise_neg);
1027
1028 struct
1029 { HB_PARTIALIZE(2);
1030   template <typename T, typename T2> constexpr auto
1031   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a + b)
1032 }
1033 HB_FUNCOBJ (hb_add);
1034 struct
1035 { HB_PARTIALIZE(2);
1036   template <typename T, typename T2> constexpr auto
1037   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a - b)
1038 }
1039 HB_FUNCOBJ (hb_sub);
1040 struct
1041 { HB_PARTIALIZE(2);
1042   template <typename T, typename T2> constexpr auto
1043   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a * b)
1044 }
1045 HB_FUNCOBJ (hb_mul);
1046 struct
1047 { HB_PARTIALIZE(2);
1048   template <typename T, typename T2> constexpr auto
1049   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a / b)
1050 }
1051 HB_FUNCOBJ (hb_div);
1052 struct
1053 { HB_PARTIALIZE(2);
1054   template <typename T, typename T2> constexpr auto
1055   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a % b)
1056 }
1057 HB_FUNCOBJ (hb_mod);
1058 struct
1059 {
1060   template <typename T> constexpr auto
1061   operator () (const T &a) const HB_AUTO_RETURN (+a)
1062 }
1063 HB_FUNCOBJ (hb_pos);
1064 struct
1065 {
1066   template <typename T> constexpr auto
1067   operator () (const T &a) const HB_AUTO_RETURN (-a)
1068 }
1069 HB_FUNCOBJ (hb_neg);
1070 struct
1071 {
1072   template <typename T> constexpr auto
1073   operator () (T &a) const HB_AUTO_RETURN (++a)
1074 }
1075 HB_FUNCOBJ (hb_inc);
1076 struct
1077 {
1078   template <typename T> constexpr auto
1079   operator () (T &a) const HB_AUTO_RETURN (--a)
1080 }
1081 HB_FUNCOBJ (hb_dec);
1082
1083
1084 /* Compiler-assisted vectorization. */
1085
1086 /* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))),
1087  * basically a fixed-size bitset. */
1088 template <typename elt_t, unsigned int byte_size>
1089 struct hb_vector_size_t
1090 {
1091   elt_t& operator [] (unsigned int i) { return v[i]; }
1092   const elt_t& operator [] (unsigned int i) const { return v[i]; }
1093
1094   void clear (unsigned char v = 0) { memset (this, v, sizeof (*this)); }
1095
1096   template <typename Op>
1097   hb_vector_size_t process (const Op& op) const
1098   {
1099     hb_vector_size_t r;
1100     for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
1101       r.v[i] = op (v[i]);
1102     return r;
1103   }
1104   template <typename Op>
1105   hb_vector_size_t process (const Op& op, const hb_vector_size_t &o) const
1106   {
1107     hb_vector_size_t r;
1108     for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
1109       r.v[i] = op (v[i], o.v[i]);
1110     return r;
1111   }
1112   hb_vector_size_t operator | (const hb_vector_size_t &o) const
1113   { return process (hb_bitwise_or, o); }
1114   hb_vector_size_t operator & (const hb_vector_size_t &o) const
1115   { return process (hb_bitwise_and, o); }
1116   hb_vector_size_t operator ^ (const hb_vector_size_t &o) const
1117   { return process (hb_bitwise_xor, o); }
1118   hb_vector_size_t operator ~ () const
1119   { return process (hb_bitwise_neg); }
1120
1121   private:
1122   static_assert (0 == byte_size % sizeof (elt_t), "");
1123   elt_t v[byte_size / sizeof (elt_t)];
1124 };
1125
1126
1127 #endif /* HB_ALGS_HH */