30

Some classic vector arcade games, such as Battlezone and Red Baron, were based on the 6502 CPU. The processor wasn't fast enough to do the 3D computations, so a co-processor commonly known as the "math box" was used for vertex transformations.

How was the Math Box programmed from the 6502? What API did it provide? What were the performance limitations?

  • I've updated my answer; now it includes almost all of the API. (At least, until I discover another part of the API...) – wizzwizz4 Dec 2 '16 at 21:28
11

Here are my findings:

Disclaimers:

  • This answer is entirely based on mame's mathbox.cpp source and assumes it is correct.
  • This answer focuses on succinct high-level description, even at the cost of being imprecise. (which it is)
  • Despite this, this answer currently misses the high-level intent behind some of the operations. (needs some help from someone more graphics-math-minded?)
  • All names are made up.
  • No warranty etc etc - parts of the answer may be mistaken or incorrect.

notes:

  • All registers/operations are signed unless specified otherwise.
  • Internal registers (REGc..REGf) are ignored by this answer.
  • "8.8 fixed-point" means a 16-bit value whose upper 8-bits contain the whole part and lower 8-bit contain the fractional part e.g. 0x1234 represents 0x12 + (0x34 / 0x100)

The mathbox consists of some 16-bit registers:

  • a result register
  • 12 user-facing registers REG0..REG11 (and some internal ones)

The mathbox has 3 8-bit read addresses:

  • read status byte (0 means done)
  • read low byte of result
  • read high byte of result

And 32 8-bit write addresses:

  • 00 - write low/frac byte of REG0, set result to REG0
  • 01 - write high/whole byte of REG0, set result to REG0
  • 02 - write low/frac byte of REG1, set result to REG1
  • 03 - write high/whole byte of REG1, set result to REG1
  • 04 - write low byte of REG2, set result to REG2
  • 05 - write high byte of REG2, set result to REG2
  • 06 - write low byte of REG3, set result to REG3
  • 07 - write high byte of REG3, set result to REG3
  • 08 - write low/frac byte of REG4, set result to REG4
  • 09 - write high/whole byte of REG4, set result to REG4
  • 0a - write low/frac byte of REG5, set result to REG5
  • 0b - write high/whole byte of REG5, then do sub-then-cross-product
  • 0c - write low byte of REG6, set result to REG6
  • 0d - write low byte of REG10, set result to REG10
  • 0e - write high byte of REG10, set result to REG10
  • 0f - write low byte of REG11, set result to REG11
  • 10 - write high byte of REG11, set result to REG11
  • 11 - write high byte of REG5, then do divide-products
  • 12 - do dot-product
  • 13 - do divide-REG89
  • 14 - do divide
  • 15 - write low byte of REG7, set result to REG7
  • 16 - write high byte of REG7, set result to REG7
  • 17 - set result to REG7
  • 18 - set result to REG9
  • 19 - set result to REG8
  • 1a - write low byte of REG8, set result to REG8
  • 1b - write high byte of REG8, set result to REG8
  • 1c - write high byte of REG5, then do window-test
  • 1d - write high byte of REG3, then do diff-max-plus-3/8-diff-min
  • 1e - do max-plus-3/8-min
  • 1f - unknown (selftest or signature analysis?)

Operation descriptions:

sub-then-cross-product:

  REG4 -= REG2
  REG5 -= REG3
  do cross-product

cross-product:

  // inputs are 8.8 fixed-point
  // interpretable as 2d vectors (REG0, REG1) and (REG5, REG4)
  REG7 = REG0 * REG4 - REG1 * REG5
  result = REG7
  // REG7 receives whole part of result, fractional part goes nowhere

dot-product:

  // inputs are 8.8 fixed-point
  // interpretable as 2d vectors (REG0, REG1) and (REG5, REG4)
  REG8.REG9 = REG0 * REG5 + REG1 * REG4
  result = REG8
  // REG8 receives whole part of result,
  // REG9 receives fractional part - but with its lowest bit forced to 0
  //
  // WARNING: going by the mame source, this operation can continue and do 
  // a divide-REG89 as well (also changing the result register) 
  // if internal register REGf is not -1.
  // (Things like calling sub-then-cross-product or any divide  
  //  will set it to -1, but reset & window-test will likely set it
  //  to some other value.)

divide-REG89:

  // REG8 should be the high/whole part of dividend, 
  // REG9 - the low/fractional part. 
  // REG7 is an integer
  result = REG8.REG9 / REG7, using a size of REG6 (see below)

