1/* 2 * Copyright (c) 1992, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This software was developed by the Computer Systems Engineering group 6 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and 7 * contributed to Berkeley. 8 * 9 * %sccs.include.redist.c% 10 * 11 * from: $Header: umul.s,v 1.4 92/06/25 13:24:05 torek Exp $ 12 */ 13 14#if defined(LIBC_SCCS) && !defined(lint) 15 .asciz "@(#)umul.s 8.1 (Berkeley) 06/04/93" 16#endif /* LIBC_SCCS and not lint */ 17 18/* 19 * Unsigned multiply. Returns %o0 * %o1 in %o1%o0 (i.e., %o1 holds the 20 * upper 32 bits of the 64-bit product). 21 * 22 * This code optimizes short (less than 13-bit) multiplies. Short 23 * multiplies require 25 instruction cycles, and long ones require 24 * 45 instruction cycles. 25 * 26 * On return, overflow has occurred (%o1 is not zero) if and only if 27 * the Z condition code is clear, allowing, e.g., the following: 28 * 29 * call .umul 30 * nop 31 * bnz overflow (or tnz) 32 */ 33 34#include "DEFS.h" 35FUNC(.umul) 36 or %o0, %o1, %o4 37 mov %o0, %y ! multiplier -> Y 38 andncc %o4, 0xfff, %g0 ! test bits 12..31 of *both* args 39 be Lmul_shortway ! if zero, can do it the short way 40 andcc %g0, %g0, %o4 ! zero the partial product and clear N and V 41 42 /* 43 * Long multiply. 32 steps, followed by a final shift step. 44 */ 45 mulscc %o4, %o1, %o4 ! 1 46 mulscc %o4, %o1, %o4 ! 2 47 mulscc %o4, %o1, %o4 ! 3 48 mulscc %o4, %o1, %o4 ! 4 49 mulscc %o4, %o1, %o4 ! 5 50 mulscc %o4, %o1, %o4 ! 6 51 mulscc %o4, %o1, %o4 ! 7 52 mulscc %o4, %o1, %o4 ! 8 53 mulscc %o4, %o1, %o4 ! 9 54 mulscc %o4, %o1, %o4 ! 10 55 mulscc %o4, %o1, %o4 ! 11 56 mulscc %o4, %o1, %o4 ! 12 57 mulscc %o4, %o1, %o4 ! 13 58 mulscc %o4, %o1, %o4 ! 14 59 mulscc %o4, %o1, %o4 ! 15 60 mulscc %o4, %o1, %o4 ! 16 61 mulscc %o4, %o1, %o4 ! 17 62 mulscc %o4, %o1, %o4 ! 18 63 mulscc %o4, %o1, %o4 ! 19 64 mulscc %o4, %o1, %o4 ! 20 65 mulscc %o4, %o1, %o4 ! 21 66 mulscc %o4, %o1, %o4 ! 22 67 mulscc %o4, %o1, %o4 ! 23 68 mulscc %o4, %o1, %o4 ! 24 69 mulscc %o4, %o1, %o4 ! 25 70 mulscc %o4, %o1, %o4 ! 26 71 mulscc %o4, %o1, %o4 ! 27 72 mulscc %o4, %o1, %o4 ! 28 73 mulscc %o4, %o1, %o4 ! 29 74 mulscc %o4, %o1, %o4 ! 30 75 mulscc %o4, %o1, %o4 ! 31 76 mulscc %o4, %o1, %o4 ! 32 77 mulscc %o4, %g0, %o4 ! final shift 78 79 80 /* 81 * Normally, with the shift-and-add approach, if both numbers are 82 * positive you get the correct result. WIth 32-bit two's-complement 83 * numbers, -x is represented as 84 * 85 * x 32 86 * ( 2 - ------ ) mod 2 * 2 87 * 32 88 * 2 89 * 90 * (the `mod 2' subtracts 1 from 1.bbbb). To avoid lots of 2^32s, 91 * we can treat this as if the radix point were just to the left 92 * of the sign bit (multiply by 2^32), and get 93 * 94 * -x = (2 - x) mod 2 95 * 96 * Then, ignoring the `mod 2's for convenience: 97 * 98 * x * y = xy 99 * -x * y = 2y - xy 100 * x * -y = 2x - xy 101 * -x * -y = 4 - 2x - 2y + xy 102 * 103 * For signed multiplies, we subtract (x << 32) from the partial 104 * product to fix this problem for negative multipliers (see mul.s). 105 * Because of the way the shift into the partial product is calculated 106 * (N xor V), this term is automatically removed for the multiplicand, 107 * so we don't have to adjust. 108 * 109 * But for unsigned multiplies, the high order bit wasn't a sign bit, 110 * and the correction is wrong. So for unsigned multiplies where the 111 * high order bit is one, we end up with xy - (y << 32). To fix it 112 * we add y << 32. 113 */ 114 tst %o1 115 bl,a 1f ! if %o1 < 0 (high order bit = 1), 116 add %o4, %o0, %o4 ! %o4 += %o0 (add y to upper half) 1171: rd %y, %o0 ! get lower half of product 118 retl 119 addcc %o4, %g0, %o1 ! put upper half in place and set Z for %o1==0 120 121Lmul_shortway: 122 /* 123 * Short multiply. 12 steps, followed by a final shift step. 124 * The resulting bits are off by 12 and (32-12) = 20 bit positions, 125 * but there is no problem with %o0 being negative (unlike above), 126 * and overflow is impossible (the answer is at most 24 bits long). 127 */ 128 mulscc %o4, %o1, %o4 ! 1 129 mulscc %o4, %o1, %o4 ! 2 130 mulscc %o4, %o1, %o4 ! 3 131 mulscc %o4, %o1, %o4 ! 4 132 mulscc %o4, %o1, %o4 ! 5 133 mulscc %o4, %o1, %o4 ! 6 134 mulscc %o4, %o1, %o4 ! 7 135 mulscc %o4, %o1, %o4 ! 8 136 mulscc %o4, %o1, %o4 ! 9 137 mulscc %o4, %o1, %o4 ! 10 138 mulscc %o4, %o1, %o4 ! 11 139 mulscc %o4, %o1, %o4 ! 12 140 mulscc %o4, %g0, %o4 ! final shift 141 142 /* 143 * %o4 has 20 of the bits that should be in the result; %y has 144 * the bottom 12 (as %y's top 12). That is: 145 * 146 * %o4 %y 147 * +----------------+----------------+ 148 * | -12- | -20- | -12- | -20- | 149 * +------(---------+------)---------+ 150 * -----result----- 151 * 152 * The 12 bits of %o4 left of the `result' area are all zero; 153 * in fact, all top 20 bits of %o4 are zero. 154 */ 155 156 rd %y, %o5 157 sll %o4, 12, %o0 ! shift middle bits left 12 158 srl %o5, 20, %o5 ! shift low bits right 20 159 or %o5, %o0, %o0 160 retl 161 addcc %g0, %g0, %o1 ! %o1 = zero, and set Z 162