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