Annotation of embedaddon/php/ext/bcmath/libbcmath/src/div.c, revision 1.1.1.1
1.1 misho 1: /* div.c: bcmath library file. */
2: /*
3: Copyright (C) 1991, 1992, 1993, 1994, 1997 Free Software Foundation, Inc.
4: Copyright (C) 2000 Philip A. Nelson
5:
6: This library is free software; you can redistribute it and/or
7: modify it under the terms of the GNU Lesser General Public
8: License as published by the Free Software Foundation; either
9: version 2 of the License, or (at your option) any later version.
10:
11: This library is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14: Lesser General Public License for more details. (COPYING.LIB)
15:
16: You should have received a copy of the GNU Lesser General Public
17: License along with this library; if not, write to:
18:
19: The Free Software Foundation, Inc.
20: 59 Temple Place, Suite 330
21: Boston, MA 02111-1307 USA.
22:
23: You may contact the author by:
24: e-mail: philnelson@acm.org
25: us-mail: Philip A. Nelson
26: Computer Science Department, 9062
27: Western Washington University
28: Bellingham, WA 98226-9062
29:
30: *************************************************************************/
31:
32: #include <config.h>
33: #include <stdio.h>
34: #include <assert.h>
35: #include <stdlib.h>
36: #include <ctype.h>
37: #include <stdarg.h>
38: #include "bcmath.h"
39: #include "private.h"
40:
41:
42: /* Some utility routines for the divide: First a one digit multiply.
43: NUM (with SIZE digits) is multiplied by DIGIT and the result is
44: placed into RESULT. It is written so that NUM and RESULT can be
45: the same pointers. */
46:
47: static void
48: _one_mult (num, size, digit, result)
49: unsigned char *num;
50: int size, digit;
51: unsigned char *result;
52: {
53: int carry, value;
54: unsigned char *nptr, *rptr;
55:
56: if (digit == 0)
57: memset (result, 0, size);
58: else
59: {
60: if (digit == 1)
61: memcpy (result, num, size);
62: else
63: {
64: /* Initialize */
65: nptr = (unsigned char *) (num+size-1);
66: rptr = (unsigned char *) (result+size-1);
67: carry = 0;
68:
69: while (size-- > 0)
70: {
71: value = *nptr-- * digit + carry;
72: *rptr-- = value % BASE;
73: carry = value / BASE;
74: }
75:
76: if (carry != 0) *rptr = carry;
77: }
78: }
79: }
80:
81:
82: /* The full division routine. This computes N1 / N2. It returns
83: 0 if the division is ok and the result is in QUOT. The number of
84: digits after the decimal point is SCALE. It returns -1 if division
85: by zero is tried. The algorithm is found in Knuth Vol 2. p237. */
86:
87: int
88: bc_divide (bc_num n1, bc_num n2, bc_num *quot, int scale TSRMLS_DC)
89: {
90: bc_num qval;
91: unsigned char *num1, *num2;
92: unsigned char *ptr1, *ptr2, *n2ptr, *qptr;
93: int scale1, val;
94: unsigned int len1, len2, scale2, qdigits, extra, count;
95: unsigned int qdig, qguess, borrow, carry;
96: unsigned char *mval;
97: char zero;
98: unsigned int norm;
99:
100: /* Test for divide by zero. */
101: if (bc_is_zero (n2 TSRMLS_CC)) return -1;
102:
103: /* Test for divide by 1. If it is we must truncate. */
104: if (n2->n_scale == 0)
105: {
106: if (n2->n_len == 1 && *n2->n_value == 1)
107: {
108: qval = bc_new_num (n1->n_len, scale);
109: qval->n_sign = (n1->n_sign == n2->n_sign ? PLUS : MINUS);
110: memset (&qval->n_value[n1->n_len],0,scale);
111: memcpy (qval->n_value, n1->n_value,
112: n1->n_len + MIN(n1->n_scale,scale));
113: bc_free_num (quot);
114: *quot = qval;
115: }
116: }
117:
118: /* Set up the divide. Move the decimal point on n1 by n2's scale.
119: Remember, zeros on the end of num2 are wasted effort for dividing. */
120: scale2 = n2->n_scale;
121: n2ptr = (unsigned char *) n2->n_value+n2->n_len+scale2-1;
122: while ((scale2 > 0) && (*n2ptr-- == 0)) scale2--;
123:
124: len1 = n1->n_len + scale2;
125: scale1 = n1->n_scale - scale2;
126: if (scale1 < scale)
127: extra = scale - scale1;
128: else
129: extra = 0;
130: num1 = (unsigned char *) safe_emalloc (1, n1->n_len+n1->n_scale, extra+2);
131: if (num1 == NULL) bc_out_of_memory();
132: memset (num1, 0, n1->n_len+n1->n_scale+extra+2);
133: memcpy (num1+1, n1->n_value, n1->n_len+n1->n_scale);
134:
135: len2 = n2->n_len + scale2;
136: num2 = (unsigned char *) safe_emalloc (1, len2, 1);
137: if (num2 == NULL) bc_out_of_memory();
138: memcpy (num2, n2->n_value, len2);
139: *(num2+len2) = 0;
140: n2ptr = num2;
141: while (*n2ptr == 0)
142: {
143: n2ptr++;
144: len2--;
145: }
146:
147: /* Calculate the number of quotient digits. */
148: if (len2 > len1+scale)
149: {
150: qdigits = scale+1;
151: zero = TRUE;
152: }
153: else
154: {
155: zero = FALSE;
156: if (len2>len1)
157: qdigits = scale+1; /* One for the zero integer part. */
158: else
159: qdigits = len1-len2+scale+1;
160: }
161:
162: /* Allocate and zero the storage for the quotient. */
163: qval = bc_new_num (qdigits-scale,scale);
164: memset (qval->n_value, 0, qdigits);
165:
166: /* Allocate storage for the temporary storage mval. */
167: mval = (unsigned char *) safe_emalloc (1, len2, 1);
168: if (mval == NULL) bc_out_of_memory ();
169:
170: /* Now for the full divide algorithm. */
171: if (!zero)
172: {
173: /* Normalize */
174: norm = 10 / ((int)*n2ptr + 1);
175: if (norm != 1)
176: {
177: _one_mult (num1, len1+scale1+extra+1, norm, num1);
178: _one_mult (n2ptr, len2, norm, n2ptr);
179: }
180:
181: /* Initialize divide loop. */
182: qdig = 0;
183: if (len2 > len1)
184: qptr = (unsigned char *) qval->n_value+len2-len1;
185: else
186: qptr = (unsigned char *) qval->n_value;
187:
188: /* Loop */
189: while (qdig <= len1+scale-len2)
190: {
191: /* Calculate the quotient digit guess. */
192: if (*n2ptr == num1[qdig])
193: qguess = 9;
194: else
195: qguess = (num1[qdig]*10 + num1[qdig+1]) / *n2ptr;
196:
197: /* Test qguess. */
198: if (n2ptr[1]*qguess >
199: (num1[qdig]*10 + num1[qdig+1] - *n2ptr*qguess)*10
200: + num1[qdig+2])
201: {
202: qguess--;
203: /* And again. */
204: if (n2ptr[1]*qguess >
205: (num1[qdig]*10 + num1[qdig+1] - *n2ptr*qguess)*10
206: + num1[qdig+2])
207: qguess--;
208: }
209:
210: /* Multiply and subtract. */
211: borrow = 0;
212: if (qguess != 0)
213: {
214: *mval = 0;
215: _one_mult (n2ptr, len2, qguess, mval+1);
216: ptr1 = (unsigned char *) num1+qdig+len2;
217: ptr2 = (unsigned char *) mval+len2;
218: for (count = 0; count < len2+1; count++)
219: {
220: val = (int) *ptr1 - (int) *ptr2-- - borrow;
221: if (val < 0)
222: {
223: val += 10;
224: borrow = 1;
225: }
226: else
227: borrow = 0;
228: *ptr1-- = val;
229: }
230: }
231:
232: /* Test for negative result. */
233: if (borrow == 1)
234: {
235: qguess--;
236: ptr1 = (unsigned char *) num1+qdig+len2;
237: ptr2 = (unsigned char *) n2ptr+len2-1;
238: carry = 0;
239: for (count = 0; count < len2; count++)
240: {
241: val = (int) *ptr1 + (int) *ptr2-- + carry;
242: if (val > 9)
243: {
244: val -= 10;
245: carry = 1;
246: }
247: else
248: carry = 0;
249: *ptr1-- = val;
250: }
251: if (carry == 1) *ptr1 = (*ptr1 + 1) % 10;
252: }
253:
254: /* We now know the quotient digit. */
255: *qptr++ = qguess;
256: qdig++;
257: }
258: }
259:
260: /* Clean up and return the number. */
261: qval->n_sign = ( n1->n_sign == n2->n_sign ? PLUS : MINUS );
262: if (bc_is_zero (qval TSRMLS_CC)) qval->n_sign = PLUS;
263: _bc_rm_leading_zeros (qval);
264: bc_free_num (quot);
265: *quot = qval;
266:
267: /* Clean up temporary storage. */
268: efree (mval);
269: efree (num1);
270: efree (num2);
271:
272: return 0; /* Everything is OK. */
273: }
274:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to div.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / bcmath / libbcmath / src