implemented wxLongLong division - seems to work

git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@5101 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775

diff --git a/include/wx/longlong.h b/include/wx/longlong.h
index 562c1e1de4d1412951bc15e9de650272357d7a11..c8778899ab94f48a363c3aa52a1a8135ed0e3797 100644 (file)
--- a/include/wx/longlong.h
+++ b/include/wx/longlong.h
@@ -25,7 +25,7 @@
 
 #include <limits.h>     // for LONG_MAX
 
 
 #include <limits.h>     // for LONG_MAX
 

-// #define wxUSE_LONGLONG_WX 1 -- for testing (VZ)
+//#define wxUSE_LONGLONG_WX 1 // for testing (VZ)

 
 // ----------------------------------------------------------------------------
 // decide upon which class we will use
 
 // ----------------------------------------------------------------------------
 // decide upon which class we will use


@@ -59,7 +59,7 @@
     // have any 64 bit integer type
     #if !defined(__VISAGECPP__) && \
         !defined(__VISUALC__) && \
     // have any 64 bit integer type
     #if !defined(__VISAGECPP__) && \
         !defined(__VISUALC__) && \

-        !defined(__BORLANDC__
+        !defined(__BORLANDC__)

         #warning "Your compiler does not appear to support 64 bit integers, "\
                  "using emulation class instead."
     #endif // known compilers without long long
         #warning "Your compiler does not appear to support 64 bit integers, "\
                  "using emulation class instead."
     #endif // known compilers without long long

diff --git a/samples/console/console.cpp b/samples/console/console.cpp
index 771db68871bb711c51874fd9307e614b05cedd41..ee96ced5d48c86515d4e6764b0b72d4f0ea01f1b 100644 (file)
--- a/samples/console/console.cpp
+++ b/samples/console/console.cpp
@@ -32,11 +32,11 @@
 //#define TEST_ARRAYS
 //#define TEST_DIR
 //#define TEST_LOG
 //#define TEST_ARRAYS
 //#define TEST_DIR
 //#define TEST_LOG

-#define TEST_LONGLONG
+//#define TEST_LONGLONG

 //#define TEST_MIME
 //#define TEST_STRINGS
 //#define TEST_THREADS
 //#define TEST_MIME
 //#define TEST_STRINGS
 //#define TEST_THREADS

-//#define TEST_TIME
+#define TEST_TIME

 
 // ============================================================================
 // implementation
 
 // ============================================================================
 // implementation


@@ -224,14 +224,16 @@ static void TestSpeed()
 
 static void TestDivision()
 {
 
 static void TestDivision()
 {

+    puts("*** Testing wxLongLong division ***\n");
+

     #define MAKE_LL(x1, x2, x3, x4) wxLongLong((x1 << 16) | x2, (x3 << 16) | x3)
 
     // seed pseudo random generator
     #define MAKE_LL(x1, x2, x3, x4) wxLongLong((x1 << 16) | x2, (x3 << 16) | x3)
 
     // seed pseudo random generator

-    //srand((unsigned)time(NULL));
+    srand((unsigned)time(NULL));

 
     wxLongLong q, r;
     size_t nTested = 0;
 
     wxLongLong q, r;
     size_t nTested = 0;

-    for ( size_t n = 0; n < 10000; n++ )
+    for ( size_t n = 0; n < 100000; n++ )

     {
         // get a random wxLongLong (shifting by 12 the MSB ensures that the
         // multiplication will not overflow)
     {
         // get a random wxLongLong (shifting by 12 the MSB ensures that the
         // multiplication will not overflow)


@@ -242,12 +244,19 @@ static void TestDivision()
         q = ll / l;
         r = ll % l;
 
         q = ll / l;
         r = ll % l;
 

+        // verify the result

         wxASSERT_MSG( ll == q*l + r, "division failure" );
 
         wxASSERT_MSG( ll == q*l + r, "division failure" );
 

+        if ( !(nTested % 1000) )
+        {
+            putchar('.');
+            fflush(stdout);
+        }
+

         nTested++;
     }
 
         nTested++;
     }
 

-    printf("\n*** Tested %u divisions/multiplications: ok\n", nTested);
+    puts(" done!");

 
     #undef MAKE_LL
 }
 
     #undef MAKE_LL
 }

diff --git a/src/common/longlong.cpp b/src/common/longlong.cpp
index bca0d2d1fede0ef6bc56bcbf6b086ec1a8d91413..d1738aff745d0ab3594734eeb3304a69055da45d 100644 (file)
--- a/src/common/longlong.cpp
+++ b/src/common/longlong.cpp
@@ -391,54 +391,128 @@ wxLongLongWx& wxLongLongWx::operator*=(const wxLongLongWx& ll)
 
 // division
 
 
 // division
 

-void wxLongLongWx::Divide(const wxLongLongWx& divisor,
+void wxLongLongWx::Divide(const wxLongLongWx& divisorIn,

                           wxLongLongWx& quotient,
                           wxLongLongWx& remainder) const
 {
                           wxLongLongWx& quotient,
                           wxLongLongWx& remainder) const
 {

-    if ((divisor.m_lo == 0) && (divisor.m_hi == 0))
+    if ((divisorIn.m_lo == 0) && (divisorIn.m_hi == 0))

     {
         // provoke division by zero error and silence the compilers warnings
         // about an expression without effect and unused variable
     {
         // provoke division by zero error and silence the compilers warnings
         // about an expression without effect and unused variable

-        long dummy = divisor.m_lo/divisor.m_hi;
+        long dummy = divisorIn.m_lo/divisorIn.m_hi;

         dummy += 0;
     }
 
     // VZ: I'm writing this in a hurry and it's surely not the fastest way to
     //     do this - any improvements are more than welcome
         dummy += 0;
     }
 
     // VZ: I'm writing this in a hurry and it's surely not the fastest way to
     //     do this - any improvements are more than welcome

+    //
+    //     code inspired by the snippet at
+    //          http://www.bearcave.com/software/divide.htm
+    //
+    //     Copyright notice:
+    //
+    //     Use of this program, for any purpose, is granted the author, Ian
+    //     Kaplan, as long as this copyright notice is included in the source
+    //     code or any source code derived from this program. The user assumes
+    //     all responsibility for using this code. 
+
+    // init everything
+    wxLongLongWx dividend = *this,
+                 divisor = divisorIn;
+
+    quotient = 0l;
+    remainder = 0l;
+
+    // check for some particular cases
+    if ( divisor > dividend )
+    {
+        remainder = dividend;
+
+        return;
+    }

 
 

-    // the algorithm: first find N such that 2^N * divisor is less than us,
-    // then substract divisor from *this - 2^N * divisor as many times as
-    // possible
+    if ( divisor == dividend )
+    {
+        quotient = 1l;
+
+        return;
+    }
+
+    // always do unsigned division and adjust the signs later: in C integer
+    // division, the sign of the remainder is the same as the sign of the
+    // dividend, while the sign of the quotient is the product of the signs of
+    // the dividend and divisor. Of course, we also always have
+    //
+    //      dividend = quotient*divisor + remainder
+    //
+    // with 0 <= abs(remainder) < abs(divisor)
+    bool negRemainder = dividend.m_hi < 0;
+    bool negQuotient = FALSE;   // assume positive
+    if ( dividend.m_hi < 0 )
+    {
+        negQuotient = !negQuotient;
+        dividend = -dividend;
+    }
+    if ( divisor.m_hi < 0 )
+    {
+        negQuotient = !negQuotient;
+        divisor = -divisor;
+    }

 
 

-    wxLongLongWx prev = divisor;
-    remainder = *this;
+    // here: dividend > divisor and both are positibe: do unsigned division
+    size_t nBits = 64u;
+    wxLongLongWx d;

 
 

-    quotient = 1l;
+    #define IS_MSB_SET(ll)  ((ll.m_hi) & (1 << (8*sizeof(long) - 1)))

 
 

-    for ( wxLongLongWx tmp = divisor; tmp < remainder; )
+    while ( remainder < divisor )

     {
     {

-        prev = tmp;
+        remainder <<= 1;
+        if ( IS_MSB_SET(dividend) )
+        {
+            remainder |= 1;
+        }
+
+        d = dividend;
+        dividend <<= 1;

 
 

-        tmp <<= 1;
+        nBits--;
+    }
+
+    // undo the last loop iteration
+    dividend = d;
+    remainder >>= 1;
+    nBits++;

 
 

-        if ( tmp < 0 )
+    for ( size_t i = 0; i < nBits; i++ )
+    {
+        remainder <<= 1;
+        if ( IS_MSB_SET(dividend) )

         {
         {

-            // shifted too far
-            break;
+            remainder |= 1;

         }
 
         }
 

+        wxLongLongWx t = remainder - divisor;
+        dividend <<= 1;

         quotient <<= 1;
         quotient <<= 1;

+        if ( !IS_MSB_SET(t) )
+        {
+            quotient |= 1;
+
+            remainder = t;
+        }

     }
 
     }
 

-    while ( remainder >= prev )
+    // adjust signs
+    if ( negRemainder )

     {
     {

-        remainder -= divisor;
-        quotient++;
+        remainder = -remainder;

     }
 
     }
 

-    // remainder should be in this range at the end
-    wxASSERT_MSG( (0l <= remainder) && (remainder < divisor.Abs()),
-                  _T("logic error in wxLongLong division") );
+    if ( negQuotient )
+    {
+        quotient = -quotient;
+    }

 }
 
 wxLongLongWx wxLongLongWx::operator/(const wxLongLongWx& ll) const
 }
 
 wxLongLongWx wxLongLongWx::operator/(const wxLongLongWx& ll) const