Mame Gp2x Inline Assembler For Vector Games

[slaanesh]

I was having a look at the vidhrdw/vector.c and found that there already is some inline ASM for multiply instructions.
This works well as it seems ARM has a nice multiply command to do this easily.

Here's the equivalent 'C' code if there is no ASM version:

CODE
#ifndef vec_mult
INLINE int vec_mult(int parm1, int parm2)
{
int temp,result;

temp = abs(parm1);
result = (temp&0x0000ffff) * (parm2&0x0000ffff);
result >>= 16;
result += (temp&0x0000ffff) * (parm2>>16 );
result += (temp>>16 ) * (parm2&0x0000ffff);
result >>= 16;
result += (temp>>16 ) * (parm2>>16 );

if( parm1 < 0 )
return(-result);
else
return( result);
}
#endif


But we do have some ASM; here it is:

CODE
#define vec_mult _vec_mult
INLINE int _vec_mult(int x, int y)
{
int res_hi, res_lo;

__asm__ __volatile__
("smull\t%1,%0,%2,%3"
: "=r"(res_hi), "=r"(res_lo)
: "r"(x), "r"(y)
);

return res_hi;
}


I was wondering if we could do the same thing for divide?
I realize that the ARM doesn't have native DIVIDE functionality, but perhaps an ASM guru could whip up the equivalent ASM from this 'C' code?

The vector case looks specific and it seems to be doing some sanity and bounds checking, however a generic version may also be handy for other areas of code with lots of divide maths.

Anyone interested?

Here's the vector divide code:

CODE
#ifndef vec_div
INLINE int vec_div(int parm1, int parm2)
{
if( (parm2>>12) )
{
parm1 = (parm1<<4) / (parm2>>12);
if( parm1 > 0x00010000 )
return( 0x00010000 );
if( parm1 < -0x00010000 )
return( -0x00010000 );
return( parm1 );
}
return( 0x00010000 );
}
#endif

 

[Squidge]

True, it doesn't have hardware divide, but it does have hardware multiply, and you can always divide by using multiplication. That is, unless gcc has already optimised the code to do that.

 

[slaanesh]

...you can always divide by using multiplication.

By using non-integers? Wouldn't that be slow again?

ie. 100 / 10 = 10

or

100 * 0.1 = 10

Or is there some other cunning method?

 

[Franxis]

...you can always divide by using multiplication.

By using non-integers? Wouldn't that be slow again?

ie. 100 / 10 = 10

or

100 * 0.1 = 10

Or is there some other cunning method?


With fixed point. E.g. ((unsigned)(100<<8)) * ((unsigned)(1<<5))>>8
Probably the example is not ok

 

[hal9000]

By using non-integers? Wouldn't that be slow again?

ie. 100 / 10 = 10

or

100 * 0.1 = 10

Or is there some other cunning method?

Do never use float on GP2X. It is extremely slow.

As Franxis said, use fixed point arithmetic. Let's be a bit more precise on the example

Let's say you use 24.8 representation (24 bits for the integer part and 8 bits for the remaining part). The precision of the number you can define will be 1/256. You could do 16.16 too, if you need more precision.

100 will be represented by 100<<8
0.1 will be represented by 0,1*256~=26

Then you do ((100<<8)*26)>>8), and you obtain the result in 24.8 representation.

You should always be carefull that none of your value, including the tmp ones inside expressions, overflow 24 bits.

 

[slaanesh]

Thanks for these suggestions.

However what I really want is an assembler version of a fast divide, something specifically tailored to provide the ARM with the fastest possible divide function but which is functionally equivalent to the 'C' library.

The suggestions made look interesting, but I am wondering if these will be functionally equivalent to a normal 'C' library integer divide?

In the example given:

100/10=10

How does this transform into ((100<<8)*26)>>8)?

ie.

#define DIV(a,B) ((a<<8) * (???) >>8)

 

[Squidge]

I was thinking more along the lines of using 32-bit overflow as a speedup. Too late now (and I'm being nagged at), so I'll post more tomorrow. Basically it's just integer multiplication, and the usual operators (shifts, and, etc)

 

[slaanesh]

I was thinking more along the lines of using 32-bit overflow as a speedup. Too late now (and I'm being nagged at), so I'll post more tomorrow. Basically it's just integer multiplication, and the usual operators (shifts, and, etc)

Yes please! I'm interested in all suggestions

EDIT: I was having a look at www.arm.com which provide some examples of division.

They recommend a couple things.

1). If the denominator is a value to the power of 2 then you can just use LSR (or >> in 'C') "value of power".

ie. 100 / 16 is faster written as 100>>4 (because 2^4 = 16)
1000 / 64 is faster written as 1000>>6 (because 2^6 = 64)
and so on.,,

2). Similar to 1), using logical AND as an equivalent to modulus where values are to the power of 2. The key is to use a value of n-1 for the AND.

