3  * Forth Inspired Command Language - 64 bit math support routines
8  * Rev 2.03: Support for 128 bit DP math. This file really ouught to
13  * Copyright (c) 1997-2001 John Sadler (john_sadler@alum.mit.edu)
20  * if you would like to contribute to the Ficl release, please
35  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
57 	 * Once we have the quotient, it's cheaper to calculate the  in ficl2UnsignedDivide()
58 	 * remainder this way than with % (mod).  --lch  in ficl2UnsignedDivide()
60 	result.remainder  = (ficlInteger)(q - (result.quotient * y));  in ficl2UnsignedDivide()
67 #define	FICL_CELL_HIGH_BIT	((uintmax_t)1 << (FICL_BITS_PER_CELL-1))
69 #define	UMOD_MASK		((1L << (FICL_BITS_PER_CELL / 2)) - 1)
78 	return (x.high < 0);  in ficl2IntegerIsNegative()
88 	x.high = ~x.high;  in ficl2IntegerNegate()
89 	x.low = ~x.low;  in ficl2IntegerNegate()
90 	x.low ++;  in ficl2IntegerNegate()
91 	if (x.low == 0)  in ficl2IntegerNegate()
92 		x.high++;  in ficl2IntegerNegate()
101  * Mul is typically the numeric base, and add represents a digit to be
102  * appended to the growing number.
109 	ficl2Unsigned resultLo = ficl2UnsignedMultiply(u.low, mul);  in ficl2UnsignedMultiplyAccumulate()
110 	ficl2Unsigned resultHi = ficl2UnsignedMultiply(u.high, mul);  in ficl2UnsignedMultiplyAccumulate()
111 	resultLo.high += resultHi.low;  in ficl2UnsignedMultiplyAccumulate()
112 	resultHi.low = resultLo.low + add;  in ficl2UnsignedMultiplyAccumulate()
114 	if (resultHi.low < resultLo.low)  in ficl2UnsignedMultiplyAccumulate()
115 		resultLo.high++;  in ficl2UnsignedMultiplyAccumulate()
117 	resultLo.low = resultHi.low;  in ficl2UnsignedMultiplyAccumulate()
134 		sign = -sign;  in ficl2IntegerMultiply()
135 		x = -x;  in ficl2IntegerMultiply()
139 		sign = -sign;  in ficl2IntegerMultiply()
140 		y = -y;  in ficl2IntegerMultiply()
155 	if (x.low == INTMAX_MIN)  in ficl2IntegerDecrement()
156 		x.high--;  in ficl2IntegerDecrement()
157 	x.low--;  in ficl2IntegerDecrement()
167 	result.high = x.high + y.high;  in ficl2UnsignedAdd()
168 	result.low = x.low + y.low;  in ficl2UnsignedAdd()
170 	if (result.low < y.low)  in ficl2UnsignedAdd()
171 		result.high++;  in ficl2UnsignedAdd()
187 	addend.low = y;  in ficl2UnsignedMultiply()
188 	addend.high = 0; /* No sign extension--arguments are unsigned */  in ficl2UnsignedMultiply()
208 	result.high = x.high - y.high;  in ficl2UnsignedSubtract()
209 	result.low = x.low - y.low;  in ficl2UnsignedSubtract()
211 	if (x.low < y.low) {  in ficl2UnsignedSubtract()
212 		result.high--;  in ficl2UnsignedSubtract()
227 	result.high = x.high << 1;  in ficl2UnsignedArithmeticShiftLeft()
228 	if (x.low & FICL_CELL_HIGH_BIT) {  in ficl2UnsignedArithmeticShiftLeft()
229 		result.high++;  in ficl2UnsignedArithmeticShiftLeft()
232 	result.low = x.low << 1;  in ficl2UnsignedArithmeticShiftLeft()
239  * 64 bit right shift (unsigned - no sign extend)
246 	result.low = x.low >> 1;  in ficl2UnsignedArithmeticShiftRight()
247 	if (x.high & 1) {  in ficl2UnsignedArithmeticShiftRight()
248 		result.low |= FICL_CELL_HIGH_BIT;  in ficl2UnsignedArithmeticShiftRight()
251 	result.high = x.high >> 1;  in ficl2UnsignedArithmeticShiftRight()
264 	result.high = x.high | y.high;  in ficl2UnsignedOr()
265 	result.low = x.low | y.low;  in ficl2UnsignedOr()
272  * Return -1 if x < y; 0 if x==y, and 1 if x > y.
277 	if (x.high > y.high)  in ficl2UnsignedCompare()
279 	if (x.high < y.high)  in ficl2UnsignedCompare()
280 		return (-1);  in ficl2UnsignedCompare()
282 	/* High parts are equal */  in ficl2UnsignedCompare()
284 	if (x.low > y.low)  in ficl2UnsignedCompare()
286 	else if (x.low < y.low)  in ficl2UnsignedCompare()
287 		return (-1);  in ficl2UnsignedCompare()
306 	quotient.low = 0;  in ficl2UnsignedDivide()
307 	quotient.high = 0;  in ficl2UnsignedDivide()
309 	subtrahend.low = y;  in ficl2UnsignedDivide()
310 	subtrahend.high = 0;  in ficl2UnsignedDivide()
312 	mask.low = 1;  in ficl2UnsignedDivide()
313 	mask.high = 0;  in ficl2UnsignedDivide()
316 	    (subtrahend.high & FICL_CELL_HIGH_BIT) == 0) {  in ficl2UnsignedDivide()
321 	while (mask.low != 0 || mask.high != 0) {  in ficl2UnsignedDivide()
331 	result.remainder = q.low;  in ficl2UnsignedDivide()
341  * the sign of the divisor or is zero, and the quotient is rounded to
347  * Table 3.3 - Floored Division Example
349  * --------        ------- ---------       --------
351  * -10                7       4               -2
352  *  10               -7      -4               -2
353  * -10               -7      -3                1
356  * Table 3.4 - Symmetric Division Example
358  * --------        ------- ---------       --------
360  * -10                7      -3               -1
361  *  10               -7       3               -1
362  * -10               -7      -3                1
375 		signQuot = -signQuot;  in ficl2IntegerDivideFloored()
379 		den = -den;  in ficl2IntegerDivideFloored()
380 		signRem = -signRem;  in ficl2IntegerDivideFloored()
381 		signQuot = -signQuot;  in ficl2IntegerDivideFloored()
392 			qr.remainder = den - qr.remainder;  in ficl2IntegerDivideFloored()
397 		qr.remainder = -qr.remainder;  in ficl2IntegerDivideFloored()
420 		signRem  = -signRem;  in ficl2IntegerDivideSymmetric()
421 		signQuot = -signQuot;  in ficl2IntegerDivideSymmetric()
425 		den = -den;  in ficl2IntegerDivideSymmetric()
426 		signQuot = -signQuot;  in ficl2IntegerDivideSymmetric()
434 		qr.remainder = -qr.remainder;  in ficl2IntegerDivideSymmetric()