GP32 Some Tricks For Division

[mATkEUpON]

I started to write a little tutorial to optimize things for the gp32, and I've got something about divisions that might be useful I hope...

Here it is:

Optimizing code for GP32 handheld


1) - Divisions

As you must already know, the ARM 9 hasn't got the divide operation.
Which means that if you use the / operation, the compiler will convert
it into some c code that will do the operation. But this is very slow.

a) Bitwise shifts

Bitwize shift operation (<< and >>) just decays the bits of the given value
either left (<<) or right (>>). Shifting right a value of one bit (x >> 1)
will divide the value by 2. (x >> 2) will divide by 4, etc...
Just be careful to only divide a positive value with this.
Be careful also, the >> operation has the lowest priority, so always enclose it with ().

B) Fixed operand divison

If you have to divide a value by a fixed operand, (w / 24) for example,
you can also use the bitwise shift, which is much more useful than only
dividing by powers of 2.

To do that, you have to use your calculator before, and be careful also
for a few things.
The trick is that we will multiply the value by a constant first, and then
divide by another constant that will be a power of 2.
ex: (213 / 24) = (213 x constant) / 65536
I often choose 65536 as it gives good precision, and leaves some good margin.
Just calculate your constant (here 65536 / 24), which gives ~ 2731
The your code would be:
result = ( (w * 2731) >> 16);

213 / 24 would give 8, and result would also contain 8.

Be careful:

-The value you will divide should be positive, but also should fit into an
integer when multiplied by the constant (which limits precision sometimes...).
-The constant should always be rounded to the upper value (2105.12 would give 2106).

c) Divison with a common operand

When you will have to do many divisions with the same value (which is variable),
you can use the same trick, by storing the constant into a global variable.
ex: (witdh / zoom) => when the same zoom value will be used for the whole display

constant = 65536 / zoom;

Then to divide by zoom:

w = ( (width * constant) >> 16);

 

[Rico]

NICE work! Don't forget though, that the compiler tends to auto-optimise power-of-two division at the very least, although I'm not sure whether or nor it optimises anything else.

 

[Robster]

One correction, the shift operator handles negative numbers just fine. If you're shifting a number left, sign will not be affected as long as the result doesn't overflow. If shifting right, the operation copies the sign bit of the operand to the sign bit of the result - for example, -4 (0xFFFFFFFD) becomes -2 (0xFFFFFFFE). In binary terms,

sign                                   sign
|                                      |
11111111 11111111 11111111 11111101 -> 11111111 11111111 11111111 11111110

 

[mATkEUpON]

Actually I always guessed it would cause a problem, as I never use that in my programs for numbers that can be negative. Thanks for the tip then !!!!

 

[Inopia]

in many cases, you can use a 1/x table mucho fast!

also, read this:

http://www.cs.helsinki.fi/u/jikorhon/conde.../doc/thedoc.txt

 

[Squidge]

Here's some other webpages with optimized math routines:

ARM code square root routines:
http://www.finesse.demon.co.uk/steven/sqrt.html

Division 32/32=32 Bit
Division 64/32=32 Bit
Floating Point Routines Single Precision
http://www.peter-teichmann.de/ahinte.html

 

[bs42]

And: If you have to divide with a constant or many times thru the same value, computing the reciprocal may help:

a/b = a * 1/b
// compute the 1/r1
// destroy r2,r3

mov r2,r1
cmp r2,#0x00010000
movlo r2,r2,lsl #16

cmp r2,#0x01000000
movlo r2,r2,lsl #8

cmp r2,#0x10000000
movlo r2,r2,lsl #4

cmp r2,#0x40000000
movlo r2,r2,lsl #2

cmp r2,#0x80000000
movlo r2,r2,lsl #1

mov r3,#1
rsc r0,r2,#0
mov r2,r2,lsr #1
1:
cmp r0,r2
adc r3,r3,r3
subcs r0,r0,r2
cmp r1,r2
movne r2,r2,lsr #1
bne 1b

cmp r0,#0
addne r3,r3,#1
mov r1,r3

; r0/r1
later:
mov r3,r0
mov r2,r1
umull r1,r0,r3,r2 // r0 = r0/r1

42Bastian

 

[dr.no]

[...]
mov r2,r1
cmp r2,#0x00010000
movlo r2,r2,lsl #16
[...]

Just one general, off-topic question from a noob:
When deving for GP32, do you have to use assembly code a lot? Of course when you plan to optimize a emulator etc., you should - but do you have to to get decent speed in your projects?

 

[rtb7]

No

 

[TeDaDeS]

[...]
mov r2,r1
cmp r2,#0x00010000
movlo r2,r2,lsl #16
[...]

