| 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 | * Redistribution and use in source and binary forms, with or without␊ |
| 10 | * modification, are permitted provided that the following conditions␊ |
| 11 | * are met:␊ |
| 12 | * 1. Redistributions of source code must retain the above copyright␊ |
| 13 | * notice, this list of conditions and the following disclaimer.␊ |
| 14 | * 2. Redistributions in binary form must reproduce the above copyright␊ |
| 15 | * notice, this list of conditions and the following disclaimer in the␊ |
| 16 | * documentation and/or other materials provided with the distribution.␊ |
| 17 | * 3. All advertising materials mentioning features or use of this software␊ |
| 18 | * must display the following acknowledgement:␊ |
| 19 | *␉This product includes software developed by the University of␊ |
| 20 | *␉California, Berkeley and its contributors.␊ |
| 21 | * 4. Neither the name of the University nor the names of its contributors␊ |
| 22 | * may be used to endorse or promote products derived from this software␊ |
| 23 | * without specific prior written permission.␊ |
| 24 | *␊ |
| 25 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND␊ |
| 26 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE␊ |
| 27 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE␊ |
| 28 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE␊ |
| 29 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL␊ |
| 30 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS␊ |
| 31 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)␊ |
| 32 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT␊ |
| 33 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY␊ |
| 34 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF␊ |
| 35 | * SUCH DAMAGE.␊ |
| 36 | *␊ |
| 37 | * $FreeBSD: src/sys/libkern/qdivrem.c,v 1.8 1999/08/28 00:46:35 peter Exp $␊ |
| 38 | */␊ |
| 39 | ␊ |
| 40 | /*␊ |
| 41 | * Multiprecision divide. This algorithm is from Knuth vol. 2 (2nd ed),␊ |
| 42 | * section 4.3.1, pp. 257--259.␊ |
| 43 | */␊ |
| 44 | ␊ |
| 45 | #include "quad.h"␊ |
| 46 | ␊ |
| 47 | #define␉B␉(1 << HALF_BITS)␉/* digit base */␊ |
| 48 | ␊ |
| 49 | /* Combine two `digits' to make a single two-digit number. */␊ |
| 50 | #define␉COMBINE(a, b) (((u_long)(a) << HALF_BITS) | (b))␊ |
| 51 | ␊ |
| 52 | /* select a type for digits in base B: use unsigned short if they fit */␊ |
| 53 | #if ULONG_MAX == 0xffffffff && USHRT_MAX >= 0xffff␊ |
| 54 | typedef unsigned short digit;␊ |
| 55 | #else␊ |
| 56 | typedef u_long digit;␊ |
| 57 | #endif␊ |
| 58 | ␊ |
| 59 | /*␊ |
| 60 | * Shift p[0]..p[len] left `sh' bits, ignoring any bits that␊ |
| 61 | * `fall out' the left (there never will be any such anyway).␊ |
| 62 | * We may assume len >= 0. NOTE THAT THIS WRITES len+1 DIGITS.␊ |
| 63 | */␊ |
| 64 | static void␊ |
| 65 | shl(register digit *p, register int len, register int sh)␊ |
| 66 | {␊ |
| 67 | ␉register int i;␊ |
| 68 | ␊ |
| 69 | ␉for (i = 0; i < len; i++)␊ |
| 70 | ␉␉p[i] = LHALF(p[i] << sh) | (p[i + 1] >> (HALF_BITS - sh));␊ |
| 71 | ␉p[i] = LHALF(p[i] << sh);␊ |
| 72 | }␊ |
| 73 | ␊ |
| 74 | /*␊ |
| 75 | * __qdivrem(u, v, rem) returns u/v and, optionally, sets *rem to u%v.␊ |
| 76 | *␊ |
| 77 | * We do this in base 2-sup-HALF_BITS, so that all intermediate products␊ |
| 78 | * fit within u_long. As a consequence, the maximum length dividend and␊ |
| 79 | * divisor are 4 `digits' in this base (they are shorter if they have␊ |
| 80 | * leading zeros).␊ |
| 81 | */␊ |
| 82 | u_quad_t␊ |
| 83 | __qdivrem(uq, vq, arq)␊ |
| 84 | u_quad_t uq, vq, *arq;␊ |
| 85 | {␊ |
| 86 | ␉union uu tmp;␊ |
| 87 | ␉digit *u, *v, *q;␊ |
| 88 | ␉register digit v1, v2;␊ |
| 89 | ␉u_long qhat, rhat, t;␊ |
| 90 | ␉int m, n, d, j, i;␊ |
| 91 | ␉digit uspace[5], vspace[5], qspace[5];␊ |
| 92 | ␊ |
| 93 | ␉/*␊ |
| 94 | ␉ * Take care of special cases: divide by zero, and u < v.␊ |
| 95 | ␉ */␊ |
| 96 | ␉if (vq == 0) {␊ |
| 97 | ␉␉/* divide by zero. */␊ |
| 98 | ␉␉static volatile const unsigned int zero = 0;␊ |
| 99 | ␊ |
| 100 | ␉␉tmp.ul[Hi] = tmp.ul[Lo] = 1 / zero;␊ |
| 101 | ␉␉if (arq)␊ |
| 102 | ␉␉␉*arq = uq;␊ |
| 103 | ␉␉return (tmp.q);␊ |
| 104 | ␉}␊ |
| 105 | ␉if (uq < vq) {␊ |
| 106 | ␉␉if (arq)␊ |
| 107 | ␉␉␉*arq = uq;␊ |
| 108 | ␉␉return (0);␊ |
| 109 | ␉}␊ |
| 110 | ␉u = &uspace[0];␊ |
| 111 | ␉v = &vspace[0];␊ |
| 112 | ␉q = &qspace[0];␊ |
| 113 | ␊ |
| 114 | ␉/*␊ |
| 115 | ␉ * Break dividend and divisor into digits in base B, then␊ |
| 116 | ␉ * count leading zeros to determine m and n. When done, we␊ |
| 117 | ␉ * will have:␊ |
| 118 | ␉ *␉u = (u[1]u[2]...u[m+n]) sub B␊ |
| 119 | ␉ *␉v = (v[1]v[2]...v[n]) sub B␊ |
| 120 | ␉ *␉v[1] != 0␊ |
| 121 | ␉ *␉1 < n <= 4 (if n = 1, we use a different division algorithm)␊ |
| 122 | ␉ *␉m >= 0 (otherwise u < v, which we already checked)␊ |
| 123 | ␉ *␉m + n = 4␊ |
| 124 | ␉ * and thus␊ |
| 125 | ␉ *␉m = 4 - n <= 2␊ |
| 126 | ␉ */␊ |
| 127 | ␉tmp.uq = uq;␊ |
| 128 | ␉u[0] = 0;␊ |
| 129 | ␉u[1] = HHALF(tmp.ul[Hi]);␊ |
| 130 | ␉u[2] = LHALF(tmp.ul[Hi]);␊ |
| 131 | ␉u[3] = HHALF(tmp.ul[Lo]);␊ |
| 132 | ␉u[4] = LHALF(tmp.ul[Lo]);␊ |
| 133 | ␉tmp.uq = vq;␊ |
| 134 | ␉v[1] = HHALF(tmp.ul[Hi]);␊ |
| 135 | ␉v[2] = LHALF(tmp.ul[Hi]);␊ |
| 136 | ␉v[3] = HHALF(tmp.ul[Lo]);␊ |
| 137 | ␉v[4] = LHALF(tmp.ul[Lo]);␊ |
| 138 | ␉for (n = 4; v[1] == 0; v++) {␊ |
| 139 | ␉␉if (--n == 1) {␊ |
| 140 | ␉␉␉u_long rbj;␉/* r*B+u[j] (not root boy jim) */␊ |
| 141 | ␉␉␉digit q1, q2, q3, q4;␊ |
| 142 | ␊ |
| 143 | ␉␉␉/*␊ |
| 144 | ␉␉␉ * Change of plan, per exercise 16.␊ |
| 145 | ␉␉␉ *␉r = 0;␊ |
| 146 | ␉␉␉ *␉for j = 1..4:␊ |
| 147 | ␉␉␉ *␉␉q[j] = floor((r*B + u[j]) / v),␊ |
| 148 | ␉␉␉ *␉␉r = (r*B + u[j]) % v;␊ |
| 149 | ␉␉␉ * We unroll this completely here.␊ |
| 150 | ␉␉␉ */␊ |
| 151 | ␉␉␉t = v[2];␉/* nonzero, by definition */␊ |
| 152 | ␉␉␉q1 = u[1] / t;␊ |
| 153 | ␉␉␉rbj = COMBINE(u[1] % t, u[2]);␊ |
| 154 | ␉␉␉q2 = rbj / t;␊ |
| 155 | ␉␉␉rbj = COMBINE(rbj % t, u[3]);␊ |
| 156 | ␉␉␉q3 = rbj / t;␊ |
| 157 | ␉␉␉rbj = COMBINE(rbj % t, u[4]);␊ |
| 158 | ␉␉␉q4 = rbj / t;␊ |
| 159 | ␉␉␉if (arq)␊ |
| 160 | ␉␉␉␉*arq = rbj % t;␊ |
| 161 | ␉␉␉tmp.ul[Hi] = COMBINE(q1, q2);␊ |
| 162 | ␉␉␉tmp.ul[Lo] = COMBINE(q3, q4);␊ |
| 163 | ␉␉␉return (tmp.q);␊ |
| 164 | ␉␉}␊ |
| 165 | ␉}␊ |
| 166 | ␊ |
| 167 | ␉/*␊ |
| 168 | ␉ * By adjusting q once we determine m, we can guarantee that␊ |
| 169 | ␉ * there is a complete four-digit quotient at &qspace[1] when␊ |
| 170 | ␉ * we finally stop.␊ |
| 171 | ␉ */␊ |
| 172 | ␉for (m = 4 - n; u[1] == 0; u++)␊ |
| 173 | ␉␉m--;␊ |
| 174 | ␉for (i = 4 - m; --i >= 0;)␊ |
| 175 | ␉␉q[i] = 0;␊ |
| 176 | ␉q += 4 - m;␊ |
| 177 | ␊ |
| 178 | ␉/*␊ |
| 179 | ␉ * Here we run Program D, translated from MIX to C and acquiring␊ |
| 180 | ␉ * a few minor changes.␊ |
| 181 | ␉ *␊ |
| 182 | ␉ * D1: choose multiplier 1 << d to ensure v[1] >= B/2.␊ |
| 183 | ␉ */␊ |
| 184 | ␉d = 0;␊ |
| 185 | ␉for (t = v[1]; t < B / 2; t <<= 1)␊ |
| 186 | ␉␉d++;␊ |
| 187 | ␉if (d > 0) {␊ |
| 188 | ␉␉shl(&u[0], m + n, d);␉␉/* u <<= d */␊ |
| 189 | ␉␉shl(&v[1], n - 1, d);␉␉/* v <<= d */␊ |
| 190 | ␉}␊ |
| 191 | ␉/*␊ |
| 192 | ␉ * D2: j = 0.␊ |
| 193 | ␉ */␊ |
| 194 | ␉j = 0;␊ |
| 195 | ␉v1 = v[1];␉/* for D3 -- note that v[1..n] are constant */␊ |
| 196 | ␉v2 = v[2];␉/* for D3 */␊ |
| 197 | ␉do {␊ |
| 198 | ␉␉register digit uj0, uj1, uj2;␊ |
| 199 | ␊ |
| 200 | ␉␉/*␊ |
| 201 | ␉␉ * D3: Calculate qhat (\^q, in TeX notation).␊ |
| 202 | ␉␉ * Let qhat = min((u[j]*B + u[j+1])/v[1], B-1), and␊ |
| 203 | ␉␉ * let rhat = (u[j]*B + u[j+1]) mod v[1].␊ |
| 204 | ␉␉ * While rhat < B and v[2]*qhat > rhat*B+u[j+2],␊ |
| 205 | ␉␉ * decrement qhat and increase rhat correspondingly.␊ |
| 206 | ␉␉ * Note that if rhat >= B, v[2]*qhat < rhat*B.␊ |
| 207 | ␉␉ */␊ |
| 208 | ␉␉uj0 = u[j + 0];␉/* for D3 only -- note that u[j+...] change */␊ |
| 209 | ␉␉uj1 = u[j + 1];␉/* for D3 only */␊ |
| 210 | ␉␉uj2 = u[j + 2];␉/* for D3 only */␊ |
| 211 | ␉␉if (uj0 == v1) {␊ |
| 212 | ␉␉␉qhat = B;␊ |
| 213 | ␉␉␉rhat = uj1;␊ |
| 214 | ␉␉␉goto qhat_too_big;␊ |
| 215 | ␉␉} else {␊ |
| 216 | ␉␉␉u_long nn = COMBINE(uj0, uj1);␊ |
| 217 | ␉␉␉qhat = nn / v1;␊ |
| 218 | ␉␉␉rhat = nn % v1;␊ |
| 219 | ␉␉}␊ |
| 220 | ␉␉while (v2 * qhat > COMBINE(rhat, uj2)) {␊ |
| 221 | qhat_too_big:␊ |
| 222 | ␉␉␉qhat--;␊ |
| 223 | ␉␉␉if ((rhat += v1) >= B)␊ |
| 224 | ␉␉␉␉break;␊ |
| 225 | ␉␉}␊ |
| 226 | ␉␉/*␊ |
| 227 | ␉␉ * D4: Multiply and subtract.␊ |
| 228 | ␉␉ * The variable `t' holds any borrows across the loop.␊ |
| 229 | ␉␉ * We split this up so that we do not require v[0] = 0,␊ |
| 230 | ␉␉ * and to eliminate a final special case.␊ |
| 231 | ␉␉ */␊ |
| 232 | ␉␉for (t = 0, i = n; i > 0; i--) {␊ |
| 233 | ␉␉␉t = u[i + j] - v[i] * qhat - t;␊ |
| 234 | ␉␉␉u[i + j] = LHALF(t);␊ |
| 235 | ␉␉␉t = (B - HHALF(t)) & (B - 1);␊ |
| 236 | ␉␉}␊ |
| 237 | ␉␉t = u[j] - t;␊ |
| 238 | ␉␉u[j] = LHALF(t);␊ |
| 239 | ␉␉/*␊ |
| 240 | ␉␉ * D5: test remainder.␊ |
| 241 | ␉␉ * There is a borrow if and only if HHALF(t) is nonzero;␊ |
| 242 | ␉␉ * in that (rare) case, qhat was too large (by exactly 1).␊ |
| 243 | ␉␉ * Fix it by adding v[1..n] to u[j..j+n].␊ |
| 244 | ␉␉ */␊ |
| 245 | ␉␉if (HHALF(t)) {␊ |
| 246 | ␉␉␉qhat--;␊ |
| 247 | ␉␉␉for (t = 0, i = n; i > 0; i--) { /* D6: add back. */␊ |
| 248 | ␉␉␉␉t += u[i + j] + v[i];␊ |
| 249 | ␉␉␉␉u[i + j] = LHALF(t);␊ |
| 250 | ␉␉␉␉t = HHALF(t);␊ |
| 251 | ␉␉␉}␊ |
| 252 | ␉␉␉u[j] = LHALF(u[j] + t);␊ |
| 253 | ␉␉}␊ |
| 254 | ␉␉q[j] = qhat;␊ |
| 255 | ␉} while (++j <= m);␉␉/* D7: loop on j. */␊ |
| 256 | ␊ |
| 257 | ␉/*␊ |
| 258 | ␉ * If caller wants the remainder, we have to calculate it as␊ |
| 259 | ␉ * u[m..m+n] >> d (this is at most n digits and thus fits in␊ |
| 260 | ␉ * u[m+1..m+n], but we may need more source digits).␊ |
| 261 | ␉ */␊ |
| 262 | ␉if (arq) {␊ |
| 263 | ␉␉if (d) {␊ |
| 264 | ␉␉␉for (i = m + n; i > m; --i)␊ |
| 265 | ␉␉␉␉u[i] = (u[i] >> d) |␊ |
| 266 | LHALF(u[i - 1] << (HALF_BITS - d));␊ |
| 267 | ␉␉␉u[i] = 0;␊ |
| 268 | ␉␉}␊ |
| 269 | ␉␉tmp.ul[Hi] = COMBINE(uspace[1], uspace[2]);␊ |
| 270 | ␉␉tmp.ul[Lo] = COMBINE(uspace[3], uspace[4]);␊ |
| 271 | ␉␉*arq = tmp.q;␊ |
| 272 | ␉}␊ |
| 273 | ␊ |
| 274 | ␉tmp.ul[Hi] = COMBINE(qspace[1], qspace[2]);␊ |
| 275 | ␉tmp.ul[Lo] = COMBINE(qspace[3], qspace[4]);␊ |
| 276 | ␉return (tmp.q);␊ |
| 277 | } |
