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 20 namespace 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 85 template <typename T> class Modulo { 86 T mValue; 87 88 public: 89 typedef typename std::make_signed<T>::type signedT; 90 typedef typename std::make_unsigned<T>::type unsignedT; 91 Modulo()92 Modulo() { } // intentionally uninitialized data Modulo(const T & value)93 Modulo(const T &value) { mValue = value; } value()94 const T & value() const { return mValue; } // not assignable signedValue()95 signedT signedValue() const { return mValue; } unsignedValue()96 unsignedT unsignedValue() const { return mValue; } getValue(T * value)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