icuSources/i18n/double-conversion-bignum.h

   1 // © 2018 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3 //
   4 // From the double-conversion library. Original license:
   5 //
   6 // Copyright 2010 the V8 project authors. All rights reserved.
   7 // Redistribution and use in source and binary forms, with or without
   8 // modification, are permitted provided that the following conditions are
   9 // met:
  10 //
  11 //     * Redistributions of source code must retain the above copyright
  12 //       notice, this list of conditions and the following disclaimer.
  13 //     * Redistributions in binary form must reproduce the above
  14 //       copyright notice, this list of conditions and the following
  15 //       disclaimer in the documentation and/or other materials provided
  16 //       with the distribution.
  17 //     * Neither the name of Google Inc. nor the names of its
  18 //       contributors may be used to endorse or promote products derived
  19 //       from this software without specific prior written permission.
  20 //
  21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32
  33 // ICU PATCH: ifdef around UCONFIG_NO_FORMATTING
  34 #include "unicode/utypes.h"
  35 #if !UCONFIG_NO_FORMATTING
  36
  37 #ifndef DOUBLE_CONVERSION_BIGNUM_H_
  38 #define DOUBLE_CONVERSION_BIGNUM_H_
  39
  40 // ICU PATCH: Customize header file paths for ICU.
  41
  42 #include "double-conversion-utils.h"
  43
  44 // ICU PATCH: Wrap in ICU namespace
  45 U_NAMESPACE_BEGIN
  46
  47 namespace double_conversion {
  48
  49 class Bignum {
  50  public:
  51   // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately.
  52   // This bignum can encode much bigger numbers, since it contains an
  53   // exponent.
  54   static const int kMaxSignificantBits = 3584;
  55
  56   Bignum();
  57   void AssignUInt16(uint16_t value);
  58   void AssignUInt64(uint64_t value);
  59   void AssignBignum(const Bignum& other);
  60
  61   void AssignDecimalString(Vector<const char> value);
  62   void AssignHexString(Vector<const char> value);
  63
  64   void AssignPowerUInt16(uint16_t base, int exponent);
  65
  66   void AddUInt64(uint64_t operand);
  67   void AddBignum(const Bignum& other);
  68   // Precondition: this >= other.
  69   void SubtractBignum(const Bignum& other);
  70
  71   void Square();
  72   void ShiftLeft(int shift_amount);
  73   void MultiplyByUInt32(uint32_t factor);
  74   void MultiplyByUInt64(uint64_t factor);
  75   void MultiplyByPowerOfTen(int exponent);
  76   void Times10() { return MultiplyByUInt32(10); }
  77   // Pseudocode:
  78   //  int result = this / other;
  79   //  this = this % other;
  80   // In the worst case this function is in O(this/other).
  81   uint16_t DivideModuloIntBignum(const Bignum& other);
  82
  83   bool ToHexString(char* buffer, int buffer_size) const;
  84
  85   // Returns
  86   //  -1 if a < b,
  87   //   0 if a == b, and
  88   //  +1 if a > b.
  89   static int Compare(const Bignum& a, const Bignum& b);
  90   static bool Equal(const Bignum& a, const Bignum& b) {
  91     return Compare(a, b) == 0;
  92   }
  93   static bool LessEqual(const Bignum& a, const Bignum& b) {
  94     return Compare(a, b) <= 0;
  95   }
  96   static bool Less(const Bignum& a, const Bignum& b) {
  97     return Compare(a, b) < 0;
  98   }
  99   // Returns Compare(a + b, c);
 100   static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c);
 101   // Returns a + b == c
 102   static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
 103     return PlusCompare(a, b, c) == 0;
 104   }
 105   // Returns a + b <= c
 106   static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
 107     return PlusCompare(a, b, c) <= 0;
 108   }
 109   // Returns a + b < c
 110   static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) {
 111     return PlusCompare(a, b, c) < 0;
 112   }
 113  private:
 114   typedef uint32_t Chunk;
 115   typedef uint64_t DoubleChunk;
 116
 117   static const int kChunkSize = sizeof(Chunk) * 8;
 118   static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8;
 119   // With bigit size of 28 we loose some bits, but a double still fits easily
 120   // into two chunks, and more importantly we can use the Comba multiplication.
 121   static const int kBigitSize = 28;
 122   static const Chunk kBigitMask = (1 << kBigitSize) - 1;
 123   // Every instance allocates kBigitLength chunks on the stack. Bignums cannot
 124   // grow. There are no checks if the stack-allocated space is sufficient.
 125   static const int kBigitCapacity = kMaxSignificantBits / kBigitSize;
 126
 127   void EnsureCapacity(int size) {
 128     if (size > kBigitCapacity) {
 129       UNREACHABLE();
 130     }
 131   }
 132   void Align(const Bignum& other);
 133   void Clamp();
 134   bool IsClamped() const;
 135   void Zero();
 136   // Requires this to have enough capacity (no tests done).
 137   // Updates used_digits_ if necessary.
 138   // shift_amount must be < kBigitSize.
 139   void BigitsShiftLeft(int shift_amount);
 140   // BigitLength includes the "hidden" digits encoded in the exponent.
 141   int BigitLength() const { return used_digits_ + exponent_; }
 142   Chunk BigitAt(int index) const;
 143   void SubtractTimes(const Bignum& other, int factor);
 144
 145   Chunk bigits_buffer_[kBigitCapacity];
 146   // A vector backed by bigits_buffer_. This way accesses to the array are
 147   // checked for out-of-bounds errors.
 148   Vector<Chunk> bigits_;
 149   int used_digits_;
 150   // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).
 151   int exponent_;
 152
 153   DISALLOW_COPY_AND_ASSIGN(Bignum);
 154 };
 155
 156 }  // namespace double_conversion
 157
 158 // ICU PATCH: Close ICU namespace
 159 U_NAMESPACE_END
 160
 161 #endif  // DOUBLE_CONVERSION_BIGNUM_H_
 162 #endif // ICU PATCH: close #if !UCONFIG_NO_FORMATTING