Debian Codegraph @

podofo/3rdparty/adobe/afdko/source/cffwrite/cffwrite_subr.c

raw
1 /* Copyright 2014 Adobe Systems Incorporated (http://www.adobe.com/). All Rights Reserved.
2 This software is licensed as OpenSource, under the Apache License, Version 2.0.
3 This license is available at: http://opensource.org/licenses/Apache-2.0. */
4 /***********************************************************************/
5
6 /* Temporary debug control */
7 #define TC_DEBUG 0
8 #define DB_FONT 0 /* Font input charstrings */
9 #define DB_INFS 0 /* Inferior subr selection */
10 #define DB_ASSOC 0 /* Associate with subrs */
11 #define DB_RELNS 0 /* Subr relationship building */
12 #define DB_SELECT 0 /* Subr selection */
13 #define DB_GROUPS 0 /* Selected groups */
14 #define DB_CHARS 0 /* Chars with selected subrs */
15 #define DB_SUBRS 0 /* Subrs with selected subrs */
16 #define DB_CALLS 0 /* Call counts */
17
18 #define EDGE_HASH_STAT 0 /* Collect edge hash table statistics */
19
20 /*
21 T2 subroutinizer.
22
23 The idea of the subroutinizer is to reduce the size of a font by replacing all
24 repeated charstring code in a font by references to a single instance of that
25 code. This idea may be extended to a number of fonts in a FontSet where
26 repeated charstring code in different fonts is replaced. The single instance of
27 charstring code is stored as a subroutine and is assigned a unique subroutine
28 number that may be used to identify it.
29
30 In CFF technology charstring repeats that occur within a single font or across
31 multiple fonts are stored in 2 separate data structures and are known as the
32 "local" and "global" subroutines, respectively. Local and global subroutines
33 are referenced by calling them with the callsubr or callgsubr operators,
34 respectively. These operators take a subroutine number, which serves to
35 identify the subroutine, as an argument. The local and global subroutine number
36 spaces identify different sets of subroutines, therefore local subroutine
37 number 1 is distinct from global subroutine number 1.
38
39 ...
40
41 The most challenging part of the process of subroutinization is finding and
42 counting the repeated charstrings. This is achieved by first building a suffix
43 CDAWG using the concatenation of all the charstrings from all the fonts as
44 input. Subsequently the completed suffix CDAWG is traversed in order to count
45
46 The suffix CDAWG is built as a compact DAWG (CDAWG) using an algorithm described in paper
47 "On-Line Construction of Compact Directed Acyclic Word Graphs" (200), S. Inenaga, et. al.
48 <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.474> which is an extension
49 to the compact suffix tree construction algorithm "On-line construction of suffix trees"
50 (1995) by Esko Ukkonen <http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf>
51
52 The original code used a DAWG algorithm described in "Text Algorithms, Maxime Crochemore
53 and Wojciech Ryter, OUP" p.113. CDAWG is expected to use less memory than DAWG.
54
55 ...
56 regular.saved = count * (length - call - num) - (off + length + ret);
57 tail.saved = count * (length - call - num) - (off + length);
58
59 Bytes saved for various counts and lengths.
60
61 Following table calculated with the following parameters:
62
63 callsubr 1
64 subr# 1
65 offset 2
66 return 1
67 length
68 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
69 +------------------------------------------------------------------------
70 2| -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
71 3| -3 -1 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
72 c 4| -2 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49
73 o 5| -1 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 67
74 u 6| 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85
75 n 7| 1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97 103
76 t 8| 2 9 16 23 30 37 44 51 58 65 72 79 86 93 100 107 114 121
77 9| 3 11 19 27 35 43 51 59 67 75 83 91 99 107 115 123 131 139
78 10| 4 13 22 31 40 49 58 67 76 85 94 103 112 121 130 139 148 157
79 +------------------------------------------------------------------------
80
81 Following table calculated with the following parameters:
82
83 callsubr 1
84 subr# 2
85 offset 2
86 return 1
87 length
88 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
89 +------------------------------------------------------------------------
90 2| -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11
91 3| -6 -4 -2 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
92 c 4| -6 -3 0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45
93 o 5| -6 -2 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
94 u 6| -6 -1 4 9 14 19 24 29 34 39 44 49 54 59 64 69 74 79
95 n 7| -6 0 6 12 18 24 30 36 42 48 54 60 66 72 78 84 90 96
96 t 8| -6 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 113
97 9| -6 2 10 18 26 34 42 50 58 66 74 82 90 98 106 114 122 130
98 10| -6 3 12 21 30 39 48 57 66 75 84 93 102 111 120 129 138 147
99 +------------------------------------------------------------------------
100
101 */
102
103 #include "cffwrite_subr.h"
104 #include "cffwrite.h"
105
106 #include <limits.h>
107 #include <stdio.h>
108 #include <stdlib.h>
109 #include <string.h>
110
111 #include "dynarr.h"
112
113 #define DB_TEST_STRING 0
114 #if DB_TEST_STRING
115 static unsigned char *gTestString = (unsigned char *)"Humpty Dumpty sat on a wall.Humpty Dumpty had a great fall.";
116 #define FONT_CHARS_DATA gTestString
117 #define OPLEN(h, cstr) 1
118 #define SEPARATOR ','
119 #else
120 #define FONT_CHARS_DATA font->chars.data
121 #define OPLEN(h, cstr) ((h)->opLenCache[*(cstr)] == 0 ? (cstr)[1] : (h)->opLenCache[*(cstr)])
122 #define SEPARATOR t2_separator
123 #endif
124
125 #define MAX_NUM_SUBRS 32765L /* Maximum number of subroutines in one INDEX structure. 64K is valid by the spec, but the Google font validation tool OTS rejects fonts with subrs in a subrindex which is over 32K -3.*/
126
127 /* --- Memory management --- */
128 #define MEM_NEW(g, s) cfwMemNew(g, s)
129 #define MEM_FREE(g, p) cfwMemFree(g, p)
130
131 /* ------------------------------- CDAWG data ------------------------------- */
132 typedef struct Edge_ Edge;
133 typedef struct Node_ Node;
134 struct Edge_ {
135 unsigned char *label; /* Pointer to the edge label, or the beginning of the edge string */
136 Node *son; /* Son node. red/black color is encoded as the LSB in this pointer */
137 unsigned length; /* Length of the edge string */
138 };
139 struct Node_ {
140 Node *suffix; /* Suffix link */
141 Edge *edgeTable; /* Pointer to the edge table */
142 long misc; /* Initially longest path from root, then subr index */
143 unsigned edgeCount; /* Number of edges from this node */
144 unsigned edgeTableSize; /* Number of entries allocated in the edge table */
145 unsigned short paths; /* Paths through node; depth for subr trie */
146 unsigned short id; /* Font id */
147 #define NODE_GLOBAL USHRT_MAX /* Identifies global subr */
148 #define NODE_ANY (NODE_GLOBAL - 1)
149 short flags; /* Status flags */
150 #define NODE_COUNTED (1 << 15) /* Paths have been counted for this node */
151 #define NODE_TESTED (1 << 14) /* Candidacy tested for this node */
152 #define NODE_FAIL (1 << 13) /* Node failed candidacy test */
153 #define NODE_TAIL (1 << 12) /* Tail subr (terminates with endchar in CFF1 or CFF2) */
154 #define NODE_SUBR (1 << 11) /* Node has subr info (index in misc) */
155 };
156
157 typedef struct NodeLink_ NodeLink;
158 struct NodeLink_ {
159 Node *node;
160 NodeLink *next;
161 };
162 /* ------------------------------- hash table parameters ------------------------------- */
163
164 #define EDGE_TABLE_SMALLEST_SPARSE_SIZE 128 /* Double the hash table size even before it becomes full beyond this size */
165 #define EDGE_TABLE_SIZE_USE_SIMPLE_HASH 16 /* Use a better hash function for edges if the table size is larger than this */
166
167 /* ------------------------------- Call list ------------------------------- */
168
169 typedef struct /* Subr call within charstring */
170 {
171 struct Subr_ *subr; /* Inferior subr */
172 uint32_t offset; /* Offset within charstring */
173 } Call;
174
175 typedef dnaDCL(Call, CallList); /* List of subr calls for a subr/charstring */
176 typedef dnaDCL(CallList, CallLists); /* List of call lists for charstrings */
177
178 /* ------------------------------- Subr data ------------------------------- */
179 typedef struct Subr_ Subr;
180 typedef struct Link_ Link;
181 struct Subr_ {
182 Node *node; /* Associated node */
183 Link *sups; /* Superior subrs */
184 Link *infs; /* Inferior subrs */
185 Subr *next; /* Next member of social group */
186 Subr *output; /* Link to next subr for match trie output */
187 unsigned char *cstr; /* Charstring */
188 uint32_t length; /* Subr length (original bytes spanned) */
189 uint32_t count; /* Occurrence count */
190 int32_t deltalen; /* Delta length */
191 short subrnum; /* Biased subr number */
192 short numsize; /* Size of subr number (1, 2, or 3 bytes) */
193 short maskcnt; /* hint/cntrmask count */
194 short misc; /* subrSaved value/call depth (transient) */
195 short flags; /* Status flags */
196 #define SUBR_SELECT (1 << 0) /* Flags subr selected */
197 #define SUBR_REJECT (1 << 1) /* Flags subr rejected */
198 #define SUBR_MEMBER (1 << 2) /* Flags subr added to social group */
199 size_t order; /* index value used for stable sort. */
200 CallList callList; /* subrs called by this subr */
201 #if DB_CALLS
202 short calls; /* xxx remove */
203 #endif
204 };
205
206 #define SUBR_MARKED (SUBR_SELECT | SUBR_REJECT) /* Flags if subr marked */
207
208 struct Link_ /* Social group link */
209 {
210 Subr *subr; /* Superior/inferior subr */
211 Link *next; /* Next record */
212 uint32_t offset; /* Offset within superior/inferior */
213 };
214
215 typedef dnaDCL(Subr *, SubrList); /* List of subrs */
216
217 typedef struct MemBlk_ MemBlk;
218 struct MemBlk_ /* Generalized memory block for object allocation */
219 {
220 MemBlk *nextBlk; /* Next memory block in chain */
221 char *array; /* Object array */
222 short iNext; /* Next free element index */
223 };
224
225 typedef struct {
226 MemBlk *head; /* Allocated block list */
227 MemBlk *free; /* Free block list */
228 } MemInfo;
229
230 #define NODES_PER_BLK 5000
231 #define LINKS_PER_BLK 1000
232 #define NODE_LINKS_PER_BLK 500
233 #define TRIE_NODES_PER_BLK 1000
234
235 /* Subroutinization context */
236 struct subrCtx_ {
237 MemInfo nodeBlks; /* Node blocks */
238 MemInfo linkBlks; /* Relation blocks */
239 MemInfo trieNodeBlks; /* Trie node blocks */
240 MemInfo nodeLinkBlks; /* Node link blocks */
241
242 Node *root; /* CDAWG root */
243 Node *base; /* CDAWG base */
244 dnaDCL(Node *, sinks); /* CDAWG sinks (one for each font id) */
245
246 Edge baseEdge; /* dummy edge from base to root */
247
248 Node *trieRoot; /* Subr match trie root */
249 Node *trieParent; /* parent node used during trie walk */
250 NodeLink *trieQueue; /* node link queue */
251
252 dnaDCL(Subr, subrs); /* Subr list (all) */
253 dnaDCL(Subr *, tmp); /* Temporary subr list */
254 SubrList globalSubrs; /* List of global subrs */
255 dnaDCL(SubrList, localSubrs); /* List of local subr lists */
256 dnaDCL(CallLists, charsCallLists); /* List of subr calls in charstrings */
257 CallList calls; /* Temporary subr call accumulator */
258 dnaDCL(Subr *, members); /* Temporary social group member accumulator */
259 dnaDCL(Subr *, leaders); /* Social group leaders */
260 dnaDCL(char, cstrs); /* Charstring data accumulator */
261
262 short singleton; /* Single font in font set */
263 short offSize; /* Subr INDEX offset size */
264 short subrStackOvl; /* Subr stack overflow */
265
266 subr_CSData gsubrs; /* Global subrs */
267 short nFonts; /* Font count */
268 subr_Font *fonts; /* Font list */
269
270 unsigned char opLenCache[256]; /* Cached values of t2oplen. If 0, the second byte in the charstring indicates the length */
271 dnaDCL(Subr *, subrHash); /* Subr hash table */
272 #define SUBR_PREFIX_MAP_SIZE ((1 << (2 * 8)) / 8)
273 #define SUBR_PREFIX_MAP_INDEX(b1, b2) ((((unsigned)(b1)) << 5) | ((b2) >> 3))
274 #define SUBR_PREFIX_MAP_BIT(b2) (1 << ((b2)&7))
275 #define TEST_SUBR_PREFIX_MAP(ctx, str) ((ctx)->subrPrefixMap[SUBR_PREFIX_MAP_INDEX(str[0], str[1])] & SUBR_PREFIX_MAP_BIT(str[1]))
276 #define SET_SUBR_PREFIX_MAP(ctx, str) ((ctx)->subrPrefixMap[SUBR_PREFIX_MAP_INDEX(str[0], str[1])] |= SUBR_PREFIX_MAP_BIT(str[1]))
277 unsigned char subrPrefixMap[SUBR_PREFIX_MAP_SIZE]; /* bit table where a bit is set when its corresponding subr 2-byte prefix selected */
278 dnaDCL(uint32_t, subrLenMap); /* boolean table where a value is set when any subr with the corresponding length is selected */
279 dnaDCL(uint32_t, prefixLen); /* Prefix byte length for each byte in a charstring */
280 unsigned maxSubrLen; /* Maximum subr length */
281 unsigned minSubrLen; /* Minimum subr length */
282
283 unsigned long maxNumSubrs; /* Maximum number of subroutines (0 means default MAX_NUM_SUBRS) */
284
285 cfwCtx g; /* Package context */
286 };
287
288 #define CALL_OP_SIZE 1 /* Size of call(g)subr (bytes) */
289
290 /* xxx This copy of the module context make this module non-reentrant. It is
291 required because the ANSI qsort() function doesn't allow a client to pass
292 anything except array elements to the comparison routine. When I have time I
293 will write one that does. */
294 static subrCtx ctx;
295
296 #if TC_DEBUG
297 static long dbnodeid(subrCtx h, Node *node);
298 static void dbop(int length, unsigned char *cstr);
299 static void dbsubr(subrCtx h, unsigned iSubr, int c, unsigned offset);
300 static void dbnode(subrCtx h, Node *node);
301 static void dbcstr(subrCtx h, unsigned length, unsigned char *cstr);
302 static void dbcstrs(subrCtx h,
303 unsigned char *cstr, unsigned char *end, int index);
304 static void dbgroups(subrCtx h);
305
306 #endif /* TC_DEBUG */
307
308 /* --------------------------- Type 2 charstring functions --------------------------- */
309
310 /* Return operator length from opcode */
311 static int t2oplen(unsigned char *cstr) {
312 switch (cstr[0]) {
313 default:
314 return 1;
315
316 case tx_escape:
317 case 247:
318 case 248:
319 case 249:
320 case 250:
321 case 251:
322 case 252:
323 case 253:
324 case 254:
325 return 2;
326
327 case t2_shortint:
328 return 3;
329
330 case t2_separator:
331 return 4;
332
333 case 255:
334 return 5;
335
336 case t2_hintmask:
337 case t2_cntrmask:
338 return cstr[1];
339 }
340 }
341
342 /* Copy and edit cstr by removing length bytes from mask operators. Return
343 advanced destination buffer pointer */
344 static unsigned char *t2cstrcpy(unsigned char *pdst, unsigned char *psrc,
345 unsigned length) {
346 int left;
347 unsigned char *pend = psrc + length;
348
349 while (psrc < pend) {
350 switch (*psrc) {
351 case t2_hintmask:
352 case t2_cntrmask: /* Mask ops; remove length byte */
353 *pdst++ = *psrc++;
354 left = *psrc++ - 2;
355 while (left--) {
356 *pdst++ = *psrc++;
357 }
358 length--;
359 break;
360
361 case 255: /* 5-byte number */
362 *pdst++ = *psrc++;
363 *pdst++ = *psrc++;
364 /* Fall through */
365
366 case t2_shortint: /* 3-byte number */
367 *pdst++ = *psrc++;
368 /* Fall through */
369
370 case tx_escape: /* 2-byte number/esc operator */
371 case 247:
372 case 248:
373 case 249:
374 case 250:
375 case 251:
376 case 252:
377 case 253:
378 case 254:
379 *pdst++ = *psrc++;
380 /* Fall through */
381
382 default: /* 1-byte number/operator */
383 *pdst++ = *psrc++;
384 break;
385 }
386 }
387
388 return pdst;
389 }
390
391 /* --------------------------- Object Management --------------------------- */
392
393 /* Return new memory block based object */
394 static void *newObject(subrCtx h, MemInfo *info, long size, long count) {
395 MemBlk *pblk = info->head;
396 if (pblk == NULL || pblk->iNext == count) {
397 /* Re/allocate new block */
398 MemBlk *_new;
399 if (info->free != NULL) {
400 /* Remove block from free list */
401 _new = info->free;
402 info->free = _new->nextBlk;
403 } else {
404 /* Allocate new block from heap */
405 _new = (MemBlk *)MEM_NEW(h->g, sizeof(MemBlk));
406 _new->array = (char *)MEM_NEW(h->g, size * count);
407 }
408 _new->nextBlk = pblk;
409 _new->iNext = 0;
410 info->head = pblk = _new;
411 }
412 /* Return next object */
413 return &pblk->array[pblk->iNext++ * size];
414 }
415
416 /* Copy objects to free list */
417 static void reuseObjects(cfwCtx g, MemInfo *info) {
418 MemBlk *pblk;
419 MemBlk *next;
420 for (pblk = info->head; pblk != NULL; pblk = next) {
421 next = pblk->nextBlk;
422 pblk->nextBlk = info->free;
423 pblk->iNext = 0;
424 info->free = pblk;
425 }
426 info->head = NULL;
427 }
428
429 /* Free objects and memory blocks */
430 static void freeObjects(cfwCtx g, MemInfo *info) {
431 MemBlk *pblk;
432 MemBlk *next;
433 for (pblk = info->free; pblk != NULL; pblk = next) {
434 next = pblk->nextBlk;
435 MEM_FREE(g, pblk->array);
436 MEM_FREE(g, pblk);
437 }
438 info->free = NULL;
439 }
440
441 /* Create and initialize new CDAWG node */
442 static Node *newNode(subrCtx h, long length, unsigned id) {
443 Node *node = (Node *)newObject(h, &h->nodeBlks, sizeof(Node), NODES_PER_BLK);
444 node->edgeTable = NULL;
445 node->edgeCount = 0;
446 node->edgeTableSize = 0;
447 node->misc = length;
448 node->paths = 0;
449 node->id = (unsigned short)id;
450 node->flags = 0;
451 return node;
452 }
453
454 /* Create and initialize new subr link */
455 static Link *newLink(subrCtx h, Subr *subr, unsigned offset, Link *next) {
456 Link *link = (Link *)newObject(h, &h->linkBlks, sizeof(Link), LINKS_PER_BLK);
457 link->subr = subr;
458 link->next = next;
459 link->offset = (uint32_t)offset;
460 return link;
461 }
462
463 /* Create and initialize new trie node */
464 static Node *newTrieNode(subrCtx h, long depth) {
465 Node *node = (Node *)newObject(h, &h->trieNodeBlks, sizeof(Node), TRIE_NODES_PER_BLK);
466 node->edgeTable = NULL;
467 node->edgeCount = 0;
468 node->edgeTableSize = 0;
469 node->suffix = NULL; /* suffix link */
470 node->misc = -1; /* subr index */
471 node->paths = (unsigned short)depth; /* debug only */
472 node->id = 0;
473 node->flags = 0;
474 return node;
475 }
476
477 /* Create and initialize new node link */
478 static NodeLink *newNodeLink(subrCtx h, Node *node, NodeLink *next) {
479 NodeLink *link = (NodeLink *)newObject(h, &h->nodeLinkBlks, sizeof(NodeLink), NODE_LINKS_PER_BLK);
480 link->node = node;
481 link->next = next;
482 return link;
483 }
484
485 /* --------------------------- Call Lists -------------------------- */
486
487 static void initCallLists(subrCtx h, CallLists *lists, long cnt)
488 {
489 long i;
490 dnaSET_CNT(*lists, cnt);
491 for (i = 0; i < cnt; i++) {
492 dnaINIT(h->g->ctx.dnaSafe, lists->array[i], 0, 1);
493 }
494 }
495
496 static void freeCallLists(subrCtx h, CallLists *lists)
497 {
498 long i;
499 for (i = 0; i < lists->cnt; i++) {
500 dnaFREE(lists->array[i]);
501 }
502 dnaFREE(*lists);
503 }
504
505 /* --------------------------- Context Management -------------------------- */
506
507 /* Initialize module */
508 void cfwSubrNew(cfwCtx g) {
509 subrCtx h = (subrCtx)MEM_NEW(g, sizeof(struct subrCtx_));
510
511 h->nodeBlks.head = h->nodeBlks.free = NULL;
512 h->linkBlks.head = h->linkBlks.free = NULL;
513 h->trieNodeBlks.head = h->trieNodeBlks.free = NULL;
514 h->nodeLinkBlks.head = h->nodeLinkBlks.free = NULL;
515
516 h->root = NULL;
517 h->base = NULL;
518
519 h->trieRoot = NULL;
520 h->trieQueue = NULL;
521 h->maxNumSubrs = 0;
522
523 /* xxx tune these parameters */
524 dnaINIT(g->ctx.dnaSafe, h->subrs, 500, 1000);
525 dnaINIT(g->ctx.dnaSafe, h->tmp, 500, 1000);
526 dnaINIT(g->ctx.dnaSafe, h->globalSubrs, 500, 1000);
527 dnaINIT(g->ctx.dnaSafe, h->localSubrs, 1, 1);
528 dnaINIT(g->ctx.dnaSafe, h->charsCallLists, 1, 1);
529 dnaINIT(g->ctx.dnaSafe, h->calls, 10, 10);
530 dnaINIT(g->ctx.dnaSafe, h->members, 40, 40);
531 dnaINIT(g->ctx.dnaSafe, h->leaders, 100, 200);
532 dnaINIT(g->ctx.dnaSafe, h->cstrs, 5000, 2000);
533 dnaINIT(g->ctx.dnaSafe, h->sinks, 1, 1);
534 dnaINIT(g->ctx.dnaSafe, h->subrHash, 0, 1);
535 dnaINIT(g->ctx.dnaSafe, h->prefixLen, 10, 10);
536 dnaINIT(g->ctx.dnaSafe, h->subrLenMap, 0, 1);
537
538 h->offSize = 2;
539
540 h->gsubrs.nStrings = 0;
541 h->gsubrs.offset = NULL;
542
543 ctx = h; /* xxx temporary */
544
545 /* Link contexts */
546 h->g = g;
547 g->ctx.subr = h;
548 }
549
550 static void freeEdges(subrCtx h, MemInfo *info);
551
552 /* Free charstring data */
553 static void csFreeData(cfwCtx g, subr_CSData *data) {
554 if (data->nStrings != 0) {
555 MEM_FREE(g, data->offset);
556 MEM_FREE(g, data->data);
557 data->nStrings = 0;
558 }
559 }
560
561 /* Prepare module for reuse */
562 void cfwSubrReuse(cfwCtx g) {
563 subrCtx h = g->ctx.subr;
564
565 freeEdges(h, &h->nodeBlks);
566 freeEdges(h, &h->trieNodeBlks);
567 dnaSET_CNT(h->sinks, 0);
568 dnaSET_CNT(h->subrHash, 0);
569
570 reuseObjects(g, &h->nodeBlks);
571 reuseObjects(g, &h->linkBlks);
572 reuseObjects(g, &h->trieNodeBlks);
573 reuseObjects(g, &h->nodeLinkBlks);
574
575 csFreeData(g, &h->gsubrs);
576
577 h->root = NULL;
578 h->offSize = 2;
579 }
580
581 /* Free resources */
582 void cfwSubrFree(cfwCtx g) {
583 subrCtx h = g->ctx.subr;
584 long i;
585
586 if (h == NULL)
587 return;
588
589 freeEdges(h, &h->nodeBlks);
590 freeEdges(h, &h->trieNodeBlks);
591
592 freeObjects(g, &h->nodeBlks);
593 freeObjects(g, &h->linkBlks);
594 freeObjects(g, &h->trieNodeBlks);
595 freeObjects(g, &h->nodeLinkBlks);
596
597 for (i = 0; i < h->subrs.cnt; i++)
598 dnaFREE(h->subrs.array[i].callList);
599 dnaFREE(h->subrs);
600 dnaFREE(h->tmp);
601 dnaFREE(h->globalSubrs);
602 for (i = 0; i < h->localSubrs.cnt; i++)
603 dnaFREE(h->localSubrs.array[i]);
604 dnaFREE(h->localSubrs);
605 dnaFREE(h->calls);
606 dnaFREE(h->members);
607 dnaFREE(h->leaders);
608 dnaFREE(h->cstrs);
609 dnaFREE(h->sinks);
610 dnaFREE(h->subrHash);
611 dnaFREE(h->prefixLen);
612 dnaFREE(h->subrLenMap);
613 for (i = 0; i < h->charsCallLists.cnt; i++)
614 freeCallLists(h, &h->charsCallLists.array[i]);
615 dnaFREE(h->charsCallLists);
616
617 MEM_FREE(g, h);
618 }
619
620 /* --------------------------- Edge Table -------------------------- */
621
622 /* Allocate the initial edge table for a given node */
623 static void newEdgeTable(cfwCtx g, Node *node, unsigned size) {
624 unsigned long byteSize = sizeof(Edge) * size;
625 node->edgeTableSize = size;
626 node->edgeCount = 0;
627 node->edgeTable = (Edge *)MEM_NEW(g, byteSize);
628 memset(node->edgeTable, 0, sizeof(Edge) * size);
629 }
630
631 /* Initialize new CDAWG edge */
632 static void initEdge(Edge *edge, unsigned char *label, unsigned edgeLength, Node *son) {
633 edge->label = label;
634 edge->length = edgeLength;
635 edge->son = son;
636 }
637
638 /* free edge tables allocated for all nodes */
639 static void freeEdges(subrCtx h, MemInfo *info) {
640 MemBlk *pblk = info->head;
641 while (pblk) {
642 short i;
643 Node *node;
644 for (i = 0, node = (Node *)&pblk->array[0]; i < pblk->iNext; i++, node++) {
645 if (node->edgeTable) {
646 MEM_FREE(h->g, node->edgeTable);
647 node->edgeTable = NULL;
648 }
649 }
650 pblk = pblk->nextBlk;
651 }
652 }
653
654 /* --------------------------- CDAWG Construction --------------------------- */
655 /* Compare two edge labels */
656 static int labelcmp(subrCtx h,
657 int length1, unsigned char *label1, unsigned char *label2) {
658 int cmp = *label1++ - *label2;
659 if (cmp != 0) {
660 return cmp; /* First byte differs */
661 } else {
662 int length2 = OPLEN(h, label2);
663 int length = (length1 < length2) ? length1 : length2;
664
665 label2++;
666 while (--length) {
667 cmp = *label1++ - *label2++;
668 if (cmp != 0) {
669 return cmp; /* Subsequent byte differs */
670 }
671 }
672
673 /* Equal up to shortest label */
674 return length1 - length2;
675 }
676 }
677
678 /* Calculate a hash value for a given edge; this simple formula appears good enough */
679 static unsigned hashLabel(unsigned char *label, unsigned length) {
680 unsigned long hash = *label;
681
682 hash += (hash << 5);
683 while (--length > 0) {
684 unsigned long temp = *++label;
685 hash += temp;
686 hash <<= 5;
687 hash += temp;
688 }
689 return hash;
690 }
691
692 #if EDGE_HASH_STAT
693 static unsigned long gTotalEdgeTableSize;
694 static unsigned long gTotalEdgeCount;
695 static unsigned long long gTotalEdgeLookupCount;
696 static unsigned long gTotalEdgeMissCount;
697 #endif
698
699 /* Look up the edge table as a hash table for a given edge label
700 returns a pointer to an edge entry which may be empty if not found */
701 static Edge *lookupEdgeTable(subrCtx h, Node *node, unsigned length, unsigned char *label) {
702 unsigned tableSize = node->edgeTableSize;
703 unsigned tableSizeMinus1 = tableSize - 1;
704 unsigned hashValue = (tableSize <= EDGE_TABLE_SIZE_USE_SIMPLE_HASH) ? (*label + length) : hashLabel(label, length);
705 unsigned hashIncrement = 0;
706 unsigned count = 0;
707 #if EDGE_HASH_STAT
708 gTotalEdgeLookupCount++;
709 gTotalEdgeTableSize += tableSize;
710 gTotalEdgeCount += node->edgeCount;
711 #endif
712
713 while (count < tableSize) {
714 Edge *edge = &node->edgeTable[hashValue & tableSizeMinus1]; /* (hashValue % node->edgeTableSize) */
715 if (edge->label == NULL) {
716 return edge;
717 }
718
719 if (labelcmp(h, length, label, edge->label) == 0) {
720 return edge;
721 }
722
723 /* Collided with a wrong entry. Update the hash value using the
724 quadratic probing algorithm and try again. */
725 hashValue += ++hashIncrement;
726 count++;
727 #if EDGE_HASH_STAT
728 gTotalEdgeMissCount++;
729 #endif
730 }
731
732 /* couldn't find an entry (and the table was full) */
733 return NULL;
734 }
735
736 static void doubleEdgeTable(subrCtx h, Node *node);
737
738 /* Enter a new edge into the edge table represented as a hash table */
739 static void addEdgeToHashTable(subrCtx h, Node *node, Node *son,
740 unsigned length, unsigned char *label, unsigned edgeLength) {
741 int doubleIt = 0;
742 Edge *edge;
743
744 if (node->edgeTable == NULL) {
745 /* The initial edge table starts out with only one entry */
746 newEdgeTable(h->g, node, 1);
747 edge = &node->edgeTable[0];
748 } else {
749 /* Double the hash table if the large table is almost full or no empty slot available */
750 if (node->edgeCount >= node->edgeTableSize) {
751 doubleIt = 1;
752 } else if (node->edgeTableSize >= EDGE_TABLE_SMALLEST_SPARSE_SIZE) {
753 if (node->edgeCount >= (node->edgeTableSize - (node->edgeTableSize >> 3))) {
754 /* When the hash table is >= 87.5% full, double its size */
755 doubleIt = 1;
756 }
757 }
758
759 if (doubleIt) {
760 doubleEdgeTable(h, node);
761 }
762
763 edge = lookupEdgeTable(h, node, length, label);
764 }
765 #if TC_DEBUG
766 if (!edge || edge->label) {
767 printf("addEdgeToHashTable: failed to find an empty slot\n");
768 }
769 #endif
770 initEdge(edge, label, edgeLength, son);
771 node->edgeCount++;
772 }
773
774 /* Double the size of the edge table for a given node */
775 static void doubleEdgeTable(subrCtx h, Node *node) {
776 Edge *oldTable = node->edgeTable;
777 unsigned oldTableSize = node->edgeTableSize;
778 unsigned newTableSize = node->edgeTableSize * 2;
779 unsigned newTableByteSize = sizeof(Edge) * newTableSize;
780 Edge *newTable = (Edge *)MEM_NEW(h->g, newTableByteSize);
781 Edge *edge;
782 unsigned i;
783
784 /* Replace the old hash table with a new blank hash table */
785 memset(newTable, 0, newTableByteSize);
786 node->edgeTable = newTable;
787 node->edgeTableSize = newTableSize;
788 node->edgeCount = 0;
789
790 /* Copy all edges from the old hash table to the new hash table */
791 for (i = 0, edge = oldTable; i < oldTableSize; i++, edge++) {
792 if (edge->label != NULL) {
793 addEdgeToHashTable(h, node, edge->son, OPLEN(h, edge->label), edge->label, edge->length);
794 }
795 }
796
797 MEM_FREE(h->g, oldTable);
798 }
799
800 /* Add edge to between father and son nodes */
801 static void addEdge(subrCtx h, Node *father, Node *son,
802 unsigned length, unsigned char *label, unsigned edgeLength) {
803 addEdgeToHashTable(h, father, son, length, label, edgeLength);
804 }
805
806 /* handle the special case where the base node has a virtual edge for every token to the root node */
807 #define FIND_EDGE(h, node, length, label) ((node)->misc == -1 ? &(h)->baseEdge : findEdge(h, node, length, label))
808
809 /* Find linking edge from node with label */
810 static Edge *findEdge(subrCtx h,
811 Node *node, unsigned length, unsigned char *label) {
812 Edge *edge = lookupEdgeTable(h, node, length, label);
813 if (edge == NULL || edge->label) {
814 return edge;
815 } else {
816 return NULL;
817 }
818 }
819
820 /* Copy the edge table from the source node to the destination node */
821 static void copyEdgeTable(subrCtx h, Node *destNode, Node *srcNode) {
822 newEdgeTable(h->g, destNode, srcNode->edgeTableSize);
823 destNode->edgeCount = srcNode->edgeCount;
824 memcpy(destNode->edgeTable, srcNode->edgeTable, sizeof(Edge) * srcNode->edgeTableSize);
825 }
826
827 typedef void (*walkEdgeTableProc)(subrCtx h, Edge *edge, long param1, long param2);
828
829 static void walkEdgeTable(subrCtx h, Node *node, walkEdgeTableProc proc, long param1, long param2) {
830 unsigned size = node->edgeTableSize;
831 Edge *edge = node->edgeTable;
832 unsigned i;
833
834 if (!edge) {
835 return;
836 }
837
838 for (i = 0; i < size; i++, edge++) {
839 if (edge->label) {
840 proc(h, edge, param1, param2);
841 }
842 }
843 }
844
845 /* Determine whether the state with the canonical reference pair (s,(k,p)) is the end point */
846 static int CheckEndPoint(subrCtx h, Node *s, unsigned char *k, unsigned char *p,
847 unsigned length, unsigned id) {
848 /* c == *p */
849 if (s->misc == -1) {
850 /* base node is always an end point */
851 return 1;
852 }
853
854 if (k < p) {
855 /* implicit node */
856 /* let s (k',p')-> s' be the text[k]-edge from s;
857 return (c == text[k' + p - k]) */
858 Edge *edge = FIND_EDGE(h, s, OPLEN(h, k), k);
859 return labelcmp(h, length, p, edge->label + (p - k)) == 0;
860 } else {
861 /* explicit node */
862 /* is there 'c'-edge from s? */
863 return (FIND_EDGE(h, s, length, p) != NULL);
864 }
865 }
866
867 /* Return either an explicit/implicit node corresponding to the canonical reference pair (s,(k,p)) */
868 static Node *Extension(subrCtx h, Node *s, unsigned char *k, unsigned char *p) {
869 if (k >= p) {
870 /* explicit node */
871 return s;
872 } else {
873 /* implicit node */
874 /* let s (k',p')-> s' be the text[k]-edge from s */
875 return FIND_EDGE(h, s, OPLEN(h, k), k)->son;
876 }
877 }
878
879 /* Redirect the edge (s,(k,p)) to r */
880 static void Redirect(subrCtx h, Node *s, unsigned char *k, unsigned char *p, Node *r) {
881 /* let s (k',p')-> s' be the text[k]-edge from s */
882 Edge *edge = FIND_EDGE(h, s, OPLEN(h, k), k);
883
884 /* replace this edge by edge s (k',k'+p-k)-> r;
885 note that the edge has the same label so it can be replaced in place
886 within the edge tree */
887 edge->son = r;
888 edge->length = (unsigned int)(p - k);
889 }
890
891 #define CANONIZE(h, s, k, p, s_ret, k_ret) \
892 { \
893 if ((k) < (p)) { \
894 Canonize(h, s, k, p, s_ret, k_ret); /* implicit node */ \
895 } else { \
896 *(s_ret) = (s); \
897 *(k_ret) = (k); \
898 } /* explicit node */ \
899 }
900
901 /* Canonize (normalize) a reference pair (s,(k,p)) of an implicit node and return it as (s',k') */
902 static void Canonize(subrCtx h, Node *s, unsigned char *k, unsigned char *p, Node **s_ret, unsigned char **k_ret) {
903 Edge *edge;
904 int length = OPLEN(h, k);
905
906 if (s->misc == -1) {
907 /* base node has a one-length edge to root for every token */
908 s = h->root;
909 k += length;
910 if (k >= p) {
911 /* explicit node */
912 *s_ret = s;
913 *k_ret = k;
914 return;
915 }
916 length = OPLEN(h, k);
917 }
918 /* (s,(k,p)) is an implicit node */
919 /* find the text[k]-edge s (k',p') -> s' from s */
920 edge = FIND_EDGE(h, s, length, k);
921 while (edge->length <= (unsigned)(p - k)) {
922 k += edge->length;
923 s = edge->son;
924 if (k < p) {
925 /* find the text[k]-edge s (k',p')-> s' from s */
926 edge = FIND_EDGE(h, s, OPLEN(h, k), k);
927 }
928 }
929 *s_ret = s;
930 *k_ret = k;
931 }
932
933 /* Split an edge at the canonical reference point (s,(k,p)) and returns the split point as an explicit node */
934 static Node *SplitEdge(subrCtx h, Node *s, unsigned char *k, unsigned char *p, int id) {
935 Node *r;
936 unsigned char *newLabel;
937 /* let s (k',p') -> s' be the text[k]-edge from s */
938 Edge *edge = FIND_EDGE(h, s, OPLEN(h, k), k);
939 /* replace this edge by edges s (k',k'+p-k) -> r and r (k'+p-k+1,p') -> s',
940 where r is a new node */
941 r = newNode(h, s->misc + (long)(p - k), (edge->son->id != id) ? NODE_GLOBAL : id);
942 newLabel = edge->label + (p - k);
943 addEdge(h, r, edge->son, OPLEN(h, newLabel), newLabel, (unsigned int)((edge->label + edge->length) - newLabel));
944 edge->length = (unsigned int)(p - k);
945 edge->son = r;
946
947 return r;
948 }
949
950 /* If a node at the canonical reference point (s,(k,p)) is a non-solid, explicit node,
951 then duplicate the node and return a new active point */
952 static void SeparateNode(subrCtx h, Node *s, unsigned char *k, unsigned char *p,
953 Node **s_ret, unsigned char **k_ret, int id) {
954 Node *ss;
955 Node *rr;
956 unsigned char *kk;
957 unsigned char *pminus1;
958 Node *cs;
959 unsigned char *ck;
960 CANONIZE(h, s, k, p, &ss, &kk);
961 if (kk < p) {
962 /* implicit node */
963 *s_ret = ss;
964 *k_ret = kk;
965 return;
966 }
967 /* (s',(k',p)) is an explicit node */
968 if (s->misc == -1 /*base node*/) {
969 *s_ret = ss;
970 *k_ret = kk;
971 return;
972 }
973 if (ss->misc == s->misc + (p - k)) {
974 /* solid edge */
975 Node *suffix;
976 for (suffix = ss; suffix != NULL; suffix = suffix->suffix) {
977 if (suffix->id != id) {
978 suffix->id = NODE_GLOBAL;
979 }
980 }
981 *s_ret = ss;
982 *k_ret = kk;
983 return;
984 }
985
986 /* non-solid case */
987 /* create a new node r' as a duplication of s' */
988 rr = newNode(h, s->misc + (long)(p - k), (ss->id != id) ? NODE_GLOBAL : id);
989 /* Copy the edge table */
990 copyEdgeTable(h, rr, ss);
991 /* set up suffix link */
992 rr->suffix = ss->suffix;
993 ss->suffix = rr;
994
995 do {
996 /* replace the text[k]-edge from s to s' by edge s (k,p)-> r' */
997 Node *son;
998 Edge *edge = FIND_EDGE(h, s, OPLEN(h, k), k);
999 ss = edge->son;
1000 edge->son = rr;
1001 edge->label = k;
1002 edge->length = (unsigned int)(p - k);
1003
1004 /* calculate a canonical reference for Suf(s) with edge (k,p-1);
1005 (s, k) := Canonize(Suf(s),(k,p-1))
1006 that is, we need to back up from (k,p) by one token. Since we can't
1007 parse a charstring backwards, we parse from k forward to find p-1.
1008 this code may need optimization since it is O(n^2) */
1009 pminus1 = k;
1010 for (;;) {
1011 int length = OPLEN(h, pminus1);
1012 if (pminus1 + length >= p) {
1013 break;
1014 }
1015 pminus1 += length;
1016 }
1017 CANONIZE(h, s->suffix, k, pminus1, &s, &k);
1018 if (k < p) {
1019 /* implicit node */
1020 son = FIND_EDGE(h, s, OPLEN(h, k), k)->son;
1021 } else {
1022 son = s;
1023 }
1024 if (son->id != id) {
1025 son->id = NODE_GLOBAL;
1026 }
1027
1028 /* do {..} until (s',k') != Canonize(s,(k,p)) */
1029 CANONIZE(h, s, k, p, &cs, &ck);
1030 } while ((ss == cs) && (kk == ck));
1031
1032 /* return (r',p) */
1033 *s_ret = rr;
1034 *k_ret = p;
1035 }
1036
1037 /* Append font's charstring data to CDAWG. This construction algorithm closely
1038 follows the one presented in "On-Line Construction of Compact Directed Acyclic
1039 Word Graphs" although this one also adds code the identify
1040 nodes in the CDAWG with a particular font or as global nodes if they
1041 terminate charstrings that appear in multiple fonts.
1042 A notational difference is that an edge is represented as (k,p) where
1043 p points at the next token after the end of the string as opposed to
1044 p pointing at the last token in the string.
1045 */
1046 static void addFont(subrCtx h, subr_Font *font, unsigned iFont, int multiFonts) {
1047 unsigned char *p;
1048 unsigned char *pend;
1049 unsigned char *pfd;
1050 unsigned id;
1051 Node *s; /* active point */
1052 unsigned char *k; /* beginning of the current reference point */
1053 Node *e; /* extension node */
1054 Node *r, *oldr;
1055
1056 if (font->chars.nStrings == 0) {
1057 return; /* Synthetic font */
1058 }
1059 #if DB_TEST_STRING
1060 p = gTestString;
1061 pend = p + strlen((char *)p);
1062 multiFonts = 1;
1063 #else
1064 p = (unsigned char *)font->chars.data;
1065 pend = p + font->chars.offset[font->chars.nStrings - 1];
1066 #endif
1067
1068 if (font->flags & SUBR_FONT_CID) {
1069 pfd = font->fdIndex;
1070 id = iFont + *pfd++;
1071 } else {
1072 pfd = NULL; /* Suppress optimizer warning */
1073 id = iFont;
1074 }
1075
1076 if (h->base == NULL) {
1077 h->base = newNode(h, -1, id);
1078 h->base->misc = -1; /* length from source */
1079 h->base->suffix = NULL;
1080 }
1081
1082 if (h->root == NULL) {
1083 h->root = newNode(h, 0, id);
1084 h->root->suffix = h->base;
1085 }
1086
1087 /* set up base edge */
1088 h->baseEdge.son = h->root;
1089
1090 s = h->root;
1091 k = p;
1092
1093 #if DB_FONT
1094 dbcstrs(h, p, pend, iFont);
1095 #endif
1096
1097 /* Extend path (token by token) */
1098 while (p < pend) {
1099 int length = OPLEN(h, p);
1100
1101 r = NULL;
1102 oldr = NULL;
1103 e = NULL;
1104
1105 /* Update at (s,(k,p)) which is the canonical reference pair for the active point. */
1106 while (!CheckEndPoint(h, s, k, p, length, id)) {
1107 Node *sink;
1108 if (k < p) {
1109 /* implicit */
1110 Node *newe = Extension(h, s, k, p);
1111 if (newe == e) {
1112 Redirect(h, s, k, p, r);
1113 CANONIZE(h, s->suffix, k, p, &s, &k);
1114 continue;
1115 } else {
1116 e = newe;
1117 r = SplitEdge(h, s, k, p, id);
1118 }
1119 } else {
1120 /* explicit */
1121 r = s;
1122 }
1123
1124 /* create p new edge r (p,infinity) -> sink */
1125 /* we furnish one sink for each font */
1126 if (id >= (unsigned)h->sinks.cnt) {
1127 long cnt = h->sinks.cnt;
1128 dnaSET_CNT(h->sinks, id + 1);
1129 while (cnt < h->sinks.cnt) {
1130 h->sinks.array[cnt++] = NULL;
1131 }
1132 }
1133 sink = h->sinks.array[id];
1134 if (!sink) {
1135 sink = h->sinks.array[id] = newNode(h, 0, id);
1136 sink->flags |= NODE_COUNTED;
1137 sink->paths = 1;
1138 }
1139
1140 addEdge(h, r, sink, length, p, (unsigned int)(pend - p));
1141
1142 if (oldr != NULL) {
1143 oldr->suffix = r;
1144 }
1145 oldr = r;
1146 CANONIZE(h, s->suffix, k, p, &s, &k);
1147 }
1148
1149 if (oldr != NULL) {
1150 oldr->suffix = s;
1151 }
1152
1153 /* Even though we reached an end point, we need to follow the suffix
1154 link in order to mark shared nodes as NODE_GLOBAL in the case of
1155 multi-fonts. */
1156 if (multiFonts) {
1157 Node *ss = s;
1158 unsigned char *kk = k;
1159 unsigned char *pp = p + length;
1160 while (ss->misc != -1) {
1161 CANONIZE(h, ss->suffix, kk, pp, &ss, &kk);
1162 if (kk >= pp) {
1163 /* explicit */
1164 if (ss->id != id) {
1165 ss->id = NODE_GLOBAL;
1166 }
1167 }
1168 }
1169 }
1170
1171 SeparateNode(h, s, k, p + length, &s, &k, id);
1172
1173 #if DB_TEST_STRING
1174 if (p[0] == SEPARATOR) {
1175 id++;
1176 }
1177 #else
1178 if (font->flags & SUBR_FONT_CID &&
1179 p[0] == SEPARATOR &&
1180 p + length < pend) {
1181 /* Change id for CID font on charstring boundary */
1182 id = iFont + *pfd++;
1183 }
1184 #endif
1185
1186 p += length;
1187 }
1188 }
1189
1190 /* ----------------------- Candidate Subr Selection ------------------------ */
1191
1192 static long countPathsForNode(subrCtx h, Node *node);
1193
1194 /* Count paths running through each node */
1195 static unsigned countPaths(subrCtx h, Edge *edge) {
1196 Node *node;
1197
1198 if (edge == NULL) {
1199 return 0;
1200 }
1201 node = edge->son;
1202
1203 if (!(node->flags & NODE_COUNTED)) {
1204 /* Count descendant paths */
1205 long count = node->paths;
1206
1207 /* Recursively descend complex node */
1208 count += countPathsForNode(h, node);
1209
1210 /* Update node */
1211 node->paths = (unsigned short)((count > USHRT_MAX) ? USHRT_MAX : count);
1212 node->flags |= NODE_COUNTED;
1213 }
1214 return node->paths;
1215 }
1216
1217 static long countPathsForNode(subrCtx h, Node *node) {
1218 long count = 0;
1219 unsigned i, tableSize;
1220 Edge *edge = node->edgeTable;
1221
1222 tableSize = node->edgeTableSize;
1223 for (i = 0; i < tableSize; i++, edge++) {
1224 if (edge->label) {
1225 count += countPaths(h, edge);
1226 }
1227 }
1228 return count;
1229 }
1230
1231 /* Test candidate subr and save if it meets candidate requirements.
1232
1233 This function selects all candidate subrs using a subr number size of 1 and
1234 Subr INDEX offset element size of 2. The actual sizes will be used later
1235 when accepting or rejecting subrs from the initial candidate list. The
1236 savings available are as follows:
1237
1238 call = 1 callsubr op size
1239 num = 1 subr number size
1240 off = 2 subr INDEX offset element size
1241 ret = 1 return op size
1242
1243 Regular Tail
1244 length count saved count saved
1245 ------ ----- ----- ----- -----
1246 3 7 1 6 1
1247 4 4 1 4 2
1248 5 3 1 3 2
1249 6 3 3 3 4
1250 7 3 5 2 1
1251 8 2 1 2 2
1252 9- 2 >0 2 >0
1253 */
1254 static void saveSubr(subrCtx h, unsigned char *edgeEnd, Node *node,
1255 int maskcnt, int tail, long subrLen) {
1256 Subr *subr;
1257 unsigned count = node->paths;
1258
1259 node->flags |= NODE_FAIL; /* Assume test will fail and mark node */
1260 /* Treat CFF2 subrs the same as CFF1 tail subrs, i.e., no return op required at end */
1261 if (h->g->flags & CFW_WRITE_CFF2)
1262 tail = 1;
1263
1264 /* Test for candidacy */
1265 switch (subrLen - maskcnt) {
1266 case 1:
1267 case 2:
1268 return;
1269
1270 case 3:
1271 if (count < (7 - (unsigned)tail)) {
1272 return;
1273 }
1274 break;
1275
1276 case 4:
1277 if (count < 4) {
1278 return;
1279 }
1280 break;
1281
1282 case 5:
1283 case 6:
1284 if (count < 3) {
1285 return;
1286 }
1287 break;
1288
1289 case 7:
1290 if (count < (3 - (unsigned)tail)) {
1291 return;
1292 }
1293 break;
1294
1295 default:
1296 if (count < 2) {
1297 return;
1298 }
1299 break;
1300 }
1301
1302 node->flags &= ~NODE_FAIL; /* Test passed; removed mark */
1303
1304 /* Select as candidate subr */
1305 subr = dnaNEXT(h->subrs);
1306 subr->node = node;
1307 subr->sups = NULL;
1308 subr->infs = NULL;
1309 subr->next = NULL;
1310 subr->output = NULL;
1311 subr->cstr = edgeEnd - subrLen;
1312 subr->length = (uint32_t)subrLen;
1313 subr->count = (uint32_t)count;
1314 subr->deltalen = 0;
1315 subr->numsize = 1;
1316 subr->maskcnt = (short)maskcnt;
1317 subr->flags = 0;
1318 dnaINIT(h->g->ctx.dnaSafe, subr->callList, 0, 1);
1319 #if DB_CALLS
1320 subr->calls = 0;
1321 #endif
1322
1323 /* Update subr node */
1324 node->misc = h->subrs.cnt - 1;
1325 node->flags |= NODE_SUBR;
1326 if (tail) {
1327 node->flags |= NODE_TAIL;
1328 }
1329 }
1330
1331 static void findCandSubrs(subrCtx h, Edge *edge, int maskcnt);
1332
1333 static void findCandSubrsProc(subrCtx h, Edge *edge, long maskcnt, long misc) {
1334 if ((long)(misc + edge->length) == edge->son->misc) {
1335 /* Descend solid edge */
1336 findCandSubrs(h, edge, maskcnt);
1337 }
1338 }
1339
1340 /* Find candidate subrs in CDAWG */
1341 static void findCandSubrs(subrCtx h, Edge *edge, int maskcnt) {
1342 long misc;
1343 Node *node;
1344 unsigned char *edgeEnd;
1345
1346 for (;;) {
1347 unsigned char *pstr;
1348 node = edge->son;
1349
1350 if (node->flags & NODE_TESTED || node->paths == 1) {
1351 return;
1352 }
1353 node->flags |= NODE_TESTED;
1354
1355 /* scan the edge string for masks and endchar */
1356 pstr = edge->label;
1357 edgeEnd = pstr + edge->length;
1358 while (pstr < edgeEnd) {
1359 int oplen = OPLEN(h, pstr);
1360 if (*pstr == tx_endchar) {
1361 if (node->paths > 1) {
1362 pstr += oplen;
1363 saveSubr(h, pstr, node, maskcnt, 1, (long)(node->misc - ((edge->label + edge->length) - pstr)));
1364 }
1365 return;
1366 } else if (*pstr == t2_hintmask ||
1367 *pstr == t2_cntrmask) {
1368 maskcnt++;
1369 }
1370 pstr += oplen;
1371 }
1372
1373 misc = node->misc;
1374 if (node->edgeCount > 1) {
1375 goto complex;
1376 } else if (node->paths > node->edgeTable[0].son->paths) {
1377 saveSubr(h, edgeEnd, node, maskcnt, 0, misc);
1378 }
1379 }
1380
1381 complex:
1382 saveSubr(h, edgeEnd, node, maskcnt, 0, misc);
1383 walkEdgeTable(h, node, findCandSubrsProc, maskcnt, misc);
1384 }
1385
1386 /* Calculate byte savings for this subr. See candSubr() for details */
1387 static int subrSaved(subrCtx h, Subr *subr) {
1388 int length = subr->length - subr->maskcnt;
1389 return subr->count * (length - CALL_OP_SIZE - subr->numsize) -
1390 (h->offSize + length + ((subr->node->flags & NODE_TAIL) == 0));
1391 }
1392
1393 /* ----------------------- Subr match trie ----------------------- */
1394
1395 /* Set up suffix links */
1396 static void setTrieSuffixProc(subrCtx h, Edge *edge, long param1, long param2) {
1397 Node *node = edge->son;
1398 Node *state;
1399 Edge *suffixEdge = NULL;
1400
1401 /* Append this node to the queue for later processing of its children */
1402 h->trieQueue->next = newNodeLink(h, node, NULL);
1403 h->trieQueue = h->trieQueue->next;
1404 if (h->trieParent == h->trieRoot)
1405 return;
1406
1407 state = h->trieParent->suffix;
1408
1409 for (;;) {
1410 if (!state)
1411 state = h->trieRoot;
1412 suffixEdge = findEdge(h, state, edge->length, edge->label);
1413 if (suffixEdge) {
1414 node->suffix = suffixEdge->son;
1415 break;
1416 }
1417 if (state == h->trieRoot)
1418 return;
1419
1420 state = state->suffix;
1421 }
1422
1423 /* Chain the output subr of this node to the output subr of the suffix node */
1424 if (node->misc >= 0) {
1425 Subr *subr = &h->subrs.array[node->misc];
1426
1427 if (node->suffix->misc >= 0)
1428 subr->output = &h->subrs.array[node->suffix->misc];
1429 } else
1430 node->misc = node->suffix->misc;
1431 }
1432
1433 /* Update each suffix link with the pointer to the next node */
1434 static void setTrieNextProc(subrCtx h, Edge *edge, long param1, long param2) {
1435 Node *node = edge->son;
1436 Node *suffix;
1437 Edge *suffixEdge = NULL;
1438
1439 /* Append this node to the queue for later processing of its children */
1440 h->trieQueue->next = newNodeLink(h, node, NULL);
1441 h->trieQueue = h->trieQueue->next;
1442 if (h->trieParent == h->trieRoot)
1443 return;
1444
1445 suffix = h->trieParent->suffix;
1446 if (!suffix)
1447 suffix = h->trieRoot;
1448 suffixEdge = findEdge(h, suffix, edge->length, edge->label);
1449 if (!suffixEdge) {
1450 if (suffix == h->trieRoot)
1451 return;
1452
1453 suffixEdge = findEdge(h, suffix, edge->length, edge->label);
1454 if (suffixEdge)
1455 node->suffix = suffixEdge->son;
1456 else
1457 node->suffix = NULL;
1458 }
1459 }
1460
1461 /* Build a subr match trie using Aho-Corasick algorithm */
1462 static void buildSubrMatchTrie(subrCtx h) {
1463 long i;
1464 NodeLink *link;
1465 Node *node;
1466
1467 h->trieRoot = newTrieNode(h, 0);
1468
1469 /* Add all subrs to the trie */
1470 for (i = 0; i < h->subrs.cnt; i++) {
1471 Subr *subr = &h->subrs.array[i];
1472 unsigned char *pstr, *pend;
1473 long oplen;
1474 long depth;
1475
1476 node = h->trieRoot;
1477 pstr = subr->cstr;
1478 pend = pstr + subr->length;
1479 for (depth = 1; pstr < pend; pstr += oplen, depth++) {
1480 Edge *edge;
1481
1482 oplen = OPLEN(h, pstr);
1483 edge = findEdge(h, node, oplen, pstr);
1484 if (edge) {
1485 node = edge->son;
1486 } else {
1487 Node *son = newTrieNode(h, depth);
1488 addEdge(h, node, son, oplen, pstr, oplen);
1489 node = son;
1490 }
1491 }
1492 node->misc = (long)(subr - h->subrs.array); /* store output subr index in the trie node */
1493 }
1494
1495 /* Set up suffix links */
1496 reuseObjects(h->g, &h->nodeLinkBlks);
1497 link = h->trieQueue = newNodeLink(h, h->trieRoot, NULL);
1498 for (; link; link = link->next) {
1499 h->trieParent = link->node;
1500 walkEdgeTable(h, link->node, setTrieSuffixProc, 0, 0);
1501 }
1502
1503 /* Update each suffix link with the pointer to the next node */
1504 reuseObjects(h->g, &h->nodeLinkBlks);
1505 link = h->trieQueue = newNodeLink(h, h->trieRoot, NULL);
1506 for (; link; link = link->next) {
1507 h->trieParent = link->node;
1508 walkEdgeTable(h, link->node, setTrieNextProc, 0, 0);
1509 }
1510 }
1511
1512 /* List up all subrs matching the given string against the subr match trie */
1513 static void listUpSubrMatches(subrCtx h, unsigned char *pstart, long length, int buildPhase, int selfMatch,
1514 unsigned id, short subrDepth, CallList *callList) {
1515 Node *node = h->trieRoot;
1516 unsigned char *pstr, *pend = pstart + length;
1517 int oplen;
1518 Edge *edge;
1519
1520 for (pstr = pstart; pstr < pend; pstr += oplen) {
1521 oplen = OPLEN(h, pstr);
1522
1523 for (;;) {
1524 edge = findEdge(h, node, oplen, pstr);
1525 if (edge) {
1526 node = edge->son;
1527 break;
1528 } else {
1529 node = node->suffix;
1530 if (!node)
1531 break;
1532 }
1533 }
1534
1535 if (!node) {
1536 node = h->trieRoot;
1537 continue;
1538 }
1539 if (node->misc >= 0) {
1540 Subr *subr = &h->subrs.array[node->misc];
1541
1542 for (; subr; subr = subr->output) {
1543 long offset;
1544
1545 if (buildPhase) {
1546 if ((subr->flags & SUBR_MARKED) != SUBR_SELECT)
1547 continue;
1548 if (subr->node->id != NODE_GLOBAL && subr->node->id != id)
1549 continue;
1550 }
1551
1552 offset = (long)(pstr - pstart + oplen - subr->length);
1553 if ((offset >= 0) && (offset + subr->length <= length)) {
1554 Call *c;
1555
1556 if (!selfMatch && offset == 0 && offset + subr->length == length)
1557 continue;
1558 /* respect the max subr stack depth observed by checkSubrStackOvl */
1559 if ((subrDepth >= 0) && (subrDepth <= subr->misc))
1560 continue;
1561
1562 c = dnaNEXT(*callList);
1563 c->subr = subr;
1564 c->subr->order = callList->cnt;
1565 c->offset = (uint32_t)offset;
1566 }
1567 }
1568 }
1569 }
1570 }
1571
1572 /* Compare subr calls by length (longest first) then by offset (smallest first) */
1573 static int CTL_CDECL cmpSubrLengths(const void *first, const void *second) {
1574 Call *a = (Call *)first;
1575 Call *b = (Call *)second;
1576 if (a->subr->length != b->subr->length)
1577 return (int)b->subr->length - (int)a->subr->length;
1578 else if (a->offset != b->offset)
1579 return (int)a->offset - (int)b->offset;
1580 else
1581 return (int)b->subr->order - (int)a->subr->order;
1582 }
1583
1584 /* Scan charstring and build call list of subrs */
1585 /* The same function is called with buildPhase = 0 for setting subr count during
1586 overlap handling phase and called with buildPhase = 1 for building call list.
1587
1588 The code looks for subrs with the longest length first, then try to cover
1589 a given charstring. During the following iterations shorter subrs are tried
1590 to fill gaps (if we apply the same logic to each gap recursively, we can get
1591 the most optimal result). Lists are created and are tried to fill their gaps in
1592 the order of the subr size. All subrs including those inferior to others are tried.
1593 If a subr can't fit in any gap in lists, then a new list is created for it.
1594 At the end, the most space saving list of subrs is selected as the call list.
1595 The call list may not contain the longest inferior subr for the given charstring
1596 as the result.
1597
1598 TODO: If this approach works well the overlap handling phase should be rewritten
1599 using the same logic in order to resolve the logic disparity between the two phases.
1600 */
1601
1602 static void buildCallList(subrCtx h, int buildPhase, unsigned length, unsigned char *pstart,
1603 int selfMatch, unsigned id, short subrDepth,
1604 CallList *callList) {
1605 // unsigned char *pend = pstart + length;
1606 unsigned i, j;
1607 CallList candList;
1608
1609 /* List up all matching subrs */
1610 dnaINIT(h->g->ctx.dnaSafe, candList, 100, 100);
1611 listUpSubrMatches(h, pstart, length, buildPhase, selfMatch, id, subrDepth, &candList);
1612 qsort(candList.array, candList.cnt, sizeof(Call), cmpSubrLengths);
1613
1614 /* Try to fill lists with longest subrs first */
1615 dnaSET_CNT(*callList, 0);
1616 for (i = 0; i < (unsigned)candList.cnt; i++) {
1617 Call *c = &candList.array[i];
1618 Subr *subr = c->subr;
1619 unsigned subrEndOffset = c->offset + subr->length;
1620
1621 /* Try to fill a gap in calls array */
1622 unsigned cnt;
1623 int overlap = 0;
1624 cnt = callList->cnt;
1625
1626 for (j = 0; j < cnt; j++) {
1627 Call *call = &callList->array[j];
1628 if (subrEndOffset <= call->offset) {
1629 /* found gap before at j'th call */
1630 break;
1631 }
1632 if (subrEndOffset > call->offset && c->offset < (unsigned)call->offset + call->subr->length) {
1633 /* overlap */
1634 overlap = 1;
1635 break;
1636 }
1637 if (c->offset < call->offset + (unsigned)call->subr->length && subrEndOffset > call->offset) {
1638 /* overlap */
1639 overlap = 1;
1640 break;
1641 }
1642 }
1643
1644 /* insert the subr into this gap */
1645 if (!overlap) {
1646 dnaSET_CNT(*callList, cnt + 1);
1647 memmove(&callList->array[j + 1], &callList->array[j], sizeof(Call) * (cnt - j));
1648 callList->array[j] = *c;
1649 }
1650 }
1651
1652 dnaFREE(candList);
1653
1654 for (i = 0; i < (unsigned)callList->cnt; i++) {
1655 Call *call = &callList->array[i];
1656 call->subr->count++;
1657 #if DB_ASSOC
1658 dbsubr(h, call->subr - h->subrs.array, 'i', call->offset);
1659 #endif
1660 }
1661
1662 #if DB_INFS
1663 if (buildPhase && callList->cnt != 0) {
1664 int j;
1665 for (j = 0; j < callList->cnt; j++) {
1666 Call *call = &callList->array[j];
1667 if (call->subr != NULL) {
1668 dbsubr(h, call->subr - h->subrs.array, 'y', call->offset);
1669 }
1670 }
1671 }
1672 #endif
1673 }
1674
1675 /* Reset subr count */
1676 static void resetSubrCount(subrCtx h, unsigned id) {
1677 long i;
1678 Subr *subr;
1679
1680 for (i = 0; i < h->subrs.cnt; i++) {
1681 subr = &h->subrs.array[i];
1682 if (subr->node->id == id || id == NODE_ANY)
1683 subr->count = 0;
1684 }
1685 }
1686
1687 /* Renamed from setSubrActCount, since set call count are
1688 * more like estimate at this point */
1689 static void setSubrTentativeCount(subrCtx h) {
1690 long i, j;
1691 Subr *subr;
1692 Link *infs;
1693
1694 #if DB_ASSOC
1695 printf("--- assoc subrs with subrs\n");
1696 #endif
1697
1698 resetSubrCount(h, NODE_ANY);
1699
1700 /* Make call list for each subr and set actual call count in each */
1701 for (i = 0; i < h->subrs.cnt; i++) {
1702 #if DB_ASSOC || DB_RELNS
1703 dbsubr(h, i, '-', 0);
1704 #endif
1705 subr = &h->subrs.array[i];
1706 buildCallList(h, 0, subr->length, subr->cstr, 0, 0, -1, &h->calls);
1707
1708 infs = NULL;
1709 for (j = h->calls.cnt - 1; j >= 0; j--) {
1710 Call *call = &h->calls.array[j];
1711 Subr *inf = call->subr;
1712
1713 /* Add superior subr to inferior subrs */
1714 inf->sups = newLink(h, subr, call->offset, inf->sups);
1715
1716 /* Add inferior subr to list */
1717 infs = newLink(h, inf, call->offset, infs);
1718 }
1719 subr->infs = infs;
1720 }
1721 }
1722
1723 static void sortInfSubrs(subrCtx h) {
1724 long i;
1725 Subr *subr;
1726
1727 /* Cache the subrSaved value for use during sort below */
1728 for (i = 0; i < h->subrs.cnt; i++) {
1729 subr = &h->subrs.array[i];
1730 subr->misc = (short)subrSaved(h, subr);
1731 }
1732
1733 /* Reorder inferiors by savings (largest first) */
1734 for (i = 0; i < h->subrs.cnt; i++) {
1735 Link *head; /* Head if inferior list */
1736 subr = &h->subrs.array[i];
1737
1738 /* Sort list in-place */
1739 for (head = subr->infs; head != NULL; head = head->next) {
1740 Link *try_ = head->next;
1741 if (try_ == NULL) {
1742 break; /* End of list */
1743 } else {
1744 Link *best = NULL;
1745 int max = head->subr->misc;
1746
1747 /* Find best inferior subr in remainder of list */
1748 do {
1749 int saved = try_->subr->misc;
1750 if (saved > max) {
1751 best = try_;
1752 max = saved;
1753 }
1754 try_ = try_->next;
1755 } while (try_ != NULL);
1756
1757 if (best != NULL) {
1758 /* Swap "head" and "best" nodes */
1759 Call tmp;
1760 tmp.subr = head->subr;
1761 tmp.offset = head->offset;
1762
1763 head->subr = best->subr;
1764 head->offset = best->offset;
1765
1766 best->subr = tmp.subr;
1767 best->offset = tmp.offset;
1768 }
1769 }
1770 }
1771 }
1772 }
1773
1774 /* Select candidate subrs */
1775 static void selectCandSubrs(subrCtx h) {
1776 /* Count paths */
1777 (void)countPathsForNode(h, h->root);
1778
1779 /* Find candidate subrs */
1780 h->subrs.cnt = 0;
1781 walkEdgeTable(h, h->root, findCandSubrsProc, 0, 0);
1782
1783 #if 0
1784 printf("--- xfindSubrRelns\n");
1785 h->tmp.cnt = 0;
1786 for (edge = &h->root->edge; edge != NULL; edge = edge->next) {
1787 if (OPLEN(h, edge->label) == edge->son->misc) {
1788 xfindSubrRelns(h, edge, 0);
1789 }
1790 }
1791 #endif
1792 }
1793
1794 /* ----------------------- Associate Subrs With Font ----------------------- */
1795
1796 /* Associate subrs with a font in the FontSet */
1797 static void assocSubrs(subrCtx h) {
1798 int i;
1799
1800 #if DB_ASSOC
1801 printf("--- assoc chars with subrs\n");
1802 #endif
1803
1804 for (i = 0; i < h->nFonts; i++) {
1805 long j;
1806 long offset;
1807 subr_Font *font = &h->fonts[i];
1808
1809 offset = 0;
1810 for (j = 0; j < font->chars.nStrings; j++) {
1811 long nextoff = font->chars.offset[j];
1812
1813 #if DB_ASSOC
1814 printf("[%3d:%4ld] ", i, j);
1815 dbcstr(h, nextoff - offset,
1816 (unsigned char *)&FONT_CHARS_DATA[offset]);
1817 printf("\n");
1818 #endif
1819
1820 buildCallList(h, 0, nextoff - offset, (unsigned char *)&FONT_CHARS_DATA[offset], 1, 0, -1, &h->calls);
1821
1822 offset = nextoff;
1823 }
1824 }
1825 }
1826
1827 /* --------------------------- Select Final Subrs -------------------------- */
1828
1829 #if 0
1830 static void prints(Subr *subr) {
1831 int c = (subr->node->id == NODE_GLOBAL) ? 'g' : 'l';
1832 if (subr->flags & SUBR_MEMBER) {
1833 c -= 'a' - 'A';
1834 }
1835 printf("%d%c", subrSaved(ctx, subr), c);
1836 if (subr->flags & SUBR_SELECT) {
1837 printf("s ");
1838 } else if (subr->flags & SUBR_REJECT) {
1839 printf("r ");
1840 } else {
1841 printf(" ");
1842 }
1843 }
1844
1845 #endif
1846
1847 #if 0 /*Recursive*/
1848 /* Add social group member subr */
1849 static void addMember(subrCtx h, Subr *subr) {
1850 Link *link;
1851
1852 *dnaNEXT(h->members) = subr;
1853 subr->flags |= SUBR_MEMBER;
1854
1855 for (link = subr->sups; link != NULL; link = link->next) {
1856 if (!(link->subr->flags & SUBR_MEMBER)) {
1857 addMember(h, link->subr);
1858 }
1859 }
1860
1861 for (link = subr->infs; link != NULL; link = link->next) {
1862 if (!(link->subr->flags & SUBR_MEMBER)) {
1863 addMember(h, link->subr);
1864 }
1865 }
1866 }
1867
1868 #else
1869 /* Add social group member subr */
1870
1871 #define LISTSIZE 4000
1872 static void addMember(subrCtx h, Subr *subr) {
1873 Link *link;
1874 Subr **list; /*Used to reverse the order of the Subr's*/
1875 int listlength;
1876 int i;
1877
1878 dnaDCL(Subr *, subrStack);
1879 dnaINIT(h->g->ctx.dnaSafe, subrStack, 4000, 4000);
1880
1881 list = (Subr **)malloc(LISTSIZE * sizeof(Subr *));
1882 listlength = 0;
1883
1884 *dnaNEXT(subrStack) = subr;
1885 while (subrStack.cnt > 0) {
1886 --subrStack.cnt;
1887 subr = *dnaINDEX(subrStack, subrStack.cnt);
1888 if (!(subr->flags & SUBR_MEMBER)) {
1889 /* Add member and mark subr to avoid reselection */
1890 *dnaNEXT(h->members) = subr;
1891 subr->flags |= SUBR_MEMBER;
1892 subr->order = h->members.cnt;
1893
1894 for (link = subr->sups; link != NULL; link = link->next) {
1895 /* Add superior member to temporary list*/
1896 list[listlength++] = link->subr;
1897 if (listlength >= LISTSIZE) {
1898 #if TC_DEBUG
1899 fprintf(stderr, "Typecomp Error: List Overflow\n");
1900 #endif
1901 free(list);
1902 dnaFREE(subrStack);
1903 return;
1904 }
1905 }
1906 for (link = subr->infs; link != NULL; link = link->next) {
1907 /* Add inferior member to temporary list*/
1908 list[listlength++] = link->subr;
1909 if (listlength >= LISTSIZE) {
1910 #if TC_DEBUG
1911 fprintf(stderr, "Typecomp Error: List Overflow\n");
1912 #endif
1913 free(list);
1914 dnaFREE(subrStack);
1915 return;
1916 }
1917 }
1918 /* Transfer from temporary list into stack*/
1919 for (i = listlength - 1; i >= 0; i--) {
1920 *dnaNEXT(subrStack) = list[i];
1921 }
1922 listlength = 0;
1923 }
1924 }
1925 free(list);
1926 dnaFREE(subrStack);
1927 }
1928
1929 #endif
1930
1931 /* Compare social group member subrs for a global subr set. Global subrs are
1932 sorted before local subrs, largest saving first. */
1933 static int CTL_CDECL cmpGlobalSetSubrs(const void *first, const void *second) {
1934 Subr *a = *(Subr **)first;
1935 Subr *b = *(Subr **)second;
1936 if (a->node->id == NODE_GLOBAL) {
1937 if (b->node->id == NODE_GLOBAL) {
1938 /* global global */
1939 int asaved = subrSaved(ctx, a);
1940 int bsaved = subrSaved(ctx, b);
1941 if (asaved > bsaved) {
1942 return -1;
1943 } else if (a->order > b->order) {
1944 /* Preserve original order */
1945 return 1;
1946 } else if (a->order < b->order) {
1947 return -1;
1948 } else if (asaved < bsaved) {
1949 return 1;
1950 } else {
1951 return 0;
1952 }
1953 } else {
1954 /* global local */
1955 return -1;
1956 }
1957 } else if (b->node->id == NODE_GLOBAL) {
1958 /* local global */
1959 return 1;
1960 } else if (a->order > b->order) {
1961 /* Preserve original order */
1962 return 1;
1963 } else if (a->order < b->order) {
1964 return -1;
1965 } else {
1966 /* local local */
1967 return 0;
1968 }
1969 }
1970
1971 /* Compare social group member subrs for a local subr set. Selected global
1972 subrs are sorted before local subrs which are sorted before rejected global
1973 subrs. Selected global and unselected local subrs are further sorted by
1974 largest savings first. */
1975 static int CTL_CDECL cmpLocalSetSubrs(const void *first, const void *second) {
1976 Subr *a = *(Subr **)first;
1977 Subr *b = *(Subr **)second;
1978 switch ((a->flags & SUBR_MARKED) << 2 | (b->flags & SUBR_MARKED)) {
1979 /* a-subr b-subr */
1980 case 0: /* local local */
1981 case 5: /* global.select global.select */
1982 {
1983 int asaved = subrSaved(ctx, a);
1984 int bsaved = subrSaved(ctx, b);
1985 if (asaved > bsaved) {
1986 return -1;
1987 } else if (asaved < bsaved) {
1988 return 1;
1989 } else if (a->order > b->order) {
1990 /* Preserve original order */
1991 return 1;
1992 } else if (a->order < b->order) {
1993 return -1;
1994 } else {
1995 return 0;
1996 }
1997 }
1998
1999 case 1: /* local global.select */
2000 case 8: /* global.reject local */
2001 case 9: /* global.reject global.select */
2002 return 1;
2003
2004 case 2: /* local global.reject */
2005 case 4: /* global.select local */
2006 case 6: /* global.select global.reject */
2007 return -1;
2008
2009 case 10: /* global.reject global.reject */
2010 return 0;
2011
2012 default:
2013 #if TC_DEBUG
2014 printf("cmpLocalSetSubrs() can't happen!\n");
2015 #endif
2016 break;
2017 }
2018 return 0; /* Suppress compiler warning */
2019 }
2020
2021 /* Find social groups for global or local subr set. */
2022 static void findGroups(subrCtx h, unsigned id) {
2023 long i;
2024 int(CTL_CDECL * cmpSubrs)(const void *first, const void *second) =
2025 (id == NODE_GLOBAL) ? cmpGlobalSetSubrs : cmpLocalSetSubrs;
2026
2027 h->leaders.cnt = 0;
2028 for (i = 0; i < h->tmp.cnt; i++) {
2029 long j;
2030 Subr *subr = h->tmp.array[i];
2031
2032 if (subr->flags & SUBR_MEMBER) {
2033 continue;
2034 }
2035
2036 /* Add new social group */
2037 h->members.cnt = 0;
2038 addMember(h, subr);
2039
2040 /* Sort members by largest saving first */
2041 qsort(h->members.array, h->members.cnt, sizeof(Subr *), cmpSubrs);
2042
2043 #if 0
2044 for (j = 0; j < h->members.cnt; j++) {
2045 prints(h->members.array[j]);
2046 }
2047 printf("|\n");
2048 #endif
2049
2050 /* Link members */
2051 for (j = 0; j < h->members.cnt - 1; j++) {
2052 h->members.array[j]->next = h->members.array[j + 1];
2053 }
2054 h->members.array[j]->next = NULL;
2055
2056 /* Add leader */
2057 *dnaNEXT(h->leaders) = h->members.array[0];
2058 }
2059 }
2060
2061 /* Update superior lengths */
2062 static void updateSups(subrCtx h, Subr *subr, int deltalen, unsigned id) {
2063 Link *link;
2064
2065 for (link = subr->sups; link != NULL; link = link->next) {
2066 Subr *sup = link->subr;
2067 if (!(sup->flags & SUBR_MARKED) && sup->node->id == id) {
2068 #if DB_SELECT
2069 printf("updateSups([%d]->[%d],%d) deltalen=%d\n",
2070 subr - h->subrs.array, sup - h->subrs.array,
2071 deltalen, sup->deltalen + deltalen);
2072 #endif
2073 updateSups(h, sup, deltalen, id);
2074 sup->deltalen += (short)deltalen;
2075 }
2076 }
2077 }
2078
2079 /* Select subr */
2080 static void selectSubr(subrCtx h, Subr *subr) {
2081 uint32_t count = subr->count;
2082 int length = subr->length - subr->maskcnt + subr->deltalen;
2083 int saved = count * (length - CALL_OP_SIZE - subr->numsize) -
2084 (h->offSize + length + ((subr->node->flags & NODE_TAIL) == 0));
2085
2086 #if DB_SELECT
2087 printf("selectSubr([%d]) count=%d, length=%d, saved=%d\n",
2088 subr - h->subrs.array, count, length, saved);
2089 #endif
2090
2091 if (saved > 0) {
2092 /* Select subr */
2093 unsigned id = subr->node->id;
2094 int deltalen = subr->numsize + CALL_OP_SIZE - subr->length -
2095 subr->deltalen;
2096
2097 subr->flags &= ~SUBR_REJECT;
2098 subr->flags |= SUBR_SELECT;
2099
2100 #if DB_SELECT
2101 printf("select=%d, deltalen=%d\n",
2102 saved, deltalen);
2103 #endif
2104 updateSups(h, subr, deltalen, id);
2105 } else {
2106 /* Reject subr */
2107 subr->flags &= ~SUBR_SELECT;
2108 subr->flags |= SUBR_REJECT;
2109 #if DB_SELECT
2110 printf("reject\n");
2111 #endif
2112 }
2113 }
2114
2115 /* Select global subrs from social group. */
2116 static void selectGlobalSubrs(subrCtx h, Subr *subr, unsigned id) {
2117 for (; subr != NULL; subr = subr->next) {
2118 if (subr->node->id != NODE_GLOBAL) {
2119 return; /* Quit on first local subr */
2120 } else if (!(subr->flags & SUBR_MARKED)) {
2121 selectSubr(h, subr);
2122 }
2123 }
2124 }
2125
2126 /* Select local subrs from social group. */
2127 static void selectLocalSubrs(subrCtx h, Subr *subr, unsigned id) {
2128 for (; subr != NULL; subr = subr->next) {
2129 if (subr->node->id == NODE_GLOBAL) {
2130 if (subr->flags & SUBR_SELECT) {
2131 updateSups(h, subr, subr->numsize + CALL_OP_SIZE - subr->length, id);
2132 } else {
2133 return; /* Quit on first rejected global subr */
2134 }
2135 } else if (!(subr->flags & SUBR_MARKED)) {
2136 selectSubr(h, subr);
2137 }
2138 }
2139 }
2140
2141 /* Compare subr calls by selection/saved/length/frequency */
2142 static int CTL_CDECL cmpSubrFitness(const void *first, const void *second) {
2143 Subr *a = *(Subr **)first;
2144 Subr *b = *(Subr **)second;
2145 int aselect = (a->flags & SUBR_SELECT) != 0;
2146 int bselect = (b->flags & SUBR_SELECT) != 0;
2147 if (aselect == bselect) {
2148 int asaved = subrSaved(ctx, a);
2149 int bsaved = subrSaved(ctx, b);
2150 if (asaved > bsaved) {
2151 /* Compare savings */
2152 return -1;
2153 } else if (asaved < bsaved) {
2154 return 1;
2155 } else if (a->length > b->length) {
2156 /* Compare length */
2157 return -1;
2158 } else if (a->length < b->length) {
2159 return 1;
2160 } else if (a->count > b->count) {
2161 /* Compare count */
2162 return -1;
2163 } else if (a->count < b->count) {
2164 return 1;
2165 } else if (a->order > b->order) {
2166 /* Preserve original order */
2167 return 1;
2168 } else if (a->order < b->order) {
2169 return -1;
2170 } else {
2171 return 0;
2172 }
2173 } else if (!aselect && bselect) {
2174 return 1;
2175 } else {
2176 return -1;
2177 }
2178 }
2179
2180 /* Check for subr stack depth overflow */
2181 static void checkSubrStackOvl(subrCtx h, Subr *subr, int depth, unsigned id) {
2182 Link *sup;
2183
2184 if ((subr->flags & SUBR_MARKED) == SUBR_SELECT) {
2185 /* No need to check this subr if it is local and has been checked with this or deeper stack */
2186 if (depth <= subr->misc && (subr->node->id != NODE_GLOBAL || id == NODE_GLOBAL)) {
2187 return;
2188 }
2189
2190 if (depth > subr->misc)
2191 subr->misc = (short)depth;
2192 depth++; /* Bump depth for selected subrs only */
2193
2194 if (depth >= TX_MAX_CALL_STACK) {
2195 /* Stack depth exceeded; reject subr */
2196 subr->flags &= ~SUBR_SELECT;
2197 subr->flags |= SUBR_REJECT;
2198 depth--;
2199 h->subrStackOvl = 1;
2200 subr->misc = (short)depth;
2201 }
2202 }
2203
2204 /* Recursively ascend superior subrs */
2205 for (sup = subr->sups; sup != NULL; sup = sup->next) {
2206 checkSubrStackOvl(h, sup->subr, depth, id);
2207 }
2208 }
2209
2210 /* Select subr set to be saved in font. Subr list is in the temporary array */
2211 static void selectFinalSubrSet(subrCtx h, unsigned id) {
2212 long i;
2213 void (*selectSubrs)(subrCtx h, Subr * subr, unsigned id) =
2214 (id == NODE_GLOBAL) ? selectGlobalSubrs : selectLocalSubrs;
2215 long nSelected = 0; /* Suppress optimizer warning */
2216 int multiplier = h->singleton ? 2 : 1; /* Range multiplier */
2217 int pass = 0;
2218 long limit = h->maxNumSubrs;
2219
2220 if (limit == 0) {
2221 limit = MAX_NUM_SUBRS;
2222 }
2223 limit = limit * multiplier;
2224
2225 findGroups(h, id); /* Find social groups (related subrs) */
2226
2227 reselect:
2228 for (i = 0; i < h->leaders.cnt; i++) {
2229 Subr *subr = h->leaders.array[i];
2230
2231 #if DB_SELECT
2232 printf("--- group[%ld]\n", i);
2233 #endif
2234 if (subr->next == NULL) {
2235 /* Select/reject hermit subr */
2236 subr->flags |= (subrSaved(h, subr) > 0) ? SUBR_SELECT : SUBR_REJECT;
2237 #if DB_SELECT
2238 printf("%s=%d\n", (subr->flags & SUBR_SELECT) ? "select" : "reject",
2239 subrSaved(h, subr));
2240 #endif
2241 } else {
2242 selectSubrs(h, subr, id);
2243 }
2244 }
2245
2246 #if DB_GROUPS
2247 dbgroups(h);
2248 #endif
2249
2250 /* Reset misc field for storing subr call depth by checkSubrStackOvl */
2251 for (i = 0; i < h->tmp.cnt; i++) {
2252 h->tmp.array[i]->misc = -1;
2253 h->tmp.array[i]->order = i;
2254 }
2255
2256 /* Remove membership so globals may be selected in other local sets and
2257 check for and handle subr call stack overflow */
2258 for (i = 0; i < h->leaders.cnt; i++) {
2259 Subr *subr;
2260 for (subr = h->leaders.array[i]; subr != NULL; subr = subr->next) {
2261 if (subr->infs == NULL) {
2262 checkSubrStackOvl(h, subr, 0, id);
2263 }
2264 subr->flags &= ~SUBR_MEMBER;
2265 }
2266 }
2267
2268 /* Sort selected subrs by fitness */
2269 qsort(h->tmp.array, h->tmp.cnt, sizeof(Subr *), cmpSubrFitness);
2270
2271 /* Find last selected subr */
2272 for (i = h->tmp.cnt - 1; i >= 0; i--) {
2273 if ((h->tmp.array[i]->flags & SUBR_MARKED) == SUBR_SELECT) {
2274 nSelected = i + 1;
2275 break;
2276 }
2277 }
2278
2279 if (nSelected >= limit) {
2280 for (i = limit; i < nSelected; i++) {
2281 h->tmp.array[i]->flags &= ~SUBR_SELECT;
2282 h->tmp.array[i]->flags |= SUBR_REJECT;
2283 }
2284 h->tmp.cnt = nSelected = limit;
2285 } else {
2286 h->tmp.cnt = nSelected;
2287 }
2288
2289 if (++pass == 2) {
2290 return;
2291 } else if (nSelected < 215 * multiplier) {
2292 /* All subrs fit into first 1-byte range. Since we don't have to
2293 increase the index number size, for any subroutines, their
2294 calculated savings won't change on a second pass. */
2295 h->tmp.cnt = nSelected;
2296 return;
2297 }
2298
2299 /* Removed subr marking before reselection */
2300 /* We are going to have to increase the index number size for some
2301 subroutines. This means that their savings will get smaller, and we may
2302 need to reject them. */
2303 for (i = 0; i < h->tmp.cnt; i++) {
2304 h->tmp.array[i]->flags &= ~SUBR_MARKED;
2305 }
2306
2307 /* Assign new subr number sizes */
2308 for (i = h->tmp.cnt - 1; i >= 2263 * multiplier; i--) {
2309 h->tmp.array[i]->numsize = 3;
2310 }
2311 for (; i >= 215 * multiplier; i--) {
2312 h->tmp.array[i]->numsize = 2;
2313 }
2314 for (; i >= 0; i--) {
2315 h->tmp.array[i]->numsize = 1;
2316 }
2317
2318 goto reselect;
2319 }
2320
2321 /* --------------------------- Add Subrs to INDEX -------------------------- */
2322
2323 /* Subroutinize charstring */
2324 static unsigned char *subrizeCstr(subrCtx h,
2325 unsigned char *pdst, unsigned char *psrc,
2326 unsigned length,
2327 CallList *callList) {
2328 int i;
2329 long offset;
2330
2331 /* Insert calls in charstring */
2332 offset = 0;
2333 for (i = 0; i < callList->cnt; i++) {
2334 Call *call = &callList->array[i];
2335 Subr *subr = call->subr;
2336
2337 if (subr != NULL) {
2338 /* Copy bytes preceding subr */
2339 pdst = t2cstrcpy(pdst, psrc, call->offset - offset);
2340
2341 /* Add subr call */
2342 pdst += cfwEncInt(subr->subrnum, pdst);
2343 *pdst++ = (subr->node->id == NODE_GLOBAL) ? t2_callgsubr : tx_callsubr;
2344
2345 #if DB_CALLS
2346 subr->calls++;
2347 #endif
2348
2349 /* Skip over subr's bytes */
2350 psrc += call->offset - offset + subr->length;
2351 offset = call->offset + subr->length;
2352 }
2353 }
2354
2355 /* Copy remainder of charstring and return destination buffer pointer */
2356 return t2cstrcpy(pdst, psrc, length - offset);
2357 }
2358
2359 /* Build subroutine call lists of charstrings */
2360 static void buildCharsCallLists(subrCtx h, subr_CSData *chars, unsigned id) {
2361 long i;
2362 long offset;
2363 CallLists *callLists;
2364
2365 callLists = dnaMAX(h->charsCallLists, id);
2366 dnaINIT(h->g->ctx.dnaSafe, *callLists, 500, 500);
2367 initCallLists(h, callLists, chars->nStrings);
2368
2369 offset = 0;
2370 h->cstrs.cnt = 0;
2371 for (i = 0; i < chars->nStrings; i++) {
2372 unsigned char *psrc = (unsigned char *)&chars->data[offset];
2373 long nextoff = chars->offset[i];
2374 unsigned length = nextoff - offset - 4 /* t2_separator */;
2375 long iStart = h->cstrs.cnt;
2376
2377 #if DB_CHARS
2378 printf("[%3ld] = ", i);
2379 dbcstr(h, length, psrc);
2380 printf("\n");
2381 #endif
2382
2383 /* Build subr call list */
2384 buildCallList(h, 1, length, psrc, 1, id, -1, &callLists->array[i]);
2385
2386 offset = nextoff;
2387 }
2388 }
2389
2390 /* Subroutinize charstrings from call lists */
2391 static void subrizeChars(subrCtx h, subr_CSData *chars, unsigned iFont) {
2392 long i;
2393 long offset;
2394
2395 #if DB_CHARS
2396 printf("--- subrized chars (chars marked with =)\n");
2397 #endif
2398
2399 offset = 0;
2400 h->cstrs.cnt = 0;
2401 for (i = 0; i < chars->nStrings; i++) {
2402 unsigned char *pdst;
2403 unsigned char *psrc = (unsigned char *)&chars->data[offset];
2404 long nextoff = chars->offset[i];
2405 unsigned length = nextoff - offset - 4 /* t2_separator */;
2406 long iStart = h->cstrs.cnt;
2407
2408 /* Initially allocate space for entire charstring */
2409 pdst = (unsigned char *)dnaEXTEND(h->cstrs, (long)length);
2410
2411 /* Subroutinize charstring from call lists */
2412 pdst = subrizeCstr(h, pdst, psrc, length, &h->charsCallLists.array[iFont].array[i]);
2413
2414 /* Adjust initial length estimate and save offset */
2415 h->cstrs.cnt = (long)(iStart + pdst - (unsigned char *)&h->cstrs.array[iStart]);
2416 chars->offset[i] = h->cstrs.cnt;
2417 offset = nextoff;
2418 }
2419
2420 /* Copy charstring data without loosing original data pointer */
2421 chars->refcopy = chars->data;
2422 chars->data = (char *)MEM_NEW(h->g, h->cstrs.cnt);
2423 memcpy(chars->data, h->cstrs.array, h->cstrs.cnt);
2424
2425 #if DB_CALLS
2426 printf("--- actual subr calls\n");
2427 for (i = 0; i < subrList->cnt; i++) {
2428 Subr *subr = subrList->array[i];
2429 printf("[%3d]=%2d (%2d)", subr - h->subrs.array,
2430 subr->calls, subr->count);
2431 if (subr->calls != subr->count) {
2432 printf("*\n");
2433 } else {
2434 printf("\n");
2435 }
2436 }
2437 #endif
2438 }
2439
2440 /* Create biased reordering for either global or local subrs for a singleton
2441 font using combined subr INDEXes. The global subrs are selected from even
2442 temporary array indexes and local subrs are chosen from odd indexes */
2443 static void reorderCombined(subrCtx h, int local) {
2444 long bias;
2445 long count; /* Element in reorder array */
2446 long i; /* Reorder array index */
2447 long j; /* Temporary array index */
2448 SubrList *subrList = local? &h->localSubrs.array[0]: &h->globalSubrs;
2449
2450 if (local) {
2451 /* Reorder local (odd) indexes */
2452 count = h->tmp.cnt / 2;
2453 j = (h->tmp.cnt & ~1) + 1;
2454 } else {
2455 /* Reorder global (even) indexes */
2456 count = (h->tmp.cnt + 1) / 2;
2457 j = (h->tmp.cnt + 1) & ~1;
2458 }
2459
2460 /* Set the reorder array size */
2461 dnaSET_CNT(*subrList, count);
2462
2463 i = count - 1;
2464 if (count < 1240) {
2465 /* Bias-107 reordering */
2466 for (; i >= 0; i--) {
2467 subrList->array[i + 0] = h->tmp.array[j -= 2];
2468 }
2469 bias = 107;
2470 } else if (count < 33900) {
2471 /* Bias-1131 reordering */
2472 for (; i >= 1239; i--) {
2473 subrList->array[i + 0] = h->tmp.array[j -= 2];
2474 }
2475 for (; i >= 215; i--) {
2476 subrList->array[i - 215] = h->tmp.array[j -= 2];
2477 }
2478 for (; i >= 0; i--) {
2479 subrList->array[i + 1024] = h->tmp.array[j -= 2];
2480 }
2481 bias = 1131;
2482 } else {
2483 /* Bias-32768 reordering */
2484 for (; i >= 33900; i--) {
2485 subrList->array[i + 0] = h->tmp.array[j -= 2];
2486 }
2487 for (; i >= 2263; i--) {
2488 subrList->array[i - 2263] = h->tmp.array[j -= 2];
2489 }
2490 for (; i >= 1239; i--) {
2491 subrList->array[i + 31637] = h->tmp.array[j -= 2];
2492 }
2493 for (; i >= 215; i--) {
2494 subrList->array[i + 31422] = h->tmp.array[j -= 2];
2495 }
2496 for (; i >= 0; i--) {
2497 subrList->array[i + 32661] = h->tmp.array[j -= 2];
2498 }
2499 bias = 32768;
2500 }
2501
2502 /* Add biased subr numbers and mark global subrs */
2503 for (i = 0; i < count; i++) {
2504 Subr *subr = subrList->array[i];
2505 subr->subrnum = (short)(i - bias);
2506 if (!local) {
2507 subr->node->id = NODE_GLOBAL;
2508 }
2509 }
2510 }
2511
2512 /* Create biased reordering for a non-singleton font */
2513 static void reorderSubrs(subrCtx h, unsigned id) {
2514 long i;
2515 long bias;
2516 SubrList *subrList = (id == NODE_GLOBAL)? &h->globalSubrs: &h->localSubrs.array[id];
2517
2518 /* Assign reordering index */
2519 dnaSET_CNT(*subrList, h->tmp.cnt);
2520 i = h->tmp.cnt - 1;
2521 if (h->tmp.cnt < 1240) {
2522 /* Bias-107 reordering */
2523 for (; i >= 0; i--) {
2524 subrList->array[i + 0] = h->tmp.array[i];
2525 }
2526 bias = 107;
2527 } else if (h->tmp.cnt < 33900) {
2528 /* Bias-1131 reordering */
2529 for (; i >= 1239; i--) {
2530 subrList->array[i + 0] = h->tmp.array[i];
2531 }
2532 for (; i >= 215; i--) {
2533 subrList->array[i - 215] = h->tmp.array[i];
2534 }
2535 for (; i >= 0; i--) {
2536 subrList->array[i + 1024] = h->tmp.array[i];
2537 }
2538 bias = 1131;
2539 } else {
2540 /* Bias-32768 reordering */
2541 for (; i >= 33900; i--) {
2542 subrList->array[i + 0] = h->tmp.array[i];
2543 }
2544 for (; i >= 2263; i--) {
2545 subrList->array[i - 2263] = h->tmp.array[i];
2546 }
2547 for (; i >= 1239; i--) {
2548 subrList->array[i + 31637] = h->tmp.array[i];
2549 }
2550 for (; i >= 215; i--) {
2551 subrList->array[i + 31422] = h->tmp.array[i];
2552 }
2553 for (; i >= 0; i--) {
2554 subrList->array[i + 32661] = h->tmp.array[i];
2555 }
2556 bias = 32768;
2557 }
2558
2559 /* Add biased subr numbers */
2560 for (i = 0; i < subrList->cnt; i++) {
2561 subrList->array[i]->subrnum = (short)(i - bias);
2562 }
2563 }
2564
2565 /* Add reorder subrs from reorder array */
2566 static void buildSubrsCallLists(subrCtx h, unsigned id) {
2567 long i;
2568 SubrList *subrList = (id == NODE_GLOBAL)? &h->globalSubrs: &h->localSubrs.array[id];
2569
2570 if (subrList->cnt == 0) {
2571 return; /* No subrs */
2572 }
2573
2574 for (i = 0; i < subrList->cnt; i++) {
2575 Subr *subr = subrList->array[i];
2576
2577 /* Build subr call list */
2578 buildCallList(h, 1, subr->length, subr->cstr, 0, id, subr->misc, &subr->callList);
2579 }
2580 }
2581
2582 /* Replace subroutines with calls in subroutines */
2583 static void subrizeSubrs(subrCtx h, subr_CSData *subrs, unsigned id) {
2584 SubrList *subrList = (id == NODE_GLOBAL)? &h->globalSubrs: &h->localSubrs.array[id];
2585 long i;
2586
2587 #if DB_SUBRS
2588 printf("--- subrized subrs (subrs marked with -)\n");
2589 #endif
2590
2591 if (subrList->cnt == 0) {
2592 return; /* No subrs */
2593 }
2594
2595 /* Allocate subr offset array */
2596 subrs->nStrings = (unsigned short)subrList->cnt;
2597 subrs->offset = (Offset *)MEM_NEW(h->g, subrList->cnt * sizeof(Offset));
2598
2599 h->cstrs.cnt = 0;
2600
2601 for (i = 0; i < subrList->cnt; i++) {
2602 unsigned char *pdst = NULL;
2603 Subr *subr = subrList->array[i];
2604 long iStart = h->cstrs.cnt;
2605
2606 /* Initially allocate space for entire charstring + last op */
2607 pdst = (unsigned char *)dnaEXTEND(h->cstrs, subr->length + 1);
2608
2609 #if DB_SUBRS
2610 dbsubr(h, subr - h->subrs.array, '-', 0);
2611 #endif
2612
2613 /* Subroutinize charstring */
2614 pdst = subrizeCstr(h, pdst, subr->cstr, subr->length, &subr->callList);
2615
2616 /* Terminate subr */
2617 if ((!(subr->node->flags & NODE_TAIL)) && (!(h->g->flags & CFW_WRITE_CFF2))) {
2618 *pdst++ = (unsigned char)tx_return;
2619 }
2620
2621 /* Adjust initial length estimate and save offset */
2622 h->cstrs.cnt = (long)(iStart + pdst - (unsigned char *)&h->cstrs.array[iStart]);
2623 subrs->offset[i] = h->cstrs.cnt;
2624 }
2625
2626 /* Allocate and copy charstring data */
2627 subrs->data = (char *)MEM_NEW(h->g, h->cstrs.cnt);
2628 memcpy(subrs->data, h->cstrs.array, h->cstrs.cnt);
2629 }
2630
2631 /* Build call lists for FD charstrings */
2632 static void buildFDCharsCallLists(subrCtx h, subr_Font *font,
2633 unsigned iFont, unsigned iFD) {
2634 long iSrc;
2635 subr_CSData *src = &font->chars;
2636 CallLists *callLists = &h->charsCallLists.array[iFont];
2637
2638 #if DB_CHARS
2639 printf("--- subrized FD[%u] chars (chars marked with =)\n", iFD);
2640 #endif
2641
2642 for (iSrc = 0; iSrc < src->nStrings; iSrc++) {
2643 if (font->fdIndex[iSrc] == iFD) {
2644 long offset = (iSrc == 0) ? 0 : src->offset[iSrc - 1];
2645 unsigned char *psrc = (unsigned char *)&src->data[offset];
2646 unsigned length = src->offset[iSrc] - offset - 4 /* t2_separator */;
2647
2648 /* Build subr call list */
2649 buildCallList(h, 1, length, psrc, 1, iFont + iFD, -1, &callLists->array[iSrc]);
2650 }
2651 }
2652 }
2653
2654 /* Subroutinize FD charstrings */
2655 static void subrizeFDChars(subrCtx h, subr_CSData *dst, subr_Font *font,
2656 unsigned iFont, unsigned iFD) {
2657 long iSrc;
2658 unsigned iDst;
2659 subr_CSData *src = &font->chars;
2660
2661 #if DB_CHARS
2662 printf("--- subrized FD[%u] chars (chars marked with =)\n", iFD);
2663 #endif
2664
2665 /* Count chars in this this FD */
2666 dst->nStrings = 0;
2667 for (iSrc = 0; iSrc < src->nStrings; iSrc++) {
2668 if (font->fdIndex[iSrc] == iFD) {
2669 dst->nStrings++;
2670 }
2671 }
2672
2673 /* Allocate offset array */
2674 dst->offset = (Offset *)MEM_NEW(h->g, sizeof(Offset) * dst->nStrings);
2675
2676 h->cstrs.cnt = 0;
2677 iDst = 0;
2678 for (iSrc = 0; iSrc < src->nStrings; iSrc++) {
2679 if (font->fdIndex[iSrc] == iFD) {
2680 unsigned char *pdst;
2681 long offset = (iSrc == 0) ? 0 : src->offset[iSrc - 1];
2682 unsigned char *psrc = (unsigned char *)&src->data[offset];
2683 long length = src->offset[iSrc] - offset - 4 /* t2_separator */;
2684 long iStart = h->cstrs.cnt;
2685
2686 /* Initially allocate space for entire charstring */
2687 pdst = (unsigned char *)dnaEXTEND(h->cstrs, (long)length);
2688
2689 #if DB_CHARS
2690 printf("[%3ld] = ", iSrc);
2691 dbcstr(h, length, psrc);
2692 printf("\n");
2693 #endif
2694
2695 /* Subroutinize charstring */
2696 pdst = subrizeCstr(h, pdst, psrc, length, &h->charsCallLists.array[iFont].array[iSrc]);
2697
2698 /* Adjust initial length estimate and save offset */
2699 h->cstrs.cnt = (long)(iStart + pdst -
2700 (unsigned char *)&h->cstrs.array[iStart]);
2701 dst->offset[iDst++] = h->cstrs.cnt;
2702 }
2703 }
2704
2705 /* Copy charstring data */
2706 dst->data = (char *)MEM_NEW(h->g, h->cstrs.cnt);
2707 memcpy(dst->data, h->cstrs.array, h->cstrs.cnt);
2708
2709 #if DB_CALLS
2710 {
2711 int i;
2712 printf("--- actual subr calls\n");
2713 for (i = 0; i < subrList->cnt; i++) {
2714 Subr *subr = subrList->array[i];
2715 printf("[%3d]=%2d (%2d)", subr - h->subrs.array,
2716 subr->calls, subr->count);
2717 if (subr->calls != subr->count) {
2718 printf("*\n");
2719 } else {
2720 printf("\n");
2721 }
2722 }
2723 }
2724 #endif
2725 }
2726
2727 /* Reassemble cstrs for CID-keyed font */
2728 static void joinFDChars(subrCtx h, subr_Font *font) {
2729 cfwCtx g = h->g;
2730 long i;
2731 long size;
2732 long dstoff;
2733
2734 /* Determine total size of subroutinized charstring data */
2735 size = 0;
2736 for (i = 0; i < font->fdCount; i++) {
2737 subr_FDInfo *info = &font->fdInfo[i];
2738 size += info->chars.offset[info->chars.nStrings - 1];
2739 info->iChar = 0;
2740 }
2741
2742 /* Allocate new charstring data without loosing original data pointer */
2743 font->chars.refcopy = FONT_CHARS_DATA;
2744 font->chars.data = (char *)MEM_NEW(g, size);
2745
2746 dstoff = 0;
2747 for (i = 0; i < font->chars.nStrings; i++) {
2748 subr_FDInfo *info = &font->fdInfo[font->fdIndex[i]];
2749 long srcoff =
2750 (info->iChar == 0) ? 0 : info->chars.offset[info->iChar - 1];
2751 unsigned length = info->chars.offset[info->iChar++] - srcoff;
2752
2753 memmove(&font->chars.data[dstoff], &info->chars.data[srcoff], length);
2754
2755 font->chars.offset[i] = (dstoff += length);
2756 }
2757
2758 /* Free temporary chars index for each FD */
2759 for (i = 0; i < font->fdCount; i++) {
2760 subr_CSData *chars = &font->fdInfo[i].chars;
2761 MEM_FREE(g, chars->offset);
2762 MEM_FREE(g, chars->data);
2763 }
2764 }
2765
2766 /* -------------------------- Subroutinize FontSet ------------------------- */
2767
2768 /* Build subrs with specific id */
2769 static void buildSubrs(subrCtx h, unsigned id) {
2770 long i;
2771
2772 /* Build temporary array of subrs with matching id */
2773 h->tmp.cnt = 0;
2774 for (i = 0; i < h->subrs.cnt; i++) {
2775 Subr *subr = &h->subrs.array[i];
2776 if (subr->node->id == id) {
2777 *dnaNEXT(h->tmp) = subr;
2778 }
2779 }
2780
2781 #if 0
2782 printf("--- buildSubrs()\n");
2783 for (i = 0; i < h->tmp.cnt; i++) {
2784 Link *link;
2785 Subr *subr = h->tmp.array[i];
2786 prints(subr);
2787 printf("={");
2788 for (link = subr->sups; link != NULL; link = link->next) {
2789 prints(link->subr);
2790 }
2791 printf("}{");
2792 for (link = subr->infs; link != NULL; link = link->next) {
2793 prints(link->subr);
2794 }
2795 printf("}\n");
2796 }
2797 #endif
2798
2799 selectFinalSubrSet(h, id);
2800 resetSubrCount(h, id);
2801 reorderSubrs(h, id);
2802 }
2803
2804 static void initLocalSubrs(subrCtx h, long cnt)
2805 {
2806 long i;
2807 dnaSET_CNT(h->localSubrs, cnt);
2808 for (i = 0; i < cnt; i++) {
2809 dnaINIT(h->g->ctx.dnaSafe, h->localSubrs.array[i], 500, 500);
2810 }
2811 }
2812
2813 /* Inline one-use futile subr */
2814 static void inlineFutileSubr(subrCtx h, CallList *callList)
2815 {
2816 long i;
2817 for (i = callList->cnt - 1; i >= 0; i--) {
2818 Call *call = &callList->array[i];
2819 if (call->subr->count == 1) {
2820 Subr *futile = call->subr;
2821 int32_t offset = call->offset;
2822 long diff, rest, j;
2823 inlineFutileSubr(h, &call->subr->callList); /* recursively inline futile subrs */
2824 /* copy subr calls made by the futile subr to this subr
2825 * while ordering & adjusting offsets
2826 */
2827 diff = futile->callList.cnt - 1;
2828 rest = callList->cnt - i - 1;
2829 if (diff > 0) {
2830 dnaSET_CNT(*callList, callList->cnt + diff);
2831 memmove(&callList->array[i + 1 + diff], &callList->array[i + 1], sizeof(Call) * rest);
2832 } else if (diff < 0) {
2833 memmove(&callList->array[i], &callList->array[i + 1], sizeof(Call) * rest);
2834 dnaSET_CNT(*callList, callList->cnt + diff);
2835 }
2836 for (j = 0; j < futile->callList.cnt; j++) {
2837 callList->array[i + j] = futile->callList.array[j];
2838 callList->array[i + j].offset += offset;
2839 }
2840 }
2841 }
2842 }
2843
2844 /* Inline one-use futile subrs in all subrs in a list */
2845 static void inlineFutileSubrs(subrCtx h, SubrList *list)
2846 {
2847 long i;
2848 for (i = 0; i < list->cnt; i++) {
2849 inlineFutileSubr(h, &list->array[i]->callList);
2850 }
2851 }
2852
2853 static int subrBias(long count)
2854 {
2855 if (count < 1240)
2856 return 107;
2857 else if (count < 33900)
2858 return 1131;
2859 else
2860 return 32768;
2861 }
2862
2863 /* Compare subrs by count (frequent ones first) */
2864 static int CTL_CDECL cmpSubrCount(const void *first, const void *second) {
2865 Subr **a = (Subr **)first;
2866 Subr **b = (Subr **)second;
2867 uint32_t count_a = (*a)->count;
2868 uint32_t count_b = (*b)->count;
2869 if (count_a != count_b) {
2870 return count_b - count_a;
2871 } else if ((*a)->order > (*b)->order) {
2872 /* Preserve original order */
2873 return 1;
2874 } else if ((*a)->order < (*b)->order) {
2875 return -1;
2876 } else {
2877 return 0;
2878 }
2879 }
2880
2881 /* Remove futile (zero or one use) subrs and renumber the rest */
2882 static void removeFutileSubrs(subrCtx h, SubrList *list, unsigned id)
2883 {
2884 long i;
2885
2886 dnaSET_CNT(h->tmp, 0);
2887 for (i = 0; i < list->cnt; i++) {
2888 Subr *subr = list->array[i];
2889 if (subr->count > 1) {
2890 subr->order = h->tmp.cnt;
2891 *dnaNEXT(h->tmp) = subr;
2892 }
2893 }
2894
2895 /* Reorder remaining subrs based on their actual use counts */
2896 qsort(h->tmp.array, h->tmp.cnt, sizeof(h->tmp.array[0]), cmpSubrCount);
2897 reorderSubrs(h, id);
2898 }
2899
2900 static void inlineOrRemoveFutileSubrs(subrCtx h)
2901 {
2902 long i, j;
2903
2904 /* Inline all one-use subrs at their call points. */
2905 inlineFutileSubrs(h, &h->globalSubrs);
2906 for (i = 0; i < h->localSubrs.cnt; i++) {
2907 inlineFutileSubrs(h, &h->localSubrs.array[i]);
2908 }
2909 for (i = 0; i < h->charsCallLists.cnt; i++) {
2910 for (j = 0; j < h->charsCallLists.array[i].cnt; j++) {
2911 inlineFutileSubr(h, &h->charsCallLists.array[i].array[j]);
2912 }
2913 }
2914
2915 /* Remove all zero-use and one-use subrs.
2916 * Remaining subrs are renumbered using the actual use count.
2917 */
2918 removeFutileSubrs(h, &h->globalSubrs, NODE_GLOBAL);
2919 for (i = 0; i < h->localSubrs.cnt; i++) {
2920 removeFutileSubrs(h, &h->localSubrs.array[i], (unsigned)i);
2921 }
2922 }
2923
2924 /* Subroutinize all fonts in FontSet */
2925 void cfwSubrSubrize(cfwCtx g, int nFonts, subr_Font *fonts) {
2926 subrCtx h = g->ctx.subr;
2927 unsigned iFont;
2928 long i;
2929
2930 h->nFonts = (short)nFonts;
2931 h->fonts = fonts;
2932 h->maxNumSubrs = g->maxNumSubrs;
2933
2934 /* Initialize opLenCache */
2935 {
2936 unsigned char dummycstr[2] = {
2937 0, 0};
2938 int i;
2939 for (i = 0; i < 256; i++) {
2940 dummycstr[0] = (unsigned char)i;
2941 h->opLenCache[i] = (unsigned char)t2oplen(dummycstr);
2942 }
2943 }
2944
2945 /* Determine type of FontSet */
2946 h->singleton = h->nFonts == 1 && !(h->fonts[0].flags & SUBR_FONT_CID);
2947
2948 /* Add fonts' charstring data to CDAWG */
2949 iFont = 0;
2950 for (i = 0; i < h->nFonts; i++) {
2951 addFont(h, &h->fonts[i], iFont, (h->nFonts > 1) || (h->fonts[i].flags & SUBR_FONT_CID));
2952 iFont += (h->fonts[i].flags & SUBR_FONT_CID) ? h->fonts[i].fdCount : 1;
2953 }
2954
2955 selectCandSubrs(h); /* Select candidate subrs */
2956 buildSubrMatchTrie(h);
2957 setSubrTentativeCount(h); /* Set subr tentative call counts */
2958 #if DB_TEST_STRING
2959 return;
2960 #endif
2961 assocSubrs(h); /* Associate subrs with a font */
2962 sortInfSubrs(h); /* Sort inferior subrs by saving */
2963
2964 if (h->singleton) {
2965 /* Single non-CID font */
2966
2967 /* Build temporary array from full subr list */
2968 dnaSET_CNT(h->tmp, h->subrs.cnt);
2969 for (i = 0; i < h->subrs.cnt; i++) {
2970 h->tmp.array[i] = &h->subrs.array[i];
2971 }
2972
2973 h->subrStackOvl = 0;
2974 selectFinalSubrSet(h, 0);
2975 resetSubrCount(h, 0);
2976
2977 if (h->subrStackOvl) {
2978 cfwMessage(h->g, "subr stack depth exceeded (reduced)");
2979 }
2980
2981 initLocalSubrs(h, 1);
2982 if (h->tmp.cnt >= 215) {
2983 /* Temporarily make local subrs from odd indexes for renumbering */
2984 reorderCombined(h, 1);
2985 /* Make global subrs from even indexes */
2986 reorderCombined(h, 0);
2987 buildSubrsCallLists(h, NODE_GLOBAL);
2988
2989 /* Make local subrs from odd indexes */
2990 reorderCombined(h, 1);
2991 buildSubrsCallLists(h, 0);
2992 } else {
2993 reorderSubrs(h, 0);
2994 buildSubrsCallLists(h, 0);
2995 }
2996 buildCharsCallLists(h, &h->fonts[0].chars, 0);
2997
2998 inlineOrRemoveFutileSubrs(h);
2999
3000 subrizeSubrs(h, &h->gsubrs, NODE_GLOBAL);
3001 subrizeSubrs(h, &h->fonts[0].subrs, 0);
3002 subrizeChars(h, &h->fonts[0].chars, 0);
3003 } else {
3004 /* Multiple fonts or single CID font */
3005
3006 long n = 0;
3007 for (i = 0; i < h->nFonts; i++) {
3008 n += h->fonts[i].fdCount;
3009 }
3010 initLocalSubrs(h, n);
3011
3012 /* Build global subrs */
3013 buildSubrs(h, NODE_GLOBAL);
3014 buildSubrsCallLists(h, NODE_GLOBAL);
3015
3016 /* Build call lists of local subrs for each font */
3017 iFont = 0;
3018 for (i = 0; i < h->nFonts; i++) {
3019 subr_Font *font = &h->fonts[i];
3020 CallLists *callLists = dnaMAX(h->charsCallLists, iFont);
3021 dnaINIT(h->g->ctx.dnaSafe, *callLists, 500, 500);
3022 initCallLists(h, callLists, font->chars.nStrings);
3023
3024 h->subrStackOvl = 0;
3025 if (font->flags & SUBR_FONT_CID) {
3026 /* Subroutinize CID-keyed font */
3027 int16_t iFD;
3028 for (iFD = 0; iFD < h->fonts[i].fdCount; iFD++) {
3029 buildSubrs(h, iFont + iFD);
3030 buildSubrsCallLists(h, iFont + iFD);
3031 buildFDCharsCallLists(h, font, iFont, iFD);
3032 }
3033 iFont += h->fonts[i].fdCount;
3034 } else {
3035 if (font->chars.nStrings != 0) {
3036 /* Subroutinize non-synthetic font */
3037 buildSubrs(h, iFont);
3038 buildSubrsCallLists(h, iFont);
3039 buildCharsCallLists(h, &h->fonts[iFont].chars, iFont);
3040 }
3041 iFont++;
3042 }
3043
3044 if (h->subrStackOvl) {
3045 cfwMessage(h->g, "subr stack depth exceeded (reduced)");
3046 }
3047 }
3048
3049 inlineOrRemoveFutileSubrs(h);
3050
3051 subrizeSubrs(h, &h->gsubrs, NODE_GLOBAL);
3052 /* Add local subrs to each font */
3053 iFont = 0;
3054 for (i = 0; i < h->nFonts; i++) {
3055 subr_Font *font = &h->fonts[i];
3056
3057 if (font->flags & SUBR_FONT_CID) {
3058 int16_t iFD;
3059 for (iFD = 0; iFD < font->fdCount; iFD++) {
3060 /* Subroutinize component DICT */
3061 subr_FDInfo *info = &font->fdInfo[iFD];
3062 subrizeSubrs(h, &info->subrs, iFont + iFD);
3063 subrizeFDChars(h, &info->chars, font, iFont, iFD);
3064 }
3065 joinFDChars(h, font);
3066 iFont += font->fdCount;
3067 } else {
3068 if (font->chars.nStrings != 0) {
3069 /* Subroutinize non-synthetic font */
3070 subrizeSubrs(h, &h->fonts[iFont].subrs, iFont);
3071 subrizeChars(h, &font->chars, iFont);
3072 }
3073 iFont++;
3074 }
3075 }
3076 }
3077
3078 /* Free original unsubroutinized charstring data */
3079 for (i = 0; i < h->nFonts; i++) {
3080 MEM_FREE(g, h->fonts[i].chars.refcopy);
3081 }
3082
3083 #if EDGE_HASH_STAT
3084 if (gTotalEdgeLookupCount) {
3085 printf("hash table statistics -- total lookup: %lld, average table size (dynamic): %.2lf, average fill rate (dynamic): %d%%, average miss per call: %.2lf\n",
3086 gTotalEdgeLookupCount, (double)gTotalEdgeTableSize / gTotalEdgeLookupCount,
3087 (int)(((double)gTotalEdgeCount / gTotalEdgeTableSize) * 100.0), (double)gTotalEdgeMissCount / gTotalEdgeLookupCount);
3088
3089 {
3090 MemInfo *info = &h->nodeBlks;
3091 MemBlk *pblk = info->head;
3092 long long totalTableSize = 0;
3093 long long totalEdgeCount = 0;
3094 long long nodeCount = 0;
3095 while (pblk) {
3096 short i;
3097 Node *node;
3098 for (i = 0, node = (Node *)&pblk->array[0]; i < pblk->iNext; i++, node++) {
3099 if (node->edgeTable) {
3100 totalTableSize += node->edgeTableSize;
3101 totalEdgeCount += node->edgeCount;
3102 nodeCount++;
3103 }
3104 }
3105 pblk = pblk->nextBlk;
3106 }
3107 printf("average table size (static): %2lf, average fill rate (static): %d%%\n",
3108 (double)totalTableSize / nodeCount, (int)((double)totalEdgeCount / totalTableSize * 100.0));
3109 }
3110 }
3111 #endif
3112 }
3113
3114 /* Compute size of font's subrs */
3115 long cfwSubrSizeLocal(cfwCtx g, subr_CSData *subrs) {
3116 long size = 0;
3117 if (g->flags & CFW_WRITE_CFF2) {
3118 size = (!subrs || subrs->nStrings == 0) ? 0 : INDEX2_SIZE(subrs->nStrings, subrs->offset[subrs->nStrings - 1]);
3119 } else {
3120 size = (!subrs || subrs->nStrings == 0) ? 0 : INDEX_SIZE(subrs->nStrings, subrs->offset[subrs->nStrings - 1]);
3121 }
3122 return size;
3123 }
3124
3125 /* Compute size of global subrs */
3126 long cfwSubrSizeGlobal(cfwCtx g) {
3127 subrCtx h = g->ctx.subr;
3128 long size = 0;
3129 if (g->flags & CFW_WRITE_CFF2) {
3130 size = (!h || h->gsubrs.nStrings == 0) ? INDEX2_SIZE(0, 0) : INDEX2_SIZE(h->gsubrs.nStrings, h->gsubrs.offset[h->gsubrs.nStrings - 1]);
3131 } else {
3132 size = (!h || h->gsubrs.nStrings == 0) ? INDEX_SIZE(0, 0) : INDEX_SIZE(h->gsubrs.nStrings, h->gsubrs.offset[h->gsubrs.nStrings - 1]);
3133 }
3134 return size;
3135 }
3136
3137 /* Write subrs */
3138 static void subrWrite(cfwCtx g, subr_CSData *subrs) {
3139 long dataSize;
3140 INDEXHdr header;
3141 unsigned i;
3142
3143 header.count = subrs->nStrings;
3144 if (g->flags & CFW_WRITE_CFF2) {
3145 cfwWriteN(g, 4, header.count);
3146 } else {
3147 cfwWrite2(g, header.count);
3148 }
3149
3150 if (header.count == 0) {
3151 return; /* Empty table just has zero count */
3152 }
3153 dataSize = subrs->offset[subrs->nStrings - 1];
3154 header.offSize = INDEX_OFF_SIZE(dataSize);
3155 cfwWrite1(g, header.offSize);
3156
3157 /* Write offset array */
3158 cfwWriteN(g, header.offSize, 1);
3159 for (i = 0; i < subrs->nStrings; i++) {
3160 cfwWriteN(g, header.offSize, subrs->offset[i] + 1);
3161 }
3162
3163 /* Write charstring data */
3164 cfwWrite(g, dataSize, subrs->data);
3165 }
3166
3167 /* Write local subrs */
3168 void cfwSubrWriteLocal(cfwCtx g, subr_CSData *subrs) {
3169 if (subrs && subrs->nStrings != 0) {
3170 subrWrite(g, subrs);
3171 }
3172 }
3173
3174 /* Write global subrs */
3175 void cfwSubrWriteGlobal(cfwCtx g) {
3176 subrCtx h = g->ctx.subr;
3177 if (h != NULL) {
3178 subrWrite(g, &h->gsubrs);
3179 } else {
3180 /* Write empty global subr INDEX */
3181 INDEXHdr header;
3182 header.count = 0;
3183 if (g->flags & CFW_WRITE_CFF2) {
3184 cfwWriteN(g, 4, header.count);
3185 } else {
3186 cfwWrite2(g, header.count);
3187 }
3188 }
3189 }
3190
3191 #if TC_DEBUG
3192 /* --------------------------------- DEBUG --------------------------------- */
3193 #include <ctype.h>
3194
3195 static long dbnodeid(subrCtx h, Node *node) {
3196 MemBlk *nb;
3197
3198 if (node == NULL) {
3199 return -1;
3200 }
3201
3202 for (nb = h->nodeBlks.head; nb != NULL; nb = nb->nextBlk) {
3203 if ((Node *)nb->array <= node &&
3204 (Node *)nb->array + NODES_PER_BLK > node) {
3205 long blks = node - (Node *)nb->array;
3206 for (nb = nb->nextBlk; nb != NULL; nb = nb->nextBlk) {
3207 blks += NODES_PER_BLK;
3208 }
3209 return blks;
3210 }
3211 }
3212
3213 printf("can't find node!");
3214 return 0;
3215 }
3216
3217 static void dbop(int length, unsigned char *cstr) {
3218 int i;
3219 for (i = 0; i < length; i++) {
3220 printf("%c%c",
3221 "0123456789abcdef"[cstr[i] >> 4],
3222 "0123456789abcdef"[cstr[i] & 0xf]);
3223 }
3224 }
3225
3226 static char *dbinfo(subrCtx h, Subr *subr, int mark) {
3227 static char buf[16];
3228 sprintf(buf, "%hu.%hu%c%d", subr->count, subr->length - subr->maskcnt,
3229 mark, subrSaved(h, subr));
3230 return buf;
3231 }
3232
3233 static void dbsubr(subrCtx h, unsigned iSubr, int c, unsigned offset) {
3234 Subr *subr = &h->subrs.array[iSubr];
3235 int mark = (subr->node->id == NODE_GLOBAL) ? '~' : '=';
3236 if (c == '#') {
3237 /* A regular subr rather than an inf or sup */
3238 if (!(subr->flags & SUBR_SELECT)) {
3239 c = '.';
3240 }
3241 } else if (subr->flags & SUBR_SELECT) {
3242 c = toupper(c);
3243 }
3244 printf("%-9s%-*c", dbinfo(h, subr, mark), offset * 2 + 3, c);
3245 dbcstr(h, subr->length, subr->cstr);
3246 printf(" [%hu]\n", iSubr);
3247 }
3248
3249 static void dbnodeProc(subrCtx h, Edge *edge, long misc, long param2) {
3250 if (!edge || !edge->label) {
3251 return;
3252 }
3253 printf(" %6ld (%08lx) %8s ",
3254 dbnodeid(h, edge->son), (unsigned long)edge->son,
3255 (misc + OPLEN(h, edge->label) !=
3256 edge->son->misc)
3257 ? "shortcut"
3258 : "-");
3259 dbop(OPLEN(h, edge->label), edge->label);
3260 printf(" (%08lx)\n", (unsigned long)edge);
3261 }
3262
3263 static void dbnode(subrCtx h, Node *node) {
3264 printf("--- node[%ld]\n", dbnodeid(h, node));
3265 printf("suffix=%ld (%08lx)\n",
3266 dbnodeid(h, node->suffix), (unsigned long)node->suffix);
3267 printf("misc =%ld\n", node->misc);
3268 printf("paths =%hu\n", node->paths);
3269 printf("id =%hu\n", node->id);
3270 printf("flags =%04hx (", (unsigned short)node->flags);
3271
3272 if (node->flags == 0) {
3273 printf("none");
3274 } else {
3275 char *sep = "";
3276 if (node->flags & NODE_COUNTED) {
3277 printf("%sCOUNTED", sep);
3278 sep = ",";
3279 }
3280 if (node->flags & NODE_SUBR) {
3281 printf("%sSUBR", sep);
3282 sep = ",";
3283 }
3284 }
3285 printf(")\n");
3286
3287 printf("edges:\n");
3288 if (node->edgeTable == NULL) {
3289 printf(" none\n");
3290 } else {
3291 walkEdgeTable(h, node, dbnodeProc, node->misc, 0);
3292 }
3293 }
3294
3295 static void dbcstr(subrCtx h, unsigned length, unsigned char *cstr) {
3296 unsigned char *end = cstr + length;
3297 #if DB_TEST_STRING
3298 unsigned char *start = cstr;
3299 #endif
3300 while (cstr < end) {
3301 unsigned i;
3302
3303 length = OPLEN(h, cstr);
3304 for (i = 0; i < length; i++)
3305 #if DB_TEST_STRING
3306 {
3307 printf("%c%c", cstr == start ? '"' : ' ', cstr[i]);
3308 }
3309 #else
3310 {
3311 printf("%c%c",
3312 "0123456789abcdef"[cstr[i] >> 4],
3313 "0123456789abcdef"[cstr[i] & 0xf]);
3314 }
3315 #endif
3316
3317 cstr += length;
3318 }
3319 #if DB_TEST_STRING
3320 printf("\"");
3321 #endif
3322 }
3323
3324 static void dbcstrs(subrCtx h, unsigned char *cstr, unsigned char *end,
3325 int index) {
3326 int startchar = 1;
3327 int gid = 0;
3328
3329 printf("--- glyphs (total=%ld)\n", (long)(end - cstr));
3330
3331 while (cstr < end) {
3332 int length = OPLEN(h, cstr);
3333
3334 if (startchar) {
3335 printf("%2d:%3d ", index, gid);
3336 startchar = 0;
3337 gid++;
3338 }
3339
3340 dbop(length, cstr);
3341
3342 if (cstr[0] == SEPARATOR) {
3343 startchar = 1;
3344 printf("\n");
3345 }
3346
3347 cstr += length;
3348 }
3349 }
3350
3351 static void dbgroups(subrCtx h) {
3352 long i;
3353
3354 printf("--- social groups\n");
3355
3356 for (i = 0; i < h->leaders.cnt; i++) {
3357 Subr *subr;
3358
3359 printf("--- link group[%ld]\n", i);
3360 for (subr = h->leaders.array[i]; subr != NULL; subr = subr->next) {
3361 Link *link;
3362 unsigned offset;
3363 int iSubr = subr - h->subrs.array;
3364
3365 /* Find max superior offset */
3366 offset = 0;
3367 for (link = subr->sups; link != NULL; link = link->next) {
3368 if (offset < link->offset) {
3369 offset = link->offset;
3370 }
3371 }
3372
3373 dbsubr(h, iSubr, '#', offset);
3374
3375 /* Print inferiors */
3376 for (link = subr->infs; link != NULL; link = link->next) {
3377 dbsubr(h, link->subr - h->subrs.array, 'i',
3378 offset + link->offset);
3379 }
3380
3381 /* Print superiors */
3382 for (link = subr->sups; link != NULL; link = link->next) {
3383 dbsubr(h, link->subr - h->subrs.array, 's',
3384 offset - link->offset);
3385 }
3386 }
3387 }
3388 }
3389
3390 /* This function just serves to suppress annoying "defined but not used"
3391 compiler messages when debugging */
3392 static void CTL_CDECL dbuse(int arg, ...) {
3393 dbuse(0, dbnode, dbcstrs, dbsubr, dbgroups);
3394 }
3395
3396 #endif /* TC_DEBUG */