src/Makefile.sources | 2 src/hb-cache-private.hh | 74 ----- src/hb-deprecated.h | 4 src/hb-ft.cc | 2 src/hb-ot-layout-private.hh | 2 src/hb-ot-map-private.hh | 4 src/hb-private.hh | 99 +++++-- src/hb-set-digest-private.hh | 144 +++++++++++ src/hb-set-private.hh | 555 +++++++++++++++++++++++++------------------ src/hb-set.cc | 3 src/hb-set.h | 3 test/api/test-set.c | 6 12 files changed, 563 insertions(+), 335 deletions(-)
New commits: commit deed4a48d15d4a475f8695aa3269547adf63867a Author: Behdad Esfahbod <[email protected]> Date: Sun Oct 15 16:53:09 2017 +0200 Faster hb_set_t Fixes https://github.com/behdad/harfbuzz/pull/23 diff --git a/src/hb-private.hh b/src/hb-private.hh index f8e5c8e4..46bffac2 100644 --- a/src/hb-private.hh +++ b/src/hb-private.hh @@ -411,34 +411,48 @@ struct hb_prealloced_array_t inline Type *push (void) { + if (unlikely (!resize (len + 1))) + return nullptr; + + return &array[len - 1]; + } + + inline bool resize (unsigned int size) + { if (!array) { array = static_array; allocated = ARRAY_LENGTH (static_array); } - if (likely (len < allocated)) - return &array[len++]; + if (size > allocated) + { + /* Need to reallocate */ + + unsigned int new_allocated = allocated; + while (size >= new_allocated) + new_allocated += (new_allocated >> 1) + 8; + + Type *new_array = nullptr; + + if (array == static_array) { + new_array = (Type *) calloc (new_allocated, sizeof (Type)); + if (new_array) + memcpy (new_array, array, len * sizeof (Type)); + } else { + bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type)); + if (likely (!overflows)) { + new_array = (Type *) realloc (array, new_allocated * sizeof (Type)); + } + } - /* Need to reallocate */ - unsigned int new_allocated = allocated + (allocated >> 1) + 8; - Type *new_array = nullptr; + if (unlikely (!new_array)) + return false; - if (array == static_array) { - new_array = (Type *) calloc (new_allocated, sizeof (Type)); - if (new_array) - memcpy (new_array, array, len * sizeof (Type)); - } else { - bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type)); - if (likely (!overflows)) { - new_array = (Type *) realloc (array, new_allocated * sizeof (Type)); - } + array = new_array; + allocated = new_allocated; } - if (unlikely (!new_array)) - return nullptr; - - array = new_array; - allocated = new_allocated; - return &array[len++]; + len = size; + return true; } inline void pop (void) @@ -517,7 +531,7 @@ struct hb_prealloced_array_t return true; } } - if (max < 0 || max < (int) this->len && this->array[max].cmp (x) < 0) + if (max < 0 || (max < (int) this->len && this->array[max].cmp (x) > 0)) max++; *i = max; return false; diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh index 71a843f5..cd795bc5 100644 --- a/src/hb-set-private.hh +++ b/src/hb-set-private.hh @@ -1,5 +1,5 @@ /* - * Copyright © 2012 Google, Inc. + * Copyright © 2012,2017 Google, Inc. * * This is part of HarfBuzz, a text shaping library. * @@ -35,39 +35,208 @@ * hb_set_t */ - -/* TODO Make this faster and memmory efficient. */ +struct Union +{ + 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 Intersect +{ + 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 Subtract +{ + 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 SymmetricDifference +{ + 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 hb_set_t { + struct page_map_t + { + inline int cmp (const page_map_t *o) const { return (int) o->major - (int) major; } + + uint32_t major; + uint32_t index; + }; + + struct page_t + { + inline void init (void) { + memset (&v, 0, sizeof (v)); + } + + inline unsigned int len (void) const + { return ARRAY_LENGTH_CONST (v); } + + inline bool is_empty (void) const + { + for (unsigned int i = 0; i < len (); i++) + if (v[i]) + return false; + return true; + } + + inline void add (hb_codepoint_t g) { elt (g) |= mask (g); } + inline void del (hb_codepoint_t g) { elt (g) &= ~mask (g); } + inline bool has (hb_codepoint_t g) const { return !!(elt (g) & mask (g)); } + + inline bool is_equal (const page_t *other) const + { + return 0 == memcmp (&v, &other->v, sizeof (v)); + } + + inline unsigned int get_population (void) const + { + unsigned int pop = 0; + for (unsigned int i = 0; i < len (); i++) + pop += _hb_popcount (v[i]); + return pop; + } + + inline bool next (hb_codepoint_t *codepoint) const + { + unsigned int m = (*codepoint + 1) & MASK; + if (!m) + { + *codepoint = INVALID; + return false; + } + 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 (unsigned int j = 0; j < ELT_BITS; j++) + if (v[i] & (elt_t (1) << j)) + goto found; + + *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 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 0; + } + + typedef uint64_t elt_t; + + static const unsigned int PAGE_BITS = 512; /* Use to tune. */ + static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, ""); + +#if 1 + typedef elt_t vector_t __attribute__((vector_size (PAGE_BITS / 8))); +#else + struct vector_t + { + elt_t& operator [] (unsigned int i) { return v[i]; } + const elt_t& operator [] (unsigned int i) const { return v[i]; } + + private: + elt_t v[PAGE_BITS / (sizeof (elt_t) * 8)]; + }; +#endif + + 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 (v) * 8; + static const unsigned int MASK = BITS - 1; + static_assert (PAGE_BITS == BITS, ""); + + elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; } + elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; } + elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & ELT_MASK); } + }; + hb_object_header_t header; ASSERT_POD (); bool in_error; + hb_prealloced_array_t<page_map_t, 8> page_map; + hb_prealloced_array_t<page_t, 8> pages; + + inline bool resize (unsigned int count) + { + if (unlikely (in_error)) return false; + if (!pages.resize (count) || !page_map.resize (count)) + { + pages.resize (page_map.len); + in_error = true; + return false; + } + return true; + } inline void init (void) { hb_object_init (this); - clear (); + page_map.init (); + pages.init (); } inline void fini (void) { + page_map.finish (); + pages.finish (); } inline void clear (void) { if (unlikely (hb_object_is_inert (this))) return; in_error = false; - memset (elts, 0, sizeof elts); + page_map.resize (0); + pages.resize (0); } inline bool is_empty (void) const { - for (unsigned int i = 0; i < ARRAY_LENGTH (elts); i++) - if (elts[i]) + unsigned int count = pages.len; + for (unsigned int i = 0; i < count; i++) + if (!pages[i].is_empty ()) return false; return true; } + inline void add (hb_codepoint_t g) { if (unlikely (in_error)) return; if (unlikely (g == INVALID)) return; - if (unlikely (g > MAX_G)) return; - elt (g) |= mask (g); + page_t *page = page_for_insert (g); + if (!page) + return; + page->add (g); } inline void add_range (hb_codepoint_t a, hb_codepoint_t b) { @@ -79,8 +248,10 @@ struct hb_set_t inline void del (hb_codepoint_t g) { if (unlikely (in_error)) return; - if (unlikely (g > MAX_G)) return; - elt (g) &= ~mask (g); + page_t *p = page_for (g); + if (!p) + return; + p->del (g); } inline void del_range (hb_codepoint_t a, hb_codepoint_t b) { @@ -91,80 +262,169 @@ struct hb_set_t } inline bool has (hb_codepoint_t g) const { - if (unlikely (g > MAX_G)) return false; - return !!(elt (g) & mask (g)); + const page_t *p = page_for (g); + if (!p) + return false; + return p->has (g); } inline bool intersects (hb_codepoint_t first, hb_codepoint_t last) const { - if (unlikely (first > MAX_G)) return false; - if (unlikely (last > MAX_G)) last = MAX_G; + /* TODO Speedup */ unsigned int end = last + 1; for (hb_codepoint_t i = first; i < end; i++) if (has (i)) return true; return false; } + inline void set (const hb_set_t *other) + { + if (unlikely (in_error)) return; + unsigned int count = other->pages.len; + if (!resize (count)) + return; + + memcpy (pages.array, other->pages.array, count * sizeof (pages.array[0])); + memcpy (page_map.array, other->page_map.array, count * sizeof (page_map.array[0])); + } + inline bool is_equal (const hb_set_t *other) const { - for (unsigned int i = 0; i < ELTS; i++) - if (elts[i] != other->elts[i]) + unsigned int na = pages.len; + unsigned int nb = other->pages.len; + + unsigned int a = 0, b = 0; + for (; a < na && b < nb; ) + { + if (page_at (a).is_empty ()) { a++; continue; } + if (other->page_at (b).is_empty ()) { b++; continue; } + if (page_map[a].major != other->page_map[b].major || + !page_at (a).is_equal (&other->page_at (b))) return false; + a++; + b++; + } + for (; a < na; a++) + if (!page_at (a).is_empty ()) { return false; } + for (; b < nb; b++) + if (!other->page_at (b).is_empty ()) { return false; } + return true; } - inline void set (const hb_set_t *other) + + template <class Op> + inline void process (const hb_set_t *other) { if (unlikely (in_error)) return; - for (unsigned int i = 0; i < ELTS; i++) - elts[i] = other->elts[i]; + + int na = pages.len; + int nb = other->pages.len; + + unsigned int count = 0; + int a = 0, b = 0; + for (; a < na && b < nb; ) + { + if (page_map[a].major == other->page_map[b].major) + { + count++; + a++; + b++; + } + else if (page_map[a].major < other->page_map[b].major) + { + if (Op::passthru_left) + count++; + a++; + } + else + { + if (Op::passthru_right) + count++; + b++; + } + } + if (Op::passthru_left) + count += na - a; + if (Op::passthru_right) + count += nb - b; + + if (!resize (count)) + return; + + /* Process in-place backward. */ + a = na - 1, b = nb - 1; + for (; a >= 0 && b >= 0; ) + { + if (page_map[a].major == other->page_map[b].major) + { + Op::process (page_at (--count).v, page_at (a).v, other->page_at (b).v); + a--; + b--; + } + else if (page_map[a].major < other->page_map[b].major) + { + if (Op::passthru_left) + page_at (--count).v = page_at (a).v; + a--; + } + else + { + if (Op::passthru_right) + page_at (--count).v = other->page_at (b).v; + b--; + } + } + while (a >= 0) + page_at (--count).v = page_at (--a).v; + while (b >= 0) + page_at (--count).v = other->page_at (--b).v; + assert (!count); } + inline void union_ (const hb_set_t *other) { - if (unlikely (in_error)) return; - for (unsigned int i = 0; i < ELTS; i++) - elts[i] |= other->elts[i]; + process<Union> (other); } inline void intersect (const hb_set_t *other) { - if (unlikely (in_error)) return; - for (unsigned int i = 0; i < ELTS; i++) - elts[i] &= other->elts[i]; + process<Intersect> (other); } inline void subtract (const hb_set_t *other) { - if (unlikely (in_error)) return; - for (unsigned int i = 0; i < ELTS; i++) - elts[i] &= ~other->elts[i]; + process<Subtract> (other); } inline void symmetric_difference (const hb_set_t *other) { - if (unlikely (in_error)) return; - for (unsigned int i = 0; i < ELTS; i++) - elts[i] ^= other->elts[i]; - } - inline void invert (void) - { - if (unlikely (in_error)) return; - for (unsigned int i = 0; i < ELTS; i++) - elts[i] = ~elts[i]; + process<SymmetricDifference> (other); } inline bool next (hb_codepoint_t *codepoint) const { if (unlikely (*codepoint == INVALID)) { - hb_codepoint_t i = get_min (); - if (i != INVALID) { - *codepoint = i; - return true; - } else { - *codepoint = INVALID; - return false; + *codepoint = get_min (); + return *codepoint != INVALID; + } + + page_map_t map = {major (*codepoint), 0}; + unsigned int i; + page_map.bfind (&map, &i); + if (i < page_map.len) + { + if (pages[page_map[i].index].next (codepoint)) + { + *codepoint += page_map[i].major * PAGE_SIZE; + return true; } + i++; } - for (hb_codepoint_t i = *codepoint + 1; i < MAX_G + 1; i++) - if (has (i)) { - *codepoint = i; + for (; i < page_map.len; i++) + { + hb_codepoint_t m = pages[page_map[i].index].get_min (); + if (m != INVALID) + { + *codepoint = page_map[i].major * PAGE_SIZE + m; return true; } + } *codepoint = INVALID; return false; } @@ -172,6 +432,7 @@ struct hb_set_t { hb_codepoint_t i; + /* TODO speedup. */ i = *last; if (!next (&i)) { @@ -188,46 +449,66 @@ struct hb_set_t inline unsigned int get_population (void) const { - unsigned int count = 0; - for (unsigned int i = 0; i < ELTS; i++) - count += _hb_popcount32 (elts[i]); - return count; + unsigned int pop = 0; + unsigned int count = pages.len; + for (unsigned int i = 0; i < count; i++) + pop += pages[i].get_population (); + return pop; } inline hb_codepoint_t get_min (void) const { - for (unsigned int i = 0; i < ELTS; i++) - if (elts[i]) - for (unsigned int j = 0; j < BITS; j++) - if (elts[i] & (1u << j)) - return i * BITS + j; + unsigned int count = pages.len; + for (unsigned int i = 0; i < count; i++) + if (!page_at (i).is_empty ()) + return page_map[i].major * PAGE_SIZE + page_at (i).get_min (); return INVALID; } inline hb_codepoint_t get_max (void) const { - for (unsigned int i = ELTS; i; i--) - if (elts[i - 1]) - for (unsigned int j = BITS; j; j--) - if (elts[i - 1] & (1u << (j - 1))) - return (i - 1) * BITS + (j - 1); + unsigned int count = pages.len; + for (int i = count - 1; i >= 0; i++) + if (!page_at (i).is_empty ()) + return page_map[i].major * PAGE_SIZE + page_at (i).get_max (); return INVALID; } - typedef uint32_t elt_t; - static const unsigned int MAX_G = 65536 - 1; /* XXX Fix this... */ - static const unsigned int SHIFT = 5; - static const unsigned int BITS = (1 << SHIFT); - static const unsigned int MASK = BITS - 1; - static const unsigned int ELTS = (MAX_G + 1 + (BITS - 1)) / BITS; + static const unsigned int PAGE_SIZE = sizeof (page_t) * 8; static const hb_codepoint_t INVALID = HB_SET_VALUE_INVALID; - elt_t &elt (hb_codepoint_t g) { return elts[g >> SHIFT]; } - elt_t const &elt (hb_codepoint_t g) const { return elts[g >> SHIFT]; } - elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & MASK); } - - elt_t elts[ELTS]; /* XXX 8kb */ + page_t *page_for_insert (hb_codepoint_t g) + { + page_map_t map = {major (g), pages.len}; + unsigned int i; + if (!page_map.bfind (&map, &i)) + { + if (!resize (pages.len + 1)) + return nullptr; - static_assert ((sizeof (elt_t) * 8 == BITS), ""); - static_assert ((sizeof (elt_t) * 8 * ELTS > MAX_G), ""); + pages[map.index].init (); + memmove (&page_map[i + 1], &page_map[i], (page_map.len - 1 - i) * sizeof (page_map[0])); + page_map[i] = map; + } + return &pages[page_map[i].index]; + } + page_t *page_for (hb_codepoint_t g) + { + page_map_t key = {major (g)}; + const page_map_t *found = page_map.bsearch (&key); + if (found) + return &pages[found->index]; + return nullptr; + } + const page_t *page_for (hb_codepoint_t g) const + { + page_map_t key = {major (g)}; + const page_map_t *found = page_map.bsearch (&key); + if (found) + return &pages[found->index]; + return nullptr; + } + page_t &page_at (unsigned int i) { return pages[page_map[i].index]; } + const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; } + unsigned int major (hb_codepoint_t g) const { return g / PAGE_SIZE; } }; diff --git a/test/api/test-set.c b/test/api/test-set.c index 96349512..bdc46268 100644 --- a/test/api/test-set.c +++ b/test/api/test-set.c @@ -76,12 +76,6 @@ test_set_basic (void) g_assert_cmpint (hb_set_get_min (s), ==, 10); g_assert_cmpint (hb_set_get_max (s), ==, 29); - hb_set_invert (s); - test_not_empty (s); - g_assert (!hb_set_has (s, 13)); - g_assert_cmpint (hb_set_get_min (s), ==, 0); - - hb_set_invert (s); test_not_empty (s); g_assert (hb_set_has (s, 13)); g_assert_cmpint (hb_set_get_population (s), ==, 20); commit 1d3971200be5b1c949d3eca185654e48584a0868 Author: Behdad Esfahbod <[email protected]> Date: Sun Oct 15 16:15:24 2017 +0200 Deprecate hb_set_invert() diff --git a/src/hb-deprecated.h b/src/hb-deprecated.h index 0398dfae..eac7efb4 100644 --- a/src/hb-deprecated.h +++ b/src/hb-deprecated.h @@ -34,6 +34,7 @@ #include "hb-common.h" #include "hb-unicode.h" #include "hb-font.h" +#include "hb-set.h" HB_BEGIN_DECLS @@ -54,6 +55,9 @@ hb_font_funcs_set_glyph_func (hb_font_funcs_t *ffuncs, hb_font_get_glyph_func_t func, void *user_data, hb_destroy_func_t destroy); +HB_EXTERN void +hb_set_invert (hb_set_t *set); + #endif HB_END_DECLS diff --git a/src/hb-set.cc b/src/hb-set.cc index f3fe1ba4..d33e525d 100644 --- a/src/hb-set.cc +++ b/src/hb-set.cc @@ -376,11 +376,12 @@ hb_set_symmetric_difference (hb_set_t *set, * * * Since: 0.9.10 + * + * Deprecated: 1.6.1 **/ void hb_set_invert (hb_set_t *set) { - set->invert (); } /** diff --git a/src/hb-set.h b/src/hb-set.h index 2164c1a6..2ce40607 100644 --- a/src/hb-set.h +++ b/src/hb-set.h @@ -126,9 +126,6 @@ HB_EXTERN void hb_set_symmetric_difference (hb_set_t *set, const hb_set_t *other); -HB_EXTERN void -hb_set_invert (hb_set_t *set); - HB_EXTERN unsigned int hb_set_get_population (const hb_set_t *set); commit 5e74044b6bd78c495561eb7d2981415d2c3336f4 Author: Behdad Esfahbod <[email protected]> Date: Sun Oct 15 16:15:06 2017 +0200 Add bfind() to prealloaced_array_t diff --git a/src/hb-private.hh b/src/hb-private.hh index f2290448..f8e5c8e4 100644 --- a/src/hb-private.hh +++ b/src/hb-private.hh @@ -490,23 +490,18 @@ struct hb_prealloced_array_t template <typename T> inline Type *bsearch (T *x) { - int min = 0, max = (int) this->len - 1; - while (min <= max) - { - int mid = (min + max) / 2; - int c = this->array[mid].cmp (x); - if (c < 0) - max = mid - 1; - else if (c > 0) - min = mid + 1; - else - return &this->array[mid]; - } - return nullptr; + unsigned int i; + return bfind (x, &i) ? &array[i] : nullptr; } template <typename T> inline const Type *bsearch (T *x) const { + unsigned int i; + return bfind (x, &i) ? &array[i] : nullptr; + } + template <typename T> + inline bool bfind (T *x, unsigned int *i) const + { int min = 0, max = (int) this->len - 1; while (min <= max) { @@ -517,9 +512,15 @@ struct hb_prealloced_array_t else if (c > 0) min = mid + 1; else - return &this->array[mid]; + { + *i = mid; + return true; + } } - return nullptr; + if (max < 0 || max < (int) this->len && this->array[max].cmp (x) < 0) + max++; + *i = max; + return false; } inline void finish (void) commit db5f7ef18916abb0907bc8b569a65c9c6bbd4015 Author: Behdad Esfahbod <[email protected]> Date: Sun Oct 15 16:00:22 2017 +0200 Inline another bsearch() diff --git a/src/hb-ot-map-private.hh b/src/hb-ot-map-private.hh index 22690de5..105909a1 100644 --- a/src/hb-ot-map-private.hh +++ b/src/hb-ot-map-private.hh @@ -53,8 +53,8 @@ struct hb_ot_map_t unsigned int auto_zwnj : 1; unsigned int auto_zwj : 1; - static int cmp (const feature_map_t *a, const feature_map_t *b) - { return a->tag < b->tag ? -1 : a->tag > b->tag ? 1 : 0; } + inline int cmp (const hb_tag_t *tag_) const + { return *tag_ < tag ? -1 : *tag_ > tag ? 1 : 0; } }; struct lookup_map_t { diff --git a/src/hb-private.hh b/src/hb-private.hh index 7f5cd697..f2290448 100644 --- a/src/hb-private.hh +++ b/src/hb-private.hh @@ -488,14 +488,38 @@ struct hb_prealloced_array_t } template <typename T> - inline Type *bsearch (T *key) + inline Type *bsearch (T *x) { - return (Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); + int min = 0, max = (int) this->len - 1; + while (min <= max) + { + int mid = (min + max) / 2; + int c = this->array[mid].cmp (x); + if (c < 0) + max = mid - 1; + else if (c > 0) + min = mid + 1; + else + return &this->array[mid]; + } + return nullptr; } template <typename T> - inline const Type *bsearch (T *key) const + inline const Type *bsearch (T *x) const { - return (const Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); + int min = 0, max = (int) this->len - 1; + while (min <= max) + { + int mid = (min + max) / 2; + int c = this->array[mid].cmp (x); + if (c < 0) + max = mid - 1; + else if (c > 0) + min = mid + 1; + else + return &this->array[mid]; + } + return nullptr; } inline void finish (void) commit 6fb4ac73f94636d19fcac143472b84f9d91985c9 Author: Behdad Esfahbod <[email protected]> Date: Sun Oct 15 16:00:09 2017 +0200 Add popcount for 64bit ints diff --git a/src/hb-private.hh b/src/hb-private.hh index ea6a8fa4..7f5cd697 100644 --- a/src/hb-private.hh +++ b/src/hb-private.hh @@ -333,6 +333,18 @@ _hb_popcount32 (uint32_t mask) return (((y + (y >> 3)) & 030707070707) % 077); #endif } +static inline HB_CONST_FUNC unsigned int +_hb_popcount64 (uint64_t mask) +{ +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + return __builtin_popcountl (mask); +#else + return _hb_popcount32 (mask) + _hb_popcount32 (mask >> 32); +#endif +} +template <typename T> static inline unsigned int _hb_popcount (T mask); +template <> inline unsigned int _hb_popcount<uint32_t> (uint32_t mask) { return _hb_popcount32 (mask); } +template <> inline unsigned int _hb_popcount<uint64_t> (uint64_t mask) { return _hb_popcount64 (mask); } /* Returns the number of bits needed to store number */ static inline HB_CONST_FUNC unsigned int commit 473b17af4d421f4ce7ac18c769731bb2aa4088f8 Author: Behdad Esfahbod <[email protected]> Date: Sun Oct 15 14:10:34 2017 +0200 Remove unused hb_cache_t diff --git a/src/Makefile.sources b/src/Makefile.sources index 57b7e9d3..775068ef 100644 --- a/src/Makefile.sources +++ b/src/Makefile.sources @@ -8,7 +8,6 @@ HB_BASE_sources = \ hb-buffer-private.hh \ hb-buffer-serialize.cc \ hb-buffer.cc \ - hb-cache-private.hh \ hb-common.cc \ hb-face-private.hh \ hb-face.cc \ diff --git a/src/hb-cache-private.hh b/src/hb-cache-private.hh deleted file mode 100644 index 91955b70..00000000 --- a/src/hb-cache-private.hh +++ /dev/null @@ -1,74 +0,0 @@ -/* - * Copyright © 2012 Google, Inc. - * - * This is part of HarfBuzz, a text shaping library. - * - * Permission is hereby granted, without written agreement and without - * license or royalty fees, to use, copy, modify, and distribute this - * software and its documentation for any purpose, provided that the - * above copyright notice and the following two paragraphs appear in - * all copies of this software. - * - * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR - * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES - * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN - * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH - * DAMAGE. - * - * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, - * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND - * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS - * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO - * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. - * - * Google Author(s): Behdad Esfahbod - */ - -#ifndef HB_CACHE_PRIVATE_HH -#define HB_CACHE_PRIVATE_HH - -#include "hb-private.hh" - - -/* Implements a lock-free cache for int->int functions. */ - -template <unsigned int key_bits, unsigned int value_bits, unsigned int cache_bits> -struct hb_cache_t -{ - static_assert ((key_bits >= cache_bits), ""); - static_assert ((key_bits + value_bits - cache_bits < 8 * sizeof (unsigned int)), ""); - - inline void clear (void) - { - memset (values, 255, sizeof (values)); - } - - inline bool get (unsigned int key, unsigned int *value) - { - unsigned int k = key & ((1u<<cache_bits)-1); - unsigned int v = values[k]; - if ((v >> value_bits) != (key >> cache_bits)) - return false; - *value = v & ((1u<<value_bits)-1); - return true; - } - - inline bool set (unsigned int key, unsigned int value) - { - if (unlikely ((key >> key_bits) || (value >> value_bits))) - return false; /* Overflows */ - unsigned int k = key & ((1u<<cache_bits)-1); - unsigned int v = ((key>>cache_bits)<<value_bits) | value; - values[k] = v; - return true; - } - - private: - unsigned int values[1u<<cache_bits]; -}; - -typedef hb_cache_t<21, 16, 8> hb_cmap_cache_t; -typedef hb_cache_t<16, 24, 8> hb_advance_cache_t; - - -#endif /* HB_CACHE_PRIVATE_HH */ diff --git a/src/hb-ft.cc b/src/hb-ft.cc index 6036f301..f578e9dc 100644 --- a/src/hb-ft.cc +++ b/src/hb-ft.cc @@ -33,8 +33,6 @@ #include "hb-font-private.hh" -#include "hb-cache-private.hh" // Maybe use in the future? - #include FT_ADVANCES_H #include FT_MULTIPLE_MASTERS_H #include FT_TRUETYPE_TABLES_H commit a433e60a43c4594c41a82c3741d3f870f6eec247 Author: Behdad Esfahbod <[email protected]> Date: Sun Oct 15 14:09:46 2017 +0200 Remove unused hb_frozen_set_t diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh index d7f9d82a..71a843f5 100644 --- a/src/hb-set-private.hh +++ b/src/hb-set-private.hh @@ -40,8 +40,6 @@ struct hb_set_t { - friend struct hb_frozen_set_t; - hb_object_header_t header; ASSERT_POD (); bool in_error; @@ -232,58 +230,5 @@ struct hb_set_t static_assert ((sizeof (elt_t) * 8 * ELTS > MAX_G), ""); }; -struct hb_frozen_set_t -{ - static const unsigned int SHIFT = hb_set_t::SHIFT; - static const unsigned int BITS = hb_set_t::BITS; - static const unsigned int MASK = hb_set_t::MASK; - typedef hb_set_t::elt_t elt_t; - - inline void init (const hb_set_t &set) - { - start = count = 0; - elts = nullptr; - - unsigned int max = set.get_max (); - if (max == set.INVALID) - return; - unsigned int min = set.get_min (); - const elt_t &min_elt = set.elt (min); - - start = min & ~MASK; - count = max - start + 1; - unsigned int num_elts = (count + BITS - 1) / BITS; - unsigned int elts_size = num_elts * sizeof (elt_t); - elts = (elt_t *) malloc (elts_size); - if (unlikely (!elts)) - { - start = count = 0; - return; - } - memcpy (elts, &min_elt, elts_size); - } - - inline void fini (void) - { - if (elts) - free (elts); - } - - inline bool has (hb_codepoint_t g) const - { - /* hb_codepoint_t is unsigned. */ - g -= start; - if (unlikely (g > count)) return false; - return !!(elt (g) & mask (g)); - } - - elt_t const &elt (hb_codepoint_t g) const { return elts[g >> SHIFT]; } - elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & MASK); } - - private: - hb_codepoint_t start, count; - elt_t *elts; -}; - #endif /* HB_SET_PRIVATE_HH */ commit 826a1daf2f2075459ff25a20ed8abec030d95c52 Author: Behdad Esfahbod <[email protected]> Date: Sun Oct 15 14:09:05 2017 +0200 Move set-digests into their own header file diff --git a/src/Makefile.sources b/src/Makefile.sources index 51e687b4..57b7e9d3 100644 --- a/src/Makefile.sources +++ b/src/Makefile.sources @@ -30,6 +30,7 @@ HB_BASE_sources = \ hb-ot-post-table.hh \ hb-ot-tag.cc \ hb-private.hh \ + hb-set-digest-private.hh \ hb-set-private.hh \ hb-set.cc \ hb-shape.cc \ diff --git a/src/hb-ot-layout-private.hh b/src/hb-ot-layout-private.hh index eb8cc308..460028a6 100644 --- a/src/hb-ot-layout-private.hh +++ b/src/hb-ot-layout-private.hh @@ -33,7 +33,7 @@ #include "hb-font-private.hh" #include "hb-buffer-private.hh" -#include "hb-set-private.hh" +#include "hb-set-digest-private.hh" #include "hb-open-type-private.hh" diff --git a/src/hb-set-digest-private.hh b/src/hb-set-digest-private.hh new file mode 100644 index 00000000..9135136c --- /dev/null +++ b/src/hb-set-digest-private.hh @@ -0,0 +1,144 @@ +/* + * Copyright © 2012 Google, Inc. + * + * This is part of HarfBuzz, a text shaping library. + * + * Permission is hereby granted, without written agreement and without + * license or royalty fees, to use, copy, modify, and distribute this + * software and its documentation for any purpose, provided that the + * above copyright notice and the following two paragraphs appear in + * all copies of this software. + * + * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR + * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES + * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN + * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + * + * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, + * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND + * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS + * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO + * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. + * + * Google Author(s): Behdad Esfahbod + */ + +#ifndef HB_SET_DIGEST_PRIVATE_HH +#define HB_SET_DIGEST_PRIVATE_HH + +#include "hb-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. + * + * Our filters are highly accurate if the lookup covers fairly local + * set of glyphs, but fully flooded and ineffective if coverage is + * all over the place. + * + * The frozen-set can be used instead of a digest, to trade more + * memory for 100% accuracy, but in practice, that doesn't look like + * an attractive trade-off. + */ + +template <typename mask_t, unsigned int shift> +struct hb_set_digest_lowest_bits_t +{ + ASSERT_POD (); + + static const unsigned int mask_bytes = sizeof (mask_t); + static const unsigned int mask_bits = sizeof (mask_t) * 8; + static const unsigned int num_bits = 0 + + (mask_bytes >= 1 ? 3 : 0) + + (mask_bytes >= 2 ? 1 : 0) + + (mask_bytes >= 4 ? 1 : 0) + + (mask_bytes >= 8 ? 1 : 0) + + (mask_bytes >= 16? 1 : 0) + + 0; + + static_assert ((shift < sizeof (hb_codepoint_t) * 8), ""); + static_assert ((shift + num_bits <= sizeof (hb_codepoint_t) * 8), ""); + + inline void init (void) { + mask = 0; + } + + inline void add (hb_codepoint_t g) { + mask |= mask_for (g); + } + + inline void add_range (hb_codepoint_t a, hb_codepoint_t b) { + if ((b >> shift) - (a >> shift) >= mask_bits - 1) + mask = (mask_t) -1; + else { + mask_t ma = mask_for (a); + mask_t mb = mask_for (b); + mask |= mb + (mb - ma) - (mb < ma); + } + } + + inline bool may_have (hb_codepoint_t g) const { + return !!(mask & mask_for (g)); + } + + private: + + static inline mask_t mask_for (hb_codepoint_t g) { + return ((mask_t) 1) << ((g >> shift) & (mask_bits - 1)); + } + mask_t mask; +}; + +template <typename head_t, typename tail_t> +struct hb_set_digest_combiner_t +{ + ASSERT_POD (); + + inline void init (void) { + head.init (); + tail.init (); + } + + inline void add (hb_codepoint_t g) { + head.add (g); + tail.add (g); + } + + inline void add_range (hb_codepoint_t a, hb_codepoint_t b) { + head.add_range (a, b); + tail.add_range (a, b); + } + + inline bool may_have (hb_codepoint_t g) const { + return head.may_have (g) && tail.may_have (g); + } + + private: + head_t head; + tail_t tail; +}; + + +/* + * 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; + + +#endif /* HB_SET_DIGEST_PRIVATE_HH */ diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh index fb45df9a..d7f9d82a 100644 --- a/src/hb-set-private.hh +++ b/src/hb-set-private.hh @@ -32,119 +32,6 @@ /* - * 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. - * - * Our filters are highly accurate if the lookup covers fairly local - * set of glyphs, but fully flooded and ineffective if coverage is - * all over the place. - * - * The frozen-set can be used instead of a digest, to trade more - * memory for 100% accuracy, but in practice, that doesn't look like - * an attractive trade-off. - */ - -template <typename mask_t, unsigned int shift> -struct hb_set_digest_lowest_bits_t -{ - ASSERT_POD (); - - static const unsigned int mask_bytes = sizeof (mask_t); - static const unsigned int mask_bits = sizeof (mask_t) * 8; - static const unsigned int num_bits = 0 - + (mask_bytes >= 1 ? 3 : 0) - + (mask_bytes >= 2 ? 1 : 0) - + (mask_bytes >= 4 ? 1 : 0) - + (mask_bytes >= 8 ? 1 : 0) - + (mask_bytes >= 16? 1 : 0) - + 0; - - static_assert ((shift < sizeof (hb_codepoint_t) * 8), ""); - static_assert ((shift + num_bits <= sizeof (hb_codepoint_t) * 8), ""); - - inline void init (void) { - mask = 0; - } - - inline void add (hb_codepoint_t g) { - mask |= mask_for (g); - } - - inline void add_range (hb_codepoint_t a, hb_codepoint_t b) { - if ((b >> shift) - (a >> shift) >= mask_bits - 1) - mask = (mask_t) -1; - else { - mask_t ma = mask_for (a); - mask_t mb = mask_for (b); - mask |= mb + (mb - ma) - (mb < ma); - } - } - - inline bool may_have (hb_codepoint_t g) const { - return !!(mask & mask_for (g)); - } - - private: - - static inline mask_t mask_for (hb_codepoint_t g) { - return ((mask_t) 1) << ((g >> shift) & (mask_bits - 1)); - } - mask_t mask; -}; - -template <typename head_t, typename tail_t> -struct hb_set_digest_combiner_t -{ - ASSERT_POD (); - - inline void init (void) { - head.init (); - tail.init (); - } - - inline void add (hb_codepoint_t g) { - head.add (g); - tail.add (g); - } - - inline void add_range (hb_codepoint_t a, hb_codepoint_t b) { - head.add_range (a, b); - tail.add_range (a, b); - } - - inline bool may_have (hb_codepoint_t g) const { - return head.may_have (g) && tail.may_have (g); - } - - private: - head_t head; - tail_t tail; -}; - - -/* - * 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 */
_______________________________________________ HarfBuzz mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/harfbuzz
