| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1559823002:
remove forth experiment (Closed)
Base URL: https://skia.googlesource.com/skia.git@master