1/*
2 * Copyright 2015 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#ifndef ANDROID_MODULO_H
18#define ANDROID_MODULO_H
19
20namespace android {
21
22// Modulo class is used for intentionally wrapping variables such as
23// counters and timers.
24//
25// It may also be used for variables whose computation depends on the
26// associativity of addition or subtraction.
27//
28// Features:
29// 1) Modulo checks type sizes before performing operations to ensure
30//    that the wrap points match. This is critical for safe modular arithmetic.
31// 2) Modulo returns Modulo types from arithmetic operations, thereby
32//    avoiding unintentional use in a non-modular computation.  A Modulo
33//    type is converted to its base non-Modulo type through the value() function.
34// 3) Modulo separates out overflowable types from non-overflowable types.
35//    A signed overflow is technically undefined in C and C++.
36//    Modulo types do not participate in sanitization.
37// 4) Modulo comparisons are based on signed differences to account for wrap;
38//    this is not the same as the direct comparison of values.
39// 5) Safe use of binary arithmetic operations relies on conversions of
40//    signed operands to unsigned operands (which are modular arithmetic safe).
41//    Conversions which are implementation-defined are assumed to use 2's complement
42//    representation. (See A, B, C, D from the ISO/IEC FDIS 14882
43//    Information technology — Programming languages — C++).
44//
45// A: ISO/IEC 14882:2011(E) p84 section 4.7 Integral conversions
46// (2) If the destination type is unsigned, the resulting value is the least unsigned
47// integer congruent to the source integer (modulo 2^n where n is the number of bits
48// used to represent the unsigned type). [ Note: In a two’s complement representation,
49// this conversion is conceptual and there is no change in the bit pattern (if there
50// is no truncation). — end note ]
51// (3) If the destination type is signed, the value is unchanged if it can be represented
52// in the destination type (and bit-field width); otherwise, the value is
53// implementation-defined.
54//
55// B: ISO/IEC 14882:2011(E) p88 section 5 Expressions
56// (9) Many binary operators that expect operands of arithmetic or enumeration type
57// cause conversions and yield result types in a similar way. The purpose is to
58// yield a common type, which is also the type of the result. This pattern is called
59// the usual arithmetic conversions, which are defined as follows:
60// [...]
61// Otherwise, if both operands have signed integer types or both have unsigned
62// integer types, the operand with the type of lesser integer conversion rank shall be
63// converted to the type of the operand with greater rank.
64// — Otherwise, if the operand that has unsigned integer type has rank greater than
65// or equal to the rank of the type of the other operand, the operand with signed
66// integer type shall be converted to the type of the operand with unsigned integer type.
67//
68// C: ISO/IEC 14882:2011(E) p86 section 4.13 Integer conversion rank
69// [...] The rank of long long int shall be greater than the rank of long int,
70// which shall be greater than the rank of int, which shall be greater than the
71// rank of short int, which shall be greater than the rank of signed char.
72// — The rank of any unsigned integer type shall equal the rank of the corresponding
73// signed integer type.
74//
75// D: ISO/IEC 14882:2011(E) p75 section 3.9.1 Fundamental types
76// [...] Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo
77// 2^n where n is the number of bits in the value representation of that particular
78// size of integer.
79//
80// Note:
81// Other libraries do exist for safe integer operations which can detect the
82// possibility of overflow (SafeInt from MS and safe-iop in android).
83// Signed safe computation is also possible from the art header safe_math.h.
84
85template <typename T> class Modulo {
86    T mValue;
87
88public:
89    typedef typename std::make_signed<T>::type signedT;
90    typedef typename std::make_unsigned<T>::type unsignedT;
91
92    Modulo() { } // intentionally uninitialized data
93    Modulo(const T &value) { mValue = value; }
94    const T & value() const { return mValue; } // not assignable
95    signedT signedValue() const { return mValue; }
96    unsignedT unsignedValue() const { return mValue; }
97    void getValue(T *value) const { *value = mValue; } // more type safe than value()
98
99    // modular operations valid only if size of T <= size of S.
100    template <typename S>
101    __attribute__((no_sanitize("integer")))
102    Modulo<T> operator +=(const Modulo<S> &other) {
103        static_assert(sizeof(T) <= sizeof(S), "argument size mismatch");
104        mValue += other.unsignedValue();
105        return *this;
106    }
107
108    template <typename S>
109    __attribute__((no_sanitize("integer")))
110    Modulo<T> operator -=(const Modulo<S> &other) {
111        static_assert(sizeof(T) <= sizeof(S), "argument size mismatch");
112        mValue -= other.unsignedValue();
113        return *this;
114    }
115
116    // modular operations resulting in a value valid only at the smaller of the two
117    // Modulo base type sizes, but we only allow equal sizes to avoid confusion.
118    template <typename S>
119    __attribute__((no_sanitize("integer")))
120    const Modulo<T> operator +(const Modulo<S> &other) const {
121        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
122        return Modulo<T>(mValue + other.unsignedValue());
123    }
124
125    template <typename S>
126    __attribute__((no_sanitize("integer")))
127    const Modulo<T> operator -(const Modulo<S> &other) const {
128        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
129        return Modulo<T>(mValue - other.unsignedValue());
130    }
131
132    // modular operations that should be checked only at the smaller of
133    // the two type sizes, but we only allow equal sizes to avoid confusion.
134    //
135    // Caution: These relational and comparison operations are not equivalent to
136    // the base type operations.
137    template <typename S>
138    __attribute__((no_sanitize("integer")))
139    bool operator >(const Modulo<S> &other) const {
140        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
141        return static_cast<signedT>(mValue - other.unsignedValue()) > 0;
142    }
143
144    template <typename S>
145    __attribute__((no_sanitize("integer")))
146    bool operator >=(const Modulo<S> &other) const {
147        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
148        return static_cast<signedT>(mValue - other.unsignedValue()) >= 0;
149    }
150
151    template <typename S>
152    __attribute__((no_sanitize("integer")))
153    bool operator ==(const Modulo<S> &other) const {
154        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
155        return static_cast<signedT>(mValue - other.unsignedValue()) == 0;
156    }
157
158    template <typename S>
159    __attribute__((no_sanitize("integer")))
160    bool operator <=(const Modulo<S> &other) const {
161        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
162        return static_cast<signedT>(mValue - other.unsignedValue()) <= 0;
163    }
164
165    template <typename S>
166    __attribute__((no_sanitize("integer")))
167    bool operator <(const Modulo<S> &other) const {
168        static_assert(sizeof(T) == sizeof(S), "argument size mismatch");
169        return static_cast<signedT>(mValue - other.unsignedValue()) < 0;
170    }
171
172
173    // modular operations with a non-Modulo type allowed with wrapping
174    // because there should be no confusion as to the meaning.
175    template <typename S>
176    __attribute__((no_sanitize("integer")))
177    Modulo<T> operator +=(const S &other) {
178        mValue += unsignedT(other);
179        return *this;
180    }
181
182    template <typename S>
183    __attribute__((no_sanitize("integer")))
184    Modulo<T> operator -=(const S &other) {
185        mValue -= unsignedT(other);
186        return *this;
187    }
188
189    // modular operations with a non-Modulo type allowed with wrapping,
190    // but we restrict this only when size of T is greater than or equal to
191    // the size of S to avoid confusion with the nature of overflow.
192    //
193    // Use of this follows left-associative style.
194    //
195    // Note: a Modulo type may be promoted by using "differences" off of
196    // a larger sized type, but we do not automate this.
197    template <typename S>
198    __attribute__((no_sanitize("integer")))
199    const Modulo<T> operator +(const S &other) const {
200        static_assert(sizeof(T) >= sizeof(S), "argument size mismatch");
201        return Modulo<T>(mValue + unsignedT(other));
202    }
203
204    template <typename S>
205    __attribute__((no_sanitize("integer")))
206    const Modulo<T> operator -(const S &other) const {
207        static_assert(sizeof(T) >= sizeof(S), "argument size mismatch");
208        return Modulo<T>(mValue - unsignedT(other));
209    }
210
211    // multiply is intentionally omitted, but it is a common operator in
212    // modular arithmetic.
213
214    // shift operations are intentionally omitted, but perhaps useful.
215    // For example, left-shifting a negative number is undefined in C++11.
216};
217
218} // namespace android
219
220#endif /* ANDROID_MODULO_H */
221