summaryrefslogtreecommitdiff
path: root/src/mongo/util/summation.cpp
blob: d4700a2b3818ca2f68818cb2337d78107b775ef3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
 *    Copyright (C) 2018-present MongoDB, Inc.
 *
 *    This program is free software: you can redistribute it and/or modify
 *    it under the terms of the Server Side Public License, version 1,
 *    as published by MongoDB, Inc.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    Server Side Public License for more details.
 *
 *    You should have received a copy of the Server Side Public License
 *    along with this program. If not, see
 *    <http://www.mongodb.com/licensing/server-side-public-license>.
 *
 *    As a special exception, the copyright holders give permission to link the
 *    code of portions of this program with the OpenSSL library under certain
 *    conditions as described in each individual source file and distribute
 *    linked combinations including the program with the OpenSSL library. You
 *    must comply with the Server Side Public License in all respects for
 *    all of the code used other than as permitted herein. If you modify file(s)
 *    with this exception, you may extend this exception to your version of the
 *    file(s), but you are not obligated to do so. If you do not wish to do so,
 *    delete this exception statement from your version. If you delete this
 *    exception statement from all source files in the program, then also delete
 *    it in the license file.
 */

#include "mongo/platform/basic.h"

#include "summation.h"

#include <cmath>

#include "mongo/util/assert_util.h"

namespace mongo {
void DoubleDoubleSummation::addLong(long long x) {
    // Split 64-bit integers into two doubles, so the sum remains exact.
    int64_t high = x / (1ll << 32) * (1ll << 32);
    int64_t low = x - high;
    dassert(high + low == x && 1.0 * high == high && 1.0 * low == low);
    addDouble(low);
    addDouble(high);
}

/**
 * Returns whether the sum is in range of the 64-bit signed integer long long type.
 */
bool DoubleDoubleSummation::fitsLong() const {
    using limits = std::numeric_limits<long long>;
    // Fast path: if the rounded _sum is strictly between the minimum and maximum long long value,
    // it must be valid. This is the common case. Note that this is correct for NaNs/infinities.
    if (_sum > limits::min() && _sum < limits::max())
        return true;

    // Now check the cases where the _sum equals one of the boundaries, and check the compensation
    // amount to determine to what integer the value would round.

    // If _sum is equal to limits::max() + 1, _addend must cause us to round down to a lower integer
    // and thus be strictly less than -0.5. limits.max() rounds up to limits.max() + 1, as double
    // precision does not have enough precision.
    if (_sum == limits::max())
        return _addend < -0.5;

    // If _sum is equal to limits::min(), _addend must not cause us to round down and thus be
    // greater than or equal to -0.5.
    if (_sum == limits::min())
        return _addend >= -0.5;

    // The sum is out of range, an infinity or a NaN.
    return false;
}

/**
 * Returns result of sum rounded to nearest integer, rounding half-way cases away from zero.
 */
long long DoubleDoubleSummation::getLong() const {
    uassert(ErrorCodes::Overflow, "sum out of range of a 64-bit signed integer", fitsLong());
    if (_sum == std::numeric_limits<long long>::max()) {
        // Can't directly convert, because _sum would overflow a signed 64-bit number.
        dassert(_addend < -0.5 && -_sum == std::numeric_limits<long long>::min());
        return llround(_addend) - std::numeric_limits<long long>::min();
    }
    long long sum = llround(_sum);
    sum += llround((_sum - sum) + _addend);
    return sum;
}
}  // namespace mongo