From f34eb76357fdfc314d6451fd11a2e4d6fcfce434 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Mon, 15 Apr 2013 15:28:12 -0600 Subject: Initial checkin. This project will most likely just be stuck into libbu++, but I didn't want to deal with building it all in windows. --- .gitignore | 4 ++ src/main.cpp | 54 +++++++++++++++++++ src/number.cpp | 54 +++++++++++++++++++ src/number.h | 30 +++++++++++ src/packedintarray.cpp | 137 +++++++++++++++++++++++++++++++++++++++++++++++++ src/packedintarray.h | 36 +++++++++++++ 6 files changed, 315 insertions(+) create mode 100644 .gitignore create mode 100644 src/main.cpp create mode 100644 src/number.cpp create mode 100644 src/number.h create mode 100644 src/packedintarray.cpp create mode 100644 src/packedintarray.h diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..5a6e66f --- /dev/null +++ b/.gitignore @@ -0,0 +1,4 @@ +.*.swp +*.o +*.exe + diff --git a/src/main.cpp b/src/main.cpp new file mode 100644 index 0000000..be49a1d --- /dev/null +++ b/src/main.cpp @@ -0,0 +1,54 @@ +#include "number.h" +#include "packedintarray.h" + +#include +using namespace Bu; + +void packedtest1() +{ + println("-==- Packed Int Test -==-"); + + PackedIntArray a(4); + a.append( 3 ); + a.append( 9 ); + a.append( 5 ); + + println("%1").arg( a.toString() ); + println("%1").arg( a.toBitString() ); + println("%1").arg( PackedIntArray(4, 10).toString() ); + + PackedIntArray b(5); + for( int j = 0; j < 16; j++ ) + { + b.append( 21 ); + if( b[j] != 21 ) + { + println("Error at position %1").arg( j ); + println("Raw: %1 (%2)").arg( b.toBitString() ).arg( b.toString() ); + } + } +} + +void numbertest1() +{ + println("-==- Number test -==-"); + + Number a("523"); + Number b("498"); + + println("%1 + %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a + b).toString() ); +} + +int main( int argc, char *argv[] ) +{ + println("CliC"); + + packedtest1(); +// numbertest1(); + + return 0; +} + diff --git a/src/number.cpp b/src/number.cpp new file mode 100644 index 0000000..e64be94 --- /dev/null +++ b/src/number.cpp @@ -0,0 +1,54 @@ +#include "number.h" + +#include + +#define iRadix (10) + +Number::Number( int iOrd ) : + iOrd( iOrd ), + aInt( 4 ) +{ +} + +Number::Number( const Bu::String &sData, int iOrd ) : + iOrd( iOrd ), + aInt( 4 ) +{ + for( int j = sData.getSize()-1; j >= 0; j-- ) + aInt.append( sData[j]-'0' ); +} + +Number::~Number() +{ +} + +Number Number::operator+( const Number &rhs ) const +{ + Number ret( iOrd ); + + int iPlaces = Bu::buMax(rhs.aInt.getSize(), aInt.getSize() )+1; + + int iCarry = 0; + for( int j = 0; j < iPlaces; j++ ) + { + int iRes = iCarry + digit( j ) + rhs.digit( j ); + Bu::println(" Place: %1 + %2 + (%3) = %4"). + arg( digit(j) ).arg( rhs.digit( j ) ).arg( iCarry ) + .arg( iRes ); + ret.aInt.append( (iRes%iRadix) ); + if( iRes < iRadix ) + iCarry = 0; + else + iCarry = iRes/iRadix; + } + + return ret; +} + +int Number::digit( int iOrder ) const +{ + if( iOrder >= aInt.getSize() ) + return 0; + return aInt[iOrder]; +} + diff --git a/src/number.h b/src/number.h new file mode 100644 index 0000000..4ada829 --- /dev/null +++ b/src/number.h @@ -0,0 +1,30 @@ +#ifndef NUMBER_H +#define NUMBER_H + +#include +#include "packedintarray.h" + +class Number +{ +public: + Number( int iOrd=0 ); + Number( const Bu::String &sData, int iOrd=0 ); + virtual ~Number(); + + Number operator+( const Number &rhs ) const; + + operator Bu::String() const + { + return aInt.toString(); + } + + Bu::String toString() const { return aInt.toString(); } + + int digit( int iOrder ) const; + +private: + int iOrd; + PackedIntArray aInt; +}; + +#endif diff --git a/src/packedintarray.cpp b/src/packedintarray.cpp new file mode 100644 index 0000000..817a7ab --- /dev/null +++ b/src/packedintarray.cpp @@ -0,0 +1,137 @@ +#include "packedintarray.h" + +#include + +#define bitsizeof( x ) ((sizeof(x))*8) +#define StoreBits ((bitsizeof(PackedIntArray::Store))) +#define StoreCount( x ) (((x*iBitWidth)/StoreBits)+(((x*iBitWidth)%StoreBits)?1:0)) + +PackedIntArray::PackedIntArray( PackedIntArray::Unit iBitWidth ) : + iBitWidth( iBitWidth ), + aData( NULL ), + iCapacity( 0 ), + iCount( 0 ), + uMask( 0 ) +{ + aData = new Store[4]; + iCapacity = (StoreBits*4)/iBitWidth; + if( iBitWidth < StoreBits ) + { + if( (StoreBits%iBitWidth) == 0 ) + iMaxSpan = 1; + else + { + iMaxSpan = (iBitWidth/StoreBits)+1; + } + } + for( int j = 0; j < iBitWidth; j++ ) + uMask |= (1<>iBit)&uMask; + + for( iBit = StoreBits-iBit; iBit < iBitWidth; ) + { + iStore++; +// Bu::println(" ==> iStore = %2, iBit = %3"). +// arg( idx ).arg( iStore ).arg( iBit ); + ret |= (aData[iStore]&((Store)uMask)>>iBit)< iStore = %2, iBit = %3"). +// arg( idx ).arg( iStore ).arg( iBit ); + aData[iStore] = (aData[iStore]& ~(((Store)uMask)>>iBit)) | + ((Store)i)>>iBit; + iBit += StoreBits; + } +} + +Bu::String PackedIntArray::toBitString() const +{ + Bu::String sRet; + for( int j = iCount*iBitWidth-1; j >= 0; j-- ) + { + sRet += (aData[j/StoreBits] & (1<<(j%StoreBits))) + ? "1" : "0"; + if( j > 0 && j%iBitWidth == 0 ) + sRet += " "; + } + return sRet; +} + +Bu::String PackedIntArray::toString() const +{ + Bu::String sRet; + for( int j = iCount-1; j >= 0; j-- ) + { + sRet += (char)(get(j))+'0'; + } + + return sRet; +} + +void PackedIntArray::checkCapacity() +{ + if( iCount > iCapacity ) + { + Bu::println("!!! Resizing !!!"); + Store *aOldData = aData; + int iNewSize = StoreCount(iCapacity*2); + int iSize = StoreCount(iCapacity); + Bu::println(" %1 => %2 (%3 bit words)").arg( iSize ).arg( iNewSize ) + .arg( StoreBits ); + aData = new Store[iNewSize]; + memset( aData, 0, iNewSize*sizeof(Store) ); + memcpy( aData, aOldData, iSize*sizeof(Store) ); + iCapacity *= 2; + delete[] aOldData; + } +} + diff --git a/src/packedintarray.h b/src/packedintarray.h new file mode 100644 index 0000000..953492b --- /dev/null +++ b/src/packedintarray.h @@ -0,0 +1,36 @@ +#ifndef PACKED_INT_ARRAY_H +#define PACKED_INT_ARRAY_H + +#include + +class PackedIntArray +{ +public: + typedef uint_fast8_t Unit; + PackedIntArray( Unit iBitWidth ); + PackedIntArray( Unit iBitWidth, int iCapacity ); + virtual ~PackedIntArray(); + + void append( Unit i ); + Unit operator[]( int idx ) const { return get( idx ); } + Unit get( int idx ) const; + Unit set( int idx, Unit i ); + int getSize() const { return iCount; } + + Bu::String toBitString() const; + Bu::String toString() const; + +private: + void checkCapacity(); + +private: + typedef uint_fast32_t Store; + Unit iBitWidth; + Store *aData; + int iCapacity; + int iCount; + int iMaxSpan; + Unit uMask; +}; + +#endif -- cgit v1.2.3