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 >> 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
103template <typename Type, int Bytes = sizeof (Type)>
104struct BEInt;
105template <typename Type>
106struct 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};
114template <typename Type>
115struct 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};
148template <typename Type>
149struct 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};
163template <typename Type>
164struct 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. */
205static 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
224struct
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}
230HB_FUNCOBJ (hb_identity);
231struct
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}
240HB_FUNCOBJ (hb_lidentity);
241struct
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}
247HB_FUNCOBJ (hb_ridentity);
248
249struct
250{
251 template <typename T> constexpr bool
252 operator () (T&& v) const { return bool (std::forward<T> (v)); }
253}
254HB_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
290static 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
342static 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
351struct
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> constexpr auto
371 impl (const T& v, hb_priority<0>) const HB_RETURN (uint32_t, std::hash<hb_decay<decltype (hb_deref (v))>>{} (hb_deref (v)))
372
373 public:
374
375 template <typename T> constexpr auto
376 operator () (const T& v) const HB_RETURN (uint32_t, impl (v, hb_prioritize))
377}
378HB_FUNCOBJ (hb_hash);
379
380
381struct
382{
383 private:
384
385 /* Pointer-to-member-function. */
386 template <typename Appl, typename T, typename ...Ts> auto
387 impl (Appl&& a, hb_priority<2>, T &&v, Ts&&... ds) const HB_AUTO_RETURN
388 ((hb_deref (std::forward<T> (v)).*std::forward<Appl> (a)) (std::forward<Ts> (ds)...))
389
390 /* Pointer-to-member. */
391 template <typename Appl, typename T> auto
392 impl (Appl&& a, hb_priority<1>, T &&v) const HB_AUTO_RETURN
393 ((hb_deref (std::forward<T> (v))).*std::forward<Appl> (a))
394
395 /* Operator(). */
396 template <typename Appl, typename ...Ts> auto
397 impl (Appl&& a, hb_priority<0>, Ts&&... ds) const HB_AUTO_RETURN
398 (hb_deref (std::forward<Appl> (a)) (std::forward<Ts> (ds)...))
399
400 public:
401
402 template <typename Appl, typename ...Ts> auto
403 operator () (Appl&& a, Ts&&... ds) const HB_AUTO_RETURN
404 (
405 impl (std::forward<Appl> (a),
406 hb_prioritize,
407 std::forward<Ts> (ds)...)
408 )
409}
410HB_FUNCOBJ (hb_invoke);
411
412template <unsigned Pos, typename Appl, typename V>
413struct hb_partial_t
414{
415 hb_partial_t (Appl a, V v) : a (a), v (v) {}
416
417 static_assert (Pos > 0, "");
418
419 template <typename ...Ts,
420 unsigned P = Pos,
421 hb_enable_if (P == 1)> auto
422 operator () (Ts&& ...ds) -> decltype (hb_invoke (hb_declval (Appl),
423 hb_declval (V),
424 hb_declval (Ts)...))
425 {
426 return hb_invoke (std::forward<Appl> (a),
427 std::forward<V> (v),
428 std::forward<Ts> (ds)...);
429 }
430 template <typename T0, typename ...Ts,
431 unsigned P = Pos,
432 hb_enable_if (P == 2)> auto
433 operator () (T0&& d0, Ts&& ...ds) -> decltype (hb_invoke (hb_declval (Appl),
434 hb_declval (T0),
435 hb_declval (V),
436 hb_declval (Ts)...))
437 {
438 return hb_invoke (std::forward<Appl> (a),
439 std::forward<T0> (d0),
440 std::forward<V> (v),
441 std::forward<Ts> (ds)...);
442 }
443
444 private:
445 hb_reference_wrapper<Appl> a;
446 V v;
447};
448template <unsigned Pos=1, typename Appl, typename V>
449auto hb_partial (Appl&& a, V&& v) HB_AUTO_RETURN
450(( hb_partial_t<Pos, Appl, V> (a, v) ))
451
452/* The following, HB_PARTIALIZE, macro uses a particular corner-case
453 * of C++11 that is not particularly well-supported by all compilers.
454 * What's happening is that it's using "this" in a trailing return-type
455 * via decltype(). Broken compilers deduce the type of "this" pointer
456 * in that context differently from what it resolves to in the body
457 * of the function.
458 *
459 * One probable cause of this is that at the time of trailing return
460 * type declaration, "this" points to an incomplete type, whereas in
461 * the function body the type is complete. That doesn't justify the
462 * error in any way, but is probably what's happening.
463 *
464 * In the case of MSVC, we get around this by using C++14 "decltype(auto)"
465 * which deduces the type from the actual return statement. For gcc 4.8
466 * we use "+this" instead of "this" which produces an rvalue that seems
467 * to be deduced as the same type with this particular compiler, and seem
468 * to be fine as default code path as well.
469 */
470#ifdef _MSC_VER
471/* https://github.com/harfbuzz/harfbuzz/issues/1730 */ \
472#define HB_PARTIALIZE(Pos) \
473 template <typename _T> \
474 decltype(auto) operator () (_T&& _v) const \
475 { return hb_partial<Pos> (this, std::forward<_T> (_v)); } \
476 static_assert (true, "")
477#else
478/* https://github.com/harfbuzz/harfbuzz/issues/1724 */
479#define HB_PARTIALIZE(Pos) \
480 template <typename _T> \
481 auto operator () (_T&& _v) const HB_AUTO_RETURN \
482 (hb_partial<Pos> (+this, std::forward<_T> (_v))) \
483 static_assert (true, "")
484#endif
485
486
487struct
488{
489 private:
490
491 template <typename Pred, typename Val> auto
492 impl (Pred&& p, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
493 (
494 hb_deref (std::forward<Pred> (p)).has (std::forward<Val> (v))
495 )
496
497 template <typename Pred, typename Val> auto
498 impl (Pred&& p, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
499 (
500 hb_invoke (std::forward<Pred> (p),
501 std::forward<Val> (v))
502 )
503
504 public:
505
506 template <typename Pred, typename Val> auto
507 operator () (Pred&& p, Val &&v) const HB_RETURN (bool,
508 impl (std::forward<Pred> (p),
509 std::forward<Val> (v),
510 hb_prioritize)
511 )
512}
513HB_FUNCOBJ (hb_has);
514
515struct
516{
517 private:
518
519 template <typename Pred, typename Val> auto
520 impl (Pred&& p, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
521 (
522 hb_has (std::forward<Pred> (p),
523 std::forward<Val> (v))
524 )
525
526 template <typename Pred, typename Val> auto
527 impl (Pred&& p, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
528 (
529 std::forward<Pred> (p) == std::forward<Val> (v)
530 )
531
532 public:
533
534 template <typename Pred, typename Val> auto
535 operator () (Pred&& p, Val &&v) const HB_RETURN (bool,
536 impl (std::forward<Pred> (p),
537 std::forward<Val> (v),
538 hb_prioritize)
539 )
540}
541HB_FUNCOBJ (hb_match);
542
543struct
544{
545 private:
546
547 template <typename Proj, typename Val> auto
548 impl (Proj&& f, Val &&v, hb_priority<2>) const HB_AUTO_RETURN
549 (
550 hb_deref (std::forward<Proj> (f)).get (std::forward<Val> (v))
551 )
552
553 template <typename Proj, typename Val> auto
554 impl (Proj&& f, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
555 (
556 hb_invoke (std::forward<Proj> (f),
557 std::forward<Val> (v))
558 )
559
560 template <typename Proj, typename Val> auto
561 impl (Proj&& f, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
562 (
563 std::forward<Proj> (f)[std::forward<Val> (v)]
564 )
565
566 public:
567
568 template <typename Proj, typename Val> auto
569 operator () (Proj&& f, Val &&v) const HB_AUTO_RETURN
570 (
571 impl (std::forward<Proj> (f),
572 std::forward<Val> (v),
573 hb_prioritize)
574 )
575}
576HB_FUNCOBJ (hb_get);
577
578struct
579{
580 private:
581
582 template <typename T1, typename T2> auto
583 impl (T1&& v1, T2 &&v2, hb_priority<3>) const HB_AUTO_RETURN
584 (
585 std::forward<T2> (v2).cmp (std::forward<T1> (v1)) == 0
586 )
587
588 template <typename T1, typename T2> auto
589 impl (T1&& v1, T2 &&v2, hb_priority<2>) const HB_AUTO_RETURN
590 (
591 std::forward<T1> (v1).cmp (std::forward<T2> (v2)) == 0
592 )
593
594 template <typename T1, typename T2> auto
595 impl (T1&& v1, T2 &&v2, hb_priority<1>) const HB_AUTO_RETURN
596 (
597 std::forward<T1> (v1) == std::forward<T2> (v2)
598 )
599
600 template <typename T1, typename T2> auto
601 impl (T1&& v1, T2 &&v2, hb_priority<0>) const HB_AUTO_RETURN
602 (
603 std::forward<T2> (v2) == std::forward<T1> (v1)
604 )
605
606 public:
607
608 template <typename T1, typename T2> auto
609 operator () (T1&& v1, T2 &&v2) const HB_AUTO_RETURN
610 (
611 impl (std::forward<T1> (v1),
612 std::forward<T2> (v2),
613 hb_prioritize)
614 )
615}
616HB_FUNCOBJ (hb_equal);
617
618struct
619{
620 template <typename T> void
621 operator () (T& a, T& b) const
622 {
623 using std::swap; // allow ADL
624 swap (a, b);
625 }
626}
627HB_FUNCOBJ (hb_swap);
628
629
630template <typename T1, typename T2>
631struct hb_pair_t
632{
633 typedef T1 first_t;
634 typedef T2 second_t;
635 typedef hb_pair_t<T1, T2> pair_t;
636
637 template <typename U1 = T1, typename U2 = T2,
638 hb_enable_if (std::is_default_constructible<U1>::value &&
639 std::is_default_constructible<U2>::value)>
640 hb_pair_t () : first (), second () {}
641 hb_pair_t (T1 a, T2 b) : first (std::forward<T1> (a)), second (std::forward<T2> (b)) {}
642
643 template <typename Q1, typename Q2,
644 hb_enable_if (hb_is_convertible (T1, Q1) &&
645 hb_is_convertible (T2, Q2))>
646 operator hb_pair_t<Q1, Q2> () { return hb_pair_t<Q1, Q2> (first, second); }
647
648 hb_pair_t<T1, T2> reverse () const
649 { return hb_pair_t<T1, T2> (second, first); }
650
651 bool operator == (const pair_t& o) const { return first == o.first && second == o.second; }
652 bool operator != (const pair_t& o) const { return !(*this == o); }
653 bool operator < (const pair_t& o) const { return first < o.first || (first == o.first && second < o.second); }
654 bool operator >= (const pair_t& o) const { return !(*this < o); }
655 bool operator > (const pair_t& o) const { return first > o.first || (first == o.first && second > o.second); }
656 bool operator <= (const pair_t& o) const { return !(*this > o); }
657
658 static int cmp (const void *pa, const void *pb)
659 {
660 pair_t *a = (pair_t *) pa;
661 pair_t *b = (pair_t *) pb;
662
663 if (a->first < b->first) return -1;
664 if (a->first > b->first) return +1;
665 if (a->second < b->second) return -1;
666 if (a->second > b->second) return +1;
667 return 0;
668 }
669
670 friend void swap (hb_pair_t& a, hb_pair_t& b)
671 {
672 hb_swap (a.first, b.first);
673 hb_swap (a.second, b.second);
674 }
675
676
677 T1 first;
678 T2 second;
679};
680template <typename T1, typename T2> static inline hb_pair_t<T1, T2>
681hb_pair (T1&& a, T2&& b) { return hb_pair_t<T1, T2> (a, b); }
682
683typedef hb_pair_t<hb_codepoint_t, hb_codepoint_t> hb_codepoint_pair_t;
684
685struct
686{
687 template <typename Pair> constexpr typename Pair::first_t
688 operator () (const Pair& pair) const { return pair.first; }
689}
690HB_FUNCOBJ (hb_first);
691
692struct
693{
694 template <typename Pair> constexpr typename Pair::second_t
695 operator () (const Pair& pair) const { return pair.second; }
696}
697HB_FUNCOBJ (hb_second);
698
699/* Note. In min/max impl, we can use hb_type_identity<T> for second argument.
700 * However, that would silently convert between different-signedness integers.
701 * Instead we accept two different types, such that compiler can err if
702 * comparing integers of different signedness. */
703struct
704{
705 template <typename T, typename T2> constexpr auto
706 operator () (T&& a, T2&& b) const HB_AUTO_RETURN
707 (a <= b ? a : b)
708}
709HB_FUNCOBJ (hb_min);
710struct
711{
712 template <typename T, typename T2> constexpr auto
713 operator () (T&& a, T2&& b) const HB_AUTO_RETURN
714 (a >= b ? a : b)
715}
716HB_FUNCOBJ (hb_max);
717struct
718{
719 template <typename T, typename T2, typename T3> constexpr auto
720 operator () (T&& x, T2&& min, T3&& max) const HB_AUTO_RETURN
721 (hb_min (hb_max (std::forward<T> (x), std::forward<T2> (min)), std::forward<T3> (max)))
722}
723HB_FUNCOBJ (hb_clamp);
724
725/*
726 * Bithacks.
727 */
728
729/* Return the number of 1 bits in v. */
730template <typename T>
731static inline unsigned int
732hb_popcount (T v)
733{
734#if hb_has_builtin(__builtin_popcount)
735 if (sizeof (T) <= sizeof (unsigned int))
736 return __builtin_popcount (v);
737#endif
738
739#if hb_has_builtin(__builtin_popcountl)
740 if (sizeof (T) <= sizeof (unsigned long))
741 return __builtin_popcountl (v);
742#endif
743
744#if hb_has_builtin(__builtin_popcountll)
745 if (sizeof (T) <= sizeof (unsigned long long))
746 return __builtin_popcountll (v);
747#endif
748
749 if (sizeof (T) <= 4)
750 {
751 /* "HACKMEM 169" */
752 uint32_t y;
753 y = (v >> 1) &033333333333;
754 y = v - y - ((y >>1) & 033333333333);
755 return (((y + (y >> 3)) & 030707070707) % 077);
756 }
757
758 if (sizeof (T) == 8)
759 {
760 uint64_t y = (uint64_t) v;
761 y -= ((y >> 1) & 0x5555555555555555ull);
762 y = (y & 0x3333333333333333ull) + (y >> 2 & 0x3333333333333333ull);
763 return ((y + (y >> 4)) & 0xf0f0f0f0f0f0f0full) * 0x101010101010101ull >> 56;
764 }
765
766 if (sizeof (T) == 16)
767 {
768 unsigned int shift = 64;
769 return hb_popcount<uint64_t> ((uint64_t) v) + hb_popcount ((uint64_t) (v >> shift));
770 }
771
772 assert (0);
773 return 0; /* Shut up stupid compiler. */
774}
775
776/* Returns the number of bits needed to store number */
777template <typename T>
778static inline unsigned int
779hb_bit_storage (T v)
780{
781 if (unlikely (!v)) return 0;
782
783#if hb_has_builtin(__builtin_clz)
784 if (sizeof (T) <= sizeof (unsigned int))
785 return sizeof (unsigned int) * 8 - __builtin_clz (v);
786#endif
787
788#if hb_has_builtin(__builtin_clzl)
789 if (sizeof (T) <= sizeof (unsigned long))
790 return sizeof (unsigned long) * 8 - __builtin_clzl (v);
791#endif
792
793#if hb_has_builtin(__builtin_clzll)
794 if (sizeof (T) <= sizeof (unsigned long long))
795 return sizeof (unsigned long long) * 8 - __builtin_clzll (v);
796#endif
797
798#if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
799 if (sizeof (T) <= sizeof (unsigned int))
800 {
801 unsigned long where;
802 _BitScanReverse (&where, v);
803 return 1 + where;
804 }
805# if defined(_WIN64)
806 if (sizeof (T) <= 8)
807 {
808 unsigned long where;
809 _BitScanReverse64 (&where, v);
810 return 1 + where;
811 }
812# endif
813#endif
814
815 if (sizeof (T) <= 4)
816 {
817 /* "bithacks" */
818 const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
819 const unsigned int S[] = {1, 2, 4, 8, 16};
820 unsigned int r = 0;
821 for (int i = 4; i >= 0; i--)
822 if (v & b[i])
823 {
824 v >>= S[i];
825 r |= S[i];
826 }
827 return r + 1;
828 }
829 if (sizeof (T) <= 8)
830 {
831 /* "bithacks" */
832 const uint64_t b[] = {0x2ULL, 0xCULL, 0xF0ULL, 0xFF00ULL, 0xFFFF0000ULL, 0xFFFFFFFF00000000ULL};
833 const unsigned int S[] = {1, 2, 4, 8, 16, 32};
834 unsigned int r = 0;
835 for (int i = 5; i >= 0; i--)
836 if (v & b[i])
837 {
838 v >>= S[i];
839 r |= S[i];
840 }
841 return r + 1;
842 }
843 if (sizeof (T) == 16)
844 {
845 unsigned int shift = 64;
846 return (v >> shift) ? hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift :
847 hb_bit_storage<uint64_t> ((uint64_t) v);
848 }
849
850 assert (0);
851 return 0; /* Shut up stupid compiler. */
852}
853
854/* Returns the number of zero bits in the least significant side of v */
855template <typename T>
856static inline unsigned int
857hb_ctz (T v)
858{
859 if (unlikely (!v)) return 8 * sizeof (T);
860
861#if hb_has_builtin(__builtin_ctz)
862 if (sizeof (T) <= sizeof (unsigned int))
863 return __builtin_ctz (v);
864#endif
865
866#if hb_has_builtin(__builtin_ctzl)
867 if (sizeof (T) <= sizeof (unsigned long))
868 return __builtin_ctzl (v);
869#endif
870
871#if hb_has_builtin(__builtin_ctzll)
872 if (sizeof (T) <= sizeof (unsigned long long))
873 return __builtin_ctzll (v);
874#endif
875
876#if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
877 if (sizeof (T) <= sizeof (unsigned int))
878 {
879 unsigned long where;
880 _BitScanForward (&where, v);
881 return where;
882 }
883# if defined(_WIN64)
884 if (sizeof (T) <= 8)
885 {
886 unsigned long where;
887 _BitScanForward64 (&where, v);
888 return where;
889 }
890# endif
891#endif
892
893 if (sizeof (T) <= 4)
894 {
895 /* "bithacks" */
896 unsigned int c = 32;
897 v &= - (int32_t) v;
898 if (v) c--;
899 if (v & 0x0000FFFF) c -= 16;
900 if (v & 0x00FF00FF) c -= 8;
901 if (v & 0x0F0F0F0F) c -= 4;
902 if (v & 0x33333333) c -= 2;
903 if (v & 0x55555555) c -= 1;
904 return c;
905 }
906 if (sizeof (T) <= 8)
907 {
908 /* "bithacks" */
909 unsigned int c = 64;
910 v &= - (int64_t) (v);
911 if (v) c--;
912 if (v & 0x00000000FFFFFFFFULL) c -= 32;
913 if (v & 0x0000FFFF0000FFFFULL) c -= 16;
914 if (v & 0x00FF00FF00FF00FFULL) c -= 8;
915 if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4;
916 if (v & 0x3333333333333333ULL) c -= 2;
917 if (v & 0x5555555555555555ULL) c -= 1;
918 return c;
919 }
920 if (sizeof (T) == 16)
921 {
922 unsigned int shift = 64;
923 return (uint64_t) v ? hb_bit_storage<uint64_t> ((uint64_t) v) :
924 hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift;
925 }
926
927 assert (0);
928 return 0; /* Shut up stupid compiler. */
929}
930
931
932/*
933 * Tiny stuff.
934 */
935
936/* ASCII tag/character handling */
937static inline bool ISALPHA (unsigned char c)
938{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); }
939static inline bool ISALNUM (unsigned char c)
940{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); }
941static inline bool ISSPACE (unsigned char c)
942{ return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; }
943static inline unsigned char TOUPPER (unsigned char c)
944{ return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; }
945static inline unsigned char TOLOWER (unsigned char c)
946{ return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; }
947static inline bool ISHEX (unsigned char c)
948{ return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'); }
949static inline unsigned char TOHEX (uint8_t c)
950{ return (c & 0xF) <= 9 ? (c & 0xF) + '0' : (c & 0xF) + 'a' - 10; }
951static inline uint8_t FROMHEX (unsigned char c)
952{ return (c >= '0' && c <= '9') ? c - '0' : TOLOWER (c) - 'a' + 10; }
953
954static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)
955{ return (a + (b - 1)) / b; }
956
957
958#undef ARRAY_LENGTH
959template <typename Type, unsigned int n>
960static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }
961/* A const version, but does not detect erratically being called on pointers. */
962#define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
963
964
965static inline void *
966hb_memcpy (void *__restrict dst, const void *__restrict src, size_t len)
967{
968 /* It's illegal to pass 0 as size to memcpy. */
969 if (unlikely (!len)) return dst;
970 return memcpy (dst, src, len);
971}
972
973static inline int
974hb_memcmp (const void *a, const void *b, unsigned int len)
975{
976 /* It's illegal to pass NULL to memcmp(), even if len is zero.
977 * So, wrap it.
978 * https://sourceware.org/bugzilla/show_bug.cgi?id=23878 */
979 if (unlikely (!len)) return 0;
980 return memcmp (a, b, len);
981}
982
983static inline void *
984hb_memset (void *s, int c, unsigned int n)
985{
986 /* It's illegal to pass NULL to memset(), even if n is zero. */
987 if (unlikely (!n)) return s;
988 return memset (s, c, n);
989}
990
991static inline unsigned int
992hb_ceil_to_4 (unsigned int v)
993{
994 return ((v - 1) | 3) + 1;
995}
996
997template <typename T> static inline bool
998hb_in_range (T u, T lo, T hi)
999{
1000 static_assert (!std::is_signed<T>::value, "");
1001
1002 /* The casts below are important as if T is smaller than int,
1003 * the subtract results will become a signed int! */
1004 return (T)(u - lo) <= (T)(hi - lo);
1005}
1006template <typename T> static inline bool
1007hb_in_ranges (T u, T lo1, T hi1)
1008{
1009 return hb_in_range (u, lo1, hi1);
1010}
1011template <typename T, typename ...Ts> static inline bool
1012hb_in_ranges (T u, T lo1, T hi1, Ts... ds)
1013{
1014 return hb_in_range<T> (u, lo1, hi1) || hb_in_ranges<T> (u, ds...);
1015}
1016
1017
1018/*
1019 * Overflow checking.
1020 */
1021
1022static inline bool
1023hb_unsigned_mul_overflows (unsigned int count, unsigned int size, unsigned *result = nullptr)
1024{
1025#if hb_has_builtin(__builtin_mul_overflow)
1026 unsigned stack_result;
1027 if (!result)
1028 result = &stack_result;
1029 return __builtin_mul_overflow (count, size, result);
1030#endif
1031
1032 if (result)
1033 *result = count * size;
1034 return (size > 0) && (count >= ((unsigned int) -1) / size);
1035}
1036
1037
1038/*
1039 * Sort and search.
1040 */
1041
1042template <typename K, typename V, typename ...Ts>
1043static int
1044_hb_cmp_method (const void *pkey, const void *pval, Ts... ds)
1045{
1046 const K& key = * (const K*) pkey;
1047 const V& val = * (const V*) pval;
1048
1049 return val.cmp (key, ds...);
1050}
1051
1052template <typename V, typename K, typename ...Ts>
1053static inline bool
1054hb_bsearch_impl (unsigned *pos, /* Out */
1055 const K& key,
1056 V* base, size_t nmemb, size_t stride,
1057 int (*compar)(const void *_key, const void *_item, Ts... _ds),
1058 Ts... ds)
1059{
1060 /* This is our *only* bsearch implementation. */
1061
1062 int min = 0, max = (int) nmemb - 1;
1063 while (min <= max)
1064 {
1065 int mid = ((unsigned int) min + (unsigned int) max) / 2;
1066#pragma GCC diagnostic push
1067#pragma GCC diagnostic ignored "-Wcast-align"
1068 V* p = (V*) (((const char *) base) + (mid * stride));
1069#pragma GCC diagnostic pop
1070 int c = compar ((const void *) std::addressof (key), (const void *) p, ds...);
1071 if (c < 0)
1072 max = mid - 1;
1073 else if (c > 0)
1074 min = mid + 1;
1075 else
1076 {
1077 *pos = mid;
1078 return true;
1079 }
1080 }
1081 *pos = min;
1082 return false;
1083}
1084
1085template <typename V, typename K>
1086static inline V*
1087hb_bsearch (const K& key, V* base,
1088 size_t nmemb, size_t stride = sizeof (V),
1089 int (*compar)(const void *_key, const void *_item) = _hb_cmp_method<K, V>)
1090{
1091 unsigned pos;
1092#pragma GCC diagnostic push
1093#pragma GCC diagnostic ignored "-Wcast-align"
1094 return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar) ?
1095 (V*) (((const char *) base) + (pos * stride)) : nullptr;
1096#pragma GCC diagnostic pop
1097}
1098template <typename V, typename K, typename ...Ts>
1099static inline V*
1100hb_bsearch (const K& key, V* base,
1101 size_t nmemb, size_t stride,
1102 int (*compar)(const void *_key, const void *_item, Ts... _ds),
1103 Ts... ds)
1104{
1105 unsigned pos;
1106#pragma GCC diagnostic push
1107#pragma GCC diagnostic ignored "-Wcast-align"
1108 return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar, ds...) ?
1109 (V*) (((const char *) base) + (pos * stride)) : nullptr;
1110#pragma GCC diagnostic pop
1111}
1112
1113
1114/* From https://github.com/noporpoise/sort_r
1115 Feb 5, 2019 (c8c65c1e)
1116 Modified to support optional argument using templates */
1117
1118/* Isaac Turner 29 April 2014 Public Domain */
1119
1120/*
1121hb_qsort function to be exported.
1122Parameters:
1123 base is the array to be sorted
1124 nel is the number of elements in the array
1125 width is the size in bytes of each element of the array
1126 compar is the comparison function
1127 arg (optional) is a pointer to be passed to the comparison function
1128
1129void hb_qsort(void *base, size_t nel, size_t width,
1130 int (*compar)(const void *_a, const void *_b, [void *_arg]),
1131 [void *arg]);
1132*/
1133
1134#define SORT_R_SWAP(a,b,tmp) ((void) ((tmp) = (a)), (void) ((a) = (b)), (b) = (tmp))
1135
1136/* swap a and b */
1137/* a and b must not be equal! */
1138static inline void sort_r_swap(char *__restrict a, char *__restrict b,
1139 size_t w)
1140{
1141 char tmp, *end = a+w;
1142 for(; a < end; a++, b++) { SORT_R_SWAP(*a, *b, tmp); }
1143}
1144
1145/* swap a, b iff a>b */
1146/* a and b must not be equal! */
1147/* __restrict is same as restrict but better support on old machines */
1148template <typename ...Ts>
1149static inline int sort_r_cmpswap(char *__restrict a,
1150 char *__restrict b, size_t w,
1151 int (*compar)(const void *_a,
1152 const void *_b,
1153 Ts... _ds),
1154 Ts... ds)
1155{
1156 if(compar(a, b, ds...) > 0) {
1157 sort_r_swap(a, b, w);
1158 return 1;
1159 }
1160 return 0;
1161}
1162
1163/*
1164Swap consecutive blocks of bytes of size na and nb starting at memory addr ptr,
1165with the smallest swap so that the blocks are in the opposite order. Blocks may
1166be internally re-ordered e.g.
1167 12345ab -> ab34512
1168 123abc -> abc123
1169 12abcde -> deabc12
1170*/
1171static inline void sort_r_swap_blocks(char *ptr, size_t na, size_t nb)
1172{
1173 if(na > 0 && nb > 0) {
1174 if(na > nb) { sort_r_swap(ptr, ptr+na, nb); }
1175 else { sort_r_swap(ptr, ptr+nb, na); }
1176 }
1177}
1178
1179/* Implement recursive quicksort ourselves */
1180/* Note: quicksort is not stable, equivalent values may be swapped */
1181template <typename ...Ts>
1182static inline void sort_r_simple(void *base, size_t nel, size_t w,
1183 int (*compar)(const void *_a,
1184 const void *_b,
1185 Ts... _ds),
1186 Ts... ds)
1187{
1188 char *b = (char *)base, *end = b + nel*w;
1189
1190 /* for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
1191 printf("\n"); */
1192
1193 if(nel < 10) {
1194 /* Insertion sort for arbitrarily small inputs */
1195 char *pi, *pj;
1196 for(pi = b+w; pi < end; pi += w) {
1197 for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,ds...); pj -= w) {}
1198 }
1199 }
1200 else
1201 {
1202 /* nel > 9; Quicksort */
1203
1204 int cmp;
1205 char *pl, *ple, *pr, *pre, *pivot;
1206 char *last = b+w*(nel-1), *tmp;
1207
1208 /*
1209 Use median of second, middle and second-last items as pivot.
1210 First and last may have been swapped with pivot and therefore be extreme
1211 */
1212 char *l[3];
1213 l[0] = b + w;
1214 l[1] = b+w*(nel/2);
1215 l[2] = last - w;
1216
1217 /* printf("pivots: %i, %i, %i\n", *(int*)l[0], *(int*)l[1], *(int*)l[2]); */
1218
1219 if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
1220 if(compar(l[1],l[2],ds...) > 0) {
1221 SORT_R_SWAP(l[1], l[2], tmp);
1222 if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
1223 }
1224
1225 /* swap mid value (l[1]), and last element to put pivot as last element */
1226 if(l[1] != last) { sort_r_swap(l[1], last, w); }
1227
1228 /*
1229 pl is the next item on the left to be compared to the pivot
1230 pr is the last item on the right that was compared to the pivot
1231 ple is the left position to put the next item that equals the pivot
1232 ple is the last right position where we put an item that equals the pivot
1233 v- end (beyond the array)
1234 EEEEEELLLLLLLLuuuuuuuuGGGGGGGEEEEEEEE.
1235 ^- b ^- ple ^- pl ^- pr ^- pre ^- last (where the pivot is)
1236 Pivot comparison key:
1237 E = equal, L = less than, u = unknown, G = greater than, E = equal
1238 */
1239 pivot = last;
1240 ple = pl = b;
1241 pre = pr = last;
1242
1243 /*
1244 Strategy:
1245 Loop into the list from the left and right at the same time to find:
1246 - an item on the left that is greater than the pivot
1247 - an item on the right that is less than the pivot
1248 Once found, they are swapped and the loop continues.
1249 Meanwhile items that are equal to the pivot are moved to the edges of the
1250 array.
1251 */
1252 while(pl < pr) {
1253 /* Move left hand items which are equal to the pivot to the far left.
1254 break when we find an item that is greater than the pivot */
1255 for(; pl < pr; pl += w) {
1256 cmp = compar(pl, pivot, ds...);
1257 if(cmp > 0) { break; }
1258 else if(cmp == 0) {
1259 if(ple < pl) { sort_r_swap(ple, pl, w); }
1260 ple += w;
1261 }
1262 }
1263 /* break if last batch of left hand items were equal to pivot */
1264 if(pl >= pr) { break; }
1265 /* Move right hand items which are equal to the pivot to the far right.
1266 break when we find an item that is less than the pivot */
1267 for(; pl < pr; ) {
1268 pr -= w; /* Move right pointer onto an unprocessed item */
1269 cmp = compar(pr, pivot, ds...);
1270 if(cmp == 0) {
1271 pre -= w;
1272 if(pr < pre) { sort_r_swap(pr, pre, w); }
1273 }
1274 else if(cmp < 0) {
1275 if(pl < pr) { sort_r_swap(pl, pr, w); }
1276 pl += w;
1277 break;
1278 }
1279 }
1280 }
1281
1282 pl = pr; /* pr may have gone below pl */
1283
1284 /*
1285 Now we need to go from: EEELLLGGGGEEEE
1286 to: LLLEEEEEEEGGGG
1287 Pivot comparison key:
1288 E = equal, L = less than, u = unknown, G = greater than, E = equal
1289 */
1290 sort_r_swap_blocks(b, ple-b, pl-ple);
1291 sort_r_swap_blocks(pr, pre-pr, end-pre);
1292
1293 /*for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
1294 printf("\n");*/
1295
1296 sort_r_simple(b, (pl-ple)/w, w, compar, ds...);
1297 sort_r_simple(end-(pre-pr), (pre-pr)/w, w, compar, ds...);
1298 }
1299}
1300
1301static inline void
1302hb_qsort (void *base, size_t nel, size_t width,
1303 int (*compar)(const void *_a, const void *_b))
1304{
1305#if defined(__OPTIMIZE_SIZE__) && !defined(HB_USE_INTERNAL_QSORT)
1306 qsort (base, nel, width, compar);
1307#else
1308 sort_r_simple (base, nel, width, compar);
1309#endif
1310}
1311
1312static inline void
1313hb_qsort (void *base, size_t nel, size_t width,
1314 int (*compar)(const void *_a, const void *_b, void *_arg),
1315 void *arg)
1316{
1317#ifdef HAVE_GNU_QSORT_R
1318 qsort_r (base, nel, width, compar, arg);
1319#else
1320 sort_r_simple (base, nel, width, compar, arg);
1321#endif
1322}
1323
1324
1325template <typename T, typename T2, typename T3 = int> static inline void
1326hb_stable_sort (T *array, unsigned int len, int(*compar)(const T2 *, const T2 *), T3 *array2 = nullptr)
1327{
1328 static_assert (hb_is_trivially_copy_assignable (T), "");
1329 static_assert (hb_is_trivially_copy_assignable (T3), "");
1330
1331 for (unsigned int i = 1; i < len; i++)
1332 {
1333 unsigned int j = i;
1334 while (j && compar (&array[j - 1], &array[i]) > 0)
1335 j--;
1336 if (i == j)
1337 continue;
1338 /* Move item i to occupy place for item j, shift what's in between. */
1339 {
1340 T t = array[i];
1341 memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
1342 array[j] = t;
1343 }
1344 if (array2)
1345 {
1346 T3 t = array2[i];
1347 memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T3));
1348 array2[j] = t;
1349 }
1350 }
1351}
1352
1353static inline hb_bool_t
1354hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out)
1355{
1356 unsigned int v;
1357 const char *p = s;
1358 const char *end = p + len;
1359 if (unlikely (!hb_parse_uint (&p, end, &v, true/* whole buffer */, base)))
1360 return false;
1361
1362 *out = v;
1363 return true;
1364}
1365
1366
1367/* Operators. */
1368
1369struct
1370{ HB_PARTIALIZE(2);
1371 template <typename T> constexpr auto
1372 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & b)
1373}
1374HB_FUNCOBJ (hb_bitwise_and);
1375struct
1376{ HB_PARTIALIZE(2);
1377 template <typename T> constexpr auto
1378 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a | b)
1379}
1380HB_FUNCOBJ (hb_bitwise_or);
1381struct
1382{ HB_PARTIALIZE(2);
1383 template <typename T> constexpr auto
1384 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a ^ b)
1385}
1386HB_FUNCOBJ (hb_bitwise_xor);
1387struct
1388{ HB_PARTIALIZE(2);
1389 template <typename T> constexpr auto
1390 operator () (const T &a, const T &b) const HB_AUTO_RETURN (~a & b)
1391}
1392HB_FUNCOBJ (hb_bitwise_lt);
1393struct
1394{ HB_PARTIALIZE(2);
1395 template <typename T> constexpr auto
1396 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & ~b)
1397}
1398HB_FUNCOBJ (hb_bitwise_gt); // aka sub
1399struct
1400{ HB_PARTIALIZE(2);
1401 template <typename T> constexpr auto
1402 operator () (const T &a, const T &b) const HB_AUTO_RETURN (~a | b)
1403}
1404HB_FUNCOBJ (hb_bitwise_le);
1405struct
1406{ HB_PARTIALIZE(2);
1407 template <typename T> constexpr auto
1408 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a | ~b)
1409}
1410HB_FUNCOBJ (hb_bitwise_ge);
1411struct
1412{
1413 template <typename T> constexpr auto
1414 operator () (const T &a) const HB_AUTO_RETURN (~a)
1415}
1416HB_FUNCOBJ (hb_bitwise_neg);
1417
1418struct
1419{ HB_PARTIALIZE(2);
1420 template <typename T, typename T2> constexpr auto
1421 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a + b)
1422}
1423HB_FUNCOBJ (hb_add);
1424struct
1425{ HB_PARTIALIZE(2);
1426 template <typename T, typename T2> constexpr auto
1427 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a - b)
1428}
1429HB_FUNCOBJ (hb_sub);
1430struct
1431{ HB_PARTIALIZE(2);
1432 template <typename T, typename T2> constexpr auto
1433 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (b - a)
1434}
1435HB_FUNCOBJ (hb_rsub);
1436struct
1437{ HB_PARTIALIZE(2);
1438 template <typename T, typename T2> constexpr auto
1439 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a * b)
1440}
1441HB_FUNCOBJ (hb_mul);
1442struct
1443{ HB_PARTIALIZE(2);
1444 template <typename T, typename T2> constexpr auto
1445 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a / b)
1446}
1447HB_FUNCOBJ (hb_div);
1448struct
1449{ HB_PARTIALIZE(2);
1450 template <typename T, typename T2> constexpr auto
1451 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a % b)
1452}
1453HB_FUNCOBJ (hb_mod);
1454struct
1455{
1456 template <typename T> constexpr auto
1457 operator () (const T &a) const HB_AUTO_RETURN (+a)
1458}
1459HB_FUNCOBJ (hb_pos);
1460struct
1461{
1462 template <typename T> constexpr auto
1463 operator () (const T &a) const HB_AUTO_RETURN (-a)
1464}
1465HB_FUNCOBJ (hb_neg);
1466struct
1467{
1468 template <typename T> constexpr auto
1469 operator () (T &a) const HB_AUTO_RETURN (++a)
1470}
1471HB_FUNCOBJ (hb_inc);
1472struct
1473{
1474 template <typename T> constexpr auto
1475 operator () (T &a) const HB_AUTO_RETURN (--a)
1476}
1477HB_FUNCOBJ (hb_dec);
1478
1479
1480/* Adapted from kurbo implementation with extra parameters added,
1481 * and finding for a particular range instead of 0.
1482 *
1483 * For documentation and implementation see:
1484 *
1485 * [ITP method]: https://en.wikipedia.org/wiki/ITP_Method
1486 * [An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality]: https://dl.acm.org/doi/10.1145/3423597
1487 * https://docs.rs/kurbo/0.8.1/kurbo/common/fn.solve_itp.html
1488 * https://github.com/linebender/kurbo/blob/fd839c25ea0c98576c7ce5789305822675a89938/src/common.rs#L162-L248
1489 */
1490template <typename func_t>
1491double solve_itp (func_t f,
1492 double a, double b,
1493 double epsilon,
1494 double min_y, double max_y,
1495 double &ya, double &yb, double &y)
1496{
1497 unsigned n1_2 = (unsigned) (hb_max (ceil (log2 ((b - a) / epsilon)) - 1.0, 0.0));
1498 const unsigned n0 = 1; // Hardwired
1499 const double k1 = 0.2 / (b - a); // Hardwired.
1500 unsigned nmax = n0 + n1_2;
1501 double scaled_epsilon = epsilon * double (1llu << nmax);
1502 double _2_epsilon = 2.0 * epsilon;
1503 while (b - a > _2_epsilon)
1504 {
1505 double x1_2 = 0.5 * (a + b);
1506 double r = scaled_epsilon - 0.5 * (b - a);
1507 double xf = (yb * a - ya * b) / (yb - ya);
1508 double sigma = x1_2 - xf;
1509 double b_a = b - a;
1510 // This has k2 = 2 hardwired for efficiency.
1511 double b_a_k2 = b_a * b_a;
1512 double delta = k1 * b_a_k2;
1513 int sigma_sign = sigma >= 0 ? +1 : -1;
1514 double xt = delta <= fabs (x1_2 - xf) ? xf + delta * sigma_sign : x1_2;
1515 double xitp = fabs (xt - x1_2) <= r ? xt : x1_2 - r * sigma_sign;
1516 double yitp = f (xitp);
1517 if (yitp > max_y)
1518 {
1519 b = xitp;
1520 yb = yitp;
1521 }
1522 else if (yitp < min_y)
1523 {
1524 a = xitp;
1525 ya = yitp;
1526 }
1527 else
1528 {
1529 y = yitp;
1530 return xitp;
1531 }
1532 scaled_epsilon *= 0.5;
1533 }
1534 return 0.5 * (a + b);
1535}
1536
1537
1538#endif /* HB_ALGS_HH */
1539