summaryrefslogtreecommitdiff
path: root/Build/source/libs/graphite/engine-2.4/src/segment/GrFSM.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/graphite/engine-2.4/src/segment/GrFSM.cpp')
-rw-r--r--Build/source/libs/graphite/engine-2.4/src/segment/GrFSM.cpp545
1 files changed, 0 insertions, 545 deletions
diff --git a/Build/source/libs/graphite/engine-2.4/src/segment/GrFSM.cpp b/Build/source/libs/graphite/engine-2.4/src/segment/GrFSM.cpp
deleted file mode 100644
index 92424f1feb7..00000000000
--- a/Build/source/libs/graphite/engine-2.4/src/segment/GrFSM.cpp
+++ /dev/null
@@ -1,545 +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.cpp
-Responsibility: Sharon Correll
-Last reviewed: Not yet.
-
-Description:
- Implements the finite state machine.
-----------------------------------------------------------------------------------------------*/
-
-//:>********************************************************************************************
-//:> Include files
-//:>********************************************************************************************
-#include "Main.h"
-#include <cstring>
-#ifdef _MSC_VER
-#pragma hdrstop
-#endif
-// any other headers (not precompiled)
-
-//:End Ignore
-
-//:>********************************************************************************************
-//:> Forward declarations
-//:>********************************************************************************************
-
-//:>********************************************************************************************
-//:> Local Constants and static variables
-//:>********************************************************************************************
-
-namespace gr
-{
-
-//:>********************************************************************************************
-//:> Methods
-//:>********************************************************************************************
-
-/*----------------------------------------------------------------------------------------------
- Fill in the FSM by reading from the font stream.
- Assumes the stream is in the correct position.
-----------------------------------------------------------------------------------------------*/
-bool GrFSM::ReadFromFont(GrIStream & grstrm, int /*fxdVersion*/, int crul, int cbSpace)
-{
- short snTmp;
-
- // number of FSM states
- snTmp = grstrm.ReadShortFromFont();
- m_crow = snTmp;
- // number of transitional states
- snTmp = grstrm.ReadShortFromFont();
- int crowTransitional = snTmp;
- // number of success states
- snTmp = grstrm.ReadShortFromFont();
- int crowSuccess = snTmp;
- m_crowFinal = m_crow - crowTransitional;
- m_crowNonAcpt = m_crow - crowSuccess;
- m_rowFinalMin = crowTransitional;
- // number of columns
- snTmp = grstrm.ReadShortFromFont();
- m_ccol = snTmp;
-
- // Sanity checks.
- // TODO: add a sanity check for m_ccol.
- if (m_crowFinal < 0 || m_crowNonAcpt < 0)
- return false;
-
- // number of FSM glyph ranges and search constants
- snTmp = grstrm.ReadShortFromFont();
- m_cmcr = snTmp;
- if (m_cmcr < 0 || m_cmcr > cbSpace)
- return false;
- snTmp = grstrm.ReadShortFromFont();
- m_dimcrInit = snTmp;
- if (m_dimcrInit > m_cmcr)
- return false;
- snTmp = grstrm.ReadShortFromFont();
- m_cLoop = snTmp;
- if (m_cLoop > m_dimcrInit)
- return false;
- snTmp = grstrm.ReadShortFromFont();
- m_imcrStart = snTmp;
- if (m_imcrStart != m_cmcr - m_dimcrInit)
- return false;
-
- m_prgmcr = new GrFSMClassRange[m_cmcr];
- for (int imcr = 0; imcr < m_cmcr; imcr++)
- {
- m_prgmcr[imcr].m_chwFirst = grstrm.ReadUShortFromFont();
- m_prgmcr[imcr].m_chwLast = grstrm.ReadUShortFromFont();
- m_prgmcr[imcr].m_col = grstrm.ReadUShortFromFont();
- }
-
- // rule map and offsets (extra item at end gives final offset, ie, total)
- m_prgirulnMin = new data16[crowSuccess + 1];
- data16 * pchw = m_prgirulnMin;
- int i;
- for (i = 0; i <= crowSuccess; i++, pchw++)
- {
- *pchw = grstrm.ReadUShortFromFont();
- if (i == 0 && *pchw != 0)
- return false;
- if (i > 0 && *pchw <= *(pchw - 1))
- return false;
- }
-
- // Last offset functions as the total length of the rule list.
- // Note that the number of rules in the map is not necessarily equal to the number of
- // rules in the pass; some rules may be listed multiple times, if they are matched by more
- // than one state.
- int crulInMap = m_prgirulnMin[crowSuccess];
- m_prgrulnMatched = new data16[crulInMap];
- m_crulnMatched = crulInMap;
- pchw = m_prgrulnMatched;
- for (i = 0; i < crulInMap; i++, pchw++)
- {
- *pchw = grstrm.ReadUShortFromFont();
- if (*pchw > crul)
- return false; // bad font
- }
-
- // min rule pre-context number of items
- byte bTmp = grstrm.ReadByteFromFont();
- m_critMinRulePreContext = bTmp;
- if (m_critMinRulePreContext < 0)
- return false;
- // max rule pre-context number of items
- bTmp = grstrm.ReadByteFromFont();
- m_critMaxRulePreContext = bTmp;
- if (m_critMaxRulePreContext < m_critMinRulePreContext)
- return false;
-
- if (m_critMinRulePreContext > kMaxSlotsPerRule || m_critMaxRulePreContext > kMaxSlotsPerRule)
- return false; // bad table
-
- int cStartStates = m_critMaxRulePreContext - m_critMinRulePreContext + 1;
-
- // start states
- m_prgrowStartStates = new short[cStartStates];
- short * psn = m_prgrowStartStates;
- for (int ic = 0; ic < cStartStates; ic++, psn++)
- {
- *psn = grstrm.ReadShortFromFont();
- if (*psn >= m_crow)
- return false; // bad table
- }
-
- return true;
-}
-
-/*----------------------------------------------------------------------------------------------
- Fill in the FSM's state table by reading from the font stream.
- Assumes the stream is in the correct position.
-----------------------------------------------------------------------------------------------*/
-bool GrFSM::ReadStateTableFromFont(GrIStream & grstrm, int /*fxdVersion*/, int /*cbSpace*/)
-{
- int cCells = ((m_crow - m_crowFinal) * m_ccol);
- m_prgrowTransitions = new short[cCells];
- short * psn = m_prgrowTransitions;
- for (int iCell = 0; iCell < cCells; iCell++, psn++)
- {
- *psn = grstrm.ReadShortFromFont();
- if (*psn < 0 || *psn >= m_crow)
- return false;
- }
-
- return true;
-}
-
-/*----------------------------------------------------------------------------------------------
- Use the transition table to find a rule or rules that match; then run the contraint
- code to see if the rule is active. Return the rule number of the rule to be applied.
-
- @param ppass - pass, which knows how to run constraint code
- @param psstrmIn - input stream
- @param psstrmOut - output stream (from which to get recently output slots)
-----------------------------------------------------------------------------------------------*/
-int GrFSM::GetRuleToApply(GrTableManager * ptman, GrPass * ppass,
- GrSlotStream * psstrmIn, GrSlotStream * psstrmOut)
-{
- // List of accepting states and corresponding count of slots that were
- // matched by each.
- int prgrowAccepting[kMaxSlotsPerRule];
- int prgcslotMatched[kMaxSlotsPerRule];
-
- // Run the transition table until it jams.
- int crowAccepting = RunTransitionTable(ppass, psstrmIn, psstrmOut,
- prgrowAccepting, prgcslotMatched);
-
- // Nothing matched; fail quickly.
- if (crowAccepting == 0)
- return -1;
-
- int * prow = prgrowAccepting + crowAccepting - 1;
- int * pcslot = prgcslotMatched + crowAccepting - 1; // # of slots matched AFTER the curr pos
-
- // Quick test for common case of exactly one rule matched.
- if (crowAccepting == 1 &&
- (m_prgirulnMin[*prow - m_crowNonAcpt + 1] - m_prgirulnMin[*prow - m_crowNonAcpt]) == 1)
- {
- int iruln = m_prgirulnMin[*prow - m_crowNonAcpt];
- int ruln = m_prgrulnMatched[iruln];
- if (RunConstraintAndRecordLog(ptman, ppass, ruln, psstrmIn, psstrmOut,
- ppass->PreModContextForRule(ruln), *pcslot))
- {
- return ruln;
- }
- else
- return -1;
- }
-
- // Several rules were matched. We need to sort them and then run the constraints
- // for each rule, accepting the first one whose constraints succeed.
-
- // Count up the number of rules that matched and allocate a buffer of the right size.
- int crulMatched = 0;
- while (prow >= prgrowAccepting)
- {
- crulMatched +=
- m_prgirulnMin[*prow - m_crowNonAcpt + 1] - m_prgirulnMin[*prow - m_crowNonAcpt];
- --prow;
- }
- MatchedRule * prgmr = new MatchedRule[crulMatched];
-
- prow = prgrowAccepting + crowAccepting - 1;
-
- // Do a dumb insertion sort, ordering primarily by sort key (largest first)
- // and secondarily by the order in the original file (rule number).
- // Review: is this kind of sort fast enough? We are assuming that we usually only
- // have a handful of matched rules.
- int cmr = 0;
- while (prow >= prgrowAccepting)
- {
- int iruln = m_prgirulnMin[*prow - m_crowNonAcpt];
- // Get all the rules matches by a single state.
- while (iruln < m_prgirulnMin[*prow - m_crowNonAcpt + 1])
- {
- int ruln = m_prgrulnMatched[iruln];
- int nSortKey = ppass->SortKeyForRule(ruln);
- int cslot = *pcslot;
- int imr;
- for (imr = 0; imr < cmr; imr++)
- {
- if (nSortKey > prgmr[imr].nSortKey ||
- (nSortKey == prgmr[imr].nSortKey && ruln < prgmr[imr].ruln))
- {
- // Insert here.
- memmove(prgmr+imr+1, prgmr+imr, (sizeof(MatchedRule) * (cmr - imr)));
- prgmr[imr].ruln = ruln;
- prgmr[imr].nSortKey = nSortKey;
- prgmr[imr].cslot = cslot;
- break;
- }
- }
- if (imr >= cmr)
- {
- prgmr[cmr].ruln = ruln;
- prgmr[cmr].nSortKey = nSortKey;
- prgmr[cmr].cslot = cslot;
- }
- cmr++;
-
- iruln++;
- }
- --prow;
- --pcslot;
- }
-
-
- for (int imr = 0; imr < cmr; imr++)
- {
- int ruln = prgmr[imr].ruln;
- if (RunConstraintAndRecordLog(ptman, ppass, ruln, psstrmIn, psstrmOut,
- ppass->PreModContextForRule(ruln), prgmr[imr].cslot))
- {
- // Success!
- delete[] prgmr;
- return ruln;
- }
- }
-
- // No rule matched or the constraints failed.
- delete[] prgmr;
- return -1;
-}
-
-/*----------------------------------------------------------------------------------------------
- Run the transition table, generating a list of rows corresponding to accepting states.
-
- @param psstrmIn - input stream
- @param prgrowAccepting - array to fill in with accepting rows
- @param prgcslotMatched - corresponding array with number of slots matched
-----------------------------------------------------------------------------------------------*/
-int GrFSM::RunTransitionTable(GrPass * ppass, GrSlotStream * psstrmIn, GrSlotStream * psstrmOut,
- int * prgrowAccepting, int * prgcslotMatched)
-{
- int ipass = ppass->PassNumber();
-
- // Remember we're reading the pre-context items from the output stream, not the input.
- int cslotPreContextAvail = psstrmOut->WritePos();
-
- if (cslotPreContextAvail < m_critMinRulePreContext)
- return 0; // not enough input to match any rule
-
- // Look backwards by the number of pre-context items for this pass, but not earlier
- // than the beginning of the stream.
- int cslot = -1 * min(cslotPreContextAvail, m_critMaxRulePreContext);
-
- // Normally the start state is state 0. But if we are near the beginning of the stream,
- // we may need to adjust due to the fact that we don't have enough input yet to
- // match the pre-context items in all the rules. So in effect we skip some states
- // corresponding to the earlier items that aren't present.
- int row = m_prgrowStartStates[max(0, m_critMaxRulePreContext - cslotPreContextAvail)];
-
- int * prowTop = prgrowAccepting;
- int * pcslotTop = prgcslotMatched;
- while (true)
- {
- if (row >= m_rowFinalMin)
- // final state--jammed
- return (prowTop - prgrowAccepting);
-
- if (psstrmIn->SlotsPendingInContext() <= cslot)
- // no more input
- return (prowTop - prgrowAccepting);
-
- // Figure out what column the input glyph belong in.
- // Since this is a time-critical routine, we cache the results for the current pass.
- GrSlotState * pslot = (cslot < 0) ?
- psstrmOut->PeekBack(cslot) :
- psstrmIn->Peek(cslot);
- int col;
- if (pslot->PassNumberForColumn() == ipass)
- {
- col = pslot->FsmColumn();
- }
- else
- {
- gid16 chwGlyphID = (cslot < 0) ?
- psstrmOut->PeekBack(cslot)->GlyphID() :
- psstrmIn->Peek(cslot)->GlyphID();
- col = FindColumn(chwGlyphID);
- pslot->CacheFsmColumn(ipass, col);
- }
- int rowNext;
- if (col < 0)
- rowNext = 0;
- else
- rowNext = m_prgrowTransitions[(row * m_ccol) + col];
-
- if (rowNext == 0) // jammed
- return (prowTop - prgrowAccepting);
-
- cslot++;
- if (rowNext >= m_crowNonAcpt) // or (rowNext < 0)
- {
- // Accepting state--push it on the stack.
- //rowNext *= -1;
- gAssert((prowTop - prgrowAccepting) < kMaxSlotsPerRule);
- *prowTop++ = rowNext;
- *pcslotTop++ = cslot;
- }
- row = rowNext;
-
- gAssert((prowTop - prgrowAccepting) == (pcslotTop - prgcslotMatched));
- }
-}
-
-/*----------------------------------------------------------------------------------------------
- Run the transition table, generating a list of rows corresponding to accepting states.
- Optimized to avoid matrix arithmetic for non-accepting states.
-
- Review: do we need to use this version?
-
- @param psstrmIn - input stream
- @param prgrowAccepting - array to fill in with accepting rows
- @param prgcslotMatched - corresponding array with number of slots matched
-----------------------------------------------------------------------------------------------*/
-#if 0
-
-int GrFSM::RunTransitionTableOptimized(GrSlotStream * psstrmIn, GrSlotStream * psstrmOut,
- int * prgrowAccepting, int * prgcslotMatched)
-{
- int cslot = 0;
- int ichwRowOffset = 0;
- int ichwRowOffsetLim = m_crowFinal * m_ccol; // number of cells
- int * prowTop = prgrowAccepting;
- int * pcslotTop = prgcslotMatched;
- while (true)
- {
- if (ichwRowOffset >= ichwRowOffsetLim)
- // final state--jammed
- return (prowTop - prgrowAccepting);
-
- if (psstrmIn->SlotsPendingInContext() < cslot)
- // no more input
- return (prowTop - prgrowAccepting);
-
- gid16 chwGlyphID = psstrmIn->Peek(cslot)->GlyphID();
- int col = FindColumn(chwGlyphID);
- short cellValue = *(m_prgprgrowXitions + ichwRowOffset + col);
-
- if (cellValue == 0) // jammed
- return (prowTop - prgrowAccepting);
-
- cslot++;
- if (cellValue < 0)
- {
- // Accepting state--push it on the stack.
- int rowNext = cellValue * -1;
- gAssert((prowTop - prgrowAccepting) < kMaxSlotsPerRule);
- *prowTop++ = rowNext;
- *pcslotTop++ = cslot;
- ichwRowOffset = rowNext * m_ccol;
- }
- else
- ichwRowOffset = cellValue;
-
- gAssert((prowTop - prgrowAccepting) == (pcslotTop - prgcslotMatched));
- }
-}
-
-#endif // 0
-
-
-/*----------------------------------------------------------------------------------------------
- Run all the constraints for the rules matched by the state that we have reached.
- The rules are ordered as they were in the GDL file. When we hit a constraint that
- matches, return the corresponding rule number. Return -1 if no rule passed.
-
- @param ppass - pass, which knows how to actually run the constraints
- @param psstrmIn - input stream
- @param cslotMatched - number of slots matched; constraints must be run for each of these
-----------------------------------------------------------------------------------------------*/
-//:Ignore
-int GrFSM::RunConstraints_Obsolete(GrTableManager * ptman, GrPass * ppass, int row,
- GrSlotStream * psstrmIn, int cslotMatched)
-{
- int iruln = m_prgirulnMin[row - m_crowNonAcpt];
- while (iruln < m_prgirulnMin[row - m_crowNonAcpt + 1])
- {
- int ruln = m_prgrulnMatched[iruln];
- bool fSuccess = ppass->RunConstraint(ptman, ruln, psstrmIn, NULL, 0, cslotMatched);
- if (fSuccess)
- {
- if (ptman->LoggingTransduction())
- ppass->RecordRuleFired(psstrmIn->ReadPosForNextGet(), ruln);
- return ruln;
- }
- else
- {
- if (ptman->LoggingTransduction())
- ppass->RecordRuleFailed(psstrmIn->ReadPosForNextGet(), ruln);
- }
-
- iruln++;
- }
- return -1; // no rule succeeded
-}
-//:End Ignore
-
-/*----------------------------------------------------------------------------------------------
- Run the constraints for the given rule, and record whether it failed or succeeded in the
- transduction log.
-
- @param ppass - pass, which knows how to actually run the constraints
- @param psstrmIn - input stream
- @param cslotPreModContext - number of slots before the current position that must be tested
- @param islotLimMatched - number of slots matched AFTER the current position
-
- @return True if the constraints succeeded.
-----------------------------------------------------------------------------------------------*/
-bool GrFSM::RunConstraintAndRecordLog(GrTableManager * ptman, GrPass * ppass, int ruln,
- GrSlotStream * psstrmIn, GrSlotStream * psstrmOut,
- int cslotPreModContext, int islotLimMatched)
-{
- bool fSuccess = ppass->RunConstraint(ptman, ruln, psstrmIn, psstrmOut,
- cslotPreModContext, islotLimMatched);
-
- if (ptman->LoggingTransduction())
- {
- if (fSuccess)
- ppass->RecordRuleFired(psstrmIn->ReadPosForNextGet(), ruln);
- else
- ppass->RecordRuleFailed(psstrmIn->ReadPosForNextGet(), ruln);
- }
-
- return fSuccess;
-}
-
-/*----------------------------------------------------------------------------------------------
- Search for the class range containing the glyph ID, and return the matching FSM column.
- Does a fast binary search that uses only shifts, no division.
-----------------------------------------------------------------------------------------------*/
-int GrFSM::FindColumn(gid16 chwGlyphID)
-{
- #ifdef _DEBUG
- // Check that the pre-calculated constants are correct.
- int nPowerOf2 = 1;
- while (nPowerOf2 <= m_cmcr)
- nPowerOf2 <<= 1;
- nPowerOf2 >>= 1;
- // Now nPowerOf2 is the max power of 2 <= m_cclsrg.
- // m_cLoop is not needed for our purposes, but it is included because it is part of
- // the TrueType standard.
- gAssert(1 << m_cLoop == nPowerOf2); // m_cloop == log2(nPowerOf2)
- gAssert(m_dimcrInit == nPowerOf2);
- gAssert(m_imcrStart == m_cmcr - m_dimcrInit);
- #endif
-
- int dimcrCurr = m_dimcrInit;
-
- GrFSMClassRange * pmcrCurr = m_prgmcr + m_imcrStart;
- while (dimcrCurr > 0)
- {
- int nTest;
- if (pmcrCurr < m_prgmcr)
- nTest = -1;
- else
- {
- nTest = pmcrCurr->m_chwFirst - chwGlyphID;
- if (nTest < 0 && chwGlyphID <= pmcrCurr->m_chwLast)
- //nTest = 0;
- // This is a tiny bit more efficient:
- return pmcrCurr->m_col;
- }
-
- if (nTest == 0)
- // found it
- return pmcrCurr->m_col;
-
- dimcrCurr >>= 1; // divide by 2
- if (nTest < 0)
- pmcrCurr += dimcrCurr;
- else // (nTest > 0)
- pmcrCurr -= dimcrCurr;
- }
-
- return -1;
-}
-
-} // namespace gr