Much of the last few days has been spent in toying with data structures, and testing a few dozen hash functions for use with a simple hash table module. It’s actually the first time I’ve ever had to implement a hash table myself, lol. It’s a fairly simple creation built on top of chaining.

The perfect hungry mans analogy for those that know squat about data structures: let’s say you want to find a recipe for peanut butter cookies in a cook book. You could thumb through every couple pages of the book, looking for cookie recipes, or even flip over to the index in back, and depending on the quality of the index, hunt down by looking down the index and systematically checking all cookie references; linked lists and arrays more or less work similar. A hash table is more like a table of contents: you flip open the book, go to the ToC, and find the section with the cookie recipes, then flip to that page and start flipin’ every few pages until you find the one you want.

Hash tables work essentially the same way, you feed in the key (peanut butter cookies, yum), hash it down to an index to where you can find the target. Although hash functions that don’t collide (often enough to care) are possible, when you have to bind the generated index within a given size, the odds of several different keys sharing the same index skyrockets. So instead of a direct 1 to 1 mapping, you have a needle to which haystack mapping.

My implementation uses a dynamic array of bucket lists that are allocated with HashTableCreate(), each element is a list: every key is hashed then squashed down to the size. When a new key:value is inserted, it gets added to the bucket list. On look up, the key is hashed back to the same value in order to find the correct list, in which to hunt down the correct entry.

One reason I chose separate chaining, other then it fits with how my brain works; many schemes for open addressing (the alternative), feels more like something I would think up, in order to skip writing a hash table >_>. Although, I must admit the possibilities of  open addressing combined with quadratic probing are interesting; I’m more in favour of the chains. While I doubt my implementation is memory efficient—since the only two design goals were to be faster then a (pure) linear search and quick to hash out the code, it undoubtedly has it’s flaws. For the sake of testing how it effects the intended usage, I may try augment/replace the current behavior of prepending new entries to the lists with moving last requested keys to the head, or switch to using red-black trees in place of a linked list.

I spent several hours testing different hash functions, using a small input set of words and a larger system dictionary file for testing. HashTableCreate() allows one to specify which hash function should be used, and it’s possible to override with a user supplied one. In testing, I’ve found using hash functions created by people with a background in mathematics, works significantly better then my own, as duly expected lol. Other then dealing with hash function issues, the rest was a cake walk.

Building SpiderMonkey 1.8.0 rc1 on Windows XP with Visual C++ 2008 / 9.0

Finding this note in SpiderMonkies documentation was a huge NO NO for me, because a dependency on Autoconf 2.13 is *worse* then a dependency on Autotools in general.

As I said I would, I investigated Windows/MSVC builds with SpiderMonkey before completing and utterly refusing to ever use the thing ^_^. This is a summery of my findings.

A lot of people are still using Visual C++ 7.1/2003.NET or 8.0/2005 versions, while I however use the Express Edition of Visual C++ 9.0/2008 for Windows builds, which generally means no pre-compiled libs binaries are available. That’s ok, since I prefer to evaluate the buildability of a dependency before I commit to using it…. hehe. One perk of doing most of my coding under FreeBSD, no need to buy a Professional Edition of Visual Studio :-D. I think this post should apply to most versions of Microsoft’s compiler, +/- differences in compiler flags.

The proper build requires MinGW, MSys, GNU Make, and a suitable copy of Visual C++.

MSys is required because of UNIX tools, such as uname, sed, and countless others are used by the build system; which also seems to depend on GNU Make.

Open the Visual Studio command prompt, or call  %VS90COMNTOOLS%vsvars32.bat from your current cmd session (VS90 = 2008 fyi; adapt as needed for older/newer versions). Then execute a MSys RXVT terminal from that. You do that by running the msys.bat script in the MSys root with the -rxvt argument, example:

+> C:DevFilesMSYS1.0msys.bat -rxvt

which will close the cmd session and open RXVT.

Change over to the js/src directory of where you extracted SpideryMonkey to, and run make on the projects makefile:

bash $ pushd /C/DevFiles/Libraries/SpiderMonkey/1.8.0rc1/js/src/
bash $ make BUILD_OPT=1 -f Makefile.ref

