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 #ifndef Uint16WithFraction_h
  27 #define Uint16WithFraction_h
  28
  29 #include <wtf/MathExtras.h>
  30
  31 namespace 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.
  40 class Uint16WithFraction {
  41 public:
  42     explicit Uint16WithFraction(double number, uint16_t divideByExponent = 0)
  43     {
  44         ASSERT(number && isfinite(number) && !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
 234 private:
 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