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
30namespace JSC {
31
32// Would be nice if this was a static const member, but the OS X linker
33// seems to want a symbol in the binary in that case...
34#define oneGreaterThanMaxUInt16 0x10000
35
36// A uint16_t with an infinite precision fraction. Upon overflowing
37// the uint16_t range, this class will clamp to oneGreaterThanMaxUInt16.
38// This is used in converting the fraction part of a number to a string.
39class Uint16WithFraction {
40public:
41 explicit Uint16WithFraction(double number, uint16_t divideByExponent = 0)
42 {
43 ASSERT(number && std::isfinite(number) && !std::signbit(number));
44
45 // Check for values out of uint16_t range.
46 if (number >= oneGreaterThanMaxUInt16) {
47 m_values.append(oneGreaterThanMaxUInt16);
48 m_leadingZeros = 0;
49 return;
50 }
51
52 // Append the units to m_values.
53 double integerPart = floor(number);
54 m_values.append(static_cast<uint32_t>(integerPart));
55
56 bool sign;
57 int32_t exponent;
58 uint64_t mantissa;
59 decomposeDouble(number - integerPart, sign, exponent, mantissa);
60 ASSERT(!sign && exponent < 0);
61 exponent -= divideByExponent;
62
63 int32_t zeroBits = -exponent;
64 --zeroBits;
65
66 // Append the append words for to m_values.
67 while (zeroBits >= 32) {
68 m_values.append(0);
69 zeroBits -= 32;
70 }
71
72 // Left align the 53 bits of the mantissa within 96 bits.
73 uint32_t values[3];
74 values[0] = static_cast<uint32_t>(mantissa >> 21);
75 values[1] = static_cast<uint32_t>(mantissa << 11);
76 values[2] = 0;
77 // Shift based on the remainder of the exponent.
78 if (zeroBits) {
79 values[2] = values[1] << (32 - zeroBits);
80 values[1] = (values[1] >> zeroBits) | (values[0] << (32 - zeroBits));
81 values[0] = (values[0] >> zeroBits);
82 }
83 m_values.append(values[0]);
84 m_values.append(values[1]);
85 m_values.append(values[2]);
86
87 // Canonicalize; remove any trailing zeros.
88 while (m_values.size() > 1 && !m_values.last())
89 m_values.removeLast();
90
91 // Count the number of leading zero, this is useful in optimizing multiplies.
92 m_leadingZeros = 0;
93 while (m_leadingZeros < m_values.size() && !m_values[m_leadingZeros])
94 ++m_leadingZeros;
95 }
96
97 Uint16WithFraction& operator*=(uint16_t multiplier)
98 {
99 ASSERT(checkConsistency());
100
101 // iteratate backwards over the fraction until we reach the leading zeros,
102 // passing the carry from one calculation into the next.
103 uint64_t accumulator = 0;
104 for (size_t i = m_values.size(); i > m_leadingZeros; ) {
105 --i;
106 accumulator += static_cast<uint64_t>(m_values[i]) * static_cast<uint64_t>(multiplier);
107 m_values[i] = static_cast<uint32_t>(accumulator);
108 accumulator >>= 32;
109 }
110
111 if (!m_leadingZeros) {
112 // With a multiplicand and multiplier in the uint16_t range, this cannot carry
113 // (even allowing for the infinity value).
114 ASSERT(!accumulator);
115 // Check for overflow & clamp to 'infinity'.
116 if (m_values[0] >= oneGreaterThanMaxUInt16) {
117 m_values.shrink(1);
118 m_values[0] = oneGreaterThanMaxUInt16;
119 m_leadingZeros = 0;
120 return *this;
121 }
122 } else if (accumulator) {
123 // Check for carry from the last multiply, if so overwrite last leading zero.
124 m_values[--m_leadingZeros] = static_cast<uint32_t>(accumulator);
125 // The limited range of the multiplier should mean that even if we carry into
126 // the units, we don't need to check for overflow of the uint16_t range.
127 ASSERT(m_values[0] < oneGreaterThanMaxUInt16);
128 }
129
130 // Multiplication by an even value may introduce trailing zeros; if so, clean them
131 // up. (Keeping the value in a normalized form makes some of the comparison operations
132 // more efficient).
133 while (m_values.size() > 1 && !m_values.last())
134 m_values.removeLast();
135 ASSERT(checkConsistency());
136 return *this;
137 }
138
139 bool operator<(const Uint16WithFraction& other)
140 {
141 ASSERT(checkConsistency());
142 ASSERT(other.checkConsistency());
143
144 // Iterate over the common lengths of arrays.
145 size_t minSize = std::min(m_values.size(), other.m_values.size());
146 for (size_t index = 0; index < minSize; ++index) {
147 // If we find a value that is not equal, compare and return.
148 uint32_t fromThis = m_values[index];
149 uint32_t fromOther = other.m_values[index];
150 if (fromThis != fromOther)
151 return fromThis < fromOther;
152 }
153 // If these numbers have the same lengths, they are equal,
154 // otherwise which ever number has a longer fraction in larger.
155 return other.m_values.size() > minSize;
156 }
157
158 // Return the floor (non-fractional portion) of the number, clearing this to zero,
159 // leaving the fractional part unchanged.
160 uint32_t floorAndSubtract()
161 {
162 // 'floor' is simple the integer portion of the value.
163 uint32_t floor = m_values[0];
164
165 // If floor is non-zero,
166 if (floor) {
167 m_values[0] = 0;
168 m_leadingZeros = 1;
169 while (m_leadingZeros < m_values.size() && !m_values[m_leadingZeros])
170 ++m_leadingZeros;
171 }
172
173 return floor;
174 }
175
176 // Compare this value to 0.5, returns -1 for less than, 0 for equal, 1 for greater.
177 int comparePoint5()
178 {
179 ASSERT(checkConsistency());
180 // If units != 0, this is greater than 0.5.
181 if (m_values[0])
182 return 1;
183 // If size == 1 this value is 0, hence < 0.5.
184 if (m_values.size() == 1)
185 return -1;
186 // Compare to 0.5.
187 if (m_values[1] > 0x80000000ul)
188 return 1;
189 if (m_values[1] < 0x80000000ul)
190 return -1;
191 // Check for more words - since normalized numbers have no trailing zeros, if
192 // there are more that two digits we can assume at least one more is non-zero,
193 // and hence the value is > 0.5.
194 return m_values.size() > 2 ? 1 : 0;
195 }
196
197 // Return true if the sum of this plus addend would be greater than 1.
198 bool sumGreaterThanOne(const Uint16WithFraction& addend)
199 {
200 ASSERT(checkConsistency());
201 ASSERT(addend.checkConsistency());
202
203 // First, sum the units. If the result is greater than one, return true.
204 // If equal to one, return true if either number has a fractional part.
205 uint32_t sum = m_values[0] + addend.m_values[0];
206 if (sum)
207 return sum > 1 || std::max(m_values.size(), addend.m_values.size()) > 1;
208
209 // We could still produce a result greater than zero if addition of the next
210 // word from the fraction were to carry, leaving a result > 0.
211
212 // Iterate over the common lengths of arrays.
213 size_t minSize = std::min(m_values.size(), addend.m_values.size());
214 for (size_t index = 1; index < minSize; ++index) {
215 // Sum the next word from this & the addend.
216 uint32_t fromThis = m_values[index];
217 uint32_t fromAddend = addend.m_values[index];
218 sum = fromThis + fromAddend;
219
220 // Check for overflow. If so, check whether the remaining result is non-zero,
221 // or if there are any further words in the fraction.
222 if (sum < fromThis)
223 return sum || (index + 1) < std::max(m_values.size(), addend.m_values.size());
224
225 // If the sum is uint32_t max, then we would carry a 1 if addition of the next
226 // digits in the number were to overflow.
227 if (sum != 0xFFFFFFFF)
228 return false;
229 }
230 return false;
231 }
232
233private:
234 bool checkConsistency() const
235 {
236 // All values should have at least one value.
237 return (m_values.size())
238 // The units value must be a uint16_t, or the value is the overflow value.
239 && (m_values[0] < oneGreaterThanMaxUInt16 || (m_values[0] == oneGreaterThanMaxUInt16 && m_values.size() == 1))
240 // There should be no trailing zeros (unless this value is zero!).
241 && (m_values.last() || m_values.size() == 1);
242 }
243
244 // The internal storage of the number. This vector is always at least one entry in size,
245 // with the first entry holding the portion of the number greater than zero. The first
246 // value always hold a value in the uint16_t range, or holds the value oneGreaterThanMaxUInt16 to
247 // indicate the value has overflowed to >= 0x10000. If the units value is oneGreaterThanMaxUInt16,
248 // there can be no fraction (size must be 1).
249 //
250 // Subsequent values in the array represent portions of the fractional part of this number.
251 // The total value of the number is the sum of (m_values[i] / pow(2^32, i)), for each i
252 // in the array. The vector should contain no trailing zeros, except for the value '0',
253 // represented by a vector contianing a single zero value. These constraints are checked
254 // by 'checkConsistency()', above.
255 //
256 // The inline capacity of the vector is set to be able to contain any IEEE double (1 for
257 // the units column, 32 for zeros introduced due to an exponent up to -3FE, and 2 for
258 // bits taken from the mantissa).
259 Vector<uint32_t, 36> m_values;
260
261 // Cache a count of the number of leading zeros in m_values. We can use this to optimize
262 // methods that would otherwise need visit all words in the vector, e.g. multiplication.
263 size_t m_leadingZeros;
264};
265
266} // namespace JSC
267