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);
363struct
364{
365 template <typename T, typename T2, typename T3> constexpr auto
366 operator () (T&& x, T2&& min, T3&& max) const HB_AUTO_RETURN
367 (hb_min (hb_max (hb_forward<T> (x), hb_forward<T2> (min)), hb_forward<T3> (max)))
368}
369HB_FUNCOBJ (hb_clamp);
370
371
372/*
373 * Bithacks.
374 */
375
376/* Return the number of 1 bits in v. */
377template <typename T>
378static inline HB_CONST_FUNC unsigned int
379hb_popcount (T v)
380{
381#if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
382 if (sizeof (T) <= sizeof (unsigned int))
383 return __builtin_popcount (v);
384
385 if (sizeof (T) <= sizeof (unsigned long))
386 return __builtin_popcountl (v);
387
388 if (sizeof (T) <= sizeof (unsigned long long))
389 return __builtin_popcountll (v);
390#endif
391
392 if (sizeof (T) <= 4)
393 {
394 /* "HACKMEM 169" */
395 uint32_t y;
396 y = (v >> 1) &033333333333;
397 y = v - y - ((y >>1) & 033333333333);
398 return (((y + (y >> 3)) & 030707070707) % 077);
399 }
400
401 if (sizeof (T) == 8)
402 {
403 unsigned int shift = 32;
404 return hb_popcount<uint32_t> ((uint32_t) v) + hb_popcount ((uint32_t) (v >> shift));
405 }
406
407 if (sizeof (T) == 16)
408 {
409 unsigned int shift = 64;
410 return hb_popcount<uint64_t> ((uint64_t) v) + hb_popcount ((uint64_t) (v >> shift));
411 }
412
413 assert (0);
414 return 0; /* Shut up stupid compiler. */
415}
416
417/* Returns the number of bits needed to store number */
418template <typename T>
419static inline HB_CONST_FUNC unsigned int
420hb_bit_storage (T v)
421{
422 if (unlikely (!v)) return 0;
423
424#if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
425 if (sizeof (T) <= sizeof (unsigned int))
426 return sizeof (unsigned int) * 8 - __builtin_clz (v);
427
428 if (sizeof (T) <= sizeof (unsigned long))
429 return sizeof (unsigned long) * 8 - __builtin_clzl (v);
430
431 if (sizeof (T) <= sizeof (unsigned long long))
432 return sizeof (unsigned long long) * 8 - __builtin_clzll (v);
433#endif
434
435#if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
436 if (sizeof (T) <= sizeof (unsigned int))
437 {
438 unsigned long where;
439 _BitScanReverse (&where, v);
440 return 1 + where;
441 }
442# if defined(_WIN64)
443 if (sizeof (T) <= 8)
444 {
445 unsigned long where;
446 _BitScanReverse64 (&where, v);
447 return 1 + where;
448 }
449# endif
450#endif
451
452 if (sizeof (T) <= 4)
453 {
454 /* "bithacks" */
455 const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
456 const unsigned int S[] = {1, 2, 4, 8, 16};
457 unsigned int r = 0;
458 for (int i = 4; i >= 0; i--)
459 if (v & b[i])
460 {
461 v >>= S[i];
462 r |= S[i];
463 }
464 return r + 1;
465 }
466 if (sizeof (T) <= 8)
467 {
468 /* "bithacks" */
469 const uint64_t b[] = {0x2ULL, 0xCULL, 0xF0ULL, 0xFF00ULL, 0xFFFF0000ULL, 0xFFFFFFFF00000000ULL};
470 const unsigned int S[] = {1, 2, 4, 8, 16, 32};
471 unsigned int r = 0;
472 for (int i = 5; i >= 0; i--)
473 if (v & b[i])
474 {
475 v >>= S[i];
476 r |= S[i];
477 }
478 return r + 1;
479 }
480 if (sizeof (T) == 16)
481 {
482 unsigned int shift = 64;
483 return (v >> shift) ? hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift :
484 hb_bit_storage<uint64_t> ((uint64_t) v);
485 }
486
487 assert (0);
488 return 0; /* Shut up stupid compiler. */
489}
490
491/* Returns the number of zero bits in the least significant side of v */
492template <typename T>
493static inline HB_CONST_FUNC unsigned int
494hb_ctz (T v)
495{
496 if (unlikely (!v)) return 8 * sizeof (T);
497
498#if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__)
499 if (sizeof (T) <= sizeof (unsigned int))
500 return __builtin_ctz (v);
501
502 if (sizeof (T) <= sizeof (unsigned long))
503 return __builtin_ctzl (v);
504
505 if (sizeof (T) <= sizeof (unsigned long long))
506 return __builtin_ctzll (v);
507#endif
508
509#if (defined(_MSC_VER) && _MSC_VER >= 1500) || (defined(__MINGW32__) && (__GNUC__ < 4))
510 if (sizeof (T) <= sizeof (unsigned int))
511 {
512 unsigned long where;
513 _BitScanForward (&where, v);
514 return where;
515 }
516# if defined(_WIN64)
517 if (sizeof (T) <= 8)
518 {
519 unsigned long where;
520 _BitScanForward64 (&where, v);
521 return where;
522 }
523# endif
524#endif
525
526 if (sizeof (T) <= 4)
527 {
528 /* "bithacks" */
529 unsigned int c = 32;
530 v &= - (int32_t) v;
531 if (v) c--;
532 if (v & 0x0000FFFF) c -= 16;
533 if (v & 0x00FF00FF) c -= 8;
534 if (v & 0x0F0F0F0F) c -= 4;
535 if (v & 0x33333333) c -= 2;
536 if (v & 0x55555555) c -= 1;
537 return c;
538 }
539 if (sizeof (T) <= 8)
540 {
541 /* "bithacks" */
542 unsigned int c = 64;
543 v &= - (int64_t) (v);
544 if (v) c--;
545 if (v & 0x00000000FFFFFFFFULL) c -= 32;
546 if (v & 0x0000FFFF0000FFFFULL) c -= 16;
547 if (v & 0x00FF00FF00FF00FFULL) c -= 8;
548 if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4;
549 if (v & 0x3333333333333333ULL) c -= 2;
550 if (v & 0x5555555555555555ULL) c -= 1;
551 return c;
552 }
553 if (sizeof (T) == 16)
554 {
555 unsigned int shift = 64;
556 return (uint64_t) v ? hb_bit_storage<uint64_t> ((uint64_t) v) :
557 hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift;
558 }
559
560 assert (0);
561 return 0; /* Shut up stupid compiler. */
562}
563
564
565/*
566 * Tiny stuff.
567 */
568
569/* ASCII tag/character handling */
570static inline bool ISALPHA (unsigned char c)
571{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); }
572static inline bool ISALNUM (unsigned char c)
573{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); }
574static inline bool ISSPACE (unsigned char c)
575{ return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; }
576static inline unsigned char TOUPPER (unsigned char c)
577{ return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; }
578static inline unsigned char TOLOWER (unsigned char c)
579{ return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; }
580static inline bool ISHEX (unsigned char c)
581{ return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'); }
582static inline unsigned char TOHEX (uint8_t c)
583{ return (c & 0xF) <= 9 ? (c & 0xF) + '0' : (c & 0xF) + 'a' - 10; }
584static inline uint8_t FROMHEX (unsigned char c)
585{ return (c >= '0' && c <= '9') ? c - '0' : TOLOWER (c) - 'a' + 10; }
586
587static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)
588{ return (a + (b - 1)) / b; }
589
590
591#undef ARRAY_LENGTH
592template <typename Type, unsigned int n>
593static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }
594/* A const version, but does not detect erratically being called on pointers. */
595#define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
596
597
598static inline int
599hb_memcmp (const void *a, const void *b, unsigned int len)
600{
601 /* It's illegal to pass NULL to memcmp(), even if len is zero.
602 * So, wrap it.
603 * https://sourceware.org/bugzilla/show_bug.cgi?id=23878 */
604 if (unlikely (!len)) return 0;
605 return memcmp (a, b, len);
606}
607
608static inline void *
609hb_memset (void *s, int c, unsigned int n)
610{
611 /* It's illegal to pass NULL to memset(), even if n is zero. */
612 if (unlikely (!n)) return 0;
613 return memset (s, c, n);
614}
615
616static inline unsigned int
617hb_ceil_to_4 (unsigned int v)
618{
619 return ((v - 1) | 3) + 1;
620}
621
622template <typename T> static inline bool
623hb_in_range (T u, T lo, T hi)
624{
625 static_assert (!hb_is_signed<T>::value, "");
626
627 /* The casts below are important as if T is smaller than int,
628 * the subtract results will become a signed int! */
629 return (T)(u - lo) <= (T)(hi - lo);
630}
631template <typename T> static inline bool
632hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2)
633{
634 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2);
635}
636template <typename T> static inline bool
637hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3)
638{
639 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2) || hb_in_range (u, lo3, hi3);
640}
641
642
643/*
644 * Overflow checking.
645 */
646
647/* Consider __builtin_mul_overflow use here also */
648static inline bool
649hb_unsigned_mul_overflows (unsigned int count, unsigned int size)
650{
651 return (size > 0) && (count >= ((unsigned int) -1) / size);
652}
653
654
655/*
656 * Sort and search.
657 */
658
659template <typename K, typename V, typename ...Ts>
660static int
661_hb_cmp_method (const void *pkey, const void *pval, Ts... ds)
662{
663 const K& key = * (const K*) pkey;
664 const V& val = * (const V*) pval;
665
666 return val.cmp (key, ds...);
667}
668
669template <typename V, typename K, typename ...Ts>
670static inline bool
671hb_bsearch_impl (unsigned *pos, /* Out */
672 const K& key,
673 V* base, size_t nmemb, size_t stride,
674 int (*compar)(const void *_key, const void *_item, Ts... _ds),
675 Ts... ds)
676{
677 /* This is our *only* bsearch implementation. */
678
679 int min = 0, max = (int) nmemb - 1;
680 while (min <= max)
681 {
682 int mid = ((unsigned int) min + (unsigned int) max) / 2;
683#pragma GCC diagnostic push
684#pragma GCC diagnostic ignored "-Wcast-align"
685 V* p = (V*) (((const char *) base) + (mid * stride));
686#pragma GCC diagnostic pop
687 int c = compar ((const void *) hb_addressof (key), (const void *) p, ds...);
688 if (c < 0)
689 max = mid - 1;
690 else if (c > 0)
691 min = mid + 1;
692 else
693 {
694 *pos = mid;
695 return true;
696 }
697 }
698 *pos = min;
699 return false;
700}
701
702template <typename V, typename K>
703static inline V*
704hb_bsearch (const K& key, V* base,
705 size_t nmemb, size_t stride = sizeof (V),
706 int (*compar)(const void *_key, const void *_item) = _hb_cmp_method<K, V>)
707{
708 unsigned pos;
709#pragma GCC diagnostic push
710#pragma GCC diagnostic ignored "-Wcast-align"
711 return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar) ?
712 (V*) (((const char *) base) + (pos * stride)) : nullptr;
713#pragma GCC diagnostic pop
714}
715template <typename V, typename K, typename ...Ts>
716static inline V*
717hb_bsearch (const K& key, V* base,
718 size_t nmemb, size_t stride,
719 int (*compar)(const void *_key, const void *_item, Ts... _ds),
720 Ts... ds)
721{
722 unsigned pos;
723#pragma GCC diagnostic push
724#pragma GCC diagnostic ignored "-Wcast-align"
725 return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar, ds...) ?
726 (V*) (((const char *) base) + (pos * stride)) : nullptr;
727#pragma GCC diagnostic pop
728}
729
730
731/* From https://github.com/noporpoise/sort_r
732 Feb 5, 2019 (c8c65c1e)
733 Modified to support optional argument using templates */
734
735/* Isaac Turner 29 April 2014 Public Domain */
736
737/*
738hb_qsort function to be exported.
739Parameters:
740 base is the array to be sorted
741 nel is the number of elements in the array
742 width is the size in bytes of each element of the array
743 compar is the comparison function
744 arg (optional) is a pointer to be passed to the comparison function
745
746void hb_qsort(void *base, size_t nel, size_t width,
747 int (*compar)(const void *_a, const void *_b, [void *_arg]),
748 [void *arg]);
749*/
750
751#define SORT_R_SWAP(a,b,tmp) ((tmp) = (a), (a) = (b), (b) = (tmp))
752
753/* swap a and b */
754/* a and b must not be equal! */
755static inline void sort_r_swap(char *__restrict a, char *__restrict b,
756 size_t w)
757{
758 char tmp, *end = a+w;
759 for(; a < end; a++, b++) { SORT_R_SWAP(*a, *b, tmp); }
760}
761
762/* swap a, b iff a>b */
763/* a and b must not be equal! */
764/* __restrict is same as restrict but better support on old machines */
765template <typename ...Ts>
766static inline int sort_r_cmpswap(char *__restrict a,
767 char *__restrict b, size_t w,
768 int (*compar)(const void *_a,
769 const void *_b,
770 Ts... _ds),
771 Ts... ds)
772{
773 if(compar(a, b, ds...) > 0) {
774 sort_r_swap(a, b, w);
775 return 1;
776 }
777 return 0;
778}
779
780/*
781Swap consecutive blocks of bytes of size na and nb starting at memory addr ptr,
782with the smallest swap so that the blocks are in the opposite order. Blocks may
783be internally re-ordered e.g.
784 12345ab -> ab34512
785 123abc -> abc123
786 12abcde -> deabc12
787*/
788static inline void sort_r_swap_blocks(char *ptr, size_t na, size_t nb)
789{
790 if(na > 0 && nb > 0) {
791 if(na > nb) { sort_r_swap(ptr, ptr+na, nb); }
792 else { sort_r_swap(ptr, ptr+nb, na); }
793 }
794}
795
796/* Implement recursive quicksort ourselves */
797/* Note: quicksort is not stable, equivalent values may be swapped */
798template <typename ...Ts>
799static inline void sort_r_simple(void *base, size_t nel, size_t w,
800 int (*compar)(const void *_a,
801 const void *_b,
802 Ts... _ds),
803 Ts... ds)
804{
805 char *b = (char *)base, *end = b + nel*w;
806
807 /* for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
808 printf("\n"); */
809
810 if(nel < 10) {
811 /* Insertion sort for arbitrarily small inputs */
812 char *pi, *pj;
813 for(pi = b+w; pi < end; pi += w) {
814 for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,ds...); pj -= w) {}
815 }
816 }
817 else
818 {
819 /* nel > 9; Quicksort */
820
821 int cmp;
822 char *pl, *ple, *pr, *pre, *pivot;
823 char *last = b+w*(nel-1), *tmp;
824
825 /*
826 Use median of second, middle and second-last items as pivot.
827 First and last may have been swapped with pivot and therefore be extreme
828 */
829 char *l[3];
830 l[0] = b + w;
831 l[1] = b+w*(nel/2);
832 l[2] = last - w;
833
834 /* printf("pivots: %i, %i, %i\n", *(int*)l[0], *(int*)l[1], *(int*)l[2]); */
835
836 if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
837 if(compar(l[1],l[2],ds...) > 0) {
838 SORT_R_SWAP(l[1], l[2], tmp);
839 if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
840 }
841
842 /* swap mid value (l[1]), and last element to put pivot as last element */
843 if(l[1] != last) { sort_r_swap(l[1], last, w); }
844
845 /*
846 pl is the next item on the left to be compared to the pivot
847 pr is the last item on the right that was compared to the pivot
848 ple is the left position to put the next item that equals the pivot
849 ple is the last right position where we put an item that equals the pivot
850 v- end (beyond the array)
851 EEEEEELLLLLLLLuuuuuuuuGGGGGGGEEEEEEEE.
852 ^- b ^- ple ^- pl ^- pr ^- pre ^- last (where the pivot is)
853 Pivot comparison key:
854 E = equal, L = less than, u = unknown, G = greater than, E = equal
855 */
856 pivot = last;
857 ple = pl = b;
858 pre = pr = last;
859
860 /*
861 Strategy:
862 Loop into the list from the left and right at the same time to find:
863 - an item on the left that is greater than the pivot
864 - an item on the right that is less than the pivot
865 Once found, they are swapped and the loop continues.
866 Meanwhile items that are equal to the pivot are moved to the edges of the
867 array.
868 */
869 while(pl < pr) {
870 /* Move left hand items which are equal to the pivot to the far left.
871 break when we find an item that is greater than the pivot */
872 for(; pl < pr; pl += w) {
873 cmp = compar(pl, pivot, ds...);
874 if(cmp > 0) { break; }
875 else if(cmp == 0) {
876 if(ple < pl) { sort_r_swap(ple, pl, w); }
877 ple += w;
878 }
879 }
880 /* break if last batch of left hand items were equal to pivot */
881 if(pl >= pr) { break; }
882 /* Move right hand items which are equal to the pivot to the far right.
883 break when we find an item that is less than the pivot */
884 for(; pl < pr; ) {
885 pr -= w; /* Move right pointer onto an unprocessed item */
886 cmp = compar(pr, pivot, ds...);
887 if(cmp == 0) {
888 pre -= w;
889 if(pr < pre) { sort_r_swap(pr, pre, w); }
890 }
891 else if(cmp < 0) {
892 if(pl < pr) { sort_r_swap(pl, pr, w); }
893 pl += w;
894 break;
895 }
896 }
897 }
898
899 pl = pr; /* pr may have gone below pl */
900
901 /*
902 Now we need to go from: EEELLLGGGGEEEE
903 to: LLLEEEEEEEGGGG
904 Pivot comparison key:
905 E = equal, L = less than, u = unknown, G = greater than, E = equal
906 */
907 sort_r_swap_blocks(b, ple-b, pl-ple);
908 sort_r_swap_blocks(pr, pre-pr, end-pre);
909
910 /*for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
911 printf("\n");*/
912
913 sort_r_simple(b, (pl-ple)/w, w, compar, ds...);
914 sort_r_simple(end-(pre-pr), (pre-pr)/w, w, compar, ds...);
915 }
916}
917
918static inline void
919hb_qsort (void *base, size_t nel, size_t width,
920 int (*compar)(const void *_a, const void *_b))
921{
922#if defined(__OPTIMIZE_SIZE__) && !defined(HB_USE_INTERNAL_QSORT)
923 qsort (base, nel, width, compar);
924#else
925 sort_r_simple (base, nel, width, compar);
926#endif
927}
928
929static inline void
930hb_qsort (void *base, size_t nel, size_t width,
931 int (*compar)(const void *_a, const void *_b, void *_arg),
932 void *arg)
933{
934#ifdef HAVE_GNU_QSORT_R
935 qsort_r (base, nel, width, compar, arg);
936#else
937 sort_r_simple (base, nel, width, compar, arg);
938#endif
939}
940
941
942template <typename T, typename T2, typename T3> static inline void
943hb_stable_sort (T *array, unsigned int len, int(*compar)(const T2 *, const T2 *), T3 *array2)
944{
945 for (unsigned int i = 1; i < len; i++)
946 {
947 unsigned int j = i;
948 while (j && compar (&array[j - 1], &array[i]) > 0)
949 j--;
950 if (i == j)
951 continue;
952 /* Move item i to occupy place for item j, shift what's in between. */
953 {
954 T t = array[i];
955 memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
956 array[j] = t;
957 }
958 if (array2)
959 {
960 T3 t = array2[i];
961 memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T3));
962 array2[j] = t;
963 }
964 }
965}
966
967template <typename T> static inline void
968hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
969{
970 hb_stable_sort (array, len, compar, (int *) nullptr);
971}
972
973static inline hb_bool_t
974hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out)
975{
976 unsigned int v;
977 const char *p = s;
978 const char *end = p + len;
979 if (unlikely (!hb_parse_uint (&p, end, &v, true/* whole buffer */, base)))
980 return false;
981
982 *out = v;
983 return true;
984}
985
986
987/* Operators. */
988
989struct hb_bitwise_and
990{ HB_PARTIALIZE(2);
991 static constexpr bool passthru_left = false;
992 static constexpr bool passthru_right = false;
993 template <typename T> constexpr auto
994 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & b)
995}
996HB_FUNCOBJ (hb_bitwise_and);
997struct hb_bitwise_or
998{ HB_PARTIALIZE(2);
999 static constexpr bool passthru_left = true;
1000 static constexpr bool passthru_right = true;
1001 template <typename T> constexpr auto
1002 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a | b)
1003}
1004HB_FUNCOBJ (hb_bitwise_or);
1005struct hb_bitwise_xor
1006{ HB_PARTIALIZE(2);
1007 static constexpr bool passthru_left = true;
1008 static constexpr bool passthru_right = true;
1009 template <typename T> constexpr auto
1010 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a ^ b)
1011}
1012HB_FUNCOBJ (hb_bitwise_xor);
1013struct hb_bitwise_sub
1014{ HB_PARTIALIZE(2);
1015 static constexpr bool passthru_left = true;
1016 static constexpr bool passthru_right = false;
1017 template <typename T> constexpr auto
1018 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & ~b)
1019}
1020HB_FUNCOBJ (hb_bitwise_sub);
1021struct
1022{
1023 template <typename T> constexpr auto
1024 operator () (const T &a) const HB_AUTO_RETURN (~a)
1025}
1026HB_FUNCOBJ (hb_bitwise_neg);
1027
1028struct
1029{ HB_PARTIALIZE(2);
1030 template <typename T, typename T2> constexpr auto
1031 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a + b)
1032}
1033HB_FUNCOBJ (hb_add);
1034struct
1035{ HB_PARTIALIZE(2);
1036 template <typename T, typename T2> constexpr auto
1037 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a - b)
1038}
1039HB_FUNCOBJ (hb_sub);
1040struct
1041{ HB_PARTIALIZE(2);
1042 template <typename T, typename T2> constexpr auto
1043 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a * b)
1044}
1045HB_FUNCOBJ (hb_mul);
1046struct
1047{ HB_PARTIALIZE(2);
1048 template <typename T, typename T2> constexpr auto
1049 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a / b)
1050}
1051HB_FUNCOBJ (hb_div);
1052struct
1053{ HB_PARTIALIZE(2);
1054 template <typename T, typename T2> constexpr auto
1055 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a % b)
1056}
1057HB_FUNCOBJ (hb_mod);
1058struct
1059{
1060 template <typename T> constexpr auto
1061 operator () (const T &a) const HB_AUTO_RETURN (+a)
1062}
1063HB_FUNCOBJ (hb_pos);
1064struct
1065{
1066 template <typename T> constexpr auto
1067 operator () (const T &a) const HB_AUTO_RETURN (-a)
1068}
1069HB_FUNCOBJ (hb_neg);
1070struct
1071{
1072 template <typename T> constexpr auto
1073 operator () (T &a) const HB_AUTO_RETURN (++a)
1074}
1075HB_FUNCOBJ (hb_inc);
1076struct
1077{
1078 template <typename T> constexpr auto
1079 operator () (T &a) const HB_AUTO_RETURN (--a)
1080}
1081HB_FUNCOBJ (hb_dec);
1082
1083
1084/* Compiler-assisted vectorization. */
1085
1086/* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))),
1087 * basically a fixed-size bitset. */
1088template <typename elt_t, unsigned int byte_size>
1089struct hb_vector_size_t
1090{
1091 elt_t& operator [] (unsigned int i) { return v[i]; }
1092 const elt_t& operator [] (unsigned int i) const { return v[i]; }
1093
1094 void clear (unsigned char v = 0) { memset (this, v, sizeof (*this)); }
1095
1096 template <typename Op>
1097 hb_vector_size_t process (const Op& op) const
1098 {
1099 hb_vector_size_t r;
1100 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
1101 r.v[i] = op (v[i]);
1102 return r;
1103 }
1104 template <typename Op>
1105 hb_vector_size_t process (const Op& op, const hb_vector_size_t &o) const
1106 {
1107 hb_vector_size_t r;
1108 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
1109 r.v[i] = op (v[i], o.v[i]);
1110 return r;
1111 }
1112 hb_vector_size_t operator | (const hb_vector_size_t &o) const
1113 { return process (hb_bitwise_or, o); }
1114 hb_vector_size_t operator & (const hb_vector_size_t &o) const
1115 { return process (hb_bitwise_and, o); }
1116 hb_vector_size_t operator ^ (const hb_vector_size_t &o) const
1117 { return process (hb_bitwise_xor, o); }
1118 hb_vector_size_t operator ~ () const
1119 { return process (hb_bitwise_neg); }
1120
1121 private:
1122 static_assert (0 == byte_size % sizeof (elt_t), "");
1123 elt_t v[byte_size / sizeof (elt_t)];
1124};
1125
1126
1127#endif /* HB_ALGS_HH */
1128