| /* |
| * Copyright 2015 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #ifndef ANDROID_MODULO_H |
| #define ANDROID_MODULO_H |
| |
| namespace android { |
| |
| // Modulo class is used for intentionally wrapping variables such as |
| // counters and timers. |
| // |
| // It may also be used for variables whose computation depends on the |
| // associativity of addition or subtraction. |
| // |
| // Features: |
| // 1) Modulo checks type sizes before performing operations to ensure |
| // that the wrap points match. This is critical for safe modular arithmetic. |
| // 2) Modulo returns Modulo types from arithmetic operations, thereby |
| // avoiding unintentional use in a non-modular computation. A Modulo |
| // type is converted to its base non-Modulo type through the value() function. |
| // 3) Modulo separates out overflowable types from non-overflowable types. |
| // A signed overflow is technically undefined in C and C++. |
| // Modulo types do not participate in sanitization. |
| // 4) Modulo comparisons are based on signed differences to account for wrap; |
| // this is not the same as the direct comparison of values. |
| // 5) Safe use of binary arithmetic operations relies on conversions of |
| // signed operands to unsigned operands (which are modular arithmetic safe). |
| // Conversions which are implementation-defined are assumed to use 2's complement |
| // representation. (See A, B, C, D from the ISO/IEC FDIS 14882 |
| // Information technology — Programming languages — C++). |
| // |
| // A: ISO/IEC 14882:2011(E) p84 section 4.7 Integral conversions |
| // (2) If the destination type is unsigned, the resulting value is the least unsigned |
| // integer congruent to the source integer (modulo 2^n where n is the number of bits |
| // used to represent the unsigned type). [ Note: In a two’s complement representation, |
| // this conversion is conceptual and there is no change in the bit pattern (if there |
| // is no truncation). — end note ] |
| // (3) If the destination type is signed, the value is unchanged if it can be represented |
| // in the destination type (and bit-field width); otherwise, the value is |
| // implementation-defined. |
| // |
| // B: ISO/IEC 14882:2011(E) p88 section 5 Expressions |
| // (9) Many binary operators that expect operands of arithmetic or enumeration type |
| // cause conversions and yield result types in a similar way. The purpose is to |
| // yield a common type, which is also the type of the result. This pattern is called |
| // the usual arithmetic conversions, which are defined as follows: |
| // [...] |
| // Otherwise, if both operands have signed integer types or both have unsigned |
| // integer types, the operand with the type of lesser integer conversion rank shall be |
| // converted to the type of the operand with greater rank. |
| // — Otherwise, if the operand that has unsigned integer type has rank greater than |
| // or equal to the rank of the type of the other operand, the operand with signed |
| // integer type shall be converted to the type of the operand with unsigned integer type. |
| // |
| // C: ISO/IEC 14882:2011(E) p86 section 4.13 Integer conversion rank |
| // [...] The rank of long long int shall be greater than the rank of long int, |
| // which shall be greater than the rank of int, which shall be greater than the |
| // rank of short int, which shall be greater than the rank of signed char. |
| // — The rank of any unsigned integer type shall equal the rank of the corresponding |
| // signed integer type. |
| // |
| // D: ISO/IEC 14882:2011(E) p75 section 3.9.1 Fundamental types |
| // [...] Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo |
| // 2^n where n is the number of bits in the value representation of that particular |
| // size of integer. |
| // |
| // Note: |
| // Other libraries do exist for safe integer operations which can detect the |
| // possibility of overflow (SafeInt from MS and safe-iop in android). |
| // Signed safe computation is also possible from the art header safe_math.h. |
| |
| template <typename T> class Modulo { |
| T mValue; |
| |
| public: |
| typedef typename std::make_signed<T>::type signedT; |
| typedef typename std::make_unsigned<T>::type unsignedT; |
| |
| Modulo() { } // intentionally uninitialized data |
| Modulo(const T &value) { mValue = value; } |
| const T & value() const { return mValue; } // not assignable |
| signedT signedValue() const { return mValue; } |
| unsignedT unsignedValue() const { return mValue; } |
| void getValue(T *value) const { *value = mValue; } // more type safe than value() |
| |
| // modular operations valid only if size of T <= size of S. |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| Modulo<T> operator +=(const Modulo<S> &other) { |
| static_assert(sizeof(T) <= sizeof(S), "argument size mismatch"); |
| mValue += other.unsignedValue(); |
| return *this; |
| } |
| |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| Modulo<T> operator -=(const Modulo<S> &other) { |
| static_assert(sizeof(T) <= sizeof(S), "argument size mismatch"); |
| mValue -= other.unsignedValue(); |
| return *this; |
| } |
| |
| // modular operations resulting in a value valid only at the smaller of the two |
| // Modulo base type sizes, but we only allow equal sizes to avoid confusion. |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| const Modulo<T> operator +(const Modulo<S> &other) const { |
| static_assert(sizeof(T) == sizeof(S), "argument size mismatch"); |
| return Modulo<T>(mValue + other.unsignedValue()); |
| } |
| |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| const Modulo<T> operator -(const Modulo<S> &other) const { |
| static_assert(sizeof(T) == sizeof(S), "argument size mismatch"); |
| return Modulo<T>(mValue - other.unsignedValue()); |
| } |
| |
| // modular operations that should be checked only at the smaller of |
| // the two type sizes, but we only allow equal sizes to avoid confusion. |
| // |
| // Caution: These relational and comparison operations are not equivalent to |
| // the base type operations. |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| bool operator >(const Modulo<S> &other) const { |
| static_assert(sizeof(T) == sizeof(S), "argument size mismatch"); |
| return static_cast<signedT>(mValue - other.unsignedValue()) > 0; |
| } |
| |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| bool operator >=(const Modulo<S> &other) const { |
| static_assert(sizeof(T) == sizeof(S), "argument size mismatch"); |
| return static_cast<signedT>(mValue - other.unsignedValue()) >= 0; |
| } |
| |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| bool operator ==(const Modulo<S> &other) const { |
| static_assert(sizeof(T) == sizeof(S), "argument size mismatch"); |
| return static_cast<signedT>(mValue - other.unsignedValue()) == 0; |
| } |
| |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| bool operator <=(const Modulo<S> &other) const { |
| static_assert(sizeof(T) == sizeof(S), "argument size mismatch"); |
| return static_cast<signedT>(mValue - other.unsignedValue()) <= 0; |
| } |
| |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| bool operator <(const Modulo<S> &other) const { |
| static_assert(sizeof(T) == sizeof(S), "argument size mismatch"); |
| return static_cast<signedT>(mValue - other.unsignedValue()) < 0; |
| } |
| |
| |
| // modular operations with a non-Modulo type allowed with wrapping |
| // because there should be no confusion as to the meaning. |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| Modulo<T> operator +=(const S &other) { |
| mValue += unsignedT(other); |
| return *this; |
| } |
| |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| Modulo<T> operator -=(const S &other) { |
| mValue -= unsignedT(other); |
| return *this; |
| } |
| |
| // modular operations with a non-Modulo type allowed with wrapping, |
| // but we restrict this only when size of T is greater than or equal to |
| // the size of S to avoid confusion with the nature of overflow. |
| // |
| // Use of this follows left-associative style. |
| // |
| // Note: a Modulo type may be promoted by using "differences" off of |
| // a larger sized type, but we do not automate this. |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| const Modulo<T> operator +(const S &other) const { |
| static_assert(sizeof(T) >= sizeof(S), "argument size mismatch"); |
| return Modulo<T>(mValue + unsignedT(other)); |
| } |
| |
| template <typename S> |
| __attribute__((no_sanitize("integer"))) |
| const Modulo<T> operator -(const S &other) const { |
| static_assert(sizeof(T) >= sizeof(S), "argument size mismatch"); |
| return Modulo<T>(mValue - unsignedT(other)); |
| } |
| |
| // multiply is intentionally omitted, but it is a common operator in |
| // modular arithmetic. |
| |
| // shift operations are intentionally omitted, but perhaps useful. |
| // For example, left-shifting a negative number is undefined in C++11. |
| }; |
| |
| } // namespace android |
| |
| #endif /* ANDROID_MODULO_H */ |