[HarfBuzz] harfbuzz: Branch 'bitops' - 3 commits

[Behdad Esfahbod]

 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 <behdad at behdad.org>
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 <behdad at behdad.org>
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 <behdad at behdad.org>
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;