220 lines
9.4 KiB
C++
220 lines
9.4 KiB
C++
/*
|
||
* 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 */
|