[subset] Add table duplication overflow resolution.
diff --git a/src/hb-debug.hh b/src/hb-debug.hh
index ec3a1ff..a92614d 100644
--- a/src/hb-debug.hh
+++ b/src/hb-debug.hh
@@ -438,6 +438,10 @@
#define TRACE_SUBSET(this) hb_no_trace_t<bool> trace
#endif
+#ifndef HB_DEBUG_SUBSET_REPACK
+#define HB_DEBUG_SUBSET_REPACK (HB_DEBUG+0)
+#endif
+
#ifndef HB_DEBUG_DISPATCH
#define HB_DEBUG_DISPATCH ( \
HB_DEBUG_APPLY + \
diff --git a/src/hb-repacker.hh b/src/hb-repacker.hh
index e489494..83a4db7 100644
--- a/src/hb-repacker.hh
+++ b/src/hb-repacker.hh
@@ -39,6 +39,36 @@
// TODO(garretrieger): add an error tracking system similar to what serialize_context_t
// does.
+ struct overflow_record_t
+ {
+ unsigned parent;
+ const hb_serialize_context_t::object_t::link_t* link;
+ };
+
+ struct clone_buffer_t
+ {
+ clone_buffer_t () : head (nullptr), tail (nullptr) {}
+
+ void copy (const hb_serialize_context_t::object_t& object)
+ {
+ fini ();
+ unsigned size = object.tail - object.head;
+ head = (char*) malloc (size);
+ memcpy (head, object.head, size);
+ tail = head + size;
+ }
+
+ char* head;
+ char* tail;
+
+ void fini ()
+ {
+ if (!head) return;
+ free (head);
+ head = nullptr;
+ }
+ };
+
/*
* A topological sorting of an object graph. Ordered
* in reverse serialization order (first object in the
@@ -72,6 +102,7 @@
~graph_t ()
{
objects_.fini_deep ();
+ clone_buffers_.fini_deep ();
}
/*
@@ -214,10 +245,44 @@
}
/*
+ * Creates a copy of child and re-assigns the link from
+ * parent to the clone. The copy is a shallow copy, objects
+ * linked from child are not duplicated.
+ */
+ void duplicate (unsigned parent_idx, unsigned child_idx)
+ {
+ const auto& child = objects_[child_idx];
+ clone_buffer_t* buffer = clone_buffers_.push ();
+ buffer->copy (child);
+
+ auto* clone = objects_.push ();
+ clone->head = buffer->head;
+ clone->tail = buffer->tail;
+ for (const auto& l : child.links)
+ clone->links.push (l);
+
+ auto& parent = objects_[parent_idx];
+ unsigned clone_idx = objects_.length - 2;
+ for (unsigned i = 0; i < parent.links.length; i++)
+ {
+ auto& l = parent.links[i];
+ if (l.objidx == child_idx) l.objidx = clone_idx;
+ }
+
+ // The last object is the root of the graph, so swap back the root to the end.
+ // The root's obj idx does change, however since it's root nothing else refers to it.
+ // all other obj idx's will be unaffected.
+ hb_serialize_context_t::object_t root = objects_[objects_.length - 2];
+ objects_[objects_.length - 2] = *clone;
+ objects_[objects_.length - 1] = root;
+ }
+
+ /*
* Will any offsets overflow on graph when it's serialized?
*/
- bool will_overflow ()
+ bool will_overflow (hb_vector_t<overflow_record_t>* overflows)
{
+ if (overflows) overflows->resize (0);
hb_vector_t<unsigned> start_positions;
start_positions.resize (objects_.length);
hb_vector_t<unsigned> end_positions;
@@ -232,7 +297,7 @@
}
- for (unsigned parent_idx = 0; parent_idx < objects_.length; parent_idx++)
+ for (int parent_idx = objects_.length - 1; parent_idx >= 0; parent_idx--)
{
for (const auto& link : objects_[parent_idx].links)
{
@@ -241,11 +306,52 @@
start_positions,
end_positions);
- if (!is_valid_offset (offset, link)) return true;
+ if (is_valid_offset (offset, link))
+ continue;
+
+ if (!overflows) return true;
+
+ overflow_record_t r;
+ r.parent = parent_idx;
+ r.link = &link;
+ overflows->push (r);
}
}
- return false;
+ if (!overflows) return false;
+ return overflows->length;
+ }
+
+ /*
+ * Creates a map from objid to # of incoming edges.
+ */
+ void incoming_edge_count (hb_vector_t<unsigned>* out) const
+ {
+ out->resize (0);
+ out->resize (objects_.length);
+ for (const auto& o : objects_)
+ {
+ for (const auto& l : o.links)
+ {
+ (*out)[l.objidx] += 1;
+ }
+ }
+ }
+
+ void print_overflows (const hb_vector_t<overflow_record_t>& overflows) const
+ {
+ if (!DEBUG_ENABLED(SUBSET_REPACK)) return;
+
+ hb_vector_t<unsigned> edge_count;
+ incoming_edge_count (&edge_count);
+ for (const auto& o : overflows)
+ {
+ DEBUG_MSG (SUBSET_REPACK, nullptr, "overflow from %d => %d (%d incoming , %d outgoing)",
+ o.parent,
+ o.link->objidx,
+ edge_count[o.link->objidx],
+ objects_[o.link->objidx].links.length);
+ }
}
private:
@@ -371,22 +477,6 @@
}
}
- /*
- * Creates a map from objid to # of incoming edges.
- */
- void incoming_edge_count (hb_vector_t<unsigned>* out)
- {
- out->resize (0);
- out->resize (objects_.length);
- for (const auto& o : objects_)
- {
- for (const auto& l : o.links)
- {
- (*out)[l.objidx] += 1;
- }
- }
- }
-
template <typename O> void
serialize_link_of_type (const hb_serialize_context_t::object_t::link_t& link,
char* head,
@@ -426,6 +516,7 @@
public:
hb_vector_t<hb_serialize_context_t::object_t> objects_;
+ hb_vector_t<clone_buffer_t> clone_buffers_;
};
@@ -438,13 +529,49 @@
hb_serialize_context_t* c) {
graph_t sorted_graph (packed);
sorted_graph.sort_kahn ();
- if (sorted_graph.will_overflow ()) {
- sorted_graph.sort_shortest_distance ();
- // TODO(garretrieger): try additional offset resolution strategies
- // - Dijkstra sort of weighted graph.
- // - Promotion to extension lookups.
- // - Table duplication.
- // - Table splitting.
+ if (!sorted_graph.will_overflow (nullptr)) return;
+
+ sorted_graph.sort_shortest_distance ();
+
+ unsigned round = 0;
+ hb_vector_t<graph_t::overflow_record_t> overflows;
+ // TODO(garretrieger): select a good limit for max rounds.
+ while (sorted_graph.will_overflow (&overflows) && round++ < 10) {
+ DEBUG_MSG (SUBSET_REPACK, nullptr, "Over flow resolution round %d", round);
+ sorted_graph.print_overflows (overflows);
+
+ // TODO(garretrieger): cache ege count in the graph object . Will need to be invalidated
+ // by graph modifications.
+ hb_vector_t<unsigned> edge_count;
+ sorted_graph.incoming_edge_count (&edge_count);
+
+ // Try resolving the furthest overflow first.
+ bool resolution_attempted = false;
+ for (int i = overflows.length - 1; i >= 0; i--)
+ {
+ const graph_t::overflow_record_t& r = overflows[i];
+ if (edge_count[r.link->objidx] > 1)
+ {
+ DEBUG_MSG (SUBSET_REPACK, nullptr, "Duplicating %d => %d",
+ r.parent, r.link->objidx);
+ // The child object is shared, we may be able to eliminate the overflow
+ // by duplicating it.
+ sorted_graph.duplicate (r.parent, r.link->objidx);
+ sorted_graph.sort_shortest_distance ();
+ resolution_attempted = true;
+ break;
+ }
+
+ // TODO(garretrieger): add additional offset resolution strategies
+ // - Promotion to extension lookups.
+ // - Table splitting.
+ }
+
+ if (!resolution_attempted)
+ {
+ DEBUG_MSG (SUBSET_REPACK, nullptr, "No resolution available :(");
+ break;
+ }
}
sorted_graph.serialize (c);
diff --git a/src/test-repacker.cc b/src/test-repacker.cc
index a070cdd..e18cabd 100644
--- a/src/test-repacker.cc
+++ b/src/test-repacker.cc
@@ -75,12 +75,12 @@
static void
populate_serializer_with_overflow (hb_serialize_context_t* c)
{
- std::string large_string(40000, 'a');
+ std::string large_string(50000, 'a');
c->start_serialize<char> ();
- unsigned obj_1 = add_object (large_string.c_str(), 40000, c);
- unsigned obj_2 = add_object (large_string.c_str(), 40000, c);
- unsigned obj_3 = add_object (large_string.c_str(), 40000, c);
+ unsigned obj_1 = add_object (large_string.c_str(), 10000, c);
+ unsigned obj_2 = add_object (large_string.c_str(), 20000, c);
+ unsigned obj_3 = add_object (large_string.c_str(), 50000, c);
start_object ("abc", 3, c);
add_offset (obj_3, c);
@@ -92,6 +92,26 @@
}
static void
+populate_serializer_with_dedup_overflow (hb_serialize_context_t* c)
+{
+ std::string large_string(70000, 'a');
+ c->start_serialize<char> ();
+
+ unsigned obj_1 = add_object ("def", 3, c);
+
+ start_object (large_string.c_str(), 60000, c);
+ add_offset (obj_1, c);
+ unsigned obj_2 = c->pop_pack (false);
+
+ start_object (large_string.c_str(), 10000, c);
+ add_offset (obj_2, c);
+ add_offset (obj_1, c);
+ c->pop_pack (false);
+
+ c->end_serialize();
+}
+
+static void
populate_serializer_complex_1 (hb_serialize_context_t* c)
{
c->start_serialize<char> ();
@@ -116,7 +136,7 @@
{
c->start_serialize<char> ();
- unsigned obj_5 = add_object ("mn", 3, c);
+ unsigned obj_5 = add_object ("mn", 2, c);
unsigned obj_4 = add_object ("jkl", 3, c);
@@ -137,6 +157,36 @@
c->end_serialize();
}
+static void
+populate_serializer_complex_3 (hb_serialize_context_t* c)
+{
+ c->start_serialize<char> ();
+
+ unsigned obj_6 = add_object ("opqrst", 6, c);
+
+ unsigned obj_5 = add_object ("mn", 2, c);
+
+ start_object ("jkl", 3, c);
+ add_offset (obj_6, c);
+ unsigned obj_4 = c->pop_pack (false);
+
+ start_object ("ghi", 3, c);
+ add_offset (obj_4, c);
+ unsigned obj_3 = c->pop_pack (false);
+
+ start_object ("def", 3, c);
+ add_offset (obj_3, c);
+ unsigned obj_2 = c->pop_pack (false);
+
+ start_object ("abc", 3, c);
+ add_offset (obj_2, c);
+ add_offset (obj_4, c);
+ add_offset (obj_5, c);
+ c->pop_pack ();
+
+ c->end_serialize();
+}
+
static void test_sort_kahn_1 ()
{
size_t buffer_size = 100;
@@ -227,6 +277,79 @@
assert(graph.objects_[0].links.length == 0);
}
+static void test_duplicate_leaf ()
+{
+ size_t buffer_size = 100;
+ void* buffer = malloc (buffer_size);
+ hb_serialize_context_t c (buffer, buffer_size);
+ populate_serializer_complex_2 (&c);
+
+ graph_t graph (c.object_graph ());
+ graph.duplicate (4, 1);
+
+ assert(strncmp (graph.objects_[5].head, "abc", 3) == 0);
+ assert(graph.objects_[5].links.length == 3);
+ assert(graph.objects_[5].links[0].objidx == 3);
+ assert(graph.objects_[5].links[1].objidx == 4);
+ assert(graph.objects_[5].links[2].objidx == 0);
+
+ assert(strncmp (graph.objects_[4].head, "jkl", 3) == 0);
+ assert(graph.objects_[4].links.length == 0);
+
+ assert(strncmp (graph.objects_[3].head, "def", 3) == 0);
+ assert(graph.objects_[3].links.length == 1);
+ assert(graph.objects_[3].links[0].objidx == 2);
+
+ assert(strncmp (graph.objects_[2].head, "ghi", 3) == 0);
+ assert(graph.objects_[2].links.length == 1);
+ assert(graph.objects_[2].links[0].objidx == 1);
+
+ assert(strncmp (graph.objects_[1].head, "jkl", 3) == 0);
+ assert(graph.objects_[1].links.length == 0);
+
+ assert(strncmp (graph.objects_[0].head, "mn", 2) == 0);
+ assert(graph.objects_[0].links.length == 0);
+}
+
+static void test_duplicate_interior ()
+{
+ size_t buffer_size = 100;
+ void* buffer = malloc (buffer_size);
+ hb_serialize_context_t c (buffer, buffer_size);
+ populate_serializer_complex_3 (&c);
+
+ graph_t graph (c.object_graph ());
+ graph.duplicate (3, 2);
+
+ assert(strncmp (graph.objects_[6].head, "abc", 3) == 0);
+ assert(graph.objects_[6].links.length == 3);
+ assert(graph.objects_[6].links[0].objidx == 4);
+ assert(graph.objects_[6].links[1].objidx == 2);
+ assert(graph.objects_[6].links[2].objidx == 1);
+
+ assert(strncmp (graph.objects_[5].head, "jkl", 3) == 0);
+ assert(graph.objects_[5].links.length == 1);
+ assert(graph.objects_[5].links[0].objidx == 0);
+
+ assert(strncmp (graph.objects_[4].head, "def", 3) == 0);
+ assert(graph.objects_[4].links.length == 1);
+ assert(graph.objects_[4].links[0].objidx == 3);
+
+ assert(strncmp (graph.objects_[3].head, "ghi", 3) == 0);
+ assert(graph.objects_[3].links.length == 1);
+ assert(graph.objects_[3].links[0].objidx == 5);
+
+ assert(strncmp (graph.objects_[2].head, "jkl", 3) == 0);
+ assert(graph.objects_[2].links.length == 1);
+ assert(graph.objects_[2].links[0].objidx == 0);
+
+ assert(strncmp (graph.objects_[1].head, "mn", 2) == 0);
+ assert(graph.objects_[1].links.length == 0);
+
+ assert(strncmp (graph.objects_[0].head, "opqrst", 6) == 0);
+ assert(graph.objects_[0].links.length == 0);
+}
+
static void
test_serialize ()
{
@@ -257,7 +380,7 @@
populate_serializer_complex_2 (&c);
graph_t graph (c.object_graph ());
- assert (!graph.will_overflow ());
+ assert (!graph.will_overflow (nullptr));
}
static void test_will_overflow_2 ()
@@ -268,9 +391,63 @@
populate_serializer_with_overflow (&c);
graph_t graph (c.object_graph ());
- assert (graph.will_overflow ());
+ assert (graph.will_overflow (nullptr));
}
+static void test_will_overflow_3 ()
+{
+ size_t buffer_size = 160000;
+ void* buffer = malloc (buffer_size);
+ hb_serialize_context_t c (buffer, buffer_size);
+ populate_serializer_with_dedup_overflow (&c);
+ graph_t graph (c.object_graph ());
+
+ assert (graph.will_overflow (nullptr));
+}
+
+static void test_resolve_overflows_via_sort ()
+{
+ size_t buffer_size = 160000;
+ void* buffer = malloc (buffer_size);
+ hb_serialize_context_t c (buffer, buffer_size);
+ populate_serializer_with_overflow (&c);
+ graph_t graph (c.object_graph ());
+
+ void* out_buffer = malloc (buffer_size);
+ hb_serialize_context_t out (out_buffer, buffer_size);
+
+ hb_resolve_overflows (c.object_graph (), &out);
+ assert (!out.offset_overflow);
+ hb_bytes_t result = out.copy_bytes ();
+ assert (result.length == (80000 + 3 + 3 * 2));
+
+ result.free ();
+ free (buffer);
+ free (out_buffer);
+}
+
+static void test_resolve_overflows_via_duplication ()
+{
+ size_t buffer_size = 160000;
+ void* buffer = malloc (buffer_size);
+ hb_serialize_context_t c (buffer, buffer_size);
+ populate_serializer_with_dedup_overflow (&c);
+ graph_t graph (c.object_graph ());
+
+ void* out_buffer = malloc (buffer_size);
+ hb_serialize_context_t out (out_buffer, buffer_size);
+
+ hb_resolve_overflows (c.object_graph (), &out);
+ assert (!out.offset_overflow);
+ hb_bytes_t result = out.copy_bytes ();
+ assert (result.length == (10000 + 2 * 2 + 60000 + 2 + 3 * 2));
+
+ result.free ();
+ free (buffer);
+ free (out_buffer);
+}
+
+// TODO(garretrieger): update will_overflow tests to check the overflows array.
// TODO(garretrieger): add a test(s) using a real font.
int
@@ -282,4 +459,9 @@
test_sort_shortest ();
test_will_overflow_1 ();
test_will_overflow_2 ();
+ test_will_overflow_3 ();
+ test_resolve_overflows_via_sort ();
+ test_resolve_overflows_via_duplication ();
+ test_duplicate_leaf ();
+ test_duplicate_interior ();
}
