1 /* GRAPHITE2 LICENSING
2
3 Copyright 2010, SIL International
4 All rights reserved.
5
6 This library is free software; you can redistribute it and/or modify
7 it under the terms of the GNU Lesser General Public License as published
8 by the Free Software Foundation; either version 2.1 of License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
15
16 You should also have received a copy of the GNU Lesser General Public
17 License along with this library in the file named "LICENSE".
18 If not, write to the Free Software Foundation, 51 Franklin Street,
19 Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
20 internet at http://www.fsf.org/licenses/lgpl.html.
21
22 Alternatively, the contents of this file may be used under the terms of the
23 Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
24 License, as published by the Free Software Foundation, either version 2
25 of the License or (at your option) any later version.
26 */
27 #include "inc/Main.h"
28 #include "inc/debug.h"
29 #include "inc/Endian.h"
30 #include "inc/Pass.h"
31 #include <cstring>
32 #include <cstdlib>
33 #include <cassert>
34 #include <cmath>
35 #include "inc/Segment.h"
36 #include "inc/Code.h"
37 #include "inc/Rule.h"
38 #include "inc/Error.h"
39 #include "inc/Collider.h"
40
41 using namespace graphite2;
42 using vm::Machine;
43 typedef Machine::Code Code;
44
45 enum KernCollison
46 {
47 None = 0,
48 CrossSpace = 1,
49 InWord = 2,
50 reserved = 3
51 };
52
Pass()53 Pass::Pass()
54 : m_silf(0),
55 m_cols(0),
56 m_rules(0),
57 m_ruleMap(0),
58 m_startStates(0),
59 m_transitions(0),
60 m_states(0),
61 m_codes(0),
62 m_progs(0),
63 m_numCollRuns(0),
64 m_kernColls(0),
65 m_iMaxLoop(0),
66 m_numGlyphs(0),
67 m_numRules(0),
68 m_numStates(0),
69 m_numTransition(0),
70 m_numSuccess(0),
71 m_successStart(0),
72 m_numColumns(0),
73 m_minPreCtxt(0),
74 m_maxPreCtxt(0),
75 m_colThreshold(0),
76 m_isReverseDir(false)
77 {
78 }
79
~Pass()80 Pass::~Pass()
81 {
82 free(m_cols);
83 free(m_startStates);
84 free(m_transitions);
85 free(m_states);
86 free(m_ruleMap);
87
88 if (m_rules) delete [] m_rules;
89 if (m_codes) delete [] m_codes;
90 free(m_progs);
91 }
92
readPass(const byte * const pass_start,size_t pass_length,size_t subtable_base,GR_MAYBE_UNUSED Face & face,passtype pt,GR_MAYBE_UNUSED uint32 version,Error & e)93 bool Pass::readPass(const byte * const pass_start, size_t pass_length, size_t subtable_base,
94 GR_MAYBE_UNUSED Face & face, passtype pt, GR_MAYBE_UNUSED uint32 version, Error &e)
95 {
96 const byte * p = pass_start,
97 * const pass_end = p + pass_length;
98 size_t numRanges;
99
100 if (e.test(pass_length < 40, E_BADPASSLENGTH)) return face.error(e);
101 // Read in basic values
102 const byte flags = be::read<byte>(p);
103 if (e.test((flags & 0x1f) &&
104 (pt < PASS_TYPE_POSITIONING || !m_silf->aCollision() || !face.glyphs().hasBoxes() || !(m_silf->flags() & 0x20)),
105 E_BADCOLLISIONPASS))
106 return face.error(e);
107 m_numCollRuns = flags & 0x7;
108 m_kernColls = (flags >> 3) & 0x3;
109 m_isReverseDir = (flags >> 5) & 0x1;
110 m_iMaxLoop = be::read<byte>(p);
111 if (m_iMaxLoop < 1) m_iMaxLoop = 1;
112 be::skip<byte>(p,2); // skip maxContext & maxBackup
113 m_numRules = be::read<uint16>(p);
114 if (e.test(!m_numRules && m_numCollRuns == 0, E_BADEMPTYPASS)) return face.error(e);
115 be::skip<uint16>(p); // fsmOffset - not sure why we would want this
116 const byte * const pcCode = pass_start + be::read<uint32>(p) - subtable_base,
117 * const rcCode = pass_start + be::read<uint32>(p) - subtable_base,
118 * const aCode = pass_start + be::read<uint32>(p) - subtable_base;
119 be::skip<uint32>(p);
120 m_numStates = be::read<uint16>(p);
121 m_numTransition = be::read<uint16>(p);
122 m_numSuccess = be::read<uint16>(p);
123 m_numColumns = be::read<uint16>(p);
124 numRanges = be::read<uint16>(p);
125 be::skip<uint16>(p, 3); // skip searchRange, entrySelector & rangeShift.
126 assert(p - pass_start == 40);
127 // Perform some sanity checks.
128 if ( e.test(m_numTransition > m_numStates, E_BADNUMTRANS)
129 || e.test(m_numSuccess > m_numStates, E_BADNUMSUCCESS)
130 || e.test(m_numSuccess + m_numTransition < m_numStates, E_BADNUMSTATES)
131 || e.test(m_numRules && numRanges == 0, E_NORANGES)
132 || e.test(m_numColumns > 0x7FFF, E_BADNUMCOLUMNS))
133 return face.error(e);
134
135 m_successStart = m_numStates - m_numSuccess;
136 // test for beyond end - 1 to account for reading uint16
137 if (e.test(p + numRanges * 6 - 2 > pass_end, E_BADPASSLENGTH)) return face.error(e);
138 m_numGlyphs = be::peek<uint16>(p + numRanges * 6 - 4) + 1;
139 // Calculate the start of various arrays.
140 const byte * const ranges = p;
141 be::skip<uint16>(p, numRanges*3);
142 const byte * const o_rule_map = p;
143 be::skip<uint16>(p, m_numSuccess + 1);
144
145 // More sanity checks
146 if (e.test(reinterpret_cast<const byte *>(o_rule_map + m_numSuccess*sizeof(uint16)) > pass_end
147 || p > pass_end, E_BADRULEMAPLEN))
148 return face.error(e);
149 const size_t numEntries = be::peek<uint16>(o_rule_map + m_numSuccess*sizeof(uint16));
150 const byte * const rule_map = p;
151 be::skip<uint16>(p, numEntries);
152
153 if (e.test(p + 2*sizeof(uint8) > pass_end, E_BADPASSLENGTH)) return face.error(e);
154 m_minPreCtxt = be::read<uint8>(p);
155 m_maxPreCtxt = be::read<uint8>(p);
156 if (e.test(m_minPreCtxt > m_maxPreCtxt, E_BADCTXTLENBOUNDS)) return face.error(e);
157 const byte * const start_states = p;
158 be::skip<int16>(p, m_maxPreCtxt - m_minPreCtxt + 1);
159 const uint16 * const sort_keys = reinterpret_cast<const uint16 *>(p);
160 be::skip<uint16>(p, m_numRules);
161 const byte * const precontext = p;
162 be::skip<byte>(p, m_numRules);
163
164 if (e.test(p + sizeof(uint16) + sizeof(uint8) > pass_end, E_BADCTXTLENS)) return face.error(e);
165 m_colThreshold = be::read<uint8>(p);
166 if (m_colThreshold == 0) m_colThreshold = 10; // A default
167 const size_t pass_constraint_len = be::read<uint16>(p);
168
169 const uint16 * const o_constraint = reinterpret_cast<const uint16 *>(p);
170 be::skip<uint16>(p, m_numRules + 1);
171 const uint16 * const o_actions = reinterpret_cast<const uint16 *>(p);
172 be::skip<uint16>(p, m_numRules + 1);
173 const byte * const states = p;
174 if (e.test(2u*m_numTransition*m_numColumns >= (unsigned)(pass_end - p), E_BADPASSLENGTH)
175 || e.test(p >= pass_end, E_BADPASSLENGTH))
176 return face.error(e);
177 be::skip<int16>(p, m_numTransition*m_numColumns);
178 be::skip<uint8>(p);
179 if (e.test(p != pcCode, E_BADPASSCCODEPTR)) return face.error(e);
180 be::skip<byte>(p, pass_constraint_len);
181 if (e.test(p != rcCode, E_BADRULECCODEPTR)
182 || e.test(size_t(rcCode - pcCode) != pass_constraint_len, E_BADCCODELEN)) return face.error(e);
183 be::skip<byte>(p, be::peek<uint16>(o_constraint + m_numRules));
184 if (e.test(p != aCode, E_BADACTIONCODEPTR)) return face.error(e);
185 be::skip<byte>(p, be::peek<uint16>(o_actions + m_numRules));
186
187 // We should be at the end or within the pass
188 if (e.test(p > pass_end, E_BADPASSLENGTH)) return face.error(e);
189
190 // Load the pass constraint if there is one.
191 if (pass_constraint_len)
192 {
193 face.error_context(face.error_context() + 1);
194 m_cPConstraint = vm::Machine::Code(true, pcCode, pcCode + pass_constraint_len,
195 precontext[0], be::peek<uint16>(sort_keys), *m_silf, face, PASS_TYPE_UNKNOWN);
196 if (e.test(!m_cPConstraint, E_OUTOFMEM)
197 || e.test(m_cPConstraint.status() != Code::loaded, m_cPConstraint.status() + E_CODEFAILURE))
198 return face.error(e);
199 face.error_context(face.error_context() - 1);
200 }
201 if (m_numRules)
202 {
203 if (!readRanges(ranges, numRanges, e)) return face.error(e);
204 if (!readRules(rule_map, numEntries, precontext, sort_keys,
205 o_constraint, rcCode, o_actions, aCode, face, pt, e)) return false;
206 }
207 #ifdef GRAPHITE2_TELEMETRY
208 telemetry::category _states_cat(face.tele.states);
209 #endif
210 return m_numRules ? readStates(start_states, states, o_rule_map, face, e) : true;
211 }
212
213
readRules(const byte * rule_map,const size_t num_entries,const byte * precontext,const uint16 * sort_key,const uint16 * o_constraint,const byte * rc_data,const uint16 * o_action,const byte * ac_data,Face & face,passtype pt,Error & e)214 bool Pass::readRules(const byte * rule_map, const size_t num_entries,
215 const byte *precontext, const uint16 * sort_key,
216 const uint16 * o_constraint, const byte *rc_data,
217 const uint16 * o_action, const byte * ac_data,
218 Face & face, passtype pt, Error &e)
219 {
220 const byte * const ac_data_end = ac_data + be::peek<uint16>(o_action + m_numRules);
221 const byte * const rc_data_end = rc_data + be::peek<uint16>(o_constraint + m_numRules);
222
223 precontext += m_numRules;
224 sort_key += m_numRules;
225 o_constraint += m_numRules;
226 o_action += m_numRules;
227
228 // Load rules.
229 const byte * ac_begin = 0, * rc_begin = 0,
230 * ac_end = ac_data + be::peek<uint16>(o_action),
231 * rc_end = rc_data + be::peek<uint16>(o_constraint);
232
233 // Allocate pools
234 m_rules = new Rule [m_numRules];
235 m_codes = new Code [m_numRules*2];
236 int totalSlots = 0;
237 const uint16 *tsort = sort_key;
238 for (int i = 0; i < m_numRules; ++i)
239 totalSlots += be::peek<uint16>(--tsort);
240 const size_t prog_pool_sz = vm::Machine::Code::estimateCodeDataOut(ac_end - ac_data + rc_end - rc_data, 2 * m_numRules, totalSlots);
241 m_progs = gralloc<byte>(prog_pool_sz);
242 byte * prog_pool_free = m_progs,
243 * prog_pool_end = m_progs + prog_pool_sz;
244 if (e.test(!(m_rules && m_codes && m_progs), E_OUTOFMEM)) return face.error(e);
245
246 Rule * r = m_rules + m_numRules - 1;
247 for (size_t n = m_numRules; r >= m_rules; --n, --r, ac_end = ac_begin, rc_end = rc_begin)
248 {
249 face.error_context((face.error_context() & 0xFFFF00) + EC_ARULE + int((n - 1) << 24));
250 r->preContext = *--precontext;
251 r->sort = be::peek<uint16>(--sort_key);
252 #ifndef NDEBUG
253 r->rule_idx = uint16(n - 1);
254 #endif
255 if (r->sort > 63 || r->preContext >= r->sort || r->preContext > m_maxPreCtxt || r->preContext < m_minPreCtxt)
256 return false;
257 ac_begin = ac_data + be::peek<uint16>(--o_action);
258 --o_constraint;
259 rc_begin = be::peek<uint16>(o_constraint) ? rc_data + be::peek<uint16>(o_constraint) : rc_end;
260
261 if (ac_begin > ac_end || ac_begin > ac_data_end || ac_end > ac_data_end
262 || rc_begin > rc_end || rc_begin > rc_data_end || rc_end > rc_data_end
263 || vm::Machine::Code::estimateCodeDataOut(ac_end - ac_begin + rc_end - rc_begin, 2, r->sort) > size_t(prog_pool_end - prog_pool_free))
264 return false;
265 r->action = new (m_codes+n*2-2) vm::Machine::Code(false, ac_begin, ac_end, r->preContext, r->sort, *m_silf, face, pt, &prog_pool_free);
266 r->constraint = new (m_codes+n*2-1) vm::Machine::Code(true, rc_begin, rc_end, r->preContext, r->sort, *m_silf, face, pt, &prog_pool_free);
267
268 if (e.test(!r->action || !r->constraint, E_OUTOFMEM)
269 || e.test(r->action->status() != Code::loaded, r->action->status() + E_CODEFAILURE)
270 || e.test(r->constraint->status() != Code::loaded, r->constraint->status() + E_CODEFAILURE)
271 || e.test(!r->constraint->immutable(), E_MUTABLECCODE))
272 return face.error(e);
273 }
274
275 byte * const moved_progs = prog_pool_free > m_progs ? static_cast<byte *>(realloc(m_progs, prog_pool_free - m_progs)) : 0;
276 if (e.test(!moved_progs, E_OUTOFMEM))
277 {
278 free(m_progs);
279 m_progs = 0;
280 return face.error(e);
281 }
282
283 if (moved_progs != m_progs)
284 {
285 for (Code * c = m_codes, * const ce = c + m_numRules*2; c != ce; ++c)
286 {
287 c->externalProgramMoved(moved_progs - m_progs);
288 }
289 m_progs = moved_progs;
290 }
291
292 // Load the rule entries map
293 face.error_context((face.error_context() & 0xFFFF00) + EC_APASS);
294 //TODO: Coverity: 1315804: FORWARD_NULL
295 RuleEntry * re = m_ruleMap = gralloc<RuleEntry>(num_entries);
296 if (e.test(!re, E_OUTOFMEM)) return face.error(e);
297 for (size_t n = num_entries; n; --n, ++re)
298 {
299 const ptrdiff_t rn = be::read<uint16>(rule_map);
300 if (e.test(rn >= m_numRules, E_BADRULENUM)) return face.error(e);
301 re->rule = m_rules + rn;
302 }
303
304 return true;
305 }
306
cmpRuleEntry(const void * a,const void * b)307 static int cmpRuleEntry(const void *a, const void *b) { return (*(RuleEntry *)a < *(RuleEntry *)b ? -1 :
308 (*(RuleEntry *)b < *(RuleEntry *)a ? 1 : 0)); }
309
readStates(const byte * starts,const byte * states,const byte * o_rule_map,GR_MAYBE_UNUSED Face & face,Error & e)310 bool Pass::readStates(const byte * starts, const byte *states, const byte * o_rule_map, GR_MAYBE_UNUSED Face & face, Error &e)
311 {
312 #ifdef GRAPHITE2_TELEMETRY
313 telemetry::category _states_cat(face.tele.starts);
314 #endif
315 m_startStates = gralloc<uint16>(m_maxPreCtxt - m_minPreCtxt + 1);
316 #ifdef GRAPHITE2_TELEMETRY
317 telemetry::set_category(face.tele.states);
318 #endif
319 m_states = gralloc<State>(m_numStates);
320 #ifdef GRAPHITE2_TELEMETRY
321 telemetry::set_category(face.tele.transitions);
322 #endif
323 m_transitions = gralloc<uint16>(m_numTransition * m_numColumns);
324
325 if (e.test(!m_startStates || !m_states || !m_transitions, E_OUTOFMEM)) return face.error(e);
326 // load start states
327 for (uint16 * s = m_startStates,
328 * const s_end = s + m_maxPreCtxt - m_minPreCtxt + 1; s != s_end; ++s)
329 {
330 *s = be::read<uint16>(starts);
331 if (e.test(*s >= m_numStates, E_BADSTATE))
332 {
333 face.error_context((face.error_context() & 0xFFFF00) + EC_ASTARTS + int((s - m_startStates) << 24));
334 return face.error(e); // true;
335 }
336 }
337
338 // load state transition table.
339 for (uint16 * t = m_transitions,
340 * const t_end = t + m_numTransition*m_numColumns; t != t_end; ++t)
341 {
342 *t = be::read<uint16>(states);
343 if (e.test(*t >= m_numStates, E_BADSTATE))
344 {
345 face.error_context((face.error_context() & 0xFFFF00) + EC_ATRANS + int(((t - m_transitions) / m_numColumns) << 8));
346 return face.error(e);
347 }
348 }
349
350 State * s = m_states,
351 * const success_begin = m_states + m_numStates - m_numSuccess;
352 const RuleEntry * rule_map_end = m_ruleMap + be::peek<uint16>(o_rule_map + m_numSuccess*sizeof(uint16));
353 for (size_t n = m_numStates; n; --n, ++s)
354 {
355 RuleEntry * const begin = s < success_begin ? 0 : m_ruleMap + be::read<uint16>(o_rule_map),
356 * const end = s < success_begin ? 0 : m_ruleMap + be::peek<uint16>(o_rule_map);
357
358 if (e.test(begin >= rule_map_end || end > rule_map_end || begin > end, E_BADRULEMAPPING))
359 {
360 face.error_context((face.error_context() & 0xFFFF00) + EC_ARULEMAP + int(n << 24));
361 return face.error(e);
362 }
363 s->rules = begin;
364 s->rules_end = (end - begin <= FiniteStateMachine::MAX_RULES)? end :
365 begin + FiniteStateMachine::MAX_RULES;
366 if (begin) // keep UBSan happy can't call qsort with null begin
367 qsort(begin, end - begin, sizeof(RuleEntry), &cmpRuleEntry);
368 }
369
370 return true;
371 }
372
readRanges(const byte * ranges,size_t num_ranges,Error & e)373 bool Pass::readRanges(const byte * ranges, size_t num_ranges, Error &e)
374 {
375 m_cols = gralloc<uint16>(m_numGlyphs);
376 if (e.test(!m_cols, E_OUTOFMEM)) return false;
377 memset(m_cols, 0xFF, m_numGlyphs * sizeof(uint16));
378 for (size_t n = num_ranges; n; --n)
379 {
380 uint16 * ci = m_cols + be::read<uint16>(ranges),
381 * ci_end = m_cols + be::read<uint16>(ranges) + 1,
382 col = be::read<uint16>(ranges);
383
384 if (e.test(ci >= ci_end || ci_end > m_cols+m_numGlyphs || col >= m_numColumns, E_BADRANGE))
385 return false;
386
387 // A glyph must only belong to one column at a time
388 while (ci != ci_end && *ci == 0xffff)
389 *ci++ = col;
390
391 if (e.test(ci != ci_end, E_BADRANGE))
392 return false;
393 }
394 return true;
395 }
396
397
runGraphite(vm::Machine & m,FiniteStateMachine & fsm,bool reverse) const398 bool Pass::runGraphite(vm::Machine & m, FiniteStateMachine & fsm, bool reverse) const
399 {
400 Slot *s = m.slotMap().segment.first();
401 if (!s || !testPassConstraint(m)) return true;
402 if (reverse)
403 {
404 m.slotMap().segment.reverseSlots();
405 s = m.slotMap().segment.first();
406 }
407 if (m_numRules)
408 {
409 Slot *currHigh = s->next();
410
411 #if !defined GRAPHITE2_NTRACING
412 if (fsm.dbgout) *fsm.dbgout << "rules" << json::array;
413 json::closer rules_array_closer(fsm.dbgout);
414 #endif
415
416 m.slotMap().highwater(currHigh);
417 int lc = m_iMaxLoop;
418 do
419 {
420 findNDoRule(s, m, fsm);
421 if (m.status() != Machine::finished) return false;
422 if (s && (s == m.slotMap().highwater() || m.slotMap().highpassed() || --lc == 0)) {
423 if (!lc)
424 s = m.slotMap().highwater();
425 lc = m_iMaxLoop;
426 if (s)
427 m.slotMap().highwater(s->next());
428 }
429 } while (s);
430 }
431 //TODO: Use enums for flags
432 const bool collisions = m_numCollRuns || m_kernColls;
433
434 if (!collisions || !m.slotMap().segment.hasCollisionInfo())
435 return true;
436
437 if (m_numCollRuns)
438 {
439 if (!(m.slotMap().segment.flags() & Segment::SEG_INITCOLLISIONS))
440 {
441 m.slotMap().segment.positionSlots(0, 0, 0, m.slotMap().dir(), true);
442 // m.slotMap().segment.flags(m.slotMap().segment.flags() | Segment::SEG_INITCOLLISIONS);
443 }
444 if (!collisionShift(&m.slotMap().segment, m.slotMap().dir(), fsm.dbgout))
445 return false;
446 }
447 if ((m_kernColls) && !collisionKern(&m.slotMap().segment, m.slotMap().dir(), fsm.dbgout))
448 return false;
449 if (collisions && !collisionFinish(&m.slotMap().segment, fsm.dbgout))
450 return false;
451 return true;
452 }
453
runFSM(FiniteStateMachine & fsm,Slot * slot) const454 bool Pass::runFSM(FiniteStateMachine& fsm, Slot * slot) const
455 {
456 fsm.reset(slot, m_maxPreCtxt);
457 if (fsm.slots.context() < m_minPreCtxt)
458 return false;
459
460 uint16 state = m_startStates[m_maxPreCtxt - fsm.slots.context()];
461 uint8 free_slots = SlotMap::MAX_SLOTS;
462 do
463 {
464 fsm.slots.pushSlot(slot);
465 if (slot->gid() >= m_numGlyphs
466 || m_cols[slot->gid()] == 0xffffU
467 || --free_slots == 0
468 || state >= m_numTransition)
469 return free_slots != 0;
470
471 const uint16 * transitions = m_transitions + state*m_numColumns;
472 state = transitions[m_cols[slot->gid()]];
473 if (state >= m_successStart)
474 fsm.rules.accumulate_rules(m_states[state]);
475
476 slot = slot->next();
477 } while (state != 0 && slot);
478
479 fsm.slots.pushSlot(slot);
480 return true;
481 }
482
483 #if !defined GRAPHITE2_NTRACING
484
485 inline
input_slot(const SlotMap & slots,const int n)486 Slot * input_slot(const SlotMap & slots, const int n)
487 {
488 Slot * s = slots[slots.context() + n];
489 if (!s->isCopied()) return s;
490
491 return s->prev() ? s->prev()->next() : (s->next() ? s->next()->prev() : slots.segment.last());
492 }
493
494 inline
output_slot(const SlotMap & slots,const int n)495 Slot * output_slot(const SlotMap & slots, const int n)
496 {
497 Slot * s = slots[slots.context() + n - 1];
498 return s ? s->next() : slots.segment.first();
499 }
500
501 #endif //!defined GRAPHITE2_NTRACING
502
findNDoRule(Slot * & slot,Machine & m,FiniteStateMachine & fsm) const503 void Pass::findNDoRule(Slot * & slot, Machine &m, FiniteStateMachine & fsm) const
504 {
505 assert(slot);
506
507 if (runFSM(fsm, slot))
508 {
509 // Search for the first rule which passes the constraint
510 const RuleEntry * r = fsm.rules.begin(),
511 * const re = fsm.rules.end();
512 while (r != re && !testConstraint(*r->rule, m))
513 {
514 ++r;
515 if (m.status() != Machine::finished)
516 return;
517 }
518
519 #if !defined GRAPHITE2_NTRACING
520 if (fsm.dbgout)
521 {
522 if (fsm.rules.size() != 0)
523 {
524 *fsm.dbgout << json::item << json::object;
525 dumpRuleEventConsidered(fsm, *r);
526 if (r != re)
527 {
528 const int adv = doAction(r->rule->action, slot, m);
529 dumpRuleEventOutput(fsm, *r->rule, slot);
530 if (r->rule->action->deletes()) fsm.slots.collectGarbage(slot);
531 adjustSlot(adv, slot, fsm.slots);
532 *fsm.dbgout << "cursor" << objectid(dslot(&fsm.slots.segment, slot))
533 << json::close; // Close RuelEvent object
534
535 return;
536 }
537 else
538 {
539 *fsm.dbgout << json::close // close "considered" array
540 << "output" << json::null
541 << "cursor" << objectid(dslot(&fsm.slots.segment, slot->next()))
542 << json::close;
543 }
544 }
545 }
546 else
547 #endif
548 {
549 if (r != re)
550 {
551 const int adv = doAction(r->rule->action, slot, m);
552 if (m.status() != Machine::finished) return;
553 if (r->rule->action->deletes()) fsm.slots.collectGarbage(slot);
554 adjustSlot(adv, slot, fsm.slots);
555 return;
556 }
557 }
558 }
559
560 slot = slot->next();
561 return;
562 }
563
564 #if !defined GRAPHITE2_NTRACING
565
dumpRuleEventConsidered(const FiniteStateMachine & fsm,const RuleEntry & re) const566 void Pass::dumpRuleEventConsidered(const FiniteStateMachine & fsm, const RuleEntry & re) const
567 {
568 *fsm.dbgout << "considered" << json::array;
569 for (const RuleEntry *r = fsm.rules.begin(); r != &re; ++r)
570 {
571 if (r->rule->preContext > fsm.slots.context())
572 continue;
573 *fsm.dbgout << json::flat << json::object
574 << "id" << r->rule - m_rules
575 << "failed" << true
576 << "input" << json::flat << json::object
577 << "start" << objectid(dslot(&fsm.slots.segment, input_slot(fsm.slots, -r->rule->preContext)))
578 << "length" << r->rule->sort
579 << json::close // close "input"
580 << json::close; // close Rule object
581 }
582 }
583
584
dumpRuleEventOutput(const FiniteStateMachine & fsm,const Rule & r,Slot * const last_slot) const585 void Pass::dumpRuleEventOutput(const FiniteStateMachine & fsm, const Rule & r, Slot * const last_slot) const
586 {
587 *fsm.dbgout << json::item << json::flat << json::object
588 << "id" << &r - m_rules
589 << "failed" << false
590 << "input" << json::flat << json::object
591 << "start" << objectid(dslot(&fsm.slots.segment, input_slot(fsm.slots, 0)))
592 << "length" << r.sort - r.preContext
593 << json::close // close "input"
594 << json::close // close Rule object
595 << json::close // close considered array
596 << "output" << json::object
597 << "range" << json::flat << json::object
598 << "start" << objectid(dslot(&fsm.slots.segment, input_slot(fsm.slots, 0)))
599 << "end" << objectid(dslot(&fsm.slots.segment, last_slot))
600 << json::close // close "input"
601 << "slots" << json::array;
602 const Position rsb_prepos = last_slot ? last_slot->origin() : fsm.slots.segment.advance();
603 fsm.slots.segment.positionSlots(0, 0, 0, fsm.slots.segment.currdir());
604
605 for(Slot * slot = output_slot(fsm.slots, 0); slot != last_slot; slot = slot->next())
606 *fsm.dbgout << dslot(&fsm.slots.segment, slot);
607 *fsm.dbgout << json::close // close "slots"
608 << "postshift" << (last_slot ? last_slot->origin() : fsm.slots.segment.advance()) - rsb_prepos
609 << json::close; // close "output" object
610
611 }
612
613 #endif
614
615
616 inline
testPassConstraint(Machine & m) const617 bool Pass::testPassConstraint(Machine & m) const
618 {
619 if (!m_cPConstraint) return true;
620
621 assert(m_cPConstraint.constraint());
622
623 m.slotMap().reset(*m.slotMap().segment.first(), 0);
624 m.slotMap().pushSlot(m.slotMap().segment.first());
625 vm::slotref * map = m.slotMap().begin();
626 const uint32 ret = m_cPConstraint.run(m, map);
627
628 #if !defined GRAPHITE2_NTRACING
629 json * const dbgout = m.slotMap().segment.getFace()->logger();
630 if (dbgout)
631 *dbgout << "constraint" << (ret && m.status() == Machine::finished);
632 #endif
633
634 return ret && m.status() == Machine::finished;
635 }
636
637
testConstraint(const Rule & r,Machine & m) const638 bool Pass::testConstraint(const Rule & r, Machine & m) const
639 {
640 const uint16 curr_context = m.slotMap().context();
641 if (unsigned(r.sort + curr_context - r.preContext) > m.slotMap().size()
642 || curr_context - r.preContext < 0) return false;
643
644 vm::slotref * map = m.slotMap().begin() + curr_context - r.preContext;
645 if (map[r.sort - 1] == 0)
646 return false;
647
648 if (!*r.constraint) return true;
649 assert(r.constraint->constraint());
650 for (int n = r.sort; n && map; --n, ++map)
651 {
652 if (!*map) continue;
653 const int32 ret = r.constraint->run(m, map);
654 if (!ret || m.status() != Machine::finished)
655 return false;
656 }
657
658 return true;
659 }
660
661
collectGarbage(Slot * & aSlot)662 void SlotMap::collectGarbage(Slot * &aSlot)
663 {
664 for(Slot **s = begin(), *const *const se = end() - 1; s != se; ++s) {
665 Slot *& slot = *s;
666 if(slot && (slot->isDeleted() || slot->isCopied()))
667 {
668 if (slot == aSlot)
669 aSlot = slot->prev() ? slot->prev() : slot->next();
670 segment.freeSlot(slot);
671 }
672 }
673 }
674
675
676
doAction(const Code * codeptr,Slot * & slot_out,vm::Machine & m) const677 int Pass::doAction(const Code *codeptr, Slot * & slot_out, vm::Machine & m) const
678 {
679 assert(codeptr);
680 if (!*codeptr) return 0;
681 SlotMap & smap = m.slotMap();
682 vm::slotref * map = &smap[smap.context()];
683 smap.highpassed(false);
684
685 int32 ret = codeptr->run(m, map);
686
687 if (m.status() != Machine::finished)
688 {
689 slot_out = NULL;
690 smap.highwater(0);
691 return 0;
692 }
693
694 slot_out = *map;
695 return ret;
696 }
697
698
adjustSlot(int delta,Slot * & slot_out,SlotMap & smap) const699 void Pass::adjustSlot(int delta, Slot * & slot_out, SlotMap & smap) const
700 {
701 if (!slot_out)
702 {
703 if (smap.highpassed() || slot_out == smap.highwater())
704 {
705 slot_out = smap.segment.last();
706 ++delta;
707 if (!smap.highwater() || smap.highwater() == slot_out)
708 smap.highpassed(false);
709 }
710 else
711 {
712 slot_out = smap.segment.first();
713 --delta;
714 }
715 }
716 if (delta < 0)
717 {
718 while (++delta <= 0 && slot_out)
719 {
720 slot_out = slot_out->prev();
721 if (smap.highpassed() && smap.highwater() == slot_out)
722 smap.highpassed(false);
723 }
724 }
725 else if (delta > 0)
726 {
727 while (--delta >= 0 && slot_out)
728 {
729 if (slot_out == smap.highwater() && slot_out)
730 smap.highpassed(true);
731 slot_out = slot_out->next();
732 }
733 }
734 }
735
collisionShift(Segment * seg,int dir,json * const dbgout) const736 bool Pass::collisionShift(Segment *seg, int dir, json * const dbgout) const
737 {
738 ShiftCollider shiftcoll(dbgout);
739 // bool isfirst = true;
740 bool hasCollisions = false;
741 Slot *start = seg->first(); // turn on collision fixing for the first slot
742 Slot *end = NULL;
743 bool moved = false;
744
745 #if !defined GRAPHITE2_NTRACING
746 if (dbgout)
747 *dbgout << "collisions" << json::array
748 << json::flat << json::object << "num-loops" << m_numCollRuns << json::close;
749 #endif
750
751 while (start)
752 {
753 #if !defined GRAPHITE2_NTRACING
754 if (dbgout) *dbgout << json::object << "phase" << "1" << "moves" << json::array;
755 #endif
756 hasCollisions = false;
757 end = NULL;
758 // phase 1 : position shiftable glyphs, ignoring kernable glyphs
759 for (Slot *s = start; s; s = s->next())
760 {
761 const SlotCollision * c = seg->collisionInfo(s);
762 if (start && (c->flags() & (SlotCollision::COLL_FIX | SlotCollision::COLL_KERN)) == SlotCollision::COLL_FIX
763 && !resolveCollisions(seg, s, start, shiftcoll, false, dir, moved, hasCollisions, dbgout))
764 return false;
765 if (s != start && (c->flags() & SlotCollision::COLL_END))
766 {
767 end = s->next();
768 break;
769 }
770 }
771
772 #if !defined GRAPHITE2_NTRACING
773 if (dbgout)
774 *dbgout << json::close << json::close; // phase-1
775 #endif
776
777 // phase 2 : loop until happy.
778 for (int i = 0; i < m_numCollRuns - 1; ++i)
779 {
780 if (hasCollisions || moved)
781 {
782
783 #if !defined GRAPHITE2_NTRACING
784 if (dbgout)
785 *dbgout << json::object << "phase" << "2a" << "loop" << i << "moves" << json::array;
786 #endif
787 // phase 2a : if any shiftable glyphs are in collision, iterate backwards,
788 // fixing them and ignoring other non-collided glyphs. Note that this handles ONLY
789 // glyphs that are actually in collision from phases 1 or 2b, and working backwards
790 // has the intended effect of breaking logjams.
791 if (hasCollisions)
792 {
793 hasCollisions = false;
794 #if 0
795 moved = true;
796 for (Slot *s = start; s != end; s = s->next())
797 {
798 SlotCollision * c = seg->collisionInfo(s);
799 c->setShift(Position(0, 0));
800 }
801 #endif
802 Slot *lend = end ? end->prev() : seg->last();
803 Slot *lstart = start->prev();
804 for (Slot *s = lend; s != lstart; s = s->prev())
805 {
806 SlotCollision * c = seg->collisionInfo(s);
807 if (start && (c->flags() & (SlotCollision::COLL_FIX | SlotCollision::COLL_KERN | SlotCollision::COLL_ISCOL))
808 == (SlotCollision::COLL_FIX | SlotCollision::COLL_ISCOL)) // ONLY if this glyph is still colliding
809 {
810 if (!resolveCollisions(seg, s, lend, shiftcoll, true, dir, moved, hasCollisions, dbgout))
811 return false;
812 c->setFlags(c->flags() | SlotCollision::COLL_TEMPLOCK);
813 }
814 }
815 }
816
817 #if !defined GRAPHITE2_NTRACING
818 if (dbgout)
819 *dbgout << json::close << json::close // phase 2a
820 << json::object << "phase" << "2b" << "loop" << i << "moves" << json::array;
821 #endif
822
823 // phase 2b : redo basic diacritic positioning pass for ALL glyphs. Each successive loop adjusts
824 // glyphs from their current adjusted position, which has the effect of gradually minimizing the
825 // resulting adjustment; ie, the final result will be gradually closer to the original location.
826 // Also it allows more flexibility in the final adjustment, since it is moving along the
827 // possible 8 vectors from successively different starting locations.
828 if (moved)
829 {
830 moved = false;
831 for (Slot *s = start; s != end; s = s->next())
832 {
833 SlotCollision * c = seg->collisionInfo(s);
834 if (start && (c->flags() & (SlotCollision::COLL_FIX | SlotCollision::COLL_TEMPLOCK
835 | SlotCollision::COLL_KERN)) == SlotCollision::COLL_FIX
836 && !resolveCollisions(seg, s, start, shiftcoll, false, dir, moved, hasCollisions, dbgout))
837 return false;
838 else if (c->flags() & SlotCollision::COLL_TEMPLOCK)
839 c->setFlags(c->flags() & ~SlotCollision::COLL_TEMPLOCK);
840 }
841 }
842 // if (!hasCollisions) // no, don't leave yet because phase 2b will continue to improve things
843 // break;
844 #if !defined GRAPHITE2_NTRACING
845 if (dbgout)
846 *dbgout << json::close << json::close; // phase 2
847 #endif
848 }
849 }
850 if (!end)
851 break;
852 start = NULL;
853 for (Slot *s = end->prev(); s; s = s->next())
854 {
855 if (seg->collisionInfo(s)->flags() & SlotCollision::COLL_START)
856 {
857 start = s;
858 break;
859 }
860 }
861 }
862 return true;
863 }
864
collisionKern(Segment * seg,int dir,json * const dbgout) const865 bool Pass::collisionKern(Segment *seg, int dir, json * const dbgout) const
866 {
867 Slot *start = seg->first();
868 float ymin = 1e38f;
869 float ymax = -1e38f;
870 const GlyphCache &gc = seg->getFace()->glyphs();
871
872 // phase 3 : handle kerning of clusters
873 #if !defined GRAPHITE2_NTRACING
874 if (dbgout)
875 *dbgout << json::object << "phase" << "3" << "moves" << json::array;
876 #endif
877
878 for (Slot *s = seg->first(); s; s = s->next())
879 {
880 if (!gc.check(s->gid()))
881 return false;
882 const SlotCollision * c = seg->collisionInfo(s);
883 const Rect &bbox = seg->theGlyphBBoxTemporary(s->gid());
884 float y = s->origin().y + c->shift().y;
885 if (!(c->flags() & SlotCollision::COLL_ISSPACE))
886 {
887 ymax = max(y + bbox.tr.y, ymax);
888 ymin = min(y + bbox.bl.y, ymin);
889 }
890 if (start && (c->flags() & (SlotCollision::COLL_KERN | SlotCollision::COLL_FIX))
891 == (SlotCollision::COLL_KERN | SlotCollision::COLL_FIX))
892 resolveKern(seg, s, start, dir, ymin, ymax, dbgout);
893 if (c->flags() & SlotCollision::COLL_END)
894 start = NULL;
895 if (c->flags() & SlotCollision::COLL_START)
896 start = s;
897 }
898
899 #if !defined GRAPHITE2_NTRACING
900 if (dbgout)
901 *dbgout << json::close << json::close; // phase 3
902 #endif
903 return true;
904 }
905
collisionFinish(Segment * seg,GR_MAYBE_UNUSED json * const dbgout) const906 bool Pass::collisionFinish(Segment *seg, GR_MAYBE_UNUSED json * const dbgout) const
907 {
908 for (Slot *s = seg->first(); s; s = s->next())
909 {
910 SlotCollision *c = seg->collisionInfo(s);
911 if (c->shift().x != 0 || c->shift().y != 0)
912 {
913 const Position newOffset = c->shift();
914 const Position nullPosition(0, 0);
915 c->setOffset(newOffset + c->offset());
916 c->setShift(nullPosition);
917 }
918 }
919 // seg->positionSlots();
920
921 #if !defined GRAPHITE2_NTRACING
922 if (dbgout)
923 *dbgout << json::close;
924 #endif
925 return true;
926 }
927
928 // Can slot s be kerned, or is it attached to something that can be kerned?
inKernCluster(Segment * seg,Slot * s)929 static bool inKernCluster(Segment *seg, Slot *s)
930 {
931 SlotCollision *c = seg->collisionInfo(s);
932 if (c->flags() & SlotCollision::COLL_KERN /** && c->flags() & SlotCollision::COLL_FIX **/ )
933 return true;
934 while (s->attachedTo())
935 {
936 s = s->attachedTo();
937 c = seg->collisionInfo(s);
938 if (c->flags() & SlotCollision::COLL_KERN /** && c->flags() & SlotCollision::COLL_FIX **/ )
939 return true;
940 }
941 return false;
942 }
943
944 // Fix collisions for the given slot.
945 // Return true if everything was fixed, false if there are still collisions remaining.
946 // isRev means be we are processing backwards.
resolveCollisions(Segment * seg,Slot * slotFix,Slot * start,ShiftCollider & coll,GR_MAYBE_UNUSED bool isRev,int dir,bool & moved,bool & hasCol,json * const dbgout) const947 bool Pass::resolveCollisions(Segment *seg, Slot *slotFix, Slot *start,
948 ShiftCollider &coll, GR_MAYBE_UNUSED bool isRev, int dir, bool &moved, bool &hasCol,
949 json * const dbgout) const
950 {
951 Slot * nbor; // neighboring slot
952 SlotCollision *cFix = seg->collisionInfo(slotFix);
953 if (!coll.initSlot(seg, slotFix, cFix->limit(), cFix->margin(), cFix->marginWt(),
954 cFix->shift(), cFix->offset(), dir, dbgout))
955 return false;
956 bool collides = false;
957 // When we're processing forward, ignore kernable glyphs that preceed the target glyph.
958 // When processing backward, don't ignore these until we pass slotFix.
959 bool ignoreForKern = !isRev;
960 bool rtl = dir & 1;
961 Slot *base = slotFix;
962 while (base->attachedTo())
963 base = base->attachedTo();
964 Position zero(0., 0.);
965
966 // Look for collisions with the neighboring glyphs.
967 for (nbor = start; nbor; nbor = isRev ? nbor->prev() : nbor->next())
968 {
969 SlotCollision *cNbor = seg->collisionInfo(nbor);
970 bool sameCluster = nbor->isChildOf(base);
971 if (nbor != slotFix // don't process if this is the slot of interest
972 && !(cNbor->ignore()) // don't process if ignoring
973 && (nbor == base || sameCluster // process if in the same cluster as slotFix
974 || !inKernCluster(seg, nbor)) // or this cluster is not to be kerned
975 // || (rtl ^ ignoreForKern)) // or it comes before(ltr) or after(rtl)
976 && (!isRev // if processing forwards then good to merge otherwise only:
977 || !(cNbor->flags() & SlotCollision::COLL_FIX) // merge in immovable stuff
978 || ((cNbor->flags() & SlotCollision::COLL_KERN) && !sameCluster) // ignore other kernable clusters
979 || (cNbor->flags() & SlotCollision::COLL_ISCOL)) // test against other collided glyphs
980 && !coll.mergeSlot(seg, nbor, cNbor, cNbor->shift(), !ignoreForKern, sameCluster, collides, false, dbgout))
981 return false;
982 else if (nbor == slotFix)
983 // Switching sides of this glyph - if we were ignoring kernable stuff before, don't anymore.
984 ignoreForKern = !ignoreForKern;
985
986 if (nbor != start && (cNbor->flags() & (isRev ? SlotCollision::COLL_START : SlotCollision::COLL_END)))
987 break;
988 }
989 bool isCol = false;
990 if (collides || cFix->shift().x != 0.f || cFix->shift().y != 0.f)
991 {
992 Position shift = coll.resolve(seg, isCol, dbgout);
993 // isCol has been set to true if a collision remains.
994 if (std::fabs(shift.x) < 1e38f && std::fabs(shift.y) < 1e38f)
995 {
996 if (sqr(shift.x-cFix->shift().x) + sqr(shift.y-cFix->shift().y) >= m_colThreshold * m_colThreshold)
997 moved = true;
998 cFix->setShift(shift);
999 if (slotFix->firstChild())
1000 {
1001 Rect bbox;
1002 Position here = slotFix->origin() + shift;
1003 float clusterMin = here.x;
1004 slotFix->firstChild()->finalise(seg, NULL, here, bbox, 0, clusterMin, rtl, false);
1005 }
1006 }
1007 }
1008 else
1009 {
1010 // This glyph is not colliding with anything.
1011 #if !defined GRAPHITE2_NTRACING
1012 if (dbgout)
1013 {
1014 *dbgout << json::object
1015 << "missed" << objectid(dslot(seg, slotFix));
1016 coll.outputJsonDbg(dbgout, seg, -1);
1017 *dbgout << json::close;
1018 }
1019 #endif
1020 }
1021
1022 // Set the is-collision flag bit.
1023 if (isCol)
1024 { cFix->setFlags(cFix->flags() | SlotCollision::COLL_ISCOL | SlotCollision::COLL_KNOWN); }
1025 else
1026 { cFix->setFlags((cFix->flags() & ~SlotCollision::COLL_ISCOL) | SlotCollision::COLL_KNOWN); }
1027 hasCol |= isCol;
1028 return true;
1029 }
1030
resolveKern(Segment * seg,Slot * slotFix,GR_MAYBE_UNUSED Slot * start,int dir,float & ymin,float & ymax,json * const dbgout) const1031 float Pass::resolveKern(Segment *seg, Slot *slotFix, GR_MAYBE_UNUSED Slot *start, int dir,
1032 float &ymin, float &ymax, json *const dbgout) const
1033 {
1034 Slot *nbor; // neighboring slot
1035 float currSpace = 0.;
1036 bool collides = false;
1037 unsigned int space_count = 0;
1038 Slot *base = slotFix;
1039 while (base->attachedTo())
1040 base = base->attachedTo();
1041 SlotCollision *cFix = seg->collisionInfo(base);
1042 const GlyphCache &gc = seg->getFace()->glyphs();
1043 const Rect &bbb = seg->theGlyphBBoxTemporary(slotFix->gid());
1044 const float by = slotFix->origin().y + cFix->shift().y;
1045
1046 if (base != slotFix)
1047 {
1048 cFix->setFlags(cFix->flags() | SlotCollision::COLL_KERN | SlotCollision::COLL_FIX);
1049 return 0;
1050 }
1051 bool seenEnd = (cFix->flags() & SlotCollision::COLL_END) != 0;
1052 bool isInit = false;
1053 KernCollider coll(dbgout);
1054
1055 ymax = max(by + bbb.tr.y, ymax);
1056 ymin = min(by + bbb.bl.y, ymin);
1057 for (nbor = slotFix->next(); nbor; nbor = nbor->next())
1058 {
1059 if (nbor->isChildOf(base))
1060 continue;
1061 if (!gc.check(nbor->gid()))
1062 return 0.;
1063 const Rect &bb = seg->theGlyphBBoxTemporary(nbor->gid());
1064 SlotCollision *cNbor = seg->collisionInfo(nbor);
1065 if ((bb.bl.y == 0.f && bb.tr.y == 0.f) || (cNbor->flags() & SlotCollision::COLL_ISSPACE))
1066 {
1067 if (m_kernColls == InWord)
1068 break;
1069 // Add space for a space glyph.
1070 currSpace += nbor->advance();
1071 ++space_count;
1072 }
1073 else
1074 {
1075 space_count = 0;
1076 if (nbor != slotFix && !cNbor->ignore())
1077 {
1078 seenEnd = true;
1079 if (!isInit)
1080 {
1081 if (!coll.initSlot(seg, slotFix, cFix->limit(), cFix->margin(),
1082 cFix->shift(), cFix->offset(), dir, ymin, ymax, dbgout))
1083 return 0.;
1084 isInit = true;
1085 }
1086 collides |= coll.mergeSlot(seg, nbor, cNbor->shift(), currSpace, dir, dbgout);
1087 }
1088 }
1089 if (cNbor->flags() & SlotCollision::COLL_END)
1090 {
1091 if (seenEnd && space_count < 2)
1092 break;
1093 else
1094 seenEnd = true;
1095 }
1096 }
1097 if (collides)
1098 {
1099 Position mv = coll.resolve(seg, slotFix, dir, dbgout);
1100 coll.shift(mv, dir);
1101 Position delta = slotFix->advancePos() + mv - cFix->shift();
1102 slotFix->advance(delta);
1103 cFix->setShift(mv);
1104 return mv.x;
1105 }
1106 return 0.;
1107 }
1108