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