src/common/longlong.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        wx/longlong.cpp
   3 // Purpose:     implementation of wxLongLongNative
   4 // Author:      Jeffrey C. Ollie <jeff@ollie.clive.ia.us>, Vadim Zeitlin
   5 // Remarks:     this class is not public in wxWindows 2.0! It is intentionally
   6 //              not documented and is for private use only.
   7 // Modified by:
   8 // Created:     10.02.99
   9 // RCS-ID:      $Id$
  10 // Copyright:   (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
  11 // Licence:     wxWindows license
  12 /////////////////////////////////////////////////////////////////////////////
  13
  14 // ============================================================================
  15 // headers
  16 // ============================================================================
  17
  18 #ifdef __GNUG__
  19     #pragma implementation "longlong.h"
  20 #endif
  21
  22 #include "wx/wxprec.h"
  23
  24 #ifdef __BORLANDC__
  25     #pragma hdrstop
  26 #endif
  27
  28 #if wxUSE_LONGLONG
  29 #include "wx/longlong.h"
  30
  31 #if defined(__MWERKS__) && defined(__WXMSW__)
  32 #include <string.h>     // for memset()
  33 #else
  34 #include <memory.h>     // for memset()
  35 #endif
  36
  37 #include <math.h>       // for fabs()
  38
  39 // ============================================================================
  40 // implementation
  41 // ============================================================================
  42
  43 #if wxUSE_LONGLONG_NATIVE
  44
  45 // ----------------------------------------------------------------------------
  46 // misc
  47 // ----------------------------------------------------------------------------
  48
  49 void *wxLongLongNative::asArray() const
  50 {
  51     static unsigned char temp[8];
  52
  53     temp[0] = (m_ll >> 56) & 0xFF;
  54     temp[1] = (m_ll >> 48) & 0xFF;
  55     temp[2] = (m_ll >> 40) & 0xFF;
  56     temp[3] = (m_ll >> 32) & 0xFF;
  57     temp[4] = (m_ll >> 24) & 0xFF;
  58     temp[5] = (m_ll >> 16) & 0xFF;
  59     temp[6] = (m_ll >> 8)  & 0xFF;
  60     temp[7] = (m_ll >> 0)  & 0xFF;
  61
  62     return temp;
  63 }
  64
  65 #endif // wxUSE_LONGLONG_NATIVE
  66
  67 // ============================================================================
  68 // wxLongLongWx: emulation of 'long long' using 2 longs
  69 // ============================================================================
  70
  71 #if wxUSE_LONGLONG_WX
  72
  73 // assignment
  74 wxLongLongWx& wxLongLongWx::Assign(double d)
  75 {
  76     bool positive = d >= 0;
  77     d = fabs(d);
  78     if ( d <= ULONG_MAX )
  79     {
  80         m_hi = 0;
  81         m_lo = (long)d;
  82     }
  83     else
  84     {
  85         m_hi = (unsigned long)(d / (1.0 + (double)ULONG_MAX));
  86         m_lo = (unsigned long)(d - ((double)m_hi * (1.0 + (double)ULONG_MAX)));
  87     }
  88
  89 #ifdef wxLONGLONG_TEST_MODE
  90     m_ll = (wxLongLong_t)d;
  91
  92     Check();
  93 #endif // wxLONGLONG_TEST_MODE
  94
  95     if ( !positive )
  96         Negate();
  97
  98     return *this;
  99 }
 100
 101 wxLongLongWx wxLongLongWx::operator<<(int shift) const
 102 {
 103     wxLongLongWx ll(*this);
 104     ll <<= shift;
 105
 106     return ll;
 107 }
 108
 109 wxLongLongWx& wxLongLongWx::operator<<=(int shift)
 110 {
 111     if (shift != 0)
 112     {
 113         if (shift < 32)
 114         {
 115             m_hi <<= shift;
 116             m_hi |= m_lo >> (32 - shift);
 117             m_lo <<= shift;
 118         }
 119         else
 120         {
 121             m_hi = m_lo << (shift - 32);
 122             m_lo = 0;
 123         }
 124     }
 125
 126 #ifdef wxLONGLONG_TEST_MODE
 127     m_ll <<= shift;
 128
 129     Check();
 130 #endif // wxLONGLONG_TEST_MODE
 131
 132     return *this;
 133 }
 134
 135 wxLongLongWx wxLongLongWx::operator>>(int shift) const
 136 {
 137     wxLongLongWx ll(*this);
 138     ll >>= shift;
 139
 140     return ll;
 141 }
 142
 143 wxLongLongWx& wxLongLongWx::operator>>=(int shift)
 144 {
 145     if (shift != 0)
 146     {
 147         if (shift < 32)
 148         {
 149             m_lo >>= shift;
 150             m_lo |= m_hi << (32 - shift);
 151             m_hi >>= shift;
 152         }
 153         else
 154         {
 155             m_lo = m_hi >> (shift - 32);
 156             m_hi = (m_hi < 0 ? -1L : 0);
 157         }
 158     }
 159
 160 #ifdef wxLONGLONG_TEST_MODE
 161     m_ll >>= shift;
 162
 163     Check();
 164 #endif // wxLONGLONG_TEST_MODE
 165
 166     return *this;
 167 }
 168
 169 wxLongLongWx wxLongLongWx::operator+(const wxLongLongWx& ll) const
 170 {
 171     wxLongLongWx res(*this);
 172     res += ll;
 173
 174     return res;
 175 }
 176
 177 wxLongLongWx wxLongLongWx::operator+(long l) const
 178 {
 179     wxLongLongWx res(*this);
 180     res += l;
 181
 182     return res;
 183 }
 184
 185 wxLongLongWx& wxLongLongWx::operator+=(const wxLongLongWx& ll)
 186 {
 187     unsigned long previous = m_lo;
 188
 189     m_lo += ll.m_lo;
 190     m_hi += ll.m_hi;
 191
 192     if ((m_lo < previous) || (m_lo < ll.m_lo))
 193         m_hi++;
 194
 195 #ifdef wxLONGLONG_TEST_MODE
 196     m_ll += ll.m_ll;
 197
 198     Check();
 199 #endif // wxLONGLONG_TEST_MODE
 200
 201     return *this;
 202 }
 203
 204 wxLongLongWx& wxLongLongWx::operator+=(long l)
 205 {
 206     unsigned long previous = m_lo;
 207
 208     m_lo += l;
 209     if (l < 0)
 210         m_hi += -1l;
 211
 212     if ((m_lo < previous) || (m_lo < (unsigned long)l))
 213         m_hi++;
 214
 215 #ifdef wxLONGLONG_TEST_MODE
 216     m_ll += l;
 217
 218     Check();
 219 #endif // wxLONGLONG_TEST_MODE
 220
 221     return *this;
 222 }
 223
 224 // pre increment
 225 wxLongLongWx& wxLongLongWx::operator++()
 226 {
 227     m_lo++;
 228     if (m_lo == 0)
 229         m_hi++;
 230
 231 #ifdef wxLONGLONG_TEST_MODE
 232     m_ll++;
 233
 234     Check();
 235 #endif // wxLONGLONG_TEST_MODE
 236
 237     return *this;
 238 }
 239
 240 // negation
 241 wxLongLongWx wxLongLongWx::operator-() const
 242 {
 243     wxLongLongWx res(*this);
 244     res.Negate();
 245
 246     return res;
 247 }
 248
 249 wxLongLongWx& wxLongLongWx::Negate()
 250 {
 251     m_hi = ~m_hi;
 252     m_lo = ~m_lo;
 253
 254     m_lo++;
 255     if ( m_lo == 0 )
 256         m_hi++;
 257
 258 #ifdef wxLONGLONG_TEST_MODE
 259     m_ll = -m_ll;
 260
 261     Check();
 262 #endif // wxLONGLONG_TEST_MODE
 263
 264     return *this;
 265 }
 266
 267 // subtraction
 268
 269 wxLongLongWx wxLongLongWx::operator-(const wxLongLongWx& ll) const
 270 {
 271     wxLongLongWx res(*this);
 272     res -= ll;
 273
 274     return res;
 275 }
 276
 277 wxLongLongWx& wxLongLongWx::operator-=(const wxLongLongWx& ll)
 278 {
 279     unsigned long previous = m_lo;
 280
 281     m_lo -= ll.m_lo;
 282     m_hi -= ll.m_hi;
 283
 284     if (previous < ll.m_lo)
 285         m_hi--;
 286
 287 #ifdef wxLONGLONG_TEST_MODE
 288     m_ll -= ll.m_ll;
 289
 290     Check();
 291 #endif // wxLONGLONG_TEST_MODE
 292
 293     return *this;
 294 }
 295
 296 // pre decrement
 297 wxLongLongWx& wxLongLongWx::operator--()
 298 {
 299     m_lo--;
 300     if (m_lo == 0xFFFFFFFF)
 301         m_hi--;
 302
 303 #ifdef wxLONGLONG_TEST_MODE
 304     m_ll--;
 305
 306     Check();
 307 #endif // wxLONGLONG_TEST_MODE
 308
 309     return *this;
 310 }
 311
 312 // comparison operators
 313
 314 bool wxLongLongWx::operator<(const wxLongLongWx& ll) const
 315 {
 316     if ( m_hi < ll.m_hi )
 317         return TRUE;
 318     else if ( m_hi == ll.m_hi )
 319         return m_lo < ll.m_lo;
 320     else
 321         return FALSE;
 322 }
 323
 324 bool wxLongLongWx::operator>(const wxLongLongWx& ll) const
 325 {
 326     if ( m_hi > ll.m_hi )
 327         return TRUE;
 328     else if ( m_hi == ll.m_hi )
 329         return m_lo > ll.m_lo;
 330     else
 331         return FALSE;
 332 }
 333
 334 // bitwise operators
 335
 336 wxLongLongWx wxLongLongWx::operator&(const wxLongLongWx& ll) const
 337 {
 338     return wxLongLongWx(m_hi & ll.m_hi, m_lo & ll.m_lo);
 339 }
 340
 341 wxLongLongWx wxLongLongWx::operator|(const wxLongLongWx& ll) const
 342 {
 343     return wxLongLongWx(m_hi | ll.m_hi, m_lo | ll.m_lo);
 344 }
 345
 346 wxLongLongWx wxLongLongWx::operator^(const wxLongLongWx& ll) const
 347 {
 348     return wxLongLongWx(m_hi ^ ll.m_hi, m_lo ^ ll.m_lo);
 349 }
 350
 351 wxLongLongWx& wxLongLongWx::operator&=(const wxLongLongWx& ll)
 352 {
 353     m_lo &= ll.m_lo;
 354     m_hi &= ll.m_hi;
 355
 356 #ifdef wxLONGLONG_TEST_MODE
 357     m_ll &= ll.m_ll;
 358
 359     Check();
 360 #endif // wxLONGLONG_TEST_MODE
 361
 362     return *this;
 363 }
 364
 365 wxLongLongWx& wxLongLongWx::operator|=(const wxLongLongWx& ll)
 366 {
 367     m_lo |= ll.m_lo;
 368     m_hi |= ll.m_hi;
 369
 370 #ifdef wxLONGLONG_TEST_MODE
 371     m_ll |= ll.m_ll;
 372
 373     Check();
 374 #endif // wxLONGLONG_TEST_MODE
 375
 376     return *this;
 377 }
 378
 379 wxLongLongWx& wxLongLongWx::operator^=(const wxLongLongWx& ll)
 380 {
 381     m_lo ^= ll.m_lo;
 382     m_hi ^= ll.m_hi;
 383
 384 #ifdef wxLONGLONG_TEST_MODE
 385     m_ll ^= ll.m_ll;
 386
 387     Check();
 388 #endif // wxLONGLONG_TEST_MODE
 389
 390     return *this;
 391 }
 392
 393 wxLongLongWx wxLongLongWx::operator~() const
 394 {
 395     return wxLongLongWx(~m_hi, ~m_lo);
 396 }
 397
 398 // multiplication
 399
 400 wxLongLongWx wxLongLongWx::operator*(const wxLongLongWx& ll) const
 401 {
 402     wxLongLongWx res(*this);
 403     res *= ll;
 404
 405     return res;
 406 }
 407
 408 wxLongLongWx& wxLongLongWx::operator*=(const wxLongLongWx& ll)
 409 {
 410     wxLongLongWx t(m_hi, m_lo);
 411     wxLongLongWx q(ll.m_hi, ll.m_lo);
 412
 413     m_hi = m_lo = 0;
 414
 415 #ifdef wxLONGLONG_TEST_MODE
 416     wxLongLong_t llOld = m_ll;
 417     m_ll = 0;
 418 #endif // wxLONGLONG_TEST_MODE
 419
 420     int counter = 0;
 421     do
 422     {
 423         if ((q.m_lo & 1) != 0)
 424             *this += t;
 425         q >>= 1;
 426         t <<= 1;
 427         counter++;
 428     }
 429     while ((counter < 64) && ((q.m_hi != 0) || (q.m_lo != 0)));
 430
 431 #ifdef wxLONGLONG_TEST_MODE
 432     m_ll = llOld * ll.m_ll;
 433
 434     Check();
 435 #endif // wxLONGLONG_TEST_MODE
 436
 437     return *this;
 438 }
 439
 440 // division
 441
 442 void wxLongLongWx::Divide(const wxLongLongWx& divisorIn,
 443                           wxLongLongWx& quotient,
 444                           wxLongLongWx& remainder) const
 445 {
 446     if ((divisorIn.m_lo == 0) && (divisorIn.m_hi == 0))
 447     {
 448         // provoke division by zero error and silence the compilers warnings
 449         // about an expression without effect and unused variable
 450         long dummy = divisorIn.m_lo/divisorIn.m_hi;
 451         dummy += 0;
 452     }
 453
 454     // VZ: I'm writing this in a hurry and it's surely not the fastest way to
 455     //     do this - any improvements are more than welcome
 456     //
 457     //     code inspired by the snippet at
 458     //          http://www.bearcave.com/software/divide.htm
 459     //
 460     //     Copyright notice:
 461     //
 462     //     Use of this program, for any purpose, is granted the author, Ian
 463     //     Kaplan, as long as this copyright notice is included in the source
 464     //     code or any source code derived from this program. The user assumes
 465     //     all responsibility for using this code.
 466
 467     // init everything
 468     wxLongLongWx dividend = *this,
 469                  divisor = divisorIn;
 470
 471     quotient = 0l;
 472     remainder = 0l;
 473
 474     // always do unsigned division and adjust the signs later: in C integer
 475     // division, the sign of the remainder is the same as the sign of the
 476     // dividend, while the sign of the quotient is the product of the signs of
 477     // the dividend and divisor. Of course, we also always have
 478     //
 479     //      dividend = quotient*divisor + remainder
 480     //
 481     // with 0 <= abs(remainder) < abs(divisor)
 482     bool negRemainder = dividend.m_hi < 0;
 483     bool negQuotient = FALSE;   // assume positive
 484     if ( dividend.m_hi < 0 )
 485     {
 486         negQuotient = !negQuotient;
 487         dividend = -dividend;
 488     }
 489     if ( divisor.m_hi < 0 )
 490     {
 491         negQuotient = !negQuotient;
 492         divisor = -divisor;
 493     }
 494
 495     // check for some particular cases
 496     if ( divisor > dividend )
 497     {
 498         remainder = dividend;
 499     }
 500     else if ( divisor == dividend )
 501     {
 502         quotient = 1l;
 503     }
 504     else
 505     {
 506         // here: dividend > divisor and both are positibe: do unsigned division
 507         size_t nBits = 64u;
 508         wxLongLongWx d;
 509
 510         #define IS_MSB_SET(ll)  ((ll.m_hi) & (1 << (8*sizeof(long) - 1)))
 511
 512         while ( remainder < divisor )
 513         {
 514             remainder <<= 1;
 515             if ( IS_MSB_SET(dividend) )
 516             {
 517                 remainder |= 1;
 518             }
 519
 520             d = dividend;
 521             dividend <<= 1;
 522
 523             nBits--;
 524         }
 525
 526         // undo the last loop iteration
 527         dividend = d;
 528         remainder >>= 1;
 529         nBits++;
 530
 531         for ( size_t i = 0; i < nBits; i++ )
 532         {
 533             remainder <<= 1;
 534             if ( IS_MSB_SET(dividend) )
 535             {
 536                 remainder |= 1;
 537             }
 538
 539             wxLongLongWx t = remainder - divisor;
 540             dividend <<= 1;
 541             quotient <<= 1;
 542             if ( !IS_MSB_SET(t) )
 543             {
 544                 quotient |= 1;
 545
 546                 remainder = t;
 547             }
 548         }
 549     }
 550
 551     // adjust signs
 552     if ( negRemainder )
 553     {
 554         remainder = -remainder;
 555     }
 556
 557     if ( negQuotient )
 558     {
 559         quotient = -quotient;
 560     }
 561 }
 562
 563 wxLongLongWx wxLongLongWx::operator/(const wxLongLongWx& ll) const
 564 {
 565     wxLongLongWx quotient, remainder;
 566
 567     Divide(ll, quotient, remainder);
 568
 569     return quotient;
 570 }
 571
 572 wxLongLongWx& wxLongLongWx::operator/=(const wxLongLongWx& ll)
 573 {
 574     wxLongLongWx quotient, remainder;
 575
 576     Divide(ll, quotient, remainder);
 577
 578     *this = quotient;
 579
 580     return *this;
 581 }
 582
 583 wxLongLongWx wxLongLongWx::operator%(const wxLongLongWx& ll) const
 584 {
 585     wxLongLongWx quotient, remainder;
 586
 587     Divide(ll, quotient, remainder);
 588
 589     return remainder;
 590 }
 591
 592 // ----------------------------------------------------------------------------
 593 // misc
 594 // ----------------------------------------------------------------------------
 595
 596 // temporary - just for testing
 597 void *wxLongLongWx::asArray(void) const
 598 {
 599     static unsigned char temp[8];
 600
 601     temp[0] = (char)((m_hi >> 24) & 0xFF);
 602     temp[1] = (char)((m_hi >> 16) & 0xFF);
 603     temp[2] = (char)((m_hi >> 8)  & 0xFF);
 604     temp[3] = (char)((m_hi >> 0)  & 0xFF);
 605     temp[4] = (char)((m_lo >> 24) & 0xFF);
 606     temp[5] = (char)((m_lo >> 16) & 0xFF);
 607     temp[6] = (char)((m_lo >> 8)  & 0xFF);
 608     temp[7] = (char)((m_lo >> 0)  & 0xFF);
 609
 610     return temp;
 611 }
 612
 613 #endif // wxUSE_LONGLONG_WX
 614
 615 wxString
 616 #if wxUSE_LONGLONG_NATIVE
 617 wxLongLongNative::ToString() const
 618 #else
 619 wxLongLongWx::ToString() const
 620 #endif
 621 {
 622     // TODO: this is awfully inefficient, anything better?
 623     wxString result;
 624
 625     wxLongLong ll = *this;
 626
 627     bool neg;
 628     if ( ll < 0 )
 629     {
 630         ll.Negate();
 631         neg = TRUE;
 632     }
 633     else
 634     {
 635         neg = FALSE;
 636     }
 637
 638     while ( ll != 0 )
 639     {
 640         result.Prepend((wxChar)(_T('0') + (ll % 10).ToLong()));
 641         ll /= 10;
 642     }
 643
 644     if ( result.empty() )
 645         result = _T('0');
 646     else if ( neg )
 647         result.Prepend(_T('-'));
 648
 649     return result;
 650 }
 651
 652 #if wxUSE_STD_IOSTREAM
 653
 654 // input/output
 655 wxSTD ostream& operator<< (wxSTD ostream& o, const wxLongLong& ll)
 656 {
 657     return o << ll.ToString();
 658 }
 659
 660 #endif // wxUSE_STD_IOSTREAM
 661
 662 #endif // wxUSE_LONGLONG