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