Hi,
sorry for not really knowing what the etiquette should be here. This
patch alters the MPN class so that when performing adds and subtracts it
avoids the use of longs. This is possible by an "unsigned_less_than"
operation that itself uses longs, but any tree pattern matcher (such as
those produced by iburg) should be able to convert into an unsigned
integer comparison. ie match:
boolcmp: BOOLEAN_CMP_INT(LONG_AND(register, INT_CONSTANT),
LONG_AND(register, INT_CONSTANT))
where the INT_CONSTANTs are both 0xFFFFFFFFL the boolean operation is
less than and the emitted code just does an unsigned integer compare on
the two registers.
In any case the revised code has fewer long/int operations, I believe.
I've also not tested the code, so I'm really just putting it here to
generate discussion.
Thanks,
Ian Rogers
-- http://www.cs.man.ac.uk/~irogers
--- MPN.java 2005-07-02 21:32:13.000000000 +0100
+++ MPN.hack 2006-03-22 10:55:05.000000000 +0000
@@ -47,68 +47,66 @@
* (at least on platforms that use 32-bit "limbs").
*/
public class MPN
{
+ /**
+ * Perform an unsigned less than comparison on two signed integers
+ */
+ private static boolean unsigned_less_than(int x, int y)
+ {
+ return ((long)x & 0xffffffffL) < ((long)y & 0xffffffffL);
+ }
/** Add x[0:size-1] and y, and write the size least
* significant words of the result to dest.
* Return carry, either 0 or 1.
* All values are unsigned.
* This is basically the same as gmp's mpn_add_1. */
public static int add_1 (int[] dest, int[] x, int size, int y)
{
- long carry = (long) y & 0xffffffffL;
- for (int i = 0; i < size; i++)
- {
- carry += ((long) x[i] & 0xffffffffL);
- dest[i] = (int) carry;
- carry >>= 32;
- }
- return (int) carry;
+ boolean carry = false;
+ for (int i = 0; i < size; i++) {
+ int result = x[i] + y + (carry ? 1 : 0);
+ carry = unsigned_less_than(result, x[i]);
+ dest[i] = result;
+ }
+ return carry ? 1 : 0;
}
/** Add x[0:len-1] and y[0:len-1] and write the len least
* significant words of the result to dest[0:len-1].
* All words are treated as unsigned.
* @return the carry, either 0 or 1
* This function is basically the same as gmp's mpn_add_n.
*/
public static int add_n (int dest[], int[] x, int[] y, int len)
{
- long carry = 0;
- for (int i = 0; i < len; i++)
- {
- carry += ((long) x[i] & 0xffffffffL)
- + ((long) y[i] & 0xffffffffL);
- dest[i] = (int) carry;
- carry >>>= 32;
- }
- return (int) carry;
+ boolean carry = false;
+ for (int i = 0; i < size; i++) {
+ int result = x[i] + y[i] + (carry ? 1 : 0);
+ carry = unsigned_less_than(result, x[i]);
+ dest[i] = result;
+ }
+ return carry ? 1 : 0;
}
/** Subtract Y[0:size-1] from X[0:size-1], and write
* the size least significant words of the result to dest[0:size-1].
* Return borrow, either 0 or 1.
* This is basically the same as gmp's mpn_sub_n function.
*/
- public static int sub_n (int[] dest, int[] X, int[] Y, int size)
+ public static int sub_n (int[] dest, int[] x, int[] y, int size)
{
- int cy = 0;
- for (int i = 0; i < size; i++)
- {
- int y = Y[i];
- int x = X[i];
- y += cy; /* add previous carry to subtrahend */
- // Invert the high-order bit, because: (unsigned) X > (unsigned) Y
- // iff: (int) (X^0x80000000) > (int) (Y^0x80000000).
- cy = (y^0x80000000) < (cy^0x80000000) ? 1 : 0;
- y = x - y;
- cy += (y^0x80000000) > (x ^ 0x80000000) ? 1 : 0;
- dest[i] = y;
- }
- return cy;
+ boolean borrow = false;
+ for (int i = 0; i < size; i++) {
+ int subtrahend = y[i] + (borrow ? 1 : 0);
+ int result = x[i] - subtrahend;
+ borrow = unsigned_less_than(x[i], subtrahend);
+ dest[i] = result;
+ }
+ return borrow ? 1 : 0;
}
/** Multiply x[0:len-1] by y, and write the len least
* significant words of the product to dest[0:len-1].
* Return the most significant word of the product.
