experimental hack to write a forth engine to drive skia
git-svn-id: http://skia.googlecode.com/svn/trunk@343 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/forth/Forth.cpp b/forth/Forth.cpp
new file mode 100644
index 0000000..722ed08
--- /dev/null
+++ b/forth/Forth.cpp
@@ -0,0 +1,682 @@
+#include "Forth.h"
+#include "SkTDArray.h"
+#include "SkTDict.h"
+#include "SkString.h"
+
+ForthEngine::ForthEngine(ForthOutput* output) : fOutput(output) {
+ size_t size = 32 * sizeof(intptr_t);
+ fStackBase = reinterpret_cast<intptr_t*>(sk_malloc_throw(size));
+ fStackStop = fStackBase + size/sizeof(intptr_t);
+ fStackCurr = fStackStop;
+}
+
+ForthEngine::~ForthEngine() {
+ sk_free(fStackBase);
+}
+
+void ForthEngine::sendOutput(const char text[]) {
+ if (fOutput) {
+ fOutput->show(text);
+ } else {
+ SkDebugf("%s", text);
+ }
+}
+
+///////////////// ints
+
+void ForthEngine::push(intptr_t value) {
+ if (fStackCurr > fStackBase) {
+ SkASSERT(fStackCurr <= fStackStop && fStackCurr > fStackBase);
+ *--fStackCurr = value;
+ } else {
+ this->signal_error("overflow");
+ }
+}
+
+intptr_t ForthEngine::peek(size_t index) const {
+ SkASSERT(fStackCurr < fStackStop && fStackCurr >= fStackBase);
+ if (fStackCurr + index < fStackStop) {
+ return fStackCurr[index];
+ } else {
+ this->signal_error("peek out of range");
+ return 0x80000001;
+ }
+}
+
+void ForthEngine::setTop(intptr_t value) {
+ if (fStackCurr < fStackStop) {
+ SkASSERT(fStackCurr < fStackStop && fStackCurr >= fStackBase);
+ *fStackCurr = value;
+ } else {
+ this->signal_error("underflow");
+ }
+}
+
+intptr_t ForthEngine::pop() {
+ if (fStackCurr < fStackStop) {
+ SkASSERT(fStackCurr < fStackStop && fStackCurr >= fStackBase);
+ return *fStackCurr++;
+ } else {
+ this->signal_error("underflow");
+ return 0x80000001;
+ }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+void ForthWord::call(ForthCallBlock* block) {
+ ForthEngine engine(NULL);
+ if (block) {
+ // walk the array backwards, so that the top of the stack is data[0]
+ for (size_t i = 0; i < block->in_count; i++) {
+ engine.push(block->in_data[i]);
+ }
+ }
+ this->exec(&engine);
+ if (block) {
+ size_t n = engine.depth();
+ block->out_depth = n;
+ if (n > block->out_count) {
+ n = block->out_count;
+ }
+ for (size_t i = 0; i < n; i++) {
+ block->out_data[i] = engine.peek(i);
+ }
+ }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+class drop_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ (void)fe->pop();
+ }
+};
+
+class clearStack_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ fe->clearStack();
+ }
+};
+
+class dup_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ fe->push(fe->top());
+ }
+};
+
+class swap_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ int32_t a = fe->pop();
+ int32_t b = fe->top();
+ fe->setTop(a);
+ fe->push(b);
+ }
+};
+
+///////////////// ints
+
+class add_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ intptr_t tmp = fe->pop();
+ fe->setTop(fe->top() + tmp);
+ }
+};
+
+class sub_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ intptr_t tmp = fe->pop();
+ fe->setTop(fe->top() - tmp);
+ }
+};
+
+class mul_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ intptr_t tmp = fe->pop();
+ fe->setTop(fe->top() * tmp);
+ }
+};
+
+class div_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ intptr_t tmp = fe->pop();
+ fe->setTop(fe->top() / tmp);
+ }
+};
+
+class dot_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ SkString str;
+ str.printf("%d ", fe->pop());
+ fe->sendOutput(str.c_str());
+ }
+};
+
+class abs_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ int32_t value = fe->top();
+ if (value < 0) {
+ fe->setTop(-value);
+ }
+ }
+};
+
+class min_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ int32_t value = fe->pop();
+ if (value < fe->top()) {
+ fe->setTop(value);
+ }
+ }
+};
+
+class max_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ int32_t value = fe->pop();
+ if (value > fe->top()) {
+ fe->setTop(value);
+ }
+ }
+};
+
+///////////////// floats
+
+class fadd_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ float tmp = fe->fpop();
+ fe->fsetTop(fe->ftop() + tmp);
+ }
+};
+
+class fsub_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ float tmp = fe->fpop();
+ fe->fsetTop(fe->ftop() - tmp);
+ }
+};
+
+class fmul_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ float tmp = fe->fpop();
+ fe->fsetTop(fe->ftop() * tmp);
+ }
+};
+
+class fdiv_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ float tmp = fe->fpop();
+ fe->fsetTop(fe->ftop() / tmp);
+ }
+};
+
+class fdot_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ SkString str;
+ str.printf("%g ", fe->fpop());
+ fe->sendOutput(str.c_str());
+ }
+};
+
+class fabs_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ float value = fe->ftop();
+ if (value < 0) {
+ fe->fsetTop(-value);
+ }
+ }
+};
+
+class fmin_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ float value = fe->fpop();
+ if (value < fe->ftop()) {
+ fe->fsetTop(value);
+ }
+ }
+};
+
+class fmax_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ float value = fe->fpop();
+ if (value > fe->ftop()) {
+ fe->fsetTop(value);
+ }
+ }
+};
+
+class floor_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ fe->fsetTop(floorf(fe->ftop()));
+ }
+};
+
+class ceil_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ fe->fsetTop(ceilf(fe->ftop()));
+ }
+};
+
+class round_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ fe->fsetTop(floorf(fe->ftop() + 0.5f));
+ }
+};
+
+class f2i_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ fe->setTop((int)fe->ftop());
+ }
+};
+
+class i2f_ForthWord : public ForthWord {
+public:
+ virtual void exec(ForthEngine* fe) {
+ fe->fsetTop((float)fe->top());
+ }
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+/*
+ reading an initial 32bit value from the code stream:
+
+ xxxxxxxx xxxxxxxx xxxxxxxx xxxxxx00
+
+ Those last two bits are always 0 for a word, so we set those bits for other
+ opcodes
+
+ 00 -- execute this word
+ 01 -- push (value & ~3) on the data stack
+ 10 -- push value >> 2 on the data stack (sign extended)
+ 11 -- switch (value >>> 2) for Code
+ */
+
+class FCode {
+public:
+ enum Bits {
+ kWord_Bits = 0, // must be zero for function address
+ kDataClear2_Bits = 1,
+ kDataShift2_Bits = 2,
+ kCodeShift2_Bits = 3
+ };
+ enum Code {
+ kPushInt_Code,
+ kDone_Code
+ };
+
+ void appendInt(int32_t);
+ void appendWord(ForthWord*);
+ void appendIF() {}
+ bool appendELSE() { return false; }
+ bool appendTHEN() { return false; }
+ void done();
+
+ intptr_t* detach() {
+ this->done();
+ return fData.detach();
+ }
+ intptr_t* begin() {
+ this->done();
+ return fData.begin();
+ }
+
+ static void Exec(const intptr_t*, ForthEngine*);
+
+private:
+ SkTDArray<intptr_t> fData;
+};
+
+void FCode::appendInt(int32_t value) {
+ if ((value & 3) == 0) {
+ *fData.append() = value | kDataClear2_Bits;
+ } else if ((value >> 2 << 2) == value) {
+ *fData.append() = value | kDataShift2_Bits;
+ } else {
+ intptr_t* p = fData.append(2);
+ *p++ = (kPushInt_Code << 2) | kCodeShift2_Bits;
+ *p++ = value;
+ }
+}
+
+void FCode::appendWord(ForthWord* word) {
+ SkASSERT((reinterpret_cast<intptr_t>(word) & 3) == 0);
+ *fData.append() = reinterpret_cast<intptr_t>(word);
+}
+
+void FCode::done() {
+ *fData.append() = (kDone_Code << 2) | kCodeShift2_Bits;
+}
+
+void FCode::Exec(const intptr_t* curr, ForthEngine* engine) {
+ for (;;) {
+ intptr_t c = *curr++;
+ switch (c & 3) {
+ case kWord_Bits:
+ reinterpret_cast<ForthWord*>(c)->exec(engine);
+ break;
+ case kDataClear2_Bits:
+ engine->push(c & ~3);
+ break;
+ case kDataShift2_Bits:
+ engine->push(c >> 2);
+ break;
+ case kCodeShift2_Bits:
+ switch ((uint32_t)c >> 2) {
+ case kPushInt_Code:
+ engine->push(*curr++);
+ break;
+ case kDone_Code:
+ return;
+ }
+ break;
+ }
+ }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+class CustomWord : public ForthWord {
+public:
+ // we assume ownership of code[]
+ CustomWord(intptr_t code[]) : fCode(code) {}
+ virtual ~CustomWord() { sk_free(fCode); }
+
+ virtual void exec(ForthEngine* engine) {
+ FCode::Exec(fCode, engine);
+ }
+
+private:
+ intptr_t* fCode;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+class ForthParser {
+public:
+ ForthParser() : fDict(4096) {
+ this->addStdWords();
+ }
+
+ const char* parse(const char text[], FCode*);
+
+ void addWord(const char name[], ForthWord* word) {
+ this->add(name, strlen(name), word);
+ }
+
+ ForthWord* find(const char name[], size_t len) const {
+ ForthWord* word;
+ return fDict.find(name, len, &word) ? word : NULL;
+ }
+
+private:
+ void add(const char name[], size_t len, ForthWord* word) {
+ (void)fDict.set(name, len, word);
+ }
+
+ void addStdWords() {
+ this->add("clr", 3, new clearStack_ForthWord);
+ this->add("drop", 4, new drop_ForthWord);
+ this->add("dup", 3, new dup_ForthWord);
+ this->add("swap", 4, new swap_ForthWord);
+
+ this->add("+", 1, new add_ForthWord);
+ this->add("-", 1, new sub_ForthWord);
+ this->add("*", 1, new mul_ForthWord);
+ this->add("/", 1, new div_ForthWord);
+ this->add(".", 1, new dot_ForthWord);
+ this->add("abs", 3, new abs_ForthWord);
+ this->add("min", 3, new min_ForthWord);
+ this->add("max", 3, new max_ForthWord);
+
+ this->add("f+", 2, new fadd_ForthWord);
+ this->add("f-", 2, new fsub_ForthWord);
+ this->add("f*", 2, new fmul_ForthWord);
+ this->add("f/", 2, new fdiv_ForthWord);
+ this->add("f.", 2, new fdot_ForthWord);
+ this->add("fabs", 4, new fabs_ForthWord);
+ this->add("fmin", 4, new fmin_ForthWord);
+ this->add("fmax", 4, new fmax_ForthWord);
+ this->add("fmax", 4, new fmax_ForthWord);
+ this->add("floor", 5, new floor_ForthWord);
+ this->add("ceil", 4, new ceil_ForthWord);
+ this->add("round", 5, new round_ForthWord);
+ this->add("f>i", 3, new f2i_ForthWord);
+ this->add("i>f", 3, new i2f_ForthWord);
+ }
+
+ SkTDict<ForthWord*> fDict;
+};
+
+static const char* parse_error(const char msg[]) {
+ SkDebugf("-- parser error: %s\n", msg);
+ return NULL;
+}
+
+/** returns true if c is whitespace, including null
+ */
+static bool is_ws(int c) {
+ return c <= ' ';
+}
+
+static const char* parse_token(const char** text, size_t* len) {
+ const char* s = *text;
+ while (is_ws(*s)) {
+ if (0 == *s) {
+ return NULL;
+ }
+ s++;
+ }
+ const char* token = s++;
+ while (!is_ws(*s)) {
+ s++;
+ }
+ *text = s;
+ *len = s - token;
+ return token;
+}
+
+static bool is_digit(int c) { return (unsigned)(c - '0') <= 9; }
+static int hex_val(int c) {
+ if (is_digit(c)) {
+ return c - '0';
+ } else {
+ if (c <= 'Z') {
+ return 10 + c - 'A';
+ } else {
+ return 10 + c - 'a';
+ }
+ }
+}
+
+static bool parse_num(const char str[], size_t len, int32_t* numBits) {
+ if (1 == len && !is_digit(*str)) {
+ return false;
+ }
+ const char* start = str;
+ int32_t num = 0;
+ bool neg = false;
+ if (*str == '-') {
+ neg = true;
+ str += 1;
+ } else if (*str == '#') {
+ str++;
+ while (str - start < len) {
+ num = num*16 + hex_val(*str);
+ str += 1;
+ }
+ *numBits = num;
+ return true;
+ }
+
+ while (is_digit(*str)) {
+ num = 10*num + *str - '0';
+ str += 1;
+ }
+ SkASSERT(str - start <= len);
+ if (str - start == len) {
+ if (neg) {
+ num = -num;
+ }
+ *numBits = num;
+ return true;
+ }
+ // if we're not done with the token then the next char must be a decimal
+ if (*str != '.') {
+ return false;
+ }
+ str += 1;
+ float x = num;
+ float denom = 1;
+ while (str - start < len && is_digit(*str)) {
+ x = 10*x + *str - '0';
+ denom *= 10;
+ str += 1;
+ }
+ x /= denom;
+ if (str - start == len) {
+ if (neg) {
+ x = -x;
+ }
+ *numBits = f2i_bits(x);
+ return true;
+ }
+ return false;
+}
+
+static const char* parse_comment(const char text[]) {
+ SkASSERT(*text == '(');
+ while (')' != *++text) {
+ if (0 == *text) {
+ return NULL;
+ }
+ }
+ return text + 1; // skip past the closing ')'
+}
+
+const char* ForthParser::parse(const char text[], FCode* code) {
+ for (;;) {
+ size_t len;
+ const char* token = parse_token(&text, &len);
+ if (NULL == token) {
+ break;
+ }
+ if (1 == len) {
+ if ('(' == *token) {
+ text = parse_comment(token);
+ if (NULL == text) {
+ return NULL;
+ }
+ continue;
+ }
+ if (';' == *token) {
+ break;
+ }
+ if (':' == *token) {
+ token = parse_token(&text, &len);
+ if (NULL == token) {
+ return parse_error("missing name after ':'");
+ }
+ FCode subCode;
+ text = this->parse(text, &subCode);
+ if (NULL == text) {
+ return NULL;
+ }
+ this->add(token, len, new CustomWord(subCode.detach()));
+ continue;
+ }
+ }
+ int32_t num;
+ if (parse_num(token, len, &num)) {
+ // note that num is just the bit representation of the float
+ code->appendInt(num);
+ } else if (2 == len && memcmp(token, "IF", 2) == 0) {
+ code->appendIF();
+ } else if (2 == len && memcmp(token, "ELSE", 4) == 0) {
+ if (!code->appendELSE()) {
+ return parse_error("ELSE with no matching IF");
+ }
+ } else if (2 == len && memcmp(token, "THEN", 4) == 0) {
+ if (!code->appendTHEN()) {
+ return parse_error("THEN with no matching IF");
+ }
+ } else{
+ ForthWord* word = this->find(token, len);
+ if (NULL == word) {
+ SkString str(token, len);
+ str.prepend("unknown word ");
+ return parse_error(str.c_str());
+ }
+ code->appendWord(word);
+ }
+ }
+ return text;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+class ForthEnv::Impl {
+public:
+ ForthParser fParser;
+ FCode fBuilder;
+};
+
+ForthEnv::ForthEnv() {
+ fImpl = new Impl;
+}
+
+ForthEnv::~ForthEnv() {
+ delete fImpl;
+}
+
+void ForthEnv::addWord(const char name[], ForthWord* word) {
+ fImpl->fParser.addWord(name, word);
+}
+
+void ForthEnv::parse(const char text[]) {
+ fImpl->fParser.parse(text, &fImpl->fBuilder);
+}
+
+ForthWord* ForthEnv::findWord(const char name[]) {
+ return fImpl->fParser.find(name, strlen(name));
+}
+
+void ForthEnv::run(ForthOutput* output) {
+ ForthEngine engine(output);
+ FCode::Exec(fImpl->fBuilder.begin(), &engine);
+}
+
+#if 0
+void ForthEnv::run(const char text[], ForthOutput* output) {
+ FCode builder;
+
+ if (fImpl->fParser.parse(text, &builder)) {
+ ForthEngine engine(output);
+ FCode::Exec(builder.begin(), &engine);
+ }
+}
+#endif
+