[repacker] restrict 32 bit subgraph connected component search to only nodes reachable via directed links.
diff --git a/src/hb-repacker.hh b/src/hb-repacker.hh
index 6df7c42..5016625 100644
--- a/src/hb-repacker.hh
+++ b/src/hb-repacker.hh
@@ -374,16 +374,18 @@
{
if (l.width == 4 && !l.is_signed)
{
- visited.add (i);
roots.add (l.objidx);
+ find_subgraph (l.objidx, visited);
}
}
}
+ // Mark everything not in the subgraphs of 32 bit roots as visited.
+ // This prevents 32 bit subgraphs from being connected via nodes not in the 32 bit subgraphs.
+ visited.invert ();
+
if (!roots) return false;
- // TODO(grieger): add 16 bit only space to visited so it can't be used to connect 32 bit
- // subgraphs.
unsigned space = 0;
while (roots)
{
@@ -473,6 +475,14 @@
}
}
+ void find_subgraph (unsigned node_idx, hb_set_t& subgraph)
+ {
+ if (subgraph.has (node_idx)) return;
+ subgraph.add (node_idx);
+ for (const auto& link : vertices_[node_idx].obj.links)
+ find_subgraph (link.objidx, subgraph);
+ }
+
/*
* duplicates all nodes in the subgraph reachable from node_idx. Does not re-assign
* links. index_map is updated with mappings from old id to new id. If a duplication has already
@@ -1013,11 +1023,9 @@
|| table_tag == HB_OT_TAG_GSUB)
&& sorted_graph.will_overflow ())
{
+ DEBUG_MSG (SUBSET_REPACK, nullptr, "Assigning spaces to 32 bit subgraphs.");
if (sorted_graph.assign_32bit_spaces ())
- {
- DEBUG_MSG (SUBSET_REPACK, nullptr, "Assigning spaces to 32 bit subgraphs.");
sorted_graph.sort_shortest_distance ();
- }
}
unsigned round = 0;
diff --git a/src/test-repacker.cc b/src/test-repacker.cc
index 55c906c..a143cac 100644
--- a/src/test-repacker.cc
+++ b/src/test-repacker.cc
@@ -329,6 +329,93 @@
}
static void
+populate_serializer_spaces_16bit_connection (hb_serialize_context_t* c)
+{
+ std::string large_string(70000, 'a');
+ c->start_serialize<char> ();
+
+ unsigned obj_g = add_object ("g", 1, c);
+ unsigned obj_h = add_object ("h", 1, c);
+
+ start_object (large_string.c_str (), 40000, c);
+ add_offset (obj_g, c);
+ unsigned obj_e = c->pop_pack (false);
+
+ start_object (large_string.c_str (), 40000, c);
+ add_offset (obj_h, c);
+ unsigned obj_f = c->pop_pack (false);
+
+ start_object ("c", 1, c);
+ add_offset (obj_e, c);
+ unsigned obj_c = c->pop_pack (false);
+
+ start_object ("d", 1, c);
+ add_offset (obj_f, c);
+ unsigned obj_d = c->pop_pack (false);
+
+ start_object ("b", 1, c);
+ add_offset (obj_e, c);
+ add_offset (obj_h, c);
+ unsigned obj_b = c->pop_pack (false);
+
+ start_object ("a", 1, c);
+ add_offset (obj_b, c);
+ add_wide_offset (obj_c, c);
+ add_wide_offset (obj_d, c);
+ c->pop_pack (false);
+
+ c->end_serialize();
+}
+
+static void
+populate_serializer_spaces_16bit_connection_expected (hb_serialize_context_t* c)
+{
+ std::string large_string(70000, 'a');
+ c->start_serialize<char> ();
+
+ unsigned obj_g_prime = add_object ("g", 1, c);
+
+ start_object (large_string.c_str (), 40000, c);
+ add_offset (obj_g_prime, c);
+ unsigned obj_e_prime = c->pop_pack (false);
+
+ start_object ("c", 1, c);
+ add_offset (obj_e_prime, c);
+ unsigned obj_c = c->pop_pack (false);
+
+ unsigned obj_h_prime = add_object ("h", 1, c);
+
+ start_object (large_string.c_str (), 40000, c);
+ add_offset (obj_h_prime, c);
+ unsigned obj_f = c->pop_pack (false);
+
+ start_object ("d", 1, c);
+ add_offset (obj_f, c);
+ unsigned obj_d = c->pop_pack (false);
+
+ unsigned obj_g = add_object ("g", 1, c);
+
+ start_object (large_string.c_str (), 40000, c);
+ add_offset (obj_g, c);
+ unsigned obj_e = c->pop_pack (false);
+
+ unsigned obj_h = add_object ("h", 1, c);
+
+ start_object ("b", 1, c);
+ add_offset (obj_e, c);
+ add_offset (obj_h, c);
+ unsigned obj_b = c->pop_pack (false);
+
+ start_object ("a", 1, c);
+ add_offset (obj_b, c);
+ add_wide_offset (obj_c, c);
+ add_wide_offset (obj_d, c);
+ c->pop_pack (false);
+
+ c->end_serialize ();
+}
+
+static void
populate_serializer_complex_1 (hb_serialize_context_t* c)
{
c->start_serialize<char> ();
@@ -770,6 +857,40 @@
free (out_buffer);
}
+static void test_resolve_overflows_via_isolating_16bit_space ()
+{
+ size_t buffer_size = 160000;
+ void* buffer = malloc (buffer_size);
+ hb_serialize_context_t c (buffer, buffer_size);
+ populate_serializer_spaces_16bit_connection (&c);
+ graph_t graph (c.object_graph ());
+
+ void* out_buffer = malloc (buffer_size);
+ hb_serialize_context_t out (out_buffer, buffer_size);
+
+ assert (c.offset_overflow ());
+ hb_resolve_overflows (c.object_graph (), HB_TAG ('G', 'S', 'U', 'B'), &out, 0);
+ assert (!out.offset_overflow ());
+ hb_bytes_t result = out.copy_bytes ();
+
+ void* expected_buffer = malloc (buffer_size);
+ hb_serialize_context_t e (expected_buffer, buffer_size);
+ assert (!e.offset_overflow ());
+ populate_serializer_spaces_16bit_connection_expected (&e);
+ hb_bytes_t expected_result = e.copy_bytes ();
+
+ assert (result.length == expected_result.length);
+ for (unsigned i = 0; i < result.length; i++)
+ assert (result[i] == expected_result[i]);
+
+ result.fini ();
+ expected_result.fini ();
+ free (buffer);
+ free (expected_buffer);
+ free (out_buffer);
+}
+
+
static void test_resolve_overflows_via_isolation_spaces ()
{
size_t buffer_size = 160000;
@@ -814,6 +935,7 @@
test_resolve_overflows_via_isolation ();
test_resolve_overflows_via_isolation_with_recursive_duplication ();
test_resolve_overflows_via_isolation_spaces ();
+ test_resolve_overflows_via_isolating_16bit_space ();
test_duplicate_leaf ();
test_duplicate_interior ();
}