Christmas special answer.
Fully tested using Unit tests, but as yet only on Java SE.
Needs some work for instantiating the backing array.
Some code can still be optimized by in-lining the left hand operand.
Note that this code uses *= - assignment of the answer to the first variable - rather than * as it is not a good idea to create object instances during Java Card runtime (they are created in persistent memory).
Stripped all the JavaDoc comments, as it would not fit the maximum post size otherwise.
/**
* Free for use by all, please keep this line and the author line intact.
*
* @author Maarten Bodewes
*/
public final class JCInteger {
private static final short BYTE_SIZE = 8;
private static final short SHORT_SIZE = 16;
private static final short INTEGER_SIZE = 32;
private static final short HIGH = 0;
private static final short LOW = 1;
private final short[] values;
private JCInteger(final byte memoryType) {
// TODO this should be backed by an array in RAM, using JCSystem.makeTransientByteArray()
// using either JCSystem.CLEAR_ON_RESET or JCSystem.CLEAR_ON_DESELECT
values = new short[(short) 2];
}
public static JCInteger createInstance(final byte memoryType) {
return new JCInteger(memoryType);
}
public JCInteger assign(final JCInteger rightHandOperand) {
values[HIGH] = rightHandOperand.values[HIGH];
values[LOW] = rightHandOperand.values[LOW];
return this;
}
public JCInteger assign(final short high, final short low) {
values[HIGH] = high;
values[LOW] = low;
return this;
}
public JCInteger assignSigned(final short signedValue) {
if (signedValue >= 0) {
values[HIGH] = (short) 0x0000;
} else {
values[HIGH] = (short) 0xFFFF;
}
values[LOW] = signedValue;
return this;
}
public JCInteger assignUnsigned(final short unsignedValue) {
values[HIGH] = (short) 0x0000;
values[LOW] = unsignedValue;
return this;
}
public short getHigh() {
// no pun intended
return values[HIGH];
}
public short getLow() {
return values[LOW];
}
public short[] getBackingShortArray() {
return values;
}
public JCInteger negate() {
// basically invert, then increase, note that -Integer.MIN_VALUE = Integer.MIN_VALUE (as it is in Java)
values[HIGH] = (short)~values[HIGH];
values[LOW] = (short)~values[LOW];
increment();
return this;
}
public JCInteger increment() {
values[LOW]++;
if (values[LOW] == 0) {
values[HIGH]++;
}
return this;
}
public JCInteger decrement() {
values[LOW]--;
if (values[LOW] == -1) {
values[HIGH]--;
}
return this;
}
public JCInteger add(final JCInteger y) {
addUnsignedLow(y.values[LOW]);
values[HIGH] += y.values[HIGH];
return this;
}
public JCInteger subtract(final JCInteger y) {
// subtracts by adding the negated i
// negation is identical to invert + increase
// however the increase is performed to the result of adding the inverted value
// invert
final short xlInv = (short) ~y.values[LOW];
final short xhInv = (short) ~y.values[HIGH];
// add
addUnsignedLow(xlInv);
values[HIGH] += xhInv;
// increase
increment();
return this;
}
public JCInteger multiply(JCInteger y) {
// uses the fact that:
// x * y =
// (x1 * 2 ^ 16 + x0) * (y1 * 2 ^ 16 + y0) =
// (x1 * y1 * 2 ^ 32) + x1 * y0 * 2 ^ 16 + x0 * y1 * 2 ^ 16 + x0 * y0 =
// x1 * y0 * 2 ^ 16 + x0 * y1 * 2 ^ 16 + x0 * y0 (because anything * 2 ^ 32 overflows all the bits) =
// x1 * y0 * 2 ^ 16 + x0 * y1 * 2 ^ 16 + z1 | z0 (where z1 = high 16 bits of x0 * y* and z0 is the low part) =
// r1 | r0 where r1 = x1 * y0 + x0 * y1 + z1 and r0 = z0
// r1 is only 16 bits so x1 * y0 and x0 * y0 may overflow, as may the additions, hopefully leaving the sign
// bit correctly set
boolean xPositive = this.isPositive();
if (!xPositive) {
this.negate();
}
final short xh = this.values[HIGH];
final short xl = this.values[LOW];
short yh = y.values[HIGH];
short yl = y.values[LOW];
// --- if signed then negate y ---
final boolean yPositive;
if ((yh & 0x8000) == 0) {
yPositive = true;
} else {
// negation (complement then increase)
yh = (short) ~yh;
yl = (short) ~yl;
yl++;
if (yl == 0) {
yh++;
}
yPositive = false;
}
// calculates z1 and z0 and stores it in the current values
multiplyUnsigned(xl, yl, values);
// perform the calculation for the high parts
values[HIGH] += (short) (xh * yl + xl * yh);
// make sure we return a correctly signed value
if ((xPositive && !yPositive) || (!xPositive && yPositive)) {
this.negate();
}
return this;
}
public JCInteger divide(JCInteger y) {
// --- pre-calculations on y ---
// put y in yh and yl
short yh = y.values[HIGH];
short yl = y.values[LOW];
if (yh == 0 && yl == 0) {
// division by zero
throw new ArithmeticException();
}
final boolean yPositive;
if ((yh & 0x8000) == 0) {
yPositive = true;
} else {
// negation (complement then increase)
yh = (short) ~yh;
yl = (short) ~yl;
yl++;
if (yl == 0) {
yh++;
}
yPositive = false;
}
final short divisorSize = (short) (INTEGER_SIZE - numberOfLeadingZeros(yh, yl));
// --- pre-calculations on x ---
final boolean xPositive = this.isPositive();
if (!xPositive) {
this.negate();
}
final short dividentSize = (short) (INTEGER_SIZE - numberOfLeadingZeros());
// --- setup the maximum number of shifts ---
final short maxShifts = (short) (dividentSize - divisorSize);
// --- slightly superfluous check if divisor is higher than dividend ---
if (maxShifts < 0) {
// return 0, no division can be performed
values[HIGH] = 0;
values[LOW] = 0;
return this;
}
// --- shift divisor left until the highest bit is aligned with the highest bit of the dividend ---
if (maxShifts <= JCInteger.SHORT_SIZE) {
yh = (short) (((yl & 0xFFFF) >>> (SHORT_SIZE - maxShifts)) | (yh << maxShifts));
yl <<= maxShifts;
} else {
yh = (short) (yl << (maxShifts - SHORT_SIZE));
yl = 0;
}
short rh = 0, rl = 0;
for (short i = maxShifts; i >= 0; i--) {
final short xho = values[HIGH];
final short xlo = values[LOW];
// --- subtract (add complement and increment does the job) ---
// add complement
addUnsignedLow((short) ~yl);
values[HIGH] += (short) ~yh;
// increase to create subtraction
increment();
if (isPositive()) {
// --- we have subtracted y * 2 ^ n, so include 2 ^ n to the result ---
if (i >= SHORT_SIZE) {
rh |= 1 << (i - SHORT_SIZE);
} else {
rl |= 1 << i;
}
} else {
// --- we could not subtract, so restore ---
values[HIGH] = xho;
values[LOW] = xlo;
}
// --- shift right by 1 ---
// first do low shift as high shift changes value
yl = (short) ((yh << (JCInteger.SHORT_SIZE - 1)) | ((yl & 0xFFFF) >>> 1));
yh = (short) ((yh & 0xFFFF) >>> 1);
}
values[HIGH] = rh;
values[LOW] = rl;
// make sure we return a correctly signed value (may mess up sign bit on overflows?)
if ((xPositive && !yPositive) || (!xPositive && yPositive)) {
this.negate();
}
return this;
}
public JCInteger remainder(JCInteger y) {
// --- pre-calculations on y ---
// put y in yh and yl
short yh = y.values[HIGH];
short yl = y.values[LOW];
if (yh == 0 && yl == 0) {
// division by zero
throw new ArithmeticException();
}
if ((yh & 0x8000) != 0) {
// negation (complement then increase)
yh = (short) ~yh;
yl = (short) ~yl;
yl++;
if (yl == 0) {
yh++;
}
}
final short divisorSize = (short) (INTEGER_SIZE - numberOfLeadingZeros(yh, yl));
// --- pre-calculations on x ---
final boolean xPositive = this.isPositive();
if (!xPositive) {
this.negate();
}
final short dividentSize = (short) (INTEGER_SIZE - numberOfLeadingZeros());
// --- setup the maximum number of shifts ---
final short maxShifts = (short) (dividentSize - divisorSize);
// --- slightly superfluous check if divisor is higher than dividend ---
if (maxShifts < 0) {
if (!xPositive) {
return this.negate();
}
return this;
}
// --- shift divisor left until the highest bit is aligned with the highest bit of the dividend ---
if (maxShifts <= JCInteger.SHORT_SIZE) {
yh = (short) (((yl & 0xFFFF) >>> (SHORT_SIZE - maxShifts)) | (yh << maxShifts));
yl <<= maxShifts;
} else {
yh = (short) (yl << (maxShifts - SHORT_SIZE));
yl = 0;
}
for (short i = maxShifts; i >= 0; i--) {
final short xho = values[HIGH];
final short xlo = values[LOW];
// --- subtract (add complement and increment does the job) ---
// add complement
addUnsignedLow((short) ~yl);
values[HIGH] += (short) ~yh;
// increase to create subtraction
increment();
if (!isPositive()) {
values[HIGH] = xho;
values[LOW] = xlo;
}
// --- shift right by 1 ---
// first do low shift as high shift changes value
yl = (short) ((yh << (JCInteger.SHORT_SIZE - 1)) | ((yl & 0xFFFF) >>> 1));
yh = (short) ((yh & 0xFFFF) >>> 1);
}
if (!xPositive) {
negate();
}
return this;
}
public JCInteger leftShift(short shiftDistance) {
shiftDistance = (short) (shiftDistance & 0x1F);
if (shiftDistance == 0) {
return this;
}
final short low = values[LOW];
final short high = values[HIGH];
// TODO test if we can
与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…
