/*
 * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.
 * Copyright (C) 2017-2023 MicroEJ Corp. - EDC compliance and optimizations.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package java.time;

/**
 * A class used to represent multiprecision integers that makes efficient
 * use of allocated space by allowing a number to occupy only part of
 * an array so that the arrays do not have to be reallocated as often.
 * When performing an operation with many iterations the array used to
 * hold a number is only reallocated when necessary and does not have to
 * be the same size as the number it represents. A mutable number allows
 * calculations to occur on the same number without having to create
 * a new number for every step of the calculation as occurs with
 * BigIntegers.
 *
 * @see     BigInteger
 * @author  Michael McCloskey
 * @author  Timothy Buktu
 * @since   1.3
 */

import static java.time.BigInteger.LONG_MASK;

import java.util.Arrays;

import ej.annotation.Nullable;

class MutableBigInteger {
	/**
	 * Holds the magnitude of this MutableBigInteger in big endian order. The magnitude may start at an offset into the
	 * value array, and it may end before the length of the value array.
	 */
	int[] value;

	/**
	 * The number of ints of the value array that are currently used to hold the magnitude of this MutableBigInteger.
	 * The magnitude starts at an offset and offset + intLen may be less than value.length.
	 */
	int intLen;

	/**
	 * The offset into the value array where the magnitude of this MutableBigInteger begins.
	 */
	int offset = 0;

	
	// Constructors

	/**
	 * The default constructor. An empty MutableBigInteger is created with a one word capacity.
	 */
	MutableBigInteger() {
		this.value = new int[1];
		this.intLen = 0;
	}

	/**
	 * Construct a new MutableBigInteger with a magnitude specified by the int val.
	 */
	MutableBigInteger(int val) {
		this.value = new int[1];
		this.intLen = 1;
		this.value[0] = val;
	}

	/**
	 * Construct a new MutableBigInteger with the specified value array up to the length of the array supplied.
	 */
	MutableBigInteger(int[] val) {
		this.value = val;
		this.intLen = val.length;
	}


	/**
	 * Construct a new MutableBigInteger with a magnitude equal to the specified MutableBigInteger.
	 */
	MutableBigInteger(MutableBigInteger val) {
		this.intLen = val.intLen;
		this.value = Arrays.copyOfRange(val.value, val.offset, val.offset + this.intLen);
	}


	/**
	 * Internal helper method to return the magnitude array. The caller is not supposed to modify the returned array.
	 */
	private int[] getMagnitudeArray() {
		if (this.offset > 0 || this.value.length != this.intLen) {
			return Arrays.copyOfRange(this.value, this.offset, this.offset + this.intLen);
		}
		return this.value;
	}


	/**
	 * Convert this MutableBigInteger to a BigInteger object.
	 */
	BigInteger toBigInteger(int sign) {
		if (this.intLen == 0 || sign == 0) {
			return BigInteger.ZERO;
		}
		return new BigInteger(getMagnitudeArray(), sign);
	}


	/**
	 * Clear out a MutableBigInteger for reuse.
	 */
	void clear() {
		this.offset = this.intLen = 0;
		for (int index = 0, n = this.value.length; index < n; index++) {
			this.value[index] = 0;
		}
	}

	/**
	 * Set a MutableBigInteger to zero, removing its offset.
	 */
	void reset() {
		this.offset = this.intLen = 0;
	}

	/**
	 * Compare the magnitude of two MutableBigIntegers. Returns -1, 0 or 1 as this MutableBigInteger is numerically less
	 * than, equal to, or greater than <tt>b</tt>.
	 */
	final int compare(MutableBigInteger b) {
		int blen = b.intLen;
		if (this.intLen < blen) {
			return -1;
		}
		if (this.intLen > blen) {
			return 1;
		}

		// Add Integer.MIN_VALUE to make the comparison act as unsigned integer
		// comparison.
		int[] bval = b.value;
		for (int i = this.offset, j = b.offset; i < this.intLen + this.offset; i++, j++) {
			int b1 = this.value[i] + 0x80000000;
			int b2 = bval[j] + 0x80000000;
			if (b1 < b2) {
				return -1;
			}
			if (b1 > b2) {
				return 1;
			}
		}
		return 0;
	}


