1  /*
  2   * Copyright (C) 2011 Apple Inc. All rights reserved.
  3   *
  4   * Redistribution and use in source and binary forms, with or without
  5   * modification, are permitted provided that the following conditions
  6   * are met:
  7   * 1. Redistributions of source code must retain the above copyright
  8   *    notice, this list of conditions and the following disclaimer.
  9   * 2. Redistributions in binary form must reproduce the above copyright
 10   *    notice, this list of conditions and the following disclaimer in the
 11   *    documentation and/or other materials provided with the distribution.
 12   *
 13   * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 14   * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 15   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 16   * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 17   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 18   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 19   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 20   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 21   * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 22   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 23   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 24   */
 25  
 26  #pragma once
 27  
 28  #include <wtf/MathExtras.h>
 29  
 30  namespace JSC {
 31  
 32  // This is used in converting the integer part of a number to a string.
 33  class BigInteger {
 34  public:
 35      BigInteger(double number)
 36      {
 37          ASSERT(std::isfinite(number) && !std::signbit(number));
 38          ASSERT(number == floor(number));
 39  
 40          bool sign;
 41          int32_t exponent;
 42          uint64_t mantissa;
 43          decomposeDouble(number, sign, exponent, mantissa);
 44          ASSERT(!sign && exponent >= 0);
 45  
 46          int32_t zeroBits = exponent - 52;
 47  
 48          if (zeroBits < 0) {
 49              mantissa >>= -zeroBits;
 50              zeroBits = 0;
 51          }
 52  
 53          while (zeroBits >= 32) {
 54              m_values.append(0);
 55              zeroBits -= 32;
 56          }
 57  
 58          // Left align the 53 bits of the mantissa within 96 bits.
 59          uint32_t values[3];
 60          values[0] = static_cast<uint32_t>(mantissa);
 61          values[1] = static_cast<uint32_t>(mantissa >> 32);
 62          values[2] = 0;
 63          // Shift based on the remainder of the exponent.
 64          if (zeroBits) {
 65              values[2] = values[1] >> (32 - zeroBits);
 66              values[1] = (values[1] << zeroBits) | (values[0] >> (32 - zeroBits));
 67              values[0] = (values[0] << zeroBits);
 68          }
 69          m_values.append(values[0]);
 70          m_values.append(values[1]);
 71          m_values.append(values[2]);
 72  
 73          // Canonicalize; remove all trailing zeros.
 74          while (m_values.size() && !m_values.last())
 75              m_values.removeLast();
 76      }
 77  
 78      uint32_t divide(uint32_t divisor)
 79      {
 80          uint32_t carry = 0;
 81  
 82          for (size_t i = m_values.size(); i; ) {
 83              --i;
 84              uint64_t dividend = (static_cast<uint64_t>(carry) << 32) + static_cast<uint64_t>(m_values[i]);
 85  
 86              uint64_t result = dividend / static_cast<uint64_t>(divisor);
 87              ASSERT(result == static_cast<uint32_t>(result));
 88              uint64_t remainder = dividend % static_cast<uint64_t>(divisor);
 89              ASSERT(remainder == static_cast<uint32_t>(remainder));
 90              
 91              m_values[i] = static_cast<uint32_t>(result);
 92              carry = static_cast<uint32_t>(remainder);
 93          }
 94  
 95          // Canonicalize; remove all trailing zeros.
 96          while (m_values.size() && !m_values.last())
 97              m_values.removeLast();
 98  
 99          return carry;
100      }
101  
102      bool operator!() { return !m_values.size(); }
103  
104  private:
105      Vector<uint32_t, 36> m_values;
106  };
107  
108  } // namespace JSC