2 * Copyright © 2017 Google, Inc.
3 * Copyright © 2019 Facebook, Inc.
5 * This is part of HarfBuzz, a text shaping library.
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.
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
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.
25 * Google Author(s): Behdad Esfahbod
26 * Facebook Author(s): Behdad Esfahbod
35 #include "hb-number.hh"
38 /* Encodes three unsigned integers in one 64-bit number. If the inputs have more than 21 bits,
39 * values will be truncated / overlap, and might not decode exactly. */
40 #define HB_CODEPOINT_ENCODE3(x,y,z) (((uint64_t) (x) << 42) | ((uint64_t) (y) << 21) | (uint64_t) (z))
41 #define HB_CODEPOINT_DECODE3_1(v) ((hb_codepoint_t) ((v) >> 42))
42 #define HB_CODEPOINT_DECODE3_2(v) ((hb_codepoint_t) ((v) >> 21) & 0x1FFFFFu)
43 #define HB_CODEPOINT_DECODE3_3(v) ((hb_codepoint_t) (v) & 0x1FFFFFu)
45 /* Custom encoding used by hb-ucd. */
46 #define HB_CODEPOINT_ENCODE3_11_7_14(x,y,z) (((uint32_t) ((x) & 0x07FFu) << 21) | (((uint32_t) (y) & 0x007Fu) << 14) | (uint32_t) ((z) & 0x3FFFu))
47 #define HB_CODEPOINT_DECODE3_11_7_14_1(v) ((hb_codepoint_t) ((v) >> 21))
48 #define HB_CODEPOINT_DECODE3_11_7_14_2(v) ((hb_codepoint_t) (((v) >> 14) & 0x007Fu) | 0x0300)
49 #define HB_CODEPOINT_DECODE3_11_7_14_3(v) ((hb_codepoint_t) (v) & 0x3FFFu)
53 /* Note. This is dangerous in that if it's passed an rvalue, it returns rvalue-reference. */
54 template <typename T> constexpr auto
55 operator () (T&& v) const HB_AUTO_RETURN ( hb_forward<T> (v) )
57 HB_FUNCOBJ (hb_identity);
60 /* Like identity(), but only retains lvalue-references. Rvalues are returned as rvalues. */
61 template <typename T> constexpr T&
62 operator () (T& v) const { return v; }
64 template <typename T> constexpr hb_remove_reference<T>
65 operator () (T&& v) const { return v; }
67 HB_FUNCOBJ (hb_lidentity);
70 /* Like identity(), but always returns rvalue. */
71 template <typename T> constexpr hb_remove_reference<T>
72 operator () (T&& v) const { return v; }
74 HB_FUNCOBJ (hb_ridentity);
78 template <typename T> constexpr bool
79 operator () (T&& v) const { return bool (hb_forward<T> (v)); }
87 template <typename T> constexpr auto
88 impl (const T& v, hb_priority<1>) const HB_RETURN (uint32_t, hb_deref (v).hash ())
91 hb_enable_if (hb_is_integral (T))> constexpr auto
92 impl (const T& v, hb_priority<0>) const HB_AUTO_RETURN
94 /* Knuth's multiplicative method: */
95 (uint32_t) v * 2654435761u
100 template <typename T> constexpr auto
101 operator () (const T& v) const HB_RETURN (uint32_t, impl (v, hb_prioritize))
103 HB_FUNCOBJ (hb_hash);
110 /* Pointer-to-member-function. */
111 template <typename Appl, typename T, typename ...Ts> auto
112 impl (Appl&& a, hb_priority<2>, T &&v, Ts&&... ds) const HB_AUTO_RETURN
113 ((hb_deref (hb_forward<T> (v)).*hb_forward<Appl> (a)) (hb_forward<Ts> (ds)...))
115 /* Pointer-to-member. */
116 template <typename Appl, typename T> auto
117 impl (Appl&& a, hb_priority<1>, T &&v) const HB_AUTO_RETURN
118 ((hb_deref (hb_forward<T> (v))).*hb_forward<Appl> (a))
121 template <typename Appl, typename ...Ts> auto
122 impl (Appl&& a, hb_priority<0>, Ts&&... ds) const HB_AUTO_RETURN
123 (hb_deref (hb_forward<Appl> (a)) (hb_forward<Ts> (ds)...))
127 template <typename Appl, typename ...Ts> auto
128 operator () (Appl&& a, Ts&&... ds) const HB_AUTO_RETURN
130 impl (hb_forward<Appl> (a),
132 hb_forward<Ts> (ds)...)
135 HB_FUNCOBJ (hb_invoke);
137 template <unsigned Pos, typename Appl, typename V>
140 hb_partial_t (Appl a, V v) : a (a), v (v) {}
142 static_assert (Pos > 0, "");
144 template <typename ...Ts,
146 hb_enable_if (P == 1)> auto
147 operator () (Ts&& ...ds) -> decltype (hb_invoke (hb_declval (Appl),
151 return hb_invoke (hb_forward<Appl> (a),
153 hb_forward<Ts> (ds)...);
155 template <typename T0, typename ...Ts,
157 hb_enable_if (P == 2)> auto
158 operator () (T0&& d0, Ts&& ...ds) -> decltype (hb_invoke (hb_declval (Appl),
163 return hb_invoke (hb_forward<Appl> (a),
166 hb_forward<Ts> (ds)...);
170 hb_reference_wrapper<Appl> a;
173 template <unsigned Pos=1, typename Appl, typename V>
174 auto hb_partial (Appl&& a, V&& v) HB_AUTO_RETURN
175 (( hb_partial_t<Pos, Appl, V> (a, v) ))
177 /* The following, HB_PARTIALIZE, macro uses a particular corner-case
178 * of C++11 that is not particularly well-supported by all compilers.
179 * What's happening is that it's using "this" in a trailing return-type
180 * via decltype(). Broken compilers deduce the type of "this" pointer
181 * in that context differently from what it resolves to in the body
184 * One probable cause of this is that at the time of trailing return
185 * type declaration, "this" points to an incomplete type, whereas in
186 * the function body the type is complete. That doesn't justify the
187 * error in any way, but is probably what's happening.
189 * In the case of MSVC, we get around this by using C++14 "decltype(auto)"
190 * which deduces the type from the actual return statement. For gcc 4.8
191 * we use "+this" instead of "this" which produces an rvalue that seems
192 * to be deduced as the same type with this particular compiler, and seem
193 * to be fine as default code path as well.
196 /* https://github.com/harfbuzz/harfbuzz/issues/1730 */ \
197 #define HB_PARTIALIZE(Pos) \
198 template <typename _T> \
199 decltype(auto) operator () (_T&& _v) const \
200 { return hb_partial<Pos> (this, hb_forward<_T> (_v)); } \
201 static_assert (true, "")
203 /* https://github.com/harfbuzz/harfbuzz/issues/1724 */
204 #define HB_PARTIALIZE(Pos) \
205 template <typename _T> \
206 auto operator () (_T&& _v) const HB_AUTO_RETURN \
207 (hb_partial<Pos> (+this, hb_forward<_T> (_v))) \
208 static_assert (true, "")
216 template <typename Pred, typename Val> auto
217 impl (Pred&& p, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
218 (hb_deref (hb_forward<Pred> (p)).has (hb_forward<Val> (v)))
220 template <typename Pred, typename Val> auto
221 impl (Pred&& p, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
223 hb_invoke (hb_forward<Pred> (p),
229 template <typename Pred, typename Val> auto
230 operator () (Pred&& p, Val &&v) const HB_RETURN (bool,
231 impl (hb_forward<Pred> (p),
242 template <typename Pred, typename Val> auto
243 impl (Pred&& p, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
245 hb_has (hb_forward<Pred> (p),
249 template <typename Pred, typename Val> auto
250 impl (Pred&& p, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
252 hb_forward<Pred> (p) == hb_forward<Val> (v)
257 template <typename Pred, typename Val> auto
258 operator () (Pred&& p, Val &&v) const HB_RETURN (bool,
259 impl (hb_forward<Pred> (p),
264 HB_FUNCOBJ (hb_match);
270 template <typename Proj, typename Val> auto
271 impl (Proj&& f, Val &&v, hb_priority<2>) const HB_AUTO_RETURN
272 (hb_deref (hb_forward<Proj> (f)).get (hb_forward<Val> (v)))
274 template <typename Proj, typename Val> auto
275 impl (Proj&& f, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
277 hb_invoke (hb_forward<Proj> (f),
281 template <typename Proj, typename Val> auto
282 impl (Proj&& f, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
284 hb_forward<Proj> (f)[hb_forward<Val> (v)]
289 template <typename Proj, typename Val> auto
290 operator () (Proj&& f, Val &&v) const HB_AUTO_RETURN
292 impl (hb_forward<Proj> (f),
300 template <typename T1, typename T2>
305 typedef hb_pair_t<T1, T2> pair_t;
307 hb_pair_t (T1 a, T2 b) : first (a), second (b) {}
309 template <typename Q1, typename Q2,
310 hb_enable_if (hb_is_convertible (T1, Q1) &&
311 hb_is_convertible (T2, T2))>
312 operator hb_pair_t<Q1, Q2> () { return hb_pair_t<Q1, Q2> (first, second); }
314 hb_pair_t<T1, T2> reverse () const
315 { return hb_pair_t<T1, T2> (second, first); }
317 bool operator == (const pair_t& o) const { return first == o.first && second == o.second; }
318 bool operator != (const pair_t& o) const { return !(*this == o); }
319 bool operator < (const pair_t& o) const { return first < o.first || (first == o.first && second < o.second); }
320 bool operator >= (const pair_t& o) const { return !(*this < o); }
321 bool operator > (const pair_t& o) const { return first > o.first || (first == o.first && second > o.second); }
322 bool operator <= (const pair_t& o) const { return !(*this > o); }
327 #define hb_pair_t(T1,T2) hb_pair_t<T1, T2>
328 template <typename T1, typename T2> static inline hb_pair_t<T1, T2>
329 hb_pair (T1&& a, T2&& b) { return hb_pair_t<T1, T2> (a, b); }
333 template <typename Pair> constexpr typename Pair::first_t
334 operator () (const Pair& pair) const { return pair.first; }
336 HB_FUNCOBJ (hb_first);
340 template <typename Pair> constexpr typename Pair::second_t
341 operator () (const Pair& pair) const { return pair.second; }
343 HB_FUNCOBJ (hb_second);
345 /* Note. In min/max impl, we can use hb_type_identity<T> for second argument.
346 * However, that would silently convert between different-signedness integers.
347 * Instead we accept two different types, such that compiler can err if
348 * comparing integers of different signedness. */
351 template <typename T, typename T2> constexpr auto
352 operator () (T&& a, T2&& b) const HB_AUTO_RETURN
353 (hb_forward<T> (a) <= hb_forward<T2> (b) ? hb_forward<T> (a) : hb_forward<T2> (b))
358 template <typename T, typename T2> constexpr auto
359 operator () (T&& a, T2&& b) const HB_AUTO_RETURN
360 (hb_forward<T> (a) >= hb_forward<T2> (b) ? hb_forward<T> (a) : hb_forward<T2> (b))
365 template <typename T, typename T2, typename T3> constexpr auto
366 operator () (T&& x, T2&& min, T3&& max) const HB_AUTO_RETURN
367 (hb_min (hb_max (hb_forward<T> (x), hb_forward<T2> (min)), hb_forward<T3> (max)))
369 HB_FUNCOBJ (hb_clamp);
376 /* Return the number of 1 bits in v. */
377 template <typename T>
378 static inline HB_CONST_FUNC unsigned int
381 #if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
382 if (sizeof (T) <= sizeof (unsigned int))
383 return __builtin_popcount (v);
385 if (sizeof (T) <= sizeof (unsigned long))
386 return __builtin_popcountl (v);
388 if (sizeof (T) <= sizeof (unsigned long long))
389 return __builtin_popcountll (v);
396 y = (v >> 1) &033333333333;
397 y = v - y - ((y >>1) & 033333333333);
398 return (((y + (y >> 3)) & 030707070707) % 077);
403 unsigned int shift = 32;
404 return hb_popcount<uint32_t> ((uint32_t) v) + hb_popcount ((uint32_t) (v >> shift));
407 if (sizeof (T) == 16)
409 unsigned int shift = 64;
410 return hb_popcount<uint64_t> ((uint64_t) v) + hb_popcount ((uint64_t) (v >> shift));
414 return 0; /* Shut up stupid compiler. */
417 /* Returns the number of bits needed to store number */
418 template <typename T>
419 static inline HB_CONST_FUNC unsigned int
422 if (unlikely (!v)) return 0;
424 #if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
425 if (sizeof (T) <= sizeof (unsigned int))
426 return sizeof (unsigned int) * 8 - __builtin_clz (v);
428 if (sizeof (T) <= sizeof (unsigned long))
429 return sizeof (unsigned long) * 8 - __builtin_clzl (v);
431 if (sizeof (T) <= sizeof (unsigned long long))
432 return sizeof (unsigned long long) * 8 - __builtin_clzll (v);
435 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
436 if (sizeof (T) <= sizeof (unsigned int))
439 _BitScanReverse (&where, v);
446 _BitScanReverse64 (&where, v);
455 const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
456 const unsigned int S[] = {1, 2, 4, 8, 16};
458 for (int i = 4; i >= 0; i--)
469 const uint64_t b[] = {0x2ULL, 0xCULL, 0xF0ULL, 0xFF00ULL, 0xFFFF0000ULL, 0xFFFFFFFF00000000ULL};
470 const unsigned int S[] = {1, 2, 4, 8, 16, 32};
472 for (int i = 5; i >= 0; i--)
480 if (sizeof (T) == 16)
482 unsigned int shift = 64;
483 return (v >> shift) ? hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift :
484 hb_bit_storage<uint64_t> ((uint64_t) v);
488 return 0; /* Shut up stupid compiler. */
491 /* Returns the number of zero bits in the least significant side of v */
492 template <typename T>
493 static inline HB_CONST_FUNC unsigned int
496 if (unlikely (!v)) return 8 * sizeof (T);
498 #if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
499 if (sizeof (T) <= sizeof (unsigned int))
500 return __builtin_ctz (v);
502 if (sizeof (T) <= sizeof (unsigned long))
503 return __builtin_ctzl (v);
505 if (sizeof (T) <= sizeof (unsigned long long))
506 return __builtin_ctzll (v);
509 #if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
510 if (sizeof (T) <= sizeof (unsigned int))
513 _BitScanForward (&where, v);
520 _BitScanForward64 (&where, v);
532 if (v & 0x0000FFFF) c -= 16;
533 if (v & 0x00FF00FF) c -= 8;
534 if (v & 0x0F0F0F0F) c -= 4;
535 if (v & 0x33333333) c -= 2;
536 if (v & 0x55555555) c -= 1;
543 v &= - (int64_t) (v);
545 if (v & 0x00000000FFFFFFFFULL) c -= 32;
546 if (v & 0x0000FFFF0000FFFFULL) c -= 16;
547 if (v & 0x00FF00FF00FF00FFULL) c -= 8;
548 if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4;
549 if (v & 0x3333333333333333ULL) c -= 2;
550 if (v & 0x5555555555555555ULL) c -= 1;
553 if (sizeof (T) == 16)
555 unsigned int shift = 64;
556 return (uint64_t) v ? hb_bit_storage<uint64_t> ((uint64_t) v) :
557 hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift;
561 return 0; /* Shut up stupid compiler. */
569 /* ASCII tag/character handling */
570 static inline bool ISALPHA (unsigned char c)
571 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); }
572 static inline bool ISALNUM (unsigned char c)
573 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); }
574 static inline bool ISSPACE (unsigned char c)
575 { return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; }
576 static inline unsigned char TOUPPER (unsigned char c)
577 { return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; }
578 static inline unsigned char TOLOWER (unsigned char c)
579 { return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; }
580 static inline bool ISHEX (unsigned char c)
581 { return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'); }
582 static inline unsigned char TOHEX (uint8_t c)
583 { return (c & 0xF) <= 9 ? (c & 0xF) + '0' : (c & 0xF) + 'a' - 10; }
584 static inline uint8_t FROMHEX (unsigned char c)
585 { return (c >= '0' && c <= '9') ? c - '0' : TOLOWER (c) - 'a' + 10; }
587 static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)
588 { return (a + (b - 1)) / b; }
592 template <typename Type, unsigned int n>
593 static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }
594 /* A const version, but does not detect erratically being called on pointers. */
595 #define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
599 hb_memcmp (const void *a, const void *b, unsigned int len)
601 /* It's illegal to pass NULL to memcmp(), even if len is zero.
603 * https://sourceware.org/bugzilla/show_bug.cgi?id=23878 */
604 if (unlikely (!len)) return 0;
605 return memcmp (a, b, len);
609 hb_memset (void *s, int c, unsigned int n)
611 /* It's illegal to pass NULL to memset(), even if n is zero. */
612 if (unlikely (!n)) return 0;
613 return memset (s, c, n);
616 static inline unsigned int
617 hb_ceil_to_4 (unsigned int v)
619 return ((v - 1) | 3) + 1;
622 template <typename T> static inline bool
623 hb_in_range (T u, T lo, T hi)
625 static_assert (!hb_is_signed<T>::value, "");
627 /* The casts below are important as if T is smaller than int,
628 * the subtract results will become a signed int! */
629 return (T)(u - lo) <= (T)(hi - lo);
631 template <typename T> static inline bool
632 hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2)
634 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2);
636 template <typename T> static inline bool
637 hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3)
639 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2) || hb_in_range (u, lo3, hi3);
647 /* Consider __builtin_mul_overflow use here also */
649 hb_unsigned_mul_overflows (unsigned int count, unsigned int size)
651 return (size > 0) && (count >= ((unsigned int) -1) / size);
659 template <typename K, typename V, typename ...Ts>
661 _hb_cmp_method (const void *pkey, const void *pval, Ts... ds)
663 const K& key = * (const K*) pkey;
664 const V& val = * (const V*) pval;
666 return val.cmp (key, ds...);
669 template <typename V, typename K, typename ...Ts>
671 hb_bsearch_impl (unsigned *pos, /* Out */
673 V* base, size_t nmemb, size_t stride,
674 int (*compar)(const void *_key, const void *_item, Ts... _ds),
677 /* This is our *only* bsearch implementation. */
679 int min = 0, max = (int) nmemb - 1;
682 int mid = ((unsigned int) min + (unsigned int) max) / 2;
683 #pragma GCC diagnostic push
684 #pragma GCC diagnostic ignored "-Wcast-align"
685 V* p = (V*) (((const char *) base) + (mid * stride));
686 #pragma GCC diagnostic pop
687 int c = compar ((const void *) hb_addressof (key), (const void *) p, ds...);
702 template <typename V, typename K>
704 hb_bsearch (const K& key, V* base,
705 size_t nmemb, size_t stride = sizeof (V),
706 int (*compar)(const void *_key, const void *_item) = _hb_cmp_method<K, V>)
709 #pragma GCC diagnostic push
710 #pragma GCC diagnostic ignored "-Wcast-align"
711 return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar) ?
712 (V*) (((const char *) base) + (pos * stride)) : nullptr;
713 #pragma GCC diagnostic pop
715 template <typename V, typename K, typename ...Ts>
717 hb_bsearch (const K& key, V* base,
718 size_t nmemb, size_t stride,
719 int (*compar)(const void *_key, const void *_item, Ts... _ds),
723 #pragma GCC diagnostic push
724 #pragma GCC diagnostic ignored "-Wcast-align"
725 return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar, ds...) ?
726 (V*) (((const char *) base) + (pos * stride)) : nullptr;
727 #pragma GCC diagnostic pop
731 /* From https://github.com/noporpoise/sort_r
732 Feb 5, 2019 (c8c65c1e)
733 Modified to support optional argument using templates */
735 /* Isaac Turner 29 April 2014 Public Domain */
738 hb_qsort function to be exported.
740 base is the array to be sorted
741 nel is the number of elements in the array
742 width is the size in bytes of each element of the array
743 compar is the comparison function
744 arg (optional) is a pointer to be passed to the comparison function
746 void hb_qsort(void *base, size_t nel, size_t width,
747 int (*compar)(const void *_a, const void *_b, [void *_arg]),
751 #define SORT_R_SWAP(a,b,tmp) ((tmp) = (a), (a) = (b), (b) = (tmp))
754 /* a and b must not be equal! */
755 static inline void sort_r_swap(char *__restrict a, char *__restrict b,
758 char tmp, *end = a+w;
759 for(; a < end; a++, b++) { SORT_R_SWAP(*a, *b, tmp); }
762 /* swap a, b iff a>b */
763 /* a and b must not be equal! */
764 /* __restrict is same as restrict but better support on old machines */
765 template <typename ...Ts>
766 static inline int sort_r_cmpswap(char *__restrict a,
767 char *__restrict b, size_t w,
768 int (*compar)(const void *_a,
773 if(compar(a, b, ds...) > 0) {
774 sort_r_swap(a, b, w);
781 Swap consecutive blocks of bytes of size na and nb starting at memory addr ptr,
782 with the smallest swap so that the blocks are in the opposite order. Blocks may
783 be internally re-ordered e.g.
788 static inline void sort_r_swap_blocks(char *ptr, size_t na, size_t nb)
790 if(na > 0 && nb > 0) {
791 if(na > nb) { sort_r_swap(ptr, ptr+na, nb); }
792 else { sort_r_swap(ptr, ptr+nb, na); }
796 /* Implement recursive quicksort ourselves */
797 /* Note: quicksort is not stable, equivalent values may be swapped */
798 template <typename ...Ts>
799 static inline void sort_r_simple(void *base, size_t nel, size_t w,
800 int (*compar)(const void *_a,
805 char *b = (char *)base, *end = b + nel*w;
807 /* for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
811 /* Insertion sort for arbitrarily small inputs */
813 for(pi = b+w; pi < end; pi += w) {
814 for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,ds...); pj -= w) {}
819 /* nel > 9; Quicksort */
822 char *pl, *ple, *pr, *pre, *pivot;
823 char *last = b+w*(nel-1), *tmp;
826 Use median of second, middle and second-last items as pivot.
827 First and last may have been swapped with pivot and therefore be extreme
834 /* printf("pivots: %i, %i, %i\n", *(int*)l[0], *(int*)l[1], *(int*)l[2]); */
836 if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
837 if(compar(l[1],l[2],ds...) > 0) {
838 SORT_R_SWAP(l[1], l[2], tmp);
839 if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
842 /* swap mid value (l[1]), and last element to put pivot as last element */
843 if(l[1] != last) { sort_r_swap(l[1], last, w); }
846 pl is the next item on the left to be compared to the pivot
847 pr is the last item on the right that was compared to the pivot
848 ple is the left position to put the next item that equals the pivot
849 ple is the last right position where we put an item that equals the pivot
850 v- end (beyond the array)
851 EEEEEELLLLLLLLuuuuuuuuGGGGGGGEEEEEEEE.
852 ^- b ^- ple ^- pl ^- pr ^- pre ^- last (where the pivot is)
853 Pivot comparison key:
854 E = equal, L = less than, u = unknown, G = greater than, E = equal
862 Loop into the list from the left and right at the same time to find:
863 - an item on the left that is greater than the pivot
864 - an item on the right that is less than the pivot
865 Once found, they are swapped and the loop continues.
866 Meanwhile items that are equal to the pivot are moved to the edges of the
870 /* Move left hand items which are equal to the pivot to the far left.
871 break when we find an item that is greater than the pivot */
872 for(; pl < pr; pl += w) {
873 cmp = compar(pl, pivot, ds...);
874 if(cmp > 0) { break; }
876 if(ple < pl) { sort_r_swap(ple, pl, w); }
880 /* break if last batch of left hand items were equal to pivot */
881 if(pl >= pr) { break; }
882 /* Move right hand items which are equal to the pivot to the far right.
883 break when we find an item that is less than the pivot */
885 pr -= w; /* Move right pointer onto an unprocessed item */
886 cmp = compar(pr, pivot, ds...);
889 if(pr < pre) { sort_r_swap(pr, pre, w); }
892 if(pl < pr) { sort_r_swap(pl, pr, w); }
899 pl = pr; /* pr may have gone below pl */
902 Now we need to go from: EEELLLGGGGEEEE
904 Pivot comparison key:
905 E = equal, L = less than, u = unknown, G = greater than, E = equal
907 sort_r_swap_blocks(b, ple-b, pl-ple);
908 sort_r_swap_blocks(pr, pre-pr, end-pre);
910 /*for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
913 sort_r_simple(b, (pl-ple)/w, w, compar, ds...);
914 sort_r_simple(end-(pre-pr), (pre-pr)/w, w, compar, ds...);
919 hb_qsort (void *base, size_t nel, size_t width,
920 int (*compar)(const void *_a, const void *_b))
922 #if defined(__OPTIMIZE_SIZE__) && !defined(HB_USE_INTERNAL_QSORT)
923 qsort (base, nel, width, compar);
925 sort_r_simple (base, nel, width, compar);
930 hb_qsort (void *base, size_t nel, size_t width,
931 int (*compar)(const void *_a, const void *_b, void *_arg),
934 #ifdef HAVE_GNU_QSORT_R
935 qsort_r (base, nel, width, compar, arg);
937 sort_r_simple (base, nel, width, compar, arg);
942 template <typename T, typename T2, typename T3> static inline void
943 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T2 *, const T2 *), T3 *array2)
945 for (unsigned int i = 1; i < len; i++)
948 while (j && compar (&array[j - 1], &array[i]) > 0)
952 /* Move item i to occupy place for item j, shift what's in between. */
955 memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
961 memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T3));
967 template <typename T> static inline void
968 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
970 hb_stable_sort (array, len, compar, (int *) nullptr);
973 static inline hb_bool_t
974 hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out)
978 const char *end = p + len;
979 if (unlikely (!hb_parse_uint (&p, end, &v, true/* whole buffer */, base)))
989 struct hb_bitwise_and
991 static constexpr bool passthru_left = false;
992 static constexpr bool passthru_right = false;
993 template <typename T> constexpr auto
994 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & b)
996 HB_FUNCOBJ (hb_bitwise_and);
999 static constexpr bool passthru_left = true;
1000 static constexpr bool passthru_right = true;
1001 template <typename T> constexpr auto
1002 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a | b)
1004 HB_FUNCOBJ (hb_bitwise_or);
1005 struct hb_bitwise_xor
1007 static constexpr bool passthru_left = true;
1008 static constexpr bool passthru_right = true;
1009 template <typename T> constexpr auto
1010 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a ^ b)
1012 HB_FUNCOBJ (hb_bitwise_xor);
1013 struct hb_bitwise_sub
1015 static constexpr bool passthru_left = true;
1016 static constexpr bool passthru_right = false;
1017 template <typename T> constexpr auto
1018 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & ~b)
1020 HB_FUNCOBJ (hb_bitwise_sub);
1023 template <typename T> constexpr auto
1024 operator () (const T &a) const HB_AUTO_RETURN (~a)
1026 HB_FUNCOBJ (hb_bitwise_neg);
1030 template <typename T, typename T2> constexpr auto
1031 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a + b)
1033 HB_FUNCOBJ (hb_add);
1036 template <typename T, typename T2> constexpr auto
1037 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a - b)
1039 HB_FUNCOBJ (hb_sub);
1042 template <typename T, typename T2> constexpr auto
1043 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a * b)
1045 HB_FUNCOBJ (hb_mul);
1048 template <typename T, typename T2> constexpr auto
1049 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a / b)
1051 HB_FUNCOBJ (hb_div);
1054 template <typename T, typename T2> constexpr auto
1055 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a % b)
1057 HB_FUNCOBJ (hb_mod);
1060 template <typename T> constexpr auto
1061 operator () (const T &a) const HB_AUTO_RETURN (+a)
1063 HB_FUNCOBJ (hb_pos);
1066 template <typename T> constexpr auto
1067 operator () (const T &a) const HB_AUTO_RETURN (-a)
1069 HB_FUNCOBJ (hb_neg);
1072 template <typename T> constexpr auto
1073 operator () (T &a) const HB_AUTO_RETURN (++a)
1075 HB_FUNCOBJ (hb_inc);
1078 template <typename T> constexpr auto
1079 operator () (T &a) const HB_AUTO_RETURN (--a)
1081 HB_FUNCOBJ (hb_dec);
1084 /* Compiler-assisted vectorization. */
1086 /* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))),
1087 * basically a fixed-size bitset. */
1088 template <typename elt_t, unsigned int byte_size>
1089 struct hb_vector_size_t
1091 elt_t& operator [] (unsigned int i) { return v[i]; }
1092 const elt_t& operator [] (unsigned int i) const { return v[i]; }
1094 void clear (unsigned char v = 0) { memset (this, v, sizeof (*this)); }
1096 template <typename Op>
1097 hb_vector_size_t process (const Op& op) const
1100 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
1104 template <typename Op>
1105 hb_vector_size_t process (const Op& op, const hb_vector_size_t &o) const
1108 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
1109 r.v[i] = op (v[i], o.v[i]);
1112 hb_vector_size_t operator | (const hb_vector_size_t &o) const
1113 { return process (hb_bitwise_or, o); }
1114 hb_vector_size_t operator & (const hb_vector_size_t &o) const
1115 { return process (hb_bitwise_and, o); }
1116 hb_vector_size_t operator ^ (const hb_vector_size_t &o) const
1117 { return process (hb_bitwise_xor, o); }
1118 hb_vector_size_t operator ~ () const
1119 { return process (hb_bitwise_neg); }
1122 static_assert (0 == byte_size % sizeof (elt_t), "");
1123 elt_t v[byte_size / sizeof (elt_t)];
1127 #endif /* HB_ALGS_HH */