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
51 struct
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 }
57 HB_FUNCOBJ (hb_identity);
58 struct
59 {
60 /* Like identity(), but only retains lvalue-references. Rvalues are returned as rvalues. */
61 template <typename T> constexpr T&
operator ()__anon84fd9ba0020862 operator () (T& v) const { return v; }
63
64 template <typename T> constexpr hb_remove_reference<T>
operator ()__anon84fd9ba0020865 operator () (T&& v) const { return v; }
66 }
67 HB_FUNCOBJ (hb_lidentity);
68 struct
69 {
70 /* Like identity(), but always returns rvalue. */
71 template <typename T> constexpr hb_remove_reference<T>
operator ()__anon84fd9ba0030872 operator () (T&& v) const { return v; }
73 }
74 HB_FUNCOBJ (hb_ridentity);
75
76 struct
77 {
78 template <typename T> constexpr bool
operator ()__anon84fd9ba0040879 operator () (T&& v) const { return bool (hb_forward<T> (v)); }
80 }
81 HB_FUNCOBJ (hb_bool);
82
83 struct
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 }
103 HB_FUNCOBJ (hb_hash);
104
105
106 struct
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 }
135 HB_FUNCOBJ (hb_invoke);
136
137 template <unsigned Pos, typename Appl, typename V>
138 struct hb_partial_t
139 {
hb_partial_thb_partial_t140 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
operator ()hb_partial_t147 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
operator ()hb_partial_t158 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 };
173 template <unsigned Pos=1, typename Appl, typename V>
174 auto hb_partial (Appl&& a, V&& v) HB_AUTO_RETURN
175 (( hb_partial_t<Pos, Appl, V> (a, v) ))
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
212 struct
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 }
236 HB_FUNCOBJ (hb_has);
237
238 struct
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 }
264 HB_FUNCOBJ (hb_match);
265
266 struct
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 }
297 HB_FUNCOBJ (hb_get);
298
299
300 template <typename T1, typename T2>
301 struct hb_pair_t
302 {
303 typedef T1 first_t;
304 typedef T2 second_t;
305 typedef hb_pair_t<T1, T2> pair_t;
306
hb_pair_thb_pair_t307 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))>
operator hb_pair_t<Q1,Q2>hb_pair_t312 operator hb_pair_t<Q1, Q2> () { return hb_pair_t<Q1, Q2> (first, second); }
313
reversehb_pair_t314 hb_pair_t<T1, T2> reverse () const
315 { return hb_pair_t<T1, T2> (second, first); }
316
operator ==hb_pair_t317 bool operator == (const pair_t& o) const { return first == o.first && second == o.second; }
operator !=hb_pair_t318 bool operator != (const pair_t& o) const { return !(*this == o); }
operator <hb_pair_t319 bool operator < (const pair_t& o) const { return first < o.first || (first == o.first && second < o.second); }
operator >=hb_pair_t320 bool operator >= (const pair_t& o) const { return !(*this < o); }
operator >hb_pair_t321 bool operator > (const pair_t& o) const { return first > o.first || (first == o.first && second > o.second); }
operator <=hb_pair_t322 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>
328 template <typename T1, typename T2> static inline hb_pair_t<T1, T2>
hb_pair(T1 && a,T2 && b)329 hb_pair (T1&& a, T2&& b) { return hb_pair_t<T1, T2> (a, b); }
330
331 struct
332 {
333 template <typename Pair> constexpr typename Pair::first_t
operator ()__anon84fd9ba00a08334 operator () (const Pair& pair) const { return pair.first; }
335 }
336 HB_FUNCOBJ (hb_first);
337
338 struct
339 {
340 template <typename Pair> constexpr typename Pair::second_t
operator ()__anon84fd9ba00b08341 operator () (const Pair& pair) const { return pair.second; }
342 }
343 HB_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. */
349 struct
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 }
355 HB_FUNCOBJ (hb_min);
356 struct
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 }
362 HB_FUNCOBJ (hb_max);
363 struct
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 }
369 HB_FUNCOBJ (hb_clamp);
370
371
372 /*
373 * Bithacks.
374 */
375
376 /* Return the number of 1 bits in v. */
377 template <typename T>
378 static inline HB_CONST_FUNC unsigned int
hb_popcount(T v)379 hb_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 */
418 template <typename T>
419 static inline HB_CONST_FUNC unsigned int
hb_bit_storage(T v)420 hb_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 */
492 template <typename T>
493 static inline HB_CONST_FUNC unsigned int
hb_ctz(T v)494 hb_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 */
ISALPHA(unsigned char c)570 static inline bool ISALPHA (unsigned char c)
571 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); }
ISALNUM(unsigned char c)572 static inline bool ISALNUM (unsigned char c)
573 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); }
ISSPACE(unsigned char c)574 static inline bool ISSPACE (unsigned char c)
575 { return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; }
TOUPPER(unsigned char c)576 static inline unsigned char TOUPPER (unsigned char c)
577 { return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; }
TOLOWER(unsigned char c)578 static inline unsigned char TOLOWER (unsigned char c)
579 { return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; }
580
DIV_CEIL(const unsigned int a,unsigned int b)581 static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)
582 { return (a + (b - 1)) / b; }
583
584
585 #undef ARRAY_LENGTH
586 template <typename Type, unsigned int n>
ARRAY_LENGTH(const Type (&)[n])587 static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }
588 /* A const version, but does not detect erratically being called on pointers. */
589 #define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
590
591
592 static inline int
hb_memcmp(const void * a,const void * b,unsigned int len)593 hb_memcmp (const void *a, const void *b, unsigned int len)
594 {
595 /* It's illegal to pass NULL to memcmp(), even if len is zero.
596 * So, wrap it.
597 * https://sourceware.org/bugzilla/show_bug.cgi?id=23878 */
598 if (unlikely (!len)) return 0;
599 return memcmp (a, b, len);
600 }
601
602 static inline void *
hb_memset(void * s,int c,unsigned int n)603 hb_memset (void *s, int c, unsigned int n)
604 {
605 /* It's illegal to pass NULL to memset(), even if n is zero. */
606 if (unlikely (!n)) return 0;
607 return memset (s, c, n);
608 }
609
610 static inline unsigned int
hb_ceil_to_4(unsigned int v)611 hb_ceil_to_4 (unsigned int v)
612 {
613 return ((v - 1) | 3) + 1;
614 }
615
616 template <typename T> static inline bool
hb_in_range(T u,T lo,T hi)617 hb_in_range (T u, T lo, T hi)
618 {
619 static_assert (!hb_is_signed<T>::value, "");
620
621 /* The casts below are important as if T is smaller than int,
622 * the subtract results will become a signed int! */
623 return (T)(u - lo) <= (T)(hi - lo);
624 }
625 template <typename T> static inline bool
hb_in_ranges(T u,T lo1,T hi1,T lo2,T hi2)626 hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2)
627 {
628 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2);
629 }
630 template <typename T> static inline bool
hb_in_ranges(T u,T lo1,T hi1,T lo2,T hi2,T lo3,T hi3)631 hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3)
632 {
633 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2) || hb_in_range (u, lo3, hi3);
634 }
635
636
637 /*
638 * Overflow checking.
639 */
640
641 /* Consider __builtin_mul_overflow use here also */
642 static inline bool
hb_unsigned_mul_overflows(unsigned int count,unsigned int size)643 hb_unsigned_mul_overflows (unsigned int count, unsigned int size)
644 {
645 return (size > 0) && (count >= ((unsigned int) -1) / size);
646 }
647
648 /* Right now we only have one use for signed overflow and as it
649 * is GCC 5.1 > and clang we don't care about its fallback ATM */
650 #ifndef __has_builtin
651 # define __has_builtin(x) 0
652 #endif
653 #if __has_builtin(__builtin_mul_overflow)
654 # define hb_signed_mul_overflows(x, y, result) __builtin_mul_overflow(x, y, &result)
655 #else
656 # define hb_signed_mul_overflows(x, y, result) (result = (x) * (y), false)
657 #endif
658
659
660 /*
661 * Sort and search.
662 */
663
664 template <typename K, typename V, typename ...Ts>
665 static int
_hb_cmp_method(const void * pkey,const void * pval,Ts...ds)666 _hb_cmp_method (const void *pkey, const void *pval, Ts... ds)
667 {
668 const K& key = * (const K*) pkey;
669 const V& val = * (const V*) pval;
670
671 return val.cmp (key, ds...);
672 }
673
674 template <typename V, typename K, typename ...Ts>
675 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)676 hb_bsearch_impl (unsigned *pos, /* Out */
677 const K& key,
678 V* base, size_t nmemb, size_t stride,
679 int (*compar)(const void *_key, const void *_item, Ts... _ds),
680 Ts... ds)
681 {
682 /* This is our *only* bsearch implementation. */
683
684 int min = 0, max = (int) nmemb - 1;
685 while (min <= max)
686 {
687 int mid = ((unsigned int) min + (unsigned int) max) / 2;
688 #pragma GCC diagnostic push
689 #pragma GCC diagnostic ignored "-Wcast-align"
690 V* p = (V*) (((const char *) base) + (mid * stride));
691 #pragma GCC diagnostic pop
692 int c = compar ((const void *) hb_addressof (key), (const void *) p, ds...);
693 if (c < 0)
694 max = mid - 1;
695 else if (c > 0)
696 min = mid + 1;
697 else
698 {
699 *pos = mid;
700 return true;
701 }
702 }
703 *pos = min;
704 return false;
705 }
706
707 template <typename V, typename K>
708 static inline V*
709 hb_bsearch (const K& key, V* base,
710 size_t nmemb, size_t stride = sizeof (V),
711 int (*compar)(const void *_key, const void *_item) = _hb_cmp_method<K, V>)
712 {
713 unsigned pos;
714 #pragma GCC diagnostic push
715 #pragma GCC diagnostic ignored "-Wcast-align"
716 return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar) ?
717 (V*) (((const char *) base) + (pos * stride)) : nullptr;
718 #pragma GCC diagnostic pop
719 }
720 template <typename V, typename K, typename ...Ts>
721 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)722 hb_bsearch (const K& key, V* base,
723 size_t nmemb, size_t stride,
724 int (*compar)(const void *_key, const void *_item, Ts... _ds),
725 Ts... ds)
726 {
727 unsigned pos;
728 #pragma GCC diagnostic push
729 #pragma GCC diagnostic ignored "-Wcast-align"
730 return hb_bsearch_impl (&pos, key, base, nmemb, stride, compar, ds...) ?
731 (V*) (((const char *) base) + (pos * stride)) : nullptr;
732 #pragma GCC diagnostic pop
733 }
734
735
736 /* From https://github.com/noporpoise/sort_r
737 Feb 5, 2019 (c8c65c1e)
738 Modified to support optional argument using templates */
739
740 /* Isaac Turner 29 April 2014 Public Domain */
741
742 /*
743 hb_qsort function to be exported.
744 Parameters:
745 base is the array to be sorted
746 nel is the number of elements in the array
747 width is the size in bytes of each element of the array
748 compar is the comparison function
749 arg (optional) is a pointer to be passed to the comparison function
750
751 void hb_qsort(void *base, size_t nel, size_t width,
752 int (*compar)(const void *_a, const void *_b, [void *_arg]),
753 [void *arg]);
754 */
755
756 #define SORT_R_SWAP(a,b,tmp) ((tmp) = (a), (a) = (b), (b) = (tmp))
757
758 /* swap a and b */
759 /* a and b must not be equal! */
sort_r_swap(char * __restrict a,char * __restrict b,size_t w)760 static inline void sort_r_swap(char *__restrict a, char *__restrict b,
761 size_t w)
762 {
763 char tmp, *end = a+w;
764 for(; a < end; a++, b++) { SORT_R_SWAP(*a, *b, tmp); }
765 }
766
767 /* swap a, b iff a>b */
768 /* a and b must not be equal! */
769 /* __restrict is same as restrict but better support on old machines */
770 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)771 static inline int sort_r_cmpswap(char *__restrict a,
772 char *__restrict b, size_t w,
773 int (*compar)(const void *_a,
774 const void *_b,
775 Ts... _ds),
776 Ts... ds)
777 {
778 if(compar(a, b, ds...) > 0) {
779 sort_r_swap(a, b, w);
780 return 1;
781 }
782 return 0;
783 }
784
785 /*
786 Swap consecutive blocks of bytes of size na and nb starting at memory addr ptr,
787 with the smallest swap so that the blocks are in the opposite order. Blocks may
788 be internally re-ordered e.g.
789 12345ab -> ab34512
790 123abc -> abc123
791 12abcde -> deabc12
792 */
sort_r_swap_blocks(char * ptr,size_t na,size_t nb)793 static inline void sort_r_swap_blocks(char *ptr, size_t na, size_t nb)
794 {
795 if(na > 0 && nb > 0) {
796 if(na > nb) { sort_r_swap(ptr, ptr+na, nb); }
797 else { sort_r_swap(ptr, ptr+nb, na); }
798 }
799 }
800
801 /* Implement recursive quicksort ourselves */
802 /* Note: quicksort is not stable, equivalent values may be swapped */
803 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)804 static inline void sort_r_simple(void *base, size_t nel, size_t w,
805 int (*compar)(const void *_a,
806 const void *_b,
807 Ts... _ds),
808 Ts... ds)
809 {
810 char *b = (char *)base, *end = b + nel*w;
811
812 /* for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
813 printf("\n"); */
814
815 if(nel < 10) {
816 /* Insertion sort for arbitrarily small inputs */
817 char *pi, *pj;
818 for(pi = b+w; pi < end; pi += w) {
819 for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,ds...); pj -= w) {}
820 }
821 }
822 else
823 {
824 /* nel > 9; Quicksort */
825
826 int cmp;
827 char *pl, *ple, *pr, *pre, *pivot;
828 char *last = b+w*(nel-1), *tmp;
829
830 /*
831 Use median of second, middle and second-last items as pivot.
832 First and last may have been swapped with pivot and therefore be extreme
833 */
834 char *l[3];
835 l[0] = b + w;
836 l[1] = b+w*(nel/2);
837 l[2] = last - w;
838
839 /* printf("pivots: %i, %i, %i\n", *(int*)l[0], *(int*)l[1], *(int*)l[2]); */
840
841 if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
842 if(compar(l[1],l[2],ds...) > 0) {
843 SORT_R_SWAP(l[1], l[2], tmp);
844 if(compar(l[0],l[1],ds...) > 0) { SORT_R_SWAP(l[0], l[1], tmp); }
845 }
846
847 /* swap mid value (l[1]), and last element to put pivot as last element */
848 if(l[1] != last) { sort_r_swap(l[1], last, w); }
849
850 /*
851 pl is the next item on the left to be compared to the pivot
852 pr is the last item on the right that was compared to the pivot
853 ple is the left position to put the next item that equals the pivot
854 ple is the last right position where we put an item that equals the pivot
855 v- end (beyond the array)
856 EEEEEELLLLLLLLuuuuuuuuGGGGGGGEEEEEEEE.
857 ^- b ^- ple ^- pl ^- pr ^- pre ^- last (where the pivot is)
858 Pivot comparison key:
859 E = equal, L = less than, u = unknown, G = greater than, E = equal
860 */
861 pivot = last;
862 ple = pl = b;
863 pre = pr = last;
864
865 /*
866 Strategy:
867 Loop into the list from the left and right at the same time to find:
868 - an item on the left that is greater than the pivot
869 - an item on the right that is less than the pivot
870 Once found, they are swapped and the loop continues.
871 Meanwhile items that are equal to the pivot are moved to the edges of the
872 array.
873 */
874 while(pl < pr) {
875 /* Move left hand items which are equal to the pivot to the far left.
876 break when we find an item that is greater than the pivot */
877 for(; pl < pr; pl += w) {
878 cmp = compar(pl, pivot, ds...);
879 if(cmp > 0) { break; }
880 else if(cmp == 0) {
881 if(ple < pl) { sort_r_swap(ple, pl, w); }
882 ple += w;
883 }
884 }
885 /* break if last batch of left hand items were equal to pivot */
886 if(pl >= pr) { break; }
887 /* Move right hand items which are equal to the pivot to the far right.
888 break when we find an item that is less than the pivot */
889 for(; pl < pr; ) {
890 pr -= w; /* Move right pointer onto an unprocessed item */
891 cmp = compar(pr, pivot, ds...);
892 if(cmp == 0) {
893 pre -= w;
894 if(pr < pre) { sort_r_swap(pr, pre, w); }
895 }
896 else if(cmp < 0) {
897 if(pl < pr) { sort_r_swap(pl, pr, w); }
898 pl += w;
899 break;
900 }
901 }
902 }
903
904 pl = pr; /* pr may have gone below pl */
905
906 /*
907 Now we need to go from: EEELLLGGGGEEEE
908 to: LLLEEEEEEEGGGG
909 Pivot comparison key:
910 E = equal, L = less than, u = unknown, G = greater than, E = equal
911 */
912 sort_r_swap_blocks(b, ple-b, pl-ple);
913 sort_r_swap_blocks(pr, pre-pr, end-pre);
914
915 /*for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
916 printf("\n");*/
917
918 sort_r_simple(b, (pl-ple)/w, w, compar, ds...);
919 sort_r_simple(end-(pre-pr), (pre-pr)/w, w, compar, ds...);
920 }
921 }
922
923 static inline void
hb_qsort(void * base,size_t nel,size_t width,int (* compar)(const void * _a,const void * _b))924 hb_qsort (void *base, size_t nel, size_t width,
925 int (*compar)(const void *_a, const void *_b))
926 {
927 #if defined(__OPTIMIZE_SIZE__) && !defined(HB_USE_INTERNAL_QSORT)
928 qsort (base, nel, width, compar);
929 #else
930 sort_r_simple (base, nel, width, compar);
931 #endif
932 }
933
934 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)935 hb_qsort (void *base, size_t nel, size_t width,
936 int (*compar)(const void *_a, const void *_b, void *_arg),
937 void *arg)
938 {
939 #ifdef HAVE_GNU_QSORT_R
940 qsort_r (base, nel, width, compar, arg);
941 #else
942 sort_r_simple (base, nel, width, compar, arg);
943 #endif
944 }
945
946
947 template <typename T, typename T2, typename T3> static inline void
hb_stable_sort(T * array,unsigned int len,int (* compar)(const T2 *,const T2 *),T3 * array2)948 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T2 *, const T2 *), T3 *array2)
949 {
950 for (unsigned int i = 1; i < len; i++)
951 {
952 unsigned int j = i;
953 while (j && compar (&array[j - 1], &array[i]) > 0)
954 j--;
955 if (i == j)
956 continue;
957 /* Move item i to occupy place for item j, shift what's in between. */
958 {
959 T t = array[i];
960 memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
961 array[j] = t;
962 }
963 if (array2)
964 {
965 T3 t = array2[i];
966 memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T3));
967 array2[j] = t;
968 }
969 }
970 }
971
972 template <typename T> static inline void
hb_stable_sort(T * array,unsigned int len,int (* compar)(const T *,const T *))973 hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
974 {
975 hb_stable_sort (array, len, compar, (int *) nullptr);
976 }
977
978 static inline hb_bool_t
hb_codepoint_parse(const char * s,unsigned int len,int base,hb_codepoint_t * out)979 hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out)
980 {
981 unsigned int v;
982 const char *p = s;
983 const char *end = p + len;
984 if (unlikely (!hb_parse_uint (&p, end, &v, true/* whole buffer */, base)))
985 return false;
986
987 *out = v;
988 return true;
989 }
990
991
992 /* Operators. */
993
994 struct hb_bitwise_and
995 { HB_PARTIALIZE(2);
996 static constexpr bool passthru_left = false;
997 static constexpr bool passthru_right = false;
998 template <typename T> constexpr auto
999 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & b)
1000 }
1001 HB_FUNCOBJ (hb_bitwise_and);
1002 struct hb_bitwise_or
1003 { HB_PARTIALIZE(2);
1004 static constexpr bool passthru_left = true;
1005 static constexpr bool passthru_right = true;
1006 template <typename T> constexpr auto
1007 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a | b)
1008 }
1009 HB_FUNCOBJ (hb_bitwise_or);
1010 struct hb_bitwise_xor
1011 { HB_PARTIALIZE(2);
1012 static constexpr bool passthru_left = true;
1013 static constexpr bool passthru_right = true;
1014 template <typename T> constexpr auto
1015 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a ^ b)
1016 }
1017 HB_FUNCOBJ (hb_bitwise_xor);
1018 struct hb_bitwise_sub
1019 { HB_PARTIALIZE(2);
1020 static constexpr bool passthru_left = true;
1021 static constexpr bool passthru_right = false;
1022 template <typename T> constexpr auto
1023 operator () (const T &a, const T &b) const HB_AUTO_RETURN (a & ~b)
1024 }
1025 HB_FUNCOBJ (hb_bitwise_sub);
1026 struct
1027 {
1028 template <typename T> constexpr auto
1029 operator () (const T &a) const HB_AUTO_RETURN (~a)
1030 }
1031 HB_FUNCOBJ (hb_bitwise_neg);
1032
1033 struct
1034 { HB_PARTIALIZE(2);
1035 template <typename T, typename T2> constexpr auto
1036 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a + b)
1037 }
1038 HB_FUNCOBJ (hb_add);
1039 struct
1040 { HB_PARTIALIZE(2);
1041 template <typename T, typename T2> constexpr auto
1042 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a - b)
1043 }
1044 HB_FUNCOBJ (hb_sub);
1045 struct
1046 { HB_PARTIALIZE(2);
1047 template <typename T, typename T2> constexpr auto
1048 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a * b)
1049 }
1050 HB_FUNCOBJ (hb_mul);
1051 struct
1052 { HB_PARTIALIZE(2);
1053 template <typename T, typename T2> constexpr auto
1054 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a / b)
1055 }
1056 HB_FUNCOBJ (hb_div);
1057 struct
1058 { HB_PARTIALIZE(2);
1059 template <typename T, typename T2> constexpr auto
1060 operator () (const T &a, const T2 &b) const HB_AUTO_RETURN (a % b)
1061 }
1062 HB_FUNCOBJ (hb_mod);
1063 struct
1064 {
1065 template <typename T> constexpr auto
1066 operator () (const T &a) const HB_AUTO_RETURN (+a)
1067 }
1068 HB_FUNCOBJ (hb_pos);
1069 struct
1070 {
1071 template <typename T> constexpr auto
1072 operator () (const T &a) const HB_AUTO_RETURN (-a)
1073 }
1074 HB_FUNCOBJ (hb_neg);
1075 struct
1076 {
1077 template <typename T> constexpr auto
1078 operator () (T &a) const HB_AUTO_RETURN (++a)
1079 }
1080 HB_FUNCOBJ (hb_inc);
1081 struct
1082 {
1083 template <typename T> constexpr auto
1084 operator () (T &a) const HB_AUTO_RETURN (--a)
1085 }
1086 HB_FUNCOBJ (hb_dec);
1087
1088
1089 /* Compiler-assisted vectorization. */
1090
1091 /* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))),
1092 * basically a fixed-size bitset. */
1093 template <typename elt_t, unsigned int byte_size>
1094 struct hb_vector_size_t
1095 {
operator []hb_vector_size_t1096 elt_t& operator [] (unsigned int i) { return v[i]; }
operator []hb_vector_size_t1097 const elt_t& operator [] (unsigned int i) const { return v[i]; }
1098
clearhb_vector_size_t1099 void clear (unsigned char v = 0) { memset (this, v, sizeof (*this)); }
1100
1101 template <typename Op>
processhb_vector_size_t1102 hb_vector_size_t process (const Op& op) const
1103 {
1104 hb_vector_size_t r;
1105 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
1106 r.v[i] = op (v[i]);
1107 return r;
1108 }
1109 template <typename Op>
processhb_vector_size_t1110 hb_vector_size_t process (const Op& op, const hb_vector_size_t &o) const
1111 {
1112 hb_vector_size_t r;
1113 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++)
1114 r.v[i] = op (v[i], o.v[i]);
1115 return r;
1116 }
operator |hb_vector_size_t1117 hb_vector_size_t operator | (const hb_vector_size_t &o) const
1118 { return process (hb_bitwise_or, o); }
operator &hb_vector_size_t1119 hb_vector_size_t operator & (const hb_vector_size_t &o) const
1120 { return process (hb_bitwise_and, o); }
operator ^hb_vector_size_t1121 hb_vector_size_t operator ^ (const hb_vector_size_t &o) const
1122 { return process (hb_bitwise_xor, o); }
operator ~hb_vector_size_t1123 hb_vector_size_t operator ~ () const
1124 { return process (hb_bitwise_neg); }
1125
1126 private:
1127 static_assert (0 == byte_size % sizeof (elt_t), "");
1128 elt_t v[byte_size / sizeof (elt_t)];
1129 };
1130
1131
1132 #endif /* HB_ALGS_HH */
1133