sys/i386/gnu/fpemul/wm_sqrt.s

   1         .file   "wm_sqrt.S"
   2 /*
   3  *  wm_sqrt.S
   4  *
   5  * Fixed point arithmetic square root evaluation.
   6  *
   7  * Call from C as:
   8  *   void wm_sqrt(FPU_REG *n, unsigned int control_word)
   9  *
  10  *
  11  * Copyright (C) 1992,1993,1994
  12  *                       W. Metzenthen, 22 Parker St, Ormond, Vic 3163,
  13  *                       Australia.  E-mail   billm@vaxc.cc.monash.edu.au
  14  * All rights reserved.
  15  *
  16  * This copyright notice covers the redistribution and use of the
  17  * FPU emulator developed by W. Metzenthen. It covers only its use
  18  * in the 386BSD, FreeBSD and NetBSD operating systems. Any other
  19  * use is not permitted under this copyright.
  20  *
  21  * Redistribution and use in source and binary forms, with or without
  22  * modification, are permitted provided that the following conditions
  23  * are met:
  24  * 1. Redistributions of source code must retain the above copyright
  25  *    notice, this list of conditions and the following disclaimer.
  26  * 2. Redistributions in binary form must include information specifying
  27  *    that source code for the emulator is freely available and include
  28  *    either:
  29  *      a) an offer to provide the source code for a nominal distribution
  30  *         fee, or
  31  *      b) list at least two alternative methods whereby the source
  32  *         can be obtained, e.g. a publically accessible bulletin board
  33  *         and an anonymous ftp site from which the software can be
  34  *         downloaded.
  35  * 3. All advertising materials specifically mentioning features or use of
  36  *    this emulator must acknowledge that it was developed by W. Metzenthen.
  37  * 4. The name of W. Metzenthen may not be used to endorse or promote
  38  *    products derived from this software without specific prior written
  39  *    permission.
  40  *
  41  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
  42  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  43  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
  44  * W. METZENTHEN BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  45  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  46  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  47  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  48  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  49  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  50  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  51  *
  52  *
  53  * The purpose of this copyright, based upon the Berkeley copyright, is to
  54  * ensure that the covered software remains freely available to everyone.
  55  *
  56  * The software (with necessary differences) is also available, but under
  57  * the terms of the GNU copyleft, for the Linux operating system and for
  58  * the djgpp ms-dos extender.
  59  *
  60  * W. Metzenthen   June 1994.
  61  *
  62  *
  63  * $FreeBSD: src/sys/gnu/i386/fpemul/wm_sqrt.s,v 1.9.2.1 2000/07/07 00:38:42 obrien Exp $
  64  * $DragonFly: src/sys/i386/gnu/fpemul/Attic/wm_sqrt.s,v 1.3 2003/08/07 21:17:21 dillon Exp $
  65  *
  66  */
  67
  68
  69 /*---------------------------------------------------------------------------+
  70  |  wm_sqrt(FPU_REG *n, unsigned int control_word)                           |
  71  |    returns the square root of n in n.                                     |
  72  |                                                                           |
  73  |  Use Newton's method to compute the square root of a number, which must   |
  74  |  be in the range  [1.0 .. 4.0),  to 64 bits accuracy.                     |
  75  |  Does not check the sign or tag of the argument.                          |
  76  |  Sets the exponent, but not the sign or tag of the result.                |
  77  |                                                                           |
  78  |  The guess is kept in %esi:%edi                                           |
  79  +---------------------------------------------------------------------------*/
  80
  81 #include "fpu_asm.h"
  82
  83
  84 .data
  85 /*
  86         Local storage:
  87  */
  88         ALIGN_DATA
  89 accum_3:
  90         .long   0               /* ms word */
  91 accum_2:
  92         .long   0
  93 accum_1:
  94         .long   0
  95 accum_0:
  96         .long   0
  97
  98 /* The de-normalised argument:
  99 //                  sq_2                  sq_1              sq_0
 100 //        b b b b b b b ... b b b   b b b .... b b b   b 0 0 0 ... 0
 101 //           ^ binary point here */
 102 fsqrt_arg_2:
 103         .long   0               /* ms word */
 104 fsqrt_arg_1:
 105         .long   0
 106 fsqrt_arg_0:
 107         .long   0               /* ls word, at most the ms bit is set */
 108
 109 .text
 110
 111 ENTRY(wm_sqrt)
 112         pushl   %ebp
 113         movl    %esp,%ebp
 114         pushl   %esi
 115         pushl   %edi
 116         pushl   %ebx
 117
 118         movl    PARAM1,%esi
 119
 120         movl    SIGH(%esi),%eax
 121         movl    SIGL(%esi),%ecx
 122         xorl    %edx,%edx
 123
 124 /* We use a rough linear estimate for the first guess.. */
 125
 126         cmpl    EXP_BIAS,EXP(%esi)
 127         jnz     sqrt_arg_ge_2
 128
 129         shrl    $1,%eax                 /* arg is in the range  [1.0 .. 2.0) */
 130         rcrl    $1,%ecx
 131         rcrl    $1,%edx
 132
 133 sqrt_arg_ge_2:
 134 /* From here on, n is never accessed directly again until it is
 135 // replaced by the answer. */
 136
 137         movl    %eax,fsqrt_arg_2                /* ms word of n */
 138         movl    %ecx,fsqrt_arg_1
 139         movl    %edx,fsqrt_arg_0
 140
 141 /* Make a linear first estimate */
 142         shrl    $1,%eax
 143         addl    $0x40000000,%eax
 144         movl    $0xaaaaaaaa,%ecx
 145         mull    %ecx
 146         shll    %edx                    /* max result was 7fff... */
 147         testl   $0x80000000,%edx        /* but min was 3fff... */
 148         jnz     sqrt_prelim_no_adjust
 149
 150         movl    $0x80000000,%edx        /* round up */
 151
 152 sqrt_prelim_no_adjust:
 153         movl    %edx,%esi       /* Our first guess */
 154
 155 /* We have now computed (approx)   (2 + x) / 3, which forms the basis
 156    for a few iterations of Newton's method */
 157
 158         movl    fsqrt_arg_2,%ecx        /* ms word */
 159
 160 /* From our initial estimate, three iterations are enough to get us
 161 // to 30 bits or so. This will then allow two iterations at better
 162 // precision to complete the process.
 163
 164 // Compute  (g + n/g)/2  at each iteration (g is the guess). */
 165         shrl    %ecx            /* Doing this first will prevent a divide */
 166                                 /* overflow later. */
 167
 168         movl    %ecx,%edx       /* msw of the arg / 2 */
 169         divl    %esi            /* current estimate */
 170         shrl    %esi            /* divide by 2 */
 171         addl    %eax,%esi       /* the new estimate */
 172
 173         movl    %ecx,%edx
 174         divl    %esi
 175         shrl    %esi
 176         addl    %eax,%esi
 177
 178         movl    %ecx,%edx
 179         divl    %esi
 180         shrl    %esi
 181         addl    %eax,%esi
 182
 183 /* Now that an estimate accurate to about 30 bits has been obtained (in %esi),
 184 // we improve it to 60 bits or so.
 185
 186 // The strategy from now on is to compute new estimates from
 187 //      guess := guess + (n - guess^2) / (2 * guess) */
 188
 189 /* First, find the square of the guess */
 190         movl    %esi,%eax
 191         mull    %esi
 192 /* guess^2 now in %edx:%eax */
 193
 194         movl    fsqrt_arg_1,%ecx
 195         subl    %ecx,%eax
 196         movl    fsqrt_arg_2,%ecx        /* ms word of normalized n */
 197         sbbl    %ecx,%edx
 198         jnc     sqrt_stage_2_positive
 199 /* subtraction gives a negative result
 200 // negate the result before division */
 201         notl    %edx
 202         notl    %eax
 203         addl    $1,%eax
 204         adcl    $0,%edx
 205
 206         divl    %esi
 207         movl    %eax,%ecx
 208
 209         movl    %edx,%eax
 210         divl    %esi
 211         jmp     sqrt_stage_2_finish
 212
 213 sqrt_stage_2_positive:
 214         divl    %esi
 215         movl    %eax,%ecx
 216
 217         movl    %edx,%eax
 218         divl    %esi
 219
 220         notl    %ecx
 221         notl    %eax
 222         addl    $1,%eax
 223         adcl    $0,%ecx
 224
 225 sqrt_stage_2_finish:
 226         sarl    $1,%ecx         /* divide by 2 */
 227         rcrl    $1,%eax
 228
 229         /* Form the new estimate in %esi:%edi */
 230         movl    %eax,%edi
 231         addl    %ecx,%esi
 232
 233         jnz     sqrt_stage_2_done       /* result should be [1..2) */
 234
 235 #ifdef PARANOID
 236 /* It should be possible to get here only if the arg is ffff....ffff*/
 237         cmp     $0xffffffff,fsqrt_arg_1
 238         jnz     sqrt_stage_2_error
 239 #endif PARANOID
 240
 241 /* The best rounded result.*/
 242         xorl    %eax,%eax
 243         decl    %eax
 244         movl    %eax,%edi
 245         movl    %eax,%esi
 246         movl    $0x7fffffff,%eax
 247         jmp     sqrt_round_result
 248
 249 #ifdef PARANOID
 250 sqrt_stage_2_error:
 251         pushl   EX_INTERNAL|0x213
 252         call    EXCEPTION
 253 #endif PARANOID
 254
 255 sqrt_stage_2_done:
 256
 257 /* Now the square root has been computed to better than 60 bits */
 258
 259 /* Find the square of the guess*/
 260         movl    %edi,%eax               /* ls word of guess*/
 261         mull    %edi
 262         movl    %edx,accum_1
 263
 264         movl    %esi,%eax
 265         mull    %esi
 266         movl    %edx,accum_3
 267         movl    %eax,accum_2
 268
 269         movl    %edi,%eax
 270         mull    %esi
 271         addl    %eax,accum_1
 272         adcl    %edx,accum_2
 273         adcl    $0,accum_3
 274
 275 /*      movl    %esi,%eax*/
 276 /*      mull    %edi*/
 277         addl    %eax,accum_1
 278         adcl    %edx,accum_2
 279         adcl    $0,accum_3
 280
 281 /* guess^2 now in accum_3:accum_2:accum_1*/
 282
 283         movl    fsqrt_arg_0,%eax                /* get normalized n*/
 284         subl    %eax,accum_1
 285         movl    fsqrt_arg_1,%eax
 286         sbbl    %eax,accum_2
 287         movl    fsqrt_arg_2,%eax                /* ms word of normalized n*/
 288         sbbl    %eax,accum_3
 289         jnc     sqrt_stage_3_positive
 290
 291 /* subtraction gives a negative result*/
 292 /* negate the result before division */
 293         notl    accum_1
 294         notl    accum_2
 295         notl    accum_3
 296         addl    $1,accum_1
 297         adcl    $0,accum_2
 298
 299 #ifdef PARANOID
 300         adcl    $0,accum_3      /* This must be zero */
 301         jz      sqrt_stage_3_no_error
 302
 303 sqrt_stage_3_error:
 304         pushl   EX_INTERNAL|0x207
 305         call    EXCEPTION
 306
 307 sqrt_stage_3_no_error:
 308 #endif PARANOID
 309
 310         movl    accum_2,%edx
 311         movl    accum_1,%eax
 312         divl    %esi
 313         movl    %eax,%ecx
 314
 315         movl    %edx,%eax
 316         divl    %esi
 317
 318         sarl    $1,%ecx         /* divide by 2*/
 319         rcrl    $1,%eax
 320
 321         /* prepare to round the result*/
 322
 323         addl    %ecx,%edi
 324         adcl    $0,%esi
 325
 326         jmp     sqrt_stage_3_finished
 327
 328 sqrt_stage_3_positive:
 329         movl    accum_2,%edx
 330         movl    accum_1,%eax
 331         divl    %esi
 332         movl    %eax,%ecx
 333
 334         movl    %edx,%eax
 335         divl    %esi
 336
 337         sarl    $1,%ecx         /* divide by 2*/
 338         rcrl    $1,%eax
 339
 340         /* prepare to round the result*/
 341
 342         notl    %eax            /* Negate the correction term*/
 343         notl    %ecx
 344         addl    $1,%eax
 345         adcl    $0,%ecx         /* carry here ==> correction == 0*/
 346         adcl    $0xffffffff,%esi
 347
 348         addl    %ecx,%edi
 349         adcl    $0,%esi
 350
 351 sqrt_stage_3_finished:
 352
 353 /* The result in %esi:%edi:%esi should be good to about 90 bits here,
 354 // and the rounding information here does not have sufficient accuracy
 355 // in a few rare cases. */
 356         cmpl    $0xffffffe0,%eax
 357         ja      sqrt_near_exact_x
 358
 359         cmpl    $0x00000020,%eax
 360         jb      sqrt_near_exact
 361
 362         cmpl    $0x7fffffe0,%eax
 363         jb      sqrt_round_result
 364
 365         cmpl    $0x80000020,%eax
 366         jb      sqrt_get_more_precision
 367
 368 sqrt_round_result:
 369 /* Set up for rounding operations*/
 370         movl    %eax,%edx
 371         movl    %esi,%eax
 372         movl    %edi,%ebx
 373         movl    PARAM1,%edi
 374         movl    EXP_BIAS,EXP(%edi)      /* Result is in  [1.0 .. 2.0)*/
 375         movl    PARAM2,%ecx
 376         jmp     FPU_round_sqrt
 377
 378
 379 sqrt_near_exact_x:
 380 /* First, the estimate must be rounded up.*/
 381         addl    $1,%edi
 382         adcl    $0,%esi
 383
 384 sqrt_near_exact:
 385 /* This is an easy case because x^1/2 is monotonic.
 386 // We need just find the square of our estimate, compare it
 387 // with the argument, and deduce whether our estimate is
 388 // above, below, or exact. We use the fact that the estimate
 389 // is known to be accurate to about 90 bits. */
 390         movl    %edi,%eax               /* ls word of guess*/
 391         mull    %edi
 392         movl    %edx,%ebx               /* 2nd ls word of square*/
 393         movl    %eax,%ecx               /* ls word of square*/
 394
 395         movl    %edi,%eax
 396         mull    %esi
 397         addl    %eax,%ebx
 398         addl    %eax,%ebx
 399
 400 #ifdef PARANOID
 401         cmp     $0xffffffb0,%ebx
 402         jb      sqrt_near_exact_ok
 403
 404         cmp     $0x00000050,%ebx
 405         ja      sqrt_near_exact_ok
 406
 407         pushl   EX_INTERNAL|0x214
 408         call    EXCEPTION
 409
 410 sqrt_near_exact_ok:
 411 #endif PARANOID
 412
 413         or      %ebx,%ebx
 414         js      sqrt_near_exact_small
 415
 416         jnz     sqrt_near_exact_large
 417
 418         or      %ebx,%edx
 419         jnz     sqrt_near_exact_large
 420
 421 /* Our estimate is exactly the right answer*/
 422         xorl    %eax,%eax
 423         jmp     sqrt_round_result
 424
 425 sqrt_near_exact_small:
 426 /* Our estimate is too small*/
 427         movl    $0x000000ff,%eax
 428         jmp     sqrt_round_result
 429
 430 sqrt_near_exact_large:
 431 /* Our estimate is too large, we need to decrement it*/
 432         subl    $1,%edi
 433         sbbl    $0,%esi
 434         movl    $0xffffff00,%eax
 435         jmp     sqrt_round_result
 436
 437
 438 sqrt_get_more_precision:
 439 /* This case is almost the same as the above, except we start*/
 440 /* with an extra bit of precision in the estimate.*/
 441         stc                     /* The extra bit.*/
 442         rcll    $1,%edi         /* Shift the estimate left one bit*/
 443         rcll    $1,%esi
 444
 445         movl    %edi,%eax               /* ls word of guess*/
 446         mull    %edi
 447         movl    %edx,%ebx               /* 2nd ls word of square*/
 448         movl    %eax,%ecx               /* ls word of square*/
 449
 450         movl    %edi,%eax
 451         mull    %esi
 452         addl    %eax,%ebx
 453         addl    %eax,%ebx
 454
 455 /* Put our estimate back to its original value*/
 456         stc                     /* The ms bit.*/
 457         rcrl    $1,%esi         /* Shift the estimate left one bit*/
 458         rcrl    $1,%edi
 459
 460 #ifdef PARANOID
 461         cmp     $0xffffff60,%ebx
 462         jb      sqrt_more_prec_ok
 463
 464         cmp     $0x000000a0,%ebx
 465         ja      sqrt_more_prec_ok
 466
 467         pushl   EX_INTERNAL|0x215
 468         call    EXCEPTION
 469
 470 sqrt_more_prec_ok:
 471 #endif PARANOID
 472
 473         or      %ebx,%ebx
 474         js      sqrt_more_prec_small
 475
 476         jnz     sqrt_more_prec_large
 477
 478         or      %ebx,%ecx
 479         jnz     sqrt_more_prec_large
 480
 481 /* Our estimate is exactly the right answer*/
 482         movl    $0x80000000,%eax
 483         jmp     sqrt_round_result
 484
 485 sqrt_more_prec_small:
 486 /* Our estimate is too small*/
 487         movl    $0x800000ff,%eax
 488         jmp     sqrt_round_result
 489
 490 sqrt_more_prec_large:
 491 /* Our estimate is too large*/
 492         movl    $0x7fffff00,%eax
 493         jmp     sqrt_round_result