Gwynne's Blog

A QTKit-based video recorder is now integrated into the code. I tried about twenty ways to get it to record audio too, but between CoreAudio’s failings and QTKit’s limitations, nothing both sounded correct and remained correctly synchronized.

1. Capture the sound output of the game and add it as a sound track to the video. Failure reason: CoreAudio provides insufficient API to do this when using OpenAL.
2. Pipe the sound output through SoundFlower and add it as a sound track to the video. Because OpenAL is broken on OS X, this necessitated changing the *system* default audio output device to use SoundFlower. Failure reason: Because video was recorded one frame at a time, with the accompanying delays necessary to compress each frame, while the audio was recorded in realtime, synchronization was impossible.
3. Pipe the output through SoundFlower and manipulate the audio data to solve the synchronization issues. Failure reason: QTKit, unlike the original QuickTime API, provides no API whatsoever for manipulating raw audio data in a movie.
4. Add the sounds used by the game as tracks to the video. Failure reason: QTKit’s API again proved unequal to the task, even in the Snow Leopard version and using SPI, an approach quickly abandoned.
5. Record each sound event, construct a sound track from those events, and add that track to the video. Failure reason: QTKit’s API once again.
6. Forgo QTKit entirely and use FFmpeg to do the media authoring. Failure reason: The documented -itsoffset flag is not implemented by the FFmpeg commandline driver, nor correctly supported by the supporting libraries.
7. Manually manipulate every input sound file to have the necessary time of silence at the beginning, then pipe through FFmpeg or QTKit. Failure reason: The entire effort was becoming ridiculous, and I felt my time would be better spent working on the actual game and worrying about something like that much later, especially since there was no need for it at all.

In every case, QTKit either had no API to accomplish the task, or its provided APIs didn’t work correctly, as with FFmpeg. I wasn’t able to drop back to the old QuickTime API because it isn’t supported in 64-bit code and I intended this game to be forward-compatible.

There was one interesting side note to all this. In the process of recording video frames, I naturally ran into the issue that OpenGL and QuickTime have flipped coordinate systems relative to each other. Rather than play around with matrices, I wrote a quick in-place pixel flipping routine:

- (void)addFrameFromOpenGLAreaOrig:(NSRect)rect
{
    NSAutoreleasePool   *pool = [[NSAutoreleasePool alloc] init];
    NSUInteger          w = rect.size.width, h = rect.size.height, rowBytes = w * sizeof(uint32_t), i = 0, j = 0, rowQs = rowBytes >> 3;
    void                *bytes = [[NSMutableData dataWithLength:h * rowBytes] mutableBytes];
    uint64_t            *p = (uint64 *)bytes, *r = NULL, *s = NULL;
    NSImage             *image = [[[NSImage alloc] init] autorelease];

    glReadPixels(rect.origin.x, rect.origin.y, w, h, GL_RGBA, GL_UNSIGNED_BYTE, bytes);
    for (i = 0; i < h >> 1; ++i)
        for (j = 0, r = p + (i * rowQs), s = p + ((h - i) * rowQs); j < rowQs; ++j, ++r, ++s)
            *r ^= *s, *s ^= *r, *r ^= *s;
            
    [image addRepresentation:[[[NSBitmapImageRep alloc]
        initWithBitmapDataPlanes:(unsigned char **)&bytes pixelsWide:w pixelsHigh:h bitsPerSample:8 samplesPerPixel:4 hasAlpha:YES
        isPlanar:NO colorSpaceName:NSDeviceRGBColorSpace bitmapFormat:0 bytesPerRow:rowBytes bitsPerPixel:32] autorelease]];
    [self addFrame:image];
    [pool drain];
}

No doubt the more skilled among you can see the ridiculous inefficiency of that approach. Through staring at the code a great deal, I was able to reduce it to:

- (void)addFrameFromOpenGLArea:(NSRect)rect
{
    // All of this code assumes at least 16-byte aligned width and height
    
    // Start r at top row. Start s at bottom row.
    // For each row, swap rowBytes bytes (in 8-byte chunks) of r and s, incrementing r and s.
    // Width = the number of 8-byte chunks in two rows (rb = w * 4, rq = rb / 8, times two rows = ((w*4)/8)*2 = (w/2)*2 = w
    NSAutoreleasePool   *pool = [[NSAutoreleasePool alloc] init];
    NSUInteger          w = rect.size.width, h = rect.size.height, i;
    uint64_t            *p = malloc(h * w << 2), *r = p, *s = p + (h * (w >> 1));
    NSImage             *image = [[[NSImage alloc] init] autorelease];

    glReadPixels(rect.origin.x, rect.origin.y, w, h, GL_RGBA, GL_UNSIGNED_BYTE, p);
    for (; s > r; s -= w)
        for (i = 0; i < w; i += 2)
            *r ^= *s, *s ^= *r, *r++ ^= *s++;
    [image addRepresentation:[[[NSBitmapImageRep alloc]
        initWithBitmapDataPlanes:(unsigned char **)&p pixelsWide:w pixelsHigh:h bitsPerSample:8 samplesPerPixel:4 hasAlpha:YES
        isPlanar:NO colorSpaceName:NSDeviceRGBColorSpace bitmapFormat:0 bytesPerRow:w << 2 bitsPerPixel:32] autorelease]];
    [self addFrame:image];
    free(p);
    [pool drain];
}

Much better, but still pretty inefficient when the size of every single frame is the same. Why keep redoing all those width/height calculations and buffer allocation and defeat loop unrolling? So I wrote a specialized version for 640×480 frames, with all the numbers precalculated.

