src/hb-private.hh | 4 +-- src/hb-set-private.hh | 61 ++++++++++++++++++-------------------------------- 2 files changed, 24 insertions(+), 41 deletions(-)
New commits: commit f18b9fbf6583dff72675be7859fc147ec24a0dd2 Author: Behdad Esfahbod <[email protected]> Date: Fri Feb 16 18:14:41 2018 -0800 [set] Implement iteration using bitop intrinsics diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh index 55a52919..49cd7912 100644 --- a/src/hb-set-private.hh +++ b/src/hb-set-private.hh @@ -109,21 +109,16 @@ struct hb_set_t unsigned int i = m / ELT_BITS; unsigned int j = m & ELT_MASK; - for (; j < ELT_BITS; j++) - if (v[i] & (elt_t (1) << j)) - goto found; - for (i++; i < len (); i++) - if (v[i]) - for (j = 0; j < ELT_BITS; j++) - if (v[i] & (elt_t (1) << j)) - goto found; + const elt_t vv = v[i] & ~((elt_t (1) << j) - 1); + for (const elt_t *p = &vv; i < len (); p = &v[++i]) + if (*p) + { + *codepoint = i * ELT_BITS + elt_get_min (*p); + return true; + } *codepoint = INVALID; return false; - - found: - *codepoint = i * ELT_BITS + j; - return true; } inline bool previous (hb_codepoint_t *codepoint) const { @@ -136,44 +131,29 @@ struct hb_set_t unsigned int i = m / ELT_BITS; unsigned int j = m & ELT_MASK; - for (; (int) j >= 0; j--) - if (v[i] & (elt_t (1) << j)) - goto found; - for (i--; (int) i >= 0; i--) - if (v[i]) - for (j = ELT_BITS - 1; (int) j >= 0; j--) - if (v[i] & (elt_t (1) << j)) - goto found; + const elt_t vv = v[i] & ((elt_t (1) << (j + 1)) - 1); + for (const elt_t *p = &vv; (int) i >= 0; p = &v[--i]) + if (*p) + { + *codepoint = i * ELT_BITS + elt_get_max (*p); + return true; + } *codepoint = INVALID; return false; - - found: - *codepoint = i * ELT_BITS + j; - return true; } inline hb_codepoint_t get_min (void) const { for (unsigned int i = 0; i < len (); i++) if (v[i]) - { - elt_t e = v[i]; - for (unsigned int j = 0; j < ELT_BITS; j++) - if (e & (elt_t (1) << j)) - return i * ELT_BITS + j; - } + return i * ELT_BITS + elt_get_min (v[i]); return INVALID; } inline hb_codepoint_t get_max (void) const { for (int i = len () - 1; i >= 0; i--) if (v[i]) - { - elt_t e = v[i]; - for (int j = ELT_BITS - 1; j >= 0; j--) - if (e & (elt_t (1) << j)) - return i * ELT_BITS + j; - } + return i * ELT_BITS + elt_get_max (v[i]); return 0; } @@ -181,6 +161,9 @@ struct hb_set_t static const unsigned int PAGE_BITS = 1024; static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, ""); + static inline unsigned int elt_get_min (const elt_t &elt) { return _hb_ctz (elt); } + static inline unsigned int elt_get_max (const elt_t &elt) { return _hb_bit_storage (elt) - 1; } + #if 0 && HAVE_VECTOR_SIZE /* The vectorized version does not work with clang as non-const * elt() errs "non-const reference cannot bind to vector element". */ commit 6a91a2eb04951f6e33706c2b8e9cd987b429fce9 Author: Behdad Esfahbod <[email protected]> Date: Fri Feb 16 17:49:41 2018 -0800 Fix wide bitops implemenetation diff --git a/src/hb-private.hh b/src/hb-private.hh index a8bc5ed1..c9e5a5ca 100644 --- a/src/hb-private.hh +++ b/src/hb-private.hh @@ -374,10 +374,10 @@ _hb_bit_storage (T v) return sizeof (unsigned int) * 8 - __builtin_clz (v); if (sizeof (T) <= sizeof (unsigned long)) - return sizeof (unsigned int) * 8 - __builtin_clzl (v); + return sizeof (unsigned long) * 8 - __builtin_clzl (v); if (sizeof (T) <= sizeof (unsigned long long)) - return sizeof (unsigned int) * 8 - __builtin_clzll (v); + return sizeof (unsigned long long) * 8 - __builtin_clzll (v); #endif #if defined(_MSC_VER) || defined(__MINGW32__) commit d25c3e69e9b0cb9d947e98845b9e3a14ce58e350 Author: Behdad Esfahbod <[email protected]> Date: Fri Feb 16 17:45:09 2018 -0800 [set] Readjust parameters diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh index 0c73d32d..55a52919 100644 --- a/src/hb-set-private.hh +++ b/src/hb-set-private.hh @@ -177,9 +177,8 @@ struct hb_set_t return 0; } - typedef uint32_t elt_t; - static const unsigned int ELT_BITS = sizeof (elt_t) * 8; - static const unsigned int PAGE_BITS = ELT_BITS * ELT_BITS; /* 1024. Use to tune. */ + typedef unsigned long long elt_t; + static const unsigned int PAGE_BITS = 1024; static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, ""); #if 0 && HAVE_VECTOR_SIZE @@ -192,6 +191,7 @@ struct hb_set_t vector_t v; + static const unsigned int ELT_BITS = sizeof (elt_t) * 8; static const unsigned int ELT_MASK = ELT_BITS - 1; static const unsigned int BITS = sizeof (vector_t) * 8; static const unsigned int MASK = BITS - 1; _______________________________________________ HarfBuzz mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/harfbuzz