divide:

  // REG11 should be the high/whole part of dividend, 
  // REG10 - the low/fractional part. 
  // REG7 is an integer
  result = REG11.REG10 / REG7, using a size of REG6 (see below)

divide's REG6 explanation:

  • REG6 controls the size of the division as follows:
  • if REG6 is set to 16, then the full 32-bit dividend is divided by the divisor, resulting in a 16-bit result.
  • if REG6 is set to 8, then only the middle two bytes of the two-word dividend comprise an 8.8 fixed-point dividend, though the other bytes should be 0 (lowest byte) and sign-extension (highest byte) to get a correct result, which is in 1.8 fixed point.
  • other REG6 values (<= 16) seem to act similarly, making up a REG6.REG6 fixed-point dividend, "centered" between the dividend's two words. (Other bits should be 0s and sign-extensions), with the result being in 1.REG6 fixed point.
  • (a lower REG6 is faster)

divide-products:

  // effectively, if REG0,REG1 and REG5,REG4 are 2D vectors
  // this operation computes their (dot-product + REG3),
  // divided by their (cross-product + REG2)
  // (TODO: there's probably a better explanation of what this actually achieves)

  do cross-product // -> REG7
  do dot-product // -> REG8.REG9
  REG7 += REG2
  REG8 += REG3
  REG9 &= 0xff00 // mask lower byte (presumably to allow REG6 being >= 8)
  do divide-REG89 // this sets result to the division result

window-test:

  // likely related to computing midpoint-subdivision for line-clipping, or a similar algorithm (thanks @fadden)
  do (REG6 + 1) times:
  {
    midx = (REG4 + REG7) / 2
    midy = (REG5 + REG8) / 2
    if (midx > REG11 && midx > midy && midx + midy >= 0):
    {
      REG7 = midx
      REG8 = midy
    }
    else
    {
      REG4 = midx
      REG5 = midy
    }
  }
  REG6 = -1
  result = REG8

diff-max-plus-3/8-diff-min:

  REG2 = abs(REG2 - REG0)
  REG3 = abs(REG3 - REG1)
  do max-plus-3/8-min

max-plus-3/8-min:

  result = max(REG2, REG3) + (3/8) * min(REG2, REG3)

Thanks for Tommy and fadden for pointing out that the complex math is most likely meant to be vector math.

| improve this answer | |
  • 1
    "window-test" might be midpoint subdivision, used for line clipping. – fadden Jul 10 '19 at 22:14
  • 1
    @fadden that's exactly what I thought; I also think the stuff about complex numbers is a misdirect: it looks more likely to be used as a vector dot product, which you'd use to apply a transformation to a vector. E.g. it'd directly do the 2d rotations of Asteroids, and if you did it twice you could apply an arbitrary 3d transform. – Tommy Jul 10 '19 at 23:52
  • @Tommy: I agree about the complex numbers. The docs at jmargolin.com/uvmath/uvmenu.htm discuss using the dot product for surface normals, but make no reference to quaternions. I haven't figured out what the deal with computing 3/8ths of things is though. – fadden Jul 11 '19 at 0:06
  • @ fadden & @Tommy - yeah, vector math does make more sense than complex numbers, I was thrown off by the register order, but if the points are given by (REG0,REG1) and (REG5,REG4), then the complex-number multiplies do become vector dot/cross product, which does make a whole lot more sense for 2d games. I'll edit. – secondperson Jul 11 '19 at 0:59
  • One more guess: 3/8ths might be to do with the aspect ratio for final output? I've no great confidence in this guess; I'm of course taking it as given that it wasn't worth implementing 4/8ths because you hardly need a maths box for that. – Tommy Jul 11 '19 at 3:43
19

The 6502 accesses the Atari Math Box, via a pre-defined memory map and address decoder,[1§I] as a memory-mapped I/O device.[1§IV] The top four bits of the External Address Bus are sent to the address decoder to determine whether to activate the high-score module, the POKEY module or the Math Box for a given operation.[1§IV]