- (void)addFrameFromOpenGL640480
{
    NSAutoreleasePool   *pool = [[NSAutoreleasePool alloc] init];
    
    if (frameBuffer == NULL)
        frameBuffer = malloc(1228800);
    glReadPixels(0, 0, 640, 480, GL_RGBA, GL_UNSIGNED_BYTE, frameBuffer);

    register uint64_t   i, *r = frameBuffer, *s = r + 153280;

    for (; s > r; s -= 640)
        for (i = 0; i < 40; ++i)
        {
            *r ^= *s, *s ^= *r, *r++ ^= *s++;   *r ^= *s, *s ^= *r, *r++ ^= *s++;
            *r ^= *s, *s ^= *r, *r++ ^= *s++;   *r ^= *s, *s ^= *r, *r++ ^= *s++;
            *r ^= *s, *s ^= *r, *r++ ^= *s++;   *r ^= *s, *s ^= *r, *r++ ^= *s++;
            *r ^= *s, *s ^= *r, *r++ ^= *s++;   *r ^= *s, *s ^= *r, *r++ ^= *s++;
        }   

    NSImage             *image = [[[NSImage alloc] init] autorelease];

    [image addRepresentation:[[[NSBitmapImageRep alloc]
        initWithBitmapDataPlanes:(unsigned char **)&frameBuffer pixelsWide:640 pixelsHigh:480 bitsPerSample:8 samplesPerPixel:4
        hasAlpha:YES isPlanar:NO colorSpaceName:NSDeviceRGBColorSpace bitmapFormat:0 bytesPerRow:2560 bitsPerPixel:32] autorelease]];
    [self addFrame:image];
    [pool drain];
}

I took a look at the code the compiler produces at -O2, and I’m fairly sure that its assembly will run parallelized, though not actually vectorized.

Yes, I’m fully aware that glReadPixels() is slower than creating a texture. I was testing my optimization skill on the low-level C stuff, not the entire routine. I only regret I didn’t have the patience to try doing it in raw SSE3 assembly, because I recognize an algorithm like this as being ideally suited to vector operations.

“Lock phasers on target.” – Khan
“Locking phasers on target.” – Joachim
“They’re locking phasers.” – Spock
“Raise shields!” – Kirk
“FIRE!” – Khan

The Reliant now has targetting and scanning systems implemented. There’s still several bugs to work out, but the basic system is in place. When that one little fighter I put in as a test shows up, the ship can lock onto it. Of course there’s no indication on the radar (since there isn’t a radar yet) and no way to destroy it (since there isn’t a laser cannon – though there are laser couplings – or torpedo holds or torpedo launchers yet), but at least we can scan it! Or we could if fighters weren’t always unscannable. Oh well.

Still, that little flashing box on top of the fighter is darn aggressive.

The reason I don’t have more to show than a buggy targeting system is I spent the majority of the time implementing it also working out a huge mess of memory management bugs I’d been ignoring since day one. Leaks, retain cycles, overreleases, you name it. What kills me is that the Leaks tool missed all but a very few of them. I ended up with manual debugging of retain counts by calls to backtrace_symbols_fd(). As uuuuuuuuuuuuuuuuuugly as lions (Whoopi Goldberg, eat your heart out). In the end a few tweaks to the way things were done were in order. Too much work being done in -dealloc when I had a perfectly good -teardown method handy that functions much like the -invalidate suggested by the GC manual.

Why aren’t I using GC and saving myself this kinda trouble? Frankly, given my current understanding of things, I think GC would be even more trouble than this! This, at least, I understand quite thoroughly, and I have considerable experience dealing with the issues that arise. I know how to manage weak references properly to avoid retain cycles and how to do a proper finalize-vs-release model. I haven’t even gotten tripped up by hidden retains in blocks more than once! Yes, I screwed it up badly here, but that’s because I was paying very little attention. I do know how to do it right if I try, and now I’m trying.

Garbage collection, on the other hand, is a largely unknown beast to me, and from what I’ve read on Apple’s mailing lists, the docs Apple provides are very little help to developers new to the tech. The hidden gotchas are nasty devils, much worse than hidden retains in blocks. Interior pointers and missed root objects come to mind, especially since I’m targeting 10.5 where GC support was still new and several bugs in it were known to exist (and may still). Apple chose to provide an automatic stack-and-heap scanning collector, whereas I would only have been comfortable with a manual heap-scanning collector, which is really little more than autorelease anyway. In such a light, the model I’m familiar with and clearly understand seemed a much better choice than trying to learn an entirely new paradigm for this project. Ironically, I still chafe at manual memory management in C++ projects, especially the lack of autorelease, and as with GC, I don’t understand such things as auto_ptr and shared_ptr well enough to get any use of them. Templates make me cringe.

With the targeting scanner implemented, all I need to do is debug it. The next step will be to write the radar, so as to double-check that the fighter AI is working as it should and that the target scanner is de-targeting properly when something falls out of range. After that I need to test the scanner versus multiple targets, especially the new smart-targeting mode I’ve added as an easter egg. What can I say, it always drove me nuts that it targeted “the next enemy in the internal array of enemies” rather than “the nearest enemy to my ship”. But finding how to enable it is left as an exercise to you nostalgic people like me who’ll actually play this port :-).

Come on, iTunes. Jesse Hold On – B*Witched? *punches the shuffle button* 太陽と月 – 合田彩. Much better! Sorry, interlude *sweat*.

Anyway, once the scanner can handle multiple targets, it’s time to implement the third and final component of the laser: the cannon. Time to blow things up with multicolored hypotenuses of triangles! I might even study up on a little QTKit so I can take movies from the OpenGL context to show off. Bandwidth, though; this blog isn’t exactly hosted off DreamHost. (Linode actually, and they’re really awesome). Oh well, we’ll see. Maybe I’ll even leave the feature in as another easter egg…

To summarize, the current plan is:

