[HarfBuzz] harfbuzz: Branch 'master' - 8 commits
Behdad Esfahbod
behdad at kemper.freedesktop.org
Sun Oct 15 19:46:16 UTC 2017
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 <behdad at behdad.org>
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 <behdad at behdad.org>
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 <behdad at behdad.org>
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 <behdad at behdad.org>
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 <behdad at behdad.org>
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 <behdad at behdad.org>
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 <behdad at behdad.org>
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 <behdad at behdad.org>
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
*/
More information about the HarfBuzz
mailing list