# 32-bit Division Algorithm Description

Started by July 24, 2001
 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); } __________________________________________________