diff options
Diffstat (limited to 'Build/source/libs/graphite/engine-2.3.1/src/segment/GrFSM.h')
-rw-r--r-- | Build/source/libs/graphite/engine-2.3.1/src/segment/GrFSM.h | 245 |
1 files changed, 245 insertions, 0 deletions
diff --git a/Build/source/libs/graphite/engine-2.3.1/src/segment/GrFSM.h b/Build/source/libs/graphite/engine-2.3.1/src/segment/GrFSM.h new file mode 100644 index 00000000000..b1909553daa --- /dev/null +++ b/Build/source/libs/graphite/engine-2.3.1/src/segment/GrFSM.h @@ -0,0 +1,245 @@ +/*--------------------------------------------------------------------*//*:Ignore this sentence. +Copyright (C) 1999, 2001 SIL International. All rights reserved. + +Distributable under the terms of either the Common Public License or the +GNU Lesser General Public License, as specified in the LICENSING.txt file. + +File: GrFSM.h +Responsibility: Sharon Correll +Last reviewed: Not yet. + +Description: + The GrFSM class, which is the mechanism that examines input in a glyph stream and + determines which rule matches and should be run. +----------------------------------------------------------------------------------------------*/ +#ifdef _MSC_VER +#pragma once +#endif +#ifndef FSM_INCLUDED +#define FSM_INCLUDED + +//:End Ignore + +namespace gr +{ + +class GrPass; + +/*---------------------------------------------------------------------------------------------- + A machine class range consists of a range of contiguous glyph IDs that map to + a single column in the FSM (a machine class). (Note that there might be more than one + range mapping to a given column.) + + Keep in mind that these "classes" are completely different from the classes that + are used for substitution. These are used only for matching by the FSM. + + Hungarian: mcr +----------------------------------------------------------------------------------------------*/ +class GrFSMClassRange +{ + friend class GrFSM; + +protected: + gid16 m_chwFirst; // first glyph ID in range + gid16 m_chwLast; // last glyph ID in range + data16 m_col; // column (machine class) to which this range maps +}; + +/*---------------------------------------------------------------------------------------------- + The finite state machine that is used to match sequences of glyphs and + determine which rule to apply. There is one FSM per pass. + + The states in the FSM are grouped and ordered in the following way: + - non-accepting states (no rule completely matched) + - accepting non-final states (a rule matched, but a longer rule is possible) + - final states (a rule matched and no longer rule is possible) + In other words, we have: + - transition, non-accepting + - transition, accepting + - non-transition, accepting + The transition states have information about the next state to transition to; + the accepting states have information about the rule(s) that matched. + + There are three main data structures that are part of the finite state machine: + + (1) the transition matrix: m_prgprgrowXitions. It contains a row for each transition + state (non-accepting states plus accepting non-final states), and a column for each + machine class. The cell values indicate the next state to transition to for the + matched input. A positive number indicates that the next state is a non-accepting state; + a negative value indicates an accepting state. Zero means there is no next state; + no more matches are possible; machine has "jammed." + + (2) the matched-rule list: m_prgrulnMatched. This is a list of rule numbers, + which are indices into the pass's action- and constraint-code arrays. + It contains the numbers of the rules matched by the first accepting state, + followed by those matched by the second accepting state, etc. For each state, + the rules must be ordered using the same order of the rules in the RDL file. + + (3) the matched-rule-offsets list: m_prgirulnMin. This gives the starting index into + the matched-rule list for each accepting state. (Non-accepting states are not included, + so the first item is for state m_crowNonAcpt.) + + In addition, the FSM interacts with the action- and constraint-code lists in the pass + itself. These lists are indexed by rule number (the values of m_prgrulnMatched). + When some input matches the rule, the constraint-code is run; if it succeeds, + the rule number is returned to the caller and that rule is applied (ie, the action-code + is run). + + Hungarian: fsm + + Other hungarian: + row - row (state) + col - column (machine class) + ruln - rule number + + REVIEW: This is quite a time-critical class, and there are two potential optimizations + that have been proposed for the value of a cell: + + (1) use a negative cell number to indicate an accepting state and a positive number + to indicate a non-accepting state. So this gives a comparison with zero rather than + some arbitrary number + + (2) have the positive numbers--the most common case--be the actual byte offset into the + table rather than the row number. This saves matrix multiplication at each step, + ie, "m_prgsnTransitions[(row * m_ccol) + col]". + + The two versions are implemented in RunTransitionTable and RunTransitionTableOptimized. + Do these seem to be worth the inconvenience of added complexity in understanding + and debugging? +----------------------------------------------------------------------------------------------*/ +class GrFSM +{ + friend class FontMemoryUsage; + +public: + GrFSM() : + m_prgirulnMin(NULL), + m_prgrulnMatched(NULL), + m_prgrowTransitions(NULL), + m_prgibStateDebug(NULL), + m_prgmcr(NULL), + m_prgrowStartStates(NULL) + { + } + + ~GrFSM() + { + delete[] m_prgirulnMin; + delete[] m_prgrulnMatched; + + delete[] m_prgrowTransitions; + + delete[] m_prgibStateDebug; + + delete[] m_prgmcr; + + delete[] m_prgrowStartStates; + } + + bool ReadFromFont(GrIStream & grstrm, int fxdVersion); + bool ReadStateTableFromFont(GrIStream & grstrm, int fxdVersion); + + int GetRuleToApply(GrTableManager *, GrPass * ppass, + GrSlotStream * psstrmIn, GrSlotStream * psstrmOut); + + int RunTransitionTable(GrPass * ppass, GrSlotStream * psstrmIn, GrSlotStream * psstrmOut, + int * prgrowAccepting, int * prgcslotMatched); + int RunTransitionTableOptimized(GrSlotStream * psstrmIn, GrSlotStream * psstrmOut, + int * prgrowAccepting, int * prgcslotMatched); + bool RunConstraintAndRecordLog(GrTableManager *, GrPass * ppass, int ruln, + GrSlotStream * psstrmIn, GrSlotStream * psstrmOut, + int cslotPreModContext, int cslotMatched); + + int RunConstraints_Obsolete(GrTableManager *, GrPass * ppass, int row, GrSlotStream * psstrmIn, + int cslotMatched); + + // For sorting matched rules + struct MatchedRule // mr + { + int ruln; + int nSortKey; + int cslot; // number of slots matched AFTER the current stream position + }; + + int MaxRulePreContext() + { + return m_critMaxRulePreContext; + } + +protected: + int FindColumn(gid16 chwGlyphID); +protected: + // Instance variables: + int m_crow; // number of rows (states) + int m_crowFinal; // number of final states; no transitions for these + int m_rowFinalMin; // index of first final row + int m_crowNonAcpt; // number of non-accepting states; no rule indices for these + + int m_ccol; // number of columns (machine classes) + + data16 * m_prgirulnMin; // m_crow-m_crowNonAcpt+1 of these; + // index within m_prgrulnMatched, start of matched + // rules for each accepting state + + data16 * m_prgrulnMatched; // long ordered list of rule indices matched by + // subsequent states; total length is sum of number + // of rules matched for each accepting state + int m_crulnMatched; // needed only for memory instrumentation + + // Transition matrix--for optimized version: +// short ** m_prgprgrowXitions; // ((m_crow-m_crowFinal) * m_ccol) of these; + // positive number indicates + // next state is non-accepting; negative number is + // negative of accepting state. + + // Transition matrix--for current version: + short * m_prgrowTransitions; // ((m_crow-m_crowFinal) * m_ccol) of these + + // debugger string offsets + data16 * m_prgibStateDebug; // for transition states; (m_crow-m_crul+1) of these + + // constants for fast binary search; these are generated by the compiler so that the + // engine doesn't have to take time to do it + data16 m_dimcrInit; // (max power of 2 <= m_cmcr); + // size of initial range to consider + data16 m_cLoop; // log2(max power of 2 <= m_cmcr); + // indicates how many iterations are necessary + data16 m_imcrStart; // m_cmcr - m_dimcrInit; + // where to start search + + int m_cmcr; // number of machine-class-ranges + GrFSMClassRange * m_prgmcr; // array of class ranges; we search these to find the + // mapping to the machine-class-column + + // minimum and maximum number of items in the rule contexts before the first modified + // item. + int m_critMinRulePreContext; + int m_critMaxRulePreContext; + + // start states--row in the FSM to start on depending on how many bogus slots we + // are skipping; (max rule-precontext - min rule-precontext + 1) of these; + // first always = zero + short * m_prgrowStartStates; + +//:Ignore +#if OLD_TEST_STUFF +public: + // For test procedures: + void SetUpSimpleFSMTest(); + void SetUpRuleActionTest(); + void SetUpRuleAction2Test(int); + void SetUpAssocTest(int); + void SetUpAssoc2Test(int); + void SetUpDefaultAssocTest(); + void SetUpFeatureTest(); + void SetUpLigatureTest(int); + void SetUpLigature2Test(int); +#endif // OLD_TEST_STUFF +//:End Ignore + +}; + +} // namespace gr + + +#endif // !FSM_INCLUDED |