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