1. Fix bugs in target scanner.
2. Implement radar.
3. Spawn multiple targets for the target scanner.
4. Implement laser cannon.
5. Maybe implement movie capture of gameplay.
6. ???
7. Profit!

I’m not making it up as I go, I swear!

As if all the mucking about with coordinates before wasn’t bad enough, next I had to deal with unit vectors, polar/Cartesian coordinate conversion, sign adjustment vs. trigonometric functions… you get the idea.

In this case, my problem wasn’t caused by needing to update the algorithms Mike used at all, but rather by my need to replace the old MacToolbox FixRatio() and AngleFromSlope() functions with modern trigonometrics. Now, I’d already done all this, or else the impulse and warp drives would never have worked for this long, but in poking about in the implementation for mobile enemies, I realized I’d have to generalize the code, or else end up repeating it in about a dozen places, a well-known recipe for disaster.

In literal code, warp speed goes like this:

double diffx = warpCoordX - playerCoordX, diffy = warpCoordY - playerCoordY,
       theta_raw = atan2(-diffy, diffx), theta = round(fma(theta_raw, RAD_TO_DEG_FACTOR, 360 * signbit(theta_raw))),
       // make use of theta in degrees here to calculate a turn factor
       maxSpeed = warpSpeed,
       newDeltaX = cos(theta * DEG_TO_RAD_FACTOR), newDeltaY = -sin(theta * DEG_TO_RAD_FACTOR),
       finalDeltaX = playerDeltaX + newDeltaX, finalDeltaY = playerDeltaY + newDeltaY;
if (fabs(addedDeltaX) >= fabs(maxSpeed) * newDeltaX) finalDeltaX = maxSpeed + newDeltaX;
if (fabs(addedDeltaY) >= fabs(maxSpeed) * newDeltaY) finalDeltaY = maxSpeed + newDeltaY;

Conceptually, this reads:

1. Calculate the difference between the player’s current position and the destination in Cartesian coordinates.
2. Take the arctangent of the Cartesian coordinates, adjusted for inverted Y, converted to degrees and adjusted to the range [0,360] (atan2() returns [-π,π]).
3. Convert the polar coordinates (using the implied mangitude of 1) back to Cartesian coordinates.
4. Calculate the movement delta with a speed limit.

Why, one wonders, do I do a Cartesian->polar conversion, only to immediately convert back to Cartesian again? Answers: 1) I need the angle to calculate which way to turn the ship towards its destination. 2) The distance between current position and destination is a vector of (usually) rather high magnitude; I need to normalize that vector to get a delta. And the formula for normalizing a Cartesian vector is x/sqrt(x*x+y*y), y/sqrt(x*x+y*y). Two multiplies, an add, a square root, and two divides, all floating point. Without benchmarking I still intuitively think that’s slower (and I’m SURE it’s conceptually more confusing) than cos(atan2(-y, x)), -sin(atan2(-y, x)), two negations, an arctangent, a sine, and a cosine. Maybe I’m crazy.

Of course, typing all this out made me realize that I can, in fact, eliminate the degree/radian conversion entirely, as well as the range adjustment, by changing the conditional in the turn calculation. Once again I fell for the trap of not thinking my way through the code I was porting. At least you weren’t as bad at geometry as me, Mike :-).

Then I had to go and get really curious and benchmark it:

#include <stdio.h>
#include <math.h>
#include <sys/time.h>

int     main(int argc, char **argv)
{
        struct timeval cS, cE, pS, pE;
        // Volatile prevents compiler from reading the loops as invariant and only running them once.
        volatile double x1 = 1.0, x2 = 2.5, y1 = 0.4, y2 = 3.2, dx = 0.0, dy = 0.0, inter = 0.0;

        gettimeofday(&cS, NULL);
        for (int i = 0; i < 100000000; ++i)
        {
                dx = x2 - x1;
                dy = y2 - y1;
                inter = sqrt(dx*dx+dy*dy);
                dx /= inter;
                dy /= inter;
        }
        gettimeofday(&cE, NULL);

        gettimeofday(&pS, NULL);
        for (int i = 0; i < 100000000; ++i)
        {
                inter = atan2(y2 - y1, x2 - x1);
                dx = cos(inter);
                dy = sin(inter);
        }
        gettimeofday(&pE, NULL);

        struct timeval cD, pD;

        timersub(&cE, &cS, &cD);
        timersub(&pE, &pS, &pD);

        printf("Cartesian diff = %lu.%06u\n", cD.tv_sec, cD.tv_usec);
        printf("    Polar diff = %lu.%06u\n", pD.tv_sec, pD.tv_usec);

        return 0;
}

Foot in mouth. cos|sin(atan2()) is consistently 3x slower than x|y/sqrt(x^2+y^2) at all optimization levels. Somehow I just can’t see this as being an artifact of the brutal abuse of volatile for the benchmark.

Mike got around the whole issue, in the end. Knowing that he only ever had to calculate cos()/sin() for the angles in the period [0,35]*10, he just precalculated them in a lookup table. And cutting the cosine and sine calls out of the benchmark reduces the difference between the methods to about 1.6x, making his way a win over a four-way compare/branch for the turn calculation.

Live and learn.

Oh, and changes to Missions: Again, nothing you can see in play yet. But at least now I have the right building blocks to make the enemies from.

At last, an update!

1. Absolutely nothing visible to the user has changed whatsoever.
2. The internal structure of the code has been significantly reorganized.

As with the lament of all programmers faced with the demands of the technologically disinclined, I’ve accomplished a great deal, but since it can’t be seen, it might as well be nothing at all. Wasted time, the hypothetical slave driver- I mean, boss- would say. But it isn’t, I swear to all two of you who read this blog!

And now, another math rant.

