Remove excessive headers from JavaScriptCore
[WebKit-https.git] / Source / JavaScriptCore / runtime / Uint16WithFraction.h
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 // 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.
39 class Uint16WithFraction {
40 public:
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
233 private:
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