1 /*
2  * Copyright (C) 2022 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <atomic>
20 #include <cstdint>
21 #include <tuple>
22 #include <type_traits>
23 
24 #include <log/log.h>
25 
26 namespace android::mediautils {
27 
28 // The goal of this class is to detect and accumulate wraparound occurrences on a
29 // lower sized integer.
30 
31 // This class assumes that the underlying unsigned type is either incremented or
32 // decremented by at most the underlying signed type between any two subsequent
33 // polls (or construction). This is well-defined as the modular nature of
34 // unsigned arithmetic ensures that every new value maps 1-1 to an
35 // increment/decrement over the same sized signed type. It also ensures that our
36 // counter will be equivalent mod the size of the integer even if the underlying
37 // type is modified outside of this range.
38 //
39 // For convenience, this class is thread compatible. Additionally, it is safe
40 // as long as there is only one writer.
41 template <typename Integral = uint32_t, typename AccumulatingType = uint64_t>
42 class ExtendedAccumulator {
43     static_assert(sizeof(Integral) < sizeof(AccumulatingType),
44                   "Accumulating type should be larger than underlying type");
45     static_assert(std::is_integral_v<Integral> && std::is_unsigned_v<Integral>,
46                   "Wraparound behavior is only well-defiend for unsigned ints");
47     static_assert(std::is_integral_v<AccumulatingType>);
48 
49   public:
50     enum class Wrap {
51         Normal = 0,
52         Underflow = 1,
53         Overflow = 2,
54     };
55 
56     using UnsignedInt = Integral;
57     using SignedInt = std::make_signed_t<UnsignedInt>;
58 
mAccumulated(initial)59     explicit ExtendedAccumulator(AccumulatingType initial = 0) : mAccumulated(initial) {}
60 
61     // Returns a pair of the calculated change on the accumulating value, and a
62     // Wrap type representing the type of wraparound (if any) which occurred.
poll(UnsignedInt value)63     std::pair<SignedInt, Wrap> poll(UnsignedInt value) {
64         auto acc = mAccumulated.load(std::memory_order_relaxed);
65         const auto bottom_bits = static_cast<UnsignedInt>(acc);
66         std::pair<SignedInt, Wrap> res = {0, Wrap::Normal};
67         const bool overflow = __builtin_sub_overflow(value, bottom_bits, &res.first);
68 
69         if (overflow) {
70             res.second = (res.first > 0) ? Wrap::Overflow : Wrap::Underflow;
71         }
72 
73         const bool acc_overflow = __builtin_add_overflow(acc, res.first, &acc);
74         // If our *accumulating* type overflows or underflows (depending on its
75         // signedness), we should abort.
76         if (acc_overflow) LOG_ALWAYS_FATAL("Unexpected overflow/underflow in %s", __func__);
77 
78         mAccumulated.store(acc, std::memory_order_relaxed);
79         return res;
80     }
81 
getValue()82     AccumulatingType getValue() const { return mAccumulated.load(std::memory_order_relaxed); }
83 
84   private:
85     // Invariant - the bottom underlying bits of accumulated are the same as the
86     // last value provided to poll.
87     std::atomic<AccumulatingType> mAccumulated;
88 };
89 
90 }  // namespace android::mediautils
91