blob: 173fe4a2fb87929a462efe323fc69f1fd6886233 [file] [log] [blame]
/*
* Copyright © 2020 Google, Inc.
*
* This is part of HarfBuzz, a text shaping library.
*
* Permission is hereby granted, without written agreement and without
* license or royalty fees, to use, copy, modify, and distribute this
* software and its documentation for any purpose, provided that the
* above copyright notice and the following two paragraphs appear in
* all copies of this software.
*
* IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
* DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
* ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
* IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
* DAMAGE.
*
* THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
* BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
* FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
* ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
* PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
*
* Google Author(s): Garret Rieger
*/
#ifndef HB_REPACKER_HH
#define HB_REPACKER_HH
#include "hb-open-type.hh"
#include "hb-map.hh"
#include "hb-priority-queue.hh"
#include "hb-serialize.hh"
#include "hb-vector.hh"
#include "graph/graph.hh"
#include "graph/serialize.hh"
using graph::graph_t;
/*
* For a detailed writeup on the overflow resolution algorithm see:
* docs/repacker.md
*/
static inline
bool _try_isolating_subgraphs (const hb_vector_t<graph::overflow_record_t>& overflows,
graph_t& sorted_graph)
{
unsigned space = 0;
hb_set_t roots_to_isolate;
for (int i = overflows.length - 1; i >= 0; i--)
{
const graph::overflow_record_t& r = overflows[i];
unsigned root;
unsigned overflow_space = sorted_graph.space_for (r.parent, &root);
if (!overflow_space) continue;
if (sorted_graph.num_roots_for_space (overflow_space) <= 1) continue;
if (!space) {
space = overflow_space;
}
if (space == overflow_space)
roots_to_isolate.add(root);
}
if (!roots_to_isolate) return false;
unsigned maximum_to_move = hb_max ((sorted_graph.num_roots_for_space (space) / 2u), 1u);
if (roots_to_isolate.get_population () > maximum_to_move) {
// Only move at most half of the roots in a space at a time.
unsigned extra = roots_to_isolate.get_population () - maximum_to_move;
while (extra--) {
unsigned root = HB_SET_VALUE_INVALID;
roots_to_isolate.previous (&root);
roots_to_isolate.del (root);
}
}
DEBUG_MSG (SUBSET_REPACK, nullptr,
"Overflow in space %d (%d roots). Moving %d roots to space %d.",
space,
sorted_graph.num_roots_for_space (space),
roots_to_isolate.get_population (),
sorted_graph.next_space ());
sorted_graph.isolate_subgraph (roots_to_isolate);
sorted_graph.move_to_new_space (roots_to_isolate);
return true;
}
static inline
bool _process_overflows (const hb_vector_t<graph::overflow_record_t>& overflows,
hb_set_t& priority_bumped_parents,
graph_t& sorted_graph)
{
bool resolution_attempted = false;
// Try resolving the furthest overflows first.
for (int i = overflows.length - 1; i >= 0; i--)
{
const graph::overflow_record_t& r = overflows[i];
const auto& child = sorted_graph.vertices_[r.child];
if (child.is_shared ())
{
// The child object is shared, we may be able to eliminate the overflow
// by duplicating it.
if (!sorted_graph.duplicate (r.parent, r.child)) continue;
return true;
}
if (child.is_leaf () && !priority_bumped_parents.has (r.parent))
{
// This object is too far from it's parent, attempt to move it closer.
//
// TODO(garretrieger): initially limiting this to leaf's since they can be
// moved closer with fewer consequences. However, this can
// likely can be used for non-leafs as well.
// TODO(garretrieger): also try lowering priority of the parent. Make it
// get placed further up in the ordering, closer to it's children.
// this is probably preferable if the total size of the parent object
// is < then the total size of the children (and the parent can be moved).
// Since in that case moving the parent will cause a smaller increase in
// the length of other offsets.
if (sorted_graph.raise_childrens_priority (r.parent)) {
priority_bumped_parents.add (r.parent);
resolution_attempted = true;
}
continue;
}
// TODO(garretrieger): add additional offset resolution strategies
// - Promotion to extension lookups.
// - Table splitting.
}
return resolution_attempted;
}
/*
* Attempts to modify the topological sorting of the provided object graph to
* eliminate offset overflows in the links between objects of the graph. If a
* non-overflowing ordering is found the updated graph is serialized it into the
* provided serialization context.
*
* If necessary the structure of the graph may be modified in ways that do not
* affect the functionality of the graph. For example shared objects may be
* duplicated.
*
* For a detailed writeup describing how the algorithm operates see:
* docs/repacker.md
*/
template<typename T>
inline hb_blob_t*
hb_resolve_overflows (const T& packed,
hb_tag_t table_tag,
unsigned max_rounds = 20) {
graph_t sorted_graph (packed);
sorted_graph.sort_shortest_distance ();
bool will_overflow = graph::will_overflow (sorted_graph);
if (!will_overflow)
{
return graph::serialize (sorted_graph);
}
if ((table_tag == HB_OT_TAG_GPOS
|| table_tag == HB_OT_TAG_GSUB)
&& will_overflow)
{
DEBUG_MSG (SUBSET_REPACK, nullptr, "Assigning spaces to 32 bit subgraphs.");
if (sorted_graph.assign_spaces ())
sorted_graph.sort_shortest_distance ();
}
unsigned round = 0;
hb_vector_t<graph::overflow_record_t> overflows;
// TODO(garretrieger): select a good limit for max rounds.
while (!sorted_graph.in_error ()
&& graph::will_overflow (sorted_graph, &overflows)
&& round < max_rounds) {
DEBUG_MSG (SUBSET_REPACK, nullptr, "=== Overflow resolution round %d ===", round);
print_overflows (sorted_graph, overflows);
hb_set_t priority_bumped_parents;
if (!_try_isolating_subgraphs (overflows, sorted_graph))
{
// Don't count space isolation towards round limit. Only increment
// round counter if space isolation made no changes.
round++;
if (!_process_overflows (overflows, priority_bumped_parents, sorted_graph))
{
DEBUG_MSG (SUBSET_REPACK, nullptr, "No resolution available :(");
break;
}
}
sorted_graph.sort_shortest_distance ();
}
if (sorted_graph.in_error ())
{
DEBUG_MSG (SUBSET_REPACK, nullptr, "Sorted graph in error state.");
return nullptr;
}
if (graph::will_overflow (sorted_graph))
{
DEBUG_MSG (SUBSET_REPACK, nullptr, "Offset overflow resolution failed.");
return nullptr;
}
return graph::serialize (sorted_graph);
}
#endif /* HB_REPACKER_HH */