On 11/10/2018 11:10, Werner LEMBERG wrote: > >> I've recently came across ft_adobe_glyph_list array which is a 56kB >> table. It seems that it's possible to compress it better by >> extracting duplicate substrings possibly at some small performance >> cost. >> >> My preliminary calculations put the size of the optimized table >> somewhere between 24-26kB. That would be 30kB savings which is >> non-insignificant part of the freetype library. >> >> Would you be interested in this kind of optimization? I'd be glad >> to continue working on it. > > Yes, I'm interested! However, before you are investing more time into > it, could you give us a reference to what algorithm you plan to use? > Alternatively, please outline with a few words how you are going to > implement the compression. >
The size reduction is a result of several optimizations: - the most common substrings are deduplicated by putting them into a single location and referring to them by index. We use the fact that the AGL uses only ~90 ASCII points out of 256 available, so we can fit enough indices into the byte that previously referred to the letter of the node. The "notlast" field is no longer used. - the size of the node and its value is reduced from 3 to 2 bytes in a lot of cases. This has been achieved by noticing that with some remap function 13 bits are enough to store information required to produce the original 16-bit unicode value. - the size needed to represent links from a node to its children has been reduced from 2*<num_children> bytes to <num_children>-1 bytes in a lot of cases. We notice that most nodes have few children which are nearby, so instead of absolute offset in the table we use child size as a way to get relative offset and thus absolute offset. This makes binary search slower in such cases, but linear search is likely not much slower in nodes with few children anyway. - a\d+ and afii\d+ entries are handled separately in a simple, but more optimized format. All of the above increase the complexity and size of the retrieval function. Unfortunately we can't know the impact of the changes until basically everything is finished and we do tests. Maybe the slowdown will be so severe that the proposal does not make sense :-) Regards, Povilas _______________________________________________ Freetype mailing list Freetype@nongnu.org https://lists.nongnu.org/mailman/listinfo/freetype