GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — tokthr/tokthr.S at master · kragen/tokthr Expand file tree/ Copy pathtokthr.SMore file actions 1163 lines (1004 loc) · 44.7 KB / Copy pathtokthr.SFile metadata and controls1163 lines (1004 loc) · 44.7 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 # Simple token-threaded "Forth" interpreter. -*- asm -*- # Version 3. # by Kragen Javier Sitaker; dedicated to the public domain, # i.e. I relinquish whatever exclusive rights copyright law # gives me with regard to this work. # Major parts taken from Richard W.M. Jones's public-domain # http://annexia.org/forth # As of version 2, this program just outputs the following under # Linux: # hell, world, hello # -120 1 104 # s: 102 101 100 # 397 # lit8 lit ret execute (if) (else) (loop) ! @ c! c@ rp@ rp! r> >r sp@ sp! pop dup over swap 0< & | ^ um+ /% um* r@ syscall5 syscall3 syscall1 bye 0 1 type hello world comma count cr -1 + 1- rot -rot tuck emit u. (u.) ((u.)) ~ 1+ negate . scolon .s pick cells * depth - / cellsize nip (do) i 2dup 2drop dict dictp dictsize nextword pastdict? words < >= 0= cbcmp c@+ bcmp memcmp unloop find r2@ 2swap # hello134517863 # , 0 # 134517710 # to compile: # gcc -m32 -nostdlib -static -o tokthr tokthr.S ### Why Small Things are Interesting # There are still a lot of computers out there that have tens of # kilobytes of memory or less, and they cost a lot less than, # say, a cellphone. Cellphones are apparently still too # expensive for half the world's population. I want to see how # close I can get to having a comfortable programming # environment in a smaller device. # Some smallish microcontroller chips from five different # manufacturers, with current Digi-Key prices: # Name bytes RAM bytes ROM MHz price # ATtiny2313 128 2048 20 US$1.38 # ATMega48-20AU 512 4096 20 US$1.62 # MSP430F1111AIPW 128 2264 8 US$2.43 # LPC2101 2048 8192 70 US$2.52 # H8/300H Tiny 1536 8192 12 US$3.58 # M16C/R8C/Tiny/1B 1024 16384 12 US$3.54 # SX28AC/SS 136 3072 50 US$2.79 # There are essentially no 386-compatible devices in this price # range as far as I can tell; for why I'm not worried about # that, see the section "How Small This Is". # More practically and short-termly, small projects can take # less time to finish, and I feel like I need to learn about # different approaches to implementing programming languages. ### Why This is Small # The normal Forth representation of a function is as an array # of pointers to the other functions it calls, in sequence; a # few of those other functions may move the interpreter pointer # around in that array, or snarf up a constant that's stored in # the array, or stuff like that, but for the most part, the # functions just get called in sequence. This is called # "threaded code" and it's fairly compact, especially on 16-bit # systems where the pointers are only two bytes. # A traditional approach taken by Forth implementations to # reduce code size even further is called "token threading". # Rather than making arrays of 16-bit or 32-bit pointers, they # make lists of 8-bit indices into an array of pointers. This # has two advantages: # 1. the indices are one fourth the size of a list of 32-bit # pointers; # 2. it is possible to save these lists of indices somewhere # outside of memory and continue to use them even after # making some changes to the code, as long as the same # indices in the table have the same meanings. So, for # example, you could write some boot firmware in this # "bytecode". # It also has some disadvantages: # 1. You run out of space in the table. Even a fairly minimal # full Forth system contains close to 256 subroutines. You # can mitigate this by packing, say, two 12-bit pointers # every three bytes, or maybe by having a special bytecode # that looks up the next byte in an extended table. # 2. It's slower and makes the machine-code part of the program # take more space. The traditional LODSW; JMP AX version of # $NEXT from the eForth Model, which fetches and executes the # next execution token in the threaded list, is three bytes # and two instructions; my 'next' here is 41 bytes and 14 # instructions, which is big enough that I jump to it (2 # bytes) rather than making an assembler macro. Which blows # your branch target buffers to pieces. Oh well. The # performance penalty is probably two orders of magnitude # over native code, but I haven't measured it yet. I # measured an earlier version on my 700MHz PIII laptop on an # empty loop at about a factor of 3.5 over simple # direct-threading, which in turn is on the order of 10 times # slower than machine code. # Anyway, so this is an example program built using this # technique. It implements two Forthlike stacks and interpreted # subroutines, but not yet the ability to define new subroutines # at run-time. ### What's Here # I've implemented all of the primitives from C. H. Ting and # Bill Muench's public-domain (?) eForth Model 1.0, except for # the following: # - I haven't implemented their lowercase "next" (as in FOR # NEXT) because I think it's a bad idea, it's complex, and it # can be implemented at a higher level if you really need it; # instead, I implemented (loop). # - I didn't implement !IO because it's a no-op in this context; # - I haven't yet implemented ?RX, although I think it's # possible to implement it on top of syscall5, using select(); # Additionally, I implemented multiply and divide primitives. # However, some of it is untested and therefore probably broken. # Procedure call and return and the system calls do work. # Currently registers are used as follows: # %esi --- interpreter pointer; points to next byte to execute # %ebp --- return stack pointer; points to last thing pushed. This stack, # like the other one, grows downwards. # %esp --- data stack pointer; points to last thing pushed. This is # the processor's standard stack pointer; "push" and "pop" # instructions use it, which makes assembly code to use it # quite concise. The Intel "call" and "ret" instructions # would also use this stack, but they aren't used in this # program. # flags --- the "down" direction flag must be cleared. # It's probably missing a couple of primitives needed because of # the token-threading implementation strategy; the address of # the token table probably needs to be knowable, at least. # Direct and indirect threading, the normal Forth approaches to # allowing unrestricted coexistence of words written in assembly # language and interpreted Forth, both had heavy space costs # here --- close to 100% for the bytecode currently in the # system. So the inner interpreter checks, for each bytecode, # whether it is in the range of bytecodes whose interpretations # are in native code, and picks the relevant code path. This # avoids consuming any space per-word for this distinction, but with # what appears to be a heavy performance cost. # This is similar to an approach called "bit threading"; as # explained by Jeff Fox in a comp.lang.forth message # 2007-05-13, on thread "Cases where Forth seems a little # clunky": # I have seen hardware and software implemenations of # bit-threading where the msb of the address space # selects between threaded code address lists and # addresses of CODE subroutines. In both cases 0 is a # valid address and negative addresses are valid. I think # this applied to Novix. # Except that this approach uses a fraction of a bit for most # tokens instead of a whole bit. ### How Small This Is # As a point of comparison, eForth 1.0's machine-code part seems # to be 171 instructions and 399 bytes, including some data # that's mixed in there with it. # As of version 3, the machine-code part of this interpreter is # 239 bytes in 129 machine-code instructions, plus 19 bytes of # read-only data, 172 bytes of token table for the 86 # currently-defined words (30 of which are primitive), 397 # bytes of their names, and another 370 bytes of bytecode in # the 56 bytecode words (including a couple of data values # scattered around), and then another 56 bytes in the main # program, for a total of 1253 bytes. So the program is # already less than half written in assembly, in terms of # object-code size. # As of version 3, the machine-code part of this program uses # only 25 different instructions: cld; jmp, jz, jnc, jbe; push, # pop, lodsb, lodsl, xchg, mov; cmp, movsbl, inc, and, xor, or, # lea, cdq, rcl, add, idiv, imul; and int. Interestingly, many # of them are only used once. # Just before version 3, the non-comment lines were 14% # assembler macros, 51% assembly language, and 35% bytecode. # From Brad Rodriguez's January/February 1993 Computer Journal # article, "Moving Forth: Part 1: Design Decisions in the Forth # Kernel": # You can expect the usual 16-bit Forth kernel (see below) # to occupy about 8K bytes of program space. For a full # kernel that can compile Forth definitions, you should # allow a minimum of 1K byte of RAM. # I'm pretty sure I can beat the 8K requirement by quite a bit # and still be able to compile Forth definitions --- I'm hoping # for a factor of 4. Consider, from Jeff Fox's "Thoughtful # Programming", chapter 3: http://www.ultratechnology.com/forth3.htm # People assume that since Chuck has refined his Forth down to # about a 1K object that this means he has just stripped his # Forth down to a 1K kernel that will boot like in the old days # and that he is going to compile a complete Forth system on top # of the 1K before he starts an application. This is wrong. The # complete Forth system is 1K, and the reason for that is # maximize Chuck's productivity. What stops people from doing # what they need to do to solve a problem is all the time spend # solving all the related sub-problems that pop up as a result # of complex interconnections between components. To maximize # his productivity Chuck minimizes the number of these side # problems that pop up. Keep it simple, and don't get to where # you are spending 90% or 99% or you time dealing with related # sub-problems. Avoid unsolvable problems, don't waste your time # trying to solve them. # Consider also this quote from Elizabeth Rather: # As you have seen, so much depends on the specific # machine architecture. We implemented a TTC [token # threaded] Forth on some low-end AVR processors with # very limited code space, and it ran faster than a # native-code 8051 at comparable clock speed. # (2007-06-23 comp.lang.forth post on thread "Build your own # Forth for Microchip PIC (Episode 838): Threading") # http://objectmix.com/forth/168105-build-your-own-forth-microchip-pic-episode-838-threading.html # Consider also this quote from the abstract of Frank # Sergeant's 1991 "A 3-Instruction Forth for Embedded Systems # Work: Illustrated on the Motorola MC68HC11": # A 3- instruction Forth makes Forth affordable for # target systems with very limited memory. It can be # brought up quickly on strange new hardware. You don't # have to do without Forth because of memory or time # limitations. It only takes 66 bytes for the Motorola # MC68HC11. Full source is provided. . . . The absolute # minimum the target must do, it seems to me, is fetch a # byte, store a byte, and call a subroutine. # http://pygmy.utoh.org/3ins4th.html # As I said before, there are no small, cheap 386s, and so of # course the code size of this version is an approximation, and # it won't be a simple recompile to port it to one of these # other architectures; but 129 instructions' worth of assembly # are probably not that big a deal to rewrite for a new # platform. (I'll probably want to write multiply and divide # routines, though.) ### Other Things I Tried # I tried switching to caching the top of the data stack in a # register, on the theory that it would shorten things like # 'and'. Currently 'and' is pop %eax; pop %ebx; and %ebx, # %eax; push %eax; jmp next. If top of stack is cached in %eax # instead of being stored in memory, this becomes pop %ebx; and # %ebx, %eax; jmp next, which is considerably shorter. # However, most things don't change, and other things become # longer due to the extra work to save top-of-stack. I tried # using both %ebx and %eax as the top-of-stack cache. # In the version using %ebx as top-of-stack, the total size of # the machine-code part was 216 bytes, 115 instructions, # compared to 197 bytes, 112 instructions for the version using # the current strategy. In the version using %eax as # top-of-stack, it was only 215 bytes, but that's still worse # than 197. # In previous versions, all routines were machine-code routines # that you could just jmp to. High-level bytecode words began # with "call dolist", which took the saved %eip off the stack # and stuck it in %esi. Unfortunately, that added 5 bytes to # each bytecode word; in version 2, the bytecode region is 221 # bytes and contains 36 word definitions (the 30 machine-code # primitives aren't defined there) --- so 5 bytes each would # have been 180 bytes of overhead, or 82%! It also would have # required a region to be both executable and writable to # support run-time routine definition, which is kind of a pain # thse days, and also on Harvard-architecture microcontrollers. # In previous versions, the token-table entries were 32 bits # each (instead of 16 bits as they are now), which added # another 2 bytes of overhead per word. In version 2, there # are currently 66 words, so that's another 132 bytes of shaved # overhead. ### Performance (Speed) # To version 2, I added a simple program to print out a # badly-formatted 8-bit extended ASCII table; it was 11 # bytecode operations long. It executed 81615 bytecodes in all # (according to gdb). On my 700MHz PIII-Coppermine laptop from # 1999, 'time' reports CPU times varying from 4-12 # milliseconds. So it seems like it can execute about 10 000 # bytecodes in a millisecond, or about 10 million bytecodes in # a second --- about 100ns per bytecode. # It also made 1459 system calls. # That's slightly faster than Python's bytecode engine (maybe # --- probably within measurement error --- and anyway Python's # bytecodes are larger-grained), and an order of magnitude # slower than simple direct-threading, and about three times # slower than direct-threading with a simple bytecode # indirection layer. # I would be surprised if version 3 had any measurable change # in speed from version 2. # To version 3, I added a little loop to repeatedly search the # 86-word wordlist for ", ", which isn't there. I was able to # do this search 10 000 times in 4.59 CPU seconds, which is # 5.34 microseconds per comparison, or about 3700 CPU cycles. # If we eventually have 300 words in the wordlist, each search # will therefore take 1.6 milliseconds in the worst case, so # the system won't be able to compile or interpret more than # about 50-100 lines of code per second. It should probably be # pretty easy to fix this particular performance problem # (recode wordlist search in asm, restructure, or whatever) if # it comes up, but it's a bit worrisome... ### What's Wrong With This Program # - It's a long way from doing anything useful. # - There's 21 instructions of unused code which may be broken. # In Version 3, these words are in use and so probably work: # hello, sub1, type, comma, world, newline, dolit_s8, dot, # bye, exit, branch_on_0, c_bang, drop, dup, swap, negative, # umplus, divmod, syscall5, syscall3, zero, syscall1, rpop, # rpush, one, dolit_32, neg1, add, emit, tuck, udot, # udot_nospc, udot_nonzero, branch, invert, add1, negate, # xor, printstack, cells, mul, depth, div, sub, cellsize, # nip, pick, twodup, i, _do, r_at, over, at, sp_at, bang, # twoswap, r_2at, find, unloop, memcmp, bcmp, c_at_inc, # cbcmp, zeq, ge, lt, words, pastdict, nextword, dictsize, # dictp, dict, c_at. These are not tested, and therefore may be # broken: execute, rp_at, rp_bang, sp_bang, and, or. # - There's no dictionary structure yet. # - It probably needs another couple of primitives. # - There's no checking for stack overflow or underflow, but # they will break things. # - It's slow; see above about performance. ### The Beginning of the Program # .. include system library header so we know __NR_exit = 1 and # __NR_write = 4 #include <asm/unistd.h> ### The token table and dictionary # To save space, we're trying to avoid storing pointers # as much as possible. So most of the code is # represented as "tokens", which are offsets into the # "token table", which contains 16-bit offsets into # either the machine-code primitives or the data # segment. # The "dictionary" is stored in this program as a # sequence of strings, stuffed next to each other with # no intervening pointers at all. The idea is that if # you want to execute or compile a word, you walk # through the dictionary, examining each string in turn # to see if it's the right word. If so, then the # number of strings you rejected is the index into the # token table. # This implies that the dictionary needs to be stored # somewhere where it can expand without overwriting # other stuff. So I'm putting it in its own section # for the time being. I'm pretty sure that means it'll # get at least a page, which is enough space to define # at least several hundred words. Maybe at some future # time I'll copy it into .bss at boot time instead. .data 1 # Start putting stuff in data subsection 1 .align 4 ## table to define the "bytecode" instructions token_table: # "a" means "allocatable", "w" means "writable" .section .dictionary, "aw" dictionary: ## I was frustrated with the unreadability of my ## bytecode lists; I was counting token table entries ## by hand and writing bytecodes numerically. So I ## wrote a macro to help. ## Note that we are using a separate .subsection ## directive because gas 2.17 doesn't support putting ## that in the .pushsection line, even though it is ## documented to do so; see message from Maciej ## W. Rozycki on 2007-10-11, subject "Re: How to use ## .pushsection?", ## http://sourceware.org/ml/binutils/2007-10/msg00176.html ## for more details) ## The first few entries in the table of bytecodes are ## all defined in machine code; the rest are all ## defined in bytecode. The inner interpreter examines ## each bytecode to determine which category it falls ## in in order to figure out how to execute it, ## including what base address to add its offset to. ## This sucks for extensibility but rocks for ## compactness. .macro countedstring name .byte stringlength\@ 1: .ascii "\name" ## Here we count the length of the string --- computers ## are for counting bytes so people don't have to! stringlength\@ = . - 1b .endm .macro define_bytecode name, realname, origin .pushsection .data # save current position, go to data section .subsection 1 # and subsection 1, where we put the addrs b_\name = (. - token_table) / 2 # define b_foo as the index of this ptr .ifeq b_\name - 256 .error "\name got bytecode 256" .endif .short \name - \origin # insert offset which will be resolved next .popsection # return to where we were, and .pushsection .dictionary countedstring "\realname" .popsection \name: # define the name .endm .macro defasm name, realname define_bytecode \name, "\realname", machine_code_primitives .endm .macro defbytes name, realname define_bytecode \name, "\realname", bytecode_start .endm ### The Return Stack # We put Forth return addresses here, but programs can also use # it for other purposes. .bss .space 4096 initial_return_stack_pointer: ### Initialization .text # the following stuff goes in the text segment .global _start # declare _start as a global symbol # (otherwise ld won't be able to find it) _start: # this is the entry point for ELF I guess cld # clear direction flag; unnecessary? mov $initial_return_stack_pointer, %ebp mov $instructions, %esi # %esi is the interpreter pointer register jmp next # and now we start the interpreter. # (somewhat silly since we could just # fall through..) ### The Machine-Code Primitives # Also next (aka the address interpreter or inner interpreter) # is in this section. machine_code_primitives: # dolit_s8 takes a signed 8-bit literal from the instruction # stream and pushes it onto the stack. defasm dolit_s8, "lit8" lodsb movsbl %al, %eax jmp pusheax defasm dolit_32, "lit" # more general dolit lodsl jmp pusheax defasm exit, "ret" # Return from a colon defn. xchg %ebp, %esp pop %esi xchg %ebp, %esp jmp next defasm execute, "execute" # Run xt on data stack. pop %eax # Here 'xt' is the one-byte token. jmp execute_eax # Branch if top of stack is 0 (implementing IF). # Both branch instructions take a signed byte offset from the bytecode # stream. defasm branch_on_0, "(if)" pop %eax and %eax, %eax jz branch inc %esi # skip 1-byte jump offset jmp next defasm branch, "(else)" lodsb movsbl %al, %eax # same insn size as cbtw; cwde add %eax, %esi jmp next # (loop) is what we do at the end of a DO LOOP. # DO puts a number on top of the return stack that is zero minus # the number of iterations remaining. So when it finally # reaches zero, we're done. It also put a number underneath # that on the return stack from which you can recover the # iteration counter. # This scheme is mostly due to F-83, except that in F-83 it # reached 0x8000 instead of 0, which seemed perverse to me. # This isn't strictly necessary as part of the minimal primitive # set, but it seemed like it would make inner loops maybe ten # times faster, and as with most words that do return-stack # manipulation, the size penalty is actually negative. (This # version is 14 bytes; in bytecode it would be 17.) # ( -- ) ( R: -1 adjustment -- ) in end-of-loop case, and skip # the interpreter pointer over the jump offset. # ( -- ) ( R: counter -- counter+1 ) in normal case, and adjust # interpreter pointer by number of bytes stored after call to # this routine. defasm _loop, "(loop)" xor %eax, %eax # mov $1, %eax is 5 bytes inc %eax add %eax, (%ebp) jnc branch # if no carry, go branch # If there was a carry, we're done! add $8, %ebp # drop loop-sys from rstack lodsb # skip jump offset jmp next # Store a cell. defasm bang, "!" pop %ebx pop (%ebx) # I'm amazed this is legal jmp next # Fetch a cell. defasm at, "@" pop %ebx push (%ebx) # I'm amazed this is legal too jmp next # Store a byte. defasm c_bang, "c!" pop %ebx pop %eax mov %al, (%ebx) # push and pop don't do bytes jmp next # Fetch a byte. defasm c_at, "c@" pop %ebx xor %eax, %eax mov (%ebx), %al jmp pusheax # Get the return stack pointer. defasm rp_at, "rp@" push %ebp jmp next # Set the return stack pointer. defasm rp_bang, "rp!" pop %ebp jmp next # Pop the return stack to the data stack defasm rpop, "r>" xchg %esp, %ebp pop %eax xchg %esp, %ebp jmp pusheax # Push the return stack from the data stack defasm rpush, ">r" lea -4(%ebp), %ebp pop (%ebp) jmp next # Get the data stack pointer (before it gets pushed). defasm sp_at, "sp@" push %esp # safe on 286 and later jmp next # Set the data stack pointer. defasm sp_bang, "sp!" pop %esp jmp next # Pop the stack. defasm drop, "pop" pop %eax jmp next # Push a copy of TOS. # eForth 1.0 used BX to index the stack here, for a couple of # reasons: on the 8086, SP got decremented prior to the fetch, # and also wasn't valid as a base or index register. defasm dup, "dup" pop %eax push %eax jmp pusheax # Stack manipulation ( w1 w2 -- w1 w2 w1 ) # technically not necessary, but it's so easy and tiny defasm over, "over" push 4(%esp) jmp next # Swap top two stack items ("exch" in PostScript) defasm swap, "swap" pop %edx pop %eax # jmp pushedxeax fall through because pushedxeax is next # pusheax and pushedxeax: a prologue to 'next' that first pushes %edx # and %eax, or just %eax. # For a net savings of 13 bytes, last I checked, in all those # primitives that finish up by pushing something! Clever trick from # F-83's 1PUSH and 2PUSH. pushedxeax: push %edx pusheax: push %eax # now we fall through to 'next' # "next" fetches the next bytecode and runs it. It's placed # here in the middle of the bytecode definitions so that more # of them can use the short two-byte jump form to get to it. next: xor %eax, %eax # set %eax to 0 xor %ebx, %ebx # clear high half of %ebx lodsb # load %al from where %esi points # (%esi is the interpreter pointer) execute_eax: ## load offset of new word into %ebx mov token_table(,%eax,2), %bx # bx := token_table[eax * 2bytes] cmp $last_asm_bytecode, %eax jbe next_primitive # if primitive, handle primitive word ## otherwise, handle a bytecode definition or "colon list" # save old %esi on return stack xchg %ebp, %esp push %esi xchg %ebp, %esp lea bytecode_start(%ebx), %esi jmp next next_primitive: lea machine_code_primitives(%ebx), %ebx jmp *%ebx # Push true if n negative. ( n -- f ) defasm negative, "0<" pop %eax cdq push %edx jmp next # Bitwise operators: defasm and, "&" pop %eax pop %ebx and %ebx, %eax jmp pusheax defasm or, "|" pop %eax pop %ebx or %ebx, %eax jmp pusheax defasm xor, "^" pop %eax pop %ebx xor %ebx, %eax jmp pusheax # add two unsigned numbers, returning sum and carry. # ( u1 u2 -- u3 cy ) defasm umplus, "um+" xor %eax, %eax pop %edx pop %ebx add %ebx, %edx rcl $1, %eax jmp pushedxeax # Divide double-precision by single-precision, unsigned (?). # UM/MOD from eForth. ( udl udh un -- ur uq ) defasm divmod, "/%" pop %ebx pop %edx pop %eax idiv %ebx jmp pushedxeax # Multiply two single-precision numbers, giving a double- # precision result. ( d1 d2 -- udl udh ) defasm mmul, "um*" pop %eax pop %ebx imul %ebx push %eax push %edx jmp next # Copy the top of the return stack onto the data stack. defasm r_at, "r@" push (%ebp) jmp next # syscall5: # Linux system call with up to 5 arguments # This is no longer the fashionable way to make system calls # in Linux. Now you're supposed to use SYSENTER on newer # CPUs, and rather than have you figure out which one to use, # the kernel mmaps a chunk of code called a VDSO into your # memory space at a random address and tells you where to # find it using the ELF auxiliary vector. Then you're # supposed to invoke the dynamic linker or something to parse # the ELF executable mysteriously manifested in this way by # the kernel, and then resolve an undefined symbol in libc # into calls to it. See "What is linux-gate.so.1?" # http://www.trilithium.com/johan/2005/08/linux-gate/ # "The Linux kernel: System Calls" by Andries Brouwer, 2003-02-01 # http://www.win.tue.nl/%7Eaeb/linux/lk/lk-4.html # "About ELF Auxiliary Vectors" by Manu Garg # http://manugarg.googlepages.com/aboutelfauxiliaryvectors # But the old int $0x80 approach still works, thank goodness, # because all of that is *way* more than these ten # instructions. defasm syscall5, "syscall5" pop %edi ## we have to save %esi for the interpreter mov %esi, -4(%ebp) pop %esi pop %edx pop %ecx pop %ebx pop %eax int $0x80 mov -4(%ebp), %esi jmp pusheax last_asm_bytecode = b_syscall5 ### Basic Interpreted Words ## a macro for defining interpreted words ## Because after I left off b_exit once, I wasted a long ## time trying to figure out what was wrong, so I use this when I can: .macro def name, realname, bytes:vararg defbytes \name, "\realname" .byte \bytes .byte b_exit .endm ## Macros for conditional branch and loop: ## Because I am tired of tracking down bugs due to ## getting the jump offsets wrong. .macro fif, target # if, or end of while loop .byte b_branch_on_0, \target - . - 1 .endm .macro floop, target # do loop .byte b__loop, \target - . - 1 .endm .macro felse, target # else, unconditional jump .byte b_branch, \target - . - 1 .endm .data 2 # separate subsection from token table bytecode_start: # System call with three arguments. def syscall3, "syscall3", b_zero, b_zero, b_syscall5 # System call with one argument. def syscall1, "syscall1", b_zero, b_zero, b_syscall3 def bye, "bye", b_dolit_s8,__NR_exit, b_zero, b_syscall1 # exit program def zero, "0", b_dolit_s8,0 # push 0 def one, "1", b_dolit_s8,1 # This word outputs a string whose address and count are on # the stack. ( b u -- ) defbytes type, "type" .byte b_rpush, b_rpush # move two args onto rstack # system call is __NR_write: .byte b_dolit_s8,__NR_write .byte b_one # push constant 1: stdout .byte b_rpop, b_rpop # move two args back from rstack .byte b_syscall3 # call syscall with 3 args .byte b_drop # discard return value .byte b_exit # return # The next few words exist just to poke string addresses # and lengths onto the stack so "type" can print them. .macro def_counted_string name, contents defbytes \name, "\name" .byte b_dolit_32 # dolit_32 pushes a 32-bit .int string_\name # literal --- an addr, here # now push literal length and return .byte b_count, b_exit .pushsection .rodata # define the actual string: string_\name: countedstring "\contents" .popsection .endm def_counted_string hello, "hello" def_counted_string world, "world" def_counted_string comma, ", " # convert a counted string in memory to an address and # count on the stack def count, "count", b_dup, b_add1, b_swap, b_c_at def cr, "cr", b_dolit_s8, '\n, b_emit ### Some More Basic Words def neg1, "-1", b_dolit_s8, -1 # ( -- -1 ) def add, "+", b_umplus, b_drop # ( a b -- a+b ) drop the carry def sub1, "1-", b_neg1, b_add # ( n -- n-1 ) def rot, "rot", b_rpush, b_swap, b_rpop, b_swap # ( a b c -- b c a ) def unrot, "-rot", b_rot, b_rot # ( a b c -- c a b ) def tuck, "tuck", b_dup, b_unrot # ( a b -- b a b ) # emit: output a single byte. eForth calls this "TX!". # This version is 11 bytes, including the buffer byte, plus the 2-byte # token table pointer. a machine-code version I wrote the other day # was 28 bytes. However, I also added rot, unrot, and tuck to support # this function, and they total 11 bytes, plus 6 bytes of overhead. # For a total of 11+2+11+6 = 30 bytes. Not winning yet on size over # x86 asm! But we're getting close. emit_buffer: .byte 0 defbytes emit, "emit" .byte b_dolit_32 .int emit_buffer .byte b_tuck # save a copy of address for b_type .byte b_c_bang # store into emit buffer .byte b_one, b_type, b_exit # output one-byte buffer ### "u." prints out an unsigned number. # I had a version of this in x86 machine code in 52 bytes (23 # instructions), essentially exactly the same code as here. # This is 31 bytes, plus 6 bytes of overhead, plus I had # to define b_divmod (9 bytes plus 2 bytes overhead). Now we are # starting to win! defbytes udot, "u." # print space after number .byte b_udot_nospc, b_dolit_s8, 0x20, b_emit, b_exit defbytes udot_nospc, "(u.)" # print number without space .byte b_dup fif 1f .byte b_udot_nonzero, b_exit 1: .byte b_drop, b_dolit_s8, '0, b_emit, b_exit defbytes udot_nonzero, "((u.))" .byte b_zero, b_dolit_s8,10, b_divmod # divide by 10 .byte b_dup fif 2f # recurse if nonzero .byte b_udot_nonzero felse 3f 2: .byte b_drop # drop zero quotient 3: .byte b_dolit_s8, '0, b_add, b_emit # print digit .byte b_exit ### Add signed numeric output, ".". This cost 20 bytes plus 8 bytes # of overhead, but added some fundamental numeric operations; only 12 # of those 28 bytes are specific to "." # logical bitwise not def invert, "~", b_dolit_s8, -1, b_xor def add1, "1+", b_one, b_add # arithmetic negation def negate, "negate", b_invert, b_add1 # print signed number defbytes dot, "." .byte b_dup, b_negative fif 1f .byte b_dolit_s8, '-, b_emit, b_negate # in the negative case 1: .byte b_udot, b_exit ### Obviously the next thing to do is to add ".S", print the # stack, so that I can stop having to investigate problems by # using gdb. # The bytecode for this consumed 78 bytes in 12 words, plus a # new 8-byte primitive (mmul) and a new 14-byte primitive # (_loop), plus six bytes in the initialization routine, for 28 # bytes of overhead and a total of 78+28+14+8+6 = 134 bytes. # This is definitely not a size win over machine code! Machine # code would only be 22 bytes in 7 instructions, if there were a # way to just CALL the "." routine from machine code, which # there isn't. # However, the words added were cells * - / cellsize nip (do) # (loop) 2dup which are all generally useful, and # depth pick .s which are more special-purpose. # The special-purpose words are 35 out of those 78 bytes. # PRINTSTACK itself is only 15 bytes, and there's hope that the # 6 bytes of PICK and the 14 bytes of DEPTH will be useful in # other debugging routines. # I'm not happy with (do) and (loop), only because (do) # implements dpANS DO, not dpANS ?DO, so it loops many times # when it should loop zero times; def_counted_string scolon, "s: " defbytes printstack, ".s" .byte b_scolon, b_type .byte b_depth, b_zero # loop limits .byte b_twodup, b_xor fif 1f # skip loop if stack empty .byte b__do 2: .byte b_i, b_pick, b_dot # DO I PICK . LOOP floop 2b 1: .byte b_cr, b_exit def pick, "pick", b_add1, b_cells, b_sp_at, b_add, b_at def cells, "cells", b_cellsize, b_mul def mul, "*", b_mmul, b_drop # drop upper 32 bits of multiplication result bottom_of_stack: .int 0 defbytes depth, "depth" .byte b_sp_at, b_dolit_32 .int bottom_of_stack .byte b_at, b_swap, b_sub, b_zero, b_cellsize, b_div, b_exit def sub, "-", b_negate, b_add # subtract ( a b -- a-b ) def div, "/", b_divmod, b_nip # int divide ( ul uh n -- quotient ) def cellsize, "cellsize", b_dolit_s8,4 # ( -- 4 ) def nip, "nip", b_swap, b_drop # stack manipulation ( a b -- b ) # 10 0 DO ... LOOP loops 0, 1...9. # _do sets up return stack for _loop # similar to F83: ( limit initial -- ) ( R: X -- X initial-limit limit ) defbytes _do, "(do)" .byte b_over, b_sub, b_swap, b_rpop, b_swap, b_rpush .byte b_swap, b_rpush, b_rpush, b_exit ## return loop counter def i, "i", b_rpop, b_rpop, b_r_at, b_over, b_rpush, b_add, b_swap, b_rpush def twodup, "2dup", b_over, b_over def twodrop, "2drop", b_drop, b_drop # Now some stuff for dealing with the dictionary. # This stuff was from 804930a to 8049396, 140 bytes. In that we got: # - new words: dict dictp dictsize nextword pastdict? words < >= 0= # cbcmp c@+ bcmp memcmp unloop find r2@ 2swap # - less concretely: # - the ability to list of words in the dictionary; # - the ability to find words in the dictionary; # - <, >=, and 0= numerical comparisons; # - cbcmp, bcmp, and memcmp memory manipulations; # - 2swap and r2@ stack manipulations; # - unloop loop control; # - c@+ for iterating over memory. # That's 17 new words, averaging 8.2 bytecodes each. dictionary_pointer: .int end_of_dictionary defbytes dict, "dict" .byte b_dolit_32 .int dictionary .byte b_exit defbytes dictp, "dictp" .byte b_dolit_32 .int dictionary_pointer .byte b_exit def dictsize, "dictsize", b_dictp, b_at, b_dict, b_sub def nextword, "nextword", b_dup, b_c_at, b_add, b_add1 def pastdict, "pastdict?", b_dictp, b_at, b_ge defbytes words, "words" .byte b_dict 1: .byte b_dup, b_count, b_type, b_dolit_s8,32, b_emit .byte b_nextword .byte b_dup, b_pastdict fif 1b .byte b_exit def lt, "<", b_sub, b_negative def ge, ">=", b_lt, b_zeq # logical not: return true for 0, false (0) otherwise defbytes zeq, "0=" fif 1f .byte b_zero, b_exit 1: .byte b_neg1, b_exit # To find a word in the dictionary: # - move the word onto the return stack, and get the dictionary pointer |
| You are visitor 01402605 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |