| qdivrem.c (84221) | qdivrem.c (92913) |
|---|---|
| 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 * --- 24 unchanged lines hidden (view full) --- 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 * From: Id: qdivrem.c,v 1.7 1997/11/07 09:20:40 phk Exp 38 */ 39 40#include <sys/cdefs.h> | 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 * --- 24 unchanged lines hidden (view full) --- 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 * From: Id: qdivrem.c,v 1.7 1997/11/07 09:20:40 phk Exp 38 */ 39 40#include <sys/cdefs.h> |
| 41__FBSDID("$FreeBSD: head/lib/libstand/qdivrem.c 84221 2001-09-30 22:28:01Z dillon $"); | 41__FBSDID("$FreeBSD: head/lib/libstand/qdivrem.c 92913 2002-03-21 23:39:28Z obrien $"); |
| 42 43/* 44 * Multiprecision divide. This algorithm is from Knuth vol. 2 (2nd ed), 45 * section 4.3.1, pp. 257--259. 46 */ 47 48#include "quad.h" 49 --- 10 unchanged lines hidden (view full) --- 60#endif 61 62/* 63 * Shift p[0]..p[len] left `sh' bits, ignoring any bits that 64 * `fall out' the left (there never will be any such anyway). 65 * We may assume len >= 0. NOTE THAT THIS WRITES len+1 DIGITS. 66 */ 67static void | 42 43/* 44 * Multiprecision divide. This algorithm is from Knuth vol. 2 (2nd ed), 45 * section 4.3.1, pp. 257--259. 46 */ 47 48#include "quad.h" 49 --- 10 unchanged lines hidden (view full) --- 60#endif 61 62/* 63 * Shift p[0]..p[len] left `sh' bits, ignoring any bits that 64 * `fall out' the left (there never will be any such anyway). 65 * We may assume len >= 0. NOTE THAT THIS WRITES len+1 DIGITS. 66 */ 67static void |
| 68shl(register digit *p, register int len, register int sh) | 68shl(digit *p, int len, int sh) |
| 69{ | 69{ |
| 70 register int i; | 70 int i; |
| 71 72 for (i = 0; i < len; i++) 73 p[i] = LHALF(p[i] << sh) | (p[i + 1] >> (HALF_BITS - sh)); 74 p[i] = LHALF(p[i] << sh); 75} 76 77/* 78 * __qdivrem(u, v, rem) returns u/v and, optionally, sets *rem to u%v. --- 4 unchanged lines hidden (view full) --- 83 * leading zeros). 84 */ 85u_quad_t 86__qdivrem(uq, vq, arq) 87 u_quad_t uq, vq, *arq; 88{ 89 union uu tmp; 90 digit *u, *v, *q; | 71 72 for (i = 0; i < len; i++) 73 p[i] = LHALF(p[i] << sh) | (p[i + 1] >> (HALF_BITS - sh)); 74 p[i] = LHALF(p[i] << sh); 75} 76 77/* 78 * __qdivrem(u, v, rem) returns u/v and, optionally, sets *rem to u%v. --- 4 unchanged lines hidden (view full) --- 83 * leading zeros). 84 */ 85u_quad_t 86__qdivrem(uq, vq, arq) 87 u_quad_t uq, vq, *arq; 88{ 89 union uu tmp; 90 digit *u, *v, *q; |
| 91 register digit v1, v2; | 91 digit v1, v2; |
| 92 u_long qhat, rhat, t; 93 int m, n, d, j, i; 94 digit uspace[5], vspace[5], qspace[5]; 95 96 /* 97 * Take care of special cases: divide by zero, and u < v. 98 */ 99 if (vq == 0) { --- 93 unchanged lines hidden (view full) --- 193 } 194 /* 195 * D2: j = 0. 196 */ 197 j = 0; 198 v1 = v[1]; /* for D3 -- note that v[1..n] are constant */ 199 v2 = v[2]; /* for D3 */ 200 do { | 92 u_long qhat, rhat, t; 93 int m, n, d, j, i; 94 digit uspace[5], vspace[5], qspace[5]; 95 96 /* 97 * Take care of special cases: divide by zero, and u < v. 98 */ 99 if (vq == 0) { --- 93 unchanged lines hidden (view full) --- 193 } 194 /* 195 * D2: j = 0. 196 */ 197 j = 0; 198 v1 = v[1]; /* for D3 -- note that v[1..n] are constant */ 199 v2 = v[2]; /* for D3 */ 200 do { |
| 201 register digit uj0, uj1, uj2; | 201 digit uj0, uj1, uj2; |
| 202 203 /* 204 * D3: Calculate qhat (\^q, in TeX notation). 205 * Let qhat = min((u[j]*B + u[j+1])/v[1], B-1), and 206 * let rhat = (u[j]*B + u[j+1]) mod v[1]. 207 * While rhat < B and v[2]*qhat > rhat*B+u[j+2], 208 * decrement qhat and increase rhat correspondingly. 209 * Note that if rhat >= B, v[2]*qhat < rhat*B. --- 96 unchanged lines hidden --- | 202 203 /* 204 * D3: Calculate qhat (\^q, in TeX notation). 205 * Let qhat = min((u[j]*B + u[j+1])/v[1], B-1), and 206 * let rhat = (u[j]*B + u[j+1]) mod v[1]. 207 * While rhat < B and v[2]*qhat > rhat*B+u[j+2], 208 * decrement qhat and increase rhat correspondingly. 209 * Note that if rhat >= B, v[2]*qhat < rhat*B. --- 96 unchanged lines hidden --- |