afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * m a t h 6 4 . c
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Forth Inspired Command Language - 64 bit math support routines
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Authors: Michael A. Gauland (gaulandm@mdhost.cse.tek.com)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Larry Hastings (larry@hastings.org)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * John Sadler (john_sadler@alum.mit.edu)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Created: 25 January 1998
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Rev 2.03: Support for 128 bit DP math. This file really ouught to
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * be renamed!
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * $Id: double.c,v 1.2 2010/09/12 15:18:07 asau Exp $
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Copyright (c) 1997-2001 John Sadler (john_sadler@alum.mit.edu)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * All rights reserved.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Get the latest Ficl release at http://ficl.sourceforge.net
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * I am interested in hearing from anyone who uses Ficl. If you have
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * a problem, a success story, a defect, an enhancement request, or
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * if you would like to contribute to the Ficl release, please
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * contact me by email at the address above.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * L I C E N S E and D I S C L A I M E R
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Redistribution and use in source and binary forms, with or without
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * modification, are permitted provided that the following conditions
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * are met:
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * 1. Redistributions of source code must retain the above copyright
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * notice, this list of conditions and the following disclaimer.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * 2. Redistributions in binary form must reproduce the above copyright
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * notice, this list of conditions and the following disclaimer in the
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * documentation and/or other materials provided with the distribution.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * SUCH DAMAGE.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#include "ficl.h"
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#if FICL_PLATFORM_HAS_2INTEGER
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedQR
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedDivide(ficl2Unsigned q, ficlUnsigned y)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2UnsignedQR result;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.quotient = q / y;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome /*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Once we have the quotient, it's cheaper to calculate the
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * remainder this way than with % (mod). --lch
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.remainder = (ficlInteger)(q - (result.quotient * y));
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (result);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#else /* FICL_PLATFORM_HAS_2INTEGER */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#define FICL_CELL_HIGH_BIT ((uintmax_t)1 << (FICL_BITS_PER_CELL-1))
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#define UMOD_SHIFT (FICL_BITS_PER_CELL / 2)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#define UMOD_MASK ((1L << (FICL_BITS_PER_CELL / 2)) - 1)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2IntegerIsNegative
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Returns TRUE if the specified ficl2Unsigned has its sign bit set.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeint
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2IntegerIsNegative(ficl2Integer x)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (x.high < 0);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2IntegerNegate
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Negates an ficl2Unsigned by complementing and incrementing.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2Integer
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2IntegerNegate(ficl2Integer x)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome x.high = ~x.high;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome x.low = ~x.low;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome x.low ++;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (x.low == 0)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome x.high++;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (x);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2UnsignedMultiplyAccumulate
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Mixed precision multiply and accumulate primitive for number building.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Multiplies ficl2Unsigned u by ficlUnsigned mul and adds ficlUnsigned add.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Mul is typically the numeric base, and add represents a digit to be
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * appended to the growing number.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Returns the result of the operation
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2Unsigned
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedMultiplyAccumulate(ficl2Unsigned u, ficlUnsigned mul,
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficlUnsigned add)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned resultLo = ficl2UnsignedMultiply(u.low, mul);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned resultHi = ficl2UnsignedMultiply(u.high, mul);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome resultLo.high += resultHi.low;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome resultHi.low = resultLo.low + add;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (resultHi.low < resultLo.low)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome resultLo.high++;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome resultLo.low = resultHi.low;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (resultLo);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2IntegerMultiply
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Multiplies a pair of ficlIntegers and returns an ficl2Integer result.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2Integer
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2IntegerMultiply(ficlInteger x, ficlInteger y)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned prod;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Integer result;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome int sign = 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (x < 0) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome sign = -sign;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome x = -x;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (y < 0) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome sign = -sign;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome y = -y;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome prod = ficl2UnsignedMultiply(x, y);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome FICL_2INTEGER_SET(FICL_2UNSIGNED_GET_HIGH(prod),
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome FICL_2UNSIGNED_GET_LOW(prod), result);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (sign > 0)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (result);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome else
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (ficl2IntegerNegate(result));
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2Integer
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2IntegerDecrement(ficl2Integer x)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (x.low == INTMAX_MIN)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome x.high--;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome x.low--;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (x);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2Unsigned
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedAdd(ficl2Unsigned x, ficl2Unsigned y)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned result;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.high = x.high + y.high;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.low = x.low + y.low;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (result.low < y.low)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.high++;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (result);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2UnsignedMultiply
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Contributed by:
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Michael A. Gauland gaulandm@mdhost.cse.tek.com
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2Unsigned
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedMultiply(ficlUnsigned x, ficlUnsigned y)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned result = { 0, 0 };
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned addend;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome addend.low = y;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome addend.high = 0; /* No sign extension--arguments are unsigned */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome while (x != 0) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (x & 1) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result = ficl2UnsignedAdd(result, addend);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome x >>= 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome addend = ficl2UnsignedArithmeticShiftLeft(addend);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (result);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2UnsignedSubtract
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2Unsigned
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedSubtract(ficl2Unsigned x, ficl2Unsigned y)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned result;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.high = x.high - y.high;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.low = x.low - y.low;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (x.low < y.low) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.high--;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (result);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2UnsignedArithmeticShiftLeft
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * 64 bit left shift
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2Unsigned
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedArithmeticShiftLeft(ficl2Unsigned x)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned result;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.high = x.high << 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (x.low & FICL_CELL_HIGH_BIT) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.high++;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.low = x.low << 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (result);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2UnsignedArithmeticShiftRight
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * 64 bit right shift (unsigned - no sign extend)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2Unsigned
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedArithmeticShiftRight(ficl2Unsigned x)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned result;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.low = x.low >> 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (x.high & 1) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.low |= FICL_CELL_HIGH_BIT;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.high = x.high >> 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (result);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2UnsignedOr
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * 64 bit bitwise OR
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2Unsigned
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedOr(ficl2Unsigned x, ficl2Unsigned y)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned result;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.high = x.high | y.high;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.low = x.low | y.low;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (result);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2UnsignedCompare
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Return -1 if x < y; 0 if x==y, and 1 if x > y.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeint
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedCompare(ficl2Unsigned x, ficl2Unsigned y)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (x.high > y.high)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (1);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (x.high < y.high)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (-1);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome /* High parts are equal */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (x.low > y.low)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (1);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome else if (x.low < y.low)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (-1);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (0);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2UnsignedDivide
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Portable versions of ficl2Multiply and ficl2Divide in C
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Contributed by:
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Michael A. Gauland gaulandm@mdhost.cse.tek.com
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedQR
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2UnsignedDivide(ficl2Unsigned q, ficlUnsigned y)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2UnsignedQR result;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned quotient;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned subtrahend;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned mask;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome quotient.low = 0;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome quotient.high = 0;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome subtrahend.low = y;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome subtrahend.high = 0;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome mask.low = 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome mask.high = 0;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome while ((ficl2UnsignedCompare(subtrahend, q) < 0) &&
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome (subtrahend.high & FICL_CELL_HIGH_BIT) == 0) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome mask = ficl2UnsignedArithmeticShiftLeft(mask);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome subtrahend = ficl2UnsignedArithmeticShiftLeft(subtrahend);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome while (mask.low != 0 || mask.high != 0) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (ficl2UnsignedCompare(subtrahend, q) <= 0) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome q = ficl2UnsignedSubtract(q, subtrahend);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome quotient = ficl2UnsignedOr(quotient, mask);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome mask = ficl2UnsignedArithmeticShiftRight(mask);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome subtrahend = ficl2UnsignedArithmeticShiftRight(subtrahend);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.quotient = quotient;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome result.remainder = q.low;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (result);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#endif /* !FICL_PLATFORM_HAS_2INTEGER */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2IntegerDivideFloored
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * FROM THE FORTH ANS...
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Floored division is integer division in which the remainder carries
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * the sign of the divisor or is zero, and the quotient is rounded to
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * its arithmetic floor. Symmetric division is integer division in which
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * the remainder carries the sign of the dividend or is zero and the
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * quotient is the mathematical quotient rounded towards zero or
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * truncated. Examples of each are shown in tables 3.3 and 3.4.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Table 3.3 - Floored Division Example
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Dividend Divisor Remainder Quotient
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * -------- ------- --------- --------
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * 10 7 3 1
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * -10 7 4 -2
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * 10 -7 -4 -2
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * -10 -7 -3 1
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Table 3.4 - Symmetric Division Example
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Dividend Divisor Remainder Quotient
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * -------- ------- --------- --------
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * 10 7 3 1
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * -10 7 -3 -1
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * 10 -7 3 -1
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * -10 -7 -3 1
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2IntegerQR
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2IntegerDivideFloored(ficl2Integer num, ficlInteger den)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2IntegerQR qr;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2UnsignedQR uqr;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned u;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome int signRem = 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome int signQuot = 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (ficl2IntegerIsNegative(num)) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome num = ficl2IntegerNegate(num);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome signQuot = -signQuot;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (den < 0) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome den = -den;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome signRem = -signRem;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome signQuot = -signQuot;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome FICL_2UNSIGNED_SET(FICL_2UNSIGNED_GET_HIGH(num),
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome FICL_2UNSIGNED_GET_LOW(num), u);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome uqr = ficl2UnsignedDivide(u, (ficlUnsigned)den);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome qr = FICL_2UNSIGNEDQR_TO_2INTEGERQR(uqr);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (signQuot < 0) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome qr.quotient = ficl2IntegerNegate(qr.quotient);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (qr.remainder != 0) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome qr.quotient = ficl2IntegerDecrement(qr.quotient);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome qr.remainder = den - qr.remainder;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (signRem < 0)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome qr.remainder = -qr.remainder;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (qr);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * ficl2IntegerDivideSymmetric
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Divide an ficl2Unsigned by a ficlInteger and return a ficlInteger quotient
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * and a ficlInteger remainder. The absolute values of quotient and remainder
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * are not affected by the signs of the numerator and denominator
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * (the operation is symmetric on the number line)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2IntegerQR
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomeficl2IntegerDivideSymmetric(ficl2Integer num, ficlInteger den)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2IntegerQR qr;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2UnsignedQR uqr;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome ficl2Unsigned u;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome int signRem = 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome int signQuot = 1;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (ficl2IntegerIsNegative(num)) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome num = ficl2IntegerNegate(num);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome signRem = -signRem;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome signQuot = -signQuot;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (den < 0) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome den = -den;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome signQuot = -signQuot;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome FICL_2UNSIGNED_SET(FICL_2UNSIGNED_GET_HIGH(num),
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome FICL_2UNSIGNED_GET_LOW(num), u);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome uqr = ficl2UnsignedDivide(u, (ficlUnsigned)den);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome qr = FICL_2UNSIGNEDQR_TO_2INTEGERQR(uqr);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (signRem < 0)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome qr.remainder = -qr.remainder;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome if (signQuot < 0)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome qr.quotient = ficl2IntegerNegate(qr.quotient);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome return (qr);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}