The BUILD_OPT causes an optimised release build to be made, default seems to be debug builds; read the Makefiles and Wiki for details on that.

Now for an example app to test, to see if more then js.exe works!

bash $ cat > test.c

#include "jsapi.h"

/* The class of the global object. */
static JSClass global_class = {
    "global", JSCLASS_GLOBAL_FLAGS,
    JS_PropertyStub, JS_PropertyStub, JS_PropertyStub, JS_PropertyStub,
    JS_EnumerateStub, JS_ResolveStub, JS_ConvertStub, JS_FinalizeStub,
    JSCLASS_NO_OPTIONAL_MEMBERS
};

/* The error reporter callback. */
void reportError(JSContext *cx, const char *message, JSErrorReport *report)
{
    fprintf(stderr, "%s:%u:%sn",
            report->filename ? report->filename : "",
            (unsigned int) report->lineno,
            message);
}

int main(int argc, const char *argv[])
{
    /* JS variables. */
    JSRuntime *rt;
    JSContext *cx;
    JSObject  *global;

    /* Create a JS runtime. */
    rt = JS_NewRuntime(8L * 1024L * 1024L);
    if (rt == NULL)
        return 1;

    /* Create a context. */
    cx = JS_NewContext(rt, 8192);
    if (cx == NULL)
        return 1;
    JS_SetOptions(cx, JSOPTION_VAROBJFIX);
    JS_SetVersion(cx, JSVERSION_LATEST);
    JS_SetErrorReporter(cx, reportError);

    /* Create the global object. */
    global = JS_NewObject(cx, &global_class, NULL, NULL);
    if (global == NULL)
        return 1;

    /* Populate the global object with the standard globals,
       like Object and Array. */
    if (!JS_InitStandardClasses(cx, global))
        return 1;


    /* Your application code here. This may include JSAPI calls
       to create your own custom JS objects and run scripts. */

    /* Cleanup. */
    JS_DestroyContext(cx);
    JS_DestroyRuntime(rt);
    JS_ShutDown();
    return 0;
}


bash $ $ cl -nologo -DXP_WIN  -I.. -MD -Fetest test.c js32.lib
bash $ ./test.exe

footnote: that test.c is just the minimal app example from the user guide, here. Also note that using /dos style switches with cl under bash/rxvt, doesn’t seem to work (it’s converted to file names).

I’ll need to do some further testing but everything appears to be working fine.

Of geeks and logs

Took it ‘easy’ yesterday, played some games and the only work that got done, was fairly light debugging / library installing / feature adding. Originally I planned to setup expat, libxml2, and libxslt under MinGW/MSVC, but called it a night after expat. Found an interesting thread on Daemon Forums, which shows either I really need to get a life, or a good nights sleep.

Grabbed a trio of cookies, put on the simpsons, and went to bed early, around 0100R; the easier solution :-o.

Had a fair bit of trouble getting to sleep as always, but being winded helps. By a quarter to 0700R, I had already woken up three times :-/. It was a half past noon when I finally got out of bed, not being disturbed makes for an interesting opportunity to sleep like a log and enjoy crazy dreams lol.

For my p resent activities, I’ve merely worke don importing my Live Journal entries from February 2009, into Blogger. I don’t think I’ll make my goal of having it all done before 2010 arrives, but alas, it will get done eventually!

Local time is reading 01:40R, so it seems that I’ve survived another Christmas on this rock. Much of the day, has really been spent trying to avoid the holiday altogether, for all practical intents and purposes. At least I got plenty of C code written for my games :-/.

The only real good thing out of the day, was a the ecard a friend sent—my one smile of the day.

Yipee-Kai-Yay Terminus font now avail. on Windows !

As some no, after spending a night of debugging only to learn that I had typed structobj,member instead of structojb.member, after a 6-8 hour coding run, I went in search of a new font. The font I found, was Terminus, and ever since I have _absolutely fucking loved it_ in fact, I can’t even look at my terminal in another font without missing it.

When filing a bug report to the libmng folks, I left a comment in the bug entry about using a font where O != 0; then went in search of my dear terminus, and then found this and just had to install them :-D.

