Reply by dharani kumar ●July 24, 20012001-07-24
Dear Friends,

I am working with ADSP-2192, I have a Fixed-point
C-code with me I could not understand one 32-bit
Division function ("div_32" function) how it is has
implemented in fixed point implementation. Please
kindly give the algorithm description for the below
program ( I have also included some of the important
functions that are called in the div_32 function):

/******************************************************
*
* Function Name : div_32
*
* Purpose :
*
* Fractionnal integer division of two 32 bit numbers.
* L_num / L_denom
* L_num and L_denom must be positive and L_num <
L_denom
* L_denom = denom_hi<<15 + denom_lo
* denom_hi is a normalized number
* The result is in Q30
*
* Complexity Weight : 52
*
* Inputs :
*
* L_num
* 32 bit long signed integer (Word32) whose value
falls in the
* range : 0x0000 0000 <= L_num <= L_denom.
*
* (L_denom = denom_hi<<15 + denom_lo)
*
* denom_hi
* 16 bit normalized integer whose value falls in the
* range : 0x4000000 < hi < 0x7fff ffff.
*
* denom_lo
* 16 bit positive integer whose value falls in the
* range : 0 < lo < 0x7fff ffff.
*
* Outputs :
*
* none
*
* Returned Value :
*
* L_div
* 32 bit long signed integer (Word32) whose value
falls in the
* range : 0x0000 0000 <= L_div <= 0x3fff ffff.
* L_div is a Q30 value (point between b30 and b29)
*
* Algorithm :
*
* - find = 1/L_denom
* First approximation: approx = 1 / denom_hi
* 1/L_denom = approx * (2.0 - L_denom * approx )
* - result = L_num * (1/L_denom)
*
************************************************************************/

Word32 div_32(Word32 L_num, Word16 denom_hi, Word16
denom_lo)
{
Word16 approx, hi, lo, n_hi, n_lo;
Word32 t0; /* First approximation: 1 / L_denom = 1/denom_hi */

approx = div_s( (Word16)0x3fff, denom_hi); /* result
in Q15 */
/* 1/L_denom = approx * (2.0 - L_denom * approx) */

t0 = mpy_mix(denom_hi, denom_lo, approx); /* result
in Q29 */

t0 = L_sub( (Word32)0x40000000, t0); /* result in
Q29 */

L_extract(t0, &hi, &lo);

t0 = mpy_mix(hi, lo, approx); /* = 1/L_denom in
Q28 */

/* L_num * (1/L_denom) */

L_extract(t0, &hi, &lo);
L_extract(L_num, &n_hi, &n_lo);
t0 = mpy_32(n_hi, n_lo, hi, lo);

return( L_shl( t0,(Word16)2) ); /* From Q28 to Q30
*/
}
/************************************************************************
*
* Function Name : L_extract
*
* Purpose :
*
* Extract from a 31 bit integer two 16 bit DPF.
*
* Complexity Weight : 5
*
* Inputs :
*
* L_32
* 32 bit long signed integer (Word32) with b30 ==
b31
* whose value falls in the range : 0xc000 0000 <=
L_32 <= 0x3fff ffff.
*
* Outputs :
*
* hi
* b15 to b30 of L_32
*
* lo
* L_32 - hi<<15
*
* Returned Value :
*
* none
*
************************************************************************/

void L_extract(Word32 L_32, Word16 *hi, Word16 *lo)
{
*hi = extract_h( L_shl( L_32,(Word16)1 ) );
*lo = extract_l( sub_sh( L_32, *hi, (Word16)15 ) );
return;
} /************************************************************************
*
* Function Name : mpy_mix
*
* Purpose :
*
* Multiply a 16 bit integer by a 32 bit (DPF).
* The result is divided by 2**16
* L_32 = hi1*lo2 + (lo1*lo2)>>15
*
* Complexity Weight : 4
*
* Inputs :
*
* hi1
* hi part of 32 bit number
*
* lo1
* lo part of 32 bit number
*
* lo2
* 16 bit number
*
* Outputs :
*
* none
*
* Returned Value :
*
* L_var_out
* 32 bit long signed integer (Word32) whose value
falls in the
* range : 0x0000 0000 <= L_var_out <= 0x7fff ffff.
*
************************************************************************/

