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