[HarfBuzz] harfbuzz: Branch 'master' - 5 commits
Behdad Esfahbod
behdad at kemper.freedesktop.org
Tue Sep 1 08:14:28 PDT 2015
src/hb-buffer-private.hh | 2
src/hb-buffer.cc | 25 ++++
src/hb-ot-shape-complex-arabic-fallback.hh | 6 -
src/hb-ot-shape-complex-indic.cc | 2
src/hb-ot-shape-complex-myanmar.cc | 2
src/hb-ot-shape-normalize.cc | 6 -
src/hb-private.hh | 54 ++++------
test/Makefile.am | 4
test/api/Makefile.am | 4
test/shaping/Makefile.am | 4
test/shaping/fonts/sha1sum/43ef465752be9af900745f72fe29cb853a1401a5.ttf |binary
test/shaping/fonts/sha1sum/MANIFEST | 1
test/shaping/tests/cluster.tests | 1
13 files changed, 69 insertions(+), 42 deletions(-)
New commits:
commit e995d33c10a4bd9404699d01bddb2b69d811e9ed
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Tue Sep 1 16:13:32 2015 +0100
[OT] Merge clusters when reordering marks for normalization
Fixes https://bugzilla.gnome.org/show_bug.cgi?id=541608
and cluster test.
diff --git a/src/hb-buffer-private.hh b/src/hb-buffer-private.hh
index 9aa5e7d..7fed738 100644
--- a/src/hb-buffer-private.hh
+++ b/src/hb-buffer-private.hh
@@ -201,6 +201,8 @@ struct hb_buffer_t {
HB_INTERNAL scratch_buffer_t *get_scratch_buffer (unsigned int *size);
inline void clear_context (unsigned int side) { context_len[side] = 0; }
+
+ HB_INTERNAL void sort (unsigned int start, unsigned int end, int(*compar)(const hb_glyph_info_t *, const hb_glyph_info_t *));
};
diff --git a/src/hb-buffer.cc b/src/hb-buffer.cc
index 1709305..420da82 100644
--- a/src/hb-buffer.cc
+++ b/src/hb-buffer.cc
@@ -1678,3 +1678,24 @@ hb_buffer_normalize_glyphs (hb_buffer_t *buffer)
}
normalize_glyphs_cluster (buffer, start, end, backward);
}
+
+void
+hb_buffer_t::sort (unsigned int start, unsigned int end, int(*compar)(const hb_glyph_info_t *, const hb_glyph_info_t *))
+{
+ assert (!have_positions);
+ for (unsigned int i = start + 1; i < end; i++)
+ {
+ unsigned int j = i;
+ while (j > start && compar (&info[j - 1], &info[i]) > 0)
+ j--;
+ if (i == j)
+ continue;
+ /* Move item i to occupy place for item j, shift what's in between. */
+ merge_clusters (j, i + 1);
+ {
+ hb_glyph_info_t t = info[i];
+ memmove (&info[j + 1], &info[j], (i - j) * sizeof (hb_glyph_info_t));
+ info[j] = t;
+ }
+ }
+}
diff --git a/src/hb-ot-shape-normalize.cc b/src/hb-ot-shape-normalize.cc
index dff7a74..a706461 100644
--- a/src/hb-ot-shape-normalize.cc
+++ b/src/hb-ot-shape-normalize.cc
@@ -350,7 +350,7 @@ _hb_ot_shape_normalize (const hb_ot_shape_plan_t *plan,
continue;
}
- hb_stable_sort (buffer->info + i, end - i, compare_combining_class);
+ buffer->sort (i, end, compare_combining_class);
i = end;
}
commit b6d7d161a87b5dde710924e5c557d39c302f5630
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Tue Sep 1 16:12:44 2015 +0100
[tests] Add Hebrew test for normalization under cluster-level=1
Currently fails.
https://bugzilla.gnome.org/show_bug.cgi?id=541608
diff --git a/test/shaping/fonts/sha1sum/43ef465752be9af900745f72fe29cb853a1401a5.ttf b/test/shaping/fonts/sha1sum/43ef465752be9af900745f72fe29cb853a1401a5.ttf
new file mode 100644
index 0000000..649c156
Binary files /dev/null and b/test/shaping/fonts/sha1sum/43ef465752be9af900745f72fe29cb853a1401a5.ttf differ
diff --git a/test/shaping/fonts/sha1sum/MANIFEST b/test/shaping/fonts/sha1sum/MANIFEST
index 1e78f0a..1de86c8 100644
--- a/test/shaping/fonts/sha1sum/MANIFEST
+++ b/test/shaping/fonts/sha1sum/MANIFEST
@@ -4,6 +4,7 @@
270b89df543a7e48e206a2d830c0e10e5265c630.ttf
298c9e1d955f10f6f72c6915c3c6ff9bf9695cec.ttf
37033cc5cf37bb223d7355153016b6ccece93b28.ttf
+43ef465752be9af900745f72fe29cb853a1401a5.ttf
4cce528e99f600ed9c25a2b69e32eb94a03b4ae8.ttf
5028afb650b1bb718ed2131e872fbcce57828fff.ttf
57a9d9f83020155cbb1d2be1f43d82388cbecc88.ttf
diff --git a/test/shaping/tests/cluster.tests b/test/shaping/tests/cluster.tests
index 3a3a397..24f04dd 100644
--- a/test/shaping/tests/cluster.tests
+++ b/test/shaping/tests/cluster.tests
@@ -1 +1,2 @@
fonts/sha1sum/6466d38c62e73a39202435a4f73bf5d6acbb73c0.ttf:--cluster-level=2:U+0078,U+030A,U+0058,U+030A:[gid2=0+1083|gid4=1 at -555,-8+0|gid1=2+1200|gid4=3 at -614,349+0]
+fonts/sha1sum/43ef465752be9af900745f72fe29cb853a1401a5.ttf:--cluster-level=1:U+05D4,U+05B7,U+05E9,U+05BC,U+05C1,U+05B8,U+05DE,U+05B4,U+05DD:[uni05DD=8+1359|uni05B4=7 at 111,0+0|uni05DE=6+1391|uni05B8=5+0|uni05BC=3+0|uni05C1=3+0|uni05E9=2+1451|uni05B7=1 at 28,0+0|uni05D4=0+1338]
commit 93099748e39740a3f6f003c83d9dec1d21660ce8
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Tue Sep 1 16:11:27 2015 +0100
Minor
diff --git a/src/hb-private.hh b/src/hb-private.hh
index ce92b72..c081029 100644
--- a/src/hb-private.hh
+++ b/src/hb-private.hh
@@ -866,15 +866,13 @@ hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *),
continue;
/* Move item i to occupy place for item j, shift what's in between. */
{
- T t;
- t = array[i];
+ T t = array[i];
memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
array[j] = t;
}
if (array2)
{
- T2 t;
- t = array2[i];
+ T2 t = array2[i];
memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T2));
array2[j] = t;
}
commit 85846b3de7491b6a07fed6a2c0c6c1b09943b249
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Tue Sep 1 15:07:52 2015 +0100
Use insertion-sort instead of bubble-sort
Needed for upcoming merge-clusters fix.
diff --git a/src/hb-buffer.cc b/src/hb-buffer.cc
index 03fe8e1..1709305 100644
--- a/src/hb-buffer.cc
+++ b/src/hb-buffer.cc
@@ -1636,7 +1636,7 @@ normalize_glyphs_cluster (hb_buffer_t *buffer,
pos[end - 1].x_advance = total_x_advance;
pos[end - 1].y_advance = total_y_advance;
- hb_bubble_sort (buffer->info + start, end - start - 1, compare_info_codepoint, buffer->pos + start);
+ hb_stable_sort (buffer->info + start, end - start - 1, compare_info_codepoint, buffer->pos + start);
} else {
/* Transfer all cluster advance to the first glyph. */
pos[start].x_advance += total_x_advance;
@@ -1645,7 +1645,7 @@ normalize_glyphs_cluster (hb_buffer_t *buffer,
pos[i].x_offset -= total_x_advance;
pos[i].y_offset -= total_y_advance;
}
- hb_bubble_sort (buffer->info + start + 1, end - start - 1, compare_info_codepoint, buffer->pos + start + 1);
+ hb_stable_sort (buffer->info + start + 1, end - start - 1, compare_info_codepoint, buffer->pos + start + 1);
}
}
diff --git a/src/hb-ot-shape-complex-arabic-fallback.hh b/src/hb-ot-shape-complex-arabic-fallback.hh
index a77f24e..d97d285 100644
--- a/src/hb-ot-shape-complex-arabic-fallback.hh
+++ b/src/hb-ot-shape-complex-arabic-fallback.hh
@@ -75,9 +75,9 @@ arabic_fallback_synthesize_lookup_single (const hb_ot_shape_plan_t *plan HB_UNUS
if (!num_glyphs)
return NULL;
- /* Bubble-sort!
+ /* Bubble-sort or something equally good!
* May not be good-enough for presidential candidate interviews, but good-enough for us... */
- hb_bubble_sort (&glyphs[0], num_glyphs, OT::GlyphID::cmp, &substitutes[0]);
+ hb_stable_sort (&glyphs[0], num_glyphs, OT::GlyphID::cmp, &substitutes[0]);
OT::Supplier<OT::GlyphID> glyphs_supplier (glyphs, num_glyphs);
OT::Supplier<OT::GlyphID> substitutes_supplier (substitutes, num_glyphs);
@@ -126,7 +126,7 @@ arabic_fallback_synthesize_lookup_ligature (const hb_ot_shape_plan_t *plan HB_UN
first_glyphs_indirection[num_first_glyphs] = first_glyph_idx;
num_first_glyphs++;
}
- hb_bubble_sort (&first_glyphs[0], num_first_glyphs, OT::GlyphID::cmp, &first_glyphs_indirection[0]);
+ hb_stable_sort (&first_glyphs[0], num_first_glyphs, OT::GlyphID::cmp, &first_glyphs_indirection[0]);
/* Now that the first-glyphs are sorted, walk again, populate ligatures. */
for (unsigned int i = 0; i < num_first_glyphs; i++)
diff --git a/src/hb-ot-shape-complex-indic.cc b/src/hb-ot-shape-complex-indic.cc
index b7f3d5c..8b55484 100644
--- a/src/hb-ot-shape-complex-indic.cc
+++ b/src/hb-ot-shape-complex-indic.cc
@@ -1012,7 +1012,7 @@ initial_reordering_consonant_syllable (const hb_ot_shape_plan_t *plan,
info[i].syllable() = i - start;
/* Sit tight, rock 'n roll! */
- hb_bubble_sort (info + start, end - start, compare_indic_order);
+ hb_stable_sort (info + start, end - start, compare_indic_order);
/* Find base again */
base = end;
for (unsigned int i = start; i < end; i++)
diff --git a/src/hb-ot-shape-complex-myanmar.cc b/src/hb-ot-shape-complex-myanmar.cc
index 7e3ab01..9afcbf8 100644
--- a/src/hb-ot-shape-complex-myanmar.cc
+++ b/src/hb-ot-shape-complex-myanmar.cc
@@ -393,7 +393,7 @@ initial_reordering_consonant_syllable (hb_buffer_t *buffer,
buffer->merge_clusters (start, end);
/* Sit tight, rock 'n roll! */
- hb_bubble_sort (info + start, end - start, compare_myanmar_order);
+ hb_stable_sort (info + start, end - start, compare_myanmar_order);
}
static void
diff --git a/src/hb-ot-shape-normalize.cc b/src/hb-ot-shape-normalize.cc
index 111b590..dff7a74 100644
--- a/src/hb-ot-shape-normalize.cc
+++ b/src/hb-ot-shape-normalize.cc
@@ -344,15 +344,13 @@ _hb_ot_shape_normalize (const hb_ot_shape_plan_t *plan,
if (_hb_glyph_info_get_modified_combining_class (&buffer->info[end]) == 0)
break;
- /* We are going to do a bubble-sort. Only do this if the
- * sequence is short. Doing it on long sequences can result
- * in an O(n^2) DoS. */
+ /* We are going to do a O(n^2). Only do this if the sequence is short. */
if (end - i > 10) {
i = end;
continue;
}
- hb_bubble_sort (buffer->info + i, end - i, compare_combining_class);
+ hb_stable_sort (buffer->info + i, end - i, compare_combining_class);
i = end;
}
diff --git a/src/hb-private.hh b/src/hb-private.hh
index 8112934..ce92b72 100644
--- a/src/hb-private.hh
+++ b/src/hb-private.hh
@@ -855,42 +855,36 @@ hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3)
template <typename T, typename T2> static inline void
-hb_bubble_sort (T *array, unsigned int len, int(*compar)(const T *, const T *), T2 *array2)
+hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *), T2 *array2)
{
- if (unlikely (!len))
- return;
-
- unsigned int k = len - 1;
- do {
- unsigned int new_k = 0;
-
- for (unsigned int j = 0; j < k; j++)
- if (compar (&array[j], &array[j+1]) > 0)
- {
- {
- T t;
- t = array[j];
- array[j] = array[j + 1];
- array[j + 1] = t;
- }
- if (array2)
- {
- T2 t;
- t = array2[j];
- array2[j] = array2[j + 1];
- array2[j + 1] = t;
- }
-
- new_k = j;
- }
- k = new_k;
- } while (k);
+ for (unsigned int i = 1; i < len; i++)
+ {
+ unsigned int j = i;
+ while (j && compar (&array[j - 1], &array[i]) > 0)
+ j--;
+ if (i == j)
+ continue;
+ /* Move item i to occupy place for item j, shift what's in between. */
+ {
+ T t;
+ t = array[i];
+ memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
+ array[j] = t;
+ }
+ if (array2)
+ {
+ T2 t;
+ t = array2[i];
+ memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T2));
+ array2[j] = t;
+ }
+ }
}
template <typename T> static inline void
-hb_bubble_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
+hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
{
- hb_bubble_sort (array, len, compar, (int *) NULL);
+ hb_stable_sort (array, len, compar, (int *) NULL);
}
static inline hb_bool_t
commit fad2674874591b4a1df822603144c8864f5364c1
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Tue Sep 1 14:45:46 2015 +0100
Minor
diff --git a/test/Makefile.am b/test/Makefile.am
index 16a3cd2..bbd8e5f 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -2,4 +2,8 @@
SUBDIRS = api shaping
+# Convenience targets:
+lib:
+ @$(MAKE) $(AM_MAKEFLAGS) -C $(top_builddir)/src lib
+
-include $(top_srcdir)/git.mk
diff --git a/test/api/Makefile.am b/test/api/Makefile.am
index 314a09f..d7d40af 100644
--- a/test/api/Makefile.am
+++ b/test/api/Makefile.am
@@ -6,6 +6,10 @@ CLEANFILES =
DISTCLEANFILES =
MAINTAINERCLEANFILES =
+# Convenience targets:
+lib:
+ @$(MAKE) $(AM_MAKEFLAGS) -C $(top_builddir)/src lib
+
if HAVE_GLIB
AM_CPPFLAGS = -DSRCDIR="\"$(srcdir)\"" -I$(top_srcdir)/src/ -I$(top_builddir)/src/ $(GLIB_CFLAGS)
LDADD = $(top_builddir)/src/libharfbuzz.la $(GLIB_LIBS)
diff --git a/test/shaping/Makefile.am b/test/shaping/Makefile.am
index 69779b1..e34d83b 100644
--- a/test/shaping/Makefile.am
+++ b/test/shaping/Makefile.am
@@ -6,6 +6,10 @@ CLEANFILES =
DISTCLEANFILES =
MAINTAINERCLEANFILES =
+# Convenience targets:
+lib:
+ @$(MAKE) $(AM_MAKEFLAGS) -C $(top_builddir)/src lib
+
manifests:
@$(srcdir)/hb-manifest-update "$(srcdir)/texts" "$(srcdir)/fonts" "$(srcdir)/tests"
More information about the HarfBuzz
mailing list