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