CFF Subroutinizer

[be5invis]

• [ ] Add a Subroutinizer to CFF support (in charstring_il.c, or a separate file).
• [ ] Assign to otfcc’s -O3

cc. @huntzhan @schriftgestalt

[be5invis]

Objective: Extract one subroutine from the existing charstrings or subroutine definitions, which is defined as the most "valuable" common substrings in them. The value is calculated as (length - 2) × ((non-overlapping occurrences) - 1).

A program may be either a charstring or a subroutine. A charstring follows:

any* (rmoveto_operator | hmoveto_operator | vmoveto_operator) ((operand * | progid) operator special*)+ endchar_operator
                                                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

while a subroutine follows

 ((operand * | progid) operator special*)+ return_operator
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

When analyzing a program, you should only analyze the range with wavy underline above, using this pattern:

(operand * | progid) operator special*

as its basic unit.

Your extracted subroutine should follow this pattern either.

Interface: cff_CharstringIL extract_subroutine(cff_CharstringIL *in, uint32_t cs_length, uint32_t sr_length, uint16_t progid);

• cs: The array of input programs. The programs will be modified.
• cs_length: the quantity of charstrings in in.
• sr_length: The quantity of existing subroutines in in. cs_length + sr_length == the length of in.
• progid: The subroutine ID of the subroutines.
• return value: The extracted subroutine. If all substrings in in do not have positive value, return NULL. Otherwise, return a new charstring_il containing its content and a return command (IL_TYPE_OPERATOR with i equal to op_return), and replace all its occurrences in in with a call stub (which is a IL_TYPE_PROGID argument and a IL_TYPE_OPERATOR with i = op_callgsubr).

Limitations:

• The stack depth used for subroutine invocation is 10. See Appendix B of (Ado1).

cc. @clerkma

[be5invis]

@huntzhan @clerkma @schriftgestalt

Found papers about this:

• Alberto Apostolico, Stefano Lonardi: Off-Line Compression by Greedy Textual Substitution. Proc. IEEE, vol. 88 no. 11, pp. 1733-1744, Nov. 2000
• Alberto Apostolico, Stefano Lonardi: Some Theory and Practice of Greedy Off-Line Textual Substitution. Data Compression Conference 1998:119-128
• Alberto Apostolico, Stefano Lonardi: Compression of Biological Sequences by Greedy Off-Line Textual Substitution. Data Compression Conference 2000:143-152

[be5invis]

Done.