src/hb-set-private.hh | 112 +++++++++++++++++++++++++++----------------------- 1 file changed, 61 insertions(+), 51 deletions(-)
New commits: commit f7466ee76f2bd3812209426e2c39fe517227406d Author: Behdad Esfahbod <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 { _______________________________________________ HarfBuzz mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/harfbuzz
