Arbint class with += and -= operators
authorSam Moore <matches@ucc.asn.au>
Sat, 5 Jul 2014 04:44:48 +0000 (12:44 +0800)
committerSam Moore <matches@ucc.asn.au>
Sat, 5 Jul 2014 04:44:48 +0000 (12:44 +0800)
Using x64 assembly routines for addition and subtraction loops,
but C++ for memory management through std::vector

Dealing with the sign is a bit annoying.

(Get it?)

src/Makefile
src/arbint.cpp
src/arbint.h
src/main.cpp
src/tests/add_digits.s [deleted file]
src/tests/add_digits_test.c [deleted file]
src/tests/arb.cpp

index 0041932..d92c969 100644 (file)
@@ -3,7 +3,7 @@ ARCH := $(shell uname -m)
 # TODO: stb_truetype doesn't compile with some of these warnings.
 CXX = g++ -std=gnu++0x -g -Wall -Werror -Wshadow -pedantic -rdynamic
 MAIN = main.o
 # TODO: stb_truetype doesn't compile with some of these warnings.
 CXX = g++ -std=gnu++0x -g -Wall -Werror -Wshadow -pedantic -rdynamic
 MAIN = main.o
-OBJ = log.o real.o bezier.o document.o objectrenderer.o view.o screen.o vfpu.o graphicsbuffer.o framebuffer.o shaderprogram.o stb_truetype.o gl_core44.o
+OBJ = log.o real.o bezier.o document.o objectrenderer.o view.o screen.o vfpu.o graphicsbuffer.o framebuffer.o shaderprogram.o stb_truetype.o gl_core44.o add_digits_asm.o sub_digits_asm.o arbint.o
 LIB_x86_64 = ../contrib/lib/libSDL2-2.0.so.0 -lGL
 LIB_i386 = ../contrib/lib32/libSDL2-2.0.so.0 -lGL
 
 LIB_x86_64 = ../contrib/lib/libSDL2-2.0.so.0 -lGL
 LIB_i386 = ../contrib/lib32/libSDL2-2.0.so.0 -lGL
 
@@ -73,6 +73,10 @@ $(BIN) : $(LINKOBJ) ../obj/$(MAIN)
        @mkdir -p $(dir $@)
        $(CXX) $(CFLAGS) $(DEF) -c -MMD -o $@ $<
 
        @mkdir -p $(dir $@)
        $(CXX) $(CFLAGS) $(DEF) -c -MMD -o $@ $<
 
+../obj/%_asm.o : %_asm.s main.h
+       @mkdir -p $(dir $@)
+       $(CXX) -c -o $@ $<
+
 -include $(DEPS)
 
 clean_bin :
 -include $(DEPS)
 
 clean_bin :
index ccde0dd..4f8aff2 100644 (file)
 #include "arbint.h"
 #include <algorithm>
 #include <cstring>
 #include "arbint.h"
 #include <algorithm>
 #include <cstring>
+
+
+#include <string>
+#include <iomanip>
+#include <sstream>
+#include <cstdarg>
+
 using namespace std;
 
 using namespace std;
 
