diff options
Diffstat (limited to 'Build/source/libs/graphite-engine/src/segment/GrFSM.h')
-rw-r--r-- | Build/source/libs/graphite-engine/src/segment/GrFSM.h | 245 |
1 files changed, 0 insertions, 245 deletions
diff --git a/Build/source/libs/graphite-engine/src/segment/GrFSM.h b/Build/source/libs/graphite-engine/src/segment/GrFSM.h deleted file mode 100644 index b1909553daa..00000000000 --- a/Build/source/libs/graphite-engine/src/segment/GrFSM.h +++ /dev/null @@ -1,245 +0,0 @@ -/*--------------------------------------------------------------------*//*: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 |