Commit Graph

100 Commits

Author SHA1 Message Date
Garret Rieger f2b9065246 [repacker] for ext promotion choose lookups from highest subtables per byte to lowest.
Attempts to roughly maximize the number of subtables that are non-ext.
2022-07-25 21:55:03 +00:00
Garret Rieger e4fd5ff727 [repacker] count subtable size in each group of consecutive layers for extension promotion decisions.
Enforce that the following groups are all <64k in size:
- LookupList + Lookups
- Lookups + SubTables
- SubTables + Descendants
2022-07-25 21:31:17 +00:00
Garret Rieger 0a5b69b255 [repacker] when calculating 16bit space size also consider ext lookup subtables. 2022-07-25 20:11:24 +00:00
Garret Rieger fa177b7f33 [repacker] include LookupList size when calculating size of 16bit space for ext promotion decisions. 2022-07-25 19:42:58 +00:00
Garret Rieger ffb0f7936f [repacker] add ext promotion test. 2022-07-22 22:36:04 +00:00
Garret Rieger 7ebc92f2e0 [repacker] todo. 2022-07-21 23:12:15 +00:00
Garret Rieger 8c6afa69d5 [repacker] Add basic version of the extension promotion selection algorithm. 2022-07-21 22:50:14 +00:00
Garret Rieger 2f63f0c861 [repacker] support extension promotion in 24bit GSUB/GPOS. 2022-07-21 21:54:42 +00:00
Garret Rieger ede7b74584 [repacker] add sanitization for GSUB/LookupList/Lookup during extension promotion. 2022-07-21 21:45:04 +00:00
Garret Rieger c61c05e431 [repacker] add make_extension_context_t. 2022-07-21 19:07:55 +00:00
Garret Rieger f2a0e69162 [repacker] size buffer correctly. 2022-07-21 18:36:20 +00:00
Garret Rieger 5babfda3f2 [repack] fix new node bounds. 2022-07-20 03:26:29 +00:00
Garret Rieger c20b85cfed [repack] WIP implement extension promotion mechanism. 2022-07-19 23:33:16 +00:00
Garret Rieger d9295d88a7 [repacker] WIP extension promotion implementation. 2022-07-19 21:50:13 +00:00
Garret Rieger 9c2518988d [repack] Don't count space isolation against round limit.
Restore max rounds to 20 but don't count space isolation against the limit. The number of iterations space isolation can make changes for is already bounded to a reasonable max (the number of lookups in the font) so no need to cap the number of iterations.
2022-07-13 20:24:59 -06:00
Garret Rieger a369ab133b [repacker] Increase max_rounds when called via public api. 2022-07-13 14:01:42 -06:00
Garret Rieger 401066bf3d [subset] Prepare the repacker for handling 24bit offsets in GSUB/GPOS.
The boring expansion (https://github.com/be-fonts/boring-expansion-spec) plans to introduce 24bit offsets into GSUB/GPOS. This changes the repacker to treat 24 bit offsets similar to 32 bit offsets and assign the top level 24 bit offsets into spaces to improve packing.
2022-07-06 18:44:40 +00:00
Garret Rieger 7078560e33 [repacker] extract graph serialization code into a seperate file. 2022-06-24 17:16:50 -06:00
Garret Rieger 20b02a672d [repacker] Begin splitting up the repacker implementation into several files. 2022-06-24 17:16:50 -06:00
Garret Rieger af74ab452f [repack] always run the sort in repack.
This is needed to ensure virtual link ordering constraints are respected when repack is being called from fontTools. For subset usage, repack won't be called if the graph doesn't already overflow so this change doesn't cause any extra work.
2022-06-16 15:17:58 -06:00
Behdad Esfahbod e9c0a74063 Fix clang -Wcomma warnings
Fixes https://github.com/harfbuzz/harfbuzz/issues/3656
2022-06-15 17:28:36 -06:00
Behdad Esfahbod 997d9cc466 [map] Make unique_ptr hashable 2022-06-02 18:47:42 -06:00
Behdad Esfahbod ec6cefc46a [repacker] Simplify map types 2022-05-30 05:54:20 -06:00
Behdad Esfahbod 371e14d99c Combine uses of map has() then get() with has(.., &..) 2022-05-28 13:40:30 -06:00
Garret Rieger cbf8f44c9b [subset-perf] swap instead of copying vertice's when reordering during sort. 2022-05-20 09:41:18 -06:00
Garret Rieger b32ca2a292 [subset-perf] remove sort_kahn from repacker.
Without an optimized FIFO queue implementation it's nearly as slow as the now optimized sort_shortest_distance.
2022-05-20 09:41:18 -06:00
Behdad Esfahbod bff8248a9d [repacker] Pre-alloc vertices 2022-05-18 16:25:03 -06:00
Behdad Esfahbod c7317ef761 [repacker] Avoid destroying and recreating objects 2022-05-18 16:03:41 -06:00
Behdad Esfahbod 864e09a0c4 [repacker] Reuse allocated vector 2022-05-18 15:59:29 -06:00
Behdad Esfahbod ca77f16470 [repacker] Remove unnecessary vector .fini() calls 2022-05-18 15:55:49 -06:00
Qunxin Liu a35757c6bc [repacker] expose hb_subset_repack() API, hb_object_t and hb_link_t structs 2022-03-10 17:26:20 -07:00
Garret Rieger 112cb9fe69 [repacker] Fix missing initilization of obj in vertex_t. 2022-01-20 08:03:52 -08:00
Behdad Esfahbod 15cceff3d7 [repacker] Replace fini_deep() with fini()
Vector calls destructor now.
2022-01-17 16:46:45 -07:00
luz paz e2e305066a Fix various typos
Found via `codespell -q 3 -S ./perf/texts -L actualy,ba,beng,fo,gir,inout,nd,ot,pres,ro,te,teh,timne`
2022-01-16 05:39:03 -08:00
Garret Rieger c4573c2ec7 [repacker] don't infinite loop if visited or roots is in error.
Fixes https://oss-fuzz.com/testcase-detail/5205038086094848
2021-12-14 15:57:48 -07:00
Garret Rieger 5914acb3cb [repacker] Clear distance and position cache when assigning a new space.
A change in space will effect the distance assigned to the node and any of it's children so clear the distance cache.
2021-12-10 11:09:03 -07:00
Garret Rieger be2c488e5d [repacker] Improve vertex priority packing.
Previous priority implementation would move a node further back within it's layer, but at max priority was unable to move any further up than that. This updates the implementation to have 3 priority levels:
1. Distance is reduced by half of table size.
2. Distance is reduced by full table size (move to beginning of the layer).
3. Distance is set to 0. Vertex will be packed as soon as possible.

Also makes the iterative resolutions aware of max priority, so it won't keep trying to raise priority beyond the maximum.
2021-12-09 17:46:52 -07:00
Garret Rieger 3e4a25098d [repacker] add a maximum number of roots that can be moved in one iteration.
Set to half of the roots in a space. This prevents the repacker from moving all roots in a space to a new space if their are overflows in every root.
2021-12-06 21:27:28 -07:00
Garret Rieger 02b12d7965 [repacker] Move all overflowing roots to a new space simultaneously. 2021-12-06 21:27:28 -07:00
Garret Rieger fa966bcc29 [repacker] create repacker output buffer after final length is known.
Don't rely on a buffer provided by the caller, as it may not be large enough.
2021-12-06 21:27:28 -07:00
Garret Rieger 39e76af19e [subset] add all_links () to object_t.
Helper to provide easy access to concatenated real and virtual links iterator.
2021-12-01 08:37:04 -07:00
Garret Rieger 9121ed0cec [subset] Improve sharing of Ligature subtables.
Ligature subtables use virtual links to enforce an ordering constraint between the subtables and the coverage table. Unfortunately this has the sideeffect of prevent the subtables from being shared by another Ligature with a different coverage table since object equality compares all links real and virtual. This change makes virtual links stored separately from real links and updates the equality check to only check real links. If an object is de-duped any virtual links it has are merged into the object that replaces it.
2021-12-01 08:37:04 -07:00
Garret Rieger 7615b94ecf [repacker] add 'virtual links' to the serializer.
These aren't associated with an offset field, but instead exist solely to add an ordering constraint to the object graph.
2021-11-02 12:19:13 -06:00
Behdad Esfahbod 8c05569930 [algs] Add hb_swap() ala, and using, std::swap()
Use it in vector.

Use ADL idiom.
2021-11-01 17:59:17 -06:00
Behdad Esfahbod 4262636926
Merge pull request #3248 from googlefonts/connected_components
[repacker] Keep connected subgraphs in the same space.
2021-10-23 13:18:22 -07:00
Garret Rieger d17155f5d2 [repacker] use possibly updated root idx after isolate_subgraph.
isolate_subgraph can change the root indices in some cases. So operations after the isolation need to use the roots from the output of isolate_subgraph.
2021-10-13 14:40:00 -07:00
Behdad Esfahbod a7a3608553 [docs] Rename overflow_resolution to repacker 2021-10-12 16:11:25 -07:00
Garret Rieger 6bc64317ca Add a writeup of the overflow resolution algorithm in harfbuzz. 2021-10-12 17:10:07 -06:00
Garret Rieger 5b882c420a [repacker] performance optimizations for topological sorting.
- Presize the output sorted graph and write it once in the correct order to avoid needing to reverse.
- Swap the old/new graph vectors instead of copying.
- Use a boolean vector for tracking visited instead of a set.
2021-10-06 11:43:47 -07:00
Garret Rieger ff7a86e9b0 [repacker] remove clone buffer, they are unnessecary.
When nodes are duplicated it's fine to just reuse head, tail from the node being cloned since we don't modify the contents.
2021-10-06 10:51:45 -07:00