Raw source and immediate archive at
http://www.icculus.org/~phaethon/plan/Entries are currently sorted in: Newest First
Syntax (time and date in UTC, my local timezone is PST/PDT):
[YEAR].[MONTH].[DAY] <space> ~[APPROX. HOUR] <space> <space> [SUMMARY]
<empty line>
[CONTENT]
<empty line>
<empty line>
2003.03.13 ~04 Triseism - standalone Q3VM interpreter
http://www.icculus.org/triseism/Standalone Q3VM interpreter. Most of the workings of a stack-based
machine became clearer when I brushed up on Forth. And Forth didn't
make much sense until after I learned Lisp. After learning lisp, the
idiosyncrancies of python became understandable.
Q3VM sets aside 64KB total for stack. Forth uses two stacks. If Q3VM's
stack is split in two (which I'm not absolutely certain on, but makes
sense), to mirror the two Forth stacks, this gives a limit of 32KB for a
stack frame. This limit is enforced by q3lcc at compile time, and I've
always wondered why 32KB in particular. Looks like the run-time stack
is involved.
Some of the emulation techniques I borrowed from my experience on PHFC,
the CUSP emulator. And from hacking on q3asm, the opcodes were fairly
transparent. I created and compiled many very simple programs to see
the translations of C source into Q3VM asm.
The Q3VM syscalls are a bit of a zinger. For one, I can't possibly
implement ALL the syscalls -- this would basically lead to rewriting Q3.
The other problem is that Q3 has three sets of syscalls, one each for
game (server-side), cgame (client-side), and ui (client-side menus).
I'm thinking of using a dlopen() system to optionally load one set of
syscalls over another. Splitting off the syscalls package would also be
helpful in utilizing triseism as a general-purpose sandboxed VM.
The other problem I'm having is the mysterious two words allocated on
the (return) stack upon entering a procedure. Local storage starts
after these two words, so the two words are likely involved with the
return process.
I'm thinking of distilling triseism into a library. One of my
motivations for finishing this was an acquaintance's desire for being
able to load a .qvm in another app, as one would open a dll.
In other possibilities, since the opcodes of the Q3VM are now very
clear, it should be possible to compile Lisp directly to qvm bytecode,
bypassing any C translations or C compilation, i.e. foo.l -> foo.qvm.
Also, I'm certain gcc and the gnu toolchains to can be hacked to compile
directly to .qvm.
Implementing a dll system within Q3VM is doable, but would probably need
changes to the .qvm format. The current .qvm format discards the symbol
table, precluding any dynamic symbol resolution.
Since triseism is developed independently of Q3 proper, triseism isn't
bug-for-bug compatible with idsoftware's Q3VM. This means triseism may
not mimick every tiny detail of Q3VM down to the fiddling of bits.
Triseism may help in tracing an execution path through a Q3 mod, but
without debugging symbols, there isn't a simple way to link an
instruction location with its matching line of C source.
2003.02.05 ~09 snes9x console
http://www.icculus.org/~phaethon/snes/console.htmlI started on this hack the day before shuttle Columbia disintegrated.
Motivation to hack this up came from several places. Primarily, I
wanted arbitrary bindings of the buttons on my gamepad (Thrustmaster
FireStorm Dual Analog 3) for use in snes9x. A strong impetus came from
ZSNES and its GUI. I liked the immediacy of changing key binds and
fiddling with options in zsnes. In snes9x, changing options meant
saving game state, quitting, futzing with command-line options,
starting, and restoring state.
Another source of inspiration was Brad Jorsch's control-remapping patch,
which is applied to the Debianized snes9x package. I thought the
configuration file for that to be rather clumsy, and it didn't bind
joystick axes and buttons.
The notion of a console came from Quake (1, 2, 3) and Unreal Tournament
(pre-2003). I settled on mimicking Quake's console since (a) I am
familiar with Quake III's console, and (b) snes9x lacks the underlying
objects, widgets, and language system to mimick Unreal's console. Also
Quake's console is based on a command language, simpler than Unreal's
more advanced Algol-family language. I mimicked most of the
functionality and commands found in Quake's console, with various
extensions of commands and cvars appropriate for snes9x.
The cvars that affect emulator settings are not directly tied to their
associated C++ variables. Rather, there are explicit calls to
synchronize the values between cvars and their variables. Somewhat
inefficient, but saved massive refactoring.
FlightGear has an interesting configuration system. A key binding
describes how a particular "FlightGear property" is modified. For
example, swapping values with another property, incrementing the
property by a certain amount, or _conditionally_ setting the value of
one property based on the value of another property, at key press or key
release. Bindings for (analog) joysticks are described in the same
syntax, but describes a formula for translating the joystick position
into a property value, using a scaling factor, an offset value, and a
"dead-zone" range.
Anyway, FlightGear's binding of analog joysticks inspired me to figure
out a way to incorporate axis-handling in the new snes9x console. I
spent much time thinking over keys, input, and key states. Often, the
state of a key is treated as a boolean, as either true (pressed) or
false (released). I thought of an axis of a directional (digital) pad
as being one key with three possible states: 0, positive, and negative
(i.e. left and right do not occur at the same time on a joystick). In
the case of an analog axis, there would need to be continuous values on
either side of 0. At first, I considered using floating-point values,
i.e. -1.0 for one end, +1.0 for the other, and fractional values to
represent intermediate axis positions. Well, due to some inconsistency
in the cvars mechanism at the time with float-point values, I wanted to
stay away from floats. That's when I remembered joystick calibrators
worked with integers, where 32767 represented maximum and -32767
minimum. So I went with integer-only values for a key state. For
regular keys, the state would still be 0 or 1, but for axes, would be a
value from -32767 through +32767.
In Tribes 2, a key is bound to a function -- a key handler. This
function is passed one parameter, a value of either 0 or 1, indicating
whether the function was called because the key was released (0) or the
key was pressed (1). I never dealt with joystick handling in Tribes 2,
but a reasonable extension would be an axis-handler function being
passed a value indicating the axis position.
Quake III supplies commands linked to action primitives, in a "start"
and a "stop" flavor. For example, "+attack" means start firing, and
"-attack" means stop firing. If a key is bound simply to just
"+attack", when the key is released, Quake III automagically runs the
command "-attack" (i.e. replaces the '+' with a '-'). The '+'-'-'
swapping is apparent with a simple test: "/bind SPACE +crap". Hit Space,
and the Q3 console complains about not finding "+crap" nor "-crap". The
complaint about "-crap" happens when Space is released.
A while ago, in an attempt to extend the Q3 console capability to be
more shell-like, I added an "alias" capability. This capability allowed
a cvar to run as a command without need for an explicit "vstr". The
basic idea was, for some alias named "foo", to prefix it with an
ampersand, "&foo". Should the Q3 engine fail to understand a command
(and pass it off to Q3VM code), the VM code tries to find a cvar
matching the unknown command's name, but with a leading ampersand.
Then, on a successful match, runs the cvar's content as a command.
I took this idea over to the snes9x console. The primary goal was to
have a bind named "+turbokey", defined entirely in terms of commands
(instead of C++ code). This alias would then be bound to Tab, such that
holding down Tab puts the emulator into "fast-forward mode" (skipping
boring/useless/pointless parts of a game), and releasing Tab returns the
emulator to "normal" speed.
Most of the keynames were ripped from Quake III. Q3 basically goes off
on its own naming system for high-bit key, so there had to be a way to
map the host key to Q3's (or rather, snes9x console's). This comprises
the most massive patch to files outside of the console/ directory --
just mapping host keys to s9xconsole keys.
I didn't want to mimick FlightGear's axis handling completely. One
problem I have with FlightGear's joystick handling is the complexity
involved in trying to control the throttle properly with an
auto-centering joystick (i.e. a little push to increase a little, big
push to increase a lot, instead of the throttle every time the joystick
auto-centers). The Tribes 2 style was more attractive, but that meant
having some primitive form of conditional and flow control.
That got nasty. I don't want to get into it, other than the commands
for conditional and flow control are more reminiscent of assembly than
any kind of HLL.
I implemented a primitive form of multitasking to deal with rapid-fire
(press, release, repeat, but if the console doesn't yield to the rest of
the emu, the emu never gets to see the buttons) and a primitive form of
multithreading to deal with infinitely-looping commands. Also, as part
of rapid-fire, I had threads record the key that initiated the thread.
Then the thread manager kills off all threads associated with a key
whenever its state changes (e.g. killing rapid-fire loop on release).
Originally I had a cvar named "axisval" that records the axis position
for the AXISn "keys" (analog axes). One AXIS bind could make several
comparisons to the cvar, but then the multithreading meant another AXIS
bind would then change value of "axival", before the first thread manage
dall its comparisions. Race condition. I resolved this by attaching
the axis number to the end of the cvar name, so that each AXIS bind has
its own associated cvar (instead of one cvar shared across them all).
So, now, any of the three joysticks on my gamepad (one D-pad, two
ministicks) can emulate the SNES Directional-Pad.
2003.01.22 ~10 Random thought: shell as "action-oriented programming"
Stumbled across this thought while pondering config/rc files.
Object-oriented programming, as in C++, usually has a form of:
OBJECT <delim> METHOD <delim> ARGUMENT1 ARGUMENT2
(object first, a method in that object, arguments to pass to the method)
e.g. foo->bar(0), bonk.oif(quux, quuux, quuuux), $fred->yabba(dabba, doo)
Shell programming, when typed out, usually has a form of:
COMMAND <delim> OBJECT1 OBJECT2 ...
(command first, then objects to operate upon)
e.g. rm -rf /, mv foo bar, touch this that private pubic lockfile
Of course, shell programming can get much hairier. But if shelling can
be considered "action-oriented programming", that'd be some kind of
fit-the-slot counterpart to OOP.
Just a random thought.
2003.01.12 ~03 WFA dead
Lead coder for Q3 mod WFA called it quits. The alternate coder is
throwing the mod into the freezer, never mind the back burner. The new
project leader can't touch the WFA sources.
It's essentially dead.
I may take up coding WF for Q3 from scratch, separate from my FI mod,
for speed/time reasons. For those same reasons, I may have to abandon
much of what I consider "good coding style" to churn out results.
2003.01.07 ~08 X10 Firecracker
Got one of those X10 Firecracker starter kits. The halogen lamp I
intend to control is rated 500W, so I had to purchase a separate
500W-capable X10 module. The transceiver that comes with the kit is
capable of 500W, but the lamp's socket is rather far from the 'puter.
The 300W dimmable module that came with the kit is currently unused. We
have no pluggable lamps under 300W.
The Firecracker dongle is tiny. I expected it to be at least half the
size of an average X10 module (which in itself is about the size of a
typical AC/DC power adapter). The Firecracker is small enough to be
mistaken for a mismanufactured serial gender-bender.
The Firecracker connects on the (9-pin) serial port and is a write-only
gadget. Lack of read ability is no matter, as I can get direct feedback
of any X10 action by turning my head.
Curently, to drive the Firecracker, I'm using Bottle Rocket. I have
GNOME launchers to control the lamp, for gawk-and-click controls.
2003.01.04 ~10 mark-and-partial-sweep garbage collection
This turned out to be an interesting hack to the mark-and-sweep gc. For
some reason, TinyScheme partitions its heap into N segments of M cons
cells. This appears inexplicable, as TinyScheme is hard-coded to use
only 3 of the segments and refuses to use any more segments (short of an
explicit procedure call to "new-segment").
I decided to use this inherent partitioning of the heap for a partial
sweep mechanism. Partly inspired by incremental-style garbage
collection (superset of "multi-threaded garbage collection"), the idea
was to sweep one segment per Q3 frame, so that the time to sweep up all
the garbage is spread out over a long time, interpersing regular Scheme
processing. This depends on the sweeper recovering garbage faster than
Scheme allocating space, which is most of the time (recovering up to M
cells per frame, vs allocating perhaps a dozen cells per frame). Each
module's vmMain() would need to call the partial sweeper once per frame
or somehow ensure the sweeper gets called frequently per second.
A problem is that in between partial sweeps, Scheme can still request
additional cells. By default, TinyScheme does not initiate garbage
collection until the heap is entirely exhausted. With this behavior,
Scheme may wind up requesting cells when the sweeper has barely started,
triggering another mark+sweep cycle. The free-at-exhausted behavior is
also annoying as it tends to lead to lost symbols and bindings (no
chance to establish a path from a root cell). As a workaround, I
changed TinyScheme to initiate garbage collection after the freelist
dips below a certain low mark, which is currently half a segment's size.
This way, fresh objects get a chance to join the marked tree, and the
allocator gets "padding" to keep Scheme satisifed as the sweeper starts.
I also had the sweeper watch for "extremely tight memory situations".
This would happen should Scheme allocate a very large chunk of memory
right after a mark pass (just as partial sweeping start). Since
sweeping when freelist hits zero tends to cause lost objects, I wanted
a non-zero panic point. Should the freelist drop below the panic point,
the sweeper goes into aggressive full-heap sweeping. Lacking a
reference for this panic point, I chose a random number, 42.
Empirically, on my K7/1200, with N=32 and M=32768 (total 1MiB), mark
phase takes about 5ms, and a partial sweep of one segment takes 18ms,
with a full-heap sweep taking a little under 600ms.
Wishlist items: somehow automagically setting partial sweep to stop
after a certain time threshold. One hack is to continually sample
elapsed time, but the call to get the time (a Q3VM trap) takes up
processing time. A better method would be to calculate the cells-per-ms
rate, then using an appropriate number-of-cells to finish a partial
sweep within time, but that method is more complicated.
2003.01.03 ~20 Showstopper in Scheme UI
Just ran across two showstopping bugs in implementing the entire ui
module in Scheme. The current garbage-collector algorithm is
mark-and-sweep. Even with a heap of 1MB, every gc cycle takes a
noticeable time to complete. This produces a heartbeat-like lag
pattern, where the entire UI just freezes up as the heap is marked and
swept. A clean solution is to use a garbage collector better suited to
realtime interactive use.
The other showstopper, partly related, is that due to the way TinyScheme
manages memory (to wit, symbols are not garbage-collected), the Scheme
subsystem eventually exhausts the heap after running the ui module for a
moderate time. Once the heap exhausts, anything can happen. Usually Q3
abends.
I'm thinking about falling back to my prior UI idea, which describes the
menus in S-expressions and uses Scheme as a Turing-complete language for
the more complex UI behaviors. This way, the most frequent actions
(drawing, repositioning, etc.) can be done in C or something, and leave
the less frequent actions (fancy animation, commands-wrapping) to Scheme
(less frequent garbage collecting).
Life: No Life found.
Project:
1. Project FI, Quake 3 mod (
http://www.icculus.org/fi/)
a. provide an extensible environment for a Q3 mod. The intended notion is that of "mutators" in Unreal Tournament.
b. FI:WFC, a more faithful reproduction of Q2WF for Q3 than WFA.
2. QuakeScheme
* Extensible language for Project FI.
* Builds on TinySCHEME (
http://tinyscheme.sourceforge.net/)
* Deal with idiosyncrasies of Q3VM not handled by most other Scheme impls.
3. Q3VM libc
* Implementation of Standard C Library for Q3VM bytecode.
* Implementation of a subset of Single Unix Specification v2 (SUS v2).
* Help import third-party library into Q3VM.
4. QS GUI/widget set
a. Need to research advanced OO and GUI of Scheme derivatives and Common Lisp.
b. Replication/extension of boxy widgets in Q3TA (Q3 PR 1.27+).
c. Pie menus -- just to annoy theoddone33.
5. Q3 compilation toolchain
[X] q3lcc sources (official version out with Q3A SDK 1.32)
[X] q3asm - get static to work, dammit.
[ ] q3as - assemble-only (.asm to .o).
[ ] q3ld - link-only (.o/.a to .qvm).
5. PalmOS stuff
a. PiNGer (gfx viewer)
* generalize interface to a "any-gfx" viewer (libpnm?)
b. ZBoxZ (file manager)
* beef up its appness: menus, dialogs, pen actions