Just one general, off-topic question from a noob:
When deving for GP32, do you have to use assembly code a lot? Of course when you plan to optimize a emulator etc., you should - but do you have to to get decent speed in your projects?

The compiler will create good code, but its the programmer that doesn't know this.
Some that do, know the compiler sometimes does something you don't think you need. Then you use assembly to get rid of it.
You might get a extra frame out of that.

 

[mATkEUpON]

It will create good code, if you use -O2 at least as option. I noticed major slowdowns on loops in my game, that will appear if I didn't use it, and you won't see anything if you use -O2.

But even with this, divisions will never automatically be converted to any of these faster routines.

But the important thing is always to keep in mind which actions will be repeated a lot of times and work on them.

 

[fdave]

[...]
mov r2,r1
cmp r2,#0x00010000
movlo r2,r2,lsl #16
[...]

Just one general, off-topic question from a noob:
When deving for GP32, do you have to use assembly code a lot? Of course when you plan to optimize a emulator etc., you should - but do you have to to get decent speed in your projects?

No. I once recoded the entire graphics engine for an emulator in assembler. It ran 1% slower than the C version.

Compilers are smart and people are dumb

I never use assembler for anything if I can possibly avoid it, because compilers are so good. Okay, some don't know about LDMIA, but you could put a tiny bit of assembler in if it was going to make a difference. Make it the exception and not the rule though.

The single exception is emulator cpu cores, and *ONLY* cpu cores, not the rest of the emulator. And that's only because of two things:
- Flag calculations
- Opcode jumping

I use a few techniques in C which is sort of call "fast C", but it's not usually caleld that. e.g. consider this:

int i=0;
for (i=0;i<width;i++)
{
plot a pixel
}


now consider this:
int i=0;
if (width>0)
do
{
plot a pixel
i++;
}
while (i<width)

Same effect, however one has two branches per iteration and the other has one. Makes for much better assembly. So basically the idea is to code as good assembly as you possibly can without actually coding any assembly directly
You merely try and coax the compiler into making good decisions.
Now at first there's very little point other than compatibility, but after a while, it becomes a natural part of your coding style, and then you automatically become a 'faster' programmer. Cool huh?!

It's quite a black art - if you look though the Pico and GigaDrive source there's quite a lot of little random things like that.

Anyone else got anything similar?

 

[Ranting Nord]

A stupid way to do division:

int divide(int numerator, int denominator)
{
if(numerator < denominator)
return 0:
return 1 + divide(numerator - denominator, denominator);
}

Yay for me! B)

 

[mr.spiv]

Small is beatiful - unsigned 32bits to 32bis division:

@
@ Parameters:
@  r0 = dividend
@  r1 = divisor
@ returns:
@  r0 = quotient
@
divu_32d32s:
        mov       r3,r0
        mov       r2,r1
        cmp       r2,r3,lsr #1
0:     movls      r2,r2,lsl #1
        cmp       r2,r3,lsr #1
        bls       0b
        @
        mov       r0,#0
1:      cmp       r3,r2
        subcs      r3,r3,r2
        adc       r0,r0,r0
        mov       r2,r2,lsr #1
        cmp       r2,r1
        bhs       1b
        @
        mov       pc,lr

 

[mATkEUpON]

:rolleyes: great !!

 

[bs42]

Just one general, off-topic question from a noob:
When deving for GP32, do you have to use assembly code a lot? Of course when you plan to optimize a emulator etc., you should - but do you have to to get decent speed in your projects?

Use assembly wise

Most often C compilers produce decent code, but they generally add an overhead.
I earn my living with writing RTOS in assembly, the assembly version (any CPU) is about 20%..40%
smaller and 20%..%40 faster than the one in C/C++ !

But I would not write an TCP/IP stack in assembly, I crazy, but not that crazy.

 

[bs42]

Small is beatiful - unsigned 32bits to 32bis division:

divu_32d32s:
        mov       r3,r0

        mov       r2,r1
        cmp       r2,r3,lsr #1
0:     movls      r2,r2,lsl #1
        cmp       r2,r3,lsr #1
        bls       0b

I'd replace the first loop by this (untested, no ARM at hand

cmp r1,r3,lsr #16
movls r2,r1,lsl #16
movhi r2,r1

cmp r2,r3,lsr #8
movls r2,r2,lsl #8

cmp r2,r3,lsr #4
movls r2,r2,lsl #4

cmp r2,r3,lsr #2
movls r2,r2,lsl #2

cmp r2,r3,lsr #1
movls r2,r2,lsl #1

Which does omit the branch and has a fixed length (binary search).

42Bastian

 

[mr.spiv]

I'd replace the first loop by this (untested, no ARM at hand

I didn't show an unroller version because "small is beatiful" statement <_< If you have shorter version of equivalent ly fast algortihm I would really love to see one. Nice optimization in any case!