Home | History | Annotate | Download | only in forth 
      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
    502