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
38/* Encodes three unsigned integers in one 64-bit number. If the inputs have more than 21 bits,
39 * values will be truncated / overlap, and might not decode exactly. */
40#define HB_CODEPOINT_ENCODE3(x,y,z) (((uint64_t) (x) << 42) | ((uint64_t) (y) << 21) | (uint64_t) (z))
41#define HB_CODEPOINT_DECODE3_1(v) ((hb_codepoint_t) ((v) >> 42))
42#define HB_CODEPOINT_DECODE3_2(v) ((hb_codepoint_t) ((v) >> 21) & 0x1FFFFFu)
43#define HB_CODEPOINT_DECODE3_3(v) ((hb_codepoint_t) (v) & 0x1FFFFFu)
44
45/* Custom encoding used by hb-ucd. */
46#define HB_CODEPOINT_ENCODE3_11_7_14(x,y,z) (((uint32_t) ((x) & 0x07FFu) << 21) | (((uint32_t) (y) & 0x007Fu) << 14) | (uint32_t) ((z) & 0x3FFFu))
47#define HB_CODEPOINT_DECODE3_11_7_14_1(v) ((hb_codepoint_t) ((v) >> 21))
48#define HB_CODEPOINT_DECODE3_11_7_14_2(v) ((hb_codepoint_t) (((v) >> 14) & 0x007Fu) | 0x0300)
49#define HB_CODEPOINT_DECODE3_11_7_14_3(v) ((hb_codepoint_t) (v) & 0x3FFFu)
50
51struct
52{
53 /* Note. This is dangerous in that if it's passed an rvalue, it returns rvalue-reference. */
54 template <typename T> constexpr auto
55 operator () (T&& v) const HB_AUTO_RETURN ( hb_forward<T> (v) )
56}
57HB_FUNCOBJ (hb_identity);
58struct
59{
60 /* Like identity(), but only retains lvalue-references. Rvalues are returned as rvalues. */
61 template <typename T> constexpr T&
62 operator () (T& v) const { return v; }
63
64 template <typename T> constexpr hb_remove_reference<T>
65 operator () (T&& v) const { return v; }
66}
67HB_FUNCOBJ (hb_lidentity);
68struct
69{
70 /* Like identity(), but always returns rvalue. */
71 template <typename T> constexpr hb_remove_reference<T>
72 operator () (T&& v) const { return v; }
73}
74HB_FUNCOBJ (hb_ridentity);
75
76struct
77{
78 template <typename T> constexpr bool
79 operator () (T&& v) const { return bool (hb_forward<T> (v)); }
80}
81HB_FUNCOBJ (hb_bool);
82
83struct
84{
85 private:
86
87 template <typename T> constexpr auto
88 impl (const T& v, hb_priority<1>) const HB_RETURN (uint32_t, hb_deref (v).hash ())
89
90 template <typename T,
91 hb_enable_if (hb_is_integral (T))> constexpr auto
92 impl (const T& v, hb_priority<0>) const HB_AUTO_RETURN
93 (
94 /* Knuth's multiplicative method: */
95 (uint32_t) v * 2654435761u
96 )
97
98 public:
99
100 template <typename T> constexpr auto
101 operator () (const T& v) const HB_RETURN (uint32_t, impl (v, hb_prioritize))
102}
103HB_FUNCOBJ (hb_hash);
104
105
106struct
107{
108 private:
109
110 /* Pointer-to-member-function. */
111 template <typename Appl, typename T, typename ...Ts> auto
112 impl (Appl&& a, hb_priority<2>, T &&v, Ts&&... ds) const HB_AUTO_RETURN
113 ((hb_deref (hb_forward<T> (v)).*hb_forward<Appl> (a)) (hb_forward<Ts> (ds)...))
114
115 /* Pointer-to-member. */
116 template <typename Appl, typename T> auto
117 impl (Appl&& a, hb_priority<1>, T &&v) const HB_AUTO_RETURN
118 ((hb_deref (hb_forward<T> (v))).*hb_forward<Appl> (a))
119
120 /* Operator(). */
121 template <typename Appl, typename ...Ts> auto
122 impl (Appl&& a, hb_priority<0>, Ts&&... ds) const HB_AUTO_RETURN
123 (hb_deref (hb_forward<Appl> (a)) (hb_forward<Ts> (ds)...))
124
125 public:
126
127 template <typename Appl, typename ...Ts> auto
128 operator () (Appl&& a, Ts&&... ds) const HB_AUTO_RETURN
129 (
130 impl (hb_forward<Appl> (a),
131 hb_prioritize,
132 hb_forward<Ts> (ds)...)
133 )
134}
135HB_FUNCOBJ (hb_invoke);
136
137template <unsigned Pos, typename Appl, typename V>
138struct hb_partial_t
139{
140 hb_partial_t (Appl a, V v) : a (a), v (v) {}
141
142 static_assert (Pos > 0, "");
143
144 template <typename ...Ts,
145 unsigned P = Pos,
146 hb_enable_if (P == 1)> auto
147 operator () (Ts&& ...ds) -> decltype (hb_invoke (hb_declval (Appl),
148 hb_declval (V),
149 hb_declval (Ts)...))
150 {
151 return hb_invoke (hb_forward<Appl> (a),
152 hb_forward<V> (v),
153 hb_forward<Ts> (ds)...);
154 }
155 template <typename T0, typename ...Ts,
156 unsigned P = Pos,
157 hb_enable_if (P == 2)> auto
158 operator () (T0&& d0, Ts&& ...ds) -> decltype (hb_invoke (hb_declval (Appl),
159 hb_declval (T0),
160 hb_declval (V),
161 hb_declval (Ts)...))
162 {
163 return hb_invoke (hb_forward<Appl> (a),
164 hb_forward<T0> (d0),
165 hb_forward<V> (v),
166 hb_forward<Ts> (ds)...);
167 }
168
169 private:
170 hb_reference_wrapper<Appl> a;
171 V v;
172};
173template <unsigned Pos=1, typename Appl, typename V>
174auto hb_partial (Appl&& a, V&& v) HB_AUTO_RETURN
175(( hb_partial_t<Pos, Appl, V> (a, v) ))
176
177/* The following, HB_PARTIALIZE, macro uses a particular corner-case
178 * of C++11 that is not particularly well-supported by all compilers.
179 * What's happening is that it's using "this" in a trailing return-type
180 * via decltype(). Broken compilers deduce the type of "this" pointer
181 * in that context differently from what it resolves to in the body
182 * of the function.
183 *
184 * One probable cause of this is that at the time of trailing return
185 * type declaration, "this" points to an incomplete type, whereas in
186 * the function body the type is complete. That doesn't justify the
187 * error in any way, but is probably what's happening.
188 *
189 * In the case of MSVC, we get around this by using C++14 "decltype(auto)"
190 * which deduces the type from the actual return statement. For gcc 4.8
191 * we use "+this" instead of "this" which produces an rvalue that seems
192 * to be deduced as the same type with this particular compiler, and seem
193 * to be fine as default code path as well.
194 */
195#ifdef _MSC_VER
196/* https://github.com/harfbuzz/harfbuzz/issues/1730 */ \
197#define HB_PARTIALIZE(Pos) \
198 template <typename _T> \
199 decltype(auto) operator () (_T&& _v) const \
200 { return hb_partial<Pos> (this, hb_forward<_T> (_v)); } \
201 static_assert (true, "")
202#else
203/* https://github.com/harfbuzz/harfbuzz/issues/1724 */
204#define HB_PARTIALIZE(Pos) \
205 template <typename _T> \
206 auto operator () (_T&& _v) const HB_AUTO_RETURN \
207 (hb_partial<Pos> (+this, hb_forward<_T> (_v))) \
208 static_assert (true, "")
209#endif
210
211
212struct
213{
214 private:
215
216 template <typename Pred, typename Val> auto
217 impl (Pred&& p, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
218 (hb_deref (hb_forward<Pred> (p)).has (hb_forward<Val> (v)))
219
220 template <typename Pred, typename Val> auto
221 impl (Pred&& p, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
222 (
223 hb_invoke (hb_forward<Pred> (p),
224 hb_forward<Val> (v))
225 )
226
227 public:
228
229 template <typename Pred, typename Val> auto
230 operator () (Pred&& p, Val &&v) const HB_RETURN (bool,
231 impl (hb_forward<Pred> (p),
232 hb_forward<Val> (v),
233 hb_prioritize)
234 )
235}
236HB_FUNCOBJ (hb_has);
237
238struct
239{
240 private:
241
242 template <typename Pred, typename Val> auto
243 impl (Pred&& p, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
244 (
245 hb_has (hb_forward<Pred> (p),
246 hb_forward<Val> (v))
247 )
248
249 template <typename Pred, typename Val> auto
250 impl (Pred&& p, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
251 (
252 hb_forward<Pred> (p) == hb_forward<Val> (v)
253 )
254
255 public:
256
257 template <typename Pred, typename Val> auto
258 operator () (Pred&& p, Val &&v) const HB_RETURN (bool,
259 impl (hb_forward<Pred> (p),
260 hb_forward<Val> (v),
261 hb_prioritize)
262 )
263}
264HB_FUNCOBJ (hb_match);
265
266struct
267{
268 private:
269
270 template <typename Proj, typename Val> auto
271 impl (Proj&& f, Val &&v, hb_priority<2>) const HB_AUTO_RETURN
272 (hb_deref (hb_forward<Proj> (f)).get (hb_forward<Val> (v)))
273
274 template <typename Proj, typename Val> auto
275 impl (Proj&& f, Val &&v, hb_priority<1>) const HB_AUTO_RETURN
276 (
277 hb_invoke (hb_forward<Proj> (f),
278 hb_forward<Val> (v))
279 )
280
281 template <typename Proj, typename Val> auto
282 impl (Proj&& f, Val &&v, hb_priority<0>) const HB_AUTO_RETURN
283 (
284 hb_forward<Proj> (f)[hb_forward<Val> (v)]
285 )
286
287 public:
288
289 template <typename Proj, typename Val> auto
290 operator () (Proj&& f, Val &&v) const HB_AUTO_RETURN
291 (
292 impl (hb_forward<Proj> (f),
293 hb_forward<Val> (v),
294 hb_prioritize)
295 )
296}
297HB_FUNCOBJ (hb_get);
298
299
300template <typename T1, typename T2>
301struct hb_pair_t
302{
303 typedef T1 first_t;
304 typedef T2 second_t;
305 typedef hb_pair_t<T1, T2> pair_t;
306
307 hb_pair_t (T1 a, T2 b) : first (a), second (b) {}
308
309 template <typename Q1, typename Q2,
310 hb_enable_if (hb_is_convertible (T1, Q1) &&
311 hb_is_convertible (T2, T2))>
312 operator hb_pair_t<Q1, Q2> () { return hb_pair_t<Q1, Q2> (first, second); }
313
314 hb_pair_t<T1, T2> reverse () const
315 { return hb_pair_t<T1, T2> (second, first); }
316
317 bool operator == (const pair_t& o) const { return first == o.first && second == o.second; }
318 bool operator != (const pair_t& o) const { return !(*this == o); }
319 bool operator < (const pair_t& o) const { return first < o.first || (first == o.first && second < o.second); }
320 bool operator >= (const pair_t& o) const { return !(*this < o); }
321 bool operator > (const pair_t& o) const { return first > o.first || (first == o.first && second > o.second); }
322 bool operator <= (const pair_t& o) const { return !(*this > o); }
323
324 T1 first;
325 T2 second;
326};
327#define hb_pair_t(T1,T2) hb_pair_t<T1, T2>
328template <typename T1, typename T2> static inline hb_pair_t<T1, T2>
329hb_pair (T1&& a, T2&& b) { return hb_pair_t<T1, T2> (a, b); }
330
331struct
332{
333 template <typename Pair> constexpr typename Pair::first_t
334 operator () (const Pair& pair) const { return pair.first; }
335}
336HB_FUNCOBJ (hb_first);
337
338struct
339{
340 template <typename Pair> constexpr typename Pair::second_t
341 operator () (const Pair& pair) const { return pair.second; }
342}
343HB_FUNCOBJ (hb_second);
344
345/* Note. In min/max impl, we can use hb_type_identity<T> for second argument.
346 * However, that would silently convert between different-signedness integers.
347 * Instead we accept two different types, such that compiler can err if
348 * comparing integers of different signedness. */
349struct
350{
351 template <typename T, typename T2> constexpr auto
352 operator () (T&& a, T2&& b) const HB_AUTO_RETURN
353 (hb_forward<T> (a) <= hb_forward<T2> (b) ? hb_forward<T> (a) : hb_forward<T2> (b))
354}
355HB_FUNCOBJ (hb_min);
356struct
357{
358 template <typename T, typename T2> constexpr auto
359 operator () (T&& a, T2&& b) const HB_AUTO_RETURN
360 (hb_forward<T> (a) >= hb_forward<T2> (b) ? hb_forward<T> (a) : hb_forward<T2> (b))
361}
362HB_FUNCOBJ (hb_max);
363
364
365/*
366 * Bithacks.
367 */
368
369/* Return the number of 1 bits in v. */
370template <typename T>
371static inline HB_CONST_FUNC unsigned int
372hb_popcount (T v)
373{
374#if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
375 if (sizeof (T) <= sizeof (unsigned int))
376 return __builtin_popcount (v);
377
378 if (sizeof (T) <= sizeof (unsigned long))
379 return __builtin_popcountl (v);
380
381 if (sizeof (T) <= sizeof (unsigned long long))
382 return __builtin_popcountll (v);
383#endif
384
385 if (sizeof (T) <= 4)
386 {
387 /* "HACKMEM 169" */
388 uint32_t y;
389 y = (v >> 1) &033333333333;
390 y = v - y - ((y >>1) & 033333333333);
391 return (((y + (y >> 3)) & 030707070707) % 077);
392 }
393
394 if (sizeof (T) == 8)
395 {
396 unsigned int shift = 32;
397 return hb_popcount<uint32_t> ((uint32_t) v) + hb_popcount ((uint32_t) (v >> shift));
398 }
399
400 if (sizeof (T) == 16)
401 {
402 unsigned int shift = 64;
403 return hb_popcount<uint64_t> ((uint64_t) v) + hb_popcount ((uint64_t) (v >> shift));
404 }
405
406 assert (0);
407 return 0; /* Shut up stupid compiler. */
408}
409
410/* Returns the number of bits needed to store number */
411template <typename T>
412static inline HB_CONST_FUNC unsigned int
413hb_bit_storage (T v)
414{
415 if (unlikely (!v)) return 0;
416
417#if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
418 if (sizeof (T) <= sizeof (unsigned int))
419 return sizeof (unsigned int) * 8 - __builtin_clz (v);
420
421 if (sizeof (T) <= sizeof (unsigned long))
422 return sizeof (unsigned long) * 8 - __builtin_clzl (v);
423
424 if (sizeof (T) <= sizeof (unsigned long long))
425 return sizeof (unsigned long long) * 8 - __builtin_clzll (v);
426#endif
427
428#if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
429 if (sizeof (T) <= sizeof (unsigned int))
430 {
431 unsigned long where;
432 _BitScanReverse (&where, v);
433 return 1 + where;
434 }
435# if defined(_WIN64)
436 if (sizeof (T) <= 8)
437 {
438 unsigned long where;
439 _BitScanReverse64 (&where, v);
440 return 1 + where;
441 }
442# endif
443#endif
444
445 if (sizeof (T) <= 4)
446 {
447 /* "bithacks" */
448 const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
449 const unsigned int S[] = {1, 2, 4, 8, 16};
450 unsigned int r = 0;
451 for (int i = 4; i >= 0; i--)
452 if (v & b[i])
453 {
454 v >>= S[i];
455 r |= S[i];
456 }
457 return r + 1;
458 }
459 if (sizeof (T) <= 8)
460 {
461 /* "bithacks" */
462 const uint64_t b[] = {0x2ULL, 0xCULL, 0xF0ULL, 0xFF00ULL, 0xFFFF0000ULL, 0xFFFFFFFF00000000ULL};
463 const unsigned int S[] = {1, 2, 4, 8, 16, 32};
464 unsigned int r = 0;
465 for (int i = 5; i >= 0; i--)
466 if (v & b[i])
467 {
468 v >>= S[i];
469 r |= S[i];
470 }
471 return r + 1;
472 }
473 if (sizeof (T) == 16)
474 {
475 unsigned int shift = 64;
476 return (v >> shift) ? hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift :
477 hb_bit_storage<uint64_t> ((uint64_t) v);
478 }
479
480 assert (0);
481 return 0; /* Shut up stupid compiler. */
482}
483
484/* Returns the number of zero bits in the least significant side of v */
485template <typename T>
486static inline HB_CONST_FUNC unsigned int
487hb_ctz (T v)
488{
489 if (unlikely (!v)) return 0;
490
491#if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
492 if (sizeof (T) <= sizeof (unsigned int))
493 return __builtin_ctz (v);
494
495 if (sizeof (T) <= sizeof (unsigned long))
496 return __builtin_ctzl (v);
497
498 if (sizeof (T) <= sizeof (unsigned long long))
499 return __builtin_ctzll (v);
500#endif
501
502#if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
503 if (sizeof (T) <= sizeof (unsigned int))
504 {
505 unsigned long where;
506 _BitScanForward (&where, v);
507 return where;
508 }
509# if defined(_WIN64)
510 if (sizeof (T) <= 8)
511 {
512 unsigned long where;
513 _BitScanForward64 (&where, v);
514 return where;
515 }
516# endif
517#endif
518
519 if (sizeof (T) <= 4)
520 {
521 /* "bithacks" */
522 unsigned int c = 32;
523 v &= - (int32_t) v;
524 if (v) c--;
525 if (v & 0x0000FFFF) c -= 16;
526 if (v & 0x00FF00FF) c -= 8;
527 if (v & 0x0F0F0F0F) c -= 4;
528 if (v & 0x33333333) c -= 2;
529 if (v & 0x55555555) c -= 1;
530 return c;
531 }
532 if (sizeof (T) <= 8)
533 {
534 /* "bithacks" */
535 unsigned int c = 64;
536 v &= - (int64_t) (v);
537 if (v) c--;
538 if (v & 0x00000000FFFFFFFFULL) c -= 32;
539 if (v & 0x0000FFFF0000FFFFULL) c -= 16;
540 if (v & 0x00FF00FF00FF00FFULL) c -= 8;
541 if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4;
542 if (v & 0x3333333333333333ULL) c -= 2;
543 if (v & 0x5555555555555555ULL) c -= 1;
544 return c;
545 }
546 if (sizeof (T) == 16)
547 {
548 unsigned int shift = 64;
549 return (uint64_t) v ? hb_bit_storage<uint64_t> ((uint64_t) v) :
550 hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift;
551 }
552
553 assert (0);
554 return 0; /* Shut up stupid compiler. */
555}
556
557
558/*
559 * Tiny stuff.
560 */
561
562/* ASCII tag/character handling */
563static inline bool ISALPHA (unsigned char c)
564{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); }
565static inline bool ISALNUM (unsigned char c)
566{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); }
567static inline bool ISSPACE (unsigned char c)
568{ return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; }
569static inline unsigned char TOUPPER (unsigned char c)
570{ return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; }
571static inline unsigned char TOLOWER (unsigned char c)
572{ return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; }
573
574static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)
575{ return (a + (b - 1)) / b; }
576
577
578#undef ARRAY_LENGTH
579template <typename Type, unsigned int n>
580static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }
581/* A const version, but does not detect erratically being called on pointers. */
582#define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
583
584
585static inline int
586hb_memcmp (const void *a, const void *b, unsigned int len)
587{
588 /* It's illegal to pass NULL to memcmp(), even if len is zero.
589 * So, wrap it.
590 * https://sourceware.org/bugzilla/show_bug.cgi?id=23878 */
591 if (unlikely (!len)) return 0;
592 return memcmp (a, b, len);
593}
594
595static inline void *
596hb_memset (void *s, int c, unsigned int n)
597{
598 /* It's illegal to pass NULL to memset(), even if n is zero. */
599 if (unlikely (!n)) return 0;
600 return memset (s, c, n);
601}
602
603static inline bool
604hb_unsigned_mul_overflows (unsigned int count, unsigned int size)
605{
606 return (size > 0) && (count >= ((unsigned int) -1) / size);
607}
608
609static inline unsigned int
610hb_ceil_to_4 (unsigned int v)
611{
612 return ((v - 1) | 3) + 1;
613}
614
615template <typename T> static inline bool
616hb_in_range (T u, T lo, T hi)
617{
618 static_assert (!hb_is_signed<T>::value, "");
619
620 /* The casts below are important as if T is smaller than int,
621 * the subtract results will become a signed int! */
622 return (T)(u - lo) <= (T)(hi - lo);
623}
624template <typename T> static inline bool
625hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2)
626{
627 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2);
628}
629template <typename T> static inline bool
630hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3)
631{
632 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2) || hb_in_range (u, lo3, hi3);
633}
634
635
636/*
637 * Sort and search.
638 */
639template <typename ...Ts>
640static inline void *
641hb_bsearch (const void *key, const void *base,
642 size_t nmemb, size_t size,
643 int (*compar)(const void *_key, const void *_item, Ts... _ds),
644 Ts... ds)
645{
646 int min = 0, max = (int) nmemb - 1;
647 while (min <= max)
648 {
649 int mid = ((unsigned int) min + (unsigned int) max) / 2;
650 const void *p = (const void *) (((const char *) base) + (mid * size));
651 int c = compar (key, p, ds...);
652 if (c < 0)
653 max = mid - 1;
654 else if (c > 0)
655 min = mid + 1;
656 else
657 return (void *) p;
658 }
659 return nullptr;
660}
661
662
663/* From https://github.com/noporpoise/sort_r
664 Feb 5, 2019 (c8c65c1e)
665 Modified to support optional argument using templates */
666
667/* Isaac Turner 29 April 2014 Public Domain */
668
669/*
670hb_qsort function to be exported.
671Parameters:
672 base is the array to be sorted
673 nel is the number of elements in the array
674 width is the size in bytes of each element of the array
675 compar is the comparison function
676 arg (optional) is a pointer to be passed to the comparison function
677
678void hb_qsort(void *base, size_t nel, size_t width,
679 int (*compar)(const void *_a, const void *_b, [void *_arg]),
680 [void *arg]);
681*/
682
683#define SORT_R_SWAP(a,b,tmp) ((tmp) = (a), (a) = (b), (b) = (tmp))
684
685/* swap a and b */
686/* a and b must not be equal! */
687static inline void sort_r_swap(char *__restrict a, char *__restrict b,
688 size_t w)
689{
690 char tmp, *end = a+w;
691 for(; a < end; a++, b++) { SORT_R_SWAP(*a, *b, tmp); }
692}
693
694/* swap a, b iff a>b */
695/* a and b must not be equal! */
696/* __restrict is same as restrict but better support on old machines */
697template <typename ...Ts>
698static inline int sort_r_cmpswap(char *__restrict a,
699 char *__restrict b, size_t w,
700 int (*compar)(const void *_a,
701 const void *_b,
702 Ts... _ds),
703 Ts... ds)
704{
705 if(compar(a, b, ds...) > 0) {
706 sort_r_swap(a, b, w);
707 return 1;
708 }
709 return 0;
710}
711
712/*
713Swap consecutive blocks of bytes of size na and nb starting at memory addr ptr,
714with the smallest swap so that the blocks are in the opposite order. Blocks may
715be internally re-ordered e.g.
716 12345ab -> ab34512
717 123abc -> abc123
718 12abcde -> deabc12
719*/
720static inline void sort_r_swap_blocks(char *ptr, size_t na, size_t nb)
721{
722 if(na > 0 && nb > 0) {
723 if(na > nb) { sort_r_swap(ptr, ptr+na, nb); }
724 else { sort_r_swap(ptr, ptr+nb, na); }
725 }
726}
727
728/* Implement recursive quicksort ourselves */
729/* Note: quicksort is not stable, equivalent values may be swapped */
730template <typename ...Ts>
731static inline void sort_r_simple(void *base, size_t nel, size_t w,
732 int (*compar)(const void *_a,
733 const void *_b,
734 Ts... _ds),
735 Ts... ds)
736{
737 char *b = (char *)base, *end = b + nel*w;
738
739 /* for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
740 printf("\n"); */
741
742 if(nel < 10) {
743 /* Insertion sort for arbitrarily small inputs */
744 char *pi, *pj;
745 for(pi = b+w; pi < end; pi += w) {
746 for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,ds...); pj -= w) {}
747 }
748 }
749 else
750 {
751 /* nel > 9; Quicksort */
752
753 int cmp;
754 char *pl, *ple, *pr, *pre, *pivot;
755 char *last = b+w*(nel-1), *tmp;
756
757 /*
758 Use median of second, middle and second-last items as pivot.
759 First and last may have been swapped with pivot and therefore be extreme
760 */
761 char *l[3];
762 l[0] = b + w;
763 l[1] = b+w*(nel/2);
764 l[2] = last - w;
765
766 /* printf("pivots: %i, %i, %i\n", *(int*)l[0], *(int*)l[1], *(int*)l[2]); */
767
768 if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
769 if(compar(l[1],l[2],ds...) > 0) {
770 SORT_R_SWAP(l[1], l[2], tmp);
771 if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
772 }
773
774 /* swap mid value (l[1]), and last element to put pivot as last element */
775 if(l[1] != last) { sort_r_swap(l[1], last, w); }
776
777 /*
778 pl is the next item on the left to be compared to the pivot
779 pr is the last item on the right that was compared to the pivot
780 ple is the left position to put the next item that equals the pivot
781 ple is the last right position where we put an item that equals the pivot
782 v- end (beyond the array)
783 EEEEEELLLLLLLLuuuuuuuuGGGGGGGEEEEEEEE.
784 ^- b ^- ple ^- pl ^- pr ^- pre ^- last (where the pivot is)
785 Pivot comparison key:
786 E = equal, L = less than, u = unknown, G = greater than, E = equal
787 */
788 pivot = last;
789 ple = pl = b;
790 pre = pr = last;
791
792 /*
793 Strategy:
794 Loop into the list from the left and right at the same time to find:
795 - an item on the left that is greater than the pivot
796 - an item on the right that is less than the pivot
797 Once found, they are swapped and the loop continues.
798 Meanwhile items that are equal to the pivot are moved to the edges of the
799 array.
800 */
801 while(pl < pr) {
802 /* Move left hand items which are equal to the pivot to the far left.
803 break when we find an item that is greater than the pivot */
804 for(; pl < pr; pl += w) {
805 cmp = compar(pl, pivot, ds...);
806 if(cmp > 0) { break; }
807 else if(cmp == 0) {
808 if(ple < pl) { sort_r_swap(ple, pl, w); }
809 ple += w;
810 }
811 }
812 /* break if last batch of left hand items were equal to pivot */
813 if(pl >= pr) { break; }
814 /* Move right hand items which are equal to the pivot to the far right.
815 break when we find an item that is less than the pivot */
816 for(; pl < pr; ) {
817 pr -= w; /* Move right pointer onto an unprocessed item */
818 cmp = compar(pr, pivot, ds...);
819 if(cmp == 0) {
820 pre -= w;
821 if(pr < pre) { sort_r_swap(pr, pre, w); }
822 }
823 else if(cmp < 0) {
824 if(pl < pr) { sort_r_swap(pl, pr, w); }
825 pl += w;
826 break;
827 }
828 }
829 }
830
831 pl = pr; /* pr may have gone below pl */
832
833 /*
834 Now we need to go from: EEELLLGGGGEEEE
835 to: LLLEEEEEEEGGGG
836 Pivot comparison key:
837 E = equal, L = less than, u = unknown, G = greater than, E = equal
838 */
839 sort_r_swap_blocks(b, ple-b, pl-ple);
840 sort_r_swap_blocks(pr, pre-pr, end-pre);
841
842 /*for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
843 printf("\n");*/
844
845 sort_r_simple(b, (pl-ple)/w, w, compar, ds...);
846 sort_r_simple(end-(pre-pr), (pre-pr)/w, w, compar, ds...);
847 }
848}
849
850static inline void
851hb_qsort (void *base, size_t nel, size_t width,
852 int (*compar)(const void *_a, const void *_b))
853{
854#if defined(__OPTIMIZE_SIZE__) && !defined(HB_USE_INTERNAL_QSORT)
855 qsort (base, nel, width, compar);
856#else
857 sort_r_simple (base, nel, width, compar);
858#endif
859}
860
861static inline void
862hb_qsort (void *base, size_t nel, size_t width,
863 int (*compar)(const void *_a, const void *_b, void *_arg),
864 void *arg)
865{
866#ifdef HAVE_GNU_QSORT_R
867 qsort_r (base, nel, width, compar, arg);
868#else
869 sort_r_simple (base, nel, width, compar, arg);
870#endif
871}
872
873
874template <typename T, typename T2, typename T3> static inline void
875hb_stable_sort (T *array, unsigned int len, int(*compar)(const T2 *, const T2 *), T3 *array2)
876{
877 for (unsigned int i = 1; i < len; i++)
878 {
879 unsigned int j = i;
880 while (j && compar (&array[j - 1], &array[i]) > 0)
881 j--;
882 if (i == j)
883 continue;
884 /* Move item i to occupy place for item j, shift what's in between. */
885 {
886 T t = array[i];
887 memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
888 array[j] = t;
889 }
890 if (array2)
891 {
892 T3 t = array2[i];
893 memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T3));
894 array2[j] = t;
895 }
896 }
897}
898
899template <typename T> static inline void
900hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
901{
902 hb_stable_sort (array, len, compar, (int *) nullptr);
903}
904
905static inline hb_bool_t
906hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out)
907{
908 unsigned int v;
909 const char *p = s;
910 const char *end = p + len;
911 if (unlikely (!hb_parse_uint (&p, end, &v, true/* whole buffer */, base)))
912 return false;
913
914 *out = v;
915 return true;
916}
917
918
919/* Operators. */
920
921struct hb_bitwise_and
922{ HB_PARTIALIZE(2);
923 static constexpr bool passthru_left = false;
924 static constexpr bool passthru_right = false;
925 template <typename T> constexpr auto
926 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & b)
927}
928HB_FUNCOBJ (hb_bitwise_and);
929struct hb_bitwise_or
930{ HB_PARTIALIZE(2);
931 static constexpr bool passthru_left = true;
932 static constexpr bool passthru_right = true;
933 template <typename T> constexpr auto
934 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a | b)
935}
936HB_FUNCOBJ (hb_bitwise_or);
937struct hb_bitwise_xor
938{ HB_PARTIALIZE(2);
939 static constexpr bool passthru_left = true;
940 static constexpr bool passthru_right = true;
941 template <typename T> constexpr auto
942 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a ^ b)
943}
944HB_FUNCOBJ (hb_bitwise_xor);
945struct hb_bitwise_sub
946{ HB_PARTIALIZE(2);
947 static constexpr bool passthru_left = true;
948 static constexpr bool passthru_right = false;
949 template <typename T> constexpr auto
950 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & ~b)
951}
952HB_FUNCOBJ (hb_bitwise_sub);
953struct
954{
955 template <typename T> constexpr auto
956 operator () (const T &a) const HB_AUTO_RETURN (~a)
957}
958HB_FUNCOBJ (hb_bitwise_neg);
959
960struct
961{ HB_PARTIALIZE(2);
962 template <typename T, typename T2> constexpr auto
963 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a + b)
964}
965HB_FUNCOBJ (hb_add);
966struct
967{ HB_PARTIALIZE(2);
968 template <typename T, typename T2> constexpr auto
969 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a - b)
970}
971HB_FUNCOBJ (hb_sub);
972struct
973{ HB_PARTIALIZE(2);
974 template <typename T, typename T2> constexpr auto
975 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a * b)
976}
977HB_FUNCOBJ (hb_mul);
978struct
979{ HB_PARTIALIZE(2);
980 template <typename T, typename T2> constexpr auto
981 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a / b)
982}
983HB_FUNCOBJ (hb_div);
984struct
985{ HB_PARTIALIZE(2);
986 template <typename T, typename T2> constexpr auto
987 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a % b)
988}
989HB_FUNCOBJ (hb_mod);
990struct
991{
992 template <typename T> constexpr auto
993 operator () (const T &a) const HB_AUTO_RETURN (+a)
994}
995HB_FUNCOBJ (hb_pos);
996struct
997{
998 template <typename T> constexpr auto
999 operator () (const T &a) const HB_AUTO_RETURN (-a)
1000}
1001HB_FUNCOBJ (hb_neg);
1002struct
1003{
1004 template <typename T> constexpr auto
1005 operator () (T &a) const HB_AUTO_RETURN (++a)
1006}
1007HB_FUNCOBJ (hb_inc);
1008struct
1009{
1010 template <typename T> constexpr auto
1011 operator () (T &a) const HB_AUTO_RETURN (--a)
1012}
1013HB_FUNCOBJ (hb_dec);
1014
1015
1016/* Compiler-assisted vectorization. */
1017
1018/* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))),
1019 * basically a fixed-size bitset. */
1020template <typename elt_t, unsigned int byte_size>
1021struct hb_vector_size_t
1022{
1023 elt_t& operator [] (unsigned int i) { return v[i]; }
1024 const elt_t& operator [] (unsigned int i) const { return v[i]; }
1025
1026 void clear (unsigned char v = 0) { memset (this, v, sizeof (*this)); }
1027
1028 template <typename Op>
1029 hb_vector_size_t process (const Op& op) const
1030 {
1031 hb_vector_size_t r;
1032 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
1033 r.v[i] = op (v[i]);
1034 return r;
1035 }
1036 template <typename Op>
1037 hb_vector_size_t process (const Op& op, const hb_vector_size_t &o) const
1038 {
1039 hb_vector_size_t r;
1040 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
1041 r.v[i] = op (v[i], o.v[i]);
1042 return r;
1043 }
1044 hb_vector_size_t operator | (const hb_vector_size_t &o) const
1045 { return process (hb_bitwise_or, o); }
1046 hb_vector_size_t operator & (const hb_vector_size_t &o) const
1047 { return process (hb_bitwise_and, o); }
1048 hb_vector_size_t operator ^ (const hb_vector_size_t &o) const
1049 { return process (hb_bitwise_xor, o); }
1050 hb_vector_size_t operator ~ () const
1051 { return process (hb_bitwise_neg); }
1052
1053 private:
1054 static_assert (0 == byte_size % sizeof (elt_t), "");
1055 elt_t v[byte_size / sizeof (elt_t)];
1056};
1057
1058
1059#endif /* HB_ALGS_HH */
1060