Diff: BigInt.cpp

Revision:

0:9d554894785b

Child:

1:00f2c40d46ed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/BigInt.cpp	Fri Sep 20 13:29:23 2013 +0000
@@ -0,0 +1,290 @@
+#include "BigInt.h"
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <iostream>
+#include <climits>
+
+
+static uint32_t max(const uint32_t a, const uint32_t b)
+{
+    return a < b ? b : a;
+}
+
+static uint32_t num(const uint32_t a)
+{
+    return a/4 + (a%4 ? 1:0); 
+}
+    
+BigInt::BigInt():
+size(0),
+bits(0)
+{
+}
+
+BigInt::BigInt(const BigInt &a):
+size(a.size)
+{
+    uint32_t l = num(size);
+    bits = new uint32_t[l];
+    for(int i = 0; i < l; ++i)
+        bits[i] = a.bits[i];
+}
+
+
+BigInt::~BigInt()
+{
+    if(bits)
+        delete[] bits;
+    bits = 0;
+}
+
+BigInt& BigInt::operator=(const BigInt& a)
+{
+    size = a.size;
+    uint32_t l = num(size);
+    if(bits)
+        delete[] bits;
+    bits = new uint32_t[l];
+    for(int i = 0; i < l; ++i)
+        bits[i] = a.bits[i];    
+    return *this;
+}
+
+void BigInt::import(uint8_t *data, uint32_t length)
+{
+    size = length;
+    size_t l = size/4;
+    if(size % 4 != 0)
+        l++;
+    if(bits)
+        delete[] bits;
+    bits = new uint32_t[l];
+    memset(bits, 0, sizeof(uint32_t)*l);
+    for(int i = 0; i < length; ++i)
+        bits[i/4] |= data[i] << ((i%4)*8);
+}
+
+BigInt operator+(const BigInt &a, const BigInt& b)
+{
+    BigInt result;
+    
+    result.size = a.size > b.size ? a.size : b.size;
+    size_t l = result.size/4;
+    if(result.size % 4 != 0)
+        l++;
+    result.bits = new uint32_t[l];
+    memset(result.bits, 0, sizeof(uint32_t)*l);
+    uint32_t al = num(a.size);
+    uint32_t bl = num(b.size);
+    uint32_t carry = 0;
+    for(int i = 0; i < l; ++i)
+    {
+        uint32_t tmpA = 0, tmpB = 0;
+        if(i < al)
+            tmpA = a.bits[i];
+        if(i < bl)
+            tmpB = b.bits[i];
+        result.bits[i] = tmpA + tmpB + carry;
+        carry = result.bits[i] < max(tmpA, tmpB);
+    }
+    if(carry)
+    {
+        result.size++;
+        if(result.size > l*4)
+        { 
+            l++;
+            result.bits = (uint32_t*)realloc(result.bits, l * sizeof(uint32_t));
+            result.bits[l-1] = 0x00000001;
+        }
+        else
+        {
+            result.bits[l-1] += 1 << (8 *((result.size-1)%4));
+        }
+    }
+    
+    return result;
+}
+
+BigInt& BigInt::operator+=(const BigInt &b)
+{
+    return (*this = (*this) + b);
+}
+
+BigInt& BigInt::operator++()
+{
+    uint8_t tmp = 1;
+    BigInt a;
+    a.import(&tmp, 1);
+    
+    return (*this += a);
+}
+
+BigInt BigInt::operator++(int)
+{
+    BigInt t = *this;
+    uint8_t tmp = 1;
+    BigInt a;
+    a.import(&tmp, 1);
+    this->operator+=(a);
+    return t;
+}
+
+// a - b, if b >= a, returns 0
+// No negative number allowed
+BigInt operator-(const BigInt &a, const BigInt& b)
+{
+    BigInt result;
+
+    if(b >= a)
+    {
+        uint8_t tmp = 0;
+        result.import(&tmp, 1);
+        return result;
+    }
+    else
+    {
+        result.size = a.size;
+        uint32_t l = num(a.size);
+        result.bits = new uint32_t[l];
+        memset(result.bits, 0, sizeof(uint32_t)*l);
+        uint32_t bl = num(b.size);
+        uint8_t borrow = 0;
+        for(uint32_t i = 0; i < l; ++i)
+        {
+            uint32_t tmpA = a.bits[i], tmpB = 0;
+            if(i < bl)
+                tmpB = b.bits[i];
+            if(borrow)
+            {
+                if(tmpA == 0)
+                    tmpA = ULONG_MAX;
+                else
+                    --tmpA;
+                    
+                if(tmpA < tmpB)            
+                    result.bits[i] = tmpA + 1 + (ULONG_MAX - tmpB);
+                else
+                    result.bits[i] = tmpA - tmpB;
+
+                if(a.bits[i] != 0 && tmpA > tmpB)
+                    borrow = 0;
+            }
+            else
+            {
+                if(tmpA < tmpB)            
+                    result.bits[i] = tmpA + 1 + (ULONG_MAX - tmpB);
+                else
+                    result.bits[i] = tmpA - tmpB;
+                borrow = tmpA < tmpB;
+            }
+        }
+        
+        // trim result
+        uint8_t *tmp = (uint8_t*)result.bits;
+        uint32_t newSize = result.size;
+        while(tmp[newSize-1] == 0 && newSize > 0)
+            newSize--;
+        result.size = newSize;
+        uint32_t tmpL = num(result.size);
+        if(tmpL < l)
+            result.bits = (uint32_t*)realloc(result.bits, sizeof(uint32_t)*tmpL); 
+        
+        return result;
+    }
+}
+
+BigInt& BigInt::operator-=(const BigInt &b)
+{
+    return (*this = (*this) - b);
+}
+
+BigInt& BigInt::operator--()
+{
+    uint8_t tmp = 1;
+    BigInt a;
+    a.import(&tmp, 1);
+    
+    return (*this -= a);
+}
+
+BigInt BigInt::operator--(int)
+{
+    BigInt t = *this;
+    uint8_t tmp = 1;
+    BigInt a;
+    a.import(&tmp, 1);
+    this->operator-=(a);
+    return t;
+}
+
+bool operator==(const BigInt &a, const BigInt &b)
+{
+    if(a.size != b.size)
+        return false;
+        
+    uint32_t l = num(a.size);
+    for(int i = 0; i < l; ++i)
+        if(a.bits[i] != b.bits[i])
+            return false;
+    return true;
+}
+
+bool operator!=(const BigInt &a, const BigInt &b)
+{
+    return ! (a==b);
+}
+
+bool operator<(const BigInt &a, const BigInt &b)
+{
+    if(a.size < b.size)
+        return true;
+    if(a.size > b.size)
+        return false;
+    uint32_t l = num(a.size);
+    for(int i = l-1; i >= 0; --i)
+        if(a.bits[i] < b.bits[i])
+            return true;
+    return false;
+}
+
+bool operator<=(const BigInt &a, const BigInt &b)
+{
+    return (a < b) || (a == b);
+}
+
+bool operator>(const BigInt &a, const BigInt &b)
+{
+    if(a.size > b.size)
+        return true;
+    if(a.size < b.size)
+        return false;
+    uint32_t l = num(a.size);
+    for(int i = l-1; i >= 0; --i)
+        if(a.bits[i] > b.bits[i])
+            return true;
+    return false;
+}
+
+bool operator>=(const BigInt &a, const BigInt &b)
+{
+    return (a > b) || (a == b);
+}
+
+bool BigInt::operator!()
+{
+    if(size != 1)
+        return false;
+    return bits[0] == 0;
+}
+ 
+void BigInt::print()
+{
+    printf("size: %d bytes\n", size);
+    uint32_t n = num(size);
+    for(int i = n-1; i >= 0; --i)
+    {
+        printf("%08x", bits[i]);
+    }
+    printf("\n");
+}