| /* |
| * 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" |
| #include "markbasepos-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 && |
| type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::MarkBase) |
| return true; |
| |
| 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]); |
| unsigned parent_index = this_index; |
| if (is_ext) { |
| unsigned ext_subtable_index = subtable_index; |
| parent_index = ext_subtable_index; |
| ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>* extension = |
| (ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>*) |
| c.graph.object (ext_subtable_index).head; |
| 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 |
| && type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::MarkBase) |
| continue; |
| } |
| |
| hb_vector_t<unsigned> new_sub_tables; |
| switch (type) |
| { |
| case 2: |
| new_sub_tables = split_subtable<PairPos> (c, parent_index, subtable_index); break; |
| case 4: |
| new_sub_tables = split_subtable<MarkBasePos> (c, parent_index, subtable_index); break; |
| default: |
| break; |
| } |
| if (new_sub_tables.in_error ()) return false; |
| 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) { |
| return 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 parent_idx, |
| 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, parent_idx, objidx); |
| } |
| |
| bool add_sub_tables (gsubgpos_graph_context_t& c, |
| unsigned this_index, |
| unsigned type, |
| hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>>& subtable_ids) |
| { |
| 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 () |
| + new_subtable_count * OT::Offset16::static_size; |
| char* buffer = (char*) hb_calloc (1, new_size); |
| if (!buffer) return false; |
| if (!c.add_buffer (buffer)) |
| { |
| hb_free (buffer); |
| return false; |
| } |
| hb_memcpy (buffer, v.obj.head, v.table_size()); |
| |
| v.obj.head = buffer; |
| v.obj.tail = buffer + new_size; |
| |
| Lookup* new_lookup = (Lookup*) buffer; |
| |
| unsigned shift = 0; |
| new_lookup->subTable.len = subTable.len + new_subtable_count; |
| for (const auto& p : subtable_ids) |
| { |
| unsigned offset_index = p.first + shift + 1; |
| shift += p.second.length; |
| |
| for (unsigned subtable_id : p.second) |
| { |
| if (is_ext) |
| { |
| unsigned ext_id = create_extension_subtable (c, subtable_id, type); |
| c.graph.vertices_[subtable_id].add_parent (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].add_parent (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); |
| return true; |
| } |
| |
| 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) |
| { |
| 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 = -1; |
| unsigned* existing_ext_index = nullptr; |
| if (c.subtable_to_extension.has(subtable_index, &existing_ext_index)) { |
| ext_index = *existing_ext_index; |
| } else { |
| ext_index = create_extension_subtable(c, subtable_index, type); |
| c.subtable_to_extension.set(subtable_index, ext_index); |
| } |
| |
| if (ext_index == (unsigned) -1) |
| return false; |
| |
| auto& subtable_vertex = c.graph.vertices_[subtable_index]; |
| auto& lookup_vertex = c.graph.vertices_[lookup_index]; |
| for (auto& l : lookup_vertex.obj.real_links.writer ()) |
| { |
| if (l.objidx == subtable_index) { |
| // Change lookup to point at the extension. |
| l.objidx = ext_index; |
| if (existing_ext_index) |
| subtable_vertex.remove_parent(lookup_index); |
| } |
| } |
| |
| // Make extension point at the subtable. |
| auto& ext_vertex = c.graph.vertices_[ext_index]; |
| ext_vertex.add_parent (lookup_index); |
| if (!existing_ext_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 || !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_BEYOND_64K |
| 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_BEYOND_64K |
| 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 || !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 || !lookup->sanitize (graph.vertices_[lookup_idx])) continue; |
| lookups.set (lookup_idx, lookup); |
| } |
| } |
| }; |
| |
| |
| |
| |
| } |
| |
| #endif /* GRAPH_GSUBGPOS_GRAPH_HH */ |
