Auto status change to "Under Review"
@@ -0,0 +1,127 | |||||
|
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 | } |
@@ -13,7 +13,7 | |||||
13 | <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' "> |
|
13 | <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' "> | |
14 | <DebugSymbols>true</DebugSymbols> |
|
14 | <DebugSymbols>true</DebugSymbols> | |
15 | <DebugType>full</DebugType> |
|
15 | <DebugType>full</DebugType> | |
16 |
<Optimize> |
|
16 | <Optimize>true</Optimize> | |
17 | <OutputPath>bin\Debug</OutputPath> |
|
17 | <OutputPath>bin\Debug</OutputPath> | |
18 | <DefineConstants>TRACE;DEBUG;NET_4_5</DefineConstants> |
|
18 | <DefineConstants>TRACE;DEBUG;NET_4_5</DefineConstants> | |
19 | <ErrorReport>prompt</ErrorReport> |
|
19 | <ErrorReport>prompt</ErrorReport> | |
@@ -31,7 +31,7 | |||||
31 | <ConsolePause>false</ConsolePause> |
|
31 | <ConsolePause>false</ConsolePause> | |
32 | </PropertyGroup> |
|
32 | </PropertyGroup> | |
33 | <PropertyGroup> |
|
33 | <PropertyGroup> | |
34 |
<SignAssembly> |
|
34 | <SignAssembly>false</SignAssembly> | |
35 | </PropertyGroup> |
|
35 | </PropertyGroup> | |
36 | <PropertyGroup> |
|
36 | <PropertyGroup> | |
37 | <AssemblyOriginatorKeyFile>implab.snk</AssemblyOriginatorKeyFile> |
|
37 | <AssemblyOriginatorKeyFile>implab.snk</AssemblyOriginatorKeyFile> |
General Comments 3
ok, latest stable version should be in default
You need to be logged in to leave comments.
Login now