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

source code of flutter_engine/third_party/harfbuzz/src/hb-algs.hh