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 #include <algorithm>
  38 #include <initializer_list>
  39 #include <functional>
  40 #include <new>
  41
  42 /*
  43  * Flags
  44  */
  45
  46 /* Enable bitwise ops on enums marked as flags_t */
  47 /* To my surprise, looks like the function resolver is happy to silently cast
  48  * one enum to another...  So this doesn't provide the type-checking that I
  49  * originally had in mind... :(.
  50  *
  51  * For MSVC warnings, see: https://github.com/harfbuzz/harfbuzz/pull/163
  52  */
  53 #ifdef _MSC_VER
  54 # pragma warning(disable:4200)
  55 # pragma warning(disable:4800)
  56 #endif
  57 #define HB_MARK_AS_FLAG_T(T) \
  58         extern "C++" { \
  59           static inline constexpr T operator | (T l, T r) { return T ((unsigned) l | (unsigned) r); } \
  60           static inline constexpr T operator & (T l, T r) { return T ((unsigned) l & (unsigned) r); } \
  61           static inline constexpr T operator ^ (T l, T r) { return T ((unsigned) l ^ (unsigned) r); } \
  62           static inline constexpr unsigned operator ~ (T r) { return (~(unsigned) r); } \
  63           static inline T& operator |= (T &l, T r) { l = l | r; return l; } \
  64           static inline T& operator &= (T& l, T r) { l = l & r; return l; } \
  65           static inline T& operator ^= (T& l, T r) { l = l ^ r; return l; } \
  66         } \
  67         static_assert (true, "")
  68
  69 /* Useful for set-operations on small enums.
  70  * For example, for testing "x ∈ {x1, x2, x3}" use:
  71  * (FLAG_UNSAFE(x) & (FLAG(x1) | FLAG(x2) | FLAG(x3)))
  72  */
  73 #define FLAG(x) (static_assert_expr ((unsigned)(x) < 32) + (((uint32_t) 1U) << (unsigned)(x)))
  74 #define FLAG_UNSAFE(x) ((unsigned)(x) < 32 ? (((uint32_t) 1U) << (unsigned)(x)) : 0)
  75 #define FLAG_RANGE(x,y) (static_assert_expr ((x) < (y)) + FLAG(y+1) - FLAG(x))
  76 #define FLAG64(x) (static_assert_expr ((unsigned)(x) < 64) + (((uint64_t) 1ULL) << (unsigned)(x)))
  77 #define FLAG64_UNSAFE(x) ((unsigned)(x) < 64 ? (((uint64_t) 1ULL) << (unsigned)(x)) : 0)
  78
  79
  80 /*
  81  * Big-endian integers.
  82  */
  83
  84 /* Endian swap, used in Windows related backends */
  85 static inline constexpr uint16_t hb_uint16_swap (uint16_t v)
  86 { return (v >> 8) | (v << 8); }
  87 static inline constexpr uint32_t hb_uint32_swap (uint32_t v)
  88 { return (hb_uint16_swap (v) << 16) | hb_uint16_swap (v >> 16); }
  89
  90 #ifndef HB_FAST_INT_ACCESS
  91 #if defined(__OPTIMIZE__) && \
  92     defined(__BYTE_ORDER) && \
  93     (__BYTE_ORDER == __BIG_ENDIAN || \
  94      (__BYTE_ORDER == __LITTLE_ENDIAN && \
  95       hb_has_builtin(__builtin_bswap16) && \
  96       hb_has_builtin(__builtin_bswap32)))
  97 #define HB_FAST_INT_ACCESS 1
  98 #else
  99 #define HB_FAST_INT_ACCESS 0
 100 #endif
 101 #endif
 102
 103 template <typename Type, int Bytes = sizeof (Type)>
 104 struct BEInt;
 105 template <typename Type>
 106 struct BEInt<Type, 1>
 107 {
 108   public:
 109   BEInt () = default;
 110   constexpr BEInt (Type V) : v {uint8_t (V)} {}
 111   constexpr operator Type () const { return v; }
 112   private: uint8_t v;
 113 };
 114 template <typename Type>
 115 struct BEInt<Type, 2>
 116 {
 117   struct __attribute__((packed)) packed_uint16_t { uint16_t v; };
 118
 119   public:
 120   BEInt () = default;
 121
 122   BEInt (Type V)
 123 #if HB_FAST_INT_ACCESS
 124 #if __BYTE_ORDER == __LITTLE_ENDIAN
 125   { ((packed_uint16_t *) v)->v = __builtin_bswap16 (V); }
 126 #else /* __BYTE_ORDER == __BIG_ENDIAN */
 127   { ((packed_uint16_t *) v)->v = V; }
 128 #endif
 129 #else
 130     : v {uint8_t ((V >>  8) & 0xFF),
 131          uint8_t ((V      ) & 0xFF)} {}
 132 #endif
 133
 134   constexpr operator Type () const {
 135 #if HB_FAST_INT_ACCESS
 136 #if __BYTE_ORDER == __LITTLE_ENDIAN
 137     return __builtin_bswap16 (((packed_uint16_t *) v)->v);
 138 #else /* __BYTE_ORDER == __BIG_ENDIAN */
 139     return ((packed_uint16_t *) v)->v;
 140 #endif
 141 #else
 142     return (v[0] <<  8)
 143          + (v[1]      );
 144 #endif
 145   }
 146   private: uint8_t v[2];
 147 };
 148 template <typename Type>
 149 struct BEInt<Type, 3>
 150 {
 151   static_assert (!std::is_signed<Type>::value, "");
 152   public:
 153   BEInt () = default;
 154   constexpr BEInt (Type V) : v {uint8_t ((V >> 16) & 0xFF),
 155                                 uint8_t ((V >>  8) & 0xFF),
 156                                 uint8_t ((V      ) & 0xFF)} {}
 157
 158   constexpr operator Type () const { return (v[0] << 16)
 159                                           + (v[1] <<  8)
 160                                           + (v[2]      ); }
 161   private: uint8_t v[3];
 162 };
 163 template <typename Type>
 164 struct BEInt<Type, 4>
 165 {
 166   struct __attribute__((packed)) packed_uint32_t { uint32_t v; };
 167
 168   public:
 169   BEInt () = default;
 170
 171   BEInt (Type V)
 172 #if HB_FAST_INT_ACCESS
 173 #if __BYTE_ORDER == __LITTLE_ENDIAN
 174   { ((packed_uint32_t *) v)->v = __builtin_bswap32 (V); }
 175 #else /* __BYTE_ORDER == __BIG_ENDIAN */
 176   { ((packed_uint32_t *) v)->v = V; }
 177 #endif
 178 #else
 179     : v {uint8_t ((V >> 24) & 0xFF),
 180          uint8_t ((V >> 16) & 0xFF),
 181          uint8_t ((V >>  8) & 0xFF),
 182          uint8_t ((V      ) & 0xFF)} {}
 183 #endif
 184
 185   constexpr operator Type () const {
 186 #if HB_FAST_INT_ACCESS
 187 #if __BYTE_ORDER == __LITTLE_ENDIAN
 188     return __builtin_bswap32 (((packed_uint32_t *) v)->v);
 189 #else /* __BYTE_ORDER == __BIG_ENDIAN */
 190     return ((packed_uint32_t *) v)->v;
 191 #endif
 192 #else
 193     return (v[0] << 24)
 194          + (v[1] << 16)
 195          + (v[2] <<  8)
 196          + (v[3]      );
 197 #endif
 198   }
 199   private: uint8_t v[4];
 200 };
 201
 202 /* Floats. */
 203
 204 /* We want our rounding towards +infinity. */
 205 static inline float
 206 _hb_roundf (float x) { return floorf (x + .5f); }
 207 #define roundf(x) _hb_roundf(x)
 208
 209
 210 /* Encodes three unsigned integers in one 64-bit number.  If the inputs have more than 21 bits,
 211  * values will be truncated / overlap, and might not decode exactly. */
 212 #define HB_CODEPOINT_ENCODE3(x,y,z) (((uint64_t) (x) << 42) | ((uint64_t) (y) << 21) | (uint64_t) (z))
 213 #define HB_CODEPOINT_DECODE3_1(v) ((hb_codepoint_t) ((v) >> 42))
 214 #define HB_CODEPOINT_DECODE3_2(v) ((hb_codepoint_t) ((v) >> 21) & 0x1FFFFFu)
 215 #define HB_CODEPOINT_DECODE3_3(v) ((hb_codepoint_t) (v) & 0x1FFFFFu)
 216
 217 /* Custom encoding used by hb-ucd. */
 218 #define HB_CODEPOINT_ENCODE3_11_7_14(x,y,z) (((uint32_t) ((x) & 0x07FFu) << 21) | (((uint32_t) (y) & 0x007Fu) << 14) | (uint32_t) ((z) & 0x3FFFu))
 219 #define HB_CODEPOINT_DECODE3_11_7_14_1(v) ((hb_codepoint_t) ((v) >> 21))
 220 #define HB_CODEPOINT_DECODE3_11_7_14_2(v) ((hb_codepoint_t) (((v) >> 14) & 0x007Fu) | 0x0300)
 221 #define HB_CODEPOINT_DECODE3_11_7_14_3(v) ((hb_codepoint_t) (v) & 0x3FFFu)
 222
 223
 224 struct
 225 {
 226   /* Note.  This is dangerous in that if it's passed an rvalue, it returns rvalue-reference. */
 227   template <typename T> constexpr auto
 228   operator () (T&& v) const HB_AUTO_RETURN ( std::forward<T> (v) )
 229 }
 230 HB_FUNCOBJ (hb_identity);
 231 struct
 232 {
 233   /* Like identity(), but only retains lvalue-references.  Rvalues are returned as rvalues. */
 234   template <typename T> constexpr T&
 235   operator () (T& v) const { return v; }
 236
 237   template <typename T> constexpr hb_remove_reference<T>
 238   operator () (T&& v) const { return v; }
 239 }
 240 HB_FUNCOBJ (hb_lidentity);
 241 struct
 242 {
 243   /* Like identity(), but always returns rvalue. */
 244   template <typename T> constexpr hb_remove_reference<T>
 245   operator () (T&& v) const { return v; }
 246 }
 247 HB_FUNCOBJ (hb_ridentity);
 248
 249 struct
 250 {
 251   template <typename T> constexpr bool
 252   operator () (T&& v) const { return bool (std::forward<T> (v)); }
 253 }
 254 HB_FUNCOBJ (hb_bool);
 255
 256
 257 /* The MIT License
 258
 259    Copyright (C) 2012 Zilong Tan (eric.zltan@gmail.com)
 260
 261    Permission is hereby granted, free of charge, to any person
 262    obtaining a copy of this software and associated documentation
 263    files (the "Software"), to deal in the Software without
 264    restriction, including without limitation the rights to use, copy,
 265    modify, merge, publish, distribute, sublicense, and/or sell copies
 266    of the Software, and to permit persons to whom the Software is
 267    furnished to do so, subject to the following conditions:
 268
 269    The above copyright notice and this permission notice shall be
 270    included in all copies or substantial portions of the Software.
 271
 272    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 273    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 274    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 275    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 276    BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 277    ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 278    CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 279    SOFTWARE.
 280 */
 281
 282
 283 // Compression function for Merkle-Damgard construction.
 284 // This function is generated using the framework provided.
 285 #define mix(h) (                                        \
 286                         (void) ((h) ^= (h) >> 23),              \
 287                         (void) ((h) *= 0x2127599bf4325c37ULL),  \
 288                         (h) ^= (h) >> 47)
 289
 290 static inline uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
 291 {
 292         struct __attribute__((packed)) packed_uint64_t { uint64_t v; };
 293         const uint64_t    m = 0x880355f21e6d1965ULL;
 294         const packed_uint64_t *pos = (const packed_uint64_t *)buf;
 295         const packed_uint64_t *end = pos + (len / 8);
 296         const unsigned char *pos2;
 297         uint64_t h = seed ^ (len * m);
 298         uint64_t v;
 299
 300 #ifndef HB_OPTIMIZE_SIZE
 301         if (((uintptr_t) pos & 7) == 0)
 302         {
 303           while (pos != end)
 304           {
 305 #pragma GCC diagnostic push
 306 #pragma GCC diagnostic ignored "-Wcast-align"
 307             v  = * (const uint64_t *) (pos++);
 308 #pragma GCC diagnostic pop
 309             h ^= mix(v);
 310             h *= m;
 311           }
 312         }
 313         else
 314 #endif
 315         {
 316           while (pos != end)
 317           {
 318             v  = pos++->v;
 319             h ^= mix(v);
 320             h *= m;
 321           }
 322         }
 323
 324         pos2 = (const unsigned char*)pos;
 325         v = 0;
 326
 327         switch (len & 7) {
 328         case 7: v ^= (uint64_t)pos2[6] << 48; HB_FALLTHROUGH;
 329         case 6: v ^= (uint64_t)pos2[5] << 40; HB_FALLTHROUGH;
 330         case 5: v ^= (uint64_t)pos2[4] << 32; HB_FALLTHROUGH;
 331         case 4: v ^= (uint64_t)pos2[3] << 24; HB_FALLTHROUGH;
 332         case 3: v ^= (uint64_t)pos2[2] << 16; HB_FALLTHROUGH;
 333         case 2: v ^= (uint64_t)pos2[1] <<  8; HB_FALLTHROUGH;
 334         case 1: v ^= (uint64_t)pos2[0];
 335                 h ^= mix(v);
 336                 h *= m;
 337         }
 338
 339         return mix(h);
 340 }
 341
 342 static inline uint32_t fasthash32(const void *buf, size_t len, uint32_t seed)
 343 {
 344         // the following trick converts the 64-bit hashcode to Fermat
 345         // residue, which shall retain information from both the higher
 346         // and lower parts of hashcode.
 347         uint64_t h = fasthash64(buf, len, seed);
 348         return h - (h >> 32);
 349 }
 350
 351 struct
 352 {
 353   private:
 354
 355   template <typename T> constexpr auto
 356   impl (const T& v, hb_priority<2>) const HB_RETURN (uint32_t, hb_deref (v).hash ())
 357
 358   // Horrible: std:hash() of integers seems to be identity in gcc / clang?!
 359   // https://github.com/harfbuzz/harfbuzz/pull/4228
 360   //
 361   // For performance characteristics see:
 362   // https://github.com/harfbuzz/harfbuzz/pull/4228#issuecomment-1565079537
 363   template <typename T,
 364             hb_enable_if (std::is_integral<T>::value && sizeof (T) <= sizeof (uint32_t))> constexpr auto
 365   impl (const T& v, hb_priority<1>) const HB_RETURN (uint32_t, (uint32_t) v * 2654435761u /* Knuh's multiplicative hash */)
 366   template <typename T,
 367             hb_enable_if (std::is_integral<T>::value && sizeof (T) > sizeof (uint32_t))> constexpr auto
 368   impl (const T& v, hb_priority<1>) const HB_RETURN (uint32_t, (uint32_t) (v ^ (v >> 32)) * 2654435761u /* Knuth's multiplicative hash */)
 369
 370   template <typename T,
 371             hb_enable_if (std::is_floating_point<T>::value)> constexpr auto
 372   impl (const T& v, hb_priority<1>) const HB_RETURN (uint32_t, fasthash32 (std::addressof (v), sizeof (T), 0xf437ffe6))
 373
 374   template <typename T> constexpr auto
 375   impl (const T& v, hb_priority<0>) const HB_RETURN (uint32_t, std::hash<hb_decay<decltype (hb_deref (v))>>{} (hb_deref (v)))
 376
 377   public:
 378
 379   template <typename T> constexpr auto
 380   operator () (const T& v) const HB_RETURN (uint32_t, impl (v, hb_prioritize))
 381 }
 382 HB_FUNCOBJ (hb_hash);
 383
 384
 385 struct
 386 {
 387   private:
 388
 389   /* Pointer-to-member-function. */
 390   template <typename Appl, typename T, typename ...Ts> auto
 391   impl (Appl&& a, hb_priority<2>, T &&v, Ts&&... ds) const HB_AUTO_RETURN
 392   ((hb_deref (std::forward<T> (v)).*std::forward<Appl> (a)) (std::forward<Ts> (ds)...))
 393
 394   /* Pointer-to-member. */
 395   template <typename Appl, typename T> auto
 396   impl (Appl&& a, hb_priority<1>, T &&v) const HB_AUTO_RETURN
 397   ((hb_deref (std::forward<T> (v))).*std::forward<Appl> (a))
 398
 399   /* Operator(). */
 400   template <typename Appl, typename ...Ts> auto
 401   impl (Appl&& a, hb_priority<0>, Ts&&... ds) const HB_AUTO_RETURN
 402   (hb_deref (std::forward<Appl> (a)) (std::forward<Ts> (ds)...))
 403
 404   public:
 405
 406   template <typename Appl, typename ...Ts> auto
 407   operator () (Appl&& a, Ts&&... ds) const HB_AUTO_RETURN
 408   (
 409     impl (std::forward<Appl> (a),
 410           hb_prioritize,
 411           std::forward<Ts> (ds)...)
 412   )
 413 }
 414 HB_FUNCOBJ (hb_invoke);
 415
 416 template <unsigned Pos, typename Appl, typename V>
 417 struct hb_partial_t
 418 {
 419   hb_partial_t (Appl a, V v) : a (a), v (v) {}
 420
 421   static_assert (Pos > 0, "");
 422
 423   template <typename ...Ts,
 424             unsigned P = Pos,
 425             hb_enable_if (P == 1)> auto
 426   operator () (Ts&& ...ds) -> decltype (hb_invoke (hb_declval (Appl),
 427                                                    hb_declval (V),
 428                                                    hb_declval (Ts)...))
 429   {
 430     return hb_invoke (std::forward<Appl> (a),
 431                       std::forward<V> (v),
 432                       std::forward<Ts> (ds)...);
 433   }
 434   template <typename T0, typename ...Ts,
 435             unsigned P = Pos,
 436             hb_enable_if (P == 2)> auto
 437   operator () (T0&& d0, Ts&& ...ds) -> decltype (hb_invoke (hb_declval (Appl),
 438                                                             hb_declval (T0),
 439                                                             hb_declval (V),
 440                                                             hb_declval (Ts)...))
 441   {
 442     return hb_invoke (std::forward<Appl> (a),
 443                       std::forward<T0> (d0),
 444                       std::forward<V> (v),
 445                       std::forward<Ts> (ds)...);
 446   }
 447
 448   private:
 449   hb_reference_wrapper<Appl> a;
 450   V v;
 451 };
 452 template <unsigned Pos=1, typename Appl, typename V>
 453 auto hb_partial (Appl&& a, V&& v) HB_AUTO_RETURN
 454 (( hb_partial_t<Pos, Appl, V> (a, v) ))
 455
 456 /* The following, HB_PARTIALIZE, macro uses a particular corner-case
 457  * of C++11 that is not particularly well-supported by all compilers.
 458  * What's happening is that it's using "this" in a trailing return-type
 459  * via decltype().  Broken compilers deduce the type of "this" pointer
 460  * in that context differently from what it resolves to in the body
 461  * of the function.
 462  *
 463  * One probable cause of this is that at the time of trailing return
 464  * type declaration, "this" points to an incomplete type, whereas in
 465  * the function body the type is complete.  That doesn't justify the
 466  * error in any way, but is probably what's happening.
 467  *
 468  * In the case of MSVC, we get around this by using C++14 "decltype(auto)"
 469  * which deduces the type from the actual return statement.  For gcc 4.8
 470  * we use "+this" instead of "this" which produces an rvalue that seems
 471  * to be deduced as the same type with this particular compiler, and seem
 472  * to be fine as default code path as well.
 473  */
 474 #ifdef _MSC_VER
 475 /* https://github.com/harfbuzz/harfbuzz/issues/1730 */ \
 476 #define HB_PARTIALIZE(Pos) \
 477   template <typename _T> \
 478   decltype(auto) operator () (_T&& _v) const \
 479   { return hb_partial<Pos> (this, std::forward<_T> (_v)); } \
 480   static_assert (true, "")
 481 #else
 482 /* https://github.com/harfbuzz/harfbuzz/issues/1724 */
 483 #define HB_PARTIALIZE(Pos) \
 484   template <typename _T> \
 485   auto operator () (_T&& _v) const HB_AUTO_RETURN \
 486   (hb_partial<Pos> (+this, std::forward<_T> (_v))) \
 487   static_assert (true, "")
 488 #endif
 489
 490
 491 struct
 492 {
 493   private:
 494
 495   template <typename Pred, typename Val> auto
 496   impl (Pred&& p, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
 497   (
 498     hb_deref (std::forward<Pred> (p)).has (std::forward<Val> (v))
 499   )
 500
 501   template <typename Pred, typename Val> auto
 502   impl (Pred&& p, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
 503   (
 504     hb_invoke (std::forward<Pred> (p),
 505                std::forward<Val> (v))
 506   )
 507
 508   public:
 509
 510   template <typename Pred, typename Val> auto
 511   operator () (Pred&& p, Val &&v) const HB_RETURN (bool,
 512     impl (std::forward<Pred> (p),
 513           std::forward<Val> (v),
 514           hb_prioritize)
 515   )
 516 }
 517 HB_FUNCOBJ (hb_has);
 518
 519 struct
 520 {
 521   private:
 522
 523   template <typename Pred, typename Val> auto
 524   impl (Pred&& p, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
 525   (
 526     hb_has (std::forward<Pred> (p),
 527             std::forward<Val> (v))
 528   )
 529
 530   template <typename Pred, typename Val> auto
 531   impl (Pred&& p, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
 532   (
 533     std::forward<Pred> (p) == std::forward<Val> (v)
 534   )
 535
 536   public:
 537
 538   template <typename Pred, typename Val> auto
 539   operator () (Pred&& p, Val &&v) const HB_RETURN (bool,
 540     impl (std::forward<Pred> (p),
 541           std::forward<Val> (v),
 542           hb_prioritize)
 543   )
 544 }
 545 HB_FUNCOBJ (hb_match);
 546
 547 struct
 548 {
 549   private:
 550
 551   template <typename Proj, typename Val> auto
 552   impl (Proj&& f, Val &&v, hb_priority<2>) const HB_AUTO_RETURN
 553   (
 554     hb_deref (std::forward<Proj> (f)).get (std::forward<Val> (v))
 555   )
 556
 557   template <typename Proj, typename Val> auto
 558   impl (Proj&& f, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
 559   (
 560     hb_invoke (std::forward<Proj> (f),
 561                std::forward<Val> (v))
 562   )
 563
 564   template <typename Proj, typename Val> auto
 565   impl (Proj&& f, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
 566   (
 567     std::forward<Proj> (f)[std::forward<Val> (v)]
 568   )
 569
 570   public:
 571
 572   template <typename Proj, typename Val> auto
 573   operator () (Proj&& f, Val &&v) const HB_AUTO_RETURN
 574   (
 575     impl (std::forward<Proj> (f),
 576           std::forward<Val> (v),
 577           hb_prioritize)
 578   )
 579 }
 580 HB_FUNCOBJ (hb_get);
 581
 582 struct
 583 {
 584   private:
 585
 586   template <typename T1, typename T2> auto
 587   impl (T1&& v1, T2 &&v2, hb_priority<3>) const HB_AUTO_RETURN
 588   (
 589     std::forward<T2> (v2).cmp (std::forward<T1> (v1)) == 0
 590   )
 591
 592   template <typename T1, typename T2> auto
 593   impl (T1&& v1, T2 &&v2, hb_priority<2>) const HB_AUTO_RETURN
 594   (
 595     std::forward<T1> (v1).cmp (std::forward<T2> (v2)) == 0
 596   )
 597
 598   template <typename T1, typename T2> auto
 599   impl (T1&& v1, T2 &&v2, hb_priority<1>) const HB_AUTO_RETURN
 600   (
 601     std::forward<T1> (v1) == std::forward<T2> (v2)
 602   )
 603
 604   template <typename T1, typename T2> auto
 605   impl (T1&& v1, T2 &&v2, hb_priority<0>) const HB_AUTO_RETURN
 606   (
 607     std::forward<T2> (v2) == std::forward<T1> (v1)
 608   )
 609
 610   public:
 611
 612   template <typename T1, typename T2> auto
 613   operator () (T1&& v1, T2 &&v2) const HB_AUTO_RETURN
 614   (
 615     impl (std::forward<T1> (v1),
 616           std::forward<T2> (v2),
 617           hb_prioritize)
 618   )
 619 }
 620 HB_FUNCOBJ (hb_equal);
 621
 622 struct
 623 {
 624   template <typename T> void
 625   operator () (T& a, T& b) const
 626   {
 627     using std::swap; // allow ADL
 628     swap (a, b);
 629   }
 630 }
 631 HB_FUNCOBJ (hb_swap);
 632
 633
 634 template <typename T1, typename T2>
 635 struct hb_pair_t
 636 {
 637   typedef T1 first_t;
 638   typedef T2 second_t;
 639   typedef hb_pair_t<T1, T2> pair_t;
 640
 641   template <typename U1 = T1, typename U2 = T2,
 642             hb_enable_if (std::is_default_constructible<U1>::value &&
 643                           std::is_default_constructible<U2>::value)>
 644   hb_pair_t () : first (), second () {}
 645   hb_pair_t (T1 a, T2 b) : first (std::forward<T1> (a)), second (std::forward<T2> (b)) {}
 646
 647   template <typename Q1, typename Q2,
 648             hb_enable_if (hb_is_convertible (T1, Q1) &&
 649                           hb_is_convertible (T2, Q2))>
 650   operator hb_pair_t<Q1, Q2> () { return hb_pair_t<Q1, Q2> (first, second); }
 651
 652   hb_pair_t<T1, T2> reverse () const
 653   { return hb_pair_t<T1, T2> (second, first); }
 654
 655   bool operator == (const pair_t& o) const { return first == o.first && second == o.second; }
 656   bool operator != (const pair_t& o) const { return !(*this == o); }
 657   bool operator < (const pair_t& o) const { return first < o.first || (first == o.first && second < o.second); }
 658   bool operator >= (const pair_t& o) const { return !(*this < o); }
 659   bool operator > (const pair_t& o) const { return first > o.first || (first == o.first && second > o.second); }
 660   bool operator <= (const pair_t& o) const { return !(*this > o); }
 661
 662   static int cmp (const void *pa, const void *pb)
 663   {
 664     pair_t *a = (pair_t *) pa;
 665     pair_t *b = (pair_t *) pb;
 666
 667     if (a->first < b->first) return -1;
 668     if (a->first > b->first) return +1;
 669     if (a->second < b->second) return -1;
 670     if (a->second > b->second) return +1;
 671     return 0;
 672   }
 673
 674   friend void swap (hb_pair_t& a, hb_pair_t& b)
 675   {
 676     hb_swap (a.first, b.first);
 677     hb_swap (a.second, b.second);
 678   }
 679
 680
 681   T1 first;
 682   T2 second;
 683 };
 684 template <typename T1, typename T2> static inline hb_pair_t<T1, T2>
 685 hb_pair (T1&& a, T2&& b) { return hb_pair_t<T1, T2> (a, b); }
 686
 687 typedef hb_pair_t<hb_codepoint_t, hb_codepoint_t> hb_codepoint_pair_t;
 688
 689 struct
 690 {
 691   template <typename Pair> constexpr typename Pair::first_t
 692   operator () (const Pair& pair) const { return pair.first; }
 693 }
 694 HB_FUNCOBJ (hb_first);
 695
 696 struct
 697 {
 698   template <typename Pair> constexpr typename Pair::second_t
 699   operator () (const Pair& pair) const { return pair.second; }
 700 }
 701 HB_FUNCOBJ (hb_second);
 702
 703 /* Note.  In min/max impl, we can use hb_type_identity<T> for second argument.
 704  * However, that would silently convert between different-signedness integers.
 705  * Instead we accept two different types, such that compiler can err if
 706  * comparing integers of different signedness. */
 707 struct
 708 {
 709   template <typename T, typename T2> constexpr auto
 710   operator () (T&& a, T2&& b) const HB_AUTO_RETURN
 711   (a <= b ? a : b)
 712 }
 713 HB_FUNCOBJ (hb_min);
 714 struct
 715 {
 716   template <typename T, typename T2> constexpr auto
 717   operator () (T&& a, T2&& b) const HB_AUTO_RETURN
 718   (a >= b ? a : b)
 719 }
 720 HB_FUNCOBJ (hb_max);
 721 struct
 722 {
 723   template <typename T, typename T2, typename T3> constexpr auto
 724   operator () (T&& x, T2&& min, T3&& max) const HB_AUTO_RETURN
 725   (hb_min (hb_max (std::forward<T> (x), std::forward<T2> (min)), std::forward<T3> (max)))
 726 }
 727 HB_FUNCOBJ (hb_clamp);
 728
 729 /*
 730  * Bithacks.
 731  */
 732
 733 /* Return the number of 1 bits in v. */
 734 template <typename T>
 735 static inline unsigned int
 736 hb_popcount (T v)
 737 {
 738 #if hb_has_builtin(__builtin_popcount)
 739   if (sizeof (T) <= sizeof (unsigned int))
 740     return __builtin_popcount (v);
 741 #endif
 742
 743 #if hb_has_builtin(__builtin_popcountl)
 744   if (sizeof (T) <= sizeof (unsigned long))
 745     return __builtin_popcountl (v);
 746 #endif
 747
 748 #if hb_has_builtin(__builtin_popcountll)
 749   if (sizeof (T) <= sizeof (unsigned long long))
 750     return __builtin_popcountll (v);
 751 #endif
 752
 753   if (sizeof (T) <= 4)
 754   {
 755     /* "HACKMEM 169" */
 756     uint32_t y;
 757     y = (v >> 1) &033333333333;
 758     y = v - y - ((y >>1) & 033333333333);
 759     return (((y + (y >> 3)) & 030707070707) % 077);
 760   }
 761
 762   if (sizeof (T) == 8)
 763   {
 764     uint64_t y = (uint64_t) v;
 765     y -= ((y >> 1) & 0x5555555555555555ull);
 766     y = (y & 0x3333333333333333ull) + (y >> 2 & 0x3333333333333333ull);
 767     return ((y + (y >> 4)) & 0xf0f0f0f0f0f0f0full) * 0x101010101010101ull >> 56;
 768   }
 769
 770   if (sizeof (T) == 16)
 771   {
 772     unsigned int shift = 64;
 773     return hb_popcount<uint64_t> ((uint64_t) v) + hb_popcount ((uint64_t) (v >> shift));
 774   }
 775
 776   assert (0);
 777   return 0; /* Shut up stupid compiler. */
 778 }
 779
 780 /* Returns the number of bits needed to store number */
 781 template <typename T>
 782 static inline unsigned int
 783 hb_bit_storage (T v)
 784 {
 785   if (unlikely (!v)) return 0;
 786
 787 #if hb_has_builtin(__builtin_clz)
 788   if (sizeof (T) <= sizeof (unsigned int))
 789     return sizeof (unsigned int) * 8 - __builtin_clz (v);
 790 #endif
 791
 792 #if hb_has_builtin(__builtin_clzl)
 793   if (sizeof (T) <= sizeof (unsigned long))
 794     return sizeof (unsigned long) * 8 - __builtin_clzl (v);
 795 #endif
 796
 797 #if hb_has_builtin(__builtin_clzll)
 798   if (sizeof (T) <= sizeof (unsigned long long))
 799     return sizeof (unsigned long long) * 8 - __builtin_clzll (v);
 800 #endif
 801
 802 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
 803   if (sizeof (T) <= sizeof (unsigned int))
 804   {
 805     unsigned long where;
 806     _BitScanReverse (&where, v);
 807     return 1 + where;
 808   }
 809 # if defined(_WIN64)
 810   if (sizeof (T) <= 8)
 811   {
 812     unsigned long where;
 813     _BitScanReverse64 (&where, v);
 814     return 1 + where;
 815   }
 816 # endif
 817 #endif
 818
 819   if (sizeof (T) <= 4)
 820   {
 821     /* "bithacks" */
 822     const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
 823     const unsigned int S[] = {1, 2, 4, 8, 16};
 824     unsigned int r = 0;
 825     for (int i = 4; i >= 0; i--)
 826       if (v & b[i])
 827       {
 828         v >>= S[i];
 829         r |= S[i];
 830       }
 831     return r + 1;
 832   }
 833   if (sizeof (T) <= 8)
 834   {
 835     /* "bithacks" */
 836     const uint64_t b[] = {0x2ULL, 0xCULL, 0xF0ULL, 0xFF00ULL, 0xFFFF0000ULL, 0xFFFFFFFF00000000ULL};
 837     const unsigned int S[] = {1, 2, 4, 8, 16, 32};
 838     unsigned int r = 0;
 839     for (int i = 5; i >= 0; i--)
 840       if (v & b[i])
 841       {
 842         v >>= S[i];
 843         r |= S[i];
 844       }
 845     return r + 1;
 846   }
 847   if (sizeof (T) == 16)
 848   {
 849     unsigned int shift = 64;
 850     return (v >> shift) ? hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift :
 851                           hb_bit_storage<uint64_t> ((uint64_t) v);
 852   }
 853
 854   assert (0);
 855   return 0; /* Shut up stupid compiler. */
 856 }
 857
 858 /* Returns the number of zero bits in the least significant side of v */
 859 template <typename T>
 860 static inline unsigned int
 861 hb_ctz (T v)
 862 {
 863   if (unlikely (!v)) return 8 * sizeof (T);
 864
 865 #if hb_has_builtin(__builtin_ctz)
 866   if (sizeof (T) <= sizeof (unsigned int))
 867     return __builtin_ctz (v);
 868 #endif
 869
 870 #if hb_has_builtin(__builtin_ctzl)
 871   if (sizeof (T) <= sizeof (unsigned long))
 872     return __builtin_ctzl (v);
 873 #endif
 874
 875 #if hb_has_builtin(__builtin_ctzll)
 876   if (sizeof (T) <= sizeof (unsigned long long))
 877     return __builtin_ctzll (v);
 878 #endif
 879
 880 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
 881   if (sizeof (T) <= sizeof (unsigned int))
 882   {
 883     unsigned long where;
 884     _BitScanForward (&where, v);
 885     return where;
 886   }
 887 # if defined(_WIN64)
 888   if (sizeof (T) <= 8)
 889   {
 890     unsigned long where;
 891     _BitScanForward64 (&where, v);
 892     return where;
 893   }
 894 # endif
 895 #endif
 896
 897   if (sizeof (T) <= 4)
 898   {
 899     /* "bithacks" */
 900     unsigned int c = 32;
 901     v &= - (int32_t) v;
 902     if (v) c--;
 903     if (v & 0x0000FFFF) c -= 16;
 904     if (v & 0x00FF00FF) c -= 8;
 905     if (v & 0x0F0F0F0F) c -= 4;
 906     if (v & 0x33333333) c -= 2;
 907     if (v & 0x55555555) c -= 1;
 908     return c;
 909   }
 910   if (sizeof (T) <= 8)
 911   {
 912     /* "bithacks" */
 913     unsigned int c = 64;
 914     v &= - (int64_t) (v);
 915     if (v) c--;
 916     if (v & 0x00000000FFFFFFFFULL) c -= 32;
 917     if (v & 0x0000FFFF0000FFFFULL) c -= 16;
 918     if (v & 0x00FF00FF00FF00FFULL) c -= 8;
 919     if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4;
 920     if (v & 0x3333333333333333ULL) c -= 2;
 921     if (v & 0x5555555555555555ULL) c -= 1;
 922     return c;
 923   }
 924   if (sizeof (T) == 16)
 925   {
 926     unsigned int shift = 64;
 927     return (uint64_t) v ? hb_bit_storage<uint64_t> ((uint64_t) v) :
 928                           hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift;
 929   }
 930
 931   assert (0);
 932   return 0; /* Shut up stupid compiler. */
 933 }
 934
 935
 936 /*
 937  * Tiny stuff.
 938  */
 939
 940 /* ASCII tag/character handling */
 941 static inline bool ISALPHA (unsigned char c)
 942 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); }
 943 static inline bool ISALNUM (unsigned char c)
 944 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); }
 945 static inline bool ISSPACE (unsigned char c)
 946 { return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; }
 947 static inline unsigned char TOUPPER (unsigned char c)
 948 { return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; }
 949 static inline unsigned char TOLOWER (unsigned char c)
 950 { return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; }
 951 static inline bool ISHEX (unsigned char c)
 952 { return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'); }
 953 static inline unsigned char TOHEX (uint8_t c)
 954 { return (c & 0xF) <= 9 ? (c & 0xF) + '0' : (c & 0xF) + 'a' - 10; }
 955 static inline uint8_t FROMHEX (unsigned char c)
 956 { return (c >= '0' && c <= '9') ? c - '0' : TOLOWER (c) - 'a' + 10; }
 957
 958 static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)
 959 { return (a + (b - 1)) / b; }
 960
 961
 962 #undef  ARRAY_LENGTH
 963 template <typename Type, unsigned int n>
 964 static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }
 965 /* A const version, but does not detect erratically being called on pointers. */
 966 #define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
 967
 968
 969 static inline void *
 970 hb_memcpy (void *__restrict dst, const void *__restrict src, size_t len)
 971 {
 972   /* It's illegal to pass 0 as size to memcpy. */
 973   if (unlikely (!len)) return dst;
 974   return memcpy (dst, src, len);
 975 }
 976
 977 static inline int
 978 hb_memcmp (const void *a, const void *b, unsigned int len)
 979 {
 980   /* It's illegal to pass NULL to memcmp(), even if len is zero.
 981    * So, wrap it.
 982    * https://sourceware.org/bugzilla/show_bug.cgi?id=23878 */
 983   if (unlikely (!len)) return 0;
 984   return memcmp (a, b, len);
 985 }
 986
 987 static inline void *
 988 hb_memset (void *s, int c, unsigned int n)
 989 {
 990   /* It's illegal to pass NULL to memset(), even if n is zero. */
 991   if (unlikely (!n)) return s;
 992   return memset (s, c, n);
 993 }
 994
 995 static inline unsigned int
 996 hb_ceil_to_4 (unsigned int v)
 997 {
 998   return ((v - 1) | 3) + 1;
 999 }
1000
1001 template <typename T> static inline bool
1002 hb_in_range (T u, T lo, T hi)
1003 {
1004   static_assert (!std::is_signed<T>::value, "");
1005
1006   /* The casts below are important as if T is smaller than int,
1007    * the subtract results will become a signed int! */
1008   return (T)(u - lo) <= (T)(hi - lo);
1009 }
1010 template <typename T> static inline bool
1011 hb_in_ranges (T u, T lo1, T hi1)
1012 {
1013   return hb_in_range (u, lo1, hi1);
1014 }
1015 template <typename T, typename ...Ts> static inline bool
1016 hb_in_ranges (T u, T lo1, T hi1, Ts... ds)
1017 {
1018   return hb_in_range<T> (u, lo1, hi1) || hb_in_ranges<T> (u, ds...);
1019 }
1020
1021
1022 /*
1023  * Overflow checking.
1024  */
1025
1026 static inline bool
1027 hb_unsigned_mul_overflows (unsigned int count, unsigned int size, unsigned *result = nullptr)
1028 {
1029 #if hb_has_builtin(__builtin_mul_overflow)
1030   unsigned stack_result;
1031   if (!result)
1032     result = &stack_result;
1033   return __builtin_mul_overflow (count, size, result);
1034 #endif
1035
1036   if (result)
1037     *result = count * size;
1038   return (size > 0) && (count >= ((unsigned int) -1) / size);
1039 }
1040
1041
1042 /*
1043  * Sort and search.
1044  */
1045
1046 template <typename K, typename V, typename ...Ts>
1047 static int
1048 _hb_cmp_method (const void *pkey, const void *pval, Ts... ds)
1049 {
1050   const K& key = * (const K*) pkey;
1051   const V& val = * (const V*) pval;
1052
1053   return val.cmp (key, ds...);
1054 }
1055
1056 template <typename V, typename K, typename ...Ts>
1057 static inline bool
1058 hb_bsearch_impl (unsigned *pos, /* Out */
1059                  const K& key,
1060                  V* base, size_t nmemb, size_t stride,
1061                  int (*compar)(const void *_key, const void *_item, Ts... _ds),
1062                  Ts... ds)
1063 {
1064   /* This is our *only* bsearch implementation. */
1065
1066   int min = 0, max = (int) nmemb - 1;
1067   while (min <= max)
1068   {
1069     int mid = ((unsigned int) min + (unsigned int) max) / 2;
1070 #pragma GCC diagnostic push
1071 #pragma GCC diagnostic ignored "-Wcast-align"
1072     V* p = (V*) (((const char *) base) + (mid * stride));
1073 #pragma GCC diagnostic pop
1074     int c = compar ((const void *) std::addressof (key), (const void *) p, ds...);
1075     if (c < 0)
1076       max = mid - 1;
1077     else if (c > 0)
1078       min = mid + 1;
1079     else
1080     {
1081       *pos = mid;
1082       return true;
1083     }
1084   }
1085   *pos = min;
1086   return false;
1087 }
1088
1089 template <typename V, typename K>
1090 static inline V*
1091 hb_bsearch (const K& key, V* base,
1092             size_t nmemb, size_t stride = sizeof (V),
1093             int (*compar)(const void *_key, const void *_item) = _hb_cmp_method<K, V>)
1094 {
1095   unsigned pos;
1096 #pragma GCC diagnostic push
1097 #pragma GCC diagnostic ignored "-Wcast-align"
1098   return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar) ?
1099          (V*) (((const char *) base) + (pos * stride)) : nullptr;
1100 #pragma GCC diagnostic pop
1101 }
1102 template <typename V, typename K, typename ...Ts>
1103 static inline V*
1104 hb_bsearch (const K& key, V* base,
1105             size_t nmemb, size_t stride,
1106             int (*compar)(const void *_key, const void *_item, Ts... _ds),
1107             Ts... ds)
1108 {
1109   unsigned pos;
1110 #pragma GCC diagnostic push
1111 #pragma GCC diagnostic ignored "-Wcast-align"
1112   return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar, ds...) ?
1113          (V*) (((const char *) base) + (pos * stride)) : nullptr;
1114 #pragma GCC diagnostic pop
1115 }
1116
1117
1118 /* From https://github.com/noporpoise/sort_r
1119    Feb 5, 2019 (c8c65c1e)
1120    Modified to support optional argument using templates */
1121
1122 /* Isaac Turner 29 April 2014 Public Domain */
1123
1124 /*
1125 hb_qsort function to be exported.
1126 Parameters:
1127   base is the array to be sorted
1128   nel is the number of elements in the array
1129   width is the size in bytes of each element of the array
1130   compar is the comparison function
1131   arg (optional) is a pointer to be passed to the comparison function
1132
1133 void hb_qsort(void *base, size_t nel, size_t width,
1134               int (*compar)(const void *_a, const void *_b, [void *_arg]),
1135               [void *arg]);
1136 */
1137
1138 #define SORT_R_SWAP(a,b,tmp) ((void) ((tmp) = (a)), (void) ((a) = (b)), (b) = (tmp))
1139
1140 /* swap a and b */
1141 /* a and b must not be equal! */
1142 static inline void sort_r_swap(char *__restrict a, char *__restrict b,
1143                                size_t w)
1144 {
1145   char tmp, *end = a+w;
1146   for(; a < end; a++, b++) { SORT_R_SWAP(*a, *b, tmp); }
1147 }
1148
1149 /* swap a, b iff a>b */
1150 /* a and b must not be equal! */
1151 /* __restrict is same as restrict but better support on old machines */
1152 template <typename ...Ts>
1153 static inline int sort_r_cmpswap(char *__restrict a,
1154                                  char *__restrict b, size_t w,
1155                                  int (*compar)(const void *_a,
1156                                                const void *_b,
1157                                                Ts... _ds),
1158                                  Ts... ds)
1159 {
1160   if(compar(a, b, ds...) > 0) {
1161     sort_r_swap(a, b, w);
1162     return 1;
1163   }
1164   return 0;
1165 }
1166
1167 /*
1168 Swap consecutive blocks of bytes of size na and nb starting at memory addr ptr,
1169 with the smallest swap so that the blocks are in the opposite order. Blocks may
1170 be internally re-ordered e.g.
1171   12345ab  ->   ab34512
1172   123abc   ->   abc123
1173   12abcde  ->   deabc12
1174 */
1175 static inline void sort_r_swap_blocks(char *ptr, size_t na, size_t nb)
1176 {
1177   if(na > 0 && nb > 0) {
1178     if(na > nb) { sort_r_swap(ptr, ptr+na, nb); }
1179     else { sort_r_swap(ptr, ptr+nb, na); }
1180   }
1181 }
1182
1183 /* Implement recursive quicksort ourselves */
1184 /* Note: quicksort is not stable, equivalent values may be swapped */
1185 template <typename ...Ts>
1186 static inline void sort_r_simple(void *base, size_t nel, size_t w,
1187                                  int (*compar)(const void *_a,
1188                                                const void *_b,
1189                                                Ts... _ds),
1190                                  Ts... ds)
1191 {
1192   char *b = (char *)base, *end = b + nel*w;
1193
1194   /* for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
1195   printf("\n"); */
1196
1197   if(nel < 10) {
1198     /* Insertion sort for arbitrarily small inputs */
1199     char *pi, *pj;
1200     for(pi = b+w; pi < end; pi += w) {
1201       for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,ds...); pj -= w) {}
1202     }
1203   }
1204   else
1205   {
1206     /* nel > 9; Quicksort */
1207
1208     int cmp;
1209     char *pl, *ple, *pr, *pre, *pivot;
1210     char *last = b+w*(nel-1), *tmp;
1211
1212     /*
1213     Use median of second, middle and second-last items as pivot.
1214     First and last may have been swapped with pivot and therefore be extreme
1215     */
1216     char *l[3];
1217     l[0] = b + w;
1218     l[1] = b+w*(nel/2);
1219     l[2] = last - w;
1220
1221     /* printf("pivots: %i, %i, %i\n", *(int*)l[0], *(int*)l[1], *(int*)l[2]); */
1222
1223     if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
1224     if(compar(l[1],l[2],ds...) > 0) {
1225       SORT_R_SWAP(l[1], l[2], tmp);
1226       if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
1227     }
1228
1229     /* swap mid value (l[1]), and last element to put pivot as last element */
1230     if(l[1] != last) { sort_r_swap(l[1], last, w); }
1231
1232     /*
1233     pl is the next item on the left to be compared to the pivot
1234     pr is the last item on the right that was compared to the pivot
1235     ple is the left position to put the next item that equals the pivot
1236     ple is the last right position where we put an item that equals the pivot
1237                                            v- end (beyond the array)
1238       EEEEEELLLLLLLLuuuuuuuuGGGGGGGEEEEEEEE.
1239       ^- b  ^- ple  ^- pl   ^- pr  ^- pre ^- last (where the pivot is)
1240     Pivot comparison key:
1241       E = equal, L = less than, u = unknown, G = greater than, E = equal
1242     */
1243     pivot = last;
1244     ple = pl = b;
1245     pre = pr = last;
1246
1247     /*
1248     Strategy:
1249     Loop into the list from the left and right at the same time to find:
1250     - an item on the left that is greater than the pivot
1251     - an item on the right that is less than the pivot
1252     Once found, they are swapped and the loop continues.
1253     Meanwhile items that are equal to the pivot are moved to the edges of the
1254     array.
1255     */
1256     while(pl < pr) {
1257       /* Move left hand items which are equal to the pivot to the far left.
1258          break when we find an item that is greater than the pivot */
1259       for(; pl < pr; pl += w) {
1260         cmp = compar(pl, pivot, ds...);
1261         if(cmp > 0) { break; }
1262         else if(cmp == 0) {
1263           if(ple < pl) { sort_r_swap(ple, pl, w); }
1264           ple += w;
1265         }
1266       }
1267       /* break if last batch of left hand items were equal to pivot */
1268       if(pl >= pr) { break; }
1269       /* Move right hand items which are equal to the pivot to the far right.
1270          break when we find an item that is less than the pivot */
1271       for(; pl < pr; ) {
1272         pr -= w; /* Move right pointer onto an unprocessed item */
1273         cmp = compar(pr, pivot, ds...);
1274         if(cmp == 0) {
1275           pre -= w;
1276           if(pr < pre) { sort_r_swap(pr, pre, w); }
1277         }
1278         else if(cmp < 0) {
1279           if(pl < pr) { sort_r_swap(pl, pr, w); }
1280           pl += w;
1281           break;
1282         }
1283       }
1284     }
1285
1286     pl = pr; /* pr may have gone below pl */
1287
1288     /*
1289     Now we need to go from: EEELLLGGGGEEEE
1290                         to: LLLEEEEEEEGGGG
1291     Pivot comparison key:
1292       E = equal, L = less than, u = unknown, G = greater than, E = equal
1293     */
1294     sort_r_swap_blocks(b, ple-b, pl-ple);
1295     sort_r_swap_blocks(pr, pre-pr, end-pre);
1296
1297     /*for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
1298     printf("\n");*/
1299
1300     sort_r_simple(b, (pl-ple)/w, w, compar, ds...);
1301     sort_r_simple(end-(pre-pr), (pre-pr)/w, w, compar, ds...);
1302   }
1303 }
1304
1305 static inline void
1306 hb_qsort (void *base, size_t nel, size_t width,
1307           int (*compar)(const void *_a, const void *_b))
1308 {
1309 #if defined(__OPTIMIZE_SIZE__) && !defined(HB_USE_INTERNAL_QSORT)
1310   qsort (base, nel, width, compar);
1311 #else
1312   sort_r_simple (base, nel, width, compar);
1313 #endif
1314 }
1315
1316 static inline void
1317 hb_qsort (void *base, size_t nel, size_t width,
1318           int (*compar)(const void *_a, const void *_b, void *_arg),
1319           void *arg)
1320 {
1321 #ifdef HAVE_GNU_QSORT_R
1322   qsort_r (base, nel, width, compar, arg);
1323 #else
1324   sort_r_simple (base, nel, width, compar, arg);
1325 #endif
1326 }
1327
1328
1329 template <typename T, typename T2, typename T3 = int> static inline void
1330 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T2 *, const T2 *), T3 *array2 = nullptr)
1331 {
1332   static_assert (hb_is_trivially_copy_assignable (T), "");
1333   static_assert (hb_is_trivially_copy_assignable (T3), "");
1334
1335   for (unsigned int i = 1; i < len; i++)
1336   {
1337     unsigned int j = i;
1338     while (j && compar (&array[j - 1], &array[i]) > 0)
1339       j--;
1340     if (i == j)
1341       continue;
1342     /* Move item i to occupy place for item j, shift what's in between. */
1343     {
1344       T t = array[i];
1345       memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
1346       array[j] = t;
1347     }
1348     if (array2)
1349     {
1350       T3 t = array2[i];
1351       memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T3));
1352       array2[j] = t;
1353     }
1354   }
1355 }
1356
1357 static inline hb_bool_t
1358 hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out)
1359 {
1360   unsigned int v;
1361   const char *p = s;
1362   const char *end = p + len;
1363   if (unlikely (!hb_parse_uint (&p, end, &v, true/* whole buffer */, base)))
1364     return false;
1365
1366   *out = v;
1367   return true;
1368 }
1369
1370
1371 /* Operators. */
1372
1373 struct
1374 { HB_PARTIALIZE(2);
1375   template <typename T> constexpr auto
1376   operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & b)
1377 }
1378 HB_FUNCOBJ (hb_bitwise_and);
1379 struct
1380 { HB_PARTIALIZE(2);
1381   template <typename T> constexpr auto
1382   operator () (const T &a, const T &b) const HB_AUTO_RETURN (a | b)
1383 }
1384 HB_FUNCOBJ (hb_bitwise_or);
1385 struct
1386 { HB_PARTIALIZE(2);
1387   template <typename T> constexpr auto
1388   operator () (const T &a, const T &b) const HB_AUTO_RETURN (a ^ b)
1389 }
1390 HB_FUNCOBJ (hb_bitwise_xor);
1391 struct
1392 { HB_PARTIALIZE(2);
1393   template <typename T> constexpr auto
1394   operator () (const T &a, const T &b) const HB_AUTO_RETURN (~a & b)
1395 }
1396 HB_FUNCOBJ (hb_bitwise_lt);
1397 struct
1398 { HB_PARTIALIZE(2);
1399   template <typename T> constexpr auto
1400   operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & ~b)
1401 }
1402 HB_FUNCOBJ (hb_bitwise_gt); // aka sub
1403 struct
1404 { HB_PARTIALIZE(2);
1405   template <typename T> constexpr auto
1406   operator () (const T &a, const T &b) const HB_AUTO_RETURN (~a | b)
1407 }
1408 HB_FUNCOBJ (hb_bitwise_le);
1409 struct
1410 { HB_PARTIALIZE(2);
1411   template <typename T> constexpr auto
1412   operator () (const T &a, const T &b) const HB_AUTO_RETURN (a | ~b)
1413 }
1414 HB_FUNCOBJ (hb_bitwise_ge);
1415 struct
1416 {
1417   template <typename T> constexpr auto
1418   operator () (const T &a) const HB_AUTO_RETURN (~a)
1419 }
1420 HB_FUNCOBJ (hb_bitwise_neg);
1421
1422 struct
1423 { HB_PARTIALIZE(2);
1424   template <typename T, typename T2> constexpr auto
1425   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a + b)
1426 }
1427 HB_FUNCOBJ (hb_add);
1428 struct
1429 { HB_PARTIALIZE(2);
1430   template <typename T, typename T2> constexpr auto
1431   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a - b)
1432 }
1433 HB_FUNCOBJ (hb_sub);
1434 struct
1435 { HB_PARTIALIZE(2);
1436   template <typename T, typename T2> constexpr auto
1437   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (b - a)
1438 }
1439 HB_FUNCOBJ (hb_rsub);
1440 struct
1441 { HB_PARTIALIZE(2);
1442   template <typename T, typename T2> constexpr auto
1443   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a * b)
1444 }
1445 HB_FUNCOBJ (hb_mul);
1446 struct
1447 { HB_PARTIALIZE(2);
1448   template <typename T, typename T2> constexpr auto
1449   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a / b)
1450 }
1451 HB_FUNCOBJ (hb_div);
1452 struct
1453 { HB_PARTIALIZE(2);
1454   template <typename T, typename T2> constexpr auto
1455   operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a % b)
1456 }
1457 HB_FUNCOBJ (hb_mod);
1458 struct
1459 {
1460   template <typename T> constexpr auto
1461   operator () (const T &a) const HB_AUTO_RETURN (+a)
1462 }
1463 HB_FUNCOBJ (hb_pos);
1464 struct
1465 {
1466   template <typename T> constexpr auto
1467   operator () (const T &a) const HB_AUTO_RETURN (-a)
1468 }
1469 HB_FUNCOBJ (hb_neg);
1470 struct
1471 {
1472   template <typename T> constexpr auto
1473   operator () (T &a) const HB_AUTO_RETURN (++a)
1474 }
1475 HB_FUNCOBJ (hb_inc);
1476 struct
1477 {
1478   template <typename T> constexpr auto
1479   operator () (T &a) const HB_AUTO_RETURN (--a)
1480 }
1481 HB_FUNCOBJ (hb_dec);
1482
1483
1484 /* Adapted from kurbo implementation with extra parameters added,
1485  * and finding for a particular range instead of 0.
1486  *
1487  * For documentation and implementation see:
1488  *
1489  * [ITP method]: https://en.wikipedia.org/wiki/ITP_Method
1490  * [An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality]: https://dl.acm.org/doi/10.1145/3423597
1491  * https://docs.rs/kurbo/0.8.1/kurbo/common/fn.solve_itp.html
1492  * https://github.com/linebender/kurbo/blob/fd839c25ea0c98576c7ce5789305822675a89938/src/common.rs#L162-L248
1493  */
1494 template <typename func_t>
1495 double solve_itp (func_t f,
1496                   double a, double b,
1497                   double epsilon,
1498                   double min_y, double max_y,
1499                   double &ya, double &yb, double &y)
1500 {
1501   unsigned n1_2 = (unsigned) (hb_max (ceil (log2 ((b - a) / epsilon)) - 1.0, 0.0));
1502   const unsigned n0 = 1; // Hardwired
1503   const double k1 = 0.2 / (b - a); // Hardwired.
1504   unsigned nmax = n0 + n1_2;
1505   double scaled_epsilon = epsilon * double (1llu << nmax);
1506   double _2_epsilon = 2.0 * epsilon;
1507   while (b - a > _2_epsilon)
1508   {
1509     double x1_2 = 0.5 * (a + b);
1510     double r = scaled_epsilon - 0.5 * (b - a);
1511     double xf = (yb * a - ya * b) / (yb - ya);
1512     double sigma = x1_2 - xf;
1513     double b_a = b - a;
1514     // This has k2 = 2 hardwired for efficiency.
1515     double b_a_k2 = b_a * b_a;
1516     double delta = k1 * b_a_k2;
1517     int sigma_sign = sigma >= 0 ? +1 : -1;
1518     double xt = delta <= fabs (x1_2 - xf) ? xf + delta * sigma_sign : x1_2;
1519     double xitp = fabs (xt - x1_2) <= r ? xt : x1_2 - r * sigma_sign;
1520     double yitp = f (xitp);
1521     if (yitp > max_y)
1522     {
1523       b = xitp;
1524       yb = yitp;
1525     }
1526     else if (yitp < min_y)
1527     {
1528       a = xitp;
1529       ya = yitp;
1530     }
1531     else
1532     {
1533       y = yitp;
1534       return xitp;
1535     }
1536     scaled_epsilon *= 0.5;
1537   }
1538   return 0.5 * (a + b);
1539 }
1540
1541
1542 #endif /* HB_ALGS_HH */