diff options
Diffstat (limited to 'thirdparty/harfbuzz/src/graph')
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/coverage-graph.hh | 80 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/graph.hh | 140 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/gsubgpos-context.cc | 71 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/gsubgpos-context.hh | 67 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/gsubgpos-graph.hh | 351 | ||||
| -rw-r--r-- | thirdparty/harfbuzz/src/graph/pairpos-graph.hh | 299 |
6 files changed, 1004 insertions, 4 deletions
diff --git a/thirdparty/harfbuzz/src/graph/coverage-graph.hh b/thirdparty/harfbuzz/src/graph/coverage-graph.hh new file mode 100644 index 0000000000..1d9fd0eb5b --- /dev/null +++ b/thirdparty/harfbuzz/src/graph/coverage-graph.hh @@ -0,0 +1,80 @@ +/* + * 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 "../OT/Layout/Common/Coverage.hh" + +#ifndef GRAPH_COVERAGE_GRAPH_HH +#define GRAPH_COVERAGE_GRAPH_HH + +namespace graph { + +struct CoverageFormat1 : public OT::Layout::Common::CoverageFormat1_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::Layout::Common::CoverageFormat1_3<SmallTypes>::min_size; + if (vertex_len < min_size) return false; + return vertex_len >= min_size + glyphArray.get_size () - glyphArray.len.get_size (); + } +}; + +struct CoverageFormat2 : public OT::Layout::Common::CoverageFormat2_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::Layout::Common::CoverageFormat2_4<SmallTypes>::min_size; + if (vertex_len < min_size) return false; + return vertex_len >= min_size + rangeRecord.get_size () - rangeRecord.len.get_size (); + } +}; + +struct Coverage : public OT::Layout::Common::Coverage +{ + bool sanitize (graph_t::vertex_t& vertex) const + { + int64_t vertex_len = vertex.obj.tail - vertex.obj.head; + if (vertex_len < OT::Layout::Common::Coverage::min_size) return false; + switch (u.format) + { + case 1: return ((CoverageFormat1*)this)->sanitize (vertex); + case 2: return ((CoverageFormat2*)this)->sanitize (vertex); +#ifndef HB_NO_BORING_EXPANSION + // Not currently supported + case 3: + case 4: +#endif + default: return false; + } + } +}; + + +} + +#endif // GRAPH_COVERAGE_GRAPH_HH diff --git a/thirdparty/harfbuzz/src/graph/graph.hh b/thirdparty/harfbuzz/src/graph/graph.hh index 49638f34a7..b3aef558a2 100644 --- a/thirdparty/harfbuzz/src/graph/graph.hh +++ b/thirdparty/harfbuzz/src/graph/graph.hh @@ -24,6 +24,10 @@ * Google Author(s): Garret Rieger */ +#include "../hb-set.hh" +#include "../hb-priority-queue.hh" +#include "../hb-serialize.hh" + #ifndef GRAPH_GRAPH_HH #define GRAPH_GRAPH_HH @@ -76,6 +80,22 @@ struct graph_t } } + void remove_real_link (unsigned child_index, const void* offset) + { + for (unsigned i = 0; i < obj.real_links.length; i++) + { + auto& link = obj.real_links[i]; + if (link.objidx != child_index) + continue; + + if ((obj.head + link.position) != offset) + continue; + + obj.real_links.remove (i); + return; + } + } + void remap_parents (const hb_vector_t<unsigned>& id_map) { for (unsigned i = 0; i < parents.length; i++) @@ -107,6 +127,10 @@ struct graph_t return priority >= 3; } + size_t table_size () const { + return obj.tail - obj.head; + } + int64_t modified_distance (unsigned order) const { // TODO(garretrieger): once priority is high enough, should try @@ -199,13 +223,24 @@ struct graph_t return vertices_.length - 1; } - const hb_serialize_context_t::object_t& object(unsigned i) const + const hb_serialize_context_t::object_t& object (unsigned i) const { return vertices_[i].obj; } /* * Generates a new topological sorting of graph ordered by the shortest + * distance to each node if positions are marked as invalid. + */ + void sort_shortest_distance_if_needed () + { + if (!positions_invalid) return; + sort_shortest_distance (); + } + + + /* + * Generates a new topological sorting of graph ordered by the shortest * distance to each node. */ void sort_shortest_distance () @@ -256,12 +291,12 @@ struct graph_t check_success (!queue.in_error ()); check_success (!sorted_graph.in_error ()); - if (!check_success (new_id == -1)) - print_orphaned_nodes (); remap_all_obj_indices (id_map, &sorted_graph); - hb_swap (vertices_, sorted_graph); + + if (!check_success (new_id == -1)) + print_orphaned_nodes (); } /* @@ -310,6 +345,22 @@ struct graph_t } } + 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) + { + if (offset != node.head + link.position) + continue; + return link.objidx; + } + + return -1; + } + + /* * Assign unique space numbers to each connected subgraph of 24 bit and/or 32 bit offset(s). * Currently, this is implemented specifically tailored to the structure of a GPOS/GSUB @@ -317,6 +368,8 @@ struct graph_t */ bool assign_spaces () { + update_parents (); + hb_set_t visited; hb_set_t roots; find_space_roots (visited, roots); @@ -458,6 +511,21 @@ struct graph_t find_subgraph (link.objidx, subgraph); } + size_t find_subgraph_size (unsigned node_idx, hb_set_t& subgraph, unsigned max_depth = -1) + { + if (subgraph.has (node_idx)) return 0; + subgraph.add (node_idx); + + const auto& o = vertices_[node_idx].obj; + size_t size = o.tail - o.head; + if (max_depth == 0) + return size; + + for (const auto& link : o.all_links ()) + size += find_subgraph_size (link.objidx, subgraph, max_depth - 1); + return size; + } + /* * Finds the topmost children of 32bit offsets in the subgraph starting * at node_idx. Found indices are placed into 'found'. @@ -475,6 +543,37 @@ struct graph_t } /* + * Moves the child of old_parent_idx pointed to by old_offset to a new + * vertex at the new_offset. + */ + template<typename O> + void move_child (unsigned old_parent_idx, + const O* old_offset, + unsigned new_parent_idx, + const O* new_offset) + { + distance_invalid = true; + positions_invalid = true; + + auto& old_v = vertices_[old_parent_idx]; + auto& new_v = vertices_[new_parent_idx]; + + unsigned child_id = index_for_offset (old_parent_idx, + old_offset); + + auto* new_link = new_v.obj.real_links.push (); + new_link->width = O::static_size; + new_link->objidx = child_id; + new_link->position = (const char*) new_offset - (const char*) new_v.obj.head; + + auto& child = vertices_[child_id]; + child.parents.push (new_parent_idx); + + old_v.remove_real_link (child_id, old_offset); + child.remove_parent (old_parent_idx); + } + + /* * duplicates all nodes in the subgraph reachable from node_idx. Does not re-assign * links. index_map is updated with mappings from old id to new id. If a duplication has already * been performed for a given index, then it will be skipped. @@ -581,6 +680,39 @@ struct graph_t return true; } + + /* + * Adds a new node to the graph, not connected to anything. + */ + unsigned new_node (char* head, char* tail) + { + positions_invalid = true; + distance_invalid = true; + + auto* clone = vertices_.push (); + if (vertices_.in_error ()) { + return -1; + } + + clone->obj.head = head; + clone->obj.tail = tail; + clone->distance = 0; + clone->space = 0; + + unsigned clone_idx = vertices_.length - 2; + + // The last object is the root of the graph, so swap back the root to the end. + // The root's obj idx does change, however since it's root nothing else refers to it. + // all other obj idx's will be unaffected. + hb_swap (vertices_[vertices_.length - 2], *clone); + + // Since the root moved, update the parents arrays of all children on the root. + for (const auto& l : root ().obj.all_links ()) + vertices_[l.objidx].remap_parent (root_idx () - 1, root_idx ()); + + return clone_idx; + } + /* * Raises the sorting priority of all children. */ diff --git a/thirdparty/harfbuzz/src/graph/gsubgpos-context.cc b/thirdparty/harfbuzz/src/graph/gsubgpos-context.cc new file mode 100644 index 0000000000..e0ff6ff85f --- /dev/null +++ b/thirdparty/harfbuzz/src/graph/gsubgpos-context.cc @@ -0,0 +1,71 @@ +/* + * 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-graph.hh" + +namespace graph { + +gsubgpos_graph_context_t::gsubgpos_graph_context_t (hb_tag_t table_tag_, + graph_t& graph_) + : table_tag (table_tag_), + graph (graph_), + lookup_list_index (0), + lookups (), + buffers () +{ + if (table_tag_ != HB_OT_TAG_GPOS + && table_tag_ != HB_OT_TAG_GSUB) + return; + + GSTAR* gstar = graph::GSTAR::graph_to_gstar (graph_); + if (gstar) { + gstar->find_lookups (graph, lookups); + lookup_list_index = gstar->get_lookup_list_index (graph_); + } +} + +unsigned gsubgpos_graph_context_t::create_node (unsigned size) +{ + char* buffer = (char*) hb_calloc (1, size); + if (!buffer) + return -1; + + buffers.push (buffer); + + return graph.new_node (buffer, buffer + size); +} + +unsigned gsubgpos_graph_context_t::num_non_ext_subtables () { + unsigned count = 0; + for (auto l : lookups.values ()) + { + if (l->is_extension (table_tag)) continue; + count += l->number_of_subtables (); + } + return count; +} + +} diff --git a/thirdparty/harfbuzz/src/graph/gsubgpos-context.hh b/thirdparty/harfbuzz/src/graph/gsubgpos-context.hh new file mode 100644 index 0000000000..49b24198ff --- /dev/null +++ b/thirdparty/harfbuzz/src/graph/gsubgpos-context.hh @@ -0,0 +1,67 @@ +/* + * 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-gsubgpos.hh" + +#ifndef GRAPH_GSUBGPOS_CONTEXT_HH +#define GRAPH_GSUBGPOS_CONTEXT_HH + +namespace graph { + +struct Lookup; + +struct gsubgpos_graph_context_t +{ + hb_tag_t table_tag; + 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); + } + + private: + HB_INTERNAL unsigned num_non_ext_subtables (); +}; + +} + +#endif // GRAPH_GSUBGPOS_CONTEXT diff --git a/thirdparty/harfbuzz/src/graph/gsubgpos-graph.hh b/thirdparty/harfbuzz/src/graph/gsubgpos-graph.hh new file mode 100644 index 0000000000..afa1152c44 --- /dev/null +++ b/thirdparty/harfbuzz/src/graph/gsubgpos-graph.hh @@ -0,0 +1,351 @@ +/* + * 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-gsubgpos.hh" +#include "../OT/Layout/GSUB/ExtensionSubst.hh" +#include "gsubgpos-context.hh" +#include "pairpos-graph.hh" + +#ifndef GRAPH_GSUBGPOS_GRAPH_HH +#define GRAPH_GSUBGPOS_GRAPH_HH + +namespace graph { + +struct Lookup; + +template<typename T> +struct ExtensionFormat1 : public OT::ExtensionFormat1<T> +{ + void reset(unsigned type) + { + this->format = 1; + this->extensionLookupType = type; + this->extensionOffset = 0; + } + + bool sanitize (graph_t::vertex_t& vertex) const + { + int64_t vertex_len = vertex.obj.tail - vertex.obj.head; + return vertex_len >= OT::ExtensionFormat1<T>::static_size; + } + + unsigned get_lookup_type () const + { + return this->extensionLookupType; + } + + unsigned get_subtable_index (graph_t& graph, unsigned this_index) const + { + return graph.index_for_offset (this_index, &this->extensionOffset); + } +}; + +struct Lookup : public OT::Lookup +{ + unsigned number_of_subtables () const + { + return subTable.len; + } + + bool sanitize (graph_t::vertex_t& vertex) const + { + int64_t vertex_len = vertex.obj.tail - vertex.obj.head; + if (vertex_len < OT::Lookup::min_size) return false; + return vertex_len >= this->get_size (); + } + + bool is_extension (hb_tag_t table_tag) const + { + return lookupType == extension_type (table_tag); + } + + bool make_extension (gsubgpos_graph_context_t& c, + unsigned this_index) + { + unsigned type = lookupType; + unsigned ext_type = extension_type (c.table_tag); + if (!ext_type || is_extension (c.table_tag)) + { + // NOOP + return true; + } + + DEBUG_MSG (SUBSET_REPACK, nullptr, + "Promoting lookup type %u (obj %u) to extension.", + type, + this_index); + + for (unsigned i = 0; i < subTable.len; i++) + { + unsigned subtable_index = c.graph.index_for_offset (this_index, &subTable[i]); + if (!make_subtable_extension (c, + this_index, + subtable_index)) + return false; + } + + lookupType = ext_type; + return true; + } + + bool split_subtables_if_needed (gsubgpos_graph_context_t& c, + unsigned this_index) + { + unsigned type = lookupType; + bool is_ext = is_extension (c.table_tag); + + if (c.table_tag != HB_OT_TAG_GPOS) + return true; + + if (!is_ext && type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair) + return true; + + 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]); + if (is_ext) { + unsigned ext_subtable_index = subtable_index; + 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])) + 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) + 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); + if (new_sub_tables.in_error ()) return false; + + new_sub_tables.iter() | hb_sink (all_new_subtables); + } + + if (all_new_subtables) + add_sub_tables (c, this_index, type, all_new_subtables); + + return true; + } + + void add_sub_tables (gsubgpos_graph_context_t& c, + unsigned this_index, + unsigned type, + hb_vector_t<unsigned>& subtable_indices) + { + bool is_ext = is_extension (c.table_tag); + auto& v = c.graph.vertices_[this_index]; + + size_t new_size = v.table_size () + + subtable_indices.length * OT::Offset16::static_size; + char* buffer = (char*) hb_calloc (1, new_size); + c.add_buffer (buffer); + memcpy (buffer, v.obj.head, v.table_size()); + + v.obj.head = buffer; + v.obj.tail = buffer + new_size; + + 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) + { + 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); + } + + // 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); + } + + unsigned create_extension_subtable (gsubgpos_graph_context_t& c, + unsigned subtable_index, + unsigned type) + { + unsigned extension_size = OT::ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>::static_size; + + unsigned ext_index = c.create_node (extension_size); + if (ext_index == (unsigned) -1) + return -1; + + auto& ext_vertex = c.graph.vertices_[ext_index]; + ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>* extension = + (ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>*) ext_vertex.obj.head; + extension->reset (type); + + // Make extension point at the subtable. + auto* l = ext_vertex.obj.real_links.push (); + + l->width = 4; + l->objidx = subtable_index; + l->position = 4; + + return ext_index; + } + + bool make_subtable_extension (gsubgpos_graph_context_t& c, + unsigned lookup_index, + unsigned subtable_index) + { + unsigned type = lookupType; + + unsigned ext_index = create_extension_subtable(c, subtable_index, type); + if (ext_index == (unsigned) -1) + return false; + + auto& lookup_vertex = c.graph.vertices_[lookup_index]; + for (auto& l : lookup_vertex.obj.real_links.writer ()) + { + if (l.objidx == subtable_index) + // Change lookup to point at the extension. + l.objidx = ext_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); + + return true; + } + + private: + unsigned extension_type (hb_tag_t table_tag) const + { + switch (table_tag) + { + case HB_OT_TAG_GPOS: return 9; + case HB_OT_TAG_GSUB: return 7; + default: return 0; + } + } +}; + +template <typename T> +struct LookupList : public OT::LookupList<T> +{ + bool sanitize (const graph_t::vertex_t& vertex) const + { + int64_t vertex_len = vertex.obj.tail - vertex.obj.head; + if (vertex_len < OT::LookupList<T>::min_size) return false; + return vertex_len >= OT::LookupList<T>::item_size * this->len; + } +}; + +struct GSTAR : public OT::GSUBGPOS +{ + static GSTAR* graph_to_gstar (graph_t& graph) + { + const auto& r = graph.root (); + + GSTAR* gstar = (GSTAR*) r.obj.head; + if (!gstar->sanitize (r)) + return nullptr; + + return gstar; + } + + const void* get_lookup_list_field_offset () const + { + switch (u.version.major) { + case 1: return u.version1.get_lookup_list_offset (); +#ifndef HB_NO_BORING_EXPANSION + case 2: return u.version2.get_lookup_list_offset (); +#endif + default: return 0; + } + } + + bool sanitize (const graph_t::vertex_t& vertex) + { + int64_t len = vertex.obj.tail - vertex.obj.head; + if (len < OT::GSUBGPOS::min_size) return false; + return len >= get_size (); + } + + void find_lookups (graph_t& graph, + hb_hashmap_t<unsigned, Lookup*>& lookups /* OUT */) + { + switch (u.version.major) { + case 1: find_lookups<SmallTypes> (graph, lookups); break; +#ifndef HB_NO_BORING_EXPANSION + case 2: find_lookups<MediumTypes> (graph, lookups); break; +#endif + } + } + + unsigned get_lookup_list_index (graph_t& graph) + { + return graph.index_for_offset (graph.root_idx (), + get_lookup_list_field_offset()); + } + + template<typename Types> + void find_lookups (graph_t& graph, + 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])) + 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; + lookups.set (lookup_idx, lookup); + } + } +}; + + + + +} + +#endif /* GRAPH_GSUBGPOS_GRAPH_HH */ diff --git a/thirdparty/harfbuzz/src/graph/pairpos-graph.hh b/thirdparty/harfbuzz/src/graph/pairpos-graph.hh new file mode 100644 index 0000000000..3ca4fc701c --- /dev/null +++ b/thirdparty/harfbuzz/src/graph/pairpos-graph.hh @@ -0,0 +1,299 @@ +/* + * 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_PAIRPOS_GRAPH_HH +#define GRAPH_PAIRPOS_GRAPH_HH + +#include "coverage-graph.hh" +#include "../OT/Layout/GPOS/PairPos.hh" +#include "../OT/Layout/GPOS/PosLookupSubTable.hh" + +namespace graph { + +struct PairPosFormat1 : public OT::Layout::GPOS_impl::PairPosFormat1_3<SmallTypes> +{ + bool sanitize (graph_t::vertex_t& vertex) const + { + 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; + + return vertex_len >= + min_size + pairSet.get_size () - pairSet.len.get_size(); + } + + hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c, unsigned this_index) + { + hb_set_t visited; + + 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; + + 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. + + // 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. + + if (accumulated > (1 << 16)) + { + split_points.push (i); + accumulated = base_size; + visited.clear (); // Pretend node sharing isn't allowed between splits. + } + } + + return do_split (c, this_index, 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; + + 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] : 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); + } + + if (!shrink (c, this_index, split_points[0])) + { + new_objects.reset (); + new_objects.allocated = -1; // mark error + } + + return new_objects; + } + + bool shrink (gsubgpos_graph_context_t& c, + unsigned this_index, + unsigned count) + { + DEBUG_MSG (SUBSET_REPACK, nullptr, + " Shrinking PairPosFormat1 (%u) to [0, %u).", + this_index, + count); + unsigned old_count = pairSet.len; + if (count >= old_count) + return true; + + 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_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; + + auto new_coverage = + + hb_zip (coverage_table->iter (), hb_range ()) + | hb_filter ([&] (hb_pair_t<unsigned, unsigned> p) { + return p.second < count; + }) + | hb_map_retains_sorting (hb_first) + ; + + return make_coverage (c, new_coverage, coverage_id, coverage_size); + } + + // Create a new PairPos including PairSet's from start (inclusive) to end (exclusive). + // Returns object id of the new object. + unsigned clone_range (gsubgpos_graph_context_t& c, + unsigned this_index, + unsigned start, unsigned end) const + { + DEBUG_MSG (SUBSET_REPACK, nullptr, + " Cloning PairPosFormat1 (%u) range [%u, %u).", this_index, start, end); + + unsigned num_pair_sets = end - start; + unsigned prime_size = OT::Layout::GPOS_impl::PairPosFormat1_3<SmallTypes>::min_size + + num_pair_sets * SmallTypes::size; + + unsigned pair_pos_prime_id = c.create_node (prime_size); + if (pair_pos_prime_id == (unsigned) -1) return -1; + + PairPosFormat1* pair_pos_prime = (PairPosFormat1*) c.graph.object (pair_pos_prime_id).head; + pair_pos_prime->format = this->format; + pair_pos_prime->valueFormat[0] = this->valueFormat[0]; + pair_pos_prime->valueFormat[1] = this->valueFormat[1]; + pair_pos_prime->pairSet.len = num_pair_sets; + + for (unsigned i = start; i < end; i++) + { + c.graph.move_child<> (this_index, + &pairSet[i], + pair_pos_prime_id, + &pair_pos_prime->pairSet[i - start]); + } + + 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; + + 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) + ; + + 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)) + 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); + + 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 + { + 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 ()) + { + 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; + } + + 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 + { + // TODO(garretrieger): implement me! + return true; + } + + hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c, unsigned this_index) + { + // TODO(garretrieger): implement me! + return hb_vector_t<unsigned> (); + } +}; + +struct PairPos : public OT::Layout::GPOS_impl::PairPos +{ + hb_vector_t<unsigned> split_subtables (gsubgpos_graph_context_t& c, unsigned this_index) + { + switch (u.format) { + case 1: + return ((PairPosFormat1*)(&u.format1))->split_subtables (c, this_index); + case 2: + return ((PairPosFormat2*)(&u.format2))->split_subtables (c, this_index); +#ifndef HB_NO_BORING_EXPANSION + case 3: HB_FALLTHROUGH; + case 4: 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 ((PairPosFormat1*)(&u.format1))->sanitize (vertex); + case 2: + return ((PairPosFormat2*)(&u.format2))->sanitize (vertex); +#ifndef HB_NO_BORING_EXPANSION + case 3: HB_FALLTHROUGH; + case 4: HB_FALLTHROUGH; +#endif + default: + // We don't handle format 3 and 4 here. + return false; + } + } +}; + +} + +#endif // GRAPH_PAIRPOS_GRAPH_HH |