As with asteroids, I plan to start out as closely as I can to the old 1978 Space Invaders program. That means I want to create 8-bit bitmaps of the invaders, much like the original. Today I’ll start that process.

I found the old source code on the excellent Computer Archeology site. This includes a patch of code that defines the invaders in bits:

; Alien sprite type A,B, and C at positions 0
;  ........ ........ ........
;  ........ ........ ........
;  *..***.. ........ ........
;  *..****. ...****. ........
;  .*.****. *.***... *..**...
;  .***.**. .*****.* .*.***..
;  ..**.*** ..**.**. *.**.**.
;  .*.***** ..****.. .*.*****
;  .*.***** ..****.. .*.*****
;  ..**.*** ..****.. *.**.**.
;  .***.**. ..**.**. .*.***..
;  .*.****. .*****.* *..**...
;  *..****. *.***... ........
;  *..***.. ...****. ........
;  ........ ........ ........
;  ........ ........ ........
1C00: 00 00 39 79 7A 6E EC FA FA EC 6E 7A 79 39 00 00
1C10: 00 00 00 78 1D BE 6C 3C 3C 3C 6C BE 1D 78 00 00
1C20: 00 00 00 00 19 3A 6D FA FA 6D 3A 19 00 00 00 00

I can’t read that comment as invaders, but I can sort of see that it probably is. So my plan is to import those bitmaps and use them, somehow, to draw the invaders, probably as sprites, because I’m quite certain that Codea’s bit processing isn’t capable of doing the job a bit at a time, which is all we have.

So today’s mission will be to create a function to fetch bit N from an array of hex numbers, so that we can use it to draw pixel N on the screen. It would be nice if I could just declare the array to be an image, but that seems not to be possible.

I’m going to do this job using TDD, test-driven development, because it’s a perfect mission for TDD: complicated code that it’s easy to get wrong.

I’ve decided to call the function fetchBit, and to try to use TDD very closely to the ideal fashion for Codea. I’ll explain that as I go.

Here’s the starting empty test file that comes with my CodeaUnit template, except with the test name changed:

function testSpaceInvaders()
    CodeaUnit.detailed = true

    _:describe("SpaceInvaders fetchBit", function()

        _:before(function()
            -- Some setup
        end)

        _:after(function()
            -- Some teardown
        end)

        _:test("Hookup test", function()
            _:expect("Foo").is("Foo")
        end)

    end)
end

I’m going to use one assertion per test. Briefly that’s because when there’s more than one, and one fails, the framework doesn’t make it clear which assertion has failed.

My “story” is this:

Given an array of (hex) integers, and an integer bit number, return the one or zero bit at that location in the array, starting at word 1, the leftmost bit.

I figure a good test array will look like this:

    local words = {0x80000001, 0x7FFFFFFE }

The first word has only the first and last bit set, the second only the first and last unset. Hm, no. A possible failure is to start at the wrong end of the word. How about this:

    local words = {0x80000004, 0x7FFFFFF7 }

Biggest problem with that is figuring out the answers. Imagine a more random test. Anyway, way too much obsessing, let’s write a test:

        _:test("leftmost bit", function()
            _:expect(fetchBit(words,0)).is(1)
        end)

This fails:

1: leftmost bit -- Tests:19: attempt to call a nil value (global 'fetchBit')

Not a surprise. Fake it till you make it:

function fetchBit(words, n)
    return 1
end

Works, ship it.

I should mention that the “fake it till you make it” pattern was invented by Kent Beck, and while it seems kind of dumb, it results in your setting up the function and its return in the right shape. We could have skipped the parameter definition, of course, but how fanatical do we really want to be? Let’s write a test that makes us write some code:

        _:test("leftmost bit is one", function()
            _:expect(fetchBit(words,0)).is(1)
        end)
        
        _:test("bit one is zero", function()
            _:expect(fetchBit(words,1)).is(0)
        end)

I gave the second test a better name, and so I renamed the first one to match. Now we’ll have to do some work.

Now of course we know basically how this has to go. We’re going to mod n against 32 to select the word, and shift against the reminder to position the bit and and it off. I could work that out on paper or in my head, and probably be right. What I prefer to do, however, is to keep as little in my head as I can, because I enjoy the melon-like sound of things striking it.

Therefore my practice when writing things that are even this tricky is to write them out longhand. When we’re evolving the code this works rather neatly. Let’s see if it does this time.

Both these tests happen to hit the first word. So the nearly minimal code we can write is something like this:

function fetchBit(words, n)
    local word = words[1]
    local shifted = word >> shift
    return shifted&1
end

