[repacker] add space assignment based on connected components.
Assign each connected component that is underneath one or more 32 bit offsets into a unique space. This ensures that 32 bit subgraphs which are connected are packed into the same space.
diff --git a/src/hb-repacker.hh b/src/hb-repacker.hh
index 49a4b24..fdcef0f 100644
--- a/src/hb-repacker.hh
+++ b/src/hb-repacker.hh
@@ -361,6 +361,50 @@
}
/*
+ * Assign unique space numbers to each connected subgraph of 32 bit offset(s).
+ */
+ bool assign_32bit_spaces ()
+ {
+ unsigned root_index = root_idx ();
+ hb_set_t visited;
+ hb_set_t roots;
+ for (unsigned i = 0; i <= root_index; i++)
+ {
+ for (auto& l : vertices_[i].obj.links)
+ {
+ if (l.width == 4 && !l.is_signed)
+ {
+ visited.add (i);
+ roots.add (l.objidx);
+ }
+ }
+ }
+
+ if (!roots) return false;
+
+ unsigned space = 0;
+ while (roots)
+ {
+ unsigned next = HB_SET_VALUE_INVALID;
+ if (!roots.next (&next)) break;
+
+ hb_set_t connected_roots;
+ find_connected_nodes (next, roots, visited, connected_roots);
+
+ space++;
+ for (unsigned root : connected_roots)
+ {
+ DEBUG_MSG (SUBSET_REPACK, nullptr, "Subgraph %u gets space %u", root, space);
+ vertices_[root].space = space;
+ distance_invalid = true;
+ positions_invalid = true;
+ }
+ }
+
+ return true;
+ }
+
+ /*
* Finds any links using 32 bits and isolates the subgraphs they point too.
*/
bool isolate_32bit_links ()
@@ -867,6 +911,37 @@
}
}
+ /*
+ * Finds all nodes in targets that are reachable from start_idx, nodes in visited will be skipped.
+ * For this search the graph is treated as being undirected.
+ *
+ * Connected targets will be added to connected and removed from targets. All visited nodes
+ * will be added to visited.
+ */
+ void find_connected_nodes (unsigned start_idx,
+ hb_set_t& targets,
+ hb_set_t& visited,
+ hb_set_t& connected)
+ {
+ if (visited.has (start_idx)) return;
+ visited.add (start_idx);
+
+ if (targets.has (start_idx))
+ {
+ targets.del (start_idx);
+ connected.add (start_idx);
+ }
+
+ const auto& v = vertices_[start_idx];
+
+ // Graph is treated as undirected so search children and parents of start_idx
+ for (const auto& l : v.obj.links)
+ find_connected_nodes (l.objidx, targets, visited, connected);
+
+ for (unsigned p : v.parents)
+ find_connected_nodes (p, targets, visited, connected);
+ }
+
public:
// TODO(garretrieger): make private, will need to move most of offset overflow code into graph.
hb_vector_t<vertex_t> vertices_;
@@ -956,9 +1031,9 @@
|| table_tag == HB_OT_TAG_GSUB)
&& sorted_graph.will_overflow ())
{
- if (sorted_graph.isolate_32bit_links ())
+ if (sorted_graph.assign_32bit_spaces ())
{
- DEBUG_MSG (SUBSET_REPACK, nullptr, "Isolated extension sub tables.");
+ DEBUG_MSG (SUBSET_REPACK, nullptr, "Assigning spaces to 32 bit subgraphs.");
sorted_graph.sort_shortest_distance ();
}
}
diff --git a/src/test-repacker.cc b/src/test-repacker.cc
index 32228f7..b377676 100644
--- a/src/test-repacker.cc
+++ b/src/test-repacker.cc
@@ -75,7 +75,7 @@
start_object ("abc", 3, c);
add_offset (obj_2, c);
add_offset (obj_1, c);
- c->pop_pack ();
+ c->pop_pack (false);
c->end_serialize();
}
@@ -94,7 +94,7 @@
add_offset (obj_3, c);
add_offset (obj_2, c);
add_offset (obj_1, c);
- c->pop_pack ();
+ c->pop_pack (false);
c->end_serialize();
}
@@ -129,16 +129,16 @@
start_object (large_string.c_str(), 60000, c);
add_offset (obj_4, c);
- unsigned obj_3 = c->pop_pack ();
+ unsigned obj_3 = c->pop_pack (false);
start_object (large_string.c_str(), 10000, c);
add_offset (obj_4, c);
- unsigned obj_2 = c->pop_pack ();
+ unsigned obj_2 = c->pop_pack (false);
start_object ("1", 1, c);
add_wide_offset (obj_3, c);
add_offset (obj_2, c);
- c->pop_pack ();
+ c->pop_pack (false);
c->end_serialize();
}
@@ -153,29 +153,33 @@
start_object ("e", 1, c);
add_offset (obj_f, c);
- unsigned obj_e = c->pop_pack ();
+ unsigned obj_e = c->pop_pack (false);
start_object ("cc", 2, c);
add_offset (obj_e, c);
- unsigned obj_c = c->pop_pack ();
+ unsigned obj_c = c->pop_pack (false);
start_object ("d", 1, c);
add_offset (obj_e, c);
- unsigned obj_d = c->pop_pack ();
+ unsigned obj_d = c->pop_pack (false);
+
+ start_object (large_string.c_str(), 60000, c);
+ add_offset (obj_d, c);
+ unsigned obj_h = c->pop_pack (false);
start_object (large_string.c_str(), 60000, c);
add_offset (obj_c, c);
- add_offset (obj_d, c);
- unsigned obj_b = c->pop_pack ();
+ add_offset (obj_h, c);
+ unsigned obj_b = c->pop_pack (false);
start_object (large_string.c_str(), 10000, c);
add_offset (obj_d, c);
- unsigned obj_g = c->pop_pack ();
+ unsigned obj_g = c->pop_pack (false);
start_object ("a", 1, c);
add_wide_offset (obj_b, c);
add_offset (obj_g, c);
- c->pop_pack ();
+ c->pop_pack (false);
c->end_serialize();
}
@@ -256,6 +260,57 @@
}
static void
+populate_serializer_spaces (hb_serialize_context_t* c, bool with_overflow)
+{
+ std::string large_string(70000, 'a');
+ c->start_serialize<char> ();
+
+ unsigned obj_i;
+
+ if (with_overflow)
+ obj_i = add_object ("i", 1, c);
+
+ // Space 2
+ unsigned obj_h = add_object ("h", 1, c);
+
+ start_object (large_string.c_str(), 30000, c);
+ add_offset (obj_h, c);
+ unsigned obj_e = c->pop_pack (false);
+
+ start_object ("b", 1, c);
+ add_offset (obj_e, c);
+ unsigned obj_b = c->pop_pack (false);
+
+ // Space 1
+ if (!with_overflow)
+ obj_i = add_object ("i", 1, c);
+
+ start_object (large_string.c_str(), 30000, c);
+ add_offset (obj_i, c);
+ unsigned obj_g = c->pop_pack (false);
+
+ start_object (large_string.c_str(), 30000, c);
+ add_offset (obj_i, c);
+ unsigned obj_f = c->pop_pack (false);
+
+ start_object ("d", 1, c);
+ add_offset (obj_g, c);
+ unsigned obj_d = c->pop_pack (false);
+
+ start_object ("c", 1, c);
+ add_offset (obj_f, c);
+ unsigned obj_c = c->pop_pack (false);
+
+ start_object ("a", 1, c);
+ add_wide_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> ();
@@ -270,7 +325,7 @@
start_object ("abc", 3, c);
add_offset (obj_2, c);
add_offset (obj_4, c);
- c->pop_pack ();
+ c->pop_pack (false);
c->end_serialize();
}
@@ -296,7 +351,7 @@
add_offset (obj_2, c);
add_offset (obj_4, c);
add_offset (obj_5, c);
- c->pop_pack ();
+ c->pop_pack (false);
c->end_serialize();
}
@@ -326,7 +381,7 @@
add_offset (obj_2, c);
add_offset (obj_4, c);
add_offset (obj_5, c);
- c->pop_pack ();
+ c->pop_pack (false);
c->end_serialize();
}
@@ -608,6 +663,38 @@
free (out_buffer);
}
+static void test_resolve_overflows_via_space_assignment ()
+{
+ size_t buffer_size = 160000;
+ void* buffer = malloc (buffer_size);
+ hb_serialize_context_t c (buffer, buffer_size);
+ populate_serializer_spaces (&c, true);
+ 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 (&e, false);
+ 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 ()
{
@@ -621,7 +708,7 @@
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);
+ hb_resolve_overflows (c.object_graph (), HB_TAG ('G', 'S', 'U', 'B'), &out, 1);
assert (!out.offset_overflow ());
hb_bytes_t result = out.copy_bytes ();
assert (result.length == (1 + 10000 + 60000 + 1 + 1
@@ -644,7 +731,7 @@
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);
+ hb_resolve_overflows (c.object_graph (), HB_TAG ('G', 'S', 'U', 'B'), &out, 1);
assert (!out.offset_overflow ());
hb_bytes_t result = out.copy_bytes ();
@@ -705,6 +792,7 @@
test_will_overflow_3 ();
test_resolve_overflows_via_sort ();
test_resolve_overflows_via_duplication ();
+ test_resolve_overflows_via_space_assignment ();
test_resolve_overflows_via_isolation ();
test_resolve_overflows_via_isolation_with_recursive_duplication ();
test_resolve_overflows_via_isolation_spaces ();
