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
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
33void 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);
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
116class FCode {
117public:
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
165private:
166    SkTDArray<intptr_t> fData;
167    SkTDStack<size_t>   fIfStack;
168};
169
170void 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
182void FCode::appendWord(ForthWord* word) {
183    SkASSERT((reinterpret_cast<intptr_t>(word) & 3) == 0);
184    *fData.append() = reinterpret_cast<intptr_t>(word);
185}
186
187void 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
224void 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:
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
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
282ForthParser::ForthParser() : fDict(4096) {
283    this->addStdWords();
284}
285
286ForthParser::~ForthParser() {
287    SkTDict<ForthWord*>::Iter iter(fDict);
288    ForthWord* word;
289    while (iter.next(&word)) {
290        delete word;
291    }
292}
293
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();
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
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