	/**
	 * Ensure that the MutableBigInteger is in normal form, specifically making sure that there are no leading zeros,
	 * and that if the magnitude is zero, then intLen is zero.
	 */
	final void normalize() {
		if (this.intLen == 0) {
			this.offset = 0;
			return;
		}

		int index = this.offset;
		if (this.value[index] != 0) {
			return;
		}

		int indexBound = index + this.intLen;
		do {
			index++;
		} while (index < indexBound && this.value[index] == 0);

		int numZeros = index - this.offset;
		this.intLen -= numZeros;
		this.offset = (this.intLen == 0 ? 0 : this.offset + numZeros);
	}

	/**
	 * Sets this MutableBigInteger's value array to the specified array. The intLen is set to the specified length.
	 */
	void setValue(int[] val, int length) {
		this.value = val;
		this.intLen = length;
		this.offset = 0;
	}


	/**
	 * Right shift this MutableBigInteger n bits. The MutableBigInteger is left in normal form.
	 */
	void rightShift(int n) {
		if (this.intLen == 0) {
			return;
		}
		int nInts = n >>> 5;
		int nBits = n & 0x1F;
		this.intLen -= nInts;
		if (nBits == 0) {
			return;
		}
		int bitsInHighWord = BigInteger.bitLengthForInt(this.value[this.offset]);
		if (nBits >= bitsInHighWord) {
			this.primitiveLeftShift(32 - nBits);
			this.intLen--;
		} else {
			primitiveRightShift(nBits);
		}
	}

	/**
	 * Left shift this MutableBigInteger n bits.
	 */
	void leftShift(int n) {
		/*
		 * If there is enough storage space in this MutableBigInteger already the available space will be used. Space to
		 * the right of the used ints in the value array is faster to utilize, so the extra space will be taken from the
		 * right if possible.
		 */
		if (this.intLen == 0) {
			return;
		}
		int nInts = n >>> 5;
		int nBits = n & 0x1F;
		int bitsInHighWord = BigInteger.bitLengthForInt(this.value[this.offset]);

		// If shift can be done without moving words, do so
		if (n <= (32 - bitsInHighWord)) {
			primitiveLeftShift(nBits);
			return;
		}

		int newLen = this.intLen + nInts + 1;
		if (nBits <= (32 - bitsInHighWord)) {
			newLen--;
		}
		if (this.value.length < newLen) {
			// The array must grow
			int[] result = new int[newLen];
			for (int i = 0; i < this.intLen; i++) {
				result[i] = this.value[this.offset + i];
			}
			setValue(result, newLen);
		} else if (this.value.length - this.offset >= newLen) {
			// Use space on right
			for (int i = 0; i < newLen - this.intLen; i++) {
				this.value[this.offset + this.intLen + i] = 0;
			}
		} else {
			// Must use space on left
			for (int i = 0; i < this.intLen; i++) {
				this.value[i] = this.value[this.offset + i];
			}
			for (int i = this.intLen; i < newLen; i++) {
				this.value[i] = 0;
			}
			this.offset = 0;
		}
		this.intLen = newLen;
		if (nBits == 0) {
			return;
		}
		if (nBits <= (32 - bitsInHighWord)) {
			primitiveLeftShift(nBits);
		} else {
			primitiveRightShift(32 - nBits);
		}
	}

	/**
	 * A primitive used for division. This method adds in one multiple of the divisor a back to the dividend result at a
	 * specified offset. It is used when qhat was estimated too large, and must be adjusted.
	 */
	private int divadd(int[] a, int[] result, int offset) {
		long carry = 0;

		for (int j = a.length - 1; j >= 0; j--) {
			long sum = (a[j] & LONG_MASK) + (result[j + offset] & LONG_MASK) + carry;
			result[j + offset] = (int) sum;
			carry = sum >>> 32;
		}
		return (int) carry;
	}