Once again, as with so many things, the way Mike did things in the original code was correct and logical for the time he did it, but doesn’t fit into the object-oriented model I’m cramming his code into, despite its pitiful cries for mercy from such rigid structure. There are days I wish we were living in times when code could be so freeform as his was and still be comprehensible, but you can’t do that in Cocoa. Oh sure, I could port all the Pascal functions 1-to-1, but the Toolbox calls would be sticky at best. Anyway, in this particular case, I was trying to wrestle with the radar range calculation.

The original code reads something vaguely like: screenPos = Planetabs - (Playerabs - Playerscreen)  inRadarRange = n <= screenPos / 16 <= m. Translating, this means that whether or not a given entity (a planet in this case) is within radar range of the planet is dependant upon the Player’s position in screen coordinates, as well as in the game’s absolute coordinate system.

In the old days, this design made a certain amount of sense. He already had the screen coordinates immediately handy, so why take the hit of indirecting through A5 to touch a global for the absolute position? However, my design makes the screen coordinates a bit dodgy to use. So I had to recalibrate n and m to represent distances in game coordinates.

Algebra to the rescue. The code above, reduced and replacing the inequalities, becomes the algebraic equation (x - (y - z)) / 16 = a, where a is the radar range coordinate. The only screen coordinate term in this equation is z, so solve to eliminate z:

(x - (y - z)) / 16 = a
x - (y - z) = 16a       - multiply both sides by 16
x - y + z = 16a         - distribute the subtraction over the parenthetical expression
x - y = 16a - z         - subtract z from both sides

But, because both a (the radar range) and z (the player’s position on screen) are actually constants, all I had to do was take Mike’s original numbers (let’s use 64 for a and 268 for z) and calculate 16*64 - 268 = 756. Then, retranslating, the equation becomes the inequality inRadarRange = (myPosition - playerPosition) <= 756;. Repeat for the lower and upper bounds of x and y coordinates, and boom, no screen coordinates at all and I can calculate whether or not an object's in radar range based on nothing but its offset from the player.

To be clear, what I did up there was to eliminate a term from the inequalities so that they could be evaluated based on the position of the given entity in game space, rather than on the position of the entity's sprite on the screen.

I can't believe it took me a week to doodle out that bit of math.

Let me describe the setup for this issue.

Take a gobal (set property on a singleton object) list of objects which holds only weak references (in this case, if it held strong references, the objects would never lose their last retain and could never be deallocated, yes I know GC avoids it):

@implementation Singleton
- (void)init
{
    if ((self = [super init]))
    {
        CFSetCallBacks cb = { 0, NULL, NULL, CFCopyDescription, CFEqual, CFHash };
        NSMutableSet *container = (NSMutableSet *)CFSetCreateMutable(kCFAllocatorDefault, 0, &cb);
    }
    return self;
}

- (NSMutableSet *)container { return container; }
- (void)setContainer:(NSSet *)value { if (value != container) { [container setSet:value]; } }
// The other KVC-complaint methods for an unordered to-many relationship

// Singleton pattern stuff here
@end

Now consider a class which, as part of its initialization and deallocation, adds itself to and removes itself from this singleton’s container:

@implementation ListedObject
- (id)init
{
    if ((self = [super init]))
    {
        [[Singleton singleton] addContainerObject:self];
    }
    return this;
}

- (void)dealloc
{
    [[Singleton singleton] removeContainerObject:self];
    [super dealloc];
}
@end

This pattern is useful when you need to track every instance of a given class – in this case, my actual code maintains the set property as a property on the class object itself rather than a separate singleton, but the result is the same and I thought I’d use something more familiar for this example.

The first time you release an instance of ListedObject to the point of deallocation, you’ll crash during your next event loop.

Next event loop? Experienced Cocoa readers will immediately guess “autorelease pool”. And they’d be right. To debug this, I added backtrace_symbols_fd() calls to -retain and -release of the ListedObject class. This may seem strange versus using a GUI tool like Instruments’ “Object Allocation” template, but I’m old-fashioned and this was simple. The object was indeed being overreleased, with the extra release coming from the main event loop’s autorelease pool.

The cause is rather intricate. At the time of the deallocation, I had a registered key-value observation on the container property. So, when the object removed itself from the list, KVO called [NSSet setWithObject:removedObject] in order to pass it as part of the change dictionary to the observer callback. This naturally went on the autorelease pool. But oops, we were already in -dealloc of the removed object, so the retain the autoreleased set tried to add was a no-op. Finally, next time through the event loop, that set was freed by the autorelease pool, and tried to call -release on the removed object, but that object had already been fully deallocated. Crash!

Now, a purist will say “stop trying to do things in -dealloc!” Others would point out that GC would bypass this entire problem. Either way, I wanted a simple solution. The problem was an autorelease pool, so just add another one!

- (void)dealloc
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    [[Singleton singleton] removeContainerObject:self];
    [pool release];
    [super dealloc];
}

KVO’s set is no longer deferred-release, and all is well.

As it happens, this uncovered an underlying issue in my code, a design flaw which essentially makes the entire debacle unnecessary because the list management needed to be in other methods rather than -init and -dealloc, but I thought it was an interesting note nonetheless.

I’m back, and I didn’t give up on Missions! I’m sure there must be exactly one person out there who cares :-).

But seriously. I don’t have any new features to show at the moment, unfortunately. When I went to implement the laser cannon for the player, I realized I’d never be able to test it without something to fire at. I also realized the cannon itself would be useless without the target scanner since it has to lock onto a target. The scanner is also useless without something to scan. So, it was time to implement the base code for mobile enemies. Probably should’ve done that long ago, and here’s why…

