diff options
Diffstat (limited to 'src/3rdparty/harfbuzz-ng/src/graph')
10 files changed, 658 insertions, 174 deletions
diff --git a/src/3rdparty/harfbuzz-ng/src/graph/classdef-graph.hh b/src/3rdparty/harfbuzz-ng/src/graph/classdef-graph.hh index c2e24a7067..da6378820b 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/classdef-graph.hh +++ b/src/3rdparty/harfbuzz-ng/src/graph/classdef-graph.hh @@ -39,6 +39,7 @@ struct ClassDefFormat1 : public OT::ClassDefFormat1_3<SmallTypes> int64_t vertex_len = vertex.obj.tail - vertex.obj.head; constexpr unsigned min_size = OT::ClassDefFormat1_3<SmallTypes>::min_size; if (vertex_len < min_size) return false; + hb_barrier (); return vertex_len >= min_size + classValue.get_size () - classValue.len.get_size (); } }; @@ -50,6 +51,7 @@ struct ClassDefFormat2 : public OT::ClassDefFormat2_4<SmallTypes> int64_t vertex_len = vertex.obj.tail - vertex.obj.head; constexpr unsigned min_size = OT::ClassDefFormat2_4<SmallTypes>::min_size; if (vertex_len < min_size) return false; + hb_barrier (); return vertex_len >= min_size + rangeRecord.get_size () - rangeRecord.len.get_size (); } }; @@ -72,7 +74,7 @@ struct ClassDef : public OT::ClassDef class_def_link->width = SmallTypes::size; class_def_link->objidx = class_def_prime_id; class_def_link->position = link_position; - class_def_prime_vertex.parents.push (parent_id); + class_def_prime_vertex.add_parent (parent_id); return true; } @@ -94,7 +96,13 @@ struct ClassDef : public OT::ClassDef } hb_bytes_t class_def_copy = serializer.copy_bytes (); - c.add_buffer ((char *) class_def_copy.arrayZ); // Give ownership to the context, it will cleanup the buffer. + if (!class_def_copy.arrayZ) return false; + // Give ownership to the context, it will cleanup the buffer. + if (!c.add_buffer ((char *) class_def_copy.arrayZ)) + { + hb_free ((char *) class_def_copy.arrayZ); + return false; + } auto& obj = c.graph.vertices_[dest_obj].obj; obj.head = (char *) class_def_copy.arrayZ; @@ -108,6 +116,7 @@ struct ClassDef : public OT::ClassDef { int64_t vertex_len = vertex.obj.tail - vertex.obj.head; if (vertex_len < OT::ClassDef::min_size) return false; + hb_barrier (); switch (u.format) { case 1: return ((ClassDefFormat1*)this)->sanitize (vertex); @@ -125,20 +134,23 @@ struct ClassDef : public OT::ClassDef struct class_def_size_estimator_t { + // TODO(garretrieger): update to support beyond64k coverage/classdef tables. + constexpr static unsigned class_def_format1_base_size = 6; + constexpr static unsigned class_def_format2_base_size = 4; + constexpr static unsigned coverage_base_size = 4; + constexpr static unsigned bytes_per_range = 6; + constexpr static unsigned bytes_per_glyph = 2; + template<typename It> class_def_size_estimator_t (It glyph_and_class) - : gids_consecutive (true), num_ranges_per_class (), glyphs_per_class () + : num_ranges_per_class (), glyphs_per_class () { - unsigned last_gid = (unsigned) -1; + reset(); for (auto p : + glyph_and_class) { unsigned gid = p.first; unsigned klass = p.second; - if (last_gid != (unsigned) -1 && gid != last_gid + 1) - gids_consecutive = false; - last_gid = gid; - hb_set_t* glyphs; if (glyphs_per_class.has (klass, &glyphs) && glyphs) { glyphs->add (gid); @@ -168,28 +180,54 @@ struct class_def_size_estimator_t } } - // Incremental increase in the Coverage and ClassDef table size - // (worst case) if all glyphs associated with 'klass' were added. - unsigned incremental_coverage_size (unsigned klass) const + void reset() { + class_def_1_size = class_def_format1_base_size; + class_def_2_size = class_def_format2_base_size; + included_glyphs.clear(); + included_classes.clear(); + } + + // Compute the size of coverage for all glyphs added via 'add_class_def_size'. + unsigned coverage_size () const { - // Coverage takes 2 bytes per glyph worst case, - return 2 * glyphs_per_class.get (klass).get_population (); + unsigned format1_size = coverage_base_size + bytes_per_glyph * included_glyphs.get_population(); + unsigned format2_size = coverage_base_size + bytes_per_range * num_glyph_ranges(); + return hb_min(format1_size, format2_size); } - // Incremental increase in the Coverage and ClassDef table size - // (worst case) if all glyphs associated with 'klass' were added. - unsigned incremental_class_def_size (unsigned klass) const + // Compute the new size of the ClassDef table if all glyphs associated with 'klass' were added. + unsigned add_class_def_size (unsigned klass) { - // ClassDef takes 6 bytes per range - unsigned class_def_2_size = 6 * num_ranges_per_class.get (klass); - if (gids_consecutive) - { - // ClassDef1 takes 2 bytes per glyph, but only can be used - // when gids are consecutive. - return hb_min (2 * glyphs_per_class.get (klass).get_population (), class_def_2_size); + if (!included_classes.has(klass)) { + hb_set_t* glyphs = nullptr; + if (glyphs_per_class.has(klass, &glyphs)) { + included_glyphs.union_(*glyphs); + } + + class_def_1_size = class_def_format1_base_size; + if (!included_glyphs.is_empty()) { + unsigned min_glyph = included_glyphs.get_min(); + unsigned max_glyph = included_glyphs.get_max(); + class_def_1_size += bytes_per_glyph * (max_glyph - min_glyph + 1); + } + + class_def_2_size += bytes_per_range * num_ranges_per_class.get (klass); + + included_classes.add(klass); } - return class_def_2_size; + return hb_min (class_def_1_size, class_def_2_size); + } + + unsigned num_glyph_ranges() const { + hb_codepoint_t start = HB_SET_VALUE_INVALID; + hb_codepoint_t end = HB_SET_VALUE_INVALID; + + unsigned count = 0; + while (included_glyphs.next_range (&start, &end)) { + count++; + } + return count; } bool in_error () @@ -205,9 +243,12 @@ struct class_def_size_estimator_t } private: - bool gids_consecutive; hb_hashmap_t<unsigned, unsigned> num_ranges_per_class; hb_hashmap_t<unsigned, hb_set_t> glyphs_per_class; + hb_set_t included_classes; + hb_set_t included_glyphs; + unsigned class_def_1_size; + unsigned class_def_2_size; }; diff --git a/src/3rdparty/harfbuzz-ng/src/graph/coverage-graph.hh b/src/3rdparty/harfbuzz-ng/src/graph/coverage-graph.hh index 49d0936315..61ca063e34 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/coverage-graph.hh +++ b/src/3rdparty/harfbuzz-ng/src/graph/coverage-graph.hh @@ -39,6 +39,7 @@ struct CoverageFormat1 : public OT::Layout::Common::CoverageFormat1_3<SmallTypes int64_t vertex_len = vertex.obj.tail - vertex.obj.head; constexpr unsigned min_size = OT::Layout::Common::CoverageFormat1_3<SmallTypes>::min_size; if (vertex_len < min_size) return false; + hb_barrier (); return vertex_len >= min_size + glyphArray.get_size () - glyphArray.len.get_size (); } }; @@ -50,6 +51,7 @@ struct CoverageFormat2 : public OT::Layout::Common::CoverageFormat2_4<SmallTypes int64_t vertex_len = vertex.obj.tail - vertex.obj.head; constexpr unsigned min_size = OT::Layout::Common::CoverageFormat2_4<SmallTypes>::min_size; if (vertex_len < min_size) return false; + hb_barrier (); return vertex_len >= min_size + rangeRecord.get_size () - rangeRecord.len.get_size (); } }; @@ -96,7 +98,7 @@ struct Coverage : public OT::Layout::Common::Coverage coverage_link->width = SmallTypes::size; coverage_link->objidx = coverage_prime_id; coverage_link->position = link_position; - coverage_prime_vertex.parents.push (parent_id); + coverage_prime_vertex.add_parent (parent_id); return (Coverage*) coverage_prime_vertex.obj.head; } @@ -118,7 +120,13 @@ struct Coverage : public OT::Layout::Common::Coverage } hb_bytes_t coverage_copy = serializer.copy_bytes (); - c.add_buffer ((char *) coverage_copy.arrayZ); // Give ownership to the context, it will cleanup the buffer. + if (!coverage_copy.arrayZ) return false; + // Give ownership to the context, it will cleanup the buffer. + if (!c.add_buffer ((char *) coverage_copy.arrayZ)) + { + hb_free ((char *) coverage_copy.arrayZ); + return false; + } auto& obj = c.graph.vertices_[dest_obj].obj; obj.head = (char *) coverage_copy.arrayZ; @@ -132,6 +140,7 @@ struct Coverage : public OT::Layout::Common::Coverage { int64_t vertex_len = vertex.obj.tail - vertex.obj.head; if (vertex_len < OT::Layout::Common::Coverage::min_size) return false; + hb_barrier (); switch (u.format) { case 1: return ((CoverageFormat1*)this)->sanitize (vertex); diff --git a/src/3rdparty/harfbuzz-ng/src/graph/graph.hh b/src/3rdparty/harfbuzz-ng/src/graph/graph.hh index dc5b6a36fe..2a9d8346c0 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/graph.hh +++ b/src/3rdparty/harfbuzz-ng/src/graph/graph.hh @@ -43,12 +43,28 @@ struct graph_t { hb_serialize_context_t::object_t obj; int64_t distance = 0 ; - int64_t space = 0 ; - hb_vector_t<unsigned> parents; + unsigned space = 0 ; unsigned start = 0; unsigned end = 0; unsigned priority = 0; - + private: + unsigned incoming_edges_ = 0; + unsigned single_parent = (unsigned) -1; + hb_hashmap_t<unsigned, unsigned> parents; + public: + + auto parents_iter () const HB_AUTO_RETURN + ( + hb_concat ( + hb_iter (&single_parent, single_parent != (unsigned) -1), + parents.keys_ref () + ) + ) + + bool in_error () const + { + return parents.in_error (); + } bool link_positions_valid (unsigned num_objects, bool removed_nil) { @@ -123,7 +139,7 @@ struct graph_t while (a || b) { DEBUG_MSG (SUBSET_REPACK, nullptr, - " 0x%x %s 0x%x", *a, (*a == *b) ? "==" : "!=", *b); + " 0x%x %s 0x%x", (unsigned) *a, (*a == *b) ? "==" : "!=", (unsigned) *b); a++; b++; } @@ -143,7 +159,9 @@ struct graph_t hb_swap (a.obj, b.obj); hb_swap (a.distance, b.distance); hb_swap (a.space, b.space); + hb_swap (a.single_parent, b.single_parent); hb_swap (a.parents, b.parents); + hb_swap (a.incoming_edges_, b.incoming_edges_); hb_swap (a.start, b.start); hb_swap (a.end, b.end); hb_swap (a.priority, b.priority); @@ -154,6 +172,7 @@ struct graph_t { hb_hashmap_t<unsigned, unsigned> result; + result.alloc (obj.real_links.length); for (const auto& l : obj.real_links) { result.set (l.position, l.objidx); } @@ -163,27 +182,92 @@ struct graph_t bool is_shared () const { - return parents.length > 1; + return parents.get_population () > 1; } unsigned incoming_edges () const { - return parents.length; + if (HB_DEBUG_SUBSET_REPACK) + { + assert (incoming_edges_ == (single_parent != (unsigned) -1) + + (parents.values_ref () | hb_reduce (hb_add, 0))); + } + return incoming_edges_; + } + + unsigned incoming_edges_from_parent (unsigned parent_index) const { + if (single_parent != (unsigned) -1) { + return single_parent == parent_index ? 1 : 0; + } + + unsigned* count; + return parents.has(parent_index, &count) ? *count : 0; + } + + void reset_parents () + { + incoming_edges_ = 0; + single_parent = (unsigned) -1; + parents.reset (); + } + + void add_parent (unsigned parent_index) + { + assert (parent_index != (unsigned) -1); + if (incoming_edges_ == 0) + { + single_parent = parent_index; + incoming_edges_ = 1; + return; + } + else if (single_parent != (unsigned) -1) + { + assert (incoming_edges_ == 1); + if (!parents.set (single_parent, 1)) + return; + single_parent = (unsigned) -1; + } + + unsigned *v; + if (parents.has (parent_index, &v)) + { + (*v)++; + incoming_edges_++; + } + else if (parents.set (parent_index, 1)) + incoming_edges_++; } void remove_parent (unsigned parent_index) { - for (unsigned i = 0; i < parents.length; i++) + if (parent_index == single_parent) { - if (parents[i] != parent_index) continue; - parents.remove_unordered (i); - break; + single_parent = (unsigned) -1; + incoming_edges_--; + return; + } + + unsigned *v; + if (parents.has (parent_index, &v)) + { + incoming_edges_--; + if (*v > 1) + (*v)--; + else + parents.del (parent_index); + + if (incoming_edges_ == 1) + { + single_parent = *parents.keys (); + parents.reset (); + } } } void remove_real_link (unsigned child_index, const void* offset) { - for (unsigned i = 0; i < obj.real_links.length; i++) + unsigned count = obj.real_links.length; + for (unsigned i = 0; i < count; i++) { auto& link = obj.real_links.arrayZ[i]; if (link.objidx != child_index) @@ -197,18 +281,53 @@ struct graph_t } } - void remap_parents (const hb_vector_t<unsigned>& id_map) + bool remap_parents (const hb_vector_t<unsigned>& id_map) { - for (unsigned i = 0; i < parents.length; i++) - parents[i] = id_map[parents[i]]; + if (single_parent != (unsigned) -1) + { + assert (single_parent < id_map.length); + single_parent = id_map[single_parent]; + return true; + } + + hb_hashmap_t<unsigned, unsigned> new_parents; + new_parents.alloc (parents.get_population ()); + for (auto _ : parents) + { + assert (_.first < id_map.length); + assert (!new_parents.has (id_map[_.first])); + new_parents.set (id_map[_.first], _.second); + } + + if (parents.in_error() || new_parents.in_error ()) + return false; + + parents = std::move (new_parents); + return true; } void remap_parent (unsigned old_index, unsigned new_index) { - for (unsigned i = 0; i < parents.length; i++) + if (single_parent != (unsigned) -1) { - if (parents[i] == old_index) - parents[i] = new_index; + if (single_parent == old_index) + single_parent = new_index; + return; + } + + const unsigned *pv; + if (parents.has (old_index, &pv)) + { + unsigned v = *pv; + if (!parents.set (new_index, v)) + incoming_edges_ -= v; + parents.del (old_index); + + if (incoming_edges_ == 1) + { + single_parent = *parents.keys (); + parents.reset (); + } } } @@ -224,6 +343,16 @@ struct graph_t return true; } + bool give_max_priority () + { + bool result = false; + while (!has_max_priority()) { + result = true; + priority++; + } + return result; + } + bool has_max_priority () const { return priority >= 3; } @@ -328,11 +457,12 @@ struct graph_t bool removed_nil = false; vertices_.alloc (objects.length); vertices_scratch_.alloc (objects.length); - for (unsigned i = 0; i < objects.length; i++) + unsigned count = objects.length; + for (unsigned i = 0; i < count; i++) { // If this graph came from a serialization buffer object 0 is the // nil object. We don't need it for our purposes here so drop it. - if (i == 0 && !objects[i]) + if (i == 0 && !objects.arrayZ[i]) { removed_nil = true; continue; @@ -340,9 +470,9 @@ struct graph_t vertex_t* v = vertices_.push (); if (check_success (!vertices_.in_error ())) - v->obj = *objects[i]; + v->obj = *objects.arrayZ[i]; - check_success (v->link_positions_valid (objects.length, removed_nil)); + check_success (v->link_positions_valid (count, removed_nil)); if (!removed_nil) continue; // Fix indices to account for removed nil object. @@ -354,7 +484,6 @@ struct graph_t ~graph_t () { - vertices_.fini (); for (char* b : buffers) hb_free (b); } @@ -364,6 +493,18 @@ struct graph_t return root ().equals (other.root (), *this, other, 0); } + void print () const { + for (int i = vertices_.length - 1; i >= 0; i--) + { + const auto& v = vertices_[i]; + printf("%d: %u [", i, (unsigned int)v.table_size()); + for (const auto &l : v.obj.real_links) { + printf("%u, ", l.objidx); + } + printf("]\n"); + } + } + // Sorts links of all objects in a consistent manner and zeroes all offsets. void normalize () { @@ -396,9 +537,10 @@ struct graph_t return vertices_[i].obj; } - void add_buffer (char* buffer) + bool add_buffer (char* buffer) { buffers.push (buffer); + return !buffers.in_error (); } /* @@ -414,7 +556,7 @@ struct graph_t link->width = 2; link->objidx = child_id; link->position = (char*) offset - (char*) v.obj.head; - vertices_[child_id].parents.push (parent_id); + vertices_[child_id].add_parent (parent_id); } /* @@ -443,7 +585,8 @@ struct graph_t update_distances (); - hb_priority_queue_t queue; + hb_priority_queue_t<int64_t> queue; + queue.alloc (vertices_.length); hb_vector_t<vertex_t> &sorted_graph = vertices_scratch_; if (unlikely (!check_success (sorted_graph.resize (vertices_.length)))) return; hb_vector_t<unsigned> id_map; @@ -460,7 +603,7 @@ struct graph_t { unsigned next_id = queue.pop_minimum().second; - hb_swap (sorted_graph[new_id], vertices_[next_id]); + sorted_graph[new_id] = std::move (vertices_[next_id]); const vertex_t& next = sorted_graph[new_id]; if (unlikely (!check_success(new_id >= 0))) { @@ -488,8 +631,8 @@ struct graph_t check_success (!queue.in_error ()); check_success (!sorted_graph.in_error ()); - remap_all_obj_indices (id_map, &sorted_graph); - hb_swap (vertices_, sorted_graph); + check_success (remap_all_obj_indices (id_map, &sorted_graph)); + vertices_ = std::move (sorted_graph); if (!check_success (new_id == -1)) print_orphaned_nodes (); @@ -579,8 +722,8 @@ struct graph_t const auto& node = object (node_idx); if (offset < node.head || offset >= node.tail) return -1; - unsigned length = node.real_links.length; - for (unsigned i = 0; i < length; i++) + unsigned count = node.real_links.length; + for (unsigned i = 0; i < count; i++) { // Use direct access for increased performance, this is a hot method. const auto& link = node.real_links.arrayZ[i]; @@ -600,7 +743,7 @@ struct graph_t { unsigned child_idx = index_for_offset (node_idx, offset); auto& child = vertices_[child_idx]; - for (unsigned p : child.parents) + for (unsigned p : child.parents_iter ()) { if (p != node_idx) { return duplicate (node_idx, child_idx); @@ -683,12 +826,15 @@ struct graph_t subgraph.set (root_idx, wide_parents (root_idx, parents)); find_subgraph (root_idx, subgraph); } + if (subgraph.in_error ()) + return false; unsigned original_root_idx = root_idx (); hb_map_t index_map; bool made_changes = false; for (auto entry : subgraph.iter ()) { + assert (entry.first < vertices_.length); const auto& node = vertices_[entry.first]; unsigned subgraph_incoming_edges = entry.second; @@ -700,6 +846,9 @@ struct graph_t } } + if (in_error ()) + return false; + if (!made_changes) return false; @@ -724,8 +873,7 @@ struct graph_t remap_obj_indices (index_map, parents.iter (), true); // Update roots set with new indices as needed. - uint32_t next = HB_SET_VALUE_INVALID; - while (roots.next (&next)) + for (auto next : roots) { const uint32_t *v; if (index_map.has (next, &v)) @@ -742,10 +890,10 @@ struct graph_t { for (const auto& link : vertices_[node_idx].obj.all_links ()) { - const uint32_t *v; + hb_codepoint_t *v; if (subgraph.has (link.objidx, &v)) { - subgraph.set (link.objidx, *v + 1); + (*v)++; continue; } subgraph.set (link.objidx, 1); @@ -817,7 +965,7 @@ struct graph_t new_link->position = (const char*) new_offset - (const char*) new_v.obj.head; auto& child = vertices_[child_id]; - child.parents.push (new_parent_idx); + child.add_parent (new_parent_idx); old_v.remove_real_link (child_id, old_offset); child.remove_parent (old_parent_idx); @@ -833,7 +981,11 @@ struct graph_t if (index_map.has (node_idx)) return; - index_map.set (node_idx, duplicate (node_idx)); + unsigned clone_idx = duplicate (node_idx); + if (!check_success (clone_idx != (unsigned) -1)) + return; + + index_map.set (node_idx, clone_idx); for (const auto& l : object (node_idx).all_links ()) { duplicate_subgraph (l.objidx, index_map); } @@ -857,18 +1009,18 @@ struct graph_t clone->obj.tail = child.obj.tail; clone->distance = child.distance; clone->space = child.space; - clone->parents.reset (); + clone->reset_parents (); unsigned clone_idx = vertices_.length - 2; for (const auto& l : child.obj.real_links) { clone->obj.real_links.push (l); - vertices_[l.objidx].parents.push (clone_idx); + vertices_[l.objidx].add_parent (clone_idx); } for (const auto& l : child.obj.virtual_links) { clone->obj.virtual_links.push (l); - vertices_[l.objidx].parents.push (clone_idx); + vertices_[l.objidx].add_parent (clone_idx); } check_success (!clone->obj.real_links.in_error ()); @@ -890,6 +1042,11 @@ struct graph_t * 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. + * + * Returns the index of the newly created duplicate. + * + * If the child_idx only has incoming edges from parent_idx, this + * will do nothing and return the original child_idx. */ unsigned duplicate_if_shared (unsigned parent_idx, unsigned child_idx) { @@ -903,31 +1060,33 @@ struct graph_t * 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. + * + * Returns the index of the newly created duplicate. + * + * If the child_idx only has incoming edges from parent_idx, + * duplication isn't possible and this will return -1. */ unsigned duplicate (unsigned parent_idx, unsigned child_idx) { update_parents (); - unsigned links_to_child = 0; - for (const auto& l : vertices_[parent_idx].obj.all_links ()) - { - if (l.objidx == child_idx) links_to_child++; - } + const auto& child = vertices_[child_idx]; + unsigned links_to_child = child.incoming_edges_from_parent(parent_idx); - if (vertices_[child_idx].incoming_edges () <= links_to_child) + if (child.incoming_edges () <= links_to_child) { // Can't duplicate this node, doing so would orphan the original one as all remaining links // to child are from parent. - DEBUG_MSG (SUBSET_REPACK, nullptr, " Not duplicating %d => %d", + DEBUG_MSG (SUBSET_REPACK, nullptr, " Not duplicating %u => %u", parent_idx, child_idx); return -1; } - DEBUG_MSG (SUBSET_REPACK, nullptr, " Duplicating %d => %d", + DEBUG_MSG (SUBSET_REPACK, nullptr, " Duplicating %u => %u", parent_idx, child_idx); unsigned clone_idx = duplicate (child_idx); - if (clone_idx == (unsigned) -1) return false; + if (clone_idx == (unsigned) -1) return -1; // duplicate shifts the root node idx, so if parent_idx was root update it. if (parent_idx == clone_idx) parent_idx++; @@ -943,6 +1102,62 @@ struct graph_t return clone_idx; } + /* + * Creates a copy of child and re-assigns the links from + * parents to the clone. The copy is a shallow copy, objects + * linked from child are not duplicated. + * + * Returns the index of the newly created duplicate. + * + * If the child_idx only has incoming edges from parents, + * duplication isn't possible or duplication fails and this will + * return -1. + */ + unsigned duplicate (const hb_set_t* parents, unsigned child_idx) + { + if (parents->is_empty()) { + return -1; + } + + update_parents (); + + const auto& child = vertices_[child_idx]; + unsigned links_to_child = 0; + unsigned last_parent = parents->get_max(); + unsigned first_parent = parents->get_min(); + for (unsigned parent_idx : *parents) { + links_to_child += child.incoming_edges_from_parent(parent_idx); + } + + if (child.incoming_edges () <= links_to_child) + { + // Can't duplicate this node, doing so would orphan the original one as all remaining links + // to child are from parent. + DEBUG_MSG (SUBSET_REPACK, nullptr, " Not duplicating %u, ..., %u => %u", first_parent, last_parent, child_idx); + return -1; + } + + DEBUG_MSG (SUBSET_REPACK, nullptr, " Duplicating %u, ..., %u => %u", first_parent, last_parent, child_idx); + + unsigned clone_idx = duplicate (child_idx); + if (clone_idx == (unsigned) -1) return false; + + for (unsigned parent_idx : *parents) { + // duplicate shifts the root node idx, so if parent_idx was root update it. + if (parent_idx == clone_idx) parent_idx++; + auto& parent = vertices_[parent_idx]; + for (auto& l : parent.obj.all_links_writer ()) + { + if (l.objidx != child_idx) + continue; + + reassign_link (l, parent_idx, clone_idx); + } + } + + return clone_idx; + } + /* * Adds a new node to the graph, not connected to anything. @@ -981,7 +1196,7 @@ struct graph_t */ bool raise_childrens_priority (unsigned parent_idx) { - DEBUG_MSG (SUBSET_REPACK, nullptr, " Raising priority of all children of %d", + DEBUG_MSG (SUBSET_REPACK, nullptr, " Raising priority of all children of %u", parent_idx); // This operation doesn't change ordering until a sort is run, so no need // to invalidate positions. It does not change graph structure so no need @@ -997,13 +1212,13 @@ struct graph_t { update_parents(); - if (root().parents) + if (root().incoming_edges ()) // Root cannot have parents. return false; for (unsigned i = 0; i < root_idx (); i++) { - if (!vertices_[i].parents) + if (!vertices_[i].incoming_edges ()) return false; } return true; @@ -1067,14 +1282,14 @@ struct graph_t parents_invalid = true; update_parents(); - if (root().parents) { + if (root().incoming_edges ()) { DEBUG_MSG (SUBSET_REPACK, nullptr, "Root node has incoming edges."); } for (unsigned i = 0; i < root_idx (); i++) { const auto& v = vertices_[i]; - if (!v.parents) + if (!v.incoming_edges ()) DEBUG_MSG (SUBSET_REPACK, nullptr, "Node %u is orphaned.", i); } } @@ -1106,6 +1321,8 @@ struct graph_t unsigned space_for (unsigned index, unsigned* root = nullptr) const { + loop: + assert (index < vertices_.length); const auto& node = vertices_[index]; if (node.space) { @@ -1114,22 +1331,24 @@ struct graph_t return node.space; } - if (!node.parents) + if (!node.incoming_edges ()) { if (root) *root = index; return 0; } - return space_for (node.parents[0], root); + index = *node.parents_iter (); + goto loop; } void err_other_error () { this->successful = false; } size_t total_size_in_bytes () const { size_t total_size = 0; - for (unsigned i = 0; i < vertices_.length; i++) { - size_t size = vertices_[i].obj.tail - vertices_[i].obj.head; + unsigned count = vertices_.length; + for (unsigned i = 0; i < count; i++) { + size_t size = vertices_.arrayZ[i].obj.tail - vertices_.arrayZ[i].obj.head; total_size += size; } return total_size; @@ -1144,12 +1363,8 @@ struct graph_t unsigned wide_parents (unsigned node_idx, hb_set_t& parents) const { unsigned count = 0; - hb_set_t visited; - for (unsigned p : vertices_[node_idx].parents) + for (unsigned p : vertices_[node_idx].parents_iter ()) { - if (visited.has (p)) continue; - visited.add (p); - // Only real links can be wide for (const auto& l : vertices_[p].obj.real_links) { @@ -1176,21 +1391,21 @@ struct graph_t { if (!parents_invalid) return; - for (unsigned i = 0; i < vertices_.length; i++) - vertices_[i].parents.reset (); + unsigned count = vertices_.length; - for (unsigned p = 0; p < vertices_.length; p++) + for (unsigned i = 0; i < count; i++) + vertices_.arrayZ[i].reset_parents (); + + for (unsigned p = 0; p < count; p++) { - for (auto& l : vertices_[p].obj.all_links ()) - { - vertices_[l.objidx].parents.push (p); - } + for (auto& l : vertices_.arrayZ[p].obj.all_links ()) + vertices_[l.objidx].add_parent (p); } - for (unsigned i = 0; i < vertices_.length; i++) + for (unsigned i = 0; i < count; i++) // parents arrays must be accurate or downstream operations like cycle detection // and sorting won't work correctly. - check_success (!vertices_[i].parents.in_error ()); + check_success (!vertices_.arrayZ[i].in_error ()); parents_invalid = false; } @@ -1232,15 +1447,13 @@ struct graph_t // According to https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf // for practical performance this is faster then using a more advanced queue // (such as a fibonacci queue) with a fast decrease priority. - for (unsigned i = 0; i < vertices_.length; i++) - { - if (i == vertices_.length - 1) - vertices_[i].distance = 0; - else - vertices_[i].distance = hb_int_max (int64_t); - } + unsigned count = vertices_.length; + for (unsigned i = 0; i < count; i++) + vertices_.arrayZ[i].distance = hb_int_max (int64_t); + vertices_.tail ().distance = 0; - hb_priority_queue_t queue; + hb_priority_queue_t<int64_t> queue; + queue.alloc (count); queue.insert (0, vertices_.length - 1); hb_vector_t<bool> visited; @@ -1258,15 +1471,15 @@ struct graph_t { if (visited[link.objidx]) continue; - const auto& child = vertices_[link.objidx].obj; + const auto& child = vertices_.arrayZ[link.objidx].obj; unsigned link_width = link.width ? link.width : 4; // treat virtual offsets as 32 bits wide int64_t child_weight = (child.tail - child.head) + - ((int64_t) 1 << (link_width * 8)) * (vertices_[link.objidx].space + 1); + ((int64_t) 1 << (link_width * 8)) * (vertices_.arrayZ[link.objidx].space + 1); int64_t child_distance = next_distance + child_weight; - if (child_distance < vertices_[link.objidx].distance) + if (child_distance < vertices_.arrayZ[link.objidx].distance) { - vertices_[link.objidx].distance = child_distance; + vertices_.arrayZ[link.objidx].distance = child_distance; queue.insert (child_distance, link.objidx); } } @@ -1294,7 +1507,7 @@ struct graph_t unsigned old_idx = link.objidx; link.objidx = new_idx; vertices_[old_idx].remove_parent (parent_idx); - vertices_[new_idx].parents.push (parent_idx); + vertices_[new_idx].add_parent (parent_idx); } /* @@ -1322,17 +1535,20 @@ struct graph_t /* * Updates all objidx's in all links using the provided mapping. */ - void remap_all_obj_indices (const hb_vector_t<unsigned>& id_map, + bool remap_all_obj_indices (const hb_vector_t<unsigned>& id_map, hb_vector_t<vertex_t>* sorted_graph) const { - for (unsigned i = 0; i < sorted_graph->length; i++) + unsigned count = sorted_graph->length; + for (unsigned i = 0; i < count; i++) { - (*sorted_graph)[i].remap_parents (id_map); - for (auto& link : (*sorted_graph)[i].obj.all_links_writer ()) + if (!(*sorted_graph)[i].remap_parents (id_map)) + return false; + for (auto& link : sorted_graph->arrayZ[i].obj.all_links_writer ()) { link.objidx = id_map[link.objidx]; } } + return true; } /* @@ -1363,7 +1579,7 @@ struct graph_t for (const auto& l : v.obj.all_links ()) find_connected_nodes (l.objidx, targets, visited, connected); - for (unsigned p : v.parents) + for (unsigned p : v.parents_iter ()) find_connected_nodes (p, targets, visited, connected); } diff --git a/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-context.cc b/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-context.cc index b2044426d4..d66eb49cfd 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-context.cc +++ b/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-context.cc @@ -52,7 +52,11 @@ unsigned gsubgpos_graph_context_t::create_node (unsigned size) if (!buffer) return -1; - add_buffer (buffer); + if (!add_buffer (buffer)) { + // Allocation did not get stored for freeing later. + hb_free (buffer); + return -1; + } return graph.new_node (buffer, buffer + size); } diff --git a/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-context.hh b/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-context.hh index 9fe9662e64..b25d538fe3 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-context.hh +++ b/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-context.hh @@ -40,16 +40,16 @@ struct gsubgpos_graph_context_t graph_t& graph; unsigned lookup_list_index; hb_hashmap_t<unsigned, graph::Lookup*> lookups; - + hb_hashmap_t<unsigned, unsigned> subtable_to_extension; HB_INTERNAL gsubgpos_graph_context_t (hb_tag_t table_tag_, graph_t& graph_); HB_INTERNAL unsigned create_node (unsigned size); - void add_buffer (char* buffer) + bool add_buffer (char* buffer) { - graph.add_buffer (buffer); + return graph.add_buffer (buffer); } private: diff --git a/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-graph.hh b/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-graph.hh index c170638409..0f6d5662e0 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-graph.hh +++ b/src/3rdparty/harfbuzz-ng/src/graph/gsubgpos-graph.hh @@ -76,6 +76,7 @@ struct Lookup : public OT::Lookup { int64_t vertex_len = vertex.obj.tail - vertex.obj.head; if (vertex_len < OT::Lookup::min_size) return false; + hb_barrier (); return vertex_len >= this->get_size (); } @@ -166,7 +167,7 @@ struct Lookup : public OT::Lookup } if (all_new_subtables) { - add_sub_tables (c, this_index, type, all_new_subtables); + return add_sub_tables (c, this_index, type, all_new_subtables); } return true; @@ -184,7 +185,7 @@ struct Lookup : public OT::Lookup return sub_table->split_subtables (c, parent_idx, objidx); } - void add_sub_tables (gsubgpos_graph_context_t& c, + bool add_sub_tables (gsubgpos_graph_context_t& c, unsigned this_index, unsigned type, hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>>& subtable_ids) @@ -200,7 +201,12 @@ struct Lookup : public OT::Lookup size_t new_size = v.table_size () + new_subtable_count * OT::Offset16::static_size; char* buffer = (char*) hb_calloc (1, new_size); - c.add_buffer (buffer); + if (!buffer) return false; + if (!c.add_buffer (buffer)) + { + hb_free (buffer); + return false; + } hb_memcpy (buffer, v.obj.head, v.table_size()); v.obj.head = buffer; @@ -220,7 +226,7 @@ struct Lookup : public OT::Lookup if (is_ext) { unsigned ext_id = create_extension_subtable (c, subtable_id, type); - c.graph.vertices_[subtable_id].parents.push (ext_id); + c.graph.vertices_[subtable_id].add_parent (ext_id); subtable_id = ext_id; } @@ -229,7 +235,7 @@ struct Lookup : public OT::Lookup link->objidx = subtable_id; link->position = (char*) &new_lookup->subTable[offset_index++] - (char*) new_lookup; - c.graph.vertices_[subtable_id].parents.push (this_index); + c.graph.vertices_[subtable_id].add_parent (this_index); } } @@ -239,6 +245,7 @@ struct Lookup : public OT::Lookup // The head location of the lookup has changed, invalidating the lookups map entry // in the context. Update the map. c.lookups.set (this_index, new_lookup); + return true; } void fix_existing_subtable_links (gsubgpos_graph_context_t& c, @@ -293,24 +300,35 @@ struct Lookup : public OT::Lookup unsigned subtable_index) { unsigned type = lookupType; + unsigned ext_index = -1; + unsigned* existing_ext_index = nullptr; + if (c.subtable_to_extension.has(subtable_index, &existing_ext_index)) { + ext_index = *existing_ext_index; + } else { + ext_index = create_extension_subtable(c, subtable_index, type); + c.subtable_to_extension.set(subtable_index, ext_index); + } - unsigned ext_index = create_extension_subtable(c, subtable_index, type); if (ext_index == (unsigned) -1) return false; + auto& subtable_vertex = c.graph.vertices_[subtable_index]; auto& lookup_vertex = c.graph.vertices_[lookup_index]; for (auto& l : lookup_vertex.obj.real_links.writer ()) { - if (l.objidx == subtable_index) + if (l.objidx == subtable_index) { // Change lookup to point at the extension. l.objidx = ext_index; + if (existing_ext_index) + subtable_vertex.remove_parent(lookup_index); + } } // Make extension point at the subtable. auto& ext_vertex = c.graph.vertices_[ext_index]; - auto& subtable_vertex = c.graph.vertices_[subtable_index]; - ext_vertex.parents.push (lookup_index); - subtable_vertex.remap_parent (lookup_index, ext_index); + ext_vertex.add_parent (lookup_index); + if (!existing_ext_index) + subtable_vertex.remap_parent (lookup_index, ext_index); return true; } @@ -334,6 +352,7 @@ struct LookupList : public OT::LookupList<T> { int64_t vertex_len = vertex.obj.tail - vertex.obj.head; if (vertex_len < OT::LookupList<T>::min_size) return false; + hb_barrier (); return vertex_len >= OT::LookupList<T>::item_size * this->len; } }; @@ -347,6 +366,7 @@ struct GSTAR : public OT::GSUBGPOS GSTAR* gstar = (GSTAR*) r.obj.head; if (!gstar || !gstar->sanitize (r)) return nullptr; + hb_barrier (); return gstar; } @@ -366,6 +386,7 @@ struct GSTAR : public OT::GSUBGPOS { int64_t len = vertex.obj.tail - vertex.obj.head; if (len < OT::GSUBGPOS::min_size) return false; + hb_barrier (); return len >= get_size (); } diff --git a/src/3rdparty/harfbuzz-ng/src/graph/markbasepos-graph.hh b/src/3rdparty/harfbuzz-ng/src/graph/markbasepos-graph.hh index 84ef5f71b9..fb4166128a 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/markbasepos-graph.hh +++ b/src/3rdparty/harfbuzz-ng/src/graph/markbasepos-graph.hh @@ -40,6 +40,7 @@ struct AnchorMatrix : public OT::Layout::GPOS_impl::AnchorMatrix { int64_t vertex_len = vertex.obj.tail - vertex.obj.head; if (vertex_len < AnchorMatrix::min_size) return false; + hb_barrier (); return vertex_len >= AnchorMatrix::min_size + OT::Offset16::static_size * class_count * this->rows; @@ -128,6 +129,7 @@ struct MarkArray : public OT::Layout::GPOS_impl::MarkArray int64_t vertex_len = vertex.obj.tail - vertex.obj.head; unsigned min_size = MarkArray::min_size; if (vertex_len < min_size) return false; + hb_barrier (); return vertex_len >= get_size (); } @@ -217,7 +219,7 @@ struct MarkBasePosFormat1 : public OT::Layout::GPOS_impl::MarkBasePosFormat1_2<S const unsigned base_coverage_id = c.graph.index_for_offset (this_index, &baseCoverage); const unsigned base_size = - OT::Layout::GPOS_impl::PairPosFormat1_3<SmallTypes>::min_size + + OT::Layout::GPOS_impl::MarkBasePosFormat1_2<SmallTypes>::min_size + MarkArray::min_size + AnchorMatrix::min_size + c.graph.vertices_[base_coverage_id].table_size (); @@ -318,8 +320,11 @@ struct MarkBasePosFormat1 : public OT::Layout::GPOS_impl::MarkBasePosFormat1_2<S { hb_vector_t<class_info_t> class_to_info; - unsigned class_count= classCount; - class_to_info.resize (class_count); + unsigned class_count = classCount; + if (!class_count) return class_to_info; + + if (!class_to_info.resize (class_count)) + return hb_vector_t<class_info_t>(); auto mark_array = c.graph.as_table<MarkArray> (this_index, &markArray); if (!mark_array) return hb_vector_t<class_info_t> (); @@ -327,6 +332,7 @@ struct MarkBasePosFormat1 : public OT::Layout::GPOS_impl::MarkBasePosFormat1_2<S for (unsigned mark = 0; mark < mark_count; mark++) { unsigned klass = (*mark_array.table)[mark].get_class (); + if (klass >= class_count) continue; class_to_info[klass].marks.add (mark); } @@ -335,6 +341,7 @@ struct MarkBasePosFormat1 : public OT::Layout::GPOS_impl::MarkBasePosFormat1_2<S unsigned mark = (link.position - 2) / OT::Layout::GPOS_impl::MarkRecord::static_size; unsigned klass = (*mark_array.table)[mark].get_class (); + if (klass >= class_count) continue; class_to_info[klass].child_indices.push (link.objidx); } @@ -479,7 +486,7 @@ struct MarkBasePos : public OT::Layout::GPOS_impl::MarkBasePos return ((MarkBasePosFormat1*)(&u.format1))->split_subtables (c, parent_index, this_index); #ifndef HB_NO_BEYOND_64K case 2: HB_FALLTHROUGH; - // Don't split 24bit PairPos's. + // Don't split 24bit MarkBasePos's. #endif default: return hb_vector_t<unsigned> (); @@ -490,6 +497,7 @@ struct MarkBasePos : public OT::Layout::GPOS_impl::MarkBasePos { int64_t vertex_len = vertex.obj.tail - vertex.obj.head; if (vertex_len < u.format.get_size ()) return false; + hb_barrier (); switch (u.format) { case 1: diff --git a/src/3rdparty/harfbuzz-ng/src/graph/pairpos-graph.hh b/src/3rdparty/harfbuzz-ng/src/graph/pairpos-graph.hh index 1c13eb24f9..fd46861de4 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/pairpos-graph.hh +++ b/src/3rdparty/harfbuzz-ng/src/graph/pairpos-graph.hh @@ -42,6 +42,7 @@ struct PairPosFormat1 : public OT::Layout::GPOS_impl::PairPosFormat1_3<SmallType int64_t vertex_len = vertex.obj.tail - vertex.obj.head; unsigned min_size = OT::Layout::GPOS_impl::PairPosFormat1_3<SmallTypes>::min_size; if (vertex_len < min_size) return false; + hb_barrier (); return vertex_len >= min_size + pairSet.get_size () - pairSet.len.get_size(); @@ -198,6 +199,7 @@ struct PairPosFormat2 : public OT::Layout::GPOS_impl::PairPosFormat2_4<SmallType size_t vertex_len = vertex.table_size (); unsigned min_size = OT::Layout::GPOS_impl::PairPosFormat2_4<SmallTypes>::min_size; if (vertex_len < min_size) return false; + hb_barrier (); const unsigned class1_count = class1Count; return vertex_len >= @@ -215,7 +217,7 @@ struct PairPosFormat2 : public OT::Layout::GPOS_impl::PairPosFormat2_4<SmallType auto gid_and_class = + coverage->iter () | hb_map_retains_sorting ([&] (hb_codepoint_t gid) { - return hb_pair_t<hb_codepoint_t, hb_codepoint_t> (gid, class_def_1->get_class (gid)); + return hb_codepoint_pair_t (gid, class_def_1->get_class (gid)); }) ; class_def_size_estimator_t estimator (gid_and_class); @@ -245,8 +247,8 @@ struct PairPosFormat2 : public OT::Layout::GPOS_impl::PairPosFormat2_4<SmallType for (unsigned i = 0; i < class1_count; i++) { unsigned accumulated_delta = class1_record_size; - coverage_size += estimator.incremental_coverage_size (i); - class_def_1_size += estimator.incremental_class_def_size (i); + class_def_1_size = estimator.add_class_def_size (i); + coverage_size = estimator.coverage_size (); max_coverage_size = hb_max (max_coverage_size, coverage_size); max_class_def_1_size = hb_max (max_class_def_1_size, class_def_1_size); @@ -278,8 +280,10 @@ struct PairPosFormat2 : public OT::Layout::GPOS_impl::PairPosFormat2_4<SmallType split_points.push (i); // split does not include i, so add the size for i when we reset the size counters. accumulated = base_size + accumulated_delta; - coverage_size = 4 + estimator.incremental_coverage_size (i); - class_def_1_size = 4 + estimator.incremental_class_def_size (i); + + estimator.reset(); + class_def_1_size = estimator.add_class_def_size(i); + coverage_size = estimator.coverage_size(); visited.clear (); // node sharing isn't allowed between splits. } } @@ -386,14 +390,14 @@ struct PairPosFormat2 : public OT::Layout::GPOS_impl::PairPosFormat2_4<SmallType auto klass_map = + coverage_table->iter () | hb_map_retains_sorting ([&] (hb_codepoint_t gid) { - return hb_pair_t<hb_codepoint_t, hb_codepoint_t> (gid, class_def_1_table->get_class (gid)); + return hb_codepoint_pair_t (gid, class_def_1_table->get_class (gid)); }) | hb_filter ([&] (hb_codepoint_t klass) { return klass >= start && klass < end; }, hb_second) - | hb_map_retains_sorting ([&] (hb_pair_t<hb_codepoint_t, hb_codepoint_t> gid_and_class) { + | hb_map_retains_sorting ([&] (hb_codepoint_pair_t gid_and_class) { // Classes must be from 0...N so subtract start - return hb_pair_t<hb_codepoint_t, hb_codepoint_t> (gid_and_class.first, gid_and_class.second - start); + return hb_codepoint_pair_t (gid_and_class.first, gid_and_class.second - start); }) ; @@ -419,7 +423,7 @@ struct PairPosFormat2 : public OT::Layout::GPOS_impl::PairPosFormat2_4<SmallType class_def_link->width = SmallTypes::size; class_def_link->objidx = class_def_2_id; class_def_link->position = 10; - graph.vertices_[class_def_2_id].parents.push (pair_pos_prime_id); + graph.vertices_[class_def_2_id].add_parent (pair_pos_prime_id); graph.duplicate (pair_pos_prime_id, class_def_2_id); return pair_pos_prime_id; @@ -519,7 +523,7 @@ struct PairPosFormat2 : public OT::Layout::GPOS_impl::PairPosFormat2_4<SmallType auto klass_map = + coverage.table->iter () | hb_map_retains_sorting ([&] (hb_codepoint_t gid) { - return hb_pair_t<hb_codepoint_t, hb_codepoint_t> (gid, class_def_1.table->get_class (gid)); + return hb_codepoint_pair_t (gid, class_def_1.table->get_class (gid)); }) | hb_filter ([&] (hb_codepoint_t klass) { return klass < count; @@ -625,6 +629,7 @@ struct PairPos : public OT::Layout::GPOS_impl::PairPos { int64_t vertex_len = vertex.obj.tail - vertex.obj.head; if (vertex_len < u.format.get_size ()) return false; + hb_barrier (); switch (u.format) { case 1: diff --git a/src/3rdparty/harfbuzz-ng/src/graph/serialize.hh b/src/3rdparty/harfbuzz-ng/src/graph/serialize.hh index d03a61bd19..06e4bf44d8 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/serialize.hh +++ b/src/3rdparty/harfbuzz-ng/src/graph/serialize.hh @@ -116,10 +116,10 @@ will_overflow (graph_t& graph, for (int parent_idx = vertices.length - 1; parent_idx >= 0; parent_idx--) { // Don't need to check virtual links for overflow - for (const auto& link : vertices[parent_idx].obj.real_links) + for (const auto& link : vertices.arrayZ[parent_idx].obj.real_links) { int64_t offset = compute_offset (graph, parent_idx, link); - if (is_valid_offset (offset, link)) + if (likely (is_valid_offset (offset, link))) continue; if (!overflows) return true; @@ -153,8 +153,8 @@ void print_overflows (graph_t& graph, const auto& child = graph.vertices_[o.child]; DEBUG_MSG (SUBSET_REPACK, nullptr, " overflow from " - "%4d (%4d in, %4d out, space %2d) => " - "%4d (%4d in, %4d out, space %2d)", + "%4u (%4u in, %4u out, space %2u) => " + "%4u (%4u in, %4u out, space %2u)", o.parent, parent.incoming_edges (), parent.obj.real_links.length + parent.obj.virtual_links.length, @@ -165,7 +165,7 @@ void print_overflows (graph_t& graph, graph.space_for (o.child)); } if (overflows.length > 10) { - DEBUG_MSG (SUBSET_REPACK, nullptr, " ... plus %d more overflows.", overflows.length - 10); + DEBUG_MSG (SUBSET_REPACK, nullptr, " ... plus %u more overflows.", overflows.length - 10); } } @@ -226,6 +226,9 @@ inline hb_blob_t* serialize (const graph_t& graph) { hb_vector_t<char> buffer; size_t size = graph.total_size_in_bytes (); + + if (!size) return hb_blob_get_empty (); + if (!buffer.alloc (size)) { DEBUG_MSG (SUBSET_REPACK, nullptr, "Unable to allocate output buffer."); return nullptr; diff --git a/src/3rdparty/harfbuzz-ng/src/graph/test-classdef-graph.cc b/src/3rdparty/harfbuzz-ng/src/graph/test-classdef-graph.cc index 55854ff5c2..2da9348111 100644 --- a/src/3rdparty/harfbuzz-ng/src/graph/test-classdef-graph.cc +++ b/src/3rdparty/harfbuzz-ng/src/graph/test-classdef-graph.cc @@ -26,27 +26,119 @@ #include "gsubgpos-context.hh" #include "classdef-graph.hh" +#include "hb-iter.hh" +#include "hb-serialize.hh" -typedef hb_pair_t<hb_codepoint_t, hb_codepoint_t> gid_and_class_t; +typedef hb_codepoint_pair_t gid_and_class_t; typedef hb_vector_t<gid_and_class_t> gid_and_class_list_t; +template<typename It> +static unsigned actual_class_def_size(It glyph_and_class) { + char buffer[100]; + hb_serialize_context_t serializer(buffer, 100); + OT::ClassDef_serialize (&serializer, glyph_and_class); + serializer.end_serialize (); + assert(!serializer.in_error()); -static bool incremental_size_is (const gid_and_class_list_t& list, unsigned klass, - unsigned cov_expected, unsigned class_def_expected) + hb_blob_t* blob = serializer.copy_blob(); + unsigned size = hb_blob_get_length(blob); + hb_blob_destroy(blob); + return size; +} + +static unsigned actual_class_def_size(gid_and_class_list_t consecutive_map, hb_vector_t<unsigned> classes) { + auto filtered_it = + + consecutive_map.as_sorted_array().iter() + | hb_filter([&] (unsigned c) { + for (unsigned klass : classes) { + if (c == klass) { + return true; + } + } + return false; + }, hb_second); + return actual_class_def_size(+ filtered_it); +} + +template<typename It> +static unsigned actual_coverage_size(It glyphs) { + char buffer[100]; + hb_serialize_context_t serializer(buffer, 100); + OT::Layout::Common::Coverage_serialize (&serializer, glyphs); + serializer.end_serialize (); + assert(!serializer.in_error()); + + hb_blob_t* blob = serializer.copy_blob(); + unsigned size = hb_blob_get_length(blob); + hb_blob_destroy(blob); + return size; +} + +static unsigned actual_coverage_size(gid_and_class_list_t consecutive_map, hb_vector_t<unsigned> classes) { + auto filtered_it = + + consecutive_map.as_sorted_array().iter() + | hb_filter([&] (unsigned c) { + for (unsigned klass : classes) { + if (c == klass) { + return true; + } + } + return false; + }, hb_second); + return actual_coverage_size(+ filtered_it | hb_map_retains_sorting(hb_first)); +} + +static bool check_coverage_size(graph::class_def_size_estimator_t& estimator, + const gid_and_class_list_t& map, + hb_vector_t<unsigned> klasses) +{ + unsigned result = estimator.coverage_size(); + unsigned expected = actual_coverage_size(map, klasses); + if (result != expected) { + printf ("FAIL: estimated coverage expected size %u but was %u\n", expected, result); + return false; + } + return true; +} + +static bool check_add_class_def_size(graph::class_def_size_estimator_t& estimator, + const gid_and_class_list_t& map, + unsigned klass, hb_vector_t<unsigned> klasses) +{ + unsigned result = estimator.add_class_def_size(klass); + unsigned expected = actual_class_def_size(map, klasses); + if (result != expected) { + printf ("FAIL: estimated class def expected size %u but was %u\n", expected, result); + return false; + } + + return check_coverage_size(estimator, map, klasses); +} + +static bool check_add_class_def_size (const gid_and_class_list_t& list, unsigned klass) { graph::class_def_size_estimator_t estimator (list.iter ()); - unsigned result = estimator.incremental_coverage_size (klass); - if (result != cov_expected) + unsigned result = estimator.add_class_def_size (klass); + auto filtered_it = + + list.as_sorted_array().iter() + | hb_filter([&] (unsigned c) { + return c == klass; + }, hb_second); + + unsigned expected = actual_class_def_size(filtered_it); + if (result != expected) { - printf ("FAIL: coverage expected size %u but was %u\n", cov_expected, result); + printf ("FAIL: class def expected size %u but was %u\n", expected, result); return false; } - result = estimator.incremental_class_def_size (klass); - if (result != class_def_expected) + auto cov_it = + filtered_it | hb_map_retains_sorting(hb_first); + result = estimator.coverage_size (); + expected = actual_coverage_size(cov_it); + if (result != expected) { - printf ("FAIL: class def expected size %u but was %u\n", class_def_expected, result); + printf ("FAIL: coverage expected size %u but was %u\n", expected, result); return false; } @@ -57,43 +149,45 @@ static void test_class_and_coverage_size_estimates () { gid_and_class_list_t empty = { }; - assert (incremental_size_is (empty, 0, 0, 0)); - assert (incremental_size_is (empty, 1, 0, 0)); + assert (check_add_class_def_size (empty, 0)); + assert (check_add_class_def_size (empty, 1)); gid_and_class_list_t class_zero = { {5, 0}, }; - assert (incremental_size_is (class_zero, 0, 2, 0)); + assert (check_add_class_def_size (class_zero, 0)); gid_and_class_list_t consecutive = { {4, 0}, {5, 0}, + {6, 1}, {7, 1}, + {8, 2}, {9, 2}, {10, 2}, {11, 2}, }; - assert (incremental_size_is (consecutive, 0, 4, 0)); - assert (incremental_size_is (consecutive, 1, 4, 4)); - assert (incremental_size_is (consecutive, 2, 8, 6)); + assert (check_add_class_def_size (consecutive, 0)); + assert (check_add_class_def_size (consecutive, 1)); + assert (check_add_class_def_size (consecutive, 2)); gid_and_class_list_t non_consecutive = { {4, 0}, - {5, 0}, + {6, 0}, - {6, 1}, - {7, 1}, + {8, 1}, + {10, 1}, {9, 2}, {10, 2}, {11, 2}, - {12, 2}, + {13, 2}, }; - assert (incremental_size_is (non_consecutive, 0, 4, 0)); - assert (incremental_size_is (non_consecutive, 1, 4, 6)); - assert (incremental_size_is (non_consecutive, 2, 8, 6)); + assert (check_add_class_def_size (non_consecutive, 0)); + assert (check_add_class_def_size (non_consecutive, 1)); + assert (check_add_class_def_size (non_consecutive, 2)); gid_and_class_list_t multiple_ranges = { {4, 0}, @@ -108,12 +202,95 @@ static void test_class_and_coverage_size_estimates () {12, 1}, {13, 1}, }; - assert (incremental_size_is (multiple_ranges, 0, 4, 0)); - assert (incremental_size_is (multiple_ranges, 1, 2 * 6, 3 * 6)); + assert (check_add_class_def_size (multiple_ranges, 0)); + assert (check_add_class_def_size (multiple_ranges, 1)); +} + +static void test_running_class_and_coverage_size_estimates () { + // #### With consecutive gids: switches formats ### + gid_and_class_list_t consecutive_map = { + // range 1-4 (f1: 8 bytes), (f2: 6 bytes) + {1, 1}, + {2, 1}, + {3, 1}, + {4, 1}, + + // (f1: 2 bytes), (f2: 6 bytes) + {5, 2}, + + // (f1: 14 bytes), (f2: 6 bytes) + {6, 3}, + {7, 3}, + {8, 3}, + {9, 3}, + {10, 3}, + {11, 3}, + {12, 3}, + }; + + graph::class_def_size_estimator_t estimator1(consecutive_map.iter()); + assert(check_add_class_def_size(estimator1, consecutive_map, 1, {1})); + assert(check_add_class_def_size(estimator1, consecutive_map, 2, {1, 2})); + assert(check_add_class_def_size(estimator1, consecutive_map, 2, {1, 2})); // check that adding the same class again works + assert(check_add_class_def_size(estimator1, consecutive_map, 3, {1, 2, 3})); + + estimator1.reset(); + assert(check_add_class_def_size(estimator1, consecutive_map, 2, {2})); + assert(check_add_class_def_size(estimator1, consecutive_map, 3, {2, 3})); + + // #### With non-consecutive gids: always uses format 2 ### + gid_and_class_list_t non_consecutive_map = { + // range 1-4 (f1: 8 bytes), (f2: 6 bytes) + {1, 1}, + {2, 1}, + {3, 1}, + {4, 1}, + + // (f1: 2 bytes), (f2: 12 bytes) + {6, 2}, + {8, 2}, + + // (f1: 14 bytes), (f2: 6 bytes) + {9, 3}, + {10, 3}, + {11, 3}, + {12, 3}, + {13, 3}, + {14, 3}, + {15, 3}, + }; + + graph::class_def_size_estimator_t estimator2(non_consecutive_map.iter()); + assert(check_add_class_def_size(estimator2, non_consecutive_map, 1, {1})); + assert(check_add_class_def_size(estimator2, non_consecutive_map, 2, {1, 2})); + assert(check_add_class_def_size(estimator2, non_consecutive_map, 3, {1, 2, 3})); + + estimator2.reset(); + assert(check_add_class_def_size(estimator2, non_consecutive_map, 2, {2})); + assert(check_add_class_def_size(estimator2, non_consecutive_map, 3, {2, 3})); +} + +static void test_running_class_size_estimates_with_locally_consecutive_glyphs () { + gid_and_class_list_t map = { + {1, 1}, + {6, 2}, + {7, 3}, + }; + + graph::class_def_size_estimator_t estimator(map.iter()); + assert(check_add_class_def_size(estimator, map, 1, {1})); + assert(check_add_class_def_size(estimator, map, 2, {1, 2})); + assert(check_add_class_def_size(estimator, map, 3, {1, 2, 3})); + + estimator.reset(); + assert(check_add_class_def_size(estimator, map, 2, {2})); + assert(check_add_class_def_size(estimator, map, 3, {2, 3})); } int main (int argc, char **argv) { test_class_and_coverage_size_estimates (); + test_running_class_and_coverage_size_estimates (); + test_running_class_size_estimates_with_locally_consecutive_glyphs (); } |