	/**
	 * This method is used for division. It multiplies an n word input a by one word input x, and subtracts the n word
	 * product from q. This is needed when subtracting qhat*divisor from dividend.
	 */
	private int mulsub(int[] q, int[] a, int x, int len, int offset) {
		long xLong = x & LONG_MASK;
		long carry = 0;
		offset += len;

		for (int j = len - 1; j >= 0; j--) {
			long product = (a[j] & LONG_MASK) * xLong + carry;
			long difference = q[offset] - product;
			q[offset--] = (int) difference;
			carry = (product >>> 32) + (((difference & LONG_MASK) > (((~(int) product) & LONG_MASK))) ? 1 : 0);
		}
		return (int) carry;
	}

	/**
	 * The method is the same as mulsun, except the fact that q array is not updated, the only result of the method is
	 * borrow flag.
	 */
	private int mulsubBorrow(int[] q, int[] a, int x, int len, int offset) {
		long xLong = x & LONG_MASK;
		long carry = 0;
		offset += len;
		for (int j = len - 1; j >= 0; j--) {
			long product = (a[j] & LONG_MASK) * xLong + carry;
			long difference = q[offset--] - product;
			carry = (product >>> 32) + (((difference & LONG_MASK) > (((~(int) product) & LONG_MASK))) ? 1 : 0);
		}
		return (int) carry;
	}

	/**
	 * Right shift this MutableBigInteger n bits, where n is less than 32. Assumes that intLen > 0, n > 0 for speed
	 */
	private final void primitiveRightShift(int n) {
		int[] val = this.value;
		int n2 = 32 - n;
		for (int i = this.offset + this.intLen - 1, c = val[i]; i > this.offset; i--) {
			int b = c;
			c = val[i - 1];
			val[i] = (c << n2) | (b >>> n);
		}
		val[this.offset] >>>= n;
	}

	/**
	 * Left shift this MutableBigInteger n bits, where n is less than 32. Assumes that intLen > 0, n > 0 for speed
	 */
	private final void primitiveLeftShift(int n) {
		int[] val = this.value;
		int n2 = 32 - n;
		for (int i = this.offset, c = val[i], m = i + this.intLen - 1; i < m; i++) {
			int b = c;
			c = val[i + 1];
			val[i] = (b << n) | (c >>> n2);
		}
		val[this.offset + this.intLen - 1] <<= n;
	}


	/**
	 * Subtracts the smaller of this and b from the larger and places the result into this MutableBigInteger.
	 */
	int subtract(MutableBigInteger b) {
		MutableBigInteger a = this;

		int[] result = this.value;
		int sign = a.compare(b);

		if (sign == 0) {
			reset();
			return 0;
		}
		if (sign < 0) {
			MutableBigInteger tmp = a;
			a = b;
			b = tmp;
		}

		int resultLen = a.intLen;
		if (result.length < resultLen) {
			result = new int[resultLen];
		}

		long diff = 0;
		int x = a.intLen;
		int y = b.intLen;
		int rstart = result.length - 1;

		// Subtract common parts of both numbers
		while (y > 0) {
			x--;
			y--;

			diff = (a.value[x + a.offset] & LONG_MASK) - (b.value[y + b.offset] & LONG_MASK) - ((int) -(diff >> 32));
			result[rstart--] = (int) diff;
		}
		// Subtract remainder of longer number
		while (x > 0) {
			x--;
			diff = (a.value[x + a.offset] & LONG_MASK) - ((int) -(diff >> 32));
			result[rstart--] = (int) diff;
		}

		this.value = result;
		this.intLen = resultLen;
		this.offset = this.value.length - resultLen;
		normalize();
		return sign;
	}

