Source code
Revision control
Copy as Markdown
Other Tools
/*
* 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_SERIALIZE_HH
#define GRAPH_SERIALIZE_HH
namespace graph {
struct overflow_record_t
{
unsigned parent;
unsigned child;
bool operator != (const overflow_record_t o) const
{ return !(*this == o); }
inline bool operator == (const overflow_record_t& o) const
{
return parent == o.parent &&
child == o.child;
}
inline uint32_t hash () const
{
uint32_t current = 0;
current = current * 31 + hb_hash (parent);
current = current * 31 + hb_hash (child);
return current;
}
};
inline
int64_t compute_offset (
const graph_t& graph,
unsigned parent_idx,
const hb_serialize_context_t::object_t::link_t& link)
{
const auto& parent = graph.vertices_[parent_idx];
const auto& child = graph.vertices_[link.objidx];
int64_t offset = 0;
switch ((hb_serialize_context_t::whence_t) link.whence) {
case hb_serialize_context_t::whence_t::Head:
offset = child.start - parent.start; break;
case hb_serialize_context_t::whence_t::Tail:
offset = child.start - parent.end; break;
case hb_serialize_context_t::whence_t::Absolute:
offset = child.start; break;
}
assert (offset >= link.bias);
offset -= link.bias;
return offset;
}
inline
bool is_valid_offset (int64_t offset,
const hb_serialize_context_t::object_t::link_t& link)
{
if (unlikely (!link.width))
// Virtual links can't overflow.
return link.is_signed || offset >= 0;
if (link.is_signed)
{
if (link.width == 4)
return offset >= -((int64_t) 1 << 31) && offset < ((int64_t) 1 << 31);
else
return offset >= -(1 << 15) && offset < (1 << 15);
}
else
{
if (link.width == 4)
return offset >= 0 && offset < ((int64_t) 1 << 32);
else if (link.width == 3)
return offset >= 0 && offset < ((int32_t) 1 << 24);
else
return offset >= 0 && offset < (1 << 16);
}
}
/*
* Will any offsets overflow on graph when it's serialized?
*/
inline bool
will_overflow (graph_t& graph,
hb_vector_t<overflow_record_t>* overflows = nullptr)
{
if (overflows) overflows->resize (0);
graph.update_positions ();
hb_hashmap_t<overflow_record_t*, bool> record_set;
const auto& vertices = graph.vertices_;
for (int parent_idx = vertices.length - 1; parent_idx >= 0; parent_idx--)
{
// Don't need to check virtual links for overflow
for (const auto& link : vertices.arrayZ[parent_idx].obj.real_links)
{
int64_t offset = compute_offset (graph, parent_idx, link);
if (likely (is_valid_offset (offset, link)))
continue;
if (!overflows) return true;
overflow_record_t r;
r.parent = parent_idx;
r.child = link.objidx;
if (record_set.has(&r)) continue; // don't keep duplicate overflows.
overflows->push (r);
record_set.set(&r, true);
}
}
if (!overflows) return false;
return overflows->length;
}
inline
void print_overflows (graph_t& graph,
const hb_vector_t<overflow_record_t>& overflows)
{
if (!DEBUG_ENABLED(SUBSET_REPACK)) return;
graph.update_parents ();
int limit = 10;
for (const auto& o : overflows)
{
if (!limit--) break;
const auto& parent = graph.vertices_[o.parent];
const auto& child = graph.vertices_[o.child];
DEBUG_MSG (SUBSET_REPACK, nullptr,
" overflow from "
"%4u (%4u in, %4u out, space %2u) => "
"%4u (%4u in, %4u out, space %2u)",
o.parent,
parent.incoming_edges (),
parent.obj.real_links.length + parent.obj.virtual_links.length,
graph.space_for (o.parent),
o.child,
child.incoming_edges (),
child.obj.real_links.length + child.obj.virtual_links.length,
graph.space_for (o.child));
}
if (overflows.length > 10) {
DEBUG_MSG (SUBSET_REPACK, nullptr, " ... plus %u more overflows.", overflows.length - 10);
}
}
template <typename O> inline void
serialize_link_of_type (const hb_serialize_context_t::object_t::link_t& link,
char* head,
hb_serialize_context_t* c)
{
OT::Offset<O>* offset = reinterpret_cast<OT::Offset<O>*> (head + link.position);
*offset = 0;
c->add_link (*offset,
// serializer has an extra nil object at the start of the
// object array. So all id's are +1 of what our id's are.
link.objidx + 1,
(hb_serialize_context_t::whence_t) link.whence,
link.bias);
}
inline
void serialize_link (const hb_serialize_context_t::object_t::link_t& link,
char* head,
hb_serialize_context_t* c)
{
switch (link.width)
{
case 0:
// Virtual links aren't serialized.
return;
case 4:
if (link.is_signed)
{
serialize_link_of_type<OT::HBINT32> (link, head, c);
} else {
serialize_link_of_type<OT::HBUINT32> (link, head, c);
}
return;
case 2:
if (link.is_signed)
{
serialize_link_of_type<OT::HBINT16> (link, head, c);
} else {
serialize_link_of_type<OT::HBUINT16> (link, head, c);
}
return;
case 3:
serialize_link_of_type<OT::HBUINT24> (link, head, c);
return;
default:
// Unexpected link width.
assert (0);
}
}
/*
* serialize graph into the provided serialization buffer.
*/
inline hb_blob_t* serialize (const graph_t& graph)
{
hb_vector_t<char> buffer;
size_t size = graph.total_size_in_bytes ();
if (!size) return hb_blob_get_empty ();
if (!buffer.alloc (size)) {
DEBUG_MSG (SUBSET_REPACK, nullptr, "Unable to allocate output buffer.");
return nullptr;
}
hb_serialize_context_t c((void *) buffer, size);
c.start_serialize<void> ();
const auto& vertices = graph.vertices_;
for (unsigned i = 0; i < vertices.length; i++) {
c.push ();
size_t size = vertices[i].obj.tail - vertices[i].obj.head;
char* start = c.allocate_size <char> (size);
if (!start) {
DEBUG_MSG (SUBSET_REPACK, nullptr, "Buffer out of space.");
return nullptr;
}
hb_memcpy (start, vertices[i].obj.head, size);
// Only real links needs to be serialized.
for (const auto& link : vertices[i].obj.real_links)
serialize_link (link, start, &c);
// All duplications are already encoded in the graph, so don't
// enable sharing during packing.
c.pop_pack (false);
}
c.end_serialize ();
if (c.in_error ()) {
DEBUG_MSG (SUBSET_REPACK, nullptr, "Error during serialization. Err flag: %d",
c.errors);
return nullptr;
}
return c.copy_blob ();
}
} // namespace graph
#endif // GRAPH_SERIALIZE_HH