Terminus is my favourite font, but my only compliant has been needing X to actually enjoy it…. now that’s solved!

Here’s my notes from installing JPEG-7 on Windows

Take note: I install libraries into C:DevFilesLibrariesWhat; with compiler specific files dumped under sub folders, e.g. C:DevFilesLibrarieszlibmsvczdll.lib and C:DevFilesLibrarieszlibmingwlibzdll.a. Like wise, I leave a README.TXT file in the root, noting anything I will need to remember when it comes to using the library.

# build for Visual C++ 2008 / 9.0
> unzip "pathtojpegsr7.zip"
# I want it in jpegsrc for safe keeping
> mkdir jpeg
> move jpeg-7 jpegsrc
# use the corresponding .vcX files for version
> copy makeasln.vc9 apps.sln
> copy makejsln.vc9 jpeg.sln
> copy makewvcp.vc9 wrjpgcom.vcproj
> copy maketvcp.vc9 jpegtran.vcproj
> copy makervcp.vc9 rdjpgcom.vcproj
> copy makedvcp.vc9 djpeg.vcproj
> copy makecvcp.vc9 cjpeg.vcproj
> copy makejvcp.vc9 jpeg.vcproj
> copy jconfig.vc jconfig.h
# I'm using vcbuild, since I read .vcproj files in vim; you may want the IDE
> vcbuild /nologo jpeg.sln "Release|Win32"
...
> vcbuild /nologo apps.sln "Release|Win32"
# I put compiler specific files in a suitable folder
> mkdir ..msvc
> copy Releasejpeg.lib ..msvc
# jconfig.h is compiler specific, so we dump it in our compiler directory
> copy jconfig.h ..msvc
> del jconfig.h
# build for MinGW/MSys
$ pushd /C/DevFiles/Libraries/jpeg/
$ pushd src
# works for most packages
$ ./configure --prefix=/C/DevFiles/Libraries/jpeg/ --exec-prefix=/C/DevFiles/L
ibraries/jpeg/mingw/
$ make
$ make install
# move jconfig out of independent include and into compiler specific dir
$ mv ../include/jconfig.h

Now copy jerror.h, jinclude.h, jmorecfg.h, jpegint.h, and jpeglib.h into ../include/. Those are the portable headers, that won’t very based on compiler (MinGW/MSVC).

and here’s my notes file:

MinGW -> static link as normal
MinGW -> Use import library libjpeg.dll.a for dynamic linking with libjpeg-7.dll
MinGW -> Last build JPEG-7 on 2009-12-24

MSVC -> Can only static link agaisnt jpeg.lib; must use /MD
MSVC -> also add msvc/ to include path, for jconfig.h
MSVC -> Last build JPEG-7 on 2009-12-23

In all cases, add include + compiler folders to your include path.

Although my original plan for the day, was to spend it working on Stargella, I’ve not found time for it, and I’ve to much of a headache now to worry about it.

I got in some good SWAT action then set to work on dependency compiling and evaluation, getting the freetype and jpeg libraries built. It was excellent to see that the freetype folks know how to use autotools, something a lot of projects fail at; and that jpeg has an gone through insane hoops to make their package easily built, on virtually anything lol. Tomorrow is moving on to other libs that may be useful. Since the handling of model and map information, will likely be done through XML files, I also need to start evaluating XML parsers again; something I have absolutely no love for. Also, because of that, there’s no point in taking a few moments to write a simple config file parser, when the application requires an XML parser :-S.

Code wise, the main focus for the day was to be working on implementing a simple drop down console, but I haven’t had time to focus on it, due to the time and effort it takes to compile software in a Windows environment. Which is approximately 200% more trouble then a unix environment, or 90% higher if it’s a Linux application written by assholes who knew less about what they’re doing then the puts who wrote the tools 8=).

I’m interested in seeing what SDL_ttf can do for rendering the textual part of the console, but that requires freetype, lol. Freetype however is a very painless thing to setup under Windows, at least using MinGW and MSVC. Whether or not SDL_ttf will be so hunky dory, remains to be seen.

