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