Division in CDFJ

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Andrew Davie

Technically, division is not possible in the ARMv4T architecture as used in CDFJ bank-switching, and for the longest time I used lookup tables for simple divisions, or repeated subtract loops. But recently I've realised that it's actually possible to do reasonably accurate, extremely quick division simply by multiplying by the reciprocal.

Say you want to divide by 7.  Now if you wrote "x = y/7" you'd have a big fail.  You'd ALSO have a big fail if you wrote "x = y * 1/7", but for a different reason. The GCC compiler will replace 1/7 with a compile-time-calculated value which will effectively be 0 - as we don't have floating point either (at least, I work in integer arithmetic).  But what we CAN do is "x = y * (0x100/7)" -- and that will result in "x = y * 36" being compiled. Well, that's hardly dividing by 7, right?  It's multiplying by 36.  Yes, but if you look closely... the result will be 256 times bigger than we want (because of the 0x100 in the statement).  So if we then shift right by 8 bits, we'll have the answer.  So the full statement would be "x = (y * (0x100/7) >> 8" and what does that give us?  Yep x/7.  Let's work an example.

y = 12345678
so, x = (12345678 * (256/7)) >> 8
 = (12345678 * 36) / 256
 = 1736110

... which, when multiplied by 7 is definitely NOT 12345678.
It's 12152770. The correct answer should be 1763668.285714285714286... (or 1763668 integer).

SO at first glance it's completely wrong. That's because of our inaccuracy in representing 256/7 as 36, when in fact it's 36.57...

Now there's a bunch of round-offs and truncations that happen, so I twiddle the actual value of (256/7) in several ways to make sure my specific use-case works. I might use "(y * (0x10000/7) >> 16" for extra precision, for example. Since that comes to 9362.28... I might round that to 9363. Depends on circumstances/tests. I could use 37, which would give the result 1784336.

In actual use I tend to use the 0x10000 multiplier, so for the given example, we'd have...

x = 12345678 * ((0x10000/7)) >> 16
 = (12345678 * 9362) >> 16
 = 1763614

(remembering the acutal value 1763668.28...) this is certainly good enough for most uses.
Using 9363 would give 1763802 so it's a bit either-or in terms of which is best.


So there we go - a handy tip for dividing by a known constant value in ARM.
It saves heaps of time and space in Boulder Dash, and I use it a lot.


Al_Nafuur

Does this also workes in 6502 ASM?

Andrew Davie

Quote from: Al_Nafuur on 17 Apr 2024, 11:29 AMDoes this also workes in 6502 ASM?

Well, yes in principle.  To divide by a constant, multiply by (0x100/constant) and then shift down 8 bits. Limited bits though. Or you could extend it to 8 or more bits. But in 6502 you don't have hardware multiply so you might as well do a SOFTWARE division because you'll be doing lots of calculations to multiply anyway.

Al_Nafuur

Quote from: Andrew Davie on 17 Apr 2024, 11:38 AM
Quote from: Al_Nafuur on 17 Apr 2024, 11:29 AMDoes this also workes in 6502 ASM?

Well, yes in principle.  To divide by a constant, multiply by (0x100/constant) and then shift down 8 bits. Limited bits though. Or you could extend it to 8 or more bits. But in 6502 you don't have hardware multiply so you might as well do a SOFTWARE division because you'll be doing lots of calculations to multiply anyway.
Yes, I completely overlooked that the 6502 has no general multiplication, so it makes no sense to simulate one by the other.

Thomas Jentzsch

Multiplications can be done much faster than divisions when done in software. So this approach is good for 6507 too.

Fast multiplications can be done using square tables:

Example

This page compares multiple algorithms.

marcoj

Ah, I had wondered about this. When I have tried to divide in CDFJ, it kills off elements of the ARM emulation, but keeps running, at least in Stella. I had done long division by a counter/subtract loop and that worked OK. Interestingly, the Unocart/PlusCart CDFJ version works as expected with the native divide instruction operation - it is supported OK. Now to decide how to handle both cases, probably need to do a long division for both to maintain compatibility. The operation i'm doing is a trigonometric tan operation, which needs to divide by a variable.

JetSetIlly

Quote from: marcoj on 23 Jun 2025, 12:26 PMInterestingly, the Unocart/PlusCart CDFJ version works as expected with the native divide instruction operation - it is supported OK.

If you're targeting the UnoCart/PlusCart then that ARM type has SDIV and UDIV instructions for signed and unsigned divides in hardware (doesn't require the FPU). Not present in the Chameleon Cart unfortunately.