As we all know, I’m using Objective-C to write this code. That means, among other things, that my code is object-oriented in nature. Up until this point, things like planets, starbases, and the player had all been entirely separate implementations. This is what Mike did with the original code. As always, what he did then was only sensible for the time and environment, but I can avoid a hell of a lot of code duplication by giving everything that exists in space a common superclass: a “Presence”. (Presences are themselves subclasses of the even more general “Responder”, which is used for everything that needs to process game happenings in any way, but that’s only a side note). As one can imagine, since I didn’t have the foresight to design the code this way to begin with, implementing it now required some significant refactoring.

Another issue cropped up halfway through the refactoring: The severe limitations of Apple’s built-in Key-Value Observing, which I use extensively throughout the code to avoid having to call “update this” and “update that” manually for every single affected object whenever something changes. For example, KVO doesn’t let you use blocks for callbacks, and if a superclass and a subclass both register for the same notification, there’s no way to manage the two independantly. Fortunately, Michael Ash noticed these problems some time back, and created a replacement, his MAKVONotificationCenter. Unfortunately, even the updated version published by Jerry Krinock didn’t do everything I needed, at least not in a way that I found usable with blocks added to the equation. Managing observations by tracking the resulting observation objects means having lots of instance variables to hold the observations, and since I’m building for Leopard, I can’t use the new associated objects for the purpose.

“Wait a minute,” you’re saying! “Leopard? Then why are you talking about using blocks?” Answer: I’m using PLBlocks.

So, armed with PLBlocks on one side, and Michael Ash’s typically brilliant code on the other, I dove in and pretty much rewrote the entire MAKVONotificationCenter to do three things it didn’t before:

1. Block callbacks.
2. Tagging observations with a simple integer value.
3. Several alternative ways of specifying groups of observations to remove, based on observer, target, key path, selector, tag, or most combinations thereof.

With that done (and unit tested, and Doxygen-documented), I’m now integrating them into my revised class heirarchy for Missions itself. With any luck, I’ll have at least a screenshot of a fighter flying around before the week is out. Stay tuned, those of you who are crazy enough to stick around for all this :-).

Footnote: I was finally able to find a way to access the original model files for the game’s graphics; with some luck and a bit of help from Mike (I’m clueless when it comes to this stuff), there may be higher-quality graphics to be seen in the screenshots soon.

In the course of experimentation, I just discovered a neat trick. You can use key-value observing on a class object! Consider this simple example:

#import <Cocoa/Cocoa.h>

static int      Test_x = 0;

@interface Test : NSObject
{
}
+ (int)x;
+ (void)setX:(int)x_;
@end

@implementation Test
+ (int)x
{
        return Test_x;
}

+ (void)setX:(int)x_
{
        [self willChangeValueForKey:@"x"];
        Test_x = x_;
        [self didChangeValueForKey:@"x"];
}
@end
 
@interface Observer : NSObject
{
}
- (void)observeValueForKeyPath:(NSString *)keyPath ofObject:(id)object change:(NSDictionary *)change context:(void *)context;
@end

@implementation Observer
- (void)observeValueForKeyPath:(NSString *)keyPath ofObject:(id)object change:(NSDictionary *)change context:(void *)context;
{
        printf("observed for %s, value = %d\n", [keyPath UTF8String], [Test x]);
}
@end

int     main(int argc, char **argv)
{
        NSAutoreleasePool               *pool = [[NSAutoreleasePool alloc] init];
        Observer                        *o = [[[Observer alloc] init] autorelease];

        [[Test class] addObserver:o forKeyPath:@"x" options:NSKeyValueObservingOptionInitial context:NULL];
        [Test setX:99];
        [[Test class] removeObserver:o forKeyPath:@"x"];

        [pool drain];
        return 0;
}

And it works!

$ gcc kvotest.m -o ./kvotest
$ ./kvotest
observed for x, value = 0
observed for x, value = 99
$ 

It has some caveats, of course:

• Automatic notification doesn’t work, probably for some reason having to do with the way the runtime implements class objects and the method swizzling KVO does to make automatic notifications work. Your setters have to explicitly call -willChangeValueForKey: and -didChangeValueForKey:
• This is a hack. It’s not documented to work at all and thus Apple is under no obligation to see that it keeps working.
• You’re not supposed to do things like this with classes. You’re supposed to define a singleton object, e.g. [NSNotificationCenter defaultCenter] and use that.
• I’ve only tried this on Snow Leopard (though it was compiled against the Leopard SDK). I don’t have anything else handy to test with.
• I haven’t tried this with any of the more advanced KVO features (to-many relationships, dependent keys, NSKeyValueObservingOptionPrior).
• Obviously, as shown this isn’t thread-safe, though that’s more for the use of the static variable to hold the value.

The only use for it I can think of offhand is when you have a class which keeps a list of its objects and provides a method for accessing that list as an array, and you want some other object to be notified when that list changes (for example, one could in theory want to observe changes in NSValueTransformer’s +valueTransformerNames). The documentation explicitly states, “Instead of observing an array, observe the ordered to-many relationship for which the array is the collection of related objects.”, so to see changes in the list by KVO, one has to observe the property of the class itself. Classes can’t have properites (or static instance variables, come on Apple), so something like this is one way of doing the trick.

Use at your own risk!

I ran across this bit in Mike’s code, and couldn’t help but smile:

IF totalEnergy < 0 THEN
    totalEnergy := 0;   {this line saved my sanity! Believe me, shieldLevel _can_ be negative}

I’ve met few programmers who don’t put funny comments in their code now and again. For example, here’s one of mine from the warp drive subsystem:

if (enteringWarp && velocity > minWarpVelocity)     // We hit 88 miles per hour! Activate the flux capacitor!

I pity anyone whose code review guidelines forbid them from doing things like this. When trying to figure out someone else’s code, a little humor is desperately needed.

Skip the roleplay blurb

