From ee5287fabfb214e8f7b483cde424108270525fd7 Mon Sep 17 00:00:00 2001 From: Sam Moore Date: Sat, 5 Jul 2014 12:44:48 +0800 Subject: [PATCH] Arbint class with += and -= operators 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 | 6 +- src/arbint.cpp | 186 +++++++++++++++++++++++++++++++----- src/arbint.h | 62 +++++++++++- src/main.cpp | 4 +- src/tests/add_digits.s | 28 ------ src/tests/add_digits_test.c | 39 -------- src/tests/arb.cpp | 9 +- 7 files changed, 232 insertions(+), 102 deletions(-) delete mode 100644 src/tests/add_digits.s delete mode 100644 src/tests/add_digits_test.c diff --git a/src/Makefile b/src/Makefile index 0041932..d92c969 100644 --- a/src/Makefile +++ b/src/Makefile @@ -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 -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 @@ -73,6 +73,10 @@ $(BIN) : $(LINKOBJ) ../obj/$(MAIN) @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 : diff --git a/src/arbint.cpp b/src/arbint.cpp index ccde0dd..4f8aff2 100644 --- a/src/arbint.cpp +++ b/src/arbint.cpp @@ -1,52 +1,190 @@ #include "arbint.h" #include #include + + +#include +#include +#include +#include + 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(""); - 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 { - uint32_t q = w % 10; + digit_t q = w % 10; 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; } +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(m_digits[i]); + } + return ss.str(); +} + } diff --git a/src/arbint.h b/src/arbint.h index d90a43b..1507ba7 100644 --- a/src/arbint.h +++ b/src/arbint.h @@ -1,26 +1,78 @@ #ifndef _ARBINT_H #define _ARBINT_H -#include +#include "common.h" 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); + + + 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: - std::vector m_words; + + Arbint & AddBasic(const Arbint & add); + Arbint & SubBasic(const Arbint & sub); + + std::vector m_digits; 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 diff --git a/src/main.cpp b/src/main.cpp index 8ead652..cd74d6d 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -94,11 +94,11 @@ int main(int argc, char ** argv) for (int y = 0; y < 8; ++y) { //doc.Add(static_cast((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(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 index 39f4af9..0000000 --- a/src/tests/add_digits.s +++ /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 index 7bf385a..0000000 --- a/src/tests/add_digits_test.c +++ /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 -#include - -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]); - } - - -} diff --git a/src/tests/arb.cpp b/src/tests/arb.cpp index 29c6325..c867a8f 100644 --- a/src/tests/arb.cpp +++ b/src/tests/arb.cpp @@ -2,13 +2,16 @@ #include #include -#include "arbint.cpp" +#include "arbint.h" 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()); } -- 2.20.1