Hardware Division via Multiplication

[+SpiceWare]

In Frantic I draw the playfield using datastreams with a 0.20 increment, which repeats the playfield data over 5 scanlines. All collision processing in Frantic is done using software, so to determine collisions with the playfield I needed to divide the Y position by 5.

 

The ARM used in the Harmony/Melody does not have support for division, but it does support multiplication. Most of you are probably familiar with fractional or subpixel positioning the moveable objects in the 2600, and we can use the same idea to implement hardware division by using what's known as Reciprocal Multiplication.  Basically Y / 5 is the same as Y * 0.20 , and we can implement that by allocating the lower X bits of the 32 bit value as the fractional value. The article I linked to has this handy chart:

 

n	scaled reciprocal	shift count
3	1010101010101011 AAAB	17
5	1100110011001101 CCCD	18
6	1010101010101011 AAAB	18
7	10010010010010011	19
9	1110001110001111 E38F	19
10	1100110011001101 CCCD	19
11	1011101000101111 BA2F	19
12	1010101010101011 AAAB	19
13	1001110110001010 9D8A	19
14	10010010010010011	20
15	1000100010001001 8889	19

 

Which shows us that to divide by 5 we need to use the lower 18 bits as the fractional value, and that 0.20 works out to be 0xCCCD.

 

#define DIV_BY_5                0xCCCD
#define DIV_BY_5_SHIFT          18

    y5 = (y * DIV_BY_5) >> DIV_BY_5_SHIFT;

 

You'll notice the list skips a number of values - for those we can use bit shifting to divide by powers of 2:

    result = value >> 1; // divide by 2
    result = value >> 2; // divide by 4
    result = value >> 3; // divide by 8
    result = value >> 4; // divide by 16

 

The table is based on needing to divide a 16 bit value, which does not work for /7 or /14.  I haven't looked into it, but suspect they'd work just fine to divide a Y position which is an 8 bit value.  The article does go into the extra steps needed to divide a 16 bit value by 7 or 14.

 

[Omegamatrix]

A while ago I started working on a header file with a bunch of constants for division. I'm posting what I have here so that other people can use it. Note, some of the values don't work for the full 16 bit range but most can handle a pretty decent amount of numbers.

 

Math.h

[+Andrew Davie]

Just reading up on CDFJ+ to see how to get up to speed, and came to this page as part of the documentation.

I just thought I'd add that for division by known constant, I pretty much let the compiler do all the work for me.

I usually allocate 16 bits for fraction and do this...

 

divide_by_5 = (value * (0x10000 / 5)) >> 16;

divide_by_17 = (value * (0x10000 / 17)) >> 16;

 

No need for tables or looking up shifts/values.