Back to index...

	/*
	* Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
	* 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 sun.security.util.math.intpoly;

	import sun.security.util.math.*;

	import java.math.BigInteger;
	import java.nio.ByteBuffer;
	import java.nio.ByteOrder;
	import java.util.Arrays;

	/**
	* A large number polynomial representation using sparse limbs of signed
	* long (64-bit) values. Limb values will always fit within a long, so inputs
	* to multiplication must be less than 32 bits. All IntegerPolynomial
	* implementations allow at most one addition before multiplication. Additions
	* after that will result in an ArithmeticException.
	*
	* The following element operations are branch-free for all subclasses:
	*
	* fixed
	* mutable
	* add
	* additiveInverse
	* multiply
	* square
	* subtract
	* conditionalSwapWith
	* setValue (may branch on high-order byte parameter only)
	* setSum
	* setDifference
	* setProduct
	* setSquare
	* addModPowerTwo
	* asByteArray
	*
	* All other operations may branch in some subclasses.
	*
	*/

	public abstract class IntegerPolynomial implements IntegerFieldModuloP {

	protected static final BigInteger TWO = BigInteger.valueOf(2);

	protected final int numLimbs;
	private final BigInteger modulus;
	protected final int bitsPerLimb;
	private final long[] posModLimbs;
	private final int maxAdds;

	/**
	* Reduce an IntegerPolynomial representation (a) and store the result
	* in a. Requires that a.length == numLimbs.
	*/
	protected abstract void reduce(long[] a);

	/**
	* Multiply an IntegerPolynomial representation (a) with a long (b) and
	* store the result in an IntegerPolynomial representation in a. Requires
	* that a.length == numLimbs.
	*/
	protected void multByInt(long[] a, long b) {
	for (int i = 0; i < a.length; i++) {
	a[i] *= b;
	}
	reduce(a);
	}

	/**
	* Multiply two IntegerPolynomial representations (a and b) and store the
	* result in an IntegerPolynomial representation (r). Requires that
	* a.length == b.length == r.length == numLimbs. It is allowed for a and r
	* to be the same array.
	*/
	protected abstract void mult(long[] a, long[] b, long[] r);

	/**
	* Multiply an IntegerPolynomial representation (a) with itself and store
	* the result in an IntegerPolynomialRepresentation (r). Requires that
	* a.length == r.length == numLimbs. It is allowed for a and r
	* to be the same array.
	*/
	protected abstract void square(long[] a, long[] r);

	IntegerPolynomial(int bitsPerLimb,
	int numLimbs,
	int maxAdds,
	BigInteger modulus) {


	this.numLimbs = numLimbs;
	this.modulus = modulus;
	this.bitsPerLimb = bitsPerLimb;
	this.maxAdds = maxAdds;

	posModLimbs = setPosModLimbs();
	}

	private long[] setPosModLimbs() {
	long[] result = new long[numLimbs];
	setLimbsValuePositive(modulus, result);
	return result;
	}

	protected int getNumLimbs() {
	return numLimbs;
	}

	public int getMaxAdds() {
	return maxAdds;
	}

	@Override
	public BigInteger getSize() {
	return modulus;
	}

	@Override
	public ImmutableElement get0() {
	return new ImmutableElement(false);
	}

	@Override
	public ImmutableElement get1() {
	return new ImmutableElement(true);
	}

	@Override
	public ImmutableElement getElement(BigInteger v) {
	return new ImmutableElement(v);
	}

	@Override
	public SmallValue getSmallValue(int value) {
	int maxMag = 1 << (bitsPerLimb - 1);
	if (Math.abs(value) >= maxMag) {
	throw new IllegalArgumentException(
	"max magnitude is " + maxMag);
	}
	return new Limb(value);
	}

	/**
	* This version of encode takes a ByteBuffer that is properly ordered, and
	* may extract larger values (e.g. long) from the ByteBuffer for better
	* performance. The implementation below only extracts bytes from the
	* buffer, but this method may be overridden in field-specific
	* implementations.
	*/
	protected void encode(ByteBuffer buf, int length, byte highByte,
	long[] result) {

	int numHighBits = 32 - Integer.numberOfLeadingZeros(highByte);
	int numBits = 8 * length + numHighBits;
	int requiredLimbs = (numBits + bitsPerLimb - 1) / bitsPerLimb;
	if (requiredLimbs > numLimbs) {
	long[] temp = new long[requiredLimbs];
	encodeSmall(buf, length, highByte, temp);
	// encode does a full carry/reduce
	System.arraycopy(temp, 0, result, 0, result.length);
	} else {
	encodeSmall(buf, length, highByte, result);
	}
	}

	protected void encodeSmall(ByteBuffer buf, int length, byte highByte,
	long[] result) {

	int limbIndex = 0;
	long curLimbValue = 0;
	int bitPos = 0;
	for (int i = 0; i < length; i++) {
	long curV = buf.get() & 0xFF;

	if (bitPos + 8 >= bitsPerLimb) {
	int bitsThisLimb = bitsPerLimb - bitPos;
	curLimbValue += (curV & (0xFF >> (8 - bitsThisLimb))) << bitPos;
	result[limbIndex++] = curLimbValue;
	curLimbValue = curV >> bitsThisLimb;
	bitPos = 8 - bitsThisLimb;
	}
	else {
	curLimbValue += curV << bitPos;
	bitPos += 8;
	}
	}

	// one more for the high byte
	if (highByte != 0) {
	long curV = highByte & 0xFF;
	if (bitPos + 8 >= bitsPerLimb) {
	int bitsThisLimb = bitsPerLimb - bitPos;
	curLimbValue += (curV & (0xFF >> (8 - bitsThisLimb))) << bitPos;
	result[limbIndex++] = curLimbValue;
	curLimbValue = curV >> bitsThisLimb;
	}
	else {
	curLimbValue += curV << bitPos;
	}
	}

	if (limbIndex < result.length) {
	result[limbIndex++] = curLimbValue;
	}
	Arrays.fill(result, limbIndex, result.length, 0);

	postEncodeCarry(result);
	}

	protected void encode(byte[] v, int offset, int length, byte highByte,
	long[] result) {

	ByteBuffer buf = ByteBuffer.wrap(v, offset, length);
	buf.order(ByteOrder.LITTLE_ENDIAN);
	encode(buf, length, highByte, result);
	}

	// Encode does not produce compressed limbs. A simplified carry/reduce
	// operation can be used to compress the limbs.
	protected void postEncodeCarry(long[] v) {
	reduce(v);
	}

	public ImmutableElement getElement(byte[] v, int offset, int length,
	byte highByte) {

	long[] result = new long[numLimbs];

	encode(v, offset, length, highByte, result);

	return new ImmutableElement(result, 0);
	}

	protected BigInteger evaluate(long[] limbs) {
	BigInteger result = BigInteger.ZERO;
	for (int i = limbs.length - 1; i >= 0; i--) {
	result = result.shiftLeft(bitsPerLimb)
	.add(BigInteger.valueOf(limbs[i]));
	}
	return result.mod(modulus);
	}

	protected long carryValue(long x) {
	// compressing carry operation
	// if large positive number, carry one more to make it negative
	// if large negative number (closer to zero), carry one fewer
	return (x + (1 << (bitsPerLimb - 1))) >> bitsPerLimb;
	}

	protected void carry(long[] limbs, int start, int end) {

	for (int i = start; i < end; i++) {

	long carry = carryOut(limbs, i);
	limbs[i + 1] += carry;
	}
	}

	protected void carry(long[] limbs) {

	carry(limbs, 0, limbs.length - 1);
	}

	/**
	* Carry out of the specified position and return the carry value.
	*/
	protected long carryOut(long[] limbs, int index) {
	long carry = carryValue(limbs[index]);
	limbs[index] -= (carry << bitsPerLimb);
	return carry;
	}

	private void setLimbsValue(BigInteger v, long[] limbs) {
	// set all limbs positive, and then carry
	setLimbsValuePositive(v, limbs);
	carry(limbs);
	}

	protected void setLimbsValuePositive(BigInteger v, long[] limbs) {
	BigInteger mod = BigInteger.valueOf(1 << bitsPerLimb);
	for (int i = 0; i < limbs.length; i++) {
	limbs[i] = v.mod(mod).longValue();
	v = v.shiftRight(bitsPerLimb);
	}
	}

	/**
	* Carry out of the last limb and reduce back in. This method will be
	* called as part of the "finalReduce" operation that puts the
	* representation into a fully-reduced form. It is representation-
	* specific, because representations have different amounts of empty
	* space in the high-order limb. Requires that limbs.length=numLimbs.
	*/
	protected abstract void finalCarryReduceLast(long[] limbs);

	/**
	* Convert reduced limbs into a number between 0 and MODULUS-1.
	* Requires that limbs.length == numLimbs. This method only works if the
	* modulus has at most three terms.
	*/
	protected void finalReduce(long[] limbs) {

	// This method works by doing several full carry/reduce operations.
	// Some representations have extra high bits, so the carry/reduce out
	// of the high position is implementation-specific. The "unsigned"
	// carry operation always carries some (negative) value out of a
	// position occupied by a negative value. So after a number of
	// passes, all negative values are removed.

	// The first pass may leave a negative value in the high position, but
	// this only happens if something was carried out of the previous
	// position. So the previous position must have a "small" value. The
	// next full carry is guaranteed not to carry out of that position.

	for (int pass = 0; pass < 2; pass++) {
	// unsigned carry out of last position and reduce in to
	// first position
	finalCarryReduceLast(limbs);

	// unsigned carry on all positions
	long carry = 0;
	for (int i = 0; i < numLimbs - 1; i++) {
	limbs[i] += carry;
	carry = limbs[i] >> bitsPerLimb;
	limbs[i] -= carry << bitsPerLimb;
	}
	limbs[numLimbs - 1] += carry;
	}

	// Limbs are positive and all less than 2^bitsPerLimb, and the
	// high-order limb may be even smaller due to the representation-
	// specific carry/reduce out of the high position.
	// The value may still be greater than the modulus.
	// Subtract the max limb values only if all limbs end up non-negative
	// This only works if there is at most one position where posModLimbs
	// is less than 2^bitsPerLimb - 1 (not counting the high-order limb,
	// if it has extra bits that are cleared by finalCarryReduceLast).
	int smallerNonNegative = 1;
	long[] smaller = new long[numLimbs];
	for (int i = numLimbs - 1; i >= 0; i--) {
	smaller[i] = limbs[i] - posModLimbs[i];
	// expression on right is 1 if smaller[i] is nonnegative,
	// 0 otherwise
	smallerNonNegative *= (int) (smaller[i] >> 63) + 1;
	}
	conditionalSwap(smallerNonNegative, limbs, smaller);

	}

	/**
	* Decode the value in v and store it in dst. Requires that v is final
	* reduced. I.e. all limbs in [0, 2^bitsPerLimb) and value in [0, modulus).
	*/
	protected void decode(long[] v, byte[] dst, int offset, int length) {

	int nextLimbIndex = 0;
	long curLimbValue = v[nextLimbIndex++];
	int bitPos = 0;
	for (int i = 0; i < length; i++) {

	int dstIndex = i + offset;
	if (bitPos + 8 >= bitsPerLimb) {
	dst[dstIndex] = (byte) curLimbValue;
	curLimbValue = 0;
	if (nextLimbIndex < v.length) {
	curLimbValue = v[nextLimbIndex++];
	}
	int bitsAdded = bitsPerLimb - bitPos;
	int bitsLeft = 8 - bitsAdded;

	dst[dstIndex] += (curLimbValue & (0xFF >> bitsAdded))
	<< bitsAdded;
	curLimbValue >>= bitsLeft;
	bitPos = bitsLeft;
	} else {
	dst[dstIndex] = (byte) curLimbValue;
	curLimbValue >>= 8;
	bitPos += 8;
	}
	}
	}

	/**
	* Add two IntegerPolynomial representations (a and b) and store the result
	* in an IntegerPolynomialRepresentation (dst). Requires that
	* a.length == b.length == dst.length. It is allowed for a and
	* dst to be the same array.
	*/
	protected void addLimbs(long[] a, long[] b, long[] dst) {
	for (int i = 0; i < dst.length; i++) {
	dst[i] = a[i] + b[i];
	}
	}

	/**
	* Branch-free conditional assignment of b to a. Requires that set is 0 or
	* 1, and that a.length == b.length. If set==0, then the values of a and b
	* will be unchanged. If set==1, then the values of b will be assigned to a.
	* The behavior is undefined if swap has any value other than 0 or 1.
	*/
	protected static void conditionalAssign(int set, long[] a, long[] b) {
	int maskValue = 0 - set;
	for (int i = 0; i < a.length; i++) {
	long dummyLimbs = maskValue & (a[i] ^ b[i]);
	a[i] = dummyLimbs ^ a[i];
	}
	}

	/**
	* Branch-free conditional swap of a and b. Requires that swap is 0 or 1,
	* and that a.length == b.length. If swap==0, then the values of a and b
	* will be unchanged. If swap==1, then the values of a and b will be
	* swapped. The behavior is undefined if swap has any value other than
	* 0 or 1.
	*/
	protected static void conditionalSwap(int swap, long[] a, long[] b) {
	int maskValue = 0 - swap;
	for (int i = 0; i < a.length; i++) {
	long dummyLimbs = maskValue & (a[i] ^ b[i]);
	a[i] = dummyLimbs ^ a[i];
	b[i] = dummyLimbs ^ b[i];
	}
	}

	/**
	* Stores the reduced, little-endian value of limbs in result.
	*/
	protected void limbsToByteArray(long[] limbs, byte[] result) {

	long[] reducedLimbs = limbs.clone();
	finalReduce(reducedLimbs);

	decode(reducedLimbs, result, 0, result.length);
	}

	/**
	* Add the reduced number corresponding to limbs and other, and store
	* the low-order bytes of the sum in result. Requires that
	* limbs.length==other.length. The result array may have any length.
	*/
	protected void addLimbsModPowerTwo(long[] limbs, long[] other,
	byte[] result) {

	long[] reducedOther = other.clone();
	long[] reducedLimbs = limbs.clone();
	finalReduce(reducedOther);
	finalReduce(reducedLimbs);

	addLimbs(reducedLimbs, reducedOther, reducedLimbs);

	// may carry out a value which can be ignored
	long carry = 0;
	for (int i = 0; i < numLimbs; i++) {
	reducedLimbs[i] += carry;
	carry = reducedLimbs[i] >> bitsPerLimb;
	reducedLimbs[i] -= carry << bitsPerLimb;
	}

	decode(reducedLimbs, result, 0, result.length);
	}

	private abstract class Element implements IntegerModuloP {

	protected long[] limbs;
	protected int numAdds;

	public Element(BigInteger v) {
	limbs = new long[numLimbs];
	setValue(v);
	}

	public Element(boolean v) {
	this.limbs = new long[numLimbs];
	this.limbs[0] = v ? 1l : 0l;
	this.numAdds = 0;
	}

	private Element(long[] limbs, int numAdds) {
	this.limbs = limbs;
	this.numAdds = numAdds;
	}

	private void setValue(BigInteger v) {
	setLimbsValue(v, limbs);
	this.numAdds = 0;
	}

	@Override
	public IntegerFieldModuloP getField() {
	return IntegerPolynomial.this;
	}

	@Override
	public BigInteger asBigInteger() {
	return evaluate(limbs);
	}

	@Override
	public MutableElement mutable() {
	return new MutableElement(limbs.clone(), numAdds);
	}

	protected boolean isSummand() {
	return numAdds < maxAdds;
	}

	@Override
	public ImmutableElement add(IntegerModuloP genB) {

	Element b = (Element) genB;
	if (!(isSummand() && b.isSummand())) {
	throw new ArithmeticException("Not a valid summand");
	}

	long[] newLimbs = new long[limbs.length];
	for (int i = 0; i < limbs.length; i++) {
	newLimbs[i] = limbs[i] + b.limbs[i];
	}

	int newNumAdds = Math.max(numAdds, b.numAdds) + 1;
	return new ImmutableElement(newLimbs, newNumAdds);
	}

	@Override
	public ImmutableElement additiveInverse() {

	long[] newLimbs = new long[limbs.length];
	for (int i = 0; i < limbs.length; i++) {
	newLimbs[i] = -limbs[i];
	}

	ImmutableElement result = new ImmutableElement(newLimbs, numAdds);
	return result;
	}

	protected long[] cloneLow(long[] limbs) {
	long[] newLimbs = new long[numLimbs];
	copyLow(limbs, newLimbs);
	return newLimbs;
	}
	protected void copyLow(long[] limbs, long[] out) {
	System.arraycopy(limbs, 0, out, 0, out.length);
	}

	@Override
	public ImmutableElement multiply(IntegerModuloP genB) {

	Element b = (Element) genB;

	long[] newLimbs = new long[limbs.length];
	mult(limbs, b.limbs, newLimbs);
	return new ImmutableElement(newLimbs, 0);
	}

	@Override
	public ImmutableElement square() {
	long[] newLimbs = new long[limbs.length];
	IntegerPolynomial.this.square(limbs, newLimbs);
	return new ImmutableElement(newLimbs, 0);
	}

	public void addModPowerTwo(IntegerModuloP arg, byte[] result) {

	Element other = (Element) arg;
	if (!(isSummand() && other.isSummand())) {
	throw new ArithmeticException("Not a valid summand");
	}
	addLimbsModPowerTwo(limbs, other.limbs, result);
	}

	public void asByteArray(byte[] result) {
	if (!isSummand()) {
	throw new ArithmeticException("Not a valid summand");
	}
	limbsToByteArray(limbs, result);
	}
	}

	protected class MutableElement extends Element
	implements MutableIntegerModuloP {

	protected MutableElement(long[] limbs, int numAdds) {
	super(limbs, numAdds);
	}

	@Override
	public ImmutableElement fixed() {
	return new ImmutableElement(limbs.clone(), numAdds);
	}

	@Override
	public void conditionalSet(IntegerModuloP b, int set) {

	Element other = (Element) b;

	conditionalAssign(set, limbs, other.limbs);
	numAdds = other.numAdds;
	}

	@Override
	public void conditionalSwapWith(MutableIntegerModuloP b, int swap) {

	MutableElement other = (MutableElement) b;

	conditionalSwap(swap, limbs, other.limbs);
	int numAddsTemp = numAdds;
	numAdds = other.numAdds;
	other.numAdds = numAddsTemp;
	}


	@Override
	public MutableElement setValue(IntegerModuloP v) {
	Element other = (Element) v;

	System.arraycopy(other.limbs, 0, limbs, 0, other.limbs.length);
	numAdds = other.numAdds;
	return this;
	}

	@Override
	public MutableElement setValue(byte[] arr, int offset,
	int length, byte highByte) {

	encode(arr, offset, length, highByte, limbs);
	this.numAdds = 0;

	return this;
	}

	@Override
	public MutableElement setValue(ByteBuffer buf, int length,
	byte highByte) {

	encode(buf, length, highByte, limbs);
	numAdds = 0;

	return this;
	}

	@Override
	public MutableElement setProduct(IntegerModuloP genB) {
	Element b = (Element) genB;
	mult(limbs, b.limbs, limbs);
	numAdds = 0;
	return this;
	}

	@Override
	public MutableElement setProduct(SmallValue v) {
	int value = ((Limb) v).value;
	multByInt(limbs, value);
	numAdds = 0;
	return this;
	}

	@Override
	public MutableElement setSum(IntegerModuloP genB) {

	Element b = (Element) genB;
	if (!(isSummand() && b.isSummand())) {
	throw new ArithmeticException("Not a valid summand");
	}

	for (int i = 0; i < limbs.length; i++) {
	limbs[i] = limbs[i] + b.limbs[i];
	}

	numAdds = Math.max(numAdds, b.numAdds) + 1;
	return this;
	}

	@Override
	public MutableElement setDifference(IntegerModuloP genB) {

	Element b = (Element) genB;
	if (!(isSummand() && b.isSummand())) {
	throw new ArithmeticException("Not a valid summand");
	}

	for (int i = 0; i < limbs.length; i++) {
	limbs[i] = limbs[i] - b.limbs[i];
	}

	numAdds = Math.max(numAdds, b.numAdds) + 1;
	return this;
	}

	@Override
	public MutableElement setSquare() {
	IntegerPolynomial.this.square(limbs, limbs);
	numAdds = 0;
	return this;
	}

	@Override
	public MutableElement setAdditiveInverse() {

	for (int i = 0; i < limbs.length; i++) {
	limbs[i] = -limbs[i];
	}
	return this;
	}

	@Override
	public MutableElement setReduced() {

	reduce(limbs);
	numAdds = 0;
	return this;
	}
	}

	class ImmutableElement extends Element implements ImmutableIntegerModuloP {

	protected ImmutableElement(BigInteger v) {
	super(v);
	}

	protected ImmutableElement(boolean v) {
	super(v);
	}

	protected ImmutableElement(long[] limbs, int numAdds) {
	super(limbs, numAdds);
	}

	@Override
	public ImmutableElement fixed() {
	return this;
	}

	}

	class Limb implements SmallValue {
	int value;

	Limb(int value) {
	this.value = value;
	}
	}


	}

Back to index...