https://github.com/JetSetIlly/Gopher2600
@JetSetIlly@mastodon.gamedev.place
@jetsetilly.bsky.social

marcoj

Ah true. I guess I was quite spoiled with my earlier ACE projects, having hardware division and hard floats. It does make things fast. Long division is acceptable if it can be completed timely, especially in the context of 2600 with it's limited code execution timings.

Here is my long division routine for CDFJ. If the divisor is small enough, it should complete without exceeding the VBLANK/OVERSCAN period.

//Perform long division - dividend/divisor = quotient, with optional remainder
int divide(int dividend, int divisor, int *remainder) {

if (divisor==0)  return 0; //Handle DIV0 case.

//Temporary Store of quotient and remainder
int quotient = 0;
int r = dividend; //remainder begins as the dividend


while (r>0) {
r-=divisor; //subtract divisor each time
if (r>=0) { //Loop again
quotient++; //quotient goes up for every successful substraction where r>0 after operation.
}
}
if (r<0) r += divisor; //Calculate final remainder

*remainder = r;  //Write back remainder through pointer.

return quotient;

}

Thomas Jentzsch

Quote from: marcoj on 23 Jun 2025, 12:26 PMAh, I had wondered about this. When I have tried to divide in CDFJ, it kills off elements of the ARM emulation, but keeps running, at least in Stella.
The CPUs used (e.g. LPC2101) in Harmony carts do not support divide opcodes.

Therefore source codes for effective divisions are published.

Andrew Davie

Quote from: marcoj on 24 Jun 2025, 10:01 PMHere is my long division routine for CDFJ. If the divisor is small enough, it should complete without exceeding the VBLANK/OVERSCAN period.

With respect, repeated subtraction is not a reasonable, nor sufficiently fast, way to do long division on any processor! There are rotate/subtract routines that require at maximum the number of bits in the quotient for ANY dividend/divisor. That is, a 32 bit division would take 32 shifts and 32 subtracts at the very most.

Look for the "restoring division algorithm" for example code and explanations.

Andrew Davie

The following is untested by me - AI generated - but should be a good starting point.

void restoring_divide(unsigned int dividend, unsigned int divisor,
                      unsigned int *quotient, unsigned int *remainder)
{
    unsigned int q = 0;
    unsigned int r = 0;

    for (int i = 31; i >= 0; --i) {
        // Shift left remainder and bring in the next highest bit of dividend
        r = (r << 1) | ((dividend >> i) & 1);

        // Try subtracting divisor
        if (r >= divisor) {
            r = r - divisor;
            q |= (1U << i);  // Set bit i in quotient
        }
        // else: r is automatically restored by not subtracting
    }

    *quotient = q;
    *remainder = r;
}

Thomas Jentzsch

And if you can use assembler, there are even faster routines.

marcoj

Quote from: Andrew Davie on 26 Jun 2025, 12:59 AM
Quote from: marcoj on 24 Jun 2025, 10:01 PMHere is my long division routine for CDFJ. If the divisor is small enough, it should complete without exceeding the VBLANK/OVERSCAN period.

With respect, repeated subtraction is not a reasonable, nor sufficiently fast, way to do long division on any processor! There are rotate/subtract routines that require at maximum the number of bits in the quotient for ANY dividend/divisor. That is, a 32 bit division would take 32 shifts and 32 subtracts at the very most.

Look for the "restoring division algorithm" for example code and explanations.

Hmmm, using the divide algorithms does seem a lot more attractive. The subtract method has worked OK where the divisor is very low and repeatably so,say 40. However the screen is indeed rolling where the divisor is over about 200. There seems to be quite a few algorithms, some using look up tables, others not. Being able to complete the calculation in a predictable time is an advantage. 

marcoj

With some adaption, it slotted right in, and no more screen rolling.

int divide(unsigned int dividend, unsigned int divisor,
                      unsigned int *remainder)
{
    unsigned int q = 0;
    unsigned int r = 0;

    for (int i = 31; i >= 0; --i) {
        // Shift left remainder and bring in the next highest bit of dividend
        r = (r << 1) | ((dividend >> i) & 1);

        // Try subtracting divisor
        if (r >= divisor) {
            r = r - divisor;
            q |= (1U << i);  // Set bit i in quotient
        }
        // else: r is automatically restored by not subtracting
    }

    *remainder = r;
    return q;

}