Unit testing on an 8-bit CPU

* * * * *

Unit testing on an 8-bit CPU

I've been using my assembler [1] to write silly little programs for the Color
Computer [2] (simulated [3]—easier than setting up my Color Computer, the
first computer I owned as a kid). It took me entirely too long to locate a
bug in a maze-drawing program I've been writing, and I want to do a deep dive
on this.

The program is simple, it just draws a maze, following a few simple rules:

1. pick a random direction (up, right, left or down);
2. attempt to draw a maze segment (using color 1) in the given direction;
3. if we're boxed in (no direction to go in)—
3. 1. if we're at the starting location, we're done;
3. 2. backtrack along a segment of the path we've drawn (using color 2);
3. 3. if we are no longer boxed in, go back to step 1;
3. 4. otherwise, go back to step 3.

Nothing hard about it, yet the program kept getting stuck.

[Image of a partially drawn maze] [4]

It starts in the upper left, meanders a bit (in blue), backtracks a bit (in
red) until it gets stuck. I would then stare at the code until blood formed
on my brow, simplify the code if I could, and try again only to watch it get
stuck, again.

The issue is that I have no debugger on this system. I don't have two screens
upon which to show debugging output. I have no way of single-stepping though
the code. I don't even have a log to go through. Debugging consists of
running the code, then thinking real hard. And yes, it was a stupid mistake
that took all of two lines of code to fix.

[Image of a fully drawn maze] [5]