I’ve accomplished surprisingly little in the last couple of days, in functional terms. I can sum up why pretty easily: I’ve had to stop and puzzle out exactly how Michael did some of the things in his code. Player velocity, especially, is giving me grief.

This isn’t Michael’s fault. He didn’t write obscure code (well, a little…) or implement anything stupidly. The problem was his confinement to old Mac Toolbox APIs in Pascal. One does not simply toss around floating-point math in System 7. (Nor does one simply walk into Mordor, but that’s another story.) Pascal had a floating-point type (REAL), but in those days it was slower than my brain on a Monday morning. I’m not sure why, since almost every Mac since the Mac II had a MC68881 or better FPU, but we were always told to use the FixMath package for efficiency just the same. So we used fixed point types and did fun little things like this:

integerPart := trunc(Fix2X(fixedValue));
fractionPart := fixedValue - Long2Fix(integerPart);

With math like that, and manual compensation for overflow going on, I think I can be forgiven for having to stare blindly at the uncommented code for about two hours before it finally made sense to me. It’s been quite a few years since I’ve worked without native floating-point, and a lot of that time was spent dredging up the memories. 21 lines of Michael’s Pascal code, all of them necessary in the environment it was written for, boil down to a single line in modern C, and in fact a single assembly language instruction too if you care to look at things at that level. In these days of multimedia CPU extensions, if I thought it were necessary for performance I could write it such that all the calculations for all the game objects that needed to move around were done in one vector instruction (SIMD add). I don’t think it’s necessary, but the fact that I could is a sign of just how much CPUs have changed. It’s also a tribute to all those people who did it the hard way 15 years ago.

Other progress includes implementation of the sector object map (meaning planets and starbases, and their locations), reconversion of the rather broken SapirSans font (just opening it in Font Book made ATSUI whine quite loudly, and the italic variant was progmatically indistinguishable from the plain one) into a correctly-formed font suitcase by the very helpful if cryptic FontForge font editor program, and cargo, personnel, and crew management code. As usual, all of this stuff is backend and not visible in a build yet, so I have no screenshots to show. I will soon, though; now that I’ve figured out how the player moves around I can at least make the viewscreen work. Stay tuned.

P.S.: If there’s anyone who follows and enjoys the little roleplay blurbs, speak up in a comment and I’ll continue them. It only takes one voice!

Alliance Headquarters
Stardate 2310.13816640048673

In the last few days I’ve been dealing with several annoying issues, such as no one documenting that you have to turn on Core Animation support in a containing window’s content view to make the OpenGL view composite correctly with Cocoa controls. Four hours wasted on one checkbox. Sigh.

Still, there’s some progress to be had.

1. The loading bar now displays and loads all the various data needed.
2. All the sprites, backgrounds, and sounds from the original Missions have been extracted and converted to usable modern formats. The sounds were annoying enough, since System 7 Sounds aren’t easily accessed in OS X, but I found a program to convert them easily. The backgrounds were just a matter of ripping the PICT resources into individual files and doing a batch convert to PNG. The sprites… those were a problem. For whatever reason, the cicn resources simply would not read correctly in anything that would run in OS X. Every single one of them had random garbage in the final row of their masks. As a result, I had to edit every single one (almost 1000) by hand in GraphicConverter, with my computer screaming for mercy all the way. Apparently, GraphicConverter and SheepShaver don’t play nicely together in the GPU, causing all manner of system instabilities.
3. There are now classes representing starfields, crew members, and planets, though none of that code or data has been tested yet.
4. I’m now building with PLBlocks GCC instead of Clang. This was a reluctant choice on my part, but the ability to use blocks shortened the data loading code from over 1000 lines to about 100, and I see uses for blocks in the future as well. Pity the Clang that comes with 10.6 refuses to work correctly with files using blocks and the 10.5 SDK.
5. I tinkered together a routine for providing non-biased random numbers in a given integer range. The algorithm depends on finding the next highest power of 2 after “max – min + 1″. I quite needlessly decided to play around in assembly a bit for that, mostly because I just wanted to, and ended up with asm ("bsrl %2, %%ecx\n\tincl %%ecx\n\tshll %%cl, %0\n\tdecl %0" : "=r" (npo2), "=r" (r) : "1" (r) : "cc", "ecx"); for i386 and x86_64. I fall back on a pure-C approach for PPC compilation. I haven’t benchmarked this in any way, and I know for a fact that doing so would be meaningless (as the arc4random() call is inevitably far slower than either approach). It was mostly an exercise in knowing assembly language.
6. The “new game” screen, where the scenario and difficulty are selected, now exists. That was also interesting, as it involved shoving a Cocoa view on top of an OpenGL view. I can use that experience for all the other dialogs in the game.

As always, more updates will be posted as they become available.

Alliance Headquarters
Stardate 2310.12630998555023

Progress today was unfortunately small, interrupted by a sudden power outage and further stalled by an Internet service that refused to be restored, but here’s the usual list of what was accomplished.

1. Cleaned up the code a bit more
2. Made the main menu buttons draw and interact. Mostly, anyway; they highlight for mouse clicks and key presses, but they don’t do anything else yet.

Yep, that’s all *shame*. I suspect I’ll have better luck tomorrow.

Alliance Headquarters
Stardate 2310.11526541942353

P.S.: Neither the gibberish in the report nor the numbers in the signature are random. A copy of the latest build will be sent to the first person to correctly guess what either of them actually mean in a comment on this blog.

“For all we know, at this very moment, somewhere far beyond all those distant stars, Benny Russell is dreaming of us.” – Avery Brooks as Benjamin Sisko, Star Trek: Deep Space 9, “Far Beyond the Stars”.

Working on Missions at the level I am so far, I feel about that far away from the game’s universe. Still, there’s been a bit of progress today.

