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