1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
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
|
