common/lib/libc/arch/m68k/gen/udivsi3.S

   1 /*      $NetBSD: udivsi3.S,v 1.2 2006/01/05 22:33:34 he Exp $   */
   2
   3 /*-
   4  * Copyright (c) 1990 The Regents of the University of California.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * the Systems Programming Group of the University of Utah Computer
   9  * Science Department.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. Neither the name of the University nor the names of its contributors
  20  *    may be used to endorse or promote products derived from this software
  21  *    without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  */
  35
  36 #include <machine/asm.h>
  37
  38 #if defined(LIBC_SCCS) && !defined(lint)
  39 #if 0
  40         RCSID("from: @(#)udivsi3.s      5.1 (Berkeley) 6/7/90")
  41 #else
  42         RCSID("$NetBSD: udivsi3.S,v 1.2 2006/01/05 22:33:34 he Exp $")
  43 #endif
  44 #endif /* LIBC_SCCS and not lint */
  45
  46 /* unsigned / unsigned */
  47 ENTRY(__udivsi3)
  48 #ifndef __mc68010__
  49         movel   %sp@(4),%d0
  50         divul   %sp@(8),%d0
  51         rts
  52 #else
  53         movel   %d2, %sp@-      | save %d2
  54         movel   %sp@(12), %d0   | load divisor
  55         movel   %sp@(8), %d1    | load dividend
  56
  57 | first, we divide the divisor and dividend by two until
  58 | the divisor fits into 16 bits:
  59 1:      cmpil   #0x10000, %d0
  60         bcs     2f
  61         lsrl    #1, %d0
  62         lsrl    #1, %d1
  63         bra     1b
  64 2:
  65
  66 | now we can do the divide.  to avoid overflow, we have to
  67 | do the divide in two parts, high and low, and add the
  68 | results together:
  69         movew   %d1, %d2        | save low(dividend)
  70         clrw    %d1
  71         swap    %d1             | %d1 = dividend >> 16
  72         divuw   %d0, %d1        | do the high divide
  73         moveal  %d1, %a1        | save high divide result
  74         movew   %d2, %d1        | concat(remainder, low(dividend))
  75         divuw   %d0, %d1        | do the low divide
  76         movel   %a1, %d0        | recover high divide result
  77         swap    %d0
  78         clrw    %d0             | %d0 = finished high divide result
  79         andil   #0xffff, %d1    | %d1 = finished low divide result
  80         addl    %d1, %d0        | %d0 = quotient guess
  81
  82 | the quotient we have so far is only a guess.  the divide we
  83 | did above was really the divide of some dividendB by some
  84 | divisorB, where the following hold:
  85 |
  86 | (dividend - divisor) <= dividendB <= dividend
  87 | (divisor / 2) < divisorB <= divisor
  88 |
  89 | so our guess quotient cannot be less than our real desired
  90 | quotient.  however, it might be one too big.
  91 |
  92 | to adjust this quotient, we multiply it by the original
  93 | divisor and subtract the result from the original dividend.
  94 | if the result is nonnegative, our guessed quotient was
  95 | correct, and the subtraction result is our remainder.
  96 | if the result is negative, our guessed quotient was one
  97 | too big, and the subtraction result plus the original
  98 | divisor is our remainder.
  99 |
 100 | as in mulsi3, we have to do the multiply in stages to avoid
 101 | overflow:
 102
 103         movel   %sp@(12), %d2   | load divisor
 104         swap    %d2
 105         movel   %d0, %d1
 106         muluw   %d2, %d1        | high(divisor) * low(guess)
 107         moveal  %d1, %a1        | save high(divisor) * low(guess)
 108         swap    %d2
 109         movel   %d0, %d1
 110         swap    %d1
 111         muluw   %d2, %d1        | low(divisor) * high(guess)
 112         addl    %a1, %d1
 113         swap    %d1
 114         clrw    %d1             | %d1 = finished high multiply result
 115         moveal  %d2, %a1        | save original divisor
 116         muluw   %d0, %d2        | low(guess) * low(divisor)
 117         addl    %d1, %d2        | %d2 = guess * divisor
 118
 119         movel   %sp@(8), %d1    | load original dividend
 120         subl    %d2, %d1        | subtract
 121         bcc     3f
 122         subql   #1, %d0         | adjust quotient
 123         addl    %a1, %d1        | adjust remainder
 124 3:      movel   %sp@+, %d2      | restore %d2
 125         rts
 126 #endif /* __mc68010__ */