[HarfBuzz] harfbuzz: Branch 'master' - 6 commits
Behdad Esfahbod
behdad at kemper.freedesktop.org
Wed Apr 17 15:21:50 PDT 2013
src/hb-set-private.hh | 112 +++++++++++++++++++++++++++-----------------------
1 file changed, 61 insertions(+), 51 deletions(-)
New commits:
commit f7466ee76f2bd3812209426e2c39fe517227406d
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Wed Apr 17 18:20:44 2013 -0400
Remove hb_set_digest_common_bits_t
Was unused.
diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh
index 8128a69..c6099cc 100644
--- a/src/hb-set-private.hh
+++ b/src/hb-set-private.hh
@@ -40,44 +40,6 @@
* queries. As a result, our filters have much higher.
*/
-struct hb_set_digest_common_bits_t
-{
- ASSERT_POD ();
-
- typedef unsigned int mask_t;
-
- inline void init (void) {
- mask = ~0;
- value = (mask_t) -1;
- }
-
- inline void add (hb_codepoint_t g) {
- if (unlikely (value == (mask_t) -1)) {
- value = g;
- return;
- }
-
- mask ^= (g & mask) ^ value;
- value &= mask;
- }
-
- inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {
- add (a);
- /* The negation here stands for ~(x-1). */
- mask_t upper_bits = -(1 << _hb_bit_storage (a ^ b));
- mask &= upper_bits;
- value &= upper_bits;
- }
-
- inline bool may_have (hb_codepoint_t g) const {
- return (g & mask) == value;
- }
-
- private:
- mask_t mask;
- mask_t value;
-};
-
template <typename mask_t, unsigned int shift>
struct hb_set_digest_lowest_bits_t
{
commit 0d5798a137b52d9be7ef88c79e59f9bf01d54f3b
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Wed Apr 17 18:19:21 2013 -0400
Improve hb_set_digest_t
Make Amiri rendering faster a whopping 45% again! Speends up pretty
much anything I tested.
diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh
index cc5d7e0..8128a69 100644
--- a/src/hb-set-private.hh
+++ b/src/hb-set-private.hh
@@ -167,11 +167,29 @@ struct hb_set_digest_combiner_t
tail_t tail;
};
-typedef hb_set_digest_combiner_t<
- hb_set_digest_common_bits_t,
- hb_set_digest_lowest_bits_t<unsigned long, 0>
- >
- hb_set_digest_t;
+
+/*
+ * hb_set_digest_t
+ *
+ * This is a combination of digests that performs "best".
+ * There is not much science to this: it's a result of intuition
+ * and testing.
+ */
+typedef hb_set_digest_combiner_t
+<
+ hb_set_digest_lowest_bits_t<unsigned long, 4>,
+ hb_set_digest_combiner_t
+ <
+ hb_set_digest_lowest_bits_t<unsigned long, 0>,
+ hb_set_digest_lowest_bits_t<unsigned long, 9>
+ >
+> hb_set_digest_t;
+
+
+
+/*
+ * hb_set_t
+ */
/* TODO Make this faster and memmory efficient. */
commit c7851efcd3a1e5317ab4ea57535cb755bace0848
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Wed Apr 17 17:45:39 2013 -0400
Templatize hb_set_digest_lowest_bits_t filter
diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh
index e50d7bc..cc5d7e0 100644
--- a/src/hb-set-private.hh
+++ b/src/hb-set-private.hh
@@ -78,11 +78,21 @@ struct hb_set_digest_common_bits_t
mask_t value;
};
+template <typename mask_t, unsigned int shift>
struct hb_set_digest_lowest_bits_t
{
ASSERT_POD ();
- typedef unsigned long mask_t;
+ static const unsigned int num_bits = 0
+ + (sizeof (mask_t) >= 1 ? 3 : 0)
+ + (sizeof (mask_t) >= 2 ? 1 : 0)
+ + (sizeof (mask_t) >= 4 ? 1 : 0)
+ + (sizeof (mask_t) >= 8 ? 1 : 0)
+ + (sizeof (mask_t) >= 16? 1 : 0)
+ + 0;
+
+ ASSERT_STATIC (shift < sizeof (hb_codepoint_t) * 8);
+ ASSERT_STATIC (shift + num_bits <= sizeof (hb_codepoint_t) * 8);
inline void init (void) {
mask = 0;
@@ -93,7 +103,7 @@ struct hb_set_digest_lowest_bits_t
}
inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {
- if (b - a >= sizeof (mask_t) * 8 - 1)
+ if ((b >> shift) - (a >> shift) >= sizeof (mask_t) * 8 - 1)
mask = (mask_t) -1;
else {
mask_t ma = mask_for (a);
@@ -108,7 +118,10 @@ struct hb_set_digest_lowest_bits_t
private:
- static inline mask_t mask_for (hb_codepoint_t g) { return ((mask_t) 1) << (g & (sizeof (mask_t) * 8 - 1)); }
+ static inline mask_t mask_for (hb_codepoint_t g)
+ {
+ return ((mask_t) 1) << ((g >> shift) & (sizeof (mask_t) * 8 - 1));
+ }
mask_t mask;
};
@@ -156,7 +169,7 @@ struct hb_set_digest_combiner_t
typedef hb_set_digest_combiner_t<
hb_set_digest_common_bits_t,
- hb_set_digest_lowest_bits_t
+ hb_set_digest_lowest_bits_t<unsigned long, 0>
>
hb_set_digest_t;
commit 0edd0fd255790471118fae1fd7a1309a2b77cf62
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Wed Apr 17 17:26:56 2013 -0400
Add comment
diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh
index fee09cf..e50d7bc 100644
--- a/src/hb-set-private.hh
+++ b/src/hb-set-private.hh
@@ -32,6 +32,14 @@
#include "hb-object-private.hh"
+/*
+ * The set digests here implement various "filters" that support
+ * "approximate member query". Conceptually these are like Bloom
+ * Filter and Quotient Filter, however, much smaller, faster, and
+ * designed to fit the requirements of our uses for glyph coverage
+ * queries. As a result, our filters have much higher.
+ */
+
struct hb_set_digest_common_bits_t
{
ASSERT_POD ();
commit b40f2c0372acbc51b13be5cda7dd013e74e3e11a
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Tue Apr 16 23:21:38 2013 -0400
Add hb_set_digest_combiner_t
diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh
index 8f741b0..fee09cf 100644
--- a/src/hb-set-private.hh
+++ b/src/hb-set-private.hh
@@ -108,43 +108,50 @@ struct hb_set_digest_lowest_bits_t
extern unsigned long digest_total, digest_yes, digest_yes1, digest_yes2;
#endif
-struct hb_set_digest_t
+template <typename head_t, typename tail_t>
+struct hb_set_digest_combiner_t
{
ASSERT_POD ();
inline void init (void) {
- digest1.init ();
- digest2.init ();
+ head.init ();
+ tail.init ();
}
inline void add (hb_codepoint_t g) {
- digest1.add (g);
- digest2.add (g);
+ head.add (g);
+ tail.add (g);
}
inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {
- digest1.add_range (a, b);
- digest2.add_range (a, b);
+ head.add_range (a, b);
+ tail.add_range (a, b);
}
inline bool may_have (hb_codepoint_t g) const {
#ifdef HB_DEBUG_SET_DIGESTS
digest_total++;
- if (digest1.may_have (g) && digest2.may_have (g))
+ if (head.may_have (g) && tail.may_have (g))
digest_yes++;
- if (digest1.may_have (g))
+ if (head.may_have (g))
digest_yes1++;
- if (digest2.may_have (g))
+ if (tail.may_have (g))
digest_yes2++;
#endif
- return digest1.may_have (g) && digest2.may_have (g);
+ return head.may_have (g) && tail.may_have (g);
}
private:
- hb_set_digest_common_bits_t digest1;
- hb_set_digest_lowest_bits_t digest2;
+ head_t head;
+ tail_t tail;
};
+typedef hb_set_digest_combiner_t<
+ hb_set_digest_common_bits_t,
+ hb_set_digest_lowest_bits_t
+ >
+ hb_set_digest_t;
+
/* TODO Make this faster and memmory efficient. */
commit 02e5e583688999c4dc04f11b3924da65f99af7e3
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Tue Apr 16 23:13:10 2013 -0400
Speed up Speed up hb_set_digest_common_bits_t calcs
Correctly this time.
diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh
index d9e0d29..8f741b0 100644
--- a/src/hb-set-private.hh
+++ b/src/hb-set-private.hh
@@ -54,9 +54,11 @@ struct hb_set_digest_common_bits_t
}
inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {
- /* TODO Speedup. */
- for (unsigned int i = a; i < b + 1; i++)
- add (i);
+ add (a);
+ /* The negation here stands for ~(x-1). */
+ mask_t upper_bits = -(1 << _hb_bit_storage (a ^ b));
+ mask &= upper_bits;
+ value &= upper_bits;
}
inline bool may_have (hb_codepoint_t g) const {
More information about the HarfBuzz
mailing list