1. First off, I went to grab the main screen out of the original Missions. This time I didn’t have to play around with PICT resources (I did anyway, but that’s besides the point). There was a nice non-composited Photoshop document sitting around with all its individual layers to play with. I tore into it with a vengeance – poor file. In the end, I didn’t do much, just added my copyright to Michael’s and erased the UI buttons.
   
   Erased the UI buttons?
   
   Well, yes. Having looked through the old code, Michael had used QuickDraw as it was meant to be used and been drawing the user interaction with the buttons by writing over the bitmap data with DrawString(). An time-honored and venerable way of doing things in the Mac Toolbox, but not at all suited to efficiency in an OpenGL application. Wiping out the buttons was the first step in separating them out entirely for compositing as OpenGL textures. Probably overkill anyway in the end, but keep in mind this is a learning experience for me and I figured I’d use the general code instead of special-casing this screen more than necessary.
2. Once I had the main screen image re-composited into a nice PNG (bye-bye PICT!), I plugged that into glTexImage2D() and voila, the main screen now displayed in the window! Of course, that screen was bereft of all the nice details that make Missions what it is, so I set about adding the little touches back in. The most obvious of these was the version number in the lower-right corner of the screen. It took me a while to figure out how to get the arcane combination of string drawing in NSImage and writing into an OpenGL texture object correct, but I got there in the end thanks to a little timely help. Incompatible coordinate systems and swapped RGBA/BGRA component ordering were the order of that couple of hours. Whew. A few calls to -[NSBundle objectForInfoDictionaryKey:] and several searches online for versions of the embedded fonts that worked properly later, I had the version number composited neatly on top of the background. Progress!
3. Of course, the code was a disaster at this point. I’d gone through so many dozen iterations of fixing my snafus… well, long story short, I took some time out to reorganize, and got my texture loading and sprite management all neatly separated into their respective classes, including having the sprite class (replacing Michael’s use of SAT in the original code) do the necessary coordinate transformation so I could use the numbers from the original code cleanly. Not to mention some carefully managed global constants to hold useful values, such as references to the fonts and custom colors being used.

And here’s the reward of all that hard work:

First draft of the Missions of the Reliant main screen

I know it doesn’t look like much, but as with all programming, it’s the infrastructure behind it that counts. It’s something most users never see and don’t realize the sheer difficulty of maintaining, but it’s there and it’s important. With all that structure in place, once I’ve gotten some sleep I can make much faster progress tomorrow.

Stay tuned for further updates.

Alliance Headquarters
Stardate 2310.11299452429843

Well, having the project file for Missions in place, I went to organize some of the resources – sprites, backgrounds, strings, all that fun jazz, and there’s plenty of it. In particular, I found myself re-engineering a couple of icons to support the much larger icon sizes we’ve gotten in Mac OS since the ancient days – 8-bit 32×32 icons are well and good, but how’s a 32-bit 512×512 snapshot with alpha channel sound? Pretty good? I thought so. A couple hours tweaking around in GraphicConverter and Photoshop Elements later, I had a nice large icon for the application and saved games. Of course I kept the original icon for 32×32 and 16×16 sizes.

One might ask, what the heck was I doing playing around with graphics when there’s so much code to write? There are two answers. One, that’s just the way I work: Once I get it into my head to finish a task, I get a bit exclusive about it. Two, it was fun, and a part of adding the tiny little bits of personal touch to the port. I wouldn’t want to detract from Michael’s work, of course, but at the same time I am putting in quite a bit of effort to bring that work to the modern audience, so I see no reason that effort can’t be remotely noticable.

Of course, most of the original graphics were vector models done in an old program called Infini-D. Unfortunately, I can’t find this program or anything which can read its format…

Having finished poking around in Photoshop Elements, I went to look up the fundamentals of OpenGL 2D on Mac OS X. Four hours of playing around with CGImage, NSOpenGLView, and glTexImage2D later, I figured out why the alpha channel in the PNG I was using to test was being completely ignored: I never called glEnable(GL_BLEND);. Egg on face much? Oh well. At least I finally made it work. I now have a basic setup in place with which to draw sprites and backgrounds in the game window. Not bad for a few hours and not having done OpenGL in five years, if you ask me.

At least I was vindicated in thinking NSOpenGLView had to be at least a little bit useful despite loud claims by OpenGL coders that I might as well resign myself to subclassing NSView and doing the setup by hand!

That’s about it for today. I’d like, however, to share this amusingly useful little macro with my fellow Objective-C users who aren’t in GC-land yet. I wanted a nice compact way to add a Core Foundation object to an NSAutoreleasePool without doing lots of ugly typecasts. The result was this:

#define CFAutorelease(cftyp)        ((typeof((cftyp)))[((id)(cftyp)) autorelease])

Nothing like cheating a bit with typeof(); despite appearances, the expression is not evaluated twice! That let me write bits like CGColorSpaceRef colorSpace = CFAutorelease(CGColorSpaceCreateDeviceRGB()); instead of CGColorSpaceRef colorSpace = (CGColorSpaceRef)[(id)CGColorSpaceCreateDeviceRGB() autorelease];. Much more readable, IMHO. The fact that sending autorelease to nil/NULL does nothing and returns NULL is just a lovely little bonus. This doesn’t work quite right in GC code, of course, so don’t try it there.

The other thing that made me happy was thumbing my nose at all the “ARB_texture_rectangle is so useless” noise. Sure, if you’re doing fancy 3D drawing, a texture with non-parameterized coordinates and no non-clamp wrapping and no mipmaps or borders is a problem. Not so much in simple 2D. Why complicate backwards compatibility by using ARB_texture_non_power_of_two?

Those who have been using Macs for at least 14 years may or may not remember a space game for old Macs that went by the name “Missions of the Reliant”.

