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>
2002.10.29 ~04 Splay tree, a more complex tree structure
OK, because of this q3asm thing, I'm suddenly in a tree mood.
Apparently in my textbook, three chapters after the one on R-B and A-A
trees, is splay tree. This may be a(n overkill) solution for my opcodes
worries. Basically the idea of a splay tree is to repeatedly split
apart the tree and glue them back together in different ways such that
more frequently-accessed elements rise towards the root (and thus
cheaper for *future* accesses), while still maintaining the tree's
order. The penalty here is that worst-case scenario is much much worse
than RB/AA tree, on the hopes that average-case, for the more frequent
nodes, gets better. And all that splitting/splaying also costs.
The idea is to spread out the cost of the few worst-case accesses across
many very-good-case accesses (this is where the term "amortize" comes
in, but I'm still not sure exactly what the definition of the word is).
Of course, this depends on there being *some* "frequent nodes".
Apparently the cost of splay trees is horrendous for purely-random
accesses. Fortunately, (functioning) assembly doesn't involve throwing
together random opcodes in random sequences.
The splay tree, in some ways, reminds me of Huffman coding, where the
more frequent sequences use fewer bits than less-frequent sequences. Or
of caches, scoring big wins for frequently accessed memory. Splay tree
would dynamically re-arrange itself so that the more freqently sought
node cost less to find than less frequently sought nodes.
Splay tree may also be a good idea for the symbols tree, as there are
likely to be some symbols accessed more frequently than others. For
example, g_entities[], the list of all entities in the game world.
2002.10.29 ~01 Bring back hashtable to q3asm-turbo?
Just now I bothered looking at the numbers related to q3asm-turbo's data
structures. For my mod, the hashtable q3asm-turbo had these numbers:
Symbol hash: 17819 nodes, longest chain = 45, mean non-empty = 9.320
Opcode hash: 95 nodes, longest chain = 3, mean non-empty = 1.484
The Bal.Bin.Tree implementation has these numbers:
Symbol tree: 17819 nodes, tree height = 19
Opcode tree: 95 nodes, tree height = 10
Export tree: 26515 nodes, tree height = 21
In the optimal case the symbol tree would have a height of 15 (log2 of
17819), and the opcode tree would have height of 7. The height of the
tree represents worst case time for searching.
In the hashtable implementation, the longest chain indicates worst-case
time for search, and the mean average roughly corresponds to mean
(average) search time. Within each chain in the hashtable, though,
sorting is done by linear-time insertion sort, and thus the major
portion of cost. The thing is that the opcode hash has a longest chain
of 3. This is next to squat (almost constant) for sorting and
searching. Meanwhile, the opcode tree has a height of 10, worst case
searching is visiting 10 nodes. In the tree, only 15 opcodes would be
reachable in 3 hops, while any opcode in the hashtable can be reached,
guaranteed, within 3 hops.
The question here is if I should resurrect the hashtable specifically
for the opcodes. Trees have major wins in the large-amount-of-data
department (due to reduced insertion costs), but hashing seems to win in
small-sets-of-data.
2002.10.29 ~00 q3asm "static" and balanced binary tree done
http://www.icculus.org/~phaethon/q3a/q3asm-turbo/q3asm-turbo.htmlhttp://www.linux.ucla.edu/~phaethon/q3a/q3asm-turbo/q3asm-turbo.htmlI did it. Two birds with... uh... two stones. Two separate forked
updates. The first is just a straight port of the old q3asm to the 1.32
SDK, so that patch(1) stays quiet. The second has some major mojo.
Firstly, I finally carried out my threat of moving the data structures
from hashtables to (balanced) binary trees. The speed improvement over
hashtables isn't very dramatic, but still noteworthy. Empirical testing
suggests a time decrease of 10% to 30% compared to hashtables. I'm too
lazy to set up millisecond-resolution timing, but it feels faster to me.
I actually cracked open my CS textbook and read through the trees
chapter for the nth time. I finally half-grok what's going on with the
rotations, but I'd be ****ed if I have to implement a R-B tree from
scratch on a blank screen without any references.
An added benefit of putting in trees is extra flexibility in additional
data... data... err... yeah, additional data. For example, a mapping
of private symbol names to public symbol names. Such as that implied by
the "static" keyword in C.
As I had priorly brainstormed, all symbols in a file are mangled based
on filename (actually, file index number, but close enough) to mimic
private namespaces. The "export" assembler directive, which takes as
the sole parameter the name of the local symbol to be made global,
creates a mapping such that the specified global name resolves to the
file's particular private symbol (name). The "import" directive acts
similarly, creating a mapping such that the local private symbol name
resolves to the global name, then recursively re-resolves to the
"actual" private symbol in the other file('s namespace). These mappings
are sorted and searched in a balanced binary tree. Good thing, too,
since there are upwards of 20K such entries.
Basically, it was a matter of mimicking private namespaces and shifting
names between those (fake) namespaces.
2002.10.28 ~09 Thoughts on Blender win32 build, and q3asm "static" keyword
+ Blender win32
Blender is a cross-platform app, so consistency dictates the build process
should remain cross-platform. The problem is that the primary compiler
used in win32 is Microsoft Visual... um... Studio? C++? Whatever.
(Whether this can be considered "the system's C compiler" is a topic of
another rant). The point stands that MSVC isn't very make(1)-unfriendly,
is very non-standard. The problem is that automake as-is does not work
well with MSVC as the C(++) compiler.
One solution is to attempt to conjure up the necessary MSVC files based on
the automake files. This method seems doable -- the tree structure of the
source is patterned enough to establish a build path even without the
automake files. The problem with this attempt is, again, non-standardism.
I can't grok the formats of the MSVC files (the ones packaged with the
Blender source tree). Or maybe I don't want to... but they seem just plain
weird. Primarily on issues such as whether those header lines are
critical, the sensitivity on whitespaces (valid chars and amounts), and wtf
are the comment delimiters. Oh yeah, and those crazy-ass backslash for
path separator.
Wonder if there's a grammar describing these .dsp (.dsw?) files.
+ q3asm
I have many reasons for wanting to split q3asm into two distinct programs,
q3as and q3ld. One is to assist the migration of q3vm compilation into GCC
later on (WAAAAAAY later on). Another is to allow use of library (.a)
files in Q3VM linking -- this helps cut down on reaching across
directories, as is currently done in cgame/ for obtaining bg_* (both games)
source files. Related is testing my libc reimplementation, to avoid
repeated recompilation and to test standalone worthiness (i.e. not
intimately linked to my mod). An offshoot to that is properly handling the
C keyword "static" (libc has stuff that really should be private).
I already started on a hack for "static" support, using the source filename
as a "tag" to symbol names, to make symbols unique to a particular source
file. This establishes private namespaces per file. The sticky part with
this method is trying to get globals to be globals. At some point the
filename-"tag" portion needs to be stripped (simple), and somehow resolve
to the unique still-tagged symbol (a little hairy), while ensuring no
conflicts (some more hair). The key to the breakthrough lies in the
assembler directives "import" and "export". The hard part is trying to
come up with the proper data structures to express this method of scoping.
I think I need to work out some more of this on paper.
I really want to shift q3asm's symbol table to a tree, for many reasons.
For one, trees would boost the speed some more (although the need is
arguable, as some people are getting reported time-elapsed of 0 seconds).
Second, the data structure and methods for trees are much neater than those
for a chain-and-bucket hash table. And finally, trees are just cool. For
speed reasons, the tree would need to be weight-balanced somehow. I would
like to just link to a tree library of some kind, but that would be an
extra burden on whomever wants to use the tree'd q3asm. So my options are
either to rip tree code and stuff 'em into q3asm, or dig through my CS
books again looking at the tree implementations. I understand the basic
concept of R-B tree, that the markings help keep the balance... but I just
get lost in all those rotations. :(
2002.10.27 ~06 improved RNG in Q3VM, Q3 1.32
+ Towards a better (Pseudo-)Random Number Generator.
http://www.icculus.org/~phaethon/q3a/nbrng/nbrng.htmlMy quest for a better RNG started in Quake 3 Urban Terror (q3ut) v2.5,
fueled by countless numbers of "Bullshit Incidents", aka "being 2.5'd".
I'm not in a position to improve q3ut myself (read: damn elitist "dev
group"), but the repeated 2.5'ing fired up my drive.
The stock random number generator in Q3A is a laughably deterministic
cyclic PRNG. Just multiplying the seed by 69069, storing the result back
into the seed, and then using the new seed value as the random number.
(Note: mods compiled to native code use the host OS's (P)RNG)
A google search for free RNG source turned up "noiz". The original noiz
acts like an ad-hoc system-wide RNG, using an entropy pool file in /etc (or
elsewhere) and explicit programs to take the pool, stirs the pool with
stdin, and writes back the altered pool; basically a shellified+disked
variant of an entropy collector.
My terminology is probably rather shoddily used and incorrectly applied,
since I just started to look into RNG. I never realized the breadth of
research on just figuring out how to *induce* randomness.
Anyway, I took noiz and modified it to be function+cvar based. The
function to actually collect entropy needs to be strategically placed
throughout the mod to correctly scoop up entropy, but otherwise the
noiz-based RNG is far more nondeterministic than the stock PRNG.
+ Quake 3 Software Development Kit v1.32.
ftp://ftp.idsoftware.com/idstuff/quake3/source/linuxq3a-sdk-1.32.x86.runSo, the new SDK to reflect the new Q3A mod (baseq3) source was released a
few days ago. Apparently most of the baseq3 changes involve
PunkBuster-related options, such as UI elements to turn it on/off. At
last id released their patched lcc, which compiles C to Q3VM assembly
(which is actually a variant on the lcc bytecode machine description).
As far as I can tell, the 1.32 q3asm doesn't have any speedups over the
prior (1.27?) version, although someone took the time to clean up the code
to keep gcc quiet.
+ PunkBuster
So now Q3 1.32 has PunkBuster. I have no idea what the basic principles
are behind it, but apparently it's supposed to reduce cheating somehow.
Since it (PB) deposits .so files on my (client) side, I presume these
checks are done client-side. One lesson I recall from the Q1 source
release is that anything run on client-side is totally untrustable, as
there is really no limit to what the client-side can "say". So I seriously
doubt PB can catch "all" or even "most" cheats, if it relies on this
client-side .so file to check for client-side... um... stuff.
Aside from that, I'm starting to notice strange lags in Q3. Now everything
feels like a 100+ ms lag, instead of the usual inherent 50ms lag. It
almost feels like CPU/client-side lag, but the framerate still pegs the
meter at high double digits. Everything, from baseq3 to ufreeze to q3ut2
to wfa, from extremely low ping to extremely high ping. Either the netcode
in Q3 1.32 has hit the shitter, or PunkBuster is stuffing Q3's face into
the shitter with extra net comm.
Neither one bodes well. Still, it would be extremely stupid if PunkBuster
maintains some kind of "out-of-bounds" channel _during_ gameplay, since
even so much as a rogue SYN packet can exponentially compound the lag on a
56K connection (a large segment of Q3 players, iirc) and completely ruin
the experience (of either side of 0wn@ge). But I find it harder to believe
Id would deliberately cripple the netcode in 1.32 sufficiently to make the
difference noticeable on a broadband connection. Which is it? Which way
would Occam's Razor cut?
2002.10.19 ~05 Blender web plugin problems
The last compilation stretch is the Blender GamePlayer web plugin. The
problem is that the plugin was initially developed using the API in Mozilla
1.0 (or earlier?). Debian unstable has the bins and dev files for moz 1.1.
Problems at compile time. My options at this point are hacking on the
plugin to use the 1.1 API (XPCOM in particular), fall back to moz 1.0 (via
cvs), or abandon the compiling plugin altogether and concentrating on the
preliminary ODE patch (physics engine) for Blender trunk.
Oh, fwiw, the original collision-detection library in Blender, SOLID, had
to be removed from the Open version due to licensing constraints. Yay
proprietary license.
2002.10.18 ~01 Blender Open-Source
Blender Liberated
The Blender source code is distributed under a dual GPL/not-so-GPL license.
Reminds me a bit of Mozilla. Freed 13 October 2002.
Blender Autoconfiscating
http://www.linux.ucla.edu/~phaethon/blender/blender-autoconf.htmlThe initial build environment was heavily broken/undocumented. It didn't
"out-of-the-box", so on Sunday night (localtime) I started rearranging
directories and files, and autoconfiscating the tree. Started late 13
October 2002. Hacking at it since. First I got a modelling-only Blender.
Then GameBlender eventually fell into the autostream. Now it's mostly
cleanup and tweaks. Hoping for a pub CVS repository on www.blender.org.
Blender Publisher semi-freeware
The v2.25 that was previously off-limits to non-bondaged users was released
in limited "freeware" style, um... yesterday, I think. RE'ing and
decompilation are still forbidden, but at least the "common rabble" can take
a stab at 2.25 without trying to figure out the compile path.
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)
[ ] 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