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