diff options
Diffstat (limited to 'thirdparty/harfbuzz/src/graph')
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/classdef-graph.hh | 216 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/coverage-graph.hh | 72 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/graph.hh | 201 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/gsubgpos-context.cc | 5 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/gsubgpos-context.hh | 10 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/gsubgpos-graph.hh | 120 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/markbasepos-graph.hh | 507 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/pairpos-graph.hh | 527 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/split-helpers.hh | 69 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/test-classdef-graph.cc | 119 |
10 files changed, 1712 insertions, 134 deletions
diff --git a/thirdparty/harfbuzz/src/graph/classdef-graph.hh b/thirdparty/harfbuzz/src/graph/classdef-graph.hh new file mode 100644 index 0000000000..0bda76ac2f --- /dev/null +++ b/thirdparty/harfbuzz/src/graph/classdef-graph.hh @@ -0,0 +1,216 @@ +/* + * Copyright © 2022 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 + */ + +#include "graph.hh" +#include "../hb-ot-layout-common.hh" + +#ifndef GRAPH_CLASSDEF_GRAPH_HH +#define GRAPH_CLASSDEF_GRAPH_HH + +namespace graph { + +struct ClassDefFormat1 : public OT::ClassDefFormat1_3<SmallTypes> +{ + bool sanitize (graph_t::vertex_t& vertex) const + { + 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; + return vertex_len >= min_size + classValue.get_size () - classValue.len.get_size (); + } +}; + +struct ClassDefFormat2 : public OT::ClassDefFormat2_4<SmallTypes> +{ + bool sanitize (graph_t::vertex_t& vertex) const + { + 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; + return vertex_len >= min_size + rangeRecord.get_size () - rangeRecord.len.get_size (); + } +}; + +struct ClassDef : public OT::ClassDef +{ + template<typename It> + static bool add_class_def (gsubgpos_graph_context_t& c, + unsigned parent_id, + unsigned link_position, + It glyph_and_class, + unsigned max_size) + { + unsigned class_def_prime_id = c.graph.new_node (nullptr, nullptr); + auto& class_def_prime_vertex = c.graph.vertices_[class_def_prime_id]; + if (!make_class_def (c, glyph_and_class, class_def_prime_id, max_size)) + return false; + + auto* class_def_link = c.graph.vertices_[parent_id].obj.real_links.push (); + 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); + + return true; + } + + template<typename It> + static bool make_class_def (gsubgpos_graph_context_t& c, + It glyph_and_class, + unsigned dest_obj, + unsigned max_size) + { + char* buffer = (char*) hb_calloc (1, max_size); + hb_serialize_context_t serializer (buffer, max_size); + OT::ClassDef_serialize (&serializer, glyph_and_class); + serializer.end_serialize (); + if (serializer.in_error ()) + { + hb_free (buffer); + return false; + } + + 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. + + auto& obj = c.graph.vertices_[dest_obj].obj; + obj.head = (char *) class_def_copy.arrayZ; + obj.tail = obj.head + class_def_copy.length; + + hb_free (buffer); + return true; + } + + bool sanitize (graph_t::vertex_t& vertex) const + { + int64_t vertex_len = vertex.obj.tail - vertex.obj.head; + if (vertex_len < OT::ClassDef::min_size) return false; + switch (u.format) + { + case 1: return ((ClassDefFormat1*)this)->sanitize (vertex); + case 2: return ((ClassDefFormat2*)this)->sanitize (vertex); +#ifndef HB_NO_BORING_EXPANSION + // Not currently supported + case 3: + case 4: +#endif + default: return false; + } + } +}; + + +struct class_def_size_estimator_t +{ + template<typename It> + class_def_size_estimator_t (It glyph_and_class) + : gids_consecutive (true), num_ranges_per_class (), glyphs_per_class () + { + unsigned last_gid = (unsigned) -1; + 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); + continue; + } + + hb_set_t new_glyphs; + new_glyphs.add (gid); + glyphs_per_class.set (klass, std::move (new_glyphs)); + } + + if (in_error ()) return; + + for (unsigned klass : glyphs_per_class.keys ()) + { + if (!klass) continue; // class 0 doesn't get encoded. + + const hb_set_t& glyphs = glyphs_per_class.get (klass); + hb_codepoint_t start = HB_SET_VALUE_INVALID; + hb_codepoint_t end = HB_SET_VALUE_INVALID; + + unsigned count = 0; + while (glyphs.next_range (&start, &end)) + count++; + + num_ranges_per_class.set (klass, count); + } + } + + // 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 + { + // Coverage takes 2 bytes per glyph worst case, + return 2 * glyphs_per_class.get (klass).get_population (); + } + + // 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 + { + // 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); + } + + return class_def_2_size; + } + + bool in_error () + { + if (num_ranges_per_class.in_error ()) return true; + if (glyphs_per_class.in_error ()) return true; + + for (const hb_set_t& s : glyphs_per_class.values ()) + { + if (s.in_error ()) return true; + } + return false; + } + + private: + bool gids_consecutive; + hb_hashmap_t<unsigned, unsigned> num_ranges_per_class; + hb_hashmap_t<unsigned, hb_set_t> glyphs_per_class; +}; + + +} + +#endif // GRAPH_CLASSDEF_GRAPH_HH diff --git a/thirdparty/harfbuzz/src/graph/coverage-graph.hh b/thirdparty/harfbuzz/src/graph/coverage-graph.hh index 1d9fd0eb5b..3c1022f090 100644 --- a/thirdparty/harfbuzz/src/graph/coverage-graph.hh +++ b/thirdparty/harfbuzz/src/graph/coverage-graph.hh @@ -56,6 +56,78 @@ struct CoverageFormat2 : public OT::Layout::Common::CoverageFormat2_4<SmallTypes struct Coverage : public OT::Layout::Common::Coverage { + static Coverage* clone_coverage (gsubgpos_graph_context_t& c, + unsigned coverage_id, + unsigned new_parent_id, + unsigned link_position, + unsigned start, unsigned end) + + { + unsigned coverage_size = c.graph.vertices_[coverage_id].table_size (); + auto& coverage_v = c.graph.vertices_[coverage_id]; + Coverage* coverage_table = (Coverage*) coverage_v.obj.head; + if (!coverage_table || !coverage_table->sanitize (coverage_v)) + return nullptr; + + auto new_coverage = + + hb_zip (coverage_table->iter (), hb_range ()) + | hb_filter ([&] (hb_pair_t<unsigned, unsigned> p) { + return p.second >= start && p.second < end; + }) + | hb_map_retains_sorting (hb_first) + ; + + return add_coverage (c, new_parent_id, link_position, new_coverage, coverage_size); + } + + template<typename It> + static Coverage* add_coverage (gsubgpos_graph_context_t& c, + unsigned parent_id, + unsigned link_position, + It glyphs, + unsigned max_size) + { + unsigned coverage_prime_id = c.graph.new_node (nullptr, nullptr); + auto& coverage_prime_vertex = c.graph.vertices_[coverage_prime_id]; + if (!make_coverage (c, glyphs, coverage_prime_id, max_size)) + return nullptr; + + auto* coverage_link = c.graph.vertices_[parent_id].obj.real_links.push (); + coverage_link->width = SmallTypes::size; + coverage_link->objidx = coverage_prime_id; + coverage_link->position = link_position; + coverage_prime_vertex.parents.push (parent_id); + + return (Coverage*) coverage_prime_vertex.obj.head; + } + + template<typename It> + static bool make_coverage (gsubgpos_graph_context_t& c, + It glyphs, + unsigned dest_obj, + unsigned max_size) + { + char* buffer = (char*) hb_calloc (1, max_size); + hb_serialize_context_t serializer (buffer, max_size); + OT::Layout::Common::Coverage_serialize (&serializer, glyphs); + serializer.end_serialize (); + if (serializer.in_error ()) + { + hb_free (buffer); + return false; + } + + 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. + + auto& obj = c.graph.vertices_[dest_obj].obj; + obj.head = (char *) coverage_copy.arrayZ; + obj.tail = obj.head + coverage_copy.length; + + hb_free (buffer); + return true; + } + bool sanitize (graph_t::vertex_t& vertex) const { int64_t vertex_len = vertex.obj.tail - vertex.obj.head; diff --git a/thirdparty/harfbuzz/src/graph/graph.hh b/thirdparty/harfbuzz/src/graph/graph.hh index b3aef558a2..64878a84a4 100644 --- a/thirdparty/harfbuzz/src/graph/graph.hh +++ b/thirdparty/harfbuzz/src/graph/graph.hh @@ -49,6 +49,51 @@ struct graph_t unsigned end = 0; unsigned priority = 0; + void normalize () + { + obj.real_links.qsort (); + for (auto& l : obj.real_links) + { + for (unsigned i = 0; i < l.width; i++) + { + obj.head[l.position + i] = 0; + } + } + } + + bool equals (const vertex_t& other, + const graph_t& graph, + const graph_t& other_graph, + unsigned depth) const + { + if (!(as_bytes () == other.as_bytes ())) + { + DEBUG_MSG (SUBSET_REPACK, nullptr, + "vertex [%lu] bytes != [%lu] bytes, depth = %u", + table_size (), + other.table_size (), + depth); + + auto a = as_bytes (); + auto b = other.as_bytes (); + while (a || b) + { + DEBUG_MSG (SUBSET_REPACK, nullptr, + " 0x%x %s 0x%x", *a, (*a == *b) ? "==" : "!=", *b); + a++; + b++; + } + return false; + } + + return links_equal (obj.real_links, other.obj.real_links, graph, other_graph, depth); + } + + hb_bytes_t as_bytes () const + { + return hb_bytes_t (obj.head, table_size ()); + } + friend void swap (vertex_t& a, vertex_t& b) { hb_swap (a.obj, b.obj); @@ -60,6 +105,18 @@ struct graph_t hb_swap (a.priority, b.priority); } + hb_hashmap_t<unsigned, unsigned> + position_to_index_map () const + { + hb_hashmap_t<unsigned, unsigned> result; + + for (const auto& l : obj.real_links) { + result.set (l.position, l.objidx); + } + + return result; + } + bool is_shared () const { return parents.length > 1; @@ -84,7 +141,7 @@ struct graph_t { for (unsigned i = 0; i < obj.real_links.length; i++) { - auto& link = obj.real_links[i]; + auto& link = obj.real_links.arrayZ[i]; if (link.objidx != child_index) continue; @@ -155,6 +212,57 @@ struct graph_t return -table_size; } + + private: + bool links_equal (const hb_vector_t<hb_serialize_context_t::object_t::link_t>& this_links, + const hb_vector_t<hb_serialize_context_t::object_t::link_t>& other_links, + const graph_t& graph, + const graph_t& other_graph, + unsigned depth) const + { + auto a = this_links.iter (); + auto b = other_links.iter (); + + while (a && b) + { + const auto& link_a = *a; + const auto& link_b = *b; + + if (link_a.width != link_b.width || + link_a.is_signed != link_b.is_signed || + link_a.whence != link_b.whence || + link_a.position != link_b.position || + link_a.bias != link_b.bias) + return false; + + if (!graph.vertices_[link_a.objidx].equals ( + other_graph.vertices_[link_b.objidx], graph, other_graph, depth + 1)) + return false; + + a++; + b++; + } + + if (bool (a) != bool (b)) + return false; + + return true; + } + }; + + template <typename T> + struct vertex_and_table_t + { + vertex_and_table_t () : index (0), vertex (nullptr), table (nullptr) + {} + + unsigned index; + vertex_t* vertex; + T* table; + + operator bool () { + return table && vertex; + } }; /* @@ -169,7 +277,8 @@ struct graph_t : parents_invalid (true), distance_invalid (true), positions_invalid (true), - successful (true) + successful (true), + buffers () { num_roots_for_space_.push (1); bool removed_nil = false; @@ -201,6 +310,20 @@ struct graph_t ~graph_t () { vertices_.fini (); + for (char* b : buffers) + hb_free (b); + } + + bool operator== (const graph_t& other) const + { + return root ().equals (other.root (), *this, other, 0); + } + + // Sorts links of all objects in a consistent manner and zeroes all offsets. + void normalize () + { + for (auto& v : vertices_.writer ()) + v.normalize (); } bool in_error () const @@ -228,6 +351,27 @@ struct graph_t return vertices_[i].obj; } + void add_buffer (char* buffer) + { + buffers.push (buffer); + } + + /* + * Adds a 16 bit link from parent_id to child_id + */ + template<typename T> + void add_link (T* offset, + unsigned parent_id, + unsigned child_id) + { + auto& v = vertices_[parent_id]; + auto* link = v.obj.real_links.push (); + link->width = 2; + link->objidx = child_id; + link->position = (char*) offset - (char*) v.obj.head; + vertices_[child_id].parents.push (parent_id); + } + /* * Generates a new topological sorting of graph ordered by the shortest * distance to each node if positions are marked as invalid. @@ -345,13 +489,43 @@ struct graph_t } } - unsigned index_for_offset(unsigned node_idx, const void* offset) const + template <typename T, typename ...Ts> + vertex_and_table_t<T> as_table (unsigned parent, const void* offset, Ts... ds) + { + return as_table_from_index<T> (index_for_offset (parent, offset), std::forward<Ts>(ds)...); + } + + template <typename T, typename ...Ts> + vertex_and_table_t<T> as_table_from_index (unsigned index, Ts... ds) + { + if (index >= vertices_.length) + return vertex_and_table_t<T> (); + + vertex_and_table_t<T> r; + r.vertex = &vertices_[index]; + r.table = (T*) r.vertex->obj.head; + r.index = index; + if (!r.table) + return vertex_and_table_t<T> (); + + if (!r.table->sanitize (*(r.vertex), std::forward<Ts>(ds)...)) + return vertex_and_table_t<T> (); + + return r; + } + + // Finds the object id of the object pointed to by the offset at 'offset' + // within object[node_idx]. + unsigned index_for_offset (unsigned node_idx, const void* offset) const { const auto& node = object (node_idx); if (offset < node.head || offset >= node.tail) return -1; - for (const auto& link : node.real_links) + unsigned length = node.real_links.length; + for (unsigned i = 0; i < length; i++) { + // Use direct access for increased performance, this is a hot method. + const auto& link = node.real_links.arrayZ[i]; if (offset != node.head + link.position) continue; return link.objidx; @@ -360,6 +534,24 @@ struct graph_t return -1; } + // Finds the object id of the object pointed to by the offset at 'offset' + // within object[node_idx]. Ensures that the returned object is safe to mutate. + // That is, if the original child object is shared by parents other than node_idx + // it will be duplicated and the duplicate will be returned instead. + unsigned mutable_index_for_offset (unsigned node_idx, const void* offset) + { + unsigned child_idx = index_for_offset (node_idx, offset); + auto& child = vertices_[child_idx]; + for (unsigned p : child.parents) + { + if (p != node_idx) { + return duplicate (node_idx, child_idx); + } + } + + return child_idx; + } + /* * Assign unique space numbers to each connected subgraph of 24 bit and/or 32 bit offset(s). @@ -1039,6 +1231,7 @@ struct graph_t bool positions_invalid; bool successful; hb_vector_t<unsigned> num_roots_for_space_; + hb_vector_t<char*> buffers; }; } diff --git a/thirdparty/harfbuzz/src/graph/gsubgpos-context.cc b/thirdparty/harfbuzz/src/graph/gsubgpos-context.cc index e0ff6ff85f..b2044426d4 100644 --- a/thirdparty/harfbuzz/src/graph/gsubgpos-context.cc +++ b/thirdparty/harfbuzz/src/graph/gsubgpos-context.cc @@ -33,8 +33,7 @@ gsubgpos_graph_context_t::gsubgpos_graph_context_t (hb_tag_t table_tag_, : table_tag (table_tag_), graph (graph_), lookup_list_index (0), - lookups (), - buffers () + lookups () { if (table_tag_ != HB_OT_TAG_GPOS && table_tag_ != HB_OT_TAG_GSUB) @@ -53,7 +52,7 @@ unsigned gsubgpos_graph_context_t::create_node (unsigned size) if (!buffer) return -1; - buffers.push (buffer); + add_buffer (buffer); return graph.new_node (buffer, buffer + size); } diff --git a/thirdparty/harfbuzz/src/graph/gsubgpos-context.hh b/thirdparty/harfbuzz/src/graph/gsubgpos-context.hh index 49b24198ff..9fe9662e64 100644 --- a/thirdparty/harfbuzz/src/graph/gsubgpos-context.hh +++ b/thirdparty/harfbuzz/src/graph/gsubgpos-context.hh @@ -40,22 +40,16 @@ struct gsubgpos_graph_context_t graph_t& graph; unsigned lookup_list_index; hb_hashmap_t<unsigned, graph::Lookup*> lookups; - hb_vector_t<char*> buffers; + HB_INTERNAL gsubgpos_graph_context_t (hb_tag_t table_tag_, graph_t& graph_); - ~gsubgpos_graph_context_t () - { - for (char* b : buffers) - hb_free (b); - } - HB_INTERNAL unsigned create_node (unsigned size); void add_buffer (char* buffer) { - buffers.push (buffer); + graph.add_buffer (buffer); } private: diff --git a/thirdparty/harfbuzz/src/graph/gsubgpos-graph.hh b/thirdparty/harfbuzz/src/graph/gsubgpos-graph.hh index afa1152c44..a93e7d1c73 100644 --- a/thirdparty/harfbuzz/src/graph/gsubgpos-graph.hh +++ b/thirdparty/harfbuzz/src/graph/gsubgpos-graph.hh @@ -29,6 +29,7 @@ #include "../OT/Layout/GSUB/ExtensionSubst.hh" #include "gsubgpos-context.hh" #include "pairpos-graph.hh" +#include "markbasepos-graph.hh" #ifndef GRAPH_GSUBGPOS_GRAPH_HH #define GRAPH_GSUBGPOS_GRAPH_HH @@ -121,10 +122,12 @@ struct Lookup : public OT::Lookup if (c.table_tag != HB_OT_TAG_GPOS) return true; - if (!is_ext && type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair) + if (!is_ext && + type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair && + type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::MarkBase) return true; - hb_vector_t<unsigned> all_new_subtables; + hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>> all_new_subtables; for (unsigned i = 0; i < subTable.len; i++) { unsigned subtable_index = c.graph.index_for_offset (this_index, &subTable[i]); @@ -133,39 +136,66 @@ struct Lookup : public OT::Lookup ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>* extension = (ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>*) c.graph.object (ext_subtable_index).head; - if (!extension->sanitize (c.graph.vertices_[ext_subtable_index])) + if (!extension || !extension->sanitize (c.graph.vertices_[ext_subtable_index])) continue; subtable_index = extension->get_subtable_index (c.graph, ext_subtable_index); type = extension->get_lookup_type (); - if (type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair) + if (type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair + && type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::MarkBase) continue; } - PairPos* pairPos = (PairPos*) c.graph.object (subtable_index).head; - if (!pairPos->sanitize (c.graph.vertices_[subtable_index])) continue; - - hb_vector_t<unsigned> new_sub_tables = pairPos->split_subtables (c, subtable_index); + hb_vector_t<unsigned> new_sub_tables; + switch (type) + { + case 2: + new_sub_tables = split_subtable<PairPos> (c, subtable_index); break; + case 4: + new_sub_tables = split_subtable<MarkBasePos> (c, subtable_index); break; + default: + break; + } if (new_sub_tables.in_error ()) return false; - + new_sub_tables.iter() | hb_sink (all_new_subtables); + if (!new_sub_tables) continue; + hb_pair_t<unsigned, hb_vector_t<unsigned>>* entry = all_new_subtables.push (); + entry->first = i; + entry->second = std::move (new_sub_tables); } - if (all_new_subtables) + if (all_new_subtables) { add_sub_tables (c, this_index, type, all_new_subtables); + } return true; } + template<typename T> + hb_vector_t<unsigned> split_subtable (gsubgpos_graph_context_t& c, + unsigned objidx) + { + T* sub_table = (T*) c.graph.object (objidx).head; + if (!sub_table || !sub_table->sanitize (c.graph.vertices_[objidx])) + return hb_vector_t<unsigned> (); + + return sub_table->split_subtables (c, objidx); + } + void add_sub_tables (gsubgpos_graph_context_t& c, unsigned this_index, unsigned type, - hb_vector_t<unsigned>& subtable_indices) + hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>>& subtable_ids) { bool is_ext = is_extension (c.table_tag); auto& v = c.graph.vertices_[this_index]; + fix_existing_subtable_links (c, this_index, subtable_ids); + + unsigned new_subtable_count = 0; + for (const auto& p : subtable_ids) + new_subtable_count += p.second.length; size_t new_size = v.table_size () - + subtable_indices.length * OT::Offset16::static_size; + + new_subtable_count * OT::Offset16::static_size; char* buffer = (char*) hb_calloc (1, new_size); c.add_buffer (buffer); memcpy (buffer, v.obj.head, v.table_size()); @@ -175,30 +205,61 @@ struct Lookup : public OT::Lookup Lookup* new_lookup = (Lookup*) buffer; - new_lookup->subTable.len = subTable.len + subtable_indices.length; - unsigned offset_index = subTable.len; - for (unsigned subtable_id : subtable_indices) + unsigned shift = 0; + new_lookup->subTable.len = subTable.len + new_subtable_count; + for (const auto& p : subtable_ids) { - if (is_ext) + unsigned offset_index = p.first + shift + 1; + shift += p.second.length; + + for (unsigned subtable_id : p.second) { - unsigned ext_id = create_extension_subtable (c, subtable_id, type); - c.graph.vertices_[subtable_id].parents.push (ext_id); - subtable_id = ext_id; + if (is_ext) + { + unsigned ext_id = create_extension_subtable (c, subtable_id, type); + c.graph.vertices_[subtable_id].parents.push (ext_id); + subtable_id = ext_id; + } + + auto* link = v.obj.real_links.push (); + link->width = 2; + link->objidx = subtable_id; + link->position = (char*) &new_lookup->subTable[offset_index++] - + (char*) new_lookup; + c.graph.vertices_[subtable_id].parents.push (this_index); } - - auto* link = v.obj.real_links.push (); - link->width = 2; - link->objidx = subtable_id; - link->position = (char*) &new_lookup->subTable[offset_index++] - - (char*) new_lookup; - c.graph.vertices_[subtable_id].parents.push (this_index); } + // Repacker sort order depends on link order, which we've messed up so resort it. + v.obj.real_links.qsort (); + // 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); } + void fix_existing_subtable_links (gsubgpos_graph_context_t& c, + unsigned this_index, + hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>>& subtable_ids) + { + auto& v = c.graph.vertices_[this_index]; + Lookup* lookup = (Lookup*) v.obj.head; + + unsigned shift = 0; + for (const auto& p : subtable_ids) + { + unsigned insert_index = p.first + shift; + unsigned pos_offset = p.second.length * OT::Offset16::static_size; + unsigned insert_offset = (char*) &lookup->subTable[insert_index] - (char*) lookup; + shift += p.second.length; + + for (auto& l : v.obj.all_links_writer ()) + { + if (l.position > insert_offset) l.position += pos_offset; + } + } + } + unsigned create_extension_subtable (gsubgpos_graph_context_t& c, unsigned subtable_index, unsigned type) @@ -281,7 +342,7 @@ struct GSTAR : public OT::GSUBGPOS const auto& r = graph.root (); GSTAR* gstar = (GSTAR*) r.obj.head; - if (!gstar->sanitize (r)) + if (!gstar || !gstar->sanitize (r)) return nullptr; return gstar; @@ -327,17 +388,16 @@ struct GSTAR : public OT::GSUBGPOS hb_hashmap_t<unsigned, Lookup*>& lookups /* OUT */) { unsigned lookup_list_idx = get_lookup_list_index (graph); - const LookupList<Types>* lookupList = (const LookupList<Types>*) graph.object (lookup_list_idx).head; - if (!lookupList->sanitize (graph.vertices_[lookup_list_idx])) + if (!lookupList || !lookupList->sanitize (graph.vertices_[lookup_list_idx])) return; for (unsigned i = 0; i < lookupList->len; i++) { unsigned lookup_idx = graph.index_for_offset (lookup_list_idx, &(lookupList->arrayZ[i])); Lookup* lookup = (Lookup*) graph.object (lookup_idx).head; - if (!lookup->sanitize (graph.vertices_[lookup_idx])) continue; + if (!lookup || !lookup->sanitize (graph.vertices_[lookup_idx])) continue; lookups.set (lookup_idx, lookup); } } diff --git a/thirdparty/harfbuzz/src/graph/markbasepos-graph.hh b/thirdparty/harfbuzz/src/graph/markbasepos-graph.hh new file mode 100644 index 0000000000..56fa812406 --- /dev/null +++ b/thirdparty/harfbuzz/src/graph/markbasepos-graph.hh @@ -0,0 +1,507 @@ +/* + * Copyright © 2022 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 GRAPH_MARKBASEPOS_GRAPH_HH +#define GRAPH_MARKBASEPOS_GRAPH_HH + +#include "split-helpers.hh" +#include "coverage-graph.hh" +#include "../OT/Layout/GPOS/MarkBasePos.hh" +#include "../OT/Layout/GPOS/PosLookupSubTable.hh" + +namespace graph { + +struct AnchorMatrix : public OT::Layout::GPOS_impl::AnchorMatrix +{ + bool sanitize (graph_t::vertex_t& vertex, unsigned class_count) const + { + int64_t vertex_len = vertex.obj.tail - vertex.obj.head; + if (vertex_len < AnchorMatrix::min_size) return false; + + return vertex_len >= AnchorMatrix::min_size + + OT::Offset16::static_size * class_count * this->rows; + } + + bool shrink (gsubgpos_graph_context_t& c, + unsigned this_index, + unsigned old_class_count, + unsigned new_class_count) + { + if (new_class_count >= old_class_count) return false; + auto& o = c.graph.vertices_[this_index].obj; + unsigned base_count = rows; + o.tail = o.head + + AnchorMatrix::min_size + + OT::Offset16::static_size * base_count * new_class_count; + + // Reposition links into the new indexing scheme. + for (auto& link : o.real_links.writer ()) + { + unsigned index = (link.position - 2) / 2; + unsigned base = index / old_class_count; + unsigned klass = index % old_class_count; + if (klass >= new_class_count) + // should have already been removed + return false; + + unsigned new_index = base * new_class_count + klass; + + link.position = (char*) &(this->matrixZ[new_index]) - (char*) this; + } + + return true; + } + + unsigned clone (gsubgpos_graph_context_t& c, + unsigned this_index, + unsigned start, + unsigned end, + unsigned class_count) + { + unsigned base_count = rows; + unsigned new_class_count = end - start; + unsigned size = AnchorMatrix::min_size + + OT::Offset16::static_size * new_class_count * rows; + unsigned prime_id = c.create_node (size); + if (prime_id == (unsigned) -1) return -1; + AnchorMatrix* prime = (AnchorMatrix*) c.graph.object (prime_id).head; + prime->rows = base_count; + + auto& o = c.graph.vertices_[this_index].obj; + int num_links = o.real_links.length; + for (int i = 0; i < num_links; i++) + { + const auto& link = o.real_links[i]; + unsigned old_index = (link.position - 2) / OT::Offset16::static_size; + unsigned klass = old_index % class_count; + if (klass < start || klass >= end) continue; + + unsigned base = old_index / class_count; + unsigned new_klass = klass - start; + unsigned new_index = base * new_class_count + new_klass; + + + unsigned child_idx = link.objidx; + c.graph.add_link (&(prime->matrixZ[new_index]), + prime_id, + child_idx); + + auto& child = c.graph.vertices_[child_idx]; + child.remove_parent (this_index); + + o.real_links.remove (i); + num_links--; + i--; + } + + return prime_id; + } +}; + +struct MarkArray : public OT::Layout::GPOS_impl::MarkArray +{ + bool sanitize (graph_t::vertex_t& vertex) const + { + int64_t vertex_len = vertex.obj.tail - vertex.obj.head; + unsigned min_size = MarkArray::min_size; + if (vertex_len < min_size) return false; + + return vertex_len >= get_size (); + } + + bool shrink (gsubgpos_graph_context_t& c, + const hb_hashmap_t<unsigned, unsigned>& mark_array_links, + unsigned this_index, + unsigned new_class_count) + { + auto& o = c.graph.vertices_[this_index].obj; + for (const auto& link : o.real_links) + c.graph.vertices_[link.objidx].remove_parent (this_index); + o.real_links.reset (); + + unsigned new_index = 0; + for (const auto& record : this->iter ()) + { + unsigned klass = record.klass; + if (klass >= new_class_count) continue; + + (*this)[new_index].klass = klass; + unsigned position = (char*) &record.markAnchor - (char*) this; + unsigned* objidx; + if (!mark_array_links.has (position, &objidx)) + { + new_index++; + continue; + } + + c.graph.add_link (&(*this)[new_index].markAnchor, this_index, *objidx); + new_index++; + } + + this->len = new_index; + o.tail = o.head + MarkArray::min_size + + OT::Layout::GPOS_impl::MarkRecord::static_size * new_index; + return true; + } + + unsigned clone (gsubgpos_graph_context_t& c, + unsigned this_index, + const hb_hashmap_t<unsigned, unsigned>& pos_to_index, + hb_set_t& marks, + unsigned start_class) + { + unsigned size = MarkArray::min_size + + OT::Layout::GPOS_impl::MarkRecord::static_size * + marks.get_population (); + unsigned prime_id = c.create_node (size); + if (prime_id == (unsigned) -1) return -1; + MarkArray* prime = (MarkArray*) c.graph.object (prime_id).head; + prime->len = marks.get_population (); + + + unsigned i = 0; + for (hb_codepoint_t mark : marks) + { + (*prime)[i].klass = (*this)[mark].klass - start_class; + unsigned offset_pos = (char*) &((*this)[mark].markAnchor) - (char*) this; + unsigned* anchor_index; + if (pos_to_index.has (offset_pos, &anchor_index)) + c.graph.move_child (this_index, + &((*this)[mark].markAnchor), + prime_id, + &((*prime)[i].markAnchor)); + + i++; + } + + return prime_id; + } +}; + +struct MarkBasePosFormat1 : public OT::Layout::GPOS_impl::MarkBasePosFormat1_2<SmallTypes> +{ + bool sanitize (graph_t::vertex_t& vertex) const + { + int64_t vertex_len = vertex.obj.tail - vertex.obj.head; + return vertex_len >= MarkBasePosFormat1::static_size; + } + + hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c, unsigned this_index) + { + hb_set_t visited; + + 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 + + MarkArray::min_size + + AnchorMatrix::min_size + + c.graph.vertices_[base_coverage_id].table_size (); + + hb_vector_t<class_info_t> class_to_info = get_class_info (c, this_index); + + unsigned class_count = classCount; + auto base_array = c.graph.as_table<AnchorMatrix> (this_index, + &baseArray, + class_count); + if (!base_array) return hb_vector_t<unsigned> (); + unsigned base_count = base_array.table->rows; + + unsigned partial_coverage_size = 4; + unsigned accumulated = base_size; + hb_vector_t<unsigned> split_points; + + for (unsigned klass = 0; klass < class_count; klass++) + { + class_info_t& info = class_to_info[klass]; + partial_coverage_size += OT::HBUINT16::static_size * info.marks.get_population (); + unsigned accumulated_delta = + OT::Layout::GPOS_impl::MarkRecord::static_size * info.marks.get_population () + + OT::Offset16::static_size * base_count; + + for (unsigned objidx : info.child_indices) + accumulated_delta += c.graph.find_subgraph_size (objidx, visited); + + accumulated += accumulated_delta; + unsigned total = accumulated + partial_coverage_size; + + if (total >= (1 << 16)) + { + split_points.push (klass); + accumulated = base_size + accumulated_delta; + partial_coverage_size = 4 + OT::HBUINT16::static_size * info.marks.get_population (); + visited.clear (); // node sharing isn't allowed between splits. + } + } + + + const unsigned mark_array_id = c.graph.index_for_offset (this_index, &markArray); + split_context_t split_context { + c, + this, + this_index, + std::move (class_to_info), + c.graph.vertices_[mark_array_id].position_to_index_map (), + }; + + return actuate_subtable_split<split_context_t> (split_context, split_points); + } + + private: + + struct class_info_t { + hb_set_t marks; + hb_vector_t<unsigned> child_indices; + }; + + struct split_context_t { + gsubgpos_graph_context_t& c; + MarkBasePosFormat1* thiz; + unsigned this_index; + hb_vector_t<class_info_t> class_to_info; + hb_hashmap_t<unsigned, unsigned> mark_array_links; + + hb_set_t marks_for (unsigned start, unsigned end) + { + hb_set_t marks; + for (unsigned klass = start; klass < end; klass++) + { + + class_to_info[klass].marks.iter () + | hb_sink (marks) + ; + } + return marks; + } + + unsigned original_count () + { + return thiz->classCount; + } + + unsigned clone_range (unsigned start, unsigned end) + { + return thiz->clone_range (*this, this->this_index, start, end); + } + + bool shrink (unsigned count) + { + return thiz->shrink (*this, this->this_index, count); + } + }; + + hb_vector_t<class_info_t> get_class_info (gsubgpos_graph_context_t& c, + unsigned this_index) + { + hb_vector_t<class_info_t> class_to_info; + + unsigned class_count= classCount; + class_to_info.resize (class_count); + + auto mark_array = c.graph.as_table<MarkArray> (this_index, &markArray); + if (!mark_array) return hb_vector_t<class_info_t> (); + unsigned mark_count = mark_array.table->len; + for (unsigned mark = 0; mark < mark_count; mark++) + { + unsigned klass = (*mark_array.table)[mark].get_class (); + class_to_info[klass].marks.add (mark); + } + + for (const auto& link : mark_array.vertex->obj.real_links) + { + unsigned mark = (link.position - 2) / + OT::Layout::GPOS_impl::MarkRecord::static_size; + unsigned klass = (*mark_array.table)[mark].get_class (); + class_to_info[klass].child_indices.push (link.objidx); + } + + unsigned base_array_id = + c.graph.index_for_offset (this_index, &baseArray); + auto& base_array_v = c.graph.vertices_[base_array_id]; + + for (const auto& link : base_array_v.obj.real_links) + { + unsigned index = (link.position - 2) / OT::Offset16::static_size; + unsigned klass = index % class_count; + class_to_info[klass].child_indices.push (link.objidx); + } + + return class_to_info; + } + + bool shrink (split_context_t& sc, + unsigned this_index, + unsigned count) + { + DEBUG_MSG (SUBSET_REPACK, nullptr, + " Shrinking MarkBasePosFormat1 (%u) to [0, %u).", + this_index, + count); + + unsigned old_count = classCount; + if (count >= old_count) + return true; + + classCount = count; + + auto mark_coverage = sc.c.graph.as_table<Coverage> (this_index, + &markCoverage); + if (!mark_coverage) return false; + hb_set_t marks = sc.marks_for (0, count); + auto new_coverage = + + hb_zip (hb_range (), mark_coverage.table->iter ()) + | hb_filter (marks, hb_first) + | hb_map_retains_sorting (hb_second) + ; + if (!Coverage::make_coverage (sc.c, + new_coverage, + mark_coverage.index, + 4 + 2 * marks.get_population ())) + return false; + + + auto base_array = sc.c.graph.as_table<AnchorMatrix> (this_index, + &baseArray, + old_count); + if (!base_array || !base_array.table->shrink (sc.c, + base_array.index, + old_count, + count)) + return false; + + auto mark_array = sc.c.graph.as_table<MarkArray> (this_index, + &markArray); + if (!mark_array || !mark_array.table->shrink (sc.c, + sc.mark_array_links, + mark_array.index, + count)) + return false; + + return true; + } + + // Create a new MarkBasePos that has all of the data for classes from [start, end). + unsigned clone_range (split_context_t& sc, + unsigned this_index, + unsigned start, unsigned end) const + { + DEBUG_MSG (SUBSET_REPACK, nullptr, + " Cloning MarkBasePosFormat1 (%u) range [%u, %u).", this_index, start, end); + + graph_t& graph = sc.c.graph; + unsigned prime_size = OT::Layout::GPOS_impl::MarkBasePosFormat1_2<SmallTypes>::static_size; + + unsigned prime_id = sc.c.create_node (prime_size); + if (prime_id == (unsigned) -1) return -1; + + MarkBasePosFormat1* prime = (MarkBasePosFormat1*) graph.object (prime_id).head; + prime->format = this->format; + unsigned new_class_count = end - start; + prime->classCount = new_class_count; + + unsigned base_coverage_id = + graph.index_for_offset (sc.this_index, &baseCoverage); + graph.add_link (&(prime->baseCoverage), prime_id, base_coverage_id); + graph.duplicate (prime_id, base_coverage_id); + + auto mark_coverage = sc.c.graph.as_table<Coverage> (this_index, + &markCoverage); + if (!mark_coverage) return false; + hb_set_t marks = sc.marks_for (start, end); + auto new_coverage = + + hb_zip (hb_range (), mark_coverage.table->iter ()) + | hb_filter (marks, hb_first) + | hb_map_retains_sorting (hb_second) + ; + if (!Coverage::add_coverage (sc.c, + prime_id, + 2, + + new_coverage, + marks.get_population () * 2 + 4)) + return -1; + + auto mark_array = + graph.as_table <MarkArray> (sc.this_index, &markArray); + if (!mark_array) return -1; + unsigned new_mark_array = + mark_array.table->clone (sc.c, + mark_array.index, + sc.mark_array_links, + marks, + start); + graph.add_link (&(prime->markArray), prime_id, new_mark_array); + + unsigned class_count = classCount; + auto base_array = + graph.as_table<AnchorMatrix> (sc.this_index, &baseArray, class_count); + if (!base_array) return -1; + unsigned new_base_array = + base_array.table->clone (sc.c, + base_array.index, + start, end, this->classCount); + graph.add_link (&(prime->baseArray), prime_id, new_base_array); + + return prime_id; + } +}; + + +struct MarkBasePos : public OT::Layout::GPOS_impl::MarkBasePos +{ + hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c, + unsigned this_index) + { + switch (u.format) { + case 1: + return ((MarkBasePosFormat1*)(&u.format1))->split_subtables (c, this_index); +#ifndef HB_NO_BORING_EXPANSION + case 2: HB_FALLTHROUGH; + // Don't split 24bit PairPos's. +#endif + default: + return hb_vector_t<unsigned> (); + } + } + + bool sanitize (graph_t::vertex_t& vertex) const + { + int64_t vertex_len = vertex.obj.tail - vertex.obj.head; + if (vertex_len < u.format.get_size ()) return false; + + switch (u.format) { + case 1: + return ((MarkBasePosFormat1*)(&u.format1))->sanitize (vertex); +#ifndef HB_NO_BORING_EXPANSION + case 2: HB_FALLTHROUGH; +#endif + default: + // We don't handle format 3 and 4 here. + return false; + } + } +}; + + +} + +#endif // GRAPH_MARKBASEPOS_GRAPH_HH diff --git a/thirdparty/harfbuzz/src/graph/pairpos-graph.hh b/thirdparty/harfbuzz/src/graph/pairpos-graph.hh index 3ca4fc701c..976b872329 100644 --- a/thirdparty/harfbuzz/src/graph/pairpos-graph.hh +++ b/thirdparty/harfbuzz/src/graph/pairpos-graph.hh @@ -27,7 +27,9 @@ #ifndef GRAPH_PAIRPOS_GRAPH_HH #define GRAPH_PAIRPOS_GRAPH_HH +#include "split-helpers.hh" #include "coverage-graph.hh" +#include "classdef-graph.hh" #include "../OT/Layout/GPOS/PairPos.hh" #include "../OT/Layout/GPOS/PosLookupSubTable.hh" @@ -51,68 +53,62 @@ struct PairPosFormat1 : public OT::Layout::GPOS_impl::PairPosFormat1_3<SmallType const unsigned coverage_id = c.graph.index_for_offset (this_index, &coverage); const unsigned coverage_size = c.graph.vertices_[coverage_id].table_size (); - const unsigned base_size = OT::Layout::GPOS_impl::PairPosFormat1_3<SmallTypes>::min_size - + coverage_size; + const unsigned base_size = OT::Layout::GPOS_impl::PairPosFormat1_3<SmallTypes>::min_size; + unsigned partial_coverage_size = 4; unsigned accumulated = base_size; hb_vector_t<unsigned> split_points; for (unsigned i = 0; i < pairSet.len; i++) { unsigned pair_set_index = pair_set_graph_index (c, this_index, i); - accumulated += c.graph.find_subgraph_size (pair_set_index, visited); - accumulated += SmallTypes::size; // for PairSet offset. + unsigned accumulated_delta = + c.graph.find_subgraph_size (pair_set_index, visited) + + SmallTypes::size; // for PairSet offset. + partial_coverage_size += OT::HBUINT16::static_size; - // TODO(garretrieger): don't count the size of the largest pairset against the limit, since - // it will be packed last in the order and does not contribute to - // the 64kb limit. + accumulated += accumulated_delta; + unsigned total = accumulated + hb_min (partial_coverage_size, coverage_size); - if (accumulated > (1 << 16)) + if (total >= (1 << 16)) { split_points.push (i); - accumulated = base_size; - visited.clear (); // Pretend node sharing isn't allowed between splits. + accumulated = base_size + accumulated_delta; + partial_coverage_size = 6; + visited.clear (); // node sharing isn't allowed between splits. } } - return do_split (c, this_index, split_points); + split_context_t split_context { + c, + this, + this_index, + }; + + return actuate_subtable_split<split_context_t> (split_context, split_points); } private: - // Split this PairPos into two or more PairPos's. split_points defines - // the indices (first index to include in the new table) to split at. - // Returns the object id's of the newly created PairPos subtables. - hb_vector_t<unsigned> do_split (gsubgpos_graph_context_t& c, - unsigned this_index, - const hb_vector_t<unsigned> split_points) - { - hb_vector_t<unsigned> new_objects; - if (!split_points) - return new_objects; + struct split_context_t { + gsubgpos_graph_context_t& c; + PairPosFormat1* thiz; + unsigned this_index; - for (unsigned i = 0; i < split_points.length; i++) + unsigned original_count () { - unsigned start = split_points[i]; - unsigned end = (i < split_points.length - 1) ? split_points[i + 1] : pairSet.len; - unsigned id = clone_range (c, this_index, start, end); - - if (id == (unsigned) -1) - { - new_objects.reset (); - new_objects.allocated = -1; // mark error - return new_objects; - } - new_objects.push (id); + return thiz->pairSet.len; } - if (!shrink (c, this_index, split_points[0])) + unsigned clone_range (unsigned start, unsigned end) { - new_objects.reset (); - new_objects.allocated = -1; // mark error + return thiz->clone_range (this->c, this->this_index, start, end); } - return new_objects; - } + bool shrink (unsigned count) + { + return thiz->shrink (this->c, this->this_index, count); + } + }; bool shrink (gsubgpos_graph_context_t& c, unsigned this_index, @@ -129,11 +125,12 @@ struct PairPosFormat1 : public OT::Layout::GPOS_impl::PairPosFormat1_3<SmallType pairSet.len = count; c.graph.vertices_[this_index].obj.tail -= (old_count - count) * SmallTypes::size; - unsigned coverage_id = c.graph.index_for_offset (this_index, &coverage); + unsigned coverage_id = c.graph.mutable_index_for_offset (this_index, &coverage); unsigned coverage_size = c.graph.vertices_[coverage_id].table_size (); auto& coverage_v = c.graph.vertices_[coverage_id]; + Coverage* coverage_table = (Coverage*) coverage_v.obj.head; - if (!coverage_table->sanitize (coverage_v)) + if (!coverage_table || !coverage_table->sanitize (coverage_v)) return false; auto new_coverage = @@ -144,7 +141,7 @@ struct PairPosFormat1 : public OT::Layout::GPOS_impl::PairPosFormat1_3<SmallType | hb_map_retains_sorting (hb_first) ; - return make_coverage (c, new_coverage, coverage_id, coverage_size); + return Coverage::make_coverage (c, new_coverage, coverage_id, coverage_size); } // Create a new PairPos including PairSet's from start (inclusive) to end (exclusive). @@ -178,79 +175,431 @@ struct PairPosFormat1 : public OT::Layout::GPOS_impl::PairPosFormat1_3<SmallType } unsigned coverage_id = c.graph.index_for_offset (this_index, &coverage); - unsigned coverage_size = c.graph.vertices_[coverage_id].table_size (); - auto& coverage_v = c.graph.vertices_[coverage_id]; - Coverage* coverage_table = (Coverage*) coverage_v.obj.head; - if (!coverage_table->sanitize (coverage_v)) - return false; + if (!Coverage::clone_coverage (c, + coverage_id, + pair_pos_prime_id, + 2, + start, end)) + return -1; - auto new_coverage = - + hb_zip (coverage_table->iter (), hb_range ()) - | hb_filter ([&] (hb_pair_t<unsigned, unsigned> p) { - return p.second >= start && p.second < end; + return pair_pos_prime_id; + } + + + + unsigned pair_set_graph_index (gsubgpos_graph_context_t& c, unsigned this_index, unsigned i) const + { + return c.graph.index_for_offset (this_index, &pairSet[i]); + } +}; + +struct PairPosFormat2 : public OT::Layout::GPOS_impl::PairPosFormat2_4<SmallTypes> +{ + bool sanitize (graph_t::vertex_t& vertex) const + { + 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; + + const unsigned class1_count = class1Count; + return vertex_len >= + min_size + class1_count * get_class1_record_size (); + } + + hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c, unsigned this_index) + { + const unsigned base_size = OT::Layout::GPOS_impl::PairPosFormat2_4<SmallTypes>::min_size; + const unsigned class_def_2_size = size_of (c, this_index, &classDef2); + const Coverage* coverage = get_coverage (c, this_index); + const ClassDef* class_def_1 = get_class_def_1 (c, this_index); + 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)); }) - | hb_map_retains_sorting (hb_first) ; + class_def_size_estimator_t estimator (gid_and_class); + + const unsigned class1_count = class1Count; + const unsigned class2_count = class2Count; + const unsigned class1_record_size = get_class1_record_size (); - unsigned coverage_prime_id = c.graph.new_node (nullptr, nullptr); - auto& coverage_prime_vertex = c.graph.vertices_[coverage_prime_id]; - if (!make_coverage (c, new_coverage, coverage_prime_id, coverage_size)) + const unsigned value_1_len = valueFormat1.get_len (); + const unsigned value_2_len = valueFormat2.get_len (); + const unsigned total_value_len = value_1_len + value_2_len; + + unsigned accumulated = base_size; + unsigned coverage_size = 4; + unsigned class_def_1_size = 4; + unsigned max_coverage_size = coverage_size; + unsigned max_class_def_1_size = class_def_1_size; + + hb_vector_t<unsigned> split_points; + + hb_hashmap_t<unsigned, unsigned> device_tables = get_all_device_tables (c, this_index); + hb_vector_t<unsigned> format1_device_table_indices = valueFormat1.get_device_table_indices (); + hb_vector_t<unsigned> format2_device_table_indices = valueFormat2.get_device_table_indices (); + bool has_device_tables = bool(format1_device_table_indices) || bool(format2_device_table_indices); + + hb_set_t visited; + 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); + 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); + + if (has_device_tables) { + for (unsigned j = 0; j < class2_count; j++) + { + unsigned value1_index = total_value_len * (class2_count * i + j); + unsigned value2_index = value1_index + value_1_len; + accumulated_delta += size_of_value_record_children (c, + device_tables, + format1_device_table_indices, + value1_index, + visited); + accumulated_delta += size_of_value_record_children (c, + device_tables, + format2_device_table_indices, + value2_index, + visited); + } + } + + accumulated += accumulated_delta; + unsigned total = accumulated + + coverage_size + class_def_1_size + class_def_2_size + // The largest object will pack last and can exceed the size limit. + - hb_max (hb_max (coverage_size, class_def_1_size), class_def_2_size); + if (total >= (1 << 16)) + { + 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); + visited.clear (); // node sharing isn't allowed between splits. + } + } + + split_context_t split_context { + c, + this, + this_index, + class1_record_size, + total_value_len, + value_1_len, + value_2_len, + max_coverage_size, + max_class_def_1_size, + device_tables, + format1_device_table_indices, + format2_device_table_indices + }; + + return actuate_subtable_split<split_context_t> (split_context, split_points); + } + private: + + struct split_context_t + { + gsubgpos_graph_context_t& c; + PairPosFormat2* thiz; + unsigned this_index; + unsigned class1_record_size; + unsigned value_record_len; + unsigned value1_record_len; + unsigned value2_record_len; + unsigned max_coverage_size; + unsigned max_class_def_size; + + const hb_hashmap_t<unsigned, unsigned>& device_tables; + const hb_vector_t<unsigned>& format1_device_table_indices; + const hb_vector_t<unsigned>& format2_device_table_indices; + + unsigned original_count () + { + return thiz->class1Count; + } + + unsigned clone_range (unsigned start, unsigned end) + { + return thiz->clone_range (*this, start, end); + } + + bool shrink (unsigned count) + { + return thiz->shrink (*this, count); + } + }; + + size_t get_class1_record_size () const + { + const size_t class2_count = class2Count; + return + class2_count * (valueFormat1.get_size () + valueFormat2.get_size ()); + } + + unsigned clone_range (split_context_t& split_context, + unsigned start, unsigned end) const + { + DEBUG_MSG (SUBSET_REPACK, nullptr, + " Cloning PairPosFormat2 (%u) range [%u, %u).", split_context.this_index, start, end); + + graph_t& graph = split_context.c.graph; + + unsigned num_records = end - start; + unsigned prime_size = OT::Layout::GPOS_impl::PairPosFormat2_4<SmallTypes>::min_size + + num_records * split_context.class1_record_size; + + unsigned pair_pos_prime_id = split_context.c.create_node (prime_size); + if (pair_pos_prime_id == (unsigned) -1) return -1; + + PairPosFormat2* pair_pos_prime = + (PairPosFormat2*) graph.object (pair_pos_prime_id).head; + pair_pos_prime->format = this->format; + pair_pos_prime->valueFormat1 = this->valueFormat1; + pair_pos_prime->valueFormat2 = this->valueFormat2; + pair_pos_prime->class1Count = num_records; + pair_pos_prime->class2Count = this->class2Count; + clone_class1_records (split_context, + pair_pos_prime_id, + start, + end); + + unsigned coverage_id = + graph.index_for_offset (split_context.this_index, &coverage); + unsigned class_def_1_id = + graph.index_for_offset (split_context.this_index, &classDef1); + auto& coverage_v = graph.vertices_[coverage_id]; + auto& class_def_1_v = graph.vertices_[class_def_1_id]; + Coverage* coverage_table = (Coverage*) coverage_v.obj.head; + ClassDef* class_def_1_table = (ClassDef*) class_def_1_v.obj.head; + if (!coverage_table + || !coverage_table->sanitize (coverage_v) + || !class_def_1_table + || !class_def_1_table->sanitize (class_def_1_v)) return -1; - auto* coverage_link = c.graph.vertices_[pair_pos_prime_id].obj.real_links.push (); - coverage_link->width = SmallTypes::size; - coverage_link->objidx = coverage_prime_id; - coverage_link->position = 2; - coverage_prime_vertex.parents.push (pair_pos_prime_id); + 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)); + }) + | 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) { + // 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); + }) + ; + + if (!Coverage::add_coverage (split_context.c, + pair_pos_prime_id, + 2, + + klass_map | hb_map_retains_sorting (hb_first), + split_context.max_coverage_size)) + return -1; + + // classDef1 + if (!ClassDef::add_class_def (split_context.c, + pair_pos_prime_id, + 8, + + klass_map, + split_context.max_class_def_size)) + return -1; + + // classDef2 + unsigned class_def_2_id = + graph.index_for_offset (split_context.this_index, &classDef2); + auto* class_def_link = graph.vertices_[pair_pos_prime_id].obj.real_links.push (); + 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.duplicate (pair_pos_prime_id, class_def_2_id); return pair_pos_prime_id; } - template<typename It> - bool make_coverage (gsubgpos_graph_context_t& c, - It glyphs, - unsigned dest_obj, - unsigned max_size) const + void clone_class1_records (split_context_t& split_context, + unsigned pair_pos_prime_id, + unsigned start, unsigned end) const { - char* buffer = (char*) hb_calloc (1, max_size); - hb_serialize_context_t serializer (buffer, max_size); - Coverage_serialize (&serializer, glyphs); - serializer.end_serialize (); - if (serializer.in_error ()) + PairPosFormat2* pair_pos_prime = + (PairPosFormat2*) split_context.c.graph.object (pair_pos_prime_id).head; + + char* start_addr = ((char*)&values[0]) + start * split_context.class1_record_size; + unsigned num_records = end - start; + memcpy (&pair_pos_prime->values[0], + start_addr, + num_records * split_context.class1_record_size); + + if (!split_context.format1_device_table_indices + && !split_context.format2_device_table_indices) + // No device tables to move over. + return; + + unsigned class2_count = class2Count; + for (unsigned i = start; i < end; i++) { - hb_free (buffer); - return false; + for (unsigned j = 0; j < class2_count; j++) + { + unsigned value1_index = split_context.value_record_len * (class2_count * i + j); + unsigned value2_index = value1_index + split_context.value1_record_len; + + unsigned new_value1_index = split_context.value_record_len * (class2_count * (i - start) + j); + unsigned new_value2_index = new_value1_index + split_context.value1_record_len; + + transfer_device_tables (split_context, + pair_pos_prime_id, + split_context.format1_device_table_indices, + value1_index, + new_value1_index); + + transfer_device_tables (split_context, + pair_pos_prime_id, + split_context.format2_device_table_indices, + value2_index, + new_value2_index); + } } + } - 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. + void transfer_device_tables (split_context_t& split_context, + unsigned pair_pos_prime_id, + const hb_vector_t<unsigned>& device_table_indices, + unsigned old_value_record_index, + unsigned new_value_record_index) const + { + PairPosFormat2* pair_pos_prime = + (PairPosFormat2*) split_context.c.graph.object (pair_pos_prime_id).head; - auto& obj = c.graph.vertices_[dest_obj].obj; - obj.head = (char *) coverage_copy.arrayZ; - obj.tail = obj.head + coverage_copy.length; + for (unsigned i : device_table_indices) + { + OT::Offset16* record = (OT::Offset16*) &values[old_value_record_index + i]; + unsigned record_position = ((char*) record) - ((char*) this); + if (!split_context.device_tables.has (record_position)) continue; + + split_context.c.graph.move_child ( + split_context.this_index, + record, + pair_pos_prime_id, + (OT::Offset16*) &pair_pos_prime->values[new_value_record_index + i]); + } + } - hb_free (buffer); - return true; + bool shrink (split_context_t& split_context, + unsigned count) + { + DEBUG_MSG (SUBSET_REPACK, nullptr, + " Shrinking PairPosFormat2 (%u) to [0, %u).", + split_context.this_index, + count); + unsigned old_count = class1Count; + if (count >= old_count) + return true; + + graph_t& graph = split_context.c.graph; + class1Count = count; + graph.vertices_[split_context.this_index].obj.tail -= + (old_count - count) * split_context.class1_record_size; + + unsigned coverage_id = + graph.mutable_index_for_offset (split_context.this_index, &coverage); + unsigned class_def_1_id = + graph.mutable_index_for_offset (split_context.this_index, &classDef1); + auto& coverage_v = graph.vertices_[coverage_id]; + auto& class_def_1_v = graph.vertices_[class_def_1_id]; + Coverage* coverage_table = (Coverage*) coverage_v.obj.head; + ClassDef* class_def_1_table = (ClassDef*) class_def_1_v.obj.head; + if (!coverage_table + || !coverage_table->sanitize (coverage_v) + || !class_def_1_table + || !class_def_1_table->sanitize (class_def_1_v)) + return false; + + 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)); + }) + | hb_filter ([&] (hb_codepoint_t klass) { + return klass < count; + }, hb_second) + ; + + if (!Coverage::make_coverage (split_context.c, + + klass_map | hb_map_retains_sorting (hb_first), + coverage_id, + coverage_v.table_size ())) + return false; + + return ClassDef::make_class_def (split_context.c, + + klass_map, + class_def_1_id, + class_def_1_v.table_size ()); } - unsigned pair_set_graph_index (gsubgpos_graph_context_t& c, unsigned this_index, unsigned i) const + hb_hashmap_t<unsigned, unsigned> + get_all_device_tables (gsubgpos_graph_context_t& c, + unsigned this_index) const { - return c.graph.index_for_offset (this_index, &pairSet[i]); + const auto& v = c.graph.vertices_[this_index]; + return v.position_to_index_map (); } -}; -struct PairPosFormat2 : public OT::Layout::GPOS_impl::PairPosFormat2_4<SmallTypes> -{ - bool sanitize (graph_t::vertex_t& vertex) const + const Coverage* get_coverage (gsubgpos_graph_context_t& c, + unsigned this_index) const { - // TODO(garretrieger): implement me! - return true; + unsigned coverage_id = c.graph.index_for_offset (this_index, &coverage); + auto& coverage_v = c.graph.vertices_[coverage_id]; + + Coverage* coverage_table = (Coverage*) coverage_v.obj.head; + if (!coverage_table || !coverage_table->sanitize (coverage_v)) + return &Null(Coverage); + return coverage_table; } - hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c, unsigned this_index) + const ClassDef* get_class_def_1 (gsubgpos_graph_context_t& c, + unsigned this_index) const + { + unsigned class_def_1_id = c.graph.index_for_offset (this_index, &classDef1); + auto& class_def_1_v = c.graph.vertices_[class_def_1_id]; + + ClassDef* class_def_1_table = (ClassDef*) class_def_1_v.obj.head; + if (!class_def_1_table || !class_def_1_table->sanitize (class_def_1_v)) + return &Null(ClassDef); + return class_def_1_table; + } + + unsigned size_of_value_record_children (gsubgpos_graph_context_t& c, + const hb_hashmap_t<unsigned, unsigned>& device_tables, + const hb_vector_t<unsigned> device_table_indices, + unsigned value_record_index, + hb_set_t& visited) + { + unsigned size = 0; + for (unsigned i : device_table_indices) + { + OT::Layout::GPOS_impl::Value* record = &values[value_record_index + i]; + unsigned record_position = ((char*) record) - ((char*) this); + unsigned* obj_idx; + if (!device_tables.has (record_position, &obj_idx)) continue; + size += c.graph.find_subgraph_size (*obj_idx, visited); + } + return size; + } + + unsigned size_of (gsubgpos_graph_context_t& c, + unsigned this_index, + const void* offset) const { - // TODO(garretrieger): implement me! - return hb_vector_t<unsigned> (); + const unsigned id = c.graph.index_for_offset (this_index, offset); + return c.graph.vertices_[id].table_size (); } }; diff --git a/thirdparty/harfbuzz/src/graph/split-helpers.hh b/thirdparty/harfbuzz/src/graph/split-helpers.hh new file mode 100644 index 0000000000..61fd7c2d2f --- /dev/null +++ b/thirdparty/harfbuzz/src/graph/split-helpers.hh @@ -0,0 +1,69 @@ +/* + * Copyright © 2022 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 GRAPH_SPLIT_HELPERS_HH +#define GRAPH_SPLIT_HELPERS_HH + +namespace graph { + +template<typename Context> +HB_INTERNAL +hb_vector_t<unsigned> actuate_subtable_split (Context& split_context, + const hb_vector_t<unsigned>& split_points) +{ + hb_vector_t<unsigned> new_objects; + if (!split_points) + return new_objects; + + for (unsigned i = 0; i < split_points.length; i++) + { + unsigned start = split_points[i]; + unsigned end = (i < split_points.length - 1) + ? split_points[i + 1] + : split_context.original_count (); + unsigned id = split_context.clone_range (start, end); + + if (id == (unsigned) -1) + { + new_objects.reset (); + new_objects.allocated = -1; // mark error + return new_objects; + } + new_objects.push (id); + } + + if (!split_context.shrink (split_points[0])) + { + new_objects.reset (); + new_objects.allocated = -1; // mark error + } + + return new_objects; +} + +} + +#endif // GRAPH_SPLIT_HELPERS_HH diff --git a/thirdparty/harfbuzz/src/graph/test-classdef-graph.cc b/thirdparty/harfbuzz/src/graph/test-classdef-graph.cc new file mode 100644 index 0000000000..55854ff5c2 --- /dev/null +++ b/thirdparty/harfbuzz/src/graph/test-classdef-graph.cc @@ -0,0 +1,119 @@ +/* + * Copyright © 2022 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 + */ + +#include "gsubgpos-context.hh" +#include "classdef-graph.hh" + +typedef hb_pair_t<hb_codepoint_t, hb_codepoint_t> gid_and_class_t; +typedef hb_vector_t<gid_and_class_t> gid_and_class_list_t; + + +static bool incremental_size_is (const gid_and_class_list_t& list, unsigned klass, + unsigned cov_expected, unsigned class_def_expected) +{ + graph::class_def_size_estimator_t estimator (list.iter ()); + + unsigned result = estimator.incremental_coverage_size (klass); + if (result != cov_expected) + { + printf ("FAIL: coverage expected size %u but was %u\n", cov_expected, result); + return false; + } + + result = estimator.incremental_class_def_size (klass); + if (result != class_def_expected) + { + printf ("FAIL: class def expected size %u but was %u\n", class_def_expected, result); + return false; + } + + return true; +} + +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)); + + gid_and_class_list_t class_zero = { + {5, 0}, + }; + assert (incremental_size_is (class_zero, 0, 2, 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)); + + gid_and_class_list_t non_consecutive = { + {4, 0}, + {5, 0}, + + {6, 1}, + {7, 1}, + + {9, 2}, + {10, 2}, + {11, 2}, + {12, 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)); + + gid_and_class_list_t multiple_ranges = { + {4, 0}, + {5, 0}, + + {6, 1}, + {7, 1}, + + {9, 1}, + + {11, 1}, + {12, 1}, + {13, 1}, + }; + assert (incremental_size_is (multiple_ranges, 0, 4, 0)); + assert (incremental_size_is (multiple_ranges, 1, 2 * 6, 3 * 6)); +} + +int +main (int argc, char **argv) +{ + test_class_and_coverage_size_estimates (); +} |