[repacker] Handle the case where a subgraph root has an incoming 32 and 16 bit edge.
In this case the entire subgraph from that root will be duplicated.
diff --git a/src/hb-repacker.hh b/src/hb-repacker.hh
index 5016625..dfe9c44 100644
--- a/src/hb-repacker.hh
+++ b/src/hb-repacker.hh
@@ -416,22 +416,21 @@
* that originate from outside of the subgraph will be removed by duplicating the linked to
* object.
*/
- bool isolate_subgraph (hb_set_t roots)
+ bool isolate_subgraph (const hb_set_t& roots)
{
update_parents ();
hb_hashmap_t<unsigned, unsigned> subgraph;
// incoming edges to root_idx should be all 32 bit in length so we don't need to de-dup these
// set the subgraph incoming edge count to match all of root_idx's incoming edges
- //
- // TODO(grieger): the above assumption does not always hold, as there are 16 bit incoming
- // edges, handle that case here by not including them in the count.
+ hb_set_t parents;
for (unsigned root_idx : roots)
{
- subgraph.set (root_idx, vertices_[root_idx].incoming_edges ());
+ subgraph.set (root_idx, wide_parents (root_idx, parents));
find_subgraph (root_idx, subgraph);
}
+ unsigned original_root_idx = root_idx ();
hb_hashmap_t<unsigned, unsigned> index_map;
bool made_changes = false;
for (auto entry : subgraph.iter ())
@@ -450,6 +449,14 @@
if (!made_changes)
return false;
+ if (original_root_idx != root_idx ()
+ && parents.has (original_root_idx))
+ {
+ // If the root idx has changed since parents was determined, update root idx in parents
+ parents.add (root_idx ());
+ parents.del (original_root_idx);
+ }
+
auto new_subgraph =
+ subgraph.keys ()
| hb_map([&] (unsigned node_idx) {
@@ -457,7 +464,10 @@
return node_idx;
})
;
+
remap_obj_indices (index_map, new_subgraph);
+ remap_obj_indices (index_map, parents.iter ());
+
return true;
}
@@ -538,6 +548,10 @@
vertices_[clone_idx] = *clone;
vertices_[vertices_.length - 1] = root;
+ // Since the root moved, update the parents arrays of all children on the root.
+ for (const auto& l : root.obj.links)
+ vertices_[l.objidx].remap_parent (root_idx () - 1, root_idx ());
+
return clone_idx;
}
@@ -571,15 +585,12 @@
unsigned clone_idx = duplicate (child_idx);
if (clone_idx == (unsigned) -1) return false;
// duplicate shifts the root node idx, so if parent_idx was root update it.
- unsigned original_parent_idx = parent_idx;
if (parent_idx == clone_idx) parent_idx++;
auto& parent = vertices_[parent_idx];
for (unsigned i = 0; i < parent.obj.links.length; i++)
{
auto& l = parent.obj.links[i];
- if (original_parent_idx != parent_idx)
- vertices_[l.objidx].remap_parent (original_parent_idx, parent_idx);
if (l.objidx != child_idx)
continue;
@@ -657,6 +668,26 @@
private:
+ /*
+ * Returns the numbers of incoming edges that are 32bits wide.
+ */
+ unsigned wide_parents (unsigned node_idx, hb_set_t& parents) const
+ {
+ unsigned count = 0;
+ for (unsigned p : vertices_[node_idx].parents)
+ {
+ for (const auto& l : vertices_[p].obj.links)
+ {
+ if (l.objidx == node_idx && l.width == 4 && !l.is_signed)
+ {
+ count++;
+ parents.add (p);
+ }
+ }
+ }
+ return count;
+ }
+
bool check_success (bool success)
{ return this->successful && (success || (err_other_error (), false)); }
@@ -673,7 +704,9 @@
for (unsigned p = 0; p < vertices_.length; p++)
{
for (auto& l : vertices_[p].obj.links)
+ {
vertices_[l.objidx].parents.push (p);
+ }
}
parents_invalid = false;
diff --git a/src/test-repacker.cc b/src/test-repacker.cc
index a143cac..1cfa487 100644
--- a/src/test-repacker.cc
+++ b/src/test-repacker.cc
@@ -416,6 +416,74 @@
}
static void
+populate_serializer_short_and_wide_subgraph_root (hb_serialize_context_t* c)
+{
+ std::string large_string(70000, 'a');
+ c->start_serialize<char> ();
+
+ unsigned obj_e = add_object ("e", 1, c);
+
+ start_object (large_string.c_str (), 40000, c);
+ add_offset (obj_e, c);
+ unsigned obj_c = c->pop_pack (false);
+
+ start_object (large_string.c_str (), 40000, c);
+ add_offset (obj_c, c);
+ unsigned obj_d = c->pop_pack (false);
+
+ start_object ("b", 1, c);
+ add_offset (obj_c, c);
+ add_offset (obj_e, 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_short_and_wide_subgraph_root_expected (hb_serialize_context_t* c)
+{
+ std::string large_string(70000, 'a');
+ c->start_serialize<char> ();
+
+ unsigned obj_e_prime = add_object ("e", 1, c);
+
+ start_object (large_string.c_str (), 40000, c);
+ add_offset (obj_e_prime, c);
+ unsigned obj_c_prime = c->pop_pack (false);
+
+ start_object (large_string.c_str (), 40000, c);
+ add_offset (obj_c_prime, c);
+ unsigned obj_d = c->pop_pack (false);
+
+ unsigned obj_e = add_object ("e", 1, c);
+
+ start_object (large_string.c_str (), 40000, c);
+ add_offset (obj_e, c);
+ unsigned obj_c = c->pop_pack (false);
+
+
+ start_object ("b", 1, c);
+ add_offset (obj_c, c);
+ add_offset (obj_e, c);
+ unsigned obj_b = c->pop_pack (false);
+
+ start_object ("a", 1, c);
+ add_offset (obj_b, c);
+ add_wide_offset (obj_c_prime, 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> ();
@@ -890,6 +958,42 @@
free (out_buffer);
}
+static void test_resolve_overflows_via_isolating_16bit_space_2 ()
+{
+ size_t buffer_size = 160000;
+ void* buffer = malloc (buffer_size);
+ hb_serialize_context_t c (buffer, buffer_size);
+ populate_serializer_short_and_wide_subgraph_root (&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_short_and_wide_subgraph_root_expected (&e);
+ hb_bytes_t expected_result = e.copy_bytes ();
+
+ assert (result.length == expected_result.length);
+ for (unsigned i = 0; i < expected_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 ()
{
@@ -936,6 +1040,7 @@
test_resolve_overflows_via_isolation_with_recursive_duplication ();
test_resolve_overflows_via_isolation_spaces ();
test_resolve_overflows_via_isolating_16bit_space ();
+ test_resolve_overflows_via_isolating_16bit_space_2 ();
test_duplicate_leaf ();
test_duplicate_interior ();
}