← Back to branch summary

~ubuntu-branches/ubuntu/wily/mozjs17/wily

« back to all changes in this revision

Viewing changes to mfbt/double-conversion/bignum.h

  • Committer: Package Import Robot
  • Author(s): Rico Tzschichholz
  • Date: 2013-05-25 12:24:23 UTC
  • Revision ID: package-import@ubuntu.com-20130525122423-zmxucrhtensw90xy
Tags: upstream-17.0.0
Import upstream version 17.0.0

Show diffs side-by-side

added added

removed removed

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