-/*
-static bool addc(uint32_t a, uint32_t b, uint32_t * r)
+namespace IPDF
+{
+
+Arbint::Arbint(digit_t i) : m_digits(1), m_sign(i < 0)
 {
 {
-       volatile uint32_t carry = false;
-       volatile uint32_t result = a + b;
-       asm volatile
-       (
-               "jc 1f;"
-               "mov $0, %%eax;"
-               "1:"
-               : "=a" (carry)
-       );
-       *r = result;    
-       return (carry == 1);
+       m_digits[0] = i;
 }
 }
-*/
 
 
-namespace IPDF
+Arbint::Arbint(unsigned n, digit_t d0, ...) : m_digits(n), m_sign(false)
+{
+       va_list ap;
+       va_start(ap, d0);
+       if (n > 1)
+               m_digits[0] = d0;
+       for (unsigned i = 1; i < n; ++i)
+       {
+               m_digits[i] = va_arg(ap, digit_t);
+       }
+       va_end(ap);
+}
+
+Arbint::Arbint(const Arbint & cpy) : m_digits(cpy.m_digits.size()), m_sign(cpy.m_sign)
+{
+       memcpy(m_digits.data(), cpy.m_digits.data(), 
+               sizeof(digit_t)*m_digits.size());
+}
+
+Arbint & Arbint::operator=(const Arbint & cpy)
+{
+       memmove(m_digits.data(), cpy.m_digits.data(), 
+               sizeof(digit_t)*min(m_digits.size(), cpy.m_digits.size()));
+       if (cpy.m_digits.size() > m_digits.size())
+       {
+               unsigned old_size = m_digits.size();
+               m_digits.resize(cpy.m_digits.size());
+               memset(m_digits.data()+old_size, 0, sizeof(digit_t)*m_digits.size()-old_size);
+       }
+       return *this;
+}
+
+void Arbint::Zero()
+{
+       memset(m_digits.data(), 0, sizeof(digit_t)*m_digits.size());
+}
+
+unsigned Arbint::Shrink()
+{
+       if (m_digits.size() <= 1)
+               return 0;
+       unsigned i;
+       for (i = m_digits.size()-1; (i > 0 && m_digits[i] != 0L); --i);
+       unsigned result = m_digits.size() - i;
+       m_digits.resize(i);
+       return result;
+}
+
+Arbint & Arbint::operator+=(const Arbint & add)
+{
+       if (m_sign == add.m_sign)
+       {
+               // -a + -b == -(a + b)
+               return AddBasic(add);
+       }
+       
+       if (m_sign)
+       {
+               // -a + b == -(a - b)
+               m_sign = false;
+               SubBasic(add);
+               m_sign = !m_sign;
+       }
+       else
+       {
+               // a + -b == a - b
+               SubBasic(add);
+       }
+       return *this;
+}
+
+Arbint & Arbint::operator-=(const Arbint & sub)
 {
 {
+       if (m_sign == sub.m_sign)
+               return SubBasic(sub);
+       return AddBasic(sub);
+}
 
 
-Arbint::Arbint(int64_t i) : m_words(2), m_sign(false)
+Arbint & Arbint::AddBasic(const Arbint & add)
 {
 {
-       m_sign = i < 0;
-       memcpy(m_words.data(), &i, sizeof(int64_t));
+       if (add.m_digits.size() >= m_digits.size())
+       {
+               m_digits.resize(add.m_digits.size()+1,0L);
+       }
+       
+       digit_t carry = add_digits((digit_t*)m_digits.data(), 
+                       (digit_t*)add.m_digits.data(), add.m_digits.size());
+       if (carry != 0L)
+               m_digits[m_digits.size()-1] = carry;
+       else if (m_digits.back() == 0L)
+               m_digits.resize(m_digits.size()-1);
+       return *this;
 }
 
 }
 
-string Arbint::Str() const
+Arbint & Arbint::SubBasic(const Arbint & sub)
+{
+       if (sub.m_digits.size() >= m_digits.size())
+       {
+               m_digits.resize(sub.m_digits.size(),0L);
+       }
+       digit_t borrow = sub_digits((digit_t*)m_digits.data(), 
+                       (digit_t*)sub.m_digits.data(), sub.m_digits.size());
+               
+               
+       //TODO: Write ASM to do this bit?
+       if (borrow != 0L)
+       {
+               m_sign = !m_sign;
+               for (unsigned i = 0; i < m_digits.size(); ++i)
+                       m_digits[i] = -m_digits[i];
+       }
+       return *this;
+       return *this;
+}
+
+
+string Arbint::Str(const string & base) const
 {
        string s("");
 {
        string s("");
-       for (unsigned i = 0; i < m_words.size(); ++i)
+       for (unsigned i = 0; i < m_digits.size(); ++i)
        {
        {
-               uint32_t w = m_words[i];
+               digit_t w = m_digits[i];
                do
                {
                do
                {
-                       uint32_t q = w % 10;
+                       digit_t q = w % 10;
                        w /= 10;
                        s += ('0' + q);
                }
                while (w > 0);
                        w /= 10;
                        s += ('0' + q);
                }
                while (w > 0);
-               if (i+1 < m_words.size()) s += ",";     
+               if (i+1 < m_digits.size()) s += ",";    
        }
        }
-       if (m_sign) s += '-';
        reverse(s.begin(), s.end());
        return s;
 }
 
        reverse(s.begin(), s.end());
        return s;
 }
 
+bool Arbint::operator==(const Arbint & equ) const
+{
+       if (m_sign != equ.m_sign) return false;
+       unsigned min_size = m_digits.size();
+       const Arbint * larger = &equ;
+       if (m_digits.size() > equ.m_digits.size())
+       {
+               min_size = equ.m_digits.size();
+               larger = this;
+       }
+       
+       if (memcmp(m_digits.data(), equ.m_digits.data(), min_size) != 0)
+               return false;
+       
+       for (unsigned i = min_size; i < larger->m_digits.size(); ++i)
+       {
+               if (larger->m_digits[i] != 0L)
+                       return false;
+       }
+       return true;
+}
+
+string Arbint::DigitStr() const
+{
+       stringstream ss("");
+       //ss << std::hex << std::setfill('0');
+       for (unsigned i = 0; i < m_digits.size(); ++i)
+       {
+               if (i != 0) ss << ',';
+               ss << std::setw(2*sizeof(digit_t)) << static_cast<digit_t>(m_digits[i]);
+       }
+       return ss.str();
+}
+
 }
 }
