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