| #include "Forth.h" |
| #include "ForthParser.h" |
| #include "SkTDArray.h" |
| #include "SkString.h" |
| #include "SkTDStack.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); |
| } |
| } |
| |
| 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); |
| |
| // setup the initial stack with the callers input data |
| 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]); |
| } |
| } |
| |
| // now invoke the word |
| this->exec(&engine); |
| |
| // now copy back the stack into the caller's output data |
| 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); |
| } |
| } |
| } |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| |
| /* |
| 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 { |
| kCodeShift = 2, |
| kCodeMask = 7, |
| kCodeDataShift = 5 |
| }; |
| static unsigned GetCode(intptr_t c) { |
| return ((uint32_t)c >> kCodeShift) & kCodeMask; |
| } |
| static unsigned GetCodeData(intptr_t c) { |
| return (uint32_t)c >> kCodeDataShift; |
| } |
| |
| enum Bits { |
| kWord_Bits = 0, // must be zero for function address |
| kDataClear2_Bits = 1, |
| kDataShift2_Bits = 2, |
| kCodeShift2_Bits = 3 |
| }; |
| |
| enum Code { |
| kPushInt_Code, // for data that needs more than 30 bits |
| kIF_Code, |
| kELSE_Code, |
| kDone_Code |
| }; |
| static unsigned MakeCode(Code code) { |
| return (code << kCodeShift) | kCodeShift2_Bits; |
| } |
| |
| void appendInt(int32_t); |
| void appendWord(ForthWord*); |
| void appendIF(); |
| bool appendELSE(); |
| bool appendTHEN(); |
| 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; |
| SkTDStack<size_t> fIfStack; |
| }; |
| |
| void FCode::appendInt(int32_t value) { |
| if ((value & 3) == 0) { |
| *fData.append() = value | kDataClear2_Bits; |
| } else if ((value << 2 >> 2) == value) { |
| *fData.append() = (value << 2) | 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::appendIF() { |
| size_t ifIndex = fData.count(); |
| fIfStack.push(ifIndex); |
| *fData.append() = MakeCode(kIF_Code); |
| } |
| |
| bool FCode::appendELSE() { |
| if (fIfStack.empty()) { |
| return false; |
| } |
| |
| size_t elseIndex = fData.count(); |
| *fData.append() = MakeCode(kELSE_Code); |
| |
| size_t ifIndex = fIfStack.top(); |
| // record the offset in the data part of the if-code |
| fData[ifIndex] |= (elseIndex - ifIndex) << kCodeDataShift; |
| |
| // now reuse this IfStack entry to track the else |
| fIfStack.top() = elseIndex; |
| return true; |
| } |
| |
| bool FCode::appendTHEN() { |
| if (fIfStack.empty()) { |
| return false; |
| } |
| |
| // this is either an IF or an ELSE |
| size_t index = fIfStack.top(); |
| // record the offset in the data part of the code |
| fData[index] |= (fData.count() - index - 1) << kCodeDataShift; |
| |
| fIfStack.pop(); |
| return true; |
| } |
| |
| 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 (GetCode(c)) { |
| case kPushInt_Code: |
| engine->push(*curr++); |
| break; |
| case kIF_Code: |
| if (!engine->pop()) { |
| // takes us past the ELSE or THEN |
| curr += GetCodeData(c); |
| } |
| break; |
| case kELSE_Code: |
| // takes us past the THEN |
| curr += GetCodeData(c); |
| 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; |
| }; |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| |
| ForthParser::ForthParser() : fDict(4096) { |
| this->addStdWords(); |
| } |
| |
| ForthParser::~ForthParser() { |
| SkTDict<ForthWord*>::Iter iter(fDict); |
| ForthWord* word; |
| while (iter.next(&word)) { |
| delete word; |
| } |
| } |
| |
| 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 (4 == len && memcmp(token, "ELSE", 4) == 0) { |
| if (!code->appendELSE()) { |
| return parse_error("ELSE with no matching IF"); |
| } |
| } else if (4 == 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 |
| |