blob: be366fcf4e0bac5a25bfaaddfa5f9e1312c8e1a3 [file] [log] [blame]
epoger@google.comec3ed6a2011-07-28 14:26:00 +00001
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 */
reed@android.comf56e2952009-08-29 21:30:25 +00008#include "Forth.h"
reed@android.com19a89f22009-08-30 03:24:51 +00009#include "ForthParser.h"
reed@android.comf56e2952009-08-29 21:30:25 +000010#include "SkTDArray.h"
reed@android.comf56e2952009-08-29 21:30:25 +000011#include "SkString.h"
reed@android.com19a89f22009-08-30 03:24:51 +000012#include "SkTDStack.h"
reed@android.comf56e2952009-08-29 21:30:25 +000013
14ForthEngine::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
21ForthEngine::~ForthEngine() {
22 sk_free(fStackBase);
23}
24
25void ForthEngine::sendOutput(const char text[]) {
26 if (fOutput) {
27 fOutput->show(text);
28 } else {
29 SkDebugf("%s", text);
30 }
31}
32
reed@android.comf56e2952009-08-29 21:30:25 +000033void 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
42intptr_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
52void 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
61intptr_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
73void ForthWord::call(ForthCallBlock* block) {
74 ForthEngine engine(NULL);
reed@android.com19a89f22009-08-30 03:24:51 +000075
76 // setup the initial stack with the callers input data
reed@android.comf56e2952009-08-29 21:30:25 +000077 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 }
reed@android.com19a89f22009-08-30 03:24:51 +000083
84 // now invoke the word
reed@android.comf56e2952009-08-29 21:30:25 +000085 this->exec(&engine);
reed@android.com19a89f22009-08-30 03:24:51 +000086
87 // now copy back the stack into the caller's output data
reed@android.comf56e2952009-08-29 21:30:25 +000088 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
reed@android.comf56e2952009-08-29 21:30:25 +0000102/*
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
116class FCode {
117public:
reed@android.com19a89f22009-08-30 03:24:51 +0000118 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
reed@android.comf56e2952009-08-29 21:30:25 +0000130 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 };
reed@android.com19a89f22009-08-30 03:24:51 +0000136
reed@android.comf56e2952009-08-29 21:30:25 +0000137 enum Code {
reed@android.com19a89f22009-08-30 03:24:51 +0000138 kPushInt_Code, // for data that needs more than 30 bits
139 kIF_Code,
140 kELSE_Code,
reed@android.comf56e2952009-08-29 21:30:25 +0000141 kDone_Code
142 };
reed@android.com19a89f22009-08-30 03:24:51 +0000143 static unsigned MakeCode(Code code) {
144 return (code << kCodeShift) | kCodeShift2_Bits;
145 }
146
reed@android.comf56e2952009-08-29 21:30:25 +0000147 void appendInt(int32_t);
148 void appendWord(ForthWord*);
reed@android.com19a89f22009-08-30 03:24:51 +0000149 void appendIF();
150 bool appendELSE();
151 bool appendTHEN();
reed@android.comf56e2952009-08-29 21:30:25 +0000152 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
165private:
166 SkTDArray<intptr_t> fData;
reed@android.com19a89f22009-08-30 03:24:51 +0000167 SkTDStack<size_t> fIfStack;
reed@android.comf56e2952009-08-29 21:30:25 +0000168};
169
170void FCode::appendInt(int32_t value) {
171 if ((value & 3) == 0) {
172 *fData.append() = value | kDataClear2_Bits;
reed@android.com19a89f22009-08-30 03:24:51 +0000173 } else if ((value << 2 >> 2) == value) {
174 *fData.append() = (value << 2) | kDataShift2_Bits;
reed@android.comf56e2952009-08-29 21:30:25 +0000175 } else {
176 intptr_t* p = fData.append(2);
177 *p++ = (kPushInt_Code << 2) | kCodeShift2_Bits;
178 *p++ = value;
179 }
180}
181
182void FCode::appendWord(ForthWord* word) {
183 SkASSERT((reinterpret_cast<intptr_t>(word) & 3) == 0);
184 *fData.append() = reinterpret_cast<intptr_t>(word);
185}
186
reed@android.com19a89f22009-08-30 03:24:51 +0000187void FCode::appendIF() {
188 size_t ifIndex = fData.count();
189 fIfStack.push(ifIndex);
190 *fData.append() = MakeCode(kIF_Code);
191}
192
193bool 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
210bool 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
reed@android.comf56e2952009-08-29 21:30:25 +0000224void FCode::done() {
225 *fData.append() = (kDone_Code << 2) | kCodeShift2_Bits;
226}
227
228void 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:
reed@android.com19a89f22009-08-30 03:24:51 +0000242 switch (GetCode(c)) {
reed@android.comf56e2952009-08-29 21:30:25 +0000243 case kPushInt_Code:
244 engine->push(*curr++);
245 break;
reed@android.com19a89f22009-08-30 03:24:51 +0000246 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;
reed@android.comf56e2952009-08-29 21:30:25 +0000256 case kDone_Code:
257 return;
258 }
259 break;
260 }
261 }
262}
263
264///////////////////////////////////////////////////////////////////////////////
265
266class CustomWord : public ForthWord {
267public:
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
276private:
277 intptr_t* fCode;
278};
279
280///////////////////////////////////////////////////////////////////////////////
281
reed@android.com19a89f22009-08-30 03:24:51 +0000282ForthParser::ForthParser() : fDict(4096) {
283 this->addStdWords();
284}
reed@android.comf56e2952009-08-29 21:30:25 +0000285
reed@android.com19a89f22009-08-30 03:24:51 +0000286ForthParser::~ForthParser() {
reed@google.com1d5aaa82011-05-31 15:35:54 +0000287 SkTDict<ForthWord*>::Iter iter(fDict);
288 ForthWord* word;
289 while (iter.next(&word)) {
290 delete word;
291 }
reed@android.com19a89f22009-08-30 03:24:51 +0000292}
reed@android.comf56e2952009-08-29 21:30:25 +0000293
294static 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 */
301static bool is_ws(int c) {
302 return c <= ' ';
303}
304
305static 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
322static bool is_digit(int c) { return (unsigned)(c - '0') <= 9; }
323static 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
335static 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
390static 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
400const 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();
reed@android.com19a89f22009-08-30 03:24:51 +0000438 } else if (4 == len && memcmp(token, "ELSE", 4) == 0) {
reed@android.comf56e2952009-08-29 21:30:25 +0000439 if (!code->appendELSE()) {
440 return parse_error("ELSE with no matching IF");
441 }
reed@android.com19a89f22009-08-30 03:24:51 +0000442 } else if (4 == len && memcmp(token, "THEN", 4) == 0) {
reed@android.comf56e2952009-08-29 21:30:25 +0000443 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
461class ForthEnv::Impl {
462public:
463 ForthParser fParser;
464 FCode fBuilder;
465};
466
467ForthEnv::ForthEnv() {
468 fImpl = new Impl;
469}
470
471ForthEnv::~ForthEnv() {
472 delete fImpl;
473}
474
475void ForthEnv::addWord(const char name[], ForthWord* word) {
476 fImpl->fParser.addWord(name, word);
477}
478
479void ForthEnv::parse(const char text[]) {
480 fImpl->fParser.parse(text, &fImpl->fBuilder);
481}
482
483ForthWord* ForthEnv::findWord(const char name[]) {
484 return fImpl->fParser.find(name, strlen(name));
485}
486
487void ForthEnv::run(ForthOutput* output) {
488 ForthEngine engine(output);
489 FCode::Exec(fImpl->fBuilder.begin(), &engine);
490}
491
492#if 0
493void 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
502