ie. 100 % 16 is faster written as 100&15
1000 % 64 is faster written as 1000&63
and so on.

I already knew of these two and they are a great way of speeding up divides/modulus functions.
Perhaps GCC already does this for us, I'm not sure?

3). Using unsigned datatypes is also faster as there are otherwise additional instructions required to handle signedness.

I didn't know this one!

 

[slaanesh]

Does anyone have the ARM assembler skills to produce the following code?

http://courses.cs.vt.edu/~cs1104/BuildingB...divide.030.html

 

[Squidge]

didn't you get or understand my pm?

 

[bitbank]

if you're forced into the shift and subtract method, hopefully you can use ARMv5 instructions such as CLZ to save a few instructions in aligning the divisor with the dividend.

With CLZ (count leading zeros) you can quickly determine if the divisor is a simple power of 2 (1 bit set) and then just do a shift. If not, then a more complicated loop would be required.

Knowledge of the data you're working with is the best way to optimize your code. e.g. knowing how probable certain inputs are you can code the shortest code path for the frequent/best case.

L.B.

 

[bitbank]

Here's some off the cuff code to quickly determine if your divisor is a simple power of 2
R0 = divisor
R1 = dividend

CLZ r4,r0
MOV r5,r0,LSL r4 ; shift it up to compare with 0x80000000
CMP r5,#0x80000000 ; is it a simple power of 2?
RSBEQ r6,r4,#31 ; get the shift amount for the dividend
MOVEQ r0,r1,LSR r6 ; do the "divide"
BXEQ LR ; return with quotient in R0

L.B.

 

[slaanesh]

didn't you get or understand my pm?

I got your PM - thanks. I investigated the shift and subtract algorithm which looks nice, however I as thinking that an ASM version of it would probably be easy to write (if one knows ASM) and consquently faster too.

I was thinking that there might be ASM short cuts which don't have 'C' equivalents, like aligning the dividend and divisor and Bitbank has now made clear too.

Thanks everyone for your answers!

 

[Blah]

Sometimes nothing works better than precalculating at runtime and storing the results in a LUT...but that's too easy

 

[HenrikE]

There is a CLZ instruction on the GP2x? Really??

 

[Exophase]

There is a CLZ instruction on the GP2x? Really??

No. ARM920T is ARMv4, not ARMv5.

 

[fishybawb]

There is a CLZ instruction on the GP2x? Really??

No. ARM920T is ARMv4, not ARMv5.


According to this it does, even though it indeed doesn't (SIGILL). I have a history of misreading technical docs though, so I could be missing something obvious

 

[Squidge]

There is a CLZ instruction on the GP2x? Really??

Thanks for bringing up a 9 month old thread... I got half way through before noticing! :angry:

 

[Exophase]

According to this it does, even though it indeed doesn't (SIGILL). I have a history of misreading technical docs though, so I could be missing something obvious



Wow, that's pretty bad, that a product document would get that wrong. Especially considering it got the ARMv4T part right. clz, bkpt, and blx are definitely not part of ARMv4. I know this for sure because they're not on the GBA, also because I tried using blx on GP2X before realizing it was not in fact ARMv5 and got a nice error message.

 

[slaanesh]

I was thinking more along the lines of using 32-bit overflow as a speedup. Too late now (and I'm being nagged at), so I'll post more tomorrow. Basically it's just integer multiplication, and the usual operators (shifts, and, etc)

Just a quick follow up to this. I think Squidge originally meant something like this:

Taken from Flubba's site

CODE
Division by constant
r0 is input/output register.

Division by 3
ldr r1,=0x55555555
umull r2,r0,r1,r0

Division by 5
ldr r1,=0x33333333
umull r2,r0,r1,r0

Division by 7
ldr r1,=0x24924924
umull r2,r0,r1,r0

Division by N
ldr r1,=0x100000000/N
umull r2,r0,r1,r0



With the addition of a look-up table of pre-calculated constants (for r1) I would say you've got a pretty fast divide function.