This shows the shape of my proposed solution, and it also lets me focus on the value of shift. It should be 31 when n is zero, and 30 when n is 1. Sounds a lot like 31 - n to me.

(Yes, I know there needs to be a remainder in there. I could put it in now, but the test doesn’t require it. So I am playing dumb and just letting the tests tell me what to do. It’s not that I don’t know. I promise.)

function fetchBit(words, n)
    local word = words[1]
    local shift = 31-n
    local shifted = word >> shift
    return shifted&1
end

Both tests run. Now we’ll drive out the mod and remainder:

        _:test("bit 32 is zero", function()
            _:expect(fetchBit(words,32)).is(0)
        end)

Remember that words looks like this:

local words = {0x80000004, 0x7FFFFFF7 }

That actually runs, to my surprise. Why? Because we’re going to shift right -1 times, whatever that does, and it’s going to return zero throughout. Mrrph.

Belay that test. I’ve not even fetched the 4 bit out of the first word. Here’s my new test 3:

        _:test("bit 29 is one", function()
            _:expect(fetchBit(words,29)).is(1)
        end)

That one has the courtesy to run correctly. Let’s think a bit more about the next test. We need to drive out two things: the fetching of the next word, and remaindering the bit number. And we’ve learned that testing next for zero is a poor idea. How about this, then:

        _:test("bit 33 is one", function()
            _:expect(fetchBit(words,33)).is(1)
        end)

32 is the zero bit, which we do expect to be zero and will check soon, while 33 is bit 1 in the next word, which is 1. This test should fail.

4: bit 33 is one -- Actual: 0, Expected: 1

Yes. Now we can make it work properly:

function fetchBit(words, n)
    local wordNr = 1 + n//32
    local word = words[wordNr]
    local shift = 31-n%32
    local shifted = word >> shift
    return shifted&1
end

Test runs. And I’m quite sure others will as well, though I’ll write a few more in a moment. First let’s read our little program in its longhand form. I rather like it.

  • the word number we want is one, plus n divided by 32. We force integer division, since otherwise Lua would return a float.
  • the word we want is the array subscripted by word number.
  • the shift we need is 31 minus the remainder of n mod 32, i.e. the leftover number of bits after the divide calculation has taken out all but the last 0-31.
  • the shift puts the bit of interest at the right end of the word
  • we and it off and return it

I’m really confident that this works, and if it turns out later on in the series that it doesn’t, there’ll be some learnin’ to do, but I’m going to write a couple more tests for security.

        
        _:test("bit 32 is zero", function()
            _:expect(fetchBit(words,32)).is(0)
        end)
        
        _:test("bit 63 is zero", function()
            _:expect(fetchBit(words,63)).is(0)
        end)

To my very great surprise, the 63 test fails.

6: bit 63 is zero -- Actual: 1, Expected: 0

What’s up with that? What’s the input:

    local words = {0x80000004, 0x7FFFFFF7 }

Oh, right. I thought I had FE there but I changed my mind. We’ll fix that test and also fetch bit 60, which should be zero, if I’ve counted correctly on my fingers:

        _:test("bit 63 is one", function()
            _:expect(fetchBit(words,63)).is(1)
        end)
        
        _:test("bit 60 is zero", function()
            _:expect(fetchBit(words,60)).is(0)
        end)

Now I’m really sure this thing works. And it does need to be fast, I’m guessing (and shouldn’t), so it is arguably a good idea to fold up all these Explaining Temporary Variables into one marvelous hard-to-understand expression.

I fold it up carefully and leave the old version because I think the resulting code is correct but not communicative:

--[[
function fetchBit(words, n)
    local wordNr = 1 + n//32
    local word = words[wordNr]
    local shift = 31-n%32
    local shifted = word >> shift
    return shifted&1
end
]]--

function fetchBit(words, n)
    return (words[1 + n//32] >> (31-n%32))&1
end

I have no idea what the precedence of all those operators is, and I have no desire to know. I ain’t afraid of no parentheses. Well, no, I am afraid of no parentheses, and I’m not afraid of parentheses. These classical references are hard to manage sometimes.

Summing Up

We’re off to a marvelous start. We have 47 lines of test and 3 lines of code. I expect to see this article quoted as proving that TDD is inefficient, since any fool could have coded this up and debugged it in no time.

On the other hand, I coded it up with confidence that it works, and while eating a lovely breakfast as I worked. It took very little concentration, because the code said exactly what it meant at every moment.

A good result. Next time, maybe even later today, I’ll see about making something that looks like whatever that computer archaeology code represents.

I tried to put the project under Working Copy but haven’t been able to make it work yet. Will keep trying and have a support request in.

See you next time!

Invaders.zip