summaryrefslogtreecommitdiff
path: root/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-dsalgs.hh
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/harfbuzz/harfbuzz-src/src/hb-dsalgs.hh')
-rw-r--r--Build/source/libs/harfbuzz/harfbuzz-src/src/hb-dsalgs.hh705
1 files changed, 704 insertions, 1 deletions
diff --git a/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-dsalgs.hh b/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-dsalgs.hh
index 9586871947f..6a8ddaa995b 100644
--- a/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-dsalgs.hh
+++ b/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-dsalgs.hh
@@ -30,6 +30,243 @@
#include "hb-private.hh"
+/* Void! For when we need a expression-type of void. */
+typedef const struct _hb_void_t *hb_void_t;
+#define HB_VOID ((const _hb_void_t *) nullptr)
+
+
+/*
+ * Bithacks.
+ */
+
+/* Return the number of 1 bits in v. */
+template <typename T>
+static inline HB_CONST_FUNC unsigned int
+hb_popcount (T v)
+{
+#if (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) && defined(__OPTIMIZE__)
+ if (sizeof (T) <= sizeof (unsigned int))
+ return __builtin_popcount (v);
+
+ if (sizeof (T) <= sizeof (unsigned long))
+ return __builtin_popcountl (v);
+
+ if (sizeof (T) <= sizeof (unsigned long long))
+ return __builtin_popcountll (v);
+#endif
+
+ if (sizeof (T) <= 4)
+ {
+ /* "HACKMEM 169" */
+ uint32_t y;
+ y = (v >> 1) &033333333333;
+ y = v - y - ((y >>1) & 033333333333);
+ return (((y + (y >> 3)) & 030707070707) % 077);
+ }
+
+ if (sizeof (T) == 8)
+ {
+ unsigned int shift = 32;
+ return hb_popcount<uint32_t> ((uint32_t) v) + hb_popcount ((uint32_t) (v >> shift));
+ }
+
+ if (sizeof (T) == 16)
+ {
+ unsigned int shift = 64;
+ return hb_popcount<uint64_t> ((uint64_t) v) + hb_popcount ((uint64_t) (v >> shift));
+ }
+
+ assert (0);
+ return 0; /* Shut up stupid compiler. */
+}
+
+/* Returns the number of bits needed to store number */
+template <typename T>
+static inline HB_CONST_FUNC unsigned int
+hb_bit_storage (T v)
+{
+ if (unlikely (!v)) return 0;
+
+#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__)
+ if (sizeof (T) <= sizeof (unsigned int))
+ return sizeof (unsigned int) * 8 - __builtin_clz (v);
+
+ if (sizeof (T) <= sizeof (unsigned long))
+ return sizeof (unsigned long) * 8 - __builtin_clzl (v);
+
+ if (sizeof (T) <= sizeof (unsigned long long))
+ return sizeof (unsigned long long) * 8 - __builtin_clzll (v);
+#endif
+
+#if (defined(_MSC_VER) && _MSC_VER >= 1500) || defined(__MINGW32__)
+ if (sizeof (T) <= sizeof (unsigned int))
+ {
+ unsigned long where;
+ _BitScanReverse (&where, v);
+ return 1 + where;
+ }
+# if _WIN64
+ if (sizeof (T) <= 8)
+ {
+ unsigned long where;
+ _BitScanReverse64 (&where, v);
+ return 1 + where;
+ }
+# endif
+#endif
+
+ if (sizeof (T) <= 4)
+ {
+ /* "bithacks" */
+ const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
+ const unsigned int S[] = {1, 2, 4, 8, 16};
+ unsigned int r = 0;
+ for (int i = 4; i >= 0; i--)
+ if (v & b[i])
+ {
+ v >>= S[i];
+ r |= S[i];
+ }
+ return r + 1;
+ }
+ if (sizeof (T) <= 8)
+ {
+ /* "bithacks" */
+ const uint64_t b[] = {0x2ULL, 0xCULL, 0xF0ULL, 0xFF00ULL, 0xFFFF0000ULL, 0xFFFFFFFF00000000ULL};
+ const unsigned int S[] = {1, 2, 4, 8, 16, 32};
+ unsigned int r = 0;
+ for (int i = 5; i >= 0; i--)
+ if (v & b[i])
+ {
+ v >>= S[i];
+ r |= S[i];
+ }
+ return r + 1;
+ }
+ if (sizeof (T) == 16)
+ {
+ unsigned int shift = 64;
+ return (v >> shift) ? hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift :
+ hb_bit_storage<uint64_t> ((uint64_t) v);
+ }
+
+ assert (0);
+ return 0; /* Shut up stupid compiler. */
+}
+
+/* Returns the number of zero bits in the least significant side of v */
+template <typename T>
+static inline HB_CONST_FUNC unsigned int
+hb_ctz (T v)
+{
+ if (unlikely (!v)) return 0;
+
+#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__)
+ if (sizeof (T) <= sizeof (unsigned int))
+ return __builtin_ctz (v);
+
+ if (sizeof (T) <= sizeof (unsigned long))
+ return __builtin_ctzl (v);
+
+ if (sizeof (T) <= sizeof (unsigned long long))
+ return __builtin_ctzll (v);
+#endif
+
+#if (defined(_MSC_VER) && _MSC_VER >= 1500) || defined(__MINGW32__)
+ if (sizeof (T) <= sizeof (unsigned int))
+ {
+ unsigned long where;
+ _BitScanForward (&where, v);
+ return where;
+ }
+# if _WIN64
+ if (sizeof (T) <= 8)
+ {
+ unsigned long where;
+ _BitScanForward64 (&where, v);
+ return where;
+ }
+# endif
+#endif
+
+ if (sizeof (T) <= 4)
+ {
+ /* "bithacks" */
+ unsigned int c = 32;
+ v &= - (int32_t) v;
+ if (v) c--;
+ if (v & 0x0000FFFF) c -= 16;
+ if (v & 0x00FF00FF) c -= 8;
+ if (v & 0x0F0F0F0F) c -= 4;
+ if (v & 0x33333333) c -= 2;
+ if (v & 0x55555555) c -= 1;
+ return c;
+ }
+ if (sizeof (T) <= 8)
+ {
+ /* "bithacks" */
+ unsigned int c = 64;
+ v &= - (int64_t) (v);
+ if (v) c--;
+ if (v & 0x00000000FFFFFFFFULL) c -= 32;
+ if (v & 0x0000FFFF0000FFFFULL) c -= 16;
+ if (v & 0x00FF00FF00FF00FFULL) c -= 8;
+ if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4;
+ if (v & 0x3333333333333333ULL) c -= 2;
+ if (v & 0x5555555555555555ULL) c -= 1;
+ return c;
+ }
+ if (sizeof (T) == 16)
+ {
+ unsigned int shift = 64;
+ return (uint64_t) v ? hb_bit_storage<uint64_t> ((uint64_t) v) :
+ hb_bit_storage<uint64_t> ((uint64_t) (v >> shift)) + shift;
+ }
+
+ assert (0);
+ return 0; /* Shut up stupid compiler. */
+}
+
+
+/*
+ * Tiny stuff.
+ */
+
+#undef MIN
+template <typename Type>
+static inline Type MIN (const Type &a, const Type &b) { return a < b ? a : b; }
+
+#undef MAX
+template <typename Type>
+static inline Type MAX (const Type &a, const Type &b) { return a > b ? a : b; }
+
+static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)
+{ return (a + (b - 1)) / b; }
+
+
+#undef ARRAY_LENGTH
+template <typename Type, unsigned int n>
+static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }
+/* A const version, but does not detect erratically being called on pointers. */
+#define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
+
+static inline bool
+hb_unsigned_mul_overflows (unsigned int count, unsigned int size)
+{
+ return (size > 0) && (count >= ((unsigned int) -1) / size);
+}
+
+static inline unsigned int
+hb_ceil_to_4 (unsigned int v)
+{
+ return ((v - 1) | 3) + 1;
+}
+
+
+/*
+ * Sort and search.
+ */
+
static inline void *
hb_bsearch_r (const void *key, const void *base,
size_t nmemb, size_t size,
@@ -53,7 +290,6 @@ hb_bsearch_r (const void *key, const void *base,
}
-
/* From https://github.com/noporpoise/sort_r */
/* Isaac Turner 29 April 2014 Public Domain */
@@ -158,4 +394,471 @@ static inline void hb_sort_r(void *base, size_t nel, size_t width,
sort_r_simple(base, nel, width, compar, arg);
}
+
+template <typename T, typename T2> static inline void
+hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *), T2 *array2)
+{
+ for (unsigned int i = 1; i < len; i++)
+ {
+ unsigned int j = i;
+ while (j && compar (&array[j - 1], &array[i]) > 0)
+ j--;
+ if (i == j)
+ continue;
+ /* Move item i to occupy place for item j, shift what's in between. */
+ {
+ T t = array[i];
+ memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
+ array[j] = t;
+ }
+ if (array2)
+ {
+ T2 t = array2[i];
+ memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T2));
+ array2[j] = t;
+ }
+ }
+}
+
+template <typename T> static inline void
+hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
+{
+ hb_stable_sort (array, len, compar, (int *) nullptr);
+}
+
+static inline hb_bool_t
+hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out)
+{
+ /* Pain because we don't know whether s is nul-terminated. */
+ char buf[64];
+ len = MIN (ARRAY_LENGTH (buf) - 1, len);
+ strncpy (buf, s, len);
+ buf[len] = '\0';
+
+ char *end;
+ errno = 0;
+ unsigned long v = strtoul (buf, &end, base);
+ if (errno) return false;
+ if (*end) return false;
+ *out = v;
+ return true;
+}
+
+
+#define HB_VECTOR_INIT {0, 0, false, nullptr}
+template <typename Type, unsigned int StaticSize=8>
+struct hb_vector_t
+{
+ unsigned int len;
+ unsigned int allocated;
+ bool successful;
+ Type *arrayZ;
+ Type static_array[StaticSize];
+
+ void init (void)
+ {
+ len = 0;
+ allocated = ARRAY_LENGTH (static_array);
+ successful = true;
+ arrayZ = static_array;
+ }
+
+ inline Type& operator [] (unsigned int i)
+ {
+ if (unlikely (i >= len))
+ return Crap (Type);
+ return arrayZ[i];
+ }
+ inline const Type& operator [] (unsigned int i) const
+ {
+ if (unlikely (i >= len))
+ return Null(Type);
+ return arrayZ[i];
+ }
+
+ inline Type *push (void)
+ {
+ if (unlikely (!resize (len + 1)))
+ return &Crap(Type);
+ return &arrayZ[len - 1];
+ }
+ inline Type *push (const Type& v)
+ {
+ Type *p = push ();
+ *p = v;
+ return p;
+ }
+
+ /* Allocate for size but don't adjust len. */
+ inline bool alloc (unsigned int size)
+ {
+ if (unlikely (!successful))
+ return false;
+
+ if (likely (size <= allocated))
+ return true;
+
+ /* Reallocate */
+
+ unsigned int new_allocated = allocated;
+ while (size >= new_allocated)
+ new_allocated += (new_allocated >> 1) + 8;
+
+ Type *new_array = nullptr;
+
+ if (arrayZ == static_array)
+ {
+ new_array = (Type *) calloc (new_allocated, sizeof (Type));
+ if (new_array)
+ memcpy (new_array, arrayZ, len * sizeof (Type));
+ }
+ else
+ {
+ bool overflows = (new_allocated < allocated) || hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
+ if (likely (!overflows))
+ new_array = (Type *) realloc (arrayZ, new_allocated * sizeof (Type));
+ }
+
+ if (unlikely (!new_array))
+ {
+ successful = false;
+ return false;
+ }
+
+ arrayZ = new_array;
+ allocated = new_allocated;
+
+ return true;
+ }
+
+ inline bool resize (int size_)
+ {
+ unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
+ if (!alloc (size))
+ return false;
+
+ if (size > len)
+ memset (arrayZ + len, 0, (size - len) * sizeof (*arrayZ));
+
+ len = size;
+ return true;
+ }
+
+ inline void pop (void)
+ {
+ if (!len) return;
+ len--;
+ }
+
+ inline void remove (unsigned int i)
+ {
+ if (unlikely (i >= len))
+ return;
+ memmove (static_cast<void *> (&arrayZ[i]),
+ static_cast<void *> (&arrayZ[i + 1]),
+ (len - i - 1) * sizeof (Type));
+ len--;
+ }
+
+ inline void shrink (int size_)
+ {
+ unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
+ if (size < len)
+ len = size;
+ }
+
+ template <typename T>
+ inline Type *find (T v) {
+ for (unsigned int i = 0; i < len; i++)
+ if (arrayZ[i] == v)
+ return &arrayZ[i];
+ return nullptr;
+ }
+ template <typename T>
+ inline const Type *find (T v) const {
+ for (unsigned int i = 0; i < len; i++)
+ if (arrayZ[i] == v)
+ return &arrayZ[i];
+ return nullptr;
+ }
+
+ inline void qsort (int (*cmp)(const void*, const void*))
+ {
+ ::qsort (arrayZ, len, sizeof (Type), cmp);
+ }
+
+ inline void qsort (void)
+ {
+ ::qsort (arrayZ, len, sizeof (Type), Type::cmp);
+ }
+
+ inline void qsort (unsigned int start, unsigned int end)
+ {
+ ::qsort (arrayZ + start, end - start, sizeof (Type), Type::cmp);
+ }
+
+ template <typename T>
+ inline Type *lsearch (const T &x)
+ {
+ for (unsigned int i = 0; i < len; i++)
+ if (0 == this->arrayZ[i].cmp (&x))
+ return &arrayZ[i];
+ return nullptr;
+ }
+
+ template <typename T>
+ inline Type *bsearch (const T &x)
+ {
+ unsigned int i;
+ return bfind (x, &i) ? &arrayZ[i] : nullptr;
+ }
+ template <typename T>
+ inline const Type *bsearch (const T &x) const
+ {
+ unsigned int i;
+ return bfind (x, &i) ? &arrayZ[i] : nullptr;
+ }
+ template <typename T>
+ inline bool bfind (const T &x, unsigned int *i) const
+ {
+ int min = 0, max = (int) this->len - 1;
+ while (min <= max)
+ {
+ int mid = (min + max) / 2;
+ int c = this->arrayZ[mid].cmp (&x);
+ if (c < 0)
+ max = mid - 1;
+ else if (c > 0)
+ min = mid + 1;
+ else
+ {
+ *i = mid;
+ return true;
+ }
+ }
+ if (max < 0 || (max < (int) this->len && this->arrayZ[max].cmp (&x) > 0))
+ max++;
+ *i = max;
+ return false;
+ }
+
+ inline void fini (void)
+ {
+ if (arrayZ != static_array)
+ free (arrayZ);
+ arrayZ = nullptr;
+ allocated = len = 0;
+ }
+};
+
+
+#define HB_LOCKABLE_SET_INIT {HB_VECTOR_INIT}
+template <typename item_t, typename lock_t>
+struct hb_lockable_set_t
+{
+ hb_vector_t <item_t, 1> items;
+
+ inline void init (void) { items.init (); }
+
+ template <typename T>
+ inline item_t *replace_or_insert (T v, lock_t &l, bool replace)
+ {
+ l.lock ();
+ item_t *item = items.find (v);
+ if (item) {
+ if (replace) {
+ item_t old = *item;
+ *item = v;
+ l.unlock ();
+ old.fini ();
+ }
+ else {
+ item = nullptr;
+ l.unlock ();
+ }
+ } else {
+ item = items.push (v);
+ l.unlock ();
+ }
+ return item;
+ }
+
+ template <typename T>
+ inline void remove (T v, lock_t &l)
+ {
+ l.lock ();
+ item_t *item = items.find (v);
+ if (item) {
+ item_t old = *item;
+ *item = items[items.len - 1];
+ items.pop ();
+ l.unlock ();
+ old.fini ();
+ } else {
+ l.unlock ();
+ }
+ }
+
+ template <typename T>
+ inline bool find (T v, item_t *i, lock_t &l)
+ {
+ l.lock ();
+ item_t *item = items.find (v);
+ if (item)
+ *i = *item;
+ l.unlock ();
+ return !!item;
+ }
+
+ template <typename T>
+ inline item_t *find_or_insert (T v, lock_t &l)
+ {
+ l.lock ();
+ item_t *item = items.find (v);
+ if (!item) {
+ item = items.push (v);
+ }
+ l.unlock ();
+ return item;
+ }
+
+ inline void fini (lock_t &l)
+ {
+ if (!items.len) {
+ /* No need for locking. */
+ items.fini ();
+ return;
+ }
+ l.lock ();
+ while (items.len) {
+ item_t old = items[items.len - 1];
+ items.pop ();
+ l.unlock ();
+ old.fini ();
+ l.lock ();
+ }
+ items.fini ();
+ l.unlock ();
+ }
+
+};
+
+
+template <typename Type>
+struct hb_auto_t : Type
+{
+ hb_auto_t (void) { Type::init (); }
+ ~hb_auto_t (void) { Type::fini (); }
+ private: /* Hide */
+ void init (void) {}
+ void fini (void) {}
+};
+
+struct hb_bytes_t
+{
+ inline hb_bytes_t (void) : bytes (nullptr), len (0) {}
+ inline hb_bytes_t (const char *bytes_, unsigned int len_) : bytes (bytes_), len (len_) {}
+
+ inline int cmp (const hb_bytes_t &a) const
+ {
+ if (len != a.len)
+ return (int) a.len - (int) len;
+
+ return memcmp (a.bytes, bytes, len);
+ }
+ static inline int cmp (const void *pa, const void *pb)
+ {
+ hb_bytes_t *a = (hb_bytes_t *) pa;
+ hb_bytes_t *b = (hb_bytes_t *) pb;
+ return b->cmp (*a);
+ }
+
+ const char *bytes;
+ unsigned int len;
+};
+
+
+struct HbOpOr
+{
+ static const bool passthru_left = true;
+ static const bool passthru_right = true;
+ template <typename T> static void process (T &o, const T &a, const T &b) { o = a | b; }
+};
+struct HbOpAnd
+{
+ static const bool passthru_left = false;
+ static const bool passthru_right = false;
+ template <typename T> static void process (T &o, const T &a, const T &b) { o = a & b; }
+};
+struct HbOpMinus
+{
+ static const bool passthru_left = true;
+ static const bool passthru_right = false;
+ template <typename T> static void process (T &o, const T &a, const T &b) { o = a & ~b; }
+};
+struct HbOpXor
+{
+ static const bool passthru_left = true;
+ static const bool passthru_right = true;
+ template <typename T> static void process (T &o, const T &a, const T &b) { o = a ^ b; }
+};
+
+
+/* Compiler-assisted vectorization. */
+
+/* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))),
+ * using vectorized operations if HB_VECTOR_SIZE is set to **bit** numbers (eg 128).
+ * Define that to 0 to disable. */
+template <typename elt_t, unsigned int byte_size>
+struct hb_vector_size_t
+{
+ elt_t& operator [] (unsigned int i) { return u.v[i]; }
+ const elt_t& operator [] (unsigned int i) const { return u.v[i]; }
+
+ template <class Op>
+ inline hb_vector_size_t process (const hb_vector_size_t &o) const
+ {
+ hb_vector_size_t r;
+#if HB_VECTOR_SIZE
+ if (HB_VECTOR_SIZE && 0 == (byte_size * 8) % HB_VECTOR_SIZE)
+ for (unsigned int i = 0; i < ARRAY_LENGTH (u.vec); i++)
+ Op::process (r.u.vec[i], u.vec[i], o.u.vec[i]);
+ else
+#endif
+ for (unsigned int i = 0; i < ARRAY_LENGTH (u.v); i++)
+ Op::process (r.u.v[i], u.v[i], o.u.v[i]);
+ return r;
+ }
+ inline hb_vector_size_t operator | (const hb_vector_size_t &o) const
+ { return process<HbOpOr> (o); }
+ inline hb_vector_size_t operator & (const hb_vector_size_t &o) const
+ { return process<HbOpAnd> (o); }
+ inline hb_vector_size_t operator ^ (const hb_vector_size_t &o) const
+ { return process<HbOpXor> (o); }
+ inline hb_vector_size_t operator ~ () const
+ {
+ hb_vector_size_t r;
+#if HB_VECTOR_SIZE && 0
+ if (HB_VECTOR_SIZE && 0 == (byte_size * 8) % HB_VECTOR_SIZE)
+ for (unsigned int i = 0; i < ARRAY_LENGTH (u.vec); i++)
+ r.u.vec[i] = ~u.vec[i];
+ else
+#endif
+ for (unsigned int i = 0; i < ARRAY_LENGTH (u.v); i++)
+ r.u.v[i] = ~u.v[i];
+ return r;
+ }
+
+ private:
+ static_assert (byte_size / sizeof (elt_t) * sizeof (elt_t) == byte_size, "");
+ union {
+ elt_t v[byte_size / sizeof (elt_t)];
+#if HB_VECTOR_SIZE
+ typedef unsigned long vec_t __attribute__((vector_size (HB_VECTOR_SIZE / 8)));
+ vec_t vec[byte_size / sizeof (vec_t)];
+#endif
+ } u;
+};
+
+
#endif /* HB_DSALGS_HH */