	/**
	 * This method is used for division of an n word dividend by a one word divisor. The quotient is placed into
	 * quotient. The one word divisor is specified by divisor.
	 *
	 * @return the remainder of the division is returned.
	 *
	 */
	int divideOneWord(int divisor, MutableBigInteger quotient) {
		long divisorLong = divisor & LONG_MASK;

		// Special case of one word dividend
		if (this.intLen == 1) {
			long dividendValue = this.value[this.offset] & LONG_MASK;
			int q = (int) (dividendValue / divisorLong);
			int r = (int) (dividendValue - q * divisorLong);
			quotient.value[0] = q;
			quotient.intLen = (q == 0) ? 0 : 1;
			quotient.offset = 0;
			return r;
		}

		if (quotient.value.length < this.intLen) {
			quotient.value = new int[this.intLen];
		}
		quotient.offset = 0;
		quotient.intLen = this.intLen;

		// Normalize the divisor
		int shift = IntegerHelper.numberOfLeadingZeros(divisor);

		int rem = this.value[this.offset];
		long remLong = rem & LONG_MASK;
		if (remLong < divisorLong) {
			quotient.value[0] = 0;
		} else {
			quotient.value[0] = (int) (remLong / divisorLong);
			rem = (int) (remLong - (quotient.value[0] * divisorLong));
			remLong = rem & LONG_MASK;
		}
		int xlen = this.intLen;
		while (--xlen > 0) {
			long dividendEstimate = (remLong << 32) | (this.value[this.offset + this.intLen - xlen] & LONG_MASK);
			int q;
			if (dividendEstimate >= 0) {
				q = (int) (dividendEstimate / divisorLong);
				rem = (int) (dividendEstimate - q * divisorLong);
			} else {
				long tmp = divWord(dividendEstimate, divisor);
				q = (int) (tmp & LONG_MASK);
				rem = (int) (tmp >>> 32);
			}
			quotient.value[this.intLen - xlen] = q;
			remLong = rem & LONG_MASK;
		}

		quotient.normalize();
		// Unnormalize
		if (shift > 0) {
			return rem % divisor;
		} else {
			return rem;
		}
	}


