1/*
2 * Copyright © 2017 Google, Inc.
3 *
4 * This is part of HarfBuzz, a text shaping library.
5 *
6 * Permission is hereby granted, without written agreement and without
7 * license or royalty fees, to use, copy, modify, and distribute this
8 * software and its documentation for any purpose, provided that the
9 * above copyright notice and the following two paragraphs appear in
10 * all copies of this software.
11 *
12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
16 * DAMAGE.
17 *
18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
23 *
24 * Google Author(s): Behdad Esfahbod
25 */
26
27#ifndef HB_DSALGS_HH
28#define HB_DSALGS_HH
29
30#include "hb.hh"
31
32
33/* Void! For when we need a expression-type of void. */
34typedef const struct _hb_void_t *hb_void_t;
35#define HB_VOID ((const _hb_void_t *) nullptr)
36
37
38/*
39 * Bithacks.
40 */
41
42/* Return the number of 1 bits in v. */
43template <typename T>
44static inline HB_CONST_FUNC unsigned int
45hb_popcount (T v)
46{
47#if (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) && defined(__OPTIMIZE__)
48 if (sizeof (T) <= sizeof (unsigned int))
49 return __builtin_popcount (v);
50
51 if (sizeof (T) <= sizeof (unsigned long))
52 return __builtin_popcountl (v);
53
54 if (sizeof (T) <= sizeof (unsigned long long))
55 return __builtin_popcountll (v);
56#endif
57
58 if (sizeof (T) <= 4)
59 {
60 /* "HACKMEM 169" */
61 uint32_t y;
62 y = (v >> 1) &033333333333;
63 y = v - y - ((y >>1) & 033333333333);
64 return (((y + (y >> 3)) & 030707070707) % 077);
65 }
66
67 if (sizeof (T) == 8)
68 {
69 unsigned int shift = 32;
70 return hb_popcount<uint32_t> ((uint32_t) v) + hb_popcount ((uint32_t) (v >> shift));
71 }
72
73 if (sizeof (T) == 16)
74 {
75 unsigned int shift = 64;
76 return hb_popcount<uint64_t> ((uint64_t) v) + hb_popcount ((uint64_t) (v >> shift));
77 }
78
79 assert (0);
80 return 0; /* Shut up stupid compiler. */
81}
82
83/* Returns the number of bits needed to store number */
84template <typename T>
85static inline HB_CONST_FUNC unsigned int
86hb_bit_storage (T v)
87{
88 if (unlikely (!v)) return 0;
89
90#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__)
91 if (sizeof (T) <= sizeof (unsigned int))
92 return sizeof (unsigned int) * 8 - __builtin_clz (v);
93
94 if (sizeof (T) <= sizeof (unsigned long))
95 return sizeof (unsigned long) * 8 - __builtin_clzl (v);
96
97 if (sizeof (T) <= sizeof (unsigned long long))
98 return sizeof (unsigned long long) * 8 - __builtin_clzll (v);
99#endif
100
101#if (defined(_MSC_VER) && _MSC_VER >= 1500) || defined(__MINGW32__)
102 if (sizeof (T) <= sizeof (unsigned int))
103 {
104 unsigned long where;
105 _BitScanReverse (&where, v);
106 return 1 + where;
107 }
108# if _WIN64
109 if (sizeof (T) <= 8)
110 {
111 unsigned long where;
112 _BitScanReverse64 (&where, v);
113 return 1 + where;
114 }
115# endif
116#endif
117
118 if (sizeof (T) <= 4)
119 {
120 /* "bithacks" */
121 const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
122 const unsigned int S[] = {1, 2, 4, 8, 16};
123 unsigned int r = 0;
124 for (int i = 4; i >= 0; i--)
125 if (v & b[i])
126 {
127 v >>= S[i];
128 r |= S[i];
129 }
130 return r + 1;
131 }
132 if (sizeof (T) <= 8)
133 {
134 /* "bithacks" */
135 const uint64_t b[] = {0x2ULL, 0xCULL, 0xF0ULL, 0xFF00ULL, 0xFFFF0000ULL, 0xFFFFFFFF00000000ULL};
136 const unsigned int S[] = {1, 2, 4, 8, 16, 32};
137 unsigned int r = 0;
138 for (int i = 5; i >= 0; i--)
139 if (v & b[i])
140 {
141 v >>= S[i];
142 r |= S[i];
143 }
144 return r + 1;
145 }
146 if (sizeof (T) == 16)
147 {
148 unsigned int shift = 64;
149 return (v >> shift) ? hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift :
150 hb_bit_storage<uint64_t> ((uint64_t) v);
151 }
152
153 assert (0);
154 return 0; /* Shut up stupid compiler. */
155}
156
157/* Returns the number of zero bits in the least significant side of v */
158template <typename T>
159static inline HB_CONST_FUNC unsigned int
160hb_ctz (T v)
161{
162 if (unlikely (!v)) return 0;
163
164#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__)
165 if (sizeof (T) <= sizeof (unsigned int))
166 return __builtin_ctz (v);
167
168 if (sizeof (T) <= sizeof (unsigned long))
169 return __builtin_ctzl (v);
170
171 if (sizeof (T) <= sizeof (unsigned long long))
172 return __builtin_ctzll (v);
173#endif
174
175#if (defined(_MSC_VER) && _MSC_VER >= 1500) || defined(__MINGW32__)
176 if (sizeof (T) <= sizeof (unsigned int))
177 {
178 unsigned long where;
179 _BitScanForward (&where, v);
180 return where;
181 }
182# if _WIN64
183 if (sizeof (T) <= 8)
184 {
185 unsigned long where;
186 _BitScanForward64 (&where, v);
187 return where;
188 }
189# endif
190#endif
191
192 if (sizeof (T) <= 4)
193 {
194 /* "bithacks" */
195 unsigned int c = 32;
196 v &= - (int32_t) v;
197 if (v) c--;
198 if (v & 0x0000FFFF) c -= 16;
199 if (v & 0x00FF00FF) c -= 8;
200 if (v & 0x0F0F0F0F) c -= 4;
201 if (v & 0x33333333) c -= 2;
202 if (v & 0x55555555) c -= 1;
203 return c;
204 }
205 if (sizeof (T) <= 8)
206 {
207 /* "bithacks" */
208 unsigned int c = 64;
209 v &= - (int64_t) (v);
210 if (v) c--;
211 if (v & 0x00000000FFFFFFFFULL) c -= 32;
212 if (v & 0x0000FFFF0000FFFFULL) c -= 16;
213 if (v & 0x00FF00FF00FF00FFULL) c -= 8;
214 if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4;
215 if (v & 0x3333333333333333ULL) c -= 2;
216 if (v & 0x5555555555555555ULL) c -= 1;
217 return c;
218 }
219 if (sizeof (T) == 16)
220 {
221 unsigned int shift = 64;
222 return (uint64_t) v ? hb_bit_storage<uint64_t> ((uint64_t) v) :
223 hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift;
224 }
225
226 assert (0);
227 return 0; /* Shut up stupid compiler. */
228}
229
230
231/*
232 * Tiny stuff.
233 */
234
235/* ASCII tag/character handling */
236static inline bool ISALPHA (unsigned char c)
237{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); }
238static inline bool ISALNUM (unsigned char c)
239{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); }
240static inline bool ISSPACE (unsigned char c)
241{ return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; }
242static inline unsigned char TOUPPER (unsigned char c)
243{ return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; }
244static inline unsigned char TOLOWER (unsigned char c)
245{ return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; }
246
247#undef MIN
248template <typename Type>
249static inline Type MIN (const Type &a, const Type &b) { return a < b ? a : b; }
250
251#undef MAX
252template <typename Type>
253static inline Type MAX (const Type &a, const Type &b) { return a > b ? a : b; }
254
255static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)
256{ return (a + (b - 1)) / b; }
257
258
259#undef ARRAY_LENGTH
260template <typename Type, unsigned int n>
261static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }
262/* A const version, but does not detect erratically being called on pointers. */
263#define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
264
265static inline bool
266hb_unsigned_mul_overflows (unsigned int count, unsigned int size)
267{
268 return (size > 0) && (count >= ((unsigned int) -1) / size);
269}
270
271static inline unsigned int
272hb_ceil_to_4 (unsigned int v)
273{
274 return ((v - 1) | 3) + 1;
275}
276
277template <typename T> class hb_assert_unsigned_t;
278template <> class hb_assert_unsigned_t<unsigned char> {};
279template <> class hb_assert_unsigned_t<unsigned short> {};
280template <> class hb_assert_unsigned_t<unsigned int> {};
281template <> class hb_assert_unsigned_t<unsigned long> {};
282
283template <typename T> static inline bool
284hb_in_range (T u, T lo, T hi)
285{
286 /* The sizeof() is here to force template instantiation.
287 * I'm sure there are better ways to do this but can't think of
288 * one right now. Declaring a variable won't work as HB_UNUSED
289 * is unusable on some platforms and unused types are less likely
290 * to generate a warning than unused variables. */
291 static_assert ((sizeof (hb_assert_unsigned_t<T>) >= 0), "");
292
293 /* The casts below are important as if T is smaller than int,
294 * the subtract results will become a signed int! */
295 return (T)(u - lo) <= (T)(hi - lo);
296}
297template <typename T> static inline bool
298hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2)
299{
300 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2);
301}
302template <typename T> static inline bool
303hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3)
304{
305 return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2) || hb_in_range (u, lo3, hi3);
306}
307
308
309/*
310 * Sort and search.
311 */
312
313static inline void *
314hb_bsearch_r (const void *key, const void *base,
315 size_t nmemb, size_t size,
316 int (*compar)(const void *_key, const void *_item, void *_arg),
317 void *arg)
318{
319 int min = 0, max = (int) nmemb - 1;
320 while (min <= max)
321 {
322 int mid = (min + max) / 2;
323 const void *p = (const void *) (((const char *) base) + (mid * size));
324 int c = compar (key, p, arg);
325 if (c < 0)
326 max = mid - 1;
327 else if (c > 0)
328 min = mid + 1;
329 else
330 return (void *) p;
331 }
332 return nullptr;
333}
334
335
336/* From https://github.com/noporpoise/sort_r */
337
338/* Isaac Turner 29 April 2014 Public Domain */
339
340/*
341
342hb_sort_r function to be exported.
343
344Parameters:
345 base is the array to be sorted
346 nel is the number of elements in the array
347 width is the size in bytes of each element of the array
348 compar is the comparison function
349 arg is a pointer to be passed to the comparison function
350
351void hb_sort_r(void *base, size_t nel, size_t width,
352 int (*compar)(const void *_a, const void *_b, void *_arg),
353 void *arg);
354*/
355
356
357/* swap a, b iff a>b */
358/* __restrict is same as restrict but better support on old machines */
359static int sort_r_cmpswap(char *__restrict a, char *__restrict b, size_t w,
360 int (*compar)(const void *_a, const void *_b,
361 void *_arg),
362 void *arg)
363{
364 char tmp, *end = a+w;
365 if(compar(a, b, arg) > 0) {
366 for(; a < end; a++, b++) { tmp = *a; *a = *b; *b = tmp; }
367 return 1;
368 }
369 return 0;
370}
371
372/* Note: quicksort is not stable, equivalent values may be swapped */
373static inline void sort_r_simple(void *base, size_t nel, size_t w,
374 int (*compar)(const void *_a, const void *_b,
375 void *_arg),
376 void *arg)
377{
378 char *b = (char *)base, *end = b + nel*w;
379 if(nel < 7) {
380 /* Insertion sort for arbitrarily small inputs */
381 char *pi, *pj;
382 for(pi = b+w; pi < end; pi += w) {
383 for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,arg); pj -= w) {}
384 }
385 }
386 else
387 {
388 /* nel > 6; Quicksort */
389
390 /* Use median of first, middle and last items as pivot */
391 char *x, *y, *xend, ch;
392 char *pl, *pr;
393 char *last = b+w*(nel-1), *tmp;
394 char *l[3];
395 l[0] = b;
396 l[1] = b+w*(nel/2);
397 l[2] = last;
398
399 if(compar(l[0],l[1],arg) > 0) { tmp=l[0]; l[0]=l[1]; l[1]=tmp; }
400 if(compar(l[1],l[2],arg) > 0) {
401 tmp=l[1]; l[1]=l[2]; l[2]=tmp; /* swap(l[1],l[2]) */
402 if(compar(l[0],l[1],arg) > 0) { tmp=l[0]; l[0]=l[1]; l[1]=tmp; }
403 }
404
405 /* swap l[id], l[2] to put pivot as last element */
406 for(x = l[1], y = last, xend = x+w; x<xend; x++, y++) {
407 ch = *x; *x = *y; *y = ch;
408 }
409
410 pl = b;
411 pr = last;
412
413 while(pl < pr) {
414 for(; pl < pr; pl += w) {
415 if(sort_r_cmpswap(pl, pr, w, compar, arg)) {
416 pr -= w; /* pivot now at pl */
417 break;
418 }
419 }
420 for(; pl < pr; pr -= w) {
421 if(sort_r_cmpswap(pl, pr, w, compar, arg)) {
422 pl += w; /* pivot now at pr */
423 break;
424 }
425 }
426 }
427
428 sort_r_simple(b, (pl-b)/w, w, compar, arg);
429 sort_r_simple(pl+w, (end-(pl+w))/w, w, compar, arg);
430 }
431}
432
433static inline void hb_sort_r(void *base, size_t nel, size_t width,
434 int (*compar)(const void *_a, const void *_b, void *_arg),
435 void *arg)
436{
437 sort_r_simple(base, nel, width, compar, arg);
438}
439
440
441template <typename T, typename T2> static inline void
442hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *), T2 *array2)
443{
444 for (unsigned int i = 1; i < len; i++)
445 {
446 unsigned int j = i;
447 while (j && compar (&array[j - 1], &array[i]) > 0)
448 j--;
449 if (i == j)
450 continue;
451 /* Move item i to occupy place for item j, shift what's in between. */
452 {
453 T t = array[i];
454 memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
455 array[j] = t;
456 }
457 if (array2)
458 {
459 T2 t = array2[i];
460 memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T2));
461 array2[j] = t;
462 }
463 }
464}
465
466template <typename T> static inline void
467hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
468{
469 hb_stable_sort (array, len, compar, (int *) nullptr);
470}
471
472static inline hb_bool_t
473hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out)
474{
475 /* Pain because we don't know whether s is nul-terminated. */
476 char buf[64];
477 len = MIN (ARRAY_LENGTH (buf) - 1, len);
478 strncpy (buf, s, len);
479 buf[len] = '\0';
480
481 char *end;
482 errno = 0;
483 unsigned long v = strtoul (buf, &end, base);
484 if (errno) return false;
485 if (*end) return false;
486 *out = v;
487 return true;
488}
489
490
491template <typename Type>
492struct hb_auto_t : Type
493{
494 hb_auto_t (void) { Type::init (); }
495 /* Explicitly allow the following only for pointer and references,
496 * to avoid any accidental copies.
497 *
498 * Apparently if we template for all types, then gcc seems to
499 * capture a reference argument in the type, but clang doesn't,
500 * causing unwanted copies and bugs that come with it. Ideally
501 * we should use C++11-style rvalue reference &&t1. */
502 template <typename T1> explicit hb_auto_t (T1 *t1) { Type::init (t1); }
503 template <typename T1> explicit hb_auto_t (T1 &t1) { Type::init (t1); }
504 ~hb_auto_t (void) { Type::fini (); }
505 private: /* Hide */
506 void init (void) {}
507 void fini (void) {}
508};
509
510struct hb_bytes_t
511{
512 inline hb_bytes_t (void) : bytes (nullptr), len (0) {}
513 inline hb_bytes_t (const char *bytes_, unsigned int len_) : bytes (bytes_), len (len_) {}
514 inline hb_bytes_t (const void *bytes_, unsigned int len_) : bytes ((const char *) bytes_), len (len_) {}
515
516 inline void free (void) { ::free ((void *) bytes); bytes = nullptr; len = 0; }
517
518 inline int cmp (const hb_bytes_t &a) const
519 {
520 if (len != a.len)
521 return (int) a.len - (int) len;
522
523 return memcmp (a.bytes, bytes, len);
524 }
525 static inline int cmp (const void *pa, const void *pb)
526 {
527 hb_bytes_t *a = (hb_bytes_t *) pa;
528 hb_bytes_t *b = (hb_bytes_t *) pb;
529 return b->cmp (*a);
530 }
531
532 const char *bytes;
533 unsigned int len;
534};
535
536
537struct HbOpOr
538{
539 static const bool passthru_left = true;
540 static const bool passthru_right = true;
541 template <typename T> static void process (T &o, const T &a, const T &b) { o = a | b; }
542};
543struct HbOpAnd
544{
545 static const bool passthru_left = false;
546 static const bool passthru_right = false;
547 template <typename T> static void process (T &o, const T &a, const T &b) { o = a & b; }
548};
549struct HbOpMinus
550{
551 static const bool passthru_left = true;
552 static const bool passthru_right = false;
553 template <typename T> static void process (T &o, const T &a, const T &b) { o = a & ~b; }
554};
555struct HbOpXor
556{
557 static const bool passthru_left = true;
558 static const bool passthru_right = true;
559 template <typename T> static void process (T &o, const T &a, const T &b) { o = a ^ b; }
560};
561
562
563/* Compiler-assisted vectorization. */
564
565/* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))),
566 * using vectorized operations if HB_VECTOR_SIZE is set to **bit** numbers (eg 128).
567 * Define that to 0 to disable. */
568template <typename elt_t, unsigned int byte_size>
569struct hb_vector_size_t
570{
571 elt_t& operator [] (unsigned int i) { return u.v[i]; }
572 const elt_t& operator [] (unsigned int i) const { return u.v[i]; }
573
574 template <class Op>
575 inline hb_vector_size_t process (const hb_vector_size_t &o) const
576 {
577 hb_vector_size_t r;
578#if HB_VECTOR_SIZE
579 if (HB_VECTOR_SIZE && 0 == (byte_size * 8) % HB_VECTOR_SIZE)
580 for (unsigned int i = 0; i < ARRAY_LENGTH (u.vec); i++)
581 Op::process (r.u.vec[i], u.vec[i], o.u.vec[i]);
582 else
583#endif
584 for (unsigned int i = 0; i < ARRAY_LENGTH (u.v); i++)
585 Op::process (r.u.v[i], u.v[i], o.u.v[i]);
586 return r;
587 }
588 inline hb_vector_size_t operator | (const hb_vector_size_t &o) const
589 { return process<HbOpOr> (o); }
590 inline hb_vector_size_t operator & (const hb_vector_size_t &o) const
591 { return process<HbOpAnd> (o); }
592 inline hb_vector_size_t operator ^ (const hb_vector_size_t &o) const
593 { return process<HbOpXor> (o); }
594 inline hb_vector_size_t operator ~ () const
595 {
596 hb_vector_size_t r;
597#if HB_VECTOR_SIZE && 0
598 if (HB_VECTOR_SIZE && 0 == (byte_size * 8) % HB_VECTOR_SIZE)
599 for (unsigned int i = 0; i < ARRAY_LENGTH (u.vec); i++)
600 r.u.vec[i] = ~u.vec[i];
601 else
602#endif
603 for (unsigned int i = 0; i < ARRAY_LENGTH (u.v); i++)
604 r.u.v[i] = ~u.v[i];
605 return r;
606 }
607
608 private:
609 static_assert (byte_size / sizeof (elt_t) * sizeof (elt_t) == byte_size, "");
610 union {
611 elt_t v[byte_size / sizeof (elt_t)];
612#if HB_VECTOR_SIZE
613 hb_vector_size_impl_t vec[byte_size / sizeof (hb_vector_size_impl_t)];
614#endif
615 } u;
616};
617
618
619#endif /* HB_DSALGS_HH */
620