epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 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 | */ |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 8 | #include "Forth.h" |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 9 | #include "ForthParser.h" |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 10 | #include "SkTDArray.h" |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 11 | #include "SkString.h" |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 12 | #include "SkTDStack.h" |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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 | |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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); |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 75 | |
| 76 | // setup the initial stack with the callers input data |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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 | } |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 83 | |
| 84 | // now invoke the word |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 85 | this->exec(&engine); |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 86 | |
| 87 | // now copy back the stack into the caller's output data |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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 | |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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: |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 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 | |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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 | }; |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 136 | |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 137 | enum Code { |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 138 | kPushInt_Code, // for data that needs more than 30 bits |
| 139 | kIF_Code, |
| 140 | kELSE_Code, |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 141 | kDone_Code |
| 142 | }; |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 143 | static unsigned MakeCode(Code code) { |
| 144 | return (code << kCodeShift) | kCodeShift2_Bits; |
| 145 | } |
| 146 | |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 147 | void appendInt(int32_t); |
| 148 | void appendWord(ForthWord*); |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 149 | void appendIF(); |
| 150 | bool appendELSE(); |
| 151 | bool appendTHEN(); |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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; |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 167 | SkTDStack<size_t> fIfStack; |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 168 | }; |
| 169 | |
| 170 | void FCode::appendInt(int32_t value) { |
| 171 | if ((value & 3) == 0) { |
| 172 | *fData.append() = value | kDataClear2_Bits; |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 173 | } else if ((value << 2 >> 2) == value) { |
| 174 | *fData.append() = (value << 2) | kDataShift2_Bits; |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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 | |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 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 | |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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: |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 242 | switch (GetCode(c)) { |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 243 | case kPushInt_Code: |
| 244 | engine->push(*curr++); |
| 245 | break; |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 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; |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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 | |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 282 | ForthParser::ForthParser() : fDict(4096) { |
| 283 | this->addStdWords(); |
| 284 | } |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 285 | |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 286 | ForthParser::~ForthParser() { |
reed@google.com | 1d5aaa8 | 2011-05-31 15:35:54 +0000 | [diff] [blame] | 287 | SkTDict<ForthWord*>::Iter iter(fDict); |
| 288 | ForthWord* word; |
| 289 | while (iter.next(&word)) { |
| 290 | delete word; |
| 291 | } |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 292 | } |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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(); |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 438 | } else if (4 == len && memcmp(token, "ELSE", 4) == 0) { |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 439 | if (!code->appendELSE()) { |
| 440 | return parse_error("ELSE with no matching IF"); |
| 441 | } |
reed@android.com | 19a89f2 | 2009-08-30 03:24:51 +0000 | [diff] [blame] | 442 | } else if (4 == len && memcmp(token, "THEN", 4) == 0) { |
reed@android.com | f56e295 | 2009-08-29 21:30:25 +0000 | [diff] [blame] | 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 | |