Now, the question I want to ask is—would I have saved time if I did “unit
testing?” Not just testing, which I was doing all along, but the typical
style of “unit testing” where you test a “unit” of code (getting back to that
question again [6]). Looking over the code [7] (and that version has the bug—
see if you can find it; you'll also need these two [8] files [9]), the most
isolated “unit” is random (the last subroutine in the code).

-----[ Assembly ]-----
;***********************************************************************
; RANDOM Generate a random number
;Entry: none
;Exit: B - random number (1 - 255)
;***********************************************************************

random ldb lfsr
andb #1
negb
andb #$B4
stb ,-s ; lsb = -(lfsr & 1) & taps
ldb lfsr
lsrb ; lfsr >>= 1
eorb ,s+ ; lfsr ^= lsb
stb lfsr
rts
-----[ END OF LINE ]-----

It implements a linear-feedback shift register [10] with a period of 255 (in
that it will return each value in the range of 1‥255 once in some randomesque
order before repeating, which is Good Enough™ for this code). So what if we
want to test that the code is correct?

And it's here I came to a realization—“unit testing” really depends upon the
language and tooling around it. Modern orthodoxy holds “unit testing über
alles” and therefore, modern languages and tooling is created to support
“unit testing über alles” (and woe betide those who question it). I think my
struggle with “unit testing” is that the environments I find myself in don't
lend themselves very well to “unit testing.” Even when I worked at The
Enterprise, we were using C (C99 at best) and C++ (C++98, maybe C++03?) which
take a lot of work upfront to support “unit testing” well, and there wasn't a
lot of work upfront to support “unit testing” well, and there was a decidely
lack of a “unit testing” framework. And here, there's definitely not a “unit
testing” framework. Any “unit testing” I have to do involves writing yet more
code. So let's write yet more code and test this sucker.

-----[ Assembly ]-----
CHROUT equ $A002 ; BASIC character output routine
lfsr equ $F6 ; unused location in direct page

org $4000

start ldx #result_array ; point to memory
clra ; storing 0 to memory
clrb ; 256 bytes to clear

clrarray sta ,x+ ; clear memory
decb ; decrement count
bne .clrarray ; keep going until count = 0

ldx #result_array ; point to array
lda #255 ; cycle length

checkrnd bsr random ; get random number in B
tst b,x ; have we seen this number?
bne .failed ; if so, we have failed
inc b,x ; set flag for this number
deca ; are we done with the cycle
bne checkrnd ; if not, keep going

ldx #msg.success ; SUCCESS!
bsr puts
rts

;---------------------------------------------------
; Store count (register A) and random # (register B)
; so we can use PEEK in BASIC to see where we failed
;---------------------------------------------------

failed std lfsr+1
ldx #msg.failed ; failed message
bsr puts ; display it
rts ; return to BASIC

puts.10 jsr [CHROUT] ; print character
puts lda ,x+ ; get character
bne puts.10 ; if not NUL, print it
rts ; return to BASIC

;******************************************************************

random ldb lfsr
andb #1
negb
andb #$B4
stb ,-s ; lsb = -(lfsr & 1) & taps
ldb lfsr
lsrb ; lfsr >>= 1
eorb ,s+ ; lfsr ^= lsb
stb lfsr
rts

;*******************************************************************

msg.success asciiz 'SUCCESS!\r'
msg.failed asciiz 'FAILED!\r'
result_array equ *
end start
-----[ END OF LINE ]-----

The tooling here doesn't support linking 6809 code, and I'd rather not have
to keep each routine in its own file since the program is so simple and makes
editing it easier if everything is in one file (no IDE (Integrated
Development Environment) here—and yes, I have thoughts about testing and IDEs
but that's beyond the scope for this post). So I have to copy the routine to
the test program.

This was something I kept trying to tell my manager at The Enterprise—the
test program itself might be buggy (he personally treated the output as
gospel—sigh). And the “unit testing” proponents seem to hem and haw about
testing the testing code, implying that one does not simply test the testing
code. But if programmers aren't trusted to write code and must test, then why
are they trusted to write testing code without testing?

It might seem I digress, but I'm not. There are four bugs in the above test.
The code I'm testing, random? It was fine. And I wasn't intending to write a
buggy test harness, it just happened as I was writing it. Bug one—I forgot to
test that random didn't return 0 (that's a degenerate case with LFSR (Linear-
Feedback Shift Register)s). Second bug—I forgot to ininitialize the LFSR
state with a non-zero value, so random would return nothing but zero. The
third bug was thinking I had used the wrong condition when branching to the
failure case, but no, I had it right the first time (the fact that I changed
it, and then changed it back, is the bug). The actual bug that caused this
was the fourth bug, but I have to digress a bit to explain it.

The 6809 has an extensive indexing addressing mode for an 8-bit CPU (Central
Processing Unit). One of the modes allow one to use an accumulator register
(A, B or D) as an offset to the index register. I used the B register, which
contains the random number, as an offset into a 256-element array to track
the return values, thus the use of b,x in the code above. What I forgot about
in the moment of writing the code is that the “accumulator,index-register”
indexing mode sign extends the accumulator. And the first value from random
is, due to the LFSR I'm using, if treated as signed, a negative value—it
would fail on the very first attempt.

Sigh.

This is why I panicked and thought I botched the conditional branch.

Now, all of that just to test the most isolated of subroutines in the
program.

But had I continued, would any form of “unit testing” been beneficial?
There's the subroutine point_addr—which converts an X,Y position into a byte
address in the frame buffer, and the pixel in said byte. I could have done an
exhaustive test of all 4,096 points, again, that's code I would have write
(in 6809 Assembly code) and unfortunately, test, to have any confidence in
it. And working up the chain, there's getpixel and setpixel. Testing those
would require a bit of thought—let's see … getpixel returns the color of the
pixel at the given X,Y location on the screen. and assuming point_addr is
working, it would only take four tests (one per pixel in the byte) but at
this point, would I even trust myself to write the test code?

In fact, would “unit testing” have saved me any time?

Given that I would have to write the testing framework, no, I don't think I
would have saved time. Perhaps if I thought the issue through before diving
into changing the code, I would have solved this earlier.

And the clues were there. I did discover pretty early on that the bug was in
the backtracking code. The top level code is pretty easy to visually inspect:

-----[ Assembly ]-----
backtrack lda #BACKTRACK
sta color

loop ldd xpos ; check to see if we're back
cmpd xstart ; at the starting point,
beq done ; and if so, we're done

ldd xpos ; can we backtrack NORTH?
decb
lbsr getpixel
cmpb #EXPLORE
bne .check_east
lbsr move_north.now ; if so, move NORTH and see if
bra .probe ; we have to keep backtracking

check_east ldd xpos ; east ...
inca
lbsr getpixel
cmpb #EXPLORE
bne .check_west
lbsr move_east.now
bra .probe

check_west ldd xpos ; yada yada ...
deca
lbsr getpixel
cmpb #EXPLORE
bne .check_south
lbsr move_west.now
bra .probe

check_south ldd xpos
incb
lbsr getpixel
cmpb #EXPLORE
bne .probe
lbsr move_south.now

probe bsr boxed_in ; can we stop backtracking?
bne explore ; if so, go back to exploring
bra .loop ; else backtrack some more
-----[ END OF LINE ]-----

The thing to keep in mind here is that the D register is a 16-bit register
where the upper 8-bits is the A register, and the lower 8-bits are the B
register, and that the 6809 is big-endian. So when we do ldd xpos we are
loading the A register with the X coordinate, and B with the Y coordinate.
And the move_*.now subroutines work, or else we wouldn't get the starting
maze segments at all. So it's clear that setpixel works fine.

The code is getting stuck trying to backtrack along already drawn segments,
and it does that by calling getpixel, therefore, it seems prudent to check
getpixel. And sure enough, that is where the bug resides.

-----[ Assembly ]-----
;*************************************************************************
; GETPIXEL Get the color of a given pixel
;Entry: A - x pos
; B - y pos
;Exit: X - video address
; A - 0
; B - color
;*************************************************************************

getpixel bsr point_addr ; get video address
comb ; reverse mask (since we're reading
stb ,-s ; the screen, not writing it)
ldb ,x ; get video data
andb ,s+ ; mask off the pixel
rotate lsrb ; shift color bits
deca
bne .rotate
done rts ; return color in B

;*************************************************************************
; POINT_ADDR calculate the address of a pixel
;Entry: A - xpos
; B - ypos
;Exit: X - video address
; A - shift value
; B - mask
;*************************************************************************

point_addr.bits fcb %00111111,%11001111,%11110011,%11111100 ; masks
fcb 6,4,2,0 ; bit shift counts
-----[ END OF LINE ]-----

I've included a bit of point_addr to give some context. point_addr returns
the number of shifts required to move the color value into place, and one of
those shift values is 0. But getpixel doesn't check to see it's 0 before
decrementing it. And thus, getpixel will return the wrong value for the last
pixel in any byte. The fix is simple:

-----[ Assembly ]-----
tsta
beq .done
-----[ END OF LINE ]-----

just before the .rotate label fixes the bug (two instructions, three bytes
and here's a link to the fixed code [11]).

Yes, I freely admit that a “unit test“ of this subroutine would have shown
the bug. But how much time would I have spent writing the test code to begin
with? The only reason it took me as long as it did to find was because the
reference code I was using was quite convoluted, and I spent time simplifying
the code as I went along (which is worthy of doing anyway).

What I wish the “unit testing” proponents would realize is that easy testing
depends upon the language and tooling involved in the project, and what a
“unit” is truly depends upon the language. I suspect that “unit test”
proponents also find “unit testing” easier to deal with than “integration
testing” or even “end-to-end testing,” thus why we get “unit tests über
alles” shouted from the roof tops.

[1] gopher://gopher.conman.org/0Phlog:2023/11/24.1
[2] https://en.wikipedia.org/wiki/TRS-80_Color_Computer
[3] http://www.6809.org.uk/xroar/
[4] gopher://gopher.conman.org/IPhlog:2023/11/27/stuck-maze.png
[5] gopher://gopher.conman.org/IPhlog:2023/11/27/maze.png
[6] gopher://gopher.conman.org/0Phlog:2023/11/19.1
[7] gopher://gopher.conman.org/0Phlog:2023/11/27/maze-bug.asm
[8] gopher://gopher.conman.org/0Phlog:2023/11/27/Coco-DP.i
[9] gopher://gopher.conman.org/0Phlog:2023/11/27/Coco-video.i
[10] https://en.wikipedia.org/wiki/Linear-feedback_shift_register
[11] gopher://gopher.conman.org/0Phlog:2023/11/27/maze.asm
---

Discussions about this page

Unit testing on an 8-bit CPU - ZeroBytes
https://zerobytes.monster/post/3904613

Unit testing on an 8-bit CPU - derp.foo
https://derp.foo/post/444794

Unit testing on an 8-bit CPU | Hacker News
https://news.ycombinator.com/item?id=38443368

Two Stop Bits | Unit testing on an 8-bit CPU
https://twostopbits.com/item?id=1143

Email author at [email protected]