# Simple token-threaded "Forth" interpreter. -*- asm -*-
# 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
# JONESFORTH 42 by Richard W.M. Jones <rich at annexia.org>
# http://annexia.org/forth
# This program just outputs "hello, world, hello" under Linux.
# to compile:
# gcc -m32 -nostdlib -static -o tokthr2 tokthr2.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
# 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;
# - 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();
# However, most 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.
# Fortunately this seems to be the case by default.
# 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 I assume is a heavy performance cost.
### How Small This Is
# 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.
# Last I checked, this program uses only 19 different
# instructions: jmp, jz; push, pop, lodsb, lodsl, xchg, mov;
# movsbl, inc, and, xor, or, lea, cdq, rcl, add, idiv; and int.
# At the moment, this program is 229 bytes in 125 machine-code
# instructions, plus 13 bytes of read-only data, 104 bytes of
# token table for the 52 currently-defined words, and another
# 143 bytes of bytecode in those words, and then another 22
# bytes in the main program, for a total of 511 bytes.
# One important thing that's missing here is the dictionary
# structure, which will minimally use up another hundred bytes
# or so.
### 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; as I write this, the bytecode region is
# 143 bytes and contains 24 word definitions --- so 5 bytes each
# would have been 120 bytes of overhead, or 84%! 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.
# 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. There are currently 52 words,
# so that's another 104 bytes of shaved overhead.
### What's Wrong With This Program
# - It's a long way from doing anything useful.
# - Only these words are tested: 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. These are
# not tested, and therefore may be broken: execute, bang, at,
# c_at, rp_at, rp_bang, sp_at, sp_bang, over, and, or, r_at.
# - 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.
### 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
## 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 define_bytecode name, 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
#.int \name # insert pointer which will be resolved next:
.short \name - \origin # insert offset which will be resolved next
.popsection # return to where we were, and
\name: # define the name
.endm
.macro defasm name
define_bytecode \name, machine_code_primitives
.endm
.macro defbytes name
define_bytecode \name, bytecode_start
.endm
.data 1 # Start putting stuff in data subsection 1
.align 4
## table to define the "bytecode" instructions
token_table:
.data 3
instructions:
# And here is the actual "program" in that bytecode.
.byte b_hello # string "hello" and count
.byte b_sub1 # subtract 1 from count: "hell"
.byte b_type # spit it out
.byte b_comma, b_type, b_world, b_type # ", world"
.byte b_comma, b_type, b_hello, b_type, b_newline, b_type
# test the "dot" command to print out numbers
.byte b_dolit_s8, -120, b_dot
.byte b_dolit_s8, 104, b_dot, b_newline, b_type
.byte b_bye
### 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
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
lodsb
movsbl %al, %eax
push %eax
jmp next
defasm dolit_32 # more general dolit
lodsl
push %eax
jmp next
defasm exit # Return from a colon defn.
xchg %ebp, %esp
pop %esi
xchg %ebp, %esp
jmp next
defasm 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
pop %eax
and %eax, %eax
jz branch
inc %esi # skip 1-byte jump offset
jmp next
defasm branch
lodsb
movsbl %al, %eax # same insn size as cbtw; cwde
add %eax, %esi
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
pop %ebx
pop %eax
mov %al, (%ebx) # push and pop don't do bytes
jmp next
# Fetch a byte.
defasm c_at
pop %ebx
xor %eax, %eax
mov (%ebx), %al
push %eax
jmp next
# Get the return stack pointer.
defasm rp_at
push %ebp
jmp next
# Set the return stack pointer.
defasm rp_bang
pop %ebp
jmp next
# Pop the return stack to the data stack ( R> )
defasm rpop
push (%ebp)
lea 4(%ebp), %ebp # add or xchg/pop: same size
jmp next
# Push the return stack from the data stack ( >R )
defasm rpush
lea -4(%ebp), %ebp
pop (%ebp)
jmp next
# Get the data stack pointer (before it gets pushed).
defasm sp_at
push %esp # safe on 286 and later
jmp next
# Set the data stack pointer.
defasm sp_bang
pop %esp
jmp next
# Pop the stack.
defasm drop
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
push (%esp)
jmp next
# Swap top two stack items ("exch" in PostScript)
defasm swap
pop %eax
pop %ebx
push %eax
push %ebx
jmp next
# Stack manipulation ( w1 w2 -- w1 w2 w1 )
# technically not necessary, but it's so easy and tiny
defasm over
push 4(%esp)
# jmp next fall through because "next" is 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
pop %eax
cdq
push %edx
jmp next
# Bitwise operators:
defasm and
pop %eax
pop %ebx
and %ebx, %eax
push %eax
jmp next
defasm or
pop %eax
pop %ebx
or %ebx, %eax
push %eax
jmp next
defasm xor
pop %eax
pop %ebx
xor %ebx, %eax
push %eax
jmp next
# add two unsigned numbers, returning sum and carry.
# ( u1 u2 -- u3 cy )
defasm umplus
xor %ecx, %ecx
pop %eax
pop %ebx
add %ebx, %eax
rcl $1, %ecx
push %eax
push %ecx
jmp next
# 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
push %edx
push %eax
jmp next
# Copy the top of the return stack onto the data stack.
# May be the traditional Forth word "I".
defasm r_at
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
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
push %eax
mov -4(%ebp), %esi
jmp next
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
.macro def name, bytes:vararg
defbytes \name
.byte \bytes
.byte b_exit
.endm
.data 2 # separate subsection from token table
bytecode_start:
# System call with three arguments.
def syscall3, b_zero, b_zero, b_syscall5
# System call with one argument.
def syscall1, b_zero, b_zero, b_syscall3
def bye, b_dolit_s8,__NR_exit, b_zero, b_syscall1 # exit program
def zero, b_dolit_s8,0 # push 0
def one, b_dolit_s8,1
# This word outputs a string whose address and count are on
# the stack. ( b u -- )
defbytes 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 make_counted_string name, contents
defbytes \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_dolit_s8,string_length_\name, b_exit
.pushsection .rodata # define the actual string:
string_\name:
.ascii "\contents"
## Here we count the length of the string --- computers
## are for counting bytes so people don't have to!
string_length_\name = . - string_\name
.popsection
.endm
make_counted_string hello, "hello"
make_counted_string world, "world"
make_counted_string comma, ", "
make_counted_string newline, "\n"
### Some More Basic Words
def neg1, b_dolit_s8, -1 # ( -- -1 )
def add, b_umplus, b_drop # ( a b -- a+b ) drop the carry
def sub1, b_neg1, b_add # ( n -- n-1 )
def rot, b_rpush, b_swap, b_rpop, b_swap # ( a b c -- b c a )
def unrot, b_rot, b_rot # ( a b c -- c a b )
def 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
.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 # print space after number
.byte b_udot_nospc, b_dolit_s8, 0x20, b_emit, b_exit
defbytes udot_nospc # print number without space
.byte b_dup, b_branch_on_0,2, b_udot_nonzero, b_exit
.byte b_drop, b_dolit_s8, '0, b_emit, b_exit
defbytes udot_nonzero
.byte b_zero, b_dolit_s8,10, b_divmod # divide by 10
.byte b_dup, b_branch_on_0,3, b_udot_nonzero # recurse if nonzero
.byte b_branch,1 # else
.byte b_drop # drop zero quotient
.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 not: return true for 0, false (0) otherwise
#def zeq, b_branch_on_0,2, b_zero, b_exit, b_neg1
# logical bitwise not
def invert, b_dolit_s8, -1, b_xor
def add1, b_one, b_add
# arithmetic negation
def negate, b_invert, b_add1
# print signed number
defbytes dot
.byte b_dup, b_negative, b_branch_on_0,4
.byte b_dolit_s8, '-, b_emit, b_negate # in the negative case
.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.
