OLD | NEW |
| (Empty) |
1 | |
2 /* | |
3 * Copyright 2011 Google Inc. | |
4 * | |
5 * Use of this source code is governed by a BSD-style license that can be | |
6 * found in the LICENSE file. | |
7 */ | |
8 #include "Forth.h" | |
9 #include "ForthParser.h" | |
10 #include "SkTDArray.h" | |
11 #include "SkString.h" | |
12 #include "SkTDStack.h" | |
13 | |
14 ForthEngine::ForthEngine(ForthOutput* output) : fOutput(output) { | |
15 size_t size = 32 * sizeof(intptr_t); | |
16 fStackBase = reinterpret_cast<intptr_t*>(sk_malloc_throw(size)); | |
17 fStackStop = fStackBase + size/sizeof(intptr_t); | |
18 fStackCurr = fStackStop; | |
19 } | |
20 | |
21 ForthEngine::~ForthEngine() { | |
22 sk_free(fStackBase); | |
23 } | |
24 | |
25 void ForthEngine::sendOutput(const char text[]) { | |
26 if (fOutput) { | |
27 fOutput->show(text); | |
28 } else { | |
29 SkDebugf("%s", text); | |
30 } | |
31 } | |
32 | |
33 void ForthEngine::push(intptr_t value) { | |
34 if (fStackCurr > fStackBase) { | |
35 SkASSERT(fStackCurr <= fStackStop && fStackCurr > fStackBase); | |
36 *--fStackCurr = value; | |
37 } else { | |
38 this->signal_error("overflow"); | |
39 } | |
40 } | |
41 | |
42 intptr_t ForthEngine::peek(size_t index) const { | |
43 SkASSERT(fStackCurr < fStackStop && fStackCurr >= fStackBase); | |
44 if (fStackCurr + index < fStackStop) { | |
45 return fStackCurr[index]; | |
46 } else { | |
47 this->signal_error("peek out of range"); | |
48 return 0x80000001; | |
49 } | |
50 } | |
51 | |
52 void ForthEngine::setTop(intptr_t value) { | |
53 if (fStackCurr < fStackStop) { | |
54 SkASSERT(fStackCurr < fStackStop && fStackCurr >= fStackBase); | |
55 *fStackCurr = value; | |
56 } else { | |
57 this->signal_error("underflow"); | |
58 } | |
59 } | |
60 | |
61 intptr_t ForthEngine::pop() { | |
62 if (fStackCurr < fStackStop) { | |
63 SkASSERT(fStackCurr < fStackStop && fStackCurr >= fStackBase); | |
64 return *fStackCurr++; | |
65 } else { | |
66 this->signal_error("underflow"); | |
67 return 0x80000001; | |
68 } | |
69 } | |
70 | |
71 /////////////////////////////////////////////////////////////////////////////// | |
72 | |
73 void ForthWord::call(ForthCallBlock* block) { | |
74 ForthEngine engine(NULL); | |
75 | |
76 // setup the initial stack with the callers input data | |
77 if (block) { | |
78 // walk the array backwards, so that the top of the stack is data[0] | |
79 for (size_t i = 0; i < block->in_count; i++) { | |
80 engine.push(block->in_data[i]); | |
81 } | |
82 } | |
83 | |
84 // now invoke the word | |
85 this->exec(&engine); | |
86 | |
87 // now copy back the stack into the caller's output data | |
88 if (block) { | |
89 size_t n = engine.depth(); | |
90 block->out_depth = n; | |
91 if (n > block->out_count) { | |
92 n = block->out_count; | |
93 } | |
94 for (size_t i = 0; i < n; i++) { | |
95 block->out_data[i] = engine.peek(i); | |
96 } | |
97 } | |
98 } | |
99 | |
100 /////////////////////////////////////////////////////////////////////////////// | |
101 | |
102 /* | |
103 reading an initial 32bit value from the code stream: | |
104 | |
105 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxx00 | |
106 | |
107 Those last two bits are always 0 for a word, so we set those bits for other | |
108 opcodes | |
109 | |
110 00 -- execute this word | |
111 01 -- push (value & ~3) on the data stack | |
112 10 -- push value >> 2 on the data stack (sign extended) | |
113 11 -- switch (value >>> 2) for Code | |
114 */ | |
115 | |
116 class FCode { | |
117 public: | |
118 enum { | |
119 kCodeShift = 2, | |
120 kCodeMask = 7, | |
121 kCodeDataShift = 5 | |
122 }; | |
123 static unsigned GetCode(intptr_t c) { | |
124 return ((uint32_t)c >> kCodeShift) & kCodeMask; | |
125 } | |
126 static unsigned GetCodeData(intptr_t c) { | |
127 return (uint32_t)c >> kCodeDataShift; | |
128 } | |
129 | |
130 enum Bits { | |
131 kWord_Bits = 0, // must be zero for function address | |
132 kDataClear2_Bits = 1, | |
133 kDataShift2_Bits = 2, | |
134 kCodeShift2_Bits = 3 | |
135 }; | |
136 | |
137 enum Code { | |
138 kPushInt_Code, // for data that needs more than 30 bits | |
139 kIF_Code, | |
140 kELSE_Code, | |
141 kDone_Code | |
142 }; | |
143 static unsigned MakeCode(Code code) { | |
144 return (code << kCodeShift) | kCodeShift2_Bits; | |
145 } | |
146 | |
147 void appendInt(int32_t); | |
148 void appendWord(ForthWord*); | |
149 void appendIF(); | |
150 bool appendELSE(); | |
151 bool appendTHEN(); | |
152 void done(); | |
153 | |
154 intptr_t* detach() { | |
155 this->done(); | |
156 return fData.detach(); | |
157 } | |
158 intptr_t* begin() { | |
159 this->done(); | |
160 return fData.begin(); | |
161 } | |
162 | |
163 static void Exec(const intptr_t*, ForthEngine*); | |
164 | |
165 private: | |
166 SkTDArray<intptr_t> fData; | |
167 SkTDStack<size_t> fIfStack; | |
168 }; | |
169 | |
170 void FCode::appendInt(int32_t value) { | |
171 if ((value & 3) == 0) { | |
172 *fData.append() = value | kDataClear2_Bits; | |
173 } else if ((value << 2 >> 2) == value) { | |
174 *fData.append() = (value << 2) | kDataShift2_Bits; | |
175 } else { | |
176 intptr_t* p = fData.append(2); | |
177 *p++ = (kPushInt_Code << 2) | kCodeShift2_Bits; | |
178 *p++ = value; | |
179 } | |
180 } | |
181 | |
182 void FCode::appendWord(ForthWord* word) { | |
183 SkASSERT((reinterpret_cast<intptr_t>(word) & 3) == 0); | |
184 *fData.append() = reinterpret_cast<intptr_t>(word); | |
185 } | |
186 | |
187 void FCode::appendIF() { | |
188 size_t ifIndex = fData.count(); | |
189 fIfStack.push(ifIndex); | |
190 *fData.append() = MakeCode(kIF_Code); | |
191 } | |
192 | |
193 bool FCode::appendELSE() { | |
194 if (fIfStack.empty()) { | |
195 return false; | |
196 } | |
197 | |
198 size_t elseIndex = fData.count(); | |
199 *fData.append() = MakeCode(kELSE_Code); | |
200 | |
201 size_t ifIndex = fIfStack.top(); | |
202 // record the offset in the data part of the if-code | |
203 fData[ifIndex] |= (elseIndex - ifIndex) << kCodeDataShift; | |
204 | |
205 // now reuse this IfStack entry to track the else | |
206 fIfStack.top() = elseIndex; | |
207 return true; | |
208 } | |
209 | |
210 bool FCode::appendTHEN() { | |
211 if (fIfStack.empty()) { | |
212 return false; | |
213 } | |
214 | |
215 // this is either an IF or an ELSE | |
216 size_t index = fIfStack.top(); | |
217 // record the offset in the data part of the code | |
218 fData[index] |= (fData.count() - index - 1) << kCodeDataShift; | |
219 | |
220 fIfStack.pop(); | |
221 return true; | |
222 } | |
223 | |
224 void FCode::done() { | |
225 *fData.append() = (kDone_Code << 2) | kCodeShift2_Bits; | |
226 } | |
227 | |
228 void FCode::Exec(const intptr_t* curr, ForthEngine* engine) { | |
229 for (;;) { | |
230 intptr_t c = *curr++; | |
231 switch (c & 3) { | |
232 case kWord_Bits: | |
233 reinterpret_cast<ForthWord*>(c)->exec(engine); | |
234 break; | |
235 case kDataClear2_Bits: | |
236 engine->push(c & ~3); | |
237 break; | |
238 case kDataShift2_Bits: | |
239 engine->push(c >> 2); | |
240 break; | |
241 case kCodeShift2_Bits: | |
242 switch (GetCode(c)) { | |
243 case kPushInt_Code: | |
244 engine->push(*curr++); | |
245 break; | |
246 case kIF_Code: | |
247 if (!engine->pop()) { | |
248 // takes us past the ELSE or THEN | |
249 curr += GetCodeData(c); | |
250 } | |
251 break; | |
252 case kELSE_Code: | |
253 // takes us past the THEN | |
254 curr += GetCodeData(c); | |
255 break; | |
256 case kDone_Code: | |
257 return; | |
258 } | |
259 break; | |
260 } | |
261 } | |
262 } | |
263 | |
264 /////////////////////////////////////////////////////////////////////////////// | |
265 | |
266 class CustomWord : public ForthWord { | |
267 public: | |
268 // we assume ownership of code[] | |
269 CustomWord(intptr_t code[]) : fCode(code) {} | |
270 virtual ~CustomWord() { sk_free(fCode); } | |
271 | |
272 virtual void exec(ForthEngine* engine) { | |
273 FCode::Exec(fCode, engine); | |
274 } | |
275 | |
276 private: | |
277 intptr_t* fCode; | |
278 }; | |
279 | |
280 /////////////////////////////////////////////////////////////////////////////// | |
281 | |
282 ForthParser::ForthParser() : fDict(4096) { | |
283 this->addStdWords(); | |
284 } | |
285 | |
286 ForthParser::~ForthParser() { | |
287 SkTDict<ForthWord*>::Iter iter(fDict); | |
288 ForthWord* word; | |
289 while (iter.next(&word)) { | |
290 delete word; | |
291 } | |
292 } | |
293 | |
294 static const char* parse_error(const char msg[]) { | |
295 SkDebugf("-- parser error: %s\n", msg); | |
296 return NULL; | |
297 } | |
298 | |
299 /** returns true if c is whitespace, including null | |
300 */ | |
301 static bool is_ws(int c) { | |
302 return c <= ' '; | |
303 } | |
304 | |
305 static const char* parse_token(const char** text, size_t* len) { | |
306 const char* s = *text; | |
307 while (is_ws(*s)) { | |
308 if (0 == *s) { | |
309 return NULL; | |
310 } | |
311 s++; | |
312 } | |
313 const char* token = s++; | |
314 while (!is_ws(*s)) { | |
315 s++; | |
316 } | |
317 *text = s; | |
318 *len = s - token; | |
319 return token; | |
320 } | |
321 | |
322 static bool is_digit(int c) { return (unsigned)(c - '0') <= 9; } | |
323 static int hex_val(int c) { | |
324 if (is_digit(c)) { | |
325 return c - '0'; | |
326 } else { | |
327 if (c <= 'Z') { | |
328 return 10 + c - 'A'; | |
329 } else { | |
330 return 10 + c - 'a'; | |
331 } | |
332 } | |
333 } | |
334 | |
335 static bool parse_num(const char str[], size_t len, int32_t* numBits) { | |
336 if (1 == len && !is_digit(*str)) { | |
337 return false; | |
338 } | |
339 const char* start = str; | |
340 int32_t num = 0; | |
341 bool neg = false; | |
342 if (*str == '-') { | |
343 neg = true; | |
344 str += 1; | |
345 } else if (*str == '#') { | |
346 str++; | |
347 while (str - start < len) { | |
348 num = num*16 + hex_val(*str); | |
349 str += 1; | |
350 } | |
351 *numBits = num; | |
352 return true; | |
353 } | |
354 | |
355 while (is_digit(*str)) { | |
356 num = 10*num + *str - '0'; | |
357 str += 1; | |
358 } | |
359 SkASSERT(str - start <= len); | |
360 if (str - start == len) { | |
361 if (neg) { | |
362 num = -num; | |
363 } | |
364 *numBits = num; | |
365 return true; | |
366 } | |
367 // if we're not done with the token then the next char must be a decimal | |
368 if (*str != '.') { | |
369 return false; | |
370 } | |
371 str += 1; | |
372 float x = num; | |
373 float denom = 1; | |
374 while (str - start < len && is_digit(*str)) { | |
375 x = 10*x + *str - '0'; | |
376 denom *= 10; | |
377 str += 1; | |
378 } | |
379 x /= denom; | |
380 if (str - start == len) { | |
381 if (neg) { | |
382 x = -x; | |
383 } | |
384 *numBits = f2i_bits(x); | |
385 return true; | |
386 } | |
387 return false; | |
388 } | |
389 | |
390 static const char* parse_comment(const char text[]) { | |
391 SkASSERT(*text == '('); | |
392 while (')' != *++text) { | |
393 if (0 == *text) { | |
394 return NULL; | |
395 } | |
396 } | |
397 return text + 1; // skip past the closing ')' | |
398 } | |
399 | |
400 const char* ForthParser::parse(const char text[], FCode* code) { | |
401 for (;;) { | |
402 size_t len; | |
403 const char* token = parse_token(&text, &len); | |
404 if (NULL == token) { | |
405 break; | |
406 } | |
407 if (1 == len) { | |
408 if ('(' == *token) { | |
409 text = parse_comment(token); | |
410 if (NULL == text) { | |
411 return NULL; | |
412 } | |
413 continue; | |
414 } | |
415 if (';' == *token) { | |
416 break; | |
417 } | |
418 if (':' == *token) { | |
419 token = parse_token(&text, &len); | |
420 if (NULL == token) { | |
421 return parse_error("missing name after ':'"); | |
422 } | |
423 FCode subCode; | |
424 text = this->parse(text, &subCode); | |
425 if (NULL == text) { | |
426 return NULL; | |
427 } | |
428 this->add(token, len, new CustomWord(subCode.detach())); | |
429 continue; | |
430 } | |
431 } | |
432 int32_t num; | |
433 if (parse_num(token, len, &num)) { | |
434 // note that num is just the bit representation of the float | |
435 code->appendInt(num); | |
436 } else if (2 == len && memcmp(token, "IF", 2) == 0) { | |
437 code->appendIF(); | |
438 } else if (4 == len && memcmp(token, "ELSE", 4) == 0) { | |
439 if (!code->appendELSE()) { | |
440 return parse_error("ELSE with no matching IF"); | |
441 } | |
442 } else if (4 == len && memcmp(token, "THEN", 4) == 0) { | |
443 if (!code->appendTHEN()) { | |
444 return parse_error("THEN with no matching IF"); | |
445 } | |
446 } else{ | |
447 ForthWord* word = this->find(token, len); | |
448 if (NULL == word) { | |
449 SkString str(token, len); | |
450 str.prepend("unknown word "); | |
451 return parse_error(str.c_str()); | |
452 } | |
453 code->appendWord(word); | |
454 } | |
455 } | |
456 return text; | |
457 } | |
458 | |
459 /////////////////////////////////////////////////////////////////////////////// | |
460 | |
461 class ForthEnv::Impl { | |
462 public: | |
463 ForthParser fParser; | |
464 FCode fBuilder; | |
465 }; | |
466 | |
467 ForthEnv::ForthEnv() { | |
468 fImpl = new Impl; | |
469 } | |
470 | |
471 ForthEnv::~ForthEnv() { | |
472 delete fImpl; | |
473 } | |
474 | |
475 void ForthEnv::addWord(const char name[], ForthWord* word) { | |
476 fImpl->fParser.addWord(name, word); | |
477 } | |
478 | |
479 void ForthEnv::parse(const char text[]) { | |
480 fImpl->fParser.parse(text, &fImpl->fBuilder); | |
481 } | |
482 | |
483 ForthWord* ForthEnv::findWord(const char name[]) { | |
484 return fImpl->fParser.find(name, strlen(name)); | |
485 } | |
486 | |
487 void ForthEnv::run(ForthOutput* output) { | |
488 ForthEngine engine(output); | |
489 FCode::Exec(fImpl->fBuilder.begin(), &engine); | |
490 } | |
491 | |
492 #if 0 | |
493 void ForthEnv::run(const char text[], ForthOutput* output) { | |
494 FCode builder; | |
495 | |
496 if (fImpl->fParser.parse(text, &builder)) { | |
497 ForthEngine engine(output); | |
498 FCode::Exec(builder.begin(), &engine); | |
499 } | |
500 } | |
501 #endif | |
OLD | NEW |