Word32 mpy_mix(Word16 hi1, Word16 lo1, Word16 lo2)
{
Word16 p1;
Word32 L_32;

p1 = extract_h(L_mult0(lo1, lo2));
L_32 = L_mult0(hi1,lo2 );

return(add_sh( L_32, p1, (Word16)1 ));
} /************************************************************************
*
* Function Name : mpy_32
*
* Purpose :
*
* Multiply two 32 bit integers (DPF). The result is
divided by 2**32
* L_32 = hi1*hi2 + (hi1*lo2)>>15 + (lo1*hi2)>>15)
*
* Complexity Weight : 7
*
* Inputs :
*
* hi1
* hi part of first number
*
* lo1
* lo part of first number
*
* hi2
* hi part of second number
*
* lo2
* lo part of second number
*
* Outputs :
*
* none
*
* Returned Value :
*
* L_var_out
* 32 bit long signed integer (Word32) whose value
falls in the
* range : 0x0000 0000 <= L_var_out <= 0x7fff ffff.
*
*************************************************************************/

Word32 mpy_32(Word16 hi1, Word16 lo1, Word16 hi2,
Word16 lo2)
{
Word16 p1, p2;
Word32 L_32;

p1 = extract_h(L_mult0(hi1, lo2));
p2 = extract_h(L_mult0(lo1, hi2));
L_32 = L_mult0(hi1, hi2);
L_32 = add_sh( L_32, p1, (Word16)1 );

return(add_sh( L_32, p2, (Word16)1 ));
} /************************************************************************
*
* Function Name : L_shl
*
* Purpose :
*
* Arithmetically shift the 32 bit input L_var1 left
var2 positions. Zero fill the var2 LSB * of the
result. If var2 is negative, L_var1 right by -var2
arithmetically shift with sign
* extension. Saturate the result in case of
underflows or overflows.
*
* Complexity Weight : 2
*
* Inputs :
*
* L_var1
* 32 bit long signed integer (Word32) whose value
falls in the
* range : 0x8000 0000 <= L_var1 <= 0x7fff ffff.
*
* var2
* 16 bit short signed integer (Word16) whose value
falls in the
* range : 0xffff 8000 <= var2 <= 0x0000 7fff.
*
* Outputs :
*
* none
*
* Returned Value :
*
* L_var_out
* 32 bit long signed integer (Word32) whose value
falls in the
* range : 0x8000 0000 <= L_var_out <= 0x7fff ffff.
*
************************************************************************/
Word32 L_shl(Word32 L_var1, Word16 var2)
{
Word32 L_var_out;
if (var2 <= 0)
{
L_var_out = L_shr( L_var1, (Word16)(-var2) );
}
else
{
for(;var2>0;var2--)
{
if (L_var1 > (Word32) 0X3fffffff)
{
Overflow = 1;
L_var_out = MAX_32;
break;
}
else
{
if (L_var1 < (Word32) 0xc0000000)
{
Overflow = 1;
L_var_out = MIN_32;
break;
}
}
L_var1 *= 2;
L_var_out = L_var1;
}
}
return(L_var_out);
}

/************************************************************************
*
* Function Name : L_sub
*
* Purpose :
*
* 32 bits subtraction of the two 32 bits variables
(L_var1-L_var2) with
* overflow control and saturation; the result is set
at +2147483647 when
* overflow occurs or at -214783648 when underflow
occurs.
*
* Complexity Weight : 2
*
* Inputs :
*
* L_var1
* 32 bit long signed integer (Word32) whose value
falls in the
* range : 0x8000 0000 <= L_var1 <= 0x7fff ffff.
*
* L_var2
* 32 bit long signed integer (Word32) whose value
falls in the
* range : 0x8000 0000 <= L_var2 <= 0x7fff ffff.
*
* Outputs :
*
* none
*
* Returned Value :
*
* L_var_out
* 32 bit long signed integer (Word32) whose value
falls in the
* range : 0x8000 0000 <= L_var_out <= 0x7fff ffff.
*
************************************************************************/

Word32 L_sub(Word32 L_var1, Word32 L_var2)
{
Word32 L_var_out;

L_var_out = L_var1 - L_var2;

if (((L_var1 ^ L_var2) & MIN_32) != 0)
{
if ((L_var_out ^ L_var1) & MIN_32)
{
L_var_out = (L_var1 < 0L) ? MIN_32 : MAX_32;
Overflow = 1;
}
}
return(L_var_out);
}
__________________________________________________