It was a really fun little game with a few missions in it, changable crew members in your ship, powerups for your ship, a nice big galaxy to hang around in, systems that took damage and could be repaired… if you’re thinking Rescue!, don’t, Missions was much better.

Anyway, like all the old Mac games, it’s long since nonfunctional on modern machines. But I wasn’t willing to settle for that, so I pulled up my e-mail and wrote a letter to Michael Rubin, the original author of Missions, asking if I might get the source code and take a crack at porting it to OS X.

His enthusiasm was beyond anything I could have hoped for. I’m very grateful to him for the opportunity he’s given me to bring a classic back to the Mac. I’ll be posting updates here regularly about my progress on the port.

Progress Report 1

Well, I’ve got the code, and I’ve looked it over. Ah, the old glory days of Pascal, inline A-traps, GWorlds, manual event handling… The Mac Toolbox did almost nothing for you; it was a true low-level interface to the OS, something I feel we’ve gotten away from in these days of Cocoa. Sure, OS X has the POSIX interfaces, but they’re a whole different world. Anyway, the code is a real trip back to olden times, and I love every minute of it.

First step was to create the Xcode project. That took about three hours.

Wait, what? Three hours? Well, once you figure setting up the project settings, the target settings, tweaking the things Xcode’s templates don’t get quite right, editing the pregenerated files to not have broken line breaks and incorrect heading comments, and writing the entire Info.plist for the application, that’s a lot of work! I had to look up Info.plist keys, UTI listings, sweep the original source code for the proper value of NSHumanReadableCopyright, and ask a question or two about semantics in the #macdev IRC channel.

Next step, I figure, is to sweep up all the original visual resources – strings, pictures, icons – and reorganize them out of old-style rsrc files into a modern application’s Resources folder. Yes, I’m aware you can still use resource files in OS X, but I feel if you’re going to do something, you might as well do it right!

After that, I have to take a little time out to brush up on my OpenGL 2D, it’s been awhile since I used it and I never did use it for anything this complex. Binding several dozens of textures to represent all the various sprites should be a fascinating undertaking.

I’m enjoying the hell out of myself *grin*. Thanks again, Michael!

String parsing in C is painful and annoying.

I want to parse the components of an absolute POSIX path. Here’s the code to do it in several languages.

So I was looking at the macro used to calculate 16-bit parity in pure C without branching:

#define parity(v)   ({ \
        uint16_t pv = (v); \
        pv ^= (uint16_t)(pv < < 8); \
        pv ^= (uint16_t)(pv << 4); \
        pv ^= (uint16_t)(pv << 2); \
        pv ^= (uint16_t)(pv << 1); \
        (uint16_t)(pv & 0x0001); \
    })

It uses GCC’s handy compound statement syntax, but otherwise it’s plain old C. Let’s look at the 64-bit ASM this compiles to at -Os: (more…)

Given this code:

- (void)calculateData:(int32_t)n intoLeftBuffer:(int16_t *)lbuf rightBuffer:(int16_t *)rbuf
{
    static uint64_t            (*calculateInternalCall)(id, SEL) = NULL;

    if (!calculateInternalCall)
        calculateInternalCall = (uint64_t (*)(id, SEL))[self methodForSelector:@selector(calculateInternal)];
    
    uint64_t    leftEnableMask = self.isEnabled && lbuf ?
                          ((-(is0Enabled & leftEnabled[0])) & 0xFFFF000000000000) |
                          ((-(is1Enabled & leftEnabled[1])) & 0x0000FFFF00000000) |
                          ((-(is2Enabled & leftEnabled[2])) & 0x00000000FFFF0000) |
                          ((-(is3Enabled & leftEnabled[3])) & 0x000000000000FFFF)
                      : 0,
                rightEnableMask = self.isEnabled && rbuf ?
                          ((-(is0Enabled & rightEnabled[0])) & 0xFFFF000000000000) |
                          ((-(is1Enabled & rightEnabled[1])) & 0x0000FFFF00000000) |
                          ((-(is2Enabled & rightEnabled[2])) & 0x00000000FFFF0000) |
                          ((-(is3Enabled & rightEnabled[3])) & 0x000000000000FFFF)
                : 0;

    for (int32_t i = 0; i < n; ++i)
    {
        uint64_t     data = calculateInternalCall(self, @selector(calculateInternal)),
                     lv = data & leftEnableMask, rv = data & rightEnableMask;
        int16_t      *l = (int16_t *)&lv, *r = (int16_t *)&rv;
        lbuf[i] += l[0] + l[1] + l[2] + l[3];
        rbuf[i] += r[0] + r[1] + r[2] + r[3];
    }
}

Where are the two NULL dereferences Clang claims to have found?

We all make mistakes when coding, and some of them are quite deeply foolish. But this particular snafu I just made takes the cake, in my opinion (dumbed-down code):

// Written as a static inline C function for max
// speed; this is called in a very tight loop, usually
// at something like 40,000 times per second.
static inline uint8_t _readByte(NSUIntger *cursor,
                                const char *bytes,
                                NSUInteger maxlen)
{ return (*cursor < maxlen) ? bytes[*cursor++] : 0x66; }
// Macro for readability, known to be called only from the one function
#define readByte() _readByte(&cursor, buffer, bufferlen)
// Macro to skip so many bytes
#define skipBytes(n) do { \
    __typeof__(n) nn = (n); \
    for (uint8_t i = 0; i < nn; ++i) \
        readByte(); \
    } while (0)
- (void)processBuffer
{
    // assume the declarations of n, cursor, buffer, bufferlen
    // ...
    n = readByte();
    // ...
    else if (n > 0x29)
        skipBytes((uint8_t[16]){0,0,0,1,1,2,0,0,0,0,2,2,3,3,4,4})(n & 0xF0) >> 4);
}

See it? (Hint: Look at the implementation of skipBytes().)