.file "wm_sqrt.S"
/*---------------------------------------------------------------------------+
| wm_sqrt.S |
| |
| Fixed point arithmetic square root evaluation. |
| |
| Copyright (C) 1992,1993,1995,1997 |
| W. Metzenthen, 22 Parker St, Ormond, Vic 3163, |
| Australia. E-mail billm@suburbia.net |
| |
| Call from C as: |
| int wm_sqrt(FPU_REG *n, unsigned int control_word) |
| |
+---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------+
| wm_sqrt(FPU_REG *n, unsigned int control_word) |
| returns the square root of n in n. |
| |
| Use Newton's method to compute the square root of a number, which must |
| be in the range [1.0 .. 4.0), to 64 bits accuracy. |
| Does not check the sign or tag of the argument. |
| Sets the exponent, but not the sign or tag of the result. |
| |
| The guess is kept in %esi:%edi |
+---------------------------------------------------------------------------*/
#include "exception.h"
#include "fpu_emu.h"
#ifndef NON_REENTRANT_FPU
/* Local storage on the stack: */
#define FPU_accum_3 -4(%ebp) /* ms word */
#define FPU_accum_2 -8(%ebp)
#define FPU_accum_1 -12(%ebp)
#define FPU_accum_0 -16(%ebp)
/*
* The de-normalised argument:
* sq_2 sq_1 sq_0
* b b b b b b b ... b b b b b b .... b b b b 0 0 0 ... 0
* ^ binary point here
*/
#define FPU_fsqrt_arg_2 -20(%ebp) /* ms word */
#define FPU_fsqrt_arg_1 -24(%ebp)
#define FPU_fsqrt_arg_0 -28(%ebp) /* ls word, at most the ms bit is set */
#else
/* Local storage in a static area: */
.data
.align 4,0
FPU_accum_3:
.long 0 /* ms word */
FPU_accum_2:
.long 0
FPU_accum_1:
.long 0
FPU_accum_0:
.long 0
/* The de-normalised argument:
sq_2 sq_1 sq_0
b b b b b b b ... b b b b b b .... b b b b 0 0 0 ... 0
^ binary point here
*/
FPU_fsqrt_arg_2:
.long 0 /* ms word */
FPU_fsqrt_arg_1:
.long 0
FPU_fsqrt_arg_0:
.long 0 /* ls word, at most the ms bit is set */
#endif /* NON_REENTRANT_FPU */
.text
ENTRY(wm_sqrt)
pushl %ebp
movl %esp,%ebp
#ifndef NON_REENTRANT_FPU
subl $28,%esp
#endif /* NON_REENTRANT_FPU */
pushl %esi
pushl %edi
pushl %ebx
movl PARAM1,%esi
movl SIGH(%esi),%eax
movl SIGL(%esi),%ecx
xorl %edx,%edx
/* We use a rough linear estimate for the first guess.. */
cmpw EXP_BIAS,EXP(%esi)
jnz sqrt_arg_ge_2
shrl $1,%eax /* arg is in the range [1.0 .. 2.0) */
rcrl $1,%ecx
rcrl $1,%edx
sqrt_arg_ge_2:
/* From here on, n is never accessed directly again until it is
replaced by the answer. */
movl %eax,FPU_fsqrt_arg_2 /* ms word of n */
movl %ecx,FPU_fsqrt_arg_1
movl %edx,FPU_fsqrt_arg_0
/* Make a linear first estimate */
shrl $1,%eax
addl $0x40000000,%eax
movl $0xaaaaaaaa,%ecx
mull %ecx
shll %edx /* max result was 7fff... */
testl $0x80000000,%edx /* but min was 3fff... */
jnz sqrt_prelim_no_adjust
movl $0x80000000,%edx /* round up */
sqrt_prelim_no_adjust:
movl %edx,%esi /* Our first guess */
/* We have now computed (approx) (2 + x) / 3, which forms the basis
for a few iterations of Newton's method */
movl FPU_fsqrt_arg_2,%ecx /* ms word */
/*
* From our initial estimate, three iterations are enough to get us
* to 30 bits or so. This will then allow two iterations at better
* precision to complete the process.
*/
/* Compute (g + n/g)/2 at each iteration (g is the guess). */
shrl %ecx /* Doing this first will prevent a divide */
/* overflow later. */
movl %ecx,%edx /* msw of the arg / 2 */
divl %esi /* current estimate */
shrl %esi /* divide by 2 */
addl %eax,%esi /* the new estimate */
movl %ecx,%edx
divl %esi
shrl %esi
addl %eax,%esi
movl %ecx,%edx
divl %esi
shrl %esi
addl %eax,%esi
/*
* Now that an estimate accurate to about 30 bits has been obtained (in %esi),
* we improve it to 60 bits or so.
*
* The strategy from now on is to compute new estimates from
* guess := guess + (n - guess^2) / (2 * guess)
*/
/* First, find the square of the guess */
movl %esi,%eax
mull %esi
/* guess^2 now in %edx:%eax */
movl FPU_fsqrt_arg_1,%ecx
subl %ecx,%eax
movl FPU_fsqrt_arg_2,%ecx /* ms word of normalized n */
sbbl %ecx,%edx
jnc sqrt_stage_2_positive
/* Subtraction gives a negative result,
negate the result before division. */
notl %edx
notl %eax
addl $1,%eax
adcl $0,%edx
divl %esi
movl %eax,%ecx
movl %edx,%eax
divl %esi
jmp sqrt_stage_2_finish
sqrt_stage_2_positive:
divl %esi
movl %eax,%ecx
movl %edx,%eax
divl %esi
notl %ecx
notl %eax
addl $1,%eax
adcl $0,%ecx
sqrt_stage_2_finish:
sarl $1,%ecx /* divide by 2 */
rcrl $1,%eax
/* Form the new estimate in %esi:%edi */
movl %eax,%edi
addl %ecx,%esi
jnz sqrt_stage_2_done /* result should be [1..2) */
#ifdef PARANOID
/* It should be possible to get here only if the arg is ffff....ffff */
cmp $0xffffffff,FPU_fsqrt_arg_1
jnz sqrt_stage_2_error
#endif /* PARANOID */
/* The best rounded result. */
xorl %eax,%eax
decl %eax
movl %eax,%edi
movl %eax,%esi
movl $0x7fffffff,%eax
jmp sqrt_round_result
#ifdef PARANOID
sqrt_stage_2_error:
pushl EX_INTERNAL|0x213
call EXCEPTION
#endif /* PARANOID */
sqrt_stage_2_done:
/* Now the square root has been computed to better than 60 bits. */
/* Find the square of the guess. */
movl %edi,%eax /* ls word of guess */
mull %edi
movl %edx,FPU_accum_1
movl %esi,%eax
mull %esi
movl %edx,FPU_accum_3
movl %eax,FPU_accum_2
movl %edi,%eax
mull %esi
addl %eax,FPU_accum_1
adcl %edx,FPU_accum_2
adcl $0,FPU_accum_3
/* movl %esi,%eax */
/* mull %edi */
addl %eax,FPU_accum_1
adcl %edx,FPU_accum_2
adcl $0,FPU_accum_3
/* guess^2 now in FPU_accum_3:FPU_accum_2:FPU_accum_1 */
movl FPU_fsqrt_arg_0,%eax /* get normalized n */
subl %eax,FPU_accum_1
movl FPU_fsqrt_arg_1,%eax
sbbl %eax,FPU_accum_2
movl FPU_fsqrt_arg_2,%eax /* ms word of normalized n */
sbbl %eax,FPU_accum_3
jnc sqrt_stage_3_positive
/* Subtraction gives a negative result,
negate the result before division */
notl FPU_accum_1
notl FPU_accum_2
notl FPU_accum_3
addl $1,FPU_accum_1
adcl $0,FPU_accum_2
#ifdef PARANOID
adcl $0,FPU_accum_3 /* This must be zero */
jz sqrt_stage_3_no_error
sqrt_stage_3_error:
pushl EX_INTERNAL|0x207
call EXCEPTION
sqrt_stage_3_no_error:
#endif /* PARANOID */
movl FPU_accum_2,%edx
movl FPU_accum_1,%eax
divl %esi
movl %eax,%ecx
movl %edx,%eax
divl %esi
sarl $1,%ecx /* divide by 2 */
rcrl $1,%eax
/* prepare to round the result */
addl %ecx,%edi
adcl $0,%esi
jmp sqrt_stage_3_finished
sqrt_stage_3_positive:
movl FPU_accum_2,%edx
movl FPU_accum_1,%eax
divl %esi
movl %eax,%ecx
movl %edx,%eax
divl %esi
sarl $1,%ecx /* divide by 2 */
rcrl $1,%eax
/* prepare to round the result */
notl %eax /* Negate the correction term */
notl %ecx
addl $1,%eax
adcl $0,%ecx /* carry here ==> correction == 0 */
adcl $0xffffffff,%esi
addl %ecx,%edi
adcl $0,%esi
sqrt_stage_3_finished:
/*
* The result in %esi:%edi:%esi should be good to about 90 bits here,
* and the rounding information here does not have sufficient accuracy
* in a few rare cases.
*/
cmpl $0xffffffe0,%eax
ja sqrt_near_exact_x
cmpl $0x00000020,%eax
jb sqrt_near_exact
cmpl $0x7fffffe0,%eax
jb sqrt_round_result
cmpl $0x80000020,%eax
jb sqrt_get_more_precision
sqrt_round_result:
/* Set up for rounding operations */
movl %eax,%edx
movl %esi,%eax
movl %edi,%ebx
movl PARAM1,%edi
movw EXP_BIAS,EXP(%edi) /* Result is in [1.0 .. 2.0) */
jmp fpu_reg_round
sqrt_near_exact_x:
/* First, the estimate must be rounded up. */
addl $1,%edi
adcl $0,%esi
sqrt_near_exact:
/*
* This is an easy case because x^1/2 is monotonic.
* We need just find the square of our estimate, compare it
* with the argument, and deduce whether our estimate is
* above, below, or exact. We use the fact that the estimate
* is known to be accurate to about 90 bits.
*/
movl %edi,%eax /* ls word of guess */
mull %edi
movl %edx,%ebx /* 2nd ls word of square */
movl %eax,%ecx /* ls word of square */
movl %edi,%eax
mull %esi
addl %eax,%ebx
addl %eax,%ebx
#ifdef PARANOID
cmp $0xffffffb0,%ebx
jb sqrt_near_exact_ok
cmp $0x00000050,%ebx
ja sqrt_near_exact_ok
pushl EX_INTERNAL|0x214
call EXCEPTION
sqrt_near_exact_ok:
#endif /* PARANOID */
or %ebx,%ebx
js sqrt_near_exact_small
jnz sqrt_near_exact_large
or %ebx,%edx
jnz sqrt_near_exact_large
/* Our estimate is exactly the right answer */
xorl %eax,%eax
jmp sqrt_round_result
sqrt_near_exact_small:
/* Our estimate is too small */
movl $0x000000ff,%eax
jmp sqrt_round_result
sqrt_near_exact_large:
/* Our estimate is too large, we need to decrement it */
subl $1,%edi
sbbl $0,%esi
movl $0xffffff00,%eax
jmp sqrt_round_result
sqrt_get_more_precision:
/* This case is almost the same as the above, except we start
with an extra bit of precision in the estimate. */
stc /* The extra bit. */
rcll $1,%edi /* Shift the estimate left one bit */
rcll $1,%esi
movl %edi,%eax /* ls word of guess */
mull %edi
movl %edx,%ebx /* 2nd ls word of square */
movl %eax,%ecx /* ls word of square */
movl %edi,%eax
mull %esi
addl %eax,%ebx
addl %eax,%ebx
/* Put our estimate back to its original value */
stc /* The ms bit. */
rcrl $1,%esi /* Shift the estimate left one bit */
rcrl $1,%edi
#ifdef PARANOID
cmp $0xffffff60,%ebx
jb sqrt_more_prec_ok
cmp $0x000000a0,%ebx
ja sqrt_more_prec_ok
pushl EX_INTERNAL|0x215
call EXCEPTION
sqrt_more_prec_ok:
#endif /* PARANOID */
or %ebx,%ebx
js sqrt_more_prec_small
jnz sqrt_more_prec_large
or %ebx,%ecx
jnz sqrt_more_prec_large
/* Our estimate is exactly the right answer */
movl $0x80000000,%eax
jmp sqrt_round_result
sqrt_more_prec_small:
/* Our estimate is too small */
movl $0x800000ff,%eax
jmp sqrt_round_result
sqrt_more_prec_large:
/* Our estimate is too large */
movl $0x7fffff00,%eax
jmp sqrt_round_result