index d90a43b..1507ba7 100644 (file)
@@ -1,26 +1,78 @@
 #ifndef _ARBINT_H
 #define _ARBINT_H
 
 #ifndef _ARBINT_H
 #define _ARBINT_H
 
-#include <vector>
+#include "common.h"
 
 namespace IPDF
 {
        class Arbint
        {
                public:
 
 namespace IPDF
 {
        class Arbint
        {
                public:
-                       Arbint(int64_t i);
+                       typedef int64_t digit_t;
+               
+                       Arbint(digit_t i);
+                       Arbint(unsigned n, digit_t d0, ...);
+                       Arbint(const std::string & str, const std::string & base="0123456789");
                        ~Arbint() {}
                        Arbint(const Arbint & cpy);
                        ~Arbint() {}
                        Arbint(const Arbint & cpy);
+                       
+                       
+                       inline bool Sign() const {return m_sign;}
+                       inline char SignChar() const {return (m_sign) ? '-' : '+';}
+                       std::string DigitStr() const;
 
 
-                       std::string Str() const;
-               
+                       std::string Str(const std::string & base="0123456789") const;
+                       inline std::string Str(const char * base) const
+                       {
+                               return Str(std::string(base));
+                       }
+                       
+                       Arbint & operator=(const Arbint & equ);
+                       Arbint & operator+=(const Arbint & add);
+                       Arbint & operator-=(const Arbint & sub);
+       
+                       
+                       bool operator==(const Arbint & equ) const;
+                       
+                       
+                       inline Arbint operator+(const Arbint & add) const 
+                       {
+                               Arbint a(*this);
+                               a += add;
+                               return a;
+                       }
+                       inline Arbint operator-(const Arbint & add) const 
+                       {
+                               Arbint a(*this);
+                               a -= add;
+                               return a;
+                       }       
+                       inline bool operator!=(const Arbint & equ) const 
+                       {
+                               return !this->operator==(equ);
+                       }
+                       
+                       unsigned Shrink();
                private:                
                private:                
-                       std::vector<uint32_t> m_words;
+                               
+                       Arbint & AddBasic(const Arbint & add);
+                       Arbint & SubBasic(const Arbint & sub);
+       
+                       std::vector<digit_t> m_digits;
                        bool m_sign;
                        bool m_sign;
+                       void Zero();
+
                        
                        
                        
        };      
                        
                        
                        
        };      
+
+extern "C"
+{
+       typedef int64_t digit_t;
+       digit_t add_digits(digit_t * dst, digit_t * add, digit_t size);
+       digit_t sub_digits(digit_t * dst, digit_t * add, digit_t size);
 }
 
 }
 
+}
 #endif //_ARBINT_H
 #endif //_ARBINT_H
