1 #include <u.h>
2 #include <libc.h>
3 #include "debug.h"
4 #include "tap.h"
5
6
7 static stdebug = 1;
8
9 /*
10 !8c -FVw tap.c
11 !8l -o tap tap.8
12 !tap > /tmp/l
13 */
14
15 static char *stnames[] = {
16 [TapReset] "TapReset",
17 [TapIdle] "TapIdle",
18 [TapSelDR] "TapSelDR",
19 [TapCaptureDR] "TapCaptureDR" ,
20 [TapShiftDR] "TapShiftDR",
21 [TapExit1DR] "TapExit1DR",
22 [TapPauseDR] "TapPauseDR",
23 [TapExit2DR] "TapExit2DR",
24 [TapUpdateDR] "TapUpdateDR",
25 [TapSelIR] "TapSelIR",
26 [TapCaptureIR] "TapCaptureIR",
27 [TapShiftIR] "TapShiftIR",
28 [TapExit1IR] "TapExit1IR",
29 [TapPauseIR] "TapPauseIR",
30 [TapExit2IR] "TapExit2IR",
31 [TapUpdateIR] "TapUpdateIR",
32 [NStates] "",
33 [TapUnknown] "TapUnknown",
34 };
35
36 typedef struct TapState TapState;
37 struct TapState {
38 int next[2];
39 };
40
41
42 static TapState sm[] = {
43 [TapReset] {TapIdle, TapReset},
44 [TapIdle] {TapIdle, TapSelDR},
45 [TapSelDR] {TapCaptureDR, TapSelIR},
46 [TapCaptureDR] {TapShiftDR, TapExit1DR},
47 [TapShiftDR] {TapShiftDR, TapExit1DR,},
48 [TapExit1DR] {TapPauseDR, TapUpdateDR},
49 [TapPauseDR] {TapPauseDR, TapExit2DR},
50 [TapExit2DR] {TapShiftDR, TapUpdateDR},
51 [TapUpdateDR] {TapIdle, TapSelDR},
52 [TapSelIR] {TapCaptureIR, TapReset},
53 [TapCaptureIR] {TapShiftIR, TapExit1IR},
54 [TapShiftIR] {TapShiftIR, TapExit1IR},
55 [TapExit1IR] {TapPauseIR, TapUpdateIR},
56 [TapPauseIR] {TapPauseIR, TapExit2IR},
57 [TapExit2IR] {TapShiftIR, TapUpdateIR},
58 [TapUpdateIR] {TapIdle, TapSelDR},
59 };
60
61 static int state=TapReset;
62
63 static int
isvalidst(int state)64 isvalidst(int state)
65 {
66 if(state < 0 || state >= NStates && state != TapUnknown){
67 fprint(2, "invalid state: %d\n", state);
68 return 0;
69 }
70 return 1;
71 }
72
73 static int
tapsmmove(int state,int tms)74 tapsmmove(int state, int tms)
75 {
76 assert(tms == 0 || tms == 1);
77
78 state = sm[state].next[tms];
79
80 return state;
81 }
82
83 /*
84 * To find the shortest path from here to a state
85 * go in parallel through all neighbour states till I find it
86 * with memoization of advancing passed states
87 * (Breadth First Search)
88 * (all paths weight the same, simple topology)
89 * could probably use this to generate a lookup table
90 * but all time is spent waiting for usb anyway
91 */
92
93 static void
movepath(SmPath * path,int tms,int newst)94 movepath(SmPath *path, int tms, int newst)
95 {
96 path->st = newst;
97 path->ptmslen++;
98 path->ptms <<= 1;
99 path->ptms |= tms;
100 }
101
102
103 static SmPath
findpath(int origin,int dest)104 findpath(int origin, int dest)
105 {
106 int np, memost, tms, nc, i, j, ip, st;
107 SmPath paths[NStates], nextp, newp;
108
109 memset(paths, 0, sizeof(SmPath));
110 paths[0].st = origin;
111 np = 1;
112 memost = 0;
113 if(origin == dest)
114 return *paths;
115
116 for(i = 0; i < NStates; i++){
117 for(j = 0; j < np; j++){
118 nc = 0;
119 nextp = paths[j];
120 for(tms = 0; tms < 2; tms++){
121 newp = nextp;
122 st = tapsmmove(newp.st, tms);
123 if((1 << st) & memost){
124 if(++nc == 2) /*trapped state kill*/
125 paths[j] = paths[--np];
126 continue;
127 }
128 movepath(&newp, tms, st);
129 memost |= 1 << newp.st;
130
131 if(newp.st == dest)
132 return newp;
133 if(tms == 0)
134 ip = j;
135 else
136 ip = np++;
137 paths[ip] = newp;
138
139 }
140 }
141 }
142 fprint(2, "should not come through here\n");
143 newp.st = -1;
144 return newp;
145 }
146
147
148 static void
concatpath(SmPath * p1,SmPath * p2)149 concatpath(SmPath *p1, SmPath *p2)
150 {
151 ulong msk;
152 assert(p1->ptmslen < 8*sizeof(p1->ptms));
153
154 msk = (1 << p2->ptmslen)-1;
155 p1->ptms = (p1->ptms << p2->ptmslen)|(p2->ptms & msk);
156 p1->ptmslen += p2->ptmslen;
157 p1->st = p2->st;
158 }
159
160 static void
dumppath(SmPath * pth)161 dumppath(SmPath *pth)
162 {
163 uchar frstbit;
164 int i;
165
166 fprint(2, "\n(");
167 for(i = 0; i < pth->ptmslen; i++){
168 frstbit = (pth->ptms >> (pth->ptmslen-i-1))&1;
169 fprint(2, "tms[%d] = %ud ", i, frstbit);
170 }
171 fprint(2, ")\n");
172 }
173
174 SmPath
pathto(TapSm * sm,int dest)175 pathto(TapSm *sm, int dest)
176 {
177 SmPath pth1, pth2;
178
179 if(!isvalidst(sm->state) || !isvalidst(dest))
180 sysfatal("invalid state");
181 dprint(DState, "pathto: %s -> %s\n",
182 stnames[sm->state], stnames[dest]);
183 if(sm->state == TapUnknown){
184 pth1.ptmslen = 5; /* resynch */
185 pth1.ptms = 0x1f;
186 pth2 = findpath(TapReset, dest);
187
188 concatpath(&pth1, &pth2);
189 if(debug[DPath])
190 dumppath(&pth1);
191 return pth1;
192 }
193 pth1 = findpath(sm->state, dest);
194 if(debug[DPath])
195 dumppath(&pth1);
196 return pth1;
197 }
198
199 void
moveto(TapSm * sm,int dest)200 moveto(TapSm *sm, int dest)
201 {
202 dprint(DState, "moveto: %s -> %s\n",
203 stnames[sm->state], stnames[dest]);
204 sm->state = dest;
205 }
206
207 static ulong
pathpref(SmPath * pth,int nbits)208 pathpref(SmPath *pth, int nbits)
209 {
210 ulong msk;
211 assert(pth->ptmslen >= nbits);
212
213 msk = (1 << nbits)-1;
214 return msk & (pth->ptms >> (pth->ptmslen - nbits));
215 }
216
217 SmPath
takepathpref(SmPath * pth,int nbits)218 takepathpref(SmPath *pth, int nbits)
219 {
220 SmPath pref;
221
222 pref.ptmslen = 0;
223 if(pth->ptmslen == 0)
224 return pref;
225 if(nbits > pth->ptmslen)
226 nbits = pth->ptmslen;
227 pref.ptmslen = nbits;
228 pref.ptms = pathpref(pth, nbits);
229 pth->ptmslen -= nbits;
230 return pref;
231 }
232
233 /*
234 * Testing
235
236 void
237 main(int, char *[])
238 {
239 SmPath pth;
240 TapSm sm;
241 int orig, dest;
242
243 orig = TapReset;
244 dest = TapExit2DR;
245
246 print("origin %s dest %s\n", stnames[orig], stnames[dest]);
247 pth = findpath(orig, dest);
248 print("\n");
249 dumppath(&pth);
250 orig = TapShiftIR;
251 dest = TapExit2DR;
252
253 print("origin %s dest %s\n", stnames[orig], stnames[dest]);
254 pth = findpath(orig, dest);
255 print("\n");
256 dumppath(&pth);
257 orig = TapIdle;
258 dest = TapExit2IR;
259
260 print("origin %s dest %s\n", stnames[orig], stnames[dest]);
261 pth = findpath(orig, dest);
262 print("\n");
263 dumppath(&pth);
264 sm.state = TapUnknown;
265 pth = pathto(&sm, TapExit2DR);
266 dumppath(&pth);
267
268 }
269 */
270