|
| 1 | +/* |
| 2 | + * Copyright (C) 2024 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 | +/* |
| 27 | + * This is the Math.sumPrecise() polyfill by Kevin Gibbons, ported to C++. Original LICENSE is as follows: |
| 28 | + * |
| 29 | + * BSD 3-Clause License |
| 30 | + * |
| 31 | + * Copyright (c) 2024 Kevin Gibbons |
| 32 | + * |
| 33 | + * Redistribution and use in source and binary forms, with or without modification, |
| 34 | + * are permitted provided that the following conditions are met: |
| 35 | + * |
| 36 | + * 1. Redistributions of source code must retain the above copyright notice, |
| 37 | + * this list of conditions and the following disclaimer. |
| 38 | + * |
| 39 | + * 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions |
| 40 | + * and the following disclaimer in the documentation and/or other materials provided with the distribution. |
| 41 | + * |
| 42 | + * 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse |
| 43 | + * or promote products derived from this software without specific prior written permission. |
| 44 | + * |
| 45 | + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED |
| 46 | + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 47 | + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE |
| 48 | + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| 49 | + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| 50 | + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, |
| 51 | + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN |
| 52 | + * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 53 | + */ |
| 54 | + |
| 55 | +#include "config.h" |
| 56 | +#include <wtf/PreciseSum.h> |
| 57 | + |
| 58 | +#include <cmath> |
| 59 | + |
| 60 | +namespace WTF { |
| 61 | + |
| 62 | +static constexpr double MAX_DOUBLE = 1.79769313486231570815e+308; |
| 63 | +static constexpr double PENULTIMATE_DOUBLE = 1.79769313486231550856e+308; |
| 64 | +static constexpr double MAX_ULP = MAX_DOUBLE - PENULTIMATE_DOUBLE; |
| 65 | +static constexpr double TWO_POW_1023 = 8.98846567431158e+307; |
| 66 | + |
| 67 | +ALWAYS_INLINE std::pair<double, double> twosum(double x, double y) |
| 68 | +{ |
| 69 | + double hi = x + y; |
| 70 | + double lo = y - (hi - x); |
| 71 | + return std::make_pair(hi, lo); |
| 72 | +} |
| 73 | + |
| 74 | +void PreciseSum::add(double x) |
| 75 | +{ |
| 76 | + if (!(!x && std::signbit(x))) |
| 77 | + m_everyValueIsNegativeZero = false; |
| 78 | + |
| 79 | + unsigned actuallyUsedPartials = 0; |
| 80 | + |
| 81 | + for (double y : m_partials) { |
| 82 | + if (std::fabs(x) < std::fabs(y)) |
| 83 | + std::swap(x, y); |
| 84 | + |
| 85 | + auto pair = twosum(x, y); |
| 86 | + if (std::isinf(std::fabs(pair.first))) { |
| 87 | + double sign = pair.first < 0 ? -1 : 1; |
| 88 | + m_overflow += sign; |
| 89 | + |
| 90 | + x = (x - sign * TWO_POW_1023) - sign * TWO_POW_1023; |
| 91 | + if (std::fabs(x) < std::fabs(y)) |
| 92 | + std::swap(x, y); |
| 93 | + |
| 94 | + pair = twosum(x, y); |
| 95 | + } |
| 96 | + |
| 97 | + if (auto lo = pair.second) { |
| 98 | + m_partials[actuallyUsedPartials] = lo; |
| 99 | + ++actuallyUsedPartials; |
| 100 | + } |
| 101 | + |
| 102 | + x = pair.first; |
| 103 | + } |
| 104 | + |
| 105 | + m_partials.shrink(actuallyUsedPartials); |
| 106 | + |
| 107 | + if (x) |
| 108 | + m_partials.append(x); |
| 109 | +} |
| 110 | + |
| 111 | +double PreciseSum::compute() |
| 112 | +{ |
| 113 | + if (m_everyValueIsNegativeZero) |
| 114 | + return -0.0; |
| 115 | + |
| 116 | + int32_t n = m_partials.size() - 1; |
| 117 | + double hi = 0; |
| 118 | + double lo = 0; |
| 119 | + |
| 120 | + if (m_overflow) { |
| 121 | + double next = n >= 0 ? m_partials[n] : 0; |
| 122 | + --n; |
| 123 | + if (std::fabs(m_overflow) > 1 || (m_overflow > 0 && next > 0) || (m_overflow < 0 && next < 0)) |
| 124 | + return m_overflow > 0 ? std::numeric_limits<double>::infinity() : -std::numeric_limits<double>::infinity(); |
| 125 | + |
| 126 | + auto pair = twosum(m_overflow * TWO_POW_1023, next / 2); |
| 127 | + hi = pair.first; |
| 128 | + lo = pair.second * 2; |
| 129 | + |
| 130 | + if (std::isinf(std::fabs(hi * 2))) { |
| 131 | + // silly edge case: rounding to the maximum value |
| 132 | + // MAX_DOUBLE has a 1 in the last place of its significand, so if we subtract exactly half a ULP from 2**1024, the result rounds away from it (i.e. to infinity) under ties-to-even |
| 133 | + // but if the next partial has the opposite sign of the current value, we need to round towards MAX_DOUBLE instead |
| 134 | + // this is the same as the "handle rounding" case below, but there's only one potentially-finite case we need to worry about, so we just hardcode that one |
| 135 | + if (hi > 0) { |
| 136 | + if (hi == TWO_POW_1023 && lo == -(MAX_ULP / 2) && n >= 0 && m_partials[n] < 0) |
| 137 | + return MAX_DOUBLE; |
| 138 | + return std::numeric_limits<double>::infinity(); |
| 139 | + } |
| 140 | + |
| 141 | + if (hi == -TWO_POW_1023 && lo == (MAX_ULP / 2) && n >= 0 && m_partials[n] > 0) |
| 142 | + return -MAX_DOUBLE; |
| 143 | + return -std::numeric_limits<double>::infinity(); |
| 144 | + } |
| 145 | + |
| 146 | + if (lo) { |
| 147 | + m_partials[n + 1] = lo; |
| 148 | + ++n; |
| 149 | + lo = 0; |
| 150 | + } |
| 151 | + |
| 152 | + hi *= 2; |
| 153 | + } |
| 154 | + |
| 155 | + while (n >= 0) { |
| 156 | + double x = hi; |
| 157 | + double y = m_partials[n]; |
| 158 | + --n; |
| 159 | + |
| 160 | + auto pair = twosum(x, y); |
| 161 | + hi = pair.first; |
| 162 | + lo = pair.second; |
| 163 | + |
| 164 | + if (lo) |
| 165 | + break; |
| 166 | + } |
| 167 | + |
| 168 | + // handle rounding |
| 169 | + // when the roundoff error is exactly half of the ULP for the result, we need to check one more partial to know which way to round |
| 170 | + if (n >= 0 && ((lo < 0 && m_partials[n] < 0) || (lo > 0 && m_partials[n] > 0))) { |
| 171 | + double y = lo * 2; |
| 172 | + double x = hi + y; |
| 173 | + double yr = x - hi; |
| 174 | + if (y == yr) |
| 175 | + hi = x; |
| 176 | + } |
| 177 | + |
| 178 | + return hi; |
| 179 | +} |
| 180 | + |
| 181 | +} // namespace WTF |
0 commit comments