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