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 <[email protected]> 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 <[email protected]> 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@-555,-8+0|gid1=2+1200|gid4=3@-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@111,0+0|uni05DE=6+1391|uni05B8=5+0|uni05BC=3+0|uni05C1=3+0|uni05E9=2+1451|uni05B7=1@28,0+0|uni05D4=0+1338] commit 93099748e39740a3f6f003c83d9dec1d21660ce8 Author: Behdad Esfahbod <[email protected]> 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 <[email protected]> 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 <[email protected]> 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" _______________________________________________ HarfBuzz mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/harfbuzz
