447 lines
8.8 KiB
C#
447 lines
8.8 KiB
C#
using System;
|
|
using sharp.extensions;
|
|
namespace BigInt
|
|
{
|
|
public static class BigIntMath
|
|
{
|
|
/* Public Interface */
|
|
|
|
public static bool sign(UInt32[] value){
|
|
return (value[value.Length - 1] & (1 << 31)) != 0;
|
|
}
|
|
|
|
public static int log2(UInt32[] value)
|
|
{
|
|
switch (sign(value)){
|
|
case false:
|
|
for (int n = value.Length << 5; n > 0; n--)
|
|
{
|
|
if ((value[(n - 1) >> 5] & (1 << ((n - 1) & 0x1F))) != 0)
|
|
{
|
|
return n - 1;
|
|
}
|
|
}
|
|
return 0;
|
|
case true:
|
|
for (int n = (value.Length << 5)-1; n > 0; n--)
|
|
{
|
|
if ((value[(n - 1) >> 5] & (1 << ((n - 1) & 0x1F))) == 0)
|
|
{
|
|
return 1 - n;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
public static bool isZero(UInt32[] value){
|
|
foreach (UInt32 v in value){
|
|
if (v != 0){
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
public static UInt32[] ones(UInt32[] value){
|
|
UInt32[] result = value.Segment(0);
|
|
for (int n = 0; n < result.Length;n++){
|
|
result[n] ^= 0xffffffff;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
public static UInt32[] twos(UInt32[] value){
|
|
UInt32[] result = ones(value);
|
|
UInt32[] one = new UInt32[]{1};
|
|
result = add(result, one);
|
|
return result;
|
|
}
|
|
|
|
/**
|
|
* Extend signed integer to higher width
|
|
**/
|
|
public static UInt32[] extendSigned(UInt32[] value,int width){
|
|
UInt32[] result = value.Segment(0).Extend(width);
|
|
if (sign(value))
|
|
{
|
|
for (int n = value.Length; n < width; n++)
|
|
{
|
|
result[n] = 0xFFFFFFFF;
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
public static void extendEqualSigned(ref UInt32[] a, ref UInt32[] b){
|
|
int width = a.Length > b.Length ? a.Length : b.Length;
|
|
|
|
a = extendSigned(a, width);
|
|
b = extendSigned(b, width);
|
|
}
|
|
|
|
public static UInt32[] signedFromUnsigned(UInt32[] value){
|
|
if (sign(value)){
|
|
return value.Extend(value.Length+1);
|
|
}
|
|
return value;
|
|
}
|
|
|
|
/**
|
|
* Reduce signed integer to smallest width, needed to represent its value
|
|
**/
|
|
public static UInt32[] reduceSigned(UInt32[] value){
|
|
int n = value.Length;
|
|
|
|
//Console.WriteLine("reduceSigned(): < {0}", value.getBytes().Reverse().toHexString());
|
|
|
|
for (; n > 1; n--){
|
|
if (
|
|
((value[n-1] != 0) || ((value[n-2] & (1<<31))!=0)) && ((value[n-1] != 0xFFFFFFFF) || ((value[n-2] & (1<<31))==0))
|
|
){
|
|
break;
|
|
}
|
|
}
|
|
value = value.Segment(0, n);
|
|
|
|
//Console.WriteLine("reduceSigned(): > {0}", value.getBytes().Reverse().toHexString());
|
|
|
|
return value;
|
|
}
|
|
|
|
/**
|
|
* Reduce unsigned integer to smallest width, needed to represent its value
|
|
**/
|
|
public static UInt32[] reduceUnsigned(UInt32[] value)
|
|
{
|
|
int n = value.Length;
|
|
for (; n > 1; n--){
|
|
if (value[n-1] != 0){
|
|
break;
|
|
}
|
|
}
|
|
return value.Segment(0,n);
|
|
}
|
|
|
|
public static UInt32[] add(UInt32[] a, UInt32[] b)
|
|
{
|
|
UInt32 c = 0;
|
|
|
|
a = a.Segment(0);
|
|
extendEqualSigned(ref a, ref b);
|
|
|
|
for (int n = 0; n < a.Length; n++)
|
|
{
|
|
a[n] = add(a[n], b[n], ref c);
|
|
}
|
|
return a;
|
|
}
|
|
|
|
public static UInt32[] sub(UInt32[] a, UInt32[] b)
|
|
{
|
|
UInt32 c = 0;
|
|
a = a.Segment(0);
|
|
|
|
extendEqualSigned(ref a, ref b);
|
|
|
|
for (int n = 0; n < a.Length; n++)
|
|
{
|
|
a[n] = sub(a[n], b[n], ref c);
|
|
}
|
|
return a;
|
|
}
|
|
|
|
public static UInt32[] umul(UInt32[] a, UInt32[] b)
|
|
{
|
|
UInt32[] result = new UInt32[a.Length + b.Length];
|
|
|
|
for (int l1 = 0; l1 < a.Length; l1++)
|
|
{
|
|
for (int l2 = 0; l2 < (b.Length); l2++)
|
|
{
|
|
int target = l1 + l2;
|
|
UInt64 ui64 = ((UInt64)a[l1] * b[l2]);
|
|
for (int ct = target; (ct < result.Length) && (ui64 != 0); ct++){
|
|
ui64 += result[ct];
|
|
result[ct] = (UInt32)ui64;
|
|
ui64 >>= 32;
|
|
}
|
|
}
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
public static UInt32[] smul(UInt32[] a, UInt32[] b)
|
|
{
|
|
a = extendSigned(a, a.Length << 1);
|
|
b = extendSigned(b, b.Length << 1);
|
|
|
|
UInt32[] result = new UInt32[(a.Length + b.Length)>>1];
|
|
|
|
for (int l1 = 0; l1 < a.Length; l1++)
|
|
{
|
|
for (int l2 = 0; l2 < (b.Length); l2++)
|
|
{
|
|
int target = l1 + l2;
|
|
UInt64 ui64 = ((UInt64)a[l1] * b[l2]);
|
|
for (int ct = target; (ct < result.Length) && (ui64 != 0); ct++)
|
|
{
|
|
ui64 += result[ct];
|
|
result[ct] = (UInt32)ui64;
|
|
ui64 >>= 32;
|
|
}
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
/**
|
|
* @brief Calulate a / b. (unsigned values)
|
|
* @returns Result of division.
|
|
**/
|
|
public static UInt32[] udiv(UInt32[] a,UInt32[] b){
|
|
return udivmod(ref a, b);
|
|
}
|
|
public static UInt32[] umod(UInt32[] a,UInt32[] b){
|
|
UInt32[] m = a.Segment(0);
|
|
udivmod(ref m,b);
|
|
return m;
|
|
}
|
|
|
|
public static UInt32[] udivmod(ref UInt32[] _a, UInt32[] b)
|
|
{
|
|
UInt32[] a = _a;
|
|
|
|
if (cmp(a, b) < 0)
|
|
{
|
|
return new UInt32[a.Length];
|
|
}
|
|
|
|
UInt32[] result = new UInt32[a.Length];
|
|
UInt32[] d = b.Segment(0).Extend(a.Length);
|
|
|
|
int lg2a, lg2b, shift;
|
|
|
|
lg2a = log2(a);
|
|
lg2b = log2(d);
|
|
shift = lg2a - lg2b;
|
|
|
|
if (shift > 0)
|
|
{
|
|
shl(d, shift);
|
|
}
|
|
|
|
for (int n = 0; n <= (shift); n++)
|
|
{
|
|
shl(result, 1);
|
|
|
|
if (cmp(d, a) <= 0)
|
|
{
|
|
result[0] |= 1;
|
|
a = sub(a, d);
|
|
}
|
|
|
|
shr(d, 1);
|
|
}
|
|
_a = a;
|
|
return result;
|
|
}
|
|
|
|
/**
|
|
* @brief Calulate a / b. (unsigned values)
|
|
* @returns Result of division. a[] will contain reminder.
|
|
**/
|
|
public static UInt32[] sdiv(UInt32[] a, UInt32[] b)
|
|
{
|
|
return sdivmod(ref a, b);
|
|
}
|
|
public static UInt32[] smod(UInt32[] a, UInt32[] b)
|
|
{
|
|
UInt32[] m = a.Segment(0);
|
|
sdivmod(ref m, b);
|
|
return m;
|
|
}
|
|
|
|
/**
|
|
* sdivmod ( a , b )
|
|
*
|
|
* Calculate Quotient and Reminder of a / b using signed integer arithmetics
|
|
* returns quotient
|
|
* leaves reminder in <param name="a">
|
|
*
|
|
**/
|
|
public static UInt32[] sdivmod(ref UInt32[] a, UInt32[] b)
|
|
{
|
|
bool sgna, sgnb;
|
|
|
|
sgna = sign(a);
|
|
sgnb = sign(b);
|
|
|
|
//Console.WriteLine("sdivmod(): a = {0}",a.getBytes().Reverse().toHexString());
|
|
//Console.WriteLine("sdivmod(): b = {0}",b.getBytes().Reverse().toHexString());
|
|
|
|
if (sgna){
|
|
a = twos(a);
|
|
}
|
|
if (sgnb){
|
|
b = twos(b);
|
|
}
|
|
|
|
UInt32[] result = udivmod(ref a, b);
|
|
|
|
if (sgna != sgnb){
|
|
result = twos(result);
|
|
}
|
|
if (sgna){
|
|
a = twos(a);
|
|
}
|
|
|
|
//Console.WriteLine("sdivmod(): result = {0}",result.getBytes().Reverse().toHexString());
|
|
//Console.WriteLine("sdivmod(): reminder = {0}",a.getBytes().Reverse().toHexString());
|
|
|
|
return result;
|
|
}
|
|
|
|
/**
|
|
* @brief Logical Shift Left
|
|
**/
|
|
public static void shl(UInt32[] a, int n)
|
|
{
|
|
if (n > 0)
|
|
{
|
|
int step = n >> 5;
|
|
n &= 0x1F;
|
|
|
|
for (int i = a.Length; i > 0; i--)
|
|
{
|
|
int b1 = i - 1 - step;
|
|
int b2 = b1 - 1;
|
|
|
|
if (b1 >= 0){
|
|
a[i - 1] = (a[b1] << n);
|
|
if ((n != 0)&&(b2 >= 0))
|
|
{
|
|
a[i - 1] |= ((a[b2] >> (32 - n)));
|
|
}
|
|
} else {
|
|
a[i - 1] = 0;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
/**
|
|
* @brief Logical Shift Right
|
|
**/
|
|
public static void shr(UInt32[] a, int n)
|
|
{
|
|
if (n > 0)
|
|
{
|
|
bool s = sign(a);
|
|
int step = n >> 5;
|
|
n &= 0x1F;
|
|
|
|
for (int i = 0; i < a.Length; i++)
|
|
{
|
|
int b1 = i + step;
|
|
int b2 = b1 + 1;
|
|
|
|
if (b1 < a.Length)
|
|
{
|
|
a[i] = (a[b1] >> n);
|
|
if ((b2 == a.Length) && (s)){
|
|
a[i] |= ((0xffffffff << (32 - n)));
|
|
} else if ((n != 0) && (b2 < a.Length))
|
|
{
|
|
a[i] |= ((a[b2] << (32 - n)));
|
|
}
|
|
|
|
} else {
|
|
a[i] = s ? 0xFFFFFFFF : 0;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief Compare
|
|
* @returns Negative Value if a<b, Positive Value if a>b,0 if equal
|
|
**/
|
|
public static int cmp(UInt32[] a, UInt32[] b)
|
|
{
|
|
a = a.Segment(0);
|
|
b = b.Segment(0);
|
|
extendEqualSigned(ref a, ref b);
|
|
|
|
UInt32[] result = sub(a, b);
|
|
|
|
if (isZero(result))
|
|
{
|
|
return 0;
|
|
}
|
|
else if (sign(result))
|
|
{
|
|
return -1;
|
|
}
|
|
else
|
|
{
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/* Helper Functions */
|
|
|
|
private static UInt32 add(UInt32 a, UInt32 b, ref UInt32 carry)
|
|
{
|
|
UInt64 ui64 = (UInt64)carry + (UInt64)a + (UInt64)b;
|
|
carry = (UInt32)(ui64 >> 32);
|
|
return (UInt32)(ui64 & 0xffffffff);
|
|
}
|
|
private static UInt32 add(UInt32 a, ref UInt32 carry)
|
|
{
|
|
UInt64 ui64 = (UInt64)carry + (UInt64)a;
|
|
carry = (UInt32)(ui64 >> 32);
|
|
return (UInt32)(ui64 & 0xffffffff);
|
|
}
|
|
|
|
private static UInt32 sub(UInt32 a, UInt32 b, ref UInt32 carry)
|
|
{
|
|
UInt64 ui64 = (UInt64)a - (UInt64)b - (UInt64)carry;
|
|
carry = (ui64 & (1UL << 63)) != 0 ? (UInt32)1 : (UInt32)0;
|
|
return (UInt32)(ui64 & 0xffffffff);
|
|
}
|
|
private static UInt32 sub(UInt32 a, ref UInt32 carry)
|
|
{
|
|
UInt64 ui64 = (UInt64)a - (UInt64)carry;
|
|
carry = (ui64 & (1UL << 63)) != 0 ? (UInt32)1 : (UInt32)0;
|
|
return (UInt32)(ui64 & 0xffffffff);
|
|
}
|
|
|
|
private static UInt32 shl(UInt32 a, int n, ref UInt32 carry)
|
|
{
|
|
UInt64 result = (UInt64)((UInt64)a << n) | carry;
|
|
carry = (UInt32)(result >> 32);
|
|
return (UInt32)result;
|
|
}
|
|
private static UInt32 shr(UInt32 a, int n, ref UInt32 carry)
|
|
{
|
|
UInt64 result = (UInt64)((UInt64)a << (32 - n)) | ((UInt64)carry << 32);
|
|
carry = (UInt32)result;
|
|
return (UInt32)(result >> 32);
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
}
|
|
}
|