The bottom five bits of the External Address Bus are sent to ROM A1 in the Math Box, which calls one of 32 instructions accordingly.[1§IV.A][2#87-297] The Math Box communicates on the bi-directional External Data Bus,[1§Fig. 4] where the Math Box's four AM2091 chips' input and output lines are connected.[1§IV.B] There are 16 registers,[2#14-29] which are 16-bits each.[Inferred from [2]]

Writing to memory addresses 6080 -609F (inclusive) starts the Math Box clock and runs the specified routine.[1§IV] The lower five bits of the memory address will determine the lower five bits of the External Address Bus and thus the instruction that will be executed. This is the mapping between the five-bit instruction number and the instruction executed:

  • 0x00: Sets the low byte of register 0x00 to input, then returns register 0x00.[2#89]
  • 0x01: Sets the high byte of register 0x00 to input, then returns register 0x00.[2#90]
  • 0x02: Sets the low byte of register 0x01 to input, then returns register 0x01.[2#91]
  • 0x03: Sets the high byte of register 0x01 to input, then returns register 0x01.[2#92]
  • 0x04: Sets the low byte of register 0x02 to input, then returns register 0x02.[2#93]
  • 0x05: Sets the high byte of register 0x02 to input, then returns register 0x02.[2#94]
  • 0x06: Sets the low byte of register 0x03 to input, then returns register 0x03.[2#95]
  • 0x07: Sets the high byte of register 0x03 to input, then returns register 0x03.[2#96]
  • 0x08: Sets the low byte of register 0x04 to input, then returns register 0x04.[2#97]
  • 0x09: Sets the high byte of register 0x04 to input, then returns register 0x04.[2#98]
  • 0x0a: Sets the low byte of register 0x05 to input, then returns register 0x05.[2#100]
  • 0x0b: ?
  • 0x0c: Sets the low byte of register 0x06 to input, then returns register 0x06.[2#103]
  • 0x0d: Sets the low byte of register 0x0a to input, then returns register 0x0a.[2#112]
  • 0x0e: Sets the high byte of register 0x0a to input, then returns register 0x0a.[2#113]
  • 0x0f: Sets the low byte of register 0x0b to input, then returns register 0x0b.[2#114]
  • 0x10: Sets the high byte of register 0x0b to input, then returns register 0x0b.[2#115]
  • 0x11: ?
  • 0x12: ?
  • 0x13: ?
  • 0x14: ?
  • 0x15: Sets the low byte of register 0x07 to input, then returns register 0x07.[2#106]
  • 0x16: Sets the high byte of register 0x07 to input, then returns register 0x07.[2#107]
  • 0x17: Returns register 0x07.[2#117]
  • 0x18: Returns register 0x09.[2#119]
  • 0x19: Returns register 0x08.[2#118]
  • 0x1a: Sets the low byte of register 0x08 to input, then returns register 0x08.[2#109]
  • 0x1b: Sets the high byte of register 0x08 to input, then returns register 0x08.[2#110]
  • 0x1c: Window test?[2#248-263]
  • 0x1d: ?
  • 0x1e: Set register 0x0d to max(register 0x02, register 0x03) and set register 0x0c to min(register 0x02, register 0x03), then increment register 0x0d by (3/8 times register 0x0c), then return register 0x0d.[2#278-288]
  • 0x1f: Some sort of self-test or signature analysis?[2#290-294]

No function loads the low byte of register 0x05 without performing a computation.[2#101] No function loads the high part of register 0x06 at all,[2#104] so it could be overwritten during certain functions. I assume that the input is one byte, because the MAME implementation's[2] repeated bitshift-and-XOR makes more sense that way.

| improve this answer | |
  • I'm not sure how the input / return relates to the API in the above text, but might work that out soon. If anyone else can work out what any other part of the code does, please comment and / or edit this answer and / or post your own answer. – wizzwizz4 Dec 2 '16 at 21:16
  • @secondperson Please do! I could barely find any information online; if you know more, then please please write up an answer. – wizzwizz4 Jul 10 '19 at 19:18
8
  • 0x1e is a very clever (and rapid) approximation to sqrt (a^2 + b^2).
  • 0x1d is distance between two points.
  • 0x1c is, I'm fairly sure, to clip a point to screen coords. It doesn't seem to be used in any released game I have the roms for.

Here's my writeup after tearing apart the Battlezone microcode and the Mame code extant at the time, as 6502 source. Yes, I have a half-written game targetted at Tempest hardware.

; Tempest mathbox commands, reverse-engineered from the mame source, snippets of
; original 'malibu' source by Owen Rubin and Ed Logg, disassemblies of red baron,
; tempest and battlezone and comments made on the internet by Owen Rubin, Jed Margolin
; Ed Rotberg and Mike Albaugh

; The Mathbox appears to the programmer as a memory mapped device (mapped at 0x6080 - 
; 0x6100 in tempest)  Writing to one of these locations triggers a mathbox command.  Not 
; all locations are valid, according to the mame source, but I think mame is wrong, as the
; final op is probably a test op and the clip operation appears broken too (but is unused in
; all mathbox games so would not actually break anything)

; The same mathbox was used for (at least) battlezone, red baron, vortex and tempest.  
; A similar (possibly the same) but earlier model was developed by Jed Margolin for
; malibu.  Battlezone and Red Baron are the best places to look for examples of this
; hardware 'in action'; Tempest only ever uses the perspective divide Y' / X'

; All mathbox memory is write-only, with the exception of 2 'result' locations outside 
; of the main 32 byte block and a single mathbox status bit used for testing if the mathbox 
; has finished calculating.

; The coordinate system is funky. Very funky.
; X is into the screen, Y is horizontal, and Z vertical.

; Be extremely careful with division.  if n is not set to 0x10, the results will be
; rather 'wacky'.  You might be able to get 2Y'/X' by using 0x11 and Y'/2X' by using 
; 0x0f, but you will need to mask of bottom and top bits respectively and will lose precision


mb_base           = 0x6080
mb_result_lo      = 0x6060
mb_result_hi      = 0x6070
mb_status         = 0x6040         ; Test using 'foo: bit mb_status; bmi foo'

mb_ld_a           = mb_base + 0x00
mb_ld_b           = mb_base + 0x02
mb_ld_e           = mb_base + 0x04
mb_ld_f           = mb_base + 0x06
mb_ld_x           = mb_base + 0x08
mb_ld_y           = mb_base + 0x0a
mb_calc_xdash     = mb_base + 0x0b ; set y hi 
                                   ; calculate X' = A(X-E) - B(Y-F)
mb_ld_n           = mb_base + 0x0c ; count for clipping and divide, should be 0x10 for divide
mb_ld_z_hi        = mb_base + 0x0d ; 4 byte value, gets blown away regularly
mb_ld_z           = mb_base + 0x0f ; 4 byte value, gets blown away regularly
mb_calc_all       = mb_base + 0x11 ; set y hi 
                                   ; calculate X' = AX - BY + E, 
                                   ; calculate Y' = BX + AY + F, 
                                   ; return Y'/X'
mb_calc_ydash     = mb_base + 0x12 ; Y' = BX + AY + F, 
                                   ; return Y'/X'
mb_calc_yx        = mb_base + 0x13 ; Y'/X'
mb_calc_zx        = mb_base + 0x14 ; Z/X'
mb_ld_xdash       = mb_base + 0x15
mb_rd_xdash       = mb_base + 0x17
mb_rd_ydash_hi    = mb_base + 0x18
mb_rd_ydash       = mb_base + 0x19
mb_ld_ydash       = mb_base + 0x1a
mb_clip           = mb_base + 0x1c ; mame implementation appears useless, is probably wrong 
                                   ; opcode not used in bzone, red baron, or tempest at least.  
                                   ; need to disassemble the mathbox roms and reverse engineer 
                                   ; this and 0x1f.  Or contact Mike Albaugh :-)
mb_calc_distance  = mb_base + 0x1d ; set f hi, approximate sqrt ((f-b)^2 + (e-a)^2)
mb_calc_hypot     = mb_base + 0x1e ; approximate sqrt(f^2+e^2)
mb_illegal        = mb_base + 0x1f ; Not implemented in MAME - self test, maybe?
| improve this answer | |
  • Excellent information! The $1d/$1e functions were a bit baffling. Do you have a disassembly of the Battlezone ROM available somewhere? I'm currently adding wireframe visualization to 6502bench SourceGen (small example: go to 6502disassembly.com/a2-budge3d/… and scroll up a few lines). – fadden Mar 27 at 14:55
2

The earlier answers here explored the calculations that the math box performs. It's also helpful to understand what the games that use it are trying to accomplish. Battlezone, the first game that included it, used the math box for five things:

  1. 3D "view" transform
  2. 3D "model" transform and perspective projection
  3. radar blip position
  4. 2D distance calculation
  5. integer division for arctangent

An important formula to know for the first three is rotation about the Y (vertical) axis:

newX = X * cos(theta) - Z * sin(theta)
newZ = X * sin(theta) + Z * cos(theta)

3D "view" transform

For each object in the world, the game must compute the coordinates of the center of the object relative to the viewer's current position and facing. This requires translating the object's X and Z coordinates to put the viewer at the origin, and then rotating about Y.

The equations for this are:

rel_X = obj_world_X - viewer_X
rel_Z = obj_world_Z - viewer_Z
view_X = rel_X * cos(theta) - rel_Z * sin(theta)
view_Z = rel_X * sin(theta) + rel_Z * cos(theta)

To do this with the math box, we start with:

R0 = cos(theta)
R1 = -sin(theta)
R2 = viewer_Z
R3 = viewer_X

Then, for each object:

R4 = obj_world_Z
R5 = obj_world_X
obj_view_Z = (function $0b)
obj_view_X = (function $12)

3D "model" transform and perspective projection

This one is a bit more complicated. We start with the view coordinates calculated earlier, and must determine the screen X,Y position of every vertex in every visible object.

With the object at the origin, we rotate each vertex's coordinates, translate them to the object's position, and then divide the X and Y coordinates by Z to get the perspective projection. (Battlezone does some peculiar things with the math, but I don't want to get too deep here.)

rotated_Z = vertex_X * sin(theta) + vertex_Z * cos(theta)
model_Z = rotated_Z + obj_view_Z

rotated_X = vertex_X * cos(theta) - vertex_Z * sin(theta)
model_X = rotated_X + obj_view_X

screen_X = model_X / model_Z

model_Y = vertex_Y + obj_world_Y
screen_Y = model_Y / model_Z

To do this with the math box, we set registers to the object's position and facing in view space:

R0 = -cos(theta)
R1 = sin(theta)
R2 = obj_view_Z
R3 = obj_view_X

Then, for each vertex:

R4 = vertex_Z
R5 = vertex_X
screen_X = (function $11)
RB = vertex_Y + obj_world_Y
screen_Y = (function $14)

And that's it. The line clipping is performed by the vector graphics hardware, so the drawing code can just feed (screen_X,screen_Y) into the vector command list. (Actually that's not entirely it, as some results are negated and the mesh is defined a certain way to make the math come out right, but that's essentially it.)

Radar blip position

This needs to do a rotation and then translate the coordinates to where the radar display sits on the screen. It turns out the model transform does the necessary calculations if we pass in some zeroes, and does some extra stuff we can ignore.

The game plugs numbers into the calculation for screen_X with function $11, which returns R8/R7. The game then ignores the result, and uses the intermediate values left in R7 and R8 as the screen coordinates.

2D distance calculation

The game calculates the approximate distance between two objects to see if they have collided. The formula used is an approximation of an approximation, but it works well enough.

The code that uses this typically ignores the "busy" flag in favor of just stalling for 6 cycles. Function $1d or $1e is used depending on whether the code already has the coordinate deltas handy.

Integer division for arctangent

To determine the direction a tank should turn to shoot the player, the game needs to compute an arctangent, which it does with integer division and a lookup table. The math box provides a routine (function $14) that divides a 32-bit value by a 16-bit value with a certain number of iterations.

Note: the iteration count in R6 is set to 10, not 16, for the benefit of the screen-coordinate equations. Values are effectively divided by 64. Battlezone just wants the 8-bit unsigned fractional value here, so it right-shifts the 16-bit result twice more.

Other Notes

In general the math box API doesn't appear to be intended to perform general-purpose vector math; it's intended to solve the equations that Battlezone needed. If you dig into the details, though, it's not a perfect fit.

Consider the rotations performed for the view/model transforms. The sine/cosine values are provided from a table as signed 16-bit fractions, with values from 0 to 0x7fff. (Technically it's using 0.9999695 as an approximation for 1.0... close enough.) When calculating rotated coordinates, the math box code multiplies the numbers and then right-shifts the result 16x, e.g.:

mb_temp = ((int32_t) REG0) * ((int32_t) REG4);
REGc = mb_temp >> 16;

If the code were expecting to multiply two integers or two 8.8 fixed-point values, it wouldn't be right-shifting 16x. It's clearly intended to multiply something by a fractional value, such as the sine/cosine values required for the rotation. However, after multiplying a 1.15 fraction it should right-shift 15x, which means our results are all divided by two. Battlezone deals with this in two different ways. For the view transform, the result is doubled by the 6502 code. For the model transform, the inputs were fixed by doubling the X/Z coordinates in the shape mesh data. (The Y coordinate isn't part of a rotation and doesn't get shifted, so doesn't need to be doubled. Which is why, when you render the meshes, they all look squashed.)

It's possible for the 6502 to continue to do work while the math box is busy. The view transform code takes advantage of this, doing some work on the result from function $0b while function $12 is running.


A full disassembly of Battlezone's 6502 code and vector graphics data is available from 6502disassembly.com. An article with the information from this posting, but in greater detail, is available here.

I want to thank everyone who provided earlier answers to this question. The information helped me make sense of what I was seeing while disassembling the game.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.