Also spent some time in evaluating the concept of using JavaScript as an embedded scripting language. Mozillas Spidermonkey seems to be the only engine that fits the bill: written in C. It’s also fairly portable and has one hell of a nice (JS)API , with out a doubt it’s gotta be a lovely way of embedding a language into your program. The only problem, the build system issues. I will explore it’s compilation under Windows but expect it to be a wash out. The comments about autotools alone, virtually make Spidermonkey something you can rule out of any sane programmers toolkit.  I’ve already learned about Python extension modules, but have never had time to look closely into embedding the interp into an application, but will do that also in time. Another thing to consider, is embedding Lua, a language I’ve never had an excuse to study, lol.

On the embedding a language thing, my thoughts are focused around in game scripting, more so then implementing the game in it. Although with the JSAPI, it wouldn’t be to tricky to do the entire game in JavaScript, as absurd as that might sound to the uninformed. For Stargella, the scripting needs can actually be integrated into the map data, in a fairly simple manor as firing positional events off to the game code. However the underlying code is meant to be (largely) shared across several games, and some (the tactical fps for example) will need much more useful scripting capabilities. Using shared objects written in C would be possible, but then maps would become non-platform independent, and I don’t want that. Quakes solution, was inventing their own C based language, and to a lesser extent the Q3VM, but ahem, I’m not quite going to do that :-P.

Some how, the idea of scripting the game system using JavaScript is still an attractive idea…. but do I really want to live with compiling Spidermonkey in order to do it?

The principal concept of any build tool, is building stuff. In my opinion, make has the perfect idea for it: just tell it what you want, then tell you want done about it.Then exploit that what you want done, can usually be guessed or written once, hehe.

At it’s heart, tmk is still a `make`, and perhaps barrows the most from classic make and from Qts project file sytax. Personally, I feel tmk makes things more simple, I’ll not repeat here what I’m loading into the Wiki on Source Forge however.

Well, at long last: my own build tool

In dealing yet again with compiling dependencies under Win32, and yet again having to deal with a yucky mixture of GNU Autotools, CMake, and IDE-x project files…. I’ve come back to thinking about an idea from several months ago, for a project called `yet another build system`; which led me to learning CMake.

The original (yabs) idea, was centred around the concept of XML descriptions of build tools, most namely the Visual C++ and GNU compilers. Which would have been mated with a simple `make` like list of rules, basically on par with the inference rules everyone knows, and loves (or hates).

For tmk however, the horizon has expanded and the XML is dropped lol. tmk is meant to be very much, a more portable make with interesting tuning options. Conceptually, it’s the same, but, eh fixed you could say. If you don’t understand that, just think back to using Makefiles and having to support 20 different build environments! Yeah, that kind of fixing.

The main point, is abstracting away the shoe honing measures. Make is perfect for the environment it was created for, building software on UNIX. However unix has diversified and fragmented sufficiently, that the average programmer is a useless stick in the mud for writing portable sh, supporting other environments like Windows, generally requires a separate set of Makefiles or carting along the (superior) unix environment with you, which is a terrible way of doing things. Fixing that problem is simple, it’s been done.

A novel feature, tmk will aim to complete builds as quickly as possible: by inferring from the rules how to build modules in parallel, which also provides me an excuse to write some code I’ve been meaning to write for EPI ;). This part is also easy.

The interesting part, will be handling dependencies properly. The real royal fuck-baked irk of most ‘later day make’ solutions, such as CMake or VCBuild, are that can’t handle dependencies worth a shit: and it makes building software off the original work station (windows) or operating system group (unix) a bitch and a half.

That’s the personal itch tmk has to fix 😉

My chuckle of the day, 2009-12-21

One notable feature of .fetchmailrc syntax is the use of optional noise keywords that are supported simply in order to make the specifications read a bit more like English. The ‘with’ keywords and single occurrence of ‘options’ in the example aren’t actually necessary, but they help make the declarations easier to read at a glance.
The traditional term for this sort of thing is syntactic sugar; the maxim that goes with this is a famous quip that “syntactic sugar causes cancer of the semicolon”.[88] Indeed, syntactic sugar needs to be used sparingly lest it obscure more than help.

— The Art of Unix Programming