|
33cae9b4
|
2024-04-19T21:58:10
|
|
[repacker] If repacking fails for GSUB/GPOS try re-running with extension promotion and table splitting.
|
|
|
d80e0974
|
2023-12-15T22:49:46
|
|
[repacker] Increase repacker max rounds to 32.
Found an example font that needs the higher limit.
|
|
|
7160c5b9
|
2023-12-05T20:58:00
|
|
[repacker] add tests for multi-duplication.
Further improve the resolution attempt by pre-emptively raising priority of a duplicated shared node.
|
|
|
6f64fa75
|
2023-12-05T19:45:16
|
|
[repacker] improve resolution of overflows to shared nodes.
Prior to this change overflows to shared nodes were handled by duplicating the link from only a single parent on each iteration. However, I've encountered fonts where there is a large number of parents sharing a single child. Using the prior strategy requires large number of overflow resolution iterations to resolve overflows. This changes shared overflow resolution to duplicate the shared child and re-assign multiple overflowing parents in a single iteration. This reduces total packing size in these cases and allows resolution to complete in far fewer iterations.
|
|
|
8d22a570
|
2023-08-28T18:33:31
|
|
[repacker] fix potential use after free in repacker.
During table splitting we iterate over the lookups map which can be modified during table splitting. This can result in a use after free in the iterator. Create a local copy of the lookup indices to avoid this.
|
|
|
d7ee328f
|
2023-08-23T22:06:55
|
|
[repacker] include the size of all lookup tables in the layer size estimates from the start.
In extension promotion previously we incrementally added the contribution of the lookup table to the layer size estimates as the lookups were processed. However, this isn't quite correct as regardless of the promotion decision the full lookup table size will be incurred. So the size should be added to the initial sizes.
|
|
ed023f66
|
2023-01-12T17:04:24
|
|
Enable -Wformat-signedness
And fix the codebase.
|
|
|
2eacc37e
|
2022-12-31T12:27:13
|
|
[vector] Add internal API for exact-size allocation
Use it from a couple of places.
|
|
|
35233d25
|
2022-12-07T00:47:28
|
|
[repacker] fix fuzzer reported stack overflow.
Fixes https://oss-fuzz.com/testcase-detail/6014493291577344.
|
|
|
554ed06f
|
2022-12-01T21:51:17
|
|
[repacker] add cycle detection to the graph sort.
This allows us to bail early if the graph is not acyclic.
|
|
|
edf7a295
|
2022-09-08T22:59:34
|
|
[repacker] Validate link positions before running the repacker.
|
|
|
deca30b2
|
2022-09-08T21:10:06
|
|
[repacker] get repacker fuzzer working.
Additionally add helper method that allows a graph to be saved as a fuzzer seed.
|
|
|
985b19f6
|
2022-09-07T22:21:16
|
|
[repacker] begin implementing a fuzzer for the repacker api.
|
|
c813f842
|
2022-10-20T19:45:23
|
|
Make build work for arm-none-eabi
|
|
|
99f4668e
|
2022-09-29T19:39:59
|
|
[repacker] use mutable copies of Coverage/ClassDef in MarkBasePos shrink operation.
Also make mutable copies (when needed) of the top level subtables during a split operation.
|
|
|
a91bfeed
|
2022-08-18T22:01:48
|
|
[repacker] comment cleanup.
|
|
|
5cf2a25a
|
2022-08-15T22:49:24
|
|
[repacker] Expose on internal method in the repacker that allows the caller to pass in/out a graph.
Will be used in testing so we can compare graphs instead of packed result.
|
|
|
2a5902ee
|
2022-07-29T18:12:49
|
|
[repacker] cleanup.
|
|
|
fb3f6ad7
|
2022-07-29T00:25:19
|
|
[repacker] ensure lookup map is updated when lookup memory location changes.
|
|
|
65afed04
|
2022-07-28T20:54:28
|
|
[repacker] more bug fixes.
|
|
|
8e5fffc4
|
2022-07-27T20:00:00
|
|
[repack] add helper to create new nodes.
Switch to malloc'ing each node individually rather than trying to guess up front the total buffer space needed.
|
|
|
f6a242b6
|
2022-07-27T18:58:41
|
|
[repacker] begin adding PairPos splitting support.
|
|
|
5f4adb9b
|
2022-07-25T21:59:57
|
|
[repacker] fix to lookup size comparison.
|
|
|
f56e66f3
|
2022-07-25T21:55:03
|
|
[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.
|
|
|
9d0b2da5
|
2022-07-25T20:46:49
|
|
[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
|
|
|
3d37b9f4
|
2022-07-25T20:11:24
|
|
[repacker] when calculating 16bit space size also consider ext lookup subtables.
|
|
|
9db3beb7
|
2022-07-25T19:42:58
|
|
[repacker] include LookupList size when calculating size of 16bit space for ext promotion decisions.
|
|
|
7de136f8
|
2022-07-22T21:04:34
|
|
[repacker] add ext promotion test.
|
|
|
c38896e0
|
2022-07-21T23:12:15
|
|
[repacker] todo.
|
|
|
ad0041f5
|
2022-07-21T22:50:14
|
|
[repacker] Add basic version of the extension promotion selection algorithm.
|
|
|
11709f0f
|
2022-07-21T21:54:42
|
|
[repacker] support extension promotion in 24bit GSUB/GPOS.
|
|
|
ae290ff4
|
2022-07-21T21:45:04
|
|
[repacker] add sanitization for GSUB/LookupList/Lookup during extension promotion.
|
|
|
ce03c353
|
2022-07-21T19:07:55
|
|
[repacker] add make_extension_context_t.
|
|
|
ebb64b50
|
2022-07-21T18:36:20
|
|
[repacker] size buffer correctly.
|
|
|
7e6f6c3e
|
2022-07-20T03:26:29
|
|
[repack] fix new node bounds.
|
|
|
b1d38a6d
|
2022-07-19T23:33:16
|
|
[repack] WIP implement extension promotion mechanism.
|
|
|
3f7a74ff
|
2022-07-19T21:50:13
|
|
[repacker] WIP extension promotion implementation.
|
|
|
9c251898
|
2022-07-13T22:55:58
|
|
[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.
|
|
|
a369ab13
|
2022-07-13T19:00:08
|
|
[repacker] Increase max_rounds when called via public api.
|
|
|
401066bf
|
2022-07-06T18:44:40
|
|
[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.
|
|
|
7078560e
|
2022-06-24T19:20:20
|
|
[repacker] extract graph serialization code into a seperate file.
|
|
|
20b02a67
|
2022-06-24T18:58:17
|
|
[repacker] Begin splitting up the repacker implementation into several files.
|
|
|
af74ab45
|
2022-06-16T18:12:09
|
|
[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.
|
|
|
e9c0a740
|
2022-06-15T16:57:16
|
|
Fix clang -Wcomma warnings
Fixes https://github.com/harfbuzz/harfbuzz/issues/3656
|
|
|
997d9cc4
|
2022-06-02T18:04:12
|
|
[map] Make unique_ptr hashable
|
|
|
ec6cefc4
|
2022-05-26T11:26:37
|
|
[repacker] Simplify map types
|
|
|
371e14d9
|
2022-05-28T13:40:30
|
|
Combine uses of map has() then get() with has(.., &..)
|
|
|
cbf8f44c
|
2022-05-19T21:25:21
|
|
[subset-perf] swap instead of copying vertice's when reordering during sort.
|
|
|
b32ca2a2
|
2022-05-19T20:45:39
|
|
[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.
|
|
|
bff8248a
|
2022-05-18T16:25:03
|
|
[repacker] Pre-alloc vertices
|
|
|
c7317ef7
|
2022-05-18T16:03:41
|
|
[repacker] Avoid destroying and recreating objects
|
|
|
864e09a0
|
2022-05-18T15:59:29
|
|
[repacker] Reuse allocated vector
|
|
|
ca77f164
|
2022-05-18T15:55:49
|
|
[repacker] Remove unnecessary vector .fini() calls
|
|
a35757c6
|
2022-02-02T10:30:34
|
|
[repacker] expose hb_subset_repack() API, hb_object_t and hb_link_t structs
|
|
|
112cb9fe
|
2022-01-19T15:31:35
|
|
[repacker] Fix missing initilization of obj in vertex_t.
|
|
|
15cceff3
|
2022-01-17T15:53:01
|
|
[repacker] Replace fini_deep() with fini()
Vector calls destructor now.
|
|
e2e30506
|
2022-01-16T07:00:53
|
|
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`
|
|
|
c4573c2e
|
2021-12-14T14:49:15
|
|
[repacker] don't infinite loop if visited or roots is in error.
Fixes https://oss-fuzz.com/testcase-detail/5205038086094848
|
|
|
5914acb3
|
2021-12-10T10:05:47
|
|
[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.
|
|
|
be2c488e
|
2021-12-09T15:44:06
|
|
[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.
|
|
|
3e4a2509
|
2021-12-06T16:00:15
|
|
[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.
|
|
|
02b12d79
|
2021-12-06T15:23:35
|
|
[repacker] Move all overflowing roots to a new space simultaneously.
|
|
|
fa966bcc
|
2021-12-06T12:54:19
|
|
[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.
|
|
|
39e76af1
|
2021-11-30T15:25:40
|
|
[subset] add all_links () to object_t.
Helper to provide easy access to concatenated real and virtual links iterator.
|
|
|
9121ed0c
|
2021-11-30T13:45:22
|
|
[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.
|
|
|
7615b94e
|
2021-09-23T14:14:06
|
|
[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.
|
|
|
8c055699
|
2021-11-01T17:59:17
|
|
[algs] Add hb_swap() ala, and using, std::swap()
Use it in vector.
Use ADL idiom.
|
|
|
42626369
|
2021-10-23T13:18:22
|
|
Merge pull request #3248 from googlefonts/connected_components
[repacker] Keep connected subgraphs in the same space.
|
|
|
d17155f5
|
2021-10-13T14:40:00
|
|
[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.
|
|
|
a7a36085
|
2021-10-12T16:11:25
|
|
[docs] Rename overflow_resolution to repacker
|
|
|
6bc64317
|
2021-10-12T13:13:32
|
|
Add a writeup of the overflow resolution algorithm in harfbuzz.
|
|
|
5b882c42
|
2021-10-06T11:12:32
|
|
[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.
|
|
|
ff7a86e9
|
2021-10-06T10:51:45
|
|
[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.
|
|
|
8cae8b65
|
2021-10-05T14:03:02
|
|
[repacker] add missing fini for parents vector.
|
|
|
7883b7ed
|
2021-10-05T12:46:59
|
|
[repacker] Add additional splitting spaces test.
Fix issues it uncovered.
|
|
|
d97bd426
|
2021-10-05T10:53:05
|
|
[repacker] when assigning spaces use post isolation node indices.
isolate_subgraph can result in some of the roots being duplicated and moved to new indices, so do subgraph isolation before assign roots to spaces.
|
|
|
375a6c8f
|
2021-09-29T18:14:57
|
|
[repacker] add the ability to move subgraphs from a shared space into their own space.
Used to resolve overflows during manual resolution.
|
|
|
0dccbf36
|
2021-09-29T14:28:27
|
|
[repacker] Handle the case where a subgraph root has an incoming 32 and 16 bit edge.
In this case the entire subgraph from that root will be duplicated.
|
|
|
816c5302
|
2021-09-28T16:04:27
|
|
[repacker] restrict 32 bit subgraph connected component search to only nodes reachable via directed links.
|
|
|
67eb222b
|
2021-09-28T13:36:06
|
|
[repacker] when assigning each connected subgraph a space, also isolate it.
This will break any links coming from space 0 (ie. the 16 bit offset only space).
|
|
|
307acf7f
|
2021-09-28T12:08:18
|
|
[repacker] add space assignment based on connected components.
Assign each connected component that is underneath one or more 32 bit offsets into a unique space. This ensures that 32 bit subgraphs which are connected are packed into the same space.
|
|
|
c77bdf1d
|
2021-09-24T15:58:57
|
|
[repacker] begin storing each nodes parents.
Will be used for connected component search.
|
|
|
efda2f14
|
2021-09-24T16:28:34
|
|
[repacker] fix bug in subgraph isolation.
Prior to this fix id remapping at the end of the isolation operation was fed the old subgraph instead of the new one. Which results in object indices being remapped for the nodes outside of the new subgraph. Adds a test which detects this problem.
|
|
|
fe155de9
|
2021-09-10T14:55:24
|
|
[repacker] handle a couple of duplication edge cases.
- Detect cases where there are multiple links from a parent to a child. Don't duplicate that child if those are the only remaining links to the child.
- Correctly handle isolating a subgraph where the root idx has multiple incoming links.
|
|
|
c19ec97d
|
2021-09-09T10:53:09
|
|
[repacker] reduce the bits used by order by 2 to give more bits to distance.
|
|
|
d0daa7a5
|
2021-09-09T10:25:43
|
|
[repacker] add a couple more complex isolation tests.
|
|
|
62c502cd
|
2021-09-09T09:57:42
|
|
[repacker] correctly update incoming_edges in duplicate.
|
|
|
a57ef8df
|
2021-09-08T17:31:39
|
|
[repacker] default space to 0.
Since vector push() init's new objects to all zeros.
|
|
|
58facaad
|
2021-09-08T16:08:48
|
|
[repacker] put each 32 bit subgraph into it's own packing space.
Each subgraph pointed to by a 32 bit offset should be packed into it's own space. This adds a space property to vertices which affects the distance calculation. This effectively places the distances for all of the nodes of a 32 bit subgraph into a distinct range. Thus all of the nodes of the subgraph will be packed together.
|
|
|
543a3f97
|
2021-09-08T15:07:02
|
|
[repacker] Add repacker test for subgraph isolation.
|
|
|
7147f169
|
2021-09-08T13:44:25
|
|
[repacker] recursively duplicate nodes during isolation.
If a node is duplicated during isolation then any children it has will have incoming links from outside the subgraph (from the duplicated node and the original node), so they must be duplicated too.
|
|
|
41bbf281
|
2021-09-08T10:14:00
|
|
[repacker] do extension subtable isolation before starting resolution attempts.
|
|
|
8d8b7458
|
2021-09-07T16:52:37
|
|
[repacker] extract overflows processing into its own method.
|
|
|
b14b3f13
|
2021-09-07T16:32:13
|
|
[repacker] begin implementing the ability to isolate extension subtables.
Adds isolate_subgraph operation to the repacker. This severs any links from outside a subgraph by duplicating the affected vertices. This will be used to isolate the subgraphs of a extension subtable from the rest of object graph. Thus allowing the extension subtable to be packed far away from the rest of the objects.
|
|
|
02c4a516
|
2021-09-07T13:22:19
|
|
Add a debug message when offset overflow resolution fails.
|
|
|
74f96d9d
|
2021-09-17T13:46:07
|
|
[repacker] fix heap use after free in repacker.
Don't store a reference to the link in overflow records as the link object may be freed if the sorted graph vector is resized.
|
|
|
2337f0d0
|
2021-07-08T10:58:50
|
|
Internally use hb_malloc/.../hb_free instead of malloc/.../free
Redefining those stock names as macros was conflicting with gcc 10
headers.
Fixes https://github.com/harfbuzz/harfbuzz/issues/3044
|
|
|
5e0ec33b
|
2021-05-12T14:46:54
|
|
Error when link width not in [2, 4]
|
|
|
b23f29bf
|
2021-04-17T09:59:45
|
|
[subset] Add subset () method for COLRv1 Paint tables, BaseGlyphV1List and LayerV1List
Also add support for Offset24 in serializer and repacker
|
|
|
ec432106
|
2021-04-19T17:18:05
|
|
[subset] fix infinite loop caused by alloc failure in repacker.
Fixes: https://oss-fuzz.com/testcase-detail/5609112151916544.
|