	/**
	 * @see #divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
	 */
	MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient) {
		MutableBigInteger remainder = divideKnuth(b, quotient, true);
		assert remainder != null;// this cannot be null because needRemainder is "true"
		return remainder;
	}

	/**
	 * Calculates the quotient of this div b and places the quotient in the provided MutableBigInteger objects and the
	 * remainder object is returned.
	 *
	 * Uses Algorithm D in Knuth section 4.3.1. Many optimizations to that algorithm have been adapted from the Colin
	 * Plumb C library. It special cases one word divisors for speed. The content of b is not changed.
	 *
	 */
	@Nullable
	MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder) {
		if (b.intLen == 0) {
			throw new ArithmeticException("BigInteger divide by zero");
		}

		// Dividend is zero
		if (this.intLen == 0) {
			quotient.intLen = quotient.offset = 0;
			return needRemainder ? new MutableBigInteger() : null;
		}

		int cmp = compare(b);
		// Dividend less than divisor
		if (cmp < 0) {
			quotient.intLen = quotient.offset = 0;
			return needRemainder ? new MutableBigInteger(this) : null;
		}
		// Dividend equal to divisor
		if (cmp == 0) {
			quotient.value[0] = quotient.intLen = 1;
			quotient.offset = 0;
			return needRemainder ? new MutableBigInteger() : null;
		}

		quotient.clear();
		// Special case one word divisor
		if (b.intLen == 1) {
			int r = divideOneWord(b.value[b.offset], quotient);
			if (needRemainder) {
				if (r == 0) {
					return new MutableBigInteger();
				}
				return new MutableBigInteger(r);
			} else {
				return null;
			}
		}

		return divideMagnitude(b, quotient, needRemainder);
	}


	private static void copyAndShift(int[] src, int srcFrom, int srcLen, int[] dst, int dstFrom, int shift) {
		int n2 = 32 - shift;
		int c = src[srcFrom];
		for (int i = 0; i < srcLen - 1; i++) {
			int b = c;
			c = src[++srcFrom];
			dst[dstFrom + i] = (b << shift) | (c >>> n2);
		}
		dst[dstFrom + srcLen - 1] = c << shift;
	}

	/**
	 * Divide this MutableBigInteger by the divisor. The quotient will be placed into the provided quotient object & the
	 * remainder object is returned.
	 */
	@Nullable
	private MutableBigInteger divideMagnitude(MutableBigInteger div, MutableBigInteger quotient,
			boolean needRemainder) {
		// assert div.intLen > 1
		// D1 normalize the divisor
		int shift = IntegerHelper.numberOfLeadingZeros(div.value[div.offset]);
		// Copy divisor value to protect divisor
		final int dlen = div.intLen;
		int[] divisor;
		MutableBigInteger rem; // Remainder starts as dividend with space for a leading zero
		if (shift > 0) {
			divisor = new int[dlen];
			copyAndShift(div.value, div.offset, dlen, divisor, 0, shift);
			if (IntegerHelper.numberOfLeadingZeros(this.value[this.offset]) >= shift) {
				int[] remarr = new int[this.intLen + 1];
				rem = new MutableBigInteger(remarr);
				rem.intLen = this.intLen;
				rem.offset = 1;
				copyAndShift(this.value, this.offset, this.intLen, remarr, 1, shift);
			} else {
				int[] remarr = new int[this.intLen + 2];
				rem = new MutableBigInteger(remarr);
				rem.intLen = this.intLen + 1;
				rem.offset = 1;
				int rFrom = this.offset;
				int c = 0;
				int n2 = 32 - shift;
				for (int i = 1; i < this.intLen + 1; i++, rFrom++) {
					int b = c;
					c = this.value[rFrom];
					remarr[i] = (b << shift) | (c >>> n2);
				}
				remarr[this.intLen + 1] = c << shift;
			}
		} else {
			divisor = Arrays.copyOfRange(div.value, div.offset, div.offset + div.intLen);
			rem = new MutableBigInteger(new int[this.intLen + 1]);
			System.arraycopy(this.value, this.offset, rem.value, 1, this.intLen);
			rem.intLen = this.intLen;
			rem.offset = 1;
		}

		int nlen = rem.intLen;

		// Set the quotient size
		final int limit = nlen - dlen + 1;
		if (quotient.value.length < limit) {
			quotient.value = new int[limit];
			quotient.offset = 0;
		}
		quotient.intLen = limit;
		int[] q = quotient.value;

		// Must insert leading 0 in rem if its length did not change
		if (rem.intLen == nlen) {
			rem.offset = 0;
			rem.value[0] = 0;
			rem.intLen++;
		}

		int dh = divisor[0];
		long dhLong = dh & LONG_MASK;
		int dl = divisor[1];

		// D2 Initialize j
		for (int j = 0; j < limit - 1; j++) {
			// D3 Calculate qhat
			// estimate qhat
			int qhat = 0;
			int qrem = 0;
			boolean skipCorrection = false;
			int nh = rem.value[j + rem.offset];
			int nh2 = nh + 0x80000000;
			int nm = rem.value[j + 1 + rem.offset];

			if (nh == dh) {
				qhat = ~0;
				qrem = nh + nm;
				skipCorrection = qrem + 0x80000000 < nh2;
			} else {
				long nChunk = (((long) nh) << 32) | (nm & LONG_MASK);
				if (nChunk >= 0) {
					qhat = (int) (nChunk / dhLong);
					qrem = (int) (nChunk - (qhat * dhLong));
				} else {
					long tmp = divWord(nChunk, dh);
					qhat = (int) (tmp & LONG_MASK);
					qrem = (int) (tmp >>> 32);
				}
			}

			if (qhat == 0) {
				continue;
			}

			if (!skipCorrection) { // Correct qhat
				long nl = rem.value[j + 2 + rem.offset] & LONG_MASK;
				long rs = ((qrem & LONG_MASK) << 32) | nl;
				long estProduct = (dl & LONG_MASK) * (qhat & LONG_MASK);

				if (unsignedLongCompare(estProduct, rs)) {
					qhat--;
					qrem = (int) ((qrem & LONG_MASK) + dhLong);
					if ((qrem & LONG_MASK) >= dhLong) {
						estProduct -= (dl & LONG_MASK);
						rs = ((qrem & LONG_MASK) << 32) | nl;
						if (unsignedLongCompare(estProduct, rs)) {
							qhat--;
						}
					}
				}
			}

			// D4 Multiply and subtract
			rem.value[j + rem.offset] = 0;
			int borrow = mulsub(rem.value, divisor, qhat, dlen, j + rem.offset);

			// D5 Test remainder
			if (borrow + 0x80000000 > nh2) {
				// D6 Add back
				divadd(divisor, rem.value, j + 1 + rem.offset);
				qhat--;
			}

			// Store the quotient digit
			q[j] = qhat;
		} // D7 loop on j
			// D3 Calculate qhat
			// estimate qhat
		int qhat = 0;
		int qrem = 0;
		boolean skipCorrection = false;
		int nh = rem.value[limit - 1 + rem.offset];
		int nh2 = nh + 0x80000000;
		int nm = rem.value[limit + rem.offset];

		if (nh == dh) {
			qhat = ~0;
			qrem = nh + nm;
			skipCorrection = qrem + 0x80000000 < nh2;
		} else {
			long nChunk = (((long) nh) << 32) | (nm & LONG_MASK);
			if (nChunk >= 0) {
				qhat = (int) (nChunk / dhLong);
				qrem = (int) (nChunk - (qhat * dhLong));
			} else {
				long tmp = divWord(nChunk, dh);
				qhat = (int) (tmp & LONG_MASK);
				qrem = (int) (tmp >>> 32);
			}
		}
		if (qhat != 0) {
			if (!skipCorrection) { // Correct qhat
				long nl = rem.value[limit + 1 + rem.offset] & LONG_MASK;
				long rs = ((qrem & LONG_MASK) << 32) | nl;
				long estProduct = (dl & LONG_MASK) * (qhat & LONG_MASK);

				if (unsignedLongCompare(estProduct, rs)) {
					qhat--;
					qrem = (int) ((qrem & LONG_MASK) + dhLong);
					if ((qrem & LONG_MASK) >= dhLong) {
						estProduct -= (dl & LONG_MASK);
						rs = ((qrem & LONG_MASK) << 32) | nl;
						if (unsignedLongCompare(estProduct, rs)) {
							qhat--;
						}
					}
				}
			}

			// D4 Multiply and subtract
			int borrow;
			rem.value[limit - 1 + rem.offset] = 0;
			if (needRemainder) {
				borrow = mulsub(rem.value, divisor, qhat, dlen, limit - 1 + rem.offset);
			} else {
				borrow = mulsubBorrow(rem.value, divisor, qhat, dlen, limit - 1 + rem.offset);
			}

			// D5 Test remainder
			if (borrow + 0x80000000 > nh2) {
				// D6 Add back
				if (needRemainder) {
					divadd(divisor, rem.value, limit - 1 + 1 + rem.offset);
				}
				qhat--;
			}

			// Store the quotient digit
			q[(limit - 1)] = qhat;
		}

		if (needRemainder) {
			// D8 Unnormalize
			if (shift > 0) {
				rem.rightShift(shift);
			}
			rem.normalize();
		}
		quotient.normalize();
		return needRemainder ? rem : null;
	}


	/**
	 * Compare two longs as if they were unsigned. Returns true iff one is bigger than two.
	 */
	private boolean unsignedLongCompare(long one, long two) {
		return (one + Long.MIN_VALUE) > (two + Long.MIN_VALUE);
	}

	/**
	 * This method divides a long quantity by an int to estimate qhat for two multi precision numbers. It is used when
	 * the signed value of n is less than zero. Returns long value where high 32 bits contain remainder value and low 32
	 * bits contain quotient value.
	 */
	static long divWord(long n, int d) {
		long dLong = d & LONG_MASK;
		long r;
		long q;
		if (dLong == 1) {
			q = (int) n;
			r = 0;
			return (r << 32) | (q & LONG_MASK);
		}

		// Approximate the quotient and remainder
		q = (n >>> 1) / (dLong >>> 1);
		r = n - q * dLong;

		// Correct the approximation
		while (r < 0) {
			r += dLong;
			q--;
		}
		while (r >= dLong) {
			r -= dLong;
			q++;
		}
		// n - q*dlong == r && 0 <= r <dLong, hence we're done.
		return (r << 32) | (q & LONG_MASK);
	}


}