George Peter Staplin: I read the page Scripted Code Generation and noticed that there wasn't any machine code generator/assembler, so I came up with some code over the period of two days.
First I needed a way to allocate executable memory, so I borrowed code from my Perpheon project for alloc_exec_mem() and free_exec_mem() which uses mmap() where appropriate. My next step was to design an API for appending instructions to the mmap'd memory.
Here is the API provided for interfacing with the mmap'd memory:
#define cmd(func,name) \ Tcl_CreateObjCommand (interp, name, func, (ClientData) NULL, (Tcl_CmdDeleteProc *) NULL) cmd (asm_align, "asm.align"); cmd (asm_alloc, "asm.alloc"); cmd (asm_append_byte, "asm.append.byte"); cmd (asm_append_int, "asm.append.int"); cmd (asm_execute, "asm.execute"); cmd (asm_fetch_offset, "asm.fetch.offset"); cmd (asm_free, "asm.free"); cmd (asm_subtract_offsets, "asm.-.offsets"); cmd (asm_store, "asm.store"); #undef cmd
As you can see, it's quite minimal. I then began the work of reading the Intel manual for finding the codes needed. I used the Intel manual to analyze code like:
s:
asm ("movl $-1,(%esp)");
e:
dump_bytes (stderr, &&s, (&&e - &&s));I wanted my assembler to be more structured than a bunch of gotos, so I borrowed from Forth the constructs IF/THEN. I however prefer the terms THEN/OTHERWISE because they make more sense (to me).
Consider code like:
1 2 < then 5 6 7 otherwise
The 1 and 2 get pushed. < pops 2 and compares and pushes a result of the comparison. "then" pops and compares to 0 and if the comparison is true it jumps to the position of otherwise. During the compilation of then/otherwise, "then" appends some code for the pop and 0 comparison, and then two values are pushed onto a compile-time stack so that we can fill in the relative amount to jump for reaching the position of "otherwise". As "otherwise" is run it pops two addresses off the stack and stores the difference into the memory, so that we know where to jump. The end result is that THEN/OTHERWISE constructs may be nested.
You can download a tarball here: http://www.xmission.com/~georgeps/implementation/software/asm/ (latest is release 4. It works in NetBSD 2.0 x86 and should work with other systems (with minimal makefile changes).)
I wrote the sources using Fed Builder; which greatly reduced the amount of time needed. There is only one file to compile, because the others are #include'd.
Here is the core of the assembler:
load ./asm.so
set ::ops(+) add
set ::ops(-) sub
set ::ops(<) less_than
set ::ops(>) greater_than
set ::ops(drop) drop
set ::ops(dup) dup
set ::ops(otherwise) otherwise
set ::ops(then) then
#R1 is %eax
#R2 is %ecx
set ::ADD_R1_STACK "\x01\x04\x24"
set ::COMPARE_R1_TO_R2 "\x39\xc1"
set ::DROP "\x83\xc4\x04"
set ::DUP "\x8b\x04\x24\x50"
set ::JUMP_EQUAL_RELATIVE_INT "\x0f\x84"
set ::JUMP_GREATER_THAN_RELATIVE_INT "\x0f\x8f"
set ::JUMP_LESS_THAN_RELATIVE_INT "\x0f\x8c"
set ::JUMP_RELATIVE_INT "\x0f\x84"
set ::MOVE_0_INTO_TOP "\xc7\x04\x24\x00\x00\x00\x00"
set ::MOVE_0_INTO_R2 "\xb9\x00\x00\x00\x00"
set ::POP_INTO_R1 "\x58"
set ::POP_INTO_R2 "\x59"
set ::PUSH_WORD "\x68"
set ::SUB_R1_STACK "\x29\x04\x24"
set ::assemble_stack [list]
proc add exe {
asm.append.byte $exe $::POP_INTO_R1
asm.append.byte $exe $::ADD_R1_STACK
}
proc drop exe {
asm.append.byte $exe $::DROP
}
proc dup exe {
asm.append.byte $exe $::DUP
}
proc greater_than exe {
asm.append.byte $exe $::POP_INTO_R1
asm.append.byte $exe $::POP_INTO_R2
asm.align $exe 3
asm.append.byte $exe $::PUSH_WORD
asm.append.int $exe -1
asm.append.byte $exe $::COMPARE_R1_TO_R2
asm.append.byte $exe $::JUMP_GREATER_THAN_RELATIVE_INT
asm.append.int $exe 7
asm.append.byte $exe $::MOVE_0_INTO_TOP
}
proc less_than exe {
asm.append.byte $exe $::POP_INTO_R1
asm.append.byte $exe $::POP_INTO_R2
asm.align $exe 3
asm.append.byte $exe $::PUSH_WORD
asm.append.int $exe -1
asm.append.byte $exe $::COMPARE_R1_TO_R2
asm.align $exe 2
asm.append.byte $exe $::JUMP_LESS_THAN_RELATIVE_INT
asm.append.int $exe 7
asm.append.byte $exe $::MOVE_0_INTO_TOP
}
proc otherwise exe {
set s [pop]
set e [asm.fetch.offset $exe]
set jmp_addr [pop]
asm.store $jmp_addr [asm.-.offsets $e $s]
}
proc pop {} {
set r [lindex $::compile_stack end]
set ::compile_stack [lrange $::compile_stack 0 end-1]
return $r
}
proc push val {
lappend ::compile_stack $val
}
proc sub exe {
asm.append.byte $exe $::POP_INTO_R1
asm.append.byte $exe $::SUB_R1_STACK
}
proc then exe {
asm.append.byte $exe $::POP_INTO_R1
asm.append.byte $exe $::MOVE_0_INTO_R2
asm.append.byte $exe $::COMPARE_R1_TO_R2
asm.append.byte $exe $::JUMP_EQUAL_RELATIVE_INT
push [asm.fetch.offset $exe]
asm.append.int $exe 0
push [asm.fetch.offset $exe]
}
proc asm.assemble s {
set exe [asm.alloc]
foreach i [split $s] {
set i [string trim $i]
if {"" eq $i} continue
if {[string is integer $i]} {
asm.append.byte $exe $::PUSH_WORD
asm.append.int $exe $i
} else {
$::ops($i) $exe
}
}
return $exe
}
proc main {} {
set exe [asm.assemble {
5 10 <
then
4 5 +
8 >
then
1234
otherwise
otherwise
}]
puts [asm.execute $exe]
asm.free $exe
}
mainHere is a dump of the bytes generated and the result of running the code above:
BEGIN DUMP [0] = 0x68 = 104 = h [1] = 0x5 = 5 [2] = 0x0 = 0 [3] = 0x0 = 0 [4] = 0x0 = 0 [5] = 0x68 = 104 = h [6] = 0xa = 10 [7] = 0x0 = 0 [8] = 0x0 = 0 [9] = 0x0 = 0 [10] = 0x58 = 88 = X [11] = 0x59 = 89 = Y [12] = 0x68 = 104 = h [13] = 0xff = 255 [14] = 0xff = 255 [15] = 0xff = 255 [16] = 0xff = 255 [17] = 0x39 = 57 = 9 [18] = 0xc1 = 193 [19] = 0x90 = 144 [20] = 0xf = 15 [21] = 0x8c = 140 [22] = 0x7 = 7 [23] = 0x0 = 0 [24] = 0x0 = 0 [25] = 0x0 = 0 [26] = 0xc7 = 199 [27] = 0x4 = 4 [28] = 0x24 = 36 = $ [29] = 0x0 = 0 [30] = 0x0 = 0 [31] = 0x0 = 0 [32] = 0x0 = 0 [33] = 0x58 = 88 = X [34] = 0xb9 = 185 [35] = 0x0 = 0 [36] = 0x0 = 0 [37] = 0x0 = 0 [38] = 0x0 = 0 [39] = 0x39 = 57 = 9 [40] = 0xc1 = 193 [41] = 0xf = 15 [42] = 0x84 = 132 [43] = 0x3c = 60 = < [44] = 0x0 = 0 [45] = 0x0 = 0 [46] = 0x0 = 0 [47] = 0x68 = 104 = h [48] = 0x4 = 4 [49] = 0x0 = 0 [50] = 0x0 = 0 [51] = 0x0 = 0 [52] = 0x68 = 104 = h [53] = 0x5 = 5 [54] = 0x0 = 0 [55] = 0x0 = 0 [56] = 0x0 = 0 [57] = 0x58 = 88 = X [58] = 0x1 = 1 [59] = 0x4 = 4 [60] = 0x24 = 36 = $ [61] = 0x68 = 104 = h [62] = 0x8 = 8 [63] = 0x0 = 0 [64] = 0x0 = 0 [65] = 0x0 = 0 [66] = 0x58 = 88 = X [67] = 0x59 = 89 = Y [68] = 0x68 = 104 = h [69] = 0xff = 255 [70] = 0xff = 255 [71] = 0xff = 255 [72] = 0xff = 255 [73] = 0x39 = 57 = 9 [74] = 0xc1 = 193 [75] = 0xf = 15 [76] = 0x8f = 143 [77] = 0x7 = 7 [78] = 0x0 = 0 [79] = 0x0 = 0 [80] = 0x0 = 0 [81] = 0xc7 = 199 [82] = 0x4 = 4 [83] = 0x24 = 36 = $ [84] = 0x0 = 0 [85] = 0x0 = 0 [86] = 0x0 = 0 [87] = 0x0 = 0 [88] = 0x58 = 88 = X [89] = 0xb9 = 185 [90] = 0x0 = 0 [91] = 0x0 = 0 [92] = 0x0 = 0 [93] = 0x0 = 0 [94] = 0x39 = 57 = 9 [95] = 0xc1 = 193 [96] = 0xf = 15 [97] = 0x84 = 132 [98] = 0x5 = 5 [99] = 0x0 = 0 [100] = 0x0 = 0 [101] = 0x0 = 0 [102] = 0x68 = 104 = h [103] = 0xd2 = 210 [104] = 0x4 = 4 [105] = 0x0 = 0 [106] = 0x0 = 0 END DUMP executing r 1234