Performing a saturation

[Mahagon]

Hello again!

Following idea: I want to add/sub two Q0.31 fixed point numbers. So any addition that results in a value greater than +0.9999999995 or lesser than -1 is not showable in Q0.31. So i want to perform a saturation to the given max/min values. How can i handle this nicely?

My first selfmade idea was something like that:

Code: Select all

signed int result, a, b;

result=a+b;

//check for overflow
if(result<0)
	    {//a and b were positive?; so result should've been positive to
	    	if(a>0&&b>0)
	    	{
	    		temp=0x7FFFFFFF;//Q0.31 value for +0.9999999995
	    	}
	    }

	    else
	   	    {//vice versa
	   	    	if(a<0&&b<0)
	   	    	{
	   	    		temp=0x80000001;//Q0.31 value for -1
	   	    	}
	   	    }

That is working at the moment, but honestly its quiet complex and not very smooth and im not sure if its totally correct.

I've found the page http://github.xcore.com/doc_tips_and_tr ... point.html where something like:

Code: Select all

overflow = sext(x,24) != x;

is given. I've tried to port that on a Q0.31 number, but i dont get it.

Any suggestions for me?^^

Greetings

[Ross]

Code: Select all

overflow = sext(x,24) != x;

is given. I've tried to port that on a Q0.31 number, but i dont get it.

On its own that will just tell you that you need to do some saturation, you would need something like:

Code: Select all

 a = sext(b, 24);
 if(a != b)
  {
        if(b>>32)  
            b = (0x80000000);
        else
            b = (0x7fffffff);
    }

[segher]

Maybe something like (warning, untested):

Code: Select all

add_sat:
        add r2,r0,r0
        add r3,r1,r1
        ladd r0,r1,r0,r1,r2
        ladd r2,r3,r2,r3,r2
        eq r2,r1,r3
        bt r2,0f
        mkmsk r0,5
        mkmsk r0,r0
        add r0,r0,r1
0:      retsp 0

which uses the fact that there is an overflow exactly if the carry
out of the highest bit is not equal to the carry into the highest bit.

First this computes (in r2 and r3) the function arguments (r0 and r1)
shifted left one bit, so that the top bit is chopped off and if we then
later add r2 and r3, we'll get as carry what would be the carry into
the highest bit in the normal add.

Then we compute in r0 the result of the normal add, and into r1 and
r3 the two carries. Then, if they're equal we just return (we have the
result in r0 already). If not we load 0x7fffffff (the two mksmk insns,
you can do an ldw of course if you like that better), and then add the
"normal" carry, so that we get 0x7fffffff for a positive overflow, and
0x80000000 for a negative overflow (if you _really_ want 0x80000001
for a negative overflow, just do that last add another time. But you
_really_ do not want that :-) )

[Mahagon]

Maybe something like (warning, untested):

Code: Select all

add_sat:
        add r2,r0,r0
        add r3,r1,r1
        ladd r0,r1,r0,r1,r2
        ladd r2,r3,r2,r3,r2
        eq r2,r1,r3
        bt r2,0f
        mkmsk r0,5
        mkmsk r0,r0
        add r0,r0,r1
0:      retsp 0

which uses the fact that there is an overflow exactly if the carry
out of the highest bit is not equal to the carry into the highest bit.

First this computes (in r2 and r3) the function arguments (r0 and r1)
shifted left one bit, so that the top bit is chopped off and if we then
later add r2 and r3, we'll get as carry what would be the carry into
the highest bit in the normal add.

Then we compute in r0 the result of the normal add, and into r1 and
r3 the two carries. Then, if they're equal we just return (we have the
result in r0 already). If not we load 0x7fffffff (the two mksmk insns,
you can do an ldw of course if you like that better), and then add the
"normal" carry, so that we get 0x7fffffff for a positive overflow, and
0x80000000 for a negative overflow (if you _really_ want 0x80000001
for a negative overflow, just do that last add another time. But you
_really_ do not want that :-) )

Hiho,

sorry to grab out that old thread. But i think its still better, than creating a new one. At the moment i'm working on saturation again. My current solution works fine, but I have the target to reach a better performance, and so i wanted to try seghers idea. But i'm really really bad on that inline assembly ... C is my world ;) ... i understand seghers assembler flow, but i cant port it to inline assembly (i dont get that variable handling and so on ... theres always crap comming out at the end. just the adds are working right now.)

Can someone help me to get the assembler code above in xmos inline assembly ?

start is something like:

Code: Select all

signed int add_saturated(signed int a, signed int b)
{
     asm(.........................);

     return a_added_b_saturated;
}

[Ross]

Probably easiest to put the code in a .S file. Something like the following (untested)

Code: Select all

.extern add_sat
.globl add_sat.nstackwords
.linkset add_sat.nstackwords, 0
.globl add_sat
.text 
add_sat:
        add r2,r0,r0
        add r3,r1,r1
        ladd r0,r1,r0,r1,r2
        ladd r2,r3,r2,r3,r2
        eq r2,r1,r3
        bt r2,add_sat_ret
        mkmsk r0,5
        mkmsk r0,r0
        add r0,r0,r1
add_sat_ret:      
        retsp 0

(Note, the annotations for the compiler are not complete, but this should be a good starting point)

[segher]

I think I swapped the outputs of the LADD instructions, e.g. "ladd r0,r1,..." should be "ladd r1,r0,...". It's confusing :-)