|
237
|
1 using Implab.Automaton;
|
|
|
2 using System;
|
|
|
3 using System.Collections.Generic;
|
|
|
4 using System.Diagnostics;
|
|
|
5 using System.Linq;
|
|
|
6 using System.Runtime.CompilerServices;
|
|
|
7 using System.Text;
|
|
|
8 using System.Threading.Tasks;
|
|
|
9
|
|
|
10 namespace Implab.Formats {
|
|
|
11
|
|
|
12 /// <summary>
|
|
|
13 /// Fast input scanner for max 255 states and first 255 input chacters.
|
|
|
14 /// </summary>
|
|
|
15 /// <typeparam name="TTag"></typeparam>
|
|
|
16 /// <remarks>
|
|
|
17 /// Creates a one rank array to store automa transition table, each entry in this table is byte, to make this table fit into L1 cache.
|
|
|
18 ///
|
|
|
19 /// Each entry is addressed as <c>(state << 8) | input</c> which make this quite fast to get the next state.
|
|
|
20 ///
|
|
|
21 /// Each input symbol below 255 is treated as 255.
|
|
|
22 /// </remarks>
|
|
|
23 public class FastInputScanner<TTag> {
|
|
|
24 const int StateShift = 8;
|
|
|
25 const int StateMask = ~((1 << StateShift) - 1);
|
|
|
26 const int AlphabetSize = 1 << StateShift;
|
|
|
27 const int UnclassifiedInput = (1 << StateShift) - 1;
|
|
|
28 const byte UnreachableState = byte.MaxValue;
|
|
|
29
|
|
|
30 readonly TTag[] m_tags;
|
|
|
31 readonly bool[] m_final;
|
|
|
32
|
|
|
33 readonly byte m_initialState;
|
|
|
34 readonly byte[] m_dfa;
|
|
|
35
|
|
|
36 int m_position;
|
|
|
37 byte m_state;
|
|
|
38
|
|
|
39 protected FastInputScanner(byte[] table, bool[] final, TTag[] tags, byte initial) {
|
|
|
40 m_dfa = table;
|
|
|
41 m_final = final;
|
|
|
42 m_tags = tags;
|
|
|
43 m_initialState = initial;
|
|
|
44 }
|
|
|
45
|
|
|
46 public FastInputScanner(int[,] dfaTable, bool[] finalStates, TTag[] tags, int initialState, int[] inputMap) {
|
|
|
47 var states = dfaTable.GetLength(0);
|
|
|
48 Debug.Assert(states < byte.MaxValue);
|
|
|
49
|
|
|
50 m_dfa = new byte[states << StateShift];
|
|
|
51 m_initialState = (byte)initialState;
|
|
|
52
|
|
|
53 m_tags = tags;
|
|
|
54 m_final = finalStates;
|
|
|
55
|
|
|
56 // iterate over states
|
|
|
57 for(int si = 0; si < states; si++) {
|
|
|
58 // state offset for the new table
|
|
|
59 var offset = si << StateShift;
|
|
|
60
|
|
|
61 // iterate over alphabet
|
|
|
62 for(int a = 0; a < AlphabetSize; a++) {
|
|
|
63 var next = dfaTable[si, a < inputMap.Length ? inputMap[a] : AutomatonConst.UnclassifiedInput];
|
|
|
64 if (next == AutomatonConst.UnreachableState)
|
|
|
65 next = UnreachableState;
|
|
|
66
|
|
|
67 m_dfa[offset | a] = (byte)next;
|
|
|
68 }
|
|
|
69 }
|
|
|
70 }
|
|
|
71
|
|
|
72 public TTag Tag {
|
|
|
73 [MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
|
74 get {
|
|
|
75 return m_tags[m_state];
|
|
|
76 }
|
|
|
77 }
|
|
|
78
|
|
|
79 public int Position {
|
|
|
80 [MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
|
81 get {
|
|
|
82 return m_position;
|
|
|
83 }
|
|
|
84 }
|
|
|
85
|
|
|
86 public bool IsFinal {
|
|
|
87 [MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
|
88 get {
|
|
|
89 return m_final[m_state];
|
|
|
90 }
|
|
|
91 }
|
|
|
92
|
|
|
93 [MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
|
94 public void ResetState() {
|
|
|
95 m_state = m_initialState;
|
|
|
96 }
|
|
|
97
|
|
|
98 public FastInputScanner<TTag> Clone() {
|
|
|
99 var clone = new FastInputScanner<TTag>(m_dfa, m_final, m_tags, m_initialState);
|
|
|
100 clone.m_state = m_state;
|
|
|
101 clone.m_position = m_position;
|
|
|
102 return clone;
|
|
|
103 }
|
|
|
104
|
|
|
105 public bool Scan(char[] data, int offset, int max) {
|
|
|
106 var next = m_state;
|
|
|
107
|
|
|
108 m_position = offset;
|
|
|
109 while (m_position < max) {
|
|
|
110 var ch = data[m_position];
|
|
|
111
|
|
|
112 next = m_dfa[(ch >= AlphabetSize ? (next << StateShift) | UnclassifiedInput : (next << StateShift) | ch)];
|
|
|
113
|
|
|
114 if (next == UnreachableState)
|
|
|
115 // scanner stops at the next position after the last recognized symbol
|
|
|
116 return false;
|
|
|
117
|
|
|
118 m_state = next;
|
|
|
119 m_position++;
|
|
|
120 }
|
|
|
121
|
|
|
122 return true;
|
|
|
123 }
|
|
|
124
|
|
|
125
|
|
|
126 }
|
|
|
127 }
|