index 8ead652..cd74d6d 100644 (file)
@@ -94,11 +94,11 @@ int main(int argc, char ** argv)
                        for (int y = 0; y < 8; ++y)
                        {
                                //doc.Add(static_cast<IPDF::ObjectType>((x^y)%3), Rect(0.2+x-4.0,0.2+y-4.0,0.6,0.6));
                        for (int y = 0; y < 8; ++y)
                        {
                                //doc.Add(static_cast<IPDF::ObjectType>((x^y)%3), Rect(0.2+x-4.0,0.2+y-4.0,0.6,0.6));
-                               //doc.Add(BEZIER, Rect(0.2+x-4.0, 0.2+y-4.0, 0.6,0.6), (x^y)%3);
+                               doc.Add(BEZIER, Rect(0.2+x-4.0, 0.2+y-4.0, 0.6,0.6), (x^y)%3);
                        }
                        
                        //doc.Add(RECT_OUTLINE, Rect(0.1,0.1,0.8,0.8), 0);
                        }
                        
                        //doc.Add(RECT_OUTLINE, Rect(0.1,0.1,0.8,0.8), 0);
-                       doc.Add(BEZIER, Rect(0,0,1,1), 0);
+                       //doc.Add(BEZIER, Rect(0,0,1,1), 0);
                }
                
        }
                }
                
        }
diff --git a/src/tests/add_digits.s b/src/tests/add_digits.s
deleted file mode 100644 (file)
index 39f4af9..0000000
+++ /dev/null
@@ -1,28 +0,0 @@
-.section .text
-.globl add_digits
-.type add_digits, @function
-
-# Add two arrays of 64 bit digits, with carry, modifying the first argument
-# Address at first argument %rdi is array to add and modify
-# Address at second %rsi will be added (not modified)
-# Third argument is counter of number of digits
-# Result in %rax is the final result in the carry flag
-# Exploits the fact that inc and dec do not affect the carry flag
-add_digits:
-       loop:
-               movq (%rsi), %rax # Temporarily store digit from second array
-               adcq %rax, (%rdi) # Add digits in second and first array, store in first
-               dec %rdx # Decrement counter
-               jz end_loop # We are done
-               
-               # Move to next element in the first array
-               leaq 8(,%rdi,1), %rdi
-               # Move to next element in the second array
-               leaq 8(,%rsi,1), %rsi
-               jmp loop # Repeat
-       end_loop:
-               movq $0, %rax
-               jnc end
-               movq $1, %rax
-       end:
-               ret # We are done
diff --git a/src/tests/add_digits_test.c b/src/tests/add_digits_test.c
deleted file mode 100644 (file)
index 7bf385a..0000000
+++ /dev/null
@@ -1,39 +0,0 @@
-/**
- * Compile and linking:
- * gcc -c add_digits.s
- * gcc -c add_digits_test.c
- * gcc -o add_digits_test add_digits_test.o add_digits.o
- */
-//TODO: Move to C++
-
-#include <stdlib.h>
-#include <stdio.h>
-
-int64_t add_digit(int64_t * a, int64_t * b);
-
-int main(int argc, char ** argv)
-{
-       int64_t s1[] = {5,6,7,0xFFFFFFFFFFFFFFFF,0};
-       int64_t s2[] = {7,1,5,1L,0};
-       
-       int size = sizeof(s1)/sizeof(int64_t);
-       
-       printf("Before adding s1 and s2:\n");
-       int i;
-       for (i = 0; i < size; ++i)
-       {
-               printf("s1[%d] = %.16lx\t", i, s1[i]);
-               printf("s2[%d] = %.16lx\n", i, s2[i]);
-       }
-       
-       add_digits(s1, s2, size);
-       printf("\nAfter adding s1 and s2:\n");
-       for (i = 0; i < size; ++i)
-       {
-               printf("s1[%d] = %.16lx\t", i, s1[i]);
-               printf("s2[%d] = %.16lx\n", i, s2[i]);
-       }
-       
-       
-}
index 29c6325..c867a8f 100644 (file)
@@ -2,13 +2,16 @@
 #include <cstdio>
 #include <iostream>
 
 #include <cstdio>
 #include <iostream>
 
-#include "arbint.cpp"
+#include "arbint.h"
 
 using namespace std;
 using namespace IPDF;
 
 int main(int argc, char ** argv)
 {
 
 using namespace std;
 using namespace IPDF;
 
 int main(int argc, char ** argv)
 {
-       Arbint a(4294967296L);
-       printf("%s\n", a.Str().c_str());
+       Arbint a(100L);
+       Arbint b(200L);
+       
+       Arbint c(b-a);
+       printf("(%d), %s\n",c.Sign(), c.DigitStr().c_str());
 }
 }

UCC git Repository :: git.ucc.asn.au